Головна

Взаємно-двоїсті задачі лінійного програмування.

  1. I. Завдання семіотики і передумови, необхідні для її розробки
  2. I. До чого прагне педагогіка, якою вона має бути і в чому її завдання?
  3. I. Основні завдання
  4. I. Основні завдання ЗОВНІШНЬОЇ ПОЛІТИКИ
  5. I. Поняття, основні принципи, цілі, завдання та напрями забезпечення безпеки дорожнього руху.
  6. II. ЗАВДАННЯ аеродромного ПОЖЕЖНО-РЯТУВАЛЬНОЇ СЛУЖБИ В РАЗІ ВІЙНИ
  7. III. Завдання з рішеннями

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

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

Постановка взаємно-двоїстої задачі:

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

Нехай є 2 види сировини S1 і S2 , Залишки якого складають

S1 = 8 од. сировини

S2 = 9 од. сировини

З цієї сировини можна налагодити виробництво двох видів товару Т1 і Т2 про реалізацію кожного виду товару завод отримує прибуток від Т1 - 1 руб. / Шт., Від Т2 - 1 руб. / Шт. Норми витрати сировини S1 на виробництво одиниці товару Т1 складають 2 одиниці, а на виробництво Т2 - 1 одиниця. витрати S2 на Т1 - 1 одиниця, S2 на Т2 - 3 одиниці.

Пряма задача.

 Види товараВіди ресурсу Т1 Т2  запаси ресурсів
S1
S2
 Прибуток від виробництва одиниці товару  

х1 - Оптимальна кількість Т1

х2 - Оптимальна кількість Т2

f (x) = x1 + x2  max

Двоїста задача.

у1 - Ціна одиниці сировини S1

у2 - Ціна одиниці сировини S2

z (y) = 8y1 + 9y2  min

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

Цільова функція розглядається з точки зору покупця, т. Е. Скорочення до мінімуму витрат на покупку сировини.

під у1 і у2 розуміються не ринкові ціни, а ціни для внутрішнього користування підприємства або «об'єктивно-обумовлені оцінки».

Якщо до двоїстої задачі знову побудувати двоїсту задачу, то отримаємо вихідну задачу.

Не одна з двоїстих задач не є основною, т. Е. Якщо поставлена ??одна з задач, то інша може бути сформульована як двоїста і кожна з них є двоїстої по відношенню до іншої.

Вирішимо обидва завдання графічно.

В - точка максимуму

х1 = 3, х2 = 2

f (x)max = 3 + 2 = 5

у1 = 0,4; у2 = 0,2

в (0,4; 0,2)

z (y)min = 8 * 0.4 + 9 * 0.2 = 5

f (x)max = Z (y)min = 5

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

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

1. В одному завданню шукають максимум лінійної функції, а в інший мінімум.

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

3. Обидві задачі в стандартному вигляді, причому в задачі максимізації все нерівності виду «  », А в задачі мінімізації -«  ».

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

5. Число нерівностей в системі обмежень однієї задачі збігається з числом змінних в іншому завданні.

6. Умови невід'ємності змінних є в обох завданнях.

Дві завдання лінійного програмування, що володіють вказаними властивостями, називаються симетричними взаємно-подвійними завданнями.

Виходячи з визначення, можна запропонувати наступний алгоритм складання взаємно-двоїстої задачі:

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

2. Скласти розширену матрицю системи А1, В яку включити матрицю при змінних, а стовпець вільних членів системи обмежень і рядок коефіцієнтів при змінних в лінійній функції записати праворуч і знизу відповідно.

3. Знайти матрицю,  транспоновану до матриці А1.

4. Сформувати взаємно-двоїсту задачу на підставі отриманої матриці  і умовах невід'ємності змінних.

вихідна задача

f (x) = -x1 + 2x2  max

z (y) = -y1 + 24y2 + 3y3 - 5y4  min

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

Якщо в оптимальному плані однією з взаємно-двоїстих задач значення основної змінної позитивно, то відповідна їй допоміжна змінна іншої задачі дорівнює 0 і, навпаки, з позитивності допоміжної змінної слід рівність 0 відповідної їй основною змінною в оптимальному плані взаємно-двоїстих задач.

Зробимо деякі перетворення.

1. Наведемо обидва завдання до канонічного вигляду; запишемо це перетворення в загальному вигляді

пряма задача

двоїста задача

пряма задача

двоїста задача

Системи лінійних рівнянь містять m + n невідомих в першій з них n основних змінних і m допоміжних змінних, а в другій навпаки m основних змінних, n допоміжних змінних.

Складемо таблицю відповідності змінних в двох завданнях

 I  Основні змінні  допоміжні змінні
x1, x2, ... Xn xn + 1, xn + 2, ... Xn + m
 II  ym + 1, ym + 2, ... Ym + n  y1, y2, ... Ym
 допоміжні змінні  Основні змінні

Відповідність між змінними не змінюється при вирішенні задачі

Для даної задачі

 I  Основні змінні  допоміжні змінні
 3 2 x1, x2  0 0 x3, x4
 II  y3, y40 0  y1, y20,4 0,2
 допоміжні змінні  Основні змінні

х3 = 8 - (2х1 + х2)

х4 = 9 - (х1 +3 х2)

у3 = (2у1 + у2) - 1

у4 = (У1 +3 у2) - 1

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

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

Якщо ми маємо основні змінні нульові, то ми маємо перевищення витрат на ресурси над ціною їх реалізації, т. Е. Маємо об'єктивно-обумовлені оцінки рівні нулю.

Вирішуємо пряму задачу симплекс-методом

f (x) = x1 + x2  max

- F (x) = - x1 - x2  min

     -1  -1  
   базові змінні  зведені члени x1 x2 x3 x4  
х3  -1  
x4  9/3  1 /  3/1  0/0  1 /
   f (x)  
             
     -1  -1  
   базові змінні  зведені члени x1 x2 x3 x4  
х3  5/3  / 1  1 / -  / -5
 -1 x2  
   f (x)  -3 -  
             
     -1  -1  
   базові змінні  зведені члени x1 x2 x3 x4  
 -1 х1  -5  
 -1 х2 -  
   f (x)  -5 - -  
               

f (x)max = 5, при

х1 = 3

х2 = 2

х3 = 0

х4 = 0

f (x)max = Z (y)min = 5

 




Лекція №1. 8 сторінка | Лекція №1. 9 сторінка | Лекція №1. 10 сторінка | Лекція №1. 11 сторінка | Лекція №1. 12 сторінка | Лекція №1. 13 сторінка | Лінійне програмування. Загальні завдання оптимізації. | Графічний метод рішення задач лінійного програмування. | Рішення задач лінійного програмування симплекс-методом. | М-метод розв'язання задач лінійного програмування. |

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