Almost all of problems that Linear Programming is able to solve is about resource allocation, for example: product mix, production, inventory, scheduling, etc. You have limited resource, and so many things to do. So that you have decision-making problems. Linear program is a special type of mathematical program with some special properties.
Mathematical Programs
Basically, a program is to make decisions. Each mathematical program can be composed by 3 elements:
- objective function – in order to minimize or maximize some quantity
- constraints – limited resources, time, whatever you need to satisfy
- Sign constraints: xi >= 0 or xi <= 0
- Functional constrains: all others
- decision variables – some quantities we want to decide
For a mathematical program, a solution can be:
| feasible | satisfies all the constraints |
| infeasible | violates at least one constraint |
The feasible set or feasible region is the set of all feasible solutions. It is possible that there are constraints conflicting with each other, so it is possible the feasible set is empty. An optimal solution is a feasible solution that is the best, no other feasible solution is strictly better than it. It is possible that there are either multiple optimal solutions or no optimal solution at all. It is also possible there are feasible solutions, but there is no optimal solution.
Binding constraints
It is a property about constraints when you talk about a specific solution. When you have an inequality constraint, if there is a solution, which makes the constraint become equality, then we say this inequality constraint is binding at the solution. An equality constraint is always binding at any feasible solution.
Strict and weak constraints
An inequality may be strict or weak:
| strict | two sides can not be equal |
| weak | two sides may be equal |
In Operations Research, a practical mathematical program’s inequalities are all weak. We only work on weak constraint, because with strict inequalities, sometimes optimal solutions do not exist.
Linear Programs
A mathematical program is an linear program if all functions (objective and constraints) are linear functions.
Graphical approach (with 2 decision variables)
There is a graphical approach to solving the problem, illustrated as below:
- Draw the feasible region
- by drawing each constraints one by one, and then find the intersection.
- Draw some isoquant / isoprofit / isocost lines (or indifference curves in Economics)
- for the objective function, all points on one isoquant line share the same objective value
- Indicate the direction to push the isoquant line
- direction that decrease the objective value for minimization problem
- direction that increase the objective value for maximization problem
- Push the isoquant line to the end of feasible region
- when it stops, we get optimal solution
- Identify the binding constraints at an optimal solution
- Set the binding constraints to equalities and solve the linear system for an optimal solution.
- Plug in the optimal solution x obtained into the objective function f to get the objective value f(x).
Three Types
For any linear program, it must be one of the following type:
- Infeasible – if its feasible region is empty.
- Unbounded – if for any feasible solution, there is another feasible solution that is better.
- Note: an unbounded feasible region does not imply an unbounded linear program (depends on objective function)
- It is necessary for an unbounded linear program to have an unbounded feasible region.
- Finitely optimal
- A unique optimal solution
- Multiple optimal solutions – this is possible if the slope of the isoquant line is identical to that of one constraint.
Linear Programming Formulation Examples
Product Mix Problem
We produce several products to sell, each product requires some resources, which are limited. We want to maximize total sales revenue with available resources.
Production and Inventory Problem
We produce and sell products at the same time, for each day, the cost of producing is known (producing), and a certain predictable amount of demand will be fulfilled (selling). Storing products over night is also costly. Since the price of the products are all the same, this profit-maximizing problem is actually a cost-minimizing problem.
Personnel Scheduling
Suppose each employee works for 5 consecutive days, and rest for 2 consecutive days. The number of employees you need is different on different day. There are 7 shifts: Mon-Fri, Tue-Sat, etc. You want to minimize the number of employees.
Compact Formulation
Many problem instances in practice are of large scale: thousands of variables and millions of contraints. You need to have a more efficient way to write down formulations. You use compact formulation to improve readability, efficiency, and degree of abstraction. Parameters are exogenous, and variables are endogenous.
A problem is a collection of instances. A problem is an abstract description of a task to complete or a question to solve. When we express everything with symbols, we have a problem or a class or instances. An instance is a concrete realization of a problem. When we plugin concrete values into symbols, we obtain an instance.
My Certificate
For more on Operations Research: Linear Programming, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-modeling
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Checkout more course reviews at https://KZHU.ai
