Розробка автоматизованого робочого місця управління замовленнями у малому бізнесі (ПП "Сігма") (стр. 7 из 13)
Після встановлення об'єму перевезень по маршруту, визначеному в пункті 1, ми маємо справу з новою задачею, в якій сумарне число виробникїв і споживачів на 1 менше, ніж в вихідній задачі. Далі процес повторюється при можливо більшому значенні тієї змінної, якій відповідає мінімальна вартість серед невикреслених (це значення може опинитися і нульовим). Процедура завершується, коли залишається один рядок і один стовпець.
Цей метод є евристичним і зазвичай приводить до кращого початкового рішення, ніж два описаних вище. Насправді цей метод часто дає оптимальне або близьке до оптимального початкове рішення.
Схема алгоритму така. Обчислити штраф для кожного рядка (стовпця), віднімаючи найменший елемент цього рядка (стовпця) з наступного за ним по величині елементу того ж рядка (стовпця). Відзначити рядок або стовпець з найбільшим штрафом, а якщо таких декілька - вибрати серед них будь-який рядок або будь-який стовпець. У відміченому рядку або стовпці вибрати змінну з найнижчою вартістю і надати їй найбільше можливе значення. Скоректувати об'єм виробництва і попит і викреслити рядок або стовпець, відповідні виконаному обмеженню. Якщо обмеження по рядку і стовпцю виконуються одночасно, то викреслити або рядок, або стовпець, а стовпці (рядку), що залишився, приписати нульовий попит (об'єм виробництва). Рядок (або стовпець) з нульовим об'ємом виробництва (або попитом) не використовується в подальших обчисленнях. Якщо невикресленим залишається в точності один рядок або один стовпець, то закінчити обчислення. Якщо залишається невикресленою тільки один рядок (стовпець) із позитивним об'ємом виробництва (попитом), знайти базисні змінні в цьому рядку (стовпцю), використовуючи метод найменшої вартості. Якщо всім невикресленим рядкам і стовпцям відповідають нульові об'єми виробництва і величини попиту, знайти нульові базисні змінні, використовуючи метод найменшої вартості. В інших випадках обчислити нові значення штрафів для невикреслених рядків і стовпців і перейти до пункту 2. (Слід зазначити, що рядки і стовпці з нульовими значеннями об'єму виробництва і попиту не повинні використовуватися при обчисленні цих штрафів.)
1.4.3.5 Приклад рішення задачі
Для ілюстрації рішень транспортних задач, розглянемо приклад рішення цих задач із застосуванням методу потенціалів із способом знаходження початкового ДБР методом найменшої вартості.
Транспортна задача представлена у вигляді таблиці:
Таблица 1.9 – Умови транспортної задачі
| 2 | 5 | 3 | 0 | |||||
| 10 | ||||||||
| 3 | 4 | 1 | 4 | |||||
| 20 | ||||||||
| 2 | 6 | 5 | 2 | |||||
| 20 | ||||||||
| 5 | 25 | 10 | 10 | |||||
Розв'язування:
1. Виберемо змінну, якій відповідає мінімальна вартість. Такою є змінна Х14 (C14=0). Відповідні значення попиту і об'єму виробництва визначають Х14=10, тобто і по рядку, і по стовпцю обмеження виконуються одночасно. Викреслювати можна або рядок 1 або стовпець 4, викреслимо рядок 1. Після цього об'єм виробництва в стовпці 4 залишається рівним нулю.
| 10 | 10 | ¾ | |||
| 20 | |||||
| 20 | |||||
| 5 | 25 | 10 | 10 | ||
| 0 |
2. Тепер серед елементів, що залишилися, мінімальна вартість відповідає X23. Отримуємо X23=10. Викреслюємо 3-й стовпець.
| 10 | 10 | ¾ | |||
| 10 | 20 | 10 | |||
| 20 | |||||
| 5 | 25 | 10 | 10 | ||
| ¾ | 0 |
3. Далі найменша вартість відповідає X31 і X34. Виберемо X34. І отримаємо X34=0. Викреслюємо 4-й стовпець.
| 10 | 10 | ¾ | |||
| 10 | 20 | 10 | |||
| 0 | 20 | 20 | |||
| 5 | 25 | 10 | 10 | ||
| ¾ | 0 | ||||
| ¾ |
4. Серед змінних, що залишилися, найменша вартість відповідає X31. Викреслюємо 1-й стовпець.
| 10 | 10 | ¾ | ||||
| 10 | 20 | 10 | ||||
| 5 | 0 | 20 | 20 | 15 | ||
| 5 | 25 | 10 | 10 | |||
| ¾ | ¾ | 0 | ||||
| ¾ |
5. Далі викреслюємо 2-й рядок, оскільки найменша вартість відповідає X22.
| 10 | 10 | ¾ | ||||
| 10 | 10 | 20 | 10 | ¾ | ||
| 5 | 0 | 20 | 20 | 15 | ||
| 5 | 25 | 10 | 10 | |||
| ¾ | 15 | ¾ | 0 | |||
| ¾ |
6. X32=15. Оскільки залишається тільки один стовпець і лише один рядок, процес закінчується.
| 10 | 10 | ¾ | |||||
| 10 | 10 | 20 | 10 | ¾ | |||
| 5 | 15 | 0 | 20 | 20 | 15 | 0 | |
| +5 | 25 | 10 | 10 | ||||
| ¾ | 15 | ¾ | 0 | ||||
| ¾ | ¾ |
В результаті отримано наступне базисне рішення:
| 10 | 10 | |||
| 10 | 10 | 20 | ||
| 5 | 15 | 0 | 20 | |
| 5 | 25 | 10 | 10 |
Базисні змінні приймають значення: X14=10, X22=10, X23=10, X31=5, X32=15, X34=0. Решта змінних – небазисні. Сумарні транспортні витрати, відповідні цьому рішенню, рівні 10 * 0 + 10 * 4 + 10 * 1 + 5 * 2 + 15 * 6 + 0 * 2 = 150 од. вартості. Якщо вирішити задачу з використанням методу північно-західного кута, то можна побачити, що отриманий результат цим методом гірше за результат, отриманий при рішенні задачі з використанням методу найменшої вартості в розглянутому прикладі.
1.5 Опис програмного забезпечення
1.5.1 Вибір інструментів розробки
У даному проекті ми використовуватимемо середовище розробки Borland Delphi 7. Ця мова програмування на сьгодняшній час вже декілька застаріла, але для програмування застосувань, що працюють з MS Access вона дуже зручна. Borland Delphi 7 – розвинена об'єктно-орієнтована мова, що дозволяє розробляти скільки завгодно складні і, в той же час, ефективно працюючі системи. До того ж у розробника найбільший досвід програмування саме на цих "старих" мовах програмування.
1.5.1 Форми та модулі програми
Структура розроблюємого програмного забезпечення наведена на рис. 1.7.
Програмна частина дипломного проекту складається з 7-и форм, 1 модуль коду і 3-и модулів класу. Форми використовуються для введення даних користувачем. Модулі коду містять глобальні типи і змінні проекту, а також загальні процедури і функції. У модулях класів реалізовані програмні об'єкти, які використовуються при обробці подій форм.
Рисунок 1.7 – Структура Delphi-проекта
1.5.2 Опис модулів і класів системи
Модули форм містять процедури обробки таких подій:
– Form_Load – завантаження форми;
– Form_Resize – зміна розмірів форми;
– Form_Unload – вивантаження форми;
– Form_KeyPress – обробка клавіатури на полях редагування;
– Form_KeyDown - обробка клавіатури на полях редагування;
– sst_Click – обработка щиглика миші на вкладках;
– lvwGroup_GotFocus – фокус на переліку;
– lvwGroup_LostFocus – перелік втратив фокус;
– lvwGroup_ItemClick – щиглика миші на переліку;
– lvwGroup_KeyDown – клавіатура на переліку;
– txtGroup_GotFocus – поле редагування отримує фокус;
– txtGroup_LostFocus– поле редагування втрачає фокус;
– txtGroup_KeyDown– клавіатура на поле редагування.
При обробці ціх подій викликаються відповідні методи класів.
Модулі коду містять наступні глобальні процедури і функції:
– MsgErr() – повідомлення про помилку;
– CenterForm(frm) – центрирвання форми;
– SetColumnsWidth(lvw) – установка ширини стовпчиків переліку;
– CheckNullDate(vDate) sFormat – перевірка дати;
– IdToKey(nId) sKey – перведення числового ключа таблиці БД у текстовий ключ колекції;
– KeyToId(sKey) nId – зворотне переведення;
– NotChanged(vCurr(), vPrev()) bNotChange – перевірка змін у запису БД;
– EmptyFields(txt()) bEmpty – перевірка пустого текстового поля;