Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


XЬ = 0 .    (23)


iel


Для каждой коммуникации заданы стоимость перевозки единицы продукта по ней cd и пропускная способность перевозки rd > 0, d е D — множество дуг графа.


Потоком называется совокупность перевозок по сети X={xd}, d е D, xd > 0, где xd — перевозка по коммуникации d.


Цель задачи — сформировать такой поток по сбалансированной сети, при котором разница между количеством вывозимого и ввозимого в каждый пункт продукта равна объему производства в нем, величины перевозок не превосходят пропускных способностей коммуникаций, а суммарные транспортные расходы минимальны, т.е.


X cdxd


(


min


(24)


V deD


Метод потенциалов. Для задачи в сетевой постановке суть метода потенциалов и алгоритм не меняются:


1)    построить начальный допустимый невырожденный поток по сети. Поток по транспортной сети является невырожденным, если имеет N-1 перевозок, где N — количество пунктов сети;


2)    проверить найденный поток на оптимальность:


•    рассчитать потенциалы вершин;


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


3)    если поток оптимален, то задача решена;


4)    если поток не оптимален, определить наибольшую «невязку» и коммуникацию, по кото


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


по сети;


5)    проверить новый поток на оптимальность и т.д. до получения оптимального решения.


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

Скачать в pdf «Экстремальные модели менеджмента и экономики»