на максимум северо-запад. метод.

Возвращаемся к плану №7
Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;3);

	11[10]	16[6]	20[0]
		8[3]		2[20]
		4[11]	10[10]

Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 11; 0 + v₁ = 11; v₁ = 11
u₁ + v₂ = 16; 0 + v₂ = 16; v₂ = 16
u₂ + v₂ = 8; 16 + u₂ = 8; u₂ = -8
u₂ + v₄ = 2; -8 + v₄ = 2; v₄ = 10
u₃ + v₂ = 4; 16 + u₃ = 4; u₃ = -12
u₃ + v₃ = 10; -12 + v₃ = 10; v₃ = 22

	v1=11	v2=16	v3=22	v4=10
u1=0	11[10]	16[6]	20[0]
u2=-8		8[3]		2[20]
u3=-12		4[11]	10[10]
u4=-

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(2;1): -8 + 11 < 12; ∆₂₁ = -8 + 11 - 12 = -9
(3;1): -12 + 11 < 5; ∆₃₁ = -12 + 11 - 5 = -6
(3;4): -12 + 10 < 8; ∆₃₄ = -12 + 10 - 8 = -10
max(9,6,10) = -10
Выбираем максимальную оценку свободной клетки (3;4): 8
Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

					Запасы
	11[10]	16[6]	20[0]
		8[3][+]		2[20][-]
		4[11][-]	10[10]	8[+]
Потребности

Цикл приведен в таблице (3,4 → 3,2 → 2,2 → 2,4).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 11. Прибавляем 11 к объемам грузов, стоящих в плюсовых клетках и вычитаем 11 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

					Запасы
	11[10]	16[6]	20[0]
		8[14]		2[9]
			10[10]	8[11]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 11; 0 + v₁ = 11; v₁ = 11
u₁ + v₂ = 16; 0 + v₂ = 16; v₂ = 16
u₂ + v₂ = 8; 16 + u₂ = 8; u₂ = -8
u₂ + v₄ = 2; -8 + v₄ = 2; v₄ = 10
u₃ + v₄ = 8; 10 + u₃ = 8; u₃ = -2
u₃ + v₃ = 10; -2 + v₃ = 10; v₃ = 12

	v1=11	v2=16	v3=12	v4=10
u1=0	11[10]	16[6]	20[0]
u2=-8		8[14]		2[9]
u3=-2			10[10]	8[11]
u4=-

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;3): 0 + 12 < 20; ∆₁₃ = 0 + 12 - 20 = -8
(2;1): -8 + 11 < 12; ∆₂₁ = -8 + 11 - 12 = -9
(2;3): -8 + 12 < 6; ∆₂₃ = -8 + 12 - 6 = -2
max(8,9,2) = -9
Выбираем максимальную оценку свободной клетки (2;1): 12
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

					Запасы
	11[10][-]	16[6][+]	20[0]
	12[+]	8[14][-]		2[9]
			10[10]	8[11]
Потребности

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

					Запасы
		16[16]	20[0]
	12[10]	8[4]		2[9]
			10[10]	8[11]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₂ = 16; 0 + v₂ = 16; v₂ = 16
u₂ + v₂ = 8; 16 + u₂ = 8; u₂ = -8
u₂ + v₁ = 12; -8 + v₁ = 12; v₁ = 20
u₂ + v₄ = 2; -8 + v₄ = 2; v₄ = 10
u₃ + v₄ = 8; 10 + u₃ = 8; u₃ = -2
u₃ + v₃ = 10; -2 + v₃ = 10; v₃ = 12

	v1=20	v2=16	v3=12	v4=10
u1=0		16[16]	20[0]
u2=-8	12[10]	8[4]		2[9]
u3=-2			10[10]	8[11]
u4=-

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;3): 0 + 12 < 20; ∆₁₃ = 0 + 12 - 20 = -8
(2;3): -8 + 12 < 6; ∆₂₃ = -8 + 12 - 6 = -2
max(8,2) = -8
Выбираем максимальную оценку свободной клетки (1;3): 20
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

					Запасы
		16[16][-]	20[0][+]
	12[10]	8[4][+]		2[9][-]
			10[10][-]	8[11][+]
Потребности

Цикл приведен в таблице (1,3 → 1,2 → 2,2 → 2,4 → 3,4 → 3,3).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 9. Прибавляем 9 к объемам грузов, стоящих в плюсовых клетках и вычитаем 9 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

					Запасы
		16[7]	20[9]
	12[10]	8[13]
			10[1]	8[20]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₂ = 16; 0 + v₂ = 16; v₂ = 16
u₂ + v₂ = 8; 16 + u₂ = 8; u₂ = -8
u₂ + v₁ = 12; -8 + v₁ = 12; v₁ = 20
u₁ + v₃ = 20; 0 + v₃ = 20; v₃ = 20
u₃ + v₃ = 10; 20 + u₃ = 10; u₃ = -10
u₃ + v₄ = 8; -10 + v₄ = 8; v₄ = 18

	v1=20	v2=16	v3=20	v4=18
u1=0		16[7]	20[9]
u2=-8	12[10]	8[13]
u3=-10			10[1]	8[20]
u4=-

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Максимальная прибыль составит: F(x) = 16*7 + 20*9 + 12*10 + 8*13 + 10*1 + 8*20 = 686

 

3. Решение транспортной задачи

Транспортная задача.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

1 2 3 4 Запасы

1 11 16 20 7 16

2 12 8 6 2 23

3 5 4 10 8 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 16 + 23 + 21 + 0 = 60

∑b = 10 + 20 + 10 + 20 = 60

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

1 2 3 4 Запасы

1 11 16 20 7 16

2 12 8 6 2 23

3 5 4 10 8 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 2 3 4 Запасы Разности по строкам

1 11 16 20 7 16 4

2 12 8 6 2 23 4

3 5 4 10 8 21 1

4 0 0 0 0 0 0

Потребности 10 20 10 20

Разности по столбцам 5 4 6 2

 

Искомый элемент равен 6

Для этого элемента запасы равны 23, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x23 = min(23,10) = 10.

11 16 x 7 16

12 8 6 2 23 - 10 = 13

5 4 x 8 21

0 0 x 0 0

10 20 10 - 10 = 0 20

 

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

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

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

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

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

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

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

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

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

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

1 2 3 4 Запасы Разности по строкам

1 11 16 20 7 16 4

2 12 8 6 2 13 6

3 5 4 10 8 21 1

4 0 0 0 0 0 0

Потребности 10 20 [-] 20

Разности по столбцам 5 4 - 2

 

Искомый элемент равен 2

Для этого элемента запасы равны 13, потребности 20. Поскольку минимальным является 13, то вычитаем его.

x24 = min(13,20) = 13.

11 16 x 7 16

x x 6 2 13 - 13 = 0

5 4 x 8 21

0 0 x 0 0

10 20 [-] 20 - 13 = 7

 

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

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

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

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

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

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

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

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

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

1 2 3 4 Запасы Разности по строкам

1 11 16 20 7 16 4

2 12 8 6 2 [-] -

3 5 4 10 8 21 1

4 0 0 0 0 0 0

Потребности 10 20 [-] 7

Разности по столбцам 5 4 - 7

 

Искомый элемент равен 7

Для этого элемента запасы равны 16, потребности 7. Поскольку минимальным является 7, то вычитаем его.

x14 = min(16,7) = 7.

11 16 x 7 16 - 7 = 9

x x 6 2 [-]

5 4 x x 21

0 0 x x 0

10 20 [-] 7 - 7 = 0

 

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

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

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

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

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

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

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

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

1 2 3 4 Запасы Разности по строкам

1 11 16 20 7 9 5

2 12 8 6 2 [-] -

3 5 4 10 8 21 1

4 0 0 0 0 0 0

Потребности 10 20 [-] [-]

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

 

Искомый элемент равен 11

Для этого элемента запасы равны 9, потребности 10. Поскольку минимальным является 9, то вычитаем его.

x11 = min(9,10) = 9.

11 x x 7 9 - 9 = 0

x x 6 2 [-]

5 4 x x 21

0 0 x x 0

10 - 9 = 1 20 [-] [-]

 

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

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

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

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

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

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

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

1 2 3 4 Запасы Разности по строкам

1 11 16 20 7 [-] -

2 12 8 6 2 [-] -

3 5 4 10 8 21 1

4 0 0 0 0 0 0

Потребности 1 20 [-] [-]

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

 

Искомый элемент равен 5

Для этого элемента запасы равны 21, потребности 1. Поскольку минимальным является 1, то вычитаем его.

x31 = min(21,1) = 1.

11 x x 7 [-]

x x 6 2 [-]

5 4 x x 21 - 1 = 20

x 0 x x 0

1 - 1 = 0 20 [-] [-]

 

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

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

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

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

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

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

1 2 3 4 Запасы Разности по строкам

1 11 16 20 7 [-] -

2 12 8 6 2 [-] -

3 5 4 10 8 20 0

4 0 0 0 0 0 0

Потребности [-] 20 [-] [-]

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

 

Искомый элемент равен 4

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

x32 = min(20,20) = 20.

11 x x 7 [-]

x x 6 2 [-]

5 4 x x 20 - 20 = 0

x 0 x x 0

[-] 20 - 20 = 0 [-] [-]

 

1 2 3 4 Запасы

1 11[9] 16 20 7[7] 16

2 12 8 6[10] 2[13] 23

3 5[1] 4[20] 10 8 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

F(x) = 11*9 + 7*7 + 6*10 + 2*13 + 5*1 + 4*20 = 319

1 2 3 4 Запасы

1 11[9] 16 20 7[7] 16

2 12 8 6[10] 2[13] 23

3 5[1] 4[20] 10 8 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

1 2 3 4 Запасы d1 d2 d3 d4

1 11[9] 16 20 7[7] 16 4 4 4 5

2 12 8 6[10] 2[13] 23 4 6 - -

3 5[1] 4[20] 10 8 21 1 1 1 1

4 0 0 0 0 0 0 0 0 0

Потребности 10 20 10 20

d1 5 4 6 2

d2 5 4 - 2

d3 5 4 - 7

d4 5 4 - -

 

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

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

F(x) = 11*9 + 7*7 + 6*10 + 2*13 + 5*1 + 4*20 = 319

Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;2);

1 2 3 4

1 11[9] 16[0] 20 7[7]

2 12 8 6[10] 2[13]

3 5[1] 4[20] 10 8

4 0 0 0 0

 

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

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

u1 + v1 = 11; 0 + v1 = 11; v1 = 11

u3 + v1 = 5; 11 + u3 = 5; u3 = -6

u3 + v2 = 4; -6 + v2 = 4; v2 = 10

u1 + v4 = 7; 0 + v4 = 7; v4 = 7

u2 + v4 = 2; 7 + u2 = 2; u2 = -5

u2 + v3 = 6; -5 + v3 = 6; v3 = 11

v1=11 v2=10 v3=11 v4=7

u1=0 11[9] 16[0] 20 7[7]

u2=-5 12 8 6[10] 2[13]

u3=-6 5[1] 4[20] 10 8

u4=- 0 0 0 0

 

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

(1;2): 0 + 10 < 16; ∆12 = 0 + 10 - 16 = -6

(1;3): 0 + 11 < 20; ∆13 = 0 + 11 - 20 = -9

(2;1): -5 + 11 < 12; ∆21 = -5 + 11 - 12 = -6

(2;2): -5 + 10 < 8; ∆22 = -5 + 10 - 8 = -3

(3;3): -6 + 11 < 10; ∆33 = -6 + 11 - 10 = -5

(3;4): -6 + 7 < 8; ∆34 = -6 + 7 - 8 = -7

max(6,9,6,3,5,7) = -9

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

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

1 2 3 4 Запасы

1 11[9] 16[0] 20[+] 7[7][-] 16

2 12 8 6[10][-] 2[13][+] 23

3 5[1] 4[20] 10 8 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

u1 + v1 = 11; 0 + v1 = 11; v1 = 11

u3 + v1 = 5; 11 + u3 = 5; u3 = -6

u3 + v2 = 4; -6 + v2 = 4; v2 = 10

u1 + v3 = 20; 0 + v3 = 20; v3 = 20

u2 + v3 = 6; 20 + u2 = 6; u2 = -14

u2 + v4 = 2; -14 + v4 = 2; v4 = 16

v1=11 v2=10 v3=20 v4=16

u1=0 11[9] 16[0] 20[7] 7

u2=-14 12 8 6[3] 2[20]

u3=-6 5[1] 4[20] 10 8

u4=- 0 0 0 0

 

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

(1;2): 0 + 10 < 16; ∆12 = 0 + 10 - 16 = -6

(2;1): -14 + 11 < 12; ∆21 = -14 + 11 - 12 = -15

(2;2): -14 + 10 < 8; ∆22 = -14 + 10 - 8 = -12

max(6,15,12) = -15

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

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

1 2 3 4 Запасы

1 11[9][-] 16[0] 20[7][+] 7 16

2 12[+] 8 6[3][-] 2[20] 23

3 5[1] 4[20] 10 8 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

u1 + v1 = 11; 0 + v1 = 11; v1 = 11

u2 + v1 = 12; 11 + u2 = 12; u2 = 1

u2 + v4 = 2; 1 + v4 = 2; v4 = 1

u3 + v1 = 5; 11 + u3 = 5; u3 = -6

u3 + v2 = 4; -6 + v2 = 4; v2 = 10

u1 + v3 = 20; 0 + v3 = 20; v3 = 20

v1=11 v2=10 v3=20 v4=1

u1=0 11[6] 16[0] 20[10] 7

u2=1 12[3] 8 6 2[20]

u3=-6 5[1] 4[20] 10 8

u4=- 0 0 0 0

 

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

(1;2): 0 + 10 < 16; ∆12 = 0 + 10 - 16 = -6

(1;4): 0 + 1 < 7; ∆14 = 0 + 1 - 7 = -6

(3;4): -6 + 1 < 8; ∆34 = -6 + 1 - 8 = -13

max(6,6,13) = -13

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

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

1 2 3 4 Запасы

1 11[6] 16[0] 20[10] 7 16

2 12[3][+] 8 6 2[20][-] 23

3 5[1][-] 4[20] 10 8[+] 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

u1 + v1 = 11; 0 + v1 = 11; v1 = 11

u2 + v1 = 12; 11 + u2 = 12; u2 = 1

u2 + v4 = 2; 1 + v4 = 2; v4 = 1

u3 + v4 = 8; 1 + u3 = 8; u3 = 7

u3 + v2 = 4; 7 + v2 = 4; v2 = -3

u1 + v3 = 20; 0 + v3 = 20; v3 = 20

v1=11 v2=-3 v3=20 v4=1

u1=0 11[6] 16[0] 20[10] 7

u2=1 12[4] 8 6 2[19]

u3=7 5 4[20] 10 8[1]

u4=- 0 0 0 0

 

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

(1;2): 0 -3 < 16; ∆12 = 0 -3 - 16 = -19

(1;4): 0 + 1 < 7; ∆14 = 0 + 1 - 7 = -6

(2;2): 1 -3 < 8; ∆22 = 1 -3 - 8 = -10

(4;2): - -3 < 0; ∆42 = - -3 - 0 = -3

max(19,6,10,3) = -19

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

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

1 2 3 4 Запасы

1 11[6][-] 16[0][+] 20[10] 7 16

2 12[4][+] 8 6 2[19][-] 23

3 5 4[20][-] 10 8[1][+] 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

u1 + v2 = 16; 0 + v2 = 16; v2 = 16

u3 + v2 = 4; 16 + u3 = 4; u3 = -12

u3 + v4 = 8; -12 + v4 = 8; v4 = 20

u2 + v4 = 2; 20 + u2 = 2; u2 = -18

u2 + v1 = 12; -18 + v1 = 12; v1 = 30

u1 + v3 = 20; 0 + v3 = 20; v3 = 20

v1=30 v2=16 v3=20 v4=20

u1=0 11 16[6] 20[10] 7

u2=-18 12[10] 8 6 2[13]

u3=-12 5 4[14] 10 8[7]

u4=- 0 0 0 0

 

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

(2;2): -18 + 16 < 8; ∆22 = -18 + 16 - 8 = -10

(2;3): -18 + 20 < 6; ∆23 = -18 + 20 - 6 = -4

(3;3): -12 + 20 < 10; ∆33 = -12 + 20 - 10 = -2

max(10,4,2) = -10

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

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

1 2 3 4 Запасы

1 11 16[6] 20[10] 7 16

2 12[10] 8[+] 6 2[13][-] 23

3 5 4[14][-] 10 8[7][+] 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

u1 + v2 = 16; 0 + v2 = 16; v2 = 16

u2 + v2 = 8; 16 + u2 = 8; u2 = -8

u2 + v1 = 12; -8 + v1 = 12; v1 = 20

u3 + v2 = 4; 16 + u3 = 4; u3 = -12

u3 + v4 = 8; -12 + v4 = 8; v4 = 20

u1 + v3 = 20; 0 + v3 = 20; v3 = 20

v1=20 v2=16 v3=20 v4=20

u1=0 11 16[6] 20[10] 7

u2=-8 12[10] 8[13] 6 2

u3=-12 5 4[1] 10 8[20]

u4=- 0 0 0 0

 

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

(3;3): -12 + 20 < 10; ∆33 = -12 + 20 - 10 = -2

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

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

1 2 3 4 Запасы

1 11 16[6][+] 20[10][-] 7 16

2 12[10] 8[13] 6 2 23

3 5 4[1][-] 10[+] 8[20] 21

4 0 0 0 0 0

Потребности 10 20 10 20

 

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

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

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

u1 + v2 = 16; 0 + v2 = 16; v2 = 16

u2 + v2 = 8; 16 + u2 = 8; u2 = -8

u2 + v1 = 12; -8 + v1 = 12; v1 = 20

u1 + v3 = 20; 0 + v3 = 20; v3 = 20

u3 + v3 = 10; 20 + u3 = 10; u3 = -10

u3 + v4 = 8; -10 + v4 = 8; v4 = 18

v1=20 v2=16 v3=20 v4=18

u1=0 11 16[7] 20[9] 7

u2=-8 12[10] 8[13] 6 2

u3=-10 5 4 10[1] 8[20]

u4=- 0 0 0 0

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

Максимальная прибыль составит: F(x) = 16*7 + 20*9 + 12*10 + 8*13 + 10*1 + 8*20 = 686