Экономико-математическое моделирование (в Mathcad). Решение задач на примере задачи о назначениях.

2. Формулировка задачи о назначениях.





Задача.

Рассмотрим такую задачу. Фирме необходимо заполнить m вакантных должностей, на которые имеются n претендентов. Каждый из них может занять любую, но одну из предлагаемых должностей. Пусть претенденты и должности пронумерованы соответственно последовательными числами от 0 до n-1 и от 0 до m-1. В силу многих обстоятельств (способности, образование, опыт, коммуникабельность и т.п.) полезность каждого кандидата для фирмы зависит от должности, на которую он будет назначен. Пусть возможный доход фирмы за конкретный промежуток времени при принятии претендента j (j=0,1,,n-1) на должность i (i=0,1,,m-1) известен и равен Ui,j. Матрицу U = || Ui,j || (i = 0,1,,m-1; j = 0,1,,n-1) назовем матрицей доходов. Если nm, то n-m претендентов работу не получат. Определить такое назначение работников на должности, при котором фирма будет иметь наибольший доход. Подобное назначение называют оптимальным, а саму задачу  задачей о назначении.

Для данной задачи требуется определить наименьшее время, за которое будет разработано пять программ каждым из пяти программистами. Остальные условия соответствуют условиям задачи о назначениях.



Задача 4. Фирма получила закаы на разработку пяти программных продуктов. На фирме работают пять квалифицированных программистов, которым можно поручить выполнение этих заказов. Каждый программист дал оценку времени (в днях), которое ему требуется для разработки программ. Эти оценки приведены в таблице.









Программа 1 2 3 4 5

Программист

Волков 46 59 24 62 67

Лисицын 47 56 32 55 70

Медведев 44 52 19 61 60

Зайцев 47 59 17 64 73

Барсуков 43 65 20 60 75



Выполнение каждого из пяти заказов фирма решила поручить одному программисту. Требуется распределить работу между программистами так, чтобы суммарное время, затраченное ими на разработку всех программ, было минимальным.

Решение данной задачи рассмотрим в следующем пункте.