Студопедия — Графический метод решения ЗЛП
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Графический метод решения ЗЛП






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

Рассмотрим ЗЛП с двумя переменными в однородной форме записи:

(1)
(2)
(3)

Рассмотрим вектор , который называется градиентом функции Z. Его компонентами являются частные производные целевой функции по соответствующим координатам, которые по своему смыслу представляют собой скорости возрастания функции Z вдоль осей Ox1 и Ox2 соответственно. Этот вектор показывает направление наискорейшего возрастания целевой функции. Вектор называется антиградиентом целевой функции, он показывает направление наискорейшего убывания целевой функции. Выберем произвольное значение целевой функции Z=Z0. Получим уравнение прямой Z0=c1x1+c2x2 в системе координат . Эту прямую также называют линией уровня целевой функции, то есть линией постоянного значения. Положим Z0= 0, получаем линию уровня, проходящую через начало координат. При Z>Z0 линия уровня будет лежать параллельно первоначальной дальше от начала координат в направлении вектора . Очевидно, что все линии уровня параллельны между собой и, соответственно, перпендикулярны векторам - планам задачи.

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

Рассмотрим вектор роста целевой функции на плоскости

 
 

Теперь рассмотрим нетривиальные ограничения (2) и запишем их в виде:

(4)

Множество решений (4) представляет собой полуплоскость, расположенную по одну из сторон прямой, уравнение которой:

(5)

Другими словами, эта прямая представляет собой границу полуплоскости. Если построить на плоскости все полуплоскости из системы (4), а затем учесть все тривиальные неравенства (3), которые локализуют допустимые решения ЗЛП в первом квадранте системы координат, то получим область, которая называется областью допустимых решений (ОДР) ЗЛП. Эта область на плоскости, если она является ограниченной, имеет вид выпуклого многоугольника.В общей теории линейного программирования доказывается, что ОДР представляет собой выпуклую область, то есть область, в которой любые две точки соединяются отрезком прямой, полностью лежащим в этой области. Важным следствием этого положения является тот факт, что оптимальное решение ЗЛП, если оно существует, обязательно будет находиться в угловой точке ОДР (в одной или в нескольких). Теперь, подводя итог всему сказанному, можно утверждать, что оптимальное решение ЗЛП находится в той угловой точке, из которой на направление вектора роста целевой функции опускается самый дальний от начала координат перпендикуляр. После нахождения оптимальной угловой точки надо найти её координаты как пересечение соответствующих границ, это будет оптимальный план. Далее определяем значение целевой функции в оптимальной точке, подставляя в эту функцию найденные координаты.

Пример. Решить графически следующую ЗЛП:

Построим, например, полуплоскость, отвечающую первому неравенству системы (1):

2 x 1 + 1 x 2 ≤ 400.

Эта полуплоскость делит координатную плоскость граничной линией, заданной уравнением:

2 x 1 + 1 x 2 = 400.

Линию, если она не проходит через начало координат, проще всего построить по двум точкам на осях координат. При х 1= 0 получаем х 2 = 400, а при х 2 = 0 получаем х 1 = 200. Соединяем эти две точки прямой линией, получаем две полуплоскости, выше и ниже этой прямой. Исходному неравенству отвечает только одна из этих полуплоскостей. Она определяется подстановкой в неравенство пробной точки, не лежащей на граничной прямой. Например, такой точкой может быть начало координат х 1 = х 2 = 0, т.е. 0 £ 400.

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

 

 
 

 

Аналогично построим и две другие полуплоскости, получим ОДР:

 

 
 

Теперь надо найти угловую точку ОДР, в которой целевая функция достигает максимума. Для этого построим вектор роста целевой функции = (60; 40), который состоит из коэффициентов целевой функции при соответствующих переменных. Вектор роста указывает направление наискорейшего возрастания целевой функции. Надо найти в ОДР точку, наиболее удаленную от начала координат в этом направлении. Для этого на направление вектора из всех угловых точек ОДР опускаем перпендикуляры. Оптимальному плану соответствует угловая точка, порождающая самый дальний от начала координат перпендикуляр. В нашем случае такая угловая точка образована пересечением границ 1-го и 2-го неравенств, поэтому эти неравенства запишутся как уравнения:

Решение этой системы даёт оптимальный план первоначальной задачи:

= 140; = 120.

Этот план дает значение целевой функции, равное 13200:

Таким образом, решение исходной задачи получено.

 

Теперь рассмотрим другие частные случаи ОДР на плоскости.

1. ОДР представляет собой не ограниченную в направлении вектора роста целевой функции многоугольную область. В этом случае оптимального решения не существует, целевая функция стремится к бесконечности:

2. ОДР состоит из единственной точки. Этот случай встречается крайне редко, и тогда задача имеет единственное допустимое решение, которое является одновременно оптимальным

3.
 
 

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

4. Задача имеет бесконечное множество оптимальных решений. Это происходит, когда две угловые точки ОДР являются оптимальными; следовательно, оптимальными являются и все точки, лежащие на участке границы между этими угловыми точками.

 

 

Замечание. Графическимметодом можно решить ЗЛП и с большим числом неизвестных, если в её канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением:

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







Дата добавления: 2015-08-12; просмотров: 4195. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Билет №7 (1 вопрос) Язык как средство общения и форма существования национальной культуры. Русский литературный язык как нормированная и обработанная форма общенародного языка Важнейшая функция языка - коммуникативная функция, т.е. функция общения Язык представлен в двух своих разновидностях...

Патристика и схоластика как этап в средневековой философии Основной задачей теологии является толкование Священного писания, доказательство существования Бога и формулировка догматов Церкви...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

Дезинфекция предметов ухода, инструментов однократного и многократного использования   Дезинфекция изделий медицинского назначения проводится с целью уничтожения патогенных и условно-патогенных микроорганизмов - вирусов (в т...

Машины и механизмы для нарезки овощей В зависимости от назначения овощерезательные машины подразделяются на две группы: машины для нарезки сырых и вареных овощей...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия