Linear Programming

LPP is a technique of mathematical modeling to solve real life problems whose requirements are given in linear relations. It helps to find “best” solution (minimum and maximum) under given conditions.
It is a type of optimization problem that determines the feasible region (a region that contains all the possible solutions of an LPP) and optimizes the solution to get the maximum or minimum function value.
In simple terms, a linear programming problem is a set of linear equations that are used to find the value of variables to optimize the objective functions. LPP can be solved in two different ways.

LPP (linear programming problem) वास्तविक जीवनका समस्याहरू समाधान गर्ने एक गणितीय मोडलिङ हो जसको शर्तहरु रेखिय सम्बन्धमा दिएको हुन्छ । यसले दिइएको अवस्थाहरूमा “उत्तम” समाधान (न्यूनतम वा अधिकतम) को बारेमा थाहा पाउन मद्दत गर्दछ।
यो एक प्रकारको अप्टिमाइजेसन समस्या हो जसले सम्भाव्य क्षेत्र (सबै सम्भावित समाधानहरू समावेश गर्ने क्षेत्र) निर्धारण गर्छ र अधिकतम वा न्यूनतम मान प्राप्त गर्न मद्दत गर्छ ।
समान्य भाडषामा, LPP (linear programming problem) भनेको रेखिय समीकरणहरूको समुह हो जसबाट “उत्तम” समाधान (न्यूनतम वा अधिकतम) को खोज गरिन्छ।

Linear Programming Applications_Example 1

Let us take a real-life problem to understand linear programming.
A company produces two types of pots X and Y by using copper and steel. Type X pot requires 300 g of copper and 100 g of steel while Y requires 100 gram of copper and 200 grams of steel. The X pot brings profit of Rs. 400 and the Y pot brings profit of Rs. 500. Find the number of units of each type of pots that the company should produce with 5kg copper and 12kg of steel to achieve maximum profit.
Given the situation, let us take up different scenarios to analyse how the profit can be maximized.

The company can decide to produces X type pots, in this case, he can create 5000/100= 50 copper slot, 12000/200=60 steel slot. This would give him to produce 50 pots with a profit of Rs 500×50 = Rs 12500.
The company can decide to produces Y type pots, in this case, he can create 5000/300= 16 copper slot, 12000/100=120 steel slot. This would give him to produce 16 pots with a profit of Rs 400×14 = Rs 6400.
Similarly, there can be many strategies which the company can devise to maximize his profit by allocating the available row materials to the two types of pots. We do a mathematical formulation of the discussed LPP to find out the strategy which would lead to maximum profit.

Linear Programming Applications_Example 2

A home decorator company received an order to manufacture tables. The first consignment requires up to 50 tables. There are two types of tables, The first type requires 15 hours of the labour force (per piece) to be constructed and gives a profit of Rs 5000 per piece to the company. Whereas, the second type requires 9 hours of the labour force and makes a profit of Rs 3000 per piece. However, the company has only 540 hours of workforce available for the manufacture of the tables. With this information given, you are required to find a deal which gives the maximum profit to the company.

Given the situation, let us take up different scenarios to analyse how the profit can be maximized.

He decides to construct all the tablesof the first type. In this case, he can create 540/15 = 36 tables. This would give him a profit of Rs 5000 × 36 = Rs 180,000.
He decides to construct all the tables of the second type. In this case, he can create 540/9 = 60 tables. But the first consignment requires only up to 50 cabinets. Hence, he can make profit of Rs 3000 × 50 = Rs 150,000.
He decides to make 15 tables of type 1 and 35 of type 2. In this case, his profit is (5000 × 15 + 3000 × 35) Rs 180,000.

Similarly, there can be many strategies which he can devise to maximize his profit by allocating the different amount of labour force to the two types of tables. We do a mathematical formulation of the discussed LPP to find out the strategy which would lead to maximum profit.

Basic terminologies of LPP

Decision Variable: These are quantities to be determined.
Objective Function: The function that need to optimized.
Constraints: Linear equations that represents decision variables on how to use the available resource (for example, amount of time, number of people, etc.)
Feasible Solution: Set all the possible solutions that satisfy the given constants.
Optimal Solution: It is the best possible solution among all the possible feasible solutions.
Slack Variables : Slack variable represents an unused quaintly of resources ; it is added to less than or equal (<) to type constraints in order to get an equality constraint.
Surplus Variables : A surplus variable represents the amount by which solution values exceed a resource. These variables are also called ‘Negative Slack Variables’. Surplus variables carry a zero coefficient in the objective function. it is added to greater than or equal to (>) type constraints in order to get an equality constraint.

Characteristics of LPP

Decision variables will decide the output.
The objective function should be specified quantitatively.
Constraints (limitations) should be expressed in mathematical form.
Relationships between two or more variables should be linear.
The values of the variables should always be non-negative or zero.

Methods of Solving LPP

LPP बिभिन्न तरिकाबाट हल गर्न सकिन्छ।

Graphical method
Simplex method
North West Corner Method
Least Square Methods

Graphical Methods of Solving LPP

LPP models can be solved by graphical method if two variable are presented in the model.
The general process while solving LPP by graphical methods, are given below

graph the inequalities (constraints)
form walled-off region (feasible region)
find the corner points in feasible region
test corner points in the object function
find the solution (maximum or minimum)

Simplex Methods of Solving LPP

LPP models can be solved by simplex method if two or more variable are presented in the model.
The general process while solving LPP by simplex methods, are given below

Convert subjective function with ≤ inequality (standard form)
Introduce slack variables to convert inequality into equation
Prepare simplex table
Find pivot element [column (negative, lowest), Find pivot row (positive, lowest)]
Convert pivot element to 1 and else to zero
If optimal solution is NOT reached, iterate the process from 4 onwards

A company produces two types of pots X and Y by using copper and steel. Type X pot requires 300 g of copper and 100 g of steel while Y requires 100 gram of copper and 200 grams of steel. The X pot brings profit of Rs. 400 and the Y pot brings profit of Rs. 500. Find the number of units of each type of pots that the company should produce with 5kg copper and 12kg of steel to achieve maximum profit.

Solution

The decision variables: Since the question has asked for an optimum number of pots, that’s what our decision variables is. Let us say
x = number of X pots produced
y = number of Y pots produced
The constraints: Since the company can’t produce a negative number of pots, a natural constraint is:
x ≥ 0
y ≥ 0

The subjective function

pots	copper	steel	Profit
X	300	100	400
Y	100	200	500
Availability	5000	12000	?

Given
Each unit of X requires 300 unit of copper and 100 units of steel
Each unit of Y requires 100 unit of copper and 200 units of steel
The company has a total of 5 kg (5000 g) of copper and 12 kg (12000 g) of steel.
Thus, the subjective functions are
300x+100y≤5000
100x+200y≤12000

The objective function
We need to optimize the Profit. On each sale, the company makes a profit of
Rs 400 per unit X sold.
Rs 500 per unit Y sold.
The Profit Function is:
Z =400x + 500y
LPP modeling
Therefore, the LPP model is (in 100) is
Maximize Z = 4x + 5y, subject to:
3x+1y≤50
1x+2y≤120
x ≥ 0
y ≥ 0

Solution

Step 1: graph the inequalities (constraints)
We plot the following inequalities in a graph.

$2x + y \le 100$
Let us take a table for plot points

x	0	50
y	100	0

The graph is given below.

$x + y \le 80$
Let us take a table for plot points

x	0	80
y	80	0

The graph is shown with a label.

$x \ge 0,x \ge 0$
The graph is shown with a label.

Step 2: form a walled-off region (feasible region)
In this LPP, the feasible region is a polygon OABC labeled in the graph.

Step 3: find the corner points in the feasible region
In this LPP, the corner points of polygon OABC are O = (0,0), A = (16.5,0), D= (0,50)
NOTE: The corner point are obtained by solving two equations, which do intersect

Step 4: test corner points in the object function

Objective function	Point	Value	Remarks
Z=4x+5y	(0,0)	$Z=4\times 0+5\times 0=0$	Minimum
Z=4x+5y	(16.5,0)	$Z=4\times 16.5+5\times 0=66$
Z=4x+5y	(0,50)	$Z=4\times 0+5\times 50=250$	Maximum

Step 5: find the solution (maximum or minimum)
The maximum value of the function Z = 4x + 5y is 250 at the point (0,50)
The minimum value of the function Z = 4x + 5y is 0 at the point (0,0).
The graphical solution of this modeling can be shown below.

In the LPP, the graphical method is very useful in lower dimensions. If we have more than two variables then we’re looking at some higher dimensional shape, then we can’t interpret anything easily in three dimensions visually. Therefore, the simplex method gives an algorithm for solving these problems with any number of variables. Graphical method can be applied in 2D. In 3D and higher dimensions+, identifying an optimal solution using the graphical method is no longer feasible.So, simplex method can be applied to 1D, 2D, 3D and 3D+ linear programs. In other words, simplex method can be used for theoretically unlimited amounts of optimization variables

The general process for solving the maximization LPP model by the simplex method is given below

Convert subjective function with $\le$ inequality (standard form)
Introduce slack variables to convert inequality into an equation
Prepare simplex table
Find the pivot column (negative, lowest)
Find pivot row (positive, lowest)
Find pivot element
Convert pivot element to 1 and else to zero
Iterate the process from 4 onwards

Test your understandings

Why do we make an objective function with a negative coefficient?
The initial simplex table represents an augmented matrix, where slack variables form an identity matrix.

In an LPP model
Maximize $z = 400x + 500y$ , subject to:
$300x+100y \le 5000$
$100X+200y \le 12000$

x	y	u	v	z
300	100	1	0	0	5000
100	200	0	1	0	12000
-400	-500	0	0	1	0

the objective function is z=400x+500y, which is in the linear form written as z-400x-500y=0 in order to produce a unit matrix as shown in the table above

Why do we choose the most negative entry in the bottom row?

We know that the simplex method begins at a corner point where all the main variables are zero. It then moves from a corner point to the adjacent corner point always increasing the value of the objective function.
when we choose the most negative entry in the bottom row, we are trying to increase the value of the objective function ,
for example, the coefficient of y (which is 500) , this entry will increase the value of the objective function the quickest

Why do we find quotients, and why does the smallest quotient identify a row?
When we choose the most negative entry in the bottom row, we are trying to increase the value of the objective function by bringing in the variable, say y [in the example below]. But we cannot choose any value for y. Therefore, using the lowest quotients guarantees that we do not violate the constraints and that the effect is high to increase the value of the objective function.

x	y	u	v	z		ratio
300	100	1	0	0	5000	5000/100=50
100	200	0	1	0	12000	12000/200=60
-400	-500	0	0	1	0

For example,

in a model, Maximize $z = 400x + 500y$ , subject to:
$300𝑥+100𝑦 \le 5000$
$100x+200𝑦 \le 12000$
the smallest ratio is 50, which ensures the validity of the constraints

Why do we identify the pivot element?
The simplex method begins with a corner point and then moves to the next corner point to improve the value of the objective function. Therefore, the value of the objective function is improved by changing the number of units of the variables. We may add the number of units of one variable while throwing away the units of another. Pivoting allows us to do just that and help us to utilize available resources

x	y	u	v	z		ratio
300	100	1	0	0	5000	5000/100=50
100	200	0	1	0	12000	12000/200=60
-400	-500	0	0	1	0

For example,

in a model, Maximize $z = 400x + 500y$ , subject to:
$300𝑥+100𝑦 \le 5000$
$100x+200𝑦 \le 12000$

the value of the objective function is improved by changing the number 100[a12] to 1 and else to zero

Why are we finished when there are no negative entries in the bottom row?
Since all variables are non-negative, the highest value that can be achieved is guaranteed.

Example 1

Find the maximum value of the following LPP problem.
Maximize: Z = 50x + 18y
Subject to: $2x + y \le 100, x + y \le 80, x \ge 0 , y\ge 0$

Example 2

Find the maximum value of the following LPP problem.
Maximize: Z = 25x + 40y
Subject to: $2x + y \le 10, x + 2y \le 6, x \ge 0 , y\ge 0$

Solution

Step 1: Since all the subjective function are with $\le$ inequality, Prepare a simplex Tableaux

x	y	u	v
2	1	1	0	10
1	2	0	1	6
-25	-40	0	0	0

Step 2: Find the pivot column, pivot row, and pivot element.
(a) Largest negative entry is -40, thus $C_2$ is the pivot column.
(b) Smallest positive ratio is 3, thus $R_2$ is the pivot row.
(c) Based on (a) and (b), 2 is the pivot element.

x	y	u	v			ratio
2	1	1	0	10		$\frac{10}{1}=10$
1	2	0	1	6	⇐	$\frac{6}{2}=3$
-25	-40	0	0	0
	⇑

Step 3: Operating Row equivalent operation, convert pivot element 2 to 1, and else to 0.

x	y	u	v		Operation	Stage
3/2	0	1	-1/2	7	$R_1 \approx R_1-R_2$	2
1/2	1	0	1/2	3	$R_2 \approx \frac{1}{2} R_2$	1
-5	0	0	20	120	$R_3 \approx R_3+40 R_2$	3

Step 4: Since a negative entry is found in row 3, again iterate the process to find the pivot column, pivot row, and pivot element.
(a) Largest negative entry is -5, thus $C_1$ is the pivot column.
(b) Smallest positive ratio is 14/3, thus $R_1$ is the pivot row.
(c) Based on (a) and (b), $3/2$ is the pivot element.