Source: https://es.scribd.com/document/58243860/Optimizacion-Lineal
Timestamp: 2017-06-24 02:04:36+00:00

Document:
Optimizacion LinealCargado por Pilar RiveraRelated InterestsLinear ProgrammingMathematical OptimizationMathematical AnalysisMathematical ConceptsAlgebraRating and Stats0.0 (0)Document ActionsDescargaShare or Embed DocumentInsertarVer másCopyright: Attribution Non-Commercial (BY-NC)Precio de lista: $0.00Download as PDF, TXT or read online from ScribdFlag for inappropriate content21CA 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-
, (i=1, 2, …, m) ¯
y que X es una combinación lineal convexa de ellos: X = ¯
i = b ¯
s z ¯
) s z (2.14) ¯
A i ¯
tenemos Max z = c1 x1 + c2 x2 + … + cn xn=Max st
aij xj  bi. donde (x+) 0. 2. i Escrito lo anterior en forma compacta. …. Restricciones ( o () o (=): Formulación mixta. m)
xj  0.(x-).Programación Lineal
Certidumbre. vamos a pasar un problema formulado en forma canónica a otro en forma estándar. Significa que los parámetros o constantes son estimados con certeza. sean lineales. tendremos: Restricciones (=): Formulación estándar. Dependiendo del tipo de restricción que presente el problema de programación lineal. Restricciones () o (): Formulación canónica. Problema formulado en forma canónica: Max (Min)z = c1 x1 + c2 x2 + … + cn xn st (s. 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:
. tanto la función objetivo como todas las funciones de restricción. o sea. …. (i=1. Sin restricciones de signo: xk =(x+). t. am1 x1 + am2 x2 + … + amn xn  bm xi  0. pues debe cumplir que. 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. (j =1.) a11 x1 + a12 x2 + … + a1n xn  b1 a21 x1 + a22 x2 + … + a2n xn  b2 ……………………………. 2. (x-)0 Por ejemplo.
.. Las restricciones que pueden presentarse son del tipo: i) Si no se debe exceder del recurso disponible ().3. mano de obra..
2.….. x2. i
A las variables xn+1. 3ª Establecimiento de las restricciones que limitan el valor óptimo que puede tomar la función objetivo. t.) a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …. 4ª Resolución del problema y análisis de la solución o soluciones.... tiempo.. implica que el recurso de esa actividad se ha consumido en su totalidad (restricción saturada).. ingreso. xn+2.. ….   a   mj  Las restricciones las escribiremos: x1 A1+ x2 A2 +…+ xn An  b xi  0. iii) Para igualar el recurso especificado (=). 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..26  a1 j     a2 j  A j =  .. am1 x1 + am2 x2 + … + amn xn + xn+ m = bm xi  0.. 2ª Establecimiento de la función objetivo cuyo valor se desea maximizar(utilidad. xn+m se las denomina variables de holgura y se introducen para convertir desigualdades en igualdades. i Problema formulado en forma estándar: Max (Min)z = c1 x1 + c2 x2 + … + cn xn st (s... Cuando las variables de holgura son iguales a cero.. inventario). producción) o bien minimizar (costo.
. rendimiento.. ii) Para no menos de lo requerido (). xn).
.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.
Producto 1 Horas por u. Tipo de soluciones en un problema de programación lineal
(2.Programación Lineal
Ejercicio. x2 0 4ª fase : La resolución del problema y análisis de la solución o soluciones se verá posteriormente.1) (2. que pueden fabricar dos productos. resulta: 1ª fase: x1 = “ número de unidades de P1 “ x2 = “ número de unidades de P2 “ 2ª fase: Max z = 1 x1 + 1.
2. P1 y P2.50
¿Qué cantidad de cada producto P1 y P2 se debe manufacturar cada semana. 2 2 2 1. A. La tabla siguiente muestra los recursos:
Tipo de Máquina A B C Ganancia por u.2) (2. B y C. Todos los productos tienen que pasar por todas las máquinas. para obtener la máxima ganancia ? Desarrollado el problema en fases. Un empresa tiene tres tipos de máquinas.
definidas ordenadamente como un vector X = ( x1.. Generalmente las restricciones aparecen en forma de desigualdad y son convertidas en igualdades al introducir las variables de holgura. xn+m) que satisface el conjunto de ecuaciones que constituyen el sistema (2. . Si B es una de esas matrices.3) sus componentes son todas positivas o nulas.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. siendo n  m. x2. . lo que quiere decir que pueden seleccionarse m columnas de A de manera que la matriz que forman tenga determinante no nulo. invertibles) formadas seleccionando m columnas de A se llama matriz básica o matriz de base. xn . Se dividen las variables de decisión en dos bloques:
Variables básicas: aquella que resulta de (2. Cada una de las submatrices de A con determinante distinto de cero (es decir. 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.. Además se supondrá que la matriz A tiene rango m.2) al hacer (n-m) variables iguales a 0. Cada una de las submatrices de A con determinante distinto de cero (es decir. A las variables no básicas se las da el valor cero. xj...2) al hacer (nm) variables iguales a 0. el proceso de construcción es el siguiente: 1. esto hace que la suposición de que n  m esté justificada. Variables no básicas: las restantes. se llama matriz básica o matriz de base. 3. donde X es el vector formado con las variables básicas y se asignan a estas variables la solución obtenida.. Se resuelve el sistema BX = b. Si B es una de esas matrices. Las soluciones de un problema de programación lineal se clasifican en:
Es un conjunto de n + m variables xj.. inversibles) formadas seleccionando m columnas de A. se dice que es una matriz básica factible si el
.2) y (2.. 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. xn+1. El hecho de exigir que el rango de la matriz A sea m implica evitar que en el problema aparezcan restricciones redundantes o contradictorias.
Por supuesto. la primera matriz básica que puede construirse es la formada por las dos primeras columnas de A:
. x2. no siempre todas esas combinaciones dan lugar a matrices con determinante no nulo. todas las variables básicas son positivas. degeneradas o no degeneradas.
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. Éste es el número de posibles combinaciones para elegir m columnas entre las n columnas existentes. Solución factible básica no degenerada: aquella que es solución factible básica que tiene exactamente m variables xi positivas.
Y. a su vez. Solución factible mínima: aquella que es factible y hace mínimo z. Se trata de encontrar las soluciones básicas del problema
Min z=2x1+4x2+x3 2x1+2x2  6 x1+4x2-x3 12 x1. en:
Degeneradas: cuando alguna de las variables básicas tiene un valor nulo. No degeneradas: cuando todas las variables básicas son estrictamente positivas. Por ejemplo. es decir. x3  0 y clasificarlas en factibles o no factibles.Programación Lineal
vector resultante de multiplicar su inversa por el vector b tiene todas sus componentes mayores o iguales que cero. esto es. En primer lugar. Solución factible básica: aquella que es solución básica y cumple (2. A continuación se presenta un ejemplo de localización de soluciones básicas de un programa lineal. 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. todas las variables son no negativas. No factibles: alguna componente tiene un valor negativo.3).
-9.-12. mediante un ejemplo el concepto de punto básico degenerado (menos de m componentes positivas) y no degenerado:
.0.0) (12.3.0.12)
x1. x4 y x5 4 -1 2 1 x2 y x4 x1. x4 y x5 1 -1 2 1 x1 y x4 x2.3.0) (3. las no básicas.6.0. x3 y x4 1 1 2 0 x2 y x3 x1. De igual manera se construyen el resto de soluciones básicas.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.0) (0.0).0. en este caso todas las submatrices 2x2 son básicas excepto la que forman las columnas tercera y quinta.0.0) (0.9) (0.3. se las da el valor cero y la solución básica que se obtiene es X=(0. x3 y x5 4 0 2 0 x2 y x5 x1.3.0) (0. En la siguiente tabla se presentan todas las soluciones básicas obtenidas.0.6.0.0.0. x2 y x3
Veamos.0.0. x4 y x5 1 4 2 0 x1 y x3 x2.3.0. A las restantes variables.0) (0.0.0.0.0. x3 y x5 1 0 2 0 x1 y x5 x2.0) (3.0.
Variables Variables no Matriz básicas básicas básica 2 2 x1 y x2 x3.30
En este caso.0. x2 y x5 -1 0 Solución básica Tipo
(0. x3 y x4 4 1 0 1 x3 y x4 x1. 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.-18.
0.60) = 260.y) = 4x + 3y st 30x + 20y  1800 x + y  80 x0.0.
. f(D) = f(20.0) = 0.60).1/4 . f(C)=f(60.x4 st x1+x2+x3 =1 x1-x2-x3 +2x4 =1 xi  0 (i=1.0) es básico degenerado El punto (0.0) = 240.1. f(E) = f(0.y0 Tiene por región factible la región sombreada.1) es básico no degenerado El punto (1/2. 2. y corresponde al vértice para el que la función objetivo toma el valor máximo.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. En este caso es el vértice D(20.0. 4) El punto (1.Programación Lineal
Max z = x1-2x2+5x3 . 3. 1/4 . Los valores de la función objetivo en cada uno de los vértices son: f(O) = f(0.80) = 240 La solución es única.
la función objetivo es paralela a una de las restricciones.y) = x + y st y  2x . x  0 . f(C) = f(0. el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible. por lo que puede decirse que el problema carece de solución.
2.y  1 . Hay infinitas soluciones.0) = 4 f(B)=f(5/3. por tanto. f(A) = f(1.5. 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. Este tipo de problemas carece de solución. En este caso no existe un valor extremo para la función objetivo.Por tanto. Resolución de un problema de programación lineal mediante el método gráfico
. que es una región no acotada. ya que las zonas coloreadas que aparecen en la figura son únicamente soluciones de alguna de las inecuaciones . en todos los puntos del segmento BC. x + y 2 . y  0 Los valores de la función objetivo en cada uno de los vértices son: f(O)=f(0. La función crece indefinidamente para valores crecientes de x e y.2/3) = 8. En estos casos. la región factible debe estar no acotada. x .y)= 4x + 2y st 2x + y  4 . como ya vimos en el capítulo anterior. iv) Cuando no existe el conjunto de soluciones que cumplen las restricciones Maximizar la función z = f(x. que corresponden a los puntos del segmento situado entre dos vértices de la región factible. y 0 No existe la región factible. y  x/2 Tiene por región factible la zona coloreada que aparece en la figura.0) = 0. x 0 . solución múltiple.4) = 8 La función objetivo alcanza el valor máximo en los vértices B y C. Para que suceda esta situación.y) = 3x + 8y st x + y 6 .
Evalúe el primer miembro de la expresión. Se cuenta con 96 unidades de material y con 72 horas de mano de obra. 5. Dibuje la gráfica de cada restricción sobre el mismo cuadrante no negativo. 6. Dibuje una recta arbitraria de la función objetivo. El fabricante prometió construir por lo menos dos mesas. Ejercicio 3. 4. Sustituya el punto de ensayo en el primer miembro de la desigualdad y obtenga el valor numérico. 11. 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. 9. Dada la pendiente de la función objetivo y teniendo en cuenta si es un problema de maximizar o minimizar. dan la solución al problema. El procedimiento a seguir es: 1. las sillas utilizan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla. Los valores de las variables de decisión. pero nos puede dar una aproximación a lo que queremos resolver. Función objetivo:
. para obtener la pendiente de la función objetivo. El margen de beneficio es el mismo para las mesas que para las sillas: 5 euros por unidad. por ejemplo pasando por el origen. Determine si el punto de ensayo satisface la desigualdad. entonces todos los puntos que estén del mismo lado que el punto de ensayo satisfacen la desigualdad. 8. 2. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. Resolver gráficamente el problema siguiente: Un fabricante está tratando de decidir las cantidades de producción para dos artículos: mesas y sillas. en este vértice. Si el punto de ensayo satisface la desigualdad original. 10. 3. en caso contrario será un punto no factible. Determine la dirección ascendente o descendente de esta recta. Localice la región de soluciones factibles (Región Factible). Es evidente que su precisión no es la deseada. Escoja cualquier punto de ensayo que no pertenezca a la recta. Convierta las desigualdades en igualdades y represente la rectas que representan estas ecuaciones. determine el vértice del conjunto factible que esté sobre la recta que representa la función objetivo. Por otra parte.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. 7. Solución: El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL.
x2  0 La gráfica asociada al problema es:
Cualquier solución que esté en la frontera o dentro del área sombreada cumplirá con todas las restricciones.
.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
Poniendo todo junto el modelo. se tiene: Maximizar z = 5x1 + 5x2 st 12x1 + 8x2  96 6x1 + 12x2  72 x1  2 x1  0.
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 se pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones. más lejana al origen.Programación Lineal
Representando por líneas discontinuas la función objetivo moviéndose hacia el valor óptimo (máximo) del problema. tenemos:
. pero que todavía toque la región factible. Esto se muestra en la siguiente figura:
Con el punto óptimo localizado gráficamente. la única tarea que queda es encontrar las coordenadas del punto.
por lo que K es: i) K = . ii) K  . cuando K tenga un número finito de vértices que se puedan alcanzar todos (poliedro convexo). Proposición 2. Demostración
. que es precisamente el valor óptimo. 3). Propiedades de las soluciones
Las soluciones de un problema de programación lineal tienen diversas propiedades. 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. pero si lo hace.6. iii) K  . no tiene solución el problema de programación lineal.2) y (2. K es una región de Rn determinada por la intersección del conjunto finito de restricciones lineales (2. Si la región factible no es acotada. es decir. la función objetivo no alcanza necesariamente un valor óptimo concreto. cuando K tenga un número finito de vértices que no se puedan alcanzar todos (región convexa ilimitada). Existe solución de valor finito de la función objetivo.36
resultan ser (6. o a lo largo de uno de los lados. pero el máximo podría ser ilimitado. si la región factible existe y es acotada. En este caso. El conjunto de soluciones factibles de un problema de programación lineal es un conjunto convexo. Designemos por K el conjunto de las soluciones factibles de un problema de programación lineal. de modo que a lo largo de ese lado del polígono se alcanza el mismo valor de la función objetivo. y en aquel en el que el valor de la función sea mayor (o menor) habremos alcanzado el punto óptimo buscado. las líneas de nivel tienen la misma pendiente que la recta que contiene a ese lado del polígono. Si se da el caso de que los valores correspondientes a dos vértices coinciden. 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). alguna de las cuales vamos ver. El problema tiene solución. éstos serán adyacentes. entonces K es la envolvente convexa de los puntos extremos de K.
2. éste se encuentra en uno de los vértices de la región. La sustitución de este punto en la función objetivo da la ganancia máxima: z = 5(6) + 5(3) = 45 euros.1. son paralelas. el valor óptimo de la función objetivo se alcanza en uno de los vértices del polígono que limita la región.
En un problema de Programación Lineal con dos variables.3).
Proposición 2. i  0 . entonces la función objetivo z dada por (2.Programación Lineal
Sean X1 y X2 soluciones factibles. Demostración Sean X1. Si formamos un vector X que sea combinación lineal de éstos dos: X =  X1 + (1-) X2. ya estaría demostrado.
. A X2 = b.1) alcanza su mínimo en un vértice de K. Si K es un poliedro convexo. X2.
Se pueden dar los casos siguientes: i) Si X0 es un vértice de K. si este mínimo se alcanza en varios puntos. AX =  AX1 + (1-) A X2=  b + (1-) b =b por lo que X es también una solución factible. ii) Si X0 no es un vértice de K. entonces X0 se podrá poner como una combinación lineal convexa de ellos: X0 =
i Xi . Xp los vértices de K y sea X0 una solución factible mínima.2.…. además. también se alcanza en cualquier combinación lineal convexa de los mismos. esto significa que cT X0  cT X para cada XK. X1 0. X2  0. entonces A X1= b.
3. entonces podría expresarse como combinación lineal convexa de dos puntos distintos de K: X =  X1 + (1-) X2. Proposición 2. x1k. se cumple que AX1=b y AX2=b. Ak. xk.…. 0)T es un vértice del conjunto convexo K de soluciones factibles. 0)T X2 = (x21. por lo que podemos escribir: x11 A1+ x12 A2 +…+ x1k Ak = b x21 A1+ x22 A2 +…+ x2k Ak = b
. X1.….…. Si tenemos un conjunto de k vectores A1. 0. es decir. que existe un vértice de K en el que la función objetivo z= cT X alcanza su valor mínimo. Demostración Supongamos que X no fuera vértice. por ser soluciones factibles.….….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.…. [0. 0. entonces. que sean linealmente independientes y de forma que: x1 A1+ x2 A2 +…+ xk Ak = b con las xi  0.…. Para probar la segunda parte de la propiedad supongamos que z alcanza su valor mínimo en X1. i  0 . 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.
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. x12. x22. 0)T con X1  X2. X2. 0. 1]. x2k. x2. Xq y que X es una combinación lineal convexa de ellos: X=
i Xi .…. el punto X = (x1. A2. Además.
que las k primeras coordenadas son las no nulas. 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. Si los sumamos y restamos:
.x2k) Ak = 0 y por ser los vectores A1. m de estas coordenadas xi son positivas.x22) A2 +…+ (x1k .4. a lo sumo. x2. que X1 = X2.x21) A1+ (x12 . de lo que se sigue que. xn)T es un vértice de K.…. A2.…. Ak son linealmente dependientes. entonces los vectores Ai asociados con las coordenadas xi positivas forman un sistema linealmente independiente. 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. Si tenemos un vector X = (x1.…. Demostración: Supongamos. lo que contradice el hecho de haber supuesto X1  X2. para simplificar.Programación Lineal
Restando las expresiones anteriores obtenemos: (x11 . Proposición 2. A2. por lo que necesariamente X debe ser un vértice de K.
 2. 0.
. A2 . 2 ) A2 +…+ (xk . no puede hacerse la hipótesis de que los vectores A1. . xk .5. como máximo. . . prueba que existen k  m vectores linealmente independientes. Ak 1 . x2 +  2.… 0)T= 2X Despejando X= ½ (X1 + X2).…. 2xk . Ar vectores adicionales tales que el conjunto A1 . m de las xi serán positivas. A cada punto extremo del poliedro convexo se encuentra asociado un conjunto de m vectores linealmente independientes del conjunto dado A1 . A2. De ahí que.…. Supongamos que k  m y que podemos encontrar solamente Ak 1 . k ) Ak = b De manera que tenemos dos soluciones distintas del sistema de ecuaciones: X1 = (x1 +  1. por tanto son linealmente independientes y. Para k =m la propiedad 2. . 1.…. x2 . 0.… 0)T Sumando X1 y X2.…. 1 ) A1 + (x2 . para r m es linealmente independiente. k. Los n-r vectores restantes dependen de A1 . A2 . Am asociados con cada punto extremo.  i Ai = b
Es decir. Esto contradice la suposición de que tenemos siempre un conjunto de m vectores linealmente independientes A1 . An . Proposición 2. . Ak sean linealmente dependientes.5 queda comprobada. resulta: X1 + X2 = ( 2x1. de ahí que. Ar . desarrollando las expresiones anteriores: (x1 +  1 ) A1 + (x2 +  2 ) A2 +…+ (xk +  k ) Ak = b (x1 .4. Ar . Demostración La Proposición 2. 2x2. como estos vectores son m-dimensionales no podremos tener más de m linealmente independientes. xk +  k. 0. .… 0)T X2 = (x1 . lo cual contradice el hecho de que X sea vértice. Ak .40
xi Ai +   i Ai = b xi Ai .
. de coordenadas no negativas. (Caracterización de los vértices de K) El vector X = (x1. Max z = Min (-z) Cada solución factible básica corresponde a un vértice de K. An. 0.. 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). es decir. las diversas circunstancias de su preparación antes de aplicar el algoritmo y los casos especiales identificables en la tabla solución (última tabla).1. m=   . x2. se conoce una solución de punto extremo en términos de m vectores A j del conjunto original de n vectores.. que las variables no nulas sean las n-m finales X = (x1. A cada vértice de K se puede asociar una base de dimensión m del conjunto de vectores A1.…. x2. si x1 A1+ x2 A2 +…+ xn An = b y las xi > 0 son coeficientes de los vectores Ai linealmente independientes. Sea el problema de programación lineal: Min z = cTX st AX = b X0 Supongamos que tenemos una solución factible básica. 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.7. A2. es un vértice de K (conjunto convexo de soluciones factibles).….…. Resumiendo lo anteriormente expuesto mediante propiedades y teoremas tenemos: Si existe solución al 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. El máximo número de vértices que puede tener el convexo K es Cn. Podemos hacer que este conjunto de m vectores linealmente independientes sean los primeros m. es decir.. xm. Demostración La demostración es inmediata aplicando las proposiciones 3 y 4.Programación Lineal
Teorema 2. xn)T.
2. 0)T que verifica:
....  j
Investigación Operativa (2..….......1) que. i=j x’i = 0.2)
(2. donde: x’i = xi . xm=bm.2) multiplicada por un escalar j. si elegimos j  0.j  i j 0 para i=1.42
x1 A1  x2 A2    xm Am  b. …. j  1.. podemos expresar cada uno de los n vectores dados como combinación lineal de los vectores de esa base:
Ai  A j .j  2 j )A2 + … + (xm ..j  i j 0....j  m j ) + j cj= = z .. Am es la base canónica de los vectores unitarios entonces x1=b1...6) donde z es el valor de la función objetivo en X. de modo que xi .. pues bien si a (2.5)
La función objetivo en X’ = (x’1. resulta: (x1 .4)
con lo cual.. en los demás casos (2..3)
Observando en (2.. si A1..1)
Como los vectores Am forman una base en el espacio m-dimensional.. i=1. 2.j  1 j )A1 + (x2 ... 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
(2.... solución factible. x2=b2. A2. 2. .. y zj viene dada por la expresión:
. x j  0.j (zj -cj) (2...... x’2...1) le restamos (2. m x’i = j  0. x’n)T.. Tomemos un j de modo que Aj no esté en la base dada..j  m j )Am + j Aj = b (2......j  2 j ) + … + cm (xm .…. x’2.. n
11 A1   21 A2     m1 Am  A1  A   A     A  A  12 1 22 2 m2 m 2  ..….. Rm. toma el valor z’ = c1 x1’ + c2 x2’+ … + cm x’m + j cj = = c1 (x1 ..j  1 j ) + c2 (x2 .. x’n)T es una solución factible.. 2.... m tendremos que el vector X’ = (x’1. . ..
x  x1   m+1 = min  i /  ij  0 = i   1. en (2. éstas corresponden a las variables cuyos vectores asociados.m1  ij 
(2. por ejemplo. m+1. ….10).…. xm’. a continuación calcularemos los productos j (zj -cj) y nos quedaremos con el índice j que da el producto mayor. j 
.8) i    ij 
y esto para cada j para el que se cumpla (zj -cj) > 0.…. …. deberá ser m+10.
x    j = min  i /  ij  0 (2. m+1 = x1 -
1. en calcular las cantidades (zj -cj) > 0 observando las relaciones (2. por otra parte. supongamos que éste es j=m+1. A3. A3.j  i j 0. ello significará que seleccionamos el vector Am+1. Am+1 son linealmente independientes. Am son linealmente independientes. despejando Am+1 de (2. Am+1 son linealmente independientes (Vea el teorema de caracterización de los vértices de K). para i=1. supongamos que fueran linealmente dependientes. por tanto. por lo que la
nueva solución factible X’ = (x’1. 0. puesto que los vectores A2. x’n)T = (0.5).…. A3.…. esto quiere decir que existirá i tal que 2 A2 +  3j A3+ … +  m Am+  m+1 Am+1 = 0 (2. Estudiaremos dos casos: i) ii) ij > 0 ij  0
Caso i): j  0.8) se alcanza. mejoran el valor de la función objetivo. obtenemos:
. Por tanto. x2’. con lo cual z’<z.9)
ello significará que x 1’ = x1 . si los incluimos en la base.j (zj -cj). m+1 = 0. El procedimiento consiste.Programación Lineal zj = c1  1 j + c2  2 j + … + cm  m j (2. si el mínimo en (2. 0)T será un vértice de K (conjunto de soluciones factibles) si los vectores A2.5) se tenga que j(zj-cj) sea positivo y máximo. z’= z.7)
así pues.10) para algún i distinto de cero y.m+1  1.m1
 1.6) vemos que debemos seleccionar j y j de forma que verificándose (2. Para probar que los vectores A2.  i j > 0 x’i = xi . x’2.
11) de (2. En consecuencia. m+1 . Por supuesto encontrar todas las soluciones básicas de un programa lineal requiere de grandes esfuerzos de cálculo. en cuyo caso ya no se podría disminuir la función objetivo y. con (zj . 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.  i j  0 x’i = xi .2).. A2.….9)). ocurrirá que z’ tiende a menos infinito. únicamente resulta sencillo en problemas con pocas variables de decisión. . 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). .cj ) >0 Como se puede elegir un j tan grande como quiera. Am linealmente independientes obliga a que 1. m)Am
por lo que. sin embargo se supuso positivo (vea (2. no existe solución. es decir. encontramos que Am+1 = 1. 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.m+1=0 y. n. m+1 Am 0 = 1. Caso ii): j  0. por tanto. 2. m+1 A2 +…+  m. 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. m+1 . Am+1 son linealmente independientes. se habría alcanzado el mínimo con el vector X que se tuviera en esa etapa.. con j=m+1. al ser A1. m+1 A1 + ( 2..cj ) .….44 Am+1 = i  m1
  2 A2 . A2.m Am m1 m1 m1
(i=2. m+1 A1 +  2. A2.j  i j z’ = z.
Am+1 =  2 A2 +  3 A3 +…+  m Am Restando (2. 2) A2 +…+ ( m..3 A3 -…. .. m) (2.j (zj .
.Programación Lineal
Dentro de los aspectos computacionales. ya que se almacenan y calculan muchos números que no son estrictamente necesarios. para un humano no supone ningún problema reconocer los ceros y darse cuenta que al multiplicar un número por cero resulta cero. en las tablas del simplex aparecen gran número de ceros. 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. Sin embargo. Sin embargo. 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. el método Simplex no resulta muy económico desde un punto de vista computacional. En tales situaciones debe recurrirse al uso de los computadores electrónicos. Por ejemplo.
(2. entonces. 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. j (j=1. con yi  0
y valor de la función objetivo: z = c1 y1 + c2 y2+ … + cn yn se verifica z0  z.cj )  0. Demostración Sea X = (x1... m) se tiene: c 1 (   1 j y j) + c 2 (   2 j yj) + … +cm (  
(2... .12) cada cj por zj tenemos: z1 y1 + z2 y2+ … + zn yn  z (2. n). . . xn)T un punto extremo en el cual la función objetivo vale z0 y para el que se verifica que (zj .cj )  0  zj  cj y sustituyendo en la expresión (2. j (j=1.... 2. Hemos de probar que para cualquier otra solución (zj ... yn)T..13) cada zj (j=1.. n). n) Y= (y1.…. 2.46
Investigación Operativa Teorema 2.. 2. j (j=1.….2.cj )  0.12)
Como (zj . y2.cj )  0. x2.. . 2. Si en algún paso (puede ser el primero) del método simplex se
verifica que (zj .14)
... el último vértice obtenido es la solución óptima.13)
Sustituyendo en (2.
2.14) se tiene: c1 x1 + c2 x2+ … + cm xm  z es decir z0  z .. x2 =   2 j yj . b se escribe de forma única. xm =   m j yj
Sustituyendo en (2.Programación Lineal y 1 A1+ y 2 A2+ … + y n An = b Sustituyendo Aj (j=1... Am linealmente independientes. . n) por su valor: (2. …. A2.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.. Resuelva mediante el Método Simplex el problema de programación lineal siguiente: Min z = –5x1+2x2-3x3 st 2x1+2x2-x34
.. por lo cual: x1 =   1 j yj . Ejercicio 1. .15)
Sustituyendo este valor en (2.
z1 = 0. Por ejemplo.(-5)=5
. 0.c1 =0 . 2. 3)
Pasando el problema a forma estándar añadiendo variables artificiales. 0. tenemos.48 3x1.j
El vértice inicial de partida es X=(0.5x1+2x2-3x3+0x4+0x5+0x6 st 2x1+2x2-x3+x4 = 4 3x1.2=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.x2+x3+x5 = 3 2x1+x2+3x +x6= 5 xi  0 (i=1. i    ij  ij  iv) Buscando que j (zj -cj) sea positivo y máximo. 3. 2. 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.2+0. 4.3+0.x2+x33 2x1+x2+3x35 xi  0 (i=1. el valor de j que hace max j (zj . zj. 5)T. ii) Calculamos (zj -cj). 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. para j=1. z1 .
x  b   iii) Para los valores (zj -cj) >0 calculamos j = min  i  i /  ij  0 . de manera que tengamos una base canónica para comenzar el método del simplex: Min z = .cj) nos
proporciona el vector j-ésimo que entra en la base.
2. Veamos como se obtiene   : 1   0  
Llevando lo anterior a la tabla. i2  21  21 3 
El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote.5=5). tenemos: .
x b 3 . j (j=1.. Este proceso se repite de forma iterativa hasta que se verifique (zj . .Programación Lineal
Realizadas las operaciones correspondientes. El vector A1 que entra en la base se convierte en un elemento de la base canónica.cj )  0.El vector que sale de la base es el A5 (1 = min  2  2   =1).. que se genera en el cruce del vector que entra y el vector que sale.El vector que entra en la base es el A1 ( max 1 (z1 –c1)=1. deberá valer uno y el resto cero.. n). 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
. en nuestro caso el 3. 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).
zj..2857 z. A5. Tercera tabla cj Base A4 A1 A3
cB b 0 29/7=4. 2. A5 y A6 de la tabla:
1  8 / 7 5 / 7     {A4.cj )  0. j -47/7=-6.5714. en este caso a los vectores A4. x2=0 (no aparece).. 0. 0. j (j=1. La solución mediante la matriz inversa asociada a la tabla del simplex. . 9/7.. Para buscar la solución dentro de la tabla miramos la columna b y encontramos: x1=4/7=0. por lo que hemos llegado a la etapa final.50
Segunda tabla cj -5 Base cB b A1 0 2 0 A4 -5 1 A1 1 0 3 0 A6 -5 -5 z.7142 El vértice final obtenido es X=(4/7. n). z = -6.5714 -3 9/7=1. A6}=  0 3 / 7  1 / 7  0  2 / 7 3 / 7  
. 0)T. j zj-cj 0 j(zj-cj) Entra A3 y sale A6. x3=9/7=1.7142 zj-cj j(zj-cj)
Observando la tabla tenemos (zj .1448 -5 4/7=0. B-1 la podemos encontrar directamente en la última tabla del simplex observando los vectores correspondientes a los de la base inicial.2857. 29/7. zj.
571429 0.286 3.000
X2(A2) 1.000 0.857 -0.000 1.143 0.143
SLK 2(A4) SLK 3(A5) 0.000 0.285714 REDUCED COST 0.000000 1. A4.571429
X1(A1) 0.571 0.286 1. A1 y A3:
1 2  1   B  {A4.714286 VALUE 0.142857 0.571
DUAL PRICES 0.429 0.000000 1.Programación Lineal
y la matriz B se obtiene de la primera tabla mirando la base que figura en la última tabla del simplex.000 -1. tenemos:
Min -5x1+2x2-3x3 st 2x1+2x2-x3 <= 4 3x1.000 0.000 -0.000000 1.000000
SLACK OR SURPLUS 4.714 4.285714 0.286
SLK 4(A6) 0.000 1. A1.285714 0.000 0.571 0.000000 0.000 1.000 0. A3}=  0 3 1  0 2 3   
Si resolvemos el ejercicio anterior con el programa LINDO.143 0.x2+x3 <= 3 2x1+x2+3x3 <=5 LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 -6.714 -0.714
X3(A3) 0.
1  8 / 7 5 / 7     {A4.52
4 0. b) Los valores de: a. b.429 1. zj-cj
. 3) Para ciertos valores de los recursos. 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. A6}=  0 3 / 7  1 / 7  0  2 / 7 3 / 7  
1 2  1   B  {A4. A5. c. 2. Considere el problema siguiente:
Max z= 5x1+2x2+3x3 st x1+5x2+2x3b1 x1-5x2-6x3 b2 xi  0 (i=1. A1. d. e. c3.
cB 0 0 z. A3}=  0 3 1  0 2 3   
b = 5. necesitaremos de lo que se conoce como variables artificiales. zj-cj
Identificando. a continuación. mientras que las variables artificiales se introducen para facilitar el comienzo del método simplex. Las primeras se introducen para convertir desigualdades en igualdades. e= 0. b) a= -23. La base canónica inicial la configuraremos con las variables de holgura más las variables artificiales necesarias hasta tener esa base canónica. sale de la base A4 y entra A1
cj b b1 b2. podremos aplicar directamente el método del simplex. c3= -3
2. b2= 40. 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. Veamos como siempre es posible conseguir esto. c= -10. d= -5. b2.8.b1=10. Es oportuno resaltar la diferencia entre variables de holgura y variables artificiales. Veamos. tenemos: a) b1= 30. para iniciar el método simplex.
Tabla 2 Por la información que nos proporciona la tabla del enunciado. un método que nos ayude a resolver los problemas que contengan variables artificiales. Para conseguir partir de una base canónica. En la mayoría de los casos la situación anterior no se producirá. por lo que tendremos que recurrir a métodos que nos conduzcan a él.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. Éstas construyen un problema artificial más conveniente desde el punto de vista del método simplex. Si al introducir las variables de holgura necesarias para escribir el problema en forma estándar ya tenemos la base canónica.
Las iteraciones del método simplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una. hasta que todas quedan fuera de la solución.8. X=0 Debemos buscar la forma de hacer salir las variables artificiales. pueden presentarse los casos siguientes: a) Tengamos solución finita: i) Que el problema admita una solución óptima. las Xa. entonces la solución obtenida es única y óptima. Xa  0 En la resolución del problema por este método. y que entren las otras variables. 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.54
2. 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.
. Para ello les asociamos un valor muy grande M ( no es necesario especificar el valor de M) en la función objetivo.1. es decir. con lo cual tenemos el sistema siguiente: AX + I Xa = b X  0. con todas las variables artificiales iguales a cero. Xa  0 Tenemos como solución inicial: Xa =b. Xa= 0. Min z = cTX + M 1T Xa st AX + I Xa =b X  0.
j 75M zj-cj j(zj-cj)
. en este caso tenemos una solución no finita. 2. b) Tengamos solución no finita: iii) Con todas las variables artificiales iguales a cero. Xa= 0. no tenemos solución. zj. . 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. Min z = . iv) Exista al menos una variable artificial que sea positiva. Xa 0. la misma solución óptima que el problema real. 7)
cB b M 20 0 40 M 55 z.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. en caso de que exista. para resolver este problema. 3) Como explicamos anteriormente. debemos construir un problema “artificial” que tiene. entonces el problema original es imposible. entonces el problema original es imposible.Programación Lineal
ii) Que el problema admita una solución óptima en la cual encontraremos al menos una variable artificial distinta de cero.
. El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote. j (j=1.. tenemos que entra A2 y sale A6. por corresponder a una variable artificial. ya nunca más volverá a entrar. 2. zj...
-1 cB b A1 -6 10 1/2 0 30 3/2 M 45 3/2 z.cj )  0. . n). que. Este proceso se repite de forma iterativa hasta que se verifique (zj ... ya nunca más volverá a entrar. que. por corresponder a una variable artificial. 2. j (j=1. zj.
cB b -6 15 0 15 4 10 z. que se genera en el cruce del vector que entra y el vector que sale. Para buscar la solución dentro de la tabla miramos la columna b y encontramos:
.cj )  0. . en nuestro caso el 2.j -50 zj-cj
Observando la tabla tenemos (zj . en nuestro caso se da para varios j. deberá valer uno y el resto cero. por lo que hemos llegado a la etapa final.56
A los valores que hayan resultado ser (zj -cj) >0.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. n). 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.
8. z = 50
2. x3= 10.Programación Lineal
x1= 0.
. con lo cual tenemos el sistema siguiente: AX + I Xa =b X  0. x4 =15. x3= 10. z = -50 Luego. x2 =15. necesarias para tener en la primera tabla del simplex una base canónica.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. Xa  0 Si el problema original tienen solución factible. x2 =15. resolveremos el problema original planteado utilizando la última matriz obtenida en la Fase I y por tanto dicha base.
Fase II: En esta segunda fase. el mínimo del problema anterior se alcanzará cuando las variables artificiales Xa =0 y z=0. Xa. Xa  0 Su resolución se abordará en dos fases:
Min z = 1TX a st AX + I Xa =b X  0. x5= 0. la solución del problema original planteado (maximización) es: x1= 0.
a1=1. h3=2. tenemos: Primera tabla
Solución de la tabla.58 Min z = x1. 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. x2  0
Vamos a resolverlo por el método de las dos fases. al ser la función objetivo de minimizar y tener zj-cj positivos la solución no es óptima. x2=1. El problema con las variables de exceso .2x2 st x1 +x2  2 -x1 +x2  1 x2  3 x1 0 . z=1.h1+ a1 =2 .x1+x2 -h2+ a2 =1 x2+ h3 =3 pasamos a la tabla los datos y operamos según el algoritmo del simplex. Para los zj-cj >0
x2=2 h3=1. 0. 0. Para los zj-cj >0 calculamos j. con lo cual terminamos la primera fase al obtener en la próxima tabla z=0 con a1=0. 3.
. h2=1. z=-4. Introducimos entonces la función objetivo original min z=x1-2x2 y continuamos con el algoritmo del simplex:
0 A7 A3 A5 0 . 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. la cual no volverá a entrar en la base y por lo tanto se puede eliminar de la tabla. 0. y el valor máximo de j(zj-cj ) se alcanza en x1 y en h2. la solución no es óptima. tomamos x1 por tener mayor zj-cj . a2=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.1 0 1 3 3 0 3 1 0 -
Solución de la tabla. 0)T. será la nueva variable básica.Programación Lineal
calculamos j. z=-6. h1 será la nueva variable básica. 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)T. si es así.x2+x3 + 2x4 =10 x2.
. 1. 6) Los puntos extremos son: X1=(2. 4.cj)= 0. Repitiendo este proceso para cada una de las “j” que no pertenecen a la base y verifican (zj .cj ) = z no hemos mejorado la solución anterior. obtendríamos todos los vértices que son soluciones óptimas. Supongamos que ya hemos encontrado una solución óptima (mínima) de un problema y que se verifica (zj . El método simplex se detiene automáticamente al encontrar una solución factible básica óptima.60
2. por lo cual el problema tiene infinitas soluciones. Soluciones degeneradas
Al desarrollar el algoritmo del simplex supusimos que las soluciones eran siempre no degeneradas.x3  1 x2+ 2x4  8 xi  0 (i=1.j (zj .. 7/2.9. Min z = x1-2x2+3x3 st x1... . de manera que. tal que no pertenece a la base. 0. 0)T así como toda combinación convexa de dichos puntos. 0. 0. también sería solución óptima. 2. pero que cumple (zj . X2=(4. j. en un número finito de iteraciones llegábamos a la solución óptima. Tomando una combinación lineal convexa de ellas. La función objetivo es: z’ = z . se puede detectar si existen otras y. 1. mediante el método simplex.cj)= 0. 0. Toda solución óptima es una combinación lineal convexa de las soluciones factibles básicas óptimas.cj )  0. Una vez que el método simplex encuentra una solución factible básica óptima. que el problema siguiente presenta dos puntos extremos. se encuentra observando si tengo algún vector j. esto nos indicará que existe multiplicidad de óptimos.10. Compruebe. Soluciones múltiples
A2. la cual se tiene con al menos una variable básica de valor cero en el sistema de m restricciones.11. Descomponiendo la matriz A de forma que A=(B. tenemos BXB = b.. . x2. Este caso se presenta cuando se valora una solución básica no única. alguna de ellas debe ser restricción redundante que contiene sólo un punto vértice del conjunto factible. 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.. xm. la matriz no básica (los Ai que no son de la base). 0)T. esto es. N) donde Bmxm es la matriz básica y N(mx(n-m)). 0. es decir. 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. estaríamos en un punto extremo que tiene menos de “m” coordenadas positivas. Denotemos por Ai la columna i-ésima de la matriz A y supongamos que los m vectores linealmente independientes son los m primeros A1. si al calcular el valor de j = min  i /  ij  0 existen varios i i    ij  xi tal que minimizan . A2. b) = rang (A) = m. entonces. El método del simplex revisado
Un procedimiento más eficiente que el simplex en su versión matricial es el llamado simplex revisado.….
x    Ahora bien. Se identifica en la tabla simplex porque al menos una variable básica tiene valor cero en la columna de solución. XB = (x1. un punto extremo degenerado. Am. Se podría
2. XB = B-1 b
.…. 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. la matriz B= (A1.Programación Lineal
 ij elegir uno cualquiera y. Am) es la matriz básica...
75 zj-cj
A4 0. al vector columna mx1 se le denomina vector de multiplicadores del simplex asociado a la base B.5 -0.5 -0.  2 j. si se sabe que la primera restricción es () y el resto ().5 0.5 0. ….62 y puesto que
esto es Aj = BXj.75 3. Xj = B-1 Aj
Donde T= cBT B-1. Dada la tabla óptima del Simplex:
cj b 0.  m j )T.
b) Formule el problema Dual y de la solución sin hacer operaciones.5 -0.5 -0. Veamos el ejercicio siguiente. Escriba la solución en el recuadro adjunto.5
A5 -0. Xj= ( 1 j.5 -0.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.
.75 1.25 -4.5 1.
5 1.5  0.5  .5)  3 0 1  (2 0 1)  1 0 1  
.5   
A continuación se calculan los vectores Aj (j=1. 2.5  0  0.75   3       B X=b=  3 0 1 1.5   1 0 1 3.5 0.Programación Lineal Solución: a) La matriz inversa se obtiene directamente de la tabla:
0.25   4       La formulación del problema sería:
2 x1+ x2  3 3x1+x2 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.  2  1 1   T T tenemos: c =  B=(0 0. B =   1 0.75    5. x2  0
b) Operando con el vector de multiplicadores del simplex asociado a la base B.5 x1+x2  4 x1.5  0   0.
. en general la inversa de la base de la k-ésima iteración se obtiene Bk-1 = Ek-1 Ek-2 …........ ... Aj. Ar-1.....11. Xj = B-1 Aj..64
2..  E=R =  0 0 . 0     0 1 . esto es:
1 0 .  .   2 j /  rj .. tomábamos la base canónica......  1 j /  rj ...…... Ar-1.. es decir.... Determinación de la inversa...  2 j .... 1 j . A2. sea B= (A1.. Siguiendo un proceso iterativo. A2......   0 0 . 1 /  rj . 0  R=    ... Cuando comenzábamos el método del simplex.... 1 Entonces B1-1= R-1 B-1= E B-1. Ar+1.. B1-1 = I y XB = b.. tenemos: B2-1= E1 B1-1 = E1 I= E1 B3-1= E2 B2-1 = E2 E1 y.. Forma producto de la inversa
Sea B una base y B-1 su inversa.... En efecto.. 1 mj   La inversa de R la denotamos por E y viene dada por
1 0 ... Ar+1.   mj /  rj . Ar... 0     0 1 .. podemos conocer B1-1 en términos de B-1........ Am)..... B-1 B1= R
donde R es la matriz identidad reemplazando la r-ésima columna por el vector columna Xj.......….... E2 E1
.. a la matriz E se la denomina matriz elemental...1........... B1=I. 0     ... si realizamos un cambio de base a la base B1.. 0    -1  .. Am) y supongamos que al realizar el cambio de base introducimos el vector Aj y sale Ar B1= (A1...     0 0 ....
cj)  0 j. A dicha expresión se la conoce como forma producto de la inversa. Hay que hacer notar que la presentación de la salida depende del programa utilizado. En cada iteración hay que controlar si todos los (zj . mientras no se diga lo contrario. tenemos: Min z = –5x1+2x2-3x3 st 2x1+2x2-x34 3x1. 3. Etapas del método del simplex revisado
T -1 T T= cBTB-1 z = cB B b zj .cj) > 0 y Xj  0.cj = TAj . utilizaremos el programa LINDO (L = Linear IN = Interactive D = Discrete O = Optimizer). Las modificaciones deben ser hechas antes de introducir los datos en el programa. 2. se pondrán de manera que cumplan esta condición. Resolución mediante programa de ordenador
1. en tanto que todos los términos constantes (recursos) aparecerán a la derecha. E2E1Aj La última columna representa la situación en la k-ésima iteración. 2. la función objetivo no tendría solución finita. de lo contrario el problema es degenerado.
2.11. El número de variables positivas (decisión + holgura) al finalizar el Simplex debe ser igual al número de restricciones.12.
2. E2E1Aj-cj
B-1 XB = B-1 b Xj = B-1 Aj …. 3)
. En la columna de variables de holgura (SLACK OR SURPLUS) vienen los resultados de esas variables (por restricción).Programación Lineal
que expresa la inversa como producto de matrices elementales. Xj = Ek-1Ek-2 …. Si para algún (zj . zj -cj =cB Ek-1Ek-2 …. en cuyo caso ya tendríamos la solución óptima.2.x2+x33 2x1+x2+3x35 xi  0 (i=1. Utilizando el programa LINDO para resolver el ejercicio 1.cj …. Nosotros. Todas las variables de las restricciones deben aparecer en el primer miembro. las de valor cero indicarán que el recurso se ha consumido en su totalidad. Si el programa requiere que todas las variables sean no negativas.
571 0.714 4.000 0.286 3.429
6.714 X3 0.714286 VALUE 0.000 0.285714 REDUCED COST 0.714286.714 -0.000000
SLACK OR SURPLUS 4.000 0.285714 0.143 0.000 SLK 2 0.000 0. x3=9/7=1. x2=0 (no aparece).000000 1.571429
NO.2857 Que coincide con el obtenido mediante el algoritmo del simplex.000 0.000000 0.000 1.571 0.142857 0.5714.000000 1.285714 0.286 -1.000 SLK 3 1.
.000 X2 1.000 1.000000 2
DUAL PRICES 0.857 -0. x1= 4/7=0.000000 1.143 0. ITERATIONS=
ROW (BASIS) 1 ART 2 SLK 2 3 X1 4 X3 X1 0.286
SLK 4 0.143 0.429 -0.000 0. el resultado es: z = -6.571429 0.571 1.000 1.66
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 -6.286
Observando la salida del programa.
Recommended DocumentsDocumentos similares a Optimizacion LinealSkip carouselProgramacion CuadraticaProgramacion Lineal 1Cap02(PL)_IO-IProgramacion Lineal EnteraTeoria de La DualidadBasis of Solution of Syslineqhom EsParcial Investigacion359 Prog Dinamica Entera 2015_1Programación linealPlaneacion Agregada14.pdfConcurso UNIProgramación Lineal y El Método Simple1Espaciosvectoriales3Programacion Lineal-Metodo SimplexTrabajo_2_Final_100404_13502-Investigacion Operativa I- Ing Industrial Fundamentos de Programación Lineal (1)Dualidad y Sensibilidad (Invt Operaciones)Tarea N_ 7 Conceptosprogramacion matematica02 Ejercicios Prog Lineal Recintos SolucionesCartilla S7TALLER UNO 2-2014.docxOptimizaciÃ_n - ProgramaciÃ_n Lineal (PEP 1)algebra lineal unadPráctica Álgebra Arquitectura1er. Curso de Comunicaciones v2!4!2013-1ÁLGEBRA MATRICIALEspacio Vectorialespacios_vectoriales (32)

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