Upload
wanda-lazar
View
106
Download
1
Embed Size (px)
Citation preview
Managemententscheidungsunterstützungssysteme
(Ausgewählte Methoden und Fallstudien)
(Die Thesen zur Vorlesung 3)
Thema der VorlesungLösung der linearen Programmierungsprobleme:
Das Simplexverfahren
Teil 1
Prof. Dr. Michal Fendek
Institut für Operations Research und Ökonometrie
Wirtschaftsuniversität Bratislava
Dolnozemská 1
852 35 Bratislava, Slowakei
Institut für Operations Research und Ökonometrie, WU Bratislava
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:2
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
max10080),( 21211 xxxxf
Unter den Nebenbedingungen (LOP1)
0,
200
150053
120023
21
2
21
21
xx
x
xx
xx
Rekapitulation der Erkenntnissen aus der Vorlesung N.2 Beispiel aus der Vorlesung 2:
Model (LOP1): Maximierung des Gesamterlös
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:3
Graphische Darstellung der Lösung des linearen Optimierungsproblems
Der erste Schritt ist die so genannte Menge der zulässigen Lösungen zu konstruieren. Abgekürzte Schreibweise
)(,,;,,)(max LOPRRRwobeif mnnmT bxcA0xbAxxcx
Definition1 Für das lineare Optimierungsproblem (LOP) ist die Menge
0xbAxx ,D die Menge der zulässigen Lösungen
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:4
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
MOPO
-100
0
100
200
300
400
500
600
700
-100 0 100 200 300 400 500
Produkt 1
Pro
du
kt
2 f1
NB1
NB2
NB3
Maschinenkapazität
Marketingbeschränkung
Rohstoffbeschränkung
D
x1=(333,3;100)f1(x1)=36664=f1*f2(x1)=58330
Isoerlöslinie f1=0
f1
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:5
Graphische Darstellung der Lösung des linearen Optimierungsproblems
D e r z w e i t e S c h r i t t d e s V e r f a h r e n s i s t a u s d e r M e n g e d e r z u l ä s s i g e n L ö s u n g e n D s o g e n a n n t e O p t i m a l l ö s u n g z u i d e n t i f i z i e r e n . D e f i n i t i o n 2 D i e z u l ä s s i g e L ö s u n g x * D i s t d i e O p t i m a l l ö s u n g d e s l i n e a r e n O p t i m i e r u n g s p r o b l e m s
mnnmT RRRwobeif bxcA0xbAxxcx ,,,,,)(max w e n n
** ,)()(~ xxxxx ffD
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:6
Graphische Darstellung der Lösung des linearen Optimierungsproblems
D wird als Durchschnitt von endlich vielen Halbebenen ein konvexes Polyeder, d.h. eine von endlich vielen Geradestücken begrenzte konvexe Menge der Ebene. Konvex bedeutet, daß die Verbindungsstrecke zwischen zwei beliebigen Punkten von D an keiner Stelle D verlässt. Diese Eigenschaft ist für viele Rechenverfahren zur Bestimmung einer optimalen Lösung wichtig Also, die Menge der zulässigen Lösungen wird mit dem konvexen Polyeder D gebildet. Dann auch jede zulässige Lösung unserer Aufgabe befindet sich in einem Punkt des konvexen Polyeder D.
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:7
Graphische Darstellung der Lösung des linearen Optimierungsproblems
J e d e f e s t e W e r t q d e r Z i e l f u n k t i o n
n
jjj qxcf
1
)( x
w i r d a l s I s o z i e l f u n k t i o n l i n i e b e z e i c h n e t , d a j e d e a u f d i e s e r G e r a d e n l i e g e n d e K o m b i n a t i o n d e r V a r i a b l e n x = ( x 1 , x 2 , … , x n ) d e n g l e i c h e n W e r t d e r Z i e l f u n k t i o n e r b r i n g t . J e d e I s o z i e l f u n k t i o n l i n i e qf xcx T)( i s t s e n k r e c h t z u d e n G r a d i e n t e n v e k t o r )( xf d e r Z i e l f u n k t i o n )( xf . D i e R i c h t u n g d e s r a s a n t e s t e n A n s t i e g s d e r F u n k t i o n f ( x 1 , x 2 , … , x n ) i m P u n k t
x 0 w i r d d u r c h d e n G r a d i e n t )( 0xf d e r F u n k t i o n i m P u n k t x 0 a n g e z e i g t . G r a d i e n t )( xf d e r F u n k t i o n )( xf i m P u n k t x 0 i s t g e g e b e n d u r c h d e n V e k t o r d e r e r s t e n p a r t i e l l e n A b l e i t u n g e n i m P u n k t x 0 u n d g i l t
0xx
xxxx
nx
f
x
f
x
ff
)(,,
)(,
)()(
21
0
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:8
Graphische Darstellung der Lösung des linearen Optimierungsproblems
A n w e n d e n w i r j e t z t d i e a u f g e f ü h r t e n E i g e n s c h a f t e n d e r I s o z i e l f u n k t i o n l i n i e f ü r d i e L ö s u n g u n s e r e s n u m e r i s c h e n B e i s p i e l s d e r O p t i m i e r u n g d e r P r o d u k t i o n s s t r a t e g i e d e r F i r m a .
W e n n w i r w e r d e n d i e I s o e r l ö s l i n i e p a r a l l e l i n R i c h t u n g d e s O r t h o g o n a l e n v e k t o r s , ( O r t h o g o n a l v e k t o r i s t s e n k r e c h t z u d e r I s o e r l ö s l i n i e ) b z w . d e s G r a d i e n t e n d e r Z i e l f u n k t i o n f ü r d e n G e s a m t e r l ö s
100,80),(
,),(
),(2
211
1
211
211
x
xxf
x
xxfxxf
v e r s c h i e b e n , w i r k ö n n e n s e h e n , d a ß p a r t i e l l e o p t i m a l e L ö s u n g f ü r d i e Z i e l f u n k t i o n „ G e s a m t e r l ö s “ i n d e r E c k e x 1 b e f i n d e t s i c h .
I n d i e s e m P u n k t d e s k o n v e x e n P o l y e d e r g i l t x 1 = ( 3 3 3 , 3 ; 1 0 0 ) u n d d e r W e r t d e r Z i e l f u n k t i o n G e s a m t e r l ö s i s t f 1 ( x 1 ) = 3 6 6 6 4 G E = f 1
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:9
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
E r in n e r n w ir d ie e le m e n ta r e F o r m u lie r u n g d e s l in e a r e n O p tim ie r u n g sp r o b le m s B e m e r k u n g : a ) a lle N e b e n b e d in g u n g e n s in d in d e r F o r m ‚k le in e r o d e r g le ic h ‘ = < b ) a lle V a r ia b le n s in d n ic h tn e g a tiv
min xc = f(x) jj
n
j=1
u n te r d e n B e d in g u n g e n
n,1,=j x
m, ,=i b xa
j
ijij
n
j=1
0
w o m – Z a h l d e r N e b e n b e d in g u n g e n d e s P r o b le m s , n – Z a h l d e r V a r ia b le n d e s P r o b le m s , c j – K o e f f iz ie n te n d e r Z ie lfu n k tio n , j= 1 ,. . . ,n , b i – K o e f f iz ie n te n d e r r e c h te n S e ite , i= 1 , . . . ,m , a i j – K o e f f iz ie n te n d e r M a tr ix d e s S y s te m s d e r N e b e n b e d in g u n g e n , i= 1 , . . . ,m , j= 1 ,. . . ,n , x j - E n ts c h e id u n g s v a r ia b le n , j= 1 ,. . . ,n ,
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:10
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
Standardform des linearen Optimierungsproblems - Transformation des linearen Optimierungsproblems aus der Form des linearen Ungleichungssystems in der Form des linearen Gleichungssystems Bemerkung: a) alle Nebenbedingungen sind in der Form ‚ gleich‘ = formuliert b) Transformation der Ungleichungen ist mit der Hilfe so genannten Schlupfvariablen si realisiert c) alle Schlupfvariablen sind auch nichtnegativ Aufgabe LOP_SF
min xc = f(x) jj
n
1=j
unter den Bedingungen
m, ,=is
n,1,=j x
m, ,=i bs xa
i
j
iijij
n
j=1
0
0
wo cj – Koeffizienten der Zielfunktion, j=1,...,n, bi – Koeffizienten der rechten Seite, i=1,...,m, aij – Koeffizienten der Matrix des Systems der Nebenbedingungen, i=1,...,m, j=1,...,n, xj - Entscheidungsvariablen, j=1,...,n, si - Schlupfvariablen, i=1,...,m,
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:11
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
max10080),( 2121 xxxxf
Unter den Nebenbedingungen (LOP)
0,,,,
200
150053
120023
32121
32
221
121
sssxx
sx
sxx
sxx
S ta n d a r d fo r m d e s l in e a r e n O p tim ie r u n g sp r o b le m s in d e r M a tr ix fo r m S F _ L O P
mnmmnmT RRRRf sbxcEA0sxbEsAxxcx ,,,;,;,,)(max B ei d e r V o ra u sse tzu n g m n ; ra n g ( A , E ) = m
ji
jiee ijmmij 0
1,E
Model (LOP): Maximierung des Gesamterlöses
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:12
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
Erste Frage: Wie werden wir dieses linearen Optimierungsproblem in der Form des linearen Gleichungssystems lösen?
m
f T
Erang!!!
,
max)(
0sx
bEsAx
xcx
bx
xBN
x
xccx
B
N
B
NBN
,
max,)(f
0!!!
;
;
N
NB
x
xxsx
BENA
bx
BN
xccx
B
BBN
0,
0,)(f
bBx
xcx
B
BB
Tf )(
bBEx
bBBxB
BbBx
1B
1B
1
1LB
/
!!!! bBcx
bBx1
B
1B
Tf
0 *
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:13
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
Nächste Frage: Welcherart wir können diese Basische Lösung des Optimierungsproblems finden Definition 5: Geben ist eine Aufgabe in der Form LOP_ST mit m <= n. Eine Basislösung des Problems ist eine Lösung (Vektor), in der höchstens m Variablen von Null verschiedene Werte annehmen. Die mindestens n-m restlichen Variablen nehmen en Wert Null an. Die zur Basislösung gehörigen Variablen heißen Basisvariablen. Bemerkung: Eine Basislösung mit den nichtnegativen Variablen heißt Basische zulässige Lösung des Problems
0 bBx 1B
Die Lösung des Systems der linearen Nebenbedingungen in der Form:
ist Basische Lösung des Problems
bBx 1B
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:14
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
Zum Beispiel folgende drei Vektoren sind die zulässige Basislösungen in userer Optimierungsaufgabe
0,,,,
200
150053
120023
32121
32
221
121
sssxx
sx
sxx
sxx
In dem System der Nebenbedingungen in unserem Optimierungsproblem wir haben m = 3 Nebenbedingungen und n = 5 Variablen Rang der Matrix des Systems der Nebenbedingungen ist r(A) = 3. Also Vektor der zulässigen Basislösung muß höchstens 3 positive Elemente umfassen und aller übrigen Elemente des Vektors der zulässigen Basislösung müssen Nullwerte annehmen.
0,500,800,200,00,,,,0,,,,
200,300,0,0,400,,0,0,,,,,
200,1500,1200,0,0,,,0,0,,,,
212321213
321321212
32132121
ssxsssxx
ssxsssxx
ssssssxx
x
x
x1
100,0,600,300,0,0,,,0,,,, 312321214 ssxsssxxx
und zum Beispiel Vektor ist die nicht zulässige Basislösung der Optimierungsaufgabe
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:15
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
E s i s t k l a r , d a ß w i r t h e o r e t i s c h a l l e B a s i s l ö s u n g e n d e s O p t i m i e r u n g s p r o b l e m s b e r e c h n e n k ö n n e n . ? ? ? W i e v i e l d i e s e r L ö s u n g e n w i r m ü s s e n a l s o b e r e c h n e n , w e n n d a s O p t i m i e r u n g s p r o b l e m m N e b e n b e d i n g u n g e n u n d n V a r i a b l e n h a t u n d R a n g d e r M a t r i x d e s S y s t e m s d e r N e b e n b e d i n g u n g e n i s t r ( A ) = m .
m
nBLp
I n u n s e r e m B e i s p i e l f ü r d i e Z a h l d e r B a s i s l ö s u n g e n ( B i n o m i a l k o e f f i z i e n t ) d a n n g i l t
103
5
m
nBLp
A b e r s c h o n i m F a l l , w e n n m = 3 u n d n = 1 0 0 i s t
16170023/1819203
20
m
nBLp
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:16
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
Nächste Frage: Können wir diese aktuelle Basische zulässige Lösung des Problems verbessern? Oder Ist diese aktuelle Basische zulässige Lösung des Problems schon die Optimallösung? Definition 6: Die zulässige Lösung x* der Optimierungsaufgabe in der Form LOP_ST ist die Optimallösung der Aufgabe, wenn keine andere zulässige Lösung x mit dem besseren Wert der Zielfunktion existiert .
bBcx
bBx1
B
1B
Tf
0
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:17
Lösung der linearen Programmierungsprobleme:Das Simplexverfahren
Nächste Frage: Müssen wir wirklich bei der Suche der optimale Lösung so viel Basislösungen untersuchen? Die Antwort gab G B. Dantzig in seinem Simplexverfahren Ideenschema des Simplexverfahrens Algorithmus schrittweise untersucht nicht die unendliche Anzahl der allen zulässigen Lösungen, aber nur die endliche Anzahl der Basislösungen
iterativer Prozess
*21 xxxx k
0bBxxx 1. kB
kk DI Ist xk optimal? A) ja Stop B) nein II.
kkkk ffII xxxx 11 :.
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:18
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Elementar Algorithmus des Simplexverfahrens Gegeben ist das Optimierungsproblem
I. Etappe Initialisierung: Festlegung der zulässigen Ausgangsbasislösung (ZABL)
- Iterationsnummer p - Voraussetzungen:
0x
bAx
xcx
max)( Tf
0x
bAx
xcx
max)( Tf
0sx
bEsAx
xcx
,
max)( Tf
m
nn
mnm
R
RR
mR
b
,;
,rang;,~
sxc
EAEAA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:19
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Stellen wir der Iterationsnummer p = 0 Wir bekommen die zulässige Ausgangsbasislösung Führen wir nächste Substitutionen ein: II
0,,
max,)(
pp
p
p
p
p
BN
B
f
Nxbx
xBN
x
xccx
B
N
N
ZABL,,,
0
0
000
10
10
0
b0s0xxx
b0bBcx
bEbbBxs
BN
B
B
TTf
xxsx
BENA
NB
pp
p
;
;
;;b;
~;
~~;,,1,
~;
~
100
11
mmnm
m
iijj
mn
jjjj
RR
anj
XXBX
AAAABXABX
1
11
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:20
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
II. Etappe: Die Feststellung der optimalen Lösung des linearen Optimierungsmodells - OL 10 Optimalitätstest der aktuellen Basislösung (Bestimmung der eintretenden Variable) Berechnung des Vektors der reduzierten Bewertungen der Variablen a) Wenn
b) Wenn 1.1 wenn ist OL des LOP; STOP
1.2 wenn dann
Der Spaltenvektor Ak tritt in der Basis ein Die entsprechende Variable ist eintretende
( Der k-te Spaltenvektor der Simplextabelle ist s. g. Pivotspalte )
gehe zu dem Schritt 20
mnjcxccr
r
jTB
m
ijijBijj
mn
jj
TB
Tp
TB
TT
,,1,X
XA
1
1
1
c
r
ccBccr
jmnj
k rrf
,..,1
maxmax:)(x
*0 xx pkr
0kr
jmnj
k rrf
,..,1
minmin:)(x
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:21
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
20 Bestimmung der eintretenden Variable 2.1 Wenn der Wert der Zielfunktion ist unbegrenzt
STOP 2.2 Wenn wir berechnen dann
Die eintretende Variable den Wert t haben wird
Der l-te Basisspaltenvektor tritt aus der Basis aus
Die l-te Basisvariable wird austretende
Der l-te Zeilenvektor der Simplextabelle ist s.g. Pivotzeile Das Tabelleelement xlk, das im Abschnitt von Pivotspalte und Pivotzeile steht, heißt Pivotelement
gehe zu dem Schritt 30
m,ifür xik ,1,0
0,...,1
ikmi
x
lk
l
m
iik
i
x x
x
x
xmint
ik
0
1
0
0
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:22
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
30 Die elementare Basisänderung mit dem Pivotlement xlk ALLE Elemente der Simplextabelle wir werden aus der Matrix
auf die Matrix nach der folgenden Formel transformieren
mnjli für
x
xxx
li fürx
x
xx
lk
ikljij
lk
lj
ijmj
miij
,,1,0~~~ ,,1,0
,,1
X
Dann stellen wir a) b) Iterationsnummer p = p + 1
gehe zurück zu dem Schritt 10
mnj
miijx
,,1,0
,,1
~~
X
mnj
miijx
,,1,0
,,1
X
mj
miijmj
miij xx
,,1,0
,,1
,,1,0
,,1,
~
�XX
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:23
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Beispiel N. 1 Wir werden ein Unternehmen untersuchen. Das Unternehmen hat in seinem Produktionsprogramm zwei Produkte P1, P2. Für die Erzeugung diese zwei Produkte die Firma benutzt 2 Produktionsfaktoren. Disposition des Modells: a) Wir haben zur Verfügung: die Angaben über die Verbrauchsnormen der Produktionsfaktoren für die einzelne Produkte des Produktionsprogramms aij, i = 1, 2 ; j = 1, 2 die Angaben über die verfügbare Menge der einzelnen Produktionsfaktoren bi, i = 1, 2 die Angaben über die Preise pj der einzelnen Produkte des Produktionsprogramms, j = 1, 2 Diese Angaben über das Produktionsprogramm des Unternehmens sind in Tabelle 1 präsentiert.
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:24
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Tabelle 1.
Produktionsfaktor Verbrauchsnormen der
Produktionsfaktoren
verfügbare Menge der
Produktions-faktoren
P1 P2
F1 2 1 7
F2 3 2 11
Preis 8 5 -
0,
1123
712
..
18),(
21
21
21
2111
xx
xx
xx
BU
maxxxxxf
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:25
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Graphische Darstellung der Lösung
0,
1123
712
..
58),(
21
21
21
2111
xx
xx
xx
BU
maxxxxxf
x2
x1
7
11/2
7/2 11/3
D
f(x) x*=(3,1)
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:26
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Lösung Tab.1
f (x1, x2) 8 5 0 0
xB cB x1 x2 s1 s2 b
s1 0 2 1 1 0 7 s2 0 3 2 0 1 11
rj 8 5 0 0 0
Zulässige Ausgangsbasislösung nach der ersten Iteration:
0~0058
0,
11700,B
max
21
212143
jr
xxf
ssxxxAA
581023
0112
Tc
11
7bA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:27
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
2. Iteration Tab.2
f (x1, x2) 8 5 0 0
xB cB x1 x2 s1 s2 b
x1 8 1 1/2 1/2 0 7/2
s2 0 0 1/2 -3/2 1 1/2
rj 0 1 -8 0 28
Zulässige Basislösung nach der zweiten Iteration:
00810
28,
2/1002/7,B
max
21
212141
jr
xxf
ssxxxAA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:28
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
3. Iteration Tab.3
f (x1, x2) 8 5 0 0
xB cB x1 x2 s1 s2 b
x1 8 1 0 2 -1 3 x2 5 0 1 -3 2 1
rj 0 0 -1 -2 29
Optimale Basislösung nach der dritten Iteration:
29**,
0013*,B
21
212121
xxf
ssxxxAA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:29
Beispiel 2 Graphische Darstellung der Lösung
0,
122
412
..
23),(
21
2
21
2111
xx
x
xx
BU
maxxxxxf
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
x2
x1
4
-2
D
f(x)
6
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:30
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Lösung Tab.1
f (x1, x2) 2 3 0 0
xB cB x1 x2 s1 s2 b
s1 0 -2 1 1 0 4 s2 0 0 2 0 1 12
rj 2 3 0 0 0
Zulässige Ausgangsbasislösung nach der ersten Iteration:
0~0032
0,
12400,B
max
21
212143
jr
xxf
ssxxxAA
322
4
1020
0112
Tc
1bA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:31
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Tab.2
f (x1, x2) 2 3 0 0
xB cB x1 x2 s1 s2 b
x2 3 -2 1 1 0 4
s2 0 4 0 -2 1 4
rj 8 0 -3 0 12
Zulässige Ausgangsbasislösung nach der zweiten Iteration:
0~0308
12,
4040,B
21
212142
jr
xxf
ssxxxAA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:32
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Tab.3 f (x1, x2) 2 3 0 0
xB cB x1 x2 s1 s2 b
x2 3 0 1 0 1/2 6 x1 2 1 0 -1/2 1/4 1
rj 0 0 1 -2 20
Zulässige Ausgangsbasislösung nach der ersten Iteration: Wert der Zielfunktion ist unbegrenzt!!!
tttftt UBUB ;2063
2
112;06
2
11 xx
0~2100
20,
0061,B
max
21
212112
jr
xxf
ssxxxAA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:33
Beispiel 3 Graphische Darstellung der Lösung
0,
82
40410
..
25),(
21
21
21
2111
xx
xx
xx
BU
maxxxxxf
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
x2
x1
4
x*1=(2,5)
D
f(x)
10
4
x*2=(4,0)
f(x*1)= f(x*2)=20
f(x)=0
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:34
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Lösung Tab.1
f (x1, x2) 5 2 0 0
xB cB x1 x2 s1 s2 b
s1 0 10 4 1 0 40 s2 0 -1 2 0 1 8
rj 5 2 0 0 0
Zulässige Ausgangsbasislösung nach der ersten Iteration:
0~0025
0,
12400,B
max
21
212143
jr
xxf
ssxxxAA
258
40
1021
01410
TcbA
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:35
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Tab.2
f (x1, x2) 5 2 0 0
xB cB x1 x2 s1 s2 b
x1 5 1 2/5 1/10 0 4 s2 0 0 8/5 1/10 1 12
rj 0 0 -1/2 0 20
Erste alternative Basislösung nach der zweiten Iteration:
OLx
xAA
Bx
002/100
20,
12004,B
2
21
212141
xjr
xxf
ssxx
11.04.2023 Prof. Dr. Michal Fendek Folie Nr.:36
Lösung der linearen Programmierungsprobleme: Das Simplexverfahren
Tab.2
f (x1, x2) 5 2 0 0
xB cB x1 x2 s1 s2 b
x1 5 1 0 1/12 -1/6 2 x2 2 0 1 1/24 5/12 5
rj 0 0 -1/2 0 20
Zweite alternative Basislösung nach der dritten Iteration: Alle alternative Optimallösungen
OLx
xAA
Bx
002/100
20,
0052,B
2
21
212121
sjr
xxf
ssxx
25,
522521041*
21
*2*1
xxf
xxx