Симплексний метод вирішення завдань лінійного програмування

Інші статті циклу

1. Дослідження операцій
2. Метод гілок і кордонів. Завдання комівояжера
3. Симплексний метод вирішення завдань лінійного програмування
4. Симплексний метод вирішення ЗЛП. Приклад
5. Подвійне завдання лінійного програмування
6. Транспортне завдання лінійного програмування
7. Завдання вибору (призначення). Угорський метод вирішення
8. Керування запасами

Введення

Завдання лінійного програмування (ЗЛП) полягає у визначенні значень впорядкованої сукупності змінних x_j, j = 1 (1) n при яких лінійна цільова функція досягає екстремального значення і при цьому виконуються (задовольняються) всі обмеження (вони також лінійні) у формі рівностей або нерівностей. Потрібно знайти план X _< n > = < x₁, x2,..._, xn >, який забезпечує отримання цільової функції з екстремальним значенням. Ідеї моделей лінійного планування (програмування) вперше були висловлені і опубліковані радянським математиком Л. В. Канторовичем в 1939 році в роботі «» математичні методи організації і планування виробництва «». У 1975 році Л. В. Канторович і Т.Купманс отримали Нобелівську премію з економічних наук з формулюванням «за їх внесок у теорію оптимального розподілу ресурсів». У 1947 р. дуже близькі ідеї висловлені американським математиком Дж. Данцигом. А ще пізніше стали масово з'являтися роботи, присвячені проблемам вибору оптимальних рішень в силу їх виняткової важливості. Визнання пріоритету за Л. В. Канторовичем не оскаржувалося практично ніколи, а після присудження Нобелівської премії тим більше.

Загальна постановка завдання

Завдання лінійного програмування (ЗЛП) полягає у визначенні значень впорядкованої сукупності змінних x_j, j = 1 (1) n при яких лінійна цільова функція досягає екстремального значення і при цьому виконуються (задовольняються) всі обмеження у формі рівностей або нерівностей. Потрібно знайти план X _< n > = < x₁, x2,..._, xn >, який забезпечує отримання цільовою функцією екстремального значення

а) Якщо система обмежень ЗЛП має хоча б одне рішення, вона називається спільною в іншому випадку несумісною; б) Допустима безліч рішень ЗЛП не порожня, якщо система обмежень спільна; в) Безліч допустимих рішень ЗЛП (якщо воно не порожнє) в загальному випадку є багатогранною безліччю. Лінійна функція Q (_{X <} n >) називається функцією мети, цільовою функцією (ЦФ), безліч _{планів {}X < n >} задовольняючих системі обмежень (2) - (5), - безліччю допустимих рішень (альтернатив) і позначається символ_ом R, X < n > Є цілковитий, доставний, допустимий план X < n > n &n > Є > Завдання у формі (1) - (5) представляє загальне завдання лінійного програмування.

Стандартна форма завдання

Якщо всі обмеження завдання вказані у вигляді суворих рівностей і на змінні величини накладено умову неотрицатаельности xj _^ 0, j = 1 (1) n, то таке формулювання називають стандартним:

Екстремуми функцій у загальному випадку пов'язані простими співвідношеннями

Перехід від спільного завдання до стандартного

1. Для зручності застосування методів вирішення виконують перетворення вихідного спільного завдання. Обмеження нерівності перетворюють на рівності. Введено додаткові змінні за кількістю нерівностей, тобто формулюють розширену задачу x_{n + 1-0}, x_{n + 2-0},..., x_{n + k-0}. Нерівності a_i1x₁ + a_i2x₂ +... + a_inx_n ^ b_i введенням змінної x_{n + 1} ^ 0 перетворюються на рівності a_i1x₁ + a_i2x₂ +... + a_inx_n + a_{i (n + 1)} x_{n + 1} = b У ЦФ знову введені змінні мають коефіцієнти рівні нулю c_{n + 1} = c_{n + 2} =... = c_{n + k} = 0.
2. а) Якщо у вихідному загальному завданні на деякі змінні xj_, j = 1 (1) n, не накладено умови їх неотрицательности, то кожну таку змінну представляють у вигляді різниці додатних нових змінних _x'j - _x'j, де _x'j ^ 0 і x'j ^ 0, j > r. Спосіб усунення негативних змінних простий, але при цьому розмірність (кількість неотрицьових змінних) завдання зростає. б) Є інший складніший шлях. _Кожну xj ≯ 0 виражають явно через інші, для яких _умова xj ^ 0 виконується. Потім знайдені вирази підставляють в обмеження, щоб виключити їх з розгляду. При цьому розмірність завдання навіть зменшується.

Канонічна форма завдання

Зручність цієї форми ЗЛП полягає в тому, що вона дозволяє гранично просто отримати перше допустиме рішення. Для цієї форми мають бути виконані умови:

• праві частини в обмеженнях - неотрицательны b_i ^ 0, i = 1 (1) m;
• кожне рівняння містить змінну x_j ст.10 з коефіцієнтом при ній рівним «1» в цьому рівнянні і з коефіцієнтом «0» у всіх інших рівняннях; ці змінні називають додатковими або штучними;
• до ЦФ ці змінні входять з коефіцієнтом «0»;
• визначення опорного плану (початкової вершини) виконують методом штучного базису, що ще до вирішення завдання дозволяє з'ясувати факт існування рішення.

Якщо вихідне завдання має хоча б один план, то розширене завдання (після введення штучних змінних у систему обмежень) також містить цей план як своє допустиме рішення

Змінні x₁, x₂,..., xm називають базисними - інші вільними (позабазисними). Вершина допустимої області рішень записується у вигляді точки < _{^ 1}, _{^ 2},..., ^ m_, 0, 0,..., 0 >, оскільки вектори умов для _x1, _x2,..., x_m є лінійно незалежними (утворюють підматрицю, де одиниці розміщуються тільки на головній діагоналі).

Геометрична інтерпретація ЗЛП

Будемо розглядати приклад ЗЛП у виробництві двох видів продукції на підприємстві, що використовує при цьому чотири види сировини (див. раніше це завдання). Цей приклад зручний для геометричної інтерпретації тим, що простір рішень є почесним (тобто площину) і всі елементи ЗЛП допускають наочне уявлення (зображення) в тривимірному просторі. Почнемо з розгляду системи нерівностей (обмежень ЗЛП). Зауважимо, що кожна i-а нерівність в обмеженнях ЗЛП визначає напівплоскість в системі координат х₁Ох₂ з граничною прямою a_i1x₁ + a_i2x₂ = b_i, i = 1 (1) m.

Малюнок 1 - Приклади областей, рписуючих обмеження, завдання лінійного програмування

Випишемо їх і присвоїмо їм імена

Область, що формується напівплоскостями, може бути отримана у вигляді замкнутого або розімкнутого (необмеженого) багатогранника. Шляхом безпосередньої побудови меж (прямих) і виявлення області перетину напівпросторів з'ясуємо, чи є багатогранна безліч обмеженим і чи не порожня вона (рис.). Маємо на площині х₁ О х₂ багатокутник А Ո В Ո C Ո D Ո E Ո F. Він є випуклим (чи завжди?), його межа утворена відрізками прямих.

Цільова функція. Що можна сказати про лінійну форму (ЦФ)? Це функція двох змінних x₁ і x2, її образ у тривимірному просторі - площина, що проходить через початок координат. Знайдемо приватні похідні ЦФ за x_j

Оскільки приватна похідна за змінною x_j представляє найбільшу швидкість зміни функції Q в напрямку цієї вісі, то вектор C < n _{> =} < _c1, c2 > - це вектор найбільшої зміни ЦФ, вектор градієнтного напрямку. Якщо значення Q _{зафіксувати} Q = Q1 = const, то рівняння ЦФ перетворюється на рівняння _прямої c1_x1 + c₂x2 = Q1 = const _{площини х1О х2}

У тривимірному просторі це паралельна площина х₁О х₂ на висоті Q1_, в кожній точці < x1, x2, Q_{1 >} якої значення ЦФ постійно і дорівнює Q₁. На площині Q цієї прямої відповідає лінія паралельна площині х1_О х2_, яку називають лінією рівня (теслярський рівень) функції c1_x1 ₊ c2_x2_. Змінюючи Q, отримаємо сімейство ліній рівня паралельних один одному. Вимогу завдання - пошуку екстремуму Q відповідає зсув точки по поверхні функції Q в напрямку вектора C < _n > = _< c1_, c2 > від початку координат.

Обмеження ЗЛП не дозволяють аргументам ЦФ Q (x1, x2) виходити за межі багатокутної допустимої області. Іншими словами, потрібно знайти точку на площині Q найбільш віддалену від площини _х1О _х2 і проекція якої на _х1О _х2 лежить в області допустимих рішень. Координати x * 1, x * 2 знайденої точки і визначають оптимальний план ЗЛП. Покажемо, що сімейство ліній рівня (ізоліній) перпендикуля_рно C < n >, тобто перпендикулярно прямій х2 = с2х1/с1. З векторного аналізу відомо, що всі лінії рівня ЦФ Q перпендикулярні вектору градієнту ЦФ, обчисленому в деякій точці

Таким чином, переміщуючись уздовж вектора C _< n > або по _прямій х2 = с2_х1/с1, легко побудувати лінію рівня (вона перпендикуляр_на х2 = с2_х1/с1) і обчислити значення ЦФ Q для цієї лінії. Екстремум Q, очевидно, буде досягатися в положенні торкання лінією рівня (її проекцією) межі безлічі допустимих рішень. Такий дотик може бути трьох типів: у вершині, по ребру, по межі багатогранника. Цим типам дотики відповідають: єдине рішення у вершині і нескінченне безліч рішень в інших випадках. Область можливих рішень. Розглянемо випадки обмеженої та необмеженої області допустимих рішень. В останньому випадку пошук екстремуму Q може призводити до відсутності рішення, так як extr Q  і чи існує опорна пряма лінія, що стосується необмеженого багатогранника, і тоді рішення існує.

Приклад. Опис області можливих рішень.

Малюнок В - Область допустимих рішень ЗЛП

Ми можемо записати рівняння межі області D заданої нерівності:

Основні поняття і теореми лінійної алгебри Важливим поняттям лінійної алгебри є поняття лінійного векторного простору. Визначення 2.1. Впорядкована сукупність n дійсних чисел називається n-мірним вектором. Визначення 2.2. Сукупність всіляких n-мірних векторів після введення в неї операцій додавання і множення на дійсне число називається n-мірним лінійним векторним простором. Приватними випадками лінійних просторів є пряма, площина, тривимірний простір. Визначення 2.3. Система векторів X₁, X₂,..., Xn називається лінійно залежною, якщо існують такі числа в 1_, ^ 2_,..., _{що не} дорівнюють нулю одночасно, при яких має місце рівність: λ₁X₁ + _λ2_X2... +. _n Xn = 0, де _{всі 0} і. 1 +. 2 +... + ^ n = 1. Якщо ж це рівність можлива лише у випадку, коли всі  i = 0 (i = 1 (1) n), система векторів називається лінійно незалежною. Визначення 2.4. Базисом n-мірного векторного простору називається будь-яка сукупність n лінійно незалежних векторів цього простору. У почесному просторі за базис можуть бути взяті будь-які два неколінеарних вектори, зокрема, е1 = (1,0), е2 = (0, 1). У тривимірному просторі - будь-які три некомпланарних вектори, наприклад, е1 = (1,0,0), е2 = (0,1,0), е3 = (0,0,1).

Випуклою лінійною комбінацією точок X₁, X₂,..., Xn називається лінійна комбінація виду: X = λ₁X_{1 + λ}2_X2... _+'n Xn де всі'i'0 _і'1 +'2 _{+... +'n} = 1. Зокрема, коли є _дві точ_ки X1 і X2, їх випукла комбінація - _X1 + (1- ^) X2, ∈[0,1] - це точка на відрізку, що з'єднує ці точки.

Теорема 1. Будь-який вектор n-мірного векторного простору можна уявити, як лінійну комбінацію векторів базису, притому єдиним чином. Визначення 2.5. Максимальне число лінійно незалежних векторів лінійного простору називається розмірністю лінійного простору. Лінійний простір зазвичай позначають, R_n де n - його розмірність. Випуклою оболонкою точок називається безліч всіляких випуклих комбінацій цих точок. Безліч називається випуклим, якщо разом з двома будь-якими його точками воно містить і їх довільну випуклу лінійну комбінацію. З геометричної точки зору це означає, що випукла безліч містить разом з будь-якими двома своїми точками і з'єднує їх відрізок. Випукла безліч збігається зі своєю випуклою оболонкою. Прикладами випуклих безліч є прямолінійний відрізок, квадрат, коло, пряма, напівплоскість, куб, куля, напівпростір та інші. Кутовими точками випуклої безлічі називаються точки, які не є випуклою лінійною комбінацією двох довільних точок безлічі. Наприклад, кутовими точками трикутника є його вершини, кутовими точками кола - точки кола. Таким чином, випукле безліч може мати кінцеве або нескінченне число кутових точок, але може не мати їх зовсім. Наприклад, пряма, площина, напівплоскість, простір, напівпростір кутових точок не мають. Одним з основних понять теорії лінійного програмування є поняття випуклого багатогранника в n-мірному просторі, приватними випадками якого є при n = 1 відрізок на прямий, при n = 2 випуклий багатокутник на площині. Випуклим багатокутником називається випукла замкнута обмежена безліч точок на площині, що має кінцеве число кутових точок, що називаються вершинами. Прямолінійні відрізки, що з'єднують дві вершини і утворюють межу, називаються сторонами багатокутника.

Опорною прямою випуклого багатокутника називається пряма, що має з багатокутником, розташованим по один бік від неї, хоча б одну загальну точку.

Випуклим багатогранником називається випукле замкнуте обмежене безліч точок простору, що має кінцеве число кутових точок, що називаються його вершинами. Багатокутники, що обмежують багатогранник, називаються його гранями, а відрізки, за якими перетинаються межі, називаються ребрами. Опорною площиною багатогранника називається площина з багатогранником, розташованим по один бік від неї, хоча б одну загальну точку.

Теорема 2.2. Випуклий n-мірний багатогранник є випуклою лінійною комбінацією своїх кутових точок.

Слідство 2.3. З теореми випливає, що випуклий багатогранник породжується своїми кутовими точками (вершинами): відрізок - двома точками, трикутник - трьома точками, n - вугільник на площині - n точками тощо. У той же час випукла багатогранна область, що містить нескінченно віддалену точку, будучи необмеженою безліччю, не визначається однозначно своїми кутовими точками: будь-яку її точку не можна уявити у вигляді випуклої лінійної комбінації кутових точок.

Елементи випуклих безліч

Визначення 1. Безліччю називається сукупність елементів будь-якої природи, для яких вказано правило приналежності до цієї безлічі.

Визначення 2. е - о до р е з т н о з т ю точки х називається безліч всіх точок, відстань яких до точки х менше е.

Визначення 3. Точка х₁ називається внутрішньою точкою множини M, якщо існує така - околиця даної точки, всі точки якої належать безлічі M.

Визначення 4. Точка х₂ називається в н е ш н й т о ч к й м н о ж е з т в а M, якщо існує така - околиця даної точки, всі точки якої не належать безлічі М.

Визначення 5. Точка х₃ називається г р а н і ч н о й т о ч до й м н о ж е с т в а M, якщо в будь-якій її - околиці існують точки як належать безлічі M, так і не належать цій безлічі.

Визначення 6. Безліч М називається з а м до н у т м, якщо воно містить всі свої граничні точки. х 2- незамкнуте безліч, Приклад. х 2 - замкнуте безліч.

Визначення 7. Безліч М називається в и п у до л и м, якщо разом з будь-якими двома точками, що належать цій безлічі, воно містить і відрізок їх з'єднуючий. У загальній формі ЗЛП кожен символ R1, R2,..., Rm означає один із знаків: = або порожній. У такій формі завдання лінійного програмування частина змінних може бути підпорядкована умові невід'ємності (_xi-0), частина - умові недозволеності (xj-0), а якісь змінні, можливо, можуть приймати будь-які значення.

Загальний алгоритм симплексного методу ЗЛП

Вирішується завдання

Нехай система не народжена і спільна, тобто r_A = r_B = r = m < n - ранг.

Виділимо m = r базисних змінних x₁, x₂,..., x_m, ф = 1 (1) m і k = n - m вільних змінних x_{m + 1}, x_{m + 2},..., x_n, j = m + 1 (1) n; ЦФ і базисні змінні висловимо через вільні

Всі введені змінні в нових позначеннях зручно звести в таблицю, яка називається симплексною.

Алгоритм вирішення

1) Формуємо вихідний план при вільних змінних; x_j = 0, j = m + 1 (1) n, x_j =  _ф, ф = 1 (1) m при  _ф > 0 план x^o _{< n} > припустимо Q (x) = x_o.

2) Перевіряємо цей план на оптимальність, використовуючи значення  j коефіцієнтів ЦФ в останньому рядку таблиці. Можуть бути два випадки:

а) всі  j ^ 0, j = m + 1 (1) n, при цьому збільшення ніякої змінної (з вільних) не призведе до зменшення ЦФ Q, тобто пл^а_{н x}o < n > поліпшити не можна, і він вже оптимальний, таким чином, умовою оптимальності плану є - відсутність у таблиці ^ j > 0.

б) деякі  j > 0. У цьому випадку збільшення значень відповідних вільних змінних x_j ( j > 0) буде мінімізувати Q, оскільки

Щоб Q зменшувалося, такі змінні слід вводити (послідовно) в базис, але, щоб розмірність простору не змінювалася з базису повинні виводитися змінні до числа вільних (по одній) формуємо безліч індексів Г = {j | ^ j > 0}. Яка змінна повинна першою вводитися в базис? Взагалі послідовно перебираючи (вершини симплексу) рішення відшукується при довільному виборі, але для певності вибираємо нову базисну змінну з індексом v = argmax {x_j}, де j ∈ Г. Тепер визначимо змінну (базисну), яка буде виводитися з базису.

У системі рівнянь

Починаємо збільшувати x_v до тих пір, поки деякий х_ф стане негативним. Перший же хф'0 буде виводитися з базису. Визначення. Стовпчик з індексом v і рядок з індексом ф = i називаються напрямними.

3) Перевірка існування рішення (ограни