Linear Programming - Simplex
Operations research
Paweł Obszarski
1
x
1 + x2 + x3
=
6
3x1 + 2x2 + 2x3 = 13
2x1 + x2 + 2x3
= 10
2
The Standard Maximum Problem Find
X = [x1, x2, ..., xn]T
(1)
Subject to
a11x1 + a12x2+
. . .
+a1nxn ≤ a10
a21x1 + a22x2+
. . .
+a2nxn ≤ a20
(2)
. . .
am1x1 + am2x2+ . . . +amnxn ≤ am0
x1 ≥ 0, x2 ≥ 0 . . . xn ≥ 0
(3)
Maximize objective function
z = c1x1 + c2x2 + . . . + cnxn
(4)
3
THEOREM 7 Point P is a corner point of LP feasible solution if and only if it sharply satisfies n linearly independent inequalities.
4
x
1
x
Determine vector X =
2
. ∈ Rn that maximizes
..
xn
z = c1x1 + c2x2 + . . . + cnxn
Subject to:
a11x1 + a12x2 + . . . + a1nxn = a10
a21x1 + a22x2 + . . . + a2nxn = a20
...
...
. . .
...
...
am1x1 + am2x2 + . . . + amnxn = am0
x1 ≥ 0, . . . , xn ≥ 0
5
Standard Matrix Representation Find X ∈ Rn, subject to
A · X = A0
X ≥ 0n
where
z = C · X
gets its maximum.
Where
a
11
a12
. . .
a1n
0
a
0
A =
21
a22
. . .
a2n
.
, 0n = . , C = [c1, c2, . . . , cn]
..
...
. . .
...
..
am1 am2 . . . amn
0
6
Standard Vector Representation Find X ∈ Rn, that maximizes function z = C · X
subject to
A1x1 + A2x2 + . . . + Anxn = A0
X ≥ 0n
Where
a
1j
0
a
0
A
2j
j =
.
, 0n = . , C = [c1, c2, . . . , cn]
..
..
amj
0
7
THEOREM 6.
The most important theorem A vector x =
[x1, x2, ..., xn]T represents the coordinates of a feasible corner point if and only if in the linear combination A1x1 + A2x2 + ... + Anxn = A0
if Aj is an independent vector then xj > 0 (so if Aj is a dependent vector then xj = 0).
8
Standard Simplex Representation Find X ∈ Rn that maximizes the function z = c1x1 + c2x2 + . . . + cnxn
subject to:
a1,1x1 + a1,2x2 + . . . + a1,n−mxn−m + xn−m+1
= a1,0
a2,1x1 + a2,2x2 + . . . + a2,n−mxn−m
+ xn−m+2
= a2,0
...
...
. . .
...
. . .
...
am1x1 + am2x2 + . . . + am,n−mxn−m
+ xn = am,0
x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0, a1,0 ≥ 0, a2,0 ≥ 0, . . . , am,0 ≥ 0
9
Standard Simplex Representation - Example Find X = [x1, x2]T that maximizes
z = 4x1 + 6x2
subject to
6x1 + 8x2 ≤ 48
10x1 + 6x2 ≤ 60
5x1 + 15x2 ≤ 75
x1 ≥ 0, x2 ≥ 0
10
Standard Simplex Representation - Example Find X = [x1, x2, x3, x4, x5]T that maximizes z = 4x1 + 6x2 + 0x3 + 0x4 + 0x5
subject to
6x1 +
8x2 + x3
= 48
10x1 +
6x2
+ x4
= 60
5x1 + 15x2
+ x5 = 75
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
11
Standard Simplex (matrix) Representation Find X ∈ Rn that maximizes function z = C · X
subject to
A · X = A0
X ≥ 0n
A0 ≥ 0n
where
a
11
a12
. . .
a1,n−m 1 0 . . . 0
0
a
0
A =
21
a22
. . .
a2,n−m 0 1 . . . 0
.
, 0n = . , C = [c1, c2, . . . , cn]
..
...
. . .
...
... ... ... ...
..
am1 am2 . . . am,n−m 0 0 . . . 1
0
12
Standard Simplex (vector) representation Find X ∈ Rn
that maximizes function
z = C · X
subject to
A1x1 + A2x2 + . . . + Anxn = A0
X ≥ 0n
A0 ≥ 0n
a
1j
0
a
0
where A
2j
j =
.
, 0n = . , C = [c1, c2, . . . , cn]
..
..
amj
0
13
c1
c2
. . .
cn−m
cn−m+1
cn−m+2
. . .
cn
c0
i
base
ci
A1
A2
. . .
An−m
An−m+1
An−m+2
. . .
An
A0
1
An−m+1
cn−m+1
x1,1
x1,2
. . .
x1,n−m
1
0
. . .
0
x1,0
2
An−m+2
cn−m+2
x2,1
x2,2
. . .
x2,n−m
0
1
. . .
0
x2,0
..
.
.
.
.
.
.
.
.
.
.
.
.
..
..
..
..
. .
..
..
..
. .
..
..
m
An
cn
xm,1
xm,2
. . .
xm,n−m
0
0
. . .
1
xm,0
zk − ck
z1 − c1
z2 − c2
. . .
zm,n−m − cm,n−m
0
0
. . .
0
z0 − c0
14
4
6
0
0
0
0
x1
x2
x3
x4
x5
i
Base
A1
A2
A3
A4
A5
A0
1
A3
0
6
8
1
0
0
48
2
A4
0
10
6
0
1
0
60
3
A5
0
5
15
0
0
1
75
zj − cj
-4
-6
0
0
0
0
15
1. If zj − cj ≥ 0 for all j (1 ≤ j ≤ n) then the optimal (maximal) solution was found
– stop the algorithm. Otherwise go to step 2.
2. Find that k which satisfies the condition zk − ck = min (zj − cj)
1≤j≤n
3. Find that l which satiesfies the condition xj0
xi0
= min
xlk
xik>0 xik
If xik ≤ 0 for all i (1 ≤ i ≤ m) then the objective function reaches +∞ , so stop the algorithm. Otherwise go to step 4.
4. Calculate new coefficiants of the simplex tableou according to formulas (deter-mine a new corner-point feasible solution) x0 = x
x
ij
ij − xlj
x
ik for i = 1, 2, ..., l − 1, l + 1, ..., m + 1 and j = 1, 2, ..., n, 0
lk
x0 = xlj for j =, 1, 2, ..., n, 0
lj
xlk
where x0
= z0 − c
m+1,j
j
j for j = 1, 2, ..., n, 0.
Come back to step 1.
16
C
4
6
0
0
0
0
x1
x2
x3
x4
x5
i
Base
A1
A2
A3
A4
A5
A0
1
A3
0
6
8
1
0
0
48
2
A4
0
10
6
0
1
0
60
3
A5
0
5
15
0
0
1
75
zj − cj
-4
-6
0
0
0
0
X(0) = [0, 0, 48, 60, 75]
z(x(0)) = 0
17
C
4
6
0
0
0
0
x1
x2
x3
x4
x5
i
Base
A1
A2
A3
A4
A5
A0
1
A3
0
6
8
1
0
0
48
2
A4
0
10
6
0
1
0
60
3
A5
0
5
15
0
0
1
75
zj − cj
-4
-6
0
0
0
0
X(0) = [0, 0, 48, 60, 75]
z(x(0)) = 0
18
C
4
6
0
0
0
0
x1
x2
x3
x4
x5
i
Base
A1
A2
A3
A4
A5
A0
1
A3
0
10
0
1
0
− 8
8
3
15
2
A4
0
8
0
0
1
− 6
30
15
3
A2
6
1
1
0
0
1
5
3
15
zj − cj
-2
0
0
0
2
30
5
X(1) = [0, 5, 8, 30, 0]
z(x(1)) = 30
19
C
4
6
0
0
0
0
x1
x2
x3
x4
x5
i
Base
A1
A2
A3
A4
A5
A0
1
A3
0
10
0
1
0
− 8
8
3
15
2
A4
0
8
0
0
1
− 6
30
15
3
A2
6
1
1
0
0
1
5
3
15
zj − cj
-2
0
0
0
2
30
5
X(1) = [0, 5, 8, 30, 0]
z(x(1)) = 30
20
C
4
6
0
0
0
0
x1
x2
x3
x4
x5
i
Base
A1
A2
A3
A4
A5
A0
1
A
12
1
4
1
0
3
0
− 8
10
50
5
2
A
4
4
0
0
0
−24
1
44
10
50
5
3
A
21
2
6
0
1
− 1
0
6
10
50
5
zj − cj
0
0
3
0
2
344
5
25
5
X(2) = [12, 21, 0, 4, 5]
5
5
5
z(x(2)) = 344
5
21
Explanation 1. How to get from one corner point to another?
22
Explanation 1. How to get better corner point?
23
Wyszukiwarka
Podobne podstrony:
badania operacyjne wykład 4 (metoda simpleks)
Napęd Elektryczny wykład
wykład5
Psychologia wykład 1 Stres i radzenie sobie z nim zjazd B
Wykład 04
geriatria p pokarmowy wyklad materialy
ostre stany w alergologii wyklad 2003
WYKŁAD VII
Wykład 1, WPŁYW ŻYWIENIA NA ZDROWIE W RÓŻNYCH ETAPACH ŻYCIA CZŁOWIEKA
Zaburzenia nerwicowe wyklad
Szkol Wykład do Or
Strategie marketingowe prezentacje wykład
Wykład 6 2009 Użytkowanie obiektu
wyklad2
wykład 3
wyklad1 4
więcej podobnych podstron