Date post: | 13-Apr-2018 |
Category: |
Documents |
Upload: | carlosperez |
View: | 222 times |
Download: | 3 times |
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 1/18
Ejercicio de Programación Lineal
Instituto Profesional Esucomex
Módulo Herramientas Cuantitativas para la
Administración
Profesor : Carlos Pérez Urrea
Mail: [email protected]
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 2/18
Cada muñeco:• Produce un beneficio neto de 3 U$.• Requiere 2 horas de trabajo de acabado.• Requiere 1 hora de trabajo de carpinteria.
Cada tren:• Produce un beneficio neto de 2 U$.• Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora trabajo de carpinteria.
Ejemplo
epetto !.".# manufactura muñecos trenes de madera.
Cada semana epetto puede disponer de:• %odo e& materia& que necesite.• !o&amente 1'' horas de acabado.• !o&amente (' horas de carpinteria.
%ambi)n:• "a demanda de trenes puede ser cua&quiera *sin &+mite,.• "a demanda de muñecos es como mucho -'.
epetto quiere maimi/ar sus beneficios.¿Cuántos muñecos y cuántos trenes debe fabricar?
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 3/18
0a / 31 22 *funcin objeti4o,
!ujeto a *s.a:,2 1 2 5 1'' *restriccin de acabado,
1 2 5 (' *restriccin de carpinteria,
1 5 -' *restriccin de demanda de muñecos,
1# 2 6 ' *restriccin de no ne7ati4idad,
Para e& prob&ema de epetto# combinando &as restricciones desi7no 1 6 ' e 2 6 ' con &a funcin objeti4o &as restricciones#tenemos e& si7uiente mode&o de optimi/acin:
Formulación del problema
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 4/18
Región factible
1 -' e 2 2' est8 en &a
re7in factib&e porque satisfacentodas &as restricciones deepetto.
!in embar7o# 1 19# 2 ' noest8 en &a re7in factib&e porqueeste punto no satisface &arestriccin de carpinteria
;19 ' < ('=.
Restricciones de Gepetto
2x1 + x2 ≤ 100 (restricción finalizado
x1 + x2 ≤ !0 (restricción carpinter"a
x1 ≤ #0 (restricción demanda
x1$ x2 % 0 (no ne&ati'idad
"a re&ión factile de un PP" es e& conjunto de todos &os puntosque satisfacen todas &as restricciones. >s &a re7in de& p&anode&imitada por e& sistema de desi7ua&dades que forman &asrestricciones.
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 5/18
Solución óptima
"a maor+a de PP" tienen so&amente una so&ucinptima. !in embar7o# a&7unos PP" no tienenso&ucin ptima# otros PP" tienen un n?meroinfinito de so&uciones.
08s ade&ante 4eremos que &a so&ucin de& PP" de
epetto es 1 2' @2 A'. >sta so&ucin da un4a&or de &a funcin objeti4o de:
/ 31 22 3B2' 2BA' 1(' U$
Cuando decimos que 1 2' 2 A' es &a so&ucin ptima#estamos diciendo que# en nin7?n punto en &a re7in factib&e# &a
funcin objeti4o tiene un 4a&or *beneficio, superior a 1('.
Para un prob&ema de maimi/acin# una solución
óptima es un punto en &a re7in factib&e en e& cua&&a funcin objeti4o tiene un 4a&or m8imo. Para unprob&ema de minimi/acin# una so&ucin ptima esun punto en &a re7in factib&e en e& cua& &a funcinobjeti4o tiene un 4a&or m+nimo.
!e puede demostrarque &a solución
óptima de un PP"est8 siempre en &afrontera de &a re7infactib&e# en un4)rtice *si &a
so&ucin es ?nica, oen un se7mentoentre dos 4)rticesconti7uos *si hainfinitas so&uciones,
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 6/18
Representación Gráfica de las restricciones
21 2 1''
Cua&quier PP" con s&o dos
4ariab&es puede reso&4erse7r8ficamente.
Por ejemp&o# para representar7r8ficamente &a primera
restriccin# 2x1 + x2 ≤ 100 :ibujamos recta 21 2 1''
2'
2' -' A' ('
-'
A'
('
1''
2
1
>&e7imos e& semip&ano quecump&e &a desi7ua&dad: e&punto *'# ', &a cump&e
*2B' ' 5 1'',#as+ que tomamos e&semip&ano que &o contiene.
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 7/18
ibu!ar la región factible
Puesto que e& PP" de epetto tiene dos 4ariab&es# se puede reso&4er7r8ficamente. "a re7in factib&e es e& conjunto de todos &os puntosque satisfacen &as restricciones:
2 x1 + x2 ≤ 100 *restriccin de acabado,
x1 + x2 ≤ !0 *restriccin de carpinter+a,
x1 ≤ #0 *restriccin de demanda,
x1$ x2 % 0 *no ne7ati4idad,
Damos a dibujar &a re7in factib&e que satisface estas restricciones.
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 8/18
2
1
2'
2' -' A' ('
-'
A'
('
1''21 2 1''
Restricciones
2 x1 + x2 ≤ 100
x1 + x2 ≤ !0
x1 ≤ #0 x1$ x2 % 0
ibu!ar la región factible
%eniendo en
cuenta &asrestricciones desi7no *x1 % 0$ x2 %
0# nos queda:
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 9/18
2
1
2'
2' -' A' ('
-'
A'
('
1''
1 2 ('
ibu!ar la región factible
Restricciones
2 x1 + x2 ≤ 100
x1 + x2 ≤ !0
x1 ≤ #0
x1$ x2 % 0
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 10/18
2
1
2'
2' -' A' ('
-'
A'
('
1''
1 -'
ibu!ar la región factible
Restricciones
2 x1 + x2 ≤ 100
x1 + x2 ≤ !0
x1 ≤ #0
x1$ x2 % 0
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 11/18
2
1
2'
2' -' A' ('
-'
A'
('
1''21 2 1''
1 2 ('
1 -'
"a interseccin
de todos estossemip&anos*restricciones,nos da &a re7infactib&e
ibu!ar la región factible
Re7inEactib&e
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 12/18
2
1
2'
2' -' A' ('
-'
A'
('
1''21 2 1''
1 2 ('
1 -'
Re7in
Eactib&e
"a re7in factib&e *a&estar &imitada porrectas, es un po&+7ono.>n esta caso# e&po&+7ono FGC>.
F
G
C
>Como &a so&ucin
ptima est8 en a&7unode &os 4)rtices *F# G#C# o >, de &a re7infactib&e# ca&cu&amosesos 4)rtices.
Restricciones
2 x1 + x2 ≤ 100
x1 + x2 ≤ !0
x1 ≤ #0
x1$ x2 % 0
"ntersecciones de la región factible
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 13/18
Re7in
Eactib&e
>*'# (',
*2'# A',
C*-'# 2',
G*-'# ',
F*'# ',
"ntersecciones de la región factible
"os 4)rtices de &a re7infactib&e son intersecciones dedos rectas. >& punto es &ainterseccin de &as rectas
21 2 1'' 1 2 ('
"a so&ucin de& sistema 2'#
A' nos da e& punto .
2'
2' -' A' ('
-'
A'
('
1''
2
1
G es so&ucin de1 -'2 '
21 2 1''
1 -'
1 2 ('C es so&ucin de
1 -'21 2 1''
> es so&ucin de1 2 ('
1 '
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 14/18
2
1
2'
2' -' A' ('
-'
A'
('
1''
Re7inEactib&e
*'# (',
*2'# A',
*-'# 2',
*-'# ',
*'# ',
0a / 31 22
/ ' / 1''
/ 1('
Para ha&&ar &aso&ucin ptima#dibujamos &asrectas en &as
cua&es &os puntostienen e& mismo4a&or de /.
"a fi7ura muestraestas &ineas para
/ '# / 1''# / 1('
Resolución gráfica
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 15/18
Re7in
Eactib&e
*'# (',
*2'# A',
*-'# 2',
*-'# ',
*'# ',
0a / 31 22
/ ' / 1''/ 1('
"a ?&tima recta de/ que intersecta*toca, &a re7in
factib&e indica &aso&ucin ptimapara e& PP". Parae& prob&ema deepetto# estoocurre en e&punto *1 2'#2 A'# / 1(',.
2'
2' -' A' ('
-'
A'
('
1''
2
1
Resolución gráfica
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 16/18
Re7in
Eactib&e
*'# (',
*2'# A',
*-'# 2',
*-'# ',
*'# ',
%ambi)n podemos encontrar &aso&ucin ptima ca&cu&ando e&4a&or de / en &as interseccionesde &a re7in factib&e.
Hnters. / 31 22*'# ', / 3B'2B' '*-'# ', / 3B-'2B' 12'*-'# 2', / 3B-'2B2' 1A'*2'# A', / 3B2'2BA' 1('*'# (', / 3B'2B(' 1A'
2'
2' -' A' ('
-'
A'
('
1''
2
1
"a so&ucin ptima es:1 2' muñecos2 A' trenes/ 1(' U$ de beneficio
Resolución anal#tica
0a / 31 22
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 17/18
Iemos identificado &a re7in factib&e parae& prob&ema de epetto buscado &a
so&ucin ptima# &a cua& era e& punto en &are7in factib&e con e& maor 4a&or posib&ede /.
7/24/2019 Clase 2 Herramientas Cuantitativas
http://slidepdf.com/reader/full/clase-2-herramientas-cuantitativas 18/18
Recordar )ue*
• a re&ión factile en cual)uier PP
est, limitada por l"neas$ - la solución
dee uscarse .acia el ori&en de las
rectas/
• a re&ión factile de cual)uier PP
tiene solamente un nmero finito deintersecciones/ na de ellas es el
óptimo$ en el caso de la maximización
el 'alor de m,s alto/