Головна

Алгоритм методу потенціалів

  1. Адаптивні алгоритми стиснення. Кодування Хаффмена.
  2. алгоритм
  3. алгоритм
  4. Алгоритм (послідовність) неповного розбирання автомата
  5. Алгоритм (послідовність) складання автомата після неповного розбирання
  6. Алгоритм GAP - моделі Зейтгамла: причини виникнення третього, четвертого і п'ятого «розривів».
  7. алгоритм RSA

Найбільш поширеним методом вирішення транспортних задач є метод потенціалів.

Рішення завдання методом потенціалів включає наступні етапи:

1) розробку початкового плану (опорного рішення);

2) розрахунок потенціалів;

3) перевірку плану на оптимальність;

4) пошук максимального ланки неоптимальности (якщо умова п. 3 не було досягнуто);

5) складання контуру перерозподілу ресурсів;

6) визначення мінімального елемента в контурі перерозподілу і перерозподіл ресурсів по контуру;

7) отримання нового плану.

Описана процедура повторюється кілька разів (ітерацій), поки не буде знайдено оптимальне рішення. Обчислювальний алгоритм для кожної ітерації не змінюється.

Для транспортної задачі існує декілька методів відшукання початкового плану (опорного рішення):

- Метод північно-західного кута;

- Метод мінімального елемента;

- Метод подвійного переваги і т. Д.

У процесі рішення після кожної ітерації (в тому числі і після отримання допустимого рішення) по завантажених клітин перевіряється виконання наступної умови:

N=m+n-1 (9.7)

Якщо число завантажених клітин більше, то план закріплення одержувачів за постачальниками зроблений невірно і завдання вирішити не можна. Слід скласти новий план закріплення, дотримуючись наведене вище правило.

Якщо число завантажених клітин менше, то план називається виродженим. У цьому випадку в будь-які вільні клітини треба поставити стільки нулів, щоб з їх урахуванням виконувалася умова. Клітка, в якій стоїть нуль, вважається зайнятою (завантаженої). Нульову завантаження проставляють в клітинах стовпця з найменшою кількістю вантажу і мінімальним відстанню.

Розрахунок потенціалів виконують по завантажених клітин, для яких повинно виконуватися рівність:

Ui + VJ = Cij (9.8)

де Ui - потенціал iго рядка;

Vj - потенціал j-го стовпчика.

Обчислюючи потенціали за виразом (9.8), приймаємо для першого рядка U1 = 0.

Перевіряємо план на оптимальність за незавантажені клітинам,

Sij = Cij - (Ui + Vj) (9.9)

використовуючи наступне нерівність:

Ui + Vj ? Cij (9.10)

Якщо для незавантажених клітин умова (9.10) виконується, то план - оптимальний. Якщо не виконується, отже, початковий план вимагає поліпшення, здійснюємо перевірку початкового плану на оптимальність (9.9) і знаходимо саму потенційну клітину і будуємо для неї контур.

Контуром називається замкнута ламана лінія, утворена прямими відрізками, кути з'єднань між якими рівні 90 °.

Початком контуру є потенційна клітина з найбільшим за величиною потенціалом; відрізки ліній контуру повинні проходити через якомога більшу кількість завантажених клітин, але не менше двох, вважаючи і потенційну. Лінії контуру повинні замкнутися в потенційної клітці, з якої контур взяв свій початок, вершини перегинів лінії контуру повинні лежати тільки в завантажених клітина.

Транспортні завдання лінійного програмування. Постановка задачі. | Для кожної вільної клітини можна побудувати тільки один контур.


Метод північно-західного кута. | Метод мінімального елемента. | Метод подвійного переваги. | Рішення транспортної задачі методом потенціалів. | Розрахунок потенціалів. |

© 2016-2022  um.co.ua - учбові матеріали та реферати