Решение задач методом северо-западного угла, рапределительного, минимального и максимального элемента по строке
7 |
Пункт назначения Пункт отправления | 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 | = 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* - излишек нераспределенного груза от поставщика AiBj* - недостача в поставке груза потребителю 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 | = 96 | | |
Стоимость перевозок Z = 121+47+119+13+721+34+524 = 350 Допустимый план методом северо-западного угла Алгоритм состоит из двух шагов: Предварительный шаг Общеповторяющийся шаг Предварительный шаг: Находим допустимый ациклический план. Составляем систему потенциалов. Анализируем систему на потенциальность. Общеповторяющийся шаг: Положительные разности , находим наибольшую, включаем эту клетку в набор и строим на ней цикл. Означиваем цикл. Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи. Из перевозок в каждой клетке отрицательной полуцепи вычитаем , а к положительным перевозка прибавляется. Эта операция - сдвиг по циклу на величину . Пересчитываем систему потенциалов. Проверяем систему на потенциальность. Если система не потенциальна, то переходим к пункту 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 | | | |
Страницы: 1, 2
|
