Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 58
Текст из файла (страница 58)
Пусть требуется аппроксимировать произвольную нелинеиную целевую функцию кусочно-линейной функцией, как показано Хз Яэ 5 Р в с. 15.4. на рис. 15.4. Значение функции на отрезке, где она линейна, задается выпуклой линейной комбинацией аначений функции на концах этого отрезка. Таким образом, пусть х = ЛОхэ-т- Л5х5+ ° ° . + Л„хй, ?(х)=Ло?(хе)+Л5?(х5)+... +Л„?(х„), 1= Лс+Л,+... —,'.Л„, Л5 > О (1 = О, „п), ГЛ. 15.
СМЕШАННЫИ АЛГОРИТМ 328 Ло~ (бо Л1(60 61 Лз< 6,+6„ Л„,~ л„== 62-2+ 62-н бл-1 6,—, ...+6„,=1, 0(61(1(целые) (1=0, 1, ..., и — 1). Заметим, что если 6; .= 1, то Л1 и Л111 могут принимать ненулевые значения, а в сумме дают единицу; остальные Л равны нулю. Четвертый класс задач можно назвать смешанным классом. Не существует стандартного способа превращения задач этого класса в целочисленные программы. При одной формулировке может получиться намного меньше переменных, чем при другой. Для примера приведем некоторые из таких задач. Это задача об ортогопальных латинских квадратах, задача коммивояжера, задача о минимальном числе цветов для раскраски карты, некоторые задачи кодирования и другие.
Обсудим лишь задачу о коммивояжере и задачу о раскраске, так как они являются наиболее известпымн. Свести пекоторую задачу к задаче целочисленного программирования еще не значит ее решить, поскольку в последней можот оказаться слишком много переменных, слишком много ограничений и т. д. Тем не менее стоит отметить, что в терминах целочисленного программирования формулируется множество различных задач. Одной из наиболее известных нерешенных проблем в математике является задача о раскраске карты, в которой требуется доказать или опровергнуть тот факт, что любую карту на плоскости можно раскрасить, используя четыре цвета или меньше.
Карта делит плоскость на много областей; ограничение состоит в том, что две области, имеющие общу1о границу, доли1ны быть раскрашены в разные цвета. Если бы существовал алгоритм, позволяющий найти минимальное количество цветов для любой карты, то он мог бы служить для построения примеров и контр- примеров. Допустим, что карта может быть раскрашена четырьмя цветами и пусть О, 1, 2 и 3 соответствуют этим цветам. Каи дая область 1 представлена целочисленной переменной х1.
Для двух соседних областей 1 и 1 мы хотим, чтобы х1 Ф л . Это эквивалентно объединению ограничений: либо х1 — х; ' -1, либо х; — х1 1. м.з. приложения 32в Используя обсуя денную ранее технику формализации, монгно записать з, — хз — 1 ) — 46ы, зу — з, — 1 ) — 4 (1 — 6;!). Кроме того, мы хотим, чтобы О ( л; (3 (целые), О ( бы (1 (целые). Поскольку все ограничения являются неравенствами, мо2кно ввести слабые переменные и искусственные переменные, а целевой функцией сделать сумму искусственных переменных. Если целевая функция достигнет нулевого значения, то карту можно раскрасить четырьмя цветами.
Йадача коммивоя~ксра может быть поставлена следующим образом. Даны и городов и расстояния Ны от города 1 до города у. Каков должен быть маршрут коммивояжера, если оп начинает путешествовать из города, где он живет, посещает каждый город ровно один раз и возвращается в свой город, причем общая длина его пути должна быть минимальной. Мы не требуем, чтобы И;; =- = Ня, но требуем, чтобы Нм ) О и ды + Ыгь ) г(ы для всех 1, (, л. Допустим, что коммивояжер начинает из города 1.
Тогда любая перестановка из 2, 3,..., и дает возможный маршрут. Таким образом, существует (и — 1)! маршрутов, которые твебт ется перебрать. Можно пе требовать, чтобы Нм +л д~ь ~ )Н ю и сформулировать задачу так: коммивояжеру требуется побывать в каждом городе по меньшей мере один раз, прежде чеи вернуться в свой город. Однако если сначала найти кратчайший путь между кан'дой парой городов и заменить исходные расстояния между ними па полученныо, то задача станет в точности такой, какой она дана в первой формулировке. Таким образом, будем считать, что всегда Ау л ~(гь Ф- ггы В пашем случае допустим, что имеется и + 1 городов, и копмивояжер начинает свой путь в городе О, посещает каждый город в точности один раз и заканчивает его в городе п, не возвращаясь домой.
Требуется минимизировать общую длину маршрута. В такой постановке маршрут называется открытым в отличие от упомянутого выше, где маршрут был замкнутым. Для того чтобы Р Р * " у Р Ру Р к л~~~юипчв~- вить начанвпйй го о в виде двух городов, ндип-нз"пах будет городом 'О, другой и. озтому рассуждетяя будут'" йроведены примепптельяо к бткрмтому маршруту, начинающемуся в городе О и кончающемуся в городе п.
Положим лп =- 1, если коммивояжер едет из города г в город у, и х» = О, если кет. Так как Гл. 11. смкшАиный АлГОРитм каждый город можно посетить только однавтды, получим и-1 ~ хм=1 (1=1, ..., и; 1~у). 1=0 Поскольку из каждого города (кроме города и) коммивояжер дол1кен уехать, имеем ~~~ х;1=1 (1=0, 1, ..., и — 1; 1Ф1). 1=1 Эти два множества ограничений показывают, что в графе, иллюстрирующем маршрут коммивояжера, города 0 и и имеют степень 1, а все остальные города — степень 2. Однако указанные выше два множества ограничений могут выполняться и в том случае, когда коммивояжер посетит лишь часть городов, после чего окончит маршрут, а оставшиеся города соединит петлей или несколькими петлями ').
Чтобы сделать подобяые подмаршруты невозможными, введем третье множество ограничений. Во-первых, сопоставим с каждым городом 1 действительное число у; (О ~ у; ( п). Затем потребуем выполнения следующих условий: у; — у!+их)(п — 1. (0(1(и — 1; 1(1 -'и; 1Фу). Чтобы увидеть, что это множество ограничений исключает воэмон ность замкнутого подмаршрута, рассмотрим такой замкнутый подмаршрут, состоящий из я городов.
Для каждой дуги этого подмаршрута имеется введенное неравенство. Если слонсить все неравенства, соответствующие Й дугам подвтаршрута, все у! взаимно увичтожатся и в итоге получится заведомо неверное неравенство пп ~( (п — 1) ее, что невозможно. Таким образом, решение, содержащее замкнутый подмаршрут, не удовлетворяет третьему множеству ограничений. С другой стороиы, чтобы показать, что любой открытый маршрут может удовлетворять третьему множеству ограничений, полол!им у; = 1, если город 1 есть г-й город по порядку в данном маршруте. Тогда уе — ут ( и — 1 для всех 1, у, и, следовательно, если хп = О, все ограничения третьего множества выполняются.
Для хы = 1 получим у! = 1 и уу —— 1 + 1. Поэтому ! — (г + 1) + и = и — 1. Целевой функцией задачи коммивояжера является з= ~ ~ 11!ух!1. е=о 1=1 ') В етом случае граф, изображающий маршрут коммивояжера, будет несвязным.— Прим. род. глава 1е ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ С ПАРАБОЛИЧЕ- СКИМИ ОГРАНИЧЕНИЯМИ 16Л. Введение (Витцгалл (215~) В этой главе будут изучены задачи целочисленного программирования с параболнчоскими ограпиченнями. Сначала дадим Опгкдклкник.
Параболическим ограничением ранга й нагыеается ограничение, которое можно представить'е форме аг, — Лг (х) — Ь| (Ь, (х)) —... — Ьь (Л„(х))' ~ )О, (1) Л, (х) = а„х, +... + а,„х„(г = О, 1, ..., й) (2) где есть линейно негаеисимые однородные линейные функции от и пере- менных и Ь; )~ О(г = 1,..., й). Заметим, что (1) можно привести линейным преобразованием к виду Уо И~ ° ° ° Уьг '- (3) к=а+ ~ а~х~+ ~ ацх~хр $=1 г, 2=г (4) Можно считать х новой переменной и преобразовать целевую функцию в параболическое ограничение: минимизировать г при условии г — а — ~ а~х; — ~~~~ апх;хг~О. 1=1 ц о=1 (5) Параболическое ограничение ранга 0 является линейным ограничением, а параболическое ограничение ранга и — 1 определяет выпуклый и-мерный параболоид.
Многие задачи целочисленного программирования могут быть представлены в такой форме. В частности, иногда можно представить в такой форме задачу, в которой целевая функция является квадратичной положительной полуопределенной функцией, а ограничения линейны. Например, пусть целевая функция в задаче на минимум имеет вид ГЛ. 12. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Для того чтобы ограничение прииадлеяоало параболическому типу, требуется, чтобы квадратичная часть (1) была полоокительно определенной или положительно полуопределенной, т.
е. Ь (71 (х))' +... + ЬА (ХА (х))' ) О, и чтобы й + 1 однородных линейных форм (2) были линейно независимыми. Для проверки того, что данное квадратичное ограничение ао+ ~Я а;х;+ ~~~„" ацх;х, О (6) является параболическим, поступаем следующим образом. Если все а;; — неположительны, то (6) — отрицательно определенная, отрицательно полуопределенная или неопределенная функция. Если хотя бы одно из ап, скажем а11, положительно, то дополняя до полного квадрата подформу из (6) а11х! . (а12 а21) х1х2+ . "(а1 ! ао1) х!хп получим следующее выраокенио: 1 ( О12 а11, О1„—,ОО1 ) о11'1 ' 2 ''' 2 — а11Х1, — Х2 ' -( Хо Если (6) — ограничение параболического, типа, то оставшаяся квадратичная часть из (6) должна быть положительно полуопределенной.
Таким образом, мы можем продоллоить процесс выделения полных квадратов. В случае параболического ограничения, квадратичная часть из (6) в конце концов станет суммой и — 1 или меньше квадратов линейных форм. Рассмотрим задачу целочисленного программирования с липейной целевой функцией и параболическими ограничениями (некоторые из них могут быть линейными): максимиаировать с, — 2, с1х; 1=1 (7) при условиях аоо — 1 о(х) — Ь, (2,1(х))2 —... — Ьо (7,2(х))2 ЕО, х1- О (у=1, ..., п).
(8) Для простоты предположим, что имеется только одно ограничение в (8) и все х1 в (7) и (8) являются пебазисными. Если с; » О в (7), то, полагая все небазисные переменные равными нулю, получим двойственно допустимое решение. В этом случае любое неотрицательное решение х' давало бы целевой функции со — ~ с;хо значе- 16л. Вввдиник пие меньшее, чем со. Является ли данное двойственно допустимое решенно прямо допустимым, зависит от знака аом Для выполнения условия (8) необходимо (но не достаточно), чтобы аоо — То (х) > О, (9) так как квадратичная часть в (8) всегда неотрицательпа, т. о. Ь1(ра(х))о ',- ...лсЬо(йо(х))о)0 (Ьо оО; ~=-1, ..., к).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
