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

В данном разделе мы рассмотрим один из способов решения задачи фирмы Reddy Mikks. Так как модель содержит только две переменные, задачу можно решить графически. В случае трех перемен­ных графическое решение задач становится менее наглядным, а при большем числе переменных — даже невозможным. Несмотря на это, графическое решение позволит сделать некоторые выводы, которые послужат основой для разработки общего метода решении ЛП.

Первый шаг при использовании графического метода заключает­ся в геометрическом представлении допустимых решений, т. е. построении области (допустимых) решений, в которой одновременно удовлетворяются псе ограничения модели. Искомая область (про­странство) решений показана на рис. 2.1. Условия неотрицательности переменных Х₁ ≥0 и Х₂≥0 ограничивают область их допусти­мых значений первым квадрантом (представляющий собой но определению часть плоскости, расположенную над осью Х₁ и правее оси Х₂). Другие границы пространства решений изображены на плоскости Х₁, Х₂ прямыми линиями, построенными по уравнениям, которые получаются при замене знака ≤ на знак = в остальных ограничениях. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленные в сторону допустимых значений переменных. Полученное таким образом пространство решений — многоугольник АВСDЕF -нарис. 2.1.

В каждой точке, принадлежащейвнутренней области или гра­нам многоугольникарешений АВСDЕF, все ограничения выполняются, поэтому решения, соответствующие этим точкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает делена и функция модели z=3 Х₁ + 2 Х₂. На рис. 2.2 показано, как осуществ­ляется такая операция. На график наносят ряд параллельных линии, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно порастающих значениях z, что позволяет определить наклон целевой функции и направление, в котором происходит ее увеличение (т. е. возрастание общего дохода). На рис. 2.2 были использованы следующие значения нелепой функции: z=6 и z=9. (Проверьте!)

Чтобы найти оптимальное решение, следует перемещать прямую, характеризующую доход, в направлении возрастания целевой функции до тех нор, пока она не сместится в область недопустимых решений. На рис. 2.2 видно, что оптимальному решению соответствует точка С. Так как точка С является точкой пересечения прямых (I) и (2) (см. рис. 2.1), значения х₁ и Х₂ в этой точке определяются решением следующей системы двух уравнений:

Х₁+ 2 Х₂ =6

3Х₁ + Х₂=8

Решение указанной системы уравнений дает следующий результат: Х₁=3¹/₃, Х₂=1¹/₃. Полученное решение означает, что суточный

Рис. 2.2.

Поиск по сайту: