Геометрический метод

Теоретическое введение:

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

1) На плоскости, по осям которой отложены искомые переменные величины, строится система ограничений, указанная в задаче (то есть фактически решаем графически систему неравенств). Если она не имеет решения, то соответственно ЗЛП также не имеет решения. Если имеет, то обычно мы получаем некоторый многоугольник (он может быть не замкнут). Этот многоугольник представляет собой область допустимых решений ЗЛП.
2) Находим градиент целевой функции. Он представляет собой вектор, направленный в сторону наибольшего возрастания функции.

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

3) Строим так называемую линию уровня. Для этого приравниваем целевую функцию какой-либо константе. Очевидно, что мы получаем прямую, перпендикулярную градиенту.
4) Возможны два варианта:
1) Целевая функция на максимум: перемещаем линию уровня параллельно самой себе в направлении градиента. Для простоты будем считать, что ЗЛП имеет единственное оптимальное решение. Тогда последняя точка, лежащая на границе области допустимых решений ЗЛП, через которую пройдет линия уровня и будет представлять собой оптимальное решение.

Целевая функция на минимум: все аналогично пункту 1 за исключением того, что линию уровня нужно перемещать в сторону, противоположную градиенту.

Решение:

X₁ - кол-во свадебных тортов

X₂ - кол-во праздничных тортов

Целевая функция:

ѓ = 4x₁+3x₂max

Ограничения производственных мощностей:

2X1+3X2=60
2X1+X2=24 (1.0)

Максимальное значение

достигается на пересечении

(1) и (3) ограничений.

Решаем систему, состоящую

из (1) и (3)-ого уравнения

2X1+3X2=60
2X1+X2=24

Получим

X₁=3

X₂=18

Подставим в целевую функцию

ѓ(3;18) = 4*3+3*18 = 66

Т.е., наиболее выгодный план производства тортов будет: 3 свадебных торта и 18 праздничных тортов, что обеспечивает 66 ед. прибыли.