MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

CHAPTER 2
Linear Programming

2.1) Mathematical Programming Models – Two variables Model

2.1.1) Variables
A mathematical programming model comprises three basic elements
a) decision variables
b) objective
c) constraints

2.1.2) Linear Programming (LP) Models

A mathematical programming model is defined as a Linear Programming model
when the objective function and the constraints involve linear expressions and the
decision variables are continuous.

Example 1 – Maximization Model

Nippon produces both interior and exterior paint from two raw materials, M1 andM2. The
following table provides the basic data of the problem:

Tons of raw material per ton of Maximum daily

availability (tons)
Exterior paint Interior Paint
Raw material, M1 6 4 24
Raw material, M2 1 2 6
Profit per ton 5 4
(RM1000)

The daily demand for interior paint cannot exceed that for exterior paint by more than 1
ton. Also, the maximum daily demand for interior paint is 2 tons.

Nippon wants to determine the optimum (best) product mix of interior and exterior paints
that maximizes the total daily profit.

Answer
All OR models, LP included, consist of three basic components:

1. Decision variables that we seek to determine.

2. Objective (goal) that we need to optimize (maximize or minimize).
3. Constraints that the solution must satisfy.

The proper definition of the decision variables is an essential first step in the development
of the model. Once done, the task of constructing the objective function and the
constraints becomes more straightforward.

School of Mathematical Sciences (SMS) page 1 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

For the Nippon problem, we need to determine the daily amounts of exterior and interior
paints to be produced. Thus the variables of the model are defined as:

x1 = Tons produced daily of exterior paint

x2 = Tons produced daily of interior paint

The goal is to maximize the total daily profit of both paints. The two components of the
total daily profit are expressed in terms of the variables x1 and x2 as:

Profit from exterior paint = 5 x1 (thousand) dollars

Profit from interior paint = 4 x2 (thousand) dollars

Let z represent the total daily profit (in thousands of dollars), the objective (or goal) is
expressed as
Maximize z = 5 x1 + 4 x2

Next, we construct constraints that restrict raw material usage and product demand. The
raw material restrictions are expressed verbally as

( Usage ) ( availability )
of a raw material ≤ Maximum raw material
by both paints

The daily usage of raw material M1 is 6 tons per ton of exterior paint and 4 tons per ton
of interior paint. Thus,

Usage of raw material M1 by both paints = 6 x1 + 4 x2 tons/day

In a similar manner,

Usage of raw material M2 by both paints = x1 + 2 x2 tons/day

The maximum daily availabilities of raw materials M1 and M2 are 24 and 6 tons,
respectively.

Thus, the raw material constraints are:

6 x1 + 4 x2 = 24 (Raw material M1)
x1 + 2 x2 = 6 (Raw material M2)

The first restriction on product demand stipulates that the daily production of interior
paint
cannot exceed that of exterior paint by more than 1 ton, which translates to:

x2 −¿ x1 = 1 (Market limit)

The second restriction limits the daily demand of interior paint to 2 tons—that is,

x2 ≤2 (Demand limit)

School of Mathematical Sciences (SMS) page 2 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

An implicit (or “understood-to-be”) restriction requires (all) the variables, x1 and x2, to
assume zero or positive values only. The restrictions, expressed as x1 ≥ 0 and x2 ≥ 0, are
referred to as nonnegativity constraints.

The complete model is

Maximize z = 5 x1 + 4 x2

Subject to

6 x1 + 4 x2 ≤ 24 (1)
x1 + 2 x2 ≤ 6 (2)
−¿ x1 + x2 ≤ 1 (3)
x2 ≤ 2 (4)
x1, x2 ≥ 0 (5)

Any values of x1 and x2 that satisfy all five constraints constitute a feasible solution.
Otherwise, the solution is infeasible.

For example, the solution x1 = 3 tons per day and x2 = 1 ton per day is feasible because it
does not violate any of the five constraints.

The goal of the problem is to find the optimum, the best feasible solution that maximizes
the total profit z. First, we need to show that the Nippon problem has an infinite number
of
feasible solutions, a property that is shared by all nontrivial LPs. Hence the problem
cannot be solved by enumeration.

Note: The objective and the constraint function in all LPs must be linear. Additionally,
all the parameters (coefficients of the objective and constraint functions) of the model are
known with certainty.

2.1.3) Summary of LP Model Formulation Steps

Step 1: Define the decision variables

How many tons of Interior and exterior to produce daily

Step 2: Construct the objective function

Maximize profit

Step 3: formulate the constraints

The resources (M1 and M2) available

School of Mathematical Sciences (SMS) page 3 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Decision Variables : x1 = Tons produced daily of exterior paint

x2 = Tons produced daily of interior paint

Objective function : Maximize z = 5 x1 + 4 x2

Model Constraint : 6 x1 + 4 x2 ≤ 24 Resource availability

x1 + 2 x2 ≤ 6 M1 24 tons
−¿ x1 + x2≤ 1 M2 6 tons
x2 ≤ 2

Non-Negative constraint : x1, x2 ≥ 0

2.1.4) Model components

 Decision Variable – mathematical symbols representing levels of activity of a
firm

 Objective function – a linear mathematical relationship describing an objective of

the firm, in terms of decision variables.

 Constraints – requirements or restrictions placed on the firm by the operating

environment, stated in linear relationships of the decision variables

 Parameter – numerical coefficients and constants used in the objective function

and constraints

2.1.5) Assumptions of Linear Programming Model

 Proportionality - The rate of change (slope) of the objective function and
constraint equations is constant.

 Additivity - Terms in the objective function and constraint equations must be

additive, i.e. f(x, y) = 3x+ 5y.

 Divisibility -Decision variables can take on any fractional value and are therefore
continuous as opposed to integer in nature.

 Certainty - Values of all the model parameters are assumed to be known with
certainty (non-probabilistic).

Note:
1. Feasible solutions does not violate any of the constraints

School of Mathematical Sciences (SMS) page 4 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

2. Infeasible solution violates at least one of the constraints

3. Optimal solution is a feasible solution that results in the largest possible objective
function value when maximizing (or smallest when minimizing)

2.2) Graphical LP solutions

The graphical solution includes two steps:

1) Determination of the feasible solution space.
2) Determination of the optimum solution from among all the points in the
solution
space.

The presentation uses two examples to show how maximization and minimization
objective functions are handled.

Example 2 : Refer to Example 1

This example solves the Nippon Model using graphic method

Step 1 Determination of the Feasible solution space:

Figure 1 L Feasible space of Nippon Model

*All point outside the boundary of the area ABCDEF are infeasible

Step 2 Determination of the Optimum Solution

School of Mathematical Sciences (SMS) page 5 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Figure 2: Optimum solution of the Nippon Model

The solution is x1 = 3 and x2 = 1.5 with z = 15 × 32 + 14× 1.52 = 21. This calls for a daily
product mix of 3 tons of exterior paint and 1.5 tons of interior paint. The associated daily
profit is RM21,000.

Note: In practice, a typical LP may include hundreds or even thousands of variables and
constraints. What good then is the study of a two-variable LP? The answer is that the
graphical solution provides a key result: The optimum solution of an LP, when it exists,
is always associated with a corner point of the solution space, thus limiting the search for
the
optimum from an infinite number of feasible points to a finite number of corner points.

Exercise 1: Diet problem

Daily Farms uses at least 800 lb of special feed daily. The special feed is a mixture of
corn and soybean meal with the following compositions:

lb per lb of feedstuff Cost (RM/lb)

protein fiber
Corn 0.09 0.02 0.30
Soybean meal 0.60 0.06 0.90

The dietary requirements of the special feed are at least 30% protein and at most 5%
fiber.
The goal is to determine the daily minimum-cost feed mix.

Answer:
The decision variables of the model are:

x1 = lb of corn in the daily mix

x2 = lb of soybean meal in the daily mix

The objective is to minimize the total daily cost (in dollars) of the feed mix—that is,

Minimize z = 0.3x1 + 0.9x2

School of Mathematical Sciences (SMS) page 6 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

The constraints represent the daily amount of the mix and the dietary requirements. Daily
Farms needs at least 800 lb of feed a day—that is,

x1 + x2 ≥ 800

The amount of protein included in x1 lb of corn and x2 lb of soybean meal is (0.09 x1 + 0.6
x2) lb. This quantity should equal at least 30% of the total feed mix (x1+ x2) lb—that is,
(0.09 x1 + 0.06 x2) ≥ 0.3(x1 + x2)

In a similar manner, the fiber requirement of at most 5% is represented as

(0.02 x1 + 0.06 x2) ≤ 0.05(x1 + x2 )

The constraint are simplified by moving the terms in x1 and x2 left-hand side of each
inequality, leaving only a constant on the right-hand side. The complete model is

Minimize z = 0.3x1 + 0.9x2

Subject to
x1 + x2 ≥ 800
0.21x1 – 0.30 x2 ≤ 0
0.03x1 – 0.01x2 ≥ 0
x1, x2 ≥ 0

Figure 2.3 : Graphical solution of diet model

The model minimizes the value of the objective function by reducing z in the direction
shown in Figure 2.3. The optimum solution is the intersection of the two lines x1 + x2 =
800 and 0.21 x1 – 0.3 x2 = 0, which yields x1 = 470.6 lb and x2 = 329.4 lb. The minimum
cost of the feed mix is z = 0.3 × 470.6 + 0.9× 329.4 = RM 437.64 per day.

School of Mathematical Sciences (SMS) page 7 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Note:
One may wonder why the constraint x1 + x2 Ú 800 cannot be replaced with x1 + x2 = 800
because it would not be optimum to produce more than the minimum quantity. Although
the solution of the present model did satisfy the equation, a more complex model may
impose additional restrictions that would require mixing more than the minimum amount.
More importantly, the weak inequality (≥), by definition, implies the equality case, so
that the equation (=) is permitted if optimality requires it. The conclusion is that one
should not “pre-guess” the solution by imposing the additional equality restriction.

2.3 Linear programming applications

This section presents realistic LP models in which the definition of the variables and the
construction of the objective function and the constraints are not as straightforward as in
the case of the two-variable model. The areas covered by these applications include the
following:

1. Investment
2. Production planning and inventory management
3. Workforce planning
4. Urban development planning
5. Oil refining and blending.

2.3.1 Investment
Multitudes of investment opportunities are available to today’s investor. Examples of
investment problems are capital budgeting for projects, bond investment strategy, stock
portfolio selection, and establishment of bank loan policy. In many of these situations, LP
can be used to select the optimal mix of opportunities that will maximize return while
meeting requirements set by the investor and the market.

Example 3
Bank Shark is in the process of devising a loan policy that involves a maximum of RM12
million. The following table provides the pertinent data about available loans.

Type of loan Interest rate Bad debt ratio

Personal 0.140 0.10
Car 0.130 0.07
Home 0.120 0.03
Farm 0.125 0.05
Commercial 0.100 0.02

Bad debts are unrecoverable and produce no interest revenue.

School of Mathematical Sciences (SMS) page 8 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Competition with other financial institutions dictates the allocation of at least 40% of the
funds to farm and commercial loans. To assist the housing industry in the region, home
loans must equal at least 50% of the personal, car, and home loans. The bank limits the
overall ratio of bad debts on all loans to at most 4%.

Answer
Let
x1 = personal loans (in millions of dollars)
x2 = car loans
x3 = home loans
x4 = farm loans
x5 = commercial loans

The objective of Bank Shark is to maximize net return, the difference between interest
revenue and lost bad debts. Interest revenue is accrued on loans in good standing. For
example, when 10% of personal loans are lost to bad debt, the bank will receive interest
on 90% of the loan—that is, it will receive 14% interest on 0.9x1 of the original loan x1.
The same reasoning applies to the remaining four types of loans.

Total interest = 0.126x1 + 0.1209x2 + 0.1164x3 + 0.11875x4 + 0.098x5

Bad debt = 0.1x1 + 0.07x2 + 0.03x3 + 0.05x4 + 0.02x5

The objective function combines interest revenue and bad debt as:

Maximize z = Total interest−¿ Bad debt

Maximize z = 0.026x1 + 0.0509x2 + 0.0864x3 + 0.06875x4 + 0.078x5

Constraints
x1 + x2 + x3 + x4 + x5 ≤ 12

0.4x1 + 0.4x2 + 0.4x3 −¿0.6x4 −¿ 0.6x5 ≤ 0

0.5x1 + 0.5x2 −¿0.5x3 ≤ 0

0.06x1 + 0.03x2 −¿ 0.01x3 +¿ 0.01x4 −¿ 0.02x5 ≤ 0

x1 , x2 , x3, x4, x5 ≥0

The optimal solution is

z =0.99648, x1= 0 , x2 = 0 , x3 = 7.2, x4 = 0, x5 = 4.8

School of Mathematical Sciences (SMS) page 9 April 2024 Semester

MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

The optimal solution calls for allocating all RM12 million: RM7.2 million to home loans
and RM4.8 million to commercial loans. The remaining categories receive none. The
return on the investment is

z
Rate of return = =0.08034
12

This shows that the combined annual rate of return is 8.034%, which is less than the best
net interest rate 1= 8.64% for home loans2, and one wonders why the model does not
take full advantage of this opportunity. The answer is that the stipulation that farm and
commercial loans must account for at least 40% of all loans (constraint 2) forces the
solution to allocate $4.8 million to commercial loans at the lower net rate of 7.8%, hence
lowering the overall interest rate to 8.034%.

2.3.2 Production Planning and Inventory Control

There is a wealth of LP applications in the area of production planning and inventory

control.

Example 4: Single period production Model

In preparation for the winter season, a clothing company is manufacturing parka and
goose overcoats, insulated pants, and gloves. All products are manufactured in four
different departments: cutting, insulating, sewing, and packaging. The company has
received firm orders for its products. The contract stipulates a penalty for undelivered
items. Devise an optimal production plan for the company based on the following data:

Time per unit (hr)

Capacity (hr)
Department Parka Goose Pants Gloves
Cutting 0.30 0.30 0.25 0.15 1000
Insulating 0.25 0.35 0.30 0.10 1000
Sewing 0.45 0.5 0.40 0.22 1000
Packaging 0.15 0.15 0.10 0.05 1000
Demand 800 750 600 500
Unit profit $30 $40 $20 $10
Unit penalty $15 $20 $10 $8

Let
x1 = number of parka jackets
x2 = number of goose jackets
x3 = number of pairs of pants
x4 = number of pairs of gloves

The company is penalized for not meeting demand. The objective then is to maximize net
profit, defined as
Net profit = Total profit−¿ Total penalty
School of Mathematical Sciences (SMS) page 10 April 2024
Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

The total profit is 30x1 + 40x2 + 20x3 + 10x4. To compute the total
penalty, the demand constraints can be written as

x1 + s1 = 800, x2 + s2 = 750, x3 + s3 = 600, x4 + s4 = 500,

xj ≥ 0, sj ≥ 0, j = 1, 2, 3, 4

The new variable sj represents the shortage in demand for product j,

and the total penalty can be computed as 15s1 + 20s2 + 10s3 + 8s4.
The complete model thus becomes

Maximize z = 30x1 + 40x2 + 20x3 + 10x4 – (15s1 + 20s2 + 10s3 + 8s4)

Subject to

0.30x1 + 0.30x2 + 0.25x3 + 0.15x4 ≤ 1000

0.25x1 + 0.35x2 + 0.30x3 + 0.10 x4 ≤ 1000
0.45x1 + 0.50x2 + 0.40x3 + 0.22 x4 ≤ 1000
0.15x1 + 0.15x2 + 0.10x3 + 0.05 x4 ≤ 1000
x1 + s1 = 800, x2 + s2 = 750, x3 + s3 = 600, x4 + s4 =
500
xj ≥ 0, sj ≥ 0, j = 1, 2, 3, 4

The optimum solution is z = RM64,625, x1 = 800, x2 = 750, x3 = 387.5,

x4 = 500, s1 = s2 = s4 = 0, s3 = 212.5. The solution satisfies all the
demand for both types of jackets and gloves. A shortage of 213
(rounded up from 212.5) pairs of pants will result in a penalty cost of
213 × $10 = $2130.

Example 5: Multiple Period production inventory Model

Acme Manufacturing Company has a contract to deliver 100, 250, 190, 140, 220, and 110
home windows over the next 6 months. Production cost (labor, material, and utilities) per
window varies by period and is estimated to be RM50, RM 45, RM 55, RM 48, RM 52,
and RM 50 over the next 6 months. To take advantage of the fluctuations in
manufacturing cost, Acme can produce more windows than needed in a given month and
hold the extra units for delivery in later months. This will incur a storage cost at the rate
of $8 per window per month, assessed on end-of-month inventory. Develop a linear
program to determine the optimum production schedule.

Answer

School of Mathematical Sciences (SMS) page 11 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Mathematical Model: The variables of the problem include the

monthly production amount and the end-of-month inventory. For i = 1,
2, c, 6, let
xi = Number of units produced in month i
Ii = Inventory units left at the end of month i

The relationship between these variables and the monthly demand

over the 6-month horizon is represented schematically in Figure 2.4.
The system starts empty I0 = 0.
The objective is to minimize the total cost of production and end-of-
month inventory.

Total production cost = 50x1 + 45x2 + 55x3 + 48x4 + 52x5 + 50x6

Total inventory (storage) cost = 8(I1 + I2 + I3 + I4 + I5 + I6)

Thus the objective function is

Minimize z = 50x1 + 45x2 + 55x3 + 48x4 + 52x5 + 50x6 + 8(I1 + I2 + I3

+ I4 + I5 + I6)

Beginning inventory + Production amount - Ending inventory =

Demand

This is translated mathematically for the individual months as

x1 - I1 = 100 (Month 1)
I1 + x2 - I2 = 250 (Month 2)
I2 + x3 - I3 = 190 (Month 3)
I3 + x4 - I4 = 140 (Month 4)
I4 + x5 - I5 = 220 (Month 5)
I5 + x6 = 110 (Month 6)
xi, i = 1, 2, … , 6, Ii ≥ 0, i = 1, 2, …, 5

Figure 2.10 Optimum solution of the production-inventory problem

The optimum solution is summarized in Figure 2.10. It shows that each month’s demand
is satisfied from the same month’s production, except for month 2, where the production

School of Mathematical Sciences (SMS) page 12 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

quantity 1= 440 units2 covers the demand for both months 2 and 3. The total associated
cost is z = $49,980.

Exercise 1 (Multiperiod Production Smoothing Model)

A company is planning the manufacture of a product for March, April, May, and June of
next year. The demand quantities are 520, 720, 520, and 620 units, respectively. The
company has a steady workforce of 10 employees but can meet fluctuating production
needs by hiring and firing temporary workers. The extra costs of hiring and firing a temp
in any month are $200 and $400, respectively. A permanent worker produces 12 units per
month, and a temporary worker, lacking equal experience, produces 10 units per month.
The company can produce more than needed in any month and carry the surplus over to a
succeeding month at a holding cost of $50 per unit per month. Develop an optimal
hiring/firing policy over the 4-month planning horizon.

Exercise 2 (Bus scheduling Model)

Progress City is studying the feasibility of introducing a mass-transit bus system to
reduce in-city driving. The study seeks the minimum number of buses that can handle
transportation needs. After gathering necessary information, the city engineer noticed that
the minimum number of buses needed fluctuated with time of the day, and that the
required number of buses could be approximated by constant values over successive 4-hr
intervals. Figure 2.11 summarizes the engineer’s findings. To carry out the required daily
maintenance, each bus can operate only 8 successive hours a day.

School of Mathematical Sciences (SMS) page 13 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Figure: Number of buses as a function of the time of the day

Exercise 3 : Crude oil Refining and Gasoline blending

Shale Oil, located on the island of Aruba, has a capacity of 1,500,000 bbl of crude oil per
day. The final products from the refinery include three types of unleaded gasoline with
different octane numbers (ON): regular with ON = 87, premium with ON = 89, and super
with ON = 92. The refining process encompasses three stages: (1) a distillation tower that
produces feedstock 1ON = 822 at the rate of .2 bbl per bbl of crude oil, (2) a cracker unit
that produces gasoline stock 1ON = 982 by using a portion of the feedstock produced
from the distillation tower at the rate of .5 bbl per bbl of feedstock, and (3) a blender unit
that blends the gasoline stock from the cracker unit and the feedstock from the distillation
tower. The company estimates the net profit per barrel of the three types of gasoline to be
$6.70, $7.20, and $8.10, respectively. The input capacity of the cracker unit is 200,000
bbl of feedstock a day. The demand limits for regular, premium, and super gasoline are
50,000, 30,000, and 40,000 bbl, respectively, per day. Develop a model for determining
the optimum production schedule for the refinery.

2.4 Linear programming model in Equation form (Simplex method)

The development of the simplex method computations is facilitated by imposing two

requirements on the LP model:

1. All the constraints are equations with nonnegative right-hand side.

2. All the variables are nonnegative.

School of Mathematical Sciences (SMS) page 14 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Converting inequalities into equations with nonnegative right-hand side. To convert a (≤)
- inequality to an equation, a nonnegative slack variable is added to the left-hand side of
the constraint. For example, the M1-constraint of the Nippon model is converted into an
equation as
6x1 + 4x2 + s1 = 24, s1 ≥ 0

The nonnegative variable s1 is the slack (or unused amount) of resource M1.

Conversion from (≥) to (=) is achieved by subtracting a nonnegative

surplus variable from the left-hand side of the inequality. For
example, in the diet model, the surplus variable S1 (≥0) converts the
(=) feed mix constraint to the equation

x1 +¿ x2−¿ S1 = 800, S1 ≥0

The amount of S1 represents the excess tons of the mix over the
required minimum. (= 800 tons). The only remaining requirement is for
the right-hand side of the resulting equation to be nonnegative. The
requirement can be satisfied simply by multiplying both sides of the
equation by -1, if necessary.

Example 1:
Consider the following LP with two variables:

Maximize z = 2x1 + 3x2

subject to
2x1 + x2 ≤ 4
x1 + 2x2 ≤ 5
x1, x2≥ 0

School of Mathematical Sciences (SMS) page 15 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Algebraically, the solution space of the LP is represented by the

following m = 2 equations and n = 4 variables:
2x1 + x2 + s1 = 4
x1 + 2x2 + s2 = 5
x1, x2, s1, s2 ≥ 0

The basic solutions are determined by setting n – m (= 4 - 2 = 2)

variables equal to zero and solving for the remaining m(= 2) variables.
For example, if we set x1 = 0 and x2 = 0, the equations provide the
unique basic solution

s1 = 4, s2 = 5

This solution corresponds to point A in figure above (s1 = 4 and s2 = 5

at point A). Another point can be determined by setting s1 = 0 and s2
= 0 and then solving the resulting two equations
2x1 + x2 = 4
x1 + 2x2 = 5

The associated basic solution is (x1 = 1, x2 = 2), or point C in Figure above.

You probably are wondering which n - m variables should be set equal

to zero to target a specific corner point. Without the benefit of the
graphical solution space, we cannot specify the (n – m) zero variables
associated with a given corner point. But that does not prevent
enumerating all the corner points of the solution space. Simply
consider all combinations in which n - m variables equal zero and solve
the resulting equations. Once done, the optimum solution is the
feasible basic solution (corner point) with the best objective value.

Note
We can see from the preceding illustration that, as the size of the
problem increases, enumerating all the corner points becomes a
prohibitive task.

4! 4
Here, the (maximum) number of corner points is C 2= =6. Looking
2 ! 2!
at the graph, we can spot the four corner points A, B, C, and D. So,
where are the remaining two? In fact, points E and F also are corner
points. But, they are infeasible, and, hence, are not candidates for the
optimum.

To complete the transition from the graphical to the algebraic solution,

the zero n – m variables are known as non-basic variables. The
remaining m variables are called basic variables, and their solution
School of Mathematical Sciences (SMS) page 16 April 2024
Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

(obtained by solving the m equations) is referred to as basic solution.

The following table provides all the basic and non-basic solutions of the
current example.

Non-basic Basic Basic Associate Feasible? Objective

(zero) Variables Solution d Value z
variables Corner
point
(x1, x2) (s1,s2) (4,5) A Yes 0
(x1, s1) (x2,s2) (4,-3) F No -
(x1, s2) (x2,s1) (2.5,1.5) B Yes 7.5
(x2, s1) (x1,s2) (2,3) D Yes 4
(x2, s2) (x1,s1) (5,-6) E No -
(s1, s2) (x1,x2) (1.2) C Yes 8
(optimu
m)

2.5 Simplex Method

Rather than enumerating all the basic solutions (corner points) of the
LP problem as above example, the simplex method investigates only a
“select few” of these solutions.

2.5.1 Iterative nature of the simplex method

Figure 1 : Iterative process of the simplex method

Figure 1 provides the solution space of the LP. For the sake of
standardizing the algorithm, the simplex method always starts at the
origin where all the decision variables, xj, j = 1, 2, c, n, are zero. In
Figure 1, point A is the origin x1 = x2 = 0 and the associated objective
value, z, is zero. The logical question now is whether an increase in the

School of Mathematical Sciences (SMS) page 17 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

values of non-basic x1 and x2 above their current zero values can

improve (increase) the value of z. We can answer this question by
investigating the objective function:

Maximine z = 2x1 + 3x2

An increase in x1 or x2 (or both) above their current zero values will

improve the value of z. The design of the simplex method does not
allow simultaneous increases in variables. Instead, it targets the
variables one at a time. The variable slated for increase is the one with
the largest rate of improvement in z. In the present example, the rate
of improvement in the value of z is 2 for x1 and 3 for x2. We thus elect
to increase x2 (the variable with the largest rate of improvement
among all non basic variables). Figure 1 shows that the value of x2
must be increased until corner point B is reached (recall from Figure 1
that stopping short of corner point B is not an option because a
candidate for the optimum must be a corner point). At point B, the
simplex method, as will be explained later, will then increase the value
of x1 to reach the improved corner point C, which is the optimum.

The path of the simplex algorithm always connects corner points. In

the present example the path to the optimum is A-B-C. Each corner
point along the path is associated with an iteration. It is important to
note that the simplex method always moves alongside the edges of
the solution space, which means that the method does not cut across
the solution space. For example, the simplex algorithm cannot go from
A to C directly.

Example 2 – Simplex algorithm (Answer will discuss during lecture

session)

Consider the Nippon model expressed in equation form:

Maximize z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4

subject to

The variables s1, s2, s3, and s4 are the slacks associated with the
respective constraints.

School of Mathematical Sciences (SMS) page 18 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Next, we write the objective equation as

z - 5x1 - 4x2 = 0

The objective function z = 5x1 + 4x2 shows that the solution can be
improved by increasing the value of no basic x1 or x2 above zero.

School of Mathematical Sciences (SMS) page 19 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

*Gauss-Jordan row operations

The Gauss-Jordan computations needed to produce the new basic

solution include two types.
1. Pivot row
a. Replace the leaving variable in the Basic column with
the entering variable.
b. New pivot row = Current pivot row , Pivot element

2. All other rows, including z

New row = Current row - Pivot column coefficient * New
pivot row

School of Mathematical Sciences (SMS) page 20 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

School of Mathematical Sciences (SMS) page 21 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

2.6 Summary of the Simplex Method

In minimization problems, the optimality

condition calls for selecting the entering variable as the no basic
variable with the most positive objective coefficient in the z-row, the
exact opposite rule of the maximization case. This follows because
max z is equivalent to min (- z). As for the feasibility condition for
selecting the leaving variable, the rule remains unchanged.

Optimality condition. The entering variable in a maximization

(minimization) problem is the non basic variable with the most
negative (positive) coefficient in the z-row. Ties are broken arbitrarily.
The optimum is reached at the iteration where all the z-row coefficients
are nonnegative (nonpositive).

Feasibility condition. For both the maximization and the

minimization problems, the leaving variable is the basic variable
associated with the smallest nonnegative ratio with strictly positive
denominator. Ties are broken arbitrarily.

Gauss-Jordan row operation

2. Pivot row
a. Replace the leaving variable in the Basic column with
the entering variable.
b. New pivot row = Current pivot row , Pivot element

School of Mathematical Sciences (SMS) page 22 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

2. All other rows, including z

New row = Current row – Pivot column coefficient * New
pivot row

2.7 Graphical sensitivity Analysis

This section demonstrates the general idea of sensitivity analysis. Two
cases will be considered:

1. Sensitivity of the optimum solution to changes in the availability

of the resources (right-hand side of the constraints).

2. Sensitivity of the optimum solution to changes in unit profit or

unit cost (coefficients of the objective function).

Example 3 (Change in the Right-Hand Side

Degen manufactures two products on two machines. A unit of product

1 requires 2 hrs on
machine 1 and 1 hr on machine 2. For product 2, one unit requires 1 hr
on machine 1 and 3 hrs on machine 2. The revenues per unit of
products 1 and 2 are $30 and $20, respectively. The total daily
processing time available for each machine is 8 hrs.

Letting x1 and x2 represent the daily number of units of products 1

and 2, respectively, the, LP model is given as

Maximize z = 30x1 + 20x2

Subject to
2x1 + x2 ≤ 8 (Machine 1)
x1 + 3x2 ≤ 8 (Machine 2)
x1, x2 ≥ 0

School of Mathematical Sciences (SMS) page 23 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

Figure 1. Graphical sensitivity of optimal solution to changes in the

availability of resources

Figure 1 above illustrates the change in the optimum solution when

changes are made in the capacity of machine 1. If the daily capacity is
increased from 8 to 9 hrs, the new optimum will move to point G. The
rate of change in optimum z resulting from changing machine 1
capacity from 8 to 9 hrs can be computed as:

( )
Rate of revenue change zG −z c 142−128
resulting from increasing =capacity change = 9−8 =RM 14 /hr
maching 1 capacity by 1 hr
The computed rate provides a direct link between the model input
(resources) and its output (total revenue). It says that a unit increase
(decrease) in machine 1 capacity will increase (decrease) revenue by
RM14.

The name unit worth of a resource is an apt description of the rate of

change of the objective function per unit change of a resource.
Nevertheless, early LP developments have coined the abstract name
dual (or shadow) price and this name is now standard in all the LP
literature and software packages. The presentation in this book
conforms to this standard. Nevertheless, think “unit worth of resource”
whenever you come across standard names “dual or shadow price.”

Looking at Figure 1, we can see that the dual price of $14/hr remains
valid for changes (increases or decreases) in machine 1 capacity that

School of Mathematical Sciences (SMS) page 24 April 2024

Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

move its constraint parallel to itself to any point on the line segment
BF. We compute machine 1 capacities at points B and F as follows:

Minimum machine 1 capacity [at B = (0, 2.67)] = 2×0 + 1 × 2.67 =

2.67 hr
Minimum machine 1 capacity [at F = (8, 0)] = 2 × 8 + 1 × 0 = 16 hr

The conclusion is that the dual price of $14.00/hr remains valid only in
the range

2.67 hr ≤ Machine 1 capacity ≤ 16 hr

Changes outside this range produce a different dual price (worth per
unit).

Using similar computations, you can verify that the dual price for
machine 2 capacity is $2/hr, and it remains valid for changes in
machine 2 capacity within the line segment DE. Now,

Minimum machine 2 capacity [at D = (4, 0)] = 1 × 4 + 3 × 0 = 4 hr

Minimum machine 2 capacity [at E = (0, 8)] = 1 × 0 + 3×8 = 24 hr

Thus, the dual price of $2/hr for machine 2 remains applicable for the
range
4 hr ≤ Machine 2 capacity ≤ 24 hr

The computed limits for machine 1 and 2 are referred to as the

feasibility ranges. All software packages provide information about the
dual prices and their feasibility ranges.

Example 4 changes in the Objective coefficients

Figure 2 below shows the graphical solution space of the Degen

problem presented in Example [Link] optimum occurs at point C (x1 =
3.2, x2 = 1.6, z = 128). Changes in revenue units (i.e., objective-
function coefficients) will change the slope of z. However, as can be
seen from the figure, the optimum solution at point C remains
School of Mathematical Sciences (SMS) page 25 April 2024
Semester
MAT1064 Introduction to Operations Research B Sc (Hons) in Industrial Statistics

unchanged so long as the objective function lies between lines BF and

DE.

How can we determine ranges for the coefficients of the objective

function that will keep the optimum solution unchanged at C? First, we
write the objective function in the general format:
Maximinze z = c1x1 + c2x2

Imagine now that line z is pivoted at C and that it can rotate clockwise
and counterclockwise

The optimum solution will remain at point C so long as z = c1x1 + c2x2

lies between the two lines x1 + 3x2 = 8 and 2x1 + x2 = 8. This means
that the ratio c1 / c2 can vary between 1/3 and 2/1, which yields the
following optimality range:

1 c1 2 c1
≤ ≤ or 0.333 ≤ ≤ 2
3 c2 1 c2

School of Mathematical Sciences (SMS) page 26 April 2024

Semester