Io St113 Parte i

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

http://slidepdf.com/reader/full/io-st113-parte-i-55a4d6d2c5d40 1/56

UNIVERSIDAD NACIONAL DE INGENIERIAFacultad de Ingeniería Industrial y de Sistemas

Area de Sistemas y Telemática

INVESTIGACION DE OPERACIONES I

PARTE I

Profesora: Ing. IRMA INGA SERRANO

2011



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)



6

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 simplex

Casos especiales de PLMétodo simplex matricial

EXAMEN PARCIAL

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

CONTENIDO DELCURSO



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´

INTRODUCCION



6

Proceso de toma de decisiones

en la solución de un problema

Definir el

problema

Determinar los criterios de

evaluación

Análisis

cualitativo

Análisis

cuantitativo

Resumen y

Evaluación

Toma de

decisión



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 resuelvan

problemas 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



6

En 1947 George Dantzing crea el Método Simplex para laresolució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 Cienciasde 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.



6

ARTE DE LA REPRESENTACION

POR MEDIO DE MODELOS

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

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

Tipos de ModelosA) 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



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.



6

Modelos de Simulación

Simula 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



6

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

Modelo determinísticoLos 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.



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.



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



6

3.- SOLUCION DEL MODELO

En Modelos de simulación:

El concepto de optimidad no está tan bien definido y la solución son buenas y factibles pero no necesariamente la òptima.

Para obtener la solución se utiliza la computadora en el cual se programa 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.



6

4.- VALIDACION DEL MODELO

El 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 cabofrecuentemente 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.



6

TECNICA DE

PROGRAMACION LINEAL

Es una de las técnicas mas potentes de la IO, debido a su

flexibilidad 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 restriccioneslineales.

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



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)



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 + «.. + cnXnSujeto a (s.a.):

a11X1 + a12X2 + a13X3 + «« + a1nXn b1

a21X1 + a22X2 + a23X3 + «« + a2nXn b2

«. «««.. ««« ««««. .. «««. = «..

am1X1 + am2X2 + am3X3 + «« + amnXn bm

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



6

Problema

DFC es una empresa que fabrica escritorios, mesas y sillas. Para la

manufactura de cada tipo de mueble de requiere de madera y dos tipos de

mano de obra calificada: acabado y carpintería. La cantidad de recursos

necesarios para elaborar cada tipo de mueble se da en la siguiente tabla:

Madera Acabado Carpintería

MUEBLE (pie-tablón) (Hr) (Hr)

Escritorio 8 4 2

Mesa 6 2 1.5

Silla 1 1.5 0.5

Semanalmente se cuenta con 480 pies tablón de madera, 200 horas de

acabado y 80 horas de carpintería.

Un escritorio se vende en $60 , una mesa en $30 y una silla en $20. La

empresa opina que la demanda de escritorios y sillas es ilimitada pero

que se puede vender a lo mas 5º mesas semanales.

Formule el problema como un PL para maximizar los ingresos semanales

de la empresa, suponiendo que todo lo que se produce se vende y que las

variables aceptan valores fraccionarios.



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.



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

«. «««.. ««« ««««. .. «««. «..


Xi 0



6

b).- PL MIN IDEAL

PL 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«. «««.. ««« ««««. .. «««. «..


Xi 0



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.



6

Problem de producciòn

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



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 + 2000X2

s.a.

X1 + 2X2 60 (1)

2X1 + X2 80 (2)

X2 ± X1 10 (3)X2 20 (4)

X1, X2 0



6

CAPITULO III

SOLUCION DE PROBLEMAS DE PL

La solución de un PL consiste en determinar los valores de lasvariables 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.



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



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

factible

abierto

X1



6

2.- ProblemaBevco 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..



6

El modelo:

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

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



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 forma

especí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 (o planos o hiperplanos) de las restricciones.



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.



6

Conversión de un PL en Forma Estándar1.- 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.



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.



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



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



6

Método Simplex

PASOS1.- 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 PL

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



6

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

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



6

El método simplex realiza todas sus operaciones matemáticas en elTablero 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



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 = 01.- 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



6

PL Min

Seleccionar la VNB con C¶> 0. Si hay varias, se escoge la que

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



6

EJERCICIOS

Hallar la solución óptima de los siguientes PL ideales

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



6

Solución artificial para el Método Simplex

Si un PL tiene restricciones de tipo ó = (las cuales no tendránvariables de holgura) entonces existe un problema para formar

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



6

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

1.- Agregar las variables artificiales a las ecuaciones que no tienenvariables 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.



6

Ejemplo:

Min Z = 3X1+ 5X2 + 4X3

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



6

Acondicionando Z:Primera forma

Las 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



6

EJEMPLO 2Sea el siguiente PL:

Max Z = 3X1+4X2 + X3

S.a.

12x1+16x2+4x3 4500X1+2X2+X3 400

X1+X2+X3 300

X3 50

Xi 0



6

Casos Especiales

PL CON SOLUCIONES OPTIMAS ALTERNATIVASEs aquel PL que tiene mas de una solución óptima para el mismo valor de Zop.

Gráficamente:

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

En el Simplex:

La solución es óptima

Existe 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



6

PL NO ACOTADOEs 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



6

PL NO FACTIB

LEEs 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



6

Método Simplex Matricial

Sea el siguiente PL estándar de n variables (incluye variables deholgura, 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



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



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



6

b). Tablero simplex en cualquier iteración

Sea: XB = variables básicas en la iteración

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

CBB-1 b

B-1 b

CBB-1A - CI C

BB-1 - CII

XI XII

CI CII

CB B-1A B-1



6

Cálculo de la matriz inversa con Excel

Pasos

1.- Escribir la matriz A de nxn

2.- En otro lado, seleccionar una matriz de nxn para el cálculo de A

(automáticamente la primera celda de A se encuentra

seleccionada para escribir alguna función.)

3.- Escribir (sobre la 1ra celda de A ) lo siguiente:

=MINVERSA(seleccionar la matriz A)

ctrl + shift () + enter

Se obtiene la matriz inversa de A.

4.- Si se desea, se puede dar formato a las celdas para mostrar los

números como fracciones (formato celdas fraccion).



6

Ejemplo:

Sea la siguiente

matriz A de 3x3

Matriz

inversa de A

Documents

Io St113 Parte i