Завдання про комівояжера

Зміст.

Запровадження.

Постановка завдання.

Алгоритм рішення.

Математична модель завдання.

Опис програмної реалізації алгоритму.

Опис програмного інтерфейсу.

Опис програми.

Література.

Нині швидко розвивається науково-технічна революція. З’явившись на в 40-ві роки нашого століття комп’ютери і комп’ютерні технології пройшли цей час шлях від лампових систем з прямим завданням кодів операцій до надшвидких персональних комп’ютерів на монокристальной технології, використовують під час роботи многопользовательские операційні системи з графічним інтерфейсом. Найбільш бурхливий розвиток комп’ютерних технологій сталося протягом останніх 10−15 років, коли розробили технологія виробництва СБИС, але в основі мікрочіпів. Також на початку 80-х почала розвиватися концепція персональної ЕОМ, що згодом конкретизувалася у існування двох найпоширеніших апаратних платформ: Macintosh (виробляється фірмою Apple, процесори фірми Motorola) і IBM PC (виробляється фірмою IBM, процесори фірми Intel).

Кожна з цих платформ має власну спрямованість й особливо. Комп’ютери Macintosh переважно орієнтовані роботу у глобальних мережах і обробку інформації, хіба що зовнішнього сприйняття, тобто графічної і звуковий. Їх головними особливостями є вбудована в ПЗУ (ROM) графічна операційна система і несумісність різних моделей цієї фірми, проте рахунок цього досягнуть дуже швидке зростання продуктивності процесорів і системи в целом.

Фірма IBM, на відміну Apple, дотримується концепції відкритої системи, виражену у цьому, що, по-перше, IBM немає ексклюзивного права виробництво та продаж IBM-сумісних комп’ютерів (їх виробляє багато фірм, як-от Hewlett Packard, AT&T, Compaq та інші), і навіть повної сумісності пізніх моделей з більш ранніми, що дозволяло IBM довгий час утримувати ринок збуту, як і раніше, що спочатку 90-х Macintosh-и помітно перевершували PC продуктивністю (зараз, з її появою Pentium і PowerPC, Macintosh-и втратили беззастережне лідерство по производительности).

Персональні комп’ютери нині переважно використовують у чотирьох областях:

* обробка текстів і їх комп’ютерна верстка;

* зберігання баз даних із можливістю швидкої їх обработки;

* управління виробничими процессами;

* аналіз складних процессов;

Також зараз інтенсивно розвиваються ще кілька областей застосування ПЕОМ, як-от комп’ютерні ігри (1994 року 43% ринку програмних продуктів становили ігрові програми), гео-информационные системи, навчальні системи та системи мультимедиа.

Програма даної курсової роботи входить у розділ «аналіз складних процесів ». Ця область почала розвиватися у середині 80-х, коли продуктивність ПЕОМ досягла достатнього рівня в обробці необхідного об'єму інформацією реальному масштабі часу, що дозволило розпочати застосування комп’ютерів в західних областях, що з контролем складних процесів та його аналізом. Однією з цих проблем стала оптимізація систем із багатьма невідомими, коли певний параметр довелося б зводити до якомусь значенням чи навіть максимизировать.

Найяскравішим і характерним прикладом застосування завдання «Про коммивояжере «стала оптимізація операцій на конвеєрі: в 1984 року, коли було проведено аналізу послідовності і тимчасових витрат за операції у конвеєрах заводів компанії «General Motors «і прийнято рекомендовані заходи, збільшити загальну продуктивність на 13% за незмінної числі робітників і тому самому устаткуванні. Розрахунки проводилися за комп’ютерами IBM 360gr, які на той час були серед самих продуктивних систем у світі. Прорахунок і оптимізація 200 основних та 87 допоміжних операцій тривав близько 230 годин. Вважається, що це перша комерційне застосування комп’ютерних технологій у галузі управління виробництвом в целом.

Зараз вирішення цього завдання необхідно задля багатьох областях пов’язаних із замкненими і навіть жорстко пов’язаними за часом системами, такі як: конвеєрне виробництво, многооперационные обробні комплекси, суднові і залізничні навантажувальні системи, перевезення вантажів по замкненому маршруту, розрахунок авіаційних линий.

Тому викладена проблема на сучасному розвитку суспільства" має не найостанніше за значимістю место.

Постановка задачи.

Класична завдання про коммивояжере виглядає наступним образом:

Є N міст, що має обійти комівояжер з мінімальними витратами. У цьому з його маршрут накладається два ограничения:

* маршрут може бути замкнутим, тобто комівояжер маю повернутися у той місто, із якої він почав движение;

* у кожному з міст комівояжер повинен побувати точно одного разу, тобто обов’язково обійти всі міста, у своїй не побувши жодного щодо одного місті дважды.

Для розрахунку витрат існує матриця умов, яка містить видатки перехід із кожного у кожний, у своїй вважається, які можна перейти із будь-якої міста, у будь-який, ще ж (в матриці хіба що викреслюється діагональ). Метою рішення є перебування маршруту, задовольняючого всім умовам і навіть має мінімальну суму затрат.

Алгоритм решения.

У курсової роботі на вирішення завдання про коммивояжере застосовується метод гілок і національних кордонів, належить до методам дискретної оптимізації. По суті, це повний перебір рішень, який оптимізується завдяки тому, що з переборі варіантів за ознаками відтинаються неоптимальні безлічі перебору. Оскільки кількість вершин від рівня до рівня зростає у факториальной прогресії, то відсікання вершин верхніх рівнів значно скорочує загальна кількість які перебираються вариантов.

Загальна схема методу така (дана програмна реализация):

1. Усі безліч розбивається на N-1 підмножин, кожна з яких оцінюється верхньої та нижньої оценками.

2. Виробляється відсів неоптимальных множин з такого критерію: якщо нижня оцінка (рішення релаксированной завдання) більше від мінімальної з чільних оцінок (рішень нерелаксированной завдання), то безліч вважається очевидно неоптимальним і відсікається, інакше залишається до наступній итерации.

3. Перебуває безліч з кращого нижньої оцінкою (прогнозом) і дробиться кількості однакову розмірність вихідної матриці мінус кількість вже пройдених (фіксованих для даного безлічі) городов.

4. Знаходяться мінімальні верхня і нижня оцінка. Якщо вони самі рівні й досягнуто однією й тому самому безлічі, це отже, що отримано оптимальне рішення і алгоритм завершує роботу, інакше повернення до кроку 2.

Математична модель задачи.

N — число городов.

Ci j, і, j=1.N — матриця витрат, де Ci j — видатки перехід із i-го міста, у j-й.

Xi j — матриця переходів з компонентами:

Xi j = 1, якщо комівояжер робить перехід із i-го міста, у j-й,.

Xi j = 0, а то й робить перехода,.

де і, j = 1. N і i? j.

Критерий:

(1).

Ограничения:

і = 1. N (2).

j = 1. N (3).

Ui — Uj + N? Xi j? N-1, і, j = 1. N, і? j. (4).

Доказ, що модель (1−4) описує завдання про коммивояжере:

Умова (2) означає, що комівояжер з кожного виїжджає лише одне раз; умова (3) — в'їжджає у кожний місто лише одне раз; умова (4) — забезпечує замкнутість маршруту, що містить N міст, і що містить замкнутих внутрішніх петель.

Розглянемо умова (4). Застосуємо метод докази від протилежного, тобто припустимо, що умова (4) виконується для деякого подцикла T з R міст, де R.

.

Так как.

.

то N? R? (N -1), де R.

Отже, немає замкнутого подцикла із кількістю міст меншим, ніж N.

Покажемо, що є Ui, яке замкнутого циклу, який починається у певному початковому пункті, задовольняють умові (4). За всіх Xi j (j-й місто не відвідується після i-го) в (4) маємо Ui — Uj? N — 1, що припустимо з довільних Ui і Uj.

Нехай на деякому R-ом кроці i-го місто відвідується перед j-м, тобто Xi j = 1. З огляду на довільності значень Ui і Uj між іншим Ui = R, а Uj = R + 1, тоді з (4) имеем:

Ui — Uj + N? Xi j? R — (R — 1) + N = N — 1.

Отже, є такі кінцеві значення для Ui і Uj, що з маршруту, що містить N міст, умова (4) задовольняється як нерівність чи строге рівність. Отже, модель (1−4) описує завдання про коммивояжере.

Опис програмної реалізації алгоритма.

У конкурсній програмі реалізований класичний варіант методу гілок і національних кордонів, тобто алгоритм рішення следующий:

1. Усі безліч розбивається на N-1 підмножин, кожна з яких оцінюється верхньої та нижньої оценками.

2. Виробляється відсів неоптимальных множин з такого критерію: якщо нижня оцінка (рішення релаксированной завдання) більше від мінімальної з чільних оцінок (рішень нерелаксированной завдання), то безліч вважається очевидно неоптимальним і відсікається, інакше залишається до наступній итерации.

3. Перебуває безліч з кращого нижньої оцінкою (прогнозом) і дробиться кількості однакову розмірність вихідної матриці мінус кількість вже пройдених (фіксованих для даного безлічі) городов.

4. Знаходяться мінімальні верхня і нижня оцінка. Якщо вони самі рівні й досягнуто однією й тому самому безлічі, це отже, що отримано оптимальне рішення і алгоритм завершує роботу, інакше повернення до кроку 2.

У цьому передбачена можливість зміни напрями критерію, тобто можливість вирішення завдання на максимум.

Найбільший вибір програма надає за крок 3, де реалізовано чотири методу розрахунку нижньої оцінки числа й три методу розрахунку верхньої оцінки безлічі. Спочатку розглянемо методи перебування нижньої оцінки, тобто рішення релаксированной задачи:

Метод 1: «З кожного » .

Розраховується ціна маршруту по зафіксованим для даної вершини містам. Потім у кожному рядку матриці, де немає фіксованих елементів, перебуває мінімальний елемент (у програмі реалізовано функцією Min_Col) і додається до спільної сумі, тобто беруться найближчі міста для виходу із усіх ще пройдених міст. Програмна реалізація # VHCOUNT. H₁.

Метод 2: «У середньому кожен місто » .

Розраховується ціна маршруту по зафіксованим для даної вершини містам. Потім у кожному стовпці матриці, у якому фіксованих елементів перебуває мінімальний елемент (у програмі реалізовано функцією Min_Str) і додається до спільної сумі, тобто беруться найближчі міста для входити в досі не пройдені міста. Програмна реалізація # VHCOUNT. H₂.

Метод 3: «Комбінований » .

Розраховуються оцінки за попереднім двом методам і їх вибирається максимальна, тобто гірший прогноз для даної вершини. Програмна реалізація — VHCOUNT. H₁₂.

Метод 4: «Угорський метод » .

Програмна реалізація — SOLUTION. DOWNLEV.

Розраховується ціна маршруту по зафіксованим для даної вершини містам. Потім формується матриця з елементів незайнятих рядків і шпальт размерностью M? M, де M = N # кількість пройдених міст. Ця матриця передається угорському алгоритму, який описаний нижче (Програмна реалізація — VENGRSOL. CENTRAL_CONTROL):

Попередній етап. (У конкурсній програмі реалізований процедурою Begin_Set).

Розшукують мінімальний елемент в стовпці і із усіх елементів цього шпальти послідовно віднімають мінімальний. Цю операцію долають з усіх стовпчиками матриці. У результаті виходить матриця, у кожному стовпці якої є по крайнього заходу один нуль.

Розглядаємо рядок отриманої матриці і з кожного її елемента віднімаємо мінімальний елемент цього рядка. Провівши цю операцію з кожним рядком, отримуємо матрицю з неотрицательными елементи, у кожному стовпці і рядку якої є по крайнього заходу один нуль. Зазначимо довільний нуль у першому стовпці зірочкою (*). Далі переглядаємо другий стовпець, і якщо у неї є нуль, що у рядку, де немає нуля зі зірочкою, то відзначаємо зірочкою. Аналогічно переглядаємо все стовпчики на цьому попередній етап закінчується. (У конкурсній програмі реалізовано процедурою Make_Label_Zero).

(К+1)-я итерация.

Припустимо, що К-я ітерація вже проведена і цього отримана деяка матриця. Якщо матриці N нулів зі зірочкою (*), то процес розв’язування закінчується. Якщо ж у матриці нулів зі зірочкою менше N, то переходимо до (К+1)-й ітерації. (У конкурсній програмі перевіряється процедурою Central_Control).

Кожна ітерація починається перших вражень і закінчується другим етапом. Між ними може бути кілька раз проводитися третій, етап. Перед початком ітерації значком (+) виділяють стовпчики матриці, містять нулі зі зірочкою (0*). (У конкурсній програмі реалізовано процедурою Make_Label_Col).

ПЕРШИЙ ЭТАП.

Переглядають невиділені стовпчики (якщо перший етап проводиться після третього, то також відтинають і виділені рядки). (У конкурсній програмі реалізовано процедурою Check_Zero). Якщо у тому числі бракуватиме нульових елементів, то переходять до третьої этапу.

Якщо ж невыделенный нуль в матриці виявлено, то може бути одне із двох випадків :

1. в рядку, що містить нуль, є також нуль зі зірочкою (0*) ;

2. ця рядок зовсім позбавлений нуль зі звездочкой.

(Перевірка випадку виробляється у процедурі Central_Control).

У першому випадку невыделенный нуль відзначають штрихом («) і виділяють рядок, де він міститься, постановкою праворуч від неї значком (+). Потім знищують знак (+) над стовпцем, що містить нуль зі зірочкою (0*).

Далі переглядають цей стовпець, відшукують у ньому невыделенный нуль (пошук відбувається лише серед непомічених рядків), непомеченный зірочкою, відзначають його штрихом і виділяють рядок, що містить такий нуль. Потім переглядають цю рядок, відшукуючи у ній нуль зі зірочкою (0*). Цей процес відбувається за кінцеве число кроків закінчується однією з наступних фіналів :

* все нулі матриці виділено, себто в виділених рядках і шпальтах. У цьому переходять до третьої этапу;

* є невыделенный нуль в рядку, де немає нуля зі зірочкою. І тут переходять до другого етапу, зазначаючи останній усе своєю чергою нуль штрихом («).

(У конкурсній програмі реалізовано процедурою Find_Zero і подпроцедурами Find_Zero_in_Col і Find_Zero_in_Line; вибір випадку виробляється процедурою Central_Control).

ДРУГИЙ ЭТАП.

Будують такий ланцюжок з елементів матриці: вихідний нуль зі штрихом (0 "), нуль зі зірочкою (0*), що у одному стовпці з цим, нуль зі штрихом (0 "), що у однієї рядку з попереднім нулем зі зірочкою (0*), тощо. Отже, ланцюжок утворюється пересуванням від 0 «до 0* по стовпцю, від 0* до 0 «по рядку тощо. (У конкурсній програмі реалізовано процедурою Chain подпроцедурами Find_Link_in_Col і Find_Link_in_Line, і навіть внутрішньої подпроцедурой процедури Chain процедурою NewLink).

Далі над елементами ланцюжка, що стоять на непарних місцях (0 "), ставимо зірочки, знищуючи їх над парними елементами (0*). (У конкурсній програмі реалізовано процедурою Change_Chain). Потім знищуємо все штрихи над елементами матриці і знаки +. (У конкурсній програмі реалізовано процедурою Erase_Label) У цьому кількість незалежних нулів планується збільшити на одиницю. (К+1)-я ітерація закончена.

ТРЕТІЙ ЭТАП.

До цього етапу переходять після першого, коли всі нулі матриці виділено, себто в виділених рядках і шпальтах. У разі серед невыделенных елементів матриці вибирають мінімальний елемент і позначають його H (H>0). Далі віднімають H із усіх елементів матриці, котрі стоять у невыделенных рядках і додають всім елементам матрицями, розміщеним у виділених шпальтах. Отримують нову матрицю, еквівалентну вихідної. (У конкурсній програмі реалізовано процедурами Find_Min_No_Label (перебування мінімального елемента) і Plus_Minus (віднімання і прибавление)).

Оскільки серед невыделенных елементів з’являться нові нулі (за визначенням), переходять до першого етапу, розглядаючи перетворену матрицю. Завершивши перший етап, або переходять до другого, або знову до третьої етапу, коли всі нулі матриці виявляються виділеними. (У конкурсній програмі вибір реалізований у процедурі Central_Control).

У першому випадку після проведення другого етапу ітерація закінчується, тоді як у другому — після проведення третього етапу отримують нову матрицю, у якій буде невиділені нулі, й усю послідовність операцій, починаючи з першим етапом, необхідно повторити. Після кінцевого числа повторень черговий перший етап обов’язково закінчиться переходом другого етап і кількість незалежних нулів збільшиться на одиницю. (К+1)-я ітерація закончена.

Нині можна можливість перейти до розгляду методів отримання верхньої оценки:

Метод 1: «По зростанню номерів » .

Розраховується ціна маршруту по зафіксованим для даної вершини містам. Потім працює наступний алгоритм перебування маршрута:

1. Розраховується число пройдених городов.

2. Якщо пройдено все міста, то вихід, інакше з останнього міста незакінченого маршруту додається перехід у ще непройденный місто з мінімальним номером і повернення до кроку 1.

Програмна реалізація # VHCOUNT. V₁.

Метод 2: «З оптимізацією » .

Розраховується ціна маршруту по зафіксованим для даної вершини містам. Потім працює наступний алгоритм перебування маршрута:

1. Розраховується число пройдених городов.

2. Якщо пройдено все міста, то вихід, інакше з останнього міста незакінченого маршруту додається перехід у місто, перехід у який має мінімальних витрат і повернення до кроку 1.

Програмна реалізація — VHCOUNT. V₂.

Метод 3: «Угорський метод » .

Він грунтується на нижньої оцінці, одержуваної угорським методом. При установці розрахунку верхньої оцінки даним методом розрахунок нижньої оцінки автоматично встановлюється на угорський метод, оскільки необхідною умовою і те, що у кожному рядку всіх і кожного стовпці лише одне позначка. Алгоритм роботи методу следующий:

1. Отримуємо рішення релаксированной завдання угорським методом.

2. Перевіряємо скільки міст пройдено.

3. Якщо пройдено все міста, отже отримано рішення нерелаксированной завдання то перехід до 5 пункту, інакше перехід до пункту 4.

4. У рядку міста, із якого повернення у перший, знаходимо мінімальне значення серед шпальт ще пройдених міст і першого города.

5. Якщо новому маршруті пройдено N міст, те з останнього міста призначаємо перехід у первый.

6. Якщо маршрут замкнутий, то вихід із алгоритму, інакше перехід до пункту 2.

Метод схожий із методом «З оптимізацією », але особливий тим, що відсутні додаткові перевірки, оскільки вихідне рішення вже підпорядковується вищевказаним умовам. Програмна реалізація — SOLUTION. LEVELS.

Опис програмного интерфейса.

Інтерфейс програми побудований за структурі, аналогічної Turbo-средам, але з містить объекто-ориентированного внутрішнього змісту. Головне меню має таку структуру:

Розглянемо меню по пунктам:

Дані. Нова задача.

Цей пункт меню викликає спочатку процедуру введення розмірності завдання, потім процедуру її редагування. При виклик виробляється обнуління всіх поточних значень матрицы.

Дані. Розмірність задачи.

Цей пункт меню активізує процедуру зміни розмірності завдання. У цьому якщо матриця зменшується, то значення відтятою частини не зануляются і за наступному збільшенні розмірності може бути знову використані. Що стосується збільшення розміру за більший значення крайні елементи виявляються нулевыми.

Дані. Редактирование.

Пункт активізує процедуру введення початковій матриці умов. Процедури реалізований вертикальний і горизонтальний скролінг матриці, і навіть скролінг всередині введеної рядки. З іншого боку можлива настроювання ширини рядки введення, яка описано на пункті меню «Опції. Введення » .

Дані. Генерация.

Пункт активізує процедуру, генерирующую матрицю випадково в заданому діапазоні значень, який задається перед генерацией.

Дані. Фундаментальна обізнаність із диском. Зберегти матрицу.

Цей пункт дозволяє зберегти поточну вихідну матрицю в файл на диск. Можливо активізований будь-якої миті роботи меню клавіш F2.

Дані. Робота з диском. Відкрити матрицу.

Цей пункт дозволяє вважати з диска вихідну матрицю. Можливо активізований будь-якої миті роботи меню клавіш F3.

Рішення. Почати решение.

Цей пункт запускає роботу алгоритму рішення, використовуючи поточні настройки.

Рішення. Останній результат.

Цей пункт дозволяє вивести останній отриманого результату решения.

Режим рішення. Блок: Мінімум — Максимум.

Цей блок дозволяє вибрати собі напрямок виконання завдання щонайменше чи максимум. Значення за умовчанням — Минимум.

Режим рішення. Блок: Автоматичний — Обучающий.

Цей блок дозволяє вибрати між автоматичним і обучающим режимами виконання завдання. Значення за умовчанням — Автоматический.

Розрахунок оцінок. Блок «Верхня оцінка » .

Цей блок дозволяє вибрати метод розрахунку верхньої оцінки. При виборі третього методу розрахунку («Угорський метод »), під час вирішення автоматично встановлюється четвертий метод розрахунку нижньої оцінки («Угорський метод »). Значення за умовчанням — Угорський метод.

Розрахунок оцінок. Блок «Нижня оцінка » .

Цей блок дозволяє вибрати метод розрахунку нижньої оцінки. Якогось впливу метод розрахунку верхньої оцінки вибір не надає. Значення за умовчанням — Угорський метод.

Опції. Часы.

Цей пункт дозволяє включити й вимкнути часы.

Опції. Звук.

Цей пункт дозволяє включити й вимкнути звук.

Опції. Ввод.

Цей пункт дозволяє поставити ширину рядки введення при редагуванні початковій матриці завдання. Значення за умовчанням — 6.

Опції. Screen Saver.

Цей пункт дозволяє поставити час затримки спрацьовування Screen Saver-а. Час вказується в хвилинах. Значення за умовчанням — 5 минут.

Опції. Зберегти опции.

Цей пункт дозволяє запам’ятати стан годині і звуку в файлі (Shadow.dsk).

Выход.

Цей пункт здійснює вихід із программы.

Опис программы.

Структурно програма складається з дев’яти модулей:

1. DESCRIPT. PAS — опис всіх глобальних змінних програми. Виконуваних процедур не содержит.

2. IOMENU. PAS — модуль в обробці меню. Автори — Ілля Осипов, Андрій Шапошников.

3. IOCRT. PAS — модуль екранних функцій виведення. Автор — Ілля Осипов.

4. INOUT. PAS — модуль вводу-виводу. Автор — Андрій Шапошников.

5. SERVICE. PAS — модуль системних процедур програми. Автор — Андрій Шапошников.

6. VHCOUNT. PAS — модуль розрахунку оцінок. Автор — Ігор Яров.

7. SOLUTION. PAS — модуль загального управління рішенням. Автори — Ігор Яров, Андрій Шапошников.

8. VENGRSOL. PAS — модуль розрахунку оцінок угорським методом. Автор — Андрій Шапошников.

9. SHADOW. PAS — модуль загального управління програмою. Автор — Андрій Шапошников.

Процедури, що використовуються під час вирішення завдання описані раніше. І лише додати, бо загальне управління алгоритмом гілок і національних кордонів здійснюється процедурою OverDrive в автоматичному режимі рішення і процедурою StudyMode в обучающем режимі решения.

Процедури інтерфейсу програми розвитку й глобальні перемінні описані ниже.

Модуль INOUT.PAS.

Procedure MatrIn (var a: workmatr; var sz: byte; msize, diag: boolean);

Процедура введення початковій матриці умов. Передані параметры:

var a: workmatr — покажчик на матрицю (описана глобальної переменной).

var sz: byte — поточна розмірність завдання (описана глобальної переменной).

msize: boolean — можливість зміни розмірів матриці (True — може бути изменены).

diag: boolean — доступність головною діагоналі (False — введення на головною діагоналі запрещен).

Procedure Inp (x, y, l: byte; gg: char; var qq: char; var a: real; var p. s: string; st_r: boolean; scroll: boolean; attrib: byte);

Процедура введення рядки з внутрішнім скроллингом. Передані параметры:

x, y: byte — координати початку рядки ввода.

l: byte — ширина рядки ввода.

gg: char — останній запроваджений символ на початок редактирования.

var qq: char — останній запроваджений символ при редактировании.

var a: real — яке real-число.

var p. s: string — возвращаемая строка.

st_r: boolean — перемикач введення real / string (True — введення real-числа).

scroll: boolean — вимикач скроллинга всередині рядки (True — скролінг включен).

attrib: byte — поточні колірні настройки.

Procedure M_Size (var qq: char);

Процедура зміни розміру матриці. Передані параметры:

var qq: char — останній запроваджений символ при редактировании.

Procedure New_Task (var b: workmatr);

Процедура генерації нового завдання. Передані параметры:

var b: workmatr — покажчик на матрицю (описана глобальної переменной).

Procedure Matr_Rnd (var a: workmatr);

Процедура випадкової генерації матриці. Передані параметры:

var a: workmatr — покажчик на матрицю (описана глобальної переменной).

Procedure ShowSolve (Solve: vertex);

Процедура виведення останнього отриманого рішення. Передані параметры:

Solve: vertex — запис, що містить всіх параметрів останнього решения.

Function ChooseFile (Title: string; var qq: char): string;

Функція введення імені файла. Передані параметры:

Title: string — заголовок окна.

var qq: char — останній запроваджений символ при редактировании.

ChooseFile: string — рядок, що містить ім'я файла.

Procedure FileOpen (var b: workmatr; var NN: byte);

Процедура читання з диска матриці завдання. Передані параметры:

var b: workmatr — покажчик на матрицю (описана глобальної переменной).

var NN: byte — поточна розмірність завдання (описана глобальної переменной).

Procedure FileSave (var b: workmatr; var NN: byte);

Процедура записи на диск матриці завдання. Передані параметры:

var b: workmatr — покажчик на матрицю (описана глобальної переменной).

var NN: byte — поточна розмірність завдання (описана глобальної переменной).

Procedure InpWidht;

Процедура завдання ширини рядки введення при редагуванні початковій матриці задачи.

Procedure InpSaver;

Процедура завдання часу затримки спрацьовування Screen saver-а.

Function ChooseVertex (var N: Point; var Count: integer; var Act: char): Point;

Процедура вибору вершини в обробці при обучающем режимі рішення. Передані параметры:

var N: Point — покажчик початку списку вершин.

var Count: integer — загальна кількість кінцевих вершин.

var Act: char — код клавіші, визначальний дії, вироблені над вершиной.

ChooseVertex: Point — покажчик на її вершину, з якої відбуваються действия.

Модуль SERVICE.PAS.

Function GetKey: char;

Функція, повністю еквівалентна функції Readkey (має й певні відмінності з обробки переривань клавиатуры).

Procedure Knock;

Процедура, яка виробляє щелчок.

Procedure Clock_on;

Процедура включення внутрішнього таймера программы.

Procedure Clock_off;

Процедура вимикання внутрішнього таймера программы.

Procedure SaveIt;

Процедура збереження поточних установок програми в файлі shadow.dsk.

Procedure RestoreIt;

Процедура відновлення установок програми. За відсутності файла shadow. dsk робить установки по умолчанию.

Function Stop: boolean;

Процедура обробки клавіші Escape в фоновому режиме.

Procedure GetDaTi (var Time: Stime);

Процедура взяття часу й дати у внутрішній формат програми. Передані параметры:

var Time: Stime — поточні час й час у внутрішньому формате.

Procedure TIME (var Time1, Time2: Stime);

Процедура розрахунку часу роботи алгоритму. Передані параметры:

var Time1: Stime — час початку алгоритма.

var Time2: Stime — час алгоритма.

Function ProcExit: word;

Процедура підтвердження виходу з программы.

Модуль DESCRIPT.PAS.

Змінні, управляючі роботою інтерфейсу і настроюванням решения.

M: Pmenu ;

Покажчик на основне меню программы.

Sel: Word ;

Поточний обраний пункт меню.

ch, sk, gg, qq: char ;

Змінні до роботи з клавиатурой.

MethodH, MethodV, Tip, Direc: word ;

Змінні що визначають режим решения.

TimeSScr: Longint ;

Час затримки спрацьовування Screen Saver-а.

w: boolean ;

Тимчасова булевская переменная.

SScrAct,.

Активність Screen Saver-а.

ClockAct,.

Активність часов.

SoundAct,.

Активність звука.

SoluAct: boolean ;

Активність решения.

TimeN, TimeE: Stime ;

Час початку будівництва і завершення решения.

TempStr: string ;

Тимчасова string-переменная.

TempReal: real ;

Тимчасова real-переменная.

Len,.

Довжина елемента матрицы.

Step: byte ;

Інтервал виведення елементів матрицы.

Типи, використовувані під час роботи алгоритму решения.

WorkMatr = array [ 1. Nmax+1, 1. Nmax+1 ] of real ;

Тип робочої матрицы.

Solu = array [ 1. Nmax ] of byte ;

Вектор решения.

Labels = record.

gor, ver: Solu ;

end ;

Запис, яка містить вектора фіксованих городов.

Lab = array [ 1. Nmax ] of boolean ;

Масив меток.

Point =^Vertex ;

Покажчик на вершину.

Vertex = record.

Hi, Lo: real ;

Go: Solu ;

Res: Solu ;

Attr: Char ;

Prev, Next: Point ;

end ;

Запис, яка містить все властивості одиничної вершины.

Змінні, використовувані під час роботи алгоритму решения.

b,.

з: workmatr ;

Вихідна матриця завдання и.

матриця, використовувана алгоритмом угорського метода.

x: Solu ;

Вектор решения.

і, j,.

Індексні переменные.

NN: byte ;

Поточна розмірність задачи.

MaxR, MinR: real ;

Змінні, що визначають діапазон генерації матрицы.

LastSolve: Vertex ;

Запис, що містить параметри останнього решения.

1. Мамиконов О. Г. «Основи побудови АСУ », Москва, «Вищу школу «- 1981.

2. Схрейвер А. «Теорія лінійного і целочисленного програмування », Москва, «Світ «- 1981.

3. Таха Х. «Введення ЄІАС у дослідження операцій », Москва, «Світ «- 1985.

4. Вовчків Б.А., Ліфшиц І.І. «Автоматизовані системи в плануванні «, Москва, «Економіка «- 1980.

5. Касаткін А.І. «Управління ресурсами », Мінськ, «Вищу школу «-1992.

6. Журнал «PC Magazine «(№ 3 — 1994), стор. 45 — 48.