Математическая формализация задачи

Обозначим через х _ίј количество груза предназначенного к отправке или получению, где ί=1,2,3, ј= 1,2,3,4, что подлежит определению и составляет план перевозок.

Все данные и переменные удобно записать в таблице.

пункты назначения отправл. запасы	В1 в1	В2 в2	В3 в3	В4 в4
А1 а1	С11 Х11	С12 Х12	С 13 Х13	С 14 Х14
А2 а2	С21 Х21	С22 Х22	С23 Х23	С24 Х24
А3 а3	С31 Х31	С32 Х32	С33 Х33	С34 Х34

Количество груза доставленного в В₁ с А_1,2,3 составит Х₁₁ + Х₂₁ + Х₃₁ и т.д.

(2) Х₁₁ + Х₁₂ + Х₁₃ + Х₁₄ = а₁

Х₂₁ + Х₂₂ + Х₂₃ + Х₂₄ = а₂ ∑⁴_ј=1 х _ίј = а_ί

Х₃₁ + Х₃₂ + Х₃₃ + Х₃₄ = а₃

(1) Х₁₁ + Х₂₁ + Х₃₁ = в₁

Х₁₂ + Х₂₂ + Х₃₂ = в₂ ∑³_ί=1 х _ίј = в_ј

Х₁₃ + Х₂₃ + Х₃₃ = в₃

Х₁₄ + Х₂₄ + Х₃₄ = в₄

Транспортные расходы равны: С₁₁ × Х₁₁ + С₁₂ × Х₁₂ … + С₃₄ × Х₃₄

целевая функция задачи

ƒ=∑⁴_ј=1 ∑³_ί=1 х _ίј с_ίј min

двойной знак суммирования означает суммирование элементов по индексу ј при одинаковой ί, затем наоборот.

В общем виде математическая формулировка задачи:

среди матриц решения системы

∑_ί=1 х _ίј = в_ј

∑_ј=1 х _ίј = а_ί

выбрать такое при котором, функция ƒ=∑⁴_ј=1 ∑³_ί=1 х _ίј с_ίј min

имеет наименьшее значение.

Данная система уравнений (1), (2) содержит в нашем случае m×n=12 переменных и m+ n=7 уравнений.

Если сложить уравнения системы, то получим два одинаковых уравнения

систему уравнений можно разрешить относительно m+ n-1 базисных переменных, выразив их через остальные свободные переменные.

В нашем случае свободных переменных 6= m×n – (m+n -1) базисных переменных 6= m+n -1

Это позволяет искать оптимальное решение транспортной задачи среди базисных переменных m+n -1 значения неизвестных х _ίј , удовлетворяющих системе ограничений.