Метод Фогеля - Математическое моделирование в менеджменте и маркетинге

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

1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.

Данный метод состоит в следующем:

    1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы; 2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 4. Их разность равна d = min21 - min11 = 1.

Для строки N=2 первый минимальный элемент min12 = 0, второй минимальный элемент min22 = 2. Их разность равна d = min22 - min12 = 2.

Для строки N=3 первый минимальный элемент min13 = 1, второй минимальный элемент min23 = 2. Их разность равна d = min23 - min13 = 1.

Для строки N=4 первый минимальный элемент min14 = 2, второй минимальный элемент min24 = 3. Их разность равна d = min24 - min14 = 1.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 1. второй минимальный элемент min21 3. Их разность d = min21 - min11 = 2.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=3 первый минимальный элемент min13 = 0. второй минимальный элемент min23 2. Их разность d = min23 - min13 = 2.

Для столбца N=4 первый минимальный элемент min14 = 2. второй минимальный элемент min24 2. Их разность d = min24 - min14 = 0.

Для столбца N=5 первый минимальный элемент min15 = 3. второй минимальный элемент min25 6. Их разность d = min25 - min15 = 3.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует столбцу (5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (5).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

1

2

5

7

0

2

3

0

60

2

3

1

4

10

2

6

0

45

1

4

3

4

2

7

8

0

70

1

Потребности

25

40

50

30

45

5

0

Разности по столбцам

2

1

2

0

3

0

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

X25 = min(60,45) = 45.

7

3

4

8

X

0

20

5

7

0

2

3

0

60 - 45 = 15

1

4

10

2

X

0

45

3

4

2

7

X

0

70

25

40

50

30

45 - 45 = 0

5

0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 4. Их разность равна d = min21 - min11 = 1.

Для строки N=2 первый минимальный элемент min12 = 0, второй минимальный элемент min22 = 2. Их разность равна d = min22 - min12 = 2.

Для строки N=3 первый минимальный элемент min13 = 1, второй минимальный элемент min23 = 2. Их разность равна d = min23 - min13 = 1.

Для строки N=4 первый минимальный элемент min14 = 2, второй минимальный элемент min24 = 3. Их разность равна d = min24 - min14 = 1.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 1. второй минимальный элемент min21 3. Их разность d = min21 - min11 = 2.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=3 первый минимальный элемент min13 = 0. второй минимальный элемент min23 2. Их разность d = min23 - min13 = 2.

Для столбца N=4 первый минимальный элемент min14 = 2. второй минимальный элемент min24 2. Их разность d = min24 - min14 = 0.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует строке (2). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (3).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

1

2

5

7

0

2

3

0

15

2

3

1

4

10

2

6

0

45

1

4

3

4

2

7

8

0

70

1

Потребности

25

40

50

30

[-]

5

0

Разности по столбцам

2

1

2

0

-

0

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

X23 = min(15,50) = 15.

7

3

4

8

X

0

20

X

X

0

X

3

X

15 - 15 = 0

1

4

10

2

X

0

45

3

4

2

7

X

0

70

25

40

50 - 15 = 35

30

[-]

5

0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 4. Их разность равна d = min21 - min11 = 1.

Для строки N=3 первый минимальный элемент min13 = 1, второй минимальный элемент min23 = 2. Их разность равна d = min23 - min13 = 1.

Для строки N=4 первый минимальный элемент min14 = 2, второй минимальный элемент min24 = 3. Их разность равна d = min24 - min14 = 1.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 1. второй минимальный элемент min21 3. Их разность d = min21 - min11 = 2.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=3 первый минимальный элемент min13 = 2. второй минимальный элемент min23 4. Их разность d = min23 - min13 = 2.

Для столбца N=4 первый минимальный элемент min14 = 2. второй минимальный элемент min24 7. Их разность d = min24 - min14 = 5.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует столбцу (4). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (4).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

1

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

45

1

4

3

4

2

7

8

0

70

1

Потребности

25

40

35

30

[-]

5

0

Разности по столбцам

2

1

2

5

-

0

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

X34 = min(45,30) = 30.

7

3

4

X

X

0

20

X

X

0

X

3

X

[-]

1

4

10

2

X

0

45 - 30 = 15

3

4

2

X

X

0

70

25

40

35

30 - 30 = 0

[-]

5

0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 4. Их разность равна d = min21 - min11 = 1.

Для строки N=3 первый минимальный элемент min13 = 1, второй минимальный элемент min23 = 4. Их разность равна d = min23 - min13 = 3.

Для строки N=4 первый минимальный элемент min14 = 2, второй минимальный элемент min24 = 3. Их разность равна d = min24 - min14 = 1.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 1. второй минимальный элемент min21 3. Их разность d = min21 - min11 = 2.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=3 первый минимальный элемент min13 = 2. второй минимальный элемент min23 4. Их разность d = min23 - min13 = 2.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует строке (3). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (1).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

1

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

15

3

4

3

4

2

7

8

0

70

1

Потребности

25

40

35

[-]

[-]

5

0

Разности по столбцам

2

1

2

-

-

0

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

X31 = min(15,25) = 15.

7

3

4

X

X

0

20

X

X

0

X

3

X

[-]

1

X

X

2

X

X

15 - 15 = 0

3

4

2

X

X

0

70

25 - 15 = 10

40

35

[-]

[-]

5

0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 4. Их разность равна d = min21 - min11 = 1.

Для строки N=4 первый минимальный элемент min14 = 2, второй минимальный элемент min24 = 3. Их разность равна d = min24 - min14 = 1.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min11 = 3. второй минимальный элемент min21 7. Их разность d = min21 - min11 = 4.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=3 первый минимальный элемент min13 = 2. второй минимальный элемент min23 4. Их разность d = min23 - min13 = 2.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует столбцу (1). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (1).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

1

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

[-]

-

4

3

4

2

7

8

0

70

1

Потребности

10

40

35

[-]

[-]

5

0

Разности по столбцам

4

1

2

-

-

0

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

X41 = min(70,10) = 10.

X

3

4

X

X

0

20

X

X

0

X

3

X

[-]

1

X

X

2

X

X

[-]

3

4

2

X

X

0

70 - 10 = 60

10 - 10 = 0

40

35

[-]

[-]

5

0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 4. Их разность равна d = min21 - min11 = 1.

Для строки N=4 первый минимальный элемент min14 = 2, второй минимальный элемент min24 = 4. Их разность равна d = min24 - min14 = 2.

Находим разности по столбцам.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=3 первый минимальный элемент min13 = 2. второй минимальный элемент min23 4. Их разность d = min23 - min13 = 2.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (3).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

1

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

[-]

-

4

3

4

2

7

8

0

60

2

Потребности

[-]

40

35

[-]

[-]

5

0

Разности по столбцам

-

1

2

-

-

0

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

X43 = min(60,35) = 35.

X

3

X

X

X

0

20

X

X

0

X

3

X

[-]

1

X

X

2

X

X

[-]

3

4

2

X

X

0

60 - 35 = 25

[-]

40

35 - 35 = 0

[-]

[-]

5

0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min11 = 3, второй минимальный элемент min21 = 3. Их разность равна d = min21 - min11 = 0.

Для строки N=4 первый минимальный элемент min14 = 4, второй минимальный элемент min24 = 4. Их разность равна d = min24 - min14 = 0.

Находим разности по столбцам.

Для столбца N=2 первый минимальный элемент min12 = 3. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 1.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует столбцу (2). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (2).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

20

0

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

[-]

-

4

3

4

2

7

8

0

25

0

Потребности

[-]

40

[-]

[-]

[-]

5

0

Разности по столбцам

-

1

-

-

-

0

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

X12 = min(20,40) = 20.

X

3

X

X

X

X

20 - 20 = 0

X

X

0

X

3

X

[-]

1

X

X

2

X

X

[-]

3

4

2

X

X

0

25

[-]

40 - 20 = 20

[-]

[-]

[-]

5

0

Находим разности по строкам.

Для строки N=4 первый минимальный элемент min14 = 4, второй минимальный элемент min24 = 4. Их разность равна d = min24 - min14 = 0.

Находим разности по столбцам.

Для столбца N=2 первый минимальный элемент min12 = 4. второй минимальный элемент min22 4. Их разность d = min22 - min12 = 0.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (2).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

[-]

-

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

[-]

-

4

3

4

2

7

8

0

25

0

Потребности

[-]

20

[-]

[-]

[-]

5

0

Разности по столбцам

-

0

-

-

-

0

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

X42 = min(25,20) = 20.

X

3

X

X

X

X

[-]

X

X

0

X

3

X

[-]

1

X

X

2

X

X

[-]

3

4

2

X

X

0

25 - 20 = 5

[-]

20 - 20 = 0

[-]

[-]

[-]

5

0

Находим разности по строкам.

Для строки N=4 первый минимальный элемент min14 = 0, второй минимальный элемент min24 = 0. Их разность равна d = min24 - min14 = 0.

Находим разности по столбцам.

Для столбца N=6 первый минимальный элемент min16 = 0. второй минимальный элемент min26 0. Их разность d = min26 - min16 = 0.

Вычислив все разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (6).

1

2

3

4

5

6

Запасы

Разности по строкам

1

7

3

4

8

6

0

[-]

-

2

5

7

0

2

3

0

[-]

-

3

1

4

10

2

6

0

[-]

-

4

3

4

2

7

8

0

5

0

Потребности

[-]

[-]

[-]

[-]

[-]

5

0

Разности по столбцам

-

-

-

-

-

0

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

X46 = min(5,5) = 5.

X

3

X

X

X

X

[-]

X

X

0

X

3

X

[-]

1

X

X

2

X

X

[-]

3

4

2

X

X

0

5 - 5 = 0

[-]

[-]

[-]

[-]

[-]

5 - 5 = 0

0

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

Сведем все вычисления в одну таблицу.

1

2

3

4

5

6

Запасы

D1

D2

D3

D4

D5

D6

D7

1

7

3[20]

4

8

6

0

20

1

1

1

1

1

1

0

2

5

7

0[15]

2

3[45]

0

60

2

2

-

-

-

-

-

3

1[15]

4

10

2[30]

6

0

45

1

1

1

3

-

-

-

4

3[10]

4[20]

2[35]

7

8

0[5]

70

1

1

1

1

1

2

0

Потребности

25

40

50

30

45

5

D1

2

1

2

0

3

0

D2

2

1

2

0

-

0

D3

2

1

2

5

-

0

D4

2

1

2

-

-

0

D5

4

1

2

-

-

0

D6

-

1

2

-

-

0

D7

-

1

-

-

-

0

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

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

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

F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450

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

Проверим оптимальность опорного плана. Найдем Предварительные потенциалы 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.

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

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

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

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

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

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

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




Метод Фогеля - Математическое моделирование в менеджменте и маркетинге

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