Tips
for Handling Mixture Constraints
Mixture constraints are notoriously=
the
most difficult type of constraints to translate from English to Algebra.
I. A mixture constraint is typically a
requirement about some proportion or ratio. The ratio may be in the simp=
lest
case a ratio of one variable to another. In more complicated cases it is a
ratio between one linear combination of variables to another linear combina=
tion
of variables, or between a variable and a linear combination. (Linear Combination of variables i=
s a
weighted sums of variables; e.g. 2X +3Y+4Z). In the boundary of the constra=
int
we find the exact proportion or ratio.&nbs=
p;
Examples:
1=
)X is greater than Y
2=
)X is smaller than Y
3) X +5 is greater than Y.
4) X is larger than t=
he total
of Y and Z
5) X is smaller than =
one third
of Y
6) X is larger than o=
ne third
the sum of (Y and Z).
7) The sum of T and U= is smaller than one third of the sum of X,Y and Z.<= o:p>
And so on.
In linear programming=
we do
not distinguish between “greater” and greater or equal” a=
nd
between “smaller” and “smaller or equal. Hence, the boundary of every mixtu=
re
constraint in the above examples must be equality that represents some
proportion. Consider the cons=
traints
and boundaries for the above examples:
For 1), the constrain=
t is X
> Y.
The boundary is, X =
=3D Y , or alternatively&=
nbsp;
X- Y =3D 0. The ratio =
between
X and Y is one.
For 2), the constrain=
t is X
< Y.
The boundary is X =3D=
Y, or alternatively X=
-
Y =3D 0. The ratio between X =
and Y is
one.
For 3), the constrain=
t is,
X+5 > Y.
The boundary is, X+5 =3D Y, or alternatively X=
-
Y =3D -5. The ratio between X=
+5 and Y
is one.
For 4), the constrain=
t is, X
> Y + Z,
The boundary is, X =
=3D Y + Z,
or alternatively
X- Y -Z=3D 0. .=
The ratio between X and Y + Z is o=
ne.
For 5), the constrain=
t is X
< (1/3)Y.
The boundary is, X =3D =
(1/3)Y, or
alternatively X- (1/3)Y =3D 0=
The ratio of X to Y i=
s 1/3.
For (6), the constrai=
nt is X
> (1/3)(Y+Z).
The boundary is, X=3D
(1/3)(Y+Z),or alternatively X-
(1/3)Y-(1/3)Z =3D 0.
The ratio of X to Y+Z=
is 1/3.
For (7), the constrai=
nt is
T+U < =
(1/3)(X+Y+Z).
The boundary is, T+U =
=3D(1/3)(X+Y+Z),
or
alternatively,
T+U-(1/3)X-(1/3)Y-(1/3)Z=3D0 . The ratio of T+U to X+Y+Z is 1/3.
And so on.
To see if a constrain=
t was
expressed correctly algebraically, I suggest you substitute a numerical exa=
mple
in the algebraic expression and check if it satisfies the logical statement=
of
the constraint. If it is not, the algebraic statement is false.
II. A great difficulty in trans=
lation
is encountered when the direction of the mixture constraints appears in the
beginning of the sentence.
For example, consider=
the
following mixture constraint in a blending problem, (in page 327 of the
textbook),
“At least 30% o=
f the
volume of the cologne must be emulsion”
The difficulty is tha=
t the
direction of the constraint appears at the beginning of the constraint. This direction is given by the wor=
ds
“At least”
Algebraically, we nee=
d to
have the direction of any constraint only in the middle of the algebraic
sentence. The algebraic sente=
nce
must have only one of the following patterns
A > B
A < B
A =3D B
Let me suggest a step=
by step
approach to overcoming the translation problem.
Step1:<=
span
style=3D'font-size:14.0pt'> Identify the constraint and writing it down.
“At least 30% o=
f the
volume of the cologne must be emulsion”
“The vo=
lume
of emulsion in the cologne must be at least 30% of the volume of the
In short hand, to fit the sentence in one line, =
this
can be expressed as,
“The vol.of emulsion.=
in
Notice that the sentence has three parts: blue, =
red
and green
Here, we divide the translation to three parts:<= o:p>
F=
irst we
translate the blue part. We f=
ollow
by translating the direction of the constraint (the red part). Finally, we translate the green pa=
rt.
Accordingly,
“the vol.
Emulsion in the
.50Xoc + 1.00=
Xrc +
.10Xsc
“at
least” is translated as,
>
“30% of the vol=
. of the
.30(Xoc + Xrc + Xsc).=
Hence, the algebraic statement must=
be
.50Xoc + 1.00Xrc + .10Xsc > .30(Xoc
+ Xrc + Xsc)
o=
r equivalently,
.50Xoc + 1.00Xrc + .10Xsc > .30Xoc + .30Xrc +
.30Xsc.
After collecting like=
terms
we obtain,
.20Xoc + .70Xrc - .20Xsc > 0
Step 4:=
Representation of the constraint in a standardi=
zed
format.
We need to take into =
account
all the decision variables in the problem by their order on the left hand s=
ide
of the constraint, and we need to place a coefficient (a number) in front of
every decision variable. Henc=
e, we
obtain,
0Xoa + 0Xra + 0Xsa +.20Xoc + .70Xrc - .20Xsc >=
; 0.
Note: Your further questions are most
welcomed.