Programación lineal con valores objetivo.

Question

Estoy tratando de averiguar la solución general de un problema min-max. La forma general del problema es la siguiente:

  x1 +   x2 + ... +   xn  = T
a1x2 + a2x2 + ... + anxn  = At * T
  x1                     >= 0
  x1                     <= T1
         x2              >= 0
         x2              <= T2
            ...
                      xn >= 0
                      xn <= Tn

Donde T y At son valores objetivo suministrados por el usuario.

a1..an son multiplicadores conocidos para las variables x1..xn respectivamente.

T1..Tn son valores máximos conocidos para cada variable x1..xn respectivamente.

Se trata esencialmente de un problema de programación lineal multiobjetivo. Mi objetivo es obtener un valor lo más cercano posible a los valores objetivo T y At. El problema es que la mayoría de los problemas de programación lineal tratan de maximizar o minimizar el resultado (en este caso, sería T y At), sin embargo, mi objetivo es proporcionar valores para x1..xn que estén lo más cerca posible de los valores particulares.

Mi formación en matemáticas no es tan fuerte como probablemente debería ser, pero he estado investigando para resolver este problema.

¿Sería el mejor enfoque mover los valores T y At * T a la izquierda como constantes, y tratar de minimizar la función (es decir, lo más cercano a cero como sea posible)? Si ese es el caso, ¿cómo podría abordar esto para una solución? La mayoría de los ejemplos para este tipo de problema que he visto no tienen constantes dentro de la función objetivo. ¿Simplemente se ignoran en términos de la matriz de solución? Eso significa que no es tan útil. Tal vez, ignorar las constantes, y comparar las soluciones propuestas a esas constantes, y volver a calcular si están fuera de una tolerancia básica, mediante la adición de restricciones adicionales?

--- EDITAR --- Basado en las sugerencias de @calculus, he llegado a lo siguiente.

Estoy intentando utilizar un algoritmo simplex para resolver este problema. El algoritmo toma una matriz MxN de coeficientes de restricción ([A]), un vector de longitud M de límites superiores de restricción ([b]) y un vector de longitud N de coeficientes objetivo.

¿Puede alguien confirmar que los objetos que estoy utilizando son correctos?

c = [0, 0, ... 0, 1, 1, 1, 1]  

donde la primera parte corresponde a los coeficientes de x1..xn, y los últimos 4 1's corresponden a los coeficientes de y3+, y3-, y4+ e y4-.

b = [T1, T2, ..., Tn, T, AtT] 

donde estos son los límites superiores para cada individuo x1..xn, y las soluciones para las ecuaciones sum(xn), y sum(anxn) respectivamente.

A = 1, 0, ... 0,  0,  0,  0,  0
    0, 1, ... 0,  0,  0,  0,  0
          ...
    0, 0, ... 1,  0,  0,  0,  0
    1, 1, ... 1, -1,  1,  0,  0
   a1, a2,...an,  0,  0, -1,  1

donde el primer lote de filas corresponde a las filas xn <= Tn, luego la 2ª línea corresponde a x1 + .. xn - y3+, + y3- = T y la última línea corresponde a a1x1 + ... anxn - y4+ + y4- = AtT

¿Tiene esto sentido?

--- Editar 2 ---

Utilicé un problema conocido con una solución para probar esto.

T = 1000, At = 1,5, a1 = 5, a2 = 1, T1 = 500, T2 = 1000.

Esto se puede resolver aritméticamente:

x + y = 1000,       (x1+..+xn = T)
5x + y = 1500       (a1x1+...+anxn = AtT)

resulta en x = 125, y = 875

así que he creado las matricias necesarias:

b = [500, 1000, 1000, 1500]
c = [0, 0, 1, 1, 1, 1]
A = |1, 0,  0, 0,  0, 0|
    |0, 1,  0, 0,  0, 0|
    |1, 1, -1, 1,  0, 0|
    |5, 1,  0, 0, -1, 1|

pero el solucionador que estoy usando dice que el programa no tiene límites.

Answer 1

Dejemos que

$x_1 + x_2 + ... + x_n=y_1$

y $a_1x_2 + a_2x_2 + ... + a_nx_n = y_2$ las dos restricciones adicionales.

La función objetivo provisional sería $|y_1-T|+|y_2-At\cdot t|$ para calcular la suma de las dos diferencias. No tiene importancia si las diferencias son positivas o negativas o no.

Para deshacerse de los valores absolutos, hay que definir:

1. $y_3=y_1-T$ y $y_4=y_2-At\cdot t$

La función objetivo es ahora $|y_3|+|y_4|$

2. $|y_3|=y_3^++y_3^-$ y $|y_4|=y_4^++y_4^-$

Y finalmente la función objetivo es

$\texttt{min} \ \ y_3^++y_3^-+y_4^++y_4^-$

Transformando $y_3$ y $y_4$

$y_3=y_3^+-y_3^-$ y $y_4=y_4^+-y_4^-$

Las dos restricciones adicionales son

$x_1 + x_2 + ... + x_n=y_3^+-y_3^-+T$

$a_1x_2 + a_2x_2 + ... + a_nx_n = y_4^+-y_4^-+At\cdot t$

Las variables son $x_i, y_3^+,y_3^-, y_4^+,y_4^- \geq 0$

Answer 2

Gracias a la ayuda de @calculus, he podido dar con una solución que parece funcionar:

En lugar de intentar tomar el valor absoluto de la diferencia entre el objetivo y la suma de todas las variables, decidí simplemente sumar todas mis funciones objetivo en una, y maximizarla.

Todos los valores tienen que ser positivos y todas las funciones objetivo son sumas con coeficientes positivos, por lo que tomar un valor absoluto de la diferencia no significará realmente mucho, especialmente si hay una restricción que indica que las sumas individuales deben ser menores que un valor objetivo especificado.

El problema final generalizado es:

• suponer una función objetivo en forma de $Z = x_1 + .. + x_n$
• suponer un número arbitrario de funciones objetivo adicionales de [0..i] todas en forma de $Z_i = [ a_1 x_1 + ... + a_n x_n ]_i$
• con condiciones:
  • $(x_i \geq 0)]^1_n$
  • $(x_i \leq T_i)]_n^1$
  • $(x_1+...+x_n) \leq T$ (primer objetivo)
  • $(a_1i x_1i + ... + a_ni x_ni) \leq A_ni * T]_i^1 $ (objetivos adicionales si los hay)
• Donde
  • $A_ni$ es un multiplicador objetivo conocido para cada una de las funciones objetivo adicionales
  • $T$ es una suma objetivo conocida.
  • { $a_ni$ } son multiplicadores conocidos para cada variable $x_n$ para cada función objetivo adicional.
  • $T_i$ es un límite superior conocido para cada variable $x_i$ utilizado comúnmente en todo.

La estructura de la solución es:

• Crear una única función objetivo que sea una suma de todas las funciones:
  • $(1 + a_11 + a_12 + ... a_1i)x1 + ... + (1 + a_n1 + a_n2 + ... + a_ni)x_n$
• Resolver el máximo usando una tabla simplex:
  • $ A = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & & \ddots & \\ 0 & 0 & \cdots & 1 \\ 1 & 1 & \cdots & 1 \\ a_11 & a_21 & \cdots & a_n1 \\ \vdots & & \ddots & \\ a_1i & a_2i & \cdots & a_ni \end{bmatrix}$
  • $ b = \begin{bmatrix} T_1 & T_2 & \cdots & T_n & T & A_1 & \cdots & A_i \end{bmatrix}$
  • $ c = \begin{bmatrix} (1 + a_11 + a_12 + ... a_1i) & \cdots & (1 + a_n1 + a_n2 + ... + a_ni) \end{bmatrix}$

La solución es una colección de valores de x[0..n-1] a partir del resultado del simplex, proporcionando la cantidad de cada fuente requerida para totalizar el valor objetivo T, restringido por los multiplicadores A[0..i]

Answer 3

Minimizar $d$

donde

$d>T-x_1-x_2-x_3-...-x_n$

$d>x_1+x_2+x_3+...x_n-T$

$d>At \times T-a_1x+1-a_2x_2-a_3x_3-...-a_nx_n$

$d>a_1x+1+a_2x_2+a_3x_3+...+a_nx_n- At \times T$

De esta manera $d$ es una medida de lo lejos que estás de tu objetivo deseado (fíjate que tiene que ser en ambos sentidos) y estás intentando minimizar esa medida.