Математическая модель транспортной задачи по критерию стоимости

Симплекс-метод является общим, и применим для любой задачи ЛП. Но существуют специальные задачи ЛП, для которых существуют специализированные формы симплекс-метода, имеющие более простой и наглядный смысл. Важным в приложениях классом таких задач, являются так называемые транспортные задачи (ТЗ). Целью этих задач является разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, связанных с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т. д.

Постановка транспортной задачи.

Имеется m пунктов А₁, А₂, …, A_m отправления, в каждом из которых сосредоточено определенное количество груза (a_1, а_{2, …,} а_m). Груз однородный, величины а_i называется запасами.

Имеется n пунктов назначения В₁, В₂, …, В_n, где требуется количество груза (b_1, b_{2, …,}b_n); величина b_j - заявки. Известна стоимость перевозки с_ij из i- го в j –й пункт.

Требуется составить план перевозок так, чтобы запасы не были превышены, заявки выполнены, и общая стоимость перевозки Е была бы минимальной.

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

Модель:

х_ij – количество единиц груза, перевозимого из i- го в j- й пункт:

Особенности модели ТЗ:

1. Наличие условия правильного баланса приводит к тому, что задача ТЗ всегда имеет решение.

2. Одно уравнение в системе ограничений линейно зависимо, значит, ранг системы ограничений будет (n + m – 1).

3. Коэффициенты при всех переменных х_ij в системе ограничений равны единице.

4. Всего переменных m n, базисных (n + m – 1). Свободных переменных будет k = m n – m – n + 1 = (m - 1) (n – 1). Так как ТЗ является задачей ЛП, то в оптимальном решении все свободные переменные должны быть равны нулю, т. е. большинство маршрутов не будут задействованы.

Этапы решения ТЗ те же, что и в симплекс-методе:

· нахождение исходного опорного решения;

· проверка этого решения на оптимальность;

· переход от одного опорного решения к другому.