Joshua S.

González Novelo

INVESTIGACIÓN DE OPERACIONES ESTOCÁSTICAS

25 de Enero del 2023

PROGRAMACIÓN LINEAL

Universidad del Caribe

Asignatura a cargo del docente Juan Diego Canul Chale

1
INTRODUCCIÓN
En el presente ensayo se hablará acerca de lo que es la programación lineal, así como sus
aplicaciones y los tipos de métodos de resolución existentes, discutiremos las ventajas y
desventajas de cada uno de ellos así como sus pasos a seguir.

2
¿QUÉ ES LA PROGRAMACIÓN LINEAL?

La programación lineal (LP, también conocida como optimización lineal) es el campo de la

programació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 o inecuaciones también
lineales. El método tradicionalmente usado para resolver problemas de programación lineal es el
Método Simplex.

HISTORIA
El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a
Joseph Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La
programación lineal se plantea como un modelo matemático desarrollado durante la Segunda
Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y
aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas
industrias lo usaron en su planificación diaria.

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 punto
interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en
los principios teóricos y prácticos en el área.

El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70

puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de
computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor
asignación es inmensa (factorial de 70, 70!) ; el número de posibles configuraciones excede al
número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución
óptima mediante el planteamiento del problema como una programación lineal y la aplicación
del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de
posibles soluciones factibles que deben ser revisadas.

3
MÉTODOS MÁS COMUNES

Para llegar a la solución de un problema de programación se utilizan diferentes métodos de

solución. Los más difundidos son: el método Gráfico y el método Simplex. El método Simplex,
dependiendo del problema y gustos puede tener diferentes variantes.

A continuación se presentarán los métodos de programación lineal.

MÉTODO GRÁFICO: El método gráficos es un procedimiento de solución de problemas de

programación lineal muy limitado en cuanto al número de variables, pero muy rico en materia de
interpretación de resultados e incluso análisis de sensibilidad

Pasos del método gráfico

1.- Graficar las restricciones

2.- Acotar la región factible
3.- Graficar la F.O.
4.- Ubicar el punto óptimo (solución) en los extremos de la región factible

Ventajas

- Sencillo
- Se pueden explicar varios conceptos

Desventajas

- Solo permite resolver modelos de hasta 3 variables

- Se tiene que realizar una buena grafica

MÉTODO SIMPLEX: El método gráfico indica que la solución óptima de un programa lineal
siempre está asociada con un punto esquina del espacio de soluciones. Este resultado es la clave
del método Simplex algebraico y general para resolver cualquier modelo de programación lineal.
La transición de la solución del punto esquina geométrico hasta el método Simplex implica un
procedimiento de cómputo que determina en forma algebraica los puntos esquina.

4
 El desarrollo de los cálculos con el método Simplex se facilita si se imponen los
requerimientos a las restricciones de programación lineal.

1.- Todas las restricciones son ecuaciones con lado derecho no negativo.
2.- Todas las variables son no negativas

Pasos del método Simplex

La forma estándar del modelo de problema consta de una función objetivo sujeta a
determinadas restricciones

El modelo debe cumplir las siguientes condiciones:

1.- El objetivo consistirá en maximizar o minimizar el valor de la función objetivo

2.- Todas las restricciones deben ser ecuaciones de igualdad
3.- Todas las variables deben tener valor positivo o nulo
4.- Los términos independientes de cada ecuación deben ser no negativos

Debemos adaptar el problema modelando a la forma estándar para poder aplicar el algoritmo
del Simplex

Ventajas

- No hay que preocuparse por nuevos criterios de parada, condiciones de entrada y salida de la
base ya que se mantienen

Desventajas

- En el caso de que la función tenga todos los coeficientes de sus variables básicas positivos, y
además las restricciones sean del tipo de desigualdad “≤”, al hacer cambio dichos coeficientes
quedan negativos cumpliendo la condición de parada en la primera iteración. Obteniendo en este
caso por defecto un valor óptimo para la función igual a 0.

5
PROGRAMACIÓN LINEAL ENTERA

¿Qué es?

La programación lineal entera surge como respuesta a los problemas de programación lineal,
donde algunas, o todas las variables de decisión, están condicionadas a tomar valores enteros. La
condición de integralidad para las variables de decisión aparece en una gran cantidad de
problemas lineales. Por ejemplo, una constructora que construye edificios en dos zonas
diferentes de una misma ciudad (zona N y zona S), sabe que para maximizar sus beneficios debe
construir 7,8 edificios en la zona N y 9,3 en la zona B, sin embargo, esta solución no es válida.
Será necesaria una solución entera. Existen multitud de ejemplos como éste, como pueden ser los
problemas de selección de proyectos, del transporte, de asignación de servicios, del viajante, del
coste fijo, de distribución de un presupuesto.., en definitiva , de todo aquello que no es divisible.

Cabría pensar que, puesto que el conjunto de soluciones factibles de un problema entero es
mucho más reducido que el del mismo problema lineal con las variables libres de esta condición,
se podría obtener la solución simplemente evaluando la función objetivo en dichos puntos. Sin
embargo no es fácil conocer explícitamente las soluciones posibles enteras y habitualmente hay
un número excesivamente grande de ellas. Tampoco el redondeo de la solución óptima del
problema lineal continuo (problema lineal entero sin la restricción de integralidad para las
variables) conduce a la solución del problema entero ya que en la mayor parte de los casos
incumple algunas de las restricciones del problema.

Se han desarrollado métodos específicos para la resolución de estos problemas, pero no hay un
“método” de resolución de problemas lineales enteros como el algoritmo del Simplex en
Programación Lineal, sino una colección de algoritmos generalmente basados en las
particularidades específicas de cada tipo de problema. Una característica común a la mayoría 5
de estos métodos de solución es que comienzan resolviendo el P.L. Continuo (en adelante P.L.C.)
asociado y a partir de su solución óptima introducen técnicas específicas para alcanzar la
solución óptima entera. Los primeros intentos surgieron en 1958 de la mano de R. Gomory, se
trataba del primer algoritmo finito, conocido como “Método de los Cortes de Gomory”. Tan sólo
dos años después, en 1960, A. Lang y A. Doig, a partir del método de Gomory desarrollaron
“Los Métodos de Branch and Bound ”, también conocidos como métodos de ramificación y
acotación. En 1965, E. Balas desarrolló “Los Métodos de Enumeración Implícita”.

6
 A pesar de los avances en el campo de la P.L.E. y aunque la solución mediante los algoritmos
desarrollados esté teóricamente garantizada, otros factores como el número de variables y de
condiciones que hacen indispensable el uso de ordenadores restan eficacia a los procedimientos
de obtención de óptimo. En estos casos otro tipo de métodos, los algoritmos heurísticos,
proporcionan una buena aproximación a la solución del P.L.E.

Métodos de resolución de problemas de programación entera

Analizaremos dos métodos de resolución de Problemas Lineales Enteros: Métodos

Enumerativos y Métodos de Planos de Corte y haremos algunas anotaciones sobre los
procedimientos de resolución utilizados en aquellas situaciones en que dificultades de cálculo
impiden la implementación de algoritmos exactos, los Métodos Heurísticos. A continuación
describiremos dichos métodos.

MÉTODOS DE PLANOS DE CORTE: Los métodos de planos de corte parten de la

resolución del P.L.C. asociado al P.L.E. y tienen como objetivo lograr mediante la incorporación
de nuevas restricciones o planos de corte que las variables de decisión óptimas sean enteras.
Estas nuevas restricciones, restringen el conjunto factible del problema continuo sin suprimir
ninguna solución posible entera.

La resolución de los sucesivos P.L.C. generados conforme se van añadiendo los cortes se
realiza mediante el algoritmo del Simplex. La estructura de los cortes garantiza que la solución
de estos problemas converge a la solución del P.L.E. Podemos distinguir entre, algoritmo
fraccional de Gomory y algoritmo todo entero de Gomory, en función de las características del
problema.

Los métodos de los planos de corte resuelven el problema de la programación lineal de la

siguiente manera:

1. Resolución del problema lineal continuo asociado.

2. Si la solución óptima del problema es entera, ésta será la solución del problema entero.
En caso contrario se elige una de las variables de decisión que debería ser entera y a partir de ella
se construye el corte.
3. Una vez añadido el plano de corte, se resuelve nuevamente el problema. Si la solución
óptima obtenida sigue sin ser entera, debemos repetir los pasos anteriores hasta que dichas
variables sean enteras. Sin embargo, si las variables de decisión resultantes son enteras, se para el
proceso, pues hemos conseguido nuestro objetivo.

7
 MÉTODOS ENUMERATIVOS: Los métodos enumerativos, son aquellos que buscan la
solución óptima de los problemas de programación lineal entera, a partir del conjunto de
soluciones factibles enteras, de tal manera que no es necesario examinar todas las posibles
soluciones factibles enteras de manera individual. Dentro de estos métodos, podemos distinguir
entre los Métodos de Branch and Bound o de Ramificación y Acotación, y los Métodos de
Enumeración Implícita.

MÉTODOS HEURÍSTICOS: Los métodos heurísticos surgen como respuesta a la

complejidad para la resolución de problemas, los cuáles requieren soluciones en un tiempo
limitado, sin necesidad de ser soluciones óptimas, basta con que se aproximen al valor óptimo.
La resolución de este tipo de problemas se lleva a cabo a través de algoritmos heurísticos o
algoritmos aproximados , los cuáles, al contrario que el resto de algoritmos analizados
(algoritmos exactos), proporcionan siempre una solución factible al problema.

Estos algoritmos estuvieron expuestos a numerosas críticas debido a su escasa rigidez

matemática. Sin embargo, gracias a su gran aportación a problemas cotidianos, fueron poco a
poco admitidos entre los métodos de resolución de P.L.E.

CONCLUSIÓN
Después de redactar este trabajo se pudo entender la importancia que tiene la programación
lineal en nuestro dia a dia, del mismo modo entender lo explícita que se encuentra en nuestra
vida, siendo una herramienta al alcance de todos sería bueno considerar el empezar a
implementarlo en nuestras decisiones del día. Tal vez de esta forma podrá aprovechar al máximo
los resultados de las decisiones que tomemos.

Se pudo observar los distintos métodos de solución que existe para los problemas y entender
mejor las características de cada unos, así como sus ventajas y desventajas.

8
BIBLIOGRAFÍAS
- Crilly, Tony (2011). 50 cosas que hay que saber sobre matemáticas. Ed. Ariel.
- Loomba, N.P. Linear Programming: An introductory analysis. McGraw-Hill, New York,
1964
- G. Anaya N.P. Métodos de solución a problemas de programación lineal, Issuu
- M. Docio (2015). Programación Lineal Entera: Un problema de Planificación de
Plantilla, UV