Ryattel_A_V_Kontrolnaya_tetrad_po_lineynoy

v 1

v

2

1

v 0

v

4

3

v 3

1

3

5

100

200

200

300

100

u1

0

100

1

3

4

1

0

100

u2

3

200

5

2

2

7

0

200

0

u3

3

400

4

4

3

6

0

0

200

100

100

u4

0

200

7

2

5

3

0

200

Проверим опорное решение на оптимальность. С этой целью вычисляем

оценки ij

для всех незаполненных клеток таблицы (для всех занятых клеток

ij 0 ):

12 u1 v2 c12 0 1 3 4 ;

24 u2 v4 c24 3 3 7 1;

u v c

0 0 4 4;

32

u

v

c

3 1 4 2

;

13

1

3

13

3

2

32

14 u1 v4 c14 0 3 1 2 ;

41 u4 v1 c41 0 1 7 6

;

u v

c

0 3 0 3;

42

u v c

0 1 2 3 ;

15

1

5

15

4

2

42

21 u2 v1 c21 3 1 5 1;

43 u4 v3 c43 0 0 5 5 ;

23 u2 v3 c23 3 0 2 1;

45 u4 v3 c43 0 3 0 3.

Решение не является оптимальным, так как имеются положительные

оценки 14

, 23 .

5 итерация.

Переходим к новому опорному решению. Для клетки (1;4) с

положительной оценкой строим означенный цикл пересчета. Ставим в клетку

(1;4) знак «+», присоединяем ее к занятым клеткам, строим цикл. В угловых

точках цикла расставляем поочередно знаки «+» и «-», начиная с «+» в клетке

(1;4).

35

100

200

200

300

100

100

1 -

3

4

1

+

0

100

200

5

2

2

7

0

200

0

400

4

4

3

6

-

0

+

0

200

100

100

200

7

2

5

3

0

200

Определим поставку z, передаваемую по циклу:

z min(100;100) 100 .

Осуществляем сдвиг по циклу на величину z=100. В клетки, отмеченные знаком

«+», добавляется груз 100, а из клеток, отмеченных знаком «–», убавляется

такой же по величине груз. Клетка (1;4) становится заполненной поставкой 100,

клетка (1;1) – свободной, клетка (3;4) – заполненной нулевой поставкой. Таким

образом, получаем новое опорное решение.

100

200

200

300

100

100

1

3

4

1

0

100

200

5

2

2

7

0

200

0

400

4

4

3

6

0

100

200

0

100

200

7

2

5

3

0

200

Вычисляем

значение

целевой

функции

на

этом

опорном

решении:

F(X ) 1 100 2 200 0 0 4 100 3 200 6 0 0 100 3 200 =2200.

Проверим

оптимальность

найденного

распределения

поставок.

Записываем систему уравнений для нахождения потенциалов:

u

v

1

1

4

v

2

u

2

2

u

2

v

5

0

v

4

u

3

1

.

v

3

u

3

3

v

6

u

3

4

v

0

u

3

5

v

3

u

4

4

Придадим одному из потенциалов, например, u1

произвольное значение,

например, 0:

u1

0

. Остальные потенциалы находятся однозначно:

u1

0 ;

v3 3 u3 3 5 2

;

v4 1 u1 1 0 1;

v5 0 u3 0 5 5 ;

u

6 v

6 1 5;

u4 3 v4 3 1 2 ;

3

4

v

4 u

4 5 1;

u2 0 v5 0 ( 5) 5;

1

3

v

4 u

4 5 1;

v2 2 u2 2 5 3.

1

3

Значения потенциалов записываем в таблицу рядом с запасами или

запросами соответствующих поставщиков и потребителей:

v 1

v

2

3

v

3

2

v

4

1

v

5

5

1

100

200

200

300

100

u1

0

100

1

3

4

1

0

100

u2

5

200

5

2

2

7

0

200

0

u3

5

400

4

4

3

6

0

100

200

0

100

u4

2

200

7

2

5

3

0

200

Проверим опорное решение на оптимальность. С этой целью вычисляем

оценки ij

для всех незаполненных клеток таблицы (для всех занятых клеток

ij 0 ):

36

v 1

v

2

3

v

3

2

v

4

1

v

5

5

1

100

200

200

300

100

u1

0

100

1

3

4

1

0

100

u2

5

200

5

2

2

7

0

200

0

u3

5

400

4

4

3

6

0

100

200

0

100

u4

2

200

7

2

5

3

0

200

Проверим опорное решение на оптимальность. С этой целью вычисляем

оценки ij

для всех незаполненных клеток таблицы (для всех занятых клеток

ij

0 ):

u v c

0 1 1 2 ;

32

u

v

c

5 3 4 2;

11

1

1

11

3

2

32

12

u1

v2

c12

0 3 3 6

;

41 u4 v1 c41 2 1 7 6;

13

u v

c

0 2 4 6

;

42

u

v

c

2 3 2 3

;

1

3

13

4

2

42

15

u1

v5

c15

0 5 0 5

;

43

u

v

c

2 2 5 5

;

4

3

43

u

v c

5 1 5 1;

45

u

v

c

2 5 0 3 .

21

4

3

43

2

1

21

24 u2 v4 c24 5 1 7 1;

25

u

v

c

5 5 0 0 ;

2

5

25

Полученное решение является оптимальным, так как отсутствуют

положительные оценки.

Ответ:

минимальная стоимость перевозок

составит

2100

(у.е.)

при

0

0

0

100

0

200

0

0

следующей матрице перевозок:

.

100

0

200

0

0

0

0

200

35