Решение симплекс-таблицы (правило прямоугольника)

Рассмотрим подробно, как производится пересчет симплекс-таблиц (на примере одной итерации). Пусть имеется симплекс-таблица представленная на Рис.1. Решается задача максимизации целевой функции. Разрешающий столбец соответствует переменной x₂, а разрешающая строка переменной x₃ (красные числа), на их пересечении находится разрешающий элемент (клетка с серым фоном). Первое, что нам необходимо сделать - это заменить базисную переменную. Разрешающая строка показывает, какая переменная должна быть выведена из базиса (в нашем случае x₃), а разрешающий столбец показывает какая переменная должна войти в базис (в нашем случае x₂). На Рис.2 факт замены базисной переменной акцентирован синей линией.

Теперь пересчитаем элементы стоящие в разрешающей строке. Для этого просто разделим каждый из них на разрешающий элемент (в нашем примере 4). А все элементы разрешающего столбца обнулим, кроме элемента стоящего в разрешающей строке. (Смотри Рис.2)

Остальные ячейки таблицы (кроме столбца "Отношение") пересчитываются по так называемому правилу прямоугольника, смысл которого проще всего понять на примере. Пусть нужно пересчитать элемент обведенный на Рис.1 красным контуром. Мысленно проводим от него вертикальную и горизонтальную линии до пересечения, с разрешающей строкой и разрешающим столбцом. Элементы стоящие в местах пересечения обведены синими контурами (Смотри Рис.1). Новое значение "красного" элемента будет равно нынешнему значению элемента минус произведение "синих" деленное на разрешающий ("серый") элемент (Смотри Рис.1). То есть :    18 - (64 * -1) / 4  =  34 , здесь знаком "*" показана операция умножения.
Записываем новое значение на прежнее место (Смотри Рис.2 красный контур).

Пользуясь данным правилом, заполняем все пустые элементы таблицы (кроме столбца "Отношение") Смотри Рис.3. После этого определим новый разрешающий столбец. Для этого проанализируем строку "Q" и так как наша задача на максимум, то найдем в ней максимальный положительный элемент, он и определит разрешающий столбец. В нашем случае это 3/2. Все элементы разрешающего столбца показаны красным шрифтом (Смотри Рис.3). Если после очередной итерации в строке "Q" не окажется положительных элементов - это значит что оптимальное решение достигнуто, итерации прекращаются. Если бы наша задача была на минимум, то разрешающий столбец определялся бы по минимальному отрицательному элементу, и если после очередной итерации в строке "Q" не окажется отрицательных элементов, значит достигнуто оптимальное решение.

Теперь заполним столбец "Отношение". Для этого нужно соответствующий (стоящий в той же строке) элемент столбца "Решение" разделить на соответствующий элемент разрешающего столбца (Смотри Рис.3). Обратите внимание, что данная операция проводится только для положительных элементов разрешающего столбца и строка "Q" в данной операции не участвует. Если после некоторой итерации в разрешающем столбце не окажется положительных элементов, то данная задача неразрешима ввиду неограниченности целевой функции, итерации прекращаются.

После заполнения столбца "Отношение" определим новую разрешающую строку. Она определяется минимальным элементом из столбца "Отношение". В нашем случае это 32, все элементы разрешающей строки показаны красным шрифтом (Смотри Рис.3). На этом очередная итерация заканчивается, на следующей итерации переменная x₂ будет выведена из базиса (об этом нам говорит новая разрешающая строка), ее место займет переменная x₁ (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.