Головна

Алгоритм методу гілок і меж для вирішення одновимірних задач цілочисельного програмування

  1. Amp; Завдання №3 Імпорт таблиць
  2. Amp; Завдання №4 Створення таблиці за допомогою Конструктора.
  3. Amp; Завдання №5 Створити зв'язку встановленого типу. Друк Схеми БДБазаПочтаФамілія.
  4. Amp; Завдання №6 Заповнення таблиць БДБазаПочтаФамілія.
  5. Excel для вирішення прикладних завдань
  6. I. Завдання семіотики і передумови, необхідні для її розробки
  7. I. До чого прагне педагогіка, якою вона має бути і в чому її завдання?

В математичному аналізі розглядається клас задач, об'єднаних поняттям задачі цілочислового програмування. У загальному вигляді вони можуть бути сформульовані як максимізація деякого виразу в умовах обмежень.

Розглянемо наступну задачу цілочисельного програмування. Потрібно максимізувати вираз

 (1.1)

при обмеженнях

(1.2)

xj {0; 1}, j= 1, ..., n, (1.3)

причому pj ?0, cj?0.

Рішення завдання може бути отримано за допомогою методу гілок і меж.

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

Ефективність обчислювальних алгоритмів залежить від точності і простоти способу визначення верхньої межі можливих рішень і точності визначення наближеного рішення. Чим точніше спосіб визначення верхньої межі цільової функції, тим більше безперспективних гілок відсікається в процесі оптимізації. Однак збільшення точності розрахунку верхніх меж пов'язано зі зростанням обсягу обчислень. Наприклад, якщо для оцінки верхньої межі використовувати симплекс-метод, то результат буде досить точним, але потребують великого обсягу обчислювальної роботи.

Розглянемо алгоритм вирішення задачі (1.1) - (1.3) методом гілок і меж з простим і ефективним способом оцінки верхньої межі цільової функції.

безліч U змінних xj розглядається як три безлічі.

S -безліч фіксованих змінних, що увійшли до допустиме рішення; Es - Безліч залежних змінних, які не можуть бути включені в безліч S, Так як для них виконується нерівність

GS - Безліч вільних змінних, з яких проводиться вибір для включення в S черговий змінної.

позначимо h1j = pj/ cj і припустимо, що xj S (j = 1, . .., k <п), Обчислюється вказане відношення і параметри нумеруються (ранжуються) у відповідності з ранжуванням h1,k+1 ?h1,k+2? ... ?h1l, L?n, (1.4)

 (1.5)

 (1.6)

Умови (1.5), (1.6) означають, що в безліч S без порушення нерівності (1.2) можна додатково ввести елементи хдо + 1, хдо +2, ..., Хl-1. При введенні в безліч S елементів хдо + 1, хдо +2, ..., хl нерівність (1.2) не виконується.

L 'S


Мал. 1.1 Кусково-лінійна функція

Для визначення верхньої межі рішення може бути використано
вираз

 (1.7)

де

 (1.8)

 
 


(1.9)

З умов (1.1) - (1.3) випливає, що L 's не менш максимального значення величини

 при обмеженнях

Пояснимо процес визначення L 'S графіком (рис. 1.1). Будуємо кусочнолінейную функцію L (с) з убутним значенням градієнта h. обчислюємо з '1 і за графіком знаходимо L 'S.

Вибір черговий змінної для включення в безліч S проводиться за допомогою умови

 (1.10)

 Для обраної змінної хr визначаються величини РS(xr) І РS(xr), Тобто в S включається хr = 1 або хr = 0.

Якщо в процесі вирішення виявиться, що в безлічі GS немає елементів, які можуть бути введені в безліч S без порушення обмеження (1.5), то отримане рішення  приймається в якості першого наближеного рішення L0.

Всі вершини дерева можливих варіантів, для яких виконуються умови QS ? L0 з подальшого розгляду виключаються.

З решти гілок вибирається гілку з максимальним значенням РS, І процес пошуку оптимального варіанта триває. Якщо в процесі вирішення буде знайдено  , То отримане рішення приймається в якості нового наближеного результату. Обчислювальна процедура закінчується, якщо для всіх, хто лишився гілок виконується умова РS ? L0.




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

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