Властивості та типи транспортних задач
Значний клас задач оптимізації, який належить до задачлінійного програмування, включає так звану розподільну задачу. До неї належать транспортна задача, задача про призначення і розміщення та ін. Найпоширенішою задачею цього класу є розподільна задача транспортного типу, яка розглядає питання оптимального планування перевезень вантажу, тобто знаходження оптимальних схем вантажопотоків, з’ясування питання оптимальних постачань дефіцитної продукції, закріплення пунктів постачання за споживачами ресурсів та ін. Зміст та загальний вигляд математичної моделі відомі з п.1.3.2.: Такі задачі можна розв’язувати симплекс-методом, але через їх специфіку для них розроблені спеціальні методи розв’язання, які простіші у користуванні. Методи розв’язування задач транспортного типу умовно можна поділити на дві групи: – методи послідовного поліпшення опорного плану (розподільний метод, метод потенціалів та його модифікації); – методи послідовного скорочення нев’язок (метод диференціальних рент, угорський метод, метод розв’язувальних елементів); Найефективнішим і найпростішим у застосуванні є метод потенціалів – спрощений варіант модифікованого симплекс-методу. Властивості транспортної задачі: – задача завжди має оптимальний розв’язок; – якщо значення – обмеження задачі задаються тільки у вигляді строгих рівнянь; – коефіцієнти змінних в обмеженнях завжди дорівнюють +1; – кожна змінна зустрічається двічі в обмеженнях задачі; – кожна змінна має подвійну індексацію.
При розв’язуванні задачі припускається виконання таких умов:
– об’єм постачання ресурсів повинен дорівнювати об’єму споживання цих ресурсів; – ресурси постачання мають бути повністю вивезені; – попит споживачів на ці ресурси має бути повністю задоволений; – витрати на транспортування ресурсів мають бути пропорційними їх обсягам перевезень. Величини Транспортні задачі поділяють на наступні типи: – збалансована транспортна задача, коли загальна можливість пунктів постачання дорівнює загальній можливості пунктів споживання, тобто таку задачу називають закритою; – не збалансована транспортна задача, коли у цьому разі обмеження мають вигляд
та вказують на зайві ресурси або на підвищений попит їх у споживачів. Таку задачу називають відкритою. Методи розв’язання транспортної задачі розроблене тільки для закритих задач. Отже, треба всі відкриті задачі звести до закритої. Для цього математичну модель відкритої задачі доповнюють фіктивним пунктом, тобто фіктивним споживачем з попитом
або фіктивним пунктом постачання із запасом
До цільової функції у цих випадках вводять коефіцієнти
Читайте также: I Приклади розв’язання задач Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|