Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Одесская национальная академия пищевых технологий

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

МУ_ЛР ЕММ.docx

Скачиваний:

Добавлен:

09.02.2016

Размер:

1.74 Mб

Скачать

☆

<<< < Предыдущая 12 / 52 3 4 5 > Следующая >>>

Лабораторна робота № 2

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

Мета роботи: побудова математичних моделей задач лінійного програмування та рішення їх графічним методом

Теоретична частина

Завдання лінійного програмування (ЗЛП) в загальному вигляді записують таким чином:

f=(4)

(i=) (5)

Функцію f називають цільовою функцією. Вирази (5) є системою лінійних обмежень ЗЛП. У завданні потрібно визначити такі значення змінних ,,,….,.,, які задовольняють лінійним обмеженням (5) і за цією умовою оптимізують (мінімізують або максимізують) цільову функцію (4). Кожен набір значень змінних, який задовольняє системі (5), називають допустимим рішенням або планом ЗЛП. Безліч всіх допустимих рішень називають областю допустимих рішень (ОДР).

Допустиме рішення, що оптимізує цільову функцію, називають оптимальним рішенням або оптимальним планом.

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

Геометричне рішення розбивають на два етапи. Спочатку будують ОДР завдання, як геометричне місце точок (,), що задовольняють всім обмеженням. Потім будують лінії рівня цільової функції, тобто прямі

і геометрично відшукують лінію рівня, відповідну оптимальному значенню параметра а. Всі точки ОДР, через які проходить така лінія рівня, відповідають оптимальному плану ЗЛП.

Канонічний вигляд ЗЛП :

(6)

Будь-яку ЗЛП можна привести до канонічного вигляду.

Розглянемо приклад задачі, побудуємо математичну модель та розв’яжемо її графічним методом.

Задача. Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає дві моделі збірних книжкових полиць А та В. Полиці обох моделей обробляються на верстатах 1 і 2. Тривалість обробки (у хвилинах) однієї полиці моделі А на верстатах 1 і 2 – 30 і 12 хв., а моделі В відповідно 15 і 26 хв. Час роботи верстатів 1 і 2 становить відповідно 40 і 36 год на тиждень. Прибуток фірми від реалізації однієї полиці моделі А дорівнює 50 у.о., а моделі В – 30 у.о. Вивчення ринку збуту показало, що тижневий попит на полиці моделі А ніколи не перевищує попиту на моделі В більше, як на 30 одиниць, а попит на полиці моделі В не перевищує 80 одиниць на тиждень.

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

Побудова математичної моделі. Нехай x1 – кількість полиць моделі А, що виготовляється фірмою за тиждень, а x2 – відповідна кількість полиць моделі В. Цільова функція моделі – максимізація прибутку фірми від реалізації продукції. Математично вона записується так:

Z = 50x₁+ 30x₂ max

Обмеження математичної моделі враховують час роботи верстатів

1 і 2 для обробки продукції та попит на полиці різних моделей.

Обмеження на час роботи верстатів 1 і 2 набувають такого вигляду: для верстата 1

для верстата 2

Обмеження на попит набувають вигляду:

Отже, економіко-математична модель поставленої задачі має вигляд

Розв’язання. Замінимо знаки нерівностей на знаки рівностей і

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

– не задовольняють. Щоб визначити необхідну півплощину (на рис. 1 її напрям позначено стрілкою), потрібно взяти будь-яку точку та перевірити, чи задовольняють її координати зазначене обмеження. Якщо задовольняють, то півплощина, в якій міститься вибрана точка, є геометричним зображенням нерівності. У протилежному випадку таким зображенням є інша півплощина. Умова невід’ємності змінних x₁ 0, x₂ 0 обмежує область допустимих планів задачі першим квадрантом системи координат. Перетин усіх півплощин визначає область допустимих планів задачі – шестикутник OABCDE.

рис.2.1

Поставлену задачу буде розв’язано, якщо ми відшукаємо таку вершину багатокутника OABCDE, в якій цільова функція Z набуває найбільшого значення.

Для цього будуємо вектор . Він задає напрям збільшення значень цільової функції Z, а вектор, протилежний йому, – напрям її зменшення.

Побудуємо лінію, що відповідає, наприклад, значенню Z = 0. Це буде пряма 50x₁+ 30x₂= 0, яка перпендикулярна до вектора і проходить через початок координат. Оскільки маємо визначити найбільше значення цільової функції, то пересуваємо пряму 50x₁+ 30x₂= 0 в напряму вектора доти, доки не визначимо вершину багатокутника, яка відповідає оптимальному плану задачі. Останньою спільною точкою цієї прямої та багатокутника OABCDE є точка C. Координати цієї точки визначають оптимальний план задачі.

Координати точки С визначаються перетином прямих

^Ро^зв’^я^з^а^вши^цю^с^и^с^тем^у^,^д^і^с^тан^е^мо^x₁⁼⁵⁰^,^x₂⁼⁶⁰^.^Отж^е^,^X⁼⁽⁵⁰^;⁶⁰⁾^;

Це означає, що коли фірма щотижня виготовлятиме 50 збірних книжкових полиць моделі А та 60 – моделі В, то вона отримає максимальний прибуток в 4300 у.о. При цьому тижневий фонд роботи верстатів 1 і 2 буде використано повністю.

Практична частина

1. Сформулювати економіко-математичну модель задачі згідно з визначеним варіантом:

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

Ресурс	Норма витрат на одиницю продукції за видами					Запас ресурсу
Ресурс	A	B	C	D		Запас ресурсу
1	2	1	1	3	300
2	1	–	2	1	70
3	1	2	1	–	340
Ціна продукції	8	3	2	1

Задача 2. Фірма виготовляє деякий препарат побутової хімії. Продукція фірми, що надходить на споживчий ринок, має відповідати певним вимогам, які характеризуються трьома показниками: очищувальні й дезинфікувальні властивості, а також подразнювальний вплив на шкіру людини. Кожний із цих показників вимірюється за лінійною шкалою від 0 до 100 од. Кінцевий продукт виробництва утворюється як суміш основних компонентів A, B, C, характеристики яких наведено в таблиці, і повинні мати не менше, ніж 60 од. очищувальних властивостей і принаймні 60 од. дезинфікувальних.

Компонент	Очищувальні властивості	Дезинфікувальні властивості	Подразнювальний вплив на шкіру
A	90	30	70
B	65	85	50
C	45	70	10

Задача 3. Підприємство випускає r видів хімічної продукції в обсягах D1, D2, … Dr одиниць, кожна з яких є сумішшю кількох компонентів. Припустимо, що таких компонентів є n і запаси вихідної сировини відповідно дорівнюють A1, A2, …, An одиниць. Необхідно так виготовити суміші, щоб прибуток від реалізації продукції був найбільшим.

Задача 4. Грошові кошти фірми можуть використовуватися для фінансування двох проектів. Проект А гарантує отримання через рік прибутку в розмірі 60 центів на кожний вкладений долар. Проект В гарантує отримання прибутку в розмірі 2 дол. на кожний інвестований долар, але через два роки. При фінансуванні проекту В період інвестиції має бути кратним двом рокам. Визначити, як потрібно розпорядитися капіталом у сумі 100000 дол., щоб максимізувати загальний прибуток, який можна отримати через три роки після початку інвестицій.

Задача 5. На трьох складах (І, ІІ, ІІІ) знаходиться відповідно 90, 70, 50 тонн борошна, яке необхідно перевезти в магазини (1, 2, 3, 4) відповідно в кількості 80, 60, 40, 30 тонн. Вартість перевезення 1 тонни борошна в магазини 1, 2, 3, 4 зі складу І дорівнює відповідно 2, 1, 3, 2 гривні, зі складу ІІ – 2, 3, 3, 1 гривня, зі складу ІІІ – 3, 3, 2, 5 гривень. Скласти економіко-математичну модель задачі.

Задача 6. Комерційна фірма рекламує свою продукцію,

використовуючи місцеві радіо- та телевізійну мережі. Витрати на рекламу в бюджеті фірми становлять 10000 дол. на місяць. Хвилина радіореклами коштує фірмі 5 дол., а телереклами – 90 дол. Фірма має намір використовувати радіорекламу принаймні вдвічі частіше, ніж рекламу на телебаченні. Досвід показав: обсяг збуту, що його забезпечує 1 хв. телереклами, у 30 разів перевищує обсяг збуту, що його забезпечує 1 хв. радіореклами. Визначити оптимальний розподіл коштів, які щомісяця мають витрачатися на рекламу, за яким обсяг збуту продукції фірми буде найбільшим.

Задача 7. Підприємство виготовляє письмові столи типів А і В. Для одного столу типу А необхідно 2 м²деревини, а для стола типу В – 3 м². Підприємство може отримати до 1200 м²деревини за тиждень. Для виготовлення одного стола типу А потрібно 12 хв. роботи обладнання, а для моделі В – 30 хв. Обладнання може використовуватися 80 год. на тиждень. Відомо, що за тиждень може бути реалізовано до 550 столів. Відомо також, що прибуток від реалізації одного письмового столу типу А становить 30 дол., а типу В – 40 дол. Скільки столів кожного типу необхідно виготовляти за тиждень?

Задача 8. Підприємство електронної промисловості виготовляє дві моделі радіоприймачів, причому кожна модель складається на окремій технологічній лінії. Добовий обсяг виробництва першої лінії становить 60, а другої – 70 од. На один радіоприймач першої моделі витрачається 10 однотипних елементів електронних схем, а на радіоприймач другої моделі – 8. Максимальний добовий запас елементів, що використовуються у виробництві, становить 1000 од. Прибуток від реалізації одного радіоприймача першої та другої моделі дорівнює відповідно 35 та 25 дол. Визначити оптимальні обсяги виробництва радіоприймачів обох моделей. Записати економіко-математичну модель задачі та розв’язати її графічно.

2. Графічним методом визначити оптимальні плани задач лінійного програмування згідно з визначеним варіантом:

Задача1.Задача2.