Содержание
- 2. Обґрунтування методу потенціалів Розв’язання транспортної задачі має суттєвий недолік: необхідно знаходити цикли для всіх вільних віконець
- 3. Уявимо, що кожен з пунктів відправлення Aі та призначення (прийому) Bj сплачують певні кошти у розмірі
- 4. Для заданої сукупності платежів (αi,βj), загальна псевдовартість перевезень не залежить від плану перевезень, а залежить лише
- 5. Як бачимо загальна псевдовартість перевезень не залежить від допустимого плану перевезень, тобто такого плану, що задовольняє
- 6. Якщо для всіх базисних віконець допустимого плану cij*=cij, а для всіх вільних віконець допустимого плану cij*≤
- 7. В результаті отримаємо вираз для обчислення загальної вартості перевезень при новому плані (xij*): Ніякими змінами плану
- 8. Припустимо, що m=n=3. Тоді кількість базисних віконець повинні дорівнювати m+n−1=5. Загальна вартість W при виконанні умов
- 9. Припустимо, що план змінено, обчислимо вартість зміненого плану: Доведена теорема виконується і для виродженого плану. Таким
- 10. План для якого виконуються властивості 1 та 2 носить назву потенціального, а платежі, що йому відповідають
- 11. Побудова потенціального плану Для розв’язання транспортної задачі необхідно побудувати потенціальний план. Цей план можливо побудувати за
- 12. Таблиця 1
- 13. В таблиці для прикладу заштриховано 10 базисних віконець. Обираємо будь-яке вільне віконце, наприклад, (1, 5) і
- 14. Методика розв’язання транспортної задачі методом потенціалів полягає в наступному: 1. Виконати перше наближення до оптимального плану,
- 15. 3. Обчислити псевдовартості для всіх вільних віконець. Якщо виявляється, що псевдовартості вільних віконець не перевищують вартості
- 16. Приклади розв’язання транспортної задачі методом потенціалів
- 17. Знайдемо методом північно-західного кута перше наближення до оптимального плану (див. Табл.). Кількість ненульових віконець дорівнює 8,
- 18. Не всі псевдовартості у вільних віконцях (табл. 3) задовольняють умові cij*≤cij. Тому, план, наведений у таблиці
- 19. Перенесемо по циклу Ц2 (див. табл. 3) 4 одиниці і занесемо результат у таблицю другої ітерації
- 20. Остаточно отримаємо таблицю третьої ітерації (табл. 5), яка за всіма ознаками надає оптимальний план перевезень (усі
- 21. Таким чином, фірма, яка володіє усіма складами A та всіма пунктами реалізації B, але не включає
- 22. Перевіримо: r=m+n−1=3+3−1=5>3 – транспортна задача вироджена. Скористаємось методом збурення запасів та заявок (див. табл. 6). Перерахунок
- 23. У виродженій транспортній задачі при виборі Ц1 або Ц2 із іншими вільними віконцями остаточний, тобто оптимальний,
- 25. Скачать презентацию