resueltos - Usando min/max*dentro de*un programa lineal entero

programacion lineal entera ppt

Question

Estoy tratando de configurar un programa lineal en el que la función objetivo agregue un peso extra al max de las variables de decisión multiplicadas por sus respectivos coeficientes.

Teniendo esto en cuenta, ¿hay una manera de utilizar operadores max o max dentro de la función objetivo de un programa lineal?

Ejemplo:

Minimize
    (c1 * x1) + (c2 * x2) + (c3 * x3) + (c4 * max(c1*x1, c2*x2, c3*x3)) 
subject to
    #some arbitrary integer constraints:
    x1 >= ...
    x1 + 2*x2 <= ... 
    x3 >= ...
    x1 + x3 == ...

Tenga en cuenta que (c4 * max(c1*x1, c2*x2, c3*x3)) es el término "peso adicional" que me preocupa. Dejamos que c4 denote el coeficiente de "peso extra". Además, tenga en cuenta que x1 , x2 y x3 son enteros en este ejemplo en particular.

Creo que lo anterior podría estar fuera del alcance de lo que ofrece la programación lineal. Sin embargo, ¿quizás hay una manera de hackear / reformatear esto en un programa lineal válido?

Si este problema está completamente fuera del alcance de la programación lineal, tal vez alguien pueda recomendar un paradigma de optimización que sea más adecuado para este tipo de problema. (Cualquier cosa que me permita evitar enumerar y verificar manualmente todas las soluciones posibles sería útil).

Answer 1

Agregue una variable auxiliar, digamos x4, con restricciones:

x4 >= c1*x1
x4 >= c2*x2
x4 >= c3*x3  
Objective += c4*x4