Завдання лінійного програмування (ЗЛП). Різні форми запису задачі лінійного програмування

Загалом завдання лінійного програмуваннязаписується так, що обмеженнями є як рівняння, так і нерівності, а змінні можуть бути як невід'ємними, так і такими, що довільно змінюються. У тому випадку, коли всі обмеження є рівняннями і всі змінні задовольняють умову невід'ємності, завдання лінійного програмування називають канонічною. Вона може бути представлена в координатному, векторному або матричному записі.

1. Канонічна задача лінійного програмування в координатному записі має вигляд

У більш компактній формі це завдання можна записати, використовуючи знак підсумовування,

(1.7)

2. Канонічна задача лінійного програмування в векторний записмає вигляд

(1.8)

де ,

3. Канонічна задача лінійного програмування в матричному записі має вигляд

(1.9)

, .

Тут А- матриця коефіцієнтів системи рівнянь, Х- матриця-стовпець змінних завдання, - матриця-стовпець правих частин системи обмежень.

Нерідко використовуються задачі лінійного програмування, які називаються симетричними, які в матричному записі мають вигляд

(1.10)

(1.11)

1.4. Приведення загального завданнялінійного програмування
до канонічної форми

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

Теорема 1.1.Про заміну нерівності рівнянням. Кожному рішенню нерівності

відповідає єдине рішення рівняння

та нерівності

, (1.14)

і, навпаки, кожному рішенню рівняння (1.13) та нерівності (1.14) відповідає єдине рішення нерівності (1.12).

Доведення.Нехай - Вирішення нерівності (1.12), тоді . Позначимо різницю правої та лівої частин цієї нерівності через , тобто.

Очевидно . Підставимо в рівняння (1.13) замість змінних значення , отримаємо

Таким чином, задовольняє рівняння (1.13) та нерівність (1.14). Отже, доведено першу частину теореми.

Нехай тепер задовольняє рівняння (1.13) та нерівність (1.14), тобто маємо

Відкидаючи в лівій частині останньої рівності невід'ємну величину

тобто. задовольняє нерівності (1.12). Теорему доведено.

Якщо нерівність, то додаткову невід'ємну змінну необхідно ввести до неї ліву частинузі знаком мінус, тобто .

Невід'ємні змінні, що вводяться в обмеження нерівності для перетворення їх на рівняння, називаються додатковими змінними. Додаткові змінні вводяться в цільову функціюз нульовими коефіцієнтами і тому впливають її значення.

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

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

приклад 1.1.Привести до канонічному виглядузавдання лінійного програмування.

Рішення. Перейдемо до завдання знайти максимуму цільової функції. Для цього змінимо знаки коефіцієнтів цільової функції. Для перетворення на рівняння другої та третьої нерівностей системи обмежень введемо невід'ємні додаткові змінні (на математичній моделі ця операція відзначена буквою Д). Змінна вводиться в ліву частину другої нерівності зі знаком "+", оскільки нерівність має вигляд . Змінна вводиться в ліву частину третьої нерівності зі знаком "-", оскільки нерівність має вигляд . У цільову функцію змінні вводяться з коефіцієнтом, рівним нулю. Змінну , на яку не накладено умову невід'ємності замінюємо різницею , . Записуємо завдання у канонічному вигляді

У деяких випадках виникає необхідність приведення канонічного завдання до симетричного завдання. Розглянемо приклад.

приклад 1.2.Привести до симетричного виглядузавдання лінійного програмування

: Завдання лінійного програмування (ЗЛП)

1. Лінійне програмування

2. Види завдань лінійного програмування

3. Форми запису ЗЛП

4. Канонічна форма завдань лінійного програмування

Лінійне програмування

Лінійне програмування - це розділ матпрограмування, який застосовується при розробці методів знаходження екстремуму лінійних функцій кількох змінних при лінійних додаткові обмеження, що накладаються на змінні.

За типом розв'язуваних завдань методи ЛП поділяються на універсальні та спеціальні. За допомогою універсальних методівможуть вирішуватись будь-які завдання лінійного програмування (ЗЛП). Спеціальні враховують особливості моделі завдання, її цільової функції та системи обмежень.

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

Малюнок 1 - Екстремум цільової функції

Математична модель ЗЛП записується так:

max (або min) Z = z (X), (1)

ОДР може бути представлена системою лінійних рівняньчи нерівностей.

Вектор Х = (х 1, х 2, .... x п) є вектором керування або керуючим впливу.

Допустимий план Х, у якому критерій оптимальності Z=z(X) досягає екстремального значення, називається оптимальним і позначається через X*, екстремальне значення цільової функції -- через Z*=z(X*).

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

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

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

При випуску продукції підприємство обмежено наявними ресурсами, кількість яких позначимо m, а вектор ресурсів В = (b 1, b 2, ..., b т). Відомі також технологічні коефіцієнти a ij, які показують норму витрати i ресурсу на виробництво одиниці j продукції. Ефективність випуску одиниці j-ї продукціїхарактеризується прибутком p j.

Потрібно визначити план випуску продукції Х = (х 1, х 2, ..., x п), що максимізує прибуток підприємства при заданих ресурсах.

Цільова функція виглядає так

при обмеженнях

Часто асортимент продукції встановлюється вищою організацією, тобто його обсяги повинні бути укладені в деяких межах D n j і D j: тоді задається таке обмеження:

Модель завдання оптимального використання ресурсів лежить в основі моделей оптимізації річної виробничої програми підприємства. У модель включаються обмеження щодо фонду часу роботи обладнання.

Зберігаючи колишні позначення, запишемо через б j і з j відповідно відпускну ціну та витрати на одиницю j-ї продукції. Як критерій оптимальності можуть бути прийняті:

1) максимум прибутку

2) мінімум витрат за виробництво

3) максимум випуску у вартісному вираженні (виручки від продукції)

приклад. Підприємство може виготовляти чотири види продукції 1, 2, 3 та 4. Збут будь-якого її обсягу забезпечений. Підприємство має у своєму розпорядженні протягом кварталу трудові ресурси в 100 людино-змін, напівфабрикати масою 260 кг, верстатне обладнання в 370 верстато-змін. Норми витрати ресурсів та прибуток від одиниці кожного виду продукції представлені в табл.1.

Необхідно:

а) скласти математичну модельзавдання визначення плану випуску продукції, у якому досягається максимум прибутку;

б) вирішити завдання з вимогою комплектації, щоб кількість одиниць третьої продукції була втричі більше кількостіодиниць першої;

в) з'ясувати оптимальний асортимент при додаткових умов: першого продукту випускати не менше 25 одиниць, третього - не більше 30, а другого та четвертого - щодо 1:3.

Таблиця 1

Вихідні дані

Математична модель завдання:

цільова функція:

max: Z=40x1+50x2+100x3+80x4

при обмеженнях:

а) на трудові ресурси:

2,5x1+2,5x2+2x3+1,5x4? 100;

на напівфабрикати:

4x1+10x2+4x3+6x4? 260;

на верстатне обладнання:

8x1+7x2+4x3+10x4? 370;

умова невід'ємності:

б) додаткова вимога комплектації висловиться умовою

3x 1 = x 3 тобто 3x 1 x 3 = 0;

в) граничні умови та умова комплектації представимо так: х 1 ?25,

х 3 ?30, 3 * х 2 = х 4 .

Завдання про розміщення замовлень або завантаження взаємозамінних груп обладнання. Мова йдерозподілу замовлень між m (i=1,…, m) підприємствами (цехами, верстатами, виконавцями) з різними виробничими та технологічними характеристиками, але взаємозамінними у сенсі виконання замовлень. Потрібно скласти такий план розміщення замовлень, у якому завдання було б виконано, а показник ефективності досягав екстремального значення.

Сформулюємо завдання математично. Нехай на однорідних групах обладнання потрібно виготовити п видів продукції. План випуску кожного виду продукції на певний періодзаданий набором х j (j=1,2, …п). Потужність кожного виду обладнання обмежена і дорівнює b i. Відома технологічна матриця A = | | a ij | |, де a ij - число одиниць j-ої продукції, що випускається в одиницю часу на i-му устаткуванню. Матриця С - матриця витрат, де c ij - витрати, пов'язані з випуском одиниці j-їпродукції на i-му устаткуванні. Х - вектор обсягу продукції, що випускається.

Модель завдання набуде наступного вигляду:

цільова функція - мінімізація витрат на реалізацію всіх замовлень

при обмеженнях:

а) за потужністю обладнання

б) випуск продукції

в) умова невід'ємності

Це завдання називають розподільчою або завданням розподілу.

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

Як цільовий прибуток також можна прийняти:

а) максимум прибутку

б) мінімум витрат верстатного часу

Т.к. Будь-яка модель містить спрощувальні передумови, для коректного застосування отриманих результатів необхідно чітке розуміння суті цих спрощень, що, зрештою, і дозволяє зробити висновок про їхню допустимість або неприпустимість. Найбільш суттєвим спрощенням у розглянутих моделях є припущення про прямопропорційну (лінійну) залежність між обсягами витрати ресурсів та обсягами виробництва, що задається за допомогою норм витрат a ij . Очевидно, що це припущення далеко не завжди виконується. Так обсяги витрати багатьох ресурсів (наприклад, основних фондів) змінюються стрибкоподібно - в залежності від зміни програми виробництва Х. До інших спрощує передумов ставляться припущення про незалежність цін j від обсягів x j, що справедливо лише для певних меж їх зміни. Дані «уразливі» місця важливо знати ще й тому, що вони вказують на принципові напрямки вдосконалення моделі.

Форми запису ЗЛП

Існує 3 форми запису ЗЛП:

1) як функцій

max(або min)Z=,max(або min)Z=,

2) векторна форма

(скалярний добуток векторів)

при обмеженнях

A 1 х 1 +A 2 х 2 +..+A n x n = B

Де вектори

З = (З 1, З 2 .. З n), Х = (Х 1, Х 2 .. Х n), і.

3) матрична форма

при обмеженнях

де З = (з 1, з 2, ... з n),

Канонічна форма завдань лінійного програмування

Якщо всі обмеження задачі лінійного програмування є рівняннями і всі змінні x j накладаються умови неотрицательности, вона називається завданням лінійного програмування в канонічної формі чи канонічної завданням лінійного програмування (КЗЛП).

при обмеженнях

Для того щоб перейти від ЗЛП до КЛЗП, необхідно перейти від обмежень нерівностей до обмежень рівності та замінити змінні, які не підпорядковуються умовам невід'ємності.

Правила приведення ЗЛП до канонічного виду:

1) якщо в обмеженнях права частинанегативна, слід помножити це обмеження на -1;

2) якщо серед обмежень є нерівності, то шляхом введення додаткових невід'ємних змінних вони перетворюються на рівність;

3) якщо деяка змінна xk не має обмежень за знаком, то вона замінюється в цільовій функції і в усіх обмеженнях різницею між двома новими невід'ємними змінними: xk=x * k - xl, де l - зведений індекс, x * k>=, xl >=0.

Розглянемо приклад. Наведемо до канонічної форми:

Введемо у кожне рівняння системи обмежень що вирівнюють змінні х 4 , х 5 , х 6 . Система запишеться у вигляді рівностей, причому в перше і третє рівняння системи обмежень змінні х 4 х 6 вводяться в ліву частину зі знаком «+», а в друге рівняння вводиться х 5 зі знаком «-».

Вільні члени в канонічній формі повинні бути позитивними, для цього два останні рівняння помножимо на -1:

У канонічній формі запису завдань лінійного програмування всі змінні, що входять до системи обмежень, мають бути невід'ємними. Припустимо, що

Підставляючи даний виразу систему обмежень та цільову функцію та записуючи змінні у порядку зростання індексу, отримаємо завдання лінійного програмування, подану в канонічній формі:

оптимізаційний симплексний лінійний програмування

Завдання МП

Загальної ЗЛПназивають <,=,>=)bi (i=1,n) (2) за умови xj>

Симетричної < либо = и не отрицательных переменных и задача минимизации функции (1) при лінійних обмеженняху нерівностях зі знаком > Канонічної змішаної.

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Геометрична інтерпретація цільової функції та обмеження ЗЛП. Геометричне формулювання ЗЛП.

Нехай дане завдання f=c1x1+c2x2-max (1)

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

План завдання (х1, х2) – точка на площині. Кожне нерівність с-ми 2 предст. собою напівплощину. Напівплощина - опукла безліч. Випуклимназ-ся безліч у якому точки відрізка що з'єднують (х1 і х2) належать цій множині те саме належать множині. С-ма 2 являє собою перетин напівплощин. При перетині можуть вийти:

1) опукла багатокутна замкнута область.

2) опукла відкрита багатокутна область

3) єдина точка

4) порожня множина

5) промінь та відрізок

Геометрична інтерпретація цільової функції:ф-ція 1 являє собою сімейство паралельних прямих, які називають лініями рівня (лініями постійного значення цільової функції). Приватні похідні функції х1 і х2 показують швидкість зростання цільової функції вздовж координат осей. Вектор-градієнтпоказує напрямок якнайшвидшого зростання цільової функції. Для задачі 1-3 вектор-градієнт = (с1; с2) Виходить з точки (0,0) і направлений у точку з координатами (с1; с2). Вектор-градієнт перпендикулярний до ліній рівня. Перетин напівплощин прийнято наз-ть областю допустимих рішень (ОДР).

Основна теорема ЛП. Принципова схемарішення ЗЛП, що з цієї теореми.

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

БП		СП-Xm+1-Xm+2-Xn
х1	b1o	b11 b12 b1n-m
х2	b2o	b21 b22 b2n-m
хm	bm	bm1 bm2 bmn-m
f	boo	bo1 bo2 bon-m

Алгоритм симплекс-методу.

1. привести модель завдання до канонічної форми;

2. знайти початковий опорний план;

3. записати завдання в симпл. таблицю;

5. Перейти до нового опорного плану, до нової сімп. таблиці. Для того щоб перейти до нового опорного плану, достатньо замінити одну базову змінну вільною. Змінну, що включається в базис і відповідної їй роздільний стовпець визначають за найбільшим за модулем негативним елементом f-рядка. Змінну, яка виключає з базису і відповідну їй роздільну здатність визначають за найменшим симплексним відношенням, тобто. відношенню елементів одиничного стовпця до відповідного елемента стовпця, що дозволяє. Симплексне відношення – величина невід'ємна. На перетині роздільної здатності та роздільного стовпця розташований роздільний елемент, щодо якого виконується симплексне перетворенняслід. правилу: 1. елементи роздільної здатності діляться на роздільний елемент; 2. елементи роздільного стовпця діляться на роздільний елемент і змінюють знак на протилежний; 3. Інші елементи таблиці перехитуються за правилом прямокутника.

bij bis bkj = (bkj * bis-bij * bks) / bi

А теорема двоїстості.

якщо одне з двоїстих завдань має оптим план, те й інше решима, тобто. має опт. При цьому екстремальні значення цільових функцій збігаються (j=від 1 до n) Σcjxj*= (i=від 1 до m)Σbiyi* якщо у вихідн. Завдання цільова функція необмежена на безлічі планів, то в двоїстої задачісистема обмежень несумісна.

Теорема про ранг матриці ТЗ.

Ранг матриці А трансп.завдання на одиницю менше числа рівнянь: r(A)=m+n-1.

39. Алгоритм побудови початкового опорного плану ЗЛП.

Для знаходження початкового опорного плану можна запропонувати наступний алгоритм:

1. записати завдання формі жерданової таблиці те щоб всі елементи стовпця вільних членів були неотрицательными, тобто. виконувалася нерівність аio>=0 (i=1,m). Ті рівняння с-ми, у яких вільні члени негативні, попередньо множаться на -1.

		-x1 ….. -xn
0=	a1o	a11 …. a1n
…..	…..	………………………..
0=	amo	am1 ….. amn
f=		-c1 …. -cn

Таблицю перетворювати кроками жерданових винятків, замінюючи нулі у лівому стовпці відповідними х. При цьому на кожному кроці вирішальним може бути обранийбудь-який стовпець, що містить хоча б один позитивний елемент. Розв'язувальний рядок визначається за найменшим із відносин вільних членів до відповідного позитивного елементу роздільного стовпця. Якщо в процесі винятків зустрінеться 0-рядок, всі елементи якої-нули, а вільний член відмінний від нуля, то с-ма обмежувальних рівнянь рішень немає. Якщо ж зустрінеться 0-рядок, у якому, крім вільного члена, інших позитивних елементів немає, то с-ма обмежувальних рівнянь немає неотрицательных решений Якщо с-ма обмежувальних рівнянь спільна, То через кілька кроків всі нулі в лівому стовпці будуть заміщені х і тим самим отриманий деякий базис, а отже, і опорний план, що відповідає йому.

40. Алгоритм побудови оптимального опорного плану ЗЛП.

Початковий опорний план Хо досліджується оптимальність.

Якщо f-рядку немає негативних елементів (крім вільного члена), -план оптимальний. Якщо у f-рядку немає також і нульових елементівто оптимальний план єдиний; якщо ж серед елементів є хоча б один нульовий, то оптимальних планів безліч. Якщо в f-рядку є хоча б один негативний елемент, а у відповідному стовпці немає позитивних, то цільова функція не обмежена в допустимій області. Завдання не можна розв'язати. Якщо в f-рядку є хоча б один негативний елемент, а в кожному стовпці з таким елементом є хоча б один позитивний, то можна перейти до нового опорного плану, ближчого до оптимального. Для цього стовпець з заперечним елементом у f-рядку беруть за дозвільний; опред-ют по мінімальному симплексному відношенню роздільну здатність і роблять крок жорданова виключення. Отриманий опорний план знову досліджується оптимальність. Це повторюється до того часу, доки знайдено оптимальний опорний план чи встановлено нерозв'язність завдання.

Алгоритм методу Гоморі.

1.Сімплекс-методом знаходять оптимальний план задачі. Якщо всі компоненти оптимального плануцілі, то він -оптимальний. В іншому випадку переходять до пункту 2

2. Серед нецілих компонентів слід вибрати ту, у якої дробова частинає найбільшою і за відповідним цим рядком симплексної таблиці сформулювати правильне відсікання за формулою

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3.Сформульовану нерівність перетворити на еквівалентну нульову рівність і включити в симплексну таблицюз нецілочисленним оптимальним планом

4.Отриману розширену задачу вирішують симплекс-методом. Якщо отриманий план не є цілочисловим, нова переходять до пункту 2.

Якщо в процесі рішення з'явиться рядок з нецілісним вільним членом і іншими коефіцієнтами, то відповідне рівняння не має рішення в цілих числах. У такому разі і вихідне завдання нерозв'язне в цілих числах. Метод Гоморі має обмежене застосування. З його допомогою доцільно вирішувати невеликі завдання, т.к. кількість інтерацій може бути дуже великою.

Різні формизаписи ЗЛП (загальна, канонічна, симетрична)

Завдання МП: визначення оптимального плану, опред-е оптимального обсягу випуску продукції, опред-е оптим-го поєднання посівів з/хоз-их культур, форм-е оптим-го пакету активів, максиміз-ний прибуток банку і т.д.

Загальною ЗЛП називають завдання максимізації (мінімізації) лінійної функції f=Σcj*xj-max(min) (1) при лінійних обмеженнях ∑aij *xj(=<,=,>=)bi (i=1,n) (2) за умови xj>=0(j=1,n1), xj-довільне (j=n1+1,n)(3) де cj,aij, bi-постійні числа.

Симетричноїформою запису ЗЛП наз-ся завдання максимізації функції (1) при лінійних обмеженнях у нерівностях зі знаком< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >або = і невід'ємних змінних. Канонічноїформою запису ЗЛП наз-ся завдання максимальної функції (1) при лінійних обмеженнях рівності і невід'ємних змінних. Будь-яка інша форма називається змішаної.

min f(x) = -max(-f(x))

Перетворення нерав-ва на рівняння і навпаки осущ-ся з урахуванням Лемми: всякому рішенню х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) і навпаки. Будь-якому рішенню x1…xn,xn+1 рівняння 6 і нерівності 7 відповідає розв'язання x1…xn нерівності 5.

Щоб від зад сим форми перейти до зад канонич виду, необхідно ввести балансові (вирівнюючі) змінні.Це грунтується на теоремі про нерівність: будь-яке нерав-во можна як ур-я чи найпростішого нерав-ва.

Канонічна форма ЗЛП- Завдання лінійного програмування виду ax = b де a - матриця коефіцієнтів, b - вектор обмежень.

Призначення сервісу. Онлайн-калькулятор призначено для переходу ЗЛП до КЗЛП. Приведення завдання до канонічної форми означає, що це обмеження матимуть вигляд рівностей, шляхом введення додаткових змінних.
Якщо будь-яку змінну x j не накладено обмеження, вона замінюється на різницю додаткових змінних, x j = x j1 - x j2 , x j1 ≥ 0, x j2 ≥ 0.

Інструкція. Виберіть кількість змінних та кількість рядків (кількість обмежень). Отримане рішення зберігається у файлі Word.

Як привести завдання лінійного програмування до канонічної форми

Математична модель ЗЛП називається Основнийякщо обмеження в ній представлені у вигляді рівнянь за умови невід'ємності змінних.

Математична модель називається канонічноїякщо її система обмежень представлена у вигляді системи m лінійно незалежних рівнянь (ранг системи r=m), в системі виділено одиничний базис, визначені вільні змінні та цільова функція виражена через вільні змінні. У цьому праві частини рівнянь неотрицательны (b i ≥ 0).

Змінні, що входять до одного з рівнянь системи з коефіцієнтом один і відсутні в інших рівняннях, називаються базисними невідомими, а всі інші - вільними.

Рішення системи називається базисним, якщо в ньому вільні змінні дорівнюють 0, і воно має вигляд:
X баз = (0, 0; b 1 …, b m), f (X баз) = c 0

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

Базисне рішення називається опорним, якщо вона припустима, тобто. Усі праві частини рівнянь системи (або нерівностей) позитивні b i ≥ 0.

Компактна форма канонічної моделі має вигляд:
AX = b
X ≥ 0
Z = CX(max)

Поняття допустимого рішення, сфери допустимих рішень, оптимального рішення задачі лінійного програмування.
Визначення 1 . Вектор X, що задовольняє системі обмежень ЗЛП, у тому числі й умов невід'ємності, якщо вони є, називається допустимим рішенням ЗЛП.
Визначення 2 . Сукупність всіх припустимих рішень утворює область припустимих рішень (ОДР) ЗЛП.
Визначення 3 . Допустиме рішення, для якого цільова функція досягає максимуму (або мінімуму), називається оптимальним рішенням.

Приклад №1. Наступне завдання ЛП привести до канонічного вигляду: F(X) = 5x1 + 3x2 → max при обмеженнях:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Модель записана в стандартній формі. Введемо балансові невід'ємні змінні x 3 x 4 x 5 x 6 які додамо до лівих частин обмежень-нерівностей. У цільову функцію усі додаткові змінні введемо з коефіцієнтами, рівними нулю:
У першому нерівності сенсу (≤) вводимо базову змінну x 3 . У другій нерівності значення (≤) вводимо базову змінну x 4 . У третій нерівності вводимо базову змінну x 5 . У 4-й нерівності - базисну змінну x 6 . Отримаємо канонічну форму моделі:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Приклад №2. Знайти два опорні рішення системи
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2

Запис цільової функції та системи обмежень у різних завданняхлінійного програмування неоднаковий: у одних завданнях потрібно знайти мінімум цільової функції, а інших – максимум; в одних випадках змінні, що шукаються, залежать від одного індексу, а в інших – від двох; в одних завданнях обмеження задані у вигляді системи лінійних нерівностей, а інших – як системи лінійних рівнянь. Насправді можливі також завдання, у яких частина обмежень має вигляд лінійних нерівностей, а частина – лінійних рівнянь. Також не у всіх завданнях може вимагатися невід'ємність змінних.

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

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

і потрібно знайти максимум лінійної цільової функції

то вважається, що завдання лінійного програмування записано у канонічній формі.

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

У разі, коли потрібно знайти мінімум функції , можна перейти до знаходження максимуму функції , оскільки справедливе твердження:
.

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

Зауважимо, що кількість введених додаткових невід'ємних змінних завжди дорівнює кількості нерівностей у вихідній системі обмежень.

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

Зазначимо також, що якщо певна змінна не підпорядковується умові невід'ємності, то її потрібно замінити двома невід'ємними змінними і , Прийнявши
.

приклад. Записати в канонічній формі наступне завдання лінійної оптимізації: знайти мінімум функції
при обмеженнях

Рішення

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

Так як кількість нерівностей, що входять до системи обмежень завдання, дорівнює чотирьом, цей перехід має бути здійснений з введенням чотирьох додаткових невід'ємних змінних. При цьому в другій і четвертій нерівностях стоїть знак. » , тому до їхньої лівої частини додаткові змінні додаємо. У першій та третій нерівностях – знак « », отже від їхньої лівої частини додаткові змінні віднімаємо.