Linear Programming Problems (LPPs)

A Linear Programming Problem is one that is concerned with finding the optimal value (maximum or minimum value) of a linear function (called objective function) of several variables (say $x$ and $y$), subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints).

LPP

Canonical form of LPPs

Linear programming problems can be expressed in canonical form as:

Maximize $c^T x$ Subject to $AX \leq b$ and $X \geq 0$

Basic Solution

Basic solution is the solution of a problem which satisfy all the condition.

Basic Feasible Solution and Optimal Solution

In a linear programming problem, any solution that satisfy the conditions

$AX \leq b$ $X \geq 0$

is called a feasible solution.

Basic feasible solution (BFS) is the basic solution that satisfies the non-negativity conditions.

A feasible solution that optimized the objective function is called an optimal solution.

To find an optimal solution, it is sufficient to consider the basic feasible solutions.

PYQs

Linear Programming Problems (LPPs)

1) An agricultural firm has 180 tons of nitrogen fertilizer, 250 tons of phosphate and 220 tons of potash.It is able to sell a mixture of these substances in their respective ratio 3:3:4 at a profit of Rs. 1500 per ton and a mixture in the ratio 2:4:2 at a profit of Rs. 1200 per ton. Pose a linear programming problem to show how many tons of these two mixtures should be prepared to obtain the maximum profit.

[2018, 10M]

2) A paint factory produces both interior and exterior paint from materials $M_{1}$ and $M_{2}$ . The basic data is as follows:
$\begin{array}{|c|c|c|c|}\hline {} & \text {Exterior Paint} & \text {Interior Paint} & \text {Max. Daily Availability}\\ \hline \text { Raw Material } M_{1} & {6} & {4} & {24} \\ \hline \text { Raw Material } M_{2} & {1} & {2} & {2} \\ \hline \text { Profit per ton (Rs. 1000) } & {5} & {4} & { } \\ \hline\end{array}$

A market survey indicates that the daily demand interior paint cannot exceed that of exterior paint by more than 1 ton. The maximum daily demand of interior paint is 2 tons. The factory wants to determine the optimum product mix of interior and exterior paint that maximizes daily profits. Formulate the LP problem for this situation.

[2009, 12M]

3) Put the following program in standard form.
Minimize
$Z=25 x_{1}+30 x_{2}$, subject to:
$4 x_{1}+7 x_{2} \geq 1$
$\quad 8 x_{1}+5 x_{2} \geq 3$
$6 x_{1}+9 x_{2} \geq-2$
$x_{1}, x_{2} \geq 0$

[2005, 12M]

Basic Feasible Solution and Optimal Solution

1) How many basic solutions are there in the following linearly independent set of equations? Find all of them.

$2x_1-x_2+3x_3+x_4=6$ $4x_1-2x_2-x_3+2x_4=10$

[2018, 15M]`

2) Consider the following linear programming problem.
Maximize
$Z=x_{1}+2 x_{2}-3 x_{3}+4 x_{4}$ subject to:
$x_{1}+x_{2}+2 x_{3}+3 x_{4}=12$
$x_{2}+2 x_{3}+x_{4}=8$
$x_{1}, x_{2}, x_{3}, x_{4} \geq 0$
Without solving the problem, show that it has an optimal solution and which of the basic feasible solution(s) is/are optimal?

[2015, 10M]

3) Consider the following linear programming problem.
Maximize $Z=x_{1}+2 x_{2}-3 x_{3}+4 x_{4}$ subject to:
$x_{1}+x_{2}+2 x_{3}+3 x_{4}=12$
$x_{2}+2 x_{3}+x_{4}=8$
$x_{1}, x_{2}, x_{3}, x_{4} \geq 0$
Using the definition, find its all basic solutions. Which of these are degenerate basic feasible solutions and which are non-degenerate basic feasible solutions?

[2015, 10M]

4) For the following system of equations:
$x_{1}+x_{2}+x_{3}=3$
$2 x_{1}-x_{2}+3 x_{3}=4$
Determine:
i) All basic solutions
ii) All basic feasible solutions
iii) A feasible solution which is not a basic feasible solution

[2003, 12M]

5) Compute all basic feasible solutions of the linear programming problem.
Maximize $Z=2 x_{1}+3 x_{2}+2 x_{3}$, subject to
$2 x_{1}+3 x_{2}-x_{3}=8$
$x_{1}-2 x_{2}+6 x_{3}=-3$
$x_{1}, x_{2}, x_{3} \geq 0$,
and hence indicate the optimal solution.

[2001, 12M]

< Previous Next >