|
p align="left">Стоимость перевозок 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 | 24 | | Потребности | 25 | 19 | 24 | 28 | = 96 | | |
Z = 122+119+17+325+14+517+53=226, в методе северо-западного угла стоимость перевозки была выше и составляла 350. Распределительный методРаспределительный метод представляет собой набор следующих действий: вначале строится исходный опорный план перевозок по одному из вышеизложенных правил, а затем последовательно производится его улучшение до получения оптимального. Для этого для каждой свободной клетки строят замкнутый цикл. Если в матрице перевозок содержится опорный план, то для каждой свободной клетки можно образовать и притом только один замкнутый цикл, содержащий эту свободную клетку и некоторую часть занятыx клеток. Тарифы в клетках, находящихся в нечетных вершинах цикла, берем со знаком плюс, а в четных - со знаком минус. По каждому циклу подсчитываем алгебраическую сумму S ij тарифов. Если замкнутый цикл имеет вид: (i, j) - >(k, j) - >(k, l) - >(t, l) - >... ->(u, v) - >(i, v), то S ij =C ij - C kj + C kl - C tl +... + C uv - C iv, где (i,j) - свободная клетка. Если алгебраическая сумма S ij отрицательна, то путем изменения значений, стоящих в клетках замкнутого цикла, можно получить план с меньшим значением целевой функции. Критерием оптимальности при нахождении минимума функции служит неотрицательность алгебраических сумм S ij. Если указанное требование не соблюдено, план не оптимален и подлежит улучшению. Вычисления при решении транспортной задачи распределительным методом ведутся по следующему алгоритму: исходные данные задачи располагают в распределительной таблице; строят исходный опорный план по правилу "северо-западного угла", или по правилу "минимального элемента", или методом Фогеля; при этом должны оказаться занятыми r=m+n-1 клеток. Однако, если опорный план является вырожденным, то это условие не соблюдается. Для сохранения числа занятых клеток r=m+n-1 неизменным проделывают следующие шаги: в таблице отыскивают клетку, имеющую минимальный тариф и не образующую цикла с занятыми клетками, помещают в нее базисный нуль и считают ее в дальнейшем занятой. Процесс поиска таких клеток продолжается до тех пор, пока число занятых клеток не станет равным m+n-1; производят оценку первой свободной клетки путем построения замкнутого цикла и вычисления по этому циклу величины S ij. Если S ij <0, то переходят к следующему пункту алгоритма; перемещают по циклу количество груза, равное наименьшему из чисел, размещенных в четных клетках цикла (в клетках со знаком минус). Далее возвращаются к пункту с. Если S ij >=0, то оценивают следующую свободную клетку, и т.д., пока не обнаружат клетку с отрицательной оценкой. Среди всех клеток с oценкой меньше нуля нужно найти клетку с наибольшим нарушением оптимальности, т.е. клетку с наименьшей оценкой. Если, наконец, оценки всех свободных клеток окажутся неотрицательными, то оптимальное решение найдено. |
Пункт назначения Пункт отправления | 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 | 24 | | Потребности | 25 | 19 | 24 | 28 | = 96 | | |
(1,2) = c1,2-c1,1+c4,1-c4,3+c2,3-c2,2 = 2 (1,3) = c1,3-c1,1+c4,1-c4,3 = - 2 (1,4) = c1,4-c1,1+c4,1-c4,4 = 1 (2,1) = c2,1-c2,3+c4,3-c4,1 = 10 (2,4) = c2,4-c2,3+c4,3-c4,4 = 3 (3,1) = c3,1-c3,4+c4,4-c4,1 = 4 (3,2) = c3,2-c3,4+c4,4-c4,3+c2,3-c2,2 = 0 (3,3) = c3,3-c3,4+c4,4-c4,3 = 4 (4,2) = c4,2-c4,3+c2,3-c2,2 = - 2 наименьшая перевозка 17, делаем сдвиг |
Пункт назначения Пункт отправления | 1 | 2 | 3 | 4 | Запасы | | 1 | 1 4 | 7 - | 3 17 | 6 - | 21 | | 2 | 7 - | 1 19 | 1 7 | 4 - | 26 | | 3 | 3 - | 3 - | 7 - | 3 25 | 25 | | 4 | 1 21 | 3 - | 5 - | 5 3 | 24 | | Потребности | 25 | 19 | 24 | 28 | = 96 | | |
(1,2) = c1,2-c1,3+c2,3-c2,2 = 4 (1,4) = c1,4-c1,1+c4,1-c4,4 = 1 (2,1) = c2,1-c2,3+c1,3-c1,1 = 8 (2,4) = c2,4-c2,3+c1,3-c1,1+c4,1-c4,4 = 1 (3,1) = c3,1-c3,4+c4,4-c4,1 = 4 (3,2) = c3,2-c3,4+c4,4-c4,1+c1,1-c1,3+c2,3-c2,2 = 2 (3,3) = c3,3-c3,4+c4,4-c4,1+c1,1-c1,3 = 6 (4,2) = c4,2-c4,1+c1,1-c1,3+c2,3-c2,2 = 0 (4,3) = c4,3-c4,1+c1,1-c1,3 = 2 Оптимальный план получившийся распределительным методом, аналогичен оптимальному плану, получившемуся методом потенциалов
Страницы: 1, 2
|
