investigacion 2

INVESTIGACIÓN DE OPERACIONES I

PROGRAMA DE ESTUDIO

Objetivo

Familiarizar al alumno con las técnicas de modelamiento y metodologías de resolución de problemas de la Investigación de operaciones, con especial énfasis en la aplicación de algoritmos de solución para modelos de programación matemática, en especial modelos lineales

Contenido

Introducción • Investigación de operaciones• Modelos matemáticos• Programación Lineal

ProgramaciónLineal

• Formulación de modelos• Métodos Gráfico• Método Simplex• Problema Dual y Análisis de Sensibilidad• Programación Entera, Binaria y Mixta

INVESTIGACION DE OPERACIONESPROGRAMA DEL CURSO

DESCRIPCION

El curso trata principalmente sobre la aplicación de los modelos usuales de Investigación de Operaciones en la solución de problemas reales, tales como modelos de Programación Lineal, Entera, Binaria y Mixta

OBJETIVOS• Aplicar modelos cuantitativos en la resolución de problemas

lineales.• Optimizar soluciones usando la Investigación de Operaciones.

METODOLOGÍA• Clases expositivas para conceptos teóricos con discusiones sobre

cada tema.

• Practicas en laboratorio, donde se conocerán diversos software de apoyo a la Investigación de Operaciones.

BIBLIOGRAFIA

• TAHA HAMDY A. Investigación de operaciones. PEARSON. 9 Ed. 2012

• HILLIER, FREDERICK Y LIEBERMAN, GERALD: “Introducción a la Investigación de Operaciones”, McGraw – Hill Interamericana

• WINSTON WAYNE L.: “Investigación de Operaciones: Aplicaciones y Algoritmos”. Grupo Editorial Iberoamericana.

• DAVIS K ROSCOE y MC KEOWN Patrick. Modelos Cuantitativos para Administración. Grupo editorial Iberoamerica. 2 Ed. 1986.

• PRAWDA, Juan. Métodos y modelos de Investigación de operaciones. Limusa.

• JORGE ALVAREZ ALVAREZ, Investigación de Operaciones, Universidad Nacional de Ingeniería, Edición 2001

INVESTIGACION DE OPERACIONES

Definición:Conjunto de técnicas matemáticas y estadísticas aplicable a diversos sistemas con el fin de mejorarlos, buscando las mejores alternativas de acción; esto mediante el modelamiento matemático de los problemas en estudio.

¿Qué es la investigación de operaciones?

Lawrence y Pasternak, (1998) “Es un enfoque científico para la toma de decisiones ejecutivas, que consiste en:

• El arte de modelar situaciones complejas,• La ciencia de desarrollar técnicas de

solución para resolver dichos modelos.• La capacidad de comunicar efectivamente

los resultados”.

Kamblesh Mathur: “Es el uso de la Matemática y computadoras para ayudar a tomar decisiones racionales frente a problemas de administración”.

Jorge Alvarez: “Es un procedimiento o un enfoque para resolver problemas relacionados con la toma de decisiones”.

¿Qué es la investigación de operaciones?

La Investigación de Operaciones es el uso de la matemática e informática para resolver problemas del mundo real, tomando decisiones acertadas que garanticen el éxito.

La investigación de operaciones tiene como objetivo buscar las soluciones que sean significativamente mas eficientes (en tiempo, recursos , beneficios , costos , etc.)

Toda toma de decisión empieza con la detección de un problema.

Definir el problema en forma clara

Identificar las restricciones

Identificar las alternativas de solución

Formular el o los objetivos

Evaluar las alternativas y elegir la mejor

Para tomar la decisión correcta, se debe:

TOMA DE DECISIONES

Tiende a representar el problema cuantitativamente para poder analizarlo y evaluar un criterio común.

¿Como se elige la mejor alternativa?

Métodos Cualitativos

Métodos Cuantitativos

En base a la experiencia y al juicio profesional de la persona que toma la decisión

En base a la utilización de herramientas matemáticas que permitan maximizar la efectividad en la toma de decisiones.

TOMA DE DECISIONES

La dificultad de tomar decisiones ha hecho que el hombre se aboque en la búsqueda de una herramienta o método que le permita tomar las mejores decisiones de acuerdo a los recursos disponibles y a los objetivos que persigue.

Este conjunto de herramientas o métodos es lo que llamaremos Investigación de Operaciones.

“Enfoque científico de la toma de decisiones que requiere la operación de sistemas organizacionales”.

Definición más formal

La IO nos ofrece una serie de herramientas cuantitativas para la toma de decisiones.

INVESTIGACIÓN DE OPERACIONES

Modelos de IO

Programación Lineal

MétodosClásicos

Determinísticos Híbridos Estocásticos

Transporte yAsignación

Prog Enteray 0,1

Optimización Lineal

Optimización no Lineal

Métodosde búsqueda

Programación no lineal

ProgramaciónDinámica

Teoría de Inventarios

Simulación

Pert / CPM

Heurísticas

Cadenas de Markov

Teoría de Colas

ProcesosEstocásticos

Teoría de Decisionesy Juegos

MODELOS DE LA INVESTIGACIÓN DE OPERACIONES

¿Qué se busca en el curso de Investigación de Operaciones?

Se intenta encontrar una mejor solución llamada solución óptima.

Areas de Aplicación de la Investigación de Operaciones

Manufactura.

Transporte.

Telecomunicaciones.

Salud.

Planeación.

Servicios.

Finanzas.

Otros.

LA NATURALEZA DE UN SISTEMA

Un sistema es un conjunto de dos o más elementos que satisface las siguientes tres condiciones:

• La conducta de cada elemento tiene un efecto sobre la conducta del todo.

• La conducta de los elementos y sus efectos sobre el todo son interdependientes.

• Sin considerar cómo se formen los subgrupos de elementos, cada uno tiene un efecto sobre la conducta del todo, y ninguno tiene un efecto independiente sobre él.

• Proceso: Conjunto de actividades que crean una salida o resultado a partir de una o más entradas o insumos.

• Sistema: Un conjunto de elementos interconectados utilizados para realizar el proceso. Incluye subprocesos pero también incluye los recursos y controles para llevar a cabo estos procesos.

• En el diseño de procesos nos enfocamos en QUÉ se ejecuta.

• En el diseño del Sistemas el énfasis está en los detalles de CÓMO, DÓNDE Y CUÁNDO.

SISTEMAS V/S PROCESOSSISTEMAS V/S PROCESOS

Entidadesque Entran

Entidadesque Salen

Reglas deOperación(Controles)

Sistema

Recursos

Actividades

Problema

Es identificar, comprender y describir en términos precisos, el problema que la organización enfrenta. El enunciado es la definición del problema. Un problema no se formula sino se define.

Cada vez es más difícil asignar los recursos o actividades de la forma más eficaz

Los recursos son escasos

Los sistemas son cada vez

más complejos

METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES

MÉTODOS EN INVESTIGACIÓN OPERATIVA

• Métodos determinísticos: Programación lineal, programación entera, probabilidad de transporte, teoría de la localización o redes, programación multicriterio, teoría de inventarios, etc.

• Métodos probabilísticos: Cadenas de markov, teoría de juegos, líneas de espera, teoría de inventarios, etc.

• Métodos híbridos: Conjugan métodos determinísticos y probabilísticos.

• Métodos heurísticos: soluciones basadas en la experiencia.

INVESTIGACION DE OPERACIONESClasificación de los modelos según la

Investigación Operaciones• Modelo Matemático

Es aquel modelo que describe el comportamiento de un sistema a través de relaciones matemáticas y supone que todas las variables relevantes son cuantificables. Por ende tiene una solución optima.

• Modelo de Simulación

Es un modelo que imita el comportamiento de un sistema sobre un periodo de tiempo dado, esta basado en observaciones estadísticas. Este tipo de modelo entrega soluciones aproximadas.

• Modelo Heurístico

Es una regla intuitiva que nos permite la determinación de una solución mejorada, dada una solución actual del modelo, generalmente son procedimientos de búsqueda. Este tipo de modelo también entrega soluciones aproximadas.

INVESTIGACION DE OPERACIONESEl Arte del Modelado

La Investigación de Operaciones debe ser considerada como una ciencia y la vez como un arte.

• Una ciencia por el uso de técnicas matemáticas para la resolución de los problemas.

• Un arte ya que la formulación del modelo depende en gran parte de la creatividad y la experiencia de las operaciones del equipo investigador.

ELEMENTOS PARA FORMULACIÓN DE PROBLEMAS

Habilidad para describir el diseño en términos matemáticos

• Variables• Parámetros• Funciones

VARIABLES DE DISEÑO

• Las variables de diseño son aquellas que asumen más de un valor o estado durante el rango de validez del modelo.

• Los valores del conjunto de estas variables caracterizan un diseño particular

• Cambian en un determinado rango a medida que buscamos el diseño óptimo

• Son las incógnitas del problema Tamaño de un objeto, número de objetos, …

• Deben ser linealmente independientes

VARIABLES DE DISEÑO

• El conjunto de variables de diseño se identifica como vector de diseño

• Nomenclatura [ X ] X ó x [x1, x2, …, xn]

xi, i = 1,2,…,n

FUNCIÓN OBJETIVO

• Problema: “Minimizar o maximizar cierta cantidad que se calcula con una función”

• Un problema de maximización se puede convertir en uno de minimización sin más que cambiar el signo de la función objetivo

• Nomenclatura: f f(x1, x2, …, xn) o f(X)

PARÁMETROS DE DISEÑO

• Parámetros de diseño son aquellos que no cambian o no pueden cambiar su valor durante el rango de validez del modelo matemático o físico de un proceso.

• Constantes que no cambian para los diferentes diseños

• Importantes en modelo pero no en la búsqueda del diseño óptimo

• Nomenclatura: [ P ] P [p1, p2, …, pq]

RESTRICCIONES

• Comparación con un valor numérico que limita

• Tipos: De igualdad: = De desigualdad: ,

• Ejemplo 1 Volumen de la lata: fun1(X) = 500 cm3

• Ejemplo 2 Deflexión: fun2(X) 1 mm

RESTRICCIONES

• Si las restricciones no se cumplen No hay solución

• Diseño factible Todas las restricciones se satisfacen

• Un diseño óptimo debe ser factible

• El espacio definido por las restricciones se llama dominio factible

FORMATO ESTÁNDAR

• Minimizar f(x1, x2, …, xn)

• Sujeto a hk(x1, x2, …, xn) = 0, k=1,2,…,l

gj (x1, x2, …, xn) 0, j=1,2,…,m

xil xi xi

u, i=1,2,…,n

• Lenguaje natural “Minimizar la función objetivo f, sujeto a 1 restricciones

de igualdad, m restricciones de desigualdad, con n variables de diseño comprendidas entre unos límites inferior y superior”

MODELADO EJEMPLO 1

• Variables de diseño: d, h• Parámetro de diseño: C (coste del material por unidad área)• Volumen = d2h/4• Área = dh• Restricción “estética”: h2d

MODELO EJEMPLO 1

• Minimizar f(d,h): Cdh

Sujeto a h1(d,h): d2h/4 – 500 = 0

g1(d,h): 2d – h 0

6 d 9; 5 h 20

• Minimizar f(x1,x2): Cx1x2

Sujeto a h1(x1,x2): x1

2x2/4 – 500 = 0

g1(x1,x2): 2x1 – x2 0

6 x1 9; 5 x2 20

Para la aplicación de la IO se siguen los siguientes pasos:

• La IO comienza con la observación cuidadosa de la realidad.

• Formular el problema.

• Construir un modelo que intente abstraer la esencia del problema real.

• Solución del modelo.

• Análisis de sensibilidad, hay que ver como se comporta el modelo ante cambios en las restricciones y/o parámetros del modelo

• Implementar los resultados, se debe interpretar los resultados y dar conclusiones y cursos de acción para la optimización del problema real

INVESTIGACIÓN DE OPERACIONES

Desarrollo de un modelo matemático Es la traducción del problema a términos matemáticos.

Es formular un modelo matemático:Identificando variablesIdentificando la Función Objetivo Identificando las restricciones

Objetivos: función objetivoalternativas: variables de decisiónlimitaciones del sistema: restricciones

I) Identificacion de las variables Xij = # de consultores que viajan del origen i al destino j II) Identificacion de la funcion objetivo Max 540X11+300X12+420X13+ 500X21+330X22+330X23+ 520X31+310X32+350X33 III) Identificacion de las restricciones X11+X12+X13 ≤ 2 X21+X22+X23 ≤ 1 X31+X32+X33 ≤ 4 X11+X21+X31 = 3 X12+X22+X32 = 2 X13+X23+X33 = 1 Xij ≥ 0 ; entero

Desarrollo de un modelo matemático

Paso 1. Identificar las variables de decisión¿Sobre qué tengo control?¿Qué es lo que hay que decidir?¿Cuál sería una respuesta válida del caso?

Paso 2. Identificar la función objetivo¿Qué pretendemos conseguir?¿qué me interesaría más?

Paso 3. Identificar las restricciones o factores que limitan la decisión, recursos disponibles

(trabajadores, máquinas, material), fechas límite, naturaleza de las variables (no negatividad, enteras, binarias).

Paso 4.Traducción de los elementos básicos a un modelo matemático.

Resolución del modelo

Es resolver el modelo usando una técnica adecuada, es decir obtener valores numéricos para la variable de decisión.

Es determinar los valores de las variables de decisión de modo que la solución sea óptima (o satisfactoria) sujeta a las restricciones.

Puede haber distintos algoritmos y formas de aplicarlos. En esta parte se usa el Software WIN QSB. Hay otros como el LINDO, MLP y TORA

Un método óptimo para lograr un objetivo.Una forma de evaluar preguntas de sensibilidad de la forma: ¿Qué sucedería sí ...?

VENTAJA DE LOS MODELOS

EL MODELO DE PROGRAMACIÓN LINEAL PROVEE UNA SOLUCIÓN INTELIGENTE PARA ESTE

PROBLEMA

Es un Arte que mejora con la práctica…

¡ PRACTIQUEMOS!

Hoy en día, la toma de decisiones abarca una gran cantidad de problemas reales cada más complejos y especializados, que necesariamente requieren del uso de metodologías para la formulación matemática de estos problemas y, conjuntamente, de métodos y herramientas de resolución, como los que provee la Investigación de Operaciones.

La Programación Lineal es una herramienta para resolver problemas de optimización que se caracterizan por tener como función objetivo y restricciones combinaciones lineales de las variables de decisión.

Función Objetivo: Max o Min (Z) = C X

Sujeto a : A X B Xi 0 ; i = 1, 2,...., n

Conceptos Básicos:

• Variables de Decisión• Función Objetivo• Restricciones• Restricciones de Signo

FORMULACION DE UN PROBLEMA PROGRAMACIÓN LINEAL

Consideremos los siguientes ejemplos para describir los conceptos básicos presentes en todo problema de programación lineal (PPL)

CONSTRUCCIÓN DE MODELOS DE PROGRAMACION LINEAL

Ejemplo N° 1

La Compañía PARGOLF es un pequeño fabricante de equipo y suministros para golf. El distribuidor de PARGOLF cree que existe un mercado tanto para una bolsa de golf de precio moderado, denominada modelo estándar, como para una bolsa de precio elevado, denominada modelo de lujo. El distribuidor está tan confiado en el que, si PARGOLF puede hacer las bolsas a un precio competitivo, el distribuidor comprará todas las bolsas que PARGOLF pueda fabricar durante los siguientes tres meses. Un análisis cuidadoso de los requerimientos de tiempo de producción para las cuatro operaciones de manufactura y la estimación hecha por el departamento de contabilidad de la contribución a la ganancia por bolsa.

Producto

Estándar

De lujo

Corte y teñido Costura Terminado

Inspección y empaque

Ganancia por bolsa

S/. 10

Tiempo de producción (horas/bolsa)

El director de manufactura estima que dispondrán de 630 horas de tiempo de corte y teñido, 600 horas de tiempo de costura, 708 horas de tiempo de terminado y 135 horas de tiempo de inspección y empaque para la producción de bolsas de golf durante los siguientes tres meses.

a) Si la compañía desea maximizar la contribución a la ganancia total, ¿Cuántas bolsas de cada modelo debería fabricar?

b) ¿Cuántas horas de tiempo de producción se programaran para cada operación?

c) ¿Cuántas horas de tiempo de ocio se tendrán en cada operación?

Formulación:

Variable de decisión:

Xi = Número de bolsas de modelo i a fabricar por trimestre i = 1, 2

Objetivo:

Maximizar: Ganancia/trimestre

Restricciones:

Tiempo disponible por trimestre

Corte y teñido

Acabado

Condiciones técnicas.

X1, X2 > 0

Inspección y empaque

Modelo Matemático de Programación Lineal:

Máx: Ganancia

Max. (Z) = 10X1 + 9X2

Sujeto a:

7/10X1 + X2 < 630 Corte y teñido

1/2X1 + 5/6X2 < 600 Costura

X1 + 2/3X2 < 708 Acabado

X1, X2 > 0

Trimestre = S/.

Trimestre

Bolsas

Trimestre=

Trimestre

1/10X1 + 1/4X2 < 135 Inspección y empaque

Ejemplo N° 2: El problema de la industria de juguetes “Galaxia”.

• Galaxia produce dos tipos de juguetes:

* Space Ray

* Zapper

• Los recursos están limitados a:

* 1200 libras de plástico especial.

* 40 horas de producción semanalmente.

• Requerimientos de Marketing.

* La producción total no puede exceder de 800 docenas.

* El número de docenas de Space Rays no puede exceder al

número de docenas de Zappers por más de 450.

• Requerimientos Tecnológicos.

* Space Rays requiere 2 libras de plástico y 3 minutos de

producción por docena.

* Zappers requiere 1 libra de plástico y 4 minutos de producción

por docena.

• Plan común de producción para:

* Fabricar la mayor cantidad del producto que deje mejores

ganancias, el cual corresponde a Space Ray (S/. 8 de utilidad

por docena).

* Usar la menor cantidad de recursos para producir Zappers,

porque estos dejan una menor utilidad (S/. 5 de utilidad por

docena).

Solución

• Variables de decisión

* X1 = Cantidad producida de Space Rays (en docenas por

semana).

* X2 = Cantidad producida de Zappers (en docenas por

semana).

• Función objetivo

* Maximizar la ganancia semanal.

• Modelo de Programación Lineal

Max (Z) = 8X1 + 5X2 (ganancia semanal)

Sujeto a:2X1 + 1X2 1200 (Cantidad de plástico)3X1 + 4X2 2400 (Tiempo de producción)

X1 + X2 800 (Limite producción total) X1 - X2 450 (Producción en exceso)

Xj 0, j = 1, 2. (Resultados positivos)

• El plan común de producción consiste en:Space Rays = 550 docenas

Zappers = 100 docenas

Utilidad = S/. 4900 por semana

EJEMPLO N° 3

Una firma industrial elabora dos productos, en los cuales entran cuatro componentes en cada uno. Hay una determinada disponibilidad de cada componente y un beneficio por cada producto. Se desea hallar la cantidad de cada articulo que debe fabricarse con el fin de maximizar los beneficios.

El siguiente cuadro resume los coeficientes de transformación o sea la cantidad de cada componente que entra en cada producto.

Producto Componente

P1 P2 Disponibilidad (kilogramos)

A B C D

1 2 2 1

3 1 2 1

15,000 10,000 12,000 10,000

Beneficios S/./unidad

X1 = Nº de unidades de producto P1

X2 = Nº de unidades de producto P2

Entonces el programa lineal correspondiente es:

Max (Z) = 4X1 + 3X2

Sujeto a :

1X1 + 3X2 ≤ 15,000

2X1 + 1X2 ≤ 10,000

2X1 + 2X2 ≤ 12,000

1X1 + 1X2 ≤ 10,000

X1, X2 ≥ 0

EJEMPLO Nº 4

En una fábrica de cerveza se producen dos tipos: rubia y negra. Su precio de venta es de S/. 0.5 / litro y S/. 0.3 / litro, respectivamente. Sus necesidades de mano de obra son de 3 y 5 empleados, y de 5,000 y 2,000 soles de materias primas por cada 10,000 litro.

La empresa dispone semanalmente de 15 empleados y 10,000 soles para materias primas, y desea maximizar su beneficio. ¿Cuántos litros debe producir?

FORMULACIÓN

1 2Max (Z) = 5,000X + 3,000X

3X + 5X 15

5,000X + 2,000X 10,000

X , X 0

Una mueblería produce mesas y sillas de madera. Cada mesa es vendida en $27.000 y se requiere $10.000 en materiales para su construcción, además, el costo unitario por mano de obra es de $14.000. En el caso de las sillas, el precio de venta es de $21.000 y los costos de materiales y mano de obra son $9.000 y $10.000 respectivamente.

La fabricación de cada producto requiere de dos labores: carpintería y terminaciones. Una mesa requiere de 1 hora de carpintería y 2 de terminaciones, mientras que la silla requiere de 1 hora en cada labor.

Ejemplo N° 5

Cada semana, la mueblería puede obtener todos los materiales que desee, sin embargo, se pueden dedicar hasta 100 horas a las terminaciones y hasta 80 horas a la carpintería. La demanda por mesas no está limitada, mientras que la demanda por sillas es de 40 unidades.

Formule un modelo matemático que permita maximizar las utilidades de la mueblería.

Variables de decisión: Variables de decisión:

Se debe comenzar definiendo las variables de decisión relevantes. En un PPL las variables de decisión deben ser capaces de describir completamente las decisiones que puedan ser tomadas y todas las variantes que existan.

Formulación

Antes de definir las variables de decisión es importante definir las unidades involucradas en el problema.

En este caso, se habla de unidades de sillas y mesas, de horas de trabajo por unidad y de demanda semanal. De acuerdo a ello, una buena opción para definir las variables de decisión consiste en asociar las variables al número de unidades de sillas y mesas a producir por semana. Por lo tanto, podemos definir:

X1 = Número de mesas producidas por semana.X2 = Número de sillas producidas por semana.

Función Objetivo: Función Objetivo:

En un PPL, se debe tomar la decisión de maximizar (usualmente las utilidades) o de minimizar (usualmente los costos) cierta función de las variables de decisión.

En el ejemplo, los costos e ingresos no dependen del valor de X1 o X2 por lo tanto basta concentrarse en maximizar la diferencia entre:

La función que se va a optimizar se llama Función Objetivo y en ella no aparece ningún término independiente o constante. Los valores de las variables de decisión son independientes de cualquier constante.

Ingresos Semanales – Costos de Materiales – Costos por mano de obraIngresos Semanales – Costos de Materiales – Costos por mano de obra

Luego se deben expresar los términos anteriores en función de las variables de decisión X1 y X2.

Por lo que la función objetivo queda (expresada en miles de $):

(27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2 (27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2

Así, el objetivo de la mueblería es escoger los valores X1 y X2 tal que se maximice 3X1 + 2X2

Denotando por Z el valor de la Función Objetivo para cualquier Problema de Programación Lineal, la función de la mueblería es:

Max Z = 3X1 + 2X2 Max Z = 3X1 + 2X2

El coeficiente que acompaña a cada variable en la Función Objetivo se denomina coeficiente en la función objetivo de la variable y refleja el aporte unitario de dicha variable.

Restricciones: Restricciones:

En las medidas que las variables crecen, la Función Objetivo aumenta su valor. Por lo tanto si se pudiera escoger arbitrariamente el valor de la variables, la mueblería podría hacer crecer el valor de sus utilidades en forma infinita. En la práctica esto no es posible y en el ejemplo el valor que toman las variables está limitado por las siguientes 3 restricciones:

• Máximo 100 horas semanales para terminaciones.• Máximo 80 horas semanales para carpintería.• Producción máxima de 40 sillas semanales.

Luego, el próximo paso consiste en formular matemáticamente las restricciones anteriores en función de las variables de decisión.

Para formular la primera restricción en función de las variables X1 y X2 observamos que:

Hrs. terminaciones x mesa + hrs. terminaciones x silla hrs. disponibles para terminaciónHrs. terminaciones x mesa + hrs. terminaciones x silla hrs. disponibles para terminación

Por lo que la restricción queda:

2X1 + X2 1002X1 + X2 100

Es importante notar que todos los valores en la expresión anterior son por semana, ya que las variables de decisión se han escogido con esa referencia.

Análogamente la segunda restricción queda:

X1 + X2 80X1 + X2 80

Finalmente, la tercera restricción sólo limita el valor de la variable X2

X2 40X2 40

Restricciones de Signo: Restricciones de Signo:

Para completar la formulación del modelo es importante definir si existe alguna restricción de signo para cada variable de decisión.

Si una variable de decisión Xi debe cumplir condiciones de NO NEGATIVIDAD, debemos agregar la siguiente restricción:

Xi 0Xi 0

Si la variable de decisión Xi puede asumir valores positivos o negativos se dice que Xi no tiene restricción de signo (SRS).

Combinando todas las expresiones anteriores, es posible completar el modelo matemático para este problema de optimización, quedando de la siguiente forma:

En el ejemplo ambas variables de decisión se refieren a cantidades a producir, por lo tanto son no negativas. Sin embargo, en otros ejemplos las variables pueden ser SRS, por ejemplo en el caso de que Xi se refiere al saldo de alguna cuenta.

Definición de variables:

X1: número de mesas producidas por semana.X2: número de sillas producidas por semana.

Función Objetivo:

Max Z = 3X1 + 2X2

Sujeto a:

2X1 + X2 100 Horas disponibles para terminaciones por semana

X1 + X2 80 Horas disponibles para carpintería por semana

X2 40 Producción máxima de sillas por semana

Xj 0 j = 1 y 2 No negatividad

Sujeto a:

. . . . .

X1,2,.....n > 0

Variables de decisiónCoeficientes objetivo

Coeficientes tecnológicos Coeficientes recurso

Condiciones técnicas o

No negatividad

MODELO GENERAL DE PROGRAMACIÓN LINEAL

nnXCXCXCMax(Z)

Optimizar

+++= ......2211

22222121

),,(..... bXaXaXann

≥=≤+++

1212111),,(..... bXaXaXa

nn≥=≤+++

mnmnmm bXaXaXa ),,(.....

2211≥=≤+++

• Donde el vector c también conocido como el vector costos, viene dado por:

• El vector de lado derecho o b, viene dado por:

• Este es un vector columna, que representa los recursos de las m actividades. Es por lo tanto el elemento de la mano derecha de cada una de las m ecuaciones.

...1 2 n-1 nC = c c c c

• La matriz A, representa los coeficiente tecnológicos; es la matriz para el sistema de ecuaciones Ax = b:

• El sistema de ecuaciones o el modelo de PL, queda representado por:

Max (Z) = C X

Sujeto a:

A X = bi

A X ≤ bi

A X ≥ bi

X ≥ 0

11 12 1n

21 22 2n

m,1 m,2 m,n

a a ... a

. . ... .

a a ... a

EL MODELO DE P.L.

Z: función objetivoC (c1,...,cn): vector de coeficientes de la f. o.X (x1,...,xn): vector de variables de decisiónA (...,aij,...): matriz de coeficientes técnicosb (b1,...,bm): vector de demandas

Matricialmente,

Optimización Max o Min = CXS.A.

AX bx 0 Forma canónica

Problema N° 1

Variables de Decisión

X1 = Cantidad de Manteles comprados (sólo se puede comprar el

primer día).

X2 = Cantidad de Manteles mandados a lavar en servicio rápido el primer día.

X3 = Cantidad de Manteles mandados a lavar en servicio normal el primer día.

X4 = Cantidad de Manteles mandados a lavar en servicio rápido el segundo día.

Día 1(40)

Día 2(70)

Día 3(60)

Restricciones.a) Satisfacción de la necesidad de manteles al primer día X1 ≥ 40b) Satisfacción de la necesidad de manteles al segundo día. (X1 − 40) + X2 ≥ 60 ↔ X1 + X2 ≥ 100c) Satisfacción de la necesidad de manteles al tercer día. (X1 − 40) + X2 − 60 + X3 + X4 ≥ 70 ↔ X1 + X2 + X3 + X4 ≥ 170d) El número de manteles mandados a lavar el primer día, puede a l

o mas ser igual al número de manteles usados ese día. X2 + X3 ≥ 40e) El número de manteles mandados a lavar hasta el segundo día,

puede a lo mas ser igual al número de manteles usados hasta ese día.

X2 + X3 + X4 ≥ 40 + 60 ↔ X2 + X3 + X4 ≥ 100f ) No negatividad. X1, X2, X3, X4 ≥ 0

Función ObjetivoMin (Z) = 20X1 + 15X2 + 8X3 + 15X4

Problema N° 2

Variables de DecisiónX1 = numero de libras de carne molida de res empleadas en cada libra de albóndigas.X2 = numero de libras de carne molida de cerdo empleadas en cada libra de albóndigas. Restricciones

Cada libra de albóndigas tendrá 0.20 X1, libras de grasa provenientes de la carne de res y 0.32 X2 libras de grasa de la carne de cerdo. El contenido total de grasa de una libra de albóndigas no debe ser mayor de 0.25 libras. Entonces:

0.20X1 + 0.32X2 ≤ 0.25 El número de libras de carne de res y de cerdo empleadas en cada libra de albóndigas debe sumar 1; entonces:

X1 + X2 = 1Finalmente, la tienda no puede usar cantidades negativas de ninguna de las carnes, así que hay dos restricciones de no negatividad: X1≥ 0 y X2 ≥ 0.

Función Objetivo

Min (Z) = 80X1 + 60X2

Problema N° 3

• Variables de decisiónX1: Unidades de A producidas en totalX2: Unidades de B producidas en totalX3: Unidades de C producidas en totalX4: Unidades de A vendidasX5: Unidades de B vendidas

• Función Objetivo

Max (Z) = 700 X4 + 3,500 X5 + 7,000 X3

• Restricciones

Sujeto a:

X1 + 2X2 + 3X3 ≥ 40

X1 = X4 + 2X2

X2 = X5 + X3

X1, X2, X3, X4, X5 ≥ 0

Problema N° 5

Un fabricante cuyo negocio es mezclar aguardiente, compra tres grados A, B, y C. Los combina de acuerdo a las recetas que especifican los porcentajes máximo y mínimo de los grados A y C en cada mezcla. Estos porcentajes se dan en la tabla N° 1.

La provisión de los tres grados de aguardientes básicos, junto con sus costos se presente en la tabla N° 2.

TABLA N° 2 DISPONIBILIDAD Y COSTOS DE AGUARDIENTE

AGUARDIENTEMAXIMA CANTIDAD

DISPONIBLEBOTELLAS POR DIA

COSTO POR BOTELLA

A 2000 S/. 7.00

B 2500 S/. 5.00

C 1200 S/. 4.00

TABLA N° 1 ESPECIFICACIONES DE MEZCLAS

MEZCLA ESPECIFICACION PRECIO POR BOTELLA

Súper FuerteNo menos de 60% de ANo mas de 20% de C

S/. 6.80

FuerteNo más de 60% de CNo menos de 15% de A

S/. 5.70

Menos Fuerte No más de 50% de C S/. 4.50

Indique cómo se obtiene la primera matriz en un modelo de programación lineal de una política de producción que haga máxima la ganancia.

Solución

X11 : Cantidad de A usada para el super fuerteX21 : Cantidad de B usada para el super fuerteX31 : Cantidad de C usada para el super fuerteX12 : Cantidad de A usada para el fuerteX22 : Cantidad de B usada para el fuerteX32 : Cantidad de C usada para el fuerte

Max (Z) = 6.80 (X11 + X21 + X31) + 5.7 (X12 + X22 + X32) – [ 7(X11 + X12) + 5(X21 + X22) + 4(X31 + X32)]Sujeto a:X11 + X12 ≤ 2,000X21 + X22 ≤ 2,500 DisponibilidadX31 + X32 ≤ 1,200

X11 ≥ 0.60 (X11 + X21 + X31) X31 ≤ 0.20 (X11 + X21 + X31)

X32 ≤ 0.60 (X12 + X22 + X32)

X12 ≥ 0.15 (X12 + X22 + X32)

Xij ≥ 0 : i = 1, 2, 3 ; j = 1, 2

Problema N° 6

Una compañía fabrica dos clases de cinturones de piel. El cinturón A es de alta calidad, y el cinturón B es de baja calidad. La ganancia respectiva por cinturón es de S/. 0.40 y S/. 0.30. Cada cinturón de tipo A requiere el doble de tiempo que el que usa el de tipo B, y si todos los cinturones fueran de tipo B, la compañía podría fabricar 1000 día, el abastecimiento de piel es suficiente únicamente para 800 cinturones diarios (A y B combinados) el cinturón A requiere una hebilla elegante, de las que solamente se dispone 400 diarias. Se tiene únicamente 700 hebillas al día para el cinturón B. Establezca las ecuaciones de programación lineal para el problema.

Tipo de cinturón Ganancia Disponibilidad

S/. / Cin hebillas/día

A 0.4 400

B 0.3 700

Xi: Número de cinturones producidos por día del tipo i; donde i =

tA = 2tB

FUNCIÓN OBJETIVO: Max (Z) = 0.4 XA + 0.3 XB

Sujeto a:

2 XA + XB ≤ 1,000

XA + XB ≤ 800

XA ≤ 400

XB ≤ 700

XA, XB ≥ 0

Problema N° 5

Un fabricante cuyo negocio es mezclar aguardiente, compra tres grados A, B, y C. Los combina de acuerdo a las recetas que especifican los porcentajes máximo y mínimo de los grados A y C en cada mezcla. Estos porcentajes se dan en la tabla N° 1.

La provisión de los tres grados de aguardientes básicos, junto con sus costos se presente en la tabla N° 2.

TABLA N° 2 DISPONIBILIDAD Y COSTOS DE AGUARDIENTE

AGUARDIENTEMAXIMA CANTIDAD

DISPONIBLEBOTELLAS POR DIA

COSTO POR BOTELLA

A 2000 S/. 7.00

B 2500 S/. 5.00

C 1200 S/. 4.00

TABLA N° 1 ESPECIFICACIONES DE MEZCLAS

MEZCLA ESPECIFICACION PRECIO POR BOTELLA

Súper FuerteNo menos de 60% de ANo mas de 20% de C

S/. 6.80

FuerteNo más de 60% de CNo menos de 15% de A

S/. 5.70

Menos Fuerte No más de 50% de C S/. 4.50

Indique cómo se obtiene la primera matriz en un modelo de programación lineal de una política de producción que haga máxima la ganancia.

Solución

X11 : Cantidad de A usada para el super fuerteX21 : Cantidad de B usada para el super fuerteX31 : Cantidad de C usada para el super fuerteX12 : Cantidad de A usada para el fuerteX22 : Cantidad de B usada para el fuerteX32 : Cantidad de C usada para el fuerte

Max (Z) = 6.80 (X11 + X21 + X31) + 5.7 (X12 + X22 + X32) – [ 7(X11 + X12) + 5(X21 + X22) + 4(X31 + X32)]Sujeto a:X11 + X12 ≤ 2,000X21 + X22 ≤ 2,500 DisponibilidadX31 + X32 ≤ 1,200

X11 ≥ 0.60 (X11 + X21 + X31) X31 ≤ 0.20 (X11 + X21 + X31)

X32 ≤ 0.60 (X12 + X22 + X32)

X12 ≥ 0.15 (X12 + X22 + X32)

Xij ≥ 0 : i = 1, 2, 3 ; j = 1, 2

Problema N° 7

Mineral N° 1

Mineral N° 2

X1 = toneladas de mineral 1 en el molde

X2 = toneladas de mineral 2 en el molde

Mineral 1 Mineral 2

Hierro forjado 60% 13%

Plomo 10% 3%

Min (Z) = 260 X1 + 80 X2

Sujeto a:

0.60 X1 + 0.13 X2 ≥ 0.20 (X1 + X2)

0.10 X1 + 0.03 X2 ≥ 0.05 (X1 + X2)

X1, X2, ≥ 0

Problema N° 8

Una industria de muebles requiere de 350 barras de 2x4x20 cm. y de 200 barras de 2x3x20 cm., si dicha empresa dispone de barras cuyas dimensiones son 7x5x20 cm., cual debe ser el programa que debe seguir para minimizar desperdicios sabiendo que el máximo debe ser de 140 cm3.

Solución

2 2 2 1

140 cm3 = 7 cm2

350 2 x 4 x 20

200 2 x 3 x 20

Xi = cantidad de barras a obtenerse en la modalidad de corte i

Min (Z) = 100 X1 + 60 X2 + 140 X3

X1 X2 X3

2 x 4 x 20 0 1 2

2 x 3 x 20 5 4 2

Sujeto a:

X2 + 2 X3 ≥ 350

5 X1 + 4 X2 + 2 X3 ≥ 200

X1, X2, X3 ≥ 0

Problema N° 9

Un fabricante de láminas metálicas recibe un pedido para producir 2000 láminas de tamaño 2’ x 4’ y 1000 láminas de tamaño 4’ x 7’. Se dispone de dos láminas estándar de tamaño 10’ x 3000’ y 11’ x 2000’. El personal del departamento de ingeniería decide que los tres siguientes patrones de corte son adecuados para satisfacer el pedido y minimizar el desperdicio. Formule el problema como un modelo de programación lineal.

2' 72' 2' 7'

Patron N° 1 Patron N° 2

Patron N° 3

2' 2' 2' 2' 2'

Solución

Láminas 2 x 4 2,000 10’ x 3,000’

4 x 7 1,000 11’ x 2,000’

Xij = Cantidad de patrones i utilizado para cortar

en la lámina j

Sujeto a:

2’ x 4’ 1 X11 + 5 X31 + 2 X22 + 5 X32 ≥ 2,000

4’ x 7’ 1 X11 + 0 X31 + 1 X22 + 0 X32 ≥ 1,000

X11 + X31 ≥ 3,000/4

X22 + X32 ≥ 2,000/4 X11, X31, X22, X32 ≥ 0

Min (Z) = 4 X11 + 0 X31 + 0 X22 + 4 X32

750 para cortar

500 para cortar

Problema N° 10

• El Real Hotel opera los 7 días a la semana. Las mucamas son contratadas para trabajar seis horas diarias. El contrato colectivo especifica que cada mucama debe trabajar 5 días consecutivos y descansar 2 días. Todas las mucamas reciben el mismo sueldo semanal. El Real hotel requiere como mínimo las horas de servicio.

Lunes 150, Martes 200, Miércoles 400, Jueves 300, Viernes 700, Sábado 800 y Domingo 300. El administrador desea encontrar un plan de programación de empleos que satisfaga estos requerimientos y a un costo mínimo.

Formule este problema como un modelo de programación lineal.

Solución

L Ma Mi J V S D L Ma Mi J V S D L Ma Mi J XL

Continuación…..

Xi = Número de mucamas que empiezan a trabajar el día i durante

cinco dias consecutivos

XJ + XV + XS + XD + XL ≥ 150 / 6 XV + XS + XD + XL + XMa ≥ 200 / 6

XS + XD + XL + XMa+ XMi ≥ 400 / 6 XD + XL + XMa+ XMi+ XJ ≥ 300 / 6

XL + XMa+ XMi+ XJ + XV ≥ 700 / 6 XMa+ XMi+ XJ + XV +XS ≥ 800 / 6 XMi+ XJ + XV +XS + XD ≥ 300 / 6XL , XMa, XMi, XJ , XV , XS , XD ≥ 0

Min (Z) = XL + XMa+ XMi+ XJ + XV + XS + XD

Problema

• El hospital ESSALUD ha decidido ampliar su servicio de urgencias (abierto las 24 horas) con la consiguiente necesidad de nuevo personal de enfermería. La gerencia del hospital ha estimado las necesidades mínimas de personal por tramos horarios para poder cubrir las urgencias que se presenten. Se definieron 6 tramos de 4 horas. La necesidad mínima de personal en cada tramo se indica en el cuadro mostrado. Por otro lado, el departamento de recursos humanos ha informado a gerencia que los contratos laborales han de ser de ocho horas seguidas, según el Convenio firmado con los sindicatos, independientemente de los horarios de entrada y salida del personal.

El problema es encontrar el número mínimo de personal necesario para cubrir la

demanda.

Cuadro: Necesidades de personal por tramos horarios

J Tramos Horarios

1 0:00 - 4:00

2 4:00 – 8:00

3 8:00 – 12:00

4 12:00-16:00

5 16:00-20:00

6 20:00-24:00

Personal Nj

9 5 3 7 5 6

Solución

Min (Z) = X1 + X2 + X3 + X4 + X5 + X6

Sujeto a:

X1 + X2 ≥ 5

X2 + X3 ≥ 3

X3 + X4 ≥ 7

X4 + X5 ≥ 5

X5 + X6 ≥6

X6 + X1 ≥ 9

Xj ≥ 0, j= 1,...,6

Cuadro: Necesidades de personal

Hora Tramos Horarios

1 0:00 - 4:00

2 4:00 – 8:00

3 8:00 – 12:00

4 12:00-16:00

5 16:00-20:00

6 20:00-24:00

0:00 4:00 8:00

12:00 16:00 20:00

Personal Nj

9 5 3 7 5 6

ProblemaDos aleaciones, A y B, están hechas de cuatro metales diferentes: I, II, III y IV, según las especificaciones siguientes:

Los cuatro metales se extraen de tres minerales metálicos diferentes:

Suponiendo que los precios de venta de las aleaciones A y B son US$ 200 y US$ 399 por tonelada, formule el problema como un modelo de programación lineal.

Sugerencia: supóngase que Xijk representa el número de toneladas del i-ésimo metal obtenido de la j-ésimo mineral metálico y asignado a la k-ésima aleación.

Aleación Especificaciones

Cuando mucho el 80% de I Cuando mucho el 30% de II Por lo menos el 50% de IV Entre 40% y el 60% de II Cuando menos el 30% de III A lo más el 70% de IV

Mineral

Capacidad máxima (ton)

Constituyentes (%) Precio (US$ / ton)

I II III IV Otros

1000 2000 3000

20 10 5

10 20 5

30 30 70

30 30 20

10 10 0

30 40 50

Solución

Xijk = número de toneladas del i – esimo metal obtenido de la j – esimo mineral metálico

asignado a la k – esima aleación

Max (Z) = [(X11A + X21A + X31A + X41A + X12A + X22A + X32A + X42A + X13A + X23A + X33A + X43A)200

(X11B + X21B + X31B + X41B + X12B + X22B + X32B + X42B + X13B + X23B + X33B + X43B)399] - (X11A + X21A + X31A + X41A )30 – (X11B + X21B + X31B + X41B)30 – (X12A + X22A + X32A +

X42A)40 - (X12B + X22B + X32B + X42B)40 – (X13A + X23A + X33A + X43A)50 – (X13B + X23B + X33B + X43B)50

Sujeto a:

X11A + X21A + X31A + X41A + X11B + X21B + X31B + X41B ≤ 1,000

X12A + X22A + X32A + X42A + X12B + X22B + X32B + X42B ≤ 2,000 Disponibilidad

X13A + X23A + X33A + X43A + X13B + X23B + X33B + X43B ≤ 3,000

X11A + X12A + X13A ≤ 0.80 [X11A + X21A + X31A + X41A + X12A + X22A + X32A + X42A + X13A +

X23A + X33A + X43A]

Xijk ≥ 0

Problema N° 11

La Compañía XYZ produce tornillos y clavos. La materia Prima para los tornillos cuesta S/. 2 por unidad, mientras que la materia prima para el clavo cuesta S/. 2.50. Un clavo requiere dos horas de mano de obra en el departamento N° 1 y tres en el departamento N° 2, mientras que un tornillo requiere 4 horas en el departamento N° 1 y 2 horas en departamento N° 2, el jornal por hora en ambos departamentos es de S/. 2. Si ambos productos se venden a S/. 18, y el número de horas de mano de obra disponibles por semana en los departamentos son de 160 y 180 respectivamente. Expresar el problema propuesto como un programa lineal, tal que maximice las utilidades.

DPTO 1 DPTO 2 MATERIA

PRIMA JORNAL PRECIO

Clavos 2 hrs. 3 hrs. S/. 2 / unid S/. 2 / hora S/. 18 / unid. Tornillo 4 hrs. 2 hrs. S/. 2.5/unid. S/. 2 / hora S/. 18 / unid Disponibilidad 160 hrs./sem. 180 hrs./sem.

Solución

X1 : unidades de clavos a producirse por semana

X2 : unidades de tornillos a producirse por semana

Max (Z) = 18(X1 + X2) – [10 X1 + 2 X1 + 12 X2 + 2.5 X2]

Sujeto a:

2 X1 + 4 X2 ≤ 160

3 X1 + 2 X2 ≤ 180

X1 , X2 ≥ 0

Problema N° 12

Xi : cantidad de unidades del tipo i a ser fabricados para ser vendidos a la semana

i : 1, 2, y 31 = válvula globo2 = válvula aguja3 = módulo

Max (Z) = 10 X1 + 20 X2 + 60 X3

Sujeto a:

10X1 + 15X2 + (25 + 2 x 10)X3 ≤ 25,000

5X1 + 5X2 + (10 + 2 x 5) X3 ≤ 15,000

5X1 + 5X2 + 10 X3 ≤ 45,000

5X2 + 10 X3 ≤ 45,000

5X2 + 20 X3 ≤ 45,000

X3 ≥ 200

X1, X2 , X3 ≥ 0

Problema N° 13

TAKAGAKI S. A. fabrica dos tipos de alimentos balanceados, recibe un pedido especial de 200 TN de una mezcla de proteínas y carbohidratos, la mezcla debe contener a lo más 40% de proteínas y por lo menos 30% de carbohidratos, el costo de cada TN de proteínas es de S/. 3 y de cada TN de carbohidratos es de 8, determinar la mezcla óptima.

XP: TN. de proteínas utilizadas en la mezcla

Xc: TN. de carbohidratos utilizadas en la mezcla

Max (Z) = 3 XP + 8 XC

Sujeto a:

XP + XC = 200

XP ≤ 0.40 ( XP + XC)

XC ≥ 0.30 ( XP + XC)

XP , XC ≥ 0

Problema N° 14

Xi: Número de acres que se destinan a cada cosecha en cada comunidad

I = 1, 2, 3, 4, 5, 6, 7, 8, 9

Max (Z) = 1,000 (X1 + X2 + X3) + 750 (X4 + X5 + X6) + 250 (X7 + X8 + X9)

Sujeto a:

Terreno para uso en cada comunidad

X1 + X4 + X7 ≤ 400

X2 + X5 + X8 ≤ 600

X3 + X6 + X9 ≤ 300

Comunidad Cosecha

1 2 3 1 Remolacha 2 Algodón 3 Sorgo

X1 X4 X7

X2 X5 X8

X3 X6 X9

Comunidad Cosecha

1 2 3 1 Remolacha 2 Algodón 3 Sorgo

X11 X21 X31

X12 X22 X32

X13 X23 X33

ContinuaciónAsignación de agua para cada comunidad

3 X1 + 2 X4 + X7 ≤ 600

3 X2 + 2 X5 + X8 ≤ 800

3 X3 + 2 X6 + X9 ≤ 375

Total de acres para cada cosecha

X1 + X2 + X3 ≤ 600

X4 + X5 + X6 ≤ 500

X7 + X8 + X9 ≤ 325

Igual proporción del área planteada

X1 + X4 + X7 = X2 + X5 + X8

400 600

X2 + X5 + X8 = X3 + X6 + X9

600 300

Xi ≥ 0 , i = 1,………,9

Problema N° 15

Variable de decisión

Xi = El uso de cada uno de los tres métodos de abatimiento en cada tipo de horno, expresado como una fracción de la capacidad de abatimiento de tal manera que Xi no exceda a 1

Función Objetivo

Min (Z) = 8X1 + 10X2 + 7X3 + 6X4 + 11X5 + 9X6 Sujeto a:

12X1 + 9X2 + 25X3 + 20X4 + 17X5 + 13X6 ≥ 60

35X1 + 42X2 + 18X3 + 31X4 + 56X5 + 49X6 150

37X1 + 53X2 + 28X3 + 24X4 + 29X5 + 20X6 125

X1 + X2 + X3 + X4 + X5 + X6 ≤ 1

X1, X2 , X3 , X4, X5, X6 0

Método de abatimiento

Tecnología

METODOS DE SOLUCION DE PROBLEMAS LINEALES

Métodos: Gráfico. Fácilmente comprensible y permite visualizar

algunas propiedades. Analítico. El método simplex ha demostrado ser

eficiente por el uso del computador. Algeibraíco

Método Gráfico: Este método consiste en delinear sobre el primer cuadrante (debido a la condición de no negatividad) la región de soluciones factibles; luego sobre ella se grafica la función objetivo.

Ejemplo 1Xi = Número de unidades del producto i

Max (Z) = X1 + X2 Sujeto a:

2 X1 + 2 X2 ≤ 8 6 X1 + 2 X2 ≤ 18 2 X1 + 4 X2 ≤ 16 X1 , X2 ≥ 0

SOLUCION GRAFICA

Cualquier punto dentro de la región cumple simultáneamente con las tres restricciones y con la no negatividad. Ahora el problema consiste en maximizar la función objetivo Z = X1+X2 sobre la región sombreada que representa a las restricciones del problema lineal en estudio:

X1+X2 = 0 M = - X2

La recta X1+X2 = 4 representa el máximo valor de Z, Sujeta a las restricciones del programa lineal propuesto. Cualquier valor de Z > 6, no tendrá ningún punto con la región sombreada

Región Factible. Es aquella que cumple con todas las restricciones y las condiciones de no negatividad.

Solución Factible. Es cualquier punto situado en la región factible.

Solución Básica. Es aquella que se encuentra en la intersección de rectas o hiperplanos o en la intersección con los ejes coordenados.

Solución Básica Factible. Es una solución básica que pertenece a la región factible.

Solución Optima. Es una solución factible que maximiza o minimiza la función objetivo según sea el caso

Solución Básica Factible Degenerada. Es una solución factible básica en la que una o más variables básicas toman el valor de cero.

TEOREMA 1. El conjunto de todas las soluciones factibles al problema de programación lineal es un conjunto convexo.

TEOREMA 2. La función objetivo alcanza su máximo en un punto extremo del conjunto convexo, generado por el conjunto de soluciones factibles al problema de programación lineal.

1. Existe un punto extremo del polígono (poliedro) convexo en el

cual la función objetivo tiene su máximo (mínimo).

2. Cada solución factible básica corresponde a un punto extremo

del polígono (poliedro) convexo.

Se tendrá que buscar que investigar únicamente los puntos extremos del polígono (poliedro) convexo y buscar aquel punto que proporcione el mayor (menor) valor para que la función objetivo y así obtendremos la solución buscada.

Restricción de mayor o igual que cero, límite mínimo

Ejemplo 2

Min (Z) = 2 X1 + 6 X2

Sujeto a:

12 X1 + 6 X2 ≥ 16

4 X1 + 12 X2 ≥ 12

X1 , X2 ≥ 0

Ejemplo 3

Min (Z) = 2 X1 + 3 X2

Sujeto a:

X1 + X2 ≤ 4

6 X1 + 2 X2 = 8

X1 + 5 X2 ≥ 4

X1 ≤ 3

X2 ≤ 3

X1 , X2 ≥ 0

La solución se encuentra en el segmento A y B, donde X1 = 8/7 y X2 = 4/7. la función objetivo toma el valor de 4.

Ejemplo 4

Max (Z) = X1 + X2

Sujeto a:

- 4 X1 + 2 X2 ≤ 2

2 X1 ≤ 4

2 X1 + 2 X2 ≤ 6

X1 , X2 ≥ 0

Se aprecia que la recta de la función objetivo no es ahora tangente a un vértice del polígono factible, si no es coincidente con uno de los lados del mismo.

¿Cuál es entonces la solución?

En este caso es posible definir cualquier punto sobre la recta BC y hallar en consecuencia los valores X1 y X2.

X1 = 2 ; X2 = 1; Z = 3, otro resultado X1 = 2/3 , X2 = 7/3 ; Z = 3

B(2,1)

(2/3,7/3)

Ejemplo 5

Max (Z) = 2 X1 + 2 X2

Sujeto a:

X1 - X2 ≥ 1

1/ 2 X1 + X2 ≤ 2

X1 , X2 ≥ 0

No tiene un valor máximo finito.

En problemas prácticos no puede presentarse este tipo de solución

Ejemplo 6

Max (Z) = 3 X1 + 2 X2

Sujeto a:

X1 + X2 ≤ 1

2 X1 + 2 X2 ≥ 4

X1 , X2 ≥ 0

Ejemplo 7

Max (Z) = X1 + X2

Sujeto a:

3 X1 - X2 ≥ - 3

X1 + X2 ≤ 4

X1 , X2 ≥ 0

No se puede garantizar que todo problema tenga solución factible.

USANDO UN GRAFICO SE PUEDEN REPRESENTAR TODAS

LAS RESTRICCIONES, LA FUNCION OBJETIVO Y LOS

TRES TIPOS DE PUNTOS DE FACTIBILIDAD.

Ejemplo: El problema de la industria de juguetes “Galaxia”.

• Galaxia produce dos tipos de juguetes:

* Space Ray

* Zapper

• Los recursos están limitados a:

* 1200 libras de plástico especial.

* 40 horas de producción semanalmente.

• Requerimientos de Marketing.

* La producción total no puede exceder de 800 docenas.

* El número de docenas de Space Rays no puede exceder al

número de docenas de Zappers por más de 450.

• Requerimientos Tecnológicos.

* Space Rays requiere 2 libras de plástico y 3 minutos de

producción por docena.

* Zappers requiere 1 libra de plástico y 4 minutos de producción

por docena.

• Plan común de producción para:

Fabricar la mayor cantidad del producto que deje mejores ganancias, el cual corresponde a Space Ray (S/. 8 de utilidad por docena).

Usar la menor cantidad de recursos para producir Zappers, porque estos dejan una menor utilidad (S/. 5 de utilidad por docena).

Solución

• Variables de decisión

X1 = Cantidad producida de Space Rays (en docenas por semana).

X2 = Cantidad producida de Zappers (en docenas por semana).

• Función objetivo

Maximizar la ganancia semanal.

• Modelo de Programación Lineal

Max (Z) = 8X1 + 5X2 (ganancia semanal)

Sujeto a:2X1 + 1X2 1200 (Cantidad de plástico)3X1 + 4X2 2400 (Tiempo de producción)

X1 + X2 800 (Limite producción total) X1 - X2 450 (Producción en exceso)

Xj 0, j = 1, 2. (Resultados positivos)

• El plan común de producción consiste en:Space Rays = 550 docenas

Utilidad = S/. 4900 por semana

Tipos de Puntos de factibilidad

Factible

Restricción del plástico: 2X1 + X2 1200

No Factible

Horas deProducción3X1 + 4X2 2400

Restricción del total de producción: X1 + X2 800

Restricción del exceso de producción:X1 - X2 450

Punto InferiorPunto Medio Punto Extremo

• Resolución gráfica para encontrar la solución optima

Recalcular la re

gión factib

400 600 800

comenzar con una ganancia dada de = S/. 2,000...

Util. = S/. 000 2,

Entonces aumente la ganancia...

...y continúe hasta que salga de la región factible

Ganancia = S/. 5,040

400 600 800

Se toma un valor cercano al punto óptimo

FeasibleregionRegiónFactible

Región no factible

• Resumen de la solución óptima

Space Rays = 480 docenas

Ganancia = S/. 5,040

*Esta solución utiliza todas las materias primas (plástico) y

todas las horas de producción.

* La producción total son 720 docenas (no 800).

* La producción de Space Rays excede a la de Zappers por

solo 240 docenas y no por 450.

• Soluciones óptimas y puntos extremos.

* Si un problema de programación lineal tiene una solución óptima, entonces esta corresponde a un punto extremo.

• Múltiples soluciones óptimas.

* Cuando existen múltiples soluciones óptimas implica que la función objetivo es una recta paralela a uno de los lados de la región factible.

* Cualquier promedio ponderado de la solución óptima es también una solución óptima.

METODO SIMPLEX

1. bi ≤ 02. Restricciones ≤3. Restricciones ≥4. Restricciones =

5. Xj ≤ 0; xi = - Xi, donde Xi ≥ 0

6. Xi Sin Restricción de Signo (SRS)+ , - , 0

X1 ; SRS

X1 = X1+

X1 = A1 - D1

A1 > D1; X1 > 0; X1 = A1 - 0

A1 = D1; X1 = 0; X1 = 0 - 0

A1< D1; X1 < 0; X1 = 0 - D1

donde :

A1, D1 ≥ 0

7. Empate en el criterio en la variable que ingresa se escoge arbitrariamente cualquiera.

Seleccionamos la variable que sale {θi menor}

8. Empate en el criterio en la variable que sale se escoge arbitrariamente cualquiera.

Criterio de Optimalidad

Max Zj - Cj ≥ 0 ; Cj - Zj ≤ 0

Min Zj - Cj ≤ 0 ; Cj - Zj ≥ 0

9. Tipo de soluciones.

Ejemplo – Método Simplex

La compañía SONYT S. A. produce radios y televisores, cada radio se vende con una ganancia de S/. 30, mientras que cada televisor vendido se gana S/. 50. Ambos productos deben pasar por los departamentos A y B (impresión de circuitos y ensamble) respectivamente: mensualmente se dispone de 200 horas en el departamento A y 140 horas en el departamento B. Cada radio requiere de una hora en departamento A como en el departamento B, cada televisor requiere de 2 horas en departamento A y una hora en el departamento B. Cuál es el programa de producción que maximiza la ganancia.

REQUERIMIENTOS DEPARATMENTO RADIO TELEVISOR

DISPONIBILIDAD

1 hr. 1 hr.

2 hrs. 1 hr.

200 hrs / mes 140 hrs. / mes

Xi: Numero de unidades del producto tipo i que se deben producir mensualmente.

Max (Z) = 30 X1 + 50 X2

Sujeto a:

X1 + 2 X2 ≤ 200

X1 + X2 ≤ 140

X1 , X2 ≥ 0

Solución

(80,60)

(140,0)

(0,100)

Cj 30 50 0 0

Ci XB X1 X2 S1 S2 bi θi

0 S1 1 2 1 0 200 100

0 S2 1 1 0 1 140 140

Cj -Zj 30 50 0 0 0

Solución

Iteración N° 1

Cj 30 50 0 0

50 X2 1/2 1 1/2 0 100 200

0 S2 1/2 0 -1/2 1 40 80

Cj -Zj 5 0 -25 0 5000

Iteración N° 2

Cj 30 50 0 0

50 X2 0 1 1 -1 60

30 X1 1 0 -1 2 80

Cj -Zj 0 0 -20 -10 5400

Solución

Iteración N° 3

¿Cuántos artefactos de A y B deben de producir para obtener el máximo beneficio?

ARTEFACTO A

(min/unid)

ARTEFACTO B

(min/unid)DISPONIBILIDAD

Maquinado

Armado

Montaje

Beneficio

Xi: Cantidad de artefactos del tipo i a producirse al día.

FUNCIÓN OBJETIVO

• Max (Z) = 100 X1 + 120 X2

• Sujeto a:

4 X1 + 8 X2 480 → Area de Maquinado

5 X1 + 6 X2 600 → Area de Armado

12 X1 + 8 X2 540 → Area de Montaje

X1, X2 0

(15/2, 225/4)

(0, 60)

(45, 0)

Cj 100 120 0 0 0

Ci XB X1 X2 S1 S2 S3 bi θi

0 S1 4 8 1 0 0 480 60

0 S2 5 6 0 1 0 600 100

0 S3 12 8 0 0 1 540 135/2

Cj -Zj 100 120 0 0 0 0

Solución

Iteración N° 1

Cj 100 120 0 0 0

120 X2 1/2 1 1/8 0 0 60 120

0 S2 2 0 -3/4 1 0 240 120

0 S3 8 0 -1 0 1 60 15/2

Cj -Zj 40 0 -15 0 0 7200

Iteración N° 2

Iteración N° 3

Cj 100 120 0 0 0

120 X2 0 1 3/16 0 -1/16 225/4

0 S2 0 0 -1/2 1 -1/4 225

100 X1 1 0 -1/8 0 1/8 15/2

Cj -Zj 0 0 -10 0 -5 7500

Xi: Variable de decisión

FUNCIÓN OBJETIVO

• Max (Z) = 4 X1 + 3 X2

Sujeto a:

4 X1 + 2 X2 12

X1 + 3 X2 9

7 X1 + 2 X2 28

X1, X2 0

Cj 4 3 0 0 0

0 S1 2 8 1 0 0 12 3

0 S2 3 6 0 1 0 9 9

0 S3 7 8 0 0 1 28 4

Cj -Zj 4 3 0 0 0 0

Tipos de Solución

Iteraciones

4 X1 1 1/2 1/4 0 0 3 6

0 S2 0 5/2 -1/4 1 0 6 12/5

0 S3 0 -3/2 -7/4 0 1 7 -

Cj -Zj 0 1 -1 0 0 24

4 X1 1 0 3/10 -1/5 0 9/5

3 X2 0 1 -1/10 2/5 0 12/5

0 S3 0 0 -19/10 3/5 1 53/5

Cj -Zj 0 0 -9/10 -2/5 0 72/5

Solución Optima Unica

FUNCIÓN OBJETIVO

• Max (Z) = 3 X1 + 5 X2

Sujeto a:

2 X2 12

3 X1 + 2 X2 18

X1, X2 0

Cj 3 5 0 0 0

0 S1 1 0 1 0 0 4 -

0 S2 0 2 0 1 0 12 6

0 S3 3 2 0 0 1 18 9

Cj - Zj 3 5 0 0 0 0

Tipos de Solución

Iteraciones

0 S1 1 0 1 0 0 4 4

5 X2 0 1 0 1/2 0 6 -

0 S3 3 0 0 -1 1 6 2

Cj - Zj 3 0 0 -5/2 0 30

0 S1 0 0 1 1/3 -1/3 2

5 X2 0 1 0 1/2 0 6

3 X1 1 0 0 -1/3 1/3 2

Cj - Zj 0 0 0 -3/2 -1 36

Solución Optima Unica

FUNCIÓN OBJETIVO

• Max (Z) = 3 X1 + 2 X2

Sujeto a:

2 X2 12

3 X1 + 2 X2 18

X1, X2 0

Cj 3 2 0 0 0

0 S1 1 0 1 0 0 4 4

0 S2 0 2 0 1 0 12 -

0 S3 3 2 0 0 1 18 6

Cj - Zj 3 2 0 0 0 0

Tipos de Solución

Iteraciones

3 X1 1 0 1 0 0 4 -

0 S2 0 2 0 1 0 12 6

0 S3 0 2 -3 0 1 6 3

Cj - Zj 0 2 -3 0 0 12

3 X1 1 0 1 0 0 4

0 S2 0 0 3 1 -1 6

2 X2 0 1 -3/2 0 1/2 3

Cj - Zj 0 0 0 0 -1 18

3 X1 1 0 0 -1/3 1/3 2

0 S1 0 0 1 1/3 -1/3 2

2 X2 0 1 0 1/2 0 6

Cj - Zj 0 0 0 0 -1 18

Solución Optima Altenativa

FUNCIÓN OBJETIVO

• Max (Z) = 10 X1 + 5 X2

Sujeto a:

-3 X1 + 4 X2 12

X1 - 2 X2 2

X1 + 2 X2 8

X1, X2 0

Cj 10 5 0 0 0 -M

Ci XB X1 X2 S1 S2 S3 A3 bi θi

0 S1 -3 4 1 0 0 0 12 3

0 S2 1 -2 0 1 0 0 2 -

-M A3 1 2 0 0 -1 1 8 4

Cj - Zj 10+M 5 + 2M 0 0 -M 0 0

Tipos de Solución

Iteraciones

5 X2 -3/4 1 1/4 0 0 0 3 -

0 S2 -1/2 0 1/2 1 0 0 8 -

-M A3 5/2 0 -1/2 0 -1 1 2 4/5

Cj - Zj 55/4+5M/2 0 -5/4-M/2 0 -M 0 15

5 X2 0 1 1/10 0 -3/10 3/10 18/5

0 S2 0 0 4/10 1 -1/5 1/5 42/5

10 X1 1 0 -1/5 0 -2/5 2/5 4/5

Cj - Zj 0 0 3/2 0 11/2 -M-11/2 26

Solución No Acotada

FUNCIÓN OBJETIVO

• Min (Z) = X1 + X2

Sujeto a:

9 X1 + 3 X2 9

3 X1 + 3 X2 15

3 X1 + 4 X2 = 12

X1, X2 0

Cj 1 1 0 0 M M

Ci XB X1 X2 S1 S2 A1 A3 bi θi

M A1 9 3 -1 0 1 0 9 1

0 S2 3 3 0 1 0 0 15 5

M A3 3 4 0 0 0 1 12 4

Cj – Zj 1-12M 1-7M M 0 0 0

Tipos de Solución

Iteraciones

1 X1 1 1/3 -1/9 0 1/9 0 1 3

0 S2 0 2 1/3 1 -1/3 0 12 6

M A3 0 3 1/3 0 -1/3 1 9 3

Cj - Zj 0 2/3-3M 1/9-M/3 0 -1/9+4M/3 0

1 X1 1 0 -4/27 0 4/27 -1/9 0

0 S2 0 0 1/9 1 -1/9 -2/3 6

1 X2 0 1 1/9 0 -1/9 1/3 3

Cj - Zj 0 0 1/27 0 M-1/27 M-2/9 3

Solución Degenerada

FUNCIÓN OBJETIVO

• Min (Z) = X1 + X2

Sujeto a:

9 X1 + 3 X2 9

X1 - 2 X2 15

X1 + 2 X2 = 12

X1, X2 0

Cj 1 1 0 0 M M

Ci XB X1 X2 S1 S2 A1 A3 bi θi

M A1 9 3 -1 0 1 0 9 1

0 S2 1 -2 0 1 0 0 15 15

M A3 1 2 0 0 0 1 12 12

Cj – Zj 1-10M 1-5M M 0 0 0

Tipos de Solución

Iteraciones

1 X1 1 1/3 -1/9 0 1/9 0 1 3

0 S2 0 -7/3 1/9 1 -1/9 0 14 -

M A3 0 5/3 1/9 0 -1/9 1 11 33/5

Cj - Zj 0 2/3-5M/3 1/9-M/9 0 -1/9+M/9 0

1 X2 3 1 -1/3 0 1/3 0 3 -

0 S2 7 0 -2/3 1 2/3 0 21 -

M A3 -5 0 2/3 0 -2/3 1 6 9

Cj - Zj -2+5M 0 1/3-2M/3 0 5M/3-1/3 0 3

1 X2 1/2 1 0 0 0 1/2 6

0 S2 2 0 0 1 0 1 27

0 S1 -15/2 0 1 0 -1 3/2 9

Cj - Zj 1/2 0 0 0 M M-1/2 6

FUNCIÓN OBJETIVO

• Max (Z) = 3X1 + 5X2

Sujeto a:

2 X2 12

3 X1 + 2 X2 = 18

X1, X2 0

GRAFICA

Cj 3 5 0 0 0 -M

Ci XB X1 X2 S1 S2 S3 A1 Bi θi

-M A1 1 0 -1 0 0 1 8 8

0 S2 0 2 0 1 0 0 12 -

-M A3 3 2 0 0 1 0 18 6

Cj – Zj 3 + M 5 + 2M -M 0 0 0

Tipos de Solución

Iteraciones

-M A1 0 -2/3 -1 0 -1/3 0 2

0 S2 0 2 0 1 0 0 12

3 X1 1 2/3 0 0 1/3 1 6

Cj - Zj 0 5-2M/3 -M 0 -M/3-1 0

Solución No Factible

FUNCIÓN OBJETIVO

• Max (Z) = 460X1 + 200X2

Sujeto a:

18 X1 + 3 X2 ≤ 800

9 X1 + 4 X2 600

X1 ≥ 80

X1, X2 0

Cj 460 200 0 0 0 -M

Ci XB X1 X2 S1 S2 S3 A3 bi θi

0 S1 18 3 1 0 0 0 800 400/9

0 S2 9 4 0 1 0 0 600 200/3

-M A3 1 0 0 0 -1 1 80 80

Cj – Zj 460+M 200 0 0 -M 0

Tipos de Solución

Iteraciones

460 X1 1 1/6 1/18 0 0 0 400/9

0 S2 0 5/2 -1/2 1 0 0 200

-M A3 0 -1/6 -1/18 0 -1 1 320/9

Cj – Zj 0 370/3-M/6 230/9-M/18 0 -M 0

Solución No Factible

FUNCIÓN OBJETIVO

• Max (Z) = X1 + X2

Sujeto a:

2 X1 + 2 X2 ≤ 8

6 X1 + 2 X2 18

2 X1 + 4 X2 ≤ 16

X1, X2 0

Cj 1 1 0 0 0

0 S1 2 2 1 0 0 8 4

0 S2 6 2 0 1 0 18 3

0 S3 2 4 0 0 1 16 8

Cj - Zj 1 1 0 0 0 0

Tipos de Solución

Iteraciones

0 S1 0 4/3 1 -1/3 0 2 -

1 X1 1 1/3 0 1/6 0 3 6

0 S3 0 10/3 0 -1/3 1 10 3

Cj - Zj 0 2/3 0 -1/6 0 3

1 X1 0 0 3/4 -1/4 0 3/2

1 X2 10 0 -1/4 1/4 0 5/2

0 S3 0 1 -5/2 -1/2 1 5

Cj - Zj 0 0 -1/2 0 0 4

1 X2 1 1 1/2 0 0 4

0 S2 4 0 -1 1 0 10

0 S3 2 0 -3 0 1 10

Cj - Zj 0 0 -1/2 0 0 4

Solución Optima Altenativa

Max (Z) = 4 X1 + 8 X2

Sujeto a:

6 X1 + 8 X2 ≤ 24

20 X1 = 10X2

8 X1 - 4 X2 ≤ 16

X1, X2 0

Cj 4 8 0 -M 0

Ci XB X1 X2 S1 A2 S3 bi θi

0 S1 6 8 1 0 0 24 4

-M A2 20 -10 0 1 0 0 0

0 S3 8 -4 0 0 1 16 2

Cj - Zj 4+20M 8 -10M 0 0 0

Tipos de Solución

Iteraciones

0 S1 0 11 1 -3/10 0 24 24/11

1 X1 1 -1/2 0 1/20 0 0 -

0 S3 0 0 0 -2/5 1 16 -

Cj - Zj 0 10 0 -1/6 0

1 X2 0 1 1/11 -3/110 0 24/11

1 X1 1 0 1/22 2/55 0 12/11

0 S3 0 0 0 -2/5 1 16

Cj - Zj 0 0 -10/11 -M-4/55 0 240/11

investigacion 2

Documents

2 Investigacion Cualitativa

Trabajo de investigacion 2

2 Investigacion Del Consumidor Clase 2

Investigacion (2)

2. problema investigacion

Investigacion 2 unidad

Proyecto de Investigacion (2)

Investigacion seguridad 2

Investigacion de 2 clic

Investigacion 2

Investigacion APUNTES 2

Investigacion represion11a 2

COBIT / INVESTIGACION 2

Investigacion Laboratorio 2

Investigacion Juridica 2

2 investigacion cientifica

Investigacion 2 Part2

2 paradigmas-de-investigacion 2

INVESTIGACION cientifica 2

Investigacion Organica 2