Indice

Unidad 1, PROGRAMACIÓN LINEAL

Programación lineal...........................................................................................................4
Introducción...................................................................................................................4
Elementos de la programación lineal............................................................................5
La función objetivo.....................................................................................................5
Las variables de decisión............................................................................................5
Ventajas y desventajas de la programación lineal........................................................6
Ventajas......................................................................................................................6
Desventajas................................................................................................................6
Estructura y construcción de modelos (en programación lineal)..................................6
La etapa de formulación comprende:........................................................................7
La etapa de construcción del modelo engloba:.........................................................7
La etapa de ejecución de los análisis comprende:.....................................................8
La etapa de implementación de los resultados y la actualización del modelo
comprende:................................................................................................................8
Ejercicios.....................................................................................................................8
Métodos de solución: simplex y gráfico..........................................................................10
Método Simplex de Programación Lineal....................................................................10
Objetivo del Método Simplex de Programación Lineal...........................................10
Importancia del Método Simplex de Programación Lineal.....................................10
Características del Método Simplex de Programación Lineal..................................11
Pasos del Método Simplex de Programación Lineal................................................12
Ventajas del Método Simplex de Programación Lineal...........................................12
Desventajas del Método Simplex de Programación Lineal......................................12
Ejercicios Método Simplex de Programación Lineal................................................13
Método Gráfico de Programación Lineal.....................................................................15
Objetivo de Método Gráfico de Programación Lineal.............................................16
Importancia de Método Gráfico de Programación Lineal.......................................16
Características de Método Gráfico de Programación Lineal...................................16
Pasos de Método Gráfico de Programación Lineal..................................................17
Ventajas de Método Gráfico de Programación Lineal.............................................18
Desventajas de Método Gráfico de Programación Lineal.......................................18

1
 Ejercicios Método Gráfico de Programación Lineal.................................................18
Métodos de solución de Planeación Lineal en enteros y mixta......................................20
La programación lineal Programación lineal entera....................................................20
La programación lineal Programación lineal mixta.....................................................20
Método de Gomory.....................................................................................................20
Métodos de Branch and Bound...................................................................................23
Método Aditivo de balas.................................................................................................25
Ejercicios Método Aditivo de balas..............................................................................27
Dualidad en programación lineal....................................................................................29
Relaciones entre problemas primales y duales...........................................................29
Importancia de la dualidad en programación lineal....................................................30
Ejercicio de un problema dual, paso a paso................................................................30
El modelo queda de la siguiente forma:......................................................................32
Teoremas de la dualidad en programación lineal.......................................................35
Unidad 2, PROBLEMAS DE TRANSPORTE Y ASIGNACIÓN
Problema del transporte.................................................................................................36
Modelo de transporte..................................................................................................36
El problema..................................................................................................................37
Solución mediante programación lineal......................................................................37
Bibliografía.......................................................................................................................41

2
Programación lineal
Introducción.
La Programación Lineal es una rama de la investigación de operaciones que
estudia la optimización de una función lineal sujeta a un conjunto de
restricciones, también lineales.
Su origen no es del todo claro ya que el contexto de la Guerra Fría dificultó la
difusión de los trabajos provenientes de la Unión Soviética. A pesar de estas
circunstancias, los pioneros en este campo son el matemático soviético Leonid
Kantorovich y el estadounidense George B. Dantzig.
La programació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. El método tradicionalmente usado para resolver problemas de
programación lineal es el Método Simplex.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70
personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación
lineal. La potencia de computación necesaria para examinar todas las
permutaciones a fin de seleccionar la mejor asignación es inmensa (factorial de
70, 70!) ; el número de posibles configuraciones excede al número de partículas
en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima
mediante el planteamiento del problema como una programación lineal y la
aplicación del algoritmo simplex. La teoría de la programación lineal reduce
drásticamente el número de posibles soluciones factibles que deben ser revisadas.

3
Elementos de la programación lineal.

La función objetivo

La función objetivo tiene una estrecha relación con la pregunta general que se
desea responder. Si en un modelo resultasen distintas preguntas, la función
objetivo se relacionaría con la pregunta del nivel superior, es decir, la pregunta
fundamental. Así 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.

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.
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 darles un valor
infinito a nuestras variables de decisión, por ejemplo, ¿qué pasaría si en un
problema que precisa maximizar sus utilidades en un sistema de producción de
calzado decidiéramos producir una cantidad infinita de zapatos? Por lo tanto,
vamos a tener muchas 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?

4
Pues bueno, entonces habríamos descubierto que nuestro sistema presenta una
serie de limitantes, tanto físicas, como de contexto, de tal manera que los valores
que en un momento dado podrían tomar nuestras variables de decisión se
encuentran condicionados por una serie de restricciones.

Ventajas y desventajas de la programación lineal.

Ventajas.

 Requieren menos tiempo y es menos caro que experimentar con el objeto

o la situación real.
 Permiten una identificación rápida de las expectativas esperadas.
 Reducen los riesgos asociados con la experimentación real.

Desventajas.

 Se pierde información (que puede ser relevante) del fenómeno que se está
estudiando.
 Las diferentes interpretaciones de la información, pueden ocasionar
resultados que estén lejos de la realidad.
 La recolección de datos puede ser muy costosa y complicada.
 Sensibilidad ante errores de medición; a veces pequeñas variaciones en los
datos ocasionan que se tengan resultados opuestos.

Estructura y construcción de modelos (en programación lineal)

Un modelo representa o describe los elementos relevantes de una situación y
sus interacciones existentes entre ellos. La concepción de un modelo tiene por
finalidad facilitar el entendimiento y la manipulación de las relaciones que
ocurren entre los diversos parámetros que integran un sistema o proceso,
abstraídas de una realidad.
Como el proceso de modelado depende del espíritu creativo del hombre, tal
vez no podemos definir claramente los límites de los modelos de
Programación Matemática y sus aplicaciones. Generalmente podemos decir
que su empleo clásico seria:
5
“Utilizar de forma eficiente recursos limitados y que pueden ser disputados por
actividades alternativas”
En los modelos matemáticos, la representación de determinado sistema es
generalmente realizada por tres conjuntos principales de elementos:
1. Variables de decisión y parámetros: las variables de decisión son las incógnitas
a ser determinadas por la solución del modelo. Los parámetros son los valores
fijos en el problema. Simbólicamente, las variables de decisión son representadas
por letras minúsculas con subíndices como: xi , i =1,2,3,...,n 
2. Restricciones: de modo a llevar en cuenta las limitaciones físicas del sistema,
el modelo debe incluir restricciones que limitan las variables de decisión a sus
valores posibles (o viables). Estas restricciones pueden ser expresadas
matemáticamente por medio de ecuaciones e inecuaciones.
3. Función objetivo: es una función matemática que define la calidad de la
solución en función de las variables de decisión. En forma general es
representada como una función de varias variables z = f (x1, x2,...,xn) .
Podemos resumir de forma sucinta los pasos del proceso de análisis cuantitativo
conforme se expresa en el siguiente flujo:

La etapa de formulación comprende:

 La definición de las variables controlables (de decisión o control) y las no

controlables (externas o de estado).
 La elaboración de la función objetivo y del criterio de optimización.
 La formalización de las restricciones del modelo.

La etapa de construcción del modelo engloba:

 La elaboración de la estructura de entrada y salida de información.

 Las fórmulas de interrelación.
 Los horizontes de tiempo.

6
La etapa de ejecución de los análisis comprende:

 Análisis de sensibilidad de la solución.

 Levantamiento de la precisión de los datos.
 Estudio de la estabilidad computacional.
 Levantamiento de las demás especificaciones del modelo.

La etapa de implementación de los resultados y la actualización del modelo

comprende:

 Un gran proceso de feedback repasando las etapas anteriores, haciendo

uso del modelo en el sistema de producción o prestación de servicios.

Ejercicios

Really Big Shoe es un fabricante de calzado deportivo para básquetbol y fútbol.

El gerente de marketing, Ed Sullivan, tiene que decidir la mejor forma de gastar
los recursos destinados a publicidad. Cada uno de los equipos de fútbol
patrocinados requiere 120 pares de zapatos. Cada equipo de básquetbol requiere
32 pares de zapatos. Los entrenadores de fútbol reciben $300,000 por concepto
de patrocinio para calzado, y los entrenadores de básquetbol reciben $1,000,000.
El presupuesto de Sullivan para promociones asciende a $30,000,000.

The Really Big Shoe dispone de una provisión limitada (4 litros, o sea, 4,000
centímetros cúbicos) de flubber, un compuesto raro y costoso que se utiliza en la
fabricación del calzado atlético de promoción. Cada par de zapatos para
básquetbol requiere 3 cc de flubber y cada par de zapatos de fútbol requiere 1 cc.
Sullivan desea patrocinar el mayor número de equipos de básquetbol y fútbol que
sus recursos le permitan.

 Formule un conjunto de ecuaciones lineales para describir la función

objetivo y las restricciones.
 Utilice el análisis gráfico para encontrar la solución visual.

7
Solución
a) El planteamiento del problema de programación lineal sería:
Variables:
x = Número de equipos de futbol a patrocinar
y = Número de equipos de básquetbol a patrocinar
Función Objetivo:
Z = Maximizar (x + y)
Restricciones:
Presupuesto: 300,000x + 1,000,000y ≤ 30,000,000
Flubber: 120x + 96y ≤ 4000
No negatividad: x, y ≥ 0
b)  Elaboración del gráfico

El área de color azul representa la región factible y la línea de color rojo indica la
función objetivo en su punto óptimo.

*Los mismos colores se utilizarán para todos los problemas.En el vértice D se

tiene los valores máximos:

 x = 700/57=12.28
 y = 500/19 = 26.32
 Z = 38.60
c) Dado que el número de equipos no puede ser un valor decimal
consideramos los siguientes valores:
 x = 12
 y = 26
8
Métodos de solución: simplex y gráfico
Método Simplex de Programación Lineal
El método simplex de programación lineal, se han resuelto dificultades de
programación lineal a través de un método geométrico. Este método no resulta
práctico cuando el número de variables se aumenta a tres, y con más variables
resulta imposible de utilizar. Ahora se examinará una técnica diferente, el método
simplex, cuyo nombre está asociado en análisis más avanzados a un objeto
geométrico al que se denomina simplex.

Este método comienza con una solución posible y prueba si es o no óptima. Si no

lo es, el método sigue a una mejor solución. Se dice mejor en el sentido de nueva
solución no es óptima, entonces se repite el procedimiento. En algún momento el
método simplex conduce a una solución óptima, si es que existe la misma.

También este método es eficaz, es completamente mecánico. De esta manera, no

implica el uso de geometría. Esto permite resolver problemas de programación
lineal que tiene cualquier número de restricciones y variables del problema.

Objetivo del Método Simplex de Programación Lineal

El objetivo del método simplex de programación lineal, es utilizado para resolver

problemas en todo tipo de problema reales de programación lineal generalmente
tienen variables de decisión y muchas restricciones. Tales problemas no pueden
ser resueltos gráficamente. Se usan algoritmos tales como los simples.

El método simplex es un procedimiento iterativo que progresivamente permite

obtener una solución óptima para los problemas de programación lineal. Existen
numerosos programas tanto para computadoras centrales como para personales.
Aunque el método simple es especialmente útil en problemas de gran escala.

Importancia del Método Simplex de Programación Lineal

Este método pertenece a la programación lineal debido a que se requiere que

todas las funciones matemáticas en este modelo sean funcionales lineales y como

9
sinónimo de planificación de los recursos, es decir, un resultado que alcance la
meta especificada en la mejor forma entre las alternativas factibles.

Es una técnica poderosa para tratar el problema de asignación de recursos

limitados entre actividades, así como para otros problemas que tengan un
planteamiento matemático semejante.

El método simplex es un algoritmo, un proceso en que se repite, un

procedimiento hasta lograr el resultado, determinando un proceso de arranque y
un criterio para determinar cuándo debe detenerse.

El método simplex se ha convertido en una herramienta estándar de gran

importancia para numerosas organizaciones comerciales e industriales. Además,
casi cualquier organización social tiene que ver con la asignación de recursos en
algún contexto y existe un reconocimiento creciente de la extremadamente
amplia aplicabilidad de la técnica del método. 

Este no solo aporta la solución óptima de las variables sino, su utilidad máxima,
y costo mínimo, sino también una gran cantidad de valiosa información
económica. Por esta razón resulta de vital importancia tanto el aprender las
técnicas de solución través de este método y además dominar ampliamente la
interpretación de resultados. 

Características del Método Simplex de Programación Lineal 

Algunas características de este método llamado simplex de programación lineal,

son las siguientes: 

 Es aplicable a problemas de Programación Lineal multidimensionales.

 Tiene como base el álgebra matricial y el proceso de eliminación de
Gauss-Jordán.
 Es un proceso de búsqueda que se vuelve sorprendentemente eficiente
para solucionar problemas muy grandes.
 Hoy en día puede aplicarse con eficiencia dad la diversidad de paquetes de
software que facilitan el proceso de cálculo. 

10
Pasos del Método Simplex de Programación Lineal

Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de
la región factible que normalmente es el origen, en cada iteración se mueve a otro
punto extremo adyacente hasta llegar a la solución óptima.

Los pasos son los siguientes:

 Manejando la forma estándar, determinar una solución básica factible

inicial igualando a la n-m variables iguales a cero o llamado también el
origen.
 Elegir la variable de entrada de las variables no básicas que al incrementar
su valor pueda mejorar el valor en la función objetivo. Cuando no exista
esta situación, la solución actual es la óptima; si no, ir al siguiente paso.
 Elegir la variable de salida de las variables básicas actuales.
 Establecer la nueva solución al hacer la variable de entrada básica y la
variable de salida no básica, ir de nuevo al paso 2.

Ventajas del Método Simplex de Programación Lineal

Las ventajas de este método, son las siguientes:

 Es un método heurístico. Se basa en consideraciones geométricas y no

requiere el uso de derivadas de la función objetivo.
 Es de gran eficacia incluso para ajustar gran número de parámetros.
 Es fácil de implementar y usar, y sin embargo tiene una alta eficacia.
 Se puede usar con funciones objetivo muy sinuosas pues en las primeras
iteraciones busca el mínimo más ampliamente y evita caer en mínimos
locales fácilmente.

Desventajas del Método Simplex de Programación Lineal

Las desventajas de este método, son las siguientes:

 Converge más lentamente que otros métodos pues requiere mayor número
de iteraciones.

11
Ejercicios Método Simplex de Programación Lineal

12
13
Método Gráfico de Programación Lineal
El Método Gráfico es poco poderoso ya que está limitado a resolver problemas
de dos o máximo tres variables de decisión. Sin embargo, su importancia radica
en que permite visualizar los conceptos matemáticos implicados en la
Programación Lineal.

Es un método poderoso, utilizado para resolver problemas de "n" variables de

decisión, aunque también se puede emplear para resolver problemas de dos
variables.

El método gráfico para solucionar a un problema de programación lineal es el

siguiente:

 Dibuje la región factible de las restricciones.

 Calcule las coordenadas de los puntos extremos.
 Sustituya las coordenadas de los puntos de esquina en la función objetiva
para ver cual da el valor óptimo. Este punto da la solución del problema de
programación lineal.
 Si la región factible no es acotada, este método puede ser erróneo:
soluciones óptimas siempre existen cuando la región factible está acotada, pero
pueden no existir en el caso no acotado.
 Si la región factible no es acotada, estamos minimizando una función
objetiva cuyos coeficientes son no negativos, entonces existe una solución dado
por este método.

Para determinar si existe una solución en el caso general no acotado:

 Acote la región por añadir una recta horizontal por encima del punto de
esquina más arriba, y una recta vertical a la derecha del punto de esquina
que esté más hacia la derecha.
 Calcule las coordenadas de los puntos nuevos de esquina que se obtiene.
 Halle el punto de esquina donde ocurre el valor óptimo de la función
objetiva.

14
  Si el valor óptimo se ocurre a un punto de esquina de la región original,
entonces existe la solución óptima a aquel punto.

Si ocurra el valor óptimo solo a un punto nuevo de esquina, entonces el problema

de programación lineal no tiene soluciones.

Objetivo de Método Gráfico de Programación Lineal

El método gráfico se utiliza para la solución de problemas de programación

lineal, representando geométricamente a las restricciones, condiciones técnicas y
el objetivo. El modelo se puede resolver en forma gráfica si sólo tiene dos
variables. Para modelos con tres o más variables, el método gráfico es impráctico
o imposible. Cuando los ejes son relacionados con las variables del problema, el
método es llamado método gráfico en actividad. Cuando se relacionan las
restricciones tecnológicas se denomina método gráfico en recursos.

Importancia de Método Gráfico de Programación Lineal

La importancia de Método Gráfico de Programación Lineal, radica en que

permite visualizar los conceptos matemáticos implicados en la Programación
Lineal. Este método es de poca importancia en lo relacionado a una aplicación
directa a problemas prácticos, debido a que los problemas prácticos significativos
involucran más de dos variables.

Sin embargo, el propósito es aprender una idea geométrica de la naturaleza del

problema, que será valiosa cuando se considere el método algebraico más
abstracto para el problema como veremos pueden ocurrir diversas situaciones
diferentes en conexión con los problemas de dos variables y cada una tiene una
solución para los de n variables, n>2.

Características de Método Gráfico de Programación Lineal

Algunas de las características de este método, llamado Método Gráfico de

Programación Lineal, son las siguientes:

15
  La metodología para la resolución de un problema de dos variables de
decisión.
 Es poco poderoso ya que está limitado a resolver problemas de dos o
máximo tres variables de decisión.
 Permite visualizar los conceptos matemáticos implicados en la
Programación Lineal.
 Puede ser impráctico o imposible.

Pasos de Método Gráfico de Programación Lineal

Los pasos necesarios para realizar el método son los siguientes:

 Ilustrar en forma de grafica las soluciones factibles, o el espacio de

soluciones, que satisfagan todas las restricciones en forma simultánea.
 Las restricciones de no negatividad Xi>= 0 confían todos los valores
posibles.
 El espacio encerrado por las restricciones restantes se determina
sustituyendo en primer término <= por (=) para cada restricción, con lo
cual se produce la ecuación de una línea recta.
 Delinear cada línea recta en el plano y la región en cual se encuentra cada
restricción cuando se considera la desigualdad lo indica la dirección de la
flecha situada sobre la línea recta asociada.
 Cada punto contenido o situado en la frontera del espacio de soluciones
satisfacen todas las restricciones y por consiguiente, representa un punto
factible. 
 Aunque hay un número infinito de puntos factibles en el espacio de
soluciones, la solución óptima puede determinarse al observar la dirección
en la cual aumenta la función objetivo.
 Las líneas paralelas que representan la función objetivo se trazan mediante
la asignación de valores arbitrarios a fin de determinar la pendiente y la
dirección en la cual crece o decrece el valor de la función objetivo.

16
Ventajas de Método Gráfico de Programación Lineal

Las ventajas que posee este método gráfico de programación lineal, son las
siguientes:

 Fácil de aprender, ya que gran parte del proceso es materia de enseñanza

media.
 Conocimiento de los conceptos básicos de la programación lineal.
 Facilita la comprensión de los métodos más complejos.

Desventajas de Método Gráfico de Programación Lineal

Las desventajas que posee este método gráfico de programación lineal, son las
siguientes:

 Solo resulta con modelos que tienen 2 o 3 incógnitas.

 Sólo sirve para problemas con dos variables de decisión.
 La Solución para la desventaja de Método Gráfico es el Método Simplex. 

Ejercicios Método Gráfico de Programación Lineal

Resolver gráficamente el siguiente sistema de ecuaciones:

Lo primero que hacemos es despejar la yy en ambas ecuaciones.

Primera ecuación:

Segunda ecuación:

17
Ahora vamos a calcular unos cuantos puntos de las dos funciones para
representarlas. Utilizaremos x=1x=1 y x=−1x=−1.

Para la primera función tenemos la tabla

Para la segunda función tenemos la tabla

Ahora representamos los puntos de cada tabla uniéndolos:

18
La solución del sistema es el punto donde las gráficas se cortan:

Métodos de solución de Planeación Lineal en enteros y mixta

La programación lineal Programación lineal entera
Son aquellos en que todas las variables únicamente pueden tomar valores enteros.
También se distinguen dentro de estos los problemas totalmente enteros como
aquellos en que tanto las variables como todos los coeficientes que intervienen en
el problema han de ser enteros.

La programación lineal Programación lineal mixta

Son aquellos en los que hay al mismo tiempo variables continuas y variables que
sólo pueden tomar valores enteros.

Método de Gomory
Los métodos de planos de corte parten de la resolución del P.L.C. asociado al
P.L.E. y tienen como objetivo lograr mediante la incorporación de nuevas
restricciones o planos de corte que las variables de decisión óptimas sean enteras.
Estas nuevas restricciones, restringen el conjunto factible del problema continuo
sin suprimir ninguna solución posible entera. La resolución de los sucesivos
P.L.C. generados conforme se van añadiendo los cortes se realiza mediante el
algoritmo del Simplex. La estructura de los cortes garantiza que la solución de
estos problemas converge a la solución del P.L.E.

Podemos distinguir entre, algoritmo fraccional de Gomory y algoritmo todo

entero de Gomory, en función de las características del problema.

Los métodos de los planos de corte resuelven el problema de la programación

lineal de la siguiente manera:

 Resolución del problema lineal continúo asociado.

19
  Si la solución óptima del problema es entera, ésta será la solución del
problema entero. En caso contrario se elige una de las variables de
decisión que debería ser entera y a partir de ella se construye el corte.
 Una vez añadido el plano de corte, se resuelve nuevamente el problema. Si
la solución óptima obtenida sigue sin ser entera, debemos repetir los pasos
anteriores hasta que dichas variables sean enteras. Sin embargo, si las
variables de decisión resultantes son enteras, se para el proceso, pues
hemos conseguido nuestro objetivo.

Ilustramos el método con un sencillo ejemplo:

Resolvemos el problema continuo asociado por el algoritmo del Simplex:

Aplicando el algoritmo del Simplex entra en la base la variable x y sale la

variable de holgura h2.

Solución óptima del problema continuo x = 7/2, y = 0 que no es entera ya que

x=7/2= 3+1/2. Construimos el corte utilizando la fila correspondiente a x en la
tabla del Simplex: 1/2h1 = 3 + 1/2 → 1/2h1 ≥ 1/2 y, añadiendo una nueva
variable de holgura s, -1/2h1 + s = -1/2.

La tabla modificada:

20
Aplicando el algoritmo Dual del Simplex, sale de la base s y entra h2.

La solución óptima del problema x=3, y=0.

A continuación, resolveremos el problema gráficamente. En la Gráfica 3.1.1. se

observa el conjunto inicial de soluciones factibles, mientras que, en la gráfica
3.1.2., aplicando el corte de Gomory vemos como el conjunto de soluciones se ha
visto reducido.

21
Métodos de Branch and Bound
Se pueden aplicar tanto a problemas de programación lineales enteros puros
como mixtos.

Los métodos de Branch and Bound (Ramificación y Acotación) se fundamentan

en dos procesos, el de acotar y el de ramificar, ambos diseñados con el fin de
hallar la solución entera óptima dentro del conjunto de soluciones factibles del
problema de programación lineal continúo asociado.

En el proceso de Ramificación, se incluyen restricciones diseñadas para eliminar

una parte de la región factible que no incluya soluciones enteras, generando
subproblemas del problema dado, de tal forma que todas las soluciones enteras
del problema inicial, estén incluidas en la unión de las regiones factibles de los
subproblemas generados. Repitiendo este proceso, un subproblema dejará de
ramificarse, cuando la solución óptima es entera; no es factible; o bien no se
pueden ramificar más problemas.

La Acotación reduce enormemente la generación de subproblemas. El proceso de

Acotación consiste en fijar como cota superior (en problemas de mínimos) o
inferior (en problemas de máximos), el mejor valor de la función objetivo en las
soluciones enteras, obtenidas en la resolución de los subproblemas generados
hasta el momento, y a partir de la cota se eliminan todos aquellos subproblemas,
para los cuáles el valor de la función es mayor o menor que la cota dada en
problemas de minimización o maximización, respectivamente. En caso contrario
se fija en ese mejor valor una nueva cota.

Los métodos Branch and Bound (Ramificación y Acotación) se basan en las

siguientes ideas:

 Resolución del P.L.C. asociado.

 Si la solución cumple con las condiciones de integridad, esa es la solución
del problema entero.
 Si la solución no cumple las condiciones de integridad, se elige una
variable no entera xi y a partir de ella se divide el problema en dos nuevos

22
 subproblemas con restricciones excluyentes, el primero con la restricción
xi ≥ [xi] +1 y el segundo con xi ≥ [xi].
 Si al resolver alguno de estos problemas obtenemos una solución entera,
ésta será un candidato al óptimo del problema lineal y el valor de la
función objetivo en esta solución, una cota. La obtención de dicha
solución entera, interrumpe además los procesos de Ramificación, en los
que el valor de la función objetivo en el óptimo del correspondiente
subproblema, sea o no entera, no supere el valor de la cota en problemas
de máximos o no lo disminuya en problemas de mínimos.
 El proceso de Ramificación se detiene por el criterio de Acotación
establecido o por ser un problema no factible.

Ahora en términos de mínimo, para una mejor comprensión del método,

obtenemos la solución aplicando el método de Branch and Bound:

Resolvemos el problema continuo asociado por el algoritmo del Simplex:

23
Aplicando el algoritmo del Simplex entra en la base la variable y, y sale la
variable de holgura h1.

Volviendo a aplicar el algoritmo del Simplex entra en la base la variable x, y sale

la variable de holgura h2.

La solución óptima para dicho problema es 𝑥 = 7/4 , 𝑦 = 7/4 , 𝑧 = −7/4 .

Seleccionaremos, por ejemplo, la variable 𝑥 = 1,75.

Método Aditivo de balas

Algoritmo aditivo de Balas Otro algoritmo enumerativo importante es el
algoritmo aditivo. Es debido originalmente a Egon Balas (1965). Se llama aditivo
porque todas las operaciones matemáticas que se realizan consisten en sumar o
restar. El procedimiento consiste en generar una secuencia de soluciones
parciales añadiendo encada iteración una variable y considerando las soluciones
complementarias (resto de soluciones posibles). De esta forma, podemos por
enumeración implícita, eliminar conjuntos de soluciones sin necesidad de

24
evaluarlos exhaustivamente. La selección de la variable añadida se hace en
función de reducir al máximo la infactibilidad en la solución actual y eliminar la
redundancia.

El método consta de los siguientes pasos (la k puede variar dependiendo de la

ramificación):

 El valor máximo de Z (cota superior) Zcota=∞ k=0. Checar la factibilidad

de la solución (0,0,…0), si no es factible continuar con el método, si es factible
entonces se ha llegado a la solución óptima.
 Ramificación: Se definen los subconjuntos de solución:
(x1,x2, … xk) como solución parcial
(x1, x2, … xk, xk+1, … xn) la segunda parte de la solución es el
complemento de la solución parcial.Selecciona a partir de la solución
parcial (x1, …xk) para hacer una partición y crear dos nuevas soluciones
parciales una xk+1=1 y otro con xk+1=0 y k=k+1
 Sondeo: Si alguna de las restricciones cumple:

Entonces no existe solución factible y se detiene la ramificación.

 Se complementa la solución haciendo xk+1=1-xk y el resto de las

variables igual a cero. Se calcula Z y si Zcota≠∞ y Z> Zcota → ya no se
ramifica.
 Si la solución es factible y Z< Zcota→Zcota=Z y se deja de analizar. Si la
solución es factible entonces ya no se ramifica. Regresar al paso 2.

Este método es un procedimiento de enumeración que encuentra el óptimo en

forma más rápida; en el método de Balas, la eficacia consiste en la evaluación
solo de unas soluciones. El método empieza poniendo todas las variables iguales
a cero y luego por medio de un procedimiento sistemático de forma consecutiva
se asigna a una por una de las variables el valor 1. Luego se reemplaza en cada
una de las restricciones y se averigua la infactibilidad. Por esta razón el método
es algunas veces llamado el algoritmo aditivo.

25
Para describir el algoritmo, se considera la forma general siguiente de un
problema de Programación Lineal con variables cero-uno.

Paso 1. La función objetivo debe ser del tipo minimización, contodos los
 

coeficientes no negativos.

Paso 2. Todas las restricciones deben ser del tipo £, con los lados derechos
negativos de ser necesario. Luego, estas restricciones se convierten a ecuaciones,
usando las variables auxiliares en el lado izquierdo de las restricciones.

Ejercicios Método Aditivo de balas

MAX Z = 3 Y1 + 2 Y2– 5 Y3 – 2 Y4 + 3 Y5

Sujeta a:

MIN W = – 3 Y1 – 2 Y2 + 5 Y3 + 2 Y4– 3 Y5

Con sus restricciones:

Reemplazamos: Y1 = 1 – X1; Y2 = 1 – X2; Y3 = X3; Y4 = X4; Y5 = 1 – X5

MIN W´ = 3 X1 + 2 X2 + 5 X3 + 2 X4 + 3 X5 – 8

Sujeta a:

26
Sustituimos W´ + 8 = W

MIN W = 3 X1 + 2 X2 + 5 X3 + 2 X4 + 3 X5

Con sus restricciones:

Siempre el problema nuevo a resolver consiste en la minimización de la función

objetivo, teniendo en cuenta la medida de la no factibilidad de la holgura.
Cuando la infactibilidad da el menor valor, continuamos con el siguiente paso; en
el caso de una infactibilidad cero, ésta corresponde a la solución óptima; si
encontramos varias infactibilidades iguales a cero, reemplazamos en la función
objetivo y la respuesta será la que haga esta función mínima.

X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0  1; 0  – 2; 0  – 1; Infactibilidad 3
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 2; 0  5; 0 – 12; Infactibilidad 12
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 2; 0  – 2; 0  5; Infactibilidad 2
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0  0; 0 – 5; 0 – 1; Infactibilidad 6
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 – 1; 0 2; 0 2; Infactibilidad 1
X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0  2; 0  1; 0  2; Infactibilidad 0
Solución Óptima Única:

X*1 = 0; X*2 = 0; X*3 = 0; X*4 = 0; X*5 = 1; W* = 3

Solución Óptima Única para el problema original:

Y*1 = 1; Y*2 = 1; Y*3 = 0; Y*4 = 0; Y*5 = 0; Z* = 5

27
Algunos autores emplean el algoritmo de Balas modificado, el cual consiste en
introducirle al modelo una restricción denominada de filtro, la cual no es otra que
la función objetivo con una cota inferior del valor óptimo. Históricamente es muy
importante, ya que ha demostrado que algoritmos eficaces de programación en
números enteros podrían emplear la enumeración implícita.

Dualidad en programación lineal

Cada uno de los problemas abordados hasta entonces en los módulos anteriores
se consideran problemas primales, dado que tienen una relación directa con la
necesidad del planteamiento, y sus resultados responden a la formulación del
problema original; sin embargo, cada vez que se plantea y resuelve un problema
lineal, existe otro problema ínsitamente planteado y que puede ser resuelto, es el
considerado problema dual, el cual tiene unas importantes relaciones y
propiedades respecto al problema primal que pueden ser de gran beneficio para la
toma de decisiones.

Los problemas primales y duales se encuentran ligados por una serie de

relaciones, saber la existencia de estas puede ser considerado de gran utilidad
para la resolución de problemas que parecen no factibles, o que no pueden ser
resueltos mediante un método en particular.

Relaciones entre problemas primales y duales

 El número de variables que presenta el problema dual se ve determinado
por el número de restricciones que presenta el problema primal.
 El número de restricciones que presenta el problema dual se ve
determinado por el número de variables que presenta el problema primal.
 Los coeficientes de la función objetivo en el problema dual corresponden
a los términos independientes de las restricciones (RHS), que se ubican
del otro lado de las variables.
 Los términos independientes de las restricciones (RHS) en el problema
dual corresponden a los coeficientes de la función objetivo en el problema
primal.

28
  La matriz que determina los coeficientes técnicos de cada variable en cada
restricción corresponde a la transpuesta de la matriz de coeficientes
técnicos del problema primal.

El sentido de las igualdades y desigualdades se comporta según la tabla

de Tucker, presentada a continuación.

Importancia de la dualidad en programación lineal

La resolución de los problemas duales respecto a los primales se justifica dada la
facilidad que se presenta dados problemas donde el número de restricciones
supere al número de variables. Además de tener gran aplicación en el análisis
económico del problema.

Otra de las ventajas que presenta, es que dado a que el número de restricciones y
variables entre problema dual y primal es inverso, se pueden resolver
gráficamente problemas que presenten dos restricciones sin importar el número
de variables.

Ejercicio de un problema dual, paso a paso

El siguiente problema a resolver es hasta el momento el modelo más completo de
los resueltos en los módulos anteriores, dado que trataremos de resolver un
problema primal y su dual mediante Método Simplex utilizando variables de
holgura, exceso y artificiales; además resolveremos el primal utilizando Simplex
maximizando y el dual minimizando.

Dado el siguiente modelo primal:

Función objetivo

ZMAX = 40X1 + 18X2

29
Restricciones

16X1 + 2X2 ≤ 700
6X1 + 3X2 ≤ 612
X1 ≤ 80
X2 ≤   120

Cuya respuesta es:

X1 = 28,75

X2 = 120

S1 = 79.5

S3 = 51.25

30
Función objetivo = 3310

Procedemos a resolver el problema dual

Este paso se lleva a cabo teniendo en cuenta las relaciones que se expusieron en
la definición de la dualidad. Ahora las variables en el dual las representaremos
por «ʎ» y corresponden a cada restricción.

El modelo queda de la siguiente forma:

ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4

16ʎ1 + 6ʎ2 + ʎ3 ≥ 40

2ʎ1 + 3ʎ2 + ʎ4 ≥ 18

ʎ1;ʎ4 ≥ 0

Ahora preparamos el modelo para ser resuelto mediante Método Simplex,

utilizaremos el procedimiento en el cual la función objetivo es multiplicada por (-
1) y resolveremos el modelo mediante maximización.

ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4

Lo que es igual

(-Z)MAX = -700ʎ1 – 612ʎ2 – 80ʎ3 – 120ʎ4

31
Ahora dado que los signos de las inecuaciones son mayor o igual procedemos a
volverlas ecuaciones agregando variables de exceso, recordemos que en este caso
las variables de exceso se restan del lado izquierdo de la igualdad, por ende.

16ʎ1    + 6ʎ2   + ʎ3     + 0ʎ4   – 1S1    + 0S2  = 40

21ʎ1    + 3ʎ2   + 0ʎ3   + ʎ4     + 0S1   – 1S2   = 18

ʎ1;ʎ4 ≥ 0

Recordemos que el Método Simplex solo es posible por la formación de la matriz

identidad, sin embargo en una matriz identidad no pueden ir coeficientes
negativos, el cual es el caso, por ende recurriremos al artificio
denominado «Método de la M grande» utilizando variables artificiales, las cuales
siempre se suman.

16ʎ1    + 6ʎ2   + ʎ3     + 0ʎ4   – 1S1    + 0S2   + 1A1  + 0A2  ≥ 40

21ʎ1    + 3ʎ2   + 0ʎ3   + ʎ4     + 0S1   – 1S2    + 0A1  + 1A2  ≥ 18

ʎ1; ʎ4 ≥ 0

Ahora si observamos la matriz identidad formada por las variables artificiales,

nuestra función objetivo es la siguiente (varía dada la incorporación de las nuevas
variables).

(-Z) MAX = -700ʎ1 – 612ʎ2 – 80ʎ3 – 120ʎ4 + 0S1 + 0S2 – MA1 – MA2

Recordemos que el coeficiente de las variables de holgura y exceso es 0, además

que los coeficientes de las variables artificiales es M, donde M corresponde a un
número grande poco atractivo cuyo signo en la función objetivo depende del
criterio de la misma, dado que la función es maximizar el signo es negativo.
Dado que utilizaremos el Método Simplex y no un software para la resolución
del modelo es necesario que M adquiera valor, en este caso será «-10000» un
número bastante grande en el problema.

Las iteraciones que utiliza el Método Simplex son las siguientes:

32
Podemos observar que todos los Cj – Zj son menores o iguales a 0, por ende
hemos llegado a la solución óptima del problema, sin embargo recordemos que la
función objetivo fue alterada en su signo al principio, por ende se hace necesario
regresarle su signo original a Zj y a la fila Cj – Zj.

(-Z)max = -3310   *           (-1)

Zmax = 3310

Podemos cotejar con la función objetivo del modelo primal y encontraremos que
hallamos el mismo resultado.

Ahora se hace necesario interpretar los resultados de la tabla dual respecto al

modelo primal, y esta interpretación se realiza siguiendo los siguientes
principios.

33
La interpretación del tabulado final del modelo dual es la siguiente:

Teoremas de la dualidad en programación lineal

 Si el modelo primal o dual tiene solución óptima finita entonces su
respectivo dual o primal tendrán solución óptima finita.
 Si el modelo primal o dual tiene solución óptima no acotada, entonces su
respectivo dual o primal no tendrán solución, será un modelo infactible.
 Si el modelo primal o dual no tiene solución entonces su respectivo dual o
primal no tendrán solución.
 Sea «A» un modelo primal cuyo modelo dual es «B», el modelo dual de
«B» es igual a «A», es decir «El modelo dual de un dual es un modelo
primal».

Unidad 2

34
Problema del transporte
El problema del transporte es un planteamiento clásico de las técnicas de
programación lineal. En este problema se pretende elegir el camino óptimo de
envío de una mercancía desde varios orígenes (por ejemplo, plantas de
producción) a diferentes destinos (centros de almacenamiento o consumo), de
forma que el coste sea mínimo.

Como en todo problema de programación lineal, han de cumplirse las siguientes

etapas:

 Definir las variables del problema (por ejemplo, las cantidades de partida
solicitadas en cada destino, el coste de envío de una unidad de mercancía a
cada destino).
 Escribir conceptualmente el sistema de inecuaciones asociado a las
restricciones del problema (por ejemplo, el número de unidades máximas
producidas en cada origen y las requeridas en cada destino).
 Definir conceptualmente la función objetivo, que determina el coste.

Modelo de transporte
El procedimiento de resolución de un modelo de transporte se puede llevar a
cabo mediante programación lineal común, sin embargo su estructura permite la
creación de múltiples alternativas de solución tales como los modelos de
asignación, o los métodos de flujos de red. También es posible emplear los
heurísticos más populares como Vogel, Esquina Noroeste o Mínimos Costos.

35
Los problemas de transporte o distribución son uno de los más aplicados en la
economía actual, dejando, como es de prever, múltiples casos de éxito a escala
global que estimulan la aprehensión de los mismos.

El problema
Una empresa energética colombiana dispone de cuatro plantas de generación para
satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín
y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones
de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá,
Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día
respectivamente. Los costos asociados al envío de suministro energético por cada
millón de KW entre cada planta y cada ciudad son los registrados en la siguiente
tabla.

Solución mediante programación lineal

El modelo básico de transporte es el modelo en el cual la cantidad ofertada es
igual a la cantidad demandada, como es el caso de este ejercicio, sin embargo
trasladar esta suposición a la realidad es casi imposible por lo cual hace falta
crear orígenes y/o destinos ficticios con el excedente de oferta y/o demanda (es
sugerible que se haga con la demanda).

Como ya lo hemos planteado en módulos anteriores el primer paso corresponde a

la definición de las variables, regularmente se le denomina a las variables de
manera algebraica Xi,j donde i simboliza a la fuente y j simboliza al destino. En
este caso i define el conjunto {Planta 1, Planta 2, Planta 3 y Planta 4}, y j define
el conjunto {Cali, Bogotá, Medellín y Barranquilla}. Sin embargo es práctico
renombrar cada fuente y destino por un número respectivo, por ende la variable
X1,2 corresponde a la cantidad de millones de KW enviados diariamente de la
Planta 1 a la ciudad de Bogotá.
36
El segundo paso corresponde a la formulación de las restricciones de oferta y
demanda, cuya cantidad se encuentra determinada por el factor entre fuentes y
destinos, en este caso 16 restricciones.

Restricciones de oferta o disponibilidad, las cuales son de signo ≤:

X1,1 + X1,2 + X1,3 + X1,4 ≤ 80

X2,1 + X2,2 + X2,3 + X2,4 ≤ 30
X3,1 + X3,2 + X3,3 + X3,4 ≤ 60
X4,1 + X4,2 + X4,3 + X4,4 ≤ 45
Restricciones de demanda, las cuales son de signo ≥:

X1,1 + X2,1 + X3,1 + X4,1 ≥ 70

X1,2 + X2,2 + X3,2 + X4,2 ≥ 40
X1,3 + X2,3 + X3,3 + X4,3 ≥ 70
X1,4 + X2,4 + X3,4 + X4,4 ≥ 35
Luego se procede a formular la función objetivo, en la cual se relaciona el costo
correspondiente a cada ruta.

ZMIN = 5X1,1 + 2X1,2 + 7X1,3 + 3X1,4 + 3X2,1 + 6X2,2 + 6X2,3 + 1X2,4 + 6X3,1 + 1X3,2 +
2X3,3 + 4X3,4 + 4X4,1 + 3X4,2 + 6X4,3 + 6X4,4

Luego se puede proceder al uso de la herramienta WinQSB para resolver el

modelo realizado, aquí están los resultados.

37
Este problema presenta una solución óptima alternativa, aquí los resultados.

38
Los análisis de dualidad y sensibilidad en los modelos de transporte resultan ser
bastante interesantes, pues pueden llegar a determinar aumentos de capacidad en
las fuentes si el precio sombra de las rutas en relación a ellas lo justifica.

39
Bibliografía

Amor, N. (29 de Marzo de 2013). slideshare. Obtenido de

https://es.slideshare.net/nellysamor/metodo-simplex-metodo-grafico-raiza
Bustamante, P. (15 de Enero de 2018). metodosdeprogramacionentera. Obtenido
de
https://sites.google.com/site/metodosdeprogramacionentera/clasificacion-
de-metodos/metodo-aditivo-de-balas
Docio, M. R. (27 de Julio de 2015). uvadoc. Obtenido de
https://uvadoc.uva.es/bitstream/handle/10324/15593/TFG-E-125.pdf?
sequence=7
Llopis, J. (8 de febrero de 2016). MatesFacil. Obtenido de
https://www.matesfacil.com/ESO/sistema-ecuaciones/metodo-grafico/met
odo-grafico-sistemas-ecuaciones-lineales-resueltos-grafica-recta-
interseccion-solucion-interseccion.html
López, B. S. (11 de Junio de 2019). Ingenieria Industrial online. Obtenido de
https://www.ingenieriaindustrialonline.com/investigacion-de-
operaciones/problema-del-transporte-o-distribucion/
Respreto, O. (6 de abril de 2020). klasesdematematicasymas. Obtenido de
https://www.klasesdematematicasymas.com/pdfs/investigacion/Metodo-
Simplex.pdf

40