ТРАНСПОРТНАЯ ЗАДАЧА Лекции 10,11. Транспортная задача является частным случаем задачи линейного программирования и может быть решена симплекс-методом. - презентация

1 ТРАНСПОРТНАЯ ЗАДАЧА Лекции 10,11

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. Метод «северо-западного угла» Метод заключается в том, что заполнение клеток таблицы начинают с левой верхней клетки (северо-западная часть таблицы) для перевозки и продолжают вниз и вправо, заканчивая клеткой для перевозки. При этом способе распределения на тарифы не обращают внимания.

26 2. Метод «наименьшей стоимости» Метод заключается в том, что заполнение клеток таблицы начинают с клетки, имеющей наименьшую стоимость перевозки. Если таких клеток несколько, то следует выбрать любую из них.

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

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 Пример Найти опорное решение методом минимальной стоимости и проверить оптимальность решения методом потенциалов.

41

42

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

44 Положим и решим систему. Получим Найдем псевдо стоимости пустых клеток План перевозок оптимален

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

46 Расходы на перевозки 1 т продукции заданы матрицей (у.е.) Сумма потребностей и сумма запасов равны = =600. Модель закрытая.

47

48 План

49 2)Проверим план на оптимальность методом потенциалов. В таблице занято клеток Для них найдем потенциалы.

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

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

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

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

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

55

56

57

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

59 Потенциалы заполненных клеток

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

61

62

63 Новый план Снова проверяем его на оптимальность. Для занятых клеток Находим

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

65 Оценки свободных клеток

66 Все оценки положительны, поэтому план оптимален. Ответ:. При этом По сравнению с первоначальним планом расходы уменьшились на величину =330 у.е.