Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен c11=7. Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

X11 = min(20,25) = 20.

7

X

X

X

X

X

20 - 20 = 0

5

7

0

2

3

0

60

1

4

10

2

6

0

45

3

4

2

7

8

0

70

25 - 20 = 5

40

50

30

45

5

Искомый элемент равен c21=5. Для этого элемента запасы равны 60, потребности 5. Поскольку минимальным является 5, то вычитаем его.

X21 = min(60,5) = 5.

7

X

X

X

X

X

0

5

7

0

2

3

0

60 - 5 = 55

X

4

10

2

6

0

45

X

4

2

7

8

0

70

5 - 5 = 0

40

50

30

45

5

Искомый элемент равен c22=7. Для этого элемента запасы равны 55, потребности 40. Поскольку минимальным является 40, то вычитаем его.

X22 = min(55,40) = 40.

7

X

X

X

X

X

0

5

7

0

2

3

0

55 - 40 = 15

X

X

10

2

6

0

45

X

X

2

7

8

0

70

0

40 - 40 = 0

50

30

45

5

Искомый элемент равен c23=0. Для этого элемента запасы равны 15, потребности 50. Поскольку минимальным является 15, то вычитаем его.

X23 = min(15,50) = 15.

7

X

X

X

X

X

0

5

7

0

X

X

X

15 - 15 = 0

X

X

10

2

6

0

45

X

X

2

7

8

0

70

0

0

50 - 15 = 35

30

45

5

Искомый элемент равен c33=10. Для этого элемента запасы равны 45, потребности 35. Поскольку минимальным является 35, то вычитаем его.

X33 = min(45,35) = 35.

7

X

X

X

X

X

0

5

7

0

X

X

X

0

X

X

10

2

6

0

45 - 35 = 10

X

X

X

7

8

0

70

0

0

35 - 35 = 0

30

45

5

Искомый элемент равен c34=2. Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его.

X34 = min(10,30) = 10.

7

X

X

X

X

X

0

5

7

0

X

X

X

0

X

X

10

2

X

X

10 - 10 = 0

X

X

X

7

8

0

70

0

0

0

30 - 10 = 20

45

5

Искомый элемент равен c44=7. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.

X44 = min(70,20) = 20.

7

X

X

X

X

X

0

5

7

0

X

X

X

0

X

X

10

2

X

X

0

X

X

X

7

8

0

70 - 20 = 50

0

0

0

20 - 20 = 0

45

5

Искомый элемент равен c45=8. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его.

X45 = min(50,45) = 45.

7

X

X

X

X

X

0

5

7

0

X

X

X

0

X

X

10

2

X

X

0

X

X

X

7

8

0

50 - 45 = 5

0

0

0

0

45 - 45 = 0

5

Искомый элемент равен c46=0. Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.

X46 = min(5,5) = 5.

7

X

X

X

X

X

0

5

7

0

X

X

X

0

X

X

10

2

X

X

0

X

X

X

7

8

0

5 - 5 = 0

0

0

0

0

0

5 - 5 = 0

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7[40]

0[15]

2

3

0

60

3

1

4

10[35]

2[10]

6

0

45

4

3

4

2

7[20]

8[45]

0[5]

70

Потребности

25

40

50

30

45

5

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

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 7*20 + 5*5 + 7*40 + 0*15 + 10*35 + 2*10 + 7*20 + 8*45 + 0*5 = 1315

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v1 = 7; 0 + v1 = 7; v1 = 7

U2 + v1 = 5; 7 + u2 = 5; u2 = -2

U2 + v2 = 7; -2 + v2 = 7; v2 = 9

U2 + v3 = 0; -2 + v3 = 0; v3 = 2

U3 + v3 = 10; 2 + u3 = 10; u3 = 8

U3 + v4 = 2; 8 + v4 = 2; v4 = -6

U4 + v4 = 7; -6 + u4 = 7; u4 = 13

U4 + v5 = 8; 13 + v5 = 8; v5 = -5

U4 + v6 = 0; 13 + v6 = 0; v6 = -13

V1=7

V2=9

V3=2

V4=-6

V5=-5

V6=-13

U1=0

7[20]

3

4

8

6

0

U2=-2

5[5]

7[40]

0[15]

2

3

0

U3=8

1

4

10[35]

2[10]

6

0

U4=13

3

4

2

7[20]

8[45]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (1;2): 0 + 9 > 3; ?12 = 0 + 9 - 3 = 6 (3;1): 8 + 7 > 1; ?31 = 8 + 7 - 1 = 14 (3;2): 8 + 9 > 4; ?32 = 8 + 9 - 4 = 13 (4;1): 13 + 7 > 3; ?41 = 13 + 7 - 3 = 17 (4;2): 13 + 9 > 4; ?42 = 13 + 9 - 4 = 18 (4;3): 13 + 2 > 2; ?43 = 13 + 2 - 2 = 13

Max(6,14,13,17,18,13) = 18

Выбираем максимальную оценку свободной клетки (4;2): 4

Для этого в перспективную клетку (4;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7[40][-]

0[15][+]

2

3

0

60

3

1

4

10[35][-]

2[10][+]

6

0

45

4

3

4[+]

2

7[20][-]

8[45]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (4,2 > 4,4 > 3,4 > 3,3 > 2,3 > 2,2).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (4, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7[20]

0[35]

2

3

0

60

3

1

4

10[15]

2[30]

6

0

45

4

3

4[20]

2

7

8[45]

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v1 = 7; 0 + v1 = 7; v1 = 7

U2 + v1 = 5; 7 + u2 = 5; u2 = -2

U2 + v2 = 7; -2 + v2 = 7; v2 = 9

U4 + v2 = 4; 9 + u4 = 4; u4 = -5

U4 + v5 = 8; -5 + v5 = 8; v5 = 13

U4 + v6 = 0; -5 + v6 = 0; v6 = 5

U2 + v3 = 0; -2 + v3 = 0; v3 = 2

U3 + v3 = 10; 2 + u3 = 10; u3 = 8

U3 + v4 = 2; 8 + v4 = 2; v4 = -6

V1=7

V2=9

V3=2

V4=-6

V5=13

V6=5

U1=0

7[20]

3

4

8

6

0

U2=-2

5[5]

7[20]

0[35]

2

3

0

U3=8

1

4

10[15]

2[30]

6

0

U4=-5

3

4[20]

2

7

8[45]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (1;2): 0 + 9 > 3; ?12 = 0 + 9 - 3 = 6 (1;5): 0 + 13 > 6; ?15 = 0 + 13 - 6 = 7 (1;6): 0 + 5 > 0; ?16 = 0 + 5 - 0 = 5 (2;5): -2 + 13 > 3; ?25 = -2 + 13 - 3 = 8 (2;6): -2 + 5 > 0; ?26 = -2 + 5 - 0 = 3 (3;1): 8 + 7 > 1; ?31 = 8 + 7 - 1 = 14 (3;2): 8 + 9 > 4; ?32 = 8 + 9 - 4 = 13 (3;5): 8 + 13 > 6; ?35 = 8 + 13 - 6 = 15 (3;6): 8 + 5 > 0; ?36 = 8 + 5 - 0 = 13

Max(6,7,5,8,3,14,13,15,13) = 15

Выбираем максимальную оценку свободной клетки (3;5): 6

Для этого в перспективную клетку (3;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7[20][-]

0[35][+]

2

3

0

60

3

1

4

10[15][-]

2[30]

6[+]

0

45

4

3

4[20][+]

2

7

8[45][-]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (3,5 > 3,3 > 2,3 > 2,2 > 4,2 > 4,5).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7[5]

0[50]

2

3

0

60

3

1

4

10

2[30]

6[15]

0

45

4

3

4[35]

2

7

8[30]

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v1 = 7; 0 + v1 = 7; v1 = 7

U2 + v1 = 5; 7 + u2 = 5; u2 = -2

U2 + v2 = 7; -2 + v2 = 7; v2 = 9

U4 + v2 = 4; 9 + u4 = 4; u4 = -5

U4 + v5 = 8; -5 + v5 = 8; v5 = 13

U3 + v5 = 6; 13 + u3 = 6; u3 = -7

U3 + v4 = 2; -7 + v4 = 2; v4 = 9

U4 + v6 = 0; -5 + v6 = 0; v6 = 5

U2 + v3 = 0; -2 + v3 = 0; v3 = 2

V1=7

V2=9

V3=2

V4=9

V5=13

V6=5

U1=0

7[20]

3

4

8

6

0

U2=-2

5[5]

7[5]

0[50]

2

3

0

U3=-7

1

4

10

2[30]

6[15]

0

U4=-5

3

4[35]

2

7

8[30]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (1;2): 0 + 9 > 3; ?12 = 0 + 9 - 3 = 6 (1;4): 0 + 9 > 8; ?14 = 0 + 9 - 8 = 1 (1;5): 0 + 13 > 6; ?15 = 0 + 13 - 6 = 7 (1;6): 0 + 5 > 0; ?16 = 0 + 5 - 0 = 5 (2;4): -2 + 9 > 2; ?24 = -2 + 9 - 2 = 5 (2;5): -2 + 13 > 3; ?25 = -2 + 13 - 3 = 8 (2;6): -2 + 5 > 0; ?26 = -2 + 5 - 0 = 3

Max(6,1,7,5,5,8,3) = 8

Выбираем максимальную оценку свободной клетки (2;5): 3

Для этого в перспективную клетку (2;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7[5][-]

0[50]

2

3[+]

0

60

3

1

4

10

2[30]

6[15]

0

45

4

3

4[35][+]

2

7

8[30][-]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (2,5 > 2,2 > 4,2 > 4,5).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5]

7

0[50]

2

3[5]

0

60

3

1

4

10

2[30]

6[15]

0

45

4

3

4[40]

2

7

8[25]

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v1 = 7; 0 + v1 = 7; v1 = 7

U2 + v1 = 5; 7 + u2 = 5; u2 = -2

U2 + v3 = 0; -2 + v3 = 0; v3 = 2

U2 + v5 = 3; -2 + v5 = 3; v5 = 5

U3 + v5 = 6; 5 + u3 = 6; u3 = 1

U3 + v4 = 2; 1 + v4 = 2; v4 = 1

U4 + v5 = 8; 5 + u4 = 8; u4 = 3

U4 + v2 = 4; 3 + v2 = 4; v2 = 1

U4 + v6 = 0; 3 + v6 = 0; v6 = -3

V1=7

V2=1

V3=2

V4=1

V5=5

V6=-3

U1=0

7[20]

3

4

8

6

0

U2=-2

5[5]

7

0[50]

2

3[5]

0

U3=1

1

4

10

2[30]

6[15]

0

U4=3

3

4[40]

2

7

8[25]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (3;1): 1 + 7 > 1; ?31 = 1 + 7 - 1 = 7 (4;1): 3 + 7 > 3; ?41 = 3 + 7 - 3 = 7 (4;3): 3 + 2 > 2; ?43 = 3 + 2 - 2 = 3

Max(7,7,3) = 7

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5[5][-]

7

0[50]

2

3[5][+]

0

60

3

1[+]

4

10

2[30]

6[15][-]

0

45

4

3

4[40]

2

7

8[25]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7[20]

3

4

8

6

0

20

2

5

7

0[50]

2

3[10]

0

60

3

1[5]

4

10

2[30]

6[10]

0

45

4

3

4[40]

2

7

8[25]

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v1 = 7; 0 + v1 = 7; v1 = 7

U3 + v1 = 1; 7 + u3 = 1; u3 = -6

U3 + v4 = 2; -6 + v4 = 2; v4 = 8

U3 + v5 = 6; -6 + v5 = 6; v5 = 12

U2 + v5 = 3; 12 + u2 = 3; u2 = -9

U2 + v3 = 0; -9 + v3 = 0; v3 = 9

U4 + v5 = 8; 12 + u4 = 8; u4 = -4

U4 + v2 = 4; -4 + v2 = 4; v2 = 8

U4 + v6 = 0; -4 + v6 = 0; v6 = 4

V1=7

V2=8

V3=9

V4=8

V5=12

V6=4

U1=0

7[20]

3

4

8

6

0

U2=-9

5

7

0[50]

2

3[10]

0

U3=-6

1[5]

4

10

2[30]

6[10]

0

U4=-4

3

4[40]

2

7

8[25]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (1;2): 0 + 8 > 3; ?12 = 0 + 8 - 3 = 5 (1;3): 0 + 9 > 4; ?13 = 0 + 9 - 4 = 5 (1;5): 0 + 12 > 6; ?15 = 0 + 12 - 6 = 6 (1;6): 0 + 4 > 0; ?16 = 0 + 4 - 0 = 4 (4;3): -4 + 9 > 2; ?43 = -4 + 9 - 2 = 3

Max(5,5,6,4,3) = 6

Выбираем максимальную оценку свободной клетки (1;5): 6

Для этого в перспективную клетку (1;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7[20][-]

3

4

8

6[+]

0

20

2

5

7

0[50]

2

3[10]

0

60

3

1[5][+]

4

10

2[30]

6[10][-]

0

45

4

3

4[40]

2

7

8[25]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (1,5 > 1,1 > 3,1 > 3,5).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7[10]

3

4

8

6[10]

0

20

2

5

7

0[50]

2

3[10]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3

4[40]

2

7

8[25]

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v1 = 7; 0 + v1 = 7; v1 = 7

U3 + v1 = 1; 7 + u3 = 1; u3 = -6

U3 + v4 = 2; -6 + v4 = 2; v4 = 8

U1 + v5 = 6; 0 + v5 = 6; v5 = 6

U2 + v5 = 3; 6 + u2 = 3; u2 = -3

U2 + v3 = 0; -3 + v3 = 0; v3 = 3

U4 + v5 = 8; 6 + u4 = 8; u4 = 2

U4 + v2 = 4; 2 + v2 = 4; v2 = 2

U4 + v6 = 0; 2 + v6 = 0; v6 = -2

V1=7

V2=2

V3=3

V4=8

V5=6

V6=-2

U1=0

7[10]

3

4

8

6[10]

0

U2=-3

5

7

0[50]

2

3[10]

0

U3=-6

1[15]

4

10

2[30]

6

0

U4=2

3

4[40]

2

7

8[25]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (2;4): -3 + 8 > 2; ?24 = -3 + 8 - 2 = 3 (4;1): 2 + 7 > 3; ?41 = 2 + 7 - 3 = 6 (4;3): 2 + 3 > 2; ?43 = 2 + 3 - 2 = 3 (4;4): 2 + 8 > 7; ?44 = 2 + 8 - 7 = 3

Max(3,6,3,3) = 6

Выбираем максимальную оценку свободной клетки (4;1): 3

Для этого в перспективную клетку (4;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7[10][-]

3

4

8

6[10][+]

0

20

2

5

7

0[50]

2

3[10]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3[+]

4[40]

2

7

8[25][-]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (4,1 > 4,5 > 1,5 > 1,1).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7

3

4

8

6[20]

0

20

2

5

7

0[50]

2

3[10]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3[10]

4[40]

2

7

8[15]

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v5 = 6; 0 + v5 = 6; v5 = 6

U2 + v5 = 3; 6 + u2 = 3; u2 = -3

U2 + v3 = 0; -3 + v3 = 0; v3 = 3

U4 + v5 = 8; 6 + u4 = 8; u4 = 2

U4 + v1 = 3; 2 + v1 = 3; v1 = 1

U3 + v1 = 1; 1 + u3 = 1; u3 = 0

U3 + v4 = 2; 0 + v4 = 2; v4 = 2

U4 + v2 = 4; 2 + v2 = 4; v2 = 2

U4 + v6 = 0; 2 + v6 = 0; v6 = -2

V1=1

V2=2

V3=3

V4=2

V5=6

V6=-2

U1=0

7

3

4

8

6[20]

0

U2=-3

5

7

0[50]

2

3[10]

0

U3=0

1[15]

4

10

2[30]

6

0

U4=2

3[10]

4[40]

2

7

8[15]

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

(4;3): 2 + 3 > 2; ?43 = 2 + 3 - 2 = 3

Выбираем максимальную оценку свободной клетки (4;3): 2

Для этого в перспективную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7

3

4

8

6[20]

0

20

2

5

7

0[50][-]

2

3[10][+]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3[10]

4[40]

2[+]

7

8[15][-]

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (4,3 > 4,5 > 2,5 > 2,3).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (4, 5) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7

3

4

8

6[20]

0

20

2

5

7

0[35]

2

3[25]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3[10]

4[40]

2[15]

7

8

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v5 = 6; 0 + v5 = 6; v5 = 6

U2 + v5 = 3; 6 + u2 = 3; u2 = -3

U2 + v3 = 0; -3 + v3 = 0; v3 = 3

U4 + v3 = 2; 3 + u4 = 2; u4 = -1

U4 + v1 = 3; -1 + v1 = 3; v1 = 4

U3 + v1 = 1; 4 + u3 = 1; u3 = -3

U3 + v4 = 2; -3 + v4 = 2; v4 = 5

U4 + v2 = 4; -1 + v2 = 4; v2 = 5

U4 + v6 = 0; -1 + v6 = 0; v6 = 1

V1=4

V2=5

V3=3

V4=5

V5=6

V6=1

U1=0

7

3

4

8

6[20]

0

U2=-3

5

7

0[35]

2

3[25]

0

U3=-3

1[15]

4

10

2[30]

6

0

U4=-1

3[10]

4[40]

2[15]

7

8

0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj

    (1;2): 0 + 5 > 3; ?12 = 0 + 5 - 3 = 2 (1;6): 0 + 1 > 0; ?16 = 0 + 1 - 0 = 1

Max(2,1) = 2

Выбираем максимальную оценку свободной клетки (1;2): 3

Для этого в перспективную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

1

2

3

4

5

6

Запасы

1

7

3[+]

4

8

6[20][-]

0

20

2

5

7

0[35][-]

2

3[25][+]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3[10]

4[40][-]

2[15][+]

7

8

0[5]

70

Потребности

25

40

50

30

45

5

Цикл приведен в таблице (1,2 > 1,5 > 2,5 > 2,3 > 4,3 > 4,2).

Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 5) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

6

Запасы

1

7

3[20]

4

8

6

0

20

2

5

7

0[15]

2

3[45]

0

60

3

1[15]

4

10

2[30]

6

0

45

4

3[10]

4[20]

2[35]

7

8

0[5]

70

Потребности

25

40

50

30

45

5

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.

U1 + v2 = 3; 0 + v2 = 3; v2 = 3

U4 + v2 = 4; 3 + u4 = 4; u4 = 1

U4 + v1 = 3; 1 + v1 = 3; v1 = 2

U3 + v1 = 1; 2 + u3 = 1; u3 = -1

U3 + v4 = 2; -1 + v4 = 2; v4 = 3

U4 + v3 = 2; 1 + v3 = 2; v3 = 1

U2 + v3 = 0; 1 + u2 = 0; u2 = -1

U2 + v5 = 3; -1 + v5 = 3; v5 = 4

U4 + v6 = 0; 1 + v6 = 0; v6 = -1

V1=2

V2=3

V3=1

V4=3

V5=4

V6=-1

U1=0

7

3[20]

4

8

6

0

U2=-1

5

7

0[15]

2

3[45]

0

U3=-1

1[15]

4

10

2[30]

6

0

U4=1

3[10]

4[20]

2[35]

7

8

0[5]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию uI + vJ ? cIj.

Минимальные затраты составят: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450

Анализ оптимального плана.

Из 1-го склада необходимо часть груза (20) направить в 2-й магазин.

Из 2-го склада необходимо груз направить в 3-й магазин (15), в 5-й магазин (45)

Из 3-го склада необходимо груз направить в 1-й магазин (15), в 4-й магазин (30)

Из 4-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин (35)

На 4-ом складе остался невостребованным груз в количестве 5 ед.

Оптимальный план является вырожденным, так как базисная переменная x46=0.

Похожие статьи




Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге

Предыдущая | Следующая