Математична модель задачі на призначення на максимум

[Введите текст]

ДЕРЖАВНА МИТНА СЛУЖБА УКРАЇНИ АКАДЕМІЯ МИТНОЇ СЛУЖБИ УКРАЇНИ

Контрольна робота

з дисципліни: «Економіко-математичне моделювання»

м. Дніпропетровськ

Завдання 1

Скласти математичну модель задачі на призначення.

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

Відома матриця ефективності С.

Розв’язати задачу за допомогою електронних таблиць Microsoft Excel на максимум та мінімум (для задачі на мінімум cij — час виконання, а на максимум cij — продуктивність виконання i-м митником j-ї роботи).

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

Проаналізувати розв’язок задачі на максимум: як зміниться загальна продуктивність виконання усіх робіт, якщо на виконання роботи призначити «найгіршого» митника.

Розв’язок Складемо математичну модель задачі на призначення на максимум.

Де, коефіцієнт Сij визначає продуктивність призначення робітника i на роботу j.

Нехай:

i, j = 1,2,…6.

Цільова функція:

Складемо систему обмежень:

x11+x12+x13+x14+x15+x16=1

x21+x22+x23+x24+x25+x26=1

x31+x32+x33+x34+x35+x36=1

x41+x42+x43+x44+x45+x46=1

x51+x52+x53+x54+x55+x56=1

x61+x62+x63+x64+x65+x66=1

x11+x21+x31+x41+x51+x61=1

x12+x22+x32+x42+x52+x62=1

x13+x23+x33+x43+x53+x63=1

x14+x24+x34+x44+x54+x64=1

x15+x25+x35+x45+x55+x65=1

x16+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.

Нехай:

1, якщо і-й виконавець призначений на j-тий вид робіт,

0 — в іншому випадку,

i, j= 1,2,…6.

Цільова функція:

Складемо систему обмежень:

x11+x12+x13+x14+x15+x16=1

x21+x22+x23+x24+x25+x26=1

x31+x32+x33+x34+x35+x36=1

x41+x42+x43+x44+x45+x46=1

x51+x52+x53+x54+x55+x56=1

x61+x62+x63+x64+x65+x66=1

x11+x21+x31+x41+x51+x61=1

x12+x22+x32+x42+x52+x62=1

x13+x23+x33+x43+x53+x63=1

x14+x24+x34+x44+x54+x64=1

x15+x25+x35+x45+x55+x65=1

x16+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).