Количество

Текущее значение 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) Новое значение ряда О

На ЭТОМ этапе будет полезно рассмотреть таблицы относительно графика области возможных решений. Это показано на рисунке 5п-10.

5. Вычислите новые значения строки Z. Обратите внимание, что теперь к решению добавляется переменная xi; прибыль на единицу в этой строке составляет $4.

Полученные в результате значения третьей таблицы показаны в таблице 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. Выходящая и входящая переменные

Входящая переменная х,

2-я 21-таблица

таблица

Рис. 5п-10. Графические аналоги симплексных таблиц

Таблица 5п-7. Третья таблица содержит оптимальное решение

Обработка ограничений типа > и =

До этого момента мы работали с ограничениями типа <. Ограничения типа равенства или > обрабатываются несколько иным способом.

Когда имеет место ограничение типа равенства, использование симплексного метода требует введения искусственной переменной.

Цель таких переменных - всего лишь обеспечить разработку начального решения. Например, мы имеем следующие равенства:

(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). Если существует связь, выберите один столбец произвольно.

б. Определить уходящую переменную: разделите каждое значение в строке ограничения на значения опорной строки; наименьшее положительное отношение указывает уходящую переменную. Если возникает связь, разделите