Содержание1. Распределительный метод решения транспортной задачи 3
Литература 16ВведениеДанный метод состоит в последовательном улучшении опорного плана перевозок путем отыскания на каждом шаге выгодных циклов переноса грузов. Опорный план для данного метода (как и для других методов решения транспортной задачи методом потенциалов) можно сформировать, применяя метод "северо-западного" угла.
Более подробно рассмотрим теперь процесс формирования очередного цикла переноса на каждом новом шаге алгоритма.
Очевидно, что при перемещении х единиц груза по некоторому циклу с ценой стоимость перевозок изменяется на величину х .
Тогда, для улучшения текущего плана перевозок имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна.
Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что оптимальный план достигнут.
При улучшении плана циклическими переносами пользуются приемом, заимствованным из симплекс-метода: на каждом шаге (цикле) заменяют одну свободную переменную на базисную, т.е. заполняют одну клетку и взамен того освобождают одну из базисных клеток.
Можно доказать, что для любой свободной клетки транспортной таблицы всегда существует цикл (и притом единственный), одна из вершин которого лежит в этой клетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободной клетке, отрицательна, то план можно улучшить. Количество единиц груза (х), которые можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла. [3]Литература1. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. - М.: ДИС, 1997.
2. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Мн., Вышэйшая школа, 1994.
3. Кузнецов А.В., Холод Н.И. Математическое программирование. - Мн., Вышэйшая школа, 1984.
4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: Высшая школа, 1980.
5. Экономико-математические методы и модели / Под редакцией Кузнецова А.В. - Мн.: Вышэйшая школа, 1999.
|