Ejercicios

UNIDAD 6
PROGRAMACIÓN LINEAL ENTERA

de programación lineal entera.
lineal entera.

Investigación de operaciones

Introducción

E

n la unidad 5 aprendimos a resolver modelos de P. L. por el
método símplex y el dual símplex, el resultado obtenido podía
ser cualquier número real, sin embargo, existen problemas que
no aceptan como solución un número real, por ejemplo, pensemos en
el problema deselección de personal de la unidad 3, en este caso no
podemos colocar 1.5 empleados. Por esta razón se han desarrollado
algoritmos especiales para la búsqueda de soluciones enteras de modelos
de P. L.
Podemos suponer que es más fácil resolver un problema de P. L. entera
que uno de P. L. estándar, pero esto en general no es cierto, ya que en
la actualidad no existe un algoritmo óptimo (desde elpunto de vista
computacional) para su puesta en práctica; por esta razón mostramos dos
de los métodos más utilizados en la practica:
Branch and Bound).
).

Los problemas que resuelven corresponden a los llamados modelos de
programación lineal entera (P. L. E.). Estos modelos se clasif ican de la
siguiente manera:
M odelos de P. L. E. puros. Cuando todas las variables de decisión
sólo tienen sentido sitoman valores enteros.
M odelos de P. L. E. mixtos. Cuando alguna de las variables de
decisión pueden tomar valores reales y sólo un subconjunto está
restringido a tomar valores enteros.
. Cuando las variables de decisión
sólo pueden tomar dos valores, por ejemplo, verdadero o falso, esto
se representa con cero o uno.

Empezaremos la unidad dando un ejemplo de cada uno de ellos y
posteriormenteanalizaremos los dos métodos de solución mencionados.
Estos dos métodos se estudian sólo con modelos de P. L. E. que tienen
como objetivo maximizar; para resolver problemas de minimización se
sugiere obtener el modelo dual presentado en la unidad 5.

223

Unidad 6

6.1. Aplicaciones ilustrativas
En la unidad 3 obtuvimos los modelos de algunos problemas de P. L.,
sin embargo, no hicimos hincapié enque algunos de ellos eran modelos
de P. L. E. En esencia la formulación de un modelo de P. L. E. sigue los
mismos pasos que un modelo de P. L. estándar, la única diferencia es que
algunas de las variables de decisión o todas están restringidas a tomar
sólo valores enteros. Veamos algunos ejemplos:

Ejemplo 1

Una fábrica produce tres tipos de herramientas, taladros, máquina
caladora y desarmadoreléctrico. Los costos para producir cada
herramienta están dados por un costo f ijo que es aplicable sólo si se
produce al menos una unidad, más un costo por unidad. En la siguiente
tabla mostramos los datos correspondientes.

Esto es, si producimos 3 taladros el costo es C(3) = 100 + 3(25) = 175,
ya que el costo fijo aplica desde una unidad hasta varias unidades.
La empresa tiene que fabricar porlo menos 50 taladros, 80 máquinas
caladoras y 100 desarmadores eléctricos, sin embargo sólo tiene un
capital de $ 20 930. El taladro deja una ganancia de $ 100 por unidad,
la máquina caladora $ 50 y el desarmador eléctrico $ 20. ¿Cuál es la
combinación que optimiza las ganancias? Obtener el modelo de P. L. E.
asociado.

224

Investigación de operaciones

Las variables de decisión son:
x1 =número de taladros que se van a producir.
x2 = número de caladoras que se van a producir.
x3 = número de desarmadores que se van a producir.
Hacemos la suposición de que toda la producción se vende, ya que el
problema no nos proporciona información al respecto.
La f unción objetivo la podemos escribir como:
Zmáx = 100x1 + 50x2 + 20x3
Las restricciones son:
100 + 25x1 + 80 + 20x2 + 50 + 10x3 < 20 930
x1> 50
x2 > 80
x3 > 100
Por lo tanto el modelo de P. L. E. es:
Zm á x

100x1 50x2

20x3

s. a.: 25x1 20x2 10x3

20 700

x1 50
x2 80
x3 100
xi

0 i 1, 2, 3

xi

enteros

La última restricción es necesaria ya que no podemos producir fracción
de taladros o fracción de desarmadores. Este modelo se resuelve en la
sección de problemas resueltos (problema 2).
Nota. Aquí es importante el hecho de que las...