Анотація
Транспортна задача з правильним балансом полягає у тому, щоб знайти оптимальний план по заданій таблиці перевезень, при якому вартість перевезень буде мінімальна.
Таке завдання актуальна в областях пов'язаних з транспортуванням вантажів.
Зміст
Введення. 3
Постановка завдання. 4
Метод рішення. 5
Мова програмування. 7
Опис алгоритму. 8
Опис основних структур даних. 12
Опис інтерфейсу з користувачем. 14
Висновок. 16
Література. 17
Текст програми .. 18
Введення
Завдання полягає в тому, щоб інтуїтивно такий спосіб перевезення при якому витрати пов'язані з перевезенням були б мінімальні
Це завдання зацікавила мене тому, що її рішення напряму пов'язане з економією коштів. Важливо знаходження такого алгоритму, який дозволить найбільш оптимально вирішити задачу.
Рішення транспортної задачі починається із знаходження опорного плану. Для цього існують різні способи. Наприклад, спосіб "північно-західного кута" Розглянемо конкретний прикладі:
Умови транспортної задачі задані транспортної таблицею.
Будемо заповнювати таблицю перевезеннями поступово починаючи з лівої верхньої комірки ("північно-західного кута" таблиці). Будемо міркувати при цьому таким чином. Пункт В1 подав заявку на 18 одиниць вантажу. Задовольнимо цю заявку за рахунок запасу 48, наявного в пункті А1, і запишемо перевезення 18 в клітці (1,1). Після цього заявка пункту В1 задоволена, а в пункті А1 залишилося ще 30 одиниць вантажу. Задовольнимо за рахунок них заявку пункту В2 (27 одиниць), запишемо 27 у клітці (1,2), решта 3 одиниці пункту А1 призначимо пункту В3. У складі заявки пункту В3 залишилися незадоволеними 39 одиниць. З них 30 покриємо за рахунок пункту А2, ніж його запас буде вичерпано, і ще 9 візьмемо з пункту А3. З решти 18 одиниць пункту А3 12 виділимо пункту В4; залишилися 6 одиниць призначимо пункту В5, що разом з усіма 20 одиницями пункту А4 покриє його заявку. На цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж згідно своєї заявки. Це виражається в тому, що сума перевезень в кожному рядку дорівнює відповідному запасу, а в стовпці - заявці. Таким чином, нами відразу ж складений план перевезень, що задовольняє балансовим умов. Отримане рішення є опорним вирішенням транспортної задачі:
Складений нами план перевезень, не є оптимальним за вартістю, так як при його побудові ми зовсім не врахували вартість перевезень Сi, j.
2.Распределітельний метод досягнення оптимального плану
Тепер спробуємо поліпшити план, складений способом "північно-західного кута". Перенесемо, наприклад, 18 одиниць з клітки (1,1) в клітину (2,1) і щоб не порушити балансу перенесемо ті ж 18 одиниць з клітки (2,3) в клітину (1,3). Отримаємо новий план. Підрахувавши вартість опорного плану (вона ровняется 1039) і вартість нового плану (вона ровняется 913) неважко переконатися що вартість нового плану на 126 одиниць менше. Таким чином за рахунок циклічної перестановки 18 одиниць вантажу з одних клітин в інші нам вдалося знизити вартість плану:
На цьому способі зменшення вартості надалі і буде заснований алгоритм оптимізації плану перевезень. Циклом в транспортній задачі ми будемо називати кілька зайнятих клітин, з'єднаних замкнутої ламаної лінією, яка в кожній клітині робить поворот на 90 °.
Існує кілька варіантів циклу:
1.) 2.) 3.)
Неважко переконатися, що кожен цикл має парне число вершин і значить, парне число ланок (стрілок). Домовимося відзначати знаком "+" ті вершини циклу, в яких перевезення необхідно збільшити, а знаком "-" ті вершини, в яких перевезення необхідно зменшити. Цикл із зазначеними вершинами будемо називати "зазначеним". Перенести якусь кількість одиниць вантажу по зазначеному циклу - це значить збільшити перевезення, які стоять в позитивних вершинах циклу, на цю кількість одиниць, а перевезення, які стоять в негативних вершинах зменшити на ту ж кількість. Очевидно, при перенесенні будь-якого числа одиниць по циклу рівновагу між запасами та замовленнями не змінюється: як і раніше сума перевезень в кожному рядку дорівнює запасам цього рядка, а сума перевезень в кожному стовпці - заявці цього стовпця. Таким чином при будь-якому циклічному перенесення, який полишає перевезення невід'ємними допустимий план залишається допустимим. Вартість же плану при цьому може змінюватися: збільшуватися або зменшуватися. Назвемо ціною циклу збільшення вартості перевезень при переміщенні однієї одиниці вантажу по зазначеному циклу. Очевидно ціна циклу рівна алгебраїчній сумі вартостей, які стоять у вершинах циклу, причому стоять в позитивних вершинах беруться зі знаком "+", а в негативних зі знаком "-". Вершини чергуються починаючи з "+". Позначимо ціну циклу через g. При переміщенні однієї одиниці вантажу по циклу вартість перевезень збільшується на величину g. При переміщенні по ньому k одиниць вантажу вартість перевезень збільшитися на kg. Очевидно, для поліпшення плану має сенс переміщати перевезення тільки за тим циклам, ціна яких негативна. Кожного разу, коли нам вдається зробити таке переміщення вартість плану зменшується на відповідну величину kg. Так як перевезення не можуть бути негативними, ми будемо користуватися лише такими циклами, негативні вершини яких лежать в базисних клітинах таблиці, де стоять позитивні перевезення. Якщо циклів з негативною ціною в таблиці більше не залишилося, це означає, що подальше поліпшення плану неможливо, то є оптимальний план досягнутий.
Метод послідовного поліпшення плану перевезень і полягає в тому, що в таблиці відшукуються цикли з негативною ціною, за ним переміщуються перевезення, і план поліпшується до тих пір поки циклів з негативною ціною вже не залишиться. Можна довести, що для будь-якої вільної клітці транспортної таблиці завжди існує цикл і притому єдиний, одна з вершин якого лежить в цій вільній клітці, а всі інші в базисних клітинах. Якщо ціна такого циклу, з плюсом у вільній клітці, негативна, то план можна поліпшити переміщенням перевезень по даного циклу. Кількість одиниць вантажу k, яке можна перемістити, визначається мінімальним значенням перевезень, що стоять в негативних вершинах циклу (якщо перемістити більше число одиниць вантажу, виникнуть негативні перевезення).
Застосований вище метод відшукання оптимального рішення транспортної задачі називається розподіленим; він полягає у безпосередньому відшуканні вільних клітин з негативною ціною циклу і в переміщенні перевезень по цьому циклу.
1. Visual Basic for Applications був написаний спеціально для Office додатків тобто потенційному замовникові досить встановить Office і запустити Ms Excel щоб програми працювала
2. Так як Транспортна задача заданна у вигляді таблиці то зручніше вирішувати її використовую можливості табличного редактора
3. Це одна з мов, в якому я непогано розбираюся. Тому мені зручніше писати програму з допомогою VBA.
А) Виконується перевірка на правильність введення. Якщо введені числа то
Б) Вимальовується таблиця
2. Після промальовування таблиці користувачеві пропонується заповнити таблицю вартості перевезень
А) Після підтвердження заповнення користувачем станься перевірка на правильність введення
Б) Підсумовується рядок Запити і стовпець Запаси виконується перевірка на рівність. Якщо рівні то
3. Виконуємо побудова опорного плану методом Північно-західного кута
A) БУДУВАТИ нульову матрицю заданого розміру на "лісте2"
Б) Потім методом північно-західного кута виходячи з даних на аркуші "Дані"
В) Переносимо вийшла таблицю на аркуш "Цикли"
4.Іспользуем метод розподілу наступним чином
З наведеного прикладу вже можна виділити, як алгоритм перебирає шляху. Він діє за такою схемою:
0. Початкове значення j = 1 (перше місце в маршруті).
1. Ми знаходимося в місті k.
2. Для кожного міста (i = від 1 до n)
3. Розглядаємо місто i.
4. Якщо це місто ще не відвідано,
4.1. тоді переходимо до міста i; j збільшуємо на одиницю. Додаємо номер міста до маршруту на місце j. Позначаємо місто як відвіданий. Переходимо до пункту 1 (k = i).
4.2. інакше йти нікуди, тобто всі міста ми відвідали.
4.2.1. якщо j = кількості міст (n), тобто ми дісталися до останнього пункту в маршруті і наш шлях сформований,
тоді порівнюємо довжину шляху з довжиною мінімального маршруту.
4.2.2. Позначаємо місто як не відвіданий і виходимо з нього. Зменшуємо j на одиницю.
5. Беремо наступний місто (i = i +1).
Опис основних структур даних
Тепер розглянемо структуру програми, опишемо класи та процедури, які були змінені і наповнені кодом.
Програма складається з 4 класів:
1. CAboutDlg пов'язаний з вбудованим діалоговим вікном «Про програму».
2. CKurs_LipinApp управляє запуском програми, але не пов'язаний з яким-небудь діалоговим вікном. [1]
3. CKurs_LipinDlg пов'язаний з вікном IDD_KURS_LIPIN_DIALOG. Цей клас організовує постановку і рішення задачі.
4. CSetting пов'язаний з вікном IDD_DIALOG1. У вікні вводяться параметри до задачі - відстані між містами.
Клас CKurs_LipinDlg.
На початку при виклику функції OnInitDialog () змінні заповнюються початковими даними. Потім з файлу «table.ini» зчитується таблиця відстаней між містами. І тепер діалогове вікно готове до роботи з користувачем.
Функція OnPaint () виводить на екран карту, дозволяє виділяти міста, вибрані користувачем, а також з'єднує міста лініями-шляхами, коли задача вирішена. Крім того, забезпечується висновок інформації для користувача: пояснення, довжина мінімального шляху і список відстаней між містами, складові мінімальний шлях.
При натисненні лівої кнопкою миші викликається функція
OnLButtonDown (). Вона визначає за якого міста клацнув користувач і ставить / знімає виділення з нього. Також тут здійснюється перевірка на кількість виділених міст, тому що час очікування рішення задачі для кількості понад 13 міст стане не задовільним (від 1,5 хвилин і більше). Тому програма видасть повідомлення, якщо ми спробуємо вийти за допустимі межі.
Кнопка «Вибрати стандартні міста» виділяє міста, які потрібно з'єднати в умові завдання, а саме Москва, Ярославль, Нижній Новгород, Самара, Саратов, Волгоград, Воронеж, Пенза, Липецьк, Тамбов, Орел, Курськ, Тула.
Кнопка «Очистити» знімає виділення з усіх міст і задає початкові значення ряду необхідних змінних.
Функція OnButton3 () пов'язана з кнопкою «Поставити пункт відправлення». Після натискання кнопки користувач може клацанням миші вибрати пункт відправлення комівояжера.
Кнопка «Параметри» викликає діалогове вікно «Параметри», де користувач може редагувати таблицю відстаней між містами.
Функція OnOK () обробляє натискання кнопки «Розрахувати шлях». Вона готує початкові значення для виклику рекурсивної функції: створюється таблиця відстаней тільки для виділених міст, заповнюється початковий мінімальний шлях, виводиться пояснюючий інформація. Потім викликається функція recursiv (), яка перебирає варіанти маршрутів, відсікає зайві гілки шляхів і знаходить мінімальний.
Клас CSetting.
Функція OnInitDialog () програмним шляхом створює і виводить поля введення, імітуючи таблицю відстаней між містами. Потім зчитується файл «table.ini», і заповнюються поля введення отриманими значеннями. Викликається функція Proverka (), яка сканує отримані дані на помилки, тобто визначає чи введені тільки цифри, і якщо ні, тоді видаляє всі зайві символи.
При натисканні кнопки «Зберегти» програма передає дані в батьківське вікно, записує дані з полів введення в файл і закриває діалогове вікно.
Тут користувач може вибрати кілька міст і розрахувати для них мінімальний шлях.
Щоб скасувати виділення міст потрібно клацнути по кнопці «Очистити». Натиснувши кнопку «Розрахувати шлях», ми отримаємо результат: міста з'єднані мінімальним шляхом, його довжина дана у вікні інформації, в списку показані відстані між містами, що входять в отриманий шлях (рис. 4).
Кнопка «Вибрати стандартні міста» виділяє міста, необхідні в завданні.
Щоб виділити пункт відправлення комівояжера потрібно вибрати «Поставити пункт відправлення».
Кнопка «Параметри» викликає діалогове вікно для введення відстаней між містами (мал. 5). Це вікно є модальним і його особливістю є те, що немає можливості переходу до батьківського вікна.
Тут користувач може відредагувати відстані між містами. Для цього потрібно клацнути в полі введення, і ввести інше значення. Переміщатися по цій «таблиці» можна по рядках за допомогою клавіш Tab або Shift + Tab.
По завершенні введення потрібно натиснути кнопку «Зберегти», щоб програма записала змінені дані у файл. При цьому автоматично перевіриться правильність введений інформації і всі помилки будуть виправлені.
Кнопка «Скасувати» дозволяє не зберігати введені зміни, якщо користувач помилився у введеної інформації.
За натисканні будь-якої з кнопок діалогове вікно «Параметри» закривається і ми повертаємося до головного вікна.
Якщо в рядку заголовка головного вікна клацнути правою кнопкою миші і вибрати пункт «Про програму», то з'явиться діалогове вікно, що містить відомості про програму та про автора (рис. 6). Натиснувши кнопку «OK» повертаємося до головного вікна.
Висновок
Був розроблений алгоритм, що дозволяє швидко знайти найкоротший шлях між містами. За алгоритмом розроблений додаток, вирішальне завдання про комівояжера.
2. Бєляєв С.П. Курс лекцій з «Дослідженню операцій».
Транспортна задача з правильним балансом полягає у тому, щоб знайти оптимальний план по заданій таблиці перевезень, при якому вартість перевезень буде мінімальна.
Таке завдання актуальна в областях пов'язаних з транспортуванням вантажів.
Саровський ДЕРЖАВНИЙФІЗИКО-ТЕХНІЧНИЙ ІНСТИТУТ | ||||||||||
ЕКОНОМІКО-МАТЕМАТИЧНИЙ ФАКУЛЬТЕТ | ||||||||||
КАФЕДРА МАТЕМАТИЧНИХ МЕТОДІВ ІДОСЛІДЖЕНЬ ОПЕРАЦІЙ В ЕКОНОМІЦІ | ||||||||||
ПОЯСНЮВАЛЬНА ЗАПИСКА | ||||||||||
До курсової роботи | ||||||||||
| на тему: | ||||||||||
| Рішення транспортної задачі з правильним балансом | ||||||||||
Студента | ||||||||||
| керівник роботи | ||||||||||
| консультанти роботи | ||||||||||
| Зав. кафедрою | ||||||||||
| м. Саров | ||||||||||
Зміст
Введення. 3
Постановка завдання. 4
Метод рішення. 5
Мова програмування. 7
Опис алгоритму. 8
Опис основних структур даних. 12
Опис інтерфейсу з користувачем. 14
Висновок. 16
Література. 17
Текст програми .. 18
Введення
Завдання полягає в тому, щоб інтуїтивно такий спосіб перевезення при якому витрати пов'язані з перевезенням були б мінімальні
Це завдання зацікавила мене тому, що її рішення напряму пов'язане з економією коштів. Важливо знаходження такого алгоритму, який дозволить найбільш оптимально вирішити задачу.
Постановка завдання
Транспортна задача ставиться так: є m пунктів відправлення А1, А2, ..., Аm, в яких зосереджені запаси якихось однорідних вантажів у кількості відповідно а1, а2, ... , Аm. Є n пунктів призначення В1, В2, ... , Вn подали заявки відповідно на b1, b2, ... , Bn вантажу. Відомі вартості Сi, j перевезення від кожного пункту відправлення Аі до кожного пункту призначення Вj. Всі числа Сi, j, що утворюють прямокутну таблицю задані. Потрібно скласти такий план перевезень (звідки, куди і скільки поставити), щоб усі заявки були виконані, а загальна вартість всіх перевезень була мінімальна.Метод рішення
1.Составленіе опорного плану.Рішення транспортної задачі починається із знаходження опорного плану. Для цього існують різні способи. Наприклад, спосіб "північно-західного кута" Розглянемо конкретний прикладі:
Умови транспортної задачі задані транспортної таблицею.
ПЗ | В1 | В2 | В3 | В4 | В5 | Запаси аi |
| А1 | 10 | 8 | 5 | 6 | 9 | 48 |
| А2 | 6 | 7 | 8 | 6 | 5 | 30 |
| А3 | 8 | 7 | 10 | 8 | 7 | 27 |
| А4 | 7 | 5 | 4 | 6 | 8 | 20 |
| Заявки bj | 18 | 27 | 42 | 12 | 26 | 125 |
ПЗ | В1 | В2 | В3 | В4 | В5 | Запаси аi |
| А1 | 10 18 | 8 27 | 5 3 | 6 | 9 | 48 |
| А2 | 6 | 7 | 8 30 | 6 | 5 | 30 |
| А3 | 8 | 7 | 10 9 | 8 12 | 7 6 | 27 |
| А4 | 7 | 5 | 4 | 6 | 8 20 | 20 |
| Заявки bj | 18 | 27 | 42 | 12 | 26 | 125 |
2.Распределітельний метод досягнення оптимального плану
Тепер спробуємо поліпшити план, складений способом "північно-західного кута". Перенесемо, наприклад, 18 одиниць з клітки (1,1) в клітину (2,1) і щоб не порушити балансу перенесемо ті ж 18 одиниць з клітки (2,3) в клітину (1,3). Отримаємо новий план. Підрахувавши вартість опорного плану (вона ровняется 1039) і вартість нового плану (вона ровняется 913) неважко переконатися що вартість нового плану на 126 одиниць менше. Таким чином за рахунок циклічної перестановки 18 одиниць вантажу з одних клітин в інші нам вдалося знизити вартість плану:
ПЗ | В1 | В2 | В3 | В4 | В5 | Запаси аi |
| А1 | 10 | 8 27 | 5 21 | 6 | 9 | 48 |
| А2 | 6 18 | 7 | 8 12 | 6 | 5 | 30 |
| А3 | 8 | 7 | 10 9 | 8 12 | 7 6 | 27 |
| А4 | 7 | 5 | 4 | 6 | 8 20 | 20 |
| Заявки bj | 18 | 27 | 42 | 12 | 26 | 125 |
Існує кілька варіантів циклу:
Неважко переконатися, що кожен цикл має парне число вершин і значить, парне число ланок (стрілок). Домовимося відзначати знаком "+" ті вершини циклу, в яких перевезення необхідно збільшити, а знаком "-" ті вершини, в яких перевезення необхідно зменшити. Цикл із зазначеними вершинами будемо називати "зазначеним". Перенести якусь кількість одиниць вантажу по зазначеному циклу - це значить збільшити перевезення, які стоять в позитивних вершинах циклу, на цю кількість одиниць, а перевезення, які стоять в негативних вершинах зменшити на ту ж кількість. Очевидно, при перенесенні будь-якого числа одиниць по циклу рівновагу між запасами та замовленнями не змінюється: як і раніше сума перевезень в кожному рядку дорівнює запасам цього рядка, а сума перевезень в кожному стовпці - заявці цього стовпця. Таким чином при будь-якому циклічному перенесення, який полишає перевезення невід'ємними допустимий план залишається допустимим. Вартість же плану при цьому може змінюватися: збільшуватися або зменшуватися. Назвемо ціною циклу збільшення вартості перевезень при переміщенні однієї одиниці вантажу по зазначеному циклу. Очевидно ціна циклу рівна алгебраїчній сумі вартостей, які стоять у вершинах циклу, причому стоять в позитивних вершинах беруться зі знаком "+", а в негативних зі знаком "-". Вершини чергуються починаючи з "+". Позначимо ціну циклу через g. При переміщенні однієї одиниці вантажу по циклу вартість перевезень збільшується на величину g. При переміщенні по ньому k одиниць вантажу вартість перевезень збільшитися на kg. Очевидно, для поліпшення плану має сенс переміщати перевезення тільки за тим циклам, ціна яких негативна. Кожного разу, коли нам вдається зробити таке переміщення вартість плану зменшується на відповідну величину kg. Так як перевезення не можуть бути негативними, ми будемо користуватися лише такими циклами, негативні вершини яких лежать в базисних клітинах таблиці, де стоять позитивні перевезення. Якщо циклів з негативною ціною в таблиці більше не залишилося, це означає, що подальше поліпшення плану неможливо, то є оптимальний план досягнутий.
Метод послідовного поліпшення плану перевезень і полягає в тому, що в таблиці відшукуються цикли з негативною ціною, за ним переміщуються перевезення, і план поліпшується до тих пір поки циклів з негативною ціною вже не залишиться. Можна довести, що для будь-якої вільної клітці транспортної таблиці завжди існує цикл і притому єдиний, одна з вершин якого лежить в цій вільній клітці, а всі інші в базисних клітинах. Якщо ціна такого циклу, з плюсом у вільній клітці, негативна, то план можна поліпшити переміщенням перевезень по даного циклу. Кількість одиниць вантажу k, яке можна перемістити, визначається мінімальним значенням перевезень, що стоять в негативних вершинах циклу (якщо перемістити більше число одиниць вантажу, виникнуть негативні перевезення).
Застосований вище метод відшукання оптимального рішення транспортної задачі називається розподіленим; він полягає у безпосередньому відшуканні вільних клітин з негативною ціною циклу і в переміщенні перевезень по цьому циклу.
Мова програмування
Для написання програми була обрана мова VBA з наступних причин:1. Visual Basic for Applications був написаний спеціально для Office додатків тобто потенційному замовникові досить встановить Office і запустити Ms Excel щоб програми працювала
2. Так як Транспортна задача заданна у вигляді таблиці то зручніше вирішувати її використовую можливості табличного редактора
3. Це одна з мов, в якому я непогано розбираюся. Тому мені зручніше писати програму з допомогою VBA.
Опис алгоритму
1.При запуску програми користувачеві пропонується ввести кількість запасів та запитівА) Виконується перевірка на правильність введення. Якщо введені числа то
Б) Вимальовується таблиця
2. Після промальовування таблиці користувачеві пропонується заповнити таблицю вартості перевезень
А) Після підтвердження заповнення користувачем станься перевірка на правильність введення
Б) Підсумовується рядок Запити і стовпець Запаси виконується перевірка на рівність. Якщо рівні то
3. Виконуємо побудова опорного плану методом Північно-західного кута
A) БУДУВАТИ нульову матрицю заданого розміру на "лісте2"
Б) Потім методом північно-західного кута виходячи з даних на аркуші "Дані"
В) Переносимо вийшла таблицю на аркуш "Цикли"
4.Іспользуем метод розподілу наступним чином
З наведеного прикладу вже можна виділити, як алгоритм перебирає шляху. Він діє за такою схемою:
0. Початкове значення j = 1 (перше місце в маршруті).
1. Ми знаходимося в місті k.
2. Для кожного міста (i = від 1 до n)
3. Розглядаємо місто i.
4. Якщо це місто ще не відвідано,
4.1. тоді переходимо до міста i; j збільшуємо на одиницю. Додаємо номер міста до маршруту на місце j. Позначаємо місто як відвіданий. Переходимо до пункту 1 (k = i).
4.2. інакше йти нікуди, тобто всі міста ми відвідали.
4.2.1. якщо j = кількості міст (n), тобто ми дісталися до останнього пункту в маршруті і наш шлях сформований,
тоді порівнюємо довжину шляху з довжиною мінімального маршруту.
4.2.2. Позначаємо місто як не відвіданий і виходимо з нього. Зменшуємо j на одиницю.
5. Беремо наступний місто (i = i +1).
Опис основних структур даних
Тепер розглянемо структуру програми, опишемо класи та процедури, які були змінені і наповнені кодом.
Програма складається з 4 класів:
1. CAboutDlg пов'язаний з вбудованим діалоговим вікном «Про програму».
2. CKurs_LipinApp управляє запуском програми, але не пов'язаний з яким-небудь діалоговим вікном. [1]
3. CKurs_LipinDlg пов'язаний з вікном IDD_KURS_LIPIN_DIALOG. Цей клас організовує постановку і рішення задачі.
4. CSetting пов'язаний з вікном IDD_DIALOG1. У вікні вводяться параметри до задачі - відстані між містами.
Клас CKurs_LipinDlg.
На початку при виклику функції OnInitDialog () змінні заповнюються початковими даними. Потім з файлу «table.ini» зчитується таблиця відстаней між містами. І тепер діалогове вікно готове до роботи з користувачем.
Функція OnPaint () виводить на екран карту, дозволяє виділяти міста, вибрані користувачем, а також з'єднує міста лініями-шляхами, коли задача вирішена. Крім того, забезпечується висновок інформації для користувача: пояснення, довжина мінімального шляху і список відстаней між містами, складові мінімальний шлях.
При натисненні лівої кнопкою миші викликається функція
OnLButtonDown (). Вона визначає за якого міста клацнув користувач і ставить / знімає виділення з нього. Також тут здійснюється перевірка на кількість виділених міст, тому що час очікування рішення задачі для кількості понад 13 міст стане не задовільним (від 1,5 хвилин і більше). Тому програма видасть повідомлення, якщо ми спробуємо вийти за допустимі межі.
Кнопка «Вибрати стандартні міста» виділяє міста, які потрібно з'єднати в умові завдання, а саме Москва, Ярославль, Нижній Новгород, Самара, Саратов, Волгоград, Воронеж, Пенза, Липецьк, Тамбов, Орел, Курськ, Тула.
Кнопка «Очистити» знімає виділення з усіх міст і задає початкові значення ряду необхідних змінних.
Функція OnButton3 () пов'язана з кнопкою «Поставити пункт відправлення». Після натискання кнопки користувач може клацанням миші вибрати пункт відправлення комівояжера.
Кнопка «Параметри» викликає діалогове вікно «Параметри», де користувач може редагувати таблицю відстаней між містами.
Функція OnOK () обробляє натискання кнопки «Розрахувати шлях». Вона готує початкові значення для виклику рекурсивної функції: створюється таблиця відстаней тільки для виділених міст, заповнюється початковий мінімальний шлях, виводиться пояснюючий інформація. Потім викликається функція recursiv (), яка перебирає варіанти маршрутів, відсікає зайві гілки шляхів і знаходить мінімальний.
Клас CSetting.
Функція OnInitDialog () програмним шляхом створює і виводить поля введення, імітуючи таблицю відстаней між містами. Потім зчитується файл «table.ini», і заповнюються поля введення отриманими значеннями. Викликається функція Proverka (), яка сканує отримані дані на помилки, тобто визначає чи введені тільки цифри, і якщо ні, тоді видаляє всі зайві символи.
При натисканні кнопки «Зберегти» програма передає дані в батьківське вікно, записує дані з полів введення в файл і закриває діалогове вікно.
Опис інтерфейсу з користувачем
При завантаженні програми з'являється основне діалогове вікно (рис. 3).Тут користувач може вибрати кілька міст і розрахувати для них мінімальний шлях.
Щоб скасувати виділення міст потрібно клацнути по кнопці «Очистити». Натиснувши кнопку «Розрахувати шлях», ми отримаємо результат: міста з'єднані мінімальним шляхом, його довжина дана у вікні інформації, в списку показані відстані між містами, що входять в отриманий шлях (рис. 4).
Кнопка «Вибрати стандартні міста» виділяє міста, необхідні в завданні.
Щоб виділити пункт відправлення комівояжера потрібно вибрати «Поставити пункт відправлення».
Кнопка «Параметри» викликає діалогове вікно для введення відстаней між містами (мал. 5). Це вікно є модальним і його особливістю є те, що немає можливості переходу до батьківського вікна.
Тут користувач може відредагувати відстані між містами. Для цього потрібно клацнути в полі введення, і ввести інше значення. Переміщатися по цій «таблиці» можна по рядках за допомогою клавіш Tab або Shift + Tab.
По завершенні введення потрібно натиснути кнопку «Зберегти», щоб програма записала змінені дані у файл. При цьому автоматично перевіриться правильність введений інформації і всі помилки будуть виправлені.
Кнопка «Скасувати» дозволяє не зберігати введені зміни, якщо користувач помилився у введеної інформації.
За натисканні будь-якої з кнопок діалогове вікно «Параметри» закривається і ми повертаємося до головного вікна.
Якщо в рядку заголовка головного вікна клацнути правою кнопкою миші і вибрати пункт «Про програму», то з'явиться діалогове вікно, що містить відомості про програму та про автора (рис. 6). Натиснувши кнопку «OK» повертаємося до головного вікна.
Висновок
Був розроблений алгоритм, що дозволяє швидко знайти найкоротший шлях між містами. За алгоритмом розроблений додаток, вирішальне завдання про комівояжера.
Література
1. Круглінскі Д., Програмування на Microsoft Visual C + + 6.0 для професіоналів / Пер.с англ. -СПб: Пітер; 2004р. - 861 с.: Іл.2. Бєляєв С.П. Курс лекцій з «Дослідженню операцій».