На головну

Метод відсікань. Формулювання вірного відсікання. алгоритм методу

  1. B) Систематизація конкретно-наукових і загальнонаукових методів пізнання.
  2. D. Симплекс-метод
  3. FDDI. Архітектура мережі, метод доступу, стек протоколів.
  4. I. Внесення відомостей в форму ДМВ-1 при використанні методу визначення митної вартості за ціною угоди із ввезених товарів
  5. I. МЕТОДИКА
  6. I. Методичні вказівки для виконання контрольних робіт
  7. I. Методичні вказівки з підготовки

суть методу відтинають площин полягає в наступному:

1. Спочатку вирішується завдання з відкинутим умовою целочисленности.

2. За отриманими результатами робляться такі висновки:

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

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

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

- Якщо рішення на області Dнц є нецілочисельне, то здійснюється перехід до 3-го етапу.

3. Складається додаткове обмеження, яке називається правильним

відсіканням. Правильне відсікання повинно відповідати таким

вимогам:

- Бути лінійним

- Відсікати знайдене оптимальне нецелочисленное рішення задачі.

4. Здійснюється повернення до задачі лінійного програмування з

відкинутим умовою целочисленности, але з розширеною системою обмежень, в яку включено додаткове обмеження отримане на 3-му етапі. Розширена задача вирішується якщо знайдене оптимальне рішення

буде знову нецілим, то формуємо нове додаткове обмеження і процес повторюємо.

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

- Оптимальне рішення задачі з розширеною системою обмежень є оптимальним рішенням вихідної задачі.

- З порожнечі допустимої області розширеної задачі слід порожнеча допустимої області вихідної задачі.

З геометричної точки зору, кожному додатковому обмеженню в n-вимірному просторі відповідає певна гіперплоскость відсікає від багатокутника рішень деяку його частину, включаючи і оптимальну на даному етапі нецілочисельне вершину. При цьому всі точки з цілочисельними координатами, в тому числі і шукана оптимальна, знаходяться всередині цього багатокутника. Т. к. Безліч цілих точок усіченого багатогранника збігається з безліччю цілих точок вихідного багатогранника - це значить, що якщо оптимальне рішення задачі на усіченому многограннике задовольняє умові целочисленности, то воно і є оптимальним цілочисельним рішенням вихідної задачі. Через кілька операцій відсікання шукана целочисленная точка виявляється спочатку на кордоні області, а потім стає вершиною, неодноразово усіченого багатогранника рішень. У тому випадку якщо багатогранник рішень не містить жодної целочисленной точки, то скільки б не вводили правильних відсікань целочисленное рішення отримати не можна.



Математичне формулювання завдань дискретного програмування | Переваги та недоліки алгоритму.

Формування нижніх і верхніх оцінок цільової функції | алгоритм методу | комбінаторні методи | Метод лексикографічного перебору | Метод неявного перебору по векторної решітці | наближені методи | Алгоритм симплекс методу | Друга стандартна форма | Вихідна задача в канонічній формі | Xi |

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