Транспортная задача линейного программирования

1. Транспортная задача линейного программирования

2. Постановка транспортной задачи

3. Математическая модель ТЗ

4. ТЗ – ЗЛП специального типа

5. Терминология в ТЗ

План перевозок
Допустимый план перевозок
Опорный план перевозок
Оптимальный план перевозок
Вырожденный план перевозок

6. Вид транспортных таблиц

7. Алгоритм решения ТЗ

• 1. Определение начального допустимого
базисного решения (опорный план)
• 2. В соответствии с условиями оптимальности
определение переменной, вводимой в базис
• 3. Определение переменной, исключаемой из
базиса
• 4. Определение нового базисного решения
(опорного плана)

8. Методы решения ТЗ

• 1. Методы определения начального
базисного решения (метод «северозападного угла», метод «минимальных
стоимостей перевозок», метод
наименьшей стоимости, метод Фогеля)
• 2. Методы улучшения базисного
решения (метод потенциалов,
распределительный метод)

9. Метод потенциалов

10. Метод потенциалов (продолжение)

11. Варианты системы потенциалов

12. Вырождение на этапе оптимизации

13. Несбалансированная ТЗ

14. Транспортная задача в сетевой постановке

15. Построение опорного плана

16. Метод потенциалов – проверка плана на оптимальность

17. Метод потенциалов – проверка плана на оптимальность

18. Особые случаи ТЗ в сетевом виде

19. ТЗ с промежуточными пунктами

• Способ решения
задачи о нахождении
наикратчайшего
расстояния на сети
связи между двумя
пунктами
• Сведение в ТЗ в
матричной форме
введением буфера

20. Пример ТЗ с промежуточными пунктами

21. ТЗ с промежуточными пунктами

22. Оптимальное решение в ТЗ с ПП (Z=20700)

23. Поиск наикратчайшего пути на сети связи между двумя пунктами методом решения ТЗ с ПП

24. Поиск наикратчайшего пути на сети связи между двумя пунктами методом решения ТЗ с ПП (оптимум)

25. Задача о назначениях – частный случай ТЗ

26. Алгоритм венгерского метода

27. Пример решения задачи о назначениях

28. Особые случаи решения задачи о назначениях