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.