V.1.0. [Guía Rápida]
- Resumen
- Como instalar el programa
- Como resolver un Modelo
- Como interpretar el reporte combinado
- Bibliogafía
En este trabajo se explora la utilización del El LP-ILP [LINEAR PROGRAMMING AND INTEGER LINEAR PROGRAMMING], Software de Investigación de Operaciones WINQSB 1.0, el cual puede resolver modelos de Programación Lineal muy fácilmente.
Palabras clave:
Programación lineal, Software, LP-ILP, precio sombra, simples, restricciones, función objetivo.
El LP-ILP [LINEAR PROGRAMMING AND INTEGER LINEAR PROGRAMMING], fuefuefue desarrollado por el Prof. Yih Long Chang del MIT como un módulo de trabajo del Software de Investigación de Operaciones WINQSB 1.0, dada su interfaz amigable y sus rutinas de optimización, puede ser utilizado como programa maestro, para cualquier curso de Programación Lineal de Pregrado o Postgrado. El LP-ILP V.1.0, puede resolver modelos de Programación Lineal de una función objetivo (Uni-objetivo), y de programación Lineal Metas bien especificados (Ees decir con funciones objetivos lineales de ponderación aditiva o arreglos lexicográficos de funciones lineales objetivos) para un número limitado de restricciones y variables. La versión 1.0 desarrollada en estas notas, corre bajo ambiente Windows 95/98/ME/2000/XP, y su lenguaje por defecto es el Ingles.
Entre sus funciones tenemos:
- Aplicación del Método Gráfico y del Método Simplex.
- Aplicación del método de Ramificación y Corte (Branch-and-bound) para Programación Lineal entera.
- Muestra los Tableros Simplex por cada iteración y el tablero final.
- Permite realizar análisis parametrico.
- Construcción del modelo dual automáticamente.
Se recomienda copiar todo el contenido de la carpeta WINQSB del CD, al disco duro local y crear un acceso directo en el escritorio; sin embargo el programa corre perfectamente si la aplicación se ejecuta desde el CD. .
- Como Instalar el programa:
- Como resolver un Modelo:
Se debe partir del supuesto que la el modelo de PL esta bien especificado, sin embargo dicho modelo a lo largo de su resolución puede sufrir modificaciones según sea el caso.
Por ejemplo, :s
Supongamos que tenemos el siguiente modelo de producción:
MAX Z = 3X1 + 5X2 (Utilidad total)
S.A.
X1 + 0X2 <= 4 (Restricción del Recurso A)
3X1 + 2X2 < =18 (Restricción del Recurso B)
X1, X2 >= 0 (No negatividad)
Donde X1 y X2, representa el numero de unidades semanales a producir del Producto 1 y 2 respectivamente, y la restricción C1, y C2 representa la disponibilidad de recursos A y B para el proceso productivo.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Hacemos doble click o un clik según sea el caso sobre el icono:
- Para Abrir el programa:
- Para crear un archivo nuevo:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
En la ventana inicial, hacemos un click en el icono:
Otra opción es ir al [Menú FILE→NEW PROBLEM] tal y como se muestra en la Figura Nº1.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº1. Crear un archivo nuevo por menú.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
En la ventana inicial también podemos,
Abrir un archivo. [MENU FILE→-LOAD PROBLEM]
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Salir del programa. [MENU FILE→-EXIT]
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Ir a la Ayuda. [MENU HELP]
Para ver el gráfico seleccione la opción "Descargar" del menú superior
3. Para cargar los datos:
En la caja de dialogodiálogo, debemos especificar la configuración inicial del problema:
PROBLEM TITLE: Titulo del problema.
[Este nombre será usado en los informes escritos y en la pantalla]
NUMBER OF VARIABLES: Número de Variables.
NUMBER OF CONSTRAINT: Número de restricciones:
OBJECTIVE CRITERION: Criterio del Objetivo.
Si queremos maximizar pulsamos la casilla de Maximization.
Si queremos minimizar pulsamos la casilla de Minimization.
DATA ENTRY FORMAT: Tipo de Formato de entrada.
MATRIX FORM: Forma matricial.
NORMAL MODEL: Modelo final.
DEFAULT VARIABLE TYPE:
NONEGATIVE CONTINOUS: (Si las variables son no- negativas y continuas se activa esta casilla, el programa por defecto activa esta casilla siempre).
NONEGATIVE INTEGER: (Si las variables son no- negativas y enteras se activa esta casilla).
BINARY (0,1): (Si las variables son de tipo binarias se activa esta casilla).
UNSIGNED/UNRESTRICTED: (Si las variables son de tipo sin signos e o irrestricta se activa esta casilla).
En nuestro ejemploVeamos con nuestro ejemplo la figura Nº2:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
PROBLEM TITLE: PROBLEMA Nº1.
NUMBER OF VARIABLES: 2.
NUMBER OF CONSTRAINT: 2
OBJECTIVE CRITERION:
Maximization.
DATA ENTRY FORMAT:
Normal Model.
DEFAULT VARIABLE TYPE:
Nonegative Continous.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº2. . Configuración inicial del problema
Posteriormente debemos Ccargar el modelo final: en la hoja.
Aquí En nuestro ejemplo lo haremos bajo una forma funcional normal, es decir con las ecuaciones completas del modelo especificado, sin embargo vale decir que en la forma alterna de matriz o hoja dae calculocálculo se introducen solo los coeficientes que acompañan a las ecuaciones, entonces es cuestión de preferencia sobre como introducir los datos,. vale decir que existeExista ciertoa preferenciafavoritismo entre los analistas de IO a preferir la forma normal pues permite copiar y pegar el modelo de cualquier editor de texto. La figura Nº3 nos muestra dicha situación.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Para editar el
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº3. Modelo cargado bajo la forma normal.
Opciones de edición:
Para completar la compresión de los reportes, es recomendable editar el nombre de las restricciones con una frase que documente su significado en el modelo.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Para editar el nombre de las restricciones podemos ir
a Menú EDIT- CONSTRAINT NAME
Similarmente para editar el nombre de las variables
podemos ir Menú EDIT- VARIABLES NAME.
[ eEl programa
trabaja por defecto con las
variables X1, X2, …XN]
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº4. Editando restricciones.
Para editar el nombre de las variables podemos ir
a Menú EDIT- VARIABLES NAME. [ EL PROGRAMA
TRABAJA POR DEFECTO CON LAS
VARIABLES X1, X2, …XN]
4.Para resolver el modelo:
Finalmente si queremos resolver el modelo por el "mMétodo gGráfico" hacemos clik en el icono donde aparece una gráfica de un área factible en 2 dimensiones, tal y como se muestra en la Figura Nº5:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Nº5. Aplicación del método gráfico.
Y en la caja de dialogo posterior se solicita el sentido de los ejes:
Nº6. Selección de ejes.
Confirmados los ejes y h
Haciendo clik en Ok, nos suministra la solución gráfica:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Nº7. Solución Gráfica.
En algunos sistemas operativos de la Familia WINDOWS se han reportado fallas de ejecución de la gráfica, para su óptima visualización se recomienda instalar los SERVICE PACK más recientes, y en Windows XP activar la compatibilidad de la aplicación con Windows 95/98. En Linux el Software no ha sido probado por el autor.
Si queremos resolverlo por el algoritmo sSIMPLEX:
Hacemos clik en el icono donde aparece el un hombrecillo corriendo y como se muestra en la Figura Nº8:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº8: Correr el Método Simplex.
Una vez introducidos los datos y corrido el modelo obtenemos el siguiente reporte combinado:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº9. Reporte Combinado.
La Solución Óptima.
1er Bloque Solución Optima:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº10. 1er Bloque Solución Optima.
En ésta área, el significado para la fila 1, de los datos de izquierda a derecha es:
Del artículo 1 (X1) debemos producir cero (0) unidades. Su utilidad por unidad (C1) es de 3 y su contribución a al utilidad total es de Bs. Cero (0) [(0)X(3)=0].
Del artículo 2 (X2) debemos producir 9 unidades. Su utilidad por unidad (C2) es de 5 y su contribución a al utilidad total es de Bs.45 [(5)X(9)=45].
En la siguiente fila se muestra el valor total de la contribución ó valor máximo de la función objetivo Z* = $45 [(0)+(45)=45]. Es claro que dado el modelo actual, no es posible obtener una utilidad superior a Bs.45.
2do. Bloque. Análisis de sensibilidad de los coeficientes.
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº11. Bloque de análisis de sensibilidad de los coeficientes.
En las dos últimas casillas de la fila uno, Figura Nº11, se muestra el análisis de sensibilidad para C1 que nos indica que la utilidad por unidad del artículo 1 debe estar en el rango de: – ∞ < C1’ < 7,5 para que la solución actual se mantenga óptima. Similarmente en las dos últimas casillas de la fila dos, se muestra el análisis de sensibilidad para C2 que nos indica que la utilidad por unidad del artículo 2 debe estar en el rango de: 2 < C2 < + ∞ para que la solución actual se mantenga óptima.
Supongamos que la utilidad unitaria del producto 2 (C2) disminuye en un 50%, y se ubica en 2.5, este valor se ubica en el intervalo de sensibilidad 2 < C2 < + ∞ por lo tanto el valor actual de la solución optima sigue siendo X1=0 y X2=9, es decir:
Del artículo 1 (X1) debemos producir cero (0) unidades. Su utilidad por unidad (C1) es de 3 y su contribución a al utilidad total es de Bs. Cero (0) [(0)X(3)=0]. Del artículo 2 (X2) debemos producir 9 unidades. Su nueva utilidad por unidad (C2) es de 2.5 y su contribución a al utilidad total seria: 22.5 [(2.5)X(9)=22,5]. El valor de Z seria: [(0)+(22.5)=22.5].
Cualquier variación del coeficiente que viole los limites de sensibilidad provocara un cambio en los valores de la solución optima, por lo tanto para poder realizar un análisis tendríamos que disponer de una nueva salida computacional hoy en día esta tarea significa invertir unos cuantos segundos al re-definir el modelo, pero hace 50 años era todo un dilema decidir correr una nueva salida..
Sin embargo, y volviendo al ejemplo, Ssi decidiéramos llevar la contraria a ésta solución óptima y decidiéramos producir unidades del producto 1, entonces por cada unidad producida, debemos reducir nuestros costos unitarios en $4,50 (costo reducido) con lo cual la utilidad unitaria se ubicaría 7,5 de esta manera el valor de la solución optima de X1 será diferente a cero (en caso de presentarse un problema de minimización de costos, la reducción del costo unitario es directa ).
En la fila 2 el costo reducido es de 0 en atención a que sí se van a producir unidades del artículo 2 y por lo tanto el valor optimo de X2 ya es diferente de cero (en este caso X2=9).
3er Bloque Análisis de Sensibilidad de los Recursos:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Figura Nº12. Bloque de análisis de sensibilidad de los recursos.
En figura 12, Lla fila 1 referente a la disponibilidad del recurso A , indica que del recurso A no se utilizará ninguna unidad, de las 4 disponibles, por ello la holgura de dicho recurso es de 4 unidades, siendo la restricción inactiva por poseer un valor de holgura diferente de cero. El precio sombra nos indica que si se dispone de una unidad adicional del recurso A, ello ocasionará un incremento en la utilidad de $0 (si se dispone de una unidad menos del recurso A, ello ocasionará un decremento de $0); siempre y cuando el valor del recurso se encuentre entre los límites de sensibilidad 0 < b1 < ∞ ; que son los valores que hacen que restricción permanezca en su misma condición.
La fila 2, referente a la disponibilidad del recurso B indica que del recurso B se utilizan 18 unidades, de las 18 disponibles, por ello la holgura de dicho recurso es de 0 unidades, siendo la restricción activa por poseer un valor de holgura igual a cero. El precio sombra nos indica que si se dispone de una unidad adicional del recurso B, ello ocasionará un incremento en la utilidad de $2,50 (si se dispone de una unidad menos del recurso B, ello ocasionará un decremento de 2,50) siempre y cuando el valor del recurso se encuentre entre los límites de sensibilidad 0 < b2 < ∞; que son los valores que hacen que la restricción permanezca en su misma condición.
En el caso en que una unidad del recurso deba ser vendido, su precio ideal seríia como mínimo su precio sombra, ya que este nos indica el aporte marginal a la función objetivo por cada cambio unitario en el total de recursos. Es decir, si cada unidad del recurso B, debe ser vvendida a otra empresa del mismo ramo, el precio minimomínimo de referencia debe ser $2,50, pues este es su aporte a la utilidad total.
Cualquier efecto en valor de la Función Objetivo producto de la variación de recursos dentro de los limites permitidos, puede estimarse con la siguiente formula:
FO´= FO + (Precio Sombra X Incremento)
Por ejemplo se disminuye en 10 unidades el recurso B, ubicándose la disponibilidad en 8 como el valor del recurso se encuentre entre los límites de sensibilidad 0 < b2 < ∞, es posible inferir que:
FO´= 45 + (2.5 X -10) = 20.
Análogamente el incremento necesario para obtener un valor de la función objetivo requerido (FO´) puede estimarse con:
Incremento = (FO´- FO)/Precio Sombra
Es decir, si queremos obtener, un valor optimo de 65 por ejemplo, calculamos:
Incremento = (65- 45)/2.5 = 8. Y eEl incremento de ocho unidades esta en el intervalo permitido 0 < b2 < ∞.
El reporte combinado, la salida o el problema puede catalogarse como no degenerado porque el numero de restricciones (2) es igual a la sumatoria de los valores positivos de la solución optima (1) y los valores de holgura (1). Por ello todos los análisis de sensibilidad son correctamente estimados y no se corre el riesgo de Ciclar el problema.
Nota final:
Los alumnos que deseen este material y el manual en formato digital [PDF], enviar correo al:
Carrasquero, N (1996). Programación Lineal. Postgrado de Investigación de Operaciones. Facultad de Ingeniería. UCV.
Chediak, F (2000). Investigación De Operaciones Volumen I. Disponible desde:
http://personales.com/colombia/ibague/chediak/ http://www.udlap.mx/~is103394/InvDeOp/ consultado el 20/03/2002.
LP-ILP (1998). LP-ILP Help Contents.[Ayuda del programa].
Ojeda, C(2002). Introducción al uso del LP-ILP. Primera versión.edición. UNELLEZ. Programa Economía Agrícola.
Datos del autor:
Prof. Carlos Julio Ojeda Aponte
Economista agrícola
Candidato a Msc en Investigación de Operaciones UCV.
E-mail:
Centro de Investigaciones Económicas y Sociales.
Segunda Versión. Noviembre 2004
Sub-Proyecto: Investigaciión de Operaciones.
Universidad Nacional Experimental De Los Llanos Occidentales "Ezequiel Zamora"
Programa de Ciencias Sociales y Jurídicas.
UNELLEZ.