Mit Apunte Investigación Operativa PDF

MOVIMIENTO DE INCLUSIÓN TOTAL
Apunte de Investigación Operativa
INVESTIGACIÓN
OPERATIVA
Introducción a la IO
La IO es una es una ciencia de la administración basado en el uso de las matemáticas y las

computadoras para ayudar a la toma de decisiones racionales frente a problemas de la
administración complejos de la vida real.
La IO eleva la habilidad de un gerente para hacer planes a largo plazo, resolver problemas diarios y
predecir nuevos posibles problemas.
Aunque algunos problemas son lo suficientemente simple como para que un administrador pueda
aplicar su experiencia personal para resolverlos, en el complejo mundo actual muchos problemas no
pueden resolverse de esta manera. La evaluación y análisis de cada alternativa es difícil o requiere
demasiado tiempo, además el número de soluciones alternativas puede ser tan grande que el
gerente no puede evaluarlas a todas para elegir la más apropiada.
Historia de la IO
Generalmente se atribuye a los inicios de la IO a los servicios militares durante la 2° Guerra Mundial
donde era necesario e importante asignar recursos escasos de la manera más efectiva posible.
La fuerza Aérea británica formo el primer grupo para tratar estos problemas operacionales mediante
métodos cuantitativos. Poco después las fuerzas militares estadounidenses formaron un grupo
similar.
Después de la 2° Guerra Mundial los administradores en general reconocieron el valor de aplicar
técnicas derivadas de la IO por lo que en 1950 se introdujo la IO en la industria de los negocios y el
gobierno.
A fines de la década del 50’ muchas de las herramientas de la IO como PL, colas y teoría de
inventarios ya estaban completamente desarrolladas.
Un avance más tuvo lugar en 1980 con el desarrollo de la computadora personal ya que ofrecía una
mayor capacidad de procesamiento con respecto a los seres humanos.
1
Recopilación de Material Digital para el Final de Investigación Operativa
METODOLOGIA DE LA IO:
1º PASO: Formular el problema. Definir costos, objetivos, aspectos financiero etc. ¿A cuántos
clientes puede atender un cajero en un ahora?
2º PASO: Observar el Sistema. Recolectar Datos, Definir Alcances (qué elementos estarán dentro del
sistema y cuáles no). ¿Cuántos clientes llegan cada hora?
3º PASO: Formular un modelo matemático para el problema. Se realiza una representación
idealizada. MODELO es una abstracción del mundo real.
4º PASO: Verificar el modelo y utilizarlo para predicciones.
• Se debe construir un modelo matemático de forma que se ajuste a la realidad.
• Si el modelo construido no se ajusta, se lo debe corregir, ya sea por completo o tan solo
algunas variables.
• Si el modelo se ajusta solo en un intervalo, se lo puede tomar, adoptando entonces dichas
restricciones.
Lo ideal es que se pueda prescindir del sistema en que se basa el modelo y utilizar este último para
trabajar.
5º PASO: Selecciona un modelo Adecuado: ver si el modelo se adapta a los objetivos (que pueden
ser diversos)
6º PASO: Presentación de Resultados y conclusión del estudio de la organización
7º PASO: Implantar y evaluar recomendaciones
Aplicación de la IO
Problemas de Inventario y Producción:
Por ejemplo una empresa cervecera que tiene varias sucursales donde sus productos varían en
disponibilidad, precios, costo, etc.
• Problemas de Maximización:
Una empresa busca una combinación de sus recursos que dispone para generar la máxima ganancia
• Problema de planeación Laboral:
Un hospital que cuenta con una determinada capacidad de contratación deberá determinar la
velocidad para contratar un nuevo personal
• Problema de Transporte:
Una empresa de encomiendas desea reducir los costos de transporte y distribución a partir de la
minimización del recorrido a realizar. (Camino más corto)
• Problema de la línea de espera:
Por ejemplo una sala de urgencias debe determinar el número necesario de profesionales médicos
para pacientes que llegan a una determinada franja horaria de manera que los médicos no tengan
tiempo ocioso ni los pacientes esperen demasiado poniendo en riesgo sus vidas
2
Ingeniería de Sistemas
La Ing. de Sistemas es el ARTE y la CIENCIA de seleccionar de entre un gran número de alternativas
posibles con un abundante contenido de metodologías de ingeniería, aquel conjunto de acciones que
satisfagan mejor los objetivos totales de quienes toman las decisiones, siempre respetando las
restricciones legales, económicas, morales, de recursos, sociales, políticas y las leyes que gobiernan
las diversas ciencias físicas, biológicas y demás ciencias naturales.
ARTE: es la parte intuitiva, empírica
CIENCIA: Es la magnitud de los procesos de decisión.
SISTEMA: Es un conjunto de objetos que interaccionan de manera regular e independiente. La IS se
ocupa de aquellos aspectos del sistema que pueden ser controlados de manera de alcanzar los
objetivos deseados
Controladas Deseables
Parcialmente Controladas Sistema Indeseables
No Controladas Neutrales
Realimentación
• Variables de estado
• Relaciones Funcionales
• Parámetros
Caracterización del Sistema

FRONTERA del SISTEMA: Es una regla que determina si cualquier objeto puede ser considerado
como parte del sistema o si es parte del medio que lo rodea. La frontera divide al universo en 2
partes, el medio y el sistema. A su vez, un mismo sistema puede estudiarse considerando diversas
fronteras.
• La interacción entre el Sistema y el Medio se realiza a través de las variables de E/S
(estudiando al sistema como parte del medio ambiente)
• Las interacciones internas entre las variables de estado del sistema
• Las interacciones externas entras las variables de E y S. Esto es la Retroalimentación.
Estado del Sistema: Condiciones en la que se encuentra el sistema
Terminología y conceptos:
VARIABLES DE ESTADO: Representan el estado del sistema. Corresponden a un conjunto de valores
necesarios para describir el sistema en un determinado momento.
VARIABLES de DECISION: Son variables de Entrada controlables y parcialmente controlables
RESTRICCIONES: Son Limitaciones impuestas en el rango de valores que pueden asumir las variables
de decisión
POLITICAS: Es el conjunto de valores particulares asignados a las variables de decisión.
POLITICAS FACTIBLES (PF) es toda política que no viola ninguna restricción.
3
ESPACIO DE POLITICAS FACTIBLES (EPF): Es el conjunto compuesto por todas las PF. Un EPF no
siempre es estático, porque varían las restricciones o las variables de decisión con el tiempo.
EPF CONVEXO y NO CONVEXO: Un EPF es convexo cuando 2 puntos cualesquiera del EPF forman un
segmento contenido totalmente dentro del EPF.
NO
Convex Convex
o o
PARAMETROS del SISTEMA: Son variables que no cambian sensiblemente de valor durante el
análisis, por lo que se consideran constantes.
OBJETIVO: Es la meta a la cual se quiere llegar y tiene implícito el criterio en base al cual se quiere
determinar la salida del sistema para una cierta entrada controlada. Un objetivo es la suma de
muchos sub objetivos.
Existen distintos tipos de objetivos:
• CUANTITATIVOS: son aquellos que son mesurables con cierta exactitud numérica
• NO CUANTITATIVOS: son mesurables solo cualitativamente.
• NO CONMENSURABLES: No pueden ser expresados en las mismas unidades o el orden de
magnitud de los errores inherentes en la evaluación de uno de ellos esconde el significado de
la magnitud de los otros.
FUNCION OBJETIVA: Es una función escalar que depende de las variables de decisión, de las variables
de estado y de los parámetros y que permite, dada una política, calcular la salida del sistema. Es la
función de respuesta del sistema.
Dadas las limitaciones de este enunciado matemático, vemos que no existe ningún método capaz de
optimizar funciones no conmensurables y menos aun no cuantitativas, por lo que un sistema real no
puede analizarse completamente por la IS, y es necesario hacer simplificaciones en el análisis
cuantitativo.
PASOS PARA LA CONSTRUCCIÓN DE MODELOS MATEMÁTICOS:
1.- ¿Quiénes toman decisiones y cuáles son sus objetivos? Se debe identificar la FO en caso de haber
una sola persona que toma decisiones el objetivo es único en caso de ser varias los objetivos son
múltiples
2.- ¿Cuáles son los factores que están bajo el control de quienes toman decisiones y como afecta a la
solución? Se deben analizar las Variables de Decisión y luego por análisis del modelo se determinaran
sus valores
3.- ¿Cuáles son los rangos de valores permitidos para las variables decisión? Se deben identificar las
restricciones que surjan porque generalmente el problema se encuentra condicionado por
requerimientos económicos, tecnológicos, etc.
4.- ¿Cuáles son los factores incontrolables que influyen en el sistema? Se deben identificar las
variables incontroladas que generalmente se encuentran especificadas o estimadas. Estas variables
se convierten en parámetros
MODELOS:
4
Representación idealizada de un sistema de la vida Real
CLASIFICACION DE LOS MODELOS:
Estaticos
Analogicos/a
Fisicos
Escala
Dinámicos
Numericos
Estaticos
Analiticos
Matematicos
o Simbolicos
Numericos
(Simulacion)
Dinamicos
Analiticos
MODELOS A ESCALA (iónico): Semejanza. Por ejemplo, hay ecuaciones semejantes en geometría,
cinemática y dinámica.
MODELOS ANALOGOS: Fenómenos físicos de distinta naturaleza con ecuaciones con formas
matemáticas idénticas. Por ejemplo, analogía entre las ecuaciones eléctricas e hidráulicas.
MODELOS MATEMÁTICOS o SIMBOLICOS: utiliza letras, números y relaciones matemáticas para
representar las propiedades de un sistema de la vida real. Tiene la ventaja de ser conciso pero tiene
como desventaja el grado de abstracción, lo que requiere experiencia a la hora de construir estos
modelos
Elementos Principales:
• Variables: pueden ser controladas o no controladas, las variables controladas son
generalmente las variables de decisión
• Función Objetivo (FO)
• Restricciones
Función Objetivo (FO):

Z (xi, Sj, Pk) → (MAX); (también puede ser (MIN))
Restricciones:
gi (xi, Sj, Pk) ≤ 0
: : : : ≤:
gm(xi, Sj, Pk)≤ 0
xi 1 ≤ i ≤ k → Variables de Decisión
Sj 1 ≤ j ≤ L → Variables de Estado
Pk 1 ≤ k ≤ t → Parámetros
Es posible reducir el problema real a través de ciertas simplificaciones a algunas de estas herramientas:
• Programación Lineal (PL)
• Programación NO Lineal (PNL)
5
• Programación Dinámica (PD)
• Etc.
PASOS GENERALES y TECNICAS en la CONSTRUCCION de MODELOS MATEMÁTICOS:

1- IDENTIFICAR las Variables de Decisión - ¿Cómo?
a. Qué elementos se pueden elegir o controlar libremente?
b. Qué decisiones deben tomarse?
c. Qué valores constituyen una solución que puede ser transmitida a otra persona?
d. Qué elementos afectan los costos y/o ganancias?
e. Deben estar vinculadas al objetivo general.
2- IDENTIFICAR los DATOS del PROBLEMA: Son elementos de información conocida y necesarios
para llevar adelante el proyecto
3- IDENTIFICAR la FUNCION OBJETIVO: Son los objetivos llevados a términos matemáticos.
4- IDENTIFICAR las RESTRICCIONES

a. Físicas: Ej, restricciones estructurales.
b. Lógicas
Los modelos deben clasificarse:

Pueden ser Deterministicos, cuando los datos se conocen con certeza o Estocásticos, cuando
no.
También pueden ser Restringidos o Irrestrictos.
O Lineales o NO Lineales, según el problema tenga variables enteras o continuas.
INTRODUCCION a la PROGRAMACIÓN LINEAL

¿QUÉ ES UN PROBLEMA DE PROGRAMACIÓN LINEAL?
Consiste en un problema analítico que permite encontrar entre un gran número de soluciones
aquella política única que optimice la FO. Es decir encontrar la mejor de las soluciones factibles
medida por la función objetivo.
La PL es un caso particular de un problema de optimización donde la FO y las restricciones son
lineales en cada una de las variables de decisión involucradas utilizan un modelo matemático para
describir el problema.
El problema general de PL consiste en encontrar un vector (x1,x2,…,xn) que optimice (maximice o
minimice) la forma lineal (o sea la función objetivo) sujeta a restricciones lineales.
Es un método analítico que nos permite encontrar dentro de un gran número de soluciones aquella
política que optimice el valor de la FO.
Es un caso particular de los métodos de optimización y se da cuando tanto la FO como las
restricciones son lineales en cada una de las variables de decisión xi y estas son no negativas.
PROBLEMA DE LA PROGRAMACIÓN LINEAL
Un PL es un problema de optimización en el cual se realiza lo siguiente:
6
a) Se trata de MAX o MIN una función Lineal de variables de decisión que no es más que la FO.
Aquí también se identifica las Variables de decisión y los coeficientes
b) Los valores de cada una de las variables de decisión deben respetar un conjunto de
restricciones que están en forma de ecuación lineal o desigualdades lineales
c) Debe existir una restricción de Signo para cada variable de decisión. Puede ser una variable Xi
→ (Xi>0) o puede ser Xi SRS (sin restricción de signo)
CARACTERISTICAS de un PROBLEMA de PROGRAMACIÓN LINEAL:
• Variables de decisión REALES: Son cantidades numéricas a determinar que representan la
solución del problema. Estos valores son controlables de manera que podemos cambiarlos
para optimizar la solución, son reales porque se obtienen de situaciones reales. Se debe
especificar que representan y en que unidades esta
• Variables de decisión FICTICIAS: son cantidades numéricas que se introducen al modelo con
el objetivo de aplicar artificios matemáticos para llegar a la optima solución del problema.
Pueden ser de EXCESO u OLGURA
• OBJETIVOS
FO → C1x1 + C2x2 + … + Cixi + … + Cnxn
• RESTRICCIONES: son las limitaciones que restringen el rango de valores que pueden tomar
las variables de decisión.
si:
{a11x1 + a12x2 + … + a1jxj + … + a1nxn ≤ b1
{a21x1 + a22x2 + … + a2jxj + … + a2nxn ≤ b2
{ … + … + … + … + … + …
{ai1x1 + ai2x2 + … + aijxj + … + ainxn ≤ bi
{ … + … + … + …. + … + …
{am1x1 + am2x2 + … + amjxj + … + amnxn ≤ bm
Donde las aij, bi y Cj son constantes y m < n

Siempre supondremos que las ecuaciones han sido multiplicadas por -1 cuando sea necesario para
hacer bi >0
Si hay una igualdad en las restricciones, estas son OBLIGATORIAS.
INTERPRETACION DE VARIABLES
aij → Coeficientes tecnológicos, coeficientes de las variables de decisión. Se llaman así puesto que
𝑢𝑅
nos indican la cantidad de recursos utilizados para producir cada unidad de producto. |𝑎𝑖𝑗 | = [𝑢𝑃]
𝑎𝑖𝑗 𝑥𝑖
⏞𝑢𝑅
[ ] 𝑥[𝑢𝑃] = [𝑢𝑅]
𝑢𝑃
bi → Indican la cantidad de recursos de las que se dispone. |𝑏𝑖 | = [𝑢𝑅]
𝑢𝑀
Ci → Es el coeficiente de beneficio (unidad económica) por unidad de producto. |𝐶𝑖 | = [ 𝑢𝑃 ]
FO : Z = 4x1 + 3x2 (MAX)
7
Sa:
−2𝑥1 + 𝑥2 ≤ 2
{ −𝑥1 − 𝑥2 ≤ 2
−. 𝑥1 + 𝑥2 ≤ 5
𝑥1 ; 𝑥2 ≥ 0
• Condición de No NEGATIVIDAD: En la mayoría de los casos las variables de decisión

representan cantidades de material a producir, a almacenar o a transportar, por lo que no
sería posible tener valores negativos.
RESOLUCION DE UN PROBLEMA DE PL
Primero: Identificar las variables de decisión (decisiones de la empresa) (id q representa y unidades)
Segundo: Identificar los datos del problema
Tercero: Formular la FO a optimizar
Cuarto: Especificar las restricciones estructurales de recurso y las rstricciones de signo
SUPOSICIONES:
SUPOSICIONES DE PROPORCIONALIDAD y de ADITIVIDAD
El hecho de que la FO de un PL tenga que ser una función lineal tiene 2 aplicaciones
1- La contribución de cada variable de decisión a la FO es proporcional al valor de dicha
variable de decisión
2- La contribución a la FO por parte de cualquier variable de decisión es independiente de los
valores de las otras variables de decisión.
De manera análoga, el hecho de que cada restricción deba ser una igualdad o desigualdad lineal,
implica que.
1- La aportación de cada variable al lado izquierdo de la restricción es proporcional al valor de
esa variable
2- La contribución de cada variable al lado izquierdo de la restricción es independiente de las
otras variables.
Para que un PL sea una representación apropiada de un problema de la vida real, las variables de
decisión deben satisfacer ambas suposiciones y además deben satisfacer las suposiciones de
divisibilidad y certidumbre.
SUPOSICION DE DIVISIBILIDAD: Requiere que cada variable de decisión pueda tomar valores
fraccionarios
SUPOSICION DE CERTIDUMBRE: Significa que tiene que conocerse con certidumbre cada parámetro.
Si no tuviéramos la cantidad exacta de cada uno de ellos, entonces no se cumple la suposición.
SOLUCION GRAFICA DE PROBLEMAS BIDIMENSIONALES DE PL

Cuando un problema tiene 2 variables de decisión se lo puede resolver GRAFICAMENTE
8
ESPACIO DE PF: se determina por la intersección de los semiplanos determinados por el grafico de las
restricciones.
PASOS A SEGUIR:
1) Se dibujan los ejes cartesianos
2) Sobre este espacio se grafican las restricciones
3) Se dibuja el funcional (la FO) haciendo Z=0
𝑍 = 𝐶1 𝑥1 + 𝐶2 𝑥2
| −𝐶 𝑍|
𝑥2 = 𝐶 1 𝑥1 + 𝐶
2 2
4) Se busca el último punto de contacto entre la RPF y el funcional. Es decir, desplazamos la FO
hasta el límite, donde tenga solo un punto de contacto con la RPF.
La diferencia entre los recursos disponibles y los consumidos, es el exceso o sobrante. Estas son las
VARIABLES DE HOLGURA o de EXCESO. Estas se agregan en las restricciones al momento de realizar el
grafico para poder representar los recursos no utilizados.
Por ejemplo:
−2𝑥1 + 𝑥2 + 𝑥3 =2
{− − − −. 𝑥1 − 𝑥2 + 𝑥4 =2
−. 𝑥1 + 𝑥2 − 𝑥5 = 5
La línea de ISOUTILIDADES, es aquella donde el valor de Z es igual en todos los puntos. (por ejemplo,
cuando hacemos Z=0, esa línea es de isoutilidades, donde el valor de Z es siempre igual a 0)
PUNTO EXTREMO: Para cualquier conjunto convexo S un punto P de S es un punto extremo si para
cada segmento rectilíneo que se encuentra completamente en S y que pasa por el punto P, es un
punto extremo del segmento rectilíneo.
VERTICE ADYACENTE: analíticamente se reconoce un vértice adyacente ya que al pasar de un vértice
al siguiente las variables deben cambiar de estado (pasar de 0 a ≠ 0 y viceversa) de forma paralela.
Por ejemplo para los vértices B y C, las variables x3 y x4 intercambian su estado al pasar de un
punto al otro:
𝑥1 ≠ 0 𝑥1 ≠ 0
𝑥2 ≠ 0 𝑥2 ≠ 0
𝑥3 𝑥3 ≠ 0
𝑥𝐵 = 𝑥 = 0 𝑥𝐶= 𝑥 = 0
4 ≠0 4
𝑥5 ≠ 0 𝑥5 ≠ 0
[𝑥6 ] ≠ 0 [𝑥6 ] ≠ 0
RESTRICCIÓNES REDUNDANTES: son aquellas que no forman parte de los límites del EPF y por lo
tanto pueden ser ignoradas sin consecuencias.
9
IMPOSIBILIDAD: PROGRAMA LINEAL NO FACTIBLE: Ocurre cuando el EPF es NO CONVEXO
ILIMITABILIDAD: POLIGONO NO ACOTADO: Ocurre cuando las restricciones son insuficientes para
poder plantear el problema, por lo tanto, si se intenta maximizar el funcional se obtendrá que 𝑃𝑜𝑝𝑡 =
∞
Ahora, si se intenta minimizarlo, se puede obtener un resultado valido para el 𝑃𝑜𝑝𝑡 (en este caso = B)
PROGRAMA LINEAL con SOLUCIONES MULTIPLES

Esto puede ocurrir cuando el punto extremo, es decir, el punto donde el funcional adquiere su valor
máximo, es todo punto en un segmento. En este caso el Punto Optimo será dicho segmento: Pop: ̅̅̅̅𝐵𝐶
Esto nos permite, al momento de tomar una decisión, de poder elegir qué recurso deseamos utilizar
y cuál no, dado que ambos producirán el mismo valor Optimo de Z.
Por ejemplo, podemos observar esto en estos vectores con los valores de las variables en los puntos
B y C. ISOUTILIDAD
𝑥1 𝑥1 𝑥1
𝑥2 𝑥2 𝑥2
𝑥3 𝑥3 𝑥3
𝛼 × . + (1 − 𝛼) × . = . 0≤𝛼≤1
. . .
[𝑥𝑛 ] [𝑥𝑛 ] [𝑥𝑛 ]
Este mismo problema, en caso de que fuese una minimización, tendría una única solución.
PROBLEMA DE DEGENERACION: Se plantea cuando ocurre que en un punto se hacen 0 más de n-m
variables, siento n el número de variables de decisión y m el número de restricciones.
10
PROBLEMA DE REGION FACTIBLE QUE NO TOCA EL ORIGEN: en este caso se puede complicar la
resolución con el método simplex que comienza en (0,0) generalmente. Por lo que se deberá elegir
un punto inicial que se encuentre en el convexo y a la vez re calcular los valores de las variables de la
base
TIPOS DE RESTRICCIONES:
ACTIVAS (Obligatorias): Son aquellas donde se han consumido todos sus recursos, es decir, donde
sus variables de holgura son = 0
INACTIVAS (No Obligatorias): Son aquellas donde las variables de holgura son ≠ 0
FORMAS
FORA CANONICA: en la forma canónica debe existir una FO (máx. o min.), restricciones y las
condiciones de no negatividad. Además no deben existir variables de holgura
FORMA ESTANDAR: En esta forma se exige que la FO se encuentre MAX. Ademas las restricciones
deben estar con la desigualdad <=. Por otra parte TODAS las variable incluidas la de holgura deben
tener condición de no negatividad
FO: Z MAX = CX
S.a.{ AX ≤ b
X ≥ 0}
Z = 𝐶1 𝑥1 + 𝐶2 𝑥2 → 𝑀𝐴𝑋
𝑎11 𝑥1 + 𝑎12 𝑥2 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 ≤ 𝑏2
𝑥1 ≥ 0
𝑥2 ≥ 0
Cualquier forma distinta de esta es EQUIVALENTE y podemos llevarla siempre a la forma estandar.
REGLA 1:
11
- MAX Cx es equivalente a MIN – Cx
- MIN Cx es equivalente a MAX – Cx
REGLA 2:
- AX ≤ b es equivalente a -AX ≥ -b
- AX ≥ b es equivalente a -AX ≤ -b
REGLA 3: IGUALDAD EN UNA RESTRICCION

- AX = b ≡ AX ≤ b & AX ≥ b
REGLA 4
- ADICION DE VARIABLE DE HOLGURA:
AX ≤ b → AX + Y1 = b
- RESTA DE VARIABLE DE EXCESO O SUPERFLUA
AX ≥ b → AX – Y2 = b
REGLA 5:
- VARIABLE NO RESTRINGIDA
x1 no está restringida → x1 = x2 – x3
x1 No restringida (nrs); x2 ≥ 0 y x3 ≥ 0
- VARIABLE NEGATIVA
x1 <= 0 → x1 = - x2
DEFINICIONES Y TEOREMAS:
VARIABLE NO BASICA: Cuando una variable en el punto analizado es = 0. Esta variable esta fuera de
la solución.
CANTIDAD MAXIMA de PUNTOS a EVALUAR: La solución va a estar a lo sumo en un vértice y se
tendrán que analizar:
𝑛!
𝑐𝑜𝑛 Cnm
𝑚!(𝑛−𝑚)!
SOLUCION BASICA: Representan vértices producto de la intersección de dos o más restricciones.
Pueden ser factibles o no factibles
SOLUCION FACTIBLE: al problema de PL es un vector X = x1,x2,…,xN el cual satisface las ecuaciones de
las restricciones y las condiciones de no negatividad
SOLUCION FACTIBLE BASICA para la ecuación es una solución obtenida al hacer n-m variables = 0 y
resolver por las ni variables remanentes, siempre que el determinante de los coeficientes de estas m
variables no sean cero. Las m variables se llaman VARIABLES BASICAS. Entonces la SFB es aquella
donde el vector X tiene no más de m componentes positivas.
SOLUCION FACTIBLE BASICA NO DEGENERADA es una solución factible básica donde el vector X
tiene exactamente m componentes positivas.
SOLUCIÓN FACTIBLE BASICA DEGENERADA: es una solución factible básica donde hay menos de m
componentes positivas del vector X.
REGION DE FACTIBILIDAD: Es el conjunto de todas las soluciones factibles.
12
Una SOLUCION FACTIBLE MAXIMA (PUNTO OPTIMO) es una solución posible que también
MAXimiza la FO.
Una función f(x1,x2,…,xN) es una FUNCION LINEAL de (x1,x2,…,xN) si y solo si para algún conjunto de
constantes (C1,C2,…,Cn), F(x1,x2,…,xN) = C1x1 + C2x2 + … + Cnxn
Un problema de PL es un PROBLEMA DE OPTIMIZACION para el cual tratamos de MAX o MIN una
función de variables de decisión.
1- La función que se pretende optimizar se llama FO
2- Los valores de las VD deben satisfacer un conjunto de restricciones lineales
3- Hay una restricción de signo para cada variable xi ≥ 0 con i =1,2,…,n
Una RESTRICCION se considera OBLIGATORIA si el lado izquierdo es = al derecho de la restricción al

sustituir los valores óptimos de las vD en la restricción.
Una RESTRICCION se llama NO OBLIGATORIA si el lado izquierdo NO es igual al lado derecho de la
restricción al sustituir los valores óptimos de las vD en la restricción.
SOLUCION OPTIMA: Corresponde al conjunto de los valores de las variables de decisión que
corresponden al punto optimo. Representan a las mejores decisiones a tomar para el problema
TEOREMAS BASICOS DE LA PROGRAMACIÓN LINEAL

[TEOREMA 1]: El conjunto de todas las soluciones posibles al problema de PL es un conjunto
convexo.
[TEOREMA 2]: La FO alcanza un MAX o MIN en un punto extremo del conjunto convexo generado
por el conjunto de soluciones posibles al problema de PL. Si alcanza este MIN o MAX en más de un
punto extremo, entonces toma el mismo valor para toda combinación convexa de estos puntos
particulares.
[TEOREMA 3]: Si puede encontrarse un conjunto de k < m vectores P1, P2, …, Pk que son linealmente
independiente y tal que x1P1 + … + xkPk = P0 y todos los xi > 0 → el punto x = (x1,x2,…,xk, 0, 0, …, 0) es
un punto extremo del polígono convexo de soluciones posibles. En este caso, x es un vector n-
dimensional cuyos últimos n-k elementos son 0.
[TEOREMA 4]: Si x=(x1, x2,…,xN) es un punto extremo del convexo, entonces los valores asociados con
los xi positivos, forman un conjunto linealmente independiente. De esto surge que al menos m de los
xi son positivos.
{COROLARIO 1}: Con cada punto extremo del convexo se encuentra asociado un conjunto de
m vectores linealmente independientes del junto dado p1, p2, …, pn
CONCLUSION: De acuerdo a los teoremas anteriormente nombrados, la solución optima en este
método se encontrara sobre, por lo menos, un punto extremo del conjunto convexo, y este punto
extremo tendrá un máximo de m variables no nulas.
13
SIMPLEX
El algoritmo Simplex fue creado por Gorge Datzing en 1947 se trata de un método algebraico, con
conceptos geométricos fundamentales, para la resolución de problemas de PL. Consiste en la
selección de una solución óptima mediante la generación iterativa de un número finito de soluciones
factibles cada una de las cuales produce un nuevo valor de la FO estrictamente mejor que la anterior
Dada la FO: Z = C1x1+ C2x2
Y las restricciones:
a11 x1+ a12x2 + x3 = b1
a21x1 – a22x2 + x4 = b2
a31x1+ a32x2 + x5 = b3
Para empezar con este método, se representa matricialmente los valores de las variables en la
primera solución básica factible. Esto es, cuando tanto Z como x1y x2 son = 0.
Si estos son 0, entonces
x3 = b1
x4 = b2
x5 = b3
Con esta matriz se puede empezar a trabajar en la tabla correspondiente, agregando las ecuaciones y
el funcional
Esta solución estará integrada por las variables cuyos coeficientes integran la submatriz unidad
REGLAS DEL METODO SIMPLEX
1- Se transforma el PL en la forma estándar
2- Se obtiene una Solución básica factible a partir de la forma estándar, esto es, se hace n-m
variables iguales a cero y se despejan las m variables que quedan. Esto supone que al hacer
las n-m variables = 0, nos proporciona valores únicos para las m variables restantes o,
equivalentemente, las columnas de las m variables restantes son linealmente
independientes.
3- Se determina si esta solución es optima
4- Si no es optima, se determina qué variable NO básica se tiene que convertir en una variable
básica y viceversa, para encontrar una nueva Solución básica factible con un mejor valor de la
FO.
5- Se realizan OER de la tabla simplex para obtener la nueva solución básica factible con un
mejor valor de la FO.
DEFINICION DE ADYACENCIA:
Para cualquier problema de PL con n variables de decisión genuinas, dos soluciones factibles son
adyacentes si comparten n-1 fronteras de decisión.
Frontera de Decisión: Una frontera de decisión es una recta que marca el limite de lo qe permite y
no permite la restricción correspondiente que representa. Los diferentes puntos de intersección
entre fronteras de decisión representan vértices a evaluar.
Dos SBF son adyacentes si todas menos una de las variables básicas son las mismas
14
INTERPRETACION TECNICA-ECONOMICA de TODOS los ELEMENTOS de la TABLA OPTIMA del

SIMPLEX
Supongamos que la siguiente es la tabla óptima de un problema
Cj (1) 8 6 0 0
Ck (2) Xk (3) bk (4) X1 (5) X2 X3 X4
8 X1 6 1 0 1/3 -1/6
6 X2 18 0 1 -1/6 1/3
Zj (6) 156 8 6 5/3 2/3
Zj-cj (7) 0 0 5/3 2/3
(1) Esta fila nos indica el beneficio que nos otorga cada unidad de xj en el valor del funcional, es
decir, cuanto impacta la cantidad de xj en la solución.
(2) Esta columna nos indica el beneficio que nos otorga cada unidad de xK que se encuentra en
la solución básica.
(3) Esta columna nos indica qué variable de decisión se encuentre en la base.
(4) Esta columna representa la cantidad de cada variable de decisión que hay en la base.
(5) Estas columnas (x1-x4) nos indican las tasas de sustitución de las variables no básicas con
respecto a las básicas. Por ejemplo, si deseo liberar una unidad de x3, deberé dejar de
producir 1/3 de unidad de x1 y podre producir a su vez, 1/6 de unidad de x2.
(6) Esta fila nos muestra el valor del funcional primero y luego nos muestra los costos de
oportunidad que resulta de traer una variable a la solución. Esto significa, cuanto se reduce el
valor de Z si incrementamos en una unidad esta variable. Como mencionamos en el punto 5)
si traemos una unidad de x3 a la solución, se reduce 1/3 la cantidad de x1 producido, y eso
significa una disminución de a13 x C1 = 1/3 x 8 = 8/3 y a su vez, un aumento en la producción
de x2 que implica un aumento en el funcional de a23 x C2 = -1/6 x 6 = -1, por lo tanto, si
incrementamos en una unidad x3, el valor de Z disminuiría en 5/3. A su vez, si se trata de
una variable genuina no básica, el valor de Zj nos dará el costo reducido de la variable, es
decir, el valor que debería tener el Cj de dicha variable para entrar en la solución.
(7) Esta fila contiene el beneficio o la pérdida neta que resulta de traer una unidad de esta
variable a la solución. Si el valor es de la columna perteneciente a una variable de holgura,
este valor nos indicara cuanto crecería el valor de Z si incorporásemos una unidad más de
este recurso al sistema. (es decir, modificáramos el valor de bj en la restricción). Esto se
puede observar por ejemplo, en el hecho de que si incrementásemos b1 en 1, entonces x3
podría incrementarse en uno también, permitiendo que se incremente la producción
de x1 y se disminuya la de x2, trayendo un beneficio de 5/3. Este valor se conoce
como PRECIO SOMBRA y nos dice también cuanto más se debe estar dispuesto a
15
pagar por una unidad más del recurso en cuestión. Ya que si nos da un beneficio de
5/3, entonces podemos pagar hasta 5/3 más sin reducir el valor del funcional.
CAMBIO DEL VALOR DE Z EN CADA ITERACION

En cada iteración del algoritmo Simplex, Z variara en un ∆Z = -ѳ(Zj – Cj)
Donde ∆Z es la variación del funcional al transformar la base
Ѳ es el valor que toma la variable que será introducida en la base, siempre debe ser no negativo.
(Zj – Cj) corresponde al incremento de beneficio neto provocado por el incremento en 1 unidad de la
variable de decisión xj
METODO SIMPLEX para MAXIMIZAR (MIN): Paso a Paso
1- Se plantean la FO y las restricciones en forma estándar
2- Se transforman las desigualdades en igualdades introduciendo las VH. Este paso es necesario,
pues las variables de holgura generaran la primera base, que resulta ser una matriz
identidad. Y esto genera a su vez el primer punto extremo de la región de factibilidad cuyas
coordenadas están dadas por el vector b.
3- Se plantea la tabla SIMPLEX: esta consiste básicamente en una matriz de los coeficientes de
las m ecuaciones de restricciones incluyendo las VH.
aij = coeficientes en la ecuación de restricción i de la vD xj
Cj C1 C2 0 0
Ck Xk bk X1 X2 X3 X4 Ѳ
0 X3 b1 a11 a21 1 0 Ѳ3
0 X4 b2 a12 a22 0 1 Ѳ4
Zj 0 Z1 Z2 Z3 Z4
Zj-cj Z1- C1 Z2- C2 Z3 Z4
PRIMER TABLA DEL METODO SIMPLEX para un PL de 2 var y 2 restricciones
4- Se selecciona la variable de entrada calculando Zj –Cj. Entra aquel con el valor más negativo
(positivo) (esto es una decisión arbitraria, se puede seleccionar cualquier variable con un
valor negativo, y el algoritmo Simplex tarde o temprano llegara al optimo)
5- Se selecciona la variable de salida calculando Ѳ = bj / a ij , siendo j la columna de la variable de
decisión que entra. Aquel con el valor de Ѳ > 0 más pequeño, será la variable que salga. Ѳ
debe ser positivo para que el ingreso de la variable a la solución, incremente el valor de Z.
6- Por combinación lineal se obtiene un nuevo sistema de ecuaciones deseado, con la vD que
entra reemplazando a la que sale.
Para esto se extrae el pivote awv , que es el coeficiente ubicado en la intersección de la fila (w)
de la Variable de Salida y la columna (v) de la Variable de Entrada.
o La fila del pivote se divide por este, esto se hace para que el coeficiente de la VE sea
1.
o Los coeficientes de las filas restantes se modifican de acuerdo a:
16
𝑎𝑤𝑗 ×𝑎𝑖𝑣
▪ aij ‘ = aij - 𝑎𝑤𝑣
7- Con la nueva tabla se repiten los pasos 4, 5 y 6 hasta que no haya ninguna variable que
introduzca beneficio (reduzca) al valor del funcional. En ese momento se estará en la
Solución Optima. Este paso se conoce como PRUEBA DE OPTIMALIDAD o CRITERIO de
OPTIMALIDAD
Z n+1= Z n – ѳn (Zj – Cj)n
CASOS PARTICULARES QUE PUEDEN PRESENTARSE AL REALIZAR EL ALGORITMO SIMPLEX

PL DEGENERADO - CASO DE EMPATE ENTRE VARIABLES DE SALIDA - CONVERGENCIA
Se produce cuando en uno de los vértices se cortan más de 2 vectores y por lo tanto se anulan más
de 2 variables, entonces, el numero de variables no nulas en ese extremo no alcanza el valor m.
Por lo que decimos que un PL es degenerado si tiene por lo menos una Solución Básica Factible en la
que una variable básica es igual a cero.
Esto se observa cuando hay 2 o más valores de ѳ iguales al mínimo valor positivo cuando intentamos
determinar qué variable saldrá de la solución. Sin importar cuál de las 2 variables seleccionemos,
terminaremos en el mismo punto extremo (degenerado) y el valor de Z será el mismo (ya que es el
mismo punto). Pero, según cual camino tomemos, puede que tengamos que hacer una (o más,
incluso puede generarse un ciclo infinito) tabla simplex, antes de poder salir de dicho punto y pasar
a otro extremo más optimo. En este punto corremos el riesgo de que el valor de Z no cambie, siendo
el valor de ѳ = 0 para la variable que sale.
Para evitar esto, se realiza lo siguiente:
1- Se dividen todos los valores de cada una de las filas en las que se produjo el empate por el
que será su elemento pivote de resultar seleccionada.
2- Los valores de las filas así obtenidas se comparan ordenadamente, valor por valor, de
izquierda a derecha. A la primera desigualdad encontrada, aquella con el menor valor será la
que se seleccione para que salga de la base.
Con este procedimiento nos aseguramos que una misma base no aparezca más de una vez durante el
proceso de cómputo.
CUANDO EL PUNTO EXTREMO DEGENERADO ES OPTIMO: no podrá detectarse el Punto optimo en
dicho extremo, por lo que deberá redefinirse dicho extremo para que se evidencie que se esta en el
optimo. Por lo tanto, cuando un punto extremo es degenerado y optimo, puede encontrarse una
base asociada al mismo que ponga de manifiesto esta última condición.
PL NO ACOTADO – INCOMPATIBILIDAD - CASO DE CONVEXO ABIERTO
Un PL no acotado para un problema de maximización se presenta cuando una variable con
coeficiente negativo en el renglón (Zj - Cj) tiene un coeficiente no positivo en cada restricción. De
forma que el valor de ѳ no es un cociente positivo. Esto nos indica que la variable que entra en la
solución puede incrementarse por un valor de ѳ arbitrario.
Este problema surge de errores al momento de plantear las restricciones, que olvidan restringir
alguna de las variables y por lo tanto pueden incrementarse indefinidamente.
SOLUCIONES MULTIPLES - ALTERNATIVAS
17
Esto se da cuando existe un valor de (Zj - Cj) nulo en correspondencia con una variable no básica. Esto
implicaría que si esta variable entra en la solución, el valor de Z no cambiaria, pero si variarían las
variables básicas y por lo tanto se estaría en otro punto extremo. Las soluciones básicas factibles
correspondientes a ambos extremos se denominan SOLUCIONES ALTERNATIVAS. Y en caso que esto
se presente en correspondencia con el punto óptimo, entonces ambas soluciones son óptimas así
como cada punto que se pueda obtener de la combinación lineal entre ellas.
Dado P1 y P2, los 2 puntos extremos que son Soluciones alternativas, dado un número 0≥ α ≥1
tenemos y dados los vectores XP1 y XP2 correspondientes a los valores de las vD en cada uno de los
Puntos, tenemos:
(1-α) x [XP1] + (α) x [XP2]
Dándole valores a α podemos obtener todas las soluciones alternativas.
Si es posible graficar el PL, este caso se puede observar ya que el funcional tendrá la misma
pendiente que una de las restricciones que forman parte de ese punto extremo. Por lo tanto, todos
los puntos en el segmento que unen las 2 soluciones alternativas son también una solución óptima
para el PL.
TECNICA DE LA BASE ARTIFICIAL:
Esta técnica se utiliza para aquellos PL donde existe al menos una restricción de la forma ≥ o =, donde
no podemos generar la matriz identidad con las variables de holgura para poder obtener la primer
solución básica factible de inicio. Para suplir la falta de variables de holgura, utilizamos variables
artificiales o ficticias que realizan el trabajo de las holguras en las primeras iteraciones y luego son
desechadas de forma legítima de la base.
METODO DE PENALIZACION:
Este método consiste en:
- Para cada restricción i en la que no haya una variable de holgura, se aumenta una VARIABLE
ARTIFICIAL µk, para poder formar una solución factible básica de inicio. El valor Ck de esta
variable será un valor suficientemente grande |𝑀|. Si se maximiza, este valor será –M y si se
minimiza será M. Esta PENALIZACION en el valor del coeficiente es para lograr que la variable
sea extraída de la base y que no regrese a la misma. En caso de que al llegar a la tabla óptima
alguna variable artificial siga en la base, significa que el problema es NO FACTIBLE.
METODO de 2 FASES:
- Este método es muy similar al anterior, excepto que esta refinado para evitar los problemas
de redondeo y exactitud que pueden surgir al utilizar un valor M suficientemente grande
contra los valores de los coeficientes de las demás variables que serán pequeños. Entonces,
se divide el problema en 2 fases, en la primera encontrándose una solución básica factible de
inicio sin las variables artificiales, y en la segunda optimizando el funcional en base a dicha
base.
1- Se modifican las restricciones para que el lado derecho sea NO NEGATIVO
2- Se agregan las variables artificiales necesarias luego de pasar las restricciones a
igualdades (usando el mismo criterio que en el método de penalización)
3- Se calculará el MINIMO de la función W’ = ∑𝑘𝑖=1 µk . Es decir, la suma de todas las
variables artificiales.
18
4- De acuerdo al valor del optimo de W’ vemos que:
o Si W’op > 0 el PL NO tiene solución factible
o Si W’op = 0 y no hay variables artificiales en la base, se continua optimizando sin las
columnas de las variables artificiales y con el funcional original en vez de W’.
DUALIDAD
METODO SIMPLEX DUAL
Se puede aplicar este método para un PL de minimización o uno de maximización con alguna
restricción del tipo ≥. Este método siempre busca la factibilidad de la solución básica, ya que esta
permanece optima. Se puede resumir en los siguientes pasos:
1- Si todos los valores de la columna bk son positivos o cero, la solución optima actual es factible
y hemos finalizado, en caso contrario, se continua con el siguiente paso.
2- Seleccionamos como variable básica saliente aquella con el valor bk más negativo. El renglón
correspondiente a esta variable es el renglón pivote.
3- Efectuamos los cocientes entre los elementos del renglón Cj y los elementos del renglón
pivote cuyos valores son negativos, correspondientes a las posibles variables entrantes que
encabezan cada columna.
4- Elegimos como variable entrante a la base aquella que posea el menor cociente, en valor
absoluto, de los calculados anteriormente.
5- Efectuamos la transformación acostumbrada de la tabla, como se haría con el método
simplex convencional, y luego se regresa al paso 1.
Este método nos permite detectar si al agregar una nueva restricción, esta nos afectara al
convexo
ESQUEMA DUAL
Dado un PL con las siguientes características:
FO → Z= C1x1 + C2x2 + … + Cixi + … + Cnxn (MAX)
sa:
{a11x1 + a12x2 + … + a1jxj + … + a1nxn ≤ b1
{a21x1 + a22x2 + … + a2jxj + … + a2nxn ≤ b2
{ … + … + … + … + … + …
{ai1x1 + ai2x2 + … + aijxj + … + ainxn ≤ bi
{ … + … + … + …. + … + …
{am1x1 + am2x2 + … + amjxj + … + amnxn ≤ bm
Xj ≥ 0; j= 1,2 … n
19
El dual de este PL será el siguiente:
FO → Z(d)= b1y1 + b2y2 + … + biyi + … + bmym (MIN)
sa:
{a11y1 + a12y2 + … + a1jyj + … + a1mym ≥ C1
{a21y1 + a22y2 + … + a2jyj + … + a2mym ≥ C2
{ … + … + … + … + … + …
{ai1y1 + ai2y2 + … + aijyj + … + aimym ≥ Ci
{ … + … + … + …. + … + …
{an1y1 + an2y2 + … + anjyj + … + anmym ≥ Cn
yj ≥ 0; j= 1,2 … m
De aquí observamos que aparece una nueva vD “y” que representa el costo de oportunidad o valor
marginal por unidad de cada recurso. Surge una por restricción (es decir, habrá m variables y) y luego
se les adicionan las variables de holgura y exceso, habiendo entonces hasta m+n variables “y”; igual
que en el directo.
TABLA PARA LA CONVERSION DEL PRIMAL A DUAL
MIN Z(d) → MAX Z MIN Z →MAX Z(d)
(X1 ≥ 0) (X2 ≥ 0) … (Xn ≥ 0) (Xi srs) (Xi ≤ 0)
X1 X2 … Xn I I
(y1 ≥ 0) y1 a11 a12 … a1n ≤b1 I I
(y2 ≥ 0) Y2 a21 a22 … a2n ≤b2 I I
… … … … … … … I I
(ym ≥ 0) Ym am1 am2 … amn ≤bm ↓ ↓
≥C1 ≥C2 … ≥Cn =Ci ≤Ci
(yi ≤ 0)  -------- --------- -- −−−−→ ≥bi
(yi srs)  -------- --------- -- −−−−→ =bi
PROPIEDADES DEL DUAL

- Si un PL tiene solución, también la tendrá su dual respectivo y viceversa.
- El valor MAX de Z será igual al valor MIN de Z(d) (y viceversa)
Esto puede interpretarse como que el beneficio máximo que podemos obtener (Z) tiene el
mismo valor monetario que la valorización de los recursos que podemos utilizar (Z(d))
- Dualidad Debil:
20
Lo que constituiria la Dualidad Fuerte.
- Una vez resuelto el Directo o el Dual, puede generarse con los valores del cuadro óptimo
hallado, el cuadro optimo del otro.
TEOREMAS DEL DUAL

1- Si un PL tiene soluciones factibles y una FO acotada (y por lo tanto una solución optima),
entonces, ocurre lo mismo con el problema Dual.
2- Si uno de los problemas tiene soluciones factibles y una FO no acotada (es decir no tiene una
solución optima), entonces el otro problema no tiene soluciones factibles.
3- Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones
factibles o bien la FO es no acotada.
SIGNIFICADO ECONOMICO del DUAL (recortes de libros para expandir el tema)
21
22
En el ESQUEMA DIRECTO: Punto de vista desde los beneficios
𝑛
Z ⏟ ∑𝑗=1 𝐶𝑗 . [u. monetaria/u. Producida]
⏟= [u. monetaria] =
𝑏𝑒𝑛𝑒𝑓𝑖𝑐𝑖𝑜 𝑡𝑜𝑡𝑎𝑙 𝑏𝑒𝑛𝑒𝑓𝑖𝑐𝑖𝑜 𝑑𝑒 𝑐𝑖𝑐𝑙𝑜 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑜
s.a.
∑ 𝑘
⏟𝑗=1 𝑎𝑖𝑗 . [u. recurso/u. Producida]. xi [u. Producida] ≤ b
⏟j [u. Recurso]
𝑟𝑒𝑞𝑢𝑒𝑟𝑖𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒𝑙 𝑟𝑒𝑐𝑢𝑟𝑠𝑜 𝑖 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑 𝑑𝑒𝑙 𝑟𝑒𝑐𝑢𝑟𝑠𝑜 𝑗
En el ESQUEMA DUAL: Punto de vista desde los costos
El dual es un esquema equivalente que nos permite varias cosas. Por un lado, a veces puede ser más
sencillo de resolver, y siendo que el óptimo del dual será el optimo del directo, podemos elegir
resolver el que nos sea más simple. También puede servir para verificar un resultado obtenido, por la
misma razón que el anterior. Y por último, el Dual de un PL nos proporciona valiosa información en
relación con el efecto de la variación de las disponibilidades de las restricciones activas sobre el costo
marginal del producto.
Desde el punto de vista del esquema Directo en el beneficio marginal, es el beneficio producido por
incrementar en 1 unidad la disponibilidad del recurso.
Desde el punto de vista del esquema Dual, es un costo marginal lo que pagaría por incrementar 1
unidad del recurso, es decir, el costo de exceder en 1 unidad la restricción.
∑ 𝑚
⏟𝑗=1 𝑎𝑗𝑖 . [u. recurso/u. Producida]. yj [u. monetaria/u. Recurso] ≥
𝑏𝑒𝑛𝑒𝑓𝑖𝑐𝑖𝑜𝑠 𝑑𝑒 𝑐𝑎𝑑𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑑𝑒 𝑙𝑜𝑠 𝑟𝑒𝑐𝑢𝑟𝑠𝑜𝑠 𝑒𝑚𝑝𝑙𝑒𝑎𝑑𝑜𝑠
Ci [u. monetaria/u. Producida]
⏟
𝑣𝑎𝑙𝑜𝑟 𝑑𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 𝑖
Esto nos representa el costo económico de utilizar la actividad xj valuada de acuerdo con los precios
sombra yi.
Las restricciones duales aseguran que en el punto optimo no se utilizara una actividad xj cuya utilidad
(Cj.xj) sea menor a su costo económico. Esto quiere decir que el proceso toma a todas las variables xj
cuya utilidad sea menor a su costo económico como no básicas, mientras que aquellas cuya utilidad
sea por lo menos igual o mayor a su costo económico, las hace básicas.
Si vemos el valor del funcional del dual Z(d),observamos que al representar yi los beneficios de cada
recurso y estar multiplicados por cantidades de unidades producidas, Z(d) valoriza el total de los
recursos en base a las unidades producidas.
En el Primal, buscamos la cantidad de productos a elaborar para maximizar el beneficio al colocarlos
en el mercado, dando por conocido el beneficio esperado por cada unidad y respetando una serie de
restricciones derivadas de las limitaciones propias de la empresa. En el dual, intentamos conocer los
valores de los beneficios que debemos asignarle a cada unidad insumida yi, para poder minimizar el
valor de insumo a emplear, conociendo bi y Ci.
23
Esto podemos interpretarlo si consideramos que las medidas de los recursos utilizados están dadas
en valor monetario, entonces las variables yi representaran los beneficios que la empresa debe
asignar a cada unidad monetaria invertida en los diferentes recursos. Por ejemplo, la variable puede
representar el beneficio que nos deja cada peso invertido en aceite de oliva, utilizado para fabricar
aceite de mesa y de cocina.
RELACION ENTRE LAS VARIABLES ORIGINALES y LAS DUALES en la TABLA ÓPTIMA.
Las variables ficticias del dual se corresponden con las variables genuinas del primal, mientras que
las variables ficticias del primal se corresponden con las variables genuinas del dual.
Cuando una variable del esquema directo = 0, la correspondiente variable del dual será ≠ 0, esto
significa que cuando el recurso está agotado este tiene un costo marginal, inversamente, si la
variable del Directo es ≠ 0, el valor del Dual será 0, ya que al haber recursos libres, no habrá un costo
marginal.
Esto significa que si una variable es básica en el directo, será no básica en el dual y viceversa.
Luego, los valores de Zj – Cj serán traspasados, cambiando el signo, al dual en la columna de las Ck (y
a su vez, los valores de las Zj – bj serán traspasados al primal en la columna de las bj.
24
Ejemplo: PRIMAL
Cj 15 9 0 0 0
Ck xk bk X1 X2 X3 X4 X5
15 X1 5 1 0 0 -1 5
9 X2 8 0 1 0 4 -5
0 X3 3 0 0 1 2 2
Zj 149 15 9 0 21 30
Zj-Cj 0 0 0 21 30
DUAL
Bj 17 7 3 0 0
bk yk Ck y1 y2 y3 y4 y5
7 y2 21 -2 1 0 1 -4
3 y3 30 -2 0 1 -5 5
Zj 149 20 7 3 5 8
Zj-Bj -3 0 0 -5 -8
NOTA: Los valores de bk y Cj son inventados, por lo tanto esta solución no se verificara
matemáticamente, lo importante es como las variables se relacionan, no la validez de esta solución
óptima.
PRECIOS SOMBRA: El Precio Sombre de la i-esima restricción de un PL es la cantidad con que mejora
el valor óptimo Z si el segundo miembro de la i-esima restricción se incrementa en una unidad
(suponiendo que la base actual sigue siendo óptima). Por lo que el precio sombra puede ser
considerado como el costo (o sobreprecio, según el caso) que se debe estar dispuesto a pagar por
agregar una unidad más de este recurso.
Entonces, si el lado derecho de una restricción se incrementa en ∆bi, entonces (suponiendo que la
base actual sigue siendo óptima), el nuevo valor óptimo de Z para una MAX será:
(Nuevo valor optimo de Z) = (antiguo valor optimo de Z) + (precio sombra de la restricción i). ∆bi
En el caso de una MIN será:
(Nuevo valor optimo de Z) = (antiguo valor optimo de Z) - (precio sombra de la restricción i). ∆bi
El precio sombra para la restricción i será el valor de (Zi – Ci).
- Una restricción ≥ tendrá un precio sombra no positivo, esto es porque al aumentar el lado
derecho de una restricción ≥, se eliminan puntos de la región factible. Por lo tanto, el valor
óptimo de Z tiene que disminuir o conservarse sin cambio.
- Una restricción ≤ tendrá un precio sombra no negativo, esto es porque sumar puntos a la
región factible de un problema de MAX no puede reducir el valor óptimo de Z.
- Una restricción = tendrá un precio sombra negativo, positivo o cero.
DUALIDAD Y ANALISIS DE SENSIBILIDAD
25
El teorema del dual nos muestra que si un conjunto de variables básicas VB es factible, entonces VB
es optimo (es decir el coeficiente de todas las variables en el renglón Zj – Cj es no negativo) si y solo si
la solución del dual asociada cBVB-1 es factible para el dual.
De esta forma, es posible usar este resultado para realizar los siguientes análisis de sensibilidad:
- Cambio de coeficiente de una variable no básica de la FO
- Modificación de la columna de una variable no básica
- Agregado de una nueva actividad.
En cada uno de estos casos se determina simplemente si al modificar el PL original, se mantiene la

factibilidad del dual. Si se conserva, entonces la base actual sigue siendo óptima.
ANÁLISIS DE SENSIBILIDAD
El ANALISIS DE SENSIBILIDAD consiste en determinar cuánto variará Z al alterar alguno de los
recursos o de los coeficientes del funcional, así como también determinar entre qué rangos de
valores para los coeficientes y restricciones, la solución optima seguirá siendo optima.
INTERVALO PARA UN COEFICIENTE DE LA FO:
Es el intervalo de los valores para un coeficiente de la FO para los cuales la base actual permanece
óptima. En este intervalo no cambian los valores de las vD, pero el valor de Z puede o no cambiar.
COSTO REDUCIDO:
Para cualquier variable NO básica, el costo reducido de la variable es la cantidad en la cual hay que
mejorar el coeficiente de la variable no básica en la FO para que esta sea básica en alguna solución
óptima para el PL.
Por ejemplo, si x4 = 0, y su valor de Cj = 10 tenemos que:
Cj 10 …
… X4 …
… → Aquí vemos que para que el valor de Zj – Cj sea no positivo,
Zj 22 Cj debería ser ≥ 22, es decir, debería ser ≥ al valor de Zj.
Zj - Cj 12 … HOLGURA COMPLEMENTARIA: cada solución básica en el
problema primal tiene una solución básica complementaria en
el problema dual, donde los valores respectivos de la FO son iguales, de esta forma, la propiedad de
holgura complementaria establece que para cada par de variables asociadas, si una de ellas tiene
holgura no negativa, entonces la otra no debe tener holgura.
RESTRICCIÓN ACTIVA: Cuando el recurso correspondiente a esta restricción está agotado. Tiene un
valor marginal positivo.
RESTRICCIÓN INACTIVA: Tiene un valor marginal = 0 (es decir, Zj-Cj = 0)
ANALISIS DE FACTIBILIDAD: Al variar los valores de los recursos disponibles, se modifica la región
factible y la solución optima puede cambiar, por lo que se determina el rango de variación de bj
dentro del cual la solución optima sigue siendo factible
ANALISIS DE OPTIMALIDAD:
Los Cj definen la pendiente del funcional, por lo tanto si cambian ellos, la pendiente varia también.
ANALISIS DE OPTIMALIDAD para los COEFICIENTES que NO ESTAN en la SOLUCIÓN
∆Cj ≤ Zj – Cj para MAX
26
Para que la solución óptima se mantenga igual
∆Cj ≥ Zj – Cj para MIN
ANALISIS DE OPTIMALIDAD para los COEFICIENTES que ESTAN en la SOLUCIÓN

El coeficiente Ck podrá variar entre (∆Ck1 - Ck) ≤ Ck ≤ (∆Ck2 + Ck)
𝑍𝑗 −𝐶𝑗
Para calcular los valores de ∆Ck se hace | 𝑎𝑘𝑗
| con cada variable no básica j.
Para determinar el signo de ∆Ck se verifica lo siguiente:
MAX MIN ∆Ck
𝑎𝑖𝑗 (-) 𝑎𝑖𝑗 (+) (+)
Ck (+)
𝑎𝑖𝑗 (+) 𝑎𝑖𝑗 (-) (-)
𝑎𝑖𝑗 (-) 𝑎𝑖𝑗 (+) (-)
Ck (-)
𝑎𝑖𝑗 (+) 𝑎𝑖𝑗 (-) (+)
Si dos ∆Ck tienen el mismo signo, se toma el de menor valor absoluto, es decir, el más restrictivo.
ANALISIS GRAFICO DE SENSIBLIDAD:
Para determinar si la base actual todavía es optima después de cambiar un coeficiente de la FO,
observe que al modificar el coeficiente de la FO de una variable, cambia la pendiente de la recta de
isoutilidades. La base actual continua siendo óptima siempre que la solución optima actual sea el
último punto en la región factible que tenga contacto con las rectas de isoutilidades a medida que uno
se desplaza en la dirección en que se incrementa Z (para un problema de MAX). Si la base actual es
óptima, los valores de las variables de decisión se conservan sin cambio, pero si podría cambiar el valor
optimo de Z.
Para determinar si la base actual sigue siendo optima después de cambiar el segundo miembro de una
restricción, empiece por encontrar las restricciones que son activas para la solución optima actual.
Como cambiamos el segundo miembro de la restricción, la base actual sigue siendo óptima siempre
que el punto donde las restricciones son activas se conserve factible. Incluso si la base actual continua
siendo optima, podrían cambiar los valores de las vD y el valor optimo de Z
CAMBIO EN EL LADO DERECHO DE LAS RESTRICCIONES (es decir, cambio en la cantidad de recursos
disponibles bk)
Para determinar si un cambio en la cantidad de recursos disponibles modifica la solución básica, se
calcula:
𝑥𝑏 -1 𝑏̅, donde B-1 es la matriz inversa, formada por los valores aij de las variables de holgura y 𝑏̅ es
̅̅̅=B
el vector correspondiente al lado derecho de las restricciones, con el nuevo valor de la restricción bk
modificado.
Si ̅̅̅
𝑥𝑏 es positivo, entonces la solución actual seguirá siendo básica, sino, debe calcularse la nueva
solución por medio del método simplex dual.
Por ejemplo, se tiene la FO siguiente:
Max 2x1 + 7x2 - 3x3
s.a.: x1 + 3x2 + 4x3 <= 30
x1 + 4x2 - x3 <= 10
x1,x2,x3 >= 0
Y la tabla óptima es la siguiente:
27
X1 X2 X3 X4 X5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
Se desea modificar el valor de b a (20, 30), por lo tanto, se calculara
Como se puede apreciar, un valor de Xb es negativo, lo que implica que si se modifican de esta forma
las restricciones, el valor del funcional óptimo puede seguir mejorándose, por lo que se procede con
el método simplex dual para seguir resolviendo.
INTERVALO DE VARIACION DEL LADO DERECHO DE UNA RESTRICCIÓN bK
Para determinar el intervalo en el cual bK puede variar sin modificar la solución básica óptima obtenida,
se calculara:
−𝐵𝑖
para cada i y los valores resultantes se sumaran al valor de bk y de acuerdo a los resultados
𝑎𝑖𝐾
obtenidos se tomaran los más restrictivos como limites del intervalo.
Por ejemplo, si tomamos esta tabla optima, con valor de b2 = 10, obtendremos que:
xi Bi X1 X2 X3 X4 X5 -20/-1 = 20
x4 20 0 -1 5 1 -1 -10/1 = -10
x1 10 1 4 -1 0 1
10+20 = 30 // 10-10 = 0
Zj 20 0 -1 1 0 1
Por lo tanto, bk podrá tomar cualquier

valor entre 0 y 30 sin modificar la base. 0 ≤ bk ≤30
INCLUSION DE UNA NUEVA VARIABLE Xk: Debemos evaluar si la nueva variable es un aporte
significativo a los resultados del original. Por lo que, para verificarlo, calculamos el costo reducido de
la nueva variable haciendo de cuenta que la incluimos en la tabla simplex optima. Si se cumple que el
costo reducido es mayor o igual a cero, entonces se conserva la actual solución optima, en caso
contrario, se puede continuar optimizando con el Simplex agregando a la tabla una nueva columna
con los valores de B-1 Ak para los valores akj de la tabla, y el valor rk en el campo Zk - Ck
28
Entonces, El costo reducido para la variable Xk será: rk = Zk - Ck = (CB B-1 Ak) - Ck, donde k es el índice de
la nueva variable, CB es el valor de los Cj para las variables que están en la solución y Ak es la columna
de coeficientes tecnológicos de la nueva variable.
Por ejemplo: Se desea estudiar la posibilidad de elaborar un nuevo producto con beneficio neto igual
a 8 y que requiere 4, 2 y 5 unidades de los recursos asociados a cada restricción. ¿Conviene elaborar
el producto?
Max 9x1 + 12x2
sa: 4x1 + 3x2 <= 180
2x1 + 3x2 <= 150
4x1 + 2x2 <= 160
x1,x2 >= 0
CB X1 X2 X3 X4 X5
-9 1 0 1/2 -1/2 0 15
-12 0 1 -1/3 2/3 0 40
0 0 0 -4/3 2/3 1 20
Cj-Zj 0 0 1/2 7/2 0 615
Se debe evaluar rk y determinar si este es >=0. (NOTA, en este ejercicio el cálculo esta hecho al revés,
es decir (Cj-Zj, ya que es como trabajan algunos libros, pero el resultado será el mismo, ya que ellos
toman para el valor de Cj cambiado de signo en la tabla simplex)
En este ejemplo rk=1>=0, por lo cual no conviene la incorporación de esta nueva variable al modelo,
es decir, aun cuando sea incorporada no obtendremos un valor óptimo que supere el actual V(P)=615.
De todas formas si incluyésemos la variable nueva en la tabla simplex, nos quedaría así
X1 X2 X3 X4 X5 XNew
1 0 1/2 -1/2 0 1 15
0 1 -1/3 2/3 0 0 40
0 0 -4/3 2/3 1 1 20
0 0 1/2 7/2 0 1 615
Si el costo reducido de esta nueva variable hubiese sido cero, entonces el nuevo escenario tendría
infinitas soluciones.
CAMBIO EN LOS COEFICIENTES DE LA FO: En caso de que uno o varios de los coeficientes de la FO se
modifiquen, las variables básicas para la solución optima se mantendrán si los nuevos costos reducidos
29
calculados con los nuevos valores de coeficiente son mayores o iguales a cero. El valor de la FO se
modificara de acuerdo al cambio en los valores de C y de qué variables estén en la solución.
• Por lo tanto, para verificar esto haremos: ̅𝒓̅̅̅ ̅̅̅̅ −𝟏 ̅̅̅̅

𝑫 = 𝑪𝑩 𝑩 𝑫 − 𝑪𝑫 ≥ 𝟎
• si el cambio se da en solo un coeficiente: 𝒓̅𝒋 = ̅̅̅̅
𝑪𝑩 𝑩 𝑨𝒋 − ̅̅̅
−𝟏
𝑪𝒋 ≥ 𝟎 donde j es el índice del
coeficiente cambiado.
• En caso de que el valor del costo reducido sea menor a 0, entonces se reemplaza(n) los costos
en el renglón Zj – Cj con los obtenidos por medio de este cálculo y se sigue optimizando con
el algoritmo simplex.
EJEMPLO: (NUEVAMENTE TENER EN CUENTA, QUE EN EL EJEMPLO LOS VALORES DE Cj SE TOMAN

CAMBIADOS DE SIGNO y se hace Cj - Zj, pero el resultado es el mismo aplicando el método simplex
tradicional y haciendo Zj-Cj es el mismo.)
Se desea saber que sucede si se modifica los parámetros de la función objetivo, quedando éstos de la
siguiente forma: Z = x1 + 5x2 - 2x3. (X4 y X5 son las variables de holgura de la restricción 1 y 2
respectivamente).
Max 2x1 + 7x2 - 3x3
sa: x1 + 3x2 + 4x3 <= 30
x1 + 4x2 - x3 <= 10
x1,x2,x3 >= 0
X1 X2 X3 X4 X5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
Debido a que los cambios en los parámetros de la función objetivo se producen en más de una variable
consideraremos la siguiente fórmula:
Debido a que al menos uno de los costos reducidos de las variables no básicas se ha vuelto negativo,
entonces cambia la actual solución y valor óptimo del problema. Para incorporar esta modificación en
la tabla final del Método Simplex se actualiza los costos reducidos asociados a las variables no básicas,
además del valor óptimo, quedando como sigue:
X1 X2 X3 X4 X5
0 -1 5 1 -1 20
30
1 4 -1 0 1 10
0 -1 1 0 1 10
INCLUSION DE UNA NUEVA RESTRICCIÓN: Para saber si la actual solución y valor óptimo se mantendrá
luego de incorporar una nueva restricción al problema se debe evaluar la solución actual y verificar si
satisface la nueva restricción. En caso afirmativo, la actual solución también lo será del problema con
la nueva restricción, en caso contrario se incorpora la nueva restricción a la tabla final del Simplex del
escenario base.
EJEMPLO: Sin resolver nuevamente el problema, se desea saber que sucede si se considera una nueva
restricción de la forma: 3x1 + 2x2 + 3x3 <= 25. (Observación: Considerar mismo modelo y tabla final
del ejemplo anterior)
Se evalua la solución actual en la restricción: 3*(10) + 2*(0) + 3*(0) <= 25. No cumple. Por tanto se
incorpora esta nueva restricción como fila a la tabla final del Simplex. Adicionalmente, se agrega X6
como variable de holgura asociada a esta nueva restricción:
X1 X2 X3 X4 X5 X6
0 -1 5 1 -1 0 20
1 4 -1 0 1 0 10
3 2 3 0 0 1 25
0 1 1 0 2 0 20
Una alternativa para encontrar el óptimo a través de esta tabla es formar la identidad (debemos hacer
cero el parámetro asociado a X1 en la tercera fila) multiplicando la fila 2 por -3 y sumando dicho
resultado a la fila 3. De esta forma se obtiene:
X1 X2 X3 X4 X5 X6
0 -1 5 1 -1 0 20
1 4 -1 0 1 0 10
0 -10 6 0 -3 1 -5
0 1 1 0 2 0 20
Finalmente obtenemos X4, X1 y X6 como variables básicas. Producto de la transformación un lado
derecho queda negativo y en este caso podemos continuar adelante utilizando el Método Simplex
Dual.
PROBLEMAS ESPECIALES DE PROGRAMACIÓN LINEAL: PROBLEMAS DE

DISTRIBUCION
MODELO DE TRANSPORTE: es una clase especial de PL que tiene que ver con transportar un articulo
desde sus fuentes hasta sus destinos. El objetivo es determinar el programa de transporte que
minimice el costo total del transporte y que al mismo tiempo satisfaga los límites de la oferta y la
demanda. En el modelo se supone que el costo de transporte es proporcional a la cantidad de unidades
transportadas en determinada ruta.
31
DEFINICION DEL MODELO DE TRANSPORTE
Dado el siguiente grafo:
C11 : x11
a1 1 1 b1
a2 2 2 b1
. .
. .
: :
a3 m n bn
Cmn : xmn
Tenemos m fuentes (oferta) y n destinos (demanda), representados en los nodos. Los arcos
representan las rutas que enlazan las fuentes y los destinos. El arco (i,j) que una la fuente i con el
destino j conduce dos clases de información, el costo de transporte por unidad Cij y la cantidad
transportada xij. La cantidad de oferta en la fuente i es ai y la cantidad demandada en el destino j es
bj. El objetivo del modelo es determinar las incógnitas xij que minimicen el costo total del transporte y
que al mismo tiempo satisfaga las restricciones de oferta y demanda.
El modelo de transporte se basa en la premisa de que el modelo este BALANCEADO, esto significa que
la oferta total sea igual a la demanda total. Si el modelo esta DESBALANCEADO se podrá agregar una
fuente ficticia o un destino ficticio de forma tal de balancear el problema. En general el costo de
transporte desde la fuente ficticia a cualquier destino será 0, ya que la fuente no existe realmente.
Pero, si se desea que un destino en particular reciba todo lo que necesita (es decir, que no reciba nada
de la fuente ficticia) se penaliza el costo de transporte desde la fuente ficticia a ese destino, de forma
tal que al momento de calcular el mínimo costo, no convenga enviar nada desde la fuente ficticia. Lo
mismo si el destino es ficticio, si uno desea que cierta fuente envíe toda su producción a los destinos
verdaderos, se penalizará el costo de envío hacia el destino ficticio, de forma tal que no envíe nada
hacia allí. Este costo de penalización se puede considerar como el costo de desabastecimiento, es decir,
cuanto perdería la empresa si cierto destino se quedase sin productos. De esta forma, cuando se
optimice, se distribuirán los productos de forma tal de que dicho costo sea mínimo.
FORMULACION GENERAL – PLANTEO MATEMATICO

La formulación general para el PL de transporte será:
s.a.:
ai
bj
0
Si el problema esta balanceado, es decir, se verifica:
32
Entonces las ecuaciones serian todas igualdades:

ai
bj
0
Esto se puede representar en una tabla simplex modificada para el modelo de transporte que es la
siguiente:
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠
D1 D2 … Dn Oferta
𝐹𝑢𝑒𝑛𝑡𝑒𝑠
C11 C21 C1n
F1 … a1
x11 x21 x1n
C21 C22 C2n
F2 … a2
x21 x22 x2n
… … … … … …
Cm1 Cm2 Cmn
Fm xm1 xm2 … xmn am
Demanda b1 b2 … bn
PROCEDIMIENTO DE SOLUCIÓN:
Los pasos del algoritmo de transporte son exactamente iguales a los del algoritmo simplex:
Paso (1) Determinar una solución básica factible de inicio y seguir con el paso 2
Paso (2) Usar la condición de optimalidad del método simplex para determinar la variable de entrada
entre las variables no básicas. Si se satisface la condición de optimalidad, detenerse. En caso
contrario continuar con el paso 3.
Paso (3) Usar la condición de factibilidad del método simplex para determinar la variable de salida
entre todas las variables básicas en ese momento y determinar la nueva solución básica. Regresar al
paso 2.
PASO 1 – DETERMINACION DE LA SOLUCIÓN DE INICIO:

Un modelo general de transporte con m fuentes y n destinos tiene m+n ecuaciones de restricción,
una para cada fuete y una para cada destino. Sin embargo, como el modelo de transporte siempre
debe estar balanceado, una de esas ecuaciones es redundante. Por lo que el modelo tendrá entonces
m+n – 1 ecuaciones independientes de restricción, lo que quiere decir que la solución básica de inicio
tendrá m+n-1 variables básicas.
METODOS PARA OBTENER LA SOLUCIÓN NO ARTIFICIAL DE INICIO:

Existen varios métodos para obtener esta solución, que difieren principalmente en la cantidad de
cálculos requeridos para realizarlos y en la calidad de la solución (es decir, el método más complejo
producirá una solución básica de inicio más cercana al mínimo óptimo que el más simple.)
33
MÉTODO DE LA ESQUINA NOROESTE: este método es el más simple y es el que nos dará la solución
menos óptima, ya que no tiene en cuenta el valor del costo del transporte de los productos para
determinar la solución.
El método comienza en la celda en la esquina superior izquierda (es decir, a11):
1- Asignar el máximo posible a la celda seleccionada y ajustar las cantidades de oferta y

demanda restantes.
2- Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar
que no se pueden hacer más asignaciones a esa fila o columna (esto es porque se ha
satisfecho alguna de las restricciones). Si un renglón y una columna dan cero al mismo
tiempo, tachar solo uno y dejar una oferta (o demanda) cero en la fila (o columna) que no se
tacho.
3- Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a
la celda de la derecha si se acaba de tachar una columna o la de abajo si se tacho una fila.
Volver al paso 1.
D1 D2 D3 D4 Oferta
10 2 20 11 15 10
F1
5 10 - - 0
12 7 9 20 25 20
F2
- 5 15 5 50
4 14 16 18
F3 - - - 10 10 0
15 5 15 10
Demanda 50 15 0
0 0
Z inicial = 520
MÉTODO DEL COSTO MINIMO de la MATRIZ:

Este método determina una mejor solución de inicio ya que tiene en cuenta el costo de los
transportes y se concentra en los de menor costo. Se inicia asignando todo lo posible a la celda que
tenga el mínimo costo unitario (los empates se rompen de manera arbitraria). A continuación, la fila
o columna cuya demanda u oferta hayan sido satisfechas se tacha, y las cantidades se ajustan en
consecuencia. Si se satisfacen en forma simultánea un renglón y una columna al mismo tiempo, solo
se tacha uno de los dos. A continuación se busca la celda no tachada con el costo unitario mínimo y
se repite el proceso hasta que queda sin tachar exactamente una fila o columna.
Z inicial = 475
D1 D2 D3 D4 Oferta
10 2 20 11 Este método es el más general, existiendo también
F1 15 0
variantes de mínimo de la fila y mínimo de la
- 15 - 0
12 7 9 20 25 10 columna, en el primero, nos centramos en despachar
F2 todo, es decir, ponemos énfasis en reducir los valores
- - 15 10 0
4 14 16 18 de la oferta, mientras que en el mínimo de la columna,
F3 5 - - 5 10 5 0 intentamos satisfacer las demandas primero.
15 10
Demanda 50 15 0 15 0
0 En estos métodos, vamos fila por fila (o columna por
columna) empezando desde arriba (o la izquierda),
34
tomando el valor mínimo de dicha fila (columna) y asignando todo lo posible a dicha celda, si es que
se satisface la oferta (demanda) pasamos a la siguiente fila (columna), sino, nos movemos hacia el
siguiente valor mínimo en esa fila (columna) que quede sin asignar. Debemos tener en cuenta como
en los 2 métodos anteriores, que si se satisfacen los requerimientos tanto de una fila como de una
columna, debemos tachar la fila (columna) correspondiente.
MINIMO DE LA FILA MINIMO DE LA COLUMNA
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠 𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠
D1 D2 D3 D4 Oferta D1 D2 D3 D4 Oferta
𝐹𝑢𝑒𝑛𝑡𝑒𝑠 𝐹𝑢𝑒𝑛𝑡𝑒𝑠
10 2 20 11 10 2 20 11
F1 15 0 F1 15 0
- 15 - - - 15 - 0
12 7 9 20 25 20 12 7 9 20 25 10
F2 F2
5 0 15 5 15 0 - - 15 10 0
4 14 16 18 4 14 16 18
F3 - - - 10 10 0 F3 5 - - 5 10 5 0
15 10 15 10
Demanda 50 15 0 15 0 Demanda 50 15 0 15 0
0 0
Z inicial = 505 Z inicial = 475
MÉTODO DE APROXIMACION DE VOGEL
Este método es una versión mejorada del método del costo mínimo y que produce, en general,
mejores soluciones de inicio.
1- Determinar para cada fila (y columna) una medida de penalización restando el elemento de
costo unitario mínimo en la fila (columna) del elemento con costo unitario siguiente al
mínimo de la misma fila (columna)
2- Identificar el renglón o columna con la mayor penalización, romper los empates en forma
arbitraria. Asignar todo lo posible a la variable que tenga el mínimo costo unitario del
renglón o columna seleccionado. Ajustar la oferta y la demanda y tachar el renglón o la
columna ya satisfechos.
3- A- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse
B- si queda sin tachar una fila (columna) con oferta (demanda) positiva, , determinar las
variables básicas en el renglón con el método del costo mínimo. Detenerse.
C- Si todos los renglones que no se tacharon tienen cero oferta y demanda, determinar las
variables básicas cero por el método del costo mínimo. Detenerse.
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠 1º 2º 3º 4º
D1 D2 D3 D4 Oferta
iteración iteración iteración iteración
10 2 20 11 10-2 = 11-2 = ------- -------
F1 15 0
- 15 - - 8 9
12 7 9 20 25 10 9-7 = 2 9-7 = 2 9-7 = 2 20-7 =
F2 13
- 0 15 10 0
4 14 16 18 10 5 0
35
5 - - 5 14-4 = 16-14 = 16-14 = 18-14 = D- En cualquier

F3
10 2 2 4 otro caso,
Demanda 50 15 0 15 0
15 5 seguir con el
0 paso 1.
1º y 2º 12-4 7-2 = 16-9 18-11
iteración =8 5 =7 =7
3º ------- 14-7 16-9 20-18
Iteración =7 =7 =2
4º -------- 14-7 ------- 20-18
iteración =7 =2
DETERMINACION DE LA SOLUCIÓN OPTIMA a partir de la SOLUCIÓN DE INICIO obtenida:
Después de determinar la solución de inicio, se usa el siguiente algoritmo para determinar la solución
óptima:
1- Se usa la condición de optimalidad del simplex para determinar la variable de entrada. Si se satisface
la condición de optimalidad detenerse, de otra forma continuar con el paso 2.
2- Se determina la variable de salida con la condición de factibilidad del simplex. Se cambia la base y se
regresa al paso 1.
Los cambios de base no implicaran las OER utilizadas en el simplex, en vez de eso, la estructura
particular del modelo de transporte nos permite realizar cálculos más sencillos:
MÉTODO FUNDAMENTAL o de los COSTOS NETOS – Determinación de variables de Entrada

Para determinar que variable nos conviene ingresar a la solución, debemos tener en cuenta que si
modificamos un valor en una variable, deberemos modificarlo para varias variables mas, todas
aquellas que estén relacionadas con el depósito y fuente a la que hace referencia la variable a
agregar, así como también aquellas relacionadas con estas últimas variables.
Por ello es que se utiliza un método partiendo de la solución de inicio, donde evaluamos cada
variable no básica para determinar si ingresara en la solución.
Para ello utilizamos el concepto de ciclo, este será un conjunto de nodos (es decir, celdas en la tabla
de transporte) que deben estar siempre en la misma columna o fila que la variable evaluada y
también que deben ser variables básicas. El ciclo entonces, tendrá como vértices estos nodos, cada
cual relacionado con una variable en la misma fila y una variable en la misma columna, hasta llegar a
la variable inicial de la que partió el ciclo.
36
D1 D2 D3 D4 Oferta
Por ejemplo, para x31 nuestro ciclo será: 10 2 20 11
F1 15
- 15 - -
12 7 9 20
F2 25
5 0 15 5
4 14 16 18
F3 - - - 10 10
Demanda 5 15 15 15
Si incrementamos en una unidad la variable

x31 debemos restar en una unidad la variable básica x34, para no exceder la oferta. Si realizamos este
último cambio, deberemos incrementar en una unidad la variable básica x24, para poder satisfacer
toda la demanda. Si realizamos este cambio, deberemos reducir en una unidad la variable x21, de
forma tal de no exceder la oferta (ni de exceder la demanda, ya que agregamos una unidad en x31
que excedería la demanda si no modificásemos x12). Entonces, el valor con que se modificaría el
funcional si la variable x31 ingresase en la solución será de:
∆Z= C31 – C34 + C24 – C21 = 4-18+20-12 = -6.
Esto significa que el valor del funcional se reducirá en 6 unidades si agregásemos una unidad de esta
variable.
Este cálculo se realiza para todas las variables no básicas, y luego se determinara aquella con el
menor valor negativo, ya que nuestro objetivo es minimizar el valor de Z.
Determinación de variables de Entrada

Luego de determinar la variable que entrara en la base, calculamos cuantas unidades (∆) podemos
agregar de dicha variable (y a su vez, determinar que variable será la saliente), de forma de poder
mantener el balance del PL. Para ello, verificamos en los nodos correspondientes al ciclo de la
variable entrante aquellos que deben disminuirse en caso de que entre la variable a la base. De ellos,
verificamos el valor de xij y tomamos el más pequeño. Esta variable será la que salga de la solución y
ese valor de xij será el valor con que la variable entrara a la solución. Esto lo representaremos abajo
para la variable indicada en el ejemplo anterior:
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠 Ofe
D1 D2 D3 D4 rta
10 2 20 11
F1 15
- 15 - -
12 7 9 20
F2 25
5-∆ 0 15 5+∆
4 14 16 18
F3 - +∆ - - 10 - ∆ 10
Demanda 5 15 15 15
Aquí vemos que x31 puede aumentar un máximo de ∆ unidades y que ∆ no puede ser mayor a
5, ya que si lo fuese al restárselo a x21 obtendríamos un valor negativo. Como nos interesa reducir lo
máximo posible el valor de Z, debemos ingresar a la solución la mayor cantidad de unidades de x31, y
dado que el valor máximo que podemos ingresar es 5, será ese el valor de ∆. Por lo tanto, la tabla de
transporte siguiente nos quedaría, luego de ingresar x31 a la solución, de esta forma:
37
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠 Ofe
D1 D2 D3 D4 rta
10 2 20 11
F1 15
- 15 - -
12 7 9 20
F2 25
0 0 15 10
4 14 16 18
F3 Obsérvese que se respetan todas las ofertas y
10
5 - - 5
demandas y que el PL esta balanceado.
Demanda 5 15 15 15
Se continuara operando de esta manera hasta que
todos los valores calculados de los ciclos para todas las variables no básicas sean positivos. En ese
punto estaremos en la solución optima.
MÉTODO DE LOS MODIFICADORES o MODI
En este método se asocian los multiplicadores ui y vj a la fila i y columna j de la tabla de transporte.
Estos multiplicadores satisfacen la siguiente ecuación ui + vj = Cij para toda variable xij básica. (Esto es
así ya que el valor de Zj-Cj para toda variable básica debe ser = 0)
Esto nos generara m+n-1 ecuaciones, igual al número de variables básicas. Para poder resolverlas,
suponemos que u1 = 0, lo que nos hace vj = C1j. Con el valor de vj y u1 podremos empezar a despejar
los demás valores de ui y vj.
Una vez obtenidos todos estos valores, calculamos, ui + vj - Cij para cada variable no básica. Que
equivale a calcular el valor de Zj-Cj en la tabla simplex.
Como estamos minimizando, debemos buscar la variable cuyo valor de ui + vj - Cij sea el más positivo.
Si todas las variables son negativas, implica que estamos en el óptimo, sino, se toma como variable
entrante la más positiva y para determinar la variable saliente así como el estado de la tabla de
transporte se utilizara el método del ciclo descripto arriba. Utilizando como inicio del ciclo la variable
entrante determinada por el método MODI, creamos el ciclo y determinamos el valor de ∆, este valor
lo restamos y sumamos alternativamente hasta completar el ciclo.
CASOS ESPECIALES DEL MODELO DE TRANSPORTE:
SOLUCIONES ALTERNATIVAS: estas soluciones no modifican el valor de la FO pero si cambian las
variables básicas. Esto permite tener mayores consideraciones para determinar las rutas a
comunicar, como por ejemplo seguridad de los transportes a utilizar, inconvenientes en la carga o
descarga, etc.
La SOLUCIÓN ALTERNATIVA se presenta cuando al obtener una solución optima, NO TIENE un nº
mayor de m+n- casillas con valor nulo en la matriz de los ui + vj-Cij si aplico el método MODI o en los
∆Z en el método fundamental de los costos netos.
DEGENERADO: cuando hay menos de m+n-1 variables ≠ 0
Esto saldrá a la luz ya que no podremos armar el circuito
Puede ser necesario colocar cantidades infinitesimales en varias casillas ε1, ε2,… ,εn para que el
número de soluciones distintas a 0 no sea inferior a m+n-1. El agregado de una cantidad ε es tal que
se desprecia cuando aparece sumado o restado a una cantidad, es decir xij +o- ε = xij. Solo va a figurar
en una casilla cuando aparece como el único valor. El valor de ε se agregara de forma de facilitar la
creación de ciclos, por lo tanto hay que tener en cuenta eso al momento de agregarlo.
38
Puede ocurrir que en el transcurso de las sucesivas iteraciones ε desaparezca o continúe en la tabla
hasta llegar a ala SO. Si el ε ha desaparecido de la solución no hay ningún problema.
Ejemplo: La siguiente es la matriz obtenida luego de realizar el método de la esquina noroeste.
D1 D2 D3 D4 Oferta
5 3 2 4
F1 50
25 25 - -
2 3 4 2
F2 20
5 - 10 10
4 1 3 5 Como se puede observar, no hay forma de cerrar el ciclo
F3 - ε - 35 35
para la variable x34, y tampoco para la variable x12 ni para
Demanda 25 25 10 45 x11 o x21, por lo tanto, agregamos la variable ε como valor
de x32, esto nos permite entonces cerrar todos los ciclos y
continuar operando normalmente.
MODELO DE TRANSBORDO
Este modelo reconoce que puede ser más económico el transporte pasando por nodos intermedios o
transitorios antes de llegar al destino final. Este concepto es mas general que el del modelo normal
de transporte, que solo permite envíos directos. Para poder convertir un modelo de transbordo a
uno de transporte, se utilizaran amortiguadores.
Se utilizaran los siguientes conceptos:
Nodo de OFERTA PURA: Serán los nodos que solo envíen productos, sin recibir nada.
La oferta en este nodo será igual al suministro original
Nodo de DEMANDA PURA: son los nodos que solo reciben productos, sin reenviarlos.
La demanda en ellos será igual a la demanda original.
Nodo de TRANSBORDO: Estos nodos reciben y envían productos, a veces consumen productos y a
veces son solo depósitos desde los cuales se redistribuyen los productos.
Entonces, el nodo tendrá de oferta la oferta original del nodo, si es que este producía algo, más un
valor amortiguador, que debe ser lo suficientemente grande como para permitir que toda la oferta (o
demanda) original pase por cualquiera de los nodos de transbordo. Por lo tanto esta será la suma de
las ofertas o demandas originales.
La demanda será igual a la demanda original del nodo mas el valor amortiguador mencionado arriba.
Una vez representado esto, se procede a resolver el problema como si fuese un modelo de
transporte normal.
MODELO DE ASIGNACION
Este modelo se utiliza para asignar recursos o empleados a cierto puesto en particular. Este método
considera que la mejor persona para el puesto o el recurso más efectivo o la maquina más productiva
para cierta tarea cuesta menos que colocar un trabajador menos calificado, o usar recursos menos
efectivos o maquinas menos productivas. Por lo tanto el objetivo del modelo es determinar la
asignación más efectiva (optima, es decir, de costo mínimo) de trabajadores a puestos o recursos a
productos o maquinas a procesos.
En los ejemplos siguientes y demás, se tratara el modelo como si fuese la asignación de empleados a
puestos de trabajo.
39
Entonces, el modelo general de asignación con n trabajadores y n puestos, se representa de la
siguiente manera:
𝑃𝑢𝑒𝑠𝑡𝑜𝑠
𝑇𝑟𝑎𝑏𝑎𝑗𝑎𝑑𝑜𝑟𝑒𝑠
1 2 … n Oferta
1 C11 C12 … C1n 1
2 C21 C22 … C2n 1
… … … … … …
Como se ve, es una tabla de transporte, donde la
n Cn1 Cn2 … Cnn 1
demanda y la oferta de cada fuente y destino son 1 y
Demanda 1 1 … 1 donde la cantidad de fuentes y destinos es n. El elemento
Cij representa el costo de asignar al trabajador i al puesto j. No se pierde generalidad al suponer que
la cantidad de trabajadores es igual a la cantidad de puestos, puesto que siempre se pueden agregar
puestos o trabajadores ficticios para lograr el balance.
En este último caso, se creara el puesto o trabajador ficticio, cuyo valor de C será 0 a menos que se
desee penalizar un puesto o trabajador, de forma que no sea asignada una variable ficticia.
Si bien este problema puede resolverse como un problema de transporte, existe un método más
simple y rápido para resolverlo, que hace uso de las características particulares de este modelo.
MÉTODO HUNGARO
1- En la matriz original de costo, identificar el mínimo de cada fila y restarlo de todos los
elementos de la fila
2- En la matriz resultante, identificar el mínimo de cada columna y restarlo de todos los
elementos de la columna. En este punto debemos verificar que haya una asignación factible
en base a los elementos cero de la matriz. Cada puesto debe tener asignado un solo
trabajador y cada trabajador debe ser asignado a un solo puesto. Cuando un empleado sea
asignado a un puesto, el valor en la celda correspondiente será 0.
3- En caso de que no obtengamos una asignación factible en el punto anterior, deberemos
realizar lo siguiente:
o Trazar la cantidad mínima de líneas horizontales y verticales en la última matriz
reducida que cubran todos los elementos cero.
o Seleccionar el elemento mínimo que no esté tachado con una línea, restarlo de todos
los elementos no tachados y sumarlo a todos los elementos en la intersección de dos
líneas.
o Si no se puede encontrar una asignación factible entre los elementos cero que
resulten, se debe repetir el paso 3. En caso contrario, continuamos con el paso 4.
Para verificar si existe la asignación factible, lo que se hace es contar la cantidad de
líneas trazadas, si esta es = al número de puestos o de trabajadores, entonces la
solución es optima, en caso contrario se repite el paso 3
4- Identificar la solución optima como la asignación factible asociada con los elementos cero de
la matriz obtenida en el paso 3.
EJEMPLO:
40
𝑃𝑢𝑒𝑠𝑡𝑜𝑠 𝑃𝑢𝑒𝑠𝑡𝑜𝑠 𝑃𝑢𝑒𝑠𝑡𝑜𝑠

1 2 3 4 1 2 3 4 1 2 3 4
𝑇𝑟𝑎𝑏𝑎𝑗𝑎𝑑𝑜𝑟𝑒𝑠 𝑇𝑟𝑎𝑏𝑎𝑗𝑎𝑑𝑜𝑟𝑒𝑠 𝑇𝑟𝑎𝑏𝑎𝑗𝑎𝑑𝑜𝑟𝑒𝑠
1 $1 $4 $6 $3 1 0 $3 $5 $2 1 0 $3 $2 $2
2 $9 $7 $10 $9 2 $2 0 $3 $2 2 $2 0 $0 $2
3 $4 $5 $11 $7 3 0 $1 $7 $3 3 0 $1 $4 $3
4 $8 $7 $8 $5 4 $3 $2 $3 0 4 $3 $2 $0 0
Al finalizar el paso 2, podemos ver en la última tabla que si asignáramos al trabajador 1 el puesto 1, el
trabajador 3 no tendría ningún puesto en el que desempeñarse, por lo que esta no es una solución
optima factible.
Procederemos a realizar el paso 3 para poder obtener dicha solución

𝑃𝑢𝑒𝑠𝑡𝑜𝑠 𝑃𝑢𝑒𝑠𝑡𝑜𝑠
1 2 3 4 1 2 3 4
𝑇𝑟𝑎𝑏𝑎𝑗𝑎𝑑𝑜𝑟𝑒𝑠 𝑇𝑟𝑎𝑏𝑎𝑗𝑎𝑑𝑜𝑟𝑒𝑠
1 0 $3 $2 $2 1 0 $1 0 0
2 $2 0 $0 $2 2 $3 0 0 $2
3 0 $1 $4 $3 3 0 0 $3 $2
Por lo tanto, la solución optima
4 $3 $2 $0 0 4 $4 $2 $0 0 será Z=1+10+5+5 = 21
MODELO DE OPTIMIZACION DE REDES

RED – DEFINICIONES:
Una red consiste en una serie de NODOS enlazados con ARCOS (o RAMAS). La notación para una red
es (N,A), donde N es el conjunto de nodos y A es el conjunto de arcos.
Ejemplo de Red:
N= {1, 2, 3, 4, 5} 1 3 5
A= {(1,2), (1,3), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5)}
2 4
Cada red tiene asociado algún tipo de flujo (por ejemplo, flujo de productos petroleros por un
acueducto, flujo de vehículos por una ruta, etc.). En general el flujo en una red está limitado por la
capacidad de sus arcos, que pueden ser finitos o infinitos.
41
Se dice que un arco es DIRIGIDO u ORIENTADO si permite flujo positivo en una dirección pero no en
la dirección contraria. Una RED DIRIGIDA solo permite flujo dirigido. (La red ejemplo es una red
dirigida)
Una RUTA es una sucesión de arcos distintos que unen dos nodos, pasando por otros nodos,
independientemente de la dirección de flujo de cada arco. Una ruta forma un CICLO si conecta un
nodo consigo mismo, pasando por otros nodos. Por ejemplo, los arcos (2,3), (3,1) y (1,2) forman un
ciclo o bucle. Un CICLO es DIRIGIDO si consiste en una ruta dirigida, por ejemplo la ruta formada por
(2,3), (3,5), (5,4) y (4,2).
Una RED CONECTADA es aquella donde cada dos nodos distintos están enlazados al menos por una
ruta. La red ejemplo es conectada.
Un ARBOL es una red conectada que puede consistir solo en un subconjunto de todos los nodos en
ella, donde no se permiten ciclos, y un ARBOL DE EXPANSION es un árbol que enlaza todos los nodos
de la red, también sin permitir ciclos.
Ejemplos
ARBOL ARBOL DE EXPANSION
1 3 1 3 5
2 2 4
ARBOL DE EXPANSION MINIMA:
Este algoritmo enlaza los nodos de una red en forma directa e indirecta, con la mínima longitud de
las ramas enlazantes. Los pasos del procedimiento se pueden resumir en lo siguiente:
Tenemos dos conjuntos de nodos, aquellos conectados al árbol de expansión (C) y aquellos que no
están conectados (nC) .
En el inicio, el primer conjunto esta vacio, mientras que el segundo tiene todos los nodos disponibles.
1- El primer paso consiste en seleccionar un nodo cualquiera e incluirlo en el primer conjunto,
sacándolo del segundo.
2- Luego, se selecciona el nodo del conjunto (nC) que tenga el arco más corto entre el y
cualquier nodo del conjunto (C) y se lo extrae de su conjunto, transfiriéndose al conjunto (C)
3- Si es que el conjunto (nC) esta vacio, se ha formado un árbol de expansión mínima. En caso
contrario repetir el paso 2.
Ejemplo: 1 Empezamos con el nodo 1 por comodidad (PASO 1)
(C) 3
3 1 3 5
2
1 3 5
5 (nC)
2 8 1 4 3
5 2 4
(C) 2 2 (C) 2
2 4
1 3 5
1 3 5 42 8 4
5
8 1 2
2 4
5
4
5
(C) 1 3 5
1 3 5
(C)
5
PROBLEMA DE LA RUTA MÁS CORTA: Este problema consiste en encontrar la ruta más corta entre
2
2 4
2
una fuente y un destino, 4 modelo de transporte.
en un
(nC)
43
MÉTODO DE FLUJO MAXIMO: este método se utiliza para determinar el flujo máximo posible en una
red, esto es, la cantidad máxima que puede viajar por la red al mismo tiempo, desde un origen a un
destino o sumidero.
3 7 9 3
1 3 5
0
1 7
3 0 9
5
0
0 4
Para determinar
F esta
0 capacidad, debemos definir
2 2
0 primero
S el concepto de CORTE. Un corte define un
5
10 arcos que2cuando 0 5
conjunto de 4
se eliminan de la red, causan una interrupción total del flujo entre los
0
nodos fuente y sumidero
La capacidad de corte es igual a la suma de las capacidades de los arcos correspondientes. Entre
TODOS los posibles cortes en la red, el que tenga la capacidad menor será el que permite el flujo
máximo de la red. Dado que es muy trabajoso calcular cada posible corte en la red, se utiliza el
siguiente algoritmo que es bastante eficiente:
ALGORITMO DE FLUJO MAXIMO (FORD-FURKELSON):
Este algoritmo se basa en determinar rutas de interrupción que tengan flujo neto positivo entre los
nodos fuente y sumidero. Cada ruta comunica parte o todas las capacidades de sus arcos al flujo total
en la red.
Cada arco tiene dos valores, cij y cji, que representan el flujo máximo en cada dirección (desde el nodo
i al j y viceversa).
El nodo Fuente siempre tendrá una etiqueta de valor [∞; --], ya que teóricamente puede
recibir/emitir infinito flujo y este no proviene de ningún nodo de la red. El resto de los nodos llevaran
etiquetas de la forma [aj; i], siendo aj el valor del flujo máximo e i el nodo anterior del cual proviene
el flujo.
Paso 1: Empezando desde el nodo fuente, seleccionamos el arco con el mayor valor de cij (si hay
empate se rompe arbitrariamente, en general, tomando el de menor valor ordinal). Una vez nos
posicionamos en el nodo j, se le etiqueta de la siguiente forma [cij, i]. Luego se hace i=j y volvemos a
seleccionar el arco con el mayor valor de cij. Siendo J cualquier nodo conectado a este nodo.
Repetimos este paso hasta llegar al sumidero o destino. En caso de que algún nodo no tenga ningún
arco con valor de cij > 0 para poder seleccionar el siguiente, se tacha temporalmente este nodo de la
ruta y se vuelve al nodo anterior, seleccionando el siguiente nodo de mayor valor de cij. Si es que
luego de alguna iteración al volver al nodo fuente todos los arcos tienen cij = 0, significa que hemos
finalizado calculando y que hemos encontrado el flujo máximo.
Paso 2: Luego, para determinar el flujo (fk) máximo de esta ruta, seleccionamos el menor valor de ai
de todos los nodos etiquetados.
Paso 3: A cada valor de cij (el valor de c en el sentido del flujo) le restamos el valor de fk y a cada valor
de cji, es decir, en el sentido contrario al que tomo la ruta de corte formada, se le suma el valor de fk.
Paso 4: Volvemos al paso 1, pero con los valores de cij y cji cambiados en el paso anterior, los nodos
tachados se restablecen y las etiquetas (menos la del nodo fuente) se borran.
44
Finalmente, cuando terminamos de calcular todas las posibles rutas de corte (es decir, llegamos al
punto en que todos los arcos que salen de la fuente tienen valor 0, calculamos el flujo máximo de la
siguiente forma:
A) Si se han determinado m rutas de irrupción, entonces el flujo máximo de la red será:

F= f1+ f2+… +fm
B) Luego, para cada arco que va desde el nodo i al j, siendo los residuales inicial (𝐶 ̅̅̅̅ ̅̅̅
𝑖𝑗 ,𝐶𝑗𝑖 ) y final
̅̅̅̅
(cij, cji), para calcular el valor del flujo optimo en ese arco se calcular (α,β) = (𝐶 ̅̅̅
𝑖𝑗 - cij,𝐶𝑗𝑖 - cji). Solo uno
debe ser positivo y el valor del flujo óptimo de i a j será tal valor positivo.
Ejemplo:
45
ALGORITMO DE DIJKSTRA: Este método tiene por objeto determinar las rutas más cortas entre el
nodo fuente y todos los demás nodos de la red.
Este algoritmo funciona analizando cada nodo del modelo, partiendo desde el nodo 1 (la fuente)
hasta el destino, pasando por cada nodo de la red y determinando así el camino más corto a cada
uno de ellos. Se utilizan etiquetas temporales y permanentes para mostrar la distancia más corta
hasta el momento y el nodo predecesor con dicha distancia. [ui, k]
1- El algoritmo se inicia asignando al nodo fuente la etiqueta permanente [0, -], luego, a cada
nodo conectado al nodo fuente se le calcula la etiqueta temporal, tomando los valores [d1i,
1].
2- Nos posicionamos en el nodo S con el menor valor de us en su etiqueta temporal, y
calculamos la etiqueta para todos los nodos (j) que estén conectados a el, excepto aquellos
con etiqueta permanente. Si es que el nodo j ya tiene una etiqueta de valor [ujk, k],
verificamos si el valor de us + dsj ≤ ujk. Si es así, entonces se le cambiara la etiqueta al nodo
por [us + dsj; S]. Esto significa que si la distancia etiquetada mínima desde la fuente del nodo
analizado j es mayor a la distancia mínima desde la fuente del nodo S + la distancia entre S y
j, entonces modificamos la etiqueta para reflejar la menor distancia.
3- Si hemos analizado ya todos los nodos conectados al nodo S, entonces convertimos su
etiqueta en permanente, y verificamos si queda algún nodo con etiqueta temporal. Si es así,
pasamos al paso 2 nuevamente. Sino, significa que hemos encontrado el camino mínimo.
EJEMPLO: Encontraremos el camino mínimo de la red mostrada en el ejemplo anterior.

Paso 1
33 22
1
[0,-] 3
[3,1] 5
1 3 5
88 11 44
55
2
[5,1]
22 4
2 4
46
Paso 2
3 2 En este caso, este es el camino mínimo desde la fuente a
[0,-] [3,1] [5,3]
1 3 5 todos los nodos. En general, el problema no se resuelve
directamente en el paso 2, sino que toma varias iteraciones
8 1 4
5 para resolver.
[5,1] 2 [4,3]
2 4
47
PROGRAMACIÓN ENTERA
48
PROBLEMA DE CARGOS FIJOS
49
50
51
52
53
54
55
56
57
58
59
60
TEORIA DE COLAS
61
OBJETIVO:
- Diseño optimo para su instalación

- Cuando la capacidad del servicio disminuye, hay espera (en la cola o en el servidor)
- Debe haber equilibrio entre los tiempos de servicio y los tiempos de espera, ya que sino el
sistema colapsara.
• LINEA DE ESPERA: Se forma por la llegada aleatoria de clientes que entran a un

establecimiento a recibir un servicio proporcionado por un servidor (cuando la velocidad a la
que atiende el servidor es mayor a la velocidad de llegada de los clientes del sistema)
Servidor Simple
Clientes
Servidor Clientes
Cola de
que llegan que se van
Espera
Fuente de Sistema
Clientes
Servidores Paralelos
Servidor 1
Servidor 2
Clientes Cola de
que llegan Espera
Servidor 3
Fuente de Clientes
Clientes que se van
Sistema
Servidores en Serie
Servidor 1 Servidor 2
Clientes Cola de Clientes
Cola de
que llegan Espera 2 que se van
Espera 1
Fuente de Sistema
Clientes
TEORIA DE COLAS:
Los actores principales en una coa son el cliente y el servidor.
62
Los CLIENTES se generan en una FUENTE. Al llegar al SISTEMA pueden recibir servicio de inmediato o
esperar en una COLA, si es que no hay ningún servidor disponible. Cuando un servidor termina un
servicio, en forma automática un cliente pasa a ser atendido, si es que existe, desde la cola.
El proceso de llegada al sistema se describe con El TIEMPO ENTRE LLEGADAS de los sucesivos
clientes, mientras que el proceso de salida se representa con el TIEMPO DE SERVICIO por cada
cliente.
El TAMAÑO DE LA COLA puede ser finito o infinito
La DISCIPLINA DE LA COLA, representa el orden en que se seleccionan los clientes de una cola, las
más comunes son las siguientes
- FIFO: 1º en llegar, 1º en ser atendido

- LIFO: Ultimo en llegar, 1º en ser atendido
- Sistema de selección en orden aleatorio
- Sistema con prioridad en la espera
El comportamiento de los clientes en espera juega un papel importante en el análisis de las colas, ya
que los clientes humanos pueden saltarse de una cola muy llena a una más vacía o incluso abandonar
la cola por haber esperado demasiado.
Los servidores pueden ordenarse en PARALELO, EN SERIE, o incluso formar una RED de servidores.
La fuente donde se generan los clientes puede ser finita o infinita, una fuente FINITA es aquella
donde la cantidad de clientes a ser atendidos es limitada, mientras que la INFINITA es abundante por
siempre.
Estado del Sistema
Fase Fase de Estado

Transitoria Estable
FASE TRANSITORIA: Al inicio de la operación del sistema, su estado se encuentra bastante afectado
por el estado inicial y el tiempo que ha transcurrido desde el inicio.
FASE de ESTADO ESTABLE: Una vez que ha pasado suficiente tiempo, el estado del sistema se vuelve
independiente del estado inicial del sistema y del tiempo transcurrido. La distribución de
probabilidad del sistema se conserva a través del tiempo.
MODELO GENERALIZADO de COLA DE POISSON:

63
El desarrollo del modelo generalizado se basa en el comportamiento en ESTADO ESTABLE de la cola.
Este modelo supone que las frecuencias tanto de llegada como de salida dependen del estado, y eso
significa que dependen de la cantidad de clientes en la instalación de servicio. Esto se puede
observar, por ejemplo, en un supermercado, donde si la cola es muy larga, los cajeros trabajaran más
rápido que cuando no lo es.
TERMINOLOGIA Y NOTACION:
• N(t): nº de clientes en el sistema en el instante t. Describe el ESTADO DEL SISTEMA

• Nq(t): nº de clientes en la cola en el instante t. Describe el ESTADO DE LA COLA
• Pn(t): Es la probabilidad que en el instante t se encuentren n clientes en el sistema. Se supone
es conocido el nº de clientes en el instante inicial (usualmente 0)
• S: es el nº de servidores en el sistema
• λn: nº medio de llegadas al sistema por unidad de tiempo cuando ya hay n clientes (TASA DE
LLEGADAS para el estado n)
• μn: nº medio de clientes a los que se les completa el servicio por unidad de tiempo cuando
hay n clientes en el sistema (TASA DE SERVICIO para el estado n)
• λ: cuando λn es constante para todo n
• μ: cundo μn es contante para todo n ≥ 1
• 1⁄ : tiempo entre llegadas esperado
λ
• 1⁄ : tiempo de servicio esperado
μ
• ρ: factor de utilización para la instalación : λ⁄𝑠μ
DIAGRAMA DE TRANSICION en COLAS DE POISSON:
𝝀0 𝝀0 𝝀n-1 𝝀n
0 1 2 … n-1 n n+1
μ1 μ2 μn μn+1
Este diagrama nos representa la transición de estados en una cola de Poisson, el sistema se
encuentra en el estado n, cuando hay n clientes en él. Al ser una distribución de poisson, la
probabilidad de que se dé más de un cambio de estado en un intervalo pequeño h, tiende a 0 cuando
h→0.
Esto quiere decir que para n > 0, el estado n solo puede cambiar a dos estados, n-1 cuando hay una
salida con la frecuencia μn y al estado n+1 cuando hay una llegada con la frecuencia 𝝀n. El estado 0
solo puede cambiar al estado 1 cuando hay una llegada con la frecuencia 𝝀0. μ0 no está definida ya
que no puede haber salidas si el sistema esta vacio.
Entonces, si el sistema se encuentra en estado estable, para cualquier n >0, las tasas esperadas de
flujo de entrada y salida del estado n deben ser iguales. Como n solo puede cambiar a los estados
n+1 y n-1, tenemos:
64
Tasa esperada de flujo HACIA el estado n = 𝝀n-1 Pn-1 + μn+1 Pn+1
Tasa esperada de flujo DESDE el estado n = (𝝀n + μn) Pn
Al ser iguales tenemos: 𝝀n-1 Pn-1 + μn+1 Pn+1 = (𝝀n + μn) Pn para cualquier n >0
Luego, para n = 0 tendremos que 𝝀n-1 = 0 y que μn = 0, entonces la ecuación anterior nos quedaría
como:
μ1P1 = 𝝀0P0
Las demás ecuaciones de balance para las demás Pn con n> 0 se resuelven recursivamente a partir de
P0, entonces tenemos que:
𝝀𝟎 𝑷𝟎
P1 = 𝛍𝟏
Después, para n = 1, tendremos :
𝝀0 P0 + μ2 P2 = (𝝀1 + μ1) P1
si reemplazamos la ecuación anterior obtenemos
𝜆0 𝑃0 𝜆0 𝑃0 1
𝝀0 P0 + μ2 P2 = (𝝀1 + μ1) μ1
μ2 P2 =(𝝀1 + μ1) μ1
- 𝝀0 P0 μ2 P2 =((𝝀1 + μ1) μ – 1) 𝝀0 P0 μ2
1
λ1
P2 =( +1-1) 𝝀0 P0
μ1
𝛌 𝛌
P2 = 𝛍𝟏𝛍𝟎 P0
𝟏 𝟐
Por inducción, llegamos a que en general para n = n tenemos:
𝛌𝒏−𝟏 𝛌𝒏−𝟐 … 𝛌𝟎
Pn = P0 para todo n = 1,2,…
𝛍𝒏 𝛍𝒏−𝟏 …𝛍𝟏
Y el valor de P0 podemos determinarlo sabiendo que la suma de las probabilidades de que ocurra
un suceso n, con n ≥ 0, será igual a 1:
∑∞
𝒏=𝟎 𝑷𝒏 = 1
Otra fórmula a tener en cuenta para calcular el valor de P0 es la suma de una serie geométrica, que
nos dice que:
𝟏
∑∞ 𝒊
𝒊=𝟎 𝒙 = para todo |𝒙| < 1 (ya que en el límite, cuando i tiende a infinito, el valor de 𝑥 𝑖 tenderá a
𝟏−𝒙
0, de otra manera, se aplican la formulas que siguen:
𝒙 − 𝒙𝒏+𝟏
∑𝒏𝒊=𝟏 𝒙𝒊 =
𝟏−𝒙
𝒏−𝟏 𝒊 𝟏 − 𝒙𝒏
∑𝒊=𝟎 𝒙 =
𝟏−𝒙
NOTACION DE KENDALL-LEE para sistemas de COLAS
(a/b/c) : (d/e/f)
Donde:
a- Descripción de la distribución de llegadas

b- Descripción de la distribución de salidas
c- Numero de servidores paralelos
d- Disciplina de cola
e- Número máximo (finito o infinito) permitido en el sistema (en cola y además en servicio)
f- Tamaño de fuente demandante (finito o infinito)
MEDIDAS DE RENDIMIENTO DE ESTADO ESTABLE:

65
Ls = Cantidad esperada de clientes en el sistema
Lq = cantidad esperada de clientes en la cola
Ws = Tiempo aproximado de espera en el sistema, es decir, el tiempo que permanece un cliente en el

sistema desde que ingresa hasta que sale
Wq = tiempo aproximado de espera en la cola
𝑐̅ = Numero esperado de servidores ocupados
A partir de estas definiciones podemos deducir que:
Ls = ∑∞
𝒏=𝟏 𝒏𝑷𝒏
Lq = ∑∞
𝒏=𝒄+𝟏(𝒏 − 𝒄)𝑷𝒏 , siendo C la cantidad total de servidores
Las relaciónes entre L y W están dadas por las FORMULAS DE LITTLE y son:
Ls = Wsλef
Lq = Wqλef
λef es la tasa de llegada efectiva, es decir, todos aquellos clientes que llegan y se quedan en el
sistema. Este valor diferirá del valor de λ si la cola tiene un tamaño límite (N-1), en esos casos, λef <λ
λef = λ(1 – PN)
Luego, sabemos que el tiempo de espera en el sistema (Ws) sera igual a la cantidad de tiempo de
espera en la cola (Wq), más el tiempo de servicio (1⁄μ), entonces:
Ws = Wq + 𝟏⁄𝛍
Si a esta ecuación la multiplicamos por λef podemos relacionar la cantidad de clientes en el sistema y
en la cola con la tasa de salida, entonces tendremos:
λ
Ls = Lq + ef ⁄μ
Ls = Lq + ρ
Sabemos que el numero de servidores ocupados (𝑐̅) es igual a la diferencia entre la cantidad total de
clientes en el sistema, menos la cantidad de clientes en la cola, entonces tenemos que:
𝑐̅ = Ls – Lq = ρ
El porcentaje de utilización de los servidores se calcula como s/𝑐̅ %
MODELO DE UN SOLO SERVIDOR:
M/M/1
En este modelo tenemos que:
66
- los tiempos de llegadas son exponenciales
- la rapidez de llegadas por unidad de tiempo es λ
- tenemos un solo servidor
- Los tiempos de servicio son exponenciales
- La rapidez de servicio para cada cliente es μ
Entonces, el sistema se puede representar como un proceso de nacimientos y muertes con los
siguientes parámetros:
𝝀j = 𝝀 para todo j=0,1,2,…
μ0 = 0 por definición
μj = μ para todo j=1,2,3…
De la formula general para determinar Pn tenemos que:

𝛌𝒏−𝟏 𝛌𝒏−𝟐 … 𝛌𝟎
Pn = 𝛍𝒏 𝛍𝒏−𝟏 …𝛍𝟏
P0
Dado que 𝝀j y μj son constantes, la formula se convierte en:

𝛌𝐧
Pn = 𝛍𝐧 P0 o lo que es lo mismo: Pn = 𝝆𝒏 P0
Para determinar P0 utilizamos la identidad mencionada anteriormente:
∑∞
𝒏=𝟎 𝑷𝒏 = 1
de aquí vemos que

𝒏
∑∞ 2 3 n
𝒏=𝟎 𝝆 P0 = P0(1 + ρ + ρ + ρ + … + ρ ) = 1
Si suponemos que ρ es < 1 (ya que nos encontramos en un estado estable, de otra forma, la cola
crecería infinitamente), podemos aplicar la suma de una serie geométrica, entonces la formula
anterior se convertiría en:
𝟏
P0𝟏−𝝆 = 1 → P0 = 𝟏 − 𝝆
Habiendo determinado P0 podemos calcular las medidas de rendimiento para el sistema:
Ls = ∑∞
𝒏=𝟎 𝒏𝑷𝒏
Ls = ∑∞ 𝑛
𝑛=0 𝑛𝜌 P0
Ls = ∑∞ 𝑛 ∞
𝑛=0 𝑛𝜌 (1 − 𝜌) = (1 − 𝜌) ∑𝑛=0 𝑛𝜌
𝑛
Luego si definimos S’ como ∑∞ 𝑛 0 1 2 3

𝑛=0 𝑛𝜌 = 0ρ + ρ +2ρ +3ρ + …
Observamos que ρS’ = ρ2 +2ρ3 +3ρ4 + …

entonces si hacemos
67
ρ
S’ - ρS’= ρ +ρ2 +ρ3 + … =∑∞ 𝑛
𝑛=1 𝜌 =
1−ρ
ρ 𝛒
Por lo tanto, S’ (1 – ρ) = --> S’ =
(1−ρ) (𝟏−𝛒)𝟐
ρ
Ls = (1 − ρ) 2
(1−ρ)
𝛒
Ls =
𝟏−𝛒
A partir de Ls podemos calcular las demás medidas de rendimiento:
Ws = Ls / 𝝀
𝛌
𝝆 𝟏 𝟏 𝟏
Ws = 𝟏−𝝆 𝛌 = 𝝁
𝟏−𝝆 𝛌
=
𝝁 (𝟏−𝝆)
1 1 1 – (1−𝜌) 𝛒
Wq = Ws – 1/ 𝜇 = − = =
𝜇 (1−𝜌) 𝜇 𝜇 (1−𝜌) 𝛍 (𝟏−𝛒)
𝛒 𝛒𝟐
Lq = Wq.𝝀 = 𝛍 (𝟏−𝛒) λ=
𝟏−𝛒
𝒄̅ = Ls – Lq = ρ
M/M/1 FIFO/C/∞
- Si la capacidad del sistema es C, entonces el tamaño de la cola será de C-1, en cambio, si se
considera C como el tamaño de la cola, el sistema tendrá una capacidad de C+1 clientes.
- Aparece una TASA EFECTIVA de clientes que ingresan y que depende de C, ya que aquellos
clientes que lleguen luego de que se alcanza la capacidad límite del sistema, se perderán
permanentemente.
- No se necesita que ρ sea < 1 porque el sistema NO explota, ya que la cola está limitada (no
crecerá infinitamente).
El sistema se modela como un proceso de nacimiento y muerte, con un límite C que es la capacidad
del sistema, entonces tenemos:
𝝀 𝝀 𝝀
0 1 2 … C-1 C
μ μ μ
68
𝝀n y μn son constantes para todo n < C, μ0 = 0 y 𝝀C = 0, esto evita que se pase a un estado imposible
como ser el -1 o que se supere el tamaño del sistema, es decir el estado C+1.+6
Sabemos que Pn = ρnP0
También sabemos que ∑∞

𝒏=𝟎 𝑷𝒏 = 1 pero como C es el límite del sistema, Pn = 0 para n > c, entonces
→
∑𝑪𝒏=𝟎 𝑷𝒏 = 1 de aquí podemos deducir el valor de P0
∑𝑪𝒏=𝟎 𝝆𝒏 P0= 1
Luego, ∑𝑪𝒏=𝟎 𝝆𝒏 = ρ0 + ρ1 +ρ2 + ρ3 +… + ρC
De aquí, tenemos 2 posibilidades, si ρ = 1 entonces:
ρ0 + [ρ1 +ρ2 + ρ3 +… + ρC] = 1 + C
1 − 𝑥 𝑛+1
Si ρ ≠ 1 entonces, aplicando la formula ∑𝑛𝑖=0 𝑥 𝑖 = , tenemos:
1−𝑥
𝟏 − 𝝆𝑪+𝟏
∑𝑪𝒏=𝟎 𝝆𝒏 =
𝟏−𝝆
Finalmente, según el valor de ρ tendremos:

𝟏−𝝆
𝟏−𝝆𝑪+𝟏
, 𝜌≠1
𝑃0 = { 𝟏
, 𝜌=1
𝟏−𝑪
Luego, a partir del valor de P0 podemos calcular el valor de Ls y todas las demás medidas de
rendimiento.
Ls = ∑𝑪𝒏=𝟎 𝒏𝑷𝒏
Ls = ∑𝑪𝒏=𝟎 𝒏𝝆𝒏 P0 = P0∑𝑪𝒏=𝟎 𝒏𝝆𝒏
Luego, si 𝜌 ≠ 1, entonces :
Si S’ = ∑𝑪𝒏=𝟎 𝒏𝝆𝒏 = 0ρ0 + ρ1 +2ρ2 + 3ρ3 +… + CρC y ρS’ = ρ2 +2ρ3 + 3ρ4 +… + CρC+1
Entonces S’ - ρS’ = ρ1 +ρ2 + ρ3 +… + ρC - CρC+1
𝜌 − ρ𝐶+1 𝜌 − ρ𝐶+1 −𝐶ρ𝐶+1 +𝐶ρ𝐶+2

S’ (1-ρ) =∑𝐶𝑛=1 𝜌𝑛 - CρC+1 --> 1−ρ
- C ρC+1 --> 1−ρ
𝜌 − ρ𝐶+1 (1−𝐶+𝐶ρ) 𝜌 − ρ𝐶+1 (1−𝐶+𝐶ρ)

S’ (1-ρ) = --> S’ = (1−ρ)2
1−ρ
Finalmente, reemplazando en la formula de Ls, tenemos:
𝟏 − 𝝆 𝜌 − ρ𝐶+1 (1−𝐶+𝐶ρ)
Ls = P0∑𝑪𝒏=𝟎 𝒏𝝆𝒏 = 𝟏−𝝆𝑪+𝟏 (1−ρ)2
69
𝝆 − 𝛒𝑪+𝟏 (𝟏−𝑪+𝑪𝛒)
Ls = (𝟏−𝛒 )(𝟏−𝝆𝑪+𝟏 )
El resto de las medidas de rendimiento pueden ser calculadas a partir de este valor.
M/M/S FIFO/∞/∞
- El sistema estará formado por S servidores en paralelo, con una velocidad de atención μ cada
uno, esto implica que la rapidez de atención será igual a la suma de la rapidez de atención de
los servidores ocupados. Esto es, si hay j servidores ocupados, la velocidad de atención del
sistema será jμ.
De aquí podemos deducir que:
𝑛𝜇 𝑛 ≤ 𝑠
μn = {
𝑠𝜇 𝑛 > 𝑠
- Dado que no hay un límite en el tamaño del sistema, 𝝀j = 𝝀 para todo j.
El sistema se modela como un proceso de nacimiento y muerte,
𝝀 𝝀 𝝀 𝝀
0 1 2 … S S+1 …
μ 2μ sμ sμ
Podemos entonces, calcular Pn = P0ρn

λn λn ρn
Si 𝑛 ≤ 𝑠, entonces Pn = P0 ( )= ( 𝑛 )P0 = ( )P0
𝜇(2𝜇)(3𝜇)… 𝜇 𝑛! 𝑛!
λn λn ρn
Si 𝑛 > 𝑠, entonces Pn = P0 (𝜇(2𝜇)(3𝜇)…((𝑠−1)𝜇)(𝑠𝜇)𝑛−𝑠+1 )= (𝜇𝑛 𝑠!𝑠𝑛−𝑠 )P0 = (𝑠!𝑠𝑛−𝑠 ) P0
Luego, si ρ/c < 1, entonces el valor de P0 se determina de ∑𝑪𝒏=𝟎 𝑷𝒏 = 1
λn λn
Esto es igual a ∑𝒔−𝟏 ∞ 𝒔−𝟏 ∞
𝒏=𝟎 𝑷𝒏 + ∑𝒏=𝒔 𝑷𝒏 = ∑𝒏=𝟎 (𝜇𝑛 𝑛!)P0 + ∑𝒏=𝒔 (𝜇𝑛 𝑠!𝑠𝑛−𝑠 ) P0
λn λn
-- > P0 (∑𝒔−𝟏 ∞
𝒏=𝟎 (𝜇𝑛 𝑛!) + ∑𝒏=𝒔 (𝜇𝑛 𝑠!𝑠𝑛−𝑠 )) = 1
λn ρn 1 ∞ ρn
Si ρn = 𝜇𝑛 entonces -- > P0 (∑𝒔−𝟏
𝒏=𝟎 ( 𝑛! ) + 𝑠! ∑𝒏=𝒔 (𝑠𝑛−𝑠 )) = 1
n n−s s
Si consideramos que en la segunda sumatoria ρ = ρ ρ , entonces tenemos:
ρn ρs ρn−s ρn ρs ∞ ρ 𝑛−𝑠
P0(∑𝒔−𝟏
𝒏=𝟎 ( ) + ∑∞
𝒏=𝒔 ( )) = P0(∑𝑠−1
𝑛=0 ( ) + ∑𝑛−𝑠=0 ( ) )=1
𝑛! 𝑠! 𝑠𝑛−𝑠 𝑛! 𝑠! 𝑠
Finalmente, resolvemos la segunda sumatoria y obtenemos:
ρn ρs 1
P0(∑𝑠−1
𝑛=0 ( 𝑛! ) + ( ρ))
𝑠! 1−
= 1, pasando al otro término, obtenemos:
𝑠
70
−1
ρn ρs 1
P0 = (∑𝑠−1
𝑛=0 ( 𝑛! ) + ( ρ))
𝑠! 1−
𝑠
Con estas formulas podemos calcular el resto de las medidas de rendimiento.

NOTA: En el libro se usa C en vez de S para el número de servidores
M/M/S FIFO/C/∞
- El sistema estará formado por S servidores en paralelo, con una velocidad de atención μ cada
uno, esto implica que la rapidez de atención será igual a la suma de la rapidez de atención de
los servidores ocupados. Esto es, si hay j servidores ocupados, la velocidad de atención del
sistema será jμ.
De aquí podemos deducir que:
𝑛𝜇 𝑛 ≤ 𝑠
μn = {
𝑠𝜇 𝑛 > 𝑠
- El tamaño del sistema está limitado a C clientes, por lo tanto
λ 𝑛≤ 𝐶
𝝀n = {
0 𝑛 > 𝐶
El sistema se modela como un proceso de nacimiento y muerte,
𝝀 𝝀 𝝀 𝝀 𝝀
0 1 2 … S S+1 … C-1 C
μ 2μ sμ sμ sμ
71
ρn
( ) P0 𝑛 ≤ 𝑆
𝑛!
Entonces, Pn = { ρn
(𝑠!𝑠𝑛−𝑠 ) P0 𝑆 < 𝑛 < 𝐶
NOTA: En el libro se usa C en vez de S para el número de servidores
M/M/∞ FIFO/∞/∞ - MODELO DE AUTOSERVICIO
En este modelo, el número de servidores es ilimitado porque el cliente es también el servidor. Un

ejemplo típico es tomar la parte escrita de la prueba para el permiso de conducir.
El modelo supone que la tasa de llegadas es constante. La tasa de servicio también es constante.
Entonces, tendremos que:
𝝀j = 𝝀 para todo j=0,1,2,…
μ0 = 0 por definición
μj = μ para todo j=1,2,3…
72
ρn
Pn = ( )P0
𝑛!
M/M/R FIFO/K/K R < K- MODELO DE Servicio de Maquinas
El escenario para este modelo es un taller que incluye un total de K maquinas. Cada vez que
una maquina se avería, se requiere el servicio de uno de los R mecánicos disponibles. La tasa
de averías por maquina es 𝝀 averías por unidad de tiempo, este valor también nos indicara
cuanto tiempo permanecerá una maquina sin averiarse. Un mecánico dará servicio a las
maquinas averiadas a una tasa de μ maquinas por unidad de tiempo. Se supone que las
averías y servicios siguen una distribución de poisson.
Este modelo difiere de los anteriores en que la fuente demandante es finita, en el sentido de
que hay un límite en el número de demandas que la fuente puede generar. Esto es obvio, ya
que si todas las maquinas del taller están averiadas, no será posible que se generen más
demandas. En esencia, solo las maquinas que funcionan se pueden averiar.
Esto implica que en cualquier momento una maquina está en buen estado o en mal estado
(averiada)
Si el numero de maquinas averiadas es menor al número de mecánicos, cuando alguna se

averíe se empezara a trabajar sobre ella inmediatamente. En cambio, si la cantidad de
maquinas averiadas es igual o mayor al número de servidores, entonces las maquinas
pasaran a una cola de espera.
El modelo reparación de maquinas puede representarse como un proceso de nacimiento y

muerte en el que el estado j en cualquier momento es el numero de maquinas averiadas.
73
Servidor 1
1 Maquinas que se
2 averían con una
tasa de 𝝀
Servidor 2
…
i Cola de Espera de …………

capacidad max K-R
…
Servidor R
K
Fuente de Maquinas que se

Clientes de reparan con una
tamaño K velocidad μ
Sistema
Dada la tasa de averías por maquina 𝝀, la tasa de averías para todo el taller es proporcional
al número de maquinas que funcionan. En termino de modelo de colas, tener n maquinas en
el sistema, significa que n maquinas están averiadas. Así, la tasa de averías para todo el taller
se calcula como:
Y generalizando obtenemos:
Con esto podemos calcular las probabilidades:
Para este modelo, es difícil obtener una forma cerrada para Ls o Lq, ya que variara dependiendo la
cantidad de maquinas, por lo que debe calcularse como:
Luego, la tasa de averías efectiva será:

PROCESOS DE DECISIÓN:
Fijar el nivel de los parámetros tal que se logre un equilibrio entre el costo de operar el sistema y el
costo asociado a la empresa.
74
C(E )
Costo
Costo
minimo
Numero
Nº de Servidores Optimo de
Servidores
Hay 3 tipos de problemas:
1- Dados C(E) y C(S), 𝝀 y μ, encontrar S*
2- Dados μ y S encontrar el mejor ρ (la forma más eficiente de atender a los clientes)
3- Dado el Costo medio de servicio, el costo fijo de servicio por unidad de tiempo, 𝝀 y μ,
encontrar el numero de estaciones de servicio y el numero de servidores por estación que
minimicen el CT.
SISTEMAS DE REDES QUE FORMAN COLAS:

Una RED DE COLAS es un grafo orientado donde cada nodo representa una ESTACION DE SERVICIO y
cada arco representa un flujo entre estos nodos.
Ejemplo, RED ABIERTA DE JACKSON:
1
P12
𝝀1 s=1 𝝀3
μ1
P13
P21 2
P31 s=2
P23 μ2
3
𝝀2
s=1 P32
μ3
Cada nodo tiene S servidores, con s ≥ 1

Los clientes dentro de la red pueden salir del sistema o ir a otro nodo. Al entrar a un nodo, lo pueden
hacer desde otro nodo o desde el exterior.
El tiempo de permanencia puede ser finito o infinito
La ESTACION DE SERVICIO (o de servidores) “j” tiene las siguientes propiedades:
1 Los clientes llegan desde fuera del sistema de acuerdo a un proceso de Poisson con tasa de
llegada 𝝀j
2 Los servidores de dicha estación tienen un tiempo de servicio μj
75
3 Cuando un cliente deja la instalación i, pueden ocurrir 2 cosas:
a) Se encamina hacia la instalación j (j = 1,2, … j≠ i ), con probabilidad Pij (es independiente
del estado del sistema)
b) Sale del sistema con probabilidad:
Pi0 = 1- ∑𝑘𝑗=1 𝑃𝑖𝑗, donde i = 1,2,…, k y j = 1,2,…,k pero I ≠ j
4 Los clientes llegan desde otros nodos de acuerdo a un proceso de Poisson con parámetro
ΛjPij.
5 Los clientes llegan desde afuera del sistema y desde otros nodos con una tasa de llegadas:
6 Λj = 𝝀j + ∑𝑘𝑖=1 Λ i𝑃𝑖𝑗 (sjμj > Λj)
𝑖≠𝑗
Donde:
Λ j: Tasa de flujo medio total en el nodo j
Λ i𝑃𝑖𝑗: Tasa a la que los clientes llegan a la estación j desde otros nodos
𝝀j : Tasa de llegada de los clientes desde el exterior del sistema
REDES ABIERTAS: Los clientes pueden entrar y salir

REDES CERRADAS: Ningún cliente puede entrar o salir del sistema
𝝀j = 0 para todo j : ningún cliente puede entrar al sistema
Pj0 = 0 para todo j : Ningún cliente puede salir del sistema
PROPIEDADES DE EQUIVALENCIA:
Si una estación de servicio tiene s servidores, 𝝀 flujo de entrada poisson, μ flujo de servicio
exponencial, sjμj > Λj
> La salida en estado estable de esta instalación de servicio, también es un proceso de poisson
con parámetro 𝝀
> Por lo tanto, los clientes servidos dejaran la instalación de servicio de acuerdo a un proceso
de poisson.
COLAS EN SERIE:
Son sistemas de colas exponenciales con K estaciones diferentes en serie (o tándem) de manera que
el cliente deberá pasar por todas las estaciones antes de completar el servicio.
Los clientes solo pueden entrar por el primer nodo y salir por el último nodo, es decir, no pueden
saltearse ningún nodo.
Si consideramos un sistema en serie de K estaciones, entonces:
1- Las llegadas al sistema son generadas de una población infinita
2- Los clientes llegan al sistema con tasa de poisson 𝝀
3- Los clientes pasan por totas las estaciones hasta que salen por la estación K
4- Cada nodo tiene un mecanismo de servicio con s servidores con tasas de servicio μk
5- Toda estación tiene sala de espera de capacidad infinita
6- Los tiempos entre llegadas para alcanzar cada nodo del sistema de colas están distribuidos
exponencialmente con tasa de llegada 𝝀
Para que esto ocurra: sjμj > 𝝀j
76
Podemos analizar cada estación separadamente como colas de nivel único (es decir, no en serie)
Entonces, para cada instalación se puede obtener Pi, Lqi, Wqi
La probabilidad de tener N clientes en una instalación en particular dada por Pn, según el caso si la
cola es M/M/1 o M/M/s
PARA EL SISTEMA COMPLETO:
- La probabilidad conjunta de tener n1 clientes en la estación 1, n2 clientes en la estación 2, etc.,
es el producto de las probabilidades individuales y se conoce como solución en forma de
producto y se la expresa como
P{(n1,n2,n3… nk) = Pn1 . Pn2 . … . Pnk }
- El tiempo medio total esperado en la cola es la suma de los tiempos de espera en cada estación:
Wq = ∑𝑘𝑖=1 Wqi
- El numero esperado total de clientes en el sistema
Ls = ∑𝑘𝑖=1 Lsi
Lq = ∑𝑘𝑖=1 Lqi
- El tiempo promedio que pasa un cliente en el sistema
W = Ls / 𝝀
COLAS EN SERIE CON BLOQUEO

Cada estación esta libre u ocupada.
La estación 1 se dice que está bloqueada si el cliente en esta estación completa su servicio antes que
la próxima estación llegue a estar libre.
Los estados se representan con 0, 1, B, para libre, ocupado y bloqueado.
Los estados posibles de 2 estaciones consecutivas son :
(0,0) (0,1) (1,0) (1,1) (B,1)
Pij (t) es la probabilidad de que las estaciones este en el estado (i,j) en el tiempo t.
La probabilidad de transición entre los tiempos t y t+∆t se resumen como:
0,0 0,1 1,0 1,1 B,1
0,0 1 - 𝝀h 𝝀h
0,1 μ-h(1- 2h) 1- μh-𝝀h 2h(1- μh)
1,0 μh(1- 𝝀h)
1,1 1- μh 1- μh μh
B,1 μh 1- μh
(COMPLETAR)
P00= 2/A
P01 = 2ρ/A
P10= (ρ2 + 2ρ) / A
PB1= ρ2/A
A = 3ρ3+4ρ+2
Ls = 5ρ2 + 4 ρ / A
La probabilidad de que un cliente llegue a la estación 1 es P00 + P01
77
Tasa efectiva de llegada a la estación 1 𝜆̅ = 𝝀(𝑷𝟎𝟎 𝑷𝟎𝟏 )
𝐿
El tiempo de espera en el sistema es: W = 𝜆̅
El tiempo promedio en que un cliente puede ser atendido siempre que no esté bloqueada la estación
2
1=𝜇
2
El tiempo promedio que espera un cliente si la estación 1 está bloqueada: W - 𝜇
REDES DE JACKSON
Es una generalización de las colas en serie para una red abierta.
Es un sistema de k instalaciones de servicio donde la instalación j tiene las siguientes propiedades:
1- Una cola INFINITA (es decir, no existen bloqueos)
2- Los clientes llegan desde fuera del sistema de acuerdo a un proceso de Poisson con tasa de
llegada 𝝀j
3- Los servidores de dicha estación tienen un tiempo de servicio μj
4- Cuando un cliente deja la instalación i, pueden ocurrir 2 cosas:
c) Se encamina hacia la instalación j (j = 1,2, … j≠ i ), con probabilidad Pij (es independiente
del estado del sistema)
d) Sale del sistema con probabilidad:
Pi0 = 1- ∑𝑘𝑗=1 𝑃𝑖𝑗, donde i = 1,2,…, k y j = 1,2,…,k pero I ≠ j
5- Los clientes llegan desde otros nodos de acuerdo a un proceso de Poisson con parámetro
ΛjPij.
6- Los clientes llegan desde afuera del sistema y desde otros nodos con una tasa de llegadas:
Λj = 𝝀j + ∑𝑘𝑖=1 Λ i𝑃𝑖𝑗 (sjμj > Λj) Comportandose como si fuense un sistema M/M/S
𝑖≠𝑗
Dado que esta última propiedad no puede ser demostrada directamente, podemos deducirla:
P10 1
𝝀1 Λ1 P12 𝝀3
M/M/S
μ1
P13
P21 2 Λ2=𝝀2 + Λ1P12 +Λ3P32
Λ2 P20
P31 M/M/S Λ1=𝝀1 + Λ2P21 +Λ3P31
P23 μ2 Λ3=𝝀3 + Λ2P23 +Λ1P13
=2
3
𝝀2 Λ3
P32
M/M/S
μ Λ
=1
P30
3
- ρi = 𝜇 𝑠𝑖
𝑖 𝑖
- Tasa de llegada al sistema:
λ = ∑𝑘𝑗=1 𝜆𝑗 donde 𝜆𝑗 es la tasa de llegadas desde el exterior al sistema
- Probabilidad de tener N clientes en una estación particular:
78
𝑀/𝑀/1
Pnj {𝑀/𝑀/∞
𝑀/𝑀/𝑠
- Probabilidad Conjunta (solución en forma de producto)
P{(n1,n2,n3… nk) = Pn1 . Pn2 . … . Pnk }
- Numero esperado de clientes Lsi en la estación i:
𝜌𝑖
𝑀/𝑀/1
1−𝜌𝑖
Lsi = {𝐿𝑞 𝜌 𝑀/𝑀/∞
𝑖+ 𝑖
𝜌𝑖 𝑀/𝑀/𝑠
- Número total de clientes en todo el sistema:
Ls = ∑𝑘𝑗=1 𝐿𝑠𝑗
- Tiempo de espera total en el sistema:
𝐿𝑠 𝐿𝑠
W= =
∑𝑘
𝑗=1 𝜆𝑗 𝜆
- Tiempo de espera de un cliente que va del nodo 1 al 2

Wq1 + Wq2
- Probabilidad de que un cliente deje la estación i y salga del sistema
qi = 1 - ∑𝑘𝑗=1 𝑃𝑖𝑗 = Pi0
Matriz de probabilidades:
1 2 … 𝑖 … 𝑘
1 0 𝑃12 ⋯ 𝑃1𝑖 ⋯ 𝑃1𝑘
2 𝑃21 0 ⋯ 𝑃2𝑖 ⋯ 𝑃2𝑘
P = {Pij} = ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑖 𝑃𝑖1 𝑃𝑖2 ⋯ 0 ⋯ 𝑃𝑖𝑘
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑘 (𝑃𝑘1 𝑃𝑘2 ⋯ 𝑃𝑘𝑖 ⋯ 0 )
REDES CERRADAS DE JACKSON

- Si en Λj =𝝀j + ∑𝑘𝑖=1 Λi𝑃𝑖𝑗 establecemos que 𝝀j = 0 y además, Pj0 = 0, con j = 1,2,… k, entonces
𝑖≠𝑗
tenemos una red cerrada de Jackson
- También tendremos una cola de fuentes finitas de N ítems que continuamente viajaran
dentro de la red.
Para un servidor si Si=1 para todo i, podemos obtener las ecuaciones de equilibrio para el flujo de
estado estable a partir de las ecuaciones para el modelo de redes abierta, donde establecemos 𝝀j =
Pj0 = 0. Entonces planteamos que el flujo dentro del nodo i debe ser igual al flujo fuera del nodo i
SIMULACION
- Es una técnica muy poderosa que se utiliza para analizar problemas complejos
- En escencia imita el funcionamiento de un sistema del mundo real cuando evoluciona en el
tiempo
79
80
El uso de la simulación permite de una manera rápida y económica adquirir el conocimiento que se
obtiene normalmente de la experiencia.
La idea básica es la construcción de un dispositivo experimental o SIMULADOR que actuara como el
sistema de interés en ciertos aspectos importantes, de una manera rápida y redituable.
81
En un modelo de simulación los valores de las variables de decisión son entradas, mientras que en un
modelo de optimización las variables de decisión son resultados.
SIMULACION DE EVENTOS DISCRETOS:
Considérese un sistema de colas de espera con un solo servidor. Los clientes son servidos
inmediatamente si el servidor está desocupado, sino deberán hacer cola.
Llegada Salida
Desocupado Ocupado
Esta No Hay Si
do Cola
Seleccionar
Cliente es Cliente Cambiar
cliente de la
Atendido Espera en estado a cola. Cambiar
Cola desocupado estado a
ocupado
AT = TM + IT
DT = TM + ST
Donde:
- AT (Arrival Time):Tiempo programado para la próxima llegada
- TM: Hora de la simulación
- IT: Tiempo entre llegadas
- DT (Departure Time): Tiempo programado para la próxima salida
- ST (Service Time): Tiempo de servicio
Lo que se hace es pogramar el tiempo de salida del 1º como el tiempo de salida a la hora en el
momento de la simulación + el Tiempo de salida programado.
Lo mismo con el tiempo de llegada.
IT Prob ST Prob
1 min 0.20 1 min 0.35
2 min 0.30 2 min 0.40
3 min 0.35 3 min 0.25
4 min 0.15
Luego, se generan números aleatorios siguiendo la probabilidad.

Otra forma de generar los números es por medio de una tabla de números al azar
82
83
84
85
86
87
88
89

Mit Apunte Investigación Operativa PDF

Cargado por

Copyright:

Formatos disponibles

Mit Apunte Investigación Operativa PDF

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Mit Apunte Investigación Operativa PDF

Cargado por

Copyright:

Formatos disponibles

MOVIMIENTO DE INCLUSIÓN TOTAL

Apunte de Investigación Operativa

La IO es una es una ciencia de la administración basado en el uso de las matemáticas y las

Parcialmente Controladas Sistema Indeseables

Caracterización del Sistema

Estado del Sistema: Condiciones en la que se encuentra el sistema

Función Objetivo (FO):

PASOS GENERALES y TECNICAS en la CONSTRUCCION de MODELOS MATEMÁTICOS:

3- IDENTIFICAR la FUNCION OBJETIVO: Son los objetivos llevados a términos matemáticos.

4- IDENTIFICAR las RESTRICCIONES

Los modelos deben clasificarse:

INTRODUCCION a la PROGRAMACIÓN LINEAL

FO → C1x1 + C2x2 + … + Cixi + … + Cnxn

Donde las aij, bi y Cj son constantes y m < n

• Condición de No NEGATIVIDAD: En la mayoría de los casos las variables de decisión

Segundo: Identificar los datos del problema

Tercero: Formular la FO a optimizar

Cuarto: Especificar las restricciones estructurales de recurso y las rstricciones de signo

SOLUCION GRAFICA DE PROBLEMAS BIDIMENSIONALES DE PL

PROGRAMA LINEAL con SOLUCIONES MULTIPLES

REGLA 3: IGUALDAD EN UNA RESTRICCION

Una RESTRICCION se considera OBLIGATORIA si el lado izquierdo es = al derecho de la restricción al

TEOREMAS BASICOS DE LA PROGRAMACIÓN LINEAL

INTERPRETACION TECNICA-ECONOMICA de TODOS los ELEMENTOS de la TABLA OPTIMA del

CAMBIO DEL VALOR DE Z EN CADA ITERACION

PRIMER TABLA DEL METODO SIMPLEX para un PL de 2 var y 2 restricciones

Z n+1= Z n – ѳn (Zj – Cj)n

CASOS PARTICULARES QUE PUEDEN PRESENTARSE AL REALIZAR EL ALGORITMO SIMPLEX

PROPIEDADES DEL DUAL

TEOREMAS DEL DUAL

SIGNIFICADO ECONOMICO del DUAL (recortes de libros para expandir el tema)

En el ESQUEMA DIRECTO: Punto de vista desde los beneficios

DUALIDAD Y ANALISIS DE SENSIBILIDAD

En cada uno de estos casos se determina simplemente si al modificar el PL original, se mantiene la

ANALISIS DE OPTIMALIDAD para los COEFICIENTES que ESTAN en la SOLUCIÓN

INTERVALO DE VARIACION DEL LADO DERECHO DE UNA RESTRICCIÓN bK

Por lo tanto, bk podrá tomar cualquier

• Por lo tanto, para verificar esto haremos: ̅𝒓̅̅̅ ̅̅̅̅ −𝟏 ̅̅̅̅

EJEMPLO: (NUEVAMENTE TENER EN CUENTA, QUE EN EL EJEMPLO LOS VALORES DE Cj SE TOMAN

PROBLEMAS ESPECIALES DE PROGRAMACIÓN LINEAL: PROBLEMAS DE

FORMULACION GENERAL – PLANTEO MATEMATICO

Si el problema esta balanceado, es decir, se verifica:

Entonces las ecuaciones serian todas igualdades:

PASO 1 – DETERMINACION DE LA SOLUCIÓN DE INICIO:

METODOS PARA OBTENER LA SOLUCIÓN NO ARTIFICIAL DE INICIO:

1- Asignar el máximo posible a la celda seleccionada y ajustar las cantidades de oferta y

MÉTODO DEL COSTO MINIMO de la MATRIZ:

MINIMO DE LA FILA MINIMO DE LA COLUMNA

Z inicial = 505 Z inicial = 475

MÉTODO DE APROXIMACION DE VOGEL

5 - - 5 14-4 = 16-14 = 16-14 = 18-14 = D- En cualquier

DETERMINACION DE LA SOLUCIÓN OPTIMA a partir de la SOLUCIÓN DE INICIO obtenida:

MÉTODO FUNDAMENTAL o de los COSTOS NETOS – Determinación de variables de Entrada

Si incrementamos en una unidad la variable

Determinación de variables de Entrada

1 C11 C12 … C1n 1

2 C21 C22 … C2n 1

𝑃𝑢𝑒𝑠𝑡𝑜𝑠 𝑃𝑢𝑒𝑠𝑡𝑜𝑠 𝑃𝑢𝑒𝑠𝑡𝑜𝑠

Procederemos a realizar el paso 3 para poder obtener dicha solución