На шаге 2: :

На шаге 3 . Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4: .

2.3 Алгоритм метода искусственного базиса

Шаг 1. Приводим задачу ЛП к канонической форме:

(10)

с неотрицательными правыми частями .

Шаг 2. В каждую i-ю строку этих ограничений вводим искусственную переменную z_i и строим вспомогательную задачу ЛП вида

(11)

Эта задача имеет очевидное базисное допустимое решение .

Шаг 3. Для построенной вспомогательной задачи строим симплексную таблицу 2:

	b	x1…xn
ω	ωо
z1 … zm	b1 … bm

Таблица 2 – Симплекс-таблица для метод искусственного базиса

и находим оптимальное решение с помощью симплекс-метода.

Шаг 4. Если , то все переменные являются небазисными, а m переменных из войдут в базис и система ограничений, соответствующих оптимальной симплексной таблице, будет иметь вид:

(12)

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

Шаг 5. Если >0, то допустимого решения в исходной задачи не существует – процесс решения исходной задачи завершается.

2.4 Алгоритм метода Гомори

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

Шаг 1. Симплекс-методом находим оптимальное решение задачи без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В случае алгоритм завершает работу.

Шаг 2. Пусть оптимальная таблица имеет вид:

	B		…		…
L			…		…
			…		…
..	..	…………
			…		…
..	..	…………
			…		…

Таблица 3 – Симплекс таблица для специальной формы

Если - целые, то оптимальное решение является целочисленным. В этом случае вычисления заканчиваем.

Шаг 3. Среди дробных компонент таблицы выбираем элемент b_i с максимальной дробной частью β_i и по строке i составляем дополнительное ограничение:

; (13)

. (14)

Здесь - целая часть числа z (наибольшее целое число, не превышающее число z).

Шаг 4. Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение.

Переходим к шагу 2.

Замечание.

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

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

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