Приведення довільної задачі лінійного програмування до канонічного вигляду

1. В більшості задач лінійного програмування обмеження задаються не у вигляді рівнянь, а у вигляді нерівностей, при чому можливі різні форми таких систем, наприклад:

або

Система обмежень може бути також змішаною, тобто в ній частина обмежень записана у вигляді рівнянь, частина – у вигляді нерівностей. Але будь-яку систему обмежень можна привести до системи рівнянь вигляду (2.18). Для цього достатньо до лівої частини кожної нерівності додати або відняти невід’ємне число – додаткову змінну такої величини, щоб відповідна нерівність стала рівністю – перетворилась в рівняння.

Нехай система обмежень задана у вигляді нерівностей

Від лівої частини кожної з перших нерівностей віднімемо відповідну додаткову невід’ємну змінну , а до лівої частини кожної з останніх нерівностей додамо невід’ємну змінну . В результаті, замість системи обмежень, отримаємо еквівалентну систему рівнянь, аналогічну системі (2.18):

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

2. Часто в задачах лінійного програмування доводиться шукати найменше значення лінійної форми (2.19). Такі задачі теж легко зводяться до канонічного вигляду. Досить ввести в розгляд функцію , тоді для знаходження найменшого значення функції потрібно знайти найбільше значення функції .

Дата добавления: 2017-02-01