RESUMEN INVESTIGACION OPERATIVA

UNIDAD 1: Metodología de la Investigación Operativa

Investigación Operativa: “La aplicación de procedimientos, técnicas y herramientas científicas en el

análisis de problemas operativos que se presentan en las organizaciones, con el objetivo de desarrollar y
ayudar a evaluar soluciones"
Metodología que estudia los problemas de decisión de naturaleza compleja a través del método
científico, crea modelos matemáticos de problemas reales multidisciplinarios y utiliza las matemáticas, la
estadística y las computadoras como herramientas para encontrar soluciones racionales y servir de apoyo
a las decisiones de las organizaciones y lograr una visión estructurada y cuantitativa de la realidad.
Se desarrolló a partir de grandes éxitos obtenidos mediante su aplicación en la toma de decisiones
en problemas de organización de defensa táctica y estrategia militar durante la segunda guerra mundial en
Gran Bretaña (1939-1945). Luego fue trasladado y aplicado al sector industrial donde la complejidad de los
procesos iba en aumento.

UNIDAD 2: Programación Lineal

Modelo Matemático
Formular el problema de una manera conveniente para su análisis, en Investigación de
Operaciones, a través de un modelo matemático. Los modelos son representaciones idealizadas de una
parte de la vida real. En general extraen la esencia del problema, reflejan las interrelaciones y facilitan el
análisis.
Al proceso de representar un problema mediante un modelo matemático, se denomina
modelización. Para modelizar un problema debemos identificar el objetivo, definir las variables y enunciar
las restricciones en forma verbal.
Los modelos matemáticos consisten en fórmulas matemáticas, igualdades, y/o desigualdades. En
general tendremos una función objetivo, que dará una medida de la efectividad, representado en una
ecuación matemática y algunas limitaciones, que representarán las restricciones que podrán ser
igualdades o desigualdades. Las constantes que sea necesario utilizar, tanto en la función.

Características: (nos dan la idea de que podría modelarse mediante programación matemática)
● Es un problema de decisión
● Existe un desempeño que quiere optimizarse
● Las decisiones posibles pueden expresarse como variables
● Existen condiciones que acotan el espacio de soluciones

Es fundamental que en cada problema se identifique cual es el objetivo del problema,

(maximización o minimización). En la modelización, normalmente si aparecen ingresos y costos, la función
objetivo corresponde a la utilidad.
Utilidad = ingresos – costos.

Formalmente, un Modelo de Programación Matemática tiene la siguiente estructura:

Donde m representa el número total de ecuaciones y/o inecuaciones de restricción existentes

en el modelo.
 Podemos decir que estamos frente a un problema de Programación Matemática si el mismo trata
de optimizar (maximizar o minimizar) una función donde las variables pueden asumir únicamente
los valores que verifican un conjunto de restricciones expresadas como ecuaciones y/o
inecuaciones.
De acuerdo a las características de la función objetivo y las restricciones, un modelo de
programación matemática puede ser de:

❖ Programación Lineal: Cuando la función objetivo y las restricciones son lineales.

❖ Programación Lineal Entera: Si algunas o todas las variables de modelo deben ser enteras.
❖ Programación No Lineal: Cuando la función objetivo y/o alguna o todas las restricciones son no
lineales.
❖ Programación Multiobjetivo: Cuando existe más de una función objetivo.

Programación Lineal (PL): Es un modelo matemático que representa características

observadas comunes, en la que tanto las utilidades como el uso de los insumos son proporcionales
a la cantidad que se fabrique de los productos. No es posible fabricar cantidades negativas de los
productos. Entonces, la programación lineal es un modelo de programación matemática en el cual:

● Se intenta maximizar o minimizar una función lineal llamada objetivo. (variables elevadas a
la 1)
● Los valores de las variables de decisión deben satisfacer un conjunto de restricciones.
Dichas restricciones deben poder expresarse como ecuaciones o inecuaciones lineales.
Esto acota el espacio de soluciones.
➔ ≥ o ≤ inecuaciones
➔ = ecuaciones
● Restricción de signo de no negatividad, las variables deben ser mayor o igual a 0.

Resolver un problema lineal significa encontrar un conjunto de valores para las variables de
decisión que, cumpliendo con todas las restricciones, incluidas las de no negatividad, optimicen a la
función objetivo.

Propiedades o supuestos de la programación lineal:

Único objetivo (función objetivo): un espacio de soluciones acotado por un conjunto de restricciones y
restricciones de no negatividad de las variables.
Aditividad: la solución de la función objetivo se obtiene por la sumatoria de los aportes de cada variables.
Proporcionalidad: El valor del aporte de cada variable es proporcional al valor que adopta dicha variable
ya que cada una de ellas es multiplicada por un coeficiente.
Divisibilidad: las variables pueden ser valores fraccionarios o valores decimales.
Certidumbre: los parámetros son valores conocidos y ciertos. Los parámetros son los coeficientes que
multiplican las variables y los resultados de las inecuaciones de restricciones, son dados por el problema.

Etapas de Construcción del Modelo Matemático:

● Formulación del Problema
● Construir un modelo matemático que represente al sistema
● Derivar una solución a partir del modelo
● Probar el modelo y la solución obtenida
● Establecimiento de controles sobre la solución
● Llevar la solución a la práctica
¿Por qué construir un modelo del problema de programación lineal?
● Nos ayuda a analizar, entender y explicar el problema
● Formaliza las relaciones entre las variables, las restricciones y el objetivo
● Existen múltiples métodos para encontrar el valor de las variables que resuelven el problema de
optimización (método gráfico, método simplex, otros)
El modelo puede ser expresado de diferentes maneras:

1) Forma Explícita

2) Forma Matricial

- Estándar: Tiene todas las restricciones de igualdades (independientemente de que la

Función Objetivo sea de Máximo o mínimo), es decir:
 - Canónica: En caso de máximo, todas las restricciones son de tipo <=. En caso de
mínimo, todas las restricciones son de >=.

- Mixta: Cuando las restricciones son de cualquier tipo, cualquiera sea el sentido de
optimalidad de la Función Objetivo, decimos que el problema lineal es mixto.

3) Forma Vectorial

Problema EJEMPLO:

Un amigo es consultor independiente. Actualmente cuenta únicamente con dos potenciales

clientes, debiendo definir aún cuántas horas semanales le dedicara a cada uno. El cliente 1 le genera
una utilidad de $40 por hora de consultoría, mientras que por cada hora del cliente 2 le genera $50.

Considera trabajar 8 horas diarias, 5 días a la semana. Puede distribuir las horas como quiera,
aunque sabe que el cliente 2 solo está dispuesto a contratar hasta 24 horas por semana máximo.

Para poder realizar el trabajo, necesita utilizar un insumo del que dispone solamente de 960
unidades semanales. Por cada hora de consultoría trabajada para el cliente 1 o el 2, debe consumir 20
o 30 unidades de insumo respectivamente.

Considerando que nuestro amigo desea obtener la máxima utilidad semanal posible bajo las
condiciones descritas: ¿Qué recomendación podríamos darle para lograrlo?
MÉTODO GRÁFICO:
Nos permite encontrar la solución óptima en un problema de programación lineal de DOS variables,
siempre que esta exista.
Se puede resumir en los siguientes pasos:
1. Identificar, de forma gráfica, el espacio de soluciones
2. Identificar, una recta que corresponda a la función objetivo para algún valor de z dado
3. Desplazar dicha función sobre el gráfico en el sentido de la optimalidad hasta encontrar el punto
extremo óptimo (o los puntos en el caso de problemas con múltiples soluciones óptimas)
4. Identificar la solución óptima encontrada

Espacio de solución: conjunto de soluciones que cumplen con el sistema de inecuaciones.

● restricciones funcionales
● restricciones de no negatividad
Para encontrarlo, las restricciones deben ser representadas en mismo gráfico. Los puntos en
común, son los que pertenecen al conjunto definido por ambas inecuaciones. Es decir, cumplen con todas
las inecuaciones a la vez. Dichas soluciones son entonces factibles.

Para identificar el espacio de soluciones, se grafican las restricciones.

1. Identificando el signo de la inecuación, decidimos de qué lado permanece el espacio de
soluciones.
Variables ≥ - por arriba de la recta
variables ≤ - por debajo de la recta
(Recordar que si las variables tienen signo negativo esto puede cambiar, por lo tanto, comprobar dándole
valores de (0,0) a las variables y verificar)

2. Se grafica la función objetivo

Teniendo en cuenta la función objetivo:

Z= 40 x1 + 50 x2

Podemos deducir que, al modificar el valor de Z lo que va cambiando no es la inclinación de

la recta de la función objetivo, sino su Ordenada al origen.
Le damos a Z un valor arbitrario y una de las variables va a tomar valor de 0 para buscar
el valor de la otra variable.

Z= 1000 1000 = 40 x1+50 x2

X1=0 x2= 1000/50= 20
X2=0 x1= 1000/40= 25

Entonces se grafica la recta x2=20 y x1=20, la cual da un z=1000.

3. Desplazar dicha función sobre el gráfico en el sentido de la optimalidad

Al incrementar el valor de Z, la recta (curva de isoutilidad) se incrementará paralelamente

hasta en algún punto encontrar el punto óptimo.

4. Identificar la solución óptima encontrada

¿Cómo saber cuál es el valor de z en el punto óptimo? Para encontrar los valores exactos de
las variables x1 y x2 tengo que identificar el punto y las rectas de restricción que intersectan ahí. En
este caso la intersección es en el punto D, donde intersectan las restricciones, pero como
hablamos de rectas y no de regiones, las rectas de las restricciones se expresan como
ecuaciones.

Las restricciones entonces son:

x1 + x2 = 40
20 x1 +30 x2 = 960

Si hacemos despeje de una variable en función de la otra y luego sustitución para obtener el valor
de cada una.
x1= 40 – x2
20 (40- x2) + 30 x2 = 960
800 – 20 x2+ 30 x2 = 960
960 – 800 = 10 x2
160/10 = x2
16 = x2
 x1= 40- 16
x1= 24

Entonces el punto D es (24, 16) y reemplazando esos valores en la función objetivo encontramos
el valor de Z*=1760. Esto nos indica que “En la semana, deberá dedicar 24 horas al cliente 1 y 16 horas al
cliente 2. Con esta política, obtendrá una utilidad de $1760 por semana”

Clasificación y análisis de las soluciones:

Para un problema de PL, en forma estándar, con m ecuaciones de restricción y n variables incluidas
las de holgura o excedente, enunciamos los siguientes conceptos respecto al conjunto de soluciones del
problema:

Solución (se deben cumplir al menos las restricciones y las variables principales deben ser ≥0)

Solución Factible o Posible: se deben cumplir las restricciones y las variables principales y las de
holgura debes ser ≥0 (restricción de no negatividad)

Solución Factible Básica: se deben cumplir al menos las restricciones y las variables principales y de
holgura debes ser ≥0 y considerando que hay n variables y m restricciones deben existir al menos
(n-m) variables nulas por ejemplo si son 5 variables y 3 restricciones de igual deben ser 2 o más
variables nulas para que sea básica y todas las variables mayores o iguales a cero para que sea
posible

▪ Solución Posible Básica No Degenerada: considerando una Solución Posible Básica y

considerando que hay n variables y m restricciones, deben existir exactamente (n-m) variables
nulas por ejemplo si son 5 variables y 3 restricciones deben ser exactamente 2 variables nulas
para que sea básica y todas las variables mayores o iguales a cero para que sea posible.

▪ Solución Posible Básica Degenerada: considerando una Solución Posible Básica y

considerando que hay n variables y m restricciones deben existir más de (n-m) variables nulas
por ejemplo si son 5 variables y 3 restricciones deben ser más de 2 variables nulas para que sea
básica degenerada además de que todas las demás variables sean mayores o iguales a cero
para que sea solución posible.
 Considerando lo analizado hasta el momento, podemos hacer las siguientes observaciones:
1. Para cumplir con las restricciones de no negatividad de las variables, gráficamente se
trabaja siempre en el 1º cuadrante.
2. El poliedro de soluciones es un conjunto convexo.
3. Los puntos que resulta necesario considerar para buscar el óptimo son los que se
encuentran sobre la frontera de la región factible.
4. En particular podemos observar que, si el PL tiene solución, esta se encontrará en, al
menos, uno de los vértices.
5. Se puede obtener la solución en cada vértice resolviendo en forma simultánea las
ecuaciones lineales que lo determinan.
6. Las soluciones factibles en los vértices son soluciones factibles básicas.
7. Todos los puntos del poliedro de soluciones verifican las restricciones, es decir que el
problema tiene infinitas soluciones factibles.
8. En todo punto situado sobre una recta no hay sobrante de ese insumo.
9. En las ecuaciones determinantes del óptimo (restricciones limitantes), no hay sobrantes de
insumos, por lo tanto, las variables de holgura son nulas.
10. En las ecuaciones no determinantes del óptimo (restricciones no limitantes) siempre hay
sobrantes de insumos, o sea, las variables de holgura son positivas.
11. Si el funcional verifica su máximo valor en un único vértice del poliedro, significa que el
problema tiene una única solución óptima.
12. Si z fuera paralela a una restricción limitante, el problema tendría infinitas soluciones
óptimas.
13. Si el óptimo se verifica en un vértice donde se cruzan tres o más rectas de restricción, la
solución óptima es degenerada.

Variable Básica (considerando una Solución Posible Básica las variables básicas serán las que tienen
valor positivo)

Variable No Básica (considerando una Solución Posible Básica las variables no básicas serán las que
tienen valor nulo)

MÉTODO SIMPLEX:
El método Simplex permite encontrar la solución óptima de cualquier problema de Programación
Lineal sin importar el número de variables o restricciones. También admite fracciones o números
decimales en el valor de las variables.

Teorema fundamental de Programación Lineal:

“Si un problema de programación lineal tiene solución óptima, existirá siempre por lo menos una
solución factible básica (vértice) que también sea óptima”.
Este teorema demuestra que cuando una solución es factible básica la solución está en un punto
extremo del polígono de soluciones.
Entonces, para obtener los valores de cada punto extremo se van reemplazando los valores
posibles de x1 y x2 en cada una de las restricciones, obteniendo así, los valores de las variables de
holgura. Es decir, es necesario poder identificar cada vértice.
Características:
▪ Dos soluciones de punto extremo (SFB) son adyacentes en la región factible si ambas son
extremos de una misma recta. (Ej: E y F)
 ▪ Dos soluciones de punto extremo (SFB) son adyacentes si al compararlas, una de las
variables positivas de la primera se anula en la segunda, mientras que una variable nula se
hace positiva en la segunda y viceversa. (Ej: A y B)
▪ Dos soluciones factibles básicas son adyacentes, es decir, puntos extremos de una misma
arista del polígono de soluciones, si todas sus variables nulas (variables no básicas) coinciden
EXCEPTO UNA (una de cada solución, no una entre las dos). Por descarte ocurre lo mismo
con las variables básicas o no nulas de dichas soluciones. (Ej: A y B)

Esto sirve para encontrar rápidamente y en pocas iteraciones la solución óptima (que siempre es
uno de los puntos extremos del polígono), sin tener que pasar por los infinitos puntos que se encuentran
dentro del polígono.

Algoritmo del método simplex

Primero plantea una solución factible básica, y luego explora de manera sistemática los puntos
adyacentes del poliedro de soluciones hasta encontrar la solución óptima, en cada iteración encuentra una
posible solución más cercana a la óptima.

Si analizamos el poliedro de soluciones factibles, podemos observar que, cada vértice se forma por
la intersección de las rectas representativas de las restricciones. A su vez, cada punto extremo o vértice
corresponde a una posible solución básica del problema.
Además, como las restricciones son lineales y la función objetivo también, el óptimo se dará en al
menos un vértice del poliedro. Decimos en al menos un vértice porque la recta de isoutilidad (o
isocosto) puede coincidir con dos vértices del poliedro de soluciones y, en ese caso, tendríamos dos
vértices óptimos y los infinitos puntos del segmento de recta que los une.
 También, analizando las soluciones del gráfico, observamos que los vértices corresponden a
soluciones factibles básicas, es decir que en ellas tenemos como máximo m valores positivos y los
restantes nulos, por lo que podemos concluir que la solución óptima (si existe) será una solución factible
básica.
Entonces, el método simplex, basándose en estas conclusiones generales, analiza
sistemáticamente los puntos extremos de la región factible hasta identificar el punto óptimo,
asegurándose en cada paso que el vértice analizado no es peor que el anterior, esto es, que le dé a la
función objetivo un valor mejor o al menos igual que el anterior.
El método consta de dos fases: en la primera identifica una solución factible básica (vértice) y
la segunda corresponde al mejoramiento de esta hasta llegar al óptimo.
Supongamos que se identifica como primer SFB de partida al vértice 0, lo primero que simplex
analiza es si es solución óptima o no, y lo hace a través de un criterio de optimidad, y evidentemente que
este vértice no es óptimo.
Si el vértice no es óptimo, entonces debe decidir hacia dónde se mueve. Siempre pasa de un
vértice a otro adyacente (el otro vértice del mismo lado), en nuestro caso será al A o al B. Esto se debe a
que solo cambia de una variable por vez, es decir que una variable que en ese vértice es igual a cero
asumirá un valor positivo y, por lo tanto, una de las que son positivas asumirá el valor cero. Para decidir
hasta qué vértice conviene desplazarse, analiza la tasa de cambio de z, es decir, en cuánto se incrementa
z si se mueve una unidad hacia el vértice A y cuál será el incremento si se mueve hacia B.

Propiedades del método simplex

● Si existe exactamente una solución óptima, entonces es un punto extremo.

● Si existen múltiples o infinitas soluciones óptimas, entonces al menos dos de ellas serán puntos
extremos adyacentes (de la misma arista).

● Si existe una región factible, entonces existe solo un número finito de puntos extremos (soluciones
factibles básicas) sin importar el número de restricciones.

● Si una solución factible básica es igual o mejor que todas sus adyacentes, entonces es igual o
mejor que todas las demás soluciones, es decir, es óptima.

● Hay un teorema que dice que la región factible siempre va a ser de forma convexa.
Formas de presentación

Forma Explícita: consideraremos a Xi como las variables de decisión, Z es el valor de la función objetivo,
Ci coeficientes de cada variable en la función objetivo, aij coeficientes técnicos o tasas de sustitución, bj
disponibilidades del recurso j, y no olvidar la restricción de no negatividad)

➔ Si el problema es de maximización y las restricciones es ≤ es CANÓNICA.

➔ Si el problema es de minimización y las restricciones es ≥ es CANÓNICA.
➔ Si el problema es de maximización o minimización y las restricciones es = es ESTÁNDAR
➔ Si el problema es de maximización o minimización y las restricciones son ≤, ≥ o = es MIXTA.

Modelo equivalente y variables de holgura

Analizando las restricciones del problema, observamos que se admite la posibilidad de utilizar una
menor cantidad de recursos que los disponibles. Esta situación puede representarse matemáticamente a
través de variables que representan los insumos no utilizados, conocidas con el nombre de “variables de
holgura” o “excedente”.

Aquellos modelos que utilizan las variables de holgura para lograr la igualdad generan un modelo
equivalente del original, ya que se sustituyen las inecuaciones por ecuaciones agregando dichas
variables de holgura formando una matriz.

Entonces, las variables de holgura representan la diferencia entre el resultado de la ecuación y la

suma de las variables de decisión en cada restricción, es decir, el sobrante o valor necesario para lograr
la igualdad. Cada variable de holgura representa conceptos diferentes. Económicamente, esto
representaría excedente de horas en el caso de S3, excedente de horas para el cliente 2 en S4 o insumo
que no consumimos durante la semana en S5.
 El conjunto de soluciones entre ambos modelos equivalentes es el mismo, la única diferencia es
que uno tiene ecuaciones y el otro inecuaciones.
Recordar que las variables de holgura (s3, s4 y s5) se agregan en la función objetivo como
valores nulos, ya que no representan pérdida o ganancia, es decir, no aportan nada a las utilidades.

Signos de las variables de holgura:

● Para el caso de ≤ cuando armamos el modelo equivalente es = y la variable de holgura se
SUMA. Aquí la variable de holgura representa un excedente.

● Para el caso de ≥ cuando armamos el modelo equivalente es = y la variable de holgura se

RESTA. Aquí la variable de holgura representa una cantidad sobre el mínimo.

Pasos del método simplex (para forma canónica de máxima ≤)

1. Partir del modelo de programación lineal en su forma canónica

2. Pasar el modelo original al equivalente (forma estándar) agregando variables de holgura a las
restricciones y función original. En caso de que en el vector del lado derecho exista algún valor
negativo, se deberá multiplicar ambos miembros de la restricción por -1.
3. Analizar la matriz de coeficientes del sistema de ecuaciones de restricción e identificar la matriz
identidad. Las variables cuyo coeficientes corresponden con la matriz identidad, serán las variables
consideradas básicas en la solución inicial y sus valores en la solución serán los términos
independientes de las restricciones. Entonces, los vectores unitarios son los que entran en la base,
como están ubicados en la solución trivial donde x1 = 0 y x2 = 0 es claro que los que entran en la base
al comienzo son las variables de holgura. Se anulan [n – m] variables (las principales), sabiendo que
las que NO se anularon son las variables de la base (básicas).
Ejemplo la solución es Z=0 para (X1, X2, S3 ,S4, S5) = (0, 0, 40, 24, 960).
Si no se identifica la matriz identidad no es posible comenzar con simplex. Se puede llegar a la
matriz identidad mediante operaciones elementales por filas.

Recordar que el orden de los vectores unitarios nos indica cómo entran en la base, tienen un
orden específico. Cómo S3 tiene el 1 en la primera fila, su variable de holgura entra a la base en la
primera fila, y así con el resto de las variables.
4. Completar la tabla Simplex y obtener la primera solución factible básica.

Analizar las diferencias Cj - Zj. Estos valores miden el incremento de la función objetivo ante
un aumento unitario en el valor de cada una de las variables no básicas. Por lo tanto:
 Corroborar si la solución es la óptima:
● Para maximización: Todos los valores de [Cj – Zj] deben ser negativos o nulos.
● Para minimización: Todos los valores de [Cj – Zj] deben ser positivos o nulos.

5. Si la solución no es óptima, se debe buscar una solución factible básica adyacente mejor. En
cada nueva solución una variable entra en la base y otra sale de la misma. Se debe pasar a otra SFB
haciendo un cambio de variables en la base, es decir que alguna variable no básica (nula) pasa a ser
básica positiva y alguna variable básica pasa a ser no básica (nula).

Recordar que las variables que no están en la base son nulas y siempre van a ser al menos
dos en este caso porque el algoritmo va a ir buscando puntos extremos (SFB) y cumplen con ≥ (n –
m). Si alguna variable de la base tiene valor 0, es decir, además de las que no pertenecen a la base,
hay otra nula en la base, entonces es una SFB degenerada ya que son más de (n – m). Pero si se
cumple con = (n – m) es SFB no degenerada.

Determinación de la variable que entra y la variable que sale de la base:

⮚ Variable que entra: (toma valor positivo): Debe ser aquella que tenga el mayor incremento
positivo en el caso de maximización (o mayor incremento negativo en el caso de minimización),
ya que ésta es la variable que aumenta (disminuye) más rápidamente el valor de la función
objetivo.
● Para maximización: Entra la variable [Cj – Zj] más grande (más positivo).
● Para minimización: Entra la variable [Cj – Zj] más pequeña (más negativo).

⮚ Variable que sale: (toma valor nulo): Se calcula θ (tita) y se elige la más pequeña que sea
mayor a cero, no importa si es Max o Min, es decir, no importa el sentido de la optimidad. Este
cociente representa el máximo que puede tomar la variable entrante, antes que viole las
condiciones de no negatividad.
Si todos los λ (landas) son ≤ 0 la solución es no acotada. Esto significa que la función
objetivo podría incrementar (disminuir) infinitamente su valor.

Recordar que la variable que entra lo hace exactamente en la misma posición de la variable
que sale. (Se realiza un “cambio de base”)
6. Se construye una nueva tabla simplex en donde se coloca la nueva variable en la base junto con
su coeficiente. El número que se encuentra en la intersección entre la columna de la variable que
entra y la fila de la variable que sale se llama “elemento pivot” en el cual se deberán realizar
operaciones elementales de filas de forma que en la columna de la variable se forme un vector
unitario.

Para lograr esto, se emplean las siguientes operaciones elementales en filas:

➔ multiplicar una fila por un número distinto de cero.
➔ sumarle a una fila otra multiplicada por un número.

Se multiplica al elemento pivote (1) por un escalar que convierte al vector en unitario, es decir,
para hacer las celdas que quedan ceros. Entonces se multiplica la fila del pivote por un escalar y
luego se lo suma a la fila de arriba o de abajo.

7. Se termina de completar la tabla calculando Zj y [Cj – Zj] para determinar si la solución es óptima y si
no, se vuelve a repetir todas las veces que sea necesario. Cuando encuentra las variables básicas
que dan el valor óptimo finaliza el algoritmo. Recordar, que aquellas variables que no estén
presentes en la base tendrán valor nulo (0).

Corroborar si la solución es la óptima:

● Para maximización: Todos los valores de [Cj – Zj] deben ser negativos o nulos.
● Para minimización: Todos los valores de [Cj – Zj] deben ser positivos o nulos.

TÉCNICA DE LA BASE ARTIFICIAL (Para restricciones de ≥ o =)

⮚ Cuando las restricciones son de ≥ sucede que las variables de holgura quedan negativas y no
cumplen con la restricción de no negatividad. Es así que no se forma el vector unitario, por ende,
no pueden ir a la base.
⮚ Cuando las restricciones son de = sucede que no hay variables de holgura.
 Para estos casos se utiliza un ARTIFICIO MATEMÁTICO donde se agregan variables artificiales
que generan un nuevo espacio de soluciones, que incluyen al del problema original (si este existe)
pero estos no son equivalentes (El nuevo espacio no tiene interpretación económica en el problema).

La variable artificial me permite armar el vector unitario y encontrar una SFB inicial que si bien no
es real, con el simplex luego entró al espacio de soluciones real para encontrar el punto óptimo. Se
agregan tantas variables artificiales como vectores unitarios nos falten en la matriz para obtener la matriz
identidad.

Estas variables NO son variables del problema original. Por ello, decimos que una solución del
mismo se obtiene una vez que se hayan eliminado de la base todas las variables artificiales.

Para eliminarlas de la base rápidamente, se deben agregar en la función objetivo precedidas

de un coeficiente que deberá ser:
● Maximización: Muy grandes en valor absoluto y negativo (-M).
● Minimización: Muy grande en valor absoluto y positivo (+M).

Como la variable artificial es un valor que nos resta mucho en la función objetivo siempre va a ser la
primera en salir. Por cada unidad de la variable X2 que entra, la Z incrementa en 50+M, en cambio, por
cada unidad de A1 que sale, dejo de perder –M.

Se itera hasta que pueda alcanzarse una de las soluciones posibles básicas del problema original
hasta cumplir la condición de optimidad.
 Si se verifica la condición de optimidad y en la base aún queda alguna variable artificial, puede
suceder alguna de las siguientes dos cosas:
➢ Si la variable artificial quedó en la base con un valor positivo, se trata de una solución no
factible, porque no existe una solución del problema original que cumpla con todas las
restricciones al mismo tiempo.
➢ Si la variable artificial quedó en la base, pero con un valor nulo (VLD), entonces la solución
encontrada sí es solución del problema original y será solución factible básica degenerada, ya
que tiene más de n-m variables nulas.

Interpretación económica de la tabla simplex

● La solución es X = (50, 0, 0, 1200, 0, 40, 0) y Z = 5500

X1 = 50 / X2 = 0 / X3 = 0 / S4 = 1200 / S5 = 0 / S6 = 40 / A = 0 /

● La cantidad óptima a producir es 50 unidades de X1, y 0 de X2 y X3.

● El sobrante de MP es S4 = 1200, como disponíamos de 3200, es una variable NO limitante.

● El sobrante de Hs MO es S5 = 0, como gastamos las 5000 y no queda nada, es la variable limitante, si

quisiéramos seguir produciendo tendríamos que contratar más empleados o pagar horas extra.

● S6 = 40 es la variable de excedente (no limitante), es decir, nos pasamos por 40 unidades el mínimo de
10.

Cuando una variable de holgura es cero me limita la producción, entonces es limitante. Cuando una
variable de holgura es positiva es no limitante.
 Análisis de la tasa de sustitución: Cuánto pierdo de la variable básica por cada unidad que ingresa
de la variable no básica.
Hacemos el análisis en el caso si quisiéramos ingresar una unidad del producto X2, como estoy
tengo una variable limitante que me limita mi capacidad de producción (S5 Horas de mano de obra)
tengo que dejar de fabricar algo del producto X1, para así poder liberar horas de cocción.

Si quisiéramos añadir más unidades de X2 por ejemplo una más, nos fijamos en la columna de X2 para ver
lo siguiente:

● Ganaríamos 40 pesos por cada unidad de X2 agregada (es el coeficiente)

● Perderíamos 55 pesos por cada unidad de X2 agregada (es zj) 110 * 0,5 = $55

● Por cada unidad de X2 que fabricamos en lugar de X1 perderíamos -15 pesos (cj – zj) $55 – $40 = $15

● Los 60 indican cuántas unidades pierdo de la variable básica (S4) por una unidad que ingresa de la
variable no básica (X2). (la materia prima) S4 (1200- 60=1140)

● Ganaríamos 0,5 unidades de la variable básica a S6 por cada unidad que ingresa de la variable no básica
(X2) (el excedente del mínimo) S6 (40 - (-0,5)= 40,5)

● Por cada unidad de producto x2 pierdo 0,5 unidades, entonces voy a poder fabricar 50-0,5=49,5
unidades.

X1 (50- 0,5= 49.5)

X = (49.5, 1, 0, 1140, 0, 40.5) y Z = 5485

Es por lo que el método simplex termina cuando aparecen utilidades negativas en la última fila. El neto
del intercambio te dice que meter esa variable va a ser que disminuya z.

¿Cuántas unidades puedo ingresar de cada producto?

Para saber cuántas unidades de X2 puedo agregar hay que mirar el menor valor de tita θ para ver qué
variable es la limitante. En el caso de variables negativas, no se las considera en el cálculo de tita porque
no van a disminuir la variable básica, por lo que no afecta.
Casos particulares:
● Problema con soluciones degeneradas

Observemos que existe un empate entre S1 y S2 al decidir la variable que sale de la

base. En principio, se puede seleccionar como variable de salida a cualquiera de las dos. Si
elegimos sacar S2 (tabla 19), se observa que S1 se hace nula en la columna VLD. En este
caso, la solución encontrada es una solución degenerada.

La degeneración se observa cuando el vector solución verifica menos de m valores

positivos o más de (n – m) valores nulos. Recordemos que también se presenta un caso de
problema degenerado cuando en la solución óptima quedan variables artificiales nulas.

● Problema con múltiples soluciones óptimas

La recta z es paralela a una restricción limitante. Esto implica que existirán dos vértices que
son óptimos, el A y el B, y además todos los puntos que forman el segmento de recta que
los une.
 Observemos que la diferencia c2 – z2 es igual a cero y la variable x2 no es básica.
Esto significa que si introducimos x2 a la base y eliminamos la que corresponda, en este
caso S1, obtendremos otra solución que le dará a z el mismo valor. Esto es así, porque
según el Teorema del método simplex, el valor de una nueva solución se obtiene
calculando:

Entonces podemos concluir que el problema posee una infinidad de soluciones

óptimas que derivan a un mismo resultado.

● Problema no acotado

Es imposible seleccionar la variable que sale, ya que todos los elementos de la

columna de S1 son negativos y ceros. En este caso, debe detenerse el proceso y revisar el
planteo, puesto que esto surge de un error en la modelización del problema.
Podemos decir que un PL es no acotado cuando el conjunto de soluciones factibles
es un conjunto convexo abierto y el sentido de optimización del funcional se dirige hacia la
zona no acotada del mismo.
● Problema incompatible

En la tabla se observa que el criterio de optimidad indica que es la solución óptima,

sin embargo, como ha quedado en la base una variable artificial positiva, concluimos que el
problema original es incompatible o no factible.
 DUALIDAD Y SENSIBILIDAD

DUALIDAD
Para cada problema de programación lineal existe siempre, asociado al mismo, otro problema lineal.
A este nuevo programa se lo puede emplear para obtener la solución del problema original, de manera que
las variables proporcionen información útil acerca de la solución óptima del problema lineal original.
Entonces, si un problema posee muchas variables y pocas restricciones, es posible encontrar un problema
dual que tenga pocas variables y muchas restricciones, que es más simple de resolver y que provee los
mismos resultados. Es así como convendremos en llamar “primal” al programa original y “dual” al problema
lineal asociado.
A partir del modelo primal se puede crear un modelo dual asociado para definir qué valor aporta
cada recurso (restricción) en el modelo principal.

● Si el primal es de maximización el dual será de minimización, y viceversa.

● El dual tendrá tantas variables como restricciones tenga el primal.
● Cada restricción del primal estará asociada a una variable del dual.
● Los VLD de las restricciones del primal pasan a ser los coeficientes de las variables del dual.
● Cada variable del primal está asociada a una restricción del dual.
● El dual tendrá tantas restricciones como variables tenga el primal.
● Los coeficientes de las variables del primal pasarán a ser los VLD de las restricciones del
dual.
● Como cada variable del primal está asociada a una restricción del dual y cada restricción del
primal está asociada a una variable del dual, por cada columna de las restricciones del primal se
construirá una restricción del dual utilizando los coeficientes, y las variables serán las asociadas a
cada fila/restricción. (cada variable de holgura del primal será una variable de la función
objetivo del dual)

Observemos que cada restricción del primal se relaciona con una variable principal del dual, y
viceversa. Es decir, la primera restricción primal se corresponde con la primera variable dual; la segunda
restricción primal, con la segunda variable dual; y así sucesivamente. Razón por la cual decimos que, si el
programa primal tiene n variables principales y m restricciones, el dual tendrá m variables principales
y n restricciones.
También cabe mencionar que si una variable de primal es básica, la variable de dual asociada a ella
será una variable no básica, y por la misma razón si una variable de primal es no básica, la correspondiente
variable de dual será una variable básica.
Existen distintas formas de dualidad: canónica o simétrica, dualidad estándar y dualidad mixta; el
nombre de cada una de ellas se origina de acuerdo con la forma en que se presenta el problema original.
 Forma canónica:

Forma estándar:

Forma Mixta:
A los fines de plantear el modelo dual de un programa lineal presentado en forma mixta, debemos
tener en cuenta la relación que existe entre las restricciones de uno de los programas y las variables del
otro. Tener en cuenta que “el dual del dual es el primal”, por lo que las definiciones dadas se pueden aplicar
al revés.
Relación entre variables y restricciones:
● Las restricciones de la forma “menor o igual que” en el problema de máximo dan origen a variables
≥ 0 en el problema de mínimo.
● Las restricciones “igual que” dan origen a variables “no restringidas” en el otro problema.
● Las restricciones “mayor o igual que” en el problema de máximo originan variables ≤ 0 en el
programa mínimo.
Relación entre los valores objetivos:
Se puede demostrar que el valor de la función objetivo, para cualquier solución factible del problema
de máximo, es siempre menor o igual que el valor de la función objetivo para cualquier solución factible del
problema de mínimo, es decir: Z ≤ G. En particular, la igualdad se verifica cuando ambos problemas están
en el óptimo Z = G.
Hay que recordar que si establecemos las relaciones entre las soluciones óptimas de los dos
problemas, veremos que el valor que aparece en las respectivas tablas optimas es el mismo pero cambiado
de signo, ello se debe a que en un problema estamos maximizando y en el otro estamos minimizando, y
para un problema de minimización realizamos la transformación de mínimo a máximo, cambiando el signo
de la función, por ello a la hora de comparar los valores de ambos problemas no se puede hacer directamente
desde una tabla a la otra.

Teorema fundamental de la dualidad:

La condición necesaria y suficiente para que un problema de programación lineal tenga solución es
que, tanto el conjunto de soluciones del primal (Z*) como en conjunto de soluciones del dual (G*) no sean
vacíos, es decir, que ambos problemas sean factibles.
1) Ambos problemas tienen la misma solución óptima, siendo Z*= G*.
2) Uno de los problemas es no acotado, en cuyo caso el otro problema es no factible. (o viceversa)
3) Ambos problemas son no factibles.

Teorema débil de la holgura complementaria:

Este teorema para el caso de la dualidad canónica sostiene que en el óptimo, “si una variable en
uno de los problemas es positiva, entonces la restricción correspondiente en el otro problema es sin
holgura (limitante); y si una restricción en uno de los problemas es con holgura (no limitante),
entonces la variable correspondiente en el otro problema debe ser nula”.
Este teorema denomina “variable” sólo a las variables de decisión y simplemente “holgura” a las
variables de holgura. Si ahora nombramos variable a todas, sean de decisión o de holgura, podemos
enunciar el teorema de la siguiente manera: “Si una variable en uno de los problemas (primal o dual) es
positiva, entonces la variable relacionada en el otro problema debe ser nula”.
Cuidado porque esta relación no siempre es viceversa.

A continuación se detallan los casos en los que este teorema no se cumple:

1) En un PROBLEMA DEGENERADO
 Debido a que hay más de m-n variables nulas. En el programa primal P5 está en la base debido a que es 0, pero
su valor del lado derecho VLD es 0, entonces su coeficiente de la variable de la función objetivo del programa dual
es 0.

2) En un problema con MÚLTIPLES SOLUCIONES ÓPTIMAS

Sabemos que son múltiples soluciones porque una variable (P4) da 0 y no está en la base.

Interpretación económica de las variables duales

En el óptimo, la variable dual representa la cantidad que incrementa la función Z ante un incremento unitario
en el i-ésimo valor del lado derecho (VLD). El incremento en Z sobre el incremento del VLD (insumos) es
igual a el incremento de la variable dual sobre los cambios de VLD (insumos).

Es imprescindible, para interpretar el significado económico de las variables duales tener en claro
qué es lo que representa la función objetivo del primal y la restricción relacionada a la variable dual que
se analiza.
Por ejemplo, si la restricción representa la disponibilidad de bi unidades de insumo para elaborar un
producto y Z representa la contribución total a las utilidades, entonces yi (variable dual) representa el
incremento en las utilidades por adicionar una unidad del i-ésimo insumo.
Si, en cambio, la i-ésima restricción representa la demanda de al menos bi unidades producidas y Z
representa el costo total de producción, entonces yi es el costo incremental de producir una unidad más del
i-ésimo producto.
 Y1 = Hs. De maquinado
Y2 = Hs. De Armado
Y3 = Hs. De montaje

● Si agregamos una hora extra de maquinado (Y1) ganamos 10 pesos.

● Si agregamos una hora extra de armado (Y2) ganamos 0 pesos. Tiene sentido porque S4 nos dice
que ya nos sobraban 225 horas.
● Si agregamos una hora extra de montaje (Y3) ganamos 5 pesos.
ANALISIS DE SENSIBILIDAD
El análisis de sensibilidad permite estudiar los efectos que tienen las variaciones que pueden
producirse en los valores de los parámetros en la solución óptima del problema.

Interpretación de las tasas de sustitución:

• Tasa de sustitución positiva (+): cuantas unidades se REDUCE el valor de solución de la variable
básica que se encuentra en la fila i, por cada unidad que se incrementa la variable de la columna j.
• Tasa de sustitución negativa (-): cuantas unidades se INCREMENTA el valor de solución de la
variable básica que se encuentra en la fila i por cada unidad que se incrementa la variable de la
columna j.

Por cada X2 que se produzca,

• el sobrante del “recurso asociado a” S4 se reduce en 60 unidades

• el sobrante del “recurso asociado a” S6 se INCREMENTA en 0.5 unidades
• la cantidad producida de X1 se reduce en 0.5 unidades

Tipos de variaciones a analizar:

• Coeficientes de la función objetivo (Cb)

➢ Variable básica

Fórmula: Variación permitida i = valor de fila cj-zj / Tasa de sustitución en fila i, columna j.

• Columna j: es la columna que corresponde a la VARIABLE NO BÁSICA en análisis.

• Los valores más cercanos al 0, positivos o negativos, son los límites permitidos de variación.
 Representa en cuantas unidades monetarias podría variar “el precio (max) o el costo (min)” (el
coeficiente) de la variable básica en análisis para que se equipare con una de las variables NO
BÁSICAS. Por lo cual se convertiría en una posible variable a SALIR de la base (habría múltiples
soluciones). Si la variación es superior, ya saldría de la base.

➢ Variable no básica
o Variación de producción (X2)
Cantidad posible de producir de la “variable j” que no está en la base.

Fórmula: Variación permitida = Solución en fila i / Tasa de sustitución en fila i y columna j.

• Columna j: es la columna que corresponde a la variable no básica en análisis.

• El valor “positivo” más cercano a 0 es el límite máximo de variación.

*ATENCIÓN: si hay una tasa de sustitución negativa, el resultado de la fórmula no se

considera, porque se está indicando producción negativa de “algo físico”, por lo cual no es
posible.
 o Variación del coeficiente (Cb)
Representa en cuántas unidades monetarias podría variar como máximo el “precio (max) o
el costo (min)” (coeficiente) de la variable no básica en análisis para que se equipare con una
de las variables básicas (habría múltiples soluciones). Si la variación es superior ya
convendría y entraría a la base.

Fórmula: Variación de “precio” = Valor contrario a su Cj-Zj

• Variaciones en los valores del lado derecho (VLD)

➢ Restricciones no limitantes
o Holguras básicas
Significa que ese recurso “B” (asociado a la holgura) SOBRA en esa cantidad, por lo
cual se puede reducir su disponibilidad en esa cantidad. NUNCA hay valores con el signo
negativo en la columna solución (es una de las condiciones básicas de simplex).

Fórmula: Variación de “disponibilidad” = al valor que figura en su solución.

 o Excedentes básicas
Se interpreta como que el límite de mínima es SUPERADO en esa cantidad, por lo cual se
puede INCREMENTAR esa restricción de mínimo “consumo de un recurso o insumo, o producción
de un producto”, a un valor superior. NUNCA hay valores con el signo – (negativo) en la columna
solución.
Fórmula: Variación de “límite de mínima” = al valor que figura en la solución.

➢ Restricciones limitantes
o Holguras no básicas (restricciones de “<= “)
Representa en cuántas unidades podría variar la “disponibilidad de ese recurso (b)” que es
limitante.
VLD + ∆bi * Ts >=0

• ∆bi: es la variación permitida corresponde al recurso bi asociado a la HOLGURA NO

BÁSICA en análisis
• Ts: tasa de sustitución que vincula las variables básicas contra la variable no básica en
análisis.
• VLD: valor de solución de cada variable básica contra la cual comparamos.

Se interpreta igual a su signo, si es + (positivo) es un INCREMENTO, si es – (negativo) es una

REDUCCIÓN.
o Excedentes no básicas (restricciones de “>=“)
Se interpreta como las posibilidades de reducción o ampliación del límite de mínima asociado a
esa variable de excedente (ejemplos: consumo mínimo de un recurso o producción mínima de
un producto.
VLD - V * Ts >=0

• V: es la variación permitida corresponde a la HOLGURA NO BÁSICA en análisis

• Ts: tasa de sustitución de la variable básica en análisis.
• VLD: valor de solución de la variable básica en análisis.

Se interpreta igual a su signo, si es + (positivo) es un INCREMENTO, si es – (negativo) es una

REDUCCIÓN.

o Holguras no básicas (precio sombra)

Fórmula: “precio sombra” = valor contrario al Cj-Zj de su columna.
• CJ-Zj = Representa el aporte a Z por unidad de la variable en análisis.
• Zj = representa al sumatoria de sustituciones por unidad de la variable en análisis.

MAXIMIZACIÓN: Se interpreta como el incremento en Z que se produce por cada incremento en

el valor de los lados derechos.
En casos de max. de beneficios se puede interpretar como el precio extra que yo estaría
dispuesto a pagar (por encima del valor de compra actual, porque Cj-Zj ya significa beneficio)
por una unidad adicional de “recurso” (b) que actualmente es limitante. (ej: yo pagaría hasta 1,10
unidades monetarias extras)

MINIMIZACION: Se interpreta como costo en que se incrementa Z, por el incremento de una

unidad en el valor del lado derecho (b) que actualmente es limitante.
PRECIO SOMBRA VS. PRECIO DUAL
Al analizar los cambios en los lados derechos de las restricciones aparecen alguno de estos dos
importantes conceptos: precio dual y precio sombra.
Precio sombra indica la variación que se produce en el valor de la función objetivo ante un incremento en
el lado derecho de una restricción. El precio sombra es el valor de la variable dual correspondiente.
Esto significa que, para un problema de maximización, si el precio sombra es positivo, un incremento
en el valor del lado derecho (VLD) implicará un crecimiento en el valor de la función objetivo y, por lo tanto,
el valor de la función objetivo mejora. Si, en cambio, el problema es de minimización, como un precio sombra
positivo indica un incremento de la función objetivo, entonces nuestro objetivo desmejora.
● Problema de máximo: precio sombra (+) es algo bueno
● Problema de mínimo: precio sombra (+) es algo malo

Precio dual representa la mejora o desmejora que se produce en el valor de la función objetivo, ante un
incremento en el lado derecho de una restricción, según que el precio dual sea positivo o negativo.
Esto quiere decir que un precio dual positivo nos indica en cuánto mejora el valor de la función
objetivo ante un incremento del lado derecho; y aquí mejora expresa que el valor objetivo crece en caso de
máximo y decrece en caso de mínimo.
De la misma manera, un precio dual negativo representará la desmejora que se produce en el valor
de la función objetivo ante un incremento del VLD.
● Precio dual es (+) siempre es algo bueno
● Precio dual es (-) siempre es algo malo

Como resumen de lo anterior, podemos decir que:

● En caso de maximización, precio sombra y precio dual son iguales
● En caso de minimización, uno es el opuesto del otro.
 ENTERA Y MIXTA

Este capítulo trata sobre modelos que podrían ser formulados y resueltos como modelos de PL,
con la condición de que algunas o todas sus variables tienen que asumir valores enteros. Es decir, no es
aceptable un valor fraccionario en una variable. Por lo que, además de la restricción de no negatividad va a
haber una restricción del tipo “solo variables enteras”.
El modelo de programación entera es un modelo de programación lineal donde las variables deben
asumir valores enteros. Si solo es necesario que algunas variables sean enteras, entonces se trata de un
problema de programación entera mixta. Cuando las variables pueden asumir solamente valores 0 o 1,
se denomina programación entera binaria.

Entonces, la programación entera se divide en 3 tipos de modelos:

● Programación Entera Pura: Todas las variables de decisión tienen valores enteros.
● Programación Entera Mixta: Algunas de las variables de decisión tienen valores enteros. Las
demás cumplen con la suposición de divisibilidad.
● Programación Entera Binaria: Utiliza variables binarias.

En este tema se presenta un tipo de problemas similares a los problemas de Programación Lineal,
ya que en su descripción solo se establecen expresiones lineales. Sin embargo, no responden a
problemas lineales ya que algunas (o todas) las variables del problema toman valores que no están en
un conjunto continuo, pueden ser variables que toman valores 0 o 1(binarias), o variables que toman
valores enteros no negativos (0, 1, 2,), etc. Pero la diferencia esencial que existe la programación lineal y
la entera es que en la programación lineal se maximiza o minimiza una función sobre una región de
factibilidad convexa, mientras que al usar los métodos de programación entera se maximiza una función
sobre una región de factibilidad que generalmente no es convexa. De tal manera que la programación
entera tiene más complicaciones que la programación lineal.

Relajación Lineal del programa entero (RPL)

La relajación lineal se da cuando se resuelve el mismo problema pero sin la restricción de que sean
enteras las variables. La relajación lineal (RPL) de un PE se obtiene al omitir la condición que exige que
las variables sean enteras. En consecuencia, el problema se transforma en un PL continuo, resultando una
versión menos restringida del problema entero.

Si la región factible de la relajación lineal de un programa entero puro es acotada, entonces la

región factible del programa entero estará formada por un número finito de puntos. El problema consiste
en hallar el valor óptimo de dicha región y que estén dados en números enteros, entonces surge la
siguiente pregunta.

¿Por qué no redondear los valores óptimos de la relajación lineal para que sean enteros?
Podríamos trabajar con una solución redondeada al entero más próximo. El uso de este tipo de
soluciones es aceptable en situaciones en que el redondeo no tenga una importancia relativa significativa.
El problema es que si redondeo para arriba eventualmente puedo salir de la región factible, y si
redondeo para abajo no me aseguro de que sea una solución óptima, aunque sea dentro del conjunto de
solución. Por eso la solución del programa lineal truncado o redondeado está lejos de ser el óptimo entero,
siendo necesario usar algún algoritmo para hallar esta solución de forma exacta.
Por ejemplo:
Si analizamos la solución gráfica de este problema, podemos ver que:
● La solución óptima de la relajación lineal es A = 4,39 y B = 5,7, siendo el valor objetivo de $328,90.
● Si se redondea en A = 4 y B = 6, la solución queda fuera del conjunto de soluciones factibles.
● Si se redondea en A = 4 y B = 5, el objetivo asume el valor de $290.

Entonces podemos afirmar que, en problemas cuyas variables asumen valores fraccionarios
relativamente grandes (5,7) , podemos pensar en redondear el valor de estas al entero más próximo (6).
Sin embargo, el método de redondeo puede conducir a situaciones como:
● Puede suceder que, redondeando al entero más próximo, este valor de la variable no sea factible.
● Aun cuando uno o más de los puntos enteros cercanos sean factibles:
✓ No necesariamente serán óptimos para el PE.
✓ No necesariamente estarán cerca de la solución óptima.

La solución óptima entera la encuentro mediante el método de “Ramificación y Acotación”.

Método de Ramificación y Acotación

Es una metodología que consiste en dividir, progresivamente, una relajación lineal en dos nuevos
modelos que acoten a las variables de valor óptimo decimal (no enteras).
Estas variables se acotan a través de restricciones excluyentes, para que estas dividan a la
región factible en dos partes. De manera tal que se eliminen los valores no enteros de la variable
seleccionada en la relajación lineal, hasta encontrar la solución entera óptima.

El primer modelo se genera agregando una restricción que acote dicha variable a valores menores
o iguales a la parte entera de la solución óptima y el segundo, agregando una restricción que acote la
variable a valores mayores o iguales a la parte entera más uno de la solución óptima.

Esta metodología se repite sucesivamente hasta encontrar la mejor solución óptima entera. En
estas circunstancias se genera un árbol de modelos cuya cúspide es el modelo original, el que se ha
expandido sucesivamente al efectuar la bifurcación por el acotamiento de las variables de valor óptimo
decimal. Cada modelo queda representado por un nodo y cada nueva restricción por una rama que
conecta un nodo con el siguiente.
 La acotación se basa en el hecho de que las regiones factibles de los problemas que surjan al
agregar las nuevas restricciones son, en realidad, subconjuntos del conjunto de soluciones de la RPL
y, por lo tanto, el valor óptimo de Z en estos dos subconjuntos será:

● En caso de MAXIMIZACIÓN, “el valor objetivo óptimo de la relajación lineal es siempre ≥ que el
valor objetivo óptimo del programa entero”. Esto significa que “el valor objetivo óptimo de la
relajación lineal es una cota superior para el valor objetivo óptimo del programa entero”.

Z* óptimo de simplex > Z* óptimo de enteros en MAX

● En caso de MINIMIZACIÓN, “el valor objetivo óptimo de la relajación lineal es una cota inferior
para el valor objetivo óptimo del programa entero”.

Z* óptimo de simplex < Z* óptimo de enteros en MIN

Algoritmo del método

1. Encontrar la solución mediante el Método Simplex. Si la solución no es entera, pase al segundo
punto.
2. Se genera la Relajación Lineal del programa entero (RPL)
3. A partir de la relajación lineal, se divide el problema en dos nuevos subproblemas agregándole a
cada uno una nueva restricción, de manera tal que se excluya el valor fraccionario.

Como no me he dado entera X1 sigo ramificando. Creó dos programas lineales donde busco el
valor entero de la variable X1 que vale 0,67, entonces va a ser mayor a 1 y otro menor a 0.
4. Se selecciona una variable (variable X1) y se crean dos ramas mutuamente excluyentes, esto da
lugar a dos (2) nuevos problemas de Programación Lineal; que se deben resolver.

Como ya encontré una solución donde las variables son enteras, pero tengo del otro lado un Z
mayor entonces se busca una solución mejor explorando ramas donde el valor de Z sea mayor.
Nuestro primer Z con variables enteras es nuestra COTA. Pero seguimos ramificando por el otro
lado.
5. Si ninguna solución es entera, con la rama de mayor valor de Z, se crean nuevas ramas y se
resuelven nuevos problemas por programación lineal (Método Simplex).
 6. Se repite el punto 4), Hasta encontrar la solución entera óptima.

Existen cuatro posibles resultados para cada subproblema:

1. Si un problema no es factible, no se lo investiga más.
2. Si la solución de la relajación de PL para el problema es entera, se registra esta como la posible
mejor solución y se la guarda como cota inferior.
3. Si la solución de la relajación de PL es peor que alguna solución entera que ya se conoce,
entonces no se investigará más el problema.
4. Si la solución de la relajación de PL es fraccionaria, pero mejor que cualquier solución entera que
se conoce hasta ese momento, se divide a la región factible para ese subproblema, de manera que
se excluya una parte de la solución. Se continúa este procedimiento hasta que no existan
subproblemas que deban investigarse.

Recordar!
Tener en cuenta, que puede haber el caso de que las dos variables tengan valor fraccionario. En tal
caso, elijo una única variable donde aplicamos las dos restricciones. Elegimos alguna de ellas, tomar
aquella que esté más cerca de 0,5.
Cuando se va abriendo de ambos lados la ramificación, más ramas, la lógica que sigo es seguir
explorando aquellas ramas donde el Z me da más grande.
Variables Enteras Binarias
Existen situaciones en las que la decisión a tomar es hacer o dejar de hacer algo es SI o NO. En
estas circunstancias se introduce una nueva variable que puede tomar sólo dos valores posibles: 1 (Uno)
si la decisión es SI y 0 (Cero) si la decisión es NO.
La filosofía del método se basa en pensar que si se tiene una función objetiva minimizando y todos
sus términos son positivos, entonces, entre menos variables tomen el valor de uno (1), la función objetiva
será mínima.
A continuación, se ejemplifican diferentes situaciones en las cuales se hace imprescindible su utilización:

● Restricciones mutuamente excluyentes (“Either – Or”)

Algunas veces, en una situación de decisión, hay que mantener una restricción u otra (a lo menos
una de ellas), pero no ambas.

En la programación entera se puede manejar esta situación con una variable binaria "Y" si
se usan las siguientes restricciones modificadas:

Observe que si Y = 0, la primera restricción es efectiva, pero el término independiente de la

segunda se hace muy grande y por lo tanto no es en la práctica efectiva. Por el contrario, si Y = 1,
la segunda restricción limita pero no la primera, ya que MY es muy grande.

● Decisiones dependientes o consecuenciales (“If – Then”)

En otras oportunidades, en situaciones también de decisión, se desea asegurar que si una

restricción (M) se cumple, otra restricción (K) también deba cumplirse; sin embargo si K no se
cumple, entonces M puede o no cumplirse.
K depende de M, pero M no depende de K
 Para asegurar lo anterior utilizamos la siguiente formulación de restricciones:
a) La opción M puede ser elegida sin que lo sea la opción K.
b) Si se elige la opción K, entonces la opción M también. A este tipo de restricciones se las
suele llamar “restricciones de correquisito”.
c) Si NO elige la opción M, no podrá elegir la K. Sin embargo, puede no seleccionar ninguna
de las dos.
Ejemplo:

M = X1
K = - X1 + 4X2 + 24

● Si X1 > 0 entonces X1 - 4X2 - 24 puede cumplirse sólo si Y = 0

● Si no se satisface X1 > 0, en la segunda restricción se puede aceptar que Y sea 0 o bien
1 y la primera restricción podrá cumplirse (Y=0) o nó (Y=1).

● Restricciones en el tamaño del lote

Un problema en el cual se requiere un nivel mínimo para emprender una actividad. Por
ejemplo, una empresa puede tener la necesidad de comprar una cantidad mínima de 50 unidades
de cierto producto pero no más de 150 unidades. Sea X el número de unidades que se compran;
entonces, se debe modelar que X = 0 o bien:

Si se presenta el caso de que esté la opción de que se decida comprar, que se compre
más de 50 pero no más de 150. Para modelizar esta situación, necesitamos usar una variable 0-1
para la acción de comprar.
➔ Y = 0 si se decide no comprar
➔ Y = 1 si se decide comprar
Si tengo un costo asociado por unidad comprada, el costo vale cuando se “compra” y no
vale nada cuando “no se compra”

Si no tengo la cantidad máxima de unidades que puedo comprar entonces debo utilizar el
número “M” muy grande. De esta manera si Y = 0, ambas restricciones hacen que X debe ser 0.
 Por el contrario si Y = 1, por la segunda restricción X debe ser por lo menos 50 y la primera
restricción no restringe a X porque M es un número muy grande.

Se resuelve de esta manera debido a que sin la restricción de M, cuando Y = 0, la

restricción queda X ≥ 0, de esta forma podría X tomar cualquier valor mayor que 0, con lo cual no
se respeta el número mínimo de 50 unidades.

● Restricciones de costo fijo

En muchas situaciones, nos encontramos con un costo de producción con dos
componentes: uno fijo y uno variable. El uso de variables 0-1 nos permite incluir el componente fijo
del costo en caso de que se produzca el producto considerado.
Supongamos que una empresa que fabrica un producto A tiene que disponer de una
maquinaria especial, la que debe alquilar a:
● Maquinaria para el producto A a $500 por semana.
● Maquinaria para el producto B a $550 por semana.

Variables:
● xA = unidades del producto A a producir semanalmente.
● xB = unidades del producto B a producir semanalmente.
● yA = 1 o 0, si es que el producto A se produce o no se produce.
● yB = 1 o 0, si es que el producto B se produce o no se produce.
 La producción máxima de A está dada por el mínimo entre: 250/5 y 300/7 entonces, M = 42
unidades. En el caso de B, está dada por el mínimo entre 250/3 y 300/2, entonces, N = 83
unidades.
Ej 2:
Suponga que un producto nuevo contribuirá con cinco dólares por unidad a la utilidad total
del negocio y que se realiza un gasto único de 100 dólares para preparar la maquinaria para una
batch de producción. El costo es cero si no se producen unidades.
Sea X el número de unidades que se producirán. Entonces, podemos formular el problema para
que:

● Cuando Y = 0, la segunda restricción hace que X sea 0 y la contribución Z = (5X - 100Y)

también es cero.
● Cuando Y = 1 no existe un límite práctico para X ya que M es un número muy grande y
además la cantidad de cargo fijo de 100 dólares se descuenta de la utilidad.
Un error que en ocasiones se comete en las formulaciones de programación entera es que
se emplean funciones no lineales. Por ejemplo, el problema de cargo fijo se podría formular como
la maximización de Z = 5XY - 100Y, donde Y es una variable binaria como las anteriores. Observe
que se cumplen los requisitos, ya que no hay beneficio si Y = 0 y el beneficio es 5X - 100 si Y = 1.
No obstante, el término 5XY no representa un problema válido de programación lineal entera ya
que es una expresión cuadrática.

Practicar con:
ANÁLISIS DE SENSIBILIDAD EN PROGRAMAS LINEALES ENTEROS
Es muy importante aclarar que, en el caso de programas lineales enteros, no es posible utilizar la
información proporcionada por los precios sombra ni por el análisis de sensibilidad, ya que fueron
diseñados para programas lineales continuos.
Sin embargo, sabemos que esta información es muy importante y la manera de salvar esta
situación es realizando múltiples corridas del software que se esté utilizando para obtener dicha
información.
En problemas mixtos (sin la presencia de variables binarias), para aprovechar las ventajas del
análisis de sensibilidad, se suele utilizar el siguiente procedimiento:
1) Se resuelve el problema de PE.
2) Se añaden, como restricciones al problema, las variables enteras con el valor obtenido en el paso
anterior; de esta forma, el PE se transforma en un PL.
3) Se resuelve el PL obteniendo, de esta manera, el análisis de sensibilidad.
 PROGRAMA DE TRANSPORTE Y ASIGNACIÓN

TRANSPORTE
Distribución de bienes o servicios desde varios lugares de suministros y hasta varias
ubicaciones de demanda. Por lo general, es limitada la cantidad de bienes que están disponibles en
cada ubicación de oferta - orígenes - y los bienes se requieren en diversas ubicaciones de demanda -
destinos -.
El objetivo es minimizar el costo total de transportar los artículos desde los orígenes hacia los
destinos.
SUPUESTOS de programación lineal de Transporte:
⮚ Existe un conjunto de “m” o “h” orígenes conocidos con una oferta conocida
⮚ Existe un conjunto de “n” o “k” destinos conocidos con una demanda conocida.
⮚ La sumatoria de la oferta “a” tiene que ser igual a la sumatoria de la demanda “b”.
⮚ El flujo de producto es en un solo sentido, desde los orígenes hacia los destinos.
⮚ Los costos unitarios de envío son conocidos y permanecen constantes en el tiempo.

Se representa mediante un conjunto de nodos en forma de red, con origen y destino.

o Sumatoria de las unidades de los orígenes
o Sumatoria de las unidades de los destinos
o Las fechas significan un costo entre origen y destino por unidad
Planteo del problema:
1. Variables de decisión Xij = cantidad a enviar desde el origen i al destino j por semana
2. Objetivo: si yo estoy hablando de costos, el objetivo es minimizar el costo total semanal
3. Restricciones
I. Restricción por cada origen
II. Restricción por cada destino
4. Condición de no negatividad

MODELO:
𝑀𝑖𝑛 (𝑍) = 9𝑋11 + 7𝑋12 + 3𝑋13 + 2𝑋21 + 5𝑋22 + 8𝑋23

S.A
𝑋11 + 𝑋12 + 𝑋13 = 600 Restricción O1

𝑋21 + 𝑋22 + 𝑋23 = 700 Restricción O2

𝑋11 + 𝑋21 = 400 Restricción D1

𝑋12 + 𝑋22 = 500 Restricción D2

𝑋13 + 𝑋23 = 400 Restricción D3

Cantidad total de variables = m*n = 2*3 = 6

Cantidad de variables básicas = m + n -1 = 4
VARIANTES DEL PROBLEMA
Las variantes adicionales del problema básico de transporte pueden contemplar una o más de las
siguientes situaciones:
A. Oferta total distinta de la demanda total
Se pueden dar dos situaciones:

➔ Oferta > Demanda: Para equilibrar este problema, creamos un destino ficticio que
recibe la diferencia entre:

El costo de envío desde cada origen hacia ese destino ficticio es nulo. La o las
variables positivas que en la solución final aparezcan relacionadas con dicho destino
indicarán dónde quedó el excedente de oferta.

➔ Demanda > Oferta: Para equilibrar este problema, creamos un origen ficticio con una
oferta igual a la diferencia entre:

El costo de envío desde este origen hacia cada uno de los destinos es nulo. La o las
variables positivas que en la solución óptima aparezcan relacionadas con dicho origen
indicarán los destinos que quedaron con demanda insatisfecha.

B. Función objetivo de maximización

En este caso, los coeficientes de la función objetivo representarán beneficios unitarios
o contribución unitaria a los beneficios; en cuanto a las restricciones, no sufren modificaciones.
C. Rutas inaceptables
Se eliminan del planteamiento de programación lineal a las correspondientes variables de
decisión.

MÉTODO DE RESOLUCIÓN DE PROBLEMAS DE TRANSPORTE:

Procedimiento de dos fases (similar al Simplex). En primer lugar, se requiere encontrar la solución
factible básica inicial y, después, se procede en forma iterativa a realizar mejoramientos en la solución
hasta que se llega a la solución óptima.
FASE I: Determinación de la Solución Factible Inicial
Para determinar la SFB inicial, que debe ser no degenerada, se pueden usar varios
métodos:
a) Esquina noroeste
b) Mínimo costo
c) Vogel
d) Otros
FASE II: Mejoramiento de la Solución
Para cada variable básica, se plantea una ecuación:

Ui y Vi son variables auxiliares y tendremos una Ui para cada origen y una Vi para cada destino.
 Se formará un sistema de ecuaciones indeterminado el cual se debe resolver con cualquier método.
El objetivo es encontrar un conjunto de valores para las Ui y las Vi que luego a su vez, permitan
determinar para cada variable no básica, un índice de mejoramiento que se calcula como:

Esto nos indica el incremento que se produce en el costo total, es decir, Z, ante un incremento
unitario de variable Xij. Es decir, cuánto crece el costo total si enviamos una unidad desde el origen
i hasta el destino j.
Como lo que queremos es minimizar el costo total, entonces:

- Si , la solución analizada es la óptima.

- Si algún índice da un valor < 0, entonces la solución no es la óptima y debemos
determinar, al igual que en el simplex, cuál es la variable que entra y cuál es la que sale de
la base.

ESTRUCTURA:

En el lado derecho tenemos lo que puede producir cada origen, y la última fila representa lo que
demanda cada destino. Cada uno de los rectángulos representa una variable distinta. Los cuadrados
pequeños representan los costos de envío entre los nodos.
Problema de transporte método ESQUINA NOROESTE:

1) Equilibrar el problema, es decir verificar que: (Fase I)

Como en este caso la sumatoria de ai = 140 > sumatoria de bi = 120, debe crearse un destino
ficticio (D3) con todos sus costos de envío (Cij) iguales a cero, y con un requerimiento de demanda igual a
la diferencia entre el total ofrecido y el total demandado.
Modificando la tabla quedaría así:
Cada celda representará a una Xij (cantidades a enviar desde el origen i al destino j), y en el ángulo
superior derecho se colocará el costo unitario de envío desde cada origen a cada destino (Cij).
2) Elegir método para encontrar una primer SFB no degenerada:
Utilizaremos el método de la esquina [Link] en la primera celda superior izquierda.
Asignamos el mayor valor posible a la variable X11, teniendo en cuenta las restricciones de demanda y de
disponibilidad, es decir, la cantidad que el destino D1 requiere y la que el origen O1 tiene disponible para
enviar. Este valor es 45; quedando el origen O1 sin disponibilidad y el destino D1 con una necesidad de 45
unidades más, que se le enviarán desde el origen O2. Una vez satisfecha la demanda del primer destino,
pasamos al segundo destino, cuya demanda es de 30 unidades. Como el origen O2 todavía dispone de 5
unidades, se las enviaremos al D2, quedando aún una demanda insatisfecha de 25 unidades, las que
recibirá desde el origen O3. De esta manera, cada origen ha enviado todo lo que dispone y cada destino
ha recibido todo lo solicitado.
Corresponde ahora controlar que la solución encontrada sea una SFB no degenerada, para la cual
contamos el número de variables positivas, las que, para este problema, debe ser : 3 + 3 - 1 = 5.

La solución factible básica inicial es:

X11 = 45 X23 = 0
X12 = 0 X31 = 0
X13 = 0 X32 = 25
X21 = 45 X33 = 20
X22 = 5
El valor de Z = 1030
Cada una de las variables positivas muestra la cantidad de mercadería a enviar desde el origen Oi al
destino Dj, a excepción de X33, que indica la mercadería que quedó sin enviar en el O3.
En la Fase II del método, debe verificarse si la solución encontrada es óptima; si no lo es, deberá
determinarse una variable que entra a la base y otra que sale.
3) Verificar optimidad (Fase II)
Se plante para cada variable básica la siguiente ecuación:

Luego para cada variable no básica se calcula el índice:

Si estos índice de mejoramiento son todos mayores o iguales a cero, entonces la solución es óptima; de lo

contrario, deberá seleccionarse como variable de entrada a la que tenga el negativo más pequeño.
 Para seleccionar la variable que sale de la base, se procede con el siguiente razonamiento: Se
determina qué modificaciones deben hacerse en la solución actual si pretendemos enviar una unidad
desde el O3 al D1, respetando el conjunto restricciones de oferta y demanda. Con esta finalidad,
colocamos un signo más en la celda de la variable que entra y luego vamos compensando con sucesivos
signos más y menos hasta cerrar el circuito y solo afectando a variables básicas, como se muestra a
continuación:

El valor máximo que puede asumir la variable que entra (X31) estará dado por el mínimo entre X21
y X32, esto es, donde se colocaron signos menos. Es decir;

Para encontrar la nueva solución, se procede a actualizar la tabla, sumando y restando el valor de
X31 en todas las celdas donde haya algún signo más o menos.

La variable que salió de la base fue X32.

El valor de Z puede calcularse como:

Esta nueva solución es:

Nuevamente hay que evaluar si esta solución puede mejorarse y el proceso se repite hasta que
todos los sigma sean mayor o igual a cero, momento en el que se habrá encontrado la solución óptima.

Determinamos la variable que sale de la base en la tabla 6:

La nueva solución es:

 Verificamos si la solución encontrada es la óptima:

Como todos son mayores o iguales a cero, concluimos que es la más óptima.

Problema transporte Método Mínimo Costo

Se parte de la celda con menor costo y se va asignando el mayor valor posible.

En este caso, sería la celda con costo de $7, y se asigna 1500. La demanda insatisfecha es de 1600.
El siguiente menor costo debería de ser el de $9, pero como del origen O3 no dispongo de nada. Sigo con
el costo menor siguiente, en este caso el de $11.
Siempre evitar que se asignen unidades a M.
 ASIGNACIÓN - MÉTODO HUNGARO
Caso especial de la programación lineal
Busca encontrar la forma de asignar ciertos RECURSOS (MAQ O PERSONAS) para la realización de
determinadas TAREAS O ACTIVIDADES AL MENOR COSTO.
OPTIMIZAR RENDIMIENTOS: costos, tiempos, utilidad, otro.
Generalmente es de minimización, pero a veces es de maximización.
Objetivo: asignar “n” tareas a “n” máquinas a un mínimo costo.
- Las tareas son independientes y pueden realizarse en cualquier máquina.
- Cada tarea debe realizarse en una sola máquina – cada máquina 1 tarea.

FORMULACIÓN

X ij = 1, si la tarea i se asigna a la máq. j.

X ij = 0, de otra manera.
C ij = costo de cada variable.
Se tiene 1 restricción por cada variable a asignar.
Se tiene 1 variable por cada máquina asignada.

VARIANTES DEL PROBLEMA

1. Objetivo de Maximización: Al igual que en el problema de transporte, en este caso, los
coeficientes de la función objetivo representarán algún tipo de beneficio, monetario o no.
2. Número total de individuos diferente al número total de tareas: Si el número de individuos es
menor al número de tareas, deberán crearse tanto orígenes ficticios como individuos faltantes, con
un costo de asignación igual a cero. Por el contrario, si el número de tareas es inferior al número de
individuos, deberán crearse tantos destinos ficticios como tareas faltantes, con costo de asignación
igual a cero.
3. Asignaciones no aceptables: Se deben eliminar del problema lineal las correspondientes
variables de decisión.
4. Asignaciones múltiples: Se modifica la formulación del problema de la siguiente manera, si
representamos como ai al número de tareas que pueden ser asignadas al individuo i, la restricción
correspondiente será:
 PASOS DEL MÉTODO HUNGARO
1) Reducción por filas: Elegir el menor elemento de cada fila y restárselo a todos los valores de la
fila.
2) Reducción por columnas: Elegir el menor elemento de cada columna y restárselo a todos los
valores de la columna. La matriz encontrada mediante estos dos pasos es una matriz de costos
reducidos.
3) Cubrir los ceros de la matriz: Cubrir todos los ceros de la matriz con el menor número de líneas
(horizontales y verticales) posibles.
4) Prueba de optimidad: Si el número de líneas trazadas es igual al número de filas (columnas), se
encuentra entonces una solución óptima entre los ceros de la matriz. Si el número de líneas
trazadas es menor a m, volver a reducir la matriz, de acuerdo a lo explicado en el punto 5.
5) Reducción de la matriz: Seleccionar el menor número no cubierto por la línea y restárselo a los
restantes elementos no cubiertos y sumárselo a los elementos que se encuentran en las
intersecciones de las líneas.
6) Volver al paso 3

TEOREMA: “El número máximo de celdas cero independientes en una matriz de asignación reducida es
igual al número mínimo de líneas que cubren todos los ceros de la matriz”. En base a este teorema es que
se plantea la prueba de optimidad del método.

MINIMIZACIÓN
No se selecciona la tarea con menor costo, ya que se busca una minimización general.
En la tabla se observa los costos de realizar la tarea i en la máquina j.

FUNCIÓN OBJETIVO:
MIN Z= 5 X11 + 7 X12 + 9 X13 + 14 X21 + 10 X22 + 12 X23 + 15 X31 + 13 X32 + 16 X33

SUJETO A:
X11 + X12 + X13 = 1
X21 + X22 + X23 = 1 Cada tarea puede ser asignada a 1 sola máquina.
X31 + X32 + X33 = 1

X11 + X21 + X31 = 1

X12 + X22 + X32 = 1 Cada máquina puede ser asignada sólo a 1 tarea.
X13 + X23 + X33 = 1
X ij = 1, 0
 A) De la tabla de costos identificar el MENOR costo de cada fila.

B) Generar una nueva matriz de costos, RESTANDO a todos los elementos de la fila el menor
elemento de ella (Pn). REDUCCIÓN POR FILA.

Q1=0 Q2=0 Q3=2

C) Generar una nueva matriz de costos, RESTANDO a todos los elementos de la columna el menor
elemento de ella (Qn). REDUCCIÓN POR COLUMNA.

D) Tachar con líneas los ceros de todas las filas y columnas. La cantidad de líneas debe ser
IGUAL al tamaño de la matriz.

Cuando no es Óptima, es decir, cuando el tamaño de la matriz no es igual a la cantidad de líneas: Se

identifica el MENOR de los no tachados:
1- Se los RESTA los no tachados.
2- Se los SUMA a en donde hay cruces.
3- Los que están en la línea quedan IGUAL.
Ahora si tachamos con líneas los ceros. Tendríamos 4 líneas. Estaríamos en el ÓPTIMO.

E) Asignación de la matriz. Asignar los ceros que sean ÚNICOS en cada fila o columna.

COSTO: P1 + P2 + P3 + Q1 + Q2 + Q3 = 5 + 10 + 13 + 0 + 0 + 2 = 30

COSTO MÍNIMO: 30
 UNIDAD 3: PROGRAMACIÓN DINÁMICA

Permite encontrar la solución de problemas complejos, descomponiéndolos en una secuencia de

problemas más pequeños y, de esta manera, encontrar la combinación de decisiones que optimicen la
efectividad global.
La secuencia u orden cronológico es hacerlo de atrás para adelante (desde la última hacia la primera).

METODOLOGÍA:
A) Identificar el objetivo y variables que intervienen en el problema.
- Objetivo: Maximizar rendimiento total
- Etapas: distintas inversiones
- Estados: Dinero disponible para inversión al inicio de cada etapa
- Decisiones: Dinero invertido en cada etapa
B) Identificar, al inicio de cada etapa, cuáles son los estados posibles. Ej dinero disponible para
realizar la inversión.
C) Calcular para cada combinación de un estado y una decisión el rendimiento obtenido, que es igual
al rendimiento de invertir $dn en esta etapa más el rendimiento óptimo de invertir $(Xn-dn) en las
etapas siguientes. La función aquí utilizada se denomina función recursiva.
D) Para cada estado, identificar cuál es la decisión óptima (d*) según el objetivo del problema, cómo
maximizar el rendimiento total. En cada etapa, tenemos como entradas el dinero disponible y las
alternativas de cuánto invertir; y como salida, el dinero disponible para la próxima etapa. Es decir
que en cada etapa los estados al inicio se determinaron como:

En general:

Y el rendimiento óptimo para la etapa n dado el estado Xn será:

CONCEPTOS IMPORTANTES:
Existen 3 tipos de variables:
Variable de ETAPA: Se trata de una variable ordenadora que representa cada uno de los
subproblemas en los cuales se divide un problema de PD.
Variable de DECISIÓN (dn): Representa a las acciones posibles a tomar en la etapa n.
Variable de ESTADO (Xn): Sirven de enlace entre las etapas, describiendo la condición en que se
encuentra el proceso al inicio de cada una de ellas. Estas variables son las más difíciles de identificar. Se
debe preguntar ¿Qué es lo que cambia de una etapa a otra?, ¿Qué información se necesita para identificar
la política óptima de aquí en adelante?, ¿Cómo se puede describir la situación actual?

Características comunes:
● El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.
En el ejemplo, las etapas estaban dadas por las diferentes alternativas de inversión. La política de
decisión fue elegir, en cada una, aquella que ofreciera mayor rendimiento.
● Cada etapa tiene un cierto número de estados asociados a ella. Los estados asociados a cada etapa
era el dinero disponible para invertir.
● El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado
asociado con la siguiente etapa. La decisión de cuánto invertir en la opción actual determina el
dinero disponible para inversión en la siguiente alternativa analizada.
● En el problema de inversión, en el procedimiento de solución, se construyó una tabla para cada
etapa (n) que prescribe la decisión óptima (dn*) para cada estado posible (xn).

PRINCIPIO DE OPTIMIDAD DE BELLMAN

“Una política óptima tiene la propiedad de que, independientemente de las decisiones tomadas para llegar
a un estado particular en una etapa particular, las decisiones restantes que dependen de esta deben
también ser óptimas.”
I. CASO PROBLEMA DE CAMINO MÁS CORTO
Tenemos 10 ciudades, en cada camino tenemos costos asociados, y tenemos que encontrar el
menor costo [Link] el que en cada nodo aumenta los caminos posibles. Según donde estemos
vemos hacia dónde vamos.
Los subproblemas los llamamos etapas, en este caso tenemos 4 etapas diferentes. Los subproblemas
están relacionados. En cada instancia, en cada subproblema no necesariamente elegir el menor costo me
va a llevar al mejor camino.

El costo es lo que está sobre las flechas (f) y el costo acumulado es (f*)

1) Definimos las tres variables.

n: es la variable de etapa que representa las diferentes etapas en las que puedo estar. En este caso sería
la sección del viaje.

Dn (xn): es la variable de decisión representa la ciudad de destino en la etapa n.

Xn (sn): es la variable de estado representa a la ciudad de origen al inicio de la etapa n.

Tengo que tomar 4 decisiones que juntas forman una política óptima, que en este problema es minimizar
el costo total. Siempre resulta más fácil arrancar desde la última etapa, porque sabemos a dónde
queremos llegar, y casi siempre los problemas se tiene identificado el destino.

n=4
La última etapa es la trivial. Entonces resolvemos la última etapa para los posibles estados que
tenga, una vez que la tenga resuelta pasamos a la etapa anterior (n-1)

dn* es el destino óptimo en la etapa n.

fn* es el costo acumulado óptimo en la etapa n.

n=3
Estados posibles de origen son 5, 6 o 7, ahora no es trivial, entonces ahora si se va a tener más de
una ciudad de destino (d3) posible óptima. d3 puede dirigirse a la ciudad 8 u 9.
Se van analizando los problemas, interrelacionándolos entre ellos. Entonces el costo que se coloca
en dn es acumulado, por que la decisión de tomar el camino en 8 implica tomar el costo adicional de
$3 para llegar hasta el destino del nodo 10.
De la ciudad 6 se puede ir a la ciudad 8 o 9, tomando como costo: de ir de la ciudad 6 a la 8 un costo
de $6 más el costo adicional de $3 para ir de la ciudad 8 al destino final 10. Lo mismo se repite para
cada origen Xn (5,6,7).

Para la elección del destino óptimo d3*, de cada fila Xn de ciudad origen se elige el dn de menor
costo y ese es el destino elegido como posible óptimo (d3*) con su respectivo costo acumulado (f3*).
Ej de la ciudad origen 5, el destino de menor costo acumulado es el de la ciudad destino 8 con un
costo de $4 contra $8. Por lo que se coloca en d3* = 8 y en f3* $4.
n=2
Los orígenes posibles son la ciudad 2, 3 o 4. Identificamos las decisiones que podemos tomar d2=
5,6,7 (destinos posibles).
Desde la ciudad 2 hasta la 5 tengo un costo de 7, pero como tengo que interrelacionar los problemas
tengo que sumarle 1 + 3, obteniendo un costo de 11.
Entonces elegimos el costo menor en el camino de 2 por 5, 6 y 7 y a partir de ahí, definimos cuál
destino elegimos, en este caso, podría ser 5 o 6 ya que ambos implican un costo de 11.

n=1
Va a haber una única fila, ya que es el único origen inicial. Similar a cuando es el único destino.

Política óptima
Una vez calculadas todas las etapas con sus respectivos costos acumulados, se arma la política
óptima.

Desde la ciudad 1 elijo la ciudad 3 por que es una de las ciudades óptimas, luego elijo a la 5 me dice
que voy a 8, y de la 8 voy a 10.
Costo total de tomar este camino = 4+3+1+3=11

Ahora voy por el camino en donde en vez de ir por la 3 voy por la ciudad 4. Estoy en la ciudad 1, voy
a la 4, voy a la 5 o 6, elijo la 5, la siguiente etapa voy a la 8 y luego a la 10.
Costo total de tomar este camino = 3 + 4 + 1 +3 = 11

Ahora voy por el camino en donde en vez de ir por la 3 voy por la ciudad 4. Estoy en la ciudad 1, voy
a la 4, voy a la 5 o 6, elijo la 6, la siguiente etapa voy a la 8 y luego a la 10.
Costo total de tomar este camino = 3 + 2 + 3 + 4 = 12

Función de Recurrencia
Hay que identificar una función que represente todo el problema que se llama “función de recurrencia”
(Fn*), representa el problema completo.
Primero tengo que identificar la función de las tablas de forma generalizada:
Fn (xn,dn) = costo (xn,dn) + f(n+1)* (dn)
f3 (7,8) = costo (7,8) + f4*(8)
f3 (7,8) = 6 + 3
f3 (7,8) = 9

Ahora si calculamos la Función de Recurrencia o Recursiva:

fn* (xn) = Min [ fn (xn,dn) ]
fn* (xn) = Min [ costo (xn,dn) + f(n+1)* (dn) ]
f2*(3) = Min [ f2 (3,5) ]

I.
II. CASO PROBLEMA REEMPLAZO DE EQUIPO

Un fabricante de autopartes posee un torno con 2 años de uso. En la tabla se muestran las
estimaciones de mantenimiento, costo de reemplazo e ingresos producidos para un torno de iguales
características, en función de la edad de este.

No desea conservar ningún torno después de cumplir 6 años.

Se requiere determinar una política de reemplazo que maximice el beneficio total que proporciona
el torno durante los próximos 4 años.
Edad inicial del torno: 2 años.

Analizando el gráfico:
Las etapas del problema son cada uno de los próximos 4 años.
Los estados en cada etapa son las posibles edades de la máquina al inicio de cada año.
Las variables de decisión en cada etapa pueden definirse como las alternativas de conservar o
reemplazar el torno.
n=4
Estudiando la gráfica, podemos ver que al inicio de la etapa 4 la máquina puede tener 1, 2,
3 o 5 años. Cuatro años no puede tener, ya que si no la reemplazamos cuando tenía 2 años,
entonces se trata de la máquina con la cual iniciamos el análisis.

Analizando los resultados obtenidos correspondientes al estado X4 = 1:

Si la máquina tiene 1 año y decidimos conservarla, tendremos un ingreso de $9.000 y, como
gastos de mantenimiento, tendremos $500, lo que arroja un beneficio de $8.500
Si nuestra decisión es reemplazarla por la nueva, entonces vamos a comenzar el año con una
máquina de 0 años, la que nos dará un ingreso de $10.000 con un gasto de mantenimiento de $100;
pero además debemos contar con el costo de reemplazo, que es de $3.000. Esto resulta en un
beneficio neto de $6.900, siendo en este caso la decisión óptima conservar la máquina.

Con una lógica similar, se determinan los restantes resultados de la tabla.

n=3
Las edades posibles de la máquina son 1, 2, o 4 años.

El caso de que la máquina teng 1 año al inicio de la etapa 3:

Si la máquina tiene 1 año al inicio de la etapa y decidimos conservarla, tendremos un
ingreso de $9.000 con un gasto de mantenimiento de $500; a esto debemos sumarle el beneficio
óptimo de entrar al año siguiente (etapa 4) con una máquina de 2 años de antigüedad - que es
$8.300 -. El beneficio que tendremos si tomamos esta decisión será de $16.800.
Si la decisión es cambiarla, tendremos un ingreso de $10.000 con un gasto de
mantenimiento de $100 y con un costo por el reemplazo de $3.000; como vamos a comenzar el año
siguiente con una máquina de 1 año, le sumamos el beneficio óptimo correspondiente a este
estado para la etapa 4, es decir, $8.500. Obtenemos, en este caso, un beneficio de $15.400.
Observemos que siempre que conserva la máquina, entra en la otra etapa con una máquina
que tiene 1 año más. Igualmente, siempre que la decisión es reemplazar, entra a la siguiente etapa
con una máquina de 1 año de edad.

n=2

n=1

Para lograr el beneficio de $28.800 en los próximos 4 años, comenzando con una máquina de 2 años, la
empresa tiene 2 opciones.
La primera es conservar durante el primer año, reemplazar en el segundo año y conservar hasta el
final del 5to año.
La segunda opción plantea reemplazarla el primer año, reemplazarla en el segundo año y
conservar hasta el final del 5to año.
 TRANSPORTE, TRANSBORDO Y ASIGNACIÓN

TRANSPORTE

El problema de transporte se presenta cuando se planea la distribución de bienes o servicios desde

varios lugares de suministros y hasta varias ubicaciones de demanda. Por lo general, es limitada la cantidad de
bienes que están disponibles en cada ubicación de oferta - orígenes y los bienes se requieren en diversas
ubicaciones de demanda - destinos. El objetivo del problema es minimizar el costo total de transportar los
artículos desde los orígenes hacia los destinos.

Simbología
• Cij = costo unitario de envío desde el origen i al destino j.
• Cada origen tiene una disponibilidad u oferta, a la que vamos a denominar ai.
• Cada destino demanda una cierta cantidad, a la que llamaremos bj.

El objetivo es determinar qué cantidad de mercadería deberíamos enviar desde cada origen hacia cada
destino, de manera tal que el costo total del envío sea mínimo.

Modelo General de Transporte

Se representa mediante un conjunto de nodos en forma de red, con origen y destino.

o Sumatoria de las unidades de los orígenes

o Sumatoria de las unidades de los destinos
o Las fechas significan un costo unitario entre origen y destino

SUPUESTOS del modelo de Transporte:

⮚ Existe un conjunto de “m” o “h” orígenes conocidos con una oferta conocida
⮚ Existe un conjunto de “n” o “k” destinos conocidos con una demanda conocida.
⮚ La sumatoria de la oferta “ai” tiene que ser igual a la sumatoria de la demanda “bj”.
⮚ El flujo de producto es en un solo sentido, desde los orígenes hacia los destinos.
⮚ Los costos unitarios de transporte Cij son conocidos y permanecen constantes en el tiempo.
Planteo del problema:

1. Variables de decisión Xij = cantidad a enviar desde el origen i al destino j por semana
2. Objetivo: si yo estoy hablando de costos, el objetivo es minimizar el costo total semanal
3. Restricciones
I. Restricción por cada origen
II. Restricción por cada destino
4. Condición de no negatividad

MODELO:
𝑀𝑖𝑛 (𝑍) = 9𝑋11 + 7𝑋12 + 3𝑋13 + 2𝑋21 + 5𝑋22 + 8𝑋23
S.A
𝑋11 + 𝑋12 + 𝑋13 = 600 Restricción O1
𝑋21 + 𝑋22 + 𝑋23 = 700 Restricción O2
𝑋11 + 𝑋21 = 400 Restricción D1
𝑋12 + 𝑋22 = 500 Restricción D2
𝑋13 + 𝑋23 = 400 Restricción D3

Cantidad total de variables = m*n = 2*3 = 6

Cantidad de variables básicas = m + n -1 = 4

Variantes del Problema

Las variantes adicionales del problema básico de transporte pueden contemplar una o más de las
siguientes situaciones:

A. Oferta total distinta de la demanda total

Se pueden dar dos situaciones:

➔ Oferta > Demanda: Para equilibrar este problema, creamos un destino ficticio que recibe la
diferencia entre:

El costo de envío desde cada origen hacia ese destino ficticio es nulo. La o las variables
positivas que en la solución final aparezcan relacionadas con dicho destino indicarán dónde
quedó el excedente de oferta.

➔ Demanda > Oferta: Para equilibrar este problema, creamos un origen ficticio con una oferta
igual a la diferencia entre:
 El costo de envío desde este origen hacia cada uno de los destinos es nulo. La o las
variables positivas que en la solución óptima aparezcan relacionadas con dicho origen indicarán
los destinos que quedaron con demanda insatisfecha.

B. Función objetivo de maximización

En este caso, los coeficientes de la función objetivo representarán beneficios o contribución

unitarios a los beneficios; en cuanto a las restricciones, no sufren modificaciones.

C. Rutas inaceptables

Se eliminan del planteamiento de programación lineal a las correspondientes variables de

decisión.

MÉTODO DE RESOLUCIÓN DE PROBLEMAS DE TRANSPORTE:

Procedimiento de dos fases (similar al Simplex). En primer lugar, se requiere encontrar la solución factible
básica inicial y, después, se procede en forma iterativa a realizar mejoramientos en la solución hasta que se llega
a la solución óptima.

FASE I: Determinación de la Solución Factible Inicial

Para determinar la SFB inicial, que debe ser no degenerada, se pueden usar varios métodos:

a) Esquina noroeste
b) Mínimo costo
c) Vogel
d) Otros

FASE II: Mejoramiento de la Solución

Para cada variable básica, se plantea una ecuación:

Ui y Vi son variables auxiliares y tendremos una Ui para cada origen y una Vi para cada destino.

Se formará un sistema de ecuaciones indeterminado el cual se debe resolver con cualquier método.
El objetivo es encontrar un conjunto de valores para las Ui y las Vi que luego a su vez, permitan determinar
para cada variable no básica, un índice de mejoramiento que se calcula como:

Esto nos indica el incremento que se produce en el costo total, es decir, Z, ante un incremento unitario
de variable Xij. Es decir, cuánto crece el costo total si enviamos una unidad desde el origen i hasta el
destino j.
Como lo que queremos es minimizar el costo total, entonces:
• Si , la solución analizada es la óptima.
• Si algún índice da un valor δ < 0, entonces la solución no es la óptima y debemos determinar, al
igual que en el simplex, cuál es la variable que entra y cuál es la que sale de la base.
Tabla de Modelo Transporte:

En el lado derecho tenemos lo que puede producir cada origen (oferta), y la última fila representa lo que
demanda cada destino. Cada uno de los rectángulos representa una variable Xij (cantidades a enviar desde el
origen i al destino j). En el ángulo superior derecho se colocaran los costos de envío desde cada origen a cada
destino (cij).

Problema de transporte método ESQUINA NOROESTE:

1) Equilibrar el problema, es decir verificar que: (Fase I)

Como en este caso la sumatoria de ai = 140 > sumatoria de bi = 120, debe crearse un destino ficticio
(D3) con todos sus costos de envío (Cij) iguales a cero, y con un requerimiento de demanda igual a la diferencia
entre el total ofrecido y el total demandado.

Modificando la tabla quedaría así:

Cada celda representará a una Xij (cantidades a enviar desde el origen i al destino j), y en el ángulo superior
derecho se colocará el costo unitario de envío desde cada origen a cada destino (Cij).

2) Elegir método para encontrar una primer SFB no degenerada:

Utilizaremos el método de la esquina noroeste. Arrancamos en la primera celda superior izquierda.

Asignamos el mayor valor posible a la variable X11, teniendo en cuenta las restricciones de demanda y de
disponibilidad, es decir, la cantidad que el destino D1 requiere y la que el origen O1 tiene disponible para enviar.
Este valor es 45; quedando el origen O1 sin disponibilidad y el destino D1 con una necesidad de 45 unidades
más, que se le enviarán desde el origen O2. Una vez satisfecha la demanda del primer destino, pasamos al
segundo destino, cuya demanda es de 30 unidades. Como el origen O2 todavía dispone de 5 unidades, se las
enviaremos al D2, quedando aún una demanda insatisfecha de 25 unidades, las que recibirá desde el origen
O3. De esta manera, cada origen ha enviado todo lo que dispone y cada destino ha recibido todo lo solicitado.

Corresponde ahora controlar que la solución encontrada sea una SFB no degenerada, para la cual
contamos el número de variables positivas, las que, para este problema, debe ser : 3 + 3 - 1 = 5.

La solución factible básica inicial es:

X11 = 45 X23 = 0

X12 = 0 X31 = 0

X13 = 0 X32 = 25

X21 = 45 X33 = 20

X22 = 5

El valor de Z = 1030

Cada una de las variables positivas muestra la cantidad de mercadería a enviar desde el origen Oi al destino Dj,
a excepción de X33, que indica la mercadería que quedó sin enviar en el O3.

En la Fase II del método, debe verificarse si la solución encontrada es óptima; si no lo es, deberá determinarse
una variable que entra a la base y otra que sale.

3) Verificar optimidad (Fase II)

Se plantea para cada variable básica la siguiente ecuación:

Luego para cada variable no básica se calcula el índice:

Si estos índice de mejoramiento son todos mayores o iguales a cero, entonces la solución es óptima; de lo
contrario, deberá seleccionarse como variable de entrada a la que tenga el negativo más pequeño.
 Para seleccionar la variable que sale de la base, se procede con el siguiente razonamiento: Se determina
qué modificaciones deben hacerse en la solución actual si pretendemos enviar una unidad desde el O3 al D1,
respetando el conjunto restricciones de oferta y demanda. Con esta finalidad, colocamos un signo más en la
celda de la variable que entra y luego vamos compensando con sucesivos signos más y menos hasta cerrar el
circuito y solo afectando a variables básicas, como se muestra a continuación:

El valor máximo que puede asumir la variable que entra (X31) estará dado por el mínimo entre X21 y
X32, esto es, donde se colocaron signos menos. Es decir;

Para encontrar la nueva solución, se procede a actualizar la tabla, sumando y restando el valor de X31
en todas las celdas donde haya algún signo más o menos.

La variable que salió de la base fue X32.

El valor de Z puede calcularse como:

Esta nueva solución es:

Nuevamente hay que evaluar si esta solución puede mejorarse y el proceso se repite hasta que todos
los sigma sean mayor o igual a cero, momento en el que se habrá encontrado la solución óptima.

Determinamos la variable que sale de la base en la tabla 6:

La nueva solución es:

Verificamos si la solución encontrada es la óptima:

Como todos son mayores o iguales a cero, concluimos que es la óptima.

Problema transporte Método Mínimo Costo

Se parte de la celda con menor costo y se va asignando el mayor valor posible.

En este caso, sería la celda con costo de $7, y se asigna 1500. La demanda insatisfecha es de 1600.

El siguiente menor costo debería de ser el de $9, pero como del origen O3 no dispongo de nada. Sigo con el
costo menor siguiente, en este caso el de $11.

Siempre evitar que se asignen unidades a M.

TRANSBORDO

Un problema de transbordo es una generalización del

problema de transporte, en el cual aparecen nodos intermedios
llamados “nodos de transbordo” (ej: almacenes o depósitos)

El flujo de mercadería que circula entre los nodos puede

ser, desde los orígenes había los destinos, pasando o no, por
nodos de transbordo.

Se considera que el flujo de mercadería entrante en cada

nodo menos el flujo de mercadería saliente debe ser igual a cero.

En los nodos “origen” el flujo entrante de mercadería corresponde a la oferta de ese nodo, de igual
manera, en los nodos de destino, el flujo saliente esta representado por la demanda de ese destino.

Siendo los costos unitarios de transporte de las fábricas a los almacenes los siguientes:

Y los costos unitarios de transporte desde los almacenes a los distribuidores:

Considerando la numeración asignada a cada nodo en el gráfico y definiendo a las variables xij como la
cantidad de unidades a enviar desde el nodo i al nodo j, el modelo lineal para este problema es:

Los problemas de transbordo pueden modificarse fácilmente para poder ser resueltos con el método de
transporte. Sin embargo, hay otros métodos para resolver este tipo de problemas.
Formulación general del modelo:

xij = representa cantidad de unidades a enviar desde el nodo i al nodo j

representa que el flujo total que sale menos flujo total que
entra es igual a la oferta del nodo.

Además, si:
• Lj < 0 - nodo de demanda
• Lj > 0 - nodo de oferta
• Lj = 0 - nodo de transbordo

El modelo supone que oferta total = demanda total y cij ≥ 0.

Observación: Si todos los Lij y uij son enteros, el problema tendrá siempre una solución óptima con valores
enteros.
ASIGNACIÓN

Un problema de asignación es un caso especial de la programación lineal (generalmente de minimización) donde

es necesario asignar ciertos RECURSOS (MAQ O PERSONAS) para la realización de determinadas TAREAS O
ACTIVIDADES AL MENOR COSTO.

Objetivo: asignar “n” tareas a “n” máquinas a un mínimo costo.

• Las tareas son independientes y pueden realizarse en cualquier máquina.

• Cada tarea debe realizarse en una sola máquina – cada máquina 1 tarea.

Formulación

Si definimos a las variables como:

• Xij = 1, si la tarea i se asigna a la maquina j.

• Xij = 0 si la tarea i no es asignada a la maquina j.
• Cij = costo de asignar la tarea i a la maquina j.

Variantes del problema

1. Objetivo de Maximización: Al igual que en el problema de transporte, en este caso, los coeficientes
de la función objetivo representarán algún tipo de beneficio, monetario o no.
2. Número total de individuos diferente al número total de tareas: Si el número de individuos es
menor al número de tareas, deberán crearse tanto orígenes ficticios como individuos faltantes, con
un costo de asignación igual a cero. Por el contrario, si el número de tareas es inferior al número de
individuos, deberán crearse tantos destinos ficticios como tareas faltantes, con costo de asignación
igual a cero.
3. Asignaciones no aceptables: Se deben eliminar del problema lineal las correspondientes variables
de decisión.
4. Asignaciones múltiples: Se modifica la formulación del problema de la siguiente manera, si
representamos como ai al número de tareas que pueden ser asignadas al individuo i, la restricción
correspondiente será:
 Puede resolverse utilizando el método de simplex, o el método de transporte, pero debido a que las ofertas
y las demandas son todas iguales a uno, se ha desarrollado un algoritmo de resolución especial llamado Método
Húngaro.

Método Húngaro:

Este método trabaja a partir de la tabla de costos originales y mediante sucesivos cuadros, va reduciendo
los mismos hasta encontrar la asignación de costo mínimo.

Podemos resumir el método mediante los siguientes pasos:

1) Reducción por filas: Elegir el menor elemento de cada fila y restárselo a todos los valores de la fila.
2) Reducción por columnas: Elegir el menor elemento de cada columna y restárselo a todos los valores de
la columna. La matriz encontrada mediante estos dos pasos es una matriz de costos reducidos.
3) Cubrir los ceros de la matriz: Cubrir todos los ceros de la matriz con el menor número de líneas
(horizontales y verticales) posibles.
4) Prueba de optimidad: Si el número de líneas trazadas es igual al número de filas (columnas), se encuentra
entonces una solución óptima entre los ceros de la matriz. Si el número de líneas trazadas es menor a
m, volver a reducir la matriz, de acuerdo a lo explicado en el punto 5.
5) Reducción de la matriz: Seleccionar el menor número no cubierto por la línea y restárselo a los restantes
elementos no cubiertos y sumárselo a los elementos que se encuentran en las intersecciones de las
líneas.
6) Volver al paso 3

TEOREMA: “El número máximo de celdas cero independientes en una matriz de asignación reducida es igual al
número mínimo de líneas que cubren todos los ceros de la matriz”. En base a este teorema es que se plantea la
prueba de optimidad del método.

MINIMIZACIÓN

No se selecciona la tarea con menor costo, ya que se busca una minimización general.
En la tabla se observa los costos de realizar la tarea i en la máquina j.

FUNCIÓN OBJETIVO:

MIN Z= 5 X11 + 7 X12 + 9 X13 + 14 X21 + 10 X22 + 12 X23 + 15 X31 + 13 X32 + 16 X33

SUJETO A:

• Se tiene 1 restricción por cada tarea a asignar.

• Se tiene 1 restricción por cada máquina asignada.
 X11 + X12 + X13 = 1

X21 + X22 + X23 = 1 Cada tarea puede ser asignada a 1 sola máquina.

X31 + X32 + X33 = 1

X11 + X21 + X31 = 1

X12 + X22 + X32 = 1 Cada máquina puede ser asignada sólo a 1 tarea.

X13 + X23 + X33 = 1

X ij = 1, 0

A) De la tabla de costos identificar el MENOR costo de cada fila.

B) Generar una nueva matriz de costos, RESTANDO a todos los elementos de la fila el menor elemento de
ella (Pn). REDUCCIÓN POR FILA.

Q1=0 Q2=0 Q3=2

C) Generar una nueva matriz de costos, RESTANDO a todos los elementos de la columna el menor
elemento de ella (Qn). REDUCCIÓN POR COLUMNA.

D) Tachar con líneas los ceros de todas las filas y columnas. La cantidad de líneas debe ser IGUAL al tamaño
de la matriz.
Cuando no es Óptima, es decir, cuando el tamaño de la matriz no es igual a la cantidad de líneas: Se identifica
el MENOR de los no tachados:

1- Se los RESTA los no tachados.

2- Se los SUMA a en donde hay cruces.
3- Los que están en la línea quedan IGUAL.

Ahora si tachamos con líneas los ceros. Tendríamos 4 líneas. Estaríamos en el ÓPTIMO.

E) Asignación de la matriz. Asignar los ceros que sean ÚNICOS en cada fila o columna.

COSTO: P1 + P2 + P3 + Q1 + Q2 + Q3 = 5 + 10 + 13 + 0 + 0 + 2 = 30

COSTO MÍNIMO: 30
 UNIDAD 3: PROGRAMACIÓN DINÁMICA

La programación dinámica es un modelo de optimización que nos permite encontrar la solución de

problemas complejos, descomponiéndolos en una secuencia de problemas más pequeños y, de esta manera,
encontrar la combinación de decisiones que optimicen la efectividad global.

La secuencia u orden cronológico es hacerlo de atrás para adelante (desde la última hacia la primera).

Existen tipos de variables:

• Variable de ETAPA: Se trata de una variable ordenadora que representa cada uno de los subproblemas en
los cuales se divide un problema de PD.

• Variable de DECISIÓN (dn): Representa a las acciones posibles a tomar en la etapa n.

• Variable de ESTADO (Xn): Sirven de enlace entre las etapas, describiendo la condición en que se encuentra
el proceso al inicio de cada una de ellas. Estas variables son las más difíciles de identificar. Se debe
preguntar ¿Qué es lo que cambia de una etapa a otra?, ¿Qué información se necesita para identificar la
política óptima de aquí en adelante?, ¿Cómo se puede describir la situación actual?
Cantidad de dinero que disponemos en miles de $ para esta etapa de inversión

• Variable de RENDIMIENTO (fn): Rendimiento a obtener si disponemos de Xn pesos para esta etapa de
inversión, y las que siguen en etapas posteriores, sabiendo que se decide invertir Dn pesos en esta etapa.
Le añadimos un * a las decisiones y rentabilidades que representen los mejores valores.

Ejemplo:
Etapa 3:

En la columna x3 hemos colocado todas las

alternativas posibles de dinero disponible para
invertir.
En la columna d3* identificamos la mejor
decisión frente a cada estado. En este caso, por
ser la última etapa o último proyecto, se decidirá
invertir la totalidad del dinero disponible y, para
cada una de ellas, identificamos su resultado
como f3 esto es el rendimiento obtenido.

Etapa 2:

Es lógico pensar que lo

disponible menos lo invertido en
la etapa 2 es lo disponible para
invertir en la etapa 3.

Etapa 1:
Como estamos en la primera
etapa, tenemos disponibles
4000 para invertir, entonces
podemos decidir invertir entre 0
a 4 mil pesos en esta etapa.

Debemos determinar ahora la política óptima, es decir, la sucesión de decisiones que nos llevarán a obtener el
máximo rendimiento posible.

En la tabla de la etapa 1 vemos que la decisión óptima es invertir $1.000. Como teníamos $4.000, nos
quedan disponibles $3.000. Entramos en la tabla de la etapa 2 en el estado x2=3 y vemos que la decisión óptima
es invertir $2.000 en esta opción; después de esto, nos quedan $1.000 que los destinamos a la alternativa 1.
Una secuencia de decisiones determinada de antemano y que satisface las condiciones del problema se
llama una política.

Metodología:
A) Identificar el objetivo y variables que intervienen en el problema.
- Objetivo: Maximizar rendimiento total
- Etapas: cantidad de inversiones =3
- Estados: Dinero disponible para inversión al inicio de cada etapa
- Decisiones: Dinero invertido en cada etapa

B) Identificar, al inicio de cada etapa, cuáles son los estados posibles. Ej dinero disponible para realizar la
inversión.
 C) Calcular para cada combinación de un estado y una decisión el rendimiento obtenido (Fn), que es igual
al rendimiento de invertir $dn en esta etapa más el rendimiento óptimo de invertir $(Xn-dn) en las etapas
siguientes. La función aquí utilizada se denomina función recursiva.

D) Para cada estado, identificar cuál es la decisión óptima (d*) según el objetivo del problema, cómo
maximizar el rendimiento total.

Resolución:

1.
a. El problema se puede dividir en etapas que requieren una política de decisión en cada una de
ellas. En el ejemplo, las etapas estaban dadas por las diferentes alternativas de inversión. La
política de decisión fue elegir, en cada una, aquella que ofreciera mayor rendimiento.
b. Cada etapa tiene un cierto número de estados asociados a ella. Los estados asociados a cada
etapa era el dinero disponible para invertir.
c. La decisión de cuánto invertir en la opción actual determina el dinero disponible para inversión
en la siguiente alternativa analizada.

2. En el problema de inversión, se construyó una tabla para cada etapa (n) que prescribe la decisión
óptima (dn*) para cada estado posible (xn).
En cada etapa, tenemos como entradas el dinero disponible y las alternativas de cuánto invertir;
y como salida, el dinero disponible para la próxima etapa. Es decir que en cada etapa los estados al
inicio se determinaron como:

3. Entonces, se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada
la política óptima para la etapa n+1:

4. Y el rendimiento óptimo para la etapa n dado el estado Xn será:

 Cuando se usa esta relación recursiva, el procedimiento de solución se mueve hacia atrás etapa por
etapa, encontrando cada vez la política optima para esa etapa, hasta que encuentra la política optima desde la
etapa inicial.

Función de transformación por etapas

Las variables de estado de las sucesivas etapas se encuentran relacionadas a través de una relación
recursiva. El tipo de relación recursiva que existe entre dichas variables es la responsable de que no exista un
algoritmo de optimización único, como el simplex por ejemplo, sino que en realidad se trate de un enfoque para
resolver problemas de este tipo.
En esta relación recursiva, es de fundamental importancia la función de transformación por etapas, que
enlaza a las variables de estado de etapas sucesivas (xn, xn-1), permitiendo identificar a la variable de estado
xn-1 utilizando el valor de xn y la decisión dn.

Principio de optimidad de Bellman

“Una política óptima tiene la propiedad de que, independientemente de las decisiones tomadas para llegar a un
estado particular en una etapa particular, las decisiones restantes que dependen de esta deben también ser
óptimas.”

I. CASO PROBLEMA DE CAMINO MÁS CORTO

Tenemos 10 ciudades, en cada camino tenemos costos asociados, y tenemos que encontrar el menor
costo asociado. En el que en cada nodo aumenta los caminos posibles. Según donde estemos vemos hacia
dónde vamos.
Los subproblemas los llamamos etapas, en este caso tenemos 4 etapas diferentes. Los subproblemas están
relacionados. En cada instancia, en cada subproblema no necesariamente elegir el menor costo me va a llevar
al mejor camino.

El costo es lo que está sobre las flechas (f) y el costo acumulado es (f*)

1) Definimos las tres variables.

n: es la variable de etapa que representa las diferentes etapas en las que puedo estar. En este caso sería la
sección del viaje.

Dn (xn): es la variable de decisión representa la ciudad de destino en la etapa n.

Xn (sn): es la variable de estado representa a la ciudad de origen al inicio de la etapa n.

Tengo que tomar 4 decisiones que juntas forman una política óptima, que en este problema es minimizar el costo
total. Siempre resulta más fácil arrancar desde la última etapa, porque sabemos a dónde queremos llegar, y casi
siempre los problemas se tiene identificado el destino.

n=4
La última etapa es la trivial. Entonces resolvemos la última etapa para los posibles estados que tenga, una
vez que la tenga resuelta pasamos a la etapa anterior (n-1)

dn* es el destino óptimo en la etapa n.

fn* es el costo acumulado óptimo en la etapa n.

n=3
Estados posibles de origen son 5, 6 o 7, ahora no es trivial, entonces ahora si se va a tener más de una
ciudad de destino (d3) posible óptima. d3 puede dirigirse a la ciudad 8 u 9.

Se van analizando los problemas, interrelacionándolos entre ellos. Entonces el costo que se coloca en dn
es acumulado, por que la decisión de tomar el camino en 8 implica tomar el costo adicional de $3 para
llegar hasta el destino del nodo 10.

De la ciudad 6 se puede ir a la ciudad 8 o 9, tomando como costo: de ir de la ciudad 6 a la 8 un costo de

$6 más el costo adicional de $3 para ir de la ciudad 8 al destino final 10. Lo mismo se repite para cada
origen Xn (5,6,7).

Para la elección del destino óptimo d3*, de cada fila Xn de ciudad origen se elige el dn de menor costo y
ese es el destino elegido como posible óptimo (d3*) con su respectivo costo acumulado (f3*). Ej de la
ciudad origen 5, el destino de menor costo acumulado es el de la ciudad destino 8 con un costo de $4
contra $8. Por lo que se coloca en d3* = 8 y en f3* $4.
n=2
Los orígenes posibles son la ciudad 2, 3 o 4. Identificamos las decisiones que podemos tomar d2= 5,6,7
(destinos posibles).

Desde la ciudad 2 hasta la 5 tengo un costo de 7, pero como tengo que interrelacionar los problemas
tengo que sumarle 1 + 3, obteniendo un costo de 11.

Entonces elegimos el costo menor en el camino de 2 por 5, 6 y 7 y a partir de ahí, definimos cuál destino
elegimos, en este caso, podría ser 5 o 6 ya que ambos implican un costo de 11.

n=1
Va a haber una única fila, ya que es el único origen inicial. Similar a cuando es el único destino.

Política óptima

Una vez calculadas todas las etapas con sus respectivos costos acumulados, se arma la política óptima.

Desde la ciudad 1 elijo la ciudad 3 por que es una de las ciudades óptimas, luego elijo a la 5 me dice que
voy a 8, y de la 8 voy a 10.
Costo total de tomar este camino = 4+3+1+3=11

Ahora voy por el camino en donde en vez de ir por la 3 voy por la ciudad 4. Estoy en la ciudad 1, voy a la
4, voy a la 5 o 6, elijo la 5, la siguiente etapa voy a la 8 y luego a la 10.
Costo total de tomar este camino = 3 + 4 + 1 +3 = 11

Ahora voy por el camino en donde en vez de ir por la 3 voy por la ciudad 4. Estoy en la ciudad 1, voy a la
4, voy a la 5 o 6, elijo la 6, la siguiente etapa voy a la 8 y luego a la 10.
Costo total de tomar este camino = 3 + 2 + 3 + 4 = 12
Función de Recurrencia

Hay que identificar una función que represente todo el problema que se llama “función de recurrencia” (Fn*),
representa el problema completo.

Primero tengo que identificar la función de las tablas de forma generalizada:

Fn (xn,dn) = costo (xn,dn) + f(n+1)* (dn)

f3 (7,8) = costo (7,8) + f4*(8)

f3 (7,8) = 6 + 3
f3 (7,8) = 9

Ahora si calculamos la Función de Recurrencia o Recursiva:

fn* (xn) = Min [ fn (xn,dn) ]

fn* (xn) = Min [ costo (xn,dn) + f(n+1)* (dn) ]

f2*(3) = Min [ f2 (3,5) ]

 I.
II. CASO PROBLEMA REEMPLAZO DE EQUIPO

Un fabricante de autopartes posee un torno con 2 años de uso. En la tabla se muestran las estimaciones
de mantenimiento, costo de reemplazo e ingresos producidos para un torno de iguales características, en función
de la edad de este.

No desea conservar ningún torno después de cumplir 6 años.

Se requiere determinar una política de reemplazo que maximice el beneficio total que proporciona el
torno durante los próximos 4 años.
Edad inicial del torno: 2 años.

Analizando el gráfico:
• Las etapas del problema son cada uno de los próximos 4 años.
• Los estados en cada etapa son las posibles edades de la máquina al inicio de cada año.
• Las variables de decisión en cada etapa pueden definirse como las alternativas de conservar o reemplazar
el torno.
n=4
Estudiando la gráfica, podemos ver que al inicio de la etapa 4 la máquina puede tener 1,
2, 3 o 5 años. Cuatro años no puede tener, ya que si no la reemplazamos cuando tenía 2 años, entonces
se trata de la máquina con la cual iniciamos el análisis.

Analizando los resultados obtenidos correspondientes al estado X4 = 1:

Si la máquina tiene 1 año y decidimos conservarla, tendremos un ingreso de $9.000 y, como gastos
de mantenimiento, tendremos $500, lo que arroja un beneficio de $8.500
Si nuestra decisión es reemplazarla por la nueva, entonces vamos a comenzar el año con una máquina
de 0 años, la que nos dará un ingreso de $10.000 con un gasto de mantenimiento de $100; pero además
debemos contar con el costo de reemplazo, que es de $3.000. Esto resulta en un beneficio neto de $6.900,
siendo en este caso la decisión óptima conservar la máquina.

Con una lógica similar, se determinan los restantes resultados de la tabla.

n=3
Las edades posibles de la máquina son 1, 2, o 4 años.

El caso de que la máquina teng 1 año al inicio de la etapa 3:

Si la máquina tiene 1 año al inicio de la etapa y decidimos conservarla, tendremos un ingreso de
$9.000 con un gasto de mantenimiento de $500; a esto debemos sumarle el beneficio óptimo de entrar
al año siguiente (etapa 4) con una máquina de 2 años de antigüedad - que es $8.300 -. El beneficio que
tendremos si tomamos esta decisión será de $16.800.
Si la decisión es cambiarla, tendremos un ingreso de $10.000 con un gasto de mantenimiento de
$100 y con un costo por el reemplazo de $3.000; como vamos a comenzar el año siguiente con una
máquina de 1 año, le sumamos el beneficio óptimo correspondiente a este estado para la etapa 4, es
decir, $8.500. Obtenemos, en este caso, un beneficio de $15.400.
Observemos que siempre que conserva la máquina, entra en la otra etapa con una máquina que
tiene 1 año más. Igualmente, siempre que la decisión es reemplazar, entra a la siguiente etapa con una
máquina de 1 año de edad.
n=2

n=1

Para lograr el beneficio de $28.800 en los próximos 4 años, comenzando con una máquina de 2 años, la empresa
tiene 2 opciones.
• La primera es conservar durante el primer año, reemplazar en el segundo año y conservar hasta el final
del 5to año.
• La segunda opción plantea reemplazarla el primer año, reemplazarla en el segundo año y conservar
hasta el final del 5to año.

III. CASO DE PROGRAMACION DE LA PRODUCCION

Córdoba Autopartes SA quiere determinar la mejor política de producción y almacenamiento de uno de sus
productos para los próximos tres meses. Los datos disponibles para el trimestre se muestran en la siguiente
tabla:

Los productos que se fabrican durante un mes pueden servir para abastecer la demanda de ese mes o
de alguno futuro.
El costo de almacenamiento se calcula sobre la mercadería en inventario al inicio de cada mes,
actualmente existe un inventario de 10 unidades y la empresa desea que no exista inventario al final del trimestre.
La capacidad de almacenamiento es de 30 unidades.
Las corridas de producción se llevan a cabo en múltiplos de 10 unidades (es decir 10, 20 o 30 unidades).
Resolución del problema
En este problema se revisa el inventario al inicio de cada periodo de producción –mes– y, a continuación, se
decide cuánto producir ese mes.
Las características fundamentales son:
1. El problema se puede dividir en subproblemas, en cada uno de ellos debe tomarse una decisión. Cada
subproblema corresponde a una etapa en el proceso de resolución, en nuestro caso, un mes.
2. Al principio de cada mes, la empresa conoce la demanda durante ese periodo y debe determinar
cuántas unidades producir.
3. La capacidad de producción en cada mes es limitada.
4. Se debe cumplir con la demanda de cada mes, y esto puede hacerse con las unidades que se
produzcan durante el periodo y/o con las que están en inventario.
5. Existe una capacidad limitada de almacenamiento.
6. Las unidades que quedan en almacén al final de un periodo generan un costo que se carga por las
existencias de mercadería en inventario al inicio de cada mes. No se considerarán almacenadas en
cada etapa las unidades que se produjeran en esa etapa.
7. Los costos de producción y almacenamiento son diferentes en cada periodo.

Luego de este análisis, definimos el objetivo y las variables del problema.

• Objetivo: minimizar los costos totales –producción más almacenamiento– de satisfacer a tiempo la
demanda.
• Variables de etapa: cada uno de los próximos tres meses.
• Variables de decisión: las alternativas de decisión en la etapa i (di) estarán representadas por el
número de unidades a producir en cada mes.
• Variables de estado: para definir estas variables, nos preguntamos: ¿qué información necesitamos para
tomar decisiones factibles en la etapa actual sin reexaminar las decisiones que se tomaron en las
etapas anteriores?

Antes de construir los cuadros para cada etapa, analizamos cuáles pueden ser los estados posibles al inicio de
cada una de ellas, recordando que los estados al inicio de una etapa representan a los estados al final de la
etapa anterior.
En nuestro caso, el inventario al inicio de un mes en particular será igual al inventario al final del mes anterior.
Al inicio de cada mes, establecemos cuál es la cantidad mínima y máxima que puede haber en almacén
teniendo en cuenta la capacidad de inventario, la capacidad de producción y la demanda del mes anterior. Así:

Mes 1 (etapa 1)
• Inventario al inicio = 10 unidades
• Capacidad máxima de producción = 50 unidades
• Demanda = 50 unidades
Teniendo en cuenta estas tres restricciones, podemos decir que, partiendo de un inventario inicial de 10
unidades, produciendo a la capacidad máxima y con una demanda de 50 unidades, el número máximo de
unidades que pueden quedar al final del mes es 10.

Mes 2 (etapa 2)
• Inventario máximo al inicio = 10 unidades
• Capacidad máxima de producción = 40 unidades
• Demanda = 30 unidades
Analizando las condiciones de la etapa notamos que, si comenzamos el mes con el máximo posible de unidades
en inventario (10) y producimos a máxima capacidad (40), dado que la demanda es de 30 unidades, como
máximo nos pueden quedar 20 unidades al final del mes.

Mes 3 (etapa 3)
En este mes, iniciamos con 20 unidades en inventario como máximo y debemos tener presente que la empresa
no quiere inventarios al final del trimestre, es decir que Inventario Final = 0.

Recuerde que:
Inventario Inicial
xn = xn-1+dn-1-Dn-1
 RESUMEN INVESTIGACIÓN OPERATIVA 2DA PARTE
Introducción a la Teoría de la Decisión
Un proceso de toma decisión se presenta cuando, frente a un problema, existe más de una
alternativa o curso de acción posible, y conlleva a la elección de lo “mejor” entre lo “posible”.
En todo proceso de decisión intervienen dos actores, aunque en algunos casos la misma persona
asume los dos roles:
• Decisor: es quien tiene el poder y la responsabilidad de ratificar una decisión y asumir sus
consecuencias.
• Analista: es el encargado de estructurar el problema y ayudar al decisor a visualizarlo.

Tipos de teorías de decisión:

1. Teoría de la decisión con certidumbre

En general se tienen necesidades por satisfacer con cierto número de recursos limitados o
escasos y con el objetivo de lograrlo en forma óptima. A modo de ejemplo, esto significa la
búsqueda de un valor máximo cuando se trata de beneficios; o bien la búsqueda de un mínimo
cuando se trata de costos o esfuerzos a desarrollar

2. Teoría de la decisión con incertidumbre o riesgo

Se analiza la toma de decisiones con aleatoriedad o incertidumbre en los resultados, de modo
que las consecuencias de una decisión no están determinadas de antemano, sino que están
sujetas al azar

3. Decisión Multicriterio
Si bien dada una decisión sus consecuencias están perfectamente determinadas, lo que no
está definido tan claramente es qué es lo mejor, existiendo varios objetivos en conflicto.

4. Teoría de juegos
Las consecuencias de una decisión no dependen únicamente de la decisión adoptada, sino,
también de la que elijan otros jugadores

Proceso de Toma de decisiones: Así, la toma de decisiones se inicia al identificar y definir el problema,
y termina con la elección de una alternativa, que es el acto de tomar una decisión.

1. Definición del problema

2. Identificación de Alternativas
3. Determinación de criterios
4. Evaluación de alternativas de solución
5. Selección de la mejor alternativa
6. Implementar la decisión
7. Evaluar los resultados
 • Problemas de decisión de criterio único o monocriterio: Interviene solo un criterio u objetivo en
el proceso
• Problemas de decisión Multicriterio y Multiobjetivo: se implican mas de un criterio de decisión.

ELEMENTOS:

Conjunto de Alternativas (X)

Son las variables de decisión del problema, representan acciones o alternativas de decisión.

Al conjunto de las alternativas posibles lo denominaremos X. Este conjunto está formado por un
numero finito de elementos Xi es decir, X= (X1, X2, X3… Xn) siendo n el número de alternativas de
decisión.

Son todas las alternativas posibles, entre las cuales debemos elegir un elemento particular xj, tal
que el mismo sea preferible o a lo sumo indiferente a cualquier otro del conjunto, deberemos haber
previamente definido una relación que me permita decir, por ejemplo, que x1 es preferible a x2 o
viceversa o ambas son indiferentes.

Función de decisión d(x)

• Si esta función mide algo deseable, como un beneficio o un ingreso a los fines de seleccionar
la mejor alternativa, la decisión optima es Máx d(x)
• Si la función mide algo no deseable, como un costo o pérdida, con el fin de seleccionar la
decisión óptima es Mín d(x)

Estados de Naturaleza
A menudo los resultados que se obtienen al seleccionar una alternativa se ven condicionados
por la presentación de ciertos sucesos que no dependen del tomador de decisiones, estos son “estados
de la naturaleza” que pueden modificar los resultados de la acción seleccionada.
Se representan como el conjunto Y siendo Y = {y1, y2, ……, ym}. Siendo m el numero de estados de
naturaleza.

Compensaciones
Son consecuencias o resultados cij que surgen de
la elección de la alternativa Xi cuando la naturaleza
presenta el estado Yj. Cada vez que el decisor elige un
elemento xi del conjunto X, se presenta, un elemento
particular yj del conjunto Y, tal que el par ordenado
(xi,yj) determina un resultado o compensación c(xi,yj).
Las compensaciones miden el grado de satisfacción que le produce al tomador de decisiones el
hecho de seleccionar una alternativa Xi cuando se presenta un estado natural Yj.
Cuando el número de compensaciones es finito, los resultados se los puede resumir en forma
matricial, en una matriz de compensaciones.
Relaciones de preferencia
Este establece relaciones entre los elementos del conjunto, de forma tal que para cualquier par
de elementos propondremos decir si uno es preferible o indiferente al otro.

Universos: Ambientes de decisión

Como el decisor no controla el valor que asumirá yj, deberá contar con algunos elementos
adicionales que informen sobre el comportamiento de los estados de la naturaleza y le permitan
construir una función de decisión d(x), esa información disponible se puede representar en “Universos”.
Dependiendo de la disponibilidad de la información, se organizan los problemas de decisión en
cuatro universos:
1. Universo cierto: Decisiones con certidumbre
2. Universo aleatorio: Decisiones con riesgo
3. Universo Incierto: Decisiones con incertidumbre
4. Universo Hostil: Decisiones en entornos competitivos

1. UNIVERSO CIERTO
En este ambiente, quienes toman la decisión saben con certeza la consecuencia de cada
alternativa o decisión a seguir. Se tiene la información completa y precisa. Se conoce toda la
información necesaria para la toma de una decisión. Naturalmente, los decisores escogen la
alternativa que maximizará su compensación o con la que se obtendrán mejores resultados.
En este universo se conoce con exactitud cual es el estado de la naturaleza que se
presentara ante determinadas circunstancias, es decir, que el decisor conoce la compensación
c (x, y) que obtendrá por depender únicamente de x.

Función de decisión d(x) = c (x, y)

Decisión Optima: Conocida la función de decisión d(x) se deberá encontrar el valor de x que la
optimice, para lo cual, en el caso más sencillo bastará con reemplazar en d(x) cada posible valor
del vector x y seleccionar como decisión optima aquel elemento que le de el mejor valor a d(x).
2. UNIVERSO ALEATORIO (Esperanza Matemática)
La información disponible no es suficiente o puede obtenerse con cierto margen de
incertezas, debiendo ser reflejada esta situación mediante una distribución de probabilidad, es
decir, se conoce la probabilidad de ocurrencia de cada uno de los estados de naturaleza.
De esta manera, surge como natural usar, como función de decisión, el valor esperado de
las compensaciones ante cada decisión posible.

La función de decisión d(x) es entonces la Esperanza Matemática de las compensaciones.

La decisión optima será:

• En el caso de compensaciones deseables (beneficios o ingresos)

La decisión óptima es la alternativa x3 por que ofrece el mayor beneficio esperado, en este caso de $151

• En el caso de compensaciones indeseables (perdidas o costos)

La decisión óptima es la alternativa x3 por que ofrece el menor costo esperado, en este caso de $ 120

Criticas de la esperanza matemática:

1. Debería incorporarse alguna medida de dispersión de las compensaciones como podría ser
la desviación estándar, ya que es un problema cuando aparecen valores similares de la
esperanza matemática para distintas alternativas.
Por ejemplo: Dos proyectos de inversión tienen
una esperanza matemática de $150, no obstante,
el proyecto b tiene mayor dispersión respecto a
ese valor, pudiendo obtener rentas muy superiores
e incluso entrar en pérdidas.

2. El valor de la esperanza matemática se vuelve significativo solamente cuando la decisión se

repite un numero grande de veces, en cuyo caso el promedio de los resultados tendrá un
valor tanto más próximo al de la esperanza matemática. Por el contrario, si la decisión debe
tomarse por única vez, el criterio debe aplicarse con cautela, ya que podría conducir a una
elección equivocada.
3. UNIVERSO INCIERTO
Se presenta cuando no conocemos la distribución de probabilidad de los estados de la
naturaleza. Para estos universos existen distintos criterios racionales de decisión.
Una característica fundamental de los criterios bajo condiciones de incertidumbre se refiere a
que un mismo problema con diferentes enfoques del análisis de decisiones puede tener varias
soluciones.
No es posible decir que un criterio sea mejor que otro, el decisor deberá utilizar el que considere
el más adecuado según el problema, teniendo en cuenta las desventajas de cada uno de ellos.

Criterios de decisión
1. WALD – PESIMISMO
Este criterio se basa en evitar perdidas elevadas o inaceptables. De esta manera, debemos
colocarnos en la situación mas desfavorable ante cada alternativa de decisión y luego elegir
entre ellas la mas favorable. En caso de beneficios, a este modelo se lo conoce como criterio
maximin; y en el caso de costos, como el criterio minimax.
Beneficio = MAXIMIN
Costo = MINIMAX
Procedimiento
a. Determinar el resultado más desfavorable para cada alternativa de la función de decisión
d(x)

b. Seleccionar el que nos proporcione el mejor valor para d(x). La alternativa asociada con
este resultado es la decisión optima.

Criticas del criterio:

Al considerar solamente las situaciones mas desfavorables que pueden presentarse y
dejar de lado las restantes, en algunos casos, puede conducir a decisiones poco racionales.
Por ejemplo: hay dos alternativas de tamaño de una nueva planta industrial, cuyos
resultados dependerán de la situación económica del país en los próximos 10 años.
 De acuerdo con el criterio se deberá construir la planta I, sin embargo, es indudable que
muchos decisores en situaciones similares no dudarían en escoger la alternativa II.

2. HURWICZ – PESIMISMO RELATIVO

Este criterio supone que el decisor no es completamente pesimista o totalmente optimista y

que el grado de optimismo se puede medir a través de un coeficiente de optimismo α que está
comprendido entre 0 y 1, con lo cual el nivel de pesimismo queda definido a través de su
complemento (1 - α).

Dato: Observe que si α = 0, entonces el criterio es el de Wald; por el contrario, si α = 1,

estaremos ante un optimismo total.

Se define a través de este coeficiente la función de decisión d(x) como un promedio

ponderado entre el mejor y el peor resultado que corresponde a cada alternativa de decisión.

Entonces la decisión optima se obtiene calculando:

 Critica al criterio:
Considera solamente situaciones extremas (más y menos favorables) perdiendo
información sobre los valores intermedios de las compensaciones.

Sensibilidad del coeficiente de optimismo α:

El cálculo de la sensibilidad de este coeficiente supone determinar los puntos en los
cuales las alternativas son indiferentes.

Observemos que el
punto de indiferencia
entre las alternativas
X2 y X3 es 0,3334.
Para valores
superiores, la
alternativa X2 es
preferible a X3,
también podemos
observar que X1
nunca seria elegida
bajo el criterio de
Hurwicz.

3. SAVAGE – MÍNIMO ARREPENTIMIENTO

Savage pone en duda si realmente las compensaciones c (x, y) miden la satisfacción que
le produce a un individuo tomar una decisión y que se presente determinado suceso. Es así
como plantea medir el grado de satisfacción a través de lo que “deja de ganar por no haber
elegido la alternativa correcta frente a ese estado natural”
Se debe construir una nueva matriz a partir de la matriz de compensaciones, esta se
llama “matriz de los lamentos o arrepentimientos” y muestra los costos de oportunidad de
no haber seleccionado la mejor decisión ante cada posible estado de la naturaleza. Para
elegir la mejor alternativa, Savage aconseja aplicar el criterio de Wald para costos a la matriz
de los lamentos.

Cada elemento Rij de la matriz de los lamentos:

En este modelo, quien toma las decisiones busca evitar perdidas elevadas de oportunidad
a través de un análisis minimax de la matriz de lamentos. Al hacer esto, se minimiza la
diferencia máxima que puede ocurrir entre la mejor alternativa para un estado de la
 naturaleza determinado y cada uno de los resultados, es decir, se asegura minimizar el
arrepentimiento máximo.

Función de decisión:

Entonces la decisión optima será:

4. LAPLACE / LAGRANGE (PROMEDIO)

Este criterio le asigna igual probabilidad de presentación a cada estado de naturaleza. De
esta manera, si m es el numero de estados naturales, la probabilidad de presentación de cada
uno de ellos será 1/m. Luego, utilizando estas probabilidades, se procede de igual manera que
en un universo aleatorio.

La función de decisión será:

La decisión óptima para este criterio se calcula como:

Critica al criterio:
Se basa en el grado de subjetividad al considerar como igualmente probables a todos los
estados naturales. En ese sentido, podría el decisor asignar diferentes probabilidades a los
estados naturales basándose en su experiencia, conocimientos previos o intuición, por ejemplo.
Además, se pueden hacer las mismas criticas que las realizadas a la utilización del valor
esperado (universo aleatorio).
 4. UNIVERSO HOSTIL – TEORÍA DE JUEGOS
Se trata de un universo de decisión donde la ocurrencia de alguno de los estados de naturaleza no
se produce al azar, sino por elección de un opositor inteligente que a fin de obtener su mayor beneficio
procura hacerle al decisor el mayor daño.

Un juego incluye dos o más tomadores de decisión que buscan maximizar sus ganancias. El
resultado del juego depende de las acciones que toma cada uno de los jugadores.

Conceptos básicos
1. La característica básica es que el resultado final depende de la combinación de estrategias
seleccionadas por los adversarios.
2. El caso más simple es el juego de dos personas de Suma Cero, denominado así porque todo lo
que gana un jugador es lo que pierde el otro tal que la suma de sus ganancias netas es cero
Estrategia Pura: es un plan previamente determinado, que establece la secuencia de
movimientos y contra movimientos que un jugador realiza durante un juego completo.
3. Un juego de dos personas se caracteriza por:
a) Las estrategias del Jugador 1
b) Las estrategias del Jugador 2
c) La Matriz de Pagos
4. Antes de iniciar el juego, cada adversario conoce las estrategias que dispone, las que dispone
su oponente y los valores de la matriz de pagos
5. Una jugada real consiste en que los dos jugadores elijan al mismo tiempo una estrategia sin
saber cuál es la elección de su oponente
6. El objetivo primordial de la Teoría de Juegos es que ambos jugadores eligen sus estrategias para
promover su propio bienestar.

Tipos de Juegos:

• Número de jugadores: de dos o más jugadores

• Suma algebraica de todos los pagos
➢ Suma cero: lo que gana un jugador el otro lo pierde
➢ No suma cero: lo que gana un jugador no necesariamente lo pierde el otro
• Numero de estrategias o acciones posibles: de dos o más estrategias
• Juego de Estrategia Pura: cada jugador tiene una y solo una estrategia optima
• Juego de Estrategia Mixta: carecen de estrategias optimas
• Juegos Cooperativos: Los jugadores pueden comunicarse entre ellos y negociar los resultados
• Juegos no Cooperativos: Los jugadores no tienen la posibilidad de comunicarse para llegar a
acuerdos previos.
• Juegos repetidos: Un grupo dijo de jugadores juega repetidamente y tienen en cuenta el
resultado de las jugadas anteriores antes de hacer la siguiente jugada.
DOS JUGADORES Y SUMA CERO:

Todo lo que pierde o gana un jugador lo gana o pierde el otro respectivamente. Se asume
que la decisión de un jugador es efectuada con total desconocimiento de la jugada que efectúa el
oponente. Es por esto que se utiliza el criterio pesimista extrayendo las peores consecuencias de
cada decisión y eligiendo de entre todas ellas a la mejor.

La matriz de compensaciones ahora se llama “matriz de pagos” y se obtiene considerando

al decisor como si fuera un jugador (jugador I) con todas sus estrategias y el universo fuera
reemplazado por el oponente (jugador II) representando lo que antes eran los estados de
naturaleza.

Las estrategias del jugador I son las filas y las estrategias del jugador II son las columnas.

Dominancia:
Existe dominancia de una estrategia A1 sobre otra A2, cuando todos los resultados de la
estrategia A1 son preferibles o indiferentes a los resultados de la estrategia A2,
independientemente de lo que haga el oponente.
Si una estrategia An está dominada por las restantes estrategias del jugador, puede ser
eliminada de la matriz de pagos y de esta manera reducir el tamaño de la matriz de pagos.

La matriz de pagos se construye de manera

que los pagos son las ganancias del jugador I y las
pérdidas del jugador II, entonces el jugador I elegirá
el máximo de los mínimos (criterio maximin) y el
jugador II elegirá el mínimo de los máximos (criterio
minimax).

Estrategia Pura Optima

Si la elección hecha por ambos jugadores recae en el mismo par (x,y) el juego tiene punto
de equilibrio. Esta dará como resultado el pago que recibirá el jugador I (que también podrá ser
una pérdida y entonces llevará signo negativo) por parte de su oponente (que será ganancia para
este si lleva signo menos). En este caso, al valor del pago, ubicado en la intersección de la fila
maximin y la columna minimax, se lo designa “valor del juego” (V), porque si ninguno comete un
error siempre el juego se resolverá de esa forma, ya que le garantiza al jugador I tener como mínimo
ese beneficio y al jugador II tener como máximo esa perdida, en caso de que el punto de equilibrio
tenga valor CERO se lo designa “Juego Justo”
 Decimos que a cada jugador le conviene jugar una estrategia única, que justamente es la
indicada por el criterio de Wald aplicado a ambos jugadores. Cuando el juego se resuelve con
una estrategia única se lo denomina “juego con estrategia pura óptima”, en caso de no tener un
punto de equilibrio, se utilizan “estrategias mixtas”

Estrategias Mixtas
Siempre que un juego no tenga punto silla, la Teoría de Juegos establece que cada jugador
debe asignar una distribución de probabilidad sobre su conjunto de estrategias.
El objetivo es determinar una estrategia mejor para cada jugador, bajo la consideración de que
el oponente es racional y realizará movimientos inteligentes en contra

En esta situación el juego puede ser resuelto si se admite la realización de varias jugadas
donde cada jugador puede efectuar varias decisiones alternando las posibles estrategias.
Sea:
pi = probabilidad de que el jugador 1 use la estrategia i (i = 1,2,…,m)
qi = probabilidad de que el jugador 2 use la estrategia j (j = 1,2,…,n)
Donde n y m son el número de estrategias disponibles.
 Así, cada jugador especifica su plan de juego asignando valores de probabilidad a (p1, p2, …,
pm) y a (q1, q2, …, qn). Estos planes se denominan ESTRATEGIAS MIXTAS y las originales (sin
valor de probabilidad) son las ESTRATEGIAS PURAS.

el valor de juego se obtiene cuando:

Ejemplo:

El jugador 1 elige las estrategias mixtas (p1, p2, p3) = (½, ½, 0). Para el jugador 1 esto significa
que da igual oportunidad a las estrategias puras p1 y p2, pero descarta la p3 por tener la mayor
pérdida y además está dominada por la estrategia 2.
El jugador 2 elige (q1, q2, q3) = (0, ½, ½). Descarta la estrategia 1 porque representa su mayor
pérdida, pero asigna igual probabilidad a q2 e q3.
Entonces, teniendo ½ de probabilidad para cada estrategia de cada jugador, es válido lanzar una
moneda al aire, pero para resolver se hace necesario que en estrategias mixtas: Máximin = miniMáx
para estabilizar la solución.

(Se recordará que cuando Máximin > miniMáx el juego no tiene punto silla, la solución es inestable
y los jugadores querrán cambiar sus planes para mejorar su condición).
 5. TEORÍA DE BAYES – ARBOLES DE DECISION
Un árbol de decisión es una forma gráfica y analítica de representar todos los eventos que pueden
surgir a partir de una decisión asumida en cierto momento. Ayuda a tomar la mejor decisión desde un
punto de vista probabilístico ante un abanico de posibles soluciones.
Una de las ventajas es que el decisor es forzado a examinar todos los resultados posibles,
incluyendo los desfavorables. El decisor es forzado a hacer decisiones de una manera lógica y
secuencial.
Los nodos de un árbol de decisión representan las decisiones, los eventos fortuitos y las
consecuencias. Los rectángulos o cuadrados representan los nodos de decisión; los círculos u óvalos
los nodos fortuitos o estados de la naturaleza, y los recuadros en las hojas del árbol representan los
nodos de consecuencia o compensaciones posibles.

• Nodo de decisión: Indica la necesidad de tomar una decisión en ese momento del
proceso

• Nodo de probabilidad: Indica el punto del proceso en el que ocurre un evento

aleatorio (estado de naturaleza)

• Rama: nos muestra los distintos caminos que se pueden emprender

Pasos para el árbol de decisión

1. Definir el problema
2. Dibujar el árbol de decisión
3. Asignar probabilidades a los eventos aleatorios
4. Estimar los resultados para cada combinación posible de alternativas
5. Resolver el problema obteniendo como solución la ruta que proporcione la política optima.
Primero hay que disponer de la información de las compensaciones correspondientes:

Método Tabular
 Se dibuja el árbol de izquierda a derecha, partiendo de la primera decisión que es consultar o no
consultar, la parte superior que corresponde a no consultar, se continúa en dos decisiones posibles de
las cuales salen las alternativas correspondientes a los estados de la naturaleza posibles.

Por la parte inferior se continúa con los dos (pueden ser más) resultados posibles de consultar
(ESTUDIO) y a continuación las correspondientes decisiones y estados que pueden aparecer, que son
idénticos a los de la parte superior.

Los cuadros de extrema derecha representan las compensaciones reales que se obtendrían de
tomar una de las decisiones y que se produzca uno de los estados probables. El tercio superior
representa la decisión sin información extra y los dos tercios inferiores representan la decisión con
información extra, por lo tanto, los resultados de éstos últimos deben ir afectados del costo de dicho
estudio.

Sobre cada rama de estado probable se coloca el valor de su probabilidad, lo que multiplicado por
el correspondiente resultado que se encontrará a la derecha, dará su contribución a la Esperanza
Matemática; luego sumadas todas las ramas que concurren a un círculo se obtiene el valor de
Esperanza Matemática (E) correspondiente a esa decisión el que se coloca en ese círculo.

Se sigue avanzando de derecha a izquierda, al encontrar un cuadrado quiere decir que corresponde
a una alternativa de decisión y como se decide por la Esperanza Matemática, se coloca allí el valor
correspondiente a la rama que maximiza (o minimiza, según el sentido de la optimización) la Esperanza.

Se continúa así hacia la izquierda llenando todo el árbol, recordando que los cuadrados representan
situaciones de decisión y los círculos situaciones aleatorias no gobernadas por el decididor. Si el costo
de la prueba se conoce de antemano, se podrá llegar al último cuadrado de la izquierda y conocer el
valor esperado total y los valores esperados con y sin la prueba y la correspondiente decisión más
conveniente.
INFORMACION
Como sabemos, que nos den información perfecta no implica un cambio en las probabilidades,
por lo que los estados de la naturaleza seguirán teniendo la misma probabilidad de presentación,
aunque ahora se podría elegir la mejor alternativa ante cada uno de los resultados posibles.

(En caso de problemas de Maximización)

La función de decisión sin información adicional, es decir, tener información imperfecta (valor
esperado con probabilidades)

VE info imperfecta= Σi [c(x,yi) * P(yi)]

La función de decisión con inf. Perfecta se podría elegir la mejor alternativa ante cada una de
las decisiones posibles y luego considerar el valor esperado.

VE info perfecta= Σi [ Max X c(x,yi) * P(yi)]

Entonces el VALOR DE LA INFORMACIÓN PERFECTA (VIP) es la diferencia entre el valor esperado

con los mejores resultados y el valor esperado con información imperfecta, representando la mejora
que podría haber en las utilidades o pagos y será:

VIP= VE info perfecta – VE info imperfecta

Valor información perfecta = Resultado info perfecta - Resultado Info imperfecta

Información extra (pagar por ESTUDIO):

Valor bruto = VE7

Valor neto = VE7 – costo del estudio

Valor información extra = Valor neto – VE s/info extra

 6. DECISIÓN MULTICRITERIO o MULTIOBJETIVO
Surge para afrontar específicamente situaciones en las que un decisor debe resolver un problema
en el cual son diversos los objetivos que se pretenden alcanzar simultáneamente. Es un problema de
optimización con varias funciones objetivo simultaneas.

En este tipo de problemas, es prácticamente imposible que exista una alternativa o solución (es
decir un valor concreto del vector x) para el cual alcancen su valor optimo, simultáneamente, todas y
cada una de las funciones objetivo.
Suele ocurrir que una solución sea mejor que otras en alguno de ellos, mientras que para los
restantes objetivos, sea superada por otras soluciones. En estos casos el decisor elegirá la mejor entre
un conjunto de alternativas consideradas por él, satisfactorias.
Ramas del multicriterio:

• Decisión multiobjetivo: problemas con objetivos múltiples, en los cuales las alternativas pueden
tomar un numero infinito de valores.
• Decisión multicriterio discreta (DMD): El conjunto de alternativas de decisión esta formado por
un numero finito y generalmente pequeño de variables.

DECISIÓN MULTICRITERIO DISCRETA

Es una metodología de toma de decisiones útil en una gran cantidad de campos de
aplicación, cuando hay que decidir entre varias alternativas teniendo en cuenta diversos
objetivos o puntos de vista, generalmente en conflicto.

Conjunto de elección: El decisor se enfrenta a un conjunto finito y discreto de

alternativas, conocido como conjunto de elección, al que denominaremos A= (A1, A2,
A3…Am). Suponemos que las alternativas son diferentes, exhaustivas y excluyentes.

• Exhaustivas: si se introduce una nueva alternativa al conjunto de elección, se deberá

plantear nuevamente el modelo.
• Excluyentes: no se admite la elección de una solución mixta.
Conceptos básicos:

• Atributos
Para realizar la elección entre alguna de las alternativas del conjunto de selección, se supone
que el decisor posee varios ejes de evaluación. Estos ejes de evaluación son los elementos que
direccionan el análisis y se deben establecer con base en la modelización de las consecuencias,
de manera que representen las dimensiones del problema. A partir de estos ejes es posible
hacer comparaciones entre las alternativas. Dichos ejes son los atributos, que representan
propiedades, características, capacidades de satisfacer necesidades y/o deseos, que poseen
las alternativas, aunque en diferentes cantidades o intensidades.

• Criterios
Cuando a esos atributos se les agrega información relativa a las preferencias del decisor, de
tal manera que proporcionan un conjunto de reglas que permiten comparar las alternativas con
respecto a un atributo, se dice que ese conjunto de reglas representa un criterio de decisión.
Entonces un criterio es una función que refleja las preferencias del decisor en relación con un
atributo.
Denominaremos el conjunto de todos los criterios como C = (C1, C2, …, Cn). Suponemos
siempre que C es un conjunto finito y discreto.
Propiedades de los criterios:
✓ Exhaustividad: Se deben considerar todos los criterios necesarios que permitan la
discriminación entre alternativas
✓ Coherencia: Las preferencias del decisor deben ser coherentes con las preferencias en cada
criterio.
✓ No redundancia entre criterios: si no se la tienen en cuenta, se corre el riesgo de otorgar
duplicada importancia a un atributo.
Se aconseja trabajar simultáneamente con menos de 20 criterios en una misma decisión,
por la dificultad de percibir las características más significativas del problema de decisión en una
visión global del mismo. También en el caso de tener gran numero de criterios, se aconseja
estructurarlos en una jerarquía de criterios y subcriterios.

• Matriz de decisión
Suponemos que el decisor es capaz de dar, para cada uno de los criterios
considerados y para cada alternativa del conjunto de elección, un valor numérico aij, que
expresa una evaluación de la alternativa Ai respecto al criterio Cj.
Se pueden resumir estas evaluaciones bajo la
forma de una matriz A=(aij) en la cual cada fila expresa
las cualidades de la alternativa i respecto de los n
atributos considerados, mientras que cada columna j
recoge las evaluaciones que el decisor hizo de todas las
alternativas respecto al atributo j. De esta manera un
elemento genérico aij de la matriz, indica la evaluación
de la i-ésima alternativa respecto al j-ésimo atributo.
 • Tipos de problemas
▪ Problema tipo α: seleccionar la mejor alternativa
▪ Problema tipo β: Clasificar las alternativas en buenas y malas. Aceptar las buenas y
rechazar las malas.
▪ Problema tipo γ: generar un ordenamiento de las alternativas
▪ Problema tipo δ: realizar una descripción de las alternativas
Estos tipos de problemas no son independientes entre sí, ya que uno puede servir para otro.

Preferencias del decisor: El tomador de decisiones, frente a dos alternativas A1 y A2 que pertenecen
al conjunto de elección, es capaz de decir cual prefiere:
1. Prefiere A1 a A2: se denota como A1 > A2 (> significa “estrictamente preferido a”)
2. Es indiferente entre A1 y A2: se denota como A1≈A2 (≈ significa “indiferente a”)
3. No sabe si prefiere A1 a A2 o si le resultan indiferentes (preferencia débil): se denota como A1
≥ A2 (≥ significa “es preferida o indiferente a”)
GESTIÓN DE STOCK
El objetivo de la administración de inventarios es determinar reglas que puedan aplicarse para
reducir al mínimo los costos relacionados con el mantenimiento de existencias de mercadería y, al
mismo tiempo, poder cumplir con la demanda.
Los modelos de administración de inventarios responden las siguientes preguntas:

• ¿Cuánto se debe pedir de un producto?

• ¿Cuándo se debe hacer el pedido?
Cada modelo de inventario contempla una realidad diferente, entonces se debe seleccionar el
modelo correcto de acuerdo con sus características, como la política de administración de inventarios
y los elementos mas importantes que la componen como:
• Características de la demanda.
• Costos relevantes.
• Posibilidad de admitir faltantes en almacén.
• Retrasos en el ingreso de los pedidos.
• Precio del producto.
• Posibilidad de aceptar pedidos pendientes.
• Modalidad de ingreso del pedido.
Supuestos del modelo: Es muy importante, al momento de utilizar un modelo de inventarios en
particular, conocer las hipótesis o supuestos que lo sustentan, ya que, si alguno de estos variara, el
modelo ya no sería válido.

1. Política de Inventario

Gráfico: En el eje de abscisa se representa el tiempo

y en el de las ordenadas, la cantidad de unidades
almacenadas.
En los momentos 0, t0, t1 se tienen S unidades
almacenadas, luego, a medida que pasa el tiempo,
esa cantidad va disminuyendo.

Punto de reorden: el momento en el que deben realizarse los pedidos está determinada por un nivel
mínimo de inventario x, llamado punto de renovación de pedido o nivel de reorden. Este nivel de
inventario nos indica el momento de realización del pedido, lo que hace que la periodicidad sea variable.
Existen varias formas de administrar un inventario, algunas de ellas son:

Política de pedidos con cantidades fijas por periodos

variables:

La cantidad fija que se repone (q) estará dada por S - x, la

cual ingresa en forma instantánea. Tiene la ventaja de
evitar que se produzcan faltantes de stock, pero es difícil
prever el momento en que se debe efectuar el pedido

Política de pedidos con cantidades variables por periodos

fijos:

En este caso, sabemos exactamente el momento en el

que hay que hacer un pedido (t1, 2t1). Sin embargo, la
cantidad a pedir dependerá del stock existente en ese
momento. Es decir que se realizan pedidos en periodos de
tiempo fijos, pero con cantidades variables.

2. Características de la demanda: La demanda puede ser determinista o aleatoria. Al considerar

que la demanda es determinista, implícitamente se está suponiendo que ella es perfectamente
conocida y que se da a una tasa constante en el tiempo. En el caso de ser aleatoria, podrá
corresponder a una variable discreta o continua.

3. Costos relevantes: Cuando se realiza un análisis de inventarios, deben tenerse en cuenta

diversos costos. Algunos de ellos son:
• Costo de pedido: al emitir una orden de pedido, se incurre en diversos gastos,
fundamentalmente administrativos. De la misma manera, también se tienen gastos al iniciar
un lote de producción, por ejemplo, al poner en marcha una línea de producción o al
preparar una máquina para una corrida de producción. Se trata de un costo fijo, es decir,
independiente del número de unidades pedidas o fabricadas.
• Costo de almacenamiento: el hecho de tener mercadería almacenada produce un costo
que comúnmente se llama costo de conservación o de almacenamiento y que, por lo
general, se expresa por unidad de producto y para el periodo total de análisis o por unidad
de producto y por unidad de tiempo. Este costo incluye ítems tales como alquileres de los
depósitos destinados a almacén, seguros, requerimientos de manejo especial –como
refrigeración–, robo, objetos rotos, etc. Y, el más importante de todos, el costo del capital
inmovilizado en inventarios.
• Costo de ruptura o agotamiento: se produce una ruptura de stock cuando la demanda
supera la cantidad de mercadería en inventario. Cuando se produce una ruptura, puede
ocurrir que esta quede como pedido pendiente, en cuyo caso la mercadería se entregará
cuando se disponga nuevamente de stock, o puede suceder que la venta se pierda. En
cualquier caso, una ruptura produce un costo, llamado costo de agotamiento o de ruptura.
Este costo, que puede incluir tanto componentes explícitos como implícitos, suele medirse
 por unidad de producto y para el periodo total de análisis o, al igual que el de
almacenamiento, por unidad de producto y por unidad de tiempo.

4. Retrasos en el ingreso de los pedidos: debe tenerse en cuenta el periodo que transcurre entre
el momento de hacer el pedido –o iniciar un lote de producción– y aquel en el cual está disponible
la mercadería. La mercadería puede ingresar en forma instantánea, en cuyo caso se dice que
el periodo de adelanto (τ) es cero. De lo contrario, puede ocurrir que este periodo sea distinto
de cero, pero perfectamente conocido –determinista– o que sea aleatorio.

5. Modalidad de ingreso del pedido: puede suceder que el pedido ingrese al almacén en un solo
lote o en forma parcial a lo largo de un periodo de tiempo.

6. Precio del producto: se deben tener en cuenta aquellos casos en los que el precio del producto
varía según el tamaño del pedido.

Simbología:
(T): período de análisis.

(N) demanda total en el período de análisis.

(t) unidad de tiempo.

(h) demanda en la unidad de tiempo o tasa de demanda.

(S) nivel máximo de stock.

(q) cantidad a pedir o tamaño del lote (de producción o compra).

(t1) periodicidad de efectuar los pedidos o iniciar las corridas de producción.

(τ) tiempo que transcurre entre el momento de realización del pedido (o corridas de producción) y su
ingreso al almacén, también conocido como período de adelanto o de reaprovisionamiento.

(v) cantidad de pedidos (o corridas de producción) a efectuar en el período de análisis T.

(pi) costo unitario de producción o adquisición del producto.

(Cs) costo de almacenar una unidad de producto en la unidad de tiempo.

(Cp) costo de efectuar un pedido o iniciar un lote de producción.

(Cr) costo de ruptura por unidad de producto y por unidad de tiempo.

(Cf) costo por unidad de producto faltante al final del período de análisis.

(Ce) costo por unidad de producto excedente o sobrante al final del período.

(CT) costo total variable de la política de inventarios.

Universo cierto: MODELO SIN RUPTURA (SR)
También llamado modelo de la cantidad económica de pedido (CEP), es un modelo de universo
cierto o determinístico a partir de que se considera la demanda como una cantidad conocida.

Supuestos del modelo:

• La demanda es conocida y se produce a una tasa constante en el tiempo.
• No se permiten rupturas de stock.
• El volumen del pedido o lote de producción es constante.
• Se emite una orden de pedido/producción cuando el nivel del inventario llega a cero.
• El pedido o lote de producción ingresa instantáneamente, es decir que el periodo de adelanto
es cero.
• La mercadería se recibe en un solo lote.
• El horizonte de tiempo es infinito y continuo.
• El precio de costo/producción es constante, no importa la cantidad que se pida/fabrique.
• Los costos se consideran constantes en el horizonte de tiempo.

Los costos relevantes en este modelo son el costo de emisión de la orden de pedido (Cp) y el costo
de mantener almacenado el producto (Cs).

Desarrollo del modelo

El objetivo de este modelo es determinar la cantidad óptima de pedido (q*), de manera que se
minimicen los costos totales (CT) y se cumpla con la demanda del producto (N).

Las variables, cuyos valores nos interesan determinar, son:

q = cantidad a pedir o tamaño del lote.
t1 = periodicidad de efectuar los pedidos o iniciar las corridas de producción.
v = cantidad de pedidos (o corridas de producción) a efectuar en el período de análisis T.

Dado que la tasa de demanda (h) es constante por unidad de tiempo, podemos establecer las
siguientes relaciones entre las variables:
 1) Se construye la función objetivo que queremos minimizar, esta es una función de costo total
variable (CT), teniendo en cuenta que los costos relevantes son Cs y Cp.

CT = CTp + CTs

Reemplazando t1 y v por las fórmulas iniciales

Entonces CT en función de la variable q es:

2) Ahora se tiene que calcular la cantidad a pedir que minimice la función de CT, es decir, el (q*)

Observe que esta

es una fórmula que
solo permite
encontrar el valor
del CT para la
cantidad óptima.
Relación entre CTs y CTp
Podemos deducir que, en el valor óptimo de q, se verifica que el costo total de almacenamiento
se iguala al costo total de hacer pedidos, situación que podemos observar en el gráfico.
Una de las características de la función de CT de este modelo es que es poco sensible para
variaciones cercanas al tamaño del lote optimo.

Universo cierto: MODELO CON RUPTURA (CR)

En algunos modelos el tiempo entre pedidos se alarga y se permiten faltantes o rupturas de
stocks, esto hace que el número de pedidos en el periodo total sea menor, con lo cual el costo total de
pedidos se reduce.
El costo total del almacenamiento también disminuye, ya que el nivel de inventario es menor al
permitir faltantes o rupturas, pero se produce un costo por la falta de mercadería que debe ser
considerado. Lo que pretende es equilibrar los costos de ruptura, que son crecientes, con los costos
decrecientes de pedidos y almacenamiento.

Supuestos del modelo:

• La demanda es conocida y se produce una tasa constante en el tiempo

• Se permiten rupturas o faltantes de stock
• El volumen del pedido es constante
• El pedido se recibe instantáneamente, es decir que el periodo de adelante es cero
• La mercadera se recibe en un solo lote
• El horizonte de tiempo es infinito y continuo
• El costo del producto es constante, no importa la cantidad que se pida
• Los costos se consideran constantes en el horizonte de tiempo
• La demanda que se produce cuando no hay stock no se pierde, se lo toma como pedidos
pendientes que se satisfacen al llegar el reabastecimiento.
 • Las q unidades que llegan con cada pedido se tratan de la siguiente manera: se destinan (q-S)
unidades a satisfacer los pedidos pendientes y las S unidades restantes se destinan al nuevo
ciclo.
• El ciclo t1 se divide en dos partes: t2 y t3. Durante el tiempo t2 se dispone de mercadería para
atender la demanda y durante t3 se anotan los requerimientos para satisfacerlos cuando
llegue el próximo pedido

Los costos que se consideran relevantes en este modelo son:

• Cs = costo de mantener una unidad en inventario por unidad de tiempo

• Cp = costo de pedido
• Cr = costo de tener una unidad como pedido pendiente por unidad de tiempo
Las variables, cuyos valores nos interesan determinar, son:

• q = cantidad a pedir o tamaño del lote.

• t1 = periodicidad de los pedidos.
• v = cantidad de pedidos (o corridas de producción) a efectuar en el período de análisis T.
• t2 = tiempo durante el cual existe mercadería en el almacén.
• t3 = tiempo en el cual no existe mercadería en el almacén o, lo que es lo mismo, hay rupturas
de stock.

1o) Se construye la función de costo total variable (CT) teniendo en cuenta que los costos relevantes
son Cs, Cp y Cr.

Considerando que ahora el subperíodo de análisis se divide en un período durante el cual existe
mercadería para atender la demanda y un período donde la demanda se mantiene como pedidos
Pendientes.
2º) Para obtener el valor de q y S que hagan óptima a CT

Observamos que la cantidad óptima de pedido se obtiene ahora de la misma manera que en el
modelo CEP, pero multiplicada por un factor que depende de la magnitud relativa Cr y Cs.

Cuanto mayor sea el costo de mantenimiento de inventario con respecto al costo de los pedidos
pendientes, conviene mantener un nivel de inventario más bajo y, por el contrario, cuanto mayor
importancia tenga el costo por faltantes, el nivel de inventarios será más alto y menor la ruptura.

Entonces cuando el costo de ruptura es inmensamente alto, el modelo 2 se transforma en el

modelo 1, que justamente no admite rupturas porque tienen un costo imposible de afrontar.

También puede observarse que, en el óptimo, el costo total de pedir es igual a la suma del costo
total de almacenar y el costo total de la ruptura.

Modelo con REABASTECIMIENTO UNIFORME (RU)

En este modelo consideraremos que, al realizar una orden, las piezas van ingresando al
inventario a una tasa constante durante un cierto periodo de tiempo. Esta tasa, a la cual se fabrica el
producto debe ser mayor a la tasa de demanda, de lo contrario no se podría cumplir con la demanda.
Supuestos del modelo
• La demanda es conocida y se produce a una tasa constante en el tiempo llamada h.
• El lote se produce a una tasa de producción conocida de a unidades por unidad de tiempo.
• Los bienes ingresan al almacén a una tasa constante a que debe ser mayor a la tasa de
demanda h, de otra manera no existiría inventario, es decir, a > h.
• No se permiten rupturas de stock.
• El volumen del lote de producción (q) es constante.

Se desarrolla el modelo del lote de producción a partir de una función de costo total que
contempla el costo total de almacenamiento más el costo total de preparación de la producción.
 Considerando que durante t4 la mercadería se produce a una tasa a, por lo que al final de este
periodo se habrá completado la producción del lote completo q, es decir:

Debido a que, durante el período t4, ingresa y sale mercadería, la tasa a la cual se acumula el
inventario es (a - h), por lo que el stock máximo, que se da al final del periodo t4 será:

La función de costo total es igual al costo total de fabricar más el costo total de almacenar

El tamaño del lote de producción óptimo será:

En este modelo, como en el modelo sin rupturas, para el lote óptimo:

Modelo RU y modelo SR
Comparando el modelo RU con el modelo SR podemos observar que se realizan pedidos más
grandes y los costos son menores. Esto es así porque, durante el periodo t4, algunas unidades que se
reciben se distribuyen inmediatamente, lo cual reduce los costos de almacenamiento.

El costo total variable de almacenamiento del modelo con reabastecimiento uniforme es igual al
costo total variable del modelo sin ruptura multiplicado por la raíz cuadrada de [1- (h/a)].
Nivel de Reorden (NR)

En los modelos analizados hasta el momento hemos considerado que:

✓ Se emite una orden de pedido cuando el nivel del inventario llega a cero.
✓ El pedido se recibe instantáneamente, es decir que el periodo de adelanto (τ) es cero.

Sin embargo, en la mayoría de los casos transcurre un tiempo entre el momento de realizar el pedido
y el momento en que este ingresa al almacén, llamado periodo de adelanto o de reabastecimiento. Esto
trae como consecuencia la necesidad de fijar un punto de reorden, es decir, un momento en el tiempo
en el cual deberíamos realizar el pedido o un nivel de reorden distinto de cero.

Si recordamos que definimos como nivel de reorden al nivel de inventario que indica el momento de
realizar el pedido, estaremos de acuerdo en que este nivel de inventario debe ser suficiente para
atender a la demanda en el periodo τ, dado que la mercadería no ingresa instantáneamente.

Modelo sin ruptura (SR)

• En el caso de que τ sea menor al t1 NR = h * τ

• En el caso de que τ sea mayor a t1 NR = (τ – x t1) *h

Modelo con ruptura (CR)

En este modelo podríamos analizar si el período de reabastecimiento se produce mientras hay

mercadería en almacén o cuando el stock está en falla.

a) Caso en que el momento de realizar el pedido (t1- τ) se encuentra dentro del período que hay
stock (t2):

NR = h (τ - t3)

b) Caso en que el momento de realizar el

pedido (t1- τ) se encuentra en el período en que no hay stock (t3):
 NR = h (τ - t3)

Observamos que, en ambos casos, el nivel de reorden se calcula de la misma manera. Si el

resultado es positivo, indicará el nivel de stock que nos alerta de realizar el pedido; mientras que, si es
negativo, nos mostrará el nivel de ruptura que advierte cuándo realizar el pedido.

Modelo con Reabastecimiento Uniforme (RU)

En este modelo debemos analizar si el período de reaprovisionamiento se produce mientras está

ingresando mercadería o en el período de solo consumo.

a) Caso en que el momento de realizar el pedido (t1- τ) se encuentra durante el período de demanda
(t5):

NR = h * τ

b) Caso en que el momento de realizar el pedido (t1- τ) se encuentra durante el período de ingreso de
mercadería (t4):

NR = (a - h) (t1 - τ)
Modelo con DESCUENTOS POR COMPRAS EN CANTIDADES
Ocurre frecuentemente que los proveedores ofrecen descuentos si los pedidos son
suficientemente grandes.

Por ejemplo, supongamos que:

• Si el pedido es entre 0 y q1 unidades, el precio unitario es p1

• Si el pedido es entre q1 y q2 unidades, el precio unitario es p2
• Si el pedido es entre q2 y q3 unidades, el precio unitario es p3

Donde el precio unitario va disminuyendo a medida que se

incrementa el tamaño del lote.

q1 < q2 < q3 p1 > p2 > p3

El procedimiento consta de dos etapas:

• Etapa 1: calcular qi* para cada intervalo de precio, comenzando por el intervalo que tiene el
menor precio hasta encontrar un qi* comprendido en el intervalo de cantidades.
• Etapa 2: comparar las funciones de costo total para el qi* encontrado y las cantidades (q)
mínimas que permiten acceder a los descuentos en el precio del producto.

Etapa 1: ¿Como determinar la cantidad óptima a pedir?

Procedimiento
1. Comenzamos por el intervalo de menor
precio y calculamos el qi* con ese precio.
Si qi* está comprendido en ese intervalo,
entonces ese es el volumen óptimo de
pedido.

2. Si qi* no está en ese intervalo,

continuamos con el siguiente intervalo; y
si está comprendido, calculamos el costo
total para ese valor de qi* y para la menor
cantidad con la que se puede acceder al
descuento; el costo total menor indicará
el volumen óptimo (q*).

3. Si qi* no está en ese intervalo,

repetimos el paso 2 hasta encontrar un
qi* comprendido en un intervalo y
comparamos el costo total para ese valor
con los que surgen de considerar las
cantidades mínimas para acceder a cada
descuento.
 CT =CTp + CTs + demanda total valuada según el precio del producto

Para cada valor de pi existirá una función de costo total, la que dependerá solo de q.
SIMULACIÓN
La simulación es un método que le permite al decisor estudiar el comportamiento de un sistema
real experimentando con un modelo que lo representa, llamado modelo de simulación. Este está
formado por las expresiones matemáticas y las relaciones lógicas entre los componentes
fundamentales del sistema y permiten calcular el valor de las salidas de interés dadas las entradas
controlables del sistema.

• Ventaja: Ayuda a comprender el funcionamiento de un sistema ante cambios o nuevas

situaciones. También ayuda a sugerir mejoras y detectar variables importantes.
• Desventaja: presenta el problema de requerir equipo de cómputo y recursos humanos, en
ocasiones costosas. Además, generalmente se requiere bastante tiempo para que un modelo
de simulación sea desarrollado y perfeccionado

Etapas de un estudio de simulación

1. Definición del sistema: realizar un análisis preliminar del mismo para identificar relaciones con
otros sistemas, variables y sus relaciones, medidas de efectividad y resultados que se esperan
obtener del estudio.
2. Formulación del modelo: definir y construir el modelo con el cual se obtendrán los resultados
deseados. Es necesario definir todas las variables y sus relaciones lógicas.
3. Recolección de datos: definir con claridad y exactitud los datos que el modelo va a requerir para
producir los resultados deseados.
4. Implementación del modelo en la computadora.
5. Validación: detallar deficiencias en la formulación del modelo o en los datos que lo alimentan.
Se deberán considerar aspectos tales como:

- Opinión de expertos sobre los resultados.

- Exactitud con que se predicen datos históricos.

- Comprobación de fallas del modelo al utilizar datos que hacen fallar al sistema real.

6. Experimentación.
7. Interpretación.

Números Aleatorios (RANDOM): en cualquier experimento de simulación existe la necesidad de contar

con una fuente de números aleatorios, que nos permiten representar muchos escenarios, generando
valores en forma aleatoria para las entradas probabilísticas. Luego, es posible realizar un análisis
estadístico de los datos obtenidos.

Para la generación de los números aleatorios, es necesario conocer cuál es la distribución de

probabilidad (distribución uniforme) que estos siguen.

RANDOM (RN): Números aleatorios representativos de la realidad.

SIMULACION CONTINUA: Generación de números aleatorios no uniformes (con probabilidad no
constante)

• Poisson

• Exponencial

• Uniforme

• Normal

SIMULACION DISCRETA:

1. Simulación Estática: Montecarlo

Generación de números aleatorios uniformes (con probabilidad constante)

Es usado para conocer el comportamiento de los modelos de simulación estáticos que

se basan en resolver ensayos independientes, en los que los resultados que ocurren en un
ensayo no afectan lo que ocurre en ensayos subsecuentes.

Se utilizan números “aleatorios” generados matemáticamente con distribución uniforme

que ocurren supuestamente al azar.

El método Monte Carlo consiste en:

➢ Identificar el experimento o sistema a simular.
➢ Identificar el espacio muestral y definir la variable aleatoria.
➢ Definir la función de probabilidad.
➢ Construir la función acumulada de probabilidad.
➢ Tratar de determinar el valor de la variable aleatoria en base a números aleatorios
➢ Ofrecer conclusiones sobre la simulación
2. Simulación Dinámica: Líneas de Espera

Una situación de línea de espera se produce cuando un “cliente” (hombre o máquina)

llega a una instalación para recibir un “servicio”, espera en una fila hasta ser atendido y luego
se retira. La cola se forma cuando la demanda de un servicio es mayor que la capacidad del
servicio.

La teoría de las colas comprende a un grupo muy grande de modelos en donde cada uno
se refiere a un tipo diferente de situación de línea de espera. Sin embargo, todos ellos tienen
algunas cosas en común.

Los componentes que caracterizan a las líneas de espera son:

• Población de clientes o fuente de clientes, que puede ser finita o infinita.

• Proceso de llegada, que es la forma en que llegan los clientes al sistema y que está
especificado por el tiempo entre llegadas.
• Proceso de servicio, que está especificado por el tiempo que dura el servicio.
• Disciplina de la cola, es decir, el orden en el que son atendidos los clientes.

En general, los sistemas de colas pasan por dos fases:

• Fase transitoria: este periodo inicial tiene muchas características transitorias que no son
similares a los valores promedios a largo plazo o de estado estacionario.
• Fase estable: es la condición del sistema luego de haberse eliminado las condiciones
iniciales, esto es, cuando el sistema alcanza el estado estacionario.

Los modelos de colas son de tipo descriptivos. Es decir que no solucionan directamente el
problema, pero aportan información fundamental al momento de tomar decisiones describiendo
las características de operación del sistema como son la longitud de la cola o el tiempo de espera
en el sistema, entre otras.

Existen numerosas situaciones para las cuales no pueden ser utilizados ninguno de los
modelos matemáticos ya desarrollados; en estas situaciones, la alternativa es realizar un análisis
por simulación para así determinar las características de operación del sistema de espera en
fila.

La operación física del sistema es:

1. El cliente llega:

➢ Si el servidor está desocupado, es atendido.

➢ Si el servidor está ocupado, se suma a la cola de espera hasta que el servidor se

desocupa, recibiendo a continuación el servicio.

2. Una vez atendido, se retira del sistema.

Para el modelo de simulación, es necesario describir y sincronizar la llegada de los

clientes y el suministro del servicio.

Existen dos enfoques para la lógica y el seguimiento de los registros del modelo:
incremento de tiempo fijo e incremento según el evento siguiente.
• Incremento de tiempo fijo: todos los periodos son de igual duración y se actualiza el estado
del sistema al principio o al final de cada lapso o intervalo de tiempo.
• Incremento según el evento siguiente: consiste en generar aleatoriamente el tiempo que
transcurre entre llegadas y el tiempo que se requiere para cumplir el servicio de un cliente.
Se actualizará el sistema en cada momento en que llegue un cliente o en el que se termina
de atender a uno. De modo que es variable el tiempo entre actualizaciones del sistema.

Tiempo entre llegadas:

Tiempos de servicio: