Introduction
Cries of anguish and obnoxious sirens alike polluted the air as legions of grimy men attempted to seek cover within the muddy trenches. Despite being plagued by fear they grit their teeth and valiantly stood up once again to empty their magazines. The year was 1939 and World War II had just begun.
In the midst of all this chaos a young George B. Dantzig made the difficult choice to put his doctorate studies at Berkeley on hold and get to work as Head of the Combat Analysis Branch at the Air Force Headquarters for Statistical Control. In this role he would have to create detailed routes to efficiently transport and produce necessary war supplies such as ammunition. Overtime Dantzig realized that optimization problems such as this could best be approached through use of mathematics and geometry. This process would come to be known as linear programming.
What is Linear Programming?
Linear programming is a mathematical technique used to maximize or minimize a linear function within certain constraints in order to achieve the most efficient and optimized outcome. Common uses of linear programming include the optimization of production, management, pricing, transportation, and energy use. The general form of a linear program, as devised by George B. Dantzig consists of 2 key pieces:
An objective linear function to maximize based off your decision variables:
f(x1x2) = c1x1 + c2x2
Situational and Non Negative Constraints:
a11x1 + a12x2 ≤ b1
a21x1 + a22x2 ≤ b2
a31x1 + a32x2 ≤ b3
x1 ≥ 0
x2 ≥ 0
Solving Linear Programs Graphically
Suppose a company receives in sales $20 per book and $18 per calculator. The cost per unit to manufacture each book and calculator are $5 and $4 respectively and the 30 day cost must not exceed $27,000 per month. If the manufacturing equipment used by the company takes 5 minutes to produce a book and 15 minutes to produce a calculator, how many books and calculators should the company make to maximize their 30 day profit?
In this scenario maximizing the company's profit is equivalent to maximizing their sales total. Since this is our objective we can create the function:
S = 20B + 18C
From there, we can create the following constraints based upon cost and time:
5B + 4C ≤ 27000
5B + 15C ≤ 43200
These components lay the basis for our linear function. From here we can use the graphical method to solve the linear programs.
As seen above the graphed limits create 2 distinct areas between them and axes in red and yellow. The orange overlap in these areas is the feasible region which satisfies both constraints. In order to maximize or minimize the function we take one of the vertices of this range as shown in blue, purple and green above. In this scenario where we’re looking for maximum profit, we can immediately rule out the green point as it’s the smallest possible profit with it being at (0,0). The purple points can also be ruled out as they’re the extreme, inefficient cases in which we only produce books or only produce calculators. This leaves the blue point which lies at the intersection of the 2 restraints, this is the situation in which the maximum profit may be produced. Through solving the constraints system of equations we find that this point lies at (4221, 1473). Which when plugged in tells us the company's maximum 30 day profit is $110,934.
Solving Linear Programs With The Simplex Method
Another way of optimizing linear programs devised by Dantzig is the simplex method which utilizes matrices. We start with the same base objective function and constraints but we add a variable known as the slack variable to convert the constraints to equations and change the function to an equation as well. This gives us: S – 20B – 18C = 0
5B + 4C + y1 = 27000
5B + 15C + y2 = 43200
From here using the coefficients of your various equations construct a matrix as such:
Then identify the column with the highest negative entry and label it the pivot column. In this case that would be column 1 with -20. From here excluding the bottom row divide the entries in the rightmost columns by the entries within the pivot column:
27000/5 = 5400
43200/5 = 8640
The row containing the smallest quotient is identified to get the pivot row. As 5400 is the smaller quotient as compared to 8640, row 1 becomes the pivot row. The intersection of the pivot row and the pivot column gives the pivot element. Thus, pivot element = 5. Here through basic matrix operations we make all other entries in the pivot column = 0:
R2 = R2 – R1
R3 = R3 + 4R1
Check if the bottom-most row has negative entries. If there are none then the optimal solution has been found, otherwise repeat the process with a newly selected pivot column. -2 is a negative entry in the matrix thus, the process needs to be repeated. We eventually end up getting:
This tells us that when B = 4218 and C = 1472, S = a maximum value of $110,945 which is nearly the exact same value as we found when using the graphical approach.
Takeaways
Linear programming is a technique that is used to determine the optimal solution of a linear objective function.
A Linear program is made up of an objective function and constraints
A linear programming problem may be solved using the graphical or simplex method
That’s all for this post! Happy holidays and see you next year!
Comments