República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Instituto Universitario Politécnico
´´Santiago Mariño´´
Carrera: 46 Ing. De Mtto. Mecánico.
Cátedra: Algebra Lineal
Sección: G
PROGRAMACION LINEAL
Profesor: Bachiller:
William Morillo Vallenilla , Vera María Victoria
C.I 31.035.324
Venezuela, Bna-Edo Anzoátegui 31 de julio de 2021
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. Típicamente trata del problema
de asignar recursos limitados entre actividades
competidoras en la mejor forma posible, es decir, óptimas.
En un problema de programación lineal se trata de optimizar
(hacer máxima o mínima, según los casos) una función
(llamada función objetivo) sujeta a una serie de restricciones
dadas mediante un sistema de ecuaciones y/o inecuaciones
lineales. El adjetivo “lineal” significa que se requiere que
todas las funciones matemáticas en este modelo sean
funciones lineales.
El método tradicionalmente usado para resolver problemas
de programación lineal es el Método Simplex
Historia de la programación lineal
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.2 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.
Todo programa lineal consta de :
Variables
Las variables son números reales mayores o iguales a cero
En caso que se requiera que el valor resultante de las variables sea un número
entero, el procedimiento de resolución se denomina Programación entera. Por
otro lado cuando se requiera que el valor resultante de las variables solo tome 2
Valores (0 , 1) , el procedimiento de resolución se denomina Programación
Binaria.
Cuando hablamos de las restricciones en un problema de programación lineal,
nos referimos a todo aquello que limita la libertad de los valores que pueden
tomar las variables de decisión
Función objetivo :
En esencia la programación lineal consiste en optimizar
(maximizar o minimizar) una función objetivo, que es una
función lineal de varias variables:
Ejemplo : La función objetivo está sujeta a una serie de
restricciones, expresadas por inecuaciones lineales:
Cada desigualdad del sistema de restricciones determina
un semiplano.
Solución factible:
Es el conjunto intersección, de todos los semiplanos formados por
las restricciones, determina un recinto, acotado o no, que recibe el
nombre de región de validez o zona de soluciones factibles.
Solución óptima : El conjunto de los vértices del recinto se
denomina conjunto de soluciones factibles básicas y el vértice
donde se presenta la solución óptima se llama solución máxima
(o mínima según el caso).
Valor del programa lineal : El valor que toma la función
objetivo en el vértice de solución óptima se llama valor del programa
lineal.
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
posibilidad de que el modelo no se haya formulado correctamente, en virtud
de que las restricciones están en conflicto
En el siguiente ejemplo se explicara cómo
resolver un problema de programación lineal
Una compañía fabrica y venden dos modelos de lámpara L1 y
L2. Para su fabricación se necesita un trabajo manual de 20
minutos para el modelo L1 y de 30 minutos para el L2; y un
trabajo de máquina de 20 minutos para el modelo L1 y de 10
minutos para L2.
Se dispone para el trabajo manual de 100 horas al mes y para
la máquina 80 horas al mes. Sabiendo que el beneficio por
unidad es de 15 y 10 euros para L1 y L2, respectivamente,
planificar la producción para obtener el máximo beneficio.
Paso 1 Elección de las incógnitas.
x = nº de lámparas L1
y = nº de lámparas L2
Paso 2 Función objetivo
f(x, y) = 15x + 10y
Paso de 3 Restricciones .Pasamos los tiempos a horas
20 min = 1/3 h
30 min = 1/2 h
10 min = 1/6 h
Para escribir las restricciones vamos a ayudarnos de una tabla:
Como el número de lámparas son números naturales, tendremos dos
restricciones más
x≥0
y≥0
Paso 4 Hallar el conjunto de soluciones factibles,
Tenemos que representar gráficamente las restricciones. Al ser x ≥ 0 e y ≥ 0,
trabajaremos en el primer cuadrante. Representamos las rectas, a partir de sus
puntos de corte con los ejes. Resolvemos gráficamente la inecuación: 1/3 x +
1/2 y ≤ 100; para ello, tomamos un punto del plano, por ejemplo el (0,0).
1/3•0 + 1/2•0 ≤ 100
La zona de intersección de las soluciones de las
1/3•0 + 1/6•0 ≤ 80 inecuaciones sería la solución al sistema de inecuaciones,
que constituye el conjunto de las soluciones factibles.
Paso 5 : Calcular las coordenadas de los vértices del recinto de las
soluciones factibles.
La solución óptima si es única se encuentra en un vértice del recinto. Estos
son las soluciones a los sistemas:
1/3x + 1/2y = 100; x = 0 (0, 200)
1/3x + 1/6y = 80; y = 0 (240, 0)
1/3x + 1/2y = 100; 1/3x + 1/6y = 80 (210, 60)
Paso 6 : Calcular el valor de la función objetivo
En la función objetivo sustituimos cada uno de los vértices.
f(x, y) = 15x + 10y
f(0, 200) = 15•0 + 10•200 = 2 000 €
f(240, 0 ) = 15•240 + 10•0 = 3 600 €
f(210, 60) = 15•210 + 10•60 = 3 750 € Máximo
La solución óptima es fabricar 210 del modelo L1 y 60 del modelo L2 para
obtener un beneficio de 3 750 € .
Ejemplo 2: Se dispone de 600 g de un determinado fármaco para elaborar pastillas
grandes y pequeñas. Las grandes pesan 40 g y las pequeñas 30 g. Se necesitan al menos
tres pastillas grandes, y al menos el doble de pequeñas que de las grandes. Cada pastilla
grande proporciona un beneficio de 2 € y la pequeña de 1 €.
¿Cuántas pastillas se han de elaborar de cada clase para que el beneficio sea máximo?
Paso 1 Elección de las incógnitas.
x = Número de pastillas grandes
y = Número de pastillas pequeñas
Paso 2 Función objetivo
f(x, y) = 2x + y
Paso 3 Restricciones
40x + 30y ≤ 600
x≥3
y ≥ 2x
x≥0
y≥0
Paso 5 Calcular las coordenadas de
Paso 4 Hallar el conjunto de soluciones factibles
los vértices del recinto de las
soluciones factibles.
Paso 6 Calcular el valor de la función objetivo
f(x, y) = 2 • 3 + 16 = 22 €
f(x, y) = 2 • 3 + 6 = 12 €
f(x, y) = 2 • 6 + 12 = 24 € Máximo
El máximo beneficio es de 24 €, y se obtiene fabricando 6
pastillas grandes y 12 pequeñas.
Método Simplex
El 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. El Método Simplex es un método iterativo que
permite ir mejorando la solución en cada paso.
Para comprender de mejor manera el método simplex vamos a revisar
algunas definiciones.
El método parte de dos afirmaciones importantes:
[Link] conjunto de posibles soluciones o conjunto factible de cualquier
problema de programación lineal puede representarse mediante un
poliedro convexo.
[Link] un problema de programación lineal tiene una solución óptima y finita,
ésta estará en un vértice del poliedro convexo que representa al problema.
El algoritmo simplex parte de uno de los vértices del poliedro, y verifica si es el
óptimo; si no lo es, busca un nuevo vértice adyacentes que va mejorando el valor
de la función objetivo
Se continúa iterando hasta llegar al vértice que representa la solución óptima. En
la siguiente imagen vemos el poliedro que representa la solución factible y cómo
realiza el recorrido el algoritmo simplex:
Los pasos a seguir en el método Simplex son:
[Link] el problema en la forma estándar y generar nuestra matriz.
[Link] la solución básica inicial.
[Link] la variable de entrada utilizando la condición de optimalidad. Si no se
puede seleccionar una variable de entrada, quiere decir que estamos en la condición
óptima y finalizan las iteraciones. De otro modo se continúa con el siguiente paso.
[Link] la variable de salida utilizando la condición de factibilidad.
[Link] nuestra matriz realizando las operaciones de Gauss-Jordan. Volver al
paso número 3.
¿Qué es una matriz identidad?
Una matriz puede definirse como una ordenación rectangular de elementos, (o
listado finito de elementos), los cuales pueden ser números reales o complejos,
dispuestos en forma de filas y de columnas. La matriz idéntica o identidad es una
matriz cuadrada (que posee el mismo número tanto de columnas como de filas) de
orden n que tiene todos los elementos diagonales iguales a uno (1) y todos los
demás componentes iguales a cero (0), se denomina matriz idéntica o identidad de
orden n, y se denota por:
La importancia de la teoría de matrices en el Método Simplex es
fundamental, dado que el algoritmo se basa en dicha teoría para la
resolución de sus problemas.
Este método busca mejorar la función objetivo evaluando la misma en las
intersecciones de las restricciones, las iteraciones se realizan de manera tal
que la función objetivo es siempre mejorada, puede aplicarse a problemas de
cualquier tamaño. El algoritmo define variables adicionales, que se introducen
en las restricciones de desigualdad, convirtiéndolas en restricciones de
igualdad, estas variables se denominan variables flojas
(slack). Dada una restricción general de ≤, se convierte en restricción de
igualdad agregando variables
flojas no negativas (slack) de la siguiente manera:
Donde sj es la variable floja. Si la variable floja es cero, la restricción se
encuentra en su límite, se
dice que esta activa, sino la restricción estará inactiva.
Ejemplo: La empresa Seventeen SRL se dedica a la fabricación de manteles
de mesa. Fabrica dos modelos, el redondo (x1) y el rectangular (x2). Cada uno
consume 2 y 3 m2 de tela, respectivamente. Además deben ser cortados y
cosidos a mano, tarea que lleva una hora para los manteles rectangulares y
dos para los redondos. Por último, a los manteles rectangulares se les deben
colocar cuatro esquineros de refuerzo.
.
Semanalmente se pueden conseguir 600 m2 de tela, 600 esquineros y
500 horas de corte y costura. Los márgenes de ganancia son de $8 para
los manteles redondos y $10 para los rectangulares.
El número total de variables, incluyendo las variables flojas, de nuestro problema
es 5. El número de ecuaciones es 3 (restricciones). El problema no tendrá
solución única. Si se fijan valores para dos variables, por ejemplo iguales a 0,
tendremos un sistema de 3 ecuaciones con 3 incógnitas, encontraremos así los
valores de las tres variables restantes.
Este proceso se denomina formulación de la solución básica. Las variables no
nulas se denominan variables básicas. En nuestro caso la primer solución básica
corresponde a x1 y x2 iguales a cero unidades por semana, por lo tanto el resto de
las variables serán las variables básicas. La tabla del método simplex se forma de
la siguiente manera, la matriz anterior es la estructura central de la tabla:
La tabla así armada representa un vértice del poliedro del problema.
Este vértice es el determinado por la intersección de las rectas
asociadas a las variables que no están representadas por la base
canónica, esta base esta representada por las variables incluidas en la
matriz identidad, o sea cuyas columnas tienen como coeficientes uno en
la intersección de su propia fila y cero en las demás.
En este problema las variables que no están en la base canónica son x1
y x2, ambas son cero, indicando esto que no se fabrica ningún mantel y
las demás variables tienen los valores indicados en la columna de los
términos independientes, o sea, sobra la totalidad de los recursos. Las
variables que no se encuentran en la base no tienen influencia en la
función objetivo, ya que su valor es cero.
Examinamos ahora la función objetivo para determinar cual de las variables no
básicas (x1 o x2) genera un mayor incremento de la función objetivo al
modificar su valor. Esta variable pasa a ser básica. Una regla general para
elegir la variable que pasará a ser básica es seleccionar la variable
que posea el coeficiente negativo mayor en la dila de la función objetivo. En
nuestro caso la nueva variable básica es x2, simultáneamente una de las
variables básicas anteriores dejara de serlo, debemos determinar ahora cual
de ellas.
La variable que aumenta en mayor proporción la función objetivos es x2,
entonces esta variable debe aumentarse tanto como sea posible. El límite
lo establecen las restricciones. Para determinar que variable pasará a ser
no básica se deben realizar los cocientes entre el valor actual de cada
variable (términos independientes) y los coeficientes de la columna
correspondiente a la variable que entra en la base.
En definitiva la programación lineal constituye un importante campo de la
optimización por varias razones, muchos problemas prácticos de la
investigación de operaciones pueden plantearse como problemas de
programación lineal. Algunos casos especiales de programación lineal, tales
como los problemas de flujo de redes y problemas de flujo de mercancías se
consideraron en el desarrollo de las matemáticas lo suficientemente
importantes como para generar por sí mismos mucha investigación sobre
algoritmos especializados en su solución.
Una serie de algoritmos diseñados para resolver otros tipos de problemas de
optimización constituyen casos particulares de la más amplia técnica de la
programación lineal. Históricamente, las ideas de programación lineal han
inspirado muchos de los conceptos centrales de la teoría de optimización
tales como la dualidad, la descomposición y la importancia de la convexidad y
sus generalizaciones. Del mismo modo, la programación lineal es muy usada
en la microeconomía, la ingeniería y la administración de empresas, ya sea
para aumentar al máximo los ingresos o reducir al mínimo los costos de un
sistema de producción.
