Вiдкрита модель тз
Транспортна задача називається відкритою (ВТЗ), якщо сума запасів вантажів постачальників ( ai) не дорівнює сумі потреб споживачів ( bj), тобто
ai bj . (9.5)
Розглянемо два випадки ВТЗ.
Випадок 1. Сума запасів у постачальників більша, ніж сума потреб споживачів
ai > bj . (9.6)
Потрібно мінімізувати цільову функцію Z (сумарну “транспортну роботу”)
Z = сij xij min (9.7)
при повному забезпеченні потреб споживачів
xij = bj , j = (9.8)
і необов’язковому вивезенні вантажів від постачальників
xij aj, i = . (9.9)
Економічна інтерпретація постановки ВТЗ (випадок 1). Знайти такий план перевезень вантажу, при якому сумарна вартість перевезень мінімальна при повному забезпеченні всіх потреб споживачів та необов’язковому вивезенні запасів вантажів від постачальників.
Зведемо
відкриту транспортну задачу до закритої.
Для цього введемо додаткового (фіктивного)
споживача
з потребами
bn+1 = ai - bj , (9.10)
де bn+1 - це залишок, який не вивозиться від постачальників. При цьому відстані між постачальниками та фіктивним споживачем дорівнюють нулю: ci,n+1 = 0, i= . Тоді математична модель ВТЗ (9.6)-(9.9) набуде вигляду: мінімізувати цільову функціцю Z
Z=
сij
xij
min
(9.11)
при обмеженнях :
а) в запасах вантажів, які є у постачальників
xij = aj, i= ; (9.12)
б) у потребах вантажів
xij
=
bj,
j=
.
(9.13)
Випадок 2. Нехай сума запасів вантажів у постачальників менше, ніж сума потреб споживачів
ai < bj (9.14)
Потрібно мінімізувати цільову функцію Z (сумарну “транспортну роботу”)
Z = сij xij min (9.15)
при повному вивозі всіх запасів вантажів від постачальників
xij = aі, i= (9.16)
і необов’язковому забезпечені потреб споживачів
xij bj, j= . (9.17)
Економічна інтерпретація постановки ВТЗ (випадок 2). Знайти такий план перевезень вантажу, при якому сумарна вартість перевезень мінімальна при повному вивезені вантажів від постачальників та необов’язковому забезпеченні всіх потреб споживачів.
Аналогічно,
як в попередньому випадку, зведемо
відкриту транспортну задачу до закритої.
Для цього введемо додаткового (фіктивного)
постачальника
із запасами
аn+1 = bj - ai . (9.18)
Тут an+1 - це сумарний об’єм вантажу, якого не вистачає для повного забезпечення потреб споживачів. При цьому відстані між споживачами та фіктивним постачальником дорівнюють нулю: cm+1,j= 0, j= .
Тоді математична модель задачі (9.14)-(9.17) набуде вигляду:
мінімізувати цільову функцію
Z
=
сij
xij
min
(9.19)
при обмеженнях в ресурсах
xij
=
aі,
i=
(9.20)
та в потребах
xij = bj, j= . (9.21)
Методи побудови опорних планів перевезень
Для побудови опорного плану використовують, в основному, такі методи: північно-західного кута, мінімального елемента в матриці, подвійної переваги та інші.
Метод північно-західного кута. Заповнення починають з верхньої лівої клітинки і продовжують, по діагоналі, до правої нижньої клітинки. Так наприклад, в клітинку А1В1 поміщають вантаж х11= min (a1, b1) і виводять з розгляду рядок або стовпець і т.д., поки не закінчать розподіл вантажів в правій нижній клітинці.
Метод мінімального елемента в матриці. Заповнення табл.9.1 починають з клітинки, для якої тарифи перевезень сij найменші і продовжують в порядку зростання тарифів.
Метод подвійної переваги. В рядках знаходять клітинки з найменшими тарифами перевезень і помічають їх під знаком “V”; аналогічно проводять цей процес по стовпчиках Після цього починають заповнювати, в першу чергу ті клітини, де два знаки “V”, потім - де один знак “V”, і на кінець - решту клітинок в порядку зростання їх тарифів.
|
j |
С п о ж и в а ч і |
Об’єм запасів |
|||||||||
i |
|
B1 |
B2 |
… |
Bj |
… |
Bn |
|||||
Постачальники |
A1 |
|
c11 |
|
c12 |
… |
|
c1j |
… |
|
c1n |
a1 |
x11 |
x12 |
x1j |
x1n |
|||||||||
A2 |
|
c21 |
|
c22 |
… |
|
c2j |
… |
|
c2n |
a2 |
|
x21 |
x22 |
x2j |
x2n |
|||||||||
… |
… |
… |
… |
… |
… |
… |
… |
|||||
Ai |
|
ci1 |
|
ci2 |
… |
|
cij |
… |
|
cin |
ai |
|
xi1 |
xi2 |
xij |
xin |
|||||||||
… |
… |
… |
… |
… |
… |
… |
… |
|||||
Am |
|
cm1 |
|
cm2 |
… |
|
cmj |
… |
|
cmn |
am |
|
xm1 |
xm2 |
xmj |
xmn |
|||||||||
Об’єм потреб |
b1 |
b2 |
… |
bj |
… |
bn |
|
|||||
Методи оптимізації опорних планів.
Для перевiрки опорного плану перевезень на оптимальнiсть та, у разі неохідності, покращення його використовують метод потенцiалiв, розподiльчий метод, тощо. Розглянемо метод потенціалів.
Алгоритм методу потенцiалiв
Нехай побудовано початковий опорний невироджений план перевезень вантажів. Запишемо систему потенціалів для цього плану. Кожному постачальнику Ai, i= поставимо у відповідність деяке число ui, i= , а кожному споживачу Bj, j= - деяке число vj, j= . Числа ui, vj називаються відповідно потенціалами постачальників Ai і спожиавчів Bj. Потенціали ui, vj вибирають так, щоб для кожної заповненої клітинки виконувалась умова
ui + vj= cij , i= , j= тобто їх сума дорівнювала тарифу перевезень цієї клітинки. Оскільки потенціалів ui, vj всього (m+n) штук, а заповнених клітинок в таблиці (m+n-1) і відповідно стільки ж лінійно-незалежних рівнянь з (m+n) невідомими, то така система невизначена. Для її розв’язання одному з невідомих потрібно надати певне значення (наприклад, u1 покласти рівним нулю) і після цього знаходять значення інших потенціалів.
Для того, щоб опорний план був оптимальним, необхідно виконання таких умов:
а) для кожної заповненої клітинки сума потенціалів не повинна дорівнювати тарифу перевезень, тобто повинні виконуватись умови
ui + vj= cij , i= , j=
б) для кожної порожньої клітинки сума потенціалів повинна не перевищувати тариф перевезень ui + vj cij, i= , j=
Якщо хоча б для однієї порожньої клітинки не виконується умова , то опорний план не є оптимальний і його необхідно покращити, ввівши в базис вектор, який відповідає цій клітинці. Для цього знаходять оцінку плану dij = (ui + vj) - cij, i= , j= для порожніх клітинок. Найбільша додатня оцінка плану відповідає клітинці, для якої необхідно провести перерозподіл. Відмітимо її знаком + і побудуємо замкнений цикл, вершини якого лежать в заповнених клітинках, з чергуванням знаків “-“ на “+”. Серед клітинок із знаком “-“ знаходимо найменшу кількість вантажу , яку будемо перерозподіляти так, щоб не порушився баланс по рядках та стовпчиках табл. 9.1, а саме: величини об’ємів вантажів у клітинках із знаком “+” збільшуємо на величину , а в клітинках під знаком “-“ - зменшуємо на . В результаті отримаємо новий опорний план, який перевіряємо на оптимальність. Цей процес продовжуємо до тих пір, поки для одного з опорних планів виконаються умови оптимальності
Після цього для оптимального плану визначаємо сумарну вартість перевезень, яка буде мінімальною. Z= сij xij min