Introduction to Linear Programming

Dr. Muhammad Shafiq

1
 Linear Programming Assumptions
 LINEARITY OR PROPORTIONALITY:
– Proportionality means that the objective function and constraint coefficients are strictly proportional to the decision variable
(e.g., If the first unit of production requires ‘2’ hours of labor so it must the 50th and 100th unit also requires ‘2’ hours of labor).

 DIVISIBILITY:
– Divisibility means that non integer (fractional) values of the decision variables are acceptable.
– Integer Programming is a special technique which can be used for finding non-fractional values of resource usage and decision
variables).

 CERTAINTY:
– Certainty means that the values of the parameters are known and constant

 ADDITIVITY:
– Additivity means the total effect of each decision variable (Profit, Cost, etc.) must equal the sum of the effects contributed by
each decision variable and terms of each constraint must be additive
– (Total amount of resource consumed or provided) must equal the sum of the resources used (or provided) by each decision
variable.

 NON–NEGATIVITY:
– Non – negativity means that the decision variables are permitted to have only the values which are greater than or equal to2zero.
 Steps for Optimization Study
1. To Define Problem
– Objectives
– Alternatives
– Constraints
– Scope/ Limitations

2. Model development
– Physical
– Mathematical
– Simulation
 Phases of Optimization Study Cont.

3. Solving the Model

– Standard mathematical techniques
– Heuristics
– Meta heuristic
– Simulation
– Sensitivity Analysis (Observe the behavior of optimum solution under
parametric change)
4. Verification and Validation
– The proposed model fulfill the objective for which it has been developed?
5. Implementation of the Solution
– Translate results into understandable operating instructions
 1. To Define the Problem
The sales manager for a publisher of college textbooks has six traveling
salespeople to assign to three different regions of the country. She has
decided that each region should be assigned at least one salesperson and
that each individual salesperson should be restricted to one of the regions,
but now she wants to determine how many salespeople should be
assigned to the respective regions in order to maximize sales.
• The owner of a chain of three grocery stores has purchased five crates of fresh
strawberries. The estimated probability distribution of potential sales of the
strawberries before spoilage differs among the three stores. Therefore, the owner
wants to know how to allocate five crates to the three stores to maximize expected
profit. For administrative reasons, the owner does not wish to split crates between
stores. However, he is willing to distribute no crates to any of his stores. The
following table gives the estimated expected profit at each store when it is allocated
various numbers of crates
• A college student has 7 days remaining before final examinations begin in her four
courses, and she wants to allocate this study time as effectively as possible. She
needs at least 1 day on each course, and she likes to concentrate on just one course
each day, so she wants to allocate 1, 2, 3, or 4 days to each course. Having recently
taken an OR course, she decides to use dynamic programming to make these
allocations to maximize the total grade points to be obtained from the four courses.
She estimates that the alternative allocations for each course would yield the
number of grade points shown in the following table
NATURE OF LINEAR PROGRAMMING PROBLEM
• Two of the most common are:
• 1. The product-mix problem
• 2. The blending Problem
• In the product- mix problem there are two or more product also called
candidates or activities competing for limited resources. The problem is to
find out which products to include in production plan and in what
quantities these should be produced or sold in order to maximize profit,
market share or sales revenue.
• The blending problem involves the determination of the best blend of
available ingredients to form a certain quantity of a product under strict
specifications. The best blend means the least cost blend of the required
inputs.
 FORMULATION OF THE LINEAR
PROGRAMMING MODEL
• Three components are:
• 1. The decision variable
• 2. The environment (uncontrollable) parameters
• 3. The result (dependent) variable
• OR teacher of the MS SCM program wants to maximize understanding of the students about the lecture. The
students who are late unable to understand if he starts on time at 6 PM. On the other hand, if he waits for the
late-comers, he has less time to explain the planned contents which again effects understanding of the students.
The values of number of students and understanding level of each student are given in the following table:

Class starting time No. of students present Understanding level of each

student
6:00 PM 20 95%
6:10 PM 27 92%
6:20 PM 40 88%
6:30 PM 47 75%

10
 FORMULATION STEPS OF LPP
• 1. Identify decision variables
• 2. Write objective function
• 3. Formulate constraints
 PRODUCTION ALLOCATION PROBLEM
• A firm produces three products. These products are processed on three
different machines.
• The time required to manufacture one unit of each of the three products and
the daily capacity of the three machines are given in the table below:
• It is required to determine the daily number of units to be manufactured for
each product.
• The profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3 and Rs.6 respectively.
It is assumed that all the amounts produced are consumed in the market.
Formulate the mathematical (L.P.) model that will maximise the daily profit.
 PRODUCT MIX PROBLEM
• A factory manufactures two products A and B. To manufacture one unit of A, 1.5
machine hours and 2.5 labour hours are required. To manufacture product B, 2.5
machine hours and 1.5 labour hours are required. In a month, 300 machine hours
and 240 labour hours are available.
• Profit per unit for A is Rs. 50 and for B is Rs. 40. Formulate as LPP.
• A company produces three products A, B, C.
• For manufacturing three raw materials P, Q and R are used.
• Profit per unit A - Rs. 5, B - Rs. 3, C - Rs. 4
• Maximum raw material availability:
• P - 80 units; Q - 100 units; R - 150 units.
• Formulate LPP.
 PORTFOLIO SELECTION (INVESTMENT
DECISIONS)
• An investor is considering investing in two securities 'A' and 'B'.
The risk and return associated with these securities is different.
• Security 'A' gives a return of 9% and has a risk factor of 5 on a
scale of zero to 10. Security 'B' gives return of 15% but has risk
factor of 8. Total amount to be invested is Rs. 5, 00, 000/- Total
minimum returns on the investment should be 12%.
Maximum combined risk should not be more than 6.
• Formulate as LPP.
 INSPECTION PROBLEM
• A company has two grades of inspectors, I and II to undertake
quality control inspection. At least 1500 pieces must be
inspected in an 8-hour day. Grade I inspector can check 20
pieces in an hour with an accuracy of 96%. Grade II inspector
checks 14 pieces an hour with an accuracy of 92%. Wages of
grade I inspector are Rs. 5 per hour while those of grade II
inspector are Rs. 4 per hour. Any error made by an inspector
costs Rs. 3 to the company. If there are, in all, 10 grade I
inspectors and 15 grade II inspectors in the company, find the
optimal assignment of inspectors that minimise the daily
inspection cost.
 TRIM LOSS PROBLEM
• A manufacturer of cylindrical containers receives tin sheets in
widths of 30 cm and 60 cm respectively. For these containers
the sheets are to be cut to three different widths of 15 cm, 21
cm and 27 cm respectively. The number of containers to be
manufactured from these three widths are 400, 200 and 300
respectively. The bottom plates and top covers of the
containers are purchased directly from the market. There is no
limit on the lengths of standard tin sheets.
• Formulate the LPP for the production schedule that minimises
the trim losses.
 MEDIA SELECTION
• An advertising agency is planning to launch an ad campaign.
Media under consideration are T.V., Radio & Newspaper. Each
medium has different reach potential and different cost.
• Minimum 10, 000, 000 households are to be reached through
T.V. Expenditure on newspapers should not be more than Rs.
10, 00, 000. Total advertising budget is Rs. 20 million. Following
data is available:
 DIET PROBLEM
• Vitamins B1 and B2 are found in two foods F1 and F2. 1 unit of
F1 contains 3 units of B1 and 4 units of B2. 1 unit of F2
contains 5 units of B1 and 3 units of B2 respectively.
• Minimum daily prescribed consumption of B1 & B2 is 50 and
60 units respectively. Cost per unit of F1 & F2 is Rs. 6 & Rs. 3
respectively.
• Formulate as LPP.
 BLENDING PROBLEM
• A manager at an oil company wants to find optimal mix of two
blending processes.
• Formulate LPP.
 FARM PLANNING
• A farmer has 200 acres of land. He produces three products X, Y & Z. Average yield
per acre for X, Y & Z is 4000, 6000 and 2000 kg. Selling price of X, Y & Z is Rs. 2, 1.5 &
4 per kg respectively. Each product needs fertilizers. Cost of fertilizer is Rs. 1 per kg.
Per acre need for fertilizer for X, Y & Z is 200, 200 & 100 kg respectively. Labour
requirements for X, Y & Z is 10, 12 & 10 man hours per acre. Cost of labour is Rs. 40
per man hour. Maximum availability of labour is 20, 000 man hours.
Formulate as LPP to maximise profit.
 MERITS OF LPP
• 1. Helps management to make efficient use of resources.
• 2. Provides quality in decision making.
• 3. Excellent tools for adjusting to meet changing demands.
• 4. Fast determination of the solution if a computer is used.
• 5. Provides a natural sensitivity analysis.
• 6. Finds solution to problems with a very large or infinite
number of possible solution.
 DEMERITS OF LPP
• 1. Existence of non-linear equation: The primary requirements of Linear
Programming is the objective function and constraint function should be
linear. Practically linear relationship do not exist in all cases.
• 2. Interaction between variables: LP fails in a situation where non-
linearity in the equation emerge due to joint interaction between some
of the activities like total effectiveness.
• 3. Fractional Value: In LPP fractional values are permitted for the
decision variable.
• 4. Knowledge of Coefficients of the equation: It may not be possible to
state all coefficients in the objective function and constraints with
certainty.
 Development (Formulation) of LP Model
PRODUCT (PRODUCTION) MIX PROBLEM # 1:
A firm is engaged in producing two products ‘A’ and ‘B’. Each unit of product ‘A’ requires 3Kg of raw material and 5 labor hour
for processing, where as each unit of product ‘B’ requires 6Kg of raw material and 4 labor hours of the same type. Every month
the firm has the availability of 60Kg of raw material and 70 Labor hours. One unit of product ‘A’ sold earns profit Rs. 30 and
one unit of product ‘B’ sold gives Rs. 40 as profit.
Formulate this problem as linear programming problem to determine as to how many units of each of the products should be
produced per month so that the firm can earn maximum profit, assume all unit produced can be sold in the market.

CONSTRAINTS:
Decision Variables: Let X1 and X2 be the number of Material Constraint: 3X1 + 6X2 ≤ 60
products ‘A’ and ‘B’ respectively. Labor Constraint: 5X1 + 4X2 ≤ 70
Non–negativity Constraint: As X1 and X2, being the number
Objective Function:
of units produced of products ‘A’ and ‘B’ cannot have
Product – A: As, ‘X1’ are the units of product ‘A’, So,
negative values thus, X1≥0 and X2≥0. i.e. X1,X2 ≥ 0.
Product ‘A’ contributes a profit of Rs. 30X1 from one
unit of product. The Complete LP problem model is:
Product – B: As, X2 are the units of product ‘B’, So, Maximize: Z = 30X1 + 40X2
Product ‘B’ contributes a profit of Rs. 40X2 from one Subject to:
unit of product. 3X1 + 6X2 ≤ 60
5X1 + 4X2 ≤ 70
Maximize Z = 30X1 + 40X2 24
X1 , X2 ≥ 0
 Development (Formulation) of LP Model
PRODUCT (PRODUCTION) MIX PROBLEM # 2:

25
 Development (Formulation) of LP Model
PRODUCT (PRODUCTION) MIX PROBLEM # 2:

Decision Variables:  Let X1 & X2 be the number of bowls and mugs produced, respectively.

Objective Function:  Maximize: Z = 40X1 + 50X2

LP MODEL: Maximize: Z = 40X1 + 50X2
Constraints:  (Profit Function)
X1 + 2X2 ≤ 40 (Labor Constraint) SUBJECT TO:
4X1 + 3X2 ≤ 120 (Clay Constraint) X1 + 2X2 ≤ 40 (Labor Constraint)
X1, X2 ≥0 (Non–Negativity) 4X1 + 3X2 ≤ 120 (Clay Constraint)
X1, X2 ≥ 0 26
(Non–Negativity)
 Development (Formulation) of LP Model
PRODUCT (PRODUCTION) MIX PROBLEM # 3: Four varieties of ties produced: i) one is an expensive, all-silk tie, ii) one is an all-
polyester tie, and iii) two are blends of polyester and cotton. The table on the following slide illustrates the cost and availability (per monthly
production planning period) of the three materials used in the production process

 The following table summarizes the contract demand for each of

o the four styles of ties,
o the selling price per tie, and
o the fabric requirements of each variety.

Fifth Avenue’s goal is to maximize its monthly

profit. It must decide upon a policy for product
mix.

DECISION VARIABLES: Subject to:

Let X1 = # of all-silk ties; 0.125X1 ≤ 800 (Total Silk Availability Constraint)
X2 = # polyester ties; 0.08X2 + 0.05X3 + 0.03X4 ≤ 3,000 (Total Polyester Availability Constraint)
X3 = # of blend 1 poly-cotton ties; 0.05X3 + 0.07X4 ≤ 1,600 (Total Cotton Availability Constraint)
X4 = # of blend 2 poly-cotton ties produced per month X1 ≥ 6,000 (Contract Constraint – 1)
X2 ≥ 10,000 (Contract Constraint – 2)
Calculate profit for each tie: Profit = Sales price – (Cost per yard * Yards per tie) X3 ≥ 13,000 (Contract Constraint – 3)
Silk ties = $6.70 – $21 x 0.125 = $4.08 X4 ≥ 6,000 (Contract Constraint – 4)
Polyester = $3.55 – $6 x 0.08 = $3.07 X1 ≤ 7,000 (Demand Constraint – 1)
Poly-blend 1 = $4.31 – ($6 x 0.05 + $9 x 0.05) = $3.56 X2 ≤ 14,000 (Demand Constraint – 2)
Poly-blend 2 = $4.81 – ($6 x 0.03 + $9 x 0.07) = $4.00 X3 ≤ 16,000 (Demand Constraint – 3)
Objective function: maximize profit = $4.08X1 + $3.07X2 + $3.56X3 + $4.00X4 X4 ≤ 8,500 (Demand Constraint – 4)
X ,X ,X ,X ≥ 0 (Non-Negativity Constraints)
 Development (Formulation) of LP Model
PRODUCT (PRODUCTION) MIX PROBLEM # 4: A company produces three types of parts for automatic washing machines. It
purchases castings of the parts from a local foundry & then finishes the parts on drilling, shaping, & polishing machines. The selling prices
of parts A, B, & C respectively are Rs. 8, Rs. 10 & Rs. 14. All parts made can be sold. Castings of parts A, B, & C respectively, cost Rs. 5,
Rs. 6, & Rs. 10. The company possesses only one of each type of machine. Costs per hour to run each of the three machines are Rs. 20 for
drilling, Rs. 30 for shaping, & Rs. 30 for polishing. The capacities (parts per hour) for each part on each machine are shown in the following
table: Capacity Per Hour
Machine
Part ‘A’ Part ‘B’ Part ‘C’
Drilling 25 40 25
Shaping 25 20 20
Polishing 40 30 40
The manager of the company wants to know how many of each type to produce per hour in order to maximize profit for the hour’s run.
Formulate the problem as a LP model.

Decision Variable: Let X1, X2, & X3 to be the number of three

type of parts to be produced per hour, respectively.
Max. Z = 0.25X1+X2+0.95X3
Contribution Per Hour
Particulars
Part ‘A’ Part ‘B’ Part ‘C’ Subject to:
a. Purchase Price 5 6 10 1/25X1+1/40X2+1/25X3 ≤ 1 (Drilling Constraint)
b. Drilling Cost 20/25 = 0.80 20 / 40 = 0.50 20 / 25 = 0.80 1/25X1+1/20X2+1/20X3 ≤ 1 (Shaping Constraint)
c. Shaping Cost 30 / 25 = 1.20 30 / 20 = 1.50 30 / 20 = 1.50 1/40X1+1/30X2+1/40X3 ≤ 1 (Polishing Constraint)
d. Polishing Cost 30 / 40 = 0.75 30 / 30 = 1.00 30 / 40 = 0.75 X1, X2, X3 ≥ 0 (Non–Negativity Constraint)
e. Total Cost 7.75 9.00 13.05
f. Selling Price 8.00 10.00 14.00
28
g. Profit (f – e) 0.25 1.00 0.95
 Linear Programming: Model Formulation
PORTFOLIO SELECTION PROBLEM: Mr. Ali has Rs. 70, 000 to investment in several alternatives. The alternative investments are
national certificates with an 8.5% return, Defense Savings Certificates with a 10% return, NIT with a 6.5% return, and khas deposit with a
return of 13%. Each alternative has the same time until maturity. In addition, each investment alternative has a different perceived risk thus
creating a desire to diversify. Ali wants to know how much to invest in each alternative in order to maximize the return.
The following guidelines have been established for diversifying the investments and lessening the risk;
 No more than 20% of the total investment should be in khas deposit.
 The amount invested in Defense Savings Certificates should not exceed the amount invested in the other three alternatives.
 At least 30% of the investment should be in NIT and Defense Savings Certificates.
 The ratio of the amount invested in national certificates to the amount invested in NIT should not exceed one to three.
Formulate the problem as a LP model.

DECISION VARIABLES: Let X1, X2, X3 & X4 be the amount (Rs.) invested in national certificates, Defense savings certificates, NIT, and
khas deposit, respectively.

OBJECTIVE FUNCTION: Maximize (the total return from all investment): Z = 0.085X1 + 0.100X2 + 0.065X3 + 0.130X4
CONSTRAINTS:  LP MODEL:
X1 + X2 + X3 + X4 = 70,000 (Amount Availability Constraint) Maximize Z = 0.085X1 + 0.100X2 + 0.065X3 + 0.130X4 (Investment return Function)
X4 ≤ (0.20 x 70,000 = 14,000) (Investment Constraint – i) SUBJECT TO:
X1 + X2 + X3 + X4 = 70,000 (Amount Availability Constraint)
X2 ≤ (X1 + X3 + X4)  X2 – X1 – X3 – X4 ≤ 0 (Investment Constraint – ii) X4 ≤ 14,000 (Investment Constraint – i)
X2 + X3 ≥ (0.30 x 70,000 = 21, 000) (Investment Constraint – iii) X2 – X1 – X3 – X4 ≤ 0 (Investment Constraint – ii)
(X1) / (X3) ≤ 1/3  3X1 – X3 ≤ 0 (Investment Constraint – iv) X2 + X3 ≥ 21, 000 (Investment Constraint – iii)
X1, X2, X3 , X4 ≥ 0 (Non–Negativity Constraint) 3X1 – X3 ≤ 0 (Investment Constraint – iv)
X1, X2, X3, X4 ≥ 0 (Non – Negativity Constraint)
 Resource Allocation Problem
 All allocation models have in common that they attempt to allocate a scarce resource
so as to optimize the consequence of that allocation.
o The “Product Mix Problem” is a special case of the resource allocation
problem
o An agricultural allocation problem
• Amount of farmland that is devoted to the 𝑖𝑡ℎ activity; maximize profit
o A portfolio selection problem
o the investor selecting the optimal portfolio from a set of possible portfolios
𝑛
Indices:
 𝑖 = 1…𝑛 Activities (Products) 𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 Prof𝑖𝑡 = 𝑝𝑖 𝑥𝑖
 𝑗 = 1…𝑚 Resources (Machines) 𝑖=1
Parameters: Subject to:
 𝑝𝑖 = Profit for activity ‘𝑖’
𝑛
 𝑏𝑗 = Amount available of resource ‘𝑗’
 𝑎𝑖𝑗 = Amount of resource ‘𝑗’ used by a unit of activity ‘𝑖’ 𝑎𝑖𝑗 𝑥𝑖 ≤ 𝑏𝑗 𝑓𝑜𝑟 𝑗 = 1,2, . . . , 𝑚
𝑖=1
Decision Variables: 𝑥𝑖 ≥ 0 𝑓𝑜𝑟 𝑖 = 1,2, . . . , 𝑛
𝑥𝑖 = Amount of activity ‘𝑖’ selected 30
 Linear Programming: Model Formulation
PRODUCTION PLANNING PROBLEM: Let us consider a company making a single product. The estimated demand for
the product for the next four months are 1000, 800, 1200, 900 respectively. The company has a regular time capacity of 800
per month and an over time capacity of 200 per month. The cost of regular time production is Rs. 20 per unit and the cost of
over time production is Rs. 25 per unit. The company can carry inventory to the next month and the holding cost is Rs. 3 per
unit per month. The demand has to be met every month. Formulate linear programming problem for the above situation.

DECISION VARIABLES:
 Let Rt = Quantity Produced Using Regular time in month ‘t’  t = 1, 2, 3, 4
1st Way
 Let Ot = Quantity Produced Using Over time in month ‘t’  t = 1, 2, 3, 4
 Let It = Quantity Carried at the end of month ‘t’ to the next month  t = 1, 2, 3
OBJECTIVE FUNCTION:
Minimize (the total cost): Z = 20 (R1+R2+R3+R4) + 25(O1+O2+O3+O4) + 3 (I1+I2+I3)
CONSTRAINTS: 
Demand Constraints:
R1 +O1 = 1000 + I1
I1 + R2 + O2 = 800 + I2
I2 + R3 + O3 = 1200 + I3
I3 + R4 + O4 = 900
Capacity Constraints:
Rt ≤ 800 Where t = 1, 2, 3, 4
Ot ≤ 200 Where t = 1, 2, 3, 4
Non–Negativity Constraints:
Rt , Ot , It ≥ 0
12 Constraints & 11 Variables
 Linear Programming: Model Formulation…
DECISION VARIABLES: 2nd Way
 Let Rt = Quantity Produced Using Regular time in month ‘t’  t = 1, 2, 3, 4
 Let Ot = Quantity Produced Using Over time in month ‘t’  t = 1, 2, 3, 4

OBJECTIVE FUNCTION:
Minimize (the total cost):
Z = 20 (R1+R2+R3+R4) + 25(O1+O2+O3+O4) + 3 (R1 + O1 – 1000) + 3 (R1 + O1 + R2 + O2 – 1800) + 3 (R1 + O1 + R2 + O2 +
R3 + O3 – 3000) + 3 (R1 + O1 + R2 + O2 + R3 + O3 + R4 + O4 – 3900)

CONSTRAINTS: 
Demand Constraints:
R1 + O1 ≥ 1000
R1 + O1 – 1000 + R2 + O2 ≥ 800
R1 + O1 + R2 + O2 – 1000 – 800 + R3 + O3 ≥ 1200
R1 + O1 + R2 + O2 + R3 + O3 – 1000 – 800 – 1200 + R4 + O4 ≥ 900
Capacity Constraints:
Rt ≤ 800 Where t = 1, 2, 3, 4
Ot ≤ 200 Where t = 1, 2, 3, 4
Non–Negativity Constraints:
Rt , Ot ≥ 0
12 Constraints & 8 Variables
 Linear Programming: Model Formulation…
A Production Planning Problem (Single Product, Multi-period ): Suppose a production manager is responsible for scheduling the monthly
production levels of a certain product for a planning horizon of twelve months.
For planning purposes, the manager was given the following information:
 The total demand for the product in month 𝑡 is 𝑑𝑡 , for 𝑡 = 1, 2, . . . , 12. These could either be targeted values or be based on forecasts.
𝑝
 The cost of producing each unit of the product in month 𝑡 is 𝑐𝑡 (Rs.), for 𝑡 = 1, 2, . . . , 12. There is no setup/fixed cost for production.
 The inventory holding cost per unit for month 𝑡 is 𝑕𝑡 (Rs.), for 𝑡 = 1, 2, . . . , 12. These are incurred at the end of each month.
 The production capacity for month 𝑡 is 𝐶𝑡 , for 𝑡 = 1, 2, . . . , 12.
The manager’s task is to generate a production schedule that minimizes the total production and inventory-holding costs over this twelve-month
planning horizon.
Assumption:
1. There is no initial inventory at the beginning of the first month.
2. Shortage of the product is not allowed at the end of any month.
 Linear Programming: Model Formulation…
A Production Planning Problem (Single Product, Multi-period ): Suppose a production manager is responsible for scheduling the monthly
production levels of a certain product for a planning horizon of twelve months.
For planning purposes, the manager was given the following information:
 The total demand for the product in month 𝑡 is 𝑑𝑡 , for 𝑡 = 1, 2, . . . , 12. These could either be targeted values or be based on forecasts.
𝑝
 The cost of producing each unit of the product in month 𝑡 is 𝑐𝑡 (Rs.), for 𝑡 = 1, 2, . . . , 12. There is no setup/fixed cost for production.
 The inventory holding cost per unit for month 𝑡 is 𝑕𝑡 (Rs.), for 𝑡 = 1, 2, . . . , 12. These are incurred at the end of each month.
 The production capacity for month 𝑡 is 𝐶𝑡 , for 𝑡 = 1, 2, . . . , 12.
The manager’s task is to generate a production schedule that minimizes the total production and inventory-holding costs over this twelve-month
planning horizon.
Assumption:
1. There is no initial inventory at the beginning of the first month.
2. Shortage of the product is not allowed at the end of any month.

Objective Function:  Index:

𝑇 𝑇
o 𝑡: 𝑇𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑
𝑝  Data & Parameters:
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒: 𝑐𝑡 𝑄𝑡 + 𝑕𝑡 𝐼𝑡 𝑝
o 𝑐𝑡 : 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑒𝑎𝑐𝑕 𝑢𝑛𝑖𝑡 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 t
𝑡=1 𝑡=1
o 𝑕𝑡 : 𝐼𝑛𝑣𝑒𝑛𝑡𝑜𝑟𝑦 𝑕𝑜𝑙𝑑𝑖𝑛𝑔 𝑐𝑜𝑠𝑡 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡
Constraints: o 𝐶𝑡 : 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡
𝐼𝑡 = 𝐼𝑡−1 + 𝑄𝑡 − 𝑑𝑡 , 𝑡 = 1,2, … , 𝑇 o 𝑑𝑡 : 𝑑𝑒𝑚𝑎𝑛𝑑 𝑜𝑓 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡
 Decision Variable:
𝑄𝑡 ≤ 𝐶𝑡 , 𝑡 = 1,2, … , 𝑇 o 𝑄𝑡 : 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡
𝑄𝑡 , 𝐼𝑡 ≥ 0 o 𝐼𝑡 : 𝐼𝑛𝑣𝑒𝑛𝑡𝑜𝑟𝑦 𝑖𝑛 𝑡𝑖𝑚𝑒 𝑝𝑒𝑟𝑖𝑜𝑑 𝑡
 LINEAR PROGRAMMING: MODEL FORMULATION
A marketing manager wishes to allocate his annual advertising budget of Rs. 20,000
in two media ‘A’ and ‘B’. The unit cost of message in media ‘A’ is Rs. 1000 and in
media ‘B’ is Rs. 1500. Media ‘A’ is the monthly magazine and is desired in one issue.
At least 5 messages should appear in media ‘B’. The expected effective audience for
one message in media ‘A’ is 40,000 and for media ‘B’ is 50,000. Formulate the
problem as a LP model.

Decision Variables: 
Let X1, X2 be the number of messages in media ‘A’ and ‘B’, respectively.
Objective Function: Maximize: Z = 40,000X1 + 50,000X2 (Effective Audience Function)
Constraints: 
1000X1 + 1500X2 ≤ 20,000 (Cost Constraint)
X1 ≤ 1 (Program Constraint – i)
X2 ≥ 5 (Program Constraint – ii)
X1, X2 ≥ 0 (Non–Negativity Constraint)
LP MODEL: Maximize: Z = 40,000X1 + 50,000X2 (Effective Audience Function)
SUBJECT TO:
1000X1 + 1500X2 ≤ 20,000 (Cost Constraint)
X1 ≤ 1 (Program Constraint – i)
X2 ≥ 5 (Program Constraint – ii)
X1, X2 ≥ 0 (Non–Negativity Constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 The Apex Television Company has to decide on the number of 27- and 20-inch sets to be
produced at one of its factories. Market research indicates that at most 40 of the 27-inch
sets and 10 of the 20-inch sets can be sold per month. The maximum number of work-
hours available is 500 per month. A 27-inch set requires 20 work-hours and a 20-inch set
requires 10 work-hours. Each 27-inch set sold produces a profit of $120 and each 20-inch
set produces a profit of $80. A wholesaler has agreed to purchase all the television sets
produced if the numbers do not exceed the maxima indicated by the market research.

Decision Variables: 
Let x1 = number of 27-inch TV sets to be produced per month,
x2 = number of 20-inch TV sets to be produced per month
Objective Function: Maximize: Z = 120 x1 + 80 x2 (Total Profit Per Month)
Constraints: 
x1  40 (Number of 27-inch sets sold per month)
x2  10 (Number of 20-inch sets sold per month)
20 x1 + 10 x2  500 (Work-hours availability)
X1, X2 ≥ 0 (Non–Negativity Constraint)
LP MODEL: Maximize Z = 120 x1 + 80 x2,
SUBJECT TO:
x1  40
x2  10
20 x1 + 10 x2  500
X , X ≥ 0 (Non–Negativity Constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 A store sells men's and women's tennis shoes. It makes a profit of $1 per pair of
men's shoes and $1.20 per pair of women's shoes. It takes two minutes of a
salesperson's time and two minutes of a cashier's time to sell a pair of men's
shoes. It takes three minutes of a salesperson's time and one minute of a
cashier's time per pair of women's shoes. The store is open eight hours per day,
during which time there are two salespersons and one cashier on duty. How
many pairs of shoes of each type should the store sell in order to maximize profit
each day?
Decision Variables:
Let X1, X2 be the # of pair of men’s & women’s shoes, respectively.
Objective Function: Maximize the Profit: Maximize: Z = $1X1 + $1.20X2
Constraints:
2X1 + 3X2 ≤ (2 X 8 X 60 = 960 Minutes) (Sales Persons Constraint)
2X1 + 1X2 ≤ (8 X 60 = 480 Minutes) (Cashier’s Constraint)
X1, X2 ≥ 0 (Non–Negativity Constraint)
LP MODEL: Maximize: Z = 1X1 + 1.20X2 (Profit Function)
SUBJECT TO:
2X1 + 3X2 ≤ 960 (Sales Persons Constraint)
2X1 + 1X2 ≤ 480 (Cashier’s Constraint)
X1, X2 ≥ 0 (Non–Negativity Constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 A company manufactures two products ‘A’ and ‘B’. These products are processed in the
same machine. It takes 10 minutes to process one unit of product ‘A’ and ‘2’ minutes for
each unit of product ‘B’ and machine operates for a maximum of 35 hours in a week.
Product ‘A’ requires 1 kg. and ‘B’ 0.5 kg. of raw material per unit the supply of which is 600
kg. per week. Market constraint on product ‘B’ is known to be 800 units every week.
Product ‘A’ costs Rs. 5 per unit and sold at Rs. 10. Product ‘B’ costs Rs. 6 per unit and can be
sold in the market at a unit price of Rs. 8. Determine the number of units of ‘A’ and ‘B’ per
week to maximize the profit.
Decision Variables: Let X1, X2 be the # of products ‘A’ and ‘B’, respectively.
Objective Function: Maximize the Profit.
Product – A: Cost of product ‘A’ per unit is Rs. 5 and sold at Rs. 10 per unit. So, Profit on one
unit of product ‘A’ = 10 – 5 = Rs. 5.
Product – B: Cost of product ‘B’ per unit is Rs. 6 and sold at Rs. 8 per unit. So, Profit on one
unit of product ‘B’ = 8 – 6 = Rs. 2.
Maximize: Z = 5X1 + 2X2
LP MODEL: Maximize: Z = 5X1 + 2X2 (Profit Function)
SUBJECT TO:
10X1 + 2X2 ≤ (35X60) = 2100 (Time Requirement Constraint)
X1 + 0.5X2 ≤ 600 (Raw Material Constraint)
X2 ≥ 800 (Market Demand for Product ‘B’ Constraint)
X1 , X2 ≥ 0 (Non–Negativity Constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 ABC advertising agency wishes to reach two types of audiences; Customers with annual income of more
than Rs. 20,000 (i.e.: Target Audience–A) and Customers with annual income of less than Rs. 20,000
((i.e.: Target Audience–B). The total advertising budget is Rs. 2,00,000. One T.V. advertising costs Rs.
50,000 and one radio advertising costs Rs. 20,000. For contract reasons, at least 3 advertisements have
to be on T.V. and the number of radio advertisements must be limited to 5. Surveys indicate that a single
T.V. advertisement reaches 4,50,000 customers in Target Audience–A and 50,000 in the Target Audience–
B. One radio advertisement researches 20,000 in Target Audience–A and 80,000 in the Target Audience–
B. Formulate the given problem in such a way that the media–mix to maximize the total audience reach.

Decision Variables:
Let X1 and X2 be the number of advertisements on T.V. and Radio, respectively.
Objective Function:
T.V.: Number of customers with annual income more than Rs. 20,000 is 4,50,000 while the
number of customers with annual income less than Rs. 20,000 is 50,000. So,
Total T.V. Audience = 4,50,000 + 50,000 = 5,00,000.
Radio: Number of customers with annual income more than Rs. 20,000 is 20,000 while the
number of customers with annual income less than Rs. 20,000 is 80,000. So,
Total Radio Audience = 20,000 + 80,000 = 1,00,000.
MAXIMIZE: Z = 5,00,000X1 + 1,00,000X2 TOTAL AUDIENCE REACH
CONSTRAINTS: 
50,000X1 + 20,000X2 ≤ 2,00,000 (Total available amount constraint)
X1 ≥ 3 (Minimum T.V. advertisement constraint)
X2 ≤ 5 (Maximum Radio advertisement constraint)
X1,X2 ≥ 0 (Non–Negativity constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 The Service Shoe Company has contracted with an advertising firm to determine the types
and amount of advertising it should have for its stores. The three types of advertising
available are radio and television commercials and newspaper ads. The retail store desires to
know the number of each type of advertisement it should purchase in order to Maximize
exposure. It is estimated that each ad and commercial will reach the following potential
audience and cost the following amount.

Type of Advertisement Exposure (people/ad or commercial) Cost

Television commercial 20,000 Rs. 15,000
Radio commercial 12,000 Rs. 8,000
Newspaper ad. 9,000 Rs. 4,000

The following resource constraints exist:

1. There is a budget limit of Rs. 100,000 available for advertising.
2. The television station has enough time available for four commercials.
3. The radio station has enough time available for ten radio commercials.
4. The newspaper has enough space available for seven ads.
5. The advertising agency has time and staff to produce at most a total of fifteen
commercials ads.
Formulate the problem as a LP model.
 LINEAR PROGRAMMING: MODEL FORMULATION
Decision Variables: Let X1, X2 & X3 be the number of Television commercial,
Radio commercial and Newspaper ad respectively.

Objective Function: Maximize (the total number of audience exposures):

Z = 20,000X1 + 12,000X2 + 9,000X3
Constraints: 
15, 000 X1 + 6, 000 X2 + 4, 000 X3 ≤ 100, 000 (Advertisement Budget Constraint)
X1 ≤ 4 (Time / Space Constraint – i)
X2 ≤ 10 (Time / Space Constraint – ii)
X3 ≤ 7 (Time / Space Constraint – iii)
X1 + X2 + X3 ≤ 15 (Limitations of commercials / ads constraint)
X1, X2, X3 ≥ 0 (Non–Negativity Constraint)
LP MODEL:
Maximize : Z = 20, 000 X1 + 12, 000 X2 + 9, 000 X3 (Audience Exposures Fuction)
SUBJECT TO:
15, 000 X1 + 6, 000 X2 + 4, 000 X3 ≤ 100, 000 (Advertisement Budget Constraint)
X1 ≤ 4 (Time / Space Constraint – i)
X2 ≤ 10 (Time / Space Constraint – ii)
X3 ≤ 7 (Time / Space Constraint – iii)
X1 + X2 + X3 ≤ 15 (Limitations of commercials / ads constraint)
X1, X2, X3 ≥ 0 (Non–Negativity Constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 Mr. Saqib has Rs. 70, 000 to invest in several alternatives. The alternative
investments are national certificates with an 8.5% return, Defense Savings
Certificates with a 10% return, NIT with a 6.5% return, and khas deposit with a
return of 13%. Each alternative has the same time until maturity. In addition,
each investment alternative has a different perceived risk thus creating a desire
to diversify. Saqib wants to know how much to invest in each alternative in order
to maximize the return.
The following guidelines have been established for diversifying the investments
and lessening the risk;
 No more than 20% of the total investment should be in khas deposit.
 The amount invested in Defense Savings Certificates should not exceed the
amount invested in the other three alternatives.
 At least 30% of the investment should be in NIT and Defense Savings
Certificates.
 The ratio of the amount invested in national certificates to the amount
invested in NIT should not exceed one to three.
Formulate the problem as a LP model.
 LINEAR PROGRAMMING: MODEL FORMULATION
DECISION VARIABLES: Let X1, X2, X3 & X4 be the amount (Rs.) invested in national
certificates, Defense savings certificates, NIT, and khas deposit, respectively.

OBJECTIVE FUNCTION: Maximize (the total return from all investment):

Z = 0.085X1 + 0.100X2 + 0.065X3 + 0.130X4
CONSTRAINTS: 
X1 + X2 + X3 + X4 = 70,000 (Amount Availability Constraint)
X4 ≤ (0.20 x 70,000 = 14,000) (Investment Constraint – i)
X2 ≤ (X1 + X3 + X4)  X2 – X1 – X3 – X4 ≤ 0 (Investment Constraint – ii)
X2 + X3 ≥ (0.30 x 70,000 = 21, 000) (Investment Constraint – iii)
(X1) / (X3) ≤ 1/3  3X1 – X3 ≤ 0 (Investment Constraint – iv)
X1, X2, X3 , X4 ≥ 0 (Non–Negativity Constraint)
LP MODEL:
Maximize Z = 0.085X1 + 0.100X2 + 0.065X3 + 0.130X4 (Investment return Function)
SUBJECT TO:
X1 + X2 + X3 + X4 = 70,000 (Amount Availability Constraint)
X4 ≤ 14,000 (Investment Constraint – i)
X2 – X1 – X3 – X4 ≤ 0 (Investment Constraint – ii)
X2 + X3 ≥ 21, 000 (Investment Constraint – iii)
3X1 – X3 ≤ 0 (Investment Constraint – iv)
X1, X2, X3, X4 ≥ 0 (Non – Negativity Constraint)
 LINEAR PROGRAMMING: MODEL FORMULATION
 A Hotel remains open 24 hours a day. Waiters and busboys report for duty at 2
a.m., 6 a.m., 10 a.m., 2 p.m., 6 p.m. or 10 p.m. and each works an 8 hour shift. The
following table shows the minimum number of workers needed during the six
periods into which the day is divided. The hotel’s scheduling problem is to
determine how many waiters and busboys should report for work at the start of
each period in order to minimize the total staff required for one day’s operations.

Period Time Number of Waiters and Busboys required

1 2 a.m. – 6 a.m. 4
2 6 a.m. – 10 a.m. 13
3 10 a.m. – 2 p.m. 15
4 2 p.m. – 6 p.m. 8
5 6 p.m. – 10 p.m. 12
6 10 p.m. – 2 a.m. 5

Formulate the problem as a LP model.

 LINEAR PROGRAMMING: MODEL FORMULATION

DECISION VARIABLES: Let X1, X2, X3, X4, X5, X6 be the number of waiters and
Busboys in time periods.

PERIODS MINIMUM REQUIREMENTS

1 and 2 13
2 and 3 15
3 and 4 8
4 and 5 12
5 and 6 5
6 and 1 4
THE COMPLETE LP MODEL IS:
Minimize: Z = X1 + X2 + X3 + X4 + X5 + X6 (Waiters & Busboys Function)
Subject to :
X1 + X2 ≥ 13 (Waiters & Busboys requirement for periods 1 & 2 Constraint)
X2 + X3 ≥ 15 (Waiters & Busboys requirement for periods 2 & 3 Constraint)
X3 + X4 ≥ 8 (Waiters & Busboys requirement for periods 3 & 4 Constraint)
X4 + X5 ≥ 12 (Waiters & Busboys requirement for periods 4 & 5 Constraint)
X5 + X6 ≥ 5 (Waiters & Busboys requirement for periods 5 & 6 Constraint)
X6 + X1 ≥ 4 (Waiters & Busboys requirement for periods 6 & 1 Constraint)
X1, X2, X3, X4, X5, X6 ≥ 0 (Non – Negativity Constraint)
A Carpenter wants to maximize his profit; the LP
model shows his objective and constraints:
LP Solution: Graphical Method
Maximize: 5 X1 + 3 X2
(X1 = # of Chairs, X2 = # of Tables)
Subject to: Maximize: 5 X1 + 3 X2
2 X1 + X2 ≤ 40 (Where X1 = Number of pencils of Type ‘A’, Minimize: 6 X1 + 14 X2
X1 + 2 X2 ≤ 50 X2 = Number of pencils of Type ‘B’) Subject to:
X1, X2 ≥ 0 Subject to: 5X1 + 4X2 ≥ 60
2 X1 + X2 ≤ 1000 3X1 + 7X2 ≤ 84
Solve the following LP problem graphically: X1 ≤ 400 X1 + 2X2 ≥ 18
Minimize: 6 X1 + 14 X2 X2 ≤ 700 X1, X2 ≥ 0
Subject to: X1, X2 ≥ 0
5X1 + 4X2 ≥ 60
3X1 + 7X2 ≤ 84
X1 + 2X2 ≥ 18
X1, X2 ≥ 0

 Binding Constraints: Satisfy the equality of the constraint at the optimal point.
 Non-Binding Constraints: Not satisfy the equality of the constraint at the optimal point.
 Slack: Unused resources (Zero Vs non-negative quantities)
 Each solution to any system of equations is called a Basic Solution (BS).
 A Basic Feasible Solution (BFS) satisfies the model constraints and has the same number of variables with nonnegative values as there are
constraints.
 Every linear program has an extreme point that is an optimal solution.
 WHAT IS A SYSTEM?
• SYSTEM:
– A system may be defined as a collection of entities
(People, Objects, Elements or Components) interrelated to
each other and to the whole so as to achieve a common
goal.
• ENTITY:
– Entities are units transformed by the system over time.
Entities are not part of, but move through, the system.
Entities may represent customers requesting service,
inventory waiting to be processed, or jobs to be completed.
• ATTRIBUTE:
– AN ATTRIBUTE is a property of an entity.
• ACTIVITY:
– AN ACTIVITY represents a time period of specified length;
alternatively, any process that changes the attributes of an
entity is called an activity.
 WHAT IS A SYSTEM?
• EXAMPLES:
– (BANKING SYSTEM)
• If a banking system is being studied:
– Customers might be one of the entities.
– The balance in their checking accounts might be an
attribute.
– Making deposits might be an activity
– (COMPUTING SYSTEM)
• If a computing system is being studied:
– One of the entity might be computer.
– Cost, Speed, Capability and usefulness may be
attributes.
– The compilation process is its activity.
 MODEL & Its TYPES
• MODEL: A model is a representation of the structure of a
real life system.
– In general, models can be classified as fellows:
• Iconic models
• Analogue models
• Symbolic models

• ICONIC MODELS: An iconic model is a look like

representation of some specific entity (e.g., a house, an
airplane).
• ANALOGUE MODELS: An analogue model uses a set of
properties to represent the properties of a real life
system (e.g., through diagrams).
 MODEL & Its TYPES
• SYMBOLIC MODELS: Symbolic (i.e., algebraic, numerical, logical)
models represent the properties of the real life system through
the means of symbols, mathematical equations, computer
programs and simulation models are also symbolic models.
– DETERMINISTIC MODELS: Deterministic models are models which
do not contain the element of probability. Deterministic models
involve optimization.
• Examples are: Linear programming, Non – linear programming,
Integer programming, Network optimization, and Dynamic
programming.
– STOCHASTIC MODELS: stochastic models are models which contain
the element of probability. Stochastic models characterize/estimate
system performance.
• Examples are: Queuing theory, Stochastic processes, Reliability
theory, and Simulation techniques.
 AREAS OF APPLICATION OF LINEAR
PROGRAMMING
1. INDUSTRIAL APPLICATIONS
 Product mix problems
 Blending Problems
 Productions Scheduling Problems
 Trim Loss Problems
 Assembly Line Balancing
 Make – or – Buy (Sub – Contracting) Problems
2. MANAGEMENT APPLICATIONS
 Media Selection Problems
 Portfolio Selection Problems
 Profit Planning Problems
 Man–Power Scheduling Problem
 Transportation Problems
 Assignment Problems
3. MISCELLANEOUS APPLICATIONS
 Diet Problems
 Agriculture Problems
 Flight Scheduling Problems
 Environment Protection
 Facilities Location
Classification of LP Solution
 Classification of LP Solution
Multiple / Alternative Optimum Solution:
 More than One Optimal Solution:
o Two or more optimal solutions may exist, and
o This actually allows management great flexibility in deciding which combination to select.

Maximize: Z = 4X1 + 4X2

Subject to:
X1 + 2X2 ≤ 10
6X1 + 6X2 ≤ 36
X1 ≤ 4
X1, X2 ≥0

As, at point ‘A’ (2,4) the value of the objective function

is: Z = 4(2) + 4(4) = 24, and at point ‘B’ (4,2) the value
of the objective function is: Z = 4(2) + 4(4) = 24.
 Classification of LP Solution
Unbounded Solution: In some LP models, the values of the variables may be increased indefinitely without
violating any of the constraints in this result the solution space becomes unbounded so As a result the value of the
objective function may increase (in Maximization Case) or decrease (in Minimization Case) indefinitely. But it is
wrong to conclude that just because the solution space is unbounded then solution also unbounded. The solution
space may be unbounded but the solution may be finite.
Example-1: Example-2:
Maximize: Z = 2X1 + X2 Minimize: 6X1 + 4X2
Subject to: X1 – X2 ≤ 10 Subject to:
2X1 ≤ 40 3X1 + 3X2 ≥ 40
X1 , X2 ≥ 0 3X1 + X2 ≥ 40
2X1 + 5X2 ≥ 44
X1, X2 ≥ 0

Optimal value to be 88, at X1 = 12, and X2 = 4.

 Classification of LP Solution
Degeneracy: In LP problems, intersection of two constraints will define a corner point of the feasible region.
But if more than two constraints pass through any one of the corner points of the feasible region, excess
constraints will not serve any purpose, and therefore they act as redundant constraints, so redundant constraints
create the Degeneracy.

Maximize: Z = 4X1 + 6X2

Subject to:
6X1 + 4X2 ≤ 24
X2 ≤ 3
5X1 + 10X2 ≤ 40
X1, X2 ≥ 0

Optimal value to be 26, at X1 = 2, and X2 = 3.

 Classification of LP Solution
Non–Existing / Infeasible Solution: A linear programming problem is infeasible if there is no solution
exists that satisfies all of the constraints.

Maximize: Z = 3X1 + 2X2

Subject to:
2X1 + X2 ≤ 2
3X1 + 4X2 ≥ 12
X1, X2 ≥ 0
QUESTIONS

57