Метод северо-западного угла

Заполнение таблицы начинается с левого верхнего угла, двигаясь далее или по строке вправо или по столбцу вниз. В клетку (1,1) заносим перевозку х₁₁=min (a₁,b₁) . Если a₁> b₁ , то х₁₁ = b₁ , первый столбец закрыт, т.е. потребности первого потребителя удовлетворены полностью.

Далее заполняем клетку (1,2), занося туда перевозку х₁₂=min (a₁ - b₁ ,b₂ ), и т.д., до тех пор, пока не исчерпаем запасы первого поставщика. После этого сдвигаемся на строку вниз и, начиная с того столбца, на котором остановились в предыдущей строке, продолжаем опять двигаться вправо, до тех пор, пока не исчерпаем запасы второго поставщика. Процесс продолжается до тех пор пока ресурсы всех поставщиков не будут исчерпаны, а потребности всех потребителей не будут удовлетворены, т.е. пока мы не окажемся в крайней правой нижней клетке (m,n ).

ЗАДАЧА№3

Поставщики товара - оптовые коммерческие предприятия , имеют запасы товаров соответственно в количестве , ,... единиц и розничные торговые предприятия , ,..., .- подали заявку на закупку товаров в объемах соответственно: , , ..., . Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы

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

Первая буква	Фамилия	Имя
А
Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
ЮЯ

Первая буква

Отчество

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Э

ЮЯ

Пример 8.

В пунктах отправления А₁ и А₂ находится 150 т и 90 т горючего. Его надо доставить в пункты потребления В₁, В₂, и В₃ в количествах b₁= 60 т, b₂ = 110 т, b₃= 70 т. Стоимость перевозки горючего задана матрицей тарифов С = Составить план перевозок с min стоимостью.

Решение методом северо-западного угла Таблица 4

Стоимость перевозок в этом случае будет:

F = 6·60+10·90+2·20+8·70 = 360+900+40+560 = 1860 руб.

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

Метод минимального элемента

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

Пример 9

Для тех же условий, что в примере 8 распределить груз методом минимального элемента.

Решение методом минимального элемента

Таблица 5

Заполнение начинаем с клетки (2,2) с наименьшим тарифом c₂₂=2, куда заносим перевозку х₂₂=min (90, 110) = 90. Затем переходим к клетке (1,3) с c₁₃ = 4, куда заносим перевозку х₁₃=min (70, 150) = 70. Затем переходим к клетке (1,1) , куда заносим х₁₁=min (60, 150-70) = 60. И, наконец, в клетку (1,2) заносим оставшиеся 20 ед. груза. Стоимость перевозок будет:

F = 60∙6 + 20∙10 + 70∙4 + 90∙2 = 360+200+280 +180 = 1020 руб. – очевидно ближе к оптимальному плану.

Не нашли, что искали? Воспользуйтесь поиском по сайту: