Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

Следует отметить, что система записи при построении опорного плана может быть упрощена и сведена в одну табличную форму, каждая угловая запись в которой соответствует одному шагу по­ строения плана. Применительно к полученному опорному плану эта запись выглядела бы следующим образом:

Полученный опорный план лишь случайно может оказаться оп­ тимальным, а в общем случае требует своего улучшения до построе­ ния оптимального плана перевозок. Так как при построении опор­ ного плана методом северо-западного угла не учитываются стои­ мостные характеристики перевозок сц, трудно рассчитывать на то, что значение линейной формы (целевой функции) для него будет близко к минимальному. Поэтому число итераций для оптимиза­ ции плана может быть значительным, особенно при больших зна­ чениях п я т (число потребителей и число поставщиков).

Существует ряд методов получения опорного плана, обеспечи­ вающих в некоторых случаях уменьшение числа итераций для по­ строения оптимального плана. Используем один из них (метод «минимума по строке») при решении нашей задачи. В первой стро­

получим вспомогательную таблицу-матрицу:

В первой строке табл. 17 наименьшей после Сц стоимостной ха­ рактеристикой перевозки является Ci3 = 0,30. На 2-м шаге примем

76

Xi3=m in [ («i—bA)\ 6 3]. Тогда *i3 = ai— 6 4 = 2. При этом *ц = 0 и *[2=

Переходя ко второй строке табл. 17, найдем, что минимальное значение Cij есть с24 = 0. Однако после 1-го шага значение * 24 = 0

уже определилось. Следующее, меньшее значение c,-j во второй строке табл. 17 c2i = 0,5. Примем поэтому *2 i = min(a2 ; Ь\)\ в нашем

случае Xzi = b\ = b. Вспомогательная таблица-матрица после 3-го шага следующая:

Поступая аналогично, примем x2 3 = m in{(a2 — b\ ) ; \ЬЪ— {а^ —6 4)]},

т. е. х2з= Ь3— (ai—Ь4) =2. Тогда после 4-го шага будем иметь сле­ дующую таблицу-матрицу:

77

Вычислим значения целевой функции для опорных планов, по­ строенных обоими методами. Для опорного плана, построенного по методу северо-западного угла, получим:

Для опорного плана, построенного по методу «минимума по строке», получим:

£ = 0,80 -0+ 0,60 -0 + 0 ,3 0 -2 + 0 -2 + 0 ,5 0 -5 + 1,0-3 +

+ 0,75-2 + 0-0 = 7,60.

Таким образом, опорный план, построенный по методу «миниму­ ма по строке», обусловливает меньшие значения целевой функции и потребует для своей оптимизации меньшего числа итераций.

Для оптимизации последнего опорного плана воспользуемся ме­ тодом потенциалов. Суть метода состоит в том, что каждая итера­ ция, приближающая исходный (опорный) план к оптимальному, состоит из двух этапов. На первом этапе план, полученный в ре­ зультате предыдущей итерации, проверяется на оптимальность. Если он оказался неоптимальным, то на втором этапе строится но­ вый план, обусловливающий меньшие транспортные перевозки по сравнению с предыдущим планом.

Рассмотрим на примере нашей задачи, как осуществляются оба упомянутых этапа для каждой из итераций улучшения плана пере­ возок. Первичный опорный план содержал величины хц для всех возможных в условиях задачи перевозок. В методе потенциалов доказывается, что для любого опорного плана могут быть найдены такие числа Ui и Vj, при которых для всех переменных хц опорного плана имеет место равенство

то опорный план является оптимальным.

Проверим вначале на первом этапе анализа по методу потенциа­ лов, не является ли опорный план, полученный ранее по методу минимума в строке, оптимальным. Составим для него систему урав­ нений типа равенства (V.26).

Каждое из уравнений этой системы должно быть записано для значений хц, входящих в опорный план, т. е. для х13, хц, x2i, *22 , Хгз-

78

(J2-]-V1 — C2i=0,5',

В данной системе из пяти уравнений мы имеем шесть неиз­ вестных.

Система является неопределенной и имеет бесчисленное мно­ жество решений. Возьмем поэтому произвольно значение одного из неизвестных для того, чтобы получить решение системы. Примем,

в частности, £/i = Ch = 0. Тогда Уз= 0,3; 1^4 = 0; U2 = 0,45; У2=0,55;

У, = 0,05.

Внесем полученные значения £/, и V, в табл. 18, в которой по­ лужирным шрифтом выделены суммы Ui + Vj = cn для переменных, входящих в опорный план. В остальных клетках таблицы сосчита­ ны величины U i+V j = ca для переменных, не входящих в опорный план, т. е. для хц, хц и л:24.

Второй этап действий по методу потенциалов состоит в улучше­ нии плана предыдущей итерации. Для ввода в новый план выбира­ ется именно та переменная хц, для которой имела место разность са—Cij>0. Если бы таких разностей было несколько, то следовало бы в новый опорный план ввести ту переменную хц, для которой стоимость перевозок сц имеет меньшее значение. В нашей задаче в новый опорный план мы должны ввести переменную х24. Обра­ тившись к исходному опорному плану, введем в него перевозку х24 с некоторой интенсивностью 0Ь причем 01^0. Соответствующая матрица примет вид:

79