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

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

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

Інститут нафти і газа.

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

У галузях ТЭК.

Контрольна робота по.

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

Варіант № 4.

Виконав: студент гр.

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

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

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

[pic] при условиях.

[pic].

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

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

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

[pic].

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

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

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

[pic] при условиях[pic].

[pic] xj — цілі (j=[pic]).

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

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

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

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

(I)[pic] (II)[pic].

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

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

[pic].

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

[pic](III) [pic].

(IV) [pic].

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

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

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

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

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

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

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

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

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

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

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

[pic] і кількості qi і pi визначено компонентами оптимального плану і залежить від t0:

[pic].

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

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

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

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

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

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

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

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

[pic] при условиях.

[pic] Р е ш е зв і е. Вважаючи значення параметра 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 |-Ѕ | |2 |Р4 |0 |13+t |1 |0 |0 |1 |Ѕ | |3 |Р2 |-2 |5−3t |-1 |1 |0 |0 |Ѕ | |4 | | |25+26t |9 |0 |0 |0 |Ѕ |.

Як очевидно з табл. 2.41, [pic]при t =0 є оптимальний план завдання. Проте [pic] є оптимальним планом і тоді у його компонентів не виявиться негативних чисел, тобто. при 5−3t[pic]0; 7+4t[pic]0; 13+t[pic] або за [pic] Отже, якщо [pic] то[pic]- оптимальний план завдання (80)-(82), у якому [pic].

Досліджуємо тепер, чи є завдання оптимальні плани при [pic][pic]. Якщо [pic], то 5−3t17/2, то [pic]не є планом завдання, оскільки третя компонента 17 — 2t є негативне число. Оскільки серед елементів 1-ї рядки табл. 2.42 немає негативних при t>17/2 вихідна завдання неразрешима.

Досліджуємо тепер разрешимость завдання при t< -7/4. І тут Х= (0,5 -3t, 7+4t, 13+t, 0) (див. табл.2.41) перестав бути планом завдання, оскільки третій компонент 7+4t є негативне число. Щоб при даному значенні параметра знайти оптимальний план (можна зробити, позаяк у рядку вектора Р3 стоїть негативне число -½), потрібно вилучити з базису вектор Р3 і введення в базис вектор Р5 (табл. 2.43).

Таблиця 2.43 і |Базис |Рб |Р0 |3 |-2 |5 |0 |-4 | | | | | |Р1 |Р2 |Р3 |Р4 |Р5 | |1 |Р5 |- 4 |-14−8t |-4 |0 |-2 |0 |1 | |2 |Р4 |0 |20+5t |3 |0 |1 |1 |0 | |3 |Р2 |-2 |12+t |1 |1 |1 |0 |0 | |4 | | |32+30t |11 |11 |1 |0 |0 | |Як очевидно з табл. 2.43, [pic] є оптимальним планом завдання всім значень параметра t, у яких [pic].

Отже, якщо [pic], то завдання (80)-(82) має оптимальний план [pic], у якому [pic].

З табл. 2.43 як і видно, що з t.