Io St113 Parte i

5/9/2018 Io St113 Parte i - slidepdf.com

http://slidepdf.com/reader/full/io-st113-parte-i 1/52

UNIVERSIDAD NACIONAL DE INGENIERIA

Facultad de Ingeniería Industrial y de SistemasArea de Sistemas Computación e Informática

INVESTIGACION DE OPERACIONES I

PARTE I

(ST – 113)

Profesora: Ing. IRMA INGA SERRANO

2011



U n i v e r

s i d a d

N a c i o n a l d e I n g e n i e r í a

F a c u l t a d

d e I n g e n i e r i a

I n d u s t r

i a l y d e S i s t e m a s

6

DATOS DEL CURSO

CODIGO DEL CURSO: ST-113

CREDITOS: 03

SISTEMA DE EVALUACION: F Examen Parcial: Peso 1

Examen Final : Peso 2

Promedio de Prácticas: Peso 1

(4 prácticas calificadas, se elimina la mas baja)



U n i v e r

s i d a d


F a c u l t a d

d e I n g e n i e r i a

I n d u s t r


6

CONTENIDO DEL CURSO

1.- Introducción- Conceptos de Inv. de Operaciones.

2.- Programación Lineal

Formulación de Problemas de Prog. Lineal

Solución de problemas PL. Método simplexCasos especiales de PL

Método simplex matricial

Dualidad- Método simplex-dual

Análisis de Sensibilidad3.- Programación Entera

Formulación de PE

Solución de problemas PE

4.- Programación por metas



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

¿QUE ES LA INVESTIGACION DE OPERACIONES?La Investigación de operaciones es también llamada Ciencia de laAdministración ó Ciencia de las Decisiones ó de los MétodosCuantitativos.

Aquí se muestra la definición que le dan algunos autores:

“ Es el conjunto de conocimientos que involucran procedimientosracionales cuantitativos para la toma de decisiones con base enmétodos científicos.”

“ Es una disciplina que ayuda en la toma de decisiones mediante

la aplicación de un enfoque científico a problemas de decisiónque involucran factores cuantitativos”

Resumen:

“Es la aplicación del método científico a problemas de decisión”

CAPITULO I

INTRODUCCION A LA INVESTIGACION DE OPERACIONES



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

Proceso de toma de decisiones

en la solución de un pro

blema

Definir elproblema

Determinarlos criterios de

evaluación

Análisis

cualitativo

Análisis

cuantitativo

Resumen yEvaluación

Toma dedecisión



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

La Investigación de Operaciones tiene sus orígenes durante laSegunda Guerra Mundial cuando existía la necesidad urgentede asignar en forma efectiva los escasos recursos a lasdiferentes operaciones y actividades militares.

Los americanos y británicos encargaron a un grupo decientíficos para que aplicando el método científico resuelvanproblemas como despliegue de radares, colocación de minas,manejo de operaciones de bombardeo y otros problemasestratégicos y tácticos. Los esfuerzos de este primer grupo

científico dieron resultados excelentes.

Al terminar la guerra el éxito de la IO generó gran interés ensus aplicaciones fuera del campo militar como la industria, losnegocios, gobierno, etc.

RESUMEN HISTORICO



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

En 1947 George Dantzing crea el Método Simplex para la

resolución de problemas de programación lineal. Asimismo,

otras herramientas de la IO como la Programación Dinámica,

Líneas de Espera, Teoría de Inventarios, etc.se desarrollaron

antes de 1950 .

La revolución de las computadoras contribuyó al desarrollo de laIO y con ella surgió una nueva herramienta de la IO: la

Simulación.

Actualmente existen sociedades de profesionales de IO como:

INFORMS (Instituto de Investigación de Operaciones y Ciencias

de la Administración) con sede en EE.UU;

IFORS (Federación Internacional de Sociedades de Investigación

de Operaciones) que agrupa a mas de 45 países miembros.

Objetivo: desarrollo de la IO como ciencia unificada y avance en

todas las naciones del mundo.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

ARTE DE LA REPRESENTACION

POR MEDIO DE MODELOS

SISTEMA: Conjunto de partes que interactúan entre si para lograrun conjunto de metas.

MODELOS: representación de objetos o de situaciones reales.

Tipos de Modelos

A) Por su forma de expresión

1.- Modelos Físicos: representación física de la realidad.

Ejm. maqueta de un edificio.

2.- Modelos Abstractos:

2.1. Modelo descriptivo:

Forma de expresión: lenguaje natural.

Metodología para solucionar el problema: sentido común



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

2.1. Modelo Matemático

Forma de expresión: en forma cuantitativa mediante símbolos y

expresiones matemáticos.

Metodología para solucionar el problema: método matemático

Características

Describe el problema en forma concisa

Facilita el manejo del problema y de sus interrelaciones

Facilita el uso de las técnicas matemáticas en computadoras

Entrega soluciones hallados con técnicas matemáticas que

pueden ser las óptimas.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r


6

Modelos de SimulaciónSimula el sistema real.

En IO, un modelo de simulación es un conjunto de pasosenlazados lógicamente que simulan el comportamiento delsistema real y en el que se experimentarán las posibles

soluciones.Características:

Se utilizan en problemas cuya representación matemática esmuy compleja

Puede llevarse a cabo usando muchos lenguajes de

programación de computadoras y paquetes ya construidos Mide la calidad de la solución sugerida.

Se puede determinar una buena solución, no necesariamente laóptima



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r i a l y d e S i s t e m a s

6

B).- Modelos Matemáticos según su estructura

Modelo determinístico

Los datos o parámetros del sistema son conocidos con certeza.

Modelo probabilístico

Algunos parámetros son de tipo probable

Modelo lineal

Las relaciones funcionales son de tipo lineal Modelo no lineal

Algunas relaciones funcionales son no lineales

Modelo Continuo

Las variables de decisión pueden tomar valores fraccionarios

Modelo DiscretoUna o mas variables de decisión toman valores enteros

Modelo estàtico

Las propiedades y relaciones funcionales no sufren cambios en el tiempo.

Modelo dinámico:

El tiempo juega en él un rol muy importante.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

Técnicas de la IO

Los modelos utilizados en la IO son :

Modelos matemáticos

Modelos de simulación

En los modelos matemáticos

Los problemas de optimización planteados dieron origen a una

variedad de técnicas:

La programación lineal

La Programación lineal entera

La Programación no lineal

La programación dinámica

La programación de metas

La programación de redes, etc.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

1.- DEFINICION DEL PROBLEMA

Comprende:

• Determinar claramente el o los objetivos del estudio

• Identificar las partes de la organización involucrados en el

estudio .• Recolección de datos relevantes

2.- FORMULACION DEL MODELO

Dependiendo de la definición del problema, el analista decideel tipo de modelo mas adecuado para representar el problema.

El modelo debe expresar en forma cuantitativa el objetivo del

estudio y las limitaciones o restricciones del problema

Metodología de la Investigación de Operaciones



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

3.- SOLUCION DEL MODELO

En Modelos de simulación:El concepto de optimidad no está tan bien definido y la solución sonbuenas y factibles pero no necesariamente la òptima.

Para obtener la solución se utiliza la computadora en el cual seprograma los pasos indicados en el modelo o bien se utilizan los

paquetes ya diseñados para este fin. (GPSS, Estela, Promodel, etc)En Modelos Matemáticos:

Se utilizan técnicas de optimización bien definidos llamadosalgoritmos los cuales en forma iterativa halla la solución óptima.

Sin embargo, existen problemas con ciertas características que:

- necesita de muchas iteraciones para solucionarlos, ó

- a veces es imposible hallar una algoritmo de solución.

Entonces, existen otros métodos prácticos (heurísticos) basadas enreglas prácticas con el cual se obtiene una buena solución en forma

rápida y simple. Ejm. Problemas de redes.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

4.- VALIDACION DEL MODELOEl modelo debe ser verificado y probado completamente para

asegurar que ofrece una representación suficientemente precisa

del problema real.

El ensayo y validación del modelo se llevan a cabo

frecuentemente con problemas “de práctica” relativamente

pequeños cuyas soluciones son conocidos o esperados.

5.- GENERACION DE INFORMES E IMPLEMENTACION

Presentar un informe con los resultados del modelo que sea de

fácil comprensión para quien toma las decisiones. El informetambién debe incluir la decisión recomendada y cualquier otra

información respecto a los resultados que sean de utilidad para

el tomador de decisiones.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

CAPITULO II

PROGRAMACION LINEAL

Es una de las técnicas mas potentes de la IO, debido a suflexibilidad para describir situaciones reales. Ha sido

desarrollado para representar y solucionar problemas de

decisión que implican la optimización (maximización o

minimización) de una función lineal sujeta a restricciones

lineales.

Se aplica en diferentes campos: industrial, militar, financiero,

salud, informática, etc.

Es una herramienta determinística. Para compensar esta

situación, una vez hallada la solución óptima la IO proporcionael “Análisis de sensibilidad”.



U n i v e r

s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

Estructura de un modelo de programación lineal

Un Problema de programación lineal tiene:

Variables de decisión: son aquellas definidas por el analista

cuyos valores van a solucionar el problema

Función Objetivo (FO): Es aquella función lineal que se va a

optimizar (Maximizar o Minimizar)

Restricciones: representan las limitaciones que tiene el

problema.

Restricciones estructurales: son inecuaciones lineales de tipo

>=, <= o = que un valor b.Signo de las variables

Las variables de decisión pueden ser de tipo: >=0, <= 0 o sin

restricción de signo (srs)



U n i v e r s i d a d


F a c u l t a d

d e

I n g e n i e r i a


6

Forma general de un modelo de programación lineal

Sea Xi las variables de decisión del problema, (i= 1,2,..n)

FO: Max (ó Min) Z = c1x1 + c2X2 + ….. + cnXn

Sujeto a (s.a.):

a11X1 + a12X2 + a13X3 + …… + a1nXn ≤ b1

a21X1 + a22X2 + a23X3 + …… + a2nXn ≥ b2

…. ……….. ……… …………. .. ………. = …..

am1X1 + am2X2 + am3X3 + …… + amnXn bm

Xi (>=0, <=0, srs)





F a c u l t a d

d e

I n g e n i e r i a


6

MODELOS IDEALES

a).- PL MAX IDEAL

PL que tiene:

* Todas sus restricciones de tipo ≤

* Xi ≥0

Max Z = c1x1 + c2X2 + ….. + cnXn

s.a:

a11X1 + a12X2 + a13X3 + …… + a1nXn ≤ b1

a21X1 + a22X2 + a23X3 + …… + a2nXn ≤ b2

…. ……….. ……… …………. .. ………. ≤ …..

am1X1 + am2X2 + am3X3 + …… + amnXn ≤ bm

Xi ≥ 0





F a c u l t a d

d e

I n g e n i e r i a


6

b).- PL MIN IDEALPL que tiene:

* Todas sus restricciones de tipo ≥

* Xi ≥0

Min Z = c1x1 + c2X2 + ….. + cnXn

s.a:

a11X1 + a12X2 + a13X3 + …… + a1nXn ≥ b1

a21X1 + a22X2 + a23X3 + …… + a2nXn ≥ b2…. ……….. ……… …………. .. ………. ≥ …..

am1X1 + am2X2 + am3X3 + …… + amnXn ≥ bm

Xi ≥ 0





F a c u l t a d

d e

I n g e n i e r i a


6

Ejemplo de un problema de programación lineal

Una fábrica produce pinturas para exteriores y para interiores de casas, paradistribuirlos al por mayor.

Para producir las pinturas se utilizan dos materiales básicos A y B. Ladisponibilidad máxima de A es de 60Tn y la de B es de 80Tn por día. Lanecesidad diaria de materia prima por cada Tn de pintura es el siguiente:

Pintura para exteriores: 1Tn de materia prima A y 2 Tn de materia prima B

Pintura para interiores: 2 Tn de materia prima A y 1 Tn de materia prima B

Un estudio de mercado ha establecido que la demanda diaria de pintura parainteriores no puede ser mayor que la de pintura para exteriores en mas de 10Tn. Asimismo, el estudio señala que la demanda máxima de pintura parainteriores está limitada a 20 Tn diarias.

El precio al por mayor por Tn es de $3000 para la pintura de exteriores y de$2000 para la pintura para interiores.

¿Cuánta pintura para exteriores e interiores debe producir la compañía todoslo días para maximizar el ingreso total?

Nota: Suponga que todo lo que se produce se vende.




N a c i o n a l d

e I n g e n i e r í a

F a c u l t a d

d e

I n g e n i e r i a


6

FORMULACION DEL PL

Sea X1: tn de pintura para exteriores a producir y vender por día

X2: tn de pintura para exteriores a producir y vender por día

FO: Max Z = 3000X1 + 2000X2s.a.

X1 + 2X2 ≤ 60 (1)

2X1 + X2 ≤ 80 (2)

X2 – X1 ≤ 10 (3)

X2 ≤ 20 (4)

X1, X2 ≥ 0




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


6

Suposiciones de la Programación lineal

Un problema de programación lineal satisface:

1.-Suposición de certidumbre

Los parámetros del sistema se conocen con certeza

2.- Suposición de divisibilidad

Las variables pueden tomar valores fraccionarios (valores reales)

3.- Suposición de proporcionalidad

La contribución de cada variable a al función objetivo y al lado

izquierdo de cada restricción es proporcional al valor de la variable4.- Suposición de Aditividad

La contribución de cada variable a al función objetivo y al lado

izquierdo de cada restricción es independiente de los valores de las

otras variables.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


6

Formulación de Problemas de Programación Lineal

Para la formulación del problema como un modelo de

programación lineal (PL), se debe tener en cuenta lo siguiente:

El modelo es la representación del problema. Por lo tanto no se

debe agregar ni quitar restricciones que no están en el problema.No debe tratar de solucionarlo mientras formula.

En cada restricción tome en cuenta que las unidades debe ser la

misma tanto en el lado izquierdo como en el lado derecho.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t r i a l y d e S i s t e m a

s

6

CAPITULO III

SOLUCION DE PROBLEMAS DE PL

La solución de un PL consiste en determinar los valores de las

variables que cumplan con todas las restricciones y den el mejor

valor para la F.O.

METODOS PARA LA SOLUCION DE un PL

1.- Método gráfico

Consiste en graficar las regiones que cumplan con cada una de

las restricciones. La intersección de dichas regiones forma el

espacio de soluciones factibles del PL (región factible).

La recta de la FO se fija en un punto de la región factible, luegose desplaza sobre ella en la dirección en el cual mejora Z.

El último punto (o puntos) que toca la recta de la FO antes de

abandonar la región factible, es la solución óptima.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

EJEMPLO:

1.- Sea el siguiente PL

Max Z = 2X1 + 3X2

s.a.

2X1 + X2 ≤ 230 (1) X1 + 2X2 ≤ 250 (2)

X2 ≤ 120 (3)

Xi ≥0

O

AB

C

D

(1)

(2)

(3)

Z

X2

X1

Z

Solución óptima:

X1= 70 , X2= 90 (punto C)

Zop = 410

Región

Factible




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Tipos de regiones

factibles:

Las regiones factibles

pueden ser:

A) cerrado

B) abierto

C) un segmento de recta

D) un punto

A

B

C

Z

X2

Regiónfactible

abierto

X1




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

2.- Problema

Bevco produce una bebida Cifrut con sabor a naranja que se

obtiene al mezclar refresco con sabor a naranja y jugo de

naranja. Cada Oz de refresco de naranja contiene 0.5 Oz de

azúcar y 1 mg de vitamina C. Cada Oz de jugo de naranja

contiene 0.25 OZ de azúcar y 3 mg de vitamina C.A Bevco le cuesta 2 centavos cada Oz de refresco de naranja y 3

centavos cada Oz de jugo de naranja. El departamento de

mercadotecnia de Bevco ha decidido que cada botella de 40 Oz

de Cifrut debe contener por lo menos 80 mg de vitamina C y a

lo mas 20 Oz de azúcar.Formule y determine la solución óptima del problema para

satisfacer sus necesidades al menor costo..




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

El modelo:

Sea X1: Oz de refresco de naranja en 1 botella de CifrutX2: Oz de jugo de naranja en 1 botella de Cifrut

MinZ = 2X1+ 3X2

s.a.0.5 X1+ 0.25X2 ≤ 20

X1 + 3X2 ≥ 80

X1 + X2 = 40

Xi ≥0

Solución óptima (Punto B)

X1=20, X2=20 Zop= 100

(1)

(2)

(3)

Z

A

B

X2

X1

Región

factible




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

2.- Método Algebraico- Método Simplex

El método Simplex es un método iterativo que empieza con unasolución factible y en cada iteración obtiene una nueva soluciónque mejora Z, hasta encontrar la solución óptima, si existe.

Características

El método simplex soluciona modelos que tienen una formaespecífica conocida como forma estándar. Las restricciones deeste PL son ecuaciones.

El método simplex divide las variables del PL en dos grupos:

Variables Básicas (VB) y

Variables No Básicas (VNB)

El método simplex utiliza el Método de Gauss-Jordan parasolucionar el sistema de ecuaciones.

El método simplex halla soluciones básicas factibles (sbf)

sbf: solución que se encuentra en la intersección de las rectas (oplanos o hiperplanos) de las restricciones.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

FORMA ESTANDAR DE UN PL Es un PL que tiene las siguientes características:

F.O. : Max ó Min

Los lados derechos de las restricciones son ≥0

Las restricciones son igualdades Las variables son ≥0

Nota:

La forma estándar es un PL equivalente al original, por lo

tanto la solución óptima de la forma estándar lo es del PLoriginal.

Si la forma estándar es un PL no factible entonces el PLoriginal también lo es.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t

r i a l y d e S i s t e m a

s

6

Conversión de un PL en Forma Estándar

1.- Restricciones:

Restricción ≤ : Para convertirla en = se le adiciona una variable

de holgura Si (Si ≥0), que representa la cantidad de recursos no

utilizados, demanda insatisfecha, etc.

Ejm.3X1+ 4X2 + 2X3 ≤ 500 …….. (1)

3X1+ 4X2 + 2X3 +S1 = 500 …… (1)

Restricción ≥: Para convertirla en = se le agrega una variable deexceso Ei (Ei ≥0), que representa la cantidad excedente al

requerimiento mínimo.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

Ejm.

4X1+2X2+X3 ≥ 100 ……. (2)

4X1+2X2+X3 + e2 = 100 …(2)

Nota: Los coeficientes de Si y Ei en la función objetivo son cero.

2.- Variables

Variable Xi ≤0: Se hace un cambio de variable

Xi = - Xi’, tal que Xi’≥0

Variable Xi srs: Esta variable se reemplaza por la diferencia dedos variables no negativas

Xi = Xi’ – Xi” , tal que Xi’ y Xi” ≥0

Ejemplo.




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

VARIABLES BASICAS Y VARIABLES NO BASICAS Un PL preparado para el Método simplex (forma estándar

preparado) tiene:

n variables y m restricciones tal que n >m

Para resolver el sistema de ecuaciones, es necesario agrupar las

variables en dos grupos:

VB: m variables para resolver el sistema de m ecuaciones

VNB: n-m variables que toman el valor arbitrario cero

SOLUCION BASICA DEL PL

Está formado por la unión del conjunto de VB y VNB




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

EJEMPLO:PL original PL estándar

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

s.a. s.a.

2X1 + X2 ≤ 230 … (1) 2X1+X2 + S1 = 230 ... (1)

X1 + 2X2 ≤ 250 … (2) X1+2X2+ S2 = 250 … (2)

X2 ≤ 120 … (3) X2+ S3 = 120 … (3)

Xi ≥0 Xi, Si ≥0

Número de Variables = n=5

Número de VB = número de restricciones = m =3

Número de VNB = n-m = 5-3 = 2




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

Método Simplex

PASOS

1.- Determinar la solución inicial

Usando la forma estándar del PL original, determinar la sbf

inicial el cual está formado por:

VB: las variables de holgura de cada restricción

VNB: las demás variables del PL2.- Seleccionar la VNB entrante, utilizando la condición de

optimidad.

Condición de optimidad: la VNB que entra debe ser aquella

que tenga el mejor coeficiente para mejorar Z. Un empate serompe arbitrariamente

El óptimo se alcanza cuando todas las VNB tienen coeficientes

desfavorables para Z




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

3.- Seleccionar la VB saliente, utilizando la condición de

factibilidad.

Condición de factibilidad: el valor que tome la variable

entrante debe ser de tal manera que las otras variables básicas

sigan siendo factibles. Esta condición es la que determina la

variable que sale.Un empate se rompe arbitrariamente.

4.- Determinar la nueva solución

Realizar las operaciones matemáticas para determinar el valor

de las nuevas VB y el valor de Z

5.- Volver al paso 2

Ejemplo: realizar el simplex algebraico para el problema




N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

El método simplex realiza todas sus operaciones matemáticas en el

Tablero Simplex, el cual tiene la siguiente estructura:

Características de un Tablero Simplex en cualquier iteración

Los coeficientes de las VB en la fila Z, tienen valor cero.

Los coeficientes de la VB en las restricciones forman la matriz

identidad

Todas las variables del modelo

VB

Z Coeficientes de las variables en la fila Z

Solución

Valor de Z

Coeficientes de las variables en

las restricciones

Valores

de las

VB

r

Método Simplex Tabular



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

PASOS (METODO SIMPLEX TABULAR)

0.- Acondicionar la F.O.

Escribir la F.O. como si fuera una restricción

Ejm. Max Z = 2X1+ 3X2

Se escribe: Max Z – 2X1 - 3X2 = 0

1.- Determinar la SBF inicial

VB: Las variables de holgura de cada restricción

VNB: Las demás variables

2.- Seleccionar la VNB entrante

PL Max:

Seleccionar la VNB con C’< 0. Si hay varias, se escoge la que

tiene el coeficiente mas negativo.

Si todas las variables tienen C’≥ 0, se ha llegado al tablero final



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

PL Min

Seleccionar la VNB con C’> 0. Si hay varias, se escoge la quetiene el coeficiente mas positivo.

Si todas las variables tienen C’≤ 0, se ha llegado al tablero final.

En cualquier caso, un empate se rompe arbitrariamente.

3.- Seleccionar la VNB saliente:La VB que sale es aquella que tiene la menor razón r.

valor de la columna solución

coef. positivo de la VNB entrante

Un empate se rompe arbitrariamente.4.- Nueva solución:

Realizar las operaciones necesarias (Gauss-Jordan) para obtener

el nuevo Tablero Simplex

5.- Volver al paso 2.

r =



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

EJERCICIOS

Hallar la solución óptima de los siguientes PL ideales1) Max Z = 2X1 + 3X2

s.a.

2X1 + X2 ≤ 230 (1)

X1 + 2X2 ≤ 250 (2)

X2 ≤ 120 (3) Xi ≥0

2) Max Z = 60X1 + 30X2 + 20X3

s.a.

8X1 + 6X2 + X3 ≤ 480 (1) 4X1 + 2X2 + 1.5X3 ≤ 200 (2)

2X1 + 1.5X2 + 0.5X3 ≤ 80 (3)

Xi ≥0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

Solución artificial para el Método Simplex

Si un PL tiene restricciones de tipo ≥ ó = (las cuales no tendrán

variables de holgura) entonces existe un problema para formarla sbf inicial del método simplex.

Entonces, a las ecuaciones que no tienen variables de holgura,

se le agrega una variable artificial ai (ai ≥0 ). Estas variables

artificiales serán utilizadas como “variables de holgura” paraformar la sbf inicial del simplex.

Ejm 3X1+4X2 ≥ 100 .. (1) ; 2X1+3X2 = 60 … (2)

3X1+4X2 – e1+a1 = 100 (1) 2X1+3X2+ a2 = 60 ..(2)

Las variables artificiales no tienen significado físico para el

modelo, por lo tanto se deben tomar medidas para llevarlas a

nivel cero en la solución óptima. Para este propósito existen

métodos como:

Técnica M ó método de la penalización

La técnica de las dos fases.



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a

I n d u s t


s

6

Técnica M (ó Método de la Penalización)

Pasos1.- Agregar las variables artificiales a las ecuaciones que no tienen

variables de holgura.

2.- Penalizar a las variables artificiales dándoles en la F.O. un coeficientegrande M (M>>0)desfavorable.

Para un PL Max:Max Z= C1X1+ …… +CnXn – Ma1 – Ma2 - ….

Para un PL Min:

Min Z= C1X1+….. + CnXn + Ma1 + Ma2 + …

3.- Acondicionar la fila Z :

Las variables artificiales formarán parte de las VB iniciales, entoncesdeben tener coeficiente cero en la fila Z. De esta manera se tendrá unasolución inicial artificial para el simplex.

4.- Realizar las operaciones comunes del método simplex para buscar lasolución óptima, si existe.



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Ejemplo:

Min Z = 3X1+ 5X2 + 4X3s.a.

2X1+ 4X2 +2X3 ≤ 80

3X1 + 4X2 +X3 ≤ 100

X1 + X2 +X3 = 30

X3 ≥ 15 Xi ≥0

Técnica M

Min Z= 3X1 + 5X2 +4X3 + Ma3 + Ma4

s.a.

2X1 + 4X2 +2X3 + S1 = 80 …... (1)

3X1 + 4X2 + X3 + S2 = 100 ….. (2)

X1 + X2 +X3 + a3 = 30 ……. (3)

X3 – e4 + a4 = 15 ……. (4)

X1, X2, S1, S2, a3, e4, a4 ≥0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Acondicionando Z:

Primera formaLas ecuaciones (3) y (4) se suman y se despeja:

a3 + a4 = 45 – X1 – X2 – 2X3+ e4

Reemplazando en la F.O.

Min Z = 3X1+5X2 +4X3 + M (45-X1- X2-2X3 +e4)

= (3-M)X1 + (5-M)X2 + (4-2M)X3+ Me4 + 45M

Escribiendo la F.O. como restricción:

Min Z + (M-3)X1 + (M-5)X2 + (2M-4)X3 – Me4 = 45M

Segunda forma:

Utilizando el método simplex matricial

Pasar al Tablero Simplex donde la solución inicial será:

VB: S1, S2 a3, a4

VNB: X1, X2, X3, e4

Valor inicial de Z: 45M



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Casos Especiales

PL CON SOLUCIONES OPTIMAS ALTERNATIVAS

Es aquel PL que tiene mas de una solución óptima para el mismo valorde Zop.

Gráficamente:

La recta Z es paralela a una restricción límite antes de salir

En el Simplex:

La solución es óptimaExiste una VNB que tiene coeficiente 0 en la fila Z y que al entrar ala base se halla otra solución, pero Zop no cambia.

Ejm.

Max Z= 2X1+ 4X2

s.a.X1 + 2X2 ≤ 100

X1 + X2 ≤ 80

X1 + X2 ≥ 20

Xi ≥0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

PL NO ACOTADO

Es aquel PL que tiene soluciones factibles pero no tiene soluciónóptima.

Gráficamente:

El PL no acotado tiene región factible abierto.

En el PL no acotado la recta Z nunca sale de la región factible

En el Simplex:El tablero no es óptimo

Existe VNB que entra pero no existe VB que sale (no existe r)

Ejemplo:

Max Z= 2X1+ 4X2

s.a.

X1 + 2X2 ≥ 100

X1 + X2 ≥ 80

X1 ≤ 100

Xi ≥0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

PL NO FACTIBLE

Es aquel PL que no tiene soluciones factibles.Gráficamente:

No existe región factible.

En el Simplex:

El último Tablero Simplex tiene como VB a variable(s)artificial(es) con valor >0

Ejemplo:

Max Z= 2X1+ 3X2

s.a.

X1 + 2X2 ≤ 100 X1 + X2 ≤ 80

X2 ≥ 60

Xi ≥0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Método Simplex Matricial

Sea el siguiente PL estándar de n variables (incluye variables de

holgura, exceso y artificiales) y m restricciones:

Max (Min) Z = c1X1+c2X2 + ……. + cnXn

s.a.

a11X1+a12X2 + …….. + a1nXn = b1

a12X1+a22X2+ ……… + a2nXn = b2

..

am1X1+ am2X2+ ……. + amnXn = bm

Xi ≥ 0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Si:

X T = (X1, X2, …., Xn) C = (c1, c2, …., cn)

a11 a12 …. a1n b1

(A, I) = a21 a22 …. a2n b = b2

… ..

am1 am2 …. Amn bm

Entonces el PL se puede escribir en forma matricial:

Max (Min) Z = C X

s.a.

(A, I) X = b

X ≥ 0



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

Tablero simplex matricial

Si el vector de variables se subdivide en dos grupos:

XII = variables básicas iniciales (holgura y artificiales)XI = las otras variables (var de decisión y var de exceso)

De igual manera el vector de coeficientes de la F.O.:

CII = los coeficientes asociados a XII

CI = coeficientes asociados al vector XI

a). Tablero simplex inicial

XII

Z

Solución

CII b

b

CIIA - CI 0

XI XII

CI CII

CII A I



U n i v e

r s i d a d

N a c i o n a l d


F a c u l t a d

d e

I n g e n i e r i a


s

6

b). Tablero simplex en cualquier iteración

Sea: XB = variables básicas en la iteraciónCB = coeficientes asociados a las variables básicas

B = matriz de coeficientes de las variables básicas (en el

orden en que se han colocado XB

B-1

= matriz inversa de BEl tablero simplex en esta iteración es:

XB

Z

Solución

CB B-1 b

B-1 b

CBB-1A - CI CBB-1 - CII

XI XII

CI CII

CB B-1A B-1

Io St113 Parte i

Documents

Transcript of Io St113 Parte i