3. Лекция. Линейное программирование

Рассмотрим задачу.
Торговая фирма для продажи товара трех видов использует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида даны в таблице. Прибыль получаемая от реализации одной парии товаров 1 вида – 5 у.е. 2 вида – 8 у.е.

Ресурсы	Вид товара		Объем ресурсов
	1	2
Время	0,5	0,7	370
Площадь	0,1	0,3	90

Определить оптимальную структуру товарооборота, обеспечивающую фирме максимальную прибыль.

Решение задачи.
Математическая модель прямой задачи
Max Z= 5x₁+8x₂
0,5 x₁+0,7x₂  370
0,1 x₁+0,3x₂  90
x_1,2  0
Математическая модель двойственной задачи
Min Z’= 370y₁+90y₂
0,5y₁+0,1y₂  5
0,7у₁+0,3у₂  8
y₁,₂  0
Разберем экономический смысл переменных, входящих в модели и ограничений, составленных на основе условия задачи.
x₁ – количество товара первого вида, которое необходимо продавать согласно оптимальному плану.
х₂ – количество товара второго вида, которое необходимо продавать согласно оптимальному плану.
0,5 x₁+0,7x₂ – это условие показывает, сколько времени всего будет потрачено на продажу товаров первого и второго вида.
0,1 x₁+0,3x₂ – это условие показывает, сколько площади будет потрачено на продажу товаров первого и второго вида.
5x₁+8x₂ – выручка, полученная при продаже оптимального количества товаров первого и второго вида.
у₁ – цена одной единицы первого ресурса (1 часа работы продавца)
у₂ – цена одной единицы второго ресурса (1 м² площади торгового зала).
0,5y₁+0,1y₂ – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого вида.
0,7у₁+0,3у₂ это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий второго вида.
370y₁+90y₂ – это условие показывает, сколько всего денежных единиц будет потрачено на продажу изделий первого и второго вида.
Непосредственное решение состоит из построения нескольких прямых на плоскости XOY. Построение неравенств на плоскости состоит из построения соответствующих прямых и выбора нужной полуплоскости. Для выбора полуплоскости необходимо подставить какую-нибудь точку плоскости (чаще всего точку (0,0)) в соответствующее неравенство и о выполнении или невыполнении этого неравенства сделать вывод о том, какая именно полуплоскость соответствует неравенству.
Для построения прямых достаточно взять две точки.
Целевая функция приравнивается к 0 для возможности ее построения. Потом с помощью параллельного переноса функция цели двигается так, чтобы из положения секущей она стала касательной. В точке, где целевая функция становится касательной области допустимых значений и будет точка оптимального решения.
Построение системы ограничений для данной задачи дает следующую область ограничений.

Темным цветом показана область допустимых значений. Теперь, если построить целевую функцию на этом же графике, то видно, что при параллельном переносе из точки (0,0) она становится касательной в точке (600,100).

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

Решая эту систему, получаем, что для получения максимальной прибыли необходимо продавать 600 единиц товара первого вида и 100 товара второго вида. При этом максимальная выручка от продажи составит 600*5+100*8=3800 ден. ед.