Самостійна по ЛП

Запитання по темі “Лінійне програмування”

1.        Що розуміють під терміном «програмування» у назві математичної дисципліни «Математичне програмування»?

2.        Які задачі розв'язує така математична дисципліна, як дослідження операцій?

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

4.        Яке відношення має математичне програмування до теорії прийняття рішень?

5.        На які два типи можна поділити всі задачі математичного програмування? Які їх характерні ознаки?

6.        Які класи задач виділяються окремо у математичному програмуванні?

7.        Як формулюється задача про використання сировини? Чому її можна віднести до задач лінійного програмуваня?

8.        Як формулюється задача про складання харчового раціону? Чому її можна віднести до задач лінійного програмування?

9.        Як формулюється задача про рюкзак? Чому її можна віднести до задач лінійного програмування?

10.     Як формулюється транспортна задача? Чому її можна віднести до задач лінійного програмування?

11.     Як формулюється загальна задача лінійного програмування?

12.     Що називають системою обмежень задачі лінійного програмування?

13.     Що називають цільовою функцією задачі лінійного програмування?

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

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

16.     Сформулюйте алгоритм геометричного розв'язування задачі лінійного програмування від двох параметрів.

17.     Виконайте алгоритм геометричного розв'язування задачі лінійного програмування від двох параметрів на власному прикладі.

18.     Які можливі випадки одержання розв'язку задачі лінійного програмування?

Тема 17. Геометрична інтерпретація розв'язування задач лінійного програмування

Геометрична інтерпретація

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

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

Геометрично систему обмежень цієї задачі, що є системою нерівностей

2*x1 + 5*x2 <= 20

8*x1 + 5*x2 <= 40

5*x1 + 6*x2 <= 30

можна зобразити у вигляді деякої області на декартовій площині:

Оскільки розв'язки задач лінійного програмування завжди знаходяться в області невід'ємних значень, то до обмежень задач лінійного програмування потрібно дописати ще дві нерівності: x1>=0 та x2>=0. На малюнку ці дві нерівності визначають першу чверть системи координат. Координати множини точок, що належать побудованому багатокутнику, є розв'язками цієї системи, а багато­кутник називається областю допустимих розв'язків.

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

Далі для пошуку максимального розв'язку серед усіх допустимих будується опорна пряма (або пряма нульового рівня):

L = 50*x1 + 40*x2 = 0

З цього рівняння видно, що пряма проходить через початок координат. Якщо цільова функція матиме вільний член, то при побудові опорної прямої його можна проігнорувати, адже максимум лінійної функції L = b*x1 + c*x2 +d досягається при тих самих значеннях x1 та x2, що і максимум лінійної функції без вільного члена d. Щоб визначити точку - максимум або мінімум серед допустимих розв'язків, потрібно переміщувати опорну пряму паралельно самій собі в одному з напрямів. При цьому значення L2 буде або збільшуватись, або зменшуватись. Залежно від постановки вихідної задачі (у даній задачі - це пошук максимуму) визначається напрям руху опорної прямої: за вектором напряму у випадку максимізації цільової функції або проти вектора напряму при мінімізації цільової функції. Вектор напряму визначається коефіцієнтами цільової функції:  вектор a(b,c)

Для даної задачі вектор напряму матиме вигляд: вектор а(50,40). Оскільки цільову функцію цієї задачі потрібно дослідити на максимум L = 50*x1 + 40*x2 —> max, то опорну пряму потрібно переміщувати в напрямі, який вказує побудований вектор напряму (на малюнку).

Координати останньої крайньої точки багатокутника допустимих значень, яку перетне опорна лінія на своєму шляху, і будуть тими значеннями, при яких величина L2 набуде максимального значення. Для нашої задачі такою вершиною багатокутника є вершина С. Вона утворюється при перетині прямих 8*x1 + 5*x2 = 40 та 5*x1 + 6*x2 = 30. Для визначення координат цієї вершини потрібно лише розв'язати відповідну систему лінійних рівнянь:

8*x1 + 5*x2  = 40

5*x1 + 6*x2  = 30

і підставити отриманий розв'язок (приблизно x1 =3,9; x2 =1,74) у функцію. У результаті отримаємо такий розв'язок цієї задачі лінійного програмування L2 = 264,6.

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

1.   За умовою задачі записати обмеження та цільову функцію.

2.   Побудувати багатокутник допустимих значень.

3. Побудувати опорну пряму відповідно до скоректо­ваної цільової функції: прибрати вільний член і прирів­няти до 0.

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

5. Визначити точку, в якій цільова функція набуває опти­мального значення, та рівняння прямих, на перетині яких зна­ходиться визначена точка.

6. Розв'язати систему лінійних рівнянь, яку утворюють рівняння визначених прямих. 7. Для отримання шуканого оптимального значення цільової  функції підставити розв'язок системи рівнянь у цільову функцію.

Обов'язково потрібно розглядати такі три можливі випадки одержання розв'язку задачі лінійного програмування:

1) задача має один розв'язок, тобто опорна пряма на останньому кроці перетинає одну точку, яка є вершиною області до­пустимих розв'язків;

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

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

Завдання

1. Розв'язати геометрично задачу про використання сировини для випадку існування одного оптимального розв'язку, ви­користавши власні вхідні дані.

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

3. Розв'язати геометрично задачу про використання сировини для випадку відсутності жодного оптимального розв'язку, використавши власні вхідні дані.

4. Розв'язати геометрично задачу про складання харчового раціону для випадку існування одного оптимального роз­в'язку, використавши власні вхідні дані.

5). Розв'язати геометрично задачу про складання харчового ра­ціону для випадку існування безлічі оптимальних розв'яз­ків, використавши власні вхідні дані.

6. Розв'язати геометрично задачу про складання харчового раціону для випадку відсутності жодного оптимального роз­в'язку, використавши власні вхідні дані.

Тема 16. Загальна задача лінійного програмування

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

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

У кожному з  наведених прикладів задач вхідні дані задовольняють деяку систему обмежень:

a[1,1]*x[1] + a[1,2]*x[2] + ... + a[1,n]*x[n]  <=> b[1]

a[2,1]*x[1] + a[2,2]*x[2] + ... + a[2,n]*x[n]  <=> b[2]

-----------------------------------------------------------------

a[m,1]*x[1] + a[m,2]*x[2] + ... + a[m,n]*x[n]  <=> b[m]

де a[i,j], b[i]  - фіксовані дійсні числа, а символ « <=> » означає один із знаків «<=», «>=», «=». Саме ця система обмежень описує умови, які накладаються на вхідні дані задачі.

Для отримання розв'язку задачі потрібно задати формулу, яка визначає мету досягнення результату (максимальне або мінімальне значення). У загальному випадку її можна представити так:

L = c[1]*x[1] + c[2]*x[2] + ... + c[n]*x[n] 

де c[i] набуває дійсних значень. Наведений вираз називається цільовою функцією.

Рівняння, яке представляє цільову функцію, має безліч розв'язків x[1], x[2], ..., x[n]. Однак серед них потрібно вибрати тільки ті, які задовольняють систему обмежень даної задачі. Але і таких розв'язків є багато, оскільки система обмежень має невідомих більше, ніж нерівностей ( n > m ). Сукупність таких невід'ємних розв'язків, які задовольняють систему обмежень, називається допустимими розв'язками або планами даної задачі.

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

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

Тема 15. Пошук рішень в Excel

Пошук рішень в Excel

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

Нехай деяке підприємство виробляє два види продукції Р1 і Р2. Для випуску цих видів продукції необхідно використати три види сировини С1, С2 і С3. Відомо, яка кількість кожної сировини витрачається для виробництва продукції Р1 і Р2 відповідно. Також відома інформація про наявність усіх видів сировини на складі.

Види сировини	Запаси сировини	Кількість одиниць сировини для виготовлення одиниці продукції
		Р1	Р2
С1 С2 С3	20 40 30	2 8 5	5 5 6

Прибуток від реалізації одиниці продукції Р1 становить 50 грн., а продукції Р2 - 40 грн.

Шукатимемо розв'язок такої задачі: скільки потрібно виробити продукції Р1 і Р2 для отримання максимального при­бутку.

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

2* х1 + 5* х2 <= 20

8* х1 + 5* х2 <= 40

5* х1 + 6* х2 <= 30

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

За умовою задачі прибуток підприємства складається з при­бутку від реалізації х1 одиниць продукції Р1 (50 грн. за кожну) та х2 одиниць продукції Р2 (40 грн. за кожну). Сумарний прибу­ток розраховуватиметься за формулою:

L = 50*х1 + 40*х2

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

Задамо всі дані в Excel:

У комірках А12, А13, А14 і D12 будуть відображатись 0, бо у комірках C9 i D9 записані 0.

Задамо команду Сервіс/Пошук рішень (якщо такої команди немає, то у  Сервіс/Настройки встановити відповідний прапорець).

·         Виберемо функцію у комірці D12, шукатимемо її максимум,

·         шукані величини - це діапазон C9:D9,

·         задамо обмеження : діапазон C9:D9 >= 0, діапазон C9:D9 - цілі числа, діапазон A12:A14 <= B12:B14.

Нові значення ми отримаємо в комірках C9 i D9 - це кількості одиниць продукції, в D12 отримаємо максимальний прибуток, в А12, А13, А14 - отримаємо кількості витраченої сировини на продукції Р1 та Р2 (порівняємо їх із запасами сировини - В12, В13, В14).

Відео-урок для розв'язання задачі лінійного програмування:

                  https://www.youtube.com/watch?v=Xmo-M6a4wWI

Тема 14. Транспортна задача

Транспортна задача

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

Нехай у місті є два продовольчі склади і дві пекарні. Потрібно щоденно з першого складу вивозити 50 т борошна, а з другого - 70 т. Перша пекарня при цьому отримує 40 т, а друга - 80 т борошна.

Вартість перевезення борошна зі складів до пекарень у гривнях за тонну подана в таблиці:

	1 пекарня	2 пекарня
1 склад 2 склад	1,2 0,8	1,6 1,0

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

Позначимо m[i,j] — кількість борошна, яка перевозиться зі складу і на пекарню j. Запишемо математичну модель транспортної за­дачі.

Система обмежень буде такою:

m[1,1] + m[1,2] = 50

m[2,1] + m[2,2] = 70

m[1,1] + m[2,1] = 40

m[1,2] + m[2,2] = 80

Перші два рядки системи обмежень визначають кількість борошна, що виво­зиться зі складів на пекарні, а другі два - кількість борошна, яка ввозиться на пекарні зі складів.

Оскільки нам відома вартість кожного з перевезень, то за­гальна сума вартості визначатиметься за формулою:

L=1,2*m[1,1] + 1,6*m[1,2] + 0,8*m[2,1] + m[2,2]

Отже, розв'язок транспортної задачі полягає у відшуканні таких невід'ємних значень m[i,j], які задовольняють систему об­межень, a функція L набуває мінімального значення.

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

Завдання

Фабрики Світоч, Roshen та АВК виробляють солодощі та перевозять їх у супермаркети: Aшан, Метро, Сільпо, Вопак.

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

Створити математичну модель цієї транспортної задачі.