Начальный план перевозок

В процессе решения после каждой итерации (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение следующего условия;

(9.7)

В нашем примере т = 3, п = 4, а число загруженных клеток равно 6, т. е. соответствует условию (9.7): N = 3 + 4 — 1 =6. Если условие (9.7) не выполняется, план называется вырожденным. В этом случае в любые свободные клетки надо поставить столько ну­лей, чтобы с их учетом выполнялось условие (8.7). Клетка, в которой стоит ноль, считается занятой. Значение целевой функции по результатам расчета допустимого плана

д.е.

Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:

(9.8)

где — потенциал i-й строки;

- потенциал j-го столбца.

Вычисляя потенциалы по выражению (9.8), принимаем для пер­вой строки = 0. Используя загруженные клетки (i — j) = (1 — 1), (1 — 2). получаем:

Далее по загруженным клеткам (2 - 2), (2 - 3) определяем дру­гие потенциалы:

Проверяем план на оптимальность по незагруженным клеткам, используя следующее неравенство:

(9.9)

Если для незагруженных клеток условие (9.9) выполняется, то план - оптимальный! По табл. 9.3 осуществляем проверку началь­ного плана на оптимальность:

Итак, по трем клеткам условие (9.9) не выполняется, следова­тельно, начальный план требует улучшения. Характеристики показывают размер экономии транспортных издержек на 1 ед. пе­ревозимого груза. В нашем примере наибольшую экономию можно получить по клетке (i -j) = (3 - 1), где . Сле­довательно, клетку (3-1) необходимо загрузить за счет перераспре­деления ресурсов из других загруженных клеток. В табл. 9.3 клетку (3-1) помечаем знаком «+», так как здесь в начальном плане нахо­дится вершина максимальной неоптимальности.

Контур перераспределения ресурсов составляют по следующим. правилам:

• этот контур представляет замкнутый многоугольник с вершин ми в загруженных клетках, за исключением клетки с вершиной максимальной неоптимальности «+», и звеньями, лежащие вдоль строк и столбцов матрицы;

• ломаная линия должна быть связанной в том смысле, что из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной цепи (по строке или по столбцу);

• в каждой вершине контура встречаются только два звена, одно из них располагается по строке, другое — по столбцу;

• число вершин контура четное, все они в процессе перераспределения делятся на загружаемые и разгружаемые;

• в каждой строке (столбце) имеются две вершины: одна - загружаемая, другая — разгружаемая.

В этой клетке намечаем одну из вершин контура и далее по вышеизложенным правилам строим контур, вершины которого будут находиться в клетках (3-1) - (1-1) - (1-2) - (2-2) - (2-3) - (3-3). Вершины контура последовательно подразделяем нагружаемые (3) и разгружаемые (Р), начиная с вершины максимальной неоптимальности «+» (табл. 9.3).

Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных ни одно из этих значений не должно превра­титься в отрицательное число. Поэтому анализируют только клетки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере X_min = min{40;40; 40} = 40. Следовательно, клетки (1-1), (2-2), (3-3) полностью разгружаются. В клетке (1—2) загрузка увеличится на 40 и достигнет 60, в клетке (2-3) загрузка составит 40 + 40 = 80, и клетка (3—1) загрузится на 40 (табл. 8.4).

Проверяем условие N = т + п — I. В нашем примере т = 3, п = 4, а число загруженных клеток равно 4, т. е. условие не выполняется и 6 4. В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае следует в две клетки проставить нули (нулевой ресурс) и считать условно их загруженными. Например, в клетки (1 — 1) и (3—3) проставим нулевой ресурс (рис. 9.4). Получе­ние нового плана (итерации) осуществляется в том же порядке, ко­торый был рассмотрен выше, т. е.

• по загруженным клеткам (в соответствии с новой загрузкой) вы­числяются потенциалы и ;

• по незагруженным клеткам производится проверка плана на оп­тимальность;

• находится вершина максимальной неоптимальности и строится новый контур перераспределения, и т. д., до тех пор, пока не бу­дет найдено оптимальное решение, удовлетворяющее неравенст­ву (9.9).

По результатам первой итерации имеем

Ниже приведены расчеты по второй итерации и оптимальный план.

Поиск потенциалов следующий:

Проведём проверку на оптимальность:

Клетку (2—4) необходимо загрузить.

В соответствии с перераспределением ресурсов по контуру получаем табл. 9.5, для которой вновь рассчитываем потенциалы и последовательность вычислений повторяется.

Таблица 9.5