Содержание
- 2. Транспортная задача является частным случаем задачи линейного программирования и может быть решена симплекс-методом. Однако, в силу
- 3. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов
- 4. Рассмотрим транспортную задачу, в которой в качестве критерия оптимальности берется минимальная стоимость перевозок всего груза. Обозначим
- 5. Математическая модель транспортной задачи Найти при ограничениях
- 6. Первое ограничение означает, что все потребности должны быть удовлетворены , а второе - , что все
- 7. Определение. Всякое неотрицательное решение системы ограничений транспортной задачи, определяемое матрицей размера m×n , называют допустимым решением
- 8. Определение. План , при котором целевая функция принимает минимальное значение, называется оптимальным.
- 9. Тарифы или стоимости перевозок единицы груза также задаются матрицей, которая называется матрицей транспортных издержек или матрицей
- 10. Транспортная таблица
- 11. Необходимое и достаточное условие разрешимости транспортной задачи Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы
- 12. При выполнении этого условия модель транспортной задачи называется закрытой. Если балансовое условие не выполняется, то есть
- 13. В случае открытой транспортной задачи выполнение балансового условия достигается введением фиктивного поставщика или фиктивного потребителя с
- 14. Любое решение транспортной задачи представляет собой распределение перевозок в транспортной таблице. Оптимальному решению транспортной задачи соответствует
- 15. Пример
- 16. Все грузы должны быть перевезены, поэтому Это три первых уравнения. Все потребности должны быть удовлетворены и,
- 17. А целевую функцию составили по матрице С - матрице тарифов перевозок.
- 18. Пример. Задача организации оптимального снабжения . Три фермерских хозяйства ежедневно могут доставлять в город соответственно 60,
- 19. Таблица
- 20. Экономико-математическая модель задачи. Переменные : - количество молока , поставляемое i-м фермерским хозяйством в j-ю торговую
- 21. Эта задача является задачей открытого типа, так как запасы молока у фермерских хозяйств (поставщиков) больше потребностей
- 22. Функциональные ограничения: По поставщикам (их 3) по потребителям (их 5)
- 23. Этапы решения транспортной задачи Составляют математическую модель задачи. Находят исходное опорное решение. Проверяют это решение на
- 24. Будем называть переменные , стоящие в занятых клетках распределительной или транспортной таблицы, базисными, а переменные находящиеся
- 25. Определение исходного допустимого решения 1. Метод «северо-западного угла» Метод заключается в том, что заполнение клеток таблицы
- 26. 2. Метод «наименьшей стоимости» Метод заключается в том, что заполнение клеток таблицы начинают с клетки, имеющей
- 27. Найти опорный план транспортной задачи методом наименьшей стоимости
- 28. Минимальный тариф, равный 1 , находится в клетке . Положим . Запишем это значение в соответствующую
- 29. В оставшейся части таблицы с двумя строками и и c четырьмя столбцами клетка с наименьшим тарифом
- 30. Временно исключим из рассмотрения столбец и будем считать запасы пункта равными 120 ед. После этого рассмотрим
- 31. Заполним описанным выше способом эту клетку и аналогично заполним ( в определенном порядке) клетки, находящиеся на
- 32. В результате получим опорный план При данном плане перевозок общая стоимость перевозок составляет .
- 33. Условие невырожденности плана Если число заполненных клеток равно m + n – 1, то план является
- 34. В нашей задаче число заполненных клеток равно m + n – 1=3 + 4 – 1
- 35. Метод потенциалов проверки решения на оптимальность Предположим, что каждый пункт отправления Ai вносит за перевозку единицы
- 36. Совокупность уравнений , составленных для всех базисных переменных, представляет совместную систему линейных уравнений, причем одну из
- 37. Обозначим через , где назовем псевдостоимостями или косвенными стоимостями (тарифами). Псевдостоимости находятся для всех свободных клеток.
- 38. Теорема «о платежах». Для заданной совокупности платежей и суммарная косвенная стоимость перевозок при любом допустимом плане
- 39. Теорема оптимальности. Если для всех базисных клеток а для всех свободных клеток , то допустимый план
- 40. Пример Найти опорное решение методом минимальной стоимости и проверить оптимальность решения методом потенциалов.
- 43. Находим потенциалы базисных клеток
- 44. Положим и решим систему. Получим Найдем псевдостоимости пустых клеток План перевозок оптимален
- 45. Пример 2. На складах имеются запасы продукции 90, 400 и 110 тонн соответственно. Потребители должны получить
- 46. Расходы на перевозки 1 т продукции заданы матрицей (у.е.) Сумма потребностей и сумма запасов равны 140+300+160=90+400+110=600.
- 48. План
- 49. 2)Проверим план на оптимальность методом потенциалов. В таблице занято клеток Для них найдем потенциалы.
- 50. Положим Решим систему:
- 51. Внесем в таблицу потенциалы занятых клеток
- 52. Найдем оценки свободных клеток. Решение не оптимально, т.к. имеется отрицательная оценка.
- 53. 3)Переход к другому решению. Перераспределим грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится
- 54. Около свободной клетки цикла ставится (+), а затем поочередно(-) , (+).У вершин со знаком (-) выбирают
- 58. Получили новое решение Проверим его на оптимальность, вычислив потенциалы базисных клеток.
- 59. Потенциалы заполненных клеток
- 60. Оценки свободных клеток План не оптимален, т.к. оценка клетки (21) отрицательна.
- 63. Новый план Снова проверяем его на оптимальность. Для занятых клеток Находим
- 64. Для свободных клеток псевдостоимости равны
- 65. Оценки свободных клеток
- 67. Скачать презентацию