NEW ABYSSINIA COLLEGE

DEPARTMENT OF BUSINESS MANAGEMENT

INDIVIDUAL ASSIGNMENT FOR THE COURSE OPERATIONS RESEARCH

Prepared by :kalkidan Ayehu

ID: 0276/11

Section:05/1

Submitted to:
 NEW ABYSSINIA COLLEGE

DEPARTMENT OF BUSINESS MANAGEMENT

INDIVIDUAL ASSIGNMENT FOR THE COURSE OPERATIONS RESEARCH

1.State and explain the special cases of solving linear programming problems using
Graphic methods
o Multiple optimal solution
o Degeneracy
o Redundant constraint
o Infeasibility

I.Multiple optimal solution

First of all the graphical solution procedure is one of the methods of solving two variables
linear programming problems

The multiple optimal solution is 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 optional value at more than one solution point for
this reason they are called multiple optimal .

Example :-

The information given below is for the products A and B.

_____________________________________________________________________

Machine hours per week Maximum available

Department Product A Product B per week

_____________________________________________________________________

Cutting 3 6 900

Assembly 1 1 200

Profit per unit Birr 8 Birr 16

_____________________________________________________________________

Assume that the company has a marketing constraint on selling products B and therefore
it can sale a maximum of 125 units of this product.
 Required:

a. Formulate the LPP of this problem?

b. Find the optimal solution?

Solution: Let X1 =The Number of units’ f product A produced per week

X2 = The number of units f product B produced per week

The LPP Model of the problem is:

Max. Z=8 X 1 +16 X 2

Subjectto :
3 X 1 +6 X 2 ≤900
X 1 +X 2 ≤200
X 2 ≤125
X 1 , X 2 ≥0

X2 X2=0

(0, 200) X 1 +X 2 ≤200

X2=125 Marketing equation
(0,150) C (50, 125)
B (0, 125)
D (100,100) Cutting: 3X1+6X2=900
FR
X1=0

A (0, 0) X1
(200, 0) (300, 0)

Corners Coordinates Maximize Z=8 X1 + 16X2

A (0, 0) 0

B (0, 125) 2000

C (50, 125) 2400

D (100, 100) 2400

E (200, 100) 1600

Interpretation:

Both C and D are optimal solutions. Any point on the line segment CD will also lead to the
same optimal solution.

==>Multiple optimal solutions provide more choices for management to reach their
objectives.

II. Degeneracy

Degeneracy is occurred when the number of occupied cells contains is less than ( m+n-1 ) is
such case the current solution can not be improved because it is not possible to draw a
closed path for every occupied cell, also the values dual variables ui & vj which are used to
test the optimally can not be computed, Thus we need to remove the degeneracy during the
solution during initial and intermediate

III. Redundant Constraint

Redundant constraint is when the upper bound inflate on the value of the RHS of the
constraint during sensitivity analysis.

IV.Infeasible Solution

A solution is called feasible if it satisfies all the constraints and 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. Let see an example for Infeasible solution.

Example:

Maximize Z=20X1+30X2

Subject to:

2X1+X2< 40

4X1+X2< 60
 X1 > 30 and X1, X2 > 0

Solution:

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.
2.Simplex methods
 Tie for leaving variable
 Tie for entering variable
 Degeneracy
 Unboundedness
 Multiple optimal solution

Simplex method 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.

I. Tie for leaving variable

Tie for leaving 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”.

II. Tie for entering variable

-In order to break this tie the selection for the key column ( entering variable ) can be made
arbitrary. However, the number of solution can be minimized by adopting the following
rules.

- If there is a tie between two decision variables, then the selection can be made arbitrary.

-if there is a tie between a decision variable and a slack (or surplus) variable then select the
decision variable to enter into basis first.

-if there is a tie between slack or surplus variable, then selection can be made arbitrary.

III. Degeneracy

Degeneracy is a solution to the system of equations is termed as degeneracy if one or more

of the basic variables become equal to zero.
IV. Unboundedness

In maximization LPP if Ci – Zi > 0 ( Ci – Zi ) < 0 , for a minimization case for a column

not in the basis and

All entries in this column are negative then for determining key row, we have to calculate
minimum ratio corresponding to each basic variable have negative or zero value in the
denominator.

Negative value in denominator can not be considered as it would indicate the entry of a
none basic variable in the basis with a negative value (an infeasible solution will occur). A
zero value in the denominator would result a value of (+ ∞), The implies that the entering
variable could be increased indefinitely with any of the current basic variables being
removed the basis.

Let see an example.

Let’s solve the following LP problem

Maximize Z= 3 x 1+5 x 2

Subject to x 1−2 x2 ≤ 6

x 1 ≤ 10

x2 ≥ 1

x 1∧x 2 ≥ 0

add slack s1, s2 and surplus s 3∧artificial A1 , and we solve by the simplex method, using
tableau representation.

Maximize Z= 3 x 1+5 x 2+0 s1 +0 s 2 +−MA 1

Subject to x 1−2 x2 + s1=6

x 1 ≤ s 2=10

x 2−s3 + A 1=1

x 1 , x 2 , s1 , s 2 , s 3∧ A 1 ≥ 0
The initial solution to this problem is presented below

Cj 3 5 0 0 0 -M RHS Min
ratio
BV x1 x2 s1 s2 s3 A1

0 s1 1 -2 1 0 0 0 6 ___

0 s2 1 0 0 1 0 0 10 ___

-M A1 0 1 0 0 -1 1 1 1

Zj 0 -M 0 0 M -M 48

C j−Z j 3 5+M 0 0 -M 0

Variable X2 enter in to the basis and variable A1 leaves the basis

Cj 3 5 0 0 0 -M RHS Min
ratio
BV x1 x2 s1 s2 s3 A1

0 s1 1 -2 1 0 0 0 6 ___

0 s2 1 0 0 1 0 0 10 ___

-M A1 0 1 0 0 -1 1 1 1

Zj 0 -M 0 0 M -M -M

C j−Z j 3 5+M 0 0 -M 0
 Second table

Cj 3 5 0 0 0 -M RHS Min
ratio
BV x1 x2 s1 s2 s3 A1

0 s1 1 0 1 0 -2 2 6 ___

0 s2 1 0 0 1 0 0 10 ___

5 x2 0 1 0 0 -1 1 1 1

Zj 0 5 0 0 -5 5 5

C j−Z j 3 0 0 0 5 -M-5

Variable s3 should inter to the basis but it may be noted that coefficient in the S3 column ar
all negative or zero. This indicates that S3 cannot be entered in to the basis. However, the
value of S3 can be increased infinitely without removing any one of the basic variable.

Infeasible solution

In final simplex table if at least one artificial variable appear with a positive value, no
feasible solution exists, because it is not possible to remove such an artificial variable from
the basis using the simplex algorithm.

Example solving the following LPP

Max Z =6 x 1+ 4 x 2

Subject to: x 1+ x2 ≤5

x2 ≥ 8

x 1∧x 2 ≥

By adding slack, surplus and artificial variable, the LPP becomes

Max Z =6 x 1+ 4 x 2+0 s1 +0 s 2- MA 1
Subject to: x 1+ x2 + s1=¿

x 2 + s2 + A1 =8

x 1 , x 2 , s1 , s 2∧A 1 ≥ 0

The second table of the solution shows

Cj 6 4 0 0 -M RHS

BV x1 x2 s1 s2 A1

4 x2 1 1 1 0 0 5

- A1 -1 0 -1 -1 1 3
M
Zj 4+M 4 4+M M -M 20-3M

C j−Z j 2-M 0 -4- -M 0

M

Since the C j−Z j ≤ 0 the solution is optimal. But the solution not feasible for the given
problem since it has X1=0, X2=5 (recall that in the second constraint X2 ≥ 8). The fact that
artificial variable A1 =3 is in the solution also indicates that the final solution violates the
second constraint (X2 ≥ 8) by 3 unites.

V. Multiple optimal solution

-if non basic element (variable) corresponding to which Ci – Zi = 0 the problem have
multiple optimal solution.

Let see an example

As before, we add slacks, and we solve by the Simplex method, using tableau
representation.

Max Z =6 x 1+ 4 x 2

Subject to: 2 x1 +3 x 2 ≤ 30

3 x 1+2 x 2 ≤ 24

x 1+ x2 ≥3

x 1∧x 2 ≥ 0
Write it in standard form

As before, we add slacks s1, s2 and surplus s 3∧artificial A1 , and we solve by the simplex
method, using tableau representation.

Max Z =6 x 1+ 4 x 2+0 s1 +0 s 2- MA 1

Subject to: 2 x1 +3 x 2+ s 1=30

3 x 1+2 x 2 + s2 =24

x 1+ x2 + A1 =3

x 1 , x 2 , s1 , s 2 , s 3 + A1 ≥0

The optimal solution for this LP problem is presented in the following table

Cj 6 4 0 0 0 RHS

BV x1 x2 s1 s2 s3

0 s1 0 5/3 1 -2/3 0 14

0 s3 0 - 0 1/3 1 5
1/3
6 x1 1 2/3 0 1/3 0 8

Zj 6 4 0 2 0 48

C j−Z j 0 0 0 -2 0

The optimal solution is x1=8, x2=0, s1=14, and s3= 5 and max Z=48
But the C j−Z j row shows a value zero corresponding to a non basic variable X2. Thus an
alternative optimal solution can also be obtained by entering variable X2 in to the basis and
removing S1 from the basis.

Alternative solution

Cj 6 4 0 0 0 RHS

BV x1 x2 s1 s2 s3

0 x2 0 1 3/5 -2/3 0 42/5

0 s3 0 0 1/5 1/5 1 39/5

6 x1 1 0 -2/5 3/5 0 12/5

Zj 6 4 0 2 0 48

C j−Z j 0 0 0 -2 0

The optimal solution is x1=12/5, x2=42/5, s1=0, and s3= 39/5 and max Z=48
3. Assignment model
It is a special case of transportation problem in which the number of sources and
destinations are the same and the objective is to assign the given job (tasks ) to most
appropriate machine ( person ) so as to optimize the objective function like minimizing cost
or maximizing profit.

The modeling of assignment a rise because available resources such as men, machine etc
have varying degree of efficiency for performing different activities there fore cost profit or
time of performing the different activities is different Thus, the problem is “how the
assignment is made so as to optimize the given objective”.

There are some assumption and solution methods for assignment modals. It is obviously
calculated on the principles of reducing the given cost matrix to a matrix of opportunity
costs.
4. Transportation problems
I. Unbalanced transportation route

- For a feasible solution to exit it is necessary that the total supply must equal total demand
unbalanced case may be of two types Demand > supply or Supply > demand.

Let see case 1 (demand more than supply ) “Demand > supply ”

If total demand exceeds total supply a dummy row (called a dummy supply center)
can be added to the transportation table to account for the excess demand. The unit
transportation cost for the cells in the dummy row is set equal to zero.

Case 2 (Supply more than demand)”supply > demand”

If total supply exceed total demand, an additional column (called dummy demand
center ) can be added to the transportation table to absorb the excess supply. The
unity transportation cost for these cells in the column is set equal to zero because
these represent product of items that are not being made and being not sent.