Before moving direct into the problems of Linear Programming 1, let's see what we need to know about Linear Programming.
Meaning of Linear Programming
Linear programming sometimes called Linear Optimization (LP) may be defined in various ways as follows:
- Is a mathematical technique for maximizing or minimizing a linear function of several variables, such as output or cost
- Is the simplest technique where we depict complex relationships through linear functions and then find the optimum points.
- Is the method to achieve the best outcome (maximum or minimum profit or lowest cost) in a mathematical model whose
requirements are represented by linear relationships.
- Is the method to allocate scarce resources to competing activities in an optimal manner when the problem can be expressed
using linear objective function and linear inequality constraints.
Common Terminologies used in Linear Programming
- Decision variables:
Are the variables which will decide the output. They represent the ultimate solution.
- Objective function:
It is defined as the objective of making decisions. For example "to make profit" is a objective function
Are restrictions or limitations on decision variables. They usually limit the value of the decision variables.
- Non-negativity restrictions:
For all linear programs, the decision variables should always take
non-negative values, which means the values for decision variables should be greater or equal to zero (0).
Process to formulate a Linear Programming problem
- Identify the decision variables
- Write the objective function
- Mention the constraints
- Explicitly state the non-negativity restrictions
For a problem to be a linear programming problem, the decision variables, objective function
and constraints altogether have to be linear functions
Solutions of Linear Programming problem
Linear programming problems can be solved using different methods such as:
- Graphical method
- Using Open solver
- Simplex method
- Northwest Corner & least count method
The commonly used method is Graphical method, let's see how to solve using Graphical Method
How to solve LP problem using Graphical method ?
- If a linear programming problem P has a solution, then it must occurs at a vertex, or corner points of feasible region
(set), S associated with the problem.
Feasible region is the region where solutions are possible and likely to be achieved.
It is bounded by corner points
Suppose we are given a linear programming problem with a feasible set S and an objective function P = ax + by, then:
- If S (feasible region) is bounded then P has both maximum and minimum values on S.
- If S is unbounded and both a and b are non-negative, then P has a maximum value on S provided that the constraints
defining S include x ≥ 0 and y ≥ 0.
Method of Corners:
- Graph the feasible set, S
- Find exact coordinates of all corner points
- Evaluate the objective function, P at each vertex.
- The maximum (if it exists) is the largest value of P at a vertex
- The minimum is the smallest value of P at a vertex.