ign="justify"> Особливістю завдань лінійного програмування є те, що екстремуму цільова функція досягає на кордоні області допустимих рішень. Класичні ж методи диференціального числення пов'язані з перебуванням екстремумів функції у внутрішній точці області допустимих значень. Звідси - необхідність розробки нових методів.
Форми запису задачі лінійного програмування:
Загальним завданням лінійного програмування називають завдання
при обмеженнях
-довільний
де
-задає дійсні числа; (2.1) - цільова функція; (2.1) - (2.6) -обмеження;
- план завдання.
Нехай ЗЛП представлена ??в наступному записі:
Щоб задача (2.7) - (2.8) мала рішення, системі її обмежень (2.8) повинна бути спільною. Це можливо, якщо r цієї системи не більше числа невідомих n. Випадок r gt; n взагалі неможливий. При r=n система має єдине рішення, яке буде при оптимальним. У цьому випадку проблема вибору оптимального рішення втрачає сенс. З'ясуємо структуру координат кутовий точки багатогранних рішень. Нехай r lt; n. У цьому випадку система векторів містить базис - максимальну лінійно незалежну підсистему векторів, через яку будь-який вектор системи може бути виражений як її лінійна комбінація. Базисів, взагалі кажучи, може бути декілька, але не більше Кожен з них складається точно з r векторів. Змінні ЗЛП, відповідні r векторах базису, називають, як відомо, базисними і позначають БП. Решта n - r змінних будуть вільними, їх позначають СП. Не обмежуючи спільності, будемо вважати, що базис складають першу m векторів. Цьому базису відповідають базисні змінні, а вільними будуть змінні
Якщо вільні змінні прирівняти нулю, а базисні змінні при цьому візьмуть невід'ємні значення, то отримане приватне рішення системи (8) називають опорним рішенням (планом).
Теорема. Якщо система векторів містить m лінійно незалежних векторів, то допустимий план є крайньою точкою багатогранника планів.
Теорема. Якщо ЗЛП має рішення, то цільова функція досягає екстремального значення хоча б в одній з крайніх точок багатогранника рішень. Якщо ж цільова функція досягає екстремального значення більш ніж в одній крайній точці, то вона досягає того ж значення в будь-якій точці, що є їх опуклою лінійною комбінацією.
.3 ГРАФІЧНИЙ СПОСІБ ВИРІШЕННЯ ЗЛП
Геометрична інтерпретація економічних завдань дає можливість наочно уявити, їх структуру, виявити особливості і відкриває шляхи дослідження більш складних властивостей. ЗЛП з двома змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення, взагалі кажучи, неможливо. Випадок двох змінних не має особливого практичного значення, проте його розгляд прояснює властивості ОЗЛП, призводить до ідеї її вирішення, робить геометрично наочними способи вирішення та шляхи їх практичної реалізації.
Нехай дана задача
Дамо геометричну інтерпретацію елементів цього завдання. Кожне з обмежень (2.12), (2.13) задає на площині деяку полуплоскость. Напівплощина - опукле безліч. Але перетин будь-якого числа опуклих множин є опуклим безліччю. Звідси випливає, що область допустимих рішень задачі (2.11) - (2.13) є опукле безліч.
Перейдемо до геометричної інтерпретації цільової функції. Нехай область допустимих рішень ЗЛП - непорожнє безліч, наприклад багатокутник.
Виберемо довільне значення цільової функції. Отримаємо. Це рівняння прямої лінії. У точках прямої NМ цільова функція зберігає одне і те ж постійне значення. Вважаючи в рівності (2.11) Z параметром, одержимо рівняння сімейства паралельних прямих, званих лініями рівня цільової функції (лініями постійного значення).
Знайдемо приватні похідні цільової функції по x1 і x2:
Приватна похідна (2.14) (так само як і (2.15)) функції показує швидкість її зростання уздовж даної осі. Отже, c1 і c2 - швидкості зростання Z відповідно уздовж осей і. Вектор називається градієнтом функції. Він показує напрямок найшвидшого зростання цільової функції:
Вектор вказує напрямок найшвидшого убування цільової функції. Його називають антіградіентом.
Вектор перпендикулярний до прямих сімейства.
З геометричній інтерпретації елементів ЗЛП випливає наступний порядок її графічного рішення.
. З урахуванням системи обмежень будуємо область допустимих ріше...
