Файл: Практикум Челябинск 2019.pdf

71
Рис. 4.25. Найденное оптимальное решение венгерским методом
Варианты заданий для самостоятельной работы
Записать матрицу назначений и найти значение целевой функции с помощью надстройки Поиск решения и венгерского метода.
Вариант 1
Руководство фирмы приняло решение произвести инспекцию своих предприятий в Москве, Питере, Одессе, Берлине и Ньювасюках, направляя туда своих вице-президентов, каждый из которых в компании возглавляет одно из направлений (финансы, маркетинг, производство и персонал).
Хотя может существовать большое число факторов, которые нужно учесть при таком назначении (знание языка, узкая специализация, невозможность оторваться от прямых обязанностей и т. д.), руководство компании решило оптимизировать в качестве первого шага только суммарные затраты на командировку вице-президентов. Таблица командировочных расходов в различные города (тыс. руб) приведена ниже.
Вице- президенты
Москва
Питер
Одесса
Берлин
Ньювасюки
По финансам
22,45 22,92 34 45 11,77
По маркетингу
21,85 22,5 4 32 43 15,87
По производству 23,91 17,56 35 46 10,33
По персоналу
22,22 29,62 31 42 14,83
Требуется составить схему распределения вице-президентов по филиалам, минимизирующую командировочные расходы.
Вариант 2
Администрация деревоперерабатывающего предприятия «Осинка» приняла на работу пять человек. Каждый из них имеет различные способности и навыки и затрачивает различное время на выполнение определенной работы. В настоящее время необходимо выполнить пять

72 видов работ. Время выполнения работы каждым работником приведено в таблице.
Работник
Время выполнения, ч работы 1 работы 2 работы 3 работы 4 работы 5
M
l
21 15 20 18 16
М
2 24 18 18 23 15
М
З
22 15 25 15 14
М
4 26 21 22 25 12
М
5 27 19 23 32 23
Требуется назначить на каждый вид работы одного из работников. Как это нужно сделать, чтобы общее время, необходимое для завершения всех видов работ, было минимальным?
Вариант 3
Членов Ассоциации ученых Новосибирска недавно уведомили, что их ассоциация получит государственные гранты на проведение исследований в соответствии с четырьмя основными исследовательскими проектами.
Исполнительный директор ассоциации должен по каждому проекту назначить научного руководителя. В настоящее время эти обязанности можно возложить на одного из пяти исследователей – Иванов, Петров,
Сидоров, Андреев и Симонов. Время, требуемое для завершения каждого из исследовательских проектов, зависит от опыта и способностей исследователя, которому будет поручено руководство выполнением проекта. Исполнительному директору были представлены оценки времени выполнения проекта каждым из ученых (в днях).
Ученый-исследователь
Проект
1 2
3 4
Иванов
80 99 60 79
Петров
72 87 48 91
Сидоров
96 96 72 89
Андреев
60 89 52 92
Симонов
64 78 60 96
Так как все четыре проекта обладают равным приоритетом в выполнении, исполнительный директор заинтересован в таком назначении научных руководителей, которое бы позволило свести к минимуму общее время (в днях), требуемое для завершения всех четырех проектов.
Требуется определить оптимальный вариант назначения научных руководителей проектов и, следовательно, общее число дней, необходимое для завершения четырех проектов.
Вариант 4
Руководство рекламного агентства должно решить, кто из четырех делопроизводителей будет работать со счетами каждого из четырех

73 основных клиентов. Затраты при каждом назначении для каждого делопроизводителя представлены в таблице.
Делопроизводитель
Проект
1 2
3 4
A
15 19 20 18
B
14 23 17 14
C
11 22 22 14
D
21 24 26 24
Сформулируйте задачу и найдите оптимальное решение.
Вариант 5
Компании «Авто» нужно назначить четырех представителей в четыре региона. Каждый представитель в разных регионах способен добиться разного объема продаж. Объемы продаж (в тыс. ден. ед.) при различных вариантах назначений показаны в таблице.
Представитель
Регион
1 2
3 4
A
65 73 105 58
B
90 67 87 75
C
106 86 96 89
D
84 69 79 103
Компания хочет максимизировать суммарный объем продаж. Однако назначить продавца B в регион 1 и продавца А в регион 2 нельзя, поскольку будет нарушен принцип ротации персонала. Постройте модель для данной ситуации и найдите оптимальное решение.
Вариант 6
В некоторой фирме появились вакантные должности: менеджера, программиста, бизнес-аналитика, маркетолога и руководителя проектов. В качестве кандидатов на эти должности рассматриваются сотрудники этой же фирмы: Андреев, Ильин, Смирнов, Котов и Дмитриев. Затраты на замещение должностей кандидатами (в тыс. руб.), связанные с необходимостью их предварительного обучения и стажировки, заданы в таблице.
Кандидаты
Должности
Менеджер Програм- мист
Бизнес- аналитик
Маркетолог Руководитель проекта
Андреев
5 10 9
14 6
Ильин
13 15 11 19 17
Смирнов
7 14 12 8
10
Котов
8 11 6
7 9
Дмитриев
6 17 10 9
16
Требуется распределить всех кандидатов по работам так, чтобы общие затраты на замещение должностей кандидатами были минимальными.

74
Вариант 7
Фирма получила заказы на разработку пяти программных продуктов.
На фирме работают шесть квалифицированных программистов, которым можно поручить выполнение этих заказов. Каждый из них дал оценку времени (в днях), требуемого для разработки программ. Эти оценки приведены в таблице.
Программисты
Программные продукты
1 2
3 4
5
Андреев
46 59 24 62 67
Ильин
47 56 32 55 70
Смирнов
44 52 29 61 60
Котов
47 59 27 64 73
Дмитриев
43 65 20 60 75
Кузьмин
41 53 28 54 68
Выполнение каждого из пяти заказов фирма решила поручить одному программисту. Очевидно, что один из программистов не получит заказ.
Каждому программисту, которому будет поручено выполнить заказ, фирма предложит оплату 2 тыс. руб. в день. Распределите работу между программистами так, чтобы общие издержки на разработку программ были минимальными.
Вариант 8
Фирма получила заказы на разработку пяти программных продуктов.
На фирме работают пять квалифицированных программистов, которым можно поручить выполнение этих заказов. Каждый из них дал оценку времени (в днях), требуемого для разработки программ. Эти оценки приведены в таблице.
Программисты
Программные продукты
1 2
3 4
5
Андреев
46 59 24 62 67
Ильин
47 56 32 55 70
Смирнов
44 52 39 61 60
Котов
47 59 27 64 73
Дмитриев
43 65 20 60 75
Выполнение каждого из пяти заказов фирма решила поручить одному программисту.
В зависимости от квалификации программистов была достигнута договоренность о следующих размерах оплаты в день (в тыс. руб.).

75
Программист
Размер оплаты
Андреев
1
Ильин
2
Смирнов
1,5
Котов
2
Дмитриев
1,5
Распределите работу между программистами так, чтобы общие издержки на разработку программ были минимальными.
Вариант 9
В Центральном административном округе города Москвы открываются четыре магазина торговли по предварительным заказам – в районах
Басманный, Замоскворечье, Мещанский и Таганский. Идея проекта состоит в том, что товары хранятся на четырех централизованных складах, находящихся в Северном, Северо-Восточном, Южном и Западном административных округах, и несколько раз в день по мере поступления заказов доставляются в магазины небольшими партиями.
Время, затрачиваемое на доставку продукции со складов в магазины, приведено в таблице (в минутах):
Басманный
Замоскворечье Мещанский
Таганский
Северный
20 30 45 30
Северо-
Восточный
45 25 20 20
Южный
35 15 30 20
Западный
30 20 20 30
Руководство сети магазинов должно решить вопрос прикрепления магазинов к складам так, чтобы каждый склад обслуживал только один магазин, а время доставки товаров было минимальным.
Вариант 10
Фирма получила заказ на срочный перевод четырех книг с итальянского языка. Фирма может располагать услугами 5 переводчиков, способных выполнить работу такого уровня. Время в днях, за которое каждый переводчик справится с работой, приведено в таблице:
Книга 1
Книга 2
Книга 3
Книга 4
Смирнов
10 25 14 25
Зайцев
8 12 16 28
Кротов
12 18 17 33
Попов
14 10 15 31
Свистунов
11 20 18 28
Фирма использует повременную оплату труда. Переводчики имеют разную квалификацию, поэтому за день работы фирма платит Смирнову
700 рублей в день, Зайцеву

800 рублей в день, Кротову

600, Попову

900, Свистунову

650.

76
Поскольку по оценке фирмы качество переводов в итоге будет примерно одинаковым, руководство фирмы просит Вас составить такое распределение работ, которое позволит минимизировать затраты на переводы.
Вариант 11
Компания «Евротур» организует экскурсионные автобусные туры по странам Европы. Компания получила четыре новых автобуса и предполагает направить их на маршруты во Францию, Италию, Чехию и
Испанию.
Каждый автобус обслуживают два водителя. Компанией приглашены восемь водителей, в различной степени знакомых с дорогами европейских стран (в % от экскурсионного маршрута).
Франция
Италия
Чехия
Испания
Александр
56 43 85 68
Алексей
56 48 99 70
Валентин
63 94 54 84
Василий
96 89 65 34
Николай
44 62 69 72
Виктор
74 85 42 68
Андрей
23 59 37 92
Юрий
89 45 53 78
Необходимо распределить водителей так, чтобы общий показатель освоения маршрутов был максимальным.
Вариант 12
В распоряжении некоторой компании имеется шесть торговых точек и шесть продавцов. Из опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор оценил деятельность каждого продавца в каждой торговой точке при условии, что назначение первого продавца на четвертую торговую точку недопустимо. Результаты этой оценки представлены в таблице.
Продавец
Объем продаж по торговым точкам
I
II
III
IV
V
VI
A
68 73 74 82 75 69
B
57 61 58 63 61 59
C
36 38 41 45 25 27
D
40 42 47 46 54 36
E
62 70 68 67 69 70
F
65 63 69 70 72 68
Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?

77
Вариант 13
Существует четыре продавца A, B, C, D и четыре торговые точки.
Эффективность работы продавцов на торговых точках представлена в таблице.
Продавец
Эффективность работы по торговым точкам
I
II
III
IV
A
6 13 7
8
B
5 6
8 16
C
3 8
14 5
D
10 12 7
6
Найти оптимальное распределение продавцов по торговым точкам.
Вариант 14
Необходимо распределить четырех рабочих по четырем видам работ.
Различная квалификация рабочих обуславливает различную стоимость выполнения работ. Стоимость работ (ден. ед.) приведена в таблице.
Рабочие
Виды работ
I
II
III
IV
A
50 50

40
B
70 40 20 30
C
90 30 50

D
50 20 60 70
Отметим, что первый рабочий не может выполнять работу 3, а третий – работу 4. Найдите оптимальное решение.
Предположим, что можно ввести нового (пятого) рабочего, способного выполнить любой вид работ со стоимостью соответственно 60, 45, 32 и 80 ден. ед. Будет ли экономически выгодным заменить одного из
«работающих» рабочих новым?
Вариант 15
Необходимо распределить четырех рабочих по четырем видам работ.
Различная квалификация рабочих обуславливает различную стоимость выполнения работ. Стоимость работ (ден. ед.) приведена в таблице.
Рабочие
Виды работ
I
II
III
IV
A
50

50 20
B
70 50 20 30
C
90 30

50
D
50 20 60 70
Отметим, что первый рабочий не может выполнять работу 2, а третий – работу 3. Найдите оптимальное решение.
Предположим, необходимо ввести новый вид работы, который может выполнить любой из четырех рабочих, со стоимостью соответственно 20,

78 30, 20 и 80 ден. ед. Будет ли новая работа более выгодной по сравнению с имеющимися?
Вариант 16
Пять учебных групп экономического факультета МГУ собираются посетить во время практики 10 промышленных предприятий (П-i) и научно-исследовательских институтов (НИИ-i). Каждая учебная группа может посетить две организации. Путем опроса студентов выявлены предпочтения каждой группы для 10 организаций (1 означает «наиболее предпочтительна», а 10 – «наименее предпочтительна»). Предпочтения каждой из пяти учебных групп показаны в таблице.
Группа
Организация
П-1 П-2 П-3 П-4 П-5 НИИ-
1
НИИ-
2
НИИ-
3
НИИ-
4
НИИ-
5 1
3 2
1 4
6 7
10 5
9 8
2 2
5 1
3 7
4 8
6 9
10 3
1 3
2 5
4 8
6 7
10 9
4 4
3 1
2 6
7 10 5
9 8
5 2
5 1
3 6
4 9
10 8
7
Определить, какие две организации должна посетить каждая группа, чтобы в максимальной степени были учтены предпочтения всех студентов.

79
Таблица 5.1.1
g
1
g
2
…
g
i
…
g
n
x
1
g
1
(x
1
) g
2
(x
1
)
… g
i
(x
1
)
… g
n
(x
1
)
x
2
g
1
(x
2
) g
2
(x
2
)
… g
i
(x
2
)
… g
n
(x
2
)
x
i
…
…
… g
i
(x i
)
…
…
x
n
g
1
(x n
) g
2
(x n
)
… g
i
(x n
)
… g
n
(x n
)
Определить вектор


*
n
*
k
*
*
*
x
,
,
x
,
,
x
,
x
X


2 1

, удовлетворяющий условиям
,
,
1
,
0
,
1
n
i
x
T
x
i
n
i
i





и обеспечивающий максимум целевой функции
Процесс оптимизации разобьем на n шагов и на k-м шаге будем оптимизировать инвестирование не всех предприятий, а только предприятий с k- го по n-е.
При этом на них расходуются не все средства, а некоторая меньшая сумма C
k

T , которая и будет являться переменной состояния системы.
Переменной управления на k-м шаге назовем величину x
k
средств, вкладываемых в k-е предприятие.
В качестве функции Беллмана F
k
(C
k
) на k-м шаге можно выбрать максимально возможную прибыль, которую можно получить с предприятий с k- го по n-е при условии, что на их инвестирование осталось C
k
средств.
Очевидно, что при вложении в k-е предприятие x
k
средств получим прибыль
g
k
(x
k
), а система к (k+1)-му шагу перейдет в состояние C
k+1
=C
k

x
k
, т.е. на инвестирование предприятий с (k+1)-го до n-го останется C
k+1 средств.
Таким образом, на первом шаге условной оптимизации при k=n функция
Беллмана представляет собой прибыль только с n-го предприятия.
При этом на его инвестирование может выделяться количество средств C
k
,


C
k

T.
Очевидно, чтобы получить максимум прибыли с этого последнего предприятия, надо вложить в него все эти средства, т.е.
F
n
(C
n
) = g
n
(C
n
) и x
n
= C
n
На каждом из последующих шагов для вычисления функции Беллмана следует использовать результаты предыдущего шага.
Максимально возможная прибыль, которая может быть получена предприятием с k-го по n-е, равна
 
 




,
1
,
max
1
n
k
x
C
F
x
g
C
F
k
k
k
k
k
C
x
k
k
k
k






 
 
max
1
*




n
i
i
i
x
g
X
F