J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij icon

J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij




Скачати 44.53 Kb.
НазваJ (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij
Дата06.09.2012
Розмір44.53 Kb.
ТипЗадача

4. Задача про призначення


4.1. Формулювання задачі

Потрібно розподілити серед m виконавців n завдань (робіт). Робота j (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij. Завдання полягає в такому розподілі робіт серед виконавців, якому відповідає мінімум сумарних витрат. Причому, кожному виконавцю доручається тільки одна робота. Така задача і називається задачею про призначення Її можна розглядати як окремий випадок транспортної задачі. Тут виконавці можуть представляти “пункти відправлення”, а види робіт - “пункти призначення” і навпаки. Пропозиція і попит у кожному пункті відправлення і пункті призначення дорівнює одиниці. Якщо яку роботу не можна доручити якомусь виконавцю, то відповідна вартість Cij береться рівної дуже великому числу М.


^ 4.2. Математична модель задачі про призначення.

Нехай xij - невідомі перемінні. Очевидно, що



Тоді необхідно мінімізувати цільову функцію

,

при обмеженнях

, j=1, n;

, i=1, m;

xij=0 або 1.

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


^ 4.3. Рішення задачі про призначення

Властивість. Оптимальне рішення задачі про призначення не зміниться, якщо до будь-якого рядку або стовпцю матриці вартостей відняти (або додати) постійний розмір. Дійсно, якщо з і-й рядки відняти постійну рі, із j-го стовпця - gi, те нові вартості будуть иметь вид



Тоді нова цільова функція



Тому що , те . Звідси випливає, що мінімізація вихідної цільової функції L приводить до такого ж рішенню, як і мінімізація L'.

Використовуючи приведене вище властивість, можна побудувати матрицю вартості з нульовими елементами. І якщо ці нульові елементи матриці вартостей відповідають припустимому рішенню, то таке рішення буде оптимальним, оскільки вартість не може бути негативної.

Покажемо, як реалізується цей прийом на наступному прикладі: a=||1,1,1||; b=||1,1,1||; .

У матриці с’ нульові елементи отримані вирахуванням найменшого елемента в кожному рядку з усіх елементом цього рядка:



Віднімаючи g3=2 із третього стовпця, одержуємо матрицю з виду

,

g3=2.

Квадратами в матриці з” відзначені елементи, що відповідають припустимому (а оскільки ці елементи нульові, те й оптимальному) рішенню: x11=х2332=1,

min L=c11+c23+c32=5+12+13=30. Зауважимо, що ця вартість дорівнює p1+p2+p3+g3=30.

На жаль, не завжди удасться визначити припустиме рішення настільки просто, як у приведеному прикладі. Тому вимагаються додаткові прийоми для перебування оптимального рішення. Ці прийоми проілюструємо на наступному прикладі: a=||1,1,1,1||; b=||1,1,1,1||;

.

Виконуючи ті ж нараховані кроки, що й у попередньому прикладі, маємо:



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



На наступному кроку вибирається найменший невикреслені елемент (х32=1). Цей елемент відраховується їх кожного невикресленого елемента і додається до кожному елементу, що коштує на перетинанні проведений прямих. У результаті отримуємо матрицю



У матриці с’’’ відзначені елементи, що відповідають припустимому і, отже, оптимальному рішенню: х11233244=1.

min L=c11+c23+c32+c44=1+10+5+5=21.

Якщо на останньому кроку оптимальне рішення не досягнуте, те процедуру проведення прямих варто повторити доти, поки не буде отримане припустиме рішення.

Як і для випадку транспортної задачі, якщо в задачі про призначення , та задачу потрібно збалансувати.


ТЕСТИ

(вірно або невірно)

4.1. Задачу про призначення можна вирішити методом, використовуваним для рішення транспортної задачі.

4.2. Якщо до будь-якого рядку (стовпцю) матриці платежів задачі про призначення додати (відняти) ту саму постійний розмір, то оптимальне рішення не зміниться.

4.3. У задачі про призначення допускається одному виконавцю доручати декілька робіт.

4.4. Допустимість рішення задачі про призначення полягає в тому, що в кожному рядку і кожному стовпці тільки одне значення xij дорівнює одиниці.

4.5. Будь-яке базисне рішення задачі про призначення є виродженим.


ЗАВДАННЯ

Вирішите наступні задачі про призначення


4.1. a=||1,1,1,1||; b=||1,1,1,1||




4.2. a=||1,1,1,1,1||; b=||1,1,1,1,1||



4.3. a=||1,1,1,1||; b=||1,1,1,1,1||




4.4. a=||1,1,1,1,1||; b=||1,1,1,1||



4.5. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.6. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.7. a=||1,1,1,1,1,1||; b=||1,1,1,1||




4.8. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.9. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.10. a=||1,1,1,1||; b=||1,1,1,1||




4.11. a=||1,1,1,1,1||; b=||1,1,1,1,1,1||




4.12. a=||1,1,1,1||; b=||1,1,1,1,1||




4.13. a=||1,1,1,1,1||; b=||1,1,1,1||




4.14. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.15. a=||1,1,1,1||; b=||1,1,1,1,1||




4.16. a=||1,1,1,1,1||; b=||1,1,1,1,1||





4.17. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.18. a=||1,1,1,1||; b=||1,1,1,1||




4.19. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.20. a=||1,1,1,1,1||; b=||1,1,1,1||




4.21. a=||1,1,1,1,1||; b=||1,1,1,1,1||




4.22. a=||1,1,1,1||; b=||1,1,1,1,1||





Схожі:

J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconРоманова О. В., старший викладач Дніпропетровський національний університет імені Олеся Гончара підходи до класифікації людського капіталу в бухгалтерському обліку
Людський капітал – це один з різновидів капіталу, який має відповідні ознаки капіталу (потребує витрат часу і матеріальних витрат...
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconУхвала вченої Ради двнз «Київський національний економічний університет імені Вадима Гетьмана» «Про підвищення оплати за проведення практики студентів» від 25 вересня 2008р
Ння організації практики студентів. В останні роки виникли значні труднощі при оформленні договорів на проходження практики. Головною...
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconЛекція №9 Час відпочинку. Поняття та види часу
Оскільки законодавець протиставляє час відпочинку робочому часу, то тим самим весь час особи, що знаходиться в трудових відносинах,...
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconПравове регулювання робочого часу Поняття робочого часу та його види за трудовим законодавством
Трудове законодавство не містить визначення поняття робочого часу, його визначено у науковій літературі
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconНаказ №23-10 Про організацію навчального процесу екстернів на кафедрах навчально-наукових інститутів
З метою підвищення якості підготовки фахівців за кошти фізичних та юридичних осіб, покращення організації навчального процесу екстернів...
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij icon7: Правове регулювання державних витрат. Фінансування органів внутрішніх справ
Правове значення кошторису витрат бюджетної установи, порядок його розробки та затвердження
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconТема 7: Правове регулювання державних витрат Фінансування органів внутрішніх справ
Правове значення кошторису витрат бюджетної установи, порядок його розробки та затвердження
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconВ. О. Сухомлинського наказ 27 квітня 2012 р м. Миколаїв №119 Про розмір І порядок внесення оплати за навчання Згідно з рішення
Згідно з рішенням Вченої ради університету від 27. 03. 2012 р. (протокол № 10) щодо розміру оплати за навчання для студентів, які...
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconВ. О. Сухомлинського наказ 27 квітня 2012 р м. Миколаїв №119 Про розмір І порядок внесення оплати за навчання Згідно з рішення
Згідно з рішенням Вченої ради університету від 27. 03. 2012 р. (протокол № 10) щодо розміру оплати за навчання для студентів, які...
J (j=1,n), виконувана i-м виконавцем, вимагає витрат (оплати, часу) Cij iconТема практичного заняття №6 правове регулювання робочого часу
Чи можна в установах встановити меншу норму тривалості робочого часу, ніж це передбачено ч. 1 ст. 50 Кзпп україни?
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи