Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

Метод гілок і національних кордонів

Реферат: Метод гілок і національних кордонів

Метод гілок і національних кордонів. Розглянемо завдання, яке у визначенні максимального значення функції

за умов

І за рішенні сформульованої завдання методом Гомори, спочатку знаходимо симплексным методом штучного базису оптимальний план завдання не враховуючи целочисленности змінних. Нехай таким є план X0. Якщо серед компонент цього плану немає дробових чисел, тим самим знайдено дані вирішення завдання і .

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

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

Знайдемо розглянутими вище методами вирішення завдань лінійного програмування (I) і (II). Вочевидь, тут може бути одне із наступних 4:

1. Одне із завдань нерозв'язна, іншу має целочисленный оптимальний план. Тоді це план і значення цільової функції ньому й прокурори дають рішення вихідної завдання.

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

3. Обидва завдання можна розв'язати. Одне із завдань має оптимальний целочисленный план, а оптимальному плані другий завдання є дробные числа. Тоді обчислюємо значення цільової функції цих плани та порівнюємо їх між собою. Коли целочисленном оптимальному плані значення цільової функції більше, або дорівнює її значенням на плані, серед компонент якого є дробные числа, то даний целочисленный план є оптимальним для вихідної завдання й він разом із значенням цільової функції у ньому дає дані рішення.

Якщо ж значення цільової функції понад плані, серед компонент якого є дробные числа, слід взяти одна з таких чисел й у завдання, план якої розглядається, необхідно побудувати два завдання, аналогічні (I) і (II).

4. Обидва завдання можна розв'язати, серед оптимальних планів обох завдань є дробные числа. Тоді виділяємо значення цільової функції на даних оптимальних плани та розглядаємо ту із завдань, на яку значення цільової функції найбільший. У оптимальному плані це завдання вибираємо жодну з компонент, значення є дробовим числом, й будуємо два завдання, аналогічні (I) і (II).

Отже, описане вище інтеграційний процес то, можливо подано у вигляді деякого дерева, у якому вихідна вершина відповідає оптимальному плану Х0 завдання (32)-(34), а кожна сполучена із нею гілкою вершина відповідає оптимальним планам завдань (I) і (II). Кожна з цих вершин має розгалуження. У цьому кожному кроці вибирається та вершина, на яку значення найбільший. Коли деякому кроці отримають план, має целочисленные компоненти, і значення функції у ньому виявиться більше або одно, ніж значення функції за іншими можливих для розгалуження вершинах, то даний план є оптимальним планом вихідної завдання целочисленного програмування і значення цільової функції у ньому є межею.

Отже, процес знаходження рішення завдання целочисленного програмування (32)-(35) методом гілок і національних кордонів входять такі етапи:

10 Знаходять вирішення завдання лінійного програмування (32)-(34)

20 Становлять додаткових обмежень до котроїсь із змінних, значення в оптимальному плані завдання (32)-(34) є дробовим числом.

30 Знаходять вирішення завдань (I) і (II), які виходять з завдання (32)-(34) внаслідок приєднання додаткових обмежень.

40 У разі потреби становлять додаткових обмежень для перемінної, значення є дробовим, формулюють завдання, аналогічні завданням (I) і (II), і знаходять їхнє рішення. Інтеграційний процес продовжують до того часу, поки що не знайдено вершина, відповідна целочисленному плану завдання (32)-(34) і такі, що значення у цій вершині більше або одно значенням функції за іншими можливих для розгалуження вершинах.

Описаний вище метод гілок і національних кордонів має як просту логічний схему розрахунків, ніж розглянутий вище метод Гомори. Тож у вона найчастіше перебування вирішення конкретних завдань целочисленного програмування з допомогою ЕОМ застосовується саме такий метод. Зокрема розглянутий вище ППП «Линейное програмування в АСУ» для відшукання целочисленного вирішення конкретних завдань використовується метод розгалуження і національних кордонів.

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

за умов

xj – цілі (j=)

Р е ш е зв і е. Знаходимо рішення сформульованої завдання симплексным методом - без обліку умови целочисленности змінних. Через війну встановлюємо, що завдання має оптимальний план Х0= (18/5, 3/5, 0, 0, 24/5). У цьому плані F= (X0)=39/5.

Позаяк у плані Х0 значення три змінні є дробовими числами, то Х0 не задовольняє умові целочисленности, і отже, перестав бути оптимальним планом вихідної завдання.

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

Розглянемо два завдання лінійного програмування:

(I) (II)

Завдання (I) має оптимальний план у якому значення цільової функції . Завдання (II) нерозв'язна.

Досліджуємо завдання (I). Адже серед компонент оптимального плану це завдання є дробные числа, то тут для одній з змінних, наприклад x2, вводимо додаткових обмежень:

Розглянемо тепер наступні два завдання:

(III)

(IV)

Завдання (IV) нерозв'язна, а завдання (III) має оптимальний план (3, 1, 3, 3, 3), у якому значення цільової функції завдання


Схожі реферати

Статистика

[1] 2 3 4