Имя материала: Исследование операций в экономике: модели, задачи, решения

Автор: Афанасьев Михаил Юрьевич

Глава 6. задача о назначениях

Цели

В процессе управления производством зачастую возникают задачи назначения исполнителей на различные виды работ, например: подбор кадров и назначение кандидатов на вакантные должности, распределение источников капитальных вложении между различными проектами научно-технического развития, распределение экипажей самолетов между авиалиниями.

Задачу о назначениях можно сформулировать следующим образом. Необходимо выполнить N различных работ. Для их выполнения можно привлечь N рабочих. Каждый рабочий за определенную плату готов выполнить любую работу. Выполнение любой работы следует поручить одному рабочему. Требуется так распределить работы между рабочими, чтобы общие затраты на выполнение всех работ были минимальными.

После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь определять и использовать для экономического анализа:

• задачу о назначениях в стандартной форме;

• открытую задачу о назначениях;

• таблицу задачи о назначениях;

• матрицу назначений;

• эффективность назначений.

Модели

Пусть т — количество работ.

Задача о назначениях в стандартной форме. При рассмотрении задачи о назначениях в стандартной форме предполагается, что количество рабочих равно количеству работ.

Обозначения:

сij — показатель эффективности назначения i-го рабочего на j-й работе, например издержки выполнения i-м рабочим j-й работы;

xij — переменная модели (хij = 1, если i-й рабочий используется на j-й работе, и xij = 0 в противном случае).

Модель задачи о назначениях:

Здесь     (1) — целевая функция (минимум издержек на выполнение всех работ);

(2) — система ограничений, отражающая следующие условия:

а) каждая работа должна быть выполнена одним рабочим;

б) каждый рабочий может быть привлечен к одной работе;

(3) — условия неотрицательности переменных.

При решении задачи о назначениях исходной информацией является таблица задачи о назначениях с={сij}, элементами которой служат показатели эффективности назначений. Для задачи о назначениях, записанной в стандартной форме, количество строк этой таблицы совпадает с количеством столбцов:

Результатом решения задачи о назначениях (1)—(3) является вектор х* = {}, компоненты которого — целые числа.

Оптимальный план задачи о назначениях (1)—(3) можно представить в виде квадратной матрицы назначений, в каждой строке и в каждом столбце которой находится ровно одна единица. Такую матрицу иногда называют матрицей перестановок. Значение целевой функции (1), соответствующее оптимальному плану, называют эффективностью назначений.

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

Пусть, например, количество рабочих п превышает количество работ т.

Введем дополнительные фиктивные работы с индексами j = w + 1,..., п. Коэффициенты таблицы назначений сij , i = 1,..., п; j = т + 1,..., п, положим равными нулю. В этом случае получаем задачу, сформулированную в стандартной форме. Если в оптимальном плане этой задачи  = 1 при j = т + 1,..., п, то исполнитель i назначается на выполнение фиктивной работы, т.е. остается без работы. Заметим, что оптимальное значение целевой функции исходной задачи совпадает с оптимальным значением задачи, приведенной к стандартной форме. Поэтому эффективность назначений в результате такого преобразования не меняется.

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

Примеры

Пример 1. Распределение работ.

Фирма получила заказы на разработку пяти программных продуктов. Для выполнения этих заказов решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В следующей таблице приведены оценки времени (в днях), необходимого программистам для выполнения каждой из этих работ:

Оценки даны самими программистами, и у фирмы нет основания им не доверять.

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

Вопросы:

1. Какое минимальное количество человекодней необходимо для выполнения всех пяти заказов?

2. Какую программу следует поручить Малкину?

3. Какую программу следует поручить Залкинду?

Решение. Таблица задачи о назначениях представлена в условии. Проведя расчеты, получаем следующую матрицу назначений:

Учитывая исходную информацию, получаем следующий результат:

Ответы: 1. 234 человекодня. 2. Программу 2. 3. Программу 1.

Вопросы

Вопрос 1. Задача о назначениях относится к классу задач:

1) линейного программирования;

2) эконометрических;

3) статистических;

4) имитационных;

5) не относится ни к одному из указанных классов.

Вопрос 2. Имеются две работы r1, r2, и два рабочих L1 , L2, каждый из которых может выполнить любую работу. Элемент aij матрицы А показывает время, необходимое рабочему i для выполнения работы j:

Решите задачу о назначениях. Чему равно минимальное время выполнения двух работ?

Варианты ответов:

1) 9; 2) 10; 3) 11; 4) 12; 5)13.

Вопрос 3. Как известно, задача о назначениях является частным случаем транспортной задачи. Какая из приведенных ниже характеристик транспортной таблицы, построенной для задачи о назначениях, наиболее правильная?

Варианты ответов:

1) объемы потребления равны единице, объемы поставок отличны от единицы;

2) объемы поставок равны единице, объемы потребления отличны от единицы;

3) матрица транспортных затрат квадратная, объемы поставок отличны от единицы;

4) матрица транспортных затрат квадратная, объемы потребления отличны от единицы;

5) матрица транспортных затрат прямоугольная, объемы поставок равны единице.

Вопрос 4. Оптимальный план задачи о назначениях можно представить в виде:

1) квадратной матрицы, в каждой строке которой находится одна единица;

2) квадратной матрицы, в каждом столбце которой находится одна единица;

3) квадратной матрицы, в каждой строке и в каждом столбце которой находится одна единица;

4) квадратной матрицы, в каждой строке которой находится хотя бы одна единица;

5) квадратной матрицы, в каждом столбце которой находится хотя бы одна единица.

Вопрос 5. Имеются две работы r1, r2 и трое рабочих L1, L2 и L3, каждый из которых может выполнить любую работу. Элемент аij матрицы А показывает время, необходимое рабочему i для выполнения работы j:

Решите задачу о назначениях. Чему равно минимальное время выполнения двух работ?

Варианты ответов:

1) 5; 2) 6; 3) 7; 4) 8; 5) 9.

Задачи

Задача 1. Цех металлообработки получил срочный заказ на выпуск партии деталей. Для производства детали необходимо выполнить операции на четырех станках. В цехе работают четыре слесаря высокой квалификации, каждый из которых может работать на любом станке, но с различным процентом брака (процент брака известен из документации ОТК):

Распределите станки между рабочими таким образом, чтобы процент брака был минимальным. (Предполагается, что ОТК проверяет готовую деталь, т.е. общий процент брака определяется как сумма процентов брака, допущенного всеми рабочими.)

Вопросы:

1. На каком станке должен работать рабочий 2?

2. Чему равен минимальный общий процент брака?

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

В следующей таблице указан объем спроса (в млн руб.):

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

Так, представитель П1 может освоить 70\% от объема спроса в любом городе. Например, если направить его в Москву, то доход фирмы на этом рынке составит 6,3 млн руб.

Распределите торговых агентов по городам таким образом, чтобы фирма получила максимальный доход.

Вопросы:

1. Чему равен максимальный доход фирмы?

2. В какой город следует направить торгового представителя П1?

3. Кто из торговых представителей не будет использован?

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

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

Каждому программисту, которому будет поручено выполнять заказ, фирма предложила оплату 1 тыс. руб. в день. Распределите работу между программистами, чтобы общие издержки на разработку программ были минимальными.

Вопросы:

1. Чему равны минимальные издержки фирмы на выполнение всех пяти заказов?

2. Какую программу следует поручить Малкину?

3. Какую программу следует поручить Залкинду?

4. Кто из программистов не получит заказа?

5. Стало известным, что не все программисты согласились с условиями оплаты, обосновывая это тем, что имеют разную квалификацию. В результате была достигнута договоренность о следующих размерах оплаты в день (в тыс. руб.):

Изменится ли распределение работ между программистами при новых условиях оплаты труда? Каковы будут в этом случае общие минимальные издержки? б. Кто из программистов при новых условиях не получит заказа?

Задача 4. Пять учебных групп экономического факультета МГУ собираются посетить во время практики 10 предприятии и НИИ. Каждая учебная группа может посетить две организации. Путем опроса студентов выявлены предпочтения каждой группы для 10 организаций (1 означает «наиболее предпочтительна», а 10 — «наименее предпочтительна»). Предпочтения каждой из пяти учебных групп показаны в таблице (П-1 ¸ П-5 — промышленные предприятия; НИИ-1 ¸ НИИ-5 — научно-исследовательские институты):

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

Вопросы:

1. Чему равна сумма баллов, соответствующая наилучшему распределению групп по организациям?

2. Какая группа должна посетить НИИ-2?

3. Какую еще организацию должна посетить эта группа?

4. Деканат внес предложение, чтобы каждая группа посетила одно предприятие и один НИИ. Укажите теперь такой вариант распределения, чтобы каждой группе досталось по одному промышленному предприятию и одному НИИ. Чему равна сумма оценочных баллов в этом случае?

5. Какая группа должна посетить НИИ-5 при новых условиях?

6. Какую еще организацию должна посетить эта группа?

Задача 5. Самолеты компании «Аэрофлот» летают между Москвой и Сочи. Полеты беспосадочные. График движения показан в следующей таблице:

Рейсы могут обслуживаться московскими или сочинскими экипажами. Любой экипаж выполняет пару рейсов — «туда и обратно». Время, необходимое для подготовки самолета к очередному рейсу, — один час. Требуется определить, какую пару рейсов следует выполнять каждому экипажу и из какого отряда, московского или сочинского, должен быть соответствующий экипаж. Распределение рейсов необходимо осуществить таким образом, чтобы суммарное время ожидания вылета в «чужом» городе было минимальным. Время ожидания не включает тот час, который уходит на подготовку самолета к очередному рейсу.

Вопросы:

1. Верно ли, что рейс 210 должен выполняться московским экипажем?

2. Верно ли, что рейсы 240 и 160 должны выполняться одним экипажем?

3. Верно ли, что рейс 160 должен обслуживаться сочинским экипажем?

4. Каково минимальное общее время пребывания экипажей в «чужих» городах?

5. Какое количество рейсов должны выполнять московские экипажи?

Ответы и решения

Ответы на вопросы: 1—1, 2 — 2, 3—5, 4 — 3, 5 —3.

Задача 1. Решение.

Таблица задачи о назначениях представлена в условии. Проводя оптимизационные расчеты, получаем следующую матрицу назначений:

Решение можно представить в следующем виде:

Ответы:   1. На станке 4. 2. 7,9\%.

Задача 2. Решение.

Способ 1 (без проведения оптимизационных расчетов). Известно, что при любых неотрицательных а1, b1, а2, b2 соотношение а1b1 + а2b2 ³ а2b1 + а1b2 выполняется в случае, когда a1 ³ а2, и b1 ³ b2. Используя это утверждение, можно показать, что максимальный доход будет в том случае, когда торговый представитель, обеспечивающий максимальную долю освоения рынка, будет направлен в город с максимальным объемом спроса, и т.д.

Способ 2. В таблице задачи о назначениях указан размер дохода (в млн руб.), который можно получить при направлении представителя фирмы в соответствующий город:

Проводя оптимизационные расчеты, получаем следующий результат:

Ответы:   1. 17,9 млн руб. 2. В Ростов. 3. Представитель П5.

Задача 3. Решение.

В таблице задачи о назначениях указан размер оплаты (в тыс. руб.) в случае, если программисту будет поручена соответствующая программа:

Проводя расчеты, получаем следующую матрицу назначений:

Учитывая исходную информацию, получаем следующий результат:

Из последней таблицы следует, что минимальные издержки составляют 228 тыс. руб., Малкину следует поручить программу 5, а Залкинду — программу 1. Заказа не получит Галкин.

При новых условиях оплаты труда таблица задачи о назначениях имеет следующий вид:

Проводя расчеты, получаем следующую матрицу назначений:

В следующей таблице приведен итоговый результат:

Ответы:  1. 228 тыс. руб. 2. Программу 5. 3. Программу 1. 4. Программист Галкин. 5. 351 тыс. руб.

6. Программист Палкин.

Задача 4. Решение.

В таблице задачи о назначениях указаны предпочтения каждой группы, при этом каждая группа представлена дважды, так как может посетить две организации:

Проводя оптимизационные расчеты, получаем следующий результат:

Если учесть предложение деканата, то надо решить две задачи о назначениях: сначала распределить группы по предприятиям, затем — по НИИ. Эти две задачи можно представить в виде одной оптимизационной задачи, имеющей следующую таблицу (М— большое число):

Минимизируя общую сумму баллов, получаем следующую матрицу назначений:

Ответ можно представить в виде следующей таблицы:

Ответы:   1. 41. 2. Группа 3.            3. Предприятие П-5. 4. 42. 5. Группа 5. 6. Предприятие П-1.

Задача 5. Решение.

Составляем таблицу задачи о назначениях, предполагая, что все рейсы выполняются московскими экипажами. Наименование столбца таблицы — номер рейса «Москва — Сочи» (М — С). Наименование строки — номер обратного рейса «Сочи — Москва» (С — М). В таблице для каждой возможной пары рейсов, выполняемых одним экипажем, указано время ожидания вылета в Сочи (в часах):

Московский экипаж

Составляем таблицу задачи о назначениях, предполагая, что все рейсы выполняются сочинскими экипажами. Наименование строки — номер рейса «Сочи — Москва». Наименование столбца — номер обратного рейса «Москва — Сочи». В таблице для каждой возможной пары рейсов, выполняемых одним экипажем, указано время ожидания вылета в Москве (в часах):

Сочинский экипаж

Составляем итоговую таблицу задачи о назначениях. Учитываем, что каждая пара рейсов может выполняться либо московским, либо сочинским экипажем. Поэтому в итоговую таблицу включаем минимальные значения времени ожидания (в часах) из двух приведенных выше таблиц:

Элементы, выделенные полужирным шрифтом, взяты из таблицы для московского экипажа. Соответствующие пары рейсов должны выполняться московским экипажем. Элементы, выделенные курсивом, взяты из таблицы для сочинского экипажа. Соответствующие пары рейсов должны выполняться сочинским экипажем. Элементы, выделенные полужирным курсивом, показывают, что соответствующая пара рейсов может выполняться экипажем, приписанным к любому из двух городов.

Решая задачу, получаем следующую матрицу назначений:

В матрице назначений единица, выделенная полужирным шрифтом, означает, что соответствующая пара рейсов должна выполняться московским экипажем. Единица, выделенная курсивом, означает, что соответствующая пара рейсов должна выполняться сочинским экипажем.

В итоге получаем следующее решение задачи:

Ответы:  1. Нет, рейс 210 должен выполняться сочинским экипажем. 2. Да. 3. Да. 4. 9 часов. 5. Восемь рейсов.

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |