Торговая компания "ОптТранс Сервис" - Присвоение потенциалов

2. Присвоение потенциалов потребителям и поставщикам. Како-му-либо поставщику или потребителю присваивают произвольный
потенциал (число одного порядка с максимальной величиной Сц в матрице). В рассматриваемом примере потенциал 12 присвоен второму поставщику. Затем определяют потенциалы остальных поставщиков Ui и потребителей y,:u,=y,-C,,, y;=Ui+C,-/, если jc,;0, т. е. по занятым клеткам. Например, потенциал третьего потребителя y3-2+C23=12+3=15, потенциал первого поставщика щ = =Уз—Ci3= 15—5= 10 и т. д.
3. Проверка по всем незанятым клеткам соблюдения условия Vj-Ui LCij. Если это условие соблюдается по всем незанятым (незаполненным) клеткам, то задача решена, т. е. план оптимальный. При наличии нарушений этого условия находят наибольшую величину нарушения Нц=таху;—щ—С при условии, что ,,0 и
переходят к п. 4.
В примере (табл. 19.1) имеется нарушение этого условия только
в клетке 3—2: Я:12=13—8—4=1.
4. Построение замкнутого контура по занятым клеткам. Из клетки с нарушением проводим ломаную линию, заканчивающуюся в этой же клетке, т. е. строим замкнутый контур, двигаясь аналогично ходу шахматной ладьи. При этом направление движения меняется под прямым углом только в занятых клетках (см. табл. 19.1). Там, где ломаная линия меняет направление (делает поворот), объем поставок xi) подлежит изменению. В примере ломаная линия проходит по клеткам: 3—2 2—2 2—3 1—3 1—5 3—5 3—2.
5. Нумерация клеток контура. В замкнутом контуре последовательно нумеруют все клетки контура, в которых ломаная линия меняет направление, начиная с клетки с нарушением. В таблице нумерация показана цифрами в скобках.
6. Определение изменения объемов поставок. Из всех клеток контура, получивших четные номера, выбирают клетку с минимальным значением хц. В нашем примере наименьшее значение хц из клеток с четными номерами равно 19.
7. Исправление плана прикрепления. Во всех клетках контура с четными номерами уменьшаем объемы поставок Хц на величину минимального из них, а во всех клетках контура с нечетными номерами объемы поставок хц увеличиваем на эту величину. Далее переходим к п. 2.
В нашем примере объемы поставок в клетках 2—2, 1—3 и 3—5 уменьшаем на 19 ед., а в клетках 3—2, 2—3 и 1—5 увеличиваем на столько же. В результате получаем новый и, как показали дальнейшие расчеты, оптимальный план прикрепления