Пятерым следователям 
нужно поручить расследование пяти уголовных дел 
. В силу разной квалификации на завершение расследования им потребуется различное время. Время выполнения (в сутках) приведено в таблице. Как следует распределить следователей прокуратуры по заданиям, чтобы минимизировать время выполнения?
| Люди | Задания | ||||
| 
| 
| 
| 
| |
| |||||
| |||||
| |||||
| |||||
|
Указания:
К задачам целочисленного (дискретного) программированием относятся задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Это продиктовано физической неделимостью многих элементов расчета (например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д.). В таких задачах переменные могут принимать только два значения – единица и нуль.
Пусть 
– время участия i человека в выполнении j -го задания. Все величины – неотрицательны, и, поскольку каждый человек должен быть полностью задействован, а каждое задание полностью выполнено, величины должны удовлетворять следующим ограничениям:
При этих ограничениях минимизируется полное время
Таким образом, получилась задача линейного программирования транспортного типа. Все суммы по строкам и по столбцам равны 1. Поскольку задача транспортная, в ее оптимальном решении (целочисленном) пять из величин будут равны 1, а остальные – 0. Далее задача решается стандартными средствами Excel.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задание 2.1.
Для изготовления трех видов изделий А,В,С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в таблицах. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия данного вида.
Требуется определить, сколько и какого вида изделий следует изготовить предприятию, чтобы прибыль от их реализации была максимальной.
| Тип оборудования | Затраты времени (станко-ч) на обработку одного изделия вида | Общий фонд рабочего времени оборудования (ч) | ||
| А | В | С | ||
| Фрезерное | ||||
| Токарное | ||||
| Сварочное | ||||
| Шлифовальное | ||||
| Прибыль |
Задание 2.2.
Продукцией городского молочного завода являются молоко, кефир и сметана. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-ч. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 ч., а автоматы по расфасовке сметаны – в течении 16,25 ч. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в пакеты. На производство другой продукции не имеется никаких ограничений.
Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной.
Задание 2.3.
Кондитерская фабрика для производства трех видов карамели А,В,С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство 1 т карамели данного вида приведены в таблице.
В ней же указано обще количество сырья каждого вида, которое может быть использовано фабрикой, а также приведена прибыль от реализации 1 т карамели данного вида.
| Вид сырья | Нормы расхода сырья (т) на 1 т карамели | Общее количество сырья (т) | ||
| А | В | С | ||
| Сахарный песок | 0,8 | 0,5 | 0,6 | |
| Патока | 0,4 | 0,4 | 0,3 | |
| Фруктовое пюре | 0,1 | 0,1 | ||
| Прибыль (руб.) |
Найти план производства карамели обеспечивающий максимальную прибыль от ее реализации.
Задание 2.4.
Компания производит полки двух размеров – А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В – 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В – 30 мин. ЭВМ можно использовать 160 ч в неделю. Если прибыль от продажи полок типа А составляет 3 дол., а от полок типа В – 4 дол., то сколько полок каждого типа следует выпускать в неделю.
Задание 2.5.
Автозавод выпускает две модели: «Каприз» и «Фиаско». На заводе работает 1000 неквалифицированных и 800 квалифицированных рабочих, каждому из которых оплачивается 40 ч в неделю. Для изготовления модели «Каприз» требуется 30 ч неквалифицированного и 50 ч квалифицированного труда; для «Фиаско» требуется 40 ч неквалифицированного и 20 ч квалифицированного труда. Каждая модель «Фиаско» требует затрат в размере 500 дол. на сырье и комплектующие изделия, тогда как каждая модель «Каприз» требует затрат в размере 1500 дол.; суммарные затраты не должны превосходить 900 000 дол. в неделю. Рабочие, осуществляющие доставку, работают по пять дней в неделю и могут забрать с завода не более 210 машин в день.
Каждая модель «Каприз» приносит фирме 1000 дол. прибыли, а каждая модель «Фиаско» – 500 дол. прибыли. Какой объем выпуска каждой модели вы бы порекомендовали? Что бы вы порекомендовали для повышения прибыли фирмы?
Задание 2.6.
Заводы фирмы расположены в городах Лидсе и Кардиффе; они доставляют товары на склады городов Манчестер, Бирмингем и Лондон. Расстояния между этими городами приведены в таблице.
Завод в г. Лидсе выпускает в год 800 т товаров, а в г. Кардиффе – 500 т. Манчестерский склад вмещает 400 т, бирмингемский – 600 т, а лондонский – 300 т. Как следует транспонировать товары для минимизации цен на перевозки.
| Манчестер | Бирмингем | Лондон | |
| Лидс | |||
| Кардифф |
Стоимость перевозки составляет 2 дол за километр.
Задание 2.7.
Фирма занимается составлением диеты, содержащей по крайней мере 20 единиц белков, 30 единиц углеводов, 10 единиц жиров и 40 единиц витаминов. Как дешевле всего достичь этого при указанных в таблице ценах на 1 кг (или 1 л) пяти имеющихся продуктов?
| Хлеб | Соя | Сушеная рыба | Фрукты | Молоко | |
| Белки | |||||
| Углеводы | |||||
| Жиры | |||||
| Витамины | |||||
| Цена |
Задание 2.8.
Небольшая фирма производит два вида продукции, столы и стулья. Для изготовления одного стула требуется 3 фута древесины, а для изготовления одного стола — 7 футов. На изготовление одного стула уходит 2 ч. рабочего времени, а на изготовление стола — 8 ч. Каждый стул приносит 1 дол. прибыли, а каждый стол — 3 дол. Сколько стульев и сколько столов должна изготовить эта фирма, если она располагает 420 футами древесины и 400 ч. рабочего времени и хочет получить максимальную прибыль?
Задание 2.9.
У фермера есть 400 акров земли, он планирует посеять зерно и соевые бобы. Засеять каждый акр зерна и собрать с него урожай стоит 200 дол., а засеять и собрать урожай с каждого акра соевых бобов – 100 дол. Фермер получил заем в 60 тыс. долларов для того, чтобы покрыть затраты. Каждый акр зерна принесет 30 бушелей зерна, а каждый акр соевых бобов — 60 бушелей. Фермер обязался продавать зерно и соевые бобы по 3 и по 6 дол. за бушель, соответственно. Однако фермеру нужно хранить в амбаре зерно и соевые бобы в течение нескольких месяцев после сбора урожая. Амбар максимум вмещает 21 тыс. бушелей. Фермер хочет знать, сколько акров каждой культуры нужно засеять, чтобы прибыль была наибольшей.
Задание 2.10.
Фирма, изготовляющая деревянную продукцию, производит два вида обшивочных панелей: колониальную и западную. Производство панелей осуществляется двумя операциями: прессованием и отделкой. Задача администрации фирмы — узнать, сколько пластов обоих типов обшивочной панели нужно производить в месяц, чтобы получить максимальную прибыль.
Проблема в том, что продукция панелей ограничена — фирма ограничена средствами для производства продуктов. Задача состоит в оптимальном размещении средств для получения наибольшей прибыли.
Фирма обладает ресурсами в условиях доступности леса, имеется достаточно рабочих часов для прессования и обработки, а также долларовый бюджет.
Ресурсные потребности и возможности для каждого типа панелей, которые образовывают параметры модели, смотрите в таблице.
| Необходимые средства для партии из 100 пластов обшивочной панели | Всего средств в месяц | ||
| Средства | Колониальные | Западные | |
| Деревянная продукция | 20 кг | 40 кг | 4000 кг |
| Прессование | 4 ч. | 6ч. | 900 ч. |
| Отделка | 4 ч. | 4 ч. | 600 ч. |
| Стоимость | $ 30 | $ 50 | $ 6000 |
Фирма получает 80 дол. прибыли за каждые 100 пластов колониальной панели и 100 дол. – за каждые 100 пластов западной панели.
Задание 2.11.
В трех пунктах отправления сосредоточен однородный груз в количествах, равных 420, 380 и 400 т. Этот груз необходимо перевезти в три пункта назначения в количествах, соответственно равных 260, 520 и 420 т. Тарифы перевозок 1 т груза из каждого пункта отправления в каждый пункт назначения являются известными величинами и задаются матрицей
Найти план перевозок, обеспечивающий вывоз имеющегося в пунктах отправления и завоз необходимого в пунктах назначения груза при минимальной общей стоимости перевозок.
Задание 2.12.
Четыре предприятия для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей
Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.
Задание 2.13.
На трех складах оптовой базы сосредоточен однородный груз в количествах 90, 60 и 150 ед. Этот груз необходимо перевезти в четыре магазина. Каждый из магазинов должен получить соответственно 120, 40, 60 и 80 ед. груза. Тарифы перевозок единицы груза из каждого из складов во все магазины задаются матрицей
Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.
Задание 2.14.
Производственное объединение имеет в своем составе три филиала, которые производят однородную продукцию соответственно в количествах, равных 50, 30 и 10 ед. Эту продукцию получают четыре потребителя, расположенные в разных местах. Их потребности соответственно равны 30, 30, 10 и 20 ед. Тарифы перевозок единицы продукции от каждого из филиалов соответствующим потребителям задаются матрицей
Составить такой план прикрепления получателей продукции к ее поставщикам, при котором общая стоимость перевозок является минимальной.
Задание 2.15.
Три предприятия могут производить некоторую однородную продукцию в количествах, соответственно равных 180, 350 и 20 ед. Эта продукция должна быть поставлена пяти потребителям в количествах, соответственно равных 110, 90, 120, 80 и 150 ед. Затраты, связанные с производством и доставкой единицы продукции, задаются матрицей
Составить такой план прикрепления потребителей к поставщикам, при котором общие затраты являются минимальными.
Задание 2.16.
Для строительства трех дорог используется гравий из четырех карьеров. Запасы гравия в каждом из карьеров соответственно равны 120, 280 и 160 усл.ед. Потребности в гравии для строительства каждой из дорог соответственно равны 130, 220, 60 и 70 усл.ед. Известны также тарифы перевозок 1 усл.ед. гравия из каждого из карьеров к каждой из строящихся дорог, которые задаются матрицей
Составить такой план перевозок гравия, при котором потребности в нем каждой из строящихся дорог были удовлетворены при наименьшей общей стоимости перевозок.
Задание 2.17.
Для строительства четырех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 50 усл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны 75, 80, 60 и 85 усл.ед. Известны также тарифы перевозок 1 усл.ед. кирпича с каждого с заводов к каждому из строящихся объектов:
Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной.
Задание 2.18.
На трех хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, потребности которых равны соответственно 80, 60, 170 и 80 т. Тарифы перевозок 1 т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей
Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.
Задание 2.19.
В трех хранилищах горючего ежедневно хранится 175, 125 и 140 т бензина. Этот бензин ежедневно получают четыре заправочные станции в количествах, равных соответственно 180, 110, 60 и 40 т. Тарифы перевозок 1 т бензина с хранилищ к заправочным станциям задаются матрицей
Составить такой план перевозок бензина, при котором общая стоимость перевозок является минимальной.
Задание 2.20.
Компания имеет два товарных склада (А1 и А2) и трех оптовых покупателей (Bl, B2, ВЗ). Известно, что общий объем запасов на складах составляет 300 тыс. единиц продукции и совпадает с общим объемом заказов покупателей. Конкретные данные о загруженности каждого из складов (в тыс. ед.), потребности каждого покупателя (в тыс. ед.) и стоимости перевозки (тыс. руб./тыс. ед.) приведены в таблице. Минимизируйте общую стоимость перевозок.
| Стоимость перевозок к потребителям | Наличие | ||||
| В1 | В2 | ВЗ | |||
| Склады | А1 | ||||
| А2 | |||||
| Запрос |
Задание 2.21.
Два торговых склада поставляют продукцию в четыре магазина. Издержки транспортировки продукции с торговых складов в магазины, наличие продукции на складах и потребности магазинов приведены в таблице.
| Стоимость перевозок к потребителям | Наличие | |||||
| В1 | В2 | ВЗ | В4 | |||
| Склады | А1 | |||||
| А2 | ||||||
| Запрос |
Минимизируйте общую стоимость перевозок.
Задание 2.22.
Предположим, что нужно перевезти весь груз с трех складов в два пункта, причем весь груз должен быть перевезен во все пункты. В первый пункт должно быть перевезено 45 единиц груза, во второй — 79. На складах груз распределен следующим образом: на первом — 18, на втором — 75, на третьем — 31. Стоимость перевозки единицы груза со склада в пункт определяется таблице.
| Пункт 1 | Пункт 2 | |
| Склад 1 | ||
| Склад 2 | ||
| Склад 3 |
Требуется определить такую организацию перевозок, чтобы затраты на них были минимальными.