Programacion Lineal Para Administracion

5/24/2018 Programacion Lineal Para Administracion

1/49

PROGRAMACIN LINEALPARA ADMINISTRACIN

RENZO DEVOTO RATTO

EDUARDO RUIZ VIDAL

EDICIONES UNIVERSITARIAS DE VALPARASOPONTIFICIA UNIVERSIDAD CATLICA DE VALPARASO


2/49

Quedan rigurosamente prohibidas, sin la autorizacin escrita de los titulares delCopyright, bajo las sanciones establecidas en las leyes, la reproduccin total o

parcial de esta obra por cualquier medio o procedimiento, comprendidos lareprografa y el tratamiento informtico y la distribucin de ejemplares de ella

mediante alquiler o prstamo pblicos.

Renzo Devoto Ratto, Eduardo Ruiz Vidal, 2003Inscripcin N 133.082

ISBN 956-17-0343-2

Tirada de 300 ejemplares

Derechos Reservados

Edicione s Unive rsitarias de ValparasoPontificia Universidad Catlica de Valparaso

Calle 12 de Febrero 187, ValparasoFono (32) 273087 - Fax (32) 273429

[email protected]

Diseo Grfico: Guido Olivares S.Diagramacin: Mauricio Guerra P.

Correccin de Pruebas: Osvaldo Oliva P.

Impreso en Salesianos S.A.

HECHO EN CHILE


3/49

A Mnica y Alessan dro, amadosmot ivos para perseverar y gan ar le ala in ercia. A la memoria d e Angelo,

nu estro ngel d e la gua rd a, que seasoma da a da ent re n ubes deapa cible nostalg ia.

A mis pa dres, Luis y Rina, por lasuerte d e an compa rt ir recuerd os yprolongar momentos.

RDR

A mis pad res, Edu ardo y Ena, enagrad ecimiento por tan tos paseos yconversaciones.

ERV


4/49


5/49

Los autores agradecen a todas aquellas personas e instituciones que co-operaron para que este libro fuera terminado y publicado. An corriendoel riesgo de cometer alguna omisin importante, los principales destina-tarios de estos agradecimientos son los siguientes:

Todos los estudiantes que han utilizado algn material de este libro, a lolargo de ms de dos dcadas. El nivel de aprendizaje alcanzado por cadauno de ellos ha sido uno de los principales incentivos para llevar adelanteesta tarea.

Los ayudantes de los cursos Investigacin de Operaciones e Investiga-cin y Administracin de Operaciones I de los distintos planes de estu-dios de la carrera de Ingeniera Comercial de la Pontificia UniversidadCatlica de Valparaso, especialmente en la dcada de los 80. Cada uno deellos aport alguna idea interesante para preparar ejemplos y ejercicios.

Un agradecimiento muy especial a Gonzalo Reyes Budinich, quien en supoca de ayudante- colabor intensivamente en la preparacin del docu-mento docente que sienta las bases de este libro.

Los colegas de la Escuela de Ingeniera Comercial de la Pontificia Universi-dad Catlica de Valparaso, por los consejos y por el apoyo moral brindados.

La Pontificia Universidad Catlica de Valparaso, por el apoyo financieroprestado para la publicacin de este libro, a travs del Fondo de Publica-ciones.

El personal de Ediciones Universitarias de Valparaso, de la Pontificia Uni-

versidad Catlica de Valparaso, por el trabajo profesional desarrollado. Nuestras familias, que adoptaron como propio este proyecto, por todas las

horas regaladas con amor para facilitar su consecucin.

A todos ellos........., muchas gracias!

LOSAUTORES

AGRADECIMIENTOS


6/49


7/49

PRLOGO

Este libro est basado en los apuntes de clases y documentos docentes de losautores, preparados a lo largo de ms de 20 aos de experiencia impartiendoprimero la asignatura Investigacin de Operaciones y luego la asignaturaInvestigacin y Administracin de Operaciones I, en la carrera de Ingeniera

Comercial de la Pontificia Universidad Catlica de Valparaso.

Como tal, su orientacin es hacia los estudiantes y profesionales de la Admi-nistracin y Direccin de Empresas. Por ello, se ha preferido un enfoque conmenor rigor matemtico de lo que es habitual en este tipo de materias. Noobstante, el tratamiento de los temas se realiza en un marco de rigor acad-mico.

Seguramente puede parecer redundante la preparacin de un libro de estaespecie, en circunstancias que existe una bibliografa muy nutrida en rela-cin al tema de la Programacin Lineal.

Al respecto, es obvio que no se pretende realizar un gran aporte al desarrollode la disciplina, existiendo tantos brillantes autores en este campo. En cam-

bio, se ha formulado el objetivo ms modesto de aportar un mayor grado deintegracin de algunas temticas, que facilite el aprendizaje y que permita unconocimiento ms verstil de la Programacin Lineal.

Asimismo, es probable que tambin parezca irrelevante la preparacin deeste libro, utilizando el argumento de que los estudiantes y profesionales dela Administracin podran hacer uso de la Programacin Lineal, sin necesi-dad de conocer los fundamentos del modelo y de los algoritmos de resolucin,apoyados slo en una nutrida variedad de eficaces y eficientes programascomputacionales ad hoc.

La opinin de los autores es que tal enfoque es altamente riesgoso, por cuan-to debido a ello esta rama de la Investigacin de Operaciones puede llegar aser visualizada como una herramienta relativamente simple al lado de otras,pero a la vez muy poderosa, con la consecuente tentacin de aplicarla enmuchas situaciones en que ello no procede, por parte de personas no califica-


8/49

das. Slo un profundo conocimiento de los aspectos tericos involucrados,permitir al usuario lograr un adecuado aprovechamiento de esta herramienta

y del software disponible. En caso contrario, probablemente la situacin ser

similar a la de una locomotora manejada por un nio.El libro est dividido en 5 captulos y contiene 3 apndices, cuyo contenidogeneral se presenta a continuacin.

El Captulo I, denominado El modelo de programacin lineal, presenta losaspectos fundamentales del modelo, incluyendo sus supuestos, tras una br e-

vsima mencin a la Investigacin de Operaciones y a la Programacin Mate-mtica. El contenido fundamental del captulo lo constituye la presentacinde una variada gama de formulaciones de problemas de programacin lineal(PPL), con la finalidad de que el lector visualice las posibilidades de aplica-

cin y se introduzca a la formulacin de modelos.El Captulo II, denominado Mtodos de resolucin de PPL, presenta el mto-do Simplex, tanto en la modalidad de Simplex Revisado como en la de CuadroSimplex. Se pone especial nfasis en alcanzar una adecuada integracin en-tre ambas modalidades, para lo cual se asigna la misma importancia a cadauna de ellas y se estudian todas sus interrelaciones ms importantes.

El Captulo III, denominado Dualidad, presenta el problema Dual, las rela-ciones primal dual y algunos aspectos de la interpretacin econmica de ladualidad. Asimismo, se complementa el tema de resolucin de PPL, con la

presentacin de la importante variante denominada Simplex Dual.El Captulo IV, denominado Anlisis de Sensibilidad, aborda la importantetemtica del anlisis post-optimal, utilizando el conocimiento terico delmtodo Simplex y de las interrelaciones existentes entre sus distintas varian-tes. Junto con tratar en forma individual cada una de las modificacionesposibles, se presenta un procedimiento general para tratar cambios simult-neos en ms de un parmetro.

El Captulo V, denominado Programacin Entera, presenta el problema deprogramacin lineal cuando se agrega como restriccin adicional que una o

ms de sus variables de decisin slo pueden tomar valores enteros. Aqu seresuelve un ejemplo bsico utilizando el algoritmo de ramificacin y acota-miento. Lo anterior se complementa con un extenso anlisis grfico.

Todos los captulos finalizan con la presentacin de algunos ejercicios re-sueltos y con una proposicin de ejercicios para trabajo personal, salvo loscaptulos I y V, en los cuales slo se proponen ejercicios. En relacin a losejercicios presentados, no se ha pretendido alcanzar un alto nivel de origina-lidad, cosa de por s difcil, prefirindose ms bien una adecuada seleccin de


9/49

ejercicios propios y adaptados de otras fuentes. Todos los ejercicios resueltosde los captulos II, III y IV y los ejercicios propuestos en los captulos II y IIIprovienen de pruebas o exmenes preparados ya sea por los autores o por el

exprofesor del rea de Mtodos Cuantitativos de la Escuela de IngenieraComercial de la Pontificia Universidad Catlica de Valparaso y actual ejecu-tivo de una importante empresa naviera, seor Rodrigo Vergara Barbagelata,a quien agradecemos su generosa contribucin. En otros casos, se han efec-tuado adaptaciones de ejercicios que ya forman parte de la tradicin de laenseanza de la Investigacin de Operaciones, siendo difcil determinar suautora original.

El Apndice N 1, denominado Nociones bsicas de conjuntos convexos,presenta en forma muy breve el concepto de conjunto convexo y su relacincon la resolucin de un sistema de inecuaciones lineales.

El Apndice N 2, denominado Matrices y Sistemas de Ecuaciones Lineales,comienza con definiciones y operaciones bsicas de matrices y vectores, parafinalizar con la presentacin de algunos mtodos de resolucin de sistemasde ecuaciones lineales, con nfasis en el mtodo de resolucin de Gauss-

Jordan, procedimiento integrante del mtodo Simplex.

Como requisito fundamental para lograr un adecuado aprovechamiento deeste documento, el estudiante debe contar con nociones fundamentales dematrices y sistemas de ecuaciones lineales, con una perspectiva y profundi-dad similar a la considerada en el Apndice N 2 ya citado. A aquellos lectoresque encuentren dificultades para comprender las bases del algoritmo de re-solucin Simplex, se les recomienda repasar las materias presealadas.

El Apndice N 3, denominado Nociones de Programacin No Lineal, pre-senta una breve introduccin a la programacin matemtica, cuando se rela-

ja la exigencia de linealidad para la funcin objetivo y/o una o ms restriccio-nes. Por medio de un ejemplo, se pueden apreciar algunos mtodos particu-lares de resolucin para este tipo de problemas.

Se espera que los principales aportes de este libro, para el aprendizaje yaplicacin de la Programacin Lineal, se encuentren en el tratamiento que seda a algunos temas, en relacin al que es habitual en la bibliografa disponi-

ble. En tal sentido, se pretende reivindicar la importancia de la modalidad deSimplex Revisado y de sus relaciones con las otras modalidades de mtodoSimplex. Asimismo, se asume una perspectiva integradora, la cual culminaen el tratamiento del tema de anlisis de sensibilidad, el cual debiera resultarfcilmente asimilable para cualquier lector que haya comprendido los otrostemas tratados.


10/49

Finalmente, cabe sealar que es prcticamente imposible que este libro seencuentre exento de errores, especialmente debido a la complejidad del tra-

bajo de digitacin, dada la notacin utilizada, aunque ha sido exhaustivamente

revisado y corregido. En todo caso, los autores asumen toda la responsabili-dad por los errores de distinta naturaleza que puedan existir, agradeciendo alos lectores se los hagan notar, para proceder a enmendarlos en futuras edi-ciones. Asimismo, se agradece todo tipo de sugerencias que puedan mejorartanto el contenido como la presentacin de este libro.

RENZODEVOTORATTOEDUARDORUIZVIDAL

Valparaso, marzo de 2003.


11/49

NDICE

CAPTULO I:EL MODELO DE PROGRAMACIN LINEAL .................Pg. 15

1. LA INVESTIGACIN DE OPERACIONES .............................................. 15

2. LA PROGRAMACIN MATEMTICA ..................................................... 17

2.1) El modelo general de Programacin Matemtica........................... 172.2) Ejemplos bsicos de P.M. y resolucin grfica .............................. 18

3. EL MODELO DE PROGRAMACIN LINEAL .......................................... 24

3.1) El modelo matemtico de Programacin Lineal ............................ 243.2) Ejemplos de Problemas de Programacin Lineal (PPL) .................. 263.3) Supuestos del modelo de Programacin Lineal ............................. 42

4. EJERCICIOS PROPUESTOS ................................................................. 44

CAPTULO II: MTODOS DE RESOLUCIN DE PPL ............................... 53

1. CONCEPTOS FUNDAMENTALES ......................................................... 532. INTRODUCCIN AL MTODO SIMPLEX .............................................. 55

2.1) Presentacin general .................................................................... 552.2) Transformaciones en PPL para uso de Simplex ............................ 57

3. MTODO SIMPLEX REVISADO ............................................................ 61

4. CUADRO O TABLEAU SIMPLEX ........................................................... 75

4.1) Cuadro Simplex sin variables artificiales ...................................... 764.2) Cuadro Simplex con variables artificiales ..................................... 80

5. RELACIONES SIMPLEX REVISADO-CUADRO SIMPLEX ...................... 87

6. EJERCICIOS RESUELTOS ................................................................... 93

7. EJERCICIOS PROPUESTOS ................................................................. 99

CAPTULO III:DUALIDAD ..................................................................... 105

1. EL PROBLEMA DUAL DE UN PPL ...................................................... 105

2. RELACIONES PRIMAL-DUAL ............................................................. 108

3. TEOREMAS DE LA DUALIDAD .......................................................... 114


12/49

4. MTODO SIMPLEX- DUAL ................................................................. 119

5. INTERPRETACIN ECONMICA DE LASOLUCIN PTIMA DEL DUAL .......................................................... 123

6. EJERCICIOS RESUELTOS ................................................................. 1307. EJERCICIOS PROPUESTOS ............................................................... 140

CAPTULO IV:ANLISIS DE SENSIBILIDAD ......................................... 147

1. INTRODUCCIN ................................................................................ 147

2. PROCEDIMIENTO DE ANLISIS DE SENSIBILIDAD .......................... 148

2.1) Cambios en vector b ................................................................... 1502.2) Cambios en vector c ................................................................... 1502.3) Cambios en matriz A(variables no bsicas)................................ 157

2.4) Introduccin de nuevas variables ............................................... 1602.5) Cambios en matriz A(variables bsicas) .................................... 1612.6) Adicin de nuevas restricciones ................................................. 1652.7) Procedimiento general para cambios combinados ...................... 166

3. EJERCICIOS RESUELTOS ................................................................. 170

4. EJERCICIOS PROPUESTOS ............................................................... 177

CAPTULO V: PROGRAMACIN ENTERA .............................................. 185

1. INTRODUCCIN ................................................................................ 185

1.1) Solucin de un Problema de Programacin Entera ..................... 1852. ALGORITMO DE RAMIFICACIN Y ACOTAMIENTO ........................... 188

2.1) El Algoritmo de Ramificacin y Acotamiento .............................. 1882.2) Resolucin de un Ejemplo .......................................................... 191

3. EJERCICIOS RESUELTOS ................................................................. 199

APNDICE N 1:NOCIONES BSICAS DE CONJUNTOS CONVEXOS .............................. 201

APNDICE N 2:

MATRICES Y SISTEMAS DE ECUACIONES LINEALES ........................... 207

APNDICE N 3:NOCIONES DE PROGRAMACIN NO LINEAL ........................................ 275

BIBLIOGRAFA ...................................................................................... 291


13/49

15

CAPTULO I / EL MODELO DE PROGRAMACIN LINEAL

Captu lo I

EL MODELO DE PROGRAMACIN LINEAL

1. LA INVESTIGACIN DE OPERACIONES

Desde que, a comienzos del siglo XX, Frederick Taylor, Henry Gantt,Frank y Lilian Gilbreth, entre otros, realizaron las primeras aplicacio-nes del mtodo cientfico a los problemas de las organizaciones, a la

vez que Henry Fayol postul los principios generales de la administra-cin, podra decirse que la administracin de organizaciones dej deser una actividad intuitiva.

Mientras ms complejas y especializadas se hicieron las organizacio-

nes industriales, los problemas a resolver por los administradores fue-ron alcanzando una complejidad que no slo era inherente a la situa-cin bajo anlisis, sino tambin a su interrelacin con otros compo-nentes de la organizacin, lo que reforz la necesidad de adoptar unpunto de vista cientfico y sistemtico para interpretar, analizar y re-solver los problemas de empresas e instituciones.

En este contexto se inscribe una disciplina o actividad denominadaInve st igacin de Operacion es (IO), la cual se desarroll a partir de laSegunda Guerra Mundial, aunque existen trabajos anteriores que po-

dran situarse en la misma lnea. En esa guerra, el problema de asig-nacin efectiva de recursos escasos a las diversas operaciones milita-res, al igual que la resolucin de otros problemas que requeran elanlisis de las operaciones militares, dio lugar a la formacin de gru-pos de cientficos en Inglaterra y en EE.UU. que realizaron importan-tes aportes a la resolucin de problemas tcticos y estratgicos.

Despus de la Segunda Guerra Mundial, lentamente primero y con


14/49

16

RENZO DEVOTO RATTO / EDUARDO RUIZ VIDAL

gran nfasis a partir de la dcada de 1950, esta disciplina pas desdeel mbito de las operaciones militares al de las operaciones industria-les, siendo reconocida hoy como una actividad fundamental en la ad-

ministracin moderna de organizaciones, as como en otros camposde la actividad humana. Precisamente, el fuerte desarrollo terico dela Programacin Lineal y su rpida y exitosa introduccin al campoindustrial a partir de la dcada de 1950, marc el inicio de una ola deaplicaciones empresariales de otras tcnicas y modelos de la IO, quehasta entonces eran conocidos slo por los especialistas.

Actualmente, la mayor parte de las empresas de los pasesindustrializados utilizan tcnicas y modelos especficos de la Investi-gacin de Operaciones, tales como la Programacin Lineal, la Progra-

macin Entera, la Simulacin, la Programacin Dinmica, la Teorade Colas o Modelos de Fenmenos de Espera, los Modelos deInventarios, las Cadenas de Markov, los Modelos de Secuenciacin(CPM, PERT), entre otras.

La siguiente definicin de Investigacin de Operaciones pretendesintetizar los principales aspectos que caracterizan a esta actividad odisciplina:

La Inves ti gacin d e Operaciones (IO) es la apl ica cin d el mtod o cient-fico al estu d io de los problema s de toma de decisin en situ acionesdeterm instica s o pr obab ilsti cas a l in terior d e sist ema s comp lejos, con-sid eran do la form ula cin d e un m odelo generalm ente ma temtico quepermita estudia r el problema y desarrol lar u na solucin que ind ique elmejor u ptim o cur so de accin posib le, coherente con los objet ivosgloba les del sistema.

Las dos caracters t icas ese ncia les , que distinguen a la IO de otrasdisciplinas o actividades que podran asimilarse a la anterior defini-cin, son:

i) El modelamiento generalmente matemtico de los problemas dedecisin.

ii) La bsqueda de la mejor o la ptima solucin de los problemas dedecisin.

Otras caractersticas de la IO, aunque no necesariamente esenciales,son la casi ineludible participacin de grupos interdisciplinarios y de


15/49

17


los computadores en su aplicacin. Lo primero proviene del hecho deque los problemas a resolver son habitualmente muy complejos y conconsecuencias sobre distintas partes del sistema. Lo segundo provie-

ne del hecho que la resolucin de un problema, mediante la IO, re-quiere habitualmente procesar gran cantidad de datos numricos.

La m eto dologa de un es t udio de IOpuede ser resumida a travs delas siguientes fases:

a) Form ulac in de l problema:implica definir objetivos y metas, exa-minar los recursos internos para lograrlos y los aspectos relevan-tes del entorno, determinar programas de accin alternativos.

b) Desarrol lo de u n m odelo para repres en tar el problem a que s e

es t es tudiando:reducir el problema a una estructura gene-ralmente matemtica en la cual se encuentran presentes el o losobjetivos y las restricciones explcitas y subyacentes para lo-grarlos. Esto puede implicar la formulacin de varios modelos ysu confrontacin con la realidad, hasta hallar el ms adecuado.

c) Bsqueda de una so lucin a l problem a:hallar la mejor o laptima solucin para el logro del objetivo, en el marco de lasrestricciones.

d) Poner en prct ica la so lucin:implantar la solucin, ya sea amodo de prueba o en forma definitiva.

e) Establec imien to de controles sobre la so lucin:prestar aten-cin a los cambios en la situacin, a fin de incorporarlos al mo-delo retroalimentacin.

Estas fases no son estrictamente secuenciales, existiendo un lmitedifuso entre cada una de ellas.

2. LA PROGRAMACIN MATEMTICA

2 .1 ) EL MODELO GENERAL DE PROGRAMACIN MAT EMTI CA

La Programacin Matemtica (PM) provee modelos matemticos aso-ciados con situaciones-problema que involucran decisiones de corto omediano plazo, en que se intenta optimizar (maximizar o minimizar)un determinado objetivo, pudiendo existir restricciones a las decisio-nes posibles para lograrlo.


16/49

18


Una aplicacin tpica de la PM corresponde a situaciones en que sedebe asignar un conjunto de recursos limitados entre actividades quecompiten por su utilizacin, existiendo la intencin de realizar la asig-

nacin de recursos en una forma tal que se maximicen utilidades o seminimicen costos.

Considerando n variables de decisin xj, el modelo general de PMmultidimensional restringidaest compuesto por una funcin ob-

jetivo (FO), sujeta a m restricciones propias de la situacin proble-ma.

La funcin objetivo es una representacin matemtica de la meta totalde optimizacin establecida en trminos de las variables de decisin.

El conjunto de las m restricciones, expresado en trminos de lasvariables de decisin, es una representacin matemtica de las condi-

ciones simultneas que se deben cumplir al establecer los valores paralas variables de decisin, como consecuencia de las limitaciones exis-tentes en la situacin-problema para el logro del objetivo.

En general, los m odelos m s re levantes de la PMson:

* Modelos de programacin lineal* Modelos de programacin no lineal* Modelos de programacin entera

2 .2 ) EJ EMPLOS BSICOS DE PM Y RESOLUCIN GRFI CA

Ejem plo bsico de programac in l ineal

Para el prximo mes, una empresa desea saber cuntas unidades debeproducir y vender de cada uno de sus dos productos principales (A yB). Los dos bienes se producen en dos fases de proceso (I y II) con lossiguientes coeficientes tcnicos:

Opt Z f x ,x ,x ......,x

g x ,x ,x ......,x b

, n

i , n i

i ......

s.a

= ( )

( )

=

1 2 3

1 2 3

1 2 3, , ,m


17/49

19


Pro duc t o Pro c e s o I Pro c e s o II

A 15 hrs/u 20 hrs/u

B 25 hrs/u 12 hrs/uCap. mx. prx. m es 75 hrs. 60 hrs.

El beneficio unitario estimado por ventas es de US$ 3.000 y US$ 4.000para el bien A y el B, respectivamente.

Plantear matemticamente y resolver grficamente.

Formulacin matemtica:

Sean:

x1= N de unidades/mes a producir y vender de Ax2= N de unidades/mes a producir y vender de B

Resolucin grfica:

En este punto, se recomienda revisar el Apndice N 1, en lo que res-pecta a resolucin grfica de sistemas de inecuaciones lineales.

Max

s.a

Z x x

x x

x x

x ,x

= +

+

+

3000 4000

15 25 75

20 12 60

0

1 2

1 2

1 2

1 2


18/49

20


La FO Max Z= 3000x1+ 4000x2se puede escribir como:

{rectas paralelas con pendiente -3/4 e intercepto 0,00025Z}

R= conjunto convexo de soluciones del sistema de inecuaciones linea-

les conformado por las restricciones (tales soluciones son las solucio-nes realizables o factibles).

Solucin ptima = x*=

Valor Optimo FO = Z*= US$ 13.125

4000 3000

4000 3000 4000

0 00025 0 75

2 1

2 1

2 1

x Z x

x Z x

x Z x

=

=( )( )

=

/ /

, ,

x

x

1

2

1 875

1 875

*

*

,

,

=


19/49

21


Ejem plo bsico de programac in e nte ra

En el Ejemplo anterior, considerar el caso ms realista en que no esposible producir y vender 1,875 unidades de producto, debiendoagregarse la restriccin de que tanto x1como x2deben tener un valorentero.

Resolver grficamente.

Resolucin grfica:

Si se aproxima la solucin (1,875; 1,875) se tiene el punto (2,2), que esun punto no realizable o no factible.

Algunas posibilidades factibles son:

(2,1) Z= US$ 10.000(1,2) Z= US$ 11.000

R ={ }(0,1);(0,2);(0,3);(0,0);(1,1);(1,2);(2,1);(1,0);(2,0);(3,0)


20/49

22


pero puede verificarse que el punto ptimo es:

(0,3) Z= US$ 12.000

Z*= US$ 12.000 Valor ptimo FO

Si bien con el mtodo grfico no se cometera error, s se habra come-tido error aproximando la solucin obtenida sin la restriccin de solu-cin entera, lo cual indica que no basta resolver el PPL en el mbito de

los reales y luego arribar a la solucin ptima entera por aproxima-cin a nmeros enteros.

Ejem plo bsico de programac in n o l ineal

Una empresa monoplica est interesada en optimizar sus resultadoseconmicos en el corto plazo, maximizando su beneficio por perodo.

Esta empresa produce 2 bienes en forma independiente, con las si-guientes funciones de demanda:

p1= 10 - 0,1q1 (q1= 100 - 10p1)p2= 20 - 0,2q2 (q2= 100 - 5p2)

Los coeficientes tcnicos para la produccin de estos 2 bienes, ascomo la capacidad mxima de recursos productivos para el prximoperodo son:

Bie n Man o de Obra Maquin ado

1 5 hrs-hombre/u 1 hr-mq/u

2 1 hr- hombre/u 2 hrs-mq/u

Cap.Mx 200 hrs-hombre 90 hrs- mquina

Se desea conocer la produccin ptima de los bienes 1 y 2 paramaximizar el beneficio del prximo perodo.

x* x

x=

=

1

2

0

3

*

*


21/49

23


Plantear matemticamente y resolver grficamente.

Formulacin matemtica:

Sea x1= q1= N unidades a producir y vender de 1x2= q2= N unidades a producir y vender de 2

Se tendra, entonces:

Agregando las restricciones se tendra:

Resolucin grfica:

La FO es un conjunto de elipses con centro comn en (50 ; 50), ya que:

Max Z p x p x - x x - , x x = + =( ) +( )1 1 2 2 1 1 2 210 0 1 20 0 2,

Z -0,1 - 0,2 75012

2

2= ( ) ( ) +x x50 50

Max

s.a

Z x x x , x

x x

x x

x ,x

= +

+

+

10 0 1 20 0 2

5 200

2 90

0

1 12

2 22

1 2

1 2

1 2

,


22/49

24


Por lo tanto, la solucin ptima es:

3. EL MODELO DE PROGRAMACIN LINEAL

3 .1 ) EL MODELO MAT EMTICO DE PROGRAMACIN L INEAL

Si en el modelo general de Programacin Matemtica, tanto la funcinobjetivo de optimizacin como las m restricciones del problema sonlineales y se agregan n restricciones de no negatividad para las va-riables de decisin, se tiene el modelo matemtico de ProgramacinLineal:

x*

*

*

x

x=

=

1

2

30

30

Z* = 630 Valor Optimo FO


23/49

25


En trminos matriciales, se tiene:

donde:c = [cj]1xn = vector-fila de coeficientes de la FOx = [xj]nx1 = vector-columna de variables de decisinb = [bi]mx1 = vector-columna de capacidades en las restriccionesA = [ai j]mxn = matriz de coeficientes restriccionales

con componentes pertenecientes al campo de los nmeros reales.

Si existiese la condicin de que a lo menos una de las variables debie-ra ser entera, entonces el modelo sera de Programacin Lineal Ente-

ra.Cualquiera discrepancia respecto de la linealidad en la FO y/o en lasm restricciones de problema conducira a un modelo de Programa-cin No Lineal.

Max

s.a.

Z c x c x c x

a x a x a x b a x a x a x b

a x a x a x b

n n

n n

n n

m m mn n m

= + + +

+ + + + + +

+ + +

1 1 2 2

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

LL

KK

KK

M M M M

KK

xx

j , , ,n

j

=

0

12 L

Opt

s.a

Z =

c x

Ax b

x 0


24/49

26


3 .2 ) EJ EMPLOS DE PROBLEMAS DE PROGRAMACIN LI NEAL (PPL )

La Programacin Lineal puede ser aplicada en una amplia gama de

problemas de decisin, aun cuando existe una cierta tendencia aasociarla errneamente slo con problemas de produccin.

En esta seccin se presenta un variado conjunto de situaciones dedecisin, con la finalidad de mostrar algunas de las mltiples aplica-ciones de la Programacin Lineal. Si bien no se presentan situacionesde alta complejidad, la formulacin de estos modelos permite adquiriruna adecuada capacitacin para emprender posteriormenteformulaciones ms complejas, que muchas veces corresponden a com-

binaciones de modelos ms sencillos.

Ejem plo N 1 :(programacin de produccin en un perodo)Para el prximo mes, una empresa manufacturera ha obtenido pedi-dos correspondientes a sus dos principales productos (A y B), ascen-dentes a 200 unidades de A y a 300 unidades de B.

Ambos productos son fabricados en dos fases de operacin, la prime-ra de las cuales es realizada en el Depto. I y la segunda en cualquierade los Deptos. II III. Los tiempos de proceso por unidad de cadaproducto en cada fase y/o Depto. son:

Pro duc t o De pt o . I De pt o . II De pt o . III

A 2 hrs. 4 hrs. 10 hrs.

B 4 hrs. 7 hrs. 12 hrs.

Para el prximo mes, se cuenta con 1.700 hrs. de proceso en Depto. I,con 1.000 hrs. de proceso en Depto. II y con 3.000 hrs. de proceso enDepto. III. En el Depto. II es posible operar en sobretiempo 500 hrs.adicionales.

Los costos unitarios de operacin son de US$ 3, US$ 3 y US$ 2 porhora de proceso dentro de los Deptos. I, II y III, respectivamente, y deUS$ 4,5 por hora de sobretiempo en Depto. II.

Se desea saber cmo producir las unidades requeridas de A y B parael prximo mes, al mnimo costo total de fabricacin. Plantear estasituacin como un PPL.


25/49

27


Desarrollo:

Slo para efectos de formulacin del modelo antes de intentar suresolucin se definirn las variables de la siguiente manera:

xi j = N unids. del bien i a producir en tiempo normal, procesan-do en Deptos. I y j.

yi2 = N unids. del bien i a producir en sobretiempo, procesandoen Deptos. I y II.

donde i= 1, 2 (bienes A y B, en ese orden)j= 2, 3 (Deptos II y III, en ese orden)

Entonces, se tiene el siguiente modelo:

Si los productos tienen caractersticas tales que no resulta posiblefabricar y vender fracciones de unidad de producto, debiera agregarsela restriccin de que cada una de las variables es entera, con lo que setendra en tal caso un modelo de programacin lineal entera.

Cuando se requiera resolver este PPL, se realizar una redefinicinconveniente, de manera que las variables para tal efecto sean, porejemplo, x1, x2, x3, x4, x5, x6.

Ejem plo N 2:(programacin de produccin con restricciones financieras)

Una empresa produce slo 2 bienes (A y B), los cuales requieren pro-cesamiento slo en 3 departamentos (1, 2 y 3), con las siguientes ho-ras de proceso por unidad:

Min

s.a

2

Z x y x x y x

x y x x y x

x x

x x

y

= + + + + +

+ +( ) + + +( ) +

+

18 24 26 33 43 5 36

4 1 700

4 7 1 000

10 12 3 000

4

12 12 13 22 22 23

12 12 13 22 22 23

12 22

13 23

12

,

.

.

.

++

+ + + +

7 500

200300

0

22

12 12 13

22 22 23

12 12 13 22 22 23

y

x y xx y x

x y x x y x , , , , ,


26/49

28


De pt o . 1 De pt o . 2 De pt o . 3

Bien A 3 2 1

Bien B 1 2 3

Se desea programar la produccin del prximo mes, sabindose quese cuenta con un mximo de 800, 750 y 600 horas de proceso en cadadepartamento, respectivamente, y que no existen restricciones ni dedisponibilidad de otros insumos ni de demanda. Se ha estimado pre-cios de $ 500 y de $ 800 para cada unidad a vender de A y B, respec-tivamente, y costos unitarios variables de produccin ascendentes a $200 y $ 350, respectivamente. No hay inventario de estos productos al

comienzo del mes y se cuenta con un saldo inicial de caja (incluyendocuenta bancos) ascendente a $ 800.000, no habiendo deudas de cortoplazo que pagar ni cuentas por cobrar.

Los costos de produccin se pagarn totalmente al final del mes deproduccin, pero los ingresos por ventas se percibirn al final del messiguiente. Es posible conseguir un prstamo bancario hasta por unmximo de $ 150.000, pagadero a un mes plazo, a una tasa de intersde 3% mensual. El Banco exige que durante la vigencia del prstamo,la empresa mantenga un coeficiente de saldo caja / pasivo CP no

inferior a 0,35.Plantear como un PPL de Max la utilidad mensual.

Desarrollo:

Sean: x1 = N de unidades a producir bien A, fondos propios.x1' = N de unidades a producir bien A, con prstamo.x2 = N de unidades a producir bien B, fondos propios.x2' = N de unidades a producir bien B, con prstamo.


27/49

29


Ejem plo N 3 :(programacin de produccin varios perodos)

Una empresa desea programar la produccin y venta de su principalartculo en cada uno de los meses del prximo trimestre, dadas lassiguientes estimaciones y consideraciones:

Me s 1 Me s 2 Me s 3

Dda. Mnima ( por contrato) 80 u 100 u 75 u

Capac. Mx. produccin 130 u 150 u 100 u

Cos to u nitario produc cin 1.500 $ /u 1.800 $ /u 1.600 $ /u

Prec io unitario vent a 2.000 $ /u 2.200 $ /u 2.300 $ /u

El costo unitario mensual de almacenaje de una unidad terminada esde aproximadamente $ 30 y al comenzarse este trimestre no habr uni-dades en proceso ni unidades almacenadas. Las unidades que se ven-

den en el mismo mes de produccin no tienen costo de almacenaje.Plantear un PPL de maximizacin que refleje esta situacin-problema.

Max -

s.a

Z x x - x , x

x x x x x x x x

x x x x

x

= + +( ) +( )

+ + +

+ + +

+ + +

300 450 300 6 450 10 5

3 3 8002 2 2 2 750

3 3 600

200

1 2 1 2

1 1 2 2

1 1 2 2

1 1 2 2

1

' '

' '' '

' '

- -

0

+

+

+( )( )

350 800 000

200 350 150 000

800 000 200 350

200 350 1 030 35

2

1 2

1 2

1 2

1 1 2 2

x

x x

x x

x x

x x x x

.

' ' .

.

' ' ,,

, ', , '


28/49

30


Desarrollo:

Sean xj = N unidades a producir en mes jj= 1, 2, 3.

xj = N unidades que debieran estar en inventario al ini-ciarse el mes j

j= 2, 3, 4

Max Ingreso por ventas - Costo produccin - Costo de almacenaje

s.a

-

Z

. x x ' . x x ' x ' . x x ' x ' . x

. x . x x ' x ' x '

x x '

x

=

= ( ) + + ( ) + + ( )

2 000 2 200 2 300 1500

1800 1600 30 30 30

80

1 2 2 2 3 3 3 4 1

2 3 2 3 4

1 2

22 2 3

3 3 4

1

2

3

100

75

130

150

100

0

+

+

x ' - x '

x x ' -x '

x

x

x

x ,x ' j j

Notas: i) Sera preferible que en la FO se maximizase el beneficiototal trimestral actualizado (lo que implicara aplicar unatasa de descuento).

ii) Otra posibilidad de definicin de variables sera xi j= Nunidades a producir en mes i y a vender en mes j.

iii) Tambin se podra definir variables de produccin y va-riables de venta, eliminando las variables explcitas deinventario.

Ejem plo N 4 :(problema de la dieta)Considrense dos alimentos: A y B. Cada unidad del alimento A con-tiene 20 unidades del nutriente I y 60 unidades del nutriente II. Cadaunidad del alimento B contiene 30 unidades del nutriente I y 23 uni-dades del nutriente II. Se ha determinado que los nios en edad deeducacin bsica deben consumir diariamente por lo menos 350 uni-dades del nutriente I y 700 unidades del nutriente II, cada uno.


29/49

31


Si a cada nio de esa edad, en un rea urbana, se le va a hacer entre-ga de una bolsa que contenga los alimentos A y B, determinar cuntasunidades de A y cuntas unidades de B debiera incluir la bolsa, a un

costo total mnimo y cumpliendo los requerimientos nutricionales. Elcosto de cada unidad de A es $ 25 y el de cada unidad de B es de $ 9.

Plantear como un PPL.

Desarrollo:

Sean x1= N unidades de A que debiera tener c/bolsax2= N unidades de B que debiera tener c/bolsa

Nota: Si se tratase de 1.000 nios y se contase con fondos de 120.000

$ /da, se tendra otra restriccin:

o bien

Ejem plo N 5 :(problema de la mezcla)

Para producir una determinada aleacin metlica que requiere cobre,estao y cinc, se van a mezclar 3 tipos de aleacin de estos 3 metales,disponibles en el mercado: A, B y C.

Cada libra de la aleacin final deseada debe contener a lo menos un20% de cobre, no ms de un 45% de estao y la proporcin de cincdebe ser un 30%. Las caractersticas de las aleaciones A, B y C son:

Mins.a

Z x x

x x

x x

x ,x

= +

+

+

25 9

20 30 350

60 23 700

0

1 2

1 2

1 2

1 2

1000 25 9 120 0001 2. x x .+( )

25 9 1201 2x x+


30/49

32


A B C

% Cobre 30% 10% 70%

% Estao 50% 60% 10%% Cinc 20% 30% 20%

Cos to por l ibra $ 130 $ 110 $ 90

Plantear como un PPL la situacin-problema de determinar los por-centajes de A, B y de C que debe contener 1 libra de aleacin deseada.

Desarrollo:

Sean x1= proporcin de A en 1 libra de aleacinx2= proporcin de B en 1 libra de aleacinx3= proporcin de C en 1 libra de aleacin

Ejem plo N 6 :(problema de transporte)

Una empresa tiene 3 fbricas y 2 tiendas mayoristas. Los datos deproduccin semanal del bien A en cada fbrica, los requerimientos

semanales del bien A en cada tienda y el costo unitario de transportedesde cada fbrica hasta cada tienda son:

Min

s.a

Z x x x

, x , x , x ,

, x , x , x ,

, x , x , x ,

x x x ,

xj

= + +

+ +

+ +

+ + =

+ + =

130 110 90

0 30 010 0 70 0 20

0 50 0 60 010 0 45

0 20 0 30 0 20 0 30100

0

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3


31/49

33


Min

s.a

Z x x x x x x

x x

x x

x x

x x x

x x x

xi j

= + + + + +

+

+

+

+ +

+ +

15 10 8 25 50 34

280

400

350

500

300

0

11 21 31 12 22 32

11 12

21 22

31 32

11 21 31

12 22 32

Notas: i) La forma general de este problema es cmo y cuntasunidades de c/bien deben llevarse desde un conjunto deorgenes (por ej.: fbricas) hasta un conjunto de destinos

(por ej.: tiendas mayoristas), minimizando el costo totalde transporte?

ii) Si se trata de asignar n elementos o recursos a un con-junto de n destinos, de tal forma que cada elemento seasocie con uno y slo uno de los destinos y viceversa (porejemplo, asignar trabajadores a mquinas vendedoresa territorios de ventas), se tiene un caso especial de pro-

blema de transporte llamado problema de asignacin.

Fbrica

1 2 3 Dda. Mn im a

Tienda 1 15 $/u 10 $/u 8 $/u 500 uTienda 2 25 50 34 300 u

Produccin 280 u 400 u 350 u

Plantear como un PPL, para minimizar el costo total semanal de trans-porte.

Desarrollo:

Sean xi j= N unidades a transportar desde fbrica i hasta tienda ji= 1, 2, 3 j= 1, 2


32/49

34


Ejem plo N 7 :(problema del recorte)

Una empresa manufacturera de papeles debe surtir un pedido consis-tente en 800 rollos de papel de 30 cms. de ancho, 500 rollos de papelde 45 cms. de ancho y 1.000 rollos de papel de 56 cms. de ancho. Eneste momento, la empresa cuenta solamente con rollos de 108 cms. deancho y debe decidir cmo cortarlos para surtir el pedido con un mni-mo desperdicio de papel.

Desarrollo:

Sea xj = N de rollos de 108 cms. que se cortan en la modalidad j.j= 1,2,3,4,5.

MODALIDAD DE CORTE

1 2 3 4 5

R o llo s de 3 0 c m s . 3 2 1 0 0

R o llo s de 4 5 c m s . 0 1 0 2 1

R o llo s de 5 6 c m s . 0 0 1 0 1

Prdida por recorte (cms) 18 3 22 18 7

Min

s.a

Z x x x x x

x x x

x x x

x x

xj

= + + + +

+ +

+ +

+

18 3 22 18 7

3 2 3 800

2 500

1 000

0

1 2 3 4 5

1 2 3

2 4 5

3 5 .

Ejem plo N 8 :(problema de seleccin de portfolio)

La corporacin Gamma quiere invertir la suma de US$ 1.000.000 enel prximo ao fiscal.

Para tomar una decisin acertada, los ejecutivos de la mencionadaorganizacin han pedido una completa investigacin de los ndices derentabilidad promedio, en los ltimos aos, para las distintas catego-


33/49

35


ras de valores de inversin. La informacin relevante, proveniente deun estudio de portfolio, es la siguiente:

CATEGORA DE LA INVERSIN RETORNO REAL FACTOR DEESPERADO ANUAL RIESGO ()

Acciones Comunes 15% 1,6

Cuotas de fondos m utuos 12% 1,0

Debentures 10% 0,5

Bonos de Gobierno 5% 0

Cuen tas de ah orro 8% 0,1

La poltica de inversin que ha seguido Gamma en los ltimos aos esbastante clara: la inversin en acciones y en cuotas de fondos mutuosno debe ser mayor que un 30% del total de las inversiones; la inver-sin en Bonos de Gobierno no debe ser inferior a la inversin en cuen-tas de ahorro; la inversin en debentures y bonos de Gobierno no debeexceder el 50% del total de las inversiones; adems, por ley, la inver-sin en bonos gubernamentales debe superar el 25% del total de lasinversiones.

En cuanto a riesgo, la corporacin no permite que el portfolio de valo-

res escogidos tenga un factor de riesgo ponderado mayor que 1,0.Si se puede suponer que los retornos reales esperados y los factoresde riesgo permanecen constantes para el horizonte de planeacin delproblema, entonces plantear un modelo de programacin lineal quepermita obtener el portfolio de inversin que optimice el retorno espe-rado de la corporacin y simultneamente no viole su poltica de in-

versin.

Desarrollo:

Sea xj= US$ a invertir en alternativa j.j= 1,2,3,4,5.


34/49

36


Slo restara ordenar, para presentarlo en formato general de PPL.

Ejem plo N 9 :(problema de seleccin de medios)

La empresa XAB cuenta con M$ 30.000 para realizar publicidad alproducto Q durante el prximo semestre. Los medios de publicidadconsiderados son: TV, radio, diarios y revistas. El objetivo es maximizarla exposicin publicitaria del producto Q durante el semestre (es de-cir, el n de veces que una persona promedio en el mercado objetivo

estara expuesta al mensaje publicitario).Se cuenta con estimaciones de la exposicin media por cada M$ 1desembolsado en publicidad en cada medio y se ha decidido respectoa las cantidades mximas a desembolsar en cada medio.

Me dio Expo s ic i n De s e m bo ls oPublic it ario po r c ada M$ 1 Mxim o

TV 9 M$ 18.000

Radios 5 5.000

Diarios 6 9.000

Revis tas 4 10.000

Adems, se ha especificado que el desembolso en publicidad televisivano debe ser superior al desembolso conjunto en los restantes medios.

Max

s.a

Z x x x x x

x x x x x x x

x x

x x x x x x x

x

= + + + +

+ + + + +( )

+ + + + +( )

0 15 0 12 0 10 0 05 0 08

0 3

0 5

1 2 3 4 5

1 2 1 2 3 4 5

4 5

3 4 1 2 3 4 5

4

, , , , ,

,

,

> + + + +( )+ + + + + + +

+ + + +

0 25

1 6 0 5 0 1

1 000 000

0

1 2 3 4 5

1 2 3 4 1 2 3 4 5

1 2 3 4 5

,

, , ,

. .

x x x x x

x x x x x x x x x

x x x x x

xj


35/49

37


Desarrollo:

Sea xj = M$ a desembolsar en publicidad del producto Q, en me-dio j, en el semestre.

j= 1,2,3,4

Max

s.a

10.000

Z x x x x

x

x

x

x

x x x x

x x x x

xj

= + + +

+ + +

+ + +

9 5 6 4

18 000

5 000

9 000

30 000

0

0

1 2 3 4

1

2

3

4

1 2 3 4

1 2 3 4

.

.

.

.

Ejemplo N 10:(problema de inversiones)

Un inversionista tiene las actividades A y B que producen dinero, dis-ponibles al principio de cada uno de los cinco aos siguientes (lla-mmoslos aos 1 al 5). Cada peso invertido en A al principio del ao 1,retribuye $ 1,40 (una utilidad de $ 0,40) dos aos ms tarde (en elinstante necesario para la reinversin inmediata). Cada peso invertidoen B al principio del ao 1, retribuye $ 1,70 tres aos ms tarde.

Adems, en un instante futuro, estarn disponibles cada una de lasactividades C y D. Cada peso invertido en C al principio del ao 2,retribuye $ 1,90 al final del ao 5. Cada peso invertido en D al princi-

pio del ao 5, retribuye $ 1,30 al final del ao 5.El inversionista empieza con $ 20.000. Desea saber cul plan de in-

versiones maximiza la cantidad de dinero que puede acumular al prin-cipio del ao 6. Plantese un modelo de programacin lineal para esteproblema.


36/49

38


Desarrollo:

A o 1 A o 2 A o 3 A o 4 A o 5

0 1 2 3 4 5

A 0 A 1 A 2 A 3

B0 B1 B2

C1 D4

N0 N1 N2 N3 N4

Donde Nj = $ no invertidos al principio del ao jj= 0,1,2,3

Se desea maximizar la cantidad de dinero acumulado al momento 5(comienzo ao 6).

Max

s.a

Z C B A D

A B N

A B C N N

A B N A N

A N A B N

D

= + + +

+ + =

+ + + =

+ + = +

+ = + +

1 9 1 7 1 4 1 3

20 000

1 41 4 1 7

1 2 3 4

0 0 0

1 1 1 1 0

2 2 2 0 1

3 3 1 0 2

, , , ,

.

,, ,

44 2 1 3

1

4

1 4 1 7

0 0 1 2 3

0 0 1 2

0

0

0 0 1 2 3

= + +

=

=

=

, ,

, , ,

, ,

, , ,

A B N

A j

B j

C

D

N j

j

j

j


37/49

39


Ejem plo N 11 :(problema de distribucin de carga)

Una Ca. naviera posee una dotacin de 3 barcos para el transporte decarga general. Cada uno de estos barcos posee 3 bodegas: una en laproa, otra en el centro y la ltima en la popa. Los lmites de capacidadde estas bodegas son los siguientes:

Bo de ga Pe s o (t o n s ) Vo lum e n (m 3)

Proa 2.000 100.000

Centro 3.000 135.000

Popa 1.500 30.000

Las siguientes cargas estn disponibles, pudiendo aceptarse la totali-dad o parte de ellas, contndose con slo uno de los barcos para ello:

Art c u lo Can t idad Vo lum e n Ut ilidad(t o n s ) (m 3/ t o n ) ($ / t o n )

A 6.000 60 12

B 4.000 50 16

C 2.000 25 10

Para mantener la lnea de flotacin del barco, el peso en cada bodegadebe ser proporcional a su capacidad en toneladas. El problema escmo distribuir la carga en el barco para obtener el mximo de utili-dad total. Plantear como PPL.

Desarrollo:

Sea xi j= toneladas carga i a almacenar en bodega j.

i = 1 carga A j = 1 Proa

2 carga B 2 Centro3 carga C 3 Popa

Max Z x x x j

j

j

j

j

j

= + +

= = =

12 16 1011

3

21

3

31

3

s.a. las siguientes restricciones:


38/49

40


CARGA DISPONIBLE

1)

2)3)

CAPACIDAD EN PESO

4)

5)

6)

CAPACIDAD EN ESPACIO O VOLUMEN

7)

8)

9)

LINEA DE FLOTACION (una de ellas es redundante)

10)

11)

12)

13)

Nota: Las restricciones 10), 11) y 12) han sido expresadas en laforma convencional.

Ejemplo N 12:(problema de arrendamiento)

Una compaa necesita arrendar espacio de almacenamiento durantelos prximos 5 meses. La compaa sabe con precisin cunto espaciorequerir en cada uno de estos meses. Sin embargo, como estos re-

x

.

.

.

i

ii

i j

j

=

=

=

=1

36 000

4 0002000

1

23

x

.

.

.

j

j

j

i j

i

=

=

=

=1

32 000

3 000

1500

1

2

3

60 50 25

100 000

135 000

30 000

1

2

31 2 3x x x

.

.

.

j

j

j

j j j+ +

=

=

=

3 000 2 000 01 21

3

1

3

. x . x i iii

===

1500 2 000 01 31

3

1

3

. x . x i i

ii

===

1500 3 000 02 31

3

1

3

. x . x i i

ii

===

x i , , j , ,

i j0 = =12 3 12 3


39/49

41


querimientos de espacio son bastante diferentes, es posible que resul-te ms econmico arrendar nicamente la cantidad necesaria cadames, sobre una base de mes a mes. Por otra parte, el costo adicional

por espacio arrendado para meses adicionales es mucho menor quepara el primer mes, de modo que puede ser menos caro arrendar lacantidad mxima necesaria para los 5 meses completos. Otra opcines el punto de vista intermedio de cambiar la cantidad total de espacioarrendado (agregando un nuevo arriendo y teniendo un vencimientode arriendo anterior, o bien, con el vencimiento de un arriendo ante-rior) al menos una vez, pero no en todos los meses.

El requerimiento de espacio (en miles de pies cuadrados) y los costosde arrendamiento (en cientos de dlares) para los diversos perodos de

arrendamiento son:

Me s Es pac io Re que rido Pe ro do de Co s t oArre ndam ie nt o ($ / 1 .0 0 0 pie s 2)

1 30 Mpies2 1 mes 450

2 20 2 700

3 40 3 950

4 10 4 1.150

5 50 5 1.300

Desarrollo:

Sea xi j = espacio a arrendar (miles pies2) en mes i por un pero-

do de j meses.

i , , , , j , , , , j -i = = +( )12 3 4 5 12 3 4 5 5 1

Min Z

950 1.150s.a

= + + + +( ) + + + +( )+ + +

( ) + +

( ) +

+ + + +

+ + + + + + +

450 700

1300

30

11 21 31 41 51 12 22 32 42

13 23 33 14 24 15

11 12 13 14 15

12 13 14 15 21 22 23 24

x x x x x x x x x

x x x x x . x

x x x x x

x x x x x x x x

+ + + + + + + +

+ + + + + + +

+ + + +

20

40

10

50

13 14 15 22 23 24 31 32 33

14 15 23 24 32 33 41 42

15 24 33 42 51

x x x x x x x x x

x x x x x x x x

x x x x x

xi j

0


40/49

42


3 .3 ) SUPUESTOS DEL MODELO DE PROGRAMACIN LI NEAL

Sea el siguiente problema de programacin lineal (PPL):

En general, este PPL podra representar una situacin tpica de pro-duccin y venta de n bienes, con m restricciones correspondientesa disponibilidad mxima de m insumos, con una funcin objetivo deMax beneficios (donde los cjson las contribuciones unitarias al bene-ficio por parte de los respectivos bienes).

Entonces, los supuestos fundamentales de este modelo son:

a) Linealidadb) Divisibilidadc) Certidumbre

a) Linealidad

Evidentemente, ste es el supuesto fundamental del modelo, el cualinvolucra 2 supuestos subyacentes: proporcionalidad en cada activi-dad individual e independencia entre actividades.

a.1) Proporcionalidad en cada actividad individual

En cada actividad (produccin de cada bien) debe cumplirse que:

- Si para producir una unidad del bien j se requiere de ai junidades de insumo i, entonces para producir xjunidadesdel bien j se requiere de ai jxjunidades de insumo i.

- Si el beneficio asociado a la venta de una unidad del bien jes cj, entonces el beneficio total asociado a la venta de xjuni-dades del bien j es cjxj.

Max

s.a

Z c x c x c x

a x a x a x b

a x a x a x b

a x a x a x b

x

n n

n n

n n

m m mn n m

j

= + + +

+ + +

+ + +

+ + +

1 1 2 2

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

0

LL

LL

LL

M M M M

LL


41/49

43


Si bien lo anterior parece a primera vista muy lgico, no siempreello se cumple en casos reales para todo nivel de actividad, debi-do a problemas de inversin inicial y a la existencia de rendi-

mientos a escala.El problema de inversin inicial se refiere al hecho de que parainiciar la produccin de un artculo nuevo, puede que se requie-ra efectuar una inversin inicial. Si Kes el costo de esa inver-sin inicial, se tendr que para xj> 0 el beneficio de la venta dexjunidades ser igual a (cjxj-K), pero si xj= 0 se tendr un bene-ficio igual a 0, siendo el bien j aquel para el cual se requiere talinversin inicial.Los rendimientos a escala se refieren al hecho de que tanto los

beneficios unitarios como los costos unitarios de tipo variablepueden estar asociados con el nivel de produccin o de venta(nivel de actividad). Puede haber rendimientos crecientes o ren-dimientos decrecientes, segn la escala de actividad.

a.2) Independencia entre actividades individuales

No existen interacciones entre actividades, de tal forma que lautilizacin total de cada insumo y los ingresos totales, costostotales o utilidades totales son la suma de los correspondientesa cada actividad (suma de los ai jxj suma de los cjxj). En snte-

sis, ello significa que no se gana ni se pierde nada adicional porla fabricacin o la venta simultnea de dos o ms productos.Esto no siempre se cumple en situaciones reales, porque existencasos en que se producen ahorros (desahorros) de insumos alutilizar procesos comunes de produccin o se ven afectadas lasutilidades en el caso de productos sustitutos o competidores.

Si el supuesto de linealidad falla, debiera considerarse el uso deProgramacin No Lineal; no obstante, en muchos casos podrasumirse linealidad para los niveles de actividad relevantes y, en

otros casos, existir la posibilidad de replantear el problema enuna forma adecuada para que se cumpla este supuesto. Al respec-to, debe acotarse que los algoritmos de resolucin en ProgramacinLineal son mucho ms poderosos que en Programacin No Lineal.

b) Divisibilidad

Es posible fabricar o vender una fraccin de unidad de producto.


42/49

44


En caso contrario se debiera considerar el uso de ProgramacinLineal Entera. Al respecto, cabe recordar que el simple redondeo deuna solucin fraccionaria al entero ms prximo, puede arrojar una

solucin infactible con los insumos de que se dispone, o bien, unasolucin bastante alejada de la verdadera solucin ptima entera.

c) Certidumbre

Los valores de los parmetros del modelo son conocidos, es decir,se conocen los valores de ai j, cj, bi.

En realidad, los valores de ai j, cj, bique se utilizan al formular elPPL son slo estimaciones. Sin embargo, el anlisis de sensibilidado post-optimal permite conocer el comportamiento de la solucinptima, ante variaciones en los valores de esos parmetros.

4. EJERCICIOS PROPUESTOS

Ejercic io N 1:

La empresa Shogun S.A. est fundamentalmente dedicada a la pro-duccin de lentes para mquinas fotogrficas, luego de que intentaseinfructuosamente entrar en el mercado de las mquinas fotogrficas

de alta sofisticacin tcnica.Aprovechando la experiencia de la empresa en el rubro, ha decididoespecializarse en lentes de alta calidad, que le permitan estar entrelos principales exportadores japoneses de lentes para mquinas deltipo reflex.

En la actualidad, fabrica tres modelos distintos:

- el modelo KIKU, zoom de 100 - 200 mm. con f. 5,6- el modelo OMI, zoom de 35 - 105 mm. con f. 3,5

- el modelo ANGIN, zoom de 100 - 300 mm. con f. 5,6En su produccin, la empresa utiliza dos tipos de insumos (A y B), delos cuales dispone de 4.000 y 6.000 unidades respectivamente.


43/49

45


Los requerimientos unitarios de insumos son:

INSUMO KIKU OMI ANGIN

A 2 3 5

B 4 2 7

El tiempo destinado a producir cada unidad del modelo KIKU es eldoble del destinado al modelo OMI, y el triple del dedicado al modelo

ANGIN. Los operarios de la empresa pueden llegar a producir un equi-valente a 1.500 lentes KIKU mensualmente.

El departamento de Marketing ha realizado algunas proyecciones de

las ventas futuras, y ha indicado que la demanda mnima para los tresmodelos es de 200, 200 y 150 unidades mensualmente, respectiva-mente.

Los precios de cada modelo y sus costos unitarios, expresados en d-lares, son los siguientes:

MODELO PRECIO VENTA COSTO PRODUCCIN

KIKU US$ 120 US$ 90

OMI 100 80

ANGIN 130 80

Formular un modelo de programacin lineal que permita determinarla produccin de cada tipo de zoom, tal que se optimice el resultadooperacional de la empresa.

Ejercic io N 2:

Una embotelladora debe decidir cunto producir de cada uno de suscuatro productos en el prximo mes. Los productos en cuestin son

bebidas de fantasa (Koka-Kola, Fhanta, Eight Up y Zprite), para lascuales el departamento de Comercializacin ha realizado estimacio-nes de precio y de cantidad demandada mxima mensual, para elprximo mes:


44/49

46


Marc a Can t idad De m an dada Pre c io de ve n t a

Koka-Kola Sin lmite $ 50,5

Fhanta 80.000 botellas 51,5

Zprite 60.000 botellas 50,0

Eight Up 72.000 botellas 52,4

La Koka-Kola requiere por cada botella 3 minutos de proceso, la Fhantarequiere 2,5 minutos, la Eight Up y la Zprite requieren 3,8 minutoscada una.

La mquina selladora enva 14 botellas de Kola-Kola cada 2 horas, 12botellas de Fhanta cada hora, 27 botellas de Zprite cada 3 horas y 30

botellas de Eight Up cada 3 horas.Se contratan 1.500 horas de reparto y se sabe que en 1 hora dereparto se logra colocar 300 botellas de Koka-Kola, 200 de Fhanta, 180 de Zprite 200 de Eight Up.

Las horas disponibles de proceso mensual son 500 horas y las horasdisponibles de sellado son 2.000 horas mensuales. Los costos porhora son:

Costo por hora proceso $ 52

Costo por hora sellado $ 47Costo por hora reparto $ 55

Al comienzo del prximo mes no habr unidades en inventario de pro-ductos en proceso y productos terminados. No obstante, en conside-racin a nuevas polticas de la empresa, se desea terminar el prximomes con 500 botellas de Koka-Kola, 400 de Fhanta, 200 de Zprite y350 de Eight Up procesadas y selladas. Adems, durante el mes encuestin se debe cumplir con la entrega de 1.200 botellas de Koka-Kola, 600 de Zprite y 450 de Eight Up, las que corresponden a ventas

del mes anterior, ya pagadas al contado.No hay restriccin de fondos, realizndose todos los pagos en el mesde produccin con fondos propios y vendindose todo al contado.

Plantear un PPL relacionado con la situacin-problema de programarla produccin de cada producto para el prximo mes. Especifique cla-ramente sus supuestos (de ser ellos necesarios).


45/49

47


Ejercic io N 3:

El Royal Club de Mnaco ofrecer un almuerzo de gala en cada uno delos siete das de la Semana de la Primavera. Las reservas de mesas yahan sido realizadas, sabindose el nmero de mesas que seran ocu-padas en cada da.

Lun e s Mart e s Mi rc o le s J ue ve s Vie rn e s Sbado Do m in go

75 90 105 120 105 135 150

En esta oportunidad, habr que adquirir manteles nuevos, ya quecada mesa lucir un mantel especialmente diseado para estas cele-

braciones.Cualquier compra de un mantel nuevo puede ser realizada el mismoda en que ser usado, a un precio de $ 1.900 cada uno, pagaderos alcontado. Adems, los manteles sucios pueden ser mandados a lavar aun servicio rpido que demora dos das la entrega y cobra $ 800 pormantel, pagaderos al momento del envo a lavado, o bien, pueden sermandados a lavar a un servicio ms lento que demora 3 das la entre-ga y cobra $ 500 por mantel, pagaderos al momento del envo a lava-do.

En el contexto de la semana de inters, la administracin del Clubdesea saber -formulando y resolviendo un PPL- cuntos manteles debeadquirir en cada da y cuntos debe enviar a lavar por cada tipo deservicio en cada da, minimizando el costo total asociado a la adquisi-cin y lavado de manteles de la semana en cuestin.

Puesto que la administracin del Club sabe que el dinero tiene unvalor asociado a la variable tiempo, aun cuando no incluir explci-tamente este aspecto en la formulacin del PPL, intentar adquirir y/o lavar cada da la mnima cantidad posible de manteles para cumplir

lo requerido.

Formular el PPL, siendo muy preciso en la definicin de las variables yen la formulacin de la FO y de las restricciones.


46/49

48


Ejercic io N 4:

Contestar las siguientes preguntas, definiendo claramente las varia-bles en cada caso.

4.1) En un determinado departamento fabril se realiza una operacinde manufactura requerida por cada uno de los tres principales pro-ductos (A, B, C) de la Ca. JVC. Se sabe que si en el prximo mes sededicase la totalidad de la capacidad de este departamento a la fabri-cacin de slo uno de estos productos, podra procesarse completa-mente 3.000 unidades de A 2.500 unidades de B 1.500 unidadesde C en tal departamento. No obstante, lo habitual es que se procesenunidades de los tres productos.

Formular, entonces, la restriccin de capacidad mensual de procesoen este departamento para los tres productos sealados.

4.2) Sean tres parcelas (A, B, C) similares en productividad, con reasutilizables de 50, 32 y 85 hectreas, respectivamente. Se desea sabercuntas hectreas plantar en cada parcela, de cada uno de tres culti-

vos posibles, dado un determinado conjunto de restricciones. Una detales restricciones indica que el % de rea cultivable aprovechada debeser el mismo en cada parcela.

Formular la restriccin sealada.

4.3) Sean dos proyectos de inversin no divisibles, de tal forma querespecto de cada uno de ellos slo cabe la aceptacin total o el rechazototal. Formular la restriccin segn la cual ambos proyectos son mu-tuamente excluyentes y que necesariamente debe realizarse unode ellos.

4.4) Se cuenta con $ 1.300.000 disponibles para invertir entre 9 alter-nativas financieras divisibles (por ejemplo, acciones de S.A., bonos,etc.). Se ha estimado para cada alternativa, la tasa de rentabilidad

anual por cada $ que se invierta en ella, de tal forma que rjsera larentabilidad anual estimada para la alternativa j.

Las polticas de inversin son:

- invertir como mximo $ 300.000 en cada alternativa.- si se decide invertir en una determinada alternativa, entonces se

debe invertir por lo menos $ 100.000 en ella.


47/49

49


Plantear un modelo matemtico que refleje la situacin-problema se-alada, dado un objetivo de Max la ganancia total anual en $.

Ejercic io N 5:Una empresa debe decidir un programa de produccin en un horizon-te de planificacin de 3 perodos. Los costos de produccin, que debenpagarse en efectivo al trmino del perodo en que se haya incurrido enellos, ascienden a M$ 25 por unidad en cada perodo.

La empresa fabrica un solo producto, del cual es posible producir 25,25 y 30 unidades, en los perodos 1, 2 y 3, respectivamente. Al trmi-no del perodo en que la produccin pasa almacenada, se debe pagarcostos de almacenaje por un monto de M$ 3 la unidad.

La capacidad de venta es de 20 unidades en el perodo 1, de 15 unida-des en el perodo 2 y de 20 unidades en el perodo 3. El precio de ventapor unidad es de M$ 29, M$ 30 y M$ 31, para los perodos 1, 2 y 3,respectivamente.

La cobranza de las ventas se efecta un perodo despus del perodoen que se realiza la venta y este efectivo se encuentra disponible paradesembolsos en costos de produccin en el perodo de cobranza.

El saldo de caja inicial es de M$ 400. Sin embargo, es posible tomarun prstamo hasta M$ 200 al trmino de cada uno de los 2 primerosperodos, al 6% de inters simple por perodo, a condicin de que semantenga M$ 1 en el saldo de caja por cada M$ 3 que se toman enprstamo. Estos prstamos son de duracin de un perodo solamente,no pudiendo adeudarse cantidad alguna ms all del tercer perodo.

Plantear como un PPL la situacin-problema de programar la produc-cin y venta para cada uno de los 3 perodos.

Ejercic io N 6:

Se va a evaluar una cartera de n proyectos de inversin con la mis-ma vida til, de tal forma que se desea determinar en cules proyectosinvertir y/o cunto invertir en cada uno de ellos, con la finalidad demaximizar una determinada funcin de beneficio econmico, en unasituacin de limitacin de fondos.

Sea, en general, xj= fraccin o proporcin a aceptar (o realizar) delproyecto j.


48/49

50


6.1) Suponiendo que en esta cartera los proyectos 4 y 7 (j=4 yj=7) sonperfectamente divisibles, tales que se puede decidir invertir en el pro-

yecto completo o en una fraccin de l (por ejemplo: acciones, bonos).

a) Formular las restricciones matemticas bsicas para cada una delas variables x4y x7.

b) Alguien sugiere que si adems los proyectos 4 y 7 son mutuamenteexcluyentes, debiera formularse las siguientes restricciones, en reem-plazo de las restricciones de a):

Analizar esta sugerencia.

6.2) Suponiendo que todos los dems proyectos en cartera no sondivisibles, de tal forma que respecto de c/u de ellos slo cabe la acep-tacin o el rechazo, determinar cul de las restricciones que se listana continuacin corresponde a c/u de los siguientes casos:

a) Los proyectos 1 y 2 son mutuamente excluyentes.

b) La aceptacin del proyecto 2 depende de la aceptacin previa delproyecto 1.

Explicar claramente, desde la definicin bsica de las variables.

6.3) Supngase que ninguno de los n proyectos en cartera es divisi-ble, habindose determinado para c/u de ellos el Valor Actual Neto(VAN).

Se va a plantear un modelo de programacin matemtica, con unafuncin objetivo consistente en maximizar el VAN de la inversin total.

0 1

0

0

4 7

4

7

x x

x

x

+

x x

x x

x x

1 2

1 2

1 2

1

0

0

+

+ =

+

x x

x x

x x

1 2

1 2

1 2

0

1

1

=

+ =

+

Documents

Programacion Lineal Para Administracion