Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Припустимо, що мають місце 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 – кількість вільних змінних.

 


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал