Problème d'optimisation de base de n variables à 1 degré

Question

Disons que j'ai la fonction $f(x_1, x_2, x_3) = ax_1 + bx_2 + cx_3$ et la contrainte que $x_1+x_2+x_3=1$ avec chaque $x_1,x_2,x_3\geq0$. je veux trouver$\operatorname{argmax} f$. Il est assez évident que pour maximiser cette fonction, je trouverai lequel des$a,b,c$ est la plus grande et sa variable correspondante sera $1$ tandis que l'autre $2$ sont $0$.

Par exemple, j'ai $f(x_1, x_2, x_3) = 7x_1 + 3x_2 + 4x_3$, puis $\operatorname{argmax} f$ est simplement $x_1=1, x_2=0, x_3=0$.

Ma question concerne la manière de prouver que cela est vrai pour un nombre quelconque $x_1,\dots,x_n$ où vous choisissez simplement le $x_i$ le coefficient le plus élevé étant $1$ et tous les autres à être $0$. Toute aide pour savoir par où commencer serait appréciée!

Answer 1

Vous voulez maximiser $\sum_j c_j x_j$sous réserve de \ begin {align} \ sum_j x_j & = 1 \\ x_j & \ ge 0 && \ text {pour tous$j$} \ end {align} Soit$M = \max_j c_j$ avec argmax $j^*$. Comme vous l'avez noté, le réglage$x_{j^*}=1$ et tous les autres $x_j=0$ satisfait les contraintes et donne une borne inférieure de $M$sur la valeur objective maximale. Pour montrer que cela$M$ est également une limite supérieure, notez que $$\sum_j c_j x_j \le \sum_j M x_j = M \sum_j x_j = M \cdot 1 = M.$$

(En termes de programmation linéaire, le double multiplicateur de $M$ car la contrainte d'égalité fournit un certificat d'optimalité.)