Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 60
Текст из файла (страница 60)
Чтобы восстановить таблицу в стандартной форме, вычислим а,',= ам — ~~~~~ Ь,(рэа,~)'=-3 — 1( — 1 ° 1)'= 2, а,', = ам — 2 ~ Ь,рэа„эм = — 6 — 2 1 ( — 1) (1) (1) = — 4, а„', = аээ — 2 ~ Ь,роома„= 2 — 2 1 ( — 1) 1 О = 2, Подобным же образом для второго параболического ограничения а„" —.- — 11 — 1 ( — 1 ° 1)~.= — 12, а,',.=- — 5 — 2 1.( — 1) 1э= — 3, а,',= — 5 — 2 1( — 1) 1( — 1) = — 7. После произведенных вычйслений получаем табл.
16.6. Таблицы 16.7, 16.8 и 16.9 представляют последовательные стандартные таблицы, причем табл. -16.9 является оптимальной. 340 ГЛ. 1З. ЦЕЛОЧИСЛБННОН ПРОГРАММНРОВАНИН Рассмотрим задачу целочисленного программирования: минимизировать з =х, '+Зх, *+ 2х,' при условиях х, + 2хз — хз )~ 5.
— Зхз + хз + хз ) -2 хм х'„хз ) О (целые). Для того чтобы преобразовать зту задачу в целочисленную задачу с параболическим ограничением, введем новую переменную хз = = — аи максимизировать при условиях — 5 — ( — хз — 2хз + хз) ~ >О, 2 — (Зх, — х,— хз))О, хз — х', — Зх', — 2х,' ) О. Табаица 16.П 1 — зз — хз — хз — хз зз зз хз хз хз хз Таблица 16.16 -хз -хз -хз -хз зз хз хз хз хз нсо. доклзлткльство конкчностн Для того чтобы сделать начальную таблицу двойственно допустимой, введем избыточное ограничение — хо — х, — хо + х, + + М ~~ О, где М выбирается так, чтобы ограничение стало избыточным. Здесь мы берем М, равное 2, и получаем начальную табл.
16.10. После преобразования получаются табл. 16.11 и 16.12. Чтобы восстановить таблицу в стандартном виде, вычислим п~ =- аоо — ~~~~ Ь. (Ро, а.«)о = =0 — 1( — 3 1)' — 3 ( — 3.0)' — 2 ( — 3 0)'= — 9, а,', =-аоо — 2 1 Ьороа,',=0 — 2 1 ( — 3) 1'— а,', = аоо — 2 ~~~~~ Ь,роа„аоз = 0 — 2 1. ( — 3) (1) ( — 1) .= 6. Последовательные таблицы в стандартном виде приведены в табл. 16.13 — 16.18.
Каждой таблице соответствует множество небазисных переменных. Линейное преобразование небазисных переменных (2) из $16.3 обычно не сохраняет стандартного вида~ параболического ограничения. Поэтому требуется производить восстановление параболического ограничения в стандартном виде. В целях экономии места показаны только таблицы, соответствующие стандартному виду после каждой итерации.
16.6. Доказательство конечности Существует два случая окончания работы алгоритма: 1) все элементы производящей строки, кроме ао„ неотрицательны; 2) таблица стала прямо допустимой. В первом случае мы имеем ограничение вида аоо — ао«хо — аюхо —... — ао х. —,«~ Ь. (Ь. (х))о)0, где аоо(0, ао;)О (г=.1, ..., и). Поскольку хт ) О, левая часть ограничения отрицательна, н задача несовместна. Чтобы показать, что алгоритм приходит к случаю 2, воспользуемся тем же аргументом, что и в полностью целочисленном алгоритме. Нулевой столбец будет лексикографически уменьшаться па каждом «паге, а мы предположили, что существует нижняя граннца для целочисленного .допустимого решения.
Как и в полностью целочисленном алгоритме, коэффициенты в ограничениях не обязаны быть целочисленными. Целочисленность требуется лишь от коэффициентов целевой функции и справочных строк. ГЛАВА)У ПРЯМОЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВА- НИЯ т) (Р. Д. В)НГ) 17Л. Введение и алгоритм Термин «прямой», примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному репгению посредством получения последовательно «улучшаемых» решений. Каждое из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности '). Одним из вероятных достоинств прямого алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное.
Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дагощей прямо допустимые решения. Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых полностью целочисленных решений.
Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит з том, что в качестве ведущей строки используется отсечение Гомори с недущим элементом, равным ( — 1). Это отсечение получается из производящей строки, которая определяется как одна йз воаможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы. Оказывается, можно аналогично модифицировать симплекс- метод таким образом, чтобы получить алгоритм, который сохраняет прямую допустимость и целочисленность таблиц.
Для описа- ') Непосредственным источником для этой главм послужили работы Гловера [76) и Юнга 1225). Алгоритмы, приведенные в этой главе, более похожи на те, которые предлагал Гловер, а доказательство конечности ближе к работе Юнга. «) Алгоритмы, описанные в гл. 13 и 14, следует классифицировать как двойствепнме, поскольку получаемые промежуточные решения не являются допустнмыии решениями исходной задачи. ыл. Введение и ллгогктм 345 ния вычислительной процедуры рассмотрим следующую задачу целочисленного программирования: максимизировать хо = аоо — 2. аоФ! )=ю+ 1 при условиях х;-'; ~~' амх,=ам ()=1, ..., т), (1> ' ' у- +э хд)О (целые) (й=1, ..., и), где ао).
ам и а;о — целые числа и а;о.-»О. Предположиэт, что столбец а, выбран в качестве ведущего. и строка и — ведущая строка в итерации симплекс-метода, т. е. — ( — — для всех строк ), в которых а., ) О. Прежде чем про- аао ам а, аы вести процедуру исключения Гаусса в симплекс-методе, добавим к таблице отсечение Гомори, полученное из строки и'): ло = ~ 'о ) + ~~~~ [ — ( ( — х,), (2), ) е.о где У вЂ” множество индексов небазисных переменных в (1), ло— новая (базисная) слабая переменная и Л вЂ” неопределенная (вре- менно) полок.ительная константа.
Заметим, что если положить Л = амо то отсечение (2) будет обладать двумя важными свойствами. Во-первых, [аоО[аио) [ аоо [ ~ аоо [а„!аоо) [. а,о .) а,о ' Это означает, что прямая допустимость таблицы сохранится„ если использовать отсечение (2) в качестве ведущей строки. Во-вторых, ~ — "" 1 = 1, т. е. ведущий элемент равен 1 (если отсе! аов.3 чение используется как ведущая строка). Легко удостовериться (путем исследования формул изменения базисных переменных в симплекс-методе), что преобразование симплексной таблицы с единичным ведущим элементом сохраняет целочкслепность элементов симплексной таблицы.
Эти идеи послужили основанием интуитивного прямого алго- ритма в целочисленном программировании (см. Вен-Израел и Чар- нес И7)). Чтобы показать структуру отсекающей плоскости в прямых алгоритмах, рассмотрим этот алгоритм и решим пример„ прежде чем внести изменения, необходимые для доказательства конечности. э) Ото отсечение получево по способу, положенному в полностью целочисленном алгоритме Гоморк. (См. 1 14Л.) гл.
1ь пРямОЙ Ал1'ОРнтм Ш а г О. Начать со столбцовой таблицы, в которой аш ) О (1 ) )1) и все элементы аш, агт и аса — целые. Ш а г 1. Проверить выполнение условий аш > О (у ) 1); если они выполнены, то конец, текущее базисное решение оптимально; если нет — перейти к 1пагу 2. Ш а г 2. Выбрать ведущий столбец г с аю ( О. Выбрать строну о по правилу проверки отношения а1„!а1, среди строк с'ам ) О. Эта строка служит производящей для получения отсечения Гомори. Ш а г 3. Получить отсечение Гомори нз производящей строки и дописать ее внизу таблицы, т. е. добавить к ограничениям задачи уравнепие (2), где й =- а„.
Ш а г 4. Провести преобрааованме таблицы, используя отсечение (2) как ведущую строку. Слабая переменная гА в (2) станет небазисной. Вернуться к шагу 1. Проиллюстрируем интуитивный алгоритм на примере. Для этого решим задачу: максимизировать ха = Зх1 + х, при условиях 2х, + Зх,(6, 2х, — Зх,(3, х„х, ) >О (целые). Графически условия задачи и четыре отсечения, последовательно получающиеся в ходе решения, показаны на рис. 17.1. После введения слабых переменных (ха, х1) задача записана в табл. 17.1.
Выберем столбец под переменной х, в качестве ведущего. Строка с обозначением х1 является ведущей строкой в симплекс-алгоритме и поэтому выбирается как производящая. Запишем отсечение, полученное из этой строки, в последней строке таблицы. Новая переменная г1 является слабой переменной в отсечении. Отсечение получим, разделив каждый коэффициент проиаводящей строки на 2 = а„., = Х и взяв целую часть от.частного. Следующее преобразование таблицы использует столбец под х, и строку г, в качестве ведущих.
В результате получается табл. 17.2. На рис. 17.1 это отсечение обозначено череа с,. Выберем для введения в базис переменную х,. Строка ха является ведущей строкой симплекс-алгоритма и, следовательно, производящей строкой. Отсечение ааписано в нижней строке таблицы. Результат выполнения преобразования показан в табл. 17.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
