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

Последнее значение в строке Z указывает общую прибыль, связанную с данным решением. Так как начальное решение всегда состоит из переменных резерва, неудивительно, что прибыль равна 0.

Значения строки C-Z вычисляем, вычитая значения Z в каждом столбце из значения строки целевой функции для данного столбца. Таким образом, получаем:

Завершенная таблица показана в таблице 5п-2. Табл. 5п-1. Основа начальной таблицы

Проверка на оптимальность

Если все значения в строке C-Z любой таблицы нулевые или отрицательные, то было получено оптимальное решение. В нашем случае строка C-Z содержит две положительных величины, 4 и 5, указывая на возможность дальнейшей оптимизации.

Построение второй таблицы

Значения в строке C-Z отражают потенциал прибыли для каждой единицы переменной в данном столбце. Например, значение4указывает, что каждая единица переменной XI, добавленная к решению, увеличит прибыль на $4. Аналогично, 5 указывает, что каждая единица Х2 прибавит $5 к прибыли. Выбирая между $4 на единицу и $5 на единицу, мы выбираем большее значение и сосредотачиваемся на том столбце, который означает, что Х2 будет входить в решение. Теперь мы должны определить, какая

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

Значения опорной стро- ?

ки - цифры в колонке вход- <i

ных переменых начальной f

таблицы, которые использу- f

Ют для определения пере- ;

менной, покидающей реше- п

ние. V

Чтобы определить, какая переменная покинет решение, мы используем цифры в тексте таблицы, в колонке входных переменных (т.е. 3 и 3). Они называются значениями опорной строки (row pivot values).

Поделим каждое из решений на соответствующее значение переменной, как показано в таблице 5п-3. Меньшее из этих двух отношений указывает переменную, которая покинет решение. Таким образом, переменная si покидает решение и заменяется на Х2. В графической интерпретации, мы продвинули ось Х2 к следующей угловой точке. Определяя наименьшее отношение, мы нашли ограничение, которое является наиболее критичным.

Таблица 5п-2. Начальная таблица

Таблица 5n-3. Переменные, входящие в решение и покидающие решение

Вернемся к рисунку 5п-2. Обратите внимание, что два ограничения пересекают ось Х2 в точках 4 и 8, это те два соотношения, которые мы только что вычислили. Вторая таблица будет описывать эту угловую точку; она будет показывать прибыль и количества, связанные с этой угловой точкой. Кроме того, она покажет, является эта точка оптимумом, или же нужно составлять другую таблицу.

Теперь можно начинать составление второй таблицы. Строка удаленной переменной преобразуется в новую опорную строку второй таблицы.

Это будет служить основой для составления других строк. Чтобы получить эту новую опорную строку,

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

Новая опорная строка -

я ряд переменных, покцдаю-I щих решение во второй таб-I лице; основа для постро-I ения других рядов.

Количество решения

Значение опор- 1/3 ной строки

Эти числа становятся новой строкой Х2 второй таблицы.

Числа опорной строки используются для вычисления значений в других строках ограничений (в данном случае, единственная другая строка ограничений-строка S2). Процедура вычисления состоит из следующих этапов:

1. Найти значение на пересечении строки ограничений (т.е. строки S2) и колонки входной переменной. Это 3.

2. Умножить каждое число в новой опорной строке на это значение.

3. Вычесть полученные значения, столбец за столбцом, из текущих значений строки.

Две новых строки показаны в таблице 5п-4. Таблица 5п-4. Частично законченная вторая таблица

Теперь можно вычислить новую строку Z. Умножим строку прибыли на единицу продукции и коэффициенты в каждом столбце, для каждой строки. Затем суммируем результаты внутри каждого столбца. Таким образом, получаем:

Прибыль X.,

Новый ряд!

5(1/3) 0(3) 5/3

Затем мы вычисляем строку C-Z:

Законченная вторая таблица показана в таблице 5п-5. Мы видим, на данный момент самое большее, что мы можем сделать - это 4 единицы переменной Х2 (см.столбец количества решения, строка Х2), и что прибыль при Х2 = 4, Х] = О составит $20 (см.строку Z, столбец количества решения).

Тот факт, что в строке C-Z присутствует положительное значение, говорит нам, что полученное нами решение все еще не является оптимальным. Следовательно, нам нужно составить еще одну таблицу.

Таблица 5п-5. Законченная вторая таблица