HANDOUT
TOPIC 2: LINEAR PROGRAMMING AND OPTIMIZATION
● FORMULATING LINEAR PROGRAMMING PROBLEMS
● GRAPHICAL AND SIMPLEX METHODS
Linear Programming and Optimization
● Linear programming is a tool of management science for solving optimization problems.
● Linear programming is different from computer programming.
● The use of the word "programming" here means "choosing a course of action".
● A model that consists of linear relationships representing a firm's decision(s), given an
objective and resource constraints.
The typical model consists of the set of the linear equations and/or inequalities (called
constraints) and the linear objective function (which to be maximized or minimized). The
nonnegative constraints (variables are zero or positive) are mostly involved in the model. The
manager's goal is to find the optimal solution with the best value of the objective function.
The Scientific Method:
The Management Science Process:
Model Formulation
2 3
Linear Equation: ex. 2a + 3b = 10 whereas, 2𝑎 + 3𝑏 + 𝑎𝑏 = 10 is not
Inequality: ex. A + B ≤ C
Basic Assumptions
1. Conditions of certainty exist.
2. Proportionality exists in the objective function and constraints.
3. Additivity, meaning the total of all activities equals the sum of the individual activities.
4. Divisibility, meaning the solutions need not necessarily be in whole numbers (integers).
Maximization Problem Model
LP Problem 1: Product Mix
Harry Pottery Company is a small crafts operation run by a Native American wizard council. The
company employs skilled wizards to produce clay bowls and mugs with authentic Native
American designs and colors. The two primary resources used by the company are special
pottery clay and skilled labor. Given these limited resources, the company desires to know how
many bowls and mugs to produce each day in order to maximize profit.
Model Formulation Steps
Step 1: Define the decision variables
How many bowls and mugs to produce
Step 2: Define the objective function
Maximize profit
Step 3: Define the constraints
The resources (clay and labor) available
Decision Variables
𝑥1= number of bowls to produce
𝑥2= number of mugs to produce
Objective function
Maximized Total Profit (Z) = Profit from Bowls + Profit from Mugs
Z = 𝑃𝑏* 𝑥1 + 𝑃𝑚 * 𝑥2
Z = $40𝑥1 + $50𝑥2
Model Constraints
Labor & Clay (Limited Resources)
Total Labor = Labor for Bowl + Labor for Mug
Total Labor = 1𝑥1 + 2𝑥2
Labor Constraint: 1𝑥1 + 2𝑥2 ≤ 40 hours
Clay Constraint: 4𝑥1 + 3𝑥2 ≤ 120 lb.
Nonnegativity constraint: 𝑥1 ≥ 0, 𝑥2 ≥ 0
Linear Programming Model:
Z= $40𝑥1 + $50𝑥2 SUBJECT TO
1𝑥1 + 2𝑥2 ≤ 40
4𝑥1 + 3𝑥2 ≤ 120
𝑥1 , 𝑥2 ≥ 0
Option/Possible Solution #1: Feasible
𝑥1= 5
𝑥2= 10
Z= $40(5) + $50(10) = $200 + $500 = $700
where
1(5) + 2(10) ≤ 40 25 ≤ 40
4(5) + 3(10) ≤ 120 50 ≤ 120
Option/Possible Solution #2: Infeasible
𝑥1= 10
𝑥2= 20
Z= $40(10) + $50(20) = $400 + $1000 = $1400
where
1(10) + 2(20) ≤ 40 50 ≤ 40
4(10) + 3(20) ≤ 120 100 ≤ 120
Minimization Problem Model
Objectives of Cost Minimization - The goal is to reduce total expenses while still meeting all
necessary conditions, such as production or resource needs.
- To minimize cost.
Model Formulation Steps:
Step 1: Define the Decision Variables
-Represents the choices you can control.
Step 2: Define Objective Functions(to minimize)
-The Total Cost(or other quantity) to be reduced.
-Minimize Cost Z = a1 + b2
Step 3: Identify Constraints
-The Limitations based on resources, capacities, or requirements.
-Minimize Cost Z = a1 + b2 ≥ Demand Requirements
-In the form of Inequalities.
Graphical Method - a technique used to solve linear programming problems with two decision
variables. It involves graphing the constraints, identifying the feasible region, and then finding
the optimal solution by evaluating the objective function at the corner points (vertices) of the
feasible region.
Key Elements of a Graphical Method:
1. Decision Variable - The variables that determine the outcome of the problem (typically
represented as x and y).
2. Objective Function - A linear function to be maximized or minimized. (typically in the
form Z= 𝑥1 + 𝑥2).
3. Constraints - A set of linear inequalities representing resource limitations
4. Feasible Region - The region on the graph that satisfies all constraints. This is the set of
all possible solutions.
5. Corner Points - The vertices of the feasible region.
6. Optimal Solution - The point in the feasible region where the objective function reaches
its maximum or minimum value.
STEPS IN THE GRAPHICAL METHOD:
STEP 1: Formulate the Linear Programming Problem
STEP 2: Graph the Constraints
STEP 3: Identify the Feasible Region
STEP 4: Locate the Corner Points
STEP 5: Evaluate the Objective Function
STEP 6: Choose the Optimal Solution
PROS and CONS of using Graphical Method:
PROS
1. Visual Representation - Provides a clear, visual understanding of constraints, feasible
region, and optimal solution.
2. Simple to Use - Easy to apply for problems with two variables; suitable for beginners
learning linear programming.
3. Helps in Conceptual Understanding - Demonstrates how constraints interact and how
optimization works geometrically.
4. Immediate Insight - You can quickly see if there are multiple solutions, no solution, or
unbounded solutions
CONS
1. Limited to Two Variables - Can only solve problems with two decision variables (or
sometimes three with 3D graphs, but it's impractical).
2. Not Suitable for Complex Problems - Becomes ineffective and unclear for large-scale
or real-world problems involving many constraints or variables.
3. Graph Accuracy Issues - Requires precise graphing. Small errors in plotting can lead
to incorrect solutions.
4. Time-Consuming by Hand - Drawing accurate graphs manually can be tedious,
especially with fractional constraints.
Simplex Method - An algorithm developed by George Dantzig in 1947 to solve linear
programming (LP) problems. These problems involve maximizing or minimizing a linear
objective function subject to linear constraints.
- The method works by moving along the vertices (corner points) of the feasible region
defined by the constraints.
- It finds the optimal solution by improving the objective function value at each step until
no further improvement is possible.
● Problem Statement:
Maximize function:
7𝑥1 + 6𝑥2
Subject to constraints:
2𝑥1 + 4𝑥2 ≤ 16
3𝑥1 + 2𝑥2 ≤ 12
And 𝑥1 + 𝑥2 ≥ 0
● Writing the Problem in Standard Form
Simplex method, convert inequalities into equalities by adding slack variables 𝑠1 and 𝑠2
2𝑥1 + 4𝑥2 + 𝑠1 = 16
3𝑥1 + 2𝑥2 + 𝑠1 = 12
Where, 𝑠1 ,𝑠2≥ 0
Identify the need for Slack Variables: The inequalities in our constraints need to be
converted into equalities.
● Basic and Non-Basic Variables
Variables set to zero initially are called non-basic variables (start with 𝑥1 = 0 , 𝑥2 = 0)
The slack variables 𝑠1 = 16 and 𝑠𝑠 = 12 are basic variables as they form the initial
feasible solution.
● Simplex Tableau Setup
Table Contents:
- C-row (objective coefficients): 𝑐𝑗 for variables 𝑥1𝑥2𝑠1𝑠2
- A matrix: coefficients from constraints
- B column: right-hand side values
- Basic column: current basic variables 𝑠1𝑠2
- c_B column: objective coefficients of basic variables (initially zero for slack
variables)
Calculate 𝑧𝑗 row: 𝑧𝑗 = Σ(𝑐𝑏 * 𝑐𝑜𝑙𝑢𝑚𝑛 𝑒𝑛𝑡𝑟𝑖𝑒𝑠) — 𝑧𝑗 = 0 because 𝑐𝑏 = 0
Calculate net evaluation row 𝑐𝑗 −𝑧𝑗 :
- Indicates potential improvement of basic variables (initially zero for slack
variables) e.g. 𝑐𝑥1 −𝑧𝑥1 = 7 − 0 = 7
Why does this setup matter? — Allows you to systematically perform the simplex
method. It identifies which variables should enter or leave. To update the solution as we
move forward the optimal answer.
● Optimality
- Maximization problem, if all these values are zero or negative, it means no
non-basic variable can enter the basis to improve the objective function further.
- If you find a pivot column with positive coefficient but no valid pivot row, it
means the objective can increase indefinitely without violating constraints—called
as unboundness, and the problem has no finite optimal solution.
Summary Table
