03. Ejemplo resuelto programación lineal

26
Ejemplo Productos Líquidos (TRANS.) Programación Lineal 1 Ejemplo de los Fertilizantes: (Fase 1: formulación del problema) Una empresa se dedica a la elaboración de dos tipos diferentes de fertilizantes: H-Fosfato y L-Fosfato. Para ello, utiliza tres clases de materias primas: Crudo 1, Crudo 2, Crudo 3. Los datos concretos para la fabricación de los fertilizantes son los siguientes: Tm de Crudo por Tm de Fertilizante Disponibilidad mensual Crudo H-Fosfato L-Fosfato (en Tm) de Crudo 1 2 1 1500 2 1 1 1200 3 1 0 500 Precio venta Tm 15 10 Se desea determinar el número de Tm a producir mensualmente, de cada fertilizante, para maximizar el ingreso total por ventas. Ejemplo de los Fertilizantes: (Fase 2: construcción del modelo matemático) Definición de las variables de decisión: x1 = número de Tm de H-Fosfato a producir mensualmente x2 = número de Tm de L-Fosfato a producir mensualmente Construcción del modelo matemático: Max. f(x) = 15 x1 + 10 x2 sujeto a 2 x1 + x2 ≤ 1500 (Tm de Crudo 1) x1 + x2 ≤1200 (Tm de Crudo 2) x1 ≤ 500 (Tm de Crudo 3) x1 ≥ 0, x2 ≥ 0

Transcript of 03. Ejemplo resuelto programación lineal

Page 1: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

1

Ejemplo de los Fertilizantes: (Fase 1: formulación del problema)

Una empresa se dedica a la elaboración de dos tipos diferentes de

fertilizantes: H-Fosfato y L-Fosfato. Para ello, utiliza tres clases de

materias primas: Crudo 1, Crudo 2, Crudo 3. Los datos concretos para la

fabricación de los fertilizantes son los siguientes:

Tm de Crudo por Tm de Fertilizante Disponibilidad mensual

Crudo H-Fosfato L-Fosfato (en Tm) de Crudo

1 2 1 1500

2 1 1 1200

3 1 0 500 Precio venta Tm 15 10

Se desea determinar el número de Tm a producir mensualmente, de cada

fertilizante, para maximizar el ingreso total por ventas.

Ejemplo de los Fertilizantes: (Fase 2: construcción del modelo matemático)

Definición de las variables de decisión:

x1 = número de Tm de H-Fosfato a producir mensualmente

x2 = número de Tm de L-Fosfato a producir mensualmente

Construcción del modelo matemático:

Max. f(x) = 15 x1 + 10 x2

sujeto a 2 x1 + x2 ≤ 1500 (Tm de Crudo 1)

x1 + x2 ≤1200 (Tm de Crudo 2)

x1 ≤ 500 (Tm de Crudo 3)

x1 ≥ 0, x2 ≥ 0

Page 2: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

2

Hipótesis realizadas:

- proporcionalidad: 2 x1

- aditividad: 2 x1 + x2 ≤ 1500

- continuidad (divisibilidad): x1, x2 ≥ 0

- determinismo (certidumbre)

- independencia entre las variables y homogeneidad

Representación gráfica de la región de factibilidad

Concepto de SFB (Solución Factible Básica) o Punto Extremo.

semiplano x1 ≤ 500

semiplano x1 + x2 ≤ 1 200

semiplano 2 x1 + x2 ≤ 1 500

Page 3: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

3

Ejemplo de los Fertilizantes: (Fase 3: resolución del modelo y obtención de la

solución)

Resolución gráfica

recta f = (15 x1 + 10 x2 =) 13 500

(300,900)

f = 13 500

(500,500)

f = 12 500

(0,1200)

f = 12 000

(0,0)

f = 0 (500,0)

f = 7 500

Page 4: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

4

Ejemplo de los Fertilizantes: (Fase 3: resolución del modelo y obtención de la

solución)

Resolución mediante ecuaciones de igualdad: método algebraico

Max. f(x) = 15 x1 + 10 x2 + 0 h1 + 0 h2 + 0 h3

sujeto a 2 x1 + x2 + h1 = 1500

x1 + x2 + h2 = 1200

x1 + h3 = 500

x1 ≥ 0 , x2 ≥ 0 , h1 ≥ 0 , h2 ≥ 0 , h3≥ 0

x1 = número de Tm de H-Fosfato a producir mensualmente

x2 = número de Tm de L-Fosfato a producir mensualmente

A las variables h1, h2, h3 las denominamos variables de holgura (así, h1 es el número

de Tm de Crudo 1 que sobra al mes).

1ª Solución Factible Básica (SFB): x=(0,0)

x1 = 0, x2 = 0, h1 = 1500, h2 = 1200, h3 = 500 f= 0

(x1, x2 variables no básicas ; h1, h2, h3 variables básicas )

Para ver si se puede aumentar el valor de f, se escriben de otro modo las igualdades

iniciales: se ponen las variables básicas y la función f en términos de las variables no

básicas

h1 = 1500 - 2 x1 - x2

h2 = 1200 - x1 - x2

h3 = 500 - x1

f = 0 + 15 x1 + 10 x2

aumentar f ⇔ aumentar x1 (por cada unidad que aumente x1, f aumenta 15): ¿cuánto?

x1 ≤ 2

1500 = 750, x1 ≤ 1200, x1 ≤ 500

hacemos x1 = 500 ⇒ h3 = 0 (sale de la base)

x2 = 0, h3 = 0 ; h1 = 500, h2 = 700, x1 = 500 f= 7500

Page 5: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

5

2ª Solución Factible Básica (SFB): x=(500,0)

x2 = 0, h3 = 0 ; h1 = 500, h2 = 700, x1 = 500 f= 7500

(x1, h3 variables no básicas ; h1, h2, x1 variables básicas )

Repetimos el proceso anterior y escribimos las variables básicas y la función f en

términos de las variables no básicas; para ello, despejamos x1 en la 3ª restricción y

sustituimos su valor en la 1ª, 2ª y f

h1 = 1500 - 2 (500- h3) - x2

h2 = 1200 - (500- h3) - x2

x1 = 500 - h3

f = 0 + 15 (500- h3) + 10 x2

es decir,

h1 = 500 - x2 + 2 h3

h2 = 700 - x2 + h3

x1 = 500 - h3

f = 7500 + 10 x2 - 15 h3

aumentar f ⇔ aumentar x2: ¿cuánto?

x2 ≤500, x2 ≤ 700

hacemos x2 = 500 ⇒ h1 = 0

h1 = 0, h3 = 0 ; x2 = 500, h2 = 200, x1 = 500 f= 12500

3ª Solución Factible Básica (SFB): x=(500,500)

h1 = 0, h3 = 0 ; x2 = 500, h2 = 200, x1 = 500 f= 12500

(h1, h3 variables no básicas ; x2, h2, x1 variables básicas )

Repetimos el proceso y escribimos las variables básicas y la función f en términos de las

variables no básicas; para ello, despejamos x2 en la 1ª restricción y sustituimos su valor

en la 2ª, 3ª y f

x2 = 500 - h1 + 2 h3

h2 = 700 - (500 - h1 + 2 h3) + h3

x1 = 500 - h3

f = 7500 + 10 (500 - h1 + 2 h3) - 15 h3

Page 6: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

6

x2 = 500 - h1 + 2 h3

h2 = 200 + h1 - h3

x1 = 500 - h3

f = 12500 - 10 h1 + 5 h3

aumentar f ⇔ aumentar h3: ¿cuánto?

h3 ≤ 200, h3 ≤ 500

hacemos h3 = 200 ⇒ h2 = 0

h1 = 0, h2 = 0 ; x2 = 900, h3 = 200, x1 = 300 f= 13500

4ª Solución Factible Básica (SFB): x=(300,900)

h1 = 0, h2 = 0 ; x2 = 900, h3 = 200, x1 = 300 f= 13500

(h1, h2 variables no básicas ; x2, h3, x1 variables básicas )

Repetimos el proceso y escribimos las variables básicas y la función f en términos de las

variables no básicas; para ello, despejamos h3 en la 2ª restricción y sustituimos su valor

en la 1ª, 3ª y f

x2 = 500 - h1 + 2 (200 + h1 - h2)

h3 = 200 + h1 - h2

x1 = 500 - (200 + h1 - h2)

f = 12500 - 10 h1 + 5 (200 + h1 - h2)

x2 = 900 + h1 - 2 h2

h3 = 200 + h1 - h2

x1 = 300 - h1 + h2

f = 13500 - 5 h1 - 5 h2

aumentar f ⇔ no se puede: la 4ª SFB es solución óptima

Page 7: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

7

Desarrollo gráfico

Desarrollo gráfico (despejando y sustituyendo)

Desarrollo gráfico (despejando y sustituyendo)

recta f = (15 x1 + 10 x2 =) 13 500

(300,900)

f = 13 500

(500,500)

f = 12 500

(0,1200)

f = 12 000

(0,0)

f = 0 (500,0)

f = 7 500

recta f = (15 x1 + 10 x2 =) 13 500

(300,900)

f = 13 500

Page 8: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

8

Ejemplo de los Fertilizantes: (Fase 4: interpretación y validación de la

solución) La política óptima de producción consiste en fabricar mensualmente 300 Tm de H-

Fosfato y 900 Tm de L-Fosfato, lográndose así un ingreso total por ventas de 13.500

unidades.

Ejemplo de los Fertilizantes: (Fase 5: ejecución de la solución y

establecimiento de controles)

Page 9: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

9

Ejemplo de los Fertilizantes: (Fase 3: resolución del modelo y obtención de la

solución)

Resolución por ecuaciones de igualdad: otra forma equivalente (para

WinQSB)

Max. f(x) = 15 x1 + 10 x2 + 0 h1 + 0 h2 + 0 h3

sujeto a 2 x1 + x2 + h1 = 1500

x1 + x2 + h2 = 1200

x1 + h3 = 500

x1 ≥ 0 , x2 ≥ 0 , h1 ≥ 0 , h2 ≥ 0 , h3 ≥ 0

1ª Solución Factible Básica (SFB): x=(0,0)

x1 = 0, x2 = 0, h1 = 1500, h2 = 1200, h3 = 500 f= 0

h1 = 1500 - 2 x1 - x2 2 x1 + x2 + h1 = 1500

h2 = 1200 - x1 - x2 x1 + x2 + h2 = 1200

h3 = 500 - x1 x1 + h3 = 500

f = 0 + 15 x1 + 10 x2 f(x) = 15 x1 + 10 x2 + 0

(x1, x2 variables no básicas ; h1, h2, h3 variables básicas )

aumentar f ⇔ aumentar x1: ¿cuánto?

x1 ≤ 2

1500 = 750, x1 ≤ 1200, x1 ≤ 500

hacemos x1 = 500 ⇒ h3 = 0

2ª Solución Factible Básica (SFB): x=(500,0)

x2 = 0, h3 = 0, x1 = 500, h1 = 500, h2 = 700 f= 7500

h1 = 500 - x2 + 2 h3 x2 + h1 - 2 h3 = 500

h2 = 700 - x2 + h3 x2 + h2 - h3 = 700

x1 = 500 - h3 x1 + h3 = 500

f = 7500 + 10 x2 - 15 h3 f(x) = 10 x2 - 15 h3 + 7500

(x1, h3 variables no básicas ; h1, h2, x1 variables básicas )

aumentar f ⇔ aumentar x2: ¿cuánto?

x2 ≤ 500, x2 ≤ 700

hacemos x2 = 500 ⇒ h1 = 0

Page 10: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

10

3ª Solución Factible Básica (SFB): x=(500,500)

h1 = 0, h3 = 0, x1 = 500, x2 = 500, h2 = 200 f= 12500

x2 = 500 - h1 + 2 h3 x2 + h1 - 2 h3 = 500

h2 = 200 + h1 - h3 - h1 +h2 + h3 = 200

x1 = 500 - h3 x1 + h3 = 500

f = 12500 - 10 h1 + 5 h3 f(x) = - 10 h1 + 5 h3 + 12500

(h1, h3 variables no básicas ; x2, h2, x1 variables básicas )

aumentar f ⇔ aumentar h3: ¿cuánto?

h3 ≤ 200, h3 ≤ 500

hacemos h3 = 200 ⇒ h2 = 0

4ª Solución Factible Básica (SFB): x=(300,900)

h1 = 0, h2 = 0, x1 = 300, x2 = 900, h3 = 200 f= 13500

x2 = 900 + h1 - 2 h2 x2 - h1 +2 h2 = 900

h3 = 200 + h1 - h2 - h1 + h2 + h3 = 200

x1 = 300 - h1 + h2 x1 +h1 - h2 = 300

f = 13500 - 5 h1 - 5 h2 f(x) = - 5 h1 -5 h2 + 13500

(h1, h2 variables no básicas ; x2, h3, x1 variables básicas )

aumentar f ⇔ no se puede: solución óptima

Page 11: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

11

Desarrollo gráfico (igualdades y pivotando)

recta f = (15 x1 + 10 x2 =) 13 500

(300,900)

f = 13 500

Page 12: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

12

Ejemplo de los Fertilizantes: (Fase 3: resolución del modelo y obtención de la

solución)

Resolución en forma de tabla

variables

SFB

Costo

inicial

Coeficientes de las variables en las

restricciones

Valor var. básicas

test del

cociente

coeficientes de las variables no básicas en la

función objetivo (costos reducidos)

Valor de la

función objetivo

1ª Solución Factible Básica (SFB): x=(0,0)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

h1 0 2 1 1 0 0 1500 750

h2 0 1 1 0 1 0 1200 1200

h3 0 1 0 0 0 1 500 500

15 10 0 0 0 0

2ª Solución Factible Básica (SFB): x=(500,0)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

h1 0 0 1 1 0 -2 500 500

h2 0 0 1 0 1 -1 700 700

x1 15 1 0 0 0 1 500 M

0 10 0 0 -15 7500

3ª Solución Factible Básica (SFB): x=(500,500)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

x2 10 0 1 1 0 -2 500 M

h2 0 0 0 -1 1 1 200 200

x1 15 1 0 0 0 1 500 500

0 0 -10 0 5 12500

4ª Solución Factible Básica (SFB): x=(300,900)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

x2 10 0 1 -1 2 0 900

h3 0 0 0 -1 1 1 200

x1 15 1 0 1 -1 0 300

0 0 -5 -5 0 13500

Page 13: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

13

Desarrollo gráfico (tablas)

recta f = (15 x1 + 10 x2 =) 13 500

(300,900)

f = 13 500

Page 14: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

14

Ideas previas para el algoritmo del Simplex: forma matricial

Max. f(x) = 15 x1 + 10 x2 + 0 h1 + 0 h2 + 0 h3

sujeto a 2 x1 + x2 + h1 = 1500

x1 + x2 + h2 = 1200

x1 + h3 = 500

x1 , x2 , h1 , h2 , h3 ≥ 0

Max f(x) = c x T sujeto a A x T = b

x ≥ 0

Max. f(x1,x2,h1,h2,h3) = ( )0,0,0,10,15

3

2

1

2

1

h

h

h

x

x

(c) (x T )

sujeto a

10001

01011

00112

3

2

1

2

1

h

h

h

x

x

=

500

1200

1500

(A) (x T ) (b)

x = (x1 , x2 , h1 , h2 , h3) ≥ 0

Page 15: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

15

Ideas previas para el algoritmo del Simplex: tablas en forma matricial

SFB inicial

variables

coeficientes en la f.o.

SFB

Costo

inicial

Coeficientes de las variables en las

restricciones

Valor var. básicas

test del

cociente

coeficientes de las variables en la función

objetivo (costos reducidos)

Valor de la

función objetivo

xi: variables

c: coeficientes en la f.o.

xB

cB :coeficientes en la f.o.

A

b

c Valor de la f. o.

SFB general (en una iteración cualquiera)

variables

coeficientes en la f.o.variables

SFB

(variables

básicas)

Costo

inicial

matriz actualizada de coeficientes

tecnológicos

Valores var.

básicas

test del

cociente

coeficientes de las variables no básicas en

la función objetivo (costos reducidos o

precios sombra)

Valor de la

función

objetivo

xi: variables

c

xB

cB

A = B-1

A

b = B-1

b

test del

cociente

c = c - cB B-1

A valor de la

f. o.

Page 16: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

16

Matriz de la SFB y su inversa en las tablas del algoritmo del Simplex

1ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

h1 0 2 1 1 0 0 1500 750

h2 0 1 1 0 1 0 1200 1200

h3 0 1 0 0 0 1 500 500

15 10 0 0 0 0

=100

010

001

B →

=−

100

010

0011B

2ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

h1 0 0 1 1 0 -2 500 500

h2 0 0 1 0 1 -1 700 700

x1 15 1 0 0 0 1 500 M

0 10 0 0 -15 7500

=100

110

201

B →

−−

=−

100

110

2011B

3ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

x2 10 0 1 1 0 -2 500 M

h2 0 0 0 -1 1 1 200 200

x1 15 1 0 0 0 1 500 500

0 0 -10 0 5 12500

=100

111

201

B →

−−

=−

100

111

2011B

Page 17: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

17

4ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

x2 10 0 1 -1 2 0 900

h3 0 0 0 -1 1 1 200

x1 15 1 0 1 -1 0 300

0 0 -5 -5 0 13500

=110

101

201

B →

−−−

=−

011

111

0211B

Page 18: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

18

Obtención de la tabla completa de una SFB desde la taba inicial

1ª Solución Factible Básica (SFB)

=100

010

001

B →

=−

100

010

0011B

=−

100

010

0011B multiplicado por

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

h1 0 2 1 1 0 0 1500

h2 0 1 1 0 1 0 1200

h3 0 1 0 0 0 1 500

15 10 0 0 0 0

se obtiene la tabla

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

h1 0 2 1 1 0 0 1500

h2 0 1 1 0 1 0 1200

h3 0 1 0 0 0 1 500

15 10 0 0 0 0

2ª Solución Factible Básica (SFB)

=100

110

201

B →

−−

=−

100

110

2011B

−−

=−

100

110

2011B multiplicado por

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

h1 0 2 1 1 0 0 1500

h2 0 1 1 0 1 0 1200

h3 0 1 0 0 0 1 500

15 10 0 0 0 0

se obtiene la tabla

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

h1 0 0 1 1 0 -2 500

h2 0 0 1 0 1 -1 700

x1 15 1 0 0 0 1 500

0 10 0 0 -15 7500

Page 19: 03. Ejemplo resuelto programación lineal

Ejemplo Productos Líquidos (TRANS.) Programación Lineal

19

3ª Solución Factible Básica (SFB)

=100

111

201

B →

−−

=−

100

111

2011B

−−

=−

100

111

2011B multiplicado por

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

h1 0 2 1 1 0 0 1500

h2 0 1 1 0 1 0 1200

h3 0 1 0 0 0 1 500

15 10 0 0 0 0

se obtiene la tabla

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

x2 10 0 1 1 0 -2 500

h2 0 0 0 -1 1 1 200

x1 15 1 0 0 0 1 500

0 0 -10 0 5 12500

4ª Solución Factible Básica (SFB)

=110

101

201

B →

−−−

=−

011

111

0211B

−−−

=−

011

111

0211B multiplicado por

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

h1 0 2 1 1 0 0 1500

h2 0 1 1 0 1 0 1200

h3 0 1 0 0 0 1 500

15 10 0 0 0 0

se obtiene la tabla

x1 x2 h1 h2 h3

15 10 0 0 0 SFB

x2 10 0 1 -1 2 0 900

h3 0 0 0 -1 1 1 200

x1 15 1 0 1 -1 0 300

0 0 -5 -5 0 13500

Page 20: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

20

Ejemplo de los Fertilizantes: cálculos vectoriales y matriciales

1ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

h1 0 2 1 1 0 0 1500 750

h2 0 1 1 0 1 0 1200 1200

h3 0 1 0 0 0 1 500 500

15 10 0 0 0 0

=100

010

001

B →

=−

100

010

0011B

b= B-1

b = I b =

500

1200

1500

= b

A = B-1

A = I A =

100

010

001

01

11

12

I =

10001

01011

00112

= A

c = c - cB B-1

A = c - 0 I A = (15, 10, 0, 0, 0) = c

f = cB B-1

b = 0 I b = 0

2ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

h1 0 0 1 1 0 -2 500 500

h2 0 0 1 0 1 -1 700 700

x1 15 1 0 0 0 1 500 M

0 10 0 0 -15 7500

=100

110

201

B →

−−

=−

100

110

2011B

Page 21: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

21

b = B-1

b =

−−

100

110

201

500

1200

1500

=

500

700

500

A = B-1

A =

−−

100

110

201

01

11

12

I =

01

10

101-B =

=

−−

10001

11010

20110

c = c - cB B-1

A = (15, 10, 0, 0, 0) – (0, 0, 15)

−−

100

110

201

01

11

12

I =

= (15, 10, 0, 0, 0) – (0, 0, 15)

−−

10001

11010

20110

=

= (15 - 15, 10 - 0, 0 - 0, 0 - 0, 0 - 15) = (0, 10, 0, 0, -15)

f = cB B-1

b = (0 , 0, 15)

500

700

500

= 7500

3ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

x2 10 0 1 1 0 -2 500 M

h2 0 0 0 -1 1 1 200 200

x1 15 1 0 0 0 1 500 500

0 0 -10 0 5 12500

=100

111

201

B →

−−

=−

100

111

2011B

b = B-1

b =

−−

100

111

201

500

1200

1500

=

500

200

500

Page 22: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

22

A = B-1

A =

−−

100

111

201

01

11

12

I =

01

00

101-B =

=

−−

10001

11100

20110

c = c - cB B-1

A = (15, 10, 0, 0, 0) – (10, 0, 15)

−−

100

111

201

01

11

12

I =

= (15, 10, 0, 0, 0) – (10, 0, 15)

−−

10001

11100

20110

=

= (15 - 15, 10 - 10, 0 - 10, 0 - 0, 0 + 5) = (0, 0, -10, 0, 5)

f = cB B-1

b = (10 , 0, 15)

500

200

500

= 5000 + 7500 = 12500

Page 23: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

23

4ª Solución Factible Básica (SFB)

x1 x2 h1 h2 h3

15 10 0 0 0 SFB cociente

x2 10 0 1 -1 2 0 900

h3 0 0 0 -1 1 1 200

x1 15 1 0 1 -1 0 300

0 0 -5 -5 0 13500

=110

101

201

B →

−−−

=−

011

111

0211B

b = B-1

b =

−−−

011

111

021

500

1200

1500

=

300

200

900

A = B-1

A =

−−−

011

111

021

01

11

12

I =

01

00

101-B =

=

−−−

01101

11100

02110

c = c - cB B-1

A = (15, 10, 0, 0, 0) – (10, 0, 15)

−−−

011

111

021

01

11

12

I =

= (15, 10, 0, 0, 0) – (10, 0, 15)

−−−

01101

11100

02110

=

= (15 - 15, 10 - 10, 0 - 5, 0 - 5, 0 + 0) = (0, 0, -5, -5, 0)

f = cB B-1

b = (10 , 0, 15)

300

200

900

= 9000 + 4500 = 13500

Page 24: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

24

Ejercicio 1: repetir el proceso anterior para el siguiente

Ejemplo de los Productos líquidos

Una empresa familiar se dedica a la elaboración de dos tipos diferentes de

productos líquidos para el hogar. Dichos productos precisan de la

utilización de tres máquinas distintas. Los datos concretos para la

elaboración de los productos líquidos son los siguientes:

índice de producción (horas/unidad) capacidad semanal

Máquina Producto1 Producto2 (horas/semana)

1 10 20 4000

2 5 5 1500

3 5 2 800 Beneficio neto 10 15

Se desea determinar el número de unidades de cada uno de los dos

productos líquidos a producir semanalmente, para maximizar el beneficio

neto por ventas.

Definición de las variables de decisión:

x1 = número de unidades de Producto1 a fabricar semanalmente

x2 = número de unidades de Producto2 a fabricar semanalmente

Construcción del modelo matemático:

Max. f(x) = 10 x1 + 15 x2

sujeto a 10 x1 + 20 x2 ≤ 4000

5 x1 + 5 x2 ≤ 1500

5 x1 + 2 x2 ≤ 800

x1 ≥ 0 , x2 ≥ 0

Page 25: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

25

Ejercicio 2: repetir el proceso anterior para el siguiente

Ejemplo de Fabricación de Productos

Una empresa elabora dos tipos de productos: A y B. Cada unidad de

producto, tanto del tipo A como del B, necesita para su elaboración, de la

utilización de dos tipos diferentes de máquinas M1 y M2: el producto A

requiere 4 horas de utilización de la máquina M1 y ninguna de la máquina

M2; mientras que el producto B, requiere 1 hora de la máquina M1 y 1

hora de la M2.

Por el número de máquinas disponibles de los tipos M1 y M2, se

pueden conseguir 2400 y 350 horas de trabajo semanalmente

respectivamente. Todas las unidades producidas a lo largo de la semana se

venden durante esa semana, y el beneficio que deja cada unidad del

producto A es de 7 unidades monetarias, mientras que el B deja 5 unidades

monetarias. Además, por restricciones de tipo legal, no se pueden producir

más de 350 unidades del producto A.

Plantear el problema de programación lineal que analice el número de

unidades que se deben fabricar de cada tipo con el fin de maximizar el

beneficio.

Definición de las variables de decisión:

x1 , número de unidades fabricadas por semana del producto A

x2 , número de unidades fabricadas por semana del producto B

Page 26: 03. Ejemplo resuelto programación lineal

Ejemplo Fertilizantes (TRANS.) Programación Lineal

26

Construcción del modelo matemático:

Max. f(x1,x2) = 7 x1 + 5 x2

sujeto a

4 x1 + x2 ≤ 2400

x2 ≤ 350

x1 ≤ 350

x1 , x2 ≥ 0