Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.5. Методи розв’язування транспортної задачі

5.5.1. Задача, двоїста до транспортної

Один із способів розв’язування транспортної задачі ґрунтується на розгляді двоїстої задачі.

Розглянемо транспортну задачу (5.1)—(5.4).

Позначимо змінні двоїстої задачі, які відповідають рівнянням (5.2), через , а для рівнянь (5.3) — через . Оскільки всі обмеження транспортної задачі є рівняннями, то пара спряжених задач є несиметричною і ніякі обмеження на знаки змінних двоїстої задачі та не накладаються.

Для побудови двоїстої задачі поставимо у відповідність обмеженням початкової задачі змінні двоїстої:

(5.20)

(5.21)

.

Згідно з загальними правилами побудови двоїстих задач маємо:

(5.22)

за умов:

, (5.23)

.

Змінні ui та vj задачі (5.22), (5.23) двоїстої до транспортної мають назву потенціалів.