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