Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 200
Текст из файла (страница 200)
Рассмотрим следующую задачу линейного программирования в стандартной форме: Зх1 + хз + 2хз (29.53) максимизировать при условиях (29.54) (29.55) (29.56) (29.57) х1 + хз + Зхз < 30 2х1 + 2хз + бхз < 24 4х1 + хз + 2хз < Зб х1,х2,хз ~ О. (29.58) (29.59) (29.60) (29.61) Зх1 + хз + 2хз х4 = ЗΠ— х1 — х2 — Зхз хз = 24 — 2х1 — 2х2 — бхз ха = 36 — 4х1 — хз — 2хз Чтобы можно было применить симплекс-алгоритм, необходимо преобразовать данную задачу в каноническую форму, как описано в разделе 29.!. Вспомогательные переменные — это не просто элементы алгебраического преобразования, они являются содержательным алгоритмическим понятием. Напомним (см. Раздел 29.1), что каждой переменной соответствует ограничение неотрицательностн.
Будем говорить, что ограничение-равенство является строгим (бй)11) при определенном наборе значений его небазисных переменных, если при этих значениях базисная переменная данного ограничения становится равной нулю. Аналогично набор значений небазисных переменных, который делает базисную переменную отрицательной, нарушает данное ограничение.
Таким образом, вспомогательные переменные наглядно показывают, насколько сильно каждое ограничение отличается от строгого, и тем самым помогают определить, насколько можно увеличить значения небазисных переменных, не нарушив ни одного ограничения. Свяжем с ограничениями (29.54)-(29.56) вспомогательные переменные ха, хб и ха соответственно и приведем задачу линейного программирования к канонической форме. В результате получится следующая задача: Глава г9. Линейное нрограммироеание 907 Х2 Хз Х6 хг =9 — — — — —— 4 2 4 (29.62) Система ограничений (29.59)-(29.61) содержит три уравнения и шесть переменных.
Любое задание значений переменных хм хз и хз определяет значения переменных х4, хз и х6, следовательно, существует бесконечное число решений данной системы уравнений. Решение является допустимым, если все хм хз,..., Х6 неотрицательны. Число допустимых решений также может быть бесконечным. Свойство бесконечности числа возможных решений подобной системы понадобится нам в дальнейших доказательствах. Рассмотрим блзиеиое решение (Ьаз1с зо!и!!оп): установим все (небазисные) переменные правой части равными нулю и вычислим значения (базисных) переменных левой части.
В данном примере базисным решением является (хм ха,...,ха) = (0,0,0,30,24,36), н ему соответствует целевое значение г = (3 0) + (1 0) + (2 0) = О. Заметим, что в этом базисном решении х, = 6, для всех ( Е В. Итерация симплекс-алгоритма переписывает множество уравнений и целевую функцию так, что в правой части оказывается другое множество переменных. Таким образом, с переписанной задачей связано другое базисное решение. Мы подчеркиваем, что такая перезапись никоим образом не меняет лежащую в основе задачу линейного программирования; задача на каждой итерации имеет точно то же множество допустимых решений, что и задача на предыдущей итерации. Однако эта задача имеет базисное решение, отличное от базисного решения предыдущей итерации. Если базисное решение является также допустимым, оно называется долуслеимым базисным решением.
В процессе работы симплегю-алгоритма базисное решение практически всегда будет допустимым базисным решением. Однако в разделе 29.5 мы покажем, что в нескольких первых итерациях симплекс-алгоритма базисное решение может не быть допустимым. На каждой итерации нашей целью является переформулнровка задачи линейного программирования таким образом, чтобы новое базисное решение имело большее целевое значение. Мы выбираем некоторую небазисную переменную х„ коэффициент при которой в целевой функции положителен, и увеличиваем ее значение настолько, насколько это возможно без нарушения существующих ограничений. Переменная х, становится базисной, а некоторая другая переменная хг становится небазисной. Значения остальных базисных переменных и целевой функции также могут измениться.
Продолжая изучение примера, рассмотрим возможность увеличения значения хь При увеличении х| значения переменных Х4, хь и Х6 уменьшаются. Поскольку на каждую переменную наложено ограничение неотрнцательности, ни одна из этих переменных ие должна стать отрицательной. Если х1 увеличить более чем на 30, то х4 станет отрицательным, а хз и ха стануг отрицательными прн увеличении х1 на 12 и 9 соответственно.
Третье ограничение (29.61) является самым строгим, именно оно определяет, насколько можно увеличить хь Следовательно, меняем ролями переменные хг и х6. Решив уравнение (29.61) относительно хы получим Чаете УИ. Избранные темы 90В Чтобы записать другие уравнения с ха в правой части, подставим вместо хз вы- ражение из (29.62). Для уравнения (29.59) получаем хз = 30 — хз — хз — Зхз Хз ХЗ Ха~ — (9 — — — — — — ) — хз — Зхз 4 2 4) Зхз 5хз ха — — — — + —. 4 2 4 = ЗО (29.63) = 21 Аналогично комбинируем уравнение (29.62) с ограничением (29.60) и целевой функцией (29.58) и записываем нашу задачу линейного программирования в сле- дующем виде: х2 хз Зхб 2=27+ — + — —— 4 2 4 Х2 ХЗ Ха х1 = 9 — — — — —— 4 2 4 Зхз 5хэ ха Х4=21 — — — — +— 4 2 4 Зхз Х6 хз = 6 — — 4хз+ — . 2 2 (29.64) (29.65) (29.66) (29.67) Эта операция называется замещением.
Как было показано выше, в процессе замещения выбираются небазисная переменная х„называемая вводимой неременной (еп1еппй чапаЫе), и базисная переменная хп называемая еыеодимой переменной (!еаьйп8 тапаЫе), которые затем меняются ролями. Задача, записанная уравнениями (29.64)-(29.67), эквивалентна задаче 29.58- 29.61. В процессе работы симплекс-алгоритма выполняются только операции переноса переменных из левой части уравнения в правую и обратно, а также подстановки одного уравнения в другое. Первая операция очевидным образом создает эквивалентную задачу, то же самое можно сказать и о второй операции (см.
упр. 29.3.3). Чтобы продемонстрировать эквивалентность указанных задач, убедимся, что исходное базисное решение (0,0,0,30,24,36) удовлетворяет новым уравнениям (29.65)-(29.67) и имеет целевое значение 27+(1/4) О+(1/2) 0 — (3/4) 36 = О. В базисном решении, связанном с новой задачей, новые небазисные переменные равны нулю. Таким образом, оно имеет вид (9,0,0,21,6,0), а соответствующее целевое значение х = 27. Простые арифметические действия позволяют убедиться, что данное решение также удовлетворяет уравнениям (29.59)-(29.61) и при подстановке в целевую функцию (29.58) имеет целевое значение (3 9) + (1 0) + (2 0) = 27. Продолжая рассмотрение примера, необходимо найти новую базисную переменную, значение которой можно увеличить.
Нет смысла увеличивать ха, посюльку при ее увеличении целевое значение уменьшается. Можно попробовать Увеличить хз или хз,' мы выбеРем хз. Насюлью можно Увеличить хз, чтобы не нарушить ни одно из ограничений? Ограничение (29.65) допускает увеличение, не превышающее 18, ограничение (29.66) — 42/5, а ограничение (29.67) — 3/2. Глава гя Ланвйаав аравраамираванив Третье ограничение снова оказывается самым строгим, следовательно, мы пере- писываем его так, чтобы хз было в левой части, а хб — в правой. Затем подставля- ем это новое УРавнение хз = 3/2 — Зхг/8 — хб/4+ха/8 в УРавнениЯ (29.64К29.66) и получаем новую эквивалентную задачу: 111 хг хз 11хб г= — + — — —— (29.68) 4 16 8 16 33 хг хб 5хб + (29.69) Х4 4 16 3 Зхг хз = — —— 8 16 Х5 Хб — +— (29.70) 2 8 4 8 69 Зхг Зхб хб х4 = — + — + — —— 4 16 8 16 (29.71) С этой системой связано базисное решение (33/4,0,3/2,69/4,0,0) с целевым значением 111/4.
Теперь единственная возможность увеличить целевое значение — увеличить хг. Имеющиеся ограничения задают верхние границы увеличения 132, 4 и оо соответственно. (Верхняя граница в ограничении (29.71) равна оо, поскольку при увеличении хг значение базисной переменной х4 также увеличивается. Следовательно, данное уравнение не налагает никаких ограничений на величину возможного увеличения хг.) Увеличиваем хг до 4 и делаем эту переменную базисной. Затем решаем уравнение (29.70) относительно хг, подставляем полученное выражения в другие уравнения и получаем новую задачу: хз хб 2хб г = 28 — — — — —— 6 6 3 ХЗ Х5 Хб Х4 =8+ — + — —— 6 6 3 8хз 2хб хб хг = 4 — — — — +— 3 3 3 ХЗ Х5 х4 = 18 — — + — .
2 2 (29.72) (29.73) (29.74) (29.75) В полученной задаче все коэффициенты целевой функции отрицательны. Как будет показано далее, такая ситуация возникает только тогда, когда базисное решение переписанной задачи линейного программирования является оптимальным ее решением. Таким образом, для данной задачи решение (8, 4,0, 18,0, 0) с целевым значением 28 является оптимальным. Теперь можно вернуться к исходной задаче линейного программирования, заданной уравнениями (29.53)-(29.57).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
