Agregar a favoritos      Ayuda      Português      Ingles     

Herramientas para la toma decisiones: La Programación Lineal

Enviado por fmarrero




Indice

2. Desarrollo
3. Métodos de solución
4. Aspectos Fundamentales Del Método Simplex
5. Bibliografía
6. Problemas

1. Introducción

Mucha gente sitúa el desarrollo de la programación lineal entre los avances científicos más importantes de la mitad del siglo XX, y debemos estar de acuerdo con esta afirmación si tenemos en cuenta que su impacto desde 1950 ha sido extraordinario. Se han escrito decenas de libros de texto sobre la materia y los artículos publicados que describen aplicaciones importantes se cuentan ahora por cientos. De hecho, una proporción importante de todo el cálculo científico que se lleva a cabo en computadoras se dedica al uso de la programación lineal y a técnicas íntimamente relacionadas. (Esta proporción se estimó en un 25%, en un estudio de la IBM).

Un modelo de programación lineal proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles.

En todos los problemas de Programación Lineal, el objetivo es la maximación o minimización de alguna cantidad.

2. Desarrollo

Contrucción de los Modelos de Programación Lineal

De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de Programación Lineal.

Requerimiento 1. Función objetivo. (F.O).

Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar.

Requerimiento 2. Restricciones y decisiones.

Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo.

Requerimiento 3. La F.O y las restricciones son lineales.

Deben utilizarse solamente ecuaciones lineales o desigualdades lineales.

Modelo standard de Programación Lineal

Optimizar Z = C1X1+ C1X2 +….+ Cn Xn). Función objetivo.

Sujeta a a11X1+ a11X2 +…..+ a1nXn) £ b1

a21X1+ a21X2 +…..+ a2nXn) £ b1

Restricciones

am1X1+ am1X2 +…..+ amnXn) £ bm

Debiendo ser

X1 ³ 0, X2 ³ 0, ….. Xn ³ 0

Donde :

Xj : variables de decisión, j = 1,2.., n.

n : número de variables.

m : número de restricciones.

aij , bi , cj constantes, i = 1,2.., m.

Pasos para la construcción del modelo

  1. Definir las variables de decisión.
  2. Definir el objetivo o meta en términos de las variables de decisión.
  3. Definir las restricciones.
  4. Restringir todas las variables para que sean no negativas.

Ejemplo: Taller de mantenimiento.

Un taller de mantenimiento fabrica dos tipos de piezas para la reparación de equipos fundamentales del proceso productivo. Estas piezas requieren un cierto tiempo de trabajo en cada una de las tres máquinas que las procesan. Este tiempo, así como la capacidad disponible (h) y la ganancia por cada pieza se muestran en el cuadro siguiente:

Máquina

Tiempo por Pieza

Fondo de Tiempo(h)

A

B

I

2

2

160

II

1

2

120

III

4

2

280

Ganancia ($/Pieza)

6

4

Se logra vender todo lo producido y se desea determinar la cantidad de piezas a fabricar que optimice la ganancia.

Formulando el modelo

X1 : Número de piezas del tipo A.

X2 : Número de piezas del tipo B.

Optimizando la ganancia (Z).

Max Z = 6X1 + 4X2

Sujeto a las restricciones:

2X1 + 2X2 £ 160 Fondo de tiempo de la máquina 1.

X1 + 2X2 £ 120 Fondo de tiempo de la máquina 2.

4X1 + 2X2 £ 280 Fondo de tiempo de la máquina 3.

Como ninguna variable implicada puede ser negativa.

X1 ³ 0; X2 ³ 0

3. Métodos de solución

El método simplex es un procedimiento iterativo que permite tender progresivamente hacia la solución óptima. Es un procedimiento sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad.

El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones, lo cual se logra añadiendo variables de holgura a cada inecuación del modelo, variables que nunca pueden ser negativas y tienen coeficiente 0 en la función objetivo. Para el modelo formulado anteriormente tenemos:

Z – 6X1 – 4X2 = 0

2X1 + 2X2 + s1 = 160

X1 + 2X2 + s2 = 120

4X1 + 2X2 + s3 = 280

Todas las variables son no negativas.

La solución básica inicial se obtiene seleccionando las variables de holgura como variables básicas, resultando conveniente disponer los valores como se muestran en la tabla siguiente:

i

VB

Z

X1

X2

S1

S2

S3

Bi

1

Z

1

- 6

-4

0

0

0

0

2

S1

0

2

2

1

0

0

160

3

S2

0

1

2

0

1

0

120

4

S3

0

4

2

0

0

1

280

Cada ecuación debe tener una única variable básica(VB), con el coeficiente unidad en la fila correspondiente.

Esta solución básica debe ser examinada para observar si puede ser mejorada. La presencia de coeficientes negativos en la FO indica que la solución básica puede ser mejorada, pues el valor de Z se incrementará.

Cuando no hay coeficientes negativos, significa que la solución es óptima.

Para encontrar una solución mejorada es necesario:

  • Elegir la variable que entra como la de mayor coeficiente negativo (X1)
  • Elegir la variable que sale como aquella que al ser removida permita que la variable que entra a la base pueda tener un valor tan grande como sea posible, sin violar alguna de las restricciones en el modelo. En este caso la variable S3 deja la base y a su vez X1 se introduce como la nueva variable básica.
  • El elemento pivote es el coeficiente que está en la intersección de la columna de la variable que entra y la fila de la variable que sale.
  • Los valores correspondientes a la nueva fila pivote se obtienen dividiendo los coeficientes de la fila pivote en la tabla inicial por el elemento pivote.
  • Las otras filas de la solución mejorada se calculan por la expresión:

Nueva fila = Fila anterior – elemento de la columna pivote(nueva fila pivote)

Así, se obtiene la siguiente tabla:

i

VB

Z

X1

X2

S1

S2

S3

Bi

0

Z

1

0

- 1

0

0

1.5

420

1

S1

0

0

1

1

0

-0.5

20

2

S2

0

0

1.5

0

1

- 0.25

50

3

X1

0

1

0.5

0

0

0.25

70

Como se puede apreciar esta no es aún la solución óptima ¿Por qué?

Iterando nuevamente se obtiene la tabla correspondiente que se muestra a continuación:

i

VB

Z

X1

X1

S1

S2

S3

Bi

0

Z

1

0

0

1

0

1

440

1

X2

0

0

1

1

0

- 0.5

20

2

S2

0

0

0

- 1.5

1

0.5

20

3

X1

0

1

0

- 0.5

0

0.5

60

¿Es esta la solución óptima? Si lo es determine entonces los valores de las variables para el óptimo.

Se ha aplicado el algoritmo para el caso del modelo estándard, cuando se presentan problemas con restricciones ³ o = y el criterio de optimización es mínimo, entonces hay que introducir variables artificiales y se sugiere convertir el problema en un problema de maximizar.

4. Aspectos Fundamentales Del Método Simplex

  1. Encuentra una solución óptima
  2. Es un método de cambio de bases
  3. Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0
  4. Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción.

Dualidad

Asociado a cada problema de Programación Lineal existe un llamado dual, de hecho al de Programación Lineal se le llama primal. La forma general del problema dual es la siguiente:

Optimizar Z = b1Y1+ b1Y2 +….+ bn Yn). Función objetivo.

Sujeta a a11Y1+ a11Y2 +…..+ am1Y1) £ C1

a21Y1+ a22Y2 +…..+ am2Y2) £ C1

. Restricciones

.

a1mY1+ a2mY2 +…..+ amnYm) £ Cn

Para facilitar la comprensión de lo anterior considérese el diagrama siguiente:

Primal

Dual

C1……. Cn (1)

a11 b1

(2) (3)

am1 bm

b1……. bm (3)

(2) a11……. am1 C1

(1)

C2

Variables

X1……. Xn

Variables

Y1……. Ym

El problema dual tiene las siguientes características:

  • El el objetivo de la optimización es contrario al del primal.
  • Las inecuaciones de restricción son inversas.
  • La solución del dual es la misma que la del primal.

Desde el punto de vista económico, el significado de las variables duales es de gran interés para los gerentes, ya que representan el valor por unidad de recurso adicional, lo cuál permite tomar decisiones sobre donde invertir para incrementar las utilidades.

Análisis de Sensibilidad

El objetivo del análisis de sensibilidad es determinar la influencia de ciertos valores en la solución óptima, que nos permite la interpretación razonable de los resultados obtenidos. En muchos casos la información lograda por la aplicación del análisis de sensibilidad puede ser más importante y más informativa que simple resultado obtenido en la solución óptima.

El análisis deviene del resultado de los cambios en:

  • Los coeficientes en la función objetivo.
  • Los términos independientes en las restricciones.

5. Bibliografía

  1. Arbonas, M.E. Optimización Industrial (I): Distribución de los recursos. Colección Productica No. 26. Marcombo S.A, 1989.
  2. Arbonas, M.E. Optimización Industrial (II): Programación de recursos. Colección Productica No. 29. Marcombo S.A, 1989.
  3. Anderson, D.R., Sweeney.J. , Williams,T.A. , Introducción a los Modelos Cuantitativos para Administración. Grupo Editorial Iberoamérica. 1993.
  4. Moskowitz,H. y Wright G.P. Investigación de Operaciones. Prentice_Hall Hispanoamericana S.A. 1991.
  5. Trujillo,J;Batista,A: Métodos Económicos-Matemáticos I.Editorial ISPJAE, Habana,1986.
  6. Taha,H: Investigación de Operaciones.Alfaomega,México,1995.
  7. Buffa,E: Operations Management: Problems and Models. Edición Revolucionaria,La Habana, 1968.

6. Problemas

1- Una empresa se dedica a la producción de pinturas para interiores y exteriores para su distribución al mayoreo. Se utilizan dos materiales básicos, A y B, para producir las pinturas. La disponibilidad máxima de A es de 6 toneladas diarias; la de B es de 8 toneladas por día. La necesidad diaria de materia prima por tonelada de pintura para interiores y exteriores se resumen en la tabla que sigue:

Toneladas de MP por Disponibilidad

tonelada de pintura máxima en toneladas

Exterior Interior

Materia prima A 1 2 6

Materia prima B 2 1 8

El estudio de mercado ha establecido que la demanda diaria de pintura para interiores no puede ser mayor que la pintura para exteriores en más de una tonelada. Así mismo, el estudio señala que la demanda máxima de pintura para interiores está limitada a dos toneladas diarias.

La ganancia por tonelada es de $3000 para la pintura de exteriores y $2000 para la pintura de interiores.

Cuánta pintura para exteriores e interiores debe producir la empresa todos los días para maximizar el ingreso bruto?

2- A una empresa se le ha planteado la tarea de cumplir un contrato de explotación de dos productos A y B para el próximo semestre. El contrato estipula que deben ser entregados como mínimo 2000 unidades de ambos productos, siendo al menos 800 de B. Los precios de venta son de 50 y 80 pesos por unidad para A y B respectivamente. La empresa cuenta con 3 establecimientos que pueden acometer esa tarea disponiendo los mismos de 550, 800 y 930 horas de tiempo productivo en el semestre respectivamente.

El tiempo de producción que toma cada producto, en horas, para cada establecimiento, así como el costo por hora de producción de cada uno, se dan en la tabla siguiente:

Productos

Establecimientos A B Costo/hora(pesos/h)

1 0,9 1,3 25

2 1,2 - 20

3 1,0 1,5 22

Para balancear el uso de la fuerza laboral, se desea por la empresa que el % de capacidad productiva utilizada en los tres establecimientos sea la misma.

Por otra parte para el terminado de los productos se utiliza una materia prima de importación de las que disponen 3000 unidades, siendo la norma unitaria de consumo de una unidad para A y 2 para B.

Plantee el modelo matemático que permita conocer la forma más provechosa de cumplir el contrato.

3- Existen dos centrales cerca de la bahía de Nipe: el Nicaragua y el Rafael Freire, para los cuales se plantea revincular sus dos zonas cañeras de modo que se minimicen los costos de producción de azúcar (incluyendo los costos de transportación de caña).

El costo de producción por arroba de azúcar para cada caso se muestra a continuación:

Zona Nicaragua Rafael Freire

I 1,25 1,30

II 1,80 1,60

El central Nicaragua debe moler entre un mínimo de 20 millones de arrobas de caña y un máximo de 30 millones de caña; y el Rafael Freire entre 15 y 25 millones de arrobas de caña.

Las zonas cañeras a distribuir son dos: la Zona I con una producción de caña estimada en 20 millones de arrobas, y la zona II con 15 millones de arrobas. No debe quedar caña sin cortar.

En la tabla siguiente se muestran los factores de conversión de arrobas de caña necesarias para producir una arroba de azúcar los cuales varían en cada central y por zona cañera:

Zona Nicaragua R. Freire

I 8,35 9,10

II 8,00 7,70

La meta de producción para los dos centrales en conjunto es por lo menos de 57500 arrobas de azúcar. Todos los datos del problema corresponden a una zafra.

4- Una empresa siderúrgica produce tres tipos de rollos, cada uno hecho de una diferente aleación. El problema consiste en determinar las cantidades de cada aleación que debe producirse, dentro de las limitaciones de venta y de las capacidades de las máquinas, para hacer máximas las ganancias. Los datos sobre capacidades y otros elementos se presentan en las siguientes tablas.

Operación

Máquinas

Turnos de 8 h/Semana

Tiempo Ocioso en %

Caja de Recocido

4

21

5

Recocido Continuo

1

20

10

Molinos Continuos

1

12

0

Aleación

Operación

Velocidad

Potencial Ventas (T/mes)

Ganancia (T)

1

Caja de Recocido

28 h/10 T

1250

25

Molinos Continuos

15 m/min

Recocido Continuo

6 m/min

Molinos Continuos

8 m/min

2

Caja de Recocido

35 h/10 T

250

35

Recocido Continuo

11 m/min

Molinos Continuos

6 m/min

3

Recocido Continuo

5 m/min

1500

40

Molinos Continuos

6 m/min

Los rollos de cada aleación son de 122 m de largo y pesan 4 T.4- Una empresa siderúrgica produce 3 tipos de rollos, cada uno hecho de una diferente aleación.

5- Un barco tiene 3 bodegas: en la proa, en la popa y en el centro. Los límites de capacidad son:

Proa 2000t 100000 metros cúbicos

Centro 3000t 135000 metros cúbicos

Popa 1500t 30000 metros cúbicos

Pueden ser transportadas las cantidades de mercancías que aparecen en la siguiente tabla. Puede aceptarse el total o una porción cualquiera de cada artículo.

Volumen en Ganancia en

Artículo Cantidad en toneladas t/ metro cúbico pesos/toneladas

A 6000 60 6

B 4000 50 8

C 2000 25 5

Para preservar el equilibrio del barco, el peso en cada bodega debe ser proporcional a la capacidad en toneladas. Cómo debe distribuirse la carga para hacer máxima la ganancia.

6- Una empresa tiene 2 talleres A y B. En ambos se producen los productos tipo 1 y tipo2 en base a las materias primas M y N. La empresa dispone diariamente de 10 t de M y 4t de N.

El consumo de M y N por cada producto en cada taller es el siguiente en Kg:

Taller 1 Taller 2

M N M N

Producto 1 0,7 0,3 Producto 1 0,6 0,4

Producto 2 0,8 0,2 Producto 2 0,9 0,1

La capacidad de producción del Taller 1 es de 4000 productos 1 o 6000 productos 2 o la combinación de ambos. El taller 2 puede producir 5000 productos 1 o 7000 productos 2 o la combinación de ambos.

Deben producirse al menos 4000 productos 1 y la cantidad de productos 2 que se produzcan en ambos talleres debe ser la misma.

El costo de producción del producto 1 en el taller 1 es de $0,60 y del producto 2, $0,80 El del taller 2 son un 20% mayores.

Si las capacidades de producción deben aprovecharse como mínimo a un 90% y a un 85% en cada taller. Plantee el modelo matemático que minimice los costos de la empresa.

7- En el combinado del vidrio de la Lisa se producirán en el próximo período 2 modelos de jarrones, uno de cenicero y 2 modelos de vasos de cristal para el consumo nacional.

En la obtención de estos productos se combinan dos materias primas (P y Q), siendo el consumo en Kg para cada producto y el costo de producción los que se muestra en la tabla a continuación:

Jarrones Cenicero Vasos de Cristal

1 2 1 2

P 0,03 0,63 0,07 - -

Q 0,09 0,11 0,05 0,01 0,04

Costo 2 3 1 0,5 1

($/u)

La materia prima Q es de importación y solo se dispone de 820 Kg en el período y de la materia prima P se recibirán 560 Kg. Todos los productos pasan por tres procesos: horneado, acabado y envasado de la producción.

En el Dpto de horneado pueden colocarse en un horno 200 jarrones o 350 ceniceros o 400 vasos o una combinación factible( este Dpto cuenta con 4 hornos de este tipo en el período)

En el Dpto de acabado se le da un tratamiento especial a los modelos de tipo 2 de jarrones y vasos de cristal, pudiendo atenderse 10 y 20 jarrones y vasos por hora respectivamente.

En el Dpto de envasado se invierten 3, 2 y 3 minutos en el embalaje de los jarrones, ceniceros y vasos respectivamente.

Se espera que para el período analizado se contará con un fondo de tiempo de 280 horas para cada uno de estos Departamentos.

Por las características de la demanda se desea que la cantidad de vasos producidos sea al menos el doble de la de jarrones y que por cada jarrón del modelo tipo 1 se produzca un cenicero.

Plantee el modelo m+atemático que permita obtener la planificación óptima de la producción.

8- La empresa confitera Habana se dedica a la elaboración de un amplio surtido de caramelos y bombones, considerándose que existen cuatro grupos fundamentales de estos productos, los cuales son:

Grupo Precio de venta($/Kg)

1 Caramelos especiales 1,37

2 Caramelos normales 1,23

3 Bombones surtido 5,00

4 Bombones especiales 6,00

La materia prima fundamental de los grupos 1 y2 es azúcar refino, colorante y saborizante y de los grupos 3 y 4, azúcar refino, cocoa, altea y licores.

Los caramelos pueden ser de tres sabores diferentes y los bombones especiales pueden ser elaborados con dos tipos de licor.

En la tabla siguiente se muestra el insumo( Kg de mat prima/ Kg de producto), disponibilidades y costo total.

M. PRIMA GRUPO DE PRODUCTOS DISPON(T) COSTO($)

1 2 3 4

azúcar refino 0,7 0,6 0,5 0,35 60 18000

colorante 0,2 0,2 - - 2 800

saborizante 1 0,1 0,2 - - 5 500

saborizante 2 0,1 0,2 - - 5 600

saborizante 3 0,1 0,2 - - 4 400

cocoa - - 0,3 0,5 45 27000

altea - - 0,2 0,05 5 700

licores 1 - - - 0,1 4 1200

licores 2 - - - 0,1 3 900

En la producción intervienen 2 grupos de obreros calificados cuyas productividades son:

OBREROS PRODUCTIVIDAD(T/H) por SALARIO POR HORA

grupo de producto

1 2 3 4

Obrero A 0,04 0,04 0,05 0,04 0,90

Obrero B 0,015 0,03 0,02 0,04 0,80

Se dispone de 40 obreros de calificación A y 60 de calificación B, los cuales laborarán 24 días al mes durante 8 horas cada día. No existen restricciones en cuanto al fondo de tiempo productivo disponible de sus máquinas. Plantee el modelo matemático que maximice la ganancia.

Categoría: Administración y finanzas

Categoría propuesta: Investigación de Operaciones

Palabras claves

Programación lineal, Investigación de Operaciones, Optimización, Método Simplex


Datos de los autores

Fernando Marrero Delgado. Máster en Informática Aplicada. Ingeniero Industrial. Profesor Asistente Departamento de Ingeniería Industrial. Universidad Central de Las Villas. Santa Clara. Cuba.
fmarrero[arroba]fce.uclv.etecsa.cu

Javier Asencio García. Doctor en Ciencias Técnicas. Ingeniero Industrial. Profesor Titular. Departamento de Ingeniería Industrial. Universidad Central de Las Villas. Santa Clara. Cuba. asencio[arroba]fce.uclv.etecsa.cu

René Abreu Ledón. Máster en Ingeniería Industrial. Ingeniero Industrial. Profesor Asistente Departamento de Ingeniería Industrial. Universidad Central de Las Villas. Santa Clara. Cuba. rabreu[arroba]fce.uclv.etecsa.cu

René Orozco Sánchez. Ingeniero Industrial. Aspirante a Máster del Departamento de Ingeniería Industrial. Universidad Central de Las Villas. Santa Clara. Cuba. fmarrero[arroba]fce.uclv.etecsa.cu

Hugo R. Granela Martín. Doctor en Ciencias Técnicas. Ingeniero Industrial. Profesor Auxiliar. Departamento de Ingeniería Industrial. Universidad Central de Las Villas. Santa Clara. Cuba.
hugran[arroba]fce.uclv.etecsa.cu

 

 

Autor:


Fernando Marrero Delgado



Comentarios


Trabajos relacionados

Ver mas trabajos de Programacion

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda