Постановка основної задачі лінійного програмування (ОЗЛП).

Припустимо, що мають місце n змінних х1, х2,..., xn. При цьому всі вони невід’ємні, тобто х1³0, х2³0,..., xn³0. Також мають місце m умов - обмежень, які виражають за допомогою m рівнянь:

(1)

Тобто, обмеження задані у вигляді рівнянь:

Цільова функція має вигляд:

Умова задачі: знайти невід’ємні значення змінних х1, х2,..., xn, які задовольняють системі рівнянь (1) і при яких цільова функція обертається в мінімум.

Якщо необхідно, щоб цільова функція оберталася в максимум, то треба змінити знак функції і розглянути функцію:

Допустиме рішення ОЗЛП – це деяка сукупність невід’ємних значень х1, х2,..., xn, які задовольняють системі рівнянь (1).

Оптимальне рішення ОЗЛП – це те рішення з допустимих, при якому цільова функція обертається в мінімум.

ОЗЛП може і не мати рішень у таких випадках:

– якщо система (1) несумісна, тобто її рівняння суперечать одне одному;

– якщо є рішення системи, але серед х1, х2,..., xn мають місце від’ємні значення;

– якщо є допустимі рішення, але цільова функція не обмежена знизу (немає оптимального рішення).

У випадку, коли n змінних дорівнює m рівнянням і рішення існує, то це рішення буде єдиним і оптимальним.

Основний випадок – коли n змінних більше m рівнянь.

З m рівнянь можна знайти значення тільки m змінних, які називають базисними. Решту n-m змінних називають вільними.

Якщо вільним змінним присвоїти деякі довільні значення, то решту - базисні змінні - можна однозначно визначити з m рівнянь. Така система має безліч рішень.

В окремих практичних задачах обмеження можуть задаватися нерівностями:

(2)

В цьому випадку, треба систему нерівностей замінити системою рівнянь, тобто привести до ОЗЛП.

Якщо позначити як y1, то отримаємо:

або (³0)

Тобто вводяться додаткові змінні y1, y2,...,ym.

Якщо нерівності мають вигляд , спочатку слід привести їх до вигляду , тобто (³0)

При приведенні до ОЗЛП:

m+n – загальна кількість змінних;

m – рівнянь Þ m базисних змінних;

(m+n)-m – кількість вільних змінних.

 








Дата добавления: 2015-12-22; просмотров: 591;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.