Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 55
Текст из файла (страница 55)
2) 2' 14 — 2 — 2 — 7 ОТСечеНИО а=à — А 1 — Г А 1хз — ~ А 1хз — Г ~ 1хзг гз= — 4+хз+ ха+ 2хз>0 Полученное отсечение записывается внизу табл. 14.2. Шаги итераций приводят к табл. 14.3, 14.4, 14.5 и 14.6. Оптимальное решение получается в табл. 14.6: хо = — 52, х, = 1, хз — — О, хз = 2.
ГЛАВА 1б СМЕШАННЫЙ АЛГОРИТМ ! ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ 15Л. Введение (Гомори [8Ц) В этой главе будут изучены такие задачи целочисленного программирования, в которых требование целочисленности распространяется не на все переменные, а только на некоторое подмножество из них. Будут обсуждены два типа методов решения таких задач; первый излагается по работе Гомори [811, второй— по работе Бепдерса И8). Первый алгоритм в основном совпадает с алгоритмом, изложенным в гл.
13. Ш'а г 1. Начать с оптимальной таблицы непрерывной задачи линейного программирования. Ш а г 2. Выбрать производящую строку, Ш а г 3. Составить по производящей строке отсечение и приписать его внизу таблицы. Полученная строка используется в качестве производящей. Ш а г 4. Провести итерацию двойственного симплекс-метода и вернуться к шагу 2. Единственное отличие предлагаемого алгоритма от описанного в гл. 13 состоит в получении отсечения из производящей строки.
Пусть требуется найти максимум хо = аоо — ао!х! — со!хо —... — ноях» при условиях х„„= а„+ь о — а„ы,х, — ... — а„о!, » х„)~ О, (2) х, о! =а»оп»о — а„„„,,х,—... — а„+и, »х») О, х!>~О (1=1, ..., и). Некоторые переменные х; должны быть целочисленными. Будем решать данную задачу как задачу линейного программирования, используя двойственный симплекс-метод. Если в таблице ао,' ) О (у = 1,..., и), а!о )~ О (! =- 1,..., и + ло) и все переменные, 15л.
Введении на которые налоя<ено требование целочнсленности, имеют целые значения, то, очевидно, получено оптимальное решениепоставленной задачи. Поэтому предположим, что на переменную х, нала>неко требование целочисленности, и аш Ъ 0 — нецелое. Перепишем соответствующее уравнение, опуская индекс строки: х = а, + ~ ау ( — ху). (3) Поскольку х должно быть целым, х = 0 (шоб 1).
По предполо- жению а, — нецелое, аэ = 7, (шод 1). Отсюда любое целочислен- ное оптимальное решение задачи (2) должно удовлетворять усло- вию Я ауху = ур (шок 1). (4) Пусть коэффициенты левой части сравнения (4) разбиты на два множества у+ = (у ~ ау ~ )О) и у = (у ~ ау» 0). Тогда ~ ауху+ ~ ауху = ~э(шоу(1), (5) уе уь усу где 0»у,»1, Левая часть сравнения (5) является либо положительной, либо отрицательной.
Если она положительна, то принимает значения ~ю 1 + ую и т. д. Тогда ,"~~ ауху~ ~ аух;+ ~ ауху) уш уех+ уех+ уьу- (6) Если левая часть сравнения (5) отрицательна, то ее значениями должны быть — 1 + ~ш — 2 + Уэ и т. д. Имеем ~~~~~ ауху» ~~ ауху+ ~ ауху» — 1+ум учу уеу" уеу Умножив обе части неравенства (7) на, получим уо у+уО ,У', —,ауху>й. уэ уеу- (7) (8) ,'~~ ауху-~- ~~» — ауху~1о учу+ уеу" Любое целочисленное решение должно удовлетворятн неравенству (9).
Текущее решение ему не удовлетворяет, поскольку, Таким образом, имеет место либо неравенство (6), либо неравенство (8). Поскольку левые части неравенств (6) и (8) неотрицательны и одна из ууих болыне или равна у'ш то ГЛ. 15, СМЕШАННЫЙ АЛГОРИТМ 312 подставив х1 = О, получи в левой части неравенства (9) нуль. Следует заметить, что при получении неравенства (9) использовалось лишь условие целочислелпости х в левой части (3) и неотри.
цательности х1 в правой части уравнения (3). Таким образом, получение ограничения (9) не зависит от того, было ли наложено ограничение целочисленности на переменную х;. Вводя неотрицательную слабую переменну1о г, можно переписать неравенство (9) в виде уравнения о = — 1о + ~~ агх1+ ~„"— о а1ххэ 1Е 1о 1ео- (19) Заметим, что функция у(у)= — возрастает с ростом у при ( у 1 — у у(1.) Очевидно, что Ь (1 — 1о)(1о(1 — ~о), если 6 -'1о или, что равносильно, 1„( — о(1 — ~о), если 11(~о, 1 — Го 1А) — '(1 — 1ь), если 1А) уо.
которое записывается внизу таблицы, после чего таблица перестает быть прямо допустимой. Затем проводится итерация двойствоиного симплекс-метода с использованием строки (10) в качестве ведущей. Если на некоторые х; в левой части неравенства (9) наложено требование целочисленности, то этим фактом можно воспользоваться для того, чтобы усилить неравенство (9), т.
е. мы хотим сделать коэффициенты а (1 ч Х+) и ~ (1 с Х ) 1о — 1 насколько возможно малыми. 11оскольку неравенство (9) получено из соотношения (4), рассмотрим в этом соотношении член аьхо, где па хо наложено требование целочислонности. Очевидно, увеличение или умепыпепие ад на целое число не нарушит справедливости соотношения (4)., Минимальным допустимым числом, полученным из ау » )О (а с Х+), является 11. А для ао ~ О величиной, дающей паименыпее значепие 1 ' 1 аю будет ~о — 1.
1о — 1 Поэтому было бы желательно увеличивать или уменьшать в соотношении (5) ао на целое число таким образом, чтобы получать минимальное значение коэффициентов в неравенстве (9), т. е. найти минимум из 15Д, Ввиде ние Таким образом, из уравнения (10) получим уравнение о= — Д~ — ~Д( — х;), (11) где аю([аю], если а;,) О, а[о>[а5о]-[ 1, если а;,(С, (13) где г-й столбец ведущий. Выписанные соотношепия (13) означают, что элемент нулевого столбца и производящей строки либо уменьшается до ближайшего целого [аго], либо увеличивается до следующего целого [а55] + 1. Для доказательства соотношений (13) рассмотрим подробно одну итерацию.
Если 1-я строка выбрана в качестве производящей и о-й столбец является ведущим, то а1о = аю — +1~ а ' 6о 1. Из формулы (12) получаем К=а;., если а;,) 0 жено требование целочислепности. В этом случае принимает вид (14) и на х, не налосоотношенио (14) а[о = аоо" — — ам = [аоо]. йо ом Если ам(0 и па х, не налоноено требование равенство (14) принимает вид а,'о = а;о — ' ' = [аю]+ 1. оо 1 " 1ю — 1 цолочисленпости, [ ' а,ч если а,)0 и х, нецелое; 1 — аоо если аз(0 и х, нецелое; 1о 1о — 1 6 если 11([о и х; целое; — (1 — Я, если ~~)1о и х; целое. 1о Уравнение (11) записывается внизу таблицы и далее решается задача нахождения максимума при дополнительном условии.
Для доказательства конечности предложенного алгоритма предположим, что исходная таблица двойствепно допустима, и используется лексикографический двойственный симплекс- метод. Последнее гарантирует лексикографическое уменьшение нулевого столбца после каждой итерации. Пусть аго обозначает элемент нулевого столбца и производящей строки до итерации, а а; 'обозначает такой же злемент после итерации. Тогда ГЛ. 1Ю.
СМЕ1ПАННЫЙ АЛГОРИТМ Если требуется, чтобы х, было целым и 1ц(~ю, то из (14) получим азЮ=азю — — а1,=(а1О), ЕСЛИ азз=11„ 11о 1з аззю=а;о — —,аз,((аоо). если аз,- 1'1з 11о Если требуется, чтобы х, было целым и 11, ~ 11о, то из (14) следует азо = аю — ' 1о ° " = азо (1 11о) —" . (15) 1ю111 — 1зо) 1 — 11з 1 — 11з Если О(а1,(1, т. е. азз=11з, и поскольку — 'о ( 1 — 1ю 1 — 11з ' то из (15) получаем аю (аю — Ло =, (аю). Если — 1(ао,(О, т.
е. а;,=1ю — 1, то из (15) следует а(о = аю — (1 — 1ю) —" = (азо) + 1. йз Если 1(аю, то равенство (15) принимает вид 110 озз а11о = аоо — 11о 1 —" ( азо — ~1о = (а1о). Если аю( — 1, из (15) получим аю ) аю — (1 — Ую) ( — 1' ) = а о+ (1 — 11о) = (азо) + 1. Только что было доказано, что элемент азо производящей строки после одной итерации либо увеличивается до следующего целого, либо уменьшается до ближайшего, не превосходящего его целого значения. Чтобы доказать конечность, кроме обычного предположения о существовании нижней границы для оптимального значения з, необходимо сделать дополпительное предположение о том, что оптимальное значение з должно быть целочисленным.
В исходной таблице расположим в верхней части все т' ограничений, левые части которых подчинены требованию целочислепностн, а под ними — остальные ограничения. В силу сделанного выше предколожения а;, (1 =- О, 1,..., т') доллоны быть целыми, поэтому первые т' + 1 строк могут выступать в роли производящих.' Поскольку а', лексикографически уменьшается на калздой итерации и элемент а;, производящей строки уменьшается илн увеличивается до следующего целого, ао, не может умепьшаться бесконечно и при этом оставаться больше предполагаемой нижней границы. Поэтому ао, дол1кно оставаться постоянным для всех 1) 1о. Таким образом, через конечное число Мкз.
МЕТОД РАЗБИЕНИЯ 315 шагов в качестве производящей строки будет выбираться первая, если аю нецелое. Тогда аш не монсет увеличиться до ближайшего целого длн ~ ) ~„поскольку это противоречило бы лекснкографнческому уменьшению столбца а,' (аее остается неизменным для 1 ) ~с). СлеДовательно, после опРеДеленного числа шагов а2е также должно стать фиксированным целым числом. Подобным же образом можно рассмотреть вторую, третью и, наконец, (нз' + 1) строку, пока все а;о (1 = О, 1,..., т') не станут целыми. 15.2. Метод разбиения в смешанном целочисленном программировании (Бендере 118)) Рассьсотрнм смешанную задачу целочисленного программирования: минимизировать З = С,Х + СЗУ при условиях А2х + Агу ) Ь х, у)0, у=О(шой1), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
