• Author / Uploaded
• mauro

• Categories
• Alimentos
• Comida y vino
• Matemáticas
• Ciencia
• Naturaleza

Citation preview

Método simplex con restricciones de tipo ≥ Consiste en castigar o penalizar el hecho de que estas variables artificiales asuman un valor positivo, asignándoles un costo altísimo denominado por M ( M >>>> 0 ). Por lo cual la f.o. queda :

Max Z = C1X1 + C2X2 + ... + CnXn-Ma1 -Ma2 -…….-Mai Min Z = C1X1 + C2X2 + ... + CnXn+Ma1 +Ma2 +……+Mai

Definición. • Si la restricción i-esima de un problema de programación lineal es una restricción ≥, entonces se puede convertir en una restricción de igualdad al restar una variable de excedente «Ei», de la restricción i-esima y añadir la restricción de signo Ei ≥ 0,

Definicion. Para convertir la restricción i-esima ≥ en una restricción de igualdad se define una variable de excedente «Ei». Ei: Cantidad con la cual la restricción i-esima se satisface en exceso. En resumen el problema de programación lineal resultante esta de la forma estándar y se escribe como sigue:

Pasos del Método de la Gran M Paso 1: Modificar las restricciones de tal forma que el segundo miembro o lado derecho de cada una sea no negativo. Para lograrlo, cada restricción con un segundo miembro negativo se multiplica por -1. Recordar que si usted multiplica una desigualdad por un numero negativo, se invierte la dirección de la desigualdad. Por ejemplo, este método transformaría la desigualdad X1+X2≥-1 en –X1-X2≤1. También transformaría X1-X2≤-2 en –X1+X2≥2. Paso 1`: Identificar cada restricción que es ahora (después del paso 1)una restricción = o ≥. En el paso 3 se suma una variable artificial a cada una de estas restricciones. Paso 2: Convierta cada restricción de desigualdad en la forma estándar. Esto quiere decir que si la restricción i es una restricción ≤ se suma una variable de holgura hi, y si la restricción i es una restricción ≥, se resta una variable de excedente ei. Paso 3: Si (después de haber terminado el paso 1) la restricción i es una restricción ≥ o =, sume una variable artificial ai, también sume la restricción de signo ai≥ 0. Paso 4: Sea M un numero positivo muy grande . Si el PL es un problema de minimización, sume (por cada variable artificial) Mai a la función objetivo. Si el PL es un problema de maximización, sume (por cada variable) -Mai a la función objetivo Paso 5: Como cada variable artificial esta en la base de inicio, todas las variables artificiales se tienen que eliminar de la función objetivo antes de empezar el simplex. De esta manera se asegura que se empieza con una forma canónica. Al elegir la variable entrante, recuerde que M es un numero muy grande.

Método de la Gran M Ejemplo: Bevco elabora una bebida carbonatada sabor naranja que se llama Oranj mediante la combinación de agua carbonatada de naranja y jugo de naranja. Cada onza de agua carbonatada de naranja contiene 0,5 onzas de azúcar y 1 mg de vitamina C. Cada onza de jugo de naranja contiene 0,25 onzas de azúcar y 3 mg de vitamina C. Bevco gasta 2 centavos por producir 1 onza de agua carbonatada de naranja y 3 centavos por elaborar 1 onza de jugo de naranja. El departamento de mercadotecnia de Bevco decidió que la botella de 10 onzas de Oranj debe contener por lo menos 20 mg de vitamina C y cuando mucho 4 onzas de azúcar. Utilice la programación lineal para determinar como Bevco puede cumplir los requisitos del departamento de mercadotecnia a un costo mínimo.

Método de la Gran M Sea: Variables de decisión: X1: Cantidad de onzas de agua carbonatada de naranja en una botella de Oranj. X2: Cantidad de onzas de jugo de naranja en una botella de Oranj.

min Z  2x1  3 x2 s/a 1 1 x1  x2  4.....(rest . azucar) 2 4 x1  3 x2  20.....(rest .vitam) x1  x2  10.......(10 oz en una botella) x1, x2  0

Método de la Gran M Forma Estándar

Z  2x 1  3 x2 1 1 x1  x2  h1 4 2 4 x 1  3 x2 - e 2  20 x1  x2 x 1, x2 , h1, e2  0

 10

Método de la Gran M Incorporando las variables artificiales

Z  2x1  3 x2  Ma 2  Ma3  0 1 1 x1  x2  h1 4 2 4 x 1  3 x2 - e 2  a2  20

x1  x 2

 α 3  10

x1, x2 , h1, e2 , a2, a3  0

Método de la Gran M Despejamos a2 y a3 de las ecuaciones y las reemplazamos en la función objetivo:

a 2  20  x1  3 x2  e2 a3  10  x1  x2 z  2 x1  3x2  M (20  x1 3x2  e2 )  M (10  x1  x2 )  0 z  2 x1  3x2  20M  x1M  3x2 M  Me2  10M  x1M  x2 M  0 z  2 x1  2 x1M  3x2  4 x2 M  Me2  30M  0 z  (2  2M ) x1  (3  4M ) x2  Me2  30M

Método de la Gran M

x1

x2

h1

e2

a2

a3

Sol.

Z

(2M-2)

(4M-3)

0

-M

0

0

30M

H1

1/2

1/4

1

0

0

0

4

a2

1

3

0

-1

1

0

20

a3

1

1

0

0

0

1

10

Método de la Gran M

x1

x2

h1

e2

a2

a3

Sol.

Z

(2M-3)/3

0

0

(M-3)/3

(-4M+3)/3

0

(10M+60)/3

H1

5/12

0

1

1/12

-1/12

0

7/3

a2

1/3

1

0

-1/3

1/3

0

20/3

a3

2/3

0

0

1/3

-1/3

1

10/3

Método de la Gran M x1

x2

h1

e2

a2

a3

Sol.

Z

0

0

0

-1/2

(1-2M)/2

(3-2M)/2

25

H1

0

0

1

-1/8

1/8

-5/8

1/4

x2

0

1

0

-1/2

½

-1/2

5

x1

1

0

0

1/2

-1/2

3/2

5

Como estamos trabajando con minimización, todos los valores de Z deben ser negativos, por lo tanto hemos llegado a nuestra tabla optima donde Z=25, h1= ¼, x1=5 y x2=5

Ejemplo La dieta de Juanito requiere que todos los alimentos que ingiera pertenezcan a uno de los cuatro grupos básicos de alimentos (pastel de chocolates, helado de crema, bebidas carbonatadas y pastel de queso). Por ahora hay los siguientes 4 alimentos: Barras de chocolates, helado de crema de chocolate, bebida de cola y pastel de queso con piña. Cada barra de chocolate cuesta $50 centavo, cada bola de helado de crema de chocolate cuesta $20 centavos, cada botella de bebida cuesta $30 centavos y cada rebanada de pastel de queso con piña cuesta $80 centavos. Todos los días debo ingerir por lo menos 500 calorías, 6 onzas de chocolate, 10 onzas de azúcar, y 8 onzas de grasa. El contenido nutricional por unidad de cada alimento se proporciona en la tabla. Plantee un modelo de programación lineal que se pueda utilizar para cumplir con las necesidad nutricionales de Juanito al mínimo costo. Tipo de Alimento

Calorías (onzas)

Chocolate (onzas)

Azúcar (onzas)

Grasa (onzas)

Barra de Chocolate

400

3

2

2

Helado de Crema Chocolate

200

2

2

4

Bebida de cola

150

0

4

1

Pastel de Queso

500

0

4

5

Variable de Decisión: X1:Cantidad de barras de chocolate consumidas al día. X2:Cantidad de bolas de helado de chocolate ingeridas al día. X3:Cantidad de botellas de bebida cola tomadas al día. X4:Cantidad de rebanadas de pastel de queso con piña consumidas al día.

Función Objetivo: Min Z=50X1+20X2+30X3+80X4 Restricciones: 400X1+200X2+150X3+500X4 ≥ 500…..calorías 3X1+2X2 ≥ 6………chocolate 2X1+2X2+4X3+4X4 ≥ 10…….Azúcar 2X1+4X2+1X3+5X4 ≥ 8……… Grasa X1,X2,X3,X4 ≥ 0………no negatividad

Forma Estandar Min Z=50X1+20X2+30X3+80X4 s/a 400X1+200X2+150X3+500X4-E1 ≥ 500 3X1+2X2-E2 ≥ 6 2X1+2X2+4X3+4X4-E3 ≥ 10 2X1+4X2+1X3+5X4-E4 ≥ 8 Xi,Ei ≥ 0 i=(1,2,3,4)…no negatividad

Si la restricción i-esima de un problema de programación lineal es una restricción ≥, entonces se puede convertir en una restricción de igualdad al restar una variable de excedente Ei de la restricción i-esima y añadir la restricción de signo Ei ≥ 0.

Ejemplo Max Z=20X1+15X2 s/a X1 ≤ 100 X2 ≤ 100 50X1+35X2 ≤ 6000 20X1+15X2 ≥ 2000 X1,X2≥0 Encontrar la forma estandar.