X2

Número de kg de harina tipo 2 a incluir en los 1 0 0 0 kg de alimento.

X M : kg de minerales a mezclar en los 1000 kg de alimento. W

: Función de costo del alimento.

Modelo (Primal): M I N W = 22 XA + 31 XB + 4 5 X c + 1 7 X, + 15 X2 + 125 X M Con sus restricciones:

Resumiendo:

Sujeta a :

91

PROBLEMA

14

(Cortes)

Una empresa produce bobinas de papel de 5 0 0 metros de longitud y un metro de ancho; se ha estimado que la demanda para el mes próximo es de 5 0 0 bobinas de 2 0 cm de ancho, 4 0 0 bobinas de 3 0 cm de ancho, 2 5 0 bobinas de 4 0 cm de ancho y 3 0 0 bobinas de 70 cm de ancho (todas las bobinas son de 5 0 0 metros de longitud). El fabricante debe cortar las bobinas de un metro de ancho con el tamaño de las peticiones para satisfacer la demanda, pero también desea que el desperdicio en el corte sea tal que el número de bobinas que fabrique de un metro sea mínimo con el objetivo que el costo de producción también lo sea, si se considera desperdicio los sobrantes iguales o superiores a 10 cm. Variables reales: X¡ W :

Número de bobinas a cortar de 5 0 0 metros según el patrón i, i = 1, 2, 3, 4, 5, 6, 7, 8, 10 Función de costo del desperdicio en el corte de las bobinas. Patrones

20

30

40

70

Sobrantes(cm)

1 2 3 4 5 6 7 8 9 10

5 3 3 1 0 1 0 0 1 2

0 0 1 0 1 1 2 3 0 2

o 1 0 0 0 1

0 0 0 1 1 0 0 0 0 0

,0 0 10 10 0 10 0 ao 0 0

M o d e l o (Primal): M I N W = 10 X 3 + 10 X 4 + 10 X6 + 10 X, Sujeta a :

92

1 0 2 0

PROBLEMA

15

(Mezclas)

En la Empresa Colombiana de Petróleos ECOPETROL se procesan tres tipos de gasolina:

Tipo

Clase

O c t a n a j e (Octanos)

1

Popular

95

2

Corriente

92

3

Extra

98

3ra ello se mezclan cuatro productos base, cuyo costo y disponibilidad son:

Producto

Disponibilidad

Costo/Unidad (S/Barril]

A

3000

90000

B

2000

1 80000

C

4000

120000

D

1000

150000

¿fara la clasificación de la mezcla en uno de los tres tipos de gasolina se atiende a la proporción de los productos que la componen de acuerdo a la siguiente tabla:

— : Indica que no interesa la proporción de ese producto.

V a r i a b l e s d e decisión: Yi

Cantidad de barriles de gasolina tipo 1 (Popular).

Y2

: Número de barriles de gasolina tipo 2 (Corriente).

Y3

: Cantidad de barriles de gasolina tipo 3 (Extra).

Y a : Número de barriles del producto A. Y b : Cantidad de barriles del producto B. Y C : Número de barriles del producto C. YQ : Cantidad de barriles del producto D. X¡¡

Número de barriles del producto i

{A, B, C, D} invertidos en j

Z

Función de maximización de la utilidad.

{ 1 , 2, 3 }

93

M o d e l o (Primal):

Resumiendo:

Con sus restricciones:

94

l

PROBLEMA

16

(Decisiones)

El gobierno actual requiere el máximo apoyo para que se apruebe en el Congreso el plan de desarrollo propuesto para el próximo año. A través de sus consejeros ha sabido que hay 3 5 congresistas de un grupo de coalición y 2 7 de otro partido que aún no han definido su voto. El presidente decide entonces concertar por teléfono a estos congresistas indecisos para convencerlos de que lo apoyen, sabiendo que tiene una probabilidad 0,9 de éxito con los miembros de la coalición y 0,6 de otro partido. ¿Cuántos congresistas de cada partido deberá telefonear para maximizar su probabilidad de éxito si no puede realizar un número total de llamadas superior a 3 0 en el actual régimen de austeridad? Definición d e v a r i a b l e s : Xc : Cantidad de congresistas de la coalición. XQ : Número de congresistas de otro partido. Z

Función de maximización del éxito.

Modelo (Primal):

Con sus restricciones:

95

PROBLEMA

17

(Compras)

Una empresa requiere adquirir cuatro productos (1, 2, 3 y 4) y se conoce que hay tres compañías (A, B y C) que los procesan y los venden. La diferencia entre las compañías hace que los artículos se distingan por su calidad, es decir, probabilidad que sean menos defectuosos y sus precios:

Si se pretende tener una media no inferior a 8, 14, 23 y 15 unidades sin defecto de los productos 1, 2, 3 y 4 respectivamente. Si se desea minimizar el costo que se debe comprar. Variables reales: X¡¡ :

Cantidad de artículos i, i

{ 1 , 2, 3, 4 } que se comprarán en la empresa ¡, ¡

W :

Furyción de minimización de costos.

{A, B, C}

Modelo (Primal):

Sujeta a :

PROBLEMA

18 (Producción

de

tierras)

Un granjero tiene 1.000 hectáreas de terreno para cultivar próximamente y desea planificar tales cultivos; sabe que necesitará disponer de 3 0 0 toneladas de trigo y 2 7 0 toneladas de maíz para alimentar a su ganado, lo que puede obtener mediante su propia cosecha o por medio de compra en el mercado. Lo que produzca y que no se dedique a su ganado, lo puede vender; los precios de venta son $ 5 0 0 0 0 0 y $ 4 5 0 0 0 0 por cada tonelada de trigo y de maíz, respectivamente. Los precios de compra son un 35% superior debido a las ganancias de intermediarios y a los costos de transporte.

96

Otro cultivo posible es de la caña de azúcar, que se vende a $ 3 0 0 0 0 0 cada tonelada producida. Sin embargo, normas del Mercado Común Latinoamericano imponen una cuota máxima para la producción de azúcar, lo que conlleva a que cada tonelada de caña de azúcar producida sobre tal cuota tendrá un precio de venta de $ 1 0 0 0 0 0 ; para el próximo cultivo se espera que tal cuota sea de 4 0 0 0 toneladas. Basado en experiencias anteriores, el granjero conoce que la producción media es de 8, 5 y 4 toneladas por hectárea de trigo, maíz y caña de azúcar. El costo de cultivar una hectárea de trigo, maíz y caña de azúcar es de $ 3 0 0 0 0 0 0 , $ 3 8 0 0 0 0 0 y $ 4 3 0 0 0 0 0 . Se debe plantear un modelo de Programación Lineal que le ayude al granjero a maximizar sus beneficios.

V a r i a b l e s d e decisión: Ui

: Cantidad de hectáreas en las que cultivará trigo.

U2

: Número de hectáreas en las que sembrará maíz.

U3

: Cantidad de hectáreas en las que plantará caña de azúcar.

V-|

: Número de toneladas que comprará de trigo.

V2

: Cantidad de toneladas que comprará de maíz.

W]

: Número de toneladas que venderá de trigo.

W2

: Cantidad de toneladas que venderá de maíz.

W3

: Número de toneladas que venderá de caña de azúcar a $ 3 0 0 0 0 0 .

W4

: Cantidad de toneladas que venderá de caña de azúcar a $ 1 0 0 0 0 0 .

Z

: Función de maximización de utilidades.

M o d e l o (Primal):

Con sus restricciones:

97

PROBLEMA

19 (Contaminación

ambiental)

La gerencia de una planta termoeléctrica de generación de energía, que emplea carbón como combustible, está estudiando la configuración operativa de la planta a fin de cumplir con las nuevas leyes de contaminación ambiental; para esta planta, las tasas máximas de emisión son: máxima emisión de óxido de azufre 4 0 0 0 partes por millón (ppm), máxima emisión de partículas (humo) 10 kilogramos/hora (kg/hor). El carbón se traslada a la planta por ferrocarril y se descarga en depósitos cercanos a la misma; de aquí se lleva con una cinta transportadora a la unidad pulverizadora, donde se pulveriza y alimenta directamente la cámara de combustión, a la velocidad conveniente; el calor producido en la cámara de combustión, se utiliza para crear vapor, el cual impulsa las turbinas. Se emplean dos tipos de carbón: tipo A, que es un carbón duro y de quema limpia con un bajo contenido en azufre (bastante caro) y tipo B, que es un carbón barato, relativamente suave, que produce humo y tiene un alto contenido en azufre (ver tabla adjunta). El valor térmico en términos de vapor producido es mayor para el carbón A que para el carbón B, siendo de 2 6 0 0 0 y 18000 libras por tonelada respectivamente.

Carbón

Óxido de azufre en gases combustible

Partículas(emisión/ton)

A

1600 ppm

0,5 kg/ton

B

4 8 0 0 ppm

1 kg/ton

Como el carbón A es duro, la unidad pulverizadora puede manejar a lo sumo 1 8 toneladas de carbón A por hora; sin embargo, puede pulverizar hasta 22 toneladas de carbón B por hora. El sistema de carga de la cinta transportadora tiene una capacidad de 2 0 toneladas por hora y es independiente del tipo de carbón. Uno de los interrogantes que se plantea la gerencia es que dados los límites de emisión de los agentes contaminantes y los tipos disponibles de carbón. ¿Cuál es la máxima producción posible de electricidad de la planta que le permitirá a la gerencia determinar el margen de seguridad disponible para cubrir las demandas de energía? Definición d e v a r i a b l e s : XT : X2 :

Cantidad de carbón tipo A en toneladas utilizadas por hora en la quema . Número de toneladas de carbón tipo B en toneladas empleadas en una hora para quema.

Z

Función de maximización de producción.

Modelo (Primal):

SlBUOTcCA

^

Sujeta a : 1.

2.

0,5 X, + X2 < 10

- 1 - X 11 + —

18

22

X2 2 < 1

3.

1 6 0 0 — — — + 4 8 0 0 — - J — < 4000

4.

X, + X2

X-j + X2 <

X-| + X2

20

Resumiendo:

MAX Z = 2 6 0 0 0 X, + 1 8 0 0 0 X2

Con sus restricciones:

x2

<

10

+ 9X2

<

198

XT

+

X2

<

0

XI

+

x2

<

20

Xi, x 2

>

0

1.

0,5X,

2.

IIXT

3.

4.

- 3

PROBLEMA

+

20

(Mezclas)

Una destilería dispone de malta propia en cantidad de 3 0 0 barriles/día. Además, puede comprar malta de dos distribuidores, A y B con costos de $ 1 2 0 0 0 y $ 1 5 0 0 0 por barril, en cantidades máximas de 6 0 0 y 4 0 0 barriles/día, respectivamente. La malta puede mezclarse directamente o destilarse para producir malta enriquecida de dos tipos, 1 y 2. El destilador puede procesar a lo sumo 8 0 0 barriles / día. Un barril destilado de la propia casa produce 0,3 barriles de malta tipo 1 y 0,6 barriles de malta tipo 2; un barril de malta A produce 0,4 barriles de malta tipo 1 y 0,4 barriles de malta tipo 2; un barril de malta B produce 0,7 barriles de malta tipo 1 y 0,1 barriles de malta tipo 2. La mezcla de malta no procesada se vende a $ 1 6 0 0 0 el barril, limitándose el mercado a 150 barriles/día; el sobrante de malta debe destruirse con costo de $ 1 2 0 0 el barril; con las maltas destiladas pueden hacerse dos productos, uno de superior calidad (S) que se vende a $ 2 0 0 0 0 el barril y debe contener al menos el 60% de producto 1 y otro de baja calidad (B) que se vende a $ 1 5 0 0 0 barril y puede contener a lo sumo el 50% de producto 2.

99

La destilería desea satisfacer la demanda del producto de alta calidad, que es de 2 5 0 barriles por día y asegurarse un beneficio de $ 3 0 0 . 0 0 0 diarios; además, puesto que se espera un cambio en el mercado del producto de baja calidad, la destilería desea minimizar su producción. Formular un modelo de Programación Lineal que responda al problema de planificación planteado teniendo en cuenta las limitaciones en la producción y las exigencias de demanda y beneficio económico, suponiendo, además, que la venta de la mezcla está garantizada. Variables reales:

Modelo (Primal):

Sujeta a :

100

Resumiendo:

Con sus restricciones:

101

EJERCICIOS PROPUESTOS

Plantear cada uno de los problemas siguientes como un modelo de Programación Lineal:

1 * La Empresa Manizales tiene un programa estricto de compromisos de entrega de un producto para los próximos seis meses. El costo de producción varía por mes, por los valores anticipados en costos de materiales; la capacidad de producción de la compañía es de 100 unidades por mes con tiempo normal y hasta 15 unidades adicionales por mes con tiempo extra. El cuadro siguiente muestra los requerimientos de entrega y los costos de producción mensuales:

El costo de almacenar en inventario una unidad que no se vende es de $1.600 por mes. El problema de la Compañía es determinar el número de unidades que debe producir cada mes en tiempo normal y en tiempo extra para cubrir los requerimientos con el menor costo; la empresa no tiene unidades disponibles al iniciar el mes 1 y no quiere que sobren unidades al terminar el mes 6.

2 • La firma Punto Azul opera una serie de cafeterías para instituciones públicas; para cumplir con las exigencias del Gobierno, se deben satisfacer ciertos requerimientos nutricionales: la cantidad mínima de vitamina A en una comida debe ser de 1 mg, mientras que los requerimientos mínimos de vitamina C y D son de 5 mg y 10 mg respectivamente. Se exige que en dichas cafeterías, al desayuno, se sirvan huevos y tocino. Cada libra de tocino contiene 1 mg de vitamina A, 10 mg de vitamina C y 50 mg de vitamina D; cada docena de huevos contiene 10 mg de vitamina A, 10 mg de vitamina C y 10 mg de vitamina D. Una libra de tocino vale $1.800 y una docena de huevos cuesta $1.000. Adicionalmente, se estipuló que un desayuno no puede contener más de cuatro huevos, ni más de un tercio de libra de tocino, debido principalmente al tiempo de preparación. ¿Cómo estará compuesto el desayuno más barato y más nutritivo?

3 * Un inversionista tiene disponibles dos actividades, A y B, para el comienzo de cada uno de los años siguientes. Cada peso invertido en A al principio de un año, devuelve $1,4 (una ganancia de $4), dos años más tarde y a tiempo para una reinversión inmediata. Cada peso invertido en B al comienzo del año $1,7, tres años más tarde. 102

También tiene las inversiones C y D. Cada peso invertido en C al principio del segundo año produce $2 cuatro años más tarde. Cada peso invertido en D al comienzo del quinto año, retorna $1,3 un año más tarde. El inversionista empieza con $ 1000000 y quiere saber qué plan de inversiones maximiza la cantidad total de dinero que él puede acumular al principio del sexto año, contado desde hoy.

4 * La compañía aérea AVACSAM tiene que realizar las operaciones de mantenimiento sobre sus aviones que son: 9 Concordes, 10 Airbus, 14 Aeroplanos, 12 Hidroaviones y 15 Boeings 747 . Cada avión requiere unas operaciones específicas para su mantenimiento en el taller. Dadas las dimensiones de los aviones, sólo es posible trabajar simultáneamente sobre no más de tres aviones atendiendo a las siguientes posibles configuraciones del taller: Primera configuración: un Concorde, un Airbus y un Hidroavión; Segunda configuración: un Concorde, un Hidroavión y un Boeing 747; Tercera configuración: un Concorde, un Aeroplano y un Boeing 747; Cuarta configuración: un Airbus, un Aeroplano y un Hidroavión; Quinta configuración: un Airbus, un Aeroplano y un Boeing 747. Además, la cantidad de horas que requiere un avión viene dada por:

Se asume que el taller puede pasar de una configuración a otra sólo cuando se haya terminado de trabajar sobre sus aviones. El modelo matemático a plantear nos debe servir para configurar oportunamente el taller de manera que se minimice el tiempo total de mantenimiento de la flota.

5 « La empresa de colchones EL SUEÑO FELIZ produce un colchón ortopédico, el cual para su elaboración precisa de una serie de tareas ligadas por relaciones de precedencia; además, cada tarea requiere de un tiempo de ejecución dado en la siguiente tabla:

Determinar los instantes de comienzo de las tareas para disminuir el peso del tiempo total medio. 103

CAPÍTULO

IV

MÉTODOS LINEAL

DE

SOLUCIÓN

EN

PROGRAMACIÓN

"A veces pienso que la prueba más fehaciente de que existe vida inteligente en el universo es que nadie ha intentado contactar con nosotros". Bill Watterson

MÉTODO GRÁFICO Es limitado en el hecho de graficar como máximo tres variables. Consiste en representar cada una de las restricciones y encontrar cuando se pueda el polígono (poliedro) factible, comúnmente llamado la región factible, en la cual en uno de sus vértices se obtiene la solución óptima del problema, caso en el que la optimización se denomina solución óptima única. Además, las soluciones óptimas múltiples, no acotadas, infactibles, con ecuaciones redundantes. Es de anotar que los problemas de mayor dimensión tienen soluciones semejantes, pero la forma de resolverlos ya es de manera analítica.

Comentarios g e n e r a l e s acerca d e la O p t i m i z a c i ó n

La solución de un problema es óptima única cuando sólo existe un punto extremo del conjunto de soluciones factibles que hace posible encontrar el valor máximo de la función objetivo. La solución es óptima múltiple cuando existen varios puntos (un lado del poliedro de soluciones factibles) que hacen posible encontrar el máximo valor de la función objetivo. Es posible encontrar problemas en los cuales la solución óptima no toma ningún valor finito sino infinito. En modelos reales lo que sucede es un problema formulado incorrectamente; en estos casos se presentan utilidades bastante altas. Un problema tiene solución no factible cuando no es posible encontrar un espacio de soluciones factibles, por incompatibilidad de las restricciones o porque el espacio de soluciones se encuentra en un cuadrante diferente al primero (no se cumplen las condiciones de no negatividad).

Ejemplos 1) La Hilandería "Cordillera" produce dos tipos de tela, cada una varía en el proceso de fabricación. La tela de lujo requiere de 18 horas de tintura, 9 horas de estampado y produce una utilidad de $400 el metro; la tela estándar necesita 3 horas de tintura, 4 horas de estampado y produce una utilidad de $200 el metro; se dispone de 800 horas para tintura y 600 horas para estampado cada mes. 105

Se ha pronosticado que la demanda mensual para la tela de lujo no es más de 80 metros y de la tela estándar no es más de 150 metros. La gerencia desea saber el número de metros de tela de cada clase que debe producir la empresa para maximizar la utilidad total. Formule, resuelva e interprete las variables de este problema como un modelo de Programación Lineal. Definición de variables: X! : Cantidad de metros de tela de lujo a producir mensualmente. X2 : Número de metros de tela estándar a fabricar por mes. Z

: Utilidad total.

Modelo (Primal):

Solución gráfica: X2

106

Solución Óptima Única:

La solución analítica de éste problema se presenta en la página 118.

Con sus restricciones:

Resolver el anterior problema como un modelo de Programación Lineal

Solución gráfica:

Solución Óptima Múltiple (Alterna):

Solución Alterna 1:

Solución Alterna 2:

Sujeta a:

Solucionar el anterior problema como un modelo de Programación Lineal Solución gráfica:

108

Solución Óptima No Acotada o Ilimitada o Indeterminada.

Con sus restricciones:

Resolver el anterior problema como un modelo de Programación Lineal Solución gráfica:

Solución Infactible o No Factible o Sin Solución.

Sujeta a:

109

Resolver el anterior problema como un modelo de Programación Lineal Solución gráfica:

6) El administrador del sistema de suministro de agua del acueducto municipal debe encontrar la manera de proporcionar por lo menos 10 millones de galones de agua potable por día (mgd). El agua se debe tomar de los depósitos locales o de una tubería hacia una población vecina; los depósitos locales pueden suministrar como máximo 5 mgd. La tubería, debido a su tamaño, puede proporcionar un máximo de 10 mgd; además, debido a un cláusula contractual, debe bombear por lo menos 6 mgd. Por último, el costo del agua del depósito es de $300 por un millón de galones y el costo del agua de la tubería es de $500 por un millón de galones. ¿En qué forma puede el administrador minimizar el costo diario del agua? Variables de decisión:

110

Xt :

Cantidad de galones de agua potable a tomar de los depósitos locales para suministrar por día.

X2 :

Número de galones de agua potable a tomar de la tubería para proporcionar diariamente.

W :

Costos diarios.

Sujeta a:

Resolver el anterior problema como un modelo de Programación Lineal Solución gráfica:

Solución Óptima Única:

Sujeta a:

Resolver el anterior problema como un modelo de Programación Lineal

Solución gráfica:

(2,0,0) (2,406/175,141/175) (2,20/7,0)

Solución Óptima Única:

112

^on sus restricciones:

Solución gráfica: X, (0,0,30) X,+2XJ+X3=30

X1+2X2+X3=20

•

X,

Solución Óptima Única:

El problema general de Programación Lineal se puede plantear de la siguiente manera (matricialmente):

Sujeta a:

Nota: La OPT (optimización) puede corresponder a un problema de MAX (maximización) o a un problema de MIN (minimización).

113

El anterior modelo se escribe en una tabla:

Donde Cj :

Coeficiente de las variables básicas.

X¡ :

Variables básicas.

Cj :

Coeficientes de las variables básicas y no básicas.

S¡ :

Variables de holgura (relleno).

Sj :

Variables de superávit (exceso).

An :

Variables artificiales.

B¡ :

Disponibilidad de recursos.

Z :

Valor de Z (W)

METODOS ANALITICOS Por medio de estos métodos se resuelven problemas de Programación Lineal sin importar el número de variables y/o restricciones, es decir, son modelos que nos permiten solucionar problemas más cercanos a la realidad. Entre otros, los más utilizados son:^Simplex, Dual-Simplex, Khachian, Karmarkar, Métodos Matriciales, Método Simplex Revisado, Método de las Dos Fases, Perturbación de Chames, Descomposición de Dantzig-Wolfe, Descomposición de Benders, Método Simplex Generalizado. A l g o r i t m o Simplex Fue creado en 1947 y se le atribuye a George Bernard Dantzig (Estados Unidos) y Leonid Vitalievich Kantorovich (Rusia). Con este algoritmo se resuelven problemas de m restricciones y n variables; las restricciones pueden ser >, < o = y m con respecto a n puede ser >, < 0 =. El número de soluciones básicas factibles es menor o igual a:

SOLUCION N°

X,

x2

s,

s2

S3

s4

FUNCION OBJETIVO

1

0

0

800

600

80

150

0

2

0

266,6

o

-466,6

80

919,6

NF

3

0

150

350

0

80

0

30000

4

44,4

0

0

200

35,6

150

17777,7

5

66,6

0

-400

0

13,4

150

NF

6

31,1

80

0

0

48,9

70

28444,4

El algoritmo simplex, usando el criterio del peor caso, está clasificado como un algoritmo de complejidad de tipo exponencial, es decir, que el tiempo de terminación del método simplex puede llegar a crecer exponencialmente en términos del problema a resolver. El simplex necesita a lo sumo 2n - 1 iteraciones para encontrar la respuesta (n es el número de variables). Cuando se aplica este algoritmo a la solución de un problema de Programación Lineal en la forma estándar, se encuentra normalmente una solución óptima después de examinar menos de 3m soluciones básicas factibles. Recientemente se encontró que este método examinó un promedio de 2m soluciones básicas factibles, antes de encontrar la solución óptima (m es el número de restricciones). Sin embargo, este algoritmo se emplea todavía en la actualidad porque realiza análisis post -óptimo con las variables que intervienen en la solución del problema.

115

Problema de Maximización • Criterio de entrada de variables a la base: MIN Cj, C¡ < 0 en la función objetivo. Para nuestro caso (página 106), las candidatas en el tablero 1 a entrar a la base son ( - 400, - 200), tomamos la variable que más se aleja de cero por la izquierda, es decir, - 400 que corresponde a la variable X], Cuando hay empate entre variables a entrar a la base, se prefieren las variables reales (decisión); cuando el empate es entre variables de la misma naturaleza se rompe arbitrariamente. • Criterio de salida de variables de la base: MIN B¡/A¡s i = 1,2,...,m; Ais > 0; s: subíndice de la posible variable a salir de la base. En nuestro ejemplo (página 106) , las variables opcionadas a salir de la base son: (800/18, 600/9, 80/1) = (44.4, 66.1, 80), escogemos la variable X 3 que es aquella que menos se aleja de cero por la derecha y es 44.4. Cuando hay empates entre variables a salir de la base, se recomienda escoger las variables diferentes a las de decisión, o sea, artificiales, de exceso o de holgura; cuando el empate se da entre variables de igual clase, se rompe al azar. En los casos de empate de la variable de salida de la base, la(s) variable(s) que queda(n) en la base en el tablero siguiente, forman una solución que se denomina degenerada, porque dicha variable toma el valor de cero en la base; si tal variable se toma para salir de la base, antes que su valor cambie, la variable básica entrante correspondiente también deberá permanecer en cero y el valor de Z no cambiará.

Problema de Minimización Para resolver un problema de minimización, se puede aplicar cualquiera de los dos (2) procedimientos siguientes:

Procedimiento 1: Escribir el negativo de la función objetivo y resolver el problema como uno de maximización, es decir, para cualquier función f(x) todo punto que minimice a f(x) maximizará también a - f(x). Procedimiento 2: Conserve la minimización; cuando se presentan variables artificiales estas deberán aparecer en la función objetivo con el coeficiente +M. Se escoge como variable de entrada a la base aquella que más se aleja de cero por la derecha y la variable de salida es igual que en caso de maximización, la que menos se aleja de cero por la derecha. • Criterio de entrada de variables a la base: MIN Cj, Cj > 0 en la función objetivo. Para nuestro caso (página 126), las candidatas en el tablero 1 a entrar a la base son ( - 1,-1, 4), tomamos la variable que más se aleja de cero por la derecha, es decir, 4 que corresponde a la variable X3. Cuando hay empate entre variables a entrar a la base, se prefieren las variables reales (decisión); cuando el empate es entre variables de la misma naturaleza se rompe arbitrariamente.

116

• Criterio de salida de variables de la base: MIN Bj/Ais i = 1,2,...,m; Ais > 0; s: subíndice de la posible variable a salir de la base. En nuestro ejemplo (página 126), las variables opcionadas a salir de la base son: (9/2,2/- 1,4/1) = (4.5,/-2,4), escogemos la variable X 3 que es aquella que menos se aleja de cero por la derecha y es 4. Cuando hay empates entre variables a salir de la base, se recomienda escoger las variables diferentes a las de decisión, o sea, artificiales, de exceso o de holgura; cuando el empate se da entre variables de igual clase, se rompe al azar. El valor que queda interceptado entre la columna de entrada y fila de salida se llama pivote. La rutina de cálculo para pasar de un tablero a otro es la siguiente: La variable de entrada a la base (columna) se recalcula como uno en el elemento pivote y en las demás posiciones cero. La variable de salida de la base (fila) para el tablero siguiente divide cada una de sus celdas entre el pivote. Los demás elementos se recalculan mediante la aplicación de la siguiente fórmula:

Donde: DN DA Pi y EP

: Dato nuevo. : Dato antiguo. : Proyecciones. : Elemento pivote.

Para nuestro ejemplo, al pasar del tablero 1 al tablero 2: Celda (X 5 ,b)

DN = 80 - (800*1)/18;

DN = 320/9

Se ha llegado a la solución óptima de un problema de Programación Lineal cuando todos los elementos del renglón de evaluación neta (Cj - Zj) son cero o negativos para el problema de maximización y cero o positivos para el problema de minimización.

Clases d e solución Los principales tipos de solución: • Óptima Unica: Se da cuando sólo existe un punto extremo del conjunto de soluciones factibles que hace posible encontrar el valor óptimo de Z, es decir, si solamente los costos relativos C; - Z; de los vectores básicos son cero.

117

• Óptima Múltiple (Alterna): Se presenta cuando si habiéndose satisfecho los criterios de optimalidad, los costos relativos Cj - Z de algún vector no básico aparece a nivel cero. • No Acotada o Ilimitada o Indeterminada: En cualquier iteración del procedimiento simplex, si el vector que debe salir de la base se llama a s y todas las correspondientes a¡s < 0 para i = 1,2,...,m esta solución se llama ilimitada. • Infactible o No Factible o Sin Solución: Se presenta cuando en el tablero óptimo queda una variable artificial en la base. • Degenerada (Degradada): Se da cuando en un tablero del Simplex una variable básica toma el cero en lugar de un valor positivo; este caso se presenta normalmente cuando se escoge arbitrariamente una variable para salir de la base cuando hay empate entre algunas variables. • Ecuaciones Redundantes: Se presenta cuando en un problema al graficarlo es posible hacerlo sólo con una parte de las ecuaciones, es decir, que el resto de ecuaciones sobran. Es de advertir que cuando el empate entre las variables es cero, se conduce al caso llamado ciclaje, el cual consiste en que después de varias iteraciones a partir de una solución, se regresa nuevamente a la misma solución. Soluciones Analíticas 1) La Hilandería "Cordillera" produce dos tipos de tela, cada una varía en el proceso de fabricación. La tela de lujo requiere de 18 horas de tintura, 9 horas de estampado y produce una utilidad de $400 el metro; la tela estándar necesita 3 horas de tintura, 4 horas de estampado y produce una utilidad de $200 el metro; se dispone de 800 horas para tintura y 600 horas para estampado cada mes. Se ha pronosticado que la demanda mensual para la tela de lujo no es más de 80 metros y de la tela estándar no es más de 150 metros. La gerencia desea saber el número de metros de tela de cada clase que debe producir la empresa para maximizar la utilidad total. Formule, resuelva e interprete las variables de este problema como un modelo de Programación Lineal.

Definición de variables: Xj : Cantidad de metros de tela de lujo a producir mensualmente. X2 : Número de metros de tela estándar a fabricar por mes. Z : Utilidad total. Modelo (Primal): MAX Z = 400 X, + 200 X 2

118

Sujeta a:

A. Estandarizar el modelo: Consiste en colocar las inecuaciones en forma de ecuaciones, utilizando para este caso variables de holgura (relleno): Estandarización:

Las variables X] y X 2 aparte del nombre original (variables de decisión) se denominan variables no básicas y las variables S b S 2 , S 3 y S 4 que originalmente se llaman variables de holgura en la estandarización se denominan variables básicas. Este nombre lo reciben por el sitio en el que se encuentran ubicadas. B. Establecer el canónico del sistema: Buscar que en el sistema en cada ecuación una variable tenga coeficiente +1 y en las demás ecuaciones 0 (tratar de formar la matriz identidad); si todas las inecuaciones son de la forma inmediatamente nos queda conformado el canónico. C. Las variables que forman el canónico pasan a ser las variables dependientes del sistema (variables básicas); las otras son las variables independientes del sistema (variables no básicas). El modelo se desarrolla a través de entrada de variables a la base y salida de variables de la base, es decir, intercambio de variables, una en cada iteración. A continuación solucionaremos este problema por medio del algoritmo simplex:

119

TABLERO4DUALSIMPLEX

Entra a la base Xj, sale de la base Sj VB 51 = 800 5 2 = 600 S 3 = 80 S 4 = 150

VNB Xj = 0 X2 = 0

Z= 0

TABLERO 2 CB 400 0 0 0

VB X, S2 S3 s4 z

b 400/9 200 320/9 150 160000/9

X

0 0 0 0 0

SIMPLEX

X 1/6 5/2 -1/6 1 -400/3 t

s,

1/18 -m

-1/18 0 200/9

Entra a la base X2, sale de la base S2

X! 52 53 54

VB = 400/9 = 200 = 320/9 = 150

VNB S, = 0 X2 = 0

Z = 160000/9

TABLERO 3

Entra a la base Sj, sale de la base S 4

120

SIMPLEX

S2 0 1 0 0 0

S3

0 0 1 0 0

S4 0 0 0 1 0

CB 400 200 0 0

VB X, x2 S3 S, z

b 0 150 80 350 30000

X, 1 0 0 0 0

X, 0 1 0 0 0

S, 0 0 0 1 0

s, 1/9 0 -1/9 -2 400/9

s3 0 0 1 0 0

s4 -4/9 1 4/9 5 200/9

Solución Óptima Única:

Con sus restricciones:

Resolver el anterior problema como un modelo de Programación Lineal Solución Analítica Forma Estándar

121

TABLERO4DUALSIMPLEX

TABLERO 2

SIMPLEX

No hay quién entre a la base (Forzamos a la variable X 2 a entrar a la base)

Solución Óptima Múltiple (Alterna): Solución Óptima 1:

X 2 = 0 indica Solución Óptima Múltiple (Alterna)

TART F R O 3

SIMPLEX

No hay quién entre a la base (Si quisiéramos observar que ocurre podríamos forzar a entrar a la base a S 2 y a salir de la base la variable X 2 (Tablero 2)) 122

Solución Óptima 2:

3) MAX Z = 12 X, + 12 X 2 Sujeta a:

Solucionar el anterior problema como un modelo de Programación Lineal Solución Analítica Estandarización

TABLERO 1

SIMPLEX

Entra a la base X2, sale de la base Si

123

TABLERO4DUALSIMPLEX

Entra a la base X b sale de la base S 2

TABLERO 3

SIMPLEX

Entrada a la base Si, no hay variable de salida, lo cual conduce a una Solución Optima No Acotada o Ilimitada o Indeterminada para el problema de maximización. Para un modelo de minimización la solución óptima se encuentra en uno de los vértices del polígono (poliedro).

Con sus restricciones:

Resolver el anterior problema como un modelo de Programación Lineal Solución analítica: Forma estandar se agrega una nueva función objetivo Min W = Y¡ o lo que es igual Max - W = - Y) con lo cual, restada de la ecuación (2) nos permite conformar el Tablero Simplex.

124

TABLERO 1

SIMPLEX

Entra a la base X2, sale de la base S ¡

TABLERO 2 SIMPLEX

No hay variable candidata de entrada Y, permanece en base. Por lo tanto, no hay Solución Factible o Solución Infactible o No Tiene Solución.

Con sus restricciones:

125

r

Solución Analítica Estandarización: 1.

X! + X 2 + 2 X 3 + S ,

=

9

2.

X! + X 2

-X3

=

2

3.

- X , + X2

+X 3

+ S3 =

4

+ S2

0. W - X t - X 2 + 4 X 3

= 0

Solución analítica:

TABLERO 1 SIMPLEX

CB 0 0 0

VB

s, S2 S, w

Q b 9 2 4 0

1 X, 1 1 - ] -1

1 X 1 1 1 -1

0 S, 1 0 0 0

-4 x3 .2 -1 1

4

0

0

S2

S3

0 1 0 0

0 0 1 0

Entra a la base X3, sale de la base S3 VB

VNB

S,= 9 S2= 2

X, = 0

S3=

4

x2 = 0 x3 = o TABLERO 2 SIMPLEX

CB 0 0 - 4

VB S, S2 X3 w

b 1 6 4 - 16

X, 3 0 - 1 3

Entra a la base Xj, sale de la base S!

126

VB

VNB

S, = 1 S2 = 6 X3 = 4

x, = o X2 = 0 X3 = 0

W = - 16

x2 - 1 2 1 -5

x3 0 0 1 0

Si 1 0 0 0

S2 0 1 0 0

S3 -2 1 1 -4

TABLERO 3 SIMPLEX

Solución Óptima Única:

5) MIN W = 8 X, + 5 X 2 + M A, + M A 2 Sujeta a:

Solución analítica: Estandarización

I:

Estandarización

III:

TABLERO 1 SIMPLEX

CB M M

VB A, A2 w

C, b 100 20 120 M

8

5 X2 4 ^ 2 0 1 4 M- 8 3 M-5

0 SI -1 0 -M

Entra a la base X) y sale de la base A]

TABLERO 2

SIMPLEX

Entra a la base X 2 y sale de la base A 2

TABLERO 3 SIMPLEX

128

0 S2 0 -1 - M

M A, 1 0 0

M A2 0 1 0

Solución Óptima Única:

OTROS PROBLEMAS EMPLEANDO SIMPLEX

Sujeta a

Forma estándar I:

Estandarización

II:

Notas: 1. La variable + S, se llama de holgura (relleno), la variable - S 2 se denomina de superávit (exceso) y la variable + Aj se llama artificial. 2. En la estandarización II al aparecer la variable artificial con el objeto de resolver el problema se debe reflejar en la función objetivo multiplicada por M (constante de valor alto), sumada o restada a la función objetivo según el problema sea de minimización o de maximización, lo cual se hace para que el problema se pueda optimizar. El anterior método se denomina de la Gran M. 129

Forma estándar III:

La ecuación 0' se obtuvo de la siguiente manera: 0 - 2*M.

TABLERO 1 SIMPLEX 3 X, 2 1 -M -3

Ci CB 0 - M

VB Si A, Z

b 6 2 -2 M

0 s. 1 0 0

-2 x2 3 - 1 M+ 2

0

-M

S2 0 -1 M

A, 0 1 0

Entra a la base la variable X! y sale de la base la variable Aj. La columna correspondiente a la variable artificial se puede borrar sin ningún problema. VB

VNB

S, = 6

X, = 0

Ai = 2

X2 = 0

W=- 2M

S2 = 0 TABLERO 2 CB 0 3

VB s, X, z

b 2 2 6

X, 0 1 0

SIMPLEX x2 5 - 1 - 1

Pasa a ser variable básica S 2 y se convierte en variable no básica S¡. t VB S,= X,=

130

VNB 2

X2 = 0 2

S2 = 0

W=6

S, 1 0 0

S2 2 -1 -3

TABLERO4'DUALSIMPLEX

Solución Óptima Urtica:

Con sus restricciones:

Forma estándar I:

Forma estándar II:

Forma estándar III:

131

TABLERO4'DUALSIMPLEX

CB -M -M

VB

A, A2 Z

Ci b 10 12 -22 M

1 X, 1 1 -2 M- 1

1 X2 2 - 2 - 1

2 x3 1 1 - 2M —2

0 s, 0 -1 M

-M

-M

A,

A2

1 0 0

0 1 0

Entra a la base la variable X 3 y sale de la base A]

VB

VNB

A, = 10 A2 = 12

X, = 0 X2 = 0

W = - 22 M

X3 = 0 S, = 0

TABLERO 2

SIMPLEX

Solución Infactible o Solución No Factible o No Tiene Solución, ya que hay una variable artificial en la base.

A l g o r i t m o Khachiyan

Siguiendo cronológicamente, en 1979 el ruso L. G. Khachiyan presentó un algoritmo para resolver problemas de Programación Lineal denominado algoritmo del elipsoide de Shor. El algoritmo polinómicotemporal para determinar una solución (en caso de existir), el cual consiste en ir reduciendo la región de factibilidad encerrándola en elipsoides de volúmenes decrecientes; dicho algoritmo analiza el conjunto abierto de desigualdades S = { x: Gx < g }, en donde G es una matriz de r*q, r y q > 2 , G y g tienen todas sus componentes enteras, donde 1 es un vector renglón de r unos y

132

El algoritmo define una esfera en E p con centro en el origen y radio suficientemente grande para abarcar un volumen grande de S cuando S no es vacío; si el centro de esta esfera está en S el algoritmo termina. En caso contrario se construyen una serie de elipsoides que decrecen monótonamente en volumen, aunque todos contienen la región de S que fue capturada por la esfera inicial. El resultado principal establece que si S es no vacío, entonces el centro de algún elipsoide estará en S en el transcurso de algún número de iteraciones acotado por encima por un polinomio en el tamaño del problema. El algoritmo del elipsoide es un algoritmo simple, de complejidad de tipo polinómico, usando también el criterio del peor caso, sólo que se comprobó, usando simulación, que el tiempo estimado de terminación del método del elipsoide era no sólo obtenido en el peor de los casos, sino en casi todos los casos. Telgen, en su estudio, en lugar de analizar el número de iteraciones por problema hace un análisis del número de operaciones por iteración y obtiene: Simplex:

(3 + d) m2 + dmn

Khachian:

(3 + d) n2 + dmn

Donde d: densidad de la matriz de coeficientes tecnológicos; m: número de ecuaciones y n: número de variables. De los trabajos de Telgen se puede concluir que el algoritmo de L.G. Khachiyan es atractivo solamente en problemas en los que el número de restricciones es mayor que el número de desigualdades, pero en ese caso puede ser más indicado la utilización del algoritmo simplex dual.

Algoritmo d e K a r m a r k a r El Hindú Narendra Karmarkar en 1984 de AT&T Bell Laboratories presentó un algoritmo de tipo polinómico, el cual lleva su nombre. Dicho método converge a una solución óptima al moverse a través de la región factible (pero que no realiza análisis post-óptimo). El algoritmo de Karmarkar ha resultado ser hasta cien veces más rápido que el método Simplex, especialmente en problemas con miles de variables y/o restricciones. El tiempo exponencial de convergencia se debe a Klee, Minty y Chvátal en problemas del tipo:

Sujeta a:

133

Estos problemas tienen 2n puntos extremos y es un algoritmo basado en ideas de Programación No Lineal y Geometría Proyectiva.

Método del Escalado Proyectivo de Karmarkar La forma básica del problema de Programación Lineal en la que Karmarkar basa su método es la siguiente:

Sujeta a:

Donde e = [1, 1, 1, ...,1]T. También se supone que Ae = 0, por lo que el punto e/n es factible y que el óptimo de (1) es cero. Las condiciones de optimalidad del problema (1) implican que:

donde es el vector de multiplicadores de Lagrange de las condiciones de no negatividad de (1); las condiciones de complementariedad de holguras en el óptimo, x+, también implican que :

Tomando el producto interior del vector c y x+ y usando las relaciones de las dos expresiones anteriores se obtiene que z e T x + = 0; como las condiciones del problema hacen e T x+ = 1, lo cual quiere decir que z = 0. El problema dual de (1) es:

Ejemplo: Resolver el siguiente problema de Programación Lineal aplicando el algoritmo de Karmarkar:

Con sus restricciones:

134

Solución gráfica:

Iteración 1 Partimos de un punto factible xO; la matriz X, = diag (1/3,1/3,1/3); como

, la

transformación proyectiva es . El problema en el espacio x coincide con el de la figura adjunta; el punto se transformará en él mismo.

La dirección d nos lleva desde

(1/3,1/3,1/3) t hacia la solución óptima (2/3,0,1/3)T. El nuevo punto en el espacio es: x = e/ n + ord/(n d )

0,4119 0,2548 ; W = 0,2548 0,3333

3 3 V2

Iteración 2 La matriz X 2 = diag( 0,4119 0,2548 0,3333) 0 0,2548 0

d = - (I -

B

0,4119 0,2548 -0,6666 1 1 1

Á= [0,4119 0,2548 -0,6666]; B

T

(B

t

B )

0,1243 d = -0,1455

B) c ;

= 0,1925;

0,0212

x

(2)

=

0,4828 0,1838 0,3333

0,4051 x — 0,2494 0,3456

; W = 0,1838

Iteración 3 y sucesivas Los nuevos puntos obtenidos son: "0,5397" X = 0,1270 0,3333 3

4

x =

"0,5815 0,0852 0,3333

;

Solución Óptima Única: X* = 2/3; X^=0; x ; = l/3;W* = 0.

136

10

x

"0,6604" = 0,0063 ; 0,3333

"0,4051" X = 0,2494 0,3456 20

V a r i a n t e s y Extensiones del M é t o d o d e K a r m a r k a r Algunos autores han desarrollado extensiones al método de Karmarkar a fin de poder tratar el problema de Programación Lineal en forma estandar. Las ideas propuestas se basan en que si se tiene una solución estrictamente factible x del problema MIN W = c T x Sujeta a: Ax=0

(3) donde g ^ 0 un múltiplo escalar de x será factible en el problema MIN W = ( c - z g ) T x Con sus restricciones: A x = 0 eT x = 1

Si, además, z es el valor óptimo de la función objetivo del problema (3), un múltiplo escalar de ese óptimo lo será de (4). Las ideas del método de Karmarkar se pueden aplicar al problema (4) cuando se reduce convenientemente una función potencial para un z dado; en cada iteración z es un límite inferior del valor óptimo de la función objetivo de (3) correspondiente a una solución dual factible; estos límites se adaptan de vez en cuando.

El Método del Escalado Afín Una de las dificultades que presenta el algoritmo de Karmarkar se encuentra en la transformación proyectiva; una manera de evitarlo es emplear transformaciones afines en lugar de proyectivas, dando lugar así a algoritmos del escalado afín, incluso algunos de ellos enunciados antes de la aparición del trabajo de Karmarkar. El problema que suscitan estos escalados es que no se ha podido probar que su tiempo de resolución sea polinómico.

137

RESUMEN

VALOR DE LA FUNCIÓN OBJETIVO TIPO DE RESTRICCIÓN

MAXIMIZAC1ÓN

Variable de holgura toma un 1. — Necesita sumarse una variable coeficiente cero (0) en la función de holgura (relleno). objetivo.

MINIMIZACIÓN Variable de holgura toma un coeficiente cero (0) en la función objetivo.

2. 5 Requiere restar una variable de exceso (superávit) y sumar una variable artificial positiva.

Coeficiente cero (0) para la variable Coeficiente cero (0) para la variable de exceso y + M para la variable de exceso y - M para la variable artificial. artificial.

3. = Necesita variable artificial positiva.

Coeficiente + M en la función objetivo para la variable artificial.

Coeficiente - M en la función objetivo para la variable artificial.

SOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL EN FORMA MATRICIAL Existen varias maneras de resolver un problema de Programación Lineal en forma matricial. Inicialmente aplicaremos el Método de Gauss-Jordan y luego emplearemos el método de la matriz inversa. Método de Gauss-Jordan Para resolver un sistema de m ecuaciones con n incógnitas se procede de la siguiente manera: • Se forma la matriz ampliada del sistema B = (A|b), donde A es la matriz de los coeficientes y b indica la matriz de los términos libres. • Al aplicar operaciones elementales entre filas (columnas) la matriz B se lleva a una matriz equivalente C, donde C es una matriz escalonada reducida. • Como la matriz B es equivalente a la matriz C, entonces el sistema de ecuaciones que representa la matriz B es equivalente al sistema de ecuaciones que representa la matriz C y en esta matriz es fácil encontrar las soluciones. Nota 1: Las operaciones elementales entre filas (columnas) corresponden a: - Intercambiar dos filas (columnas). - Multiplicar una fila (columna) por un número diferente de cero (0). - Añadir a una fila (columna), c veces una fila (columna) diferente.

138

Nota 2: Una matriz escalonada reducida es aquella donde el número de ceros que precede al primer elemento diferente de cero de una fila, aumenta fila a fila, hasta tener posiblemente filas de sólo ceros. Además, el primer elemento no nulo de cada fila no nula es uno (1) y éste es el único elemento diferente de cero (0) que se encuentra en la respectiva columna. Ejemplo: MAX Z = 2 X, + 3 X 2 + X 3 + 4 X4 Sujeta a:

Solución matricial: Luego del trabajo matricial se llega a:

Solución Óptima Única:

M é t o d o d e la M a t r i z Inversa Uno de los métodos más empleados para encontrar la inversa de una matriz es el siguiente: • Formar una matriz compuesta así: A la izquierda de la línea | van los elementos de la matriz conocida y a la derecha, la matriz idéntica. • Se efectúan operaciones elementales entre filas (columnas), hasta que la matriz idéntica quede a la izquierda. • La matriz que queda a la derecha de la línea es la matriz buscada. Ejemplo:

139

MAX Z = 3 X, + 2 X 2 + 4 X 3 Sujeta a:

A X = b En notación matricial, la solución es:

Solución matricial:

140

Luego del trabajo matricial se llega a:

Solución Óptima Única:

Método Simplex Revisado (Forma Matricial)

El método del simplex expuesto, que se denomina básico, se desarrolla a través de cada iteración transformando completamente una sucesión de tableros al ir cambiando de base. Teniendo en cuenta que muchos de estos cálculos no hacen falta para la determinación de cada nueva base y basados en el algoritmo del simplex revisado, el cual es realmente un esquema de ordenación de los cálculos que se llevan a cabo con el método del simplex básico, prescindiendo y evitando aquellos que sean innecesarios en relación con la solución final del problema. El inconveniente de este método es que por la forma en que se lleva a cabo induce más fácilmente a errores en los cálculos a mano que el simplex básico, aspecto que evidentemente no ocurre si está implementado en computador. En el método del simplex revisado partimos, como en el básico, del problema lineal en forma estándar: 141

M A X

Z = cT x

Sujeta a:

Dada la base factible B, hay que evaluar si alguna variable no básica Xj puede entrar a la base para mejorar la función objetivo; para ello utilizamos el costo reducido:

El vector c B está formado por los coeficientes de la función objetivo de las variables y B a¡ representa el vector a¡ en términos de la actual base. El método del simplex revisado no cambia los vectores y¡ en cada tabla como el básico, sino que utiliza siempre el vector a¡ inicial con los multiplicadores del simplex:

que si cambian con la base. Es claro que se alcanza una solución óptima cuando:

La selección de la variable de salida se hace con el mismo criterio que en el simplex básico: si Xk es la variable seleccionada para entrar a la base, la columna pivote es B 1 a^ y los valores actuales de las variables básicas B 1 b. Se aplica la regla de la mínima razón a estos elementos, quedando así determinada la variable X r que sale de la base. Finalmente, la nueva matriz básica B se obtiene sustituyendo la columna ar por la ak en la anterior matriz B. Ejemplo:

Con sus restricciones:

Resolver el anterior problema de Programación Lineal aplicando el Método Simplex Revisado. Solución analítica: Agregamos variables de holgura X 4 y X 5 a cada restricción con coeficientes cero (0) en la función objetivo para tener el problema en la forma estándar; la base inicial B y el vector c B son:

142

El valor que más se aleja de cero (0) por la izquierda es Z3 - C3: X 3 es la variable que entra a la base; la razón mínima es 8/2, luego S 2 es la variable que sale de la base. Las variables básicas son ahora (S 1; X 3 ) con matriz básica (sustituyendo a 5 por a3):

C B = (0 3);

S = (0, 3/2) y los indicadores de las variables no básicas son:

Z, - C, = 3/2 - 2 = - 1/2; Z 2 - C 2 = 9/2 - 1 = 7/2; Z 3 - C 3 = 3/2 - 0 = 3/2 y X, es la variable que entra a la base; para determinar la variable de salida calculamos: B 1 b = (3,4) y B 1 aj = (5/2,1/2); la razón mínima es 6/5, luego X 4 es la variable que sale de la base. Las variables básicas son ahora (Xj, X 3 ) y la nueva matriz básica (reemplazando en la anterior a 4 por a 0 es:

c B = (2 3);

s = (1/5, 7/5) y los indicadores de las variables no básicas son:

Z 2 - C 2 = 2 3 / 5 - 1 = 18/5; Z 4 - C 4 = 1/5 - 0 = 1/5; Z5 - C 5 = 7/5 - 0 = 7/5 y al ser todos positivos se ha alcanzado la optimalidad. La solución óptima es: XB = ( X 1 , X 3 ) = B - , b = ( L 2 , 3 . 4 )

Solución Óptima Única:

143

M é t o d o d e l a i d o s fases

Este método elimina el uso de la M y resuelve el problema en dos fases. En la fase I se utiliza el algoritmo simplex para suministrar a la fase II una forma factible de partida. Es decir, el producto final de la Fase I es una solución básica factible (en caso de que exista), en forma típica, para iniciar la Fase II del método. Los pasos de cada fase son los siguientes: Fase I 1. Utilice el algoritmo simplex para obtener la minimización de la suma de las variables artificiales, sujeta a las mismas restricciones del problema original, independientemente de si este problema original es de maximización o minimización. 2. Si la suma de las variables artificiales, x0, es mayor que cero, entonces no existe una solución básica factible y se termina el proceso. Si x0= 0, entonces inicie la Fase II del algoritmo. Fase II 1. Utilice la solución óptima obtenida en la Fase I como solución de partida al problema 1. original, remplazando la función objetivo original Z por la de xo- Como es usual, la función objetivo original debe ser expresada en función de las variables no básicas. Si al final de la Fase I las variables artificiales son no básicas, se eliminan de la Fase II. Si alguna variable artificial es básica, pero a un nivel cero, esta variable se mantiene en el conjunto de variables básicas, pero debe garantizarse que su valor nunca será mayor que cero durante la ejecución de la Fase II. Ejemplo:

Sujeta a:

Resolver el anterior problema de Programación Lineal por el Método de las Dos Fases.

Solución analítica:

Paso 1: Se introducen las variables artificiales A] yA 2 , las variables de exceso Si y S2.

144

Con sus restricciones:

Fase I Puesto que A) y A 2 son variables básicas, sus coeficientes en la fila Xo deben ser cero (0); para ello sumamos las filas (1) y (1) a la fila (0). El tablero inicial para la aplicación del algoritmo simplex es:

TABLERO 1

SIMPLEX

Entra a la base X 2 y sale de la base A2 VB A] = 20 A2 = 30

VNB X, = 0 X2 = 0 S, = 0 S2 = 0

X 0 = 50

TABLERO 2

SIMPLEX

Entra a la base Xj y sale de la base A! VB

VNB

A! = 2

Xi = 0

X2 = 6

A2 = 0 S, = 0 S2=0

X0 = 2

145

TABLERO4'DUALSIMPLEX

Al aplicar el método simplex a nuestro problema en la tercera etapa de la fase I se ha encontrado que mín X 0 = 0 y no existen variables artificiales en la base. Por lo tanto, se ha encontrado una solución básica posible al problema original. Fase II Empleamos la función objetivo original W en lugar de Xo y eliminamos las variables artificiales A] y A2, puesto que ya no son variables básicas, es decir, son variables no básicas. Como la función objetivo debe estar expresada en términos de las variables no básicas, entonces se deben realizar transformaciones para reducir a cero el coeficiente de X| y X 2 en la función objetivo.

TABLERO 4

SIMPLEX

Entra a la base S2 y sale de la base Xi VB

VNB

X, = 10/7

S[ = 0

X] = 40/7

S2 = 0

X 0 = 190/7

TABLERO 5

Solución Óptima Única:

146

SIMPLEX

Otros t e m a s en P r o g r a m a c i ó n Lineal

Degeneración en Programación Lineal

En el desarrollo del método Simplex, cuando existe una solución básica factible (no óptima), con el conjunto de restricciones y sin degeneración, es posible ir combinando sucesivamente un vector de la base para obtener una solución óptima. La degeneración se genera cuando una variable básica es cero y se da cuando hay empate al determinar la variable que sale; si posteriormente se llega a un tablero que ya se tenía, se utiliza el Método Lexicográfico, que consiste en acordar sacar otra variable diferente a la que salió para destruir el loop (ciclo). En términos geométricos, la degeneración ocurre cuando un vértice está definido por demasiadas restricciones. En los problemas en que se presenta degeneración, la función objetivo es posible que no cambie cuando se pasa de una solución factible básica a otra, lo que nos indica que podemos estar en una situación de ciclaje, repitiendo indefinidamente la misma secuencia de bases. Existe otro método para evitar el ciclaje, conocido como la Regla de Robert Bland, la cual es muy elemental; para entrar a la base se toma la de menor índice y para salir de la base, del empate se elige también la de menor índice. En las aplicaciones de la Programación Lineal el problema de ciclaje raras veces se presenta, a pesar que la degeneración es un fenómeno bastante frecuente. En general, se conocen dos métodos para resolver el problema de la degeneración: Método de Perturbación de Chames y el Método Simplex Generalizado.

Método de Perturbación de Chames Para el problema general de Programación Lineal, se desea perturbar el problema de tal manera que nos aseguremos que para cualquier posible base admisible la solución correspondiente será no degenerada. Por lo tanto, este Método de Perturbación de Chames es un procedimiento para justificar la suposición de no degeneración del Método Simplex. Ejemplo:

MIN W = - 3/4 X] +150 X2 - 1/50 X 3 + 6 X4

Con sus restricciones:

147

TABLERO4'DUALSIMPLEX

Entra a la base X 1; sale de la base S! VB

Sj = 0 52 = 0 53 = 1

VNB

x, = o X2 = 0 x3 = o

w= o

X4 = 0

TABLERO 2

SIMPLEX

Entra a la base X 2 , sale de la base S2 VB X, = 0

52 = 0 53 = 1

VNB X2 = 0

x3 = o x4 = o

w= o

S! = 0 TABLERO 3

Entra a la base X 3 , sale de la base X 2

148

SIMPLEX

VB

VNS

X, = 0

X3 = O

X2 = 0

X4=0

S3=l

s, = o

w =o

s2 = o TABLERO 4

SIMPLEX

Entra a la base X 4 , sale de la base S 3 VB

VNB

X, = 0

X2 = O

X3 = 0

X, = o s, = o s2 = o

S3 = 1

w= o

TABLERO 5

SIMPLEX

Entra a la base Si, sale de la base X 4

VB

VNB

X, = 2/125

X2 = 0

X3=

1

S, = 0

X 4 = 1/250

S2 = O

W =-1/125

S3 = 0

149

TABLERO4'DUALSIMPLEX

Solución Óptima Única

Si hubiéramos trabajado con el simplex tradicional, al pasar del tercer tablero al cuarto, la variable escogida para salir de la base es Xj en lugar de X2. Existen otras técnicas que permiten reformular un problema lineal particular como un conjunto de problemas lineales más pequeños. Tales modelos son el de Descomposición de Dantzig-Wolfe y el de Benders. Es de añadir que el procedimiento de Dantzig-Wolfe es equivalente para problemas de Programación Lineal a otras dos técnicas de partición/descomposición/relajación: Descomposición de Benders y el Método de Relajación Lagrangiano. Así mismo hay otros métodos denominados de Cota Superior y de Cota Inferior.

Descomposición de Dantzig-Wolfe Esta técnica permite resolver grandes problemas de Programación Lineal, mediante la reducción de un problema por medio de submatrices. Es un mejoramiento del Simplex Revisado; a medida que la matriz de coeficientes tecnológicos aumenta, por tener más actividades y más restricciones, ésta se va haciendo menos densa, donde la densidad es la relación de números diferentes de cero en la matriz entre el número total de sus componentes. El Método de Descomposición de Dantzig-Wolfe converge a una solución óptima de P (primal) en un número finito de iteraciones. Ejemplo: MAX Z = 4 X, + 3 X 2 Sujeta a:

150

\

Solución:

Seleccionamos entre las columnas uno y dos, aquella que más se aleja de cero por la izquierda ( - 4); los cocientes son:

el elemento más cercano a cero por la derecha (4000). A continuación expresamos el problema en submatrices:

151

A continuación seleccionamos la segunda columna y la tercera fila; efectuamos la permutación para colocarlos en la primera columna y en la primera fila:

Luego la selección se hará sobre la tercera columna y la segunda fila:

Hemos alcanzado el óptimo:

Solución Óptima Única:

153

Descomposición de Benders Recibe también el nombre de descomposición primal, porque el problema maestro fija variables del primal, descomposición en L porque se aplica a problemas con matriz de restricciones con dicha forma, descomposición por recursos porque el maestro asigna directamente las decisiones sobre los recursos al subproblema; descompone el problema lineal bietapa en un problema maestro y un subproblema. El maestro representa la primera etapa más las condiciones necesarias, denominadas cortes, derivadas de la segunda etapa; el subproblema representa la segunda etapa para decisiones conocidas de la primera etapa. El algoritmo es iterativo y alterna entre la solución del maestro y la del subproblema. Existe otro modelo de Benders llamado anidado, el cual consiste en la aplicación recursiva de Benders a los subproblemas que aparecen en el modelo de descomposición de Benders. El problema lineal bietapa se representa matemáticamente de la siguiente forma, considerando el vector X¡ las variables de la primera etapa y X 2 las variables de la segunda etapa:

Sujeta a:

Donde Las dimensiones de los demás vectores y matrices se derivan de éstas; por ser Optimización Determinística se suponen conocidas las matrices y vectores. El tamaño del problema completo es (mj + m2) * (nj + n2); la estructura de la matriz de restricciones del problema (matriz triangular inferior por bloques) es:

A,

B,

A2

El Método de Descomposición de Benders converge a una solución óptima de D (dual) en un número finito de iteraciones. Ejemplo:

154

Sujeta a:

Solución:

Iteración 1

; optimizando por ejemplo la función ui sobre:

Iteración 2

Sujeta a:

155

Con sus restricciones:

Equivalentemente:

Sujeta a:

Iteración 3

Sujeta a:

156

Con sus restricciones:

Equivalentemente: MAX Z = X 2 + X 3 Sujeta a:

Iteración 4:

D 3m : MAX Z = 4X,+

Sujeta a:

a

Con sus restricciones:

Equivalentemente: MAX Z = X 2 + X 3

Sujeta a:

Iteración 5 Una solución óptima del problema inicialmente propuesto es:

Solución Óptima Única:

158

Relaciones entre la descomposición de Dantzig-Wolfe y la descomposición de Benders

Sea P un problema Primal de Programación Lineal en forma estándar y D su problema Dual. Entonces aplicar la descomposición de Dantzig-Wolfe sobre P o la descomposición de Benders sobre D llevan, en cada iteración, a resolver problemas maestros duales y subproblemas idénticos. Por tanto, en Programación Lineal ambas técnicas se relacionan entre sí, como lo hacen el simplex primal y el simplex dual, esto es, son técnicas duales la una respecto a la otra. Además, la primera es una partición por filas y generación de columnas, porque la coordinación en la descomposición es mediante ajustes sobre el vector de costos del problema sobre el que se aplica P, mientras que la segunda es una partición por columnas y generación de filas, porque la coordinación en la descomposición es mediante ajustes sobre el vector de recursos del problema sobre el que se aplica D. Una importante consecuencia de este análisis conjunto es que, combinando oportunamente ambas metodologías, es posible resolver grandes problemas lineales. Además, esta misma idea que subyace bajo ambas técnicas puede ser utilizada para resolver problemas de Programación Lineal Entera.

El sistema d e Leontief y la P r o g r a m a c i ó n Lineal

La teoría de input-output se debe en gran parte a Wassily W. Leontief, de la Universidad de Harvard, ganador del Premio Nobel de Economía en 1973. Si se reescribiera el sistema de Leontief como problema de Programación Lineal apropiado, obtenemos realmente el resultado que W' B' x = p'c. Sin embargo, para construir un problema de Programación Lineal debemos especificar una función objetiva apropiada. Considere el caso, entonces, cuando permitimos una desigualdad en las restricciones de cantidad de modo que poder permitir que las materias primas sean producidas en el exceso de las demandas de la entrada y demanda final. Así, en la gráfica anexa, la desigualdad de las ecuaciones de la cantidad implica que una necesidad de la solución (x*, x*2) esté a lo largo del punto X en la intersección de L¡ y de L2 . Además, debemos tener en cuenta la posibilidad de la desigualdad terminante que sostiene para cualesquiera de las ecuaciones en nuestro sistema. Así, la desigualdad en la primera ecuación permite hacer combinaciones en el área debajo de L| y la desigualdad en la segunda ecuación implica que todas las áreas sobre L2 son permisibles. El área sombreada en la gráfica siguiente representa las combinaciones de la salida que son factibles dadas las desigualdades. Sin embargo, todavía deseamos obtener (x*, x 2 ) como la solución, así debemos especificar una función objetiva que rinda esto. Consideremos la minimización de los pagos totales del factor, W' B' x. Esta es, por supuesto, simplemente una suma cargada de salidas. Podemos representar esto en la gráfica por el lugar geométrico negativo-inclinado B con la intercepción horizontal (W' B' x) e inclinarse representa las combinaciones de las salidas X] y el mismo

159

factor de X 2 . Así, reduciendo al mínimo W' B' x, entonces cambiamos de puesto a B hacia la izquierda a B*, donde B* interseca el punto X del equilibrio en

B

L

x2

X,*

X,*

X

D E T E R M I N A C I O N DE LA C A N T I D A D

Por consiguiente, con desigualdades, podemos plantear el problema para las cantidades como problema de Programación Lineal de la clase siguiente:

Sujeta a:

Así, intentamos elegir los niveles no negativos de la salida (x) que reducen al mínimo los pagos del factor (W' B' x,) conforme a las restricciones de las salidas (x) para no exceder la demanda para las salidas (A' x + c). Así, dada la tecnología (A, B), el nivel y composición de la demanda final (c) y del salario verdadero histórico dado (w), para poder solucionar para las cantidades, En la Programación Lineal, cada problema principal tiene un problema dual. En este caso, deseamos considerar las ecuaciones del precio-coste, donde el precio no puede exceder el coste de producción. En la gráfica siguiente, en la cual la solución

se encuentra en la intersección de

(punto P).

La primera desigualdad permite que consideremos el área sobre Mj y la segunda desigualdad permite combinaciones en el área debajo de M 2 . Así, cualquier combinación del precio en el área sombreada en la siguiente gráfica llega a ser factible. 160

D E T E R M I N A C I Ó N DE PRECIO

La función objetiva apropiada ahora es maximizar el valor de la demanda fmal, es decir, maximiza p' c. p' c = p, c, + p2 c 2 Así, podemos sobreponer un lugar geométrico negativo-inclinado C en el gráfico anterior que representa las combinaciones de p i y p2 que rinden el mismo valor de la demanda final, p' c para una C j dada y C 2 . El lugar geométrico C tiene intercepción horizontal p' c con Q > 0 y pendiente - C¡ / C 2 < 0. Cambiar de puesto el lugar geométrico de C a la izquierda disminuye el valor de la demanda final, mientras que cambiarlo de puesto a la izquierda aumenta el valor de la demanda final. Así, maximizando p' c, nos trasladamos al lugar geométrico más alto C* y obtener de esta manera la solución del equilibrio

(p¡, P2) en P en la intersección de las curvas de

PROGRAMACIÓN LINEAL DIFUSA O BORROSA Un modelo de Programación Lineal Difusa o Borrosa es un problema del tipo:

Sujeta a:

donde los elementos difusos se consideran dados por: 161

• Para cada costo:

las cuales definen el vector de costos borrosos.

• Para cada fila

las cuales definen el número difuso en la parte derecha.

• Para cada i g M y j e N

las cuales definen los números borrosos en la matriz tecnológica.

• Para cada fila

que nos da para cada X e R", el grado de acoplamiento del número borroso

con respecto a la i-ésima restricción, es decir, la adecuación entre estos números difusos y el correspondiente bf relacionado con la i-ésima restricción.

M é t o d o d e Solución del M o d e l o G e n e r a l d e Programación Lineal Difusa Un método de solución para el modelo general consiste en la sustitución del conjunto restricción de este modelo por un conjunto borroso convexo. Sea g una función ordenadora de números difúsos, verificando que:

162

Sea la función:

con

tal que su soporte esté incluido en

una relación que mide el que

las operaciones usuales entre números borrosos. Los principales modelos para solución de problemas de Programación Lineal Difusa son Aproximación de Tanaka, Aproximación de Zimmermann, Aproximación Paramétrica, Aproximación Multiobjetivo, Aritmética Intervalar, Aproximación Posibilística, Aproximación por Reducción Estratificada a Trozos, Método de Jain, Primer índice de Yager, Segundo índice de Yager, Tercer Indice de Yager, Relación de Adamo, índice Promedio, índice de Chang, Grado de Posibilidad de Dominancia, Grado de Necesidad de Dominancia, entre otros.

EJERCICIOS PROPUESTOS Resolver gráficamente cada uno de los siguientes problemas y decir a qué tipo de solución corresponden.

MAX Z = 6 X! + 7 X 2 Sujeta a:

MAXZ = 4 X , + 2 X 2 Con sus restricciones:

163

MAX Z = 4 X| + 4 X 2 Sujeta a:

MAX Z = 5 X] + 7 X 2 Con sus restricciones:

Resolver los siguientes problemas mediante la aplicación del algoritmo Simplex correspondiente y decir a qué tipo de solución pertenece cada uno:

MAXZ = 5 X , + 6X2 Sujeta a:

MIN W = X 8 Con sus restricciones:

164

7«

MIN W = 2 X, + X 2 Sujeta a: 1. 3 X, +

X2 > 3

2. 4 X, + 3 X 2 > 6 3.

X, + 2 X 2 > 3 X,,X2 > O

8 *

MAX Z = X, + X 2 Con sus restricciones: 1. X, + X2 < 10

xu 9 »

x2 >

o

MAX Z = 4 X) + X 2 Sujeta a: 1.

X , + 2X2

2. 2 X i + Xb

1 0 -

>

30

X2

>

40

X2

>

0

MAX Z = 5 X[ + 7 X 2

Con sus restricciones: 1. 2 X , + 2 X 2 <

4

2. 4 X] + 4 X 2 > 16 Xi, x 2 >

o

CAPÍTULO

V

D U A L I D A D EN P R O G R A M A C I Ó N LINEAL A N Á L I S I S DE P O S O P T I M A L I D A D Y S E N S I B I L I D A D PROGRAMACIÓN LINEAL PARAMÉTRICA "Si los hechos no encajan en la teoría, cambie los hechos". Albert Einstein

EL PROBLEMA DUAL EN PROGRAMACIÓN LINEAL

Recursos

Producción

Fundamentalmente se trabaja con las siguientes opciones:

167

Con sus restricciones:

Sujeta a:

El dual se debe a la optimización del modelo del transporte sin trabajar con el simplex. PRIMAL

DUAL

m restricciones n variables

m variables n restricciones

Teoremas d e la d u a l i d a d 1. Si el primal o el dual tienen solución óptima finita, entonces el dual o el primal tendrán solución óptima finita. 2. Si el primal o el dual tienen solución óptima no acotada, entonces el dual o el primal no tendrán solución (será) infactible. 3. Si el primal o el dual no tienen solución, entonces el dual o el primal no tienen solución. Continuando con el ejemplo resuelto por simplex, vamos a plantear, resolver e interpretar las variables correspondientes al dual.

Primal: MAX Z = 400 X, + 200 X 2 Sujeta a:

168

Dual: MIN W = 800 Y, + 600 Y 2 + 80 Y 3 + 150 Y 4 Con sus restricciones:

Forma estándar I:

Forma estándar II:

TABLERO 1

DUAL SIMPLEX

Variables de salida: ( - 400, - 200) = - 400 (S t ). Se escoge la que más se aleja de cero por la izquierda. Variables de entrada: (800/-18, 600/-9, 80/-1, 150/0) = ( - 44.4, - 66.6, - 80, N.E.D.) = - 44.4 (Y[). Se toma aquella variable que menos se aleje de cero por la izquierda. Sale de la base S|, entra a la base Y) VB 51 = - 400 5 2 = - 200

VNB Y, = 0 Y2 = 0 169

Y3 = O Y4 = O

w= O

Nota: NED significa que la división entre cero no se encuentra definida.

TABLERO 2

DUAL SIMPLEX

Sale de la base S 2 y entra a la base Y2. VB Y, =

VNB 200/9

S2 = - 4 0 0 / 3

Y2 = 0 Y3=0 Y4 = 0 S, = 0

W = 160000/9

TABLERO 3

DUAL SIMPLEX

Sale de la base Y). Variable que pasa a ser básica: Hay empate entre Y 4 y Si; escogemos Y4.

VB

VNB

Y, = - 40/9

Y2 = 0

S2=

Y3 = 0

160/3

Y4 = 0 S| = 0

170

W = 256000/9

TABLERO 4' DUAL SIMPLEX

Llegamos al óptimo.

A continuación observamos qué ocurre si en lugar de escoger Y 4 tomamos S], en el tablero 3'.

TABLERO 3'

DUAL SIMPLEX

Variable que se convierte en no básica Y t ; variable que se vuelve básica Sj. VB

VNB

Y! = - 40/9

Y3 = 0

Y 2 = 160/3

Y4 = 0 S, = 0 S2 = 0

W = 256000/9

171

TABLERO 4' DUAL SIMPLEX

Óptimo para el tablero 4:

Óptimo para el tablero 4':

Con las respuestas conseguidas anteriormente se obtiene la corroboración de resultados entre primal y dual con sus métodos correspondientes simplex y dual-simplex (Tableros 4 y 4'). Los coeficientes de las variables de holgura en la función objetivo del primal son los valores de las variables reales del dual en orden ascendente. Los coeficientes de las variables de decisión en la función objetivo del primal son los valores de las variables del holgura del dual en orden ascendente.

Interpretación económica d e los p r o b l e m a s p r i m a l y d u a l Para el primal: Xj Cj Z bj

: Nivel de actividad j (j = 1,2,3,...,n). : Utilidad unitaria de la actividad j. : Utilidad total, : Cantidad de recurso i disponible.

a¡j :

Cantidad de recurso i consumido (i = 1,2,3,... ,m) por cada unidad de actividad j.

Para el dual: Y¡ C¡ W bj

172

: Valor implícito o precio sombra o costo marginal del recurso i : Costo unitario del recurso. : Valor total implícito de los recursos, : Cantidad de artículos j a producir.

Como cada unidad de actividad j en el problema primal consume a¡j unidades del recurso i se interpreta como la contribución en la utilidad de la mezcla de recursos que serían consumidos si una unidad de actividad j fuera usada (j = 1,2,3,...n). Establece que la contribución en la utilidad de la mezcla de recursos debe ser por lo menos tanto si fueran usados por una unidad de actividad j, de otra manera no se estaría haciendo el mejor uso posible de estos recursos. La contribución en la utilidad del recurso i (i=l ,2,3,...,m) debe ser no negativa, de lo contrario sería mejor no usar el recurso.

ANÁLISIS DE SENSIBILIDAD

Cambios discretos y / o continuos Fundamentalmente cuando se trabaja en Programación Lineal es importante realizar un análisis de postoptimalidad para observar por medio de simulación si los cambios que le vamos a introducir al modelo original, en qué aspectos nos benefician o nos afectan en las variables y/o parámetros. Es importante tener en cuenta que los cambios que se realizan en el modelo original deben ser factibles y deben responder a situaciones reales que la empresa puede llegar a vivir en un momento determinado. Los cambios en los vectores b, c y en la matriz A pueden suceder en forma discreta o continua; el cambio discreto indica que una o varias componentes originales de los vectores o de la matriz son reemplazados por nuevas cantidades; el cambio continuo en los vectores aj, b y c se da cuando se presentan cambios así:

donde A b, A c y A a,- son vectores respectivamente con las mismas dimensiones que los vectores b, c, aj; a , P y 7 son escalares que pueden tomar cualquier valor real. El análisis de sensibilidad que estudia los cambios continuos se denomina Programación Paramétrica. Para observar las variaciones que ocurren o no, vamos a ilustrar las diversas situaciones con el siguiente ejemplo:

Sujeta a:

173

Cambio en un C. cuando X. es no básica i i Va a cambiar un número en la fila de Z¡ - C¡, desde Z* - Cj hasta Z* - C'¡ ; la nueva solución sigue siendo factible ya que no se han cambiado las restricciones, ni los recursos. Cuando hay un cambio en un Cj del primal, solamente cambia el lado derecho de la j-ésima restricción del dual; puede ocurrir que la solución ya no sea factible (una de las variables básicas será menor que cero). La función objetivo va a asegurar una solución óptima, porque los recursos del primal no se han cambiado.

Ejemplo: Se cambia la función objetivo de: MAX Z = 50 X! + 120 X 2 a: MAX Z = 80 X t + 120 X 2 El cambio en la función objetivo en la variable Xj es 50 por 80. Este cambio tiene un efecto sobre el valor de Z* - C¡ en el óptimo actual (Primal: X* = 0; X 2 = 20; S*=0; S 2 =40; Z* = 2400; Dual: Y* = 30; Y2* = 0; S* = 10; S 2 = 0; W* = 2400 ), valores que se pueden convertir en: Si el valor actualizado de Zj - Cj > 0, la solución óptima permanece igual a la del problema inicial y en el problema dual sólo cambia el valor de la variable de holgura S* . Si el nuevo valor de Zj - Cj = 0, la solución óptima permanece igual a la del problema inicial cuando se presentan soluciones múltiples y en el problema dual sólo cambia el valor de la variable de holgura S * cuyo valor será cero (0). Si el valor actualizado de Z* - Cj < 0, la solución deja de ser óptima por lo cual se requiere la utilización del simplex, tomando X] como la variable que se convertirá en variable básica.

La solución óptima actual es: Primal: X* = 16; X 2 = 12; S* = 0; S * = 0 ; Z* = 2720. Dual: Y* = 28; Y* = 8; S* = 0; S 2 = 0; W* = 2720. Para que se mantenga la solución actual óptima y factible basta con plantear y resolver la ecuación que recalcula el valor de Z\ - C), sabiendo que en el tablero óptimo el valor de C| debe cumplir con la condición que Z \ - C \ > 0, por lo cual - oo < Ci < 60.

174

Cambio en un C. cuando X. es básica i i Si Xj es básica

, con lo cual se debe modificar la fila de

en el

último tablero y en algunos casos se debe variar toda la tabla, si la solución del primal dejó de ser la óptima. En algunos casos cuando

, la solución es aún óptima.

La nueva solución en el óptimo debe ser óptima o mejorar, pero en algunos casos puede no ser factible. Ejemplo: Cambiando la función objetivo de: a: El nuevo valor de

corresponde a una variable básica, cuyo valor será cero (0).

La solución óptima es: Primal: Dual: Para que permanezca lasolución actual óptima y factible basta con plantear y resolver la ecuación que recalcula el valor de de cada una de las variables no básicas, sabiendo que en el tablero óptimo el valor de Cj debe cumplir con la cdndición que , por lo cual Cambio en un b¡ (recurso) Los únicos cambios posibles son en los lados derechos de las restricciones, porque estos lados dan los valores de las variables de la base y éstas se pueden volver negativas; cuando no hay cambios en los

, la solución encontrada sigue siendo óptima. En el caso en que un bi se vuelva negativo

se debe emplear el dual simplex para solucionar el primal. Además, es posible en el problema dual encontrar e interpretar el precio sombra (marginal) y los costos reducidos. Ejemplo: Cambiando la segunda restricción de: a: La solución óptima actual es: Primal: i Dual:

175

Para que se mantenga la solución actual factible basta con plantear y resolver las ecuaciones para encontrar los valores de los nuevos bi, de tal manera que las variables básicas sean 0, por lo cual

Cambio en a., cuando X. es no básica •i i En estos casos cambian los coeficientes de Xj en todas las filas del tablero; como X¡no es básica, si la fila Z - C > 0, la solución sigue siendo óptima. Es más fácil investigar si la solución anterior es todavía óptima con el dual, ya que el único cambio es en la j-ésima restricción:

porque los valores óptimos de las variables originales

no cambian; la solución anterior es factible y aún óptima si la nueva restricción no se viola. Ejemplo: Cambiando la segunda restricción de: a: La solución actual es: Primal: Dual: Para que permanezca la solución actual óptima basta con plantear y resolver la ecuación que recalcula el valor de

con la condición que

por lo cual

Cambio en a., cuando X. es básica 'i i La solución siempre cambia (hasta volverse no factible y puede ser aún una solución óptima). Se deben encontrar los nuevos coeficientes de los Xj, es decir, los nuevos números dentro de la tabla, ya que seguramente la matriz idéntica sufrió con el cambio. Al cambiar en el dual la j-ésima restricción y su solución , puede que la nueva solución no sea factible (si viola las restricciones), ni óptima. Ejemplo

176

O

Cambiando la segunda restricción de: a: La solución actual es: Primal Dual: Para que se mantenga la solución actual factible basta con plantear y resolver las ecuaciones para encontrar los valores de los nuevos bi para la factibilidad y la optimalidad con los para las variables no básicas, de tal manera que

Adición de una nueva restricción Dicha adición no mejora la solución óptima Z*, sólo puede eliminar algunas de las soluciones; cuando la anterior solución aún es factible, debe ser la solución óptima. Se debe averiguar si la nueva restricción se cumple o no; cuando se cumple, no hay problema. En caso contrario, se deben agregar las variables correspondientes. Ejemplo Añadiendo la nueva restricción: La solución actual es: Primal: Dual:

Adición de una nueva variable Luego de encontrar la solución óptima del problema, se concluye que no se han considerado todas las actividades que consumen recursos y que aportan a función objetivo. Tener en cuenta una nueva actividad exige añadir una nueva variable con sus respectivos coeficientes a la función objetivo y a las restricciones. Si hacemos que la nueva variable pertenezca a las no básicas, no es difícil investigar que si la solución óptima anterior es todavía óptima, en este caso no hay cambio en la fila Z - C y por lo tanto la solución del dual no varía. Cuando hay un cambio en el dual (adición de una nueva restricción), correspondiente a la nueva variable del primal, si la nueva restricción se cumple usando la vieja solución del dual, la antigua solución 177