Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf

дратом, а остальные кружками.

На рис. 14 представлен замкнутый контур, который был построен следующим образом: из клетки 3.5, где нарушены угловые оптимальности плана (см. табл. 39), мы провели пер­ вое звено контура, идущее вдоль третьей строки до занятой клетки 3.3 следующее звено построено между клетками 3.3 и 1.3. Третье звено построено между клетками 1.3 и 1.4, четвер­ тое между клетками 1.4 — 4.4, пятое — между клетками 4.4— 4.5 и, наконец, шестое—между клетками 4.5 и 3.5. При этом мы соблюдали условия, чтобы все вершины контура, кроме одной,, находились в занятых клетках, звенья располагались относительн'о друг друга под углом 90° и чтобы было четное число вершин.

+

Обход построенного контура начинаем с вершины, обозна­ ченной квадратом. В этой вершине ставим знак + , далее, сле­ дуя по направлению стрелок, в следующей вершине знак —г затем снова + и т. д. (знаки чередуются). У Каждой верши­ ны внизу ставим размер поставки.

Просматриваем вершины контура с отрицательными пока­ зателями. В нашем примере их три с размерами поставок

2,14 и 3.

Меньшую из них 2 отнимаем гот размеров поставок в от­ рицательных вершинах и прибавляем к размерам поставок в пМбжи'тельйкх ёе'ршинак, т. е. 0+2=ь2-, 14—2 —12, 8+ 2=10, 2—2= 0,31+2 = 33,3—2=1.

89

90

С помощью потенциалов исследуем на оптимальность каж-

Расчеты показали, что и этот план не является оптималь- 'ным: нарушено условие оптимальности в двух клетках — 4.1 и 4.2. Наиболее нарушены условия оптимальности в клетке 4.1.

Вновь строим замкнутый контур.

Причем начальную вершину контура помещаем в свобод­ ной клетке с наибольшим нарушением условия оптималь­ ности, т. е. в клетку 4.1 (рис. 15).

+

91

Новый план поставок с учетом перераспределения по кон­ туру представлен в табл. 40.

92

Полученные потенциалы проставлены в левой и верхней частях таблицы.

Проверка на оптимальность каждой свободной клетки по­ казала, что нарушения условия оптимальности нет. Отсюда ■следует, что получен оптимальный план поставок, по которо­ му суммарная стоимость перевозок составляетД=5• 8+13 • 1+ + 4 -15+12 • 2 + 3 •10+1 ■12+15" 33 + 8-3+ 6" 11 + 7 • 6= 806 еди­ ниц стоимости, что на 29 единиц стоимости меньше, чем по опор­ ному плану перевозок.

На рис. 16 представлена блок-схема алгоритма оптимиза­ ции плана перевозок по методу потенциалов.

Рис. 1G

Нам остается пояснить, что же такое потециал, какова его экономическая интерпретация.

Для каждой занятой клетки мы имеем ul + сtj = vL.

Это означает, что цена продукта в пункте производства и, плюс стоимость перевозки с,у- равна цене продукта в пункте потребления Vj. Это аналогично потенциалам в электротех­ нике, механике и гидравлике, так что можно построить элек­

93

трическую, механическую или гидравлическую модель, кото­ рая будет полностью соответствовать транспортной задаче.

Метод коэффициентов

Метод коэффициентов (в литературе часто называется ме­ тод МОДИ, или модифицированный распределительныйметод).

Этот метод аналогичен методу потенциалов, однако вместо

Первоначальный план перевозок устанавливаем одним из; известных нам методов. В данном случае этот план установ­ лен по минимальному элементу столбца.

Для проверки полученного плана на оптимальность опре­ деляем коэффициенты строк и столбцов.

Определение коэффициентов можно начинать с любойстроки или столбца, принимая в качестве начального коэффи­ циента любое произвольно выбранное число. Для упрощения рекомендуется вести расчет, начиная с первой строки, приняв; коэффициент этой строки равным нулю.

В дальнейшем, при определении коэффициентов, следует

94