Примеры составления задач

Пример 11. Металлургическому заводу требуется уголь с содержанием фосфора не более 0,03% и с долей зольных примесей не более 3,25%. Завод закупает три сорта угля А, В, С с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, В, С, чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену? Содержание примесей и цена исходных продуктов приведены в табл. 10.

Таблица 10

Сорт угля	Содержание (%) в 1 т.	Цена 1 т, руб.
фосфора	золы
А В С	0,06 0,04 0,02	2,0 4,0 3,0

Решение. x₁ – количество угля сорта А в тонне смеси; x₂ – количество В в тонне смеси, x₃ – количество С в тонне смеси.

F(x) = 30x₁ + 30x₂ + 45x₃

0,06x₁ + 0,04x₂ + 0.02x₃ 0.03 (%) - ограничение на содержание фосфора в смеси,

2x₁ + 4x₂ + 3x₃ 3,25 (%) - ограничение на содержание зольных примесей,

x₁ + x₂ + x₃ = 1 (т.) - ограничение на состав 1 т. смеси.

x₁, x₂, x₃ 0.

Пример 12. В отделе технического контроля (ОТК) некоторой фирмы работают контролеры разрядов 1 и 2. Норма выработки ОТК за 8-часовой рабочий день составляет не менее 1800 изделий. Контролер разряда 1 проверяет 25 изделий в час, причем не ошибается в 98% случаев. Контролер разряда 2 проверяет 15 изделий в час; его точность составляет 95%.

Заработная плата контролера разряда 1 равна 4 руб. в час, контролер разряда 2 получает 3 руб. в час. При каждой ошибке контролера фирма несет убыток в размере 2 рубля. Фирма может использовать 8 контролеров разряда 1 и 10 контролеров разряда 2. Руководство фирмы хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальными.

Решение. Пусть х₁ и х₂ обозначают количество контролеров разрядов 1 и 2 соответственно. Число контролеров каждого разряда ограничено, т.е. имеются следующие ограничения: х₁ £ 8 (разряд 1), х₂ £ 10 (разряд 2). Ежедневно необходимо проверять не менее 1800 изделий. Поэтому выполняется неравенство:

8*25х₁ + 8*15х₂ = 200х₁ + 120х₂ ³ 1800, или 5х₁ + 3х₂ ³ 45.

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

1) зарплату контролеров.

2) убытки, вызванные ошибками контролеров.

Расходы на одного контролера разряда 1 в час составляют

4 руб. + 2*25*0,02 руб. = 5 руб.

Расходы на одного контролера разряда 2 в час составляют

3 руб. + 2*15*0,05 руб. = 4 руб.50 коп.

Следовательно, целевая функция, выражающая ежедневные расходы на контроль, имеет вид

F() = 8*(5х₁ + 4,5х₂) = 40х₁ + 36х₂.

Пример 13. Фирма выпускает три вида продукции (изделий). В процессе производства используются три технологические операции. На рис. 1 показана технологическая схема производства изделий видов 1, 2 и 3. При изготовлении изделия 2 технологическая операция 2 не выполняется, а при производстве изделия 3 используются только технологические операции 1 и 2. В прямоугольниках на рис. 1 указана длительность технологических операций при изготовлении изделия каждого вида.

Рис. 1. Технологическая схема производства изделий

Фонд рабочего времени, в течение которого операции 1, 2 и 3 могут быть применены для производства рассматриваемых изделий, ограничен следующими предельными значениями (в сутки): для первой операции - 430 мин, для второй операции - 460 мин, для третьей операции - 420 мин.

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

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

Решение. Пусть х₁ - количество производимых изделий вида 1, х₂ - количество производимых изделий вида 2, х₃ - количество производимых изделий вида 3.

F(х) = 3х₁ + 2х₂ + 5х₃ → max

при ограничениях (предельное время использования операций в течение суток):

х₁ + 2х₂ + х₃ £ 430 - для операции 1

3х₁ + 2х₃ £ 460 - для операции 2

х₁ + 4х₂ + £ 420 - для операции 3

х₁, х₂, х₃ ³ 0.

Пример 14. Банк, предоставляющий полный набор банковских услуг, находится в процессе формирования портфеля кредитов объемом 12 млн. долларов. В следующей таблице представлены возможные типы банковских кредитов.

Тип кредита	Ставка процента	Вероятность безнадежных долгов
Кредиты физическим лицам	0,140	0,10
Кредиты на покупку автомобилей	0,130	0,07
Кредиты на покупку жилья	0,120	0,03
Сельскохозяйственные	0,125	0,05
Коммерческие	0,100	0,02

Конкурентная борьба с другими финансовыми институтами вынуждает банк не менее 40% капитала помещать в сельскохозяйственные и коммерческие кредиты. Для содействия строительной индустрии своего региона банк планирует вложить в кредиты на покупку жилья не менее 50% от общей суммы кредитов физических лиц, на покупку автомобилей и жилья. Банк также поддерживает государственную политику, указывающую, что отношение безнадежных долгов ко всей сумме кредитов не должно превышать 0,04. Найти максимальную чистую прибыль.

Решение. Пусть х₁ – кредиты физическим лицам, х₂ – кредиты на покупку автомобилей, х₃ – кредиты на покупку жилья, х₄ – сельскохозяйственные кредиты, х₅ – коммерческие кредиты.

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

Z_max = 0,14*0,9х₁ + 0,13*0,93х₂ + 0,12*0,97х₃ – 0,125*0,95х₄ +
+ 0,1*0,98x₅ – 0,1х₁ – 0,07х₂ – 0,03х₃ – 0,055х₄ – 0,02x₅

или Z _max = 0,026х₁ + 0,0509х₂ + 0,0864х₃ – 0,06875х₄ + 0,078x₅.

Задача имеет пять ограничений.

1. Ограничение общей суммы кредитов х₁ + х₂ + х₃ + x₄ + х₅ ≤ 12.

2. Ограничение на сельскохозяйственные и коммерческие кредиты x₄ + х₅ ≥ 0,4*12 или x₄ + х₅ ≥ 4,8.

3. Ограничение кредитов на покупку жилья х₅ ≥ 0,5*(x₁ + x₂ + x₃) или 0,5х₁ + 0,5х₂ – 0,5х₃ ≤ 0.

4. Ограничения на невозвращенные кредиты

или 0,06х₁ + 0,03х₂ – 0,01х₃ +0,01x₄ – 0,02х₅ ≤ 0.

5. х₂ ≥ 0; х₃ ≥ 0; х₄ ≥ 0; х₅ ≥ 0.

Пример 15. Имеется три сорта бумаги в количествах 10, 8 и 5 т, которые можно использовать на издание четырёх книг тиражом в 8000, 6000, 15 000 и 10 000 экземпляров. Расход бумаги на одну книгу составляет 0,6, 0,8, 0,4 и 0,5 кг, а себестоимость (в к.) печатания книги при использовании i -го сорта бумаги задаётся матрицей:

30 24 16 20

C = 18 24 24 20

24 16 32 25

Определить оптимальное распределение бумажных ресурсов.

Вариант решения 1. Обозначим через x_ik количество экземпляров
k -й книги, отпечатанной на бумаге i -го сорта. Тогда функция цели:

F_min = 30х₁₁ + 24х₁₂ +16х₁₃ + 20х₁₄ + 18х₂₁ +24х₂₂ +24х₂₃ +20х₂₄+
+ 24х₃₁ +16х₃₂ +32х₃₃ + 25х₃₄.

0,6 x₁₁ +0,8 x₁₂ +0,4 x₁₃ +0,5 x₁₄ ≤ 10 000,

0,6 x₂₁ +0,8 x₂₂ +0,4 x₂₃ +0,5 x₂₄ ≤ 8000, - на запасы бумаги

0,6 x₃₁ +0,8 x₃₂ +0,4 x₃₃ +0,5 x₃₄ ≤ 5000.

x₁₁ + x₂₁ + ₃₁ x ≥ 8000,

x₁₂ + x₂₂ + x₃₂ ≥ 6000, - на производственную программу

x₁₃ + x₂₃ + x₃₃ ≥ 15 000,

x₁₄ + x₂₄ + x₃₄ ≥ 10 000.

х_ik ≥ 0

Вариант решения 2. Обозначим через x_ikколичество бумаги i -го сорта, расходуемой на печать k - й книги. Тогда функция цели:

F _min = 1/0,6*(24x₃₁ + 18 x₂₁ + 30 x₁₁) + 1/0,8*(16x₃₂ + 24 x₂₂ + 24 x₁₂) +
+ 1/0,4*(32x₃₃ + 24 x₂₃ + 16 x₁₃) + 1/0,5*(25x₄₄ + 20 x₂₄ + 20 x₁₄)

x₁₁ + x₁₂ + x₁₃ + x₁₄ ≤10000,

x₂₁ + x₂₂ + x₂₃ + x₂₄ ≤8000, на запасы бумаги (по каждому сорту)

x₃₁ + x₃₂ + x₃₃ + x₃₄ ≤5000.

1/0,6*(x ₁₁ + x₂₁ + x₃₁) ≥ 8000

1/0,8*(x₁₂ + x₂₂ + x₃₂) ≥ 6000 - на производственную программу

1/0,4*(x₁₃ + x₂₃ + x₃₃) ≥ 15 000,

1/0,5*(x₁₄ + x₂₄ + x₃₄) ≥ 10 000

х_ik ≥ 0

Пример 16. Авиакомпания для организации пассажирских перевозок между центром и четырьмя городами располагает тремя группами самолётов: 1-я группа – из 10 четырёхмоторных самолётов, 2-я – из 25 двухмоторных самолётов и 3-я – из 40 двухмоторных старого образца.

Минимальное количество пассажиров, перевозимых одним самолётом данного типа по каждому маршруту за один месяц (в тыс. человек), и связанные с этим эксплуатационные расходы на 1 самолёт (в тыс. р.) указаны соответственно в правых верхних и левых нижних углах каждой клетки таблицы 11. В двух последних строках приведены количество пассажиров, которое нужно перевезти по данному маршруту в месяц, и стоимость одного билета. Распределить самолёты по маршрутам из условия достижения максимальной прибыли авиакомпании.

Таблица 11

Самолет	Город
четырёхмоторный	1,6	2,2	1,3	–
двухмоторный	2,8	3,0	2,4	2,0
двухмоторный старого образца	0,8	-	1,0	1,5
Количество пассажиров, тыс. чел.
Стоимость билета, р.

Решение. Обозначим через x_ij количество самолетов i -го вида, выполняющих рейсы по j -му маршруту.

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

F_max = 25(1,6х₁₁ + 2,8х₂₁ + 0,8х₃₁) + 15(2,2х₁₂ + 3х₂₂) + 20(1,3х₁₃ +
+ 2,4х₂₃ +х₃₃) + 15(2х₂₄ + 1,5х₂₄) – (16х₁₁ + 20х₁₂ + 15х₁₃) – (30х₂₁ +
+ 25х₂₂ + 20х₂₃ + 25х₂₄) – (15х₃₁ + 12х₃₃ + 16х₃₄).

Ограничения на количество самолетов каждого вида:

x₁₁ + x₁₂ + x₁₃ + x₁₄ ≤ 10,

x₂₁ + x₂₂ + x₂₃ + x₂₄ ≤ 25,

x₃₁ + x₃₂ + x₃₃ + x₃₄ ≤ 40.

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

1,6 x₁₁ +2,8 x₂₁ +0,8 x₃₁ ≥ 20,

2,2 x₃₁ +3,0 x₂₂ ≥ 50,

1,3 x₃₁ +2,4 x₃₂ +1,0 x₃₃ ≥ 40,

2,0 x₄₂ +1,5 x₄₃ ≥ 30.

х_ik ≥ 0

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

Таблица 12

Завод	Максимальный недельный фонд времени, час	Производительность, (узел/час)
	Узел 1	Узел 2	Узел 3

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

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

Решение. Пусть x_ij – недельный фонд времени (в часах), выделяемый на заводе i для производства узлов вида j. Тогда объемы производства каждого из трех комплектующих узлов равны: 8x₁₁ + 6x₂₁ (узел 1), 5x₂₁ + 12x₂₂ (узел 2), 10x₁₃ + 4x₂₃ (узел 3). Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделий должно быть равно количеству комплектующих узлов, объем производства, которых минимален. Если, например, объем производства двух заводов составляет 100, 112 и 108 соответствующих узлов, то количество конечных изделий будет равно min {100,112,108} = 100. Поэтому количество конечных изделий можно выразить через число комплектующих узлов следующим образом:

F(х)_max = min{(8x₁₁ + 6x₂₁), (5x₁₂ + 12x₂₂), (10x₁₃ + 4x₂₃)}.

x₁₁ + x₁₂ + x₁₃ £ 100 (завод 1);

x₂₁ + x₂₂ + x₂₃ £ 80 (завод 2);

x_ij ³ 0.

Данная модель не является линейной, но ее можно привести к линейной с помощью преобразования. Пусть у – количество изделий y = min{8x₁₁ + 6x₂₁, 5x₁₂ + 12x₂₂, 10x₁₃ + 4x₂₃}.
Тогда F _max = у при ограничениях:

8x₁₁ + 6x₂₁ ³ у или 8x₁₁ + 6x2₁ – у ³ 0

5x₁₂ + 12x₂₂ ³ у 5x₁₂ + 12x₂₂ – у ³ 0

10x₁₃ + 4x₂₃ ³ у 10x₁₃ + 4x₂₃ – у ³ 0

x₁₁ + x₁₂ + x₁₃ £ 100 (завод 1);

x₂₁ + x₂₂ + x₂₃ £ 80 (завод 2);

x_ij³ 0, у ³ 0.