Реферати українською » Экономико-математическое моделирование » Метод гілок і національних кордонів (контрольна)


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

року міністерство освіти Р.Ф.

Тюменский державний нафтогазовий університет

Інститут нафти і є

                                                                                          Кафедра менеджменту

                                                                                          У галузях ПЕК

Контрольна робота з

Дисциплине «Економічна математика, методи лікування й моделі»

Варіант №4

                                                                                  Выполнил: студент грн.

                                                                                   МОс2 Ваганова Г.Р.

                                                                                  Перевірив: Захаров А.В

Тюмень 2002 р.


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

за умов

            І за рішенні сформульованої завдання методом Гомори, спочатку знаходимо симплексным методом штучного базису оптимальний план завдання не враховуючи целочисленности змінних. Нехай таким є план 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 не задовольняє умові целочисленности, і отже, перестав бути оптимальним планом вихідної завдання.

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

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

(I) (II)

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

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

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

(III)

(IV)

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

Отже вихідна завдання целочисленного програмування має оптимальний план Х*= (3, 1, 2, 3, 3). У цьому плані цільова функція приймає максимальне значення .

Схему реалізованого вище обчислювального процесу можна як дерева, гілками якого є відповідні обмеження на перемінні, а вершинами – рішення відповідних завдань лінійного програмування (рис 2.5).

Дамо геометричну інтерпретацію виконання завдання (50)-(53). На рис. 2.6 показано область допустимих рішень завдання (50)-(52).

З нього видно, що це завдання має оптимальний план(18/5, 3/5, 0, 0, 24/5). У той самий час перестав бути планом завдання (50)-(53), оскільки три перемінні мають дробные значення. Візьмемо зміну x1 і розглянемо завдання (I) і (II).

Як очевидно з рис. 2.7задача (I) має оптимальний план (3, 3/2, 0, 9/2, 3/2), та якщо з рис.2.8 слід, що завдання (II) нерозв'язна.

Оскільки серед компонент плану є дробные числа, виберемо зміну x2 і розглянемо завдання (III) (IV). Завдання (III) має оптимальний план(3, 1, 2, 3, 3) (рис. 2.9), а завдання (IV) нерозв'язна (рис. 2.10).

Отже, Х*= (3, 1, 2, 3, 3) є оптимальним планом завдання (50)-(53). У цьому плані .

Рішення завдання, праві частини, яких містять параметр.

Алгоритм виконання завдання (60)-(62) подібний до розглянутому вище алгоритму виконання завдання (57)-(59).

Вважаючи значення параметра t рівним деякому числу t0, знаходимо рішення отриманої завдання лінійного програмування (60)-(62). При даному значенні параметра t0 або визначаємо оптимальний план, або встановлюємо нерозв'язність завдання. У першому випадку знайдений план є оптимальним нічого для будь-якого, де

і кількості qі і pі визначено компонентами оптимального плану і залежить від t0:

            Якщо за t = t0 завдання (60)-(62) нерозв'язна, то, або цільова функція завдання (60) не обмежена на безлічі планів, або система рівнянь немає неотрицательных рішень. У першому випадку завдання нерозв'язна всім , тоді як у другий випадок визначаємо все значення параметра , котрим система рівнянь (61) несовместна, і виключаємо їх із розгляду.

            Після визначення проміжку, у якому завдання (60)-(62) має і той ж оптимальний план чи нерозв'язна, вибираємо нового значення параметра t, не те що знайденому проміжку, і знаходимо рішення отриманої завдання лінійного програмування. У цьому рішення нового завдання шукаємо з допомогою дієвого симплекс-метода. Продовжуючи итерационный процес, після кінцевого числа кроків отримуємо вирішення завдання (60)-(62).

            Отже, процес перебування завдання (60)-(62) входять такі основні етапи:

            10. Вважаючи значення параметра t рівним деякому числу , знаходять оптимальний план чи встановлюють нерозв'язність отриманої завдання лінійного програмування.

            20. Знаходять значення параметра , котрим завдання (60)-(62) має і той ж оптимальний план чи нерозв'язна. Ці значення параметра t виключають із розгляду.

            30. Вибирають значення параметра t із решти частини проміжку і встановлюють можливість визначення нового оптимального плану знаходять його двоїстим симплекс-методом.

            40. Визначають безліч значень параметра t, котрим завдання має і той ж, новий оптимальний план чи нерозв'язна. Вычисления проводять до того часу, коли будуть досліджені все значення параметра .

            2.66. До кожного значення параметра знайти максимальне значення функції

за умов

Р е ш е зв і е . Вважаючи значення параметра t у системі рівнянь (81) рівним нулю, знаходимо вирішення завдання (80)-(82) (табл. 2. 41).

Таблиця 2.41

і

Базис

Зб

Р0

3 -2 5 0 -4

Р1

Р2

Р3

Р4

Р5

1

Р3

5

12+t

1 1 1 0 0
2

Р4

0

8+4t

2 -1 0 1 0
3

Р5

-4

10-6t

-2 2 0 0 1
4

 

20+29t

10 -1 0 0 0
1

Р3

5

7+4t

2 0 1 0 -

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

Нові надходження

Замовлення реферату

Реклама

Навігація