class 12 simplex method chapter full notes

    by lalmani gautam

   sept 20                                                

                                                          Linear programming

  Introduction 

 linear programming problem is basically used in planning in business and economics, industry, engineering design e.t. c.

 OR

 Linear programming problems deals to maximum or minimum allocation value or optimum value. fundamental terms used in linear programming problem.

1) Decision variable : Those non-negative and independent variables which are used in the solution of the linear programming problem are the decision variables. i.e the decision variables may be men, materials machine etc.

 2) Objective function :An objective function defines the quantity to be optimized, and the goal of linear programming is to find the values of the variables that maximize or minimize the objective function. for example 2x + 3y

 3) Constraints: In case of solving the linear programming problem, the decision variables have to satisfy certain conditions or restrictions. The conditions to be satisfied by the decision variables are known as the constrains. Generally constrains are in inequality form.

 e.g. To solve some problem we have given

 6𝑥 +7𝑦 ≤ 23 etc

                   Linear programming problems 

A mathematical procedure for determining the best outcomes of an objective function in a region satisfying set of constrains is called a linear programming. 

A linear programming problem in two variables is a problem in which we are asked to find the maximum (or minimum) value of a linear objective function.

 𝑓( 𝑥, 𝑦) = 𝑎𝑥 + 𝑏𝑦 subject to set of linear constrains of the form α𝑥 + β𝑦 ≤ 𝑜𝑟 ≥ Υ where x and y are known as decision variables.

 

Mathematical formulation of linear programming problem

A linear programming is defined as

 Optimize z = ax1 +bx2

 subjected to a set of linear constrains of the form

 𝑎11𝑥1 + 𝑎12 𝑥2 ≤ b1

 𝑎22 𝑥1 + 𝑎23 𝑥2 ≤ 𝑏2

 𝑎31 𝑥1 + 𝑎32 𝑥2 ≤ 𝑏3 

where x1 , x2 ≥0, bi ≥ 0, i = 1,2,3

 The linear function z = ax1 +bx2 which is the optimized is the objective function. The variables x1 , x2 present in the objective function and the constraians are the decision variables. The conditions x1 ≥0 and x2≥0 are known as the non negativity constrains of the decision variables.

Example

 1. An expensive model of a manufactured item yields a net profit of Rs.20 on each one sold , and a cheaper model brings a profit of only Rs.10 each. If x and y denote the respective number of the expansive and cheaper model produced items per unit of times, find the objective function.

  solution :

 Here,   Profit on a unit expansive model item = Rs.20 

profit on x units of expansive model items = Rs.20x

 again profit on a unit cheaper model item = Rs.10

 profit on y units of cheaper model items = Rs.10y 

Total profit = Rs.20x +Rs.10y

 The objective function is 𝑓 𝑥, 𝑦 = 𝑅𝑠. 20𝑥 + 𝑅𝑠. 10𝑦

 5. A carpenter has 60, 40,and 25 meters of teak, plywood and rosewood respectively. The product A requires 2,1,2 meters and the products B requires 3,2,1 meters of teak, plywood and rosewood respectively. If A would sell for Rs.2560 and B would sell for Rs.1840 per unit . Give a mathematical formulation of the above LP problem for the maximum income.

Soln:

 Let x and y be the number of products of A and B respectively. Given problem can be expressed in table as below

Let F(x,y) be the objective function, then the mathematical formulation of LPP can be formulated as follows

: Maximize: F( x, y) = Rs 2560x+ Rs1840y

 Subject to: 2x + 3y ≤ 60; x + 2y ≤ 40, 2x + y ≤ 25; x, y ≥ 0.

2 a) A manufacturer uses two machines to produce two items A and B the profit on each item A is Rs.6 on each one sold and on each items B Rs.8. If x and y denote the respective number of the articles A and B that should be produced each day, find the objective function.

Solution :

        Here, the profit of 1 unit of article of type A is Rs.6 

        So, the profit of x articles of type A=Rs.6x

 Similarly , the profit 1 unit of article of type B is Rs.8 

      So, the profit of y articles of type B=Rs.8y

          ∴ total profit = Rs.6x+ Rs.8y

      Hence , the objective function is

           F( x, y) = Rs.6x+ Rs.8y

4a)  A watch dealer wishes to buy new watches and has two models 𝑀1and 𝑀2 to choose . Model 𝑀1 costs Rs 100 and 𝑀2 costs Rs.200. In view of the showcase of the dealer, he wants to buy watches not more then 30 and can spent upto Rs. 4000. The watch dealer can make a profit of Rs20 in 𝑀1 and Rs.50 𝑀2.Formulate the above linear programming problem for maximum profit.

Solution :

   let x and y be the number of watches of model 𝑀1 and 𝑀2. 

Total profit on x watches of model 𝑀1 and y watches of model 𝑀2

        = Rs.20x + Rs.50y

 Here, total no of watches = x +y

      Max.no of watches to buy=30

     ∴ x +y≤ 30 ………………(i) 

   Total expenditure to models of watches =100x +200y

Max. expenditure that can spend=4000

    100 x +200y≤ 4000

   i.e x +2y≤ 40

  ∴ the mathematical formulation of the problem

  Max profit F( x, y) = Rs.20x + Rs.50y

subjected to constrains

    x +y≤ 30 ………………(i) 

   x +2y≤ 40 …………….(ii)

      x ,y ≥ 0 

                                                      Simplex method

   Simplex method: 

 Simplex method is alternative method of graphical method of linear programming problem to solve this method we put given problem in simplex tableau to find the optimum value. This method is defined only for maximization Lp problem.

   Slack variables 

A non–negative variable r which is added on the left side on an inequation of the form 𝐴𝑥 ≤ 𝐵 turns the inequations into equation of the form 𝐴𝑥 + 𝑟 = 𝐵, r≥ 0 is known as slack variable.

    Surplus variable

 A non–negative variable s which on the subtraction the left side on an inequation of the form 𝐴𝑥 ≥ 𝐵 turns the inequations into equation of the form 𝐴𝑥 − 𝑠 = 𝐵,s≥ 0 is known as surplus variable

Standard form of a maximization problem in two variables. 

A linear programming problem is in standard form if it seeks to maximize the objective function 

𝑓 (𝑥, 𝑦 )= 𝛼𝑥 + 𝛽𝑦 

Subjected to the constrains

 𝛼1𝑥 + 𝛽1𝑦 ≤ 𝛾1

 𝛼2𝑥 + 𝛽2𝑦 ≤ 𝛾2

 …. … …. 

𝛼𝑚𝑥 + 𝛽𝑚𝑦 ≤ 𝛾𝑚

 where, 𝑥, 𝑦 ≥ 0 𝑎𝑛𝑑𝛾𝑚 ≥ 0

 After adding slack variables, we get the following equations

 𝛼1𝑥 + 𝛽1𝑦 + 𝑟1 = 𝛾1

 𝛼2𝑥 + 𝛽2𝑦 + 𝑟2 = 𝛾2

…. ….. …… 

𝛼𝑚𝑥 + 𝛽𝑚𝑦 + 𝑟𝑚 = 𝛾𝑚 for 𝑟𝑚 ≥ 0 and 𝑥, 𝑦 ≥ 0 

The Characteristics of the standard form of the linear programming problem.

 • All constrains are expressed in the equation form.

 • The right hand member of each constrain is non negative. If not we make it non-negative by multiplying both sides by -1.

 • All the variables involved are non –negative.

 • The objective function is of the maximization type .If the problem is of minimization type , we convert it by multiplying the objective function by -1

 Note : Basic and non-basic variable 

The variables that are non-zero are called basic variables and the variables that are zero are called non –Basic variables

Optimality check

 Observing the bottom row of the tableau, if any of these entries are negative, the current solution is not optimal.

 Iteration of Simplex Method

 An improvement process for finding larger F-value, which brings a new basic variable into the solution , the entering variables and in the mean while one of the current basic variables must leave.

 i) The entering variables corresponding to the smallest(the most negative) entry in the bottom row of the tableau.

 ii) The departing variable corresponds to the smallest non negative ratio of 𝛾𝑖 𝑎𝑖𝑗 in the 𝑗 𝑡ℎ column determine by the entering variables.

 iii) The entry in the simplex tableau in the entering variable column and departing variable row is called pivot entry

1) Reformulate the following Linear programming problems into standard form 

      a) we have given problem 

   Maximize p = 20x +30y 

         subject to constrains 

       3x +y ≤ 15

     x +3y ≤12

        x,y ≥0

 Solution:

     let r and s be the non-negative slack variables. 

Then , 3x +y +𝑟= 15 

   x +3y +s=12

     Now, the reformulation of the given Lp problem in its standard form is 

   Maximum.P = 20x +30y + 0.r + 0.s 

   subject to constrains 

    3x +y +𝑟 + 0. 𝑠= 15

     x +3y +0.r +s=12