Teoría de la planificación de dos niveles

La teoría de la planificación de dos niveles (o descomposición de Kornai-Liptak ) es un método que descompone grandes problemas de optimización lineal en subproblemas. Esta descomposición simplifica la solución del problema global. El método también modela una forma de coordinar las decisiones económicas para que las empresas descentralizadas actúen de manera que se produzca un óptimo global. Fue introducido por el economista húngaro János Kornai y el matemático Tamás Lipták en 1965. Es una alternativa a la descomposición de Dantzig-Wolfe .

El problema de programación lineal debe tener una estructura especial, conocida como estructura angular de bloques. Esta es la misma estructura requerida para la descomposición de Dantzig-Wolfe:

Hay algunas limitaciones en los recursos generales (D) de las cuales se supone que es responsable una agencia de planificación central, y n bloques de coeficientes (F1 a Fn) que son de interés para las empresas individuales.

La agencia central inicia el proceso proporcionando a cada empresa asignaciones tentativas de recursos que satisfacen las restricciones generales D. Cada empresa optimiza sus variables de decisión locales, suponiendo que las asignaciones globales de recursos son las indicadas. La solución de los problemas de programación lineal de las empresas genera multiplicadores de Lagrange (precios) para los recursos globales, que las empresas transmiten de vuelta a la agencia de planificación.

En la siguiente iteración, la agencia central utiliza la información recibida de las empresas para elaborar una asignación de recursos revisada; por ejemplo, si la empresa i informa un precio sombra elevado para el recurso j, la agencia le asignará más de este recurso y menos a las demás. Las asignaciones provisionales revisadas se envían de vuelta a las empresas individuales y el proceso continúa.

Se ha demostrado que este proceso converge (aunque no necesariamente en un número finito de pasos) hacia la solución global del problema general. (En contraste, el método de Dantzig-Wolfe converge en un número finito de pasos).

Los métodos DW y KL son duales: en DW, el mercado central establece los precios (en función de la demanda de recursos por parte de las empresas) y se los envía a estas, quienes luego modifican las cantidades que demandan; mientras que en KL, la agencia central envía información sobre las cantidades a las empresas y recibe ofertas (es decir, información sobre precios específicos de cada empresa) de las mismas.

• Descomposición de Dantzig-Wolfe
• Descomposición de Benders
• Generación de columnas

• J. Kornai, T. Liptak: Planificación de dos niveles , Econometrica, 1965, vol. 33, págs.  141–169.