• Author / Uploaded
• Julian Andres

Citation preview

4.4.2 Algoritmo s´ımplex generalizado El algoritmo s´ımplex (primal) inicia siendo factible, pero no ´optimo. El s´ımplex dual comienza mejor que el ´optimo, pero no factible. ¿Y si un modelo de programaci´on lineal iniciara no ´optimo y no factible al mismo tiempo? Hemos visto que el s´ımplex primal tiene en cuenta la no factibilidad de la soluci´on de inicio usando variables artificiales. En forma parecida, el s´ımplex dual tiene en cuenta la no optimalidad usando restricciones artificiales. Aunque esos procedimientos tienen por objeto ampliar el c´omputo autom´atico, los detalles pueden hacer perder de vista lo que realmente implica el algoritmo s´ımplex, que es que la soluci´on ´optima de una programaci´on lineal siempre se asocia con una soluci´on de punto de esquina (o b´asica). Con base en esta observaci´on usted deber´ıa poder “adaptar” su propio algoritmo s´ımplex para modelos de programaci´on lineal que inician siendo no ´optimos y no factibles a la vez. En el siguiente ejemplo se ilustra lo que se llama algoritmo s´ımplex generalizado. Ejemplo 4.4-2 El modelo de programaci´on lineal del problema 2a), del conjunto dado previamente, se puede poner en la tabla siguiente, en el que la soluci´on b´asica de inicio (x4 , x5 , x6 ) es al mismo tiempo no ´optima (por x3 ) y no factible (por x4 = −8). (La primera ecuaci´on se multiplic´o por −1 para revelar la no factibilidad en forma directa, en la columna Soluci´on). B´asica x1 x2 x3 x4 x5 x6 Soluci´on z 0 0 −2 0 0 0 0 x4 1 −2 2 1 0 0 −8 x5 −1 1 1 0 1 0 4 x6 2 −1 4 0 0 1 10 El problema se puede resolver sin usar variables ni restricciones artificiales, como sigue: quitar primero la no factibilidad aplicando una versi´on de la condici´on s´ımplex dual de factibilidad, que seleccione a x4 como variable de salida. Para determinar cu´al es la variable de entrada todo lo que se necesita es una variable no b´asica cuyo coeficiente de restricci´on en fila x4 , sea estrictamente negativo. Se puede hacer la selecci´on sin cuidarse de mantener la optimalidad, porque de cualquier manera es no existente en este punto (comp´arela con la condici´on de optimalidad dual). El resultado es la siguiente tabla:

1

B´asica x1 x2 x3 x4 x5 x6 Soluci´on z 0 0 −2 0 0 0 0 x2 −1/2 1 −1 −1/2 0 0 4 x5 −1/2 0 2 1/2 1 0 0 x6 3/2 0 3 −1/2 0 1 14

Ahora la soluci´on en esta tabla es factible, pero no ´optima, y podremos usar el s´ımplex primal para determinar la soluci´on ´optima. En general, si no nos hubi´eramos encontrado la factibilidad en la tabla anterior, habr´ıa que repetir el procedimiento las veces necesarias hasta satisfacer la factibilidad, o hasta que haya pruebas de que el problema no tenga soluci´on factible. Una vez establecida la factibilidad, el siguiente paso es atender la optimalidad, aplicando la condici´on adecuada de optimalidad del m´etodo s´ımplex primal. La esencia del ejemplo 4.4-2 es que el m´etodo s´ımplex no es r´ıgido. En las publicaciones abundan las variaciones del m´etodo s´ımplex (por ejemplo, el m´etodo primal-dual, el m´etodo sim´etrico, el m´etodo entrecruzado y el m´etodo m´ ultiplex) que dan la impresi´on que cada uno es distinto, cuando en realidad todos buscan una soluci´on de punto esquina, con inclinaci´on hacia los c´alculos autom´aticos y quiz´a hacia la eficiencia de c´omputo. ´ ´ ANALISIS POSTOPTIMO O DE SENSIBILIDAD Al estudiar el m´etodo gr´afico para problemes de optimizaci´on lineal, se describi´o el an´alisis de sensibilidad a un nivel elemental. En esta secci´on se aplicar´a la dualidad y los c´alculos primal-dual para examinar el tema en forma m´as completa. El an´alisis de sensibilidad investiga el cambio de la soluci´on ´optima que resulta de hacer cambios en los par´ametros del modelo de programaci´on lineal. La tabla siguiente contiene todos los casos posibles que pueden surgir en el an´alisis de sensibilidad, as´ı como las acciones necesarias para obtener la nueva soluci´on (suponiendo que exista):

2

Condici´on resultante de los cambios

Acci´on recomendada

La soluci´on actual queda ´optima y factible La soluci´on actual se vuelve no factible

No es necesaria acci´on alguna Usar el simplex dual para recuperar la factibilidad Usar el simplex primal para recuperar la ´optimalidad Usar el m´etodo simplex generalizado para obtener una nueva soluci´on

La soluci´on actual se vuelve no ´optima La soluci´on actual se vuelve no ´optima y no factible a la vez

Los tres primeros casos se investigar´an en esta secci´on. El cuarto, como es una combinaci´on de los casos 2 y 3, se resolver´a m´as adelante. El modelo de TOYCO en el ejemplo 4.3-2 servir´a para explicar los distintos procedimientos. Recu´erdese que ese modelo es del ensamble de tres clases de juguetes: trenes, camiones y autos. Cada art´ıculo requiere tres operaciones sucesivas. Se desea determinar la cantidad de unidades de cada juguete que haga m´axima a la utilidad. A continuaci´on se repiten el modelo y su dual, por comodidad. Primal de TOYCO

Dual de TOYCO

Maximizar z = 3x1 + 2x2 + 5x3 sujeta a x1 + 2x2 + x3 ≤ 430 (operaci´on 1) 3x1 + 2x3 ≤ 460 (operaci´on 2) x1 + 4x2 ≤ 420 (operaci´on 3) xk ≥ 0 Soluci´on ´optima: x1 = 0, x2 = 100, x3 = 230, z = $1350

Minimizar z = 430y1 + 460y2 + 420y3 sujeta a y1 + 3y2 + y3 ≥ 3 2y1 + 4y3 ≥ 2 y1 + 2y2 ≥ 5 yk ≥ 0 Soluci´on ´optima: y1 = 1, y2 = 2, y3 = 0, w = $1350

La tabla ´optima asociada para el primal es:

3

B´asica x1 x2 x3 x4 x5 x6 Soluci´on z 4 0 0 1 2 0 1350 x2 −1/4 1 0 1/2 −1/4 0 100 x3 3/2 0 1 0 1/2 0 230 x6 2 0 0 −2 1 1 20

Cambios que afectan la factibilidad La factibilidad de la soluci´on ´optima en el momento s´olo puede variar si 1) cambia el lado derecho de las restricciones, o 2) se agrega al modelo una restricci´on nueva. En ambos casos se tiene no factibilidad cuando al menos un elemento del lado derecho en la tabla ´optima se hace negativo; esto es, una o m´as de las variables b´asicas actuales se vuelve negativa. Cambios en el lado derecho Estos cambios requieren volver a calcular el lado derecho de la tabla, usando la f´ormula 1 de la secci´on 4.2.4, esto es, 

Nuevo lado derecho de la tabla en la iteraci´on i



 =

Inversa en la iteraci´on i



 ×

Nuevo lado derecho de la iteraci´on i



Recuerde que el lado derecho de la tabla expresa los valores de las variables b´asicas. El siguiente ejemplo ilustrar´a el procedimiento. Ejemplo 4.5-1 Suponga que TOYCO desea ampliar sus l´ıneas de ensamble aumentando en 40% la capacidad diaria de cada una, hasta 602, 644 y 588 minutos, respectivamente. Con esos aumentos, el u ´nico cambio que se har´a en la tabla ´optima es el lado derecho de las restricciones (y el valor objetivo ´optimo). As´ı, la nueva soluci´on b´asica se calcula como sigue: 

      x2 1/2 −1/4 0 602 140  x3  =  0 1/2 0   644  =  322  x6 −2 1 1 588 328 4

As´ı, las variables b´asicas actuales (x2 , x3 y x6 ) siguen siendo factibles con los nuevos valores 140, 322 y 328. La utilidad ´optima correspondiente es $1890. Aunque la nueva soluci´on es atrayente, tanto desde el punto de vista de mayor utilidad, TOYCO reconoce que para implementarla pasar´a algo de tiempo. En consecuencia se hizo otra proposici´on que es cambiar la holgura de capacidad de la operaci´on 3 (x6 = 20 minutos) a la capacidad de la operaci´on 1, con lo que cambia la combinaci´on de las tres operaciones a 450,460 y 400 minutos, respectivamente. La soluci´on resultante es        x2 1/2 −1/4 0 450 110  x3  =  0 1/2 0   460  =  230  x6 −2 1 1 400 −40 Esta soluci´on es no factible, porque x6 = −40. Se aplicar´a el m´etodo s´ımplex dual para recuperar la factibilidad. Primero se modifica el lado derecho de la tabla, como se ve en la columna enmarcada. Observe que el valor asociado de z = 3×0+2×110+5×230 = $1370. B´asica x1 x2 x3 x4 x5 x6 Soluci´on z 4 0 0 1 2 0 1370 x2 −1/4 1 0 1/2 −1/4 0 110 x3 3/2 0 1 0 1/2 0 230 x6 2 0 0 −2 1 1 −40

Comenzando con el s´ımplex dual, sale x6 y entra x4 , con lo que la tabla ´optima factible es la siguiente (en general, el s´ımplex dual requerir´a m´as de una iteraci´on para recuperar la factibilidad). B´asica x1 x2 x3 x4 x5 x6 Soluci´on z 5 0 0 0 5/2 1/2 1350 x2 1/4 1 0 0 0 1/4 100 x3 3/2 0 1 0 1/2 0 230 x4 −1 0 0 1 −1/2 −1/2 20 5

La soluci´on ´optima (en funci´on de x1 , x2 y x3 ) queda igual que en el modelo original. Tambi´en se demuestra que no se us´o la capacidad adicional para la operaci´on 1 (x4 = 20). La u ´nica conclusi´on entonces es que la operaci´on 2 es el cuello de botella. Intervalo de factibilidad de los elementos del lado derecho Otra forma de examinar el efecto de cambiar la disponibilidad de los recursos (es decir, el vector del lado derecho) es determinar el intervalo para el cual la soluci´on actual o del momento permanece factible. El ejemplo siguiente ilustra el procedimiento. Ejemplo 4.5-2 En el modelo de TOYCO, suponer que lo que interesa es determinar el intervalo de factibilidad de la capacidad de la operaci´on 1. Se puede hacer reemplazando el lado derecho con 

 430 + D1   460 420 La cantidad D1 representa el cambio en la capacidad de la operaci´on 1, arriba y abajo del valor actual de 430 minutos. La soluci´on actual b´asica permanece factible si todas las variables b´asicas son no negativas, esto es, 

        x2 1/2 −1/4 0 430 + D1 100 + D1 /2 0  x3  =  0       1/2 0 460 230 0  = ≥ x6 −2 1 1 420 20 − 2D1 0

Estas condiciones conducen a las siguientes cotas de D1 : (x2 ≥ 0) : 100 + D1 /2 ≥ 0 ⇒ D1 ≥ −200 (x3 ≥ 0) : x3 es independiente de D1 (x6 ≥ 0) : 20 − 2D1 ≥ 0 ⇒ D1 ≤ 10 As´ı, la soluci´on actual permanece factible cuando, −200 ≤ D1 ≤ 10 6

Esto equivale a variar los minutos de disponibilidad de la operaci´on en el intervalo 430 − 200 ≤ (Capacidad de la operaci´on 1) ≤ 430 + 10 o sea 230 ≤ (Capacidad de la operaci´on 1) ≤ 440 El cambio en el valor objetivo ´optimo asociado con D1 es D1 y1 , siendo y1 el valor por unidad (precio dual), en $ por minuto de la operaci´on 1. Para ilustrar el uso del intervalo determinado, suponga que la capacidad de la operaci´on 1 cambia desde su valor actual de 430 a 400 minutos. La soluci´on b´asica actual permanece factibie, porque la nueva capacidad queda dentro del intervalo factible. Para calcular los valores nuevos de las variables se usa D1 = 400 − 430 = −30 As´ı,      100 + (−30)/2 85 x2  =  230   x3  =  230 20 − 2(−30) 80 x6 

Para calcular el cambio asociado en el valor ´optimo de la funci´on objetivo se calculan primero los precios duales, con el m´etodo 1 de la secci´on 4.2.3, esto es



Valores ´optimos de las variables duales





   Coeficientes originales Inversa =  de las variables ´optimas  × ´optima b´asicas primales

As´ı, 

 1/2 −1/4 0 1/2 0  = (1, 2, 0) (y1 , y2 , y3 ) = (2, 5, 0)  0 −2 1 1 Esto quiere decir que el valor de la operaci´on 1 por minuto es y1 = $1, y que el cambio de la utilidad ´optima es D1 y1 = −30 × 1 = −$30. Recuerde y1 = 1, el valor dado por unidad, sigue siendo v´alido s´olo dentro del intervalo especificado: −200 ≤ D1 ≤ 10 7

Todo cambio que salga de este intervalo causa no factibilidad; de aqu´ı la necesidad de usar el m´etodo s´ımplex dual para determinar la nueva soluci´on, si es que existe. Para determinar los intervalos factibles D2 y D3 , los cambios asociados con las operaciones 2 y 3 se pueden usar procedimientos parecidos. La determinaci´on de D1 , D2 y D3 en la forma establecida, y su relaci´on con los valores duales ´optimos y1 , y2 y y3 s´olo son v´alidas cuando se considera por separado cada recurso. Si se quisiera cambiar los tres recursos al mismo tiempo, se debe deducir un conjunto distinto de condiciones, con los elementos del lado derecho 430 + D1 , 460 + D2 y 420 + D3 . Adici´ on de nuevas restricciones. La adici´on de una nueva restricci´on a un modelo existente puede llevar a uno de los dos casos siguientes: 1. La nueva restricci´on es redundante, lo que quiere decir que se satisface con la soluci´on ´optima actual y, por consiguiente, se puede eliminar por completo del modelo. 2. La soluci´on actual viola la nueva restricci´on, y en este caso se puede aplicar el m´etodo s´ımplex dual para recuperar la factibilidad. Observe que la adici´on de una nueva restricci´on, como en el caso 2, nunca puede mejorar el valor objetivo ´optimo actual. Ejemplo 4.5-3 Suponga que TOYCO cambia el dise˜ no de los juguetes, y que para el cambio se requerir´a agregar una cuarta operaci´on en las l´ıneas de ensamble. La capacidad diaria de la nueva operaci´on es 500 minutos, y los tiempos por unidad, para los tres productos en esta operaci´on, son 3, 1 y 1 minutos, respectivamente. La restricci´on resultante se forma, por consiguiente, como sigue: 3x1 + x2 + x3 ≤ 500 Esta restricci´on es redundante, porque queda satisfecha con la soluci´on ´optima actual x1 = 0, x2 = 100 y x3 = 230. Eso quiere decir que la soluci´on ´optima actual permanece sin cambio.

8

Ahora suponga que los tiempos por unidad, en TOYCO, para la cuarta operaci´on son 3,3 y 1 minutos, respectivamente. Todos los datos restantes del modelo permanecen igual. En este caso, la cuarta restricci´on 3x1 + 3x2 + x3 ≤ 500 no queda satisfecha por la soluci´on ´optima actual. En consecuencia, debemos aumentar la nueva restricci´on a la tabla ´optima actual, como sigue (x7 es una holgura): B´asica z x2 x3 x6 x7

x1 x2 x3 x4 x5 x6 x7 Soluci´on 4 0 0 1 2 0 0 1350 −1/4 1 0 1/2 −1/4 0 0 100 230 3/2 0 1 0 1/2 0 0 2 0 0 −2 1 1 0 20 3 3 1 0 0 0 1 500

Como las variables x2 y x3 son b´asicas, se deben sustituir y eliminar sus coeficientes de restricci´on en la fila de x7 , lo que se puede hacer con la siguiente operaci´on: Nueva fila de x7 =Fila anterior de x7 −{3×(fila de x2 )+1×(fila de x3 )} B´asica x1 x2 x3 x4 x5 x6 x7 Soluci´on z 4 0 0 1 2 0 0 1350 x2 −1/4 1 0 1/2 −1/4 0 0 100 230 x3 3/2 0 1 0 1/2 0 0 x6 2 0 0 −2 1 1 0 20 x7 9/4 0 0 −3/2 1/4 0 1 −30

La aplicaci´on del m´etodo s´ımplex dual dar´a como resultado la nueva soluci´on ´optima x1 = 0, x2 = 90, x3 = 230, z = $1330 (¡compru´ebelo!) Cambios que afectan la optimalidad En esta secci´on se examinan dos soluciones particulares que podr´ıan afectar la optimalidad de la soluci´on actual: 1. Cambios en los coeficientes objetivo originales. 9

2. Adici´on de una nueva actividad econ´omica (variable) al modelo. Cambios en los coeficientes de la funci´ on objetivo. Esos cambios s´olo afectan la optimalidad de la soluci´on. Por consiguiente requieren recalcular los coeficientes de la fila z, con el siguiente procedimiento: 1. Calcular los valores duales con los m´etodos 1 y 2 de la secci´on 4.2.3. 2. Usar los nuevos valores duales en la f´ormula 2, secci´on 4.2.4, para determinar los nuevos coeficientes en el fila de z. Se presentar´an dos casos: 1. La nueva fila de z satisface la condici´on de optimalidad, y la soluci´on permanece sin cambio (sin embargo, el valor objetivo ´optimo puede cambiar). 2. La condici´on de optimalidad no se satisface, y en ese caso se aplica el m´etodo s´ımplex (primal) para recuperar la optimalidad. Ejemplo 4.5-4 En el modelo de TOYCO, suponga que la empresa tiene nueva pol´ıtica de precios para igualar la competencia. Bajo la nueva pol´ıtica, las utilidades por unidad son $2, $3 y $4, por los trenes, camiones y autos, respectivamente. La nueva funci´on objetivo es Maximizar z = 2x1 + 3x2 + 4x3 As´ı, (Nuevos coeficientes objetivo de x2 , x3 y x6 b´asicas)=(3,4,0) Las variables duales se calculan con el m´etodo 1 de  1/2 −1/4 1/2 (y1 , y2 , y3 ) = (3, 4, 0)  0 −2 1

la secci´on 4.2.3, como sigue:  0 0  = (3/2, 5/4, 0) 1

Los coeficientes de la fila z se determinan como la diferencia entre los lados izquierdo y derecho de las restricciones duales (f´ormula 2, secci´on 4.2.4). No es necesario recalcular 10

los coeficientes de las variables b´asicas x2 , x3 y x6 en el fila objetivo, porque siempre son iguales a cero, independientemente de los cambios hechos a los coeficientes objetivo (¡compru´ebelo!). x1 : y1 + 3y2 + y3 − 2 = 3/2 + 3(5/4) + 0 − 2 = 13/4 x4 : y1 − 0 = 3/2 x5 : y2 − 0 = 5/4 N´otese que el lado derecho de la restricci´on dual asociada con x1 es 2, el coeficiente nuevo en la funci´on objetivo modificada. Los c´alculos indican que en la soluci´on actual, x1 = 0 trenes, x2 = 100 camiones y x3 = 230 autos, permanece ´optima. La nueva utilidad correspondiente se calcula como 2 × 0 + 3 × 100 + 4 × 230 = $1220. Ahora suponga que cambia la funci´on objetivo de TOYCO a Maximizar z = 6x1 + 3x2 + 4x3 Los cambios correspondientes en la fila de z se indican en la siguiente tabla (¡compru´ebelos!): B´asica z x2 x3 x6

x1 x2 x3 −3/4 0 0 −1/4 1 0 3/2 0 1 2 0 0

x4 x5 x6 Soluci´on 3/2 5/4 0 1220 1/2 −1/4 0 100 0 1/2 0 230 −2 1 1 20

Los elementos que est´an en las celdas enmarcadas son las nuevas zj − cj para las variables no b´asicas x1 , x4 y x5 . Todos los elementos restantes de la tabla son iguales a los de la iteraci´on original ´optima. Entonces, la nueva soluci´on ´optima se determina haciendo entrar a x1 y salir a x6 , con lo que se obtiene x1 = 10, x2 = 102.5, x3 = 215 y z = $1227.50 (¡compru´ebelo!). Intervalo de optimalidad de los coeficientes objetivo Otra forma de investigar el efecto de los cambios en los coeficientes de la funci´on objetivo es calcular el intervalo para el que cada coeficiente individual mantenga la soluci´on ´optima actual. Esto se hace reemplazando el cj actual con cj + dj donde dj representa la cantidad (positiva o negativa) de cambio.

11

Ejemplo 4.5-5 Suponga que la funci´on objetivo del modelo de TOYCO cambia a Maximizar z = (3 + d1 )x1 + 2x2 + 5x3 Determinar el intervalo de optimalidad para el cambio d1 . Seguiremos el procedimiento que se describi´o arriba. Sin embargo, observe que, como x1 no es b´asica en la tabla ´optima, los valores duales no se ver´an afectados por este cambio y en consecuencia permanecer´an igual que en el modelo original (es decir, y1 = 1, y2 = 2, y3 = 0). En realidad, como x1 es no b´asica, s´olo se afectar´a su coeficiente en la fila z, y todos los dem´as coeficientes de ese fila permanecen sin cambio (¿por qu´e?). Eso quiere decir que se necesita aplicar la f´ormula 2, secci´on 4.2.4 a la restricci´on dual asociada s´olo con x1 , esto es, x1 :

y1 + 3y2 + y3 − (3 + d1 ) = 1 + 3 × 2 + 0 − (3 + d1 ) = 4 − d1

Como el modelo de TOYCO es un problema de maximizaci´on, la soluci´on original permanecer´a ´optima siempre que 4 − d1 ≥ 0, o sea d1 ≤ 4 Esto equivale a decir que la soluci´on actual permanece ´optima siempre que el coeficiente objetivo c1 (= 3 + d1 ) de x1 , no sea mayor que 3 + 4 = $7. Ahora se considerar´a el cambio d2 en el coeficiente objetivo de x2 : Maximizar z = 3x1 + (2 + d2 )x2 + 5x3 La diferencia en este caso es que x2 es b´asica y su cambio afectar´a los valores duales para despu´es afectar todos los coeficientes de todas las variables no b´ asicas del fila z (recuerde que los coeficientes de las variables b´asicas en la fila z siempre son iguales a cero, independientemente de cualquier cambio en la funci´on objetivo). Al aplicar el m´etodo 1, secci´on 4.2.3, para calcular los valores duales se obtiene:

12



 1/2 −1/4 0 1/2 0  = (1 + d2 /2, 2 − d2 /4, 0) nueva (y1 , y2 , y3 ) = (2 + d2 , 5, 0)  0 −2 1 1 Se pueden calcular los coeficientes de las variables no b´asicas en la fila z como sigue: x1 : x4 : x5 :

y1 + 3y2 + y3 − 3 = (1 + d2 /2) + 3 × (2 − d2 /4) + 0 − 3 = 4 − d2 /4 ≥ 0 (1) y1 − 0 = (1 + d2 /2) − 0 = 1 + d2 /2 ≥ 0 (2) y2 − 0 = (2 − d2 /4) − 0 = 2 − d2 /4 ≥ 0 (3)

Las desigualdades (1), (2) y (3), respectivamente, dan como resultado d2 ≤ 16, d2 ≥ −2 y d2 ≤ 8 o sea, −2 ≤ d2 ≤ 8 Por lo tanto, dada c2 = 2 + d2 , se obtiene 0 ≤ c2 ≤ 10 Adici´ on de una nueva actividad. La adici´on de una nueva actividad en un modelo de programaci´on lineal equivale a agregar una nueva variable. En forma intuitiva, la adici´on de una nueva actividad s´olo es deseable si es rentable, esto es, si mejora el valor ´optimo de la funci´on objetivo. Esta condici´on se puede verificar aplicando la f´ormula 2, secci´on 4.2.4, a la nueva actividad. Como esa nueva actividad no es todav´ıa parte de la soluci´on, se puede considerar como una variable no b´asica. Eso quiere decir que los valores duales asociados con la soluci´on actual permanecen invariables. Si la f´ormula 2 indica que la nueva actividad satisface la condici´on de optimalidad, la actividad no es rentable. En caso contrario, es mejor tener en cuenta la nueva actividad. Ejemplo 4.5-6 TOYCO reconoce que los trenes de juguete no se producen en la actualidad porque no son rentables. La empresa quiere reemplazar los trenes con un nuevo producto, un carro de bomberos de juguete, que se arme en las instalaciones existentes. TOYCO estima que la utilidad por carro de bomberos es $4 y que los tiempos de ensamble por 13

unidad son 1 minuto en cada una de las operaciones 1 y 2, y 2 minutos en la operaci´on 3. Sea x7 el nuevo producto, el carro de bomberos. Como (y1 , y2 , y3 ) = (1, 2, 0) son los valores duales ´optimos, el costo reducido de x7 se puede calcular como sigue: 1y1 + 1y2 + 2y3 − 4 = 1 × 1 + 1 × 2 + 2 × 0 − 4 = −1 Seg´ un este resultado, conviene econ´omicamente incluir a x7 , en la soluci´on b´asica ´optima. Para obtener el nuevo ´optimo se calcula primero su columna de restricciones con la f´ormula 1, secci´on 4.2.4, como sigue:



    1/2 −1/4 0 1 1/4 1/2 0   1  =  1/2  Columna de restricci´on de x7 =  0 −2 1 1 2 1 As´ı, se debe modificar la tabla s´ımplex actual como sigue: B´asica x1 x2 x3 x7 x4 x5 x6 Soluci´on z 4 0 0 −1 1 2 0 1350 x2 −1/4 1 0 1/4 1/2 −1/4 0 100 0 1/2 0 230 x3 3/2 0 1 1/2 x6 2 0 0 1 −2 1 1 20

Se determina el nuevo valor ´optimo haciendo entrar x7 a la soluci´on b´asica, y en ese caso debe salir x6 . La nueva soluci´on es x1 = 0, x2 = 0, x3 = 125, x7 = 210 y z = $1465 (¡compruebelo!) El caso de agregar una actividad nueva tambi´en abarca al caso en que se hicieron cambios al uso de los recursos, en una actividad existente. En forma espec´ıfica se puede considerar a x7 como si al principio tuviera un coeficeinte objetivo cero y uso cero de sus tres recursos, y que esos valores cero se cambiaron a los nuevos valores para x7 . Por esta raz´on, no es necesario describir por separado el caso de cambiar los coeficientes de restricci´on de una variable existente.

14