Важный класс прикладных оптимизационных задач образуют задачи о смесях. Такие задачи возникают при выборе наилучшего способа смешения исходных ингредиентов для получения смеси с заданными свойствами. Смесь должна иметь требуемые свойства, которые определяются количеством компонент, входящих в состав исходных ингредиентов. Как правило, известны стоимостные характеристики ингредиентов и искомую смесь требуется получить с наименьшими затратами. Для многопродуктовых задач, в которых требуется получить несколько смесей, характерным является критерий максимизации прибыли. Задачи оптимального смешения встречаются во многих отраслях промышленности (металлургия, парфюмерия, пищевая промышленность, фармакология, сельское хозяйство). Примерами задач о смесях могут служить определение кормового рациона скота на животноводческих фермах, составление рецептуры шихты на металлургическом производстве.
Однопродуктовые модели оптимального смешения.Модель А.
| n | ||
| S | cj xj ® max | (1) |
| j=1 |
| n | ||
| S | ai j xj і bi , i =1,...,m | (2) |
| j=1 |
| xj і 0, j = 1,...,n, | (3) |
n - количество исходных ингредиентов, m - количество компонент в смеси,
x j- количество j-го ингредиента, входящего в смесь,
ai j - доля i-ой компоненты в j-м ингредиенте,
cj- стоимость единицы j-го ингредиента,
bi- минимально допустимое количество i-ой компоненты в смеси,
(1) - целевая функция (минимум затрат на получение смеси);
(2) - группа ограничений, определяющих содержание компонент в смеси;
(3) - ограничения на неотрицательность переменных.
В задаче могут присутствовать также ограничения на общий объем смеси и ограничения на количество используемых ингредиентов. Эти группы ограничений, а также ограничения вида (2) характерны для задачи планирования производства, рассмотренной в главе 1.
Модель Б.
| n | ||
| S | cj xj® min | (4) |
| j=1 |
| n | ||
| S | (a i j - b i ) xj і 0, i = 1,...,m, | (5) |
| j=1 | ||
| n | ||
| S | d rj xj і 0 , r = 1,...,w, | (6) |
| j=1 | ||
| x j і 0, j = 1,...,n, |
n - количество исходных ингредиентов,
m - количество компонент в смеси,
xj - количество j-го ингредиента, входящего в смесь,
a i j - доля i-ой компоненты в j-м ингредиенте,
b i - минимально допустимая доля i-ой компоненты в смеси,
cj - стоимость единицы j-го ингредиента,
d rj - коэффициент, отражающий r – ое условие на содержание j-го
ингредиента в смеси, r = 1,...,w./
(4) - целевая функция (минимум затрат на получение смеси);
(5) - группа ограничений, определяющих содержание компонент в смеси;
(6) – группа ограничений на содержание ингредиентов в смеси.
Ограничения вида (5) и (6) отличают задачу смешения от задачи оптимального планирования производства. Заметим, что значения правых частей этих ограничений равны нулю. Вектор x* с компонентами xj* , являющийся решением этой оптимизационной задачи, называют рецептом приготовления смеси, или рецептом смешения.
В многопродуктовых задачах ингредиенты используются для приготовления не одной, а нескольких смесей. При этом в качестве переменной xkj такой задачи рассматривается количество ингредиента j, используемое для приготовления смеси k. В многопродуктовой задаче обычно используется критерий максимизации прибыли.
Модель В.
| s | n | ||
| е | е | (p k - cj) xk j ® max | (7) |
| k=1 | j=1 |
| n | ||
| е | (a i j - b ik ) xkj і 0, i = 1,...,m, k = 1,...,s, | (8) |
| j=1 |
| n | ||
| S | d rk j x kj і 0 , r = 1,...,w, k = 1,...,s, | (9) |
| j=1 |
| x j і 0, j = 1,...,n, k = 1,...,s. |
n - количество исходных ингредиентов,
m - количество компонент в смеси,
s - количество смесей,
xkj- количество j-го ингредиента, входящего в k-ой смесь,
a i j - доля i-ой компоненты в j-м ингредиенте,
b ik - минимально допустимая доля i-го компонента в k-ой смеси,
cj- стоимость единицы j-го ингредиента,
pk - стоимость единицы k-ой смеси,
d r k j- коэффициент, отражающий r – ое условие на содержание j-го ингредиента в k -ой смеси.
(7) - целевая функция (минимум затрат на получение смеси);
(8) - группа ограничений, определяющих содержание компонент в смеси;
(9) – группа ограничений на содержание ингредиентов в смеси.