Симплексные таблицы и алгоритм решения задач

Рассмотрим алгоритм решения задач симплексным методом[17].

1. Математическая модель задачи должна бать канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строки таблицы 1-го шага, за исключением строки D_j (индексная строка), заполняем по данным системы ограничений и целевой функции.

Симплексная таблица имеет следующий вид:

с_i	Базисная переменная (БП)	с₁	с₂	¼	с_m	с_m+1	¼	с_n	f (` X)
x₁	x₂	¼	x_m	x_m+1	¼	x_n	b₁
c₁	x₁			¼		h_{1, m+1}	¼	h_1n	l₁
c₂	x₂			¼		h_{2, m+1}	¼	h_2n	l₂
¼	¼	¼	¼	¼	¼	¼	¼	¼	¼
c_m	x_m			¼		h_{m, m+1}	¼	h_mn	l_m
	D _j			¼		D _m+1	¼	D _n	f (` X₁)

Индексная строка (D _j) для переменных находится по формуле

и для свободного члена по формуле

При этом возможны следующие случаи решения задачи на максимум:

- если все оценки D _j ³ 0, то найденное решение оптимальное;

- если хотя бы одна оценка D _j £ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f (X) ® ¥, т.е. целевая функция не ограничена в области допустимых решений;

- если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

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

Пусть одна оценка D _k £ 0 или наибольшая по абсолютной величине D _k £ 0, тогда k -й столбец принимают за ключевой (разрешающий). За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k -го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом.

3. Заполнение симплексной таблицы 2-го шага:

- переписывается ключевая строка, разделив ее элементы на ключевой элемент;

- заполняют базисные столбцы;

- остальные коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по приведенным выше формулам или по правилу «прямоугольника». Получается новое опорное решение, которое проверяется на оптимальность и т.д.

Примечание. Если целевая функция f (X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок D _j при всех .

Правило «прямоугольника» состоит в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m +1)-го столбца h_1,_m₊₁. Тогда элемент i -й строки (m+2)-го столбца 2-го шага, который обозначим , по правилу «прямоугольника» определяется по формуле

где h_1,_m₊₁, h_i_,_m₊₁, h_i_,_m₊₂ – элементы 1-го шага.