UNIDA 2 El Método Simplex

Método Gráfico.
PASOS:

1. Graficar restricciones.

2. Identificar la región de factibilidad.

3. Identificar los puntos más óptimos.

4. Graficar la F.O.

5. Encontrar la solución óptima (Punto óptimo).

Aplicar el “Método Gráfico” con el problema no. 1 planteado

anteriormente (problema de las mesas y sillas):

Maximizar Z = 8X1 + 6X2 1. Graficar restricciones: Rectas para

cada ecuación.
S.A 4X1 + 2X2 ≤ 60
4X1 + 2X2 = 60
2X1 + 4X2 ≤ 48
cuando X1 = 0, X2 = 30 (0, 30)
X1, X2 ≥ 0
X2 = 0, X1 = 15 (15, 0)
X1, X2 ≥ 0
2X1 + 4X2 = 48

cuando X1 = 0, X2 = 12 (0, 12)

X2 = 0, X1 = 24 (24, 0)
30
4X1 + 2X2 ≤ 60

2X1 + 4X2 ≤ 48

2. Identificar la región de factibilidad:

B Z = 24 En problemas donde se tengan

12
Z = 48 restricciones ≤, así es como se identifica
8 en el gráfico; desde el origen (0, 0) hasta
C
REGIÓN DE un segmento de las rectas de cada
4
FACTIBILIDAD restricción.

A
3 6
15 D 24

1
 3. Identificar los puntos más óptimos: Son aquellos que forman la región de factibilidad,
marcándolos con una letra en el gráfico, en el sentido de las manecillas del reloj.

A (0, 0)

B (0, 12)

C ( ¿? ) Este punto por no estar en el eje cartesiano, se debe calcular con “operaciones simultáneas”

D (15, 0)

Operaciones Simultáneas (punto C):

(4X1 + 2X2 = 60) -2  (un factor que al multiplicarlo con la ecuación, permita eliminar alguna de las variables)

2X1 + 4X2 = 48

-8X1 - 4X2 = -120 4(12) + 2X2 = 60  (por sustitución)

2X1 + 4X2 = 48 48 + 2X2 = 60

-6X1 -72 X2 = (60 – 48)/ 2 = 12/2

X1 = -72/ -6 = 12 X2 = 6

C (12, 6)

4. Graficar la F.O: Rectas para la ecuación 5. Encontrar la solución óptima (Punto

Z = 8X1 + 6X2. Se pide graficar dos rectas; Óptimo): En problemas de
buscar para Z un valor arbitrario o múltiplo MAXIMIZACIÓN, el punto óptimo es el
de los coeficientes de X1 y X2. “Último” que tocarían las rectas de la Z en
el gráfico; en este caso es el PUNTO C. Se
24 = 8X1 + 6X2
comprueba sustituyendo los puntos
cuando X1 = 0, X2 = 4 (0, 4) óptimos en la ecuación de la F.O.

X2 = 0, X1 = 3 (3, 0) A (0, 0) 8(0) + 6(0) = 0

48 = 8X1 + 6X2 B (0, 12) 8(0) + 6(12) = 72

cuando X1 = 0, X2 = 8 (0, 8) C (12, 6) 8(12) + 6(6) = 132

X2 = 0, X1 = 6 (6, 0) D (15, 0) 8(15) + 6(0) = 120

INTERPRETACIÓN:

La solución óptima es X1 = 12, X2 = 6, Z = 132

Elaborar 12 mesas y 6 sillas, para obtener una utilidad máxima de $132 dlls.
2
 Aplicar el “Método Gráfico” con el problema no. 2 planteado
anteriormente (problema de las dos fuentes alimenticias):

Minimizar Z = 0.375X1 + 0.50X2

S.A 100X1 + 200X2 ≥ 1,000 1. Graficar restricciones: Rectas para cada

ecuación.
400X1 + 250X2 ≥ 2,000 100X1 + 200X2 = 1,000
200X1 + 200X2 ≥ 1,500 cuando X1 = 0, X2 = 1,000/200 = 5 (0, 5)

X1, X2 ≥ 0 X2 = 0, X1 = 1,000/100 = 10 (10, 0)

400X1 + 250X2 = 2,000

cuando X1 = 0, X2 = 2,000/250 = 8 (0, 8)

X1, X2 ≥ 0
X2 = 0, X1 = 2,000/400 = 5 (5, 0)

200X1 + 200X2 = 1,500

100X1 + 200X2 ≥ 1,000
REGIÓN DE cuando X1 = 0, X2 = 1,500/200 = 7.5 (0, 7.5)
FACTIBILIDAD 400X1 + 250X2 ≥ 2,000
X2 = 0, X1 = 1,500/200 = 7.5 (7.5, 0)
200X1 + 200X2 ≥ 1,500
D
8
7.5
C
6

5
Z=3
Z = 1.5 2. Identificar la región de factibilidad:
3 B En problemas donde se tengan
restricciones ≥, así es como se identifica
A en el gráfico; abarcando un segmento de
4 5 7.5 8
10 las rectas de cada restricción.

3. Identificar los puntos más óptimos: Son aquellos que forman la región de factibilidad,
marcándolos con una letra en el gráfico, en el sentido de las manecillas del reloj.

A (10, 0)

B ( ¿? ) Este punto por no estar en el eje cartesiano, se debe calcular con “operaciones simultáneas”

C ( ¿? ) Este punto por no estar en el eje cartesiano, se debe calcular con “operaciones simultáneas”

D (0, 8)

3
 Operaciones Simultáneas (punto B):

(100X1 + 200X2 = 1,000) -2  (un factor que al multiplicarlo con la ecuación, permita eliminar alguna de las
variables)

200X1 + 200X2 = 1,500

-200X1 - 400X2 = -2,000 100 X1 + 200(2.5) = 1,000  (por sustitución)

200X1 + 200X2 = 1,500 100X1 + 500 = 1,000

-200X2 -500 X1 = (1,000 – 500)/ 100 = 500/100

X2 = -500/ -200 = 2.5 X1 = 5

B (5, 2.5)

Operaciones Simultáneas (punto C):

400X1 + 250X2 = 2,000

(200X1 + 200X2 = 1,500) -2  (un factor que al multiplicarlo con la ecuación, permita eliminar alguna de
las variables)

400X1 + 250X2 = 2,000 400X1 + 250(6.66) = 2,000  (por sustitución)

-400X1 - 400X2 = -3,000 400X1 + 1,665 = 2,000

-150X2 -1,000 X1 = (2,000 – 1,665)/ 400 = 335/400

X2 = -1,000/ -150 = 6.66 X1 = 0 .83

C (0.83, 6.66)

4. Graficar la F.O: Rectas para la ecuación 5. Encontrar la solución óptima (Punto

Z = 0.375X1 + 0.5X2. Se pide graficar dos Óptimo): En problemas de MINIMIZACIÓN, el
rectas; buscar para Z un valor arbitrario o punto óptimo es el “Primero” que tocarían las
múltiplo de los coeficientes de X1 y X2. rectas de la Z en el gráfico; en este caso es el
PUNTO B. Se comprueba sustituyendo los puntos
3 = 0.375X1 + 0.5X2
óptimos en la ecuación de la F.O.
cuando X1 = 0, X2 = 6 (0, 6)
A (10, 0) 0.375(10) + 0.5(0) = 3.75
X2 = 0, X1 = 8 (8, 0)
B (5, 2.5) 0.375(5) + 0.5(2.5) = 3.12
1.5 = 0.375X1 + 0.5X2 C (0.83, 6.66) 0.375(0.83) + 0.5(6.66) = 3.64
cuando X1 = 0, X2 = 3 (0, 3) D (0, 8) 0.375(0) + 0.5(8) = 4
4
X2 = 0, X1 = 4 (4, 0)
 INTERPRETACIÓN:

La solución óptima es X1 = 5, X2 = 2.5, Z = 3.12

La doctora deberá suministrar al paciente 5 onzas de salmón y 2.5

onzas de pollo, con un costo mínimo de $3.12/ onza.

Método Simplex.
TABLA SIMPLEX:

Variables Originales Variables holgura (LD) Valor de la

F.O asociado a
Variables la solución
básicas Z X1 X2 …… Xn S1 S2 …… Sn actual
1 Z1 – C 1 Z2 – C 2 ……. Zn – C n 0 0 …….. 0 0

S1 0 a11 a12 ……. A1n 1 0 ……. 0

Identificación
S2 0 a21 a22 ……. a2n 0 1 ……. 0 del punto
extremo
…..

…..

…..

…..

…..

…..

…..

…..
asociado a la
base actual
Sm 0 am1 am2 ……. amn 0 0 ……. 1

Procedimiento:
PASO 1. Construir la tabla inicial igualando a cero la F.O y agregando las variables de holgura
correspondientes en cada restricción. (las variables básicas serán aquellas que formen la
matriz identidad y sean vector unitario, o sea, las formadas por 1 y 0).

PASO 2. Determinar la variable entrante: MAXIMIZACIÓN  La más negativa del renglón de Z

MINIMIZACIÓN  La más positiva del reglón de Z

PASO 3. Determinar la variable saliente. Es aquella cuyo cociente positivo sea menor al dividir
el lado derecho entre el coeficiente correspondiente en la columna de la variable entrante
(columna pivote).

PASO 4. Restablecer la base mediante simples “operaciones matriciales”.

5
PASO 5. La solución óptima será cuando en el renglón de Z para:

MAXIMIZACIÓN Todos positivos o ceros

MINIMIZACIÓN  Todos negativos o ceros

Si no, repetir los pasos anteriores.

Aplicar el “Método Simplex” al problema no. 1.

Maximizar Z = 8X1 + 6X2

S.A 4X1 + 2X2 ≤ 60

2X1 + 4X2 ≤ 48

X1, X2 ≥ 0

Paso 1. Construir tabla inicial….

Z – 8X1 - 6X2 = 0  Igualar F.O a cero

4X1 + 2X2 + S1 = 60 Agregar Variables de holgura

2X1 + 4X2 + S2 = 48 en cada restricción

Z X1 X2 S1 S2 LD
1 -8 -6 0 0 0

S1 0 4 2 1 0 60 60 /4 = 15

S2 0 2 4 0 1 48 48 / 2 = 24

1 0 -2 2 0 120

X1 0 1 1/2 1/4 0 15 15 / (1/2) = 30

S2 0 0 3 -1/2 1 18 18 / 3 = 6

6
 1 0 0 5/3 2/3 132

X1 0 1 0 1/3 -1/6 12

X2 0 0 1 -1/6 1/3 6

INTERPRETACIÓN:

La solución óptima es X1 = 12, X2 = 6, Z = 132

Elaborar 12 mesas y 6 sillas, para obtener una utilidad máxima de

$132 dlls.

Procedimiento para resolver problemas con variables

artificiales.
Método de la Gran M.
Este método es utilizado para resolver problemas que contengan restricciones del tipo
“mayor que” o simplemente “igual que”; agregando a cada una de las restricciones de esta
clase una variable a la cual llamaremos “variable artificial”, la cual no tiene valor material,
pero el hecho de que alguna de estas variables artificiales esté en la base, se paga con un
castigo o pena; por lo que este método trata de que estas variables no tengan valor mayor a
cero en la solución óptima o que no tomen parte en esta solución.

Procedimiento:
Paso 1. Cambiar de la forma canónica a la forma estándar las restricciones. Si son del tipo
“mayor o igual que” se restará la variable de holgura “S” y se la adiciona la variable artificial
“R”. Si la ecuación es del tipo “igual que”, solo se adiciona la variable “R”.

Tipo de
Variables
restricción
<= + Si
>= - Si + R i
= + Ri

7
Paso 2. Agregar a la F.O las variables artificiales que se originaron, multiplicadas por una
constante “M”, cada una de las variables artificiales. “M” es un valor muy grande que se
interpreta como una pena o multa por tener una variable artificial dentro de la base.

Para problemas de minimización se añadirán las variables a Z de la siguiente manera:

Z = +MRi

Para problemas de maximización se añadirán las variables en Z así:

Z = -MRi

Paso 3. Formar la tabla del método simplex, tomando como variables básicas a las variables
de holgura, si hay restricciones del tipo “menor o igual que” y a las variables artificiales si hay
restricciones del tipo “mayor o igual que” o “igual que”.

Paso 4. Verificar si en todas las variables básicas, el vector unitario positivo está
correctamente establecido. De lo contrario, hay que realizar operaciones matriciales
elementales.

Paso 5. Proceder con el método simplex para llegar a la solución óptima.

Ejemplo 1:

Resolver el siguiente problema lineal, con el método de la gran M:

Minimizar Z = -3X1 + 5X2

S.A X1 ≤4

X2 ≤ 6

3X1 + 2X2 ≥ 18

X1, X2 ≥ 0

Paso 1. Cambiar a la forma estándar las restricciones:

Tipo de
Variables
restricción
<= + Si
>= - Si + R i
= + Ri

8
Paso 2. Agregar a la F.O las variables artificiales que se originaron multiplicadas por una
constante “M”:

Min Z = -3X1 + 5X2 + MR1

Z + 3X1 - 5X2 - MR1 = 0  Igualar F.O a cero

X1 + S1 = 4 Agregar variables de holgura y

X2 + S2 = 6 artificiales en cada

3X1 + 2X2 – S3 + R1= 18 restricción

Paso 3, 4 y 5. Formar la tabla del método simplex, realizar operaciones matriciales y llegar a la
solución óptima.

Z X1 X2 S1 S2 S3 R1 LD
1 3 -5 0 0 -M -M 0

S1 0 1 0 1 0 0 0 4

S2 0 0 1 0 1 0 0 6

R1 0 3 2 0 0 -1 1 18

1 3+3M -5+2M 0 0 -M 0 18M

S1 0 1 0 1 0 0 0 4 4/1=4

S2 0 0 1 0 1 0 0 6 6/0=∞

R1 0 3 2 0 0 -1 1 18 18 / 3 = 6

-
1 0 -5+2M -3-3M 0 -M 0
12+6M

X1 0 1 0 1 0 0 0 4 4/0=∞

S2 0 0 1 0 1 0 0 6 6/1=6

R1 0 0 2 -3 0 -1 1 6 6/2=3

1 0 0 -21/2 0 -5/2 -M+5/2 3

X1 0 1 0 1 0 0 0 4

S2 0 0 0 3/2 1 1/2 -1/2 3

X2 0 0 1 -3/2 0 -1/2 1/2 3

9
 Este último tabulado es óptimo; el termino en Z correspondiente a la variable artificial
R1 (-M+5/2 < 0), porque “M” es un número negativo bastante grande y como R1 está fuera de
la base, R1 = 0, por lo que la solución es también óptima para el problema original. Por lo tanto,
la solución óptima es:

X1 = 4, X2 = 3, S1 = 0, S2 = 3, S3 = 0, R1 = 0, Z = 3

Ejemplo 2:

Resolver el siguiente problema lineal, con el método de la gran M:

Minimizar Z = 200X1 + 240X2

S.A 10X1 + 5 X2 ≥ 50

X1 ≤2

X1, X2 ≥ 0

6 S1 = 0, S2 = 0, R1 = 0, Z = 1,840
Solución óptima: X1 = 26, X2 = 2,

10