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

Дата добавления: 2013-12-23; просмотров: 1474; Нарушение авторских прав

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

Некоторые определения

Задачи выпуклого программирования: целевая функция f и все функции

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

Задачи линейного программирования: все функции f и

являются линейными, так что множество допустимых решений Q оказывается выпуклым линейным многогранным множеством.

Рассмотренные задачи (слайды 8-10) - являются задачами линейного программирования (ЛП).

Любой вектор Х, удовлетворяющий ограничениям задачи ЛП, называется допустимым вектором.

Допустимый вектор, доставляющий maxилиminцелевой функции задачи ЛП, называется оптимальным вектором.

Задача планирования производства m(х) = max (30 х₁ + 40 х₂) x 1) х_1,х₂³ 0 2) 12х₁+ 4 х₂_£ 300 4 х₁+ 4 х₂_£ 120 3 х₁+ 12 х₂_£ 252

Основные этапы графического метода решения задач ЛП 1. Строятся прямые, уравнения которых получаются в результате замены в ограничениях 1) и 2) знаков неравенств на знаки точных равенств. 2. Находятся полуплоскости, определяемые каждым из ограничений задачи 3. Определяется область допустимых решений - ОДР (многоугольник решений) 4. Строится вектор С =(С1;С2) (C1 и C2 – коэффициенты при неизвестных в целевой функцииm(x)) 5. Строится линия уровня – как перпендикуляр к вектору С, проходящая через ОДР 6. Линия уровня передвигается в направлении вектора С (если задача поставлена на max) или в противоположном направлении (если задача поставлена на min). В результате находится либо точка оптимума (граничная точка линии уровня с ОДР), либо устанавливается неограниченность функции на множестве допустимых решений. 7. Определяются координаты точки оптимума, и вычисляется значение целевой функции в этой точке.

При нахождении решения задачи ЛП графическим методом могут встретиться следующие случаи:

Целевая функция m принимает Целевая функция m принимает max в любой

max в единственной точке А точке отрезка АВ

<== предыдущая лекция	\|	следующая лекция ==>
Некоторые определения	\|	Определение.