Зерно из четырех районов должно быть перевезено на три элеватора

Зерно из четырех районов должно быть перевезено на три элеватора. Ожидаемый сбор зерна в районах: 1 — 400 тыс. ц., 2 — 500 тыс ц., 3 -800 тыс ц., 4 — 500 тыс ц. Мощность элеваторов 1 — 700 тыс. ц., 2 — 800 тыс. ц., 3 -700 тыс. ц. Затраты на перевозку 1 центнера зерна из районов к элеваторам приведена в таблице (руб.) Определить план перевозок зерна с минимальными транспортными затратами.

Районы

Элеваторы

1

2

3

1-й

1

4

3

2-й

7

1

5

3-й

4

8

3

4-й

4

2

8

Решение:

Исходная таблица:
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1   1

  4

  3

  400
  A2   7

  1

  5

  500
  A3   4

  8

  3

  800
  A4   4

  2

  8

  500
Потребность 700 800 700  
Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.Находим опорный план по правилу северо-западного угла:Помещаем в клетку (1,1) меньшее из чисел A1*=400 и B1*=700Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимаетсяПомещаем в клетку (2,1) меньшее из чисел A2*=500 и B1*=300Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимаетсяПомещаем в клетку (2,2) меньшее из чисел A2*=200 и B2*=800Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимаетсяПомещаем в клетку (3,2) меньшее из чисел A3*=800 и B2*=600Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимаетсяПомещаем в клетку (3,3) меньшее из чисел A3*=200 и B3*=700Так как запасы поставщика A3 исчерпаны, то строка 3 в дальнейшем в расчет не принимаетсяПомещаем в клетку (4,3) меньшее из чисел A4*=500 и B3*=500
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
300
    1
200
    5
 
  500
  A3     4
 
    8
600
    3
200
  800
  A4     4
 
    2
 
    8
500
  500
Потребность 700 800 700  
Целевая функция F=1*400+7*300+1*200+8*600+3*200+8*500=12100
Решаем задачу методом потенциалов:
Этап 1
Потенциалы Ui_U1=0V1=C1,1-U1= 1U2=C2,1-V1=6V2=C2,2-U2= -5U3=C3,2-V2=13V3=C3,3-U3= -10U4=C4,3-V3=18Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 — (u1 + v2) = 9.S1,3 = c1,3 — (u1 + v3) = 13.S2,3 = c2,3 — (u2 + v3) = 9.S3,1 = c3,1 — (u3 + v1) = -10.S4,1 = c4,1 — (u4 + v1) = -15.S4,2 = c4,2 — (u4 + v2) = -11.Наиболее потенциальной является клетка (4,1). Для нее оценка равна -15.Строим для нее цикл, помечая клетки цикла знаками «плюс» и «минус».
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2  —  7
300
 +  1
200
    5
 
  500
  A3     4
 
 —  8
600
 +  3
200
  800
  A4  +  4
 
    2
 
 —  8
500
  500
Потребность 700 800 700  
Перемещаем по циклу груз величиной в 300 единиц, прибавляя эту величину к грузу в клетках со знаком «плюс» и отнимая ее от груза в клетках со знаком «минус».В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
 
    1
500
    5
 
  500
  A3     4
 
    8
300
    3
500
  800
  A4     4
300
    2
 
    8
200
  500
Потребность 700 800 700  
Целевая функция F= 7600
Этап 2
Потенциалы Ui_U1=0V1=C1,1-U1= 1U4=C4,1-V1=3V3=C4,3-U4= 5U3=C3,3-V3=-2V2=C3,2-U3= 10U2=C2,2-V2=-9Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 — (u1 + v2) = -6.S1,3 = c1,3 — (u1 + v3) = -2.S2,1 = c2,1 — (u2 + v1) = 15.S2,3 = c2,3 — (u2 + v3) = 9.S3,1 = c3,1 — (u3 + v1) = 5.S4,2 = c4,2 — (u4 + v2) = -11.Наиболее потенциальной является клетка (4,2). Для нее оценка равна -11.Строим для нее цикл, помечая клетки цикла знаками «плюс» и «минус».
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
 
    1
500
    5
 
  500
  A3     4
 
 —  8
300
 +  3
500
  800
  A4     4
300
 +  2
 
 —  8
200
  500
Потребность 700 800 700  
Перемещаем по циклу груз величиной в 200 единиц, прибавляя эту величину к грузу в клетках со знаком «плюс» и отнимая ее от груза в клетках со знаком «минус».В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
 
    1
500
    5
 
  500
  A3     4
 
    8
100
    3
700
  800
  A4     4
300
    2
200
    8
 
  500
Потребность 700 800 700  
Целевая функция F= 5400
Этап 3
Потенциалы Ui_U1=0V1=C1,1-U1= 1U4=C4,1-V1=3V2=C4,2-U4= -1U2=C2,2-V2=2U3=C3,2-V2=9V3=C3,3-U3= -6Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 — (u1 + v2) = 5.S1,3 = c1,3 — (u1 + v3) = 9.S2,1 = c2,1 — (u2 + v1) = 4.S2,3 = c2,3 — (u2 + v3) = 9.S3,1 = c3,1 — (u3 + v1) = -6.S4,3 = c4,3 — (u4 + v3) = 11.Наиболее потенциальной является клетка (3,1). Для нее оценка равна -6.Строим для нее цикл, помечая клетки цикла знаками «плюс» и «минус».
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
 
    1
500
    5
 
  500
  A3  +  4
 
 —  8
100
    3
700
  800
  A4  —  4
300
 +  2
200
    8
 
  500
Потребность 700 800 700  
Перемещаем по циклу груз величиной в 100 единиц, прибавляя эту величину к грузу в клетках со знаком «плюс» и отнимая ее от груза в клетках со знаком «минус».В результате перемещения по циклу получим новый план:
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
 
    1
500
    5
 
  500
  A3     4
100
    8
 
    3
700
  800
  A4     4
200
    2
300
    8
 
  500
Потребность 700 800 700  
Целевая функция F= 4800
Этап 4
Потенциалы Ui_U1=0V1=C1,1-U1= 1U3=C3,1-V1=3V3=C3,3-U3= 0U4=C4,1-V1=3V2=C4,2-U4= -1U2=C2,2-V2=2Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток:S1,2 = c1,2 — (u1 + v2) = 5.S1,3 = c1,3 — (u1 + v3) = 3.S2,1 = c2,1 — (u2 + v1) = 4.S2,3 = c2,3 — (u2 + v3) = 3.S3,2 = c3,2 — (u3 + v2) = 6.S4,3 = c4,3 — (u4 + v3) = 5.Так как все оценки Si,j>=0, то полученный план является оптимальным.Транспортная задача решена.
Поставщик Потребитель Запасы груза
    B1         B2         B3       A1     1
400
    4
 
    3
 
  400
  A2     7
 
    1
500
    5
 
  500
  A3     4
100
    8
 
    3
700
  800
  A4     4
200
    2
300
    8
 
  500
Потребность 700 800 700  
Целевая функция F= 4800

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