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

2.1. Визначення та форми запису

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

а) канонічна задача ЛП у координатній формі має вигляд:

,
.

Це завдання можна записати, використовуючи знак підсумовування:

,

,

,
,
.

б) канонічна задача ЛП у векторній формі має вигляд:

,

де
;
;

,
;;
.

в) канонічна задача ЛП у матричній формі має вигляд:

,
,

де
,,.

2.2. Приведення загального завдання лінійного

програмування до канонічної форми

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

і додамо до його лівої частини певну величину
таку, щоб нерівність перетворилася на рівність.

Невід'ємна змінна
називається додатковою змінною. Наступна теорема дає основу можливості такого перетворення.

Теорема 2.2.1.Кожному рішенню
нерівності (2.2.1) відповідає єдине рішення рівняння (2.2.2) та нерівності
, і, навпаки, кожному рішенню рівняння (2.2.2)с
відповідає рішення
нерівності (2.2.1).

Доведення.Нехай
розв'язання нерівності (2.2.1). Тоді. Візьмемо число
. Зрозуміло, що
. Підставивши в рівняння (2.2.2), отримаємо

Першу частину теореми доведено.

Нехай тепер вектор задовольняє рівняння (2.2.2) з
, тобто.. Відкидаючи у лівій частині останньої рівності невід'ємну величину
, Отримуємо, і т.д.

Таким чином, доведена теорема фактично встановлює можливість приведення будь-якого завдання ЛП до канонічного виду. Для цього достатньо в кожне обмеження, що має вигляд нерівності, запровадити свою додаткову невід'ємну змінну. Причому, до нерівностей виду (1.2.1) ці змінні увійдуть зі знаком «+», а нерівності виду (1.2.2) – зі знаком « – ». Додаткові змінні вводяться в цільову функціюз нульовими коефіцієнтами і тому її значення не впливають.

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

3. Графічний метод розв'язання задач

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

3.1. Загальні поняття, приклади

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

(3.1.1)

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

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

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

, де
. Усі лінії рівня паралельні між собою. Їх нормаль
.

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

Значення
зростають у напрямку вектора
.
Тому необхідно пересувати лінію рівня у напрямку цього вектора паралельно самій собі до опорної прямої 1 L у напрямку цього вектора паралельно самій собі до опорної прямої 2).

у завданні на максимум і у протилежному напрямку – у завданні на мінімум (до опорної прямої
при обмеженнях

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

Рішення. Будуємо область допустимих рішень. Нумеруємо обмеження завдання. У прямокутній декартовій системі координат (рис. 2) будуємо пряму

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

та область рішень обмеження (2). Знаходимо загальну частину напівплощин рішень, враховуючи обмеження (3). Отриману область допустимих рішень виділимо на рис.2 темним кольором.

Будуємо лінію рівня
та вектор
, який вказує напрям зростання функції і перпендикулярний прямий

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

оптимальне вирішення.
Приклад 3.1. Знайти мінімум функції

при системі обмежень
Рішення. Будуємо область допустимих рішень (див. рис.3), вектор
та одну з ліній рівня
. Переміщуємо лінію рівня в протилежному напрямку

, Оскільки вирішується завдання знайти мінімуму функції. Опорна пряма проходить у цьому випадку через точку А (рис.3), координати якої знайдемо з розв'язання системи
Отже,

. Обчислюємо.
Зауваження.

Насправді від виду області допустимих рішень та цільової функції
при обмеженнях

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

області допустимих рішень та проходить через дві кутові точки цієї області
(Рис.4).
,
Завдання має безліч оптимальних рішень, що є точками відрізка

;
;

,
;
,
;

;
.

.

Ці точки
знаходимо, вирішуючи відповідні системи рівнянь:
,
.

Обчислюємо.

Відповідь:
при переміщуємо у напрямку нормалі. Зважаючи на те, що в цьому напрямку область допустимих рішень не обмежена, лінія рівня йде в нескінченність (рис.5).

Завдання немає рішення внаслідок необмеженості цільової функції.

Ці точки
.

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

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:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рішення

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

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

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

Таким чином, дане завданнялінійного програмування буде записано в наступному канонічному вигляді:

знайти максимум функції

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

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

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

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

Кількість змінних 2 3 4 5 6 7 8 9 10
Кількість рядків (кількість обмежень) 2 3 4 5 6 7 8 9 10

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

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

Математична модель називається канонічної, якщо її система обмежень представлена ​​у вигляді системи 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