Ryattel_A_V_Kontrolnaya_tetrad_po_lineynoy

Спрос

100

200

200

300

100

Мощность

потребителей

поставщиков

100

1

3

4

1

0

100

200

5

2

2

7

0

0

200

400

4

4

3

6

0

0

200

200

7

2

5

3

0

Вычисляем оставшиеся запасы третьего поставщика: 400-0-200=200.

Свободный северо-западный угол – ячейка (3;4). Возможная перевозка в эту

ячейку – 200, она меньше запросов третьего потребителя (300). Исключаем из

рассмотрения третьего поставщика.

Спрос

100

200

200

300

100

Мощность

потребителей

поставщиков

100

1

3

4

1

0

100

200

5

2

2

7

0

0

200

400

4

4

3

6

0

0

200

200

200

7

2

5

3

0

Следующая возможная поставка – в ячейку (4;4). Запасы четвертого

поставщика – 200, однако оставшийся неудовлетворенный спрос четвертого

поставщика лишь 300-200=100. Осуществим перевозку 100 в ячейку (4;4), и

запросы четвертого потребителя будут полностью удовлетворены.

Спрос

100

200

200

300

100

Мощность

потребителей

поставщиков

100

1

3

4

1

0

100

200

5

2

2

7

0

0

200

400

4

4

3

6

0

0

200

200

200

7

2

5

3

0

100

51

u1

0 ;

v

1 u

1 0 1;

1

1

u

2

5 v

5 1 4 ;

1

v

2

2 u

2

2 4 2 ;

u

3

4 v

2

4 ( 2) 6 ;

v

3

3 u

3

3 6 3;

v

4

6 u

3

6 6 0

;

u

4

3 v

4

3 0 0

;

v

5

0 u

4

0 0 0 .

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

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

v 1

v

2

2

v

3

3

v

4

0

v

5

0

1

Спрос

100

200

200

300

100

Мощность

потребителей

поставщиков

u1

0

100

1

3

4

1

0

100

u2

4

200

5

2

2

7

0

0

200

u3

6

400

4

4

3

6

0

0

200

200

u4

0

200

7

2

5

3

0

100

100

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

оценки

ij

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

ij 0 ):

12

u v

2

c 0 2 3 5;

24

u

v

c

4 0 7 3 ;

1

12

2

4

24

13

u v

3

c

0 3 4 7 ;

25

u

v

c

4 0 0 4 ;

1

13

2

5

25

14 u1 v4 c14 0 0 1 1;

31 u3 v1 c31 6 1 4 3 ;

15 u1 v5 c15 0 0 0 0 ;

35 u3 v5 c35 6 0 0 6 ;

23 u2 v3 c23 4 3 2 1;

41 u4 v1 c41 0 1 7 6;

53

100

200

200

300

100

100

1

3

4

1

0

100

200

5

2

2

7

0

-

+ 100

0

100

400

4

4

3

6

0

- 100

+

200

100

200

7

2

5

3

0

200

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

циклу:

z min(0;100) 0 .

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

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

же по величине груз. Таким образом, клетка (3;1) становится заполненной

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

опорное решение.

100

200

200

300

100

100

1

3

4

1

0

100

200

5

2

2

7

0

100

100

400

4

4

3

6

0

0

100

200

100

200

7

2

5

3

0

200

Вычисляем

значение

целевой

функции

на

этом

опорном

решении:

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

Проверим оптимальность найденного распределения поставок.

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

u

v

1

1

1

v

2

u

2

2

u

2

v

0

5

v

4

u

3

1

v

4

.

u

3

2

v

3

u

3

3

v

6

u

3

4

v

3

u

4

4

Придадим u1

нулевое значение:

u1 0 . Остальные потенциалы находятся

однозначно:

u1 0 ;

v4

6 u3

6 3 3

;

v

1 u 1 0 1;

u

3 v

3 3 0

;

1

1

4

4

u

4 v

4 1 3 ;

u

2 v

2 1 1

;

3

1

2

2

v

4 u

4 3 1

;

v

0 u

0 1 1

.

2

3

5

2

v

3 u

3 3 0

;

3

3