XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 22
Текст из файла (страница 22)
Для этого достаточно оптимальную симплекс-таблицу уже решенной задачи линейного программирования с ослабленными ограничениями (см. табл. 4.1, итерацию 1) дополнить новыми столбцами, соответствующими переменным ул, уя, новой строкой, соответствующей целевой функции ~р, и продолжить решение с использованием симплекс-таблиц (табл. 4.2). т Оптимальному решению У* = (6 0 6 О) соответствует оптит мальное решение Хо = (6 0) рассматриваемой полностью целочисленной задачи. Завершая рассмотрение примера, заметим, что из (4.1), (4.5) следует ограничение хг+ 2хз < 6. А прямая хг+2хз = = 6 отсекает (см.
рис. 4.4) ту часть множества допустимых решений задачи линейного программирования с ослабленными ограничениями, которая содержит ее оптимальное решение, не удовлетворяющее требованию целочисленности, и не содержит допустимых решений исходной полностью целочисленной задачи. 159 то из (4.8) получаем 7НУг = а+ 71 с1 Е Е. г'ея (4.10) сьуь -+ шах; Е л=г Е арлуь = б,, ь=г уь>0, 1=1,п, (4.6) 1=1,т, 7Нуг > 76 Е уеа (4.11) уь Е 1ЧО(0), )с=1,п. ,',),( ' — д)) у) — ()д* — д*) = д.
)ел (4.8) (4.9) 158 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Рассмотрим теперь полностью целочисленную задачу, представленную в стандартной форме: При этом будем считать, что при любых к = 1, п и 1= 1, т параметры сь, агл и 6; являются целыми числами. Решая задачу линейного программирования с ослабленными ограничениями, соответствующую (4.6), находим ее оптимальное решение У*.
Если оно удовлетворяет требованию целочисленности, то 1" — решение исходной задачи целочисленного программирования. В противном случае выбираем любое базисное переменное у,, которому в У* соответствует нецелое значение, и выписываем 1-ю строку опгпимальной симпленстабди ы: и У;+',~ оНУ)=А, (4.7) гно где л — множество индексов свободных переменных.
Полагая в (4.7), что все переменные целочисленные, полу- чаем х' огут )1 =або )ео Следовательно, для любых Ы) б Е существует такое д Е Е, что При этом если в (4.8) считать, что у; =1гас(об), 2 Е Я, О <76 < 11 7,=1гас(Д), 0<7;<1, д, = 1п1(оН), 2' 6 5, дг = 1пг(А), 4.2. Метод отсекающик плоскостей (метод Гомори) А так как левая часть равенства (4.10) является неотрицатель- ной, то с учетом (4.9) имеем д Е М0 (О) и, как следствие, Неравенство (4.11) представляет собой необходимое условие целочисленности исходной задачи.
Оно определяет новое дополнительное ограничение, известное как отсечение Гомори для полностью целочисленной задачи. Полученное ранее оптимальное решение задачи линейного программирования с ослабленными ограничениями не удовлетворяет новому ограничению (4.11), так как все небазисные переменные у, ) Е о, в этом оптимальном решении равны нулю и, как следствие, 7, < О. Метод Гомори часто называют дробным алеорипзмом. Это связано с тем, что все ненулевые коэффициенты нового ограничения (4.11) являются правильными дробями. Практическая реализация метода Гомори связана с последовательным выполнением следующих этапов.
Эт ап 1. Найти оптимальное решение задачи линейного программирования с ослабленными ограничениями, соответствующей исходной полностью целочисленной задаче (4.6). Перейти к этапу 2. Этап 2. Прекратить вычисления, если оптимальное решение задачи линейного программирования с ослабленными ограничениями удовлетворяет требованию целочисленности. В противном случае выбрать какое-либо базисное переменное у;, которому в оптимальном решении соответствует нецелое значение. Из оптимальной симплекс-таблицы выписать уравнение (4.7), содержащее это базисное переменное, и получить ограничение (4.11).
Перейти к этапу 3. 70 у) Ус+1 + ус+2 76 165 7 1 1 Уз+ У4 3 22 22 2 (4.12) 7 1 1 Уз+ — У4 — У5+ У6 =— 22 22 (4.13) лицы: 1 1 32 У1+ У4 У5— 7 7 7 7 1 7 У2+ Уз+ У4 22 22 2 160». ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Э т а.п 3 . В задачу линейного программирования с ослабленными ограничениями ввести ограничение (4.11), переходя к стандартной форме записи где у„+1 — новое неотрицательное переменное, у„+2 — ис- кусственное неотрицательное переменное. Найти оптимальное решение вновь полученной задачи линейного программирова- ния с ослабленными ограничениями и перейти к этапу 2. Пример 4.3.
Рассмотрим следующую полностью целочисленную задачу: 7х1+ 9х2 -+ шах; -х,+Зх,(6, х,+(1/7)х2(6, х1, х2 > О, х1, х2 Е 1Ч 0 (О~, которая может быть представлена в стандартной форме 7У1+9У2-4 шах; — у1+ 392+ уз = 6, 791+ у2+ У4 —— 36, уь ) О, )с = 1,4, уь Е Я0(0), й = 1,4, где у1 —— х1 У2 — — х2, а уз и у» — новые переменные задачи. В табл. 4.3 представлено решение задачи линейного программирования с ослабленными ограничениями, соответствующей рассматриваемой полностью целочисленной задаче. Ее т оптимальное решение 1" = (9/2 7/2 0 0) не удовлетворяет требованию целочисленности.
Выбираем У2 = 7/2 и выписываем соответствующее уравнение из оптимальной симплекс-таб- ».2. Метод отсекающмк плоскостей (метод Гомори) 161 Таблица 4.3 А так как в этом случае 72 = 1/2, 722 = 7/22, 724 —— 1/22, то новое ограничение имеет вид При переходе к стандартной форме записи этого ограничения вводим новое переменное модели у5 и искусственное перемен- НОЕ У6. Для продолжения решения задачи линейного программирования с ослабленными ограничениями, в которой учтено новое ограничение (4.13), воспользуемся уже известным приемом (см.
пример 4.2 и табл. 4.4). Вновь полученное оптимальное решение не удовлетворяет требованию целочисленности. Выбираем У1 = 32/7 и выписываем соответствующее уравнение из оптимальной симплекс-таблицы: Таблица 4.4 Ите- рация Базисные переменные Значе- ние У2 Уз Уг 32/7 3 11/7 4/7 1/7 О 1/7 !/7 ΠΠΠΠΠΠ— 1/7 1 -22/7 6/7 ΠΠΠ— 1 Уг Уг Уз Ув — 59 -4/7 ΠΠΠΠ— 1 1/7 — 8 6/7 Π— 1 14/3 7/3 И/3 2/3 1/6 — 1/6 2/3 1/6 О О О О 1 ΠΠ— 1/6 7/6 -11/3 — 7/6 Уг Уг Уз Уз -161/3 О О О О О 1/3 Π— 28/3 О О О 1 О О 1 О О 1 О 1 — 7 Уг У2 Уз У4 1 6 4 У4+ У5 . (4.!4( — 55 О О 1 6 4 -у4+ -У5 — Ут+ Ув =— 7 7 7 (4.1 5( Рис.
4.5 162 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ А к в этом случае 74 = 4/7, 744 = 1/7, Угз — — 6/7, то новое ограни ч ение и меет вид При переходе к стандартной форме записи этого ограничении вводим новое переменное модели ут и искусственное перемен- ное ув. Для продолжения решения задачи линейного программирования с ослабленными ограничениями, в которой учтено новое ограничение (4.15), воспользуемся уже известным приемом с учетом того, что ув — искусственное переменное (табл. 4.5). Полученное оптимальное решение определяет оптимальное решение Хо = (4 3) исходной полностью целочисленной задачи.
Обратимся к геометрической интерпретации решения рас сматриваемой полностью целочисленной задачи методом Гомори (рис. 4.5). 4.2, Метод отсехаюшмх плоскостей (метод Гомори) 163 Таблица 4.5 01 -*,+3*2=6 02 х~+(1/7)хгР 6 03 х,=О 04 хг=о 0 06 хг+ж =7 164 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Решение задачи линейного программирования с ослабленными ограничениями, соответствующей исходной полностью целочисленной задаче, за две итерации симплекс-метода (см.
табл. 4.3) из крайней точки 0(0;О) 44ножесгаеа С допустимых решений, минуя точку А(0;2), приводит в крайнюю тиочку В(9/2;7/2). Но соответствующее оптимальное решение не удовлетворяет требованию целочисленности, следствием чего является новое ограничение (4.12). Воспользовавшись представлением исходной полностью целочисленной задачи в стандартной форме, выразим новые пеРеменные моДели Уз, У4, вхоДЯЩие в (4.12), чеРез Уы Уг. Уз = 6+ у4 Зуг, У4 = 35 — 7У4 — Уг (4.16) Подставив (4.16) в (4.12), приходим к первому отсечению Гомори, выраженному с использованием переменных уы уг.
.Уг < 3. Таким образом (см. рис. 4.5), реализация ограничения (4.12) приводит к отсечению от множества С подмножества, которое не содержит допустимых решений, удовлетворяющих требованию целочисленности, и появлению двух новых крайних точек: Е(3;3) и С(32/7;3). С учетом нового ограничения (4.12) на четвертой итерации симплекс-метода (см. табл. 4.4) получаем новое оптимальное решение, которое (см. рис. 4.5) соответствует новой крайней точке С Е С и не удовлетворяет требованию целочисленности, следствием чего является новое ограничение (4.14).
В равенство (4.13) входит искусственное переменное задачи Уа, Равное нУлю: Уа = О. ПоэтомУ Ус — — (?Уз+ У4 — 11)/22 и с учетом (4.16) из (4.14) получаем второе отсечение Гомори, выраженное с использованием переменных модели уы уг.' уг+ уг < 7. Таким образом (см. рис. 4.5), реализация ограничения (4.14) приводит к отсечению от множества С еще одного подмножества, которое не содержит допустимых решений, удовлетворяющих требованию целочисленности, и появлению двух новых крайних точек: 77(4;3) и Р'(14/3;7/3), первая из 4.г.
Метод отсекаюпаех плоскостей (метод Гомера) 165 которых соответствует оптимальному решению исходной полностью целочисленной задачи (см. табл. 4.5). При рассмотрении решения полностью целочисленной задачи в примере 4.3 следует обратить внимание на то, что вид отсечения Гомори определяется выбором базисного переменного модели, которое принимает нецелочисленное значение в оптимальном решении соответствующей задачи линейного программирования с ослабленными ограничениями. Одна и та же оптимальная симплекс-таблица может порождать несколько различных отсечений Гомори (см, табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
