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

Свойства задач ЛП

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

Будем рассматривать каноническую задачу, в которой система ограничений – система уравнений.

Теорема 4. Множество всех допустимых решений системы ограничений ЗЛП (задачи линейного программирования)является выпуклым, т.е. является выпуклым многогранником (или выпуклой многогранной областью). Будем называть в дальнейшем – многогранником решений.

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

Эта теорема является фундаментальной, т.к. она указывает принципиальный путь решения ЗЛП. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений.

Теорема 6. Каждому допустимому базисному решению ЗЛП соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Из теорем 5 и 6 вытекает следствие: если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.

Итак, оптимум линейной функции ЗЛП следует искать среди конечного числа ее допустимых базисных решений.

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

Рассмотрим задачу в стандартной форме (1.4) – (1.6)

Найти такой план Х = (Х1, Х2, …, Хn) выпуска продукции, удовлетворяющий системе

а11*Х1 + а12*Х2 + … + а1n*Xn <= В1

а21*Х1 + а22*Х2 + … + а2n*Xn <= В2 (1.4)

………………………….

аm1*Х1 + аm2*Х2 + … + аmn*Xn <= Вm

и условию Х1>=0, X2>=0, …, Xn>=0, (1.5)

при котором функция

F = С1*Х1 + С2*Х2 + … + Сn*Xn (1.6)

принимает макс значение.

с двумя переменными (n=2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т.е. n – m = 2.

ABCDE – геометрическое изображение системы ограничений. Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F = С1*Х1 + С2*Х2 принимает макс или мин значение.

Рассмотрим линию, вдоль которой функция принимает одно и то же фиксированное значение а, т.е. F = а, или

с1*х1 + с2*х2 = а.

На многоугольнике решений следует найти точку, через которую проходит такая линия функции с наибольшим (при макс функции) или наименьшим (при мин функции) значением.

Уравнение линии с1*х1 + с2*х2 = а – это уравнение прямой линии. При различных значениях а линии будут параллельны, т.к. их угловые коэффициенты определяются соотношением между коэффициентами с1 и с2 и, следовательно равны.

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

Может быть неограниченная прямоугольная область:

В данном примере есть мин, но нет макс.

В вышеприведенных примерах макс и мин достигались в одной точке, т.е. задача имела единственное решение.

А

Могут быть другие варианты:

			с1 с2

На левом рисунке видно, что линия уровня с макс уровнем совпадает с граничной линией АВ многоугольника решений АВСD. Следовательно, на отрезке АВ линейная функция принимает одно и то же макс значение. Это значит, что задача имеет бесконечно много оптимальных решений (их задают координаты точек отрезка АВ), среди которых базисных оптимальных решений два – соответственно в угловых точках А и В. Точки отрезка АВ задаются уравнением соответствующей прямой, где с1 <= Х1<= c2.

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

На правом рисунке показано, что если перемещать линию уровня в направлении убывания линейной функции, то она всегда будет пересекать многоугольник решений, т.е. линейная функция неограниченно убывает (нет конечного оптимума).

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

Плюсы геометрического метода:

§ прост,

§ нагляден,

§ быстро получить ответ.

Минусы геометрического метода:

§ возможны технические погрешности,

§ можно применять, когда в задаче только 2 переменных.

Дата добавления: 2014-01-15