I этап. Запись задачи в симплекс-таблицу

Между системой ограничений задачи (10) и симплекс-таблицей взаимно однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений; а столбцов столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные – верхнюю строку таблицы. Каждая строка таблицы соответствует уравнению, при этом отрицательность коэффициентов при переменных в (11) запомнили в верхней строке как , , поэтому коэффициенты целевой функции записываются с противоположными знаками. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблице к другой должно увеличиваться. Итак, нашей системе ограничений соответствует таблица 2.5, и можно переходить ко второму этапу решения.

Таблица 2.5

свобод. базис			правые части
F	–5	–3

II этап. Проверка опорного плана на оптимальность.

Данной таблице 2.5 соответствует опорный план: . Свободные переменные равны 0, а базисные переменные принимают значения чисел столбца свободных членов. Значение целевой функции

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

Возможны ситуации:

1) в индексной F–строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу. Переходим к IV этапу;

2) в индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция неограниченно возрастает;

3) в индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к III этапу, улучшаем опорный план, пересчитывая таблицу.

III этап. Улучшение опорного плана.

1. Из отрицательных элементов индексной F–строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим .

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

В нашем примере, элемент – разрешающий. Строка, соответствующая этому элементу тоже называется разрешающей.

Таблица 2.6

свобод. базис			правые части
			80
F	–5	–3

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

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

3.2. На месте разрешающего элемента записываем обратное ему число

3.3. Элементы разрешающей строки делятся на разрешающий элемент.

3.4. Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком (см. табл. 2.7).

Таблица 2.7

свободные базис			правые части
			40

3.5. Все остальные элементы таблицы 2.6 пересчитываем по правилу прямоугольника (в любом порядке).

Правило прямоугольника:

Пусть мы хотим посчитать элемент, например . Соединяем пересчитываемый элемент мысленно с разрешающим, находим произведение .

Вычитаем произведение элементов, находящихся на другой диагонали получившегося прямоугольника. Разность делим на разрешающий элемент.

Итак, . Записываем 10 на место, где было 50.

Аналогично:

, , , .

Имеем в новом базисе пересчитанную таблицу 2.8.

Таблица 2.8

свободные базис			правые части
			40
			40

Базисными переменными теперь являются переменные . Значение целевой функции стало равно 200, т.е. увеличилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу.

Для этого проверим индексную строку и, увидев в ней отрицательный элемент , назовем ему соответствующий столбец – разрешающим. Составим соотношения правых частей к только положительным элементам разрешающего столбца, выберем среди них минимальное: . Определим разрешающий элемент 1, теперь пересчет осуществляем согласно правилам 3.1–3.5 (см. ниже).

базисные			правые части
			20

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