На головну    

 Завдання про комівояжера - Економіко-математичне моделювання

Нижегородський Ордена Трудового Червоного Прапора

Державний Університет ім. Н.І. Лобачевського

Економічний факультет

Кафедра інформатики та обчислювальної техніки

Курсова робота

з програмного забезпечення

тема:

Рішення завдання про комівояжера

Виконали:

Шапошников А.Д.

Ярів Є.І.

Науковий керівник:

Громницький В.С.

Нижній Новгород

1995

Зміст

Оглавление... 2

Введение... 3

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

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

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

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

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

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

Литература... 15

Введення

В даний час швидко розвивається науково-технічна революція. З'явившись в 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 міст, які повинен обійти комівояжер з мінімальними витратами. При цьому на його маршрут накладається два обмеження:

· Маршрут повинен бути замкнутим, тобто комівояжер повинен повернутися в те місто, з якого він почав рух;

· В кожному з міст комівояжер повинен побувати точно один раз, тобто треба обов'язково обійти всі міста, при цьому не побувавши в жодному місті двічі.

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

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

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

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

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

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

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

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

N - число міст.

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

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

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

Xi j = 0, якщо не здійснює переходу,

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

Критерій:

(1)

Обмеження:

, I = 1..N (2)

, J = 1..N (3)

Ui - Uj + N ? Xi j ? N-1, i, j = 1..N, i ? 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) описує завдання про комівояжера.

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

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

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

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

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

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

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

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

Метод 1: "З кожного міста".

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

Метод 2: "У кожне місто".

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

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

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

Метод 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). Якщо серед них не виявиться нульових елементів, то переходять до третього етапу.

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

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

 цей рядок не містить нуль із зірочкою.

(Перевірка випадку проводиться у процедурі 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.

Програмна реалізація - VHCOUNT. V_1

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

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

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

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

Програмна реалізація - VHCOUNT. V_2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дані. Редагування.

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

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

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

Дані. Робота з диском. Зберегти матрицю.

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

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

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

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

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

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

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

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

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

Режим рішення. Блок: Автоматичний - Навчальний.

Цей блок дозволяє вибрати між автоматичним і навчальним режимами рішення задачі. Значення за замовчуванням - Автоматичний.

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

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

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

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

Опції. Годинник.

Даний пункт дозволяє включити і вимкнути годинник.

Опції. Звук.

Даний пункт дозволяє включити і вимкнути звук.

Опції. Введення.

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

Опції. Screen Saver.

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

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

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

Вихід.

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

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

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

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

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

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

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

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

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

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

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

 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 s: string; st_r: boolean; scroll: boolean; attrib: byte);

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

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

l: byte - ширина рядка введення.

gg: char - останній введений символ до початку редагування.

var qq: char - останній введений символ при редагуванні.

var a: real - повертається real-число.

var 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,

 c: workmatr;

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

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

 x: Solu; Вектор рішення

 i, j, Індексні змінні

 NN: byte; Поточна розмірність задачі

 MaxR, MinR: real; Змінні, що визначають діапазон генерації матриці

 LastSolve: Vertex; Запис, що містить параметри останнього рішення

Література

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

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

 Таха Х. "Введення в дослідження операцій", Москва, "Мир" - 1985.

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

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

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

© 8ref.com - українські реферати