Графическое решение задачи линейного программирования

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

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

В каждой точке, принадлежащей внутренней области или границам многоугольника ABCDEF, все ограничения выполняются, поэтому решения, соответствующие этим точкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек, но, несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает целевая функция модели . Найдём среди множества точек из области решений совместной системы неравенств такие, которые придают линейной функции оптимальное значение. Для каждой точки плоскости функция z принимает фикси-

Рисунок 1.1 рованное значение . Множество всех таких точек есть прямая , перпендикулярная к вектору , выходящему из начала координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора , то линейная функция будет возрастать, а в противоположном направлении – убывать. Пусть при движении прямой z в положительном направлении вектора она впервые встретится с многоугольником решений в его вершине, тогда в этом положении прямая z становится опорной, и на этой прямой функция z принимает наименьшее значение. При дальнейшем движении в том же направлении прямая z пройдёт через другую вершину многоугольника решений, выходя из области решений, и станет также опорной прямой ; на ней функция z принимает наибольшее значение среди всех значений z, принимаемых на многоугольнике решений.

Таким образом, минимизация и максимизация линейной функции на многоугольнике решений достигаются в точках пересечения этого многоугольника с опорными прямыми , нормальными к вектору . Это пересечение опорной прямой может быть в одной точке (вершине многоугольника) либо в бесконечном множестве точек (это множество есть сторона многоугольника). На рисунке 1.1 видно, что оптимальному решению соответствует точка С. Так как точка С является точкой пересечения прямых (1) и (2), значения и в этой точке определяются решением следующей системы двух уравнений:

Решение указанной системы уравнений дает следующий результат: , . Полученное решение означает, что суточный объём производства краски (Н) должен быть т, а краски (В) - т. Доход, получаемый в этом случае, составит тыс. долл.