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

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

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

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

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

Замечание 1:

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

Замечание 2:

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

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

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

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

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

4. Переходим к новой симплекс таблице по следующим правилам:

   1. Меняем местами СП и БП соответствующие разрешающему элементу.

   2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:

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

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

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

5. Если все элементы в Z строке симплекс таблицы неотрицательны, то достигнуто оптимальное решение, которое равно .

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

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

Рассмотрим симплекс-метод для решения задачи Линейного программирования в случае, если существует .

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

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

СП БП		…		B
		…
…	…	…	…	…
		…
Z		…		0

1. Выбрать строку с наименьшим отрицательным свободным членом в B-столбце

2. Рассмотреть элементы s-ой строки.

   1. Если , следовательно, система несовместна, и задача Линейного программирования не имеет решений

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

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

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

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

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

6. Если в результате симплексного преобразования в столбце свободных членов B все еще есть отрицательные элементы, то необходимо применять п. 1-5 “Алгоритм 2 Симплекс преобразования на основе укороченных симплекс таблиц” до тех пор пока все элементы столбца свободных членов не будут положительными

7. Если в результате симплексного преобразования в столбце свободных членов B нет отрицательных элементов, тогда перейти к применению “Алгоритма 1 Симплекс преобразования на основе укороченных симплекс таблиц” (п.1-6)