8x1 + 5х2 = 40

5х1 + 6х2 = 30

Оптимальный план задачи: х1 = 90/23 = 3,9; х2 = 40/23 = 1,7. Подставляя значения х1 и х2 в линейную функцию, получаем Zmax = 50 3,9 + 40 1,7 = 260,3

Таким образом, для того чтобы получить максимальную прибыль в размере 260,3 руб., необходимо запланировать производство 3,9 ед. продукции Р1 и 1,7 ед. продукции Р2.

Задача составления рациона. При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S1, не менее 8 ед. вещества S2 и не менее 12 ед. вещества S3. Для составления рациона используют два вида корма. Содержание количества елиниц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.2.

Таблица 2.2.

Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.

Решение.

Для составления математической модели обозначим через х1 и х2 соответственно количество килограммов корма 1 и 2 в дневном рационе. Принимая во внимание значения, приведенные в таблице 2.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений

3х1 + х2 9

х1 + 2х2 8

х1 + 6х2 12

х1 0, х2 0.

Если корм 1 не используется в рационе, то х1=0; в противном случае x1 0. Аналогично имеем х2 0. То есть должно выполняться условие неотрицательности переменных: х1 0, х2 0.

Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4х1 + 6х2 (коп.)

Требуется найти такие х1 и х2, при которых функция Z принимает минимальное. Таким образом, необходимо найти минимальное значение линейной функции Z = 4х1 + 6х2 при ограничениях

3х1 + х2 9

х1 + 2х2 8

х1 + 6х2 12

х1 0, х2 0.

Построим многоугольник решений (рис. 2.4). Для этого в системе координат х1Ох2 на плоскости изобразим граничные прямые

3х1 + х2 = 9 (L1)

х1 + 2х2 = 8 (L2)

х1 + 6х2 = 12 (L3)

х1 = 0, х2 = 0.

Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство (эти полуплоскости на рис. 2.4 показаны стрелками). В результате получим неограниченную многоугольную область с угловыми точками А, В, С, D.

Для построения прямой 4х1 + 6х2 = 0 строим радиус-вектор N = (4;6) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. 2.4 следует, она впервые коснется многогранника решений и станет опорной по отношению к нему в угловой точе В. Если прямую перемещать дальше в направлении вектора N, то значения линейной функции на многограннике решений возрастут, значит, в точке В линейная функция Z принимает минимальное значение.

Точка В лежит на пересечении прямых L1 и L2. Для определения ее координат решим систему уравнений

3x1 + х2 = 9

х1 + 2х2 = 8

Имеем: х1 = 2; х2 = 3. Подставляя значения х1 и х2 в линейную функцию, получаем Zmin = 4 2 + 6 3 = 26.

Таким образом, для того, чтобы обеспечить минимум затрат (26 коп. в день), необходимо дневной рацион составить из 2 кг корма 1 и 3 кг корма 2.

2.2. Обобщение графического метода решения задач линейного программирования.

Вообще, с помощью графического метода может быть ре-шена задача линейного программирования, система ограниче-ний которой содержит n неизвестных и m линейно независи-мых уравнений, если N и M связаны соотношением N – M = 2.

Действительно, пусть поставлена задача линейного программирования.

Найти минимальное значение линейной функции Z = С1х1+С2х2+ . +СNxN при ограничениях

a11x1 + a22x2 + . + a1NХN = b1

(2.3) a21x1 + a22x2 + . + a2NХN = b2

. . . . . . . . . . . . . . .

aМ1x1 + aМ2x2 + . + aМNХN = bМ

xj 0 (j = 1, 2, ., N)

где все уравнения линейно независимы и выполняется cоотношение N - M = 2.

Используя метод Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х1, х2, ., хM, а свободными - два последних: хМ+1, и хN, т. е. система ограничений приняла вид

x1 + a1,М+1xМ+1 + a1NХN = b1

(2.4) x2 + a2,М+1xМ+1 + a2NХN = b2

. . . . . . . . . . . .

xМ + aМ, М+1x2 + aМNХN = bМ

xj 0 (j = 1, 2, ., N)

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные - неотрицательные: хj 0 (j = 1, 2, ., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу.

Найти минимальное значение линейной функции Z = СМ+1хМ+1+СNxN при ограничениях

a1,М+1xМ+1 + a1NХN b1

a2,М+1xМ+1 + a2NХN b2

. . . . . . . . . .

aМ,М+1xМ+1 + aМNХN bМ

xМ+1 0, хN 0

Преобразованная задача содержит два неизвестных; решая ее графическим методом, находим оптимальные значения xМ+1 и хN, а затем, подставляя их в (2.4), находим оптимальные значения х1, х2, ., хM.

Пример.

Графическим методом найти оптимальный план задачи ли-нейного программирования, при котором линейная функция Z = 2х1 - х2 + х3 - 3х4 + 4х5 достигает максимального значения при ограничениях

х1 - х2 + 3х3 - 18х4 + 2х5 = -4

2х1 - х2 + 4х3 - 21х4 + 4х5 = 2

3х1 - 2х2 + 8х3 - 43х4 + 11х5 = 38

xj 0 (j = 1, 2, ., 5)

Решение.

Используя метод Жордана-Гаусса, произведем три полных исключения неизвестных х1, х2, х3. В результате приходим к системе

х1 + х4 - 3х5 = 6

х2 + 7х4 + 10х5 = 70

х3 - 4х4 + 5х5 = 20

Откуда x1 = 6 – х4 + 3x5, х2 = 70 – 7х4-10х5, х3 = 20 + 4х4 -5х5.

Подставляя эти значения в функцию и отбрасывая в системе базисные переменные, получаем задачу, выраженную только через свободные переменные х4 и х5: найти максимальное значение линейной функции Z = 6х4 + 15х5 – 38 при ограничениях