Транспортная задача

К задачам линейного программирования сводится большой класс военных, экономических и инженерных задач. Для решения этих задач может быть использован наиболее универсальный симплексный метод. Однако некоторые задачи могут быть сформулированы относительно просто, и для их решения пригодны специальные методы линейного программирования, значительно более эффективные, чем универсальный метод. Эти задачи можно описать общей математической моделью, состоящей из ряда линейных уравнений. Впервые такая модель была использована для планирования оптимальных схем перевозок, поэтому она получила название транспортной задачи. Такое название задачи и методов ее решения является условным, так как эта математическая модель и методы ее решения могут быть использованы для решения не только транспортной, но и целого ряда других задач [13, 14].

Транспортная задача находит широкое применение в военном деле при решении задач специального технического обеспечения операций, целераспределения, организации ремонта и восстановления РАВ и боеприпасов.

Математически транспортная задача формулируется следующим образом. Требуется минимизировать

(1.26)

при ограничениях

(1.27)

(1.28)

, (1.29)

где c_ij – стоимость перевозки единицы груза из i- го пункта отправления до j- го пункта назначения;

x_ij – количество груза, перевезенного из i– го пункта отправления в j –й пункт назначения;

a_i - запасы груза на i –м пункте отправления;

b_j - потребности в грузе на j –м пункте назначения.

Условия (1.27) и (1.28) означают, что количество груза, вывозимого из i– го пункта отправления, равно запасам груза в этом пункте и количество груза, ввозимого в j –й пункт назначения, равно потребности в грузе для данного пункта назначения. Из условия (1.29) следует, что общие запасы и потребности в грузе равны.

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

Обычно исходные данные транспортной задачи задаются в виде таблицы, пример которой приведен в табл. 1.4.

Таблица 1.4

---

Дата добавления: 2015-07-20