Investigación Operativa

Unidad: Teoría de decisiones y modelos de programación

lineal

Docente: Johnny. PachecoContreras

Tema: Modelos de programación lineal
• Formulación de problemas de programación lineal.
• Método Gráfico: Solución de problemas de
programación lineal de dos variables. Casosespeciales
en problemas de programación lineal.

• Método Simplex: Planteamiento de problemas de

programación lineal de dos o más variables.
 Formulación de problemas de programación lineal (PPL)
Ejemplo - Maximización
Gepetto S.L., manufactura muñecos y trenes de madera; y quiere maximizar sus beneficios.
¿Cuántos muñecos y cuántos trenes debefabricar?
Cada muñeco: Cada tren:
• Produce un beneficio neto de $3. • Produce un beneficio neto de $2.
• Requiere 2 horas de trabajo de acabado. • Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora de trabajo de carpintería. • Requiere 1 hora trabajo de carpintería.
Cada semana Gepetto puede disponerde:
• Todo el material que necesite.
• Solamente 100 horas de acabado.
• Solamente 80 horas de carpintería.

También:
• La demanda de trenes puede ser cualquiera (sinlímite).
• La demanda de muñecos es como mucho40.
Este problema es un ejemplo típico de un problema de
programación lineal (PPL)
Variables de Decisión Función Objetivo. En Restricciones
cualquier PPL, la decisión a tomar Son desigualdades que limitan los
es como maximizar (normalmente
x = nº de muñecos producidos a el beneficio) o minimizar (el costo) posibles valores de las variables de
la semana de alguna función de las variables decisión.
y = nº de trenes producidos a la de decisión. Esta función a En este problema las restricciones
semana maximizar o minimizar se llama vienen dadas por la disponibilidad
función objetivo. de horas de acabado y carpintería
y por la demanda de muñecos.
El objetivo de Gepetto es elegir
También suele haber restricciones
valores de x e y para maximizar 3x de signo o no negatividad:
+ 2y. Usaremos la variable z para
denotar el valor de la función
objetivo. La función objetivo de x≥ 0
Gepetto es: y≥ 0
Restricciones
Cuando x e y crecen, la función objetivo de Gepetto también crece.
Pero no puede crecer indefinidamente porque, para Gepetto, los valores de x e y están limitados por
las siguientes tres restricciones:
– Restricción 1: no más de 100 horas de tiempo de acabado pueden ser usadas.
– Restricción 2: no más de 80 horas de tiempo de carpintería pueden serusadas.
– Restricción 3: limitación de demanda, no deben fabricarse más de 40 muñecos.
Estas tres restricciones pueden expresarse matemáticamente
por las siguientes desigualdades:
– Restricción 1: 2 x + y ≤ 100
– Restricción 2: x + y ≤ 80
– Restricción 3: x ≤ 40
Además, tenemos las restricciones de signo: x ≥ 0 e y ≥0
Formulación matemática del PPL

Variables de Decisión Muñeco Tren

X = nº de muñecos Beneficio 3 2 Max z = 3x + 2y (función objetivo)

producidos a la semana
Acabado 2 1 <=100 2 x + y ≤ 100 (acabado)
y = nº de trenes producidos a
la semana Carpintería 1 1 <=80 x + y ≤ 80 (carpintería)

Demanda <=40 x <=40 (demanda muñecos)

Formulación matemática del PPL
Para el problema de Gepetto, combinando las restricciones de signo x ≥ 0 e y ≥ 0 con la
función objetivo y las restricciones, tenemos el siguiente modelo de optimización:

Max z = 3x + 2y (función objetivo)

Sujeto a (s.a:) 2x + y ≤ 10 (restricción de acabado)
0
x + y ≤ 80 (restricción de carpintería)
x ≤ 40 (restricción de demanda de muñecos)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
Regiónfactible
La región factible de un PPLes el conjunto de todos los puntos que satisfacen todas las restricciones. Es
la región del plano delimitada por el sistema de desigualdades que formanlas restricciones.
x = 40 e y = 20 está en la región factible Max z = 3x + 2y (función objetivo)
porque satisfacen todas las restricciones de
Gepetto.
Sujeto a (s.a:)
Sin embargo, x = 15, y = 70 no está en la
región factible porque este punto no satisface 2x + y ≤ 100 (restricción de acabado)
la restricción de carpintería [15 + 70 > 80].
x + y ≤ 80 (restricción de carpintería)
x ≤ 40 (restricción de demanda de
muñeco
s)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)
 • Para un problema de maximización, una solución óptima es un
Solución óptima punto en la región factible en el cual la función objetivo tiene un
valor máximo.
Se puede demostrar que la • Para un problema de minimización, una solución óptima es un
punto en la región factible en el cual la función objetivo tiene un
solución óptima de un PPL valor mínimo.
está siempre en la frontera de • La mayoría de PPL tienen solamente una solución óptima. Sin
la región factible, en un vértice embargo, algunos PPL no tienen solución óptima, y otros
(si la solución es única) o en PPLtienen un número infinito desoluciones.
un segmento entre dos
vértices contiguos (si hay • Más adelante veremos que la solución del PPLde Gepetto es x =
infinitas soluciones) 20 e y = 60. Esta solución da un valor de la función objetivo de:
z = 3x + 2y = 3·20 + 2·60 = 180
Cuando decimos que x = 20 e y = 60 es la solución óptima,
estamos diciendo que, en ningún punto en la región factible, la
función objetivo tiene un valor (beneficio) superior a180.
 Método Gráfico: Solución de problemas de programación
lineal de dos variables
Representación Gráfica de las restricciones
Cualquier PPLcon sólo dos variables puede 120
Y
resolverse gráficamente.
Por ejemplo, para representar gráficamente la 100
P1
primera restricción, 2x + y ≤ 100 :
80

2X + Y= 10 0
Dibujamos la recta 2x + y = 100 60

X=0 => Y=100 P1:(0,100)

40
Y=0 => X=50 P1:(50,100)
20
(x,y) : (20,20)
Elegimos el punto (20,20) 0 X
Reemplazamos en la desigualdad: 0 20 40 P2 60 80 100

(2·(20) + (20) ≤ 100). Cumple, así que

tomamos el semiplano que lo contiene.
Dibujar la región factible
Puesto que el PPLde Gepetto tiene dos variables, se puede resolver
gráficamente. La región factible es el conjunto de todos los puntos
que satisfacen las restricciones:
2 x +y ≤ 100 (restricción de acabado)
x +y ≤ 80 (restricción de carpintería)
x ≤ 40 (restricción de demanda)
x ≥0 (restricción de signo)
y ≥0 (restricción de signo)

Vamos a dibujar la región factible que satisface

estas restricciones.
 Teniendo en cuenta las restricciones de
Dibujar la región factible signo (x ≥ 0, y ≥ 0), nos queda:
Restricciones:
2 x + y ≤ 100 Y
120
x + y ≤ 80
100
P1
x ≤ 40
x≥ 0 80
y≥0 2X + Y= 10 0
60

Dibujamos la recta 2x + y = 100 40

X=0 => Y=100 P1:(0,100)
20
Y=0 => X=50 P2:(50,100)
(x,y) : (20,20)
0 X
0 20 40 P2 60 80 100

Elegimos el punto (20,20)

Reemplazamos en la desigualdad:
La cumple (2·(20) + (20) ≤ 100), así que tomamos el semiplano que lo
contiene.
Dibujar la región factible
Teniendo en cuenta las restricciones de
Restricciones:
signo (x ≥ 0, y ≥ 0), nos queda:
2 x + y ≤ 100
x + y ≤ 80 120
Y

x ≤ 40
100
x≥ 0
P1
y≥ 0 80
X+ Y= 80
60
Dibujamos la recta x + y = 80
X=0 => Y=80 P1:(0,80) 40
Y=80 => X=0 P2:(80,0)
20
(x,y)= (20,20)
Elegimos el punto (20,20). P2
0 X
Reemplazamos en la desigualdad: 0 20 40 60 80 100
La cumple ((20) + (20) ≤ 80), así que tomamos el
semiplano que lo contiene.
Dibujar la región factible
Restricciones: Teniendo en cuenta las restricciones de
2 x + y ≤ 100 signo (x ≥ 0, y ≥ 0), nos queda:
x + y ≤ 80 Y
120
x ≤ 40
100
x≥ 0 X= 4 0
y≥ 0 80

60
Dibujamos la recta x = 40
40
Línea vertical que cruza el eje Xen40.
(x,y)=(20,20)
20
Elegimos el semiplano que cumple la desigualdad:
el punto (20,20). 0 X
0 20 40 60 80 100
La cumple ((20) ≤ 40), así que tomamos el
semiplano que lo contiene.
Dibujar la región factible
Y
120

X = 40
100

La intersección de todos
80
estos semiplanos
(restricciones) nos da la
60
X + Y= 80
región factible.

40
Región
Factible
20 2X + Y= 100

0 X
0 20 40 60 80 100
Vértices de la región factible
Y
120

Restricciones: 100
X = 40 La región factible (al estar
2 x +y ≤ 100 limitada por rectas) es un
polígono.
x +y ≤ 80 80
E Enesta caso, el polígono ABCDE.
x ≤ 40
D
x ≥0 60
X + Y= 80 Como la solución óptima está en
y ≥0 alguno de los vértices (A, B, C, D
40 o E) de la región factible,
Región calculamos esos vértices.
Factible C
20 2X + Y= 100

A B
0 X
0 20 40 60 80 100
Vértices de la región factible
Y
Los vértices de la región factible son 120
intersecciones de dos rectas.
El punto Bes la intersección de las rectas: 100
X = 40
X=40
Eje X(Y=0) 80
La solución es:
x = 40 60
X + Y= 80
y =0
40
Región
B(x,y) =B(40,0).
Factible
20 2X + Y= 100
B(40,0)
0 X
0 20 40 60 80 100
 Vértices de la región factible
Y
120
Los vértices de la región factible son
intersecciones de dos rectas.
X = 40
100
El punto Ces la intersección de las rectas:
X=40
80
2x + y = 100
La solución es:
60
Reemplazar el valor de X=40 en la recta X + Y= 80
2x + y = 100
40
Región
x =40 Factible C(40,20)
20 2X + Y= 100
y =20

0 X
C(x,y) =C(40,0). 0 20 40 60 80 100
 Vértices de la región factible
Los vértices de la región factible son Y
intersecciones de dos rectas. 120

El punto D es la intersección de las rectas:

x + y = 80 …………………………(1) 100
X = 40
2x + y = 100 …………………………(2)
La solución es:
80
Restar (2) – (1)
2x + y = 100
60
D(40,20)
x + y = 80 X + Y= 80
------------------
x = 20 ..…..(x=20 reemplazar en(1) o (2)) 40
Región
x = 40
Factible
20 2X + Y= 100
y =20
0 X
D (x,y) =D(40,20). 0 20 40 60 80 100
 Vértices de la región factible
Y
120
Los vértices de la región factible son
intersecciones de dos rectas.
El punto Bes la intersección de la recta y el X = 40
100
eje Y:
X+ Y= 80 E(0,80)
80
Eje Y(Y=80)

La solución es: 60
X + Y= 80
x=0
y = 80 40
Región
E(x,y) = E(0,80). Factible
20 2X + Y= 100

0 X
0 20 40 60 80 100
Resolucióngráfica Y
160

140
Para hallar la solución óptima, dibujamos las
120
rectas en las cuales los puntos tienen el
mismo valor de z. 100

La figura muestra estas líneaspara: E(0,80)

80

z= 0 60
D(20,60)

z = 100
40
z = 180
20 Región C(40,20)
Max z = 3x + 2y Factible X
0
-40 -20 A(0,0) 0 20 40B(40,0)6 0 80 100
-20
Z=0 Z=40 Z=180
-40
Resolucióngráfica Y
160

140
La última recta de z que interseca (toca) la
120
región factible indica la solución óptima para
el PPL. Para el problema de Gepetto, esto 100

ocurre en el punto D. E(0,80)

80
D(20,60)
60
(x = 20, y = 60, z = 180).
40

Max z = 3x + 2y 20 Región C(40,20)

0
Factible X
-40 -20 A(0,0) 0 20 40B(40,0)6 0 80 100
-20
Z=0 Z=40 Z=180
-40
Resolución analítica

Max z = 3x + 2y 120
Y

También podemos encontrar la La solución óptimaes:

100
solución óptima calculando el x = 20 muñecos
valor de z en los vértices de la E(0,80) y = 60 trenes
80
región factible.
z = 180 Dólares de beneficio
D(20,60)
60
Vértice z = 3x +2y
A(0, 0) z = 3*0 +2*0 = 0 40

B(40, 0) z = 3*40+ 2*0 = 120

C(40, 20) z = 3*40+ 2*20 = 160 20 C(40,20)

D(20, 60) z = 3*20+ 2*60 = 180 A(0,0) B(40,0)

0 X
E(0, 80) z= 3*0 + 2*80 = 160 0 20 40 60 80 100
Hemos identificado la región factible para el problema de
Gepetto y buscado la solución óptima, la cual era el punto
en la región factible con el mayor valorposible de z.
Recuerda que:
La región factible en cualquier PPLestá limitada por segmentos
(es un polígono, acotado o no).

La región factible de cualquier PPLtiene solamente unnúmero

finito de vértices.

Cualquier PPLque tenga solución óptima tiene un vértice que es

óptimo.
 Formulación de problemas de programación lineal (PPL)
Ejemplo - Minimización
Dorian Auto quiere saber ¿cuántos Dorian Auto fabrica y vende coches y furgonetas. La empresa
anuncios debe contratar en cada tipo quiere emprender una campaña publicitaria en TV y tiene que
de programa para que el costo de la decidir comprar los tiempos de anuncios en dos tipos de
campaña publicitaria seamínimo? programas: del corazón y fútbol.

• Cada anuncio del programa del corazón es visto por 6

millones de mujeres y 2 millones dehombres.
• Cada partido de fútbol es visto por 3 millones de mujeres y 8
millones de hombres.
• Un anuncio en el programa de corazón cuesta $ 50.000 y un
anuncio del fútbol cuesta $ 100.000.
• Dorian Auto quisiera que los anuncios sean vistos por lo
menos 30 millones de mujeres y 24 millones de hombres.
 Formulación del problema:
• Cada anuncio del programa del corazón es visto por 6
millones de mujeres y 2 millones dehombres. Millonesde Corazó Fútb
• Cada partido de fútbol es visto por 3 millones de personas n (x) ol
mujeres y 8 millones de (y)

• hombres.
mujeres 6 3 6x + 3y ≥ 30
• Un anuncio en el programa de corazón cuesta $50.000
y un anuncio del fútbol cuesta$100.000.
• Dorian Auto quisiera que los anuncios sean vistos por
lo menos 30 millones de mujeres y 24 millones de hombres 2 8 2x + 8y ≥ 24
hombres.
• Dorian Auto quiere saber cuántos anuncios debe
contratar en cada tipo de programa para que el coste Costo
50 100 50x +100y
de la campaña publicitaria sea mínimo. Miles $
Formulación del problema
Variables de decisión:
x = nº de anuncios en programa de corazón
y = nº de anuncios en fútbol
Min z = 50x + 100y (función objetivo en Miles de dólares)s.a:
6x + 3y ≥ 30 (mujeres)
2x + 8y ≥ 24 (hombres)
x ≥ 0 (no negatividad)
y ≥ 0 (no negatividad)
Dibujar la región factible
Teniendo en cuenta las restricciones de
Restricciones: signo (x ≥ 0, y ≥ 0), nos queda:
6x + 3y ≥ 30 Y
14
2x + 8y ≤ 24
x≥ 0 12

P1
y≥ 0 10

Dibujamos la recta 6x + 3y = 30 6
X=0 => Y=100 P1:(0,10)
Y=5 => X= 0 P2 :(50,100) 4 6X + 3Y =30

2
(x,y) : ( 2,2) P2
0 X
0 2 4 6 8 10 12 14

Elegimos el punto (2,2).

Reemplazamos en la desigualdad:
No cumple (6·(2) + 3.(2) ≥ 30), así que tomamos el
semiplano que no lo contiene.
Dibujar la región factible Teniendo en cuenta las restricciones de
signo (x ≥ 0, y ≥ 0), nos queda:
Restricciones: Y
6x + 3y ≥ 30
14

2x + 8y ≤ 24 12

x≥ 0 10

y≥ 0 8

6
Dibujamos la recta 2x + 8y = 24
X=0 => Y= 3 P1:(0,3) 4

Y=12 => X= 0 P2 :(50,100) 2

(x,y) : (2,2) 2X + 8Y = 24
0 X
0 2 4 6 8 10 12 14

Elegimos el punto (2,2).

Reemplazamos en la desigualdad:
No cumple (6·(2) + 3.(2) ≥ 30), así que tomamos el
semiplano que no lo contiene.
Dibujar la región factible
Y
14

12

10
Regi n
8
ó
6
Fact le
4 6X + 3Y = 30 ib
2

0 X
0 2 4 6 8 10 12 14
2X + 8Y = 24

La intersección de todos estos semiplanos (restricciones)

nos da la región factible.
Vértices de la región factible
Y
14
Restricciones:
12
6x + 3y ≥ 30 A
La región factible es
10 un área no acotada.
2x + 8y ≤ 24 Regi n
8
x≥ 0 ó
6
y≥ 0 Fact le
A
4 ib
2 6X + 3Y =30

0 B X
0 2 4 6 8 10 12 14
2X + 8Y = 24 C

Como la solución óptima está en alguno de los

vértices (A, B, o C) de la región factible, calculamos
esos vértices.
Vértices de la región factible
Y
Los vértices de la región factible son 14
intersecciones de dos rectas.
El punto Aes la intersección de las rectas: 12
A(0,10)
6x + 3y = 30 10
Eje Y(Y=10) Región
8
Facti le
La solución es: 6 b
x= 0 A
4 6X + 3Y =30
y =10
2
B
A (x,y) =A(0,10). 2X + 8Y = 24 C
0 X
0 2 4 6 8 10 12 14
Vértices de la región factible
Y
14
Los vértices de la región factible son intersecciones
de dos rectas.
12
El punto Bes la intersección de las rectas:
A(0,10)
6x + 3y = 30 …………………………(1) 10
2x + 8y = 24…………………………(2)
Regi n
La solución es: 8
Restar 3*(2) – (1)
ó
6x + 24y = 72 6
Facti le
b A
6x + 3y =30
4
------------------ 6X + 3Y = 30
y = 2 ..…..(y=2 reemplazar en(1) o (2)) 2
B(4,2)

La solución es: 0 C X
0 2 4 2X+ 68Y =24 8 10 12 14
x= 4
y=2

B(x,y) =B(4,2).
Vértices de la región factible
Y
Los vértices de la región factible son 14

intersecciones de dos rectas.

12
El punto Ces la intersección de las rectas: A(0,10)
2x + 8y = 24 10

Eje X(X=12) Región

8
Facti le
La solución es: 6 b
x = 12 A
4 6X + 3Y =30
y= 0
B(4,2)
2
C(x,y) =C(12,0). 2X + 8Y =24 C(12,0)
0 X
0 2 4 6 8 10 12 14
Resolucióngráfica
Y
Para hallar la solución óptima, 14
dibujamos las rectas en las cuales los
puntos tienen el mismo valor dez. 12
A(10,0) Región
Lafigura muestra estas líneaspara: 10 Facti ble
z= 800 8
z= 600
6
z= 400
4

Max z = 50x + 100y 2

B(4,2) C(12,0)
0 X Z=800
-4 -2 0 2 4 6 8 10 12 14 16
-2 Z=600
Z=400
-4
Resolucióngráfica
Y
La primera recta de z que interseca (toca) 14

la región factible indica la solución óptima 12

para el PPL. Para el problema de Dorian A(10,0) Regi ón
10
Auto, esto ocurre en el punto B. Factible
8

6
(x = 4, y = 4, z = 400).
4

Max z = 50x + 100y 0

B(4,2) C(12,0)
XZ=800
-4 -2 0 2 4 6 8 10 12 14 16
-2 Z=600
Z=400
-4
 Resolución analítica Y
14

12
Max z = 50x + 100y A(0,10)
10

También podemos encontrar la solución óptima 8

Regi n
calculando el valor de z en los vértices de la región ó
factible. 6
Facti le A
Vértice z = 50x + 100y 4 b
A(0, 10) z = 50*0 +100*10 =1000
2 6X + 3Y =30
D(4, 2) z = 50*4 +100*2 = 400
0 B(4,2) X
C(12,0) z = 50*12+ 100*0 = 600 0 2 4 6 8 10 12 14
2X+ 8Y =24
C( 12,0)

El coste mínimo se obtiene en B

La solución óptimaes:
x = 4 anuncios en pr. corazón
y = 2 anuncios en futbol
z = 400 en Miles de dólares decosto.
Casosespeciales en problemas de programación lineal
Número de Soluciones de un PPL

Los dos ejemplos anteriores, Gepetto y Dorian Algunos PPLtienen un número infinito
Auto, tienen, cada uno, una única solución de soluciones óptimas (alternativas o
óptima. No en todos los PPLocurre esto. Se múltiples soluciones óptimas).
pueden dar también las siguientes
posibilidades:

Algunos PPLno tienen soluciones

factibles (no tienen región factible).

Algunos PPLson no acotados: Existen

puntos en la región factible convalores
de z arbitrariamente
Número infinito de soluciones óptimas
Consideremos el siguiente problema: Y
80
Max. z = 3x +2y 70
s.a:
60
3x + 2y ≤ 120 C
x + y ≤ 50 50

x, y≥0 40
B
30

Cualquier punto (solución) situado en el 20

segmento AB puede ser una solución 10
óptima de z=120. A
0
X
-10 0 10 20 30 40 50 60
-10
Z=60 Z=100 Z=120
Sin soluciones factibles
Consideremos el siguiente problema:
Max z = 3x + 2y Y
80
s.a:.
No existeregión
3x + 2y ≤ 120 70
factible x ≥ 30
x + y ≤ 50 60

x ≥ 30 50
3x + 2y ≤ 120

y ≥ 30
40
y ≥ 30
x, y≥0
30

No existe región factible x + y ≤ 50

20

10

0 X
0 10 20 30 40 50 60
PPLnoacotado
Y
Consideremos el siguiente problema: 10

max z = 2x – y 9

s.a: x – y ≤ 1 8

2x + y ≥ 6 7

x, y ≥ 0 6
x – y=1
5

La región factible es no acotada. Se muestran en el 4

gráfico las rectas de nivel para z = 4 y z = 6. Pero 3
podemos desplazar las rectas de nivel hacia la 2x+ y=6
derecha indefinidamente sin abandonar la región 2

factible. 1

0
0 1 Z=4 2 3 Z=6 4 5 6 7 8 9 10

Por tanto, el valor de z puede crecer indefinidamente.

 Método Simplex
Cálculo de una iteración simplex por medio de un ejemplo numérico.

Ejercicio 1:
Max Z= 3X1 + 2X2
S.A. 2X1+X2<=18
2X1+3X2<=42
3X1+ X2 <= 24
X1 >= 0, X2 >= 0
 Método Simplex

Las variables S1, S2y S3son las holguras

asociadas con las restricciones Z– 3X1 – 2X2 =0
respectivas.
Ejemplo: 2X1 + X2 + S1 = 18
X1 <= 10 ==> X1+Holgura =10
2X1 + 3X2 + S2 = 42
3X1 + X2 + S3 =24
 Método Simplex
De esta manera, la tabla inicial Var. Var. No Básicas Var. de Holgura Sol.
simplex se representa como Básicas
sigue:
X1 X2 S1 S2 S3

S1 2 1 1 0 0 18

S2 2 3 0 1 0 42

S3 3 1 0 0 1 24
Z -3 -2 0 0 0 0
 Método Simplex
Entra como variable básica: Iteración 1

Var. Var. No Básicas Var. de Holgura Sol. Oper.

Básicas
X1 X2 S1 S2 S3

S1 2 1 1 0 0 18 18/2 =9

S2 2 3 0 1 0 42 42/2 =21
Sale
S3 3 1 0 0 1 24 24/3 =8
Z -3 -2 0 0 0 0

Elegir la columna Pivot con el valor mas negativo en Zy luego la fila con el
menor valor en la columna Oper.
 Método Simplex
Entra como variable básica

Var. Var. No Básicas Var. de Holgura Sol. Oper.

Básicas
X1 X2 S1 S2 S3

S1 0 1/3 1 0 -2/3 2 f(S1) – 2f(X1)

S2 0 7/3 0 1 -2/3 26 f(S2) – 2f(X1)

X1 1 1/3 0 0 1/3 8 (1/3)f(S3)

0 -1 0 0 1 24 f(Z)+3f(X1)

Elegir la columna Pivot con el valor mas negativo en Zy luego la fila con el
menor valor en la columna Oper.
 Método Simplex
Entra como variable básica: Iteración 2

Var. Var. No Básicas Var. de Holgura Sol. Oper.

Básicas
X1 X2 S1 S2 S3
Sale
S1 0 1/3 1 0 -2/3 2 2/(1/3)=6

S2 0 7/3 0 1 -2/3 26 26/(7/3)=78/7

X1 1 1/3 0 0 1/3 8 8/(1/3)=24

0 -1 0 0 1 24
Elegir la columna Pivot con el valor mas negativo en Zy luego la fila con el menor valor en
la columna Oper.
 Método Simplex
Entra como variable básica:

Var. Var. No Básicas Var. de Holgura Sol. Oper.

Básicas
X1 X2 S1 S2 S3

X2 0 1 3 0 -2 6 3X2

S2 0 0 -7 1 4 12 f(S2)-(7/3)f(X2)

X1 1 0 -1 0 1 6 f(X1)-(1/3)f(X2)

0 0 3 0 -1 30 f(Z)+f(X2)
 Método Simplex
Entra como variable básica: Iteración 3

Var. Var. No Básicas Var. de Holgura Sol. Oper.

Básicas
X1 X2 S1 S2 S3

X2 0 1 3 0 -2 6 6/-2=-3
Sale
S2 0 0 -7 1 4 12 12/4=3

X1 1 0 -1 0 1 6 6/1=6

0 0 3 0 -1 30
Elegir la columna Pivot con el valor mas negativo en Zy luego la fila con el
menor valor en la columna Oper.
 Método Simplex
Solución óptima: X1=3; X2=12, por consiguiente Z=3(3)+2(12)=33

Var. Var. No Básicas Var. de Holgura Sol. Oper.

Básic
as X1 X2 S1 S2 S3

X2 0 1 -1/2 1/2 0 12 f(X2)+2f(S3)

S3 0 0 -7/4 1/4 1 3 (1/4)S3

X1 1 0 3/4 -1/4 0 3 f(X1)-f(S3)

Z 0 0 5/4 1/4 0 33
Unidad
Teoría de decisiones y modelos Conclusiones
de programación lineal.

Temas
• Teoría de Decisiones
1. Teoría de decisiones para seleccionar la mejor
• Árboles de decisión alternativa de decisiones en ambientes de
• Modelos de programaciónlineal incertidumbre y de riesgo en la toma de decisiones.
• Método Gráfico: Solución de problemasde 2. Programación Lineal de dos variables para optimizar
programación lineal de dosvariables.
el uso de lo recursos.
• Casos especiales en problemasde
programación 3. Solución de problemas de programación lineal de dos
• lineal variables por el método gráfico.
4. Solución de problemas de programación lineal de dos
variables o más variables por el método simplex.
 Gracias
Docente: Johnny Pacheco Contreras