Springen naar inhoud

de L1 approximatie.// Lineair programmeren/optimaliseren


  • Log in om te kunnen reageren

#1

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 06 december 2006 - 22:23

hello! ik heb een vraagje over Lineaire optimalisatie.
Stel je hebt een aantal punten op een grafiek en je wilt de best passende lijn trekken.
De som van de absolute vertikale afstanden van de punten tot de lijn moet dus geminimaliseerd worden. Dit heet de L1 approximatie.
Er bestaat ook een andere optimalisatie: namelijk de L-oneindig optimalisatie, hierbij moet je de maximale vertikale afstand van de gegeven punten tot de lijn minimaliseren.
het probleem is dus:
min(a,b) {max1<=i<=n| yi-(axi+b|}

ik moet van dit probleem een LP formulering vinden, kan iemand mij helpen?
In dit pdf bestand vind je een voorbeeld van een L1 approximatie met een uitwerking ervan..maar nu zoek ik naar een Loneindig approximatie.
http://www.math.leid...-najaar2006.pdf
zie pagina: 205 Toepassing 4.2
enig idee?
thanx

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 07 december 2006 - 15:33

Je zult zelf al wel gemerkt hebben dat google niks bruikbaars oplevert, zelfs niet in het Engels ("L-infinite" "linear programming"). Dit komt wellicht omdat het eigenlijk geschreven wordt als L gevolgd door een liggende acht (symbool voor oneindig).
Dit valt buiten mijn ervaring met linear programming dus heb ik er maar eens een van mijn oude boeken bijgehaald: Linear Programming, door Vasek Chvatal, pagina 213-227. Overigens geeft dit wel hits in google; de man blijkt zelfs een eigen website te hebben.

Probeer het boek in de bibliotheek te vinden of anders zou ik de bladzijden volgende week (eerder gaat niet) moeten scannen in een pdf-file en op een of andere manier toegankelijk maken.
Wellicht weet de moderator hoe.
Hydrogen economy is a Hype.

#3

*_gast_PeterPan_*

  • Gast

Geplaatst op 07 december 2006 - 15:54

Ik kan je ook niet helpen. Ik heb geen ervaring met minimax problemen.
Ik heb alleen ervaring met least squares (som van kwadraten van de afstand van de punten tot de lijn minimaliseren) en total least squares (som van afstanden van de punten tot de lijn minimaliseren), maar daar heb jij niets aan.

#4

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 07 december 2006 - 17:49

het gaat eigenlijk om ťťn groot probleem:
in een formulering van een LP probleem mag je niet gebruik maken van absolute waarden of van bijv. maximum of minimum.
Noem de afstand tussen een punt en de lijn y=ax+b gewoon |di|"afhankelijk van de positie van het punt, kan het verschil positief of negatief zijn".
Dit is de afstand van ieder punt met coordinaat xi
Ik moet de maximale afstand in |d1|,d2|, |d3|,..,|dn|zien te minimaliseren.

ik vroeg me af of er een trucje bestaat om de maximale afstand anders te noteren..bijv als som of verschil van getallen, precies zoals ze gedaan hebben bij de absolute waarde. De absolute waarde kan je schrijven als verschil/som van twee natuurlijke getallen.
ALs k dat trucje vind, dan ben ik al klaar, de rest kan ik wel....
alvast bedankt

#5

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 07 december 2006 - 18:59

Nu begrijp ik wellicht de oorspronkelijke vraag niet meer.
Je zocht toch L-oneindig approximatie als alternatief voor de L1 approximatie?

Wat ik zo vlug begrijp(?) van de L-oneindig approximatie methode is dat je een Z ( = max|Di| ) definieert zodat:

Z + (A*Xi + B) >= Yi voor i = 1....n

en ook:

Z - (A*Xi + B) >= -Yi voor i = 1....n

Dat geeft dan 2n vergelijkingen.
Doelfunctie is dan: minimaliseer Z (oftewel minimaliseer de grootste |Di| )

Ik hoop dat dit je op weg helpt.
Hydrogen economy is a Hype.

#6

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 07 december 2006 - 19:38

Doelfunctie is dan: minimaliseer Z (oftewel minimaliseer de grootste |Di| )

precies. Maar je mag niet opschrijven: doelfunctie is:
minimaliseer Z (oftewel minimaliseer de grootste |Di| )

wat tussen haakjes staat: minimaliseer de grootste |Di|
mag niet zo opgeschreven worden bij een LP probleem.
De absolute waarde moet er niet staan, en het woordje 'minimaliseer' ook niet.
dus je mag niet schrijven:
min( Z=max(|di|))
die 'max' en '|di| mogen er niet staan, want het gaat om een LINEAIR programmeren probleem.

#7

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 07 december 2006 - 21:08

Ik ben bekend met LP maar je hebt me blijkbaar verkeerd begrepen. Het gaat om Z en de vergelijkingen die ik gaf waarin Z voorkomt.
Ik heb alleen tussen haakjes toegevoegd dat de Z die je uiteindelijk vindt de door jou bedoelde max |Di| is. Het was bedoeld voor de duidelijkheid maar ik had het beter weggelaten dus: vergeet alles wat tussen die haakjes staat.

De truc is immers dat door voor ieder punt twee vergelijkingen te gebruiken de waarde van Z alleen positief kan zijn.

In alle vergelijkingen komt alleen Z voor en die moet je samen met A en B oplossen gebruikmakend van de waarden voor Xi en Yi, de grafiekpunten die bekend zijn.
Dus nogmaals:

Z + (A*Xi + B) >= Yi voor i = 1....n

Z - (A*Xi + B) >= -Yi voor i = 1....n

minimaliseer Z
Hydrogen economy is a Hype.

#8

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 08 december 2006 - 12:40

okee!
ik snap het..
als Z minimaal is, dan heeft ie automatisch de waarde van de grootste afstand y-ax-b!
bedankt! het is nu gelukt.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures