• Author / Uploaded
• Ulises Miranda

Citation preview

INTRODUCCIÓN MODELO DE OPTIMIZACIÓN Están diseñados para proporcionar los "mejores" valores de diseño del sistema y las variables de política operativa - valores que conduzcan a los más altos niveles de rendimiento del sistema. Conformados por:   

Funciones objetivo Variables de decisión Restricciones

CLASIFICACIÓN 1. Estáticos y Dinámicos: Sucesión de decisiones para periodos múltiples. 2. Lineales y no lineales. Las variables de decisión aparecen en la función objetivo y restricciones, están multiplicadas por constantes y acomodadas en forma de suma. 3. Modelo enteros y no enteros: Una o más variables de decisión son enteras o fraccionarias. 4. Modelo determinístico y estocástico: Se conoce con certeza el valor de la función objetivo, cumpliendo o no las restricciones. MÉTODOS 1. Programación lineal: Planeación de las actividades para obtener un resultado óptimo 2. Programación entera: Los métodos de ramificar y acotar encuentran la solución óptima para un problema de programación entera. 3. Método de transporte: Analiza los costos de transporte tanto de la materia prima como de los productos terminados

4. Método de asignación: El objetivo es asignar los trabajos a las máquinas (un trabajo por máquina) con el costo mínimo total.

5. Programación no lineal: Los problemas no lineales se caracterizan por tener relaciones no lineales; es decir, no existe una relación directa y proporcional entre las variables que intervienen. 6. Método de sustitución directa: Es un método en donde la función objetivo está sujeta a una o dos restricciones de igualdad lineales o no lineales, con en la cual se resuelve explícitamente una variable y dicha variable se elimina en la formulación del problema.

En la teoría puede ser fácil de aplicar, sin embargo, no es conveniente su uso desde el punto de vista práctico. La razón para esto es que las restricciones serán no lineales para la mayoría de los problemas prácticos, y muchas veces son muy complicados de resolver. 7. Programación Cuadrática: Es un método usado para determinar la cartera de inversiones óptima de un conjunto dado. Este tipo de problemas de optimización se caracterizan por que la función objetivo de n variables es minimizado sujeto a “m” restricciones de desigualdades o igualdades lineales.

8. Método de LaGrange: Este método se usa para resolver PNL en los que las restricciones, son las restricciones igualdades.

Normalmente se usa un factor o multiplicador para su resolución. presentarse en problemas con dos variables y una sola restricción

También suele

9. Método de Fibonacci: Método iterativo irrestricto basado en la serie de Fibonacci. Es considerado uno de los métodos más exactos. Es usado para encontrar el mínimo de una función univariable, aunque la función no sea continua.

Programación Lineal Consiste en optimizar una función lineal, denominada función objetivo que esta sujeta a una serie de restricciones. Se verán 3 métodos para resolver un problema de programación lineal MÉTODO GRÁFICO El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones). La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos, el valor mínimo o máximo del problema. Cálculos analíticos para graficar el sistema de inecuaciones lineales, incluyendo la condición de no negatividad (NN [ ]), que nos indica que solamente trabajaremos en el primer cuadrante del plano cartesiano, cuadrante donde X1 y X2 son positivas.

El valor de la función objetivo en cada una de las esquinas del área de soluciones factible es:       La función objetivo se maximiza cuando

y

;

Algoritmo Simplex Algoritmo del método simplex para un problema de maximización 1. Convierta el PL en una forma estándar. 2. Encuentre una solución factible básica (sfb), si es posible, a partir de la forma estándar. 3. Determinar si la sfb actual es óptima. 4. Si la sfb actual no es óptima, entonces se determina cuál variable no básica se debe transformar en variable básica y cuál variable básica se debe transformar en variable no básica con el objeto de hallar una nueva sfb. 5. Aplicar Operaciones de renglón (OER) para encontrar la nueva sfb. Regresar al paso 3.

La “Dakota Furniture Company” fabrica escritorios, mesas y sillas. Para la manufactura de cada tipo de mueble se requiere madera y dos tipos de manos de obra calificada: acabado y carpintería. La cantidad de recursos necesarios para elaborar cada tipo de muebles se proporciona en la tabla 1.

Se cuenta en la actualidad con 48 ft tablón de madera, 20 horas de acabado y 8 horas de carpintería. Un escritorio se vende en 60 dólares, una mesa en 30 dólares y una silla en 20 dólares. Dakota opina que la demanda de escritorios y sillas es ilimitada, pero cuando mucho se pueden

vender 5 mesas. Puesto que los recursos disponibles ya se compraron, Dakota quiere maximizar el ingreso total. Definimos las variables: x1, x2 y x3. X1: Número de escritorios fabricados. X2: Número de mesas fabricadas. X3: Número de sillas fabricadas

Para comenzar con el paso dos, se eligen las variables básicas (VB) y las variables no básicas (VNB). Quedando de la siguiente manera: De esta manera obtenemos nuestra primera solución factible (con x1, x2 y x3 igual a cero), pero no óptima. VB

x1

x2

x3

s1

s2

s3

s4

Solución

z s1 s2 s3 s4

-60

-30

-20

0

0

0

0

0

8

6

1

1

0

0

0

48

4

2

1,5

0

1

0

0

20

2

1,5

0,5

0

0

1

0

8

0

1

0

0

0

0

1

5

Variable básica que sale:

RMC

Para determinar la variable saliente se sigue la siguiente regla:

𝐶𝑜𝑙𝑢𝑚𝑛𝑎 𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 𝐶𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑑𝑒 𝑙𝑎 𝑐𝑜𝑙𝑢𝑚𝑛𝑎 𝑝𝑖𝑣𝑜𝑡𝑒 “La restricción con el cociente más pequeño se denomina ganador de la prueba de cociente, este indicará que variable básica deberá salir” VB

x1

x2

x3

s1

s2

s3

s4

Solución

z s1 s2 s3 s4

-60

-30

-20

0

0

0

0

0

8

6

1

1

0

0

0

48

6

4

2

1,5

0

1

0

0

20

5

2

1,5

0,5

0

0

1

0

8

4

0

1

0

0

0

0

1

5

-

RMC

RMC

Las operaciones que hacemos después son: 1. Dividir toda la fila pivote entre el elemento pivote. 2. Para las demás filas se sigue la siguiente ecuación:

VB

x1

x2

x3

s1

s2

s3

s4

Solución

z s1 s2 x1 s4

0

15

-5

0

0

30

0

240

0

0

-1

1

0

-4

0

16

0

-1

0,5

0

1

-2

0

4

1

0,75

0,25

0

0

0,5

0

4

0

1

0

0

0

0

1

5

VB

x1

x2

x3

s1

s2

s3

s4

Solución

z s1 s2 x1 s4

0

15

-5

0

0

30

0

240

0

0

-1

1

0

-4

0

16

-16

0

-1

0,5

0

1

-2

0

4

8

1

0,75

0,25

0

0

0,5

0

4

16

0

1

0

0

0

0

1

5

-

VB

x2 5

x3 0

s1 0

s2 10

s3 10

s4 0

Solución 280

RMC

z

x1 0

s1 x3 x1 s4

0 0 1 0

-2 -2 1,25 1

0 1 0 0

1 0 0 0

2 2 -0,5 0

-8 -4 1,5 0

0 0 0 1

24 8 2 5

La solución óptima es:

RMC

-16 8 16 -

z x1 x2 x3

280 2 0 8

Si el caso hubiese sido de minimización, tomamos como referencia que todos los coeficientes de la fila cero sean negativos.

Método de 2 fases o M’s En la fase 1 se agregan variables artificiales y se resuelven por método simplex normal.

En la fase 2 se quitan las variables artificiales y se vuelve a utilizar el método simplex.

Programación Lineal (Problemas de ejercitación) 1. La SAVE IT COMPANY opera un centro de reciclado que recoge 4 tipos de materiales de desecho sólido y lo trata para amalgamarlo en un producto comercializable. (El tratamiento y el amalgamiento son dos procesos diferentes). Se puede hacer tres grados diferentes de este producto (Vea la Tabla 1), según la mezcla de materiales que se use. Aunque existe alguna flexibilidad para esta mezcla en cado grado, los estándares de calidad especifican una cantidad mínima y máxima para la proporción de los materiales permitidos en ese grado. (Esta proporción es el peso del material expresado como un personaje del peso total del producto de ese grado). Para los dos grados más altos se especifica un porcentaje fijo de uno de los materiales. Estas especificaciones se dan en la Tabla 1 junto con el costo de amalgamado y el precio de venta de cada producto. El centro de reciclado recoge los materiales de desecho sólido de ciertas fuentes habituales por lo que casi siempre puede mantener una tasa de producción estable para tratarlos. En la Tabla 2 se dan las cantidades disponibles para la recolección y tratamiento semanal, al igual que el costo de proceso para cada tipo de material. La Sav-It Co. Es propiedad de Green Earth, una organización dedicada a asuntos ecológicos. Esta organización ha logrado contribuciones y apoyos por la cantidad de $30,000 semanales, que deben usarse sólo para cubrir el costo del tratamiento completo de los desechos sólidos. El consejo directivo Green Earth ha girado instrucciones a la administración de la Save-It para que divida este dinero entre los materiales de manera tal que se recolecte y se trate al menos la mitad de la cantidad disponible de cada material. Esta restricción se muestra en la Tabla 2. Dentro de las restricciones especificas en las Tablas 1 y 2, la administración desea determinar la cantidad que debe producir de cada grado y la mezcla exacto de materiales que usará para cada uno, de manera que maximice la ganancia semanal neta (ingresos totales por ventas, menos costo total de amalgamiento).

Solución Variable de decisión Xij= proporción del material j usado por semana en el producto de grado i producido por semana (i=A=1, B=2, C=3; j=1, 2, 3, 4) Función objetivo Max z=Costos - Utilidades Max z=8.5(X11+ X12+ X13+ X14)+ 7.0(X21+ X22+ X23+ X24)+ 5.5(X31+ X32+ X33+ X34)-3.0 (X11+ X12+ X13+ X14)- 2.5(X21+ X22+ X23+ X24)- 2.0(X31+ X32+ X33+ X34)

Restricciones  Especicificaciones de la mezcla

 Disponibilidad de materiales

 Restricciones sobre las cantidades tratadas

 Restricciones sobre costos de tratamiento

3.0 (X11+ X21+ X31)+ 6.0(X12+ X22+ X32)+ 4.0(X13+ X23+ X33)+ 5.0 (X14+ X24+ X34)=30,000  Restricciones de no negatividad N,N

La solución en Lindo se muestra a continuación:

2. Cierta empresa produce dos tipos de gasolinas, grado normal y grado extra, estas se producen mezclando tres tipos de componentes de petróleo. La gasolina grado normal, puede venderse a $0.50 de dólar por galón, y la de grado extra en $0.54 de dólar por galón.

Los compromisos actuales con los distribuidores requiere que se fabriquen cuando menos 10 000 galones de gasolina normal. Los costos y ofertas de petróleo se muestran en las siguientes tablas:

Variable de decisión.

Función objetivo

Restricciones •

Disponibilidad de componentes.



Requerimiento de gasolina normal.



Especificaciones para gasolina normal y extra.

3. Tecnología Agrícola S.A. es una compañía fabricante de fertilizantes. El gerente desea planear la combinación de sus dos mezclas a fin de obtener la mayor de sus utilidades. Las mezclas son:

El mayorista comprara cualquier cantidad de ambas mezclas de fertilizante que la compañía pueda fabricar. Esta dispuesto a pagar a $71.50 la tonelada de (5.5.10) y a $69 la tonelada de (5.10.5). En este mes la disponibilidad y costos de materia prima son:

Hay un costo de $15 por tonelada por mezclado de fertilizantes. 

Objetivo: Maximizar las utilidades



Variables de decisión



Función objetivo:



Restricciones

Corrida en lindo:

Método de Ramificar y Acotar Programación Entera: Los programas lineales enteros son aquellos en los que algunas o todas las variables están restringidas a tener valores enteros (o discretos). La empresa Telfa Corporation se dedica a la fabricación de mesas y sillas. Para la fabricar una mesa se requieren una hora de mano de obra y 9 pies de tablón de madera, en tanto que para una silla se necesitan 1 hora de mano de obra y 5 pies de tablón de madera. En la actualidad, están disponibles 6 horas de mano de obra y 45 pies de tablón de madera al mes. Cada mesa contribuye con 8 dólares a las utilidades y cada silla con 5 dólares. Formule y resuelva un PE para maximizar las utilidades de Telfa .  Paso 1.- Definir las variables.

 Paso 2.- Establecer función objetivo. Max ( Paso 4.- Establecer Restricciones.  Restricción de la madera

)(

)

(

)(

)

(

)(

)

(

)(

)

 Restricción de mano de obra

(

)(

)

(

)(

)

Si todas las variables de decisión asumieran valores enteros la solución óptima del problema de PL sería la solución óptima del problema de PE. Como no sucede lo antes mencionado en este caso se debe continuar al paso número 6.  Paso 6.-Dividir la región factible de la relajación del PL. La solución óptima del PL es Como es maximizar, el valor óptimo no debe de ser mayor a 41.25 Se elige de modo arbitrario una variable fraccionaria de la solución óptima del problema de PL para generar dos zonas de posibles soluciones. En este caso se elige presentan 2 opciones diferentes.

y a continuación se

 Paso 7.-Se realiza un árbol (que es la representación de todos los subproblemas que se proponen). Nodo: sub problema i (1, 2, 3….N)

Arco: Línea que une los nodos Restricción: Se suma con el subproblema anterior t = Indica el orden en el cual se resuelve el problema

S S

2 3

Subproblema 1 + restricción Subproblema 1 + restricción

A esto se le conoce como ramificación sobre Paso 8.- Escoger un subproblema y resolverlo

La solución optima del subproblema 2 no ofreció una solución de enteros únicamente por lo cual se repítela metodología del paso 6.  Paso 9.- Se repite la ramificación sobre la variable fraccionaria

S

4 S

Subproblema 2 + restricción 5

Subproblema 2 + restricción

1

 Paso 10.- Escoger un subproblema y resolverlo. El subproblema 4 no es factible.

Al resolver el subproblema 5 se obtiene la solución: Z= 365/9 X1=40/9 X2=1

Como el valor de

continua siendo fraccionario esta variable se vuelve a ramificar

 Paso 11.- Escoger un subproblema y resolverlo.

S

6 S

Subproblema 5 + restricción 7

Subproblema 5 + restricción

 Paso 12.- Escoger un subproblema y resolverlo Para el Subproblema la solución es: Z= 37 X1=4 X2=1 Dado que los valores de la solución son enteros, estos representan una solución factible para el problema de PE.

Ejemplos Forme el árbol de ramificación y acotamiento para el siguiente problema:

Sujeto a

0 y enteros

Se escoge a

como la variable de ramificación.

Se tienen dos nuevos PL: PL1 y PL2 PL1:

Sujeto a

0 PL2:

Sujeto a

0

Aún se puede hacer un PL3 ya que en el PL2 no se cumple que las variables sean números enteros, entonces:

Sujeto a

0

Árbol de ramificación y acotamiento

Min z= -5x1-8x2 St X1+x2