X1 X2 X3 Y1 Y2 Y3 Y4

6 0 8 1 0 1 1
5 7 3 0 0 0 0 54
3 4 2 0 0 0 -1000 -966 <=
4 6 2 0 0 0 1000 1040 <=
0 0 0 1 1 1 0 2 <=
1 0 0 -7 0 0 0 -1 <=
0 1 0 0 -5 0 0 0 <=
0 0 1 0 0 -9 0 -1 <=
 30
1040
2
0
0
0
 Max Z = 2X1 + 20X2 - 10X3
S.T 2X1 + 20X2 + 4X3 <= 15
6X1 + 20X2 + 4X3 = 20
X1,X2,X3 >= 0

Max Z - 2X1 - 20X2 + 10X3 + 1000A1 = 0

S.T 2X1 + 20X2 + 4X3 + S1 = 15
6X1 + 20X2 + 4X3 + A1 = 20
X1,X2,X3,S1,A1>= 0

BASIC X1 X2 X3 S1 A1 SOLUTION
Z -2 -20 10 0 1000 0
S1 2 20 4 1 0 15
A1 6 20 4 0 1 20

BASIC X1 X2 X3 S1 A1 SOLUTION
Z -6002 -20020 -3990 0 0 -20000
S1 2 20 4 1 0 15
A1 6 20 4 0 1 20

BASIC X1 X2 X3 S1 A1 SOLUTION
Z -6002 -20020 -3990 0 0 -20000
S1 2 20 4 1 0 15
A1 6 20 4 0 1 20

BASIC X1 X2 X3 S1 A1 SOLUTION RATIO

Z -6002 -20020 -3990 0 0 -20000
S1 2 20 4 1 0 15 0.75
A1 6 20 4 0 1 20 1

BASIC X1 X2 X3 S1 A1 SOLUTION RATIO

Z -4000 0 14 1001 0 -4985
X2 0.1 1 0.2 0.05 0 0.75 7.5
A1 4 0 0 -1 1 5 1.25

BASIC X1 X2 X3 S1 A1 SOLUTION RATIO

Z 0 0 14 1 1000 15
X2 0 1 1/5 1/9 0 5/8
X1 1 0 0 -0.25 0.25 1 1/4

X1 = 5/4 = 1 + 1/4
X2 = 5/8
MAX Z = 15
MAX{ f1,f2} = Max {5/8,1/4} = 5/8
 X1 = 5/4 = 1 + 1/4
X2 = 5/8
MAX Z = 15
MAX{ f1,f2} = Max {5/8,1/4} = 5/8
Source row
5/8 = 0X1 + 1X2 + 1/5*X3 + 3/40*S1
1/5*X3 + 3/40*S1 >= 5/8 Fractional cut constraint
-1/5*X3 - 3/40*S1 <= -5/8
-1/5*X3 - 3/40*S1 + G1 = -5/8

BASIC X1 X2 X3 S1 A1 G1 SOLUTION
Z 0 0 14 1 0 15
X2 0 1 0.2 0.075 0 0.625
X1 1 0 0 -0.25 0 1.25
G1 0 0 -0.2 -0.075 1 -0.625

BASIC X1 X2 X3 S1 A1 G1 SOLUTION
Z 0 0 14 1 0 15
X2 0 1 0.2 0.075 0 0.625
X1 1 0 0 -0.25 0 1.25
G1 0 0 -0.2 -0.075 1 -0.625
Ratio #DIV/0! #DIV/0! 70 13.33333 #DIV/0! 0

BASIC X1 X2 X3 S1 A1 G1 SOLUTION
Z 0 0 11 1/3 0 13 1/3 6 2/3
X2 0 1 0 0 1 0
X1 1 0 2/3 0 -3 1/3 3 1/3
S1 -0 -0 2 2/3 1 -13 1/3 8 1/3
Ratio

X1 = 10/3 = 3+1/3
S1 = 25/3 = 8+1/3
MAX Z = 20/3
MAX{ f1,f2} = Max {1/3,1/3} = 1/3
source row
25/3 = 0X1 + 0X2 + 8/3*X3 + S1 - 40/3*G1
(8+1/3)= 0X1 + 0X2 + (2+2/3)*X3 + S1 + (-14+2/3)*G1

Corresponding Fractional cut constraint

2/3*X3 + 2/3*G1 >= 1/3
- 2/3*X3 - 2/3*G1 <= -1/3

- 2/3*X3 - 2/3*G1 + G2 = -1/3

Corresponding Fractional cut constraint
2/3*X3 + 2/3*G1 >= 1/3
- 2/3*X3 - 2/3*G1 <= -1/3

- 2/3*X3 - 2/3*G1 + G2 = -1/3

BASIC X1 X2 X3 S1 A1 G1 G2 SOLUTION
Z 0 0 11 1/3 0 13 1/3 0 6 2/3
X2 0 1 0 0 1 0 0
X1 1 0 2/3 0 -3 1/3 0 3 1/3
S1 0 0 2 2/3 1 -13 1/3 0 8 1/3
G2 0 0 - 2/3 0 - 2/3 1 - 1/3
RATIO #DIV/0! #DIV/0! 17 #DIV/0! 20 0

BASIC X1 X2 X3 S1 A1 G1 G2 SOLUTION
Z 0 0 0 0 2 17 1
X2 0 1 0 0 1 0 0
X1 1 0 0 0 -4 1 3
S1 0 0 0 1 -16 4 7
X3 -0 -0 1 -0 1 -1 1/2 1/2

source row
1/2 = 1X3 + G1 -3/2*G2
1/2 = 1X3 + G1 +(-2+1/2)*G2
Corresponding Fractional cut constraint

1/2*G2 >= 1/2

-1/2*G2 <= -1/2
-1/2*G2 + G3 = -1/2

BASIC X1 X2 X3 S1 A1 G1 G2 G3 SOLUTION
Z 0 0 0 0 2 17 0 1
X2 0 1 0 0 1 0 0 0
X1 1 0 0 0 -4 1 0 3
S1 0 0 0 1 -16 4 0 7
X3 0 0 1 0 1 -1.5 0 0.5
G3 0 0 0 0 0 -0.5 1 -0.5
RATIO #DIV/0! #DIV/0! #DIV/0! #DIV/0! #DIV/0! 34 0

BASIC X1 X2 X3 S1 A1 G1 G2 G3 SOLUTION
Z 0 0 0 0 2 0 34 -16
X2 0 1 0 0 1 0 0 0
X1 1 0 0 0 -4 0 2 2
S1 0 0 0 1 -16 0 8 3
X3 0 0 1 0 1 0 -3 2
G2 0 0 0 0 0 1 -2 1
SOLUTION
SOLUTION
 Max Z = X1 + X2
S.T 3X1 + 2X2 <= 5
X2 <= 2
X1,X2 >= 0 & are integers

Basic X1 X2 S1 S2 Solution
Z -1 -1 0 0 0
S1 3 2 1 0 5
S2 0 1 0 1 2

Basic X1 X2 S1 S2 Solution RATIO

Z -1 -1 0 0 0
S1 3 2 1 0 5 2.5
S2 0 1 0 1 2 2

Basic X1 X2 S1 S2 Solution RATIO

Z -1 0 0 1 2
S1 3 0 1 -2 1 0.333333
X2 0 1 0 1 2 #DIV/0!

Basic X1 X2 S1 S2 Solution
Z 0 0 1/3 1/3 2 1/3
X1 1 0 1/3 - 2/3 1/3
X2 0 1 0 1 2

1/3 = X1 + 1/3*S1 - 2/3*S2 Source row

rearrange in to integer and positive fraction coefficients
1/3 = X1 + 1/3*S1 -(1 - 1/3)S2
introduce Fractional cut constraint
1/3*S1 +1/3*S2 >= 1/3
-1/3*S1 - 1/3*S2 <= -1/3
Introducing the Gomorian slack
-1/3*S1 - 1/3*S2 + G1 = -1/3
-1/3*S1 - 1/3*S2 + G1 = -1/3

Basic X1 X2 S1 S2 G1 Solution
Z 0 0 1/3 1/3 0 2 1/3
X1 1 0 1/3 - 2/3 0 1/3
X2 0 1 0 1 0 2
G1 0 0 - 1/3 - 1/3 1 - 1/3

Basic X1 X2 S1 S2 G1 Solution
Z 0 0 1/3 1/3 0 2 1/3
X1 1 0 1/3 - 2/3 0 1/3
X2 0 1 0 1 0 2
G1 0 0 - 1/3 - 1/3 1 - 1/3
Ratio #DIV/0! #DIV/0! 1 1 0

Basic X1 X2 S1 S2 G1 Solution
Z 0 0 0 0 1 2
X1 1 0 0 -1 1 0
X2 0 1 0 1 0 2
S1 -0 -0 1 1 -3 1
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X1,X2>=0

Max Z = X1 +4X2
S.T 2X1 + 4X2 + S1 =7
5X1 + 3X2 + S2 = 15
X1,X2,S1,S2>=0

Basic X1 X2 S1 S2 Solution
Z -1 -4 0 0 0
S1 2 4 1 0 7
S2 5 3 0 1 15

Basic X1 X2 S1 S2 Solution Ratio

Z -1 -4 0 0 0
S1 2 4 1 0 7 1.75
S2 5 3 0 1 15 5

Basic X1 X2 S1 S2 Solution
Z 1 0 1 0 7
X2 0.5 1 0.25 0 1 3/4
S2 3.5 0 -0.75 1 9 3/4

Optimal and Feasible solution

X2 = 1 + 3/4 = 7/4
force X2, X2 <= 1 and X2 >= 2
Sub problem 01
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1,X2>=0

Sub problem 02
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 >= 2
X1,X2>=0
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 >= 2
X1,X2>=0

Sub problem 01
Basic X1 X2 S1 S2 S3 Solution
Max-Z -1 -4 0 0 0 0
S1 2 4 1 0 0 7
S2 5 3 0 1 0 15
S3 0 1 0 0 1 1

Basic X1 X2 S1 S2 S3 Solution Ratio

Max-Z -1 -4 0 0 0 0
S1 2 4 1 0 0 7 1.75
S2 5 3 0 1 0 15 5
S3 0 1 0 0 1 1 1

Basic X1 X2 S1 S2 S3 Solution Ratio

Max-Z -1 0 0 0 4 4
S1 2 0 1 0 -4 3 1.5
S2 5 0 0 1 -3 12 2.4
X2 0 1 0 0 1 1 #DIV/0!

Basic X1 X2 S1 S2 S3 Solution Ratio

Max-Z 0 0 0.5 0 2 5.5
X1 1 0 0.5 0 -2 1.5
S2 0 0 -2.5 1 7 4.5
X2 0 1 0 0 1 1

Sub problem 02
Basic X1 X2 S1 S2 S4 A1 Solution
Max-Z -1 -4 0 0 0 1000 0
S1 2 4 1 0 0 0 7
S2 5 3 0 1 0 0 15
A1 0 1 0 0 -1 1 2

Basic X1 X2 S1 S2 S4 A1 Solution
Max-Z -1 -1004 0 0 1000 0 -2000
S1 2 4 1 0 0 0 7
S2 5 3 0 1 0 0 15
A1 0 1 0 0 -1 1 2
Basic X1 X2 S1 S2 S4 A1 Solution Ratio
Max-Z -1 -1004 0 0 1000 0 -2000
S1 2 4 1 0 0 0 7 1.75
S2 5 3 0 1 0 0 15 5
A1 0 1 0 0 -1 1 2 2

Basic X1 X2 S1 S2 S4 A1 Solution
Max-Z 501 0 251 0 1000 0 -243
X2 0.5 1 0.25 0 0 0 1.75
S2 3.5 0 -0.75 1 0 0 9.75
A1 -0.5 0 -0.25 0 -1 1 0.25

Optimal and feasible tabulation was appeared but Artifical variable is a

Basic variable, it indicates another infeasible situation. so that Sub
Problem 2 doesn't contain feasible solution
Sub problem 03
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1 <= 1
 Sub problem 03
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1 <= 1
X1,X2>=0

Sub problem 03
Basic X1 X2 S1 S2 S3
Max-Z -1 -4 0 0 0
S1 2 4 1 0 0
S2 5 3 0 1 0
S3 0 1 0 0 1
S4 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z -1 -4 0 0 0
S1 2 4 1 0 0
S2 5 3 0 1 0
S3 0 1 0 0 1
S4 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z -1 0 0 0 4
S1 2 0 1 0 -4
X1<=1 S2 5 0 0 1 -3
X1>=2 X2 0 1 0 0 1
S4 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z 0 0 0 0 4
S1 0 0 1 0 -4
S2 0 0 0 1 -3
X2 0 1 0 0 1
X1 1 0 0 0 0

Sub problem 04
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1 >= 2
X1,X2>=0
 Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1 >= 2
X1,X2>=0

Sub problem 04
Basic X1 X2 S1 S2 S3
Max-Z -1 -4 0 0 0
S1 2 4 1 0 0
S2 5 3 0 1 0
S3 0 1 0 0 1
A1 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z -1001 -4 0 0 0
S1 2 4 1 0 0
S2 5 3 0 1 0
S3 0 1 0 0 1
A1 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z -1001 -4 0 0 0
S1 2 4 1 0 0
S2 5 3 0 1 0
S3 0 1 0 0 1
A1 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z 0 -4 0 0 0
S1 0 4 1 0 0
S2 0 3 0 1 0
S3 0 1 0 0 1
X1 1 0 0 0 0

Basic X1 X2 S1 S2 S3
Max-Z 0 0 1 0 0
X2 0 1 0.25 0 0
S2 0 0 -0.75 1 0
S3 0 0 -0.25 0 1
X1 1 0 0 0 0
 Sub problem 05
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1 >= 2
X2 <=0
X1,X2>=0

Sub problem 04
Basic X1 X2 S1 S2 S3 S4 S5 A1
Max-Z -1 -4 0 0 0 0 0 1000
S1 2 4 1 0 0 0 0 0
S2 5 3 0 1 0 0 0 0
S3 0 1 0 0 1 0 0 0
A1 1 0 0 0 0 -1 0 1
S5 0 1 0 0 0 0 1 0

Basic X1 X2 S1 S2 S3 S4 S5 A1
Max-Z -1001 -4 0 0 0 1000 0 0
S1 2 4 1 0 0 0 0 0
S2 5 3 0 1 0 0 0 0
S3 0 1 0 0 1 0 0 0
A1 1 0 0 0 0 -1 0 1
S5 0 1 0 0 0 0 1 0

Basic X1 X2 S1 S2 S3 S4 S5 A1
Max-Z -1001 -4 0 0 0 1000 0 0
S1 2 4 1 0 0 0 0 0
S2 5 3 0 1 0 0 0 0
S3 0 1 0 0 1 0 0 0
A1 1 0 0 0 0 -1 0 1
S5 0 1 0 0 0 0 1 0

Basic X1 X2 S1 S2 S3 S4 S5 A1
Max-Z 0 -4 0 0 0 -1 0 1001
S1 0 4 1 0 0 2 0 -2
S2 0 3 0 1 0 5 0 -5
S3 0 1 0 0 1 0 0 0
X1 1 0 0 0 0 -1 0 1
S5 0 1 0 0 0 0 1 0
Basic X1 X2 S1 S2 S3 S4 S5 A1
Max-Z 0 0 0 0 0 -1 4 1001
S1 0 0 1 0 0 2 -4 -2
S2 0 0 0 1 0 5 -3 -5
S3 0 0 0 0 1 0 -1 0
X1 1 0 0 0 0 -1 0 1
X2 0 1 0 0 0 0 1 0

Basic X1 X2 S1 S2 S3 S4 S5 A1
Max-Z 0 0 0 0.2 0 0 3.4 1000
S1 0 0 1 -0.4 0 0 -2.8 0
S4 0 0 0 0.2 0 1 -0.6 -1
S3 0 0 0 0 1 0 -1 0
X1 1 0 0 0.2 0 0 -0.6 0
X2 0 1 0 0 0 0 1 0

Feasible, optimal and

decision variables are
integers
Max z = 3
X1 = 3
X2 = 0
 X1<=1

Sub Problem 3
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <=1
X1<=1
X1,X2>=0
Max Z = 5, X1=1, X2=1
The solution is feasible, optimum and
 Sub Problem 3
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <=1
X1<=1
X1,X2>=0
Max Z = 5, X1=1, X2=1
The solution is feasible, optimum and

Best available Optimal inte

S4 Solution
0 0
0 7
0 15
0 1
1 1

S4 Solution Ratio
0 0
0 7 1.75
0 15 5
0 1 1
1 1 #DIV/0!

S4 Solution Ratio
0 4
0 3 1.5
0 12 2.4
0 1 #DIV/0!
1 1 1

S4 Solution Feasible, optimal and

1 5 decision variables are
-2 1 integers
-5 7 Max z = 5
0 1 X1 = 1
1 1 X2 = 1
04
S4 A1 Solution
0 1000 0
0 0 7
0 0 15
0 0 1
-1 1 2

S4 A1 Solution
1000 0 -2000
0 0 7
0 0 15
0 0 1
-1 1 2

S4 A1 Solution Ratio
1000 0 -2000
0 0 7 3.5
0 0 15 3
0 0 1 #DIV/0!
-1 1 2 2

S4 A1 Solution Ratio
-1 1001 2
2 -2 3 0.75
5 -5 5 1.666667
0 0 1 1
-1 1 2 #DIV/0!

S4 A1 Solution
1 999 5
0.5 -0.5 0.75
3.5 -3.5 2.75
-0.5 0.5 0.25
-1 1 2
X2<=0 X2>=1

Sub problem 06
Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X2 <= 1
X1 >= 2
X2 >= 1
X1,X2>=0

Sub problem 04
Solution Basic X1 X2 S1 S2 S3 S4
0 Max-Z -1 -4 0 0 0 0
7 S1 2 4 1 0 0 0
15 S2 5 3 0 1 0 0
1 S3 0 1 0 0 1 0
2 A1 1 0 0 0 0 -1
0 A2 0 1 0 0 0 0

Solution Basic X1 X2 S1 S2 S3 S4
-2000 Max-Z -1001 -4 0 0 0 1000
7 S1 2 4 1 0 0 0
15 S2 5 3 0 1 0 0
1 S3 0 1 0 0 1 0
2 A1 1 0 0 0 0 -1
0 A2 0 1 0 0 0 0

Solution Ratio Basic X1 X2 S1 S2 S3 S4

-2000 Max-Z -1001 -1004 0 0 0 1000
7 3.5 S1 2 4 1 0 0 0
15 3 S2 5 3 0 1 0 0
1 #DIV/0! S3 0 1 0 0 1 0
2 2 A1 1 0 0 0 0 -1
0 #DIV/0! A2 0 1 0 0 0 0

Solution Ratio Basic X1 X2 S1 S2 S3 S4

2 Max-Z -1001 -1004 0 0 0 1000
3 0.75 S1 2 4 1 0 0 0
5 1.666667 S2 5 3 0 1 0 0
1 1 S3 0 1 0 0 1 0
2 #DIV/0! A1 1 0 0 0 0 -1
0 0 A2 0 1 0 0 0 0
Solution Ratio Basic X1 X2 S1 S2 S3 S4
2 Max-Z -1001 0 0 0 0 1000
3 1.5 S1 2 0 1 0 0 0
5 1 S2 5 0 0 1 0 0
1 #DIV/0! S3 0 0 0 0 1 0
2 -2 A1 1 0 0 0 0 -1
0 #DIV/0! X2 0 1 0 0 0 0

Solution Ratio Basic X1 X2 S1 S2 S3 S4

3 Max-Z -999 0 1 0 0 1000
1 S5 0.5 0 0.25 0 0 0
1 S2 3.5 0 -0.75 1 0 0
1 S3 -0.5 0 -0.25 0 1 0
3 A1 1 0 0 0 0 -1
0 X2 0.5 1 0.25 0 0 0
Ratio 1998 #DIV/0! 4 #DIV/0! 0 #DIV/0!

Basic X1 X2 S1 S2 S3 S4
Max-Z -1001 0 0 0 4 1000
S5 0 0 0 0 1 0
S2 5 0 0 1 -3 0
S1 2 0 1 0 -4 0
A1 1 0 0 0 0 -1
X2 0 1 0 0 1 0

Basic X1 X2 S1 S2 S3 S4
Max-Z 0 0 500.5 0 -1998 1000
S5 0 0 0 0 1 0
S2 0 0 -2.5 1 7 0
X1 1 0 0.5 0 -2 0
A1 0 0 -0.5 0 2 -1
X2 0 1 0 0 1 0

Basic X1 X2 S1 S2 S3 S4
Max-Z 0 0 1 0 0 1
S5 0 0 0.25 0 0 0.5
S2 0 0 -0.75 1 0 3.5
X1 1 0 0 0 0 -1
S3 0 0 -0.25 0 1 -0.5
X2 0 1 0.25 0 0 0.5
Ratio #DIV/0! #DIV/0! 4 #DIV/0! #DIV/0! 2

Basic X1 X2 S1 S2 S3 S4
 Max-Z 0 0 500.5 0 0 1000
A1 0 0 -0.5 0 0 -1
S2 0 0 -2.5 1 0 0
X1 1 0 0.5 0 0 0
S3 0 0 0 0 1 0
X2 0 1 0 0 0 0

Basic X1 X2 S1 S2 S3 S4
Max-Z 0 0 500.5 0 -998 1000
A1 0 0 -0.5 0 2 -1
S2 0 0 -2.5 1 7 0
X1 1 0 0.5 0 -2 0
A2 0 0 0 0 -1 0
X2 0 1 0 0 1 0

Finally this will converge to infeasible situation as Artificial variables are continuously appeare

Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15
X1,X2>=0
Max Z = 7, X1=0, X2=7/4
X2<=1,X2>=2

X2<=1 X2>=2

Sub Problem 1 Sub Problem 2

Max Z = X1 + 4X2 Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7 S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15 5X1 + 3X2 <= 15
X2 <=1 X2>=2
X1,X2>=0 X1,X2>=0
Max Z = 11/2, X1=3/2, X2=1 infeasible solution and Branch is closed
X1<=1,X1>=2

X1<=1 X1>=2

oblem 3
= X1 + 4X2 Sub Problem 4
2X1 + 4X2 <=7 Max Z = X1 + 4X2
5X1 + 3X2 <= 15 S.T 2X1 + 4X2 <=7
X2 <=1 5X1 + 3X2 <= 15
X1<=1 X2 <=1
X1,X2>=0 X1 >=2
Max Z = 5, X1=1, X2=1 X1,X2>=0
lution is feasible, optimum and integer Max Z = 5, X1=2, X2=3/4
oblem 3
= X1 + 4X2 Sub Problem 4
2X1 + 4X2 <=7 Max Z = X1 + 4X2
5X1 + 3X2 <= 15 S.T 2X1 + 4X2 <=7
X2 <=1 5X1 + 3X2 <= 15
X1<=1 X2 <=1
X1,X2>=0 X1 >=2
Max Z = 5, X1=1, X2=1 X1,X2>=0
lution is feasible, optimum and integer Max Z = 5, X1=2, X2=3/4
X2<=0,X2>=1

X2<=0 X2>=1

Sub Problem 5 Sub Problem 6

Max Z = X1 + 4X2 Max Z = X1 + 4X2
S.T 2X1 + 4X2 <=7 S.T 2X1 + 4X2 <=7
5X1 + 3X2 <= 15 5X1 + 3X2 <= 15
X2 <=1 X2 <=1
X1 >=2 X1 >=2
X2<=0 X2>=1
X1,X2>=0 X1,X2>=0
Max Z = 3, X1=3, X2=0 Infeasible solution
The solution is feasible, optimum and integer

available Optimal integer solution is

Sub Problem 3
Max Z = 5, X1=1, X2=1
04
S5 A1 A2 Solution
0 1000 1000 0
0 0 0 7
0 0 0 15
0 0 0 1
0 1 0 2
-1 0 1 1

S5 A1 A2 Solution
0 0 1000 -2000
0 0 0 7
0 0 0 15
0 0 0 1
0 1 0 2
-1 0 1 1

S5 A1 A2 Solution
1000 0 0 -3000
0 0 0 7
0 0 0 15
0 0 0 1
0 1 0 2
-1 0 1 1

S5 A1 A2 Solution Ratio
1000 0 0 -3000
0 0 0 7 1.75
0 0 0 15 5
0 0 0 1 1
0 1 0 2 #DIV/0!
-1 0 1 1 1
 S5 A1 A2 Solution Ratio
-4 0 1004 -1996
4 0 -4 3 0.75
3 0 -3 12 4
1 0 -1 0 0
0 1 0 2 #DIV/0!
-1 0 1 1 -1

S5 A1 A2 Solution
0 0 1000 -1993
1 0 -1 0.75
0 0 0 9.75
0 0 0 -0.75
0 1 0 2
0 0 0 1.75
#DIV/0! #DIV/0! #DIV/0! 2657.333

S5 A1 A2 Solution Ratio
0 0 1000 -1996
1 0 -1 0 #DIV/0!
0 0 0 12 2.4
0 0 0 3 1.5
0 1 0 2 2
0 0 0 1 #DIV/0!

S5 A1 A2 Solution Ratio
0 0 1000 -494.5
1 0 -1 0 0
0 0 0 4.5 0.642857
0 0 0 1.5 -0.75
0 1 0 0.5 0.25
0 0 0 1 1

S5 A1 A2 Solution
0 999 1000 5
1 -0.5 -1 -0.25
0 -3.5 0 2.75
0 1 0 2
0 0.5 0 0.25
0 -0.5 0 0.75
0 1998 1000

S5 A1 A2 Solution Ratio
 1998 0 -998 -494.5
-2 1 2 0.5 0.25
-7 0 7 4.5 0.642857
2 0 -2 1.5 -0.75
1 0 -1 0 0
-1 0 1 1 1

S5 A1 A2 Solution Ratio
1000 0 0 -494.5
0 1 0 0.5 0.25
0 0 0 4.5 0.642857
0 0 0 1.5 -0.75
-1 0 1 0 0
0 0 0 1 1

bles are continuously appeared as basic variables

nch is closed
5

tion