← BCM 321 Quantitative Techniques
Linear Programming Formulation and Graphical Solution
Notes
Introduction to Linear Programming
Linear programming is a mathematical optimization technique used by managers to allocate scarce resources among competing demands. In quantitative business analysis, it enables organizations to either maximize an objective, such as revenue or profit, or minimize an objective, such as operational cost, within specified resource limits.
Key Components of an LP Model
Every linear programming model consists of four fundamental structural elements. First are decision variables, which represent the unknown quantities to be determined by the manager. Second is the objective function, which is a mathematical expression showing the target metric to be optimized. Third are structural constraints, which reflect physical, financial, or regulatory limitations such as machine hours, raw materials, or capital. Fourth is the non-negativity condition, which ensures that decision variables cannot take negative values.
Assumptions of Linear Programming
The valid application of linear programming requires four assumptions. Linearity assumes proportionality between variables and returns. Additivity requires that total output equals the sum of individual outputs. Divisibility allows fractional values for decision variables. Certainty assumes that all coefficients in the objective function and constraints are known with accuracy.
Graphical Solution Technique
The graphical method is restricted to problems with two decision variables. The modeler plots constraint equations as straight lines on a Cartesian coordinate plane, identifies the feasible region containing all mutually satisfied solutions, and finds the optimal corner point using either the extreme point method or the iso-profit line method.
Practical example
A bakery located in Nakuru produces two types of bread daily: Standard White (W) and Premium Brown (B). Standard White yields a profit of KES 20 per loaf, while Premium Brown yields KES 30 per loaf. Production is constrained by two resources: baking flour and oven time.
Each loaf of White bread requires 0.4 kg of flour and 0.1 hours of oven time. Each loaf of Brown bread requires 0.5 kg of flour and 0.2 hours of oven time. The bakery has a daily supply of 200 kg of flour and 60 oven hours.
The objective function is: Maximize Profit = 20W + 30B.
Constraint 1 (Flour): 0.4W + 0.5B <= 200.
Constraint 2 (Oven): 0.1W + 0.2B <= 60.
Non-negativity: W, B >= 0.
To find optimal values using extreme points, we evaluate the boundary intersections of the feasible region:
Point A (0, 0): Profit = KES 0.
Point B (0, 300): Tested against flour, 0.5(300) = 150 <= 200. Profit = 20(0) + 30(300) = KES 9,000.
Point C (intersection of both constraints): Solving 0.4W + 0.5B = 200 and 0.1W + 0.2B = 60 simultaneously yields W = 333.33 and B = 133.33. Profit = 20(333.33) + 30(133.33) = KES 10,666.60.
Point D (500, 0): 0.1(500) = 50 <= 60. Profit = 20(500) + 30(0) = KES 10,000.
The optimal corner point is Point C, maximizing daily profit at approximately KES 10,667.
Quiz
1. In linear programming, the non-negativity condition dictates that:
2. Why is the graphical method typically limited to problems with only two decision variables?
3. Which component of a linear programming model represents the mathematical goal to be maximized or minimized?
Sign in to submit and securely grade your quiz.