Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

Презентация на тему Транспортная задача

Содержание

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) по потребителям (их 5)

Этапы решения транспортной задачиСоставляют математическую модель задачи.Находят исходное опорное решение.Проверяют это решение

Будем называть переменные , стоящие в занятых клетках распределительной или

Определение исходного допустимого решения 1. Метод «северо-западного угла» Метод заключается

2. Метод «наименьшей стоимости» Метод заключается в том, что заполнение

Найти опорный план транспортной задачи методом наименьшей стоимости

Минимальный тариф, равный 1 , находится в клетке

В оставшейся части таблицы с двумя строками и

Временно исключим из рассмотрения столбец и

Заполним описанным выше способом эту клетку и аналогично заполним (

В результате получим опорный план При данном плане перевозок общая стоимость перевозок составляет .

Условие невырожденности плана Если число заполненных клеток равно

В нашей задаче число заполненных клеток равно m + n

Метод потенциалов проверки решения на оптимальность Предположим, что каждый пункт отправления

Теорема «о платежах». Для заданной совокупности платежей и

Теорема оптимальности. Если для всех базисных клеток

Пример Найти опорное решение методом минимальной стоимости и проверить оптимальность решения методом потенциалов.

Пример 2. На складах имеются запасы продукции 90, 400 и 110

Расходы на перевозки 1 т продукции заданы матрицей (у.е.)

2)Проверим план на оптимальность методом потенциалов. В таблице занято

Внесем в таблицу потенциалы занятых клеток

Найдем оценки свободных клеток. Решение не оптимально, т.к. имеется отрицательная оценка.

Около свободной клетки цикла ставится (+), а затем поочередно(-) ,

Получили новое решение Проверим его на оптимальность, вычислив потенциалы базисных клеток.

Оценки свободных клетокПлан не оптимален, т.к. оценка клетки (21) отрицательна.

Для свободных клеток псевдостоимости равны

Все оценки положительны, поэтому план оптимален. Ответ:

Слайды презентации

Слайд 2
Транспортная задача является частным

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

случаем задачи линейного программирования и может быть решена симплекс-методом.

Однако, в силу особенностей этой задачи, она решается с помощью так называемого распределительного метода и его модификаций

Слайд 3
Общая постановка транспортной задачи

Общая постановка транспортной задачи состоит в определении оптимального плана

состоит в определении оптимального плана перевозок некоторого однородного груза

из m пунктов отправления А1, А2,…, Аm в
n пунктов назначения B1, B2,…,Bn.
При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Слайд 4
Рассмотрим транспортную задачу, в которой в

качестве критерия оптимальности берется минимальная стоимость перевозок всего груза.

Обозначим через тарифы или стоимости перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе j-ым пунктом назначения, через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения (перевозки).

Слайд 5 Математическая модель транспортной задачи
Найти

при ограничениях

Слайд 6
Первое ограничение

означает, что

все потребности должны быть удовлетворены , а второе -

,
что все запасы должны быть перевезены.

Слайд 7
Определение. Всякое неотрицательное решение системы ограничений

транспортной задачи, определяемое матрицей размера m×n

,

называют допустимым решением (или планом) транспортной задачи.

Слайд 8
Определение.

План

,

при котором целевая функция принимает минимальное значение, называется оптимальным.

Слайд 9
Тарифы или стоимости перевозок единицы груза

Тарифы или стоимости перевозок единицы груза также задаются

также задаются матрицей, которая называется

матрицей транспортных издержек или матрицей стоимостей

Слайд 10 Транспортная таблица

Слайд 11 Необходимое и достаточное условие разрешимости транспортной задачи

Необходимое и достаточное условие разрешимости транспортной задачи Для разрешимости транспортной

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы

груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, то есть, чтобы выполнялось равенство

--балансовые условия.

Слайд 12
При выполнении этого условия модель транспортной

задачи называется закрытой. Если балансовое условие не выполняется, то

есть
,

то модель транспортной задачи называется открытой.

Слайд 13
В случае открытой транспортной задачи выполнение

балансового условия достигается введением фиктивного поставщика или фиктивного потребителя

с соответствующими тарифами, равными нулю.

Слайд 14
Любое решение транспортной задачи представляет собой

распределение перевозок в транспортной таблице.

Оптимальному решению транспортной задачи соответствует оптимальное распределение перевозок. Перераспределение перевозок в транспортной таблице осуществляется до тех пор, пока не будет найдено оптимальное распределение перевозок.

Слайд 15 Пример

Слайд 16
Все грузы должны быть перевезены, поэтому

Это три первых уравнения.
Все потребности должны быть удовлетворены и, значит,

Это четыре последних уравнения.
Здесь закрытая модель: сумма запасов равна сумме потребностей.

Слайд 17
А целевую функцию составили по матрице

С - матрице тарифов перевозок.

Слайд 18 Пример. Задача организации оптимального снабжения .
Три

фермерских хозяйства

ежедневно могут доставлять в город соответственно 60, 60 и 50 ц молока для обеспечения пяти торговых точек :

Стоимость перевозки 1ц молока и потребности торговых точек в молоке указаны в таблице

Слайд 19 Таблица

Слайд 20 Экономико-математическая модель задачи.
Переменные :

- количество молока , поставляемое i-м фермерским хозяйством в

j-ю торговую точку.
Целевая функция –суммарные транспортные издержки, которые необходимо минимизировать

Слайд 21
Эта задача является задачей открытого типа,

так как запасы молока у фермерских хозяйств (поставщиков) больше

потребностей в молоке у торговых точек. В этом случае изменяется вид системы ограничений.

Слайд 22 Функциональные ограничения:
По поставщикам (их 3)
по потребителям (их

5)

Слайд 23 Этапы решения транспортной задачи
Составляют математическую модель задачи.
Находят исходное

Этапы решения транспортной задачиСоставляют математическую модель задачи.Находят исходное опорное решение.Проверяют это

опорное решение.
Проверяют это решение на оптимальность.
Переходят от одного опорного

решения к другому.

Слайд 24
Будем называть переменные , стоящие в

занятых клетках распределительной или транспортной таблицы, базисными, а переменные

находящиеся в пустых клетках, свободными.

Слайд 25 Определение исходного допустимого решения
1. Метод «северо-западного

Определение исходного допустимого решения 1. Метод «северо-западного угла» Метод заключается в

угла»
Метод заключается в том, что заполнение клеток

таблицы начинают с левой верхней клетки (северо-западная часть таблицы) для перевозки и продолжают вниз и вправо, заканчивая клеткой для перевозки .
При этом способе распределения на тарифы не обращают внимания.

Слайд 26
2. Метод «наименьшей стоимости»
Метод заключается

в том, что заполнение клеток таблицы начинают с клетки,

имеющей наименьшую стоимость перевозки. Если таких клеток несколько, то следует выбрать любую из них.

Слайд 27 Найти опорный план транспортной задачи методом наименьшей стоимости

Слайд 28
Минимальный тариф, равный 1 , находится

в клетке .
Положим

. Запишем это значение в соответствующую клетку и временно исключим из рассмотрения строку .
Потребности пункта назначения считаем временно равными 30 ед.

Слайд 29
В оставшейся части таблицы с двумя

строками и и c

четырьмя столбцами клетка с наименьшим тарифом находится на пересечении строки и столбца , где Положим Внесем это значение в соответствующую клетку таблицы.

Слайд 30
Временно исключим из рассмотрения столбец

Временно исключим из рассмотрения столбец и будем считать запасы

и будем считать запасы пункта

равными 120 ед. После этого рассмотрим оставшуюся часть таблицы с двумя строками и и тремя столбцами , и . В ней минимальный тариф находится в клетке на пересечении строки и столбца и равен 3.

Слайд 31
Заполним описанным выше способом эту клетку

и аналогично заполним ( в определенном порядке) клетки, находящиеся

на пересечении строки и столбца .

Слайд 32
В результате получим опорный план

При данном

плане перевозок общая стоимость перевозок составляет .

Слайд 33 Условие невырожденности плана
Если число

Условие невырожденности плана Если число заполненных клеток равно m +

заполненных клеток равно
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 Пример
Найти опорное решение методом минимальной

стоимости
и проверить оптимальность решения методом потенциалов.

Слайд 41

Слайд 42

Слайд 43
Находим потенциалы базисных клеток

Слайд 44
Положим

и решим систему.
Получим

Найдем псевдостоимости пустых клеток

План перевозок оптимален

Слайд 45 Пример 2.
На складах имеются запасы продукции

90, 400 и 110 тонн соответственно. Потребители должны получить

эту продукцию в количествах 140, 300 и 160 тонн соответственно. Найти такой план закрепления поставщиков к потребителям, при котором суммы затрат на перевозки минимальны.

Слайд 46
Расходы на перевозки 1 т продукции

Расходы на перевозки 1 т продукции заданы матрицей (у.е.) Сумма

заданы матрицей (у.е.)

Сумма потребностей и сумма запасов

равны 140+300+160=90+400+110=600. Модель закрытая.

Слайд 47

Слайд 48
План

Слайд 49
2)Проверим план на оптимальность методом потенциалов.

В таблице занято клеток

Для них найдем

потенциалы.

Слайд 50

Положим
Решим систему:

Слайд 51 Внесем в таблицу потенциалы занятых клеток

Слайд 52
Найдем оценки свободных клеток.

Решение

не оптимально, т.к. имеется отрицательная оценка.

Слайд 53
3)Переход к другому

3)Переход к другому решению. Перераспределим грузы,

решению.
Перераспределим грузы, перемещая их

из занятых клеток в свободные. Свободная клетка становится занятой, а занятая- свободной.
Для свободной клетки с отрицательной оценкой строится цикл(цепь, многоугольник), все вершины которого, кроме одной находятся в занятых клетках. Углы прямые, число вершин четное

Слайд 54
Около свободной клетки цикла ставится (+),

а затем поочередно(-) , (+).У вершин со знаком (-)

выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+) и отнимают от грузов у вершин со знаком (-). В результате перемещения получают новый опорный план. Это решение проверяют на оптимальность и т. д. до тех пор ,пока не получится оптимальное решение.