1.2. Геометрический метод решения задач лп

Существует несколько методов решения задач ЛП. Одним из способов решения задач оптимизации для двух переменных является геометрический метод.

Основные теоремы [7]

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

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

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

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

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

Алгоритм решения задач ЛП геометрическим методом [3]:

• Построение области допустимых решений (ОДР) с учетом системы ограничений.

• Построение вектора – вектора наискорейшего возрастания целевой функции.

• Проведение произвольной линии уровня, перпендикулярной вектору .

• Определение оптимального плана и оптимального значения целевой функции.

Варианты одр:

1. выпуклый многоугольник;

2. выпуклая многоугольная область;

3. пустое множество;

4. единственная точка.

Таблица 2

Соотношение вариантов ОДР и вариантов

оптимальных планов

Возможные варианты ОДР	Оптимальный план в соответствии с ОДР
1. Выпуклая многоугольная область	1. Координаты одной из угловых точек, задача имеет единственное решение. 2. Координаты точек отрезка, то есть все точки отрезка оптимальны. Ответ записывается как промежуток между координатами двух точек по оси и, являющихся крайними точками отрезка.
2. Выпуклая многоугольная область	1. Координаты одной из угловых точек. 2. или, то есть, задача имеет допустимые решения, но не имеет оптимального плана. 3. Координаты точек отрезка, то есть все точки отрезка оптимальны.
3. Пустое множество	1. , то есть, у задачи нет планов, она не имеет ни допустимых, ни оптимальных решений.
4. Единственная точка	1. Координаты точки.

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

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

Перед выполнением лабораторных работ №1, №2 и №3 ответьте на теоретические вопросы.