🗊Презентация Задача лінійного програмування та методи її розв’язування

Тема 2 Задача лінійного програмування та методи її розв’язування

2.1. Постановка задач: загальна задача оптимального лінійного програмування та форми її запису Загальна лінійна (всі змінні – х в першому степені) математична модель економічних процесів і явищ – так звана загальна задача лінійного програмування подається у вигляді: (1) (2) (3)

де с1,2….n – коефіцієнти цільової функції; де с1,2….n – коефіцієнти цільової функції; х1,2….n – змінні; а1,2….m – коефіцієнти при змінних; b1,2….m – вільні члени (ресурси, запаси).

(!) Потрібно знайти значення змінних x1, x2, …, xn, які задовольняють умови (2) і (3), тоді як цільова функція набувала би екстремального (максимального чи мінімального) значення. (!) Потрібно знайти значення змінних x1, x2, …, xn, які задовольняють умови (2) і (3), тоді як цільова функція набувала би екстремального (максимального чи мінімального) значення.

Задачу (1) – (3) доцільно звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2): Задачу (1) – (3) доцільно звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2): всі bi (i = 1, 2, …, m) невід’ємні; всі обмеження є рівностями. 1. Якщо якесь bi від’ємне, то, помноживши i-те обмеження на (–1), дістанемо у правій частині відповідної рівності додатне значення. 2. Коли i-те обмеження має вигляд нерівності , то останню завжди можна звести до рівності, увівши додаткову змінну xn + 1: . Аналогічно обмеження виду зводимо до рівності, віднімаючи від лівої частини додаткову змінну хn + 2, тобто

ПРИКЛАД Записати в канонічній формі таку задачу лінійного програмування: за умов . Розв’язування. Помножимо другу нерівність на (–1) і введемо відповідно допоміжні змінні х4 і х5 для другого та третього обмеження: Неважко переконатися, що допоміжні змінні, у цьому разі х4 і х5, є невід’ємними, причому їх уведення не змінює цільової функції.

 Отже, будь-яку задачу лінійного програмування можна записати в такій канонічній формі: (4) за умов (5) (6)

Задачу (4) – (6) можна розв’язувати на мінімум, якщо цільову функцію помножити на (–1), тобто: Задачу (4) – (6) можна розв’язувати на мінімум, якщо цільову функцію помножити на (–1), тобто:

Основні поняття Допустимий розв’язок або допустимий план задачі – відображає вектор , координати якого задовольняють систему обмежень (2) і (3). (2) (3)

Сукупність допустимих розв’язків (планів) задачі утворює область допустимих розв’язків задачі. Сукупність допустимих розв’язків (планів) задачі утворює область допустимих розв’язків задачі. Опорним планом задачі лінійного програмування називається допустимий план, який задовольняє не менш ніж п лінійно незалежних обмежень системи (2) у вигляді строгих рівностей разом з обмеженням (3) щодо знака. Опорний план називається невиродженим, якщо він містить точно m додатних компонент. У противному разі опорний план є виродженим. Оптимальним розв’язком (планом) називається той допустимий розв’язок, при якому лінійна функція (1) набуває максимального (мінімального) значення.

Запис задачі лінійного програмування Задачу лінійного програмування (4-6) зручно записувати за допомогою знака суми «»: за умов Запис задачі лінійного програмування у векторно-матричному вигляді:

2.2. Побудова економіко-математичних моделей задач лінійного програмування 1 крок - З точки зору економіки, а не математики, відповідаємо на такі питання:  Що є шуканими величинами задачі?  Якою є мета розв’язку? Який параметр задачі є критерієм ефективності (оптимальності) розв’язку? У якому напрямі повинно змінюватись значення цього параметра для досягнення найкращих результатів?  Які умови у відношенні шуканих величин і ресурсів задачі повинні бути виконані? Ці умови встановлюють, як повинні співвідноситись один з одним різні параметри задачі.

2 крок – запис попередніх відповідей у математичній формі. При цьому: 2 крок – запис попередніх відповідей у математичній формі. При цьому:  Шукані величини є змінними задачі, які, як правило, позначають малими латинськими літерами з індексами. Наприклад, однотипні змінні зручно подавати у вигляді  Мета розв’язку записується у вигляді цільової функції. Яку позначають, наприклад . Математична формула цільової функції відображає спосіб розрахунку значень параметра – критерію ефективності задачі.  Умови, які накладаються на змінні і ресурси задачі, записують у вигляді системи рівностей або нерівностей, тобто обмежень. Ліві і праві частини обмежень відображають спосіб одержання (розрахунок або числові значення з умови задачі) значень тих параметрів задачі, на які були накладені відповідні обмеження.  В процесі запису математичної моделі необхідно вказувати одиниці виміру змінних задачі, цільової функції і всіх обмежень.

Приклади побудови лінійних математичних моделей Задача 1 (задача про фарби). Невелика компанія Reddy Mikks виробляє два види фарб: перший – для зовнішніх робіт (Ф1), а другий – для внутрішніх (Ф2). Для виробництва фарб використовують два складники: А і В. Максимально можливі добові запаси цих складників 6 т і 8 т відповідно. Відомі витрати цих складників А і В на одну тону відповідних фарб:

Після вивчення ринку збуту відділ маркетингу компанії встановив, що добовий попит на фарбу другого виду ніколи не перевищує попиту на фарбу першого виду більше, ніж на 1 тону, а також поставив умову, щоб добове виробництво фарби другого виду не перевищувало 2 тон (у зв’язку з відсутністю відповідного попиту). Оптові ціни однієї тони фарби рівні 3 тис. грн. для Ф1, та 2 тис. грн. для Ф2. Компанія хотіла б визначити, яким чином можна збільшити добовий дохід. Після вивчення ринку збуту відділ маркетингу компанії встановив, що добовий попит на фарбу другого виду ніколи не перевищує попиту на фарбу першого виду більше, ніж на 1 тону, а також поставив умову, щоб добове виробництво фарби другого виду не перевищувало 2 тон (у зв’язку з відсутністю відповідного попиту). Оптові ціни однієї тони фарби рівні 3 тис. грн. для Ф1, та 2 тис. грн. для Ф2. Компанія хотіла б визначити, яким чином можна збільшити добовий дохід. Необхідно:  Побудувати математичну модель задачі.  Встановити, яку кількість фарби кожного виду необхідно виробляти, щоб дохід від реалізації продукції був максимальним.

Побудова математичної моделі задачі  Шукані величини – добові об’єми виробництва кожного виду фарби: – фарби першого виду (Ф1) – фарби другого виду (Ф2)  Цільова функція – необхідно досягти максимуму прибутку від реалізації продукції, отже, критерій ефективності – параметр добового доходу, який повинен прямувати до максимуму. Оскільки оптові ціни на 1 тону фарб складають 2 і 3 тис. грн. відповідно, то: дохід від продажу Ф1 рівний дохід від продажу Ф2 рівний

Тому цільова функція записується у вигляді суми доходу від продажу Ф1 та Ф2: Тому цільова функція записується у вигляді суми доходу від продажу Ф1 та Ф2:      Обмеження. Можливі об’єми виробництва фарб та обмежуються такими умовами:  кількість складників А і В, що витрачаються за добу на виробництво Ф1 та Ф2 не може перевищувати їх добового запасу, тобто: За умовою:

 обмеження по добовому об’єму виробництва Ф1 в порівнянні з об’ємом виробництва Ф2:  обмеження по добовому об’єму виробництва Ф1 в порівнянні з об’ємом виробництва Ф2: За умовою:  обмеження по добовому виробництву фарби другого виду: За умовою:

 невід’ємність об’ємів виробництва:  невід’ємність об’ємів виробництва: Отже, математична модель задачі має вигляд:

Задача 2. Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць – А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в таблиці: Задача 2. Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць – А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в таблиці: Прибуток фірми від реалізації однієї полиці моделі А дорівнює 50 у. о., а моделі В – 30 у. о. Вивчення ринку збуту показало, що тижневий попит на книжкові полиці моделі А ніколи не перевищує попиту на модель В більш як на 30 одиниць, а продаж полиць моделі В не перевищує 80 одиниць на тиждень.

Необхідно: Необхідно:  Побудувати математичну модель задачі.  Визначити обсяги виробництва книжкових полиць цих двох моделей, що максимізують прибуток фірми.

Побудова математичної моделі задачі  Шукані величини: х1 – кількість полиць моделі А, виготовлених фірмою за тиждень, а х2 – кількість полиць моделі В.  Цільова функція – максимум прибутку фірми від реалізації продукції. Математично вона подається так:  Обмеження. Обмеження задачі враховують тривалість роботи верстатів 1 та 2 для виготовлення продукції та попит на полиці різних моделей.

Обмеження на тривалість роботи верстатів 1 та 2 мають вид: Обмеження на тривалість роботи верстатів 1 та 2 мають вид: для верстата 1: 30х1 + 15х2 ≤ 2400 (хв); для верстата 2: 12х1 + 26х2 ≤ 2160 (хв). Обмеження на попит записуються так: та х2 ≤ 80. Отже, економіко-математична модель задачі має вигляд:

Задача 3. На ринок доставляється картопля з трьох фермерських господарств по ціні відповідно 80, 75, та 65 коп. за 1 кг. На завантаження 1 т картоплі у фермерських господарствах відповідно витрачається по 1, 6, 5 хвилин. Замовлено 12 т картоплі і для своєчасної доставки необхідно, щоб на її завантаження витрачалось не більше сорока хвилин. Визначити з яких фермерських господарств і в якій кількості необхідно доставити картоплю, щоб загальна вартість закупівлі була мінімальною, якщо господарства можуть виділити для продажу відповідно 10, 8 та 6т картоплі. Задача 3. На ринок доставляється картопля з трьох фермерських господарств по ціні відповідно 80, 75, та 65 коп. за 1 кг. На завантаження 1 т картоплі у фермерських господарствах відповідно витрачається по 1, 6, 5 хвилин. Замовлено 12 т картоплі і для своєчасної доставки необхідно, щоб на її завантаження витрачалось не більше сорока хвилин. Визначити з яких фермерських господарств і в якій кількості необхідно доставити картоплю, щоб загальна вартість закупівлі була мінімальною, якщо господарства можуть виділити для продажу відповідно 10, 8 та 6т картоплі.

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

2.3. Розв’язування задачі лінійного програмування симплекс-методом – самостійне вивчення

2.4. Графічний метод розв’язування задачі лінійного програмування Графічний метод є доволі простим і наочним для розв’язування ЗЛП з двома змінними. Він базується на геометричному представленні допустимих розв’язків і цільової функції. Множина обмежень довільної ЗЛП є множиною розв’язків деякої системи лінійних рівнянь і нерівностей. Спільною властивістю таких множин є властивість опуклості.

Означення: Множина називається опуклою, якщо разом з кожними двома своїми точками вона містить весь відрізок, який з’єднує ці точки (опуклі – рис.1., не опуклі – рис.2): Означення: Множина називається опуклою, якщо разом з кожними двома своїми точками вона містить весь відрізок, який з’єднує ці точки (опуклі – рис.1., не опуклі – рис.2):

Нехай необхідно розв’язати ЗЛП з двома змінними: за обмежень: Кожна нерівність цієї системи геометрично визначає в декартовій системі координат х1Оx2 півплощину з граничною прямою (i = 1, 2, ...,т). Умови невід’ємності визначають півплощини відповідно з граничними прямими (тобто I-шу координатну чверть).

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

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

Напрям зростання значення цільової функції задачі задає вектор Напрям зростання значення цільової функції задачі задає вектор який є перпендикулярним до кожної з ліній рівня. ! Напрям вектора співпадає з напрямом зростання цільової функції, а напрям спадання цільової функції є напрямом, протилежним до напряму вектора .

Суть графічного методу полягає в наступному: ! за напрямом (або проти напряму) вектора в області допустимих розв’язків M здійснити пошук оптимальної точки Оптимальною вважається та точка, через яку проходить лінія рівня , яка відповідає найбільшому (найменшому) значенню функції F. Оптимальний розв’язок завжди знаходиться на межі області допустимих розвязків, наприклад, в останній вершині многокутника допустимих розвязків, через яку проходить цільова пряма або на всій його стороні.

Залежно від взаємного розташування многокутника М і ліній рівня можливі такі ситуації: Залежно від взаємного розташування многокутника М і ліній рівня можливі такі ситуації:  функція досягає свого найбільшого (найменшого) значення в одній точці (рис.3);  функція досягає свого найбільшого значення в нескінченній кількості точок (в кожній точці сторони многокутника) (рис.4);

Якщо ж множина М необмежена, то можливі такі ситуації: Якщо ж множина М необмежена, то можливі такі ситуації:  функція F обмежена зверху, але необмежена знизу на множині M (у цьому випадку ЗЛП на знаходження найбільшого значення має розв’язок, а на знаходження найменшого – ні) (рис.5);  функція F обмежена знизу, але необмежена зверху на множині M (у цьому випадку ЗЛП на знаходження найменшого значення має розв’язок, а на знаходження найбільшого – ні) (рис.6).

Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем. Властивість 1. (Теорема 1.) Множина всіх планів задачі лінійного програмування опукла. Властивість 2. (Теорема 2.) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин многогранника розв’язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-який точці, що є лінійною комбінацією таких вершин.

Властивість 3. (Теорема 3.) Якщо відомо, що система векторів (k n) у розкладі Властивість 3. (Теорема 3.) Якщо відомо, що система векторів (k n) у розкладі , лінійно незалежна і така, що , де всі , то точка є кутовою точкою багатогранника розв’язків. Властивість 4. (Теорема 4.) Якщо – кутова точка багатогранника розв’язків, то вектори в розкладі , , що відповідають додатнім є лінійно незалежними.

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

Приклад 1. Розглянемо графічний метод розв’язування задачі про фарби, математична модель якої має вигляд (див. п. 1.3): Послідовність дій:  Будуємо прямі обмежень. Спочатку замінюємо знаки нерівностей на знаки точних рівностей. Для побудови прямих зручно скористатись рівнянням – прямої у відрізках на координатних осях. Далі нумеруємо, а потім і будуємо прямі .

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

 Враховуємо, що многокутник розв’язків обов’язково лежатиме у I-й чверті, оскільки  Враховуємо, що многокутник розв’язків обов’язково лежатиме у I-й чверті, оскільки  Визначаємо область допустимих розв’язків (ОДР або многокутник розвязків) як частину площини, яка належить одночасно всім дозволеним областям та виділяємо її.

 Будуємо цільову пряму  Будуємо цільову пряму де, наприклад, С= У нашому прикладі тому: цільова пряма за : (рис.8).

 Будуємо вектор-градієнт:  Будуємо вектор-градієнт: з початком в точці У нашому прикладі  Шукаємо максимум цільової функції, переміщаючи пряму у напрямі вектора , при пошуку мінімуму – у напрямі, протилежному до напряму вектора . Остання по ходу руху вершина многокутника буде відповідно точкою максимуму або мінімуму. Якщо точки не існує, то йде мова про необмеженість планів ЗЛП.

У нашому прикладі точка Е буде останньою вершиною багатокутника допустимих розв’язків через яку проходить цільова пряма рухаючись у напрямі вектора . У нашому прикладі точка Е буде останньою вершиною багатокутника допустимих розв’язків через яку проходить цільова пряма рухаючись у напрямі вектора . Отже, це точка максимуму цільової функції.  Визначаємо координати точки, в якій функція досягає свого оптимуму . Для цього розв’язуємо систему рівнянь прямих, на перетині яких знаходиться дана точка. У нашому прикладі точка Е знаходиться на перетині прямих (1) та (2):  Знайти максимальне та (або) мінімальне значення цільової функції:

У нашому прикладі максимальне значення цільової функції: У нашому прикладі максимальне значення цільової функції: Висновок: Найкращим режимом роботи фабрики є добове виробництво фарби для зовнішніх робіт (Ф1) в об’ємі т і фарби для внутрішніх робіт (Ф2) в об’ємі т. При цьому дохід від продажу становитиме тисяч гривень за добу.