Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы

Построить опорный план по одному из правил.

Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m+n-1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.

Проверка плана на оптимальность.

3.1. Определение потенциалов поставщиков и потребителей. Для всех занятых клеток рассчитываются потенциалы по формуле

(3.8)

Где ui - потенциалы поставщиков (строк), vj - потенциалы потребителей (столбцов).

Так как всех занятых клеток должно быть m+n-1, т. е. на единицу меньше числа потенциалов (их m+n), то для определения чисел ui, vj необходимо решить систему из m+n-1 уравнений ui+vj=cij c m+n неизвестными. Система неопределенная, и, чтобы найти частные решения, одному из потенциалов придают произвольное числовое значение (обычно полагают u1=0), тогда остальные потенциалы определяются однозначно.

3.2. Для всех свободных клеток рассчитываются оценки по формуле

) (3.9)

Здесь - реальные тарифы, а - косвенные тарифы.

Если все sто полученный план является оптимальным. При этом, если все sij>0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка sij=0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции. Если хотя бы для одной свободной клетки, то план может быть улучшен. Переход к шагу 4.

4. Среди отрицательных оценок выбирается минимальная. Например, для клеток (i, j) и (k, l) имеем оценки: sij=-2, skl=-4. В этом случае наиболее потенциальной (перспективной) является клетка (k, l). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза. Так, от загрузки клетки (i, j) единицей груза транспортные расходы уменьшаются на денежных единиц, а от загрузки единицей груза клетки (k, l) - на денежных единиц. Эффективность плана от загрузки потенциальной клетки грузом в единиц составит денежных единиц.

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

5. В вершинах цепи, чередуя проставляются знаки "+" и "-", начиная с выбранной свободной клетки (в нее помещают знак "+"). В клетках со знаком "-" выбирается минимальная поставка (, которая перераспределяется по цепи: там, где стоит знак "+" она прибавляется, а где "-" - отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится занятой, а клетка в которой выбрана минимальная поставка - свободной (рис.3.1 а, б)

а) б)

+ - 20 20

40

- + 80

20 60

Рис.3.1

Может случится, что найденное наименьшее число ( одинаково для нескольких клеток цепи, помеченных знаком "-" (рис.3.2а). В этом случае во всех таких клетках (с минимальными стоимостями), кроме одной, нужно оставить нулевые (фиктивные) поставки (рис.3.2б).

а) б)

+ 4 - 3 33

20 20

- + 10 30

30 10

- 2 + 0 60

20 40

Рис.3.2

Составляется новый план, рассчитывается значение целевой функции. Переходим к шагу 2.

Похожие статьи




Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы

Предыдущая | Следующая