06-12-2023

Linear Programming
Problem (LPP)
Sessions 2 - 4

Linear Programming

 Linear programming method is a technique for choosing the

best alternative from a set of feasible alternatives, in situations
which the objective function as well as the constraints can be
expressed as linear mathematical functions.
 The word programming does not refer here to computer
programming; rather, it is essentially a synonym for planning.
 Thus, linear programming involves the planning of activities to
obtain an optimal result, i.e., a result that reaches the
specified goal best (according to the mathematical model)
among all feasible alternatives.

1
 06-12-2023

Requirements for linear programming

 There should an objective that should be clearly identifiable

and measurable in quantitative terms.
 The activities and resources to be included should be
distinctly identifiable and measurable in quantitative terms.
 Resources must be in limited supply.
 The objective function and the constraint equations or
inequalities must be linear in nature.
 There should be a series of feasible alternative courses of
action available to the decision-maker.

Applications of Linear Programming

 A manufacturer wants to develop a production

schedule and an inventory policy that will satisfy sales
demand in future periods. Ideally, the schedule and
policy will enable the company to satisfy demand and
at the same time minimize the total production and
inventory costs.
 A financial analyst must select an investment portfolio
from a variety of stock and bond investment
alternatives. The analyst would like to establish the
portfolio that maximizes the return on investment.

2
 06-12-2023

Applications of Linear Programming

 A marketing manager wants to determine how best to

allocate a fixed advertising budget among alternative
advertising media such as radio, television, newspaper, and
magazine. The manager would like to determine the media
mix that maximizes advertising effectiveness.
 A company has warehouses in a number of locations
throughout the United States. For a set of customer demands,
the company would like to determine how much each
warehouse should ship to each customer so that total
transportation costs are minimized.

Example 1

 Par, Inc., is a small manufacturer of golf equipment and

supplies whose management has decided to move into the
market for medium- and high-priced golf bags. Par, Inc.’s
distributor is enthusiastic about the new product line and has
agreed to buy all the golf bags Par, Inc., produces over the
next three months.
 After a thorough investigation of the steps involved in
manufacturing a golf bag, management determined that
each golf bag produced will require the following operations:
1. Cutting and dyeing the material
2. Sewing
3. Finishing (inserting umbrella holder, club separators, etc.)
4. Inspection and packaging

3
 06-12-2023

Example 1 contd…

 The director of manufacturing analyzed each of the

operations and concluded that if the company produces a
7
medium-priced standard model, each bag will require hour
10
1
in the cutting and dyeing department, hour in the sewing
2
1
department, 1 hour in the finishing department, and hour in
10
the inspection and packaging department. The more
expensive deluxe model will require 1 hour for cutting and
5 2 1
dyeing, hour for sewing, hour for finishing, and 4 hour for
6 3
inspection and packaging.

Example 1 contd…

 Par, Inc.’s production is constrained by a limited number of

hours available in each department. After studying
departmental workload projections, the director of
manufacturing estimates that 630 hours for cutting and
dyeing, 600 hours for sewing, 708 hours for finishing, and 135
hours for inspection and packaging will be available for the
production of golf bags during the next three months.
 The accounting department analyzed the production data,
assigned all relevant variable costs, and arrived at prices for
both bags that will result in a profit contribution1 of $10 for
every standard bag and $9 for every deluxe bag produced.

4
 06-12-2023

Problem Formulation

 Describe the Objective The objective is to maximize the total contribution to

profit.
 Describe Each Constraints
 Constraint 1: Number of hours of cutting and dyeing time used must be less than
or equal to the number of hours of cutting and dyeing time available.
 Constraint 2: Number of hours of sewing time used must be less than or equal to
the number of hours of sewing time available.
 Constraint 3: Number of hours of finishing time used must be less than or equal to
the number of hours of finishing time available.
 Constraint 4: Number of hours of inspection and packaging time used must be
less than or equal to the number of hours of inspection and packaging time
available.

Problem Formulation

 Define the Decision Variables The controllable inputs for Par, Inc.,
are (1) the number of standard bags produced and (2) the number
of deluxe bags produced. Let
 S = number of standard bags
 D = number of deluxe bags
 Write the Objective in Terms of the Decision Variables Par, Inc.’s
profit contribution comes from two sources: (1) the profit
contribution made by producing S standard bags and (2) the profit
contribution made by producing D deluxe bags. Thus, we have
Total Profit Contribution = 10S + 9D
 The objective function is Max 10S + 9D

5
 06-12-2023

Problem Formulation

 Write the Constraints in Terms of the Decision Variables

7
 Constraint 1: 10 𝑆 + 1𝐷 ≤ 630
1 5
 Constraint 2: 2 𝑆 + 6 𝐷 ≤ 600
2
 Constraint 3: 1𝑆 + 3 𝐷 ≤ 708
1 1
 Constraint 4: 10 𝑆 + 4 𝐷 ≤ 135
 Constraint 5: S, D ≥ 0

Complete Mathematical Model

 Maximize 10S + 9D
 Subject to (s.t.)
7
 𝑆 + 1𝐷 ≤ 630 Cutting & Dyeing
10
1 5
 𝑆 + 𝐷 ≤ 600 Sewing
2 6
2
 1𝑆 + 𝐷 ≤ 708 Finishing
3
1 1
 𝑆 + 𝐷 ≤ 135 Inspection and Packaging
10 4

 S, D ≥ 0

6
 06-12-2023

Example 2: Maximization Case

 A firm is engaged in producing two products, A and B. Each

unit of product A requires 2 kg of raw material and 4 labor
hours for processing, whereas each unit of product B requires
3 kg of raw material and 3 hours of labor, of the same type.
Every week the firm has an availability of 60 kg of raw material
and 96 labor hours. One unit of product A sold yields Rs. 40
and one unit of product B sold gives Rs. 35 as profit.
 Formulate the problem as a linear programming problem to
determine how many units of each of the products should be
produced per week so that the firm can earn the maximum
profit. Assume that there is no marketing constraint so that all
that is produced can be sold.

Solution

 Decision variables:
 Let
 𝑥1 = number of units produced of product A
 𝑥2 = number of units produced of product B
 The objective function:
 Maximize Z = 40 𝑥1 + 35 𝑥2
 Constraints
 2 𝑥1 + 3 𝑥2 ≤ 60
 4 𝑥1 + 3 𝑥2 ≤ 96
 𝑥1 , 𝑥2 ≥ 0

7
 06-12-2023

Example 3: Minimization Case

 The Agricultural Research Institute suggested to a farmer to spread

out at least 4800 kg of a special phosphate fertilizer and not less
than 7200 kg of a special nitrogen fertilizer to raise productivity of
crops in his fields. There are two sources for obtaining these—
mixtures A and B. Both of these are available in bags weighing 100
kg each and they cost Rs. 40 and Rs. 24 respectively. Mixture A
contains phosphate and nitrogen equivalent of 20 kg and 80 kg
respectively, while mixture B contains these ingredients equivalent
of 50 kg each. Write this as a linear programming problem to
determine how many bags of each type the farmer should buy in
order to obtain the required fertilizer at minimum cost.

Solution

 Decision variables
 Let
 𝑥1 = number of bags of mixture A
 𝑥2 = number of bags of mixture B
 The objective function:
 Minimize Z = 40 𝑥1 + 24 𝑥2
 Constraints
 20 𝑥1 + 50 𝑥2 ≥ 4800
 80 𝑥1 + 50 𝑥2 ≥ 7200
 𝑥1 , 𝑥2 ≥ 0

8
 06-12-2023

General Statement of Linear

Programing Problems
 In general terms, a linear programing problem can be written as:
 Maximize Z = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
 Subject to
 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
 .
 .
 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
 𝑥1 , 𝑥2 ,…, 𝑥𝑛 ≥ 0

Characteristics of the constraints

 Generally, the constraints in the maximization problems are of the ≤

type, and of the ≥ type in the minimization problems. But a given
problem may contain a mix of the constraints, involving ≤, ≥, and/ or
=.
 Usually, the decision variables are non-negative. However, they
need not always be so.
 Consider an investment problem, where 𝑥1 represents the amount to be
invested in the shares of a particular company, then variable 𝑥1 shall be
non-negative since we may decide to invest (𝑥1 > 0) or not to invest
(𝑥1 =0). But if we already have such shares which may be sold, if the
need be, then 𝑥1 may take positive value (more investment), zero value
(indicating no new investment in it) or negative value (implying
disinvestment in this share). Hence, 𝑥1 shall be unrestricted in sign or a
free variable.

9
 06-12-2023

Assumptions underlying linear

programming
 Proportionality: There is a constant return to scale, i.e., there is no
economies of scale.
 Additivity: In the objective function and constraint inequalities both, the
total of all the activities is given by the sum total of each activity
conducted separately, i.e., there is no interaction among the decision
variables (no product is a byproduct of another)
 Continuity: The decision variables are continuous. As a consequence,
combinations of output with fractional values, in the context of production
problems, are possible and obtained frequently.
 Certainty: The objective function coefficients, the coefficients of the
inequality/ equality of the constraints and the constraint (resource) values
are known with certainty.
 Finite choices: A limited number of choices is available to the decision-
maker and the decision variables do not assume negative values.

Graphical Solution to the Par, Inc.

Problem
 A linear programming
problem involving only two
decision variables can be
solved using a graphical
solution procedure.
 Consider the example of Par,
Inc.

Source: Anderson et al. (2018: 33)

10
 06-12-2023

Feasible region defined by the cutting

and dyeing & sewing constraint

Source: Anderson et al. (2018: 35-36)

Feasible region defined by the finishing

& inspection and packaging constraint

Source: Anderson et al. (2018: 36)

11
 06-12-2023

Combined constraint graph with the

common feasible region

Source: Anderson et al. (2018: 37)

Finding the optimal solution

 One approach to finding the

optimal solution would be to
evaluate the objective function
for each feasible solution; which is
practically not feasible.
 So, to compute the profit
contribution for each feasible
solution, we select an arbitrary
value for profit contribution and
identify all the feasible solutions
(S, D) that yield the selected
value.
 For example, which feasible
solutions provide a profit
contribution of $1800?
 These solutions are given by the
values of S and D in the feasible
region that will make the
objective function 10S + 9D = Source: Anderson et al. (2018: 38)
1800

12
 06-12-2023

Optimal solution

Source: Anderson et al. (2018: 39-40)

Graphical Solution to Example 2

Source: Vohra (2017: 26)

13
 06-12-2023

Graphical Solution to Example 3

Source: Vohra (2017: 28)

Binding, non-binding and redundant

constraints
 A constraint is binding if the left hand side and right hand side of it
are equal when the optimal values of the decision variables are
substituted into the constraint.
 If the substitution of the decision variables does not lead to an
equality of the left-hand and right-hand sides of the constraint, it is
said to be non-binding.
 If and when a constraint, when plotted, does not form part of the
boundary marking the feasible region of the problem, it is said to be
redundant.
 The inclusion or exclusion of the redundant constraint does not affect
the optional solution to the problem.

14
 06-12-2023

Unique and multiple optimal solutions

 When the linear programming problem has a single optimal solution, the
solution is said to be unique.
 The solution (if it exists) of a linear programing problem shall always be
unique if the slope of the objective function is different from the slopes of
the constraint.
 In case the objective function has a slope which is the same as that of a
constraint, then multiple optimal solution may exist.
 Two conditions under which multiple solution exists:
 The objective function is parallel to a constraint that forms an edge or boundary
on the feasible region, and
 The constraint must be a binding constraint

Infeasibility and Unboundedness

 Infeasibility: Sometimes it is possible that the constraints may be inconsistent

so that there is no feasible solution to the problem. Such a situation is called
infeasibility
 Unboundedness: For a maximization type of LPP, unboundedness occurs
when there is no constraint on the solution so that one or more of the
decision variables can be increased indefinitely without violating any of the
restrictions (constraints)
 While both infeasibility and unboundedness both does not give an optimal
solution, infeasibility means there is not a single feasible solution while
unboundedness means that there are infinite feasible solutions but none of
them can be termed as optimal

15
 06-12-2023

Exercise 1

 Solve graphically the following LPP:

 Maximize Z = 8𝑥1 + 16𝑥2
 Subject to:
 𝑥1 + 𝑥2 ≤ 200
 𝑥2 ≤ 125
 3𝑥1 + 6𝑥2 ≤ 900
 𝑥1 , 𝑥2 ≥ 0

Exercise 2

 Solve graphically the following LPP:

 Minimize Z = 6𝑥1 + 14𝑥2
 Subject to:
 5𝑥1 + 4𝑥2 ≥ 60
 3𝑥1 + 7𝑥2 ≤ 84
 𝑥1 + 2𝑥2 ≥ 18
 𝑥1 , 𝑥2 ≥ 0

16
 06-12-2023

Exercise 3

 Solve graphically the following LPP:

 Maximize Z = 20𝑥1 + 30𝑥2
 Subject to:
 2𝑥1 + 𝑥2 ≤ 40
 4𝑥1 − 𝑥2 ≤ 20
 𝑥1 ≥ 30
 𝑥1 , 𝑥2 ≥ 0

Exercise 4

 Solve graphically the following LPP:

 Maximize Z = 10𝑥1 + 20𝑥2
 Subject to:
 2𝑥1 + 4𝑥2 ≥ 16
 𝑥1 + 5𝑥2 ≥ 15
 𝑥1 , 𝑥2 ≥ 0

17
 06-12-2023

Linear Programming Applications in

Marketing, Finance, & Operations

Exercise 5: Media Selection (Marketing)

 The marketing department of Everest Company has collected information
on the problem of advertising for its products. This relates to the advertising
media available, the number of families expected to be reached with
each alternative, cost per advertisement, the maximum availability of each
medium and the expected exposure of each one (measured as the
relative value of one advertisement in each of the media). The information
is given below:
Advertising No. of families Cost per ad Maximum Expected
Media expected to cover (₹) availability (no. exposure (Units)
of times)
TV (30 sec) 3000 8000 8 80

Radio (50 sec) 7000 3000 30 20

Newspaper (1/4 5000 4000 4 50

page) Sunday
edition
Magazine (1 2000 3000 2 60
page)

18
 06-12-2023

Exercise 5 contd…

 Other information and requirements

 The advertising budget is Rs. 70,000
 At least 40,000 families should be covered
 At least two insertions be given in the Sunday edition of a daily but not more than
4 ads should be given on the TV.
 Draft this as a linear programming problem.

Solution
 Decision variables:
 𝑥1 : Number of ads on TV; 𝑥2 : Number of ads on radio
 𝑥3 : Number of ads on newspaper; 𝑥4 : Number of ads in a magazine
 Maximize Z = 80 𝑥1 + 20 𝑥2 + 50 𝑥3 + 60 𝑥4
 Subject to:
 3000 𝑥1 + 7000 𝑥2 + 5000 𝑥3 + 2000 𝑥4 ≥ 40,000
 8000 𝑥1 + 3000 𝑥2 + 4000 𝑥3 + 3000 𝑥4 ≤ 70,000
 𝑥1 ≤8
 𝑥2 ≤ 30
 𝑥3 ≤4
 𝑥4 ≤ 2
 𝑥3 ≥2
 𝑥1 ≤4
 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

19
 06-12-2023

Exercise 6: Portfolio Selection (Finance)

 An investment company is seeking investment opportunities for ₹10,00,000

in various industry sectors. Based on its current investments, the firm’s top
financial analyst recommends that all new investments be made in the oil
industry, in the steel industry, or in government bonds. Specifically, the
analyst identified five investment opportunities and projected their annual
rates of returns, as given below:

Investment Projected Rate of Return (%)

Indian Oil 7.3
Oil and Natural Gas Corporation (ONGC) 10.3
Tata Steel 6.4
Steel Authority of India 7.5
Government bonds 4.5

Exercise 6 contd…

 Management of the company issues the following investment guidelines:

 Neither industry (oil or steel) should receive more than ₹ 5,00,000.
 Government bonds should be at least 25% of the steel industry investments.
 The investment in ONGC, the high-return but high-risk investment, cannot be
more than 60% of the total oil industry investment.
 What portfolio recommendations—investments and amounts—should be
made for the available ₹ 10,00,000?

20
 06-12-2023

Solution to Exercise 6

 Decision variables:
 𝑥1 : Amount invested in Indian Oil; 𝑥2 : Amount invested in ONGC
 𝑥3 : Amount invested in Tata Steel; 𝑥4 : Amount invested in Steel Authority of India
 𝑥5 : Amount invested in Government Bonds
 Maximize Z = 0.073 𝑥1 + 0.103 𝑥2 + 0.064 𝑥3 + 0.075 𝑥4 + 0.045 𝑥5
 Subject to:
 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 10,00,000
 𝑥1 + 𝑥2 ≤ 5,00,000
 𝑥3 + 𝑥4 ≤ 5,00,000
 𝑥5 ≥ 0.25 (𝑥3 + 𝑥4 )
 𝑥2 ≤ 0.60 (𝑥1 + 𝑥2 )
 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0

Exercise 7: Make or Buy Decision

(Operations)
 A company markets various business and engineering products. Currently, it
is preparing to introduce two new calculators: one for the business market
called the Financial Manager and one for the engineering market called
the Technician. Each calculator has three components: a base, an
electronic cartridge, and a faceplate or top. The same base is used for
both calculators, but the cartridges and tops are different. All components
can be manufactured by the company or purchased from outside
suppliers. The manufacturing costs and purchase prices for the components
are summarized in Table below:

21
 06-12-2023

Exercise 7 contd…

 Company forecasters indicate that 3000 Financial Manager calculators

and 2000 Technician calculators will be needed. However, manufacturing
capacity is limited. The company has 200 hours of regular manufacturing
time and 50 hours of overtime that can be scheduled for the calculators.
Overtime involves a premium at the additional cost of $9 per hour. Table
below shows manufacturing times (in minutes) for the components.

 The problem for the company is to determine how many units of each
component to manufacture and how many units of each component to
purchase.

Exercise 7 Solution

 Decision Variables
 BM = number of bases manufactured
 BP = number of bases purchased
 FCM = number of Financial cartridges manufactured
 FCP = number of Financial cartridges purchased
 TCM = number of Technician cartridges manufactured
 TCP = number of Technician cartridges purchased
 FTM = number of Financial tops manufactured
 FTP = number of Financial tops purchased
 TTM = number of Technician tops manufactured
 TTP = number of Technician tops purchased
 OT = number of hours of overtime to be scheduled

22
 06-12-2023

Exercise 7 Solution

23