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

Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х_KM – объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х_KM , а именно, Х₀₁ , Х₀₂ , Х₀₃ , Х₁₂ , Х₁₃ , Х₁₄ , Х₂₃ , Х₂₄ , Х₃₄ . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид: F → max ,

Х₀₁ +Х₀₂+Х₀₃=F (0)
- Х₀₁ + Х₁₂ + Х₁₃ +Х₁₄ = 0 (1)
- Х₀₂ - Х₁₂ + Х₂₃ + Х₂₄ = 0 (2)
-Х₀₃-Х₁₃-Х₂₃+Х₃₄= 0 (3)
-Х₁₄-Х₂₄-Х₃₄=-F (4)
Х₀₁ ≤ 2

Х₀₂ ≤ 3

Х₀₃ ≤ 1

Х₁₂ ≤ 4

Х₁₃ ≤ 1

Х₁₄ ≤ 3

Х₂₃ ≤ 1

Х₂₄ ≤ 2

Х₃₄ ≤ 2

Х_КМ ≥ 0 , К, М = 0, 1, 2, 3, 4, F ≥ 0 .

Здесь F – целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1)–(3) задают балансовые соотношения для узлов 1–3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие (4) – это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции.

Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию – через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").