Optimizacion Programacion Lineal

´ Jean Monnet Universite Saint Etienne Universidad Central del Ecuador

PROYECTO Optimizaci´on Matem´atica y M´etodos Econ´omicos Para obtener la Licenciatura en Ciencia y Tecnolog´ıas, menci´on Matem´atica Autora: Ver´onica M. Acurio V´asconez

Tutor: Dr. Julio Medina

Junio 2009 Quito - Ecuador

A Dios y a mis padres, Bertila y Franklin. Las palabras son insuficientes para retribuirles su ayuda, as´ı que solo me queda decirles GRACIAS.

Optimizaci´on Matem´atica y M´etodos Econ´omicos: Programaci´on Lineal Ver´onica M. Acurio V´asconez 3 de julio de 2009

´Indice general 1. Introducci´ on

2

2. Elementos Matem´ aticos Previos 2.1. Convexidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Conjuntos Convexos . . . . . . . . . . . . . . . . . . . 2.1.2. Funciones Convexas . . . . . . . . . . . . . . . . . . . .

4 4 4 7

3. Elementos de un Problema de Optimizaci´ on 3.1. Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8

4. Programaci´ on Lineal 4.1. El Problema . . . . . . . . . . . . . . . . . . . . . 4.2. Generaci´on de Soluciones de Punto Extremo . . . 4.3. Dualidad . . . . . . . . . . . . . . . . . . . . . . . 4.4. El M´etodo Simplex . . . . . . . . . . . . . . . . . 4.4.1. Desarrollo de una soluci´on posible m´ınima 4.4.2. Procedimiento de C´omputo . . . . . . . . 4.5. Alternativa al M´etodo Simplex . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

5. Modelizaci´ on PL y Aplicaciones Activo/Pasivo, Flujo de Caja, Fondos Compensatorios 5.1. Algunos T´erminos Financieros . . . . . . . . . . . . . . . 5.1.1. Modelar . . . . . . . . . . . . . . . . . . . . . . . 5.1.2. Resolver . . . . . . . . . . . . . . . . . . . . . . . 5.1.3. Interpretar . . . . . . . . . . . . . . . . . . . . . . 5.2. Caracter´ısticas de los Programas Lineales . . . . . . . . . 5.3. Dedicaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Sensibilidad y An´alisis de la Programaci´on Lineal . . . . 6. Conclusiones

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

10 10 19 24 29 29 33 40

. . . . . . .

41 41 42 44 50 51 52 58 59

1

Cap´ıtulo 1 Introducci´ on Los problemas de optimizaci´on son de gran importancia hoy en d´ıa, est´an presentes no solo en el campo cient´ıfico, sino tambi´en en la ingenier´ıa y los negocios. En este u ´ ltimo, la aplicaci´on de esta t´ecnica, nace de la necesidad de distribuir los recursos de tal manera que se logre obtener mayor ganancia. La Optimizaci´on Matem´atica, es entonces, una rama de las aplicaciones matem´aticas que permite encontrar soluciones robustas a problemas de diferentes clases, minimizado o maximizando funciones. En el mundo de los negocios, este tema tiene una gran importancia y aplicaci´on, puesto que del maximizar o minimizar una situaci´on generada y tomar una decisi´on acertada, dependen las ganancias o p´erdidas de una acci´on econ´omica y por tanto, las finanzas de una empresa. El presente proyecto est´a divido en cinco cap´ıtulos, incluyendo la Introducci´on. El segundo cap´ıtulo es un an´alisis previo, en el que se desarrolla la teor´ıa de la convexidad por la importancia de sus conceptos dentro de la programaci´on lineal. En el tercer cap´ıtulo se explica los elementos b´asicos de un problema de optimizaci´on y la idea del problema. El cuarto hace referencia a la Programaci´on Lineal y todo lo que esta conlleva. Las definiciones, teoremas, demostraciones y ciertos ejemplos, han sido obtenidos de la lectura de la bibliograf´ıa. Finalmente, en la u ´ ltima parte se hace una introducci´on a t´erminos financieros y econ´omicos utilizados en la optimizaci´on, espec´ıficamente en el desarrollo de portafolios, y se desarrollan dos programas lineales sencillos como aplicaci´on. Si bien en el cap´ıtulo de Programaci´on Lineal se explica el algoritmo del m´etodo simplex, para la resoluci´on de problemas lineales, los modelos 2

´ CAP´ITULO 1. INTRODUCCION aqu´ı planteados, han sido realizados usando la herramienta inform´atica Matlab 7.0, que tambi´en se explica como utilizarla. Cabe recalcar que aunque el proyecto no desarrolla un tema nuevo o novedoso, pleno de investigaci´on, si presenta una teor´ıa jam´as vista durante los tres a˜ nos de licenciatura, d´andole as´ı un significado especial dentro de mi formaci´on acad´emica.

Ver´onica M. Acurio V´asconez

3

Cap´ıtulo 2 Elementos Matem´ aticos Previos 2.1. 2.1.1.

Convexidad Conjuntos Convexos

Definici´ on 2.1.1 Sean P1 , P2 , ..., Pn ∈ Rn . Una combinaci´ on convexa de los puntos P1 , P2 , ..., Pn es un punto P = α1 P1 + α2 P2 + · · · + αn Pn P donde las αi son escalares, αi ≥ 0 y αi = 1. i=1

Definici´ on 2.1.2 Sean x y y dos puntos cualesquiera dados en un espacio vectorial. Para todo λ ∈ [0, 1] la combinaci´ on λx + (1 − λ) y se dice combinaci´on convexa de x y y. Definici´ on 2.1.3 C ⊂ Rn , es convexo si y solo si para todo par de puntos P1 y P2 en C, cualquier combinaci´ on convexa de estos puntos est´ a tambi´en en C. Propiedades: 1. Para cualquier par de puntos dados en un conjunto convexo, el segmento de l´ınea que los une est´a tambi´en en el conjunto. 2. El conjunto K es convexo si y solo si toda combinaci´on lineal convexa de puntos de K pertenece a K.

4

´ CAP´ITULO 2. ELEMENTOS MATEMATICOS PREVIOS 3. El conjunto de todas las combinaciones lineales convexas de los puntos x1 , ..., xk es un conjunto conexo. 4. Si los conjuntos S y T son convexos: a) El conjunto S ∩ T es convexo. b) el conjunto S + T = {x + t : s ∈ S y t ∈ T } es convexo. c) El conjunto S = {·s : · ∈ R y 0, S ∈ S} Teorema 2.1.1 Cualquier punto sobre el segmento de l´ınea que une dos puntos de un conjunto Rn , puede ser expresado como una combinaci´ on convexa de los dos puntos. Demostraci´ on Sean P y Q los puntos unidos por el segmento de l´ınea, y sea R un punto cualquiera sobre esta. Es claro que este segmento es paralelo a la l´ınea definida por el vector P − Q. Sea 0 ≤ λ ≤ 1, por las reglas de suma de vectores se sigue que: Q + λ (P − Q) = R o tambi´en, λP + (1 − λ) Q = R que es la expresi´on de R como combinaci´on lineal de P y Q.  Teorema 2.1.2 Cualquier punto que puede ser expresado como combinaci´ on convexa de dos puntos de En estar´ a sobre el segmento de l´ınea que une a los dos puntos. Demostraci´ on Tenemos, R = (1 − λ) Q + λP o R − Q = λ (P − Q) , con 0 ≤ λ ≤ 1 Se sigue que R − Q es alg´ un m´ ultiplo positivo del vector P − Q y por tanto los vectores R − Q y P − Q deber´an coincidir en direcci´on. Por otra parte, como el segmento de l´ınea que une P con Q y el segmento de l´ınea que une R con Q son paralelos a los vectores P −Q y R−Q respectivamente, el punto R deber´a estar sobre el segmento de l´ınea que une P con Q.

Ver´onica M. Acurio V´asconez

5

´ CAP´ITULO 2. ELEMENTOS MATEMATICOS PREVIOS Definici´ on 2.1.4 Sea C un conjunto convexo. Un punto U ∈ C se dice punto extremo, si U no puede ser expresado como una combinaci´ on convexa de otros dos puntos cualquiera distintos en C. Ejemplo 2.1.1 Los puntos extremos de un conjunto convexo que incluye la frontera y el interior de un c´ırculo, es su frontera. Si el conjunto no incluyera la frontera, el conjunto no tuviera puntos extremos. Ejemplo 2.1.2 Los puntos extremos de un tri´ angulo son sus v´ertices. Definici´ on 2.1.5 Se dice casco envolvente convexo C(S) de cualquier conjunto dado de puntos S al conjunto de todas las combinaciones convexas de conjuntos de puntos de S. C(S) es el conjunto convexo m´ as peque˜ no que contiene S . Definici´ on 2.1.6 Si el conjunto S consiste de un n´ umero finito de puntos, C(S) se denomina un poliedro convexo. Ejemplo 2.1.3 El conjunto de una regi´ on factible de un problema de optimizaci´on (que se definir´a en el siguiente cap´ıtulo)es un conjunto polieldral. Definici´ on 2.1.7 Un simplex es un poliedro n-dimensional que tiene exactamente n + 1 v´ertices. Observaci´ on Las fronteras del simplex contienen varios simplex de menor dimensi´ o n llamados caras simpliciales. El n´ umero de tales caras de dimensi´on   n+1 i es . i+1 Observaci´ on Un simplex en la dimensi´on cero es un punto, en la dimensi´on 1 una l´ınea, en tres un tetraedro, y as´ı. Observaci´ on La ecuaci´on de un simplex con intersecci´on unitaria es xi ≥ 0, m P xi ≤ 1 i=1

Ver´onica M. Acurio V´asconez

6

´ CAP´ITULO 2. ELEMENTOS MATEMATICOS PREVIOS

2.1.2.

Funciones Convexas

Definici´ on 2.1.8 Sea f : S ⊂ X → R ⊂ X con X convexo. f se dice convexa si y solo si dados x, y ∈ X. f (ax + (1 − a) y) ≤ af (x) + (1 − a) f (y) , ∀a, 0 < a < 1 Se dice que f es estrictamente convexa si y solo si se cumple la desigualdad estricta. Definici´ on 2.1.9 f se dice c´ oncava o estrictamente c´ oncava si y solo si −f (x) es convexa o estrictamente convexa respectivamente. Propiedades: 1. f (x) + g(x) es convexa. 2. max[f (x), g(x)] es convexa. 3. cf (x) con c ≥ 0, es convexa.

Ver´onica M. Acurio V´asconez

7

Cap´ıtulo 3 Elementos de un Problema de Optimizaci´ on 3.1.

Generalidades

Definici´ on 3.1.1 Los elementos esenciales de un problema de optimizaci´ on son los siguientes: 1. Variables de Decisi´on o Instrumentos: Es un vector de X variables (x1 , ..., xn ) que ser´an las inc´ ognitas a encontrar al solucionar un problema de optimizaci´on. 2. Conjunto de Oportunidades: Es el conjunto K ⊂ Rn donde se resuelve el problema. Es claro que X ∈ K. 3. Funci´on Objetivo: Es la funci´ on f definida como: f : Rn → R X 7→ f (x1 , . . . , xn ) Es una descripci´on matem´ atica del objetivo del problema, el mismo que ser´a maximizado o minimizado. k Observaci´
on Si es posible encontrar una secuencia X ∈ K para todo k k, y f X diverge hacia −∞, entonces el problema se dice irresoluble.

4. Funciones y Constantes de Restricci´on: Son funciones y constantes dadas en problema, que delimitan la funci´ on objetivo. 8

´ CAP´ITULO 3. ELEMENTOS DE UN PROBLEMA DE OPTIMIZACION Un problema de optimizaci´on se reduce entonces a buscar un X ∈ K que resuelve: m´ınX f (X) (3.1) tal que X ∈ K Definici´ on 3.1.2 Se dice que un problema de optimizaci´ on es factible si ∗ existe X ∈ K que cumple con las condiciones de restricci´ on. Si el problema no es ni infactible ni irresoluble, entonces es posible encontrar una soluci´on X∗ ∈ K que satisface: f (X∗ ) ≤ f (X) , ∀X ∈ S tal que X∗ es llamado un m´ınimo global del problema de optimizaci´ on. Si f (X ∗ ) < f (X) , ∀X ∈ K, entonces X∗ se dice un m´ınimo estricto global. En ocasiones solo es posible encontrar X∗ que satisface f (X∗ ) ≤ f (X) , ∀X ∈ S ∩ BX∗ (ε) Para alg´ un ε > 0, donde BX∗ (ε) es la bola abierta de radio ε con centro ∗ en X , es decir: B (X ∗ ; ε) = BX ∗ (ε) = {X : kX − X ∗ < εk} En este caso, X∗ es llamado un m´ınimo local. El m´ınimo estricto local est´ a definido como: f (X∗ ) < f (X) , ∀X ∈ K ∩ BX∗ (ε) El conjunto factible K se lo puede escribir expl´ıcitamente como sigue: K := {X : gi (X) = 0, i ∈ ε, gi (X) ≥ 0, i ∈ I} Donde ε es el conjunto para las restricciones de igualdad e I el conjunto de las restricciones de desigualdad.

Ver´onica M. Acurio V´asconez

9

Cap´ıtulo 4 Programaci´ on Lineal La Programaci´on Lineal es considerada como uno de los avances cient´ıficos m´as importantes del siglo anterior. Desde 1950, gracias al exponencial crecimiento de la tecnolog´ıa computacional, esta herramienta se ha ido acoplando cada vez m´as dentro de toda empresa, ya sea grande o peque˜ na, ahorr´andoles a las mismas enormes cantidades de dinero al realizar sus operaciones. La aplicaci´on de esta herramienta es sumamente variada, va desde la asignaci´on de instalaciones de producci´on de una empresa hasta la asignaci´on de recursos nacionales, pasando por la selecci´on de una cartera de inversiones, patrones de env´ıo, planeaci´on agr´ıcola, de redes, hasta incluso la de una dieta. Como todo modelo matem´atico, la programaci´on lineal permite expresar un problema de la vida diaria como un conjunto de funciones, restricciones y objetivos, que permiten dar soluciones a tales problemas.

4.1.

El Problema

Resolver un problema de este tipo, consiste en elegir valores no negativos de ciertas variables, para maximizar o minimizar la funci´on objetivo, que es lineal y que est´a sujeta a restricciones dadas por ecuaciones o desigualdades lineales. Un problema gen´erico de Programaci´on Lineal (PL), se representa de la siguiente forma:

10

´ LINEAL CAP´ITULO 4. PROGRAMACION

m´ınX cT X aTi X = bi , i ∈ ε aTj X = bj, j ∈ I

(4.1)

Donde ε y I son los conjuntos de restricciones de igualdades y desigualdades respectivamente. Sin embargo, podemos expresar este problema en la forma est´andar, m´ınX cT X AX = b X≥0

(4.2)

Aqu´ı, A ∈ Rmxn , b ∈ Rm , c ∈ Rn son dados y x ∈ Rn es la variable vector a ser determinada. A es la matriz de coeficientes de las funciones de restricci´on, b el vector de las constantes de restricci´on asociadas y f (X) = cT X, donde c es el vector de coeficientes de la funci´on objetivo. Suponemos que A tiene rango n, pues caso contrario no podr´ıa ser reducida. En la forma est´andar podemos escribir las desigualdades introduciendo una variable extra estrictamente no negativa, llamadas variables de holgadura. Ejemplo 4.1.1 Sea el problema de optimizaci´ on: m´ınX f (X) = −x1 − x2 2x1 + x2 ≤ 12 x1 + 2x2 ≤ 9 x1 , x2 ≥ 0 Este problema puede reescribirse como: m´ınX f (X) = −x1 − x2 2x1 + x2 + x3 = 12 x1 + 2x2 + +x4 = 9 x1 , x2 , x3 , x4 ≥ 0 Definici´ on 4.1.1 Una soluci´ on b´ asica del problema PL es una soluci´ on obtenida al hacer n − m variables igual a cero y resolver por las m variables restantes, siempre que el determinante de los coeficientes de estas m variables no sea cero. Las m variables se llaman variables b´ asicas. Ver´onica M. Acurio V´asconez

11

´ LINEAL CAP´ITULO 4. PROGRAMACION Definici´ on 4.1.2 Una soluci´ on posible b´ asica o soluci´ on factible b´ asica es una soluci´on b´asica que tambi´en satisface las condiciones de restricci´ on. Definici´ on 4.1.3 Una soluci´ on b´ asica no degenerada es una soluci´ on b´ asica posible con exactamente m xi positivas; esto es, todas las variables b´ asicas son positivas. Teorema 4.1.1 El conjunto de todas las soluciones factibles al problema de PL, es un conjunto convexo. Demostraci´ on Debemos probar que toda combinaci´on convexa de dos soluciones cualquiera es tambi´en una soluci´on factible. Lo probaremos por recurrencia. Si el conjunto de soluciones tiene un solo elemento, el teorema es verdadero. Supongamos ahora que existen por lo menos dos soluciones X1 y X2 . Se sigue que AX1 = b y AX2 = b , para X1 , X2 ≥ 0. Sea 0 ≤ α ≤ 1 y sea X = αX1 + (1 − α) X2 una combinaci´on convexa de X1 y X2 . Es claro que X ≥ 0 pues ninguno de sus elementos es negativo. Luego, AX = A (αX1 + (1 − α) X2 ) = αAX1 + A (1 − α) X2 = αAX1 + AX2 − αAX2 = αb + b − αb =b Por tanto AX es una soluci´on factible.

Observaci´ on Se dice que X es una soluci´on factible si X satisface las restricciones y se dice que X es una soluci´on ´optima si a m´as de satisfacer las restricciones, minimiza la funci´on objetivo, comparada con las otras soluciones factibles. Es decir, X = (x1 , ..., xn ) , xi ≥ 0 para todo i = 1, ..., n es una soluci´on factible si, x1 P1 + Pn = P0 , donde   x2 P2 + ... + xn  a1n a12 a11 P1 =  .  , P2 =  .  , ..., Pn =  .  amn am2 am1 Ver´onica M. Acurio V´asconez

y

 b1 P0 =  .  bm 

12

´ LINEAL CAP´ITULO 4. PROGRAMACION Observaci´ on Existen dos circunstancias en las cuales un problema de programaci´on lineal puede no tener una soluci´on: 1. Si las restricciones son incompatibles de modo que el conjunto de oportunidades es vac´ıo. 2. Si el conjunto de oportunidades es no acotado y la funci´on objetivo puede crecer sin l´ımite dentro de este conjunto. Ejemplo 4.1.2 Supongamos que una de las restricciones para una componente xi de X xi ≤ −6, esto contradice el hecho de que xi ≥ 0 para todo i = 1, ..., n, y por tanto no existe ning´ un elemento que cumpla esta condici´ on, convirtiendo al conjunto de oportunidades en uno vac´ıo, donde el problema PL no tiene soluci´on. Ejemplo 4.1.3 Sea el problema de programaci´ on Lineal definido como, m´ınX f (X) = x1 + x2 −x1 − x2 ≤ −8 x1 , x2 ≥ 0 El conjunto de oportunidades es no acotado y la funci´ on objetivo no posee l´ımite dentro de este conjunto. Por tanto es posible que el problema no tenga soluci´on. Si el conjunto de oportunidades es no vaci´o y acotado, entonces existe una soluci´on y debe ser una soluci´on de contorno. En general, podemos decir que existen tres tipos de soluciones a estos problemas; una soluci´on u ´ nica (un v´ertice), infinitas soluciones (una recta) o ninguna soluci´on (si el conjunto de oportunidades es vac´ıo o no acotado), m´as adelante se probar´an todos estos resultados. Teorema 4.1.2 La funci´on objetivo alcanza su m´ınimo en un punto extremo del conjunto convexo generado por el conjunto de soluciones posibles al problema PL. Si alcanza este m´ınimo en m´ as de un punto extremo, entonces toma el mismo valor para toda combinaci´ on convexa de estos puntos particulares. Demostraci´ on Sea K el conjunto convexo generado por el conjunto de soluciones, podemos afirmar que K tiene un n´ umero finito de puntos extremos. Ver´onica M. Acurio V´asconez

13

´ LINEAL CAP´ITULO 4. PROGRAMACION Sea f (X) la funci´on objetivo, los vectores x1 , ..., xp las soluciones factibles y X0 la soluci´on ´optima, es decir f (X0 ) ≤ f (X) para todo X ∈ K. Si X0 es un punto extremo, entonces cumplimos con la primera parte del teorema. Supongamos que X0 no es un punto extremo, entonces lo podemos expresar como una combinaci´on convexa de los puntos extremos de K, es decir

X0 =

q X

αi xi , con αi ≥ 0 y

i=1

X

αi = 1

i

Entonces, como f (X) es lineal, se sigue que p  P f (X0 ) = f αi xi

i=1
= f α1 X1 + α2 x2 + ... + αp xp = α1 f (x1 ) + α2 f (x2 ) + ... + αp f (xp ) = m

Donde m es el m´ınimo de f (X) para toda X ∈ K. Dado que la suma anterior no se incrementa, sustituyendo por cada Pf (xi ) el m´ınimo de todos estos valores f (xm ) = m´ın f (xi ) y sabiendo que αi = i

1, tenemos que

f (X0 ) ≥ α1 f (xm ) + α2 f (xm ) + ... + αp f (xm ) = f (xm ) y como f (X0 ) ≤ f (X) para toda X ∈ K, debe cumplirse que
f (X0 ) = f Xm = m

Es decir, existe un punto extremo Xm en el que la funci´on objetivo alcanza su m´ınimo. Para probar la segunda parte del teorema, supongamos que existen x1 , ..., xq soluciones m´ınimas para el problema LP. Se sigue entonces que f (x1 ) = f (x2 ) = ..... = f (xm ) = m. Sea X una combinaci´on convexa de las xi , enq P P tonces X = αi xi para αi ≥ 0 y αi = 1. i=1

i

Luego,

Ver´onica M. Acurio V´asconez

14

´ LINEAL CAP´ITULO 4. PROGRAMACION

f (X) = f (α1 x1 + α2 x2 + ... + αq xq ) = α1 f (x1 ) + α2 fP (x2 ) + ... + αq f (xq ) = αi m i

=m

 Observaci´ on Para encontrar una soluci´on m´ınima al problema PL, necesitamos considerar solo los puntos extremos del conjunto de soluciones. Teorema 4.1.3 Si puede encontrarse un conjunto de k ≤ n vectores P1 , ..., Pk LI que cumplan x1 P1 + x2 P2 + ... + xk Pk = P0 , con xi ≥ 0 Entonces X = (x1 , ..., xk , 0, ..., 0) es un punto extremo del conjunto convexo de oportunidades. Demostraci´ on Sea K el conjunto de oportunidades. Supongamos que X no es un punto extremo. Entonces, dado que X es una soluci´on posible, se la puede expresar como una combinaci´on convexa de otros puntos X1 y X2 ∈ K. Tenemos, X = αxi + (1 − α) x2 para 0 < α < 1 Como xi ≥ 0, con xi ∈ X, se sigue que los u ´ ltimos n − k elementos de X1 y X2 son cero, es decir,   (1) (1) (1) X1 = x1 , x2 , . . . , xk , 0 . . . 0   (2) (2) (2) X2 = x1 , x2 , . . . , xk , 0 . . . 0

Ahora, como X1 y X2 son soluciones factibles, AX1 = b y AX2 = b. Entonces, (1)

(1)

(1)

x1 P1 + x2 P2 + . . . + xk Pk = P0 (2) (2) (2) x1 P1 + x2 P2 + . . . + xk Pk = P0 Ver´onica M. Acurio V´asconez

y,

15

´ LINEAL CAP´ITULO 4. PROGRAMACION Como P1 , P2 , . . . , Pk son LI, P0 puede ser expresado como una combinaci´on u ´ nica de estos vectores, es decir, (1)

(1)

xi = xi = xi

Por tanto X no puede ser expresado como una combinaci´on convexa de dos puntos distintos de K y por lo tanto X es un punto extremo. Teorema 4.1.4 Si X = (x1 , ..., xn ) es un punto extremo de K, entonces los vectores asociados con las xi positivas, forman un conjunto LI. Adem´ as, al menos m de las xi son positivas. Demostraci´ on Sean los coeficientes distintos de cero los primeros k coeficientes, tales que, k X

xi Pi = P0

i=1

Supongamos que los vectores P1 , ...P k son LD, entonces existe una combinaci´on lineal de estos vectores tal que, d 1 P1 + d 2 P2 + . . . + d k Pk = 0 donde al menos una di 6= 0. Por hip´otesis, sabemos que, x1 P1 + x2 P2 + . . . + xk Pk = P0 Luego, multiplicando la primera ecuaci´on por d > 0, y sumando ambas, se sigue que, x1 P1 + x2 P2 + . . . + xk Pk + d (d1 P1 + d2 P2 + . . . + dk Pk ) = P0 k k P P xi Pi + d diPi = P0 i=1

i=1

Por otra parte, si restamos estas ecuaciones, tenemos, Ver´onica M. Acurio V´asconez

16

´ LINEAL CAP´ITULO 4. PROGRAMACION

k X

xi Pi − d

i=1

k X

d i Pi = P0

i=1

Entonces, dos soluciones posibles son: X1 = (x1 + dd1, . . . , xk + dd1 , 0 . . . , 0) X2 = (x1 − dd1 , . . . , xk − dd1 , 0 . . . , 0)

y,

Ahora bien,   1/ X1 + 1/ X2 = 1/ x1 + dd1 + 1/ x1 − dd1, . . . , 1/ xk + ddk + 1/ xk − ddk , 0 . . . , 0 2 2 2 2 2 2 = (x1 , x2 , . . . , xk , 0, . . . , 0) =X Lo que es una contradicci´on, pues X es un punto extremo y por tanto no se lo puede expresar como combinaci´on lineal de otros puntos extremos. Por lo tanto lo que supusimos es incorrecto, y entonces los P1 , ...P k son LI. Para probar que al menos m de las xi son positivas, partimos del hecho de que todo conjunto de m + 1 de vectores en un espacio m dimensional es necesariamente LD, entonces no podemos tener m´as de m xi positivas, puesto que si esto ocurriera, por la parte anterior de este teorema, existir´ıan vectores P1 , ..., Pm , Pm+1 que son LI. Podemos entonces concluir que el conjunto de P1 , ..., Pn del problema PL, tiene siempre un conjunto m de vectores LI, es decir, posee al menos m xi positivas. 

Corolario 4.1.5 Con cada punto extremo de K, se encuentra asociado un conjunto de m vectores LI del conjunto dado P1 , ..., Pn . Demostraci´ on De acuerdo al teorema (4.1.3) existen k ≤ m vectores de P1 , ..., Pn que son LI. Si k = m, no hay nada m´as que demostrar. Sea k < m y supongamos que podemos encontrar solamente Pk+1 , ..., Pr vectores adicionales tales que P1 , ..., Pk , Pk+1, ..., P r para r < m son LI. Se sigue que los n − r vectores restantes depende de P1 , ..., Pr , lo que contradice Ver´onica M. Acurio V´asconez

17

´ LINEAL CAP´ITULO 4. PROGRAMACION el hecho de que siempre existe un conjunto de m vectores LI en el conjunto dado. Por tanto, deben haber m vectores LI P1 , ..., Pm asociados con cada punto extremo, tales que k X

xi Pi +

i=1

m X

0Pi = P0

i=k+1

 Teorema 4.1.6 X = (x1 , ..., xn ) es un punto extremo de K, si y solo si las xj positivas son coeficientes de vectores Pj LI en k X

xj Pj = P0

i=1

Demostraci´ on Este teorema es la conjunci´on de los teoremas anteriores, por tanto su demostraci´on est´a la hecha.  Observaci´ on Note que existe un punto extremo de K, donde la funci´on objetivo alcanza su m´ınimo. Observaci´ on Cada soluci´on factible corresponde a un punto extremo de K.

Ver´onica M. Acurio V´asconez

18

´ LINEAL CAP´ITULO 4. PROGRAMACION

4.2.

Generaci´ on de Soluciones de Punto Extremo

Supongamos que conocemos una soluci´on de punto extremo en t´erminos de m vectores Pj del conjunto original de n vectores. Podemos hacer que este conjunto de m vectores LI sean los primeros, es decir X = (x1 , x2 , ..., xm , 0, ..., 0) sea el vector soluci´on. Entonces tenemos x1 P1 + x2 P2 + ... + xm Pm = P0 donde todas las xi ≥ 0. Con estos elementos vamos a buscar otra soluci´on de punto extremo, soluci´ on b´ asica para el problema, suponiendo que existe una. En efecto, dado que los P1 , ..., P m son LI estos forman una base para un espacio vectorial m-dimensional, y entonces cualquier vector de los n dados se puede expresar como, Pj =

m X

xij Pi ,

j = m + 1, ..., n

(4.3)

i=1

Supongamos ahora que existe un vector Pm+1 que no est´a en la base, que tiene al menos un elemento xi,m+1 > 0 en la expresi´on x1,m+1 P1 + x2,m+1 P2 + ... + xm,m+1 Pm = Pm+1

(4.4)

Sea θ un n´ umero cualquiera, multiplic´andolo por (4.4) y restando de (4.3), se sigue que, (x1 − θx1,m+1 ) P1 + (x2 − θx2,m+1 ) P2 + ... ... + (xm − θxm,m+1 ) Pm + θPm+1 = P0

(4.5)

El vector X′ = (x1 − θx1,m+1 , x2 − θx2,m+1 , ..., xm − θxm,m+1 , θ) es una soluci´on al problema y si todos sus elementos son no negativos, es una soluci´on factible. Como estamos buscando una soluci´on factible, distinta de X, restringimos θ a θ > 0. As´ı, todos los elementos de X′ que tiene una x1,m+1 negativa o igual a 0, tambi´en tendr´an una xi − θxi,m+1 no negativa. Si xi,m+1 es positiva, deseamos encontrar un θ > 0 tal que para todas las xi,m+1 > 0, cumplan que xi − θxi,m+1 ≥ 0 Ver´onica M. Acurio V´asconez

19

´ LINEAL CAP´ITULO 4. PROGRAMACION de donde, θ≤

xi xi,m+1

xi tendremos una soluci´on factible. luego, si tomamos 0 < θ ≤ m´ın xi,m+1 i

Ahora, como estamos buscando una soluci´on de punto extremo, y por los teoremas de la Secci´on 4.2 sabemos que no podemos tener todos los elementos m + 1 de X′ positivos, entonces uno de ellos debe ser exactamente igual a cero. Sea xi θ = θ0 = m´ın i xi,m+1 para xi,m+1 > 0. Entonces el elemento en X′ para el cual se obtiene este m´ınimo se reducir´a a cero. Tomemos el primer elemento, θ0 = m´ın i

xi xi,m+1

=

x1 x1,m+1

se sigue que, x′2 P2 + x′3 P3 + ... + x′m Pm + x′m+1 Pm+1 = P0 donde x′i = xi − θ0 xi,m+1 , para i = 1, ..., m y x′m+1 = θ.
Demostremos ahora, que efectivamente X = x′2 , ..., x′m , x′m+1 es un punto extremo, para ello debemos mostrar que P2 , P3 , ..., Pm , Pm+1 son LI. Supongamos que estos vectores son LD, entonces d2 P2 + d3 P3 + ... + dm Pm + dm+1 Pm+1

(4.6)

Con alguna dj 6= 0. Luego sabemos que cualquier subconjunto de un conjunto LI es tambi´en LI, entonces P2 , ..., Pm son LI, lo que implica que dm+1 6= 0. Sea ei =

di , dm+1

se sigue que e2 P2 + e3 P3 + ... + em Pm = Pm+1

(4.7)

Si restamos (4.7) y (4.4) tenemos, xi,m+1 P1 + (x1,m+1 − e2 ) P2 + ... + (xm,m+1 − em ) Pm = 0

(4.8)

Luego, como P2 , ..., Pm son LI, se sigue que todos estos coeficientes son iguales a cero, pero xi,m+1 es estrictamente mayor a cero, por tanto lo que supusimos Ver´onica M. Acurio V´asconez

20

´ LINEAL CAP´ITULO 4. PROGRAMACION es incorrecto y podemos decir que estos vectores deben ser necesariamente LI, y por tanto podemos concluir que X′ es una soluci´on extrema factible. Para seguir extrayendo nuevas soluciones posibles, proseguimos de esta misma manera. Ahora, debemos encontrar la representaci´on de cualquier vector que no se encuentre en la nueve base P2 , ..., Pm , Pm+1 en t´erminos de esta. De (4.4) se tiene que P1 =

1 x1,m+1

(Pm+1 − x2,m+1 P2 − ... − xm,m+1 Pm )

(4.9)

Sea, Pj = x1j P1 + x2j P2 + ... + xmj Pm

(4.10)

el vector que buscamos. Reemplazando P1 de (4.9) en (4.10) tenemos,     x1j x1j Pj = x2j − x1,m+1 x2,m+1 P2 + x3j − x1,m+1 x3,m+1 P3 + ...   x1j x1j ... + xmj − x1,m+1 xm,m+1 Pm + x1,m+1 Pm+1

En este procedimiento se selecciona una nueva variable para ser introducida en el sistema y as´ı obtener la nueva soluci´on y las nuevas representaciones de los vectores que no se encuentran en la base. Ejemplo 4.2.1 Sea el conjunto de ecuaciones: P1 P2 P3 P4 P5 P6 P0 3x1 − x2 + 2x3 + x4 = 7 2x1 − 4x2 + x5 = 12 −4x1 − 3x2 + 8x3 + x6 = 10 La soluci´on inicial de punto extremo X = (0, 0, 0, 7, 12, 10), es decir 7P4 + 12P5 + 10P6 = P0

(4.11)

En este ejemplo, los vectores base P4 , P5 , P6 son unitarios. Deseamos introducir el vector P1 para obtener otra soluci´ on de punto extremo. La representaci´on de P1 en t´erminos de los vectores base es: P1 = 3P4 + 2P5 − 4P6 Ver´onica M. Acurio V´asconez

(4.12) 21

´ LINEAL CAP´ITULO 4. PROGRAMACION Y entonces, x41 = 3,

x51 = 2

y

x61 = −4

Si multiplicamos (4.12) por θ y restamos el resultado de (4.11), tenemos (7 − 3θ) P4 + (12 − 2θ) P5 + (10 + 4θ) P6 + θP1 = P0

(4.13)

Como x41 y x51 son positivos, θ0 es 0 < θ = θ0 = m´ın i

Luego, θ04 = θ05 = θ06 =

x4 x41 x5 x51 x6 x61

xi xi1

= 73 =6 = −5 2

Entonces 0 < θ = θ0 = 7/3. Reemplazando θ0 en (4.13) se sigue que 22 58 7 P5 + P6 + P1 = P0 3 3 3 

aqu´ı se ha eliminado P4 de la base, es decir X = 7/3, 0, 0, 0, 22/3, 58/3 una soluci´on de punto extremo. ′



es

Si en vez de P1 hubi´esemos buscado la soluci´ on en t´erminos de P2 , hubi´esemos obtenido que (7 + θ) P4 + (12 + 4θ) P5 + (10 + 3θ) P6 + θP2 = P0

(4.14)

donde cualquier θ > 0 nos de una soluci´ on posible X′′ = (0, θ, θ, 7 + θ, 12 + 4θ, 10 + 3θ), como en este caso, xi2 < 0, no es posible hallar una soluci´ on de extremo. Si colocamos en una matriz todos los datos, realizar este procedimiento resulta mucho m´as eficiente. P1 1 2 −4

P2 P3 P4 P5 P6 −1 2 1 0 0 −4 0 0 1 0 −3 8 0 0 1

P0 7 12 10

θ 7/3 = θ0 6

Como queremos insertar P1 a la base y θ0 se encuentra en la primera fila hacemos a x1 del vector P1 el pivote y eliminamos x1 de todas las ecuaciones, Ver´onica M. Acurio V´asconez

22

´ LINEAL CAP´ITULO 4. PROGRAMACION excepto de la del pivote, donde hacemos x1 = 1. Para hacerlo, procedemos como si la tabla fuese una matriz, por tanto con el m´etodo de eliminaci´on completa podemos obtener los resultados que deseamos. En efecto, si dividimos la primera fila por 3, tenemos P1 P2 P3 P4 P5 P6 1 −1/3 2/3 1/3 0 0 2 −4 0 0 1 0 −4 −3 8 0 0 1

P0 7/3 12 10

θ

Haciendo −2F1 + F2 y 4F1 + F3 P1 P2 P3 P4 P5 P6 P0 1 −1/3 2/3 1/3 0 0 7/3 2/3 −10/3 −4/3 −2/3 1 0 22/3 0 −13/3 32/3 4/3 0 1 58/3   donde la nueva soluci´on es X′ = 7/3, 0, 0, 0, 22/3, 58/3

θ

Y entonces la nueva base es P1 , P5 , P6 y adem´ as,

−1/3P1 − 10/3P5 − 13/3P6 = P2 2/3P1 − 4/3P5 − 32/3P6 = P3 1/3P1 − 2/3P5 − 4/3P6 = P4

Ver´onica M. Acurio V´asconez

23

´ LINEAL CAP´ITULO 4. PROGRAMACION

4.3.

Dualidad

En la resoluci´on de un problema de optimizaci´on es necesario saber reconocer una soluci´on ´optima entre las soluciones. Retomemos el problema PL del ejemplo (4.1.1). generado.    12 2 1 1 0 1/2F1 1 1/2 1/2 0 ∼ 1 2 0 1  9 1 2 0 1 1 1/2 1/2 0 6 ∼ ∼ −F1 + F2 0 3/2 0 1 3 2/3F2

Resolvamos el sistema 6 9



1 1/2 1/2 0 0 1 0 2/3

6 2/9

Entonces, x2 = (−2/9 + 2/3x4 )

y

x1 = [6 − 1/2 (−2/9 + 2/3x4 )] − 1/2x3 = 10/9 − 1/2x3 − 1/3x4

Algunas soluciones factibles a la funci´on objetivo f (X) = −x1 − x2 son: (x1 , x2 , x3 , x4 ) = (0, 9/2, 15/2, 0) (x1 , x2 , x3 , x4 ) = (6, 0, 0, 3) (x1 , x2 , x3 , x4 ) = (5, 2, 0, 0)

valor objetivo = −9/2 valor objetivo = −6 valor objetivo = −9/2

(1) (2) (3)

Como estamos minimizando la soluci´on (3) es la mejor, pero no estamos seguros de si esta es la ´optima. N´otese que las restricciones limitan el valor de la funci´on objetivo. Para el ejemplo que estamos desarrollando, usando la primera restricci´on debemos tener que: −x1 − x2 ≥ −2x1 − x2 − x3 = −12 Esta desigualdad debe cumplirse con todas las soluciones factibles dado que xi son no negativas y el coeficiente de cada variable al lado izquierdo de la inecuaci´on es al menos tan grande como el coeficiente de la variable correspondiente del lado derecho. Si utilizamos la segunda restricci´on tenemos, −x1 − x2 ≥ −x1 − 2x2 − x4 = −12 o tambi´en podemos decir que, −x1 − x2 ≥ −x1 − x2 − 1/3x3 − 1/3x4 = −12 − 9 Ver´onica M. Acurio V´asconez

24



´ LINEAL CAP´ITULO 4. PROGRAMACION de donde se sigue que, −x1 − x2 ≥ −1/3 (2x1 + x2 + x3 ) − 1/3 (x1 + 2x2 + x4 ) = −1/3 (12 + 9) = 7 (Obs´ervese que −1/3 (2x1 + x2 + x3 ) − 1/3 (x1 + 2x2 + x4 ) = −x1 − x2 − 1/3x3 − 1/3x4 ). Esta u ´ ltima desigualdad indica que para toda soluci´on factible, la soluci´on de la funci´on objetivo no puede ser m´as peque˜ na que −7. Si observamos la soluci´on (3) vemos que cuando (x1 , x2 , x3 , x4 ) = (5, 2, 0, 0) el v.o = −7 y por tanto podemos concluir que esta es una soluci´on ´optima del problema. Estragegia: Si encontramos una soluci´on para el problema de programaci´on lineal y un l´ımite sobre el valor ´optimo de tal forma que el l´ımite y el valor objetivo de la soluci´on factible coincidan, entonces podemos tomar esta soluci´on como la soluci´on ´optima. En nuestro ejemplo, la estrategia nos llev´o a buscar valores y1 y y2 tales que y1 (2x1 + x2 + x3 )+y2 (x1 + 2x2 + x4 ) = (2y1 + y2 ) x1 +(y1 + 2y2 ) x2 +y1 x3 +y2 x4 donde cada componente es menor o igual a −x1 − x2 o, 2y1 + y2 ≤ −1 y1 + 2y2 ≤ −1 y1 ≤ 0 y2 ≤ 0 Es decir, ahora buscamos y1 y y2 que formen una combinaci´on m´axima para las restricciones anteriores, es decir, m´ax

12y1 + 9y2 2y1 + y2 ≤ −1 y1 + 2y2 ≤ −1 y1 , y2 ≤0

Definici´ on 4.3.1 El problema dual es un problema correspondiente al problema original. Se lo expresa como: m´axY Ver´onica M. Acurio V´asconez

bT Y AT Y ≤ c 25

´ LINEAL CAP´ITULO 4. PROGRAMACION donde y ∈ Rm . A˜ nadiendo una variable extra, podemos expresar este problema como: m´axY bT Y AT Y + s = 0 s≥0 donde s ∈ Rn Teorema 4.3.1 (De la dualidad d´ebil) Sea X una soluci´ on factible del problema PL y Y una soluci´on factible del problema dual correspondiente. Entonces, cT X ≥ bT Y Demostraci´ on Como X ≥ 0 y c − AT Y = x ≥ 0, el producto de estos dos vectores debe ser no negativo. YT s = sT X
T = c − AT Y X = cT X − YT b ≥ 0 Por tanto cT X ≥ bT Y.  El hecho de que XT s = cT − YT b es usualmente llamada el hueco de dualidad. Los siguientes corolarios son inmediatos del teorema anterior. Corolario 4.3.2 Si el problema primario PL (respectivamente el dual) es irresoluble, su dual (respectivamente el primario) es infactible. Corolario 4.3.3 Si X es factible por el primario PL, es factible del dual PL y cT X = bT Y, entonces X es una soluci´ on ´ optima para el primario PL y Y es la soluci´on ´optima del dual PL. Demostraci´ on Del teorema de dualidad d´ebil, se sigue que para toda soluci´on factible X del problema primal, cT X ≥ bT Y∗ En consecuencia X∗ es una soluci´on ´optima al primal. De la misma manera, podemos demostrar que Y∗ es una soluci´on ´optima del dual.  Ver´onica M. Acurio V´asconez

26

´ LINEAL CAP´ITULO 4. PROGRAMACION Teorema 4.3.4 (De la dualidad Fuerte) Si el problema primal o el problema dual tiene una soluci´on ´optima finita, entonces el otro problema tiene una soluci´on ´optima finita y los extremos de las funciones lineales son iguales, es decir minf (x) = maxg(W ), y para cualquier soluci´ on ´ optima X del primal T T y Y del dual, se tiene que c X = b Y, adem´ as si uno de los problemas no es acotado, entonces K es vac´ıo. Demostraci´ on La segunda parte se deriva directamente del teorema de dualidad d´ebil. En efecto, supongamos que el primal no es acotado inferiormente, entonces se tiene que cT x → −∞. Si el dual es factible, se tiene que existe un y ≤ c que por el teorema de dualidad d´ebil cumple con bT Y ≤ cT X de donde se sigue que bT Y es una cota inferior sobre el valor de la funci´on objetivo del primal, lo que es una contradicci´on. Para demostrar la primera parte, supongamos que el primal posee una soluci´on ´optima X∗ para la que le valor de la funci´on objetivo es igual a Z∗ . Sean xj1 , xj2 , ..., xjm las variables de la base de X correspondiente. Notemos que cB = [cj1 , cj2 , ..., cjm ]T . Sea π el vector de multiplicadores asociados a la base ´optima. Recordemos que las componentes de las variables son definidas como: cj = cj − ΠT aj , ∀j = 1, 2, . . . , n donde aj es la j-´esima columna de A. Supongamos que esta soluci´on de base ´optima es tal que cj = cj − ΠT aj ≥ 0, ∀j = 1, 2, . . . , n En consecuencia, ΠT aj ≤ cj , ∀j = 1, 2, . . . , n o aTj Π ≤ cj , ∀j = 1, 2, . . . , n de donde se sigue que AT Π ≤ c lo que implica que  Π ∈ Y : AT Y ≤ c

es decir que Π es una soluci´on factible para el dual.

Ver´onica M. Acurio V´asconez

27

´ LINEAL CAP´ITULO 4. PROGRAMACION Encontremos ahora el valor de la soluci´on factible Π para el dual. Tenemos, Π = B −1T cB De aqu´ı se sigue que bT Π = bT B −1T cB = B −1 b


T

∗ cB = X∗T B cB = Z



Definici´ on 4.3.2 X ∈ Rn es una soluci´ on ´ optima de (4.2) si y solo si 1. X es primal factible: AX = b, X ≥ 0 y existen Y ∈ Rn y S ∈ Rn tales que 2. (Y, S) es dual factible: AT Y + S = c, S ≥ 0 y 3. cT X = bT Y. Un an´alisis de estas condiciones nos lleva a obtener un conjunto de condiciones ´optimas alternativas. Del teorema de dualidad d´ebil, tenemos que
T cT X − bT Y = c − AT Y X ≥ 0 para cualquier par de soluciones factibles del primal-dual.

Este producto interno es 0. cT X = bT Y si y solo si se cumple que para j = 1, 2, ..., n, xi · (c − AT Y)i = Si es cero. Es decir, T

0= c−A Y


T

X=

donde cada t´ermino es no negativo.

n X i=1


c − AT Y i Xi

Dado que esta suma es cero, cada t´ermino debe ser cero. Entonces podemos decir que X ∈ Rn es una soluci´on ´optima de (4.2) si y solo si 1. X es primal factible: AX = b, X≥ 0 y existen Y ∈ Rn y S ∈ Rn tales que 2. (Y, S) es dual factible: AT Y + S = c, S ≥ 0 y 3. Para cada i = 1, ..., n se tiene que Xi Si = 0. Ver´onica M. Acurio V´asconez

28

´ LINEAL CAP´ITULO 4. PROGRAMACION

4.4.

El M´ etodo Simplex

El m´etodo simplex fue desarrollado por George B. Dantzig en 1947, con el fin de resolver problemas de planeaci´on para el gobierno de los Estados Unidos.

4.4.1.

Desarrollo de una soluci´ on posible m´ınima

Supongamos que el problema PL tiene soluci´on, y que esta se conoce. Adem´as supongamos que sus primeras m componentes no son ni cero ni negativas. Recordemos que se dice que X es una soluci´on b´asica si es de la forma, XN = 0,

XB = B −1 b

para alguna matriz base B. Si adem´as XB = B −1 b ≥ 0, la soluci´on XB = B −1 b, XN = 0 es una soluci´on b´asica factible del problema PL original. Las variables XB son llamadas variables b´asicas, mientras que las de XN son las variables no b´asicas. Sea X0 = (x10 , x20 , ..., xm0 ) y sea P1 , ..., Pm el conjunto asociado de vectores LI, entonces x10 P1 + x20 P2 + . . . + xm0 Pm = P0

(4.15)

x10 c1 + x20 c2 + . . . + xm0 cm = z0 , con xi0 > 0

(4.16)

y, Las ci son los coeficientes de restricci´on de la funci´on objetivo y z0 es el valor correspondiente de la funci´on objetivo para la soluci´on dada. Como P1 , ..., Pm son LI, podemos expresar cualquier vector del conjunto P1 , ..., Pn en t´erminos de P1 , ..., Pm , es decir Pj = x1j P1 + x2j P2 + . . . + xmj Pj , j = 1, . . . , n

(4.17)

zj = x1j c1 + x2j c2 + . . . + xmj cj , j = 1, . . . , n

(4.18)

Definamos,

donde ci son los coeficientes de restricci´on correspondientes a Pi .

Ver´onica M. Acurio V´asconez

29

´ LINEAL CAP´ITULO 4. PROGRAMACION Teorema 4.4.1 Si para cualquier j fija, se cumple que zj − cj > 0, entonces puede construirse un conjunto de soluciones posibles tales que z < z0 para cualquier miembro del conjunto donde el l´ımite inferior de z pude ser finito o infinito (z es el valor de la funci´ on objetivo para un miembro particular del conjunto de soluciones posibles) Demostraci´ on Si multiplicamos (4.17) por un n´ umero cualquiera θ y la restamos de (4.15) se sigue que, (x10 − θx1j ) P1 + (x20 − θx2j ) P2 + . . . + (xm0 − θxmj ) Pj + θPj = P0 con j = 1, . . . , n (4.19) De igual forma si multiplicamos (4.18) por el mismo θ y la restamos de (4.16), tenemos, (x10 − θx1j ) c1 + (x20 − θx2j ) c2 + . . . + (xm0 − θxmj ) cj + θcj = z0 − (zj − cj ) con j = 1, . . . , n (4.20) Si todos los coeficientes de los vectores P1 , ..., Pm , Pj en (4.19) no son negativos, entonces hemos obtenido una nueva soluci´on z = z0 − θ(zj − cj ). Como las variables x10 , x20 , ..., xm0 en (4.19) son todas positivas y por los teoremas de la Secci´on 4.2, existe un vector θ > 0 (finito o infinito), para el cual los coeficientes de los vectores en (4.19) permanecen positivos. Como j es fija, zj − cj > 0. Luego z = z0 − θ (zj − cj ) < z0 , para θ > 0 En cada caso se puede obtener una soluci´on posible, cuyo valor correspondiente de la funci´on objetivo es menor que el valor de la soluci´on precedente. 1. Si el l´ımite inferior es finito, se puede construir una nueva soluci´on posible con exactamente m variables positivas, cuyo valor de la funci´on objetivo es menor que el valor para la soluci´on precedente. Si para j fija, al menos xij > 0 en (4.17) para i = 1, ..., m el mayor valor de θ, para el que todos los coeficientes de (4.19) permanecen no negativos est´a dado por, θ0 = m´ın i

Ver´onica M. Acurio V´asconez

xi0 > 0, para xij > 0 xij

(4.21)

30

´ LINEAL CAP´ITULO 4. PROGRAMACION 2. Si el l`ımite inferior es infinito, puede construirse una nueva soluci´on posible con exactamente m variables positivas, cuyo valor de la funci´on objetivo puede hacerse tan peque˜ na como sea necesario. Si en cualquier paso de la demostraci´on del primer caso tenemos que para cierta j, zj − cj > 0 y todas las xij < 0, entonces no existe l´ımite superior a θ y la funci´on objetivo tiene un l´ımite inferior a −∞. En este caso, para cualquier θ > 0, todos lo coeficientes de (4.19) son positivos. Creamos entonces una soluci´on posible de m + 1 elementos positivos. En esta forma, tomando θ lo suficientemente grande, el valor correspondiente de la funci´on objetivo, dada en el lado derecho de (4.20), puede hacerse arbitrariamente peque˜ no. Por lo que se supuso al comienzo de este cap´ıtulo, todas las soluciones factibles poseen m elementos positivos, entonces el m´ınimo en (4.21) se obtiene para una i u ´ nica. Si reemplazamos θ0 por θ en (4.19) y (4.20), el coeficiente correspondiente a esta i u ´ nica se anular´a. As´ı hemos construido una nueva soluci´on factible, consistente en Pj y m − 1 vectores de la base original y obteniendo tambi´en una nueva base. Este proceso puede volverse a realizar cuantas veces sea necesario, hasta que zj − cj ≤ 0 o hasta que para cierta zj − cj > 0, todas las xij ≤ 0.  Teorema 4.4.2 Si para cualquier soluci´ on b´ asica posible, X = (x10 , ..., xm0 ) las condiciones zj − cj ≤ 0 se cumplen para todas las j = 1, ..., n, entonces (4.15) y (4.16) constituyen una soluci´ on posible m´ınima. Demostraci´ on Sean, y10 P1 + y20 P2 + . . . + yn0 Pn = P0

(4.22)

y10 c1 + y20 c2 + . . . + yn0 cn = z ∗

(4.23)

y, Sea cualquier otra soluci´on posible en la que z∗ es el valor correspondiente de la funci´on objetivo. Demostremos que z0 ≤ z∗ .

Ver´onica M. Acurio V´asconez

31

´ LINEAL CAP´ITULO 4. PROGRAMACION Por hip´otesis zj − cj ≤ 0, para todas las j, as´ı que si reemplazamos cj por cada zj en (4.23), tenemos y10 z1 + y20 z2 + . . . + yn0 zn ≤ z ∗

(4.24)

Para cada j sustituimos la expresi´on para cada Pj dada por (4.17) en (4.22) y obtenemos,

y10

m X

xi1 Pi

i=1

!

+ y20

m X

xi2 Pi

i=1

!

+ . . . + yn0

m X

xin Pi

i=1

!

= P0

(4.25)

As´ı mismo, para cada j sustituimos la expresi´on para zj dada por (4.18) en (4.24) y obtenemos, m X i=1

xj0 X1j

!

c1 +

m X

xj0 X2j

i=1

!

c1 + . . . +

m X

xj0 Xmj

i=1

!

cm ≤ z ∗ (4.26)

Dado que el conjunto de vectores P1 , ..., Pm es LI, los coeficientes de los vectores componentes en (4.15) y (4.25) deben ser iguales y entonces (4.26) se convierte en: x10 c1 + x20 c2 + . . . + xm0 cm ≤ z Que por (4.16) es lo mismo que decir z0 ≤ z ∗ . Los teoremas anteriores nos permiten ir de una soluci´on factible y generar un conjunto de nuevas soluciones factibles que converjan a la soluci´on m´ınima, o bien determinar que no existe una soluci´on finita. La generaci´on de una soluci´on b´asica y el desarrollo de una soluci´on ´optima, nos induce a observar que cuando un problema PL posee una soluci´on ´optima, debe tener una soluci´on ´optima b´asica factible. La significaci´on de este resultado nos lleva a decir que para encontrar la soluci´on a un problema PL es necesario chequear el valor objetivo de cada soluci´on b´asica. Note que existe solo un n´ umero finito de estas soluciones b´asicas, lo que reduce esta b´ usqueda a un espacio infinito o finito.

Ver´onica M. Acurio V´asconez

32

´ LINEAL CAP´ITULO 4. PROGRAMACION

4.4.2.

Procedimiento de C´ omputo

Consideremos el siguiente ejemplo, sacado del libro de ¨ Introduction to Mathematical Programming” de R. Walker. Ejemplo 4.4.1 El granjero Jones tiene 100 acres de tierra que quiere dedicar a la siembra de trigo y ma´ız, y desea planear la plantaci´ on de las mismas, de tal manera que pueda obtener la m´ axima ganancia por su venta. Jones tiene solamente $800 de capital, destinados a la siembra y le cuesta $5 plantar un acre de trigo y $10 un acre de ma´ız. La extensa vida social de la familia Jones, les deja libres solo 150 d´ıas laborables para dedicarlos a la siembra. Para sembrar cada acre de trigo se necesitan dos d´ıas y para sembrar un acre de ma´ız uno. Si experiencias pasadas indican un retorno de $80 por cada acre de trigo y $60 por cada acre de ma´ız, ¿cuantos acres de cada cosa deber´ıa plantear Jones para maximizar su rentabilidad? Soluci´ on Sean x1 y x2 las variables que denotan al trigo y al ma´ız respectivamente, se obtiene la siguiente formulaci´on al problema del granjero Jonnes m´ax Z = 80x1 + 60x2 sujeto a x1 + x2 ≤ 100 2x1 + x2 ≤ 150 5x1 + 10x2 ≤ 800 x1 , x2 ≥ 0 Luego de a˜ nadir las variables no b´asicas a cada una de las funciones de restricci´on del problema, se tiene la representaci´on del problema en casi la forma est´andar (pues estamos maximizando en vez de minimizar) m´ax Z = 80x1 + 60x2 sujeto a x1 + x2 + x3 = 100 2x1 + x2 + x4 = 150 5x1 + 10x2 + x5 = 800 x1 , x2 , x3 , x4 , x5 ≥ 0 El m´etodo simplex resuelve un problema PL movi´endose de una soluci´on de b´asica factible a otra, hasta que encuentre una soluci´on de estas que sea Ver´onica M. Acurio V´asconez

33

´ LINEAL CAP´ITULO 4. PROGRAMACION presumiblemente ´optima. Pero primero, se debe empezar por una soluci´on b´asica. Siguiendo el proceso de la Secci´ on (4.2), para el problema del granjero Jones, es trivial escoger la soluci´on b´asica, P0 = 100P3 + 150P4 + 800P5 El m´etodo simplex se observa de mejor manera si lo escribimos en tablas. Empecemos escribiendo la fila del objetivo del problema del granjero Jones. Z − 80x1 − 60x2 = 0 y representando el sistema usando la siguiente tabla, Variables Basicas Z x3 ⇐ x4 x5

P1 ⇓ x1 −80 1 2∗ 5

P2

P3

P4

P5

x2

x3

x4

x5

−60 1 1 10

0 1 0 0

0 0 1 0

0 0 0 1

P0

0 100 150 800

(1)

Esta tabla es llamada la tabla simplex. Las columnas encabezadas por cada variable, contiene los coeficientes de esta variable en cada ecuaci´on, incluyendo la fila de la ecuaci´on del objetivo, que es la fila Z. La primera columna de la izquierda es usada para realizar un seguimiento de las variables b´asicas de cada fila. La primera fila representa los vectores P1 , ..., Pm LI asociados a cada variable. Paso 0 La tabla inicial Una vez que hayamos formado la tabla (1), buscamos una variable entrante, es decir, una variable que tenga un coeficiente negativo en la columna objetivo y que acreciente la funci´on objetivo si es introducida en la base. En cada caso, las dos variables x1 y x2 poseen coeficientes negativos en la columna objetivo. Dado que x1 tiene el mayor coeficiente negativo, tomaremos la columna de este coeficiente (por ello la flecha sobre la columna de x1 ). Sin embargo, en principio, cualquier variable b´asica con coeficiente negativo puede ser tomada.

Ver´onica M. Acurio V´asconez

34

´ LINEAL CAP´ITULO 4. PROGRAMACION Paso 1 Encontrar una variable con un coeficiente negativo en la fila del objetivo. Si todas las variables tienen coeficientes no negativos en la fila ob´ jetivo, DETENGASE, la tabla que posee es la ´optima.(Buscamos que los coeficientes sean no negativos porque en este caso estamos maximizando, si estuvi´eramos minimizando, entonces buscar´ıamos que las variables sean no positivas) Luego de escoger x1 , como la variable entrante, necesitamos determinar la variable de holgadura (en ocasiones llamada la variable de salida). Esta variable se la encuentra realizando el proceso descrito en la secci´on (4.2) de Generaci´on de Soluciones de Punto Extremo. En efecto, si observamos la tabla (1), tenemos que la soluci´on inicial b´asica es X = (0, 0, 100, 150, 800), es decir, 100P3 + 150P4 + 800P5 = P0

(2)

Donde P3 , P4 y P5 son unitarios y por tanto constituyen la base. Como deseamos introducir P1 en la base, y as´ı obtener otra soluci´on b´asica, entonces expresamos P1 en t´erminos de los vectores base, es decir P1 = P3 + 2P4 + 5P5

(3)

De donde, x31 = 1,

x41 = 2 x51 = 5

Si multiplicamos (3) por θ y restamos el resultado de (2), tenemos θP1 − P0 = θP3 + 2θP4 + 5θP5 − 100P3 − 150P4 − 800P5 (100 − θ)P3 + (150 − 2θ)P4 + (800 − 5θ)P5 + θP1 = P0

(4)

Como x31 , x41 y x51 son positivos, θ0 es 0 < θ = θ0 = m´ın i

xi xi1

Luego, θ03 = θ04 = θ05 = Ver´onica M. Acurio V´asconez

x3 x31 x4 x41 x5 x51

= = =

100 1 150 2 800 5

= 100 = 75 = 160 35

´ LINEAL CAP´ITULO 4. PROGRAMACION Y entonces, 0 < θ = θ0 = 75 que corresponde al vector P4 (por ello la flecha hacia fuera en la variable x4 , en la tabla (1), que identifica esta como la variable de holgadura). Cabe recordar que en el proceso se busca el m´ınimo solo entre las variables que son no negativas. Si es que todas las θ0i son cero o negativas, entonces concluimos que el problema es irresoluble.

Paso 2 Una vez ubicada la variable de holgadura, encuentre otra soluci´on b´asica en la que se incluya el vector de la variable entrante dentro de la nueva base. Del paso anterior tenemos que θ0 = 75, reemplazando este valor en (4) se sigue que, 25P3 + 75P1 + 425P5 = P0 observe que hemos eliminado P4 , es decir el vector que contiene la variable de holgadura, entonces X′ = (75, 0, 25, 0, 425) es otra soluci´on de punto extremo. Si hacemos este proceso directamente en una tabla y la tratamos como una matriz, utilizando el m´etodo de eliminaci´on completa, podemos obtener la nueva base. Para ello debemos primero convertir al vector entrante en unitario, haciendo 1 en el pivote y cero en las dem´as componentes. El pivote es el elemento de intersecci´on entre la variable de holgadura y la variable entrante, es decir el elemento de intersecci´on de las fechas colocadas en la tabla (1). En este caso, es el 2, por ello este elemento se encuentra se˜ nalado con un *. Entonces, hacemos la tabla (1)

Ver´onica M. Acurio V´asconez

36

´ LINEAL CAP´ITULO 4. PROGRAMACION

P1 ⇓ x1 −80 1 2∗ 5

P2

P3

P4

P5

x2

x3

x4

x5

−60 1 1 10

0 1 0 0

0 0 1 0

0 0 0 1

0 100 150 800

P1

P2

P3

P4

P5

P0

x1

x2

x3

x4

x5

−80 1 1 5

−60 1 1/2 10

0 1 0 0

0 0 1/2 0

0 0 0 1

Variables Basicas Z x3 ⇐ x4 x5

F1 F2 F3 F4

P0

Dividiendo para dos F3 tenemos, Variables Basicas Z x3 x1 x5

F1 F2 F3 F4

0 100 75 800

Haciendo 80F 2 + F 1, −F 3 + F 2 y −5F 3 + F 4 tenemos,

F1 F2 F3 F4

Variables Basicas Z x3 x1 x5

P1

P2

P3

P4

P5

x1

x2

x3

x4

x5

0 0 1 0

−20 1/2 1/2 15/2

0 1 0 0

40 −1/2 1/2 −5/2

0 0 0 1

P0

6000 25 75 425

(5)

Paso 3 Volver a realizar los pasos 1 y 2 hasta que el Paso 1 nos pida detenernos Con la tabla (5), podemos decir que la nueva soluci´on b´asica inicial es, 25P3 + 75P1 + 425P5 = P0 Como x2 posee un signo negativo, vamos a introducir el vector P2 en la nueva base. Hacemos P2 = 25P3 + 75P1 + 425P5 De donde, Ver´onica M. Acurio V´asconez

37

´ LINEAL CAP´ITULO 4. PROGRAMACION

x32 = 1/2,

x41 = 1/2,

x51 = 15/2

Luego, θP2 − P0 = 1/2θP3 − 25P3 + 1/2θP1 − 75P1 + 15/2θP5 − 425P5 (25 − 1/2θ)P3 + (75 − 1/2θ)P1 + (425 − 15/2θ)P5 + θP2 = P0 Se sigue que θ03 = θ01 = θ05 =

x3 x32 x1 x12 x5 x52

= = =

100 1 150 2 800 5

= 50 = 75 = 170 3

Y entonces, 0 < θ = θ0 = 50 que corresponde al vector P3 en la tabla (5), identificando x3 como la variable de holgadura. Tenemos entonces la siguiente tabla P1

F1 F2 F3 F4

Variables Basicas Z ⇐ x3 x4 x5

x1 0 0 1 0

P2 ⇓ x2 −20 1/2∗ 1/2 15/2

P3

P4

P5

P0

x3

x4

x5

0 1 0 0

40 −1/2 1/2 −5/2

0 0 0 1

6000 25 75 800

P0

Multiplicando esta tabla por 2, se sigue

F1 F2 F3 F4

Variables Basicas Z x2 x4 x5

P1

P2

P3

P4

P5

x1

x2

x3

x4

x5

0 0 1 0

−20 1 1/2 15/2

0 2 0 0

40 −1 1/2 −5/2

0 0 0 1

6000 50 75 425

Haciendo, 20F 2 + F 1, −1/2 + F 3 y −15/2F 2 + F 4 tenemos, Ver´onica M. Acurio V´asconez

38

´ LINEAL CAP´ITULO 4. PROGRAMACION

F1 F2 F3 F4

Variables Basicas Z x2 x4 x5

P1

P2

P3

P4

P5

x1

x2

x3

x4

x5

0 0 1 0

0 1 0 0

40 2 −1 −15

20 −1 1 5

0 0 0 1

P0

7000 50 50 50

Como todas las variables del objetivo son no negativas, entonces (50, 50, 0, 0, 50) es la soluci´on ´optima. Podemos entonces decirle al granjero Jones que deber´ıa sembrar 50 acres de ma´ız y 50 acres de trigo para maximizar su ganancia, teniendo en cuenta sus limitaciones y condiciones.

Observaci´ on Si queremos minimizar la misma funci´on, basta con calcular −z, es decir poner un signo menos en la funci´on objetivo y realizar el m´etodo simplex, tratando de eliminar, en vez de las variables negativas, las positivas. Sin embargo, cuando se calcule el valor objetivo (V.O), se lo debe multiplicar por −1.

Ver´onica M. Acurio V´asconez

39

´ LINEAL CAP´ITULO 4. PROGRAMACION

4.5.

Alternativa al M´ etodo Simplex

Obtener un pivote para el m´etodo simplex es sumamente r´apido gracias a los avances de los computadores, incluso para problemas con miles de restricciones, de ah´ı el gran ´exito de la aplicaci´on de este m´etodo. Sin embargo, para problemas largos, considerados como problemas de 100 000 restricciones, el n´ umero de iteraciones del m´etodo puede ser muy grande. Algunos modelos, especialmente los referentes a las aplicaciones financieras, pueden tener esta cantidad de restricciones y muchas veces no pueden ser resueltos con el m´etodo simplex. Existe otro m´etodo que nos permite resolver estos grandes problemas, conocido como el m´etodo barrera o el m´etodo del punto interior. Este m´etodo usa una estrategia totalmente distinta a la del m´etodo simplex para buscar el ´optimo, siguiendo un patr´on mucho m´as complejo, pero el n´ umero de iteraciones necesarias no depende de cuan grande sea el problema. Como resultado, el m´etodo del punto interior, puede ser mucho m´as r´apido que el m´etodo simplex para resolver problemas de grandes proporciones. Programas inform´aticos como Cplex, Xpress, OSL, etc., dan la opci´on de resolver los problemas PL por cualquiera de estos dos m´etodos.

Ver´onica M. Acurio V´asconez

40

Cap´ıtulo 5 Modelizaci´ on PL y Aplicaciones Activo/Pasivo, Flujo de Caja, Fondos Compensatorios 5.1.

Algunos T´ erminos Financieros

Las corporaciones se enfrentan habitualmente a problemas de financiaci´on de efectivo a corto plazo. La programaci´on lineal puede ayudar en la b´ usqueda de combinaciones ´optimas de los instrumentos financieros (como bonos, acciones, vencimientos, etc.) que otorgue inversiones m´as eficaces. Considere el ejemplo. Ejemplo 5.1.1 Una compa˜ n´ıa tiene el siguiente problema de financiaci´ on a corto plazo, con un capital para el efecto de $ 1000. Mes Flujo de Caja Neto

Ene Feb Mar -150 -100 200

Abr May -200 50

Jun 300

La compa˜ n´ıa tiene las siguientes fuentes de inversi´ on Una l´ınea de cr´edito sobre los $100 a una tasa de inter´es del 1 % mensual. Puede emitir papales comerciales con un inter´es total del 2 % trimestral. Los fondos excedentes pueden ser invertidos a una tasa de inter´es del 0.3 % mensual.

41

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS Existen algunas preguntas que la compa˜ n´ıa quiere responder. ¿Qu´e inter´es de pago necesita hacer la compa˜ n´ıa entre enero y junio? ¿Es econ´omico usar la l´ınea de cr´edito? si es as´ı, ¿en cu´ales?, ¿cu´anto?. La programaci´on lineal, proporciona un mecanismo para contestar estas preguntas f´acil y r´apido. Incluso nos permite responder algunas preguntas del tipo ”que tal si”sobre cambios en los datos sin tener que resolver el problema, como por ejemplo, ¿qu´e tal si el flujo de caja neto en enero fuera -200 en vez de -150?, ¿qu´e tal si el l´ımite de la l´ınea de cr´edito se incrementara de 100 a 200?, ¿qu´e tal si el flujo de caja neto negativo de enero se debe a la compra de maquinaria por un valor de $150 y el vendedor permite una parte o la totalidad del pago de la misma que se hizo en junio a un inter´es del 3 % en un periodo de cinco meses? Las respuestas a estas preguntas est´an disponibles cuando el problema es formulado y resuelto como uno de programaci´on lineal. Existen entonces tres pasos al aplicar la programaci´on lineal en estos problemas: modelar, resolver e interpretar.

5.1.1.

Modelar

Empezamos modelando el peque˜ no problema financiero anterior, es decir, escribiremos este problema en el lenguaje de programaci´on lineal. Existen reglas sobre las que se puede o no plantear un la programaci´on lineal. Estas reglas imponen algunos de los pasos necesarios para el proceso (resolviendo e interpretando el problema) que nos llevan a plantearlo exitosamente. Las claves del programa lineal es el escoger bien las variables de decisi´on, el objetivo y las restricciones. Variables de Decisi´ on Las variables de decisi´on representan (desconocidas) decisiones a tomar. Esto est´a en contraste con los datos del problema que son valores dados o calculados del mismo problema. Para el problema que planteamos como ejemplo, existen variables posibles opciones para las variables de decisi´on. Usaremos las siguientes: el monto xi sobre la l´ınea de cr´edito en el mes i, el monto yi de los papeles comerciales emitidos en el mes i, el exceso de fondos zi en el mes i y la ganancia de la compa˜ n´ıa v en junio. Note que, alternativamente, podr´ıamos usar solo las variables de decisi´on xi y yi , dado que el exceso de fondos y la ganancia de la compa˜ n´ıa pueden ser deducidos de estas dos variables.

Ver´onica M. Acurio V´asconez

42

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS Objetivo Todo problema lineal tienen un objetivo, que debe ser o bien maximizado o bien minimizado. Este objetivo debe tener variables de decisi´on lineales, lo que significa que estas deben estar sum´andose o multiplic´andose por constantes, es decir 2x1 + 10x2 es una funci´on lineal, mientras que x1 ∗ x2 no lo es. En nuestro caso, el objetivo es simplemente maximizar v. Restricciones Cada programa lineal posee tambi´en restricciones que limitan las soluciones factibles. Aqu´ı tenemos tres tipos de restricciones: el debe tiene que ser igual al haber por cada mes, los l´ımites superiores sobre xi y la no negatividad de las variables de decisi´on xi , yi y zi . Por ejemplo, en enero (i = 1), existe un requerimiento de efectivo de $150. El conocer este requerimiento permite a la compa˜ n´ıa proporcionar un monto x1 para la l´ınea de cr´edito y emitir un monto y1 de papeles comerciales. Considera tambi´en la posibilidad del exceso de fondos zi que en este mes es 0. La ecuaci´on del balance de flujo de efectivo es, x1 + y1 − z1 = 150 Luego, en febrero (i = 2), existe un requerimiento de efectivo de $100. Adicionalmente, se suma un inter´es principal de 1,01x1 vencido a la l´ınea de cr´edito y se suma 1,003z1 recibido por la inversi´on del exceso de fondos. Sabiendo esto, la compa˜ n´ıa puede proporcionar un monto x2 para la l´ınea de cr´edito y emitir un monto y2 de papeles comerciales. Entonces la ecuaci´on del balance de flujo de efectivo para este mes es, x2 + y2 − 0,01x1 + 1,003z1 − z2 = 100 Si hacemos lo mismo para los meses de marzo, abril, mayo y junio, tenemos lo siguiente, x3 + y3 − 1,01x2 + 1,003z2 − z3 = −200 x4 − 1,02y1 − 1,01x3 + 1,003z3 − z4 = 200 x5 − 1,02y2 − 1,01x4 + 1,003z4 − z5 = − 50 −1,02y3 − 1,01x5 + 1,003z5 − v = −300 Note que xi es el balance sobre la l´ınea de cr´edito en el mes i, no el incremento del pr´estamo en el mes i. Similarmente, zi representa el exceso de fondos total en el mes i. Escoger as´ı las variables es bastante conveniente para escribir casi condiciones de l´ımites superiores y la negatividad de las restricciones. Ver´onica M. Acurio V´asconez

43

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

0 ≤ xi ≤ 100 yi ≥ 0 zi ≥ 0 Esto nos da el modelo final siguiente: m´ax

v x1 + y1 − z1 = 150 x2 + y2 − 1,01x1 + 1,003z1 − z2 = 100 x3 + y3 − 1,01x2 + 1,003z2 − z3 = −200 x4 − 1,02y1 − 1,01x3 + 1,003z3 − z4 = 200 x5 − 1,02y2 − 1,01x4 + 1,003z4 − z5 = −50 −1,02y3 − 1,01x5 + 1,003z5 − v = −300 x1 ≤ 100 x2 ≤ 100 x3 ≤ 100 x4 ≤ 100 x5 ≤ 100 xi , yi, zi ≥ 0

Formular un problema como un programa lineal significa ir a trav´es del proceso antes descrito para definir claramente las variables de decisi´on, el objetivo y las restricciones.

5.1.2.

Resolver

Existen varios programas que resuelven problemas de optimizaci´on. En este proyecto se usar´a la herramienta inform´atica Matlab. Este software posee un comando que nos permite resolver problemas PL, que es linprog. Este comando resuelve el programa lineal est´andar, es decir la minimizaci´on de la funci´on objetivo. Para maximizar, habr´ıa que transformar la funci´on objetivo en −f . Estructura del comando y Par´ ametros Existen diversas maneras en las que se puede expresar las soluciones de un problema de programaci´on lineal y opciones que podemos pedir a programa tome en cuenta al momento de resolverlo. Ver´onica M. Acurio V´asconez

44

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS X = LINP ROG(c, A, b) resuelve el problema, m´ınX cT X AX ≤ b donde c ∈ Rn es la matriz de coeficientes de funci´on objetivo la objetivo, A es la matriz de coeficientes de las funciones restricciones con A ∈ Rmxn y b ∈ Rm es el vector de las constantes de restricci´on. El script que resuelve el ejemplo 4.1.1 ser´ıa el siguiente.

Figura 5.1: Script ejemplo 4.1.1

X = LINP ROG(c, A, b, Aeq, beq) Si ingresamos variables de holgadura, podemos resolver el problema con Matlab si ponemos en c la los coeficientes de la funci´on objetivo con Ver´onica M. Acurio V´asconez

45

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS todas las variables, donde obviamente las de holgadura ser´an 0. En A, colocamos la matriz original con 0 en los coeficientes de las variables de hogadura, en Aeq la matriz A con 1 en los coeficientes de estas variables y hacemos beq = b. El script es el siguiente.

Figura 5.2: Script ejemplo 4.1.1 con variables de holgadura

X = LINP ROG(c, A, b, Aeq, beq, LB, LU) Aqu´ı, LB y UB son los conjuntos de l´ımites superiores e inferiores de las variables. Es decir LB ≤ X ≤ LU. Si se dejan vac´ıos, se sobre entiende que no existen l´ımites para las variables. Si se coloca LB(i) = −Inf significa que el problema no posee l´ımites hacia abajo, y si se pone UB(i) = Inf se entiende que el problema no posee l´ımites hacia arriba.

Ver´onica M. Acurio V´asconez

46

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS Como tenemos que las variables x1 , ..., xn son siempre positivas, debemos procurar colocar LB=[0 0 .... 0], de acuerdo a la cantidad de variables que tengamos. El script da el mismo resultado. Resolvamos entonces el problema de arriba, primero pong´amoslo en orden.

Ver´onica M. Acurio V´asconez

47

v x1 + y1 − z1 = 150 −1,01x1 + x2 + y2 + 1,003z1 − z2 = 100 −1,01x2 + x3 + y3 + 1,003z2 − z3 = −200 −1,01x3 + x4 − 1,02y1 + 1,003z3 − z4 = 200 −1,01x4 + x5 − 1,02y2 + 1,003z4 − z5 = −50 −1,01x5 − 1,02y3 + 1,003z5 − v = −300 x1 , x2 , x3 , x4 , x5 ≤ 100 xi , yi , zi ≥ 0

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

Ver´onica M. Acurio V´asconez

m´ax

48

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS Crearemos un archivo maximizar.m en el que desarrollemos la matices necesarias para aplicar el comando. Recordemos que Matlab solo puede minimizar, entonces, colocaremos la funci´on objetivo como −f de tal manera que podamos encontrar optimizaci´on m´axima. La funci´on es la siguiente,

Figura 5.3: Funci´on Maximizar en Matlab

Si corremos esta funci´on en la ventana de comandos de Matlab y luego aplicamos el comando linprog, tenemos los siguiente,

Ver´onica M. Acurio V´asconez

49

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

Figura 5.4: Resoluci´on del Ejercicio Financiero

5.1.3.

Interpretar

Cada paquete inform´atico posee su propia manera de presentar los resultados. En nuestro caso, al poner X = antes de la correr el comando, el resultado que se nos despliega es el valor que debe tener cada variable a fin de minimizar (o maximizar) la funci´on objetivo. Estos valores est´an en el mismo orden en el que se coloc´o las variables en la funci´on objetivo. Es f´acil entonces interpretar los resultado obtenidos. Sin embargo, existen otros programas que por el mismo hecho de presentar una mayor cantidad de informaci´on, su interpretaci´on se vuelve m´as compleja, como es el caso de la funci´on Solver en Excel.

Ver´onica M. Acurio V´asconez

50

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

5.2.

Caracter´ısticas de los Programas Lineales

Existen ciertos supuestos dentro de los programas lineales. La utilidad de este modelo est´a directamente relacionado con las suposiciones que se toman. Los primeros dos supuestos est´an relacionados con la forma lineal de las funciones. La contribuci´on al objetivo de las variables de decisi´on es proporcional al valor de cada una de ellas. Similarmente, la contribuci´on de cada variable al lado izquierdo de cada restricci´on es proporcional al valor de cada variable. Este es llamando el Supuesto de Proporcionalidad. Sin embargo, la contribuci´on de una variable al objetivo y a las restricciones es independiente de los valores de las otras variables. Este es el Supuesto de Aditividad. El siguiente supuesto, es el Supuesto de Divisibilidad. No es posible tomar fracciones de las variables. El u ´ ltimo supuesto es el Supuesto de Certeza, un programa lineal no admite la incertidumbre sobre los n´ umeros. Es raro que un problema posea exactamente todos estos supuestos y estos no niegan la utilidad del modelo. Un modelo puede tener un uso manejable incluso si la realidad difiere ligeramente de los requerimientos rigurosos del modelo.

Ver´onica M. Acurio V´asconez

51

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

5.3.

Dedicaci´ on

La Dedicaci´on o flujo de caja correspondiente es una t´ecnica usada para encontrar conocidos pasivos en el futuro. La idea es formar un portafolio de activos cuyo efectivo compense exactamente la salida de los pasivos. Los pasivos por lo tanto ser´an liquidados, a medida que se deben, sin la necesidad de vender o comprar activos en el futuro. El portafolio se forma hoy y es entonces mantenido hasta que los pasivos sean liquidados. Dedicar portafolios usualmente solo consiste en liberar de riesgo los bonos no exigibles dado que el efectivo del portafolio futuro necesita ser conocido cuando este es construido. Esto elimina el riesgo de la tasa de inter´es completamente. Esta t´ecnica es usada por algunos municipios y peque˜ nos fondos de pensiones. Por ejemplo, los municipios algunas veces quieren encontrar pasivos derivados de bonos que hayan expedido. Estos pre-reembolsados bonos pueden ser descontados de los libros del municipio, lo que les permite evadir restricciones convenientes en los bonos que han pre-reembolsado y seguramente les permite replantear su deuda. Se debe notar sin embargo, que que el costo de la dedicaci´on de portafolios est´a entre el 3 % y el 7 % m´as en t´erminos de d´olar que los portafolios ¨ınmunizados”, los mismos que son construidos bas´andose en el valor presente, la duraci´on y la convexidad de los activos y pasivos. Dada una cuenta corriente de flujo de efectivo Ct para t = 1, ..., T son llamados valores presentes si P =

T X t=1

Ct (1 + rt )t

La duraci´on es, T 1 X tCt D= P t=1 (1 + rt )t

y la convexidad se define como, T 1 X t (t + 1) Ct C= P t=1 (1 + rt )t+2

Ver´onica M. Acurio V´asconez

52

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS En estas f´ormulas, rt representa la tasa libre de riesgo en el a˜ no t. Si la cartera se compone solo de los bonos sin riesgo, el valor presente P ∗ del efectivo del portafolio futuro puede ser calculado usando la misma tasa libre de riesgo rt . Similarmente, para su duraci´on D ∗ y la convexidad C ∗ . Un portafolio ¨ınmunizado”puede ser construido haciendo coincidir P ∗ = P , D ∗ = D y C ∗ = C. Los portafolios que son construidos igualando estos tres factores son inmunizados contra los cambios paralelos en la curva de rendimiento, pero a´ un puede existir una exposici´on y vulnerabilidad frente a otro tipo de curvas y necesitan ser activamente manejados, lo cual produce costo. En contraste, la dedicaci´on de portafolios no necesita ser manejado luego de ser construido. Veamos es siguiente ejemplo. Cuando los municipios usan flujo de caja correspondiente, la costumbre est´andar es llamar a pocos bancos de inversi´on, mandar la lista de los pasivos y los requerimientos de ofertas. Los municipios entonces comprar las seguridades que los bancos ofertan al menor precio para una exitosa igualaci´on de efectivo. Ejemplo 5.3.1 Un banco recibe la siguiente lista de pasivos: A˜ no 1 A˜ no 2 12 000 18 000

A˜ no 3 20 000

A˜ no 4 A˜ no 5 20 000 16 000

A˜ no 6 15 000

A˜ no 7 A˜ no 8 12 000 10 000

Los bonos disponibles para la adquisici´ on hoy (A˜ no 0) est´ an dados por la siguiente tabla. Todos los bonos tiene un valor nominal de $100. El valor por cada cup´on es anual. Por ejemplo, costo del Bono 5 es $98 hoy y paga $4 de retorno en el A˜ no 1, $4 en el A˜ no 2, $4 en el A˜ no 3 y $104 en el A˜ no 4. Todos estos bonos est´an ampliamente disponibles y pueden ser adquiridos en cualquier cantidad al precio establecido. Bono Precio Cup´ on Madurez

1 102 5 A˜ no 1

2 99 3,5 A˜ no 2

3 101 5 A˜ no 2

4 98 3,5 A˜ no 3

5 98 4 A˜ no 4

6 104 9 A˜ no 5

7 100 6 A˜ no 5

8 101 8 A˜ no 6

9 102 9 A˜ no 7

Formularemos y resolveremos el problema lineal, de tal manera que encuentre el portafolio menos costoso de bonos a adquirir hoy que compense las obligaciones del municipio durante los siguientes ocho a˜ nos. Para eliminar la posibilidad de cualquier reinversi´ on riesgosa, asumimos una tasa de reinversi´on igual al 0 %. Ver´onica M. Acurio V´asconez

53

10 94 7 A˜ no 8

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

Soluci´ on El programa lineal es el siguiente,

Ver´onica M. Acurio V´asconez

54

102x1 + 99x2 + 101x3 + 98x4 + 98x5 + 104x6 + 100x7 + 101x8 + 102x9 + 94x10 105x1 + 3,5x2 + 5x3 + 3,5x4 + 4x5 + 9x6 + 6x7 + 8x8 + 9x9 + 7x10 = 12 000 +103,5x2 + 105x3 + 3,5x4 + 4x5 + 9x6 + 6x7 + 8x8 + 9x9 + 7x10 = 18 000 103,5x4 + 4x5 + 9x6 + 6x7 + 8x8 + 9x9 + 7x10 = 20 000 10 4x5 + 9x6 + 6x7 + 8x8 + 9x9 + 7x10 = 20 000 109x6 + 10 6x7 + 8x8 + 9x9 + 7x10 = 16 000 10 8x8 + 9x9 + 7x10 = 15 000 109x9 + 7x10 = 12 000 107x10 = 10 000 xi ≥ 0

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

Ver´onica M. Acurio V´asconez

m´ın

55

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS La funci´on dedicar.m creada a base de los datos es la siguiente,

Figura 5.5: Funci´on Dedicar en Matlab

Ver´onica M. Acurio V´asconez

56

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS Entonces en la ventana de comandos de Matlab, al aplicar el comando linprog se nos despliega,

Figura 5.6: Resultado de la optimizaci´on de la funci´on Dedicar

Podemos entonces, por ejemplo, decirle a la empresa que deber´ıa comprar $62,16 d´olares del bono uno, ning´ un bono 2, $125.27 del bono 3 y as´ı a fin de liquidar sus pasivos cada a˜ no al menor costo.

Ver´onica M. Acurio V´asconez

57

´ PL Y APLICACIONES CAP´ITULO 5. MODELIZACION ACTIVO/PASIVO, FLUJO DE CAJA, FONDOS COMPENSATORIOS

5.4.

Sensibilidad y An´ alisis de la Programaci´ on Lineal

Encontrar la soluci´on ´optima a un modelo de programaci´on lineal es importante, pero no es la u ´ nica informaci´on disponible. Existe un conjunto enorme de informaci´on sensible o informaci´on sobre que pasar´ıa si los valores cambiaran. Recordemos que cuando formulamos un problema como un programa lineal, asumimos ciertas cosas, debemos tener en cuenta que el valor tomado y las decisiones se basan en los datos. Muchas veces, estos supuestos son de alguna manera dudosos, pues los datos pueden ser desconocidos, o supuestos o hasta incalculables. Entonces, ¿c´omo podemos determinar el efecto de las decisiones ´optimas en los cambios de valores? Obviamente, algunos n´ umeros en los datos son m´as importantes que otros ¿c´omo saber cu´ales son importantes?, ¿c´omo determinar el efecto de los errores de estimaci´on? La sensibilidad es exactamente esto y con an´alisis de la programaci´on lineal se pueden responder estas preguntas, dependiendo del del paquete inform´atico que se use. Si usamos Matlab podemos pedirle que nos retorne, a m´as del valor de las constantes, el valor objetivo, mediante el comando, [X, f val] = linprog(f, A, b, Aeq, beq, LB, LU) Recuerde que como Matlab solo minimiza, tuvimos que minimizar la funci´on −f a fin de obtener el m´aximo, por ello el par´ametro f val nos devolver´a un valor negativo. Lastimosamente, este paquete no es capaz de darnos m´as informaci´on que esta. Si usamos Excel por otro lado, podemos visualizar otros factores como la influencia de una variable en el incremento o decremento del valor final de cada mes.

Ver´onica M. Acurio V´asconez

58

Cap´ıtulo 6 Conclusiones La matem´atica se convierte en una herramienta sumamente u ´til cuando se llega a darle la aplicaci´on adecuada. Los teoremas y definiciones son importantes en el desarrollo de la teor´ıa matem´atica y cruciales para el entendimiento y sobre todo para el planteamiento de los problemas de la vida real, pero llegar a darle la aplicaci´on adecuada, es lo que hace funcionar a la teor´ıa. La forma de plantear la funci´on objetivo, las restricciones y los l´ımites es vital al momento de resolver un programa lineal, as´ı que de la interpretaci´on del problema y de su traducci´on al lenguaje matem´atico depende el ´exito o el fracaso de la optimizaci´on. Los avances tecnol´ogicos han sido los verdaderos gestores del gran ´exito de la programaci´on lineal, puesto que hace 30 a˜ nos, resolver sistemas de ecuaciones con m´as de 10 000 inc´ognitas y variables era simplemente impensable. Existen varios paquetes inform´aticos especializados en optimizaci´on como Cplex, Xpress, OLS entre otros, que permiten resolver problemas de este estilo, los mismos que son mucho m´as completos, con herramientas m´as sofisticadas que permiten una mejor visi´on de de los resultados. Matlab o Excel no son uno de ellos, as´ı que se podr´ıa profundizar m´as en los programas mencionados para un mejor desempe˜ no. Es importante tambi´en recalcar que para maximizar (o minimizar) una funci´on que en principio se est´a minimizando (o maximizando), basta con multiplicar por −1 la funci´on objetivo, dejando las restricciones tal como est´an planteadas. Sin embargo, para obtener el valor objetivo, se debe volver a multiplicar tal valor por −1. 59

CAP´ITULO 6. CONCLUSIONES

Si bien muchos de los problemas financieros pueden ser resueltos como un programa lineal, en la pr´actica no siempre poseemos todos los datos requeridos para resolverlo as´ı, o simplemente no podemos interpretar los requerimientos en forma lineal. En estos casos, son necesarias otros tipos de herramientas m´as poderosas como la optimizaci´on cuadr´atica, la no param´etrica o estoc´astica; temas que el proyecto no lleg´o a abordar.

Ver´onica M. Acurio V´asconez

60

Bibliograf´ıa [1] Gerard Corneujols Optimization Methods in Finance, Tepper Scholl of Business, Carnegie Mellon University, Pittsburgh, PA 15213 USA (2004) [2] Saul I. Gass Programaci´on Lineal, M´etodos y Aplicaciones, World Systems Laboratories, Inc. The American University, McGRAW-HILL, Inc. (1969) [3] Michael D. Intriligator Optimizaci´ on Econ´ omica y Teor´ıa Econ´ omica, Editorial Prentice/Hall Internacional (1973) [4] Silvia Garc´ıa, Clyde Monz´on Teor´ıa de la Convexidad y Teor´ıa Econ´ omica, Anuario 2002 -F.C.E - U.N.P.S.J.B.13 ´ [5] Bernard Kolman, David R. Hill Algebra Lineal, Pearson, Prentice Hill (2006) [6] Frederick S. Hillier, Gerald J. Lieberman Investigaci´ on de Operaciones, McGRAW-HILL, Inc. (1969), s´eptima edici´on [7] A. Tovar Optimizaci´on de Procesos en Ingenier´ıa: Tarea 6, Programaci´ on Lineal, http://www.unal.edu.co/optimun/docencia/chgaleanouT06.pdf [8] William Marchena, Carlos Ornelas Optimizaci´ on Lineales con Restricciones en MATLAB:Teor´ıa http://www.fglongatt.org.ve/Reportes/RPT2007-09.pdf

de y

Funciones Ejemplos,

[9] Juan M´endez Rodriguez, Antonio Falc´on Martel Introducci´ on a la Investigaci´on de Operaciones, Grupo de Inteligencia Artificial y Sistemas Universidad de Las Palmas de Gran Canaria (2003) http://serdis.dis.ulpgc.es/ a013775/asignaturas/ii-io/InvO.pdf ´ [10] Friedrich Eisenbrand Optimization Methods in Finance, Ecole Polytechnique de F´ed´erale de Lausanne http://disopt.epfl.ch/page72255.html

61

BIBLIOGRAF´IA [11] G. Cornelis van http://web.uvic.ca/ Intro.pdf

Kooten A Brief Introduction to MatLabA, kooten/OperationsResearch/Lectures/MatLab-

[12] http://www.uv.es/ sala/Clase11.pdf [13] http://chentserver.uwaterloo.ca/courses/che720/Matlab Optimization/LP.pdf

Ver´onica M. Acurio V´asconez

62