ЛАБОРАТОРНА РОБОТА
Транспортна задача
Теоретична частина
В кожному з пунктів Pi, i=1,...,m, виробляється ai одиниць деякого однорідного продукту, а в кожному з пунктів Qj, j=1,...,n, споживається bj одиниць того ж продукту. Можливе транспортування продукту із кожного пункту виробництва Pi в кожний пункт споживання Qj. Вартiсть перевезення одиниці продукту з пункту Pi в пункт Qj відома i складає cij одиниць. Вважаючи, що сумарний об'єм виробництва дорівнює сумарному об'єму споживання, потрібно скласти план перевезень продукту, що мiнiмiзує сумарні транспортні витрати.
Математична модель транспортної задачі має вигляд[12]:
L(x) = c11 x11 +...+ c1n x1n +...+ cm1 xm1 +...+ cmn xmn > min,
xi1 +...+ xin = ai, i=1,...,m,
x1j +...+ xmj = bj, j=1,...,n,
xij?0, i=1,...,m, j=1,...,n,
a1 +...+ am = b1 +...+ bn.
Остання умова визначає збалансовану транспортну задачу.
В запропонованій моделі назвемо вектор
x=(x11,...,x1n,...,xm1,...,xmn) вектором перевезень, вектор
b=(a1,...,am,b1,...,bn)т — вектором запасiв-потреб, вектор
Aij=(0,...,0,1,0...,0,0,...,0,1,0,...,0)т — вектором комунікації PiQj (вектор Aij має розмірність m+n, причому перша одиниця стоїть на i-у місці, а друга — на m+j-у) i, нарешті, вектор c=(c11,...,c1n,...,cm1,...,cmn) — вектором транспортних витрат.
Основні теореми.
1) Розв'язок транспортної задачі базисний, якщо з його основних комунікацій неможливо скласти замкнений маршрут (цикл).
2) ДБР x=(xij, i=1,...,m, j=1,...,n) оптимальний тоді i тільки тоді, коли існують потенціали ui, vj такі, що
vj – ui = cij, якщо xij ? базисне перевезення,
vj – ui ? cij, якщо xij ? небазисне перевезення.
Методи пошуку вихідного ДБР.
Метод мінімального елемента
На кожному кроцi вибирається клітинка з найменшим значенням транспортних витрат cij таблиці, покладаючи x11 = min{a1, b1}.
Можливі три випадки:
1) a1<b1, тоді x11=a1 i викреслюється 1-й рядок таблиці;
2) a1>b1, тоді x11=b1 i викреслюється 1-й стовпець таблиці;
3) a1=b1, тоді x11=a1=b1 i викреслюється як 1-й рядок, так i 1-й стовпець. В останньому випадку в одну з викреслених клітинок заноситься нульове базисне перевезення (відповідний вихідний допустимий базисний розв'язок буде виродженим).
В усіх випадках після заповнення базисної клітинки об'єми запасів a1 i потреб b1 зменшують на величину, що дорівнює x11. Кiнець кроку. На кожному з наступних кроків розглядається «обрізана» транспортна таблиця, тобто викреслені рядки i стовпцi
ігноруються.
Варіант 1
Постановка завдання
Розв'язати методом потенціалів транспортну задачу:
а\в | 25 | 40 | 50 | 35 | 45
20 | 7 | 3 | 4 | 8 | 6
60 | 5 | 7 | 2 | 3 | 5
45 | 1 | 4 | 5 | 2 | 6
70 | 3 | 4 | 2 | 7 | 8
Розв’язання
Для пошук вихідного допустимого базисного роз’язку використовуємо метод мінімального елемента.
а\в | 25 | 40 | 50 | 35 | 45
20 | 7
0 | 3 | 4 | 8 | 6
60 | 5
0 | 7 | 2 | 3 | 5
45 | 1
25 | 4 | 5 | 2 | 6
70 | 3
0 | 4 | 2 | 7 | 8
а\в | 25 | 40 | 50 | 35 | 45
20 | 7
0 | 3 | 4 | 8 | 6
60 | 5
0 | 7 | 2 | 3 | 5
20 | 1
25 | 4
0 | 5
0 | 2
20 | 6
0
70 | 3
0 | 4 | 2 | 7 | 8
а\в | 25 | 40 | 50 | 15 | 45
20 | 7
0 | 3 | 4
0 | 8 | 6
60 | 5
0 | 7 | 2
0 | 3 | 5
20 | 1
25 | 4
0 | 5
0 | 2
20 | 6
0
70 | 3
0 | 4 | 2
50 | 7 | 8
а\в | 25 | 40 | 50 | 15 | 45
20 | 7
0 | 3 | 4
0 | 8
0 | 6
60 | 5
0 | 7 | 2
0 | 3
15 | 5
20 | 1
25 | 4
0 | 5
0 | 2
20 | 6
0
20 | 3
0 | 4 | 2
50 | 7
0 | 8
а\в | 25 | 40 | 50 | 15 | 45
20 | 7
0 | 3
20 | 4
0 | 8
0 | 6
0
45 | 5
0 | 7 | 2
0 | 3
15 | 5
20 | 1
25 | 4
0 | 5
0 | 2
20 | 6
0
20 | 3
0 | 4 | 2
50 | 7
0 | 8
а\в | 25 | 20 | 50 | 15 | 45
20 | 7
0 | 3
20 | 4
0 | 8
0 | 6
0
45 | 5
0 | 7
0 | 2
0 | 3
15 | 5
20 | 1
25 | 4
0 | 5
0 | 2
20 | 6
0
20 | 3
0 | 4
20 | 2
50 | 7
0 | 8
0
а\в | 25 | 20 | 50 | 15 | 45
20 | 7
0 | 3
20 | 4
0 | 8
0 | 6
0
45 | 5
0 | 7
0 | 2
0 | 3
15 | 5
45
20 | 1
25 | 4
0 | 5
0 | 2
20 | 6
0
70 | 3
0 | 4
20 | 2
50 | 7
0 | 8
0
L(x)=7x11+3x12+4x13+8x14+6x15+5x21+7x22+2x23+3x24+5x25+x31+4x32+5x33+2x34+6x35+3x41+4x42+2x43+7x44+8x45
L(x)=3*20+3*15+5*45+1*25+2*20+4*20+2*50=575