Page 26 - 4729

Практичне заняття № 3

Тема : АНАЛІТИЧНИЙ РОЗВ’ЯЗОК ЗАДАЧ ОПТИМІЗАЦІЇ МЕТОДОМ
ЛІНІЙНОГО ПРОГРАМУВАННЯ .СИМПЛЕКС МЕТОД.

3.1 Мета і тривалість заняття:
-Набуття навиків розв’язку задач ЛПР симплекс методом.

-Тривалість заняття 4 год.

3.2 Основні теоретичні відомості

Розв’язок задач лінійного програмування (ЛП) симплекс методом

починається із приведення її до" канонічної форми, тобто обмеження-

нерівності замінюються на обмеження-рівності. Це перетворення здійснюють

шляхом введення невід’ємних базисних змінних u n+1> 0 в ліві частини

нерівностей із знаком «+» або «-» в залежності від знака нерівностей.

Якщо обмеження задачі подані у вигляді:

(3.1)

s= ; u j>0,

то для розв’язку задачі в ці рівняння вводять тільки базисні змінні. Якщо

обмеження подані у вигляді:

(3.2)

то крім базистих змінних в обмеження вводять ще штучні змінні. Для

полегшення розв’язку задачі складають симплекс-таблицю. В загальному

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

24