Графический метод решения задач ЛП

Вначале рассмотрим наиболее простой метод решения, применимый для случая, когда количество переменных не превосходит двух. Рассмотрим следующий пример.

Компания производит погрузчики и тележки. От одного погрузчика компания получает доход в размере $80 и от одной тележки в размере $40. Имеется три обрабатывающих цен- тра, на которых выполняются операции металлообработки, сварки и сборки, необходимые для производства любого из продуктов. Для интервала планирования, равного месяцу, за- дана предельная производственная мощность каждого обрабатывающего центра в часах, а также количество часов, необходимое на этом центре для производства одного погрузчика

и одной тележки. Эта информация задана в таблице.

Центр \ Изделие	Погрузчик Тележка (часы на ед.) (часы на ед.)	Общая мощность (часы)
Мет.обработка Сварка Сборка	6 4 2 3 9 3

Требуется составить допустимый план работ на месяц с максимальным доходом. Матема- тическая модель задачи может быть записана следующим образом.

80 x 1 + 40 x 2 → max,

 6 x 1



+ 4 x 2

≤ 2400

 2 x 1 + 3 x 2 ≤ 1500

 1 2



9 x + 3 x ≤ 2700

 x 1 ≥ 0, x 2 ≥ 0

где x 1 и x 2 – количества производимых погрузчиков и тележек соответственно.

Представим ограничения в виде следующего графика, где по осям (0 x 1) и (0 x 2) отклады- вается количество произведенных погрузчиков и тележек соответственно, а линии пред- ставляют ограничения на производственные мощности. Допустимая область задачи пред- ставлена в виде многоугольника.

Представим целевую функцию 80 x 1 + 40 x 2 = z с переменным значением z прерывистой линией. Любая точка (x 1, x 2) на линии 80 x 1 + 40 x 2 = z соответствует доходу в размере z. Перемещая ее параллельно себе самой, получаем разные значения дохода.

При x 1 = 0 значение z = 40 x 2. Следовательно, значение z увеличивается при увеличении x 2, т.е. при перемещении целевой функции вверх. При этом линия 80 x 1 + 40 x 2 = z не должна покинуть допустимую область.

Нетрудно заметить, что максимальный доход среди допустимых точек достигается в одной из вершин многоугольника ограничений. В данном случае в точке пересечения линий,

соответствующих ограничениям на металлообработку и сборку, x∗ = 200, x∗ = 300.

1 2

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

Возможные варианты решения задач ЛП

1) ЗЛП имеет единственное решение

x 2

✻

❇

❇

❇

❇

❇

600 ❇

❏ ❇

500 ❏ ❇

❏

❇

◗

◗ ❇

❏◗

❏◗❇◗

❇

❏ ◗

• ❏❇ ◗

❇ ◗

❆

❆

❆✟✟✯

❏ ◗

◗

❇ ❏ ◗

❇ ❏ ◗

❇ ❏ ◗

✲

◗

❆

❆ ❇ ❏ ◗

300 400 750 x 1

2) Не существует допустимого решения ЗЛП

3) ЗЛП имеет ∞ много оптимальных решений, которые называются альтернативными

4) Целевая функция ЗЛП неограничена (в допустимой области).

Дата добавления: 2015-07-08