Симплекс метод

(симплекс – это название многогранника размерность которого на 1 меньше количества вершин)

Симплекс метод – это численный метод решения задачи ЛП, основанный на направленном переборе опорных решений, обеспечивающим монотонное не убывание значения целевых функций на этом решении

Математическую основу этого перебора составляют жордановы исключения.

ОБОСНОВАНИЕ

Рассмотрим каноническую форму задачи:

Выведем условие оптимального опорного решения (они основаны на понятии условных оценок)

Пусть – опорное решение – базис опорного решения

– базисные столбцы

– базисные переменные

– небазисные столбцы

– небазисные переменные

Запишем нашу систему в этом базисе

Из линейной независимости столбцов получаем представление нашей системы в базисе

Найдем представление целевой функции в базисе

Используя (1) можем найти компоненты вектора :

ЗАМЕЧАНИЕ

Относительные оценки базисных переменных вычисляются по формуле (3).

ТЕОРЕМА

(достаточное условие оптимальности опорного решения)

Существует опорное решение , – его базис. Тогда если все относительные оценки , то – оптимальное решение задачи :

ДОКАЗАТЕЛЬСТВО

Воспользуется формулой (2):

ЗАМЕЧАНИЕ

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

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

ТЕОРЕМА

(достаточное условие неразрешимости второго типа)

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

ДОКАЗАТЕЛЬСТВО

Рассмотрим такие допустимые решения задачи, что

Оценим целевую функцию на множестве решений:

Значит, целевая функция неограниченна сверху. ¤

ТЕОРЕМА

(переход от одного опорного решения к другому)

Пусть – опорное решение, – его базис. Условие предыдущих 2х теорем не выполняются. Тогда, пусть S – номер небазисной переменной:

Тогда за один шаг жордановых исключений с разрешающим элементом ,будет получено новое опорное решение с базисом

Значение целевой функции для которого

Формальное описание симплекс метода

1. Построить начально опорное решение

2. Проверить условия оптимальности. Если выполняется, то заканчиваем

3. Проверить условия неразрешимости №2. Если выполняется, то заканчиваем

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

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ

Будем записывать нашу задачу в любом базисе в форме симплекс таблицы

Пусть – опорное решение, – его базис

Симплекс таблица имеет вид:

f