UNIDAD 1

1. Definiciones previas
 Restricción Ecuación o desigualdad que descarta ciertas combinaciones de variables de decisión
como soluciones factibles.
 Formulación del problema Proceso de traducir la definición verbal de un problema en un enunciado
matemático llamado modelo matemático.
 Modelo matemático Representación de un problema donde el objetivo y todas las condiciones de
restricción se describen por medio de expresiones matemáticas.
 Variable de decisión Insumo controlable para un modelo de programación lineal.
 Función objetivo Expresión que define la cantidad que se maximizará o minimizará en un modelo
de programación lineal.
 Restricciones de no negatividad Conjunto de restricciones que requiere que todas las variables
sean no negativas.
 Programa lineal Modelo matemático con una función objetivo lineal, una serie de restricciones
lineales y variables no negativas.
 Funciones lineales Expresiones matemáticas en las cuales las variables aparecen en términos
separados y se elevan a la primera potencia.
 Solución factible Solución que satisface todas las restricciones de forma simultánea.
 Región factible Conjunto de todas las soluciones factibles.
 Variable de holgura Variable añadida en el lado izquierdo de una restricción de menor o igual que
para convertir la restricción en una igualdad. El valor de esta variable por lo general se interpreta
como la cantidad de un recurso sin utilizar.
 Forma estándar Programa lineal en el cual todas las restricciones se expresan como igualdades.
La solución óptima de la forma estándar de un programa lineal es la misma que la solución óptima
de la formulación original del programa lineal.
 Restricción redundante Restricción que no afecta la región factible. Si una restricción es
redundante, puede eliminarse del problema sin afectar a la región factible.
 Punto extremo En términos gráficos, los puntos extremos son los de solución factible que se
encuentran en los vértices, o “esquinas”, de la región factible. En los problemas de dos variables, los
puntos extremos están determinados por la intersección de las rectas de restricción.
 Variable de excedente Variable restada en el lado izquierdo de una restricción de mayor o igual que
para convertir la restricción en una igualdad. El valor de esta variable por lo general se interpreta
como la cantidad que rebasa y está por encima de algún nivel mínimo requerido.
 Soluciones óptimas alternas Caso en el cual más de una solución proporciona el valor óptimo para
la función objetivo.
 Infactibilidad Situación en la cual ninguna solución para el problema de programación lineal
satisface todas las restricciones.
 Ilimitada Situación en la cual el valor de la solución puede ser infinitamente grande para un problema
de programación lineal de maximización o infinitamente pequeño para un problema de minimización
sin violar ninguna de las restricciones.

2. Conceptos de Programación Lineal

La programación lineal es un método mediante el cual se optimiza, ya sea maximizando o
minimizando, una función objetivo, donde las variables están elevadas a la potencia 1. Esto,
tomando en cuenta distintas restricciones dadas.
La programación lineal es, entonces, un proceso por el cual se maximizará una función lineal.
Es decir, una ecuación de primer grado, donde las variables están elevadas a la potencia 1.
𝑎𝑥 + 𝑏 = 𝑦
Debemos recordar que este tipo de ecuación es una igualdad matemática que puede tener una
o más incógnitas. Así, tiene la siguiente forma básica, donde 𝑎 y 𝑏 son las constantes, mientras
que 𝑥 e 𝑦 son las variables.
Ahora, mediante la programación lineal, se podría optimizar esta función, hallando el máximo o
el mínimo valor de 𝑦. Esto, tomando en cuenta que 𝑥 está sujeta a ciertas restricciones. Quizás
es mayor a 0 y menor que 20, por ejemplo.
La programación lineal (LP, también conocida como optimización lineal) es el campo de la
programación matemática dedicado a maximizar o minimizar (optimizar) una función lineal,
denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a
una serie de restricciones expresadas mediante un sistema de ecuaciones o inecuaciones
también lineales.

3. Modelos

A. Modelo de Programación Lineal

El primer paso durante la formulación de un problema de programación lineal es identificar las
variables de decisión las cuales son denominadas variable. Los valores, una vez determinados,
proporcionan la solución de un problema de la vida cotidiana. Como estos elementos no se dan
a conocer a cada variable de decisión toma el nombre de simbólico (Es un nombre descriptivo
dado a una variable en un modelo matemático que permite la comprensión del significado de la
variable.
Se tiene las siguientes características:
1. Qué elementos afectan los costos y/o las ganancias.
2. Qué elementos puede elegir y/o controlar libremente.
3. Qué decisión tiene que tomar.
4. Qué valores toma la variable para la solución del problema.
Identificación de la función objetivo.
Consiste en la función que se desea optimizar, es decir, maximizar utilidades o minimizar costos.
El procedimiento es el siguiente:
1. Se establece el objetivo en forma verbal.
2. En el momento adecuado se descompone el objetivo en una suma, diferencia o producto de
las cantidades individuales.
3. Se expresa las cantidades individuales matemáticamente usando las variables de decisión
y otros datos que se tienen el problema a estudiar.
Identificación de restricciones.
Las restricciones son condiciones que las variables de decisión deben satisfacer para constituir
una solución aceptable.
Estas parten de:
1. Limitaciones físicas.
2. Restricciones impuestas por la administración
3. Restricciones externas.
4. Relaciones implicadas entre las variables.
5. Restricciones lógicas de variables individuales.

B. Método gráfico
Consiste en la representación gráfica de modelos de programación lineal en el cual se utilizan
dos o más variables para la toma de decisiones de problemas de situaciones reales.
El procedimiento según el método grafico es el siguiente:
1. Se define las variables de decisión.
2. Se define la función Objetivo: si se va a maximizar utilidades y/o minimizar costos.
3. Se difieren las restricciones que deben ser lineales. Asimismo, la restricción debe adoptar
alguna de las siguientes formas (≤, ≥, =, es decir, las restricciones de programación lineal).
Maximización de utilidades
Es una tendencia en la toma de decisiones por parte del comprador o el demandante o
demandantes en obtener el mayor beneficio o la mayor ganancia posible.
Minimización de costos
La minimización de costos consiste en el menor valor que genera la función al utilizar cierto
número de unidades de las variables o recursos.
Análisis de sensibilidad de los parámetros de la función objetivo y los lados derechos de las
restricciones.
Este procedimiento se utiliza después de realizar el modelo de programación lineal en el cual
se determina un mínimo costo y máxima utilidad, en el cual me permite examinar la variabilidad
de los parámetros dentro de un problema.

C. Método Simplex
Este método le permitirá solucionar problemas que no pueden ser resueltos por el método
gráfico, es decir, cuando se tienen dos o más variables. Este nos permite resolver problemas
que tengan cualquier número de variables.
VARIABLE DE HOLGURA
Una variable de holgura es una variable que me permite que las variables de las ecuaciones de
las restricciones queden o formen una igualdad, por cada ecuación se involucra una de holgura.
Procedimiento del método simplex
Se define el problema.
𝑀𝐴𝑋 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3
Se definen las restricciones
𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 ≤ 𝑏2
𝑎31 𝑥1 + 𝑎32 𝑥2 + 𝑎33 𝑥3 ≤ 𝑏3
Donde 𝑥1 , 𝑥2 , 𝑥3 𝑦 𝑏1 , 𝑏2 , 𝑏3 son valores no negativos.
1. Configure la tabla simplex

Existen tres variables de holgura S1, S2 y S3 y una por cada restricción.

2. Si todos los indicadores en el último renglón son no negativos, entonces Z tiene un valor
máximo cuando 𝑋1 = 0, 𝑋2 = 0 y 𝑋3 = 0. El valor máximo es cero. Si existen indicadores
negativos, localice la columna en la que aparezca el indicador más negativo. Esta columna
pivote proporciona la variable entrante.
3. Divida cada entrada positiva por encima de la línea punteada en la columna de la variable
entrante, con el correspondiente valor de b. (tomando el valor de b como dividendo y la
entrada positiva como divisor).
4. Marque la entrada en la columna pivote que corresponda al cociente más pequeño del
anterior paso. Esta es la entrada pivote. La variable saliente es aquella que está a la
izquierda en la fila del pivote.
5. Utilice operaciones elementales sobre las filas para transformar la tabla en una nueva tabla
equivalente que tenga un 1 donde estaba la entrada pivote y ceros alrededor.
6. En lado izquierdo de esta tabla la variable entrada remplazada a la variable saliente.
7. Si los indicadores la nueva tabla son todos no negativos, se tendrá la solución óptima.

VIDEO: https://mx.video.search.yahoo.com/search/video?fr=mcafee&ei=UTF-
8&p=problemas+resueltos+de+m%C3%A9todo+simplex&type=E211MX714G0#id=1&vid
=da732a2b6ceeb6b8e0a0c6c9587ffb00&action=click

COMPONENTES DEL MODELO DE PROGRAMACIÓN LINEAL

En los últimos 60 años, la PL se ha aplicado ampliamente a problemas militares, industriales,
financieros, de comercialización, de contabilidad y de agricultura. Aun cuando sus aplicaciones
son diversas, todos los problemas de PL tienen varias propiedades y suposiciones comunes.
Todos los problemas buscan maximizar o minimizar alguna cantidad, por lo general la utilidad
o el costo. Nos referimos a esta propiedad como la función objetivo de un problema de PL. El
principal objetivo de un fabricante típico es maximizar las utilidades en dólares. En el caso de
un sistema de distribución por camión o por ferrocarril, el objetivo sería minimizar los costos de
envío. En todo caso, el objetivo se debe establecer con claridad y definir matemáticamente. No
importa, por cierto, si las utilidades y los costos se miden en centavos de dólar, dólares o
millones de dólares.
La segunda propiedad que los problemas de PL tienen en común es la presencia de limitaciones
o restricciones, que acotan el grado en que se puede alcanzar el objetivo. Por ejemplo, la
decisión de cuántas unidades de cada producto fabricar en la línea de productos de una
empresa está restringida tanto por el personal como por la maquinaria disponibles. La selección
de una política de publicidad o de un portafolio financiero está limitada por la cantidad de dinero
disponible para gastar o invertir.
Se desea, por lo tanto, maximizar o minimizar una cantidad (la función objetivo) sujeta a
recursos limitados (las restricciones).
Tienen que existir cursos de acción alternativos para elegir. Por ejemplo, si una organización
fabrica tres productos diferentes, la gerencia puede utilizar la PL para decidir cómo distribuir
entre ellos sus recursos de producción limitados (de personal, maquinaria, etcétera). ¿Debería
dedicar toda la capacidad de fabricación para hacer únicamente el primer producto, elaborar la
misma cantidad de cada producto o asignar los recursos en alguna otra proporción? Si no hay
alternativas para elegir, no habría necesidad de la PL.
Los objetivos y las restricciones en los problemas de PL se deben expresar en términos de
ecuaciones o desigualdades lineales. Las relaciones matemáticas lineales tan solo significan
que todos los términos utilizados en la función objetivo y en las restricciones son de primer
grado (es decir, no se elevan al cuadrado, al cubo o a una potencia mayor, ni se presentan más
de una vez). Por consiguiente, la ecuación 2𝐴 + 5𝐵 = 10 es una función lineal aceptable;
mientras que la ecuación 2𝐴2 + 5𝐵 3 − 3𝐴𝐵 = 10 no es lineal, ya que la variable A está al
cuadrado, la variable B está al cubo y las dos variables se presentan de nuevo como producto
entre ellas.
El término lineal implica tanto proporcionalidad como adición. Proporcionalidad significa que, si
la producción de una unidad de un producto utiliza tres horas, la producción de 10 unidades
tomaría 30 horas. Adición significa que el total de todas las actividades es igual a la suma de
las actividades individuales. Si la fabricación de un producto generó una utilidad de $3 y la
elaboración de otro producto generó una utilidad de $8, la utilidad total sería la suma de estas
dos, que es $11.
Se supone que existen condiciones de certeza, es decir, se conocen con certeza el número en
el objetivo y en las restricciones, y no cambia durante el periodo de estudio.
Se hace la suposición de divisibilidad: las soluciones no necesitan ser números enteros. Por el
contrario, son divisibles y quizá tomen cualquier valor fraccionario. En los problemas de
producción, a menudo se definen variables como el número de unidades fabricadas por semana
o por mes, y un valor fraccionario (como 0.3 sillas) simplemente significaría que se trata de un
trabajo en proceso.
Algo que comenzó en una semana puede terminarse en la siguiente. Sin embargo, en otros
tipos de problemas, los valores fraccionarios no tienen sentido. Si una fracción de un producto
no se puede comprar (digamos, un tercio de un submarino), existe un problema de
programación entera. La programación entera se analizará en una sección más adelante.
Por último, se supone que todas las respuestas o las variables son no negativas. Los valores
negativos de las cantidades físicas son imposibles, pues sencillamente no se puede fabricar un
número negativo de sillas, camisas, lámparas o computadoras. A continuación, se resumen las
propiedades y supuestos.
PROPIEDADES DE PROGRAMAS LINEALES
1. Una función objetivo
2. Una o más restricciones
3. Cursos de acción alternativos
4. La función objetivo y las restricciones son lineales: proporcionalidad y divisibilidad
5. Certeza
6. Divisibilidad
7. Variables no negativas

FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL (PL)

La formulación de un programa lineal implica el desarrollo de un modelo matemático que
represente el problema administrativo. Por lo tanto, para formular un programa lineal, es
necesario entender cabalmente el problema administrativo al que se enfrenta. Una vez que se
haya entendido, es posible comenzar a desarrollar la formulación matemática del problema. Los
pasos en la formulación de un programa lineal son los siguientes:
1. Entender cabalmente el problema administrativo que se enfrenta.
2. Identificar el objetivo y las restricciones.
3. Definir las variables de decisión.
4. Utilizar las variables de decisión para escribir expresiones matemáticas de la función objetivo
y de las restricciones.
Una de las aplicaciones más comunes de la PL es el problema de la mezcla de productos. Con
frecuencia dos o más productos se fabrican con recursos limitados, como personal, máquinas,
materia prima, etcétera. La utilidad que la empresa busca maximizar se basa en la contribución
a la utilidad por unidad de cada producto. (Tal vez recuerde que la contribución a la utilidad es
únicamente el precio de venta por unidad menos el costo variable por unidad*). La compañía
quiere determinar cuántas unidades de cada producto se deberían fabricar para maximizar la
utilidad general, dados sus recursos limitados. Un problema de este tipo se formula en el
siguiente ejemplo.

EJEMPLO 1.
La compañía Flair Furniture fabrica mesas y sillas de bajo precio. El proceso de fabricación de
cada una es similar, ya que ambas requieren cierto número de horas de trabajo de carpintería,
así como cierto número de horas de trabajo en el departamento de pintura y barnizado. Cada
mesa requiere de 4 horas de carpintería y 2 horas en el taller de pintura y barnizado. Cada silla
requiere de 3 horas de carpintería, y 1 hora en la pintura y barnizado. Durante el periodo de
producción actual, están disponibles 240 horas de tiempo de carpintería, así como 100 horas
de tiempo de pintura y barnizado. Cada mesa vendida genera una utilidad de $70; cada silla
fabricada se vende con una utilidad de $50.
El problema de Flair Furniture es determinar la mejor combinación posible de mesas y sillas a
fabricar, con la finalidad de alcanzar la utilidad máxima. La empresa desea que esta situación
de mezcla de producción se formule como un problema de PL.
SOLUCIÓN
El objetivo es:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑙𝑎 𝑢𝑡𝑖𝑙𝑖𝑑𝑎𝑑
Las restricciones son:
1. 𝐿𝑎𝑠 ℎ𝑜𝑟𝑎𝑠 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎𝑠 𝑛𝑜 𝑝𝑢𝑒𝑑𝑒𝑛 𝑒𝑥𝑐𝑒𝑑𝑒𝑟 𝑙𝑎𝑠 240 ℎ𝑜𝑟𝑎𝑠 𝑝𝑜𝑟 𝑠𝑒𝑚𝑎𝑛𝑎.
2. 𝐿𝑎𝑠 ℎ𝑜𝑟𝑎𝑠 𝑑𝑒 𝑝𝑖𝑛𝑡𝑢𝑟𝑎 𝑦 𝑏𝑎𝑟𝑛𝑖𝑧𝑎𝑑𝑜 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎𝑠 𝑛𝑜 𝑝𝑢𝑒𝑑𝑒𝑛 𝑒𝑥𝑐𝑒𝑑𝑒𝑟 𝑙𝑎𝑠 100 ℎ𝑜𝑟𝑎𝑠 𝑝𝑜𝑟 𝑠𝑒𝑚𝑎𝑛𝑎.
Las variables de decisión que representan las decisiones reales que tomarán se definen como:
𝑇 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑚𝑒𝑠𝑎𝑠 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑠𝑒𝑚𝑎𝑛𝑎
𝐶 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑠𝑖𝑙𝑙𝑎𝑠 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑠𝑒𝑚𝑎𝑛𝑎
Ahora se crea la función objetivo de PL en términos de 𝑇 y 𝐶. La función objetivo es
𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑙𝑎 𝑢𝑡𝑖𝑙𝑖𝑑𝑎𝑑 = $70𝑇 + $50𝐶.
El siguiente paso es desarrollar las relaciones matemáticas para describir las dos restricciones
en este problema. Una relación general es que la cantidad de un recurso utilizado debe ser
menor que o igual a (≤) la cantidad del recurso disponible.
En el caso del departamento de carpintería, el tiempo total utilizado es:
(4 ℎ𝑜𝑟𝑎𝑠 𝑝𝑜𝑟 𝑚𝑒𝑠𝑎)(𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑚𝑒𝑠𝑎𝑠 𝑓𝑎𝑏𝑟𝑖𝑐𝑎𝑑𝑎𝑠)
+ (3 ℎ𝑜𝑟𝑎𝑠 𝑝𝑜𝑟 𝑠𝑖𝑙𝑙𝑎)(𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑠𝑖𝑙𝑙𝑎𝑠 𝑓𝑎𝑏𝑟𝑖𝑐𝑎𝑑𝑎𝑠)
Entonces, la primera restricción se expresa de la siguiente manera:
𝑇𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑜 ≤ 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎
4𝑇 + 3𝐶 ≤ 240 (ℎ𝑜𝑟𝑎𝑠 𝑑𝑒 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎)
Del mismo modo, la segunda restricción es la siguiente:
𝑇𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑝𝑖𝑛𝑡𝑢𝑟𝑎 𝑦 𝑏𝑎𝑟𝑛𝑖𝑧𝑎𝑑𝑜 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑜 ≤ 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒 𝑑𝑒 𝑝𝑖𝑛𝑡𝑢𝑟𝑎 𝑦 𝑏𝑎𝑟𝑛𝑖𝑧𝑎𝑑𝑜
2𝑇 + 1𝐶 ≤ 100 (ℎ𝑜𝑟𝑎𝑠 𝑑𝑒 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑝𝑖𝑛𝑡𝑢𝑟𝑎 𝑦 𝑏𝑎𝑟𝑛𝑖𝑧𝑎𝑑𝑜)
Para obtener soluciones significativas, los valores de T y C deben ser números no negativos.
Es decir, todas las posibles soluciones tienen que representar mesas y sillas reales.
Matemáticamente, esto significa que:
𝑇 ≥ 0 (𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑚𝑒𝑠𝑎𝑠 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑎𝑠 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 𝑜 𝑖𝑔𝑢𝑎𝑙 𝑎 0)
𝐶 ≥ 0 (𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑠𝑖𝑙𝑙𝑎𝑠 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑑𝑎𝑠 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 𝑜 𝑖𝑔𝑢𝑎𝑙 𝑎 0)
Ahora el problema completo se reexpresa matemáticamente como:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑢𝑡𝑖𝑙𝑖𝑑𝑎𝑑 = $70𝑇 + $50𝐶
sujeto a las restricciones:
4𝑇 + 3𝐶 ≤ 240 (𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎)
2𝑇 + 1𝐶 ≤ 100 (𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑝𝑖𝑛𝑡𝑢𝑟𝑎 𝑦 𝑏𝑎𝑟𝑛𝑖𝑧𝑎𝑑𝑜)
𝑇 ≥ 0 (𝑝𝑟𝑖𝑚𝑒𝑟𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑)
𝐶 ≥ 0 (𝑠𝑒𝑔𝑢𝑛𝑑𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑)
En tanto que las restricciones de no negatividad son limitaciones técnicamente independientes,
se escriben a menudo en un solo renglón con las variables separadas por comas. En este
ejemplo, esto se expresaría como:
𝑇, 𝐶 ≥ 0

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑢𝑡𝑖𝑙𝑖𝑑𝑎𝑑 $70𝑇 $50𝐶

sujeto a las restricciones:
4𝑇 + 3𝐶 = 240 (𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑐𝑎𝑟𝑝𝑖𝑛𝑡𝑒𝑟í𝑎)
2𝑇 + 1𝐶 = 100 (𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑝𝑖𝑛𝑡𝑢𝑟𝑎 𝑦 𝑏𝑎𝑟𝑛𝑖𝑧𝑎𝑑𝑜)
 𝑇 ≥ 0 (𝑝𝑟𝑖𝑚𝑒𝑟𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑)
𝐶 ≥ 0 (𝑠𝑒𝑔𝑢𝑛𝑑𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑)
En tanto que las restricciones de no negatividad son limitaciones técnicamente independientes,
se escriben a menudo en un solo renglón con las variables separadas por comas. En este
ejemplo, esto se expresaría como:
𝑇, 𝐶 ≥ 0
Solución gráfica a un problema de PL
El procedimiento gráfico únicamente es útil cuando existen dos variables de decisión (tales
como el número de mesas a producir, T, y el número de sillas a producir, C) en el problema.
Cuando hay más de dos variables, no es posible mostrar la solución en una gráfica
bidimensional y se debe recurrir a enfoques más complejos. Sin embargo, el método gráfico es
muy valioso y nos ofrece una visión de cómo funcionan otros métodos.

FIGURA 7.1 Cuadrante que contiene todos los valores positivos

Para representar gráficamente la primera restricción, 4𝑇 + 3𝐶 ≤ 240, primero se grafica la parte
de la igualdad de esta, que es:
4𝑇 + 3𝐶 = 240
Como recordará, en álgebra elemental, una ecuación lineal con dos variables es una recta. La
forma más fácil de trazar la recta es encontrar cualesquier dos puntos que satisfagan la
ecuación y, después, dibujar una recta que pase a través de ellos.
Los dos puntos más fáciles de encontrar son generalmente los puntos en los cuales la recta
interseca los ejes T y C.
4𝑇 + 3𝐶 = 240
T 0 60
C 80 0
 FIGURA 2. Gráfica de la restricción 𝟒𝑻 + 𝟑𝑪 = 𝟐𝟒𝟎 de carpintería
No obstante, recuerde que la restricción de carpintería real era la desigualdad 4𝑇 + 3𝐶 ≤ 240.
¿Cómo se identifican todos los puntos de solución que satisfagan esta restricción? Resulta que
hay tres posibilidades. Primera, sabemos que cualquier punto que se encuentre en la recta 4𝑇 +
3𝐶 = 240 satisfará la restricción. Cualquier combinación de mesas y sillas en la recta agotará
las 240 horas de tiempo de carpintería. * Ahora se debe encontrar el conjunto de puntos de
solución que emplearían menos de 240 horas. Los puntos que satisfacen la parte < de la
restricción (es decir, 4𝑇 + 3𝐶 < 240) serán todos los puntos en un lado de la recta, en tanto que
todos los puntos del otro lado de la recta no cumplen con esta condición. Para determinar de
qué lado de la recta están, basta con elegir un punto a cada lado de la recta de la restricción
que se presenta en la figura 3 y comprobar si este satisface esta condición. Por ejemplo, se
elige el punto (30, 20) como se ilustra en la figura 1:
4(30) + 3(20) = 180
Como 180 < 240, este punto satisface la restricción, y todos los puntos de este lado de la recta
también satisfarán la restricción. Este conjunto de puntos se indica mediante la región
sombreada en la figura 3.
Por otro lado, si
4(70) + 3(40) = 400
Como 400 𝑛𝑜 𝑒𝑠 𝑚𝑒𝑛𝑜𝑟 𝑑𝑒 240, este punto no satisface la restricción, y todos los puntos de este
lado de la recta tampoco satisfarán la restricción.
 FIGURA 3 Región que satisface la restricción de carpintería

Para la segunda restricción 2𝑇 + 1𝐶 ≤ 100, se aplica la misma metodología que la restricción

1; por tanto, la gráfica quedaría como se muestra en la figura 4.

FIGURA 4 Región que satisface la restricción de pintura y barnizado

Al consolidar las figuras 3 y 4, se obtiene la figura 5.

FIGURA 5. Región de solución factible para el problema de la compañía Flair Furniture
PROGRAMACIÓN LINEAL

1
 PROGRAMACIÓN LINEAL
La Programación Lineal corresponde a un
algoritmo a través del cual se resuelven situaciones
reales en las que se pretende identificar y resolver
dificultades para aumentar la productividad respecto
a los recursos (principalmente los limitados y
costosos), aumentando así los beneficios. Su
objetivo es optimizar, es decir, maximizar o
minimizar funciones lineales en varias variables
reales con restricciones lineales (sistemas de
inecuaciones lineales), optimizando una función
objetivo también lineal.

2
 PROGRAMACIÓN LINEAL
Los resultados y el proceso de optimización se
convierten en un respaldo cuantitativo de las
decisiones frente a las situaciones planteadas.
Decisiones en las que sería importante tener en
cuenta diversos criterios administrativos como:
Los hechos
La experiencia
La intuición
La autoridad

3
 PROGRAMACIÓN LINEAL
¿COMO RESOLVER UN PROBLEMA MEDIANTE
PROGRAMACIÓN LINEAL?

El primer paso para la resolución de un problema de

programación lineal consiste en la identificación de los
elementos básicos de un modelo matemático, estos son:

Función Objetivo
Variables
Restricciones

4
 PROGRAMACIÓN LINEAL
¿COMO RESOLVER UN PROBLEMA MEDIANTE
PROGRAMACIÓN LINEAL?
Para la determinación de los elementos
matemático es necesario aplicar la siguiente
metodología.

IDENTIFICA IDENTIFICA
DEFINIR EL PLANTEAR
RY RY
CRITERIO LA
DEFINIR DEFINIR
DE LA FUNCIÓN
LAS RESTRICCI
FUNCIÓN OBJETIVO
VARIABLES ONES

5
 PROGRAMACIÓN LINEAL
LA FUNCIÓN OBJETIVO
La función objetivo tiene una estrecha relación con la
pregunta general que se desea responder.
Sí en un modelo resultasen distintas preguntas, la
función objetivo se relacionaría con la pregunta del
nivel superior, es decir, la pregunta fundamental.
Por ejemplo, si en una situación se desean minimizar
los costos, es muy probable que la pregunta de mayor
nivel sea la que se relacione con aumentar la utilidad
en lugar de un interrogante que busque hallar la
manera de disminuir los costos.

6
 PROGRAMACIÓN LINEAL

PREGUNTA FUNDAMENTAL / FUNCIÓN OBJETIVO

¿Cómo se pueden Minimizar costos de

disminuir los costos de mantenimiento y de
inventario? ordenar

¿Qué se debe hacer para Maximizar utilidades

mejorar las utilidades netas después de causar
de la compañía? impuestos

7
 PROGRAMACIÓN LINEAL
LAS VARIABLES DE DECISIÓN
Similar a la relación que existe entre objetivos
específicos y objetivo general se comportan las variables
de decisión respecto a la función objetivo, puesto que
estas se identifican partiendo de una serie de preguntas
derivadas de la pregunta fundamental. Las variables de
decisión son en teoría factores controlables del sistema
que se está modelando, y como tal, estas pueden tomar
diversos valores posibles, de los cuales se precisa conocer
su valor óptimo, que contribuya con la consecución del
objetivo de la función general del problema.

8
 PROGRAMACIÓN LINEAL

Variable de decisión, parten de la

función objetivo

MINIMIZAR los costos de mentenimiento.

Y de ordenar
¿Qué cantidad de ¿Qué nivel de
¿En cuáles periodos
productos deben inventario deberá
deberá ordenarse, y
ordenarse por mantenerse al final de
en cuáles no?
periodo? cada periodo?

9
 PROGRAMACIÓN LINEAL
LAS RESTRICCIONES
Cuando hablamos de las restricciones en un problema de
programación lineal, nos referimos a todo aquello que
limita la libertad de los valores que pueden tomar las
variables de decisión.
La mejor manera de hallarlas consiste en pensar en un
caso hipotético en el que decidiéramos darle un valor
infinito a nuestras variables de decisión, por ejemplo, ¿qué
pasaría sí en un problema que precisa maximizar sus
utilidades en un sistema de producción de calzado
decidiéramos producir una cantidad infinita de zapatos?

10
 PROGRAMACIÓN LINEAL
LAS RESTRICCIONES
Seguramente ahora nos surgirían múltiples interrogantes,
como por ejemplo:
Con cuánta materia prima cuento para producirlos?
Con cuánta mano de obra cuento para fabricarlos?
Pueden las instalaciones de mi empresa albergar tal
cantidad de producto?
Podría mi fuerza de mercadeo vender todos los
zapatos?
Puedo financiar tal empresa?
Pues bueno, entonces habríamos descubierto que nuestro
sistema presenta una serie de limitantes, tanto físicas, como
de contexto.
11
PROGRAMACIÓN LINEAL

12
PROGRAMACIÓN LINEAL

13
PROGRAMACIÓN LINEAL

DISPONIBILDAD
DE MATERIA
PRIMA

14
PROGRAMACIÓN LINEAL

15
16
 PROGRAMACIÓN LINEAL
El método gráfico
Es un procedimiento de solución de problemas de
programación lineal muy limitado en cuanto al número de
variables (2 si es un gráfico 2D y 3 si es 3D) pero muy rico
en materia de interpretación de resultados e incluso
análisis de sensibilidad. Este consiste en representar cada
una de las restricciones y encontrar en la medida de lo
posible el polígono (poliedro) factible, comúnmente
llamado el conjunto solución o región factible, en el cual
por razones trigonométricas en uno de sus vértices se
encuentra la mejor respuesta (solución óptima).

17
PROGRAMACIÓN LINEAL

18
PROGRAMACIÓN LINEAL

19
 PROGRAMACIÓN LINEAL
Reddy Mikks produce pinturas para interiores y exteriores con
dos materias primas, M1 y M2. La tabla siguiente proporciona
los datos básicos del problema.
Toneladas de materia prima por Disponibilidad diaria
tonelada de máxima TN
Pintura para Pintura para
exteriores interiores
Materia prima,M1 6 4 24
Materia prima,M2 1 2 6
Utilidad por tonelada ($1000) 5 4

Una encuesta de mercado indica que la demanda diaria de

pintura para interiores no puede exceder la de pintura para
exteriores en más de una tonelada. Asimismo, que la demanda
diaria máxima de pintura para interiores es de dos toneladas.

20
PROGRAMACIÓN LINEAL

21
 PROGRAMACIÓN LINEAL
Ozark Farms consume diariamente un mínimo de 800 lb de un alimento
especial, el cual es una mezcla de maíz y soya con las siguientes
composiciones:

Las necesidades dietéticas del alimento especial son un mínimo de 30% de

proteína y un máximo de 5% de fibra. El objetivo es determinar la mezcla diaria
de alimento a un costo mínimo.

22
PROGRAMACIÓN LINEAL

23
 PROGRAMACIÓN LINEAL
PROBLEMA DE DIETA
• Un comprador está tratando de seleccionar la
combinación más barata de dos alimentos, que debe
cumplir con ciertas necesidades diarias de vitaminas.
Los requerimientos vitamínicos son por lo menos 40
unidades de vitamina W, 50 unidades de vitamina X y 49
unidades de vitamina Y. Cada onza del alimento A
proporciona 4 unidades de vitamina W, 10 unidades de
vitamina X y 7 unidades de vitamina Y; cada onza del
alimento B suministra 10 unidades de W, 5 unidades de
X y 7 unidades de Y. El alimento A cuesta 5
monedas/onza y el alimento B vale 8 monedas/onza.

24
 PROGRAMACIÓN LINEAL
Una empresa va a lanzar al mercado un nuevo producto. Los planes
de promoción para el próximo mes están en marcha. Los medios
alternativos para realizar la publicidad así como los costos y la
audiencia estimada por unidad de publicidad se muestran a
continuación :
TELEVISION RADIO PRENSA
Audiencia por unidad de publicidad 100.000 18.000 40.000
Costo por unidad de publicidad USD$ 2.000,00 300 600

Para lograr un uso balanceado de los medios, la publicidad en radio

debe ser igual al 50% de unidades de publicidad autorizadas. Además
la cantidad de unidades solicitadas en televisión debe ser al menos
10% del total autorizado. El presupuesto total para promociones se ha
limitado a USD$ 18,500. Se necesita determinar el plan óptimo para
maximizar la audiencia total o cantidad de personas que vean la
publicidad.
25
• GRUPO 1: WinQSB
• GRUPO 2: TORA
• GRUPO 3: LINDO
• GRUPO 4: LINGO
• GRUPO 5: SOLVER
• GRUPO 6: POM
• GRUPO 7: WinQSB
• GRUPO 8: TORA
• GRUPO 9: LINDO
• GRUPO 10: SOLVER
26
 MODELO DE ASIGNACIÓN

PROBLEMA DE ASIGNACION.
El problema de asignación es un tipo especial de
problema de programación lineal en el que los
asignados son recursos destinados a la realización
de tareas.
Por ejemplo, los asignados pueden ser empleados a
quienes se tiene que dar trabajo.
La asignación de personas a trabajos es una
aplicación común del problema de asignación. Sin
embargo, los asignados no tienen que ser personas.
También, pueden ser maquinas, vehículos, plantas a
los que se asignan tareas.
 MODELO DE ASIGNACIÓN

Para que un problema se ajuste a la definición de

problema de asignación se deben cumplir las
siguientes suposiciones:
1. El número de asignados es igual al número de
tareas. (este numero se denota por 𝑛).
2. Cada asignado se asigna a una tarea.
3. Cada tarea debe realizarla exactamente un
asignado.
4. Existe un costo 𝐶𝐼𝐽 asociado con el asignado i ( i =
1,2...,n) que realiza la tarea j (j = 1,2...n).
5. El objetivo es determinar como deben hacerse las
n asignaciones para minimizar los costos totales.
 MODELO DE ASIGNACIÓN

Modelo del problema de asignación y

procedimientos de solución.
El modelo matemático para el problema de
asignación usa las variables de decisión:
𝑥𝑖𝑗 = 1, si el asignado 𝑖 realiza la asignación 𝑗
𝑥𝑖𝑗 = 0, en caso contrario,
Para i = 1,2..., n y j = 1,2...n. Entonces, cada 𝑥𝑖𝑗 es
una variable binaria (toma valores 0 o 1). Estas
variables representan decisiones de si o no: ¿Debe el
asignado i realizar la tarea j?.
 MODELO DE ASIGNACIÓN

Sea Z el costo total, el modelo del problema de

asignación es:

Observe que la estructura es similar al modelo de

transporte. en donde los orígenes son ahora los
asignados, y los destinos son las asignaciones o
tareas .
 MODELO DE ASIGNACIÓN

donde:
Número de orígenes (m) = número de destinos (n).
Cada recurso 𝑠𝑖 = 1
Cada demanda 𝑑𝑖 =1.
Tabla de parámetros para el problema de asignación
formulado como un problema de transporte.
 MODELO DE ASIGNACIÓN

RESOLUCIÓN DE UN PROBLEMA DE
ASIGNACIÓN MEDIANTE EL MÉTODO HÚNGARO
EL PROBLEMA
La compañía de manufactura "Jiménez y Asociados"
desea realizar una jornada de mantenimiento preventivo
a sus tres máquinas principales A, B y C. El tiempo que
demanda realizar el mantenimiento de cada máquina es
de 1 día, sin embargo la jornada de mantenimiento no
puede durar más de un día, teniendo en cuenta que la
compañía cuenta con tres proveedores de servicios de
mantenimiento debe de asignarse un equipo de
mantenimiento a cada máquina para poder cumplir con
la realización del mantenimiento preventivo.
 MODELO DE ASIGNACIÓN

Teniendo en cuenta que según el grado de

especialización de cada equipo prestador de servicios
de mantenimiento el costo de la tarea varía para cada
máquina en particular, debe de asignarse el equipo
correcto a la máquina indicada con el objetivo de
minimizar el costo total de la jornada. Los costos
asociados se pueden observar en la siguiente tabla:
 MODELO DE ASIGNACIÓN

PASO 1
Encontramos el menor elemento de cada fila

PASO 2
Construimos una nueva matriz con las diferencias
entre los valores de la matriz original y el elemento
menor de la fila a la cual corresponde.
 MODELO DE ASIGNACIÓN

PASO 3
En la matriz construida en el paso anterior se procede a
efectuar el paso 1 esta vez en relación a las columnas,
por ende escogemos el elemento menor de cada columna.
Igualmente construimos una nueva matriz con la
diferencia entre los valores de la matriz 2 y el elemento
menor de la columna a la cual corresponde cada valor.
MODELO DE ASIGNACIÓN
 MODELO DE ASIGNACIÓN
PASO 4
En este paso trazaremos la menor cantidad de combinaciones
de líneas horizontales y verticales con el objetivo de cubrir
todos los ceros de la matriz de costos reducidos.

Como se puede observar el menor número de líneas

horizontales y/o verticales necesarias para cubrir los ceros de
la matriz de costos reducidos es igual a 2, por ende al ser
menor que el número de filas o columnas es necesario recurrir
al paso 5.
 MODELO DE ASIGNACIÓN

PASO 5
En este paso seleccionamos el menor elemento de
los elementos no subrayados.
 MODELO DE ASIGNACIÓN

Luego se procede a restarse de los elementos no

subrayados y a adicionarse a los elementos
ubicados en las intersecciones de las líneas, en este
caso existe una única intersección (3).
 MODELO DE ASIGNACIÓN

Ahora ya efectuado este paso pasamos al paso 4.

Ahora observamos cómo se hace necesario trazar

tres líneas (la misma cantidad de filas o columnas
de la matriz) por ende se ha llegado al tabulado
final, en el que por simple observación se determina
las asignaciones óptimas.
 MODELO DE ASIGNACIÓN

Por ende la asignación que representa el menor costo

para la jornada de mantenimiento preventivo determina
que el Equipo 1 realice el mantenimiento de la Máquina
1, el Equipo 2 realice el mantenimiento de la Máquina 3
y el Equipo 3 realice el mantenimiento de la Máquina 2,
jornada que tendrá un costo total de 17 unidades
monetarias.
 RESOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN MEDIANTE
PROGRAMACIÓN LINEAL

EL PROBLEMA
La compañía de manufactura "Jiménez y Asociados" desea
realizar una jornada de mantenimiento preventivo a sus tres
máquinas principales A, B y C. El tiempo que demanda realizar
el mantenimiento de cada máquina es de 1 día, sin embargo la
jornada de mantenimiento no puede durar más de un día,
teniendo en cuenta que la compañía cuenta con tres
proveedores de servicios de mantenimiento debe de asignarse
un equipo de mantenimiento a cada máquina para poder
cumplir con la realización del mantenimiento preventivo.
Teniendo en cuenta que según el grado de especialización de
cada equipo prestador de servicios de mantenimiento el costo
de la tarea varía para cada máquina en particular, debe de
asignarse el equipo correcto a la máquina indicada con el
objetivo de minimizar el costo total de la jornada.
 MODELO DE ASIGNACIÓN
Los costos asociados se pueden observar en la siguiente tabla:

VARIABLES DE DECISIÓN
Las variables de decisión de este tipo de problemas es igual a
las variables de cualquier modelo de transporte tradicional, es
decir variables Xij donde i {Equipo de mantenimiento 1,2,3} y j
{Máquina 1,2,3}, y corresponden a variables binarias en las
cuales el valor 1 significa la asignación de un equipo de
mantenimiento a una máquina en particular.
 MODELO DE ASIGNACIÓN

FUNCIÓN OBJETIVO
ZMIN = 10X1,1 + 9X1,2 + 5X1,3 + 9X2,1 + 8X2,2 + 3X2,3 +
6X3,1 + 4X3,2 + 7X3,3

RESTRICCIONES
Dado que un equipo de mantenimiento no puede ser
asignado a más de una maquinaria, esta
característica debe de restringirse mediante las
siguientes inecuaciones.
X1,1 + X1,2 + X1,3 = 1
X2,1 + X2,2 + X2,3 = 1
X3,1 + X3,2 + X3,3 = 1
 MODELO DE ASIGNACIÓN

Además debe restringirse el hecho de que cada

máquina solo requiere de un equipo de
mantenimiento, por ende
X1,1 + X2,1 + X3,1 = 1
X1,2 + X2,2 + X3,2 = 1
X1,3 + X2,3 + X3,3 = 1

Ejemplos: Archivo, problemas lineales

especiales.
 MODELO DE EMPAREJAMIENTO

Una situación similar con el problema de asignación

es el de construir parejas dentro de un conjunto. Si la
formación de parejas se establece entre individuos de
dos conjuntos distintos, problema denominado
emparejamiento bipartito, su formulación coincide
exactamente con el problema de asignación.
Ahora bien, otro problema distinto es el problema
general donde se plantea formar parejas dentro de un
mismo grupo, es decir, no se trata de asignar
elementos de dos grupos distintos, sino de hacer
parejas dentro de uno solo. Este problema es el que se
denomina emparejamiento y posee una formulación
distinta al problema de asignación.
 MODELO DE EMPAREJAMIENTO
Suponiendo que el grupo es un número par (si no lo es,
tendremos que introducir un elemento ficticio, como en el caso
anterior, quedará elemento sin pareja y se denomina
emparejamiento imperfecto) este problema pretende realizar
parejas teniendo en cuenta las preferencias de los individuos u
otras características. Ejemplos de este problema pueden ser
problemas tales como la formación de parejas de trabajo, o de
parejas para formar turnos, o repartir tareas, o asignar
dormitorios, etc.
EJEMPLO.
Supongamos un grupo de seis amigos que se van de viaje
juntos y deben formar parejas para dormir, pues las
habitaciones reservadas son tres habitaciones dobles. Las
preferencias de los mismos vienen dadas por la tabla siguiente.
 MODELO DE EMPAREJAMIENTO

El problema puede pensarse inicialmente como un

problema de asignación donde no es posible que nadie
quede emparejado consigo mismo y además si la persona 𝑖
está emparejado con 𝑗 , es evidente que 𝑗 debe estar
emparejada con 𝑖 . En consecuencia, aunque tendremos
menos variables que un problema de asignación (6 ∗ 6 − 6 =
30 variables), tendremos más restricciones, todas aquellas
que corresponden con los emparejamientos recíprocos.
 MODELO DE EMPAREJAMIENTO
Esto sería como:
𝒁𝒎𝒂𝒙 = 𝟐𝑿𝟏𝟐 + 3𝑿𝟏𝟑 + 5𝑿𝟏𝟒 + 2𝑿𝟏𝟓 + 4𝑿𝟏𝟔 + 4𝑿𝟐𝟏 + 6𝑿𝟐𝟑 + 7 𝑿𝟐𝟒 +
2𝑿𝟐𝟓 + 1𝑿𝟐𝟔 + 2𝑿𝟑𝟏 + 3𝑿𝟑𝟐 + 6𝑿𝟑𝟒 + 5𝑿𝟑𝟓 + 4𝑿𝟑𝟔 + 2𝑿𝟒𝟏 + 𝟓𝑿𝟒𝟐 +
𝟏𝑿𝟒𝟑 + 𝟑𝑿𝟒𝟓 + 𝟓𝑿𝟒𝟔 + 𝟒𝑿𝟓𝟏 + 𝟑𝑿𝟓𝟐 + 𝟔𝑿𝟓𝟑 + 𝟑𝑿𝟓𝟒 + 𝟔𝑿𝟓𝟔 + 𝟕𝑿𝟔𝟏 + 𝟐𝑿𝟔𝟐 +
𝟕𝑿𝟔𝟑 + 𝟓𝑿𝟔𝟒 + 𝟒𝑿𝟔𝟓
Sujeto a: 𝑿𝟏𝟐 + 𝑿𝟏𝟑 + 𝑿𝟏𝟒 + 𝑿𝟏𝟓 + 𝑿𝟏𝟔 = 𝟏
𝑿𝟐𝟏 + 𝑿𝟐𝟑 + 𝑿𝟐𝟒 + 𝑿𝟐𝟓 + 𝑿𝟐𝟔 = 𝟏
𝑿𝟑𝟏 + 𝑿𝟑𝟐 + 𝑿𝟑𝟒 + 𝑿𝟑𝟓 + 𝑿𝟑𝟔 = 𝟏
𝑿𝟒𝟏 + 𝑿𝟒𝟐 + 𝑿𝟒𝟑 + 𝑿𝟒𝟓 + 𝑿𝟒𝟔 = 𝟏
𝑿𝟓𝟏 + 𝑿𝟓𝟐 + 𝑿𝟓𝟑 + 𝑿𝟓𝟒 + 𝑿𝟓𝟔 = 𝟏
𝑿𝟔𝟏 + 𝑿𝟔𝟐 + 𝑿𝟔𝟑 + 𝑿𝟔𝟒 + 𝑿𝟔𝟓 = 𝟏
𝑿𝟐𝟏 + 𝑿𝟑𝟏 + 𝑿𝟒𝟏 + 𝑿𝟓𝟏 + 𝑿𝟔𝟏 = 𝟏
𝑿𝟏𝟐 + 𝑿𝟑𝟐 + 𝑿𝟒𝟐 + 𝑿𝟓𝟐 + 𝑿𝟔𝟐 = 𝟏
𝑿𝟏𝟑 + 𝑿𝟐𝟑 + 𝑿𝟒𝟑 + 𝑿𝟓𝟑 + 𝑿𝟔𝟑 = 𝟏
𝑿𝟏𝟒 + 𝑿𝟐𝟒 + 𝑿𝟑𝟒 + 𝑿𝟓𝟒 + 𝑿𝟔𝟒 = 𝟏
𝑿𝟏𝟓 + 𝑿𝟐𝟓 + 𝑿𝟑𝟓 + 𝑿𝟒𝟓 + 𝑿𝟔𝟓 = 𝟏
𝑿𝟏𝟔 + 𝑿𝟐𝟔 + 𝑿𝟑𝟔 + 𝑿𝟒𝟔 + 𝑿𝟓𝟔 = 𝟏
 MODELO DE EMPAREJAMIENTO

El modelo matemático planteado se encuentra listo para ser

aplicado en el modelo de programación lineal; sin embargo,
existe un método de solución muy amigable denominado
asignación.
Se le agradece su
atención!
 MODELO DE TRANSPORTE

Representación del modelo de transporte con nodos

y arcos.
 MODELO DE TRANSPORTE

DEFINICIÓN
El problema de transporte recibe este nombre
debido a que muchas de sus aplicaciones involucran
determinar la manera óptima de transportar bienes.
Modelo del problema de transporte.
El problema general de transporte se refiere a la
distribución de cualquier bien desde cualquier
grupo de centros de suministro, llamados orígenes,
a cualquier grupo de centros de recepción, llamados
destinos, de tal manera que se minimicen los costos
totales de distribución. La terminología utilizada en
estos problemas se resume en la siguiente tabla:
 MODELO DE TRANSPORTE

Problema general Ejemplo

Unidades de un bien Cargas de latas de tomate
𝑚 orígenes Cuatro enlatadoras
𝑛 destinos Cuatro almacenes
𝑠𝑖 recursos en el origen 𝑖 Producción de la enlatadora 𝑖
Demanda 𝑑𝑗 en el destino 𝑗 Asignación al almacén 𝑗
Costo 𝑐𝑖𝑗 por unidad distribuida Costo de envío por carga desde la
desde el origen 𝑖 al destino 𝑗 enlatadora 𝑖 al almacén 𝑗
Como se indica en la tabla, cada origen tiene cierto suministro
de unidades que distribuir a los destinos, y cada destino tiene
cierta demanda de unidades que deben recibirse de los
orígenes. Las suposiciones sobre suministros y demandas son
las siguientes:
 MODELO DE TRANSPORTE
Suposición de requerimientos: Cada origen tiene un
suministro fijo de unidades y el suministro completo
debe distribuirse a los destinos. ( 𝑠𝑖 es el número de
unidades que suministra el origen 𝑖). De igual manera, el
destino tiene una demanda fija de unidades, y debe
satisfacerse desde los orígenes, ( 𝑑𝑗 es el numero de
unidades recibidas por el destino 𝑗 ). Un problema de
transporte tiene soluciones factibles si y solo si:
𝑚 𝑛

෍ 𝑠𝑖 = ෍ 𝑑𝑗
𝑖=1 𝑗=1
Esta suposición significa que es necesario un balance
entre el suministro total de todos los orígenes y la
demanda total de todos los destinos.
 MODELO DE TRANSPORTE
Algunos problemas reales no se ajustan por completo al
problema de transporte porque violan la suposición de
requerimientos. Sin embargo, es posible reformular el
problema de manera que se ajuste al modelo con la
introducción de un destino ficticio o un origen ficticio
para que se haga cargo de la holgura entre las
cantidades reales distribuidas.
Suposición de costo: el costo de distribuir unidades de
un origen a un destino dado es directamente
proporcional al número de unidades distribuidas. Por lo
tanto este costo es justo el costo unitario de
distribución multiplicado por el número de unidades
distribuidas. (el costo unitario del origen 𝑖 al destino 𝑗 se
denota por 𝑐𝑖𝑗 ).
 MODELO DE TRANSPORTE

Los únicos datos necesarios para un problema de

transporte son suministros, demandas y costos
unitarios. Estos son los parámetros del modelo.
Todos estos parámetros se pueden resumir en la
siguiente tabla de parámetros.
 MODELO DE TRANSPORTE

Cualquier problema que se ajusta al modelo de

problema de transporte debe satisfacer la suposición
de requerimientos, como la de costo. El objetivo es
minimizar el costo total de distribuir las unidades.
 MODELO DE TRANSPORTE

Los dos objetivos comunes de estos problemas son:

1. Minimizar el costo de enviar n unidades hasta m
destinos, o
2. Maximizar las utilidades de enviar n unidades a
m destinos.
Una compañía tiene cuatro enlatadoras que
abastecen a cuatro almacenes y la gerencia quiere
determinar la programación de envío de costo
mínimo para su producción mensual de latas de
tomate. La oferta de las enlatadoras, las demandas
de los almacenes y los costos de envío por caja de
latas de tomate se muestran en la Tabla 1.
 MODELO DE TRANSPORTE

De acuerdo con el modelo presentado

anteriormente, en este problema se trata de
seleccionar valores de estas 16 variables de decisión
(las 𝑥𝑖𝑗 ) para:
MODELO DE TRANSPORTE
 MODELO DE TRANSPORTE

Ejemplo.
MG Auto cuenta con tres plantas en Los Ángeles, Detroit
y Nueva Orleáns, y dos importantes centros de
distribución en Denver y Miami. Las capacidades
trimestrales de las tres plantas son 1000, 1500 y 1200
automóviles, y las demandas de los dos centros de
distribución durante el mismo periodo son de 2300 y
1400 automóviles. La distancia en millas entre las
plantas y los centros de distribución aparece en la tabla
1.
TABLA 1. Gráfica de distancia en millas
Denver Miami
Los Ángeles 1.000 2.690
Detroit 1.250 1.350
Nueva Orleáns 1.275 850
 MODELO DE TRANSPORTE

La compañía transportista cobra 8 centavos por

milla por automóvil.
En la tabla 2 se dan los costos de transporte por
automóvil en las diferentes rutas, redondeados al
dólar más cercano.
TABLA 2. Costo de transporte por automóvil
Denver (1) Miami (2)
Los Ángeles (1) $ 80 $ 215
Detroit (2) $ 100 $ 108
Nueva Orleáns (3) $ 102 $ 68
 MODELO DE TRANSPORTE

Todas estas restricciones son ecuaciones porque la oferta

total desde los tres orígenes (= 1,000 +1,500 + 1,200 =
3,700 automóviles) es igual a la demanda total en los dos
destinos (= 2,300 + 1,400 = 3,700 automóviles).
 MODELO DE TRANSBORDO

El Problema de Transbordo, Intertransporte o

Reembarque es una variación del modelo original de
transporte que se ajusta a la posibilidad común de
transportar unidades mediante nodos fuentes,
destinos y transitorios. Existe la posibilidad de
resolver un modelo de transbordo mediante las
técnicas tradicionales de resolución de modelos de
transporte y este procedimiento se basa en la
preparación del tabulado inicial haciendo uso de
artificios conocidos con el nombre
de amortiguadores, los cuales deben ser iguales a
la sumatoria de las ofertas de los nodos de oferta
pura y de coeficiente cero (0) en materia de costos.
 MODELO DE TRANSBORDO

La importancia de los modelos de transbordo

aumenta con las nuevas tendencias globales de
gestión de cadenas de abastecimiento, en las cuales
se deben de optimizar los flujos logísticos de
productos teniendo en cuenta la importancia de
minimizar los costos, asegurar disponibilidad de
unidades y reconociendo la importancia de los
centros de distribución en la búsqueda del equilibrio
entre las proyecciones y la realidad de la demanda.
MODELO DE TRANSBORDO
 MODELO DE TRANSBORDO

RESOLUCIÓN DE UN PROBLEMA DE TRANSBORDO

MEDIANTE PROGRAMACIÓN LINEAL
Para poder resolver un problema de transbordo
mediante programación lineal basta con conocer una
nueva familia de restricciones, las llamadas
restricciones de balanceo. En un problema de
transbordo existen 3 clases de nodos, los nodos de
oferta pura, los de demanda pura y los nodos
transitorios que posibilitan el transbordo y que deben
de balancearse para hacer que el sistema sea viable,
es decir, que todas las unidades que ingresen a un
nodo sean iguales a las que salgan del mismo
(unidades que salen + unidades que conserve el nodo).
 MODELO DE TRANSBORDO

EL PROBLEMA
Modelar mediante programación lineal el problema
de transbordo esbozado en la siguiente figura
 MODELO DE TRANSBORDO

La figura muestra una serie de nodos y sus

respectivas rutas mediante las cuales se supone
distribuir las unidades de un producto, el número
que lleva cada arco (flecha) representa el costo
unitario asociado a esa ruta (arco), y las cantidades
que se ubican en los nodos iniciales representan la
oferta de cada planta, así como las cantidades de los
nodos finales representa la demanda de cada
distribuidor.
LAS VARIABLES DE DECISIÓN
En este caso como en la mayoría las variables de
decisión deben representar la cantidad de unidades
enviadas por medio de cada ruta.
MODELO DE TRANSBORDO
 MODELO DE TRANSBORDO
Una vez renombrado cada nodo definiremos las variables:
XA,C = Cantidad de unidades enviadas desde P1 hacia T1
XA,D = Cantidad de unidades enviadas desde P1 hacia T2
XB,C = Cantidad de unidades enviadas desde P2 hacia T1
XB,D = Cantidad de unidades enviadas desde P2 hacia T2
XC,D = Cantidad de unidades enviadas desde T1 hacia T2
XC,E = Cantidad de unidades enviadas desde T1 hacia D1
XC,F = Cantidad de unidades enviadas desde T1 hacia D2
XD,F = Cantidad de unidades enviadas desde T2 hacia D2
XD,G = Cantidad de unidades enviadas desde T2 hacia D3
XE,F = Cantidad de unidades enviadas desde D1 hacia D2
XF,G = Cantidad de unidades enviadas desde D2 hacia D3
 MODELO DE TRANSBORDO

FUNCIÓN OBJETIVO
En este caso la definición de la función objetivo se limita
a la consignación de cada ruta con su respectivo costo
bajo el criterio "minimizar".
ZMIN = 3XA,C + 4XA,D + 2XB,C + 5XB,D + 7XC,D + 8XC,E +
6XC,F + 4XD,F + 9XD,G + 5XE,F + 3XF,G
RESTRICCIONES
Existen en este modelo 3 tipos de restricciones y están
estrechamente relacionadas con los tipos de nodos
existentes, para un nodo oferta pura existe la restricción
de oferta; para un nodo demanda pura existe la
restricción de demanda, y para un nodo transitorio y/o
transitorio de demanda existe la restricción de balance.
 MODELO DE TRANSBORDO
Recordemos que los nodos transitorios son aquellos que
tienen rutas (arcos o flechas) de entrada y salida, y si
además este presenta un requerimiento de unidades se
denomina transitorio de demanda.
Restricciones de Oferta:
XA,C + XA,D = 1000
XB,C + XB,D = 1200
Restricciones de demanda:
XD,G + XF,G = 500
Restricciones de balanceo para nodos transitorios:
Con estas restricciones aseguramos que todas las
unidades que lleguen sean iguales a las unidades que
salgan.
XA,C + XB,C - XC,D - XC,E - XC,F = 0
XA,D + XB,D + XC,D - XD,F - XD,G = 0
 MODELO DE TRANSBORDO

Recordemos que los nodos transitorios son aquellos

que tienen rutas (arcos o flechas) de entrada y
salida, y si además este presenta un requerimiento
de unidades se denomina transitorio de demanda.
Restricciones de balanceo para nodos transitorios
con requerimientos:
Con estas restricciones aseguramos que todas las
unidades que lleguen sean iguales a la sumatoria de las
unidades que salen más los requerimientos del nodo
(demanda).
XC,E - XE,F = 800
XC,F + XD,F + XE,F - XF,G = 900
 MODELO DE TRANSBORDO
Direct R.H.S
VARIABLE Xac Xad Xbc Xbd Xcd Xce Xcf Xdf Xdg Xef Xfg
ion .

MINIMIZE 3 4 2 5 7 8 6 4 9 5 3

RESTRICCIÓN 1 1 1 = 1000
RESTRICCIÓN 2 1 1 = 1200
RESTRICCIÓN 3 1 1 = 500
RESTRICCIÓN 4 1 1 -1 -1 -1 = 0
RESTRICCIÓN 5 1 1 1 -1 -1 = 0
RESTRICCIÓN 6 1 -1 = 800
RESTRICCIÓN 7 1 1 1 -1 = 900
LOWERBOUND 0 0 0 0 0 0 0 0 0 0 0

UPPERBOUND M M M M M M M M M M M

Conti Conti Conti Conti Conti Conti Conti Conti Conti Conti Conti
nuous nuous nuous nuous nuous nuous nuous nuous nuous nuous nuous
VARIABLE TYPE
 MODELO DE TRANSBORDO

Esta es la representación gráfica de la solución cuyo costo

óptimo es de 20.700 unidades monetarias
 MODELO DE TRANSBORDO
EL PROBLEMA
Este es un problema que hace referencia a una red de gasoductos en la que los
distintos nodos representan estaciones de bombeo y recepción, los costos se
encuentran en las rutas de la siguiente figura.
 MODELO DE TRANSBORDO

VARIABLES DE DECISIÓN

X12 = Cantidad de galones enviados desde la estación 1, hacia la estación 2

X17 = Cantidad de galones enviados desde la estación 1, hacia la estación 7
X37 = Cantidad de galones enviados desde la estación 3, hacia la estación 7
X34 = Cantidad de galones enviados desde la estación 3, hacia la estación 4
X72 = Cantidad de galones enviados desde la estación 7, hacia la estación 2
X75 = Cantidad de galones enviados desde la estación 7, hacia la estación 5
X57 = Cantidad de galones enviados desde la estación 5, hacia la estación 7
X62 = Cantidad de galones enviados desde la estación 6, hacia la estación 2
X65 = Cantidad de galones enviados desde la estación 6, hacia la estación 5
X56 = Cantidad de galones enviados desde la estación 5, hacia la estación 6
X54 = Cantidad de galones enviados desde la estación 5, hacia la estación 4
 MODELO DE TRANSBORDO

FUNCIÓN OBJETIVO
ZMIN = 20X12 + 3X17 + 9X37 + 30X34 + 40X72 + 10X75 + 10X57 + 8X62 +
4X65 + 4X56 + 2X54
RESTRICCIONES
Restricciones de oferta y demanda:
X12 + X17 ≤ 50000
X37 + X34 ≤ 60000
X12 + X72 + X62 = 90000
X34 + X54 =20000
Restricciones de balance
X17 + X37 + X57 - X72 - X75 = 0
X56 - X65 - X62 = 0
X75 + X65 - X57 - X56 - X54 = 0
 MODELO DE TRANSBORDO

Direc
VARIABLE X12 X17 X37 X34 X72 X57 X75 X62 X56 X65 X54 R.H.S.
tion

MINIMIZE 20 3 9 30 40 10 10 8 4 4 2

OFERTA ESTACIÓN 1 1 1 ≤ 50000

OFERTA ESTACIÓN 2 1 1 ≤ 60000
DEMANDA ESTACIÓN 2 1 1 1 = 90000
DEMANDA ESTACIÓN 4 1 1 = 20000
BALANCEO ESTACIÓN 7 1 1 -1 1 -1 = 0
BALANCEO ESTACIÓN 5 -1 1 -1 1 -1 = 0
BALANCEO ESTACIÓN 6 -1 1 -1 = 0
LOWERBOUND 0 0 0 0 0 0 0 0 0 0 0

UPPERBOUND M M M M M M M M M M M

Conti Conti Conti Conti Conti Conti Conti Conti Conti Conti Conti
nuous nuous nuous nuous nuous nuous nuous nuous nuous nuous nuous
VARIABLE TYPE
 MODELO DE TRANSBORDO
Esta es la representación grafica de la solución cuyo costo óptimo es de 2'660.000
unidades monetarias
 MODELO DE TRANSBORDO
PROBLEMA DE LA RUTA MÁS CORTA

Ya el nombre de este tipo de problemas es bastante sugestivo,

se trata si es necesario decirlo de una modalidad de problemas
de redes en el cual se debe determinar el plan de rutas que
genere la trayectoria con la mínima distancia total que una un
nodo fuente con un nodo destino, sin importar el número de
nodos que existan entre estos.

Esta modalidad de problemas puede solucionarse como un

modelo de transbordo normal, sin embargo la principal
sugerencia es la de establecer una oferta en el nodo fuente igual
a una unidad (1) y establecer una demanda en el arco destino
igual a una unidad (1).
 MODELO DE TRANSBORDO
PROBLEMA DE LA RUTA MÁS CORTA

EL PROBLEMA
Un minero ha quedado atrapado en una mina, la entrada a la mina
se encuentra ubicada en el nodo 1, se conoce de antemano que el
minero permanece atrapado en el nodo 9, para llegar a dicho nodo
hay que atravesar una red de túneles que van conectados entre sí.
El tiempo de vida que le queda al minero sin recibir auxilio es cada
vez menor y se hace indispensable hallar la ruta de acceso al nodo
9 más corta. Las distancias entre nodos de la mina se encuentran
en la siguiente gráfica dadas en cientos de metros. Formule un
modelo de transbordo y resuelva mediante cualquier paquete de
herramientas de investigación operativa que permita establecer la
ruta más corta para poder así auxiliar al minero.
MODELO DE TRANSBORDO
PROBLEMA DE LA RUTA MÁS CORTA

6
 MODELO DE TRANSBORDO
VARIABLES
X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2
X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3
X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3
X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4
X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2
X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4
X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5
X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6
X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7
X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4
X56 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6
X57 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7
X58 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8
X67 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7
X69 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9
X76 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6
X78 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8
X79 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9
X87 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7
X89 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9
 MODELO DE TRANSBORDO
FUNCIÓN OBJETIVO
ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 +
1X46 + 5X47 + 2X54 + 4X56 + 3X57 + 2X58 + 1X67 + 5X69 +
4X76 + 3X78 + 5X79 + 2X87 + 7X89

RESTRICCIONES
Restricciones de Oferta y Demanda
Hay que recordar que el objetivo de este modelo es la consecución
de un plan de ruta que nos permita encontrar al minero lo más
pronto posible al recorrer la distancia mínima posible, por ende la
clave para plantear el modelo como si fuese de transbordo es
establecer una demanda y oferta igual a la unidad (1).

X12 + X13 = 1
X69 + X79 + X89 = 1
 MODELO DE TRANSBORDO
Restricciones de Balance
X12 + X32 - X23 - X24 = 0
X13 + X23 - X32 - X34 - X35 = 0
X24 + X34 + X54 - X46 - X47 = 0
X35 - X54 - X56 – X57 – X58 = 0
X46 + X56 + X76 - X67 – X69 = 0
X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0
X78 + X58 – X89 – X87 = 0
En palabras sencillas: "Todo lo que entra a cada nodo es igual a lo
que sale de él"
La ruta más corta para rescatar al minero tiene como distancia
total 1600 metros (dado que las distancias estaban dadas en
cientos de metros) y es tal como se muestra en la siguiente
gráfica.
MODELO DE TRANSBORDO

6
Se le agradece su
atención!