Download - Ues Ixtapaluca
-
7/26/2019 Ues Ixtapaluca
1/37
21
UES IXTAPALUCA
UNIVERSIDAD MEXIQUENSE DEL BICENTENARIO
INVESTIGACION DE OPERACIONES I
OSCAR SOLS BELTRN OSCAR
ALUMNO:
ADRIANA RIVERA BASILIO
REPORTE DE INVESTIGACION
CARPETA DE EVIDENCIAS
24LF161
-
7/26/2019 Ues Ixtapaluca
2/37
21
INDICE
INTRODUCCIN................................................................................................... 3
UNIDAD III PROGRAMACIN LINEAL.................................................................... 4
!1 METODO DE SOLUCIN.................................................................................. 4
FORMAS EQUIVALENTES DEL MODELO DE PROGRAMACIN LINEAL!..............4
EQUIVALENCIA ALGEBRAICA PARA EL MODELO DE PROGRAMACIN LINEAL..5
!1!1 M"TODO GRFICO PARA RESOLVER MODELOS DE PROGRAMACIN LINEALCON SOLO DOS VARIABLES!................................................................................8
GRFICO DE UNA ECUACIN EN TRES DIMENSIONES!...................................10
PASOS PARA GRAFICAR.................................................................................10
E#EMPLO....................................................................................................... 12
$OLGURAS % EXCEDENCIAS.......................................................................... 17
CARACTERSTICAS DE LA $OLGURA..........................................................18
!1!2 TEORIA DEL METODO SIMPLEX..................................................................19
FASES............................................................................................................ 19
!1! FORMA TABULAR DEL METODO SIMPLEX..................................................22
M"TODO SIMPLEX DE 2 FASES.......................................................................29
!2 APLICACIONES DE LA PROGRAMACION LINEAL...........................................32
CUESTIONARIO..................................................................................................33
BIBLIOGRAFA................................................................................................... 34
-
7/26/2019 Ues Ixtapaluca
3/37
21
INTRODUCCIN
Mucha gente sita el desarrollo de la programacin lineal entre los avancescientficos ms importantes de la mitad del siglo XX, y debemos estar de acuerdo
con esta afirmacin si tenemos en cuenta que su impacto desde 19! ha sido
e"traordinario# $e han escrito decenas de libros de te"to sobre la materia y los
artculos publicados que describen aplicaciones importantes se cuentan ahora por
cientos# %e hecho, una proporcin importante de todo el clculo cientfico que se
lleva a cabo en computadoras se dedica al uso de la programacin lineal y a
t&cnicas ntimamente relacionadas# '(sta proporcin se estim en un )*, en un
estudio de la +M-#
.n modelo de programacin lineal proporciona un m&todo eficiente para
determinar una decisin ptima, 'o una estrategia ptima o un plan ptimo-
escogida de un gran nmero de decisiones posibles#
(n todos los problemas de /rogramacin 0ineal, el obetivo es la ma"imacin o
minimi2acin de alguna cantidad#
-
7/26/2019 Ues Ixtapaluca
4/37
21
UNIDAD III PROGRAMACIN LINEAL
!1 METODO DE SOLUCIN
("isten m&todos de solucin del modelo de programacin lineal, tanto grfico
como analtico# /ara la gran mayora de los problemas es indispensable aplicar la
metodologa analtica, con los algoritmos muy eficientes que desarrollaron los
cientficos ya citados en los antecedentes de /0# /ero en beneficio de la claridad,
conviene iniciar la e"posicin de cmo resolver el problema ya formulado con
programacin lineal, con el m&todo grfico, que por su sencille2, es posible que el
alumno se motive ms para el estudio# /ara ello primero se debe revisar la forma
en que puede presentarse un modelo o planteamiento del problema que se
estudia#
FORMAS EQUIVALENTES DEL MODELO DE PROGRAMACIN LINEAL!
3dems de la necesaria generali2acin del modelo de programacin lineal, estat&cnica requiere el uso de dos formas especiales equivalentes4 las que se
denominan forma cannica, la cual es muy til en teora de dualidad cuando se
trata de hacer una interpretacin econmica para el problema en estudio4 la otra
-
7/26/2019 Ues Ixtapaluca
5/37
21
forma se denomina estndar, la cual es indispensable si se desea resolver el
problema# 3 continuacin se dan caractersticas de ambas5
6ormas equivalentes del modelo de programacin lineal
EQUIVALENCIA ALGEBRAICA PARA EL MODELO DE PROGRAMACIN
LINEAL
1- 0a funcin obetivo cambia al multiplicar5
a#
)- .na restriccin cambia al multiplicar por5
a#
7- .na &'()&*++*,- '- *./00 '3/*0' 0 5( &'()&*++*5-'( '-
'(*./00con los mismos t&rminos4 la primera de tipo 8 y la segunda
de :, si el obetivo es m"imo4 con mnimo, se invierte el orden#
;- .na restriccin '8- se hace '-, (/0-5la holgura $*789en el lado
i2quierdo#
-
7/26/2019 Ues Ixtapaluca
6/37
21
- .na restriccin ':- se hace '-, &'()0-5una supervit S* 789en el lado
i2quierdo#
')*5 ?-*5 @FOREQUI1!
@btener las formas cannica y estndar para el siguiente modelo de /0 que
incluye condiciones muy especiales para las variables como es X 1libre, lo que
significa que puede tomar valores positivos, negativos y cero, obligando los
acuerdos para su tratamiento algebraico que permita el uso de /0# 0a variable
X7se eemplifica de manera especial, como no positiva4 todo lo anterior para meor
ilustracin del tema5
-
7/26/2019 Ues Ixtapaluca
7/37
21
-
7/26/2019 Ues Ixtapaluca
8/37
21
F5&0 C0-,-*+0 < E()=-0& +5- 5>')*5 =*5 @FOREQUI2!
$e presenta para ayuda del estudiante que requiera ilustracin adicional en la
conversin del modelo de /0 a las formas cannica y estndar5
-
7/26/2019 Ues Ixtapaluca
9/37
21
!1!1 M"TODO GRFICO PARA RESOLVER MODELOS DEPROGRAMACIN LINEAL CON SOLO DOS VARIABLES!
(n esta seccin interesa hacer anlogos geom&tricos, esto es, grficas de
funciones lineales que contiene el modelo matemtico de programacin lineal
obtenido en la formulacin del problema que se anali2a# %icho modelo puede
contener e"presiones tanto en forma de ecuaciones ' - como en desigualdades '
8 : -, cada una de ellas corresponde a un grfico en la analoga geom&trica#
-
7/26/2019 Ues Ixtapaluca
10/37
21
/rimero considere la infinidad de puntos que constituyen en conunto el plano y los
cuatro cuadrantes convencionalmente aceptados, para dividirlo en 2onas
caracteri2adas por la combinacin de signo que se puede dar, a los valores
medidos con nmeros reales# /ara lograr los cuadrantes en el plano se utili2an los
ees cartesianos con escala de medicin de valores de las variables del problema4
por eemplo, se puede asignar el ee hori2ontal de abscisas para la medicin de
valores de la variable X14 tambi&n se puede asignar el ee vertical de ordenadas,
para la medicin de valores de la variable X)# 0a locali2acin de cualquier punto
en este espacio plano requiere de una distancia hori2ontal 'X1- y de una distancia
vertical 'X)- denotado como par ordenado o vector 'X1, X)-# .n punto sobre el ee
X1 corresponde a X)! y un punto sobre el ee X)
corresponde a X1!, que son las ecuaciones respectivas
de los ees hori2ontal y vertical# %ichos ees se cru2an en
el punto 'X1, X)- '!, !-, el cual se conoce como origen#
$i la ecuacin tiene slo dos variables, el grfico de la
misma sobre el plano es una lnea recta, es decir, se requiere un espacio de dos
dimensiones, la hori2ontal y la vertical, para graficar tal ecuacin4 pero la
representacin geom&trica de una ecuacin en tres variables, requiere un espacio
de tres dimensiones# (n tal caso, a los ees X1 y X), se les agrega un tercer ee
X7 como tercera dimensin, que pasa
por el origen hacia el observador# 0os grficos de la 6igura 1?17 y 6igura 1?1;
muestran lo anterior para una ecuacin cualquiera5
-
7/26/2019 Ues Ixtapaluca
11/37
21
GRAFICO DE UNA ECUACIN DIMENCIONAL
GRFICO DE UNA ECUACIN EN TRES DIMENSIONES!
(l m&todo grfico proporciona la oportunidad de visuali2ar algunos de los
conceptos importantes de la programacin lineal# /ero tiene una gran limitacin
referente, a que slo es posible aplicarlo en problemas muy pequeAos4 para este
curso se limita el m&todo grfico aplicado a problemas con slo dos variables# (l
m&todo grfico para resolver problemas que se han modelado con programacin
lineal consiste en asignar un ee cartesiano para cada una de las dos variables
involucradas4 de esta manera se asigna, por eemplo, el ee hori2ontal como
escala para los distintos valores que pueda tener la variable X 14 tambi&n se puede
asignar el ee vertical con su respectiva escala para ubicar los distintos valores
que puede tomar la variable X)# .n sistema con dos ees cartesianos, hori2ontal y
vertical, permite representar en un espacio plano las lneas rectas que
geom&tricamente hablando representan cada e"presin matemtica lineal con
slo dos variables# 0as restricciones y condiciones de signo del problema,
representan al sistema que debe graficarse en un plano y despu&s se valora en el
mismo la funcin econmica B, con la cual se busca un punto del sistema quema"imice o bien minimice su valor#
/ara meor comprensin del m&todo grfico de solucin de problemas modelados
con programacin lineal, se presenta el siguiente eemplo que se detalla lo
suficiente para el voluntarioso estudiante de esta t&cnica poderosa en su
-
7/26/2019 Ues Ixtapaluca
12/37
21
aplicacin# /osteriormente se presentan otros eemplos con el propsito de
profundi2ar en la enseAan2a e intentar mayor avance en el aprendi2ae#
PASOS PARA GRAFICAR
/aso 1# Craficar las restricciones# 0as condiciones de no negatividad nos indican
que ambas variables deben ser mayores o iguales a cero, por lo que el espacio de
los puntos que cumplan con las condiciones necesariamente debe estar en el
primer
cuadrante# 0a primera restriccin, ") D 1!, indica que hay que producir al menos
1! mesas de tipo nrdico pues ya hay un pedido de 1! mesas 'grfica )#1-# (sta
restriccin acota la regin factible5 todos los puntos pertenecientes al rea
sombreada cumplen con la primera restriccin5 ambas variables son positivas y ")
D 1!# 0a segunda restriccin es no e"ceder las ;! horas disponibles para la
fabricacin de ambos tipos de mesas# 3l agregar esta segunda restriccin se
reduce la regin factible5 slo los puntos que aparecen sombreados en la grfica
)#) representan las posibles soluciones4 esto es, las combinaciones del nmero de
mesas de tipo colonial y nrdico que se pueden fabricar con las ;! horas y que
por lo menos haya 1! de estilo nrdico#
-
7/26/2019 Ues Ixtapaluca
13/37
21
(n general, cada restriccin acota el rea de las posibles soluciones4 aun as, el
n?mero de soluciones posibles es muy grande4 si se consideran variables reales,
hay infinitas soluciones#
/aso )# (valuacin de las posibles soluciones# /ara esto debe evaluarse la
funcin de utilidad para cada una de las posibles soluciones# (n el cuadro )#) se
muestran los resultados para algunas de estas posibles soluciones# $e puede
observar que
cuanto mayor sea el nmero de mesas, aumenta la utilidad# Eambi&n vemos que
en cuanto aumenta el nmero de mesas tipo colonial, disminuye el nmero
m"imo de mesas tipo nrdico que se pueden fabricar# /ara garanti2ar que el
resultado sea el ptimo, sera necesario calcular la funcin de utilidad para cada
uno de los puntos solucin, que en este sencillo caso llegan a algunos cientos de
puntos#
/aso 7# (valuacin de los v&rtices# 3fortunadamente no es necesario evaluar
todas las soluciones ya que para todo problema de pl, y dado que el rea factible
-
7/26/2019 Ues Ixtapaluca
14/37
21
siempre es una figura conve"a, se puede comprobar que la fo toma su valor
m"imo o mnimo en un v&rtice, o un lado del rea que representa el conunto desoluciones# 0a regin factible tiene cuatro v&rtices5
E#EMPLOP&5>'0 ' +5>*-0& &5/++*,- 0&0 =*0 /)**0 @QUIMCAR!
QUIMCAR
(s una empresa que elabora varios productos qumicos# (n un proceso de
produccin en particular se utili2an tres recursos como materia prima de dos
productos5 una cera automotri2 y una pasta pulidora, que se usan en la pintura de
la carrocera a vehculos automotores y se distribuye para su venta al menudeo a
varias empresas distribuidoras# /ara producir la cera y la pasta se utili2an tres
recursos, segn se muestra en la siguiente tabla, en la cual se observa que una
tonelada de cera es una me2cla de )F de tonelada del recurso 1 y 7F de tonelada
del 7# /or otro lado, una tonelada de pasta es la me2cla de 1F), 1F y 7F1! de
tonelada de los recursos 1,) y 7, respectivamente#
0a produccin de la cera automotri2 y la pasta pulidora est restringida a la
disponibilidad de los tres recursos# /ara el periodo de produccin anual, se tienen
disponibles las cantidades siguientes de cada una de las materias primas#
-
7/26/2019 Ues Ixtapaluca
15/37
21
F*./&0 11! R'+/&(5( *(5-*>'( 0&0 0 &5/++*,- '- ''5 QUIMCAR!
F*./&0 116! M0)'&*0 &'3/'&*5 0&0 +'&0 < 0()0 /*5&0 '- ''5
QUIMCAR!
(l departamento de contabilidad ha anali2ado las cifras de produccin, asignando
los costos correspondientes para ambos productos, lleg a precios que resultan en
una contribucin a la utilidad de ;!! dlares por cada tonelada de cera automotri2
y de 7!! dlares por cada tonelada de pasta pulidora, producidas# 0a
administracin, despu&s de anali2ar la demanda potencial, ha concluido que los
precios establecidos aseguran la venta de toda la cera y pasta que se produ2ca#
(l problema es determinar5 1G#?.n conunto de e"presiones matemticas
o 5'5, representando el obetivo y restricciones del problema descrito#
)G#? R'(5'& '- 5&0 .&=*+0y determinar cuntas toneladas de cera y pasta
debe producir la empresa para ma"imi2ar la contribucin total a la utilidad#
D'*-*+*,- ' 0( 0&*0>'( < /-+*,- 5>')*5
Homo ya se apunt anteriormente, los problemas de programacin lineal tienen un
obetivo ya sea de m"imo o bien de mnimo# (n este problema, el obetivo es
de 0**0&la +5-)&*>/+*,- a la utilidad y se plantea en forma matemtica
introduciendo alguna forma simple de notacin, como sigue5
-
7/26/2019 Ues Ixtapaluca
16/37
21
10! P0&)'!D'*-*+*,- ' 0&*0>'(!
(s importante precisar la unidad de medida5
20! 0&)'! F/-+*,- 5>')*5!
0a contribucin a la utilidad se origina de5 '1- la que proviene de la
produccin de X1toneladas de cera automotri2, y ')- la que proviene de la
produccin de X) toneladas de pasta pulidora# %ado que se gana ;!!
dlares por cada tonelada de cera producida, la empresa gana H499 X1si
se producen X1toneladas de cera# Eambi&n, en vista de que se gana 7!!
dlares por cada tonelada de pasta producida, la empresa gana H99 X2si
se producen X)toneladas de pasta# +dentificando con B la contribucin total
a la utilidad y eliminando el signo de dlares se tiene5
(l problema es encontrar la combinacin de produccin que ma"imice la
contribucin total a la utilidad# (sto es, se deben determinar los valores
para X1y X)que den el valor ms elevado posible de B# (n terminologa de
programacin lineal, se nombran a X1y a X)como las 0&*0>'( '
'+*(*,-# %ado que el obetivo de ma"imi2ar la utilidad es una funcin de
&stas, entonces se dice que B 499 X1 99 X2es la funcin obetivo, que
tambi&n se puede escribir 0>&'*0-5 5( +5'*+*'-)'(a unidades
que (*.-**+0- +*'-)5( ' ,0&'( 5& )5-'00producida, como sigue5
-
7/26/2019 Ues Ixtapaluca
17/37
21
Hualquier combinacin de produccin de cera y pasta se conoce como una
solucin al problema# $in embargo, nicamente aquellas (5/+*5-'( 3/'
(0)*(0.0- )50( 0( &'()&*++*5-'( se conocen como(5/+*5-'( 0+)*>'( 5
5(*>'# 0a combinacin especfica de produccin factible, que resulte en la
contribucin mayor a la utilidad, se conoce como la combinacin de produccin
ptima, o simplemente,0 (5/+*,- ,)*0# /ero primero se requiere conocer
todas las restricciones del problema y posteriormente se muestra un m&todo para
definir grficamente, en el plano de dibuo, el espacio en que se ubican el conunto
de puntos de solucin factible#
0! P0&)'! R'()&*++*5-'( ' 0)'&*0 &*0!
0a cantidad de materia prima disponible, condiciona o sueta el valor de la
funcin obetivo para cumplirse con los tres &'+/&(5( **)05(, calculando
las posibles soluciones en las cantidades de cera y pasta que se pueden
producir# $egn la informacin de produccin, se sabe que cada tonelada
de cera automotri2 utili2a )F toneladas del recurso 1, por lo que el total de
toneladas del mismo utili2ado en la produccin de X1toneladas de cera es
)FX14 adems, cada tonelada de pasta usa 1F) tonelada del recurso 1,como resultado, X)toneladas de pasta usan 1F) X)toneladas de recurso 1,
entonces el consumo total de toneladas de recurso 1 para producir X 1de
cera y X)de pasta est dado por
%ebido a que se tiene un m"imo de )! toneladas de materia prima 1 disponible,
la combinacin de produccin a decidir debe satisfacer la restriccin
-
7/26/2019 Ues Ixtapaluca
18/37
21
0a relacin anterior es una desigualdad que anota las contribuciones al
consumo de recurso 1, utili2adas en la produccin de X1toneladas de ceray de X)toneladas de pasta, que debe ser menos que o igual a )! toneladas
disponibles#
0a tabla indica que el recurso ) no es requerido por la cera, pero si por la
pasta pues cada tonelada producida de &sta requiere 1F tonelada de las
disponibles, se e"presa as5
$i desea, ahora verifique por s mismo que la restriccin para la materia
prima 7 es
Iasta aqu se han definido, las restricciones de materia prima4 slo falta
establecer que las toneladas de cera y pasta no puede ser un nmero
negativo#
40 0&)'! C5-*+*5-'( ' 05& -5 -'.0)*5 0&0 0( 0&*0>'(:
-
7/26/2019 Ues Ixtapaluca
19/37
21
(sto asegura valores no negativos de las variables de decisin como
solucin al problema presente, se conocen como restricciones de nonegatividad y son una caracterstica general de los problemas de
programacin lineal#
SOLUCIN GRFICA
.n problema de programacin lineal con slo dos variables de decisin se puede
resolver de manera grfica sobre el espacio plano# $e
inicia este procedimiento de solucin desarrollando
una grfica que despliegue las posibles soluciones
'valores X1y X)- para el problema J.+MH3K#
3parecen los valores de X1sobre un ee hori2ontal y
los valores de X)sobre uno vertical# %e esta manera
se divide el plano o papel de trabao, en cuatro
espacios limitados por los ees, formando as los
cuadrantes 1, ), 7 y ;# Hualquier punto de la grfica puede quedar identificado por
un par de valores X1y X), que representa la posicin del punto con respecto de losees X1y X)# Hada par 'X1, X)- corresponde a un punto solucin de esta manera se
tendra una infinidad de ellos en el plano considerado# /ero para la solucin
particular en la que X1 ! y X) !, se ubica un punto v&rtice identificado como
origen para ambos ees#
$OLGURAS % EXCEDENCIAS0a holgura es la cantidad de un recurso que sobra despu&s de haber reali2ado las
actividades que permiten optimi2ar el obetivo planteado# (n el problema, se
cuenta con horas, equivalentes a 7 7!! minutos para armar los equipos# 0a
ecuacin 1! E > 1) L 7 7!! indica la cantidad de minutos empleados
dependiendo de la cantidad de artculos armados# $i la solucin es '!, 1!!-, o sea,
producir solamente 1!! equipos ), se emplearn 1 )!! minutos de los 77!!, por
-
7/26/2019 Ues Ixtapaluca
20/37
21
lo que sobran ) 1!! minutos# (ste sobrante es la holgura correspondiente al
tiempo de armado# $i
consideramos el caso del rea de pruebas5 7! E > < L < !!!, se utili2arn
de los < !!! minutos disponibles, y queda un sobrante de ;!! minutos de tiempo
de armado# 0a primer restriccin indica que se deben producir al menos 1!!
artculos, y como efectivamente &stos se estn produciendo tal restriccin no tiene
holgura#
0a segunda restriccin, ? E > D !, debe satisfacerse para cumplir con la
condicin que pide que el nmero de artculos ) sea por lo menos igual a de
los artculos E1; que se produ2can# Homo de cero es cero y se estn
produciendo 1!!, se est cumpliendo con dicho requisito sobradamente, con 1!!
unidades ms de lo que pide la condicin4 esta es la holgura correspondiente a
dicha restriccin# /or ltimo, ? E > L 1! indica que el nmero de artculos ) no
debe de e"ceder al nmero de artculos E1; en ms de 1!4 en este caso, ?! >1!! L 1!4 la holgura entonces es de !, ya que faltaran ! unidades de ) para
llegar al lmite impuesto#
CARACTERSTICAS DE LA $OLGURA0a holgura est asociada a cada una de las restricciones
0a holgura se mide en las mismas unidades que la restriccin
correspondiente
Huando la restriccin es del tipo D, se suele llamar e"cedencia a la holgura#
0as holguras siempre deben ser positivas
-
7/26/2019 Ues Ixtapaluca
21/37
21
(l valor de las holguras depende del punto en que se calculen,
generalmente son los
v&rtices de la regin factible
$iempre interesan las holguras de cada restriccin para el punto solucin
Pasos para la construccin del modelo
%efinir las variables de decisin#
%efinir el obetivo o meta en t&rminos de las variables de decisin#
%efinir las restricciones#
Kestringir todas las variables para que sean no negativas#
!1!2 TEORIA DEL METODO SIMPLEX
(s un procedimiento iterativo que permite ir meorando la solucin a cada paso# (l
procesoconcluye cuando no es posible seguir meorando ms dicha solucin#
/artiendo del valor de lafuncin obetivo en un v&rtice cualquiera, el m&todo
consiste en buscar sucesivamente otrov&rtice que meore al anterior# 0a bsqueda
se hace siempre a trav&s de los lados del polgono'o de las aristas del poliedro, si
el nmero de variables es mayor-# Hmo el nmero de v&rtices'y de aristas- es
finito, siempre se podr encontrar la solucin#
(l m&todo del simple" se basa en la siguiente propiedad5 si la funcin obetivo, f,
no toma suvalor m"imo en el v&rtice 3, entonces hay una arista que parte de 3, a
lo largo de la cual f aumenta#(l m&todo del simple" fue creado en 19;= por el
matemtico Ceorge %ant2ig#
-
7/26/2019 Ues Ixtapaluca
22/37
21
(l m&todo del simple" se utili2a, sobre todo, para resolver problemas de
programacin lineal enlos que intervienen tres o ms variables#(l lgebra matricialy el proceso de eliminacin de Causs?Nordan para resolver un sistema
deecuaciones lineales constituyen la base del m&todo simple"#Hon miras a
conocer la metodologa que se aplica en el M&todo $+M/0(X, vamos a resolver
elsiguiente problema5
Ma"imi2ar B f'",y- 7" > )y sueto a5
)" > y 1O)" > 7y ;)
7" > y );"! , y !
FASES1# Honvertir las desigualdades en igualdades
$e introduce una variable de holgura por cada una de las restricciones, para
convertirlas en igualdades, resultando el sistema de ecuaciones lineales5
)" > y > h 1O )" > 7y > s ;) 7" >y > d );
)# +gualar la funcin obetivo a cero
? 7" ? )y > B !
7# (scribir la tabla inicial simple"
(n las columnas aparecern todas las variables del problema y, en las filas, los
coeficientes de las igualdades obtenidas, una fila para cada restriccin y la ltima
fila con los coeficientes de la funcin obetivo5
-
7/26/2019 Ues Ixtapaluca
23/37
21
Eabla + # +teracin nG 1 ase Pariable de decisin Pariable de holgura Palores
solucin
" y h s d
h ) 1 1 ! ! 1O s ) 7 ! 1 ! ;) d 7 1 ! ! 1 ); B Q7 Q) ! ! ! !
;# (ncontrar la variable de decisin que entra en la base y la variable de holgura
que sale de la base
/ara escoger la variable de decisin que entra en la base, nos fiamos en la ltima
fila, la de los coeficientes de la funcin obetivo y escogemos la variable con el
coeficiente negativo mayor 'en valor absoluto-# (n nuestro caso, la variable " de
coeficiente ? 7# $i e"istiesen dos o ms coeficientes iguales que cumplan la
condicin anterior, entonces se elige uno cualquiera de ellos#
$i en la ltima fila no e"istiese ningn coeficiente negativo, significa que se ha
alcan2ado la solucin ptima# /or tanto, lo que va a determinar el final del proceso
de aplicacin del m&todo del simple", es que en la ltima fila no haya elementos
negativos# 0a columna de la variable que entra en la base se llama columna
pivote '(n color a2ulado-#
/ara encontrar la variable de holgura que tiene que salir de la base, se divide cadat&rmino de la ltima columna 'valores solucin- por el t&rmino correspondiente de
la columna pivote, siempre que estos ltimos sean mayores que cero# (n nuestro
caso5
1OF) R9S , ;)F) R)1S y );F7 ROS
-
7/26/2019 Ues Ixtapaluca
24/37
21
$i hubiese algn elemento menor o igual que cero no se hace dicho cociente# (n
el caso de que todos los elementos fuesen menores o iguales a cero, entoncestendramos una solucin no acotada y no se puede seguir#
(l t&rmino de la columna pivote que en la divisin anterior d& lugar al menor
cociente positivo, el 7, ya O es el menor, indica la fila de la variable de holgura que
sale de la base, d# (sta fila se llama fila pivote '(n color a2ulado-#
T
$i al calcular los cocientes, dos o ms son iguales, indica que cualquiera de las
variables correspondientes pueden salir de la base# (n la interseccin de la fila
pivote y columna pivote tenemos el elemento pivote operacional, 7# # (ncontrar
los coeficientes de la nueva tabla#
0os nuevos coeficientes de " se obtienen dividiendo todos los coeficientes de la
fila d por el pivote operacional, 7, que es el que hay que convertir en 1#
3 continuacin mediante la reduccin gaussiana hacemos ceros los restantes
t&rminos de su columna, con lo que obtenemos los nuevos coeficientes de las
otras filas incluyendo los de la funcin obetivo B#
0as sucesivas tablas que hemos construido van proporcionando el valor de la
funcin obetivo en los distintos v&rtices, austndose, a la ve2, los coeficientes de
las variables iniciales y de holgura#
(n la primera iteracin 'Eabla +- han permanecido todos los coeficientes iguales, se
ha calculado el valor de la funcin obetivo en el v&rtice 3'!,!-, siendo este !# 3
continuacin se despla2a por la arista 3, calculando el valor de f , hasta llegar a
-
7/26/2019 Ues Ixtapaluca
25/37
21
# (ste paso aporta la Eabla ++# (n esta segunda iteracin se ha calculado el valor
que corresponde al v&rtice 'O,!-5 Bf'O,!- ); # $igue por la arista H, hastallegar a H, donde se para y despliega los datos de la Eabla +++# (n esta tercera
iteracin se ha calculado el valor que corresponde al v&rtice H'
-
7/26/2019 Ues Ixtapaluca
26/37
21
el nmero de variables es mayor-# Hmo el nmero de v&rtices 'y de aristas- es
finito, siempre se podr encontrar la solucin#
(l m&todo del simple" se basa en la siguiente propiedad5 si la funcin obetivo, f,
no toma su valor m"imo en el v&rtice 3, entonces hay una arista que parte de 3, a
lo largo de la cual f aumenta# Hon miras a conocer la metodologa que se aplica en
el M&todo $+M/0(X, vamos a resolver el siguiente problema5
Ma"imi2ar B f'",y- 7" > )y
sueto a5 )" > y 1O
)" > 7y ;)
7" > y );
" ! , y !$e consideran las siguientes fases5
1# Honvertir las desigualdades en igualdades
$e introduce una variable de holgura por cada una de las restricciones, para
convertirlas en igualdades, resultando el sistema de ecuaciones lineales5
)" > y > h 1O
)" > 7y > s ;)
7" >y > d );
)# +gualar la funcin obetivo a cero
-
7/26/2019 Ues Ixtapaluca
27/37
21
? 7" ? )y > B !
7# (scribir la tabla inicial simple"
(n las columnas aparecern todas las variables del problema y, en las filas, los
coeficientes de las igualdades obtenidas, una fila para cada restriccin y la ltima
fila con los coeficientes de la funcin obetivo5 Eabla + # +teracin nG 1 # ase
Pariable de decisin Pariable de holgura Palores solucin
" y h s d
h ) 1 1 ! ! 1O
s ) 7 ! 1 ! ;)
d 7 1 ! ! 1 );
B Q7 Q) ! ! ! !
;# (ncontrar la variable de decisin que entra en la base y la variable de holguraque sale de la base
3# /ara escoger la variable de decisin que entra en la base, nos fiamos en la
ltima fila, la de los coeficientes de la funcin obetivo y escogemos la variable con
el coeficiente negativo mayor 'en valor absoluto-# (n nuestro caso, la variable "
de coeficiente ? 7#
$i e"istiesen dos o ms coeficientes iguales que cumplan la condicin anterior,entonces se elige uno cualquiera de ellos# $i en la ltima fila no e"istiese ningn
coeficiente negativo, significa que se ha alcan2ado la solucin ptima# /or tanto, lo
que va a determinar el final del proceso de aplicacin del m&todo del simple", es
-
7/26/2019 Ues Ixtapaluca
28/37
21
que en la ltima fila no haya elementos negativos# 0a columna de la variable que
entra en la base se llama columna pivote '(n color a2ulado-# # /ara encontrar lavariable de holgura que tiene que salir de la base, se divide cada t&rmino de la
ltima columna 'valores solucin- por el t&rmino correspondiente de la columna
pivote, siempre que estos ltimos sean mayores que cero# (n nuestro caso5
1OF) R9S , ;)F) R)1S y );F7 ROS
$i hubiese algn elemento menor o igual que cero no se hace dicho cociente# (n
el caso de que todos los elementos fuesen menores o iguales a cero, entonces
tendramos una solucin no acotada y no se puede seguir# (l t&rmino de lacolumna pivote que en la divisin anterior d& lugar al menor cociente positivo, el 7,
ya O es el menor, indica la fila de la variable de holgura que sale de la base, d#
(sta fila se llama fila pivote '(n color a2ulado-# $i al calcular los cocientes, dos o
ms son iguales, indica que cualquiera de las variables correspondientes pueden
salir de la base# H# (n la interseccin de la fila pivote y columna pivote tenemos el
elemento pivote operacional, 7#
# (ncontrar los coeficientes de la nueva tabla#
0os nuevos coeficientes de " se obtienen dividiendo todos los coeficientes de la
fila d por el pivote operacional, 7, que es el que hay que convertir en 1#
3 continuacin mediante la reduccin gaussiana hacemos ceros los restantes
t&rminos de su columna, con lo que obtenemos los nuevos coeficientes de las
otras filas incluyendo los de la funcin obetivo B#
Eambi&n se puede hacer utili2ando el siguiente esquema5
6ila del pivote5
Uueva fila del pivote 'Piea fila del pivote- 5 '/ivote-
-
7/26/2019 Ues Ixtapaluca
29/37
21
Kesto de las filas5
Uueva fila 'Piea fila- ? 'Hoeficiente de la viea fila en la columna de la variable
entrante- X 'Uueva fila del pivote-
Pemoslo con un eemplo una ve2 calculada la fila del pivote 'fila de " en la Eabla
++-5
Piea fila de s ) 7 ! 1 ! ;)
? ? ? ? ? ?
Hoeficiente ) ) ) ) ) )
" " " " " "
Uueva fila pivote 1 1F7 ! ! 1F7 O
Uueva fila de s ! =F7 ! 1 Q)F7 )