METODOS NUMERICOS
Ingeniería Civil
ING.�CRISTIAN�CASTRO�P.
Facultad de Ingeniería de Minas, Geología y Civil
Departamento académico de ingeniería de minas y civil
CATEDRA 10
SistemaSistemaReal MODELO
ImplementaciónImplementaciónResultados DecisiónDecisiónfinal
Decisiónóptima
Comparación(+) o ( -)
Ajustes
•Variables de decisión•Parámetros y constantes•Función de optimización: Max/Min•Ecuaciones de restricción
¿Cuál es la estructura del modelo matemático?
¿Qué es un modelo?
• Una representación abstracta de…
• …ciertos aspectos de la realidad• No todos los elementos de ella (¡esto no es posibl
e!)
• Estructura basada en elementos seleccionados de la realidad• Elementos elegidos para un propósito particular• Para dar respuesta a un interrogativo en particular
R l i t l l t
¿Qué es PL?• Un tipo de modelo matemático específico
Maximiza o minimiza una cantidad específica, a través de
Selección de valores para las variables,
Sujeto a una o más restricciones,
• Todas las ecuaciones son lineales
DefinicionesVariables de decisión: Decisiones cuantificables relacionadas unas con otras. Ejemplo: Cuánto comprar, venderFunción objetivo:La medida de efectividad compuesta expresada como una función de las variables de decisión. Puede ser Maximizar o MinimizarParámetros:Valores constantes que actúan como coeficientes al lado derecho de las variables tanto en la función objetivo como en las restricciones y que se basan en datos tecnológicos de los problemas. Ejemplo fijar tasa inflación
Restricciones:Limitaciones impuestas sobre los valores de las variables de decisión, casi siempre en forma de ecuaciones o desigualdades. Pueden = / /
Max Z = 3X1 + 2X2
Sujeto a:4X1 + 11X2 = 23X1 - 2X2 200
X1, X2 0
• Fermat (1646) Newton (1670)
• Euler (1755)
• Lagrange (1797)
( ) funcion de una sola variable
0
f xdf(x)dx
=
( ) funcion vectorial( ) 0x
f xf xÑ =
xmin ( ) x vector
subject to : ( ) 0, 1k
f x
g x k ,....,m=
Desarrollos claves para la optimización.
INTRODUCCIÓN
• Dantzig (1947) Programación lineal(Restricciones con desigualdades)
• Kuhn Tucker (1951)Condiciones a satisfacer por una optimización no lineal
• Contribuciones (1960-80s) Algoritmos para optimización nolineal
• Khachain and Karmarkar (~1980) Nuevo métodos de puntosinteriores
• Desarrollos continuados en diferentes problemas(optimización entera, estocástica, global, etc.) –
Actualmente sigue con un gran desarrollo
Desarrollos clave de la segunda mitad del siglo XX
INTRODUCCIÓN
Y muchos más!
Matemática aplicada
Gestión de negocio
Ingeniería de software
Ingeniería civil
• Programación matemáticaInvestigación operativaIncluye estadística, modelado, etc.
• Optimización aplicadaTodas las áreas de ingeniería
• Planificación y logísticaGestión de la cadena de sumi-nistro, gestión de recursos.
Quién hace optimización?
INTRODUCCIÓN
¿Cuál es la característica principal de los problemas de optimización?
Característica principal
Hay un compromiso entrelas variables y el objetivo.
Hay que identificar estoscompromisos antes dedesarrollar los modelosmatemáticos.Hay que entender el problemacualitativamente antes deresolverlo cuantitativamente.
Cos
tes
ener
gía
(alta) Pureza producto (baja)
Cos
tes
prod
ucto
(-va
lor)
Coste total
Optimo
Dos opciones para realizar la optimización
Optimización basada en modelos
Optimización
empírica• Debe de existir un proceso• Necesita experimentos (suelen
ser costosos)• No hay retraso por el modelo• Se puede llevar a cabo sin
modelo• Lenta
• Se puede investigar un nuevo proceso
• No se necesitan experimentos• Se requiere un modelo (puede
necesitar experimentos en su desarrollo)
• Rápida• Depende de la exactitud del
modelo
Aplicaciones típicas – desarrollo rápido de procesos poco entendidos
• Farmacéutica• Micro-electronica• Aplicaciones pequeñas en ope
ración de planta
Aplicaciones típicas – sistemas para los que existe un buen modelo
• Componentes gases y líquidos en industrias químicas y petroquímicas
• Aplicaciones de negocio para inventario, transporte,…
• En aquellos sitios donde no se permite experimentar
INTRODUCCIÓN
Optimización basada en modelos
Decisiones a tomar modelo
Método de resolución y software
Solución
La formulación y el método de resolución permiten la solución
Es importante ver los efectos de un error
del modelo en la solución
De sencillo a muy complejo
De fácil a imposible (hoy)
EL PROBLEMA Y SU SOLUCIÓN
Opciones para la resolución de optimización basada en modelos
1.
2.
3.
Soluciones gráficas
Soluciones analíticas (Newton, Euler, etc.)
Métodos numéricos
EL PROBLEMA Y SU SOLUCIÓN
Opciones para la resolución de optmización basada en modelos
Gráfica
Variable, x
Func
ión
obje
tivo,
f(x)
Comenta:
• Ventajas
• Desventajas
Dónde está el óptimo
EL PROBLEMA Y SU SOLUCIÓN
Opciones para la resolución de optmización basada en modelos
Analítica
2
2
( ) con x unica variable
0
( ) 0
f xdf(x)dx
d f xdx
=
>
EL PROBLEMA Y SU SOLUCIÓN
Comenta:
• Ventajas
• Desventajas
Opciones para la resolución de optmización basada en modelos
Numérica
min max
min ( ). .( ) 0( ) 0
xf x
sth xg xx x x
=≤
EL PROBLEMA Y SU SOLUCIÓN
Comenta:
• Ventajas
• Desventajas≤ ≤
ALGUNOS EJEMPLOS DE OPTIMIZACIÓN3. Economía: Logística / Gestión de la cadena de
Storage
Rawmaterials Plant
Plant Which raw material?
Which plant (different yields, etc.)
How much inventory?
What routes and modes used for transportation?
How much inventory?
Definición y elementos.Definición.• Optimización es el método matemático para determinar los
valores de las variables que hacen máximo el rendimiento de unproceso o sistema.(Diccionario de la Real Academia).
• Elementos1. Función de coste o Criterio
(Funcional objeto, índice de comportamiento).1. Modelo del sistema o proceso.2. Restricciones.
Criterio Decisión
J(x) es una función escalar de una variable vectorial)1,0( xxx oIoRRJ nn
¿Cuándo es óptimo un sistema?
• Un sistema es óptimo(máximo) cuando la decisión x* es tal queel criterio J(x*)>J(x) para cualquier otra decisión x tomada.
Si en vez de máximo es mínimo el símbolo > cambiaría por el de <.• Si el criterio depende del error del sistema (diferencia entre
valores deseados y reales) este criterio debe ser de tipo par(igual ponderación a errores positivos que negativos).Funcionespares típicas son las cuadráticas o las del módulo del error.
Motivaciones y limitaciones.
• 1) Ventas limitadas por la producción.• 2) Ventas limitadas por el mercado.• 3) En las grandes unidades pequeños ahorros en la producción se magnifican enormemente.
Ej: industria de refinerías.• 4) Alto consumo de energía y materias primas.• 5) Calidad en la producción.• 6) Pérdidas en componentes valiosos en los efluentes, emanaciones, contaminación,etc.• 7) Altos costes laborales y fiscales.•• La optimización completa de una planta química es una tarea compleja. Suboptimización y
niveles jerárquicos.
• Ejemplos. Proyectos típicos donde se usa la optimización:•• 1) Determinación de los mejores lugares para la ubicación de una planta.• 2) Camino de distribución óptimo de productos refinados.• 3) Tamaño de un gaseoducto /oleoducto.• 4) Diseño y equipamiento de una planta.• 5) Mantenimiento y planificación en la reposición de equipos.• 6) Operaciones en equipos, reactores, columnas, etc.
CLASIFICACIÓN DE LOS PROBLEMAS DE OPTIMIZACIÓN
• 1.- Optimización estática.• 1.1 Problemas sin restricciones• 1.2 Problemas con restricciones
• 1.2.1 Programación lineal• 1.2.1 Programación no lineal
• 1.2.1.1.Programación geométrica• 1.2.1.2. Programación entera y mixta • 1.2.1.3. Programación estocástica
• 2.- Optimización dinámica.• 2.1 Problemas lineales• 2.2 Problemas no lineales
• 3. Programación dinámica.• Redes/grafos• Control óptimo
• 4.- Problemas complejos.Jerarquía y coordinación.
PROCEDIMIENTO PARA RESOLVER PROBLEMAS DE OPTIMIZACIÓN
• 1.-Analizar el proceso. Variables y características bien definidas.
• 2.-Determinar el criterio de optimización o función objetivo de lasvariables del proceso.
• 3.-Obtener las relaciones entre las variables(modelo matemático)tanto igualdades como desigualdades.Utilizar principios de conservación, relaciones empíricas, implícitasy restricciones externas.
• 4.-Si el problema es muy amplio• Separarle en partes más abordables.• Simplificar la función objetivo o el modelo.
5.-Aplicar una técnica de optimización adecuada al problema.
6.-Comprobar el resultado y examinar la sensibilidad a los cambiosen los coeficientes.
Métodos y algoritmos de optimización básicos
• Teoría ordinaria de máximos y mínimos.• Métodos analíticos• Métodos numéricos.• Búsquedas unidimensionales y multidimensionales.• Método del gradiente
• Método de los multiplicadores de Lagrange• Programación lineal• Programación no lineal• Programación entera-mixta• Programación dinámica• Cálculo de variaciones
La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene porobjeto ayudar a los responsables en las decisiones sobreasuntos en los que interviene un gran número de variables
El nombre de programación lineal no procede de lacreación de programas de ordenador, sino de un términomilitar, programar, que significa 'realizar planes o propuestas de tiempo para el entrenamiento, la logística o eldespliegue de las unidades de combate'.
Aunque parece ser que la programación lineal fueutilizada por G. Monge en 1776, se considera a L. V.Kantoróvich uno de sus creadores. La presentó en su libroMétodos matemáticos para la organización y laproducción (1939) y la desarrolló en su trabajo sobre latransferencia de masas (1942). Kantoróvich recibió elpremio Nóbel de economía en 1975 por sus aportacionesal problema de la asignación óptima de recursos humanos
La investigación de operaciones en general y laprogramación lineal en particular recibieron un granimpulso gracias a los ordenadores. Uno de momentos más importantes fue la aparición del método del simplex.Este método, desarrollado por G. B. Dantzig en 1947,consiste en la utilización de un algoritmo para optimizar elvalor de la función objetivo teniendo en cuenta las restricciones planteadas.
¿Qué es la programación lineal?• Es una técnica matemática:
• No es un programa de computador.
• Reparte los escasos recursos para alcanzar los objetivos.
• Fue creado por George Dantzig durante la Segunda Guerra Mundial:• Desarrolló una solución práctica en 1947.
• Se denominó método Simplex.
¿ QUE HACER Y EN QUE CANTIDAD?
FORMULACIÓN DE MODELOS MATEMÁTICOSDE PROGRAMACIÓN LINEAL
-formulación directa-
La modelación se define como el proceso de abstraccióndel sistema real a un modelo cuantitativo.Involucra desde la definición del sistema real y la deter-minación de sus fronteras, incluyendo la conceptualiza-ción del sistema asumido.
La modelación es sin duda una combinación de arte yciencia.No se puede precisar una metodología para la construc-ción de un modelo, por lo que necesariamente la modelación se aprende con la práctica.
Modelo general de PLoptimizar (maximizar o minimizar)
Z = c1x1 + c2x2 +....+ cnxn,
sujeta a las restricciones:
a11x1 + a12x2 +....+ a1nxn < b1
a21x1 + a22x2 +....+ a2nxn < b2
.
am1x1 + am2x2 +....+ amnxn < bm
donde el valor de las variables es:
X1 0, X2 0, ..., Xn 0
1. EL OBJETIVO
Con el objetivo se pretende medir la efectividad de lasdiferentes soluciones factibles que pueden obtenersey determinar la mejor solución.Deberá definirse claramente las unidades de medicióndel objetivo, como dinero, tiempo, etc.
2. LAS VARIABLES DEDECISIÓN
Son las incógnitas del problema y básicamenteconsisten en los niveles de todas actividadesque pueden llevarse a cabo en el problema aformular.Estas pueden ser de tantos tipos diferentescomo sea necesario.En la mayoría de los problemas a formularla definición de las variables es el puntoclave.
3. LAS RESTRICCIONES ESTRUCTURALES
Son diferentes requisitos que debe cumplir cualquiersolución para que pueda llevarse a cabo. En ciertamanera son las limitantes en los valores de los nivelesde las diferentes actividades (variables).Las restricciones más comunes son:
Restricciones de capacidad. Limitan el valor de lasvariables debido a la disponibilidad de horas-hombre,horas-máquina, espacio, etc.
Restricciones de mercado. Surgen de los valoresmáximos y/o mínimos de la demanda o el uso delproducto o actividad a realizar.
Restricciones de entradas. Son limitantes debido ala escasez de materias primas, mano de obra, dinero,etc.Restricciones de calidad. Son las restricciones quelimitan las mezclas de ingredientes, definiendo usual-mente la calidad de los artículos a manufacturar,mezcla de ingredientes, etcRestricciones de balance de materiales. Estos sonlas restricciones que definen la salidas de un procesoen función de las entradas, tomando en cuenta ciertoporcentaje de merma o desperdicio.
LAS RESTRICCIONES ESTRUCTURALES
Se establece el valor factibles de las variables dedecisión. Para fines de la programación lineal seestablece que todas las variables deben tomarvalores positivos.En caso de formular problemas en donde seanecesario valores negativos en las variables seemplean las variable irrestrictas.
4. LAS CONDICIONESTÉCNICAS
Ejemplos – Casos de algunas aplicaciones de PL con éxito
• Programar los autobuses escolares para minimizarla distancia total que se recorre cuando se trans-porta a los estudiantes.
• Asignar unidades de patrulla de la policía a laszonas con un mayor nivel de criminalidad paraminimizar el tiempo de respuesta a las llamadasdel 091.
• Programar los cajeros de los bancos para que secubran las necesidades durante todo el díamientras que se minimiza el costo total de manode obra.
Ejemplos – Casos de algunas aplicaciones de PL con éxito
• Elegir materias primas en procesos de alimentaciónpara obtener mezclas con unas determinadas pro-piedades al mínimo coste.
• Seleccionar el mix de producto en una fábrica parautilizar las horas del trabajo las máquinas y demano de obra disponibles de la mejor forma posible,maximizando el beneficio de la empresa.
• Asignar espacio al mix de arrendatarios de unnuevo centro comercial para maximizar los ingresosa la compañía arrendadora.
Requisitos de un problema de programación lineal
1 Los problemas de PL deben buscar maximizar ominimizar una cantidad (la función objetivo).
2 La presencia de restricciones limita el grado enque podemos perseguir el objetivo.
3 Deben existir diferentes alternativas donde poderelegir.
4 La función objetivo y las restricciones de la PLdeben ser expresadas en ecuaciones lineales.
Ejemplos.Tráfico y economía.1.-Dos ciudades Ay B (o dos puntos dentro de una población).Se desea ir de A a B escogiendo:• Tiempo mínimo.• Distancia mínima.• Pasando por un punto intermedio C.• En cada caso podemos encontrar soluciones diferentes.• Concepto medible en el problema. OBJETIVO, INDICE o CRITERIO.
2.-Queremos invertir dinero en diferentes productos bancarios escogiendo:• Máximo crecimiento del capital.• Máximo interés de la cantidad invertida.• Mínimo riesgo en la inversión.• Las soluciones son evidentemente distintas en cada caso.
• Si el objetivo es I o J existe una relación inmediata entre máximo ymínimo, propia de los números reales:
Max (J) =Min (-J)
Ejemplos.Funciones objetivo.
Máximo.
• EconomíaBeneficioRendimientoEficacia
TráficoVelocidad
QuímicaConcentración
Mínimo
• EconomíaCosteRiesgo
TráficoTiempoDistancia
QuímicaEnergía
• Control• Desviaciones de los
puntos de consigna• Tiempo• Energía
• Formulación general.
• Soluciones• Factibles. Cumplen las restricciones.• Básicas.n-m variables del vector de decisión son nulas• Óptimas
• Teoremas.• 1.- Si existe una solución factible existe una solución factible básica
.• 2.- Si existe una solución factible básica existe una solución factible
básica óptima.• Interpretación geométrica.
• Las restricciones forman una región convexa.• Las soluciones básicas son los vértices de esa región convexa.
nmmxnxmxnasujetof
),1(),1(),()(min
bxAbAxxcx T
Programación Lineal
Programación Lineal
• La palabra “programación” se usa aquí en el sentido de “planificación”
• Un problema de programación lineal es aquel donde la función objetivoes lineal en las incógnitas y las restricciones consisten en igualdadeslineales y desigualdades lineales
• Forma general de un problema de programación lineal:
Minimizar C1x1 + C2x2 +…+ Cnxn
tal que a11x1 + a12x2 +…+ a1nxn = b1
a21x1 + a22x2 +…+ a2nxn = b2
an1x1 + an2x2 +…+ annxn = bn
y x1 ≥ 0; x2 ≥ 0; … ; xn ≥ 0Donde las bi, ci y aij son constantes reales, y las xi son número reales que se quieren determinar
Programación lineal• La formulación se hace de forma tal que bi ≥ 0, de ser necesario un
a restricción puede ser multiplicada por -1 para que esto se cumpla• Usando notación vectorial, la forma general de un problema de
programación lineal se expresa como:
Minimizar cTxtal que Ax = by x ≥ 0
Donde x es un vector columna n-dimensionalcT es un vector fila n-dimensionalA es una matriz mxnb es un vector columna m-dimensional
Programación lineal• Otras formas de programas lineales pueden ser convertidos a la
forma general, según los siguientes casos
Caso 1: el problema tiene restricciones de desigualdades linealesMinimizar C1x1 + C2x2 +…+ Cnxn
tal que a11x1 + a12x2 +…+ a1nxn b1
a21x1 + a22x2 +…+ a2nxn b2
am1x1 + am2x2 +…+ amnxn bm
y x1 ≥ 0; x2 ≥ 0; … ; xn ≥ 0
Programación linealCaso 1:el problema puede ser expresado alternativamente como:
Minimizar C1x1 + C2x2 +…+ Cnxn
tal que a11x1 + a12x2 +…+ a1nxn + y1 = b1
a21x1 + a22x2 +…+ a2nxn + y2 = b2
am1x1 + am2x2 +…+ amnxn + ym = bm
y x1 ≥ 0; x2 ≥ 0; … ; xn ≥ 0
y y1 ≥ 0; y2 ≥ 0; … ; ym ≥ 0
• Las variables positivas yi introducidas para convertir las desigualdades en igualdades son llamadas variables de holgura (slacks)
Programación lineal
Caso 1:
• Ahora el problema tiene n+m incógnitas, xi, yj, y está expresado enla forma general
• La matrix m x (n+m) que describe las restricciones de igualdadeslineales es de la forma especial [A,I]
• Sus columnas pueden ser separadas en dos conjuntos; las primeras n columnas forman la matriz original A y las últimas m columnasforman una matriz identidad mxm
Programación lineal
• Caso 2: Variables libres
Cuando el problema lineal es dado en la forma general, con laexcepción de que una o más variables incógnitas no tiene larestricción xi ≥ 0 (puede ser negativa), el problema puede sertransformado a la forma general por dos técnicas
• 1ra técnica: se sustituye la variable sin restricción de signo por dosvariables, de forma tal que estas variables si tengan la restricción,de la siguiente forma:• suponiendo que x1 es libre de tomar valores positivos y negativosx1 = u1 – v1
Donde se requiere que u1 ≥ 0 y v1 ≥ 0• De esta forma se sustituye x1 por u1 y v1 en la función objetivo y en
las restricciones, preservándose la linealidad de las restricciones• Ahora el problema es expresado en términos de n+1 variables
Programación lineal• Ejemplo 2: Variables libres
2da técnica: se elimina la variable sin restricción de signo junto con alguna de las restricciones de igualdad en la cual el coeficiente de la variable sin restricción es diferente de cero
• Luego, la variable sin restricción puede ser expresada como una combinación lineal de las demás variables más una constante
• suponiendo que x1 como la variable libre
ai1x1 + ai2x2 +…+ ainxn = bi donde ai1 ≠ 0
x1 = (-ai2x2 - … - a1nxn + bi)/ai1
• Si ésta expresión es sustituida por x1 se obtiene un problema de lamisma forma pero expresado en términos del resto de las variables(n-1)
Programación lineal
• Ejemplo 2: Variables libres2da técnica: Ejemplo
Minimizar x1 + 3x2 + 4x3
sujeto a x1 + 2x2 + x3 = 52x1 + 3x2 + x3 = 6x2 ≥ 0; x3 ≥ 0
• Despejando x1 de la primera restricción x1 = 5 - 2x2 - x3
• Sustituyendo el problema queda como
Minimizar 5 + x2 + 3x3
sujeto a x2 + x3 = 4x2 ≥ 0; x3 ≥ 0
Soluciones básicas• Considerando el sistema de restricciones de igualdades
Ax = bDonde, x es un vector columna n-dimensional (incógnitas)
b es un vector columna m-dimensional (restricciones)
A es una matriz mxn• Suponiendo que de las n columnas de A se selecciona un conjunto
de m columnas linealmente independiente (tal conjunto existe si elrango de A es m)
• Asumiendo que se seleccionan las primeras m columnas de A paraformar una matriz mxm denotada por B
• Ahora la matriz B es no singular y se puede obtener una soluciónúnica del sistema lineal BxB = b, para el vector xB m-dimensional
• Fijando los primeros m componentes de x igual a xB y el resto de loscomponentes igual a cero, x = (xB, 0), se obtiene una solución aAx = b lo que conlleva a la siguiente definición
Soluciones básicas
• DEFINICIÓN: dado un conjunto de m ecuaciones lineales con nincógnitas, sea B cualquier submatriz mxm no singular formada porcolumnas de A
Entonces, si todos los n-m componentes de x no asociados con lascolumnas de B se igualan a cero, la solución del conjunto deecuaciones resultantes se dice que es una solución básica de Ax=bcon respecto a la base B
Los componentes de x asociados con columnas de B son llamadasvariables básicas
• En general Ax=b puede no tener soluciones básicas
Soluciones básicas
• Para evitar dificultades más adelante hacemos ciertas suposicionescon respecto a la estructura de la matriz A:
1. Se asume que n > m (el número de variables es mayor que lasrestricciones)
2. Las filas de A son linealmente independientes. De otra forma setendrían restricciones contradictorias y por lo tanto no habríasolución
• Bajo estas suposiciones el sistema Ax = b siempre tendrá unasolución, de hecho, siempre tendrá al menos una solución básica
Soluciones básicas
• DEFINICIÓN: si una o más de las variables básicas de una soluciónbásica es igual a cero, se dice que es una solución básicadegenerada
• Considerando ahora el sistema de restricciones, Ax = b, x ≥ 0, loscuales son las restricciones de un problema lineal en su formageneral
• DEFINICIÓN: se dice que un vector x que satisface estas restricciones es factible.
Una solución factible a estas restricciones que también es unasolución básica se dice que es una solución básica factibleSi la solución también es una solución básica degenerada entonceses llamada solución básica degenerada factible
Teorema fundamental de optimización lineal
• El teorema muestra que sólo es necesario considerar solucionesbásicas factibles cuando se está buscando una solución óptima aun problema lineal, debido a que el valor óptimo siempre seencuentra en una solución básica factible
• Considerando un problema lineal en su forma general
Minimizar cTx
Sujeto a Ax = b
y x ≥ 0
• La solución factible, según las restricciones, que tiene el mínimovalor de la función objetivo es una solución factible óptima
• Si ésta solución es básica es una solución básica factible óptima
Teorema fundamental de problemas lineales
!!!
mnmn
• Dado un problema lineal en su forma general donde A esuna matriz mxn de rango m,
1. Si existe una solución factible, existe una soluciónbásica factible
2. Si existe una solución factible óptima, existe unasolución básica factible óptima
• Este teorema reduce la tarea de resolver un problema lineala la búsqueda sobre soluciones básicas factibles
• Debido a que un problema con n variables y m restriccionestiene tantas soluciones básicas como número de formas deseleccionar m de n columnas, se tiene un número finito deposibilidades
• Sin embargo, esto sería una técnica de búsqueda muyineficiente
Interpretación geométrica del teorema fundamental de problemas lineales
• El enlace principal entre las teorías algebraica y geométrica estáen la relación existente entre una solución básica factible de lasrestricciones lineales en su forma general y los puntos extremosdel politopo formado por las restricciones (2D polígono,3D poliedro)
• Primero definimos que es un punto extremo:
Teorema de equivalencia de puntos extremos y soluciones básicas
• Sea A una matriz mxn de rango m y b un vector m-dimensional• Sea k el politopo convexo formado por todos los vectores x que
satisfacen las restricciones Ax = b, x ≥ 0• Un vector x es un punto extremo de k si y solo si x es una solución
básica factible de las restricciones
Propiedades de los politopos convexos
• Ejemplo 1: Considerando las restriccionesx1 + x2 + x3 = 1x1 ≥ 0; x2 ≥ 0; x3 ≥ 0
el conjunto tiene tres puntos extremos, que corresponden a las tres soluciones básicas de x1 + x2 + x3 = 1
x1
x3
x2
Propiedades de los politoposconvexos
0,1,211
3211
2
1
xx
• Ejemplo 2: Considerando las restriccionesx1 + x2 + x3 = 12x1 + 3x2 = 1x1 ≥ 0; x2 ≥ 0; x3 ≥ 0
el conjunto tiene dos puntos extremos correspondientes a las dos soluciones básicas de factibles
21,0,
21
11
0211
3
1
xx
32,
31,0
11
0311
3
2
xx
No factible
Factible
Factiblex1
x3
x2
Propiedades de los politopos convexos
0;032
2
438
21
1
21
21
xxx
xx
xx
• Ejemplo 3: Considerando las restricciones
• Por inspección este conjunto tiene 5puntos extremos
• Para llevar este problema a la formageneral es necesario introducirvariables de holgura
0;0;0;0;032
2
438
54321
51
421
321
xxxxxxx
xxx
xxx
0 0.5 1 1.5 2 2.5 30
0.5
1
1.5
2
2.5
3Restriccion x3 = 0Restriccion x4 = 0Restriccion x5 = 0
x 1=0
x2=0
x5 =0
Propiedades de los politoposconvexos
• Ejemplo 3: Considerando la función objetivo:-2x1 – x2
• Las soluciones básicas se determinan haciendo dos variablescualquiera cero, y resolviendo el sistema para las tres restantes
0 0.5 1 1.5 2 2.5 30
0.5
1
1.5
2
2.5
3Restriccion x3 = 0Restriccion x4 = 0Restriccion x5 = 0
-8
-7
-6
-5
-4
-3
-2
-1
Método Simplex – Ejemplo
Solución óptimax1 = 1.5x2 = 0.5
factores = A(1:3,6)./A(1:3,q) %yi0/yiq
factores =
0.9375
0.5000
Inf
sale variable basica 2 p = 2
% pivoteo sobre el elemento pq = 22
A(p,:)=A(p,:)/A(p,q)
A(1,:)=A(1,:)-(A(1,q)*A(p,:))
A(3,:)=A(3,:)-(A(3,q)*A(p,:))
A(4,:)=A(4,:)-(A(4,q)*A(p,:))
0 0 1.0000 -2.6667 0.8333 1.1667
0 1.0000 0 1.0000 -0.5000 0.5000
1.0000 0 0 0 0.5000 1.5000
0 0 0 1.0000 0.5000 3.5000
0 0.5 1 1.5 2 2.5 30
0.5
1
1.5
2
2.5
3Restriccion x3 = 0Restriccion x4 = 0Restriccion x5 = 0
-8
-7
-6
-5
-4
-3
-2
-1
Valor de la función objetivo en el punto óptimo F(1.5,0.5) = -3.5
PROGRAMACIÓN LINEAL
• Método simplex.• Ejemplo. Forma estándar
• Forma canónica inicial Iteración 1 Iteración 2
• Esta solución es la óptima porque todos los coeficientes del costo sonpositivos
0x,0 x 2x x 1xx
3xx
21
21
21
21
asujeto
fMaximizar
0x,0x0x,0 x 2 xx 1 xx
3xx
4321
421
321
21
xxasujeto
fMinimizar
0,2x,1x,0x,0 x
0 3xx 2 x x
1 xx
4321
21
421
321
finicialbásicafactibleSolución
f-x
x
3,1x,0x,1x,0 x
3 3x x4
1 x- 2x 1 xx
4321
31
431
321
fnuevabásicafactibleSolución
f-
xx
5,0x,0x,5.1x,5.0 x
5 2x x 5.0 0.5x 5.0 x5.1 0.5x 5.0 x
4321
43
431
432
fnuevabásicafactibleSolución
f-xx
PROGRAMACIÓN LINEAL• Problema del transporte.• Ejemplo en el programa/MicrosoftOffice/solvsamp.xls• Formulación algebraica.
ijij
ij
ijij
jiij
ij
xc
jix
jDx
iPx
x
5
1j
3
1i
3
1
5
1
Coste
minimizar es objetivo El,,0
negativas no son variablesLas
5,4,3,2,1,
demanda de limitaciónla cumplir debe Se
3,2,1,
producción de ónlalimitacicumplir debe Sej. almacén al ifábrica la desde
enviadas unidades de número al Llamamos
Ejemplo: Problema de transporte.
Minimizar el costo de envío de mercancías desde las plantas de producción hasta los almacenes
cercanos a los centros de demanda regionales, sin exceder las existencias disponibles
en cada planta y satisfaciendo la demanda de cada almacén regional.
Cantidad a enviar de la planta "x" al almacén "y' (en la intersección):
Plantas Total Sevilla Madri Barcelona Santander Bilbao
Galicia 5 1 1 1 1 1
La Rioja 5 1 1 1 1 1
Murcia 5 1 1 1 1 1
--- --- --- --- ---
TOTAL: 3 3 3 3 3
Demandas por almacén--> 180 80 200 160 220
Plantas: ExistenciasCostos de envío de la planta "x" al almacén "y" (en la
intersección):
Galicia 310 10 8 6 5 4
La Rioja 260 6 5 4 3 6
Murcia 280 3 4 5 5 9
Envío: 83 $ 19 $ 17 $ 15 $ 13 $ 19 $
PROGRAMACIÓN LINEALPROBLEMA TRASPORTE
PROGRAMACIÓN LINEALPROBLEMA DIETA
1.-Minimizar el coste de una dieta basada en el cuadro siguiente ycondicionada a los requerimientos diarios de proteínas(70gr..),vitaminaC(50gr..) y hierro(12gr.)
Medida1 unidad
Proteína g/u
Vitamina Cmg./u.
Hierromg./u.
CosteCent/u.
Manzanas 1 med 0.4 6 0.4 8
Plátanos 1 med 1.2 10 0.6 10
Zanahorias 1 med 0.6 3 0.4 3
Dátiles ½ copa 0.6 1 0.2 20
Huevos 2 med. 12.2 0 2.6 15
Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cual necesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora que contrata a equipos de jóvenes de dos tipos:
• Tipo A _ PAREJAS: 1 chico y 1 chica.
• Tipo B _ EQUIPOS: 1 chico y 3 chicas.
Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.
¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero?
NÚMERO CHICOS CHICAS
PAREJAS X X X
EQUIPOS Y Y 3Y
TOTAL X+Y X+3Y
Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viajepara el cual necesitan dinero. Deciden pedir trabajo por las tardes en una compañíaencuestadora que contrata a equipos de jóvenes de dos tipos:
• Tipo A _ PAREJAS: 1 chico y 1 chica.
• Tipo B _ EQUIPOS: 1 chico y 3 chicas.
Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.
¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero?
Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cualnecesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora quecontrata a equipos de jóvenes de dos tipos:
• Tipo A _ PAREJAS: 1 chico y 1 chica.
• Tipo B _ EQUIPOS: 1 chico y 3 chicas.
Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.
¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero?
NÚMERO CHICOS CHICAS
PAREJAS X X X
EQUIPOS Y Y 3Y
TOTAL X+Y X+3Y
203yx10yx0y0x
Números enteros positivos
Número máximo de chicos
Número máximo de chicas
Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cualnecesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora quecontrata a equipos de jóvenes de dos tipos:
• Tipo A _ PAREJAS: 1 chico y 1 chica.
• Tipo B _ EQUIPOS: 1 chico y 3 chicas.
Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.
¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero ?
203yx10yx0y0x
Los puntos que cumplan todas las restricciones se llaman FACTIBLES y dan lugar a la REGIÓN FACTIBLE.
La ganancia total diaria, en euros, es G(x,y)= 30x + 50y
Debemos, por tanto, MAXIMIZAR la FUNCIÓN OBJETIVO G(x,y)= 30x + 50y
203 yx
10 yx
0x0y
Las posibles soluciones (x,y) han de ser númerosenteros positivos. ¿Por qué?. ¿Siempre es así?.
Las posibles soluciones (x,y) han de pertenecer a laregión factible. ¿Por qué?. ¿Puede ser (2,7) unasolución?. ¿Por qué?
Toma la función OBJETIVO:
G(x,y)= 30x+50y
y calcula diversas ganancias:
G(2,2) = 60+ 100 = 160 €
G(2,4) = 60 + 200 = 260 €
G(9,1) = 270 + 50 = 320 €
G(5,5) = 150 + 250 = 400 €
.......
¿CÓMO AVERIGUAR EN CUÁL DE LOS PUNTOS SE OBTIENE LA GANANCIA MÁXIMA?
05030 yx
x y
0 0
5
G(0,0)= 0
G(6,0) = 180G(1,5) = 180
G(10,0)= 300
G(5,5)= 400-3
Se localiza la recta que esté lomás arriba posible y que pase poralgún punto de la región factible.
Este punto resulta ser el (5,5)
G(0,0) = 0 €
G(6,0) = 180 €
G(1,5) = 180 €
G(10,0) = 300 €
G(5,5) = 400 € VALOR MÁXIMO
04010 yx
x y
0 0
4
G(0,0)= 0
G(6,0) =G(2,1)= 60G(10,0)= 100
G(2,6)= 260
-1
Se localiza la recta que esté lomás arriba posible y que pase poralgún punto de la región factible.
Este punto resulta ser el (2,6)
G(0,0) = 0 €
G(6,0) = 60 €
G(10,0) = 100 €
G(5,5) = 250 €
G(2,6) = 260 € VALOR MÁXIMO
G(5,5)= 250
1º Representa la recta 20x + 40y = 0
06020 yx
x y
0 0
3 -1
2º Comprueba que la función objetivoes paralela a uno de los lados de laregión factible.
3º Comprueba que existen dos soluciones,que se localizan en la frontera de la regiónfactible.
G(2,6)= 400G(5,5)= 400
Planteo de un caso
En un taller metalúrgico se fabrican dos tipos depiezas, A y B, que deben seguir los siguientesprocesos: estampado en hojas metálicas, soldadoy pintado. La operación de estampado consisteen preparar partes idénticas que luego seránsoldadas de a pares, formando la pieza A.
El mismo proceso se realiza para la pieza B.
Los insumos de equipos son los siguientes
(expresados en segundos por pieza):
Planteo de un caso
Operación A B Tiempo disponible(seg/sem)
Estampado 3 8 48.000
Soldado 12 6 42.000
Pintado 9 9 36.000
Planteo de un caso
La utilidad unitaria es de $4 para la pieza A y $3 para lapieza B.Se desea establecer el programa semanal de producciónque maximice la utilidad del taller con respecto a laspiezas consideradas.
Definición del Problema
• INTERROGANTES: Producción de piezas A y B• OBJETIVO: Maximizar utilidades• RESTRICCIONES: Limitación de tiempo disponible para
los equipos de Estampado, Soldado y Pintado
Planteo del ModeloHIPOTESIS
• Producción continua• No se consideran feriados ni horas extras• No hay limitaciones de despacho, almacena
miento ni demanda• El sobrante de tiempo de los equipos no se
utiliza• No hay inflación
Planteo del ModeloDEFINICION DE VARIABLES
• X1: Producción de piezas A (piezas/sem)• X2: Producción de piezas B (piezas/sem)
Planteo del ModeloFORMULACION MATEMATICA
CONDICIONES de VINCULO
EST) 6X1 + 16X2 <= 48.000
SOL) 12X1 + 6X2 <= 42.000
PIN) 9X1 + 9X2 <= 36.000
CONDICIONES de NO NEGATIVIDAD
X1; X2 >=0
FUNCIONAL
Z= 4X1 + 3X2 (Máx.)
Formulación de un Sistema de Ecuaciones
• C.V.
6X1+16X2+X3 = 48.000
12X1+6X2 +X4 = 42.000
9X1+9X2 +X5 = 36.000
• C.N.N.: X1;X2;X3;X4;X5 >=0
• FUNCIONAL: Z = 4X1+3X2 Máx.
Interpretación de las Variables Slacks
• X3: sobrante equipo Estampado (seg/sem)
• X4: sobrante equipo Soldado (seg/sem)
• X5:sobrante equipo Pintado (seg/sem)
TIPO de SOLUCIONES• SOLUCION FACTIBLE: es aquella en que se cumple
simultáneamente con las condiciones de vínculo (orestricciones) y con las condiciones de no negatividadde las variables.
• SOLUCION BASICA: es aquella para la cual existeun número de variables iguales a 0 (cero), por lomenos igual al número de grados de libertad delsistema (Grado de libertad = N° de incógnitas - N° deecuaciones).
• SOLUCION BASICA FACTIBLE: es aquella quecumple con la doble condición de ser básica y serfactible.
SOLUCION OPTIMA
Cantidades a fabricar:• Producto A: X1 = 3.000 unidades/semana
• Producto B: X2 = 1.000 unidades/semana
Sobrantes de recursos:• Estampado: X3 = 14.000 seg/semana
• Soldado: X4 = 0
• Pintado: X5 = 0
Beneficio esperado: Z = 15.000 $/semana
DEFINICIONES• COSTO de OPORTUNIDAD (asociado a actividades):
representa el deterioro que sufre el funcional poractivar en una unidad la variable.
• VALOR MARGINAL (asociado a restricciones):representa la mejora del funcional por cada unidadque se libere la restricción.
ANALISIS DE SENSIBILIDADPermite dar respuesta a preguntas del tipo:
Qué pasa si……..?• Agregamos o eliminamos tal producto• Aumentamos o disminuimos la disponibilidad de tal recurso• Agregamos o eliminamos tal restricción• Aumentamos o disminuimos el beneficio o el costo de tal producto, etc.
PROGRAMACIÓN LINEAL Y SOLVER
Solver es una herramienta para resolver y optimizar ecuacionesmediante el uso de métodos numéricos.
Busca el valor óptimo para una celda, denominada celda objetivo
Cambia los valores de un grupo de celdas, denominadas celdascambiantes, y que estén relacionadas, directa o indirectamente,con la fórmula de la celda objetivo.
Se puede agregar restricciones
También puede especificar que los valores sean enteros.
Solver ajustará los valores de las celdas cambiantes. paragenerar el resultado especificado en la fórmula de la celdaobjetivo.
INSTALACIÓN DE SOLVER
• Menú Herramientas. Si aparece el comando Solver, ya está. Si no aparece, continua con el procedimiento.
• Herramientas, Complementos.
• Si Solver no aparece en la lista del cuadro de diálogo Complementos, ejecuta el programa de instalación de Excel
• Si Solver aparece, seleccione la casilla de verificación.
USO DE SOLVER
• Seleccione la orden Solver del menú Herramientas. aparecerá el cuadro de diálogo.
• Hay que dar a Solver tres datos: celda objetivo (función objetivo), las celdas cambiantes (las variables de decisión) y las restricciones.
FUNCIÓN OBJETIVO
• En el cuadro de diálogo Celda objetivo se indica el objetivo que debealcanzar Solver.
• Se puede introducir escribiendo las coordenadas de la celda, escribiendoun nombre que se la haya asignado a la celda o pulsando en la celda conel ratón. Si asigna un nombre a la celda, Solver lo usará para los informes.Si no le pone nombre a las celdas, Solver construirá los informes basándose en los textos de cabecera de las filas y columnas más cercanas. Enaras de la claridad, se recomienda darle nombre a todas las celdasimportantes del modelo antes de comenzar con Solver.
• Sí se desea minimizar, se selecciona Mín. Si el objetivo es maximizar, seselecciona Máx También hay ocasiones en las que la celda objetivo tieneque igualar un valor particular, en cuyo caso se selecciona Igual a y seintroduce la cifra (o referencia de la celda) en el cuadro adyacente.
• No es necesario especificar un objetivo. Si se deja en blanco el cuadroCelda objetivo, se puede obtener una solución que cumpla con lascondiciones pero no sea necesariamente óptima. Para ello, pulsa el botónopciones y selecciona la opción Mostrar resultado de iteraciones.
VARIABLES
• Las variables del problema se ubican en las celdascambiantes. Estas celdas se encuentran siempre enun rango especifico.
• Esta información se puede introducir escribiendo lascoordenadas de las celdas, escribiendo su nombreo seleccionándolas en la hoja.
• Si las variables no están en celdas adyacentes, sepueden separar las celdas (o rangos) con punto ycoma.
• Hay que especificar al menos una celda variable. Sino es así, Solver no podrá hacer nada.
RESTRICCIONES
• Pulsa el botón Agregar en el cuadro de diálogoParámetros de Solver y complete el cuadro de diálogoAgregar restricción.
Cada restricción se compone de tres elementos: unareferencia de celda (lado izquierdo de la restricción), unoperador de comparación y un valor de restricción (ladoderecho de la restricción).
Después de introducir una restricción, se puede pulsarel botón Aceptar para volver al cuadro de diálogoParámetros de Solver o pulsar Agregar para especificarotra restricción.
OPCIONES DE SOLVER• En el cuadro de diálogo de parámetros Solver,
selecionar opciones.
• Marcar aceptar modelo lineal y asumir no negativos
• Seleccionar aceptar
MENSAJES
Si Solver no puede encontrar la solución óptima de un problema, presenta unmensaje en el cuadro de diálogo Resultados el cual informa del problema. Losmensajes más frecuentes cuando no se puede alcanzar el objetivo son lossiguientes:
Solver no ha encontrado una solución válida. Solver no ha podido encontraruna solución que satisfaga todas las restricciones. Puede ocurrir si la región defactibilidad es vacía
Se ha cumplido el número máximo de iteraciones. ¿Desea continuar de todosmodos? Para evitar que la computadora se meta en un círculo sin fin cuando unproblema es irresoluble, Solver está diseñado para que se detenga y presenteeste mensaje cuando ha realizado el número por omisión de iteraciones y no hallegado a una solución.
Se ha cumplido el límite máximo de tiempo. ¿Desea continuar de todos modos?Este mensaje es similar al del límite de iteraciones. Solver está diseñado paradetenerse después de un cierto período de tiempo.
UN EJEMPLO
x1= toneladas diarias producidas de pintura para exteriores.x2= toneladas diarias producidas de pintura para interiores.
Máx Z= 5000x1+4000x2 (Utilidad diaria expresada en dólares)s.a.
6 x1+4 x2 24 ( disponibilidad máxima de M1)x1+2 x2 6 ( disponibilidad máxima de M2)
x2 2 ( demanda máxima de pintura para interiores)-x1+ x2 1 ( diferencia máx. producción de pinturas)x1 , x2 0. (no negatividad)
PROBLEMA EN EXCEL
A B C D E F G1 VARIABLES X1 X2 Utilidad2 VALOR 03 COEF. F.O. 5000 400045 RESTRICCIONES Lado I Tipo Lado D6 Disponibilidad M1 6 4 0 ≤ 247 Disponibilidad M2 1 2 0 ≤ 68 Dem. Máx. int. 1 0 ≤ 29 Diferencia produc. -1 1 0 ≤ 1
sumaproducto($B$2:$C$2;B3:C3)
sumaproducto($B$2:$C$2;B6:C6)
LA SOLUCIÓN
A B C D E F G1 VARIABLES X1 X2 Utilidad2 VALOR 3 1,5 210003 COEF. F.O. 5000 400045 RESTRICCIONES Lado I Tipo Lado D Hol-Exc6 Disponibilidad M1 6 4 24 ≤ 24 07 Disponibilidad M2 1 2 6 ≤ 6 08 Dem. Máx. int. 1 1,5 ≤ 2 0,59 Diferencia produc. -1 1 -1,5 ≤ 1 2,5
Holgura: Lado D - Lado I
Excedente: Lado I- Lado D
Método Simplex
• La idea del Método Simplex es proceder a partir de una soluciónbásica factible del conjunto de restricciones de un problema en laforma general, hacia otra solución básica factible, de forma tal quese disminuya continuamente el valor de la función objetivo hastaalcanzar el mínimo
• El método Simplex es desarrollado a partir del estudio del sistemade ecuaciones lineales que define las restricciones y las solucionesbásicas factibles del sistema, enfocándose en las variablesindividuales y su relación con el sistema
• Aquí se utiliza un aproximación matricial que se enfoca en todas lasvariables juntas, lo que lleva a una representación más compacta,aumentando el entendimiento del proceso del método
Pivotes
• Antes de empezar con el procedimiento del método Simplex, es necesario entender primero el proceso de pivoteo en un conjunto de ecuaciones lineales
• Existen dos interpretaciones del procedimiento de pivoteo, que conllevan al mismo resultado
Pivotes
mnmnmm
nn
nn
bxaxaxa
bxaxaxabxaxaxa
2211
22222121
11212111
Primera interpretación
• Considerando el conjunto de ecuaciones lineales simultáneas
• En el espacio En esto se puede interpretar como una colección de m relaciones lineales que se deben satisfacer por un x,
Donde m n
Que en forma matricial se escribe como Ax=b
mm bxa
bxabxa
2
21
1
Donde las ai son filas de A
Pivotes
Primera interpretación
• Si m < n y las ecuaciones son linealmente independientes, entonces no existe una solución única sino una familia de soluciones
• Se puede obtener una solución única haciendo n-m variables igual a cero y resolviendo para las restantes, para obtener una solución básica
• Usando un esquema de eliminación de Gauss, donde el múltiplo de una ecuación es sistemáticamente sustraído de otra ecuación, se puede llegar a una forma triangular o a una forma canónica de la matriz de restricciones
Forma canónica
0,,22,11,
0,2,222,211,22
0,1,122,111,11
mnnmmmmmmmm
nnmmmm
nnmmmm
yxyxyxyx
yxyxyxyxyxyxyxyx
• Para este caso, x1… xm variables básicasxm+1…. xn variables no básicas
• La solución básica correspondiente se obtiene directamente como,x1 = y1,0; x2 = y2,0; … ; xm = ym,0
• Entonces se considera que el sistema está en forma canónica, si hay mvariables básicas con la propiedad de que aparecen sólo en una ecuacióny su coeficiente en esa ecuación es uno
• Dado un sistema en su forma canónica, el pivoteo se utiliza paraintercambiar una variable básica por una no-básica y al mismo tiempoobtener la forma canónica para el nuevo conjunto de variables básicas
Procedimiento de Pivoteo
piyyy
yy pjpq
iqijij '
• Partiendo de un sistema en forma canónica, se quiere reemplazar lavariable básica xp, 1 p m, por la variable no-básica xq, esto sepuede hacer si y solo si ypq ≠ 0
1. Se divide la fila p entre ypq, para obtener un coeficiente unitario paraxq en la ecuación p
2. Luego, se restan múltiplos apropiados de la fila p a las demás filaspara hacer cero a los coeficientes de xq en estas filas. Esto noafecta las columnas de las otras variables básicas
• Denotando los coeficientes del nuevo sistema en forma canónicacomo yij’ las operaciones se resumen en,
pq
pjpj y
yy '
Hace el coef. de p igual a cero
Hace el coef. de p igual a uno
Procedimiento de Pivoteo
12332
5
6543
6542
6541
xxxxxxxx
xxxx
• Ejemplo: Considere el sistema en forma canónica
A =1 0 0 1 1 -1 50 1 0 2 -3 1 30 0 1 -1 2 -1 -1
Se reemplaza x1 por x4
A1 = A;A1(2:3,:)=A1(2:3,:)-A1(2:3,4)/(A1(1,4))*A1(1,:)A1(1,:) = A1(1,:)/A1(1,4)
A1 =1 0 0 1 1 -1 5-2 1 0 0 -5 3 -71 0 1 0 3 -2 4
piyyy
yy pjpq
iqijij '
pq
pjpj y
yy '
Puntos extremos adyacentes
• El método Simplex necesita pasar de una solución básica factible a otra solución básica factible a través del procedimiento de pivoteo
• Aquí se explica como seleccionar un pivote de manera que seobtenga una nueva solución básica factible
• Es posible seleccionar arbitrariamente cual variable no-básica se convertirá en básica, y luego determinar cual de las básicas debe salir
Puntos extremos adyacentes
iq
io
iq
i
yy
yx
• Asumiendo que todas las soluciones básicas factibles NO sondegeneradas
• Si se tiene un sistema en su forma canónica correspondiente auna solución básica factible, yi0 > 0, y se quiere convertir a lavariable no-básica q en básica (q > m) manteniendo factibilidad,el elemento pivote de la columna q será aquel para el cual,
i = 1,…, m es el menor positivo
Solución factible mínima
• Sabiendo como seleccionar un elemento pivote para lograr unanueva solución básica factible, ahora es necesario tener una formade seleccionar la variable no-básica que debe ser convertida enbásica para lograr una solución básica factible menor
Teorema del mejoramiento de una solución básica factible:
• Dada una solución básica factible no degenerada con funciónobjetivo z0 suponga que para alguna variable no básica j se cumpleque cj – zj < 0, donde cj es el coeficiente j de la función objetivo y
zj = y1jc1 + y2jc2 + … + ymjcm, m+1 ≤ j ≤ n
• Entonces existe una solución factible con valor objetivo z < z0
Solución factible mínima
Teorema de condición de optimalidad• Si para alguna solución básica factible cj – zj ≥ 0, para todas las
variables no-básicas j, entonces la solución es óptima
• rj = cj – zj, es conocido como Coeficientes de Costo Relativo o comoCoeficientes de Costo Reducido
• Estos coeficientes miden el costo de una variable relativo a unasolución básica dada, indicando si el valor objetivo aumenta odisminuye si xj es pivoteado dentro de la solución
Método Simplex – procedimiento de cálculo
nim
miyx i
i 1000
• Se asume que se inicia con una solución básica factible y que el sistema Ax = b está en su forma canónica
• La solución básica correspondientees factible si yi0 ≥ 0, i = ,…, m
• El valor de la función objetivo es z0
• La última fila puede ser tratada operacionalmente como cualquier otra fila de la Tabla Simplex durante el proceso de pivoteo
021
0,,,2,1,
0,2,2,22,21,2
0,1,1,12,11,1
2121
000100
010001
zrrrryyyyy
yyyyyyyyyybaaaaaaa
njmm
mnmjmmmmm
njmm
njmm
njmmm
Se agrega una fila a la matriz con los Coef. de Costo Relativo (r) y el negativo del costo actual (-z0)
Esto se conoce como la tabla Simplex
Método Simplex – Algoritmo
1. De la tabla correspondiente a una solución básica factible, secalcula los coeficientes de costo relativo, rj = cj – zj
2. Si todos los rj > 0; la solución básica factible es óptima
3. Seleccionar q tal que rq < 0, para determinar cual variable no-básicase convertirá en básica
4. Calcular los factores yi0/yiq para yiq > 0, i = 1,…, m.
• Si no hay yiq > 0, terminar y salir, el problema no tiene limites
• De otra forma, seleccione p como el índice i correspondiente almínimo factor positivo
5. Pivotee sobre el elemento pq, actualizando todas las filasincluyendo la última. Regrese al paso 2
Método Simplex – Ejemplo
% Minimizar f(x1,x2) = -2*x1 - x2
% sujeto a x1 + 8/3*x2 <= 4
% x1 + x2 <= 2
% 2*x1 <= 3
% y x1 >= 0; x2 >= 0
% Tabla Simplex 1
A =
1.0000 2.6667 1.0000 0 0 4.0000
1.0000 1.0000 0 1.0000 0 2.0000
2.0000 0 0 0 1.0000 3.0000
-2.0000 -1.0000 0 0 0 0
Solución básicax1 = 0
0 0.5 1 1.5 2 2.5 30
0.5
1
1.5
2
2.5
3Restriccion x3 = 0Restriccion x4 = 0Restriccion x5 = 0
-8
-7
-6
-5
-4
-3
-2
-1
q = 1 % la variable no-básica 1 se convertirá en básica, r mas negativo
Método Simplex – Ejemplofactores = A(1:3,6)./A(1:3,q) %yi0/yiq
factores = 4.0000
2.0000
1.5000
sale variable básica 3 p = 3
% pivoteo sobre el elemento pq = 31
A(p,:)=A(p,:)/A(p,q)
A(1,:)=A(1,:)-(A(1,q)*A(p,:))
A(2,:)=A(2,:)-(A(2,q)*A(p,:))
A(4,:)=A(4,:)-(A(4,q)*A(p,:))
0 2.6667 1.0000 0 -0.5000 2.5000
0 1.0000 0 1.0000 -0.5000 0.5000
1.0000 0 0 0 0.5000 1.5000
0 -1.0000 0 0 1.0000 3.0000
Solución básicax1 = 1.
0 0.5 1 1.5 2 2.5 30
0.5
1
1.5
2
2.5
3Restriccion x3 = 0Restriccion x4 = 0Restriccion x5 = 0
-8
-7
-6
-5
-4
-3
-2
-1
q = 2 % la variable no-básica 2 se convertirá en básica, r mas negativo
Método Simplex – Ejemplo
Solución óptimax1 = 1.
factores = A(1:3,6)./A(1:3,q) %yi0/yiq
factores =
0.9375
0.5000
Inf
sale variable basica 2 p = 2
% pivoteo sobre el elemento pq = 22
A(p,:)=A(p,:)/A(p,q)
A(1,:)=A(1,:)-(A(1,q)*A(p,:))
A(3,:)=A(3,:)-(A(3,q)*A(p,:))
A(4,:)=A(4,:)-(A(4,q)*A(p,:))
0 0 1.0000 -2.6667 0.8333 1.1667
0 1.0000 0 1.0000 -0.5000 0.5000
1.0000 0 0 0 0.5000 1.5000
0 0 0 1.0000 0.5000 3.5000
0 0.5 1 1.5 2 2.5 30
0.5
1
1.5
2
2.5
3Restriccion x3 = 0Restriccion x4 = 0Restriccion x5 = 0
-8
-7
-6
-5
-4
-3
-2
-1
Valor de la función objetivo en el punto óptimo F(1.5,0.5) = -3.5