Розробка програми розв'язку транспортної задачі

Примітка: Вище подані схеми та таблиці були взяті з праці «Моделювання економічних та виробничих процесів»  Малохатько В.В., Азарової О.С.

Розділ ІІ

2. Побудова алгоритму роботи програми для вирішення ТЗ

2.1.  Стандартний алгоритм розв’язку транспортної задачі

Транспортна задача являє собою частинний випадок  розподільної задачі[3, 5, 8]. І для розв’язку подається у вигляді таблиці: з m пунктами відправлення А₁, A₂ , ..., А_m, в яких відповідно товар а₁, а₂, ... , а_m одиниць. Та n пунктів  призначення В₁ , A₂ , ... , A_n  з заявками відповідно на b₁ , b₂ , ... , b_n одиниць товару. Усі відомі N_i,j утворюють прямокутну таблицю. Потрібно скласти такий план перевезення при якому усі заявки виконанні із мінімальними затратами на перевезення.

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

Будь-яка задача транспортного типу потребує для  вирішення опорний план, у нас  це буде план складений методом Північно-Західного кута. Але такий план не являється оптимальним, тому його потрібно удосконалювати. Досягається це за рахунок циклічних перестановок, наприклад: ми бер емо з однієї клітинки n-одиниць товару, і щоб не порушити баланс переносимо її в іншу клітинку, при цьому план перевезення змінюється. Циклом називається декілька зайнятих клітинок, які з’єднанні ламаною лінією, яка в кожній клітинці здійснює поворот на  90°. Є декілька варіантів цикла:

1.)                        2.)                                 3.)

 

Кожен цикл має  парну кількість вершин. Ті вершини  циклу, в яких вантаж  потрібно збільшити  позначають «+», а де потрібно зменшити  «-». Такий метод удосконалення  плану використовується у програмі. Цей метод полягає в тому, що в таблиці знаходяться цикли з від’ємною ціною, по ним переміщяються перевезення поки циклів з від’ємною сумою не залишиться.

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

Для закритої задачі метод потенціалів зводиться  до слідуючого:

Беремо опорний  план, в якому виконується умова для кожної базисної клітинки:

a_i  + b_j  = с_i,j

Всього таких  рівнянь m + n – 1, тобто дорівнює числу базисів. Число невідомих m + n , що дає нам змогу задати одну з невідомих довільно. Далі  з

m + n – 1 рівнянь можна знайти останні  a_i  і  b_j ,  а по ним рахувати псевдорозрахунки  с*_i,j = a_i  + b_j  для кожної вільної клітинки.  Якщо виявилось, що

с*_i,j

с_i,j

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

Продовжується поки усі рівняння будуть виконуватися.

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

 

 

 

 

 

2.2. Алгоритм роботи головної програми

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

         1                                       2                                                 3

 

 

 

 

 

 

                             E                                                               Q

 

 

 

 

 

 

                       Словесний опис:

1. Вибрати дію;
2. Якщо вибираємо розв’язок ТЗ, переходимо до розв’язку ТЗ;
3. Якщо обрано «справка», відкриваємо текст справки;
4. Якщо обрано «вихід», обираємо вийти чи повернутися до меню вибору.
5. Кінець

Програма має  класичний модульний характер написання,тому вище наведено блок-схему головного алгоритму.(Лістинг програми Додаток А)

2.3. Допоміжні алгоритми

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

Перша з них  це власне процедура розв’язку Транспортної Задачі. Вона має назву TZ.

Алгоритм процедури  TZ.

Словесний опис алгоритму TZ:

1. Вводимо початкові дані (Кількість покупців, замовників, кількість товару та вартість перевезення одиниці товару);
2. Перевіряємо задачу на відкритість: якщо відкрита вводимо фіктивних покупців (продавців), шоб звести задачу до закритої.
3. Обраховуємо опорний план методом Північно-Західного кута.
4. Провіряємо план на оптимальність: якщо неоптимальний методом потенціалів та циклічних перестановок зводимо до оптимального;
5. Кінець

Блок-схема TZ(додаток В)

 

Алгоритм процедури  SPRAVKA

Словесний опис

1. Присвоюємо змінну текстовому файлу;
2. Відкриваємо файл для читання;
3. Поки не кінець файлу виводимо текст;
4. Щоб перейти на наступну сторінку натисніть – 1;
5. Переходимо до слідуючої сторінки
6. Щоб перейти на наступну сторінку натисніть – 1, для повернення на попередню натисніть -2;
7. Кінець

Блок-схема SPRAVKA(Додаток Г)

         Розділ ІІІ

3. Програмна реаізація алгоритму

3.1 Обгрунтування вибіру мови

Для написання  програми було обрано мову Паскаля. Мова PASCAL є універсальною мовою програмування  високого рівня. Створення професором Віртом мови PASCAL у 1971 році мало своєю метою полегшити процес навчання систематичному підходу до програмування для ЕОМ, точніше сказати, структурному програмуванню. Відтоді мова PASCAL використовується для програмування майже всіх типів задач на майже всіх типах ЕОМ і довгий час вважалася однією з кращих мов програмування високого рівня, незалежно від того, для яких цілей він використовується: для навчання або для програмування як аматорами так і професіоналами. З 90-х років ця мова стала фундаментальною у вищих навчальних закладах, і досі такою є. Мова «Pascal» стала фундаментом для послідуючих розробок, зокрема «делфі».

Сам Borland Pascal має зручне середовище розробки, включає функціональний відладчик, доступний в кожний момент. Має довідкову систему, по якій можна вивчати мову самостійно, та високошвидкісний компілятор, що полегшую роботу програміста. Одним з його недостатків є неповна функціональність у нових середовищах Windows 7, що складає певні незручності у роботі. Але прогрес не стоїть на місці і вже в розробці версії повністю сумісні з новими системами.

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

   Мова «C» є мовою системного, машинного програмування низького рівня. «Delphi» більш зорієнтована на об’єктне програмування, та розробку інтерфейсів, і програми є досить громіздкими та мають певні обмеження для характеристики ЕВМ.

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

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

2. Опис роботи програми

Програма написана на мові Борланд Pascal СкулПак 2010 у класичному стилі. Для запуску програми необхідні такі складові:

• TR_ZAD2.exе – файл що запускає програму у Windows;
• TZ1.tpu – модуль користувача;
• Text.txt – текст справки;
• Text1.txt – текст справки;
• Text2.txt – текст справки;
• Text3.txt – текст справки;
• Fp__.err – файл для запуску програми з Free Pascal;
• Fp__.out – файл , конфігураці виходу Free Pascal.

Після запуску ЕХЕ – файлу з’являється вікно програми з пропозицією вибрати подальшу дію. Це вікно є головною програмою, яка здійснює перехід до підпрогам(Рис 23).

Рисунок 23. – головна програма

3.3 Допоміжні процедури та функції

Розроблена  програма побудована у класичному процедурному стилі. Всі процедури та функції користувача містяться у модулі користувача TZ1. Цей модуль має 14 процедур та 3 функції. Тільки 4 функції доступні для користувача (Додаток Б). Далі наведено перелік процедур та функцій даного модуля з коротким описом їх призначення. Підкреслені процеду – доступні для користувача.

Опис  процедур та функцій користувача:

Procedure Nul – процедура обнуляє масив;

Procedure PrintS (x,y:byte; s:string; c:byte) – процедура виводить текст з заданої позиції, заданим кольором;

x,y – координати поля виводу, s – текст повыдомлення, с –колір;

Procedure Print (x,y:byte; n:byte; a:longint; c:byte) – виводить число а заданим кольором з заданої позиції;

x,y – координат поля виводу, n – кількість чисел; а – число; с –колір;

Procedure Rid (var x:longint; y:byte) – вводить число Х;

Х – число, яке вводиться; у – кількість чисел;

Procedure Goriz, wertic, Tabl  - Креслять  таблицю, при чому

Goriz (a,b,c,d,e:char) – горизонтальні лінії,

a,b,c,d,e – символи виводу таблиці;

Wertic – вертикальні лінії,

Tabl – з’єднання та поєднання двох попередніх, та заповнення таблиці: її назва, назви стовпців і т.д.

Procedure W_W (var a:predpr; b:byte; c:char)– вводить в таблицю кількість пропозиції, попиту;

a – масив для запису кількості продукції, покупців та продавців; b – кількість комірок; с – назва стовбця, рядка;

Procedure W_p – виводить план розподілення;

Procedure div_mod (c:byte; var a,b:byte) – переводить одновимірний масив у двовимірний;

С – змінна переводу; a,b – числа масиву;

Procedure Rek (Xi,Yi:byte; var z:boolean; var c:byte) – Визначає контур переміщення(рекурсивна процедура);

Xi,Yi – координати комірок; z –логічна змінна; с – число (1, 2), яке задає для рядка чи для стовпчика виконується дія;

Procedure kontur – визначає контур переміщення;

Procedure Pauza – затримка програми, поки не натиснуто клавішу;

Function FF :longint– обчислення загальної вартості плану перевезення;

Function a_b: boolean – розрахунок потенціалів alfa і betta;

Function kkk (var ki,kj:byte):integer– розрахунок коефіцієнтів у вільних клітинках;

ki,kj – вартість вільних клітинок;

Procedure TZ – процедура обрахунку транспортної задачі;

Procedure SPRAVKA – робота зі справкою.

 

3.4 Інструкція користувача, аналіз роботи програми

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

Після вибору користувачем у головному меню пункту 1, переходимо до обрахунку транспортної задачі, точніше до введення початкових даних (Рисунок Д1. – Введенняя даних)

А1,А2 – Постачальники;

В1,В2,В3 – Покупці;

2,3 – кількість  продукції наявної у продавців (пропозиції);

5,2,2 – кількість  продукції, яку хочуть закупити (попит);

4,4 – вартість перевезення одиниці товару.