Главная » Просмотр файлов » Т. Ху - Целочисленное программирование и потоки в сетях (1984)

Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 58

Файл №1162191 Т. Ху - Целочисленное программирование и потоки в сетях (1984) (Т. Ху - Целочисленное программирование и потоки в сетях (1984)) 58 страницаТ. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191) страница 582019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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, ..., к).

Характеристики

Тип файла
DJVU-файл
Размер
5,27 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее