Канонічна форма задачі лінійного програмування

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

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

У звязку з цим домовились кожен з типів зводити до єдиної форми , яку назвали канонічна форма.Ця форма проста і зручна для дослідження. Вважатимемо, що ЗЛП записана у канонічній формі, якщо вона формулюється наступним чином:

max

.

Введемо позначення: , , ,

За таких позначень канонічна форма задачі набуде вигляду:

,

,

,

або, використавши введені вище позначення, отримаємо компактний запис ЗЛП:

Це матрична форма запису канонічної задачі лінійного програмування (матриця А називається матрицею умов задачі).

Ми будемо також використовувати так звану векторну форму запису канонічної задачі лінійного програмування, тому для стовпців матриці А введемо позначення:

, ,...,

Тоді задачу лінійного програмування можна записати так:

Це векторна форма запису канонічної задачі лінійного програмування.

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

Покажемо, як будь-яку задачу лінійного програмування звести до канонічного виду. Нехай задача лінійного програмування має вигляд:

(4)

(5)

(6)

(7)

Введемо додаткових невід'ємних змінних , ,…, .Для того, щоб нерівності (5) перетворити в рівності, до їх лівих частин додамо додаткові змінні , ,…, .Після цього система нерівностей (5) набуде вигляду:

Віднявши від лівих частин обмежень (6) додаткові невід'ємні змінні ,…, , отримаємо:

Додаткові змінні в цільову функцію введемо з коефіцієнтами, рівними нулеві. Отримаємо задачу:

(8)

(9)

(10)

(11)

Між задачею (4)-(7) і задачею (8)-(11) є тісний зв'язок, а саме: кожному допустимому розв’язку задачі (4)-(7) відповідає повністю визначений розв'язок задачі (8)-(11), де для обмежень (9) виконується

а для обмежень (10) справедливо:

Справедливим є і обернене твердження: кожному допустимому розв'язку задачі (8)-(11) відповідає повністю визначений допустимий розв’язок задачі (4)-(7) ( і їх відкидання в лівих частинах рівностей (9) і (10) робить твердження очевидним).

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

Приклад. Звести до канонічного виду задачу:

Вводимо додаткові змінні , змінну додамо до лівої частини першого обмеження, а змінну віднімемо від лівої частини другого обмеження. Отримаємо еквівалентну задачу у канонічному виді:

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

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

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

Щоб отримати оптимальне значення вихідної задачі, треба взяти оптимальне значення перетвореної задачі із оберненим знаком.

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

(12)

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

Приклад. Звести до канонічного виду задачу лінійного програмування:

Відповідь:

Поиск по сайту: