Mathematik: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
Released by matroid on Fr. 17. Juli 2009 20:57:45 [Statistics]
Written by Delastelle - 9650 x read [Outline] Printable version Printer-friendly version -  Choose language   
Software

\(\begingroup\) Plötzlich steht es da: ein Optimierungsproblem, das sich in das Schema max c^T x unter den Nebenbedingungen Ax <= b pressen lässt. Aber wie löse ich es? Gut ich kann es von Hand mittels Simplexmethode lösen in der Hoffnung, mich nicht zu verrechnen. Oder ich nehme eines der folgenden Programme, die zudem kostenlos sind.

Definition eines linearen Optimierungsproblems

(LP) array(max c^T x unter den;Nebenbedingungen Ax <= b;mit A \el \IR^mxn\, b \el \IR^m\ ; c \el R^n\, x >= 0) (ILP) array(max c^T x unter den;Nebenbedingungen Ax <= b;mit A \el \IR^mxn\, b \el \IR^m\ ; c \el R^n\, x >= 0 ganzzahlig) Wohlgemerkt aus einem LP ("linear Programming") wird ein ILP ("integer linear programming") durch die Forderung, dass x ganzzahlig sein soll. Hinweis: manchmal werden abweichende Definitionen von "LP" und "ILP" verwendet.

Beispiele

Die Beispiele (1) bis (3) sind lineare Optimierungsprobleme (LP). Sie werden beispielsweise mit dem Simplexverfahren gelöst. Beispiel (4) ist ein ganzzahliges lineares Optimierungsproblem (ILP). Es kann nicht mit dem Simplexverfahren gelöst werden. (1) Max. F(x,y) = 4x+3y x+3y <= 9 -x+2y >= 2 x, y >= 0 Bild Der zulässige Bereich ist nichtleer. Es gibt eine Lösung. Die Lösung ist x = 2,4 und y = 2,2. Die Zielfunktion beträgt dort 16,2. (2) Max. F(x,y) = x-y 2x-y <= 0 x+2y <= 1 2x+y >= 2 x,y >= 0 Bild Der zulässige Bereich ist leer. Es gibt keine Lösung da die Nebenbedingungen widersprüchlich sind. (3) Max. F(x,y) = 2x+y -x+y <= 1 x+3y >= 6 x,y >= 0 Bild Der zulässige Bereich ist nichtleer. Allerdings ist die Funktion nicht nach oben beschränkt. (4) Jetzt lösen wir das Beispiel (1) mit der zusätzlichen Nebenbedingung, dass die Variablen x und y ganzzahlig sein sollen. Max. F(x,y) = 4x+3y x+3y <= 9 -x+2y >= 2 x,y >= 0, x und y ganzzahlig Bild Der zulässige Bereich ist nichtleer. Genau 4 Punkte sind zulässig. Der Punkt (2;2) ist Lösung. Dort beträgt die Zielfunktion 14.

Besonderheiten beim Lösen von LPs mittels Scilab

Scilab ist ein kostenloses Progamm mit Schwerpunkt numerische lineare Algebra. Es ist erhältlich auf www.scilab.org . Benötigt wird der Befehl linpro: help linpro \sourceon Scilab Hilfe Description ... [x,lagr,f]=linpro(p,C,b [,x0]) Minimize p'*x under the constraints C*x <= b ... \sourceoff D.h. ich muss mein LP so umformen, bis es dasteht wie in der Hilfe. Bemerkungen: (a) Ein Maximierungsproblem kann ich durch Multiplikation des Vektors p mit -1 in ein Minimierungsproblem überführen. (b) Nebenbedingungen der Form Cx >= b kann ich durch Multiplikation von C und b mit -1 in die Form Cneu x <= bneu überführen. Dies gilt auch für einzelne Zeilen. (c) Nebenbedingungen der Form Cx = b kann ich in Ungleichungsform überführen: Cx <= b und -Cx <= -b Ich definiere mir die Matrix Cneu und den Vektor bneu: Cneu = [C; -C]; bneu = [b; -b];. Eine Gleichungsnebenbedingung kann ich immer in 2 Ungleichungsnebenbedingungen überführen. (d) falls gewünscht kann ich auch Unter- und Obergrenzen für x festlegen: ci = [0 0]'; cs = [100 100]'; der Aufruf erfolgt dann mittels [x,lagr,f] = linpro(p,C,b,ci,cs)

Lösungen in Scilab

(1) \sourceon Scilab p = [-4 -3]'; b = [9 -2]'; C = [1 3; 1 -2]; [x,lagr,f] = linpro(p,C,b) \sourceoff --> f = - 16.2 lagr = 2.2 1.8 x = 2.4 2.2 (2) \sourceon Scilab p = [-1 1]'; b = [0 1 -2]'; C = [2 -1; 1 2; -2 -1]; [x,lagr,f] = linpro(p,C,b) \sourceoff --> !--error 127 no feasible solution (3) \sourceon Scilab p = [-2 -1]'; b = [1 -6]'; C = [-1 1; -1 -3]; [x,lagr,f] = linpro(p,C,b) \sourceoff --> !--error 123 fonction not bounded from below (4) Ganzzahlige lineare Optimierungsprobleme kann ich nicht durch einen einzelnen Scilab-Befehl lösen.

Besonderheiten beim Lösen von LPs/ILPs mittels Octave

Octave ist ein kostenloses Programm mit Schwerpunkt numerische lineare Algebra. Es ist erhältlich auf www.gnu.org/software/octave/ . Benötigt wird der Befehl glpk. Bemerkungen: (a) Mit s = 1 löse ich ein Minimierungsproblem, mit s = -1 löse ich ein Maximierungsproblem. (b) in lb und ub kann ich Unter- und Obergrenzen für x festlegen (c) ctype = "U" entspricht einer Zeile mit Ax <= b ctype = "S" entspricht einer Zeile mit Ax = b ctype = "L" entspricht einer Zeile mit Ax >= b (d) vartype = "C" die entsprechende Variable wird als kontinuierlich angesehen vartype = "I" die entsprechende Variable wird als ganzzahlig angesehen (e) falls alle Variablen vom Typ "C" sind, habe ich eine lineares Optimierungsproblem (LP) falls alle Variablen vom Typ "I" sind, habe ich ein ganzzahliges lineares Optimierungsproblem (ILP)

Lösungen in Octave

(1) \sourceon Octave c = [4,3]'; a = [1,3;1,-2]; b = [9, -2]'; lb = [0, 0]'; ub = []; ctype = "UU"; % U: Ax <= b vartype = "CC"; % c continous (LP) s = -1; % Maximierung param.msglev = 1; % keine Programmausgaben param.itlim = 100; [xmin,fmin,status,extra] = ... glpk(c,a,b,lb,ub,ctype,vartype,s,param); \sourceoff >status status = 180 (Solution is optimal) >xmin xmin = 2.4 2.2 (2) \sourceon Octave c = [1,-1]'; a = [2 -1;1 2; 2 1]; b = [0, 1, 2]'; lb = [0, 0]'; ub = []; ctype = "UUL"; % U: Ax <= b // L: Ax >=b vartype = "CC"; % c continous (LP) s = -1; % Maximierung param.msglev = 1; % keine Programmausgaben param.itlim = 100; [xmin,fmin,status,extra] = ... glpk(c,a,b,lb,ub,ctype,vartype,s,param); \sourceoff > status status = 213 (No primal feasible Solution) (3) \sourceon Octave c = [2,1]'; a = [-1 1; 1 3]; b = [1, 6]'; lb = [0, 0]'; ub = []; ctype = "UL"; % U: Ax <= b / L: Ax >= b vartype = "CC"; % c continous (LP) s = -1; % Maximierung param.msglev = 1; % keine Programmausgaben param.itlim = 100; [xmin,fmin,status,extra] = ... glpk(c,a,b,lb,ub,ctype,vartype,s,param); \sourceoff > status status = 214 (no dual feasible solution) (4) \sourceon Octave c = [4,3]'; a = [1,3;1,-2]; b = [9, -2]'; lb = [0, 0]'; ub = []; ctype = "UU"; % U: Ax <= b vartype = "II"; % i integer (ILP) s = -1; % Maximierung param.msglev = 3; % jetzt mal viele Programmausgaben param.itlim = 100; [xmin,fmin,status,extra] = ... glpk(c,a,b,lb,ub,ctype,vartype,s,param); \sourceoff Bild > status status = 171 (The solution is integer optimal) > xmin xmin = 2 2

Abschluss

Damit endet dieser kleine Artikel zum Lösen linearer Optimierungsprobleme mittels Scilab und Octave. Viele Grüße Ronald Schlagworte für die Arbeitsgruppe Alexandria: Optimierung, lineare Optimierung, Simplexmethode, diskrete Optimierung, ganzzahlige lineare Optimierung, NP-Vollständigkeit, guter Artikel, Scilab, Octave Literatur: Die Beispiele 1,2 und 3 sind aus dem Buch Domschke/Drexl/Schildt/Scholl/Voß "Übungsbuch Operations Research" (Springer). Wer sich eingehender mit linearer Optimierung und Lösungsverfahren beschäftigen will kann beispielsweise von Robert J.Vanderbei "Linear Programming Foundations and Extentions" (Kluwer Academic Publishers) benutzen.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Software :: Optimierung :: Lineare Optimierung :
Lösen von linearen Optimierungsproblemen mittels Scilab und Octave [von Delastelle]  
Plötzlich steht es da: ein Optimierungsproblem, das sich in das Schema max c^T x unter den Nebenbedingungen Ax
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 9650
 
Aufrufstatistik des Artikels
Insgesamt 1783 externe Seitenaufrufe zwischen 2012.01 und 2022.08 [Anzeigen]
DomainAnzahlProz
https://google.com874.9%4.9 %
http://google.de117065.6%65.6 %
https://google.de19711%11 %
http://google.fr1126.3%6.3 %
http://google.it553.1%3.1 %
http://google.se241.3%1.3 %
http://google.li231.3%1.3 %
http://google.ru181%1 %
http://google.fi171%1 %
https://www.startpage.com70.4%0.4 %
https://duckduckgo.com70.4%0.4 %
https://www.ecosia.org60.3%0.3 %
https://www.bing.com110.6%0.6 %
http://ecosia.org50.3%0.3 %
https://metager.de20.1%0.1 %
http://search.globososo.com20.1%0.1 %
http://www.bing.com191.1%1.1 %
http://suche.aol.de10.1%0.1 %
http://search.babylon.com20.1%0.1 %
http://suche.web.de20.1%0.1 %
http://avira-int.ask.com10.1%0.1 %
http://isearch.avg.com10.1%0.1 %
http://www1.delta-search.com10.1%0.1 %
http://www.benefind.de10.1%0.1 %
http://search.sweetim.com10.1%0.1 %
http://search.yahoo.co.jp10.1%0.1 %
http://suche.t-online.de20.1%0.1 %
http://google.com10.1%0.1 %
https://de.search.yahoo.com10.1%0.1 %
http://r.duckduckgo.com10.1%0.1 %
https://startpage.com10.1%0.1 %
http://images.google.de10.1%0.1 %
http://de.yhs4.search.yahoo.com10.1%0.1 %
http://yandex.ru10.1%0.1 %
http://google.sk10.1%0.1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 1730 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (340x)http://google.de/url?sa=t&rct=j&q=
2020-2022 (189x)https://google.de/
2013-2014 (80x)http://google.fr/url?sa=t&rct=j&q=
2012-2013 (75x)http://google.de/url?sa=t&rct=j&q=scilab simplex
201204-04 (69x)http://google.de/url?sa=t&rct=j&q=x ganzzahlig in glpk
2012-2013 (67x)http://google.de/url?sa=t&rct=j&q=software für lineare optimierung
201308-11 (64x)http://google.de/url?sa=t&rct=j&q=optimierungsproblem lösen online
201211-11 (62x)http://google.de/url?sa=t&rct=j&q=software zum lösen linearer optimierungs...
201202-02 (58x)http://google.de/url?sa=t&rct=j&q=wie gut ist oktave mathematik
2020-2022 (57x)https://google.com/
201401-01 (55x)http://google.it/url?sa=t&rct=j&q=
201206-06 (55x)http://google.de/url?sa=t&rct=j&q=wie kann ich linpro laden scilab
201201-01 (53x)http://google.de/url?sa=t&rct=j&q=simplex algorithmus für scilab
201207-07 (47x)http://google.de/url?sa=t&rct=j&q=software zum lösen von optimierungsprobl...
201405-05 (36x)http://google.de/url?sa=t&source=web&cd=2&ved=0CDAQFjAB
201212-12 (36x)http://google.de/url?sa=t&rct=j&q=simplex scilab
201203-03 (32x)http://google.fr/url?sa=t&rct=j&q=linpro scilab no solution
201301-01 (31x)http://google.de/url?sa=t&rct=j&q=software lineare optimierung
201312-12 (29x)http://google.de/url?sa=t&rct=j&q=lineare algebra beispiele octave
201307-07 (25x)http://google.de/url?sa=t&rct=j&q=scilab lösen von lp
201609-11 (25x)http://google.de/search?q=lineare optimierung scilab
201503-03 (24x)http://google.se/url?sa=t&rct=j&q=
2015-2016 (23x)http://google.li/url?sa=t&rct=j&q=
201304-04 (23x)http://google.de/url?sa=t&rct=j&q=simplex verfahren scilab
201403-03 (21x)http://google.de/url?sa=t&rct=j&q=lösung lineares optimierungsproblem
201208-08 (18x)http://google.de/url?sa=t&rct=j&q=software für lineare optimierungsproblem...
201303-03 (18x)http://google.de/url?sa=t&rct=j&q=scilab + beispiele
202105-05 (18x)https://google.com/url?sa=t
201410-10 (18x)http://google.ru/url?sa=t&rct=j&q=
201302-02 (17x)http://google.fi/url?sa=t&rct=j&q=
201209-09 (17x)http://google.de/url?sa=t&rct=j&q=software lösung lineare optimierung
202005-05 (10x)https://google.com/search?client=firefox-b-m
202112-12 (8x)https://google.de
2020-2022 (7x)https://www.startpage.com/
2020-2022 (7x)https://duckduckgo.com/
202101-12 (6x)https://www.ecosia.org/
202102-09 (6x)https://www.bing.com/
202101-01 (4x)https://www.bing.com/search?form=MOZLBR

[Top of page]

"Mathematik: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave" | 6 Comments
The authors of the comments are responsible for the content.

Re: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
von: Marco_D am: Fr. 17. Juli 2009 21:52:54
\(\begingroup\)Hallo Ronald, schöner Artikel. Zeigt zudem, dass OpenSource auch einiges kann. Die Mühe hat sich in meinen Augen gelohnt 😉 Gruß Marco\(\endgroup\)
 

Re: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
von: gaussmath am: Fr. 17. Juli 2009 22:35:11
\(\begingroup\)Hey Ronald, schöner Artikel und dann noch dein erster! Gut, dass du auch an die Schlagworte für die Arbeitsgruppe Alexandria gedacht hast: ...,guter Artikel,... 😛 😁 Grüße, Marc\(\endgroup\)
 

Re: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
von: irdy am: Mo. 20. Juli 2009 16:16:14
\(\begingroup\)Trotz einiger Mängel, ein sehr guter Artikel. ILPs können nicht konvex sein, deshalb IP bzw MIP. Gruss Irdy\(\endgroup\)
 

Re: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
von: Delastelle am: Di. 21. Juli 2009 00:41:13
\(\begingroup\)Hallo, erst mal danke für eure Kommentare. Das Beispiel (4) und ganzzahlige Lösungen habe ich nur aufgenommen da der Befehl "glpk" von Octave eben mehr kann als ein einfacher Simplexalgorithmus. Viele Grüße Ronald \(\endgroup\)
 

Re: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
von: Delastelle am: Mo. 19. Februar 2018 21:52:23
\(\begingroup\)Hallo, ich habe jetzt in meinem Notizbuch ( http://www.matheplanet.com/matheplanet/nuke/html/fav.php?uname=Delastelle ) auch ein Simplexverfahren für Turbo Pascal/Free Pascal. Dort werden auch Zwischenschritte der Berechnung angegeben. Viele Grüße Ronald\(\endgroup\)
 

Re: Lösen von linearen Optimierungsproblemen mittels Scilab und Octave
von: Delastelle am: Do. 04. April 2019 23:36:38
\(\begingroup\)Hallo, neuere Scilab-Versionen (wie beispielsweise 5.5.2) kennen den Befehl "linpro" nicht mehr. Als Ersatz bietet sich das Karmarkar-Verfahren an (Befehl: "karmarkar"). Siehe auch: https://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?rd2&topic=218487&start=0#p1599791 Viele Grüße Ronald\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]