Лабораторная работа №3_4

Вариант №15 (3)

Цель: Решить транспортную задачу. Найти план перевозок, при котором суммарные транспортные расходы будут минимальны.

Составим опорный план методом северо-западного угла (табл. 1):

Zbegin=309

Таблица 1

Поставщики

Потребители

Запасы

В1

В2

В3

А1

6

15

7

5

15

А2

5

1

6

7

4

8

А3

9

10

13

6

7

20

А4

0

0

0

28

28

Потребности

16

20

35

71=71


Решение методом потенциалов:

Наибольшее число занятых клеток во 2-й и 3-й строках. Примем потенциал второй строки равным нулю (а2=0). Вычислим потенциалы всех остальных строк и столбцов.

b1=C21-a2=5-0=5

a1=C11-b1=6-5=1

b2=C22-a2=6-0=6

a3=C32-b2=10-6=4

b3=C33-a3=6-4=2

a4=C43-b3=0-2=-2

Проверим план на оптимальность, рассчитав lij для всех незанятых клеток:

lij=Cij-ai-bj

l12=7-1-6=0

l13=5-1-2=2

l23=4-0-2=2

l31=9-4-5=0

l41= 0-(-2)-5=-3

l42=0-(-2)-6=-4

Условие оптимальности не выполняется для клеток k41 и k42. Наиболее «плошая» из них k42 (l42=-4). Будем рассматривать клетку k42. Поставим в нее знак «+» и построим для нее замкнутый маршрут через занятые клетки, чередуя знаки в углах поворота.

Получили таблицу с рассчитанными потенциалами (табл. 2):

Таблица 2

Поставщики

Потребители

Запасы

В1 b1=5

В2 b2=6

В3 b3=2

А1

а1=1

6

15

7

5

15

А2
а2=0

5

1

6

7

4

8

А3

а3=4

9

- 10

13

+ 6

7

20

А4

а4=-2

0

[+ 0]

- 0

28

28

Потребности

16

20

35

71=71

В клетках со знаком «-» величина грузоперевозки равна 13т.  Вычтем эту величину из клеток, помеченных знаком «-», и прибавим ее к клеткам, помеченным знаком «+». Переходим к новому варианту плана (табл. 3).

НЕ нашли? Не то? Что вы ищете?

Приравняем потенциал 2-й строки (а2) к нулю и вычтем новые потенциалы строк и столбцов:

b1=C21-a2=5-0=5

a1=C11-b1=6-5=1

b2=C22-a2=6-0=6

a4=C42-b2=0-6=-6

b3=C43-a4=0-(-6)=6

a3=C33-b3=6-6=0

Проверим план на оптимальность, рассчитав lij для всех незанятых клеток:

l12=C12-a1-b2=7-1-6=0

l13=C13-a1-b3=5-1-6=-2

l23=C23-a2-b3=4-0-6=-2

l31=C31-a3-b1=9-0-5=4

l32=C32-a3-b2=10-0-6=4

l41=C41-a4-b1=0-(-6)-5=1

Условие оптимальности не выполняется для клетки  k23 (l23=-2). В этой клетке поставим знак «+» и построим через нее замкнутый маршрут.

Таблица 3

Поставщики

Потребители

Запасы

В1 b1=5

В2 b2=6

В3 b3=6

А1

а1=1

6

15

7

5

15

А2
а2=0

5

1

- 6

7

[+ 4]

8

А3

а3=0

9

10

6

20

20

А4

а4=-6

0

+ 0

13

- 0

15

28

Потребности

16

20

35

71=71

Минимальное значение грузоперевозки в клетках, со знаком «-» равно 7т. Вычтем его из клеток со знаком минус и прибавим к клеткам со знаком «+». Перейдем к новому плану (табл. 4).

Вычислим новые значения потенциалов и занесем их в таблицу (табл. 4).

Оптимальность не выполняется для клетки k41 (l41=-1).

Составим маршрут через клетку k41:

Таблица 4

Поставщики

Потребители

Запасы

В1 b1=1

В2 b2=0

В3 b3=0

А1

а1=5

6

15

7

5

15

А2
а2=4

- 5

1

6

+ 4

7

8

А3

а3=6

9

10

6

20

20

А4

а4=0

[+ 0]

0

20

- 0

8

28

Потребности

16

20

35

71=71

Минимальное значение грузоперевозки в клетках со знаком «-» равно 1т. Вычтем это значение из клеток со знаком «-» и прибавим его к клеткам со знаком «+». получим новый план (табл. 5).

Снова найдем значения потенциалов и занесем их в таблицу (табл. 5).

Условие оптимальности не выполняется для клетки k13 (l13=-1). Составим через нее маршрут.

Таблица 5

Поставщики

Потребители

Запасы

В1 b1=0

В2 b2=0

В3 b3=0

А1

а1=6

- 6

15

7

[+ 5]

15

А2
а2=4

5

6

4

8

8

А3

а3=6

9

10

6

20

20

А4

а4=0

+ 0

1

0

20

- 0

7

28

Потребности

16

20

35

71=71

Минимальное значение грузоперевозки в клетках со знаком «-» равно 7т. Вычтем это значение из клеток со знаком «-» и прибавим его к клеткам со знаком «+». Перейдем к новому плану (табл. 6).

Снова вычислим значения потенциалов.

Таблица 6

Поставщики

Потребители

Запасы

В1 b1=6

В2 b2=6

В3 b3=5

А1

а1=0

6

8

7

5

7

15

А2
а2=-1

5

6

4

8

8

А3

а3=1

9

10

6

20

20

А4

а4=-6

0

8

0

20

0

28

Потребности

16

20

35

71=71

Условие оптимальности выполняется для всех клеток.

Zmin=235