Головна

комбінаторні методи

  1. I. Неекспериментальні методи
  2. II. Арени. Методи отримання.
  3. II. Основні методи збору соціологічної інформації, їх коротка характеристика.
  4. II. експериментальні методи
  5. II. Метод ДЕРЖАВНОГО УПРАВЛІННЯ.
  6. IV. Методи дослідження виконавчої та пізнавальної діяльності
  7. IV. Методи опитування в соціологічному дослідженні.

алгоритм Джонсона для завдання упорядкування робіт у 2-х канальної системі.

Алгоритм включає наступні етапи:

1. пошук найменшого елемента

У таблиці вихідних даних знаходять мінімальний елемент і відзначають його точкою.

2. перестановка інформації

Визначаємо місце розташування мінімального елемента, якщо він відноситься до першого пункту обслуговування то відповідний стовпець ставимо на перше місце, якщо до другого то на останнє місце календарного плану.

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

3. викреслення з таблиці стовпці зазначеного точкою і перехід до пункту 1 до тих пір поки не буде вичерпано весь список інформації.

4. виписати оптимальне рішення.

5. визначення оптимального значення цільової функції

При цьому графічно для оптимального рішення визначається хв. час роботи і простою 2-го пункту обслуговування.

угорський алгоритм включає наступні етапи:

1. приведення вихідної матриці;

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

Аналогічні операції здійснюються за стовпцями.

2. пошук оптимального рішення;

У наведеній матриці відшукуємо одну з рядків має найменше нулів. Один з нулів цього рядка відзначаємо точкою і викреслюємо всі інші нулі цього рядка і того стовпця, де нуль знаходиться. Аналогічну операцію проводимо поки не залишиться непомічених і не викреслених нулів. Якщо точками зазначено n нулів, то призначення повне і переходимо до пункту 5, інакше переходимо до пункту 3.

3. пошук мінімального набору рядків і стовпців, що містять нулі. Для цього відзначають точкою.

a) Усі рядки, в яких жодного зазначеного точкою нуля.

б) Всі стовпці, що містять перекреслений нуль, хоча б в одній із зазначених точкою рядків.

в) Всі рядки містять відмічені точкою нулі, хоча б в одному із зазначених точкою стовпців.

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

4. перестановка нулів;

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

5. виписати оптимальне призначення.

6. визначити мінімальне значення цільової функції.



алгоритм методу | Метод лексикографічного перебору

Математичне формулювання завдань дискретного програмування | Метод відсікань. Формулювання вірного відсікання. алгоритм методу | Переваги та недоліки алгоритму. | Формування нижніх і верхніх оцінок цільової функції | Метод неявного перебору по векторної решітці | наближені методи | Алгоритм симплекс методу | Друга стандартна форма | Вихідна задача в канонічній формі | Xi |

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