cap1 - programacion lineal

7/24/2019 Cap1 - Programacion Lineal

1/42

1
mailto:[email protected]


2/42

2

Profesor: Carlos Alcayaga Pizarro

E-mail: [email protected]

Clases: Lunes 16:15 17:45 rs. !"ala #6$

%ar&es ':55 11:#5 rs. !"ala (($


3/42

3

)ormas *en&ro *e la sala *e clases: Celular en silencio o a+aga*o )o ca&ear en clases

)o comer en clases Pun&uali*a* Asis&encia )o se *e,e consi*erar las clases

e+osi&ias y &ra,a/os como el 0nicoma&erial gua.


4/42

4

Consi*eraciones: 2 +rue,as 3areas acumula&ias en clases

Eamen final )o&a mnima *e +resen&acin a eamen

2.4 Porcen&a/e mnimo *e asis&encia 75. 3e&o gua *e referencia: illier

Lie,erman


5/42

5

Tres Controles de ctedra. Promedio Final: 0,27*C1 +0,07*NC1 + 0,27*C2 + 0,07*NC2 + 0,25*C3 + 0,07*NC3

Promedio Final ! " # todos Ci!"$%ro&ado

Promedio Final '! 3,3(e%ro&ado

Promedio Final entre 3," # 3,), amen

Promedio Final !" # al-n Ci'!3,) amen

s%ecial


6/42

6

Nota de Controles

Pre&as Cortas # Tareas

/ea PP actiidad de atoa%rendia4e, ino o CPle

Pa%er 6nterace

Pro%esta de /odelamiento Pre&a de Ctedra


7/427

Fec8as de Pre&as de Ctedra

9&ado 2 de 9e%tiem&re 1era Pre&a

9&ado 31 de ;ct&re 2da Pre&a

9&ado 2< de Noiem&re 3ra Pre&aFec8as de ntreas /ea PP

/artes de ;ct&re Planteamiento 6nicial 10=

/artes 3 de Noiem&re /odelo /atemtico # ennciado

deinitio 20=nes 23 de Noiem&re ntrea de c>dio C%le o ino

30=

?iernes " de @iciem&re 10:008rs 6norme Final "0=


8/428

Fec8as de Pa%er 6nterace?iernes 23 de ;ct&re lecci>n tema Pa%er

?iernes 20 de Noiem&re ntrea PPT # ;riinal

6m%reso

$ %artir del 7 de @iciem&re %osiciones

/odelamiento Pre&a de Ctedra

?iernes 13 de Noiem&re Primera entrea ennciado #

solci>n

1 al 20 de Noiem&re ncentros indiidales con

$#dantes # Proesor

?iernes 1< de @iciem&re Presentaciones PPT


9/429

Ta&la de ce%ciones %or re%itencia:

PruebasCortas yTareas

Mega PPL Paper Modelamiento

1raOportunidad XX XX XX XX

2daOportunidad XX XX XX

3raOportunidad XX


10/4210

Programa: Programacin Lineal

3eora *e la *uali*a* y an8lisis *esensi,ili*a* %o*elos *e 3rans+or&e y Asignacin 9+&imizacin *e e*es Programacin en&era


11/4211


12/4212

Las condiciones que debe cumplir son: Las variables de decisinson no nega&ias.

El cri&erio o Funcin b!e"ivo u&iliza*o +araencon&rar los me/ores alores *e las aria,les*e *ecisin se +ue*e *escri,ir como unafuncin lineal *e ;s&as.

Las reglas *e o+eracin *el +roceso +ue*en

ser *escri&as como un se& *e ecuaciones o*esigual*a*es lineales conoci*as comores"ricciones.


13/42

13

1.


14/42

14

La Com+a>a an*y-?an*y *esea +rogramar su +ro*uccin*e cocinas. Para es&o se u&ilizan *os recursos: %ano *e o,ra yma&erial. La com+a>a consi*era &res *iferen&es mo*elos y su*e+ar&amen&o *e +ro*uccin a recolec&a*o la siguien&einformacin:

El suminis&ro *e ma&erial es&8 res&ringi*o a # l,s*a. La*is+oni,ili*a* *iaria *e mano *e o,ra es 15 rs. Bormular unmo*elo *e Programacin Lineal +ara *e&erminar la &asa *iaria*e +ro*uccin *e ca*a mo*elo *e forma *e maimizar las

u&ili*a*es.


15/42

15

%olucin:

&aso 1: aria,les *e ?ecisin:XA: Pro*uccin *iaria *e A

XB: Pro*uccin *iaria *e D

XC: Pro*uccin *iaria *e C

&aso 2:


16/42

16

As el mo*elo *e +rogramacin lineal se conier&e

en: Encon&rar los n0meros XA , XB , XC =uemaimicen la funcin:

CBA XXXZ 324 ++=

A/us&8n*ose a las res&ricciones:7 3 6 150

4 4 5 200

, , 0

A B C

A B C

A B C

X X X

X X X

X X X

+ +

+ +

&aso 3:


17/42

17

na com+a>a *en&ro *el ru,ro *e ma=uinaria +esa*a

con*uce un +rograma *e ca+aci&acin +ara sus o+era*ores.9+era*ores en&rena*os son u&iliza*os como +rofesores en el

+rograma a razn *e 1 +or ca*a 1 o+era*ores enen&renamien&o !a+ren*ices$. El +rograma *e en&renamien&o

*ura 1 mes. Por e+eriencia se sa,e =ue slo 7 *e 1o+era*ores a+rue,an el curso *e forma ei&osa.

La com+a>a +resen&a re=uerimien&os *e ma=uinis&asen&rena*os +ara los siguien&es &res meses. Fs&os son:


18/42

18

A*em8s la com+a>a re=uiere #5 o+era*oresen&rena*os en a,ril. Al comienzo *el a>o ay 12ma=uinis&as en&rena*os *is+oni,les. Los salariosmensuales son:

Operador en Entrenamiento $400Operador Entrenado $700

Operador Entrenado Ocioso $500

Bormule el PPL =ue +ro*uzca el cos&o mnimo *econ&ra&acin ca+aci&acin y cum+la con losre=uerimien&os *e la com+a>a.


19/42

19

%olucin:

Los o+erarios en&rena*os ca*a mes +ue*en realizar 2ac&ii*a*es: &ra,a/ar en una m8=uina ense>ar +ermanecerocioso. Como el n0mero *e o+erarios en m8=uinas es fi/o yconoci*o en&onces las aria,les *e *ecisin son lassiguien&es.

X1 :9+erarios en&rena*os ense>an*o en enero

X2:9+erarios en&rena*os ociosos en enero

X3:9+erarios en&rena*os ense>an*o en fe,rero

X4:9+erarios en&rena*os ociosos en fe,rero

X5:9+erarios en&rena*os ense>an*o en marzo

X6:9+erarios en&rena*os ociosos en marzo


20/42

20

Para ca*a mes se cum+le =ue:

9+erarios en %8=uinas G 9+erarios Ense>an*o G 9+erarios9ciosos H 3o&al *e 9+erarios En&rena*os *is+oni,les al inicio

*el mes

As +ara enero: 130100 21 =++ XXBe,rero:

%arzo:

143 7130150 XXX +=++

3165 77130200 XXXX ++=++

I como la com+a>a necesi&a #5 o+erarios en&rena*osen A,ril:

250777130531

=+++ XXX


21/42

21

Los cos&os relean&es =ue*an re+resen&a*os en la B9

como sigue:1 3 5 1 3 5 2 4 6400(10 10 10 ) 700( ) 500( )Min Z X X X X X X X X X= + + + + + + + +

As el PPL se re*uce a:

1 2 3 4 5 64700 500 4700 500 4700 500Min Z X X X X X X= + + + + +

Sujeto a:

1 2

1 3 4

1 3 5 6

1 3 3

30

7 207 7 70

7 7 7 120

X X

X X XX X X X

X X X

+ =

=+ =

+ + =

1 2 3 4 5 6, , , , , 0X X X X X X


22/42


23/42

23

La com+a>a no *esea gas&ar m8s *e JK.+ero re=uiere =ue:

1. Al menos # millones *e mu/eres *e,en er leer uor el comercial.

#. EL gas&o en 3 es&8 limi&a*o a J5. comom8imo.

2. Al menos se *e,en mos&rar &res comerciales +or3 en orario *iurno y *os en orario es&elar.

4. El n0mero *e comerciales en ra*io y reis&as *e,ees&ar en&re 5 y 1.


24/42

24

%olucin:

"eanX1X2X3yX4el n0mero *e uni*a*es *e aisoscomerciales com+ra*os en 3 *iurna 3 es&elarra*io y reis&as res+ec&iamen&e. En&onces:

La can&i*a* *e +o&enciales consumi*oresalcanza*os !en miles$ es:

400X1+ 900X2+ 500X3+200X4

La res&riccin so,re la com+ra *e aisoscomerciales e+resa*a en miles *e J es:

40X1+ 75X2+ 30X3+15X4 00


25/42

25

La res&riccin *e la can&i*a* *e mu/eres e+resa*a en *iez

miles es:1 2 3 4

30 40 20 10 200X X X X+ + +

1 240 75 500X X+

La res&riccin *el gas&o en 3 e+resa*a en miles *e J es:

El res&o *e las res&ricciones son:

X1 3 !comerciales en 3 en orario *iurno$

X2 2 !comerciales en 3 en orario es&elar$5 X3 10 !comerciales en ra*io$

5 X4 10 !comerciales en reis&as$


26/42

26

Binalmen&e el PPL ser8:

1 2 3 4

1 2 3 4

1 2 3 4

1 2

1

2

3

3

4

4

400 900 500 200

!

40 75 30 15 00

30 40 20 10 200

40 75 500

3

2

5

10

5

10

Max Z X X X X

sujeto a

X X X X

X X X XX X

X

X

X

X

X

X

= + + +

+ + +

+ + +

+


27/42

27

Programar la +ro*uccin *e un &em +ara las +rimas 4

semanas. El cos&o *e +ro*uccin es J1 +ara las *os+rimeras semanas y J15 +ara las *os 0l&imas. Las *eman*assemanales son 2 7 ' K y *e,en sercom+le&amen&e sa&isfecas. La +lan&a +ue*e +ro*ucir 7

usemana.La ca. +ue*e &ra,a/ar con so,re&iem+o *uran&e la # y 2semana as la +ro*uccin +ue*e aumen&ar as&a en #uni*a*es +ero el cos&o aumen&a en J5 +or &em. La

+ro*uccin en eceso se almacena a J2 +or &em. MCmo se

*e,e +rogramar la +ro*uccinN

'(uda: ?efinir aria,le *e *ecisinXij: Can&i*a* a +ro*ucir en

la semana i +ara ser consumi*a en la semana j. Pue*e ser

necesario la *efinicin *e o&ro &i+o *e aria,le.


28/42

28

OI)?9 LA"" C9. +ro*uce ar&culos *e i*rio *e al&a

cali*a* =ue incluyen en&anas y +uer&as *e i*rio. 3iene &res+lan&as. Los marcos y las mol*uras *e aluminio se acen enla +lan&a1 los *e ma*era en la +lan&a #Q y la +lan&a 2 +ro*uceel i*rio y el ensam,la*o *e los +ro*uc&os. En es&e momen&o

la com+a>a +ro*uce *os +ro*uc&os:Pro*uc&o 1: una +uer&a *e i*rio *e K +ies *e al&o con marco*e aluminio.

Pro*uc&o #: una en&ana *e res,aln con marco *e ma*era

*e 4 6 +ies#.

?e,i*o a las carac&ers&icas *e ca*a +ro*uc&o el +ro*uc&o 1re=uiere ser +rocesa*o en las +lan&as 1 y 2 mien&ras =ue el #en las +lan&as # y 2.


29/42

29

La siguien&e &a,la resume los recursos necesarios +ara la+ro*uccin semanal en lo&es *e los +ro*uc&osQ la ca+aci*a**e ca*a +lan&a y la u&ili*a* o,&eni*a +or la en&a *e ca*a lo&e.


30/42

30

#ariables de $ecisin:

X1: nR *e lo&es *el +ro*uc&o 1 fa,rica*os +or semana.

X2: nR *e lo&es *el +ro*uc&o # fa,rica*os +or semana.

Z: ganancia semanal &o&al !en miles *e *lares$.

)es"ricciones:

( )

( )

( )

1

2

1 2

1 4 1

2 12 2

3 2 1 3

hora lotes horasX Planta

lote semana semana

hora lotes horasX Plantalote semana semana

horas horas horasX X Planta

semana semana semana

+


31/42

31

1 23 5

!Max Z X Xsujeto a

= +

1

2

1 2

1 2

4

2 12

3 2 1

, 0

X

X

X X

X X

+

As la formulacin *el PPLes:

Funcin b!e"ivo: Z = 3X1+ 5X2


32/42

32

egin Bac&i,le +ara el+ro,lema *e OI)?9LA"" C9.


33/42

33

?es+lazamien&o *e la B.9.


34/42

34

M"iem+re eis&e una solucin +&imaN

I si eis&e una solucin +&ima Msiem+re es 0nicaN

Los PPL +ue*en ser *e 4 &i+os:

1. 3iene solucin p"ima *nica.#. 3iene soluciones p"imas al"erna"ivas.

2. )o es +ac"ible.

4. )o esaco"ado: "u+eriormen&e !maimizacin$ oinferiormen&e !minimizacin$


35/42

35

,n &&L no +ac"ible-"u+ongamos =ue OI)?9 LA"" C9. necesi&a

=ue el ren*imien&o ne&o !ganancias$ semanales sean

*e +or lo menos J5.. As &en*ramos =ueagregar al +ro,lema la res&riccin: 3X1+ 5X2 50"

?e es&a forma gr8ficamen&e las res&ricciones

=ue*aran e+resa*as como:


36/42

36


37/42

37

,n &&L con soluciones p"imas al"erna"ivas-

"u+ongamos =ue OI)?9 LA"" C9. a

rec&ifica*o la informacin en&rega*a *isminuyen*o la

u&ili*a* +or lo&e *el +ro*uc&o # *e J5. a J#..

As &en*ramos =ue cam,iar la B.9. *el +ro,lema la

cual =ue*ara como:Z =3X1+ 2X2" ?e es&a forma la

regin fac&i,le *el +ro,lema =ue*ara como:


38/42

38


39/42

39

,n &&L no aco"ado-

"u+ongamos =ue en el mo*elo *el +ro,lema *e

OI)?9 LA"" C9. se an omi&i*o las *os 0l&imas

res&ricciones !+lan&a # y +lan&a 2$. ?e es&a forma la

regin fac&i,le no =ue*ara aco&a*a su+eriormen&e lo

cual +roocara =ue las u&ili*a*es *e la com+a>a

+o*ran crecer en forma in*efini*a. Es&o se ilus&ra a

con&inuacin.


40/42

40


41/42

41

.l papel de los v/r"ices en la rein +ac"ible-

Primeramen&e *efiniremos

una solucin +ac"ible en

un v/r"ice como una

solucin =ue es&8 en una

es=uina *e la regin

fac&i,le.


42/42

)elacin en"re las soluciones p"imas ( las

soluciones +ac"ibles en los v/r"ices F.#

Consi*ere cual=uier PPL con soluciones fac&i,les y una

regin fac&i,le aco&a*a. El +ro,lema *e,e +oseer

soluciones BE y al menos una solucin +&ima. %8s

a0n la me!or solucin F.# *e,e ser una solucin

p"ima. En&onces si un +ro,lema &iene eac&amen&e

una solucin +&ima ;s&e *e,e ser una solucin BE. "iel +ro,lema &iene soluciones +&imas al&erna&ias al

menos *os *e,en ser BE.

cap1 - programacion lineal

Documents