CHAPTER 2: Solution of LPPs: the graphical methods and the simplex methods# Flashcards
Definition 2.1 (The general form of an LPP).
We will consider a general LPP with d independent variables:
max(or min) z =
c_1x_1 + c_2x_2 + . . . + c_dx_d
subject to m constraints:
a_{11}x_1 + . . . + a_{1d}x_d ≤ b_1
… .. .. ..
a_{m1}x_1 + . . . + a_{md}x_d ≤ b_m
and x1, x2, . . . xd ≥ 0.
The problem can be written as follows
max(or min) z =
c^Tx
subject to Ax ≤ b, x ≥ 0
where c ∈ R^d
is a constant vector, and
x ∈ R^d
They are vectors with d components:
c = (c1, c2, …, cd)^T and
x = (x1, x2, …, xd)^T
b = (b1, …, bm)^T ∈ R^m
is also a constant vector. A is a constant m × d coefficient matrix whose entries are aij’s.
Definition 2.2. DECISION VARIABLES
x1, …, xd are the decision variables,
c is the cost coefficient vector.
b is the resource vector;
bi is the resource of the ith constraint.
c_i is the cost coefficient of decision variable x_i
Definition 2.3 (Cost function).
The function to be minimized or maximized (z in the definition) is called the cost function, or the profit function or the objective function.
Definition 2.4 (Feasible region).
The set of values for the variables x that satisfy the constraints is called the feasible region (or feasible set) of the problem. In other words, the feasible region is the solution of the
inequalities Ax ≤ b and x ≥ 0. Sometimes we use A to denote the feasible region, i.e.,
A = {x ∈ R^r: Ax ≤ b, x ≥ 0}.
The goal of an LPP is to find an x in the feasible region that maximizes or minimizes z. A few comments about the notations are in order:
• x ≥ 0 means xi ≥ 0 for all components i = 1, 2, …, d. Same applies to b ≥ 0 or other similar expressions.
• We have assumed all constraints are ≤ constraints when we write Ax ≤ b.
A ≥ constraint can be converted to a ≤ constraint by multiplying the inequality by −1 . For an = constraint such as LHS = RHS,
we may replace it with two simultaneous constraints LHS ≥ RHS and LHS ≤ RHS.
• We use (Ax)_i
to represent the ith component of the product Ax.
(Ax)i
:= a_{i1}x_1 + a_{i2}x_2 + … + a_{id}x_d
is the left hand side of the ith constraint.
• Vector b is called resource vector because the constraints often represent the limited availability of the
resources in real world examples. In this case, x may represent the production rates of some products,
and
(Ax)_i
is the amount of the ith type of resources consumed by these products.
*prefer less than or equal to constraint
Graphical Solutions
We solve problem with only 2 decision vars x_1, x_2
*For a given value of z, a function like z = c1x1 + c2x2 represents a straight line (contour of the function z(x1, x2) = c1x1 + c2x2).
This line will be called a z-line. When we change the z value, we obtain
different z-lines.
There are several simple observations:
• The z-lines are all parallel
• All the points on a z-line give the same z value. eg if 2 points on same line points A And B both give z = z1 = 6, and both points C and D give z = z2 = 18.
• To find where the maximum of
z(x1, x2)
is, we only need to compare the points on different z-lines. For the example given z=2x_1+3x_2 the z-line moves up when z is increased, which means the value of z is larger on the right hand side of a z-line, and smaller on the left.
Example 2.1 (Product-Mix Problem, aka the Reddy-Mikks problem). We will use the graphical method to
solve the problem in Example 1.2.
The formulation is as follows: x1 is the amount of paint E produced per day, and x2 is that of paint I. z is the revenue per day. The LPP is:
max z =
3x_1 + 2x_2 (unit £100)
subject to x1 + 2x2 ≤ 6 2x1 + x2 ≤ 8 −x1 + x2 ≤ 1 x2 ≤ 2 with x1, x2 ≥ 0
*graph showing constraints giving feasible region
giving irregular hexagonal shape- feasible region is a polygon
- z-lines for several z values shown 6,9,… : The optimal solution is found on a corner/vertex of the feasible region.
- A feasible point is optimal in this example if there is no other feasible point on RHS of z-line. So z_max is found at point C as FR only on LHS of z-line passing through this point
solving: x_1 +2x_2=6 and 2x_1+x_2=8
(x_1,x_2) = (10/3, 4/3)
optimal is Z_max= 3(3/10)+2(4/3) = 38/3 ~12.67 (100 pounds unit)
*constraint 1 and 2 2 are binding constraints, whereas 3 and 4 are non-binding
Definition 2.5 (Binding/non-binding constraints).
A constraint is binding if the constraint (which in general
is an inequality) becomes an equation at the optimal solution. Otherwise it is non-binding. Graphically, the
boundary of a binding constraint passes through the optimal solution; the optimal solution is found at the intersection of the boundaries of all binding constraints.
redundant constraint
An extreme example of non-binding constraints is a redundant constraint. You can remove a redundant constraint without changing the feasible region.
Definition 2.6 (Slack).
Let x be a solution for the LPP, the slack of the ith constraint for the solution is bi − (Ax)i
(recall that the constraints are given by Ax ≤ b).
Remark. The slacks are some of the quantities we may want to calculate in the post-optimality analysis, because they tell us the amount of the resource left from the production of x.
e.g slack was 2-x_2 = 2/3 so if optimal (x_1,x_2) = (10/3, 4/3) from the 4th constraint x_2 ≤ 2
Definition 2.8 (Shadow cost).
The shadow cost of a constraint is the change in the optimal value of the cost function when the resource for this constraint is increased by 1 unit. More precisely, letting δz_opt denote the change in the optimal cost z_opt when b_i is increased by δb_i , the ith shadow cost is the limit of δz_opt/δb_i when δb_i → 0.
Remark. The shadow cost is also called shadow price, marginal cost or marginal profit.
Example 2.2 (Extensions to the Product-Mix Problem). We consider several extensions to Example 2.1:
1. Referring to Example 2.1, let the price for x1 (paint E) be c1 (in £100), so that the revenue is z = c1x1 + 2x2. How much can we change c1 while the optimal solution for (x1, x2) remains optimal? (i.e., what is
the optimality range for c1?)
- Constraint given by Eq. 2.1 is due to the limited availability of raw material A (6 tons/day). Suppose
the available amount is increased to (6 + δ) tons/day for a small amount δ. What is the optimal strategy
(x1, x2) and the change in revenue? What is the change for per unit δ? (i.e., what is the shadow cost for
the constraint?) - If additional material A costs 35£/ton, is it worth buying 1 ton more per day to increase the production?
*The optimal sol may not be the point C if c_1 is too large/small e.g if c_1made smaller than 3 the optimal solution is
(smaller x_1, larger x_2)=D
if c_1 made bigger (larger x_1, smaller x_2) = B
solution changes with c_1, slope of the z line decreases with c.
slope of z-line is -c_1/2. Slope BC
(2x_1+x_2=8) is -2 , CD (x_1 +2x_2=6) is -0.5
Thus at these 2 limits c_1=4 and 1 respectively.
*1≤ c_1 ≤ 4 (units 100 pounds/ton)
pounds/ ton range is 100 ≤ c_1 ≤400
(the optimal solution stays until when slopes of Z lines for between those of CD and BC ( -0.5 and -2)
thus slope -2≤ -c_1/2 ≤ -0.5 gives * . optimal range for c, without changing x1, x2.
so if possible we can increase c1 to 4 to increase profits)
2)
for z=3x_1 +2x_2
x_1+2x_2 ≤ 6 becomes
x_1+2x_2 ≤ 6+δ
ie the revenue is increased by δ/3 (100 pounds). Change per unit of δ is 1/3
(unit 100 pounds/ton)`33 pounds
The optimal solution implies new solution at vertex with lower x_1 and larger x_2 than original optimal solution. This does not improve even if we increase δ any further
the optimal solution is still found at the intersection of boundaries of constraints 1 and 2:
thus x_1+2x_2=6+δ
2x1 +x2=8 implies x_1=(10-δ )/3 x_2= (4+2δ )/3 implies z_max= 38/3 + δ/3. The change in z_max is δ/3
ie increasing a by 1 tonne per day increases revenue by £33. Since A costs £35, more than increase in revenue, it’s not worth buying.
shadow cost is 1/3 (unit of z_max/ units of δ )
100/33 ~33 so as shadow cost is smaller than t35 pounds/ton we don’t
LPPs with more than two variables: Slack variables
Graphical method is useful mostly only for problems with two variables. For problems with more variables,
we need an algebraic method. We introduce the simplex method in this module.
For problems with two decision variables such as the product mix example (Example 2.1), we observe
• that the feasible region is a polygon formed by the intersection of the half-planes defined by the inequality constraints;
• optimal solution is found on a vertex of the polygon.
In general the feasible region is a convex polyhedron (polytope) bounded by hyperplanes; the optimal solution is on a vertex of the polytope.
• How do we know the feasibility of a solution? . For problems with more variables, it is very difficult to visualize the
feasible region
• How do we define a vertex? In two variable problems, the intersection of the boundaries of two constraints
defines a vertex, which can be easily identified visually. How do we know if a point is a vertex without
a graph?
LPPs with more than two variables: Slack variables 2
we need to keep track of the ‘slack’ of a constraint: if the slack is not negative, then
the constraint is satisfied. Thus, we introduce the slack variables to record the ‘slack’ of a constraint at each
step of the calculation.
Definition 2.9 (Slack variable).
Consider the general LPP defined in Definition 2.1. The slack variable for the
ith constraint is denoted as x_{d+i} , and is defined as follows:
x_{d+i} = b_i − (a_{i1}x_1 + . . . + a_{id}x_d) = b_i − (Ax)_i
where i = 1, 2, …, m corresponding to the m constraints (excluding the conditions x ≥ 0).
Remark. The ‘slack’ defined in the previous section is simply the value of the slack variable for a given solution
FEASIBILITY OF A SOLUTION:
A solution is feasible if all variables (both decision and slack variables included) are non-negative.
CANONICAL FORM notes
Using slack variables, the ith constraint becomes an equation:
(Ax)i + x{d+i} = b_i
(i = 1, 2, …, m).
With slight abuse of notations, let
x = (x_1, x_2, ..., x_d, x_{d+1}, ..., x_{d+m})^T
That is, we now use symbol x to denote the vector including both decision and slack variables. The constraints then become [A, I]x = b, where I is the m × m identity matrix, and [A, I] is a matrix formed by putting A and I side by side. Letting A¯ := [A, I], the constraints become Ax¯ = b with A¯ being an m × n matrix where n = d + m. Finally, let c = (c1, c2, ..., cd, cd+1, ..., cd+m)T with cd+1 = cd+2 = ... = cd+m = 0, then the cost function has the same form as before z = cTx.
Definition 2.10 (Canonical form).
The canonical form of the LPP introduced in Definition 2.1 is:
max or min z = c^Tx,
subject to
Ax¯ := [A, I]x = b, x ≥ 0
where, with n = m + d,
x = (x1, x2, …, xd
x_{d+1}, …, xn)^T ∈ R^n
x_{d+1}, …, xn being the slack variables, and
c = (c1, …, cd, c_{d+1}, …, c_n)^T ∈ R^n with
c_{d+1} = c_{d+2} = … = c_n = 0.
b ∈ Rm is the resource vector as in Definition 2.1.
A¯ is an m × n matrix, which is called the extended coefficient matrix.
*we now include slack variables in x but so must make respective c_i’s=0
*canonical form is not
unique. In particular, for problems with = constraints, we may have different canonical forms depending on
how we deal with those constraints. We will normally use the method of artificial variables. In that case, we
do not introduce a slack variable for an = constraint, but introduce an artificial variable instead.
Example 2.3: (Canonical form for the product-mix problem).
The LP problem for Example 2.1 is
max z =3x1 + 2x2, subject to
x1 + 2x2 ≤ 6 2x1 + x2 ≤ 8 −x1 + x2 ≤ 1 x2 ≤ 2 with x1, x2 ≥ 0. Find its canonical form.
Solution. The canonical form of the problem is
max z = 3x_1 + 2x_2 + 0x_3 + 0x_4 + 0x_5 + 0x_6
subject to
x1 + 2x2 + x3 = 6
2x1 + x2 + x4 = 8
−x1 + x2 + x5 = 1
x2 + x6 = 2
with x1, x2, . . . , x6 ≥ 0. We have introduced four slack variables x3, x4, x5, and x6.
Example 2.4. Find the canonical form for the following set of constraints:
2x1 + 3x2 ≤ 6
x1 + 7x2 ≥ 4
in the canonical form they become:
2x1+3x2 +x3= 6 and
-x1-7x2+x4 = -4
by introducing slack vars x3 and x4
(we must have ≤ to convert to canonical form )
geometrical interpretation of slack variables
distance from point (x1, x2) to line ax1 + bx2 = c is given by
d =|c − ax1 − bx2|/(√(a^2 + b^2))
Now consider the constraint 2x1 +3x2 ≤ 6 and its canonical form which may be written as x3 = 6−2x1 −3x2.
Therefore, the distance from the point (x1, x2) to the boundary 2x1 + 3x2 = 6 is
|x3|/√13, which gives an
geometrical interpretation of x3. There is a similar relation between other slack variables and the distance
from the solution to the boundary of the corresponding constraints.
undetermined system
we have an undetermined system when more variables than equations
this implies there are infinitely many Solutions i.e. a set of Solutions
( Since a solution is feasible if and only if all the
variables are non-negative)
d+m vars in m equations
d+m vars in m equations we fix d values of the variables to find a unique solution
If we choose d variables and set them to zero, we obtain solutions with a special geometrical interpretation
In general, for a problem with d decision variables and m inequality constraints, we have the following observation:
For an LPP with d decision variables, a vertex is a solution to the set of constraints (in its canonical form) with d variables set to zero. These d variables can be either slack or decision variables.
Thus, the vertices of the feasible region of an LPP correspond to certain special types of solutions of the constraints. We have a formal name for this type of solutions. Note that, for an LPP with d decision variables and m constraints, in its canonical form, the constraints Ax¯ = b are a set of m equations with n = m + d variables.
Example: previous optimal at C solution from graphical methods
As we have seen in Example 2.1, the optimal solution is found on vertex C. The coordinates of vertex C is the
solution of the simultaneous equations:
x1 + 2x2 = 6, 2x1 + x2 = 8.
Now, using the canonical form of the problem, the 1st and 2nd constraints are given by
x1 + 2x2 + x3 = 6, 2x1 + x2 + x4 = 8.
Therefore, vertex C is actually the solution of the above equations with the slack variables x3 = x4 = 0.
Similarly, vertex D is the intersection of the boundaries of the 1st and 4th constraints, thus its coordinates are
the solution of the constraints with the slack variables x3 = x6 = 0.
On the other hand, vertex B is the intersection of
x1 + 2x2 = 6, x2 = 0.
Apparently, the first equation is the first constraint with the slack variable x3 = 0. The second equation sets
the decision variable x2 to zero.
Therefore, in Example 2.1 a vertex is the solution of the constraints in the canonical form when two of the
variables (possibly slack or decision variable) are set to zero. This is consistent with the above general statement.
