Practica1 IntroduccionMR 1

UNIVERSIDAD CATÓLICA DE SANTA MARÍA
PROGRAMA PROFESIONAL DE INGENIERÍA DE SISTEMAS



SESIÓN 1: INTRODUCCIÒN A LA PROGRAMACIÒN LINEAL



I
OBJETIVOS

Entender las características matemáticas y conceptuales de un modelo de programación lineal.
Formulación de modelos de programación lineal.
Utilizar programas de computadora para resolver modelos de programación lineal.

II
TEMAS A TRATARConceptos básicos
Formulación del problema

III
MARCO TEORICO

Programación Lineal es una técnica cuantitativa ampliamente aplicada en sistemas que presentan relaciones lineales, para utilizar los recursos escasos de la mejor manera posibles.
La mejor manera de usar los recursos escasos se logra utilizando un modelo del sistema llamado Modelo de Programación Lineal.

El Modelo de Programación Lineal esun modelo matemático con variables de decisión, coeficientes y/o parámetros, restricciones y una función objetivo.

Es determinístico porque todos los datos relevantes utilizados, son conocidos. Es lineal porque las restricciones y el objetivo son funciones lineales. La contribución de cada variable al valor total del objetivo y al lado derecho de cada restricción es proporcional al valor de lavariable. Es aditivo porque los términos de sus restricciones y objetivo pueden sumarse (o restarse). La contribución de cada variable es independiente del valor de las otras variables. Es divisible porque las variables de decisión pueden aceptar valores fraccionales. En caso de no aceptar valores fraccionales, seria preferible usar Programación Lineal Entera.

La formulación y construcción delModelo Lineal implica:

a. Definir claramente las variables de decisión y expresarlas simbólicamente o convencionalmente.
b. Definir claramente la Función Objetivo y las restricciones y expresarlas matemáticamente como funciones lineales.

Se debe estipular que las variables de decisión sean mayores o iguales a cero. Esto acerca el modelo a la realidad. En los programas de computadora para resolvermodelos lineales, ya está incluida esta condición y no hace falta incorporarla manualmente.





IV
(La práctica tiene una duración de 2 horas) ACTIVIDADES

Ejemplo 1

Una escuela prepara una excursión para 400 alumnos. La empresa de transporte tiene 8 buses de 40 plazas y 10 buses de 50 plazas, pero solo dispone de 9 conductores. El alquiler de un bus grande cuesta 80 euros y el de uno pequeño,60 euros. Calcular cuántos de cada tipo hay que utilizar para que la excursión resulte lo mas económica posible para la escuela.
Solución
Es un problema de programación lineal, en este caso lo que queremos es hacer mínima la función objetivo. Queremos minimizar los costos.
Llamamos x al nº de buses de 40 plazas e y al nº de buses de 50 plazas que alquila la escuela.
Entonces se tiene   x <= 8 ,y <= 10, restricciones sobre el máximo número de buses disponibles.
Como sólo hay 9 conductores se verifica que: x + y <= 9
Como se tienen que llevar 400 alumnos, se debe de verificar:
40x + 50y >= 400, que simplificada quedaría 4x + 5y >= 40
Por lo tanto las restricciones que nos van a permitir calcular la  región factible (conjunto de puntos solución donde se cumplen todas las condiciones) sonLa función objetivo es F(x, y)= 60x+ 80y

Ejemplo 2

En una pastelería se hacen dos tipos de tartas: Vienesa y Real. Cada tarta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 250 Pts, mientras que una tarta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la pastelería se pueden hacer diariamente hasta 150Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tartas de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio?
Solución
En primer lugar hacemos una tabla para organizar los datos:

Tipo
Nº
Bizcocho
Relleno
Beneficio
T. Vienesa
x
1.x
0,250x
250x
T. Real
y
1.y
0,500y
400y
 
 
150
50
 
 ...