Programación lineal

Investigación
de Operaciones I

Programacion Lineal
Roberto Aguilar Barrón

Definición
Metodo de optimización (maximización o minimización) de una función lineal
que satisface un conjunto de igualdades y/o desigualdades denominadas
restricciones.
Concebido por George B. Dantzing en 1947.

Page  2

Modelo general
Coeficientes
objetivo
Optimizar
Sujeta a

c1 x1  c2 x2  ... cn xn

Coeficientes
de recursos

a11 x1  a12 x2  ...  a1n xn  b1
a21 x1  a22 x2  ...  a2 n xn  b2
am1 x1  am 2 x2  ...  amn xn  bm

Coeficientes
tecnológicos

x1 , x2 ,..., xn  0
n

Optimizar

cjxj

Variables

1

n

Sujeta a:

a x
ij

 bi

i  1, , m

j

xj  0
Page  3

j

j  1,2,, n

Modelo general

x1 
x 
 2
.x 
.
.
 
xn 
 

b1 
b 
 2
.
b 
.
.
 
bm
 

a11 a12 . . . a1n 
a a . . . a 
2n 
 21 22
. .
.
A 

. .
.

. .
.


am1 am2 . . . amn



1

Optimizar
Sujeta a

Page  4

⋯

2

cx

 

Ax  b
x0

Suposiciones
Proporcionalidad. La contribución individual que una variable xj aporta a lafunción objetivo es cjxj y al consumo del recurso de la i-esima restricción es aijxj.
Aditividad. La contribución total tanto a la función objetivo como
restricciones es igual a la suma de las contribuciones individuales.

a las

Divisibilidad. Las variables de decisión pueden ser divididas a cualquier nivel
fraccionario, de tal manera que puedan tomar valores no enteros.

Page  5Limitaciones
Modelo deterministico. Los valores de cj, aij y bi son conocidos y constantes.
Modelo estático. La variable tiempo no se involucra formalmente.
Modelo que no suboptimiza. El modelo
declara que esta no existe.

Page  6

encuentra la solución óptima o

Transformaciones
El objetivo puede cambiarse de maximización a minimización y viceversa.



•
•

2

3

6
2

3

6El sentido de una desigualdad puede invertirse.
• 5
•
5

6

2
6

6
2

6

Una ecuación puede transformarse a desigualdades
• 5
• 5

Page  7

7
7

6
6

4
4 y 5

7

6

4

Transformaciones
Una desigualdad ≤ del tipo valor absoluto puede sustituirse por desigualdades
normales.
• 3
• 3

2
2

10
10 y 3

2

10

Una desigualdad del tipo ≤ puedeconvertirse a ecuación.
• 7
• 7

8
8

9
9

6
6

Una desigualdad del tipo ≥ puede convertirse a ecuación.
•
•

9
9

Page  8

4
4

3
3

12
12

Transformaciones
Una variable irrestricta en signo puede redefinirse en función de variables no
negativas.
•

Page  9

Ejemplo 1
Un ganadero decide elaborar una mezcla para alimento de animales a base de
alfalfa, sorgo,avena, maíz, soya y harinolina. De cada 100 kilogramos de
mezcla, desea que al menos 30 de ellos sean de proteínas, no mas de 40 sean
de calcio y como máximo 35 kilogramos de fosforo. En la tabla se muestra la
información nutrimental de los ingredientes. Además no se pueden usar mas de
10 kilogramos de harinolina, ni mas de 12 kilogramos de soya por cada 100
kilos de mezcla. El precio de losingredientes son 7, 9, 8, 20, 5 y 15 pesos por
cada kilogramo respectivamente.
Determina la mezcla optima para elaborar 100 Kgs de producto.
Ingrediente

Calcio (%)

Fosforo(%)

Alfalfa

25

50

25

Sorgo

40

20

40

Avena

10

30

60

Maíz

65

15

20

Soya

40

20

40

Harinolina
Page  10

Proteína
(%)

30

20

50

Ejemplo 1Variables de decisión: Xj: Cantidad (Kg) de ingrediente j en la mezcla
de 100 Kgs.
Función objetivo: X0: Minimizar el costo total de la mezcla.
Restricciones: Restricciones de calidad, entrada y capacidad.
Condiciones técnicas: Estrictamente 0 ó positivas.

Page  11

Ejemplo 1

Minimizar x0 =7x1 +9x2 +8x3 +20x4 +5x5 +15x6
x1 +x2 +x3 +x4 +x5 +x6

100 

0.25x1 +0.40x2 +0.10x3...