Question

A constraint in an LP model becomes redundant because \[\]
A. Two iso-profit lines may be parallel to each other\[\]
B. The solution is unbounded \[\]
C. The constraint is not satisfied by the solution values \[\]
D. None of the above\[\]

Answer 1

Hint: We recall the definitions of iso-profit lines, unbounded solution, feasible region and redundant constraints. We show with a two-variable cost function that the feasible region doesn’t change because of redundant constraints and is not related to iso-profit lines, unbounded solutions. \[\]

Complete step-by-step solution
We know that in linear programming problems or LPP the output is the profit or cost function. The cost or profit function is the function which has to be optimized that is minimized or maximized. It is expressed in the standard from of the LPP with $n$ linear variables ${{x}_{1}},{{x}_{2}},...,{{x}_{n}}$ and their respective costs ${{c}_{1}},{{c}_{2}},...{{c}_{n}}$ as
\[C\left( x \right)={{c}_{1}}{{x}_{1}}+{{c}_{2}}{{x}_{2}}+...{{c}_{n}}\]
We suppose that the cost has to be minimized. We define the problem constraints ( for the cost function as
\[\begin{align}
  & {{a}_{11}}{{x}_{1}}+{{a}_{12}}{{x}_{2}}+...+{{a}_{1n}}{{x}_{n}}\le {{b}_{1}} \\
 & {{a}_{21}}{{x}_{1}}+{{a}_{22}}{{x}_{2}}+...+{{a}_{2n}}{{x}_{n}}\le {{b}_{2}} \\
 & \vdots \\
 & {{a}_{m1}}{{x}_{1}}+{{a}_{m2}}{{x}_{2}}+...+{{a}_{mn}}{{x}_{n}}\le {{b}_{m}} \\
\end{align}\]
The non-negative constraints are,
\[{{x}_{1}},{{x}_{2}},...,{{x}_{n}}\ge 0\]
The redundant constraint of the constraint ${{a}_{1}}{{x}_{1}}+{{a}_{2}}{{x}_{2}}+...+{{a}_{n}}{{x}_{n}}\le b$ is defined as $k{{a}_{1}}{{x}_{1}}+k{{a}_{2}}{{x}_{2}}+...+k{{a}_{n}}{{x}_{n}}\le kb$ where $k$ is a non-zero real number.
Let us observe it for 2 variables $x,y$in the two dimensional plane. We define the profit function as with profits ${{c}_{1}},{{c}_{2}}$ as
\[C\left( x \right)={{c}_{1}}x+{{c}_{2}}y....\left( 1 \right)\]
We have to maximize it. We have the non-negative constraint ${{x}_{1}},{{x}_{2}}>0$ and we define a problem constraint as
\[ax+by < d...\left( 2 \right)\]
We convert all the inequality constraints into equalities and plot all the lines to find a graphical solution. \[\]

The blue shaded region of the interior triangle ABC is called feasible because all the points on it satisfy the problem constraints and non-negative constraints. Every point in the feasible region is called a feasible solution and the vertex where $C\left( x \right)$ is optimum is called an optimal solution. If we define a redundant constraint for (2) we have for some nonzero real constant $k$
\[kax+kby < kd...\left( 3 \right)\]
If we plot the above constraint by converting to equality it will be the same line as AC and it won’t change the feasible region. Let us check the options now. \[\]
A. Iso-profit lines are the lines representing the cost function and their parallel existence is not related to the redundant constraint. So A is not correct. \[\]
B. If the feasible region is not a closed curve and each point is called an unbounded solution. It is not related to redundancy, its constraints, and B is incorrect. \[\]
C. A point outside the feasible region may not be satisfied by one or more of the constraints. It is not related to redundancy, is constrained and C is incorrect. \[\]
So the correct option is D. \[\]

Note: There are different methods to deal and remove redundant constraints in LPP for example using linear combinations in vector spaces. We also note that the feasible region is convex set which means the line segment joining two points in the region will not have any point outside it.