Optimización Matemática: Métodos y Técnicas Esenciales

Solución Óptima de Vogel: 1. Poner la tabla de solución. n(fila) + m(columna) -1=... = valores de la tabla. Si no es igual, solución degenerada -> añadir ∅ en cualquier hueco. 2. Lo mismo que el otro

Vogel: 1. Poner la demanda (←) y la oferta (↑) 2. Equilibrar (sumar la demanda y la oferta), si hace falta añadir fila o columna 3. Calcular Zdj (←) y Edi (↑). Hacer la diferencia entre los dos números más pequeños de cada fila y columna. 4. Coger la diferencia mayor entre Zdj y Edi (solo una), de esa fila o columna pillar el elemento mínimo. 5. Pillar el mínimo entre la demanda y la oferta, x12=min{4,8}=4 a1=8-4=4 b2=4-4=0 6. Poner el mínimo antes en la tabla de la solución 7. Borrar la fila o la columna que ha dado 0 y volvemos a sacar Zdj y Edi 8. Volver a hacer el proceso

Gráficamente:1. Dibujar las restricciones, sustituyendo valores x2(↑) x1(→) 2. Dibujar la función objetivo y luego hacer la derivada para sacar el punto A 3. El punto más lejano hacer la intersección entre las dos líneas

Plantear el problema dual y la holgura complementaria: 1. Poner el problema primal y su solución. Luego hacer la inversión (cambiar la función objetivo) 2. Las soluciones del problema primal por las variables de holgura que van a dar igual a 0 y las otras (u1,u2,u3*0=0) 3. Resolver el sistema de ecuaciones del último

Bifase: 1. Plantear el problema 2. 1ª Fase: cambiar a max o min. (>= o =)-> +q1 y función objetivo= solo poner q1+q2.... Resolver el problema hasta que la Z=0 y la Zj de las q sean 0 3. 2ª Fase: coger la última tabla y quitar las columnas de las q1,q2... y poner la función objetivo del principio. Resolver hasta el final.

Penalización: Poner en la función objetivo -Mq1 y en la restricción (>=)-> -x5+q1 (=)-> +q1

Cambiar la función objetivo: Coger la última tabla y cambiar arriba por la nueva función objetivo. Volver a hacer la tabla hasta llegar a la solución.

Añadir una restricción: Poner el planteamiento anterior y sus soluciones. Poner la nueva restricción y sustituir los valores por la solución (si se cumple la restricción se cumple la solución óptima) (si no se cumple añadir la restricción a la última tabla y calcular todo)

Rango de sensibilidad: Pillar de la última tabla la matriz de la identidad matricial del principio, y multiplicar por las variables libres nuevas >= 0. Luego sacar el rango

Restricción Activa: las variables que en la solución = 0. Poner las restricciones de esa variable de holgura Restricción No Activa: las variables que no dan 0 en la solución. Poner las restricciones de esa variable de holgura

Simplex: ( A=() , Xb=()=B^-1*b=(), Xn=() ) Wj Criterio de entrada= min/max{Wj /Wj Criterio de salida = min {Xbk/Ykj /Ykj>0}

Simplex Dual: Criterio de salida= max{Xbk / Xbk Criterio de entrada= min{|Wj|/|aik| /aik

Flujo Máximo: 1. F=0 y Xij=0 2. Copiar el grafo y poner el camino 3. Δ = min {min(Kij – Xij), min Xij}= min{(9-0),...} 4. F=F+Δ y sobrescribir el grafo 5. Corte mínimo= C(P,P^c)=F

Ramificación y Acotación (Adartze-bornatze): 1. Hacer simplex (S/I) normal 2. Cuando lleguemos al final, poner la solución del P1(x1= , x2= ,Z1= ) y abrir dos ramas, el x1=3,5 pues rama 1: x1=4 3. Añadimos dos problemas, cada uno con su restricción nueva 4. Resolver los dos problemas nuevos, añadiendo a la última tabla la restricción nueva. Tener cuidado de que se cumpla la identidad matricial. 5. Cuando perdamos la factibilidad (-) utilizar simplex dual (I/S) 6. Cuando el problema sea no acotado, no seguir 7. Cuando el B^-1*B nos dé un número entero, no seguir 8. Si es max la z mayor. Si es min la Z menor

Solución Óptima Noroeste: 1. Poner u(←) y v(↑) 2. Poner las ecuaciones: ui + vi – cj (valores originales)=0 / v1=0 3. Hacer tabla u= (←) y v= (↑). Zij/Wij Zij = u1+v1, u1+v2... Wij= Z – valor original 4. Wj > 0, por lo tanto no es óptima. W32=4 -> x32 entra en la base (se coge el más grande de los positivos) 5. Poner nueva tabla y poner la t en la base que entra, sumar y restar alrededor 6. Solución= x11 (de la tabla de la t)= valor,... Z=los valores * los valores originales

Esquina Noroeste: 1. Poner la demanda (←) y la oferta (↑) 2. Equilibrar (sumar la demanda y la oferta), si hace falta añadir fila o columna 3. Borrar los valores del medio de la tabla, pillar el ↑↓ y poner el mínimo entre la demanda y la oferta. 4. 1.Paso: (1,1) / 2.Paso: x11=min{15-25}=15, b1=15-15=0, a1=25-15=10/ 3.Paso: (1,2) 5. Poner el camino: x11=15

Método Húngaro: 1. Está equilibrado 2. Restar el mínimo de la fila y poner u=... 3. Restar el mínimo de la columna y poner v=... (0 también cuenta) 4. Pillar la fila o columna con menos 0 y marcamos ese 0. Después borrar los otros 0 de la fila y columna. (1,1) asignar -> (1,4),(1,6) eliminar 5. Marcar la fila sin [0] asignado → 5.1. De la fila que hemos marcado, marcar las columnas donde se hayan borrado los

↑ 5.2. Marcar las filas donde tengamos [0] asignados de las columnas marcadas → 5.3. Borrar las filas NO marcadas y borrar las columnas marcadas ↱ ↰ 6. -1 en las filas NO borradas (0 incluido) / +1 en las columnas borradas 7. Repetir el 4º paso y si están todas las filas con un [0] asignado, acabado. 8. 1.Fábrica -> 1.Trabajo ….

Floyd: 1. Tabla de distancias (el grafo) y Matriz de Recorridos (-,1,1,1). 2. k=1... d23=min(d23, d21+d13)=(2, ∞)= 2 (los 0 no coger) 3. Volver a poner las tablas.