Grundlegendes Optimierungsproblem von n 1-Grad-Variablen

Question

Nehmen wir an, ich habe die Funktion $f(x_1, x_2, x_3) = ax_1 + bx_2 + cx_3$ und die Einschränkung, dass $x_1+x_2+x_3=1$ mit jedem $x_1,x_2,x_3\geq0$. Ich möchte finden$\operatorname{argmax} f$. Es ist ziemlich offensichtlich, dass ich zur Maximierung dieser Funktion herausfinden werde, welche von$a,b,c$ ist die größte und die entsprechende Variable wird sein $1$ während der andere $2$ sind $0$.

Zum Beispiel habe ich $f(x_1, x_2, x_3) = 7x_1 + 3x_2 + 4x_3$, dann $\operatorname{argmax} f$ ist einfach $x_1=1, x_2=0, x_3=0$.

Meine Frage betrifft, wie man beweisen kann, dass dies für eine beliebige Anzahl von Personen zutrifft $x_1,\dots,x_n$ wo Sie einfach die wählen $x_i$ mit dem größten Koeffizienten zu sein $1$ und all die anderen zu sein $0$. Jede Hilfe, wo man anfangen soll, wäre dankbar!

Answer 1

Sie möchten maximieren $\sum_j c_j x_j$vorbehaltlich \ begin {align} \ sum_j x_j & = 1 \\ x_j & \ ge 0 && \ text {für alle$j$} \ end {align} Let$M = \max_j c_j$ mit argmax $j^*$. Wie Sie bemerkt haben, Einstellung$x_{j^*}=1$ und alles andere $x_j=0$ erfüllt die Bedingungen und ergibt eine Untergrenze von $M$auf den maximalen Zielwert. Um das zu zeigen$M$ ist auch eine Obergrenze, beachten Sie, dass $$\sum_j c_j x_j \le \sum_j M x_j = M \sum_j x_j = M \cdot 1 = M.$$

(In Bezug auf die lineare Programmierung ist der Doppelmultiplikator von $M$ für die Gleichheitsbeschränkung wird ein Optimalitätszertifikat bereitgestellt.)