Геометрическая интерпретация симплекс-метода

Мы уже знакомы с геометрической интерпретацией задачи линейного программирования (п. 1.6.). Рассмотрим теперь симплекс-метод также с геометрической точки зрения. Суть дела проясняет следующая теорема.

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

Доказательство. Докажем первое утверждение теоремы. Пусть - угловая точка. Пусть отрезок целиком лежит в ОДР, и его середина совпадает с :

(1)

Векторное равенство (1) равносильно системе равенств для координат

(2)

Если - свободная переменная опорного решения , то из (2) следует, что

(3)

Поскольку и - допустимые решения, то и Сумма двух отрицательных чисел может равняться нулю, только, если эти числа сами равны нулю:

и (4)

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

Доказательство второго утверждения довольно сложное и мы его не приводим.

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

Дата добавления: 2014-12-26