Source: https://es.scribd.com/doc/58243860/Optimizacion-Lineal
Timestamp: 2016-10-23 08:10:43+00:00

Document:
NavegarNavegarInteresesBiography & MemoirBusiness & LeadershipFiction & LiteraturePolitics & EconomyHealth & WellnessSociety & CultureHappiness & Self-HelpMystery, Thriller & CrimeHistoryYoung AdultNavegar porLibrosAudio librosCómicsPartiturasExplorar todoSubirIniciar sesiónRegistrarseLibrosAudio librosCómicsPartituras21CA P Í T U L O 2 P ROGRAMACI ÓN L I NE AL 2.1. El modelo de Programación Lineal En los siglos XVII y XVIII, grandes matemáticos, como Newton, Leibnitz, Bernoulli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones. Posteriormente, el matemático francés Jean Baptiste-Joseph Fourier (1768-
vamos a pasar un problema formulado en forma canónica a otro en forma estándar. …. tendremos: Restricciones (=): Formulación estándar. pues debe cumplir que. tenemos Max z = c1 x1 + c2 x2 + … + cn xn=Max st
aij xj  bi. t. Problema formulado en forma canónica: Max (Min)z = c1 x1 + c2 x2 + … + cn xn st (s. Significa que los parámetros o constantes son estimados con certeza. donde (x+) 0. no interviene una función de probabilidad para obtenerlos El modelo de programación lineal es un caso especial de la programación matemática. (x-)0 Por ejemplo. Sin restricciones de signo: xk =(x+). 2. m)
xj  0. Dependiendo del tipo de restricción que presente el problema de programación lineal. Restricciones () o (): Formulación canónica.(x-). n) Escrito en forma matricial sería: Max z = cT X st AX b X0 Cada columna de coeficientes técnicos Aj representa un vector:
.) a11 x1 + a12 x2 + … + a1n xn  b1 a21 x1 + a22 x2 + … + a2n xn  b2 ……………………………. 2. Restricciones ( o () o (=): Formulación mixta. i Escrito lo anterior en forma compacta. am1 x1 + am2 x2 + … + amn xn  bm xi  0.Programación Lineal
Certidumbre. tanto la función objetivo como todas las funciones de restricción. (j =1. o sea. …. (i=1. sean lineales.
. x2. inventario)..   a   mj  Las restricciones las escribiremos: x1 A1+ x2 A2 +…+ xn An  b xi  0.. implica que el recurso de esa actividad se ha consumido en su totalidad (restricción saturada). 2ª Establecimiento de la función objetivo cuyo valor se desea maximizar(utilidad. t.. Cuando las variables de holgura son iguales a cero... xn). mano de obra. xn+2. i Problema formulado en forma estándar: Max (Min)z = c1 x1 + c2 x2 + … + cn xn st (s. ingreso. Fases en la resolución de problemas de Programación Lineal
Las fases en la resolución de un problema de Programación Lineal las podemos resumir en: 1ª Definir el significado cuantitativo de las variables de decisión (x1.. xn+m se las denomina variables de holgura y se introducen para convertir desigualdades en igualdades. am1 x1 + am2 x2 + … + amn xn + xn+ m = bm xi  0.26  a1 j     a2 j  A j =  .. ii) Para no menos de lo requerido (). …..….... Las restricciones que pueden presentarse son del tipo: i) Si no se debe exceder del recurso disponible (). i
A las variables xn+1. rendimiento. iii) Para igualar el recurso especificado (=).
.) a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 ….. tiempo.
2. 3ª Establecimiento de las restricciones que limitan el valor óptimo que puede tomar la función objetivo.3. producción) o bien minimizar (costo.... 4ª Resolución del problema y análisis de la solución o soluciones..
A.1) (2. x2 0 4ª fase : La resolución del problema y análisis de la solución o soluciones se verá posteriormente. La tabla siguiente muestra los recursos:
Tipo de Máquina A B C Ganancia por u. 2 2 2 1. que pueden fabricar dos productos.
Producto 1 Horas por u. Todos los productos tienen que pasar por todas las máquinas. B y C.5 x2 3ª fase : 2 x1 + 2 x2  16 x1 + 2 x2  12 4 x1 + 2 x2  28 x1  0. 2 1 4 1
Producto 2 Horas por u.2) (2. para obtener la máxima ganancia ? Desarrollado el problema en fases. Tipo de soluciones en un problema de programación lineal
Ejercicio.50
¿Qué cantidad de cada producto P1 y P2 se debe manufacturar cada semana.4. P1 y P2. resulta: 1ª fase: x1 = “ número de unidades de P1 “ x2 = “ número de unidades de P2 “ 2ª fase: Max z = 1 x1 + 1.3)
2. Un empresa tiene tres tipos de máquinas.
esto hace que la suposición de que n  m esté justificada. donde X es el vector formado con las variables básicas y se asignan a estas variables la solución obtenida. x2. se dice que es una matriz básica factible si el vector resultante de multiplicar su inversa por el vector b tiene todas sus componentes mayores o iguales que cero Cada matriz básica B del programa lleva asociado un vector que se conoce como solución básica.
2. Las soluciones de un problema de programación lineal se clasifican en:
Es un conjunto de n + m variables xj. xj. Variables no básicas: las restantes. Si B es una de esas matrices. Cada una de las submatrices de A con determinante distinto de cero (es decir. Además se supondrá que la matriz A tiene rango m. Las restricciones redundantes pueden eliminarse de la formulación del problema y las contradictorias provocan que el espacio de soluciones factibles sea vacío y el problema no tenga solución.3) sus componentes son todas positivas o nulas. se dice que es una matriz básica factible si el
.2) al hacer (n-m) variables iguales a 0. Generalmente las restricciones aparecen en forma de desigualdad y son convertidas en igualdades al introducir las variables de holgura. xn+1. invertibles) formadas seleccionando m columnas de A se llama matriz básica o matriz de base.. lo que quiere decir que pueden seleccionarse m columnas de A de manera que la matriz que forman tenga determinante no nulo. xn . siendo n  m.. 3.. .. xn+m) que satisface el conjunto de ecuaciones que constituyen el sistema (2.. inversibles) formadas seleccionando m columnas de A. Cada una de las submatrices de A con determinante distinto de cero (es decir. se llama matriz básica o matriz de base. . Se resuelve el sistema BX = b.28
Donde A es una matriz de m filas (restricciones) y n columnas (variables).  Solución básica: Solución básica: aquella que resulta de (2. definidas ordenadamente como un vector X = ( x1. Se dividen las variables de decisión en dos bloques:
Variables básicas: aquella que resulta de (2. A las variables no básicas se las da el valor cero. El hecho de exigir que el rango de la matriz A sea m implica evitar que en el problema aparezcan restricciones redundantes o contradictorias. el proceso de construcción es el siguiente: 1.2) y (2..2) al hacer (nm) variables iguales a 0. . Si B es una de esas matrices..
A continuación se presenta un ejemplo de localización de soluciones básicas de un programa lineal. Solución factible mínima: aquella que es factible y hace mínimo z. En primer lugar. Éste es el número de posibles combinaciones para elegir m columnas entre las n columnas existentes. Por ejemplo. es decir. todas las variables son no negativas. todas las variables básicas son positivas. a su vez. No factibles: alguna componente tiene un valor negativo. en:
Degeneradas: cuando alguna de las variables básicas tiene un valor nulo. x2. x3  0 y clasificarlas en factibles o no factibles. No degeneradas: cuando todas las variables básicas son estrictamente positivas. la primera matriz básica que puede construirse es la formada por las dos primeras columnas de A:
El número de soluciones básicas de un problema lineal es siempre finito y  (n  m)!  como máximo:    m! n!  donde m es el número de restricciones de igualdad y n el número de variables en su forma estándar. Se trata de encontrar las soluciones básicas del problema
Y. Solución factible básica no degenerada: aquella que es solución factible básica que tiene exactamente m variables xi positivas. degeneradas o no degeneradas. esto es. debe formularse el programa en su forma estándar y obtener las correspondientes matrices:
Las matrices básicas serán en este caso todas las submatrices inversibles formadas al seleccionar 2 columnas de A. no siempre todas esas combinaciones dan lugar a matrices con determinante no nulo.Programación Lineal
vector resultante de multiplicar su inversa por el vector b tiene todas sus componentes mayores o iguales que cero. Por supuesto. Solución factible básica: aquella que es solución básica y cumple (2.
0) (0. x3 y x4 4 1 0 1 x3 y x4 x1. x2 y x5 -1 0 Solución básica Tipo
(0. x3 y x5 4 0 2 0 x2 y x5 x1.0. Las variables básicas son no negativas por tanto la solución básica es factible y es degenerada porque la primera variable básica es nula.30
En este caso.0.0.0. x4 y x5 1 -1 2 1 x1 y x4 x2.0.0) (12.0.0.3. se las da el valor cero y la solución básica que se obtiene es X=(0. las no básicas. De igual manera se construyen el resto de soluciones básicas.0) (0.0).0.0.0. las variables básicas son x1 y x2 y los valores que toman en la correspondiente solución básica se obtienen resolviendo el sistema: 2x1+2x2 = 6 x1+4x2 = 12 La solución de dicho sistema es x1 =0 y x2=3.3.0.0.0.0. x2 y x3
Veamos.6.9) (0.-9.0. x4 y x5 1 4 2 0 x1 y x3 x2. x4 y x5 4 -1 2 1 x2 y x4 x1.0) (3.0.-12. A las restantes variables.3. en este caso todas las submatrices 2x2 son básicas excepto la que forman las columnas tercera y quinta.
Variables Variables no Matriz básicas básicas básica 2 2 x1 y x2 x3.-18.3. En la siguiente tabla se presentan todas las soluciones básicas obtenidas.3.0.0) (3.12)
x1.0.0. mediante un ejemplo el concepto de punto básico degenerado (menos de m componentes positivas) y no degenerado:
. x3 y x4 1 1 2 0 x2 y x3 x1.0) (0. x3 y x5 1 0 2 0 x1 y x5 x2.0.0) (0.6.
Los valores de la función objetivo en cada uno de los vértices son: f(O) = f(0.1/2 ) es no básico Veamos una serie de ejemplos de problemas de programación lineal con dos variables atendiendo al tipo de solución que presentan: i) Con solución única Maximizar la función z = f(x.y0 Tiene por región factible la región sombreada. 4) El punto (1.0) = 240.0) es básico degenerado El punto (0.0.1/4 .x4 st x1+x2+x3 =1 x1-x2-x3 +2x4 =1 xi  0 (i=1. y corresponde al vértice para el que la función objetivo toma el valor máximo.1. f(C)=f(60.0) = 0. f(D) = f(20.60) = 260.
Max z = x1-2x2+5x3 .0.60).0. 2.y) = 4x + 3y st 30x + 20y  1800 x + y  80 x0. 3.1) es básico no degenerado El punto (1/2.80) = 240 La solución es única. f(E) = f(0. En este caso es el vértice D(20. 1/4 .
x . iii) Solución no acotada (No existe límite para la función objetivo) Maximizar la función z = f(x.32 ii) Solución múltiple
Maximizar la función z = f(x. En estos casos. En este caso no existe un valor extremo para la función objetivo. la región factible debe estar no acotada. como ya vimos en el capítulo anterior.5.y  1 . el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible. y  0 Los valores de la función objetivo en cada uno de los vértices son: f(O)=f(0. la función objetivo es paralela a una de las restricciones.4) = 8 La función objetivo alcanza el valor máximo en los vértices B y C.0) = 4 f(B)=f(5/3. y 0 No existe la región factible.y)= 4x + 2y st 2x + y  4 .y) = 3x + 8y st x + y 6 .y) = x + y st y  2x . Resolución de un problema de programación lineal mediante el método gráfico
. iv) Cuando no existe el conjunto de soluciones que cumplen las restricciones Maximizar la función z = f(x.Por tanto. x  0 . Para que suceda esta situación. y  x/2 Tiene por región factible la zona coloreada que aparece en la figura. x 0 . Este tipo de problemas carece de solución. por lo que puede decirse que el problema carece de solución.2/3) = 8. por tanto.
2. que corresponden a los puntos del segmento situado entre dos vértices de la región factible. f(A) = f(1. que es una región no acotada. x + y 2 . La función crece indefinidamente para valores crecientes de x e y.0) = 0. ya que las zonas coloreadas que aparecen en la figura son únicamente soluciones de alguna de las inecuaciones . f(C) = f(0. Hay infinitas soluciones. en todos los puntos del segmento BC. solución múltiple.
Ejercicio 3. El fabricante prometió construir por lo menos dos mesas. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. 7. Función objetivo:
. Si el punto de ensayo satisface la desigualdad original. 10. Por otra parte. Resolver gráficamente el problema siguiente: Un fabricante está tratando de decidir las cantidades de producción para dos artículos: mesas y sillas.Programación Lineal
Lo que se pretende con el método gráfico es dar una visión geométrica del problema que queremos resolver. dan la solución al problema. las sillas utilizan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla. 8. El valor óptimo de la función objetivo se obtiene sustituyendo los valores óptimos de las variables de decisión en la función objetivo. para obtener la pendiente de la función objetivo. Escoja cualquier punto de ensayo que no pertenezca a la recta. Evalúe el primer miembro de la expresión. Los valores de las variables de decisión. en caso contrario será un punto no factible. 5. 3. 4. determine el vértice del conjunto factible que esté sobre la recta que representa la función objetivo. por ejemplo pasando por el origen. El margen de beneficio es el mismo para las mesas que para las sillas: 5 euros por unidad. Localice la región de soluciones factibles (Región Factible). Dibuje una recta arbitraria de la función objetivo. Convierta las desigualdades en igualdades y represente la rectas que representan estas ecuaciones. Dada la pendiente de la función objetivo y teniendo en cuenta si es un problema de maximizar o minimizar. 2. entonces todos los puntos que estén del mismo lado que el punto de ensayo satisfacen la desigualdad. Determine si el punto de ensayo satisface la desigualdad. 9. 11. Es evidente que su precisión no es la deseada. Se cuenta con 96 unidades de material y con 72 horas de mano de obra. Sustituya el punto de ensayo en el primer miembro de la desigualdad y obtenga el valor numérico. Determine la dirección ascendente o descendente de esta recta. pero nos puede dar una aproximación a lo que queremos resolver. Dibuje la gráfica de cada restricción sobre el mismo cuadrante no negativo. Solución: El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL. en este vértice. 6. El procedimiento a seguir es: 1.
34 Maximizar z = 5x1 + 5x2 en donde: x1 = número de mesas producidas x2 = número de sillas producidas Restricciones del problema (st): 12x1 + 8x2  96 6x1 + 12x2  72 x1  2 x1  0. Ahora se utilizará la función objetivo para seleccionar la solución óptima. x2  0 La gráfica asociada al problema es:
. se tiene: Maximizar z = 5x1 + 5x2 st 12x1 + 8x2  96 6x1 + 12x2  72 x1  2 x1  0. x2  0
Poniendo todo junto el modelo.
más lejana al origen. pero que todavía toque la región factible. tenemos:
El valor óptimo estará sobre la línea recta que representa a la función objetivo.Programación Lineal
Representando por líneas discontinuas la función objetivo moviéndose hacia el valor óptimo (máximo) del problema. Nótese que el punto óptimo está en la intersección de las líneas de restricción para materiales y horas de mano de obra. Las coordenadas de este punto
. la única tarea que queda es encontrar las coordenadas del punto. Las coordenadas de este punto se pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones. Esto se muestra en la siguiente figura:
Con el punto óptimo localizado gráficamente.
Si se da el caso de que los valores correspondientes a dos vértices coinciden. es decir. son paralelas. y en aquel en el que el valor de la función sea mayor (o menor) habremos alcanzado el punto óptimo buscado. que es precisamente el valor óptimo. cuando K tenga un número finito de vértices que no se puedan alcanzar todos (región convexa ilimitada). éstos serán adyacentes. iii) K  . Proposición 2. Si K es un poliedro convexo. Si la región es acotada lo único que hay que hacer es calcular el valor de la función objetivo en todos y cada uno de los vértices del polígono. de modo que a lo largo de ese lado del polígono se alcanza el mismo valor de la función objetivo. La sustitución de este punto en la función objetivo da la ganancia máxima: z = 5(6) + 5(3) = 45 euros. El conjunto de soluciones factibles de un problema de programación lineal es un conjunto convexo. el valor óptimo de la función objetivo se alcanza en uno de los vértices del polígono que limita la región.6. Designemos por K el conjunto de las soluciones factibles de un problema de programación lineal. pero el máximo podría ser ilimitado.
2. Si la región factible no es acotada. El problema tiene solución.3). por lo que K es: i) K = . Toda solución factible podrá representarse como una combinación convexa de las soluciones factibles extremas de K (salvo el caso en que el poliedro sea ilimitado).2) y (2. pero si lo hace. éste se encuentra en uno de los vértices de la región. las líneas de nivel tienen la misma pendiente que la recta que contiene a ese lado del polígono. 3). la función objetivo no alcanza necesariamente un valor óptimo concreto. o a lo largo de uno de los lados.
En un problema de Programación Lineal con dos variables. Propiedades de las soluciones
Las soluciones de un problema de programación lineal tienen diversas propiedades. cuando K tenga un número finito de vértices que se puedan alcanzar todos (poliedro convexo).1. K es una región de Rn determinada por la intersección del conjunto finito de restricciones lineales (2. si la región factible existe y es acotada. En este caso. entonces K es la envolvente convexa de los puntos extremos de K. Existe solución de valor finito de la función objetivo.36
resultan ser (6. alguna de las cuales vamos ver. ii) K  . Demostración
. no tiene solución el problema de programación lineal.
Si formamos un vector X que sea combinación lineal de éstos dos: X =  X1 + (1-) X2. esto significa que cT X0  cT X para cada XK. i  0 .
Se pueden dar los casos siguientes: i) Si X0 es un vértice de K. X1 0.
. A X2 = b. X2. entonces A X1= b. entonces X0 se podrá poner como una combinación lineal convexa de ellos: X0 =
i Xi . además. también se alcanza en cualquier combinación lineal convexa de los mismos. si este mínimo se alcanza en varios puntos. ii) Si X0 no es un vértice de K. X2  0. Si K es un poliedro convexo.1) alcanza su mínimo en un vértice de K. Proposición 2. Demostración Sean X1. Xp los vértices de K y sea X0 una solución factible mínima.2. AX =  AX1 + (1-) A X2=  b + (1-) b =b por lo que X es también una solución factible.….Programación Lineal
Sean X1 y X2 soluciones factibles. ya estaría demostrado. entonces la función objetivo z dada por (2.
x2. se cumple que AX1=b y AX2=b. X1.…. Xq y que X es una combinación lineal convexa de ellos: X=
i Xi . 0.….….…. Si tenemos un conjunto de k vectores A1. Proposición 2. 1]. el punto X = (x1.…. [0. 0)T con X1  X2. entonces. por lo que podemos escribir: x11 A1+ x12 A2 +…+ x1k Ak = b x21 A1+ x22 A2 +…+ x2k Ak = b
. 0)T X2 = (x21. 0.…. x1k.…. X2.3. A2. X2K Puesto que las coordenadas de las soluciones factibles son no negativas y 0 deberá ocurrir que las n-k coordenadas últimas de X1 y X2 fueran iguales a cero: X1 = (x11. xk. x12. es decir. x2k. 0. Ak. por ser soluciones factibles. Demostración Supongamos que X no fuera vértice. que existe un vértice de K en el que la función objetivo z= cT X alcanza su valor mínimo. 0)T es un vértice del conjunto convexo K de soluciones factibles. que sean linealmente independientes y de forma que: x1 A1+ x2 A2 +…+ xk Ak = b con las xi  0. Además.
cT X = cT ( 1 X1 + 2 X2 +…+q Xq) = 1 cT X1 + 2 cT X2 +…+q cT Xq = = (m1 + m2 +…+mq) = m (1 + 2 +…+q) = m con lo cual la proposición queda demostrada.38 Supongamos que cT X1 = min cT Xi
m  cT ( 1 X1 + 2 X1 +…+p X1) = cT X1(1 + 2 +…+p) = cT X1  m por consiguiente cT X1 = m. i  0 .…. x22. entonces podría expresarse como combinación lineal convexa de dos puntos distintos de K: X =  X1 + (1-) X2. Para probar la segunda parte de la propiedad supongamos que z alcanza su valor mínimo en X1.
x22) A2 +…+ (x1k . entonces los vectores Ai asociados con las coordenadas xi positivas forman un sistema linealmente independiente. m de estas coordenadas xi son positivas. x2. Si tenemos un vector X = (x1.x21) A1+ (x12 . A2. xn)T es un vértice de K. Ak linealmente independiente llegamos a la conclusión de que: x11 = x21 x12 = x22 … x1k = x2k es decir. entonces : x1 A1+ x2 A2 +…+ xk Ak = b Si los vectores A1. Demostración: Supongamos. lo que contradice el hecho de haber supuesto X1  X2. Si los sumamos y restamos:
.4. para simplificar.…. podremos encontrar una combinación lineal de los mismos igual a cero con algún coeficiente no nulo: 1 A1+ 2 A2 +…+ k Ak = 0 Así tenemos:
donde  > 0. de lo que se sigue que. A2. que las k primeras coordenadas son las no nulas. que X1 = X2.Programación Lineal
Restando las expresiones anteriores obtenemos: (x11 . Ak son linealmente dependientes. Proposición 2. por lo que necesariamente X debe ser un vértice de K.….….x2k) Ak = 0 y por ser los vectores A1. a lo sumo.
xk +  k. Los n-r vectores restantes dependen de A1 . x2 +  2. prueba que existen k  m vectores linealmente independientes. A2 . k ) Ak = b De manera que tenemos dos soluciones distintas del sistema de ecuaciones: X1 = (x1 +  1. 0. 1 ) A1 + (x2 . 0. A2.4. . Supongamos que k  m y que podemos encontrar solamente Ak 1 .…. 2x2.…. 2 ) A2 +…+ (xk . Ar vectores adicionales tales que el conjunto A1 . . Ak 1 .… 0)T= 2X Despejando X= ½ (X1 + X2).….40
xi Ai +   i Ai = b xi Ai . Demostración La Proposición 2. xk . x2 . Ar . A2 . Ar .5 queda comprobada. Ak sean linealmente dependientes. m de las xi serán positivas. como estos vectores son m-dimensionales no podremos tener más de m linealmente independientes. . 1. desarrollando las expresiones anteriores: (x1 +  1 ) A1 + (x2 +  2 ) A2 +…+ (xk +  k ) Ak = b (x1 . A cada punto extremo del poliedro convexo se encuentra asociado un conjunto de m vectores linealmente independientes del conjunto dado A1 .….  i Ai = b
Es decir. de ahí que. 2. De ahí que. no puede hacerse la hipótesis de que los vectores A1. por tanto son linealmente independientes y. Am asociados con cada punto extremo. An .… 0)T Sumando X1 y X2. . Proposición 2. k. . resulta: X1 + X2 = ( 2x1. Para k =m la propiedad 2. 0.5. para r m es linealmente independiente.… 0)T X2 = (x1 . como máximo. Esto contradice la suposición de que tenemos siempre un conjunto de m vectores linealmente independientes A1 . Ak . lo cual contradice el hecho de que X sea vértice.
. . 2xk .
. de coordenadas no negativas.…. es decir.. A cada vértice de K se puede asociar una base de dimensión m del conjunto de vectores A1. A2. x2. xm.…. las diversas circunstancias de su preparación antes de aplicar el algoritmo y los casos especiales identificables en la tabla solución (última tabla). entonces hay un vértice de K (conjunto de soluciones factibles) en el que la función objetivo alcanza su mínimo ( o su máximo). Sea el problema de programación lineal: Min z = cTX st AX = b X0 Supongamos que tenemos una solución factible básica. es decir. se conoce una solución de punto extremo en términos de m vectores A j del conjunto original de n vectores. 0)T que verifica:
.7. si x1 A1+ x2 A2 +…+ xn An = b y las xi > 0 son coeficientes de los vectores Ai linealmente independientes. que las variables no nulas sean las n-m finales X = (x1. Max z = Min (-z) Cada solución factible básica corresponde a un vértice de K. An. 0.…. (Caracterización de los vértices de K) El vector X = (x1. Demostración La demostración es inmediata aplicando las proposiciones 3 y 4. Algoritmo del Simplex
El alumno debe aprender la utilización del método del simplex que proporciona la solución de un problema de programación lineal.   Aplicando un algoritmo llamado método del Simplex en un número finito de pasos (en general entre m y 2m) se llega a la solución factible óptima.Programación Lineal
Teorema 2. xn)T.. Resumiendo lo anteriormente expuesto mediante propiedades y teoremas tenemos: Si existe solución al problema de programación lineal.
2. x2. Podemos hacer que este conjunto de m vectores linealmente independientes sean los primeros m. m=   . es un vértice de K (conjunto convexo de soluciones factibles).. El máximo número de vértices que puede tener el convexo K es Cn.1.
A2... j  1. m tendremos que el vector X’ = (x’1.6) donde z es el valor de la función objetivo en X. x2=b2... n
11 A1   21 A2     m1 Am  A1  A   A     A  A  12 1 22 2 m2 m 2  . Tomemos un j de modo que Aj no esté en la base dada....3)
Observando en (2. x’n)T es una solución factible.. i=1... xm=bm....1) le restamos (2.1) que. x’2.. m x’i = j  0. solución factible. 1n A1   2 n A2     mn Am  An  y la función objetivo z tomará en el vértice X el valor: z = c1 x1 + c2 x2 + … + cm xm
Como los vectores Am forman una base en el espacio m-dimensional.j  2 j ) + … + cm (xm ... Am es la base canónica de los vectores unitarios entonces x1=b1.. x’2... 2. toma el valor z’ = c1 x1’ + c2 x2’+ … + cm x’m + j cj = = c1 (x1 .…..j  1 j ) + c2 (x2 .. pues bien si a (2.. si A1...2) multiplicada por un escalar j.....j (zj -cj) (2.5)
La función objetivo en X’ = (x’1.2)
(2. si elegimos j  0..... resulta: (x1 .j  m j )Am + j Aj = b (2.. . de modo que xi ... podemos expresar cada uno de los n vectores dados como combinación lineal de los vectores de esa base:
Ai  A j ..…. en los demás casos (2.. x’n)T.....j  i j 0.j  2 j )A2 + … + (xm . . . x j  0..4)
con lo cual. Rm.j  i j 0 para i=1. y zj viene dada por la expresión:
......j  1 j )A1 + (x2 .j  m j ) + j cj= = z .  j
Investigación Operativa (2...…. …. 2.42
x1 A1  x2 A2    xm Am  b.... donde: x’i = xi . 2. i=j x’i = 0..
…. Am son linealmente independientes. en (2.j  i j 0.
x    j = min  i /  ij  0 (2. z’= z.8) se alcanza.7)
así pues. por lo que la
nueva solución factible X’ = (x’1.m+1  1. x’n)T = (0. Para probar que los vectores A2. j 
.m1  ij 
(2.j (zj -cj). a continuación calcularemos los productos j (zj -cj) y nos quedaremos con el índice j que da el producto mayor. éstas corresponden a las variables cuyos vectores asociados.….5) se tenga que j(zj-cj) sea positivo y máximo. 0. x’2. por otra parte.….10). esto quiere decir que existirá i tal que 2 A2 +  3j A3+ … +  m Am+  m+1 Am+1 = 0 (2.10) para algún i distinto de cero y. Am+1 son linealmente independientes. Estudiaremos dos casos: i) ii) ij > 0 ij  0
Caso i): j  0. por tanto. El procedimiento consiste. en calcular las cantidades (zj -cj) > 0 observando las relaciones (2. para i=1. por ejemplo. obtenemos:
ello significará que x 1’ = x1 . mejoran el valor de la función objetivo. con lo cual z’<z. m+1.  i j > 0 x’i = xi .8) i    ij 
y esto para cada j para el que se cumpla (zj -cj) > 0. A3. Am+1 son linealmente independientes (Vea el teorema de caracterización de los vértices de K). es decir:
x  x1   m+1 = min  i /  ij  0 = i   1. A3. m+1 = 0. ello significará que seleccionamos el vector Am+1. A3. 0)T será un vértice de K (conjunto de soluciones factibles) si los vectores A2.6) vemos que debemos seleccionar j y j de forma que verificándose (2. deberá ser m+10. despejando Am+1 de (2. si el mínimo en (2. supongamos que fueran linealmente dependientes.m1
 1.…. x2’. supongamos que éste es j=m+1. Por tanto. si los incluimos en la base. m+1 = x1 -
1.5). ….…. xm’.Programación Lineal zj = c1  1 j + c2  2 j + … + cm  m j (2. puesto que los vectores A2.
en cuyo caso ya no se podría disminuir la función objetivo y.11) de (2. Caso ii): j  0..11)
Am+1 =  2 A2 +  3 A3 +…+  m Am Restando (2. con j=m+1.….
. m+1 A2 +…+  m. 2) A2 +…+ ( m.. m+1 . al ser A1. es decir. por lo que X’ es un vértice de K y además vuelve a ser una solución factible básica puesto que tiene n-m coordenadas nulas y el resto son no negativas. En consecuencia. m+1 A1 +  2.. El proceso se volvería a repetir tomando X’ como solución factible básica inicial y se iría repitiendo el proceso hasta encontrar zj-cj  0 para todos los valores de j=1.  i j  0 x’i = xi ..cj ) . por tanto. m+1 A1 + ( 2. . m+1 Am 0 = 1. .m Am m1 m1 m1
(i=2. únicamente resulta sencillo en problemas con pocas variables de decisión.2).9)). El más famoso de los métodos de resolución de programas lineales (el método Simplex) está basado en la localización de una solución básica inicial y el paso de una a otra hasta encontrar la óptima. ocurrirá que z’ tiende a menos infinito. . m)Am
por lo que.. Am+1 son linealmente independientes. se habría alcanzado el mínimo con el vector X que se tuviera en esa etapa. no existe solución. Am linealmente independientes obliga a que 1. con (zj . sin embargo se supuso positivo (vea (2.…. m) (2.44 Am+1 = i  m1
  2 A2 . m+1 .cj ) >0 Como se puede elegir un j tan grande como quiera. encontramos que Am+1 = 1. A2.j  i j z’ = z. A2. Por supuesto encontrar todas las soluciones básicas de un programa lineal requiere de grandes esfuerzos de cálculo.3 A3 -…. n. A2. Cualquier problema de programa lineal puede reducirse a la búsqueda de mínimos en un conjunto finito de puntos (las soluciones básicas factibles).m+1=0 y. 2.j (zj .
para un humano no supone ningún problema reconocer los ceros y darse cuenta que al multiplicar un número por cero resulta cero. el método Simplex no resulta muy económico desde un punto de vista computacional. la magnitud de los problemas lineales que aparecen en la mayoría de las situaciones reales hace impensable su tratamiento mediante el método simplex de forma manual. En tales situaciones debe recurrirse al uso de los computadores electrónicos. Sin embargo.
. ya que se almacenan y calculan muchos números que no son estrictamente necesarios. Sin embargo.Programación Lineal
Dentro de los aspectos computacionales. Por ejemplo. un computador no reconoce esas situaciones y pierde tiempo realizando operaciones que realmente no son necesarias. o que sumar cero a un número no altera el resultado. en las tablas del simplex aparecen gran número de ceros.
.. . con yi  0
y valor de la función objetivo: z = c1 y1 + c2 y2+ … + cn yn se verifica z0  z. .cj )  0  zj  cj y sustituyendo en la expresión (2.. xn)T un punto extremo en el cual la función objetivo vale z0 y para el que se verifica que (zj ..….…. entonces.. ... j (j=1. Demostración Sea X = (x1.cj )  0. . 2.cj )  0... j (j=1.2.12)
Como (zj . n)..13) cada zj (j=1. 2. yn)T. Si en algún paso (puede ser el primero) del método simplex se
verifica que (zj . el último vértice obtenido es la solución óptima. y2. 2. 2... j (j=1..
(2. n) por su valor zj = c1  1 j + c2  2 j + … + cm  m j = tenemos: (  c i  i 1 ) y1 + (  c i  i 2) y2+ … + (  c i  i n) yn  z
Agrupando términos en c i (i=1. n) Y= (y1. x2..12) cada cj por zj tenemos: z1 y1 + z2 y2+ … + zn yn  z (2. Hemos de probar que para cualquier otra solución (zj . n).cj )  0..13)
Sustituyendo en (2. 2..46
Investigación Operativa Teorema 2.. m) se tiene: c 1 (   1 j y j) + c 2 (   2 j yj) + … +cm (  
x2 =   2 j yj . 2. n) por su valor: (2. Resuelva mediante el Método Simplex el problema de programación lineal siguiente: Min z = –5x1+2x2-3x3 st 2x1+2x2-x34
. Am linealmente independientes. A2. …. xm =   m j yj
Sustituyendo en (2.14) se tiene: c1 x1 + c2 x2+ … + cm xm  z es decir z0  z . b se escribe de forma única..Programación Lineal y 1 A1+ y 2 A2+ … + y n An = b Sustituyendo Aj (j=1. por lo cual: x1 =   1 j yj . .. Ejercicio 1. .15) para cada uno de los j: y 1 (   i 1 Ai) + y 2 (   i 2 Ai) + … + y n (   i n Ai) = b
Como X es un punto extremo x 1 A1+ x 2 A2+ … + x m Am = b y por ser los vectores A1..15)
Sustituyendo este valor en (2...
z1 = 0.2=0.(-5)=5
. ii) Calculamos (zj -cj). 0. 3.x2+x3+x5 = 3 2x1+x2+3x +x6= 5 xi  0 (i=1.3+0.   x  v) El valor de i que hace min  i /  ij  0 nos proporciona el vector i    ij  i-ésimo que sale de la base y. tenemos. zj. Por ejemplo.5x1+2x2-3x3+0x4+0x5+0x6 st 2x1+2x2-x3+x4 = 4 3x1.48 3x1.j
El vértice inicial de partida es X=(0. i    ij  ij  iv) Buscando que j (zj -cj) sea positivo y máximo.2+0. 0. 2.
x  b   iii) Para los valores (zj -cj) >0 calculamos j = min  i  i /  ij  0 . 2. para j=1.x2+x33 2x1+x2+3x35 xi  0 (i=1. Para ver que vector sale de la base y cuál entra operamos de la forma siguiente: i) Calculamos zj = c1  1 j + c2  2 j + … + cm  m j.c1 =0 . el valor de j que hace max j (zj . 3) Primera tabla Se lleva a la tabla los datos del problema y se comienza a operar de acuerdo con el algoritmo del simplex: cj -5 b A1 4 2 3 3 5 2 0 0 zj-cj 5 5 j(zj-cj) 2 A2 2 -1 1 0 -2 -3 A3 -1 1 3 0 3 5 0 A4 1 0 0 0 0 0 A5 0 1 0 0 0 0 A6 0 0 1 0 0 1 3 2 -3 1 5/2 5/3 1 5/3
cB 0 0 0 z. de manera que tengamos una base canónica para comenzar el método del simplex: Min z = . 5)T. 4. 3)
Pasando el problema a forma estándar añadiendo variables artificiales. z1 .cj) nos
El vector que entra en la base es el A1 ( max 1 (z1 –c1)=1.. deberá valer uno y el resto cero. tenemos: cj b 2 1 3 -5 A1 0 1 0 2 A2 8/3 -1/3 5/3 -3 A3 -5/3 1/3 7/3 0 A4 1 0 0 0 A5 -2/3 1/3 -2/3 0 A6 0 0 1
x b 3 . i2  21  21 3 
El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote. 2.5=5). en nuestro caso el 3..El vector que sale de la base es el A5 (1 = min  2  2   =1). n). Este proceso se repite de forma iterativa hasta que se verifique (zj ..Programación Lineal
Realizadas las operaciones correspondientes. tenemos: . que se genera en el cruce del vector que entra y el vector que sale.cj )  0. . Veamos como se obtiene   : 1   0  
Llevando lo anterior a la tabla. El vector A1 que entra en la base se convierte en un elemento de la base canónica. j (j=1. El elemento pivote (que ha de ser un 1) se forma en el cruce del vector  A1    0 que entra con el que sale (A1/A5).
5714 -3 9/7=1. x2=0 (no aparece).2857. x3=9/7=1. por lo que hemos llegado a la etapa final.. j (j=1. j -47/7=-6. 0. n). Para buscar la solución dentro de la tabla miramos la columna b y encontramos: x1=4/7=0. A5. 9/7.50
Segunda tabla cj -5 Base cB b A1 0 2 0 A4 -5 1 A1 1 0 3 0 A6 -5 -5 z. La solución mediante la matriz inversa asociada a la tabla del simplex.5714. z = -6. A6}=  0 3 / 7  1 / 7  0  2 / 7 3 / 7  
. en este caso a los vectores A4. 29/7. zj.1448 -5 4/7=0.7142 zj-cj j(zj-cj)
Observando la tabla tenemos (zj . zj. 2. j zj-cj 0 j(zj-cj) Entra A3 y sale A6.. A5 y A6 de la tabla:
1  8 / 7 5 / 7     {A4.2857 z. 0)T. Tercera tabla cj Base A4 A1 A3
cB b 0 29/7=4.7142 El vértice final obtenido es X=(4/7.. B-1 la podemos encontrar directamente en la última tabla del simplex observando los vectores correspondientes a los de la base inicial. . 0.cj )  0.
000000 1.000000 1.000 1.000000
DUAL PRICES 0.000 -1.857 -0.000 0.285714 0.000 1.000000 1.000 -0.000 0.714 4.571 0.143 0. A1 y A3:
1 2  1   B  {A4.285714 REDUCED COST 0.571429 0.286
SLK 4(A6) 0.285714 0.Programación Lineal
y la matriz B se obtiene de la primera tabla mirando la base que figura en la última tabla del simplex.000000
SLACK OR SURPLUS 4. A1. tenemos:
Min -5x1+2x2-3x3 st 2x1+2x2-x3 <= 4 3x1.000
SLK 2(A4) SLK 3(A5) 0.714 -0.714286 VALUE 0.143
6.000 0.571429
X1(A1) 0.x2+x3 <= 3 2x1+x2+3x3 <=5 LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 -6.714
X3(A3) 0.142857 0.000 0.000 0.571
X2(A2) 1. A3}=  0 3 1  0 2 3   
Si resolvemos el ejercicio anterior con el programa LINDO. A4.000 1.286 1.429 0.286 3.000000 0.571 0.143 0.
1  8 / 7 5 / 7     {A4. 2. A3}=  0 3 1  0 2 3   
Ejercicio 2. 3) Para ciertos valores de los recursos. c. A5.
cB 0 0 z. A6}=  0 3 / 7  1 / 7  0  2 / 7 3 / 7  
1 2  1   B  {A4.429 1. b) Los valores de: a. zj-cj
. c3. A1. la solución es: cj b 30 10 -150 -5 A1 1 0 0 -2 A2 b c a c3 A3 2 -8 -7 0 A4 1 -1 d 0 A5 0 1 e
Calcule: a) Los recursos. d. b.52
4 0. Considere el problema siguiente:
c3= -3
2. b = 5. necesitaremos de lo que se conoce como variables artificiales. Las primeras se introducen para convertir desigualdades en igualdades. para iniciar el método simplex. b) a= -23. e= 0.
. Veamos como siempre es posible conseguir esto. La base canónica inicial la configuraremos con las variables de holgura más las variables artificiales necesarias hasta tener esa base canónica. Para conseguir partir de una base canónica. sale de la base A4 y entra A1
cj b b1 b2.Programación Lineal
Tabla 2 Por la información que nos proporciona la tabla del enunciado. zj-cj
Identificando. c= -10. d= -5.8. podremos aplicar directamente el método del simplex. Si al introducir las variables de holgura necesarias para escribir el problema en forma estándar ya tenemos la base canónica. Éstas construyen un problema artificial más conveniente desde el punto de vista del método simplex.b1=10.b1 -150 -5 A1 1 0 0 -2 A2 5 -10 -23 -3 A3 2 -8 -7 0 A4 1 -1 -5 0 A5 0 1 0
CB -5 0 z. un método que nos ayude a resolver los problemas que contengan variables artificiales. b2= 40. a continuación. b2. En la mayoría de los casos la situación anterior no se producirá. mientras que las variables artificiales se introducen para facilitar el comienzo del método simplex. Veamos. Determinación de una base inicial
Hemos supuesto en el método del simplex que partíamos de una primera solución extrema a la cual teníamos asociada una base canónica. por lo que tendremos que recurrir a métodos que nos conduzcan a él. Es oportuno resaltar la diferencia entre variables de holgura y variables artificiales. tenemos: a) b1= 30.
Min z = cTX + M 1T Xa st AX + I Xa =b X  0. con lo cual tenemos el sistema siguiente: AX + I Xa = b X  0. y que entren las otras variables. Consideremos el siguiente problema de programación lineal planteado en su forma estándar: Min z = cTX st AX = b X0 Añadimos en las restricciones las variables artificiales necesarias para tener en la primera tabla del simplex una base canónica. hasta que todas quedan fuera de la solución. con todas las variables artificiales iguales a cero. Las iteraciones del método simplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una. X=0 Debemos buscar la forma de hacer salir las variables artificiales. Para ello les asociamos un valor muy grande M ( no es necesario especificar el valor de M) en la función objetivo. Xa= 0.
2. es decir. entonces la solución obtenida es única y óptima.8. pueden presentarse los casos siguientes: a) Tengamos solución finita: i) Que el problema admita una solución óptima.1. las Xa. Xa  0 Tenemos como solución inicial: Xa =b. Método de la “M” o de Penalización
En este método la función objetivo se modifica para que imponga una penalización muy grande sobre las variables artificiales en el caso de que adquieran valores mayores que cero. Xa  0 En la resolución del problema por este método.
zj.. no tenemos solución.. iv) Exista al menos una variable artificial que sea positiva.j 75M zj-cj j(zj-cj)
. Xa= 0.x1-6x2+ 4x3+ 0 x4+ 0 x5+ M x6+ M x7 st x1+2x2-x3 + x6 =20 2x1+ x2+x3 + x4 = 40 2x1+ x2+4x3 – x5+ x7 = 55 xi  0 (i=1. b) Tengamos solución no finita: iii) Con todas las variables artificiales iguales a cero. entonces el problema original es imposible. Min z = .. 2. 2. Consideremos el siguiente problema: Max z = x1+6x2-4x3 st x1+2x2-x3 =20 2x1+ x2+x3  40 2x1+ x2+4x3  55 xi  0 (i=1. 3) Como explicamos anteriormente.Programación Lineal
ii) Que el problema admita una solución óptima en la cual encontraremos al menos una variable artificial distinta de cero. en caso de que exista. . 7)
cB b M 20 0 40 M 55 z. para resolver este problema. Xa 0. en este caso tenemos una solución no finita. debemos construir un problema “artificial” que tiene. la misma solución óptima que el problema real. entonces el problema original es imposible.
2. n).56
A los valores que hayan resultado ser (zj -cj) >0...j -50 zj-cj
Observando la tabla tenemos (zj .. . Este proceso se repite de forma iterativa hasta que se verifique (zj . zj. ya nunca más volverá a entrar.j45M-60 3M/2-3 zj-cj 3M/2-2 j(zj-cj) cj -6 A2 1 0 0 -6 0 4 A3 -1/2 3/2 9/2 3M 9M/2-1 45M+10 0 A4 0 1 0 0 0 0 A5 0 0 -1 -M -M M A6 M A7 0 0 1 M 0  20 10
Entra A3 y sale A7. j (j=1. que.
cB b -6 15 0 15 4 10 z. . por corresponder a una variable artificial. que se genera en el cruce del vector que entra y el vector que sale. en nuestro caso el 2. elegimos la de mayor diferencia y aplicamos el criterio
x    j = min  i /  ij  0 i    ij   y buscando que j (zj -cj) sea positivo y máximo.... deberá valer uno y el resto cero. j (j=1. n). por lo que hemos llegado a la etapa final.cj )  0.
-1 cB b A1 -6 10 1/2 0 30 3/2 M 45 3/2 z. ya nunca más volverá a entrar. tenemos que entra A2 y sale A6.cj )  0. zj. que. El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote. por corresponder a una variable artificial. 2. en nuestro caso se da para varios j. Para buscar la solución dentro de la tabla miramos la columna b y encontramos:
Xa  0 Si el problema original tienen solución factible.
Fase II: En esta segunda fase. x4 =15. Xa  0 Su resolución se abordará en dos fases:
Min z = 1TX a st AX + I Xa =b X  0. resolveremos el problema original planteado utilizando la última matriz obtenida en la Fase I y por tanto dicha base. el mínimo del problema anterior se alcanzará cuando las variables artificiales Xa =0 y z=0. x2 =15. x2 =15.2 Método de las dos fases
Supongamos un problema planteado en su forma estándar Min z = cTX st AX = b X0 Añadimos en las restricciones las variables artificiales. x5= 0.
. con lo cual tenemos el sistema siguiente: AX + I Xa =b X  0. x3= 10. x3= 10.Programación Lineal
x1= 0.8. z = 50
2. la solución del problema original planteado (maximización) es: x1= 0. z = -50 Luego. Xa. necesarias para tener en la primera tabla del simplex una base canónica.
Vamos a resolverlo por el método de las dos fases. El problema con las variables de exceso . tenemos: Primera tabla
Solución de la tabla. holgura y artificiales y la función objetivo de la primera fase (la función objetivo del enunciado se optimiza en la segunda fase) es : Min z = a1+a2 st x1+x2.x1+x2 -h2+ a2 =1 x2+ h3 =3 pasamos a la tabla los datos y operamos según el algoritmo del simplex. x2=1.h1+ a1 =2 . Para los zj-cj >0
. z=1.2x2 st x1 +x2  2 -x1 +x2  1 x2  3 x1 0 . a1=1.58 Min z = x1. h3=2. al ser la función objetivo de minimizar y tener zj-cj positivos la solución no es óptima.
siendo a1 la fila donde se alcanza el valor mínimo de j y por lo tanto la variable que deja de ser variable básica. 0. será la nueva variable básica.1 0 1 3 3 0 3 1 0 -
Solución de la tabla. tomamos x1 por tener mayor zj-cj . 0. h1 será la nueva variable básica. con lo cual terminamos la primera fase al obtener en la próxima tabla z=0 con a1=0. siendo h3 la fila donde se alcanza el valor mínimo de j y por lo tanto la variable que deja de ser variable básica. a2=0. 0)T. y el valor máximo de j(zj-cj ) se alcanza en x1 y en h2. x2=2 h3=1. cj 1 -2 0 0 0 Base cB b A1 A2 A3 A5 A7 A5 0 2 1 0 0 1 1 A2 -2 3 0 1 0 0 1 A3 0 1 -1 0 1 0 1 z zj j -6 0 -2 0 0 -2 zj-cj -1 0 0 0 -2 El punto extremo es X1=(0.Programación Lineal
calculamos j. h2=1. 0.
. Para los zj-cj >0 calculamos j. Introducimos entonces la función objetivo original min z=x1-2x2 y continuamos con el algoritmo del simplex:
0 A7 A3 A5 0 . 3. z=-6. la cual no volverá a entrar en la base y por lo tanto se puede eliminar de la tabla. z=-4. la solución no es óptima.
de manera que. obtendríamos todos los vértices que son soluciones óptimas. pero que cumple (zj . Compruebe. . por lo cual el problema tiene infinitas soluciones. j.cj ) = z no hemos mejorado la solución anterior.. 1. Soluciones múltiples
Cualquier problema de Programación Lineal con soluciones óptimas múltiples (y una región factible acotada) tiene al menos dos soluciones factibles en los vértices que son óptimas.cj )  0. que el problema siguiente presenta dos puntos extremos. X2=(4. Repitiendo este proceso para cada una de las “j” que no pertenecen a la base y verifican (zj .cj)= 0. en un número finito de iteraciones llegábamos a la solución óptima. 0)T así como toda combinación convexa de dichos puntos..cj)= 0.x3  1 x2+ 2x4  8 xi  0 (i=1. Min z = x1-2x2+3x3 st x1. El método simplex se detiene automáticamente al encontrar una solución factible básica óptima. esto nos indicará que existe multiplicidad de óptimos. 2. se encuentra observando si tengo algún vector j. Soluciones degeneradas
Al desarrollar el algoritmo del simplex supusimos que las soluciones eran siempre no degeneradas. Toda solución óptima es una combinación lineal convexa de las soluciones factibles básicas óptimas.j (zj . tal que no pertenece a la base. mediante el método simplex. 0. también sería solución óptima. Una vez que el método simplex encuentra una solución factible básica óptima. Tomando una combinación lineal convexa de ellas.10.. 1. Supongamos que ya hemos encontrado una solución óptima (mínima) de un problema y que se verifica (zj . La función objetivo es: z’ = z . 6) Los puntos extremos son: X1=(2. 7/2.
2. se puede detectar si existen otras y.
.9. 0.x2+x3 + 2x4 =10 x2. 0. 0)T. si es así. 4. 0.60
2.…. Consideremos el siguiente problema de programación lineal: Min z = cTX st AX = b X0 donde A es una matriz de orden mxn y sea rang (A. Este caso se presenta cuando se valora una solución básica no única. Am. la cual se tiene con al menos una variable básica de valor cero en el sistema de m restricciones.…. 0)T. un punto extremo degenerado. Se identifica en la tabla simplex porque al menos una variable básica tiene valor cero en la columna de solución. Descomponiendo la matriz A de forma que A=(B. N) donde Bmxm es la matriz básica y N(mx(n-m)). A2. es decir. A2. El método del simplex revisado
Un procedimiento más eficiente que el simplex en su versión matricial es el llamado simplex revisado. entonces. Am) es la matriz básica.
x    Ahora bien. si al calcular el valor de j = min  i /  ij  0 existen varios i i    ij  xi tal que minimizan .. esto es. . estaríamos en un punto extremo que tiene menos de “m” coordenadas positivas.. XB = (x1. b) = rang (A) = m. no se podría hacer salir a la vez a todos ellos. en el nuevo punto extremo al que se pasan todas las coordenadas de X para las cuales se alcanza ese mínimo serían nulas.11.. 0. tenemos BXB = b. la matriz B= (A1. XB = B-1 b
.. la matriz no básica (los Ai que no son de la base). xm. X  Cualquier solución básica es de la forma X=  B  X   N donde XN = 0 y BXB = b Si XB es una solución factible básica. Denotemos por Ai la columna i-ésima de la matriz A y supongamos que los m vectores linealmente independientes son los m primeros A1.Programación Lineal
 ij elegir uno cualquiera y. alguna de ellas debe ser restricción redundante que contiene sólo un punto vértice del conjunto factible. x2.
al vector columna mx1 se le denomina vector de multiplicadores del simplex asociado a la base B.5 0. Dada la tabla óptima del Simplex:
cj b 0.5 -0.5 1.  2 j.62 y puesto que
esto es Aj = BXj.5 -0.75 3.5
a) Haciendo uso de la matriz básica y/o de su inversa formule el problema de programación lineal que corresponde a la tabla anterior. Xj= ( 1 j.25 -4.5 -0. Escriba la solución en el recuadro adjunto.5 -0.5
A5 -0.75 1. si se sabe que la primera restricción es () y el resto ().75 zj-cj
A4 0. Xj = B-1 Aj
Donde T= cBT B-1. Veamos el ejercicio siguiente.5 0. ….
b) Formule el problema Dual y de la solución sin hacer operaciones.  m j )T.5 -0.
75    5.Programación Lineal Solución: a) La matriz inversa se obtiene directamente de la tabla:
0.5  0   0.  2  1 1   T T tenemos: c =  B=(0 0.25   4       La formulación del problema sería:
2 x1+ x2  3 3x1+x2 5.5 x1+x2  4 x1.5   1 0 1 3.5  0  0. B =   1 0. 2.5  . 3):  2  1 1 1   2       Aj=B Xj=  3 0 1 0    3  para j=1  1 0 1 0   1        2  1 1 0  1      A2=B X2=  3 0 1 0   1  1 0 1 1  1       2  1 1 0.5 0.5)  3 0 1  (2 0 1)  1 0 1  
. x2  0
b) Operando con el vector de multiplicadores del simplex asociado a la base B.5  0.5 1.5   
A continuación se calculan los vectores Aj (j=1.75   3       B X=b=  3 0 1 1.
.. B1=I..... B-1 B1= R
donde R es la matriz identidad reemplazando la r-ésima columna por el vector columna Xj.... en general la inversa de la base de la k-ésima iteración se obtiene Bk-1 = Ek-1 Ek-2 ….... Forma producto de la inversa
Sea B una base y B-1 su inversa. Siguiendo un proceso iterativo. podemos conocer B1-1 en términos de B-1... E2 E1
... 0     ..... Cuando comenzábamos el método del simplex. es decir..   0 0 ......  .. Am) y supongamos que al realizar el cambio de base introducimos el vector Aj y sale Ar B1= (A1.     0 0 .. tomábamos la base canónica. 1 mj   La inversa de R la denotamos por E y viene dada por
1 0 .   2 j /  rj .. 1 j ...... 0     0 1 ....... Ar+1. si realizamos un cambio de base a la base B1.... a la matriz E se la denomina matriz elemental.. Aj.  E=R =  0 0 . .….. 0     0 1 .. 0  R=    .......1.. Determinación de la inversa.... sea B= (A1...... esto es:
1 0 ....... Am)..…..... Ar-1.. En efecto.11..... A2... Ar+1..   mj /  rj ....... Ar-1.... B1-1 = I y XB = b. A2.... tenemos: B2-1= E1 B1-1 = E1 I= E1 B3-1= E2 B2-1 = E2 E1 y... Ar..  1 j /  rj ... 1 /  rj . 1 Entonces B1-1= R-1 B-1= E B-1.. Xj = B-1 Aj.64
2.. 0    -1  .  2 j ..
En cada iteración hay que controlar si todos los (zj . de lo contrario el problema es degenerado. en tanto que todos los términos constantes (recursos) aparecerán a la derecha. Si el programa requiere que todas las variables sean no negativas.x2+x33 2x1+x2+3x35 xi  0 (i=1. E2E1Aj La última columna representa la situación en la k-ésima iteración.cj) > 0 y Xj  0. E2E1Aj-cj
B-1 XB = B-1 b Xj = B-1 Aj ….
2. zj -cj =cB Ek-1Ek-2 …. 2.2. tenemos: Min z = –5x1+2x2-3x3 st 2x1+2x2-x34 3x1. 2. utilizaremos el programa LINDO (L = Linear IN = Interactive D = Discrete O = Optimizer). Etapas del método del simplex revisado
T -1 T T= cBTB-1 z = cB B b zj . las de valor cero indicarán que el recurso se ha consumido en su totalidad. Todas las variables de las restricciones deben aparecer en el primer miembro.cj = TAj .Programación Lineal
que expresa la inversa como producto de matrices elementales. la función objetivo no tendría solución finita.12.cj …. El número de variables positivas (decisión + holgura) al finalizar el Simplex debe ser igual al número de restricciones. A dicha expresión se la conoce como forma producto de la inversa. 3)
. Xj = Ek-1Ek-2 …. 3. mientras no se diga lo contrario. Las modificaciones deben ser hechas antes de introducir los datos en el programa.
2. Hay que hacer notar que la presentación de la salida depende del programa utilizado. Utilizando el programa LINDO para resolver el ejercicio 1. Si para algún (zj . En la columna de variables de holgura (SLACK OR SURPLUS) vienen los resultados de esas variables (por restricción).11. Nosotros. Resolución mediante programa de ordenador
1. se pondrán de manera que cumplan esta condición.cj)  0 j. en cuyo caso ya tendríamos la solución óptima.
142857 0.000000 2
DUAL PRICES 0.000 0.000 SLK 2 0. x3=9/7=1.5714.429
6.286 -1.571 0.
.714 4.000 1.285714 0.000 1.286 3.000000
SLACK OR SURPLUS 4. el resultado es: z = -6.714 X3 0.429 -0.000 0.571 0.000000 1.286
SLK 4 0.571 1. ITERATIONS=
ROW (BASIS) 1 ART 2 SLK 2 3 X1 4 X3 X1 0.000000 0.714286 VALUE 0.000 X2 1.000 0. x1= 4/7=0.571429
NO.000000 1.286
Observando la salida del programa.571429 0.000 0.285714 0.000 SLK 3 1.143 0.714 -0.143 0.000 0.714286.66
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 -6.000 1. x2=0 (no aparece).285714 REDUCED COST 0.857 -0.143 0.000000 1.000 0.2857 Que coincide con el obtenido mediante el algoritmo del simplex.
Optimizacion LinealUploaded by Pilar Rivera649 visitaDescargaInsertarSee MoreCopyright: Attribution Non-Commercial (BY-NC)Precio de lista: $0.00Download as PDF, TXT or read online from ScribdFlag for inappropriate content

References: resolución 
 resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 Resolución