INTRODUCTION TO

LINEAR
PROGRAMMING
A Mathematical Optimization Technique
 WHAT IS LINEAR PROGRAMMING?

Definition:
A mathematical method for optimizing a linear objective function
subject to linear constraints.
Purpose:
To determine the best outcome, such as maximum profit or minimum
cost, given limited resources and specific requirements.
Linear programming provides a systematic approach to making
optimal decisions when facing constraints in business, engineering,
and scientific applications.
Example
A furniture company manufactures desks and chairs. Each desk requires 4 hours
of labor and 3 kg of wood. Each chair requires 2 hours of labour and 2 kg of wood.
The company has 300 labor hours and 175 kg of wood available per week. A desk
earns a profit of Rs. 4,000 and a chair earns Rs.2,[Link] many desks and chairs
should the company produce to maximize profit?

Desks (x) Chairs (y) Available

Labour (hours) 4 2 300

Wood (kg) 3 2 175

Profit (Rs) 40 25 ?
 KEY COMPONENTS

Objective Function: The mathematical expression to be maximized or

minimized (e.g., profit, cost). This is the goal of your optimization
problem. 𝑧 = 4000𝑥 + 2500𝑦

Decision Variables: The controllable quantities that influence the

outcome (e.g., number of units to produce, resources to allocate).

Constraints: Linear inequalities or equations that define the boundaries

4𝑥 + 2𝑦 ≤ 300
and limitations on the decision variables. These represent real-world
restrictions such as resource availability, capacity limits, or budget
3𝑥 + 2𝑦 ≤ 175
restrictions.
 FEASIBLE REGION

The feasible region is the area representing all possible solutions

that satisfy the constraints in a linear programming problem.
When constraints are plotted on a graph, the feasible region is the
intersection of all constraint inequalities—shown as a shaded
polygon where valid solutions exist.
Key insight: The optimal solution always lies at a vertex (corner
point) of the feasible region, making it efficient to evaluate only
these points when solving.
 APPLICATIONS OF LINEAR PROGRAMMING
Manufacturing Optimization: Determine optimal production quantities to
maximize profit while meeting resource constraints. Transportation &
Logistics: Minimize shipping costs and optimize delivery routes across
distribution networks.

Financial Planning: Optimize investment portfolios to maximize returns within

risk tolerance levels. Resource Allocation: Efficiently distribute limited
resources such as labor, materials, and time across competing projects.
 SOLVING LINEAR PROGRAMMING PROBLEMS

Graphical Method: An intuitive visual approach ideal for two-variable problems.

By plotting constraint lines on a coordinate plane and identifying the feasible
region, the optimal solution is found at one of the corner points (vertices) where
the objective function reaches its maximum or minimum value.

The Simplex Method: A powerful algorithmic approach developed by George Dantzig that
systematically examines vertices of the feasible region to find the optimal solution. It
efficiently handles problems with many variables and constraints, making it the standard
method for large-scale linear programming problems.
 Graphical Method
5 main steps for solving a linear programming problem, by using the graphical method

1. Place all the necessary information into a net and organized table
2. Find out what has to be maximized or minimized and in most cases it is the profit or cost. Then
write the profit/cost equation.
3. Find the variables of the problems and what parts can be controlled. These equation are known
as the constraints.
4. Once the contains have been established, plot them on a graph to find the vertices of the linear
functions
5. After the graph is drawn, the vertices of the graph will tell you the maximum or minimum of the
system by plugging them into the profit/cost function.
Worked Example 1
A magazine company sells two main types of magazines; Healthwise sells for $12 and Superteen sells for
$10. it costs the company $9 to produce Healthwise and $8 to produce Superteen. In a week publishing
company can print 200-300 copies of Healthwise and 100-250 copies of Superteen, but no more than 500
copies in total. How many of each type shoul be printed in order for the company to make maximum
profit.

Healthwise (x) Superteen (y)

Sale price ($) 12 10

Production cost ($) 9 8

Number of 200-300 100-250

printable copies
 Graphical Method
Healthwise (x) Superteen (y)
Variables : Regular 𝑥 , Heavy-duty (𝑦)
Sale price ($) 12 10

Production cost ($) 9 8

Objective function: 𝑧 = 3𝑥 + 2𝑦
Profit 3 2

Vertex Profit
Constraints :200 ≤ 𝑥 ≤ 300
(200,100) 800
100 ≤ 𝑦 ≤ 250 (200,250) 1100

𝑥 + 𝑦 ≤ 500 (250,250) 1250

(300,200) 1300

(300,100) 1100
Worked Example 2
A window manufacturing company makes two types of windows, regular and heavy-duty. Each regular
window takes approximately 2 hrs to cut and 1hour to finish. The heavy-duty windows take 1 hour to cut
and 3 hrs to finish. Each regular window makes net profit of $80 and the heavy-duty window makes a net
profit of $200. If 4 cutting and 3 finishing workers are used 10 hours per day, how many of each window
should be made for the company to make a maximumum profit?
Regular (x) Heavy-duty (y)

Cutting hrs 2 1

Finishing hrs 1 3

Profit ($) 80 200

workers 4 3
 Graphical Method
Variables : Regular 𝑥 , Heavy-duty (𝑦)
The objective is to find the maximum profit
Objective function: 𝑧 = 80𝑥 + 200𝑦

Vertex Profit

(0,0) 0
Constraints :2x + y ≤ 4 × 10
(0,10) 2000
x + 3y ≤ 3 × 10 (18,4) 2240

(20,0) 1600
Worked Example 3
The liquid potion of a diet is to provide at least 300 calories, 36 units of vitamin A, and 90 units of vitamin C
daily. A cup of dietary drink X provided 60 calories, 12 units of vitamin A and 10 units of vitamin C. A cup of
dietary drink Y provides 60 calories , 6 units of vitamin A, and 30 units of vitamin C. Now suppose that
dietary drink X costs $0.12 per cup and drink Y costs $0.15 per cup. How many cups each drink should be
consumed each day to minimize the cost and still mee the given daily requirement?
Worked Example 3
The liquid potion of a diet is to provide at least 300 calories, 36 units of vitamin A, and 90 units of vitamin C daily. A cup of dietary drink X provided 60 calories,
12 units of vitamin A and 10 units of vitamin C. A cup of dietary drink Y provides 60 calories , 6 units of vitamin A, and 30 units of vitamin C. Now suppose that
dietary drink X costs $0.12 per cup and drink Y costs $0.15 per cup. How many cups each drink should be consumed each day to minimize the cost and still
mee the given daily requirement?

Drink Calories Vitamin A Vitamin C Cost ($)

X 60 12 10 0.12

Y 60 6 30 0.15

Minimum 300 36 90 ??
Requirement
 Graphical Method Drink Calories Vitamin A Vitamin C Cost ($)

X 60 12 10 0.12
Variables : Drink 𝑋 𝑥 , Drink 𝑌 (𝑦)
Y 60 6 30 0.15

The objective is to find the minimum cost Minimum 300 36 90 ??

Objective function: 𝑧 = 0.12𝑥 + 0.15𝑦 Requireme
nt

Constraints : 60𝑥 + 60𝑦 ≥ 300 ⇒ 𝑥+𝑦 ≥5

12𝑥 + 6𝑦 ≥ 36 ⇒ 2𝑥 + 𝑦 ≥ 6

10𝑥 + 30𝑦 ≥ 90 ⇒ 𝑥 + 3𝑦 ≥ 9
 Graphical Method
Objective function: 𝑧 = 0.12𝑥 + 0.15𝑦
𝑥+𝑦 ≥5

Vertex Cost ($)

2𝑥 + 𝑦 ≥ 6
(0,6) 0.9
𝑥 + 3𝑦 ≥ 9 (1,4) 0.72

(3,2) 0.66

(9,0) 1.08
 THE SIMPLEX METHOD

The Simplex Method is an algebraic procedure for systematically solving

linear programming problems. Developed by George Dantzig in 1947, it
remains one of the most widely used algorithms for optimization. The
method transforms LP problems into standard form by introducing slack and
surplus variables.
 THE SIMPLEX METHOD

The algorithm works by moving along the vertices (corner points) of the
feasible region, testing each for optimality. At each iteration, it identifies
an adjacent vertex with a better objective function value until the optimal
solution is found. This systematic approach guarantees finding the
optimal solution when one exists.
 SLACK VARIABLES
Definition: Variables added to ≤ constraints to convert inequalities into equalities.

Example: 2𝑥 + 𝑦 + 𝑠₁ = 100, where 𝑠1 ≥ 0

Purpose: Slack variables measure the amount of unused resources in a constraint. When
𝑠₁ = 0, the constraint is binding (fully utilized). When 𝑠₁ > 0, there is "slack" or leftover
capacity.

Key Insight: Slack represents the difference between what is available and what is used.
 SURPLUS VARIABLES

Definition: Surplus variables are subtracted from ≥ constraints to convert inequalities

into equalities.

Example: 𝑥 + 𝑦 − 𝑠₂ = 50, where 𝑠 2 ≥ 0

Purpose: Measures excess amounts beyond the minimum constraint requirements.

When 𝑠₂ > 0, it indicates how much the solution exceeds the constraint threshold.
The Simplex Method — Step by Step

Convert to Standard Form Choose Entering Variable

1 4 Pick the most negative value in the
Add slack variables to all ≤ constraints
objective row — that variable enters
to convert inequalities to equations.
the basis.

Set Up the Simplex Tableau Choose Leaving Variable

2 5 Apply the Minimum Ratio Test: divide
Write all equations and the objective
RHS by pivot column values.
function in a matrix (tableau) format.
Smallest ratio leaves.

Check for Optimality Pivot & Repeat

3 6
If all objective row values are ≥ 0, Row reduce to make pivot = 1, zeroes
you're done. Otherwise, continue. elsewhere. Go back to Step 3.
Worked Example 1 Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS
𝒔𝟏 1 1 1 0 4
𝑧 = 3𝑥 + 2𝑦
𝒔𝟐 2 1 0 1 5
𝑥+𝑦 ≤4
𝒛 -3 -2 0 0 0
2𝑥 + 𝑦 ≤ 5

𝑥 + 𝑦 + 𝑠1 = 4
2𝑥 + 𝑦 + 𝑠2 = 5

𝑧 − 3𝑥 − 2𝑦 = 0
 PIVOTING
Choosing the pivot involves two steps:
Basi 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS

• Choosing the entering variable (pivot column) s

𝒔𝟏 1 1 1 0 4

Look at the objective row (usually the last row of the simplex tableau). 𝒛
𝒔𝟐 2 1 0 1 5

-3 -2 0 0 0

Select the column with the most negative coefficient in the objective row.
• Choosing the leaving variable (pivot row)
RHS

For every positive entry in the pivot column, compute 4

Right−hand side 5/2

Pivot column entry

Choose the smallest positive ratio. That row becomes the pivot row, and Basi
its 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS
s

basic variable leaves the basis. 𝒔𝟏 1 1 1 0 4

𝒔𝟐 2 1 0 1 5

The intersection cell of the above column and row is the pivot value 𝒛 -3 -2 0 0 0
 PIVOTING
Basi 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS
Divide the entire pivot row by the pivot value. s
𝒔𝟏 1 1 1 0 4

Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS 𝒔𝟐 2 1 0 1 5

𝒛 -3 -2 0 0 0

𝒔𝟏 1 1 1 0 4

𝒔𝟐 1 0.5 0 0.5 2.5

𝒛 -3 -2 0 0 0 Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS

𝒔𝟏 0 0.5 1 -0.5 1.5

Eliminate all the other values from the pivot column 𝒙 1 0.5 0 0.5 2.5

𝒛 0 -0.5 0 1.5 7.5

Repeat until all the elements of Z row become positive

Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS
RHS
𝒔𝟏 0 0.5 1 -0.5 1.5 3 𝒔𝟏 0 0.5 1 -0.5 1.5

𝒙 1 0.5 0 0.5 2.5 5 𝒙 1 0.5 0 0.5 2.5

𝒛 0 -0.5 0 1.5 7.5 𝒛 0 -0.5 0 1.5 7.5

Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟐 RHS

𝒚 0 1 2 -1 3 𝒔𝟏 0 1 2 -1 3
𝒙 1 0 -1 1 1 𝒙 1 0.5 0 0.5 2.5
𝒛 0 0 1 1 9 𝒛 0 -0.5 0 1.5 7.5
Basis RHS
The Solution
𝒚 3
𝒙 1 𝑥 = 1, y=3
𝒛 9

The maximum value of 𝑧 is 9

Worked Example 2:

A pottery company produces bowls 𝑥 and mugs 𝑦 from labor and clay. Let
the selling price of a bowl is 40 and mug is 50 in units ($,Rs. Etc) . A bowl
needs one hour of labor and 4Kg of clay while a mug needs 2 hour of labor and
3kg of clay. Suppose maximum labor hours per day is 40 and available clay is
120 Kg. Find the number of bowls and mugs to manufacture for the maximum
profit.
A pottery company produces bowls
Basis Bowl (𝒙) Mug Available
𝑥 and mugs 𝑦 from labor and clay. Let
the selling price of a bowl is 40 and mug (𝒚)
is 50 in units ($,Rs. Etc) . A bowl needs
one hour of labor and 2Kg of clay while a
Labor (hrs) 1 2 40
mug needs 2 hour of labor and 3kg of
Clay (Kg) 4 3 120
clay. Suppose maximum labor hours per
day is 40 and available clay is 120 Kg. Price (units) 40 50
Find the number of bowls and mugs to
manufacture for the maximum profit.

The constraints are Let 𝑠1 and 𝑠2 be slack variables

The objective function . 𝑥 + 2𝑦 ≤ 40 𝑥 + 2𝑦 + 𝑠1 = 40

𝑧 = 40𝑥 + 50𝑦 4𝑥 + 3𝑦 ≤ 120 4𝑥 + 3𝑦 + 𝑠2 = 120

𝑥 ≥ 0, 𝑦 ≥ 0 𝑥 ≥ 0, 𝑦 ≥ 0
 𝑥 + 2𝑦 + 𝑠1 = 40

4𝑥 + 3𝑦 + 𝑠2 = 120

𝑧 − 40𝑥 − 50𝑦 = 0

Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS

𝒔𝟏 1 2 1 0 40
𝒔𝟐 4 3 0 1 120
𝒛 -40 -50 0 0 0
Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS Basi (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS
RHS s
𝒔𝟏 1 2 1 0 40 20 𝒔𝟏 1 2 1 0 40
𝒔𝟐 4 3 0 1 120 40 𝒔𝟐 4 3 0 1 120
𝒛 -40 -50 0 0 0
𝒛 -40 -50 0 0 0

Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS Basi (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS

s
𝒚 0.5 1 0.5 0 20
𝒚 0.5 1 0.5 0 20
𝒔𝟐 2.5 0 -1.5 1 60
𝒔𝟐 2 3 0 1 120
𝒛 -15 0 25 0 1000
𝒛 -40 -50 0 0 0
Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS
RHS
𝒚 0.5 1 0.5 0 20 40 𝒚 0.5 1 0.5 0 20
𝒔𝟐 2.5 0 -1.5 1 60 24 𝒙 2.5 0 -1.5 1 60
𝒛 -15 0 25 0 1000 𝒛 -15 0 25 0 1000

Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS Basis (𝒙) (𝒚) 𝒔𝟏 𝒔𝟐 RHS

𝒚 0 1 4/5 -1/5 8 𝒚 0.5 1 0.5 0 20

𝒙 1 0 -3/5 2/5 24 𝒙 1 0 -3/5 2/5 24
𝒛 0 1 16 6 1360 𝒛 -15 0 25 0 1000
 Basic Variables are

𝑥 = 24, 𝑦=8 The maximum profit is

Non-basic Variables are

𝑧 = 40𝑥 + 50𝑦

𝑧 = 40 × 24 + 50 × 8
𝑠2 = 0, 𝑠1 = 0
𝒛 = 𝟏, 𝟑𝟔𝟎
Worked Example 3:

An electronics engineering firm designs and manufactures three types of

custom IoT microcontroller sensor nodes: EcoNodes 𝑥1 , ProNodes 𝑥2 , and
MaxNodes 𝑥3 .Production relies on three specific stages:

SMT Surface Mount Assembly (soldering chips onto PCBs), Firmware

Flashing & Calibration, and Hardware Quality Assurance (QA) Isolation
Testing.

The following table is given the time allocation for each stage and the profit
earns by each sensor node.

Determine how many of each sensor node should be produce to obtain the
maximum profit
4𝑥1 + 2𝑥2 + 𝑥3 ≤ 60 (thousands) 4𝑥1 + 2𝑥2 + 𝑥3 + 𝑠1 = 60
𝑥1 + 3𝑥2 + 2𝑥3 ≤ 60 𝑥1 + 3𝑥2 + 2𝑥3 +𝑠2 = 60
𝑥1 + 𝑥2 + 𝑥3 ≤ 24 𝑥1 + 𝑥2 + 𝑥3 +𝑠3 = 24

The objective function: z = 12𝑥1 + 15𝑥2 + 10𝑥3

Basisc variables 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑠3 RHS

𝑠1 4 2 1 1 0 0 60
𝑠2 1 3 2 0 1 0 60
𝑠3 1 1 1 0 0 1 24
𝒛 -12 -15 -10 0 0 0 0
 4𝑥1 + 2𝑥2 + 3𝑥3 ≤ 60 (thousands) 4𝑥1 + 2𝑥2 + 3𝑥3 + 𝑠1 = 60
𝑥1 + 3𝑥2 + 2𝑥3 ≤ 60 𝑥1 + 3𝑥2 + 2𝑥3 +𝑠2 = 60
𝑥1 + 3𝑥2 + 2𝑥3 ≤ 24 𝑥1 + 3𝑥2 + 2𝑥3 +𝑠3 = 24

The objective function: z = 12𝑥1 + 15𝑥2 + 10𝑥3

E𝑛𝑡𝑒𝑟𝑖𝑛𝑔 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒
Basic variables 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑠3 RHS RHS
𝑠1 4 2 1 1 0 0 60 30
𝐿𝑒𝑎𝑣𝑖𝑛𝑔 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒
𝑠2 1 𝟑 2 0 1 0 60 20
𝑠3 1 1 1 0 0 1 24 24
Pivot element

𝒛 -12 -15 -10 0 0 0 0

𝑃𝑖𝑣𝑜𝑡 𝐶𝑜𝑙𝑢𝑚𝑛
BV 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑠3 RHS BV 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑠3 RHS
𝑠1 4 2 1 1 0 0 60 𝑠1 10/3 0 −1/3 1 -1/3 0 20

𝒙𝟐 1/3 𝟏 2/3 0 1/3 0 20 𝑥2 1/3 1 2/3 0 1/3 0 20

𝑠3 1 1 1 0 0 1 24 𝑠3 2/3 1 1/3 0 -1/3 1 4
𝒛 -12 -15 -10 0 0 0 0 𝒛 -7 0 0 0 5 0 300

RHS
Both 𝑥1 and 𝑥3 can consider as entering 6
variables. Hence, choose either one 60
6
Answer: (8,000, 12,000, 4,000) or (6,000, 18,000, 0)
Example:
A Manufacture produces 3 types of plastic fixtures. The time required for
molding, timings and packaging is given below
Process Type (𝑨) Type (𝑩) Type (𝑪) Total Time available

Molding 1 2 3 12,000
2
Timing 2 2 1 4,600
3 3
Packaging 1 1 1 2,400
2 3 2
Profit ($) 11 16 15
How many of each type of fixture should be produced to obtain the maximum profit?
(600, 5,100, 800)
Worked Example 2: ( Using 𝑪𝒋 − 𝒁𝒋 tableau vales)

A pottery company produces bowls 𝑥 and mugs 𝑦 from labor and clay. Let
the selling price of a bowl is $40 and mug is $50 in units. A bowl needs one
hour of labor and 4Kg of clay while a mug needs 2 hour of labor and 3kg of clay.
Suppose maximum labor hours per day is 40 and available clay is 120 Kg. Find
the number of bowls and mugs to manufacture for the maximum profit.
Worked Example 2: ( Using 𝑪𝒋 − 𝒁𝒋 tableau vales)
The objective function is Initially both 𝑠1 and 𝑠2 are zero
𝑧 = 40𝑥 + 50𝑦 + 𝑠1 + 𝑠2

Then we initiate the table

Basis 𝑪𝑩 𝒙 𝒚 𝒔𝟏 𝒔𝟏 RHS
𝒔𝟏 0 1 2 1 0 40
𝒔𝟐 0 4 3 0 1 120
Now write the profits 𝐶𝑗
Basis 𝒙 𝒚 𝒔𝟏 𝒔𝟏 𝑪𝒋 40 50 0 0

𝑪𝒋 40 50 0 0
 Worked Example 2: ( Using 𝑪𝒋 − 𝒁𝒋 tableau vales)
Next, find 𝑍𝑗

𝑍𝑗 = ෍ 𝐶𝐵 × 𝐶𝑜𝑙𝑢𝑚𝑛 𝑒𝑛𝑡𝑟𝑖𝑒𝑠

Basis 𝑪𝑩 𝒙 𝒚 𝒔𝟏 𝒔𝟏 RHS
𝒔𝟏 0 1 2 1 0 40
𝒔𝟐 0 4 3 0 1 120
𝒁𝒋 0 0 0 0 0
𝑪𝒋 − 𝒁𝒋 40 50 0 0 0
Worked Example 2: ( Using 𝑪𝒋 − 𝒁𝒋 tableau vales)
To choose the entering variable, select the large positive 𝑪𝒋 − 𝒁𝒋 = 𝟓𝟎
𝑪𝒋 40 50 0 0

Basis 𝑪𝑩 𝒙 𝒚 𝒔𝟏 𝒔𝟏 RHS
𝒚 50 0.5 1 0.5 0 20
𝒙 40 2.5 0 -1.5 1 60
𝒁𝒋 25 50 25 0
𝑪𝒋 − 𝒁𝒋 15 0 -25 0
Worked Example 2: ( Using 𝑪𝒋 − 𝒁𝒋 tableau vales)
To choose the entering variable, select the large positive 𝑪𝒋 − 𝒁𝒋 = 𝟏𝟓
𝑪𝒋 40 50 0 0

Basis 𝑪𝑩 𝒙 𝒚 𝒔𝟏 𝒔𝟏 RHS
𝒚 50 0 1 4/5 -1/5 8
𝒙 40 1 0 -3/5 2/5 24
𝒁𝒋 40 50 16 6
𝑪𝒋 − 𝒁𝒋 0 0 -16 -6

The maximum profit is 50 × 8 + 40 × 24 = 1360

Worked example 4:
Imagine you want to prepare a quick, healthy, and low-cost breakfast using two
ingredients: Brand A Oats and Brand B Grain Powder. Your doctor recommends
that your breakfast should contain at least 3g of fiber and 6g of protein each morning.
Each scoop of the two products provides the following nutrients:
Determine the number of scoops of each ingredient required to satisfy the nutritional
requirements while minimizing the total breakfast cost.

Ingredient Fiber per scoop Protein per scoop Cost per scoop
Brand A Oats 3g 4g $3
Brand B Grain Powder 1g 3g $1
Worked example 4:
Ingredient Fiber per scoop Protein per scoop Cost per scoop

Brand A Oats (𝑥) 3g 4g $3

Brand B Grain Powder (𝑦) 1g 3g $1
Minimum requirement 3g 6g

The Objective function

𝑧 = 3𝑥 + 𝑦
The constraints are
3𝑥 + 𝑦 ≥ 3
4𝑥 + 3𝑦 ≥ 6
 Protein per The Objective function
Ingredient Fiber per scoop Cost per scoop
scoop 𝑧 = 3𝑥 + 𝑦
Brand A Oats (𝑥) 3g 4g $3
The constraints are
Brand B Grain Powder (𝑦) 1g 3g $1
Minimum requirement 3g 6g 3𝑥 + 𝑦 ≥ 3

Since this is a minimization problem with ≥constraints, we use: 4𝑥 + 3𝑦 ≥ 6

• surplus variables
• artificial variables
The constraints becomes
3𝑥 + 𝑦 − 𝑠1 + 𝑎1 = 3
4𝑥 + 3𝑦 − 𝑠2 + 𝑎2 = 6
The big M method

Because this is a minimization problem, the objective function becomes

𝑧 = 3𝑥 + 𝑦 + 𝑀𝑎1 + 𝑀𝑎2

where 𝑀 is a very large positive number used to penalize artificial variables.

Then the initial simplex table

𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS 3𝑥 + 𝑦 ≥ 3

4𝑥 + 3𝑦 ≥ 6
𝑀 𝑎1 3 1 -1 0 1 0 3

𝑀 𝑎2 4 3 0 -1 0 1 6
𝑧 = 3𝑥 + 𝑦 + 𝑀𝑎1 + 𝑀𝑎2 Find 𝑍𝑗 = ෍ 𝐶𝐵 × 𝐶𝑜𝑙𝑢𝑚𝑛 𝑒𝑛𝑡𝑟𝑖𝑒𝑠

𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS

𝐶𝑗 3 1 0 0 𝑀 𝑀

𝑀 𝑎1 3 1 -1 0 1 0 3

𝑀 𝑎2 4 3 0 -1 0 1 6

𝑍𝑗 3𝑀 + 4𝑀 𝑀+𝑀 −𝑀 −𝑀 𝑀 𝑀

𝐶𝑗 − 𝑍𝑗 3 − 7𝑀 1 − 2𝑀 𝑀 𝑀 0 0
To find the entering variable we use the most negative value

𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS
𝑅𝐻𝑆

𝐶𝑗 3 1 0 0 𝑀 𝑀 𝑃𝑖𝑣𝑜𝑡 𝐶𝑜𝑙𝑢𝑚𝑛

𝑀 𝑎1 3 1 -1 0 1 0 3 1

𝑀 𝑎2 4 3 0 -1 0 1 6 3/2

𝑍𝑗 3𝑀 + 4𝑀 𝑀 + 𝑀 −𝑀 −𝑀 𝑀 𝑀

𝐶𝑗 − 𝑍𝑗 𝟑 − 𝟕𝑴 1 − 2𝑀 𝑀 𝑀 0 0

𝑃𝑖𝑣𝑜𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑆𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜

𝐿𝑒𝑎𝑣𝑖𝑛𝑔 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒
𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS

𝐶𝑗 3 1 0 0 𝑀 𝑀

3 𝑥 1 1/3 -1/3 0 1/3 0 1

𝑀 𝑎2 0 5/3 4/3 -1 -4/3 1 2

𝑍𝑗 3 1 + 5𝑀/3 −1 + 4𝑀/3 −𝑀 1 − 4𝑀/3 𝑀

𝐶𝑗 − 𝑍𝑗 0 −5𝑀/3 1 − 4𝑀/3 𝑀 −1 − 4𝑀/3 −𝑀

Proceed until all the elements in 𝐶𝑗 − 𝑍𝑗 raw become positive

To find the entering variable we use the most negative value

𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS
𝑅𝐻𝑆
𝐶𝑗 3 1 0 0 𝑀 𝑀 𝑃𝑖𝑣𝑜𝑡 𝐶𝑜𝑙𝑢𝑚𝑛

3 𝑥 1 1/3 -1/3 0 1/3 0 1 3

𝑀 𝑎2 0 5/3 4/3 -1 -4/3 1 2 6/5
𝑍𝑗 3 1 + 5𝑀/3 −1 + 4𝑀/3 −𝑀 1 − 4𝑀/3 𝑀

𝐶𝑗 − 𝑍𝑗 0 −5𝑀/3 1 − 4𝑀/3 𝑀 −1 − 4𝑀/3 −𝑀

Make pivot element 1

𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS

𝐶𝑗 3 1 0 0 𝑀 𝑀

3 𝑥 1 1/3 -1/3 0 1/3 0 1

1 𝑦 0 1 4/5 -3/5 -4/5 4/5 6/5

1
𝑅1 → 𝑅1 − 𝑅2
3
𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS

𝐶𝑗 3 1 0 0 𝑀 𝑀

3 𝑥 1 0 -3/5 1/5 3/5 1/5 3/5

1 𝑦 0 1 4/5 -3/5 -4/5 3/5 6/5

𝑍𝑗 3 1 −1 0 1 0

𝐶𝑗 − 𝑍𝑗 0 0 1 0 𝑀−1 𝑀

All the elements in 𝐶𝑗 − 𝑍𝑗 are positive.

𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑎1 𝑎2 RHS

𝐶𝑗 3 1 0 0 𝑀 𝑀

3 𝑥 1 0 -3/5 1/5 3/5 1/5 3/5

1 𝑦 0 1 4/5 -3/5 -4/5 3/5 6/5

𝑍𝑗 3 1 −1 0 1 0

𝐶𝑗 − 𝑍𝑗 0 0 1 0 𝑀−1 𝑀

All the elements in 𝐶𝑗 − 𝑍𝑗 are positive. Then

3 6
𝑥 = and y =
5 5
𝑧 = 3𝑥 + 𝑦

3 6
𝑧=3 + =3
5 5
Therefore, the minimum cost for the breakfast is $3
 Worked example 4:
A financial engineering firm manages investments in two types of assets:
𝑥1 = number of technology stock units (cost per unit is $80)
𝑥2 = number of green energy stock units. (cost per unit is $65)
The firm wants to minimize the total investment cost, while ensuring minimum expected
performance levels in terms of return stability, liquidity coverage, and risk control as
describe in the following table.
Constraint Type 𝑥1 𝑥2 Minimum
Requirement
Return stability index 3 units 2 units 180 units

Liquidity Coverage 2 units 4 units 200 units

Risk control score 1 units 3 units 120 units

 Constraint Type 𝑥1 𝑥2 Minimum Requirement
3𝑥1 + 2𝑥2 ≥ 180
Return stability index 3 units 2 units 180 units

Liquidity Coverage 2 units 4 units 200 units 2𝑥1 + 4𝑥2 ≥ 200

Risk control score 1 units 3 units 120 units
𝑥1 + 3𝑥2 ≥ 120
Since this is a minimization problem with ≥constraints, we use:
• surplus variables
• artificial variables
Then constraints becomes: 3𝑥1 + 2𝑥2 − 𝑠1 + 𝑎1 = 180

2𝑥1 + 4𝑥2 − 𝑠2 + 𝑎2 = 200

𝑥1 + 3𝑥2 − 𝑠3 + 𝑎3 = 120
Using big M method

The objective function becomes

𝑧 = 80𝑥 + 65𝑦 + 𝑀𝑎1 + 𝑀𝑎2 + 𝑀𝑎3
where 𝑀 is a very large positive number used to penalize artificial variables.
Then the initial simplex table
3𝑥1 + 2𝑥2 − 𝑠1 + 𝑎1 = 180
𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 𝑎3 RHS
2𝑥1 + 4𝑥2 − 𝑠2 + 𝑎2 = 200
𝑀 𝑎1 3 2 -1 0 0 1 0 0 180
𝑥1 + 3𝑥2 − 𝑠3 + 𝑎3 = 120
𝑀 𝑎2 2 4 0 -1 0 0 1 0 200

𝑀 𝑎3 1 3 0 0 -1 0 0 1 120
Find 𝑍𝑗 = ෍ 𝐶𝐵 × 𝐶𝑜𝑙𝑢𝑚𝑛 𝑒𝑛𝑡𝑟𝑖𝑒𝑠
𝑧 = 80𝑥 + 65𝑦 + 𝑀𝑎1 + 𝑀𝑎2 + 𝑀𝑎3
𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 𝑎3 RHS
𝑅𝐻𝑆
𝑪𝒋 80 65 0 0 0 𝑴 𝑴 𝑴 0 𝑃𝑖𝑣𝑜𝑡 𝐶𝑜𝑙𝑢𝑚𝑛

𝑀 𝑎1 3 2 -1 0 0 1 0 0 180 90

𝑀 𝑎2 2 4 0 -1 0 0 1 0 200 50
𝑀 𝑎3 1 3 0 0 -1 0 0 1 120 40
𝑍𝑗 6𝑀 9𝑀 −𝑀 −𝑀 −𝑀 𝑀 𝑀 𝑀
80 − 6𝑀 65 − 9𝑀
𝐶𝑗 − 𝑍𝑗 𝑀 𝑀 𝑀 −𝑀 −𝑀 −𝑀
𝐶𝐵 Basis 𝑥 𝑦 𝑠1 𝑠2 𝑠3 𝑎1 𝑎2 𝑎3 RHS

𝑪𝒋 80 65 0 0 0 𝑴 𝑴 𝑴 0

𝑀 𝑎1 7/3 0 -1 0 2/3 1 0 -2/3 100

𝑀 𝑎2 2/3 0 0 -1 4/3 0 1 -4/3 40

65 𝑦 1/3 1 0 0 -1/3 0 0 1/3 40

65
𝑍𝑗 3
+ 2𝑀 65 −𝑀 −𝑀 …. 𝑀 𝑀 ….

175
𝐶𝑗 − 𝑍𝑗 3
− 2𝑀 0 𝑀 𝑀 ….. −𝑀 −𝑀 …
𝑥 = 40
𝑦 = 40
Proceed until all the elements in 𝐶𝑗 − 𝑍𝑗 raw become positive