Решите транспортную задачу Три поставщика произвольного товара обладают запасами

Решите транспортную задачу.
Три поставщика произвольного товара обладают запасами, приведенными в следующей таблице. Этот товар должен быть перевезен трем потребителям.
Требуется: 1) Определите начальное опорное решение:
методом «северо-западного угла»;
методом минимального элемента;
2) Найдите оптимальный план перевозок.
Вариант 2
Номер
поставщика Возможности
поставщика Потребители и их спрос

1 2 3

270 100 80
1 200 7 6 4
2 150 3 8 5
3 100 2 3 7

Решение:

Т.к. суммарные запасы поставщиков равны суммарной потребности потребителей (200+150+100=450≡450=270+100+80), то задача – закрытого типа.
Составляем первоначальный опорный план перевозок методом «северо-западного угла» (перевозке от A1 к B1 ставим максимально возможное значение – 200, тем самым запасы первого поставщика использованы полностью – первую строку исключаем из рассмотрения, первому потребителю необходимо еще 70 единиц товара; перевозке от A2 к B1ставим максимально возможное значение – 70 и т.д.):

b1=270
b2=100
b3=80
a1=200
7 6 4

200

a2=150
3 8 5

70 80
a3=100
2 3 7

20 80
Определим стоимость перевозки согласно полученному плану:
C=7*200+3*70+8*80+3*20+7*80=2870
Первоначальный опорный план формируем методом минимального элемента (находим в матрице стоимости минимальное значение равное 2, и ставим ему в соответствие 100 – максимально возможную перевозку от A3 к B1, тем самым запасы третьего поставщика использованы полностью – третью строку исключаем из рассмотрения, находим минимальное значение в оставшейся матрице и т.д.):

Читайте также:  Решив проверить на практике теорию вероятностей Фома бросил три игральные кости 770 раз

b1=270
b2=100
b3=80
a1=200
7 6 4

20 100 80
a2=150
3 8 5

150

a3=100
2 3 7

100

Определим стоимость перевозки согласно полученному плану:
C=7*20+6*100+4*80+3*150+2*100=1710
Т.к. суммарная стоимость опорного плана, полученного методом минимального элемента ниже, то в качестве исходного опорного плана берем его.
Число занятых клеток равно 5, при этом n + m – 1= 3 + 3 – 1 = 5, то есть план невырожденный. Рассчитаем систему потенциалов. Полагаем u1=0.
Из первой строки:
u1+v1=7,u1+v2=6,u1+v3=4 v1=7,v2=6, v3=4
Из первого столбца:
u2+v1=3,u3+v1=2 u2=-4, u3=-5
Находим величины ∆ij=ui+vj-cij для всех незанятых поставками клеток:

v1=7
v2=6
v3=4
u1=0
7 6 4

20 100 80

u2=-4
3 8 5

150

-6 -5
u3=-5
2 3 7

100

-2 -8

Поскольку нет положительных оценок, план поставок оптимален.
Т.е. матрица перевозок имеет вид:
20100801500010000
А суммарная стоимость перевозок:
C=1710

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...