Тема 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шан, Метро, Сільпо, Вопак.

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

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

Тема 13. Задача про рюкзак

Задача про рюкзак

Існує п предметів, кожний з яких важить a[i] і коштує c[i] (i = 1, 2 , ..., п). Потрібно завантажити рюкзак так, щоб сумарна вартість вкладених у нього предметів була максимальною, а вага рюкзака при цьому не перевищувала задане значення A.

Нехай x[1], x[2], … x[n] - змінні, які мають такий зміст:

x[i] = 1 , якщо і-й предмет завантажується;

x[i] = 0, якщо і-й предмет не завантажується

Математична модель задачі полягає у тому, щоб знайти такий набір значень змінних x[1], x[2], … x[n], який задовольняв би умови:

x[i] = 1 або x[i] = 0 для i = 1, 2 , ..., п

a[1]*x[1] + a[2]*x[2] + … + a[n]*x[n] <=A

при яких функція L = c[1]*x[1] + c[2]*x[2] + … + c[n]*x[n]  набуває максимального значення.

Завдання

Зібравшись на осінній рейд, пластун складає рюкзак з 6 продуктів таким чином:

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

            Створити математичну модель такої задачі.

Тема 12. Задача про складання харчового раціону

Задача про складання харчового раціону

Сільськогосподарське підприємство виробляє корми для відгодівлі худоби. Нехай є два види кормів Р1 і Р2. При відгодівлі кожна тварина має отримувати на добу не менше 9 одиниць корисної речовини С1, не менше 8 оди­ниць сировини С2 і не менше 12 одиниць сировини С3. Вміст кількості одиниць корисних речовин в 1 кг кожного виду кор­мів наведено у таблиці:

Корисна речовина	Корм Р1	Корм Р2
С1 С2 С3	3 1 1	1 2 6

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

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

              3*x1 + x2 >= 9

              x1 +2*x2 >= 8

              x1 + 6*x2 >= 12

Якщо відомо, що 1 кг корму P1 коштує 4 грн., а 1 кг корму P2 - 6 грн., то загальну вартість раціону можна представити у вигляді такої лінійної функції:

              L = 4*x1 + 6*x2

Сформульована задача зводиться до наступного: вибрати такі невід'ємні значення змінних x1 та x2, які задовольняють систему обмежень і дають мінімальне значення L.

Завдання

Кожного дня школяр повинен отримувати вітаміни A, групи В та D, які містяться в таких продуктах: молоці, яєчних жовтках, риб'ячому жирі, печінці, м'ясі. Задана таблиця вмісту цих вітамінів в одиниці кожного продукту (наприклад, в 100г печінки):

Школяр повинен отримувати на день не менше 1 мг вітаміну А, 220 вітамінів групи В, 3 мг вітаміну D.

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

Ціни на продукти задати самостійно.

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

Тема 11. Основи лінійного програмування

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

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

Розглянемо деякі математичні поняття.

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

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

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

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

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

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

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

Задача про використання сировини

Нехай деяке підприємство виробляє два види продукції Р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 набуде максимального значення (щоб отримати найбільший прибуток).

Завдання

1. Задано

Види сировини	Запаси сировини	Кількість одиниць сировини для виготовлення одиниці продукції
		Р1	Р2	Р3
С1 С2 С3	50 70 100	2 4 6	3 5 8	7 7 7

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

Скільки потрібно виробити продукції Р1, Р2 і Р3 для отримання максимального при­бутку.

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