My_horosho_postaralis_2003_WORD

48.Правила побудови двоїстих задач

Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду « », а для задачі на відшукання мінімального значення — до виду « ».

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.

4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.

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

6. Матриця

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

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.

Процес побудови двоїстої задачі зручно зобразити схематично:

Пари задач лінійного програмування бувають симетричні та несиметричні.

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

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

№ 49 Геометрична інтепретація задачі нелінійного програмування на площині. Нелінійна цільова функція і нелінійні обмеження обмеження.

(8.1)

за умов:

( ); (8.2)

. (8.3)

Геометрично цільова функція (8.1) визначає деяку поверхню, а обмеження (8.2)—(8.3) — допустиму підмножину n-вимірного евклідового простору.

Знаходження оптимального розв’язку задачі нелінійного програмування зводиться до відшукання точки з допустимої підмножини, в якій досягається поверхня найвищого (найнижчого) рівня.

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

Найпростішими для розв’язування є задачі нелінійного програмування, що містять систему лінійних обмежень та нелінійну цільову функцію. В цьому разі область допустимих розв’язків є опуклою, непустою, замкненою, тобто обмеженою.

Розглянемо приклад геометричного способу розв’язування задачі нелінійного програмування.

З найти мінімальне значення функції:

за умов:

Розв’язування. У даному прикладі множина допустимих розв’язків складається з двох окремих частин, необмежених зверху (рис. 8.2). Цільова функція аналогічно попередньому випадку є колом з центром у точці М (4; 4). Функція Z має два локальних мінімуми: в точці А ( ), і в точці В ( ).

Значення функціонала в цих точках однакове і дорівнює:

Отже, маємо два альтернативні оптимальні плани.

Даний приклад ілюструє ще одну особливість задач нелінійного програмування: на відміну від задач лінійного програмування багатогранник допустимих розв’язків задачі нелінійного програмування не обов’язково буде опуклою множиною.

Наведемо основні особливості задач нелінійного програмування, що зумовлюють необхідність застосування відповідних методів їх розв’язання.

№ 50 Симетричні та несиметричні двоїсті пари лінійного програмування

Пари задач лінійного програмування бувають симетричні та несиметричні.

Теорема двоїстості:

истема обмежень вихідної задачі в несиметричних двоїстих завданнях визначається як рівність. Двоїста ж завдання задається, як нерівність, причому змінні можуть бути і негативними. Що б простіше розуміти постановку завдання будемо інтерпретувати її в матричній формі. Сформулюємо двоїсту задачу. Необхідно визначити матрицю-рядок Y = (y 1, y 2, ..., y m), яка максимізує лінійну функцію f = YA 0 і задовольняє обмеженням YA> З (1.1) Сформулюємо вихідну завдання. Визначити матрицю-стовпець X = (x 1, x 2, ..., x n), яка мінімізує лінійну функцію Z = СХ і. задовольняє обмеженням AX = A0, Х> 0 (1.2) Як у вихідної так і в двоїстої задачах А = (a ij) - матриця коефіцієнтів системи обмежень, A 0 = (b 1, b 2, ..., b m) - матриця-стовпець, C = (c 1, c 2, ... , c n) - матриця-рядок. Теорема двоїстості встановлює зв'язок між оптимальними планами пари двоїстих задач. Теорема двоїстості говорить: якщо з пари двоїстих завдань одну володіє оптимальним планом, то й інша має рішення, причому для екстремальних значень лінійних функцій виконується співвідношення minZ = maxf. Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення Доказ. Будемо вважати, що вихідна задача має оптимальний план. План визначено симплексним методом. Можна вважати, що кінцевий базис складається з т перший векторів A 1, A 2, ..., A m. Будемо вважати, що D є матрицею, складеною з компонент векторів кінцевого базису A 1, A 2., A m Наведена вище таблиця складається з коефіцієнтів розкладання векторів A 1, A 2, ..., A n вихідної системи по векторах базису. У цій таблиці кожному вектору A j відповідає вектор X j. Використовуючи співвідношення (1.3) та (1.4), отримуємо: (1.5) A = D, D -1 A = (1.6) A 0 = DX *; D -1 A 0 = X (1.7) min Z = C * X *, (1.8) = C * - C> 0, де С = (C 1, C 2, ..., C m), С = (C 1, C 2, ..., C m, C m +1, ..., C n), a = (CX 1-C 1; СХ 2 - З 2, ..., CX n-C n) = (Z 1-С; Z 2-C 2; ..., Z n-C n) - вектор, компоненти якого непозитивно, так як вони співпадають з Z j - C j> 0, відповідними оптимальному плану. Оптимальний план вихідної задачі має вигляд X = D -1 А 0, тому оптимальний план двоїстої задачі шукаємо у вигляді (1.9) Y = C * D -1 Таким чином, значення лінійної функції двоїстої задачі від Y чисельно дорівнює мінімальному значенню лінійної функції вихідної задачі Симетричні двоїсті задачі

Різновидом двоїстих задач лінійного, програмування є подвійні симетричні завдання, в яких система обмежень як вихідної, так і двоїстої задач задається нерівностями, причому на двоїсті змінні накладається умова позитивності. Вихідна задача. Знайти матрицю-стовпець Х = (x 1, x 2, ..., x n), яка задовольняє системі обмежень (1.12). АХ> А 0, Х> 0 і мінімізує лінійну функцію Z = СХ Систему нерівностей за допомогою додаткових змінних можна перетворити в систему рівнянь, тому будь-яку пару симетричних двоїстих завдань можна перетворити в пару несиметричних, для яких теорема подвійності вже доведена. Використовуючи симетричність, можна вибрати завдання, більш зручну для вирішення. Обсяг завдання, розв'язуваної за допомогою ЕОМ, обмежений числом включаються рядків, тому завдання, досить громіздка у вихідній постановці, може бути спрощена в двоїстої формулюванні. При обчисленнях без допомоги машин використання подвійності спрощує обчислення. Очевидно, для того щоб записати двоїсту задачу, спочатку необхідно систему обмежень вихідної задачі привести до виду. Для цього друга нерівність слід помножити на -1.

Содержание