Linear programming is a technique for solving linear optimization problems by capturing the problem in a linear mathematical model and finding the maximum and minimum points.
Let's look at a linear programming problem.
CompCorp, a company that specializes in making computers, has two products: CompLap, a sleek lightweight laptop, and CompGame, a high-performance all-accessory computer system capable of handling computationally intensive tasks.
CompCorp makes a profit of USD 300 and USD 700 on selling a single CompLap and CompGame, respectively. CompCorp's production lines—hardware assembly and software loading—which are responsible for completing a finished product, are located at their only production unit in CompCity.
After production is complete, all units produced are sent for quality assurance. A single CompLap unit takes three days of work on the hardware assembly and two days for software loading. A CompGame unit takes five days on hardware assembly and one day in software loading. Both products require one day for quality assurance. The company wishes to maximize its profit by producing the optimal proportions of the two products for the next 90 days.
A solution to a linear programming problem is explained in terms of decision variables. A decision variable in linear programming problems affects the quantity being optimized. The objective of solving a linear programming problem is to find a set of decision variables that will produce the optimal output.
In our CompCorp example, the decision variables are the quantities of CompLap and CompGame units that will be produced in the upcoming quarter.
We will define our decision variables formally for the CompCorp problem. Let's assume that:
The decision variables can be arranged in a mathematical equation to give us the objective function. An objective function in linear programming defines the quantity that we wish to optimize—maximize or minimize. It is expressed as a linear equation in terms of the decision variables.
In the CompCorp problem, we wish to maximize the profit,
The output of the code snippet below shows the CompCorp problem solved using the Python PuLP library:
problem.solve() print("CompLap Made: ", X.varValue) print("CompGame Made: ", Y.varValue) print("Total Profit: ", value(problem.objective))
View all Courses