Задачи о «смесях»

Постановка задачи. Имеется р ком­понентов (i == 1, 2, ..., р), при сочетании которых в раз­личных пропорциях образуются различные смеси. Заданы р чисел Сi характеризующих цену, вес, калорийность и т.д. единицы i-го компонента. Требуется определить состав смеси (т. е. числа X1, … ,Xi, … Xp), для которой суммарная характеристика (цена, вес и т. д.) окажется наи­лучшей.

При этом предполагается, что в состав каждого компонента входят q веществ. Для каждого вещества задано число Bj, указывающее минимально необходимое содержание j-го вещества в смеси. Через Aij обозначено количество j-го вещества (j = 1, 2, ..., q), которое входит в состав единицы i-го компонента.

Решенне. Предпо­лагается, что количество вещества в смеси равно сумме количеств вещества в каждой из компонент смеси, т. е. если смесь состоит из X1 единиц 1-го компонента, X2 единиц 2-го компонента и т. д., то количество вещества j в смеси равно . Из условия обязательного минимального содержания каждого из веществ в смеси получим си­стему неравенств:

Кроме того, очевидно, что

Наконец, суммарная характеристика смеси выразится равенством .

Замечания.1. Кроме ограничений, по содержанию отдельных веществ в смеси, в задаче могут фигурировать ограничения по имеющимся запасам отдельных компонентов или по предельным нормам их включения в смеси. Могут задаваться также пропорции, в которых некоторые из компонентов должны входить в состав смеси.

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

Ресурсами в данном случае служат участки земли, на которых выращиваются различные компоненты, включаемые в рацион.

Пример задачи. Нефтеперерабатывающий завод получает 4 полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л. изопенттона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационног бензина: бензин А— 2:3:5:2, бензин В — 3 : 1 : 2: 1 и бензин С — 2: 2: 1 : 3.

Стоимость 1 тыс. л указанных сортов бензина характеризуется числами: 120 руб., 100 руб. и 150 руб.

Определить план смешения компонентов, при котором будет достигнута максимальная стоимость всей продукции. (Вариант: Определить оптимальный план смешения из усло­вия максимального использования компонентов.)

Задачи о «раскрое»

Постановка задачи. На раскрой (распил, обработку) поступает s различных материалов. Требуется изготовить из них q различных изделий в коли­честве, пропорциональном числам B1, B2, … , Bk, … ,Bq.

Каждая единица j-го материала (j == 1,2,..., s) может быть раскроена р различными способами, причем исполь­зование i-ro способа (i == 1,..., р) дает единиц k-x из­делий.

Найти план распила, обеспечивающий максимальное число комплектов, если материалов j-го вида поступает Dj единиц.

Решение. Обозначим через Xij количество единиц j-го материала, раскраиваемых по i-му способу (всего таких переменных будет p*s). Переменные Xij, очевидно, должны удовлетворять ограничениям:

где K — число комплектов изготавливаемых изделий.

Задача заключается в максимизации Z == K при вышеуказанных условиях.

В частном случае, когда на обработку поступает материал только одного образца (т. е. s = 1), в количестве D ед., модель принимает более простой вид:

Пример задачи. Для изготовления брусьев трех размеров: 0,6м, 1,5м и 2,5м в соотношении 2 : 1 : 3 на распил поступают бревна длиной в 3 м. Определить план распила, обеспечивающий максимальное число комплектов.

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

Способы распила (i)	Получаемые брусья			Количества бре­вен, распилен­ных по i-му способу
	0,6	1,5	2,5
1	5	—	—	X1
2	2	1	—	X2
3	—	2	—	X3
4	—	—	1	X4
Комплект	2	1	3

Теперь составляем математическую модель, приняв, что всего поступает на распил D бревен: максимизировать число комплектов Z=K при условиях, что все бревна должны быть распилены (X1+X2+X3+X4=D) и что число брусьев каждого размера должно удовлетворять условию комплектности:

5Х1+2Х2=2К; Х2+2Х3=1К; Х4=3К.

Из последнего равенства, определив К=1/3Х4, и исключив К из остальных выражений, придем окончательно к следующей задаче:

После решения ее получим оптимальное решение задачи Х={4/39, 5/39, 0, 10/13} н Z=10/39.

Таким образом, 10,2% (4/39) общего числа поступающих бревен следует распиливать по 1-му способу, 12,8% — по 2-му способу и 77% — 4-му способу; 3-й способ распила применять не следует. При этом будет произведено 10/39 комплекта на каждые D брёвен.

ОБЩАЯ ПЛАНОВО-ПРОИЗВОДСТВЕННАЯ ЗАДАЧА.

ВЫБОР ИНТЕНСИВНОСТЕЙ ИСПОЛЬЗОВАНИЯ РАЗЛИЧНЫХ ТЕХНОЛОГИЧЕСКИХ СПОСОБОВ ПРОИЗВОДСТВА

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

Постановка задачи. Некоторый про­изводственный процесс может вестись в p различных технологических режимах (способах организации про­изводства, способах обработки, раскроя и т. д.). В рас­сматриваемом процессе участвуют q производственных факторов (изделий, ресурсов и т. д.). Пусть Aij означает объём производства j-то фактора (j = 1, 2, ..., q), при применении i-ro технологического режима (i = 1, 2, .... p) с единичной интенсивностью. При этом если Aij > 0, то i-й фактор производится (например, изделия, продукты и т. д.), а если Aij < 0, то соответствующий фактор расходуется (например, ресурсы, сырье и т. д.).

Обозначим через Bj > 0 потребность в j-м факторе, если он производится, и через Bj < 0 — ресурсы j-ro фактора, если он расходуется. Таким образом, с помощью введения чисел Aij и Bj со знаками «+» или «-» устанавливается как бы формальное равноправие между ресурсами и потребностями.

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

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

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

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

Пример задачи. Нефтеперерабатывающий завод располагает 10 ед. нефти сорта А и 15 ед. сорта В. При переработке нефти получаются бензин и мазут. При этом известны следующие три способа переработки:

Способы переработки	Результат
	Мазут	Бензин
1А+2В	2	3
2А+1В	5	1
2А+2В	2	1
Цена за единицу	2	10

Найти наиболее выгодный план переработки, дающий максимум товарной продукции.