Session 3 - 18

Linear Programming Problem

Prof. Jigar M. Shah
Session 3 - 18

Linear Programming Problem

▪ Introduction ▪ Graphical Solution Method
▪ Meaning ▪ Introduction

▪ Requirements (General Structure) of an LP ▪ Definitions

Model
▪ Supporting Theorems
▪ Assumptions of an LP Model
▪ Extreme Point Solution Method
▪ Advantages & Limitations
▪ Special Cases
▪ Applications
▪ Sensitivity Analysis
▪ General Mathematical Model an LP Problem
▪ Concept
▪ Guidelines on LP Model Formulation
▪ Key Terms & Their Interpretations

Prof. Jigar M. Shah 2

Session 3 - 18

Linear Programming Problem

Introduction

▪ Meaning
▪ Formulation - process of converting the verbal description and numerical data into mathematical
expressions, which represents the relationship among relevant decision variables (or factors), objective
and restrictions (constraints) on the use of scarce resources (such as labor, material, machine, time,
warehouse space, capital, energy, etc.) to several competing activities (such as products, services, jobs,
new equipment, projects, etc.) on the basis of a given criterion of optimality

▪ Scarce Resources - resources that are not available in infinite quantity during the planning period

▪ Criterion of optimality is generally either performance, return on investment, profit, cost, utility, time,
distance, etc.

Prof. Jigar M. Shah 3

Session 3 - 18

Linear Programming Problem

Introduction

▪ Meaning
▪ Linear Programming (LP) - a mathematical technique useful for allocation of scarce resources, to several
competing activities on the basis of a given criterion of optimality

▪ Linear - linear relationship among variables in a model, e.g., a1x1 + a2x2 + … + anxn (higher powers of
variables like x13, x23/2, etc. or their products like x1x2, etc. do not appear in the expressions for objective
function as well as the constraints)

▪ Programming - mathematical modelling and solving of a problem that involves the use of limited
resources, by choosing a particular course of action (or strategy) among the given courses of action (or
strategies) in order to achieve the desired objective

Prof. Jigar M. Shah 4

Session 3 - 18

Linear Programming Problem

Introduction

▪ Requirements (General Structure) of an LP Model

Decision (Controllable) Variables
• A set of quantities, representing the amounts of resources to use or the levels of some activities, that need to be
determined in order to solve the problem
• Usually represented as x1, x2, … xn

Objective Function
• Expressed as a linear function of the decision variables to optimize (maximize or minimize) the criterion of optimality
(measure-of-performance) such as cost, profit, revenue, distance, etc.
• Optimize (maximize or minimize) Z = c1x1 + c2x2 + … + cnxn
where Z is the measure-of-performance variable which is a linear function of the decision variables x1, x2, … xn
c1, c2, … cn are parameters that represent the contribution of a unit of the respective variable x1, x2, … xn to the
measure-of-performance Z

Prof. Jigar M. Shah 5

Session 3 - 18

Linear Programming Problem

Introduction

▪ Requirements (General Structure) of an LP Model

Constraints
• Restrictions on the use of resources that limit the degree to which an objective can be achieved
• Expressed as linear equalities or inequalities in terms of decision variables

Alternatives
• The different courses of action or strategy from which one must be chosen in order to achieve the desired objective
considering the given constraints
• Optimize (maximize or minimize) Z = c1x1 + c2x2 + … + cnxn

Non-Negativity
• The decision variables should be interrelated and non-negative which shows that linear programming deals with real-life
situations for which negative quantities are generally illogical

Prof. Jigar M. Shah 6

Session 3 - 18

Linear Programming Problem

Introduction

▪ Assumptions of an LP Model
• There exists proportionality between the constraints & the objective function i.e., the amount of each
resource used (or supplied) and its contribution to the profit (or cost) in objective function is
Linearity proportional to the value of each decision variable
(Proportionality) • E.g., if a product yields a profit of ₹10, the profit earned from 12 such products will be 10 × 12 = ₹120
• E.g., if a product requires processing time of 5 hours, then 10 such products will require processing
time of 5 × 10 = 50 hours
• The value of the objective function & the total amount of each resource used (or supplied) is equal to
the sum of the respective individual contribution (profit or cost) of the decision variables.
• E.g., the total profit earned from the sale of two products A and B is equal to the sum of the profits
Additivity
earned separately from A and B.
• E.g., the amount of a resource consumed for producing A and B is equal to the total sum of resources
used for A and B individually.

Prof. Jigar M. Shah 7

Session 3 - 18

Linear Programming Problem

Introduction

▪ Assumptions of an LP Model
• All parameters of the LP model such as availability of resources, profit (or cost) contribution per unit
Certainty of decision variable and consumption of resources per unit of decision variable are known and
constant i.e., the LP problem is deterministic in nature
• Decision variables are continuous & can take any non-negative values that satisfy the constraints
• If any of the variable can assume only integer values or are limited to discrete number of values, LP
Continuity model is no longer applicable. (However, such problems are frequently solved by LP techniques and
(Divisibility) the values are then rounded off to the nearest integers to satisfy the constraints. Such approximation
is valid only if the variables have large optima values, and it must be ascertained whether the solution
represented by rounded values is a feasible solution and is the best integer solution

• A finite (limited) no. of choices (alternatives) are available to the decision-maker and that the decision
Finite Choices
variables are interrelated & non-negative

Prof. Jigar M. Shah 8

Session 3 - 18

Linear Programming Problem

Introduction

▪ Advantages & Limitations

Advantages Limitations
• Helps decision-makers use • Assumes linear relationships among decision variables, which in real-life
resources more effectively problems, may not be linearly related in the objective function or in the
• Improves the quality of decisions as constraints or in both
decision-making approach • Approximations required to reduce large problems having many limitations &
becomes more objective and less constraints may yield final results that may be far different from the exact ones
subjective • No guarantee that the solution will provide integer values of decision variables
• Helps arrive at optimal solution of a • Does not consider the effect of time and uncertainty
decision problem considering the • Assumes parameters in the model to be constant whereas in real-life situations,
constraints on the use of resources these are frequently neither known nor constant
• Highlights the bottlenecks in the • Deals with only single objective, whereas in real-life situations a decision
processes problem may have conflicting & multiple objectives

Prof. Jigar M. Shah 9

Session 3 - 18

Linear Programming Problem

Introduction

▪ Applications
• Farm Economics - inter-regional competition, optimum allocation of crop production, efficient
production patterns under regional land resources & national demand constraints
Agriculture
• Farm Management - allocation of limited resources such as acreage, labor, water, working capital, etc.
to maximize the net revenue
• Selection of air weapons systems against enemies
• Ensuring minimum use of aviation gasoline
Military
• Updating supply-chain to maximize the total tonnage of bombs dropped on a set of targets
• Community defense against disaster at the lowest possible cost
• Portfolio Selection - selection of specific investment activity among several other activities i.e., finding
Financial allocation that maximizes the total expected return or minimizes the risk under certain limitations
Management • Profit Planning - maximizing the profit from investment in plant, cash in hand & inventory

Prof. Jigar M. Shah 10

Session 3 - 18

Linear Programming Problem

Introduction

▪ Applications
• Product Mix - determining quantities of different products to be produced, considering their per unit
profit (or cost) contribution & resource consumption, with the objective of maximizing the total profit
• Production Planning - determining the minimum cost production plan over the planning period, for
an item with a fluctuating demand, while considering the initial number of units in inventory,
production capacity, constraints on production, manpower and all relevant cost factors, with the
Production objective of minimizing the total operation costs
Management • Assemble-line Balancing - determining task allocation to workstations considering the task times &
sequences, with the objective of minimizing the total elapsed time to balance the assembly-line
• Blending Problems - determining minimum cost blend for a product that can be made from a variety
of available materials, subject to the availability of the materials & the product constituent constraints
• Trim Loss - determining the combination of requirements / orders to be produced from standard
materials to minimize the trim losses when an item is made to standard sizes

Prof. Jigar M. Shah 11

Session 3 - 18

Linear Programming Problem

Introduction

▪ Applications
• Media Selection - determining the advertising media mix, subject to constraints of budget, specified
exposure rates to different market segments, no. of advertisements in various media, with the
objective of maximizing the effective exposure
Marketing • Traveling Salesman Problem - determining the shortest route for a salesman from a given city to each
Management of the specified cities and then returning to the original point of departure, without visiting any city
twice during the tour
• Physical Distribution - determining the most economic & efficient locations of manufacturing plants
and distribution centers for physical distribution
• Staffing Problem - allocating optimum manpower to a particular job with the objective of minimizing
Personnel the total overtime cost or total manpower
Management • Equitable Salaries - determining equitable salaries and sales incentives
• Job Evaluation & Selection - selecting suitable person for a specified job and evaluating the job

Prof. Jigar M. Shah 12

Session 3 - 18

Linear Programming Problem

Introduction

▪ General Mathematical Model an LP Problem

General Mathematical Model for an LP Problem with n Decision Variables & m Constraints
Regular Form Compact Form
Optimize (Max. or Min.) Z = c1x1 + c2x2 + ...+ cnxn Optimize (Max. or Min.) Z = σnj=1 cjxj
… Objective Function
Subject to the Constraints a11x1 + a12x2 + ...+ a1nxn (≤, =, ≥) b1 Subject to the Constraints σnj=1 aijxj (≤, =, ≥) bi ; i = 1, 2, …, m
a21x1 + a22x2 + ...+ a2nxn (≤, =, ≥) b2 … Constraints
: : : : : : and xj ≥ 0 ; j = 1, 2, …, n
am1x1 + am2x2 + ...+ amnxn (≤, =, ≥) bm … Non-negativity Conditions
and x1, x2, ... xn ≥ 0

Prof. Jigar M. Shah 13

Session 3 - 18

Linear Programming Problem

Introduction

▪ General Mathematical Model an LP Problem

General Mathematical Model for an LP Problem with n Decision Variables & m Constraints
where
cj s are coefficients representing the per unit profit (or cost) of the respective decision variables
these coefficients
xj s
can be positive,
aij s are the technological coefficients (or input-output coefficients) representing the amount of
negative or zero
respective resources i s consumed per unit of respective variables (activities) xj s
bi represents the total availability of the ith resource bi ≥ 0 for all i
(≤, =, ≥) means each constraint may take only one of the three possible forms:
i. Less than or equal to (≤) ii. Equal to (=) iii. Greater than or equal to (≥)

Prof. Jigar M. Shah 14

Session 3 - 18

Linear Programming Problem

Introduction

▪ Guidelines on LP Model Formulation

1. Identify the decision variables
a. Express constraint in words & identify the its form (≤, =, ≥)
b. Express verbally the objective function
c. Verbally identify the decision variables with the help of steps a. & b. (What decisions must be made for optimizing?)

2. Identify the problem data

• Identify the problem data in terms of constants, and parameters associated with decision variables (the decision-maker
can control values of the variables but cannot control values in the data set)

Prof. Jigar M. Shah 15

Session 3 - 18

Linear Programming Problem

Introduction

▪ Guidelines on LP Model Formulation

3. Formulate the constraints
• Convert the verbal expression of the constraints in terms of resource requirement and availability of each resource, and
express each of them as linear equality or inequality, in terms of the decision variables defined in Step 1.
• Wrong formulation can either lead to a solution that is not feasible or to the exclusion of a solution that is actually
feasible and possibly optimal

4. Formulate the objective function

• Identify whether the objective function is to be maximized or minimized and then express it in the form of linear
mathematical expression in terms of decision variables along with profit (cost) contributions associated with them

Prof. Jigar M. Shah 16

Session 3 - 18

Linear Programming Problem

Introduction

Q. A manufacturing company produces three types of products: A, B and C. The production

department produces, each day, components sufficient to make 50 units of A, 25 units of B
and 30 units of C. The management is confronted with the problem of optimizing the daily
production of the products in the assembly department, where only 100 man-hours are
available daily for assembling the products. The following additional information is available.
The company has a daily order commitment for 20 units of products A and a total of 15 units
of products B and C. Formulate this problem as an LP model so as to maximize the total profit.
Type of Product Profit Contribution per Unit of Production (₹) Assembly Time per Product (hours)
A 12 0.8
B 20 1.7
C 45 1.5

Prof. Jigar M. Shah 17

Session 3 - 18

Linear Programming Problem

Introduction

A. Resources / Constraints Product Total

A B C Availability
Problem
Production Capacity (units) 50 25 30
Data
Man-hours per Unit 0.8 1.7 2.5 100
Summary
Order Commitment (units) 20 15 (for both B & C together)
Profit Contribution (₹ per unit) 12 20 45

Decision Variables Let x1, x2 & x3 be the no. of units of products A, B & C, respectively, to be produced
Objective Function Maximize (total profit) Z = 12x1 + 20x2 + 45x3
Constraints Subject to constraints 0.8x1 + 1.7x2 + 2.5x3 ≤ 100 … Labor constraints
x1 ≤ 50 ; x2 ≤ 25 ; x3 ≤ 30 … Material constraints
x1 ≥ 20 ; x2 + x3 ≥ 15 … Order commitment constraints
and x1, x2, x3 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 18

Session 3 - 18

Linear Programming Problem

Introduction

Q. A company has two plants, each of which produces and supplies two products: A and B. The
plants can each work up to 16 hours a day. In plant 1, it takes three hours to prepare and pack
1,000 gallons of A and one hour to prepare and pack one quintal of B. In plant 2, it takes two
hours to prepare and pack 1,000 gallons of A and 1.5 hours to prepare and pack a quintal of B.
In plant 1, it costs ₹15,000 to prepare and pack 1,000 gallons of A and ₹28,000 to prepare and
pack a quintal of B, whereas in plant 2 these costs are ₹18,000 and ₹26,000, respectively. The
company is obliged to produce daily at least 10 thousand gallons of A and 8 quintals of B.
Formulate this problem as an LP model to find out as to how the company should organize its
production so that the required amounts of the two products be obtained at the minimum
cost.

Prof. Jigar M. Shah 19

Session 3 - 18

Linear Programming Problem

Introduction

A. Resources / Constraints Product Total

A B Availability
Problem
Plant 1 Plant 2 Plant 1 Plant 2 Plant 1 -
Data 16 hours
Preparation Time (hours/1,000 gallons & hours/quintal) 3.0 2.0 1.0 1.5
Summary
Production Cost (₹ per 1,000 gallons & ₹ per quintal) 15,000 18,000 28,000 26,000 Plant 2 -
Min. Daily Production (1,000 gallons & quintal) 10 8 16 hours

Decision Variables Let x1 & x2 be the quantities of product A, in 1,000 gallons, to be produced in plants 1 & 2, respectively
Let x3 & x4 be the quantities of product B, in quintals, to be produced in plants 1 & 2, respectively
Objective Function Minimize (total cost) Z = 15,000x1 + 18,000x2 + 28,000x3 + 26,000x4
Constraints Subject to constraints 3x1 + x3 ≤ 16 ; 2x2 + 1.5x4 ≤ 16 … Preparation Time constraints
x1 + x2 ≥ 10 ; x3 + x4 ≥ 8 … Min. Daily Production constraints
and x1, x2, x3, x4 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 20

Session 3 - 18

Linear Programming Problem

Introduction

Q. An electronic company producing two components C1 & C2 incurs costs of ₹5 in wages & ₹5 in
material costs for each C1, & ₹25 in wages & ₹15 in material for that of C2. It sells them on one-
period credit terms, but its labor & material expenses must be paid in cash. The selling price of
C1 is ₹30 per unit & that of C2 is ₹70 per unit. Because of the company’s strong monopoly, the
company can sell, at the prevailing prices, all its production, which is limited by two
considerations. First, at the beginning of period 1, the company has an initial balance of ₹4,000
(cash, bank credit & collections from past credit sales). Second, the company has, in each
period, 2,000 hours of machine time and 1,400 hours of assembly time. Production of each C1
requires 3 hours of machine time & 2 hours of assembly time, & production of each C2
requires 2 hours of machine time & 3 hours of assembly time. Formulate this problem as an LP
model to maximize the total profit to the company.

Prof. Jigar M. Shah 21

Session 3 - 18

Linear Programming Problem

Introduction

A. Resources / Constraints Component Total

C1 C2 Availability

Problem Labor Cost (₹ per unit) 5 25

4,000
Data Material Cost (₹ per unit) 5 15
Summary Selling Price (₹ per unit) 30 70
Machine Time (hours per unit) 3 2 2,000
Assembly Time (hours per unit) 2 3 1,400

Decision Variables Let x1 & x2 be the quantities of components C1 & C2, respectively, to be produced by the company
Objective Function Maximize (total profit) Z = (30 - 5 - 5)x1 + (70 - 25 - 15)x2 = 20x1 + 30x2
Constraints Subject to constraints (5 + 5)x1 + (25 + 15)x2 ≤ 4000 … Budget constraints
3x1 + 2x2 ≤ 2,000 ; 2x1 + 3x2 ≤ 1,400 … Machine & Assembly Times constraints
and x1, x2 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 22

Session 3 - 18

Linear Programming Problem

Introduction

Q. An electronic company produces three types of parts for automatic washing machines. It
purchases casting of the parts from a local foundry and then finishes the part on drilling,
shaping and polishing machines. The selling prices of parts A, B and C are ₹8, ₹10 and ₹14
respectively. All parts made can be sold. Castings for parts A, B and C, respectively cost ₹5, ₹6
and ₹10. The shop possesses only one of each type of casting machine. Costs per hour to run
each of the three machines are ₹20 for drilling, ₹30 for shaping and ₹30 for polishing. The
capacities (parts per hour) for each part on each machine are shown in the table below. The
management of the shop wants to know how many parts of each type it should produce per
hour in order to maximize profit for an hour’s run. Formulate this problem as an LP model so
as to maximize total profit to the company.

Prof. Jigar M. Shah 23

Session 3 - 18

Linear Programming Problem

Introduction

Q. Machine Capacity per Hour

Part A Part B Part C
Drilling 25 40 25
Shaping 25 20 20
Polishing 40 30 40

Prof. Jigar M. Shah 24

Session 3 - 18

Linear Programming Problem

Introduction

A. Resources / Constraints Part Total

A B C Availability
Selling Price (₹ per unit) 8 10 14
Material Cost (₹ per unit) 5 6 10
Problem Drilling Cost (₹ per unit) 20 ÷ 25 = 0.80 20 ÷ 40 = 0.50 20 ÷ 25 = 0.80
Data Shaping Cost (₹ per unit) 30 ÷ 25 = 1.20 30 ÷ 20 = 1.50 30 ÷ 20 = 1.50
Summary Polishing Cost (₹ per unit) 30 ÷ 40 = 0.75 30 ÷ 30 = 1.00 30 ÷ 40 = 0.75
Profit (₹ per unit) 0.25 1.00 0.95
Drilling Time (hours per unit) 1 ÷ 25 1 ÷ 40 1 ÷ 25
Shaping Time (hours per unit) 1 ÷ 25 1 ÷ 20 1 ÷ 20
Polishing Time (hours per unit) 1 ÷ 40 1 ÷ 30 1 ÷ 40

Prof. Jigar M. Shah 25

Session 3 - 18

Linear Programming Problem

Introduction

A. Decision Variables Let x1, x2 & x3 be the quantities of parts A, B & C, respectively, to be produced per hour by the company
Objective Function Maximize (total profit) Z = 0.25x1 + 1.00x2 + 0.95x3
Constraints Subject to constraints x1 x2 x3
+ + ≤ 1 … Drilling Machine constraints
25 40 25
x1 x2 x3
+ + ≤ 1 … Shaping Machine constraints
25 20 20
x1 x2 x3
+ + ≤ 1 … Polishing Machine constraints
40 30 40
and x1, x2, x3 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 26

Session 3 - 18

Linear Programming Problem

Introduction

Q. A company produces two types of sauces: A and B. Both these sauces are made by blending
two ingredients - X and Y. A certain level of flexibility is permitted in the formulae of these
products. Indeed, the restrictions are that
i. B must contain no more than 75 per cent of X, and

ii. A must contain no less than 25 per cent of X, and no less than 50 per cent of Y

Up to 400 kg. of X and 300 kg. of Y could be purchased. The company can sell as much of
these sauces as it produces at a price of ₹18 for A and ₹17 for B. The X and Y ingredients cost
₹1.60 and ₹2.05 per kg., respectively. The company wishes to maximize its net revenue from
the sale of these sauces. Formulate this problem as an LP model.

Prof. Jigar M. Shah 27

Session 3 - 18

Linear Programming Problem

Introduction

A. Decision Variables Let a & b be the quantities, in kg., of sauces A & B, respectively, to be produced by the company
Let xa & xb be the quantities, in kg., of ingredient X to be used in sauces A & B, respectively
Let ya & yb be the quantities, in kg., of ingredient Y to be used in sauces A & B, respectively
Objective Function Maximize (total profit) Z = (18a + 17b) – 1.60(xa + xb) – 2.05(ya + yb)
Constraints Subject to constraints xb
≤ 0.75 … Blending constraints of ingredient X for sauce B
b
xa
≥ 0.25 … Blending constraints of ingredient X for sauce A
a
ya
≥ 0.50 … Blending constraints of ingredient Y for sauce A
a
xa + xb ≤ 400 ; ya + yb ≤ 300 … Purchase constraints of ingredients X & Y
xa + ya - a = 0; xb + yb – b = 0 … Basic Composition constraints for sauces A & B
and a, b, xa, xb, ya, yb ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 28

Session 3 - 18

Linear Programming Problem

Introduction

Q. An advertising company wishes to plan an advertising campaign for three different media:
television, radio & a magazine to reach as many potential customers as possible. The following
are the results of a market study:
Television (₹) Radio (₹) Magazine (₹)
Prime Day Prime Time
Cost of an advertising unit 40,000 75,000 30,000 15,000
No. of potential customers reached per unit 4,00,000 9,00,000 5,00,000 2,00,000
No. of women customers reached per unit 3,00,000 4,00,000 2,00,000 1,00,000

The company does not want to spend more than ₹8,00,000 on advertising.

Prof. Jigar M. Shah 29

Session 3 - 18

Linear Programming Problem

Introduction

Q. It is further required that:

i. at least 2 million exposures take place amongst women,

ii. the cost of advertising on television be limited to ₹5,00,000,

iii. at least three advertising units be bought on prime day and two units during prime time; and

iv. the number of advertising units on the radio and the magazine should each be between 5 and 10.

Formulate this problem as an LP model to maximize potential customer reach.

Prof. Jigar M. Shah 30

Session 3 - 18

Linear Programming Problem

Introduction

A. Decision Variables Let x1, x2, x3 & x4 be the no. of advertising units on television (prime day), television (prime time), radio &
magazine, respectively, to be bought by the company
Objective Function Maximize (potential reach) Z = 4,00,000x1 + 9,00,000x2 + 5,00,000x3 + 2,00,000x4
Constraints Subject to constraints 40,000x1 + 75,000x2 +
≤ 8,00,000 … Total Budget constraints
30,000x3 + 15,000x4
3,00,000x1 + 4,00,000x2 +
≥ 20,00,000 … Women Exposure constraints
2,00,000x3 + 1,00,000x4
40,000x1 + 75,000x2 ≤ 5,00,000 … Television Budget constraints
x1 ≥ 3 ; x2 ≥ 2 ; 5 ≤ x3 ≤ 10 ; 5 ≤ x4 ≤ 10 … Advertising Units constraints
and x1, x2, x3, x4 ≥0 … Non-negativity condition

Prof. Jigar M. Shah 31

Session 3 - 18

Linear Programming Problem

Introduction

Q. A businessman is opening a new restaurant and has budgeted ₹8,00,000 for advertisement, for
the coming month. He is considering four types of advertising:
i. 30 second television commercials

ii. 30 second radio commercials

iii. Half-page advertisement in a newspaper

iv. Full-page advertisement in a weekly magazine which will appear four times during the coming month.

The owner wishes to reach families (a) with income over ₹50,000 and (b) with income under
₹50,000. The amount of exposure of each media to families of type (a) and (b) and the cost of
each media is shown below:

Prof. Jigar M. Shah 32

Session 3 - 18

Linear Programming Problem

Introduction

Q. Media Cost of Advertisement (₹) Exposure to Families with Annual Income

Over ₹50,000 Under ₹50,000
Television 40,000 2,00,000 3,00,000
Radio 20,000 5,00,000 7,00,000
Newspaper 15,000 3,00,000 1,50,000
Magazine 5,000 1,00,000 1,00,000

To have a balanced campaign, the owner has determined the following four restrictions:
i. there should be no more than four television advertisements

ii. there should be no more than four advertisements in the magazine

Prof. Jigar M. Shah 33

Session 3 - 18

Linear Programming Problem

Introduction

Q.
iii. there should not be more than 60 per cent of all advertisements in newspaper and magazine put
together

iv. there must be at least 45,00,000 exposures to families with annual income of over ₹50,000.

Formulate this problem as an LP model to determine the number of each type of

advertisement to be given so as to maximize the total number of exposures.

Prof. Jigar M. Shah 34

Session 3 - 18

Linear Programming Problem

Introduction

A. Decision Variables Let x1, x2, x3 & x4 be the no. of advertisements on television, radio, newspaper & magazine, respectively, to be
given by the company
Objective Function Maximize (total exposures) Z = 5,00,000x1 + 12,00,000x2 + 4,50,000x3 + 2,00,000x4
Constraints Subject to constraints 40,000x1 + 20,000x2 +
≤ 8,00,000 … Budget constraints
15,000x3 + 5,000x4
x1 ≤4 … Television Advertising constraints
x4 ≤4 … Magazine Advertising constraints
(x3 + x4)
≤ 0.6 … Newspaper & Magazine
(x1 + x2 + x3 + x4)
Advertising Constraints
-0.6x1 – 0.6x2 + 0.4x3 +0.4x4 ≤0

2,00,000x1 + 5,00,000x2 + ≥ 45,00,000 … Exposure constraints

3,00,000x3 + 1,00,000x4
and x1, x2, x3, x4 ≥0 … Non-negativity condition

Prof. Jigar M. Shah 35

Session 3 - 18

Linear Programming Problem

Introduction

Q. A leading CA is attempting to determine the ‘best’ investment portfolio and is considering six
alternative investment proposals. The following table indicates point estimates for the price
per share, the annual growth rate in the price per share, the annual dividend per share and a
measure of the risk associated with each investment.
Shares under Consideration A B C D E F
Current price per share (₹) 80.00 100.00 160.00 120.00 150.00 200.00
Projected annual growth rate 0.08 0.07 0.10 0.12 0.09 0.15
Projected annual dividend per share (₹) 4.00 4.50 7.50 5.50 5.75 0.00
Projected risk return 0.05 0.03 0.10 0.20 0.06 0.08

The total amount available for investment is ₹25 lakh and following conditions must be met:

Prof. Jigar M. Shah 36

Session 3 - 18

Linear Programming Problem

Introduction

Q.
i. The maximum rupee amount to be invested in alternative F is ₹2,50,000.

ii. No more than ₹5,00,000 should be invested in alternatives A and B combined.

iii. Total weighted risk should not be greater than 0.10, where
(Amount invested in alternative j) × (Risk of alternative j)
Total weighted risk =
(Total amount invested in all the alternatives)
iv. For the sake of diversity, at least 100 shares of each stock should be purchased.

v. At least 10 per cent of the total investment should be in alternatives A and B combined.

vi. Dividends for the year should be at least ₹10,000.

Prof. Jigar M. Shah 37

Session 3 - 18

Linear Programming Problem

Introduction

Q. Rupee return per share of stock is defined as the price per share one year hence, less current
price per share plus dividend per share. If the objective is to maximize total rupee return,
formulate this problem as an LP model for determining the optimal number of shares to be
purchased in each of the shares under consideration. You may assume that the time horizon
for the investment is one year.

Prof. Jigar M. Shah 38

Session 3 - 18

Linear Programming Problem

Introduction

A. Decision Variables Let x1, x2, x3, x4, x5 & x6 be the no. of shares of A, B, C, D, E & F, respectively, to be purchased by the CA

Objective Function Maximize (net returns) Z = [(0.08 × 80) + 4.00]x1 + [(0.07 × 100) + 4.50]x2 + [(0.10 × 160) + 7.50]x3 +
[(0.12 × 120) + 5.50]x4 + [(0.09 × 150) + 5.75]x5 + [(0.15 × 200) + 0.00]x6
= 10.40x1 + 11.50x2 + 23.50x3 + 19.90x4 + 19.25x5 + 30.00x6
Constraints Subject to constraints 80x1 + 100x2 + 160x3 + 120x4 +
≤ 25,00,000 … Total Investment constraints
150x5 + 200x6
200x6 ≤ 2,50,000 … Share F Investment constraints
… Shares A, B Maximum Investment
80x1 + 100x2 ≤ 5,00,000
constraints
(0.05 × 80x1) + (0.03 × 100x2) +
(0.10 × 160x3) + (0.20 × 120x4) +
(0.06 × 150x5) + (0.08 × 200x6) ≤ 0.10 … Total Weighted Risk constraints
(80x1 + 100x2 + 160x3 + 120x4 +
150x5 + 200x6)

Prof. Jigar M. Shah 39

Session 3 - 18

Linear Programming Problem

Introduction

A. 4x1 + 3x2 + 16x3 + 24x4 + 9x5 +

16x6 - 8x1 - 10x2 - 16x3 - 12x4 - 15x5 ≤0
- 20x6 … Total Weighted Risk constraints
- 4x1 - 7x2 + 0x3 + 12x4 - 6x5 -
4x6 ≤0

x1, x2, x3, x4, x5, x6 ≥ 100 … Diversity constraints

(80x1 + 100x2)
(80x1 + 100x2 + 160x3 + 120x4 + ≥ 0.10
150x5 + 200x6)
… Shares A, B Minimum Investment
80x1 + 100x2 - 8x1 - 10x2 - 16x3 - constraints
≥ 0.00
12x4 - 15x5 - 20x6
72x1 + 90x2 - 16x3 - 12x4 - 15x5 -
≥ 0.00
20x6

Prof. Jigar M. Shah 40

Session 3 - 18

Linear Programming Problem

Introduction

A. 4.00x1 + 4.50x2 + 7.50x3 + 5.50x4

≥ 10,000 … Minimum Dividend constraints
+ 5.75x5 + 0.00x6
and x1, x2, x3, x4, x5, x6 ≥0 … Non-negativity condition

Prof. Jigar M. Shah 41

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Introduction
▪ An optimal as well as a feasible solution to an LP problem is obtained by choosing one set of values from
several possible values of decision variables x1, x2, ..., xn, that satisfies the given constraints simultaneously
and also provides an optimal (maximum or minimum) value of the given objective function

▪ Graphical Solution Method - the technique used to identify the optimal solution for LP problems with
only two decision variables wherein the entire set of feasible solutions can be displayed graphically by
plotting linear constraints on a graph paper in order to locate the optimal solution

▪ For most real-world problems having more than two variables, the graphical method provides pictorial
representation of the solution process & understanding of the basic concepts used in solving LP
problems algebraically

Prof. Jigar M. Shah 42

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Definitions
Solution A set of values of decision variables xj ( j = 1, 2, ..., n) that satisfy the constraints of an LP problem

A set of values of decision variables xj ( j = 1, 2, ..., n) that satisfy all the constraints and non-
Feasible Solution
negativity conditions of an LP problem simultaneously

A solution obtained for a set of m simultaneous equations in n variables (n > m) by setting (n - m)

variables equal to zero and solving for remaining m equations in m variables
Basic Solution
Basic Variables The m variables for which the simultaneous equations are solved

Non-Basic Variables The (n – m) variables whose value did not appear in basic solution

Basic Feasible A feasible solution which is also the basic solution i.e., a basic solution with non-negative values for
Solution all basic variables

Prof. Jigar M. Shah 43

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Definitions
Degenerate Basic Feasible Solution A basic feasible solution with value of at least one basic variable as zero

Non-Degenerate Basic Feasible Solution A basic feasible solution with non-zero & positive values of all basic variables

A basic feasible solution that optimizes (maximizes or minimizes) the objective

Optimum Basic Feasible Solution
function value
A solution that can increase or decrease infinitely the value of objective
Unbounded Solution
function

Prof. Jigar M. Shah 44

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Definitions
Just as a linear equation in x1, x2 such as a1x1 + a2x2 = b represents a line in two-dimensions, so also a
linear equation in x1, x2, x3 such as a1x1 + a2x2 + a3x3= b or ax = b where a = (a1, a2, a3) & x = (x1, x2, x3)
Set of Points
represents a plane. Both are considered a set of points. A line represents a set of points that satisfy the
equation a1x1 + a2x2 = b, a plane represents a set of points that satisfy ax = b
A set S (of points) such that for any two points in the set, the line joining those two points lies entirely in
set

Convex Sets

Convex Sets Non-Convex Sets

Prof. Jigar M. Shah 45

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Supporting Theorems
The graphical method makes use of the following theorems of linear programming:
• The collection of all feasible solutions to an LP problem constitutes a convex set whose extreme points correspond to
the basic feasible solutions.
• There are a finite number of basic feasible solutions within the feasible solution space.
• If the convex set of the feasible solutions of the system of simultaneous equations: ax = b, x ≥ 0, is a convex polyhedron,
then at least one of the extreme points gives an optimal solution.
• If the optimal solution occurs at more than one extreme point, the value of the objective function will be the same for all
convex combinations of these extreme points.
Remarks • A convex set is a polygon i.e., if any two points of a polygon are selected arbitrarily, a straight line segment joining these two
points lies completely within the polygon.
• Each corner (extreme or vertex) point of the feasible region (space or area) falls at the intersection of two constraint equalities.
• The extreme points of the convex set provide the basic feasible solution to the LP problem.

Prof. Jigar M. Shah 46

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

1. Develop an LP Model
• State the problem in the mathematical LP model

2. Plot constraints on graph paper & decide the feasible region

a. Replace the inequality sign in each constraint by an equality sign
b. Draw these straight lines on graph paper & decide each time the area of feasible solutions according to the inequality
sign of the constraint. Shade the common portion of the graph satisfying all constraints simultaneously drawn so far.
c. Final shaded area is called feasible region (or solution space, the overlapping area of constraints that satisfies all
constraints) of the given LP problem. Any point inside this region is called feasible solution and this provides values of
the decision variables x1 & x2 that satisfy all the constraints.

Prof. Jigar M. Shah 47

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

3. Examine the extreme points of the feasible solution space to find an optimal solution
a. Determine the coordinates of each extreme point of the feasible solution space.
b. Compute and compare the value of the objective function at each extreme point.
c. Identify the extreme point that gives optimal (max. or min.) value of the objective function.

Q. Use the graphical method to solve the following LP problem

Maximize Z = 15x1 + 10x2
Subject to constraints 4x1 + 6x2 ≤ 360 3x1 + 0x2 ≤ 180 0x1 + 5x2 ≤ 200
and x1, x2 ≥ 0

Prof. Jigar M. Shah 48

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. 1. Develop an LP Model
Maximize Z = 15x1 + 10x2
Subject to constraints 4x1 + 6x2 ≤ 360 3x1 + 0x2 ≤ 180 0x1 + 5x2 ≤ 200
and x1, x2, x3 ≥ 0

2. Plot constraints on graph paper and decide the feasible region

• Treat x1 as the horizontal axis and x2 as the vertical axis
a. Replace the inequality sign in each constraint by an equality sign
4x1 + 6x2 = 360 ; 3x1 + 0x2 = 180 ; 0x1 + 5x2 = 200

Prof. Jigar M. Shah 49

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. 2. Plot constraints on graph paper and decide the feasible region

b. Draw these straight lines on graph paper & decide each time the
area of feasible solutions according to the inequality sign of the
constraint. Shade the common portion of the graph satisfying all
constraints simultaneously drawn so far.

4x1 + 6x2 = 360

Find any two points that satisfy the equation and then draw a
straight line through them
Decide the area of feasible solution for this line considering the
inequality sign in the constraint

Prof. Jigar M. Shah 50

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. 2. Plot constraints on graph paper and decide the feasible region

c. Final shaded area is called feasible region (or solution space, the
overlapping area of constraints that satisfies all constraints) of the
given LP problem. Any point inside this region is called feasible
solution and this provides values of the decision variables x1 & x2
that satisfy all the constraints.
4x1 + 6x2 = 360 ; 3x1 + 0x2 = 180 ; 0x1 + 5x2 = 200
Shade the common portion of the graph that satisfies all the
constraints simultaneously
The area, OABCD, bounded all constraint lines including all the
boundary points is called the feasible region (or solution space)

Prof. Jigar M. Shah 51

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. 3. Examine the extreme points of the feasible solution space to find an optimal solution
a. Determine the coordinates of each extreme point of the feasible
solution space.

The coordinates of extreme points of the feasible region are:

O = (0, 0)
A = (60, 0)
B = (60, 20)
C = (30, 40)
D = (0, 40)

Prof. Jigar M. Shah 52

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. 3. Examine the extreme points of the feasible solution space to find an optimal solution
b. Compute and compare the value of the objective function at each
extreme point.

Extreme Point Coordinates Objective Function Value Z = 15x1 + 10x2

O (0, 0) 15(0) + 10(0) = 0
A (60, 0) 15(60) + 10(0) = 900
B (60, 20) 15(60) + 10(20) = 1,100
C (30, 40) 15(30) + 10(40) = 850
D (0, 40) 15(0) + 10(40) = 400

Prof. Jigar M. Shah 53

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. 3. Examine the extreme points of the feasible solution space to find an optimal solution
c. Identify the extreme point that gives optimal (max. or min.) value of the
objective function.

Since objective function Z is to be maximized, from the comparison of

the values in the table above, the maximum value of the objective
function Z is 1,100 which is achieved at extreme point B (60, 20)

Hence, the Optimal Solution is:

x1 = 60, x2 = 20, and
Max. Z = 1,100

Prof. Jigar M. Shah 54

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Note: Determining which side of a constraint equation is in the feasible region
To determine which side of a constraint equation is in the feasible region, examine whether the origin (0, 0) satisfies the
constraints. If it does, then all points on and below the constraint equation towards the origin are feasible points. If it does
not, then all points on and above the constraint equation away from the origin are feasible points.

Q. Use the graphical method to solve the following LP problem

Maximize Z = 2x1 + x2
Subject to constraints x1 + 2x2 ≤ 10 x1 + x2 ≤ 6 x1 - x2 ≤ 2 x1 - 2x2 ≤ 1
and x1, x2 ≥ 0

Prof. Jigar M. Shah 55

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Extreme Point Coordinates Objective Function Value
A. Z = 2x1 + x2
O (0, 0) 2(0) + 1(0) = 0
A (1, 0) 2(1) + 1(0) = 2
B (3, 1) 2(3) + 1(1) = 7
C (4, 2) 2(4) + 1(2) = 10
D (2, 4) 2(2) + 1(4) = 8
E (0, 5) 2(0) + 1(5) = 5
The optimal solution is: x1 = 4, x2 = 2, and
Max. Z = 10

Prof. Jigar M. Shah 56

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. Use the graphical method to solve the following LP problem:

Maximize Z = -x1 + 2x2
Subject to constraints x 1 - x 2 ≤ -1 -0.5x1 + x2 ≤ 2
and x1, x2 ≥ 0

A. Extreme Point Coordinates Objective Function Value Z = -x1 + 2x2

A (0, 1) -1(0) + 2(1) = 2
B (0, 2) -1(0) + 2(2) = 4 Multiple Optimal
C (2, 3) -1(2) + 2(3) = 4 Solutions
The optimal solutions are: (x1 = 0, x2 = 2) & (x1 = 2, x2 = 3), and Max. Z = 4

Prof. Jigar M. Shah 57

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. The ABC Company has been a producer of picture tubes for television sets and certain printed
circuits for radios. The company has just expanded into full scale production and marketing of
AM and AM-FM radios. It has built a new plant that can operate 48 hours per week.
Production of an AM radio in the new plant will require 2 hours and production of an AM-FM
radio will require 3 hours. Each AM radio will contribute ₹40 to profits while an AM-FM radio
will contribute ₹80 to profits. The marketing department, after extensive research has
determined that a maximum of 15 AM radios and 10 AM-FM radios can be sold each week.
Formulate a linear programming model to determine the optimum production mix of AM and
FM radios that will maximize profits. Solve this problem using the graphical method.

Prof. Jigar M. Shah 58

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. Decision Variables Let x1 & x2 be the no. of AM & AM-FM radios, respectively, to be produced by the company each week

Objective Function Maximize (profits) Z = 40x1 + 80x2

Constraints Subject to constraints 2x1 + 3x2 ≤ 48 … Operating Time constraints
x1 ≤ 15 … AM Radio Sales constraints
x2 ≤ 10 … AM-FM Radio Sales constraints
and x1, x2 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 59

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A.
Extreme Point Coordinates Objective Function Value Z = 40x1 + 80x2
O (0, 0) 40(0) + 80(0) = 0
A (0, 10) 40(0) + 80(10) = 800
B (9, 10) 40(90) + 80(10) = 1,160
C (15, 6) 40(15) + 80(6) = 1,080
D (15,0) 40(15) + 80(0) = 600
The optimal solution is: (x1 = 9, x2 = 10), and Max. Z = 1,160
ABC company must produce 9 AM radios & 10 AM-FM radios every
week to yield the maximum profit of ₹1,160

Prof. Jigar M. Shah 60

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. Use the graphical method to solve the following LP problem:

Minimize Z = 3x1 + 2x2
Subject to constraints 5x1 + x2 ≥ 10 x1 + x2 ≥ 6 x1 + 4x2 ≥ 12
and x1, x2 ≥ 0

A. Extreme Point Coordinates Objective Function Value Z = 3x1 + 2x2

A (12, 0) 3(12) + 2(0) = 36
B (4, 2) 3(4) + 2(2) = 16
C (1, 5) 3(1) + 2(5) = 13
D (0, 10) 3(0) + 2(10) = 20 The optimal solution is: (x1 = 1, x2 = 5), and Min. Z = 13

Prof. Jigar M. Shah 61

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. Use the graphical method to solve the following LP problem:

Minimize Z = -x1 + 2x2
Subject to constraints -x1 + 3x2 ≤ 10 x1 + x2 ≤ 6 x1 - x2 ≤ 2
and x1, x2 ≥ 0
A. Extreme Point Coordinates Objective Function Value Z = 3x1 + 2x2
O (0, 0) -1(0) + 2(0) = 0
A (2, 0) -1(2) + 2(0) = -2
B (4, 2) -1(4) + 2(2) = 0
C (2, 4) -1(2) + 2(4) = 6
D (0, 3.3) -1(0) + 2(3.3) = 6.6 The optimal solution is: (x1 = 2, x2 = 0), and Min. Z = -2

Prof. Jigar M. Shah 62

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. G. J. Breweries Ltd. produces whisky, beer & brandy at two bottling plants, one at G & the
other at J. The no. of bottles produced per day are shown in the table. A market survey
indicates a demand of 20,000 bottles of whisky, 40,000 of beer & 44,000 of brandy that during
the month of July. The operating cost per day for plants at G & J are 600 & 400 monetary
units. For how many days each plant be run in July so as to minimize the production cost,
while still meeting the market demand? Formulate this problem as an LP problem & solve that
using graphical method.
Plant Whisky (A) Beer (B) Brandy (C)
Plant G 1,500 3,000 2,000
Plant J 1,500 1,000 5,000

Prof. Jigar M. Shah 63

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. Decision Variables Let x1, x2 & x3 be the no. of days the plants at G & J, respectively, be run by the company in the month of July

Objective Function Minimize (production cost) Z = 600x1 + 400x2

Constraints Subject to constraints 1,500x1 + 1,500x2 ≥ 20,000 … Whisky Demand constraints
3,000x1 + 1,000x2 ≥ 40,000 … Beer Demand constraints
2,000x1 + 5,000x2 ≥ 44,000 … Brandy Demand constraints
and x1, x2 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 64

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A.

Extreme Point Coordinates Objective Function Value Z = 600x1 + 400x2

O (22, 0) 600(22) + 400(0) = 13,200
A (12, 4) 600(12) + 400(4) = 8,800
B (0, 40) 600(0) + 400(40) = 16,000
The optimal solution is: (x1 = 12, x2 = 4), and Min. Z = 8,800
Plant G must be run for 12 days and plant J for 4 days in in July to yield the
minimum production cost of 8,800 monetary units while still meeting the
market demand in the month of July

Prof. Jigar M. Shah 65

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. A firm plans to purchase at least 200 quintals of scrap containing high quality metal X & low
quality metal Y. The scrap must contain at least 100 quintals of metal X & not more than 35
quintals of metal Y. The firm can purchase the scrap from two suppliers, A & B, in unlimited
quantities. The percentage of X & Y metals in terms of weight in the scrap supplied by A & B is
given below. The price of A’s scrap is ₹200 per quintal & that of B is ₹400 per quintal. The firm
wants to determine the quantities that it should buy from the two suppliers so that the total
cost is minimized.
Metals Supplier A Supplier B
X 25% 75%
Y 10% 20%

Prof. Jigar M. Shah 66

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. Decision Variables Let x1 & x2 be the quantities (in quintals) of scrap to be purchased from Supplier A & Supplier B, respectively

Objective Function Minimize (production cost) Z = 200x1 + 400x2

Constraints Subject to constraints x1 + x2 ≥ 200 … Min. Purchase constraints
0.25x1 + 0.75x2 ≥ 100
25x1 + 75x2 ≥ 10,000 … Metal X Requirement constraints
x1 + 3x2 ≥ 400
0.10x1 + 0.20x2 ≤ 35
… Metal Y Requirement constraints
x1 + 2x2 ≤ 350
and x1, x2 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 67

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. Extreme Coordinates Objective Function Value

Point Z = 200x1 + 400x2
A (100, 100) 200(100) + 400(100) = 60,000
B (250, 50) 200(250) + 400(50) = 70,000
C (50, 150) 200(50) + 400(150) = 70,000
The optimal solution is: (x1 = 100, x2 = 100), and Min. Z =
60,000
The company should purchase 100 quintals of scrap from
supplier A and 100 quintals of scrap from supplier B

Prof. Jigar M. Shah 68

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. Use the graphical method to solve the following LP problem:

Maximize Z = 7x1 + 3x2
Subject to constraints x1 + 2x2 ≥ 3 x1 + x2 ≤ 4 0 ≤ x1 ≤ 5/2 0 ≤ x2 ≤ 3/2
and x1, x2 ≥ 0

A. Extreme Point Coordinates Objective Function Value Z = 3x1 + 2x2

A (5/2, 1/4) 7(5/2) + 3(1/4) = 73/4 = 18.25
B (5/2, 3/2) 7(5/2) + 3(3/2) = 44/2 = 22
C (0, 3/2) 7(0) + 3(3/2) = 9/2 = 4.5
The optimal solution is: (x1 = 5/2, x2 = 3/2), and Min. Z = 22

Prof. Jigar M. Shah 69

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

Q. A manufacturer produces two different models - X and Y of the same product. Model X makes
a contribution of ₹50 per unit & model Y, ₹30 per unit, towards total profit. Raw materials r1 &
r2 are required for production. At least 18 kg of r1 & 12 kg of r2 must be used daily. Also, at
most 34 hours of labor are to be utilized. A quantity of 2 kg of r1 is needed for model X and 1
kg of r1 for model Y. For each of X and Y, 1 kg of r2 is required. It takes 3 hours to manufacture
model X & 2 hours to manufacture model Y. How many units of each model should be
produced in order to maximize the profit?

Prof. Jigar M. Shah 70

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A. Decision Variables Let x1 & x2 be the no. of units of model X & Y, respectively, to be produced by the manufacturer

Objective Function Maximize (profit) Z = 50x1 + 30x2

Constraints Subject to constraints 2x1 + x2 ≥ 18 … r1 Daily Min. Usage constraints
x1 + x2 ≥ 12 … r2 Daily Min. Usage constraints
3x1 + 2x2 ≤ 34 … Max. Labor Hours constraints
and x1, x2 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 71

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Extreme Point Solution Method

A.

Extreme Point Coordinates Objective Function Value Z = 200x1 + 400x2

A (6, 6) 50(6) + 30(6) = 480
B (2, 14) 50(2) + 30(14) = 520
C (10, 2) 50(10) + 30(2) = 560
The optimal solution is: (x1 = 10, x2 = 2), and Max. Z = 560
The company should produce 10 units of model X and 2 units of model Y
in order to yield the maximum profit of ₹560

Prof. Jigar M. Shah 72

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases
1. Alternative or Multiple Optimal Solutions 3. No Feasible Solution or Infeasible Solution
• When an LP problem has more than one solution • When no solution exists to an LP problem that satisfies all
yielding the same optimal objective function value. constraints & non-negativity conditions simultaneously

2. Unbounded Solution 4. Redundancy

• When an LP problem has values of the decision variables • When in an LP problem the elimination or removal of
that can increase to infinity thereby leading to an infinite one or more constraints does not change the feasible
value of the objective function region

Prof. Jigar M. Shah 73

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases
1. Alternative or Multiple Optimal Solutions
• When a given LP problem has more than one solution yielding the same optimal objective function value, each of such
optimal solutions is termed as alternative optimal solution
• Alternative optimal solutions are arrived only when slope of the objective function is same as the slope of a constraint
which falls on the boundary of the feasible region
• Two conditions that should be satisfied for an alternative optimal solution to exist:
i. Slope of objective function should be the same as that of the constraint forming the boundary of feasible solutions region, and
ii. Constraint should form a boundary on the feasible region in the direction of optimal movement of the objective function i.e., the
constraint should be an active (binding or tight) constraint
A constraint is said to be active (binding or tight), if at the point of optimality, the left-hand side of a constraint equals the right-hand
side. In other words, an equality constraint is always active, and inequality constraint may or may not be active. Geometrically, an active
constraint is one that passes through one of the extreme points of the feasible solution space.

Prof. Jigar M. Shah 74

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

Q. Use the graphical method to solve the following LP problem:

Maximize Z = 10x1 + 6x2
Subject to constraints 5x1 + 3x2 ≤ 30 x1 + 2x2 ≤ 18
and x1, x2 ≥ 0

A. Since objective function (iso-profit line) is parallel to first

constraint that also falls on boundary of feasible region,
as the iso-profit line moves away from origin for
maximization, it coincides with line BC of constraint
equation that lies on boundary of the feasible region.

Prof. Jigar M. Shah 75

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

A. The optimal solution of LP problem can be obtained at any point between B & C including extreme points B & C on
the same line. Several combinations of values of x1 & x2 give the same value of objective function. The value of
variables x1 & x2 obtained at extreme points B & C should only be considered to establish that the solution to an LP
problem will always lie at an extreme point of the feasible region.

Extreme Point Coordinates Objective Function Value Z = 3x1 + 2x2 The max. value of Z (60) occurs at two points B & C.
O (0, 0) 10(0) + 6(0) = 2 Every linear convex combination of these points will also
give the same maximum value of S. Thus, there is no
A (0, 9) 10(0) + 6(9) = 16 unique solution to the problem, i.e., the problem has
B (6/7, 60/7) 10(6/7) + 6(60/7) = 60 multiple optimal solutions & any point between B & C on
Multiple Optimal
the line BC can be taken as an optimal solution with
C (6, 0) 10(6) + 6(0) = 60 Solutions
maximum value of the objective function Z as 60.

Prof. Jigar M. Shah 76

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases
2. Unbounded Solution
• When an LP problem has values of the decision variables that can increase to infinity thereby leading to an infinite value
of the objective function without violating any of the constraints
• In an LP problem having an infinite solution, such solution is referred to as an unbounded solution
• It happens when value of certain decision variables and the value of the objective function (maximization case) are
permitted to increase infinitely, without violating the feasibility condition
• There is a difference between unbounded feasible region and unbounded solution to a LP problem
• It is possible that for a particular LP problem the feasible region may be unbounded but LP problem solution may not be
unbounded, i.e., an unbounded feasible region may yield some definite value of the objective function
• In general, an unbounded LP problem solution exists due to improper formulation of the real-life problem

Prof. Jigar M. Shah 77

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

Q. Use the graphical method to solve the following LP problem:

Maximize Z = 3x1 + 4x2
Subject to constraints x1 - x2 ≥ -1 -x1 + x2 ≤ 0
and x1, x2 ≥ 0

A. There exist an infinite number of points in the convex region for which
the value of the objective function increases moving from the extreme
point (origin) to the right, i.e., the value of variables x1 and x2 can be
made arbitrarily large and accordingly the value of objective function Z
will also increase. Thus, the LP problem has an unbounded solution.

Prof. Jigar M. Shah 78

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

Q. Use the graphical method to solve the following LP problem:

Maximize Z = 3x1 + 2x2
Subject to constraints x1 - x2 ≥ 1 x 1 + x2 ≥ 3
and x1, x2 ≥ 0

A. Solution space is unbounded from above. The two corners of the region are A(0, 3) & B (2, 1)
with value of the objective function as 6 & 8, respectively. Since the objective function is to be
maximized, there exist a no. of points in the shaded region for which the value of the objective
function is more than 8, e.g., the point (2, 2) lies in the region and the objective function value
at this point is 10 which is more than 8. Thus, as value of variables x1 and x2 increase arbitrarily
large, the value of Z also starts increasing. Hence, the LP problem has an unbounded solution.

Prof. Jigar M. Shah 79

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

Q. Use the graphical method to solve the following LP problem:

Maximize Z = -x1 + 4x2
Subject to constraints 3x1 - x2 ≥ -3 -0.3x1 + 1.2x2 ≤ 3
and x1, x2 ≥ 0

A. For Z = 0, the iso-profit line passes through origin O(0,0) & point (4,1). The value of Z can be
increased by moving the Z = 0 iso-profit line upward parallel to itself until the max. value of Z
(10) is reached at the upper edge of the shaded region. Values of x1 & x2 can be made arbitrarily
large. Any point on the upper edge, extending to infinity, of the feasible region, yields the same
optimal value of Z = 10 for the objective function. Thus, the LP problem has an unbounded
feasible region, but since value of Z is finite, it does not have an unbounded solution.

Prof. Jigar M. Shah 80

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases
3. Infeasible Solution
• When no solution exists to an LP problem that satisfies all constraints & non-negativity conditions simultaneously
• This happens when there is no unique (single) feasible region
• This situation arises when a LP model that has conflicting constraints
• Any point lying outside the feasible region violates one or more of the given constraints

Q. Use the graphical method to solve the following LP problem:

Maximize Z = 6x1 - 4x2
Subject to constraints 4x1 + 8x2 ≥ 16 2x1 + 4x2 ≤ 4
and x1, x2 ≥ 0

Prof. Jigar M. Shah 81

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

A. Since there is no unique feasible solution space, therefore a unique set of values
of variables x1 and x2 that satisfy all the constraints cannot be determined.
Hence, there is no feasible solution to this LP problem because of the conflicting
constraints.

Q. Use the graphical method to solve the following LP problem:

Maximize Z = x1 + 0.5x2
Subject to constraints 3x1 + 2x2 ≤ 12 5x1 = 10 x1 + x2 ≥ 8 -x1 + x2 ≥ 4
and x1, x2 ≥ 0

Prof. Jigar M. Shah 82

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

A. Plotting the constraints provides three shaded regions satisfying some, but
not all, of the constraints. Since, the three shaded areas do not non-overlap,
there is no unique point (x1, x2) in these shaded regions that can satisfy all
the constraints simultaneously. Thus, the LP problem has an infeasible
solution i.e., the feasible solution to the LP problem does not exist.

Q. Use the graphical method to solve the following LP problem:

Maximize Z = 3x + 2y
Subject to constraints -2x + 3y ≤ 9 3x - 2y ≤ -20
and x1, x2 ≥ 0

Prof. Jigar M. Shah 83

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

A. The two shaded areas satisfy two different conditions. These two shaded
regions do not overlap and hence there is no point (x, y) common to both the
shaded regions. This implies that the feasible solution to the problem does not
exist. Consequently, this LP problem has an infeasible solution.

4. Redundancy
• A constraint that does not affect the feasible solution region (or space) is known as a redundant constraint
• In other words, a constraint is said to be redundant when it may be more binding (restrictive) than another or does not
form boundary of the feasible region
• Redundancy of any constraint does not cause any difficulty in solving an LP problem graphically

Prof. Jigar M. Shah 84

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

Q. An oil refinery manager must decide on the optimal mix of two possible blending processes of
which the inputs & outputs per production run are as follows. The max. amounts available of
crudes A & B are 200 units & 150 units, respectively. Market requirements show that at least
100 units of gasoline X & 80 units of gasoline Y must be produced. The profits per production
run for process 1 & process 2 are ₹300 & ₹400, respectively. Formulate this problem as an LP
model & solve it using graphical method to determine the production run for process 1 & 2.
Process (units) Grade A Input (units) Grade B Input (units) Gasoline X Output (units) Gasoline Y Output (units)
1 5 3 5 8
2 4 5 4 4

Prof. Jigar M. Shah 85

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases

A. Decision Variables Let x1 & x2 be the size of the production run for process 1 & 2, respectively, to be finalized by the manager

Objective Function Minimize (total profit) Z = 300x1 + 400x2

Constraints Subject to constraints 5x1 + 4x2 ≤ 200 … Crude (Grade) A Max. Availability constraints
3x1 + 5x2 ≤ 150 … Crude (Grade) B Max. Availability constraints
5x1 + 4x2 ≥ 100 … Gasoline X Min. Production constraints
8x1 + 4x2 ≥ 80 … Gasoline Y Min. Production constraints
and x1, x2 ≥ 0 … Non-negativity condition

Prof. Jigar M. Shah 86

Session 3 - 18

Linear Programming Problem

Graphical Solution Method

▪ Special Cases
Extreme Coordinates Objective Function Value Z = 200x1 + 400x2
Point
A.
A (20, 0) 300(20) + 400(0) = 6,000
B (40, 0) 300(40) + 400(0) = 12,000
C (400/13, 150/13) 300(400/13) + 400(150/13) = 1,80,000/13
D (0, 30) 300(0) + 400(30) = 12,000
E (0, 25) 300(0) + 400(25) = 10,000
The optimal solution is: (x1 = 400/13, x2 = 150/13), and Max. Z = 1,80,000/13
The manager should produce 400/13 units of gasoline through process 1 &
150/13 units of gasoline through process 2 in order to yield the maximum profit
of ₹1,80,000/13.
Constraint 8x1 + 4x2 ≥ 80 is redundant (since it does not form boundary of the
feasible region)

Prof. Jigar M. Shah 87

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Concept
▪ In an LP model, the coefficients (also known as parameters) such as:
i. profit (cost) contribution, cj, per unit of a decision variable, xj,
ii. availability of a resources, bi, and
iii. consumption of resource per unit of decision variables, aij,

are assumed to be constant and known with certainty during a planning period

▪ However, as these parameters may change, raising doubt on the validity of the optimal solution of the
given LP model, the decision-maker would like to know how changes in these parameters may affect the
optimal solution and the range within which the optimal solution will remain unchanged

Prof. Jigar M. Shah 88

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Concept
▪ Sensitivity Analysis - a technique that is used to evaluate the effect on an optimal solution of any LP
problem due to changes in its parameters

▪ Sensitivity Analysis - a technique that determines the sensitivity range (both lower and upper limit) within
which the LP model parameters can vary (one at a time) without affecting the optimality of the current
optional solution

▪ While study of duality helps to identify only an increase (or decrease) in the value of objective function
due to per unit variation in the amounts of resources available, the sensitivity analysis reveals the
magnitude of change in the optimal solution of an LP model due to discrete variations (changes) in its
parameters

Prof. Jigar M. Shah 89

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Concept
▪ Sensitivity analysis is also referred to as post-optimality analysis because it does not begin until the
optimal solution to the given LP model has been obtained

▪ Sensitivity analysis is applicable to different parametric changes in an LP problem such as:

▪ Change in profit (or cost) per unit (cj) associated with both basic & non-basic decision variables (i.e., coefficients in
the objective function
▪ Change in availability of resources (i.e., right-hand side constants, bi in constraints)
▪ Change in consumption of resources per unit of decision variables xj (i.e., coefficients of decision variables in
constraints, aij)
▪ Addition of a new variable or a new constraint to the existing ones in the LP problem

Prof. Jigar M. Shah 90

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

Sensitivity with respect to Objective Function Coefficients
Range of Optimality range of values of the objective function coefficient over which the current
for an objective function coefficient solution will remain optimal
Allowable Increase max. possible addition to the current value of the objective function
associated with an objective function coefficient coefficient without affecting the current optimal solution
Allowable Decrease max. possible reduction from the current value of the objective function
associated with an objective function coefficient coefficient without affecting the current optimal solution

Range of Optimality for an Objective Function Coefficient = (cj - Allowable Decrease)  cj  (cj + Allowable Increase)

Prof. Jigar M. Shah 91

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

Dual Value & Reduced Cost
Dual Value (or Shadow Price) change in the value of the optimal solution per unit increase in the right-
associated with a constraint hand side of the constraint
The value of the dual value may be applicable only for small changes in the right-hand side
If an increase in the right-hand side makes the optimal objective function value smaller, the dual value is negative

the dual value for the non-negativity condition associated with the variable
Reduced Cost
i.e., change in the value of the optimal solution per unit increase in the
associated with a variable
right-hand side of the non-negativity condition for the variable
In general, if a variable has a non-zero value in the optimal solution, it will have a reduced cost of zero

Prof. Jigar M. Shah 92

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

Sensitivity with respect to Right-Hand Side of Constraints
Range of Feasibility range of values of right-hand side of constraint over which current dual
for the right-hand side of a constraint value (or shadow price) associated with the constraint is applicable
Allowable Increase max. possible addition to current value of right-hand side of constraint
associated with the right-hand side of a constraint without affecting the current dual value associated with the constraint

max. possible reduction from current value of right-hand side of

Allowable Decrease
constraint without affecting the current dual value associated with the
associated with the right-hand side of a constraint
constraint

Range of Feasibility for the Right-Hand Side of a Constraint = (bi - Allowable Decrease)  bi  (bi + Allowable Increase)

Prof. Jigar M. Shah 93

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

Q. Time for the various production processes for two types of golf bags: standard & deluxe are
given below. A max. of 630 hours are available in the cutting & dyeing department, 600 hours
in the sewing department, 708 hours in the finishing department, & 135 hours in the inspection
& packaging department. Each standard bag provides a profit contribution of $10, while the
profit contribution of each deluxe bag is $9. Formulate a LP problem to determine the number
of standard & deluxe bags to produce in order to maximize total profit contribution.
Cutting & Dyeing Sewing Finishing Inspection & Packaging
Standard Bag 0.7 hour 0.5 hour 1 hour 0.1 hour
Deluxe Bag 1 hour 0.83 hour 0.67 hour 0.25 hour

Prof. Jigar M. Shah 94

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. Decision Variables Let S & D be the no. of standard & deluxe bags, respectively, to be produced

Objective Function Max. (profit contr.) Z = 10S + 9D

Constraints Subject to constraints 7Τ S
10 + 1D ≤ 630 … Cutting & Dyeing Time constraints … 1.
1Τ S + 5Τ6D ≤ 600
2 … Sewing Time constraints … 2.
1S + 2Τ3D ≤ 708 … Finishing Time constraints … 3.
1Τ S + 1Τ4D ≤ 135 … Inspection & Packaging Time constraints … 4.
10

and S, D ≥0 … Non-negativity condition

Prof. Jigar M. Shah 95

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. Sensitivity Report (computer-generated) for the solution is shown below:

Optimal Objective Value = 7668.00000
Variable Value Reduced Cost
S 540.00000 0.00000
D 252.00000 0.00000

Constraint Slack / Surplus Dual Value

1 0.00000 4.37500
2 120.00000 0.00000
3 0.00000 6.93750
4 18.00000 0.00000

Prof. Jigar M. Shah 96

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. Variable Objective Coefficient Allowable Increase Allowable Decrease

S 10.00000 3.50000 3.70000
D 9.00000 5.28571 2.33333

Constraint RHS Value Allowable Increase Allowable Decrease

1 630.00000 52.36364 134.40000
2 600.00000 Infinite 120.00000
3 708.00000 192.00000 128.00000
4 135.00000 Infinite 18.00000

Prof. Jigar M. Shah 97

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The optimal value of the objective

i.e., the maximum profit contribution is $7668
function is 7668.00000
The optimal solution is S = for maximum profit contribution, 540 standard bags & 252 deluxe bags must be
i.e.,
540.0000 and D = 252.0000 produced
per unit increase in the RHS value of the non-negativity condition for S, keeping all other
The reduced cost associated with S coefficients constant, increases the optimal value of the objective function by 0
i.e.,
is 0.0000 increasing the RHS value of the non-negativity condition for standard bags has no effect
on the optimal value of the objective function, keeping all other coefficients constant
per unit increase in the RHS value of the non-negativity condition for D, keeping all other
The reduced cost associated with D coefficients constant, increases the optimal value of the objective function by 0
i.e.,
is 0.0000 increasing the RHS value of the non-negativity condition for deluxe bags, keeping all
other coefficients constant, has no effect on the optimal value of the objective function

Prof. Jigar M. Shah 98

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The slack / surplus associated with

there is no slack (since the constraint is of ≤ type) time available with the cutting &
i.e., dyeing process
constraint 1 is 0.00000
all the time available with the cutting & dyeing process is utilized
there is a slack (since the constraint is of ≤ type) of 120 hours available with the sewing
The slack / surplus associated with
i.e., process
constraint 2 is 120.00000
only 480 hours of the time available with the sewing process is utilized
there is no slack (since the constraint is of ≤ type) time available with the finishing
The slack / surplus associated with
i.e., process
constraint 3 is 0.00000
all the time available with the finishing process is utilized
there is a slack (since the constraint is of ≤ type) of 18 hours available with the inspection
The slack / surplus associated with
i.e., & packaging process
constraint 4 is 18.00000
only 117 hours of the time available with the inspection & packaging process is utilized

Prof. Jigar M. Shah 99

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. per unit increase in the RHS value of constraint 1, keeping all other coefficients constant,
The dual value associated with increases the optimal value of the objective function by 4.37500
i.e.,
constraint 1 is 4.37500 increasing the time available with cutting & dyeing process by 1 hour, keeping all other
coefficients constant, increases the max. profit contribution by $4.375
per unit increase in the RHS value of constraint 2, keeping all other coefficients constant,
The dual value associated with increases the optimal value of the objective function by 0.00000
i.e.,
constraint 2 is 0.00000 increasing the time available with sewing process by 1 hour, keeping all other coefficients
constant, has no effect on the max. profit contribution (since it has a slack time available)
per unit increase in the RHS value of constraint 3, keeping all other coefficients constant,
The dual value associated with increases the optimal value of the objective function by 6.93750
i.e.,
constraint 3 is 6.93750 increasing the time available with finishing process by 1 hour, , keeping all other
coefficients constant, increases the max. profit contribution by $6.93750

Prof. Jigar M. Shah 100

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. per unit increase in the RHS value of constraint 4, keeping all other coefficients constant,
increases the optimal value of the objective function by 4.37500
The dual value associated with
i.e., increasing the time available with inspection & packaging process by 1 hour, keeping all
constraint 4 is 0.00000
other coefficients constant, has no effect on the max. profit contribution (since it has a
slack time available)
The objective coefficient associated
i.e., the current profit contribution per standard bag is $10
with variable S is 10.00000
the current optimal solution will remain the optimal solution as long as the profit
contribution per standard bag is a max. of $3.5 more than its current profit contribution
The allowable increase for S is
and a max. of $3.7 less than its current profit contribution
3.50000 and the allowable decrease i.e.,
the current optimal solution will remain the optimal solution as long as $6.3 ≤ profit
for x1 is 3.70000
contribution per standard bag ≤ $13.5
range of optimality for standard bags is $6.3 to $13.5

Prof. Jigar M. Shah 101

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The objective coefficient associated

i.e., the current profit contribution per deluxe bag is $9
with variable D is 9.00000
the current optimal solution will remain the optimal solution as long as the profit
contribution per deluxe bag is a max. of $5.28571 more than its current profit
The allowable increase for D is
contribution and a max. of $2.33333 less than its current profit contribution
5.28571 and the allowable decrease i.e.,
the current optimal solution will remain the optimal solution as long as $6.67 ≤ profit
for x1 is 2.33333
contribution per deluxe bag ≤ $14.28571
range of optimality for deluxe bags is $6.67 to $14.28571
Range of Optimality
Standard Bag $6.3 to $13.5
Deluxe Bag $6.67 to $14.28571

Prof. Jigar M. Shah 102

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The RHS value of constraint 1 is

time available with the cutting & dyeing process is constrained by 630 hours
i.e., cutting & dyeing process has a maximum time (since the constraint is of ≤ type) available
630.00000
of 630 hours
the current dual value associated with constraint 1 is valid as long as its RHS value is a
max. of 52.36364 hours more than its current RHS value and a max. of 134.40000 hours
The allowable increase for
less than its current RHS value
constraint 1 is 52.36364 and the
i.e., increasing the time available with cutting & dyeing process by 1 hour, keeping all other
allowable decrease for constraint 1
coefficients constant, increases the max. profit contribution by $4.375, as long as 496.6
is 134.40000
hours ≤ time available at cutting & dyeing process ≤ 682.4 hours
range of feasibility for cutting & dyeing process is 496.6 hours to 682.4 hours

Prof. Jigar M. Shah 103

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The RHS value of constraint 2 is

time available with the sewing process is constrained by 600 hours
i.e., sewing process has a maximum time (since the constraint is of ≤ type) available of 600
600.00000
hours
the current dual value associated with constraint 2 is valid as long as its RHS value is
more than its current RHS value and a max. of 120.00000 hours less than its current RHS
The allowable increase for value
constraint 2 is Infinite and the increasing the time available with cutting & dyeing process by 1 hour, keeping all other
i.e.,
allowable decrease for constraint 2 coefficients constant, has no effect on the max. profit contribution (since it has a slack
is 120.00000 time available), as long as 480 hours ≤ time available at cutting & dyeing process ≤
Infinite hours
range of feasibility for cutting & dyeing process is 480 hours and above

Prof. Jigar M. Shah 104

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The RHS value of constraint 3 is

time available with the finishing process is constrained by 708 hours
i.e., finishing process has a maximum time (since the constraint is of ≤ type) available of 708
708.00000
hours
the current dual value associated with constraint 3 is valid as long as its RHS value is a
max. of 192.00000 hours more than its current RHS value and a max. of 128.00000 hours
The allowable increase for
less than its current RHS value
constraint 3 is 192.00000 and the
i.e., increasing the time available with finishing process by 1 hour, keeping all other
allowable decrease for constraint 3
coefficients constant, increases the max. profit contribution by $6.93750, as long as 580
is 128.00000
hours ≤ time available at cutting & dyeing process ≤ 900 hours
range of feasibility for cutting & dyeing process is 580 hours to 900 hours

Prof. Jigar M. Shah 105

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. The RHS value of constraint 4 is

time available with the inspection & packaging process is constrained by 135 hours
i.e., inspection & packaging process has a maximum time (since the constraint is of ≤ type)
135.00000
available of 135 hours
the current dual value associated with constraint 4 is valid as long as its RHS value is
more than its current RHS value and a max. of 18.00000 hours less than its current RHS
The allowable increase for value
constraint 4 is Infinite and the increasing the time available with inspection & packaging process by 1 hour, keeping all
i.e.,
allowable decrease for constraint 4 other coefficients constant, has no effect on the max. profit contribution (since it has a
is 18.00000 slack time available), as long as 117 hours ≤ time available at cutting & dyeing process ≤
Infinite hours
range of feasibility for inspection & packaging process is 117 hours and above

Prof. Jigar M. Shah 106

Session 3 - 18

Linear Programming Problem

Sensitivity Analysis

▪ Key Terms & Their Interpretations

A. Range of Feasibility
Min. Value Max. Value
Cutting & Dyeing Process 496.6 hours 682.4 hours
Sewing Process 480 hours Infinite
Finishing Process 580 hours 900 hours
Inspection & Packaging Process 117 hours Infinite

Prof. Jigar M. Shah 107

Thank You
Prof. Jigar M. Shah