ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 29.04.2024
Просмотров: 14
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Для этого в перспективную клетку (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
Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).
G = 0·400 + 1·550 + 2·300 + 1·450 + 4·250 + 4·200 + 3·350 = 4450
Ответ:
Из 1-го поставщика необходимо груз направить к 2-у потребителю (250 ед.), к 4-у потребителю (150 ед.)
Из 2-го поставщика необходимо груз направить к 1-у потребителю (350 ед.), к 4-у потребителю (200 ед.)
Из 3-го поставщика необходимо груз направить к 1-у потребителю (100 ед.), к 3-у потребителю (200 ед.)
