Загальне завдання лінійного програмування

Лінійне програмування — це наука про методи дослідження й відшукання найбільших і найменших значень лінійної функції, на невідомі який накладені лінійні обмеження. Таким чином, завдання лінійного програмування ставляться до завдань на умовний екстремум функції. Здавалося б, що для дослідження лінійної функції багатьох змінних на умовний екстремум досить застосувати добре розроблені методи математичного аналізу, однак неможливість їхнього використання можна досить просто проілюструвати Дійсно, шлях необхідно досліджувати на екстремум лінійну функцію 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. Формулювання завдання.

Дано лінійну функцію (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. Геометрична інтерпретація завдання лінійного програмування.

Розглянемо завдання лінійного програмування, система обмежень якої задана у вигляді нерівностей Знайти мінімальне значення лінійної функції (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-мірного простору, називану багатогранником рішень, тому що координати кожної його крапки є рішенням Таким чином, геометрично завдання лінійного програмування являє собою відшукання такої крапки багатогранника рішень, координати якого доставляють лінійної функції мінімальне значення, причому припустимими рішеннями служать всі крапки багатогранника рішень

  1. Графічний метод рішення завдання лінійного програмування.
    1. Область застосування.

Графічний метод заснований на геометричній інтерпретації завдання лінійного програмування й застосовується в основному при рішенні завдань двовимірного простору й тільки деяких завдань тривимірного простран6тва, тому що досить важко побудувати багатогранник рішень, що утвориться в результаті перетинання півпросторів. Завдання простору розмірності більше трьох зобразити графічно взагалі неможливо Нехай завдання лінійного програмування задані у двовимірному просторі, тобто обмеження містять дві змінні Знайти мінімальне значення функції (2.1) Z = З 1 х 1 2 х 2 при a 11 x 1 + a 22 x 2 b 1 (2.2) a 21 x 1 + a 22 x 2 b 2 . . . . a M1 x 1 + a M2 x 2 b M (2.3) х 1 0, х 2 0 Допустимо, що система (2.2) за умови (2.3) совместна і її багатокутник рішень обмежений. Кожне з нерівностей (2.2) і (2.3), як відзначалося вище, визначає напівплощина із граничними прямими: a i1 x 1 + a i2 x 2 + a i3 x 3 = b i ,(i = 1, 2, …, n), х 1 =0, х 2 =0. Лінійна функція (2.1) при фіксованих значеннях Z є рівнянням прямої лінії: З 1 х 1 + З 2 х 2 = const. Побудуємо багатокутник рішень системи обмежень (2.2) і графік лінійної функції (2.1) при Z = 0 (мал. 2.1). Тоді поставленому завданню лінійного прграммирования можна дати наступну інтерпретацію. Знайти крапку багатокутника рішень, у якій пряма З 1 х 1 + З 2 х 2 = const опорна й функція Z при цьому досягає мінімуму Значення Z = З 1 х 1 + З 2 х 2 зростають у напрямку вектора N =(З 1 , З 2 ), тому пряму Z = 0 пересуваємо паралельно самої собі в напрямку вектора Х. З мал. 2.1 треба, що пряма двічі стає опорної стосовно багатокутника рішень (у крапках А и С), причому мінімальне значення приймає в крапці А. Координати крапки А (х 1 , х 2 ) знаходимо, вирішуючи систему рівнянь прямих АВ і АЕ Якщо багатокутник рішень являє собою необмежену многоуголь-ную область, то можливі два випадки Випадок 1. Пряма З 1 х 1 + З 2 х 2 = const, пересуваючись у напрямку вектора N або протилежно йому, постійно перетинає багатокутник рішень і ні в якій крапці не є опорною до нього. У цьому випадку лінійна функція не обмежена на багатокутнику рішень як зверху, так і знизу Випадок 2. Пряма, пері-рухаючись, все-таки стає опорної відносно многоу-гольника рішень (мал. 2.2, а — 2.2, в). Тоді в зави-симости від виду чи області-нейная функція може бути обмеженої зверху й необмеженої знизу обмеженої знизу й необмеженої зверху , або обмеженої як знизу, так і зверху (р

    1. Узагальнення графічного методу рішення завдань лінійного програмування.

Взагалі, за допомогою графічного методу може бути ре-шена завдання лінійного програмування, система ограниче-ний якої містить n невідомих і m лінійно независи-мих рівнянь, якщо N і M зв’язані співвідношенням N — M = 2 Дійсно, нехай поставлене завдання лінійного програмування Знайти мінімальне значення лінійної функції Z = З 1 х 1 2 х 2 +… +З N x N при обмеженнях a 11 x 1 + a 22 x 2 + … + a 1N Х N = b 1 (2.3) 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 М x j 0 (j = 1, 2, …, N) де всі рівняння лінійно незалежні й виконується cоотношение N — M = 2 Використовуючи метод Жордана-Гаусса, робимо M виключень, у результаті яких базисними невідомими виявилися, наприклад, M перших невідомих х 1 , х 2 , …, х M , а вільними — два останніх: х М+1 , і х N , тобто система обмежень прийняла вид x 1 + a 1,М+1 x М+1 + a 1N Х N = b 1 (2.4) x 2 + a 2,М+1 x М+1 + a 2N Х N = b 2 . . . . . . . . x М + a М, М+1 x 2 + a МN Х N = b М x j 0 (j = 1, 2, …, N) За допомогою рівнянь перетвореної системи виражаємо лінійну функцію тільки через вільні невідомі й, з огляду на, що всі базисні невідомі — ненегативні: х j 0 (j = 1, 2, …, M), відкидаємо їх, переходячи до системи обмежень, виражених у вигляді нерівностей. Таким чином, остаточно одержуємо наступне завдання Знайти мінімальне значення лінійної функції Z = З М+1 х М+1 N x N при обмеженнях a 1,М+1 x М+1 + a 1N Х N b 1 a 2,М+1 x М+1 + a 2N Х N b 2 . . . . . . a М+1 x М+1 + a МN Х N b М x М+1 0, х N 0 Перетворене завдання містить два невідомих; вирішуючи її графічним методом, знаходимо оптимальні значення x М+1 і х N , а потім, підставляючи їх в (2.4), знаходимо оптимальні значення х 1 , х 2 , …, х M

Понравилась статья? Поделиться с друзьями:
Школьный софт – сборники сочинений, готовые домашние задания по всем предметам