Главная страница
Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Рішення транспортної задачі
“МЕТОД ПОТЕНЦІАЛІВ”
Даний термін здобуто із теоретичних основ електротехніки.
Нехай була задана слідуюча умова:
А(11, 11, 8);
В(5, 9, 9, 7).
Побудова плану комунікацій та розрахунок потенціалів.
     
| | | | | U=(0, 4, 8);
V=(7, 8, 9, 10).
| |
Будуємо оцінювальну матрицю С0.
Циклічний процес:
1)Пошук направляючого елемента:
 ;
Якщо направляючий елемент не знайдено, то рішення отримано в матриці X.
2)Побудова в матриці X замкненого ланцюжка. (Направляючий елемент для даної задачі (-7)). Визначення Q-мінімальний елемент серед непарних.
Q=min(x1, x3, x5, …);
     
| Значення ЦФ корегується:
Z=Z-QD=150-7*6=108
| | 3)Перерахунок матриці X: віднімаємо в ланцюжку Q з непарних та додаємо Q до парних.
ПРИМІТКА:
1)ЦФ повинна поліпшуватися(окрім випадку, коли направляючий елемент Q дорівнює e).
2)Контроль вірності обчислювань повинен завжди дорівнювати поточній митриці X на вичаткову матр.С:
3)Перерахунок матр.С0:
 а)послідовно викреслюємо рядок, починаючи з напрямляючого елемента; потім викреслюємо стовпець по істотним нулям, і т.д. до тих пір, поки всі істотні нулі не будуть викреслені.
 
Істотний нуль: коли  , а якщо   e, Xij> 0.
б)Додавання до рядків “D”;
віднімання від стовпців “D”.
   
Ітерація 2.
| Ланцюжок: (2-1)
(2-3)
(3-3) Q=min(2, 1, 5)=1
(3-4)
(1-4)
(1-1)
(2-1)
| | 
  
 
Ітер.3.
| Ланцюжок: (1-3)
(1-1)
(2-1) Q=min(4, 1)=1
(2-3)
(1-3)
| | 
 
| Ланцюжок: (3-2)
(3-3)
(1-3)
(1-1)
(2-1)
(2-2)
(3-2)
| | Ітер.4
| Z=4*5+7*3+5*2+6*4+3*3+5*1=89
| |  
Рішення знайдено.
|
