Page 36 - 6449

Формальна постановка транспортної задачі здійснюється
наступним чином.
Нехай x – це об’єм перевезення продукції з i -го пункту зберігання
ij
на j -ий пункт споживання. Тоді задача записується в такій постановці і
знайти
n m
min Z   C ij X (1.43)
ij
 i 1  j 1
за умови:
n
 x ij  a , j  ...1 m , (1.44)
j
 i 1
m
 x ij  b , i  ...1 m . (1.45)
i
 j 1
Умови (1.44) означають, що кожен споживач повинен бути
задоволений в своїх потребах, умова (1.45) означає, що з кожного з пунктів
виробництва або зберігання повинна бути вивезена вся продукція. Ранг
матриці системи обмежень (1.44) – (1.45) дорівнює m+n-1, тому в
розв’язок задачі входить n+m-1 базисна клітинка, всі інші значення Xij
дорівнюють нулю. Як правило, транспортну задачу подають у наступному
вигляді :
c c c … c b
11 12 13 1 m 1
c c c … c b
21 22 23 2 m 2
c c c … c b
31 32 33 3 m 3
… … … … … …

c c c … c b
1 n n 2 n 3 nm n
a a a … a
nm
1
3
2

Зі сказаного вище зрозуміло, що якщо в порожні клітинки вставити
відповідні об’єми перевезень, то заповненими будуть лише
n  m 1 - клітинки.
Завжди має розв’язок лише така задача транспортного типу, для
якої виконується умова замкнутості або ж правильного балансу:
n m
b   a (1.46)
 i j
 i 1  j 1
тому в подальшому розглядаються лише такі задачі.
Якщо умова (1.46) не виконується, то задача в такому випадку
називається відкритою, або задачею з неправильним балансом. Будь-яка
транспортна задача з неправильним балансом може бути збалансована,
причому залежно від величини

36