Автор работы: Пользователь скрыл имя, 21 Мая 2013 в 08:02, курсовая работа
Транспортная задача (ТЗ) является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. ТЗ является одной из наиболее распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.
Речь идет о задачах, в которых нельзя перевозить груз из некоторых пунктов отправления Ai в некоторые пункты назначения Bj. В этом случае стоимости соответствующих перевозок полагаем равными достаточно большому числу. Тогда при отыскании оптимального плана соответствующие перевозки будут блокированы.
Иногда приходится решать транспортную задачу, в которой дополнительным условием в ограничениях является обязательное обеспечение конкретных перевозок по определенным маршрутам. В этом случае каждую обязательную перевозку xij=dij реализуем условно, уменьшая на dij запасы в Ai и потребности в Bj. Если это не удается сделать, то исходная задача не имеет решения. В противном случае стоимости обязательных поставок полагаем равными достаточно большому числу, решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной задачи.
Пусть требуется решить транспортную задачу, в которой некоторые из перевозок ограничены снизу xij pij. Организуем условные перевозки, уменьшив на pij запасы в Ai и потребности в Bj. Если это сделать не удается, то исходная задача решения не имеет, в противном случае решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной транспортной задачи.