§ 64. Постановка, различные формы записи и геометрическая интерпретация задач линейногопрограммирования

п

F = C&i + С2х2 +...

мжі

где С,j — некоторые действительные числа.

Процесс построения математической модели конкретной задачи линейного программирования включает а себя три основных этапа:

выбор переменных;

построение целевой функции;

учёт всех ограничений, которые налагаются на переменные.

Рассмотрим следующую задачу.

Для изготовления двух видов изделий а и b предприятие имеет 96 единиц сырья, причем на изготовление изделия а расходуется 8 единиц, а на b — 6 единиц сырья. Прибыль от реализации изделия a — 4 условных единицы, а от изделия 6—5 усл. ед. Определить план производства изделий, который обеспечит наибольшую прибыль от их реализации, если требуется изготовить не 6o.rfee 9 изделий а и не более 12 изделий b

Построим математическую модель для дайной задачи.

Обозначим через х\ объём производства изделия at а через — объем производства изделия Ь.

Прибыль F = 4xi + §х2 от реализации изделий х\ и х2 должна быть максимальна.

Ограничения: на расход сырья 8хі -Ь- 6х2 ^ 96, на объём произ-водства xi ^ 9, х2 4 12, х\ ^ 0, х2 ^ О.

Таким образом, задача записывается так: среди всех неотрицательных решений системы неравенств

+ б з; 2 < 95, х% ^ 9, із ^ 12т

^ 0, За ^ О

найти такое, при котором функция F = 4- принимает макси-мальное значение.

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции п

F = ? (І)

при условиях

п

Ё a^ssv < ?1 - ТГк - 1 т 2,..- t /г; (2)

v*=l

п _____

Е gfivxi, = bM, р**к + 1,т = к + ик + 2,.:,т; (3)

і

xv > 0, v-I^-l, /^п, (4)

где ctiiy, 6Jt, С„ — заданные постоянные величины и к ^ тп.

Функция (J) называется целевой функцией задачи (1)-(4), а условия (2)-(4) ограничениями данной задачи.

Стандартной (или симметричной) задачей линейного программира* шия называется задача, которая состоит в определении маічсимально- го значения функции (I) при выполнении условия (2) и (4), где к — - т, І — п.

Основной (клй канонической) задачей линейного программировании называется задача, которая состоит в определен ЕЖ максимального значений функции (]) при выполнении условий (3) и (-1), где fe — О, I ~ п.

Совокупность чисел X — («ь^а, - i^nlt удовлетворяющих ограничениям задачи (2)—(4) называется допустимым решением или планом.

План, при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции Fy можно перейти к нахождению максимума функции JFj — — F, так как min F — = -max(-F).

Ограничение-неравенство исходной задачи линейного программи- ропания^ имеющее вид преобразуется в ограничение-равенство

добавлением к

его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида — в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной.

х — у - х + у

576

ІМІ Постановка, форми записи за дач линейного программирования 577

Системы уравнений 2) н 5} решения не имеют, так как прямые параллельны.

Л(0 1). ва.0), с (|,i), I,(i,|).

j-іепустое множество планоу основной задачи линейного программирования образует выпуклый многогранник, каждая вершина которого определяет опорный план. Для одного из опорных планов {т, е. Й од-ной иэ вершин многогранник ре-шений) значение целевой функции является максимальным, при условии, что функция ограничена сверху на множестве планов Для того, чтобы записать множество опти-мальны* планов при достижении экстремального значення целевой функции на некотором отрезке А В многоугольника решений, необхо-димо определить координаты вер-шин И и В и вычислить значе-ния функции в этих точках, при

этом F(A) = F(B). Тогда множе- Рис. 13а

ство оптимальных планов можно

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

t А

х \ — adtf

+ (1 — o^zf, х'2 = -t- (1 - а)х%, где 0 < а < 1.

Вершину многогранника решений, в которой целевая функций достигает максимального (или минимального) значення можно найти графическим методом, если задача в стандартной форме содержит две или три переменных. Причем геометрический метод решения наиболее эффективен лишь при двух переменных, таи как в этом случае многогранник решений есть многоугольник. Для трёх переменных мно-гогранник решений ещё можно изобразить графически, а при четырёх и более переменных мы не можем его наглядно графически изобразить.

Графический метод решения задачи линейного программирования включает три основных момента:

а} построение множества допустимых РЕШЕНИЙ которое ОСЕЮВЫВЭ- ется на том факте, что уравнение вида Ахі Л- Вх2 + О = 0 является уравнением прямой линии на плоскости Ох1X2 и разделяет её на две полуплоскости, определяемые неравенствами Ах і + Вх2 4- С > 0 и Axi 4- Вх2 + С < 0;

б) построение на плоскости Ох\х2 линии нулевого уровня для целевой функции F = С|,ті 4- С2х2 (т. е, прямой Сухі 4- С2х2 =0) и её вектора нормали n(Cj,C2);

в) нахождение максимального (минимального) значения целевой функции F, которое базируется на том факте, что вектор нормали

[9 Ю И.

[ГлД

578

Линвйноё программирование

nfC^Cs) указывает направление возрастания линейной функции F ~ = Ct^i + С2х2 (соответственно противоположный вектор С2) —

направление убываний)

Решим нашу задачу графическим методом.

а) Строим в системе координат Оххх2 прямые S^i - 96 (1), х\ — 9 (II) xi — 12 (ПО- Находим полуплоскости, определяемые нера-венствами. Многоугольником допустимых решений задачи является

пятиугольник ABCOD.

б) Строим вектор п = (4; 5) и перпендикулярно К нему прямую

4s, + 5х2 - о (IV). _

в) Перемещая прямую (IV) параллельно самой себе в направлении

вектора п} находим точку, в которой целевая функция F — 4xi + + 5^2 принимает наибольшее значение. Это будет точка А — последняя

общая точка передвигаемой пря-мой с многоугольником допустимых решений. Для определения координат точки А решим систему уравнений + 6^2 = 96 и х2 — В результате получим ап = З, Х2 = 12, a F^* — 72.

Для нахождения минимального значения целевой функции, пе~ ремещаем прямую (IV) в направлении» противоположном вектору п.. Последняя общая точка прямой (IV) и многограЕШика решений есть точка 0(0; 0). Следова-тельно, функция F в этой точке принимает минимальное значение

В каких точках многогранника решений целевая функция задачи линейного программирования достигает экстремальных вменений?

Какие точки выпуклого множества называются угловыми?

Как находятся вершины выпуклого множества?

J0. Как найти коордиЕіатьі любой точки отрезка, на котором целевая функция достигает экстремума?

И. Какие задачи линейного программирования можно решать гра-фическим методом?

12. Перечислите основные этапы графического метода решения задач лннейного программирования.

Упражнения

Построить на плоскости область решений системы линейных нера-венств н НЙКТИ экстремальные значения линешюй функции ^(агі, хг) в этой области.

J

F = 2х і + 4xj " ®ctr.

F = 2xi — 2xi — extr.

—х: + Заг2 > о, а;) + 2Х-2 ^ 5,

L a;i Х2 ^ 0;

(

Xi — < Oj —X] 4- х2 < 2, 4хі +3хг ? 36, Xi ^ x-z ^

F = Gxi + 2x2 — extr.

3.

xi — x2 ^ 2, xi < b, Зхі +X2 5і 3, —Xi + < 5, x2 xi ft G, x2 ^ 0;

Xi — 2x-z ^ 0,

F = -2xi - 3^2 ~ extr.

бо:! 4- $x2 ^ 27,

—ЛГ1 -1-3-2

xi ^ 0, X2 ^ 0;

Sxi +9X2 ^ 72, 7г;і + 2x2 ? 14,

—л;і -Ь ^ 2, F = 14xi H- Лх2 - extr.

Axi - 7x2 < 14,

xi ^ 0, X2 > 0;

Ответы

1. Fni* = Fmait ^Ffxt^a) = 10,

Xj = 3 - 3a, x-2 — 1 + l,5ctf 0 < л < 1,

2- Fm3|i = F[0; 0) - 0. FmBX - 0) = IS.

i,x2), si = 3-3*0 1, Fmax = F(6; 6) = 43

Fmы = ПО: 5) = "35, Гпіаи = F(0; 3) = —9.

F„a„ = F(x„rr3) ~ 23, - 2- I a, л* в- їг/313 i^W —

- ґ ^ 46 T 23 J 23 *