• Author / Uploaded
• Eduardo Martinez

• Categories
• Física y matemáticas
• Matemáticas
• Ciencia
• Informática y tecnología de la información
• Es / Ciencias de la Computación

Citation preview

SEGUNDO PARCIAL MÉTODO SIMPLEX El método simplex se basa en el álgebra y se lo emplea para resolver problemas de programación lineal tanto de maximización como de minimización. Es un proceso repetitivo numérico que permite llegar a una solución óptima partiendo de un punto extremo conocido; es decir, partiendo de una solución básica, si esta solución básica factible tomada como punto de partida no satisface, es necesario tomar otra solución que nos da un valor para Z mayor o menor y así sucesivamente hasta llegar a la solución final. Es un método iterativo (aproximaciones sucesivas). Existen tres requisitos en la solución de un problema de programación lineal por el método simplex. Todas las limitaciones deben estar establecidas como ecuaciones. El segundo miembro de una limitante, no puede ser negativo. Todas las variables están restringidas a valores no negativos.

OBJETIVOS Explicar detalladamente por qué el método simplex encuentra soluciones óptimas para problemas de programación lineal. Determinar cuándo un problema de programación lineal tiene soluciones. Determinar cuándo un problema de programación lineal no tiene soluciones. PROCEDIMIENTO Cualquiera que sea el número de inecuaciones y de incógnitas de un sistema, este por sí mismo se ajusta a un tratamiento de identificación que nos dé una idea de que sea sujeto de solución. Cuando el sistema reúne a un número de ecuaciones inferior al número de incógnitas, existen muchas soluciones. Justamente es el caso más frecuente de los problemas de programación lineal, de allí que es necesario introducir (+) variables de holgura en los casos de expresión ≤ (igual o menor), restar (-) variables de holgura e introducir variables artificiales en los casos de ≥ (mayor o igual) y en los casos de = se introduce variables artificiales con signo más. ≤ + Variables de Holgura. ≥ - Variables de Holgura + Variable Artificial. = + Variable Artificial.

+S –S+m +m

Ejercicios en clases

Ejercicio Nº 1 𝑍(max) = 𝑋1 + 2𝑋2 Restricciones: 𝑋1 + 3𝑋2 ≤ 200 2𝑋1 + 2𝑋2 ≤ 300 2𝑋2 ≤ 60 Variables de No negatividad: 𝑋1 , 𝑋2 ≤ 0

𝑋1 + 3𝑋2 + 𝑆1 ≤ 200 2𝑋1 + 2𝑋2 + 𝑆2 ≤ 300 2𝑋2 + 𝑆3 ≤ 60 𝑍(max) = 𝑋1 + 2𝑋2 + 0𝑆1 + 0𝑆2 + 0𝑆3

CJ

0 0 0

Xj S1 S2 S3 Zj Cj-Zj

bn 200 300 60 0 ---------

1

2

0

0

0

X1 1 2 0 0 -1

X2 3 2 1 0 -2

S1 1 0 0 0 0

S2 0 1 0 0 0

S3 0 0 1 0 0

CJ

0 0 2

Xj S1 S2 X2 Zj Cj-Zj

bn 20 180 60 120 ---------

CJ

1 0 2

Xj X1 S2 X2 Zj Cj-Zj

bn 20 140 60 140 ---------

CJ

1 0 2

Xj X1 S3 X2 Zj Cj-Zj

bn 125 35 25 175 ---------

1

2

0

0

0

X1 1 2 0 0 -1

X2 0 0 1 2 0

S1 1 0 0 0 0

S2 0 1 0 0 0

S3 -3 -2 1 2 2

1

2

0

0

0

X1 1 0 0 1 0

X2 0 0 1 2 0

S1 1 -2 0 1 1

S2 0 1 0 0 0

S3 -3 4 1 -1 -1

1

2

0

0

0

X1 1 0 0 1 0

X2 0 0 1 2 0

S1 -1/2 -1/2 ½ 1/2 1/2

S2 3/4 1/4 -1/2 1/4 1/4

S3 0 1 0 0 0

Interpretación: Para obtener una utilidad de 175 se necesita tener en disponibilidad 125 unidades de X1 Y 25 unidades de X2.

17.-La firma Kelson Sporting Equipment Inc, fabrica dos tipos de guantes para beisbol, un modelo normal y el modelo para cátcher. La empresa tiene 900 horas de tiempo de producción disponibles en su departamento de corte y costura, 300 horas disponibles en su departamento de terminado y 100 horas disponibles en su departamento de empaque y envío. Los requisitos de tiempo de producción y las utilidades por guante son las que se presentan en la siguiente tabla: TIEMPO DE PRODUCCION (horas)

MODELO

CORTE Y COSTURA TERMINADO

Normal Para Catcher

1 3/2

1/2 1/3

EMPAQUE Y ENVÍO 1/8 1/4

UTILIDAD POR GUANTE $5 $8

a) Suponiendo que la compañía desea maximizar las utilidades ¿Cuántos guantes de cada modelo debe fabricar? b) ¿Cuál es la utilidad que Kelson puede obtener con las anteriores cantidades de producción? c) ¿Cuántas horas de producción se programará en cada departamento? d) ¿Cuál es el tiempo de holgura en cada departamento? VARIABLES X1= Cantidad de guantes de modelo normal X2= Cantidad de guantes de modelo para cátcher FUNCIÓN OBJETIVO Z(max)= 5x1 + 8x2 VARIABLES DE NO NEGATIVIDAD x1, x2>=0 RESTRICCIONES 2𝑥1 + 3𝑥2 ≤ 1800

Disponibilidad de horas en el departamento de corte y costura

1 𝑥 2 1

+ 𝑥2 ≤ 300

Disponibilidad de horas en el departamento

1 𝑥 8 1

+ 4 𝑥2 ≤ 100

1 3 1

Disponibilidad de horas en el departamento de empaque y envío

SOLUCION:

Cj 0 0 0

Bn s1 s2 s3 zj cj-zj

Cj

900 300 100 0

Bn

0 0

s1 s2

8

X2 zj cj-zj

300 166,668 400 3.200

5 X1 1 0,5 0,125 0 5

8 X2 1,5 0,3333 0,25 0 8

0 S1 1 0 0 0 0

0 S2 0 1 0 0 0

0 S3 0 0 1 0 0

5 X1 0,25 0,3333

8 X2 0 0

0 S1 1 0

0 S2 0 1

0 S3 -6 -1,3333

0,5 4 1

1 8 0

0 0 0

0 0 0

4 32 -32

Cj

Bn

0 5 8

s1 X1 X2 zj

174,9996 500,0015 149,9993

5 X1 0 1 0 5

8 X2 0 0 1 8

0 S1 1 0 0 0

0 S2 -0,75 3,0 -1,5 3,0

0 S3 -5,0 -3,9999 6,0 28,0001

0

0

0

-3,0

28,0001

3.700,0015 cj-zj

a) b) c) d)

500 guantes de modelo normal y 150 de modelo tipo catcher. Una utilidad de 3700 dolares. 725h dep CC, 300h dep T Y 100h dep E. Existe holgura en el dep CC de175h.

18.- La firma Erlanger Manufacturing Company fabrica dos productos. Las estimaciones de las utilidades son de $25 por cada unidad que se vende del producto 1, y $30 por cada unidad que se vende del producto 2. En seguida se resumen los requerimientos de mano de obra por hora para los productos en cada uno de los tres departamentos. DEPARTAMENTO A DEPARTAMENTO B DEPARTAMENTO C

PRODUCTO 1 1.50 2.00 0.25

PRODUCTO 2 3.00 1.00 0.25

Los supervisores de producción de cada departamento han estimado que estarán disponibles las siguientes cantidades de mano de obra para el siguiente mes: 45º horas en el departamento A, 300 horas en el departamento B y 50 horas en el departamento C. Suponiendo que a la empresa le interesa maximizar las utilidades, responda lo siguiente: a) ¿Cuál es el modelo de programación lineal para este problema? b) Obtenga la producción óptima ¿Qué cantidad se debe fabricar de cada producto y cuál es la utilidad que se proyecta? c) ¿Cuál es el tiempo programado de producción y el tiempo de holgura en cada departamento? VARIABLES X1= Unidades a fabricar del producto A X2 = Unidades a fabricar del producto B FUNCIÓN OBJETIVO Z (max)= 25X1 + 30X2 VARIABLES DE NO NEGATIVIDAD X1, X2>=0

SOLUCIÓN a) restricciones: 1.5 X1 +3X2