30. Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке

1. При некоторых реальных условиях перевозки груза из определенного пункта Ai в пункт назначения Bj не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт Bj является сколь угодно большой величиной М и при этом условии известными методами находят решение ТЗ. Такой подход к нахождению решения ТЗ называется запрещением перевозок.

2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Ai в Bj требуется обязательно перевезти αIj единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки Ai и столбца Bj, записывают указанное число αIj и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Иногда требуется найти решение ТЗ, при котором из Ai в Bj должно быть перевезено не менее заданного количества груза αIj. Для определения оптимального плана такой задачи считают, что запасы Ai и потребности Bj меньше фактических на αIj единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.

Примечание: При целых Ai (I = 1,..., m) и Bj (J = 1,..., n), в силу специфики ограничений ТЗ, любое базисное допустимое решение является целочисленным.

< Предыдущая