Теоретические аспекты геометрической интерпретации оптимальных планов
Из первой геометрической интерпретации решения ЗЛП в 2-мерном пространстве следует, что допустимое множество есть выпуклый многогранник, а оптимальный план находится, по крайней мере, в одной из вершин.
Определение 11. Вершиной многогранника D называется такая его точка, которая не может быть представлена в виде линейной комбинации двух других точек, принадлежащих данному многограннику. Другими словами, вершину MD нельзя представить в виде:
.
На рис. 1.11 показано, что точки M и N не являются вершинами многоугольника D, так как они могут быть представлены в виде линейной (выпуклой) комбинации, например, точек M1 и M2, а также точек N1 и N2 соответственно. Угловые точки A, B, C, E, F суть вершины многоугольника D, они не могут быть выражены в виде линейной комбинации любых других точек этого множества.
Теорема 1.1. Геометрическая интерпретация базисных допустимых планов (БДП).
Для того чтобы точка x = (x1, x2, …, xn )D была БДП необходимо и достаточно, чтобы она была угловой точкой (вершиной) множества допустимых планов D.
(Без доказательства).
Теорема 1.2. Если в ЗЛП множество допустимых планов не пусто и целевая функция ограничена, то существует хотя бы один оптимальный план. (Без доказательства).
B
N2
N
N1
A
М1
М
М2
C
Множество D
F
E
Рис.1.11. Геометрическая иллюстрация множества
допустимых планов D с выделением вершин
Теорема 1.3. Если оптимальный план ЗЛП единственный, то он находится в одной из вершин множества D.
(Без доказательства).
Теорема 1.4. Если целевая функция C(x) ЗЛП принимает максимальное значение в нескольких точках допустимого множества D, то она принимает такое же значение в любой другой точке, являющейся их линейной комбинацией.
(Без доказательства).
Резюмируя все вышесказанное, можно сделать следующий вывод. Так как оптимальный план в линейной задаче, если он существует, всегда находится в вершине выпуклого многогранника, а вершина есть БДП, то оптимальный план необходимо искать среди БДП.