Головна |
лінійне програмування - Це напрямок математичного програмування, що вивчає методи вирішення екстремальних задач, які характеризуються лінійною залежністю між змінними і лінійним критерієм.
У загальній постановці завдання лінійного програмування формулюється в такий спосіб.
Є якісь змінні = (x1, x2, ..., xn) І лінійна функція цих змінних, яка носить назву цільової функції. Ставиться завдання: знайти екстремум (максимум чи мінімум) цільової функції за умови, що змінні задовольняють системі лінійних рівностей і / або нерівностей.
Класичними прикладами практичних завдань, що зводяться до задачі лінійного програмування, є завдання про дієту, а також завдання щодо складання плану виробництва.
У задачі про дієту складається найбільш економний (тобто найбільш дешевий) раціон харчування тварин, що задовольняє певним медичним вимогам. При цьому в якості змінних x1, x2, ..., xn виступають кількості продуктів харчування, які використовуються в раціоні.
Завдання щодо складання плану виробництва розглянемо більш докладно.
Нехай деяка виробнича одиниця (підприємство, цех, відділ і т.д.) може виробляти n видів товарів G1, G2, ..., Gn, Використовуючи при цьому m видів сировинних ресурсів R1, R2, ...,Rm, Запаси яких обмежені величинами b1, b2, ...,bm.
Tехнология виробництва товару Gj назвемо набір чисел aij, Який показує, яка кількість i-го ресурсу необхідно для виробництва одиниці товару Gj. Це можна записати у вигляді технологічної матриці, яка повністю описує технологічні потреби виробництва і елементами якої є числа aij.
G1 | G2 | ... | GТn | |
R1 | a11 | a12 | ... | a11 |
R2 | a21 | a22 | ... | a2n |
... | ... | ... | ... | ... |
Rm | am1 | am2 | ... | anm |
Припустимо також, що відомі ціни реалізації одиниці кожного товару с1, с2, ..., сn.
позначимо через x1, x2, ..., xn плановане виробництво одиниць товарів G1, G2, ..., Gn. В силу наявної технологічної матриці для цього буде потрібно:
a11x1+a12x2+ ... +a1nxn - ресурсу R1,
a21x1+a22x2+ ... +a2nxn - ресурсу R2,
...
am1x1+am2x2+ ... +amnxn - ресурсу Rm.
З урахуванням обмежень на запаси ресурсів, а також очевидних умов невід'ємності змінних x1, x2, ..., xn отримаємо наступну систему лінійних нерівностей:
Природно припустити, що метою виробничої одиниці є отримання максимального виручки за вироблену продукцію, тобто максимізація функції:
F=c1x1+c2x2+ ... +cnxn.
Таким чином, з урахуванням природного вимоги невід'ємності змінних отримуємо лінійну оптимізаційну задачу, яка може бути представлена ??в наступній формальної записи:
F=c1x1+c2x2+ ... +cnxn®max
Ми не будемо розглядати приклади інших завдань лінійного програмування. Відзначимо лише, що вони зустрічаються дуже часто при оптимізації найрізноманітніших виробничих і економічних завдань.
B. Форми завдань лінійного програмування. Основні поняття і твердження.
Завдання лінійного програмування математично може бути представлена ??в різних формах.
Загальним завданням ЛП називається задача, яка полягає у визначенні максимального (мінімального) значення функції
(1.1)
при умовах
(1.2)
(1.3)
де aij, bi, cj - задані постійні величини і k ? m.
Функція (1.1) називається цільовою функцією завдання (1.1) - (1.3), а умови (1.2) - (1.3) - обмеженнями даного завдання.
Таким чином, обмеження в загальному завданню ЛП задані у вигляді лінійних нерівностей і / або лінійних рівнянь. При цьому зауважимо, що в нерівностях, взагалі кажучи, можуть застосовуватися обидва знака, як "?", так і "?". Однак домноженіем при необхідності обох частин будь-якого нерівності на (-1) можна звести їх все до єдиного вигляду (1.2).
вектор = (X1 , x2, ..., Xn), компоненти якого задовольняють обмеженням (1.2) - (1.3), називається допустимим планом (або допустимим рішенням).
Сукупність усіх допустимих планів задачі лінійного програмування утворює допустиме безліч рішень цього завдання. Будемо позначати його через Х.
допустимий план = (X1 *, X2 *, ... Xn *), при якому цільова функція задачі (1) приймає своє максимальне (мінімальне) значення, називається оптимальним.
Вирішити задачу лінійного програмування - це значить, знайти всі її оптимальні плани або довести їх відсутність.
Крім загальної форми розрізняють ще дві приватні задачі лінійного програмування - стандартну і основну.
особливістю стандартної задачі ЛП є те, що її обмеження представлені у вигляді лінійних нерівностей, а також умов невід'ємності на змінні, присутні в задачі:
(1.4)
обмеження основного завдання ЛП являють собою лінійні обмеження-рівності, а також умови невід'ємності на змінні:
(1.5)
Між різними формами завдань лінійного програмування існує тісний взаємозв'язок, в сенсі можливості переходу від однієї форми запису до іншого.
Наприклад, зведення задачі мінімізації функції до задачі максимізації здійснюється простим домноженіем цільової функції на (-1). Тобто, якщо в задачі лінійного програмування функція
®min,
то, ввівши в розгляд функцію , Отримаємо:
®max.
Перехід від стандартної завдання до основної пов'язаний з введенням додаткових змінних xn + i , I =1,...,m. Покажемо це на прикладі.
Приклад 1.1. Вихідна задача ЛП має вигляд:
У першому з нерівностей ліва частина не більше правої частини. Тому додаванням в ліву частину деякого невід'ємного доданка x4 можна звести це нерівність до рівності. Аналогічно в другому нерівності ліва частина не менше правої. Отже, віднімаючи з лівої частини деякий невід'ємне число x5, Можна також звести таку нерівність до рівності. Отже, отримаємо нову форму записи завдання ЛП (основну):
Основні твердження теорії лінійного програмування стосуються, в першу чергу, виду допустимого безлічі рішень Х, а також існування і властивостей оптимальних рішень задачі. Викладемо ці твердження в інтерпретації, близькій до наочної.
Вступ | Лінійного програмування.
Глава 2. Елементи матричних ігор | C. Графоаналитический спосіб вирішення завдань лінійного програмування | D. Симплекс-метод | Алгоритм симплекс-методу | Метод штучного базису (М-метод) | Елементи теорії подвійності | Основна теорема подвійності | Третя теорема подвійності | Формальне представлення ігор. Поняття матричної гри | Принцип міінімакса рішення матричних ігор. |