Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
DevioLab
CRYPTO TRADING AUTOMATION
LIVE
AUTOMATED CRYPTO TRADING • BINANCE
Автоматизуйте свій
криптопортфель
Торгові боти DevioLab аналізують крипторинок,
автоматично відкривають і закривають позиції
та керують вашим портфелем на Binance 24/7.
CRYPTO
80 Bots
BINANCE
Spot Trading
TRADING
24 / 7
deviolab.com
Лабораторна робота 5
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №7-8
з дисципліни “Математичні методи дослідження операцій”
на тему
« Транспортна задача.
Метод потенціалів»
Львів –
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми.
План
Короткі теоретичні відомості.
Постановка задачі
Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язання транспортної задачі методом потенціалів.
Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів.
Знайти базове рішення відкритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів.
Розв’язання за допомогою пакету програм MS Exel.
Розв’язання за допомогою пакету програм MatCad .
Розв’язання за допомогою пакету програм Optimal 1_4
Алгоритм власної програми.
Розв’язання за допомогою власної програми.
Хід роботи
1. Короткі теоретичні відомості
Постановка транспортної задачі
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1( i ( m, 1 ( j ( n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Умови Т-задачі записуються у вигляді
ai
С =
bj b1 b2 b3 … bn
Введемо змінні хij ( 0, 1( i ( m, 1 ( j ( n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва ( ai ) в j пункт споживання ( bj ).
Необхідно знайти множину значень змінних хij ( 0, мінімізуючи функцію
L = ,
з виконанням умов
Матрицю
Х =
називають планом перевезень Т-задачі.
Визначення початкового опорного плану.
Метод «північно-західного кута» (ПЗК).
Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута. Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n.
Припустимо, що вже виконано t кроків.
Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай ( + ( = t + 2. Знаходимо x(( = min{}, де
.
Якщо , то заповнюється (-ий рядок матриці, починаючи з ((+1)-го елемента, нулями. Якщо , то заповнюється нулями (-й стовбець, починаючи з ((+1)-ї строки. При цьому
;
Метод потенціалів розв’язування транспортної задачі.
Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій.
Попередній етап.
1. Будується початковий опорний план Х0.
2. Обчислюється оціночна матриця
Δ1 = ,
де ui i vj – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова для хij ( 0 (базових клітин). Для зручності вибирається u1 = 0. Позиція в матриці Δ1, яка відповідає базисному елементові плану Х0, буде зайнята нулем.
Якщо всі елементи матриці Δ1 – не додатні, то план Х0 – оптимальний. Якщо ні, то виконується наступна ітерація.
k + 1 ітерація.
1. Якщо в оціночній матриці Δ (к+1) всі елементи не додатні, то план Хк – оптимальний. Якщо ні, виконується наступний крок.
2. Вибирається з Δ (к+1) найбільший додатний елемент і, починаючи з відповідного йому елемента в матриці Хк, будується замкнута послідовність, в яку входять елементи . Потім визначається ( - мінімальний елемент серед всіх непарних за порядком розміщення в послідовності, приймаючи першим елементом наступний за елемент.
3. Будується новий план Хк+1, додаванням до всіх парних елементів послідовності і відніманням від всіх непарних. Елементи матриці Хк, що не входять в послідовність, переносяться в матрицю Хк+1, без змін.
4. З матриці Δк будується оціночна матриця Δк+1 для нового плану Хк+1. Для цього підкреслюються в матриці Δк всі елементи, які відповідають ненульовим елементам матриці Хк+1 (вони обов’язково рівні нулю). В матриці Δк закреслюємо рядок, який містить елемент cst. Якщо в цьому рядку є підкреслені елементи, то закреслюються відповідні до цих елементів стовбці. Якщо в кожному закресленому стовбці є підкреслені елементи, то закреслюються відповідні до них рядки, і так до того моменту, доки описана процедура може виконуватися. Після цього до всіх елементів закреслених рядків додається (cst(, а від елементів закреслених стовбців віднімається величина (cst(.
Якщо в матриці Δк+1 відсутні від’ємні елементи, то план Хк+1 – оптимальний, інакше перехід до наступної ітерації.
2. Постановка задачі
Номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100.
Варіант 48
ai
48. С =
bj 25 30 40 15
2.1 Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язання транспортної задачі методом потенціалів.
Математична модель транспортної задачі:
F = ∑∑cijxij, (1)
При умовах:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
1
2
3
4
Запаси
1
1
3
3
8
10
2
8
6
2
6
20
3
4
7
7
3
35
4
5
2
4
5
45
Потреби
25
30
40
15
Перевіримо необхідну і достатню умову розв'язання задачі.
∑a = 10 + 20 + 35 + 45 = 110
∑b = 25 + 30 + 40 + 15 = 110
Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.
Занесемо вихідні дані в розподільну таблицю.
1
2
3
4
Запаси
1
1
3
3
8
10
2
8
6
2
6
20
3
4
7
7
3
35
4
5
2
4
5
45
Потреби
25
30
40
15
Етап I. Пошук першого опорного плану.
1. Використовуючи метод північно-західного кута, побудуємо перший опорний план транспортної задачі.
План починається заповнюватися з верхнього лівого кута.
Шуканий елемент дорівнює 1
Для цього елементу запаси дорівнюють 10, потреби 25. Оскільки мінімальним є 10, то віднімаємо його.
x11 = min(10,25) = 10.
1
x
x
x
10 - 10 = 0
8
6
2
6
20
4
7
7
3
35
5
2
4
5
45
25 - 10 = 15
30
40
15
0
Шуканий елемент дорівнює 8
Для цього елемента запаси дорівнюють 20, потреби 15. Оскільки мінімальним є 15, то віднімаємо його.
x21 = min(20,15) = 15.
1
x
x
x
0
8
6
2
6
20 - 15 = 5
x
7
7
3
35
x
2
4
5
45
15 - 15 = 0
30
40
15
0
Шуканий елемент дорівнює 6
Для цього елемента запаси дорівнюють 5, потреби 30. Оскільки мінімальним є 5, то віднімаємо його.
x22 = min(5,30) = 5.
1
x
x
x
0
8
6
x
x
5 - 5 = 0
x
7
7
3
35
x
2
4
5
45
0
30 - 5 = 25
40
15
0
Шуканий елемент дорівнює 7
Для цього елемента запаси дорівнюють 35, потреби 25. Оскільки мінімальним є 25, то віднімаємо його.
x32 = min(35,25) = 25.
1
x
x
x
0
8
6
x
x
0
x
7
7
3
35 - 25 = 10
x
x
4
5
45
0
25 - 25 = 0
40
15
0
Шуканий елемент дорівнює 7
Для цього елемента запаси дорівнюють 10, потреби 40. Оскільки мінімальним є 10, то віднімаємо його.
x33 = min(10,40) = 10.
1
x
x
x
0
8
6
x
x
0
x
7
7
x
10 - 10 = 0
x
x
4
5
45
0
0
40 - 10 = 30
15
0
Шуканий елемент дорівнює 4
Для цього елемента запаси дорівнюють 45, потреби 30. Оскільки мінімальним є 30, то віднімаємо його.
x43 = min(45,30) = 30.
1
x
x
x
0
8
6
x
x
0
x
7
7
x
0
x
x
4
5
45 - 30 = 15
0
0
30 - 30 = 0
15
0
Шуканий елемент дорівнює 5
Для цього елемента запаси дорівнюють 15, потреби 15. Оскільки мінімальним є 15, то віднімаємо його.
x44 = min(15,15) = 15.
1
x
x
x
0
8
6
x
x
0
x
7
7
x
0
x
x
4
5
15 - 15 = 0
0
0
0
15 - 15 = 0
0
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8[15]
6[5]
2
6
20
3
4
7[25]
7[10]
3
35
4
5
2
4[30]
5[15]
45
Потреби
25
30
40
15
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m + n - 1 = 7. Отже, опорний план є невиродженим.
Значення цільової функції для цього опорного плану дорівнює:
F(x) = 1*10 + 8*15 + 6*5 + 7*25 + 7*10 + 4*30 + 5*15 = 600
Етап II. Поліпшення опорного плану.
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u2 + v1 = 8; 1 + u2 = 8; u2 = 7
u2 + v2 = 6; 7 + v2 = 6; v2 = -1
u3 + v2 = 7; -1 + u3 = 7; u3 = 8
u3 + v3 = 7; 8 + v3 = 7; v3 = -1
u4 + v3 = 4; -1 + u4 = 4; u4 = 5
u4 + v4 = 5; 5 + v4 = 5; v4 = 0
v1=1
v2=-1
v3=-1
v4=0
u1=0
1[10]
3
3
8
u2=7
8[15]
6[5]
2
6
u3=8
4
7[25]
7[10]
3
u4=5
5
2
4[30]
5[15]
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
(2;3): 7 + -1 > 2; ∆23 = 7 + -1 - 2 = 4
(2;4): 7 + 0 > 6; ∆24 = 7 + 0 - 6 = 1
(3;1): 8 + 1 > 4; ∆31 = 8 + 1 - 4 = 5
(3;4): 8 + 0 > 3; ∆34 = 8 + 0 - 3 = 5
(4;1): 5 + 1 > 5; ∆41 = 5 + 1 - 5 = 1
(4;2): 5 + -1 > 2; ∆42 = 5 + -1 - 2 = 2
max(4,1,5,5,1,2) = 5
Вибираємо максимальну оцінку вільної клітинки (3; 1): 4
Для цього в перспективну клітку (3; 1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8[15][-]
6[5][+]
2
6
20
3
4[+]
7[25][-]
7[10]
3
35
4
5
2
4[30]
5[15]
45
Потреби
25
30
40
15
Цикл наведено в таблиці (3,1; 3,2; 2,2; 2,1;).
З вантажів хij ,які стоять в мінусових клітинах, вибираємо найменше, тобто
у = min (2, 1) = 15. Додаємо 15 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 15 з Хij, що стоять в мінусових клітинках. В результаті отримаємо новий опорний план.
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6[20]
2
6
20
3
4[15]
7[10]
7[10]
3
35
4
5
2
4[30]
5[15]
45
Потреби
25
30
40
15
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u3 + v1 = 4; 1 + u3 = 4; u3 = 3
u3 + v2 = 7; 3 + v2 = 7; v2 = 4
u2 + v2 = 6; 4 + u2 = 6; u2 = 2
u3 + v3 = 7; 3 + v3 = 7; v3 = 4
u4 + v3 = 4; 4 + u4 = 4; u4 = 0
u4 + v4 = 5; 0 + v4 = 5; v4 = 5
v1=1
v2=4
v3=4
v4=5
u1=0
1[10]
3
3
8
u2=2
8
6[20]
2
6
u3=3
4[15]
7[10]
7[10]
3
u4=0
5
2
4[30]
5[15]
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
(1;2): 0 + 4 > 3; ∆12 = 0 + 4 - 3 = 1
(1;3): 0 + 4 > 3; ∆13 = 0 + 4 - 3 = 1
(2;3): 2 + 4 > 2; ∆23 = 2 + 4 - 2 = 4
(2;4): 2 + 5 > 6; ∆24 = 2 + 5 - 6 = 1
(3;4): 3 + 5 > 3; ∆34 = 3 + 5 - 3 = 5
(4;2): 0 + 4 > 2; ∆42 = 0 + 4 - 2 = 2
max(1,1,4,1,5,2) = 5
Вибираємо максимальну оцінку вільної клітини (3, 4): 3
Для цього в перспективну клітку (3, 4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6[20]
2
6
20
3
4[15]
7[10]
7[10][-]
3[+]
35
4
5
2
4[30][+]
5[15][-]
45
Потреби
25
30
40
15
Цикл наведено в таблиці (3,4; 3,3; 4,3; 4,4;).
З вантажів хij стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 3) = 10. Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 10 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6[20]
2
6
20
3
4[15]
7[10]
7
3[10]
35
4
5
2
4[40]
5[5]
45
Потреби
25
30
40
15
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що
u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u3 + v1 = 4; 1 + u3 = 4; u3 = 3
u3 + v2 = 7; 3 + v2 = 7; v2 = 4
u2 + v2 = 6; 4 + u2 = 6; u2 = 2
u3 + v4 = 3; 3 + v4 = 3; v4 = 0
u4 + v4 = 5; 0 + u4 = 5; u4 = 5
u4 + v3 = 4; 5 + v3 = 4; v3 = -1
v1=1
v2=4
v3=-1
v4=0
u1=0
1[10]
3
3
8
u2=2
8
6[20]
2
6
u3=3
4[15]
7[10]
7
3[10]
u4=5
5
2
4[40]
5[5]
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
(1;2): 0 + 4 > 3; ∆12 = 0 + 4 - 3 = 1
(4;1): 5 + 1 > 5; ∆41 = 5 + 1 - 5 = 1
(4;2): 5 + 4 > 2; ∆42 = 5 + 4 - 2 = 7
max(1,1,7) = 7
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6[20]
2
6
20
3
4[15]
7[10][-]
7
3[10][+]
35
4
5
2[+]
4[40]
5[5][-]
45
Потреби
25
30
40
15
Цикл наведено в таблиці (4,2; 4,4; 3,4; 3,2;).
З вантажів хij стоять в мінусових клітинах, вибираємо найменше, тобто у = min (4, 4) = 5. Додаємо 5 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 5 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6[20]
2
6
20
3
4[15]
7[5]
7
3[15]
35
4
5
2[5]
4[40]
5
45
Потреби
25
30
40
15
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u3 + v1 = 4; 1 + u3 = 4; u3 = 3
u3 + v2 = 7; 3 + v2 = 7; v2 = 4
u2 + v2 = 6; 4 + u2 = 6; u2 = 2
u4 + v2 = 2; 4 + u4 = 2; u4 = -2
u4 + v3 = 4; -2 + v3 = 4; v3 = 6
u3 + v4 = 3; 3 + v4 = 3; v4 = 0
v1=1
v2=4
v3=6
v4=0
u1=0
1[10]
3
3
8
u2=2
8
6[20]
2
6
u3=3
4[15]
7[5]
7
3[15]
u4=-2
5
2[5]
4[40]
5
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
(1;2): 0 + 4 > 3; ∆12 = 0 + 4 - 3 = 1
(1;3): 0 + 6 > 3; ∆13 = 0 + 6 - 3 = 3
(2;3): 2 + 6 > 2; ∆23 = 2 + 6 - 2 = 6
(3;3): 3 + 6 > 7; ∆33 = 3 + 6 - 7 = 2
max(1,3,6,2) = 6
Вибираємо максимальну оцінку вільної клітини (2, 3): 2
Для цього в перспективну клітку (2, 3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6[20][-]
2[+]
6
20
3
4[15]
7[5]
7
3[15]
35
4
5
2[5][+]
4[40][-]
5
45
Потреби
25
30
40
15
Цикл наведено в таблиці (2,3; 2,2; 4,2; 4,3;).
З вантажів хij стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
1
2
3
4
Запаси
1
1[10]
3
3
8
10
2
8
6
2[20]
6
20
3
4[15]
7[5]
7
3[15]
35
4
5
2[25]
4[20]
5
45
Потреби
25
30
40
15
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u3 + v1 = 4; 1 + u3 = 4; u3 = 3
u3 + v2 = 7; 3 + v2 = 7; v2 = 4
u4 + v2 = 2; 4 + u4 = 2; u4 = -2
u4 + v3 = 4; -2 + v3 = 4; v3 = 6
u2 + v3 = 2; 6 + u2 = 2; u2 = -4
u3 + v4 = 3; 3 + v4 = 3; v4 = 0
v1=1
v2=4
v3=6
v4=0
u1=0
1[10]
3
3
8
u2=-4
8
6
2[20]
6
u3=3
4[15]
7[5]
7
3[15]
u4=-2
5
2[25]
4[20]
5
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi> cij
(1;2): 0 + 4 > 3; ∆12 = 0 + 4 - 3 = 1
(1;3): 0 + 6 > 3; ∆13 = 0 + 6 - 3 = 3
(3;3): 3 + 6 > 7; ∆33 = 3 + 6 - 7 = 2
max(1,3,2) = 3
Вибираємо максимальну оцінку вільної клітини (1, 3): 3
Для цього в перспективну клітку (1, 3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
1
2
3
4
Запаси
1
1[10][-]
3
3[+]
8
10
2
8
6
2[20]
6
20
3
4[15][+]
7[5][-]
7
3[15]
35
4
5
2[25][+]
4[20][-]
5
45
Потреби
25
30
40
15
Цикл наведено в таблиці (1,3; 1,1; 3,1; 3,2; 4,2; 4,3;).
З вантажів хij стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 5. Додаємо 5 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 5 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
1
2
3
4
Запаси
1
1[5]
3
3[5]
8
10
2
8
6
2[20]
6
20
3
4[20]
7
7
3[15]
35
4
5
2[30]
4[15]
5
45
Потреби
25
30
40
15
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u3 + v1 = 4; 1 + u3 = 4; u3 = 3
u3 + v4 = 3; 3 + v4 = 3; v4 = 0
u1 + v3 = 3; 0 + v3 = 3; v3 = 3
u2 + v3 = 2; 3 + u2 = 2; u2 = -1
u4 + v3 = 4; 3 + u4 = 4; u4 = 1
u4 + v2 = 2; 1 + v2 = 2; v2 = 1
v1=1
v2=1
v3=3
v4=0
u1=0
1[5]
3
3[5]
8
u2=-1
8
6
2[20]
6
u3=3
4[20]
7
7
3[15]
u4=1
5
2[30]
4[15]
5
Опорний план є оптимальним, тому всі оцінки вільних клітин задовольняють умові ui + vi <= cij.
Мінімальні витрати складуть:
F(x) = 1*5 + 3*5 + 2*20 + 4*20 + 3*15 + 2*30 + 4*15 = 305
Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів.
Математична модель транспортної задачі:
F = ∑∑cijxij, (1)
при умовах:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
1
2
3
4
Запаси
1
1
3
3
8
10
2
8
6
2
6
20
3
4
7
7
3
35
4
5
2
4
5
45
Потреби
25
30
40
15
Перевіримо необхідну і достатню умову розв'язання задачі.
∑a = 10 + 20 + 35 + 45 = 110
∑b = 25 + 30 + 40 + 15 = 110
Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.
Занесемо вихідні дані в розподільну таблицю.
1
2
3
4
Запаси
1
1
3
3
8
10
2
8
6
2
6
20
3
4
7
7
3
35
4
5
2
4
5
45
Потреби
25
30
40
15
Етап I. Пошук першого опорного плану.
1. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.
Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу, і в клітину, яка їй відповідає, поміщають менше з чисел ai, або bj.
Потім, з розгляду всієї таблиці виключають або рядок, який відповідає постачальнику, запаси якого повністю витрачені, або стовпець,
27.12.2013 02:49
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора