Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 1; 0 + v1 = 1; v1 = 1 u3 + v1 = 4; 1 + u3 = 4; u3 = 3 u1 + v2 = 2; 0 + v2 = 2; v2 = 2 u2 + v2 = 4; 2 + u2 = 4; u2 = 2 u2 + v3 = 3; 2 + v3 = 3; v3 = 1 u4 + v2 = 0; 2 + u4 = 0; u4 = -2 u4 + v4 = 0; -2 + v4 = 0; v4 = 2
v1=1 v2=2 v3=1 v4=2
u1=0 1[1] 2[4] 2 3
u2=2 5 4[19] 3[15] 7
u3=3 4[5] 6 7 8
u4=-2 0 0[11] 0 0[17]
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 1*1 + 2*4 + 4*19 + 3*15 + 4*5 + 0*11 + 0*17 = 150 Ответ: Из 1-го склада необходимо груз направить в 1-й магазин (1 ед.), в 2-й магазин (4 ед.) Из 2-го склада необходимо груз направить в 2-й магазин (19 ед.), в 3-й магазин (15 ед.) Из 3-го склада необходимо весь груз направить в 1-й магазин. Потребность 2-го магазина остается неудовлетворенной на 11 ед. Оптимальный план является вырожденным, так как базисная переменная x42=0. Потребность 4-го магазина остается неудовлетворенной на 17 ед. Оптимальный план является вырожденным, так как базисная переменная x44=0.
B1 B2 B3 Запасы
A1 4 2 2 100
A2 3 5 3 200
A3 9 3 6 70
Потребности 190 120 30
Нужно полное решение этой работы?
Решение
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 100 + 200 + 70 = 370 ∑b = 190 + 120 + 30 = 340 Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 30 (370—340). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю. Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 Запасы
A1 4 2 2 0 100
A2 3 5 3 0 200
A3 9 3 6 0 70
Потребности 190 120 30 30
Поиск первого опорного плана(метод наименьшей стоимости)
B1 B2 B3 B4 Запасы
A1 4 2[100] 2 0 100
A2 3[190] 5 3[10] 0 200
A3 9 3[20] 6[20] 0[30] 70
Потребности 190 120 30 30
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6
. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 2*100 + 3*190 + 3*10 + 3*20 + 6*20 + 0*30 = 980 Улучшение опорного плана( метод потенциалов)Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 2; 0 + v2 = 2; v2 = 2 u3 + v2 = 3; 2 + u3 = 3; u3 = 1 u3 + v3 = 6; 1 + v3 = 6; v3 = 5 u2 + v3 = 3; 5 + u2 = 3; u2 = -2 u2 + v1 = 3; -2 + v1 = 3; v1 = 5 u3 + v4 = 0; 1 + v4 = 0; v4 = -1
v1=5 v2=2 v3=5 v4=-1
u1=0 4 2[100] 2 0
u2=-2 3[190] 5 3[10] 0
u3=1 9 3[20] 6[20] 0[30]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;1): 0 + 5 > 4; ∆11 = 0 + 5 - 4 = 1 > 0 (1;3): 0 + 5 > 2; ∆13 = 0 + 5 - 2 = 3 > 0 max(1,3) = 3 Выбираем максимальную оценку свободной клетки (1;3): 2 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 4 2[100][-] 2[+] 0 100
2 3[190] 5 3[10] 0 200
3 9 3[20][+] 6[20][-] 0[30] 70
Потребности 190 120 30 30
Цикл приведен в таблице (1,3 → 1,2 → 3,2 → 3,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Заказать работу
на новый заказ в Автор24.
