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.leidenuniv.nl/%7Ekallenber...-najaar2006.pdf
zie pagina: 205 Toepassing 4.2
enig idee?
thanx
Laatste berichten
-
23:12
speciale rel. theorie 10
-
22:57
Straatklok loopt 5 minuten voor 11
-
22:57
wig 6
-
22:36
Gravity and gravitation 4
-
22:24
[scheikunde] vraag Chemie - wat is de oplossing? 10
-
19:47
Bruine vlekken op treinaanwijzerbord 10
-
19:44
Vogels in de stad zijn goede klussers 2
-
19:12
Rood laserlicht 3
-
17:30
Herleiden afmetingen vanaf een foto 21
-
16:34
[wiskunde] Prijs Product per KG; Alternatief Inzicht 3
-
13:57
do-re-mi-fa-so vliegtuigen 9
-
13:16
geen minkowski-ruimte toch? Doe ik dit nou fout? 17
-
13:12
[natuurkunde] kroon van koning op Syracuse 10
-
10:15
2013 – Augustus Vraag 3 3
-
24 apr
Vraag 2009 Juli Vraag 5 5
-
24 apr
positie 2
-
24 apr
Schroefdraad berekening 8
-
24 apr
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
23 apr
Weerfrustratie 9
-
23 apr
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
de L1 approximatie.// Lineair programmeren/optimaliseren
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Pluimdrager
- Berichten: 4.167
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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.
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.
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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.
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.
-
- Berichten: 171
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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
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
-
- Pluimdrager
- Berichten: 4.167
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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.
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.
-
- Berichten: 171
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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.
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.
-
- Pluimdrager
- Berichten: 4.167
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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
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.
-
- Berichten: 171
Re: de L1 approximatie.// Lineair programmeren/optimaliseren
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.
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.
