Теорема 2. (Фундаментальная)

Теорема 1. (Геометрия системы ограничений ЗЛП).

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

Теорема 2. (Фундаментальная).

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

14. Теорема 3. (Геометрическая интерпретация допустимого базисного решения).

Каждому допустимому базисному решению ЗЛП соответствует вершина многогранника решений и наоборот: каждой вершине многогранника решений соответствует допустимое базисное решение.

Следствие из теорем 2 и 3.

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

15. Основные шаги по решению ЗПЛ графическим методом следующие:

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

2) построить линию уровня целевой функции,

3) двигать линию уровня в нужном направлении, пока не достигнем крайней точки области - оптимальной точки (или множества).

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

16. Возможность перехода от прямой задачи к двойственной (и наоборот) устанавливается теоремой двойственности: если одна из задач (1) или (2) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем оптимальные значения функции цели прямой и двойственной задач совпадают, т.е. max F(x) = min F(y).

При этом выполняются следующие правила:

1. Если на переменную x_i прямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.

2. Если на переменную xi прямой задачи не наложено условие неотрицательности, то i-е ограничение двойственной задачи записывается в виде строгого равенства.

3. Если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не накладывается условие неотрицательности.