LINEAR PROGRAMMING

INTRODUCTION TO LPP
Developed by Dantzing in 1940 primarily for solving military
logistics problem

LP: is a branch of mathematical programming which is designed

to solve optimization problems where all the constraints as well
as the objectives are expressed as linear function.

LP: is a mathematical process that has been developed to help

management in decision making involving the efficient allocation
of scarce resources to achieve a certain objective.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 2
CONT’D

LP: is a mathematical technique designed to aid managers in

allocating scarce resources (such as labor, capital, or energy)
among competing activities.

The linear programming technique can be said to have a linear

objective function that is to be optimized (either maximized or
minimized) subject to linear equality or inequality constraints
and sign restrictions on the variables

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 3

CONT’D
The term linear describes the proportionate relationship of two
or more variables. Thus, a given change in one variable will
always cause a resulting proportional change in another
variable.
LP is a technique for making decisions under certainty i.e.;
when all the courses of options available to an organization are
known and the objective of the firm along with its constraints are
quantified.
The applicability of the model in real life situation is enhanced
by the availability of user-friendly computer programs such as
LINDO, STORM, TORA, QSB+ etc

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 4

STRUCTURE OF LINEAR PROGRAMMING MODEL
The general structure of an LP model consists of the following
three basic components;
• Decision variables: which denote the available choices,
• The objective function: The objective function of each LP
problem is expressed in terms of decision variables to optimize
the criterion of optimality (also called measure-of-performance)
such as profit, cost, revenue, distance etc.
• The constraints: here are always certain limitations (or
constraints) on the use of resources, such as: labour, machine, raw
material, space, money, etc., that limit the degree to which an
objective can be achieved.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 5
CONT’D

LP is the analysis of problems in which a linear function

of a few variables is to be optimized (maximized or
minimized) when the variables are subject to several
constraints in the mathematical linear inequalities.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 6

ASSUMPTIONS OF AN LP MODEL
Certainty: In LP models, it is assumed that all its parameters such
as: availability of resources, profit/cost contribution per unit of
decision variable and consumption of resources per unit of
decision variable must be known and constant.
Additivity: The value of the objective function and the total
amount of each resource used, must be equal to the sum of the
respective individual contribution profit/cost of the decision
variables.
Linearity: The amount of each resource used and its contribution
to the profit/cost in objective function must be proportional to
the value of each decision variable.
Divisibility: The solution values of decision variables are allowed
to assume continuous values.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 7

ADVANTAGES OF USING LP
Following are certain advantages of using LP technique:
LP technique helps decision-makers to use their productive
resources effectively.
LP technique improves the quality of decisions i.e. objective and
less subjective.
LP technique helps to arrive at optimal solution of a decision
problem by considering constraints on the use of resources.
LP approach for solving decision problem highlight bottlenecks in
the production processes.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 8

LIMITATION OF LP
Limitations associated LP technique are as follows:
LP assumes linear relationships among decision variables.
While solving an LP model there is no guarantee that decision
variables will get integer value.
The LP model does not take into consideration the effect of time
and uncertainty.
Parameters in the model are assumed to be constant but in real-
life situations, they are frequently neither known nor constant.
LP deals with only single objective, whereas in real-life situations
a decision problem may have conflicting and multiple objectives.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 9

APPLICATION AREAS OF LINEAR PROGRAMMING
• Agriculture
• Military
• Production (product mix, production planning, assembly line
balancing,)
• Financial Management (portfolio selection, profit planning)
• Marketing Management (media selection, traveling salesman
problem, physical distribution)
• Personnel Management (staff problem, determination of
equitable salary, job evaluation and selection etc)

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 10

GUIDELINES ON LP MODEL FORMULATION

Steps in Formulating a LP Model

Step 1: Identify the decision variables

Step 2: Identify the problem data i.e. constants, and

parameters associated with decision variables

Step 3: Formulate the constraints

Step 4: Formulate the objective function

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 11

EXAMPLE
Azaria Electronics Company has contracted with an advertising
firm to determine the types and amount of advertising it should
have for its stores. The three types of advertising available are
social media ads, Google ads, and billboard advertising. The
retail store desires to know the number of each type of
advertisement it should purchase to maximize exposure. It is
estimated that each ad and commercial will reach the following
potential audience and cost the following amount.
Type of Exposure Cost in birr
Advertisement (people/ad or commercial

Social media ads 20, 000 15, 000

Google Ads 12, 000 8, 000
Billboard advertising 9, 000 4, 000
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 12
CONT’D
The following resource constraints exist:
•There is a budget limit of Birr 100,000 available for
advertising.
•The social media has enough time available for four
commercials.
• The google ads has enough time available for ten commercials.
• The billboard advertising has enough space available for
seven ads.
•The advertising agency has time and staff to produce at most a
total of fifteen commercials ads.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 13

CONT’D

Decision Variables
This model consists of three decision variables representing
the number of each type of advertising produced:
X1 = the number of social media ads
X2 = the number of google ads
X3 = the number of billboard advertising

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 14

CONT’D
The Objective Function
Maximize Z = 20000 X1 + 12000 X2 + 9000 X3

The complete LP model for this problem is summarized as

Maximize Z = 20000 X1 + 12000 X2 + 9000 X3
S.t. 15000 X1 + 8000 X2 + 4000 X3 ≤ 100000
X1 ≤ 4
X2 ≤ 10
X3 ≤ 7
X1 + X2 + X3 ≤ 15
X1, X2, X3 ≥ 0
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 15
EXAMPLE 2
An electronic company is engaged in the production of two components C1
and C2 that are used in radio sets. Each unit of C1 costs the company Birr 5
in wages and Birr 5 in material, while each of C2 costs the company Birr 25
in wages and Birr 15 in material. The company sells both products on one
period credit terms, but the company’s labour and material expenses must
be paid in cash. The selling price of C1 is Birr 30 per unit and of C2 it is
Birr 70 per unit. Because of the company’s strong monopoly in these
components, it is assumed that the company can sell, at the prevailing prices,
as many units as it produces. The company’s production capacity is, however,
limited by two considerations. First, at the beginning of period 1, the
company has an initial balance of Birr 4,000 (cash plus bank credit plus
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. The
production of each C1 requires 3 hours of machine time and 2 hours of
assembly time, whereas the production of each C2 requires 2 hours of
machine time and 3 hours of assembly time. Formulate this problem as an LP
model so as to maximize the total profit to the company.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 16
METHODS FOR SOLVING LP

There are two types of finding a solution for Linear

programming problems.
• Graphic Solution and
• Simplex Method

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 17

GRAPHICAL SOLUTION METHODS OF LPP
While obtaining the optimal solution to the LPP by the graphical
method, the statement of the following theorems of linear
programming is used
•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.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 18

EXTREME POINT SOLUTION METHOD

Coordinates of all corner (or extreme) points of the feasible

region (space or area) are determined and then value of the
objective function at each of these points is computed and
compared.

The coordinates of an extreme point where the optimal

(maximum or minimum) value of the objective function is found
represent solution of the given LP problem.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 19

CONT’D
The steps of the method are summarized as follows:
Step 1 : Develop an LP model
Step 2 : Plot constraints on graph paper and decide the feasible
region
a) Replace the inequality sign in each constraint by an equality sign.
b) Draw these straight lines on the graph paper and decide each
time the area of feasible solutions according to the inequality sign
of the constraint.
c) The final shaded area is called the feasible region/solution space
of the given LP problem. Any point inside this region is called
feasible solution and this provides values that satisfy all the
constraints.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 20
CONT’D

•For "greater than" and "greater than or equal to" constraints, the
feasible region or the solution space is the area that lays above the
constraint lines.
•For" less than" &" less than or equal to" constraint, the feasible
region or the solution space is the area that lays below the
constraint lines.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 21

CONT’D
Step 3 : Examine 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

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 22

EXAMPLE
TEAM Ltd. Co. wishes to purchase a maximum of 3600 units of
two types of product, A & B which are available in the market.
Product A occupies a space of 3 cubic feet & cost Birr 9 whereas
B occupies a space of 1 cubic feet & cost Birr 13 per unit. The
budgetary constraints of the company do not allow spending
more than Birr 39,000. The total availability of space in the
company's is 6000 cubic feet. Profit margin of both product A &
B is Birr 3 & Birr 4 respectively. Formulate the above problem as
a linear programming model and solve it by using graphical
method. You are required to ascertain the best possible
combination of purchase of A & B so that the total profit is
maximized.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 23

CONT’D
The problem can be formulated as a linear programming model
as follows:
Let x1 = Number of units of product A &
x2 = Number of units of product B
Objective function, Max Z = 3x1+ 4x2
s.t. x1 + x2 ≤ 3600
3x1 + x2 ≤ 6000
9x1 + 13x2 ≤ 39000
X1 & X2 ≥ 0
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 24
CONT’D
X1

6000 ( Maximum unites constraint)

(Storage area constraint)

Number of unites of B

(Budgetary constraint)
3600

B
3000
A1

Feasible
region
O X1
(0, 0) C
3600 3900/9
2000

Number of unites of A

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 25

CONT’D
Step IV. Find the optimal solution by the corner point method.
At corner points (O, A, B, C), find the profit value from the
objective function. Those points which maximize the profit are the
optimal point.
Coordinates Objective function Value
Corner point
O (0,0) Z=0+0 0
A (0,3000) Z=0+4x3000 12,000
B (1300,2100) Z=3x1300 + 4 12,300
x2100
C (2000,0) 3 x 2000 + 0 6000

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 26

CONT’D

Result
The optimal solution is:
No of units of product A= 1300
No of units of product B= 2100
Total profit, = 12, 300 which is the maximum

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 27

EXAMPLE 2
Suppose that a machine shop has two different types of
machines; machine 1 and machine 2, which can be used to make
a single product. These machine vary in the amount of product
produced per hour, in the amount of labor used and in the cost
of operation.
Assume that at least a certain amount of product must be
produced and that we would like to utilize at least the regular
labor force. How much should we utilize each machine to utilize
total costs and still meets the requirement? The resource used,
the cost and the required hour is given in the following table.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 28

CONT’D

Formulation of the linear programming model and solve it by

using the graphic solution technique?
Result: the optimal solution is: X1 =2.5, X2=3.33 and Minimum
cost Z= 162.5
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 29
SPECIAL CASES IN GRAPHICS METHODS

The following are the major special cases in graphics

solution
✓ Alternative Optima
✓ Infeasible Solution
✓ Unbounded solution

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 30

ALTERNATIVE OPTIMAL SOLUTION
When the objective function is parallel to a binding constraint;
(a constraint that is satisfied in the equality sense by the optimal
solution), the objective function will assume the same optimal
value at more than one solution point, for this reason they are
called alternative optima.
Max Z= 2x1 + 4x2
S.t. x1 + 2x2 ≤ 5
x1 + x2 ≤ 4
x1, x2 ≥ 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 31

CONT’D
The above Figure demonstrates how alternative optima can
arise in LP model when the objective function is parallel to a
binding constraint. Any point on the line segment BC represents an
alternative optimum with the same objective value z = 10.
Mathematically, we can determine all the points (x1, x2) on the
line segment BC as a nonnegative weighted average of the
points B and C. That is, given 0 α 1 and

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 32

INFEASIBLE SOLUTION
A solution is called feasible if it satisfies all the constraints and
non-negativity condition. However, it is sometimes possible that
the constraints may be inconsistent so that there is no feasible
solution to the problem. Such a situation is called infeasibility.
Maximize Z=20X1+30X2
Subject to:
2X1+X2< 40
4X1+X2< 60
X1 > 30 and X1, X2 > 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 33

 CONT’D
X2 X1=0

(0, 60) X1=30

4X1+X2= 60
(0, 40)

2X1+X2= 40
X2=0
X1

(15, 0) (20, 0) (30, 0)

Note: -In the above graph, there is no common point in the shaded
area.
All constraints cannot be satisfied simultaneously and there is no
feasible solution to the problem.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 34
UNBOUNDED SOLUTION
When the value of decision variables in LP is permitted to
increase infinitely without violating the feasibility condition, then
the solution is said to be unbounded. Here, the objective function
value can also be increased infinitely. However, an unbounded
feasible region may yield some definite value of the objective
function.
Use the graphical method to solve the following LPP.
Maximize Z=3X1+4X2
Subject to:
X1-X2<-1==> -X1+X2 > 1 since the quantity solution is positive

X1+X2<0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 35

CONT’D

Maximize Z=3X1+2X2
Subject to:
X2
X1-X2<1
Unbounded
X1+X2≥3 A (0, 3)
Feasible Region
X1-X2=1
X1, X2 > 0
B (2, 1)
X1+X2=3

X1

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 36

 SIMPLEX METHOD
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 37
SIMPLEX METHOD/ALGORITHM
The applicability of the graphical method is very limited in
scope. This is due to the fact that it is quite simple to identity all
the corner points & then tests them for optimality-in the case of
a two-variable problem. As a result, the graphical method
cannot be always employed to solve the real-life practical
Linear Programming Problems (LPPs) which involve more than
two decision-variables.
Thus, simplex method(SM) is used to solve real-life problems with
more than two decision variables.
The Simplex method was developed by George Dantzig while
working for the US Air Force. It was first published in 1949.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 38
CONT’D
SM is an iterative or “step by step” method or repetitive
algebraic approach that moves automatically from one basic
feasible solution to another basic feasible solution improving the
situation each time until the optimal solution is reached at.
SM starts with a corner that is in the solution space/feasible
region and moves to another corner, the solution space
improving the value of the objective function each time until
optimal solution is reached.
The Simplex method provides a set of step-by-step instructions,
known as an algorithm, for solving an LP problem of any size.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 39

STANDARD FORMS OF LPPS
The use of SM to solve LPP requires that the problem be
converted into its standard form. The standard form of the LPP
should have the following characteristics:
▪All the constraints should be expressed as equations by adding slack or
surplus and/or artificial variables.
▪The right hand side of each constraint should be made non-negative; if it
is not, this should be done by multiplying both side of the resulting
constraint by -1.
▪The objective function should be of the maximization type.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 40

ADDITIONAL VARIABLES
▪ Slack variable(s)
▪ Surplus variable(-s), and
▪ Artificial variable(A)
The above additional variables are added in a given LPP to
convert it in to standard form for the following reasons:
• These variables allow as converting inequalities in to equalities,
there by converting the LPP in to a form that is amenable to
algebraic solution.
• These variables permit as to make a more comprehensive
economic interpretation of a final solution.
• Help us to get an initial feasible solution presented by the column
of the identity matrix.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 41

SUMMARY OF THE EXTRA VARIABLE

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 42

REMARK
• A slack variable represents unused resource (e.g. time on a
machine, labor hour, money, warehouse space etc ). Since
variable yields no profit, therefore such variable are added to
the original objective function with zero coefficients.
• A surplus variable represents amount by which solution values
exceed a resource. These variables are also called negative
slack variables. Surplus variables carry a zero coefficient in the
objective function.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 43

DEFINITIONS
Basis: is the set of variables present in the solution, have positive
non-zero value; these variables are also called basic variables.

Non-basic variables are those which are not in the ‘basis’ and
have zero-value.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 44

MAJOR STEPS TO SOLVE LPP USING SIMPLEX
METHOD
Step 1: Formulation of the mathematical model
• Formulate the LP model of the given problem.
• If the objective function is of minimization, then convert it into
equivalent maximization
• Check whether all the bi (i = 1, 2, . . . , m) values are positive. If any
one of them is negative, then multiply the corresponding constraint by –
1 in order to make bi > 0.
• Express the given LP problem in the standard form by adding
additional variables in constraints (as per requirement) and assign a
zero-cost coefficient to these variables in the objective function.
• Replace each unrestricted variable (if any) with the difference of the
two non-negative variables.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 45
CONT’D
Step 2: Set-up the initial solution
Write down the coefficients of all the variables in the LP problem in a
tabular form
After having set up the initial simplex table, locate the identity matrix
(contains all zeros except positive elements 1’s on the diagonal).
The columns of identity matrix represent the coefficients of slack
variables that have been added to the constraints.
The variables corresponding to the columns of the identity matrix are
called basic variables and the remaining ones are called non-basic
variables.
In general, if an LP model has n variables and m (< n) constraints, then
m variables would be basic and n – m variables non-basic.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 46
CONT’D
Cj raw values represent the cost (or profit) per unit associated with a
variable in the objective function
The column CB lists the coefficients of the current basic variables in
the objective function.
Numbers, aij in the columns under each variable are also called
substitution rates/exchange coefficients because these represent the
rate at which resource i (i = 1, 2, . . ., m) is consumed by each unit of
an activity j ( j = 1, 2, . . ., n).
The values Zj represent the amount by which the value of objective
function Z would be decreased or increased ) if one unit of the given
variable is added to the new solution.
Cj – Zj row values represent net profit or loss resulting from
introducing one unit of any variable into the ‘basis’ or solution mix.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 47
CONT’D
Step 3: Test for optimality
Step 4: Select the variable to enter the basis
Step 5: Test for feasibility (variable to leave the basis)
Step 6: Finding the new solution
Step 7: Repeat the procedure

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 48

MAXIMIZATION PROBLEM WITH ALL ≤
CONSTRAINTS
Convert the LP to Standard Form:
Convert the given problem into Standard maximization
problem i.e. minimization problem into a maximization one (by
multiplying the objective function by -1). All variables must be
non-negative. All right hand side values must be non-negative
(multiply both sides by -1, if needed). All constraints must be in
≤ form (except the non-negativity conditions). No strictly
equality or ≥ constraints are allowed.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 49

CONT’D
Convert all ≤ constraints to equalities by adding a different
slack variable for each one of them.
Construct the initial simplex tableau with all slack variables in
the Basic Variables(BV). The last row in the table contains the
coefficient of the objective function (row Cj)
Determine whether the current tableau is optimal. That is: if all
the right hand side values are non-negative (called the
feasibility condition). If all elements of the last row, that is Cj-Zj
rows are non-positive (called, the optimality condition)

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 50

CONT’D
If the current BASIC VRIABLES is not optimal, determine, which non
basic variable should become a basic variable and, which basic
variable should become a non-basic variable. To find the new BASIC
VRIABLES with the better objective function value, perform the
following tasks:

Identify the entering variable: the entering variable is the one with
the largest positive Cj-Zj value (in case of a tie, select the variable
that corresponds to the left most of the columns).

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 51

CONT’D
Identify the outgoing variable: the outgoing variable is the
one with smallest non-negative column ratio (to find the column
ratios, divide the RHS column by the entering variable column,
wherever possible). In case of a tie select the variable that
corresponds to the upper most of the tied rows.

Generate the new tableau

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 52

CONT’D

Check for optimality (for maximization models all values in the

C-Z row must be less than or equal to zero for the solution to
be optimal. If there is any positive value in the C-z row of the
table that is an indication that the solution is not optimal.
Hence, there is a need to iterate further by identifying the
leaving variable and entering variable using the techniques
discussed above.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 53

CONT’D
EXAMPLE EXERCISE
Max Z= 60X1 + 50 X2 Max Z = 40X1 + 35X2
S.t. S.t. 2X1 + 3X2 ≤ 60
4X1 + 10X2 ≤ 100 4X1 + 3X2 ≤ 96
2X1 + X2 ≤ 22 X1, X2 ≥ 0
3X1 + 3X2 ≤ 39 Solution: X1 = 18, X2 = 8, S1 &
S2= 0, Max Z= 1000
X1, X2 ≥ 0
Solution: X1 = 9, X2 = 4, S1=
24, S2 & S3= 0, Max Z= 740

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 54

EXERCISE
A firm produces three products A, B and C each of which
passes through three departments’ fabrication, finishing and
packaging. Each unit of product A requires 3, 4 and 2; a unit
product B requires 5, 4 and 4; while each unit of product C
requires 2, 4 and 5 hours respectively in the three departments.
Every day, 60 hours are available in the fabrication
department, 72 hours in the finishing department and 100
hours in the packaging departments. The unit contribution of
product A is birr 5, of product B is birr 10, and of product C is
birr 8.
Formulate the problem as an LPP and determine the number of
units of the product that should be made each day to maximize
contribution. Also determine if any capacity would remain
unutilized.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 55
SIMPLEX MAXIMIZATION WITH MIXED
CONSTRAINTS
Steps
• If any problem constraint has negative constraint on the right
side, multiply both by -1 to obtain a constraint with a non-
negative constraint (if the constraint is an inequality, this will
reverse the direction of the inequality).
• Introduce a slack variable in each ≤ constraints
• Introduce a surplus variable and an artificial variable in each
≥ constraints

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 56

CONT’D

• Introduce an artificial variable in each = constraints

Artificial variable do not represent any quantity relating to the
decision problem, they must be driven out of the system and
must not remain in the final solution. This can be ensured by
assigning an extremely high cost to them. Generally, a value M
is assigned to each artificial variable, where M represents a
number higher than any finite number big M method

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 57

CONT’D
➢ Assigning objective function coefficients for artificial
variables depends on whether the goal is to maximize or
minimize.
▪ In maximization problems, assigning a large negative
contribution (-M) will ensure that an artificial variable will not
appear in the optimal solution. In a minimization problem,
assigning a large positive cost (M) will have a similar effect.
➢ Form the simplex tableau for the modified problem and solve
using the simplex method

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 58

CONT’D
▪ List the variable in the order of; decision variable, slack
variable/surplus variable, and finally artificial variable.
▪ For basic variable column use artificial variables, and/or
slack variable, for the initial solution.
➢ Relate the solution of the modified problem to the original
problem.
▪ If the modified problem has no solution, the original problem
has no solution
▪ If any artificial variables are non-zero in the solution to the
modified problem, then the original problem has no solution

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 59

EXAMPLE
Max Z = 6X + 8Y
S.t.: Y≤4
X+Y=9
6X+ 2Y ≥ 24
X, Y ≥ 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 60

CONT’D
Standard form
Max Z = 6X + 8Y + 0S1 + 0S2 - MA1 – MA2
Subject to: Y+ S1 = 4
X+Y + A1 = 9
6X+ 2Y –S2 + A2 = 24
All variables ≥ 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 61

CONT’D
BV CBV X Y S1 S2 A1 A2 Quantity
6 8 0 0 -M -M

S1 0 0 1 1 0 0 0 4
A1 -M 1 1 0 0 1 0 9
A2 -M 6 2 0 -1 0 1 24

Z -7M -3M 0 M -M -M -33M

C-Z 6+ 7M 8+3M 0 -M 0 0

Note: once an artificial variable has left the basis, it has served
its purpose and can therefore be removed from the simplex
tableau. An artificial variable is never considered for re-entry
into the basis.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 62
CONT’D

BV CBV X Y S1 S3 A2 Quantity
6 8 0 0 -M

S1 0 0 1 1 0 0 4
A1 -M 0 2/3 0 1/6 1 5
X 6 1 1/3 0 -1/6 0 4

Z 6 2-2M/3 0 -1M/6 -1 -M 24 - 5M
C-Z 0 6+2M/3 0 1+ M/6 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 63

CONT’D

BV CBV X Y S1 S2 A1 Quantity
6 8 0 0 -M

Y 0 0 1 1 0 0 4
A1 -M 0 0 -2/3 1/6 1 7/3
X 6 1 0 -1/3 -1/6 0 8/3

Z 6 8 6 + 2M/3 -M/6 -1 -M 48 -7M/3

C-Z 0 0 -6-2M/3 1+ M/6 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 64

CONT’D
BV CBV X Y S1 S2 Quantity
6 8 0 0
Y 8 0 1 1 0 4
S2 0 0 0 -4 1 14
X 6 1 0 -1 0 5

Z 6 8 2 0 62
C-Z 0 0 -2 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 65

MINIMIZATION LINEAR PROGRAMMING
PROBLEMS
There are two methods for removing artificial variables from the
solution.
• Two-Phase Method
• Big-M Method or Method of Penalties
▪ Formulate the LPM, and convert it into a standard form by
introducing surplus and artificial variables. Assign a 0 and M
as coefficient for surplus and artificial variables respectively
in the objective function. M is considered a very large number
so as to finally drive out the artificial variable out of basic
solution.
▪ Set up the initial simplex tableau and initial solution
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 66
CONT’D
▪ Test for optimality of the solution. If all the entries of Cj – Zj
row are positive and zero, the solution is optimal.
▪ Determine the variable to enter the basic solution. Identify the
column with the largest number with negative sign in the Cj – Zj
row of the table.
▪ The same procedure, as in maximization case, is employed to
determine the departing variable. If an artificial variable goes
out of solution, discard it totally.
▪ Update the new solution. Evaluate the entries and repeat the
procedure until an optimal solution is obtained.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 67

EXAMPLE

Minimize Z=25x1 +30x2

Subject to:
20x1+15x2 > 100
2x1+ 3x2 > 15
x1, x2 >0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 68

CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 69

CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 70

CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 71

CONT’D

Cj – Zj ≥ 0 Optimal solution is reached

X1=5/2
X2=10/3 and Minimum Z=162.5
Note: As long as an “A” variable is available in the solution
variable column, the solution is infeasible.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 72

SPECIAL CASES
1. Multiple optimal solutions:
This condition can be detected by examining the C – Z 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 alternative solution exists.
Example
Max Z= 60X1 + 30 X2
Subject to:
4X1 + 10X2 ≤ 100
2X1 + X2 ≤ 22
3X1 + 3X2 ≤ 39
X1, X2 ≥ 0
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 73
CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 74

CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 75

CONT’D
2. Unbounded solution (problem):
➢ unbounded solution exists when all the ratio values (values of quantity
column divided by values in the pivot column) are negative or zero (no
positive value) while determining the leaving variable
3. Degeneracy solution:
➢ In the process of developing the next simplex tableau for a tableau that
is not optimal, the leaving variable must be identified. When there is a
tie for the lowest non-negative ratio (two equal values of leaving
variable) referred to as degeneracy.
4. Infeasibility solution:
➢ In the simplex approach, infeasibility can be recognized by the
presence of an artificial variable in a solution that appears optimal.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 76

 DUALITY AND POST
OPTIMALITY ANALYSIS

QADM COMPILED BY: HABTAMU E. (PHD) 4/5/2025 77

SENSITIVITY/POST-OPTIMALITY ANALYSIS
Sensitivity analysis involves an examination of the potential
impact of changes in any of the parameters of a problem. It
begins with the final simplex tableau. Its purpose is to explore
haw change in any of the parameters of a problem, such as:
▪ The coefficients of the constraints,

▪ The coefficient of the objective function, or

▪ The right hand side values would affect the solution

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 78

CONT’D
Even if the parameters of a problem are known with a high degree of
certainty, a decision maker might still want to use sensitivity analysis in
order to determine how changes in parameters would affect the final
solution. For example a manager may want to consider obtaining
additional amount of some scarce resource that might be available
and the manager wants to know the answers of the following question
▪ Will an increase in the right hand side of this constraint affect the
objective function?

▪ If so, how much of the resources can be used.

▪ Given the answer to the preceding question, what will be the revised
optimal solution?

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 79

CONT’D
Conversely, the decision maker might be facing a situation in
which the amount of a scarce resource available is less than
the original amount, in which case the issues would be.
▪ Will the decreased level of the resource have an
impact on the value of the objective function?

▪ If yes, how much of an impact will it have, and

▪ What will be the revised optimal solution

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 80

A CHANGE IN THE RIGHT HAND SIDE
QUANTITY OF A CONSTRAINT
▪ The 1st step in determining how a change in the right hand
side quantity of a constraint would influence the optimal
solution is to examine the shadow prices in the final simplex
tableau.
▪ It is a marginal value which indicates the impact that a one
unit change in the amount of a constraint would have on the
value of the objective function.
▪ More specifically, a shadow price reveals, the amount by
which the value of the objective function would increase if
the level of the constraint was increased by one unit.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 81

SHADOW PRICE

Shadow prices are values in the Z row of in the slack columns

of the final (optimal) simplex table.

It is a marginal value.

It shows the impact that a one unit change in the amount of

constraint would have on the value of the objective function

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 82

CONT’D
60 50 0 0 0 RHS
Basis c X1 X2 S1 S2 S3
S1 0 0 0 1 6 -5.3333 24
X1 60 1 0 0 1 -0.3333 9
X2 50 0 1 0 -1 002/3 4
z 60 50 0 10 40/3 740
C-Z 0 0 0 -10 -13.333

Shadow prices
Negative of Shadow
prices
4/5/2025 QADM 83
CONT’D
From the above table one can clearly see that:
• If resource one is increased by one unit, there would
be no effect on the profit.
• If the second resource is increased by one unit, profit
will increase by 10 birr and
• If the third resource is increased by one unit, profit
will increase by 40/3 birr.
shadow prices do not tell us by how much the level of
scarce resources can be increased and still have the
same impact per unit

4/5/2025 QADM 84
CONT’D
Resources with positive shadow prices are scarce goods
(binding constraints) and resources with zero shadow prices are
free goods (surplus resource).
At some point, the ability to use additional resources will
disappear because of the fixed amounts of the other
constraints.
We need to determine the range over which we can change the
right hand side quantities and still have the same shadow
prices.
This is called range of feasibility/ right hand range

4/5/2025 QADM 85
RANGE OF FEASIBILITY (RHS RANGE)
•Is the range over which we can change the right hand
side quantities/values and still have the same shadow
price.
•The key to computing the range of feasibility for the
constraint lies in each slack column of the final simplex
tableau.
•To compute the range of feasibility for each
constraint, the values in the quantity column must be
divided by the entries in the associated slack column
(substitution rate).

4/5/2025 QADM 86
CONT’D
For “≤” constraints
•Allowable decrease: the smallest positive ratio (right
hand side quantity divided by substitution rate), and
• Allowable increase: the negative ratio closest to zero
(the right hand side quantity divided by substitution
rate).
Lower Limit = bj-the smallest positive number in Q/Sj
column
Upper Limit = bj+ the negative ratio closest to zero
in Q/Sj column

4/5/2025 QADM 87
 CONT’D
For “≥” constraints
•Allowable decrease: the negative ratio closest to zero (the right
hand side quantity divided by substitution rate), and
•Allowable increase: The smallest positive ratio (right hand side
quantity divided by substitution rate)
Example find the range of feasibility for the microcomputer
problems
Lower Limit = bj - the negative ratio closest to zero in Q/ Sj
column
Upper Limit = bj+ The smallest positive ratio in Q/ Sj column

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 88

EXAMPLE
Max Z= 60X1 + 50 X2
Subject to
AT: 4X1 + 10X2 ≤ 100
IT : 2X1 + X2 ≤ 22
SS: 3X1 + 3X2 ≤ 39
NN: X1, X2 ≥ 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 89

CONT’D

Basic V Cj 60 50 0 0 0 Quantity
X1 X2 S1 S2 S3

S1 0 0 0 1 6 -16/3 24

X1 60 1 0 0 1 -1/3 9

X2 50 4
0 1 0 -1 2/3
Zi 60 50 0 10 40/3 740

Cj-Zi 0 0 0 -10 -40/3

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 90

CONT’D
The impact of RHSQ changes on the optimal solution:
▪ The values in the body of any final simplex tableau are
substitution rate.
▪ They indicate how much and in what direction a one unit change in
the column variable (RHSQ) will cause current quantity value to
change.
▪ For example, the value in the s3 column tells us the following
changes. A one unit increase in storage space will cause
• s1 (assembly slack) to decrease by 16/3 (5.33 unites),
• x1 to decrease by 1/3 (0.33 unites),
• x2 to increase by 2/3 (0.67 unites), and
• profit (Z) to increase by 40/3 (birr 13.33).

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 91

CONT’D
Example the manager in the microcomputer problem is
contemplating one of the two possible changes in the level of
storage constraints. One change would be an increase of 3
cubic feet in its level; the other would be an increase of 8
cubic feet in its level. Determine the revised solution for each
possible change.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 92

CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 93

A CHANGE IN THE OBJECTIVE FUNCTION
COEFFICIENT
It is useful to know how much the contribution of a given
decision variable to the objective function can change without
changing the optimal solution. The change may occur due to;
changed costs, new pricing policies, product or process design
changes etc.
A. A change in the non-basic variables
If there is a variable Cj, not participating in the optimal basis,
then, in order for the variable to be included in the optimal
solution, its coefficient in the objective function will have to
change from the existing Cj to a new level Cj(new).

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 94

CONT’D
The range of insignificance
➢ is the range over which Cj rates for non-basic variables can
vary without causing a change in the optimal solution mix
(variable) is called the range of insignificance.
➢ is the range over which a non-basic variables objective
function coefficient can change without that variable to enter
the solution mix.
➢ In a maximization problem if a variable is not currently in a
solution, its objective function coefficient would have to
increase by an amount that exceeds the Cj – Zj value for that
variable in the final tableau in order for it to end up (enter) as
a basic variable in the optimal solution.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 95
EXAMPLE
Given the following final simplex tableau, determine the range
over which the objective function coefficient of variable X3
could change without changing the optimal solution

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 96

B. A CHANGE IN THE BASIC DECISION
VARIABLES
The range of optimality:
▪ the range over which a basic decision variable
coefficient in the objective function can change
without changing the optimal solution mix. However,
this change will change only the optimal value of the
objective function.
▪ For both maximization and minimization problem the
range of optimality is calculated as follows:

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 97

CONT’D
The value in the Cj – Zj row must be divided by the
corresponding row values of the variable in equation.
This will result series of ratios. The smallest positive
ratio will indicate the amount of allowable increase
and the negative ratio closest to zero will indicate the
amount of allowable decrease
Allowable increase: The smallest positive number in the Cj - Zj
Xi
Allowable decrease: The negative ratio closest to zero in the
Cj - Zj
Xi
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 98
EXAMPLE
Determine the range of optimality for the coefficients of the
basic-decision variables.
Max Z = 5x1 +4.5x2 +x3
Subject to:
15 x1+15.8x2 < 150
5x1+6.4x2+15x3 < 77
2.8x2+11.8x3 < 36
x1, x2 , x3 > 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 99

CONT’D

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 100

CONT’D

Cj-Zi 0 -.842 0 -.311 -0.067 0

X1 1 1.053 0 .067 0 0
Ci-Zj/X1 1 -0.799 0 -4.64 Und. 0
X3 0 .067 1 -.022 .067 0
Ci-Zj/X3 0 -12.57 0 14.14 -4.64 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 101

DUALITY
• Every linear programming problem can have two forms; the
original formulation of a problem is referred to as its primal
form, and the other form is referred to as its dual form.
• The dual is kind of a mirror image of the primal because in
both its formulation and its solution the values of the dual are
flip flop version of the primal value.
• The solution to the primal contains the solution to the dual
problem, and vice versa.
• Analysis of the dual can enable a manager to evaluate the
marginal values of resources (constraints) and the potential
impact of a new product (the impact on the quantity and profit).

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 102

CONT’D
Duality
• The dual contains economic information useful to management
• Corresponding to every LPP, there is another LPP.
• The given problem is called the primal.
• The related problem to the given problem is known as the dual.
• The dual of a dual is the primal
• If the primal has optimal solution ,the dual will have optimal solution
• If the primal has no optimal solution, the dual will not have optimal
solution.
• Whether we follow the dual or primal system, the optimal solution
will remain equal.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 103

DUALITY ADVANTAGE
1) The dual form provides an alternative form
2) The dual reduces the computational difficulties associated
with some formulation
3) The dual provides an important economic interpretation
concerning the value of scarce resources used.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 104

CONT’D
Formulation of the dual
All the problems formulated in the proceeding can be classified
as primal problem. Because they were formulated directly from
the description of the problems but the dual is an alternative
formulation of the problem that requires the existence of the
primal.
Steps :
1. For the objective function
➢ If the primal is a maximization, the dual will be a minimization
➢ The right hand side value for each constraints will became the
coefficient of the objective function of the dual.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 105

CONT’D
2. For the constraints

•There will be one constraint for each primal decision variable.

Hence because the primal has two such variables, the dual will
have two constraints.

•The right hand side values of the dual constraints will equal the
primal objective function coefficient taken in order.

•The coefficient of the 1st primal constraint will became the 1st
coefficient in each of the dual constraint.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 106

 PRIMAL-DUAL RELATIONSHIP

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 107

EXAMPLE
Formulate the dual from the following primal
1. Min C= 40X1 + 44X2 + 48X3
Subject to;
X1 + 2X2 + 3X3 ≥ 20
4X1 + 4X2 + 4X3 ≥ 30
X1, X2, X3 ≥ 0
2. Max Z= 60X1 + 50 X2
Subject to;
4X1 + 10X2 ≤ 100
2X1 + X2 ≤ 22
3X1 + 3X2 ≤ 39
X1, X2 ≥ 0

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 108

 CONT’D
Formulation of the dual when the primal has mixed constraint:
➢ To change the direction of a constraint, multiply both sides of the constraint by -
1
➢ If a constraint is an equality, it must be replaced with two constraint one with
less than or equal to sign and the other with greater than or equal to sign. One
of these must be multiplied by -1 depending on whether the primal is a max or
a min problem.
Example; formulate the dual problem given the primal.
1. Max Z= 50X1 + 80 X2
Minimization C= 12X1 + 60X2 + 93X3
Subject to; Subject to;
3X1 + 5X2 ≤ 45 8X1 - X2 - 3X3 = 20
2X1 + 5X2 + 9X3 =35
4X1 + 2X2 ≥ 16 X1, X2, X3 ≥ 0
6X1 + 6X2 = 30
X1, X2 ≥ 0
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 109
COMPARISON OF THE PRIMAL AND THE DUAL
SIMPLEX SOLUTION

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 110

CONT’D
▪ There is a correspondence between variable of the primal
and the dual problems.
▪ The decision variable X1 in the primal corresponds to the
surplus variable S1 in the dual, while the variable X2
corresponds to S2.
▪ In a similar way the decision variable (real) Y1, Y2 and Y3 in
the dual corresponding to the slack variable S1, S2 and S3
respectively of the primal.
▪ The objective function values of both the problems are the
same. Thus, X1= 9, X2 = 4, Z = 60*9+50*4=740. Similarly,
Y1= 0, Y2= 10, Y3 = 40/3, Z= 100*0+22*10+39* 40/3
=740.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 111

CONT’D
▪ The values of the solution of the primal can be founded in
bottom row of the dual. i.e., Numerical value of each of the
variable in the optimal solution is equal to the value of its
corresponding variable in the dual contained in the C –Z row.
Thus, in the primal problem, X1 = 9, X2 = 4, and S1 = 24
where as in the dual Y1 = 24, S1= 9, S2 = 4 (in the C –Z row).
▪ Similarly, The solution quantities of the dual are equal to the
shadow price of the primal. the numerical values of each of
the variable in the optimal solution to the dual is equal to the
value of its corresponding variable in the primal, as contained
in the C – Z row of it. Thus, Y2 = 10, Y3 = 40/3, Y1 = 0 in the
dual and S2 = 10, S3 = 40/3, S1 = 0, in the primal.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 112

CROSS-REFERENCING PRIMAL AND DUAL
VALUES IN THE FINAL TABLEAU

Economical interpretation of the dual: analysis of the dual can be

enabling a manager to evaluate:
❖ the marginal value of the resource (constraint) and
❖ the potential impact of the new product.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 113
CONT’D
The marginal value of the resources:
•The value of the decision variable (Y1, Y2, Y3,...,Yn) in the dual
represents the marginal values of the resources in the primal.
• For example, suppose the microcomputer firm has been
approached by a representative of a department store chain
that wants the firm to make computers that will be sold under
the store’s brand name. The microcomputer firm has only a
limited capacity for producing computer and must decide
whether to produce its own computer or computers for the
department store. The manager of the microcomputer firm
would reason out in the following way.
•In order for the firm realistically to consider the store offer, the
amount of scarce resources that will be given up must produce a
return for the firm that is at least equal to the foregone profit.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 114
CONT’D
• Hence, giving up one unit model I will require that the value of
received by giving up 4 assembly hours + 2 inspection hours +
3 cubic feet of the storage space ≥ 60.
• By similar reasoning, giving up one unit of model II will require
that the value received by giving up 10 assembly hours + 1
inspection hours + 3 cubic feet of storage space ≥ 50.
Value received per Resources feed up Minimum profit
unit of; given required
Model I 4Y1 + 2Y2 + 3y3 Birr 60
Model II 10y1 + 1Y2 + 3y3 Birr 50

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 115

CONT’D
•Hence the constraints of the dual refer to the value of the
capacity (I.e., the scarce resource).
•The formulation indicates that in order to switch from making
units of model I and II to making computers for the store
department, the value received from that switch must be at least
equal to the profit forgone on the models.
•The variable Y1, Y2, and Y3 are the marginal values of scarce
resources Y1 (assembly time), Y2 (inspection time) and Y3 (storage
space).

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 116

CONT’D
•The department store would want to minimize the use of the
scarce resources, because the computer firm almost certainly
would base its charges on the amount of resource required.
Therefore, the objective function focuses on minimizing the use of
the scarce resources.
•Minimize C = 100Y1 + 22Y2 + 39y3, the marginal values of y2 is
10 and y3 is 40/3 in the quantity column, but the value of y1 is
0, primal did not completely used up all of the assembly
capacity.
•The optimal dual solutions always yield the same value of the
objective function as the primal. Interpretation is that the imputed
value of the resources that are required for the optimal solution
equals the amount of profit that the optimal solution would
produce.
05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 117
THE POTENTIAL IMPACT OF NEW
PRODUCTS (ADDING ANOTHER
VARIABLE)
The microcomputer firm is considering a third model that will yield
a profit of $70 per unit, and this will require 8 hours of the
assembly time, 4 hours of inspection time and 5 cubic feet of
storage per unit. What is the impact of this product on the current
solution?
Minimize C = 100Y1 + 22Y2 + 39y3
Subject to;
4Y1 + 2Y2 + 3Y3 ≥ 60
10Y1 + Y2 + 3Y3 ≥ 50
8Y1 + 4Y2 + 5Y3 ≥ 70, new product

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 118

CONT’D
•Therefore, the marginal value of the Y2 = 10, Y3 = 40/3, Y1 =
0, 8(0) + 4(10) + 5(40/3) ≥ 70, 106.7 ≥ 70
•This amount is greater than the new dual constraint, the original
solution remain optimal.
•Hence, the new variable X3 would not enter in to the solution. If
the dual constraint has not been satisfied, the new variable
would have come in to solution. The values of this approach is
that it is not necessary to rework the entire problem in order to
test the potential impact that adding a new decision variable
would have on the optimal solution.

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 119

 END

05/04/2025 QADM COMPILED BY: HABTAMU E. (PHD) 120