Алгоритм 1 Симплекс преобразования на основе укороченных симплекс таблиц

 

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

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

Тогда укороченная симплекс таблица примет вид:

 

CП БП		…		B
		…
…	…	…	…	…
		…
Z		…

 

Замечание 1:

Для дальнейшего удобства обозначим элемент в Z строке и B столбце .

 

Замечание 2:

Данный алгоритм применим, если .

 

 

1. Выбирается разрешающий столбец l соответствующий наименьшему отрицательному элементу в Z строке

1. Выбирается разрешающая строка k, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца:

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

 

1. Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом:
2. Переходим к новой симплекс таблице по следующим правилам:
1. Меняем местами СП и БП соответствующие разрешающему элементу.
2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:

 

1. Все элементы разрешающей строки делятся на разрешающее число, включая элемент последнего столбца:

 

1. Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки, с обратным знаком:

 

1. Все остальные элементы матрицы вычисляются по формулам:

1. Если все элементы в Z строке симплекс таблицы неотрицательны, то достигнуто оптимальное решение, которое равно .
2. Если в Z строке симплекс таблицы найдется хотя бы один отрицательный элемент, то необходимо выполнить еще одно симплекс преобразование к симплекс таблице , согласно п.1-6 приведенного выше алгоритма.