simplex-metoden

Du må altså selv komme med forslag. Simplex metoden er ret kompleks, så du kan ikke forvente at vi herinde kan give en lektion i det.

ok bare i orden, jamen så tror jeg at bibetingelserne ska ganges med -1 for at vende ulighedstegnene:

-1.10x - 1.10y - 1.05z <= -1
-1.10x - 0.95y - 1.05z <= 0
-0.95x - 1.10y - 1.05z <= 0
-0.95x - 0.95y - 1.05z <= 0

og mit bud på den initiale simplextabel er nu:

 0     -1        -1         -1     0   0   0   0
-1   -1.10   -1.10   -1.05   1   0   0   0
 0   -1.10   -0.95   -1.05   0   1   0   0
 0   -0.95   -1.10   -1.05   0   0   1   0
 0   -0.95   -0.95   -1.05   0   0   0   1

er det korrekt? hvis ja, hva ska jeg så? (evt bare et hint)

Det er korrekt.

Jeg går ud fra, at der gælder x, y, z ≥ 0.

Det første du skal er at få din venstre side(Den er nu normalt anbragt til højre) til kun at indeholde ikke negative tal. Det kender jeg 3 metoder til, og jeg ved ikke hvilken du har lært. Den følgende er den jeg finder simplest; men som altså ikke nødvendigvis er den du har lært.  Har du lært en anden bør du bruge den. I denne metode skal du danne en kunstig objektfunktion, der består af summen af de rækker der har negativ højre ( i din version venstre) side. Brug denne objektfunktion til at finde frem til den variabel, der skal i basis. Derefter skal du finde den variabel, der skal ud af basis.

Lige et lille tip, som du muligvis bruger i forvejen. Lav dine beregninger i et regneark

ok super - mange tak!!

der er faktisk ingen begrænsninger på x, y og z - sorry, det glemte jeg at få med!

din metode ringer umiddelbart ingen klokker men jeg antager at jeg alternativt kan gange matricen med -1, er det ik tilladt?

jeg ska til eksamen uden mulighed for at medbringe pc så blir desværre nødt til at ku det i hånden;( ellers tak for tippet!!

Du kan ikke bare gange med -1. Det svarer til at du vender ulighedstegnet. En anden mulighed er store M metoden. Du oprette en ekstra variabel, som gør at uligheden er overholdt  for den første ulighed. Denne variabel gør du så kostbar at have inde at den omgående går ud af basis.

Simpleks algoritmen bygger næsten på at de pågældende variable skal være ikke negative, så man må tage ekstra forholdsregler, hvor dette ikke er tilfælde. Jeg tvivler derfor på at det er rigtigt at der ikke er begrænsninger. Er det virkelig tilfælde kan du blot erstatte  x, y og z med -x, -y, -z og dermed få vendt ulighedstegnene.

nå ok, jeg troede ellers jeg havde elimineret ulighedstegnene på følgende måde:

LP-problemet på kanonisk form (oprindelige setup):

min x + y + z
under bibetingelse
1.10x + 1.10y + 1.05z >= 1
1.10x + 0.95y + 1.05z >= 0
0.95x + 1.10y + 1.05z >= 0
0.95x + 0.95y + 1.05z >= 0

LP-problemet på standard form ved indførelse af slack-variable, hvormed ulighedstegnene elimineres:

min x + y + z
under bibetingelse
1.10x + 1.10y + 1.05z + s₁ = 1
1.10x + 0.95y + 1.05z + s₂ = 0
0.95x + 1.10y + 1.05z + s₃ = 0
0.95x + 0.95y + 1.05z  + s₄ = 0

heraf simplextabellen:

 0      -1        -1        -1     0   0   0   0
-1   -1.10   -1.10   -1.05   1   0   0   0
 0   -1.10   -0.95   -1.05   0   1   0   0
 0   -0.95   -1.10   -1.05   0   0   1   0
 0   -0.95   -0.95   -1.05   0   0   0   1

men jeg kan altså ik gange med -1?

Indsættelsen af slæk variablene forudsætter standart formen altså ≤ på højre side. Det retter du så op på i din sidste tabel, som er rigtig.

glem mit sidste indlæg (#6)!!

nå ok, jeg troede ellers jeg havde elimineret ulighedstegnene på følgende måde:

LP-problemet på kanonisk form (oprindelige setup):

min x + y + z
under bibetingelse
1.10x + 1.10y + 1.05z >= 1
1.10x + 0.95y + 1.05z >= 0
0.95x + 1.10y + 1.05z >= 0
0.95x + 0.95y + 1.05z >= 0

Jeg vender ulighedstegnene ved at gange bibetingelserne med -1:

-1.10x - 1.10y - 1.05z <= -1
-1.10x - 0.95y - 1.05z <= 0
-0.95x - 1.10y - 1.05z <= 0
-0.95x - 0.95y - 1.05z <= 0

LP-problemet på standard form ved indførelse af slack-variable, hvormed ulighedstegnene elimineres:

min x + y + z
under bibetingelse
-1.10x - 1.10y - 1.05z + s1 = -1
-1.10x - 0.95y - 1.05z + s2 = 0
-0.95x - 1.10y - 1.05z + s3 = 0
-0.95x - 0.95y - 1.05z + s4 = 0

heraf simplextabellen:

0      -1        -1        -1      0   0   0   0
-1   -1.10   -1.10   -1.05   1   0   0   0
 0   -1.10   -0.95   -1.05   0   1   0   0
 0   -0.95   -1.10   -1.05   0   0   1   0
 0   -0.95   -0.95   -1.05   0   0   0   1

men jeg kan altså ik gange med -1?
 

Det er godt nok for du vender ulighestegnet ved samme lejlighed.

ok fino. nej undskyld, mit spørgsmål er jo selvfølgelig heller ik om jeg kan gange hele matricen med -1, men i stedet om jeg kan kan gange de nye bibetingelser (ligningerne) med -1 så jeg får:

1.10x + 1.10y + 1.05z - s1 = 1
1.10x + 0.95y + 1.05z - s2 = 0
0.95x + 1.10y + 1.05z - s3 = 0
0.95x + 0.95y + 1.05z - s4 = 0

og dermed simplextabellen:

 0     -1       -1        -1     0    0    0    0
 1   1.10   1.10   1.05   -1    0    0    0
 0   1.10   0.95   1.05    0   -1    0    0
 0   0.95   1.10   1.05    0    0   -1    0
 0   0.95   0.95   1.05    0    0    0   -1

hvormed der nu ik er negative tal i søjlen

Det laver en anden fejl. Matricen for slækvariablene skal i starten være en enhedsmatrix.

ok, holder mig til nedenstående så

 0      -1        -1        -1     0   0   0   0
-1   -1.10   -1.10   -1.05   1   0   0   0
 0   -1.10   -0.95   -1.05   0   1   0   0
 0   -0.95   -1.10   -1.05   0   0   1   0
 0   -0.95   -0.95   -1.05   0   0   0   1

den er forresten go nok, der er ingen begrænsninger på x, y og z for (x, y, z) = (20/3, 0, -380/63) ifølge en facitliste jeg har fundet. hva var det så jeg ku gøre med simplextabellen når der ik er begræsninger?

Du skal finde hvilken hvilken variabel, der skal i basis. Jeg ved ikke hvilken metode du har lært; men rent faktisk vil det i dette specielle tifælde fungere ligegyldig hvilken af de 3 variable du vælger. Dernæst skal du finde hvilken variabel, der skal ud af basis.

når betingelserne for simplex er overtrådt, med det mener jeg; når alle koefficienter i øverste række er negative (-1, -1, -1 i eksemplet) samtidig med at der er negative koefficienter i første søjle (-1 i eksemplet) mener jeg vi ska anvende dual simplex-metoden - kan jeg ha ret i det, med andre ord; kan den metode anvendes på simplex-tabellen ovenfor? eller er det kun når x, y, z >= 0?

Problemerne kan løses. Det der har været problemet indtil nu har været ar din venstre side  har et negativt tal. Det kan klares med nogle passende iterationer. Som nævnt tidligere kender jeg 3 metoder til at finde indgående variabel. Hvilken metode du har ved jeg ikke; men jeg tror ikke på at opgavestilleren vil stille en sådan opgave, hvis du ikke har haft en metode til at finde den. Som nævnt tidligere kan du i dette specielle tilfælde bruge  en hvilken som helst variabel.

 Den mest almindelige måde med variable, der hverken er opadtil eller nedadtil begrænset er at skrive dem som en differens mellem to positive tal. x kan således skrives som x = x₊- x_-, hvor x₊ og x_- begge er ikke negative tal.

Det ser ud til for mig at du har haft så lidt om simplex algoritmen, at du ikke kan bruge den for det aktuelle tilfælde. Hvad har du haft om den algoritme?

jeg har kun haft om simplex- og dual simplex-metoden i problemer hvor variablene ska være ikke-negative i et tidligere fag (operationsanalyse) og arbejder nu i finansiering med problemer - som det ovenfor - hvor der ik er begrænsninger på variablene. vi er ik blevet introduceret for udvidelser til de tidligere lærte metoder men blot fået besked på de er tilstrækkelige til løsning af problemer uden begrænsninger på variablene. jeg har dog fundet nogle eksempler hvor en særskilt variabel z introduceres, som er lig objektfunktionen. et af eksemplerne er maksimeringsproblemet:

max 2.5x + 2y
under bibetingelse
  x  + 2y <= 8000
3x  + 2y <= 9000
        x, y >= 0

som så er omformuleret til:

max z
under bibetingelse
2.5x + 2y - z = 0
      x + 2y + s₁ = 8000
    3x + 2y + s₂ = 9000
     x, y, s₁, s₂ >= 0

og den initiale simplextabel er angivet til:

 x    y  s1 s2  z      =
2.5 2   0   0   -1    0
 1   2   1   0   0   8000
 3   2   0   1   0   9000

tilføjelsen af denne ekstra søjle (-1, 0, 0) som konsekvens af indførelsen af z i objektfunktionen virker i dette tilfælde overflødig da jeg godt ka komme frem til resultatet (x, y) = (500, 3750) uden denne søjle - ved du hva årsagen er til at denne søjle er tilføjet? er det bare smag og behag?
...MEN ved til gengæld ik om denne søjle er en nødvendighed i nedenstående minimeringsproblem hvor den initiale simplextabel også er angivet i mine papirer og hvor matricen med slackvariablene rent faktisk ik er en enhedsmatrice - ved du hvorfor det er tilladt i denne tabel (nedenfor)?

min 100x + y
under bibetingelse
121.0x + 1.1025y >= 0
104.5x + 1.1025y >= 0
90.25x + 1.1025y >= 9.75
x, y tilhører R

og den initiale simplextabel er angivet til:

100            1      -1   0    0   0   0
121.0   1.1025   0  -1   0   0   0
104.5   1.1025   0   0  -1   0   0
90.25   1.1025   0   0   0  -1  9.75

i modsætning til maksimeringsproblemet ovenfor er dette minimeringsproblem desværre ik omformet i mine papirer men omformningen må vel være som følger på baggrund af simplextabellen:

min z
100x + y - z = 0
under bibetingelse
-121.0x - 1.1025y <= 0
-104.5x - 1.1025y <= 0
-90.25x - 1.1025y <= -9.75
x, y tilhører R

min z
100x + y - z = 0
under bibetingelse
-121.0x - 1.1025y + s1 = 0
-104.5x - 1.1025y + s2 = 0
-90.25x - 1.1025y + s3 = -9.75
x, y tilhører R

min z
-100x - y + z = 0
under bibetingelse
121.0x + 1.1025y - s1 = 0
104.5x + 1.1025y - s2 = 0
90.25x + 1.1025y - s3 = 9.75
x, y tilhører R

hvilket gir:

 100          1       -1   0   0   0   0
121.0   1.1025   0  -1   0   0   0
104.5   1.1025   0   0  -1   0   0
90.25   1.1025   0   0   0  -1  9.75

dvs netop den ovenfor angivne simplextabel.

jeg repeterer lige mine spørgsmål:
1) hvilken fordel er der i at tilføje z og dermed få en ekstra søjle i simplextabellen? (i maksimeringsproblemet ovenfor er den overflødig i forhold til at komme frem til det rigtige resultat men kan den i andre tilfælde være en nødvendighed fx i minimeringsproblemet hvor der ik er begrænsninger på variablene? eller har tilføjelsen af søjlen intet at gøre med ubegrænsede variable?)

2) hva er årsagen til matricen med slackvariablene i minimeringsproblemet åbenbart ik skal være en enhedsmatrice?

I almindelighed holder det med at man blot kan ignorere at variablene er ubegrænset ikke; men det kan i specielle tilfælde så forekomme at de korreke løsninger er ikke negative og så vil man slippe godt fra det. Lad variablene være nummerert så de første k variable være dem der ikke er i basis i optimum. Så vil objektfunktionen være

x₀=c₁x₁+c₂x₂+... c_kx_k = tal, hvor x₀ skal maksimeres c_i>0. Hvis x₁=x₂=...=x_k=0 er x₀ = tallet på højre side. Hvis du forøger en hvilken som helst af disse variable, vil x₀ blive mindre. Hvis du rent faktisk vælger variablene i basis til at være højreside og x₁=x₂=...=x_k=0. vil rstriktionerne være opfyldt, så det må være løsningen. Hvis variablene x₁ ,x₂, ...x_k også kan være negative holder dette argument jo ikke.

Jeg kender ikke ret meget til finansering; men jeg tror ikke på at pengene man bruger ikke er begrænset. Det er begrænset hvor mange penge du har og det er begrænset hvor mange penge du kan låne. Rentefoden er også en anden, hvis du overtrækker din konto, så alene af den grund skal lån behandles som en særskilt variabel og kan derfor vælges ikke negativ.

Med hensyn til at indføre en speciel variabel z for objektfunktionen har jeg set det en enkelt gang; men jeg kan ikke se, at det er nogen god ide. Det indføre jo blot en ekstra restriktion og en ekstra variabel, der skal holdes øje med. Det vil normalt medføre længere kørselstid og mere forbrug af hukommelse.

Det med at have den negative til en enhedsmatrix for slækvariablene har jeg aldrig set før. Ligningsmæssigt er det i orden. Man skal blot være klar over, at så er der ikke nogen variable i basis overhovedet. Det første man skal gøre er så at sætte en variabel i basis på hver linie.

fint, så er vi enige omkring den z-variabel. variablene kan være negative hvilket svarer til en kort position. hvis x eksempelvis er en position i et aktiv og y er en pengemarkedsposition svarer en negativ værdi af x til et salg af aktivet mens en negativ værdi at y svarer til at låne penge. det er derfor man i finansiering næsten altid har at gøre med variable der ka antage negative værdier. bibetingelserne vil sørge for porteføljen (x, y) ik antager enorme positive/negative tal. for at vende tilbage til de to minimeringsproblemer fra hhv svar #16 og mit indlæg:

min 100x + y
under bibetingelse
121.0x + 1.1025y >= 0
104.5x + 1.1025y >= 0
90.25x + 1.1025y >= 9.75
x, y tilhører R

 100           1      -1   0   0   0   0
121.0   1.1025   0  -1   0   0   0
104.5   1.1025   0   0  -1   0   0
90.25   1.1025   0   0   0  -1  9.75

min x + y + z
under bibetingelse
1.10x + 1.10y + 1.05z >= 1
1.10x + 0.95y + 1.05z >= 0
0.95x + 1.10y + 1.05z >= 0
0.95x + 0.95y + 1.05z >= 0
x, y, z tilhører R

 0      -1         -1         -1    0   0   0   0
-1   -1.10   -1.10   -1.05  1   0   0   0
 0   -1.10   -0.95   -1.05   0   1   0   0
 0   -0.95   -1.10   -1.05   0   0   1   0
 0   -0.95   -0.95   -1.05   0   0   0   1

...ved du så om det er muligt at anvende en metode som kan finde løsningerne hhv. (x, y) = (-0.317073171, 34.79896023) og (x, y, z) = (20/3, 0, -380/63)?

Du skal først finde hvad der skal ind i basis og ud af basis. Du kan godt bruge dual simplex til det; men ellers vil det virke ligegyldig hvilken variabel du sætter i basis. Udbasis skal være s1

ok så simplex og dual simplex virker altså ik kun når variablene skal være ikke-negative? sådan forstod jeg dig ellers i svar #17 - det du skriver i starten..