Определение опорного плана транспортной задачи Метод северо-западного угла Метод минимального элемента Метод аппроксимации Фогеля. - презентация

1 Определение опорного плана транспортной задачи Метод северо-западного угла Метод минимального элемента Метод аппроксимации Фогеля

2 Математическая дисциплина, занимающаяся изучением экстремальных (максимальных или минимальных) задач управления, планирования и разработкой методов их решения, получила название математического программирования. Задачи управления и планирования возможно представить как выбор параметров и системы функций, например: Требуется найти максимум функции f(xi,x 2,...,x n ) при условиях

3 Требуется найти максимум функции f(xi,x 2,...,x n ) при условиях Здесь f, g i функции, x 1, x 2, · · ·, x n параметры управления. Выражение f(xi,x 2,...,x n ) называется функцией цели. Условия представляют собой ограничения поставленной задачи.

4 транспортная задача Цель - в минимизации полной стоимости перевозок известного количества товаров со складов к потребителю. постановка транспортной задачи : определение оптимального плана перевозок однородного груза из m пунктов отправления A1, A2,..., Am в n пунктов назначения B1, B2,..., Bn. в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

5 транспортная задача определение оптимального плана перевозок груза из m пунктов отправления A1, A2,..., Am в n пунктов назначения B1, B2,..., Bn. определение минимального значения целевой функции стоимости перевозок Всякое неотрицательное решение систем линейных уравнений, называется планом транспортной задачи. План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

6 транспортная задача определение оптимального плана перевозок груза из m пунктов отправления A1, A2,..., Am в n пунктов назначения B1, B2,..., Bn. Пункты отправлени я Пункты назначения Запас ы B1B1...BjBj BnBn A1A1 c 11 x c 1j x 1j... c 1n x 1n a1a1... AiAi c i1 x i1... c ij x ij... c in x in aiai... AmAm c m1 x m1... c mj x mj... c mn x mn amam Потребност и b1b1...bjbj bnbn

7 транспортная задача Пункты отправлени я Пункты назначения Запас ы B1B1...BjBj BnBn A1A1 c 11 x c 1j x 1j... c 1n x 1n a1a1... AiAi c i1 x i1... c ij x ij... c in x in aiai... AmAm c m1 x m1... c mj x mj... c mn x mn amam Потребност и b1b1...bjbj bnbn Сij тарифы перевозок Xij количество груза

8 Определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. опорный план находят последовательно за n+m-1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения, либо вывоз груза из одного из пунктов отправления. Опорный план является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

9 Метод северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного X11 (северо-западный угол) заканчивается для неизвестного Xmn, т. е. идет как бы по диагонали таблицы с севера на запад. Пункты отправления Пункты назначения Запасы B1B1...BjBj BnBn A1A1 c 11 x c 1j x 1j... c 1n x 1n a1a1... AiAi c i1 x i1... c ij x ij... c in x in aiai... AmAm c m1 x m1... c mj x mj... c mn x mn amam Потребностиb1b1...bjbj bnbn

10 Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности Метод северо-западного угла Задача 1. На три базы A1, A2, A3 поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Это груз требуется перевезти в пять пунктов назначения B1, B2, B3, B4, B5 соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице:

11 Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности Метод северо-западного угла Решение. пунктов отправления m=3, а число пунктов назначения n= =7 Заполнение таблицы начнем с неизвестного x11, т. е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта A1 больше, чем потребности пункта B1, то полагаем x11=60, записываем это значение в соответствующей клетке табл и временно исключаем из рассмотрения столбец B1, считая при этом запасы пункта A1 равными 80.

12 Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности Метод северо-западного угла Решение. первые из оставшихся пунктов отправления A1 и назначения B2. Запасы пункта A1 больше потребностей пункта B2. Положим X12=70, запишем это значение в соответствующей клетке табл и временно исключим из рассмотрения столбец B2. В пункте A1 запасы считаем равными 10 ед.

13 Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности Метод северо-западного угла Решение. Снова рассмотрим первые из оставшихся пунктов отправления A1 и назначения B3. Потребности пункта B3 больше оставшихся запасов пункта A1. Положим X13=10 и исключим из рассмотрения строку A1. Значение X13=10 запишем в соответствующую клетку табл и считаем потребности пункта B3 равными 110 ед.

14 Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности Метод северо-западного угла Решение. Теперь перейдем к заполнению клетки для неизвестного x23 и т. д. Через шесть шагов остается один пункт отправления A3 с запасом груза 100 ед. и один пункт назначения B5 с потребностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая x35=100. В результате получаем опорный план

15 Метод северо-западного угла Решение. В результате получаем опорный план Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности

16 Метод северо-западного угла Пункты отправления Пункты назначенияЗапасы B1B2B3B4B5 A A A Потребности общая стоимость перевозок всего груза S=2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380

17 Метод минимального элемента Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на тарифы перевозок, а именно: на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбирать любую из них), и рассмотреть пункты назначения и отправления, соответствующие выбранной клетке. Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом. Этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем общая стоимость перевозок при плане, найденном для данной задачи с помощью метода северо-западного угла. Поэтому наиболее целесообразно опорный план транспортной задачи находить методом минимального элемента.

18 Пункты отправления Пункты назначения Запасы B1B2B3B4 A A A Потребности Метод минимального элемента Задача 2

19 Пункты отправления Пункты назначения Запасы B1B2B3B4 A A A Потребности Метод минимального элемента Решение. Минимальный тариф равный 1, находится в клетке для переменной x13. Положим x13=160, запишем это значение в соответствующую клетку таблицы и временно исключим из рассмотрения строку A1. Потребности пункта назначения B3 читаем равными 30.

20 Пункты отправления Пункты назначения Запасы B1B2B3B4 A A A Потребности Метод минимального элемента Решение. В оставшейся части таблицы с двумя строками A2 и A3 и четырьмя столбцами B1, B2, B3 и B4 клетка с наименьшим тарифом находится на пересечении строки A3 и столбца B2, где С32=2. Положим X32=50 и внесем это значение в соответствующую клетку.

21 Метод минимального элемента Решение. Временно исключим из рассмотрения столбец B2 и будем считать запасы пункта A3 равными 120. После этого рассмотрим оставшуюся часть таблицы с двумя строками A2 и A3 и тремя столбцами B1, B3 и B4. В ней минимальный тариф находится в клетке на пересечении строки A3 и столбца B3 и равен 3. Заполним описанным выше способом эту клетку и аналогично заполним клетки, находящиеся на пересечении строки A2 и столбца B1, строки A3 и столбца B4, строки A2 и столбца B4. В результате получим опорный план. При данном плане перевозок общая стоимость перевозок составляет. S=1*160+4*120+8*20+2*50+3*30+6*90=1530

22 Метод аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди разностей выбирают максимальную. В строке (или столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).

23 Метод аппроксимации Фогеля Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке. Так в строке A2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце B4 равна 6-2=4. Пункты отправления Пункты назначения Запасы B1B2B3B4 A A A Потребности

24 Метод аппроксимации Фогеля Пункты отправления Пункты назначения Запасы Разности по строкам B1B2B3B4 A A A Потребности Разности по столбцам

25 Метод аппроксимации Фогеля Пункты отправления Пункты назначения Запасы Разности по строкам B1B2B3B4 A A A Потребности Разности по столбцам 3324

26 Метод аппроксимации Фогеля Пункты отправления Пункты назначения Запасы Разности по строкам B1B2B3B4 A A A Потребности Разности по столбцам 3324 Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу B4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки A1 и столбца B4. Таким образом эту клетку следует заполнить.. Заполнив ее, тем самым мы удовлетворим потребности пункта B4. Поэтому исключим из рассмотрения столбец B4 и будем считать запасы пункта A1 равными =50

27 Метод аппроксимации Фогеля Пункты отправления Пункты назначения Запасы Разности по строкам B1B2B3B4 A A A Потребности Разности по столбцам

28 Метод аппроксимации Фогеля Пункты отправления Пункты назначения ЗапасыРазности по строкам B1B2B3B4 A A A Потребности Разности по столбцам общая стоимость перевозок S=1*50+2*110+4*120+5*20+2*30+3*140=1330.