Чтобы вычислить значения Z, умножим коэффициенты в каждом столбце на соответствующую строку значений прибыли на единицу продукции, и суммируем показатели внутри столбцов. Вначале все значения равны нулю:
| | | | | Количество |
| (1)0 | (3)0 | (1)0 | (0)0 | (12)0 |
| (4)0 | (3)0 | (0)0 | (1)0 | (24)0 |
| | | | | |
Последнее значение в строке Z указывает общую прибыль, связанную с данным решением. Так как начальное решение всегда состоит из переменных резерва, неудивительно, что прибыль равна 0.
Значения строки C-Z вычисляем, вычитая значения Z в каждом столбце из значения строки целевой функции для данного столбца. Таким образом, получаем:
Ряд переменных | | | | |
Целевой ряд (С) | | | | |
| | | | |
| | | | |
Завершенная таблица показана в таблице 5п-2. Табл. 5п-1. Основа начальной таблицы
| Прибыль за единицу для переменных | | Переменные | | Целевой ряд |
| | | | | | |
Переменные в решении | | | «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. Переменные, входящие в решение и покидающие решение
| 4 5 0 0 | |
Переменные в решении | | Решение |
0 Sj | 13 10 4 3 0 1 | 12/3 = 4 <- Наименьшее 24/3 = 8 положительное отношение |
Z C-Z | 0 0 0 0 4 5 0 0 Наибольшее положительное значение | |
Вернемся к рисунку 5п-2. Обратите внимание, что два ограничения пересекают ось Х2 в точках 4 и 8, это те два соотношения, которые мы только что вычислили. Вторая таблица будет описывать эту угловую точку; она будет показывать прибыль и количества, связанные с этой угловой точкой. Кроме того, она покажет, является эта точка оптимумом, или же нужно составлять другую таблицу.
Теперь можно начинать составление второй таблицы. Строка удаленной переменной преобразуется в новую опорную строку второй таблицы.
Это будет служить основой для составления других строк. Чтобы получить эту новую опорную строку,
мы просто делим каждый элемент в строке S на значение опорной строки (пересечение столбца ввода и строки удаленной переменной), которое равно 3. В результате получим следующие значения:
Новая опорная строка -
я ряд переменных, покцдаю-I щих решение во второй таб-I лице; основа для постро-I ения других рядов.
Количество решения
Значение опор- 1/3 ной строки
Эти числа становятся новой строкой Х2 второй таблицы.
Числа опорной строки используются для вычисления значений в других строках ограничений (в данном случае, единственная другая строка ограничений-строка S2). Процедура вычисления состоит из следующих этапов:
1. Найти значение на пересечении строки ограничений (т.е. строки S2) и колонки входной переменной. Это 3.
2. Умножить каждое число в новой опорной строке на это значение.
3. Вычесть полученные значения, столбец за столбцом, из текущих значений строки.
| | | | | Количество |
Текущее значение: | | | | | |
-Зх(опорный ряд) | -3(1/3) | -3(1) | -3(1/3) | -3(0) | -3(4) |
Новое значение ряда | | | | | |
Две новых строки показаны в таблице 5п-4. Таблица 5п-4. Частично законченная вторая таблица
| | | | | | |
| Переменные | | | | | Количество |
| в решении | | | | решения |
| | | | | | |
| | | | | | |
Теперь можно вычислить новую строку Z. Умножим строку прибыли на единицу продукции и коэффициенты в каждом столбце, для каждой строки. Затем суммируем результаты внутри каждого столбца. Таким образом, получаем:
Прибыль X.,
Новый ряд!
5(1/3) 0(3) 5/3
| | | Количество |
5(1) | 5(1/3) | 5(0) | 5(4) |
0(0) | 0(-1) | 0(1) | 0(12) |
| | | |
Затем мы вычисляем строку C-Z:
Законченная вторая таблица показана в таблице 5п-5. Мы видим, на данный момент самое большее, что мы можем сделать - это 4 единицы переменной Х2 (см.столбец количества решения, строка Х2), и что прибыль при Х2 = 4, Х] = О составит $20 (см.строку Z, столбец количества решения).
Тот факт, что в строке C-Z присутствует положительное значение, говорит нам, что полученное нами решение все еще не является оптимальным. Следовательно, нам нужно составить еще одну таблицу.
Таблица 5п-5. Законченная вторая таблица
| | | | | | |
| Переменные в решении | | | | | Количество решения |
| | | | | | |
| | | | | | |
| Z | | | | | |
| | | | -5/3 | | |