Como-plantear-de-una-manera-adecuada-el-problema-de-flujo-maximo

Vista previa del material en texto

1 
 
 
 
 
 
UNIVERSIDAD NACIONAL AUTÓNOMA 
 DE MÉXICO 
 
 FACULTAD DE CIENCIAS 
 
 
¿CÓMO PLANTEAR DE UNA MANERA ADECUADA 
EL PROBLEMA DE FLUJO MÁXIMO? 
 
 
 
 
 
 
 
 
T E S I S 
 
 QUE PARA OBTENER EL TÍTULO DE: 
 A C T U A R I A 
 P R E S E N T A : 
 CITLALLI ALEJANDRA JIMÉNEZ DE LARA 
HERNÁNDEZ 
 
 
 
 
 
 
 
 
DIRECTOR DE TESIS: 
M. EN I. NEREO ELÍAS MATA 
2012 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
 
 
2 
 
1. Datos del alumno 1. Datos del alumno 
Apellido paterno Jiménez de Lara 
Apellido materno Hernández 
Nombre(s) Citlalli Alejandra 
Teléfono (442) 2 99 34 24 
Universidad Nacional Autónoma de 
México 
Universidad Nacional Autónoma de 
México 
Facultad de Ciencias Facultad de Ciencias 
Carrera Actuaría 
Número de cuenta 404114837 
 
2. Datos del tutor 2. Datos del tutor 
Grado M en I 
Nombre(s) Nereo 
Apellido paterno Elías 
Apellido materno Mata 
 
3. Datos del sinodal 1 3. Datos del sinodal 1 
Grado Dra 
Nombre(s) Bibiana 
Apellido paterno Obregón 
Apellido materno Quintana 
 
4. Datos del sinodal 2 4. Datos del sinodal 2 
Grado Dra 
Nombre(s) Esther 
Apellido paterno Segura 
Apellido materno Pérez 
 
5. Datos del sinodal 3 5. Datos del sinodal 3 
Grado M en I 
Nombre(s) José Antonio 
Apellido paterno Climent 
Apellido materno Hernández 
 
6. Datos del sinodal 4 6. Datos del sinodal 4 
Grado Act 
Nombre(s) María Isabel 
Apellido paterno Salazar 
Apellido materno Solano 
 
7. Datos del trabajo escrito 7. Datos del trabajo escrito 
Título ¿Cómo plantear de una manera 
adecuada el problema de flujo máximo? 
Número de páginas 108 p 
Año 2012 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
3 
 
Dedicado: 
 
 A Dios , por darme la oportunidad de vivir y por estar conmigo en cada paso que 
doy, por fortalecer mi corazón e iluminar mi mente y por haber puesto en mi 
camino a aquellas personas que han sido mi soporte y compañía durante todo mi 
vida. 
 
A mis padres: José Arturo Jiménez de Lara Solís y Gloria Guillermina 
Hernández Mora por haberme apoyado en todo momento, por sus consejos, sus 
valores, por la motivación constante que me ha permitido ser una persona de bien, 
por enseñarme a buscar y lograr mis sueños, pero más que nada, por su amor. 
A mi esposo: Paris Fabricio Ponce Martínez por los ejemplos de perseverancia 
y constancia que lo caracterizan, por el valor mostrado para salir adelante, por su 
incondicional apoyo perfectamente mantenido a través del tiempo y por su amor. 
Todo este trabajo ha sido posible gracias a ellos. 
 
 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
4 
 
Agradecimientos: 
 
La presente tesis es un esfuerzo en el cual, directa o indirectamente, participaron 
varias personas leyendo, opinando, corrigiendo, teniéndome paciencia, dando 
ánimo, acompañando en los momentos de crisis y en los momentos de felicidad. 
 
Agradezco a M en I Nereo Elías Mata por haber confiado en mi persona, por la 
paciencia y por la dirección de este trabajo. A Alejandra Pliego por los consejos y 
el apoyo. A todos mis sinodales por sus comentarios y correcciones para lograr la 
finalización de esta tesis. 
 
También quiero agradecer a las familias Díaz Bravo y Bravo Sánchez por haberme 
acogido por más ocho años en sus casas dándome su apoyo, comprensión y 
ánimo. A todos mis amigos que juntos nos apoyamos para sacar adelante 
exámenes, trabajos y dificultades que se nos presentaron durante el camino para 
lograr la universidad. 
 
Gracias a todos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
5 
 
 
 
 
 
 
 
 
 
 
 
Índice 
 
Introducción………………………………………………………....................... 6 
Capítulo 1 
1.1 Investigación de operaciones…………………………………………….. 9 
1.2 Programación lineal……………………………………………………….... 13 
1.3 Teoría de gráficas o teoría de redes…………………………………….. 14 
Capítulo 2 
2.1 Formulación del problema de programación lineal…………………... 15 
2.2 Modelo de un problema de programación lineal…………………..….. 16 
2.2.1 Forma general……………………………………………………..………. 16 
2.2.2 Forma canónica…………………………………………………..……….. 17 
2.2.3 Forma estándar……………………………………………………………. 17 
2.3 Solución de un problema de programación lineal…………………….. 19 
2.3.1 Ejercicio de programación lineal………………………………………. 19 
2.4 Interpretación económica de los costos reducidos………………….. 27 
Capítulo 3 
3.1 Construcción del problema dual…………………………………………. 29 
3.2 La relación entre los problemas primal y dual………………………… 34 
3.3 Solución del problema dual……………………………………………….. 35 
3.4 Interpretación económica del problema dual y el precio dual……… 37 
Capítulo 4 
4.1 El problema de flujo máximo……………………………………………… 41 
4.2 Modelo de programación lineal de flujo máximo……………………… 42 
4.3 Obtención de la cortadura mínima………………………………………. 48 
4.3.1 Problema dual correspondiente al problema primal en forma 
estándar…………………………………………………………………………… 53 
4.3.2 Problema dual correspondiente al problema primal en forma 
canónica…………………………………………………………………………… 58 
4.4 Forma canónica y estándar del problema de la refinería……………. 59 
4.4.1 Forma canónica…………………………………………………………… 61 
4.4.1.1 Interpretación de los costos reducidos…………………………….. 64 
4.4.1.2 Interpretación de los precios duales………………………………... 66 
4.4.2 Forma estándar……………………………………………………………. 70 
4.4.2.1 Interpretación de los costos reducidos…………………………….. 72 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
6 
 
4.4.2.2 Interpretación de los precios duales………………………………... 73 
4.5 Ejercicio de las casetas……………………………………………………. 75 
4.5.1 Forma estándar……………………………………………………………. 76 
4.5.1.1 Interpretación de los costos reducidos…………………………….. 79 
4.5.1.2 Interpretación de los precios duales………………………………... 81 
4.5.2 Forma canónica…………………………………………………………… 84 
4.6 Comparación entre la forma canónica y la forma estándar…………. 89 
4.7 Conclusiones………………………………………………………………… 93 
Anexo 1 Definiciones……………………………………………………………. 95 
Anexo 2 Teoremas………………………………………………………………. 98 
Anexo 3 Demostraciones de teoremas de las cortaduras……………….. 105 
Bibliografía………………………………………………………………………… 107 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
7 
 
 
Introducción 
 
Una red es un conjunto de nodos y aristas que unen un inicio y un final, 
constituyen una entrada y una salida por la cual pueden moverse o fluir toda clase 
de recursos. 
 
Entre los problemas que se presentan en la investigación de operaciones, el 
llamado “problema de flujo máximo” resulta ser un caso particular, el cual, consiste 
en enviar el mayor flujo posible a lo largo de una red. 
 
Los problemasde programación lineal se puede plantear de dos maneras 
diferentes y en particular el problema de flujo máximo: la forma estándar y la forma 
canónica. Existe la postura en la literatura general de que estos problemas pueden 
ser abordados ya sea de manera estándar o canónica y obtener los mismos 
resultados. 
 
Sin embargo, en el desarrollo de este trabajo se mostrará con algunos ejemplos 
que en la forma estándar, las variables duales (precios duales) no coinciden con 
las definiciones de variables duales que se presentan en la literatura para la 
construcción del problema dual, como lo hacen Mokhtar S. Bazaraa y Jonh J. 
Javis [ 5 ]; Saul I. Gass [10 ] y Hamdy A. Taha [ 4 ]). 
 
Lo anterior, implica necesariamente que la interpretación del problema dual 
(cortadura mínima) no sea adecuada, lo que conduce a plantear el problema en la 
forma canónica. Para ello es necesario volver a analizar los valores de las 
variables duales y la definición se explica de una manera correcta. 
 
El propósito de esta tesis es exponer que la mejor forma de plantear un problema 
de flujo máximo es en la forma canónica, para ello se utiliza el programa LINDO 
como una herramienta para poder resolver los problemas planteados. 
 
El capítulo uno de esta tesis trata sobre las definiciones generales de la 
investigación de operaciones, programación lineal y teoría de redes; ya que el 
problema de flujo máximo es un caso particular de éstas; así como una breve 
reseña respecto de la investigación de operaciones desde su origen hasta 
nuestros días, con el objeto de poder comprender la importancia de este 
problema. 
 
En capítulo dos se formulan y muestran los diferentes modelos y solución de un 
problema de programación lineal como un problema primal, mediante un ejercicio 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
8 
 
de transporte el cual se plantea en forma estándar y canónica, y del que se 
obtiene e interpreta su solución y los costos reducidos. 
El capítulo tres presenta la construcción y solución del problema dual del problema 
primal; la relación entre el problema primal y dual; así como la interpretación 
económica del problema dual y el precio dual usando el ejercicio de transporte del 
capítulo anterior para llevar una continuidad de los resultados y así poder entender 
mejor lo que se busca exponer. 
 
Toda esta información que se proporciona en los capítulos antes mencionados es 
necesaria para poder entender el capítulo cuatro, que trata sobre el planteamiento 
y solución del problema primal y del problema dual de flujo máximo en su forma 
canónica y su forma estándar; la interpretación de los costos reducidos y precios 
duales y la comparación entre forma estándar y la forma canónica. 
 
Se consideran tres problemas: 
 
El primero, es una red de siete nodos con sus respectivas capacidades de flujo en 
sus enlaces y donde se requiere encontrar la forma óptima para llevar mayor flujo 
del nodo s al nodo t. 
 
El segundo, se refiere a una refinería donde el nodo 1 representa la refinería y el 
nodo 6 la terminal; los nodos restantes representan las estaciones de bombeo. 
Las capacidades de las ramas que parten del nodo 1 se pueden considerar como 
la producción de la refinería, por otra parte, las capacidades de las ramas que van 
al destino, es decir, a la terminal se puede considerar la demanda del petróleo y 
las ramas de las estaciones de bombeo son las tuberías que transportan el 
petróleo. Cada rama tiene una capacidad y se busca llevar la cantidad máxima de 
petróleo de la refinería a la terminal. El último problema trata de colocar casetas 
de inspección de la ciudad A a la ciudad B de tal manera que todo automóvil pase 
por lo menos una de ellas en su trayectoria de A a B. El costo de construcción de 
las casetas varía según su localización, el costo asociado con cada tramo se 
proporciona en cada arco de la red y se desea determinar dónde deberán 
colocarse las casteas si se quiere incurrir en el mínimo costo. 
 
El último rubro, se integra por las conclusiones obtenidas durante el desarrollo de 
esta tesis. 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
9 
 
 
 CAPÍTULO 1 
 
En la investigación de operaciones, “decidir” es un proceso de selección de cursos 
de acción. Tiene como fin, de acuerdo con ciertos criterios, que los resultados 
esperados se acerquen lo más posible a objetivos y metas establecidas bajo los 
entornos dados por los posibles estados de la naturaleza. 
 
La resolución de cualquier problema de programación lineal no puede ser resuelto 
de manera improvisada, sino que requiere para su solución óptima realizarse bajo 
los principios de la metodología científica. 
 
La metodología científica es la aplicación secuencial de la observación de un 
sistema, identificación y definición del problema, formulación de una hipótesis de 
solución (construcción de un modelo), experimentación (solución del modelo) y 
verificación de resultados. En esta metodología, existe una variedad extensa de 
herramientas que permiten incrementar la probabilidad de tomar mejores 
decisiones en cualquier organización. Cabe mencionar que entre esta gama de 
herramientas se encuentran, por ejemplo, los sistemas de información, los 
métodos estadísticos, las técnicas tradicionales de la ingeniería industrial, la 
evaluación económica, el procesamiento de datos, la investigación de 
operaciones, etc. 
 
Por ello, es importante conocer con exactitud las definiciones de Investigación de 
operaciones, programación lineal y la Teoría de gráficas o Teoría de redes, ya que 
estas son las herramientas que son necesito para abordar un problema de flujo 
máximo. 
 
1.1 Investigación de operaciones 
 
La investigación operativa es una moderna disciplina científica que se caracteriza 
por la aplicación de teoría, métodos y técnicas especiales, para buscar la solución 
de problemas de administración, organización y control que se producen en los 
diversos sistemas que existen en la naturaleza y los creados por el ser humano, 
tales como las organizaciones a las que identifica como sistemas organizados, 
sistemas físicos, económicos, ecológicos, educacionales, de servicio social, etc. 
 
Las primeras actividades formales de la investigación de operaciones se dieron en 
Inglaterra durante la Segunda Guerra Mundial, cuando se encomendó a un equipo 
de científicos ingleses la toma de decisiones acerca de la mejor utilización de 
materiales bélicos. Al término de la guerra, las ideas formuladas en operaciones 
militares fueron adaptadas para mejorar la eficiencia y la productividad en el sector 
civil. 
 
El enfoque fundamental de la investigación operativa es el enfoque de sistemas, 
por el cual, a diferencia del enfoque tradicional, se estudia el comportamiento de 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
10 
 
todo un conjunto de partes o sub-sistemas que interaccionan entre sí, se identifica 
el problema y se analizan sus repercusiones, buscando soluciones integrales que 
benefician al sistema como un todo. 
 
El objetivo más importante de la aplicación de la investigación operativa es apoyar 
en la “toma óptima de decisiones” a los sistemas y en la planificación de sus 
actividades. 
 
La investigación de operaciones es una ciencia interdisciplinaria y tiene un rol 
importante en los problemas de toma de decisiones porque permite tomar las 
mejores decisiones para alcanzar un determinado objetivo respetando los vínculos 
externos, no controlables por quien debe tomar la decisión; consiste en la 
aplicación del método científico, por parte de grupos interdisciplinarios, a 
problemas de control de sistemas organizativos con la finalidad de encontrar 
soluciones que atiendan de la mejor manera posible a los objetivos dela 
organización en su conjunto. 
 
La investigación de operaciones puede ser utilizada en la programación lineal 
(planificación del problema); en la programación dinámica (planificación de las 
ventas); en la teoría de las colas (para controlar problemas de tránsito), etc. 
 
Entre algunos de los métodos utilizados por la investigación de operaciones, 
aquellos que toman la decisión utilizan las matemáticas y las computadoras para 
tomar decisiones racionales en la resolución de problemas, además de la 
experiencia. 
 
Para resolver estos problemas la investigación de operaciones los agrupa en dos 
categorías básicas: 
 
1. Problemas Determinísticos: son aquellos en que la información necesaria 
se conoce para obtener una solución con certeza. 
 
2. Problemas Estocásticos: son aquellos en los que parte de la información 
necesaria no se conoce con certeza, como es el caso de los 
determinísticos, sino que más bien se comporta de una manera 
probabilística. 
La elaboración del problema está subdividida en fases que consisten en el método 
científico, las principales son: 
1. Examen de la situación real y recolección de la información; 
2. Formulación del problema, identificación de las variables controlables y las 
externas (no controlables) y la elección de la función objetivo, a ser 
maximizada o minimizada; 
3. Construcción del modelo matemático, destinado a dar una buena 
representación del problema; debe ser fácil de usar; representar el 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
11 
 
problema, dando toda la información para poder tomar una decisión lo más 
idónea posible; 
4. Resolución del modelo (mediante diferentes modalidades); 
5. Análisis y verificación de las soluciones obtenidas: se controla si la función 
objetivo ofrece las ventajas esperadas; se verifica la representación del 
modelo; y, se efectúan análisis de sensibilidad de la solución obtenida. 
6. Utilización del sistema obtenido para su posterior uso [Juan Prawda, 1976, 
vol 1. http://www.investigacion-operaciones.com/Formulacion%20Problemas.htm, 
27-07-2011] 
 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.investigacion-operaciones.com/Formulacion%20Problemas.htm,
http://www.novapdf.com/
http://www.novapdf.com/
 
 
12 
 
MAPA CONCEPTUAL DEL ÁREA DE OPERACIONES 
 
Personas capaces de definir un problema 
 
 
 
 
 
 
 
Diagnóstico 
Planeación 
de la 
Producción 
Distribución Asignación 
de recursos 
limitados 
Inventarios Programación 
de Actividades 
Pronósticos 
de Demanda 
Medio 
Ambiente 
Análisis de 
Líneas de 
Espera 
Analisis de 
Sistemas de 
Producción 
Que el área de sistemas lo proporcione 
Información Cuantitativa y 
Cualitativa del Sistema bajo estudio 
Selección del Modelo 
Modelos Determinísticos Modelos Estocásticos 
Programación 
Lineal 
 
Soluciones 
Reales 
Programación 
Lineal Entera 
 
Soluciones 
Enteras 
Programación 
Lineal por metas 
 
Soluciones en orden 
de prioridad 
Programación 
Dinámica 
 
Soluciones en 
Etapas continuas 
Optimización de 
Redes 
 
Soluciones 
orientadas a la 
distribución óptima 
Control de 
Inventarios 
 
Soluciones por 
etapas (n+1) 
Pronósticos 
 
Comportamiento 
futuro del sistema 
basado en datos 
históricos 
Teoría de 
Colas 
Determinación 
de tiempos de 
espera y 
longitud de la 
cola promedio 
Simulación de 
Sistemas 
Estimación de las 
medidas de 
desempeño del 
sistema modelado 
Herramientas de Investigación de Operaciones 
Tipos de Problemas 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 13
 
Las técnicas de la investigación de operaciones se apoyan matemáticamente 
sobre una o más de las siguientes teorías: Teoría de juegos, teoría de colas, 
teoría de la decisión, teoría de gráficas o teoría de redes, programación lineal, 
probabilidad y estadística matemática y programación dinámica. 
 
1.2 Programación lineal 
 
La programación lineal es una rama de la programación matemática que, como 
tal, se aplica en la búsqueda de soluciones óptimas de problemas de la vida 
real. Esta tiene una aplicación reconocida en diversas ramas de la ciencia 
debido a que tiene grandes ventajas, algunas de ellas son: 
 
1. Una gran variedad de problemas, en diversos campos, pueden ser 
representados, al menos aproximados, como modelos de programación 
lineal. 
2. Se tiene disponibles técnicas eficientes y sencillas para resolver 
problemas de programación lineal. 
3. Se tiene comodidad en la variación de datos [Felix R. Doldan Tie, 1989]. 
 
Los problemas de programación lineal, en general involucran el uso o 
asignación eficiente de recursos limitados o actividades conocidas como son 
materiales, máquinas, tiempo, capital, etc.; de la manera más adecuada, con la 
finalidad de alcanzar un objetivo deseado, ya sea minimizar costos o maximizar 
ganancias. 
 
La programación lineal se inició a partir de la segunda guerra mundial, pero fue 
durante la década de los cincuentas y sesentas cuando se desarrolló de forma 
más activa. En la actualidad es un poderoso instrumento para abordar 
problemas de gestión empresarial, ya que sólo se requiere de buena 
información para implementar el modelo. 
 
En 1947, George B. Dantzig publicó su Algoritmo Simplex para resolver 
modelos de programación lineal. Se inspiró en problemas que trabajó durante 
la Segunda Guerra Mundial en los campos de planeación militar. A partir de 
1949 un número de individuos han contribuido al campo de la programación 
lineal en muchas formas, incluyendo desarrollos teóricos, aspectos de 
computación y exploración de nuevas aplicaciones. El método simplex de 
programación lineal tiene mucha aceptación debido a su habilidad para 
modelar importantes problemas de decisión en las áreas administrativas y su 
capacidad para producir soluciones en un tiempo razonable. 
 
Algunos casos especiales de programación lineal, tales como los problemas de 
flujo de redes y problema de flujo de mercancías, se consideraron en el 
desarrollo de las matemáticas como suficientemente importantes para generar 
por si mismos mucha investigación sobre algoritmos especializados en su 
solución. Las ideas de programación lineal han inspirado muchos de los 
conceptos centrales de la teoría de optimización tales como la dualidad, la 
descomposición y la importancia de la convexidad y sus generalizaciones [Ma. 
del Carmen Hernández Ayuso,2007]. 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 14
 
1.3 Teoría de gráficas o Teoría de redes 
 
La teoría de gráficas o teoría de redes es una rama de las matemáticas en la 
que los problemas se representan y se resuelven justamente utilizando gráficas 
o redes. 
 
Una gráfica es un conjunto, no vacío, de objetos llamados vértices (o nodos) y 
una selección de pares de vértices, llamados aristas que pueden ser orientados 
o no. Una gráfica se representa mediante una serie de puntos (los vértices) 
conectados por líneas (las aristas). 
 
Gracias a la teoría de gráficas se pueden resolver diversos problemas como 
por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de 
apertura. Se utiliza para diferentes áreas por ejemplo, dibujo computacional, en 
todas las áreas de Ingeniería. 
 
Las gráficas se utilizan también para modelar trayectos como el de una línea de 
autobús a través de las calles de una ciudad, en el que podemos obtener 
caminos óptimos para el trayecto aplicando diversos algoritmos. 
 
La teoría de gráficas también ha servido de inspiración para las ciencias 
sociales, en especial para desarrollar un concepto no metafórico de red social, 
que sustituye los nodos por los actores sociales y verifica la posición, 
centralidad e importancia de cada actor dentro de la red.Esta medida permite 
cuantificar y abstraer relaciones complejas, de manera que la estructura social 
puede representarse gráficamente. Por ejemplo, una red social puede 
representar la estructura de poder dentro de una sociedad al identificar los 
vínculos (aristas), su dirección e intensidad y da idea de la manera en que el 
poder se transmite y a quiénes. 
[http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos, 27-07-2011. Juan Prawda, 
1976, vol 1 y vol 2]. 
 
 
 
La programación lineal y la teoría de redes son las dos herramientas que se 
utilizan en esta tesis para presentar el tema de flujo máximo. 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos,
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 15
CAPÍTULO 2 
Programación lineal 
 
La programación lineal debe su fama a que una gran variedad de problemas, 
en diversos campos, pueden ser formulados o aproximados como modelos 
lineales. 
 
Este tipo de problemas surgen en la industria, los sistemas de transporte, en la 
comunicación, en la educación, en las finanzas, en las redes eléctricas e 
hidráulicas, en los sistemas de presas, etc. 
 
En este capítulo se presenta el modelo primal del problema de programación 
lineal así como las tres formas de plantearlo (general, estándar y canónica); su 
solución y un ejemplo para explicar detalladamente cada uno de sus 
resultados. 
 
2.1 Formulación del problema de programación lineal 
 
En la formulación del problema de programación lineal hay reglas de operación 
que rigen el proceso y definen las alternativas de solución; éstas se pueden 
expresar mediante un conjunto de ecuaciones o desigualdades lineales a las 
cuales se les da el nombre de restricciones del problema: 
 
1. Dentro de la construcción del modelo matemático de un problema de 
programación lineal, las decisiones cuantificables relacionadas unas con 
otras, se representan como variables desconocidas involucradas en el 
problema, llamadas variables de decisión para las cuales se deben 
determinar los valores respectivos. Cada variable representa una cantidad 
que corresponde con una misma unidad de medida. Las variables de 
decisión son incógnitas que deben ser determinadas a partir de la solución 
del modelo. 
 
2. Restricciones: son el conjunto de posibles valores de las variables que 
representan a todas las alternativas factibles para el problema; son los 
límites del escenario de la situación planteada. Estas se definen con 
funciones lineales. 
 
3. Función objetivo: es el criterio elegido para buscar el objetivo de la 
optimización. Hay que expresar un objetivo bien definido, que debe servir 
para maximizar (para los ejercicios se abrevia como Max) la contribución 
unitaria, utilizando los recursos disponibles, o bien producir el costo más 
bajo posible usando una cantidad limitada de factores productivos 
(recursos), esto es minimizar ( para los ejercicios se abrevia como Min). 
Por lo tanto, se debe definir claramente una función objetivo en forma 
matemática y lineal. 
 
Cuando se tienen problemas y se desean modelar como problemas de 
programación lineal, es necesario tener presentes ciertas condiciones sobre las 
actividades a realizar y sobre las variables de decisión. 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 16
Condición de proporcionalidad.- Es el efecto que tiene la variable de decisión xj 
con respecto a los costos y con respecto a cada una de las restricciones, es 
decir, dada la variable xj su contribución a los costos es cjxj y su contribución a 
la i-ésima restricción es aij xj así, si se quiere doblar el nivel de una actividad es 
necesario duplicar los correspondientes flujos de insumos de la actividad. 
 
Condición de aditividad.- Esta condición garantiza que las actividades son 
independientes y que el costo total es la suma de los costos individuales y que 
la contribución a la i-ésima restricción es la suma de las contribuciones 
individuales de las actividades individuales. 
 
Condiciones de la continuidad de las variables de decisión.- Esta condición 
significa que las variables de decisión pueden tomar cualquier valor real 
positivo. 
 
Hay que hacer notar que para problemas del mundo real, las condiciones de 
proporcionalidad y aditividad, normalmente, no se cumplen pero se puede 
hacer ajustes necesarios por aproximaciones lineales y modelarlo como 
problemas de Programación Lineal [David G Luengerber, 1989]. 
 
2.2 Modelo de un Problema de Programación Lineal 
 
Hay tres formas de plantear un problema de programación lineal: La primera es 
la forma general, la segunda es la forma canónica y, por último, la forma 
estándar a continuación se explica cada una de ellas [Ma. del Carmen 
Hernández Ayuso, 2007]. 
 
 
2.2.1 Forma General 
 
El planteamiento matemático inicial del problema de programación lineal fue 
desarrollado por Dantzing en 1947; el modelo general es: 
 
Max (o Min) z = c1x1 + c2x2 + ...... +cnxn 
sujeto a 
 a11x1 + a12x2 + a13x3 + …. + a1nxn ≤ b1 (o bien ≥ o = ) 
 a21x1 + a22x2 + a23x3 + …. + a2nxn≤ b2 (o bien ≥ o = ) 
… 
 am1x1 + am2x2 + am3x3 + + amnxn≤ bm (o bien ≥ o = ) 
xi ≥ 0, i = 1, 2, 3, ….., n. 
 
La función objetivo z se debe maximizar o minimizar; está conformada por el 
vector c que se encuentra en Rn, conocidos como coeficientes de costo y el 
vector x que se encuentra en Rn de las variables de decisión. 
 
 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 17
A es la matriz de restricciones de mxn y b que se encuentra en Rm es el vector 
de recursos o términos independientes, vector columna. 
 a11 a12 a13 …. a1n b1 
 a21 a22 a23 …. a2n b2 
… 
 am1 am2 am3 …. amn bm 
 
 
 
Esta forma general es la que normalmente se genera al plantear un problema 
en la vida real. Y a partir de ésta forma se puede transformar en las dos 
siguientes formas, que ayudan a resolver el problema de programación lineal. 
 
2.2.2 Forma canónica de un problema lineal 
 
Se dice que un problema de programación lineal en forma canónica: 
 
Si es de maximización: 
a) Las restricciones del problema son todas del tipo menor o igual. 
b) Las variables de decisión son no negativas 
 
Max z = cx 
sujeto a 
Ax ≤ b 
x ≥ 0 
 
También se puede tomar esta forma para el problema de minimización donde: 
a) Las restricciones del problema son todas de tipo mayor o igual y 
b) Las variables de decisión son no negativas: 
 
Min w =cx 
sujeto a 
Ax ≥ b 
x ≥ 0 
 
 
2.2.3 Forma estándar de un problema lineal 
 
Se dice que un problema de programación lineal está en forma estándar si: 
 
a) Las restricciones del problema son todas ecuaciones. 
b) Las variables de decisión son no negativas. 
c) Los elementos del vector de recursos son todos no negativas. 
 
Max (o Min) z = cx 
sujeto a 
Ax = b 
x≥0 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 18
en donde c, x, A y b ≥0 son como se definió anteriormente. 
 
Se puede ver que, mediante manipulaciones adecuadas un problema lineal 
dado se puede escribir en distintas formas equivalentes. 
 
 
 
 
 
Todo problema de programación lineal puede ser expresado en forma 
canónica: 
 
1. Si una restricción del tipo mayor o igual que (≥) puede ser multiplicada 
por -1 para obtener una de tipo menor o igual que (≤); 
2. Una ecuación puede ser substituida por una desigualdad del tipo menor 
o igual que (≤) y otra del tipo mayor o igual que (≥); 
3. Para una variable no positiva xi puede definirse x’'i=-xi resultando x’i ≥ 
0; 
4. Para una xi no restringida pueden ser definidas dos variables no 
negativas x’i y x’’i tales que x’i – x’’i = xi considerando, deeste modo, 
todos los valores posibles de xi. En la solución una será igual a cero y la 
otra positiva; 
5. Si el problema es de minimización, puede considerarse en vez de z la 
función z’=-z y el problema equivalente se busca maximizar z’. 
 
Supóngase el siguiente problema de programación lineal: 
Max z= 2x1 – x2 – 3x3 
Sujeto a 
 
 2x1 – x2 - 2x3 ≤ 5 
-3x1 + 2x2 + x3 ≥ 6 
x1≥0; x2≤0 y x3 sin restricción 
y se pide convertirlo a forma canónica. 
 
Se sabe que en la forma canónica para un problema de maximización sus 
restricciones son menores o iguales a cero (≤0) y que las variables xi son 
mayores e iguales a cero (xi ≥0); por lo que para la restricción 
(-3x1 + 2x2 + x3 ≥ 6) se necesita multiplicarla por (-1). La variable x2 se define 
como x’2=-x2 por lo que x’2 ≥0; y para x3 se define como x3= x’3 – x’’3 donde x’3 y 
x’’3 son mayores e iguales a 0. 
 
Sustituyendo en el problema queda: 
 
Max z = 2x1 + x’2 + 3x’3 – 3x’’3 
Sujeto a 
2x1 + x’2 - 2x’3 + 2x’’3≤ 5 
3x1 + 2x’2 - x’3 + x’’3≥ 6 
x1≥0; x’2≥0; x’3≥0 y x’’3≥0 
 
 n n 
máximo∑cjxj = - mínimo∑ cjxj 
 j=1 j=1 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 19
2.3 Solución de un problema de programación lineal 
 
Uno de los métodos más utilizados para resolver un problema de programación 
lineal es el método simplex, este método fue desarrollado por George Bernard 
Dantzig, el cual es un procedimiento iterativo para resolver un problema lineal 
en forma estándar en los que las variables son no negativas; permite ir 
mejorando la solución a cada paso. El proceso concluye cuando no es posible 
seguir mejorando más dicha solución y se alcanzó el valor óptimo. 
 
El algoritmo se inicia con una solución básica factible y, en cada iteración, se 
construye otra solución básica factible que mejora la función objetivo. Los 
pasos generales son: 
 
a. Determinar una solución básica factible inicial. 
b. Determinar si la solución básica factible es óptima o no. Si lo es, 
terminar. Si no ir al paso c. 
c. Determinar una solución básica factible mejor e ir al paso b. 
 
Como apoyo técnico, se utiliza un programa matemático (versión estudiantil) 
para resolver los problemas de Programación Lineal, aquí planteados. Dicho 
programa se llama LINDO (Linear, Interactive and Discrete Optimizer). La 
plataforma de trabajo de LINDO Systems, Inc, Chicago, versión 6.1 en el 
ambiente Windows. 
 
LINDO es una aplicación para computadoras que se utiliza para resolver 
problemas de programación lineal, cuadrática y entera. Desde 1979 el 
programa LINDO ha sido una de las herramientas de optimización favoritas de 
las comunidades Educativas y Empresariales. LINDO Systems se ha dedicado 
a proveer poderosas e innovativas herramientas de optimización que también 
son flexibles y muy fáciles de usar. 
[moodle.uho.edu.cu/file.php/853/Como_usar_LINDO.doc] 
 
Al igual que todos los paquetes de programación lineal Lindo emplea el método 
simplex para resolver problemas de programación lineal. Junto con la solución 
del problema, el programa también proporciona un análisis común de 
sensibilidad de los Coeficientes de la Función Objetivo (denominados 
Coeficientes de Costos) y los valores del lado derecho de las restricciones. 
 
2.3.1 Ejercicio de programación lineal 
 
Para ejemplificar la formulación y procedimiento de un problema de 
programación lineal se muestra un ejercicio de transporte, ya que este expone 
de una manera completa todo lo que es un problema de programación lineal. 
 
Planteamiento del problema. 
 
Un productor de café debe transportar el producto desde Coatepec y Orizaba a 
sus centros de distribución en la Ciudad de México, Guadalajara y Tijuana. La 
cantidad disponible en Coatepec es de 55 toneladas de café y en Orizaba es 
de 35 toneladas. La demanda de café en sus centros de distribución es 40 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 20
toneladas en la Ciudad de México, 30 en Guadalajara y 20 en Tijuana. El costo, 
en cientos de pesos, por transportar una tonelada de café entre las ciudades se 
indica en la tabla siguiente 
 
 Cd. De México (1) Guadalajara (2) Tijuana (3) 
Coatepec (1) 5 6 3 
Orizaba (2) 3 5 4 
 Tabla 1 
 
Formulación del Modelo de programación lineal: 
 
 Variables de decisión. 
 Restricciones. 
 Función objetivo. 
 
El productor desea determinar un plan de transporte de costo mínimo tal que se 
satisfaga la demanda. 
 
I.- Las variables de decisión. Un plan posible de transporte será formulado 
mediante las variables. 
 
xij = número de toneladas de café a transportar del origen i al destino j; i= 1,2; 
j=1,2,3. 
 
Donde Coatepec y Orizaba se ha denominado origen 1 y 2 respectivamente y 
Ciudad de México, Guadalajara y Tijuana destinos 1,2 y 3 respectivamente. 
 
II.- Restricciones. Puesto que en cada origen se tiene una cantidad de café 
disponible se deben imponer restricciones a la cantidad total que se transporta 
desde él. 
 
El número total de toneladas de café que son transportadas desde Coatepec 
es: 
x11 + x12 + x13, 
 
por lo que esta suma es 55 toneladas de la oferta del primer origen. 
Análogamente, para Orizaba, se debe satisfacer: 
 
x21 + x22 + x23 = 35. 
 
A las dos ecuaciones anteriores se les llama restricciones de oferta. 
 
Por otro lado, en cada destino se tiene una demanda que deberá ser 
satisfecha. Por ejemplo, el número de toneladas que son transportadas desde 
Coatepec y Orizaba a la Ciudad de México es: 
 
x11 + x21, 
 
entonces esta cantidad debe ser de 40. 
Análogamente: 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 21
x12 + x22 = 30 
y 
x13 + x23 = 20 
 
A estas tres ecuaciones se les llama restricciones de demanda. 
Finalmente se tienen las restricciones de signo para las variables. 
 
xij ≥ 0 i=1,2;j=1,2,3. 
III.- Función objetivo. El criterio para elegir el mejor plan de transporte es su 
costo; z debe entonces representar éste: 
 
z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
 
y el problema consiste entonces en determinar los valores de las variables de 
decisión, que satisfagan las restricciones de oferta, de demanda y de signo, 
tales que aporten el valor mínimo de la función z. [Ma. del Carmen Hernández 
Ayuso,2007]. 
 
Hay que hacer notar que, cuando el problema se plantea en forma estándar, 
para este tipo de ejemplos donde se usa la oferta y la demanda se debe tener 
presente que el problema debe estar balanceado, esto es que la oferta debe 
ser igual a la demanda. 
 
Modelo de programación lineal: 
 
Min z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
Sujeto a 
x11 + x12 + x13 ≤ 55 Restricciones de oferta 
 + x21 + x22 + x2 ≤ 35 
 
x11 + x21 ≥ 40 
 +x12 + x22 ≥ 30 Restricciones de 
 +x13 + x23 ≥ 20 demanda 
 
Por tanto el modelo en forma estándar queda planteado de la siguiente 
manera: 
 
Min z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
Sujeto a 
 
x11 + x12 + x13 = 55 
 + x21 + x22 + x23 = 35 
x11 + x21 = 40 
 +x12 + x22 = 30 
 +x13 + x23 = 20 
 
xij ≥ 0; i=1,2; j=1,2,3 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 22
DESTINOS 
O
R
IG
EN
 Cd. De México (1) Guadalajara (2) Tijuana(3) 
(1)Coatepec 
 
5 6 3 
(2)Orizaba 3 5 4 
 Tabla1.1 
 
 
 
 
 
 
 
 
 
 
 
 
Planteamiento en LINDO: 
Min 5x11 + 6x12 + 3x13 + 3x21+ 5x22 + 4x23 
st 
x11 + x12 + x13 =55 
 x21 + x22 + x23 =35 
x11 + x21 =40 
 +x12 + x22 =30 
 + x13 + x23 =20 
 
end 
 
La solución que arroja LINDO es: 
 
La solución del Cuadro 2.3.1.1 que genera lindo, proporciona el valor de la 
función objetivo; el valor de las variables; los costos reducidos; las holguras y 
los precios duales que posteriormente son explicadas. 
 
OBJECTIVE FUNCTION VALUE 
 
1) 370.0000 
 
 
VARIABLE VALUE 
REDUCED 
COST 
X11 5.000000 0.000000 
X12 30.000000 0.000000 
1 
2 
1
2 
3 
5 
6 
3 
3 
5 
4 
Origen Destino 
 Figura 2 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 23
X13 20.000000 0.000000 
X21 35.000000 0.000000 
X22 0.000000 1.000000 
X23 0.000000 3.000000 
 
 
ROW 
SLACK OR 
SURPLUS DUAL PRICES 
2) 0.000000 0.000000 
3) 0.000000 2.000000 
4) 0.000000 -5.000000 
5) 0.000000 -6.000000 
6) 0.000000 -3.000000 
Cuadro 2.3.1.1 
 
La optimización de este problema es z*= 370 unidades. 
 
La cantidad que se requiere de cada variable para que el problema tenga la 
optimización que se muestra en el Cuadro 2.3.1.1 es que del origen 
Coatepec (1) al destino Cd. de México (1) se requieren 5 unidades (x11) y el 
costo es de 5 por lo que se tiene un total de 25; de Coatepec (1) a Guadalajara 
(2) 30 unidades (x12) con un costo de 6 el total es 180 y; de Coatepec (1) a 
Tijuana (3) 20 unidades (x13) con un costo de 3 dando un total de 60. Lo que 
se obtiene un total de 265 unidades del origen Coatepec. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Para el origen Orizaba (2) a Cd. de México (1) requiere 35 unidades (x21) si el 
costo es de 3 entonces da un total de 105; para Guadalajara (2) y Tijuana (3) 
no es conveniente enviar nada su valor es cero 0 (x22 y x23). 
 
 
 
 
 
 
Se tiene que 
 
(5) (5) = 25 
 
(30) (6) = 180 
 
(20) (3) = 60 
 265 
Origen Destino 
 Figura 2.1 
1
2 
3 
5 
6 
3 
1 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 24
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Esto da un total para los dos orígenes de 265 + 105 = 370 
 
Ahora se muestra que es lo que pasa si se obliga a pasar una unidad de flujo 
por la variable x22. 
El problema 2 se plantea de la siguiente forma para LINDO: 
 
Min 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
st 
x11 + x12 + x13 =55 
 x21 + x22 + x23 =35 
x11 + x21 =40 
 + x12 + x22 =30 
 + x13 + x23 =20 
 x22 = 1 
end 
 
El Programa LINDO arroja: 
 
OBJECTIVE FUNCTION VALUE 
1) 371.000…………z** 
 
VARIABLE VALUE 
REDUCED 
COST 
X11 6.000000 0.000000 
X12 29.000000 0.000000 
X13 20.000000 0.000000 
X21 34.000000 0.000000 
X22 1.000000 0.000000 
X23 0.000000 3.000000 
 
ROW 
SLACK OR 
SURPLUS 
DUAL 
PRICES 
2) 0.000000 0.000000 
3) 0.000000 2.000000 
2 
1
2 
3 
3 
5 
4 
Se tiene que 
 
(35) (3) = 105 
 
(0) (5) = 0 
 
(0) (4) = 0 
 105 
Origen Destino 
 Figura 2.2 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 25
4) 0.000000 -5.000000 
5) 0.000000 -6.000000 
6) 0.000000 -3.000000 
7) 0.000000 -1.000000 
Cuadro 2.3.1.2 
 
Y si se obliga a pasar una unidad por la variable x23 para el problema 3, pero el 
valor de la función objetivo cambia a 373, ya que para esta variable el costo 
reducido es 3. 
 
Min 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
st 
x11 + x12 + x13 =55 
 x21 + x22 + x23 =35 
x11 + x21 =40 
 + x12 + x22 =30 
 + x13 + x23 =20 
 + x23 = 1 
end 
 
El Programa LINDO arroja: 
 
OBJECTIVE FUNCTION VALUE 
1) 373.000…………z*** 
 
VARIABLE VALUE 
REDUCED 
COST 
X11 6.000000 0.000000 
X12 30.000000 0.000000 
X13 19.000000 0.000000 
X21 34.000000 0.000000 
X22 0.000000 1.000000 
X23 1.000000 0.000000 
 
ROW 
SLACK OR 
SURPLUS 
DUAL 
PRICES 
2) 0.000000 0.000000 
3) 0.000000 2.000000 
4) 0.000000 -5.000000 
5) 0.000000 -6.000000 
6) 0.000000 -3.000000 
7) 0.000000 -3.000000 
 Cuadro 2.3.1.3 
 
Al momento de obligar que una unidad pase por la variable x22, la función 
objetivo obtuvo como resultado z**=371 por lo que se dice que el costo 
reducido es de z** - z*=1 que es el valor que se encuentra en la columna de 
costos reducidos en el Cuadro 2.3.1.1. Esto se ve como una pérdida debido a 
que lo que se busca es minimizar los costos y con esto aumentó el costo de 
transportar esa cantidad de mercancía a una unidad más. Pasar la variable x23 
se tiene un aumento en el costo de 3 unidades por una unidad, lo que indica 
que no se minimizan los costos con cualquiera de ésta decisiones sino al 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 26
contrario, por lo que el Cuadro 2.3.1.1 es el que muestra la mejor situación para 
este problema, ha esto se le llama interpretación de costos reducidos. 
 
Si el ejercicio anterior se plantea en forma canónica se tiene que: 
 
Min z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
Sujeto a 
 
x11 + x12 + x13 ≤ 55 1 
 + x21 + x22 + x23 ≤ 35 2 
x11 + x21 ≥ 40 3 
 +x12 + x22 ≥ 30 4 
 +x13 + x23 ≥ 20 5 
 
xij ≥ 0; i=1,2; j=1,2,3 
 
Ahora se multiplicarpor (-1) la primara y la segunda restricción del 
planteamiento anterior, ya que se requiere que todas las restricciones sean 
mayores e iguales para poder decir que está en su forma canónica, entonces 
queda: 
 
 
Min z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
Sujeto a 
 
-x11 - x12 - x13 ≥ -55 
 - x21 - x22 - x23 ≥ -35 
x11 + x21 ≥ 40 
 +x12 + x22 ≥ 30 
 +x13 + x23 ≥ 20 
 
xij ≥ 0; i=1,2; j=1,2,3 
 
El problema se plantea de la siguiente forma para LINDO: 
 
No es necesario poner (≥ ó >=) en el planteamiento del problema para este 
programa ya que el sistema lo supone, por ello también no se necesita poner 
que las variables xij≥0 
 
 
Min 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
st 
-x11 - x12 - x13 >-55 
 - x21 - x22 - x23 >-35 
x11 + x21 > 40 
 +x12 + x22 > 30 
 + x13 + x23 > 20 
 
end 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 27
El resultado que arroja LINDO es: 
 
OBJECTIVE FUNCTION VALUE 
 
1) 370.0000 
 
VARIABLE VALUE REDUCED COST 
 X11 5.000000 0.000000 
 X12 30.000000 0.000000 
 X13 20.000000 0.000000 
 X21 35.000000 0.000000 
 X22 0.000000 1.000000X23 0.000000 3.000000 
 
 
 
ROW 
SLACK OR 
SURPLUS DUAL PRICES 
 2) 0.000000 0.000000 
 3) 0.000000 -2.000000 
 4) 0.000000 -5.000000 
 5) 0.000000 -6.000000 
 6) 0.000000 -3.000000 
 Cuadro 2.3.1.4 
 
2.4 Interpretación económica de los costos reducidos 
 
 Indica la diferencia entre el Ingreso Marginal y el Costo Marginal para 
cada actividad. 
 En una solución óptima, las actividades incluidas en la función objetivo 
cumplen con la condición Ingreso Marginal = Costo Marginal, por lo que 
el costo reducido de las mismas es igual a 0, que es el principio de 
optimización. Donde el ingreso marginal es el incremento provocado 
por el ingreso en la solución de una unidad adicional de una actividad, el 
Costo Marginal es el incremento o disminución en el costo total 
resultante de agregar una unidad de actividad en la solución. 
 En programación lineal, el Costo Marginal de una actividad se calcula 
valuando los recursos consumidos por cada actividad según el Costo 
reducido de los recursos. 
 Las actividades (variable (s)) no incluidas en la solución óptima tienen un 
Costo Marginal mayor que su Ingreso Marginal. El Costo reducido indica 
la magnitud de esta diferencia. 
 Indica en cuánto se perjudica el valor óptimo (función objetivo) cuando 
una variable no básica (xij=0) toma un valor distinto de cero. Para el 
problema que se desarrolló se interpreta en cuánto se está dispuesto a 
pagar al utilizar un arco, distinto del óptimo, para enviar una tonelada de 
café. 
 Estos cambios sólo se pueden ver en forma separada, lo que involucra 
que los resultados son mientras toda la demás información que se tiene 
del problema queda constante. 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 28
Al comparar el Cuadro 2.3.1.1 y el Cuadro 2.3.1.4, se observa, que los 
resultados son los mismos para las columnas de valor y de costo reducido por 
lo que se puede concluir que para estos resultados es igual hacer el ejercicio 
en forma estándar o en forma canónica. 
 
Y una vez que se tiene el resultado de la solución óptima, ya no es necesario 
realizar nuevamente el problema, pues la información que da el 
Cuadro 2.3.1.1(forma estándar) o el Cuadro 2.3.1.4 (forma canónica) del 
problema muestra como varía la solución óptima (función objetivo) si se hace 
algún cambio en cuanto a sus variables no básicas. 
 
Para la columna de precios duales se muestra que hay diferencias entre la 
forma canónica (Cuadro 2.3.1.4) y la forma estándar (Cuadro 2.3.1.1) pero esto 
se analiza con mayor cuidado y se explica en el próximo capítulo. 
 
 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 29
CAPÍTULO 3 
Problema dual 
 
 
 
El dual es un problema de programación lineal que se obtiene 
matemáticamente de un modelo primal de programación lineal dado. Los 
problemas dual y primal están relacionados, ya que la solución óptima de uno 
se puede obtener a partir de la del otro, ambos problemas se construyen a 
partir de los mismos coeficientes de costo y restricciones. En la mayoría de los 
procedimientos de programación lineal, el dual se define para varias formas del 
primal, dependiendo de los tipos de restricciones, del signo de las variables y 
el sentido de la optimización. 
 
Es posible interpretar las variables, restricciones y función objetivo de uno de 
los modelos en términos del significado del otro, dando una interpretación 
económica; las estructuras duales permiten resolver problemas lineales que 
tienen más restricciones que actividades. La teoría de la dualidad es muy 
usada en algunos casos, en optimización de redes tales como los problemas 
de ruta más corta, flujo máximo, flujo con costos mínimos, etc. 
 
3.1 Construcción del problema dual 
 
Hay dos formas importantes de dualidad: la forma canónica y la forma 
estándar. Estas dos formas son completamente equivalentes; pero para ello se 
requiere primero tener en cuenta el problema en el modelo primal. [Makhtar 
Bazara, 1971]. 
 
La forma estándar del primal se define como: 
 
 
 
Forma estándar 
Minimización Maximización 
n 
∑ cjxj 
j=1 
 n 
Sujeta a ∑ aijxj=bi i= 1,……..,m 
 j=1 
 xj≥0 j= 1,……..,n 
 
n 
∑ cjxj 
j=1 
 n 
Sujeta a ∑ aijxj=bi i= 1,……..,m 
 j=1 
 xj≥0 j= 1,……..,n 
 
 Cuadro 3.1.1 
 
 
 
 
 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 30
 
 
La forma canónica del problema primal se define como: 
 
Planteamiento dual de un problema primal 
en forma canónica 
Minimización Maximización 
n 
∑ cjxj 
j=1 
 n 
Sujeta a ∑ aijxj≥bi i= 1,……..,m 
 j=1 
 xj≥0 j= 1,……..,n 
 
n 
∑ cjxj 
j=1 
 n 
Sujeta a ∑ aijxj≤bi i= 1,……..,m 
 j=1 
 xj≥0 j= 1,……..,n 
 
 Cuadro 3.1.2 
 
En la Tabla 2 se muestra que el dual se obtiene simétricamente del primal de 
acuerdo con las reglas siguientes: 
1.- Para toda restricción primal hay una variable dual. 
2.- Para toda variable primal hay una restricción dual. 
3.- Los coeficientes de las restricciones de una variable primal forman los 
coeficientes del primer miembro de la restricción dual correspondiente; y el 
coeficiente objetivo de la misma variable se convierte en le segundo miembro 
de la restricción dual. (Por ejemplo, véase la columna j-ésima). Estas reglas 
indican que el problema dual tiene m variables (y1, y2, …..ym) y n restricciones, 
(correspondientes a x1, x2,……, xn) [Hamdy A. Taha, 1995]. 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 31
 
 c1 c2 ………cj…………....cn 
 
Variables primales 
x1 x2 ….. xj…………..xn Segundo 
miembro de 
restricciones 
duales 
 a11 a12 …..…a1j…………...a1n b1 
 a21 a22 ……..a2j…………...a2n b2 
 .. .. .. .. .. 
 .. .. .. .. .. 
 .. .. .. .. .. 
 am1 am2 ….....amj………..…amn. .bm 
 
Coeficientes 
del primer 
miembro de 
las 
restricciones 
duales 
 y1 
 y2 
 .. 
 .. 
 .. 
 ym 
Variable 
dual 
j-ésima 
restricción 
dual 
Función objetivo 
del dual 
 Tabla 2 
 
 
En la Tabla 3 se muestran las reglas generales para construir el problema dual 
de cualquier problema primal [Ma. del Carmen Hernández Ayuso, 2007]. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Minimización Maximización 
V
a
r
i
a
b
l
e
s 
R
e
s
t
r
i
c
c
i
o
n
e
s 
≥ 0 
 
≤ 0 
 
No restringido 
 
≤ 
 
≥ 
 
= 
≥ 
 
≤ 
 
= 
≥ 0 
 
≤ 0 
 
No restringido 
 
V
a
r
i
a
b
l
e
s 
R
e
s
t
r
i
c
c
i
o
n
e
s 
Tabla 3 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 32
 
 
 
Se puede utilizar esta tabla de izquierda a derecha o viceversa, para construir 
el dual de cualquier problema lineal; por ejemplo, se tiene un problema de 
minimización se utiliza la Tabla 3 de derecha a izquierda, lo que indica que el 
dual es un problema de maximización; y si se tiene un problema de 
maximización se procede al contrario. 
 
Para ilustrar lo anterior se construye el problema dual del ejercicio del capítulo 
anterior de la sección 2.3.1 en su forma estándar. 
 
Considere el modelo primal de programación lineal en forma estándar. 
 
Min z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
Sujeto a 
 
x11 + x12 + x13 = 55+ x21 + x22 + x23 = 35 
x11 + x21 = 40 
 +x12 + x22 = 30 
 +x13 + x23 = 20 
 
xij ≥ 0; i=1,2; j=1,2,3 
Dado que el problema es de minimización; de acuerdo a la Tabla 3 el problema 
dual es de maximización. 
 
Conforme a las reglas para obtener el problema dual patiendo del problema 
primal, el primer paso es designar una nueva variable a cada restricción de 
acuerdo con la Tabla 2. 
 
Para las restricciones de demanda se denominan wi con i=1,2.: 
 
x11 + x12 + x13 =55…………w1 
 x21 + x22 + x23 =35…………w2 
 
Para las restricciones de oferta se denominan yi con i=1,2 y 3: 
 
x11 + x21 =40………….y1 
 +x12 + x22 =30………….y2 
 + x13 + x23 =20………….y3 
 
Con base en las nuevas variables duales y los términos independientes del 
lado derecho de cada restricción se construye la función objetivo del problema 
dual como sigue: 
 
 Max w = 55w1 + 35w2 + 40y1 + 30y2 + 20y3 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 33
Donde la interpretación económica del correspondiente problema dual es 
ofrecer remplazar el tener que solucionar el transporte. 
Una empresa transportadora propone, comprar la producción de Coatepec y 
Orizaba a precios (por tonelada) w1 y w2, respectivamente y vender en la 
Ciudad de México, Guadalaraja y Tijuana, las cantidades de café requeridas a 
precios (por tonelada) y1,y2 y y3, repectivamente. 
 
Se utiliza la Tabla 3, es decir: las variables en el primal son (≥), por lo que las 
restricciones en el dual son ≤. 
 
w1 + y1 ≤5 
w1 + y2 ≤6 
w1 +y3 ≤3 
 w2 + y1 ≤3 
 w2 + y2 ≤5 
 w2 + y3 ≤4 
 
Ahora bien, dado que en el primal las restricciones son (=), entonces las 
variables en el dual son sin restricción. 
 
w1 sin restricción 
w2 sin restricción Estas variables son sin restricción debido a que las 
y1 sin restricción ecuaciones del problema primal son igualdades. 
y2 sin restricción 
y3 sin restricción 
 
Por tanto, el problema dual del problema primal en forma estándar queda 
planteado de la siguiente manera: 
 
En conclusión, se observa que el problema primal es de minimización y el dual 
es de maximización, el número de restricciones es igual al número de variables 
del problema dual, el número de variables en el dual es el número de 
restricciones en el primal y se transpone la matriz creada por las restricciones 
de demanda y de oferta anteriormente mencionadas. 
 
 Max w = 55w1 + 35w2 + 40y1 + 30y2 + 20y3 
 sujeto a 
w1 + y1 ≤5 
w1 + y2 ≤6 
w1 +y3 ≤3 
 w2 + y1 ≤3 
 w2 + y2 ≤5 
 w2 + y3 ≤4 
 
 w1 sin restricción 
 w2 sin restricción 
 y1 sin restricción 
 y2 sin restricción 
 y3 sin restricción 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 34
 
Ahora se hace el problema dual del problema primal en su forma canónica 
 
Min z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23 
Sujeto a 
 
-x11 - x12 - x13 ≥ -55 
 - x21 - x22 - x23 ≥ -35 
x11 + x21 ≥ 40 
 +x12 + x22 ≥ 30 
 +x13 + x23 ≥ 20 
 
xij ≥ 0; i=1,2; j=1,2,3 
 
con respecto a la información que se detalla en la Tabla 3, igual como se 
realizó en su forma estándar dando como resultado: 
 
 Max -55w1-35w2+40y1+30y2+20y3 
 sujeto a 
 
 -w1+y1≤ 5 
 -w1+y2≤6 
 -w1+y3≤3 
 -w2+y1≤3 
 -w2+y2≤5 
 -w2+y3≤4 
w1, w2, w3, y1, y2,y y3 ≥0. 
 
3.2 La relación entre los problemas primal y dual 
 
Los valores objetivos en un par de problemas primal-dual deben satisfacer las 
siguientes relaciones: 
 
 
1.- En cualquier par de soluciones primal y dual factibles [Hamdy A. Taha, 
1995]. 
 
 
La demostración de la validez de estos dos resultados está en el (anexo 3 
teoremas); como Teorema débil de dualidad que dice: 
 
Considere un problema primal de programación y su problema dual asociado. 
Valor optimo de un 
problema primal ≤ 
Valor optimo de un 
problema dual 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 35
 
Sean x y y soluciones factibles del problema primal (P) y el problema dual (D) 
respectivamente. Entonces se cumple que: 
 
 
Después de este resultado también se puede demostrar que Max z = Min w 
son las soluciones óptimas del problema primal y dual respectivamente, este 
teorema se encuentra en el anexo 2 teoremas. 
 
3.3 Solución del problema dual 
 
Se resuelve el problema dual del problema primal en su forma estándar 
mediante LINDO: 
 
Max 55w1 +35w2+40y1+30y2+20y3 
st 
w1 + y1 ≤5 
w1 + y2 ≤6 
w1 +y3 ≤3 
 w2 + y1 ≤3 
 w2 + y2 ≤5 
 w2 + y3 ≤4 
 
 end 
 free w1 
 free w2 
 free y1 
 free y2 
 free y3 
 
Para el programa LINDO las variables sin restricción deben ir con “free” para 
que las identifique como variables libres o sin restricciones. 
 
El resultado es: 
 
OBJETIVE FUNCION VALUE 
 
1) 370.0000 
 
VARIABLE VALUE 
REDUCED 
COST 
W1 0.000000 0.000000 
W2 -2.000000 0.000000 
Y1 5.000000 0.000000 
 
 
P 
Max z = cx 
s.a 
 Ax ≤ b 
 x ≥ 0 
 
 
D 
Min w = by 
s.a 
 Ay ≥ c 
 y ≥ 0 
cx ≤ yb 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 36
Y2 6.000000 0.000000 
Y3 3.000000 0.000000 
 
ROW 
SLACK OR 
SURPLUS 
DUAL 
PRICES 
2) 0.000000 5.000000 
3) 0.000000 30.000000 
4) 0.000000 20.000000 
5) 0.000000 35.000000 
6) 1.000000 0.000000 
7) 3.000000 0.000000 
 CUADRO 3.3.1 
 
Ahora se resolverá el problema dual del problema primal en su forma canónica 
en el programa LINDO. 
 
 Max -55w1-35w2+40y1+30y2+20y3 
 st 
 
 -w1+y1<5 
 -w1+y2<6 
 -w1+y3<3 
 -w2+y1<3 
 -w2+y2<5 
 -w2+y3<4 
 
 end 
 
Los resultados son: 
 
1) 370.0000 
 
VARIABLE VALUE 
REDUCED 
COST 
 W1 0.000000 
 
0.000000 
 W2 2.000000 
 
0.000000 
 Y1 5.000000 
 
0.000000 
 Y2 6.000000 
 
0.000000 
 Y3 3.000000 
 
0.000000 
 
ROW 
SLACK OR 
SURPLUS 
DUAL 
PRICESS 
 2) 0.000000 
 
5.000000 
 3) 0.000000 
 
30.000000 
 4) 0.000000 
 
20.000000 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 37
 5) 0.000000 
 
35.000000 
 6) 1.000000 
 
0.000000 
 7) 3.000000 
 
0.000000 
 CUADRO 3.3.2 
 
Se ha comprobado que las funciones objetivo son iguales con un valor de 370 
unidades tanto en el problema primal como en el dual. 
 
Y aquí es donde se comienza a hablar del los precios duales, los cuales se 
encuentran en la tercera columna después de los costos reducidos y están 
asociados a las restricciones como se muestran en los cuadros (Cuadro 3.3.1 y 
Cuadro 3.3.2). 
 
 
3.4 Interpretación económica del problema dual 
 
Considerando un problema primal de programación lineal y su problema dual 
asociado. 
 
 
donde 
 
 
 
 
 
 
Se puede establecer una interpretación económica de las variables duales yipor medio del siguiente análisis dimensional: 
 
El primer miembro de la ecuación representa una unidad monetaria 
(rendimiento) y bi representa unidades (cantidad) del recurso i; entonces yi, de 
acuerdo con la ecuación anterior, debe representar unidad monetaria por 
unidad de recurso i, como se muestra a continuación. 
 
$(rendimiento) = (unidades de recurso i)*($ / unidad de recurso i) 
 
 
Las variables duales yi representa el valor por unidad de recurso i. En la 
literatura a la variable yi se le llama generalmente precios duales. El análisis 
anterior conduce a una interesante observación: las soluciones del problema 
primal y dual factibles no óptimas están dadas de la siguiente manera: 
 
 
P 
Max z = cx 
s.a 
 Ax ≤ b 
 x ≥ 0 
 
 
D 
Min w = yb 
s.a 
 yA ≥ c 
 y ≥ 0 
 
n 
∑ cjxj 
j=1 
= 
m 
∑ biyi 
i=1 
m 
∑ 
i=1 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 38
 
z < w 
 
En virtud de la interpretación económica, la desigualdad indica: 
 
(ganancia) < (valor de los recursos) 
 
La desigualdad indica que tanto el rendimiento total de todas las actividades 
sea menor que el valor de los recursos del modelo, las soluciones 
correspondientes (primal y dual) factibles no pueden ser óptimas. La 
oportunidad (rendimiento máximo) se alcanza sólo cuando los recursos se han 
explotado completamente; es decir, cuando el rendimiento total iguala al valor 
total de los recursos (z = w). Alternativamente, se puede pensar en el modelo 
de programación lineal como un sistema de entrada-salida donde los recursos 
y el rendimiento representan, respectivamente, los elementos de entrada y de 
salida. El sistema permanece inestable (no óptimo) en tanto que la entrada 
(valor de los recursos) exceda a la salida (rendimiento), alcanzando la 
estabilidad cuando se igualan las dos cantidades [Ma. del Carmen Hernández 
Ayuso, 2007. Makhtar Bazara, 1971]. 
 
Por tanto se mostró que existe cierta relación desde el punto de vista 
económico entre los resultados del problema primal con el problema dual 
 
Relación del problema programación lineal en forma estándar y su dual 
 
Problema primal Problema dual 
 Dual prices Value 
x11 + x12 + x13=55 
0.000000 w1 
 0.000000 
x21 + x22 + x23 = 35 2.000000 w2 -2.000000 
x11 + x21=40 -5.000000 y1 5.000000 
x12 + x22 = 30 -6.000000 y2 6.000000 
x13 + x23 = 20 -3.000000 y3 3.000000 
 
PROBLEMA DUAL PROBLEMA PIRMAL 
 DUAL PRICES VALUE 
w1 + y1 ≤5 5.000000 x11 5.000000 
w1 + y2 ≤6 30.000000 x12 30.000000 
w1 + y3 ≤3 20.000000 x13 20.000000 
w2 + y1 ≤3 35.000000 x21 35.000000 
w2 + y2 ≤5 0.000000 x22 0.000000 
w2 + y3 ≤4 0.000000 x23 0.000000 
 Cuadro 3.4.1 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 39
Relación del problema programación lineal en forma canónica y su dual 
 
Problema primal Problema dual 
 
DUAL 
PRICES VALUE 
-x11 - x12 - x13≥-55 
0.000000 w1 
 0.000000 
-x21 - x22 - x23≥-35 -2.000000 w2 2.000000 
x11 + x21≥40 -5.000000 y1 5.000000 
x12 + x22 ≥ 30 -6.000000 y2 6.000000 
x13 + x23 ≥20 -3.000000 y3 3.000000 
 
 
 
 
Problema dual Problema primal 
 DUAL PRICES VALUE 
-w1 + y1 ≤5 5.000000 x11 5.000000 
-w1 + y2 ≤6 30.000000 x12 30.000000 
-w1 + y3 ≤3 20.000000 x13 20.000000 
-w2 + y1 ≤3 35.000000 x21 35.000000 
-w2 + y2 ≤5 0.000000 x22 0.000000 
-w2 + y3 ≤4 0.000000 x23 0.000000 
 Cuadro 3.4.2 
 
 Del problema primal al dual en su forma estándar y canónica se observa 
que los precios duales del primal con los valores del problema dual hay 
una diferencia que es el signo. Pero al momento que se ven los precios 
duales del problema dual con los valores del problema primal se ve que 
son iguales. 
 
 Los precios duales tienen el mismo valor tanto en la forma estándar 
como en la forma canónica excepto por el precio dual de la restricción 3 
con valor de 2 y -2 respectivamente para el problema. 
 
Precio dual 
 
El precio dual, costo marginal o precio marginal representa el valor por unidad 
de los recursos del problema de programación lineal; es decir cuánto está 
dispuesto a pagar por el incremento de una unidad del recurso. Con los precios 
duales y los costos reducidos se tiene una interpretación útil en dos aspectos: 
 
1.- Proporcionar un mejor entendimiento del problema de programación lineal 
como un sistema económico de entrada-salida. 
2.- Permitir una implementación eficiente del análisis. 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 40
 
Con base a los resultados de ambos problemas y la teoría estudiada 
anteriormente se puede observar: 
 
 Se muestra que la solución del dual proporciona los precios duales del 
primal, es decir los valores óptimos de las variables del dual son los 
precios duales del primal y viceversa. 
 
 Si una variable de decisión en un problema no es cero, la restricción 
asociada en el otro problema es obligatoria, es decir si una restricción 
tiene un precio dual distinto de cero es porque ésta es obligatoria. 
 
 Si una restricción en uno de los problemas es distinta de cero (slack or 
surplus), la variable asociada a esa restricción es cero (es decir el precio 
dual de la restricción es cero). 
 
 
 Tanto el problema primal como el problema dual son dos formas de 
abordar el mismo problema. Conviene no perder de vista la relación 
entre las variables básicas de un problema con las no básicas de su 
dual. Es decir, si una variable del primal es básica, la variable del dual 
asociada a ella es 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 es 
una variable básica. 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 41
CAPÍTULO 4 
Planteamiento y solución del problema de flujo máximo 
 
 
 
Suponiendo que se tiene una red de transporte (sistema de tuberías, sistema 
ferroviario, eslabones de comunicación, por el cual se desea enviar un producto 
homogéneo (petróleo, furgones, unidades de mensajes, desde un punto 
específico de la red conocido como nodo de origen o inicial a un destino 
designado conocido como nodo destino o sumidero. Además de los nodos de 
origen y destino, la red consta de un conjunto de nodos intermedios, llamados 
nodos de transbordo, los cuales están conectados entre sí a los nodos de 
origen y nodos destino mediante arcos o eslabones de la red. 
Los problemas de optimización de redes se pueden representar en términos 
generales a través de uno de estos modelos: 
1. Modelo de minimización de redes (Problema del árbol de mínima 
expansión). 
2. Modelo de la ruta más corta. 
3. Modelo de flujo máximo. 
4. Modelo de flujo a costo mínimo. 
5. Modelo de flujo máximo a costo mínimo 
 
En este capítulo se estudia el problema flujo máximo y la mejor manera de 
plantearlo como un problema de programación lineal, para así obtener la 
solución óptima y tomar una buena solución. 
 
 
4.1 El problema de flujo máximo 
 
El problema de flujo máximo determina el volumen máximo de un producto que 
puede ser enviado de un nodo oferta (origen, inicial) a un nodo de demanda 
(final, destino) a través de los enlaces (arcos) de una red. Donde en las 
restricciones del problema se considera, el flujo inicial, flujo final, la 
conservación del flujo en los nodos, las limitaciones en los enlaces 
(capacidades máximas o mínimas). 
 
Elobjetivo es conseguir la máxima capacidad de flujo entre el nodo inicial y el 
nodo final. 
 
Características: 
 
1. Todo flujo a través de una red conexa dirigida (anexo definiciones) se 
inicia en el nodo origen, y termina en el nodo destino. 
2. Los nodos restantes son nodos de trasbordo. 
3. Se permite el flujo a través de un arco sólo en la dirección indicada por 
la flecha, donde la cantidad máxima de flujo está dada por la capacidad 
del arco. En el nodo fuente, todos los arcos señalan hacia fuera. En el 
nodo destino, todos señalan hacia el nodo. 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 42
4. El valor óptimo es la cantidad total de flujo de la fuente al destino. Esta 
cantidad se mide en cualquiera de las dos maneras equivalentes, esto 
es, la cantidad que sale de la fuente (nodo inicial) o la cantidad que entra 
al destino (nodo final). 
 
Una de las formas de resolverlo es planteándolo como un problema de 
programación lineal mediante el método simplex. Otro método, es el algoritmo 
de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo 
máximo en una red de flujo; propone buscar trayectorias en los que se pueda 
aumentar el flujo, hasta que se alcance el flujo máximo; la idea es encontrar 
una ruta de penetración con un flujo positivo neto que una los nodos origen y 
destino. Su nombre viene dado por sus creadores, Lester Randolph Ford, Jr y 
Delbert Ray Fulkerson [ Juan Prawda, 1976, vol 1. Markhar Bazara, 1971, 
http://www.slideshare.net/DUANNY/clase9, 25-10-2011] 
 
4.2 Modelo de programación lineal de flujo máximo 
 
Generalmente, el problema de programación lineal de flujo máximo se plantea 
en la forma estándar considerando como igualdades las restricciones 
referentes a la conservación de flujo. Por tanto el modelo general es el 
siguiente: 
 
Maximizar z = xts 
 
Sujeto a 
  
t
sj
xij = xts si i = s (1) 
  
t
sj
xij -  
t
sk
xki = 0 si i  s ó t (2) 
 -  
t
sk
xki = -xts si i = t (3) 
 xij  uij 
 
 xij  0 
 
Donde: 
uij es la capacidad máxima de un enlace 
 xij es el flujo que transita del nodo i al nodo j 
s es el nodo inicial de la red (nodo de oferta o nodo fuente) 
t es el nodo final de la red (nodo de demanda o nodo destino) 
 
Restricción 1: la oferta que sale del nodo inicial, es la misma que llega al 
nodo final. 
 
La restricción 2: indica la conservación de flujo en cada uno de los 
nodos. Esto es, todo el flujo que llega a un nodo, tiene que salir. 
 
Restricción 3: señala que el flujo que llega al nodo final t, es igual al flujo 
que sale en el nodo inicial s. 
 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.slideshare.net/DUANNY/clase9,
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 43
Una manera muy fácil de recordar que signo le corresponde a los coeficientes 
de la conservación de flujo, es pensar que un arco que sale de un nodo es un 
ingreso (equivalente a vender), por ende se le asocia un signo positivo. Por otro 
lado, un arco que llega es comprar (egreso), por lo que le corresponde un signo 
negativo. 
 
Para ilustrar el problema de flujo máximo como un problema de programación 
lineal se considera la Red 1 como sigue: 
 
 
 
 
 
 
 
 
 
 
 
 
 
De acuerdo a la tercera restricción, se le agrega un arco imaginario que va del 
nodo t al nodo s, interpretando que la cantidad de flujo que sale del nodo t es la 
misma que llega al nodo s, como lo muestra la siguiente figura. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
De acuerdo a la red, el modelo matemático del problema de flujo máximo es el 
siguiente: 
 
Max z = xts 
 
Sujeto a 
 
xs2+xs3-xts=0 
x24-xs2=0 
x23-xs2=0 
5
2 
7 
t 
6 
5 
4
3 
9 
3
3 
4 
3 
2 
7 
s 
Red 1 
5
2 
7 
t 
6 
5 
4
3 
9 
3
3 
4 
3 
2 
7 
s 
Red 1.1 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 44
x45+x46-x24-x34=0 
x5t-x45-x65=0 
x6t+x65-x46=0 
xts-x5t-x6t=0 
xs2≤7 
xs3≤3 
x24≤3 
x34≤4 
x45≤3 
x46≤5 
x5t≤2 
x65≤9 
x6t≤7 
 
xij ≥ 0, i=s,2,…6,t. j=s,2,…6,t 
 
 El planteamiento para el programa LINDO es el siguiente; 
 
Max xts 
st 
xs2+xs3-xts=0 
x24-xs2=0 
x34-xs3=0 
x45+x46-x24-x34=0 
x5t-x44-x65=0 
x65+x6t-x46=0 
xts-x5t-x6t=0 
xs2<7 
xs3<3 
x24<3 
x34<4 
x45<3 
x46<5 
x5t<2 
x65<9 
x6t<7 
end 
 
 
El valor de la función objetivo es: 
1) 6.00 
 
 
VARIABLE VALUE 
REDUCED 
COST 
 Xts 6.000000 0.000000 
 Xs2 3.000000 0.000000 
 Xs3 3.000000 0.000000 
 X24 3.000000 0.000000 
 X34 3.000000 0.000000 
 X45 2.000000 0.000000 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 45
 
ROW 
SLACK OR 
SURPLUS DUAL PRICES 
 2) 0.000000 -1.000000 
 3) 0.000000 -1.000000 
 4) 0.000000 0.000000 
 5) 0.000000 0.000000 
 6) 0.000000 0.000000 
 7) 0.000000 0.000000 
 8) 0.000000 0.000000 
 9) 4.000000 0.000000 
 10) 0.000000 1.000000 
 11) 0.000000 1.000000 
 12) 1.000000 0.000000 
 13) 1.000000 0.000000 
 14) 1.000000 0.000000 
 15) 0.000000 0.000000 
 16) 9.000000 0.000000 
 17) 3.000000 0.000000 
Cuadro 4.2.1 
 
Interpretación 
 
La máxima cantidad que se puede enviar de un producto, partiendo del nodo s 
hacia el nodo t, son seis (6) unidades. 
 
Ahora una pregunta importante es, ¿Qué enlaces se ocupan y cuánto fluye en 
cada uno de ellos, para que lleguen esas seis (6) unidades? 
 
De acuerdo a los resultados obtenidos en el Cuadro 4.2.1, se muestra la red de 
flujo óptimo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
La interpretación es: 
 
 X46 4.000000 0.000000 
 X5t 2.000000 0.000000 
 X65 0.000000 0.000000 
 X6t 4.000000 0.000000 
4
2 
4 
t 
6 
5 
4
2 
0 
3
3 
3 
3 
2 
3 
s 
Red 1.2 
Solución óptima 
Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)
http://www.novapdf.com/
http://www.novapdf.com/
 
 
 46
De las seis unidades que parten del nodo s, éstas se trasladan de la siguiente 
manera: tres unidades se van rumbo al nodo 2, luego se van al nodo 4, de esas 
tres unidades una unidad se va al nodo 6 y después al nodo t; las otras dos 
unidades se van al nodo 5 y luego al nodo t. Las otras tres unidades restantes 
se van al nodo 3 y siguen hacia el nodo 4 y luego se van al nodo 6 hasta llegar 
al nodo t, estos valores se ven en la columna de valor en el Cuadro 4.2.1. 
 
Además indica porque arcos no pasó flujo dándole al arco el valor cero, un 
ejemplo es el arco formado por los nodos 6 y 5. También se observa en la 
columna de slack or surplus (holguras) a partir de la restricción 2 hasta la 
restricción 8 que todo flujo que entra también sale y de la restricción 9 a la 17 lo 
que se muestra es cuanta capacidad quedó en los arcos para pasar flujo; 
donde los arcos con valor cero se les conoce como arcos saturados. 
 
Igualmente se puede plantear el problema en la forma canónica: 
 
La formulación matemática del problema de flujo máximo en la forma canónica, 
es: 
 
Maximizar xts 
Sujeto a 
 
t
sj
xij  xts si i = s (1) 
 
t
sj
xij - 
t
sk
xki  0 si i  s ó t (2) 
-  
t
sk
xki  -xts si i = t (3) 
 
xij  uij 
xij  0 
 
La interpretación de las variables y de las