Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Тема. Задачі цілочисельного програмування



Мета роботи:Набути навичок складання і розв’язку оптимізаційних задач про призначення.

 

Завдання:

Задача 1.Знайти цілочисельний розв’язок задачі, заданої системою обмежень-нерівностей:

та цільовою функцією .

Задача 2.Меблеве підприємство випускає книжкові полиці, тумбу під телевізори і три види наборів меблів. Характеристики кожного виду продукції наведено в табл. 12.1. За умови отримання максимального прибутку обсяг товарної продукції повинен скласти не менше 459.31 тис. грн. Ситуація зі збутом продукції склалася наступна. Книжковими полицями ринок насичений, тому торгові організації зменшили обсяг договорів до 10 тис. шт. Тумби для телевізорів можуть бути реалізовані в обсягах від 4 до 7 тис. шт., Набори меблів 2 - від 7 до 10 тис. шт. Попит на набори меблів 1 і 3 необмежений, і потрібно не менше 10 тис. шт. Підприємство має технологічне обладнання, кількість якого і норми витрат часу на виготовлення одиниці продукції кожного виду наведені в табл. 12.2. Підприємство працює у дві зміни, ефективний час роботи кожної машини - 3945 годину (коефіцієнт змінності 1,9). Оптимізувати виробничу програму підприємства. (Потрібно знайти план випуску продукції, який максимізує прибуток підприємства).

 

Таблиця 12.1 – Характеристики видів продукції

Показники Види продукції
Набори меблів Книжкові полиці   Тумба під телевізор
Оптова ціна одиниці виробу, тис. грн. 7,2 14,3 32,5 0,182 1,5
Прибуток від реализації, тис. грн 2,4 4,5 8,9 0,061 0,45

 

Таблиця 12.2 – Норми витрат часу на виготовлення одиниці продукції

Найменування обладнання Число, шт. Види продукції
Набори меблів Книжкові полиці Тумба під телевізор
Лінія розкрою деревостружкових плит 0,068 0,096 0,207 0,018 0,042
гільйотинні ножиці 0,045 0,080 0,158 0,011 0,035
лінія облицювання 0,132 0,184 0,428 0,020 0,060
Лінія обрізки кромки 0,057 0,082 0,230 0,010 0,028
Полірувальні верстати 0,063 0,090 0,217 0,010 0,032
Полірувальні верстати 0,170 0,280 0,620 0,020 0,096

 

Завдання для самостійної роботи:

Задача 1.

1. 2.
3. 4.  
5. 6.
7.   8.
9.   10.

 



 

Література: 2, 3, 6, 8, 9.

 

Теоретичні відомості

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

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

 

за умов:

,

,

та умовах невід'ємності та цілочисельності змінних

, — цілі числа.

Методичні рекомендації до виконання завдань:

Задача 1. Завантажимо табличний процесор Excel і скопіюємо до комірок таблицю із вихідними даними. Перш ніж запистити «Поиск решений» побудуємо математичну модель задачі, увівши значення цільової функції:

=4*x1-x2

та рівняння системи обмежень у відповідні комірки (рис. 1):

=5*x1-7*x2;

=3*x1-x2;

=x1+x2.

 

Рисунок 12.1 – Модель задачі

 

Цілочисельний розв’язок такої задачі шукатимемо за допомогою програми «Поиск решения». Від розв’язування звичайної задачі лінійного програмування такий розв’язок відрізняється лише одним обмеженням: при доповненні обмежень вказується ознака цілочисельності для відповідних змінних. Окрім того, враховуючи наявність різних знаків в системі рівнянь обмежень, кожне рівняння у полі «Ограничения» вводиться окремо (рис. 12.2).

 

Рисунок 12.2 – Поиск решения



 

У результаті отримаємо наступні значення змінних (рис. 12.3).

Рисунок 12.3 – Результати розв’язку задачі

 

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

 

Задача 2.Скопіємо до комірок таблицю із вихідними даними та побудуємо економіко-математичну модель задачі:

Позначимо через Х1, Х2, Х3, Х4, Х5 кількість продукції відповідного типу (шт). Оскільки кожна машина працює у дві зміни, ефективний час роботи складає 3945 годин. Визначимо фонд часу роботи обладнання кожного типу:

линия раскроя древесностружечных плит 2∙3945 = 7890 год.;

гильотинные ножницы 1∙3945 = 3945 год.;

линия облицовки 2∙3945 = 7890 год.;

линия обрезки кромок 2∙3945 = 7890 год.;

лаконаливная машина 2∙3945 = 7890 год.;

полировальные станки 4∙3945 = 157 80 год..

 

Цільова функція в такому випадку матиме вигляд:

f(Х) = 2,4Хl + 4,5Х2 + 8,9Х3 + 0,06Х4 + 0,45X5 → mах.

Обмеження по об’єму товарної продукції:

7,2Х1 + 14,3Х2 + 26,9Х3 + 0,243Х4 + 1,5Х5 ≥ 459,31 тыс. руб.

Обмеження по фонду часу роботи обладнаня:

0,068Х1 + 0,096Х2 + 0,207Х3 + 0,018Х4 + 0,042Х5 ≤ 7890,

0,045Х1 + 0,080Х2 + 0,158Х3 + 0,011X4 + 0,035Х5 ≤ 3945,

0,132Х1 + 0,184Х2 + 0,428Х3 + 0,020Х4 + 0,060Х5 ≤ 7890,

0,057Х1 + 0,082Х2 + 0,230Х3 + 0,010Х4 + 0,028Х5 ≤ 7890,

0,063Х1 + 0,090Х2 + 0,217Х3 + 0,010Х4 + 0,033Х5 ≤ 7890,

0,170Х1 + 0,280Х2 + 0,620Х3 + 0,020Х4 + 0,096Х5 ≤ 157 800.

Обмеження по збуту продукції:

Х1 ≥ 10 000;

7000 ≤ Х2 ≤ 10000;

Х3 ≥ 10000;

Х4 ≤ 10 000;

4000 ≤ Х5 ≤ 7000;

Х1, Х2, Х3, Х4, Х5 ≥ 0;

Х1, X2, Х3, Х4, Х5 - цілі числа.

4. Уведемо до комірок математичну модель задачі:

 

Порядок дій в Excel

1. Введемо значення змінних та цільової функції (рис. 12.4):

Рисунок 12.4 – Введення значень змінних та цільової функції

 

2. Введемо обмеження на обсяг (рис. 12.5):

 

Рисунок 12.5 – Обмеження на обсяги випуску

 

3.Введемо обмеження по фонду часу роботи обладнання (рис. 12.6):

Рисунок 12.6 – Обмеження по фонду часу

 

4. Введемо обмеження по збуту продукції:

Рисунок 12.7 – Обмеження на збут продукції

 

Загальний вигляд оформлення моделі (рис. 12.7):

 

Рисунок 12.8 – Загальний вигляд моделі

 

Для розв’язування задачи використовується«Поиск решений»(рис. 12.9):

Рисунок 12.9 – Поиск решения

Для врахування цілочесельності змінних – вводять відповідні обмеження (рис. 12.10).

 

Рисунок 12.10 – Цілочисельність змінних

 

В результаті використання «Поиска решений» отримуємо наступні результати (рис. 12.11):

Рисунок 12.11 – Отримані результати

 

Відповідь. Для отримання максимального прибутку 459310 грн. необхідно виробити:

10000 шт. наборів меблів виду 1;

10000 шт. наборів меблів виду 2;

10000 шт. наборів меблів виду 3;

1500 шт. книжкових полиць;

7000 тумб під телевізор.

 

 

Питання для самоконтролю:

 

1. У чому особливості цілочисельних задач лінійного програмування?

2. Розкрийте економічний зміст цілочисельних задач лінійного програмування.

3. Охарактеризуйте методи розвзяування цілочисельних задач лінійного програмування.

 

ПРАКТИЧНЕ ЗАНЯТТЯ 14


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!