Homework From The Class

HOMEWORK 8
Homework from the Class
From the graph, we can see that this problem is infeasible.

The dual of the problem;
From the graph, we can see that dual of the problem is infeasible also.
1
HOMEWORK 8
Homework from the Book Ch-5
5.3
Standard Form
Iteration 0
Z
s1
0
s2
0
s3
0
RHS
0
s1
s2
s3
1
0
0
0
1
0
0
0
1
7
3
8
Calculating zj-cj for the non-basic variables:

zj-cj
-3
x1
] [ ]
most negative zj-cj,

Entering Variable
x2
] [ ]
-2
x3
] [ ]
-1
x4
] [ ]
-1
Calculating updated a of the entering variable:
] [ ]
[ ]
HOMEWORK 8
s1
0
s2
0
s3
0
RHS
0
x1
-3
MRT
s1
s2
s3
1
0
0
0
1
0
0
0
1
7
3
8
8
2
1
7/8
1 1/2
8
Iteration 1
Z
s1
3/8
s2
0
s3
0
RHS
2 5/8
x1
0
x1
s2
s3
1/8
- 1/4
- 1/8
0
1
0
0
0
1
7/8
1 1/4
7 1/8
1
0
0

zj-cj
s1
] [ ]
x2
] [ ]
x3
] [ ]
x4
] [ ]

Entering Variable
[ ]
[
s1 Leaving
HOMEWORK 8
s1
3/8
s2
0
s3
0
RHS
2 5/8
x2
- 7/8
MRT
x1
s2
s3
1/8
- 1/4
- 1/8
0
1
0
0
0
1
7/8
1 1/4
7 1/8
3/8
1/4
29/8
2 1/3
5
2
Iteration 2
Z
s1
1/3
s2
0
s3
1/4
RHS
4 1/3
x2
0
x1
s2
x2
1/7
- 1/4
0
0
1
0
- 1/9
0
2/7
1/7
3/4
2
0
0
1

zj-cj
s1
] [ ]
s3
] [ ]
x3
] [ ]
x4
] [ ]

Entering Variable
[ ]
[
s3 Leaving
HOMEWORK 8
s1
1/3
s2
0
s3
1/4
RHS
4 1/3
x4
- 1/6
MRT
x1
s2
x2
1/7
- 1/4
0
0
1
0
- 1/9
0
2/7
1/7
3/4
2
0
4 3/4
5/9
1/6
3 4/7
s1
1/3
s2
0
s3
1/4
RHS
4 3/8
x4
0
x1
x4
x2
1/7
0
0
0
1/5
- 1/9
- 1/9
0
2/7
1/7
1/6
1 7/8
0
1
0

zj-cj
s1
] [ ]
s3
] [ ]
x3
] [ ]
s2
] [ ]
Since all zj-cj values are non-negative we have reached to optimality.

Optimal Feasible Solution is as follow:
Z
x1
x2
x3
x4
s1
s2
s3
4 3/8
1/7
1 7/8
0
1/6
0
0
0
s2 Leaving
HOMEWORK 8
5.7
Decision Variables
Xij: Amount of car type i (i=1,2) shipped in month j (j=1,2,3).
Objective Function
Min Z= 450x11+35*12*x12+35*16*x22+40*12*x13+40*16*x23
Min Z= 450x11+420x12+560 x22+ 480x13+640x23
Constraints
Capacity Constraints
1- X11200
2- 12X12+16x224500
3- 12X13+16x236000
Demand Constraints
1234-
X11+x12250
x22200
X11+x12+x13=400
X22+x23=500
All xij0
HOMEWORK 8
x11
x12
x22
x13
x23
s4
s5
s1
s2
s3
a1
a2
a3
a4
RHS
-450
-420
-560
-480
-640
-1000000
-1000000
-1000000
-1000000
s1
200
s2
12
16
4500
s3
12
16
6000
a1
-1
250
a2
-1
200
a3
400
a4
500
x11
x12
x22
x13
x23
s4
s5
s1
s2
s3
a1
a2
a3
a4
RHS
999550
999580
-560
-480
-640
-1000000
-1000000
-1000000
-1000000
2,5E+08
x11
x12
x22
x13
x23
s4
s5
s1
s2
s3
a1
a2
a3
a4
RHS
999550
999580
999440
-480
-640
-1000000
-1000000
-1000000
-1000000
4,5E+08
x11
x12
x22
x13
x23
s4
s5
s1
s2
s3
a1
a2
a3
a4
RHS
1999550
1999580
999440
999520
-640
-1000000
-1000000
-1000000
8,5E+08
x11
x12
x22
x13
x23
s4
s5
s1
s2
s3
a1
a2
a3
a4
RHS
1999550
1999580
1999440
999520
999360
-1000000
-1000000
1,35E+09
HOMEWORK 8
Iteration 0
Z
s1
0
s2
0
s3
0
a1
0
a2
0
a3
0
a4
0
RHS
1,35E+09
s1
s2
s3
a1
a2
a3
a4
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
200
4500
6000
250
200
400
500

zj-cj
x11
]
[ ]
x12
x22
x13
The most positive zj-cj,

Entering Variable
HOMEWORK 8
x23
s4
s5
] [
Iteration 1
Z
s1
0
s2
0
s3
0
a1
0
a2
0
a3
0
a4
0
RHS
1,35E+09
x12
1999580
s1
s2
s3
a1
a2
a3
a4
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
200
4500
6000
250
200
400
500
0
12
0
1
0
1
0
MRT
375
250
400
Leaving Var.=a1
HOMEWORK 8
s1
0
s2
0
s3
0
a1
-1999580
a2
0
a3
0
a4
0
RHS
8,5E+08
x12
0
s1
s2
s3
x12
a2
a3
a4
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
-12
0
1
0
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
200
1500
6000
250
200
150
500
0
0
0
1
0
0
0

zj-cj
x11
]
[ ]
a1
]
[ ]
x22
x13

Entering Variable
10
HOMEWORK 8
x23
s4
s5
] [
Iteration 2
Z
s1
0
s2
0
s3
0
a1
-1999580
a2
0
a3
0
a4
0
RHS
8,5E+08
x22
1999440
s1
s2
s3
x12
a2
a3
a4
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
-12
0
1
0
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
200
1500
6000
250
200
150
500
0
16
0
0
1
0
1
11
MRT
93,75
200
500
Leaving Var.=s2
HOMEWORK 8
s1
0
s2
-124965
s3
0
a1
-500000
a2
0
a3
0
a4
0
RHS
6,63E+08
x22
0
s1
x22
s3
x12
a2
a3
a4
1
0
0
0
0
0
0
0
0,0625
0
0
-0,0625
0
-0,0625
0
0
1
0
0
0
0
0
-0,75
0
1
0,75
-1
0,75
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
200
93,75
6000
250
106,25
150
406,25
0
1
0
0
0
0
0

zj-cj
x11

Entering Variable
[ ]
a1
]
[ ]
s2
]
[ ]
x13
]
[
12
HOMEWORK 8
x23
]
[
s4
s5
] [ ]
Iteration 3
s1
s2
s3
a1
a2
a3
a4
RHS
x11
-124965
-500000
6,63E+08
1499550
MRT
s1
x22
s3
x12
a2
a3
a4
1
0
0
0
0
0
0
0
0,0625
0
0
-0,0625
0
-0,0625
0
0
1
0
0
0
0
0
-0,75
0
1
0,75
-1
0,75
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
200
93,75
6000
250
106,25
150
406,25
1
-0,75
0
1
0,75
0
0,75
200
13
250
141,7
541,7
Leaving Var.=a2
HOMEWORK 8
s1
0
s2
-2,5
s3
0
a1
-1999550
a2
-1999400
a3
0
a4
0
RHS
4,5E+08
x11
0
s1
x22
s3
x12
x11
a3
a4
1
0
0
0
0
0
0
0,083333
0
0
0,083333
-0,08333
0
0
0
0
1
0
0
0
0
-1
0
0
0
1
-1
0
-1,33333
1
0
-1,33333
1,333333
0
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
58,33333
200
6000
108,3333
141,6667
150
300
0
0
0
0
1
0
0

zj-cj
a2
]
[ ]
a1
]
[ ]
s2
]
[ ]
x13
]
[
14
HOMEWORK 8
x23
]
[
s4
s5

Entering Variable
] [
Iteration 4
Z
s1
0
s2
-2,5
s3
0
a1
-1999550
a2
-1999400
a3
0
a4
0
RHS
4,5E+08
s4
999550
s1
x22
s3
x12
x11
a3
a4
1
0
0
0
0
0
0
0,083333
0
0
0,083333
-0,08333
0
0
0
0
1
0
0
0
0
-1
0
0
0
1
-1
0
-1,33333
1
0
-1,33333
1,333333
0
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
58,33333
200
6000
108,3333
141,6667
150
300
1
0
0
0
-1
1
0
15
MRT
58,33
150
Leaving Var.=s1
HOMEWORK 8
s1
-999550
s2
-83298,3
s3
0
a1
-1000000
a2
-666667
a3
0
a4
0
RHS
3,92E+08
s4
0
s4
x22
s3
x12
x11
a3
a4
1
0
0
0
1
-1
0
0,083333
0
0
0,083333
0
-0,08333
0
0
0
1
0
0
0
0
-1
0
0
0
0
0
0
-1,33333
1
0
-1,33333
0
1,333333
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
58,33333
200
6000
108,3333
200
91,66667
300
1
0
0
0
0
0
0

zj-cj
a2
]
[ ]
a1
]
[ ]
s2
]
[ ]
x13
The most
positive zj-cj,
Entering
Variable
]
[
16
HOMEWORK 8
x23
]
[
s1
]
[ ]
s5
]
[
] [
Iteration 5
Z
s1
-999550
s2
-83298,3
s3
0
a1
-1000000
a2
-666667
a3
0
a4
0
RHS
3,92E+08
x13
999520
s4
x22
s3
x12
x11
a3
a4
1
0
0
0
1
-1
0
0,083333
0
0
0,083333
0
-0,08333
0
0
0
1
0
0
0
0
-1
0
0
0
0
0
0
-1,33333
1
0
-1,33333
0
1,333333
-1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
58,33333
200
6000
108,3333
200
91,66667
300
0
0
12
0
0
1
0
17
MRT
500
91,67 Leaving Var.=a3
HOMEWORK 8
s1
-30
s2
-5
s3
0
a1
-1000000
a2
-1999360
a3
-999520
a4
0
RHS
3E+08
x13
0
s4
x22
s3
x12
x11
x13
a4
1
0
12
0
1
-1
0
0,083333
0
1
0,083333
0
-0,08333
0
0
0
1
0
0
0
0
-1
0
0
0
0
0
0
-1,33333
1
-16
-1,33333
0
1,333333
-1
0
0
-12
0
0
1
0
0
0
0
0
0
0
1
58,33333
200
4900
108,3333
200
91,66667
300
0
0
0
0
0
1
0

zj-cj
a2
]
[ ]
a1
]
[ ]
s2
]
[ ]
a3
]
[ ]
18
HOMEWORK 8
x23
The most
positive zj-cj,
Entering
Variable
]
[
s1
]
[ ]
s5
]
[
] [
Iteration 6
s1
s2
s3
a1
a2
-30
-5
-1000000
s4
x22
s3
x12
x11
x13
a4
1
0
12
0
1
-1
0
0,083333
0
1
0,083333
0
-0,08333
0
0
0
1
0
0
0
0
-1
0
0
0
0
0
0
a4
RHS
X23
-1999360
a3
999520
3E+08
999360
-1,33333
1
-16
-1,33333
0
1,333333
-1
0
0
-12
0
0
1
0
0
0
0
0
0
0
1
58,33333
200
4900
108,3333
200
91,66667
300
0
0
16
0
0
0
1
19
MRT
306,25
300
Leaving Var.=a4
HOMEWORK 8
s1
s2
s3
a1
a2
a3
a4
RHS
x23
-30
-5
-1000000
-1000000
-999520
-999360
483500
s4
x22
s3
x12
x11
x13
x23
1
0
12
0
1
-1
0
0,083333
0
1
0,083333
0
-0,08333
0
0
0
1
0
0
0
0
-1
0
0
0
0
0
0
-1,33333
1
0
-1,33333
0
1,333333
-1
0
0
-12
0
0
1
0
0
0
-16
0
0
0
1
58,33333
200
100
108,3333
200
91,66667
300
0
0
0
0
0
0
1

zj-cj
a2
]
[ ]
a1
]
[ ]
s2
]
[ ]
a3
]
[ ]
20
HOMEWORK 8
a4
]
[ ]
s1
]
[ ]
s5
]
[
Since all the zj-cj for the non-basic variables are non-positive we have reached the optimality.
Optimal feasible solution is as follows:
Z
483500
x11
x12
x13
x22
x23
s3
s4
s1
s2
200
108,3333333
91,66666667
200
300
100
58,33333333
0
0
21
HOMEWORK 8
5.13
Standard Form
x1
-2
x2
-1
x3
-3
s1
0
s2
0
s3
0
RHS
0
MRT=BottleNeck2
s1
s2
s3
3
-1
0
1
1
1
1
0
2
1
0
0
0
1
0
0
0
1
12
4
8
12
4
MRT=BottleNeck2
Bottle Neck 1 4
Bottle Neck 2 4
Minimum of BN1 and BN2 is equal= 4 so I chose to go with MRT.
x1
-2
x2
1/2
x3
0
s1
0
s2
0
s3
1 1/2
RHS
12
s1
s2
x3
3
-1
0
1/2
1
1/2
0
0
1
1
0
0
0
1
0
- 1/2
0
1/2
8
4
4
Bottle Neck 1 3
Bottle Neck 2 2,67
Bottle Neck 3 0
Minimum of BN1, BN2, BN3 = BN3, 0
Updating
22
2,67
HOMEWORK 8
Z
s1
s2
x1
-2
x2
-1
3
-1
0
1
1
1
s1
0
s2
0
s3
0
RHS
12
-1
0
-2
1
0
0
0
1
0
0
0
1
8
4
0
s2
0
s3
0
RHS
17 1/3
MRT=BottleNeck2
0
1
0
0
0
1
2 2/3
6 2/3
0
8
5
0
s2
0
s3
1/3
RHS
17 1/3
0
1
0
- 1/3
-1 1/3
1
2 2/3
6 2/3
0
MRT=BottleNeck2
2,67
Bottle Neck 1 3
Bottle Neck 2 2,67
Minimum of BN1, BN2 = BN2; 2,67
Z
x1
s2
x1
0
x2
- 1/3
2 1/3
s1
2/3
1
0
0
1/3
1 1/3
1
- 1/3
- 1/3
-2
1/3
1/3
0
Bottle Neck 1 6
Bottle Neck 2 0
Bottle Neck 3 4
Minimum of BN1, BN2 and BN3 = BN2; 0 so
leaves.
x1
0
x2
0
1 2/3
s1
2/3
x1
s2
x2
1
0
0
0
0
1
1/3
2 1/3
-2
1/3
1/3
0
We have reached optimality;

Z
x1
x2
17 1/3
2 2/3
0
x3
s1
s2
s3
4
0
6 2/3
0
23

Homework From The Class

Uploaded by

Copyright:

Available Formats

Homework From The Class

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Homework From The Class

Uploaded by

Copyright:

Available Formats

HOMEWORK 8

Homework from the Class

From the graph, we can see that this problem is infeasible.

Calculating zj-cj for the non-basic variables:

most negative zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

most negative zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

most negative zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

Since all zj-cj values are non-negative we have reached to optimality.

Calculating zj-cj for the non-basic variables:

The most positive zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

The most positive zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

The most positive zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

The most positive zj-cj,

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

Calculating updated a of the entering variable:

91,67 Leaving Var.=a3

Calculating zj-cj for the non-basic variables:

Calculating updated a of the entering variable:

Calculating zj-cj for the non-basic variables:

We have reached optimality;

You might also like