Задачи линейного программирования

В общем виде задача линейного программирования формулируется следующим образом: найти экстремум целевойфункции

(1)

при наличии линейных ограничений в виде равенств или неравенств

(2)

,

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

В этой задаче число неизвестных должно быть больше числа условий , иначе будет нарушено условие единственности решения, выполняющееся в оптимизационной задаче.

Пример выполнения задания 1

Найти максимум целевой функции Z=5х₁+7х₂при ограничениях х₁+4х₂≤ 16,

5х₁+х₂≤ 23,

х₁≥ 0,х₂≥ 0.

Чтобы найти решение графически, сначала следует изобразить многоугольник допустимых решений. Для этого заменяем в ограничениях знак «≤» на «=» и строим прямыех₁+4х₂=16 и 5х₁+х₂=23. Нетрудно заметить, что прямыех₁=0 их₂=0 (третье и четвертое ограничения) являются осями координатх₁их₂.

Отметим стрелками полуплоскости, которые удовлетворяют заданным неравенствам. Область, удовлетворяющая всем четырем неравенствам, будет областью (полигоном) допустимых решений. На рис. 1 полигон допустимых решений показан светло-серым цветом.

Теперь построим график ЦФ, приравняв Zк нулю (можно взять любое число). Обозначим этот график символамиZ₀.

Для максимизации ЦФ будем перемещать прямую линию в направлении градиента возрастания ЦФ до тех пор, пока прямая линия не достигнет границы полигона допустимых решений. Из рисунка 1 видно, что оптимум находится в точке A. Запишем приблизительные координаты этой точки:х₁= 4,х₂= 3.

Рис. 1 Полигон допустимых решений

На основании приближенного графического решения задачи ЛПР найдём точный ответ аналитически. Для этого используем метод подстановок. Из рисунка 1 видно, что точка оптимума находится на пересечении двух прямых:

х₁+4х₂=16,

5х₁+х₂=23.

Решим систему уравнений и найдем координаты х₁их₂:х₁=4,х₂=3. Затем полученные значениях₁их₂подставляем в ЦФ:

Z=5х₁+7х₂=5·4+7·3

Таким образом, максимальное значение ЦФ Z=41.

В ответ записываем значения х₁ = 4,х₂ = 3 иZ= 41.

Пример выполнения задания 2

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется три исходных продуктаS1,S2 иS3. Расходы продуктов и запасы этих продуктов на складе приведены в таблице:

Исходный продукт	Расход продуктов (в тоннах на 1 т. краски)		Запас продукта на складе (тонн)
	краска для внутренних работ	краска для внешних работ
S1	10	5	250
S2	20	20	500
S3	5	5	200

Выпуск 1 тонны краски для внутренних работ приносит предприятию прибыль в размере 200 денежных единиц (ден. ед.), для внешних работ - 200 ден. ед. Требуется определить, сколько краски каждого вида следует производить предприятию, чтобы получить максимальный доход (при соблюдении ограничений на ресурсы).

Задача состоит в том, чтобы найти максимум целевой функции

Z= 200х₁ + 200х₂при ограничениях

Построение математической модели рассмотрено в практическом занятии №1.

Для решения задачи графическим способом, нужно построить прямые трех ограничений, для этого достаточно задать по две точки для каждой из них.

10 х₁ + 5 х₂= 250: (0; 50) и (25; 0),

20 х₁ + 20 х₂= 500: (0; 25) и (25; 0),

5 х₁ + 5 х₂= 200: (0; 40) и (40; 0).

Учитывая неотрицательность переменных и знаки неравенств, получим область допустимых решений (ОДР).

Рис.2 Область допустимых решений

Оптимальное решение находится в одной из угловых точек ОДР. Найдем значение целевой функции в угловых точках:

Е(0; 0) = 200∙0 + 200∙0 = 0,

Е(0; 25) = 200∙0 + 200∙25 = 5000 ден.ед.,

Е(25; 0) = 200∙25 + 200∙0 = 5000 ден.ед.

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

Ответ: Для достижения максимальной прибыли в размере 5000 ден.ед. нужно выпустить 0 тонн краски для внутренних работ и 25 тонн краски для внешних работ или 25 тонн краски для внутренних работ и 0 тонн краски для внутренних работ.