Лекція 7. Задачі лінійного програмування

Із рисунка 11 видно, що це вершина .

Висновок.

Мінімальні витрати на перевезення хліба складають 164 грошових одиниці. Оптимальний план матимемо у випадку коли:

1)із заводу №1 у 1-ий район доставляється 26 тонн, в 2-ий – 4 тонни, а в 3-ій доставок завод не здійснює.

2)із заводу №2 у 1-ий район доставок завод не здійснює, в 2-ий – 10 тонн, а в 3-ій – 20 тонн.

Задача про раціон

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

Нехай маємо два обов’язкових продукти харчування, наприклад, хліб і м’ясо, які містять два елементи харчування, наприклад, калорії і протеїн. Вагова одиниця хліба містить 1 од. протеїну і 5 од. калорій, а вагова одиниця м’яса містить 5од. протеїну і 1 од. калорій. Щоденна потреба організму складає мінімум 15 од. калорій і мінімум 15 од. протеїну.

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

Розв’язання.

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

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

Висновок. Отже, найдешевший раціон повинен складатися із вагових одиниць хліба і стільки ж м’яса.

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

Вироби Цех

1234

I4302

II2640

Максимальний час роботи цеху16301612

Цехам нараховується прибуток: 150 грн від реалізації одного столу першого виду і 200 грн від реалізації одного столу другого виду.

Розв’язання. Позначимо через число виробів I виду, а через – число виробів II виду.

Область допустимих значень змінних

Тоді, в першому цеху на виготовлення виробів I виду затрата часу становить 4 год. і 2 год. на виготовлення виробів II виду, тобто всього 4 + 2 год. Оскільки час роботи першого цеху не має перевищувати 16 год., то .

В другому цеху на виготовлення виробів I виду затрата часу становить 3 год. і 6 год. на виготовлення виробів II виду, тобто всього 3 + 6 год. Оскільки час роботи цеху не має перевищувати 30 год., то .

В третьому цеху на виготовлення виробів I виду затрата часу становить 0 год. і 4 год. на виготовлення виробів II виду, тобто всього 4 год. Оскільки час роботи цеху не має перевищувати 16 год., то .

В четвертому цеху на виготовлення виробів I виду затрата часу становить 2 год. і 0 год. на виготовлення виробів II виду, тобто всього 2 год. Оскільки час роботи цеху не має перевищувати 12 год., то .

Складемо цільову функцію, яка забезпечувала б максимальний прибуток фірми. Від реалізації столів I виду фірмі нараховується 150 грн. прибутку і від реалізації столів II виду – 200 грн. прибутку. Загальний прибуток становить грн.

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

На множині розв’язків системи нерівностей потрібно знайти найбільше значення лінійної функції .

Побудувавши в системі координат прямі , , , , дістанемо замкнений многокутник розв’зків системи нерівностей (див.рис.12). 

 Рис.12

Знайдемо координати вершин цього многокутника:

 Підставивши координати вершин у вираз лінійної функції, дістанемо:

 У точці лінійна функція досягає свого максимуму: .

Відповідь. Найбільший прибуток 1100 грн. фірма отримає, коли виготовлятиме 2 столи першого виду і 4 столи другого виду. 

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

Витрати на один виріб

Ресурси

АВ

МатеріалиСталь (кг.)1070320

Кол. метали2050420

Обладнання

Токарні станки

(станко-годинни)300400620

Фрезерні станки

(станко-години)2004003400

Прибуток за виріб (тис. грн.)38

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

Розв’язання.

Побудуємо математичну модель задачі. Позначимо через х число виробів виду А, а через у – виду В. 

На виготовлення продукції піде

10х + 70у ≤ 320 кг сталі і 20х + 50у ≤ 420 кг кольорових металів. Час роботи на токарних верстатах зображується нерівністю 300х + 400у ≤ 6200, а на фрезерних верстатах – рівнянням 200х + 100у = 3400, так як час роботи на фрезерних верстатах використовується повністю.

 Отже, система обмеження цієї задачі така або

Весь прибуток може бути виражений функцією F = 3х + 8у.

Самостійно знайти множину точок площини, координати яких задовольняють систему обмеження та переконатися, що розв'язок буде оптимальним планом: Fmax = 3 × 16 + 8 × 2 = 64.

Задача. Фірма випускає дитячі і спортивні велосипеди. Щомісячно цех здатен зібрати не більше 600 дитячих і не більше 300 спортивних велосипедів. Якість кожного велосипеда перевіряють на двох стендах А і В. Кожний дитячий велосипед перевіряють 0,3 години на стенді А і 0,1 години на стенді В, а кожний спортивний велосипед перевіряється 0,4 години на стенді А і 0,3 години на стенді В. По технологічним причинам стенд А не може працювати більше 240 годин на місяць, а стенд В – більше 120 годин на місяць. Реалізація кожного дитячого велосипеда приносить фірмі 50 грн., а кожного спортивного – 90 грн. Скільки дитячих і скільки спортивних велосипедів повинна випускати фірма, щоб її прибуток був найбільшим?

Розв’язання.

 Створимо математичну модель даної задачі. Нехай x – кількість дитячих велосипедів, які фірма виробляє щомісячно, y – кількість спортивних велосипедів. Тоді за умовою 0 ≤ х ≤ 600, 0 ≤ у ≤ 300. Зайнятість стенду А складає 0,3х+0,4у (год.), що не повинно перевищувати 240 год.

Тому 0,3х + 0,4у ≤ 240.

Аналогічно для стенду В маємо 0,1х + 0,3у ≤ 120. Прибуток фірми складає S=50х+90у (грн.). Маємо систему обмеження:

 Нам потрібно знайти такі цілі значення х і у щоб прибуток S = 50х+90у був найбільшим. На координатній площині нанесемо множину точок, які задовольняють систему обмеження. Всі можливі розв’язки задачі розташовані в середині або на границі многокутника OABCDE. (рис.13)

у

300 В(300;300)

240С(480;240)

150 D(600;150)

0 300 480 Е(600;0)

Рис.2.3.4

  На рисунку ми бачимо що функція S = 50х + 90 у досягає свого найбільшого значення в одній із вершин О, А, В, С, D або Е побудованого многокутника. Тому знайдемо координати вершин і підрахуємо величину прибутку S. Маємо: О(0; 0), А(0; 300), В(300; 300), С(480; 240), D(600; 150), і Е(600; 0).

Знайдемо значення прибутку S в кожній точці.

в точці О (0; 0), S = 50 × 0 + 90 × 0 = 0 (грн.);

в точці А (0; 300), S = 50 × 0 + 90 × 300 = 27000 (грн.);

в точці В (300; 300), S = 50 × 300 + 90 × 300 = 42000 (грн.);

в точці С (480; 240), S = 50 × 480 + 90 × 240 = 45600 (грн.);

в точці D (600; 150), S = 50 × 600 + 90 × 150 = 43500 (грн.);

в точці Е (600; 0), S = 50 × 600 + 90 × 0 = 30000 (грн.).

Висновок:

Найбільший прибуток фірми складає 45600 грн. і досягається в точці С тобто при випуску 480 дитячих велосипедів і 240 – спортивних.