Возвращаемся к плану №7
Для получения невырожденного плана принудительно добавляем нуль [0] в клетку (1;3);
| 11[10] | 16[6] | 20[0] | ||
| 8[3] | 2[20] | |||
| 4[11] | 10[10] | |||
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 11; 0 + v1 = 11; v1 = 11
u1 + v2 = 16; 0 + v2 = 16; v2 = 16
u2 + v2 = 8; 16 + u2 = 8; u2 = -8
u2 + v4 = 2; -8 + v4 = 2; v4 = 10
u3 + v2 = 4; 16 + u3 = 4; u3 = -12
u3 + v3 = 10; -12 + v3 = 10; v3 = 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=- |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): -8 + 11 < 12; ∆21 = -8 + 11 - 12 = -9
(3;1): -12 + 11 < 5; ∆31 = -12 + 11 - 5 = -6
(3;4): -12 + 10 < 8; ∆34 = -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] | ||||
| Потребности |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 11; 0 + v1 = 11; v1 = 11
u1 + v2 = 16; 0 + v2 = 16; v2 = 16
u2 + v2 = 8; 16 + u2 = 8; u2 = -8
u2 + v4 = 2; -8 + v4 = 2; v4 = 10
u3 + v4 = 8; 10 + u3 = 8; u3 = -2
u3 + v3 = 10; -2 + v3 = 10; v3 = 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=- |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 12 < 20; ∆13 = 0 + 12 - 20 = -8
(2;1): -8 + 11 < 12; ∆21 = -8 + 11 - 12 = -9
(2;3): -8 + 12 < 6; ∆23 = -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] | ||||
| Потребности |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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
u2 + v4 = 2; -8 + v4 = 2; v4 = 10
u3 + v4 = 8; 10 + u3 = 8; u3 = -2
u3 + v3 = 10; -2 + v3 = 10; v3 = 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=- |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 12 < 20; ∆13 = 0 + 12 - 20 = -8
(2;3): -8 + 12 < 6; ∆23 = -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] | ||||
| Потребности |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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 | 16[7] | 20[9] | ||
| u2=-8 | 12[10] | 8[13] | ||
| u3=-10 | 10[1] | 8[20] | ||
| u4=- |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Максимальная прибыль составит: 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
