ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
Tema 2. Programación Lineal
Introducción
El origen de la Programación Lineal (PL) data desde los siglos XVII y XVIII, con Newton,
Leibnitz, Bernouilli, Lagrange y Monge se ocuparon de la obtención de los máximos y mínimos
condicionados de determinados de determinadas funciones, por otra parte el matemático Fourier la
forma precisa de los métodos llamados PL y su potencialidad y en Rusia en el año 1947 los
científicos Koopmans y Kantarovitch desarrollaron métodos matemáticos de organización y
planificación de la producción, por los la misma época G. Stigler en Estados Unidos plantea otro
problema particular conocido como el régimen alimenticio óptimo, en este país es donde finalmente
nace la “Programación Lineal” en 1947 por el científico Dantzig al formular en términos
matemáticos el enunciado estándar muy precisos todo problema de programación lineal (PL),
Dantzig y un grupo de científicos del departamento de la Fuerza Armada forman el SCOOP
(Scientific Computation of Optimum Programs), que son que finalmente desarrollan y aplican con
gran éxito la PL.
El desarrollo de la programación lineal ha sido clasificado como uno de los avances
científicos más importantes del siglo XX, y estamos de acuerdo con esta aseveración, su efecto
desde 1950 ha dado soluciones extraordinarias a diversas organizaciones, en la actualidad es una
herramienta de uso normal que ha ahorrado miles o millones de dólares a muchas compañías o
negocios, incluso empresas medinas, en los distintos países industrializados del mundo; su
aplicación a otros sectores de la sociedad se ha ampliado con rapidez. Una proporción muy grande
de los programas científicos en computadoras está dedicada al uso de la programación lineal. Se
ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
han escrito docenas de libros de texto sobre esta materia y se cuentan por cientos los artículos
publicados que describen aplicaciones importantes.
La programación lineal utiliza un modelo matemático para describir el problema. El
adjetivo lineal significa que todas las funciones matemáticas del modelo deben ser funciones
lineales, en este caso, la palabra programación no se refiere aquí a términos computacionales; en
esencia es sinónimo de planeación, por lo tanto, la programación lineal involucra la planeación de
actividades para obtener un resultado óptimo (Hillier y Lieberman, 2010).
La Programación lineal corresponde a un algoritmo a través del cual se resuelven
situaciones reales en las que se pretende identificar y resolver diferentes problematizaciones en
cuanto a la productividad, a los recursos aumentando y a sus beneficios, el objetivo es optimizar
(maximizar o minimizar) funciones lineales en variables reales con restricciones lineales. El cual
da soluciones utilizando una gran diversidad de modelos lineales. Se le llama programación lineal
al conjunto de técnicas matemáticas que pretenden resolver la siguiente situación:
Optimizar: (maximizar o minimizar) una función objetivo, función lineal de varias
variables, sujetas a (S.A):
Una serie de restricciones, expresadas por inecuaciones lineales
La Función Objetivo (Fo), es la que es necesario optimizar
Fo = X1 + X2, donde X1 y X2 son las variables de decisión.
ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
2.2 Solución gráfica de la programación lineal
Una de la gran diversidad de solución de Programación Lineal es el “método grafico” o “solución
gráfica”, el cual puede ser utilizado solo cuando el problema afecta a dos variables decisión
donde la solución óptima de un problema de programación lineal se puede encontrar
gráficamente. Para el primer paso es establecer las dos líneas que representan las cantidades de
X1 y X2. El siguiente paso es encontrar todas las soluciones del problema y para ello se puede
utilizar la representación gráfica impuesta por cada una de las restricciones es decir determinar su
zona del espacio X1 y X2 sería aceptada por cada restricción (Lachtermacher, 2004). Según
Agosti el método Grafico es un método limitado para resolver los problemas con solo dos
variables y este método, que restringir la definición de cada una en la zona de plano cartesiano
que contiene infinitos puntos al mismo tiempo, está contenida en este ámbito y cumplir la línea de
meta. Incluso se afirma que el método garantiza que los puntos de intersección de las líneas
límites de la zona de interés son los posibles puntos que satisfagan a la tarea “objetivo” (2003).
Algunos autores mencionan que el método grafico es un procedimiento de solución de
problemas de programación lineal muy limitado en cuanto al número de variables (2 si es un gráfico
2D y 3 si es 3D), esto consiste en representar cada una de las restricciones y encontrar en la medida
de lo posible el polígono (poliedro) factible comúnmente llamado el conjunto de solución o región
factible, en el cual por razones trigonométricas en una de sus vértices se encuentra la mejor respuesta
(solución óptima).
Método de las rectas de nivel
Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.
Si la función objetivo es f (X1,X2) = aX1 + bX2, la ecuación de las rectas de nivel es de la forma:
aX1 + bX2 = 0 aX1 + bX2= k
Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para
f(X1,X2).
En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta a X 1 +
bX2= k son los que determinan su pendiente.
ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
El método grafico se utiliza para la solución de problemas de PL, representando geométricamente a las
restricciones, condiciones técnicas y el objetivo.
El modelo se puede resolver en forma geométrica si solo se tiene 2 variables. Para modelos con 3 o
más variables el método grafico es impráctico o imposible. Cuando los ejes son relacionados con las
variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las
restricciones tecnológicas se denomina método grafico en recursos, ya que la PL es una técnica
mediante la cual se toman decisiones reduciendo el problema bajo estudio a un modelo matemático
general.
Maximizar y Minimizar
Podemos maximizar y minimizar por el método grafico nuestros problemas y nos lleva a un resultado
exacto al igual que el simplex solo que este es aún más fácil, pues como al principio mandas en la
ecuación a X1 cero y después X2 así te da el primer punto a graficar y así con las demás ecuaciones, el
punto donde se intersectan dos o más líneas de las ecuaciones es el punto solución, este se sustituye
debidamente cada número en su variable en la función objetivo para dar la comprobación. Así el
espacio debajo del punto de intersección es para maximización y se presenta el resultado por ejemplo
Z=10, para la minimización es lo mismo solo se toma el punto solución como lo más y el resultado de
igual solo que se representaría –Z=10 y la zona factible cabe en la parte mayor de la gráfica.
Pasos para solución gráfica de la programación lineal
Es recomendable indicar paso a paso la resolución de problemas utilizando cualquier modelo de PL,
aunque no es difícil la solución, cada autor da explicaciones con términos técnicos en ingeniería
ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
industrial, el objetivo principal de este trabajo, es que, sea amigable para el área administrativa la
solución. El método gráfico se requiere obtener los valores de Z, X1 y X2.
Paso 1. Cuadro de Datos: El cuadro de datos se utiliza para vaciar los datos que nos indica el problema
a resolver, sino se resuelve adecuadamente todo el desarrollo estará erróneo, en la primera columna
van los materiales con los que se producen los productos y en la última fila de la 1er columna, por lo
general, se coloca la parte monetaria ($), ya sea venta, compra, utilidad, etc... Y en la última columna
se colocan los productos almacenados o producidos (cantidades producidas).
Paso 2. Desterminar:
- Función Objetivo (Fo): Z = aX1+bX2
- Variables de decisión: de X1 y X2
- Restricciones a las que están sujetas (S.a.), dos restricciones (dos ecuaciones).
Paso 3. Convertir restricciones en igualdades de cada ecuación (restricción) se sacan dos
coordenadas igualando a cero X1 y después se iguala a cero X2, con lo que se obtienen cuatro
coordenadas para graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfaga
todas las restricciones en forma simultánea.
Paso 4. Gráfica. Se grafican las coordenadas de las dos restricciones y se trazar cada línea recta de
diferente color en el plano y la región (zona óptima de rojo) en cual se encuentra cada restricción
cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta
asociada de cada restricción.
Paso 5. Vértices de la Función objetivo. Cada punto contenido o situado en la frontera del espacio de
soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible. Aunque
hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede
determinarse al tomar los vértices de la zona óptima (marcada con rojo). Se sustituyen estás
coordenadas de los vértices en la Función Objetivo Z = aX1+bX2, obteniendo así los valores de “Z”.
Paso 6. Resultados. Finalmente se toma la decisión del punto óptimo de los resultados de los
vértices de la función objetivo y se colocan el valor de “Z”, “X1” y “X2”.
A continuación, se presenta la solución de la Práctica 1 para mejor comprensión del Método
gráfico.
ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
Practica 1.-Metodo Gráfico de la granja
En una granja se preparan dos clases de producto el P y el Q mezclando 2 químicos A y B una
bolsa de producto P tiene 8kg del químico A y 2kg del químico B y una bolsa del producto Q
contiene 10kg del químico A y 5kg del B cada bolsa del producto B se vende en $300 y cada bolsa
del producto Q en $800. Si en la granja hay almacenadas 800kg del químico A 25 del químico B.
¿Cuántas bolsas de cada tipo de producto se deben preparar para obtener los máximos ingresos?
Paso1.- Cuadro de Datos:
Proceso Producto Almacén
P (X1) Q(X2)
Químico A 8kg 10kg 80kg
Químico B 2kg 5kg 25kg
Ventas ($) $300 $800
Paso 2:
Función Objetivo (Fo)
Z = 300X1 + 800X2
Variables de decisión (Cantidad de Producción)
X1= Producto P
X2= Producto Q
Sujeto a Restricciones
Químico A Químico B
8x1+10X2 < =80 2x1+5x2 <= 25
Paso 3. Convertir restricciones en igualdades
8X1+10X2 <= 80 igualar X2=0 2x1+5x2 <= 25 igualar X2=0
8X1+10(0) =80 2X1+5(0) =25
8X1=80 2X1=25
X1=80/8 X1, X2 X1=25/2 X1, X2
X1= 10 (10 , 0) X1=12.5 (12.5, 0)
8X1+10X2 <= 80 igualar X1=0 2X1+5X2 <=25 igualar X1=0
8(0)+10X2 =80 2(0)+5X2 =25
10X2=80 5X2=25
X2=80/10 X1, X2 X2=25/5 X1, X2
X1= 8 ( 0 , 8) X1= 5 ( 0 , 5)
ASIGNATURA: INVESTIGACIÓN DE OPERACIONES
Paso 4. Gráfica
X2
Químico A
PUNTO OPTIMO
Químico B
ZONA OPTIMA
V2 X1
Paso 5. Vértices de la Función objetivo. Se sustituye X1 ,X2 en la Función objetivo
Vértices X1 X2 Z Z = 300X1 + 800X2
1 0 5 4000 300 (0) + 800 (5) = 4000
2 0 0 0 300 (0) + 800 (0) = 0
3 10 0 3000 300 (10) + 800 (0)= 3000
4 7.5 2 3850 300 (7.5) + 800 (2)= 3850
Paso 6. Resultados
Z = 3850
X1 = 7.5
X2 = 2
