programación lineal Archivos - Página 14 de 17

Cómo instalar una aplicación del Método Simplex en una calculadora HP 48

En el siguiente tutorial te mostraremos cómo instalar una aplicación del Método Simplex a tu calculadora Hewlett-Packard (en adelante HP) de la serie HP 48G, HP 48G+, HP 48GX, HP 48S, HP 48SX. Esto es de gran ayuda cuando se intenta resolver un modelo de Programación Lineal que es no trivial y que por tanto requiere de un número importante de iteraciones o cálculos tediosos.

Si bien el principal objetivo de este tutorial es instalar un programa en tu calculadora sobre el Método Simplex, los pasos descritos te permiten incorporar otro tipo de programas útiles para tus estudios.

¿Qué necesitas?

1.- Una calculadora HP de alguno de los siguientes modelos: HP 48G, HP 48G+, HP 48GX, HP 48S, HP 48SX. Si no tienes una puedes comprar una de forma económica aquí:

2.- Un cable serial para conectar la calculadora con tu computador:

3.- Un conector que convierte un serial DB9 (Adaptador de 9 pines) a USB:

4.- Kit de Conectividad de la Calculadora HP 48G, HP 49G y HP 50G serie. Este programa te permitirá traspasar información y programas desde tu computador a tu calculadora y viceversa. Descárgalo gratuitamente desde HPcalc.org.

Importante: Puedes reemplazar el cable serial para conectar la calculadora a tu computador y el conector que convierte un serial RS232 a USB por un único cable de conexión que te permite conectar directamente tu calculadora al computador.

Instalar el Kit de Conectividad en tu Computador

Ejecuta el archivo “conn4x_english.exe” y sigue los sencillos pasos del instalador.

Una vez instalado el programa en tu computador podrás traspasar programas e información desde tu computador a tu calculadora HP 48 como viceversa. Todos los aspectos relativos a la conexión están cubiertos con bastante detalle y de forma muy sencilla en el menú Ayuda del Kit de Conectividad en la sección “Contenido e Indice”.

Para instalar en tu calculadora una aplicación del Método Simplex que sea compatible con tu calculadora de la serie HP 48 te recomendamos buscar alguna alternativa que te acomode en HPCalc.org filtrando por el modelo y utilizando como criterio de búsqueda “Simplex”. De esta forma te aseguras de obtener resultados pertinentes no sólo en español.

Luego selecciona uno de los programas del listado y sigue con detalle los pasos para la instalación. Como los programas son gratuitos puedes intentar instalar varios de ellos y finalmente utilizar el que más te acomode. Cuéntanos tu experiencia utilizando alguno de estos programas!.

Cómo resolver un modelo de Programación Lineal con What’sBest!

En el siguiente tutorial mostraremos Cómo resolver un modelo de Programación Lineal con What’sBest!. Para ello por supuesto se requiere previamente descargar e instalar What’sBest! como complemento de Excel tal cual lo explicamos paso a paso en un artículo previo.

Para mostrar cómo utilizar este programa utilizaremos el Problema de Transporte que consiste en determinar una política de distribución que minimice los costos de la logística, al mismo tiempo que satisface la demanda de los clientes y respeta la capacidad de los oferentes.

La información se resume en el siguiente diagrama para un caso particular de 2 plantas y 3 clientes, donde los números sobre las flechas representan los respectivos costos unitarios de transporte entre una planta y un cliente.

Los pasos para implementar este problema de programación lineal en What’sBest! son:

Paso A: Definir las Variables de Decisión: Para ello debes previamente definir en un planilla Excel las celdas que utilizarás como variables. En el ejemplo la Xij: Unidades transportadas desde la planta i al cliente j. Con i=1,2 y j=1,2,3 se tienen 6 variables de decisión.

Importante: Completa las celdas que serán variables de decisión con cero como se muestra en la imagen anterior. Luego selecciona el rango de celdas que corresponde a las variables del modelo y presiona “Make Adjustable”.

Paso B: Definir la Función Objetivo: Como el nombre lo indica, ésta celda corresponde al objetivo del problema de optimización que en este caso es minimizar los costos totales de transporte. La celda contiene una fórmula SUMAPRODUCTO(C3:E4;C12:E13) previamente ingresa que pondera los costos unitarios de transporte para las distintas combinaciones (datos o parámetros) y las variable de decisión previamente definidas. Finalmente nos posicionamos sobre la celda de la función objetivo y seleccionamos en este caso “Minimize”.

Paso C: Definir las Restricciones: Se incorporan las restricciones del modelo de optimización, es decir, las condiciones que deben cumplir las variables de decisión al momento de la resolución. Para ello se selecciona en el menú la opción “Constraints”.

En la imagen a continuación se muestra cómo se incorporó la restricción que garantiza que la cantidad de unidades enviadas por cada planta (L.IZQ) no supere (<=) la capacidad de la misma (L.DER). Como se puede apreciar se incorporan las restricciones de capacidad de la planta 1 y 2 en forma simultanea.

Finalmente para proceder a la resolución del modelo seleccionamos la opción “Solve” del menú:

Luego de lo cual se obtienen los siguientes resultados:

Solución Básica Factible Óptima: X11=80.000; X12=40.000; X13=0; X21=0; X22=30.000; X23=90.000. El Valor Óptimo (mínimo costo) es de $940.000. Para descargar el archivo Excel con la resolución del modelo de transporte con What’sBest! sigue los pasos a continuación:

[sociallocker]Descarga Aquí: http://dlu.jzt.temporary.site/wp-content/uploads/2013/02/PTWB.xlsx[/sociallocker]

Problema de Construcción de Viviendas resuelto Gráficamente

El siguiente problema fue enviado por uno de nuestros usuarios de la ciudad de Bogotá, Colombia:

En la ciudad de Armenia se va a demoler un barrio de 10 acres y la alcaldía debe decidir sobre el nuevo plan de desarrollo. Se van a considerar dos proyectos habitacionales: viviendas a bajo costo y viviendas a medio costo. Se pueden construir 20 y 15 unidades de cada vivienda por acre, respectivamente. Los costos por unidad de las viviendas a bajo y medio costo son $13.000 y $18.000, respectivamente. Los límites inferior y superior establecidos por la alcaldía sobre el número de viviendas de bajo costo son 60 y 100 respectivamente. De igual manera, el número de viviendas de costo medio debe estar entre 30 y 70. Se estima que el mercado potencial combinado máximo para las viviendas es de 150 (que es menor que la suma de los límites de los mercados individuales debido al traslapo entre los dos mercados). Se desea que la hipoteca total comprometida al nuevo plan de desarrollo no exceda los $2 millones. Finalmente, el asesor de la obra sugirió que el número de viviendas de bajo costo sea por lo menos de 50 unidades mayor que la mitad del número de viviendas de costo medio.

Formule como un Programa Lineal el problema del nuevo plan de desarrollo a costo mínimo y resuelvalo gráficamente.

A continuación detallamos la resolución de este problema de Programación Lineal utilizando el Método Gráfico:

1. Variables de Decisión:

X1: Viviendas de bajo costo a construir
X2: Viviendas de costo medio a construir

2. Función Objetivo: Minimizar 13.000X1 + 18.000X2

3. Restricciones:

Disponibilidad de acres: (X1/20) + (X2/15) <= 10
Límites de viviendas de bajo costo: 60 <= X1 <= 100
Límites de viviendas de costo medio: 30 <= X2 <= 70
Límite mercado combinado: X1 + X2 <= 150
Límite hipoteca total: 13.000X1 + 18.000X2 <= 2.000.0000
Sugerencia asesor de obra: X1 >= 50 + (X2/2)
No Negatividad: X1>=0 X2>=0

La resolución gráfica del modelo de programación lineal anterior se muestra a continuación utilizando el software Geogebra:

Solución Básica Factible Óptima: X1=65 y X2=30
Valor Óptimo: V(P)=$1.385.000

Restricción con Precio Sombra Negativo en Programación Lineal

En Programación Lineal, el Precio Sombra se refiere a una tasa de cambio del valor óptimo ante una modificación marginal del lado derecho de una restricción, entendiendo como marginal una modificación que permita mantener las actuales restricciones activas para el problema (se conserva la base óptima). En este tipo de análisis se asume que el resto de los parámetros del modelo permanecen constantes.

En artículos anteriores hemos analizado Cómo calcular el Precio Sombra de una Restricción Gráficamente y en forma complementaria Cómo interpretar los Informes de Sensibilidad de Restricciones de Solver de Excel. Esto sin duda es una buena base conceptual para entender el significado del Precio Sombra de una restricción.

En esta oportunidad nos referiremos a una situación que a priori podría parecer anómala, pero que definitivamente no lo es: que una restricción asociada a un modelo de Programación Lineal tenga un Precio Sombra negativo.

Para ilustrar este escenario utilizaremos nuevamente el Modelo de Transporte el cual se representa esquemáticamente a continuación:

La resolución computacional de este modelo utilizando Solver de Excel se resume a continuación:

Notar que la Planta 1 tiene un exceso de capacidad de 40.000 unidades (diferencia entre su capacidad de 160.000 y las 120.000 unidades que despacha).

Por el contrario la Planta 2 funciona a máxima capacidad (despacha 120.000 unidades). El Informe de Sensibilidad de restricciones reporta lo siguiente:

La restricción de capacidad de la Planta 2 tiene un Precio Sombra negativo de magnitud -1. Esto significa que si se incrementa en una unidad la capacidad de la Planta 2 (a 120.001 unidades) el nuevo valor óptimo será 939.999.

Análogamente, cualquier cambio en la capacidad de la Planta 2 en el intervalo [120.000-40.000,120.000+40.000]=[80.000,160.000] generará una modificación del valor óptimo del problema proporcional al Precio Sombra de la restricción de capacidad de dicha planta.

Por ejemplo, si la capacidad de la Planta 2 aumenta a 130.000 unidades, el nuevo valor óptimo será:

$V(\bar{P})=V(P)+\Delta b\cdot \pi =940.000+(130.000-120.000)\cdot -1=930.000$

Por el contrario, si la capacidad de la Planta 2 disminuye a 110.000 unidades, el nuevo valor óptimo es:

$V(\bar{P})=V(P)+\Delta b\cdot \pi =940.000+(110.000-120.000)\cdot -1=950.000$

¿Por qué se produce este fenómeno?. Básicamente por una reasignación debido a que resulta ser relativamente más conveniente generar despachos desde la Planta 2 en comparación a la Planta 1 (que tiene capacidad ociosa y por tanto un Precio Sombra igual a cero).

7 Recursos Gratuitos para el estudiante de Investigación de Operaciones

En Internet existen recursos gratuitos valiosos para los estudiantes de los cursos de Investigación de Operaciones (conocido también como Investigación Operativa) que son de gran ayuda para complementar los conceptos tratados en el aula y la bibliografía. En el siguiente artículo ponemos en disposición de nuestros lectores algunos recursos que recomendamos:

1. Solver: Es sin duda la principal herramienta para resolver modelos de optimización de tamaño reducido utilizado por los alumnos de cursos de ingeniería. Este complemento de Excel se puede descargar desde el sitio web de Frontline en su versión comercial (Premium Solver Pro) para implementar modelos de mayor tamaño.

2. What’sBest!: Es la alternativa a Solver dado que funciona integrada en una planilla de cálculo (Excel). La interfaz es intuitiva y seguramente quién domine Solver no demorará mucho en aprender los elementos básicos de este programa. What’sBest! ha sido desarrollado por la empresa de software Lindo.

3. AMPL: Es un lenguaje de programación matemática que permite abordar la formulación y resolución de modelos de optimización de programación lineal, programación entera y programación no lineal (entre otros). Esta plataforma es popular para modelos de mayor complejidad que requieren para su resolución de algoritmos especializados.

4. GAMS: Es una herramienta de formulación matemática alternativa a AMPL que permite formular y resolver modelos de optimización de complejidad mayor.

5. NEOS Solvers: Es un portal que consolida una gran variedad de solvers (algoritmos) que permiten resolver distintas categorías de modelos de optimización formulados en un lenguaje matemático determinado (como AMPL y GAMS). El procedimiento es el siguiente: se selecciona un solver que permita resolver nuestro modelo (depende del lenguaje de programación matemática y el tipo de modelo), se sube el archivo del modelos (y/o datos) y se obtienen los resultados online.

6. Geogebra: Es un excelente programa que nos ayuda a graficar distintas formas geométricas y en particular resolver gráficamente modelos de optimización lineales o no lineales. Este programa se puede descargar gratuitamente e instalar en nuestro computador o alternativamente utilizar su aplicación web directamente sin necesidad de descargar el programa.

7. Método Simplex (ProgramacionLineal.net): Es una herramienta que permite resolver modelos de programación lineal a través del método simplex, mostrando paso a paso las respectivas iteraciones, solución óptima y valor óptimo.

8. Linear Programming: Versión en inglés de los principales artículos de este Blog que trata sobre la Investigación de Operaciones y en particular de la Programación Lineal, con recursos educativos y ejercicios resueltos.