Unidad I

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 37

Materia: Investigación de Operaciones

UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Unidad I

Programación Lineal y Conceptos Matemáticos Básico


Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Aplica conceptos matemáticos básicos para formular modelos de programación lineal.

LA PROGRAMACION LINEAL: Es un procedimiento o algoritmo matemático mediante el


cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones
lineales, optimizando la función objetivo, también lineal.

La Programación Lineal: Es un tipo especial de


Programación Entera donde las variables sólo pueden
adoptar 0 o 1.

Es una de las herramientas más utilizadas en la


Investigación Operativa debido a que por su
naturaleza se facilitan los cálculos y en general
permite una buena aproximación de la realidad.

Programación lineal: Conceptos Matemáticos Básicos

La programación lineal es una técnica de programación matemática para resolver problemas de


optimización de recursos (maximización, minimización) cuando existe más de una restricción
lineal.

Características principales del modelo:


 Buscar una combinación de recursos.
 Satisfacer varios criterios.
 Identificar un criterio como el objetivo
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

La programación lineal es la interrelación de los componentes de un sistema, en términos matemáticos,


ya sea en forma de ecuaciones o inecuaciones lineales llamado Modelo de Programación Lineal. Es una
técnica utilizada para desarrollar modelos matemáticos, diseñada para optimizar el uso de los recursos
limitados en una empresa u organización.

Es una representación simbólica de la realidad que se estudia,


o del problema que se va a solucionar. Se forma con
expresiones de lógicas matemáticas, conteniendo términos
que significan contribuciones: a la utilidad (con máximo) o al
costo (con mínimo) en la Función Objetivo del modelo. Y al
consumo de recursos disponibles (con desigualdades = ó = e
igualdades =) en las restricciones.

Ubicación en la rama de la matemática


Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

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.

El objetivo de un modelo de programación lineal es: Maximización y Minimización, basados en la


Función Objetivo del Modelo
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

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.

Por ejemplo, si el objetivo es minimizar los costos de operación, la función objetivo


debe expresar la relación entre el costo y las variables de decisión, siendo el
resultado el menor costo de las soluciones factibles obtenidas.
o Restricciones: Las restricciones son relaciones entre las variables de decisión y los
recursos disponibles. Las restricciones del modelo limitan el valor de las variables de
decisión. Se generan cuando los recursos disponibles son limitados.
En el Modelo se incluye, adicionalmente de las restricciones, la Restricción de No
Negatividad de las Variables de decisión, o sea: Xi = 0.
Por ejemplo, si una de las variables de decisión representa el número de empleados
de un taller, el valor de esa variable no puede ser negativo. O también, si una de las
variables es la cantidad de mesas a fabricar, su valor solamente podrá ser igual a cero
ó mayor que cero, o sea positivo; sería absurdo obtener como resultado que se va a
fabricar – 4 mesas.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Problemas de aplicación para formular un modelo

FINANZAS: el problema del inversor podría ser un problema de


selección del mix de su cartera de inversiones. En general, la variedad de
carteras puede ser mucho mayor que lo que indica el ejemplo y se pueden
agregar muchas más restricciones distintas. Otro problema de decisión
implica determinar la combinación de métodos de financiación para una
cantidad de productos cuando existe más de un método de financiación
disponible. El objetivo puede ser maximizar las ganancias totales
cuando las ganancias de un producto determinado dependen del método
de financiación. Por ejemplo, se puede financiar con fondos internos,
con deuda a corto plazo o con financiación intermedia (créditos
amortizados). Puede haber limitaciones con respecto a la disponibilidad
de cada una de las opciones de financiación, así como también
restricciones financieras que exijan determinadas relaciones entre las
opciones de financiación a los efectos de satisfacer los términos y
condiciones de los préstamos bancarios o financiación intermedia.
También puede haber límites con respecto a la capacidad de producción
de los productos. Las variables de decisión serían la cantidad de
unidades que deben ser financiadas por cada opción de financiación.

Administración de Producción y Operaciones: muchas veces en las


industrias de proceso, una materia prima en particular puede
transformarse en una gran variedad de productos. Por ejemplo, en la
industria petrolera, el crudo puede refinarse para producir nafta,
kerosene, aceite para calefaccionar y distintas clases de aceite para
motor. Según el margen de ganancia actual de cada producto, el
problema es determinar la cantidad que se debería fabricar de cada
producto. Esta decisión está sujeta a numerosas restricciones tales
como límites de las capacidades de diversas operaciones de refinado,
disponibilidad de materia prima, demandas de cada producto y
políticas gubernamentales con respecto a la fabricación de
determinados productos. En la industria de productos químicos y de
procesamiento de alimentos existen problemas similares.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Recursos Humanos: los problemas de planificación


del personal también se pueden analizar con
programación lineal. Por ejemplo, en la industria
telefónica, la demanda de servicios de personal de
instalación / reparación son estacionales. El
problema es determinar la cantidad de personal de
instalación / reparación y reparación de líneas que
debemos tener incorporada en la fuerza laboral por
cada mes a fin de minimizar los costos totales de
contratación, despido, horas extras y salarios en
horas ordinarias. El conjunto de restricciones
comprende restricciones con respecto a la demanda
de servicio que se debe satisfacer, uso de horas extra, acuerdos con los sindicatos y la disponibilidad de
personal calificado para contratar. Este ejemplo es opuesto a la hipótesis de divisibilidad. Sin embargo, los
niveles de fuerza laboral de cada mes normalmente son lo suficientemente altos como para poder
redondear al número entero más cercano sin problemas, siempre y cuando no se violen las restricciones.

Marketing: Se puede utilizar la programación lineal para


determinar el mix adecuado de medios de una campaña de
publicidad. Supóngase que los medios disponibles son radio,
televisión y diarios. El problema es determinar cuántos
avisos hay que colocar en cada medio. Por supuesto que el
costo de colocación de un aviso depende del medio elegido.
El objetivo es minimizar el costo total de la campaña
publicitaria, sujeto a una serie de restricciones. Dado que
cada medio puede proporcionar un grado diferente de
exposición a la población meta, puede haber una cota
inferior con respecto a la exposición de la campaña.
Asimismo, cada medio puede tener distintos ratings de
eficiencia para producir resultados deseables y por
consiguiente puede haber una cota inferior con respecto a la eficiencia. Además, puede haber límites con
respecto a la disponibilidad para publicar en cada medio.

Distribución: otra aplicación de programación lineal es el área de la


distribución. Considere un caso en el que existen m fábricas que deben
enviar productos a n depósitos. Una determinada fábrica podría realizar
envíos a cualquier cantidad de depósitos. Dado el costo del envío de una
unidad del producto de cada fábrica a cada depósito, el problema es
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

determinar el patrón de envío (cantidad de unidades que cada fábrica


envía a cada depósito) que minimice los costos totales. Este decisión está
sujeta a restricciones que exigen que cada fábrica no pueda enviar más
productos de los que tiene capacidad para producir.

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.

Función objetivo: Maximizar sus ingresos netos.

Determinar cuántas mesas y sillas debería fabricar Comenzamos concentrándonos en un horizonte de


tiempo, es decir, un plazo de planificación, para revisar nuestra solución semanalmente, si fuera necesario.
Para saber más acerca de este problema, debemos ir al negocio del carpintero y observar lo que sucede y
medir lo que necesitamos para para formular (para crear un modelo de) su problema. Debemos confirmar
que su objetivo es maximizar sus ingresos netos. Debemos comunicarnos con el cliente.

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

Sujeta a: 2 X1 + X2 £ 40 restricción de mano de obra

X1 + 2 X2 £ 50 restricción de materiales

tanto X1 como X2 son no negativas.

Este es un modelo matemático para el problema del carpintero.

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.

La solución óptima, es decir, la estrategia óptima, es establecer X1 = 10 mesas y X2 = 20 sillas.

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.

¿Contratar o no contratar a un ayudante?

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?

X3 es la cantidad de horas extra, entonces el problema modificado es:

Maximizar 5 X1 + 3 X2 - 2 X3

Sujeta a: 2 X1 + X2 £ 40 + X3 restricción de la mano de obra con horas adicionales desconocidas

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.

X1 = Cambios del aceite, ajuste

X2 = Ajuste

Maximizar 7X1 + 15X2

Sujeta a: X1 ³ 30 Cuenta De la Flota

20X1 + 60X2 £ 4800 De trabajo tiempo

8X1 + 15X2 £ 1750 Primas Materias

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

Identifica conjuntos convexos en distintas dimensiones.

Conjuntos o regiones convexas: Un conjunto de puntos es llamado un conjunto convexo si todos


los puntos del segmento lineal que une cualesquiera dos puntos del conjunto, pertenecen también
al conjunto.

Conjunto convexo 2 dimensiones

Conj
unto
conve
xo N
dime
nsion
es
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Conjunto convexo en 2 dimensiones:


Es llamado un conjunto convexo, si todos los puntos del segmento lineal que une cualquiera dos
puntos del conjunto, pertenecen también al conjunto.

En el espacio de dos dimensiones consideremos el conjunto (x,y) que satisfacen la


relación x+y 2 este conjunto de puntos es un conjunto convexo. En efecto,
sabemos que el conjunto correspondiente al semiplano limitado por la recta

X+y=2

Gráficamente es el semiplano rayado

Otros ejemplos de conjuntos convexos en 2 dimensiones:

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

Dentro de la familia de conjuntos convexos en , la familia más sencilla son los


politopos. Este concepto es la generalización a n dimensiones del concepto clásico

de polígono convexo en o de poliedro convexo en

Polígono: si tiene todos sus ángulos


internos menores que 180º. O bien, si
un segmento que une dos puntos
cualesquiera del polígono yace en el
interior de este.

Un politopo es: es una figura plana convexa cuyos lados y esquinas son iguales.

Un politopo es la generalización del concepto polígono (2D), o poliedro (3D) a


cualquier dimensión.

Un poliedro: es aquel que tiene caras y


ángulos iguales, por ejemplo un cubo o
hexaedro (seis caras). El cubo posee seis
polígonos con lados iguales con la misma
longitud, éstos a su vez se unen en vértice
con ángulos de 90º grados
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Formula modelos de programación lineal para la toma de decisiones:

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.

Se dispone de 96 unidades de material y 72 horas de mano de obra.


Producto x1 requiere 12 unidades de materiales y 6 horas de obra al máximo.
Producto x2 usaría 8 unidades de material y 12 horas de mano de obra.
El margen de beneficio esel mismo para ambos artículos US$5.
El fabricante prometió construir por lo menos dos artículos del producto x1

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.

Determinar la combinación que disminuirá los costos:


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 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

Construya funciones: objetivo, conociendo sus variables y restricciones.

Ejemplo 1: Fabricación Unos grandes almacenes encargan a un fabricante pantalones y


chaquetas deportivas. El fabricante dispone para la confección de 750 m de tejido de algodón y
1000 m de tejido de poliéster. Cada pantalón precisa 1 m de algodón y 2 m de poliéster. Para cada
chaqueta se necesitan 1.5 m de algodón y 1 m de poliéster.

El precio del pantalón se fija en 50 € y el de la chaqueta en 40 €.

¿Qué número de pantalones y chaquetas debe suministrar el fabricante a los almacenes para que
estos consigan un beneficio máximo?

Elección de las incógnitas. x = número de pantalones

y = número de chaquetas

Función objetivo f(x,y)= 50x + 40y

Restricciones

x + 1.5y ≤ 750 2x+3y ≤ 1500

2x + y ≤ 1000

Como el número de pantalones y chaquetas son números naturales, tendremos dos

restricciones más:

x≥0 y≥0
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

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: x + 1.5y ≤ 750, para ello tomamos un punto del plano,
por ejemplo el (0,0).

0 + 1.5· 0 ≤ 750

0 ≤ 750

Entonces el punto (0,0) se encuentra en el semiplano donde se cumple la desigualdad.

De modo análogo resolvemos

2x + y ≤ 1000.

2 · 0 + 0 ≤ 1 000

La zona de intersección de las soluciones de las


inecuaciones sería la solución al sistema de
inecuaciones, que constituye el conjunto de las
soluciones factibles.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

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 + 3y = 1500; x = 0 (0, 500)

2x + y = 1000; y = 0 (500, 0)

2x + 3y =1500; 2x + y = 1000 (375, 250)

Calcular el valor de la función objetivo

En la función objetivo sustituimos cada uno de los vértices.

f(x, y) = 50x + 40y

f(0, 500) = 50 · 0 + 40 · 500 = 20 000 €

f(500, 0) = 50 · 500 + 40 · 0 = 25 000 €

f(375, 250) = 50 · 375 + 40 · 250 = 28 750 € Máximo

La solución óptima es fabricar 375 pantalones y 250 chaquetas


Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Para obtener un beneficio de 28750 €.

Ejemplo 2: oferta escolar

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

La solución óptima son 150 P1 y 100 P2 con la que se obtienen 1 675 €

Hiperplanos conjuntoso regiones convexas :

Un Hiperplano: es una extensión del concepto de plano.

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:

divide el plano en dos mitades.

ver video de apoyo

En un espacio tridimensional, un hiperplano es un plano corriente: divide el espacio

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

dimensiones y más, donde estos objetos divisores se llaman simplemente

hiperplanos, ya que la finalidad de esta nomenclatura es la de relacionar la geometría

con el plano.

Conjuntos o regiones convexas: El concepto de conjunto convexo es algo sencillo de entender

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

completamente contenido en el propio conjunto.

Un conjunto S es convexo cuando: X, Y S y [0,1] se cumple: X+(1-) Y S

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

segmento que une X y Y.

Por tanto, un conjunto es convexo cuando el segmento que une cualquier par de puntos del

conjunto está completamente contenido en el conjunto.


Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

1. Conjuntos convexos en dos dimensiones: Es llamado un conjunto convexo, si todos los

puntos del segmento lineal que une cualquiera dos puntos del conjunto, pertenecen también al

conjunto.

En el espacio de dos dimensiones consideremos el conjunto (x,y) que satisfacen la


relación x+y 2 este conjunto de puntos es un conjunto convexo. En efecto,
sabemos que el conjunto correspondiente al semiplano limitado por la recta

2. Conjuntos convexos en “n” dimensiones:

Cuando pasamos de 2 dimensiones, nos encontramos con figuras o formas geométricas

como Los polígonos, poliedros y politopos, estas figuras conforman el conjunto el

conjunto convexo en N dimensiones.

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

Un politopo en el espacio tridimensional, un poliedro.

Los poliedros y polígonos, por lo tanto, son subconjuntos de politopos. Existen numerosos

tipos de politopos, polígonos y poliedros. Las características importantes para la

clasificación incluyen caras, lados, vértices, convexidad y facetas.

3. Formulación de modelos.

1. Problema de almacenamiento en el transporte: Un barco tiene las siguientes

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

características se tabulan a continuación. Además, para preservar el equilibrio del barco

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:

xij = toneladas del producto j (j = A,B,C) a cargar en la bodega i (i = 1,2,3)

para maximizar la utilidad en el viaje

Función objetivo:

Sujeto a restricciones:
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Propiedades que debe de seguir el modelo de programación lineal.

1) Proporcionalidad. En el modelo de programación lineal los pagos deben ser

proporcionales.

El modelo de programación lineal es estático, plantea una situación del momento.

x = progreso de la actividad

2) Aditividad. Siempre los pagos se suman.

Requerimientos.

Costos

Utilidades.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

3) Divisibilidad. Las variables involucradas en el modelo de programación lineal

pueden no ser un número entero

Si los valores son muy pequeños no importa el redondeo.

Si son muy altos afecta el redondeo.

4) Certidumbre. Todos los parámetros que se manejan deben ser pasados con certeza.

Ejemplo 2: Ejemplo de producción:

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:

Formulación un modelo de P.L para este problema

Definición de variables:
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Función objetivo:

Restricciones:

4. Función objetivo. Optimización. Restricciones.

Función objetivo: La función objetivo es la ecuación que será optimizada dadas las

limitaciones o restricciones determinadas y con variables que necesitan ser minimizadas o

maximizadas usando técnicas de programación lineal o no lineal. Una función objetivo

puede ser el resultado de un intento de expresar un objetivo de negocio en términos

matemáticos para su uso en el análisis de toma de decisiones, operaciones, estudios de

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.

Ejemplo: Al minimizar la función el valor óptimo es,


y se da para, según puede verse en la figura 1.
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

Restricciones: Las restricciones son expresiones de relaciones entre variables. Dichas


relaciones se representan mediante restricciones en la programación matemática, y tienen
la formulación de una combinación lineal de variables limitada por un determinado valor.

Las restricciones se pueden clasificar en función de la realidad que pretenden representar,

o en función de su relación con el resto del modelo matemático.

Según su relación con la realidad que pretenden representar se pueden encontrar las

encontrar entre otras:

o Restricciones de capacidad. Se limita el consumo de capacidad productiva de

un conjunto de recursos/productos/operaciones.

o Disponibilidad de Materia Prima. Se limita el consumo de un

determinado conjunto de productos (y en consecuencia la producción de

un conjunto de productos) según la cantidad de materia prima disponible

en cada momento.

o Limitaciones en la demanda del mercado. Se limita la producción de

un producto en función de la venta estimada de éste


Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

5. Supuestos de Programación Lineal.

1. Proporcionalidad: Es un supuesto sobre la función objetivo y sobre las restricciones.

La contribución de cada actividad al valor de la función objetivo Z es proporcional al

nivel de la actividad xj como lo representa el término cjxj en la función objetivo.

Este supuesto elimina cualquier exponente diferente de 1 para las variables en

cualquier término de las funciones (función objetivo o en el lado izquierdo de las

restricciones funcionales) en un modelo de programación lineal.

Para entender mejor este supuesto:

Basados en el ejemplo de Ejemplo Prototipo: La Wyndor Glass Co el primer término

de la función objetivo representa la ganancia en miles de

dólares al producir el producto 1, se supuso que la ganancia es proporcional a por

lo que . es el apropiado para la función objetivo.

Si al producir este nuevo producto la empresa tuviera que

incurrir en una inversión inicial por ejemplo de su propio

capital, se podría posteriormente “amortizar” esa inversión

restándola poco a poco de la ganancia en los primeros

periodos así por ejemplo se podría decir que la ganancia

Esto implicaría una función de ganancias no proporcional.

Cuando el supuesto de proporcionalidad no se cumple con: una Programación no lineal, sede


reelaborar el problema de programación lineal y se presenta programación entera mixta
Materia: Investigación de Operaciones
UNIDAD I:
Programación Lineal y Conceptos Matemáticos Básicos

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

de La Wyndor Glass Co si:

En caso de violación de este supuesto se debe recurrir a la programación no lineal.

3. Divisibilidad: Sobre los valores para las variables de decisión:


o Las variables de decisión pueden tomar cualquier valor incluso no enteros, que
satisfagan las restricciones funcionales y de no negatividad. En consecuencia estas
variables no están restringidas solo a valores enteros.
o Como cada variable de decisión esta representa el nivel de alguna actividad se
supondrá que las actividades se pueden realizar a niveles
o Cuando exista restricción de valores enteros para algunas o todas las variables de
decisión se debe usar la programación entera.

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

En problemas reales el supuesto de certidumbre casi nunca se satisface por


completo.

Generalmente se formula un modelo de programación lineal para elegir un curso de Acción


futuro, los valores de los parámetros que se emplean están basados en una predicción de
condiciones futuras por lo que inevitablemente se introduce cierto grado de incertidumbre.

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

También podría gustarte