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

Методы решения задач оптимального планирования деятельности предприятия

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

Решение задачи графическим способом проводится в последовательности:

а) записывают уравнения граничных прямых и строят плоскости Х₁ 0 Х₂;

б) определяют полуплоскости, соответствующие исходным ограничениям-неравенствам. Для этого берут произвольную точку, лежащую по ту или иную сторону от граничной прямой и ее координаты подставляют в левую часть ограничения-неравенства. Если оно удовлетворяется, то искомой будет полуплоскость, которая содержит выбранную точку; если не удовлетворяется, то искомой будет полуплоскость, которой данная точка не принадлежит;

в) выделяют область допустимых решений задачи как общую часть m+2 полуплоскостей, где m полуплоскостей соответствует исходным неравенствам задачи, а две полуплоскости -

условию неотрицательности искомых переменных;

г) строят вектор V = (С₁; С₂)и перпендикулярно к нему одну из прямых семейства Z, например Z=0;

д) определяют экстремальную точку многоугольника решений путем параллельного перемещения вспомогательной прямой Z=0 в направлении вектора V;

е) вычисляют координаты оптимальной точки и значение функции Z .

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

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

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