Programación lineal
DOCENTE: Miguel Ernesto Martínez Silva
INTEGRANTES: Fidel José Estrada Cano
FECHA LIMITE: 27/12/2021
Examen de suficiencia de programación lineal
Resumen programación lineal y métodos de resolución
La programación lineal es un método matemático de optimización, que permite representar modelos
lineales para reducir costos o maximizar ganancias en diferentes áreas de una organización. Por lo
que, es utilizada para la administración eficiente de los procesos en todos los ámbitos de la
economía.
Una de sus aplicaciones es la mezcla de productos, generalmente se fabrican 2 o mas productos
utilizando recursos limitados, la empresa debe deducir la cantidad de ambos productos que tendría
que producir para maximizar la utilidad.
La programación lineal consta de tres elementos principales:
Función objetivo: es una ecuación matemática que mide los resultados de cualquier alternativa que
se proponga en la programación lineal, debe ser una ecuación de grado 1, todos los problemas de
programación lineal buscan maximizar la utilidad y disminuir costos.
Variables de decisión: estas son variables que representan un producto, en un problema de
programación lineal pueden aparecer dos o más variables de decisión.
Restricciones: la presencia de limitación restringe el grado en el que se puede alcanzar el objetivo,
los valores que pueden ser seleccionados como variables de decisión están restringidos, no existe la
libertad completa de elección, los valores permisibles de las variables de decisión se definen
mediante inecuaciones lineales.
Los métodos de resolución mas comunes son:
Método grafico: es necesario que el problema de programación lineal tenga no menos de dos
variables, tiene un valor practico limitado, pero es de gran utilidad para visualizar conceptos
subyacentes.
Método simplex: es utilizado para resolver cualquier problema de programación lineal
1) Explicar cada uno de los métodos de programación lineal
Método grafico: El método gráfico es muy útil para problemas de dos variables de decisión.
También se puede utilizar en ejercicios de 3 variables; sin embargo, se hace más difícil visualizar la
representación gráfica. Debido a la imposibilidad de ilustrar más de tres dimensiones no se puede
utilizar para problemas de más de tres variables. Para problemas con mayor número de variables
puedes optar por utilizar Solver (Excel) o el método simplex
Los pasos para resolver un problema mediante método grafico son:
Paso 1: Plantear el problema de Programación Lineal
El paso más importante para resolver un problema de programación lineal es un correcto
planteamiento matemático, ya que se deberá interpretar la función objetivo y las restricciones.
Paso 2: Trazar el gráfico de las restricciones
Cada una de las restricciones deben representarse en el gráfico. Para ello deben determinarse los
puntos de intersección con cada eje y sombrear el área correspondiente (de ser el caso). Se debe
incluir las restricciones de no negatividad.
Paso 3: Determinar la región factible
La zona que se genera de la intersección de las restricciones se conoce como región factible. Esta
región puedes ser acotada o no acotada, así mismo en algunos casos las restricciones no forman
ninguna región factible. Cualquier punto que se ubique dentro de esta región es una solución válida
para la función objetivo.
Paso 4: Trazar la función objetivo
Dado que el método gráfico normalmente se utiliza para problemas de dos variables, la función
objetivo es una recta. Una forma de graficarla es dándole un valor aleatorio como resultado y
calcular su dirección en el plano.
Paso 5: Encontrar la solución visual
Debes ubicar el punto óptimo donde pasará la función objetivo dependiendo si el problema es de
maximización o minimización. El punto óptimo se encontrará en uno de los vértices de la región
factible.
Paso 6: Calcular las coordenadas del punto óptimo
Para calcular las coordenadas del punto óptimo, debes resolver algebraicamente el sistema de
ecuaciones que generan las restricciones que cruzan el punto óptimo.
Paso 7: Determinar el valor óptimo
Finalmente reemplazamos las coordenadas calculadas en el paso anterior en la función objetivo para
determinar su valor óptimo.
Método simplex: es un método analítico de solución de problemas de programación lineal, capaz
de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en
el número de variables.
Los pasos para resolver mediante método Simple son:
Paso 1: identificar la función objetivo y las restricciones
Interpretar matemáticamente la función objetivo que se optimizara del problema de programación
lineal, así también como sus restricciones.
Paso 2: Realizar un cambio de variables y normalizar el signo de los términos independientes
Se realiza un cambio en la nomenclatura de las variables. Estableciéndose la correspondencia
siguiente:
x pasa a ser X1
y pasa a ser X2
Como los términos independientes de todas las restricciones son positivos no es necesario hacer
nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la inecuación (teniendo
en cuenta que esta operación también afecta al tipo de restricción).
Paso 3: Normalizar las restricciones
Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales
según la tabla siguiente
normalmente se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones
del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales, si existen
tres restricciones, por ejemplo, se agregan las tres variables de holgura a la función objetivo.
Paso 4: igualar la función objetivo a cero
Si el problema tiene tres restricciones, se agregan tres variables de holgura a la función objetivo y se
iguala a cero,
Paso 5: Escribir la tabla inicial del método Simplex
La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables de
decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 3.
La primera fila está formada por los coeficientes de la función objetivo, mientras que la última fila
contiene el valor la función objetivo y los costes reducidos Zj - Cj.
Paso 6: condición de parada
Si el objetivo es la maximización, cuando en la última fila no existe ningún valor negativo entre los
costes reducidos (columnas P1 en adelante) se alcanza la condición de parada.
En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z
(columna P0) es la solución óptima del problema.
Otro caso posible es que en la columna de la variable entrante a la base todos los valores son
negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre
resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y
también se puede dar por finalizado el algoritmo.
Paso 7: elección de la base entrante y saliente de la base
Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo
valor en la fila Z sea el menor de entre todos los negativos.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate),
entonces se optará por aquella variable que sea básica.
Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable que
sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término
independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que
ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado
haya resultado mínimo.
Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos
los elementos de la columna pivote fueran de esta condición se habría cumplido la condición de
parada y el problema tendría una solución no acotada.
Paso 8: actualizar la tabla
Los nuevos coeficientes de la tabla se calculan de la siguiente manera:
En la fila del elemento pivote cada nuevo elemento se calcula como:
Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote
En el resto de las filas cada elemento se calcula:
Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote *
Nuevo Elemento Fila Pivote)
Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos
de la columna pivote se anulan (análogo al método de Gauss-Jordan).
Paso 9: comprobar la condición de parada
Se observa en la tabla Simplex la fila de la función objetivo si existen coeficientes negativos, en
caso de que aun existan coeficientes negativos, se vuelve a repetir los pasos 7 y 8 hasta que ya no
queden coeficientes negativos en la fila de la función objetivo
Paso 10: fin del programa
Se observa que en la última fila todos los coeficientes de la función objetivo son positivos
cumpliéndose, por tanto, la condición de parada.
Se toman los valores P1 y P2 que serán la respuesta para optimizar nuestro problema, es decir
cuanta cantidad de cada producto se debe producir para maximizar la utilidad y disminuir costos.
2) Ejemplificar la aplicación de los mismos con un ejercicio resuelto
Ejercicio práctico mediante método grafico
Una empresa fabricante de juguetes produce balones de futbol y juegos de ajedrez. Cada pelota
produce una utilidad incremental de $2, cada juego de ajedrez, una de $4. La fabricación de una
pelota requiere 4 horas de trabajo en el centro de maquinado A y 2 horas en el centro de maquinado
B. La fabricación de un juego de ajedrez tarda 6 horas en el centro de maquinado A, 6 horas en el
centro de maquinado B y 1 hora en el centro de maquinado C. El centro de maquinado A tiene un
máximo de 120 horas de capacidad disponible por día, el centro de maquinado B tiene 72 horas y el
centro de maquinado C tiene 10 horas.
Si la compañía quiere maximizar la utilidad, ¿Cuántas pelotas y juegos de ajedrez debe producir por
día?
Solución:
Planteamiento matemático
P = Número de pelotas a producir por día
J = Número de juegos de ajedrez a producir por día
Función objetivo Z=2 P+ 4 J
A continuación, procedemos a ingresar los datos de nuestro ejercicio y nos vamos a ayudar de la
herramienta PHP simplex para obtener los gráficos
Indicamos el método de resolución, el numero de variables y el numero de restricciones, la de no
negatividad no se incluye porque el software lo hace por defecto
Aquí podemos
observar como
hemos introducido
los coeficientes de
la función objetivo
y las restricciones,
también indicando
el objetivo de la
función que en este
caso es maximizar
Aquí podemos ver el grafico de la función objetivo, las tres restricciones y la región factible
Las líneas negras son restricciones, la línea roja es la función objetivo
La región factible es la figura rellenada de color verde
Por lo tanto los vértices de la región factible son las posibles soluciones que maximizan nuestra
función objetivo, es decir el vértice H,G,C,B, para comprobar cuál de ellos maximiza la función
tendríamos que sustituir los valores de las coordenadas de los vértices en la función objetivo y la
que me del valor más alto será la solución, aunque a simple vista podemos decir que la solución son
las coordenadas del vértice C, ya que es la que esta mas cerca de la función objetivo y de hecho se
toca en ese punto.
Aquí podemos ver los resultados de sustituir los coeficientes de los vértices del grafico en la
función objetivo y sus respectivos valores, podemos ver que el punto C resaltado en verde es la
solución factible que cumple con todas las restricciones y maximiza la función objetivo.
Por lo tanto, la empresa debe producir 24 pelotas y 4 juegos de ajedrez para maximizar su utilidad.
Ejercicio práctico mediante método Simplex
Utilizaremos el problema anterior para realizar este ejemplo de resolución con el método Simplex
Por lo tanto, las condiciones iniciales seguirán siendo
Utilizaremos el mismo software para realizar este ejercicio, pero ahora solucionándolo mediante el
método simplex
Aquí podemos observar como se agregran la variable de holgura puesto que tenemos el menor igual
en las tres restricciones y por lo tanto son tres nuevas variables que hay que agregar a cada
restriccion y a la funcion objetivo igual.
Aquí podemos ver la primera tabla rellenada únicamente con la función objetivo, las variables de
holguras y las restricciones.
En este caso podemos ver la variable que entra es P2 por ser la que tiene el coeficiente más pequeño
en la función objetivo y la variable que entra es P5 al ser la que
tiene el menor resultado de dividir P0 entre cada elemento de P2.
A continuación, se proceden a calcular los nuevos coeficientes de
la tabla utilizando la intersección de la fila y columna pivote que
en este caso seria 1 llamado pivote, así mismo utilizando los
anteriores coeficientes para calcular la fila de la variable que entra
y las otras filas, obteniendo los siguientes resultados.
Obtenemos la siguiente tabla actualizando los coeficientes y
podemos observar que el coeficiente mas bajo de la función
objetivo lo tiene la columna P1 por lo tanto será la variable que
entra y la que sale será P4 porque da el resultado mas bajo al dividir P0 con cada elemento de la
columna P1 recordando que debe ser mayor que 0, por lo tanto, P4 sale y P1 entra
A continuación, se proceden a calcular los nuevos coeficientes de la tabla utilizando la intersección
de la fila y columna pivote que en este caso seria 1 llamado pivote, así mismo utilizando los
anteriores coeficientes para calcular la fila de la variable que entra y las otras filas, obteniendo los
siguientes resultados:
Aquí podemos ver el resultado de actualizar la tabla, podemos
observar que el coeficiente mas bajo lo tiene la columna P5 por lo
tanto será la variable que entra y la que sale será P3 por tener el
menor valor entre la división de la columna P0 con los respectivos de
P5 recordando que tienen que ser mayor que 0, por lo tanto P5 entra y
P3 sale.
A continuación, se proceden a calcular los nuevos coeficientes de la tabla utilizando la intersección
de la fila y columna pivote que en este caso seria 6 llamado pivote, así mismo utilizando los
anteriores coeficientes para calcular la fila de la variable que entra y las otras filas, obteniendo los
siguientes resultados:
si observamos ahora la tabla podemos ver que ya no tenemos coeficientes negativos en la función
objetivo por lo que podemos decir que hemos terminado el problema y la soluciones serán P1=24 y
P2=4 optimiza la función objetivo en 64.
Por lo tanto, la empresa debe producir 24 pelotas y 4 juegos de ajedrez para maximizar su utilidad.
3) Analizar y Realizar un cuadro comparativo de los métodos
Método Características Ventaja Desventaja
Grafico • Intersecciones • Solución rápida • Solo es
• Región factible • Es visual conveniente para
• Puntos • Fácil aplicación dos variables
extremos
Simplex • Variables de • Tipos de • El origen tiene
exceso, holgura, soluciones que ser parte de
básicas, no • Establece el la región factible
básicas, entrada, procedimiento a
salida, solución seguir
básica factible
Método grafico Método Simplex
• El método grafico se utiliza para la resolución • habitualmente se refiere a un conjunto de
de problemas de programación lineal, métodos muy usados para resolver problemas
representando geométricamente las de programación lineal, en los cuales se busca
restricciones, condiciones técnicas y el el máximo de una función lineal sobre un
objetivo. El modelo se puede resolver de conjunto de variables.
manera grafica solo si tiene dos variables
• Es aplicable a problemas de programación
• El método grafico es un procedimiento de lineal multidimensionales, tiene como base el
solución de problemas de programación lineal algebra matricial y el proceso de eliminación
muy limitado. Este consiste en representar cada de Gauss-Jordan. Es un proceso de búsqueda
una de las restricciones y encontrar en la que se vuelve sorprendentemente eficiente para
medida de lo posible el polígono factible solucionar problemas muy grandes.
•facilita el calculo
