<<
>>

7.5. Симплекс-методОбщая идея симплекс-метода

Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс-метода распадается на ряд шагов.
На каждом шаге от данного базиса Б переходят к другому, новому базису Б1 с таким расчетом, чтобы значение функции Z уменьшалось,

т. е. ZEі < ZB. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис 2> , ДЛЯ которого Zfrk) есть искомый минимум для линейной функции Z, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

Алгоритм симплекс-метода

Рассмотрим систему ограничений и линейную форму вида:

anxl+anx2+... + alnxn=bl; а2ХХ1+а22Х2+... + а2пХп=Ь2\

атххх +ат2х2 + ... + атпхп=Ьт;

Zmm = с0 + с\х\ + С2Х2 + ••• + спхт

X/ > 0, і = 1, п.

Используя метод Жордана—Гаусса (приложение 11), приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения: хх, х2, ..., хг — базисные переменные; X^j, хп "" свободные переменные.

х\ =Pl — (Ctir+iXr+i + Щг+2хг+2 + ... + Otj nxn)\

x2 =p2-(a2r+ixr+l +a2r+2xr+2 + ... + a2nxn)\ (7.40)

Xr =Pr —(Qrr+\xr+\ + а/г+2*г+2 + +

^min = Yo ~ (Yr+l*r+l + Yr+2xr+2 + ••• + Y/Лі)- (7.41)

По последней системе ограничений и целевой функции Z построим табл. 7.5.

Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему.

1. В последней строке симплекс-таблицы находят наименьший положительный элемент, не считая свободного члена. Столбец, со-ответствующий этому элементу, считается разрешающим.

Симплекс-таблица \Свободные \ неиз- \ вест- \ ные Ба- \ зисные\ неиз- \ вестные \ Свободный член Xr? 2 х„ Pi «1гИ alr+2 *2 р2 а2г+1 a2H-2 Рг ^min Yo YrH Уг+2 Ъ

Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение).

Находят наименьшее йз этих симплекс-отношений, оно соответствует раз-решающей строке.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симлекс- таблицы.

После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной, и наоборот. Симплекс-таблица преобразована следующим образом (табл. 7.6).

Элемент табл. 7.6, соответствующий разрешающему элементу табл. 7.5, равен обратной величине разрешающего элемента.

Элементы строки табл. 7.6, соответствующие элементам разрешающей строки табл. 7.5, получаются путем деления соответствующих элементов табл. 7.5 на разрешающий элемент.

Элементы столбца табл. 7.6, соответствующие элементам разрешающего столбца табл. 7.5, получаются путем деления соответствующих элементов табл. 7.5 на разрешающий элемент и берутся с противоположным знаком.

Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 7.6, одна вер-

Преобразование симплекс-таблицы \ Свобод- \ ные не- \ извест- \ ные Ба- \ Свободный член Хг+1 зисные\ неиз- \ вестные \ Хг+2 Pi а1г+1 1 Щп а1г+2 а1г+2 «1г+2 а\г+2 а1г+2 агг+2 а1г+2 z У г+2 а\г+2

шина которого совпадает с разрешающим элементом, а другая — с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 7.6 будет равен соответствующему элементу табл. 7.5 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе — произведение элементов из двух неиспользованных вершин прямоугольника.

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

Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.

Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Пример 7.12. Решение задачи симплекс-методом:

-xj + х2 + х3 = 1;

" Xj — х2 + х4 = 1;

Xj + х2 + х5 = 2.

^max ~ 2Xj — X2 + 3x3 ~~ + x5-

Приведем задачу к виду, допускающему применение симплекс- алгоритма:

х3 = 1 - (-*! + х2); х4 = і - (*! - х2); х5 = 2 - (*! + Х2).

Подставим в выражение Zmax величины х3, х4, х5:

Дпах = 6*1 - 1Х2 + 3. По алгоритму целевая функция должна стремиться к минимуму:

Zmin = ~ ^max = - + 7х2 - 3 = - 3 - (6хх - 7х2). Составим симплекс-таблицу (табл. 7.7).

Таблица 7.7 >4. Свободные неизвест- \ ные Базисные неизвестные Свободный член *3 1 -1 1 х4 1 ш -1 х5 2 1 1 z -3 6 -7

т

Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен + 6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Ми-нимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной х4 и столбца — х{.

Переходим к следующей таблице, используя правило прямоугольника (табл. 7.8): Свободные неизвест- Свободный Х\ х2 ные член Базисные неизвестные *3 2 1 0 х4 1 1 -1 1 -1 2 z -9 -6 -1

В последней строке нет положительных элементов, следовательно, оптимальное решение найдено:

^min — — 9; X = (0; 0; 2; 1; 1); Zmax = — Zmin = 9.

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 7.5. Симплекс-методОбщая идея симплекс-метода: