linear programming

Linear Programming Problem (LPP): 

It is used for optimization of our limited resources when there are number of alternate solution possible for the problem.

A Linear Programming Problem (LPP) has of three main parameters named as:

1. Decision Variables (Activities): 

• These are the economic or physical quantities, which are competing with one another for sharing the given limited resources.
• In linear programming, these variables must form linear relationship among them.
• The numerical values of decision variables represent the solution of LPP.

2. Objective (Goal):

• In linear programming problem, the objective function forms a linear function of the decision variable expressing the objective of the decision maker.
  Example: maximization of profit or contribution, minimization of cost/time

3. The Constraints (Restriction):

• The constraints put limitations on the resources allocated among various decision variables. The resources may be in the form of production capacity, manpower, time, space or machinery.
• Generally, these are written in linear equation in equal terms (i.e. =) or in inequalities form  (i.e. > or < type) in terms of decision variables. Thus, these represent the linear equalities or inequalities arising out of practical limitations.
• Non-negativity Restriction Non-negativity restriction indicates that:
  All decision variables ≥ 0.

Basic Assumptions or Laws of LPP

• Certainty: All parameters, availability of resources, profit consumption of resources must be fixed.
• Divisibility (or continuity): Non-negative values of decision variable can positive frictional value.
• Proportionality: Decision variable directly proportional to value of variable.
• Additivity: The value of the objective function for a given value of decision variables and the total sum of resources used by each decision respectively.

Note: LPP involving two decision variables can easily solved by graphical method.

Graphical Method Steps:

1. identify the problem, define decision variables, objective function and constraints.
2. Draw a graph including all the constraints and search the the common feasible region.
3. Find out the point within the feasible region which optimizes the objective fun these point gives the final optimum solution.
4. One of the corner point of the feasible region gives the final solution because objective fun is straight line with constant slope and as it moves away from origin there is increase in its value and the corner extreme point will be its optimum value.
5. Objective function will be tangent to that point and give the optimum solution.

Special cases:

• Infinite or multi optimal solution: Infinite solution means we get the same optimum value of objective function for different varying variables.
• No solution or in-feasibility: In some condition constraint may in inconsistent in such a manner that it is not possible to find a feasible region where all the constraints are satisfied, it is termed as no solution or in-feasibility.
• Unbounded solution: In some condition the highest value of objective function goes up-to infinite and it simply means that the common feasible region is not bounded by the limit on the constraints.

 Simplex Method: 
When the decision variables are more than two, the graphical method becomes inadequate and linear programming problem is solved by the simplex method. The simplex method is defined as an algebraic procedure that through a series of repetitive operations progressively approaches an optimal solution. Simplex method is based on 2 fundamental conditions, they are-

• Conditions of Feasibility: It assumes that if the initial solution is basic feasible, and then during computation, only basic feasible solutions will be obtained.
• Condition of Optimality: It ensures that only better solutions will be encountered.

Simplex Procedure:

1. Setup the objective function.
2. Setup the constrained equations.
3. Convert the inequalities to equalities.

Special cases

• Unique solution: If number of basic variables are equal to the number of zeros, then the solution is unique.
• Infinite or multi-optimum solution: When a non-basic variable in an optimum solution has zero value for Δ_j row then the solution is not unique and it indicates that the problem has infinite no. of solution.
• Unbounded solution: If in a case all the value in the replacement ratio column are either –ve or infinite then the solution terminates and it indicates that the problem has unbounded solution.
• No-solution/in-feasibility: When in the final solution artificial variable remains in the basis then there is no feasible solution to the problem.
• Degenerate solution: When one or more of the basic variables becomes equal to zero during calculation then the solution is called degenerate & the condition is known as degeneracy. In a degenerate solution the no. of basic variables becomes less than equality constraint.

BIG. M method:

• Big M method is a modified form of simplex method, and it is always used whenever the constraints are of (≥ or =) type irrespective of whether the problem is for maximization or for minimization.
• In this condition, we introduce artificial variables in the current solution to get an initial working matrix.
• These artificial variables must not appear in the final solution and this is ensured by providing an extremely negative value (M) to their profit coefficients in the objection function.

Duality in Linear Programming:

Corresponding to a linear programming problem is another linear programming problem formulated from the Parameters of the original problem.
Dual Theorem of Linear Programming: States a theoretic relationship between the primal and dual problems.
Dual Variables: are the variables of the dual LPP.
Primal Problem: is the original linear programming problem.
Post-Optimality (Sensitivity) Analysis: of a linear programming problem is a study of the effect of changes of the profit of resource level on the solution.

Minimization and Maximization Conditions in Dual Problem