Assignment
Problem 4.1: (Simplex Algorithm) Consider the problem
Minimize, Z = 2x1 x2
Subject to, x1 x2 <= 2, x1 + x2 <= 6, x1 >= 0 and x2 >=0
a) Convert the problem to standard form and construct a basic feasible solution at (x1, x2) =
(0,0)
The standard form is,
Maximize, Z = 2x1 + x2
Subject to, x1 x2 + s1 = 2 and x1 + x2 + s2 = 6 where s1 and s2 are slack variables.
Setting (x1, x2) = (0,0) in those two constraint, we get s1 = 2 and s2 = 6. So the corresponding
basic solution is (x1,x2,s1,s2) = (0,0, 2, 6) which is feasible so this is a BFS.
b) Carry out the full tableau implementation of the simplex algorithm, starting with the BFS of
part a
So the optimal BFS is (x1,x2,s1,s2) = (4, 2, 0, 0) and the minimum value of objective function is
2*4 2 = 10.
c) Draw a graphical representation of the problem in terms of original variables, x1 and x2, and
indicate the path taken by the simplex algorithm.
From the full tableau we implemented in b we see that the order of BFS from iteration 1 to 3 are
(x1, x2, s1, s2) = (0,0, 2, 6) , (2, 0, 0, 6), (4, 2, 0, 0). Here is the BFS direction in graphical
way…
Problem 4.2: (Computation of BFS, feasible direction and reduced cost) Consider the problem
Minimize, Z = 5x1 3x2
Subject to, 2x1 + x2 <= 8, x1 + 2x2 <= 6, x1 >= 0 and x2 >=0
a) Convert the problem to standard form
The standard form is,
Maximize, Z = 5x1 + 3x2
Subject to, 2x1 + x2 + s1 = 8 and x1 + 2x2 + s2 = 6 where s1 and s2 are slack variables.
b) Find all the basic feasible solutions (BFSs) in which x1 is not a basic variable while x2 is a
basic variable.
1. Case 1: x2 & s1 basic variables and x1 and s2 non basic. So x2 = 3 and s1 = 5. The
basic solution is (0, 3, 5, 0) which is feasible, so a BFS.
2. Case 2: x2 & s2 basic variables and x1 and s1 non basic. So x2 = 8 and s2 = 10. The
basic solution is (0, 8, 0, 10) which is not feasible, so as not a BFS.
3. Case 3: s1 & s2 basic variables and x1 and x2 non basic. So s1 = 8 and s2= 6. The
basic solution is (0, 0, 8, 6) which is feasible, so as a BFS.
c) Find the basic solution in which x1 & x2 are basic. Is this a BFS?
s1 = s2 = 0, so x1 = 10/3 and x2 = 4/3. So the basic solution is (10/3,4/3,0,0) which is feasible
and so as a BSF.
The reduced cost for x1 is 5 and for x2 is 3.
Problem 4.3 (Properties of standard form polyhedron): Consider a linear optimization problem in
standard form, i.e., minimize x subject to , where x, b, Ax, and b. For each of the following
statements, state whether it is true or false. If true, provide a justification, else, provide a
counterexample.
a. At every optimal solution, no more than M variables can be positive: This statement is
false. Consider the standard problem, minimize x1 subject to x1 = 1 and x1 >=0 and x2
>=0. For this problem, (x1, x2) = (1, B) is an optimal solution where B is positive value.
Here we see that for when B is zero, M is 1 but for other values of B, M is 2. So we see
M is 1 here for the solution (x1, x2) = (1, 0) where M is less than the number of variable,
2.
b. If there is more than one optimal solution, there are infinitely many optimal solutions.:
This statement is true. We know from Convex Set definition that If x1 and x2 are two
points, all the points x1 + (1)x2 are also in the Convex set. And we know BFS are part
of Convex set as F is a Convex set. So there will be other solutions like (x1 + (1)x2) for
[0,1].
c. If there is more than one optimal solution, then there are at least two BFSs that are
optimal: This statement is false. Let us consider the example in (a). There are infinite
number of solutions but only one BFS which is (x1, x2) = (1, 0).
REVIEW QUESTIONS
3.1 Define a line segment in ndimensional space.
Answer: A point X in an ndimensional space is characterized by an ordered set of n values or
coordinates (x1,x2,. . .,xn). The coordinates of X are also called the components of X.
If the coordinates of two points A and B are given by xj(1) and xj(2) (j = 1,2,. . . ,n), the line segment
(L) joining these points is the collection of points X (λ) whose coordinates are given by xj= λ xj(1)
+(1 λ ) xj(2) where j = 1,2,. . . ,n with 0 < λ< 1.
Thus
L = {X|X=λXj(1) +(1 λ )Xj(2) }
3.2 What happens when m = n in a (standard) LP problem?
Answer: There is either a unique solution X that satisfies Eqs. (3.2) and (3.3) (in which case
there can be no optimization) or no solution, in which case the constraints are inconsistent
3.3 How many basic solutions can an LP problem have?
Answer: This about choosing nm nonbasic variables from n variables. So it is =
n!/((nm)! x m!)
3.4 State an LP problem in standard form.
Answer: The characteristics of a linear programming problem, stated in the standard
form, are:
I. The objective function is of the minimization type.
II. All the constraints are of the equality type.
III. All the decision variables are nonnegative.
3.5 State four applications of linear programming.
Answer:
I. Oil Refinery: In general, an oil refinery has a choice of buying crude oil from several
different sources with differing compositions and at differing prices. It can manufacture
different products, such as aviation fuel, diesel fuel, and gasoline, in varying quantities.
The constraints may be due to the restrictions on the quantity of the crude oil available
from a particular source, the capacity of the refinery to produce a particular product, and
so on. A mix of the purchased crude oil and the manufactured products is sought that
gives the maximum profit.
II. In Production Firm: The optimal production plan in a manufacturing firm can also be
decided using linear programming. Since the sales of a firm fluctuate, the company can
have various options. It can build up an inventory of the manufactured products to carry
it through the period of peak sales, but this involves an inventory holding cost. It can also
pay overtime rates to achieve higher production during periods of higher demand.
Finally, the firm need not meet the extra sales demand during the peak sales period,
thus losing a potential profit. Linear programming can take into account the various cost
and loss factors and arrive at the most profitable production plan.
III. Food Processing Industry: In the foodprocessing industry, linear programming has
been used to determine the optimal shipping plan for the distribution of a particular
product from different manufacturing plants to various warehouses.
IV. Circuit Switched Network: LP used to find the optimal routing.
3.6 Why is linear programming important in several types of industries?
Answer: Every industries do seek maximum profit or minimum cost with using the available
resources they have. Linear programming enables industries and companies to find optimal
solutions to economic decisions. Generally, this means maximizing profits and minimizing
costs.
3.7 Define the following terms: point, hyperplane, convex set, extreme point.
Answer:
I. Point: A point is represented as an ordered set of coordinates. More specifically a point
X in an ndimensional space is represented as an ordered set of n values or coordinates
(x1, x2,. . .,xn)
II. Hyperplane: In ndimensional space, the set of points whose coordinates satisfy a linear
equation a1x1 + • • • + anxn = aX = b is called a hyperplane. A hyperplane, H, is represented as
H(a,b) = {X|aX = b}
III. Convex Set: A convex set is a collection of points such that if X(1 ) and X(2) are any two points in
the collection, the line segment joining them is also in the collection. A convex set, S, can be
defined mathematically as follows: If X ( 1 ) ,X ( 2 ) S , then X S where X = X(1) + (1 )X(2), 0 <= <=
1
IV. Extreme Point: This is a point in the convex set that does not lie on a line segment
joining two other points of the set. For example, every point on the circumference of a
circle and each corner point of a polygon can be called a vertex or extreme point
3.8 What is a basis?
Answer: The collection of variables not set equal to zero to obtain the basic solution is called the
basis.
3.9 What is a pivot operation?
Answer: This procedure of eliminating a particular variable from all but one equations is called a
pivot operation.
3.10 What is the difference between a convex polyhedron and a convex polytope?
Answer: A convex polyhedron is a set of points common to one or more halfspaces. A convex
polyhedron that is bounded is called a convex polytope. That is, convex polytope is a subset of
convex polyhedron. That is, all the convex polytope are convex polyhedron but opposite is not
true.
3.11 What is a basic degenerate solution?
Answer: If any of the basic variables has a zero value in a basic solution, that solution is degenrate
solution.
3.12 What is the difference between the simplex algorithm and the simplex method?
Answer: Simplex Method is a complete procedure to solve an LP problem whereas simplex
algorithm is an algorithm that is used in simplex method to find BFS in phase i and optimal
solution in phase ii.
3.13 How do you identify the optimum solution in the simplex method?
Answer: When all the elements in Z row or cost row are non zero in a iteration, we’ll then be
sure that the BFS at that iteration is an optimal solution.
3.14 Define the infeasibility form.
Answer: If w = y1 + y2+ • • • + ym, w is called the infeasibility form and has the property that if as a
result of phase I, with a minimum of w > 0, no feasible solution exists for the original linear
programming problem and thus the procedure is terminated. On the other hand, if the minimum
of w = 0, the resulting array will be in canonical form and hence initiate phase II by eliminating
the w equation as well as the columns corresponding to each of the artificial variables y1 y2, • • •
, ym from the array
3.15 What is the difference between a slack and a surplus variable?
Answer: Slack variable is added in left side to a constraint if the constraints is of ‘less than or
equal to’ whereas Surplus is subtracted from the constraint if the constraints is of type ‘greater
than or equal to’
3.16 Can a slack variable be part of the basis at the optimum solution of an LP problem?
Answer: No. Optimal solution is the solution that has positive value for the decision variables
that appear in objective function. As slack variable does not appear in objective function (or
appear with zero coefficient), so it can’t have positive value in optimal solution. In fact, if a slack
variable has a value other than zero in the basis at the end of tableau iteration, it means the
problem is of unbounded, that is has no optimal solution.
3.17 Can an artificial variable be in the basis at the optimum point of an LP problem?
Answer: No. The same reason as 3.16.
3.18 How do you detect an unbounded solution in the simplex procedure?
Answer: It at any iteration of simplex method, if no departing non basic variable, the problem is
said to be unbounded.
3.19 How do you identify the presence of multiple optima in the simplex method?
Answer: If any non basic variable in the z row has a 0 value in any iteration, it means the
problem has multiple optima.
3.20 What is a canonical form?
Answer:
Assuming that the above set of equations possesses a unique solution, a method of solving the
system consists of reducing the equations to a form by applying elementary operations of the
form kEr and/or Er + kEs known as canonical form. For the above equations, the canonical form
will be a identity matrix.
3.21 Answer true or false.
(a) The feasible region of an LP problem is always bounded.: False
(b) An LP problem will have infinite solutions whenever a constraint is redundant.: False
(c) The optimum solution of an LP problem always lies at a vertex. : True
(d) A linear function is always convex. : False
(e) The feasible space of some LP problems can be nonconvex.: False
(f) The variables must be nonnegative in a standard LP problem. : True
(g) The optimal solution of an LP problem can be called the optimal basic solution.: False
(h) Every basic solution represents an extreme point of the convex set of feasible solutions.:
False
(i) We can generate all the basic solutions of an LP problem using pivot operations.: True
(j) The simplex algorithm permits us to move from one basic solution to another basic solution.:
True
(k) The slack and surplus variables can be unrestricted in sign.: False
(l) An LP problem will have an infinite number of feasible solutions.: True
(m) An LP problem will have an infinite number of basic feasible solutions.: True
(n) The righthandside constants can assume negative values during the simplex procedure.:
False
(o) All the righthandside constants can be zero in an LP problem.: True
(p) The cost coefficient corresponding to a nonbasic variable can be positive in a basic feasible
solution.; : False
(q) If all elements in the pivot column are negative, the LP problem will not have a feasible
solution.: False
(r) A basic degenerate solution can have negative values for some of the variables.: False
(s) If a greaterthan or equalto type of constraint is active at the optimum point, the
corresponding surplus variable must have a positive value.: True
(t) A pivot operation brings a nonbasic variable into the basis.: True
(u) The optimum solution of an LP problem cannot contain slack variables in the basis.: True
(v) If the infeasibility form has a nonzero value at the end of phase I, it indicates an unbounded
solution to the LP problem.: True
(w) The solution of an LP problem can be a local optimum. False
(x) In a standard LP problem, all the cost coefficients will be positive.: False
(y) In an standard LP problem, all the righthandside constants will be positive.: True
(z) In a LP problem, the number of inequality constraints cannot exceed the number of
variables.: True
(aa) A basic feasible solution cannot have zero value for any of the variables.: False