COSTOS II

PROGRAMACIÓN LINEAL
DEFINICIÓN
“Un modelo de Programación Lineal
(PL) considera que las variables de decisión
tienen un comportamiento lineal, tanto en la
función objetivo como restricciones del problema.

En este sentido, la Programación Lineal es

una de las herramientas más utilizadas en la
Investigación Operativa debido a que por su
naturaleza se facilitan los cálculos y en general
permite una buena aproximación de la realidad.”

“La programación lineal es el campo de

la optimización matemática dedicado a
maximizar o minimizar (optimizar) una función
lineal, denominada función objetivo, de tal forma
que las variables de dicha función estén sujetas a
una serie de restricciones expresadas mediante
un sistema de ecuaciones
DEFINICIÓN

“Se conoce como programación

lineal a la técnica de la matemática que
permite la optimización de una función
objetivo a través de la aplicación de
diversas restricciones a sus variables.

Se trata de un modelo
compuesto, por lo tanto, por una
función objetivo y sus restricciones,
constituyéndose todos estos
componentes como funciones lineales
en las variables en cuestión.”
RESTRICCIONES
- Disponer de recursos ilimitados
implicaría una mezcla de productos
equivalente a una cantidad infinita de
productos.
- Recursos limitados implica
limitaciones a la cantidad a producir.
- Restricciones externas: son
limitaciones dadas por factores
externos a la organización (ejemplo:
demanda del mercado).
- Restricciones internas: son
limitaciones que se dan adentro de
las organizaciones (ejemplo: horas
máquina, horas hombre)
 MEZCLA ÓPTIMA

- La mejor decisión estaría dada por la

elección de la mezcla óptima de
producción dadas las restricciones de la
empresa.

- ¿Productos con mayor margen de

contribución mejor decisión de
producción? No necesariamente
HISTORIA
A lo largo de la historia han existido
diversos acontecimientos importantes relativos
a la programación lineal, quizás el más
destacable y trascendente:
Durante la Segunda Guerra Mundial se
mantuvo en secreto y fue utilizada como
mecanismo para poder gestionar y planificar
todos los gastos. De esta manera se pretendía,
gestionar mejor los recursos propios y reducir lo
máximo posible lo que eran los costos del
ejército.
Tres se consideran sus padres o
creadores: el húngaro-estadounidense John
von Neumann, el profesor norteamericano
George Dantzig y el matemático de origen
ruso Leonid Kantoróvich, que recibió el
Premio Nobel de Economía en 1975.
 HISTORIA
Los fundadores de la técnica
son George Dantzig, quien publicó
el algoritmo simplex, en 1947, John von
Neumann, que desarrolló la teoría de la
dualidad en el mismo año, y Leonid
Kantoróvich, un matemático de origen ruso,
que utiliza técnicas similares en la economía
antes de Dantzig y ganó el premio Nobel en
economía en 1975.
En 1979, otro matemático ruso, Leonid
Khachiyan, diseñó el llamado Algoritmo del
elipsoide, a través del cual demostró que el
problema de la programación lineal es resoluble
de manera eficiente, es decir, en tiempo
polinomial.
Más tarde, en 1984, Narendra
Karmarkar introduce un nuevo método del
MODELOS MATEMÁTICOS
Los Modelos Matemáticos se dividen
básicamente en Modelos Determistas (MD) o
Estocásticos (ME).
En el primer caso (MD) se considera que
los parámetros asociados al modelo son
conocidos con certeza absoluta, a diferencia de
los Modelos Estocásticos, donde la totalidad o
un subconjunto de los parámetros tienen una
distribución de probabilidad asociada.

Los modelos de programación lineal

contemplan que las variables de decisión (es
decir, la función objetivo y las restricciones)
mantienen un comportamiento de tipo lineal.
Esto hace que, a través de su método, se
puedan simplificar los cálculos y obtener un
resultado próximo a la realidad.
MODELOS MATEMÁTICOS
RESOLUCIÓN - MÉTODOS
La programación lineal es una técnica
matemática relativamente reciente (siglo XX), que
consiste en una serie de métodos y procedimientos
que permiten resolver problemas de
optimización en el ámbito, sobre todo, de las
Ciencias Sociales.
Nos centraremos en aquellos problemas
simples de programación lineal, los que tienen
solamente 2 variables
(bidimensionales), que se resuelven a través de la
REPRESENTACIÓN GRÁFICA.
Para sistemas de más variables, el
procedimiento no es tan sencillo y se resuelven por
el llamado MÉTODO SIMPLEX (ideado por G.
Danzig).
Como dijimos anteriormente, recientemente
(1984) el matemático indio establecido en Estados
Unidos, Narenda Karmarkar, ha encontrado un
algoritmo, llamado algoritmo de Karmarkar, que
MÉTODO SIMPLEX
El Método Simplex publicado por George
Dantzig en 1947 consiste en un algoritmo
iterativo que secuencialmente, a través de
iteraciones, se va aproximando al óptimo del
problema de Programación Lineal (en caso de
existir).La primera implementación
computacional del Método Simplex es en el año
1952 para un problema de 71 variables y 48
ecuaciones. Su resolución tardó 18 horas.
Luego, en 1956, un código llamado RSLP1,
implementado en un IBM con 4Kb en RAM,
admite EllaM.S.
resolución
hace uso de
de lamodelos con
propiedad 255
de que
restricciones.
la solución óptima de un problema de
Programación Lineal se encuentra en un vértice
o frontera del dominio de puntos factibles (esto
último en casos muy especiales), por lo cual, la
búsqueda secuencial del algoritmo se basa en
la evaluación progresiva de estos vértices hasta
RESOLUCIÓN GRÁFICA
El Método Gráfico (resolución gráfica)
constituye una excelente alternativa de
representación y resolución de modelos
de Programación Lineal que tienen 2 variables
de decisión.
El análisis gráfico es una alternativa
eficiente para enfrentar la resolución de
modelos de Programación Lineal de 2 variables,
donde el dominio de puntos factibles (en caso
de existir) se encontrará en el primer
cuadrante, como producto de la intersección de
las distintas restricciones del problema lineal.

Los puntos del plano que cumplen el

sistema de desigualdades forman un recinto
convexo acotado (poligonal) o no acotado,
llamado región factible del problema.
RESOLUCIÓN GRÁFICA
En un problema de programación lineal
de dos variables “x” e “y”, se trata de
optimizar (hacer máxima o mínima) una
función (llamada FUNCIÓN OBJETIVO) de la
forma:

F(x, y) = A . x +
B.y

Sujeta a una serie de RESTRICCIONES

dadas mediante un sistema de inecuaciones
lineales del tipo:

a1x + b1y
≤ c1
a2x + b2y
≤ c2
RESOLUCIÓN GRÁFICA
Todos los puntos de la región factible
cumplen el sistema de desigualdades
(inecuaciones) y se denominan soluciones
factibles.

Se trata de buscar, entre todos esos

puntos, aquel o aquellos que hagan el valor de
F(x,y) (función objetivo) máximo o mínimo,
según sea el problema.

De todas esas soluciones factibles,

aquellas que hacen óptima (máxima o mínima)
la función objetivo se llaman soluciones
óptimas.
RESOLUCIÓN GRÁFICA
Resumiendo:

-Solución factible: Bajo esta

denominación se encuentra un área, que puede
estar acotada o no y que está determinada por
el conjunto de las restricciones de todos los
semiplanos. También es conocida por el nombre
de región de validez.

-Solución óptima: Se llama así al

conjunto de todos los vértices del recinto. Hay
que subrayar, además, que esa puede ser
mínima o máxima según cada caso.

-Valor del programa lineal: Este viene a

ser el valor que la mencionada función objetivo
toma en lo que es el vértice de la solución
óptima
RESOLUCIÓN GRÁFICA
Inecuaciones lineales con 2 variables:
Una inecuación lineal con 2 variables es una
expresión de la forma: ax + by ≤ c
- donde el símbolo ≤ puede ser también ≥ ,
< o bien >,
- donde a, b y c son números reales y,
- “x” e “y” son las incógnitas.
Para resolver estas inecuaciones hay que
representar gráficamente en el plano la recta dada
por la correspondiente ecuación lineal y marcar
una de las dos regiones en que dicha recta divide al
plano.
Ejemplo: Si queremos resolver la inecuación: 2x +
3y ≥ −3,
representamos en primer lugar la recta 2x + 3y =
−3:
La recta divide al plano en dos regiones, una
de las cuales es la solución de la inecuación.
RESOLUCIÓN GRÁFICA

y≥
2x −3−

Observando el dibujo
vemos que la recta divide 2x
al eje de ordenadas (y) +
en dos partes. 3y
La solución de la =
inecuación será aquella −3
parte en la que “y” sea
mayor que la recta (la
parte superior).
RESOLUCIÓN GRÁFICA
Rectas horizontales y verticales:
En ocasiones, en estos sistemas, aparecen
inecuaciones del tipo x ≥ k o bien y ≥ k, donde falta
alguna de las dos incógnitas.
Estas inecuaciones en realidad corresponden
a rectas horizontales y verticales.

Por ejemplo,
la inecuación x ≤ 2
no es más que el
conjunto de puntos a la
izquierda de la recta
vertical
que pasa por el punto x
=2
RESOLUCIÓN GRÁFICA
Rectas horizontales y verticales:

Lo mismo ocurre con y ≤ 1, que ser´a en este

caso la parte inferior a la recta horizontal y = 1, es
decir:
RESOLUCIÓN GRÁFICA
SISTEMAS de inecuaciones lineales con dos
variables:

Un sistema de inecuaciones lineales es

un conjunto de inecuaciones del tipo anterior, y
resolverlo consistirá en resolver gráficamente
cada inecuación (como en el caso anterior),
representar la solución en un mismo gráfico y la
solución total será la parte común a todas las
soluciones (área, región o solución factible).

Ejercicio: Graficar el sistema de inecuaciones:

2x + 3y ≥ −3
2x − y − 9 ≤0
2x − 5y − 5 ≥0
 RESOLUCIÓN GRÁFICA
Si representamos las
rectas: s
2x + 3y = −3
(recta r)
2x − y − 9 = 0
(recta s)
2x − 5y − 5 = 0
t
(recta t)

El triángulo marcado es la solución factible del

sistema.
RESOLUCIÓN GRÁFICA
Además, para los problemas de
programación lineal es necesario el cálculo de
los vértices de la región factible de solución.
Es sencillo su cálculo, se reduce a
resolver sistemas de ecuaciones lineales con
dos incógnitas, que provienen de igualar las
ecuaciones de las rectas correspondientes.
Por ejemplo, en este caso, si queremos
el punto intersección de las rectas “r” y “s”
tendremos que resolver el sistema formado por:
r: 2x + 3y = −3 −2x − 3y
=3
s: 2x − y − 9 = 0 2x − y −
9= 0
Sumando
−4y = 12 ⇒ y = −3
Y sustituyendo queda 2x + 3(−3) = −3,
RESOLUCIÓN GRÁFICA
Ejercicio: Calcular los otros dos vértices y
graficar
2x − y − 9 = 0
2x – 5y – 5 = 0
Restando 0 + 4y - 4 = 0 ⇒ y = 1
Y sustituyendo queda 2x − 5(1) = 5,
es decir 2x - 5 = 5, ⇒ x = 5

“s” y “t” se cortan (intersección) en el

punto (5;1)
2x + 3y = −3 −2x − 3y
=3
2x – 5y – 5 = 0 ⇒ 2x − 5y −
5=0
Sumando −8y
= 8 ⇒ y = −1
Y sustituyendo queda 2x + 3(−1) = −3,
es decir 2x - 3 = −3 ⇒ x = 0
RESOLUCIÓN GRÁFICA
s

(5 ;
1) t

(0 ; -
1)

(3 ; -
3)
r

El triángulo marcado es la solución factible del

sistema.
RESOLUCIÓN GRÁFICA
Los puntos del plano que cumplen el
sistema de desigualdades (inecuaciones)
forman un recinto convexo acotado (poligonal).
Todos los puntos de dicha región
cumplen el sistema de desigualdades. Se trata
de buscar, entre todos esos puntos, aquel o
aquellos que hagan el valor de F(x,y) máximo o
mínimo, según sea el problema.
Los puntos de la región factible se
denominan soluciones factibles.
De todas esas soluciones factibles,
aquellas que hacen óptima (máxima o mínima)
la función objetivo se llaman soluciones
óptimas.
En general, un problema de
programación lineal puede tener una, infinitas o
RESOLUCIÓN GRÁFICA
Si hay una única solución óptima, ésta
se encuentra en un vértice de la región factible,
y si hay infinitas soluciones óptimas, se
encontrarán en un lado de la región factible.
También es posible que no haya solución
óptima, cuando la región es no acotada, la
función objetivo puede crecer o decrecer
indefinidamente.

Para resolver el problema, primero hay

que dibujar la región factible, resolviendo el
sistema de inecuaciones lineales
correspondiente y luego calcular los vértices de
dicha región, como lo hicimos en las
diapositivas anteriores.

Luego existen de dos formas de

abordarlo:
RESOLUCIÓN GRÁFICA
Forma Geométrica:
Ejercicio: Maximizar la función F(x, y) = 2000x
+ 5000y
Sujeta a las siguientes restricciones:
2x
+ 3y ≥ −3
2x −
y − 9 En
≤ 0este caso se representa el vector
director de la recta que viene dada por la
2x −
ecuación
5y − 5 ≥ 0de la función objetivo que hay que
maximizar.

El vector director de la recta A · x + B · y

viene dado por v = (−B, A).
*Además, como lo único que nos importa es la
dirección del vector y no su módulo (longitud),
podemos dividir a las coordenadas del vector si
los números son muy grandes, puesto que
RESOLUCIÓN GRÁFICA
Forma Geométrica:
Los vértices eran los puntos (0;-1), (5;1) y (3;-
3).
Como la función es F(x, y) = 2000x + 5000y, el
vector director es v = (−5000, 2000), que tiene
s
la misma dirección que el v = (−5, 2):

(5 ;
t
1)

(0 ; -
1)
(3 ; -
3)
r
 RESOLUCIÓN GRÁFICA
Forma Geométrica:
Se trata ahora de trazar paralelas al
vector que pasen por los vértices:

Se observa
que de las tres
(5; t paralelas trazadas, la
que corta al eje “y” en
1)
un punto mayor es la
(0;- que pasa por el punto
1) (5;1), por tanto será la
solución óptima al
(3;- problema de máximos
3) planteado.
r
Para saber cuál es este valor máximo sustituimos en
la función: F(5;1) = 2000 · 5 + 5000 · 1 = 10000 +
RESOLUCIÓN GRÁFICA
Forma Algebraica:
Maximizar la función F(x, y) = 2000x + 5000y
Sujeta a las restricciones:
2x + 3y ≥ −3
2x − y − 9 ≤ 0
2x − 5y − 5 ≥ 0

Con la misma región factible que en el caso

anterior.
Los vértices eran los puntos (0 ; -1), (5 ; 1) y (3 ; -
3).
De esta forma sustituyendo:
F(5 ; 1) = 2000 · 5 + 5000 · 1 = 10000 + 5000
= 15000
F(0; −1) = 2000 · 0 + 5000 · (−1) = 0 − 5000
= −5000
 RESOLUCIÓN GRÁFICA – Casos
Extremos
Caso 1:
Maximizar g(x, y) = 3x + 4y
Sujeta a las restricciones:

x + y ≥ 14

2x + 3y ≥ 36
Si representamos la región factible:
4x + y ≥ 16

x − 3y ≥ 0 Los vértices serán:

A = (2/3 , 40/3)
B = (6, 8)
C = (12, 4)

Observemos que la región

factible es NO acotada
superiormente.
RESOLUCIÓN GRÁFICA – Casos
Extremos
Si aplicamos el método geométrico, debería
trazar paralelas al vector director por los vértices,
pero como la región es no acotada, dichas rectas son
cada vez mayores al trazarlas sobre los puntos de la
recta t, que son soluciones factibles. Por tanto el
problema no tiene solución.
RESOLUCIÓN GRÁFICA – Casos
Extremos
Resuelva el mismo caso pero para Minimización:

Minimizar g(x, y) = 3x + 4y
Sujeta a las restricciones:

x + y ≥ 14

2x + 3y ≥ 36

4x + y ≥ 16
En general, un problema de
x − 3y ≥
máximos no0 tiene solución si la
región factible no está acotada
superiormente,
y un problema de mínimos no tiene
solución si la región no está
acotada inferiormente.
RESOLUCIÓN GRÁFICA – Casos
Extremos
Caso 2:
Minimizar g(x, y) = 3x + 3y
Sujeta a las restricciones: x+y≥5

y≤x+3

3y − x ≥ −1
Si utilizamos el método algebraico:
y + 2x ≤ 16
A : g(1, 4) = 3 + 12 = 15
B : g(2, 5)
4y =
− 6x +
≤ 15
22 = 21
C : g(6, 4) = 18 + 12 = 30
D : g(7, 2) = 21 + 6 = 27
E : g(4, 1) = 12 + 3 = 15
Observamos que el valor mínimo se toma en A y
en E, y por tanto en todos los puntos
comprendidos entre ellos, es decir, hay infinitas
soluciones.
RESOLUCIÓN GRÁFICA – Casos
Extremos
Si utilizamos el método gráfico, obtenemos:

Como buscamos el valor

mínimo, todos los
puntos comprendidos
entre A y E sirven, es
decir, hay infinitas
soluciones.
CASOS DE APLICACIÓN PRÁCTICA
El verdadero valor de las técnicas de la
programación lineal consiste en poder aplicarlas a
problemas reales.
Para resolver estos problemas se deben
seguir una serie de pasos.
Veamos un ejemplo concreto para ver como
se aplicaría:
Una fábrica de muebles fabrica dos tipos de
sillones, S1 y S2. La fábrica cuenta con dos secciones,
carpintería y tapicería.
Hacer un sillón de tipo S1 requiere 1 hora de
carpintería y 2 de tapicería, mientras que uno de tipo
S2 requiere 3 horas de carpintería y 1 de tapicería.
El personal de tapicería trabaja un total de 80
horas, y el de carpintería 90.
Las ganancias por las ventas de S1 y S2 son,
respectivamente $60 y $30 por unidad.
Calcular cuántos sillones de cada tipo hay que
hacer para MAXIMIZAR las ganancias.
CASOS DE APLICACIÓN PRÁCTICA
PASO 1:
Leer el enunciado, determinar
la función objetivo y definir las variables.

En este caso, queremos hacer máximo el

beneficio, es decir, queremos maximizar una
función.

Como queremos determinar las

cantidades de sillones S1 y S2 respectivamente,
llamemos:

x = nº de
unidades de S1
y = nº de
unidades de S2

La función objetivo a maximizar será:

CASOS DE APLICACIÓN PRÁCTICA
PASO 2:
Reordenar los datos del
problema y escribir las inecuaciones
(restricciones) correspondientes. En este
paso es conveniente el uso de tablas:

De aquí se deduce que: y

además:
x + 3y ≤ 90
x ≥ 0 el nº de unidades
2x + y ≤ 80
no puede ser
y≥0 negativo.
CASOS DE APLICACIÓN PRÁCTICA
PASO 3:
Representar gráficamente la
región factible, calcular sus vértices y el
vector si usamos el método
geométrico. Siendo los vértices: Gráficamente se
A=( 0 ; 0) observa que la
B=(0;30) solución no es
C=(30;20)
única, sino que se
B D=(40;0)
encuentran
infinitas
C soluciones
en el lado CD,
sobre la recta
2x + y = 80
A D
desde que x vale
El vector será (−30 ; 30 hasta que vale
60) equivalente a 40,
CASOS DE APLICACIÓN PRÁCTICA
PASO 4:
Sustituir las coordenadas en
la función objetivo y dar la solución
correcta.

B(x, y) = 60 · x + 30 · y

B( 0 ; 0) = 0

B( 0 ; 30) = 900

B(30 ; 20) = 2400

B(40 ; 0) = 2400

Con lo cuál hay infinitas

soluciones y el beneficio que se
obtiene es $ 2.400
CASOS DE APLICACIÓN PRÁCTICA
PASO 5:
Analizar la solución obtenida
en el contexto del problema: ¿tiene
sentido?
Debemos interpretar que en el contexto del
problema no todas las soluciones son válidas, sino
que sólo sirven soluciones enteras, es decir, no se
pueden fabricar, por ejemplo 3,8 sillones del tipo S1.
Las soluciones con sentido vendrían dadas por
números enteros:

Encontramos sólo 11 soluciones que son las de la

tabla

En cualquiera de estas soluciones el beneficio es de

$2.400, que es el MÁXIMO bajo las condiciones del
problema.
RESOLVAMOS JUNTOS EL SIGUIENTE
CASO
Una empresa tiene 2 plantas de producción
(P1 y P2) de cierto artículo que vende en 3 ciudades
(C1, C2 y C3). En P1 produce 5.000 unidades, y en P2
7.000 unidades.
De estas 12.000 unidades las vende así:
3.500 a C1, 4.000 a C2 y 4.500 a C3.
Los costos de transporte, en $ por unidad de
producto, desde las plantas de producción a las
ciudades son:

Determina el nº de artículos que debe enviar

la empresa desde cada planta a cada ciudad para que
los costos de transporte sean MÍNIMOS.
RESOLVAMOS JUNTOS EL SIGUIENTE
CASO
Para problemas de este tipo necesitamos una
nueva variable. Sea:
x = unidades de P1 a C1
y = unidades de P1 a C2
z = unidades de P1 a C3

Tiene que verificarse entonces que x + y + z = 5000.

Si desde P1 a C1 se envían x unidades, como en C1

necesitan 3500, desde P2 se mandarán a C1 3500 −
x.
Razonando del mismo modo con y y z, se obtiene la
tabla:

Hemos sustituido z por 5000 − y − x, porque

x + y + z = 5000 y así transformamos las 3
incógnitas en sólo 2.
RESOLVAMOS JUNTOS EL SIGUIENTE
CASO
Como se trata de minimizar costes, la función
objetivo es:
C(x, y) = 3 · x + 2,5 · y + 3,5 · (5000 − x − y)
+ 2,25 ·(3500 − x)+3,75 ·(4000 − y)+4
·(−500 + x + y)
C(x, y)=1,25 · x − 0,75 · y + 22625
Para obtener las restricciones imponemos
que cada cantidad ha de ser mayor o igual que cero,
es decir:
x≥0
4000 − y ≥ 0
3500 − x ≥ 0 5000
−x−y≥0
y≥0
−500 + x + y ≥ 0
Por tanto el sistema de inecuaciones es:
x≥0
x ≤ 3500
y≥0
RESOLVAMOS JUNTOS EL SIGUIENTE
CASO

B C A=(0,500)

B=(0,4000)

C=(1000,400
0)
D
D=(3500,150
0)
A
E E= (3500,0)
F
F=(500,0)
RESOLVAMOS JUNTOS EL SIGUIENTE
CASO
Sustituyendo:

C(0, 500) = 22250

C(0, 4000) = 19625
C(1000, 4000) = 20875
C(3500, 1500) = 25875
C(3500, 0) = 27000
C(500, 0) = 23250

El mínimo se da en B, cuando x = 0 e y = 4000.

Es decir, las unidades a distribuir son: