MODELOS DE DECISIÓN

• NO RESTRINGIDOS

MAX: f(X) o MIN: f(X)

2
Ejemplo: MIN : 3 ⋅ x1 + + ln x 2 + 4 ⋅ x1 ⋅ x 2
x1

• RESTRINGIDOS
(PROGRAMAS MATEMÁTICOS)
PROGRAMACIÓN MATEMÁTICA

MAX: Z = f(x)
Sujeto a:
g1(x) ≤ b1
g2(x) ≤ b2
.........
gm(x) ≤ bm
 PROGRAMACIÓN LINEAL
Maximizar Σ cj·xj

sujeto a un conjunto
de restricciones Σ aij · xj ≤ bi

siendo xj ≥ 0
 FUNCIÓN OBJETIVO
Maximizar Z = Σ cj ּ◌xj

FUNCIONAL

Ejemplo: Z = 6 ּ◌ x1 + 8 ּ◌ x2 + 3 ּ◌
x3
Coeficientes del funcional
 FUNCIÓN OBJETIVO
Maximizar Z = Σ cj · xj

FUNCIONAL

Ejemplo: Z = 6 · x1 + 8 · x2 + 3 · x3

Variables de decisión
 RESTRICCIONES
Conjunto de inecuaciones o ecuaciones

Σ aij · xj ≤ bi
CONDICIONES
DE VÍNCULO Σ aij · xj ≥ bi
Σ aij · xj = bi
CONDICIONES DE VÍNCULO

Ejemplo: 12 ּ◌ x1 + 9 ּ◌ x2 + 4 ּ◌ x3 ≤
500

COEFICIENTES TECNOLÓGICOS RHS

 CONDICIONES DE LAS
VARIABLES
Xj

• NO NEGATIVIDAD

• CONTINUIDAD
 CONDICIONES DE LOS
TÉRMINOS INDEPENDIENTES
(“RHS”)

bi

• NO NEGATIVIDAD
(en su forma estándar)
 6 ּ◌ x1 + 9 ּ◌ x2 ≤ 4 ּ◌ INCORRECTO
x3

6 ּ◌ x1 + 9 ּ◌ x2 - 4 ּ◌ x3 ≤ 0
x2 x5
+ ≥ 10 INCORRECTO
4 6

0,25 ⋅ x 2 + 0,1667 ⋅ x 5 ≥ 10
∑a ij ⋅ x j ≤ bi

∑a ij ⋅ x j ≥ b i

∑a ij ⋅ x j = bi
INECUACIÓN ECUACIÓN

12 · x1 + 9 · x2 + 4 · x3 ≤ 500
VARIABLES “SLACKS”

12 · x1 + 9 · x2 + 4 · x3 ≤ 500

12 · x1 + 9 · x2 + 4 · x3 + x4 = 500

DE HOLGURA
INECUACIÓN ECUACIÓN

2 · x1 + 2 · x2 + 3 · x3 ≥ 100
VARIABLES “SLACKS”

2 · x1 + 2 · x2 + 3 · x3 ≥ 100

2 · x1 + 2 · x2 + 3 · x3 - x4 =
100

SUPERFLUA
 FORMA NATURAL

MAX: 6 · x1 + 8 · x2 + 3 · x3
Sujeto a:
12 · x1 + 9 · x2 + 4 · x3 ≤ 500
3 · x1 + 15 · x2 + 6 · x3 ≤ 700
2 · x1 + 2 · x2 + 3 · x3 ≥ 100
7 · x1 + 4 · x2 + 3 · x3 = 200

siendo: xj ≥ 0
FORMAS DE FORMULACIÓN DE
UN MODELO DE PL
• FORMA NATURAL: Restricciones de “≤”, “≥” y “=”

• FORMA CANÓNICA
– De MAX: Todas las restricciones de “≤”
– De MIN: Todas las restricciones de “≥”

• FORMA ESTÁNDAR
– Todas las restricciones de “=”
 FORMA ESTÁNDAR

MAX: 6 · x1 + 8 · x2 + 3 · x3
Sujeto a:
12 · x1 + 9 · x2 + 4 · x3 + x4 = 500
3 · x1 + 15 · x2 + 6 · x3 + x5 = 700
2 · x1 + 2 · x2 + 3 · x3 - x6 = 100
7 · x1 + 4 · x2 + 3 · x3 = 200

siendo: xj ≥ 0
FORMA CANÓNICA DE MAX

NATURAL CANÓNICA

MAX: 6 · x1 + 8 · x2 + 3 · x3 MAX: 6 · x1 + 8 · x2 + 3 · x3

12 · x1 + 9 · x2 + 4 · x3 ≤ 500 12 · x1 + 9 · x2 + 4 · x3 ≤ 500
3 · x1 + 15 · x2 + 6 · x3 ≤ 700 3 · x1 + 15 · x2 + 6 · x3 ≤ 700
2 · x1 + 2 · x2 + 3 · x3 ≥ 100 - 2 · x1 - 2 · x2 - 3 · x3 ≤ - 100
7 · x1 + 4 · x2 + 3 · x3 = 200 7 · x1 + 4 · x2 + 3 · x3 ≤ 200
- 7 · x1 - 4 · x2 - 3 · x3 ≤ - 200

xj ≥ 0 xj ≥ 0
FORMA CANÓNICA DE MIN

NATURAL CANÓNICA

MAX: 6 · x1 + 8 · x2 + 3 · x3 MIN: - 6 · x1 - 8 · x2 - 3 · x3

12 · x1 + 9 · x2 + 4 · x3 ≤ 500 - 12 · x1 - 9 · x2 - 4 · x3 ≥ - 500
3 · x1 + 15 · x2 + 6 · x3 ≤ 700 - 3 · x1 - 15 · x2 - 6 · x3 ≥ -700
2 · x1 + 2 · x2 + 3 · x3 ≥ 100 2 · x1 + 2 · x2 + 3 · x3 ≥ 100
7 · x1 + 4 · x2 + 3 · x3 = 200 7 · x1 + 4 · x2 + 3 · x3 ≥ 200
- 7 · x1 - 4 · x2 - 3 · x3 ≥ - 200

xj ≥ 0 xj ≥ 0
 FORMA CANÓNICA
MAX: c1 x1 + c2 x2 + c3 x3 + ..................... + ck xk

Sujeto a:
a11 x1 + a12 x2 + a13 x3 + ..................... + a1k xk ≤ b1
a21 x1 + a22 x2 + a23 x3 + ..................... + a2k xk ≤ b2
a31 x1 + a32 x2 + a33 x3 + ..................... + a3k xk ≤ b3
....................

am1 x1 + am2 x2 + am3 x3 + ............... + amk xk ≤ bm

siendo: xj ≥ 0
 FORMA ESTÁNDAR
MAX: c1 x 1 + c 2 x 2 + c 3 x 3 + ......... + ck xk

Sujeto a
a11 x1 + a12 x2 + a13 x3 + ......... + a1k xk + xk+1 = b1
a21 x1 + a22 x2 + a23 x3 + ......... + a2k xk + xk+2 = b2
a31 x1 + a32 x2 + a33 x3 + ......... + a3k xk + xk+3 = b3
……….........

am1 x1 + am2 x2 + am3 x3 + ......... + amk xk + xn = bm

siendo xj ≥ 0
FORMA MATRICIAL EXPANDIDA

X1 X2 X3 RHS

6 8 3 MAX

12 9 4 ≤ 500

3 15 6 ≤ 700

2 2 3 ≥ 100

7 4 3 = 200
En un taller metalúrgico se fabrican dos tipos de piezas A y B,
que deben seguir los siguientes procesos:
1. Estampado en hojas metálicas
2. Soldado
3. Pintado

La operación de estampado consiste en preparar partes idénticas

que luego serán soldadas de a pares, formando la pieza A. El
mismo proceso se realiza para la pieza B.

La utilidad unitaria es de $ 4 para la pieza A y $ 3 para la pieza B.

Se desea establecer el programa semanal de producción que
maximice la utilidad del taller con respecto a las piezas
consideradas.

Los insumos de equipos son los siguientes, para la realización de

cada una de las operaciones (expresados en segundos por
pieza):
 Tiempo disponible
Operación A B
(seg./semana)
Estampado de c/parte 3 8 48.000
Soldado 12 6 42.000
Pintado 9 9 36.000
 A

EST SOL PIN

B
MAX: Z = 4 x1 + 3 x2

Sujeto a:
6 x1 + 16 x2 ≤ 48000
12 x1 + 6 x2 ≤ 42000
9 x1 + 9 x2 ≤ 36000

siendo: x1, x2 ≥ 0 y continuas

 6 x1 + 16 x2 ≤ 48000
x2
7

1 2 3 4 5 6 7 8 9 x1
 6 x1 + 16 x2 = 48000
x2
7

1 2 3 4 5 6 7 8 9 x1
 6 x1 + 16 x2 = 48000
x2
7

1 2 3 4 5 6 7 8 x1
EST
 6 x1 + 16 x2 ≤ 48000
x2
7

1 2 3 4 5 6 7 8 x1
EST
 6 x1 + 16 x2 ≤ 48000
x2
7

1 2 3 4 5 6 7 8 x1
EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6

1 2 3 4 5 6 7 8 x1
EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 = 42000
6

1 2 3 4 5 6 7 8 x1
SOL EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 = 42000
6

1 2 3 4 5 6 7 8 x1
SOL EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6

1 2 3 4 5 6 7 8 x1
SOL EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6

1 2 3 4 5 6 7 8 x1
SOL EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6

1 2 3 4 5 6 7 8 x1
SOL EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6 9 x1 + 9 x2 = 36000
5

1 2 3 4 5 6 7 8 x1
SOL EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6 9 x1 + 9 x2 = 36000
5

1 2 3 4 5 6 7 8 x1
SOL PIN EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6 9 x1 + 9 x2 ≤ 36000
5

1 2 3 4 5 6 7 8 x1
SOL PIN EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6 9 x1 + 9 x2 ≤ 36000
5

1 2 3 4 5 6 7 8 x1
SOL PIN EST
 6 x1 + 16 x2 ≤ 48000
x2
7 12 x1 + 6 x2 ≤ 42000
6 9 x1 + 9 x2 ≤ 36000
5

1 2 3 4 5 6 7 8 x1
SOL PIN EST
x2
7

1 2 3 4 5 6 7 8 x1
SOL PIN EST
x2
Z = 4 x1 + 3 x2

1 2 3 4
x1
x2
0 = 4 x1 + 3 x2

1 2 3 4
x1
x2
0 = 4 x1 + 3 x2
x1 = - 3/4 x2

1 2 3 4
x1
x2
0 = 4 x1 + 3 x2
x1 = - 3/4 x2

Para x2 = 0 → x1 = 0
3

1 2 3 4
x1
 x2
0 = 4 x1 + 3 x2
x1 = - 3/4 x2

Para x2 = 2 → x1 = - 1,50
3

-1,5 -1 1 2 3 4
x1
 x2
0 = 4 x1 + 3 x2

3
Z=0

-1,5 -1 0 1 2 3 4
x1
 x2

Z>0
3
Z=0

-1,5 -1 0 1 2 3 4
x1
 x2

Z>0
3
Z=0

2
>Z

-1,5 -1 0 1 2 3 4
x1
 x2

3
Z=0

-1,5 -1 0 1 2 3 4
x1
 x2

Z ⇒ Máx
4

3
Z=0

-1,5 -1 0 1 2 3 4
x1
x2

Z ⇒ Máx

0 1 2 3 4
x1
x2

Z ⇒ Máx

SOLUCIÓN
2 ÓPTIMA

0 1 2 3 4
x1
x2

Z ⇒ Máx

SOLUCIÓN
2 ÓPTIMA

0 1 2 3 4
x1
x2

Z ⇒ Máx

0 1 2 3
x1
 x2

SOL
PIN

Z ⇒ Máx

EST
1

0 1 2 3 x1
 x2

x4 = 0
x5 = 0

Z ⇒ Máx

x3 = 0
1

0 1 2 3 x1
 x2

x4 = 0
x5 = 0

Z ⇒ Máx

X3 x3 = 0
1

0 1 2 3 x1
 x2

x4 = 0
x5 = 0

Z ⇒ Máx

48000 X3 x3 = 0
1

0 1 2 3 x1
MAX: Z = 4 x1 + 3 x2

6 x1 + 16 x2 ≤ 48000
12 x1 + 6 x2 ≤ 42000
9 x1 + 9 x2 ≤ 36000

x1, x2 ≥ 0
 FORMA MATRICIAL EXTENDIDA

X1 X2 SIGNO RHS

Z) 4 3 MAX

EST) 6 16 ≤ 48000

SOL) 12 6 ≤ 42000

PIN) 9 9 ≤ 36000

Var. NN NN
MAX: Z = 4 x1 + 3 x2

6 x1 + 16 x2 + x3 = 48000
12 x1 + 6 x2 + x4 = 42000
9 x1 + 9 x2 + x5 = 36000

x1, x2, x3, x4 , x5 ≥ 0

SISTEMA DE ECUACIONES LINEALES

6 x1 + 16 x2 + x3 = 48000
12 x1 + 6 x2 + x4 = 42000
9 x1 + 9 x2 + x5 = 36000

n = número de variables (5)

m = número de restricciones (3)
 x2

x4 = 0
x5 = 0 SOLUCIÓN

x3 = 0
1

0 1 2 3 x1
 x2
X1
x4 = 0
X2
x5 = 0
X = X3

X4
Z ⇒ Máx X5

2
X
x3 = 0
1

0 1 2 3 x1
 x2
X1
x4 = 0
X2
x5 = 0
X = X3

X4
Z ⇒ Máx X5

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIÓN FACTIBLE

x4 = 0
x5 = 0

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIÓN FACTIBLE:
Todos los Xj son No Negativos
x4 = 0
x5 = 0
b1

b2
X = b3

3 b4

b5
2

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIÓN NO FACTIBLE

x4 = 0
x5 = 0

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIÓN NO FACTIBLE:
Por lo menos un Xj es Negativo
x4 = 0
x5 = 0
b1

b2
X = - b3

3 b4

- b5
2

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIÓN FACTIBLE
b1
x4 = 0
b2
x5 = 0
P = 0

b4

b5

3 P

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIÓN FACTIBLE
Y BÁSICA 0
x4 = 0
0
x5 = 0
O = b3

b4

b5

x3 = 0
1

O
1 2 3 x1
 x2 SOLUCIÓN FACTIBLE
Y BÁSICA 0
x4 = 0
b2
x5 = 0
Q = 0

b4

b5
Q
3

x3 = 0
1

1 2 3 x1
 x2 SOLUCIÓN NO FACTIBLE
Y BÁSICA 0
x4 = 0
b2
x5 = 0
R = - b3
R b4

x3 = 0
1

1 2 3 x1
 x2 SOLUCIONES BÁSICAS

x4 = 0
x5 = 0

x3 = 0
1

0 1 2 3 x1
 x2 SOLUCIONES BÁSICAS FACTIBLES

x4 = 0
x5 = 0

x3 = 0
1

0 1 2 3 x1
 x2

x4 = 0
x5 = 0 SOLUCIÓN ÓPTIMA

x3 = 0
1

0 1 2 3 x1
 x2

x4 = 0 6 x1 + 16 x2 + x3 = 48000
x5 = 0
12 x1 + 6 x2 + x4 = 42000
9 x1 + 9 x2 + x5 = 36000

Z = 4 x1 + 3 x2

x3 = 0
1

0 1 2 3 x1
 6 x1 + 16 x2 + x3 = 48000
12 x1 + 6 x2 + x4 = 42000
9 x1 + 9 x2 + x5 = 36000

x1
x2

X= x3 Z = 4 x1 + 3 x2

x4

x5
 x3 = 48000
x4 = 42000
x5 = 36000

0
0

X= 48000 Z=0

42000

36000
 x3 = 48000
x4 = 42000
x5 = 36000

x2 x4=0

0 x5=0

X= 48000 Z =0
x3=0
42000

36000
x1
 6 x1 + 16 x2 + x3 = 48000
12 x1 + 6 x2 + x4 = 42000
9 x1 + 9 x2 + x5 = 36000

x1
x2

X= x3 Z = 4 x1 + 3 x2

x4

x5
 16 x2 = 48000
6 x2 + x4 = 42000
9 x2 + x5 = 36000

0
3000

X= 0 Z = 9000

24000

9000
 16 x2 = 48000
6 x2 + x4 = 42000
9 x2 + x5 = 36000

x2 x4=0

0 x5=0

3000

X= 0 Z = 9000
x3=0
24000

9000
x1
 6 x1 + 16 x2 + x3 = 48000
12 x1 + 6 x2 + x4 = 42000
9 x1 + 9 x2 + x5 = 36000

x1
x2

X= x3 Z = 4 x1 + 3 x2

x4

x5
 6 x1 + x3 = 48000
12 x1 + x4 = 42000
9 x1 = 36000

4000
0

X= 24000 NO FACTIBLE

-6000

0
 6 x1 + x3 = 48000
12 x1 + x4 = 42000
9 x1 = 36000

x2 x4=0

4000 x5=0

X= 24000 NO FACTIBLE
x3=0
-6000

0
x1
CONJUNTO CONVEXO
CONJUNTO CONVEXO
CONJUNTO NO CONVEXO
CONJUNTO NO CONVEXO