Unidad I
Unidad I
Unidad I
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Unidad I
Modelos Matemáticos:
Modelos Deterministas (MD) o lineales: se considera que los parámetros asociados al modelo son
conocidos con certeza absoluta
Modelos Estocásticos (ME).la totalidad o un subconjunto de los parámetros tienen una distribución de
probabilidad asociada.
Compontes del modelo: Un modelo matemático consta al menos de tres elementos o condiciones básicas:
1. Las Variables de decisión: son incógnitas que deben ser determinadas a partir de la
solución del modelo. Los parámetros representan los valores conocidos del sistema o que se
pueden controlar. Las variables de decisión se representan por: X1, X2, X3,…, Xn ó Xi, i =
1, 2, 3., n.
2. La Función Objetivo y las Restricciones:
o Función Objetivo: Es una relación matemática entre las variables de decisión,
parámetros y una magnitud que representa el objetivo o producto del sistema. Es la
medición de la efectividad del Modelo formulado en función de las variables.
Determina lo que se va optimizar (Maximizar o Minimizar).
La solución ÓPTIMA se obtiene cuando el valor de la Función Objetivo es óptimo
(valor máximo o mínimo), para un conjunto de valores factibles de las variables. Es
decir, hay que reemplazar las variables obtenidas X1, X2, X3,…, Xn; en la Función
Objetivo Z = f (C1X1, C2X2, C3X3,…, CnXn) sujeto a las restricciones del modelo
matemático.
1) Problema del Carpintero: Un carpintero comunica que sólo fabrica mesas y sillas y que vende todas
las mesas y las sillas que fabrica en un mercado. Sin embargo, no tiene un ingreso estable y desea
optimizar esta situación.
La función objetivo es: 5X1 + 3X2, donde X1 y X2 representan la cantidad de mesas y sillas; y 5 y 3
representan los ingresos netos (por ejemplo, en dólares o décimas de dólares) de la venta de una mesa y
una silla, respectivamente.
Los factores limitantes, que normalmente provienen del exterior, son las limitaciones de la mano de obra
(esta limitación proviene de la familia del carpintero) y los recursos de materia prima (esta limitación
proviene de la entrega programada). Se miden los tiempos de producción requeridos para una mesa y una
silla en distintos momentos del día y se calculan en 2 horas y 1 hora, respectivamente. Las horas laborales
totales por semana son sólo 40. La materia prima requerida para una mesa y una silla es de 1 y 2 unidades,
respectivamente. El abastecimiento total de materia prima es de 50 unidades por semana. En
consecuencia, la formulación de PL es la siguiente:
Maximizar 5 X1 + 3 X2
X1 + 2 X2 £ 50 restricción de materiales
Las variables de decisión, es decir, las entradas controlables son X1, y X2.
La salida o el resultado de este modelo son los ingresos netos totales 5 X1 + 3 X2.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Todas las funciones empleadas en este modelo son lineales (las variables de decisión están elevadas a la
primera potencia). El coeficiente de estas restricciones se denomina denomina Factores Tecnológicos
(matriz). El período de revisión es de una semana, un período conveniente dentro del cual es menos
probable que cambien (fluctúen) las entradas controlables (todos los parámetros tales como 5, 50, 2,..).
Incluso en un plazo de planificación tan corto, debemos realizar el análisis what-if o de hipótesis para
responder a cualquier cambio en estas entradas a los efectos de controlar el problema, es decir, actualizar
la solución prescripta.
Nótese que dado que el Carpintero no va a ir a la quiebra al final del plazo de planificación, agregamos las
condiciones que tanto X1 como X2 deben ser no negativas en lugar de los requerimientos que X1 y X2
deben ser números enteros positivos. Recuerde que las condiciones de no negatividad también se
denominan "restricciones implícitas". Nuevamente, un Programa Lineal funcionaría bien para este
problema si el Carpintero continúa fabricando estos productos. Los artículos parciales simplemente se
contarían como trabajos en proceso y finalmente se transformarían en productos terminados, en la
siguiente semana.
Programamos las actividades semanales del carpintero para que fabrique 10 mesas y 20 sillas.
Con esta estrategia (óptima), los ingresos netos son de US$110.Esta solución prescripta sorprendió al
carpintero dado que debido a los mayores ingresos netos provenientes de la venta de una mesa (US$5), el
solía fabricar más mesas que sillas.
Supóngase que el carpintero pudiera contratar a un ayudante a un costo de US$2 por hora (adicionales $2)
¿Le conviene al carpintero contratar a un ayudante? En caso afirmativo, ¿por cuántas horas?
Maximizar 5 X1 + 3 X2 - 2 X3
X1 + 2 X2 £ 50 restricción de materiales
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
En esta nueva condición, veremos que la solución óptima es X1 = 50, X2 = 0, X3 = 60, con ingresos netos
óptimos de US$130. Por lo tanto, el carpintero debería contratar a un ayudante por 60 horas.
2) Problema de Mezcla: El taller de Joe se especializa en cambios de aceite del motor y regulación del
sistema eléctrico. El beneficio por cambio del aceite es $7 y de $15 por regulación. Joe tiene un cliente
fijo con cuya flota, le garantiza 30 cambios de aceite por semana. Cada cambio de aceite requiere de 20
minutos de trabajo y $8 de insumos. Una regulación toma una hora de trabajo y gasta $15 en insumos. Joe
paga a los mecánicos $10 por hora de trabajo y emplea actualmente a dos de ellos, cada uno de los cuales
labora 40 horas por semana. Las compras de insumos alcanzan un valor de $1.750 semanales. Joe desea
maximizar el beneficio total. Formule el problema.
Esto es una pregunta de programación lineal. Una porción de un cambio del aceite o del ajuste no es
factible.
X2 = Ajuste
X1 ³ 0, X2 ³ 0.
El coste de trabajo de $10 por hora no se requiere para formatar el problema desde el beneficio por cambio
del aceite y el ajuste toma en la consideración el coste d
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Conj
unto
conve
xo N
dime
nsion
es
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
X+y=2
Conjunto convexo en N dimensiones: a esta familia pertenecen los Polígonos, poliedros y politopos
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Un politopo es: es una figura plana convexa cuyos lados y esquinas son iguales.
En todo problema de programación lineal hay que tomar ciertas decisiones. Estas se
representan con variables de decisión que se utilizan en el modelo de programación lineal. La
estructura básica de un problema de este tipo es maximizar o minimizar la función objetivo,
satisfaciendo al mismo tiempo un grupo de condiciones restrictivas o restricciones (que
limitan el grado en que se puede perseguir algún objetivo).
la función objetivo: En un problema de programación lineal, la función por maximizar o
minimizar se llama función objetivo. Aunque por lo regular existe un número infinito de
soluciones para el sistema de restricciones (llamadas soluciones factibles o puntos factibles),
la meta es encontrar una que sea una solución óptima (esto es, una que dé el valor máximo
o mínimo de la función objetivo).
Restricciones estructurales y restricciones de no negatividad. Son limitaciones impuestas al
grupo de decisiones permisibles
Existen 2 tipos de restricciones:
1. Restricciones estructurales: reflejan factores como la limitación de recursos y otras
situaciones que impone la situación del problema.
2. Restricciones de no negatividad: garantizan que ninguna variable de decisión sea
negativa.
Caso 1: Un fabricante está tratando de decidir sobre las cantidades de producción para dos
artículos x1 y x2.
Determinar la cantidad a producir y vender de cada artículo que garanticen mayores beneficios.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Si la restricción tiene el signo ≥se sombrea a la derecha y por encima de la línea, pero si el signo es ≤
se subraya a la izquierda por debajo del gráfico de la línea recta. La región que satisface demanera
simultanea las restricciones ya sombreada se llama área o región factible, donde cada punto en esta
región representa una solución factible. Aunque existe un numero infinito de soluciones factibles,
debemos encontrar una que maximice o minimice la función objetivo.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Esta área factible tiene los siguientes vértices (8,0), (6,3), (2,0) y (2,5). Es preciso aclarar que cualquier
punto que caiga dentro del área factible garantiza beneficios, pero son los puntos extremos o vértice de
la figura lo que garantizarían máximos beneficios.
El mayor valor es $45 lo que implica que habrá que vender 6 unidades del producto x1 y 3
producto x2. Si pretendemos obtener los mayores beneficios.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Ejemplo 2:
Un comprador está tratando de seleccionar la combinación más barata de dos alimentos, que debe
cumplir con ciertas necesidades diarias de vitaminas.
Los requerimientos vitamínicos son por lo menos 40 unidades de vitaminas W, 50 unidades de vitamina X
y 49 de unidades vitaminas Y, cada onza de alimento A proporciona 4 unidades de vitamina W, 10
unidades de vitamina X y unidades de vitamina Y, cada onza de alimento B proporciona 10
unidades de W, 5 unidades de X y 7 unidades de unidades Y. El alimento A cuesta 5 centavos/onza y el
alimento B 8 centavos/onza.
Si la restricción tiene el signo ≥se sombrea a la derecha y por encima de la línea, pero si el signo es ≤
se subraya a la izquierda por debajo del gráfico de la línea recta. La región que satisface de manera
simultánea las restricciones ya sombreada se llama área o región factible, donde cada punto en esta
región representa una solución factible. Aunque existe un número infinito de soluciones factibles,
debemos encontrar una que maximice o minimice la función objetivo
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
El menor costo a que se podría comprar es a $41, pero esto implicaría 4.2 onzas del producto A y
2.5 onzas del producto B y se mantendría el nivel vitamínico
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
¿Qué número de pantalones y chaquetas debe suministrar el fabricante a los almacenes para que
estos consigan un beneficio máximo?
y = número de chaquetas
Restricciones
2x + y ≤ 1000
restricciones más:
x≥0 y≥0
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Representamos las rectas, a partir de sus puntos de corte con los ejes.
Resolvemos gráficamente la inecuación: x + 1.5y ≤ 750, para ello tomamos un punto del plano,
por ejemplo el (0,0).
0 + 1.5· 0 ≤ 750
0 ≤ 750
2x + y ≤ 1000.
2 · 0 + 0 ≤ 1 000
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. Estas son las soluciones a
los sistemas:
2x + y = 1000; y = 0 (500, 0)
Con el comienzo del curso se va a lanzar unas ofertas de material escolar. Unos almacenes
quieren ofrecer 600 cuadernos, 500 carpetas y 400 bolígrafos para la oferta, empaquetándolo de
dos formas distintas; en el primer bloque pondrá 2 cuadernos, 1 carpeta y 2 bolígrafos; en el
segundo, pondrán 3 cuadernos, 1 carpeta y 1 bolígrafo. Los precios de cada paquete serán 6.5 y 7
€, respectivamente. ¿Cuántos paquetes le conviene poner de cada tipo para obtener el máximo
beneficio?
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Soluciones factibles
En un espacio unidimensional (como una recta), un hiperplano es un punto: divide una línea
en dos líneas. En un espacio bidimensional (como el plano xy), un hiperplano es una recta:
en dos mitades. Este concepto también puede ser aplicado a espacios de cuatro
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
con el plano.
desde un punto de vista geométrico. Son conjuntos convexos aquellos que tienen la propiedad de
que al unir con un segmento dos puntos cualesquiera del conjunto, el segmento queda
Ejemplos:
Para comprender mejor la definición de conjunto convexo debe tenerse en cuenta que dados
dos puntos X y Y, los puntos de la forma corresponden justamente con los puntos del
Por tanto, un conjunto es convexo cuando el segmento que une cualquier par de puntos del
puntos del segmento lineal que une cualquiera dos puntos del conjunto, pertenecen también al
conjunto.
Un politopo tiene lados planos que encierran un área. Un politopo en un plano se llama un
polígono
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Los poliedros y polígonos, por lo tanto, son subconjuntos de politopos. Existen numerosos
3. Formulación de modelos.
capacidades de almacenamiento en sus bodegas de popa, centro y proa. Los dueños del
barco pueden elegir una porción o toda la carga de los productos A, B y C, cuyas
debe cumplirse con una carga proporcional a la capacidad de las respectivas bodegas.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Definición de variables:
Función objetivo:
Sujeto a restricciones:
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
proporcionales.
x = progreso de la actividad
Requerimientos.
Costos
Utilidades.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
4) Certidumbre. Todos los parámetros que se manejan deben ser pasados con certeza.
Una empresa ha dejado de fabricar ciertos productos, liberando de esta forma las cargas de
producción que tenían sus equipos en los departamentos de maquinado. Ahora se tienen
horas máquina que se pueden utilizar en los productos denominados 1,2,3 de la siguiente
manera:
Definición de variables:
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Función objetivo:
Restricciones:
Función objetivo: La función objetivo es la ecuación que será optimizada dadas las
investigación o de optimización.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Optimización: se tratará de encontrar una solución que represente el valor óptimo para una
función objetivo.
En el caso más sencillo se tendrá un único objetivo, que estará representado por una función del
tipo , donde y . Tanto el dominio como la imagen de la función serán números reales (escalares),
y el valor óptimo corresponderá a un mínimo o a un máximo.
Según su relación con la realidad que pretenden representar se pueden encontrar las
un conjunto de recursos/productos/operaciones.
en cada momento.
2. Aditividad: elimina la posibilidad de que existan productos cruzados (términos que incluyen el
producto de dos o más variables). Cada función de un modelo de programación lineal (función
objetivo o lado izquierdo de las restricciones funcionales) es la suma de las contribuciones
individuales de las actividades respectivas
Para entender mejor este supuesto: Ej.: dos productos complementarios por ejemplo en el caso
4. Certidumbre: Se refiere a los parámetros del modelo, es decir a los coeficientes cj en la función
objetivo y bi en el lado derecho de las restricciones funcionales y los coeficientes ai en las
restricciones funcionales. Se supone que los valores asignados a cada parámetro de un modelo
de programación lineal son constantes conocidas
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
Referencias:
https://books.google.com.co/books?id=UATsv3bgBwcC&pg=PA24&dq=conjunto+convexo+2+d
imensiones&hl=es-
419&sa=X&ei=aO2JVJGaJtHkggSb8ILoDA&ved=0CB4Q6AEwAQ#v=onepage&q=conjunto%
20convexo%202%20dimensiones&f=false
https://books.google.com.co/books?id=cGLZ7W0BzQoC&pg=PA25&lpg=PA25&dq=conjunto+c
onvexo+en+n+dimensiones&source=bl&ots=gy7eaIxhb6&sig=3jf7Gi4tkfXHQwJM95YJ-
wig7Dw&hl=es-
419&sa=X&ei=5uyJVJrAGoicNtW_gegF&ved=0CBsQ6AEwAA#v=onepage&q=conjunto%20c
onvexo%20en%20n%20dimensiones&f=false
https://books.google.com.co/books?id=cGLZ7W0BzQoC&pg=PA25&lpg=PA25&dq=conjunto+c
onvexo+en+n+dimensiones&source=bl&ots=gy7eaGwlcd&sig=lBLcPJ7BZcjHXt8EpjYjPRZlK0
Q&hl=es-
419&sa=X&ei=f5yJVPXkFY3mggTvnYSgBw&ved=0CBsQ6AEwAA#v=onepage&q=conjunto
%20convexo%20en%20n%20dimensiones&f=false
http://buscador.rincondelvago.com/formulacion+de+modelos
http://catarina.udlap.mx/u_dl_a/tales/documentos/mcc/cruz_m_ia/capitulo2.pdf
http://catarina.udlap.mx/u_dl_a/tales/documentos/mcc/cruz_m_ia/capitulo2.pdf
http://www.enciclopediafinanciera.com/definicion-funcion-objetivo.html
http://www.bdigital.unal.edu.co/5037/4/guillermojimenezlozano.2006_Parte1.pdf
http://es.wikipedia.org/wiki/Convexidad_(econom%C3%ADa)
http://es.wikipedia.org/wiki/Envolvente_convexa
http://es.wikipedia.org/wiki/Hiperplano
http://es.wikipedia.org/wiki/Lenguaje_orientado_a_objetos
http://es.wikipedia.org/wiki/Optimizaci%C3%B3n_multiobjetivo
http://es.wikipedia.org/wiki/Optimizaci%C3%B3n
http://es.wikipedia.org/wiki/Poliedro
http://es.wikipedia.org/wiki/Pol%C3%ADgonos
http://es.wikipedia.org/wiki/Politopo_regular
http://es.wikipedia.org/wiki/Restricci%C3%B3n
https://www.google.com.co/search?q=restricciones+investigacion+de+operaciones&biw=1311&b
ih=570&tbm=vid&source=lnms&sa=X&ei=P_SJVKeAPMSeNsiKgtAG&ved=0CAkQ_AUoAg
&dpr=1
http://tecdigital.tec.ac.cr/file/5017886/supuestosmodeloPL.pdf
http://www.ugr.es/~jperez/docencia/GeomConvexos/cap1.pdf
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos
http://www.virtual.unal.edu.co/cursos/sedes/medellin/3007324/und_1/html/tema_02/contenido_02
.html
http://www.virtual.unal.edu.co/cursos/sedes/manizales/4060014/html/Capitulo%20I/cconvexos.ht
m
http://www.virtual.unal.edu.co/cursos/sedes/manizales/4060014/html/descripcion.html
http://www.vitutor.com/algebra/pl/a_3.html
http://www.vitutor.com/algebra/pl/a_a.html
http://webs.um.es/mhcifre/apuntes/cap1.pdf