Un programa lineal para maximizar una fracción

Question

Dado $\lambda_1,\ldots,\lambda_n \geq 0$ y un $n\times n$ matriz $A$ Deseo maximizar la relación $$ \frac{\lambda_1x_1 + \cdots + \lambda_nx_n}{x_1+\cdots+x_n}, $$ donde $x_1,\ldots,x_n \geq 0$ no son todos cero y $A\mathbf{x} \leq \mathbf{0}$ suponiendo que $\mathbf{x} = (x_1,\ldots,x_n)^T$ .

Me gustaría formular este problema como un programa lineal, pero no estoy seguro de cómo proceder. Primero pensé en dejar que $y_i = x_i/(x_1 + \cdots + x_i + \cdots +x_n)$ pero esto no parece funcionar. Me parece que debería intentar traducir el problema a otro equivalente que sea más fácil de razonar. Cuando se trata de fracciones con las variables, ¿cómo se debe escribir un LP en forma canónica?

Cualquier pista o ayuda será muy apreciada.

Answer 1

Este es un programa lineal fraccionario . Tenga en cuenta que si $x$ es una solución, entonces también lo es $\alpha x$ para cualquier $\alpha>0$ . Se puede aprovechar esto exigiendo que el denominador sea exactamente 1, convirtiendo el resultado en un LP: \begin {array}{ll} \text {maximizar} & \sum_i \lambda_i x_i \\ \text {sujeto a} & \sum_i x_i = 1 \\ & A x \leq 0 \\ & x \geq 0 \end {array}