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

Постановку задачи рассмотрим на примере: Фирма должна отправить для продажи со складов W₁,W₂,W₃ кровати в  магазины S₁,S₂,S₃,S₄,S₅. На складах имеется 15, 25, 20 кроватей, а магазинам необходимо 20,12,5,8,15 кроватей. Стоимость перевозки кроватей со склада i в магазин j дана в таблице

1)    Сколько нужно перевозить кроватей с каких складов и в какие магазины чтобы удовлетворить все запросы и сделать стоимость перевозок минимальной?

Обозначим x_ij- количество кроватей, перевезенных с i-го склада в j-тый магазин, x_ij>=0. И в силу ограничений на возможные поставки со складов (предложение) и спрос в магазинах на x_ij наложены следующие ограничения:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=15

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅=25 ограничения на емкость складов(предложение)

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅=20

x₁₁+x₂₁+x₃₁=20

x₁₂+x₂₂+x₃₂=12

x₁₃+x₂₃+x₃₃=5   ограничение на запросы магазинов (спрос)

x₁₄+x₂₄+x₃₄=8

x₁₅+x₂₅+x₃₅=15

Необходимо минимизировать стоимость перевозок

C=x₁₁+0*x₁₂+3*x₁₃+4*x₁₄+2*x₁₅+5*x₂₁+... +4x₃₁+...  +3*x₃₅

Получили задачу линейного программирования с ограничениями специального вида:

1)коэффициенты в ограничениях принимают значения (0,1).

2)каждая переменная входит только в два уравнения.

 В теории доказано, что если a₁,...a_n,b₁...b_n-целые, то задача имеет целочисленное решение.