3.2. Стандартна форма лінійних оптимізаційних моделей
У загальному випадку права та ліва частини обмежень лінійної моделі можуть бути пов’язані знаками , або =. Крім того, змінні задачі можуть бути невід’ємними або не мати обмеження на знак. Для побудови загального методу розв’язання задач ЛП відповідні моделі мають бути представлені в деякій формі, яку назвемо стандартною формою лінійних оптимізаційних моделей. Стандартна форма лінійної моделі відповідає наступним вимогам:
1) всі обмеження записані у вигляді рівнянь з невід’ємною правою частиною;
2) значення всіх змінних моделі є невід’ємними;
3) цільова функція підлягає максимізації або мінімізації.
Покажемо, яким чином лінійну модель довільного виду можна при¬вести до стандартної форми.
Обмеження:
1. Вихідне обмеження - нерівність із знаком (або ) можна подати у вигляді рівняння, додаючидо лівої частини обмеження невід’ємну залишкову змінну (або віднімаючи надлишкову змінну). Наприклад, до лівої частини вихідного обмеження
X1+2x26
Додається залишкова змінна x3 0, в результаті чого вихідна нерівність обертається на рівняння
X1+2x2+ x3=6.
Якщо вихідне обмеження визначає витрати деякого ресурсу, то змінну x3 слід інтерпретувати як залишок або невикористану частину даного ресурсу. Розглянемо обмеження іншого типу:
3х1+2х25.
Оскільки ліва частина цього обмеження не може бути меншою від правої, для обернення вихідної нерівності на рівняння віднімемо від його лівої частини надлишкову змінну х30. В результаті отримаємо: 3х1+2х2-х3=5.
2. Праву частину обмеження завжди можна зробити невід’ємною, помноживши обидві його частини на -1.
Наприклад, рівняння 2х1-х2=-5 є еквівалентним рівнянню 2х1+x2=5.
Знак нерівності замінюється на протилежний при м¬ноженні обох його частин на -1. Наприклад, можна замість x >-4 записати -x<4.
3. Будь яку змінну y, що не має обмеження на знак, можна подати у вигляді різниці двох невід’ємних змінних:
Y=y-y , де y0, y 0.
Таку підстановку слід зробити в усіх обмеженнях, які містять вихідну змінну y, а також у рівнянні цільової функції. Після цього знаходять розв’язок задачі ЛП, в якому фігурують змінні y та у", а потім за допомогою зворотної підстановки визначають величину y. Наприклад, якщо змінні y1, y2, y3 деякої задачі ЛП не мають обмежень на знак, а в оптимальному розв’язку y1=0, у"1=6; y2=10, у"2=0; y'3=y"3=0, то відповідні значення вихідних змінних складатимуть: y1=-6, y2=10, y3=0.
Важливою особливістю змінних y, y є те, що завжди, при будь-якому допустимому розв’язку, одна з цих змінних приймає додатне значення, а друга - нульове. Тобто, якщо y>0, то , y =0 і навпаки, якщо y>0, то y=0 . Це дозволяє розглядати y як залишкову змінну, а у"- як надлишкову. Вказана закономірність широко застосовується в цільовому програмуванні.
Цільова функція. Цільова функція лінійної оптимізаційної моделі в стандартній формі може підлягати як максимізації, так і мінімізації. В деяких випадках виявляється доцільним замінити вихідну цільову функцію. Максимізація деякої функції є еквівалентною мінімізації тієї ж функції, взятої з протилежним знаком. Наприклад, мінімізація функції:
Z=5x1+2x2+3x3
Є еквівалентною мінімізації функції (-z) = - 5x1 - 2x2 - 3x3 .
Еквівалентність означає, що при одній і тій самій сукупності обмежень оптимальні значення змінних x1 , x2 , x3 в обох випадках будуть однакові. Відмінність полягає в тому, що при однакових числових значеннях цільових функцій їх знаки будуть протилежними.
Приклад 3.1. Потрібно подати у стандартній формі наступну лінійну модель:
Мінімізувати z=2x1+3x2 при обмеженнях
Необхідно виконати наступні перетворення.
1. Помножити друге обмеження на -1 и відняти від його лівої частини надлишкову змінну x30.
2. Додати залишкову змінну x40 до лівої частини третього обмеження.
3. В цільовій функції та в усіх обмеженнях виконати підстановку:
X1= x1- x1 , де x10, x1 0.
Названі операції дозволяють звести вихідну модель до стандартної форми:
Мінімізувати z= 2x1- 2x1+З x2 при обмеженнях
25 26 27 28 29 Наверх ↑