![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Графическое решение задачи линейного программирования
В данном разделе мы рассмотрим один из способов решения задачи фирмы Reddy Mikks. Так как модель содержит только две переменные, задачу можно решить графически. В случае трех переменных графическое решение задач становится менее наглядным, а при большем числе переменных — даже невозможным. Несмотря на это, графическое решение позволит сделать некоторые выводы, которые послужат основой для разработки общего метода решении ЛП. Первый шаг при использовании графического метода заключается в геометрическом представлении допустимых решений, т. е. построении области (допустимых) решений, в которой одновременно удовлетворяются псе ограничения модели. Искомая область (пространство) решений показана на рис. 2.1. Условия неотрицательности переменных Х1 ≥ 0 и Х2≥ 0 ограничивают область их допустимых значений первым квадрантом (представляющий собой но определению часть плоскости, расположенную над осью Х1 и правее оси Х2). Другие границы пространства решений изображены на плоскости Х1, Х2 прямыми линиями, построенными по уравнениям, которые получаются при замене знака ≤ на знак = в остальных ограничениях. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленные в сторону допустимых значений переменных. Полученное таким образом пространство решений — многоугольник АВСDЕF - нарис. 2.1.
В каждой точке, принадлежащейвнутренней области или гранам многоугольникарешений АВСDЕF, все ограничения выполняются, поэтому решения, соответствующие этим точкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает делена и функция модели z=3 Х1 + 2 Х2. На рис. 2.2 показано, как осуществляется такая операция. На график наносят ряд параллельных линии, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно порастающих значениях z, что позволяет определить наклон целевой функции и направление, в котором происходит ее увеличение (т. е. возрастание общего дохода). На рис. 2.2 были использованы следующие значения нелепой функции: z=6 и z=9. (Проверьте!) Чтобы найти оптимальное решение, следует перемещать прямую, характеризующую доход, в направлении возрастания целевой функции до тех нор, пока она не сместится в область недопустимых решений. На рис. 2.2 видно, что оптимальному решению соответствует точка С. Так как точка С является точкой пересечения прямых (I) и (2) (см. рис. 2.1), значения х1 и Х2 в этой точке определяются решением следующей системы двух уравнений: Х1+ 2 Х2 =6 3Х1 + Х2=8 Решение указанной системы уравнений дает следующий результат: Х1=31/3, Х2=11/3. Полученное решение означает, что суточный Рис. 2.2.
|