Лінійне програмування - це наука про методи дослідження й відшукання найбільших і найменших значень лінійної функції, на невідомі який накладені лінійні обмеження. Таким чином, завдання лінійного програмування ставляться до завдань на умовний екстремум функції. Здавалося б, що для дослідження лінійної функції багатьох змінних на умовний екстремум досить застосувати добре розроблені методи математичного аналізу, однак неможливість їхнього використання можна досить просто проілюструвати
Дійсно, шлях необхідно досліджувати на екстремум лінійну функцію Z = З 1 х 1 +З 2 х 2 +... +З N x N
при лінійних обмеженнях
a 11 x 1 + a 22 x 2 + ... + a 1N Х N = b 1
a 21 x 1 + a 22 x 2 + ... + a 2N Х N = b 2
. . . . . . . . . . .
a М1 x 1 + a М2 x 2 + ... + a МN Х N = b М
Тому що Z - лінійна функція, те = З j (j = 1, 2, ..., n), те всі коефіцієнти лінійної функції не можуть бути дорівнюють нулю, отже, усередині області, утвореною системою обмежень, екстремальні крапки не існують. Вони можуть бути на границі області, але досліджувати крапки границі неможливо, оскільки частки похідні є константами
Для рішення завдань лінійного програмування треба було створення спеціальних методів. Особливо широке поширення лінійне програмування одержало в економіці, тому що дослідження залежностей між величинами, що зустрічаються в багатьох економічних завданнях, приводить до лінійної функції з лінійними обмеженнями, накладеними на невідомі
- Загальне завдання лінійного програмування
- Формулювання завдання.
Дано лінійну функцію
(1.1) Z = З 1 х 1 +З 2 х 2 +... +З N x N
і система лінійних обмежень
a 11 x 1 + a 22 x 2 + ... + a 1N Х N = b 1
a 21 x 1 + a 22 x 2 + ... + a 2N Х N = b 2
. . . . . . . . . . .
a i1 x 1 + a i2 x 2 + ... + a i Х N = b i (1.2)
. . . . . . . . . . .
a M1 x 1 + a M2 x 2 + ... + a MN Х N = b M
(1.3) x j 0 (j = 1, 2, ... ,n)
де а ij , Ь j і З j - задані постійні величини
Знайти такі ненегативні значення х 1 , х 2 , ..., х n , які задовольняють системі обмежень (1.2) і доставляють лінійної функції (1.1)мінімальне значення
Загальне завдання має кілька форм запису
Векторна форма запису. Мінімізувати лінійну функцію Z = СХ при обмеженнях
(1.4) А 1 х 1 + А 2 x 2 + ... + А N x N = А про , X 0
де З = (з 1 , з 2 , ..., з N ); Х = (х 1 , х 2 , ..., х N ); СХ - скалярний добуток; вектори
A 1 , A 2 ,..., A N , A 0
складаються відповідно з коефіцієнтів при невідомих і вільних членах
Матрична форма запису . Мінімізувати лінійну функцію, Z = СХ при обмеженнях АХ = А 0 , Х 0, де З = (з 1 , з 2 , ..., з N ) - матриця-cтрока; А = (а ij ) - матриця системи;
Х - матриця-стовпець, А 0 - матриця-стовпець
Запис за допомогою знаків підсумовування. Мінімізувати лінійну функцію Z = З j х j при обмеженнях
0прерозподіл 1. Планом або припустимим рішенням завдання лінійного програмування називається Х = (х 1 , х 2 , ..., х N ), що задовольняє умовам (1.2) і (1.3)
0прерозподіл 2. План Х = (х 1 , х 2 , ..., х N ) називається опорним, якщо вектори А (i = 1, 2, ..., N), що входять у розкладання (1.4) з позитивними коефіцієнтами х , є лінійно незалежними
Тому що вектори А є N-Мірними, то з визначення опорного плану треба, що число його позитивних компонентів не може перевищувати М
0прерозподіл 3. Опорний план називається невирожденним, якщо він містить М позитивних компонентів, у противному випадку опорний план називається вирожденним
0прерозподіл 4 . Оптимальним планом або оптимальним рішенням завдання лінійного програмування називається план, що доставляє найменше (найбільше) значення лінійної функції
Надалі розглянуте рішення завдань лінійного програмування, пов'язаних зі знаходженням мінімального значення лінійної функції. Там, де необхідно знайти максимальне значення лінійної функції, досить замінити на протилежний знак лінійної функції й знайти мінімальне значення останньої функції. Заміняючи на протилежний знак отриманого мінімального значення, визначаємо максимальне значення вихідної лінійної функції
-
- Геометрична інтерпретація завдання лінійного програмування.
Розглянемо завдання лінійного програмування, система обмежень якої задана у вигляді нерівностей
Знайти мінімальне значення лінійної функції
(1.5) Z = З 1 х 1 +З 2 х 2 +... +З N x N
при обмеженнях
a 11 x 1 + a 22 x 2 + ... + a 1N Х N b 1
a 21 x 1 + a 22 x 2 + ... + a 2N Х N b 2
(1.6) . . . . . . . . . . .
a M1 x 1 + a M2 x 2 + ... + a MN Х N b M
(1.7) x j 0 (j = 1, 2, ... ,n)
Сукупність чисел х 1 , х 2 , ..., х N , що задовольняють обмеженням (1.6) і (1.7), називається рішенням. Якщо система нерівностей (1.6) за умови (1.7) має хоча б одне рішення, вона називається спільної, у противному випадку - неспільної
Розглянемо на площині х 1 Ох 2 спільну систему лінійних нерівностей
a 11 x 1 + a 22 x 2 b 1
a 21 x 1 + a 22 x 2 b 2
. . . .
a M1 x 1 + a M2 x 2 b M
x 1 0, x 2 0
Це однаково, що в системі (1.6) - (1.7) покласти N=2. Кожна нерівність цієї системи геометрично визначає напівплощина із граничної прямої
a i1 x 1 + a i2 x 2 = b i ,(i = 1, 2, ..., m). Умови незаперечності визначають напівплощини відповідно із граничними прямими х = 0, х = 0. Система совместна, тому напівплощини, як опуклі безлічі, перетинаючись, утворять загальну частину, що є опуклою безліччю і являє собою сукупність крапок, координати кожної з яких є рішенням даної системи (мал. 1.1)
Сукупність цих крапок (рішень) назвемо багатокутником рішень. Він може бути крапкою, відрізком, променем, багато-косинцем, необмежений-ний багатокутної облас-тью
Якщо в системі обмежень (1.6) - (1.7) n = 3, то кожне нера-венство геометрично представляє півпростір тривимірного простору, гранична площина якого a i1 x 1 + a i2 x 2 + a i3 x 3 = b i ,(i = 1, 2, ..., n), а умови незаперечності - напівпростий-ранства із граничними площинами відповідно х j = 0 (j = 1, 2, 3). Якщо система обмежень совместна, то ці півпростори, як опуклі безлічі, перетинаючись, утворять у тривимірному просторі загальну частину, що називається багатогранником рішень . Багатогранник рішень може бути крапкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю. Нехай у системі обмежень (1.6) - (1.7) n 3; тоді кожна нерівність визначає півпростір n-мірного простору із граничною гіперплощиною a i1 x 1 + a i2 x 2 + a i x N = b i (i = 1, 2, ..., m), а умови незаперечності - півпростору із граничними гіперплощинами х j 0 (j = 1, 2, ..., n)
Якщо система обмежень совместна, то за аналогією із тривимірним простором вона утворить загальну частину n-мірного простору, називану багатогранником рішень, тому що координати кожної його крапки є рішенням