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

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

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

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

або

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

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

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

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

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

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

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

або

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

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

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

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

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

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

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

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

(2.1)

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

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

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

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

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

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