UNIDAD XII.
PROGRAMACIÓN LINEAL
La programación lineal, también conocida como optimización lineal es el campo
de la programación matemática dedicado a maximizar o minimizar 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.
12.1 Método Grafico
El método gráfico es una técnica que permite resolver los problemas de
programación lineal de manera intuitiva y visual. Consiste en la representación
geométrica de las restricciones para formar la región factible y trazar la función
objetivo en el punto óptimo.
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.
12.1.1 Representación gráfica de inecuaciones lineales de dos variables
Una inecuación en dos variables es una inecuación que puede ser
escrita como:
ax+by<c
o cualquier expresión de la forma anterior que, en lugar del símbolo < incluya
cualquier otro símbolo de desigualdad: > , ≤ o ≥
donde a, b y c son constantes y x y y son variables. Resolver una
inecuación en dos variables consiste en encontrar todos los pares de
valores de (x,y) para los cuales se cumple la desigualdad.
Cuando se intercambia el signo de desigualdad por el signo igual, se
obtiene una ecuación que viene a ser la frontera de la solución de la
desigualdad. Por ejemplo, considerando la siguiente desigualdad: y<x.
Cambiando el signo < por el signo = obtenemos la ecuación: y=x. La gráfica de
esta ecuación es una recta que divide el plano en dos regiones:
Para resolver una inecuación de la forma:
ax+by<c
o cualquier expresión de la forma anterior que, en lugar del símbolo < incluya
cualquier otro símbolo de desigualdad: > , ≤ o ≥, seguiremos los siguientes
pasos:
1. Reemplazar el signo de desigualdad por el signo = ax+by=c y dividir el
plano cartesiano tomando como frontera la recta que representa la
ecuación obtenida.
2. Tomar puntos de prueba en cada región y verificar si satisfacen la
desigualdad.
3. Graficar la solución, teniendo en cuenta que si la desigualdad es ≥ o ≤ la
frontera está incluida en la solución, en caso contrario la frontera no está
incluida.
12.1.2 Representación gráfica de sistemas de inecuaciones
lineales de dos variables
La solución de una inecuación es el conjunto de valores de las variables que
verifica la inecuacíón. El conjunto de soluciones genera una región geométrica
en la recta real si la inecuación es de una variable, o en el plano si es de dos.
Ejemplo:
La inecuación nos genera la
siguiente región en el plano.
Sistema de inecuaciones
La solución de un sistema de inecuaciones es la intersección de las regiones
que corresponden a la solución de cada inecuación.
Un sistema de inecuaciones se dice que es lineal, si en ambos lados de cada
inecuación aparece una expresión de primer grado.
12.1.3 Análisis grafico de algunos casos excepcionales
En ocasiones, pueden existir múltiples soluciones que maximizan o minimizan la
función objetivo de un modelo de programación lineal, es decir, múltiples
soluciones óptimas. La elección de la solución en un contexto de aplicación
práctico dependerá tanto de la sensibilidad de las restricciones activas como de los
factores propios del sistema que no se consideran en un modelo matemático.
Dentro de los casos excepcionales existen diferentes tipos de casos:
1. Caso de infinitas soluciones: Si la función objetivo es paralela a una de las
restricciones, indicando esto que la función y esa restricción no son linealmente
independientes, existen infinitas soluciones óptimas. La función objetivo tomará
el mismo valor óptimo en más de un punto solución. Cualquier punto en el
segmento de la recta será solución del problema.
2. Caso de soluciones no acotadas: En algunos modelos de programación
lineal, los valores de las variables se pueden aumentar en forma indefinida sin
violar ninguna de las restricciones, lo que significa que el espacio de soluciones
es no acotado al menos en una dirección. Como resultado, el valor de la
función objetivo puede crecer en forma indefinida. En este caso decimos que el
espacio de soluciones y el valor óptimo de la función objetivo son no acotados.
3.- Caso de soluciones infactibles: Sucede cuando las restricciones no se
pueden satisfacer en forma simultánea, es decir no hay soluciones factibles.
Esta situación no puede ocurrir si todas las restricciones son del tipo ≤. Desde
el punto de vista práctico, un espacio infactible apunta a la posbilidad de que el
modelo no se haya formulado correctamente, en virtud de que las restricciones
están en conflicto.
12.2 El método Simplex
El método simplex es un algoritmo utilizado en la programación lineal para
resolver problemas de optimización. En términos simples, busca encontrar la
mejor solución posible a un problema dado, considerando ciertas restricciones
y maximizando o minimizando una función objetivo.
El método simplex trabaja en un espacio geométrico llamado espacio de
soluciones factibles. Cada punto en este espacio representa una combinación
de las cantidades de productos A y B que puedes fabricar dentro de las
restricciones dadas. El algoritmo se mueve de un punto a otro, mejorando
gradualmente la solución, hasta que encuentra el punto óptimo que maximiza
tus ganancias.
El método simplex tiene varias ventajas que lo convierten en una herramienta
de gran utilidad. Algunas de ellas son; Aplicable a problemas de gran escala,
buscar solución óptima; tiene Flexibilidad en la formulación del problema;
Permite identificar soluciones no factibles o ilimitadas su Interpretación es
geométrica
