Algoritmos especiales

Algoritmos especiales

Introducción

Sabemos que para que un ordenador pueda llevar adelante una tarea cualquiera, se tiene que contar con un algoritmo que le indique, a través de un programa, que es lo que debe hacer con la mayor precisión posible. Consecuencia de lo anterior es la importancia del estudio de los algoritmos.

Concepto de Algoritmo

Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que permite realizar una actividad mediante pasos sucesivos sin generar dudas a quien deba realizar dicha actividad, conduciendo a la solución de un problema determinado. De esta manera, dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. En la vida cotidiana, frecuentemente se emplean algoritmos para resolver problemas.

Algoritmos especiales

Son diseñados para problemas de programación lineal, son problemas enunciados con ecuaciones lineales y con una función objetivo, y una o más funciones restricciones, para lograr la optimización de la función objetivo que se analiza. Algunos de ellos son : Gran M, Flujo mínimo, Algoritmo Fraccional, Método Dual Simplex, entre otros.

Aplicación

Son empleados principalmente en problemas de flujo de redes y problemas de flujo de mercancías. Son muy usados en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción.

El método simplex

El método más conocido y habitual para resolver problemas de P.L. es el método del Simplex debido a Dantzig en 1947, este método es un procedimiento de cálculo algebraico para resolver modelos lineales de cualquier tamaño, es iterativo porque consiste en ir mejorando la solución a cada paso. Este concluye cuando no se puede seguir mejorando la solución.

El algoritmo Simplex requiere que el modelo lineal, para ser solucionado, cumpla las condiciones de forma estándar y sistema canónico.

La Forma Estándar incluye:

a) Una función objetivo a optimizar

b) Lado derecho de las restricciones con valor positivo.

c) Variables de decisión no negativas.

d) Las restricciones deben ser expresadas como igualdades.

Empezando en el valor de la función objetivo en algún vértice, el método trata de buscar continuamente otro vértice que mejore al anterior. La búsqueda se a través de lo realiza por los lados del polígono (o aristas del poliedro, si el número de variables es mayor). El número de vértices (y de aristas) es finito, por tanto siempre encontraremos la solución.

Se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

En una granja agrícola se desea criar conejos y pollos como complemento en su economía, de forma que no se superen en conjunto las 180 horas mensuales destinadas a esta actividad. Su almacén sólo puede albergar un máximo de 1000 kilogramos de pienso. Si se supone que un conejo necesita 20 kilogramos de pienso al mes y un pollo 10 kilogramos, que las horas mensuales de cuidados requeridos por un conejo son 3 y por un pollo son 2 y que los beneficios que reportaría su venta ascienden a 500 y 300 pesetas por cabeza respectivamente, hallar el número de animales que deben criarse para que el beneficio sea máximo.

Definimos las variables:

X1=número de conejos

X2=número de conejos

La función a maximizar, beneficio obtenido, será:

f(x1,x2)=500X1 + 300X2Las restricciones lineales del problema se formulan como:

20X1 + 10X2 <= 1000

3X1+2X2 <= 180

Finalmente, tenemos las restricciones de no negatividad de las variabes:

X1, X2 => 0

El planteamiento del problema queda, por tanto:

max f(X1, X2) = 500X1 + 300X2

s.a.: 20x1 + 10X2 <= 1000

3X1 + 2X2 <=180

X1, X2 => 0

El siguiente paso consiste en pasar a la forma estándar, esto es, introducir variables de holgura en las dos restricciones verdaderas:

max f(X1, X2) = 500X1 + 300X2

s.a.: 20x1 + 10X2 + X3H <= 1000

3X1 + 2X2 + X4H <=180

X1, X2, X3H, X4H => 0

X1 X2 X3H X4HX1 50 1 ½ ½ 0X4H 30 0 ½ -3/2 1

0 50 -250 0

La solución factible básica inicial es:

X1 = X2 = 0, X3H = 100, X4H = 180

Así obtendremos inicialmente:

Continuando con las iteraciones:

Obtenemos, por tanto, la solución óptima, cuyo valor es:

X1 = 20 conejos, X2 = 60 pollos, Z = 2800 pesetas

Algoritmo del método de la Gran M

También llamado método de la penalización. Este método comienza con la forma estándar, es decir, en forma de ecuación. Consiste en modificar el problema original para dar lugar a un nuevo problema añadiendo variables llamadas artificiales, y que se penalizaran mediante un costo “M” de valores grandes positivos, y esto permite que la función objetivo tome valores muy grandes. “M” significa un coeficiente muy grande o mucho.

Debemos llevar a cabo lo siguiente: Pasar a la forma estándar el modelo matemático. Agregar variables artificiales en las ecuaciones que no tienen variables de holgura. Se deben penalizar las variables artificiales en la función objetivo asignándoles coeficientes

positivos muy grandes. Sea M un número muy grande (en los modelos de minimización la penalización para todas las variables se suma y en los de maximización se resta)

Con la solución inicial artificial se aplica el método simplex, generando las tablas necesarias para llegar a una solución.

NOTA:

Las variables de holgura quedan con coeficiente cero en la función objetivo y las variables artificiales con coeficientes M. Positiva si es minimizando o negativa si se maximiza.

En la primera iteración, debemos seguir la siguiente regla para escoger las variables que estarán en la base:

1. Si hay variables de decisión y de holgura, se toma la de holgura.2. Si se encuentran variables de holgura, artificiales y decisión se toma la artificial.3. Si tenemos variables artificiales y de decisión toma la artificial.

Para definir el pivote:Determinar la variable que entra:¿Cuál es el valor más negativo de Cj-Zj? M representa un número finito, muy, muy grande, por tanto esta variable debe entrar a remplazar a otra variable en la base.Determinar la variable que entra:Hacemos un cociente entre la disponibilidad y la columna de la variable que entra.

Iteración Gauss – JordanLuego que se ha encontrado que variable sale y la que entra, ya tenemos la celda pivote, y ahora necesitamos hacer la eliminación Gaussiana, es decir:

Convertir la celda pivote en 1, dividiendo toda la fila por ella misma. Convertir todas las celdas por encima y por debajo de la celda pivote en cero.

Esta nueva fila que hemos calculado sirve para convertir las demás celdas por la columna del pivote en cero. Para ello hacemos operaciones entre filas y columnas, de la siguiente manera:

Multiplicamos la fila que tenía el pivote por el opuesto de cada número que deseamos eliminar y se lo sumamos a la fila que queremos convertir.

Prueba de optimidadSe debe hacer cada vez que se evalúa si hay una variable que debe entrar a la base. Si hay una variable que mejoraría la solución (esto lo vemos en la fila Cj-Zj), si al calcular esta fila aún hay valores negativos y estamos minimizando, entonces es posible mejorar la solución. Si hay valores positivos en la fila Cj-Zj y estamos maximizando, aún no hemos llegado al óptimo.

Ejemplo:

Una compañía fabrica y vende cinco productos. Se da la siguiente tabla:

A B C D ECosto por unidad 50 80 300 25 10Precio de venta 70 90 350 50 12

Se busca maximizar las utilidades totales, con las siguientes restricciones:

Hay que producir un mínimo de 20 unidades del producto A y 10 del producto B, no se dispone de suficientes materiales para una producción total mayor que 75 unidades; el número de unidades fabricados de los productos C y E deben ser iguales.

Formulación del problema:Función objetivo:Max Z = (70-50)X1 + (90-80)X2 + (350-300)X3 + (50-25)X4 + (12-10)X5Max Z = 20X1 + 10X2 + 50X3 + 25X4 + 2X5

Sujeto a:

X1 >= 20X2 >=10X1 + X2 + X3 +X4 + X5 <= 75X3 + X5 =0(X1 + X2 + X3 +X4 + X5) => 0Estandarización:

Z = 20X1 + 10X2 + 50X3 + 25X4 + 2X5 – MX7 –MX9 –Mx11Z - 20X1 - 10X2 - 50X3 - 25X4 - 2X5 – MX7 –MX9 -Mx11 = 0

X1 – X6 + X7 = 20X2 – X8 + X9 = 10X1 + X2 + X3 + X4 + X5 + X10 = 75X3 – X5 + X11 = 0

Vb X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 biZ -20 -10 -50- -25 -2 0 M 0 M 0 M 0

X7 1 0 0 0 0 -1 1 0 0 0 0 20X9 0 1 0 0 0 0 0 -1 1 0 0 10

X10 1 1 1 1 1 0 0 0 0 1 0 75X11 0 0 1 0 -1 0 0 0 0 0 1 0

Vb X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 biZ -20-M -10-M -50-M -25 -2+M 0 M 0 M 0 M -30M

X7 1 0 0 0 0 -1 1 0 0 0 0 20X9 0 1 0 0 0 0 0 -1 1 0 0 10

X10 1 1 1 1 1 0 0 0 0 1 0 75X11 0 0 1 0 -1 0 0 0 0 0 1 0

Vb X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 biZ -20-M -10-M 0 -25 -52 M 0 M 0 0 50+M -30M

X7 1 0 0 0 0 -1 0 0 0 0 0 20X9 0 1 0 0 0 0 -1 -1 1 0 0 10

X10 1 1 1 1 2 0 0 0 0 1 -1 75

X3 0 0 1 0 -1 0 0 0 0 0 1 0

Vb X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 biZ 0 0 0 -25 -52 -20 20+M -10 -10+M 0 50+M 500

X1 1 0 0 0 0 -1 1 0 0 0 0 20X2 0 1 0 0 0 0 0 -1 1 0 0 10

X10 0 0 0 1 2 1 -1 1 -1 1 -1 45X3 0 0 1 0 1 0 0 0 0 0 1 0

Vb X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 biZ 0 0 0 1 0 6 -6+M 16 -16+M 26 24+M 1670

X1 1 0 0 0 0 -1 1 0 0 0 0 20X2 0 1 0 0 0 0 0 -1 1 0 0 10X5 0 0 0 1/2 1 ½ -1/2 ½ -1/2 ½ -1/2 45/2X3 0 0 1 1/2 0 1/2 -1/2 1/2 -1/2 ½ 1/2 45/2

Solución óptima:

Z = 1670

A = X1 = 20

B = X2 = 10

C = X3 = 45/2

E = X5= 45/2

Para una unidad máxima de 1670 se deben producir 20 unidades del producto A, 10 del B y aproximadamente 23 del producto C y E, no deben producirse unidades del producto D.

Algoritmo Húngaro

El algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo. La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, o el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.

http://es.wikipedia.org/w/index.php?title=Harold_Kuhn&action=edit&redlink=1

El método Húngaro es aplicado con más frecuencia en las áreas de producción de las empresas, para ver cuál de las maquinas en operación puede presentar problemas o algún fallo que afecta a la producción.

Los problemas de asignación incluyen aplicaciones tales como asignar personas a tareas. Aunque sus aplicaciones parecen diferir de las del problema del transporte, constituye un caso particular. Los problemas de transporte y asignación son casos particulares de un grupo más grande de problemas, llamados problemas de flujo en redes.

Suposiciones de un problema de asignación:

1. El número de asignados es igual al número de tareas (se denota por n). (esto puede variar).

2. Cada asignado se asigna exactamente a una tarea.

3. Cada tarea debe realizarla exactamente un asignado.

4. Existe un costo cij asociado con el asignado i (i=1,2,…,n).

5. El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales.

Pasos para resolver un problema:

1. A todos los elementos de cada columna restar el menor elemento de la columna. En la matriz resultante, restar a todos los elementos de cada fila el menor elemento de la fila. Así se garantiza la obtención de por lo menos un cero en cada fila y columna.

2. Con la matriz resultante, verificar la existencia de una solución óptima. Para encontrarla se debe asignar un cero a cada fila (comenzando por las que tengan menor Nº de ceros), y cancelar los demás ceros de esa fila y los ceros de la columna en la que se encuentra ese cero. Repetir esta operación hasta que no queden ceros sin asignar o cancelar. Si no existe solución óptima ir al paso 3.

3. Realizar lo siguiente:

a) Marcar con un * todas la filas que no contengan ceros asignados.

b) Marcar todas las columnas que contengan uno o más ceros cancelados en alguna fila marcada.

c) Marcar toda fila que tenga un cero asignado en una columna marcada.

d) Repetir b) y c) hasta que no sea posible marcar más filas o columnas.

e) Poner un trazo (línea) sobre toda fila no marcada y sobre toda columna marcada.

4. Tomar el menor número no atravesado por un trazo (línea) y:

• Restarlo a todos los elementos de las filas no atravesadas.

• Sumarlo a todos los elementos de columnas atravesadas.

Volver al paso 2.

Ejemplo:

La compañía de manufactura "Jiménez y Asociados" desea realizar una jornada de mantenimiento preventivo a sus tres máquinas principales A, B y C. El tiempo que demanda realizar el mantenimiento de cada máquina es de 1 día, sin embargo la jornada de mantenimiento no puede durar más de un día, teniendo en cuenta que la compañía cuenta con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de mantenimiento a cada máquina para poder cumplir con la realización del mantenimiento preventivo. Teniendo en cuenta que según el grado de especialización el costo de la tarea varía para cada máquina en particular, debe de asignarse el equipo correcto a la máquina indicada con el objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la siguiente tabla:

Máquina 1 Máquina 2 Máquina 3

Equipo de mantenimiento 1 10 9 5



Paso 1: Encontramos el menor elemento de cada columna y restarlo de la columna respectiva.

- En la columna de la Máquina 1, el menor elemento es 6, en la columna de la Máquina 2, es 4, en la columna de la Máquina 3, es 3.




Equipo de mantenimiento 3 0 0 4Encontramos el menor elemento de cada fila en la matriz resultante y restarlo de la fila respectiva.

- En la fila 1, el menor elemento es 2, en la fila 2, el menor elemento es 0, en la fila 3, el menor elemento es 0.




Equipo de mantenimiento 3 0 0 4Paso 2:

Hacemos las asignaciones iniciando por la fila que tenga menos ceros y tachando los ceros de la fila y columna donde hicimos la asignación.





Se puede ver que solo hicimos dos asignaciones, pero debimos haber hecho tres, por lo que no logramos la solución óptima y pasamos al paso 3.

Máquina 1 Máquina 2 Máquina 3 *Equipo de mantenimiento 1 * 2 3 0

Equipo de mantenimiento 2 * 3 4 0


Marcamos con * las filas 1 y 2 y la columna 3. De acuerdo al algoritmo de Húngaro.

Paso 4: El menor elemento de los no atravesados en la matriz es: 2

- Se lo restamos a todos los elementos de las filas no atravesadas.

- Se lo sumamos a todos los elementos de las columnas atravesadas.




Hacemos nuevamente las asignaciones empezando por las filas que tengan menos ceros




El orden en que asignamos es el siguiente:

- Primero asignamos el equipo 2 a la Máquina 3 y tachamos el cero que hay en la columna de la Máquina 3.

- Segundo asignamos el Equipo 1 a la Máquina 1 y tachamos el cero que hay en la columna de la Máquina 1.

- Tercero asignamos el Equipo 3 a la Máquina 1.

La asignación que representa el menor costo para la jornada de mantenimiento indica que el Equipo 1 realice el mantenimiento de la Máquina 1, el Equipo 2 realice el mantenimiento de la Máquina 3 y el Equipo 3 realice el mantenimiento de la Máquina 2, jornada que tendrá un costo total de 17 unidades monetarias.

Método Simplex de 2 Fases

Esta estrategia algorítmica se aplica cuando luego de llevar un modelo de programación

lineal a su forma estándar no se dispone de una solución básica factible inicial.

Este es otra variante del simplex que se aplica para resolver modelos que requieren una

matriz unitaria de base artificial para poder iniciar el algoritmo. El nombre indica que consiste de

dos fases:

Fase 1: Consideramos un problema auxiliar que resulta de agregar tantas variables auxiliares a

las restricciones del problema, de modo de obtener una solución básica factible. Luego se debe

resolver utilizando el Método Simplex un nuevo problema que considera como función objetivo la

suma de las variables auxiliares. Si el valor óptimo alcanzado al finalizar la Fase 1 es cero ir a la

Fase 2. En caso contrario, no existe solución factible.

Fase 2: Resolver a través del Método Simplex el problema original a partir de la solución básica

factible inicial hallada en la Fase1.

Ejemplo:

Considerando el siguiente modelo:

Max 2X1 – 3X2

Sujeto a:

-X1 + X2 >= 10

X1 >= 0, X2 >= 0

FASE 1: Al agregar S1 como variable de exceso en la restricción 1 resulta evidente que no se

dispone de una solución básica factible inicial, por tanto utilizaremos una variable auxiliar "y"

que incluiremos en el lado izquierdo de la restricción y que servirá como variable básica inicial.

Esto define el problema inicial de la Fase 1 junto a su tabla.

Minimizar y

Sujeto a:

-X1 + X2 – S1 + Y = 10

X1, X2, S1, Y >= 0

X1 X2 S1 Y

-1 1 -1 1 10

1 -1 1 0 -10

Luego la variable X2 entra a la base (costo reducido negativo) y claramente "y" deja la base. Se

actualiza la tabla utilizando el método simplex:

X1 X2 S1 Y

-1 1 -1 1 10

1 0 0 1 0

Con esta tabla finaliza la Fase 1. Notar que el valor de la función objetivo al finalizar la Fase 1 es

cero, por tanto podemos continuar la Fase 2.

FASE 2: Se elimina la columna asociada a la variable artificial "y" y se actualiza el vector de

costos reducidos considerando la función objetivo original. De esta forma se obtiene la tabla

inicial de la Fase 2.

Dado que X2 es variable básica al finalizar la Fase 1 buscamos dejar esta misma variable como

básica al iniciar la Fase 2. Para ello multiplicamos por -3 la fila 1 y luego la sumamos a la fila 2.

En este sencillo ejemplo se llega inmediatamente a la tabla final de la Fase 2, con solución

óptima X1=0 y X2=10. El valor óptimo V(P)=-30.

X1 X2 S1 Rec

-1 1 -1 10

-2 3 0 0

X1 X2 S1 Rec

-1 1 -1 10

1 3 0 30

Documents

Algoritmos especiales