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

запису

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


(2)

(3)

змінних;
b1,2….m – вільні члени (ресурси, запаси).

умови (2) і (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)

помножити на (–1), тобто:

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


(2)

(3)

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

знака суми «Σ»:
за умов
Запис задачі лінійного програмування у векторно-матричному вигляді:

 

зору економіки, а не математики, відповідаємо на такі питання:
①? Що є шуканими величинами задачі?
②? Якою є мета розв’язку? Який параметр задачі є критерієм ефективності (оптимальності) розв’язку? У якому напрямі повинно змінюватись значення цього параметра для досягнення найкращих результатів?
③? Які умови у відношенні шуканих величин і ресурсів задачі повинні бути виконані? Ці умови встановлюють, як повинні співвідноситись один з одним різні параметри задачі.

Шукані величини є змінними задачі, які, як правило, позначають малими латинськими літерами з індексами. Наприклад, однотипні змінні зручно подавати у вигляді
❷? Мета розв’язку записується у вигляді цільової функції. Яку позначають, наприклад . Математична формула цільової функції відображає спосіб розрахунку значень параметра – критерію ефективності задачі.
❸? Умови, які накладаються на змінні і ресурси задачі, записують у вигляді системи рівностей або нерівностей, тобто обмежень. Ліві і праві частини обмежень відображають спосіб одержання (розрахунок або числові значення з умови задачі) значень тих параметрів задачі, на які були накладені відповідні обмеження.
✔ В процесі запису математичної моделі необхідно вказувати одиниці виміру змінних задачі, цільової функції і всіх обмежень.

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

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

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

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

За умовою:

виробництва Ф2:



За умовою:


⇨ обмеження по добовому виробництву фарби другого виду:

За умовою:

два види збірних книжкових полиць – А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в таблиці:



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

двох моделей, що максимізують прибуток фірми.

виготовлених фірмою за тиждень, а х2 – кількість полиць моделі В.

? Цільова функція – максимум прибутку фірми від реалізації продукції. Математично вона подається так:

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

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

х1 – х2 ≤ 30

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

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

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

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

цієї системи


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

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

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

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

до кожної з ліній рівня.

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

вектора в області допустимих розв’язків M здійснити пошук оптимальної точки

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

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

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

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

(k n) у розкладі
, лінійно незалежна і така, що
, де всі , то точка
є кутовою точкою багатогранника розв’язків.

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

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

якої має вигляд (див. п. 1.3):



Послідовність дій:
①? Будуємо прямі обмежень.
Спочатку замінюємо знаки нерівностей на знаки точних рівностей.
Для побудови прямих зручно скористатись рівнянням – прямої у відрізках на координатних осях.
Далі нумеруємо, а потім і будуємо прямі .

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

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

тому:

цільова пряма за : (рис.8).

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




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

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

⑨? Знайти максимальне та (або) мінімальне значення цільової функції:

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