Tema II. Programación Lineal

2.1. Programación Matemática

Segun Peñafiel y Millan (1985), existe un creciente interés en utilizar técnicas matemáticas de optimizacion para resolver problemas de programación que no es posible solucionar con los métodos clásicos del calculo diferencial y del calculo de variaciones, los cuales se han venido aplicando principalmente en ciencias físicas e ingeniería desde mediados del siglo XVII. Recientemente se han desarrollado nuevas herramientas matemáticas aplicables a los mas diversos problemas, en estos se encuentran grupos de actividades interrrelacionadas que pueden ser dispuestas en una estructura representable por símbolos y ecuaciones que nos definen a un modelo matemático.   

En la tabla 1.  se agrupan algunas tipificaciones de modelos matemáticos

Tabla 1. Algunos Modelos Matemáticos  

2.2. Programación Lineal 

2.2.1. Definición 

La Programación Lineal corresponde a un algoritmo a través del cual se resuelven situaciones reales en las que se pretende identificar y solucionar dificultades para aumentar la productividad respecto a los recursos (principalmente los limitados y costosos), aumentando así los beneficios. El objetivo primordial de la Programación Lineal es optimizar, es decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando una función objetivo también lineal.

Los resultados y el proceso de optimización se convierten en un respaldo cuantitativo de las decisiones frente a las situaciones planteadas. Decisiones en las que es recomendable considerar:  (a) Los hechos; (b) La experiencia; (c) La intuición y (d) La autoridad.

2.2.2. Resolución de problemas mediante Programación Lineal (PL)

El primer paso para la resolución de un problema de programación lineal consiste en la identificación de los elementos básicos de un modelo matemático, estos son: (a) Función Objetivo; (b) Variables y (c) Restricciones

El siguiente paso consiste en la determinación de los mismos, para lo cual proponemos seguir la siguiente metodología:

• 1. Definir el criterio de la Función Objetivo:  La función objetivo tiene una estrecha relación con la pregunta general que se desea responder. Sí en un modelo existen distintas preguntas, la función objetivo se relacionaría con la pregunta del nivel superior, es decir, la pregunta fundamental.

  2. Identificar y definir las variables: Similar a la relación que existe entre objetivos específicos y objetivo general se comportan las variables de decisión respecto a la función objetivo, puesto que estas se identifican partiendo de una serie de preguntas derivadas de la pregunta fundamental. Las variables de decisión son en teoría factores controlables del sistema que se está modelando, y como tal, estas pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor óptimo, que contribuya con la consecución del objetivo de la función general del problema.

  3. Identificar y definir restricciones: 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. La mejor manera de hallarlas consiste en pensar en un caso hipotético en el que decidiéramos darle un valor infinito a nuestras variables de decisión.

  4. Plantear la Función Objetivo

2.2.3. Formulación de Problemas mediante Programación Matemática 

Se define como programación matemática, como optimizar una función z=f (x1,x2,x3,x4,x5,...,xn) de n variables o incógnitas, llamada función objetivo, cuando esta sujeta a un conjunto de m restricciones o limitaciones expresadas por las funciones:

q1 (x1, x2, x3, x4, x5,...,xn) >o= o < b1

q2 (x1, x2, x3, x4, x5,...,xn) >o= o < b2

qm (x1, x2, x3, x4, x5,...,xn)>o= o < bm

en las que m (numero de restricciones) puede ser mayor, igual o menor que n (numero de incógnitas).

• • Si la función objetivo y las restricciones del problema están formadas expresiones de primer grado (funciones lineales) y las variables son no negativas, se tiene el caso de la programación lineal. 

  • Si la función objetivo y/o las restricciones son no lineales se hablara de programación no lineal.

  • Si se busca optimizar la función objetivo considerando que la decisión tomada no es afectada por decisiones previas y no afecte decisiones futuras, es un caso estático.

  • Si cada decisión afecta a las decisiones futuras, es un caso dinámico.  Este caso tiene aplicación en gran variedad de situaciones practicas como mantenimiento y reparación de maquinaria, remplazo de equipos, entre otros. i

  • Si se trabaja con un modelo en el que los coeficientes en la función objetivo y/o en el conjunto de restricciones son fijos y conocidos, es un caso de programación de modelos deterministicos.

  • Si existen elementos de incertidumbre que pueden introducirse de variadas formas dentro del modelo, es un caso probabilista o estocástico. 

2.2.3.1 Definición general de un problema de Programación Lineal

Se puede definir el problema de programación lineal como la obtención del máximo o mínimo de una funcion lineal 

z = c1x1 + c2x2 + c3x3 + ... cnxn

Sujeta a (SA) limitaciones o restricciones lineales expresadas como: 

a11x1 + a12x2 + a13x3 +.........+a1nxn ><= b1

a21x1 + a22x2 + a23x3 +.........+a2nxn ><= b2

a31x1 + a32x2 + a33x3 +.........+a3nxn ><= b3

am1x1 + am2x2 + am3x3 +.........+amnxn ><= bm

donde xi >= 0 para i=1...n

Referencias Bibliograficas 

Lucas Jódar y Paloma Merello (2014). Soluciones del modelo de Leontief dinámico con datos variables en el tiempo. XVI Jornadas ASEPUMA – IV Encuentro Internacional, Rect@ Vol Actas_16 Issue 1:204. Universidad Politécnica de Valencia, España. Disponible en: http://www.uv.es/asepuma/XVI/204.pdf

 Guia de teoria 

Practica 2. Programación Lineal, Ejercicios Mediante Método Gráfico 

CONTENIDO:

Un modelo matemático es una descripción, en lenguaje matemático, de un objeto que existe en un universo no-matemático. Estamos familiarizados con las previsiones del tiempo, las cuales se basan en un modelo matemático meteorológico; así como con los pronósticos económicos, basados éstos en un modelo matemático referente a economía. La mayoría de las aplicaciones de cálculo (por ejemplo, problemas de máximos y mínimos) implican modelos matemáticos. En términos generales, en todo modelo matemático se puede determinar 3 fases: 

• Construcción del modelo. Transformación del objeto no-matemático en lenguaje matemático. 

• Análisis del modelo. Estudio del modelo matemático. 

• Interpretación del análisis matemático. Aplicación de los resultados del estudio matemático al objeto inicial no-matemático. 

TIEMPO: 12 horas/prácticas

SEMANA: 6-7

EJERCICIOS:

Ejercicios Mediante Método Gráfico 

Problema 1. Con dos recursos escasos R1 y R2, se pueden elaborar dos productos distintos P1 y P2. Para producir una unidad de P1 se necesitan 8 unidades de R1y 2 unidades de R2, para producir una unidad de P2 se necesitan 6 unidades de R1 y 4 de R2. Se cuenta con 20 unidades de R1 y 10 de R2 y se sabe que P1 produce una utilidad de $8 y que P2 produce una utilidad de $10. Suponiendo que los valores dados son fijos para cualquier nivel de producción, se desea encontrar el nivel positivo de producción de cada producto, sin sobrepasar las limitaciones de recursos de modo que maximice la utilidad.  Así pues se tiene la tabla 1

Tabla 1. Datos del Problema 1

                                                          P1                            P2                      Limitación del recurso

                                       R1               8                              6                           20

                                       R2             2                              4                           10

Ganancia unitaria                             8                              10

1. Construya la Función Objetivo y las restricciones a las que está sujeta.

2. Grafique el problema y encuentre el área de solución y la solución óptima mediante el software(descargar desde el enlace de la página de la asignatura WinQSB2.0 o superior )

Ayuda: Una vez descargado el software y ejecutado el archivo setup que está en la carpeta de instalación. Entre en la aplicación y cuando se despliegue  la ventana con las opciones indique Programación lineal y entera (véase figura 1). Luego indique en archivo (FILE) nuevo problema (véase figura 2). Posteriormente señale los datos de su problema

Problema 2. Sean tres recursos escasos R1, R2 y R3, con los que se pueden elaborar dos productos distintos P1 y P2. Para producir una unidad de P1 se necesitan 5 unidades de R1, 3 unidades de R2 y 2 de R3, para producir una unidad de P2 se necesita 4 unidades de R1 2 de R2 y 6 de R3. Se cuenta con 130 unidades de R1, 234 de R2 y 105 de R3 y se sabe que P1 produce una utilidad de $18 y que P2 produce una utilidad de $5. Suponiendo que los valores dados son fijos para cualquier nivel de producción, se desea encontrar el nivel positivo de producción de cada producto, sin sobrepasar las limitaciones de recursos de modo que maximice la utilidad.

Construya la tabla asociada al problema 

Construya la Función Objetivo y las restricciones a las que está sujeta.

Grafique el problema y encuentre el área de solución y la solución óptima mediante el software(descargar desde el enlace de la página de la asignatura WinQSB2.0 o superior )

Problema 3. Para fabricar dos productos P1 y P2, se utilizan tres maquinas M1, M2 y M3, sin que sea necesario ajustarse a un orden. Los tiempos unitarios de ejecución están dados en la siguiente tabla 2

Tabla 2. Datos del problema 3

Tiempo necesario por Unidad (minutos)

Producto              M1           M2            M3

            P1                        11             7               6

                                                                                  P2                         9             12             16

Además, las máquinas no tienen tiempos muertos al esperar un producto que se esté procesando en otra maquina. El orden de las operaciones es indiferente. Las horas disponibles para cada máquina, para una actividad de un mes son: 

165 horas para la máquina M1 (9900 minutos)

140 horas para la máquina M2 (8400 minutos)

160 horas para la máquina M3 (9600 minutos)

La utilidad que producen los productos P1 y P2, por unidad producida son: $ 0,90 P1 y $1 P2

¿Cuántas unidades de P1 y P2 se deben fabricar mensualmente para tener un beneficio total máximo?

Programación

1. Descargue el software recomendado para la asignatura Aqui

2. Investigue las funciones y comendos de OCTAVE

   • funcion anonima f=@(x)

   • CLC

   • ezplot (f)

   • hold on 

   • fminbnd ()

   • fminunc

   • glpk

   • sqp

NOTA: Los Resultados los pueden enviar por el Grupo de Telegram(https://t.me/+HQ49q4UzZOX7rjZr)

Ejemplo de solución en OCTAVE