Course Outlines

Formulation of linear programming problem in three or more variables; 

Simplex method;

Dual problems;

Basic feasible solution and application of LPP.

Introduction 

·     Linear Programming: A mathematical procedure for determining the best outcome (such as maximum profit or lowest cost) of an objective function in a region satisfying set of constraints is called linear programming.

·     Objective function: Objective function is the function that is to be optimized. The goal of objective function is to maximized or to minimize the function.

·     Constraints: In case of solving the linear programming problem, the decision variables have to satisfy certain condition conditions or restrictions.

·     Graphical solution of LP problems

–       Feasible Region: A closed plane region in the xy-plane obtained by the finite intersection of the planes determined by the set of constraints, is known as the feasible region. The maximum and minimum value of the objective function occur at the vertices of the feasible region.

–       Simplex method in LP problems: Simplex method is the algebraic method used to solve the linear programming problems.

–       Slack variables: A non-negative variable which on adding on the left side of an inequality of the form Ax + By £ C changes the inequality into an equation of the form Ax + By + r = C (r£ 0) is known as slack variable.

–       Surplus variable: A non negative variable which on subtraction on the left side of an inequality of the type Ax + By £C changes the inequality into an equation of the type
Ax + By + s = C (s ≥ 0) is known as surplus variable.

–       Simplex tableau: Simplex tableau consists of the augmented matrix corresponding to the constraints together with slack variables and the objective function.

                   Standard form of maximization problems (e.g. in two variables)

                   Maximize F(x, y) = ax + by

                   Subject to the constraints

                   a1x + b1y £ c1

                   a2x + b2y£ c2

                   .....................

                   ....................

                   amx + bmy £ cm

                   Where x  ≥ 0, y ≥ 0, cm ≥ 0.                                                                                                                              

                   Standard minimization problems (e.g. in two variables)

                   Minimize c = ax + by

                   Subject to

                   a1x + b1y £ c1

                   a2x + b2y £ c2

                   c1, c2 ≥ 0,   x, y ≥ 0.

If the given problem is of the minimization type then it can also be solved by the same method as in maximization type but only after changing the given minimization LP problem into the maximization LP problem, i.e. after finding the dual of the given minimization LP problem.

Solved Problems