Prepared by: Jeremy Laurence M.

Bañez, M S I E , C I E , AAE
▪ Define and discuss the LP problem and its characteristics
▪ Analyze real-life problems that can be modelled as LP problems
▪ Formulate the LP problem in a mathematical model
▪ Solve a two-variable LP problem using graphical method
▪ Create an LP model of a real-life problem
▪ Linear programming is the most prominent O R technique for
mathematical models with linear objective and constraint
functions.
▪ The adjective linear means that all the mathematical functions
in this model are required to be linear functions.
▪ The word programming does not refer here to computer
programming rather it is essentially a synonym for planning.
▪ Linear programming involves planning of activities to obtain
an optimal result.
Example: The Reddy Mikks Company
Reddy Mikks produces both interior and exterior paints from two raw
materials, M1 and M2. The following table provides the basic data of the
problem:
Tons of raw material per ton of Maximum daily
Exterior Paint Interior Paint availability (tons)

Raw material, M1 6 4 24
Raw material, M2 1 2 6
Profit per ton (Php1000) 5 4
The daily demand for interior paint cannot exceed that for exterior paint
by more than 1 ton. Also, the maximum daily demand for interior paint
is 2 tons.
Reddy Mikks wants to determine the optimum (best) product mix of
interior and exterior paints that maximizes the daily total profit.
All O R models, LP included, consist of three basic components:
1. Decision variables that one seeks to determine
2. Objective (goal) function that one needs to optimize (maximize
or minimize)
3. Constraints that the solution must satisfy
▪ For the Reddy Mikks problem, one needs to determine the daily
amounts of exterior and interior paints to be produced.
▪ Thus, the decision variables of the model are defined as:
𝑥1 = Tons produced daily of exterior paint
𝑥2 = Tons produced daily of interior paint
▪ The goal of Reddy Mikks is to maximize the total daily profit of
both paints.
▪ The two components of the total daily profit are expressed in
terms of the variables 𝑥1 and 𝑥2 as:
Profit from the exterior paint = 5𝑥1 (thousand) pesos
Profit from the interior paint = 4𝑥2 (thousand) pesos
▪ Letting z represent the total daily profit (in thousands of pesos),
the objective (goal) function of Reddy Mikks is expressed as
𝑴𝒂𝒙 𝒛 = 𝟓𝒙𝟏 + 𝟒𝒙𝟐
▪ Next, one constructs the constraints that restrict raw material
usage and product demand.
▪ The raw material restrictions are expressed as
𝑈𝑠𝑎𝑔𝑒 𝑜𝑓 𝑎 𝑟𝑎𝑤 𝑚𝑎𝑡𝑒𝑟𝑖𝑎𝑙 𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑟𝑎𝑤 𝑚𝑎𝑡𝑒𝑟𝑖𝑎𝑙
≤
𝑏𝑦 𝑏𝑜𝑡ℎ 𝑝𝑎𝑖𝑛𝑡𝑠 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑖𝑙𝑖𝑡𝑦
▪ The daily usage of raw material M1 is 6 tons per ton of exterior
paint and 4 tons per ton of interior paint. Thus,
𝑈𝑠𝑎𝑔𝑒 𝑜𝑓 𝑟𝑎𝑤 𝑚𝑎𝑡𝑒𝑟𝑖𝑎𝑙 𝑀1 𝑏𝑦 𝑏𝑜𝑡ℎ 𝑝𝑎𝑖𝑛𝑡𝑠 = 6𝑥1 + 4𝑥2 tons/day
In a similar manner,
𝑈𝑠𝑎𝑔𝑒 𝑜𝑓 𝑟𝑎𝑤 𝑚𝑎𝑡𝑒𝑟𝑖𝑎𝑙 𝑀2 𝑏𝑦 𝑏𝑜𝑡ℎ 𝑝𝑎𝑖𝑛𝑡𝑠 = 1𝑥1 + 2𝑥2 tons/day
▪ The maximum daily availabilities of raw materials M1 and M2
are 24 and 6 tons, respectively.
▪ Thus, the raw material constraints are:
𝟔𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐𝟒 (𝑅𝑎𝑤 𝑀𝑎𝑡𝑒𝑟𝑖𝑎𝑙 𝑀1)
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟔 (𝑅𝑎𝑤 𝑀𝑎𝑡𝑒𝑟𝑖𝑎𝑙 𝑀2)

▪ The first restriction on product demand stipulates that the daily

production of interior paint cannot exceed that of exterior paint
by more than 1 ton, which translates to:
𝒙𝟐 − 𝒙𝟏 ≤ 𝟏 (𝑀𝑎𝑟𝑘𝑒𝑡 𝑙𝑖𝑚𝑖𝑡)
▪ The second restriction limits the daily demand of interior paint
to 2 tons – that is,
𝒙𝟐 ≤ 𝟐 𝐷𝑒𝑚𝑎𝑛𝑑 𝑙𝑖𝑚𝑖𝑡

▪ An implicit (or “understood-to-be”) restriction requires (all) the

variables, 𝑥1 and 𝑥 2 , to assume zero or positive values only.
▪ The restrictions, expressed as 𝒙𝟏 ≥ 𝟎 and 𝒙𝟐 ≥ 𝟎, are referred to
as nonnegativity constraints.
 𝑴𝒂𝒙 𝒛 = 𝟓𝒙𝟏 + 𝟒𝒙𝟐
subject to
𝟔𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐𝟒 (1)
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟔 2
−𝒙𝟏 + 𝒙𝟐 ≤ 𝟏 (3)
𝒙𝟐 ≤ 𝟐 4
𝒙𝟏, 𝒙𝟐 ≥ 𝟎 (5)
▪ Certain symbols are commonly used to denote the various
components of a linear programming model such as:
𝑍 = value of overall measure of performance
𝑥𝑗= level of activity j (for j = 1, 2, … , n)
𝑐𝑗= increase in Z that would result from each unit increase in level
of activity j
𝑏 𝑖= amount of resource i that is available for allocation to
activities (for i = 1, 2, … , m)
𝑎 𝑖𝑗 = amount of resource i consumed by each unit of activity j
 C a n also be
Minimize
Maximize 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐𝑛𝑥𝑛 C a n also be ≥ or =
subject to
𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛𝑥𝑛 ≤ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2

⋮
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 ≤ 𝑏𝑚
C a n also be
unrestricted (urs)
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0
▪ Proportionality – an assumption about the objective function
and the functional constraints that rules out exponents other
t han 1
▪ Additivity – an assumption that every function in a linear
programming model (objective function of the function on the
left-hand side of a functional constraint is the sum of the
individual contributions of the respective activities
▪ Divisibility – decision variables in an LP model are allowed to
have any values, including non-integer values, that satisfy the
functional and non-negativity constraints
▪ Certainty – the value assigned to each parameter of an LP
model is assumed to be a known constant
 𝑴𝒂𝒙 𝒛 = 𝟓𝒙𝟏 + 𝟒𝒙𝟐
subject to
𝟔𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐𝟒 (1)
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟔 2
−𝒙𝟏 + 𝒙𝟐 ≤ 𝟏 (3)
𝒙𝟐 ≤ 𝟐 4
𝒙𝟏, 𝒙𝟐 ≥ 𝟎 (5)
▪ Determination of the Feasible Solution Space
▪ Determination of the Optimum Solution ▪ The optimum solution of an
LP, when it exists is always
associated with a corner
point of the solution space,
thus limiting the search for
the optimum from an infinite
number of feasible points to
a finite number of corner
points .
LP Solution with Excel Solver
LP Solution with Excel Solver
Assignment No. 1: F o r m u l a t e a n d s o l v e t h e p r o b l e m u s i n g g r a p h i c a l
method in a yellow paper. Check your answers using Excel Solver and/or
Lingo software. Print the results in long bond paper afterwards.
Diet Problem
Ozark Farms uses at least 800lb of special feed daily. The special feed is
a mixture of corn and soybean meal with the following compositions:
lb per lb of feedstuff
Feedstuff Cost (Php/lb)
Protein Fiber
Corn 0.09 0.02 0.30
Soybean meal 0.60 0.06 0.90
The dietary requirements of the special feed are at least 30% protein
and at most 5% fiber. The goal is to determine the daily minimum-cost
feed mix.