Пример 1. Завод производит два вида продукции: велосипеды и мотоциклы

Завод производит два вида продукции: велосипеды и мотоциклы. При этом цех по сборке велосипедов имеет мощность 100 тыс. штук в год, цех по сборке мотоциклов — 30 тыс. Механические цеха завода оснащены взаимозаменяемым оборудованием, и одна группа цехов может производить либо детали для 120 тыс. велосипедов, либо детали для 40 тыс. мотоциклов, либо любую комбинацию деталей, ограниченную этими данными. Другая группа механических цехов может выпускать детали либо для 80 тыс. велосипедов, либо для 60 тыс. мотоциклов, либо любую допустимую их комбинацию. В результате реализации каждой тысячи велосипедов завод получает прибыль в 2 тыс. ден. ед., а каждой тысячи мотоциклов — 3 тыс. ден. ед. Найти такое сочетание объемов выпуска продукции, которое дает наибольшую сумму прибыли.

Найти оптимальный план выпуска велосипедов и мотоциклов по условиям.

Решение. В математической записи задача имеет вид:

Областью допустимых решений системы линейных неравенств будет многоугольник OABCD (рис. 2.6). Вектор имеет координаты с₁ =2, с₂ = 3. (Поскольку вектор нам необходим лишь для выяснения направления, то, сообразуясь с масштабом чертежа, можно для большей наглядности построить вектор . В данном случае построен вектор 5 .

Параллельным перемещением вспомогательной прямой f = 0, перпендикулярной к вектору 5 , находим точку С, в которой функция f достигает наибольшего значения. Решая совместно уравнения граничных прямых ВС и CD:

x₁/120+ +x₂/40 = 1 и x₁/80 + x₂/60 = 1,

находим координаты точки С: х₁ = 48, х₂ = 24; при этом f_max = 168.

Итак, выпускать следует 48 тыс. велосипедов и 24 тыс. мотоциклов; максимальная прибыль завода по этим видам продукции составит 168 тыс. ден. ед.

Задачи со многими переменными. Как указывалось, задачу со многими переменными можно решить графически, если в ее канонической записи присутствует не более двух свободных переменных, т.е. , где п — число переменных, r — ранг матрицы системы ограничительных уравнений задачи. Чтобы решить такую задачу, систему ограничительных уравнений надо преобразовать к разрешенному виду, т. е. выделить некоторый базис переменных. Затем базисные переменные следует опустить и перейти к эквивалентной системе неравенств. Целевая функция также должна быть выражена только через свободные переменные. Полученную двухмерную задачу решают обычным графическим методом. Найдя две координаты оптимального решения, подставляют их в ограничительные уравнения исходной задачи и определяют остальные координаты оптимального решения.

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

Пример 2.. Найти оптимальный план ЗЛП, используя графический способ.

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

(max)

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

Решение задачи приведено на рис. 2.8. Напомним, что на каждой граничной прямой одна из переменных исходной задачи обращается в нуль. Так, неравенству соответствует граничная прямая АВ с уравнением . Но указанное неравенство образовано из третьего уравнения системы путем отбрасывания переменной х₅, следовательно, на прямой АВ х₅ = 0.

Из рис. 2.8 видно, что наибольшего значения функция f достигает в точке А пересечения прямых АВ и АЕ (х₂ = 0), поэтому = 75, =0. Одновременно в этой вершине = 0. Значения других компонентов оптимального плана находим из уравнений , =200, =2375; при этом f_max=36500.