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

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

Дано:

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

якщо , то

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

Симетричний вид задачі ЛП:

або

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

1. Умова невід’ємності змінних.

2. Решта обмежень системи є нерівностями виду „ ≤ ” і функція мети , або решта обмежень системи є нерівностями виду „ ≥ ” і функція мети

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

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

1. Дивись рекомендації щодо приведення задачі ЛП до канонічного виду.

2. Рівняння завжди можна замінити парою нерівностей

Тоді для симетричної постановки

або

Задача 2.2. Наступну задачу лінійного програмування

привести: а) до канонічного виду; б) до симетричного виду.

Рішення

а) Задача ЛП подана в канонічному виді, якщо виконані такі умови:

1. на кожну змінну накладено умову невід’ємності;

2. кожне з обмежень подано у виді лінійного рівняння;

3. функція мети має досягати мінімуму.

Задовольнимо першу умову.

Оскільки на змінну x₁ накладено умову , подамо її у виді(де), зміннуx₂ – у виді (де), зміннуx₃ заміняємо на u₃ (), оскількиx₄ не має обмежень, подамо її у виді різниці (де,). Підставимо ці співвідношення в систему обмежень і у функцію мети:

(2.1)

Задовольнимо другу умову.

Для того, щоб нерівності записати у виді рівностей, від лівої частини першої нерівності віднімемо нову балансову змінну u₆0, а до лівої частини другої нерівності додамо балансову змінну u₇0.

До функції мети змінні u₆ і u₇ входять з нульовими коефіцієнтами.

Для виконання третьої умови введемо функцію . У результаті одержимо канонічний вид задачі лінійного програмування

б) Використовуючи вигляд (2.1) даної задачі та рекомендації до зведення до симетричного виду, отримуємо

Перелік питань для самоперевірки

1. Геометричний метод розв’язування задач лінійного програмування з двома змінними, ілюстрація можливих випадків, які трапляються під час розв’язування задачі.

2. Задача лінійного програмування, форми її запису.

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

Змістовий модуль 2

Методика розв’язування

задач лінійного програмування (ЛП)

Лекція 3

Тема 3. Симплексний метод розв’язання задач ЛП

Симплексний метод є універсальним для розв’язання задачі лінійного програмування.

Схема розв’язання задачі лінійного програмування:

1. Подати задачу в канонічному виді (всі обмеження математичної моделі, крім умов невід’ємності, мають бути у виді рівностей, функція мети має бути мінімізована).

2. Знайти вихідний опорний план задачі – початковий допустимий базисний розв’язок системи рівнянь. Базисним називається розв’язок невизначеної системи, у якому вільні змінні дорівнюють нулю, а базисні (після приведення системи до одиничного базису) – відповідним елементам стовпця вільних членів. Базисний розв’язок називається допустимим, якщо всі його компоненти невід’ємні.

3. З’ясувати, чи є вихідний опорний план оптимальним.

4. Якщо опорний план не є оптимальний, то побудувати новий опорний план, більш “близький” до оптимального (з меншим значенням функції мети).