Количество
Текущее значение 3 О -1 1 12 JHoBoejjeHne onopHoroj 0/3 -V3 J/3 12/3=4
4. Вычислите значения для строки Х2: умножьте каждое новое значение опорной строки на опорное значение строки Х2 (то есть, 1:3), и вычтите результат из соответствующих текущих значений. Таким образом, получим:
Текущее значение 1/3 -1/Зх(опорный ряд) -1/3(1) Новое значение ряда О
| | | Количество |
| | | |
-1/3(0) | -1/3(-1/3) | -1/3(1/3) | -1/3(4) |
| | -1/9 | |
На ЭТОМ этапе будет полезно рассмотреть таблицы относительно графика области возможных решений. Это показано на рисунке 5п-10.
5. Вычислите новые значения строки Z. Обратите внимание, что теперь к решению добавляется переменная xi; прибыль на единицу в этой строке составляет $4.
Ряд Прибыль X, | | | | Количество |
Хг $5 5(0) | 5(1) | 5(4/9) | 5(-1/9) | 5(8/3) |
X, $4 4(1) | 4(0) | 4(-1/3) | 4(1/3). | 4(4) |
Новый ряд Z 4 | | | | 88/3 |
6. Вычислите значения строки C-Z: | | | |
| | | | |
С 4 | | | | |
Z 4 | | | | |
C-Z 0 | 0 | -8/9 | -7/9 | |
Полученные в результате значения третьей таблицы показаны в таблице 5п-7. Обратите внимание, что каждое из значений строки C-Z является нулевым или отрицательным, указывая на то, что это решение является окончательным. Оптимальные значения X] и Х2 обозначены в столбце количества: Х2 = 8/3, или 22/3, и Х] = 4. (Количество Х2 - в строке Х2, а количество Х) - в строке Х).) Общая прибыль составит 88/3, или 29,33 (столбец количества, строка Z).
Построение третьей таблицы
Третья таблица будет составлена тем же способом, что и предыдущая:
1. Определите входную переменную: найдите столбец с самым большим положительным значением в строке C-Z (7/3, в столбце xi).
2. Определите уходящую переменную: разделите количество решения в каждом ряду на опорную строку. В итоге получаем:
=12; 1Уз = 4
Меньшее отношение показывает уходящую переменную, S2 (см. табл.5п-6).
3. Разделите каждое значение в строке уходящей переменной на значение (3) опорной строки, чтобы получить значения новой опорной строки:
Таблица 5п-6. Выходящая и входящая переменные
| | | | | | | |
| Переменные в решении | | | «1 | | Количество решения | |
| | | | | | 4:1/3=12 | Уходящая |
| | | | | | 12/3=4 <- | переменная Sg |
| | | | | | | |
| | 7/3 Т | | -5/3 | | | |
Входящая переменная х,
2-я 21-таблица
таблица
Рис. 5п-10. Графические аналоги симплексных таблиц
Таблица 5п-7. Третья таблица содержит оптимальное решение
| | | | | | |
| Переменные | | | | | Количество |
| в решении | | | | | решения |
| | | | | -1/9 | |
| | | | -1/3 | | |
| | | | | | 88/3 |
| | | | -8/9 | -7/9 | |
Обработка ограничений типа > и =
До этого момента мы работали с ограничениями типа <. Ограничения типа равенства или > обрабатываются несколько иным способом.
Когда имеет место ограничение типа равенства, использование симплексного метода требует введения искусственной переменной.
Цель таких переменных - всего лишь обеспечить разработку начального решения. Например, мы имеем следующие равенства:
(1) 7x1 + 4x2=65
(2) 5х, + 3x2 = 40
Перепишем эти уравнения с искусственными пере-
«жгч:жкг-г-, менными aj И 32:
Искусственная переменная - переменная, вводимая в случае ограничения типа равенства с целью разработки начального решения.
(1) 7X1 + 4X2+la,+ 032= 65
(2) 5xi + 3x2+0ai+1а2 = 40
Добавлений резервных переменных не требуется. Целевая функция, например, Z = 2xi + 3x2 будет переписана следующим образом:
Z = 2xi+3x2 + Mai + Ma2,
где М = большое число (например, 999).
Так как искусственные переменные нежелательны в конечном решении, выбор большого значения М (намного большего, чем другие целевые коэффициенты) будет обеспечивать их стирание в процессе решения.
Для ограничения > переменные резерва должны быть вычтены, а не добавлены к каждому ограничению. Например, ограничения
(1) 3x1 + 2x2+ 4хз> 80
(2) 5х] + 4х2 + хз>70
(3) 2X1 +8X2+2хз>68
перепишем в виде равенств:
(1) 3x, + 2x2+4x3-lsi-0s2-0s3=80
(2) 5х,+ 4x2+ Хз-0si-ls2-0s3=70
(3) 2х, + 8x2+2x3-Os,-0s2-ls3= 68
Как равенства, каждое ограничение должно затем корректироваться включением искусственной переменной. Конечный результат выглядит таким образом:
(1) 3x1 +2x2+4x3-Is,-0s2- 0S3 + Iai+032+0аз= 80
(2) 5x1 + 4x2+ Хз-0si-lS2-0s3+0ai+1а2+0аз=70
(3) 2xi + 8x2+2x3- 0si-0s2-ls3+0ai+0a2+ 1аз = 68
Если целевая функция будет: 5xi + 2x2+ 7x3, то в итоге мы получим:
5x1 + 2x2 + 7хз + Osi + 0s2 + OS3 + Mai + Ма2 + Маз.
Резюме процедуры максимизации
Основные шаги к решению проблемы максимизации только с ограничениями типа <, используя симплексный алгоритм, следующие:
1. Составить начальную таблицу.
а. Переписать ограничения так, чтобы они стали равенствами; добавить резервную переменную излишка к каждому ограничению.
б. Переписать целевую функцию, включив резервные переменные. Коэффициенты этих переменных должны равняться 0.
в. Представить целевые коэффициенты и коэффициенты ограничения в форме таблицы.
г. Вычислить значения для строки Z; умножить значения в каждой строке ограничений на значение строки С. Сложить результаты в каждом столбце.
д. Вычислить значения строки C-Z.
2. Составить последующие таблицы.
а. Определить входную переменную (наибольшее положительное значение в строке C-Z). Если существует связь, выберите один столбец произвольно.
б. Определить уходящую переменную: разделите каждое значение в строке ограничения на значения опорной строки; наименьшее положительное отношение указывает уходящую переменную. Если возникает связь, разделите