Метод двойного предпочтения

Помечаем галочкой клетку с наименьшим тарифом в каждом столбце. Это клетки А1-В1, А1-В2, А2-В3, А3-В4. Затем помечаем галочкой клетку с наименьшим тарифом в каждом строке. Это клетки А1-В1, А2-В3, А3-В3. Начинаем заполнять таблицу с клетки с двумя галочками. Их две – А1-В1 и А2-В3 в А1-В1. Помещаем в нее min (300,250)=250. Это запас – заполняем нулями остаток столбца. Клетка с двумя галочками в оставшейся части матрицы – клетка А2-В3. Значение перевозки в ней равно min (290,320)=290. Это – остаток по потребности, поэтому заполняем нулями остаток столбца. Клеток, помеченных одной галочкой в оставшейся части две – А1-В2 и А3-В4. Наименьший тариф в А1-В2. Значение перевозки в этой клетке равно min (300-50,200)=50. Это – остаток запаса, поэтому заполняем нулями остаток строки. В оставшейся части матрицы осталась одна клетка с галочкой – А3-В4. Значение перевозки в ней равно min (260,380)=260. Это – остаток по потребности, поэтому заполняем нулями остаток столбца. Оставшиеся 4 незаполненных клетки обрабатываем по методу минимальной стоимости (номера указываем в скобках под тарифом). Это – остаток запаса, поэтому заполняем нулями остаток строки. Клетка с наименьшим тарифом (1) оставшейся части матрицы – А2-В2. Значение перевозки в ней равно min (320-290,200-50)=30. Это – остаток запаса, поэтому заполняем нулями остаток строки. Последний элемент в оставшейся части матрицы – клетка А3-В2. Значение перевозки в ней равно min (200-50-30,380-260)=120. Полученный опорный план представлен на рис. 3.5. Заметим, что, несмотря на другой порядок заполнения, он совпадает с опорным планом, который получен методом минимально стоимости и стоимость перевозок по нему

F=250×1 + 50×4 + 30×8 + 290×3 + 120×15 + 260×9 =5700

Из трех полученных планов наименьшую стоимость имеет план, полученный методом Северо-Западного угла. Выберем его для первоначального плана метода потенциала.

Рис. 3.5. Нахождение опорного плана ТЗ по методу двойного предпочтения

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

U₁+V₁=1

U₁+V₂=4

U₂+V₂=8

U₂+V₃=3

U₃+V₃=7

U₃+V₄=9.

Задаем U₁=0 и разрешаем систему уравнений. Значения вычисленных потенциалов следующие:

V₁=1

V₂=4

U₂ =4

V₃=–1

U₃ =8

V₄=1.

Далее вычисляем косвенные тарифы в незанятых клетках как суммы соответствующих потенциалов:

c^*₁₃=U₁+V₃=0 – 1 =–1

c^*₁₄=U₁+V₄=0 + 1 = 1

c^*₂₁=U₂+V₁=4 + 1 = 5

c^*₂₄=U₂+V₄=4 + 1 = 5

c^*₃₁=U₃+V₁=8 + 1 = 9

c^*₃₂=U₃+V₂=8 + 4 =12.

Для определения оптимальности плана вычисляем разности между косвенным и прямым тарифами в незанятых клетках и определяем их знаки.

c^*₁₃ – c₁₃ = – 1 –5 = –6

c^*₁₄ – c₁₄ =1 – 11 = –10

c^*₂₁ – c₂₁= 5 – 12 = –7

c^*₂₄ – c₂₄= 5 – 14 = –9

c^*₃₁ – c₃₁= 9 –10 = –1

c^*₃₂ – c₃₂=12 – 15 = –3.

Все разности отрицательны, следовательно, этот план оптимален.

Рис. 3.6. Опорный план ТЗ, построенный по методу минимальной стоимости

Рассмотрим решение этой же задачи, взяв за первоначальный опорный план, полученный другими методами (по методам минимальной стоимости и двойного предпочтения мы получили один и тот же план, представленный на рис. 3.6).

Поиск по сайту: