Задача о водопроводчике

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

Пронумеруем плиты от 1 до 12. Пусть x _i = 0, если выбранное решение состоит в том, чтобы не приподнимать i - ю плиту, x _i = 1, если принимается решение приподнять i - ю плиту ( ). Каждой трубе соответствует одно ограничение, которое означает, что для получения к ней доступа необходимо приподнять, по крайней мере, одну из плит.

Математическая модель задачи выглядит следующим образом:

при условиях: . (1.74)

Эта задача попадает в класс так называемых задач о «покрытии множества», для которого характерны разнообразные практические приложения.

1	2	3	4
5	6	7	8
9	10	11	12

Рис 1.3

Пример 1.11. Стохастические модели

Задача о загрузке судна запасными деталями

Пусть рассматривается три типа запасных деталей, имеющих объемы 1, 2, и 2 единицы. Общий объем склада равен 10 единицам. Штрафные затраты  _j , возникающие при неудовлетворении потребности, равны соответствен-но 800, 600, и 1300. Будем предполагать, что спрос _j на каждую из запасных деталей подчинен пуассоновскому распределению со средними значениями  _j = (4; 2; 1). Соответственно требуется определить, каким должен быть запас деталей каждого типа, чтобы средние штрафные издержки были минимальными. В математической формулировке мы приходим к следующей модели:

найти

(1.75)

при условиях: x_j  0, целые, j = 1, 2, 3;

x₁ + 2x₂ + 2x₃  10,

где     x_j – запасы деталей j-го типа.

     Выражение   (1.76)

в функции (1.75) представляет собой вероятность случайной величины _j, подчиненной закону Пуассона, а  _j есть ожидаемая средняя потребность в деталях j -го типа: .

Из (1.76) следует, что

. (1.77)

Таким образом, можно записать:

, (1.78)

где .

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

Задачи

1. Диспетчерская служба имеет следующие минимальные потребности в количестве диспетчеров в различное время суток (табл. 1.6):

Таблица 1.6

Порядковый номер периода	1	2	3	4	5	6
Время суток час.	2 – 6	6 – 10	10 – 14	14 – 18	18 –22	22 – 2
Минимальное число диспетчеров, требуемое в указанный период	20	50	80	100	40	30

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

2. В обработку поступили две партии досок для изготовления комплектов из трех деталей, причем первая партия содержит 50 досок длиной по 6,5 м, вторая содержит 200 досок длиной 4 м. Каждый комплект состоит из двух деталей по 2 м каждая и одной детали по 1,25 м. Как распилить доски, чтобы получить наибольшее число комплектов?

2. На заводе предстоит решить, какое количество х₁ чистой стали и какое количество х₂ металлолома следует использовать для приготовления (из соответствующего сплава) литья для одного из своих заказчиков. Пусть производственные затраты на 1 т стали составляют 3 усл. ед., а затраты на 1 т металлолома 5 усл. ед. (последняя цифра больше предыдущей, т.к. использование металлолома связано с его предварительной очисткой).

Заказ предусматривает поставку не менее 5 т литья. Предположим, что предназначенные для литья запасы чистой стали составляют 4 т, а металлолома – 6 т. Отношение веса металлолома к весу чистой стали в сплаве не должно превышать 7/8.

Производственно-технологические условия таковы, что на процессы плавки и литья может быть отведено не более 18 час., при этом на 1 т стали затрачивается от 2,5 до 3 час., а на 1т металлолома от 1,5 до 2 час.

Цель завода – выполнить заказ с минимальными производственными затратами.

4. Предприятие выпускает радиоприемники трех различных моделей: модель А, модель В и модель С. Каждое изделие указанных моделей приносит доход в размере 8, 15, 25 единиц стоимости соответственно. Необходимо, чтобы фирма выпускала не менее 100 приемников модели А, 150 приемников модели В и 75 приемников модели С.

Каждая модель характеризуется определенным временем, необходимым для изготовления соответствующих деталей, сборки изделия и его упаковки. Так, в частности, в расчете на 10 приемников модели А требуется 3 ч. для изготовления соответствующих деталей, 4 ч. на сборку и 1 ч. на упаковку. Соответствующие показатели на 10 приемников модели В равняются 3; 5, 5 и 1,5 ч., а на 10 приемников модели С – 5, 8 и 3.

В течение ближайшей недели фирма может израсходовать на производство – 150 ч., на сборку – 200 ч. и на упаковку – 60 ч.

Составить производственный план.

5. На предприятии требуется произвести раскрой рулона материала шириной 60 см. Мастер сообщил следующие данные о заказах текущей недели:

Требуемая ширина (см)	28	20	15
Требуемое количество рулонов	30	60	48

Предполагается, что количество рулонов с шириной 60 см достаточно для того, чтобы удовлетворить все недельные заказы. Найти план раскроя, минимизирующий общие суммарные потери.

6. В небольшом населенном пункте А имеется школа, которую посещает некоторое число учеников, при этом место жительства 72 учеников находится вне населенного пункта, что приводит к необходимости организовать их доставку к школе на автобусах. Имеются две основные автобусные остановки В, С (В находится между А и С). Число учеников, нуждающихся в доставке к школе на автобусе равняется 42 на остановке С, 6 – между С и В, 20 на остановке В и 4 – между В и А (рис.1.4).

А (4) В (20) (6) С (42)

Рис. 1.4

Транспортное агентство, обслуживающее пункт А, располагает двумя типами автобусов: автобусы на 35 и 50 мест.

Транспортным агентством установлены следующие цены проездных билетов для каждого из отрезков пути в зависимости от типа автобуса:

Отрезок пути	ВА	СА	СВ
35 мест	39,0	54,0	45,0
50 мест	50,5	68,0	57,5

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

7. Определить максимальный поток f из пункта О в пункт М при ограниченной пропускной способности путей. Граф путей представлен на рис 1.5.

Числа над дугами графа определяют верхнюю границу потока на соответствующих путях.

8. Информация о проекте задана перечнем работ, их продолжительностью и последовательностью выполнения (табл. 1.7):

Таблица 1.7

Работа	1	2	3	4	5	6	7	8
Каким работам предшествует	4, 5, 6	4, 5, 6	5, 6	8	8	7	8	–
Продолжительность мес.	20	10	8	20	10	5	5	10

В i - ю работу можно вложить средства, где x_i  c_i , при этом время выполнения работы уменьшится до  _i ( 1 - b_i x_i ).

Пусть: b₁ = 0.2, c₁ = 2, b₄ = 0.3, c₄ = 2, b₈ = 0.1, c₈ = 5.

Определить размер вложенных средств x₁ , x₄ , x₈ в 1-ю, 4-ю, 8-ю работы так, чтобы время завершения всего комплекса работ не превышало 40 месяцев.

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

9. Участник экспедиции укладывает рюкзак, и ему требуется решить, какие положить продукты. В его распоряжении имеются мясо, мука, сухое молоко и сахар. В рюкзаке для продуктов осталось лишь 45 дм³ объема, и нужно, чтобы суммарная масса продуктов не превосходила 35 кг. Врач экспедиции рекомендовал, чтобы мяса (по массе) было больше муки по крайней мере в два раза, муки не меньше молока, а молока по крайней мере в восемь раз больше, чем сахара. Сколько и каких продуктов нужно положить в рюкзак, с тем, чтобы суммарная калорийность продуктов была наибольшей? Характеристики продуктов приведены в табл. 1.8.

Таблица 1.8

Характеристики	Продукты
	Мясо	Мука	Молоко	Сахар
Объем (дм^3/кг)	1	1.5	2	1
Калорийность (ккал/кг)	1500	5000	5000	4000

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

Предположим, что вся требуемая информация хранится в n массивах. Примем, что  _j ( j = 1, 2, ..., n) – время поиска ЭВМ нужной информации в массиве j и что время поиска не зависит от числа характеристик, выбираемых из массива. Некоторые из m видов данных записаны более чем в одном из n массивов, т.е. различные массивы содержат информацию, относящуюся к одной и той же характеристике. Расположение информации задано матрицей , где , если данные по i -ой характеристике записаны в j -ом массиве и в противном случае.

10	12	9	11	14

,    

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

б) Объясните, как следует изменить модель, если время поиска в массиве j равно плюс t _{i j} в случае, когда в результате поиска получают характеристику с индексом i . Соответствующие данные по значениям t _{i j} приводятся в матрице .

11. Для производства комплексной продукции требуется изготовить два вида изделий. Их изготовление может быть поставлено на каждом из пяти типов предприятий. Производственная мощность предприятия и количество предприятий каждого типа даны в табл. 1.9.

Таблица 1.9

Тип предприятия	Число предприятий	Производственная мощность
		По изделиям № 1 (тыс.)	По изделиям № 2 (тыс.)
№ 1	5	100	15
№ 2	3	400	200
№ 3	40	20	2,5
№ 4	9	200	50
№ 5	2	600	250

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

12. На мебельной фабрике требуется раскроить 5000 прямоугольных листов фанеры размером 4 х 5 м каждый с тем, чтобы получить два вида прямоугольных деталей: деталь А должна иметь размер 2 х 2 м, деталь Б – размер 1х 3 м. Необходимо, чтобы деталей А оказалось не меньше, чем деталей Б. Каким образом следует произвести раскрой, чтобы получить минимальное (по площади) количество отходов?

13. Построить математическую модель для выбора расписания при следующих условиях:

• задан состав операций: а₁ , а₂ , ..., а₁₀ ;

• заданы временные функции: t₁ , t₂ , ..., t₁₀ ;

• заданы ограничения на порядок следования: а₁ а₂ , а₈ а₅ , а₇ а₈ ;

• некоторые операции нельзя выполнять

• одновременно: ( а₁ и а₂ ), ( а₅ и а₇ ) ;

• целевая функция – минимизация общей длительности.

14. (241). Для строительства домов на 100 строительных площадках выбраны 5 типовых проектов. По каждому из проектов известны длительность закладки фундаментов, возведения стен и крыш, отделка, а также жилая площадь дома. Возможно, исходя из трудовых, сырьевых и технических ресурсов одновременное ведение закладки 10 фундаментов и строительства и отделки 15 зданий (см. табл. 1.10).

Таблица 1.10

Вид работ	Длительность ведения работ (дни)
	I	II	III	IV	V
Закладка фундамента	20	30	35	30	40
Строительство	30	15	40	25	15
Отделка	10	5	20	10	10
Жилая площадь м^2	3000	2000	5000	4000	6000

Составить план строительства, максимизирующий ввод жилой площади в течение года (300 рабочих дней) при условии, что домов II типа должно быть построено не меньше 10.

15. Автозавод выпускает две модели автомобилей: модель А и более дешевую модель В. На заводе работает 1000 неквалифицированных и 800 квалифицированных рабочих, каждому из которых оплачивается 40 часов в неделю. Для выпуска модели А требуется 30 ч. неквалифицированного и 50 ч. квалифицированного труда. Для модели В – 40 ч. и 20 ч. cоответ-ственно.

Каждая из моделей требует затрат на сырье в размере 500 руб. и 1500 руб. Суммарные затраты не должны превышать 900 000 руб. в неделю. Рабочие, осуществляюшие доставку, работают по 5 дней в неделю и могут забрать с завода не более 210 машин в день. Каждая модель А ( В ) приносит прибыль 1000 (500) руб.

Каким должен быть объем выпуска каждой модели?

16. Фирма производит 2 модели А и В сборных книжных полок. Их производство ограничено наличием сырья (досок) и временем машинной обработки. Для каждого изделия А требуется 3 м² досок, для В – 4 м². Фабрика может получить от поставщиков 1700 м² досок в неделю. Для каждого изделия А ( В ) требуется 12 (30) мин. машинного времени. В неделю можно использовать не более 160 ч. машинного времени. Определить план недельного выпуска, максимизирующий прибыль, если изделие А ( В ) приносит денежную прибыль 2 (4) усл. един.

16. В некоторой местности в пунктах А и В имеются потребности в дополнительном транспорте. В пункте А требуется 5 дополнительных автобусов, в пункте В – 7. Известно, что 3, 4, 5 автобусов соответственно могут быть получены из гаражей G₁ , G₂ , G₃ .

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

Таблица 1.11

Гараж	Расстояние до пунктов
	А	В
G1	3	4
G2	1	3
G3	4	2

18. Фирма производит два продукта А и В, продаваемых соответственно по 8 и по 15 руб. за упаковку. Рынок сбыта для каждого из них не ограничен.

Продукт А обрабатывается на машине 1, продукт В – на машине 2, затем оба упаковываются на фабрике. 1 кг сырья стоит 6 копеек. Машина 1 (2) обрабатывает 5000 (4000) кг сырья в час с потерями 10 % (20 %). Машина 1 (2) работает 6 (5) часов в день, ее использование стоит 288 (336) руб./час. Упаковка продукта А (В) весит 1/4 (1/3) кг. Фабрика может работать 10 час. в день, производя в 1 час продукцию стоимостью 360 руб. За 1 час можно упаковать 12 000 продуктов А и 8 000 продуктов В.

Компания хочет определить такие значения х₁ и х₂ потребления сырья для продуктов А и В (в тыс. кг), при которых дневная прибыль максимальна.

19. Для обеспечения автоперевозок в j -й день недели требуется a _j автомашин. Машины после поездки должны пройти профилактический ремонт. Обычный ремонт длится 4 дня при затратах 20 руб. на машину, срочный ремонт длится 2 дня при затратах 30 руб. на машину. Кроме того, можно использовать машины для перевозок, сняв их с другого участка, что приводит к потерям 50 руб. на машину. Определить оптимальную недельную программу подготовки машин, минимизирующую суммарные затраты автобазы, если потребность в машинах характеризуется следующими данными (табл. 1.12). Для решения использовать пример задачи о поставщике.

Таблица 1.12

Дни недели	1	2	3	4	5	6	7
aj	50	40	70	60	80	40	50