3.2. Стандартна форма лінійних оптимізаційних моделей

У загальному випадку права та ліва частини обмежень лінійної моделі можуть бути пов’язані знаками ,  або =. Крім того, змінні задачі можуть бути невід’ємними або не мати обмеження на знак. Для побудови загального методу розв’язання задач ЛП відповідні моделі мають бути представлені в деякій формі, яку назвемо стандартною формою лінійних оптимізаційних моделей. Стандартна форма лінійної моделі відповідає наступним вимогам:

1) всі обмеження записані у вигляді рівнянь з невід’ємною правою частиною;

2) значення всіх змінних моделі є невід’ємними;

3) цільова функція підлягає максимізації або мінімізації.

  Покажемо, яким чином лінійну модель довільного виду можна при¬вести до стандартної форми.

Обмеження:

1. Вихідне обмеження - нерівність із знаком  (або ) можна подати у вигляді рівняння, додаючидо лівої частини обмеження невід’ємну залишкову змінну (або віднімаючи надлишкову змінну). Наприклад, до лівої частини вихідного обмеження

X1+2x26

Додається залишкова змінна x3 0, в результаті чого вихідна нерівність обертається на рівняння

X1+2x2+ x3=6.

Якщо вихідне обмеження визначає витрати деякого ресурсу, то змінну x3 слід інтерпретувати як залишок або невикористану частину даного ресурсу. Розглянемо обмеження іншого типу:

3х1+2х25.

Оскільки ліва частина цього обмеження не може бути меншою від правої, для обернення вихідної нерівності на рівняння віднімемо від його лівої частини надлишкову змінну х30. В результаті отримаємо: 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 , де y0, y  0.

Таку підстановку слід зробити в усіх обмеженнях, які містять вихідну змінну y, а також у рівнянні цільової функції. Після цього знаходять розв’язок задачі ЛП, в якому фігурують змінні y та у", а потім за допомогою зворотної підстановки визначають величину y. Наприклад, якщо змінні y1, y2, y3 деякої задачі ЛП не мають обмежень на знак, а в оптимальному розв’язку y1=0, у"1=6; y2=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 и відняти від його лівої частини надлишкову змінну x30.

 2. Додати залишкову змінну x40 до лівої частини третього обмеження.

 3. В цільовій функції та в усіх обмеженнях виконати підстановку: 

X1= x1- x1 , де x10, x1  0.

Названі операції дозволяють звести вихідну модель до стандартної форми:

Мінімізувати  z= 2x1- 2x1+З x2 при обмеженнях