How to solve LP problems using Simplex Method?

How to construct a linear programming model? 

In the chapters on linear programming problem formulation and graphical method, we have seen how to convert a word problem into a LP model and how to solve that using the graphical method, respectively. The graphical method of linear programming is now useful when a LP problem involves two variables. However, if there is a third or a fourth variable, then the graphical method loses its utility.

In those cases, simplex methods can be easily used to solve linear programming problems. The simplex method can help in solving problems that involve any number of variables and constraints. This number can go to hundreds or even thousands. This technique is also used by computer programs to solve linear programming problems, so we will see the various steps of solving these problems using the simplex method with the help of an example.

Example: 

So, the example at hand is that a manufacturer specializing in the manufacture of gears intends to add two more types of gears to his existing product line. Both types of gear will be worked on in the blanking shop and in the gear shop. Now each gear of type “A” requires 20 minutes in the blanking shop and 40 minutes in the gear shop. Similarly, each gear of type “B” requires 10 minutes in the blanking shop and 10 minutes in the gear shop. Now the blanking shop and the gear shop have, respectively, 1200 and 1600 minutes available per week.

The marginal profit for each gear of type “A” is 10/-, and for each gear of type B, it is 4/-. The manufacturer is on the market upswing and can sell as much as he can produce. How many units of each gear should be produced to maximize profits?

Analysis: So basically, this manufacturer is in the business of manufacturing gears and he wants to add two more types of gears to his product line. Now both these types of gears have to go through a blanking shop and a gear shop. These are two different departments which have different types of machines and each of these product types has to go through each of these shops to be converted into the final product. Blanking shop can be used only for 1200 minutes while gear shop can be used for a maximum of 1600 minutes per week. Also we have been given that each year of type “A” generates a profit of rupees 10 while each year of type “B” generates a profit of rupees 4. Now of course we want to maximize our profits and we do have some constraints in terms of the time of variability of the blanking and the gear shop. So, we want to find out how many units of each gear should be produced in order to maximize our profits.

Solution:

Let us see how we can use the simplex method to solve this linear programming problem.

Step 1: Construction of a LP model. 

x1 = quantity of A to be produced

x2 = quantity of B to be produced

So the profits will be 10 x 1 and 4 x 2 respectively. 

Maximize P = 10 x 1 + 4 x 2

20 x 1 + 10 x 21 200; 40 x 1+10 x 21600 x1, x20

Therefore, Maximize P = 10 x 1 + 4 x 2

Subject to: 20×1+10×21200; 40×1+10×21600; x1, x20

1. The R.H.S of each constraint should be non negative.

• 8×1-3×2-6
• -8×1+3×26 (Multiplied the above equation by -1)

1. Each of the decision variables of the problem should be non negative. 

Max Z=5×1+7×2-2×3

2×1+5×2+3×380; 5×1+2×2-2×330

So now this is the LP model that we will solve and once the values of X 4 and X 5 are obtained using the simplex method then we can easily find the value of x 3 so if both these conditions are met, which in our case are met then we can proceed with the next step which is standardization of the problem.