Транспортная задача линейного программирования

Транспортные задачи являются особой разновидностью задач линейного программирования и в отношении постановки и в отношении методов решения.

Типичная постановка задачи линейного программирования выглядит следующим образом.

- Существует «N» производителей некоторой продукции, причем их мощности по производству этой продукции заданы в виде вектора . Также существует «M» потребителей той же продукции, причем их потребности в продукции заданы в виде вектора .

- Задана матрица стоимости перевозок единицы груза от каждого производителя каждому потребителю.

- Требуется найти такой план перевозок, при котором суммарная стоимость всех перевозок от производителей к потребителям была бы минимальной.

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

Для открытой транспортной задачи возможны два подварианта.

А) Суммарная мощность всех производителей меньше суммарной потребности всех потребителей. В этом случае для части (или всех) потребителей объемы поставок будут несколько ниже, чем их потребности (в отдельных случаях объемы поставок могут даже быть нулевые).

Б) Суммарная мощность всех производителей больше, чем потребности всех потребителей. При этом часть производителей будет работать «не на полную мощность».

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

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

А) Перевозки предполагаются только односторонними – от производителей к потребителям, но не в обратном направлении и не между потребителями.

Б) Не допускается обслуживания одним транспортным средством за один «рейс» нескольких потребителей сразу.

В) Не допускается обслуживания одним транспортным средством за один «рейс» нескольких производителей сразу

Г) Исключается возможность порчи продукции при перевозке, снижения ее качества, хищений и пр. (т.е. сколько взято от производителей, столько же доставлено потребителям).

Д) Обычно считается, что объем грузоперевозок от каждого производителя к каждому потребителю может изменяться непрерывным образом и при этом не может быть отрицательным (в силу пункта «А»).

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

Ж) Не рассматриваются возможности перевозки совокупности грузов разных типов и связанные с этим вопросы их совместимости друг с другом в процессе перевозки, максимальной грузоподъемности транспортного средства и пр.

Транспортные задачи линейного программирования могут решаться «вручную», но это очень трудоемко. Поэтому такие методы в лабораторных работах не рассматриваются, а вместо этого применяется средство «поиск решения».

В случае «закрытых» транспортных задач в стандартной постановке применение этого средства сводится к подбору объемов перевозок при условиях:

- минимум суммы «поэлементных» произведений двух матриц – «стоимости перевозок единицы груза от поставщиков потребителям» и «фактических объемов перевозок» (подчеркиваю – речь идет о поэлементном произведении двух матриц, а не об умножении этих матриц по правилам матричного умножения, т.е. «строка на столбец»);

- суммы в матрице «фактических объемов перевозок» по строкам должны быть равны потребностям соответствующих потребителей;

- суммы в матрице «фактических объемов перевозок» по столбцам должны быть равны соответствующим мощностям производителей.

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

При использовании этого средства также могут быть заданы:

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

- ограничения на перевозки в определенном направлении по нижнему значению (например, потому что при малых объемах они просто не рентабельны) и верхнему значению (ограниченная способность транспортных средств или магистралей);

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

Дата добавления: 2015-07-26; просмотров: 197; Нарушение авторских прав

Мы поможем в написании ваших работ!