3 Optimization: Linear Programming Problems (LPPs)

• Linear Programming (also called linear optimization) is a method to achieve the best outcome
(such as maximum profit or lowest cost) in a mathematical model whose requirements are
represented by linear relationships.

• Linear programming deals with optimization of a function of variables known as objective

function. It is subjected to a set of linear equalities/inequalities known as constraints.

• Optimization can be defined as the best possible outcome with the best use of resources.

3.1 Terminologies
1. Variables (Decision Variables) - The variables usually represent the things that can be
adjusted or controlled.

- The variable values are usually unknown when a problem is started.

- The goal is to find values of the variables that provide the best value of the objective function.

2. Objective function - It is a mathematical representation that combines the variables to

indicate the requirement.

- We might require either maximization/minimization of the objective function.

3. Constraints - These are mathematical expressions that combine the variables to express the
limitations on the possible solutions.

3.2 Steps for formulation of LP Problems

1. Write down the decision variables of the problem.

2. Formulate the objective function to be optimized (max or min) as a linear function of decision
variables.

3. Formulate the other constraints, interrelations between variables etc as a linear inequali-
ties/equations in terms of decision variables.

4. Add the non-negativity constraints from the considerations because the negative values
of the decision variables do not have any physical interpretation.

In this unit, we shall focus on solution of a two-variable LPs.

Example 3.2.1. Reddy Mikks produces both interior and exterior paints from two raw materials,
M1 and M2. The following table provides the basic data of the problem

Tons of raw materials per ton of Maximum daily

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

21
A market survey indicates that the daily demand for interior paint cannot exceed that for exterior
paint by more than 1 ton. Also, the maximum daily demand for the interior paint is 2 [Link]
Mikks wants to determine the optimum (best) product mix of interior and exterior paints that
maximizes the total daily profit.

Solution:

• 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.

• For the Raddy Mikks problem, we need to determine the daily amounts to be produced of
exterior and interior paints. 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 of Reddy Mikks is to maximize (i.e., increase as much as possible) the total daily
profit of both paints. The two components of the daily profit are expressed in terms of the
variables x1 and x2 as:

Profit from exterior paint = 5x1 (thousand) dollars

Profit from interior paint = 4x2 (thousand) dollars

• Letting z represent the total daily profit (in thousands of dollars), the objective or goal of
Reddy Mikks is expressed as

Maximize z = 5x1 + 4x2

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

(Usage of raw material by both paints) ≤ (Maximum raw material available)

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

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

In a similar manner,

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

22
 • The maximum daily availabilities of raw materials M1 and M2 are 24 and 6 tons, respectively.
Thus, the raw material constraints are

6x1 + 4x2 ≤ 24 (Raw material M1)

x1 + 2x2 ≤ 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

• An implicit 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 Reddy Mikks model is
Maximize z = 5x1 + 4x2
subject to

6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
−x1 + x2 ≤ 1
x2 ≤ 2
x1 , x2 ≥ 0

• 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; whereas the solution x1 = 4 and x2 = 1 is infeasible solution,
because it does not satisfy at least one constraint.
• The goal of the problem is to find the optimum, the best feasible solution that maximizes
the total profit z. This can be achieved by:
1. Graphical method.
2. Simplex algorithm in TORA
REMARKS:
(i) The objective and the constraint function in all LPs must be linear.
(ii) All the parameters (coefficients of the objective and constraint functions) of the model are
known with certainty.

23
3.3 Solving LPPs using Graphical Method
The graphical solution includes two steps:

(i) Determination of the feasible solution space.

(ii) Determination of the optimum solution from among all the points in the feasible solution
space..

Example 3.3.1. Solve the Reddy Mikks model of example 1 using the graphical method.

step 1: Determination of the Feasible Solution Space:

• First consider the nonnegativity constraints x1 ≥ 0 and x2 ≥ 0. The horizontal axis x1 and
the vertical axis x2 represent the exterior and interior-paint variables, respectively.

• To account for the remaining four constraints, first replace each inequality with an equa-
tion, and then graph the resulting straight line by locating two distict points (preferable the
intercepts).

• Determine the correct side of the drawn lines, by choosing an appropriate reference point
[preferably the origin (0,0)].

• The feasible solution space is the area in the first quadrant that satisfies all constraints
simultaneously.

24
 Fig. 1: Feasible space of the Reddy Mikks model

In Figure 1, all points in or on the boundary of the area ABCDEF define the feasible solution
space. All points outside this area are infeasible.

step 2: Determination of the Optimum Solution:

• The number of solution points in the feasible space ABCDEF in Figure 1 is infinite. A
systematic procedure is thus needed to determine the optimum solution.

• First determine the direction in which the profit function z = 5x1 + 4x2 increases, by
assigning arbitrary increasing values to z. For example, using (arbitrary) z = 10 and z = 15
would be equivalent to graphing the two lines 5x1 + 4x2 = 10 and 5x1 + 4x2 = 15, thus
identifying the direction in which z increases.

• The optimum solution occurs at C, which is the point in the solution space beyond which
any further increase will render the solution infeasible.

• The values of x1 and x2 associated with the optimum point C are determined by solving the
equations associated with the lines (1) and (2):

6x1 + 4x2 = 24
x1 + 2x2 = 6

25
 Fig. 2: Optimum solution of the Reddy Mikks model

The solution is x1 = 3 and x2 = 1.5 with z = 5(3) + 4(1.5) = 21. This calls for daily product
mix of 3 tons of exterior paint and 1.5 tons of interior paint. The associated daily profit is
$21,000.

NOTE: An important characteristic of the optimum LP solution is that it is always associated

with a corner point of the solution space.

Corner point (x1 , x2 ) z

A (0,0) 0
B (4,0) 20
C (3,1.5) 21 (OPTIMUM)
D (2,2) 18
E (1,2) 13
F (0,1) 4

As the number of constrainsts and variables increases, the number of corner points also increases,
and the proposed enumeration procedure becomes computationally impractical. Nevertheless, the
role of the corner points is key in the development of the general algebraic algorithm called the
simplex method.

26
 TORA moment
You can use TORA interactively to see that the optimum is always
associated with the corner point.
From the output screen, you can click View/Modify Input Data to modify the
objective function coefficient and re-solve the problem graphically.

Example 3.3.2. A company that produces flags makes two flags for Nova Scotia-the traditional
blue flag and the green flag for Cape Breton. To produce each flag, two types of material, nylon
and cotton, are used. The company has 450 units of nylon in stock and 300 units of cotton. The
traditional blue flag requires 6 units of nylon and 3 units of cotton. The Cape Breton flag requires
5 units of nylon and 5 units of cotton. Each blue flag that is made realizes a profit of $12 for the
company, whereas each Cape Breton flag realizes a profit of $15.

a) Identify the constraints

b) Write inequalities for the constraints in this optimization problem.
Solution:
a) Amount of nylon and cotton materials available
b) Let x represent the number of blue flags. Let y represent the number of green flags.

Step 1: Transfer the information presented in the problem to a table.

Units Required Per Blue Flag Units Required Per Green Flag Units Available
Nylon 6 5 450
cotton 3 5 300
profit (per flag) $ 12 $ 15

The information presented in the problem identifies the restrictions or conditions on the produc-
tion of the flags. These restrictions are known as constraints and are written as inequalities to
represent the information presented in the problem.

• The number of blue flags that are produced must be either zero or greater than zero. There-
fore, the constraint is
x≥0
.

• The number of green flags that are produced must be either zero or greater than zero. There-
fore, the constraint is
y≥0
.

• The total number of units of nylon required to make both types of flags cannot exceed 450.
Therefore, the constraint is
6x + 5y ≤ 450
.

27
 • The total number of units of cotton required to make both types of flags cannot exceed 300.
Therefore, the constraint is

3x + 5y ≤ 300
.

Step 3: Write an equation to identify the profit. P = 12x + 15y

Step 4: Graph the listed constraints to identify the feasible region.

Step 5: Calculate the profit, using the profit equation, for each vertex of the feasible region:

(0, 0) : P = 12x + 15y =⇒ P = 12(0) + 15(0), =⇒ P = 0. Therefore 12x + 15y = $0.

(0, 60) : P = 12x + 15y =⇒ P = 12(0) + 15(60), =⇒ P = 900. Therefore 12x + 15y = $900.
(50, 30) : P = 12x + 15y =⇒ P = 12(50) + 15(30), =⇒ P = 1050. Therefore 12x + 15y = $1050.
(75, 0) : P = 12x + 15y =⇒ P = 12(75) + 15(0), =⇒ P = 900. Therefore 12x + 15y = $900.
The maximum profit occurred at the vertex (50, 30). This means, with the supplies in stock, the
company should make 50 blue flags and 30 green flags to maximize their profit.

Exercise 5.

1. A company produces two products, A and B. The sales volume for A is at least 80% of the
total sales of both A and B. However, the company cannot sell more than 110 units of A per
day. Both products use one raw material, of which the maximum daily availability is 240 lb.
The usage rates of the raw material are 2 lb per unit of A and 4 lb per unit of B. The profit
units for A and B are $10 and $ 25, respectively. Determine the optimal product mix for the
company.
[Answer: Let x1 =Number of units of A, x2 =Number of units of B. Maximize z = 20x1 +50x2
subject to (....). Optimum solution: (x1 , x2 ) = (100, 25), z = $6250]

28
2. An individual wishes to invest $5000 over the next year in two types of investment: Investment
A yields 5% and investment B yields 8%. Market research recommends an allocation of at
least 25% in A and at most 50% in B. Moreover, investment in A should be at least half the
investment in B. How should the fund be allocated to the two investments?
[Answer: Let x1 =Dollars invested in A, x2 =Dollars invested in B. Maximize z = 0.05x1 +
0.08x2 subject to: (....) Optimum: (x1 , x2 ) = (2500, 2500), z = $325]

3. An assembly line consisting of three consecutive stations produces two radio models: HiFi-1
and HiFi-2. The following table provides the assembly times for the three workstations.

Minutes per unit

Workstation HiFi-1 HiFi-2
1 6 4
2 5 5
3 4 6

The daily maintenance for stations 1,2 and 3 consumes 10%, 14% and 12%, respectively, of
the maximum 480 minutes available for each station each day. Determine the optimal product
mix that will minimize the idle (or unused) times in the three workstations.
[Answer: Let x1 =Number of HiFi-1 units, x2 =Number of HiFi-2 units. Minimize z =
1267.2 − (15x1 + 15x2 ) subject to: 6x1 + 4x2 ≤ 432, 5x1 + 5x2 ≤ 412.8, 4x1 + 6x2 ≤ 422.4,
x1 , x2 ≥ 0
Optimum: (x1 , x2 ) = (50.88, 31.68), z = 28.8 idle min]

29
3.4 Linear Programming Applications
The areas covered by these applications include the following:
1. Investment

2. Production Planning and inventory control

3. Manpower planning

4. Urban development planning

5. Oil refining and blending.

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
estbalishment 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.4.1. Bank Loan Model
Bank One is in the process of devising a loan policy that involves a maximum of $ 12 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. 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%.

Mathematical Model: The situation deals with determining the amount of loan in each category,
thus leading to the following definitions of the variables:

x1 = Personal loans (in millions of dollars)

x2 = car loans
x3 = home loans
x4 = farm loans
x5 = commercial loans

The objective of the Bank One 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%

30
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 is applies to the
remaining four other types of loans. Thus,

Total interest = 0.14(0.90x1 ) + 0.13(0.93x2 ) + 0.12(0.97x3 ) + 0.125(0.95x4 ) + 0.10(0.98x5 )

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

We also have

Bad debt = 0.10x1 + 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.126x1 + 0.1209x2 + 0.1164x3 + 0.11875x4 + 0.098x5 )
− (0.10x1 + 0.07x2 + 0.03x3 + 0.05x4 + 0.02x5 )
= 0.026x1 + 0.0509x2 + 0.0864x3 + 0.06875x4 + 0.078x5

The problem has five constraints:

1. Total funds should not exceed $12 (million):

x1 + x2 + x3 + x4 + x5 ≤ 12

2. Farm and commercial loans equal at least 40% of all loans:

x4 + x5 ≥ 0.4(x1 + x2 + x3 + x4 + x5 )

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

3. Home loans should equal at least 50% of persoanl, car and home loans:

x3 ≥ 0.5(x1 + x2 + x3 )

or
0.5x1 + 0.5x2 − 0.5x3 ≤ 0

4. Bad debts should not exceed 4% of all loans:

0.10x1 + 0.07x2 + 0.03x3 + 0.05x4 + 0.02x5 ≤ 0.04(x1 + x2 + x3 + x4 + x5 )

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

5. Nonnegativity:
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0

31
A subtle assumption in the preceeding formulation is that all loans are issued at approximately the
same time. It allows us to ignore differences in the time value of the funds allocated to the different
loans.
Solution: The optimal solution is computed using TORA:
z = 0.99648, x1 = 0, x2 = 0, x3 = 7.2, x4 = 0, x5 = 4.8
Remarks: The optimal solution calls for allocating all $ 12 million: $ 7.2 million to home loans
and $ 4.8 million to commercial loans. The remaining categories receive none.
The return on the investment is
z 0.99648
Rate of return = = = 0.08034
12 12
This shows that the combined annual rate of return is 8.034%.
Exercise 6.

1. (Planning) A company manufactures two products X and Y , which require the following
resources. The resources are the capacities of machines M1 , M2 and M3 . The available
capacities are 50,25 and 15 hours, respectively in the planning period. Product X requires 1
hour of machine M2 and 1 hour of machine M3 . Product Y requires 2 hours of machine M1
and 2 hours of machine M2 and 1 hour of machine M3 . The profit contribution of products
X and Y are $5 and $4, respectively. Formulate and solve the mathematical (LP) model that
will maximize the profit. Use graphical method. (Easy Problem)
2. A business executive has the option to invest money in two plans: Plan A guarantees that
each dollar invested will earn $0.70 a year later, and plan B guarantees that each dollar
invested will earn $2 after 2 years. In plan A, investments can be made annually, and in plan
B, investments are allowed for periods that are multiples of 2 years only. How should the
executive invest $ 100,000 to maximize the earnings at the end of 3 years? Solve the model
using TORA. (Difficult Problem)
[Answer: Let xiA =amount invested in year i using plan A, i = 1, 2, 3; xiB =amount invested
in year i using plan B, i = 1, 2, 3. Maximize z = 3x2B + 1.7x3A subject to (....)
Optimum solution: Invest $100,000 in plan A in year 1 and $170,000 in plan B in year 2. The
problem has alternative optima.]
3. Investor Doe has $ 10,000 to invest in four projects. The following table gives the cash flow
for the four investments.

Cash flow ($ 1000) at the start of

Project Year 1 Year 2 Year 3 Year 4 Year 5
1 -1.00 0.50 0.30 1.80 1.20
2 -1.00 0.60 0.20 1.50 1.30
3 0.00 -1.00 0.80 1.90 0.80
4 -1.00 0.40 0.60 1.80 0.95

The information in the table can be interpreted as follows: For project 1, $1.00 invested at
the start of year 1 will yield $0.50 at the start of year 2, $0.30 at the start of year 3, $1.80 at

32
 the start of year 4, and $1.20 at the start of year 5. The remaining entries can be interpreted
similarly. The entry 0.00 indicates that no transaction is taking place. Doe has the additional
option of investing in a bank account that earns 6.5% annually. All funds accumulated at
the end of year 1 can be reinvested in the following [Link] the problem as a linear
program to determine the optimal allocation of funds to investment opportunities. Solve the
model using TORA. (Difficult Problem)
[Answer: Let xi =Dollars invested in project i, i = 1, 2, 3, 4; yi =Dollars invested in bank in
year j, j = 1, 2, 3, 4. Maximize z = y5 subject to (....)
Optimum solution: x1 = 0, x2 = $10, 000, x3 = $6000, x4 = 0, y1 = 0, y2 = 0, y3 = $6800,
y4 = $33, 642, z = $53, 628.73 at the start of year 5

4. (Production Allocation Problem) A firm produces three products. These products are
processed on three different machines. The time required to manufacture one unit of each of
the three products and the daily capacity of the three machines are given in the table below.

Machine Time per unit (minutes) capacity (minutes/pay)

M1 2 2 2 440
M2 4 - 3 470
M3 2 5 - 430

It is required to determine the daily number of units to be manufactured for each product.
The profit per unit for products 1,2 and 3 are $4, $3 and $6, respectively. It is assumed that
all the amounts produced are consumed in the market. Formulate and solve a mathematocal
(L.P) model that will maximize the daily profit. (Easy Problem)

** End of Topic Three **

33