EL METODO SIMPLEX (Primera parte)

.....La programación lineal es el planteamiento de un problema de optimización en ecuaciones lineales, tales que la función objetivo también sea una función lineal la cual se representa de la siguiente manera:

.....Los modelos de programación lineal a menudo presentan problemas de asignación en los cuales los recursos limitados se asignan a un cierto número de actividades en función de la formulación anterior, los coeficientes pueden interpretarse físicamente como:

bi = cantidad disponible de un recurso.

aij = cantidad del recurso i que debe asignarse a cada unidad de la cantidad j.

ci = valor por unidad de la variable de decisión Xj.

Ejemplo:

..... Se procesan tres productos a través de tres operaciones diferentes, los tiempos en minutos requeridos por unidad de cada producto, la capacidad diaria de las operaciones (min/dia) y el beneficio por unidad de cada producto vendida ($) son: tabla 2.1

tabla 2.1

.....se supone que todos los productos se venden. Además los beneficios dados por unidad son valores netos. Después de que se reajusten todos los costos pertinentes, la meta del modelo es determinar la producción diaria óptima para los tres productos que maximize el beneficio.

X1 = cantidad producida de producto 1

X2 = cantidad producida de producto 2

X3 = cantidad producida de producto 3

Función objetivo = 3X1 + 2X2 + 5X3

Sujeto a:

X1 + 2X2 + X3 <= 430

3X1 + 0X2 + 2X3 <= 460

X1 + 4X2 + 0X3 <= 420

..CARACTERISTICAS DE LA FORMA CANONICA..

1.- Todas la variables de decisión son no negativas.

2.- Todas las restricciones son del tipo < o =.

3.- La función objetivo es del tipo de maximización.

Para esto existen 5 transformaciones fundamentales:

1.- La minimización de una función +f(x) es equivalente a la maximización de una -f(x). minimizar Xo = C1 X1 + C2 X2 +C3 X3 +........+ Cn Xn. es igual a maximizar: Go = -Xo=-C1 X1 - C2 X2 -C3 X3 -........- Cn Xn.

2.- Una desigualdad en una dirección (<= ó >=) puede cambiarse a una desigualdad en la dirección opuesta (>= ó <=) multiplicando ambos lados de la desigualdad por (-1), por ejemplo: a1X1 +a2X2 >=b1 equivale a: -a1X1 - a2X2 <= -b1

3.- Una ecuación puede ser reemplazada por dos desigualdades con direcciones opuestas, por ejemplo: a1X1 +a2X2 = b1 equivale a: a1X1 + a2X2 >= b1 a1X1 + a2X2 <= b1

4.- Una restricción de desigualdad en su lado izquierdo en la forma de valor absoluto puede cambiarse por dos desigualdades dadas regulares ; por consiguiente para b>=0 |a1X1 + a2X2 | <= b equivale a: a1X1 +a2X2 >= -b a1X1 +a2X2 <=b

5.- Una variable irrestricta en signo ( esto es puede se +, - ó 0 ) es equivalente a la diferencia entre 2 variables no negativas. X irrestricta equivale a:

X = X + - X - donde:

X z+ > = 0 y X - >= 0

..CARACTERISTICAS DE LA FORMA ESTANDAR ..

Las características de la forma estándar son:

1.- Todas las restricciones son ecuaciones excepto las restricciones de no negatividad, que permanecerán como desigualdades (>=0).

2.- Los elementos del lado derecho de cada ecuación son no negativos.

3.- Todas la variables son no negativas.

4.- La función objetivo es del tipo de maximización o minimización

.....Las restricciones de desigualdad pueden cambiarse a ecuaciones introduciendo una variable ( que puede ser restada o sumada ), en el lado izquierdo de cada una de las restricciones siendo ésta no negativa. Esta variable se denomina variable de holgura.

a. Se suma la variable si la restricción es < ó =.

b. Se resta la variable si la restricción es > ó =.

La forma estándar se puede expresar así:

..METODOS GRAFICOS..

.....A continuación se presenta un modelo sencillo con dos variables de decisión y se muestra como se puede resolver gráficamente. Si bien es cierto que una solución gráfica bidimencional casi no tiene utilidad en situaciones reales ( las cuales normalmente comprenden cientos o miles de variables y restricciones), el procedimiento ofrece una excelente oportunidad para entender como funciona el proceso de optimización .

Ejemplo 2.1: COMEX posee una pequeña fábrica de pinturas para interiores y exteriores de casas para su distribución al mayoreo, se utilizan dos materiales básicos, A y B, para producir las pinturas, la disponibilidad máxima de A es de 6 toneladas diarias ; la de B es de 8 toneladas por día. La necesidad diaria de materia prima por tonelada de pintura para interiores y exteriores se resumen en la tabla 2.2

Tabla 2.2

.....Un estudio de mercado ha establecido que la demanda diaria de pinturas para interiores no puede ser mayor que la de pintura para exteriores en mas de una tonelada. Asimismo el estudio señala que la demanda máxima de pinturas para interiores está limitada a dos toneladas diarias.

.....El precio al mayoreo por tonelada es $3 000 para la pintura de exteriores y $2 000 para la pintura de interiores.

¿ Cuánta pintura para interiores y exteriores debe producir la compañía todos los días a fin de maximizar el ingreso bruto ?

Variables:

XE = Toneladas de pinturas para exteriores producidas diariamente.

XI= toneladas de pinturas para interiores producidas diariamente.

.....Como cada tonelada de pintura para exteriores se vende en $3000, el ingreso bruto obtenido de la venta de XE toneladas es 3XE miles de unidades monetarias, en forma análoga el ingreso bruto que se obtiene de vender XI toneladas de pintura para interiores es 2XI miles de unidades monetarias, bajo la suposición de que las ventas de pintura para exteriores e interiores son independientes, el ingreso bruto total se convierte en la suma de dos ingresos.

.....El problema impone restricciones sobre el uso de materias primas y sobre la demanda. La restricción del uso de materias primas en base a la tabla 2.2 se expresa como:

XE+2XI<=6 (materia prima A)

2XE+XI<=8 (materia prima B)

Las restricciones sobre la demanda se expresan como;

XI-XE<=1 (exceso de pintura para interiores )

XI<=2 (demanda máxima de pintura para interiores)

.....Una cantidad implícita es que la cantidad que se produce de cada pintura no puede ser negativa, para poder evitar tener una solución como esta, imponemos la restricción de no negatividad, que normalmente se escribe como:

XI>=0 (pintura para interiores).

XE>=0 (pintura para exteriores).

...continua...

El modelo matemático completo para éste modelo se puede resumir ahora de la manera siguiente;

MAXIMIZAR Z = 3XE +2XI

SUJETO A:

XE + 2XI <= 6

2XE + XI <= 8

- XE +XI <= 1

X1 <= 2

XE >= 0 , XI >= 0

.....El modelo se puede resolver gr1áficamente porque sólo tiene dos variables, para modelos con tres o más variables, el método gráfico es impráctico o imposible, no obstante podremos deducir conclusiones generales del método gráfico que servirán como la base para el desarrollo del método de solución general.

.....El primer paso del método gráfico consiste en graficar las soluciones factibles o el espacio de soluciones factibles, que satisfaga todas las restricciones en forma simultánea la siguiente figura representa el espacio de soluciones que se requiere. figura 2.4

Figura 2.4

.....Las restricciones de no negatividad XE>=0 y XI>=0 confinan todos los valores factibles, el espacio cerrado por las restricciones restantes se determina sustituyendo en primer término (<=) por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta. Después se traza cada línea recta en el plano (XE,XI) y, la región en la cual se encuentra cada restricción cuando se considera la desigualdad, lo indica la dirección de la flecha situada sobre la línea recta.

.....Para obtener la solución optima (máxima), desplazamos la recta del ingreso "cuesta arriba" hasta el punto donde cualquier incremento adicional en el ingreso produciría una solución infactible, la figura 2.4b muestra que la solución óptima ocurre en el punto C, como C es la intersección de las rectas 1 y 2 , los valores de XE y XI se determinan al resolver las dos ecuaciones que siguen en forma simultanea. Cada punto contenido o situado en la frontera o el espacio de soluciones ABCDEF satisface todas las restricciones y, por consiguiente representa un punto factible, aunque hay un número infinito de puntos factibles en el espacio de soluciones. véase figura 2.4b

.....La solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo z= 3XE+2XI, la figura 2.4b muestra este resultado. Las dos ecuaciones producen XE= 3.33333 y XI=1.333333 . Por lo tanto la solución indica que la producción diaria debe ser de 3.33333 toneladas de pinturas para exteriores y de 1.3333 toneladas de pintura para interiores y el ingreso asociado es

Z= 3 (3.3333) + 2(1.3333) = 12.6666 (miles de $)

Figura 2.4b

Ejemplo 2.2

.....Suponga que por un momento es dueño de una planta que produce únicamente dos tipos de cerveza; clara y obscura, existen tecnologías bastante diferentes para la elaboración de cada uno de los tipos de cerveza, obviamente cada tecnología a un costo diferente. El lector no sabe cual debe ser su producción óptima semanal de cada producto y por lo tanto se decide a identificar dos variables de decisión .

X1: miles de litros de cerveza clara a producir en una semana.

X2: miles de litros de cerveza obscura a producir en una semana.

.....El precio de mayoreo de 1000 litros de cerveza clara es de $5000.00 mientras que el precio de mayoreo de 1000 litros de cerveza obscura es de $3000.00 . El ingreso semanal de la venta de ambos productos sería :

Z=5000X1 + 3000X2 = $

.....cuyas unidades son; $/(miles de litros de cerveza clara /obscura)(miles de litros de cervezaa clara/obscura).

.....El objetivo del lector como el de cualquier industrial, es el de maximizar los ingresos semanales, es decir producir un gran volumen de X1 y X2 ¿Cuán grande? . Para maximizar Z se debe aumentar X1 y X2, desgraciadamente hay restricciones físicas en el sistema real de producción que le impiden a usted incrementar arbitrariamente la producción de X1 y X2, entre estas restricciones se pueden mencionar las siguientes ; espacio de almacenamiento, capacidad de producción, capital, mano de obra, etc. Para facilidad de explicación permítase utilizar solamente dos restricciones de las muchas que existen en la realidad. Sean éstas: restricciones de mano de obra, restricciones de producción. Un estudio de tiempos y movimientos ha demostrado que para producir 1000 litros de cerveza clara se requiere un total de 3 obreros en el proceso de producción, en cambio se requieren 5 obreros par producir 1000 litros de cerveza obscura. Se supone que la planta tiene un total de 15 obreros. Esto quiere decir que la producción de X1 y X2 depende del número disponible de obreros esto puede representarse por la siguiente desigualdad.

3X1+5X2<=15 donde las unidades son:

obreros (miles de litro de cerveza) / (miles de litros de cerveza) = obreros.

.....La desigualdad anterior dice que la cantidad de obreros utilizados en la producción semanal de X1 y X2 no puede exceder de 15, producir 100000 litros de cerveza clara y 100000 litros de cerveza obscura, utilizarían 800 obreros que exceden al límite disponible . Se supone que producir 1000 litros de cerveza clara le cuestan al dueño de la planta $500, mientras que 1000 litros de cerveza obscura le cuestan solamente $200 . Su capital no le permite gastar mas de $1000 semanales en la producción de X1 y X2 . Matemáticamente esta restricción puede expresarse así :

500X1 + 200X2 <= 1000

.....Cuyas dimensiones, como puedes comprobar fácilmente, son $ de nuevo, la producción de 100000 litros de X1 y X2, significarían un gasto semanal de 70000 que excede al límite de $1000. La pregunta a la que el dueño desea una solución es la siguiente

¿Cuáles deben ser los niveles de producción semanal de cerveza clara X1, y de cerveza obscura X2, que maximizen el ingreso por concepto de ventas semanal, sin exceder las restricciones de personal y de capital? .

.....Matemáticamente se trata de resolver el siguiente problema.

MAXIMIZAR:

Z= 5000X1 + 3000 X2.

sujeto a:

3X1 + 5X2<= 15

500X1 + 200 X2 <= 1000

X1>=0

X2>=0

.....Las últimas restricciones, se llaman condiciones de no negatividad, y evitan que los resultados den un absurdo negativo, que en este caso podrían significar una producción negativa (destrucción ) . En coordenadas rectangulares se puede escribir gráficamente, como el dueño de la planta puede resolver óptimamente su programa de producción semanal. Un eje del sistema medirá la cantidad de cerveza clara X1, y el otro la cantidad de cerveza obscura X2. Como X1 y X2 deben ser no negativas, se refiere únicamente al cuadrante derecho superior del sistema coordenado, tal como se indica en la. fig 2.5

Figura 2.5

A continuación se interpreta la representación geométrica de las desigualdades.

3X1 + 5X2 <= 15

500 X1 + 200 X2 <=1000

Si por el momento se considera estas desigualdades como igualdades se tiene:

3X1 + 5X2 = 15

500 X1 + 200 X2 =1000

o lo que es lo mismo

X2 = 3- 3/5X1

X2 = 5- 5/2X1

.....Si arbitrariamente se le dan valores a X1, se obtiene el correspondiente valor de X2 en ambas rectas. Un par de valores arbitrarios de X1 generarían dos puntos que unidos dan la recta en cuestión, se dan a X1 el valor de cero en ambas rectas, y se obtienen los valores 3 y 5 para cada recta respectivamente. La tabla a continuación da el valor de X2 fig 2.6

Figura 2.6

.....Sin embargo, no interesan las igualdades sino las desigualdades y estas se muestran gráficamente en las áreas sombreadas de la figura 2.7 a) b) c).

2.7 a)

2.7 b) y c)

...continua...

...Esto quiere decir que cualquier punto (X1,X2) en el área sombreada de la figura 11 a) satisface la restricción 5X1 + 2X2 <=10, mientras, que un punto (X1,X2) en la zona blanca de la misma figura viola esa restricción, es decir, satisface 5X1 +2X2 >10 intersectando las tres figuras se tiene la figura 2.8 .

fig 2.8

.....Los puntos (X1,X2) contenidos dentro de la zona sombreada son los únicos que satisfacen las restricciones laborales de capital y de negatividad, simultáneamente. El industrial tiene que buscar dentro de esa infinidad de puntos cuales son los que le producen la mejor utilidad Z . Por ejemplo, el punto A,(0,0), satisface todas las restricciones de desigualdad y no negatividad como se muestra a continuación:

3 (0) + 5 (0) = 0 <= 15

500 (0) + 200 (0) = 0 <= 1000

0 >= 0 , 0 >= 0

z = 50000 (0) + 3000 (0) = 0

El punto B donde se producirán X1= 1000 litros de cerveza clara y x2= 1000 litros de cerveza obscura.

3(1) + 5(1) = 8 <= 15

5000(1) + 200(1) = 700 <= 1000

1 >= 0, 1 >= 0

.....Que es una utilidad mucho mejor que la obtenida en el punto A. El punto C , donde se producirán x1=3000 litros de cerveza clara y x2=3000 litros de cerveza obscura generaran una utilidad de Z = $24 000. Que es una utilidad mucho mejor que la producida por los puntos A y B, sin embargo la producción del punto C viola las restricciones de personal y de capital. La primera porque utiliza 24 personas cuando el máximo permisible son 15, la segunda porque se están utilizando $ 2 100 cuando el máximo permisible es de 1000. Esta región sombreada lleva el nombre de región de factibilidad.

.....A continuación se verá como puede obtenerse gráficamente (X1,X2), que da el nivel de la producción, que satisfaciendo ambas restricciones proporciona la utilidad óptima. La función de utilidad se expresa como:

Z=5000 X1 + 3000 X2 Supóngase que Z=15000. Eso implica

15000 = 5000 X1 + 3000 X2

O sea X2 = (5 - 5/3 X1)

Dándole a X1 valores arbitrarios de 0 y 3, se obtiene respectivamente valores de X2, iguales a 5 y 0 . Al unir los puntos (0,5) y (3,0) con una recta, se obtendrá el lugar geométrico de todos los puntos (X1,X2)que satisfacen la recta z= 5000 X1 + 3000 X2 gráficamente se tiene : fig 2.9

2.9

.....Haciendo Z ahora igual a 10000, se obtiene una recta paralela a la anterior pero desplazada un poco hacia abajo, de la misma manera cpn una Z=30000 se obtendrá una recta paralela a las anteriores pero dezplazada un poco hacia arriba . Gráficamente se tiene : fig 2.10

2.10

..continua...

.....A estas alturas se puede afirmar que si se desplaza la recta hacia abajo, el valor de Z disminuye, mientras que un desplazamiento hacia arriba aumentaría el valor de Z, la pregunta ahora es, ¿Cuál es el máximo desplazamiento hacia arriba que proporciona el máximo valor de Z?, y cuya correspondiente producción no viole las restricciones de personal y capital, reflexionemos observando la sig figura: fig 2.11

..... 2.11

.....Se convence al lector que el punto "O" de coordenadas (X1*,X2*) , es el punto buscado. En este ejemplo, ese punto es el siguiente:

X1* = 1053 litros de cerveza clara.

Que generan una utilidad óptima de :

Z* = 5000 (1.053)) + 3000 (2.368) = 12369 pesos

.....Este problema que dista de ser real, porque una compañía cervecera produce más de dos productos y tiene mas de dos restricciones que tomar en consideración, ha permitido ilustrar gráficamente en que consiste una solución de un problema lineal. Desgraciadamente esa es la única utilidad que tienen los métodos gráficos, o sea el de ilustrar de manera sencilla los conceptos introductorios de la programación lineal, es posible, aunque francamente no recomendable, resolver problemas con tres variables de decisión. Sin embargo de 4 variables en adelante, no hay manera de resolver problemas de programación lineal por métodos gráficos. Por eso hace necesario que se utilicen otros métodos para resolver este tipo de problemas.

.....El método gráfico demuestra que la programación lineal óptima esta siempre asociada con un punto extremo o de esquina, del espacio de soluciones. Esta idea conduce precisamente a la creación del método simplex, básicamente lo que hace el método simplex es trasladar la definición geométrica del punto extremo a una definición algebraica.

.....Como paso inicial, el método simplex necesita que cada una de las restricciones estén en una forma estándar especial, en las que todas las restricciones se expresan como ecuaciones, mediante la adición de variables de holgura o de exceso, según sea necesario. Este tipo de conversión conduce normalmente a un conjunto de ecuaciones simultáneas. Donde el número de variables excede al número de ecuaciones, lo que generalmente significa que las ecuaciones dan un número infinito de punto solución. Los puntos extremo de este espacio pueden identificarse algebraicamente por medio de las soluciones básicas del sistema de ecuaciones simultáneas. De acuerdo con la teoría del álgebra lineal, una solución básica se obtiene igualando a cero las variables necesarias con el fin de igualar el número total de variables y el número total de ecuaciones para que la solución sea única, y luego se resuelven sistemas con las variables restantes. Fundamentalmente la transición del procedimiento gráfico al algebraico se basa en la validez de la siguiente relación importante.

¡¡¡¡¡¡¡¡ " Puntos extremos igual a soluciones básicas." !!!!!!!!!!!!!!!!!

.....Lo que hace el método simplex, es identificar una solución inicial y luego moverse sistemáticamente a otras soluciones básicas que tengan el potencial de mejorar el valor de la función objetivo en efecto, el método simplex es un método de cálculo iterativo donde cada iteración esté asociada con una iteración básica. El modelo de programación lineal puede incluir restricciones de los tipos <=, =, y >= además las variables pueden ser no negativas o irrestrictas (no restringidas en signo). Para desarrollar un método de solución general, el problema de programación lineal debe ponerse en un formato común, al que llamamos la forma estándar .