Chapter III: Introduction to Linear Programming

CHAPTER III
INTRODUCTION TO LINEAR PROGRAMMING
Linear Programmingis an optimization method, which shows how to
allocate scarce resources such as money, materials or time and how to do such
allocation in the best possible way subject to more than one limiting condition
expressed in the form of inequalities and/or equations.
It enables users to find optimal solution to certain problems in which the solution
must satisfy a given set of requirements or constraints.
Optimization in linear programming implies either maximization (such as profit,
revenue, sales, and market share) or minimization (such as cost, time, and
distance) a certain objective function. It implies that in LP we cannot max/min
two quantities in one model. It involves linearly related multi-variate functions,
i.e., functions with more than one independent variable.
The goal in linear programming is to find the best solution given the constraints
imposed by the problem; hence the term constrained optimization.
Linear programming Models (LPM)
Linear Programming (LP) models are mathematical representations of LP
problems. Some LP models have a specialized format, whereas others have a
more generalized format. Despite this, LP Models have certain characteristics in
common. Knowledge of these characteristics enables us to recognize problems
that are amenable to a solution using LP models and to correctly formulate an LP
model. The characteristics can be grouped into two categories: Components and
Assumptions. The components relate to the structure of a model, whereas the
assumptions reveal the conditions under which the model is valid.
Components
1. Objective function
2. Decision variables
3. Constraints
4. Parameters & RHSV

Model
Structure

Assumptions
1. Linearity
2. Divisibility
3. Certainty
4. Non-negativity

Mathematics for Management (MGMT 121)

Model
Validity

Chapter III: Introduction to Linear Programming

Components of LP model
1.

The Objective Function- is the mathematical or quantitative expression of

the objective of the company/model. The objective in problem solving is the
criterion by which all decisions are evaluated. In LPMs a single quantifiable
objective must be specified by the decision maker. For example, the objective
might relate to profits, or costs, or market share, but to only one of these.
Moreover, because we are dealing with optimization, the objective will be either
maximization or minimization, but not both at a time.

2.

The Decision Variables - represent unknown quantities to be resolved for.

These decision variables may represent such things as the number of units of
different products to be sold, the amount of Birr to be invested in various
projects, the number of ads to be placed with different media.

Since the decision maker has freedom of choice among actions, these decision
variables are controllable variables.
3.
The constraints - are restrictions which define or limit the feasibility of a
proposed course of action. They limit the degree to which the objective can be
pursued.
A typical restriction embodies scarce resources (such as labor supply, raw
materials, production capacity, machine time, storage space), legal or contractual
requirements (e.g. Product standards, work standards), or they may reflect other
limits based on forecasts, customer orders, company policies etc.
4.
Parameters - are fixed values that specify the impact that one unit of each
decision variable will have on the objective and on any constraint it pertains to as
well as to the numerical value of each constraint.
The components are the building blocks of an LP model. We can better
understand their meaning by examining a simple LP model as follows.
Example:
Maximize: 4X1 + 7X2 + 5X3 (Profit) ________________ objective function
Subject to:
2X1 + 3X2 + 6X3 300 labor hrs
5X1 + X2 + 2X3 200 lb raw material A
System Constraints
3X1 + 5X2 + 2X3 360
X1
= 30
Individual
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

X2
X1, X2, X3

40
constraints
0 Non-negativity constraints.

System constraints involve more than one decision variables.

Individual constraints involve only one decision variable.
None-negativity constraints specify that no variable will be allowed to take on a
negative value. The non-negativity constraints typically apply in an LP model,
whether they are explicitly stated or not.
Assumption of LP Models
1.

Linearity. The linearity requirement is that each decision variable has a

linear impact on the objective function and in each constraint in which it appears.
Following the above example, producing one more unit of product 1 adds Br. 4 to
the total profit. This is true over the entire range of possible values of X 1. The
same applies to each of the constraints. It is required that the same coefficient (fro
example, 2 lb. per unit) apply over the entire range of possible value so the
decision variable.

2.

Divisibility. The divisibility requirement pertains to potential values of

decision variables. It is assumed that non-integer values are acceptable. For
example: 3.5 TV sets/hr would be acceptable 7 TV sets/2hrs.

3.

Certainty. The certainty requirement involves two aspects of LP models.

i) With respect to model parameters (i.e., the numerical values) It in
assumed that these values are known and constant e.g. in the above
example each unit of product 1 requires 2lab his is known and remain
constant, and also9 the 300 lab/hr available is deemed to be known
and constant.
ii) All the relevant constraints identified and represented in the model are as
they are.

4.

Non-negativity. The non-negativity constraint is that negative values of

variables are unrealistic and, therefore, will not be considered in any potential
solution; only positive values and zero will be allowed.
Formulating LP Models

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

Once a problem has been defined, the attention of the analyst shifts to
formulating a model. Just as it is important to carefully define a problem, it is
important to carefully formulate the model that will be used to solve the
problem. If the LP model is ill formulated, ill-structured, it can easily lead to poor
decisions.
Formulating linear programming models involves the following steps:
1. Define the problem/problem definition
* To determine the # of type 1 and type 2 products to be produced per
mother so as to maximize the monthly profit given the restrictions.
2. Identify the decision variables or represent unknown quantities
* Let X1 and X2 be the monthly qualities of Type 1 and type 2 products
3. Determine the objective function
* Once the variables have been identified, the objective function can be
specified. It is necessary to decide if the problem is a maximization or a
minimization problem and the coefficients of each decision variable.
Note: a. The units of all the coefficients in the objective function must be the
same. E.g. If the contribution of type 1 is in terms of Br so does for
type 2.
b. All terms in the objective function must include a variable each term
have to have 1 variable.
c. All decision variables must be represented in the objective function.
4. Identifying the constraints
- System constraints
- more than one variable
- Individual constraints - one variable
- Non-negative constraints
Example
1. A firm that assembles computer and computer equipment is about to start
production of two new microcomputers. Each type of micro-computer will
require assembly time, inspection time and storage space. The amount of each of
these resources that can be devoted to the production of microcomputers is
limited. The manger of the firm would like to determine the quantity of each

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

microcomputer to produce in order to maximize the profit generated by sales of

these microcomputers.
Additional information
In order to develop a suitable model of the problem, the manager has met with
design and manufacturing personnel. As a result of these meetings, the manger
has obtained the following information:
Type 1
Profit per unit
Assembly time per unit
Inspection time per unit
Storage space per unit

Type 2

Birr 60
4hrs
2hrs
3cubic ft

Birr 50
10hrs
1hr
3cubic ft

The manager also has acquired information on the availability of company

resources. These weekly amounts are:

Resource
Assembly time
Inspection time
Storage space

Resource available
100hrs
22hrs
39 cubic feet

The manger also meet with the firms marketing manger and learned that
demand for the microcomputers was such that whatever combination of these
two types of microcomputer is produced, all of the output can be sold.
Required: Formulate the Linear programming model.
Solution:
Step 1: Problem Definition
- To determine the number of two types of microcomputers to be
produced (and sold) per week so as to maximize the weekly profit
given the restriction.
Step 2: Variable Representation
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

- Let X1 and X2 be the weekly quantities of type 1 and type 2

microcomputers, respectively.
Step 3: Develop the Objective Function
Maximize or Zmax = 60X1 + 50X2

Step 4: Constraint Identification

System constraints: 4X1 + 10X2 100hrs
Assembly time
2X1 + X2 22hrs
inspector time
3X1 + 3X2 39 cubic feet Storage space
Individual constraint
Non-negativity constraint

No
X1, X2 0

In summary, the mathematical model for the microcomputer problem is:

Zmax = 60X1 + 50X2
Subject to: 4X1 + 10X2 100
2X1 + X2 22
X1 + 3X2 39
X1, X2 0

2. An electronics firm produces three types of switching devices. Each type involves
a two-step assembly operation. The assembly times are shown in the following
table:
Assembly time per Unit (in minutes)

Model A
Model B
Model C

Section #1
2.5
1.8
2.0

Mathematics for Management (MGMT 121)

Section #2
3.0
1.6
2.2

Chapter III: Introduction to Linear Programming

Each workstation has a daily working time of 7.5 hrs. The manager wants to
obtain the greatest possible profit during the next five working days. Model A
yields a profit of Birr 8.25 per unit, Model B a profit of Birr 7.50 per unit and
Model C a profit of Birr 7.80 per unit. Assume that the firm can sell all it
produces during this time, but it must fill outstanding orders for 20 units of each
model type.

Required:

Formulate the linear programming model of this problem.

Solution:
Step 1. Problem definition
To determine the number of three types of switching devices to be
produced and sold for the next 5 working days so as to maximize the 5
days profit.
Step 2. Variable representation
Let X1, X2 and X3 be the number of Model A, B and C switching devices
respectively, to be produced and sold.
Step 3. Develop objective function
Zmax: 8.25X1 + 7.50X2 + 7.80X3
Step 4. Constraint identification
2.5X1 + 1.8X2 + 2.0X3 450 minutes Ass. time station 1 System
3.0X1 + 1.6X2 + 2.2X3 450 minutes Ass. time station 2
X1
20 Model A
X2
20
Model B
Individual constraint
X3 20 Model C
X1, X2, X3
0
Non negativity

In summary:
Zmax: 8.25X1 + 7.50X2 + 7.80X3
: 2.5X1 + 1.8X2 + 2.0X3 450 minutes
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

3.0X1 + 1.6X2 + 2.2X3 450
X1
20
X2
20
X3 20
X1, X2, X3 0

minutes
model A
model B
model C
non negativity

3. A diet is to include at least 140 mgs of vitamin A and at least 145 Mgs of vitamin
B. These requirements are to be obtained from two types of foods: Type 1 and
Type 2. Type 1 food contains 10Mgs of vitamin A and 20mgs of vitamin B per
pound. Type 2 food contains 30mgs of vitamin A and 15 mgs of vitamin B per
pound. If type 1 and 2 foods cost Birr 5 and Birr 8 per pound respectively, how
many pounds of each type should be purchased to satisfy the requirements at a
minimum cost?

Foods
Type 1
Type 2

Vitamins
A
10
30

B
20
15

Solution:
Step 1. Problem definition
To determine the pounds of the two types of foods to be purchased to
make the diet at a minimum possible cost within the requirements.
Step 2. Variable representation
Let X1 and X2 be the number of pounds of type 1 and type 2 foods to be
purchased, respectively.
Step 3. Objective function
Cmin: 5X1 + 8X2
4. Constraints
10X1 + 30X2 140
20X1 + 15X2 145

System constraints

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

X1, X2

non-negativity constraints.

4. A farm consists of 600 hectares of land of which 500 hectares will be planted with
corn, barley and wheat, according to these conditions.
(1) At least half of the planted hectar should be in corn.
(2) No more than 200 hectares should be barley.
(3) The ratio of corn to wheat planted should be 2:1
It costs Birr 20 per hectar to plant corn, Birr 15 per hectar to plant barley and Birr
12 per hectar to plant wheat.
a.

Formulate this problem as an LP model that will minimize

planting cost while achieving the specified conditions.

Solution:
Step 1. Problem definition
To determine the number of hectares of land to be planted with corn,
barley and wheat at a minimum possible cost meeting the requirements.
Step 2. Decision variable representation
Let X1 be the number of hectares of land to be planted with corn, X 2 be the
number of hectares of land to be planted with barley, and X 3 be the
number of hectares of land to be planted with wheat.
Step 3. Objective function
Cmin = 20X1 + 15X2 + 12X3
Step 4. Constraints
X1 + X2 + X3 = 500
X1
250
X2
200
X1 2X2
=0
X1, X2, X3 0
In summary
Cmin: 20X1 + 15X2 + 12X3
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

10

: X1 + X2 + X2 = 500
X1 2X2
=0
X1
250
X2
200
X1, X2, X3
0
Solution Approaches to Linear Programming Problems
There are two approaches to solve linear programming problems:
1. The Graphic solution method
2. The Algebraic solution/ simplex algorithm method

A. The Graphic Solution Method

It is a relatively straightforward method for determining the optimal solution to
certain linear programming problems. It gives as a clear picture. This method can
be used only to solve problems that involve two decision variables. However,
most linear programming applications involve situations that have more than
two decision variables, so the graphic approach s not used to solve them.
E.g.: 1. Solving the micro-computer problem with graphic approach
Zmax = 60X1 + 50X2
: 4X1 + 10X2 100
2X1 + X2 22
3X1 + 3X2 39
X1, X2 0
Steps:
1. Plot each of the constraints and identify its region make linear
inequalities linear equations.
2. Identify the common region, which is an area that contains all of the
points that satisfy the entire set of constraints.
3. Determine the Optimal solution- identify the point which leads to
maximum benefit or minimum cost.
24
22

2X1 + X2 = 22

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

11

20

16

(0, 13)

12
E
8
4

(0, 0) A

3X1 + 3X2 = 39

(5, 8) D

4X1 + 10X2 = 100

(9, 4) C
4

B 12

16

20

24

28

To identify the maximum (minimum) value we use the corner point approach or
the extreme point approach. The corner point/extreme point approach has one
theorem: It states that;
For problems that have optimal solutions, a solution will occur at an
extreme, or corner point. Thus, if a problem has a single optimal solution,
it will occur at a corner point. If it has multiple optimal solutions, at least
one will occur at a corner point. Consequently, in searching for an optimal
solution to a problem, we need only consider the extreme points because
one of those must be optimal. Further, by determining the value of the
objective function at each corner point, we could identify the optimal
solution by selecting the corner point that has the best value (i.e.,
maximum or minimum, depending on the optimization case) at the
objective function.
3.1

3.2
3.3

Determine the values of the decision variables at each corner point.

Sometimes, this can be done by inspection (observation) and sometimes by
simultaneous equation.
Substitute the value of the decision variables at each corner point.
After all corner points have been so evaluated, select the one with
the highest or lowest value depending on the optimization case.

Points
A

Coordinates
X1
X2
0
0

How
Determined
Observation

Value of Objective function

Z = 60X1 + 50X2
Birr 0

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

B
C

11
9

0
4

10

Observation
Simultaneous
equations
Simultaneous
equations
Observation

12

Birr 660
Birr 740
Birr 700
Birr 500

Basic solution
X1 = 9
X2 = 4
Z = Birr 740
After we have got the optimal solution, we have to substitute the value of the
decision variables into the constraints and check whether all the resources
available were used or not. If there is an unused resource we can use it for any
other purpose. The amount of unused resources is known as SLACK-the amount
of the scarce resource that is unused by a given solution.
The slack can range from zero, for a case in which all of a particular resource is
used, to the original amount of the resource that was available (i.e., none of it is
used).

Constraint
Assembly time
Inspection time
Storage space

Computing the amount of slack

Amount used with
Originally
X1 = 9 and X2 = 4
available
4(9) + 10(4) = 76
100 hrs
2(9) = 1 (4) = 22
22 hrs
3(9) + 3(4) = 39
39 cubic ft

Amount of slack
(available Used)
100 76 = 24 hrs
22 22 = 0 hr
39 39 = 0 cubic ft

Constraints that have no slack are some time referred to as binding constraints
since they limit or bind the solution. In the above case, inspection time and
storage space are binding constraints; while assembly time has slack.
Knowledge of unused capacity can be useful for planning. A manager may be
able to use the assembly time for other products, or, perhaps to schedule
equipment maintenance, safety seminars, training sessions or other activities.
Interpretation: The Company is advised to produce9 units of type 1
microcomputers and 4 units of type 2 microcomputers per week to maximize his

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

13

weekly profit to Birr 740; and in do so the company would be left with unused
resource of 24-assembly hrs that can be used for other purposes.
2. Solving the diet problem with graphic approach
Cmin: 5X1 + 8X2
10X1 + 30X2 140
20X1 + 15X2 145
X1, X2
0
16

12
(0, 9.67)

A
8

Points
A
B
C

20X1 + 15X2 = 145

B (5, 3)

4
Coordinates
X1
X2
0
9.67
5
3
14

10X1 + 30X2 = 140

C (14,0)
8
12
16
20
How
Value of the objective function
Determined
Z = 5X1 + 8X2
Observation
Birr 77.30
Simultaneous
Birr 49
equations
Observation
Birr 70

Basic solution: X1 = 5 pounds

X2 = 3 pounds
C = Birr 49
Interpretation: To make the diet at the minimum cost of Birr 49 we have to
purchase 5 pounds of Type1 food and 3 pounds Type 2 food.
If there is a difference between the minimum required amount and the optimal
solution, we call the difference surplus: That is, Surplus is the amount by which
the optimal solution causes a constraint to exceed the required minimum
amount. It can be determined in the same way that slack can: substitute the
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

14

optimal values of the decision variables into the left side of the constraint and
solve. The difference between the resulting value and the original right-hand side
amount is the amount of surplus. Surplus can potentially occur in a constraint.
B. The Simplex Algorithm/Algebraic Solution Method
The simplex method is an iterative technique that begins with a feasible solution
that is not optimal, but serves as a starting point. Through algebraic
manipulation, the solution is improved until no further improvement is possible
(i.e., until the optimal solution has been identified). Each iteration moves one step
closer to the optimal solution. In each iteration, one variable that is not in the
solution is added to the solution and one variable that is in the solution is
removed from the solution in order to keep the number of variables in the basis
equal to the number of constraints.
The optimal solution to a linear programming model will occur at an extreme
point of the feasible solution space. This is true even if a model involves more
than two variables; optimal solutions will occur at these points. Extreme points
represent intersections of constraints. Of course, not every solution will result is
an extreme point of the feasible solution space; some will be outside of the
feasible solution space. Hence, not every solution will be a feasible solution.
Solutions which represent intersections of constraints are called basic solutions;
those which also satisfy all of the constraints, including the non-negativity
constraints, are called basic feasible solutions. The simplex method is an
algebraic procedure for systematically examining basic feasible solutions. If an
optimal solution exists, the simplex method will identify it.
The simplex procedure for a maximization problem with all constraints consists
of the following steps.
1.

Write the LPM in a standard form: when all of the constraints are written
as equalities, the linear program is said to be in standard form. We convert the
LPM in to a standard form by applying the slack variables, S, which carries a
subscript that denotes which constraint it applies to. For example, S 1 refers to the
amount of slack in the first constraint, S 2 to the amount of slack in the second
constraint, and so on. When slack variables are introduced to the constraints,
they are no longer inequalities because the slack variable accounts for any
difference between the left and right-hand sides of an expression. Hence, once
slack variables are added to the constraints, they become equalities. Furthermore,
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

15

every variable in a model must be represented in the objective function. However,

since slack does not provide any real contribution to the objective, each slack
variable is assigned a coefficient of zero in the objective function.
Slack = Requirement Production, surplus = Production Requirement
Taking the microcomputer problem its standard form is as follows:
Zmax = 60X1 + 50X2
Zmax = 60X1 + 50X2 + 0S1 + S2 + 0S3
: 4X1 + 10X2 100
: 4X1 + 10X2 + S1 = 100
2X1 + X2 22
2X1 + X2 + S2 = 22
3X1 + 3X2 39
3X1 + 3X2 + S3 = 39
X1, X2 0
X1, X2, S1, S2, S3 0

2.

Develop the initial tableau: the initial tableau always represents the Do
Nothing strategy, so that the decision variables are initially non-basic.
a)
b)
c)

d)
e)

List the variables across the top of the table and write the
objective function coefficient of each variable jut above it.
There should be one row in the body of the table for each
constraint. List the slack variables in the basis column, one per raw.
In the Cj column, enter the objective function coefficient of
zero for each slack variable. (Cj - coefficient of variable j in the objective
function)
Compute values for row Zj
Computer values for Cj Zj.

60
X1
S1
0
4
S2
0
2*
S3
0
3
Zj
0
Cj-Zj 60
Entering variable
* Pivot Element
Sol/n Cj
basis

50
X2

0
S1

0
S2

0
S3

RHSV j = bj/xj (aij)

10

100

100/4 = 25

0
1
0
0

22
39
0
0

22/2 = 11
39/3 = 13

1
3
0
50
Pivot

0
1
0
0
0
0
0
0
column

Mathematics for Management (MGMT 121)

Pivot row

Leaving
variable

Chapter III: Introduction to Linear Programming

16

3.

Develop subsequent tableaus

3.1. Identify the entering variable - a variable that has a largest positive
value is the Cj Zj raw.
3.2. Identify the leaving variable - Using the constraint coefficients or
substitution rates in the entering variable column divide each one
into the corresponding quantity value. However do not divide by a
zero or negative value. The smallest non-negative ratio that results
indicate which variable will leave the solution.

4.

Find unique vectors for the new basic variable using row
operations on the pivot element.
Sol/n Cj
basis

60
X1

S1
X1

0
1

0
60

S3

0
0
Zj
60
Cj-Zj 0
Leaving variable

50
X2
8
1/2
3/2
30
20

0
S1

0
S2

0
S3

RHSV j = bj/xj (aij)

1
0

-2
1/2

0
0

56
11

56/8 = 7
11/. 5 = 22

0
0
0

-3/2 1
30
0
-30
0

6
660
0

6/1.5 = 4

Entering Variable
Sol/n
basis
S1
X1
X2

Cj
0
60
50
Zj
Cj-Zj

60
X1
0
1
0
60
0

50
X2
0
0
1
50
0

0
S1
1
0
0
0
0

0
S2
6
1
-1
10
-10

0
S3
-16/3
-1/3
2/3
40/3
-40/3

Optimal solution: X1 = 9
X2 = 4
S1 = 24 hrs
Z = Birr 740
5. Compute the Cj Zj raw

Mathematics for Management (MGMT 121)

RHSV
24
9
4
740

j = bj/xj (aij)

Chapter III: Introduction to Linear Programming

17

6. If all Cj Zj values are zeros and negatives you have reached

optimality.
7. If this is not the case (step 6), rehear step 2to5 until you get
optimal solution.
A simplex solution is a maximization problem is optimal if the Cj Zj row
consists entirely of zeros and negative numbers (i.e., there are no positive values
in the bottom row).
Note: The variables in solution all have unit vectors in their respective
columns for the constraint equations. Further, note that a zero appears is raw c
- z in every column whose variable is in solution, indicating that its maximum
contribution to the objective function has been realized.

Example 2
A manufacturer of lawn and garden equipment makes two basic types of lawn
mowers: a push-type and a self-propelled model. The push-type requires 9
minutes to assemble and 2 minutes to package; the self-propelled mower requires
12 minutes to assemble and 6 minutes to package. Each type has an engine. The
company has 12 hrs of assembly time available, 75 engines, and 5hrs of packing
time. Profits are Birr 70 for the self-propelled models and Birr 45 for the pushtype mower per unit.
Required:
1. Formulate the linear programming models for this problem.
2. Determined how many mower of each type to make in order to maximize
the total profit (use the simplex procedure).
Solution:
1.
a)
To determine ho many units of each types of mowers to produce
so as to maximize profit.
b)
Let X1 - be push type mower.
X2 - be self-propelled mower.
c) Determine the objective function
Zmax = 45X1 + 70X2
d) Identify constraints
9X1 + 12X2 720 minutes
Assembly time

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

2X1 + 6X2 300 minutes
X1 + X2 75 engines
X1, X2 0

18

packing time
Engines

In summary:
Zmax = 45X1 + 70X2
: 9X1 + 12X2 720
2X1 + 6X2 300
X1 + X2 75
X1, X2 0
2.
a. Write the LPM in a standard form
Zmax = 45X1 + 70X2 + OS1 + OS1 + OS3
: 9X1 + 12X2 + S1 = 720
2X1 + 6X2 + S2 = 300
X1 + X2 + S3 = 75
X1, X2, S1, S2, S3 o
b. Develop the initial tableau in LP matrices are commonly called
tableaus
Sol/n
basis

Cj

45
X1

S1

S2
S3

0
0
Zj

2
1
0

Cj-Zj

45

70
X2
12

0
S1

0
S2

0
S3

RHSV

j = bj/xj (aij)

720

720/12 =60

6
1

0
0
0

1
0
0

0
1
0

300
75
0

300/6 =50
75/1 = 75

0
70

Entering variable
c. Develop the subsequent tableaus
Identify the entering variable
Identify the leaving variable

Mathematics for Management (MGMT 121)

Leaving
variable

Chapter III: Introduction to Linear Programming

Sol/n Cj
basis
S1
X2
S3

0
70
0
Zj
Cj-Zj

45
X1

70
X2

0
S1

0
S2

0
S3

RHSV

j = bj/xj (aij)

5
1/3

0
1
1

1
0
0

-2
1/6
-1/6

0
0
1

120
50
25

120/5 = 24
50/. 333 =150
25/.666 = 75

70
0

0
0

70/6
-70/6

0
0

3500

0
S2
-2/5
3/10
1/10
3
-3

0
S3
0
0
1
0
0

2/3
70/3
65/3

19

Leaving
variable

Entering variable

Sol/n Cj
basis
X1
45
X2
70
S3
0
Zj
Cj-Zj

45
X1
1
0
0
45
0

70
X2
0
1
0
70
0

0
S1
1/5
-1/15
-2/15
13/3
-13/3

RHSV
24
42
9
4020

j = bj/xj (aij)

Optimal solutions: X1 = 24 units

X2 = 42 units
S3 = 9 engines
Z = Birr 4020
Interpretation: The Company is advised to produce 24 units of push type
mowers and 42 units of self-propelled mowers so as to realize
a profit of Birr 4020. In doing so the company would be left
with unused resource of 9 engines which can be used for other
purposes.
3. A firm produces products A, B, and C, each of which passes through assembly
and inspection departments. The number of person hours required by a unit of
each product in each department is given in the following table.
Person hours per unit of product
Product
Product
Product
A
B
C
Assembly 2
4
2
Inspection 3
2
1
During a given week, the assembly and inspection departments have available at
most 1500 and 1200 person-hours, respectively. if the unit profits for products A,
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

20

B, and C are Birr 50, Birr 40, and Birr 60, respectively, determine the number of
units of each product that should be produced in order to maximize the total
profit and satisfy the constraints of the problem.
Answer: 0 unit of product A, 0 unit of product B, 750 units of product C, unused
inspection time of 450 hours, and a maximum profit, Z ,of Birr 45,000.
4. The state chairman of a political party must allocate an advertising budget of birr
3,000,000 among three media: radio, television, and newspapers. The expected
number of votes gained per birr spent on each advertising medium is given
below.
Expected votes per Birr spent
Radio Television Newspapers
3
5
2
Since these data are valid with in the limited amounts spent on each medium, the
chairman has imposed the following restrictions:
No more than Birr 500,000 may be spent on television ads.
No more than Birr 1,200,000 may be spent on radio ads.
No more than Birr 2,400,000 may be spent on television and newspaper
ads combined.
How much should be spent on each medium in order to maximize the expected
number of votes gained?
Answer: Birr 500,000 should be spent on radio ads.
Birr 1,200,000 should be spent on television ads.
Birr 1,200,000 should be spent on newspaper ads.
Slack in the budget constraint is Birr 100,000.
Z = 9,900,000 is the maximum expected number of votes gained.
Some special Issues in LP
1.

Unbounded solutions
A solution is unbounded if the objective function can be improved without limit.
The solution is unbounded if there are no positive ratios in determining the
leaving variable. A negative ratio means that increasing a basic variable would
increase resources! A zero ratio means that increasing a basic variable would not
use any resources. This condition generally arises because the problem is
incorrectly formulated. For example, if the objective function is stated as

Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

21

maximization when it should be a minimization, if a constraint is stated when

it should be, or vice versa.
2.

Multiple optimal solutions

The same maximum value of the objective function might be possible with a
number of different combinations of values of the decision variables. This occurs
because the objective function is parallel to a binding constraint. With simplex
method this condition can be detected by examining the Cj Zj row of the final
tableau. If a zero appears in the column of a non-basic variable (i.e., a variable
that is not in solution), it can be concluded that an alternate solution exists.
E.g. Z = 60X1 + 30X2
4X1 + 10X2 100
2X1 + X2 22
3X1 + 3X2 39
X1, X2 0
The other optimal corner point can be determined by entering the non-basic
variable with the C - Z equal to zero and, then, finding the leaving variable in the
usual way.

3.

Degeneracy
In the process of developing the next simplex tableau for a tableau that is not
optimal, the leaving variable must be identified. This is normally done by
computing the ratios of values in the quantity column and the corresponding
row values in the entering variable column, and selecting the variable whose row
has the smallest non-negative ratio. Such an occurrence is referred to degeneracy,
because it is theoretically possible for subsequent solutions to cycle (i.e., to return
to previous solutions). There are ways of dealing with ties in a specific fashion;
however, it will usually suffice to simply select one row (variable) arbitrarily and
proceed with the computations.

Limitations of linear programming

1.
In linear programming uncertainty is not allowed, i.e., LP methods are
applicable only when values for costs, constraints, etc. are known, but in real life
such factors may be unknown.
2.
According to the LP problem, the solution variables can have any value,
whereas sometimes it happens that some of the variables can have only integral
values. For example, in finding how may machines to be produced; only integral
values of decision variables are meaningful. Except when the variables have large
Mathematics for Management (MGMT 121)

Chapter III: Introduction to Linear Programming

22

values, rounding the solution to the nearest integer will not yield an optimal
solution. Such situations justify the use of Integer Programming.
3.
Many times, it is not possible to express both the objective function and
constraints in linear form.

Mathematics for Management (MGMT 121)