Дисципліни:
Лабораторна робота №3
На тему:

Особливості розв’язку транспортної задачі.

Дисципліна: Методи синтезу та оптимізації
ВНЗ:НУ «ЛП»
Формат: Word Doc

Переглядів: 1501 Додано: 2015-04-14




Частина тексту

МЕТА РОБОТИ

Ознайомитися з особливостями розв’язування транспортної задачі.

КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ

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

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

Постановка транспортної задачі

Отже, як було зазначено вище, при постановці транспортної задачі необхідно побудувати найбільш економічний план перевозок одного виду продукції з декількох пунктів  (кількість яких позначимо через I, а кількість продукції, яка виробляється в кожному пункті - ) в пункти призначення (кількість яких позначимо через J, а кількість продукції, яку необхідно обов’язково підвести до кожного пункта - ), вартість перевезення однієї одиниці продукції з пункта i в пункт j позначимо через , а через  - позначимо кількість продукції, яку необхідно перевести з пункта i в пункт призначення j. Тепер усі вхідні дані є і сформулюємо транспортну задачу в загальному випадку.

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

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

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

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

Отже, перший крок алгоритму передбачає визначення початкового допустимого рішення з визначенням значення цільової функції. Кількість базисних змінних визначається як I+J-1. При наявності побудованої транспортної таблиці для задач даного типу досить зручно використати один зі спеціальних методів по визначенню початкового базисного рішення, зокрема: правило північно-західного кута, метод мінімальної вартості чи наближений метод Фогеля, які детально будуть розглянути нижче.

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

Метод потенціалів

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

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

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

Алгоритм побудови замкнутого циклу

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

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

Крок 2. Поставити плюси та мінуси чергуючи між собою біля базисних змінних, які розміщені на згинах циклу.  Біля змінної, що вводиться в список базисних необхідно поставити плюс. Це випливає з того, що якщо до змінної, що вводиться додати одиницю, то для виконання умови допустимості рішення базисних змінних, які розміщені на згинах необхідно зменшити на одиницю і так далі (Див. Табл.2.15) чергуючи плюс і мінус біля базисних змінних побудованого цикла. В даному випадку, біля змінної X22 ставимо плюс, X32 – мінус, X32 – плюс, X12 ставимо мінус.

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

Крок 4. Величину змінної, яка виводиться зі списку базисних необхідно відняти від величин базисних змінних, де розміщений мінус і додати до величин базисних змінних, де розміщено плюс (Див. Табл.2.16). 

Крок 5. Вирахувати значення цільової функції для нового списку базисних змінних (Ц.Ф.=300*350+400*200+700*550=570000).

Висновок: На даній лабораторній роботі я ознайомилась з особливостями розв’язування транспортної задачі.