Опорний конспект лекцій з курсу Дослідження операцій Тема 3 Лінійне програмування, Графічний розв'язок задачі, НУДПСУ

Лекція №3. ЛІНІЙНЕ ПРОГРАМУВАННЯ. Побудова економіко-математичних моделей задач лінійного програмування. Графічний розв'язок задачі лінійного програмування

План

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

2. Типові задачі оптимізації виробничої програми підприємства.

3. Критерії оптимальності в таких задачах.

4. Доцільність використання графічного способу розв'язку задач лінійного програмування.

5. Багатокутник розв'язків. Області допустимих розв'язків системи нерівностей.

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

2.2. Побудова економіко-математичних моделей задач лінійного програмування

Розглянемо процес побудови математичних моделей задач лінійного програмування на прикладах.

Приклад 2.2. Визначення оптимального асортименту продукції

Підприємство виготовляє два види продукції – П₁ і П₂, яка поступає в оптовий продаж. Для виробництва продукції використовуються два види сировини – А і В. Максимально можливі запаси сировини на добу складають 9 і 13 одиниць відповідно. Витрата сировини на одиницю продукції виду П₁ і виду П₂ дана в табл. 2.1.

Таблиця 2.1. Витрати сировини продукції

Досвід роботи показав, що добовий попит на продукцію П₁ ніколи не перевищує попиту на продукцію П₂ більш ніж на 1 од. Крім того, відомо, що попит на продукцію П₂ ніколи не перевищує 2 од. на добу.

Оптові ціни одиниці продукції рівні: 3 г.о. (грошові одиниці) – для П₁ і 4 г.о. для П₂.

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

Процес побудови математичної моделі для вирішення даної задачі починається з відповідей на наступні питання:

1. Для визначення яких величин повинна бути побудована модель, тобто як ідентифікувати змінні даної задачі?

2. Які обмеження повинні бути накладені на змінні, щоб виконувалися умови, характерні для модельованої системи?

3. У чому полягає мета задачі, для досягнення якої зі всіх допустимих значень змінних потрібно вибрати ті, які відповідатимуть оптимальному (якнайкращому) розв'язку задачі?

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

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

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

2х₁ + 3х₂ ≤ 9;

3х₁ + 2х₂ ≤ 13;

х₁ – х₂ ≤ 1;

х₂ ≤ 2;

х₁ ³ 0;

х₂ ³ 0.

Дохід від реалізації х₁ одиниць продукції П₁ і х₂ одиниць продукції П₂ складе F = 3х₁ + 4х₂.

Таким чином, приходимо до наступної математичної задачі: серед всіх ненегативних розв'язків даної системи лінійних нерівностей потрібно знайти таке, при якому функція F приймає максимальне значення F_max.

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

Приклад 2.3. Використання потужностей устаткування

Підприємство має m моделей машин різних потужностей. Задано план за часом і номенклатурі: Т – час роботи кожної машини; продукції j-го виду повинно бути випущено не менше N_j одиниць.

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

Іншими словами, задача для підприємства полягає в наступному: потрібно визначити час роботи i-ї машини по випуску j-го виду продукції x_ij, що забезпечує мінімальні витрати на виробництво при дотриманні обмежень по загальному часу роботи машин Т і заданій кількості продукції N_j.

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

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

Задача вирішується на мінімум витрат на виробництво

Необхідно також врахувати позитивність змінних х_ij ³ 0.

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

Приклад 2.4. Мінімізація дисбалансу на лінії збірки

Промислова фірма проводить виріб, що є збіркою з m різних вузлів. Ці вузли виготовляються на n заводах.

Із-за відмінностей у складі технологічного устаткування продуктивність заводів по випуску j-го вузла неоднакова і дорівнює b_ij. Кожен i-й завод має в своєму розпорядженні максимальний сумарний ресурс часу протягом тижня для виробництва m вузлів, рівного величині T_i.

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

У даній задачі потрібно визначити щотижневі витрати часу (у годинах) на виробництво j-го вузла на i-му заводі, що не перевищують в сумі погодинні ресурси 1-го заводу і забезпечують максимальний випуск виробів.

Хай x_ij – тижневий фонд часу (у годинах), що виділяється на заводі для виробництва вузла j. Тоді об'єми виробництва вузла j будуть наступними.

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

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

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

Максимізувати

х_ij ³ 0 для всіх i і j.

Ця модель не є лінійною, але її можна привести до лінійної форми за допомогою простого перетворення. Хай Y – кількість виробів.

Цьому виразу з математичної точки зору еквівалентне наступне формулювання: максимізувати Z = Y при обмеженнях

х_ij ³ 0 для всіх і j; Y ³ 0.

Приклад 2.5. Задача складання кормової суміші або задача дієті

Хай крупна фірма (умовно назвемо її «Суперраціон») має можливість купувати m різних видів сировини і готувати різні види сумішей (продуктів). Кожен вид сировини містить різну кількість живильних компонентів (інгредієнтів). Лабораторією фірми встановлено, що продукція повинна задовольняти принаймні деяким мінімальним вимогам з погляду поживності (корисності). Перед керівництвом фірми стоїть задача визначити кількість кожної i-ї сировини, що необхідна для створення суміші мінімальної вартості при дотриманні вимог до загальної витрати суміші і її поживності.

Введемо умовні позначення:

x_i – кількість i-ї сировини в суміші;

m – кількість видів сировини;

n – кількість інгредієнтів в сировині;

a_ij – кількість інгредієнта j, що міститься в одиниці i-го виду сировини;

b_j – мінімальна кількість інгредієнта j, що міститься в одиниці змішай;

c_i – вартість одиниці сировини i;

q – мінімальна загальна вага суміші, що використовується фірмою.

Задача може бути представлене у вигляді

при наступних обмеженнях на загальну витрату сумішей

на поживність суміші

на позитивність змінних

х_i ³ 0, i = 1,…,m. (2.25)

Приклад 2.6. Задача складання рідких сумішей

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

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

х_ij ³ 0, i = 1,…,n, j = 1,…,m.

Перша група обмежень відноситься до об'ємів споживаних хімічних компонентів

де S_i – об'єм i-го хімічного компоненту, який має в своєму розпорядженні фірма на початку планованого періоду.

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

де D_i – мінімальний попит на продукцію у протягом планованого періоду.

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

 або x_ij – rx_i+1j ³ 0,

де r – деяка задана константа.

Позначивши через Р_ij дохід з одиниці продукції х_ij запишемо цільову функцію.

Приклад 2.7. Задача про розкрій або про мінімізацію обрізків

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

Наприклад, продукція паперової фірми випускається у вигляді паперових рулонів стандартної ширини L. За спеціальними замовленнями споживачів фірма поставляє рулони інших розмірів, для цього проводиться розрізання стандартних рулонів. Типові замовлення на рулони нестандартних розмірів можуть включати т видів шириною H_і (i=1,…,m). Відома потреба в нестандартних рулонах кожного виду, вона дорівнює b_і. Можливі n різних варіантів побудови технологічної карти розкрою рулонів стандартної ширини L на рулони довжиною H_і.

Позначимо через a_ij кількість рулонів i-го вигляду, що отримуються при розкрої одиниці стандартного рулону по j-му варіанту. При кожному варіанті розкрою на кожен стандартний рулон можливі втрати, що дорівнюють P_i. До втрат слід відносити також надмірні рулони нестандартної довжини l_i, що отримуються при різних варіантах розкрою y_ij (j = 1,…,n).

В якості змінних слід ідентифікувати кількість стандартних рулонів, які слід розрізати при j-му варіанті розкрою. Визначимо змінну таким чином: x_j – кількість стандартних рулонів, що розрізають по варіанту j (j = 1,…,n).

Цільова функція – мінімум відходів при розкрої.

Обмеження на задоволення попиту споживача.

Приклад 2.8. Транспортна задача

Є три постачальники і чотири споживачі однорідної продукції. Відомі витрати на перевезення вантажу від кожного постачальника кожному споживачеві. Позначимо їх c_ij (j = 1,2,3,4, i = 1,2,3). Запаси вантажів у постачальників дорівнюють a_i (i = 1,…,3). Відомі потреби кожного споживача b_i (j = 1,…,4)_. Вважатимемо, що сумарні потреби дорівнюють сумарним запасам.

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

Введемо змінні х_ij – кількість вантажу, що перевозиться від i-го постачальника j-му споживачеві. Обмеження завдання виглядають таким чином:

потреби всіх споживачів повинні бути задоволені повністю.

або в загальному вигляді

вантаж від постачальника повинен бути вивезений повністю

або у загальному вигляді

умова позитивності змінних

х_ij ³ 0, i = 1,…,3, j = 1,…,4.

Цільова функція – мінімізувати сумарні витрати на перевезення.

Кількість постачальників і споживачів в загальному випадку може бути довільною.

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

1. Обмеження в задачах лінійного програмування можуть бути виражені як рівностями, так і нерівностями.

2. Лінійна функція може прагнути як до максимуму, так і до мінімуму.

3. Змінні в задачах завжди ненегативні.

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

2.3. Графічний розв'язок задачі лінійного програмування

Графічно спосіб розв'язку задач лінійного програмування доцільно використовувати для:

• розв'язків задач з двома змінними, коли обмеження виражені нерівностями;

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

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

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

Z_max = с₁х₁ + с₂х₂, (2.34)

обмеження

х₁ ³ 0, х₂ ³ 0. (2.36)

Графічний розв'язок задачі лінійного програмування базується на тому факті, що кожна з нерівностей (2.35) – (2.36) системи обмежень задачі геометрично визначає напівплощину відповідно з граничними прямими a_i1x₁ + a_i2x₂ = b_i, (i = 1,…,m), x₁ = 0, x₂ = 0. В тому випадку, коли система нерівностей (2.35) – (2.36) сумісна, область розв'язків є множина точок, що належать всім вказаним напівплощинам. Оскільки множина точок перетину даних напівплощин – опукла, то областю допустимих значень є опукла множина, яка називається багатокутником розв'язків. Сторони цього багатокутника лежать на прямих, рівняння яких виходять з початкової системи обмежень заміною знаків нерівностей на знаки рівності.

Областю допустимих розв'язків системи нерівностей (2.35) – (2.36) можуть бути:

• опуклий багатокутник;

• опукла багатокутна необмежена область;

• порожня область;

• промінь;

• відрізок;

• єдина точка.

Цільова функція (2.34) визначає на площині сімейство паралельних прямих, кожній з яких відповідає визначене значення Z.

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

Якщо в одній і тій же системі координат зобразити область допустимих розв'язків системи нерівностей (2.35) – (2.36) і сімейство паралельних прямих (2.34), то задача визначення максимуму функції Z зведеться до знаходження в допустимій області точки, через яку проходить пряма з сімейства Z = const, і яка відповідає найбільшому значенню параметра Z.

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

Для визначення даної вершини побудуємо лінію рівня, що проходить через початок координат і перпендикулярну вектору, і пересуватимемо її у напрямі вектора-градієнта С = (с₁;с₂) до тих пір, поки вона не торкнеться останньої крайньої (кутової) точки багатокутника розв'язків. Координати вказаної точки і визначають оптимальний план даної задачі.

Закінчуючи розгляд геометричної інтерпретації задачі (2.35) – (2.36), відзначимо, що при знаходженні її розв'язку можуть зустрітися випадки, зображені на мал. 2.1 – 2.4. Мал. 2.1 характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. Із мал. 2.2 видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ. На мал. 2.3 зображено випадок, коли максимум недосяжний, а на мал. 2.4. – випадок, коли система обмежень задачі є несумісною. Відзначимо, що знаходження мінімального значення Z при даній системі обмежень відрізняється від знаходження її максимального значення при тих же обмеженнях лише тим, що лінія рівня Z пересувається не у напрямі вектора, а в протилежному напрямі. Таким чином, відмічені вище випадки, що зустрічаються при знаходженні максимального значення цільової функції, мають місце і при визначенні її мінімального значення.

Отже, для практичного розв'язку задач лінійного програмування (2.34) – (2.36) на основі її геометричної інтерпретації необхідно наступне:

1. Побудувати прямі, рівняння яких виходять в результаті заміни в обмеженнях (2.35) – (2.36) знаків нерівностей на знаки рівності.

2. Знайти напівплощини, що визначаються кожним з обмежень.

3. Визначити багатокутник розв'язків.

4. Побудувати вектор-градієнт С = (с₁;с₂).

5. Побудувати пряму, що проходить через початок координат і перпендикулярну вектору С = (с₁;с₂).

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

7. Визначити координати точки максимуму функції і обчислити значення цільової функції в цій точці.

Приклад 2.9.Розглянемо розв'язок задачі про асортимент продукції (приклад 2.2) геометричним способом.

Розв'язок

Побудуємо багатокутник розв'язків (мал. 2.5). Для цього в системі координат x₁0x₂ на площині зобразимо граничні прямі

2x₁ + 3x₂ = 9, (L1);

3x₁ + 2x₂ = 13, (L2);

x₁ – 3x₂ = 1, (L3);

x₂ = 2. (L4).

Узявши яку-небудь точку, наприклад, початок координат, встановимо, яку напівплощину визначає відповідна нерівність. Напівплощини, визначувані нерівностями, на мал. 2.5 показані стрілками. Отже, областю розв'язків є багатокутник OABCD.

Для побудови прямої Z = 3x₁ + 4x₂ = 0 будуємо вектор-градієнт С = (3;4) і через початок координат проводимо пряму, перпендикулярну йому. Побудовану пряму Z = 0 переміщуємо паралельно самій собі у напрямі вектора С = (3;4). З мал. 2.5 виходить, що по відношенню до багатокутника розв'язків опорною ця пряма стає в точці C, де функція приймає максимальне значення. Точка С лежить на перетині прямих L₁ і L₃. Для визначення її координат розв'яжемо систему рівнянь.

Оптимальний план задачі x₁ = 2,4; x₂ = 1,4. Підставляючи значення х₁ і х₂ в лінійну функцію, отримаємо:

Z_max = 3x₁ + 4x₂ = 3 2,4 + 4 1,4 = 12,8.

Отриманий розв'язок означає, що об'єм виробництва продукції П₁ повинен бути рівний 2,4 од., а продукції П₂ – 1,4 од. Дохід, що отримується в цьому випадку, складе: Z = 12,8 г.о.

Контрольні запитання

1. Які основні питання слід розглядати в процесі побудови математичних моделей задач лінійного програмування?

2. Як формується ідентифікується множини змінних?

3. Подайте типові задачі оптимізації виробничої програми підприємства.

4. Що таке критерій оптимальності?

5. Для чого використовується графічний спосіб розв'язку задач лінійного програмування?

6. Що таке багатокутник розв'язків?

7. Які існують області допустимих розв'язків системи нерівностей?

8. Як можна інтерпретувати обмеження?

9. Яка інтерпретація цільової функції на графіку?

10. Що таке лінії рівня цільової функції?

11. Наведіть правила практичного вирішення задач лінійного програмування на основі її геометричної інтерпретації.

З повагою ІЦ “KURSOVIKS”!