![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
На базі наведеного математичного опису можна проілюструвати суть цієї моделі так: необхідно визначити значення n невід’ємних змінних , які задовольняють обмеженням 2.2та забезпечують екстремальне значення (максимальне або мінімальне) цільової функції, яка виражена рівнянням 2.1.
До методів вирішення задач ЛП відносяться симплекс-метод, графічний метод.
Симплекс-метод є аналітичним методом знаходження рішення задач ЛП.
Як правило, задачу зводять до канонічної форми. Вважають, що задача лінійного програмування записана в канонічній формі, якщо вона має вигляд
(2.3)
Щоб перевести задачу лінійного програмування з загальної форми (2.1–2.2) до канонічної форми (2.3) необхідно зробити такі кроки.
1-й крок. До кожної лівої частини нерівностей (2.2) додаємо нову невід'ємну невідому змінну хп+і (i= 1,2,...,l–k), яка дорівнює:
або:
Тоді група нерівностей(2.2)перетвориться на рівняння.
Введені нові змінні, хп+і,..., хт–k будемо вважати базовими, а змінні
x1,..., хп – вільними.
Дістаємо однорідну систему основних обмежень задачі:
2-й крок полягає у зведенні до однорідної системи обмежень на знак. Умови недодатності легко перетворюються в умови невід'ємності за допомогою заміни змінних
Змінну, на знак якої не накладено обмежень, подають у вигляді різниці двох невід'ємних змінних:
Ранг сумісної системи обмежень (1.3) r можна вважати таким, що дорівнює т, оскільки в іншому разі частину, а саме т – r = k рівнянь треба було б відкинути, бо вони були б лінійними комбінаціями r базових рівнянь. Однак на практиці інколи такі зайві рівняння можуть включати в систему обмежень на стадії формування реальної задачі. Такі обмеження називають неістотними і їх відкидають, що звичайно відбувається при побудові довільного базового розв'язку системи рівнянь. Отже, знайти множину планів задачі – означає знайти множину невід'ємних розв'язків системи лінійних рівнянь.
Означення. Задачу лінійного програмування вважають записаною у канонічній формі, якщо вона задовольняє такі умови:
1. Система обмежень зведена до системи рівнянь виду (2.3).
2. Система рівнянь зображена в такому вигляді, де кожна базова невідома входить тільки в одне рівняння системи з коефіцієнтом рівним одиниці, при чому немає рівнянь, в які не входила хоча б одна базова невідома. Якщо деякі рівняння системи поміняти місцями так, щоб нумерація базових невідомих була строго зростаючою, то базовий мінор в цьому випадку складає одиничну матрицю.
3. Вільні члени системи обмежень невід'ємні;
4. Оптимізуюча форма залежить тільки від вільних невідомих.
Отже, для того, щоб задачу лінійного програмування можна було розв'язувати симплексним методом потрібно загальну форму (2.1–2.2) звести до канонічної форми. Іншими словами її потрібно певним способом записати в такій формі, щоб система рівнянь була з базисом.
(2.4)
(2.5)
Для того, щоби базовий план системи обмежень (2.4)був опорним, необхідно і достатньо, щоб всі вільні члени (2.5) були невід'ємні. Отже, для зведення задачі до канонічної форми потрібно так підібрати базові невідомі, щоб у загальному розв'язку системи обмежень не було від'ємних вільних членів.
Лабораторна робота № 6
«Задача оптимального використання ресурсів»
Задача. Для виготовлення двох видів продукції А1 і А2 використовують три види сировини І, ІІ і ІІІ. Запаси сировини, норми їх витрат і прибуток від реалізації одиниці продукції задано у таблиці.
Знайти розмір максимального прибутку, який можна одержати за наявності даних запасів сировини.
Варіанти асортименту обрати з таблиці 6.1.
Таблиця 6.1
N° | Затрати ресурсів на одиницю продукції | Наявність ресурсів | Прибуток | ||||||||
І | ІІ | ІІІ | |||||||||
А1 | А2 | А1 | А2 | А1 | А2 | І | ІІ | ІІІ | П1 | П2 | |
1. | |||||||||||
2. | |||||||||||
3. | |||||||||||
4. | |||||||||||
5. | |||||||||||
6. | |||||||||||
7. | |||||||||||
8. | |||||||||||
9. | |||||||||||
10. | |||||||||||
11. | |||||||||||
12. | . 80 | ||||||||||
13. | |||||||||||
14. | |||||||||||
15. | |||||||||||
16. | |||||||||||
17. | |||||||||||
18. | |||||||||||
19. | |||||||||||
20. | |||||||||||
21. | |||||||||||
22. | |||||||||||
23. | |||||||||||
24. | |||||||||||
25. | |||||||||||
26. | |||||||||||
27. | |||||||||||
28. | |||||||||||
29. | |||||||||||
30. |
Контрольні запитання
1. Поняття про математичне програмування та лінійне програмування.
2. Загальна модель задачі лінійного програмування.
3. Принципи побудови оптимізаційних моделей.
4. Задачі оптимізації виробничої програми. Цільова функція, обмеження на зміні, умови невід'ємності змінних.
5. Який склад математичної моделі задачі лінійного програмування?
6. Методи знаходження розв’язків задач лінійного програмування.
7. Поясніть принципову суть симплекс-методу.
8. Записати математичну модель загальної задачі лінійного програмування.
9. Сформулювати задачу оптимального використання ресурсів.
10.Що визначає цільова функція в задачах оптимального використання ресурсів?
11.Обмеження на зміни в задачах оптимального використання ресурсів?
12.Умови невід'ємності змінних в задачах оптимального використання ресурсів?
13.Записати економіко-математичну модель задачі оптимального використання ресурсів.
14.Які критерії оптимальності використовуються в економічних моделях?
15.Навести приклад економічної інтерпретації двійчастої задачі.
Література [1, с. 354-358, 400-430; 2, с. 21-32; 3, с.101-107, 141-147; 5, с. 47-97; 6, с. 47-45, 66-79; 7, с. 15-23, 24, 45-54; 9, с. 45-48,59; 13, с. 31-39, 41-47].
Тема 3. МОДЕЛІ ОПТИМАЛЬНОГО ПЛАНУВАННЯ НА РІВНІ ПІДПРИЄМСТВА
Однією з основних задач планування виробництва є розрахунок оптимального плану випуску продукції з урахуванням основних факторів, які впливають на його обсяг.
Вирішення оптимізаційної задачі розподіляється на три етапи: побудування економіко-математичної моделі; находження оптимального рішення задачі; аналіз результатів рішення.
Асортиментні задачі на кондитерських фабриках являють собою групу задач, в яких визначають виробничу програму фабрики з урахуванням впливу на підприємства внутрішніх факторів (можливостей обладнання, лімітів сировини, трудових чинників) та деяких зовнішніх вимог (по товарній продукції в цілому чи окремих її асортиментних груп та видів, середньої ціни асортименту, який випускається).
В задачі оптимізуємо виробничу програму підприємства по критерію максимального прибутку від реалізації продукції; відповідно мова піде про підвищення рентабельності виробництва та зниження собівартості.
Для побудування абстрактної економіко-математичної моделі асортиментної задачі введемо наступні умовні позначення:
j – індекс виду випускаємої продукції;
j = 1, 2,..., n – кількість видів випускаємої продукції;
xj – шукаємий випуск продукції j-того виду;
і – індекс виду ведучого обладнання;
і = 1, 2,..., m – кількість одиниць ведучого обладнання;
аij – зв’язуючий коефіцієнт обмеження по обладнанню, визначаючий норму витрат часу роботи обладнання і -го виду на випуск одиниці продукції
j-го виду;
Аі – потужність обладнання і -го виду за плановий період (рік);
b – собівартість продукції звітного чи планового року;
Bj – питома собівартість j-го виду продукції;
Dj¢, Dj – границя попиту на продукцію j-го виду, відповідно верхній і нижній;
pj – питомий прибуток від реалізації одиниці продукції j-го виду;
Sj – оптово-відпускна ціна одиниці продукції j-го виду (діюча);
S – вартість порівняльної товарної продукції звітного чи планового року.
Цільова функція має наступний вигляд:
При обмеженнях:
1. По ведучому обладнанню:
2. По випуску товарної продукції:
3. По попиту на окремі види продукції:
4. По собівартості продукції:
5. Умова невід’ємності змінних:
xj ³ 0, j = 1, 2,..., n.
Лабораторна робота № 7
«Розрахунок оптимальної виробничої програми карамельного цеху»
Задача. У карамельному цеху випускають декілька видів продукції (табл.7.2). Продуктивність ліній визначається по варочному апарату. Кількість варильних апаратів – 1.
Задано: оптова ціна, собівартість продукції і попит, річна продуктивність апаратів по карамелі.
Потрібно:
1. Розрахувати обсяг ресурсів на свій асортимент (табл. 7.3).
2. Побудувати модель оптимального річного плану підприємства у загальному вигляді по критерію оптимізації – максимальний прибуток.
3. За допомогою отриманих нерівностей чи рівнянь побудувати та записати матрицю коефіцієнтів і функцію цілі.
4. Вирішити задачу за допомогою програми SIMPL.EXE або функції "Поиск решения" табличного процесора Мicrisoft Ехсеl.
5. Заповнити вихідну таблицю та дати економічний аналіз.
Варіанти асортименту обрати з таблиці 7.1.
Таблиця 7.1
Х1 | Х2 | Х3 | Х4 | Х5 | |
Варіант 1 | |||||
Варіант 2 | |||||
Варіант 3 | |||||
Варіант 4 | |||||
Варіант 5 | |||||
Варіант 6 | |||||
Варіант 7 | |||||
Варіант 8 | |||||
Варіант 9 | |||||
Варіант 10 |
Згідно варіанту завдання обрати продуктивність ліній з таблиці 7.4. Обрати обмеження по попиту з таблиці 7.5.
Таблиця 7.4
Продуктивність ліній (т/рік) | ||
Непарні варіанти | Парні варіанти: | |
Варіант 1 | ||
Варіант 2 | ||
Варіант 3 | ||
Варіант 4 | ||
Варіант 5 | ||
Варіант 6 | ||
Варіант 7 | ||
Варіант 8 | ||
Варіант 9 | ||
Варіант 10 |
Таблиця 7.5
Обмеження по попиту (т/рік)
Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | Х7 | Х8 | Х9 | |
max | |||||||||
min |
Таблиця 7.2
Дата публикования: 2015-01-04; Прочитано: 1445 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!