Рекомендації щодо приведення задачі ЛП до канонічного виду

Приведення задачі ЛП до канонічного виду

Канонічний вид задачі ЛП:

Дано:

Знайти такий план , при якому

.

Задача ЛП представлена в канонічному виді, якщо виконуються наступні умови:

1. Всі змінні невід’ємні ( – умова невід’ємності).

2. Решта обмежень є лінійними рівняннями.

3. Функція мети мінімізується .

Будь-яку задачу ЛП можна звести до канонічного виду.

I. Забезпечення умови невід’ємності змінних:

1. Якщо на змінну взагалі не накладені ніякі обмеження, то необхідно виконати заміну: де

2. Якщо на змінну накладено обмеження виду то виконуємо заміну: де

3. Якщо на змінну накладено обмеження виду то виконуємо заміну: де

II. Перетворення обмежень-нерівностей у рівняння:

1. Нерівність заміняємо рівнянням , де

2. Нерівність заміняємо рівнянням , де

III. Забезпечення пошуку найменшого значення :

якщо , то

Дата добавления: 2014-11-06