Алгоритм геометрического метода решения задач ЛП

Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму:

 

1.Строим координатные оси Х₁ОХ₂ и с учетом коэффициентов математической модели выбираем масштаб.

 

2.Находим область допустимых решений (ОДР) системы ограничений математической модели.

 

3.Строим прямую целевой функции и показываем направление наискорейшего ее изменения (нормаль- gradL).

 

4.Линию целевой функции (линия уровня) перемещаем по направлению нормали для задач на максимум целевой функции и в противоположном направлении - для задач на минимум ЦФ.

 

Перемещение линии уровня через ОДР производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений. Эта точка будет точкой экстремума, и будет определять единственное решение задачи ЛП.

 

Если окажется, что линия уровня совпадает с одной из сторон ОДР, то задача ЛП будет иметь бесчисленное множество решений.

 

Если ОДР представляет неограниченную область, то целевая функция – неограниченна.

 

Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми.

 

5.Находим координаты точки экстремума и значение ЦФ в ней.

Рассмотрим задачу.

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

 

 

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

 

 

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

Решение задачи.

 

Математическая модель прямой задачи

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 ден. ед.