PROGRAMACIÓN LINEAL ENTERA
ÍNDICE
1. Introducción: Para iniciar
2. Organiza tus ideas: Conceptos clave
3. Enfoca tus conocimientos: Variables enteras
4. Ejemplos variables enteras
5. Método de solución Ramificación y Acote
6. Formulación modelos de programación entera
7. Ejercicio modelo lineal entero
8. Ejercicio de modelo de variable binaria
9. Conclusiones: Para terminar
Introducción
Determinar cómo podemos optimizar procesos o recursos, hacer las cosas de manera
más eficiente, o aprovechar ciertas condiciones en pro de la organización, no es
fácil. Sin embargo, hay modelos que nos ayuda a clarificar la información para tomar
mejores decisiones.
Al finalizar esta unidad lograrás:
● Comprender en qué consiste la programación lineal entera mediante los
diferentes modelos matemáticos existentes.
● Desarrollar el árbol de ramificación y acote mediante la solución de los
subproblemas, permitiendo llegar a los resultados de valores óptimos.
● Formular, a partir de un caso de estudio, la aplicación del modelo de
programación lineal entera o binaria.
Para iniciar es importante mencionar algunos conceptos que nos orientaran
mejorar en el desarrollo de un modelo lineal entero. ¡Conozcámoslos!
Organiza tus ideas: Conceptos clave
Algunos términos que intervienen en el modelo lineal entero:
● Directos: Las variables que se utilizan son cuantitativas y enteras.
● Modelar: Consiste en transformar el problema a resolver en un conjunto de
ecuaciones o fórmulas que lo definen exactamente o lo aproximan.
● Problema de optimización: Son aquellos en los que se barajan varias soluciones,
y la forma de optar entre una u otra solución es indicando que queremos optimizar
algún recurso.
● Inecuación: Como cualquier ecuación, pero además de la identidad (igualdad
o equivalencia), pueden aparecer las relaciones “mayor y menor que”, es decir,
cualquiera de: =, <, >, <= y >=.
● Lineal: Informalmente, existe una relación lineal entre dos elementos cuando
hay una constante que multiplicada a uno da como resultado el otro. Toscamente
podríamos decir que son las ecuaciones más simples que podemos encontrarnos.
● Enteros puros: Son aquellos en que todas las variables únicamente pueden
tomar valores enteros. También se distinguen dentro de estos los problemas totalmente
enteros como aquellos en que, tanto las variables como todos los coeficientes que
intervienen en el problema, han de ser enteros.
● Mixtos: Son aquellos en los que hay, al mismo tiempo, variables continuas y
variables que sólo pueden tomar valores enteros.
● Binarios: Las variables sólo pueden tomar los valores cero o uno. Atendiendo
al criterio del tipo de problema.
● Codificado: Cuando se trata de un problema que contiene, además de aspectos
cuantitativos, alguna consideración de tipo cualitativos, y por ello para tratar este tipo
de aspectos se requiere el uso de variables enteras o binarias.
● Transformado: Cuando el problema no incluye variables enteras, pero para ser
tratado analíticamente requiere el uso de variable enteras “artificiales”.
¡Muy bien! Ya tenemos claros algunos conceptos que iremos abordando en
esta unidad. Ahora definiremos la programación entera, el cual es el método
empleado para resolver problemas que tienen variables de decisión enteras.
¡Adelante!
Enfoca tus conocimientos: Variables
enteras
A continuación definiremos la programación lineal y modelos de variables binarias
Programación Lineal Entera
Es aquella en la que alguna de las incógnitas sólo puede tomar valores enteros.
Aunque pueda parecer una pequeña diferencia sin importancia, en realidad lo cambia
todo.
Mientras que para la programación lineal existen algoritmos que corren en tiempo
polinómico, la programación lineal entera es NP-completo y por tanto, nadie ha sido
capaz (ni se cree que se pueda) de encontrar una forma eficiente de resolverlos.
● Modelos
Los modelos de programación entera son una extensión de los modelos lineales en
los que algunas variables toman valores enteros.
● Valores
Con frecuencia las variables enteras sólo toman valores en 0-1, ya que este tipo de
variables permiten representar condiciones lógicas.
● Ahorros
Si nuestro problema es apto para ser resuelto con programación lineal, sin duda una
forma de ahorrar muchas horas de codificación, testeo y mantenimiento de código, es
aplicar y usar las librerías que tenemos a nuestro alcance.
● Resolución
Cualquier avance que se realice en la resolución de estos problemas conllevará
automáticamente una mejora en nuestras soluciones.
¡Perfecto! Ya sabes, si tienes delante de ti un problema difícil, considera la
posibilidad de usar programación lineal. Veamos a continuación algunos
ejemplos
Ejemplos variables enteras
¡Muy bien! Continuamos con la ramificación y acote que consiste en dividir
cada problema en dos nuevos subproblemas. El método de ramificación y
acotación, también llamado Branch and Bound, resuelve el problema de tal
forma que la solución a este verifica condiciones de integridad. ¡Vamos!
Método de solución Ramificación y
Acote
¡Muy bien! Ahora conoceremos algunas de las fórmulas que se aplican en
modelos de variables binarias y enteras. La idea de estos algoritmos consiste
en particionar el conjunto factible de resolución de problemas ya sea por
programación lineal entero, binario o de ramificación de lo que trataremos a
continuación. ¡Adelante!
Formulación modelos de programación
entera
Sabías que… la solución de los diferentes subproblemas puede obtenerse
utilizando Solver por medio de las opciones add/change/delete en el cuadro
de diálogo Solver Parameters. Continuemos con los ejercicios prácticos para
así afianzar parte de los conocimientos adquiridos en esta unidad.
Ejercicio modelo lineal entero
Ahora resolveremos mediante la herramienta solver un modelo lineal entero :
Caso de estudio
Un fabricante de muebles de oficina, produce dos tipos de escritorios: ejecutivos y
secretariales.
La compañía tiene dos plantas en las que fabrica los escritorios. La planta 1 es una
planta antigua que opera con doble turno de 80 horas por semana.
La planta 2 es una planta más nueva y no opera a su capacidad total. Cada turno
de la planta 2 trabaja 25 horas por semana y la planta opera 2 turnos.
La siguiente tabla muestra el tiempo de producción (horas/unidad) y los costos
estándar ($/unidad) en cada planta. También se muestran los precios de venta de
cada escritorio.
Debido a que la compañía ha estado experimentando un exceso de costos durante
el último periodo presupuestal, los administradores han fijado una restricción
semanal sobre los costos de producción.
El Costo Semifijo por producir en cada planta asciende a $600 y $900 para las
plantas 1 y 2 respectivamente. Además, en caso de producir algún modelo de
escritorio se debe asegurar una producción mínima de 100 unidades.
El presupuesto semanal para la producción en miles de pesos también se muestra
en la tabla.
Se le pide a usted averiguar cuál es el número óptimo de escritorios de cada tipo,
a producirse en cada planta con el objeto de maximizar las ganancias.
Solucione el ejercicio utilizando la herramienta solver
¡Excelente! Ahora aplicaremos un ejercicio con un modelo de asignación
binaria. ¡Vamos!
Ejercicio de modelo de variable binaria
Ahora resolveremos mediante la herramienta solver un modelo de variable binaria:
Caso de estudio
Supongamos que tenemos n ingenieros en una empresa (con n par) que deben
evaluar n/2 proyectos, y la empresa ha decidido armar grupos de 2 ingenieros para
evaluar cada proyecto.
Cada ingeniero ha manifestado en alguna escala su preferencia para trabajar con
los otros (sea cij la suma de la preferencia de i para trabajar con j más la preferencia
de j para trabajar con i).
Por favor resolver el ejercicio utilizando la herramienta solver
¡Excelente! Ahora retomemos las ideas principales que nos deja el recorrido
por esta unidad. ¡No te las pierdas!
Conclusiones:
Hemos llegado a la parte final de esta unidad denominada Programación Lineal
Entera, de la cual podemos concluir:
● La programación lineal es una herramienta para empresas de grandes
dimensiones, debido a que se requiere la aplicación de modelos matemáticos con
gran cantidad de recursos.
● Los modelos matemáticos buscan aprovechar al máximo los recursos, de
manera que se obtengan mayores ganancias y así minimizar costos.
● La ramificación y acote es un modelo o algoritmo matemático que crea
subproblemas si se ha llegado al final de todas las ramas, con el fin de escoger
como óptima la solución con mejor función objetivo.
● En la actualidad la formulación de problemas de programación lineal entera se
realiza por medio de herramientas de programación matemática por computadora,
debido a la extensión de las variables, y sobre todo, en casos en que se presenta
modelos de ramificación y acote en bases a variables de decisión con valores
enteros.
Antes de finalizar te invitamos a realizar las actividades propuestas para esta
unidad.
En la siguiente unidad trataremos sobre programación dinámica, para la
solución de problemas de manera secuencial. Acompáñanos a seguir en este
proceso de formación de investigación de operaciones II.