-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathskript.latex
4203 lines (3794 loc) · 166 KB
/
skript.latex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% Einige zusätzliche Informationen für rubber
% rubber erkennt nicht, dass die Datei weg kann, daher sagen wir es ihm
% rubber: clean $base.thm
% rubber soll nach Änderungen an der Datei nochmal bauen
% rubber: watch $base.thm
% rubber: index.tool xindy
% rubber: index.language german-din
\RequirePackage[l2tabu,orthodox]{nag} % nag überprüft den Text auf veraltete
% Befehle oder solche, die man nicht in LaTeX verwenden
% soll -- l2tabu-Checker in LaTeX
\RequirePackage[ngerman=ngerman-x-latest]{hyphsubst} % einbinden der neuen
% Trennmuster, diese korrigieren einige Fehler der alten
% und bieten mehr Trennstellen
\documentclass[halfparskip*,ngerman,draft,twoside]{scrreprt}
\usepackage{babel}
\usepackage{index}
\usepackage{xcolor}
\usepackage[draft=false,colorlinks,bookmarksnumbered,linkcolor=blue,breaklinks]{hyperref}
\usepackage[latin1]{inputenc}
\usepackage{nicefrac}
\usepackage{lmodern} % Latin Modern
% \usepackage{type1ec} % cm-super
\usepackage[T1]{fontenc} % T1-Schriften notwendig für PDFs
\usepackage{textcomp} % wird benötigt, damit der \textbullet
% für itemize in lmodern gefunden wird.
\usepackage[intlimits,leqno]{amsmath}
\usepackage[all,warning]{onlyamsmath} % warnt bei Verwendung von nicht
% amsmath-Umgebungen z.\,B. $$...$$
\usepackage{amssymb} % wird für \R, \C,... gebraucht
\usepackage{fixmath} % ISO-konforme griech. Buchstaben
\usepackage[amsmath,thmmarks,hyperref]{ntheorem} % für die Theorem-Umgebungen
% (satz, defini, bemerk)
\usepackage{xspace} % wird weiter unten gebraucht
\usepackage{paralist} % besseres enumerate und itemize und neue
% compactenum/compactitem; s. texdoc paralist
\usepackage{svn} % Zum Auswerten und ordentlichen Darstellen der
% SVN-Schlüsselwörter (s. vor \begin{document})
% dafür muss in SVN noch das Flag svn:keywords
% auf "LastChangedRevision LastChangedDate"
% gesetzt werden
\usepackage{ellipsis} % Korrektur für \dots
\usepackage{fixltx2e}
\usepackage[final]{microtype} % Verbesserung der Typographie
\usepackage{amsfonts}
\usepackage{eurosym} %% Eingabe des Eurosymbols
\usepackage{sistyle} %% fuer die korrekte Angabe von Einheiten
\usepackage{braket} %% Zur Eingabe von Mengen: A={x| x>2}
\usepackage{booktabs} %% schöne Linien in Tabelle
\usepackage{wasysym}
\usepackage{txfonts}
\usepackage{mathtools} % Zur Definition von \abs und \norm
\usepackage{todonotes} % definiert den Befehl \todo{} um sich leicht
% Damit auch die Zeichen im Mathemode in Überschriften fett sind
% <news:[email protected]>
\addtokomafont{sectioning}{\boldmath}
% nach dem Theoremkopf wird ein Zeilenumbruch eingefügt, die Schrift des
% Körpers ist normal und der Kopf wird fett gesetzt
\theoremstyle{break}
\theorembodyfont{\normalfont}
\theoremheaderfont{\normalfont\bfseries}
\theoremnumbering{arabic}
% Die folgenden Umgebungen werden einzeln nummeriert und am Ende jedes
% Kapitels zurückgesetzt
\newtheorem{satz}{Satz}[chapter]
\newtheorem{bem}[satz]{Bemerkung}
\newtheorem{defin}[satz]{Definition}
\newtheorem{bsp}[satz]{Beispiel}
\newtheorem{verf}[satz]{Verfahren}
\newtheorem{lemma}[satz]{Lemma}
\newtheorem{kor}[satz]{Korollar}
% Die folgenden Theoremumgebungen bekommen keine Nummer
%\theoremstyle{nonumberbreak}
%\newtheorem{fakt}{Fakt}
\theoremheaderfont{\scshape}
\theorembodyfont{\normalfont}
% Das Zeichen am Ende eines Beweises
\theoremsymbol{\ensuremath{_\blacksquare}}
% \theoremsymbol{q.\,e.\,d.}
\newtheorem{proof}{Beweis:}
% Hier die Definition, wie \autoref die Umgebungen nennen soll, die mit
% \newtheorem definiert wurden
\newcommand*{\satzautorefname}{Satz}
\newcommand*{\bemautorefname}{Bemerkung}
\newcommand*{\definautorefname}{Definition}
\newcommand*{\bspautorefname}{Beispiel}
\newcommand*{\verfautorefname}{Verfahren}
\newcommand*{\lemmaautorefname}{Lemma}
\newcommand*{\korautorefname}{Korollar}
\newcommand*{\proofautorefname}{Beweis}
% Zwischen Unter- und Unterunterabschnitten sollte nicht unterschieden
% werden.
\renewcommand*{\subsectionautorefname}{Abschnitt}
\renewcommand*{\subsubsectionautorefname}{Abschnitt}
\pagestyle{headings}
\newcommand*{\R}{\mathbb{R}} % reelle Zahlen
%\newcommand*{\C}{\mathbb{C}} % komplexe Zahlen
\newcommand*{\N}{\mathbb{N}} % natürliche Zahlen
%\newcommand*{\Q}{\mathbb{Q}} % gebrochene Zahlen
%\newcommand*{\Z}{\mathbb{Z}} % ganze Zahlen
%% kalligrafische Zeichen
\newcommand*{\FF}{\mathcal{F}}
\newcommand*{\FB}{\mathcal{B}}
\newcommand*{\FN}{\mathcal{N}}
% Wenn irgendwo Unklarheiten zum Inhalt im Skript auftreten, können sie
% einfach mit \help{Ich verstehe das nicht} hervorgehoben werden. Dies
% macht es leichter sie alle zu finden und auch ganz einfach
% auszublenden, indem man den Befehl einfach leer definiert
\newcommand*{\help}[1]{\todo[color=green!40]{#1}}
% Um wichtige Begriffe im Text überall gleich vorzuheben (gleiches
% Markup), sollte dieser Befehl verwendet werden. Das Argument wird
% automatisch als Indexeintrag verwendet. Dieser kann aber auch als
% optionales Argument selbst bestimmt werden.
\newcommand*{\highl}[2][]{\textbf{\boldmath{#2}}%
\ifthenelse{\equal{#1}{}}{\index{#2}}{\index{#1}}%
}
% Befehl für die Darstellung der Gliederungsüberschriften im Index
\newcommand*{\lettergroup}[1]{\minisec{#1}}
% Für Leute, die nicht gern o.\,B.\,d.\,A. jedesmal eintippen wollen
\newcommand*{\obda}{o.\,B.\,d.\,A.\xspace}
%% unter den Nebenbedingungen ist auch zu lang zum Eintippen
\newcommand*{\unb}{unter den Nebenbedingungen\xspace}
% Um sicherzustellen, dass jeder Betrag-/jede Norm links und rechts die
% Striche bekommt, sind diese Befehle da. Damit kann man nicht die
% rechten Striche vergessen und es wird etwas übersichtlicher. (Vorschlag
% ist aus amsldoc) \abs[\big]{\abs{a}-\abs{b}} \leq \abs{a+b}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
% Das original Epsilon sieht nicht so toll aus
\renewcommand*{\epsilon}{\varepsilon}
% ... und mancheinem gefällt auch das Phi nicht
\renewcommand*{\phi}{\varphi}
\DeclareMathOperator{\co}{co} %% konvexe Huelle
\DeclareMathOperator{\rg}{rg} %% Rang
\DeclareMathOperator{\diag}{diag} %% Diagonalmatrix
\makeindex
\SVN $LastChangedRevision$
\SVN $LastChangedDate$
\begin{document}
\title{Lineare Optimierung}
\author{bei Prof.\,Walter Alt}
\date{Semester: SS 2006 und WS 2009}
\maketitle
\clearpage
\chapter*{Vorwort}
{\itshape
Dieses Dokument wurde als Skript für die auf der
Titelseite genannte Vorlesung erstellt und wird jetzt im Rahmen des
Projekts
"`\href{http://uni-skripte.lug-jena.de/}
{Vorlesungsskripte der Fakultät für Mathematik}
\href{http://uni-skripte.lug-jena.de/}{und Informatik}"'
weiter betreut. Das
Dokument wurde nach bestem Wissen und Gewissen angefertigt. Dennoch
garantiert weder der auf der Titelseite genannte Dozent, die Personen,
die an dem Dokument mitgewirkt haben, noch die
Mitglieder des Projekts für dessen Fehlerfreiheit. Für etwaige Fehler
und dessen Folgen wird von keiner der genannten Personen eine Haftung
übernommen. Es steht jeder Person frei, dieses Dokument zu lesen, zu
verändern oder auf anderen Medien verfügbar zu machen, solange ein
Verweis auf die Internetadresse des Projekts
\url{http://uni-skripte.lug-jena.de/}
enthalten ist.
Diese Ausgabe trägt die Versionsnummer~\SVNLastChangedRevision\ und ist
vom \SVNDate. Eine (mögliche) aktuellere Ausgabe ist auf der Webseite
des Projekts verfügbar.
Jeder ist dazu aufgerufen, Verbesserungen, Erweiterungen und
Fehlerkorrekturen für das Skript einzureichen bzw. zu melden oder diese
selbst einzupflegen -- einfach eine E-Mail an die
\href{mailto:[email protected]}{Mailingliste
\texttt{<[email protected]>}} senden. Weitere Informationen
sind unter der oben genannten Internetadresse verfügbar.
Hiermit möchten wir allen Personen, die an diesem Skript mitgewirkt
haben, vielmals danken:
\begin{itemize}
\item \href{mailto:[email protected]}{Jens Kubieziel
\texttt{<[email protected]>}} (2006)
\item \href{mailto:[email protected]}{Jörg Bader
\texttt{<[email protected]>}} (2009/2010)
\end{itemize}
}
\clearpage
\pdfbookmark[0]{Inhaltsverzeichnis}{inhaltsverzeichnis}
\tableofcontents
\clearpage
\pdfbookmark[0]{Auflistung der Sätze}{theoremlist}
\chapter*{Auflistung der Theoreme}
\pdfbookmark[1]{Sätze}{satzlist}
\section*{Sätze}
\theoremlisttype{optname}
\listtheorems{satz}
\pdfbookmark[1]{Definitionen}{definilist}
\section*{Definitionen}
% \theoremlisttype{all}
\listtheorems{defin}
\chapter{Einführung}
\section{Grundbegriffe und Beispiele}
Die Zielstellung in der linearen Optimierung ist die Betrachtung einer
Funktion $f\colon\R^n\rightarrow \R$ mit dem Ziel der Berechnung eines
Minimums von $f$.
\begin{bsp}
\begin{inparaenum}[(1)]
\item $f\colon\R\rightarrow\R$ mit $f(x)=x^2$ hat genau ein Minimum.
\item $f\colon\R\rightarrow\R$ mit $f(x)=x$ ist nicht nach unten
beschränkt und hat daher kein Minimum.
\item $f\colon\R\rightarrow\R$ mit $f(x)=\sin x$ ist $2\pi$"~periodisch und
hat unendlich viele Minima.
\end{inparaenum}
\end{bsp}
\begin{bsp}
Die Funktion $f\colon\R^2\rightarrow\R$ mit $f(x_1,x_2)= x_1 \sin (x_1+
x_1 x_2\sin(x_2))$.
\end{bsp}
Die Norm auf $\R^n$ ist im allgemeinen die euklidische Norm,
d.\,h. für $x\in \R^n, x=(x_1,\dotsc, x_n)^{T}$ ist $\norm{
x}=\sqrt{\sum_{i=1}^n x_i^2}$. Für
$\tilde{x}\in\R$ und $r>0$ ist die \highl[Kugel!offene]{offene Kugel} um
$\tilde{x}$ mit
Radius $r$ definiert durch $B(\tilde{x}, r)=\{x\in\R^n\colon \norm{
x-\tilde{x} }< r\}$.
\paragraph{Allgemeine Formulierung des Optimierungsproblems}
Sei $D\subset \R^n$ nichtleer und offen, $f\colon D\rightarrow \R,
\FF\subset D$:
\begin{gather}
\label{eq:P}
\min_{x\in\FF} f(x)
\end{gather}
Die Funktion $f$ heißt \highl[Zielfunktion]{Ziel-} oder \highl{Kostenfunktion}.
\begin{description}
\item[$\FF=D$] unrestringiertes Optimierungsproblem
(Optimierungsproblem ohne Nebenbedingungen)
\item[$\FF\subset D$] restringiertes Optimierungsproblem
(Optimierungsproblem mit Nebenbedingungen), $\FF$ heißt
\highl[Menge!zulässige]{zulässige Menge} und wird meist durch (Un-)gleichungen beschrieben.
\end{description}
\begin{bsp}
$n=1, D=\R, \min f(x)=x^3$, NB: $x\geq 1$.\\
In diesem Fall ist $\FF=\{x\in\R\colon x\geq 1\}$
\end{bsp}
\begin{defin}[Lokale Minima]
Ein Punkt $\tilde{x}\in\FF$ (zulässiger Punkt) heißt
\highl[Minimalpunkt!lokaler]{lokaler Minimalpunkt} von $f$ auf $\FF$ oder
\highl[Lösung!lokale]{lokale Lösung} von
\autoref{eq:P}, falls es ein $r>0$ mit $f(x)\geq f(\tilde{x})$ für
alle $x\in\FF\cap B(\tilde{x}, r)$ gibt.
Ein Punkt $\tilde{x}\in\FF$ heißt \highl[Minimalpunkt!strikter
lokaler]{strikter lokaler Minimalpunkt} von $f$ auf $\FF$ oder
\highl[Lösung!strikte lokale]{strikte lokale Lösung} von
\autoref{eq:P}, falls es ein $r>0$ mit $f(x)>f(\tilde{x})$ für alle
$x\in \FF\cap B(\tilde{x}, r)$ mit $x\neq \tilde{x}$ gibt.
Die zugehörigen Funktionswerte heißen (strikter) \highl[Minimalwert!lokaler]
{lokaler Minimalwert} oder (striktes) \highl[Minimum!lokales]{lokales Minimum}.
\end{defin}
\begin{defin}[Globales Minimum]
Ein Punkt $\tilde{x}\in\FF$ heißt \highl[Minimalpunkt!globaler]{globaler
Minimalpunkt} von $f$ auf $\FF$ oder globale Lösung von
\autoref{eq:P}, falls gilt $\forall x\in\FF\colon
f(x)\geq f(\tilde{x})$
\end{defin}
\begin{bem*}
Die Optimierungsaufgabe $\max g(x)$ unter den Nebenbedingungen
$x\in\FF$ ist äquivalent zur Minimierung. Das Problem wird als $\min
f(x) \coloneqq -g(x)$ definiert.
Anstatt lokales Minimum sagt man auch
\highl[Minimum!relatives]{relatives Minimum}. Anstatt striktes
Minimum sagt man auch
\highl[Minimum!strenges]{strenges Minimum}.
Eine lineare Optimierungsaufgabe besteht aus einer linearen Funktion
$f$ und $\FF$ wird aus linearen (Un-)gleichungen beschrieben.
\end{bem*}
\begin{bsp}[Produktionsplanung]
\label{bsp:prodplan-16}
Eine Firma produziert vier Lacke $L_1, L_2, L_3, L_4$. Dabei ist der
Gewinn pro Kilogramm Lack:
\begin{asparaitem}
\item 1,50 \euro{} für $L_1$
\item 1,00 \euro{} für $L_2$
\item 2,00 \euro{} für $L_3$
\item 1,40 \euro{} für $L_4$
\end{asparaitem}
Nebenbedingungen für die wöchentliche Produktion:
\begin{itemize}
\item von $L_1$ und $L_2$ können zusammen maximal \SI{1300}{kg} produziert werden
\item von $L_1, L_3, L_4$ können zusammen maximal \SI{2000}{kg} produziert werden
\item Mindestproduktion von $L_4$ sind \SI{800}{kg}
\item von $L_3$ sind nicht mehr als \SI{500}{kg} zu verkaufen
\end{itemize}
Ziel ist die Maximierung des Gewinns. Wir bezeichnen mit $x_i$ die
Menge, die von Lack $L_i$ produziert wird. Der Gewinn ist $1,5x_1+ x_2+
2x_3+ 1,4x_4$, d.\,h. es ist $f(x_1,x_2,x_3,x_4)= -1,5x_1 -x_2 -2x_3
-1,4x_4$ unter den Nebenbedingungen:
\begin{align*}
x_1 + x_2 &\leq 1300 & x_4 &\geq 800 \Leftrightarrow -x_4\leq -800\\
x_1+x_3+x_4 &\leq 2000 & x_3 &\leq 500
\end{align*}
zu minimieren.
Weiterhin ergibt sich aus praktischen Überlegungen $x_i\geq 0$. Wir
formulieren das Problem in Matrixschreibweise: Sei $c=-(1,5, 1, 2, 1,4)^{T}$.
Dann hat die Zielfunktion die Form $c^Tx$. Mit
\begin{align*}
A &=
\begin{pmatrix}
1&1&0&0\\
1&0&1&1\\
0&0&0&-1\\
0&0&1&0
\end{pmatrix} & b &=
\begin{pmatrix}
1300\\2000\\-800\\500
\end{pmatrix}
\end{align*}
können wir die Nebenbedingungen in der Form $Ax\leq b$ schreiben. Dann
können wir das Optimierungsproblem in der Form $\min c^Tx$ unter den
Nebenbedingungen $Ax\leq b, x\geq 0$ schreiben.
\end{bsp}
\begin{bsp}\label{bsp:17}
Eine Tierfarm kauft drei verschiedene Kornsorten, um daraus
Futtermittel zu mischen.
\begin{tabular}{l|r|r|r|r}
& $S_1$ & $S_2$ & $S_3$ & Mindestbedarf\\
\bottomrule
Nährstoff A & 2 & 3 & 7 & 1250\\
Nährstoff B & 1 & 1 & 0 & 250\\
Nährstoff C & 5 & 3 & 0 & 900\\
Nährstoff D & 0,6 & 0,25 & 1 & 232,5\\
\bottomrule
Kosten & 41 & 35 & 96 & \\
\end{tabular}
Gesucht ist eine Mischung, die den Nährstoffbedarf deckt und dabei
möglichst billig herzustellen ist.
Wir bezeichnen mit $x_i, i=1,2,3$ diejenige Menge, die von der
Kornsorte $s_i$ eingekauft wird. Dabei müssen wir die Mengen so
bestimmen, dass die Gesamtkosten der Futtermischung minimiert wird,
d.\,h. die Funktion $41x_2+ 35x_2+ 96x_3$ soll minimiert
werden. Folgende Nebenbedingungen gelten:
\begin{itemize}
\item Sinnvollerweise ist $x_i\geq 0, i=1,2,3$
\item Um den Nährstoffbedarf zu decken, müssen wir fordern:
\begin{align*}
2x_1 + 3x_2 + 7x_3 &\geq 1250 & x_1 + x_2 &\geq 250\\
5x_1 + 3x_2 &\geq 900 & 0,6x_1 + 0,25x_2+ x_3 &\geq 232,5
\end{align*}
\item Wir definieren weiter:
\begin{align*}
c =
\begin{pmatrix}
41\\35\\96
\end{pmatrix}
\qquad A =
\begin{pmatrix}
2 & 3 & 7 \\
1 & 1 & 0\\
5 & 3 & 0\\
0,6 & 0,25 & 1
\end{pmatrix}
\qquad b =
\begin{pmatrix}
1250\\250\\900\\232,5
\end{pmatrix}
\end{align*}
\item Somit können wir das Problem in der Form $\min c^Tx$ unter den
Nebenbedingungen $Ax\geq b, x\geq0$ schreiben.
\end{itemize}
\end{bsp}
\paragraph{Allgemein zur Produktplanung}
Es sollen bestimmte Güter aus Rohstoffen hergestellt werden. Durch die
Zielfunktion soll der Gewinn maximiert bzw. die Kosten minimiert
werden und als Nebenbedingung sollen keine negativen Mengen produziert
bzw. benutzt werden.
\section{Numerische Lösung von Optimierungsproblemen}
Allgemein sei das Problem
\begin{gather*}
\min f(x) \text{ mit } x\in \FF
\end{gather*}
mit der Zielfunktion $f\colon\R^n\rightarrow\R$ und der zulässigen Menge
$\FF \subset \R^n$ zu lösen.
Numerische Verfahren sind Iterationsverfahren. Sie berechnen ausgehend
von einem Startpunkt $x^{(0)}$ eine Folge $\{x^{(k)}\}\subset\R^n,
k=1,2,3, \ldots$ mit dem Ziel:
\begin{itemize}
\item nach endlich vielen Schritten $m$ ist $x^{(m)}$ eine Lösung oder,
falls dies nicht möglich ist,
\item deren Grenzwert ist eine Lösung.
\end{itemize}
Diese numerische Verfahren berechnen nur eine Näherungslösung. Da die
Zielfunktion zu minimieren ist, versucht man, die Folge $x^{(k)}$ so
zu berechnen, dass $f(x^{(k+1)})< f(x^{(k)})$ ist. Dies nennt man
\highl{Abstiegsverfahren}. Prinzipiell geht man dabei wie folgt vor:
\begin{itemize}
\item Man berechnet eine \highl{Abstiegsrichtung} $d^{(k)}$, d.\,h. eine
Richtung $d^{(k)}$ mit $f(x^{(k)} + td^{(k)})< f(x^{(k)})$ für
hinreichend kleines $t>0$.
\item Man berechnet eine geeignete Schrittweite $t_k$.
\end{itemize}
Ist $\FF\neq\R^n$, dann fordert man in der Regel
\begin{itemize}
\item $x^{(0)}\in\FF$
\item $x^{(k)}\in\FF, k=1,2,\ldots$; Dazu bestimmt man die
\highl[Abstiegsrichtung!zulässigen]{zulässige
Abstiegsrichtung} $d^{(k)}$ mit der Eigenschaft, dass
$x^{(k)}+td^{(k)} \in\FF$ für hinreichend kleines $t>0$.
\end{itemize}
Es gibt verschiedene Verfahren, die diese Vorgehensweise für bestimmte
Klassen von Optimierungsproblemen realisieren:
\begin{itemize}
\item Lineare Optimierungsprobleme: Simplexverfahren, Innere-Punkte-Verfahren
\item Differenzierbare Optimierungsprobleme: Gradientenverfahren
\end{itemize}
Es gibt auch allgemeine Verfahren, die keine speziellen
Voraussetzungen an die Zielfunktion und die Nebenbedingungen machen.
\begin{bsp}[Mutations-Selektions-Verfahren]
\begin{asparaenum}
\item Wähle $x^{(0)}\in\FF$. Setze $k\coloneqq 0$
\item Mutation: Berechne einen neuen Punkt $v^{(k)}$ durch zufällige
Änderung $x^{(k)}$.
\item Selektion: Ist $v^{(k)}\in\FF$ und $f(v^{(k)})< f(x^{(k)})$,
dann $x^{(k+1)}\coloneqq v^{(k)}$. Andernfalls $x^{(k+1)}\coloneqq x^{(k)}$.
\item Setze $k\coloneqq k+1$ und gehe zu Punkt 2.
\end{asparaenum}
Dieses Verfahren hat kein Abbruchkriterium. Eine häufig benutzte
Mutation ist die Berechnung von $v^{(k)}_i = x^{(k)}_i +t_k (d^{(k)}_i
-0,5)$. Dabei ist $d^{(k)}_i\in[0,1]$ zufällig erzeugt und $t_k$ muss
durch Probieren bestimmt werden.
\end{bsp}
\begin{bsp}
Sei folgendes Optimierungsproblem gestellt:
\begin{align*}
\min -(2000x_1+ 1200x_2+ 1000x_3+ 1500x_4) &\\
x_1+x_2+x_3+x_4 &\leq 16\\
1200x_2 &\geq 4000\\
1200x_2 - 1500x_4 &\leq 0\\
2000x_1 &\leq 7000\\
xi &\geq 0 \qquad i=1,\ldots, 4
\end{align*}
Das Simplexverfahren berechnet die Lösung in zwei Schritten. Zuerst
wird $x^{(0)}\in\FF$ ermittelt. Dazu benötigt das Verfahren vier
Iterationen. Danach erfolgt die eigentliche Berechnung in zwei
Iterationen und es stoppt mit $x=
\begin{pmatrix}
3,5\\3,33\\0\\9,16
\end{pmatrix}, f(x)=-24750$.
Das Mutations-Selektions-Verfahren wird mit einer Schrittweite
$t_0=0,8$ gestartet. Diese wird immer nach 5000 Schritten halbiert und
nach 100000 Iterationen wird abgebrochen. Das ermittelte Ergebnis ist $x=
\begin{pmatrix}
3,5\\3,333\\1,6557\cdot 10^{-7}\\9,1666
\end{pmatrix}, f(x)=-24749,999985$.
\end{bsp}
\chapter{Grundlagen der linearen Optimierung}
Ein lineares Optimierungsproblem wird im englischen auch als "`linear
program"' bezeichnet. Daher rührt die oft benutzte Abkürzung \emph{LP} her. Das
Problem besteht aus einer linearen Zielfunktion $f(x)=c^Tx$ und
Nebenbedingungen, die in Form von Gleichungen und Ungleichungen
definiert werden.
Es gibt verschiedene "`Standardformen"' von linearen
Optimierungsproblemen.
\section{Lineare Optimierungsprobleme}
\subsection{Standardformen von linearen Optimierungsproblemen}
\begin{defin}[Lineares Optimierungsproblem in allgemeiner Form]
Ein lineares Optimierungsproblem in allgemeiner Form (LPA) ist die
Aufgabe:
\begin{align*}
\min c^Tx \text{ mit }
l_x\leq x\leq u_x,
l_A\leq A^{(1)}x\leq u_A,
A^{(2)}x= b
\end{align*}
wobei gilt: $x, c, l_x, u_x\in\R^n, A^{(1)}$ ist eine
$m_1\times n$-Matrix, $l_A, u_A\in\R^{m_1}, A^{(2)}$ ist eine
$m_2\times n$-Matrix, $b\in\R^{m_2}$.
\end{defin}
\begin{bsp}
Eine Supermarktkette stellt ein Billiggetränk auf Weinbasis
her. Grundlage ist ein Landwein mit Kosten von 1~\euro{} pro
Liter. Weitere Zutaten sind Zuckerlösung (1,20~\euro{} pro Liter) und
Konservierungsmittel (1,80~\euro{} pro Liter). Das Ziel ist die
Herstellung einer möglichst billigen Mischung. Dabei müssen folgende
Restriktionen beachtet werden.
\begin{asparaitem}
\item mindestens ein Drittel Zuckerlösung
\item mindestens halb soviel Wein wie Zuckerlösung
\item Anteil des Konservierungsmittels mindestens halb so groß wie
der Anteil der Zuckerlösung und höchstens so groß wie der Anteil
der Zuckerlösung
\item Anteil des Konservierungsmittels mindestens die Hälfte des
Weinanteils
\end{asparaitem}
Wir legen folgende Optimierungsvariablen fest:
\begin{description}
\item[$x_1$] Anteil der Zuckerlösung
\item[$x_2$] Anteil des Konservierungsmittels
\item[$x_3$] Anteil des Weins
\end{description}
Die Kosten $1,2x_1+1,8x_2+x_3$ sind unter folgenden Restriktionen zu
minimieren.
\begin{align*}
x_1, x_2, x_3 &\geq 0 & x_1+x_2+x_3&=1 & x_1&\geq \frac{1}{3}\\
\frac{1}{2}x_1\leq x_2 &\leq x_1 & 2x_3&\geq x_1 & x_2&\geq
\frac{1}{2} x_3
\end{align*}
\end{bsp}
\begin{bem*}
\begin{itemize}
\item Ungleichungen zwischen Vektoren sind komponentenweise zu
verstehen.
\item Sinnvollerweise gilt: $l_x\leq u_x, l_A\leq u_A$. Gilt für
einen Index $i\in\{1, \ldots, n\}\colon l_{x_i}=u_{x_i}$, d.\,h. wir
fordern $l_{x_i}=x_i=u_{x_i}$, dann ist $x_i$ fest.
\item Das lineare Funktional $\FF=\{x\in\R^n \colon l_x\leq x\leq u_x,
l_A\leq A^{(1)}\leq u_A, A^{(2)}x=b\}$ heißt
\highl[Menge!zulässige]{zulässige Menge}
(feasible set).
\item Ein Punkt $\tilde{x}\in\FF$ (zulässiger Punkt) heißt
\highl{optimal}, falls $\forall x\in\FF\colon f(x)\geq f(\tilde{x})$
gilt, d.\,h. $\tilde{x}$ ist globales Minimum von $f$ auf $\FF$.
\end{itemize}
\end{bem*}
\paragraph{Mögliche Transformationen}
\begin{itemize}
\item Sei $a\in\R^n, b\in\R$. Eine Ungleichung vom Typ $a^Tx\leq -b$
ist äquivalent zu $-a^Tx\geq b$.
\item Eine Gleichung $a^Tx=b$ ist äquivalent zu $-a^Tx=-b$ und
äquivalent zu $a^Tx\leq b$ und $a^Tx\geq b$.
\item Gibt es für $x_i$ keine Vorzeichenbedingung, dann kann man zwei
neue Variablen $x^+_i, x^-_i$ mit $x_i=x^+_i-x^-_i$ mit $x^+_i,
x^-_i\geq 0$ einführen.
\end{itemize}
\begin{bsp}
Wir betrachten das Problem, $\min x_1-x_2$ unter der
Nebenbedingungen $x_1\geq 0, x_2\leq 5$. Die Lösung ist mit $x_1=0,
x_2=5$ eindeutig bestimmt. Um ein Problem mit Vorzeichenbedingung
für \emph{alle} Variablen zu erhalten, definieren wir $x^+_2, x^-_2$
und erhalten das Problem $\min x_1-x^+_2+x^-_2$ mit den
Nebenbedingungen $x_1, x^+_2, x^-_2\geq 0, x^+_2-x^-_2\leq 5$.
\end{bsp}
\begin{defin}[Lineares Optimierungsproblem in kanonischer Form]
Ein lineares Optimierungsproblem in kanonischer Form (LPK) ist die Aufgabe:
\begin{align*}
\min c^Tx \text{ mit } Ax\geq b, x\geq0
\end{align*}
mit $c\in\R^n, A$ ist eine $m\times n$-Matrix, $b\in\R^m$. In diesem
Fall ist die zulässige Menge $\FF= \{x\in\R^n\colon Ax\geq b, x\geq 0\}$.
\end{defin}
\begin{bsp}
siehe \autoref{bsp:prodplan-16} (Produktionsplanung)
\begin{gather*}
\max 1,5x_1+ x_2+ 2x_3+ 1,4x_4 \\
x_1+ x_2+ \leq 1300 \qquad x_1+ x_3+ x_4 \leq 2000 \qquad x_4 \leq
800\qquad x_3 \leq 500\\
c =-
\begin{pmatrix}
1,5\\1\\2\\1,4
\end{pmatrix}\qquad
A =
\begin{pmatrix}
-1 & -1 & 0 & 0\\
-1 & 0 & -1 &-1\\
0 & 0 & 0 & 1\\
0 & 0 & -1 & 0
\end{pmatrix}\qquad
b=
\begin{pmatrix}
-1300\\-2000\\800\\-500
\end{pmatrix}
\end{gather*}
\end{bsp}
\begin{defin}[Lineares Optimierungsproblem in Normalform]
Ein lineares Optimierungsproblem in Normalform oder Standardform ist
die Aufgabe
\begin{gather*}
\min c^{T} x\text{ \unb } Ax=b, x\geq 0
\end{gather*}
mit $c\in\R^{n}, b\in\R^{m}$ und $A$ ist eine $m\times n$-Matrix.
Die zulässige Menge ist
\begin{gather*}
\FF=\set{x\in\R^{n}|Ax=b,x\geq 0 }
\end{gather*}
\end{defin}
\begin{bem*}
\begin{itemize}
\item Wir können \obda $b\geq 0$ setzen.
\item Bei $n$ Variablen und $m$ Gleichungsrestriktionen folgt, dass
ein lineares Gleichungssystem vorliegt.
\item In der Regel fordert man $m<n$.
\end{itemize}
\end{bem*}
Wie kann man nun ein Problem in kanonischer Form in Standardform
umwandeln? Die Lösung ist hier die Einführung von
\highl{Schlupfvariablen}.
\begin{bsp}
Sei folgende Aufgabe gegeben:\\
Maximiere $x_{1}+x_{2}$ unter den Nebenbedingungen $x_{1}+
3x_{2}\leq 13, 3x_{1}+x_{2}\leq 15, -x_{1}+x_{2}\leq 3, x_{i}\geq
0$. Wir führen die \highl[Schlupfvariable]{Schlupfvariablen}
$x_{3}, x_{4}, x_{5}$ ein und ersetzen die Ungleichung durch:
\begin{align*}
x_{1} + 3x_{2} + x_{3} &= 13 & 3x_{1} + x_{2} + x_{4} &= 15\\
-x_{1} + x_{2} + x_{5} &= 3 & x_{i} &\geq 0\\
\end{align*}
\end{bsp}
Allgemein lässt sich der Sachverhalt so formulieren:
Sei ein lineares Problem in kanonischer Form gegeben. Um das Problem
in Standardform zu transformieren, führen wir die Schlupfvariablen
\[y=\begin{pmatrix}y_{1}\\\vdots\\y_{m}\end{pmatrix} =
\begin{pmatrix}x_{n+1}\\\vdots\\x_{n+m}\end{pmatrix}\in \R^{m}\]
ein und erhalten somit das Problem
\[\min_{x\in\R^{n}, y\in\R^{m}} c^{T}x =(c^{T}, 0^{T}_{m})
\begin{pmatrix}x\\y\end{pmatrix}\] unter den Nebenbedingungen $x,y\geq
0$, d.\,h.
\[Ax-y=b=(A-I_{m})\begin{pmatrix}x\\y\end{pmatrix}\]
\begin{bsp}[Frannie verkauft Holz]
\label{bsp:28}
Frannie verkauft jedes Jahr drei
Festmeter\footnote{\url{http://de.wikipedia.org/wiki/Festmeter}}
Holz. Zwei Kunden machen folgendes Angebot. Kunde1 bietet 90 \euro{}
für einen halben Festmeter und Kunde2 bietet 150~\euro{} für einen
Festmeter. Seien also $x_{1}$ die Anzahl der halben Festmeter an Kunde1 und
$x_{2}$ die Anzahl der Festmeter an Kunde2. Die Einnahmen sollen
maximiert werden. Damit ergibt sich folgendes Optimierungsproblem:
\[\min -90x_{1} - 150x_{2}\]
unter den Nebenbedingungen:
\[0,5x_{1} + x_{2} \leq 3 \quad x_{i} \geq 0\]
Wir betrachten die Geraden $x_{2}=-0,5x_{1} + 3$ und $-90x_{1}-150
x_{2}=r$
\end{bsp}
\subsection{Grafische Lösung von linearen Optimierungsproblemen}
\label{sec:212-grafLsg}
Hierzu muss man sich auf $n=2$ beschränken und es sind nur
Ungleichungen als Nebenbedingungen zugelassen
\todo{Grafik einfügen}
Zur Bestimmung der Lösungsmenge werden die Randgeraden eingezeichnet
und die richtige Lösungshälfte bestimmt.
\subsection{Lösbarkeit von linearen Optimierungsproblemen}
Hier kann man drei Fälle unterscheiden:
\begin{enumerate}
\item Lösung ist eindeutig bestimmt
\item Es gibt unendlich viele Lösungen.
\item Es gibt keine Lösung.
\end{enumerate}
\subsection{Software zur Lösung}
Zur Lösung von linearen Optimierungsproblemen kann man u.\,a. MATLAB
oder auch Scilab benutzen.
MATLAB ist eine kommerzielle Lösung der Firma The MathWorks, Inc. und
hat die Webseite \url{http://www.mathworks.de/}.
Scilab ist eine kostenlose Entwicklung aus Frankreich. Sie wurde am INRIA
entwickelt und ist über die Webseite \url{http://www.scilab.org/} verfügbar.
\begin{bsp}
\todo{Beispiel einfügen}
\end{bsp}
\begin{bsp}
\todo{Beispiel einfügen}
\end{bsp}
\begin{bsp}
\todo{Beispiel einfügen}
\end{bsp}
\begin{bsp}
\todo{Beispiel einfügen}
\end{bsp}
\section{Konvexe Mengen}
\begin{defin}[Konvexe Menge]
Ein Menge $C\subset\R^{n}$ heißt \highl{konvex}\index{Menge!konvexe},
falls mit $x,y\in C$ und $\alpha\in(0,1)$ auch der Punkt
$(1-\alpha)x+ \alpha y$ Element von $C$ ist.
\end{defin}
\begin{bem*}
Seien $x,y\in C$. Dann heißt $[x,y] \coloneqq \set{(1-\alpha)x + \alpha y|
\alpha\in [0,1]}$ \highl{Verbindungsstrecke}
von $x$ und $y$. Konvexität heißt $x,y\in C\Rightarrow[x,y]\in C$.
\end{bem*}
\begin{bsp}
Sei $n=1$. Dann sind die konvexen Mengen Intervalle. Für den Fall,
dass $n$ beliebig ist, gilt:
Sei $x\in\R^{n}$ und $r\in\R$. Wir betrachten $B(x, r)=\set{y\in\R^{n}|
\norm{ y-x}<r}$ und behaupten, dass $B(x,r)$ konvex ist. Also ist zu
zeigen, dass $v=(1-\alpha)y+\alpha x\in B(x,r)$ bzw. $\norm{v-x}<r$. Denn
sei $y,z\in B(x,r)$ und $\alpha\in(0,1)$. Dann folgt:
\begin{align*}
\norm{ v-x} &= \norm{ (1-\alpha)y+\alpha z -x} = \norm{
(1-\alpha)y+\alpha z -(1-\alpha)x-\alpha x}\\
&= \norm{ (1-\alpha)(y-x)+\alpha(z-x)} \leq \norm{
(1-\alpha)(y-x)} + \norm{ \alpha(z-x)}\\
&\leq (1-\alpha) \underbrace{\norm{ y-x}}_{< r} + \alpha
\underbrace{\norm{ z-x}}_{<r}\\
&< (1-\alpha+\alpha)r=r
\end{align*}
\end{bsp}
\begin{bsp}
Sei $(s,r)\in\R^{n}\times\R, s\neq 0$, wobei $0$ der Nullvektor ist.
Die Hyperebene $H_{s,r}=\set{x\in\R^{n}| \langle s,x\rangle=r}$ ist
konvex. Denn sei $y,z\in H_{s,r}$ und $\alpha\in[0,1]$ beliebig.
Also ist zu zeigen, $v=(1-\alpha)y+\alpha z\in H_{s,r}$, d.\,h.
$\langle s,v\rangle =r= \langle s,(1-\alpha)y + \alpha z\rangle=
(1-\alpha)\underbrace{\langle s,y\rangle}_{=r} +\alpha
\underbrace{\langle s,z\rangle}_{=r} =r$. Gleiches gilt für den
offenen Halbraum $\set{x\in\R^{n}| \langle s,x\rangle<r}$ und den
abgeschlossenen Halbraum $\set{x\in\R^{n}| \langle s,x\rangle\leq r}$.
\end{bsp}
\begin{lemma}
\label{lem:konvDurchsch}
Ist $(C_{j})_{j\in J}$ eine beliebige Familie konvexer Mengen, dann
ist auch der Durchschnitt dieser Mengen $C\coloneqq \bigcap_{j\in J} C_{j}$
konvex.
Denn seien $x,y\in C$ und $\alpha\in[0,1]$ beliebig. Dann folgt für
alle $j\in J$, dass $x,y\in C_{j}$ und weiter ist $(1-\alpha)x +
\alpha y\in C_{j}$. Damit gilt aber $(1-\alpha)x + \alpha y\in C$.
\end{lemma}
\begin{bsp}
Sei $(a^{(i)}, b^{(i)})\in\R^{n}\times\R, i=1,\ldots,s-1, s, s+1,\ldots,
m$. Weiter sei
\begin{gather*}
K=\set{x\in\R^{n}| \langle a^{(i)}, x\rangle = b^{(i)}, i=1,\ldots,s,
\langle a^{(i)}, x\rangle\leq b^{(i)}, i=s+1, \ldots, m}
\end{gather*}
die Lösungsmenge eines Systems linearer Gleichungen und
Ungleichungen. Man nennt $K$ auch \highl{Polyeder}. Es wird
behauptet, dass $K$ konvex ist.
Sei $C_{i}= \set{x\in\R^{n}| \langle a^{(i)}, x\rangle=b_{i}}$ mit
$i=1,\ldots,s$ bzw. $C_{i}= \set{x\in\R^{n}| \langle a^{(i)},
x\rangle\leq b_{i}}$ mit $i=s+1,\ldots,n$. Dann ist
$K=\bigcap_{i=1}^{m} C_{i}$ konvex nach
\autoref{lem:konvDurchsch} und obigem Beispiel.
Ein lineares Optimierungsproblem in allgemeiner, kanonischer oder
Standardform ist vom Typ $\min c^{T}x$ \unb $x\in K$, wobei $K$ ein
Polyeder ist.
\end{bsp}
\begin{satz}[Lineare Optimierung auf konvexen Mengen]
\label{satz:218-lokglobLsg}
Ist $c\in\R^{n}$ und $K\subset \R^{n}$ nichtleer und konvex, dann
ist jede lokale Lösung des Problems $\min c^{T}x$ \unb $x\in K$ auch
globale Lösung. Weiterhin ist die Lösungsmenge konvex.
\begin{proof}
Sei $\tilde{x}\in K$ eine beliebige lokale Lösung. Dann existiert
ein $r>0$ mit $f(x)\geq f(\tilde{x})$ für alle $x\in K\cap
B(\tilde{x}, r)$. Sei weiter $y\in K, y\neq \tilde{x}$ beliebig.
Wir zeigen: $f(y)\geq f(\tilde{x})$. Dazu nutzen wir die
Konvexität aus. Da $K$ konvex ist, gilt $\tilde{x}+\alpha
(y-\tilde{x})=(1-\alpha)\tilde{x}+\alpha y\in K$. Weiter gilt für
hinreichend kleines $\alpha>0$ (speziell für $\alpha<\frac{r}{\norm{
y- \tilde{x}}}$), dass $\tilde{x}+\alpha(y-\tilde{x})\in B(\tilde{x}, r)$
ist. Für $0<\alpha<\min\{1, \frac{r}{\norm{ y-
\tilde{x}}}\}$ gilt also: $\tilde{x}+\alpha(y-\tilde{x})\in
K\cap B(\tilde{x}, r)$. Somit folgt:
$f(\tilde{x}+\alpha(y-\tilde{x}))\geq f(\tilde{x})$. Dies ist
gleichbedeutend mit $c^{T}(\tilde{x}+\alpha(y-\tilde{x}))\geq
c^{T}\tilde{x}\Rightarrow c^{T}\tilde{x} +\alpha c^{T}y -\alpha
c^{T} \tilde{x}\geq c^{T}\tilde{x} \Rightarrow \alpha c^{T} y \geq
\alpha c^{T}\tilde{x} \Rightarrow c^{T}y \geq c^{T}\tilde{x}
\Rightarrow f(y)\geq f(\tilde{x})$.
Seien $\tilde{x}, \tilde{y}$ beliebige Lösungen. Dann sind diese
auch globale Lösungen, d.\,h. $f(\tilde{x})=f(\tilde{y})$. Sei
$\alpha\in[0,1]$. Nun ist zu zeigen, dass auch
$(1-\alpha)\tilde{x} +\alpha \tilde{y}$ Lösung ist. Es gilt:
$f((1-\alpha)\tilde{x}+\alpha\tilde{y})=c^{T} ((1-\alpha)\tilde{x}
+\alpha\tilde{y})= (1-\alpha)c^{T}\tilde{x} +\alpha c^{T}\tilde{y}
= (1-\alpha)f(\tilde{x}) + \alpha f(\tilde{y})=
(1-\alpha)f(\tilde{x}) + \alpha f(\tilde{x}) =f(\tilde{x})$.
\end{proof}
\end{satz}
\begin{bem*}
Die Aussage von \autoref{satz:218-lokglobLsg} gilt allgemein
für konvexe Zielfunktionen. Dabei heißt eine Funktion $f\colon
\R^{n}\rightarrow \R$ konvex auf $K$, wenn gilt: $f((1-\alpha) x+
\alpha y)\leq (1-\alpha)f(x)+\alpha f(y)$ für alle $x,y\in K$ und
$\alpha\in[0,1]$. Im Spezialfall $f(x)=c^{T}x$ gilt sogar
$f((1-\alpha) x+\alpha y)=(1-\alpha)x+\alpha y$.
\end{bem*}
\begin{defin}[Konvexkombination]
Eine \highl{Konvexkombination} von Punkten
$x^{(1)},\ldots,x^{(k)}\in\R^{n}$ ist ein Punkt der Form
$\sum_{i=1}^{k} \alpha_{i} x^{(i)}$ mit $\alpha_{i}\geq 0,
i=1,\ldots,k$ und $\sum_{i=1}^{k} \alpha_{i}=1$.
\end{defin}
\begin{bem*}
Für $k=2$ gilt: $\alpha_{1} x^{(1)} + \alpha_{2} x^{(2)}$ ist
Konvexkombination mit $\alpha_{1}, \alpha_{2}\geq 0,
\alpha_{1}+\alpha_{2}=1\Leftrightarrow \alpha_{1} = 1-\alpha_{2}$.
\end{bem*}
\begin{satz}
Eine Menge $C\subset\R^{n}$ ist dann konvex, wenn sie alle
Konvexkombinationen von Punkten in $C$ enthält.
\begin{proof}
Dies stellt eine Beweisidee dar:
In der Gegenrichtung zeigt man: Wenn $C$ alle Konvexkombinationen
von Punkten in $C$ enthält, dann enthält sie alle
Konvexkombinationen von zwei Punkten in $C$. Dann folgt, dass $C$
konvex ist.
In der Hinrichtung nimmt man an, dass $C$ konvex ist. Weiter sei
$x^{(1)},\ldots,x^{k}\in C$ beliebig und
$\alpha_{1},\ldots,\alpha_{k}\in\R$ mit $\alpha_{i}\geq 0,
i=1,\ldots, k, \sum_{i=1}^{k} \alpha_{i}=1$. Dann ist zu zeigen,
dass $\sum_{i=1}^{k} \alpha_{i} x^{(i)}\in C$. Dieser Beweis wird
per Induktion geführt.
\end{proof}
\end{satz}
\begin{defin}[Konvexe Hülle]
Sei $A\in\R^{n}$ beliebig. Die \highl[Hülle!konvexe]{konvexe
Hülle} von $A$ ist die Menge
\begin{gather*}
\co A:=\bigcap_{A\subset C} C
\end{gather*}
Dies ist die kleinste konvexe Menge, die $A$ umfasst.
\end{defin}
\begin{lemma}
Für eine beliebige Menge $A\subset\R^{n}$ ist $\co A= \set{x\in\R| x
\text{ ist Konvexkombination von Punkten in } A} =: B$.
\begin{proof}
Für die Richtung $\co A\subset B$ gilt, dass $B$ konvex ist und das
$A\subset B$. Somit folgt, $\co A\subset B$.
Für $B\subset\co A$ gilt: Sei $C$ eine beliebige konvexe Menge mit
$C\supset A\Rightarrow C$ enthält alle Konvexkombinationen von
Punkten in $A$, d.\,h. $C\supset B\Rightarrow B\subset
\bigcap_{C\supset A} C \subset \co A$.
\end{proof}
\end{lemma}
\section{Hauptsatz der linearen Optimierung}
Ziel dieses Abschnittes ist, zu zeigen, wenn ein lineares
Optimierungsproblem eine Lösung hat, existiert eine Ecke, die Lösung
ist.
\begin{defin}[Geometrische Definition einer Ecke]
Sei $\FF$ die zulässige Menge eines linearen Optimierungsproblems.
Dann heißt ein Punkt $x\in\FF$ \highl{Ecke} von $\FF$,
falls $x$ nicht als Konvexkombination $x=(1-\alpha)y+\alpha z$ mit
$y,z\in\FF, y\neq z, \alpha\in(0,1)$ darstellbar ist.
\end{defin}
\begin{bem}
\label{bem:224}
Ist $\FF$ die zulässige Menge eines linearen Optimierungsproblems
mit Vorzeichenbedingung $x\geq 0_{n}$ und ist der Nullpunkt
$0_{n}\in\FF$, dann ist $0_{n}$ eine Ecke von $\FF$. Denn für
$y,z\in\FF$ mit $y\neq z, \alpha\in(0,1)$ ist $0_{n}= (1-\alpha)
y+\alpha z\Rightarrow y=z=0_{n}$.
\end{bem}
% \begin{bsp}
% siehe das lineare Optimierungsproblem aus
% \autoref{sec:212-grafLsg}
% \end{bsp}
\begin{bsp}\label{bsp:227}
Sei $\FF\subset\R^{2}$ die zulässige Menge eines linearen
Optimierungsproblems in kanonischer Form. Es ist definiert durch:
$2x_{1}+3x_{2}\leq 6, x_{1}\leq 2, x_{i}\geq 0$.
\end{bsp}
\begin{bsp}\label{bsp:228}
\todo{Beispiel einfügen}
\end{bsp}
Ab jetzt betrachten wir nur noch lineare Optimierungsprobleme in
Standardform, d.\,h. mit der zulässigen Menge $\FF=\set{x\in\R^{n}|
Ax=b, x\geq 0}$. Dabei ist $A$ eine $m\times n$-Matrix. Die
zulässigen Punkte $x\in\FF$ sind insbesondere Lösung des linearen
Gleichungssystems $Ax=b$.
Es gibt folgende Spezialfälle:
\begin{itemize}
\item[$n=m$] Hat $A$ den vollen Rang, dann hat das System $Ax=b$
genau eine Lösung: $x=A^{-1}b$. Gilt für $x$ auch noch $x\geq
0_{n}\Rightarrow \FF=\{x\}$. Andernfalls ist $\FF=\emptyset$.
\item[$m>n$] In diesem Falle gibt es mehr Gleichungen als Variablen
(überbestimmtes System). Dies ist für die Optimierung uninteressant.
\item[$m<n$] Dieses System hat weniger Gleichungen als Variablen. Die
Menge $\set{x\in\R^{n}| Ax=b}$ ist dann ein affiner Unterraum.
Spezialfall: Der Rang der Matrix $A$ ist gleich $m$.
\end{itemize}
\begin{satz}[Charakterisierung einer Ecke]
\label{satz:228}
Sei $\FF=\set{x\in\R^{n}| Ax=b, x\geq 0_{n}}, A\in\R^{m\times n},
b\in\R^{m}, m\leq n$ die zulässige Menge eines linearen
Optimierungsproblems in Standardform. Dann gilt: $x\in\FF$ ist genau
dann Ecke von $\FF$, wenn die zu positiven Komponenten von $x$
gehörenden Spaltenvektoren linear unabhängig sind, d.\,h. wenn die
Vektoren $A_{.i}$ linear unabhängig sind.