Universidad Nacional del Santa

Facultad de Ingeniería

Ingeniería de Sistemas e Informática

INVESTIGACION DE OPERACIONES I

TEMA:

Modelos PL – Método Simplex

Docente :

Dr. Juan Pablo Sánchez Chávez

Nombres :

Blas Reyes Emerson Michael

Código :

0201314003

Ciclo: VI

Septiembre, Chimbote2015

METODO SIMPLEX, SOLUCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL

PROBLEMA 01

Con la siguiente información resolver el modelo de PL aplicando el Método Simplex.D.V.D.

X1 = Numero Productos Terminados tipo “A” a fabricarX2 = Numero Productos Terminados tipo “B” a fabricarC1 = S/. 8 nuevos soles es la utilidad por unidad de AC2 = S/. 6 nuevos soles es la utilidad por unidad de A

Modelo de PL.Max: Z0 = 8 X1 + 4 X2 Función objetivo

S.a.:4 X1 + 2 X2 <= 60 Restricción Ensamble (60 horas disponibles)2 X1 + 4 X2 <= 48 Restricción Acabado (48 horas disponibles)X1, X2 >= 0 Restricción de no negatividad

Forma Normal:Max: Z0 = 8 X1 + 4 X2 + 0S1 + 0S2 Función objetivo

S.a.:4 X1 + 2 X2 + S1 = 60 Restricción Ensamble (60 horas disponibles)2 X1 + 4 X2 + S2 = 48 Restricción Acabado (48 horas disponibles)X1, X2, S1, S2 >= 0 Restricción de no negatividad

X1 X2 S1 S2 Solución LD Bi/Aij>=0

V.B Cj 8 4 0 0S1 0 4 2 1 0 60 15S2 0 2 4 0 1 48 24Zj 0 0 0 0 0

Cj - Zj 8 4 0 0

X1 X2 S1 S2 Solución LD Bi/Aij>=0

V.B Cj 8 4 0 0X1 8 1 ½ ¼ 0 15 30S2 0 0 3 -½ 1 18 6Zj 8 4 2 1/2 120

Cj - Zj 0 0 -2 0

X1 X2 S1 S2 Solución LD Bi/Aij>=0

V.B Cj 8 4 0 0X1 8 1 ½ 1/6 -1/6 12X2 4 0 1 -1/6 1/3 6Zj 8 4 2/3 0 120

Cj - Zj 0 0 -2/3 0

PROBLEMA 02: (Análisis de Inversiones)

Con la siguiente información resolver el modelo de PL aplicando el Método Simplex. Una institución financiera trata de determinar su portafolio de inversiones para el próximo año. Actualmente dispone de $ 500000 para invertir en bonos, préstamos hipotecarios, préstamos para compra de autos y prestamos personales. La tasa de rendimiento anual para cada inversión resulta ser: - Bonos = 10 % - Préstamos hipotecarios = 16 % - Préstamos para compra de autos = 13 % - Préstamos personales = 20 %

Para asegurar que la cartera de esta institución financiera no sea demasiado arriesgada, el gerente de inversiones de esta institución las siguientes 3 restricciones de cartera: 1. La cantidad invertida en préstamos personales no puede ser mayor que la invertida en bonos. 2. La cantidad invertida en préstamos hipotecarios no puede ser mayor que la invertida en préstamos para autos. 3. No puede invertirse más del 25 % de la cantidad total invertida en préstamos personales.

El objetivo de esta institución financiera es maximizar el rendimiento anual de su cartera de inversiones. Solución Definición de las variables de decisión Xj = Cantidad de dinero a invertir ($) durante un año en la actividad u opción j, donde j = 1, 2, 3 y 4 y 1 = Bonos2 = Préstamos hipotecarios 3 = Préstamos para compra de autos 4 = Préstamos personales

Zo = Ganancia total de las inversiones hechas durante un año

Modelo Final. Este es el modelo al que deben aplicar el método simplex

Max : Z0 = 0.10 X1 + 0.16 X2 + 0.13 X3 + 0.20 X4 s.a.:

1 X1 + 1 X2 + 1 X3 + 1 X4 + <= 500000 - 1 X1 + 1 X4 <= 0 1 X2 - 1 X3 <= 0 -0.25 X1 – 0.25 X2 – 0.25 X3 + 0.75 X4 <= 0 X1 , X2 , X3 , X4 >= 0

FORMA ESTANDAR:

Max : Z0 = 1/10 X1 + 4/25 X2 + 13/100 X3 + 1/5 X4 + 0S1 + 0S2 + 0S3 + 0S4

S.A.: 1 X1 + 1 X2 + 1 X3 + 1 X4 + S1 = 500000 - 1 X1 + 1 X4 +S2 = 0 1 X2 - 1 X3 + S3 =0 -0.25 X1 – 0.25 X2 – 0.25 X3 + 0.75 X4 + S4 = 0 X1, X2 , X3 , X4 ,S1,S2,S3,S4 >= 0

VBX1 X2 X3 X4 S1 S2 S3 S4

Ci 1/10 4/25 13/100 1/5 0 0 0 0 Bi

S1 0 1 1 1 1 1 0 0 0 500000 500000

S2 0 -1 0 0 1 0 1 0 0 0 0

S3 0 0 1 -1 0 0 0 1 0 0 NaN

S4 0 - 1/4 - 1/4 - 1/4 3/4 0 0 0 1 0 0

Zi 0 0 0 0 0 0 0 0 0

Cj-Zj 1/10 4/25 13/100 1/5 0 0 0 0 0

S1 0 2 1 1 0 1 -1 0 0 500000 250000

X4 1/5 -1 0 0 1 0 1 0 0 0 0

S3 0 0 1 -1 0 0 0 1 0 0 #¡DIV/0!

S4 0 1/2 - 1/4 - 1/4 0 0 - 3/4 0 1 0 0

Zi - 1/5 0 0 1/5 0 1/5 0 0

Cj-Zj 3/10 4/25 13/100 0 0 - 1/5 0 0 0

S1 0 0 2 2 0 1 2 0 -4 500000 250000

X4 1/5 0 - 1/2 - 1/2 1 0 - 1/2 0 2 0 0

S3 0 0 1 -1 0 0 0 1 0 0 0

X1 1/10 1 - 1/2 - 1/2 0 0 -3/2 0 2 0 0

Zi 1/10 - 3/20 - 3/20 1/5 0 - 1/4 0 3/5

Cj-Zj 0 31/100 7/25 0 0 1/4 0 - 3/5 0

S1 0 0 0 4 0 1 2 -2 -4 500000 125000

X4 1/5 0 0 -1 1 0 - 1/2 1/2 2 0 0

X2 4/25 0 1 -1 0 0 0 1 0 0 0

X1 1/10 1 0 -1 0 0 -1 1/2 1/2 2 0 0

Zi 1/10 4/25 - 23/50 1/5 0 - 1/4 31/100 3/5 0

Cj-Zj 0 0 59/100 0 0 1/4 - 31/100 - 3/5

X3 13/100 0 0 1 0 1/4 1/2 - 1/2 -1 125000

X4 1/5 0 0 0 1 1/4 0 0 1 125000

X2 4/25 0 1 0 0 1/4 1/2 1/2 -1 125000

X1 1/10 1 0 0 0 1/4 -1 0 1 125000

Zi 1/10 4/25 13/100 1/5 59/400 9/200 3/200 1/100 73750

Cj-Zj 0 0 0 0 - 59/400 - 9/200 - 3/200 - 1/100

VB X1 X2 X3 X4 S1 S2 S3 S4

Ci 1/10 4/25 13/100 1/5 0 0 0 0 Bi

S1 0 1 1 1 1 1 0 0 0 500000 500000

S2 0 -1 0 0 1 0 1 0 0 0 0

S3 0 0 1 -1 0 0 0 1 0 0 NaN

S4 0 - 1/4 - 1/4 - 1/4 3/4 0 0 0 1 0 0

Zi 0 0 0 0 0 0 0 0 0

Cj-Zj 1/10 4/25 13/100 1/5 0 0 0 0 0

S1 0 2 1 1 0 1 -1 0 0 500000 250000

X4 1/5 -1 0 0 1 0 1 0 0 0 0

S3 0 0 1 -1 0 0 0 1 0 0 #¡DIV/0!

S4 0 1/2 - 1/4 - 1/4 0 0 - 3/4 0 1 0 0

Zi - 1/5 0 0 1/5 0 1/5 0 0

Cj-Zj 3/10 4/25 13/100 0 0 - 1/5 0 0 0

S1 0 0 2 2 0 1 2 0 -4 500000 250000

X4 1/5 0 - 1/2 - 1/2 1 0 - 1/2 0 2 0 0

S3 0 0 1 -1 0 0 0 1 0 0 0

X1 1/10 1 - 1/2 - 1/2 0 0 -3/2 0 2 0 0

Zi 1/10 - 3/20 - 3/20 1/5 0 - 1/4 0 3/5

Cj-Zj 0 31/100 7/25 0 0 1/4 0 - 3/5 0

S1 0 0 0 4 0 1 2 -2 -4 500000 125000

X4 1/5 0 0 -1 1 0 - 1/2 1/2 2 0 0

X2 4/25 0 1 -1 0 0 0 1 0 0 0

X1 1/10 1 0 -1 0 0 -1 1/2 1/2 2 0 0

Zi 1/10 4/25 - 23/50 1/5 0 - 1/4 31/100 3/5 0

Cj-Zj 0 0 59/100 0 0 1/4 - 31/100 - 3/5

X3 13/100 0 0 1 0 1/4 1/2 - 1/2 -1 125000

X4 1/5 0 0 0 1 1/4 0 0 1 125000

X2 4/25 0 1 0 0 1/4 1/2 1/2 -1 125000

X1 1/10 1 0 0 0 1/4 -1 0 1 125000

Zi 1/10 4/25 13/100 1/5 59/400 9/200 3/200 1/100 73750

Cj-Zj 0 0 0 0 - 59/400 - 9/200 - 3/200 - 1/100

PROBLEMA 03:

La empresa Dynamix fabrica tres estilos diferentes de mesas. A, B y C. Cada modelo de mesa requiere de una cierta cantidad de tiempo para el corte de las piezas, su montaje y el correspondiente proceso de pintura. La empresa puede vender todas las unidades que fabrica. Es más, el modelo B también se puede vender sin pintar. Los datos técnico-económicos se muestran a continuación.

Formule el modelo de programación lineal para maximizar la contribución total mensual.SOLUCION:Definición de Variables de Decisión:

X1: Número de mesas de tipo A pintadaX2: Número de mesas de tipo B pintadaX3: Número de mesas de tipo B sin pintarX4: Número de mesas de tipo C pintada

Max: ZO=35X1+40X2+20X3+50X4S.a:

1X1 +2X2 +2X3 +3X4≤2002X1+4X2+4X3+7X4≤3004X1+4X2+0X3+5X4≤240X1,X2,X3,X4≥0

FUNCION ESTANDAR

Max: ZO=35X1+40X2+20X3+50X4+0S1+0S2+0S3

S.A:1X1 +2X2 +2X3 +3X4+S1 = 2002X1+4X2+4X3+7X4+S2 = 3004X1+4X2+0X3+5X4+S3 = 240X1,X2,X3,X4,S1,S2,S3≥0

X1 X2 X3 X4 S1 S2 S3SOLUCION LD COCIENTES

bi/aij>0VB CJ 35 40 20 50 0 0 0

S1 0 1 2 2 3 1 0 0 200 200/3S2 0 2 4 4 7 0 1 0 300 300/7S3 0 4 4 0 5 0 0 1 240 48ZJ 0 0 0 0 0 0 0 0

CJ-ZJ 35 40 20 50 0 0 0

S1 0 1/7 2/7 2/7 0 1 -3/7 0 500/7 500X4 50 2/7 4/7 4/7 1 0 1/7 0 300/7 150S3 0 18/7 8/7 -20/7 0 0 - 5/7 1 180/7 10ZJ 100/7 200/7 200/7 50 0 50/7 0 15000/7

CJ-ZJ 145/7 80/7 -60/7 0 0 -50/7 0

S1 0 0 2/9 4/9 0 1 -7/18 -1/18 70 315/2X4 50 0 4/9 8/9 1 0 2/9 -1/9 40 45X1 35 1 4/9 -10/9 0 0 -5/18 7/18 10 -9ZJ 35 340/9 50/9 50 0 25/18 145/18 2350

CJ-ZJ 0 20/9 130/9 0 0 -25/18 -145/18

S1 0 0 0 0 -1/2 1 -1/2 0 50X3 20 0 1/2 1 9/8 0 1/4 -1/8 45X1 35 1 1 0 5/4 0 0 1/4 60ZJ 35 45 20 265/4 0 5 25/4 3000

CJ-ZJ 0 -5 0 -81/5 0 -5 -25/4

PROBLEMA 04

Con la siguiente información resolver el modelo de PL aplicando el Método Simplex. David, Diana y Lidia son los únicos socios y empleados de una compañía de produce relojes. David y Diana pueden trabajar un máximo de 40 horas por semana (cada uno de ellos), mientras que Lidia solo puede trabajar hasta 22 horas semanales. La empresa hace dos tipos de relojes: relojes de pie y relojes de pared. Para hacer un reloj. David (ingeniero mecánico) ensambla las partes interna y Diana (ebanista) produce las cajas de madera elaboradas a mano. Lidia es responsable de recibir pedidos y enviar los relojes. El tiempo que se requiere para cada tarea se muestra en la siguiente tabla.

Cada reloj de pié construido y enviado deja una ganancia de S/. 300 nuevos soles, mientras que cada reloj de pared proporciona una ganancia de S/. 200 nuevos soles. Los tres socios desean determinar cuántos relojes de cada tipo deben producir por semana para maximizar la ganancia total.

Max: Zo = 300X1 + 200X2

S.A.: 6X1 + 4X2 <= 408X1 + 4X2 <= 403X1 + 3X2 <= 22X1 , X2 >= 0

FORMATO ESTANDAR:Zo = 300X1 + 200X2 + 0S1 + 0S2 + 0S3

S.A: 6X1 + 4X2 + S1 = 40

8X1 + 4X2 + S2 = 403X1 + 3X2 + S3 = 22X1 , X2, S1,S2,S3 >= 0

Cj300 200 0 0 0

Bi Bi/CjX1 x2 S1 S2 S3

0S1 6 4 1 0 0 40 40/6

0S2 8 4 0 1 0 40 40/8 (Menor)

0S3 3 3 0 0 1 22 40/3

Zj 0 0 0 0 0 0

Cj - Zj 300 200 0 0 0

0S1 0 1 1 -3/4 0 10

300 X1 1 1/2 0 1/8 0 5

0S3 0 3/2 0 -3/8 1 7

Zj 300 150 0 37,5 0 1500

Cj - Zj 0 50 0 -37,5 0

SOLUCION:Z = 1733,33X1 = 8/3X2 = 14/3

0S1 0 0 1 -1/2 -2/3 16/3

300 X1 1 0 0 1/4 -1/3 8/3

200 X2 0 1 0 -1/4 2/3 14/3

Zj 300 200 0 25 33,3 1733,33

Cj - Zj 0 0 0 -25 -33,3

PROBLEMA 05

Una Compañía dispone de S/. 5 000 000 para distribuirlos el próximo año entre

sus tres sucursales. Debido a compromisos de estabilidad del nivel de empleados

y por razones de inversión mínima, la CIA ha establecido un nivel mínimo de

fondos para cada sucursal, estos fondos mínimos son de S/. 350 000, 580 000 y

890 000 respectivamente. Debido a la naturaleza de su inversión, la sucursal 2 no

puede utilizar en inversión más de S/. 1 850 000, sin una expansión de capital

grande. Cada sucursal tiene la oportunidad de dirigir (Administrar) distintos

proyectos con los fondos que recibe. Para cada proyecto se ha establecido una

tasa de ganancia (como un % de la inversión). En el siguiente cuadro se dan los

datos respectivos para cada proyecto. Confeccionar el modelo de programación

lineal que determine en su solución la cantidad que cada sucursal debe invertir en

sus respectivos proyectos para obtener la máxima rentabilidad.

SOLUCION:

DEFINICIÓN DE LAS VARIABLES DE DECISIÓN

Sea: X ij = Cantidad que invierte sucursal i (i=1,2,3) en el proyecto j (j=1,2,…,8)

FUNCION OBJETIVO:

SUCURSAL PROYECTO TASA DE GANANCIA LIMITE SUPERIOR DE LA INVERSION (S/.)

1

1 6% 700 000

2 7% 580 000

3 8% 990 000

2

4 6% 810 000

5 9% 1200 000

6 10% 470 000

37 11% 720 000

8 7% 420 000

Se expresa como la maximización de los retornos de inversión.

Max. Z0 = 0.06 X11 + 0.07 X12 + 0.08 X13 + 0.06 X24 + 0.09 X25 + 0.10 X26 + 0.11 X37 + 0.07 X38

SUJETO A:

Cantidad Disponible

(X11 + X12 + X13) + ( X24 + X25 + X26) + X37 + X38 ≤ 5 000 000

Fondos mínimos a nivel a invertir en cada sucursal

X11 + X12 + X13 ≥ 350 000 -------> Sucursal 1 X24 + X25 + X26 ≥ 580 000 -------> Sucursal 2 X37 + X38 ≥ 890 000 -------> Sucursal 3

Fondos máximos a invertir la sucursal 2

X24 + X25 + X26 ≥ 1 850 000

Limites superiores de inversión por proyecto en cada sucursal

X11 ≤ 700 000 X12 ≤ 580 000 X13≤ 990 000 X24≤ 810 000 X25≤ 1 200 000 X26 ≤ 470 000 X37 ≤ 720 000 X38 ≤ 420 000

X ij ≥ 0 i=1, 2, 3

J=1, 2, 3, 4, 5, 6, 7, 8

FORMA ESTANDAR:

Max. Z0 = 0.06 X11 + 0.07 X12 + 0.08 X13 + 0.06 X24 + 0.09 X25 + 0.10 X26 + 0.11 X37 + 0.07 X38 +0S2 + 0S3 + 0S4 + 0S1 – MA3 – MA4 – MA5 + 0S5 + 0S6 + 0S7 + 0S8 + 0S9 + 0S10 + 0S11 + 0S12 + 0S13

1- (X11 + X12 + X13) + ( X24 + X25 + X26) + X37 + X38 + S1 ¿ 5 000 0002- X11 + X12 + X13 - S2 + A2 ¿ 350 000 -------> Sucursal 1

3- X24 + X25 + X26 – S3 + A3 ¿ 580 000 -------> Sucursal 24- X37 + X38 - S4 + A4 ¿ 890 000 -------> Sucursal 35- X24 + X25 + X26 + S5 ¿1 850 000 6- X11 + S6 ¿ 700 000 7- X12 + S7 ¿ 580 000 8- X13+S8=¿ 990 000 9- X24+S9=¿ 810 000 10-X25+S10=¿ 1 200 000 11-X26+S11=¿ 470 000 12-X37+S12=¿ 720 000 13-X38 + S13 ¿ 420 000

X1,X2,X3,X4,X5,X6,X7,X8,S2,S3,S4,,S1,A2,A3,A4,A5,S5,S6,S7,S8,S9,S10,S11,S12,S13 >=0