Розглянемо універсальний методрозв'язання канонічного завдання лінійного програмування
з nзмінними та mобмеженнями-рівностями, відомий як симплекс-метод.
Безліч планів канонічної задачі - опукла багатогранна множина, що має кінцеву кількість кутових точок. І якщо це завдання має оптимальне рішення, то воно досягається хоча б в одній кутовій точці.
З будь-якою кутовою точкою пов'язаний базисний план завдання, в якому змінних дорівнюють нулю, а змінним, що залишилися, відповідають лінійно незалежні стовпці матриці умов. Ці лінійно незалежні стовпці утворюють невироджену базову матрицю.
Перебір усіх кутових точок пов'язаний із великими обчислювальними витратами і тому ефективний. У 1947 році Дж. Данциг запропонував упорядковану процедуру перебору кутових точок, при якій для знаходження оптимального рішення достатньо дослідити лише невелику частину. Ця процедура називається симплекс-методом.
Дж. Данциг запропонував при переході від однієї крайньої точки до іншої замінювати в базисній матриці лише один вектор. Це означає, що при такому переході ми повинні виключити одну з базисних змінних - зробити її небазисною ( рівної нулю), але в її місце запровадити нову змінну у складі небазисних (нульових) - зробити її базисної (позитивної).
Виявляється, геометрично така заміна призводить до переходу від однієї кутової точки до суміжної (сусідньої), пов'язаної з попередньою точкоюзагальним ребром.
З усіх сусідніх точок вибирається та, у якій цільова функція зростає найбільше. Оскільки число кутових точок звичайно, через кінцеве число переходів буде знайдено вершину найбільшим значеннямцільової функції або буде встановлена необмеженість цільової функції на необмеженій безлічі планів.
Загальна схема симплекс-метода складається з наступних основних кроків.
· крок 0. Визначення початкового базису та відповідної йому початкової кутової точки (базисного плану).
· крок 1. Перевірка поточного базового плану на оптимальність . Якщо критерій оптимальності виконано, то план оптимальний і рішення закінчено. Інакшеперехід крок 2.
· крок 2. Знаходження змінної, що вводиться до складу базисних. (З умови збільшення цільової функції).
· крок 3. Знаходження змінної, що виключається зі складу базисних змінних (за умови збереження обмежень завдання).
· крок 4 . Знаходження координат нового базисного плану (суміжної кутової точки). Перехід крок 1.
Повторювані кроки 1-4 утворюють одну ітерацію симплекс-метода.
З цієї схеми випливає, що по-перше, для початку роботи симплекс-методу треба мати якусь кутову точку - початковий базисний план, а по-друге, треба вміти досліджувати поточну кутову точку оптимальність, не обчислюючи всіх суміжних вершин. Ці проблеми легко вирішуються, якщо канонічна задача ЛП має певний спеціальний вид.
Визначення. Будемо говорити, що канонічна задача ЛП має "переважний вигляд", якщо
1. праві частини рівнянь, .
2. матриця умов містить одиничну підматрицю розміру
Інакше кажучи, у кожному рівнянні є змінна з коефіцієнтом рівним одиниці, відсутня інших рівняннях. Перше умова перестав бути обтяжливим, оскільки у разі негативної правої частини деякого рівняння, досить помножити їх у (-1). У задачі кращого виду початковий базовий план дуже просто.
приклад 2.1.
Матриця умов Aта вектор правих частин обмежень bмають вигляд
а цільовий вектор = (1, -3, 0, 4, 2).
Відразу очевидна одна базисна матриця: з одиничними векторами умов.
Отже, вибираючи як базові змінні x 1 , x 3 ,x 5 , і вважаючи в системі рівнянь x 2 = x 4 = 0 (небазисні змінні) , негайно знаходимо x 1 = 10,x 3 = 20,x 5 = 8, так що початковий базовий план x 0 = (10, 0, 20, 0, 8). Бачимо, що значення базисних змінних дорівнюють правим частинам обмежень. На цьому зрозуміло вимога позитивності правих частин b i .
Надалі, базисні змінні об'єднуватимемо у вектор. x Б.
Таким чином, у канонічного завданнякращого виду як початкова базисна матриця береться одинична підматриця A Б = E, А відповідні їй базисні змінні рівні правим частинам обмежень:
x Б = b.
Для базового плану такого виду може бути сформульований досить простий для перевірки критерій оптимальності. Введемо величини
? j = < с Б , A j > - c j j = 1,...,n,(2.1)
де з Б- Вектор з коефіцієнтів цільової функції при базисних змінних x Б , A j - j-й стовпець матриці умов, c j - j-й коефіцієнт цільової функції. Різниці ? jназиваються симплексними різницями або симплексними оцінками.
Критерій оптимальності базового плану. Якщо для базового плану з одиничною базисною матрицеювсі симплексні оцінки невід'ємні, цей план оптимальний.
Застосуємо цей критерій для перевірки оптимальності базового плану x 0 = (10, 0, 20, 0, 8) з прикладу 2.1.
Оскільки в цьому плані вектор базових змінних x Б =(x 1 , x 3 ,x 5 ), то з Б = (c 1 , c 3 ,c 5 ) = (1, 0, 2).
Отже,
? 1 = < с Б , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,
2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,
? 3 = < с Б , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,
? 4 = < с Б , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,
? 5 = < с Б , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.
Оскільки оцінка ? 4 < 0, то базисный план x 0 не оптимальний. Зауважимо, що симплексні оцінки, що відповідають базисним змінним, завжди дорівнюють нулю, тому достатньо перевіряти лише небазисні оцінки.
Симплекс-метод полягає у знаходженні та тестуванні вершини (кута), що є розв'язанням задачі ЛП. На кожному етапі метод виділяє вершину та відповідні їй змінні, які забезпечують рух до мінімуму (максимуму) з найбільшою швидкістю. Вибрана змінна замінює іншу, що найбільше обмежує. Симплекс-метод дозволяє також визначити, чи існує рішення. Реалізуючий симплекс-метод алгоритм можна записати у вигляді:
Крок 1.Визначається деяка вершина в ОДР, що відповідає базисним допустимим рішенням (змінним), знайденим шляхом виділення з матриці т- лінійно незалежних стовпцівта прирівнювання нулю всіх інших змінних, що відповідають іншим стовпцям матриці.
Крок 2Вибирається з усіх можливих решти п - требер, що відповідають небазисним змінним, ребро (змінна), яке приводить при русі по ньому до якнайшвидшого зменшення цільової функції.
Крок 3Здійснюється хіба що рух від початкової вершини вздовж обраного ребра до іншої вершині, що дає нове рішення, має значення ЦФ. Нова вершина утворюється шляхом заміни базисної змінної (ребра) на нову базисну змінну (ребро).
Стовпці та елементи векторів зазвичай упорядковуються та записуються у вигляді симплекс-таблиці, утворення якої буде показано нижче.
Симплекс-метод вирішує завдання ЛП стандартній формі.
Мінімізувати (максимізувати) функцію за умов х > 0; Ах = Ь.
Матриця А дійсна, має розмірність тх «і ранг т.
Сформульоване завдання ЛП можна також записати у вигляді
Виходячи із запису завдання ЛП у вигляді (8Л) можна сказати, що розширена матриця
розмірності (т + 1) (п + 2) відповідає решениям[х/] т.
Подаємо матрицю А у вигляді сукупності стовпців
Оскільки матриця А має ранг т,то знайдуться тлінійно незалежних стовпців матриці А, наприклад (а У1 ,...,а У/і Розглянемо вектор х° > 0, такий, що всі його п - телементів дорівнюють 0 і Ах° = Ь. Нехай це будуть елементи з номерами... i n _ m.Припустимо також, що розташування aw лінійно незалежних стовпців матриці А відповідає місцю розташування ненульових елементів векторах 0 . Геометрично, згідно з твердженням 3 § 7.6, це означає, що х ° є вершиною (кутом) ОДР і, крім того, задовольняє заданим умовам. Таке рішення називається допустимим базовим рішенням.Кути допустимої множини є допустимими базовими рішеннями.
Нагадаємо, що безліч базисних рішень містить всю інформацію, необхідну для оптимального розв'язання задач ЛП. Для розглянутого в § 7.6 двовимірного випадку базовими рішеннями є всі 6 точок, а допустимими базовими рішеннями є точки Л, В,Сі 0.
Таким чином, будь-який аналогічний х° вектор х можна записати як
де х в- Вектор, елементи якого відповідають лінійно незалежним стовпцям матриці A; x F -вектор з нульовими елементами.
Аналогічно визначимо вектори
Змінні елементи вектора. х,називаються базовими змінними,а змінні, що є елементами вектора x F ,називаються вільними (небазисними) змінними.
Так як x° F=0, значення цільової функції для початкового вектора х° буде дорівнює
де / ° - значення / у точці х °.
Рішення (8.1) виду [х°/°] т при х > 0 називається очевидним (явним) рішенням.Отже, якщо прирівняти нулю небазисні змінні, виходить очевидне рішення.
Для зручності переставимо тлінійно незалежних стовпців матриці А в ліву частинуі запишемо матрицю у вигляді
Тут матриця відповідає тлінійно незалежним стовпцям 
має розмірність тх тта ранг т,а матриця F
є тх (п - т)матрицею. Так як матриця складається з лінійно незалежних стовпців, то вона має зворотну -1 і detB ф 0. Зазначимо, що для утворення матриці можна вибрати будь-які тлінійно незалежних стовпців матриці А.
Подаємо задачу (8.1) з урахуванням введених позначень
Даному уявленню відповідає розширена матриця Припустимо, що
звідки слідує
Якщо вектор х вбуде рішенням системи Вх й = Ь, то він буде базовим рішенням. Якщо виконується нерівність в= В -1 Ь > О, тоді х вбуде допустимим рішенням.
Таким чином, поточне рішеннязадовольняє наступному рівнянню:
Розглянемо матрицю (8.4). Базисні змінні будуть представлені в явному вигляді, якщо замінити матрицю В одиничною матрицею I. Помноживши перший рядок матриці (8.4) зліва на ~ 1, отримаємо
де _1 Ь > О, тобто. т верхніх елементіву правому стовпці неотрицательны і є поточне значення змінних.
У лівому боці верхнього рядкавийшла одинична матриця: -1 В = I. Дане уявленнядуже зручно, тому що при множенні на вектор х вкожна змінна буде в окремому рядку.
Таким чином, базисне рішення, яке вважатимемо допустимим і відповідним базису В, є х т = [х у 0], де х в == У _1 Ь. Базове рішення є результатом припущення, що x F = 0. Однак, якщо x F * 0, то х^може бути обчислено 5 = = B~"b - B^"Fx/r. Підставивши цей вираз у цільову функцію(функцію вартості), отримаємо
Так як необхідно визначити залежність вартості від небазових змінних, одну з яких потім включити в базисні, нижній рядок під матрицею I повинен бути нульовим. Для цього в (8.7) помножимо перший рядок (матриці) на з ві складемо з другої
де - значення цільової функції для початкового століття
тора х 0 із (8.3).
Матриця (8.8) називається симплекс-таблицею.Приведення її до даному видує початковим етапомсимплекс-алгоритма. У процесі виконання алгоритму здійснюється перехід від однієї таблиці до іншої, поки нижній правий елемент таблиці стане максимальним чи мінімальним.
З використанням симплекс-таблиці легко побачити допустиме рішення. Змінні x F відповідають нульовій підматриці, змінні х в- поодинокі матриці:
Припустимо, що завдання Л П наведено до стандартної форми, обчислено симплекс-таблиця та обрано початкове базисне рішення, що відповідає вершині багатогранника рішень.
Тоді 
- Розв'язання задачі (8.1). Так
як b > О, це базове рішення допустиме.
Представимо матрицю (8.9) у зручнішому вигляді, зберігши основні позначення:
Розглянемо окремо завдання максимізації та мінімізації.
Знаходження оптимального плану. Цей метод є універсальним, він дозволяє вирішувати завдання лінійного програмування будь-якої розмірності у спільній постановці. Однак такий метод вимагає приведення вихідного завдання до канонічного вигляду.
Основна ідея Симплекс-методу полягає в тому, щоб так переходити від однієї вершини ОДР до іншої, щоб при кожному переході значення ЦФ зменшувалася. Саме так з будь-якої вершини можна дістатися оптимальної і отримати оптимальний план.
Наприклад: нехай відомий опорний план X = (x1, x2, ..., xm, 0, 0, ..., 0) і пов'язана з ним система лінійно незалежних векторів: А1, А2, ..., Am, тоді для цього опорного плану можна підрахувати значення ЦФ Z=(c1x1+c2x2+…+cmxm) та записати умови обмеження у наступному вигляді x1A1+x2A2+…+xmAm=b
Оскільки вектори А1,А2,…,Аm лінійно незалежні будь-який вектор Aj можна розкласти за цими векторами: Aj=x1jA1+x2jA2+…+xmjAm (*) Введемо величини Zj Zj=x1jc1+x2jc2+…+xmjcm, де xij коефіцієнт відповідний Ai вектора Aj за базовими векторами
Теорема1: покращення опорного плану
Якщо деякого індексу j виконується умова Zj-Cj>0, можна зменшити значення ЦФ причому:
· якщо ЦФ обмежена знизу, то можна побудувати опорний план з меншим значенням ЦФ, що цей попередній
· якщо ЦФ не обмежена знизу, то можна побудувати план відповідний як завгодно малому значенню ЦФ
Теорема2: критерій оптимальності опорного плану
Якщо деякий індекс j в опорному плані нерівність Zj-Cj0. Нехай цей мінімум досягається для вектора Ak, тоді цей вектор підлягає висновку з базису. Рядок, що відповідає цьому вектору, називається напрямною і позначається «à».
4. Після визначення напрямних стовпця та рядка заповнюють нову симплекс таблицю. У такій таблиці на місці напрямного рядка стоятиме Ai. Заповнення нової таблиціпочинається з напрямного рядка. В якості компоненти опорного плану туди пишеться величина Ψ0 X'l=Ө0=Xk/Xkl, інші елементи цього рядка визначаються за формулою X'lj діляться всі колишні елементи напрямного рядка, але в місці колишнього елемента Xkl автоматично з'являється одиниця. Загальне правилодля перерахунку напрямного рядка можна записати так: Ak (новий ел-т напрямного рядка)=(старий Ел-т направл. рядка)/(ел-т, що стоїть на перетині направл. стовпця і рядка)
5. Перераховуються всі елементи інших рядків таблиці, включаючи додаткову нижній рядок. Перерахунок здійснюється за формулами
· для компонент опорного плану X'i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil
· для компонентів розкладених по базису X'ij=Xij-(Xkj/Xkl)*Xil
· для додаткового рядка Z'j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)
Всі ці формули будуються за одним правилом:
(новий ел-т)=(старий ел-т)-(ел-т нового направл. рядка)*(ел-т направл. стовпця стоїть у соотв. рядку)
Після заповнення нової симплекс таблиці здійснюється перехід до другого етапу алгоритму.
Методи природного та штучного базису. Основні поняття, алгоритми методів.
Більшість завдань лінійного програмування виникають труднощі за її вирішенні пов'язані з визначенням вихідного опорного плану і вихідної симплекс таблиці, з якої починаються все итерации. Зумовлено це тим, що в реальних завданнях серед векторів Ai немає векторів, що містять лише одну ненульову компоненту, тобто векторів виду (0,0,0,…,0,1,0,…,0) або їх кількість не достатньо формування базису. Т. е. неможливо сформувати природний базис.
Метод штучного базису заснований на штучному введеннів математичну модельЗавдання таких векторів.
Нехай задана ЗЛП канонічноїформи
F: C1X1=C2X2+…+CnXnàmin
a11x1+a21x2+…+an1xn=b1
a12x1+a22x2+…+an2xn=b2
…………………………
a1mx1+a2mx2+…+anmxn=bm
Тоді її перетворюють на вигляд
F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin
a11x1+a21x2+…+an1xn+xn+1=b1
a12x1+a22x2+…+an2xn+xn+2=b2
……………………………….
a1mx1+a2mx2+…+anmxn+xn+m=bm
Де М – нескінченно великі числа. В отриманій задачі відразу видно вихідний базис, як його слід взяти вектора при штучно введених змінних xn+1, xn+2, xn+m. Оскільки саме ці вектори матимуть вигляд: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Потім перетворену задачу вирішують, використовуючи алгоритм симплекс методу. Вихідний опорний план перетвореної задачі має вигляд (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…,bm). Вихідна симплекс таблиця виглядає так
| Базис | коеф. ЦФ | План | C1 | C2 | … | Cn | M | M | … | M |
| A1 | A2 | … | An | An+1 | An+2 | … | An+m | |||
| An+1 | M | b1 | a11 | a21 | … | an1 | 1 | 0 | … | 0 |
| An+2 | M | b2 | a12 | a22 | … | an2 | 0 | 1 | … | 0 |
| … | … | … | … | … | … | … | … | … | … | … |
| An+m | M | bm | a1m | a2m | … | anm | 0 | 0 | … | 1 |
| Z0 | ||||||||||
Визначаємо ел-ти додаткового рядка за формулами Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi
Для визначення різниць Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n
Zj-Cj=M∑mj=1aij-Cj
Після отримання вихідної симплекс таблиці її перетворюють, намагаючись виводити з базису вектори, що відповідають введеним додатковим змінним.
Оскільки М дуже велике число, то серед різниць Zj-Cj буде багато позитивних чисел. Т. е. буде безліч претендентів на введення в базис серед векторів A1, A2, ..., An
Якщо якийсь вектор відповідає штучно введеним змінним xn+1,xn+2,…,xn+m, то відповідний вектор виводиться з базису, а стовпець симплекс таблиці при цьому векторі викреслюється і більше не повертаються до нього. Наприкінці перетворення симплекс таблиці можливі два варіанти:
· всі вектори відповідні штучним змінним були виведені з базису, у цьому випадку всі стовпці симплекс таблиці відповідні додатковим змінним зникнуть, і вирішуватиметься вихідне завдання
· Отриманий оптимальний план все ж таки буде містити якусь додаткову змінну, це означає, що ОДР вихідної задачі порожня, тобто її обмеження суперечливі, тому вихідне завдання взагалі не має рішень.
Подвійні задачі лінійного програмування. Постановка завдань, їх властивості.
Симетричні двоїсті завдання:
Перша стандартна форма
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+…+an1xn>=b1
a12x1+a22x2+…+an2xn>=b2
…………………………………………..
a1mx1+a2mx2+…+anmxn>=bm
Подвійне завдання
d(y)=b1y1+b2y2+…+bmymàmax
a11y1+a12y2+…+a1mym=0, V j=1,m
Чи не семирічна пара двоїстих завдань
Вихідне завдання в канонічної форми
f(x)=c1x1+c2x2+…+cnxnàmin
a11x1+a21x2+..+an1xn=b1
a12x1+a22x2+..+an2xn=b2
…………………………..
2. Введення природних базових змінних. Побудова симплексної таблиці. Визначення нульового плану.
Симплекс-метод. Алгоритм симплекс-методу.
Симплекс-метод- алгоритм вирішення оптимізаційної задачі лінійного програмування шляхом перебору вершин опуклого багатогранника у багатовимірному просторі. Метод був розроблений американським математиком Джорджем Данцигом у 1947 році.
Ідея симплексного методу полягає в тому, що поставлене описове завдання переводиться в математичну форму. Математичне формулювання завдання містить рівняння цільової функції із зазначенням бажаного результату - визначення мінімуму чи максимуму цільової функції; системи лінійних обмежень, заданих рівностями чи нерівностями. Отриманий математичний опис призводять до матричного вигляду. Потім матричний опис завдання призводять до канонічної форми. Після того як система лінійних рівняньприведена до канонічної форми, приступають до вирішення задачі лінійного програмування. Алгоритм розв'язання цього завдання складається з послідовності побудови матриць. Кожен крок наближає до отримання бажаного результату.
У обчислювальній схемі симплекс-метода реалізується впорядкований процес, при якому, починаючи з деякої вихідної допустимої кутової точки (зазвичай початок координат), здійснюються послідовні переходи від однієї допустимої екстремальної точки до іншої, доки не буде знайдена точка, що відповідає оптимальному рішенню.
Алгоритм симплекс-методу
1. Наводимо систему обмежень до канонічного виду (коли система обмежена). Причому у системі можна назвати одиничний базис.
2. Знаходимо початковий опорний план(Ненегативні базисні рішення системи рівнянь КЗЛП). Кожен із опорних планів визначається системою m лінійно незалежних векторів, що містяться в даній системі з n векторів А 1 , А 2 ,…, А n. Верхня межа кількості опорних планів, що містяться в цьому завданні, визначається числом поєднань З nm);
3. Будуємо симплексну таблицю (симплекс-таблицяматриця, що служить засобом перебору допустимих базисних рішень (невиродженої) задачілінійного програмування при її вирішенні симплексним методом. Утворюється з матриці коефіцієнтів системи рівнянь лінійного програмування, наведеної до канонічної форми, її послідовне перетворення за так званим симплексним алгоритмом дозволяє заобмежену кількість кроків (ітерацій) отримувати шуканий результат - план, що забезпечує екстремальне значення цільової функції).
4 В симплексної таблиціперевіряємо вектора негативність, тобто. оцінки Zj - Сjзаписані у рядку мають бути ≤ 0 (на мінімум), Zj – Сj ≥ 0(На максимум). Якщо оцінки задовольняють умовам оптимальності, то завдання вирішено.
5. Якщо для деяких векторів порушуються умови оптимальності, необхідно ввести в базис вектор, якому відповідає:
max[θ 0 j (Zj - Сj)] ; min[θ 0 j (Zj - Сj)] ; θ 0 j = min, де х i> 0
Вектор елемент θ jякий відповідає θ 0 jназивається роздільною; рядок і стовпець у яких він знаходиться, називається напрямним, з базису йде вектор, що стоїть у напрямному рядку.
6. Знайдемо коефіцієнт розкладання всім векторів у новому базисі. Застосуємо метод Джордано Гауса
Перевіримо на оптимальний опорний план. Якщо оцінка відповідає умовам оптимальності, то завдання вирішено, якщо ні, то виконуються пункти 5-7.
2. Введення природних базових змінних. Побудова симплексної таблиці. Визначення нульового плану.
Симплекс-метод найбільш ефективний при вирішенні складних завдань і представляє ітераційний (кроковий) процес, що починається з нульового(опорного) рішення (вершини n-мірного багатогранника). Далі у пошуках оптимального варіантаплану передбачається рух по кутових точках (вершин багатогранника) до тих пір, поки значення цільової функції не досягне максимальної (мінімальної) величини. Розглянемо алгоритм симплексного методу на прикладі задачі планування товарообігу при обмежених ресурсахсировини.
Підприємство реалізує nтоварних груп, маючи mобмеженими матеріально-грошовими ресурсами b i ≥0 (1 ≤ i≤ m) . Відомі витрати ресурсів кожного i- види на виробництво та реалізацію одиниці товару кожної групи, представлені у вигляді матриці ( a ij) та прибуток, одержуваний підприємством від реалізації одиниці товару j-групи, що входить до цільової функції Z(X). Метод лінійного програмування не відрізняється від системи (1) - (2):
Z(X) = з 1 Х 1 + з 2 Х 2 + з 3 Х 3 + … + з n Х n →max(min) (1)
a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,
а 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)
a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,
X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0
Етапи вирішення поставленої задачі симплексним методом включають:
1) Упорядкування нульового опорного плана. Вводимо нові невід'ємні (базисні) змінні, завдяки яким система нерівностей (2) стає системою рівнянь:
a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1
a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)
……………………………………..
a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,
Якщо приймати змінні, що вводяться за вектори-стовпці, то вони являють собою одиничні (базисні) Вектори. Зазначимо, що базисні змінні мають простий фізичний сенс– це залишокконкретного ресурсу складі при заданому плані випуску продукції, тому цей базис називають природним. Вирішуємо систему (3) щодо базисних змінних:
X n+1 = b 1 -a 11 X 1 - a 12 X 2 -...a 1n X n
X n+2 = b 2 - a 21 X 1 - a 22 X 2 -...a 2n X n (4)
………………………………………..
X n+m = b m - a m1 X 1 + a m2 X 2 +…a mn X n
Цільову функцію перепишемо у вигляді
Z(X) = 0-(-з 1 Х 1 -з 2 Х 2 -з 3 Х 3 -…-с n Х n) (5)
Вважаючи, що основні мінливі Х 1 = X 2 = X 3 = … = X n = 0, отримуємо нульовий опорний план Х = (0, 0, … 0, b 1 , b 2, b 3 … b m), при якому Z(X) = 0 (всі ресурси складі, нічого не виробляється). Заносимо план до симплексної таблиці.
| План | Базис | C i / C j | Знач. X i | X 1 | X 2 | X n | X n+1 | X n+2 | X n+ 3 | Q min |
| X n+1 | b 1 | a 11 | a 12 | a 13 | b 1 / a 12 | |||||
| X n+2 | b 2 | a 21 | a 22 | a 23 | b 2 / a 22 | |||||
| X n+3 | b 3 | a 31 | a 32 | a 33 | b 3 / a 32 | |||||
| Z(X) = 0 | -C 1 | - C 2 | - C 3 | Індекс. рядок |
2) З негативних коефіцієнтів індексного рядка вибираємо найбільший за абсолютної величини, що визначає провідний стовпець і показує – яка змінна на наступній ітерації (кроці) перейде з основних (вільних) до базисних (фактично вибирається товарна група, чия реалізація приносить максимальний дохід). Потім запаси сировини b i ділимо на відповідні коефіцієнти витрат, результати заносимо до таблиці та визначаємо мінімальне значення Q min (вибирається ресурс, чий запас найбільше обмежує випуск обраної товарної групи). Це значення виділяє провідний рядок і змінну Х i , яка за наступного кроку (ітерації) вийде з базису і стане вільною.
3) Перехід до нового плану здійснюється внаслідок перерахунку симплексної таблиці методом Жордана-Гаусса. Спочатку замінимо у базисі Х j на Х i провідного стовпця. Розділимо всі елементи провідного рядка на роздільну здатність (РЕ), в результаті чого на місці РЕ у провідному рядку буде 1. Так як Х i став базисним, то інші його коефіцієнти повинні дорівнювати 0. Нові елементи цього плану знаходяться за правилом прямокутника
НЕ = СЕ - (А * В) / РЕ (6)
Оцінка отриманого плану проводиться у разі коефіцієнтам індексного рядка: якщо вони всі позитивні, то план оптимальний, якщо ні, то план можна поліпшити, виробляючи таку ітерацію (крок).
приклад.На придбання устаткування виробничої ділянки виділено 20 тыс.руб. Обладнання може бути розміщене на площі, що не перевищує 72 кв. Можна замовити обладнання двох типів: типу А, що вимагають виробничу площу 6кв.м та дають 6 тис.од. продукції за зміну (ціна 5000 руб.) і типу, що вимагають площу 12 кв.м і дають 3тис.од., (ціна 2000 руб.). Який оптимальний план придбання обладнання, що забезпечує максимальну продуктивністьдільниці?
Позначимо кількість устаткування типу А і В, що купується через Х 1 і Х 2 відповідно.
Продуктивність ділянки (цільова функція): Z(X) = 6Х1+3Х2.
Основні обмеження пов'язані
з грошима: 5Х 1 +2Х 2 ≤ 20,
з площею виробничої ділянки: 6Х1+12Х2≤72.
Вводимо нові базисні змінні Х3 (залишок) грошових коштівпісля закупівлі обладнання) та Х 4 (залишок площ після розміщення обладнання) та перепишемо обмеження у вигляді системи рівнянь:
5X 1 +2Х 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)
6Х 1 +12Х 2 +X 4 = 72 (X 4 =72 - 6X 1 - 12X 2)
У цьому функція мети: Z(X) =6Х 1 +3Х 2 +0Х 3 +0Х 4 .
Складаємо опорний (0-ой) план: Х = (0, 0, 20, 72), тобто. поки нічого не придбано (гроші не витрачені, площі порожні). Складаємо симплексну таблицю
| План | Базис | C i / C j | Знач. X i | X 1 | X 2 | X 3 | X 4 | Q min | |||
| X 3 | 20/5=4 | ||||||||||
| X 4 | 72/6=12 | ||||||||||
| Z(X) = 0 | - 6 | - 3 | Індексний рядок | ||||||||
| →X 1 | 0,4 | 0,2 | 4/0,4=10 | ||||||||
| X 4 | 9,6 | -1,2 | 48/9,6=5 | ||||||||
| Z(X) = 6 * 4 = 24 | -0,6 | 1,2 | Індексний рядок | ||||||||
| X 1 | 0,25 | -1/24 | - | ||||||||
| →X 2 | -1/8 | 5/48 | - | ||||||||
| Z (X) = 6 * 2 +3 * 5 = 27 | 9/8 | 1/16 | Індексний рядок | ||||||||
Очевидно, що провідний стовпець відповідає Х 1 , оскільки має найбільший індекс 6. Знаходимо мінімальне значення Q min = 4 (найжорсткіше обмеження ресурсу), визначаючи провідний рядок, що показує, що з базисних змінних виводиться Х 3 а замість неї вводиться Х 1 . Перераховуємо елементи провідного рядка, розділивши їх на 5, а за формулою (6) визначаємо елементи другого та індексного рядків. Цільова функція для одного проекту дорівнює Z (X) = 6 * 4 + 3 * 0 = 24.
Однак, один з коефіцієнтів індексного рядка для стовпця Х 2 залишається негативним -0,6, отже даний планне оптимальний, і потрібна ще одна ітерація (крок) для її покращення. Вибираємо провідним другий стовпець і по мінімального значення Q min = 5 визначаємо провідний рядок з базисною змінною Х 4 . Виконавши самі перетворення, отримуємо другий план, який буде оптимальним, оскільки всі індексні коефіцієнти позитивні.
Проаналізуємо отримані результати. При оптимальному рішенніцільова функція має максимальне значення 27тыс.руб., у своїй обидва ресурсу виведені з базису, отже витрачені повністю.
Переконаємося у цьому: 5*2+2*5 = 20 тис.руб., 6*2+12*5=72 кв.м. Шукане рішення Х = (2; 5; 0; 0). Так буває далеко не завжди.
Лекція №10
Тема: Симплексний метод для завдань зі штучним базисом
Симплексний метод рішення базується на введенні додаткових (базових) змінних, що дозволяють утворити одиничну матрицю. Якщо обмеження задачі представлені у вигляді нерівностей:
a i1 X 1 + a i2 X 2 +…a in X n ≥ b i (1)
або рівнянь:
a i1 X 1 + a i2 X 2 +…a in X n = b i (1*),
то неможливо отримати опорний план у шуканому вигляді. В цьому випадку для дотримання рівностей (1*) вводиться штучний базис Y i , причому штучні змінні немає безпосередньо до змісту поставленої завдання, але дозволяють побудувати опорний (стартовий) план:
a i1 X 1 + a i2 X 2 +…a in X n +Y i = b i (2)
Цільова функція під час вирішення завдання максимум запишеться як:
Z(X) = ∑C j X j +(-M)∑Y i (3),
при вирішенні аналогічних завдань на мінімум:
Z(X)=∑C j X j +(M)∑Y i (3*),
де М – дуже велике додатне число, своєрідний штраф за використання штучних змінних.
У разі нерівностей (1) спочатку вводимо додаткові змінні Х n + i зі знаком мінус. Їх матриця не буде одиничною, тому в кожну нерівність системи (1) вводимо штучні змінні У i:
a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b i (4)
Цільова функція при цьому Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (для знаходження максимуму). Застосування штучного базису надає симплексному методу велику гнучкість і дозволяє використовувати його для кола завдань.
приклад . Визначити максимальне та мінімальне значення прибутку при випуску двох видів продукції А та В, якщо витрати на виробництво та прибутковість від реалізації одиниці продукції наведені у таблиці. Основною умовою є повна зайнятість робітників для підприємства.
Математично обмеження випуску продукції запишуться як змішаної системи:
1Х 1 + 1Х 2 ≤ 6,
2Х1 + 1Х2 =8.
Введемо для першої нерівності базисну змінну Х 3 а для другого рівняння штучну змінну Y 1:
1Х 1 + 1Х 2 + Х 3 = 6,
2Х1 + 1Х2 + Y1 =8.
Виразимо з отриманої системи рівнянь Х 3 та Y 1 і для визначення максимуму цільову функцію представимо:
Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=
3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M
Для опорного плану – Х = (0,0,6,8). Побудуємо симплексну таблицю:
| План | Базис | C i / C j | Знач. X i | X 1 | X 2 | X 3 | Y 1 | Q min |
| X 3 | 6/1=6 | |||||||
| Y 1 | -M | 8/2=4 | ||||||
| Z(X) = -8M | -2M-3 | -M-2 | Індексний рядок | |||||
| X 3 | 0,5 | -0,5 | 2/0,5=4 | |||||
| →X 1 | 0,5 | 0,5 | 4/0,5=8 | |||||
| Z(X) = 3 * 4 = 12 | - 0,5 | М+1,5 | Індексний рядок | |||||
| →X 2 | -1 | - | ||||||
| X 1 | -1 | - | ||||||
| Z (X) = 3 * 2 +2 * 4 = 14 | М+1 | Індексний рядок |
Як правило, поліпшення опорного плану починається з виведення з базису штучної змінної Y1. Оптимальний план Х = (2,4,0,0) отриманий на другій ітерації, при цьому дохід максимальний 14тис. руб. , А коефіцієнти індексного рядка невід'ємні. Легко переконатися, що у цій задачі при оптимальному плані ресурси використані повністю (2*1+4*1=6; 2*2+1*4=8).
При знаходженні мінімальної прибутковості інакше формулюємо цільову функцію (як доданок вводиться +MY 1:
Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=
3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M
Опорний плантой самий, але коефіцієнти індексного рядка в симплексной таблиці інші. Провідний стовпець, як і раніше, вибираємо по найбільшому по абсолютного значенняпозитивному коефіцієнту при X 1 , провідний рядок визначається за мінімальним значенням Q min = 4. При першій ітерації з базису виводиться штучна змінна Y 1 .
| План | Базис | C i / C j | Знач. X i | X 1 | X 2 | X 3 | Y 1 | Q min | ||
| X 3 | 6/1=6 | |||||||||
| Y 1 | M | 8/2=4 | ||||||||
| Z(X) = 8М | 2M-3 | M-2 | Індексний рядок | |||||||
| X 3 | 0,5 | -0,5 | 2/0,5=4 | |||||||
| →X 1 | 0,5 | 0,5 | 4/0,5=8 | |||||||
| Z(X) = 3 * 4 = 12 | - 0,5 | -М+1,5 | Індексний рядок | |||||||
Отримані негативні значення коефіцієнтів в індексному рядку X i свідчать про оптимальність 1-го плану, причому мінімальний дохід 12 тис. рублів.
Він забезпечується лише випуском продукції А (продукція не випускається), сировина не використовується повністю (залишок Х 3 = 2т), у своїй виконано основне умова - робітники повністю зайняті з виробництва.
Лекція №11
Тема: Закрите транспортне завдання
1. Математичне формулювання закритого транспортного завдання. Визначення необхідної кількості невідомих.
2. Етапи визначення плану розв'язання транспортного завдання.
