Транспортные задачи

 

Пример 1.

Требуется решить транспортную задачу, условия которой, представлены в таблице X.

 

 

Поставщики

Потребители

Запасы
груза

 

В1

В2

В3

В4

 

А1

2

6

3

1

11

X=

А2

3

7

8

5

11

 

А3

9

2

4

5

8

 

Потребность
 в
грузе

5

9

9

7

30

 

(Тарифы перевозок выделены синим)

 

Задача является сбалансированной, так как запасы груза и потребности равны.

 

1.      Построение начального плана перевозок

Действуем по правилу северо-западного угла и получаем:

 

 

 

 ai

bj

 

5

9

9

7

X=

11

  7

5Ю

8

6

Я

5

 

3

 

11

2

4

3Ю

5

8

Я

9

 

 8

6

3

1

1Ю

2

7

 

Находим критерий для начального плана перевозок:

            

(Количество распределяемого груза выделено красным)

 

2.      Вычисляем потенциалы и оценки следующим образом:

Вводим потенциалы:

 

                Ui - сопоставим пунктам отправления

                Vj - сопоставим пунктам назначения

 

 

 

 ai

bj

 

5

9

9

7

 

U1

11

    7

5

8

6

5

 

3

X=

U2

11

2

4

3

5

8

9

 

U3

 8

6

3

1

1

2

7

 

 

 

V1

V2

V3

V4

 

Для базисных клеток выполняется равенство Vj-Ui=Cij,  эта система содержит m+n-1 равенство. Первоначально любой из вершин U или V присваиваем любое значение, остальные U и V вычисляются из (1).

 

V1-U1=7         U1=0;V1=7;                         V2-U1=8         V2=8;

V2-U2=4         U2=4;                                  V3-U2=5         V3=9;

V3-U3=1         U3=8;                                  V4-U3=2         V4=10;

 

Находим оценки для небазисных клеток:

    

     D13=V3-U1-C13=9-0-5=4                             D14=V4-U1-C14=10-0-3=7

     D21=V1-U2-C21=7-4-2=1                             D24=V4-U2-C24=10-4-9= -3

D31=V1-U3-C31=7-8-6= -7                           D32=V2-U3-C32=8-8-3= -3

 

Строим матрицу оценок для начального плана перевозок D1:

 

0

0

4

7

1

0

0

-3

-7

-3

0

0

 

Так как есть положительные оценки, то план не является оптимальным.

 

3. Строим цикл пересчета в матрице X на клетке kr.

Строим замкнутый цикл, вершины которого, принадлежат базисным клеткам. Строить начинаем из клетки kr, значение которой является максимальным в матрице D1 , это будет значение 7 в клетке 1,4 (выделена зеленым).  Нумерацию вершин производим так, чтобы выделенная клетка была четной.

 (цепь выделена красным, первоначальная вершина *)

 

 

 

 ai

bj

 

5

9

9

7

X=

11

    7

5

8

6

Я

5

 

3

Ь*

 

11

2

4

3Ю

5

8

Я

9

 

 8

6

3

1

 

1Ю

2

Э

7

Далее, двигаясь по циклу, посчитаем q1=min(Xij ), XijОнечетным,

Получится q1=min(6,8,7)=6.

4.      Строим новую матрицу X  из старой.

Двигаемся по циклу и прибавляем q1 к четным вершинам и вычитаем из нечетных, получим:

 

 

 

 ai

bj

 

5

9

9

7

X1=

11

    7

5

8

 

5

 

3

6

 

11

2

4

9

5

2

9

 

 8

6

3

1

7

2

1

 

Критерий Lk=Lk-1-qk-1* maxDij; 

L1=150-6*7=108

5.      Строим новую матрицу D путем преобразования из предыдущей: 

1) Отмечаем элементы являющиеся базисными в новом решении, максимальный элемент выделяем особо.

2) Строим цепочку выделения, она строится от особо выделенного элемента по строкам затем по столбцам, каждый элемент попавший в цепочку выделяет и строку и столбец, кроме выделенного элемента, он только строки.

3) К выделенным столбцам прибавляем выделенный элемент, из выделенных строк – вычитаем.

(базисные в новом X отмечены жирным курсивным шрифтом, красным отмечены выделенные строки и столбцы)

Итерация 2

      

 

0

0

4

7

-7

 

0

-7

-3

0

D1=

1

0

0

-3

 

D2=

8

0

0

-3

 

-7

-3

0

0

 

 

0

-3

0

0

 

+7

 

 

 

 

 

 

 

 

 

Повторяем пункт 3:

 

 

 

 ai

bj

 

5

9

9

7

X2=

11

    7

5Ю

8

 

5

 

3

6

Я

 

11

2

Э

*

4

9

5

Ь2

9

 

 8

6

3

1

Э

7

2

 

Ь1

 

q2=min(5,1,2)=1.

 

       Повторяем пункт 4:

 

 

 

 ai

bj

 

5

9

9

7

X2=

11

    7

4

8

 

5

 

3

7

 

11

2

1

4

9

5

1

9

 

 8

6

3

1

8

2

 

 

Критерий L2=108-1*8=100

Далее повторяем пункты 5, 3, 4 до тех пор, пока все значения матрицы D будут не   положительны.

          

Итерация 3

 

 

0

-7

-3

0

 

 

0

1

5

0

D2=

8

0

0

-3

-8

D3=

0

0

0

-11

 

0

-3

0

0

 

 

0

-3

0

-8

 

 

+8

+8

 

 

 

 

 

 

 

                                         

 

 

 ai

bj

 

5

9

9

7

X2=

11

    7

4

Я

8

 

5

Ь*

3

7

 

11

2

 

1Ю

4

9

5

Э

1

9

 

 8

6

3

1

8

2

 

 

q3=min(4,1)=1

 

 

 

 ai

bj

 

5

9

9

7

X2=

11

    7

3

8

 

5

1

3

7

 

11

2

2

4

9

5

 

9

 

 8

6

3

1

8

2

 

 

Критерий L3=100-1*5=95

 

Итерация 4

 

 

0

1

5

0

-5

 

0

1

0

0

D3=

0

0

0

-11

-5

D4=

0

0

-5

-11

 

0

-3

0

-8

 

 

-3

2

0

-3

 

+5

+5

 

+5

 

 

 

 

 

 

                                + 

 

 

 ai

bj

 

5

9

9

7

X3=

11

    7

3Ю

8

 

5

1

Я

3

7

 

11

2

Э

2

4

 

Ь9

5

 

9

 

 8

6

3

Э

*

1

 

Ь8

2

 

 

q4=min(8,3,9)=3

 

 

 

 ai

bj

 

5

9

9

7

X3=

11

    7

 

8

 

5

4

3

7

 

11

2

5

4

6

5

 

9

 

 8

6

3

3

1

5

2

 

 

           Критерий L4=95-3*2=89

 

Итерация 5

 

 

0

1

0

0

-2

 

-2

-1

0

-2

D4=

0

0

-5

-11

 

D5=

0

0

-5

-11

 

-3

2

0

-3

-2

 

-5

0

0

-5

 

 

 

+2

+2

 

 

 

 

 

 

       

Все элементы матрицы D5 неположительны, следовательно, на 4ой итерации получили искомое решение X4. 

 

 

 

 

Пример 2.

Требуется решить транспортную задачу, условия которой, представлены в таблице X.

 

 

Поставщики

Потребители

Запасы

груза

 

В1

В2

В3

 

А1

5

7

6

50

X=

А2

6

6

5

40

 

А3

8

4

5

20

 

Потребность в грузе

18

21

33

 

 

Предыдущая задача была сбалансирована в ней

Эта же задача не сбалансирована, так как, в ней присутствует избыток запасов.

Как решать такую задачу ?

 

1.     Находим разницу между запасами и заявками

.

2.     Вводим фиктивный пункт отправления, которому припишем фиктивную заявку равную избытку запасов, а стоимости перевозок сделаем равными нулю,  получим:

 

 

Поставщики

Потребители

Запасы

груза

 

В1

В2

В3

В4

 

А1

5

7

6

0

50

X=

А2

6

6

5

0

40

 

А3

8

4

5

0

20

 

Потребность в грузе

18

21

33

38

110

 

3.     Так как мы свели задачу к сбалансированной, далее решаем,  как и предыдущую:

Итерация 1

 

 

 

 ai

bj

 

18

21

33

38

X=

50

5

18Ю

7

21Ю

6

11

  Я

0

 

40

6

6

5

22Ю

0

18

  Я

 

20

8

4

5

0

20

 

Вычисляем потенциалы:

 

V1-U1=5         U1=0;V1=5                          V2-U1=7         V2=7+U1=7

V3-U1=6         V3=6+U1=6                         V3-U2=5         U2=V3-5=1

V4-U2=0         V4=0+1=1                           V4-U3=0         U3=V4-0=1

 

Находим оценки для небазисных вершин:

    

     D14=V4-U1-C14=1-0-0=1                  D21=V1-U2-C21=5-1-6= -2

D22=V2-U2-C22=7-1-6=0                  D31=V1-U3-C31=5-1-8= -4

D32=V2-U3-C32=7-1-4=2                  D33=V3-U3-C33=6-1-5=0

 

Матрица D1 имеет вид:

 

0

0

0

1

-2

0

0

0

-4

2

0

0

 

Построим цикл пересчета:

 

 

 

 ai

bj

 

18

21

33

38

X=

50

5

18

7

20Ю

6

11

  Я

0

 

40

6

6

5

22Ю

0

  18

    Я

 

20

8

4

Э

*

5

0

 

Ь20

 

q1=min(21,22,20)=20.

 

 

 

 ai

bj

 

18

21

33

38

X1=

50

5

18

7

1

6

31

0

 

40

6

6

5

2

0

38

 

20

8

4

20

5

 

 

 

 Итерация 2

Строим новую матрицу D:

 

 

0

0

0

1

 

 

0

0

0

1

D1=

-2

0

0

0

 

D2=

-2

0

0

0

 

-4

2

0

0

-2

 

-6

0

-2

-2

 

 

 

 

 ai

bj

 

18

21

33

38

X1=

50

5

18

7

1

6

31

Я

0

Ь*

 

40

6

6

5

 

2Ю

0

 Э

 38

 

20

8

4

20

5

 

 

 

q2=min(31,38)=31

 

 

 

 ai

bj

 

18

21

33

38

X2=

50

5

18

7

1

6

 

0

31

 

40

6

6

5

33

0

7

 

20

8

4

20

5

 

 

 

 Итерация 3

 

 

0

0

0

1

-1

 

0

0

-1

0

D2=

-2

0

0

0

 

D3=

-1

1

0

0

 

-6

0

-2

-2

-1

 

-6

0

-3

-3

 

+1

+1

 

 

 

 

 

 

 

 

 

 

 

 

 ai

bj

 

18

21

33

38

X2=

50

5

18

7

1Ю

6

 

0

 31

 Я

 

40

6

6

Э

*

5

33

0

Ь7

 

20

8

4

20

5

 

 

 

q3=min(1,7)=1

 

 

 

 ai

bj

 

18

21

33

38

X3=

50

5

18

7

 

6

 

0

32

 

40

6

6

1

5

33

0

6

 

20

8

4

20

5

 

 

 

 Итерация 4

 

 

0

0

-1

0

-1

 

0

-1

-2

0

D3=

-1

1

0

0

-1

D4=

-1

0

-1

0

 

-6

0

-3

-3

-1

 

-6

-1

-4

-3

 

+1

 

 

+1

 

 

 

 

 

 

   

Все элементы матрицы D4 неположительны, следовательно, на 4ой итерации получили искомое решение X3.