ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.05.2024
Просмотров: 8
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 4*50 + 3*350 + 2*450 + 11*100 + 8*100 + 6*200 = 5250
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u2 + v2 = 11; 4 + u2 = 11; u2 = 7
u2 + v1 = 2; 7 + v1 = 2; v1 = -5
u3 + v2 = 8; 4 + u3 = 8; u3 = 4
u3 + v3 = 6; 4 + v3 = 6; v3 = 2
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
| | v1=-5 | v2=4 | v3=2 | v4=3 |
| u1=0 | 7 | 4[50] | 9 | 3[350] |
| u2=7 | 2[450] | 11[100] | 8 | 4 |
| u3=4 | 3 | 8[100] | 6[200] | 5 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 7 + 2 > 8; ∆23 = 7 + 2 - 8 = 1 > 0
(2;4): 7 + 3 > 4; ∆24 = 7 + 3 - 4 = 6 > 0
(3;4): 4 + 3 > 5; ∆34 = 4 + 3 - 5 = 2 > 0
max(1,6,2) = 6
Выбираем максимальную оценку свободной клетки (2;4): 4
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| | 1 | 2 | 3 | 4 | Запасы |
| 1 | 7 | 4[50][+] | 9 | 3[350][-] | 400 |
| 2 | 2[450] | 11[100][-] | 8 | 4[+] | 550 |
| 3 | 3 | 8[100] | 6[200] | 5 | 300 |
| Потребности | 450 | 250 | 200 | 350 | |
Цикл приведен в таблице (2,4 → 2,2 → 1,2 → 1,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| | B1 | B2 | B3 | B4 | Запасы |
| A1 | 7 | 4[150] | 9 | 3[250] | 400 |
| A2 | 2[450] | 11 | 8 | 4[100] | 550 |
| A3 | 3 | 8[100] | 6[200] | 5 | 300 |
| Потребности | 450 | 250 | 200 | 350 | |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u3 + v2 = 8; 4 + u3 = 8; u3 = 4
u3 + v3 = 6; 4 + v3 = 6; v3 = 2
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u2 + v4 = 4; 3 + u2 = 4; u2 = 1
u2 + v1 = 2; 1 + v1 = 2; v1 = 1
| | v1=1 | v2=4 | v3=2 | v4=3 |
| u1=0 | 7 | 4[150] | 9 | 3[250] |
| u2=1 | 2[450] | 11 | 8 | 4[100] |
| u3=4 | 3 | 8[100] | 6[200] | 5 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 4 + 1 > 3; ∆31 = 4 + 1 - 3 = 2 > 0
(3;4): 4 + 3 > 5; ∆34 = 4 + 3 - 5 = 2 > 0
max(2,2) = 2
Выбираем максимальную оценку свободной клетки (3;1): 3
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| | 1 | 2 | 3 | 4 | Запасы |
| 1 | 7 | 4[150][+] | 9 | 3[250][-] | 400 |
| 2 | 2[450][-] | 11 | 8 | 4[100][+] | 550 |
| 3 | 3[+] | 8[100][-] | 6[200] | 5 | 300 |
| Потребности | 450 | 250 | 200 | 350 | |
Цикл приведен в таблице (3,1 → 3,2 → 1,2 → 1,4 → 2,4 → 2,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| | B1 | B2 | B3 | B4 | Запасы |
| A1 | 7 | 4[250] | 9 | 3[150] | 400 |
| A2 | 2[350] | 11 | 8 | 4[200] | 550 |
| A3 | 3[100] | 8 | 6[200] | 5 | 300 |
| Потребности | 450 | 250 | 200 | 350 | |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u2 + v4 = 4; 3 + u2 = 4; u2 = 1
u2 + v1 = 2; 1 + v1 = 2; v1 = 1
u3 + v1 = 3; 1 + u3 = 3; u3 = 2
u3 + v3 = 6; 2 + v3 = 6; v3 = 4
| | v1=1 | v2=4 | v3=4 | v4=3 |
| u1=0 | 7 | 4[250] | 9 | 3[150] |
| u2=1 | 2[350] | 11 | 8 | 4[200] |
| u3=2 | 3[100] | 8 | 6[200] | 5 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 4*250 + 3*150 + 2*350 + 4*200 + 3*100 + 6*200 = 4450
Анализ оптимального плана.
Из 1-го поставщика необходимо груз направить в 2-й магазин (250 ед.), в 4-й магазин (150 ед.)
Из 2-го поставщика необходимо груз направить в 1-й магазин (350 ед.), в 4-й магазин (200 ед.)
Из 3-го поставщика необходимо груз направить в 1-й магазин (100 ед.), в 3-й магазин (200 ед.)
