Source: https://es.scribd.com/doc/67112442/Optimizacion-Lineal
Timestamp: 2017-05-23 13:28:11+00:00

Document:
Optimizacion Lineal
ScribdExploreEXPLORE BY INTERESTSCareer & MoneyBusiness Biography & HistoryEntrepreneurshipLeadership & MentoringMoney ManagementTime ManagementPersonal GrowthHappinessPsychologyRelationships & ParentingReligion & SpiritualitySelf-ImprovementPolitics & Current AffairsPoliticsSocietyScience & TechScienceTechHealth & FitnessFitnessNutritionSportsWellnessLifestyleArts & LanguagesFashion & BeautyFood & WineHome & GardenTravelEntertainmentCelebrity Biography & MemoirPop CultureBiographies & HistoryBiography & MemoirHistoryFictionChildren’s & YAClassic LiteratureContemporary FictionHistorical FictionLGBTQ FictionMystery, Thriller & CrimeRomanceScience Fiction & FantasyBROWSE BY CONTENT TYPEBooksAudiobooksNews & MagazinesSheet MusicSubirIniciar sesiónRegistrarseOptionsJoinSign InUploadOptimizacion LinealCargado por Pilar RiveraLinear ProgrammingMathematical OptimizationMathematical AnalysisMathematical ConceptsAlgebra0.0 (0)DescargaInsertarVer 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-
1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva. En 1939, el matemático ruso Leonid Vitalevich Kantorovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida, llamada hoy en día programación lineal. En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y por Kantorovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantorovitch. En los años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal. Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando. En 1947, G. B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Respecto al método simplex, que estudiaremos después, señalaremos que su Q. MARTÍN MARTÍN 22 22
estudio comenzó en 1951 y fue desarrollado por Dantzig. Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro John Von Neumann (1903-1957), quien en 1928 publicó su famoso trabajo sobre Teoría de juegos. La Programación Lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables. El nombre Programación Lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate. La Investigación Operativa en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de los momentos más importantes fue la aparición del Método del Simplex. Este método, desarrollado por G. B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas. Partiendo de uno de los vértices de la región factible, por ejemplo el vértice P, y aplicando la propiedad: si la función objetivo no toma su valor mínimo en el vértice P, entonces existe una arista que parte del vértice P y a lo largo de la cual la función objetivo no aumenta, es decir, se pasa a otro vértice donde el valor de función objetivo sea menor o igual que el alcanzado en P. Iniciarse en la técnica de programación lineal teniendo como referencia al método científico: la representación o modelo en formulación matemática lineal de algunos problemas elegidos, será nuestro objetivo en este capítulo. La Programación Lineal es una de las técnicas agrupadas como programación matemática, aplicable a problemas de asignación de recursos limitados, con actividades competitivas hacia un objetivo común, que puede ser de maximizar beneficios o minimizar pérdidas. Se utiliza un modelo matemático con representación válida de la problemática en estudio; sus relaciones deben ser lineales, que significa utilizar, sólo variables de primer grado en cada término. El objetivo de la Programación Lineal es encontrar el valor de la función que Max (Min) z = c
+ … + c
denominada función objetivo. La función objetivo se encuentra sujeta a una serie de restricciones
Programación Lineal 23 st a
…. a
donde x
i > 0 (i=1, 2, …, n) son las condiciones de no negatividad de las variables. Cada columna de coeficientes: A
= , X= |
2 ,…, A
)= |
m mn m m
.... .......... ..........
2 2 22 21
2 +…+ x
n s b; x
> 0, ¬i Matricialmente lo anterior se escribe como: Max z = c
X st AX s b X > 0 siendo z: la función objetivo c = (c
,...,c
: vector de coeficientes de la función objetivo. X = (x
,...,x
: vector de variables de decisión. A = (...,a
,...): matriz de coeficientes técnicos (i =1, 2, ..., m; j =1, 2, ..., n). b = (b
: vector de demandas (recursos). El conjunto de soluciones factibles de un problema de Programación Lineal viene dado por: Investigación Operativa 24 X = {x eR
/ A x s b , x > 0} Como se verá posteriormente, todos los óptimos (si existen) deberán estar en la frontera del conjunto de soluciones factibles. La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada. Región factible acotada Región factible no acotada La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio (s o >) o en sentido estricto (< o >). Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones siempre que no haya restricciones redundantes. 2.2. Formulación de un problema de Programación Lineal Para que un modelo de Programación Lineal sea válido, debe cumplir las propiedades siguientes: Proporcionalidad. Significa que la contribución al valor de la función objetivo y el consumo o requerimiento de los recursos utilizados, son proporcionales al valor de cada variable de decisión. Así el término 2x
es proporcional, porque contribuye al valor de la función z con 2, 4, 8, etc. para los valores 1, 2, 3, etc., respectivamente, de x
. Se puede observar el aumento constante y proporcional de 2 conforme crece el valor de x
. Aditividad. Significa que se puede valorar la función objetivo z, así como también los recursos utilizados, sumando las contribuciones de cada uno de los términos que intervienen en la función z y en las restricciones. Divisibilidad. Significa que las variables de decisión son continuas y por lo tanto son aceptados valores no enteros para ellas. La hipótesis de divisibilidad más la restricción de no negatividad, significa que las variables de decisión pueden tener cualquier valor que sea positivo o por lo menos igual a cero. Programación Lineal 25 Certidumbre. Significa que los parámetros o constantes son estimados con certeza, o sea, 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, pues debe cumplir que, tanto la función objetivo como todas las funciones de restricción, sean lineales. Dependiendo del tipo de restricción que presente el problema de programación lineal, tendremos: Restricciones (=): Formulación estándar. Restricciones (s) o (>): Formulación canónica. Restricciones (s o (>) o (=): Formulación mixta. Sin restricciones de signo: x
=(x+)- (x-), donde (x+) >0; (x-)>0 Por ejemplo, vamos a pasar un problema formulado en forma canónica a otro en forma estándar. Problema formulado en forma canónica: Max (Min)z = c
st (s. t.) a
……………………………. a
i > 0, ¬i Escrito lo anterior en forma compacta, tenemos Max z = c
=Max c
, (i=1, 2, …, m) ¿
j > 0, (j =1, 2, …, n) Escrito en forma matricial sería: Max z = c
T X st AX sb X>0 Cada columna de coeficientes técnicos A
representa un vector: Investigación Operativa 26 A
Las restricciones las escribiremos: x
n s b x
> 0, ¬i Problema formulado en forma estándar: Max (Min)z = c
…................ a
n+ m
i > 0, ¬i A las variables x
n+m se las denomina variables de holgura y se introducen para convertir desigualdades en igualdades. Cuando las variables de holgura son iguales a cero, implica que el recurso de esa actividad se ha consumido en su totalidad (restricción saturada). 2.3. 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 (x
). 2ª Establecimiento de la función objetivo cuyo valor se desea maximizar(utilidad, rendimiento, ingreso, producción) o bien minimizar (costo, tiempo, mano de obra, inventario). 3ª Establecimiento de las restricciones que limitan el valor óptimo que puede tomar la función objetivo. Las restricciones que pueden presentarse son del tipo: i) Si no se debe exceder del recurso disponible (s); ii) Para no menos de lo requerido (>); iii) Para igualar el recurso especificado (=). 4ª Resolución del problema y análisis de la solución o soluciones. Programación Lineal 27 Ejercicio. Un empresa tiene tres tipos de máquinas, A, B y C, que pueden fabricar dos productos, P1 y P2. Todos los productos tienen que pasar por todas las máquinas. La tabla siguiente muestra los recursos: Tipo de Máquina Producto 1 Horas por u. Producto 2 Horas por u. Horas disponibles semanalmente A 2 2 16 B 1 2 12 C 4 2 28 Ganancia por u. 1 1,50 ¿Qué cantidad de cada producto P1 y P2 se debe manufacturar cada semana, para obtener la máxima ganancia ? Desarrollado el problema en fases, resulta: 1ª fase: x
= “ número de unidades de P1 “ x
= “ número de unidades de P2 “ 2ª fase: Max z = 1 x
+ 1.5 x
3ª fase : 2 x
s 16 x
s 12 4 x
> 0, x
>0 4ª fase : La resolución del problema y análisis de la solución o soluciones se verá posteriormente. 2.4. Tipo de soluciones en un problema de programación lineal El problema de programación lineal formulado matricialmente (estándar):
Min z = c
X (2.1) st AX = b (2.2) X>0 (2.3) Investigación Operativa 28 Donde A es una matriz de m filas (restricciones) y n columnas (variables), siendo n > m. Generalmente las restricciones aparecen en forma de desigualdad y son convertidas en igualdades al introducir las variables de holgura, esto hace que la suposición de que n > m esté justificada. Además se supondrá que la matriz A tiene rango m; lo que quiere decir que pueden seleccionarse m columnas de A de manera que la matriz que forman tenga determinante no nulo. El hecho de exigir que el rango de la matriz A sea m implica evitar que en el problema aparezcan restricciones redundantes o contradictorias. 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. Cada una de las submatrices de A con determinante distinto de cero (es decir, inversibles) formadas seleccionando m columnas de A, se llama matriz básica o matriz de base. Si B es una de esas matrices, 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; el proceso de construcción es el siguiente: 1. Se dividen las variables de decisión en dos bloques: Variables básicas: aquella que resulta de (2.2) al hacer (n-m) variables iguales a 0. Variables no básicas: las restantes. 2. A las variables no básicas se las da el valor cero. 3. Se resuelve el sistema BX = b, donde X es el vector formado con las variables básicas y se asignan a estas variables la solución obtenida. Las soluciones de un problema de programación lineal se clasifican en: - Solución factible: Es un conjunto de n + m variables x
, definidas ordenadamente como un vector X = ( x
, ... x
) que satisface el conjunto de ecuaciones que constituyen el sistema (2.2) y (2.3) sus componentes son todas positivas o nulas. - Solución básica: Solución básica: aquella que resulta de (2.2) al hacer (n-
m) variables iguales a 0. Cada una de las submatrices de A con determinante distinto de cero (es decir, invertibles) formadas seleccionando m columnas de A se llama matriz básica o matriz de base. Si B es una de esas matrices, se dice que es una matriz básica factible si el Programación Lineal 29 vector resultante de multiplicar su inversa por el vector b tiene todas sus componentes mayores o iguales que cero. - Solución factible básica: aquella que es solución básica y cumple (2.3), esto es, todas las variables son no negativas. - Solución factible básica no degenerada: aquella que es solución factible básica que tiene exactamente m variables x
positivas, es decir, todas las variables básicas son positivas. - Solución factible mínima: aquella que es factible y hace mínimo z. - No factibles: alguna componente tiene un valor negativo. Y, a su vez, en: - Degeneradas: cuando alguna de las variables básicas tiene un valor nulo. - No degeneradas: cuando todas las variables básicas son estrictamente positivas. El número de soluciones básicas de un problema lineal es siempre finito y como máximo: |
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. Por supuesto, no siempre todas esas combinaciones dan lugar a matrices con determinante no nulo. A continuación se presenta un ejemplo de localización de soluciones básicas de un programa lineal. Se trata de encontrar las soluciones básicas del problema Min z=2x
+4x
s 6 x
3 s12 x
> 0 y clasificarlas en factibles o no factibles, degeneradas o no degeneradas. En primer lugar, debe formularse el programa en su forma estándar y obtener las correspondientes matrices: A b 2 2 0 1 0
1 4 -1 0 1
6 12 Las matrices básicas serán en este caso todas las submatrices inversibles formadas al seleccionar 2 columnas de A. Por ejemplo, la primera matriz básica que puede construirse es la formada por las dos primeras columnas de A: Investigación Operativa 30 B 2 2 1 4 En este caso, las variables básicas son x
y los valores que toman en la correspondiente solución básica se obtienen resolviendo el sistema: 2x
= 6 x
= 12 La solución de dicho sistema es x
=3. A las restantes variables, las no básicas, se las da el valor cero y la solución básica que se obtiene es X=(0,3,0,0,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. De igual manera se construyen el resto de soluciones básicas, en este caso todas las submatrices 2x2 son básicas excepto la que forman las columnas tercera y quinta. En la siguiente tabla se presentan todas las soluciones básicas obtenidas. Variables básicas Variables no básicas Matriz básica Solución básica Tipo x
2 2 1 4 (0,3,0,0,0) Factible degenerada x
1 y x
2 0 1 -1 (3,0,-9,0,0) No factible x
2 1 1 0 (12,0,0,-18,0) No factible x
2 0 1 1 (3,0,0,0,9) Factible no degenerada x
2 0 4 -1 (0,3,0,0,0) Factible degenerada x
2 1 4 0 (0,3,0,0,0) Factible degenerada x
2 0 4 1 (0,3,0,0,0) Factible degenerada x
0 1 -1 0 (0,0,-12,6,0) No factible x
1 0 0 1 (0,0,0,6,12) Factible no degenerada Veamos, mediante un ejemplo el concepto de punto básico degenerado (menos de m componentes positivas) y no degenerado: Programación Lineal 31 Max z = x
+5x
3 =1 x
3 +2x
4 =1 x
> 0 (i=1, 2, 3, 4) El punto (1,0,0,0) es básico degenerado El punto (0,0,1,1) es básico no degenerado El punto (1/2, 1/4 ,1/4 ,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) = 4x + 3y st 30x + 20y s 1800 x + y s 80 x > 0 , y > 0 Tiene por región factible la región sombreada.
Los valores de la función objetivo en cada uno de los vértices son: f(O) = f(0,0) = 0; f(C)=f(60,0) = 240; f(D) = f(20,60) = 260; f(E) = f(0,80) = 240
La solución es única, y corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(20,60). Investigación Operativa 32 ii) Solución múltiple Maximizar la función z = f(x,y)= 4x + 2y st 2x + y s 4 , x - y s 1 , x > 0 , y > 0 Los valores de la función objetivo en cada uno de los vértices son: f(O)=f(0,0) = 0, f(A) = f(1,0) = 4 f(B)=f(5/3,2/3) = 8, f(C) = f(0,4) = 8 La función objetivo alcanza el valor máximo en los vértices B y C, por tanto, en todos los puntos del segmento BC. Hay infinitas soluciones, solución múltiple, que corresponden a los puntos del segmento situado entre dos vértices de la región factible. En estos casos, como ya vimos en el capítulo anterior, la función objetivo es paralela a una de las restricciones. iii) Solución no acotada (No existe límite para la función objetivo) Maximizar la función z = f(x,y) = x + y st y s 2x , y > x/2 Tiene por región factible la zona coloreada que aparece en la figura, que es una región no acotada. La función crece indefinidamente para valores crecientes de x e y. En este caso no existe un valor extremo para la función objetivo, por lo que puede decirse que el problema carece de solución. Para que suceda esta situación, la región factible debe estar no acotada. iv) Cuando no existe el conjunto de soluciones que cumplen las restricciones Maximizar la función z = f(x,y) = 3x + 8y st x + y 6 , x + y 2 , x 0 , y 0 No existe la región factible, ya que las zonas coloreadas que aparecen en la figura son únicamente soluciones de alguna de las inecuaciones .Por tanto, el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible. Este tipo de problemas carece de solución. 2.5. Resolución de un problema de programación lineal mediante el método gráfico Programación Lineal 33 Lo que se pretende con el método gráfico es dar una visión geométrica del problema que queremos resolver. Es evidente que su precisión no es la deseada, pero nos puede dar una aproximación a lo que queremos resolver. El procedimiento a seguir es: 1. Dibuje la gráfica de cada restricción sobre el mismo cuadrante no negativo. 2. Convierta las desigualdades en igualdades y represente la rectas que representan estas ecuaciones. 3. Escoja cualquier punto de ensayo que no pertenezca a la recta. 4. Evalúe el primer miembro de la expresión. Sustituya el punto de ensayo en el primer miembro de la desigualdad y obtenga el valor numérico. 5. Determine si el punto de ensayo satisface la desigualdad. 6. Si el punto de ensayo satisface la desigualdad original, entonces todos los puntos que estén del mismo lado que el punto de ensayo satisfacen la desigualdad, en caso contrario será un punto no factible. 7. Localice la región de soluciones factibles (Región Factible). 8. Dibuje una recta arbitraria de la función objetivo, por ejemplo pasando por el origen, para obtener la pendiente de la función objetivo. 9. Determine la dirección ascendente o descendente de esta recta. 10. Dada la pendiente de la función objetivo y teniendo en cuenta si es un problema de maximizar o minimizar, determine el vértice del conjunto factible que esté sobre la recta que representa la función objetivo. 11. Los valores de las variables de decisión, en este vértice, dan la solución al problema. 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. Ejercicio 3. Resolver gráficamente el problema siguiente: Un fabricante está tratando de decidir las cantidades de producción para dos artículos: mesas y sillas. Se cuenta con 96 unidades de material y con 72 horas de mano de obra. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. Por otra parte, las sillas utilizan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla. El margen de beneficio es el mismo para las mesas que para las sillas: 5 euros por unidad. El fabricante prometió construir por lo menos dos mesas. Solución: El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL. Función objetivo: Investigación Operativa 34 Maximizar z = 5x
2 en donde: x
= número de mesas producidas x
= número de sillas producidas Restricciones del problema (st): 12x
s 96 (restricción de material) 6x
+ 12x
s 72 (restricción de mano de obra) x
> 2 (restricción de promesa del fabricante) x
> 0 (restricciones de no negatividad) Poniendo todo junto el modelo, se tiene: Maximizar z = 5x
st 12x
s 96 6x
s 72 x
> 2 x
> 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. Ahora se utilizará la función objetivo para seleccionar la solución óptima. Programación Lineal 35 Representando por líneas discontinuas la función objetivo moviéndose hacia el valor óptimo (máximo) del problema, tenemos: El valor óptimo estará sobre la línea recta que representa a la función objetivo, más lejana al origen, 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. 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. Las coordenadas de este punto Investigación Operativa 36 resultan ser (6, 3). La sustitución de este punto en la función objetivo da la ganancia máxima: z = 5(6) + 5(3) = 45 euros. En un problema de Programación Lineal con dos variables, si la región factible existe y es acotada, el valor óptimo de la función objetivo se alcanza en uno de los vértices del polígono que limita la región, o a lo largo de uno de los lados. Si la región factible no es acotada, la función objetivo no alcanza necesariamente un valor óptimo concreto, pero si lo hace, éste se encuentra en uno de los vértices de la región. 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, y en aquel en el que el valor de la función sea mayor (o menor) habremos alcanzado el punto óptimo buscado. Si se da el caso de que los valores correspondientes a dos vértices coinciden, éstos serán adyacentes, de modo que a lo largo de ese lado del polígono se alcanza el mismo valor de la función objetivo, que es precisamente el valor óptimo. En este caso, las líneas de nivel tienen la misma pendiente que la recta que contiene a ese lado del polígono, es decir, son paralelas. 2.6. Propiedades de las soluciones Las soluciones de un problema de programación lineal tienen diversas propiedades, alguna de las cuales vamos ver. Designemos por K el conjunto de las soluciones factibles de un problema de programación lineal; K es una región de R
determinada por la intersección del conjunto finito de restricciones lineales (2.2) y (2.3), por lo que K es: i) K = C, no tiene solución el problema de programación lineal. ii) K = C, cuando K tenga un número finito de vértices que se puedan alcanzar todos (poliedro convexo). Existe solución de valor finito de la función objetivo. iii) K = C, cuando K tenga un número finito de vértices que no se puedan alcanzar todos (región convexa ilimitada). El problema tiene solución, pero el máximo podría ser ilimitado. Si K es un poliedro convexo, entonces K es la envolvente convexa de los puntos extremos de 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). Proposición 2.1. El conjunto de soluciones factibles de un problema de programación lineal es un conjunto convexo. Demostración Programación Lineal 37 Sean X
soluciones factibles, entonces A X
= b, A X
2 = b, X
2 > 0. Si formamos un vector X que sea combinación lineal de éstos dos: X = o X
+ (1-o) X
, AX = o AX
+ (1-o) A X
= o b + (1-o) b =b por lo que X es también una solución factible. Proposición 2.2. Si K es un poliedro convexo, entonces la función objetivo z dada por (2.1) alcanza su mínimo en un vértice de K; además, si este mínimo se alcanza en varios puntos, también se alcanza en cualquier combinación lineal convexa de los mismos. Demostración Sean X
los vértices de K y sea X
una solución factible mínima, esto significa que c
X para cada XeK. X1
Se pueden dar los casos siguientes: i) Si X
es un vértice de K, ya estaría demostrado. ii) Si X
no es un vértice de K, entonces X
se podrá poner como una combinación lineal convexa de ellos: X
> 0 ; o
Sustituyendo: Min z = m= c
+…+o
) Investigación Operativa 38 Supongamos que c
m > c
> m por consiguiente c
= m, es decir, que existe un vértice de K en el que la función objetivo z= c
X alcanza su valor mínimo. Para probar la segunda parte de la propiedad supongamos que z alcanza su valor mínimo en X
y que X es una combinación lineal convexa de ellos: X = ¿
> 0 , o
= = (mo
+…+mo
) = m (o
) = m con lo cual la proposición queda demostrada. Proposición 2.3. Si tenemos un conjunto de k vectores A
,…, A
, que sean linealmente independientes y de forma que: x
k = b con las x
i > 0, entonces, el punto X = (x
, 0,…, 0)
es un vértice del conjunto convexo K de soluciones factibles. Demostración Supongamos que X no fuera vértice, entonces podría expresarse como combinación lineal convexa de dos puntos distintos de K: X = o X
, oe[0, 1], X
eK Puesto que las coordenadas de las soluciones factibles son no negativas y o>0 deberá ocurrir que las n-k coordenadas últimas de X
2 fueran iguales a cero: X
. Además, por ser soluciones factibles, se cumple que AX
=b y AX
=b, por lo que podemos escribir: x
k = b x
k = b Programación Lineal 39 Restando las expresiones anteriores obtenemos: (x
+ (x
2 +…+ (x
= 0 y por ser los vectores A
linealmente independiente llegamos a la conclusión de que: x
es decir, que X
, lo que contradice el hecho de haber supuesto X
, por lo que necesariamente X debe ser un vértice de K. Proposición 2.4. Si tenemos un vector X = (x
es un vértice de K, entonces los vectores A
asociados con las coordenadas x
positivas forman un sistema linealmente independiente, de lo que se sigue que, a lo sumo, m de estas coordenadas x
son positivas. Demostración: Supongamos, para simplificar, que las k primeras coordenadas son las no nulas, entonces : x
k = b Si los vectores A
son linealmente dependientes, podremos encontrar una combinación lineal de los mismos igual a cero con algún coeficiente no nulo: ì
+ ì
2 +…+ ì
k = 0 Así tenemos: x
i = b ¿
i = 0 =
donde c > 0. Si los sumamos y restamos: Investigación Operativa 40 x
i + c ì
i - c ì
Es decir, desarrollando las expresiones anteriores: (x
+ c ì
1 ) A
+…+ (x
k ) A
= b (x
- c ì
= b De manera que tenemos dos soluciones distintas del sistema de ecuaciones: X
, 0,… 0)
T Sumando X
, resulta: X
= ( 2x
,…, 2x
= 2X Despejando X= ½ (X
), lo cual contradice el hecho de que X sea vértice. De ahí que, no puede hacerse la hipótesis de que los vectores A
sean linealmente dependientes, por tanto son linealmente independientes y, como estos vectores son m-dimensionales no podremos tener más de m linealmente independientes, de ahí que, como máximo, m de las x
serán positivas. Proposición 2.5. A cada punto extremo del poliedro convexo se encuentra asociado un conjunto de m vectores linealmente independientes del conjunto dado . n
A A A , , ,
Demostración La Proposición 2.4. prueba que existen k m s vectores linealmente independientes. Para k =m la propiedad 2.5 queda comprobada. Supongamos que y que podemos encontrar solamente vectores adicionales tales que el conjunto , para m k<
A A , ,
r k k
A A A A , , , , ,
 
r< es linealmente independiente. Los n-r vectores restantes dependen de . Esto contradice la suposición de que tenemos siempre un conjunto de m vectores linealmente independientes asociados con cada punto extremo. r
Programación Lineal 41 Teorema 2.1. (Caracterización de los vértices de K) El vector X = (x
, de coordenadas no negativas, es un vértice de K (conjunto convexo de soluciones factibles), si x
n = b y las x
i > 0 son coeficientes de los vectores A
linealmente independientes. Demostración La demostración es inmediata aplicando las proposiciones 3 y 4. Resumiendo lo anteriormente expuesto mediante propiedades y teoremas tenemos: Si existe solución al problema de programación lineal, 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). Max z = Min (-z) Cada solución factible básica corresponde a un vértice de K. A cada vértice de K se puede asociar una base de dimensión m del conjunto de vectores A
. El máximo número de vértices que puede tener el convexo K es C
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. 2.7. 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, las diversas circunstancias de su preparación antes de aplicar el algoritmo y los casos especiales identificables en la tabla solución (última tabla). Sea el problema de programación lineal: Min z = c
X 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 del conjunto original de n vectores. Podemos hacer que este conjunto de m vectores linealmente independientes sean los primeros m, es decir, que las variables no nulas sean las n-m finales X = (x
, 0, ..., 0)
que verifica: j
Investigación Operativa 42 j j m m
x b A x A x A x ¬ > = + + + , 0 ,
 (2.1) Como los vectores forman una base en el espacio m-dimensional, R
, podemos expresar cada uno de los n vectores dados como combinación lineal de los vectores de esa base: m
n j A A
j i ij
, , 2 , 1 ,  = = o
y si escribimos todas las ecuaciones: (2.2) ¦
n m mn n n
2 2 2 22 1 12
1 1 2 21 1 11
y la función objetivo z tomará en el vértice X el valor: z = c
m (2.3)
Observando en (2.1) que, si A
es la base canónica de los vectores unitarios entonces x
. Tomemos un j de modo que A
j no esté en la base dada, pues bien si a (2.1) le restamos (2.2) multiplicada por un escalar u
, resulta: (x
1 + (x
+ … + (x
= b (2.4) con lo cual, si elegimos u
> 0, de modo que x
> 0 para i=1, 2, ..., m tendremos que el vector X’ = (x’
, x’
,…, x’
es una solución factible, donde: x’
> 0, i=1, 2, …, m (2.5) x’
> 0, i=j x’
= 0, en los demás casos La función objetivo en X’ = (x’
, solución factible, toma el valor z’ = c
’ + c
’+ … + c
= = c
) + … + c
= = z - u
) (2.6) donde z es el valor de la función objetivo en X, y z
viene dada por la expresión: Programación Lineal 43 z
(2.7) así pues, en (2.6) vemos que debemos seleccionar u
y j de forma que verificándose (2.5) se tenga que u
) sea positivo y máximo, con lo cual z’<z, z’= z- u
j (z
). El procedimiento consiste, por tanto, en calcular las cantidades (z
) > 0 observando las relaciones (2.5), éstas corresponden a las variables cuyos vectores asociados, si los incluimos en la base, mejoran el valor de la función objetivo. Estudiaremos dos casos: i) o
> 0 ii) o
s 0 Caso i): u
> 0, o
> 0 x’
> 0, u
> 0 / min
(2.8) y esto para cada j para el que se cumpla (z
) > 0, a continuación calcularemos los productos u
) y nos quedaremos con el índice j que da el producto mayor, supongamos que éste es j=m+1, ello significará que seleccionamos el vector A
, por otra parte, si el mínimo en (2.8) se alcanza, por ejemplo, para i=1, es decir: u
= 1 , 1
(2.9) ello significará que x
’ = x
1, m+1
= 0, por lo que la nueva solución factible X’ = (x’
= (0, x
’, …, x
’, u
, 0, …, 0)
será un vértice de K (conjunto de soluciones factibles) si los vectores A
son linealmente independientes (Vea el teorema de caracterización de los vértices de K). Para probar que los vectores A
son linealmente independientes, supongamos que fueran linealmente dependientes, esto quiere decir que existirá ì
tal que ì
2 + ì
+ … + ì
m+1 A
= 0 (2.10) para algún ì
distinto de cero y, puesto que los vectores A
son linealmente independientes, deberá ser ì
=0. Por tanto, despejando A
de (2.10), obtenemos: Investigación Operativa 44 A
3 -…- 1 + m
m haciendo ¸ i
=- 1 m
(i=2, . .., m) A
= ¸ 2
2 + ¸ 3
3 +…+ ¸ m
m (2.11) Restando (2.11) de (2.2), con j=m+1, encontramos que A
1 + o 2, m+1
2 +…+ o m, m+1
m 0 = o
1 + (o 2, m+1
- ¸ 2
2 +…+ (o m, m+1
- ¸ m
m por lo que, al ser A
m linealmente independientes obliga a que o
1,m+1
=0 y, sin embargo se supuso positivo (vea (2.9)). En consecuencia, A
son linealmente independientes, 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. 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 z
s 0 para todos los valores de j=1, 2, ..., n, en cuyo caso ya no se podría disminuir la función objetivo y, por tanto, se habría alcanzado el mínimo con el vector X que se tuviera en esa etapa. Caso ii): u
s 0 x’
z’ = z- u
j ) , con (z
j ) >0 Como se puede elegir un u
j tan grande como quiera, ocurrirá que z’ tiende a menos infinito, es decir, no existe solució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). Por supuesto encontrar todas las soluciones básicas de un programa lineal requiere de grandes esfuerzos de cálculo, únicamente resulta sencillo en problemas con pocas variables de decisión. 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. Programación Lineal 45 Dentro de los aspectos computacionales, 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, el método Simplex no resulta muy económico desde un punto de vista computacional, ya que se almacenan y calculan muchos números que no son estrictamente necesarios. Por ejemplo, en las tablas del simplex aparecen gran número de ceros; para un humano no supone ningún problema reconocer los ceros y darse cuenta que al multiplicar un número por cero resulta cero, o que sumar cero a un número no altera el resultado. Sin embargo, un computador no reconoce esas situaciones y pierde tiempo realizando operaciones que realmente no son necesarias. Investigación Operativa 46 Teorema 2.2. Si en algún paso (puede ser el primero) del método simplex se verifica que (z
) s 0, ¬j (j=1, 2, ..., n), entonces, el último vértice obtenido es la solución óptima. Demostración Sea X = (x
un punto extremo en el cual la función objetivo vale z
y para el que se verifica que (z
) s 0, ¬j (j=1, 2, ..., n). Hemos de probar que para cualquier otra solución (z
) s 0, ¬j (j=1, 2, ..., n) Y= (y
,…, y
, con y
i > 0 y valor de la función objetivo: z = c
(2.12) se verifica z
s z. Como (z
) s 0 ¬ z
y sustituyendo en la expresión (2.12) cada c
tenemos: z
+ … + z
s z (2.13) Sustituyendo en (2.13) cada z
(j=1, 2,..., n) por su valor z
tenemos: ( c
+ … + (
s z ¿
Agrupando términos en c i
(i=1, 2, ..., m) se tiene: c 1
) + … +c
m ( o
) s z (2.14) ¿
1 j =
Puesto que Y es una solución factible Programación Lineal 47 y 1
+ … + y
= b (2.15) Sustituyendo A
(j=1, 2, ..., n) por su valor: A
+ … + o
A i ¿
Sustituyendo este valor en (2.15) para cada uno de los j: y 1
) + y
) + … + y
n ( o
) = b =
Ahora agrupamos términos en A i
j )A 1
+ ( o
Como X es un punto extremo x 1
= b y por ser los vectores A
linealmente independientes, b se escribe de forma única, por lo cual: x
j ; x
j ; …; x
Sustituyendo en (2.14) se tiene: c
s z es decir z
s z . Ejercicio 1. Resuelva mediante el Método Simplex el problema de programación lineal siguiente: Min z = –5x
st 2x
s4 Investigación Operativa 48 3x
s3 2x
s5 x
> 0 (i=1, 2, 3) Pasando el problema a forma estándar añadiendo variables artificiales, de manera que tengamos una base canónica para comenzar el método del simplex: Min z = - 5x
+0x
4 = 4 3x
5 = 3 2x
= 5 x
> 0 (i=1, 2, 3) Primera tabla Se lleva a la tabla los datos del problema y se comienza a operar de acuerdo con el algoritmo del simplex: c
-5 2 -3 0 0 0 Base c
0 4 2 2 -1 1 0 0 2 -- A
0 3 3 -1 1 0 1 0 1 3 A
0 5 2 1 3 0 0 1 5/2 5/3 z, z
0 0 0 0 0 0 0 1 5/3 z
5 -2 3 0 0 0 u
) 5 - 5 - - - El vértice inicial de partida es X=(0, 0, 0, 4, 3, 5)
. Para ver que vector sale de la base y cuál entra operamos de la forma siguiente: i) Calculamos z
. ii) Calculamos (z
). iii) Para los valores (z
) >0 calculamos u
> = 0 / min
. iv) Buscando que u
) sea positivo y máximo. v) El valor de i que hace ¦
nos proporciona el vector i-ésimo que sale de la base y, el valor de j que hace u
) nos proporciona el vector j-ésimo que entra en la base. j
Por ejemplo, para j=1, tenemos, z
2=0, z
=0 - (-5)=5 Programación Lineal 49 Realizadas las operaciones correspondientes, tenemos: - El vector que entra en la base es el A
5=5). 1
- El vector que sale de la base es el A
=1). El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote, en nuestro caso el 3, que se genera en el cruce del vector que entra y el vector que sale, deberá valer uno y el resto cero. Este proceso se repite de forma iterativa hasta que se verifique (z
) s 0, ¬j (j=1, 2, ..., n). El vector A
que entra en la base se convierte en un elemento de la base canónica. El elemento pivote (que ha de ser un 1) se forma en el cruce del vector que entra con el que sale (A
). Veamos como se obtiene : |
3 3 -1 1 0 1 0 A
/3 1 1 -1/3 1/3 0 1/3 0 A
4 2 2 -1 1 0 0 2·A
2 2 -2/3 2/3 0 2/3 0 A
-2·A
2 0 8/3 -5/3 1 -2/3 0 A
5 2 1 3 0 0 1 2·A
3 0 5/3 7/3 0 -2/3 1 Llevando lo anterior a la tabla, tenemos: c
1 1 -1/3 1/3 0 1/3 0 A
3 0 5/3 7/3 0 -2/3 1 Investigación Operativa 50 Segunda tabla c
0 2 0 8/3 -5/3 1 -2/3 0 - A
-5 1 1 -1/3 1/3 0 1/3 0 3 A
0 3 0 5/3 7/3 0 -2/3 1 9/7 z, z
j -5 -5 5/3 -5/3 0 -5/3 0 9/7 z
0 -1/3 4/3 0 -5/3 0 u
) - 12/7 - - - Entra A
y sale A
. Tercera tabla c
0 29/7=4.1448 0 22/7 0 1 -8/7 5/7 A
-5 4/7=0.5714 1 -4/7 0 0 3/7 -1/7 A
-3 9/7=1.2857 0 5/7 1 0 -2/7 3/7 z, z
-47/7=-6.7142 -5 5/7 -3 0 -9/7 -4/7 z
0 -9/7 0 0 -9/7 -4/7 u
) - - - - - Observando la tabla tenemos (z
) s 0, ¬j (j=1, 2, ..., n), por lo que hemos llegado a la etapa final. Para buscar la solución dentro de la tabla miramos la columna b y encontramos: x
=4/7=0.5714, x
=0 (no aparece), x
=9/7=1.2857, z = -6.7142 El vértice final obtenido es X=(4/7, 0, 9/7, 29/7, 0, 0)
. La solución mediante la matriz inversa asociada a la tabla del simplex, B
la podemos encontrar directamente en la última tabla del simplex observando los vectores correspondientes a los de la base inicial, en este caso a los vectores A
5 y A
de la tabla: =
B {A
}= |
7 / 3 7 / 2 0
7 / 1 7 / 3 0
7 / 5 7 / 8 1
Programación Lineal 51 = =
X b B
y la matriz B se obtiene de la primera tabla mirando la base que figura en la última tabla del simplex, A
: B {A
Si resolvemos el ejercicio anterior con el programa LINDO, tenemos: Min -5x1+2x2-3x3 st 2x1+2x2-x3 <= 4 3x1- x2+x3 <= 3 2x1+x2+3x3 <=5 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) -6.714286 VARIABLE VALUE REDUCED COST X1 0.571429 0.000000 X2 0.000000 1.285714 X3 1.285714 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 4.142857 0.000000 3) 0.000000 1.285714 4) 0.000000 0.571429 THE TABLEAU ROW (BASIS) X1(A ) X2(A ) X3(A ) SLK 2(A ) SLK 3(A ) 1 2 3 4 5
1 ART 0.000 1.286 0.000 0.000 1.286 2 SLK 2(A
) 0.000 3.857 0.000 1.000 -1.143 3 X1(A
) 1.000 -0.571 0.000 0.000 0.429 4 X3(A
) 0.000 0.714 1.000 0.000 -0.286 ROW SLK 4(A
) 1 0.571 6.714 2 0.714 4.143 3 -0.143 0.571 Investigación Operativa 52 =
4 0.429 1.286 Operando de la misma forma para obtener las matrices: {A
= B {A
Ejercicio 2. Considere el problema siguiente: Max z= 5x
> 0 (i=1, 2, 3) Para ciertos valores de los recursos, la solución es: c
0 0 Base c
-5 30 1 b 2 1 0 A
0 10 0 c -8 -1 1 z
-150 0 a -7 d e Calcule: a) Los recursos. b) Los valores de: a, b, c, d, e, c
. Solución: Tabla 1 c
-5 -2 -3 0 0 Base c
1 5 2 1 0 A
1 -5 -6 0 1 z, z
0 5 2 3 0 0 Programación Lineal 53 Tabla 2 Por la información que nos proporciona la tabla del enunciado, sale de la base A
4 y entra A
-5 b
0 -10 -8 -1 1 z, z
-150 0 -23 -7 -5 0 Identificando, tenemos: a) b
= 30, b
=10, b
= 40, b) a= -23, b = 5, c= -10, d= -5, e= 0, c
= -3 2.8. 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. Si al introducir las variables de holgura necesarias para escribir el problema en forma estándar ya tenemos la base canónica, podremos aplicar directamente el método del simplex. 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. Para conseguir partir de una base canónica, para iniciar el método simplex, necesitaremos de lo que se conoce como variables artificiales. Éstas construyen un problema artificial más conveniente desde el punto de vista del método simplex. Es oportuno resaltar la diferencia entre variables de holgura y variables artificiales. Las primeras se introducen para convertir desigualdades en igualdades, mientras que las variables artificiales se introducen para facilitar el comienzo del método simplex. La base canónica inicial la configuraremos con las variables de holgura más las variables artificiales necesarias hasta tener esa base canónica. Veamos, a continuación, un método que nos ayude a resolver los problemas que contengan variables artificiales. Investigación Operativa 54 2.8.1. 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. 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. Consideremos el siguiente problema de programación lineal planteado en su forma estándar: Min z = c
X 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, con lo cual tenemos el sistema siguiente: AX + I X
= b X > 0, X
> 0 Tenemos como solución inicial: X
=b, X=0 Debemos buscar la forma de hacer salir las variables artificiales, es decir, las X
, y que entren las otras variables. Para ello les asociamos un valor muy grande M ( no es necesario especificar el valor de M) en la función objetivo. Min z = c
X + M 1
st AX + I X
=b X > 0, X
> 0 En la resolución del problema por este método, pueden presentarse los casos siguientes: a) Tengamos solución finita: i) Que el problema admita una solución óptima, con todas las variables artificiales iguales a cero, X
= 0, entonces la solución obtenida es única y óptima. Programación Lineal 55 ii) Que el problema admita una solución óptima en la cual encontraremos al menos una variable artificial distinta de cero, X
= 0, entonces el problema original es imposible, no tenemos solución. b) Tengamos solución no finita: iii) Con todas las variables artificiales iguales a cero, X
= 0, en este caso tenemos una solución no finita. iv) Exista al menos una variable artificial que sea positiva, entonces el problema original es imposible. Consideremos el siguiente problema: Max z = x
+6x
3 =20 2x
3 s 40 2x
3 > 55 x
> 0 (i=1, 2, 3) Como explicamos anteriormente, para resolver este problema, debemos construir un problema “artificial” que tiene, en caso de que exista, la misma solución óptima que el problema real. Min z = - x
+ 0 x
+ M x
6 =20 2x
4 = 40 2x
= 55 x
> 0 (i=1, 2, ..., 7) Primera tabla Se llevan a la tabla los datos del problema “artificial” y se comienza a operar de acuerdo con el algoritmo del simplex: c
-1 -6 4 0 0 M M Base c
M 20 1 2 -1 0 0 1 0 10 A
0 40 2 1 1 1 0 0 0 40 A
M 55 2 1 4 0 -1 0 1 55 z, z
75M 3M 3M 3M 0 -M M M z
3M+1 3M+6 3M-4 0 -M 0 0 u
) 30M+60 Investigación Operativa 56 A los valores que hayan resultado ser (z
) >0, en nuestro caso se da para varios j, elegimos la de mayor diferencia y aplicamos el criterio u
y buscando que u
) sea positivo y máximo, tenemos que entra A
, que, por corresponder a una variable artificial, ya nunca más volverá a entrar. El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote, en nuestro caso el 2, que se genera en el cruce del vector que entra y el vector que sale, deberá valer uno y el resto cero. Este proceso se repite de forma iterativa hasta que se verifique (z
) s 0, ¬j (j=1, 2, ..., n). Segunda tabla c
-6 10 1/2 1 -1/2 0 0 - 0 - A
0 30 3/2 0 3/2 1 0 - 0 20 A
M 45 3/2 0 9/2 0 -1 - 1 10 z, z
45M-60 3M/2-3 -6 3M 0 -M - M z
3M/2-2 0 9M/2-1 0 -M - 0 u
) 45M+10 Entra A
, que, por corresponder a una variable artificial, ya nunca más volverá a entrar. Tercera tabla c
-6 15 2/3 1 0 0 -1/9 - - A
0 15 1 0 0 1 1/3 - - A
4 10 1/3 0 1 0 -2/9 - - z, z
-50 -8/3 -6 0 0 -2/9 - - z
-5/3 0 0 0 -2/9 - - Observando la tabla tenemos (z
) s 0, ¬j (j=1, 2, ..., n), por lo que hemos llegado a la etapa final. Para buscar la solución dentro de la tabla miramos la columna b y encontramos: Programación Lineal 57 x
2 =15, x
= 10, x
4 =15, x
= 0, z = -50 Luego, la solución del problema original planteado (maximización) es: x
= 10, z = 50 2.8.2 Método de las dos fases Supongamos un problema planteado en su forma estándar Min z = c
X st AX = b X > 0 Añadimos en las restricciones las variables artificiales, X
, necesarias para tener en la primera tabla del simplex una base canónica, con lo cual tenemos el sistema siguiente: AX + I X
> 0 Su resolución se abordará en dos fases: Fase I: Esta primera fase consiste en resolver previamente el problema siguiente: Min z = 1
> 0 Si el problema original tienen solución factible, el mínimo del problema anterior se alcanzará cuando las variables artificiales X
=0 y z=0. Fase II: En esta segunda fase, resolveremos el problema original planteado utilizando la última matriz obtenida en la Fase I y por tanto dicha base. Consideremos el siguiente problema: Investigación Operativa 58 Min z = x
> 2 -x
> 1 x
s 3 x
> 0 , x
> 0 Vamos a resolverlo por el método de las dos fases. El problema con las variables de exceso , 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 = a
=2 - x
=1 x
=3 pasamos a la tabla los datos y operamos según el algoritmo del simplex, tenemos: Primera tabla c
0 0 0 1 0 1 0 Base c
1 2 1 1 -1 1 0 0 0 2 A
1 1 -1 1 0 0 -1 1 0 1 A
0 3 0 1 0 0 0 0 1 3 z z
3 0 2 -1 1 -1 1 0 1 z
0 2 -1 0 -1 0 0 Segunda tabla c
1 1 2 0 -1 1 1 - 0 1 /2 1 A
0 1 -1 1 0 0 -1 - 0 - - A
0 2 1 0 0 0 1 - 1 2 2 z z
1 2 0 -1 1 1 - 0 1/2 1 z
2 0 -1 0 1 -2 0 u
1 - - - 1 Solución de la tabla, h
=2, a
=1, x
=1, z=1, al ser la función objetivo de minimizar y tener z
positivos la solución no es óptima. Para los z
>0 Programación Lineal 59 calculamos u
, y el valor máximo de u
) se alcanza en x
1 y en h
, tomamos x
por tener mayor z
, será la nueva variable básica, siendo a
la fila donde se alcanza el valor mínimo de u
y por lo tanto la variable que deja de ser variable básica, la cual no volverá a entrar en la base y por lo tanto se puede eliminar de la tabla, con lo cual terminamos la primera fase al obtener en la próxima tabla z=0 con a
=0, a
=0. Introducimos entonces la función objetivo original min z=x
y continuamos con el algoritmo del simplex: Tercera tabla c
1 -2 0 0 0 Base c
1 1 /2 1 0 -1/2 1 /2 0 - 1 A
-2 3/2 0 1 -1/2 -1/2 0 - - A
0 3/2 0 0 1/2 1/2 1 3 3 z z
-5/2 1 -2 1/2 3/2 0 3 1 z
0 0 1/2 3/2 0 u
- - 3/2 3/2 - Cuarta tabla c
0 1 2 0 -1 1 0 - A
-2 2 1 1 -1 0 0 - A
0 1 -1 0 1 0 1 1 z z
-4 -2 -2 2 0 0 z
-1 0 2 0 0 Solución de la tabla, h
=2 h
=1, z=-4, la solución no es óptima. Para los z
>0 calculamos u
será la nueva variable básica, siendo h
y por lo tanto la variable que deja de ser variable básica. c
0 2 1 0 0 1 1 A
-2 3 0 1 0 0 1 A
0 1 -1 0 1 0 1 z z
-6 0 -2 0 0 -2
-1 0 0 0 -2
El punto extremo es X
=(0, 3, 0, 0, 0, 0)
, z=-6. Investigación Operativa 60 2.9. 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. Toda solución óptima es una combinación lineal convexa de las soluciones factibles básicas óptimas. El método simplex se detiene automáticamente al encontrar una solución factible básica óptima. Una vez que el método simplex encuentra una solución factible básica óptima, se puede detectar si existen otras y, si es así, se encuentra observando si tengo algún vector j, tal que no pertenece a la base, pero que cumple (z
)= 0, esto nos indicará que existe multiplicidad de óptimos. Supongamos que ya hemos encontrado una solución óptima (mínima) de un problema y que se verifica (z
) s 0, ¬j. La función objetivo es: z’ = z - u
) = z no hemos mejorado la solución anterior. Repitiendo este proceso para cada una de las “j” que no pertenecen a la base y verifican (z
j - c
)= 0, obtendríamos todos los vértices que son soluciones óptimas. Tomando una combinación lineal convexa de ellas, también sería solución óptima, por lo cual el problema tiene infinitas soluciones. Compruebe, mediante el método simplex, que el problema siguiente presenta dos puntos extremos. Min z = x
4 =10 x
3 s 1 x
4 s 8 x
> 0 (i=1, 2, ..., 6) Los puntos extremos son: X
=(2, 0, 0, 4, 1, 0)
=(4, 1, 0, 7/2, 0, 0)
así como toda combinación convexa de dichos puntos. 2.10. Soluciones degeneradas Al desarrollar el algoritmo del simplex supusimos que las soluciones eran siempre no degeneradas, de manera que, en un número finito de iteraciones llegábamos a la solución óptima. Programación Lineal 61 Ahora bien, si al calcular el valor de u
existen varios i tal que minimizan ij
, no se podría hacer salir a la vez a todos ellos. Se podría elegir uno cualquiera y, entonces, 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, es decir, estaríamos en un punto extremo que tiene menos de “m” coordenadas positivas, esto es, 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. Este caso se presenta cuando se valora una solución básica no única, la cual se tiene con al menos una variable básica de valor cero en el sistema de m restricciones, alguna de ellas debe ser restricción redundante que contiene sólo un punto vértice del conjunto factible. 2.11. El método del simplex revisado Un procedimiento más eficiente que el simplex en su versión matricial es el llamado simplex revisado. Consideremos el siguiente problema de programación lineal: Min z = c
X st AX = b X > 0 donde A es una matriz de orden mxn y sea rang (A, b) = rang (A) = m. Denotemos por A
la columna i-ésima de la matriz A y supongamos que los m vectores linealmente independientes son los m primeros A
, la matriz B= (A
) es la matriz básica. Descomponiendo la matriz A de forma que A=(B, N) donde B
es la matriz básica y N
(mx(n-m))
, la matriz no básica (los A
que no son de la base). Cualquier solución básica es de la forma X= |
N = 0 y BX
B = b Si X
es una solución factible básica, X
, tenemos BX
B = b, X
b Investigación Operativa 62 y puesto que A
esto es A
= (o
, …, o
El valor de la función objetivo en ese punto es z = c
b y los valores de z
= ì
Donde ì
, al vector columna ì
se le denomina vector de multiplicadores del simplex asociado a la base B. Veamos el ejercicio siguiente. Dada la tabla óptima del Simplex: c
0.75 1 0 0 0.5 -0.5 - A
1.75 0 0 1 0.5 0.5 - A
3.25 0 1 0 -0.5 1.5 - z z
-4.75 -2 -1 0 -0.5 -0.5 - z
0 0 0 -0.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, si se sabe que la primera restricción es (>) y el resto (s). Escriba la solución en el recuadro adjunto.
Ayuda: Max z= |
B st b) Formule el problema Dual y de la solución sin hacer operaciones. Programación Lineal 63 Solución: a) La matriz inversa se obtiene directamente de la tabla: B
= , (B
=B= |
5 . 1 5 . 0 0
5 . 0 5 . 0 1
5 . 0 5 . 0 0
A continuación se calculan los vectores A
(j=1, 2, 3): A
= para j=1 |
X=b= |
25 . 3
75 . 1
La formulación del problema sería: Max z= 2x
st 2 x
> 3 3x
s 5.5 x
2 s 4 x
> 0 b) Operando con el vector de multiplicadores del simplex asociado a la base B, tenemos: c
B=(0 0.5 0.5) ) 1 0 2 (
Investigación Operativa 64 2.11.1. Determinación de la inversa. Forma producto de la inversa Sea B una base y B
su inversa, si realizamos un cambio de base a la base B
, podemos conocer B
en términos de B
. En efecto, sea B= (A
) y supongamos que al realizar el cambio de base introducimos el vector A
= R donde R es la matriz identidad reemplazando la r-ésima columna por el vector columna X
; esto es: R= |
1 ... ... 0 0
.. .......... ..........
0 ... ... 1 0
0 ... ... 0 1
La inversa de R la denotamos por E y viene dada por E=R
1 ... / ... 0 0
0 .. .. / 1 ... 0 0
. .......... .......... ..........
0 ... / ... 1 0
0 ... / ... 0 1
rj mj
= E B
, a la matriz E
se la denomina matriz elemental. Cuando comenzábamos el método del simplex, tomábamos la base canónica, es decir, B
=I, B
-1 = I y X
B = b. Siguiendo un proceso iterativo, tenemos: B
I= E
y, en general la inversa de la base de la k-ésima iteración se obtiene B
…. E
Programación Lineal 65 que expresa la inversa como producto de matrices elementales. A dicha expresión se la conoce como forma producto de la inversa. 2.11.2. Etapas del método del simplex revisado Toda la información necesaria para aplicar el método del simplex se puede escribir en una tabla: ì
…. z
La última columna representa la situación en la k-ésima iteración. En cada iteración hay que controlar si todos los (z
) s 0 ¬j, en cuyo caso ya tendríamos la solución óptima. Si para algún (z
) > 0 y X
s 0, la función objetivo no tendría solución finita. 2.12. Resolución mediante programa de ordenador 1. Si el programa requiere que todas las variables sean no negativas, se pondrán de manera que cumplan esta condición. Las modificaciones deben ser hechas antes de introducir los datos en el programa. 2. Todas las variables de las restricciones deben aparecer en el primer miembro, en tanto que todos los términos constantes (recursos) aparecerán a la derecha. 3. En la columna de variables de holgura (SLACK OR SURPLUS) vienen los resultados de esas variables (por restricción), las de valor cero indicarán que el recurso se ha consumido en su totalidad. El número de variables positivas (decisión + holgura) al finalizar el Simplex debe ser igual al número de restricciones, de lo contrario el problema es degenerado. Hay que hacer notar que la presentación de la salida depende del programa utilizado. Nosotros, mientras no se diga lo contrario, utilizaremos el programa LINDO (L = Linear IN = Interactive D = Discrete O = Optimizer). Utilizando el programa LINDO para resolver el ejercicio 1, tenemos: Min z = –5x
s4 3x
> 0 (i=1, 2, 3) Investigación Operativa 66 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) -6.714286 VARIABLE VALUE REDUCED COST X1 0.571429 0.000000 X2 0.000000 1.285714 X3 1.285714 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 4.142857 0.000000 3) 0.000000 1.285714 4) 0.000000 0.571429 NO. ITERATIONS= 2 THE TABLEAU ROW (BASIS) X1 X2 X3 SLK 2 SLK 3 1 ART 0.000 1.286 0.000 0.000 1.286 2 SLK 2 0.000 3.857 0.000 1.000 -1.143 3 X1 1.000 -0.571 0.000 0.000 0.429 4 X3 0.000 0.714 1.000 0.000 -0.286 ROW SLK 4 1 0.571 6.714 2 0.714 4.143 3 -0.143 0.571 4 0.429 1.286 Observando la salida del programa, el resultado es: z = -6.714286; x
= 4/7=0.5714, x
=9/7=1.2857 Que coincide con el obtenido mediante el algoritmo del simplex. 22
Q. MARTÍN MARTÍN
estudio comenzó en 1951 y fue desarrollado por Dantzig. Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro John Von Neumann (1903-1957), quien en 1928 publicó su famoso trabajo sobre Teoría de juegos. La Programación Lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables. El nombre Programación Lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate. La Investigación Operativa en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de los momentos más importantes fue la aparición del Método del Simplex. Este método, desarrollado por G. B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas. Partiendo de uno de los vértices de la región factible, por ejemplo el vértice P, y aplicando la propiedad: si la función objetivo no toma su valor mínimo en el vértice P, entonces existe una arista que parte del vértice P y a lo largo de la cual la función objetivo no aumenta, es decir, se pasa a otro vértice donde el valor de función objetivo sea menor o igual que el alcanzado en P. Iniciarse en la técnica de programación lineal teniendo como referencia al método científico: la representación o modelo en formulación matemática lineal de algunos problemas elegidos, será nuestro objetivo en este capítulo. La Programación Lineal es una de las técnicas agrupadas como programación matemática, aplicable a problemas de asignación de recursos limitados, con actividades competitivas hacia un objetivo común, que puede ser de maximizar beneficios o minimizar pérdidas. Se utiliza un modelo matemático con representación válida de la problemática en estudio; sus relaciones deben ser lineales, que significa utilizar, sólo variables de primer grado en cada término. El objetivo de la Programación Lineal es encontrar el valor de la función que Max (Min) z = c1 x1 + c2 x2 + … + cn xn denominada función objetivo. La función objetivo se encuentra sujeta a una serie de restricciones
Programación Lineal st a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. am1 x1 + am2 x2 + … + amn xn = bm donde xi  0 (i=1, 2, …, n) son las condiciones de no negatividad de las variables. Cada columna de coeficientes:
 a1 j     a2 j  Aj = , ...   a   mj 
 x1     x2  X=   ...   x   n
 a11 a12 ... a1n b1     a21 a22 ... a2 n b2  (A1, A2 ,…, An, b )=  ........................     a a ... a b  m1 m 2 mn m   x1 A1+ x2 A2 +…+ xn An  b; xi  0, i Matricialmente lo anterior se escribe como: Max z = cTX st AX  b X0 siendo z: la función objetivo c = (c1,...,cn) T : vector de coeficientes de la función objetivo. X = (x1,...,xn)T: vector de variables de decisión. A = (...,aij,...): matriz de coeficientes técnicos (i =1, 2, ..., m; j =1, 2, ..., n). b = (b1,...,bm) T : vector de demandas (recursos). El conjunto de soluciones factibles de un problema de Programación Lineal viene dado por:
Investigación Operativa X = {x Rn / A x  b , x  0}
Como se verá posteriormente, todos los óptimos (si existen) deberán estar en la frontera del conjunto de soluciones factibles. La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada.
Región factible no acotada La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio ( o ) o en sentido estricto (< o >). Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones siempre que no haya restricciones redundantes.
Región factible acotada
2.2. Formulación de un problema de Programación Lineal
Para que un modelo de Programación Lineal sea válido, debe cumplir las propiedades siguientes: Proporcionalidad. Significa que la contribución al valor de la función objetivo y el consumo o requerimiento de los recursos utilizados, son proporcionales al valor de cada variable de decisión. Así el término 2x1 es proporcional, porque contribuye al valor de la función z con 2, 4, 8, etc. para los valores 1, 2, 3, etc., respectivamente, de x1. Se puede observar el aumento constante y proporcional de 2 conforme crece el valor de x1. Aditividad. Significa que se puede valorar la función objetivo z, así como también los recursos utilizados, sumando las contribuciones de cada uno de los términos que intervienen en la función z y en las restricciones. Divisibilidad. Significa que las variables de decisión son continuas y por lo tanto son aceptados valores no enteros para ellas. La hipótesis de divisibilidad más la restricción de no negatividad, significa que las variables de decisión pueden tener cualquier valor que sea positivo o por lo menos igual a cero.
tanto la función objetivo como todas las funciones de restricción. (j =1. i Escrito lo anterior en forma compacta. m)
xj  0. Problema formulado en forma canónica: Max (Min)z = c1 x1 + c2 x2 + … + cn xn st (s. vamos a pasar un problema formulado en forma canónica a otro en forma estándar. tendremos: Restricciones (=): Formulación estándar. donde (x+) 0. …. (i=1. pues debe cumplir que. 2. Significa que los parámetros o constantes son estimados con certeza. Restricciones ( o () o (=): Formulación mixta. ….Programación Lineal
Certidumbre. 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.) a11 x1 + a12 x2 + … + a1n xn  b1 a21 x1 + a22 x2 + … + a2n xn  b2 ……………………………. t. Restricciones () o (): Formulación canónica. sean lineales. 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:
. Dependiendo del tipo de restricción que presente el problema de programación lineal. (x-)0 Por ejemplo. o sea. tenemos Max z = c1 x1 + c2 x2 + … + cn xn=Max st
cj xj
aij xj  bi.(x-). am1 x1 + am2 x2 + … + amn xn  bm xi  0. 2. Sin restricciones de signo: xk =(x+).
... rendimiento.. tiempo. x2. xn+2..) a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 ….…. implica que el recurso de esa actividad se ha consumido en su totalidad (restricción saturada). xn). 4ª Resolución del problema y análisis de la solución o soluciones.   a   mj  Las restricciones las escribiremos: x1 A1+ x2 A2 +…+ xn An  b xi  0.
. Las restricciones que pueden presentarse son del tipo: i) Si no se debe exceder del recurso disponible (). ii) Para no menos de lo requerido (). 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... 2ª Establecimiento de la función objetivo cuyo valor se desea maximizar(utilidad.
2.. ingreso. am1 x1 + am2 x2 + … + amn xn + xn+ m = bm xi  0. mano de obra. i
A las variables xn+1...26  a1 j     a2 j  A j =  .. inventario)... producción) o bien minimizar (costo. i Problema formulado en forma estándar: Max (Min)z = c1 x1 + c2 x2 + … + cn xn st (s. ….. iii) Para igualar el recurso especificado (=)..3. t. 3ª Establecimiento de las restricciones que limitan el valor óptimo que puede tomar la función objetivo. Cuando las variables de holgura son iguales a cero..
para obtener la máxima ganancia ? Desarrollado el problema en fases.4. resulta: 1ª fase: x1 = “ número de unidades de P1 “ x2 = “ número de unidades de P2 “ 2ª fase: Max z = 1 x1 + 1. P1 y P2.2) (2.50
Horas disponibles semanalmente 16 12 28
¿Qué cantidad de cada producto P1 y P2 se debe manufacturar cada semana.
Producto 1 Horas por u. B y C. 2 2 2 1.5 x2 3ª fase : 2 x1 + 2 x2  16 x1 + 2 x2  12 4 x1 + 2 x2  28 x1  0. que pueden fabricar dos productos. Todos los productos tienen que pasar por todas las máquinas. 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.1) (2. A.Programación Lineal
Ejercicio. 2 1 4 1
Producto 2 Horas por u.3)
. Tipo de soluciones en un problema de programación lineal
El problema de programación lineal formulado matricialmente (estándar): Min z = cTX st AX = b X0
(2. Un empresa tiene tres tipos de máquinas.
xn . Si B es una de esas matrices. esto hace que la suposición de que n  m esté justificada.2) al hacer (n-m) variables iguales a 0.  Solución básica: Solución básica: aquella que resulta de (2. siendo n  m.. xn+m) que satisface el conjunto de ecuaciones que constituyen el sistema (2. Generalmente las restricciones aparecen en forma de desigualdad y son convertidas en igualdades al introducir las variables de holgura.3) sus componentes son todas positivas o nulas. 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. Además se supondrá que la matriz A tiene rango m. inversibles) formadas seleccionando m columnas de A. Se resuelve el sistema BX = b.. 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. xj. donde X es el vector formado con las variables básicas y se asignan a estas variables la solución obtenida. definidas ordenadamente como un vector X = ( x1. 3. x2. El hecho de exigir que el rango de la matriz A sea m implica evitar que en el problema aparezcan restricciones redundantes o contradictorias.28
Donde A es una matriz de m filas (restricciones) y n columnas (variables)..2) al hacer (nm) variables iguales a 0. Si B es una de esas matrices... 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.. A las variables no básicas se las da el valor cero. Se dividen las variables de decisión en dos bloques:
Variables básicas: aquella que resulta de (2.. .
2. se dice que es una matriz básica factible si el
. Cada una de las submatrices de A con determinante distinto de cero (es decir. . Cada una de las submatrices de A con determinante distinto de cero (es decir. Las soluciones de un problema de programación lineal se clasifican en:
 Solución factible:
Es un conjunto de n + m variables xj. el proceso de construcción es el siguiente: 1. se llama matriz básica o matriz de base. Variables no básicas: las restantes.2) y (2. .
todas las variables básicas son positivas. no siempre todas esas combinaciones dan lugar a matrices con determinante no nulo. la primera matriz básica que puede construirse es la formada por las dos primeras columnas de A:
. en:
Degeneradas: cuando alguna de las variables básicas tiene un valor nulo. Solución factible básica no degenerada: aquella que es solución factible básica que tiene exactamente m variables xi positivas. Solución factible básica: aquella que es solución básica y cumple (2. esto es.3). No factibles: alguna componente tiene un valor negativo. A continuación se presenta un ejemplo de localización de soluciones básicas de un programa lineal. No degeneradas: cuando todas las variables básicas son estrictamente positivas. es decir. x2. debe formularse el programa en su forma estándar y obtener las correspondientes matrices:
2 1 2 4 0 -1 1 0 0 1
Las matrices básicas serán en este caso todas las submatrices inversibles formadas al seleccionar 2 columnas de A. Por supuesto.
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. degeneradas o no degeneradas.Programación Lineal
vector resultante de multiplicar su inversa por el vector b tiene todas sus componentes mayores o iguales que cero. x3  0 y clasificarlas en factibles o no factibles. Por ejemplo. Éste es el número de posibles combinaciones para elegir m columnas entre las n columnas existentes. a su vez. todas las variables son no negativas. En primer lugar. 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.
x3 y x4 1 1 2 0 x2 y x3 x1.0.0.0) (0. las no básicas. x3 y x5 1 0 2 0 x1 y x5 x2.0.-18.0.0.0. x4 y x5 1 -1 2 1 x1 y x4 x2.0.0) (12.6. De igual manera se construyen el resto de soluciones básicas. x2 y x5 -1 0 Solución básica Tipo
(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.0) (0.0.-12.0. se las da el valor cero y la solución básica que se obtiene es X=(0.0) (3. En la siguiente tabla se presentan todas las soluciones básicas obtenidas. A las restantes variables.30
Investigación Operativa 2 2 1 4
En este caso.0) (0. en este caso todas las submatrices 2x2 son básicas excepto la que forman las columnas tercera y quinta.0.3.9) (0.12)
Factible degenerada No factible No factible Factible no degenerada Factible degenerada Factible degenerada Factible degenerada No factible Factible no degenerada
x4 y x5
Variables Variables no Matriz básicas básicas básica 2 2 x1 y x2 x3. x3 y x4 4 1 0 1 x3 y x4 x1.0). x4 y x5 1 4 2 0 x1 y x3 x2.0. x4 y x5 4 -1 2 1 x2 y x4 x1.0. mediante un ejemplo el concepto de punto básico degenerado (menos de m componentes positivas) y no degenerado:
.0.3.3.3.0.6.0.0.0. x2 y x3
Veamos.0) (3.0) (0. x3 y x5 4 0 2 0 x2 y x5 x1.0.3. 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.-9.
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.1. Los valores de la función objetivo en cada uno de los vértices son: f(O) = f(0. f(E) = f(0.60) = 260. f(D) = f(20. 1/4 .60).1) es básico no degenerado El punto (1/2.
.0) es básico degenerado El punto (0.Programación Lineal
Max z = x1-2x2+5x3 .0) = 240.0.0.1/4 . 4) El punto (1.80) = 240 La solución es única.y) = 4x + 3y st 30x + 20y  1800 x + y  80 x0. En este caso es el vértice D(20.x4 st x1+x2+x3 =1 x1-x2-x3 +2x4 =1 xi  0 (i=1.0) = 0. y corresponde al vértice para el que la función objetivo toma el valor máximo.0. f(C)=f(60.y0 Tiene por región factible la región sombreada. 2. 3.
0) = 4 f(B)=f(5/3. x + y 2 . x . En este caso no existe un valor extremo para la función objetivo. y 0 No existe la región factible.
2. y  0 Los valores de la función objetivo en cada uno de los vértices son: f(O)=f(0. como ya vimos en el capítulo anterior. el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible.y)= 4x + 2y st 2x + y  4 .2/3) = 8.y) = 3x + 8y st x + y 6 . x 0 . iii) Solución no acotada (No existe límite para la función objetivo) Maximizar la función z = f(x. que corresponden a los puntos del segmento situado entre dos vértices de la región factible.0) = 0.y) = x + y st y  2x . que es una región no acotada. iv) Cuando no existe el conjunto de soluciones que cumplen las restricciones Maximizar la función z = f(x. y  x/2 Tiene por región factible la zona coloreada que aparece en la figura. Hay infinitas soluciones.y  1 .4) = 8 La función objetivo alcanza el valor máximo en los vértices B y C. f(C) = f(0. f(A) = f(1. En estos casos.5. La función crece indefinidamente para valores crecientes de x e y. ya que las zonas coloreadas que aparecen en la figura son únicamente soluciones de alguna de las inecuaciones . la función objetivo es paralela a una de las restricciones. por tanto. solución múltiple.Por tanto. la región factible debe estar no acotada. Resolución de un problema de programación lineal mediante el método gráfico
. Este tipo de problemas carece de solución. x  0 .32 ii) Solución múltiple
Maximizar la función z = f(x. Para que suceda esta situación. por lo que puede decirse que el problema carece de solución. en todos los puntos del segmento BC.
pero nos puede dar una aproximación a lo que queremos resolver. El procedimiento a seguir es: 1. dan la solución al problema. para obtener la pendiente de la función objetivo. Escoja cualquier punto de ensayo que no pertenezca a la recta. Localice la región de soluciones factibles (Región Factible). 4. en caso contrario será un punto no factible. las sillas utilizan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla.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. por ejemplo pasando por el origen. El fabricante prometió construir por lo menos dos mesas. El margen de beneficio es el mismo para las mesas que para las sillas: 5 euros por unidad. Convierta las desigualdades en igualdades y represente la rectas que representan estas ecuaciones. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. 7. 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. 6. Dibuje una recta arbitraria de la función objetivo. entonces todos los puntos que estén del mismo lado que el punto de ensayo satisfacen la desigualdad. Los valores de las variables de decisión. 2. Ejercicio 3. Se cuenta con 96 unidades de material y con 72 horas de mano de obra. Por otra parte. Evalúe el primer miembro de la expresión. Solución: El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL. 10. Determine si el punto de ensayo satisface la desigualdad. Dibuje la gráfica de cada restricción sobre el mismo cuadrante no negativo. 5. Es evidente que su precisión no es la deseada. 11. Determine la dirección ascendente o descendente de esta recta. 8. Resolver gráficamente el problema siguiente: Un fabricante está tratando de decidir las cantidades de producción para dos artículos: mesas y sillas. Si el punto de ensayo satisface la desigualdad original. Dada la pendiente de la función objetivo y teniendo en cuenta si es un problema de maximizar o minimizar. Sustituya el punto de ensayo en el primer miembro de la desigualdad y obtenga el valor numérico. en este vértice. 3. Función objetivo:
. 9. determine el vértice del conjunto factible que esté sobre la recta que representa la función objetivo.
Ahora se utilizará la función objetivo para seleccionar la solución óptima. se tiene: Maximizar z = 5x1 + 5x2 st 12x1 + 8x2  96 6x1 + 12x2  72 x1  2 x1  0.
. 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. x2  0
(restricción de material) (restricción de mano de obra) (restricción de promesa del fabricante) (restricciones de no negatividad)
Poniendo todo junto el modelo.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.
la única tarea que queda es encontrar las coordenadas del punto. Esto se muestra en la siguiente figura:
Con el punto óptimo localizado gráficamente. Las coordenadas de este punto se pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones. 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. 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. Las coordenadas de este punto
. 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.
K es una región de Rn determinada por la intersección del conjunto finito de restricciones lineales (2. es decir. Si K es un poliedro convexo. En este caso. 3). El conjunto de soluciones factibles de un problema de programación lineal es un conjunto convexo. por lo que K es: i) K = . La sustitución de este punto en la función objetivo da la ganancia máxima: z = 5(6) + 5(3) = 45 euros. pero si lo hace. cuando K tenga un número finito de vértices que no se puedan alcanzar todos (región convexa ilimitada). el valor óptimo de la función objetivo se alcanza en uno de los vértices del polígono que limita la región. entonces K es la envolvente convexa de los puntos extremos de K. Si se da el caso de que los valores correspondientes a dos vértices coinciden. no tiene solución el problema de programación lineal. Existe solución de valor finito de la función objetivo. las líneas de nivel tienen la misma pendiente que la recta que contiene a ese lado del polígono. ii) K  . la función objetivo no alcanza necesariamente un valor óptimo concreto. o a lo largo de uno de los lados. 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. El problema tiene solución.1. y en aquel en el que el valor de la función sea mayor (o menor) habremos alcanzado el punto óptimo buscado. 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. 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). Proposición 2. que es precisamente el valor óptimo. son paralelas.3). alguna de las cuales vamos ver. si la región factible existe y es acotada.36
resultan ser (6. pero el máximo podría ser ilimitado. éste se encuentra en uno de los vértices de la región. de modo que a lo largo de ese lado del polígono se alcanza el mismo valor de la función objetivo.
En un problema de Programación Lineal con dos variables.6. éstos serán adyacentes. Si la región factible no es acotada. Designemos por K el conjunto de las soluciones factibles de un problema de programación lineal.
2. iii) K  . Demostración
Si formamos un vector X que sea combinación lineal de éstos dos: X =  X1 + (1-) X2. si este mínimo se alcanza en varios puntos.
i = 1
Sustituyendo: Min z = m= cT X0 = cT ( 1 X1 + 2 X2 +…+p Xp)
. X2  0. A X2 = b. Proposición 2. Si K es un poliedro convexo. entonces X0 se podrá poner como una combinación lineal convexa de ellos: X0 =
i Xi . además. ii) Si X0 no es un vértice de K. Demostración Sean X1. esto significa que cT X0  cT X para cada XK. X1 0.
X4 X3 X5
K X2 X6
Se pueden dar los casos siguientes: i) Si X0 es un vértice de K.1) alcanza su mínimo en un vértice de K.…. ya estaría demostrado. también se alcanza en cualquier combinación lineal convexa de los mismos. i  0 . AX =  AX1 + (1-) A X2=  b + (1-) b =b por lo que X es también una solución factible. entonces A X1= b. Xp los vértices de K y sea X0 una solución factible mínima. entonces la función objetivo z dada por (2.2. X2.Programación Lineal
Sean X1 y X2 soluciones factibles.
….…. Proposición 2.…. 1]. [0. X1. el punto X = (x1. entonces. por ser soluciones factibles.…. A2. X2. por lo que podemos escribir: x11 A1+ x12 A2 +…+ x1k Ak = b x21 A1+ x22 A2 +…+ x2k Ak = b
. 0)T con X1  X2.
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. 0)T X2 = (x21. se cumple que AX1=b y AX2=b. 0.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. Demostración Supongamos que X no fuera vértice. 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. que sean linealmente independientes y de forma que: x1 A1+ x2 A2 +…+ xk Ak = b con las xi  0.…. x2. 0)T es un vértice del conjunto convexo K de soluciones factibles. 0.…. x22. x1k. Además. i  0 . Si tenemos un conjunto de k vectores A1. x2k.….…. es decir. x12. Ak.3. Para probar la segunda parte de la propiedad supongamos que z alcanza su valor mínimo en X1. xk. 0. Xq y que X es una combinación lineal convexa de ellos: X=
i Xi . entonces podría expresarse como combinación lineal convexa de dos puntos distintos de K: X =  X1 + (1-) X2. que existe un vértice de K en el que la función objetivo z= cT X alcanza su valor mínimo.
x22) A2 +…+ (x1k . lo que contradice el hecho de haber supuesto X1  X2. por lo que necesariamente X debe ser un vértice de K. para simplificar. Ak son linealmente dependientes. Ak linealmente independiente llegamos a la conclusión de que: x11 = x21 x12 = x22 … x1k = x2k es decir. entonces los vectores Ai asociados con las coordenadas xi positivas forman un sistema linealmente independiente.….x2k) Ak = 0 y por ser los vectores A1. que las k primeras coordenadas son las no nulas.…. Proposición 2. entonces : x1 A1+ x2 A2 +…+ xk Ak = b Si los vectores A1. que X1 = X2. Demostración: Supongamos. xn)T es un vértice de K. A2. 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:
xi Ai = b
  i Ai = 0
i1 k
donde  > 0. Si los sumamos y restamos:
. de lo que se sigue que.x21) A1+ (x12 . m de estas coordenadas xi son positivas. A2.Programación Lineal
Restando las expresiones anteriores obtenemos: (x11 . a lo sumo.…. x2.4. Si tenemos un vector X = (x1.
como máximo. . lo cual contradice el hecho de que X sea vértice. Proposición 2.…. 0. 1. . xk . no puede hacerse la hipótesis de que los vectores A1.… 0)T X2 = (x1 . 2 ) A2 +…+ (xk . A cada punto extremo del poliedro convexo se encuentra asociado un conjunto de m vectores linealmente independientes del conjunto dado A1 . An . k ) Ak = b De manera que tenemos dos soluciones distintas del sistema de ecuaciones: X1 = (x1 +  1. 0. Demostración La Proposición 2. . m de las xi serán positivas. Ar .40
i1 i1 k
xi Ai +   i Ai = b xi Ai . .4. x2 +  2. k. Esto contradice la suposición de que tenemos siempre un conjunto de m vectores linealmente independientes A1 . 1 ) A1 + (x2 .…. prueba que existen k  m vectores linealmente independientes. Am asociados con cada punto extremo. 0. Ak sean linealmente dependientes. De ahí que. Ak . Ar . Ak 1 . resulta: X1 + X2 = ( 2x1. A2. 2.5. 2x2.…. Ar vectores adicionales tales que el conjunto A1 .5 queda comprobada.… 0)T= 2X Despejando X= ½ (X1 + X2). como estos vectores son m-dimensionales no podremos tener más de m linealmente independientes.  i Ai = b
Es decir. A2 . .…. xk +  k. por tanto son linealmente independientes y. Supongamos que k  m y que podemos encontrar solamente Ak 1 . de ahí que.
. Los n-r vectores restantes dependen de A1 . Para k =m la propiedad 2. desarrollando las expresiones anteriores: (x1 +  1 ) A1 + (x2 +  2 ) A2 +…+ (xk +  k ) Ak = b (x1 . para r m es linealmente independiente. . A2 .… 0)T Sumando X1 y X2. x2 . 2xk .
1. xn)T. Sea el problema de programación lineal: Min z = cTX st AX = b X0 Supongamos que tenemos una solución factible básica.…. Podemos hacer que este conjunto de m vectores linealmente independientes sean los primeros m. A cada vértice de K se puede asociar una base de dimensión m del conjunto de vectores A1. (Caracterización de los vértices de K) El vector X = (x1. x2. m=   .….   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. es decir.. A2.. . 0)T que verifica:
. las diversas circunstancias de su preparación antes de aplicar el algoritmo y los casos especiales identificables en la tabla solución (última tabla). An. xm. 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. se conoce una solución de punto extremo en términos de m vectores A j del conjunto original de n vectores.. si x1 A1+ x2 A2 +…+ xn An = b y las xi > 0 son coeficientes de los vectores Ai linealmente independientes. 0. El máximo número de vértices que puede tener el convexo K es Cn. 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). de coordenadas no negativas. x2.…. es un vértice de K (conjunto convexo de soluciones factibles). Max z = Min (-z) Cada solución factible básica corresponde a un vértice de K.7.Programación Lineal
Teorema 2. es decir. que las variables no nulas sean las n-m finales X = (x1. Demostración La demostración es inmediata aplicando las proposiciones 3 y 4.
n m
2. Resumiendo lo anteriormente expuesto mediante propiedades y teoremas tenemos: Si existe solución al problema de programación lineal.
. podemos expresar cada uno de los n vectores dados como combinación lineal de los vectores de esa base:
Ai  A j ...2) multiplicada por un escalar j.1) que... .. en los demás casos (2. toma el valor z’ = c1 x1’ + c2 x2’+ … + cm x’m + j cj = = c1 (x1 . x j  0.…. A2... x’2. Rm.5)
La función objetivo en X’ = (x’1. x’2..6) donde z es el valor de la función objetivo en X. x’n)T es una solución factible.j  2 j ) + … + cm (xm ... n
y si escribimos todas las ecuaciones:
11 A1   21 A2     m1 Am  A1  A   A     A  A  12 1 22 2 m2 m 2  ... si elegimos j  0.j  1 j )A1 + (x2 .. resulta: (x1 .... si A1..…...... Tomemos un j de modo que Aj no esté en la base dada.42
x1 A1  x2 A2    xm Am  b. de modo que xi ..j  i j 0..... 2. i=1.. …....j  2 j )A2 + … + (xm .3)
Observando en (2. m x’i = j  0......j  1 j ) + c2 (x2 . m tendremos que el vector X’ = (x’1. 2... . x’n)T..j  i j 0 para i=1.1) le restamos (2. Am es la base canónica de los vectores unitarios entonces x1=b1. 2.1)
Como los vectores Am forman una base en el espacio m-dimensional.... x2=b2. . j  1...  j
Investigación Operativa (2. solución factible...... y zj viene dada por la expresión:
. i=j x’i = 0. pues bien si a (2..….j (zj -cj) (2. 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..j  m j ) + j cj= = z ..4)
con lo cual. donde: x’i = xi .j  m j )Am + j Aj = b (2...2)
(2. xm=bm.
x2’. para i=1. con lo cual z’<z. x’2.
x    j = min  i /  ij  0 (2.5) se tenga que j(zj-cj) sea positivo y máximo. por ejemplo.….j (zj -cj). esto quiere decir que existirá i tal que 2 A2 +  3j A3+ … +  m Am+  m+1 Am+1 = 0 (2. x’n)T = (0. Por tanto.7)
así pues.m1  ij 
(2.6) vemos que debemos seleccionar j y j de forma que verificándose (2. es decir:
x  x1   m+1 = min  i /  ij  0 = i   1. j 
 ij
.j  i j 0. obtenemos:
. 0.…. Am son linealmente independientes.8) i    ij 
y esto para cada j para el que se cumpla (zj -cj) > 0. ello significará que seleccionamos el vector Am+1. ….  i j > 0 x’i = xi . en (2. supongamos que éste es j=m+1. A3. A3. despejando Am+1 de (2.…. A3. puesto que los vectores A2. por tanto. por lo que la
nueva solución factible X’ = (x’1.10). z’= z.5). m+1 = 0. m+1.…. m+1 = x1 -
1. Am+1 son linealmente independientes. a continuación calcularemos los productos j (zj -cj) y nos quedaremos con el índice j que da el producto mayor. Am+1 son linealmente independientes (Vea el teorema de caracterización de los vértices de K). en calcular las cantidades (zj -cj) > 0 observando las relaciones (2. El procedimiento consiste.10) para algún i distinto de cero y. ….Programación Lineal zj = c1  1 j + c2  2 j + … + cm  m j (2. si el mínimo en (2. mejoran el valor de la función objetivo. xm’. Estudiaremos dos casos: i) ii) ij > 0 ij  0
Caso i): j  0. por otra parte. Para probar que los vectores A2.9)
ello significará que x 1’ = x1 . 0)T será un vértice de K (conjunto de soluciones factibles) si los vectores A2.m+1  1.m1
 1. supongamos que fueran linealmente dependientes. éstas corresponden a las variables cuyos vectores asociados. si los incluimos en la base.8) se alcanza. deberá ser m+10.
En consecuencia. . es decir.…. m+1 . no existe solución. m)Am
por lo que.44 Am+1 = i  m1
  2 A2 . 2) A2 +…+ ( m. Am linealmente independientes obliga a que 1. encontramos que Am+1 = 1. ocurrirá que z’ tiende a menos infinito. al ser A1. m+1 .. .j (zj . únicamente resulta sencillo en problemas con pocas variables de decisión. m+1 A2 +…+  m.…. A2.3 A3 -…. . A2. m) (2. A2. Am+1 son linealmente independientes.11)
haciendo  i=-
Am+1 =  2 A2 +  3 A3 +…+  m Am Restando (2. en cuyo caso ya no se podría disminuir la función objetivo y. 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). 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..11) de (2. Por supuesto encontrar todas las soluciones básicas de un programa lineal requiere de grandes esfuerzos de cálculo.
.j  i j z’ = z.m+1=0 y.. 2.cj ) >0 Como se puede elegir un j tan grande como quiera.. m+1 A1 + ( 2. con j=m+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. con (zj . 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.cj ) . Caso ii): j  0. sin embargo se supuso positivo (vea (2. m+1 A1 +  2. por tanto.2).m Am m1 m1 m1
(i=2.  i j  0 x’i = xi .. n. se habría alcanzado el mínimo con el vector X que se tuviera en esa etapa.9)). m+1 Am 0 = 1.
en las tablas del simplex aparecen gran número de ceros.Programación Lineal
Dentro de los aspectos computacionales. o que sumar cero a un número no altera el resultado. Por ejemplo. 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. un computador no reconoce esas situaciones y pierde tiempo realizando operaciones que realmente no son necesarias. para un humano no supone ningún problema reconocer los ceros y darse cuenta que al multiplicar un número por cero resulta cero. ya que se almacenan y calculan muchos números que no son estrictamente necesarios.
. Sin embargo. En tales situaciones debe recurrirse al uso de los computadores electrónicos. el método Simplex no resulta muy económico desde un punto de vista computacional. Sin embargo.
…. y2.cj )  0... Hemos de probar que para cualquier otra solución (zj .12)
Como (zj . el último vértice obtenido es la solución óptima. Si en algún paso (puede ser el primero) del método simplex se
verifica que (zj . j (j=1..14)
Puesto que Y es una solución factible
(2. .. x2.cj )  0. yn)T. Demostración Sea X = (x1.…. 2.. 2.13)
Sustituyendo en (2. xn)T un punto extremo en el cual la función objetivo vale z0 y para el que se verifica que (zj .cj )  0..... 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
i1 i1 i1 m m m
ci ij
Agrupando términos en c i (i=1. n).46
Investigación Operativa Teorema 2.2. n).. 2. n) Y= (y1. j (j=1.13) cada zj (j=1..cj )  0  zj  cj y sustituyendo en la expresión (2.12) cada cj por zj tenemos: z1 y1 + z2 y2+ … + zn yn  z (2.. . .. entonces. 2. m) se tiene: c 1 (   1 j y j) + c 2 (   2 j yj) + … +cm (  
j1 j1 j1 n n n
yj)  z
(2. con yi  0
y valor de la función objetivo: z = c1 y1 + c2 y2+ … + cn yn se verifica z0  z. j (j=1.. .. 2..
Resuelva mediante el Método Simplex el problema de programación lineal siguiente: Min z = –5x1+2x2-3x3 st 2x1+2x2-x34
. 2. A2. n) por su valor: (2. …. .15) para cada uno de los j: y 1 (   i 1 Ai) + y 2 (   i 2 Ai) + … + y n (   i n Ai) = b
Ahora agrupamos términos en A i: (   1 j yj )A 1 + (   2 j yj)A2+ … + (   m j yj) Am = b
Como X es un punto extremo x 1 A1+ x 2 A2+ … + x m Am = b y por ser los vectores A1.. 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. b se escribe de forma única.14) se tiene: c1 x1 + c2 x2+ … + cm xm  z es decir z0  z .. por lo cual: x1 =   1 j yj . Ejercicio 1.15)
Aj =  1 j A1+  2 j A2+ … +  m jAm =   i j A i
Sustituyendo este valor en (2. x2 =   2 j yj .. .
cj) nos
proporciona el vector j-ésimo que entra en la base. el valor de j que hace max j (zj . de manera que tengamos una base canónica para comenzar el método del simplex: Min z = .3+0. 2.48 3x1. zj.2+0. tenemos.   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. 2. z1 . para j=1.c1 =0 .2=0. ii) Calculamos (zj -cj). 3)
Pasando el problema a forma estándar añadiendo variables artificiales. 3. i    ij  ij  iv) Buscando que j (zj -cj) sea positivo y máximo.x2+x33 2x1+x2+3x35 xi  0 (i=1. 4. 0. z1 = 0.x2+x3+x5 = 3 2x1+x2+3x +x6= 5 xi  0 (i=1. 0.
x  b   iii) Para los valores (zj -cj) >0 calculamos j = min  i  i /  ij  0 .5x1+2x2-3x3+0x4+0x5+0x6 st 2x1+2x2-x3+x4 = 4 3x1. 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
Base A4 A5 A6
cB 0 0 0 z.(-5)=5
. 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. Por ejemplo.j
El vértice inicial de partida es X=(0. 5)T.
Este proceso se repite de forma iterativa hasta que se verifique (zj . deberá valer uno y el resto cero.Programación Lineal
Realizadas las operaciones correspondientes. j (j=1. .El vector que sale de la base es el A5 (1 = min  2  2   =1)...5=5). Veamos como se obtiene   : 1   0  
A5 A1=A5/3 A4 2·A1 A4-2·A1 A6 2·A1 A6-2·A1
A1 3 1
3 1 4 2 2 5 2 3
-1 -1/3 2 -2/3 8/3 1 -2/3 5/3
1 1/3 -1 2/3 -5/3 3 2/3 7/3
0 0 1 0 1 0 0 0
1 1/3 0 2/3 -2/3 0 2/3 -2/3
Llevando lo anterior a la tabla. El vector A1 que entra en la base se convierte en un elemento de la base canónica.El vector que entra en la base es el A1 ( max 1 (z1 –c1)=1. n).
x b 3 . 2. i2  21  21 3 
El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote. 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
Base A4 A1 A6
. 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). en nuestro caso el 3. tenemos: ..cj )  0. que se genera en el cruce del vector que entra y el vector que sale.
n). x3=9/7=1. A5 y A6 de la tabla:
1  8 / 7 5 / 7     {A4. La solución mediante la matriz inversa asociada a la tabla del simplex. z = -6. 0.50
Segunda tabla cj -5 Base cB b A1 0 2 0 A4 -5 1 A1 1 0 3 0 A6 -5 -5 z. en este caso a los vectores A4. 9/7. 0)T. j (j=1. Tercera tabla cj Base A4 A1 A3
cB b 0 29/7=4.7142 El vértice final obtenido es X=(4/7.2857 z. 29/7.. por lo que hemos llegado a la etapa final. 0.5714. . zj.7142 zj-cj j(zj-cj)
2 A2 8/3 -1/3 5/3 5/3 -1/3 -
-3 A3 -5/3 1/3 7/3 -5/3 4/3 12/7
0 A4 1 0 0 0 0 -
0 A5 -2/3 1/3 -2/3 -5/3 -5/3 -
0 A6 0 0 1 0 0 -
3 3 9/7 9/7
-5 A1 0 1 0 -5 0
2 A2 22/7 -4/7 5/7 5/7 -9/7 -
-3 A3 0 0 1 -3 0 -
0 A5 -8/7 3/7 -2/7 -9/7 -9/7 -
0 A6 5/7 -1/7 3/7 -4/7 -4/7 -
Observando la tabla tenemos (zj .cj )  0.5714 -3 9/7=1.. x2=0 (no aparece). 2.1448 -5 4/7=0. j zj-cj 0 j(zj-cj) Entra A3 y sale A6. Para buscar la solución dentro de la tabla miramos la columna b y encontramos: x1=4/7=0. j -47/7=-6. A6}=  0 3 / 7  1 / 7  0  2 / 7 3 / 7  
. A5. B-1 la podemos encontrar directamente en la última tabla del simplex observando los vectores correspondientes a los de la base inicial.. zj.2857.
714286 VALUE 0.000000
ROW 2) 3) 4)
SLACK OR SURPLUS 4.000
SLK 2(A4) SLK 3(A5) 0. A1.571 0.000000 1. A1 y A3:
1 2  1   B  {A4.286 3.Programación Lineal
1  8 / 7 5 / 7  4   29 / 7       B b  X o   0 3 / 7  1 / 7  3    4 / 7   0  2 / 7 3 / 7  5   9 / 7      
y la matriz B se obtiene de la primera tabla mirando la base que figura en la última tabla del simplex.714 -0.000 0.000 0.000000 0.571429 0.000 -1.143 0.285714 0.143
X2(A2) 1. A4.000000 1.000 1.286 1.286
ROW 1 2 3
SLK 4(A6) 0.571429
ROW (BASIS) 1 ART 2 SLK 2(A4) 3 X1(A1) 4 X3(A3)
X1(A1) 0.000 0. A3}=  0 3 1  0 2 3   
Si resolvemos el ejercicio anterior con el programa LINDO.000 -0.429 0.x2+x3 <= 3 2x1+x2+3x3 <=5 LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 -6.000 0.142857 0.714 4.143 0.571
.000 1.285714 REDUCED COST 0. tenemos:
Min -5x1+2x2-3x3 st 2x1+2x2-x3 <= 4 3x1.571 0.285714 0.857 -0.714
X3(A3) 0.000000 1.000000
DUAL PRICES 0.000 1.000 0.
b. A5. A1. c3. A6}=  0 3 / 7  1 / 7  0  2 / 7 3 / 7  
B 1
1 2  1   B  {A4. Considere el problema siguiente:
Max z= 5x1+2x2+3x3 st x1+5x2+2x3b1 x1-5x2-6x3 b2 xi  0 (i=1.
Solución: Tabla 1
Base A4 A5
cB 0 0 z. 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
Base A1 A5
cB -5 0 zj-cj
Calcule: a) Los recursos.286
Operando de la misma forma para obtener las matrices:
1  8 / 7 5 / 7     {A4. zj-cj
cj b b1 b2 0
-5 A1 1 1 5
-2 A2 5 -5 2
-3 A3 2 -6 3
0 A4 1 0 0
0 A5 0 1 0
4 0. e. A3}=  0 3 1  0 2 3   
Ejercicio 2. d. 3) Para ciertos valores de los recursos. 2. b) Los valores de: a.429 1. c.
b) a= -23. Es oportuno resaltar la diferencia entre variables de holgura y variables artificiales. En la mayoría de los casos la situación anterior no se producirá. para iniciar el método simplex. Veamos como siempre es posible conseguir esto. Si al introducir las variables de holgura necesarias para escribir el problema en forma estándar ya tenemos la base canónica.Programación Lineal
Tabla 2 Por la información que nos proporciona la tabla del enunciado. b = 5. Las primeras se introducen para convertir desigualdades en igualdades. b2= 40.
. La base canónica inicial la configuraremos con las variables de holgura más las variables artificiales necesarias hasta tener esa base canónica. c3= -3
2.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. sale de la base A4 y entra A1
cj b b1 b2. Éstas construyen un problema artificial más conveniente desde el punto de vista del método simplex. necesitaremos de lo que se conoce como variables artificiales. c= -10. a continuación. 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. zj-cj
Identificando. podremos aplicar directamente el método del simplex. tenemos: a) b1= 30.8.b1=10. un método que nos ayude a resolver los problemas que contengan variables artificiales. mientras que las variables artificiales se introducen para facilitar el comienzo del método simplex. d= -5. e= 0. b2. Para conseguir partir de una base canónica. por lo que tendremos que recurrir a métodos que nos conduzcan a él.
Xa  0 En la resolución del problema por este método. 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.54
2. Xa  0 Tenemos como solución inicial: Xa =b.1.
. y que entren las otras variables. Min z = cTX + M 1T Xa st AX + I Xa =b X  0. es decir. Para ello les asociamos un valor muy grande M ( no es necesario especificar el valor de M) en la función objetivo. con lo cual tenemos el sistema siguiente: AX + I Xa = b X  0.8. hasta que todas quedan fuera de la solución. entonces la solución obtenida es única y óptima. las Xa. Las iteraciones del método simplex automáticamente fuerzan a las variables artificiales a desaparecer (a volverse cero) una a una. pueden presentarse los casos siguientes: a) Tengamos solución finita: i) Que el problema admita una solución óptima. con todas las variables artificiales iguales a cero. 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. X=0 Debemos buscar la forma de hacer salir las variables artificiales.
debemos construir un problema “artificial” que tiene. no tenemos solución. entonces el problema original es imposible. la misma solución óptima que el problema real... en este caso tenemos una solución no finita. Xa= 0. 3) Como explicamos anteriormente.j 75M zj-cj j(zj-cj)
-1 -6 A1 A2 1 2 2 1 2 1 3M 3M 3M+1 3M+6
30M+60
4 A3 -1 1 4 3M 3M-4
0 A4 0 1 0 0 0
0 A5 0 0 -1 -M -M
M A6 1 0 0 M 0
M A7 0 0 1 M 0
 10 40 55
. en caso de que exista.. 2. b) Tengamos solución no finita: iii) Con todas las variables artificiales iguales a cero. 2. iv) Exista al menos una variable artificial que sea positiva.Programación Lineal
ii) Que el problema admita una solución óptima en la cual encontraremos al menos una variable artificial distinta de cero. Xa 0. 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.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. para resolver este problema. zj. entonces el problema original es imposible. Min z = . . 7)
Primera tabla Se llevan a la tabla los datos del problema “artificial” y se comienza a operar de acuerdo con el algoritmo del simplex:
cj Base A6 A4 A7
cB b M 20 0 40 M 55 z.
que.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
Base A2 A4 A7
Entra A3 y sale A7... ya nunca más volverá a entrar. 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. n).cj )  0. zj.56
A los valores que hayan resultado ser (zj -cj) >0. deberá valer uno y el resto cero. que.
Tercera tabla
cj Base A2 A4 A3
cB b -6 15 0 15 4 10 z. 2.. por corresponder a una variable artificial. 2. por lo que hemos llegado a la etapa final. ya nunca más volverá a entrar. j (j=1. en nuestro caso se da para varios j.
Segunda tabla
-1 cB b A1 -6 10 1/2 0 30 3/2 M 45 3/2 z. n). ..cj )  0. que se genera en el cruce del vector que entra y el vector que sale. .j -50 zj-cj
-1 A1 2/3 1 1/3 -8/3 -5/3
-6 A2 1 0 0 -6 0
4 A3 0 0 1 0 0
0 A5 -1/9 1/3 -2/9 -2/9 -2/9
M A6 -
M A7 -
Observando la tabla tenemos (zj . Este proceso se repite de forma iterativa hasta que se verifique (zj . zj. por corresponder a una variable artificial. j (j=1. Para buscar la solución dentro de la tabla miramos la columna b y encontramos:
. en nuestro caso el 2. El vector entrante en la base formará parte de la base canónica de manera que el elemento pivote. tenemos que entra A2 y sale A6...
resolveremos el problema original planteado utilizando la última matriz obtenida en la Fase I y por tanto dicha base. necesarias para tener en la primera tabla del simplex una base canónica. el mínimo del problema anterior se alcanzará cuando las variables artificiales Xa =0 y z=0. con lo cual tenemos el sistema siguiente: AX + I Xa =b X  0. x5= 0. Xa  0 Su resolución se abordará en dos fases:
Fase I: Esta primera fase consiste en resolver previamente el problema siguiente:
Min z = 1TX a st AX + I Xa =b X  0. x2 =15. la solución del problema original planteado (maximización) es: x1= 0. x3= 10. z = -50 Luego.
Fase II: En esta segunda fase. x4 =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.Programación Lineal
x1= 0. Xa  0 Si el problema original tienen solución factible. x3= 10.8.
. Xa. z = 50
2x2 st x1 +x2  2 -x1 +x2  1 x2  3 x1 0 . tenemos: Primera tabla
cj Base cB b A4 1 2 A6 1 1 A7 0 3 z zj j 3 zj-cj
0 A1 1 -1 0 0 0
0 A2 1 1 1 2 2
0 A3 -1 0 0 -1 -1
1 A4 1 0 0 1 0
0 A5 0 -1 0 -1 -1
1 A6 0 1 0 1 0
0 A7 0 0 1 0 0
 2 1 3 1
cj b 1 1 2 1 j zj-cj j(zj-cj)
Base A4 A2 A7
cB 1 0 0 z zj
0 A1 2 -1 1 2 2 1
0 A2 0 1 0 0 0 -
0 A3 -1 0 0 -1 -1 -
1 A4 1 0 0 1 0 -
0 A5 1 -1 1 1 1 1
1 A6 -2
0 A7 A A5 0 1 /2 1 0 1 2 2 0 1/2 1 0
Solución de la tabla.h1+ a1 =2 . z=1. al ser la función objetivo de minimizar y tener zj-cj positivos la solución no es óptima. h3=2. 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. Para los zj-cj >0
. El problema con las variables de exceso . x2=1. a1=1.58 Min z = x1.x1+x2 -h2+ a2 =1 x2+ h3 =3 pasamos a la tabla los datos y operamos según el algoritmo del simplex. x2  0
Vamos a resolverlo por el método de las dos fases.
tomamos x1 por tener mayor zj-cj . 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. z=-4.1 0 1 3 3 0 3 1 0 -
Cuarta tabla
cj b 1 2 1 -4 j zj-cj
Base A5 A2 A7
cB 0 -2 0 z zj
1 A1 2 1 -1 -2 -1
-2 A2 0 1 0 -2 0
0 A3 -1 -1 1 2 2
0 A5 1 0 0 0 0
0 A7  A3 0 0 1 1 0 0
Solución de la tabla. x2=2 h3=1. 0. con lo cual terminamos la primera fase al obtener en la próxima tabla z=0 con a1=0.
. la cual no volverá a entrar en la base y por lo tanto se puede eliminar de la tabla. h2=1. 3. la solución no es óptima. h1 será la nueva variable básica. 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. 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. Para los zj-cj >0 calculamos j. z=-6. y el valor máximo de j(zj-cj ) se alcanza en x1 y en h2. Introducimos entonces la función objetivo original min z=x1-2x2 y continuamos con el algoritmo del simplex:
cj b 1 /2 3/2 3/2 j -5/2 zj-cj j(zj-cj)
Base A1 A2 A7
cB 1 -2 0 z zj
1 A1 1 0 0 1 0 -
-2 A2 0 1 0 -2 0 -
0 A3 -1/2 -1/2 1/2 1/2 1/2 3/2
0 A5 1 /2 -1/2 1/2 3/2 3/2 3/2
0 A7 A3 A5 0 . 0.
. se puede detectar si existen otras y. por lo cual el problema tiene infinitas soluciones. 6) Los puntos extremos son: X1=(2. Supongamos que ya hemos encontrado una solución óptima (mínima) de un problema y que se verifica (zj . se encuentra observando si tengo algún vector j. 0.60
2.cj)= 0.9. j. 0.. 0)T. El método simplex se detiene automáticamente al encontrar una solución factible básica óptima. que el problema siguiente presenta dos puntos extremos. mediante el método simplex. pero que cumple (zj . Compruebe. Una vez que el método simplex encuentra una solución factible básica óptima. también sería solución óptima. Tomando una combinación lineal convexa de ellas. Repitiendo este proceso para cada una de las “j” que no pertenecen a la base y verifican (zj . Soluciones degeneradas
Al desarrollar el algoritmo del simplex supusimos que las soluciones eran siempre no degeneradas.cj)= 0. 0)T así como toda combinación convexa de dichos puntos.cj )  0.j (zj . 0.10.x3  1 x2+ 2x4  8 xi  0 (i=1. 4. si es así. La función objetivo es: z’ = z . 0. tal que no pertenece a la base. X2=(4. 1.cj ) = z no hemos mejorado la solución anterior. en un número finito de iteraciones llegábamos a la solución óptima. esto nos indicará que existe multiplicidad de óptimos.
2. obtendríamos todos los vértices que son soluciones óptimas. de manera que. Min z = x1-2x2+3x3 st x1.
. 1. .x2+x3 + 2x4 =10 x2.. 7/2. Toda solución óptima es una combinación lineal convexa de las soluciones factibles básicas óptimas. 2. 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.
. N) donde Bmxm es la matriz básica y N(mx(n-m))..
x    Ahora bien. un punto extremo degenerado. estaríamos en un punto extremo que tiene menos de “m” coordenadas positivas. A2. Am) es la matriz básica. la matriz B= (A1. 0.. Descomponiendo la matriz A de forma que A=(B.11. Se identifica en la tabla simplex porque al menos una variable básica tiene valor cero en la columna de solución. 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. 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. la matriz no básica (los Ai que no son de la base). no se podría hacer salir a la vez a todos ellos. A2. la cual se tiene con al menos una variable básica de valor cero en el sistema de m restricciones.Programación Lineal
 ij elegir uno cualquiera y. xm. XB = (x1. XB = B-1 b
. x2. 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. Denotemos por Ai la columna i-ésima de la matriz A y supongamos que los m vectores linealmente independientes son los m primeros A1. b) = rang (A) = m. tenemos BXB = b. Se podría
2. El método del simplex revisado
Un procedimiento más eficiente que el simplex en su versión matricial es el llamado simplex revisado. 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. entonces.….. Am. esto es. . es decir. si al calcular el valor de j = min  i /  ij  0 existen varios i i    ij  xi tal que minimizan .…. 0)T.
 2 j.
.5 -0.5 -0. …. Dada la tabla óptima del Simplex:
cj b 0. Xj = B-1 Aj
El valor de la función objetivo en ese punto es z = cBTXB= cBT B-1 b y los valores de zj = c1  1 j + c2  2 j + … + cm  m j =
zj =  c i  i j = cBT Xj = cBT B-1 Aj = TAj
Donde T= cBT B-1.  m j )T.75 3. al vector columna mx1 se le denomina vector de multiplicadores del simplex asociado a la base B.5 -0.5 0.62 y puesto que
esto es Aj = BXj.5 1. Escriba la solución en el recuadro adjunto.5 -0.5
A5 -0.
Ayuda:  b11  B   b21 b  31
 1 1  0 1 0 1 
Max z= st
b) Formule el problema Dual y de la solución sin hacer operaciones.75 1. Xj= ( 1 j.5 -0. Veamos el ejercicio siguiente.75 zj-cj
Base cB A1 A3 A2 z zj
A1 1 0 0 -2 0
A2 0 0 1 -1 0
A3 0 1 0 0 0
A4 0.5 0.25 -4.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. si se sabe que la primera restricción es () y el resto ().
5 0.Programación Lineal Solución: a) La matriz inversa se obtiene directamente de la tabla:
0.5 x1+x2  4 x1. 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  0.75   3       B X=b=  3 0 1 1.  2  1 1   T T tenemos: c =  B=(0 0.5 1.5  0   0.5   
 2  1 1   (B ) =B=  3 0 1  1 0 1  
A continuación se calculan los vectores Aj (j=1. B =   1 0.5  .5  0. x2  0
b) Operando con el vector de multiplicadores del simplex asociado a la base B. 2.25   4       La formulación del problema sería:
Max z= 2x1+ x2 st
2 x1+ x2  3 3x1+x2 5.5   1 0 1 3.75    5.5)  3 0 1  (2 0 1)  1 0 1  
..... Xj = B-1 Aj.. a la matriz E se la denomina matriz elemental..11. Ar+1. Determinación de la inversa..     0 0 ...  ... 0     0 1 . 1 mj   La inversa de R la denotamos por E y viene dada por
1 0 . A2...... 1 j ....... ... A2...   mj /  rj ..….. sea B= (A1........  1 j /  rj ..  E=R =  0 0 .... Ar.. tomábamos la base canónica.... B-1 B1= R
donde R es la matriz identidad reemplazando la r-ésima columna por el vector columna Xj... si realizamos un cambio de base a la base B1. 1 /  rj .. B1-1 = I y XB = b....64
2...…. 1 Entonces B1-1= R-1 B-1= E B-1... Forma producto de la inversa
Sea B una base y B-1 su inversa.. Ar-1........ B1=I. Ar+1. En efecto..   2 j /  rj .... 0    -1  .. Am).....   0 0 . 0     ....  2 j ..... E2 E1
. Cuando comenzábamos el método del simplex......... es decir. podemos conocer B1-1 en términos de B-1... esto es:
1 0 . Aj.....1. tenemos: B2-1= E1 B1-1 = E1 I= E1 B3-1= E2 B2-1 = E2 E1 y.. 0  R=    . en general la inversa de la base de la k-ésima iteración se obtiene Bk-1 = Ek-1 Ek-2 …... 0     0 1 . Ar-1.... Siguiendo un proceso iterativo.. Am) y supongamos que al realizar el cambio de base introducimos el vector Aj y sale Ar B1= (A1..
Las modificaciones deben ser hechas antes de introducir los datos en el programa. la función objetivo no tendría solución finita. Utilizando el programa LINDO para resolver el ejercicio 1. E2E1Aj La última columna representa la situación en la k-ésima iteración.cj …. 3)
.cj) > 0 y Xj  0.cj)  0 j.
2. de lo contrario el problema es degenerado. utilizaremos el programa LINDO (L = Linear IN = Interactive D = Discrete O = Optimizer). E2E1Aj-cj
B-1 XB = B-1 b Xj = B-1 Aj …. zj -cj =cB Ek-1Ek-2 …. El número de variables positivas (decisión + holgura) al finalizar el Simplex debe ser igual al número de restricciones. Xj = Ek-1Ek-2 …. En la columna de variables de holgura (SLACK OR SURPLUS) vienen los resultados de esas variables (por restricción). Resolución mediante programa de ordenador
1. 2.11.2. las de valor cero indicarán que el recurso se ha consumido en su totalidad. Si para algún (zj . en cuyo caso ya tendríamos la solución óptima. En cada iteración hay que controlar si todos los (zj .Programación Lineal
que expresa la inversa como producto de matrices elementales. A dicha expresión se la conoce como forma producto de la inversa. se pondrán de manera que cumplan esta condición. tenemos: Min z = –5x1+2x2-3x3 st 2x1+2x2-x34 3x1.x2+x33 2x1+x2+3x35 xi  0 (i=1. mientras no se diga lo contrario. en tanto que todos los términos constantes (recursos) aparecerán a la derecha. Etapas del método del simplex revisado
Toda la información necesaria para aplicar el método del simplex se puede escribir en una tabla:
T -1 T T= cBTB-1 z = cB B b zj . Si el programa requiere que todas las variables sean no negativas. Todas las variables de las restricciones deben aparecer en el primer miembro. 3.cj = TAj . Hay que hacer notar que la presentación de la salida depende del programa utilizado. Nosotros. 2.12.
285714 0.429 -0.571429
Observando la salida del programa.714 -0.571429 0.286
ROW 1 2 3 4
SLK 4 0. x1= 4/7=0.000000 1.000 0.000000 0.000 1.000 1.000000 1.857 -0.000 SLK 2 0.000 0.000 X2 1.286 -1.143 0.285714 0.143 0.429
6. ITERATIONS=
ROW (BASIS) 1 ART 2 SLK 2 3 X1 4 X3 X1 0.000 0.142857 0.2857 Que coincide con el obtenido mediante el algoritmo del simplex.714 X3 0. x2=0 (no aparece). el resultado es: z = -6.714286.000 0.000 1.66
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 -6.571 0.143 0.000000 2
DUAL PRICES 0.714286 VALUE 0.000000 1.000 SLK 3 1.000000
SLACK OR SURPLUS 4.000 0.714 4.285714 REDUCED COST 0.5714.286 3.571 1.571 0.
. x3=9/7=1.000 0.
Documentos similares a Optimizacion LinealSkip carouselProgramacion CuadraticaProgramacion Lineal 1Cap02(PL)_IO-IAmer TrabajoTrabajo Investigacion Metodos c.Programación LinealProgramacion LinealQuiz 1 Modelo Toma de DesicionesToma de Decisiones 7mo SemestreTarea 2-GuionENSAYO DE PROGRAMACION LINEALCORRECION QUIZ MODELO TOMA DE DECISIONES.docxSD-10-Programacion-lineal-RENOLFI.pdfFormulación de un complemento nutrimental al mínimo costo para rumiantes bajo sistema de pastoreo usando una hoja de cálculo con el método de programación lineal_5 curatillasCap.2_IO1_2015-0Cap.3_IO1_2013.pptMetodo Descomposicion LinealUnidad 5- Programacion Lineal. Teoria.pdfLagrange Ejerciciosexamen-2014-11-21Informe3 Tuberias Ing.sistemasDiapositivas Solverquiz 1 Y 2 CORREGIDO DE PROGRAMACIÓN LINEALApuntes Inv de Operaciones (1)manualOPL_080410US-14Investigación de Operaciones sistemasPrograma Dual en LINDOA7Metodos Cuantitativos Para La Toma de Decisiones

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