Въпроси за самоконтрол
1. Формулирайте математически модел на проблемите с раницата и нейния двойник.
2. Формулирайте разклонен алгоритъм за решаване на проблема с раницата.
3. Към кой клас оптимизационни задачи принадлежи задачата за раницата?
ЛЕКЦИЯ 12 Проблемът с пътуващия търговец
12 . 1 Постановка на задачата на търговския пътник и решение по метода на разклоненията и границите
Формулиране на проблема. Има n града. Разстоянията между всяка двойка градове са известни и са a ij (i; j = 1; n, i 6= j). Ако няма директен маршрут между градовете i и j, тогава a ij = 1. Удобно е разстоянията между градовете да се записват под формата на матрица A = (a ij ) n n (таблица 12.1), където a ij = 1.
n a n1 a n2 . . . 1
Пътуващият търговец, напускайки града, трябва да посети всички
градове, като сте посетили всеки от тях веднъж и само веднъж и се връщате
към първоначалния град. Необходимо е да се определи такава последователност от обиколки на градовете, при която дължината на маршрута ще бъде най-малка.
Ако на градовете са присвоени върхове на графа, а пътищата, които ги свързват, са дъги, тогава от гледна точка на теорията на графите проблемът е да се определи Хамилтонов контур с минимална дължина. Хамилтонова верига (на името на английския математик Хамилтън) е път, минаващ през всички върхове на граф, чийто начален връх съвпада с крайния. Тук дължината на контура се разбира не като броя на дъгите, включени в контура, а като сбор от техните дължини.
За да напишем постановката на проблема от гледна точка на целочислена линейна оптимизация, ние дефинираме булеви променливи, както следва:
ако пътуващ търговец се премести от град i в град j (i; j = 1; n);
в противен случай.
Тогава задачата е да се намерят стойностите на променливите x ij ,минимизиране на функцията
(вход за град j);
x ij = 1; i = 1; н; (тръгване от град i);
u i u j + nx ij n 1; (i; j =
Променливи u i , i =
, може да приема произволни стойности,
въпреки това, без каквато и да е вреда, може да им бъде наложено условието за неотказ.
отричане и цялостност.
Лесно е да се види, че целочисленият проблем за линейна оптимизация
е еквивалентен на проблема с пътуващия търговец. Наистина условието
стойностите a ii = 1 изключват стойностите x ii = 1 в оптималното решение, т.к
безсмислен. Ограниченията ( 12.2 ) изискват маршрутът да включва
беше разрешен само един вход във всеки град и ограничения (12.3) - до
маршрутът включваше само по един изход от всеки град. Целева функция
ция (12.1) отразява дължината на Хамилтоновия контур. Ограничения (12.4)
изискват маршрутът да образува контур и да преминава през всички
Решението на задачата, описано само в условията, не е задължително
е наистина контур, минаващ през всички градове. В частност,
в резултат на решаването на проблема, две и
повече несвързани частични контури. За елиминиране
възможността за образуване на нехамилтонови контури и служи като ограничение
Решаване на проблема на пътуващия търговец по метода на клона и обвързаността.
Съществуват различни версии на разклонения и обвързания метод за решаване на проблема с пътуващия търговец. Помислете за стандартния метод на J. Little.
Първо, за множеството R от всички хамилтонови контури се определя някаква долна оценка (долна граница) ' (R) на тяхната дължина. Тогава множеството от всички контури на Хамилтон се разделя на две подмножества. Първото подмножество се състои от хамилтонови контури, които включват някаква дъга (i; j), означена сf(i; j)g, а вторият се състои от хамилтонови контури, които не включват тази дъга, –
(i; j) . За всяко от подмножествата f(i; j)g и
долна граница на дължината на Хамилтоновите контури '
) . Всяка нова долна граница не е по-малка от долната
границите на целия набор от контури на Хамилтон ' (R) . Сред двете под-
набори от маршрути f(i; j)g и (
подмножество с по-малък
долната граница на врата. Това подмножество отново се разделя на две и
за новообразуваните подмножества се намират долни граници. про-
процесът на разделяне на подмножества по подобен начин продължава до тези
до подмножество, съдържащо единичен
Хамилтонов контур. Връзката на подмножествата, получена в резултат
тези дялове, се изобразява като дърво (граф), върховете на което
задават се долни граници.
След като са получили контура на Хамилтон, те гледат през висящите клони на де-
rev и сравнете долните граници на подгрупите, съответстващи на
счупени клони, с дължината на получения Хамилтонов контур. Ако долните граници на подмножествата, съответстващи на прекъснати клони, се окажат по-малки от дължината на Хамилтоновия контур, тогава тези клонове се разделят съгласно същото правило. Процесът продължава, докато долните граници на новополучените подмножества са по-малки от дължината на Хамилтоновия контур. В резултат на това могат да се получат нови контури на Хамилтон. В този случай се сравняват дължините на всички хамилтонови контури и сред тях се избира контурът с най-малка дължина. Решението на задачата се счита за пълно, ако долните граници на висящите клони не са по-малки от дължината на Хамилтоновия контур. За оптимален се избира хамилтоновият контур с най-малка дължина.
Всички разгледаниЗа по-голяма яснота формулираме действията под формата на алгоритъм.
1. Представяме матрицата на разстоянията по редове и колони. Намираме долната граница на целия набор от маршрути:
2. Всяка нула в намалената матрица условно се заменя с 1 и
намерете сумата от редукционните константи (
запишете в съответните клетки до нулите.
3. Априори изключете от контура на Хамилтон тази дъга (i; j) за
при която сумата от редукционните константи е максимална (елиминиране на дъгата (i; j)
се постига чрез заместване на елемента в ij матрица на разстоянието с 1. В резултат на елиминиране на дъгата (i; j), подмножество на хамилтониана
нови контури (i; j) .
4. Представяме получената матрица на разстоянието и определяме долната
) подмножества от контури на Хамилтон
5. Априори включваме дъгата (i; j) в Хамилтоновия контур, което води
към изключение в матрицата, получена след изпълнението на стъпка 2,
колонни редове. Заменяме един от матричните елементи с 1 (в про-
в най-простия случай, симетричен), за да се предотврати образуването на отрицателни
6. Даваме намалената матрица и намираме долната граница ' (i; j)
подмножества от маршрути f(i; j)g.
7. Проверете размера на намалената матрица. Ако е съкратено
матрица с размерност 2 2, след което преминете към изпълнението на параграф 9; Ако
ако размерът на матрицата е по-голям от 2 2, преминете към стъпка 8.
8. Сравнете долните граници на подмножествата на контурите на Хамилтон
) и преминете към стъпка 2. В този случай, ако