Составление сметы на весь комплекс проектно-изыскательских работ по форме 2П. Модель транспортной задачи в аналитическом виде, страница 11

Определяется маршрут, исключаемый из базиса. С этой целью помечается так называемый цикл пересчета, представляющий собой замкнутую ломаную линию с углами поворота 90° или 270°. Начинаться и заканчиваться ломаная линия должна в клетке, соответствующей выбранному на шаге 2 маршруту, а все остальные углы поворота должны лежать в клетках, соответствующих базисным маршрутам.

После пометки цикла пересчета у вершин, начиная с вершины, соответствующей вновь выбранному маршруту, проставляются значки "+" или "-". Знаки вершин, начиная с положительного, чередуются при обходе ломанной по ходу часовой стрелки. По вновь выбранному маршруту направляется поток, величина которого равна минимальному из потоков, входящих в цикл пересчета и соответствующих отрицательным величинам.

В нашем случае цикл пересчета – 12, 32, 31, 11, 12 (табл. 3.12). Минимальный поток из входящих в цикл пересчета потоков, соответствующих отрицательным вершинам – это 4 (вершина 32).

Таблица 3.12

Z =2*2+4*3+1*0+5*5+0*8+3*15+2*9=104

Шаг 4.

Все потони по маршрутам, входящим в цикл пересчета, перераспределяются на величину, найденную на шаге 3, сообразно со знаком вершины. Контролем является сохранение баланса по строкам и столбцам.

В рассматриваемом примере после перераспределения потоков видно, что из базиса исключен маршрут 32, поток по которому стал нулевым, а включен маршрут 12, выбранный на шаге 2, так что количество базисных маршрутов не изменилось.

Подсчитывается значение целевой функции.

Этим заканчивается первая итерация, после чего следует перейти, к шагу 2 и т.д. до тех пор, пока не выяснится, что отсутствуют возможности улучшения плана перевозок, т.е. все оценки иди нулевые, или отрицательные. В этом случае достигается оптимальное решение, при котором целевая функция имеет минимальное значение.

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

Таблица 3.13

Исходные данные

I итерация