Графический метод решения ЗЛП
Графическим методом можно решать любые задачи линейного программирования (ЗЛП) с двумя переменными ( 
=2), а также ЗЛП с 
>2 переменными, если в ее канонической записи число неизвестных и число линейно независимых уравнений 
связаны соотношением 
.
Пример 6
Решим графически задачу ЛП, экономико-математическая модель которой составлена в примере 3.
;
Вначале построим многоугольник решений или ОДР задачи (рисунок 1). Для этого в системе координат 
на плоскости изобразим граничные прямые:
Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, например, начала координат. Ограничения (2.10) означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет многоугольник решений данной задачи (ОДР).
Для того, чтобы построить прямую 
=const, строим направляющий вектор 
, который перпендикулярен прямой Z. Прямая, проходящая через начало координат и перпендикулярная вектору 
, и будет прямая 
. Затем прямую 
, перемещаем параллельно самой себе в направлении вектора N по многоугольнику решений (ОДР) (рисунок 1). Последняя точка соприкосновения прямой с ОДР и есть оптимальное решение.
Рис. 1
Вектор указывает направление возрастания целевой функции Z. Оптимальное решение ЗЛП может достигаться лишь в точках, принадлежащих границе многоугольника решений. В нашем примере, как видно из рис. 1 функция Z принимает максимальное значение в точке 
. Точка лежит на пересечении прямых 
и 
. Для определения ее координат необходимо решить систему уравнений:
|
|
|
Откуда 
. Это и есть оптимальный план задачи. Подставив значение 
и 
в целевую функцию Z, получаем:
.
Таким образом, для того, чтобы получить максимальную прибыль в размере 56 ден. ед., необходимо запланировать выпуск 8 ед. продукции вида П1 и 4 ед. продукции П2.
Симплекс метод решения ЗЛП
Особенностью задач ЛП является то, что целевая функция достигает экстремума на границе области допустимых решений (ОДР).
Допустимый план, принадлежащий границе ОДР, называется опорным планом.
Алгоритм симплекс - метода
1) Находим какой-либо начальный опорный план 
.
2) Проверяем его на оптимальность. Если план оптимален, то задача решена, иначе переходим к пункту 3).
3) По правилам преобразования таблицы Жордана переходим к нехудшему опорному плану. Переходим к пункту 2).
С геометрической точки зрения перебор опорных планов можно толковать как переход по ребрам из одной вершины многогранника планов (области допустимых решений) в другую, по направлению к вершине 
, в которой целевая функция достигает экстремального значения.
|
|
|
Дата добавления: 2018-09-20; просмотров: 334; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!