183762 (584788), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

2) Метод потенциалов

Примем некоторые обозначения: i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей X_i,j - перевозка между поставщиком A_i и потребителем B_j.

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу северо-западного угла: Введем некоторые обозначения: A_i^* - излишек нераспределенного груза от поставщика A_i B_j^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1,1) меньшее из чисел A₁^*=370 и B₁^*=300 Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается Помещаем в клетку (1,2) меньшее из чисел A₁^*=70 и B₂^*=280 Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,2) меньшее из чисел A₂^*=450 и B₂^*=210 Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A₂^*=240 и B₃^*=330 Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку (3,3) меньшее из чисел A₃^*=480 и B₃^*=90 Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A₃^*=390 и B₄^*=290 Так как спрос потребителя B₄ удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем в клетку (3,5) меньшее из чисел A₃^*=100 и B₅^*=100

Целевая функция F=11320

Решаем задачу методом потенциалов:

Этап 1

Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы U_i, V_j: U₁=0 V₁=C_1,1-U₁= 14 V₂=C_1,2-U₁= 8 U₂=C_2,2-V₂= 2 V₃=C_2,3-U₂= 5 U₃=C_3,3-V₃= 3 V₄=C_3,4-U₃= 1 V₅=C_3,5-U₃= 6 Определяем значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток (неоптимальные выделены красным цветом) S_1,3 = c_1,3 - (u₁ + v₃) = 12. S_1,4 = c_1,4 - (u₁ + v₄) = 4. S_1,5 = c_1,5 - (u₁ + v₅) = -3. S_2,1 = c_2,1 - (u₂ + v₁) = 5. S_2,4 = c_2,4 - (u₂ + v₄) = 8. S_2,5 = c_2,5 - (u₂ + v₅) = -2. S_3,1 = c_3,1 - (u₃ + v₁) = -14. S_3,2 = c_3,2 - (u₃ + v₂) = -6. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,1). Для нее оценка равна -14. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Перемещаем по циклу груз величиной в 90 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Целевая функция F= 10060

Характеристики

Список файлов ответов (шпаргалок)