Algoritmos en programación lineal paramétrica

Abstract

La Programación Lineal Paramétrica (P.L.P.) estudia los cambios en la solución óptima de un problema de Programación Lineal (P.L.) debido a variaciones continuas predeterminadas en los parámetros del modelo, de un programa de la forma: min cTx Ax ≥ b como la disponibilidad de recursos que representa b, cambios de utilidades o costos que representa c ó cambios en la matriz A del lado izquierdo de las restricciones. En otras palabras la P.L.P. permitirá un ahorro considerable en los costos de utilización de una computadora. Se presenta también la formalización de la solución del P.L.P. mediante algoritmos que dan la solución de las mismas, si existen. Del programa anterior x, c e Rn , b e Rm y A es una matriz de orden m x n (m ≥ n) rango es igual a n. Las variaciones sobre el programa a ser analizadas son las siguientes: i) Cambios en el vector c: min (c + 0f)T x Ax ≥ b , Θ ≥OyfeRn ii) Cambios en b, lado derecho de las restricciones : min c T x Ax≥ b + 0f , Θ ≥ 0 y f e Rm iii) Cambios en una fila aj de la matriz no básica de A : min c T x A(Θ)x ≥ b

En los tres casos se hace un análisis para determinar los valores de Θ para los cuales la solución óptima no cambia, y correspondientemente los valores de Θ para los cuales la solución óptima si cambia. En esta parte de la introducción hacemos mención de algunos fundamentos del algoritmo simplex que nos servirá como base para el estudio en capítulos posteriores. En lo capítulos II y DI se trata de las variaciones de los vectores c y b respectivamente. Con respecto al capítulo IV se hace el estudio de las variaciones de la fila aj de la matriz no básica de A.