• Author / Uploaded
• luis j Perez

• Categories
• Investigación de operaciones
• Estocástico
• Programación lineal
• Ciencia y tecnología
• Cognición

Citation preview

Universidad Nacional de San Agustín

INVESTIGACION DE OPERACIONES 

Dr. Juan Armin Becerra Guzmán Dr. Armin Becerra Guzmán

MODELOS DE PROGRAMACION LINEAL

Dr. Armin Becerra Guzmán

HISTORIA DE LA INVESTIGACIÓN DE OPERACIONES Los inicios que hoy se conoce como IO, se remonta a los años 1759 cuando el economista Quesnay empieza a utilizar modelos primitivos de programación matemática. Más tarde, otro economista de nombre Walras, hace uso en 1874, de técnicas similares. Los modelos lineales de la IO, tiene como precursores a Jordan en 1873, Minkowsky en 1896 y a Farkas en 1903. Los modelos dinámicos probabilísticos tienen su origen con Markov a fines del siglo pasado.

Dr. Armin Becerra Guzmán

HISTORIA DE LA INVESTIGACIÓN DE OPERACIONES Los modelos matemáticos de la IO que utilizan estos precursores, estaban basados en el cálculo diferencial e integral (Newton, Lagrange, Laplace, Lebesgue, Leibinitz, Reimman, Stiegles, por mencionar algunos), la probabilidad y la estadística (Bernoulli, Poisson, Gauss, Bayes, Gosset, Snedecor, etc.). Pero fue hasta la segunda guerra mundial, cuando la IO empezó a tomar auge. Primero se le utilizó en la logística estratégica para vencer al enemigo y más tarde al finalizar la guerra, para la logística de distribución de todos los aliados repartidos por todo el mundo.

Dr. Armin Becerra Guzmán

HISTORIA DE LA INVESTIGACIÓN DE OPERACIONES

En 1947 el doctor George Dantzig, resumiendo el trabajo de sus antecesores, inventa el método simplex, con lo cual dio inicio a la programación lineal. Actualmente, la IO no solo se aplica en el sector privado, sino también en el sector público.

Dr. Armin Becerra Guzmán

Dr. Armin Becerra Guzmán

Metodología de la Investigación de Operaciones

  

 

El proceso de la Investigación de Operaciones comprende las siguientes fases: 1. Formulación y definición del problema. 2. Construcción del modelo. 3. Solución del modelo. 4. Validación del modelo. 5. Implementación de resultados.

Dr. Armin Becerra Guzmán

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.

Dr. Armin Becerra Guzmán

Sistemas v/s Procesos 

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. Dr. Armin Becerra Guzmán

Sistemas v/s Procesos Reglas de Operación (Controles)

Sistema

Entidades que Entran

Actividades

Recursos Dr. Armin Becerra Guzmán

Entidades que Salen

Modelos



Con el propósito de estudiar científicamente un sistema del mundo real debemos hacer un conjunto de supuestos de cómo trabaja.



Estos supuestos, que por lo general toman la forma de relaciones matemáticas o relaciones lógicas, constituye un Modelo que es usado para tratar de ganar cierta comprensión de cómo el sistema se comporta. Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Clasificación de los modelos Existen múltiples tipos de modelos para representar la realidad. Algunos son: •Dinámicos: Utilizados para representar sistemas cuyo estado varía con el tiempo. •Estáticos: Utilizados para representar sistemas cuyo estado es invariable a través del tiempo. •Matemáticos: Representan la realidad en forma abstracta de muy diversas maneras. •Físicos: Son aquellos en que la realidad es representada por algo tangible, construido en escala o que por lo menos se comporta en forma análoga a esa realidad (maquetas, prototipos, modelos analógicos, etc.).

•Analíticos: La realidad se representa por fórmulas matemáticas. Estudiar el sistema consiste en operar con esas fórmulas matemáticas (resolución de ecuaciones). •Numéricos: Se tiene el comportamiento numérico de las variables intervinientes. No se obtiene ninguna solución analítica. Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Clasificación de los modelos •Continuos: Representan sistemas cuyos cambios de estado son graduales. Las variables intervinientes son continuas. •Discretos: Representan sistemas cuyos cambios de estado son de a saltos. Las variables varían en forma discontinua. •Determinísticos: Son modelos cuya solución para determinadas condiciones es única y siempre la misma. •Estocásticos: Representan sistemas donde los hechos suceden al azar, lo cual no es repetitivo. No se puede asegurar cuáles acciones ocurren en un determinado instante. Se conoce la probabilidad de ocurrencia y su distribución probabilística. (Por ejemplo, llega una persona cada 20 ± 10 segundos, con una distribución equiprobable dentro del intervalo).

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Clasificación de los modelos •Es interesante destacar que algunas veces los modelos y los sistemas no pertenecen al mismo tipo. Por ejemplo: •El estudio del movimiento del fluido por una cañería (Fluidodinámica) corresponde a sistemas continuos. Sin embargo si el fluido se lo discretiza dividiéndolo en gotas y se construye un modelo discreto por el cual circulan gotas de agua (una, dos, diez, cien, mil) se está representando un sistema continuo por un modelo discreto.

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Clasificación de los modelos El azar en computadora es pseudo azar:

•Mediante un algoritmo matemático se generan números al azar con una distribución aleatoria similar a la real. Se los puede utilizar en los modelos estocásticos obteniendo similares resultados a los que se obtienen en el sistema real. Sin embargo, este azar es repetitivo (cualquiera que conoce el algoritmo

puede predecirlo) lo cual contradice a lo que sucede en un proceso aleatorio. •En este caso, un sistema estocástico es representado por un modelo pseudoazar (determinístico).

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Clasificación de los modelos según la I.O. 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.

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Tópicos relacionados •Análisis Estadístico

•Simulación •Programación Lineal •Sistema de Redes •Líneas de Espera

•Problemas de Inventario •Programación No - Lineal •Programación Dinámica •Programación Entera •Teoría de Decisiones •Teoría de Juegos

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES El Arte del Modelado

La I.O 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 delas operaciones del equipo investigador.

Dr. Armin Becerra Guzmán

INVESTIGACION DE OPERACIONES Etapas para puesta en práctica 1. Definición del problema: • Alternativas de decisión (vars. de decisión). • El objetivo de estudio (Función Objetivo). • Identificación de las restricciones del sistema que se modela. 2. Construcción del modelo: • Traducir el problema a relaciones matemáticas que incluyan las vars. decisión, la Función Objetivo y las restricciones. 3. Solución del modelo: • Uso de algoritmos de optimización. • Se encuentran los valores de las vars. decisión. 4. Validación del modelo: • ¿El modelo entrega una predicción razonable del comportamiento del sistema estudiado? 5. Puesta en práctica: • Traducir los resultados del modelo en instrucciones de operación.

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL

PROGRAMACION LINEAL FORMULACION MATEMATICA

PROBLEMA GENERAL METODO GRAFICO

PROBLEMAS ESPECIALES

METODO ALGEBRAICO (SIMPLEX)

PROBLEMAS DE TRANSPORTE

Dr. Armin Becerra Guzmán

PROBLEMAS DE ASIGNACIÓN

PROGRAMACIÓN LINEAL

Es un método matemático que se emplea para resolver problemas de optimización. En palabras simples la P.L. busca asignar recursos limitados, entre actividades que compiten, de la forma mas optima posible.

Supuestos de la P.L. •Proporcionalidad •Aditividad •Divisibilidad •Certidumbre •Objetivo único •No negatividad

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos PROBLEMA DE LA MEZCLA DE PRODUCTOS Una compañía fabrica dos tipos de componentes electrónicos: transistores y bobinas. Cada transistor requiere un minuto de tiempo en el departamento de ensamble, dos minutos de tiempo en el departamento de Control de Calidad y un minuto de tiempo en empaque. Cada bobina requiere dos minutos de tiempo en ensamble, un minuto de tiempo en Control de Calidad y dos minutos en empaque. Existe un total de 300 minutos en Ensamble, 400 minutos en C. Calidad y 400 minutos en Empaque disponibles cada día. Tanto los transistores como las bobinas contribuyen en un sol (S/)a la utilidad. La compañía desea determinar la mezcla de productos optima que maximice la utilidad total.

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Solución: Formulación Paso 1: Identificar el objetivo (meta) a optimizar Maximizar las utilidades de la compañía (U).{soles/día} Paso 2: Identificar las variables de decisión que deseamos determinar X1….Cantidad de transistores a fabricar por día {unds./día} X2….Cantidad de bobinas a fabricar por día {unds./día} Paso 3: Identificar las restricciones del modelo R1) Tiempo disponible en el depto. de Ensamble por día 300 min. R2) Tiempo disponible en el depto. de C. Calidad por día de 400 min. R3) Tiempo disponible en el depto. de Empaque por día de 400 min. R4) No Negatividad. Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Paso 4: Construcción del modelo matemático

F.Objetivo MAX U = X1 + X2 Sujeto a : R1) X1 + 2X2  300 R2) 2X1 + X2  400 R3) X1 + 2X2  400

R4) X1 , X2  0

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos EJERCICIO PROPUESTO El departamento de rayos X de un hospital tiene dos máquinas, A y B, que pueden utilizarse para revelar radiografías. La capacidad de procesamiento diaria de estas máquinas es A=80 y B=100 radiografías. El departamento debe planear procesar al menos 150 radiografías por día. Los costos de operación por radiografía son S/.4 para la máquina A y S/.3 para la máquina B. ¿Cuántas radiografías por día debe procesar cada máquina para minimizar costos? Se pide: Formular como un problema de P.L. identificando claramente la función objetivo y las variables de decisión.

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Solución: Formulación Paso 1: Identificar el objetivo (meta) a optimizar Minimizar los costos de procesamiento (C).{soles/día} Paso 2: Identificar las variables de decisión que deseamos determinar X1….Cantidad de radiografías a procesar en máquina A al día {rad./día} X2…. Cantidad de radiografías a procesar en máquina B al día {rad./día} Paso 3: Identificar las restricciones del modelo R1) Capacidad de procesamiento de rad. en la maquina A de 80. R2) Capacidad de procesamiento de rad. en la maquina B de 100. R3) Capacidad mínima del departamento de 150 rad. por día. R4) No Negatividad. Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Paso 4: Construcción del modelo matemático

F.Objetivo MIN C = 4X1 + 3X2 Sujeto a :

 80

R1) X1 X2

 100

R3) X1 + X2

 150

R2)

R4) X1 , X2  0

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos PROBLEMA DE LA DIETA La compañía OF utiliza diariamente por lo menos 800 libras de alimento especial. El alimento especial es una mezcla de maíz y semilla de soya, con las siguientes composiciones. libra componente por libra de alimento ganado A. ganado

Proteinas

Fibra

Maíz Semilla Soya

0.09 0.60

0.02 0.06

Dr. Armin Becerra Guzmán

Costo US$/lb

0.30 0.90

PROGRAMACIÓN LINEAL Construcción de modelos

Los requerimientos dietéticos diarios de alimento especial estipulan por lo menos un 30% de proteínas y cuando mucho un 5% de fibra. OF desea determinar el costo mínimo diario de la mezcla de alimento.

¿….? Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Solución: Formulación Paso 1: Identificar el objetivo (meta) a optimizar Minimizar el costo diario total de la mezcla de alimento(C).{dólares/día} Paso 2: Identificar las variables de decisión que deseamos determinar X1….libras de maiz en la mezcla diaria {lb./día} X2…. Libras de semilla de soya en la mezcla diaria {lb./día} Paso 3: Identificar las restricciones del modelo R1) Requerimientos de alimentos de por lo menos 800 lbs.al día R2) Requerimiento de proteínas de por lo menos un 30% R3) Requerimientos de fibra de cuando mucho un 5%. R4) No Negatividad. Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Paso 4: Construcción del modelo matemático

F.Objetivo MIN C = 0.3X1 + 0.9X2 Sujeto a : R1) X1 + X2

 800

R2) 0.09X1 + 0.6X2

 0.3(X1 + X2)

R3)0.02 X1 + 0.06X2

 0.05(X1 + X2)

R4) X1 , X2

 0

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Paso 4.1: Construcción del modelo matemático (ORDENADO)

F.Objetivo M IN C = 0.3X1 + 0.9X2 Sujeto a : R1) X1 + X2

 800

R2) 0.21X1 - 0.30X2

 0

R3)0.03 X1 - 0.01X2

 0

R4) X1 , X2

 0

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos PROBLEMA DE TRANSPORTE Considere el problema que enfrenta el departamento de planificación de la compañía DALLAS S.A. ,que tiene tres plantas y cuatro almacenes regionales. Cada mes se requiere de una lista de requerimientos de cada almacén y se conocen, tambien las capacidacdes de producción de las plantas. Ademas se conoce el costo de transporte de cada planta a cada almacén. El problema es determinar qué plantas deben abastecer a que almacenes de manera que minimicen los costos totales de transporte. Consideremos que los costos de transporte entre dos ciudades cualquiera, son proporcionales a las cantidades

embarcadas. Supongase que las capacidades mensuales de cada planta son 70, 90 y 180 respectivamente. Los requerimientos de cada almacén para el mes de Marzo son: 50, 80, 70 y 140. Los costos unitarios de transporte son los que se muestran en la tabla siguiente: Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Planta 1 2 3

1 19 70 40

Almacén 2 30 30 8

Se pide: Formular como un PPL.

Dr. Armin Becerra Guzmán

3 50 40 70

4 10 60 20

PROGRAMACIÓN LINEAL Construcción de modelos Solución: Formulación Paso 1: Identificar el objetivo (meta) a optimizar Minimizar el costo total de transporte (C).{u.m/mes} Paso 2: Identificar las variables de decisión que deseamos determinar Xij….Cantidad a enviar de la planta “i” al almacén “j” mensualmente {uds/mes} i = 1,2,3 / j = 1,2,3,4 Paso 3: Identificar las restricciones del modelo R1) Capacidad mensual de producción planta 1 de 70 R2) Capacidad mensual de producción planta 2 de 90 R3) Capacidad mensual de producción planta 3 de 180 R4) Requerimientos del almacén 1 para Marzo de 50 R5) Requerimientos del almacén 2 para Marzo de 80 R6) Requerimientos del almacén 3 para Marzo de 70 R7) Requerimientos del almacén 4 para Marzo de 140 R8) No Negatividad. Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos Paso 4.1: Construcción del modelo matemático F.Objetivo

MinC=19X11+70X21+40X31+30X12+30X22+8X32+50X13+40X23+70X33+10X14+60X24+20X34 Sujeto a : R1) X11+X12+X13+X14

 70

R2) X21+X22+X23+X24

 90

R3) X31+X32+X33+X34

 180

R4) X11+X21+X31

 50

R5) X12+X22+X32

 80

R6) X13+X23+X33

 70

R7) X14+X24+X34

 140

R8) Xij

 0

 i,j

Dr. Armin Becerra Guzmán

Modelo General de PL Definición de variables: Sea xj = #.... ; j = 1, 2, 3....n Función objetivo: Max. o Min. z = C1X1 + C2X2 + ... + CjXj + ... + CnXn Sujeto a restricciones: i = 1, 2, 3, ... , m a11X1 + a12X2 + ... + a1jXj + ... + a1nXn a21X1 + a22X2 + ... + a2jXj + ... + a2nXn · . · . ai1X1 + ai2X2 + ... + aijXj + ... + ainXn · . · . am1X1 + am2X2 + ... + amjXj + ... + amnXn Condiciones de signo para variables: toda xj  0 m = # total de restricciones, n = # de variables de decisión (originales) Cj, aij y bi son constantes (o parámetros) dados. Dr. Armin Becerra Guzmán

= =

b1 b2

=

bi

=

bm

Ejercicios (Proponer el Modelo) 1. Disponemos de 210000 soles para invertir en bolsa. Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el 10% anualmente y las del tipo B, que rinden el 8% anualmente. Decidimos invertir un máximo de 130000 soles en las del tipo A y como mínimo 60000 en las del tipo B. Además queremos que la inversión en las del tipo A sea menor que el doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión para obtener la máxima utilidad anual? 2. En una pastelería se hacen dos tipos de tortas: Vienesa y Real. Cada torta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 25 soles, mientras que una torta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce 40 soles. de beneficio. En la pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tortas de cada tipo. ¿Cuántas tortas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio?

Dr. Armin Becerra Guzmán

Métodos de Resolución Método Gráfico Empleado principalmente para PPL con dos variables de decisión. Este método se basa en la idea de obtener regiones de soluciones factibles (RSF), en las cuales se encontraría la combinación de variables de decisión que optimizan el modelo. Método Algebraico (SIMPLEX) Empleado principalmente para PPL con más de dos variables de decisión. Este método se desarrollo con base en el método gráfico y corresponde a un sistema heurístico, por lo cual requiere de una solución inicial factible para empezar a funcionar.

Dr. Armin Becerra Guzmán

8

METODO GRAFICO

Dr. Armin Becerra Guzmán

PROGRAMACIÓN LINEAL Construcción de modelos PROBLEMA DE LA MEZCLA DE PRODUCTOS Un fabricante produce dos tipos de Triciclos de Carga, los cuales deben procesarse a través de dos centrales de Producción Mecánica. La Central I tiene un máximo de 120 horas disponibles, y la central II tiene un máximo de 180 horas disponibles. La manufactura del Triciclo que tiene un costo de fabricación de S/. 300 requiere de 6 horas en la central I y 3 horas en la Central II. La fabricación del triciclo que tiene un costo de fabricación de S/. 320.00 requiere 4 horas en la Central I y 10 horas en la central II. Si se venden a S/. 345 y S/. 375 respectivamente ¿En que cantidad se debe fabricar de ambos para tener la máxima utilidad?

Dr. Armin Becerra Guzmán

Función Objetivo y Restricciones CENTRALES

TRICICLO X2

Central 1 Central 2 Utilidad

TRICICLO X2

6 3

4 10

45

55

Función Objetivo: (Max) Z

= 45 X1

+

55X 2

Restricciones:

(1)6 x1  4 x2  120 ( 2)3 x1  10 x2  180

Dr. Armin Becerra Guzmán

DISPONIBILIDAD

120 180

4 10 55

Resolución por el Método Gráfico 120 180

2

55X 2 1 0.8181 0

1

2

Título del gráfico 35 30

25 20 15

10 5 0 0

10

20

30 X2 (R1)

40 X2 (R2)

Dr. Armin Becerra Guzmán

50

60

70

Resolución Algebraica *3 *-6

X1 6 3 18 -18 0

+ + + +

X2 4 10 12 -60 -48

= = = =

120 180 360 -1080 -720

x2

=

15

X1

=

10

Z MAX

=

1275

Dr. Armin Becerra Guzmán

Ejercicio de Aplicación.- (Caso de Minimización) La fábrica de papel caritg y Papelera Peruana producen tres tamaños de papel bond satinado de 80 grms. -

Oficio Carta Oficial

Se tiene un requerimiento para la zona sur de 16 Tm de papel tamaño oficio, 5 Tm de tamaño carta y 20 TM de tamaño oficial. Los costos de operación son de S/. 1000 por día para la fabrica CARITG y S/. 2000 por día para la fábrica PAPELERA PERUANA. La producción de la fabrica CARITS por día es de 8 TM de papel tamaño oficio, 1 TM de tamaño carta y 2 TM de tamaño oficial. La producción de la fábrica PAPELERA PERUANA por día es de: 2 TM de tamaño oficio, 1 TM de tamaño carta y 7 TM tamaño oficial. ¿Cuántos días debe trabajar cada fábrica a fin de cumplir con el mencionado requerimiento en la forma más económica posible? Dr. Armin Becerra Guzmán

OFICIO CARTA OFICIAL Función Objetivo MIN Z =

CARITS

PAPEL PER

X1 8 1 2

X2 2 1 7

TOTAL 16 5 20

1000X1

+

2000X2

8X1 +2X2 >= 1X1 +1X2 >= 2X1 +7X2 >= (X1, X2) >=0

16 5 20

RESTRICCIONES R1 R2 R3 R4

Dr. Armin Becerra Guzmán

2 Pendiente

-0.5 1 0.5 0

1

2

Título del gráfico 9 8 7 6 5

4 3 2 1 0 0

2

4

X2 R1

6

8

X2 R2

X2 R3

Dr. Armin Becerra Guzmán

10

12

Resolución Algebraica -0.21

X1 1 0.21 -0.21 0.21 0

+ + +

X2 1 0.3 -0.21 -0.3 -0.51

= = = =

800 0 -168 0 -168

x2

=

329.411765

X1

=

470.588235

Z MIN

=

437.65

Dr. Armin Becerra Guzmán

METODO SIMPLEX

Dr. Armin Becerra Guzmán

Métodos de Resolución ALGEBRAICO SIMPLEX

El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal. El algoritmo denominado símplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con el conocido procedimiento de GaussJordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo.. •El conjunto de soluciones factibles para un problema de P.L. es un conjunto convexo. •La solución óptima del problema de programación lineal , si existe, es un punto extremo

(vértice) del conjunto de soluciones factibles. •El número máximo de puntos extremos (vértices) por revisar en la búsqueda de la solución óptima del problema es finito.

Dr. Armin Becerra Guzmán

El Modelo SIMPLEX

Dr. Armin Becerra Guzmán

Criterios Básicos del Método Simplex

Variables de Holgura y Variables Artificiales FUNCION signo OBJETIVO = Max +S +A -S+A Min +S +A -S+A

PIBOTE SOLUCION Variable de Variable de OPTIMA Entrada Salida Cj-Zj Mayor PositivoMenor Posit bi/ai Cj - Zj =0

+ A1 +A2 + A3

= = =

16 5 20

Se trabaja primero una función objetivo artificial Z* donde los coeficientes estructurales (del problema) y de holgura son " 0" y los coeficientes de las variables estructurales son "1" MIN Z*

=

0X1 + 0X2 + 0S1 +0S2 +0S3 + A1 + A2 + A3

R1 R2 R3 R4

8X1 +2X2 -S1 + A1 1X1 +1X2 -S2 +A2 2X1 +7X2 -S3 + A3 (X1, X2) >=0 Dr. Armin Becerra Guzmán

= = =

16 5 20

PROGRAMACIÓN LINEAL METODO DE 2 FASES PRIMERA FASE Cj 1 1 1

MEZCLA DE CANTIDAD PRODUCTOS 16 A1 5 A2 20 A3 Zj ZJ-CJ

0 X1 8 1 2 11 11

0 X2 2 1 7 10 10

0 S1 -1 0 0 -1 -1

0 S2 0 -1 0 -1 -1

0 S3 0 0 -1 -1 -1

1 A1 1 0 0 1 0

1 A3 0 0 1 1 0

1 A2 0 1 0 1 0

SEGUNDA FASE MIN Z Cj 1000 0 2000

=

1000X1 + 2000X2 - 0S1 -0S2 -0S3 + A1 + A2 + A3

MEZCLA DE CANTIDAD PRODUCTOS X1 1.0000 S3 10.0000 X2 4.0000 Zj 9000 ZJ-CJ

1000 X1 1.0000 0.0000 0.0000 1000 0

2000 X2 0.0000 0.0000 1.0000 2000 0.00

0 S1 -0.1667 0.8333 0.1667 167 166.67

0 S2 0.3333 -8.6667 -1.3333 -2333 -2333.33

Dr. Armin Becerra Guzmán

0 S3 0.0000 1.0000 0.0000 0 0.00

bi/aij -6 12 24.0000006

bi/aij 2 5 10

PROGRAMACIÓN LINEAL METODO SOLVER

PLANTEAMIENTO PARA SOLVER UTILIDAD

NUMERO DE OPERACIONES VARIABLE

170 160

X1 X2 X3 X4

X1 0.5 2.0 0.5 3.0

X2 1.0 1.0 0.5 1.0

180 200

ANDA H-H ULTRA CAMPEON SUPER ANDA

CORTE TALADRO PINTADO ENSAMBLAJE

CANTIDAD

0 0 0 0 Maximizar Z =

X3 1.0 1.0 0.0 2.0

TOTAL S/. 0 0 0 0 0

X4 0.5 1.0 1.0 3.0

Dr. Armin Becerra Guzmán

RESTRICCIONES

0.0 0.0 0.0 0.0

LIMITE 1800 3800 2000 5000

PROGRAMACIÓN LINEAL METODO SOLVER

RESULTADOS DE SOLVER UTILIDAD

NUMERO DE OPERACIONES VARIABLE

ANDA H-H ULTRA CAMPEON SUPER ANDA

18 20 17 16

X1 X2 X3 X4

CANTIDAD

720 840 400 400 Maximizar Z =

Dr. Armin Becerra Guzmán

TOTAL S/. 12960 16800 6800 6400 42960