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

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


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


Решение транспортной задачи методом потенциалов начинают с отыскания начального допустимого базисного решения или первоначального опорного плана задачи, аналогично симплексметоду (НДБР).


НДБР транспортной задачи можно получить разными методами, такими как методом «северозападного угла», методом наименьшего элемента, методом Фогеля. Метод «северо-западного угла» или «северо-запад-юго-восток» наиболее распространен, особенно для задач большой размерности. Остальные методы могут дать существенное преимущество только для задач небольшой размерности. Однако выбор метода отыскания НДБР не может повлиять на оптимальный план задачи.


Метод северо-западного угла состоит из однотипных шагов, на каждом из которых максимально удовлетворяется спрос потребителей за счет возможностей производителей, причем из рассмотрения исключается один поставщик и один потребитель:


•    если остаток продукта у i-го поставщика после предыдущих шагов меньше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения i-й поставщик и в клетку (i j) заносится поставка xj, равная остатку продукта у i-го поставщика после предыдущих шагов;


•    если остаток продукта у i-го поставщика после предыдущих шагов больше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения j-й потребитель и в клетку (i j) заносится поставка Х/, равная неудовлетворенному запросу j-го потребителя;


•    если остаток продукта у i-го поставщика после предыдущих шагов равен неудовлетворенному запросу j-го потребителя, то исключается из рассмотрения или i-й поставщик, или j-й потребитель.


Когда начальное допустимое решение задачи найдено (при помощи одного из перечисленных методов), начинают вычисление потенциалов.


Каждому    поставщику    ставится    в    соответствие    потенциал

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