7/22/2019 Introduccin a la PL

1/3

Introduccin a la programacin lineal (PL)1

El desarrollo de la programacin lineal ha sido clasificado como uno de los avances cientficos ms importantes demediados del siglo xx. Su efecto desde 1950 ha sido extraordinario. En la actualidad es una herramienta de uso normalque ha ahorrado miles o millones de dlares a muchas compaas o negocios, incluso empresas medianas, en losdistintos pases industrializados del mundo; su aplicacin a otros sectores de la sociedad se ha ampliado con rapidez.Una proporcin muy grande de los programas cientficos en computadoras est dedicada al uso de la programacin

lineal.

Expresado en forma breve, el tipo ms comnde aplicacin abarca el problema general de asignar de la mejor maneraposible (forma ptima) recursos limitados a actividades que compiten entre s por ellos. Con ms precisin, esteproblema consiste en elegir el nivel de ciertas actividades que compiten por recursos escasos necesarios pararealizarlas. Despus, los niveles de actividad elegidos dictan la cantidad de recursos que consumir cada una de ellas.La variedad de situaciones a las que se puede aplicar esta descripcin es sin duda muy grande, ya que abarca desdela asignacin de instalaciones de produccin a los productos hasta la asignacin de los recursos nacionales a lasnecesidades de un pas; desde la seleccin de una cartera de inversiones hasta la seleccin de los patrones de envo;desde la planeacin agrcola hasta el diseo de una terapia de radiacin, etc. No obstante, el ingrediente comn detodas estas situaciones es la necesidad de asignar recursos a las actividades mediante la eleccin de los niveles de

stas(palabras clave son recursos y actividades).

La programacin lineal utiliza un modelo matemtico para describir el problema. El adjetivo lineal significa que todas lasfunciones matemticas del modelo deber ser funciones lineales. En este caso, las palabra programacin no se refiere aprogramacin en computadoras; en esencia es un sinnimo de planeacin. As, la programacin lineal trata laplaneacin de las actividades para obtener un resultado ptimo, esto es, el resultado que mejor alcance la metaespecificada (segn el modelo matemtico) entre todas las alternativas de solucin. Cualquier problema cuyo modelomatemtico se ajuste al formato general del modelo de programacin lineal es un problema de programacin lineal.

Los tres elementos bsicos del modelo de PL (y en muchos modelos de IO) son los siguientes:

1. Variables de decisin que se tratan de determinar (sirven para elegir los niveles de actividades).

2. Objetivo o meta que se trata de optimizar.

3. Restr icc iones y/o c ondic iones que se necesitan satisfacer (relacionadas por lo comn con los recursos que

se desean asignar a las actividades).

Ejemplo de un modelo de programacin lineal

Ciertos smbolos se usan de manera convencional para denotar las distintas componentes de un modelo de

programacin lineal. Estos smbolos se enumeran a continuacin, junto con su interpretacin para el problema general

de asignacin de recursos a actividades.

Z = valor de la medida global de efectividad

x j = nivel de la actividad j (para j = 1,2,...,n)

c j= incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j

b i= cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m)

a ij= cantidad del recurso i consumido por cada unidad de la actividad j

1Tomado del texto Introduccin a la investigacin de operaciones de Hillier & Lieberman (octava edicin en espaol, 2006) einvestigacin de operaciones de Hamdy Taha (sptima edicin en espaol, 2004) y apuntes del docente.

7/22/2019 Introduccin a la PL

2/3

El modelo establece el problema en trminos de tomar decisiones sobre los niveles de las actividades, por lo que x 1,

x2,...., xn se llaman variables de decis in. Los valores de cj, bi y aij (para i = 1,2, ..., m y j = 1,2, ..., n) son las

constantes de entrada al modelo. Las cj, biy aijtambin se conocen como parmetros del m odelo.

Forma estndar para un problema de maximizacin segn Hillier (otros textos adoptan formas distintas):

Maximizar Z = c1x1+ c2x2+....+ cnxn,

sujeta a las restricciones:

a11x1+ a12x2+....+ a1nxn b1

a21x1+ a22x2+....+ a2nxn b2

.

.

.

am1x1+ am2x2+....+ amnxn bm

x1, x2, , xn 0

Supuestos de programacin lineal

En realidad, todos los supuestos de PL estn implcitos en la formulacin del modelo. En las suposiciones delinealidad estn intrnsecas las propiedades de proporcionalidad y aditividad. Sin embargo, desde el punto de vista demodelacin un modelo de PL implica que se deban considerar otros supuestos acerca de las actividades y datos delproblema que ser modelado.

Proporcionalidad.

La contribucin de cada actividad al valor de la funcin objetivo Z es proporcional al nivel de actividad xj, como lo

representa el trmino cjxjen la funcin objetivo. De manera similar, la contribucin de cada actividad al lado izquierdode cada restriccin funcional es proporcional al nivel de la actividad xj, en la forma en que lo representa el trmino a ijxjen la restriccin. En consecuencia, esta suposicin elimina cualquier exponente diferente a 1 para las variables encualquier trmino de las funciones (ya sea la funcin objetivo o la funcin en el lado izquierdo de las restriccionesfuncionales) en un modelo de programacin lineal.

Aditividad.

Cada funcin de un modelo de programacin lineal (ya sea la funcin objetivo o el lado izquierdo de las restriccionesfuncionales) es la suma de las contribuciones individuales de las actividades respectivas. Esta suposicin prohbe lostrminos de productos cruzados.

Divisibilidad.

Las variables de decisin en un modelo de programacin lineal pueden tomar cualquier valor, incluyendo valores noenteros, que satisfagan las restricciones funcionales y condiciones tcnicas. As, estas variables no estn restringidas aslo valores enteros. Como cada variable de decisin representa el nivel de alguna actividad, se supondr que lasactividades se pueden realizar a niveles fraccionales.

Certidumbre.

Los valores asignados a cada parmetro de un modelo de programacin lineal (cj, bi y aij) son constantes

conocidas.

7/22/2019 Introduccin a la PL

3/3

Pasos para formular modelos de PL2

1. Leer y entender claramente el ejercicio. Extraer toda la informacin necesaria para formularlocuantitativamente, especificando claramente las unidades de toda la informacin. Si es necesario tabule lainformacin. Identifique y escriba el objetivo del ejercicio. Escriba la pregunta o preguntas del ejercicio.

2. Represente simblicamente las variables de decisin. Asgnele un nombre a cada variable y las unidadesrespectivas. La representacin sugerida es xj, xij, xijk, xijkl, yj, yij, yijk, yijkl,etc.

3. Represente simblicamente la variable objetivo. Asgnele un nombre a sta y la unidad respectiva. Escriba larepresentacin matemtica que relacione la variable objetivo con las variables de decisin para construir lafuncin objetivo. La representacin sugerida es maxZ o minZ.

4. Escriba las limitaciones o restricciones funcionales. Consiste en relacionar las variables de decisin con lascondiciones que se deben cumplir para la formulacin.

5. Condiciones tcnicas. Obedece a diversas razones tcnicas. Por lo general que las variables de decisintomen valores no negativos.

Ejercicio 3.1-10 p. 92. Introduccin a la IO Hillier & Lieberman (octava edicin en espaol).

La compaa manufacturera Omega descontinu la produccin de cierta lnea de productos no redituable. Estamedida cre un exceso considerable de capacidad de produccin. La administracin quiere dedicar esta

capacidad a uno o ms de tres productos llamados productos 1, 2 y 3. En la siguiente tabla se resume lacapacidad disponible de cada mquina que puede limitar la produccin:

Tipo de mquina Tiempo disponible(en horas-mquina por semana)

FresadoraTornoRectificadora

500350150

El nmero de horas-mquina requeridas para elaborar cada unidad de los productos respectivos es

Coeficiente de productividad(horas-mquina por unidad)

Tipo de mquina Producto1 Producto2 Producto 3

FresadoraTornoRectificadora

953

340

502

El departamento de ventas indica que las ventas potenciales de los productos 1 y 2 exceden la tasa mxima deproduccin y que las ventas potenciales del producto 3 son de 20 unidades por semana. La ganancia unitariarespectiva sera de $50, $20 y $25, para los productos 1, 2 y 3. El objetivo es determinar cuntos productos decada tipo debe producir la compaa para maximizar la ganancia.

Formule un modelo de programacin lineal.

2Estos pasos son una sugerencia de ninguna manera es una camisa de fuerza. Son los pasos que recomienda el docente de acuerdo asu experiencia.