MIT - APUNTE INVESTIGACIÓN OPERATIVA

Vista previa del material en texto

MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
1 
Recopilación de Material Digital para el Final 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. 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
2 
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 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
3 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 
Sistema
Deseables
Indeseables
NeutralesNo Controladas
Parcialmente Controladas
Controladas
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. 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
4 
Recopilación de Material Digital para el Final de Investigación Operativa 
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. 
 
 
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 escalarque 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: 
NO 
Convex
o 
Convex
o 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
5 
Recopilación de Material Digital para el Final de Investigación Operativa 
Representación idealizada de un sistema de la vida Real 
CLASIFICACION DE LOS MODELOS: 
 
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) 
Analogicos/a 
Escala
Fisicos
Estaticos 
Dinámicos
Matematicos 
o Simbolicos
Estaticos
Numericos
Analiticos
Dinamicos
Numericos 
(Simulacion)
Analiticos
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
6 
Recopilación de Material Digital para el Final de Investigación Operativa 
• 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: 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
7 
Recopilación de Material Digital para el Final de Investigación Operativa 
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) 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
8 
Recopilaciónde Material Digital para el Final de Investigación Operativa 
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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
9 
Recopilación de Material Digital para el Final de Investigación Operativa 
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
𝐶2
𝑥1 +
𝑍
𝐶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
𝑥2
𝑥3
𝑥4
𝑥5
𝑥6]
 
 
 
 
 
≠ 0
≠ 0
= 0
≠ 0
≠ 0
≠ 0
 𝑥𝐶= 
[
 
 
 
 
 
𝑥1
𝑥2
𝑥3
𝑥4
𝑥5
𝑥6]
 
 
 
 
 
≠ 0
≠ 0
≠ 0
= 0
≠ 0
≠ 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. 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
10 
Recopilación de Material Digital para el Final de Investigación Operativa 
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
𝑥2
𝑥3
.
.
𝑥𝑛]
 
 
 
 
 
+ (1 − 𝛼) ×
[
 
 
 
 
 
𝑥1
𝑥2
𝑥3
.
.
𝑥𝑛]
 
 
 
 
 
=
[
 
 
 
 
 
𝑥1
𝑥2
𝑥3
.
.
𝑥𝑛]
 
 
 
 
 
 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. 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
11 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
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: 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
12 
Recopilación de Material Digital para el Final de Investigación Operativa 
- 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 losumo 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. 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
13 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
 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. 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
14 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
15 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
 
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 elfuncional 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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
16 
Recopilación de Material Digital para el Final de Investigación Operativa 
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: 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
17 
Recopilación de Material Digital para el Final de Investigación Operativa 
▪ 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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
18 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 restriccionesque 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’ = ∑ µk
𝑘
𝑖=1 . Es decir, la suma de todas las 
variables artificiales. 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
19 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
20 
Recopilación de Material Digital para el Final de Investigación Operativa 
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: 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
21 
Recopilación de Material Digital para el Final de Investigación Operativa 
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) 
 
 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
22 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
 
 
 
 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
23 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
En el ESQUEMA DIRECTO: Punto de vista desde los beneficios 
 
Z = [u.monetaria] ⏟ 
𝑏𝑒𝑛𝑒𝑓𝑖𝑐𝑖𝑜 𝑡𝑜𝑡𝑎𝑙
 = ∑ 𝐶𝑗
𝑛
𝑗=1 . [u.monetaria/u. Producida]⏟ 
𝑏𝑒𝑛𝑒𝑓𝑖𝑐𝑖𝑜 𝑑𝑒 𝑐𝑖𝑐𝑙𝑜 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑜
 
s.a. 
∑ 𝑎𝑖𝑗
𝑘
𝑗=1 . [u. recurso/u. Producida]. xi[u. Producida] ⏟ 
𝑟𝑒𝑞𝑢𝑒𝑟𝑖𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒𝑙 𝑟𝑒𝑐𝑢𝑟𝑠𝑜 𝑖
 ≤ bj [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ónde 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. 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
24 
Recopilación de Material Digital para el Final de Investigación Operativa 
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. 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
25 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
26 
Recopilación de Material Digital para el Final de Investigación Operativa 
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: 
 
 
→ Aquí vemos que para que el valor de Zj – Cj sea no positivo, 
Cj debería ser ≥ 22, es decir, debería ser ≥ al valor de Zj. 
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 losrecursos 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 
Cj 10 … 
… … X4 
… 
Zj 22 
Zj - Cj 12 … 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
27 
Recopilación de Material Digital para el Final de Investigación Operativa 
 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: 
𝑥𝑏̅̅ ̅=B
-1 �̅�, donde B-1 es la matriz inversa, formada por los valores aij de las variables de holgura y �̅� es 
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: 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
28 
Recopilación de Material Digital para el Final de Investigación Operativa 
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: 
-20/-1 = 20 
-10/1 = -10 
10+20 = 30 // 10-10 = 0 
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 
xi Bi X1 X2 X3 X4 X5 
x4 20 0 -1 5 1 -1 
x1 10 1 4 -1 0 1 
Zj 20 0 -1 1 0 1 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
29 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
30 
Recopilación de Material Digital para el Final de Investigación Operativa 
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ámetrosde 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 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
31 
Recopilación de Material Digital para el Final de Investigación Operativa 
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. 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
32 
Recopilación de Material Digital para el Final de Investigación Operativa 
DEFINICION DEL MODELO DE TRANSPORTE 
 Dado el siguiente grafo: 
 
 
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.: 
 
 
Si el problema esta balanceado, es decir, se verifica: 
1 
 
2 
 
m 
 
1 
 
2 
 
n 
 
. 
. 
: 
 
. 
. 
: 
 
a1 
a2 
a3 
b1 
b1 
bn 
 C11 : x11 
Cmn : xmn 
ai 
bj 
0 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
33 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
 
Entonces las ecuaciones serian todas igualdades: 
 
Esto se puede representar en una tabla simplex modificada para el modelo de transporte que es la 
siguiente: 
 
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠
𝐹𝑢𝑒𝑛𝑡𝑒𝑠
 D1 D2 … Dn Oferta 
F1 
C11 C21 
… 
C1n 
a1 x11 x21 x1n 
F2 
C21 C22 
… 
C2n 
a2 x21 x22 x2n 
… … … … … … 
Fm 
Cm1 Cm2 
… 
Cmn 
am xm1 xm2 xmn 
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.) 
 
ai 
bj 
0 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
34 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 seleccionaday 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 
F1 
10 2 20 11 15 10 
0 5 10 - - 
F2 
12 7 9 20 25 20 
5 0 - 5 15 5 
F3 
4 14 16 18 
10 0 - - - 10 
Demanda 5 0 15 5 
0 
15 0 15 10 
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 
Este método es el más general, existiendo también 
variantes de mínimo de la fila y mínimo de la 
columna, en el primero, nos centramos en despachar 
todo, es decir, ponemos énfasis en reducir los valores 
de la oferta, mientras que en el mínimo de la columna, 
intentamos satisfacer las demandas primero. 
En estos métodos, vamos fila por fila (o columna por 
columna) empezando desde arriba (o la izquierda), 
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠
𝐹𝑢𝑒𝑛𝑡𝑒𝑠
 D1 D2 D3 D4 Oferta 
F1 
10 2 20 11 
15 0 
- 15 - 0 
F2 
12 7 9 20 25 10 
0 - - 15 10 
F3 
4 14 16 18 
10 5 0 5 - - 5 
Demanda 5 0 15 0 15 0 
15 10 
0 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
35 
Recopilación de Material Digital para el Final de Investigación Operativa 
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 
F1 
10 2 20 11 
15 0 
- 15 - 0 
F2 
12 7 9 20 25 10 
0 - - 15 10 
F3 
4 14 16 18 
10 5 0 5 - - 5 
Demanda 5 0 15 0 15 0 15 10 
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. 
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠
𝐹𝑢𝑒𝑛𝑡𝑒𝑠
 D1 D2 D3 D4 Oferta 
F1 
10 2 20 11 
15 0 
- 15 - - 
F2 
12 7 9 20 25 20 
15 0 5 0 15 5 
F3 
4 14 16 18 
10 0 - - - 10 
Demanda 5 0 15 0 15 0 
15 10 
0 
𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑠
𝐹𝑢𝑒𝑛𝑡𝑒𝑠
 D1 D2 D3 D4 Oferta 
1º 
iteración 
2º 
iteración 
3º 
iteración 
4º 
iteración 
F1 
10 2 20 11 
15 0 
10-2 = 
8 
11-2 = 
9 
------- ------- 
- 15 - - 
F2 
12 7 9 20 25 10 
0 
9-7 = 2 9-7 = 2 9-7 = 2 20-7 = 
13 - 0 15 10 
4 14 16 18 10 5 0 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
36 
Recopilación de Material Digital para el Final de Investigación Operativa 
D- En cualquier 
otro caso, 
seguir con el 
paso 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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. 
F3 5 - - 5 
14-4 = 
10 
16-14 = 
2 
16-14 = 
2 
18-14 = 
4 
Demanda 5 0 15 0 15 0 15 5 
0 
 
1º y 2º 
iteración 
12-4 
= 8 
7-2 = 
5 
16-9 
= 7 
18-11 
= 7 
 
3º 
Iteración 
------- 14-7 
= 7 
16-9 
= 7 
20-18 
= 2 
 
4º 
iteración 
-------- 14-7 
= 7 
------- 20-18 
= 2 
 
MOVIMIENTO DE INCLUSIÓN TOTAL 
Apunte de Investigación Operativa 
37 
Recopilación de Material Digital para el Final de Investigación Operativa 
 
Por ejemplo, para x31 nuestro ciclo será: 
 
 
 
 
 
 
 
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