The document provides the steps to solve an optimization problem with decision variables x11, x12, x22, x13, and x23 using the simplex method. There are capacity and demand constraints. In iteration 0, x23 enters the basis. In iteration 1, a1 leaves and x12 enters. This process continues with s2 and x11 entering the basis in iterations 2 and 3 respectively. The optimal feasible solution is computed after 3 iterations.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as DOCX, PDF, TXT or read online from Scribd
The document provides the steps to solve an optimization problem with decision variables x11, x12, x22, x13, and x23 using the simplex method. There are capacity and demand constraints. In iteration 0, x23 enters the basis. In iteration 1, a1 leaves and x12 enters. This process continues with s2 and x11 entering the basis in iterations 2 and 3 respectively. The optimal feasible solution is computed after 3 iterations.
The document provides the steps to solve an optimization problem with decision variables x11, x12, x22, x13, and x23 using the simplex method. There are capacity and demand constraints. In iteration 0, x23 enters the basis. In iteration 1, a1 leaves and x12 enters. This process continues with s2 and x11 entering the basis in iterations 2 and 3 respectively. The optimal feasible solution is computed after 3 iterations.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as DOCX, PDF, TXT or read online from Scribd
The document provides the steps to solve an optimization problem with decision variables x11, x12, x22, x13, and x23 using the simplex method. There are capacity and demand constraints. In iteration 0, x23 enters the basis. In iteration 1, a1 leaves and x12 enters. This process continues with s2 and x11 entering the basis in iterations 2 and 3 respectively. The optimal feasible solution is computed after 3 iterations.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 23
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
Calculating zj-cj for the non-basic variables:
zj-cj s1
] [ ]
x2
] [ ]
x3
] [ ]
x4
] [ ]
most negative zj-cj,
Entering Variable
Calculating updated a of the 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
Calculating zj-cj for the non-basic variables:
zj-cj s1
] [ ]
s3
] [ ]
x3
] [ ]
x4
] [ ]
most negative zj-cj,
Entering Variable
Calculating updated a of the 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
Calculating zj-cj for the non-basic variables:
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
Calculating zj-cj for the non-basic variables:
zj-cj
x11
] [ ]
x12
x22
x13
The most positive zj-cj,
Entering Variable
HOMEWORK 8
x23
s4
s5
Calculating updated a of the entering variable:
] [
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
Calculating zj-cj for the non-basic variables:
zj-cj
x11
] [ ]
a1
] [ ]
x22
x13
The most positive zj-cj,
Entering Variable
10
HOMEWORK 8
x23
s4
s5
Calculating updated a of the entering variable:
] [
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
Calculating zj-cj for the non-basic variables:
zj-cj
x11
The most positive zj-cj,
Entering Variable
[ ]
a1
] [ ]
s2
] [ ]
x13
] [
12
HOMEWORK 8
x23
] [
s4
s5
Calculating updated a of the entering variable:
] [ ]
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
Calculating zj-cj for the non-basic variables:
zj-cj
a2
] [ ]
a1
] [ ]
s2
] [ ]
x13
] [
14
HOMEWORK 8
x23
] [
s4
s5
The most positive zj-cj,
Entering Variable
Calculating updated a of the 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
Calculating zj-cj for the non-basic variables:
zj-cj
a2
] [ ]
a1
] [ ]
s2
] [ ]
x13
The most positive zj-cj, Entering Variable
] [
16
HOMEWORK 8
x23
] [
s1
] [ ]
s5
] [
Calculating updated a of the entering variable:
] [
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
Calculating zj-cj for the non-basic variables:
zj-cj
a2
] [ ]
a1
] [ ]
s2
] [ ]
a3
] [ ]
18
HOMEWORK 8
x23
The most positive zj-cj, Entering Variable
] [
s1
] [ ]
s5
] [
Calculating updated a of the entering variable:
] [
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
Calculating zj-cj for the non-basic variables:
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
