Linear Programming

Introduction to Linear Programming

• Linear Programming is a mathematical technique for optimisation, where the objective is to maximise or minimise a linear function subject to linear constraints.
• It involves problems that need the best possible solution under given constraints.

Key Components

• Decision variables: These are the variables that provide viable solutions. They are the values we wish to determine.
• Objective Function: This is the function which need to be optimised, either maximised or minimised.
• Constraints: These are the equations or inequalities that bound the validity of the solution.

Constructing Linear Programming Problem

• First step is to define the decision variables.
• Next, formulate the objective function by understanding which quantity needs to be maximised or minimised.
• Subsequently, formulate the constraints. There could be multiple constraints limiting the available solution space.

Graphical Approach

• In a Graphical Method, inequalities are expressed as straight lines on a graph, and solutions are possible points within the intersection of all the constraints.
• The solution, i.e., the maximum or minimum, lies at a vertex point or a corner of the feasible region.
• Graphical method is limited to linear programming problems with two variables.

Simplex Method

• For problems with more than two variables, the simplex method is applied.
• This is a tabular-based method that iteratively reaches towards optimum solutions.

To conclude, linear programming is a key area in Discrete and Decision Mathematics, central to resource allocation and operational efficiency problems. Regular practise will cement understanding and enhance problem solving skills.