Графическое решение ЗЛП

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

Пример 1. Фирма производит двемодели изделий. Для каждого изделия модели А требуется 3 кг электротехнической стали, а для изделия модели В – 4 кг. В течение недели фирма может получить от своих поставщиков 1700 кг стали. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели B – 30 мин. В неделю можно использовать 160 ч. машинного времени. Сколько изделий каждой модели следует выпускать в неделю, если каждое изделие модели А приносит 20$ прибыли, а каждое изделие модели B – 40$ прибыли.

Чтобы сформулировать эту задачу математически, обозначим через x₁ количество выпущенных за неделю изделий модели А, а через x₂ – количество изделий модели B.

Задача состоит в том, чтобы найти наилучшие значения x₁ и x₂ . Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют прибыль.

Целевая функция в данном случае будет иметь вид

Р = 20×x₁ + 40×x₂

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

В задачах линейного программирования знание производных недостаточно для определения максимального значения целевой функции, так как никаким вы­бором значений x₁ и x₂ нельзя получить нулевые значения этих производных.

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

С математической точки зрения для увеличения Р надо увеличить x₁ и x₂ , но суть проблемы состоит в том, что эти значения не могут увеличиваться неограниченно. Определим эти ограничения.

Так как x₁ и x₂ выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательными, т.е.

(33)

Ограничения на наличие металла и машинное время могут быть записаны следующим образом:

(34)

3×x₁+ 4×x₂ 1700 (для металла),

2×x₁+ 5×x₂ 1600 (для машинного времени).

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

Условия неотрицательности позволяют ограничиться рассмотрением положительного квадранта.

Границы определяются прямыми

(35)

3×x₁+ 4×x₂ = 1700,

2×x₁+ 5×x₂ = 1600.

Стрелка на каждой границе (рис. 8) указывает, с какой стороны прямой выполняется ограничение. Заштрихованная область 0ABC, содержащая точки, для которых соблюдаются условия (33) и (34), является областью допустимых решений.

Прямая 20x₁+ 40x₂ =8000, называемая линией уровня, перпендикулярна вектору-градиенту. Все точки этой линии соответствуют прибыли 8000$ (линия уровня может быть построена для любого значения целевой функции).

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

Определим координаты точки В:

3×x₁+ 4×x₂ = 1700

2×x₁+ 5×x₂ = 1600

Решая эту систему уравнений, получаем: x₁= 300; x₂ = 200.

Следовательно, максимальная прибыль составляет

P_max = 20×300 + 40×200 = 14000$.

Дата добавления: 2014-01-06