Економічні задачі лінійного програмування і методи їх вирішення
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
? моделі.
3. Вибір методу рішення і рішення задачі.
4. Перевірка отриманого рішення на його адекватність досліджуваного явища і коректування моделі у разі потреби.
5. Реалізація знайденого рішення на практиці.
Зупинимося докладніше на другому етапі.
Математична модель є абстрактним відображенням реального процесу (явища) і в міру своєї абстрактності може його характеризувати більш-менш точно.
У побудові математичної моделі можна виділити наступні моменти:
1. Вибір невідомих величин Х = (х1, ..., хn), впливаючи на які можна змінювати поведінку досліджуваного процесу. Їх називають змінними, керованими параметрами, планом, стратегією.
2. Необхідно виділити мету (максимізація прибутку, мінімізація витрат та інше) функціонування досліджуваного процесу і записати її у вигляді математичної функції від обраних змінних. Така функція називається цільовою (функція мети, критерій оптимальності, критерій якості, показник ефективності) і дозволяє, змінюючи значення керованих параметрів x1, ..., xn, вибрати найкращий варіант з безлічі можливих. Будемо позначати функцію мети Z = f (X).
3. Запис у вигляді математичних співвідношень (рівнянь, нерівностей) умов, що накладаються на змінні. Ці співвідношення називають обмеженнями, вони можуть витікати, наприклад, через обмеженість ресурсів. Сукупність усіх обмежень складає область допустимих рішень (ОДР). Будемо позначати її буквою D (XD) [14].
За таких позначень модель задачі математичного програмування буде мати вид:
Або в розгорнутому виді
знайти план який доставляє екстремальне значення цільової функції Z, тобто
при обмеженнях:
З економічних або фізичних міркувань на деякі компоненти плану завдання, як правило, накладаються умови невідємності:
1.2 ПРИКЛАДИ ЕКОНОМІЧНИХ ЗАДАЧ лінійного програмування
1.2.1 Задача оптимального виробничого планування
Для виготовлення n видів продукції P1, ..., Pn використовується m видів сировини S1, ..., Sm, запаси якого обмежені і становлять відповідно b1, ..., bm одиниць. Відомо, що на виробництво одиниці продукції Pj (j =) витрачається аij одиниць ресурсу Si (i =, а прибуток від реалізації одиниці продукції Pj (j=) становить сj (j =.)
Потрібно визначити план виробництва, який дозволяє при готівкових ресурсах отримати максимальний прибуток підприємства від реалізації продукції [15].
Перш за все, запишемо умови задачі компактно у вигляді таблиці:
Таблиця 1.
Вид продукції
Вид сировиниР1...Pj...PnЗапас
ресурсуS1a11...a1j...a1nb1.....................Siai1...aij...ainbi.....................Smam1...amj...amnbmПрибутокc1…cj…cn
Складемо математичну модель задачі.
Позначимо через xj (j =) плановане до випуску кількість продукції Рj (j=), а через Z (х1, ..., xn) прибуток підприємства від реалізації всієї продукції. Тоді планом виробництва буде вектор Х = (х1, ..., хn), що показує, яку кількість продукції кожного виду буде вироблено. Змінні х1, ..., хn керовані змінні. Мета рішення задачі (критерій оптимальності) максимізувати прибуток:
Z = c1x1 + c2x2 +. . . + cnxn .
Сумарні витрати ресурсу Si (i = складають:
.
У силу обмеженості ресурсу Si величиною bi отримаємо систему обмежень:
.
На змінні хj повинна бути накладена умова невідємності
тобто продукція Рj або може випускатися (xj > 0), або не випускатися (xj = 0).
Отже, математична модель буде мати вид:
,
.
1.2.2 Задача про суміші
Задача визначення оптимального складу суміші виникає тоді, коли з наявних видів сировини шляхом їх змішування необхідно отримати кінцевий продукт із заданими властивостями. До цієї групи завдань відносяться, наприклад, завдання отримання сумішей для різних марок бензину в нафтопереробній промисловості, сумішей для отримання бетону в будівництві, завдання про вибір дієти, складання кормового раціону в тваринництві та інше. При цьому потрібно, щоб вартість такої суміші була мінімальною.
Нехай є m видів сировини, запаси якого становлять відповідно d1, ..., dm. З цієї сировини необхідно скласти суміш, яка містить n речовин, що визначають технічні характеристики суміші. Відомі величини визначають кількість j-ї речовини в одиниці-го виду сировини, ціна якого дорівнює а також найменший допустимий кількість j-ї речовини в суміші.
Потрібно забрати суміш із заданими властивостями при найменших витратах на вихідні сировинні матеріали.
Для складання математичної моделі запишемо умови задачі у вигляді таблиці:
Таблиця 2.
Вид речовини
Вид сировини1...j...n
Обсяг сировини
Ціна
сировини1a11...a1j...a1nd1c1…...............……iai1...aij...aindici…...............……mam1...amj...amndmcm
Мінімальна кількість речовини в суміші
b1
...
bj
...
bn
Позначимо через хi кількість сировини і-го виду, що входить у склад суміші.
Мета завдання (цільова функція) мінімізувати сумарні витрати на сировину:
Система обмежень включає в себе обмеження за технічними характеристиками:
а також обмеження за обсягом сировини, які з урахуванням невідємності будуть мати вид:
Запишемо модель у компактній формі:
при обмеженнях:
1.2.3 Задача про розкрій
Задача оптимального розкрою матеріалів полягає у визначенні найбільш раціонального способу розкрою наявного матеріалу (колоди, сталеві смуги, шкіра і т.д.), при як?/p>