Стандартна форма канонічного вигляду злп

Наведені приклади математичних моделей ЗЛП розрізнялись виглядом шуканого екстремуму й типом співвідношень у системі основних обмежень. Систему основних обмежень задачі використання ресурсів подано нерівностями типу „ ” , задачі складання раціону – нерівностями типу „ ”.

Можливі також обмеження-рівності та мішані системи основних обмежень, що містять рівняння та нерівності будь-якого вигляду.

Природно, що в процесі обґрунтування методу розв’язування виникає проблема універсалізації, тобто процедуру яку можна застосувати до всіх можливих типів ЗЛП, або має існувати спосіб зведення всіх можливих ЗЛП до одного типу.

Другий підхід більш практичний.

Означення 2.4. ЗЛП називається заданою в канонічному вигляді, якщо її систему основних обмежень подано рівняннями.

Щоб звести ЗЛП до канонічного вигляду, в системі основних обмежень треба перейти від нерівностей до рівнянь, ввівши додаткові змінні на підставі наступних теорем про заміну нерівностей рівняннями.

Теорема 2.1. Нерівність

q(x₁,x₂,…,x_n) b (2.19)

Еквівалентна системі

(2.20)

Аналогічно формулюють і доводять наступну теорему. Теорема2.2. Нерівність q(x₁,x₂,…,x_n) _b еквівалентна системі

Невід‘ємність додаткових змінних x_n+1 забезпечує збереження структури змінних ЗЛП, що, як зазначалося, мають бути невід‘ємними. Додаткові змінні входять до цільової функції з нульовими коефіцієнтами. Далі буде викладено економічне тлумачення цього факту.

Зведемо до канонічного вигляду математичну модель задачі використання ресурсів (2.9) – (2.11). Оскільки в системі основних обмежень m нерівностей і в кожне з них треба вводити додаткову змінну, то всього їх буде m: - у першому, - у другому і т.д., - у останньому.

Математичне модель набуде вигляду

Z = C₁x₁ + C₂x₂+…+C_nx_n +Ox_n+1 + Ox_n+2+…+Ox_n+m (max). (2.21)

(2.22)

(2.23)

Згідно з теоремою 2.1 задача (2.21)-(2.23)еквівалентна задачі (2.6),

тобто, знайшовши розв'язок (2.21)-(2.23) і відкинувши додаткові змінні, отримаємо розв'язок вихідної задачі. .Дійсно, нехай набір , - розв’язок ЗЛП (2.21)-(2.23). Тоді набір забезпечує цільовій функції те саме значення. Припустимо противне: Х₁ не є розв’язком ЗЛП (2.4) – (2.6), тобто існує набір Х₂, що забезпечує більше значення цільової функції (2.4). Набору Х₂ відповідає набір Х₃, отриманий додаванням додаткових змінних, які входять до (2.21) з нульовими коефіцієнтами; отже, набір Х₃ забезпечує (2.21) більше значення, ніж , що суперечить умові, згідно з якою - розв’язок задач (2.21) – (2.23).

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

Аналогічно зводиться до канонічного вигляду математична модель задачі складання раціону (2.24) – (2.26):

Z = c₁x₁ +c₂x₂ +…+c_nx_n + Ox_n+1 + Ox_n+2 + …+ Ox_n+m (min) (2.24)

(2.25)

(2.26)

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

Означення 2.5. ЗЛП називається заданою в стандартній формі кано­нічного вигляду, якщо виконуються такі умови:

1/ система основних обмежень подається рівняннями й усі вони лі­нійно незалежні;

2/ число рівнянь менше від числа змінних;

З/ розв’язується задача мінімізації цільової функції;

4/вільні члени - праві частини системи основних обмежень –невід’ємні;

5/ на всі змінні накладається умова невід’ємності.

Зведення системи основних обмежень - якщо воно необхідне - можна здійснити, ввівши додаткові змінні. Лінійну незалежність рівнянь пе­ревіряють, обчислюючи ранг матриці системи.

Друга вимога випливає із властивостей розв’язання систем ліній­них рівнянь. У разі виконання першої умови, коли число рівнянь перевищує число невідомих, система несумісна й ЗЛП розв’яз­ків не має.

Якщо система основних обмежень квадратна, вона має єдиний розв’язок, отже, постановка ЗЛП недоцільна - немає можливості вибору варіанту. Лише в тому разі, коли число рівнянь менше від числа змінних, система основних обмежень сумісна та має незліченну множину розв’язків, Якщо при цьому є невід’ємні розв‘язки, постановка ЗЛП має смисл.

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

Вимога невід’ємності правих частин стане очевидною в процесі викладення методу розв'язування ЗЛП. Зазначимо, що коли деяке b < 0, то, помноживши це рівняння не -1, можна досягти виконання цієї умови .

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

Надалі, крім окремо обумовлених випадків, під ЗЛП розумітимемо ЗЛП, задану в стандартній формі канонічного вигляду.