Cómo minimizar una función lineal sujeta a $11$ ¿limitaciones de desigualdad?

Question

No estoy seguro si esta pregunta califica para este lugar, pero tengo una ecuación lineal en la forma:

$$\begin{array}{ll} \ Ax \geq b\end{array}$$

En VBA en Excel.

con A = 11 filas, 4 columnas, con fracciones aleatorias entre 0 y 1.

x = una matriz de 4 filas y 1 columna y cada $$\begin{array}{ll}\ x_i >=0 \end{array}$$ B es una matriz de 11 filas y 1 columna que sólo contiene 1's.

Parece que se trata de un [programa lineal] (LP) y voy a investigarlo.

$$\begin{array}{ll} \text{minimize} & x_1 + x_2 + x_3 + x_4\\ \text{subject to} & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.5 x_4 \geq 1\\ & 0.1 x_1 + 0.4 x_2 + 0.3 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.3 x_3 + 0.4 x_4 \geq 1\\ & 0.4 x_1 + 0.9 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.6 x_3 + 0.1 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.4 x_2 + 0.9 x_3 + 0.2 x_4 \geq 1\\ & 0.6 x_1 + 0.4 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.7 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.5 x_3 + 0.6 x_4 \geq 1\end{array}$$ Me preguntaba cuál es el procedimiento de minimización mientras se satisface la ecuación, para la suma de todas las x_1 a x_4.

Pensé en tomar la suma minimizada de todas las fracciones en 1 fila de la matriz A y resolver para eso = 1, para que uno supiera que todas las demás son al menos mayores, pero no estaba seguro, si eso está garantizado para proporcionar la suma minimizada de x's.

Además, ese enfoque produciría infinitas soluciones con 1 fila y 4 variables.

Answer 1

Tiene lo siguiente programa lineal (LP)

$$\begin{array}{ll} \text{minimize} & x_1 + x_2 + x_3 + x_4\\ \text{subject to} & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.5 x_4 \geq 1\\ & 0.1 x_1 + 0.4 x_2 + 0.3 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.3 x_3 + 0.4 x_4 \geq 1\\ & 0.4 x_1 + 0.9 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.6 x_3 + 0.1 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.4 x_2 + 0.9 x_3 + 0.2 x_4 \geq 1\\ & 0.6 x_1 + 0.4 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.7 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.5 x_3 + 0.6 x_4 \geq 1\\ & x_1, x_2, x_3, x_4 \geq 0\end{array}$$

Utilizando PuLP ,

from pulp import *

# decision variables
x_1 = LpVariable("x_1")
x_2 = LpVariable("x_2")
x_3 = LpVariable("x_3")
x_4 = LpVariable("x_4")

# define linear problem (LP)
prob = LpProblem("problem", LpMinimize)
prob += x_1 + x_2 + x_3 + x_4   # objective function
# add 4 nonnegativity constraints
prob += x_1 >= 0
prob += x_2 >= 0
prob += x_3 >= 0
prob += x_4 >= 0
# add 11 inequality constraints to the LP
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.5*x_4 >= 1   
prob += 0.1*x_1 + 0.4*x_2 + 0.3*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.3*x_3 + 0.4*x_4 >= 1
prob += 0.4*x_1 + 0.9*x_2 + 0.1*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.6*x_3 + 0.1*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.4*x_2 + 0.9*x_3 + 0.2*x_4 >= 1
prob += 0.6*x_1 + 0.4*x_2 + 0.1*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.7*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.5*x_3 + 0.6*x_4 >= 1

# solve ILP
prob.solve()

# print results
print LpStatus[prob.status]
print value(x_1)
print value(x_2)
print value(x_3)
print value(x_4)

obtenemos

Optimal
0.0
0.0
1.4285714
1.4285714

Answer 2

Cada fila, considerada como igualdad, representa un plano de 4 dimensiones, normal al vector de coeficientes ( $\mathbf a$ ), y el avión está "distante" $1$ desde el origen (donde "distancia" es el producto punto del vector posición de los puntos del plano con $\mathbf a$ ) .
Cada desigualdad representa entonces el semiespacio limitado por el plano y que contiene puntos a "distancia" mayor que $1$ desde el origen.
Dado que los coeficientes son todos positivos, entonces una región ilimitada de puntos cuya proyección sobre los distintos $\mathbf a$ es mayor que $1$ seguramente existe.
Por término medio, el punto de solución más cercano al origen se situará en el $(1,1,1,1)$ dirección.
Así que en tu caso la única simplificación que veo factible es empezar y buscar un punto que esté en la dirección de la resultante de los coeficientes, y comprobar las desigualdades a partir de aquellas cuyo vector de coeficientes esté más alejado de la media.