Задачи

Задача 1. Цех металлообработки получил срочный заказ на выпуск партии деталей. Для производства детали необходимо выполнить операции на четырех станках. В цехе работают четыре слесаря высокой квалификации, каждый из которых может работать на любом станке, но с различным процентом брака (процент брака известен из документации ОТК):\r\nСтанок Рабочий \'—. 1 2 3 4\r\n1 2,3 1,9 2,2 2,7\r\n2 1,8 2,2 2,0 1,8\r\n3 2,5 2,0 2,2 3,0\r\n4 2,0 2,4 2,4 2,8\r\nРаспределите станки между рабочими таким образом, чтобы процент брака был минимальным.

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

Вопросы:

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

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

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

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

в млн руб.):\r\nГород Москва Санкт-Петербург Новгород Самара Ростов\r\nОбъем спроса 9 5 4 3 6\r\n

Фирма располагает данными о профессиональных возможностях шести своих сотрудников. В следующей таблице содержатся оценки степени освоения рынка, которую может обеспечить соответствующий торговый представитель фирмы: \r\nПредставитель п\\ Щ п* Пь \r\nОценка степени освоения рынка 0,7 0,6 0,5 0,8 0,4 0,5\r\nТак, представитель П1 может освоить 70% от объема спроса в любом городе. Например, если направить

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

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

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

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

Задача 3.

Фирма получила заказы на разработку пяти программных продуктов. На фирме работают шесть квалифицированных программистов, которым можно поручить выполнение этих заказов. Каждый из них дал оценку времени (в днях), требуемого для разработки программ. Эти оценки приведены в следующей таблице: \r\n^^\\^Программа Программист^- 1 2 3 4 5\r\nГалкин 46 59 24 62 67\r\nПалкин 47 56 32 55 70\r\nМалкин 44 52 19 61 60\r\nЧалкин 47 59 17 64 73\r\nЗалкинд 43 65 20 60 75\r\nКузьмин 41 53 28 54 68\r\nВыполнение каждого из пяти заказов фирма решила поручить одному программисту. Ясно, что один из программистов не получит заказа.

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

Вопросы:

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

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

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

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

размерах оплаты в день (в тыс.

зуб.):\r\nПрограммист Размер оплаты\r\nГалкин 1\r\nПалкин 2\r\nМалкин 1,5\r\nЧалкин 2\r\nЗалкинд 1,5\r\nКузьмин 2\r\n1. Изменится ли распределение работ между программистами при новых условиях оплаты труда? Каковы будут в этом случае общие минимальные издержки? б. Кто из программистов при новых условиях не получит заказа?

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

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

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

\r\n^\\Группа Организация 1 2 3 4 5\r\nП-1 3 2 1 4 2\r\nП-2 2 5 3 3 5\r\nП-3 1 1 2 1 1\r\nП-4 4 3 5 2 3\r\nП-5 6 7 4 6 6\r\nНИИ-1 7 4 8 7 4\r\nНИИ-2 10 8 6 10 9\r\nНИИ-3 5 6 7 5 10\r\nНИИ-4 9 9 10 9 8\r\nНИИ-5 8 10 9 8 7\r\nОпределите, какие две организации должна посетить каждая группа, чтобы в максимальной степени были учтены предпочтения всех студентов.

Вопросы:

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

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

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

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

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

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

Задача 5. Самолеты компании «Аэрофлот» летают между Москвой и Сочи. Полеты беспосадочные. График движения показан в следующей таблице: \r\nРейсы из Москвы в Сочи Рейсы из Сочи в Москву\r\nНомер рейса Время от-правления Время прибытия Номер рейса Время от-правления Время прибытия\r\nПО 6:00 9:00 210 7:00 10:00\r\n120 8:00 11:00 220 10:00 13:00\r\n130 12:00 15:00 230 13:00 16:00\r\n140 15:00 17:00 240 16:00 19:00\r\n150 19:00 22:00 250 21:00 24:00\r\n160 23:00 2:00 260 0:00 3:00\r\nРейсы могут обслуживаться московскими или сочинскими экипажами. Любой экипаж выполняет пару рейсов — «туда и обратно». Время, необходимое для подготовки самолета к очередному рейсу, — один час. Требуется определить, какую пару рейсов следует выполнять каждому экипажу и из какого отряда, московского или сочинского, должен быть соответствующий экипаж. Распределение рейсов необходимо осуществить таким образом, чтобы суммарное время ожидания вылета в «чужом» городе было минимальным. Время ожидания не включает тот час, который уходит на подготовку самолета к очередному рейсу.

Вопросы:

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

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

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

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

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

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

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

Задача 1.

Решение.

Таблица задачи о назначениях представлена в условии. Проводя оптимизационные расчеты, получаем следующую матрицу назначений:\r\nСтанок 1 2 3 4\r\nРабочий ^^^ \r\n1 0 1 0 0\r\n2 0 0 0 1\r\n3 0 0 I 0\r\n4 1 0 0 0\r\nРешение можно представить в следующем виде:\r\nРабочий Станок Процент брака\r\nI 2 1,9\r\n2 4 1,8\r\n3 3 2,2\r\n4 1 2,0\r\nИтого 7,9\r\nОтветы: 1. На станке 4. 2. 7,9%.

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

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

Способ 2. В таблице задачи о назначениях указан размер дохода (в млн руб.), который можно получить при направлении п\r\nредставителя с эирмы в соответствующий город:\r\nПредста- ^\\витель Город Щ Щ Щ Я4 Щ щ\r\nМосква 6,3 5,4 4,5 7,2 3,6 4,5\r\nСанкт- Петербург 3,5 3,0 2,5 4,0 2,0 2,5\r\nНовгород 2,8 2,4 2,0 3,2 1,6 2,0\r\nСамара 2,1 1,8 1,5 2,4 1,2 1,5\r\nРостов 4,2 3,6 3,0 4,8 2,4 3,0\r\nОстается дома (в Воронеже) 0 0 0 0 0 0\r\nПроводя оптимизационные расчеты, получаем следующий результат:

\r\nГород Предста-витель Доход, млн руб.\r\nМосква п* 7,2\r\nСанкт-Петербург Щ 3\r\nНовгород Щ 2\r\nСамара Щ 1,5\r\nРостов Щ 4,2\r\nОстается дома (в Воронеже) Щ 0\r\nИтого 17,9\r\nОтветы: 1. 17,9 млн руб. 2. В Ростов. 3. Представитель П5. Задача 3. Решение.

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

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

\r\nПрограммист Программа Издержки, тыс. руб.\r\nГалкин Фиктивная 0\r\nПалкин 4 55\r\nМалкин 5 60\r\nЧалкин 3 17\r\nЗалкинд 1 43\r\nКузьмин 2 53\r\nИтого 228\r\nИз последней таблицы следует, что минимальные издержки составляют 228 тыс. руб., Малкину следует

поручить программу 5, а Залкинду — программу 1. Заказа не получит Галкин. При новых условиях оплаты труда таблица задачи о назначениях имеет следующий вид:\r\n^"¦^ТТрограмма Программист^^. 1 2 3 4 5 6

(фиктивная)\r\nГалкин 46 59 24 62 67 0\r\nПалкин 94 112 64 110 140 0\r\nМалкин 66 78 28,5 91,5 90 0\r\nЧалкин 94 118 34 128 146 0\r\nЗалкинд 64,5 97,5 30 90 112,5 0\r\nКузьмин 82 106 56 108 136 0\r\nПроводя расчеты, получаем следующую матрицу назначений:

(фиктивная)\r\nГалкин 0 0 0 0 1 0\r\nПалкин 0 0 0 0 0 1\r\nМалкин 0 1 0 0 0 0\r\nЧалкин 0 0 1 0 0 0\r\nЗалкинд 0 0 0 1 0 0\r\nКузьмин 1 0 0 0 0 0\r\nВ следующей таблице приведен итоговый результат:\r\nПрограммист Программа Издержки, тыс. руб.\r\nГалкин 5 67\r\nПалкин Фиктивная 0\r\nМалкин 2 78\r\nЧалкин 3 34\r\nЗалкинд 4 90\r\nКузьмин 1 82\r\nИтого 351\r\nОтветы: 1. 228 тыс. руб. 2. Программу 5. 3. Программу 1. 4. Программист Галкин. 5. 351 тыс. руб. 6. Программист Палкин. Задача 4. Решение.

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

низация х. 1 2 3 4 5 1 2 3 4 5\r\nП-1 3 2 1 4 2 3 2 1 4 2\r\nП-2 2 5 3 3 5 2 5 3 3 5\r\nП-3 1 1 2 1 1 1 1 2 1 1\r\nП-4 4 3 5 2 3 4 3 5 2 3\r\nП-5 6 7 4 6 6 6 7 4 6 6\r\nНИИ-1 7 4 8 7 4 7 4 8 7 4\r\nНИИ-2 10 8 6 10 9 10 8 6 10 9\r\nНИИ-3 5 6 7 5 10 5 6 7 5 10\r\nНИИ-4 9 9 10 9 8 9 9 10 9 8\r\nНИИ-5 8 10 9 8 7 8 10 9 8 7\r\nПроводя оптимизационные расчеты, получаем следующий результат:

\r\nОрганизация Группа Оценочный балл\r\nП-1 2 2\r\nП-2 1 2\r\nП-3 1 1\r\nП-4 4 2\r\nП-5 3 4\r\nНИИ-1 2 4\r\nНИИ-2 3 6\r\nНИИ-3 4 5\r\nНИИ-4 5 8\r\nНИИ-5 5 7\r\nИтого 41\r\nЕсли учесть предложение деканата, то надо решить две задачи о назначениях: сначала распределить группы по предприятиям, затем — по НИИ.

Opra^N. низация^ч. 1 2 3 4 5 1 2 3 4 5\r\nП-1 0 0 0 0 1 0 0 0 , 0 0\r\nП-2 1 0 0 0 0 0 0 0 0 0\r\nП-3 0 1 0 0 0 0 0 0 0 0\r\nП-4 0 0 0 1 0 0 0 0 0 0\r\nП-5 0 0 1 0 0 0 0 0 0 0\r\nНИИ-1 0 0 0 0 0 0 1 0 0 О\r\nНИИ-2 0 0 0 0 0 0 0 1 0 0\r\nНИИ-3 0 0 0 0 0 0 0 0 1 0\r\nНИИ-4 \' 0 0 0 0 0 1 0 0 0 0\r\nНИИ-5 0 0 0 0 0 0 0 0 0 1\r\nОтвет можно представить в виде следующей таблицы:

\r\nОрганизация Группа Оценочный балл\r\nП-1 5 2\r\nП-2 1 2\r\nП-3 2 1\r\nП-4 4 2\r\nП-5 3 4\r\nНИИ-1 2 4\r\nНИИ-2 3 6\r\nНИИ-3 4 5\r\nНИИ-4 1 9\r\nНИИ-5 5 7\r\nИтого 42\r\nОтветы: 1. 41. 2. Группа 3. 3. Предприятие П-5. 4. 42. 5. Группа 5. 6. Предприятие П-1.

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

Московский экипаж\r\nС-МХ^ 110 120 130 140 150 160\r\n210 21 19 15 13 8 4\r\n220 0 22 18 16 11 7\r\n230 3 1 21 19 14 10\r\n240 6 4 0 22 17 13\r\n250 11 9 5 3 22 18\r\n260 14 12 8 6 1 21\r\nСоставляем таблицу задачи о назначениях, предполагая, что все рейсы выполняются сочинскими экипажами. Наименование строки — номер рейса «Сочи — Москва». Наименование столбца — номер обратного рейса «Москва — Сочи». В таблице для каждой возможной пары рейсов, выполняемых одним экипажем, указано время ожидания вылета в Москве (в часах):

Сочинский экипаж\r\nМ-С 110 120 130 140 150 160\r\n210 19 21 1 4 8 12\r\n220 16 18 22 1 5 9\r\n230 13 15 19 22 2 6\r\n240 10 12 16 19 23 3\r\n250 5 7 11 14 18 22\r\n260 2 4 8 11 15 19\r\nСоставляем итоговую таблицу задачи о назначениях. Учитываем, что каждая пара рейсов может выполняться либо московским, либо сочинским экипажем. Поэтому в итоговую таблицу включаем минимальные значения времени ожидания (в часах) из двух приведенных выше таблиц:

\r\n^Чм-с 110 120 130 140 150 160\r\n210 19 19 1 4 8 4\r\n220 0 18 18 1 5 7\r\n230 3 I 19 19 2 6\r\n240 6 4 0 19 17 3\r\n250 5 7 5 3 18 18\r\n260 2 4 8 6 1 19\r\nЭлементы, выделенные полужирным шрифтом, взяты из таблицы для московского экипажа. Соответствующие пары рейсов должны выполняться московским экипажем. Элементы, выделенные курсивом, взяты из таблицы для сочинского экипажа. Соответствующие пары рейсов должны выполняться сочинским экипажем. Элементы, выделенные полужирным курсивом, показывают, что соответствующая пара рейсов может выполняться экипажем, приписанным к любому из двух городов.

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

С-М 110 120 130 140 150 160\r\n210 0 0 1 0 0 0\r\n220 1 0 0 0 0 0\r\n230 0 1 0 0 0 0\r\n240 0 0 0 0 0 1\r\n250 0 0 0 1 0 0\r\n260 0 0 0 0 1 0\r\nВ матрице назначений единица, выделенная полужирным шрифтом, означает, что соответствующая пара рейсов должна выполняться московским экипажем. Единица, выделенная курсивом, означает, что соответствующая пара рейсов должна выполняться сочинским экипажем. В итоге получаем следующее\r\n)ешение задачи:\r\nРейс Время ожидания, ч Экипаж\r\n210 130 1 Сочинский\r\n220 110 0 Московский\r\n230 120 1 Московский\r\n240 160 3 Сочинский\r\n250 140 3 Московский\r\n260 150 1 Московский\r\nИтого 9 \r\nОтветы: 1. Нет, рейс 210 должен выполняться сочинским экипажем. 2. Да. 3. Да. 4. 9 часов. 5. Восемь рейсов.

Задачи

Еще по теме Задачи: