Método Simplex Procedimiento con ejemplos Parte 1 Diciembre 2020 PDF

Preview

Summary

Download Método Simplex Procedimiento con ejemplos Parte 1 Diciembre 2020 PDF

Description

Método Simplex Parte I Profesora Rosa María Da Rocha 15/12/2020

Problemas de Programación Lineal con m Restricciones y n Incógnitas.

Problemas de Programación Lineal con m Restricciones y n Incógnitas. Es de la forma: Maximizar o

Z=C1x1+ C2x2+…+ Cnxn

Minimizar Sujeto a:

a11x1+a12x2+…+a1nxn (≤ ,=,≥)b1 a21x1+a22x2+…+a2nxn (≤ ,=,≥)b2 ………………….. am1x1+am2x2+…+amnxn (≤ ,=,≥)bm xi≥0

con las bi≥0

Ejemplo: Maximizar Z=2𝑥1 + 7𝑥2 + 3𝑥3 Sujeto a 𝑥1 + 2𝑥2 + 𝑥3 ≤ 10 5𝑥1 + 𝑥2 + 3𝑥3 = 20 3𝑥1 + 4𝑥2 + 7𝑥3 ≥ 30 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 El método gráfico ya no es aplicable cuando el número de variables es mayor que 2. Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Método Simplex Este método utiliza el método de Gauss-Jordan con PIVOTEO y se puede utilizar con cualquier cantidad de variables. Aprenderemos a usarlo por casos.

Caso I.

Cuando existen restricciones con ≤

Procedimiento para tratar al PPL de la forma: Maximizar Z=C1x1+ C2x2+…+ Cnxn Sujeto a:

a11x1+a12x2+…+a1nxn ≤ b1 a21x1+a22x2+…+a2nxn ≤ b2 ………………….. am1x1+am2x2+…+amnxn ≤ bm xi≥0

con las bi≥0

Definiciones importantes Variables No Básicas(VNB): Son aquellas n-m variables que son iguales a cero en el simplex al resolver el sistema de ecuaciones.

Variables Básicas (VB): Son las que tienen una valor distinto de cero (o cero en casos muy raros) al hacer cero las n-m variables.

Variables de Holgura: Cuando las restricciones son de la forma ≤ se le suma una variable Si llamada variables de Holgura para transformar la desigualdad en igualdad, esta variable siempre es mayor o igual a cero. Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Procedimiento Tomando como base la tabla Simplex del Libro Haussler

Usaremos un ejemplo para la mejor compresión

Ejemplo: Resuelva el PPL usando el método Simplex Maximizar Z=30𝑥1 + 40𝑥2 Sujeto a 3𝑥1 + 2𝑥2 ≤ 60 2𝑥1 + 3𝑥2 ≤ 60 𝑥1 , 𝑥2 ≥ 0

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Paso 1. Transformar las desigualdades en igualdades sumando las variables de holgura así a11x1+a12x2+…+a1nxn + S1 a21x1+a22x2+…+a2nxn

= b1 + S2

=b2

………………….. am1x1+am2x2+…+amnxn

+Sm

= bm

Ejemplo: Maximizar Z=30𝑥1 + 40𝑥2 Sujeto a 3𝑥1 + 2𝑥2 + 𝑆1 = 60 2𝑥1 + 3𝑥2 + 𝑆2 = 60 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Paso 2.

Escribir la función Objetivo en la forma -C1x1- C2x2-… Cnxn

+Z

=0

Ejemplo: Maximizar

−30𝑥1 − 40𝑥2

+𝑍 = 0

Sujeto a 3𝑥1 + 2𝑥2 + 𝑆1 = 60 2𝑥1 + 3𝑥2 + 𝑆2 = 60 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Paso 3. Escribir la tabla simplex VB

Z

x1 a11 a21

x2 a12 a22

… …

xn a1n a2n

am1 -C1

am2 - C2

… …

amn Cn

S1 S2 1 0 … 0 1 ………………….. 0 0 0 0

Sn 0 0

Z 0 0

TI b1 b2

1 0

0 1

bm

cocientes

0

Los número ubicados en la última fila se le llaman INDICADORES VB: Variables Básicas TI: Término Independiente

Ejemplo:

VB

𝑍

𝑥1

𝑥2

𝑆1

𝑆2

𝑍

𝑇𝐼

3

2

1

0

0

60

2

3

0

1

0

60

-30

-40

0

0

1

0

Matemáticas Aplicadas (Diciembre 2020)

Cocientes

Prof. Rosa María Da Rocha

Paso 4. Identificar la Variables Básicas. Las variables que se encuentran encima de las columnas que forma la matriz identidad de mxm (m es el número de restricciones) serán las variables básicas y se colocan en ese orden en la columna donde dice VB. Nota: Observa que las variables básicas todas tienen coeficiente cero en la fila de Z en todas las tablas incluyendo la original.

Ejemplo:

VB

𝑥1

𝑥2

𝑆1

𝑆2

𝑍

𝑇𝐼

𝑆1 𝑆2 𝑍

3

2

1

0

0

60

2

3

0

1

0

60

-30

-40

0

0

1

0

Matemáticas Aplicadas (Diciembre 2020)

Cocientes

Prof. Rosa María Da Rocha

Determinar si estamos en la solución Óptima.

Paso 5.

Si todos los indicadores son mayores o iguales a cero la tabla es la óptima y podemos dar la respuesta al problema sino debes pasar al paso 6. VB S1 S2

x1 a11 a21

x2 a12 a22

… …

S3 Z

am1 -C1

am2 - C2

… …

xn S1 S2 a1n 1 0 a2n 0 1 ………………….. amn 0 0 Cn 0 0 Indicadores

…

Sn 0 0

Z 0 0

TI b1 b2

1 0

0 1

bm 0

Ejemplo:

VB

𝑥1

𝑥2

𝑆1

𝑆2

𝑍

𝑇𝐼

𝑆1 𝑆2 𝑍

3

2

1

0

0

60

2

3

0

1

0

60

-30

-40

0

0

1

0

Cocientes

No estamos en la tabla óptima pues hay indicadores Negativos

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Paso 6. Elección del PIVOTE Variable que ENTRA como Variable básica: Elegir en los indicadores cuál es el número más negativo y la variable que entra será justamente la que está encima de ese número. Variable que SALE: Se efectúa la división de cada elemento de la columna TI entre el correspondiente de la columna de la variable que entra (no tome en cuenta en esa columna los ceros o los números negativos) y tome la menor división, la variable que SALE se encuentra en la columna de VB y está en la fila de la menor división. El PIVOTE será el elemento que se encuentra en la fila de la variable que sale y en la columna de la variable que entra.

Ejemplo: Tabla No. 1

VB

𝑥1

𝑥2

𝑆1

𝑆2

𝑍

𝑇𝐼

Cocientes

𝑆1 𝑆2 𝑍

3

2

1

0

0

60

60/2 =30

2

3

0

1

0

60

60/3=20

-30

-40

0

0

1

0

PIVOTE

ENTRA 𝑥2

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

SALE

𝑆2

Paso 7. Actualizar la columna de las Variables Básicas.

Ejemplo: Tabla No. 1

VB

𝑥1

𝑥2

𝑆1

𝑆2

𝑍

𝑇𝐼

Cocientes

𝑆1 𝑆2 𝑍

3

2

1

0

0

60

60/2 =30

2

3

0

1

0

60

60/3=20

-30

-40

0

0

1

0

𝑆1

𝑆2

𝑍

𝑇𝐼

𝑆2

ENTRA 𝑥2 Tabla No.

VB

𝑥1

𝑥2

𝑆1 𝑥2 𝑍

Matemáticas Aplicadas (Diciembre 2020)

SALE

Cocientes

1

0

60/2 =30

0

0

60/3=20

0

1

Prof. Rosa María Da Rocha

Paso 8. Aplicar Gauss- Jordan con PIVOTE y luego pasar al paso 5

Ejemplo: Tabla No. 2

VB

𝑥1

𝑥2

𝑆1

𝑆1 𝑥2 𝑍

5/3

0

1

2/3

1

-10/3

𝑆2

𝑍

𝑇𝐼

Cocientes

-2/3

0

20

20/5/3=12

SALE

0

1/3

0

20

20/2/3=30

𝑆1

0

0

40/3

1

800

𝑍

𝑇𝐼

ENTRA 𝑥1 Tabla No. 3

VB

𝑥1

𝑥2

𝑆1

𝑆2

𝑥1 𝑥2 𝑍

1

0

3/5

-2/5

0

12

0

1

-2/5

3/5

0

12

0

0

2

12

1

840

Cocientes

Todos los indicadores son positivos ESTAMOS EN LA TABLA OPTIMA PODEMOS DAR LA RESPUESTA.

𝑥1 = 12

𝑥2 = 12 𝑆1 = 0

Matemáticas Aplicadas (Diciembre 2020)

𝑍 = 840 𝑆2 = 0

Prof. Rosa María Da Rocha

Eje Ejerc rc rcici ici icio oN No. o. 1 p par ar ara a la cclas las lase e vvir ir irtu tu tual. al. Resolver el PPL Maximizar 𝑍 = 2𝑥1 − 𝑥2 + 𝑥3 Sujeto a 2𝑥1 + 𝑥2 − 𝑥3 ≤ 10 𝑥1 + 𝑥2 + 𝑥3 ≤ 2 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

 Pr Prep ep epar ar aram am amos os el P PPL PL 2𝑥1 + 𝑥2 − 𝑥3 + 𝑆1 𝑥1 + 𝑥2 + 𝑥3 −2𝑥1 + 𝑥2 − 𝑥3

= 10 + 𝑆2 = 2

+𝑍 = 0

𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 ≥ 0

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

 Tab Tabla la lass Sim Simplex plex Tabla No. 1 VB

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑍

𝑇𝐼

𝑆1 𝑆2 𝑍

2

1

-1

1

0

0

10

10/2=5

1

1

1

0

1

0

2

2/1=2

-2

1

-1

0

0

1

0

Cocientes

Tabla No. 2 VB

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑍

𝑇𝐼

𝑆1 𝑥1 𝑍

0

-1

-3

1

-2

0

6

1

1

1

0

1

0

2

0

3

1

0

2

1

4

Cocientes

TA TABLA BLA ÓP ÓPTIM TIM TIMA A

 Dar la solución 𝑥1 = 2

𝑥2 = 0 𝑆1 = 6

Matemáticas Aplicadas (Diciembre 2020)

𝑥3 = 0

𝑍=4

𝑆2 = 0

Prof. Rosa María Da Rocha

Eje Ejerc rc rcici ici icio oN No. o. 2 p par ar ara a la cclas las lase e vvir ir irtu tu tual. al. Resolver el PPL Maximizar 𝑊 = 2𝑥1 + 𝑥2 − 2𝑥3 Sujeto a −2𝑥1 + 𝑥2 + 𝑥3 ≥ −2

2𝑥1 − 𝑥2 − 𝑥3 ≤ 2

𝑥1 − 𝑥2 + 𝑥3 ≤ 4 𝑥1 + 𝑥2 + 2𝑥3 ≤ 6 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

 Pr Prep ep epar ar aram am amos os el P PPL PL 2𝑥1 − 𝑥2 − 𝑥3 + 𝑆1 𝑥1 − 𝑥2 + 𝑥3 𝑥1 + 𝑥2 + 2𝑥3

=2 + 𝑆2

=4

+ 𝑆3 = 6

−2𝑥1 − 𝑥2 + 2𝑥3 + 𝑊 = 0 𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 , 𝑆3 ≥ 0

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

 Tab Tabla la lass SSim im implex plex Tabla No. 1 VB

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑆3

𝑊

𝑇𝐼

𝑆1 𝑆2 𝑆3 𝑊

2

-1

-1

1

0

0

0

2

2/2=1

1

-1

1

0

1

0

0

4

4/1=4

1

1

2

0

0

1

0

6

6/1=6

-2

-1

2

0

0

0

1

0

Cocientes

Tabla No. 2 VB

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑆3

𝑊

𝑇𝐼

Cocientes

𝑥1 𝑆2 𝑆2 𝑊

1

-1/2

-1/2

1/2

0

0

0

1

NEGATIVO

0

-1/2

3/2

-1/2

1

0

0

3

NEGATIVO

0

3/2

5/2

-1/2

0

1

0

5

0

-2

1

1

0

0

1

4

5/(3/2)=10/3

Tabla No. 3 VB

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑆3

𝑊

𝑇𝐼

𝑥1 𝑆2 𝑥2 𝑊

1

0

1/3

1/3

0

1/3

0

8/3

0

0

7/3

-2/3

1

1/3

0

14/3

0

1

5/3

-1/3

0

2/3

0

10/3

0

0

10/3

1/2

0

4/3

1

26/3

TABLA ÓPTIMA

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Cocientes

 Dar la solución

𝑥1 = 8/3 𝑆1 = 0

𝑥2 = 10/3 𝑆2 = 14/3

Matemáticas Aplicadas (Diciembre 2020)

𝑥3 = 0 𝑆3 = 0

𝑊 = 26/3

Prof. Rosa María Da Rocha

AP APL LICA ICACI CI CION ON ONES ES L LOS OS P PROB ROB ROBL LEMAS DE PR PROG OG OGRA RA RAMAC MAC MACION ION LI LINE NE NEAL AL Apli Aplica ca cació ció ción nN No. o. 1 Una compañía fabrica tres tipos de muebles para patio: sillas, mecedoras y sillones. Cada uno requiere de madera, plástico y aluminio, como se muestra en la tabla siguiente:

Silla Mecedora Sillón

Ma Madera dera 1 unidad 1 unidad 1 unidad

Plá Plásti sti stico co 1 unidad 1 unidades 2 unidades

Aluminio 2 unidades 3 unidades 5 unidades

La compañía cuenta con 400 unidades disponibles de madera, 500 de plástico y 1450 de aluminio. Cada silla, mecedora y sillón se vende a $21, $24 y $36, respectivamente. Suponga que todos los muebles pueden venderse, determine la producción para que el ingreso total sea máximo. ¿Cuál es el ingreso máximo? Pr Proced oced ocedimien imien imiento. to. Pas Paso o1

Definir las variables correctamente.

𝑥1 : 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑠𝑖𝑙𝑙𝑎𝑠 𝑞𝑢𝑒 𝑠𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑛 𝑥2 : 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑚𝑒𝑐𝑒𝑑𝑜𝑟𝑎𝑠 𝑞𝑢𝑒 𝑠𝑒 𝑝𝑜𝑑𝑢𝑐𝑒𝑛 𝑥3 : 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑠𝑖𝑙𝑙𝑜𝑛𝑒𝑠 𝑞𝑢𝑒 𝑠𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑛 Pas Paso o2

Plantear la Función Objetivo. (F.O.)

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝐼 = 21𝑥1 + 24𝑥2 + 36𝑥3 Pas Paso o3

Escribir todas las restricciones y las condiciones de no negatividad.

𝑥1 + 𝑥2 + 𝑥3 ≤ 400 𝑥1 + 𝑥2 + 2𝑥3 ≤ 500

(𝑚𝑎𝑑𝑒𝑟𝑎) (𝑝𝑙á𝑠𝑡𝑖𝑐𝑜)

2𝑥1 + 3𝑥2 + 5𝑥3 ≤ 1450 (𝑎𝑙𝑢𝑚𝑖𝑛𝑖𝑜) 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Pas Paso o4

Resolver por el método Simplex.

 Pr Prep ep epar ar aram am amos os el P PPL PL 𝑥1 + 𝑥2 + 𝑥3 + 𝑆1

= 400

𝑥1 + 𝑥2 + 2𝑥3

+ 𝑆2

2𝑥1 + 3𝑥2 + 5𝑥3

= 500

+ 𝑆3 = 1450

−21𝑥1 − 24𝑥2 − 36𝑥3 + 𝐼 = 0 𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 , 𝑆3 ≥ 0

 Tab Tabla la lass SSim im implex plex Tabla No. 1 VB

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑆3

𝐼

𝑇𝐼

Cocientes

𝑆1 𝑆2 𝑆3 𝐼

1

1

1

1

0

0

0

400

400/1=400

1

1

2

0

1

0

0

500

500/2=250

2

3

5

0

0

1

0

1450

1450/5=290

-21

-24

-36

0

0

0

1

0

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑆3

𝐼

𝑇𝐼

1/2

1/2

0

1

-1/2

0

0

150

Cocientes 300

1/2

1/2

1

0

1/2

0

0

250

500

-1/2

1/2

0

0

-5/2

1

0

200

400

-3

-6

0

0

18

0

1

9000

Tabla No. 2 VB

𝑆1 𝑥3 𝑆3 𝐼

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Tabla No. 3

VB 𝑥2 𝑥3 𝑆3 𝐼

𝑥1

𝑥2

𝑥3

𝑆1

𝑆2

𝑆3

𝐼

𝑇𝐼

1

1

0

2

-1

0

0

300

0

0

1

-1

1

0

0

100

-1

0

0

-1

-2

1

0

50

3

0

0

12

12

0

1

10800

Cocientes

TABLA ÓPTIMA Respuesta Numérica

𝑥1 = 0 𝑆1 = 0

Pas Paso o5

𝑥2 = 300 𝑆2 = 0

𝑥3 = 100 𝑆3 = 50

𝐼 = 10800

Dar la respuesta en forma verbal

Se deben producir para obtener un ingreso máximo con las condiciones dadas 0 sillas, 300 mecedoras, 100 sillones y se obtiene un ingreso total máximo de $10800. Sobrantes de insumos 0 unidades de madera, 0 unidades de plástico y 50 unidades de alumnio

Matemáticas Aplicadas (Diciembre 2020)

Prof. Rosa María Da Rocha

Apli Aplica ca cació ció ción nN No. o. 2 La señora Medina elabora hallacas durante todo el año en la ciudad de Coro, en diciembre del año 2017 ella dispone de Bs 5.000.000 para invertirlos en la elaboración de hallacas, el costo para elaborar el relleno de cada hallaca es el siguiente: el guiso tradicional 10000 Bs, cochino 6000 Bs y vegetarianas 7000 Bs. El costo de las hojas de plátano para envolverlas es de 1.000 Bs por cada hallaca, el costo de ...