- •6.030504, 6.030509, 6.030510, 6.030601Денної й заочної форм навчання
- •1.Рішення систем лінійних рівнянь методом гауса - жордана
- •1.1. Основні поняття
- •1.2. Приведення системи лінійних рівнянь до жорданової форми
- •1.3. Поняття загального, часного й базисного рішень
- •2. Загальні властивості задач лінійного програмування
- •2.І. Приклад задачі лінійного програмування - задача про використання обладнання.
- •2.2. Задача про використання сировини
- •2.3. Задачі складання раціону (задача про дієту)
- •2.4. Загальна постановка задач лінійного програмування
- •2.5. Геометричний метод вирішення злп
- •Приклад 1
- •2.6. Канонічний вигляд злп
- •3. Симплексний метод вирішення злп
- •3.1. Загальна характеристика й основні етапи симплекс - методу
- •3.2. Табличний вигляд злп. Симплекс - таблиці
- •3.3. Умова оптимальності опорного плану
- •3.4. Умова нерозв'язності злп через необмеженість знизу на опр цільової функції
- •3.5. Перехід до нового опорного плану.
- •3.6. Табличний симплекс-алгоритм
- •Після вибору генерального елемента переходимо до таблиці 3.11
- •Знову вибираємо генеральний елемент і переходимо до таблиці 3.14
- •3.7. Відшукування початкового опорного плану злп методом штучного базису
- •3.8. Виродженість опорного плану. Зациклення
- •Двоїстість у лінійному програмуванні
- •5.4. Цикли перерахування
- •5.4.1. Поняття циклу перерахування
- •5.4.2. Максимально припустиме зрушення по циклу перерахування
- •5.4.3. Ціна циклу перерахування
- •5.5. Потенціали
- •5.6. Алгоритм вирішення транспортної задачі методом потенціалів
- •5.7. Відкриті транспортні задачі.
- •6. Цілочислове лінійне програмування
- •6.1. Загальна постановка задачі цілочислового лінійного програмування (зцлп)
- •6.2. Цілочислова задача про використання сировини
- •6.3. Задача про рюкзак
- •6.4. Вирішення зцлп методом округлення
- •6.5. Метод гілок і меж
- •Оптимальний план оптимальний план
- •7. Загальна постановка й різновиди задач математичного програмування
- •Література
5.6. Алгоритм вирішення транспортної задачі методом потенціалів
1. Відшукуємо вихідний опорний план перевезень (наприклад, методом північно-західного кута). Перехід до пункту 2.
2. Будуємо систему потенціалів. Для цього для кожної базисної клітинки (p,q) записуємо рівняння αp+βq=cpq. Виходить система m+n–1 рівнянь із m+n невідомими потенціалами. Один з потенціалів вважаємо рівним 0 і знаходимо із системи інші потенціали. Перехід до пункту 3.
3. Для кожної вільної клітинки (i, j) обчислюємо псевдовартість . Якщо для всіх вільних клітинок, то план є оптимальний, і алгоритм зупиняється. Якщо ж існує вільна клітинка (i, j), для якої, то перехід до пункту 4.
4. Будуємо цикл перерахування, що проходить через клітинку (i, j), робимо по ньому максимально припустиме зрушення, одержавши, таким чином, новий опорний план. Перехід до пункту 2.
Приклад. Вихідні дані задачі наведені в таблиці 5.9.
Методом північно-західного кута знаходимо вихідний опорний план перевезень і записуємо його в ту ж таблицю.
Таблиця 5.9
Пп Пв |
В1 |
В2 |
В3 |
В4 |
Запаси |
αi |
А1 |
2 15 |
1 4
|
5 7
|
11 6
|
15 |
0 |
А2 |
5 7 |
4 18 |
8 10 |
14 9
|
35 |
3 |
А3 |
3 4
|
2 11
|
6 7 |
12 13 |
20 |
1 |
Потреби |
22 |
18 |
17 |
13 |
70=70 |
|
βj |
2 |
1 |
5 |
11 |
|
|
Для визначення потенціалів вирішимо наступну систему:
Покладемо α1=0. Тоді β1=2; α2=3; β2=1; β3=5; α3=1; β4=11. Знайдені потенціали вносимо в таблицю 5.9.
Обчислюємо псевдовартості для вільних клітинок і проставляємо їх у ліві верхні кути клітинок. Вибираємо вільну клітку, у якій ; наприклад, виберемо клітинку (1,4). Будуємо цикл перерахування, що проходить через цю клітинку, і зробимо по ньому максимально припустиме зрушення h = 10 (у від’ємних клітинках найменшим перевезенням є х23=10). Після зрушення клітинка (2,3) стає вільною, а клітинка (1,4) - базисною. Одержуємо новий опорний план, записаний у таблиці 5.10.
Таблиця 5.10
Пп Пв |
В1 |
В2 |
В3 |
В4 |
Запаси |
αi |
А1 |
- 5 |
1 4
|
0 7
|
+ 10 |
15 |
0 |
А2 |
5 17 |
4 18 |
3 8
|
9 9
|
35 |
3 |
А3 |
8
+
|
7 11
|
6 17 |
- 3 |
20 |
6 |
Потреби |
22 |
18 |
17 |
13 |
70=70 |
|
βj |
2 |
1 |
0 |
6 |
|
|
Знову будуємо систему потенціалів, розраховуємо псевдовартості, будуємо цикл перерахування, що проходить через клітинку (3,1), робимо по ньому максимально припустиме зрушення величиною h=3.
Таблиця 5.11
Пп Пв |
В1 |
В2 |
В3 |
В4 |
Запаси |
αi |
А1 |
2 2 |
1 4
|
-4 7
|
6 13 |
15 |
0 |
А2 |
5 17 |
4 18 |
-1 8
|
9 9
|
35 |
3 |
А3 |
4 3 |
2 11
|
6 17 |
8 12
|
20 |
2 |
Потреби |
22 |
18 |
17 |
13 |
70=70 |
|
βj |
2 |
1 |
-4 |
6 |
|
|
Після зрушення одержимо опорний план, записаний у таблиці 5.11. Побудувавши систему потенціалів і розрахувавши псевдовартості, бачимо, що для всіх вільних клітинок . Тому опорний план є оптимальний.
Отже, оптимальний план має такий вигляд: х11=2; х14=13; х21=17; х22=18; х31=3; х33=17.
При цьому fmln = 2• 2 + 13• 6 + 17• 5 + 18• 4 + 3• 4 + 17• 6 =353 гр. од.