Universidad de ChileDepartamento de Ingeniera MatemticaProblemas de Optimizacin para Estudiantes deIngenieraCaptulo 1: Matemticas para la OptimizacinCaptulo 2: Condiciones de OptimalidadCaptulo 3: Programacin LinealCaptulo 4: Dualidad en Programacin LinealCaptulo 5: Modelos y Algoritmos de ujos en redesAutores:Jorge AMAYA A.Cristopher HERMOSILLA J.Nicols HERNNDEZ S.14 de junio de 2009ndice general1. Matemticas para la Optimizacin 21.1. Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2. Funciones Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142. Caracterizacin de Optimalidad 162.1. Optimizacin con Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213. Programacin Lineal 233.1. Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304. Dualidad en Programacin Lineal 324.1. Dualidad y Anlisis de Sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395. Modelos y alg. para ujos en redes 425.1. Problemas de transporte y de ujo a costo mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571Captulo 1Matemticas para la Optimizacin1.1. Conjuntos Convexos1.1.1. Problemas ResueltosP1. Considere la norma euclideana en las siguientes deniciones:Dados v R30 y > 0, se llama Cono de Bishop-Phelps al conjunto K(v, ) denido por:K(v, ) =x R3: |v||x| v, x) (1.1.1)Dados a, b R2y [0, 1], se llama Ptalo de Penot al conjunto P(a, b) denido por:P(a, b) =x R2: |ax|+|x b| |ba| (1.1.2)Dados C R2y x0 R2, se llama Gota de Danes al conjunto [C, x0] denido por:[C, x0] =Co(x0C) (1.1.3)a) Pruebe que K(v, ) es convexo para cualquier v R30 y > 0b) Pruebe que P(a, b) es convexo para cualquier a, b R2y [0, 1]c) Pruebe que [C, x0] =x0 +t(c x0) : t [0, 1], c C C R2convexo y x0 R2d) Pruebe que dados a, b R2y (0, 1) entonces B(b, r) P(a, b), donder =|ab|11+. Concluya que [c, B(b, r)] P(a, b) c P(a, b)Solucin:a) Sean v R30 y > 0 jos, consideremos x, y K(v, ) y t [0, 1].Sea z =tx +(1t)y, veamos que z K(v, ):|v||z| = |v||tx +(1t)y|t|v||x|+(1t)|v||y| (propiedades de normas)t v, x) +(1t)v, x) (x, y K(v, ))=v, x)Luego z K(v, ), y como x, y, t son arbitrario se concluye que K(v, ) es convexo.2b) Sean a, b R2y [0, 1] jos, consideremos x, y P(a, b) y t [0, 1].Sea z =tx +(1t)y, veamos que z P(a, b):|az|+|z b| = |atx (1t)y|+|tx +(1t)y b|= |ta+(1t)atx (1t)y|+|tx +(1t)y tb(1t)b|= |t(ax) +(1t)(ay)|+|t(x b) +(1t)(y b)|t|ax|+(1t)|ay|+t|x b|+(1t)|y b|=t[|ax|+|x b|] +(1t)[|ay|+|y b|]t|ba|+(1t)|ba|=|ba|Luego z P(a, b), y como x, y, t son arbitrario se concluye que P(a, b) es convexo.c) Esto es directo de la denicin de Co(x0C)d) Sean a, b R2, (0, 1) y r como en el enunciado. Sea x B(b, r), luego:|x b| |ab|11+|ab| |x b|+|x b|+|ab||x b|+|x a|Luego B(b, r) P(a, b). Ms an como P(a, b) es convexo y contiene a B(b, r) se concluyeque[c, B(b, r)] P(a, b) c P(a, b)P2. Demuestre que la proyeccin en Rn, de un punto a, sobre la bola cerrada B(c, 1) (suponiendo quea/ B(c, 1)), est dada porp(a) =c +ac|ac|Solucin:Como B(c, 1) es un convexo cerrado no vaco entonces la proyeccin de a sobre la bola es nica,bastar entonces ver que p(a) =c +ac|ac| minimiza la distancia de a a la bola.d(p(a),a) =|p(a) a|=|c +ac|ac|a|=|(c a)_11|ac|_|=|c a|_11|ac|_=|ac|1por otro lado claramente p(a) B(c, 1), pues d(p(a),c) = 1.3Sea ahorax B(c, 1),d(a,x) =|ax|=|(ac) (x c)||ac||x c||ac|1= d(p(a),a)Con lo cual concluimos que p(a) es la proyeccin de a sobre B(c, 1).P3. Sea A, B Sn(R) (Matrices simtricas de nn). Supongamos que B no es denida negativa. Pruebela equivalencia de las siguientes armaciones:a) Bx, x) 0 y x ,= 0 Ax, x) > 0b) u 0 tq AuB es denida positivaIndicacin: Considere el conjunto C =(Ax, x), Bx, x)), |x| = 1, asuma que es convexo.Solucin:(a) (b)Consideremos el conjunto convexo C = (Ax, x), Bx, x)) R2: |x| = 1. Observemos que C nointersecta RR+puesto que se cumplira que Ax, x) 0 y Bx, x) 0 con |x| = 1, lo cual con-tradice (a). Luego por Hahn-Banach podemos separa C de RR+, ms an, como ambos conjuntosson cerrados, la separacin es estricta, luego r R y s = (s1, s2) R20 tal que:sTx > r x C sTy < r y RR+tomando y = 0 se tiene que r > 0. Adems si y RR+se tiene que ty RR+t > 0. Luegonecesariamente se debe tener que s10 y s20 pues de otra forma, si y RR+, sTy =s1y1+s2y2podra crecer hasta + contradiciendo el acotamiento por r.Notemos adems que s ,= 0 pues de no ser as, necesariamente s2< 0 ya que s ,= 0 con lo cual setendra que (x1, x2) C sTx = s1x1 +s2x2 > r lo que implicara que |x| = 1Bx, x) rs1(x1, x2) C Ax, x) + s2s1Bx, x) >rs1> 0 |x| = 1Luego tomando u =s2s1se concluye.(b) (a)Notemos que como A, B Sn(R), entonces A =ATy B =BTy como u 0 tal que AuB es denidapositiva, se tiene que x ,= 0:0 < xT(AuB)x = xTAx uxTBx (1.1.4)=ATx, x_uBTx, x_(1.1.5)=Ax, x) uBx, x) (1.1.6)Entonces uBx, x) pTw w SEquivalentemente:pTc > pTAx x RnTomando x =0 se concluye que 0. Armamos que ATp =0. En efecto, suponiendo que (ATp)i,=0 y tomando x =_2(ATp)i_ei se tiene:pTAx = (ATp)Tx = 2 > Que contradice la condicin de separador, luego necesariamente ATp = 0, tomandoy = (1cTp)pse concluye que (1.1.8) tiene solucin.P5. Considere el siguiente problema, en donde A es una matriz de mn :(P) mn cTxs.a : Ax = bx 0y sea x una solucin ptima.5a) Suponga que x1, . . . , xp > 0 y xj = 0 paraj = p+1, . . . , n. Demuestre que el sistema:(S) Ad = 0cTd < 0dp+1, ..., dn 0no tiene solucin.b) Demuestre, usando el teorema de Farkas, que existe un vector z tal que:ATz cSolucin:a) Supongamos que (S) tiene solucin d. Sea x(t) = x+tdAx(t) = Ax+tAd Ax(t) = Ax = bAdems x(t) = (x1 +td1, ..., xp +tdp, tdp+1, ..., tdn) 0 para t sucientemente pequeo. Luegox(t) es P-factible con t [0, t) donde t = mnxipi: pi < 0.Sea t (0, t) cualquiera. LuegocTx(t) = cTx+tcTd < cTxLo que implica que x no es solucin de P. Lo que es una contradiccin. Luego (S) no tienesolucin.b) Notemos que (S) puede escribirse como:Ad 0Ad 0Td 0Donde T =(eTp+1, ..., eTn ) (cada ei es un vector cannico de Rn). Luego por Farkas[AT, AT, TT] y = cy 0Sea y = (u, v, w) luegoATuATv +TTw =cu, v, w 0AT(v u) TTw = cu, v, w 0AT(v u) cpues TTw 0. Finalmente tomando z = v u se concluye.6P6. Considere el poliedro P =y Rm: ATy c con c Rn. Adems considere el siguiente P.L.(PL) mn cTxAx = 0x 0Pruebe que P es no vaco ssi el mnimo de (PL) es cero.Solucin:Supongamos que P es no vaco, es decir, y Rmtal que ATy c, agregando una variable de holguraz 0 y escribiendo y = uv con u, v 0 se tiene:ATuATv +z = cDenamos A0 = (ATATI) y = (u, v, z), luegoA0 = ccon 0Por Farkas w Rntal que AT0w 0, cTw > 0.Lo anterior implica que Aw = 0, w 0 y cTw > 0, pero esto ltimo es equivalente a que x 0 talque Ax = 0 y cTx < 0, pues basta tomar w =x.Finalmente con esto se puede concluir que si (PL) tiene solucin, entonces cTw 0 y como w = 0 esfactible, se concluye que el mnimo de (PL) es cero.Para probar la otra implicancia basta ver que si suponemos que el mnimo de (PL) es cero entoncesno puede exitir x 0 tal que Ax = 0 y cTx < 0, pues sto contradice el hecho que el mnimo es cero.Luego procediendo con Farkas al igual que la implicancia anterior se concluye.1.1.2. Problemas PropuestosP1. SeanZ(b) = m axcTx/Ax b, x 0V(c) = m axcTx/Ax b, x 0Demuestre que Z es cncava y V es convexa, asumiendo que b y c estn en dominios convexos en losque estos dos problemas son factibles y acotados.P2. Denamos la envoltura convexa de un conjunto de puntos x1, ..., xm Rnporco(x1, ..., xm) :=mi=1ixi/i [0, 1] i = 1, ..., mmi=0i = 1a) Demuestre explcitamente que co(x1, ..., xm) es un conjunto convexo.b) Demuestre que todo punto extremo de co(x1, ..., xm) es necesariamente uno de los puntos xi.c) Sean A =a1, ..., am1 y B =b1, ..., bm2. Demostrar queco(AB) = co(A) co(B)d) Calcule los puntos extremos del hipercubo en Rn[0, 1]n:=z Rn/zi [0, 1] i = 1, ..., n7P3. a) Demuestre que un poliedro es acotado si y slo si no tiene direcciones extremas.b) Sea P = x Rn: Ax = b, x 0 un poliedro convexo compacto (cerrado y acotado) en Rn,con A M(R)mn de rango m(m < n). Demuestre que las siguientes son equivalentes:1) Cada elemento de P tiene al menos m componentes mayores que cero.2) Cada punto extremo de P tiene exactamente m componentes mayores que cero.Indicacin: Use la caracterizacin de un poliedro en funcin de sus puntos extremos y susdirecciones extremas.P4. (Descripcin de un semi-espacio de Voronoi).Sean a y b puntos distintos de Rn. Muestre que el conjunto de todos los puntos que estn ms cercade a que de b en norma euclideana, i.e., x : |x a|2 |x b|2, es un semi-espacio. Descrbaloexplicitamente como una desigualdad de la forma cTx d. Dibjelo.P5. Sean A matriz pn y B matriz qn. Demuestre que uno y slo uno de los siguientes tienen solucina) Ax < 0 Bx = 0b) ATu+BTv = 0 u ,= 0, u 0P6. Considere la pareja primal-dual:(P) mncTx (D) m axbTyAx = b ATy cx 0Probar con Farkas que si (D) es no acotado entonces (P) es infactible.P7. Determine todos los puntos y direcciones extremas del poliedrox1 +x2 +x3 +x4 +x5= 10x1x2 +x3x4x5= 10x1, x2, x3, x4, x5 081.2. Funciones Convexas1.2.1. Problemas ResueltosP1. a) Considere el siguiente problema(P) mn f (x)gi(x) 0i = 1, ..., nDonde todas las gi son funciones convexas.Demuestre que la regin factible S =x Rn: gi(x) 0 , i = 1, ..., n es convexa.b) Considerefuna funcin convexa y S un conjunto convexo. EntoncesX =x : f (x) f (x) x Ses convexo.Solucin:a) Sean x1, x2 S y [0, 1]. Denamos z = x1 +(1)x2, veamos que z S.Sea i 1, ..., n entonces:gi(z) gi(x1) +(1)gi(x2) ( Convexidad de gi)y como x1, x2 S se tiene que gi(x1) 0 y gi(x2) 0, con lo que gi(z) 0.Dado que i es arbitrario, se concluye.b) Sean x1, x2 X y [0, 1]. Denamos z = x1 +(1)x2f (z) f (x1) +(1) f (x2) ( Convexidad def )f (x) +(1) f (x) (x S)= f (x)Finalmentef (z) f (x) x S, con lo cual z XP2. a) Sea S un conjunto convexo no vaco de Rn. Pruebe que:1) f (y) =nf|x y|/x S2) g(y) = supyTx/x Sson convexas.b) Seaf (x) = m ax f1(x), . . . , fk(x) yf1, ..., fk : S R (S Rn), funciones convexas.Demostrar quefes convexa.Solucin:a) 1) Sean y1, y2 Rny [0, 1]. Denamos z = y1 +(1)y2Dado x S cualquiera, ste se puede expresar como x = x +(1)x, entonces:f (z) |z x|=|(y1x) +(1)(y2x)||y1x|+(1)|y2x|9Luego tomando nf sobre S se tiene:f (z) nf|y1x|+(1)|y2x| : x Snf|y1x| : x S+(1)nf|y2x| : x S= f (y1) +(1) f (y2)De donde se concluye.2) Sean y1, y2 Rny [0, 1]. Denamos z = y1 +(1)y2, entonces se tiene:g(z) = sup[y1 +(1)y2]Tx : x S= supyT1x +(1)yT2x : x SsupyT1x : x S+(1)supyT2x : x S= g(y1) +(1)g(y2)De donde se concluye.b) Sean x1, x2 S y [0, 1]. Denamos z = x1 +(1)x2.Sea i 1, ..., n cualquiera, entonces:fi(z) fi(x1) +(1) fi(x2) ( Convexidad defi)f (x1) +(1) f (x2) ( puesfi(x) f (x) x S)Luego tomando mximo sobre i en el lado izquierdo se concluye.P3. Seaf : R R una funcin continua que satisface la desigualdad siguiente:f (x) 12h

x+hxhf (y)dy, x R, h > 0.Pruebe:a) El maximo defen un intervalo cerrado [a, b] es alcanzado en a o en b.b) fes convexa.Indicacin: Considere L(x) = (x a) f (b) (x b) f (a)bay G(x) = f (x) L(x)Solucin:a) Supongamos que el mximo no se alcanza en los extremos, luego por el teorema de Weiestrassc (a, b) que maximiza af . Adems, dado quef (a), f (b) 0 x I. Suponga que ecxf (x) es convexa en Ipara cada c R. Muestre que log f (x) es convexa en I.P5. Seaf : Rn+mR una funcin convexa. Considere la funcin F : RnR dada por:F(x) = nfuU f (x, u)Donde U Rmes un conjunto convexo no vaco tal que F(x) > x Rn. Muestre que Fesconvexa.Indicacin: Muestre que no puede existir un [0, 1], x1, x2 Rny u1, u2 U tales queF(x1 +(1)x2) > f (x1, u1) +(1) f (x2, u2)P6. Considere la funcinf : R (, +] denida por:f (x) :=___0 si x [1, 1][x[ 1 si x [2, 1) (1, 2]+ si x (, 2) (2, )Demuestre que: f (x) =___0 si x (1, 1)[1, 0] si x =1[0, 1] si x = 11 si x (2, 1)1 si x (1, 2)(, 1] si x =2[1, +) si x = 2/ 0 si x (, 2) (2, )14P7. Sea S Rn, un conjunto convexo y seanf1, . . . , fk : S R, funciones convexas y diferenciables.Sean ademsf (x) = m axf1(x), . . . , fk(x) y x S.Si se dene I =i = 1, . . . , k/ f ( x) = fi( x) entonces se cumple f ( x) =iIifi( x) / i 0, i I,iIi = 115Captulo 2Caracterizacin de Optimalidad2.1. Optimizacin con Restricciones2.1.1. Problemas ResueltosP1. Sea(P) mn 3x +y z2s.a. x +y +z 0x +2y +z2= 0a) Escriba las ecuaciones de KKT para (P).b) Encuentre la(s) solucin(ones) ptima(s) de (P) usando (a).Solucin:a) Imponiendo las condiciones se obtiene3+u = 0 (2.1.1)1+u+2 = 0 (2.1.2)2z +u+2z = 0 (2.1.3)u(x +y +z) = 0 (2.1.4)x +2y +z2= 0 (2.1.5)u 0 (2.1.6) R (2.1.7)b) De (2.1.1) y (2.1.2) se tiene que u =53 y =43. Luego de (2.1.4) necesariamente x+y+z =0.De (2.1.3) se tiene que z =514 y de (2.1.5) se concluye que x = 115588ey = 95588 .P2. Considere(P) mn f (x)s.a. gi(x) 0, i = 1, . . . , mSea x Rnun mnimo local de (P). Sea I = i / gi( x) =0. Suponga que f , giC1(Rn) i =1, ..., m.Pruebe que F0G = / 0, dondeF0 =d : f ( x)Td < 0G =d : gi( x)Td 0, i I16Solucin:Por contradiccin, supongamos que d F0G. Luego como x es un mnimo local, satisface lascondiciones de KKT, esto es, u1, ..., um 0 tales quef ( x) +iIuigi( x) = 0multiplicando la ecuacin anterior por dTse tienef ( x)Td +iIuigi( x)Td = 0 =f ( x)Td =iIuigi( x)Td.Esto no puede ser, pues el lado izquierdo de la ecuacin es< 0, sin embargo, el lado derecho 0pues es el opuesto a una combinacin lineal positiva de nmeros negativos. Finalmente F0G = / 0.P3. a) Sea x0 Rn, A Mmn(R) y b Rm. Considere el siguiente problema(P) mn12|x x0|2s.a. Ax bMuestre que los multiplicadores de KKT deben satisfacer:uTAATu = uT(Ax0b)u 0u Rmb) Resuelvamn12(x2+y2+z2)s.a. x +y +z 3Solucin:a) Sea x/ = x x0 y b/ = bAx0, entonces (P) se transforma en(P/) mn12|x/|2s.a. eTi (Ax/b/) 0, i = 1, ..., mDondeloseieseli-simovectorcannicode Rm. Six/essolucinde(P/)entoncesdebecumplir las condiciones de KKT y comof (x/) = x/gi(x/) = ATeii = 1, ..., mSe tiene que u1, ..., um 0 tales quex/+mi=1uiATei = 0ui(eTi Ax/b/i) = 0 i = 1, . . . , mDeniendo u = (u1, ..., um) Rm+ las ecuaciones anteriores quedan como (sumando sobre i enla segunda)x/+ATu = 0uT(Ax/b/) = 0u 017despejando x/ de la primera ecuacin y reemplazando en la segunda quedauTAATu =uTb/ = uT(Ax0b)que era lo pedido.b) Consideremos A = [111], b =3 y x0 = (0, 0, 0)T. Luego, por parte (a), si el problema tienesolucin el multiplicador de KKT asociado a sta debe cumplir:uTAATu =b =3u2= 3 (pues AAT= 3).Luego u = 1 y por la parte anterior se tena que x/ = ATu = [1, 1, 1]. Luego la solucin delproblema es x = y = z =1.P4. La funcin de Cobb-Douglas es muy utilizada en Economa para representar la relacin entre losinputs y los outputs de una rma. Toma la forma Y= ALK, donde Yrepresenta los outputs, Lel trabajo y K el capital. Esta formulacin puede ser aplicada a la utilidad y toma la forma u(x) =x11 xnn, donde los exponentes son positivos y suman 1. Considere el problema de maximizacinde la utilidad:m axxy1p1x + p2y = wx, y 0donde p1, p2 > 0 son los precios y w > 0 el presupuesto.a) Escriba las condiciones de KKT y encuentre una solucin de ellas, en funcin de p1, p2, w y .b) Se puede decir que esta solucin es ptima para el problema original? Justique.c) Encuentre el multiplicador , en funcin de p1, p2, w y .Solucin:a) Notemos primero que el problema se puede escribir como un problema de minimizacinmnxy1p1x + p2y = wx, y 0Adems como la funcin es continua y el conjunto de restricciones es compacto (cerrado yacotado), la existencia de un mximo est asegurada. Imponiendo las condiciones de KKT alproblema se obtienex1y1+p1u1= 0(1)xy+p2u2 = 0Si u1 ,= 0 y u2 = 0 entonces x = 0 e y =wp2y la utilizadad es 0.Si u2 ,= 0 y u1 = 0 entonces y = 0 e x =wp1y la utilizadad es 0.Si u1 ,= 0 y u2 ,= 0 entonces x = 0 e y = 0, lo cual no es factible pues se tendra w = 0. Veamosel caso ms interesante, cuando u1 = 0 y u2 = 0. Las condiciones de KKT quedanx1y1+p1 = 0(1)xy+p2 = 018esto implica quex1y1p1= = (1)xyp2y = (1)p1xp2y como p1x + p2y = w, reemplazando y se obtienex = wp1ey = (1)wp2.b) Esta solucin es ptima pues entrega una utilidad positiva y si existiera otra solucin distintacuyo valor fuese mayor, necesariamente debera satisfacer las condiciones de KKT, luego almenos uno de los multiplicadores debera ser igual a cero, con lo cual la funcin objetivo sera0, lo que es una contradiccin.c) Como = x1y1p1, basta reemplazar los valores obtenidos anteriormente.P5. Resuelva utilizando las condiciones de KKTmn x2+y2s.a. x +y = 5xy 4(x 4)2+(y 2)21Solucin:Como la funcin es continua y el conjunto de restricciones es compacto, entonces est asegurada laexistencia de un punto que resuelve el problema. Notemos que el problema tambin se puede escribircomomn x2+y2x +y 5 = 04xy 0(x 4)2+(y 2)21 0Imponiendo las condiciones de KKT se tiene2x +u1y +u2(2x 8) = 0 (2.1.8)2y +u1x +u2(2y 4) = 0 (2.1.9)u1(4xy) = 0 (2.1.10)u2((x 4)2+(y 2)21) = 0 (2.1.11)x +y 5 = 0 (2.1.12)4xy 0 (2.1.13)(x 4)2+(y 2)21 0 (2.1.14)u1, u2 0 (2.1.15) R (2.1.16)Separemos el anlisis en 4 casosa) (u1 = 0, u2 = 0)de (2.1.8) y (2.1.9) se tiene que x =y =2 y de (2.1.12) se tiene que p1 = (52, 52) es el candidato,pero este punto no satisface (2.1.14), luego no puede corresponder a un mnimo.19b) (u1 ,= 0, u2 = 0)De (2.1.10) se tiene que xy =4 y de (2.1.12) se tienen 2 posibles puntos, p2 = (4, 1) y p3 = (1, 4),pero p3 no satisface (2.1.14), luego no es un punto factible y al evaluar p2 en (2.1.8) y (2.1.9)se tiene que u1 =2 lo que indica que tampoco es un punto de KKT.c) (u1 = 0, u2 ,= 0)De(2.1.11)setieneque(x 4)2+ (y 2)2= 1yde(2.1.12)setienen2posiblespuntos,p4 = (4, 1) yp5 = (3, 2), pero al evaluarp4 en (2.1.8) y (2.1.9) se tiene que u2 = 3 lo queindica que no es un punto de KKT. Sin embargo, al evaluar p5 en (2.1.8) y (2.1.9) se tiene queu2 = 1, luego p5 es un candidato a solucin.d) (u1 ,= 0, u2 ,= 0)De (2.1.10) se tiene que xy = 4, de (2.1.11) se tiene que (x 4)2+(y 2)2= 1 y de (2.1.12) setiene que la nica solucin posible es p6 = (4, 1), pero al evaluar p6 en (2.1.8) y (2.1.9) se tieneque u1 = 8+ y u2 =30+32, pero como u10 se tiene que 8 entonces u23 < 0 locual no puede ser. Luego p6 no es punto de KKT.Como est asegurada la existencia de un mnimo, este debe ser p5 = (3, 2).P6. Encuentre el mximo de la integralJ(x, y) =

yx(ete2t)dtrespecto a los lmites de integracin sujeto a la restriccin y x = c, donde c ,= 0 es una constante.Solucin:El problema se puede plantear comomn J(x, y)s.a. y x c = 0Para imponer las condiciones de KKT, que en este caso se reducen a Multiplicadores de Lagrange,necesitamos calcular J(x, y), para ello calculemos las derivadas parciales de J(x, y), apoyndonosen el teorema fundmental del clculoJx(x, y) =x_

xy(ete2t)dt_=(exe2x)Jy(x, y) =y_

yx(ete2t)dt_= eye2yLuego, imponiendo las condiciones se tiene queJx(x, y) = exe2x = 0Jy(x, y) + =ey+e2y+ = 0 Rlo que implica queexe2x= eye2y= exece2ce2xms an(1ec)ex= (1e2c)e2x= ex= 1e2c1ec> 0Luego x = ln_1e2c1ec_ey = ln_1e2c1ec_+c es la solucin.202.1.2. Problemas PropuestosP1. Resuelva utilizando las condiciones de KKTm ax x1ex2s.a. sin(x1) +x2 0x1 3P2. Considere la siguiente familia de problemas de programacin cuadrtica:min12x21 + 12x22x12x2x1 +x2 0x1, x2 0donde R. Llamaremos instancia de esta familia de problemas, a uno particular, es decir, para un R jo.a) Entregue una interpretacin geomtrica de una instancia de esta familia de problemas.b) Explique por qu una instancia particular siempre tiene una solucin ptima.c) Usando las condiciones de KKT, verique que (3/2, 5/2)Tresuelve la instancia dada por = 4d) Encuentre los valores de para los cuales las soluciones de las correspondientes instancias seencuentran en la frontera de la regin factible. Encuentre tambin los ptimos de estas instanciasy los multiplicadore de KKT asociados.e) Con las mismas condiciones de la parte anterior, compare el valor del multiplicador de KKTasociado a la restriccin x1 +x2 0 y la derivada del valor ptimo de la funcin objetivocon respecto a .f ) Cul es la solucin ptima para una instancia arbitraria de esta familia de problemas, tal quesea alcanzada en un punto al interior de la regin factible?P3. Seanf , gi, hj C1i = 1, . . . , m j = 1, . . . , l. Dados u Rm, u 0, v Rl, considere el problema(P/) mn f (x) +mi=1uigi(x) +lj=1vjhj(x)s.a. x RnProbar que si x es solucin de (P/) entonces tambin es solucin del problema(P) mn f (x)s.a. gi(x) gi( x) i I := i / ui > 0hj(x) = hj( x) j = 1, . . . , mP4. Sea P2 el espacio vectorial de los polinomios a valores reales de grado menor igual a 2.Consideremos la funcin J : P2 R denida porJ( f ) =

10f (x)2dxSea Q = f P2 : f (1) = 1. Se sabe que J alcanza un mnimo sobre Q.Nuestro objetivo es encontrar dicho mnimo, para ello proceda de la siguiente forma:21a) Seaf (x) P2, es decir, f (x) = ax2+bx +c cona, b, c R. Pruebe que existe G : R3Rtal que G(a, b, c) = J( f ). Adems pruebe quef Q si y slo si a+b+c = 1.b) Resuelva el problemamnG(a, b, c) s.a. a+b+c = 1c) Encuentref P2 tal que J( f) J( f ) f P2. Concluya.P5. Una caja rectangular est situada en el primer octante como se muestra en la gura, con una de susesquinas en el origen y con las tres caras adyacentes a los planos formados por los ejes coordenados.El punto opuesto P = (x, y, z) est restringido a la supercie del paraboloide de ecuacin x2+y2+z =1. Determine las coordenadas de P para que la caja sea de volumen mximo, para ello:a) Pruebe que el problema se puede escribir como maximizarf (x, y) =xyx3yxy3, y determinelos punto crticos def que caen en el primer cuadrante (x > 0, y > 0). Adems determine lanaturaleza de dicho(s) punto(s) crtico(s). Determine P.b) En vez de sustituir z, uno tambin podra utilizar Multiplicadores de Lagrange para maximizarel volumen V = xyz con la misma restriccin. Resuelva y compare con su solucin anterior.P6. (Programacin Cuadrtica)Sea A Mnn(R) simtrica, C Mmn(R) de rango m, b Rny d Rm.Suponga quevTAv > 0 v Ker C =u Rn: Cu = 0.Considere el siguiente problema(Q) mn12xTAx +bTxs.a. Cx = da) Muestre que la matrix P es invertible, dondeP =_A CTC 0_.b) Escriba las condiciones de KKT del problema y muestre que tienen solucin nica.c) Si A es denida positiva, encuentre explcitamente la solucin de (Q).22Captulo 3Programacin Lineal3.1. Algoritmo Simplex3.1.1. Problemas ResueltosP1. Resolver usando fase 1 y fase 2 de simplex el problema(P)___min 3x1 +x2 +9x3 +x4s.a. x1 +2x3 +x4 = 4x2 +x3x4 = 2xi 0Solucin: Se aplica la fase 1 de simplex:(Pa)___min x5 +x6s.a. x1 +2x3 +x4 +x5 = 4x2 +x3x4 +x6 = 2xi 0Notando queA =_1 0 2 1 1 00 1 1 1 0 1_Se escogen x5, x6 en la base, luego B = I y por lo tanto B1= I, B1N = N, B1b = b.El cuadro inicial es:1 1 3 0 0 0 61 0 2 1 1 0 40 1 1 1 0 1 2

1 2 0 3 0 3 01 2 0 3 1 2 00 1 1 1 0 1 2

0 0 0 0 1 1 01 2 0 3 1 2 00 1 1 1 0 1 2A partir de la tabla nal, se escoge B como la submatriz de A formada con las columnas de x1 y x3.23Fase II:B =_1 20 1_y de la tabla nal de fase 1 se observa que:B1N =_ 2 31 1_, B1b =_02_Adems se tiene:CTB = (3, 9) CTBB1b =(3, 9)_02_=18CTN = (1, 1) CNT= (1, 1) (3, 9)_ 2 31 1_= (2, 1)El cuadro inicial es:0 2 0 1 181 2 0 3 00 1 1 1 2

0 0 2 1 141 0 2 1 40 1 1 1 2

1 0 4 0 101 0 2 1 41 1 3 0 6por lo tanto x = (0, 6, 0, 4) con z = 10.P2. Una empresa produce espirales, corbatitas y fetuccinis. La produccin se basa en 2 recursos princi-pales, R1 y R2 y que son limitados. Producir corbatitas aumenta en 2 unidades la disponibilidad de R1,mientras que producir espirales aumenta en 1 unidad la disponibilidad del R2, por otro lado producirfetuccinis y espirales disminuye en 2 y 1 unidades respectivamente la disponibilidad de R1, mientrasque producir corbatitas y fetuccinis disminuye en 3 y 1 unidades respectivamente la disponibilidad deR2. Si inicialmente hay una disponibilidad de 10 unidades de R1 y 20 unidades de R2 y los precios enel mercado de corbatitas, fetuccinis y espirales son de 3, 7 y 2 respectivamente, plantee el problemaque resuelve la empresa para planicar su produccin y obtenga la cantidad que corbatitas, fetuccinisy espirales que produce.Solucin: Sea x1 = Cantidad de corbatitas, x2 = Cantidad de fetuccinis, x3 = Cantidad de espirales.El problema que resuelve la empresa es:(P)___min 3x17x22x3s.a. 2x2 +x310+2x13x1 +x220+x3x1, x2, x30

___min 3x17x22x3 +0s1 +0s2s.a. 2x1 +2x2 +x3 +s1= 103x1 +x2x3 +s2= 20x1, x2, x3, s1, s20SeanB =_1 00 1_, N =_ 2 2 13 1 1_24AsCBT= (0, 0), CNT= (3, 7, 2), CNT= (3, 7, 2)Entonces el cuadro inicial es:3 7 2 0 0 02 2 1 1 0 103 1 1 0 1 20

10 032720 351 112120 54 0 32121 15

0 0 94945214520 11838143541 0 381814154

0 18 0 9 7 2300 8 1 3 2 701 3 0 1 1 30Por lo tanto la solucin de (P) es x1 = 30, x2 = 0, x3 = 70P3. Llevar el siguiente problema a su forma cannicamn x1 +[x2[ +x3s.a. x1 +x2 22x1 +x3 = 0Solucin: Notar que [x2[ = m axx2, x2 luego la funcin objetivo puede escribirse comom axx1 +x2 +x3, x1x2 +x3y el problema se transforma enmn m axx1 +x2 +x3, x1x2 +x3s.a. x1 +x2 22x1 +x3 = 0y este problema a su vez puede escribirse comomn x4s.a. x1 +x2 22x1 +x3 = 0x1 +x2 +x3 x4x1x2 +x3 x4Agregando variables de holgura se obtienemn x4s.a. x1 +x2 +x5 = 22x1 +x3 = 0x1 +x2 +x3x4 +x6 = 0x1x2 +x3x4 +x7 = 0x5, x6, x7 0y nalmente desdoblando las variables irrestrictas, es decir, escribiendo xi = yizicon yi, zi 0i = 1, ..., 4, se tienemn y4z4s.a. y1z1 +y2z2 +x5 = 22y12z1 +y3z3 = 0y1z1 +y2z2 +y3z3y4 +z4 +x6 = 0y1z1y2 +z2 +y3z3y4 +z4 +x7 = 0y1, ...y4, z1, ..., z4, x5, x6x7 025P4. Resolver con Simplex(P)___minx1 +1x2 +2s.a. x1 +x21x1, x20Solucin: Sean z =1x2 +2, y1 =x1x2 +2e y2 =x2x2 +2. Se cumple la relacin 2z +y2 = 1. Luego(P) es equivalente a (P/)_P/____min y1 +zs.a. y1 +y2z2z +y2= 1y1, y2, z 0Por lo tanto se resuelve (P/), agregando variables de holgura:_P/____min y1 +zs.a. y1 +y2z +s1= 02z +y2= 1y1, y2, z, s10LuegoA =_1 1 1 10 1 2 0_, b =_01_, CT= (1, 0, 1, 0)Escogiendo a z y a s1 en la base se tiene:B =_ 1 12 0_, N =_1 10 1_asCBT= (1, 0), CNT= (1, 0)B1=__012112__, B1N =__012132__B1b =_12,12_, CBTB1b =(1, 0)___1212___=12Luego1 120 0 120121 0121 320 112

430 01313130 1 1313231 0231326Por lo tanto la solucin de (P/) es:y1 = 0, y2 = 13, z = 13, s1 = 0Reemplazando en las variables de (P) se tiene que la solucin es:x1 = 0, x2 = 1, z = 13P5. Resolver con Simplex(P)___min f (x1, x2) = m axx12, x2s.a. x1 +[x2[ 1x10Solucin: Equivalentemente(P)___mn m axx12, x2s.a. x21x1x2x11x10Sea x2 = uv, con u, v 0. (P) es equivalente a:(P)___mn m axx12, uvs.a. uv +x11x1u+v 1x1, u, v 0A la vez el problema es equivalente a:(P)___mn zs.a. uv +x11x1u+v 1x12 zuv zx1, u, v 0Finalmente el problema es equivalente a:(P)___mn r ss.a. uv +x11x1u+v 1x1r +s 2uv r +s 0x1, u, v, r, s 027Agregando variables de holgura:(P)___mn r ss.a. uv +x1 +s1= 1x1u+v +s2= 1x1r +s +s3= 2uv r +s +s4= 0x1, u, v, r, s, s1, s2, s3, s40Escogiendo B = I, es fcil obtener el cuadro inicial0 0 0 1 1 0 0 0 0 01 1 1 0 0 1 0 0 0 11 1 1 0 0 0 1 0 0 11 0 0 1 1 0 0 1 0 20 1 1 1 1 0 0 0 1 0

0 1 1 0 0 0 0 0 1 01 1 1 0 0 1 0 0 0 11 1 1 0 0 0 1 0 0 11 1 1 0 0 0 0 1 1 20 1 1 1 1 0 0 0 1 0

1 0 0 0 0 0 1 0 1 12 0 0 0 0 1 1 0 0 21 1 1 0 0 0 1 0 0 10 0 0 0 0 0 1 1 1 11 0 0 1 1 0 1 0 1 1Luego, la solucin es:x1 = 0, w = 0, v = 1, r = 0, s = 1En el problema originalx2 = uv =1, z =1P6. Suponga que estamos resolviendo el problema:mn cTxs.a Ax = bx 0Y que llegamos a la siguiente tabla de Fase II:(z) 0 1 0 c1140 1 1 0 a1b10 0 2 1 a2b2a) Identique la solucin en curso y diga condiciones para que sea factible.b) Diga condiciones para que la solucin en curso sea ptima.c) Diga condiciones que aseguren que la solucin ptima es la nica solucin factible ptima.d) Diga condiciones que garanticen que el valor objetivo es no acotado.e) Diga condiciones para que la solucin ptima sea degenerada.f ) Asumiendo las condiciones en (a), de todas las condiciones bajo las cuales usted hara un pivoteen el elemento a1.Solucin:28a) La solucin en curso es (b1, b2) que es factible si b1 0b2 0b) La solucin en curso es ptima si b1 0, b2 0c1 0c) La solucin ptima es nica si b1 0, b2 0 y c1 > 0 (notar que si c1 = 0 es posible que sepueda hacer ingresar x4 a la base sin cambiar el valor de la funcin objetivo).d) El problema es no acotado si c < 0, a1 < 0 y a2 < 0.e) La solucin ptima es degenerada si se cumple (b) y (b1 = 0b2 = 0)f ) Se pivotea en a1 si c1 < 0 y tambin se cumple uno de los dos casos:1) a1 > 0 , a2 > 0 , b1a1< b2a22) a1 > 0 , a2 0293.1.2. Problemas PropuestosP1. Un productor de electricidad debe planicar su produccin horaria de energa para maximizar susbenecios por venta de la misma en un horizonte de 2 horas. Formule y resuelva el PPL que consisteen maximizar los benecios del productor siSe producen 5 unidades de energa antes del periodo de planicacin.Los precios horarios de la energa son 6 y 2 unidades monetarias.La energa mnima que se puede producir en cada hora es 0 y la mxima 10 unidades.Las producciones de energa en dos horas consecutivas no pueden diferir ms de 4 unidades.El coste de produccin es 3 unidades monetarias por unidad de energa.P2. Considere el problema fraccional:(F) mnx26x1 +x2 +2x1 +x2 3x1 +2x2 12x1, x2 0a) Deniendo y =xx1+x2+2 R2, y z convenientemente, pruebe que (F) es equivalente al problemalineal:(P)min y26zy1 +y23z 0y1 +2y212z 0y1 +y2 +2z = 1y1, y2, z 0b) Resuelva usando Simplex, verique su solucin resolviendo grcamente el problema (P) ynalmente deduzca una solucin de (F).P3. Considere el problema(P) mn [x1[ x2s.a. x1 +[x2[ 12[x1[ [x2[ 2Transforme el problema a un PPL y resuelva usando Simplex.P4. Considere el siguiente PPL(P) m ax x1 +2x2s.a. x1 +x21x11x1, x20Escriba el problema en su forma estndar. Muestre que el mtodo de Simplex entra en un procesocclico innito si escoge como base inicial las variables (x1, x2). Observe cmo la desigualdad x11es rebundante. Si se elimina esta restriccin, se detiene el mtodo?, i.e. encuentra solucin?P5. Considere el problema:(P)mn Z() = x1 +x330x1x2 +x3= 1x1 +x3 +x5= 2x1x3 +x4= 3x1, x2, x3, x4, x5 0a) Resulvalo usando Simplex, indicando el conjunto solucin:() =x Rn/x es solucion de (P)para cada [1, 1].b) Graque Z() y encuentre su valor ptimo donde [1, 1].P6. Considere el problema de Programacin Lineal:(P) min x12x24x3+2x4x12x3+x4= 4x1+x2+x3x4= 8x1, x2, x3, x4 0a) Usando Fase I del algoritmo Simplex, determine un punto extremo del poliedro factible de (P).b) A partir de la base obtenida en (a), resuelva (P) usando Fase II del algoritmo Simplex.P7. Considere el cuadro, (correspondiente a un problema de programacin lineal cannico)- 2 0 0 0 10-1 1 0 0 4 -4 0 1 0 1 3 0 0 1 Indique en qu condiciones:(a) La solucin en curso en ptima y es nica (Cules?).(b) El problema es no acotado (Cul es la direccin extrema correspondiente?).(c) La solucin en curso es ptima pero no es nica (indique el conjunto solucin).(d) La solucin en curso es factible, pero no es ptima (realice, a partir de ella, una iteracin ms,usando datos adecuados).(e) El problema no tiene solucin factible.31Captulo 4Dualidad en Programacin Lineal4.1. Dualidad y Anlisis de Sensibilidad4.1.1. Problemas ResueltosP1. Considere el siguiente problema de programacin lineal:(P) mn 2x1 +3x2 +4x3s.a. x1 +2x2 +x332x1x2 +3x34x1, x2, x30a) Escriba el problema Dual asociado.b) Resuelva el problema primal, usando el algoritmo de simplex dual.Solucin:a) Notemos que el problema primal (P) es de la forma(P) mn ctxs.a. Ax bx 0luego su dual es de la forma(D) m ax btys.a. Aty cy 0(D) m ax 3y1 +4y2s.a. y1 +2y222y1y23y1 +3y24y1, y20b) El problema se puede escribir en forma cannica como(P) mn 2x1 +3x2 +4x3s.a. x12x2x3 +x4=32x1 +x23x3 +x5=4x1, x2, x3, x4, x50tomamos como base (x4, x5) luego B = I y B1= I, luego el cuadro inicial de Simplex queda322 3 4 0 0 0-1 -2 -1 1 0 -3-2 1 -3 0 1 -4 luego x1 entra a la base y sale x5, la nueva tabla es0 4 1 0 1 -40 -5/2 -1 1 0 -1 1 1 -3 0 1 2luego x2 entra a la base y sale x4, la nueva tabla y la denitiva es0 0 9/5 8/5 1/5 -28/50 1 -1/5 -2/5 1/5 2/51 0 7/5 -1/5 -2/5 11/5Finalmente la solucin es x1 = 11/5 y x2 = 2/5 y el valor ptimo z = 28/5.P2. Considere n 2 y el siguiente problema de P.L.(P)___mn x1+ 2x2++ nxns.a. x11x1+ x22.........x1+ x2++ xnnx1, x2, . . . , xn0a) Determine el dual (D) de (P)b) Vericar que se cumple el teorema de dualidad fuerte.c) Probar que y factible de (D), se tiene que yk +yk+1 +... +yn < k k 2, ..., nd) Deducir del teorema de holgura complementaria el ptimo de (P)Solucin:a) Notemos que el problema primal (P) es de la forma(P) mn ctxs.a. Ax bx 0luego su dual es(D) m ax y1+ 2y2+ ... + nyns.a. y1+ y2+ ... + yn1y2+ ... + yn2......ynny1, y2, ... , yn0b) Notemos que (P) y (D) son factibles pues x = (1, ..., 1) y y = (0, ..., 0) satisfacen las restricciones,respectivamente. Y como por dualidad dbil se tiene que bty ctx, entonces ambos problemasson acotados y sus valores ptimos deben coincidir.33c) Sea y = (y1, ..., yk) factible de (D) y k 2, ..., n, luegoyk +yk+1 +... +yn = y1 +y2 +... +yn 1 < k.d) Sea x ptimo de (P) y y ptimo de (D), por Holgura complementaria se sabe que en el ptimo xk(c At y)k = 0 k = 1, ..., n. Como y es ptimo de (D), es en particular factible, luego porparte anterior (c At y)k = k yk +yk+1 +... +yn > 0 si k 2, ..., n, esto implica que xk = 0si k 2, ..., n. Finalmente el problema dual se tranforma en(P)mn x1s.a. x11x12...x1nx1 0cuya solucin es x1 = n. Luego la solucin de (P) es x = (n, 0, ..., 0).P3. Una orista sabe hacer solo 2 tipos distintos de arreglos orales (x1 y x2) para los cuales dispone 3tipos distintos de ores: rosas, tulipanes e ibizcos. Los requerimientos de ores para cada arreglo, ladisponibilidad de ores y los precios de cada arreglo vienen dados por:FLORES x1x2DISPONIBILIDADRosas 3 1 300Tulipanes 1 1 140Ibizcos 1 3 300PRECIO 2000 1000 a) Plantee el problema al que se enfrenta la orista para optimizar su produccin.b) Calcule el dual del problema. Qu representa?c) Si el ptimo del problema primal es x1 = 80, x2 = 60, encuentre el ptimo del problema dual.Solucin:a)m ax 2000x1 +1000x2s.a. 3x1 +x2300x1 +x2140x1 +3x2300x1, x20b)mn300y1 +140y2 +300y3s.a. 3y1 +y2 +y32000y1 +y2 +y31000y1 +y2 +3y3300y1, y2, y30El dual representa el problema de un agente externo que quiere saber que precio unitario ofrecerpor cada una de las ores si quiere comprarle todas las ores a la orista. As y1, y2 e y3 son losprecios asociados a las rosas, tulipanes e ibizcos.34c) Por el teorema de holgura complementaria se tiene:1) (3 x1 + x2300) y1 = 02) ( x1 + x2140) y2 = 03) ( x1 +3 x2300) y3 = 04) (20003 y1 y2 y3) x1 = 05) (1000 y1 y3 y3) x2 = 0Como x1 = 80 y x2 = 60, se tiene que:1) y1 R2) y2 R3) y3 = 04) 3 y1 + y2 = 20005) y1 + y2 = 1000Resolviendo el sistema: y1 = 500, y2 = 500, y3 = 0Notar que el valor ptimo de ambos problemas es 220000.Cmo se interpreta esto? La orista vender rozas y tulipanes a un precio de $500 cada una yentregar como oferta los ibizcos gratis, pero esto solo si se vende todo como un paquete. Estotoma sentido pues si vende todas las rosas y tulipanes (dado que solo sabe hacer los arreglosorales descritos) no podr sacarle provecho alguno a los ibizcos.P4. Dado el siguiente PPL(P) mn 8x19x2 +12x3 +4x4 +11x5s.a. 2x13x2 +4x3 +x4 +3x5 1x1 +7x2 +3x32x4 +x5 15x1 +4x26x3 +2x4 +3x5 22x1, x2, x3, x4, x5 0Escribaeldualdeesteproblema. Determinesielpuntox = (0, 2, 0, 7, 0)essolucinptimadelproblema.Solucin: El dual del problema es(D) m ax y1 +y2 +22y3s.a. 2y1 +y2 +5y3 83y1 +7y2 +4y3 94y1 +3y26y3 12y12y2 +2y3 43y1 +y2 +3y3 11y1, y2, y3 0Es fcil ver que el punto es factible de (P). Como la segunda restriccin de (P), no se alcanza parael punto dado, pues x1 +7x2 +3x32x4 +x5 = 0 < 1, por el teorema de holgura complementaria setiene que la variable del dual asociada a esta restriccin, y2, es 0 y que la 2 y 4 restriccin del dualse alcanza con igualdad, pues x2, x4 > 0. Luego con esto se tiene3y1 +4y3 =9y12y3 = 435Esto implica que y1 =175e y3 =310, sin embargo, las variables duales debes ser negativas o cero, luegox no puede ser ptimo pues no existe una variable dual que satisfaga las condiciones del teorema deholgura complementaria.P5. Sean A Mnm(R), b Rmy c, p, q Rn, tal que p q. Encuentre el dual de(P) mn ctxs.a. Ax = bp x qPruebe que el dual siempre posee una solucin factible.Solucin: El problema puede reescribirse como(P) mn ctxs.a. Ax = b (1)x q (2)x p (3)x Rn(4)Notemos que el problema tiene m+n +n restricciones, pues (1) aporta m igualdades, (2) aporta ndesigualdades () y (3) aporta n desigualdades (), entonces las variables del dual y pertenecen aRm+2n, luego podemos suponer que tal variable es de la forma y = (u, v, w) donde u Rmy v, w Rn,tales que u est asociada a la restriccin (1), v a la restriccin (2) y w a la restriccin (3). Utilizandola tabla de transformacin de problemas primales-duales se tiene que el dual de (P) es(D) m ax btu+qtv + ptws.a. Atu+v +w = cu Rmv 0w 0Adems como ci R i = 1, ..., n, luego ri, si0 tal que ci = risi. Luego tomando u = 0, wi = riy vi = si i = 1, ..., n se tiene que Atu+v +w = c, u Rm, v 0 y w 0, con lo cual el se puedeconcluir que el dual del (P) siempre es factible.P6. Considere el problema lineal:(P) mn z = 5x13x2s.a. 2x1x2 +4x3 4x1 +x2 +2x3 52x1x2 +x3 1x1, x2, x3 0Dado el siguiente cuadro ptimo:0 0 0231310310 1 0 -13230 21 0 0 -1313-2310 0 1130131a) Escriba B, matriz de base (ptima) y B1.36b) Si z cambia a z/ = 5x13x2 +2x3, cambia la solucin ptima?c) Si b cambia a b/ = (5, 4, 1) (en el problema original), cambia la solucin ptima?d) Si se introduce una nueva actividad u, cuyo costo unitario es 4 y cuya columna correspondientees Nu = (1, 3, 1), cambia la solucin ptima?e) Si se agrega (al problema original) la restriccin x1 +x2 +x3 5 cambia la solucin ptima?Solucin:a) El problema se puede escribir en forma cannica como(P) mn 5x13x2s.a. 2x1x2 +4x3 +x4= 4x1 +x2 +2x3 +x5= 52x1 +x2x3 +x6= 1x1, x2, x3, x4, x5, x6 0Recordemos que el cuadro nal de simplex es de la forma0 ctNctBB1N ctBB1bI B1N B1bLuego la base est formada por (x2, x1, x3). EntoncesB =__1 2 41 1 21 2 1__Notar que N, la submatriz asociada a las variables no bsicas, es la identidad, luego B1N =B1,entonces del cuado nal de simplex tenemos queB1=__1323013132313013__b) Comoslocambiact=_3 5 0_a(c/)t=_3 5 2_hayquevericarsiloscostosreducidos siguen siendo positivos, calculemos ctN = ctNctBB1N =_0 1/3 8/3_0Luego la base no cambia y por lo tanto la solucin tampoco.c) Como lo nico que cambia de el problema original es si B1b 0 entonces la base se mantiene(si no hay que iterar con simplex dual). Con un simple clculo, se puede ver queB1b =__112__ 0.Luego la base no cambia y la solucin sigue siendo la misma.d) Si se introduce una nueva actividad xu, para ver si esta afecta en algo el resultado previamenteobtenido debemos analizar el costo reducido asociado a esta variable, es decir ctu = ctuctBB1Nu = 1730Luego la base no cambia y la solucin sigue siendo la misma.37e) Cuando se agrega una nueva restriccin de la forma dtx d0, el cuadro nal de simplex es dela forma0 ctNctBB1N 0 ctBB1bI B1N 0 B1b0 dtNdtBB1N 1 d0dtBB1bpero d0dtBB1b =1 0, luego la base anterior no es ptima por lo que debemos iterar consimplex dual para encontrar una nueva base que sea ptima. El nuevo cuadro de Simplex queda0 0 023131030 10 1 0 -13230 0 21 0 0 -1313-230 10 0 1130130 10 0 0 -131 -131 -1Luego x7 sale de la base y entra x4, quedando0 0 0 073832 -10 1 0 0 -1313-1 31 0 0 0 -23-13-1 20 0 1 0 1 0 1 00 0 0 1 -3 1 -3 3Finalmente la solucin es x1 = 2, x2 = 3, x3 = 0, x4 = 3, x5 = 0, x6 = 0, x7 = 0.384.1.2. Problemas PropuestosP1. Resulvase el siguiente problema:(P) m ax 240x1 +104x2 +60x3 +19x4s.a. 20x1 +9x2 +6x3 +x42010x1 +4x2 +2x3 +x410x1, x2, x3, x30Encuentre el dual de (P) y resulvalo usando.P2. Considere los problemas, duales entre s(P) min cTxAx bx 0(D) max bTyATy cy 0a) Si llamamos u 0 al vector de variables de holgura de (P) y s 0 al vector de variables deholgura de (D), demuestre que (x, u) e (y, s) respectivamente factibles, son ptimos s y slo sxTs = 0 y uTy = 0b) SeaL(x, y) = cTx yT(Ax b)funcin de IRnIRmIR.Demuestre que una condicin necesaria y suciente para que x IRn, y IRmsean solucionesptimas respectivas de (P) y (D) es que se cumplaL(x, y) L(x, y) L(x, y) x 0, y 0P3. Considere el juego en que el jugador X puede seleccionar cualquiera de m movimientos y el jugadorY puede elegir cualquiera de n movimientos. Si X selecciona i e Y seleccionaj, entonces X gana unacantidad ai j a Y.El juego se repite muchas veces, lo cual podemos interpretar como que los jugadores desarrollan unaestrategia mixta, en la que los distintos movimientos se hacen de acuerdo con probabilidades repre-sentadas por las componentes del vector x = (x1, x2, ..., xm)T, donde xi0, i =1, 2, ..., my mi=1xi =1,en el caso del jugador X. Por su parte, Ydesarrolla otra estrategia mixta y = (y1, y2, ..., yn)T, dondeyi 0, i = 1, 2, ..., n y ni=1yi = 1. Entonces el pago promedio a X es P(x, y) = xtAy.i) Suponga que X elige el vector x como solucin del programa linealmax s.a mi=1xi= 1mi=1xiai j j = 1, ..., nxi 0 i = 1, ..., mPruebe que a Xse le garantiza una ganancia de al menos , independientemente del y selec-cionado por Y.39ii) Demuestre que el dual del problema anterior es:min s.a nj=1yj= 1nj=1yjai j i = 1, ..., myj 0 j = 1, ..., niii) Demuestre que max = min (este valor se llama valor del juego).iv) Considere el juego del emparejamieno; cada jugador elige cara o cruz. Luego se muestran laselecciones. Si las elecciones se corresponden, X gana 1 unidad a Y, si no Ygana 1 unidad a X.Encuentre el valor del juego y las estrategias mixtas optimales.P4. Considere un problema PL de maximizacin con todas las restricciones del tipo "menor o igual ()"tal que la tabla ptima del Simplex es:x1x2x3x4x5 z0 0 1/4 1/4 0 50 1 1/2 -1/2 0 21 0 -1/8 3/8 0 3/20 0 1 -2 1 4donde x3, x4, x5 son variables de holgura. Supongamos que se ha decidido incrementar el lado derechode una de las restricciones. Cul recomendara Ud. para ello y por qu? Cul es el mayor incrementoposible en ese caso? Encontrar el correspondiente nuevo valor ptimo de la funcin objetivo.P5. Considere:(P)m ax 9x2 +x32x5x65x2 +50x3 +x4 +x5= 10x115x2 +2x3= 2x2 +x3 +x5 +x6= 6x1, x2, x3, x4, x5, x6 0a) Escriba el problema dual (D) correspondiente.b) Resuelva (P) e indique la solucin de (D) (o viceversa).c) Resuelva (P), pero suponiendo que el coeciente de x5 en la funcin objetivo es c5 =1 (en lugarde -2).d) Suponga que al problema (P) (original) se le modica el recurso b1 de manera que b1 = 10Para que valores de la base ptima no cambia ?.e) Qu sucede si al problema (P) se le agrega la variable x7, con costo c7 = 1 y vector columna(0, 1, 0)t?.f ) Que sucede si a (P) se le agrega la restriccin x1 +x2 +x3 +x4 +x5 +x6 ? Analice enfuncin de .P6. Considere el siguiente problema (P)(P)mn 2x1 +x2x340x1 +x2 +x3 6x1 +2x2 4x1, x2, x3 0a) Resuelva (P) por el mtodo simplex, dando adems la solucin del problema dual.b) Suponga que los costos c2 = 1 y c3 = 1 se modican a c2 = 8 y c3 = 10 Determine si labase ptima cambia. Encuentre una nueva solucin de los problemas Primal y Dual.c) Repita lo mismo de la parte anterior con c2 =3 y c3 = 1.d) Suponga que el lado derecho de (P) se modica abt= (3, 4). Determine si la base ptimacambia. Encuentre la nueva solucin ptima de los problemas Primal y Dual.e) Suponga que en (P), la segunda columna de la matriz A (es decir, a2t= (1, 2)) se cambia pora2t= (2, 5). Determine si la base ptima cambia. Encuentre la nueva solucin ptima de losproblemas Primal y Dual.P7. Considere el problema de Programacin Lineal:(P)mn x12x24x3+2x4x12x3+x4= 4x1+x2+x3x4= 8x1, x2, x3, x4 0a) Imponiendo simultneamente que la variable x1 pertenece a la base y la variable x3 est fuerade ella, encuentre una solucin bsica factible del problema.b) A partir de la base obtenida en (a), resuelva (P) usando la Fase II del algoritmo Simplex.c) Determine la solucin ptima del problema dual de (P).d) Si se agrega la restriccin: x1 +x2 +x35 al problema (P), determine la nueva solucion ptimao justique por qu no existe.e) Determine la regin de los recursos (coecientes del lado derecho del sistema) para la cual labase encontrada en (b) es ptima para (P).f ) Determine el rango de variacin del costo de x1 de manera que la base ptima encontrada en (b)no cambie.41Captulo 5Modelos y alg. para ujos en redes5.1. Problemas de transporte y de ujo a costo mnimo5.1.1. Problemas ResueltosP1. Considere la siguiente tabla de un problema de transporte:a) Es bsica la solucin?b) Muestre que la solucin es ptima.c) Escriba el problema de programacin lineal y su dual.Solucin:a) La solucin es la siguiente:42Como es un rbol, la solucin es bsica.b) Fijando arbitrariamente u1 = 0 se obtienen los siguientes valores para las variables duales:u1= 0v1= 9v2= 8u3= 1v3= 12u2= 0u4= 1v4= 13De esta forma los costos reducidos para las variables no-bsicas son:c13= 0c14= 0c21= 1c22= 2c24= 1c32= 2c34= 0c41= 2c42= 3Como no hay costos reducidos negativos, la solucin bsica es ptima.c) El problema de programacin lineal es:(P)___min 9x11 +8x12 +12x13 +13x14 +10x21 +10x22 +12x23 +14x24+8x31 +9x32 +11x33 +12x34 +10x41 +10x42 +11x43 +12x44s.a. x11 +x12 +x13 +x14 = 18x21 +x22 +x23 +x24 = 24x31 +x32 +x33 +x34 = 6x41 +x42 +x43 +x44 = 12x11 +x21 +x31 +x41 = 6x12 +x22 +x32 +x42 = 14x13 +x23 +x33 +x43 = 35x14 +x24 +x34 +x44 = 5xi j 0El dual de este problema es:43(D)___max 18u1 +24u2 +6u3 +12u4 +6v1 +14v2 +35v3 +5v4s.a. u1 +v1 9u1 +v2 8u1 +v3 12u1 +v4 13u2 +v1 10u2 +v2 10u2 +v3 12u2 +v4 14u3 +v1 8u3 +v2 9u3 +v3 11u3 +v4 12u4 +v1 10u4 +v2 10u4 +v3 11u4 +v4 12Lo que es lo mismo:(D)___maxni=1aiui +mj=1bjvjs.a. ui +vj ci jP2. Resolver el problema de ujo a costo mnimo de la gura donde los costos sonc13 = 8 c14 = 9 c15 = 6 c23 = 20 c24 = 11 c25 = 10Solucin:Buscamos una base factible, para ello saturamos el arco de menor costo, en este caso el arco (1,5),como an queda oferta en el nodo (1) enviamos los 5 elementos restantes al siguiente arco de menorcosto que es el arco (1,3). como ya no queda oferta que distribuir en el nodo 1 pasamos al nodo 2 yprocedemos similarmente y obtenemos la siguiente base factible44Figura 5.1: base factible inicialSea ahora u1, u2, v3, v4 y v5 la variables duales, luego imponiendo que los costos reducidos de lasvariables bsicas son 0 obtenemos el siguiente sistema:8 = u1 +v36 = u1 +v520 = u2 +v311 = u2 +v4jando u1 = 0 obtenemos que u2 = 12, v3 = 8, v4 = 1 y v5 = 6. Luego los costos reducidos de lasvariables no bsicas son c14 = 10 y c25 =8. Como c25 < 0 hacemos ingresar a la base al arco (2,5),con x25 = (0, 20] como en la guraFigura 5.2: ingresa nuevo arco a la base45Se escoge el mayor que satisface15 05 05+ 0 0___ = 5Luego el arco (2,3) sale de la base, e iteramos nuevamente calculando las variables duales, el sistemapara ellas es8 = u1 +v36 = u1 +v511 = u2 +v410 = u2 +v5jando u1 = 0 obtenemos que u2 = 4, v3 = 8, v4 = 7 y v5 = 6. Luego los costos reducidos de lasvariables no bsicas son c14 = 2 y c23 = 8. Como todos los costos reducidos son mayores o iguales a0, estamos en el ptimo.P3. Una compaa produce el mismo producto X en dos fbricas, 1 y 2. El producto se debe enviar a doscentros de demanda A y B. La fbrica 1 puede enviar un nmero ilimitado del producto a A y nada delproducto a B. La fbrica 2 slo puede enviar unidades a B, ilimitadamente. Adems se puede enviara lo ms 50 unidades independientemente desde ambas fbricas a un centro de distribucin desde elcual se pueden enviar 50 unidades a lo ms a cada centro de demanda. Los costos, oferta y demandase resumen en la siguiente tabla.PPPPPPPPPDesdeHaciaC. Dist. A B OfertaFbrica 1 3 7 - 80Fbrica 2 4 - 9 70C. Dist. 2 4Demanda 60 90Solucin:El problema corresponde al siguiente ujo:46Se elige la siguiente base inicial:Figura 5.3: Base InicialEligiendo arbitrariamente 3 = 0 y usando que para los arcos de la baseci j = ci ji +jSe obtienen los siguientes valores para las variables duales:1= 34= 45= 42= 5Los costos reducidos para las variables no bsicas son:c23= 1c34= 2Ambasvariablesseencuentranensucotainferior0porloqueseeligearbitrariamentex34paraingresar a la base.Figura 5.4: Primera IteracinLas restricciones para la cantidad transportada son:60 050 20+ 050 047Se obtiene = 30 y sale de la base la variable x13 que se encuentra en su cota superior. Se obtiene lasiguiente base:Figura 5.5: Primera IteracinEligiendo arbitrariamente 3 = 0 los valores de las variables duales son:4= 21= 55= 42= 5Los costos reducidos para las variables no bsicas son:c13= 2c23= 1Ambos costos reducidos son negativos, sin embargo la variable x13 se encuentra en su cota superiormientras que x23 se encuentra en su cota inferior. Por lo tanto x23 ingresa a la base.Figura 5.6: Segunda IteracinLas restricciones para la cantidad transportada son:50 050 20+ 070 0Se obtiene = 30 y la variable x35 (que se encuentra en su cota superior) sale de la base.48Figura 5.7: Segunda iteracinEligiendo arbitrariamente 3 = 0 los valores de las variables duales son:4= 21= 52= 45= 5Los costos reducidos para las variables no bsicas son:c13= 2c35= 1Como ambas variables se encuentran en sus cotas superiores, se cumple el criterio de optimalidad yla base obtenida es solucin.P4. Resolver el problema de transporte, usando los datos:a =___705040___ b =______60303030______C =__3 6 8 142 7 3 1112 3 1 1__Solucin:Primero, notando que:ni=1ai