Самостійна робота №8

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

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

 

Завдання для самостійного розв’язання

Задача 1. Вирішити графічним методом задачу лінійного програмування: необхідно знайти максимум функції F=Х₁+3Х₂ при обмеженнях:

X₁+4X₂≥4;

X₁+X₂≤6;

X₁≥2;

X₂≥0

 

Задача 2. Вирішити графічним методом задачу лінійного програмування: необхідно знайти мінімум функції F=5Х₁+6Х₂ при обмеженнях:

2X₁+X₂≥6;

2X₁+4X₂≥12;

4X₁≥4;

X₂≥0

 

Задача 3. Для перевезення вантажів фірма має можливість найняти не більше 19 тритонних машин і не більше 17 п’ятитонних. Вартість тритонної вантажівки 4 тис. грн., п’ятитонної – 5 тис. грн.  Фірма виділяє 141 тис. грн.. Скільки яких вантажівок потрібно найняти, щоб їх сумарна вантажопідйомність була найбільшою?

 

Задача 4. Для виготовлення двох видів виробів А1 та А2 завод використовує в якості сировини алюміній і мідь. На виготовлення виробів заняті токарні та фрезерні станки. Вихідні дані задачі приведені в таблиці.

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

Види ресурсів	Запас ресурсів	Норми витрат на 1 виріб
		Виріб А1	Виріб А2
Алюміній (кг)	19	2	3
Мідь (кг)	13	2	1
Токарні верстати (верстат.-год)	15	0	3
Фрезерні верстати (верстат.-год)	18	3	0
Прибуток на 1 виріб (тис.грн.)		7	5

 

Задача 5. Розв’язати графічним методом задачу планування стану рухомого складу депо.

З пункту А в пункт Б щоденно відправляються пасажирські і швидкі поїзди. Дані про організацію перевезень в таблиці:

Поїзд	Кількість вагонів
	Багажний	Поштовий	Плацкарт	Купейний	М’який
Швидкий	1	1	5	6	3
Пасажирський	1	-	8	4	1
Число пасажирів в вагоні	-	-	58	40	32
Парк вагонів	12	8	81	70	26

Скільки повинно бути сформовано швидких і пасажирських поїздів, щоб перевезти максимальну кількість пасажирів?

 

Задача 6. (завдання про сумішах). Стандартом передбачено, що октанове число автомобільного бензину Л-76 має бути не нижче 76, а вміст сірки в ньому - не більше 0,3%. Для виготовлення такого бензину на заводі використовується суміш з чотирьох компонентів. Дані про ресурси  компонентів, їх собівартості і їх октанове число, а також про вміст сірки наведені в таблиці:

Характеристика	Компонент автомобільного бензину
	№ 1	№2	№3	№ 4
Октанове число	68	72	80	90
Вміст сірки %	0,35	0,35	0,3	0,2
Ресурси, т	700	600	500	300
Собівартість,  од. / т	40	45	60	90

Потрібно визначити, скільки тонн кожного компонента слід використовувати для отримання 1000 т автомобільного бензину А-76, щоб його собівартість була мінімальною. Для автоматизації розрахунків можна використовувати надбудову Пошук рішення MS Excel.

 

Задача 7 (задача про оптимальне використання обмежених ресурсів).

На ділянку споруджуваної дороги необхідно вивезти 20000 м ³кам'яних матеріалів. У районі будівництва є три кар'єра із запасами 8000 м ³, 9000 м ³ і 10 000 м ^3. Для навантаження матеріалів використовуються екскаватори, що мають продуктивність 250 м ³ в зміну в кар'єрах 1, 2 і 500 м ³ в зміну в кар'єрі 3.

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

Транспортні витрати на перевезення матеріалів характеризуються такими показниками: на перевезення 1000 м ³матеріалів з кар'єру 1 потрібно 1000 автомобілі-змін, з кар'єру 2 - 1350 автомобілі-змін, з кар'єру 3 - 1700 автомобілі-змін.

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

 

Задача 8. Нехай А1, А2, А3 – 3 постачальники сировини для виробництва, В1, В2, В3 – підприємства - споживачі. В таблиці задана ціна перевезення сировини від кожного постачальника до кожного підприємства. Крім того, задано запаси сировини для кожного з постачальників і потреби підприємств-виробників.

Визначити оптимальний план перевезень сировини для кожного підприємства Х₁₁, Х₁₂, Х₁₃, Х₂₁, Х₂₂, Х₂₃, Х₃₁, Х₂₃, Х₃₃  з мінімізацією затрат перевезень, де Хij – об’єм сировини, що необхідно доставити від  i-го постачальника j-му споживачу.

 

Задача 9. Телекомунікаційна компанія надає два основні види послуг: підключення користувачів по безлімітному плану в Internet і хостинг веб-сайтів.

Для організації доступу в Internet компанія купує трафік:

- вхідний з пропускною спроможністю виділеної лінії - до 10 Гбіт/с за ціною 0,02 долар за 1 Мбіт/с;

- вихідний трафік, з максимальним об'ємом 15 Гбіт/с за ціною 0,01 долара за 1 Мбіт/с.

Для надання послуги хостингу одного сайту необхідно зарезервувати 15 Мбіт/с на передачу і 20 Мбіт/с на прийом. Місячний дохід від послуги складає 5,5 доларів.

Для надання послуги доступу в Internet необхідно зарезервувати 30 Мбіт/с на прийом і 10 Мбіт/с на передачу. Місячний дохід від послуги складає 7,5 доларів.

Визначити, при якій кількості супроводжуваних сайтів і кількості користувачів Internet компанія отримає максимальний дохід, якщо кількість портів на сервері віддаленого доступу обмежена, що не дозволяє надавати послуги доступу в Internet більше 480 клієнтам, і загальна кількість клієнтів (доступ в Internet і хостинг) не може перевищувати 512.

 

Задача 10. Знайти оптимальне рішення задачі: максимум функції F=11Х₁+5Х₂+4Х₃  при обмеженнях:

3X₁+2X₂+8 Х₃≤11;

2X₁+ Х₃≤5;

3X₁+3Х₂+ Х₃≤13;

X₁≥0, X₂≥0, Х₃≥0,

 

Приклад розв’язання

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

Ресурс	Запас	Норми витрат
		Продукція №1	Продукція №2
Деталь 1	21 шт	1	3
Деталь 2	21 шт	3	2
Затрати часу	18 год	3	1
Кількість од. продукції		Х1	Х2
Прибуток		30 грн	60 грн

Складемо відповідну математичну модель:

,

,

, .

Вирішимо ЗЛП графічним методом:

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

Етап 1. Визначимо множину рішень першої нерівності. Побудуємо пряму  по двох точках (0; 7) і (21; 0), (по черзі підставимо х₁=0, х₂=0) . На рис. 1 позначимо її цифрою I. Пряма ділить простір на дві півплощини, яка з них є шуканою, можна з'ясувати за допомогою однієї контрольної точки. Якщо в довільно взятій точці, що не належить прямій, нерівність виконується, то вона виконується і у всіх точках тієї півплощині, якій належить контрольна точка. В якості такої точки зручно брати початок координат.

Аналогічним чином побудуємо області рішення двох інших нерівностей.

,  (пряма II);

,   ( пряма III);

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

Етап 2. Прирівняємо цільову функцію до постійної величини а: . Це рівняння є множиною точок, в якому цільова функція приймає значення, рівне а. Міняючи значення а, отримаємо сімейство паралельних прямих, кожна з яких називається лінією рівня. Нехай а = 0 проведемо лінію рівня  (пунктирна пряма на рис. 1)

Для визначення напрямку руху до оптимуму побудуємо вектор-градієнт, координати якого є частковими похідними функції , тобто . Щоб побудувати цей вектор, потрібно з'єднати точку (30; 60) з початком координат. При максимізації цільової функції необхідно рухатися в напрямку вектора-градієнта, а при мінімізації - у протилежному напрямку. Для зручності можна будувати вектор, пропорційний вектору. Так, на рис.1 зображений вектор.

Рис. 1. Рішення ЗЛП графічним методом

Етап 3. У нашому випадку рух лінії рівня (геометрично вона перпендикулярна вектору-градієнту) будемо здійснювати до її перетину з точкою В, далі вона виходить з області припустимих рішень. Отже, саме в цій точці досягається максимум цільової функції. Точка В отримується на пертині І і ІІ ліній, її координати знаходять з вирішення системи рівнянь цих ліній В(3;6). Підставивши ці координати в рівняння цільової функції маємо (грн).

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

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

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

Умови постановки лінійних задач дозволяють легко автоматизувати процес їх розв’язання. В пакеті програм Exсel існує ряд таких можливостей.

Засоби «Пошук розв’язку» та «Підбір параметра»

Рис. 2. Підбір параметра

 

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

ü     В полі Set сеll (Встановити в комірці) водиться необхідна формула, що містить посилання на комірку.

ü     Заданий результат вводиться в полі To value (Значення). 

ü     В полі changing сеll (Змінюючи значення комірки) вводять посилання на комірку, що  буде містити  підібране значення.

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

Задачу пошуку параметра за граничних умов, що накладаються, допоможе вирішити спеціальна надбудова Microsoft Excel Solver (Пошук рішення).

Пошук рішення.

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

В діалоговому вікні Solver (Пошук рішення) так само, як і в діалоговому вікні Goal Seek (Підбір параметра), необхідно вказати цільову комірку, її значення і комірки, які слід змінювати для досягнення мети. Для вирішення задач оптимізації цільову комірку слід вказати рівною максимальному або мінімальному значенню.

Якщо натиснути на кнопку Guess (Припустити), Excel сам спробує знайти всі комірки,  що впливають  на формулу.

Можна додати граничні умови, за допомогою клавіші Add (Додати).

Натиснувши кнопку Options (Параметри), можна змінити умови пошуку рішення: максимальний час пошуку рішення, кількість ітерацій, точність рішення, допуск на відхилення від оптимального рішення, метод екстраполяції (лінійна або квадратична), алгоритм оптимізації і т.д.

Надбудова Microsoft Excel Solver (Пошук рішення) дозволяє, також, вирішувати системи рівнянь або нерівностей. Розглянемо простий приклад: спробуємо вирішити завдання оптимізації плану випуску продукції. Для виготовлення 4 типів продукції використовують три види ресурсів. Запаси ресурсів, норми їх витрати і прибуток від реалізації кожного продукту наведені в таблиці 1. Визначити оптимальну кількість кожного виду продукції, що необхідно випускати для отримання максимального прибутку.

Таблиця 1

 

Якщо позначити х1, х2, х3, х4 – кількість продукції кожного виду, то цільова функція максимізації прибутку виглядає: .

При чому накладені обмеження на кількість кожного ресурсу:

;

;

.

ü Введемо в комірки результатів (A1:A4) довільні величини, що лежать в області визначення (початкові значення, наприклад нулі)

ü В комірки B1 та D1:D3 внесемо формули рівнянь цільової функції та обмежень (ліві частини рівнянь).

ü Запустимо Solver (Пошук рішення) з меню Analysis (Аналіз даних).

ü В полі Set Target Cell виберемо комірку, що містить цільову функцію($В$1), в полі By Changing Cells виберемо комірки значень кількості кожного продукту, які нам треба відшукати (А1:А4).

ü В полі Subject to the Constraints додамо обмеження (натиснувши Аdd) ввівши адреси комірок з функціями обмежень (D1:D3) та значення обмежень (запаси ресурсів: 2400, 1200, 3000), а також обмеження на невід’ємність змінних  $A$1:$A$4≥0.

ü Кликнемо на клавіші Solve (Виконати).

Результати пошуку відобразяться в призначених для розв’язку комірках (A1:A4), звіт про результати з'явиться на екрані.

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

 

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

1.  Завдання лінійного програмування.

2.  Допустимий і оптимальний план в завданнях лінійного програмування.

3.  Геометричний метод розв’язання ЗЛП.

4.  Побудова многогранника рішень в ЗЛП.

5.  Особливі випадки (невизначеності) при розв’язанні ЗЛП графічним методом.