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

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

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

Сторінка 2

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

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

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

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

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

Оскільки серед компонент плану є дробные числа, виберемо зміну х2 і розглянемо завдання (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 або визначаємо оптимальний план, або встановлюємо нерозв'язність завдання. У першому випадку знайдений план є оптимальним нічого для будь-якого, де

і кількості qi і pi визначено компонентами оптимального плану і залежить від 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

-


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

Статистика

1 [2] 3 4