Математична модель задачі на призначення на максимум
ДЕРЖАВНА
МИТНА СЛУЖБА УКРАЇНИ
АКАДЕМІЯ
МИТНОЇ СЛУЖБИ УКРАЇНИ
Контрольна
робота
з
дисципліни: «Економіко-математичне моделювання»
м.
Дніпропетровськ
Завдання 1
Скласти математичну модель задачі на
призначення.
Як оптимальним чином призначити 6
митників на 6 робіт, щоб загальна ефективність від виконання всіх робіт була
найкращою.
Відома матриця ефективності С.
Розв’язати задачу за допомогою
електронних таблиць Microsoft Excel на максимум та мінімум (для задачі на
мінімум cij - час виконання, а на максимум cij - продуктивність виконання i-м
митником j-ї роботи).
Проаналізувати розв’язок задачі на
мінімум: як необхідно змінити час виконання певної роботи певним митником для
того, щоб його призначили на виконання цієї роботи.
Проаналізувати розв’язок задачі на
максимум: як зміниться загальна продуктивність виконання усіх робіт, якщо на
виконання роботи призначити «найгіршого» митника.
Розв'язок
Складемо математичну модель задачі
на призначення на максимум.
Де, коефіцієнт Сij визначає
продуктивність призначення робітника i на роботу j.
Нехай:
i, j = 1,2,...6.
Цільова функція:
+x12+x13+x14+x15+x16=1+x22+x23+x24+x25+x26=1+x32+x33+x34+x35+x36=1+x42+x43+x44+x45+x46=1+x52+x53+x54+x55+x56=1+x62+x63+x64+x65+x66=1+x21+x31+x41+x51+x61=1+x22+x32+x42+x52+x62=1+x23+x33+x43+x53+x63=1+x24+x34+x44+x54+x64=1+x25+x35+x45+x55+x65=1+x26+x36+x46+x56+x66=1
Вхідна інформація заноситься
в робочий аркуш Excel.
У діапазон клітинок I12:I17
уведені значення правих частин обмежень у рядках. У клітинки Н12:Н17 введено
формули для лівих частин обмежень. Тут використовується функція СУММ. Так, в
клітинку Н12 слід увести: =СУММ (B12:G12), в клітинку Н13: =СУММ (B13:G13) і т.
д.
У діапазон клітинок B19:G19
введено значення правих частин обмежень за стовпцями. У чарунки B18:G18 введено
формули для лівих частин обмежень. Тут також використовується функція СУММ.
робітник
ефективність математичний модель
Рис. 1
Виберіть в меню Сервис =>
Поиск решения. У діалоговому вікні Поиск решения необхідно зазначити вихідні
дані та додати обмеження, що вказують на цілочисловість змінних. Для цього в
діалогове вікно Добавление ограничений потрібно ввести адресу клітинки і зі
списку, що розкрився, вибрати цел.
У діалоговому вікні Параметры
встановіть прапорці у полі Линейная модель і в полі Неотрицательные значения.
Рис. 2
Рис. 3
Аналіз розв'язку задачі. Результати
розв'язання наведено вище.
Оптимальний (максимальний) варіант
призначення x15=x26=x33=x42=x51=x64=1, решта xij = 0, тобто перший виконавець
призначається на п’яту роботу, другий - на шосту, третій - на третю, четвертий
- на другу, п'ятий - на першу, шостий - четверту. Сумарна продуктивність
максимальна і дорівнює 6+8+7+6+6+3=36 (клітинка G10).
Складемо математичну модель задачі
на призначення на мінімум.
Де, коефіцієнт cij визначає час виконання
і робітника на роботу j.
Нехай:
, якщо і-й виконавець призначений на
j-тий вид робіт,
- в іншому випадку,,j= 1,2,...6.
Складемо систему обмежень:
x11+x12+x13+x14+x15+x16=1+x22+x23+x24+x25+x26=1+x32+x33+x34+x35+x36=1+x42+x43+x44+x45+x46=1+x52+x53+x54+x55+x56=1+x62+x63+x64+x65+x66=1+x21+x31+x41+x51+x61=1+x22+x32+x42+x52+x62=1+x23+x33+x43+x53+x63=1+x24+x34+x44+x54+x64=1+x25+x35+x45+x55+x65=1+x26+x36+x46+x56+x66=1
Вхідна інформація заноситься в
робочий аркуш Excel.
У клітинки Н12:Н17 введено формули
для лівих частин обмежень. Тут використовується функція СУММ. Так, в клітинку
Н12 слід увести: =CУMM(B12:G12), в клітинку Н13: =CУMM(B13:G13) і т. д.
У діапазон клітинок B19:G19 введено
значення правих частин обмежень за стовпцями. У чарунки B18:G18 введено формули
для лівих частин обмежень. Так, у клітинку В18 використовується функція СУММ.
Рис. 4
Виберіть в меню Сервис => Поиск
решения. У діалоговому вікні Поиск решения необхідно зазначити вихідні дані та
додати обмеження, що вказують на цілочисловість змінних. Для цього в діалогове
вікно Добавление ограничений потрібно ввести адресу чарунки зі списку, що
розкрився, вибрати цел.
У діалоговому вікні Параметры
встановіть прапорці у полі Линейная модель і в полі Неотрицательные значения.
Рис. 5
Рис. 6
Аналіз розв'язку задачі. Результати
розв'язання наведено вище.
Оптимальний (мінімальний) варіант
призначення x11=x26=x35=x43=x54=x62=1, решта xij=0. Тобто необхідно змінити час
виконання певної роботи першим митником для того, щоб його призначили на
виконання першої роботи, другим - шостої, третім - п’ятої, четвертим - третьої,
п'ятим - четвертої, шостим - другої роботи. Сумарний мінімальний час виконання
робіт: 5+8+2+2+3+2=22 (клітинка G10).