Задачи ЦЛП

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

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

Категория	Кандидатуры
Женщины	a, b, c, d, e
Мужчины	f, g, h, i, j
Студенты	a, b, c, j
Администраторы	e, f
Преподаватели	d, g, h, i

Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой из указанных категорий. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение.

23. Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех шести городах. Однако в силу территориальной близости некоторых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки; оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами.

	1	2	3	4	5	6
1	0	23	14	18	10	32
2	23	0	24	13	22	11
3	14	24	0	60	19	20
4	18	13	60	0	55	17
5	10	22	19	55	0	12
6	32	11	20	17	12	0

Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, в котором определите наименьшее количество станций и их расположение.

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

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

Ресурсы	Запас ресурса	Затраты ресурсов на одну пару обуви по моделям
		№1	№2	№3	№4
Рабочее время, чел.-ч Кожа 1-го сорта Кожа 2-го сорта	1000 500 1200	1 2 0	2 1 1	2 0 4	1 0 1
Прибыль, ден. ед.		2	40	10	15

26. Мебельная фабрика может выпускать стулья двух типов ценой в 8 и 12 ден. ед. Наличие и удельный расход материальных и трудовых ресурсов, необходимых для изготовления каждого типа стула, приведены в таблице. Необходимо составить оптимальный план производства стульев, максимизирующий их суммарную стоимость.

Стул	Расход досок, м	Расход ткани, м2	Расход времени, чел.-час.
1	2	0,5	2
2	4	0,25	2,5
Ресурс	490	65	325

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

Стройматериалы	Расход стройматериалов (м3) на один дом		Запас строй- материалов, м3
	1 проекта	2 проекта
Кирпич силикатный Кирпич красный Пиломатериалы	7 6 1	3 3 2	1365 1245 650
Полезная площадь, м2	60	50

28. Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа — 3 т, проволоки — 18 т. На один трансформатор первого вида расходуются 5 кг железа и З кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 ден. ед., второго — 4 ден. ед. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль.

29. Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда данные об организации перевозок следующие:

Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?

Поезда	Количество вагонов в поезде
Багажный	Почто- вый	Плац- карт	Купей- ный	Мяг- кий
Скорый	1	1	5	6	3
Пассажирский	1	-	8	4	1
Число пассажиров	-	-	58	40	32
Парк вагонов	12	8	31	70	26

30. Чулочно-носочная фирма производит и продает два вида товаров: мужские носки и женские чулки. Фирма получает прибыль в размере 10 ден.ед. от производства и продажи одной пары чулок и в размере 4 ден.ед. от производства и продажи одной пары носков. Производство каждого изделия осуществляется на трех участках. Затраты труда (в часах) на производство одной пары указаны в следующей таблице для каждого участка.

Участок производства	Чулки	Носки
1 2 3	0,02 0,03 0,03	0,01 0,01 0,02

Руководство рассчитало, что в следующем месяце фирма ежедневно будет располагать следующими ресурсами рабочего времени на каждом из участков:

60 ч на участке 1;

70 ч на участке 2;

100 ч на участке 3.

Какое количество продукции каждого вида следует ежедневно производить предприятию, чтобы получить максимальную прибыль?

31. Для приобретения оборудования по сортировке зерна фермер выделяет 20000 ден.ед. Оборудование должно быть размещено на площади не превышающей 72 кв. м. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 2000 ден.ед., требующие производственную площадь 12 кв.м (с учетом проходов) и обеспечивающие производительность за смену 6 т зерна, и более мощные машины типа В стоимостью 5000 ден.ед., занимающие площадь 6 кв.м и обеспечивающие производительность за смену 8 т сортового зерна. Машин типа В можно заказать не более 3 ед. Определить оптимальный план приобретения оборудования обеспечивающий максимальную производительность участка.

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

Категория	Кандидатуры
Женщины	a, b, c, d, e
Мужчины	f, g, h, i, j
Студенты	a, b, c, j
Администраторы	e, f
Преподаватели	d, g, h, i

Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой из указанных категорий. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение.

33. Компания Хогсо Ноте Cosmetics начинает продвижение своих товаров на рынок региона, находящегося на юге штата Юта и состоящего из шести округов. Ниже схематически показана карта, на которой представлено относительное расположение округов и численность их населения Р, Компания планирует назначить в данный регион двух торговых представителей. Каждый представитель будет отвечать за два округа (базовый и соседний). Округа считаются соседними, если они имеют общую сторону, наличия общего угла недостаточно.

Р1 1	Р2 2	Р3 3
Р4 4	Р5 5	Р6 6

Так, на приведенной карте округа 1 и 2 являются соседними, а округа 1 и 5 — нет. Компания стремится сделать так, чтобы суммарное население в округах с назначенными представителями было максимальным. Пример допустимого решения: выбрать базовым округ 4 с соседним округом 1, а также сделать базовым округ 3 с соседним 2. Значение целевой функции для такого решения равно Р, + Р, + Р, + Р

Введем следующие переменные: В_J = 1, если округ выбран в качестве базового, и В_J =0 в противном случае (j = 1, ..., 6); Аij= 1, если округ i выбран в качестве соседнего для базового округа j, и Аij= 0 в противном случае (j = 1, ..., 6; округи i и j — соседние). Таким образом, заданы переменные решения В_1,В₂,В₃,В₄,В₅,В₆,А₂₁, А₄₁, А₁₂, А₅₂, А₃₂, А₂₃, А₆₃ и т.д.

6. В модели не должно быть двойного счета (т.е. в одном варианте назначения один и тот же округ не должен одновременно выступать в качестве базового и соседнего). Запишите ограничение, которое сделает невозможным двойной счет для округа 1.

7. Запишите ограничение: "если торговый представитель назначается в базовый округ 2, то этот же торговый представитель должен быть назначен в один из соседних округов".

8. Запишите ограничение: "если один из двух округов, соседних с округом 1, выбран в качестве соседнего округа (к округу 1), то округ 1 должен использоваться в качестве базового".

9. Верно ли утверждение, что данную модель можно описать с помощью ограничений в виде 12 неравенств и 1 равенства?

10. Верно ли утверждение, что данную модель можно описать с помощью ограничений в виде 7 неравенств и 6 равенств?