Page 13 - 100

m n
min   ij  x
c
ij
 i 1  j 1
при обмеженнях
n
 x  a i i  2 , 1 ,...,m ;
ij
j 1
m
 x ij  b j  j 1 2 , ,...,  n ;
 i 1
x  . 0
ij
Перше обмеження вимагає повного вивезення продуктів з усіх пунктів
виробництва, друге обмеження вимагає повного задоволення попиту всіх
пунктів споживання.
Не завжди має місце баланс виробництва та споживання: це означає, що
обмеження задачі перетворюється в нерівності. Така задача називається від-
критою транспортною моделлю.

n
Якщо  x ij  a (і=1...m) тоді задача відкрита і треба ввести фіктивні
i
j 1
змінні у(х i n+1) інакше кажучи один лишній вузол споживання n+1 з c in+1=0.
Вихідні дані записуєм у формі таблиці.
Споживання
Постачання 1 2 3 4 а і
1 c 11 c 12 c 1n … 0 a 1
2 c 21 c 22 c 2n … 0 a і
… … … … … …
3 c m1 c m1 c mn … 0 а m

b j b 1 b 2 b n … b n+1

Алгоритм розв’язку за методом потенціалів:
1. Знаходження початкового базового розв’язку за методом північно-
західного кута.
До першого споживача транспортують товар з першого постачальника
(якщо не стає то з другого і т.д.). Якщо залишається у 1-го постачальника, то-
ді залишок – другому споживачу і т.д.
Послідовний перебір від першого до останнього споживача з послідов-
ністю постачальників. Запис таблиці.
Споживання
1 2 3 4 Генер.
Постачання
1 x 11 0 0 0 a 1
2 x 21 x 22 x 23 0 a 2
3 0 0 x 33 x 34 а 3
b 1 b 2 b 3 b 4 0
Споживання

2. Пунктам виробництва u i – потенціали
споживання v i – потенціали

13