Зведення ЗЛП до канонічної форми

Вважають, що ЗЛП записана в канонічній формі, якщо вона має вигляд:

(8)

(9)

де , , – задані сталі величини, припускаємо та . Будь-яку задачу лінійного програмування можна звести до канонічної форми. Розглянемо можливі відхилення в запису ЗЛП від канонічної форми і шляхи їхніх усунень.

1. Якщо в ЗЛП необхідно знайти максимумлінійної форми (8), то, з огляду на те, що , задача зводиться до пошуку мінімуму лінійної форми .

2. Якщо частина або всі обмеження мають вигляд лінійних нерівностей

, (10)

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

.

3. Якщо частина або всі обмеження мають вигляд лінійних нерівностей

, (11)

то для зведення ЗЛП до вигляду (8), (9) необхідно в лівих частинах таких нерівностей відняти невід'ємні змінні і замість нерівності (11) взяти рівняння вигляду

.

При цьому додаткові змінні входять у лінійну форму з нульовими коефіцієнтами.

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

де .

Приклад 3.

Звести до канонічної форми ЗЛП:

Розв'язання. Зведення ЗЛП до канонічної форми (8), (9) будемо проводити поетапно.

1. З огляду на п. 1, перейдемо до задачі на мінімум:

2. Використовуючи рекомендації п. 2, введемо додаткові змінні , , тоді замість нерівностей

одержимо рівняння:

Тоді система обмежень прймає вигляд:

3. На змінну не накладають умови невід’ємності, тоді, з огляду на рекомендації п. 3, зробимо заміну і остаточно одержимо ЗЛП, записану у формі (8), (9):

Дата добавления: 2014-12-25