Опорний конспект лекцій з курсу Дослідження операцій Тема 6 Транспортні задачі лінійного програмування, НУДПСУ
« НазадЛекція №6. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
План 1. Транспортна задача. Загальні особливості транспортних задач. 2. Задачі, що відносяться до транспортних: прикріплення споживачів ресурсу до виробників; прив'язка пунктів відправлення до пунктів призначення; взаємна прив'язка вантажопотоків прямого і зворотного напрямів; окремі задачі оптимального завантаження промислового устаткування; оптимальний розподіл об'ємів випуску промислової продукції між заводами-виготівниками. 3. Таблиця транспортної задачі. 4. Закриті та відкриті транспортні задачі. 5. Опорний план.
3. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯТранспортна задача є представником класу задач лінійного програмування і тому володіє всіма якостями лінійних оптимізаційних задач, але одночасно вона має і ряд додаткових корисних властивостей, які дозволили розробити спеціальні методи її розв'язку. Транспортна задача є одним з найбільш поширених спеціальних задач лінійного програмування. Окремі постановки задач розглянуті рядом фахівців з транспорту. Перша строга постановка транспортної задачі (Т-задачі) належить Ф.Хичкоку, тому в зарубіжній літературі її називають проблемою Хичкока. Перший точний метод рішення Т-задачі розроблено Л.В.Канторовичем і М.Д.Гавуріним. Під назвою «транспортна задача» об'єднується широкий круг задач з єдиною математичною моделлю. Дані задачі відносяться до задач лінійного програмування і можуть бути розв'язані симплекс-методом. Проте матриця системи обмежень транспортної задачі настільки своєрідна, що для її вирішення розроблені спеціальні методи. Ці методи, як і симплекс-метод, дозволяють знайти початкове опорний розв'язок, а потім, покращуючи його, отримати і оптимальний розв'язок. 3.1. Постановка задачі Під терміном «транспортні задачі» розуміється широкий круг задач не тільки транспортного характеру. Загальним для них є, як правило, розподіл ресурсів, що знаходяться у m виробників (постачальників), по n споживачах цих ресурсів. Розрізняють два типи транспортних задач: за критерієм вартості (план перевезень оптимальний, якщо досягнуто мінімум витрат на його реалізацію) і за критерієм часу (план оптимальний, якщо на його реалізацію витрачається мінімум часу). Найчастіше зустрічаються наступні задачі, що відносяться до транспортних:
Розглянемо економіко-математичну модель прикріплення пунктів відправлення до пунктів призначення. Є m пунктів відправлення вантажу і об'єми відправлення по кожному пункту a1, a2,...,am. Відома потреба у вантажах b1, b2,...,bn по кожному з n пунктів призначення. Задана матриця вартостей доставки по кожному варіанту cij, i = 1,…,m, j = 1,…,n. Необхідно розрахувати оптимальний план перевезень, тобто визначити, скільки вантажу повинно бути відправлено з кожного i-го пункту відправлення (від постачальника) в кожен j-й пункт призначення (до споживача) xij з мінімальними транспортними витратами. У загальному вигляді початкові дані представлені в табл. 3.1. Рядки транспортної таблиці відповідають пунктам відправлення (у останній клітці кожного рядка вказаний об'єм запасу продукту ai), а стовпці – пунктам призначення (остання клітка кожного стовпця містить значення потреби bj). Всі клітки таблиці (окрім тих, які розташовані в нижньому рядку і правому стовпці) містять інформацію про перевезення з i-го пункту в j-й: у правому верхньому кутку знаходиться ціна перевезення одиниці продукту, а в лівому нижньому – значення об'єму вантажу, що перевозиться, для даних пунктів. Таблиця 3.1. Початкові дані
Транспортна задача називається закритою, якщо сумарний об'єм вантажів, що відправляються, дорівнює сумарному об'єму потреби в цих вантажах за пунктами призначення. Якщо такої рівності немає (потреби вище за запаси або навпаки), задачу називають відкритою, тобто. Для створення моделі необхідно всі умови (обмеження) і цільову функцію представити у вигляді математичних рівнянь. Всі вантажі з i-х пунктів повинні бути відправлені, тобто. Всі j-і пункти (споживачі) повинні бути забезпечені вантажами в плановому об'ємі. Сумарні об'єми відправлення повинні дорівнювати сумарним об'ємам призначення (3.1). Повинна виконуватися також умова позитивності змінних хij ³ 0, i = 1,…,m, j = 1,…,n. Перевезення необхідно здійснити з мінімальними транспортними витратами (функція цілі). Замість матриці вартостей перевезень (cij) можуть задаватися матриці відстаней. У такому разі як цільова функція розглядається мінімум сумарної транспортної роботи. Як видно з виразу (3.1), рівняння балансу є обов'язковою умовою рішення транспортної задачі. Тому, коли в початкових умовах дана відкрита задача, то її необхідно привести до закритої форми. У випадку, якщо
Варіанти, що пов'язують фіктивні пункти з реальними, мають нульові оцінки. Після введення фіктивних пунктів задача вирішується як закрита. Транспортним задачам властиві наступні особливості:
Транспортні задачі можуть вирішуватися і симплекс-методом. Проте перераховані особливості дозволяють для транспортних задач застосовувати простіші методи розв'язку. Опорний план є допустимим розв'язком транспортної задачі і використовується як початковий базисний розв'язок при знаходженні оптимального розв'язку методом потенціалів. Існує три методи знаходження опорних планів: метод північно-західного кута, метод мінімального елементу і метод Фогеля. «Якість» опорних планів, отриманих цими методами, розрізняється: у загальному випадку метод Фогеля дає якнайкращий розв'язок (часто оптимальний), а метод північно-західного кута найгірший. Всі існуючі методи знаходження опорних планів відрізняються тільки способом вибору клітки для заповнення. Саме заповнення відбувається однаково незалежно від використовуваного методу. Контрольні запитання 1. Що таке транспортна задача? 2. Наведіть загальні особливості транспортних задач. 3. Сформулюйте задачу прикріплення споживачів ресурсу до виробників. 4. Сформулюйте задачу прив'язки пунктів відправлення до пунктів призначення. 5. Сформулюйте задачу взаємної прив'язки вантажопотоків прямого і зворотного напрямів. 6. Сформулюйте задачу оптимального завантаження промислового устаткування. 7. Сформулюйте задачу оптимального розподілу об'ємів випуску промислової продукції між заводами-виготівниками. 8. Що таке таблиця транспортної задачі? 9. Що таке закриті та відкриті транспортні задачі? 10. Що таке опорний план? З повагою ІЦ “KURSOVIKS”! |