(1)

Условие реализации продукции у каждого из поставщиков:

(2)

Условие обеспечения всех потребителей продукцией по их потребности:

(3)

Условие не отрицательности переменных:

В решении системы линейных уравнений 2 и 3 необходимо найти такие не отрицательные значения переменных, чтобы целевая функция принимала минимальное значение.

m+n-1 – линейно независимых уравнений, ранг системы, r= m+n-1.

В каждом опорном плане должно быть m+n-1 базисных элементов (x_ij>0), если таких переменных равно или больше, чем m+n-1, план называется невырожденный; если одна или несколько базисных переменных равна нулю, то такой план считается вырожденным.

Открытые транспортные задачи.

a)

(1)

(2)

(3)

B_n+1: – потребность какого-то потребителя, находящегося за пределами района (фиктивный потребитель).

(1)

(2)

(3)

с_{i, n+1}=0 (i=1,2…m)

б)

(1)

(2)

(3)

А_n+1: – фиктивный поставщик.

(1)

(2)

(3)

Ограничение транспортных возможностей.

а) x_ij=0 => c_ij=М, где М»0;

б) 0 ≤ х_ij ≤ d_ij

d_ij – характеризует транспортные возможности между i-поставщиком и j-потребителем.

Тогда поставщик А_i условно делится на А_i` и А<sub>i</sub>``, при этом a<sub>i</sub>`=d_ij и a_i``= a<sub>i</sub>`-d<sub>ij</sub>, c<sub>ij</sub>`=c<sub>ij</sub> и c<sub>ij</sub>``=М, где М»0.

Рассмотрим пример решения транспортной задачи методом потенциалов.

Δ₁₁=-1

Δ₁₂=0

Δ₁₃=M-11

Δ ₂₁=6

Δ₂₄=7

Δ₂₅=5

Δ₃₁=6

Δ₃₃=M-6

Δ₃₄=7

Δ₃₅=5

Δ₄₁=0

Δ₄₂=-4

Δ₄₄=4

Δ₅₂=13

Δ₅₄=0

Δ₅₅=2

Δ₁₁=-1

Δ₁₂=4

Δ₁₃=M-11

Δ₂₁=6

Δ ₂₂=4

Δ₂₄=7

Δ₂₅=5

Δ₃₁=2

Δ₃₃=M-10

Δ₃₄=3

Δ₃₅=1

Δ₄₁=0

Δ₄₄=4

Δ₅₂=7

Δ₅₄=3

Δ₅₅=2

Δ₁₂=5

Δ ₁₃=M-10

Δ₁₅=1

Δ₂₁=6

Δ₂₂=4

Δ₂₄=6

Δ₂₅=5

Δ₃₁=2

Δ₃₃=M-10

Δ₃₄=2

Δ₃₅=1

Δ₄₁=0

Δ₄₄=3

Δ₅₂=7

Δ₅₄=2

Δ₅₅=2

F=7x₁+10x₂+Mx₃+6x₄+7x₁+10x₂+Mx₃+6x₄+9x₅+5x₆+6x₇+8x₈+8x₉+6x₁₀+11x₁₁+

+10x₁₂+6x₁₃+11x₁₄+9x₁₅+7x₁₆=min

при ограничениях:

F=7*45+6*155+5*125+6*125+6*125+11*25+9*125+6*255=6300

Оптимальный план поставок для деревообрабатывающих предприятий, обеспечивающий минимальные транспортные затраты в сумме 6300000 руб., заключается в следующем:

1-ое лесозаготовительное предприятие поставляет 45 т. м³ 1-ому деревообрабатывающему предприятию;

1-ое – 4-ому: 255 т. м³;

2-ое – 2-ому: 125 т. м³;

2-ое – 3-ему: 125 т. м³;

3-е – 2-ому: 125 т. м³;

3-е – 3-ему: 25 т. м³;

у 3-го предприятия остаётся запас в 120 т. м³;

4-е – 1-ому: 155 т. м³;

4-е – 3-ему: 125 т. м³;

имеется альтернативный приведённому план поставок при тех же транспортных издержках:

1-ое – 4-ому: 255 т. м³;

2-ое – 2-ому: 125 т. м³;

2-ое – 3-ему: 125 т. м³;