Главная Учебники - Разные Лекции (разные) - часть 33
Пункт назначения Пункт отправления 1 2 3 4 Запасы 1 1 7 3 6 21 2 7 1 1 4 26 3 3 3 7 3 25 4 1 3 5 5 24 Потребности 25 19 24 28 S = 96 Сущность его состоит в следующем. Будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клетки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1; 1) занесем меньшее из чисел a 1, b 1, т.е. x 11 =min (a 1, b 1). Если а 1 >b 1, то x 11 =b 1 и первый потребитель В 1 будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принимается; в нем переменные. Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел (a 1 - b 1) и b 2, т.е. x 12 = min ((a 1 - b 1), b 2). Если (a 1 - b 1) <b 2, то запасы первого поставщика исчерпаны и первая строка таблицы в дальнейшем в расчет не принимается. Переходим к аналогичному распределению запаса груза второго поставщика. Если b 1 >a 1 то х 11 =min (a 1, b 1) =а 1. При этом запас первого поставщика будет исчерпан, а потому. Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2; 1) заносим наименьшее из чисел (a 2, b 1 - а 1). Заполнив таким образом клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по второй, третьей и последующим строкам (столбцам) производится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы. Ai* - излишек нераспределенного груза от поставщика Ai Bj* - недостача в поставке груза потребителю Bj Помещаем в клетку (1,1) меньшее из чисел A1*=21 и B1*=25 Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,1) меньшее из чисел A2*=26 и B1*=4 Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,2) меньшее из чисел A2*=22 и B2*=19 Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A2*=3 и B3*=24 Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку (3,3) меньшее из чисел A3*=25 и B3*=21 Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшем в расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A3*=4 и B4*=28 Так как запасы поставщика A3 исчерпаны, то строка 3 в дальнейшем в расчет не принимается Помещаем в клетку (4,4) меньшее из чисел A4*=24 и B4*=24 Пункт назначения Пункт отправления 1 2 3 4 Запасы 1 1 21 7 - 3 - 6 - 21 2 7 4 1 19 1 3 4 - 26 3 3 - 3 - 7 21 3 4 25 4 1 - 3 - 5 - 5 24 24 Потребности 25 19 24 28 S = 96 Стоимость перевозок Z = 1×21+4×7+1×19+1×3+7×21+3×4+5×24 = 350 Допустимый план методом северо-западного угла Алгоритм состоит из двух шагов: Предварительный шаг Общеповторяющийся шаг Предварительный шаг: Находим допустимый ациклический план. Составляем систему потенциалов. Анализируем систему на потенциальность. Общеповторяющийся шаг: Положительные разности Означиваем цикл. Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи. Из перевозок в каждой клетке отрицательной полуцепи вычитаем Q, а к положительным перевозка прибавляется. Эта операция – сдвиг по циклу на величину Q. Пересчитываем систему потенциалов. Проверяем систему на потенциальность. Если система не потенциальна, то переходим к пункту 1 общеповторяющегося шага. Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1. . m, j=1. . n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 V1=C1,1-U1= 1 U2=C1,2-V1= 6 V2=C2,2-U2= - 5 V3=C2,3-U2= - 5 U3=C3,3-V3= 12 V4=C3,4-U3= - 9 U4=C4,4-V4= 14 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток S1,2 = c1,2 - (u1 + v2) = 12. S1,3 = c1,3 - (u1 + v3) = 8. S1,4 = c1,4 - (u1 + v4) = 15. S2,4 = c2,4 - (u2 + v4) = 7. S3,1 = c3,1 - (u3 + v1) = - 10. S3,2 = c3,2 - (u3 + v2) = - 4. S4,1 = c4,1 - (u4 + v1) = - 14. S4,2 = c4,2 - (u4 + v2) = - 6. S4,3 = c4,3 - (u4 + v3) = - 4. B1 B2 B3 B4 A1 12 8 15 A2 7 A3 -10 -4 A4 -14 -6 -4 Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (4,1). Для нее оценка равна - 14. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус". Поставщик Потребитель Запасы груза B1 B2 B3 B4 A1 1 21 7 3 6 21 A2 - 7 4 1 19 + 1 3 4 26 A3 3 3 - 7 21 + 3 4 25 A4 + 1 3 5 - 5 24 24 Потребность 25 19 24 28 Делаем сдвиг по циклу на 4, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план: Поставщик Потребитель Запасы груза B1 B2 B3 B4 A1 1 21 7 3 6 21 A2 7 1 19 1 7 4 26 A3 3 3 7 17 3 8 25 A4 1 4 3 5 5 20 24 Потребность 25 19 24 28 Стоимость перевозок Z = 294 Значение целевой функции изменилось на 56 единиц по сравнению с предыдущим этапом. Этап 2 Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1. . m, j=1. . n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 V1=C1,1-U1= 1 U4=C1,4-V1= 0 V4=C4,4-U4= 5 U3=C4,3-V4= - 2 V3=C3,3-U3= 9 U2=C3,2-V3= - 8 V2=C2,2-U2= 9 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток S1,2 = c1,2 - (u1 + v2) = - 2. S1,3 = c1,3 - (u1 + v3) = - 6. S1,4 = c1,4 - (u1 + v4) = 1. S2,1 = c2,1 - (u2 + v1) = 14. S2,4 = c2,4 - (u2 + v4) = 7. S3,1 = c3,1 - (u3 + v1) = 4. S3,2 = c3,2 - (u3 + v2) = - 4. S4,2 = c4,2 - (u4 + v2) = - 6. S4,3 = c4,3 - (u4 + v3) = - 4. B1 B2 B3 B4 A1 -2 -6 1 A2 14 7 A3 4 -4 A4 -6 -4 Поставщик Потребитель Запасы груза B1 B2 B3 B4 A1 - 1 21 7 + 3 6 21 A2 7 1 19 1 7 4 26 A3 3 3 - 7 17 + 3 8 25 A4 + 1 4 3 5 - 5 20 24 Потребность 25 19 24 28 Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,3). Для нее оценка равна - 6. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус". Делаем сдвиг по циклу на величину перевозок в 17 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план: Поставщик Потребитель Запасы груза B1 B2 B3 B4 A1 1 4 7 3 17 6 21 A2 7 1 19 1 7 4 26 A3 3 3 7 3 25 25 A4 1 21 3 5 5 3 24 Потребность 25 19 24 28 Стоимость перевозок Z= 192 Значение целевой функции изменилось на 102 единиц по сравнению с предыдущим этапом. Этап 3 Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1. . m, j=1. . n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 V1=C1,1-U1= 1 V3=C1,3-U1= 3 U4=C1,4-V1= 0 U2=C3,2-V3= - 2 V2=C2,2-U2= 3 V4=C4,4-U4= 5 U3=C4,3-V4= - 2 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток S1,2 = c1,2 - (u1 + v2) = 4. S1,4 = c1,4 - (u1 + v4) = 1. S2,1 = c2,1 - (u2 + v1) = 8. S2,4 = c2,4 - (u2 + v4) = 1. S3,1 = c3,1 - (u3 + v1) = 4. S3,2 = c3,2 - (u3 + v2) = 2. S3,3 = c3,3 - (u3 + v3) = 6. S4,2 = c4,2 - (u4 + v2) = 0. S4,3 = c4,3 - (u4 + v3) = 2. B1 B2 B3 B4 A1 4 1 A2 8 1 A3 4 2 6 A4 0 2 Так как все оценки Si,j>=0, то полученный план является оптимальным. Транспортная задача решена. Поставщик Потребитель Запасы груза B1 B2 B3 B4 A1 1 4 7 3 17 6 21 A2 7 1 19 1 7 4 26 A3 3 3 7 3 25 25 A4 1 21 3 5 5 3 24 Потребность 25 19 24 28 Стоимость перевозок F= 192 Метод минимального элемента 1111 33333 4 55 6 777 Пункт назначения Пункт отправления 1 2 3 4 Запасы 1 1 21 7 - 3 - 6 - 21 2 7 - 1 19 1 7 4 - 26 3 3 - 3 - 7 - 3 25 25 4 1 4 3 - 5 17 5 3 |