Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 183
Текст из файла (страница 183)
Избранные темы Система ограничений (29.62)-(29.64) содержит 3 уравнения и 6 переменных. Любое задание значений переменных хм хз и хз определяет значения переменных х4, хь и ха, следовательно, существует бесконечное число решений данной системы уравнений. Решение является допустимым, если все хз, хз,..., ха неотрицательны. Число допустимых решений также может быть бесконечным. Свойство бесконечности числа возможных решений подобной системы понадобится нам в дальнейших доказательствах. Рассмотрим базисное решение (Ьаз(с зо1пйоп): установим все (небазисные) переменные правой части равными 0 и вычислим значения (базисных) переменных левой части.
В данном примере базисным решением является (хз, хз,..., ха) = (О, О, О, 30, 24, Зб) и ему соответствует целевое значение з = (3 0) + (1 0) + (2. 0) = О. Заметим, что в этом базисном решении х; = 6; для всех г е В. Итерация симплекс-алгоритма переписывает множество уравнений и целевую функцию так, что в правой части оказывается другое множество переменных. Таким образом, с переписанной задачей связано другое базисное решение. Мы подчеркиваем, что такая перезапись никоим образом не меняет лежащую в основе задачу линейного программирования; задача на каждой итерации имеет точно то же множество допустимых решений, что и задача на предыдущей итерации. Однако эта задача имеет базисное решение, отличное от базисного решения предыдущей итерации.
Если базисное решение является также допустимым, оно называется донустимым базисным решением. В процессе работы симплекс-алгоритма базисное решение практически всегда будет допустимым базисным решением. Однако в разделе 29.5 мы покажем, что в нескольких первых итерациях симплекс-алгоритма базисное решение может не быть допустимым. На каждой итерации нашей целью является переформулироваиие задачи линейного программирования таким образом, чтобы новое базисное решение имело большее целевое значение.
Мы выбираем некоторую небазисную переменную х„ коэффициент при которой в целевой функции положителен, и увеличиваем ее значение настолько, насколько это возможно без нарушения существующих ограничений. Переменная х, становится базисной, а некоторая другая переменная х~ становится небазисной. Значения остальных базисных переменных и целевой функции также могут измениться. Продолжая изучение примера, рассмотрим возможность увеличения значения хз. При увеличении хз значения переменных х4, хь и ха уменьшаются.
Поскольку на каждую переменную наложено ограничение неотрицательности, ни одна из этих переменных не должна стать отрицательной. Если х~ увеличить более, чем на 30, то х4 станет отрицательной, а хь и ха стануг отрицательными при увеличении хг на 12 и 9 соответственно. Третье ограничение (29.64) является самым строгим, именно оно определяет, на сколько можно увеличить хп Следовательно, поменяем Глава 29. Линейное программирование 895 ролями переменные х1 и хб.
Решим уравнение (29.64) относительно х1 и получим Х2 ХЗ Хб Х1 = 9 — — — — —— 4 2 4 (29.65) Чтобы записать другие уравнения с хб в правой части, подставим вместо х1 выражение из (29.65). Для уравнения (29.62) получаем х4 = 30 — хз — х2 — Зхз— ( Х2 ХЗ Хб~ 9 — — — — — — ! — хг — Зхз 4 2 4/ ЗХ2 5ХЗ хб + 4 2 4 = 30— (29.66) = 21— Аналогично поступаем с ограничением (29.63) н целевой функцией (29.61) и за- писываем нашу задачу линейного программирования в следующем виде: Зхб 27+— Х2 4 Х2 9 —— 4 Зхз 21 —— 4 Зхз 6 —— 2 хз +— 2 хз (29.67) (29.68) х1 = 2 5хз 2 4 Хб (29.69) Х4 = +— 4 Хб +— 2 — 4хз (29.70) Эта операция называется замещением. Как было показано выше, в процессе замещения выбираются небазисная переменная х„называемая вводимой переменной (еп1еПп8 чаг1аЫе), и базисная переменная хн называемая выводимой леременной (1еач1л8 чапаЫе), которые затем меняются ролями.
Задача, записанная уравнениями (29.67К29.70), эквивалентна задаче (29.61)- (29.64). В процессе работы симплекс-алгоритма производятся толью операции переноса переменных из левой части уравнения в правую и наоборот, а также подстановки одного уравнения в другое. Первая операция, очевидно, создает эквивалентную задачу, то же можно сказать и о второй операции. Чтобы продемонстрировать эквивалентность указанных задач, убедимся, что исходное базисное решение (О, О, О, 30, 24, 36) удовлетворяет новым уравнениям (29.67)-(29.70) и имеет целевое значение 27+ (1/4) О+ (1/2) 0 — (3/4) 36 = О. В базисном решении, связанном с новой задачей, новые небазисные переменные равны О.
Таким образом, оно имеет вид (9,0,0,21,6, 0), а соответствующее целевое значение з = 27. Простые арифметические действия позволяют убедиться, что данное решение удовлетворяет уравнениям (29.62)-(29.64) и при подстановке в целевую функцию (29.61) имеет целевое значение (3. 9) + (1 0) + (2 0) = 27. Продолжая рассмотрение примера, необходимо найти новую базисную переменную, значение которой можно увеличить.
Нет смысла увеличивать хб, поскольку при ее увеличении целевое значение уменьшается. Можно попробовать Часть Чй. Избранные темы 896 увеличить хз или хз, мы выберем хз. Насколько можно увеличить хз, чтобы не нарушить ни одно из ограничений? Ограничение (29.68) допускает увеличение, не превышающее 18, ограничение (29.69) — 42/5, а ограничение (29.70) — 3/2. Третье ограничение снова оказывается самым строгим, следовательно, мы переписываем его так, чтобы хз было в левой части, а хз — в правой части. Затем подставляем это новое уравнение в уравнения (29.67)-(29.69) и получаем новую эквивалентную задачу: 111 — + 4 33 Х1 4 3 хз =— 2 69 Х4 = — + 4 Х2 Хз 11Х6 (29.71) 16 8 Х2 Хз — +— 16 8 Зхз Хз 16 5х6 (29.72) 16 Х6 (29.73) 8 4 8 Зхз 5хь х6 + —— (29.74) 16 8 16 С этой системой связано базисное решение (33/4, О, 3/2, 69/4, О, 0) с целевым значением 111/4.
Теперь единственная возможность увеличить целевое значение— увеличить 22. Имеющиеся ограничения задают верхние границы увеличения 132, 4 и оо соответственно (верхняя граница в ограничении (29.74) равна оо, поскольку при увеличении хз значение базисной переменной х4 также увеличивается. Следовательно, данное уравнение не налагает никаких ограничений на величину возможного увеличения х2). Увеличиваем х2 до 4 и делаем ее базисной. Затем решаем уравнение (29.73) относительно хз, подставляем полученное выражения в другие уравнения и получаем новую задачу: Хз 2Х6 хз 28 —— 6 хз 8+— 6 8хз 4 —— 3 Хз 18 —— 2 (29.75) 6 3 Хь Х6 +— (29.76) 6 3 2хз ха +— 3 (29.77) Х2 3 Хз + 2 (29.78) х4 = В полученной задаче все коэффициенты целевой функции отрицательны.
Как будет показано далее, такая ситуация возникает только тогда, когда базисное решение переписанной задачи линейного программирования является оптимальным ее решением. Таким образом, для данной задачи решение (8, 4, О, 18, О, 0) с целевым значением 28 является оптимальным. Теперь можно вернуться к исходной задаче линейного программирования, заданной уравнениями (29.56)-(29.60). Исходная задача содержит только переменные хы хз и хз, поэтому оптимальное Глава 29. Линейное программирование 897 решение имеет вид х! = 8, хз = 4, хз = О, с целевым значением (3 8) + (1 4) + + (2 0) = 28.
Заметим, что значения вспомогательных переменных в окончательном решении показывают, насколько велик резерв в каждом неравенстве. Вспомогательная переменная х4 равна 18„а значение левой части в неравенстве (29.57) равно 8+ 4+ 0 = 12, что на 18 меньше, чем значение правой части этого неравенства — 30. Вспомогательные переменные хь и ха равны О, и действительно, в неравенствах (29.58) и (29.59) левые и правые части равны. Обратите внимание на то, что даже если коэффициенты исходной канонической формы являются целочисленными, коэффициенты последующих эквивалентных задач не обязательно целочисленны, и не обязательно целочисленны и промежуточные решения.
Более того, окончательное решение задачи линейного программирования не обязательно будет целочисленным; в данном примере это просто совпадение. Замещение Формализуем процедуру замещения. Процедура Р!чс!т получает на входе каноническую форму задачи линейного программирования, заданную кортежем (Ф, В,А, Ь,с, о), индекс ! выводимой переменной х! и индекс е вводимой переменной х,. Она возвращает кортеж (Й, В, А, Ь, с, о), описывающий новую каноническую форму. (Еще раз напомним, что элементы матриц А и А являются числами, обратными коэффициентам канонической формы.) Р!уот(М,В,А,Ь,с,о,1,е) > Вычисление коэффициентов уравнения для новой базисной переменной х, 2 Ье ' Ь!/а!е 3 1ог (для) всех ! Е !!! — (е) 4 до аез е — ае/а!е 5 ае[ + 1/а!е 6 г Вычисление коэффициентов остальных ограничений 7 1ог (для) всех г Š — (1) 8 ао Ь! — Ь! — аееЬе 9 1ог (для) всех 3 Е Лг — (е) 10 йо ае " ае аееаеу 11 ац + — — аееа,! 12 [> Вычисление целевой функции !3 о ' — о+ себе 14 1ог (для) всех 3 Е Ф вЂ” (е) 15 оо с — су — сеаеу 16 с! е — — сеае! 898 Часть ЧП.
Избранные темы 17 [> Вычисление новых множеств базисных и небазисных переменных 18 Ф - 1Ч вЂ” (е) [.[(1) 19 В+-  — (Ц 0(е) 20 ге[игл (1Ч,В,А,б,с,[[) Процедура Р[уот работает следующим образом. В строках 2-5 вычисляются коэффициенты нового уравнения для х,; для этого уравнение, в левой части которого стоит х[, переписывается так, чтобы в левой части оказалась х . В строках 7-! 1 оставшиеся уравнения обновляются путем подстановки правой части полученного нового уравнения вместо всех вхождений х,. В строках 13-1б такая же подстановка выполняется для целевой функции, а в строках 18 и 19 обновляются множества небазисных и базисных переменных.
Строка 20 возвращает новую каноническую форму. Если а[, = О, вызов процедуры Рвот приведет к ошибке (деление на 0), однако, как будет показано в ходе доказательства лемм 29.2 и 29.12, данная процедура вызывается толью тогда, когда а[, ф О. Рассмотрим, как процедура Р[чот действует на значения переменных базисного решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
