UNIVERSIDAD DE ANTOFAGASTA

FACULTAD DE INGENIERÍA
DEPTO. INGENIERÍA INDUSTRIAL

Investigación
de operaciones 1

PROFESOR: Verónica Díaz

Francis Balbontín Escorza
Flor Matamala

2013
 UNIVERSIDAD DE ANTOFAGASTA
FACULTAD DE INGENIERÍA
DEPTO. INGENIERÍA INDUSTRIAL

INDICE
Página
CAPÍTULO I: ASPECTOS INTRODUCTORIOS .................................................................. 1
1.1.- INTRODUCCIÓN ...................................................................................................... 1
1.2.- DEFINICIÓN DEL PROBLEMA Y RECOLECCIÓN DE DATOS ............................ 4
1.3.- FORMULACIÓN DE UN MODELO MATEMÁTICO .............................................. 5
1.4.- OBTENCIÓN DE UNA SOLUCIÓN A PARTIR DE UN MODELO ......................... 7
1.5.- PRUEBA DEL MODELO .......................................................................................... 8
1.6.- PREPARACIÓN PARA LA APLICACIÓN DEL MODELO ..................................... 9
CAPÍTULO II: PROGRAMACIÓN LINEAL ....................................................................... 10
2.1.- INTRODUCCIÓN .................................................................................................... 10
2.2.- RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL (PPL)
MEDIANTE EL MÉTODO GRÁFICO (DOS VARIABLES DECISIONALES) .............. 13
2.2.2.- Análisis De Casos Excepcionales ....................................................................... 21
2.2.2.1.- Solución No Acotada ................................................................................... 21
2.2.2.2.- Acotamiento ................................................................................................ 22
2.2.2.3.- Inconsistencia .............................................................................................. 23
2.2.2.4.- No Factibilidad ............................................................................................ 23
2.3.- FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL .................. 24
2.4.- MÉTODO SIMPLEX DE LA PROGRAMACIÓN LINEAL .................................... 29
2.4.1.- Reglas De Programación Lineal ......................................................................... 31
2.4.2.- Terminología Básica ........................................................................................... 34
2.4.3.- Teoría del Problema Del Programación Lineal.................................................... 35
2.4.4.- Obtención de una Solución Básica Factible ........................................................ 36
2.4.4.1.-Forma Matricial ............................................................................................ 37
2.4.5.- Pasos del método simplex ................................................................................... 38
2.4.6.- Interpretación Económica ................................................................................... 42
2.5.- METODO DE LA GRAN M ..................................................................................... 44
2.6.- METODO DE DOBLE FASE ................................................................................... 47
2.7.- CASOS ESPECIALES DE PPL MEDIANTE TABLEAU ........................................ 51
2.7.1.- Problema Con Soluciones Óptimas No acotado .................................................. 51
2.7.2.- Problema Con Soluciones Óptimas Múltiples .................................................... 53
2.7.3.- Problema Sin Soluciones o Infactible ................................................................. 56
2.7.4.- Problema Con Soluciones Degeneradas .............................................................. 58
La resolución mediante el método simplex es: ....................................................................... 58
CAPITULO III: DUALIDAD Y ANÁLISIS DE SENSIBILIDAD ....................................... 60
3.1.- DUALIDAD ............................................................................................................. 60
3.1.1.- Formulación del Problema Dual. ........................................................................ 60
3.1.2.- Teoremas de Dualidad ........................................................................................ 65
3.1.4.- Solución Del Problema Dual .................................................................................. 66
3.1.5.- Interpretación Económica De Las Variables Duales ............................................ 70
3.1.6.- Método Simplex Dual......................................................................................... 72
3.1.7.- Transformación de Tabla Óptima Primal a una Tabla Óptima Dual .................... 74
 UNIVERSIDAD DE ANTOFAGASTA
FACULTAD DE INGENIERÍA
DEPTO. INGENIERÍA INDUSTRIAL

3.2.- ANÁLISIS DE SENSIBILIDAD Y PROGRAMACIÓN PARAMÉTRICA

(ANÁLISIS POST-OPTIMAL) ......................................................................................... 77
3.2.1.- Análisis De Sensibilidad Para Cambios Discretos ............................................... 78

3.2.1.1.-Cambios Del Vector b : ............................................................................. 78

3.2.1.2.-Cambios En El Vector C : ............................................................................ 82
3.2.1.3.- Cambio En El Coeficiente Tecnológico a j Cuando J No Es Básico:........... 88
3.2.1.4.- Adiciones De Nuevas Actividades X j :........................................................ 91
3.2.1.5.- Adición De Nuevas Restricciones: ............................................................... 94
3.2.2.- Cambios Continuos Y Programación Paramétrica ............................................... 98
3.2.2.1.- Cambio Continuo En El Vector C ................................................................ 98
3.2.2.2.- Cambio Continuo En El Vector b............................................................... 105
3.2.2.3.- Cambio Continuo En Una Columna Tecnológica No Básica a j De A ........ 109
 CAPÍTULO I: ASPECTOS INTRODUCTORIOS

1.1.- INTRODUCCIÓN
El origen de la investigación de operaciones (IO) surge durante la segunda guerra
mundial, cuando existía una necesidad urgente de asignar recursos escasos a las
distintas operaciones militares y actividades dentro de cada operación en la forma
más efectiva. La fuerza aérea Británica formó el primer grupo de IO, aunque se
acepta como origen de la investigación de operaciones al tiempo de la división y
especialización del trabajo; junto a ello, fueron apareciendo nuevos tipos de
problemas cada vez más complejos y especializados en donde, generalmente, se
pierde el horizonte de solución del todo (objetivo general) por lo específico (objetivo
particular), creándose el problema de asignación de recursos.

Hay dos factores que ayudan al desarrollo de esta temática: primero, es el gran
conocimiento desarrollado y adquirido en esta área producto de la especialización del
trabajo y técnicas productivas, a modo de ejemplo: el método Simplex para resolver
problemas de programación lineal (por Dantzig), así como: también programación
dinámica, líneas de espera, teoría de inventarios, etc. El segundo factor fue el
avance computacional, ya que disminuyó el tiempo de resolución de problemas muy
tediosos y largos por forma manual, por lo cual, se implementaron muchos
programas asociados a estas temáticas.

En el caso particular de Chile, hablar de investigación de operaciones es solo es

posible en grandes empresas o grupos de empresas comunes, ya que el costo de
infraestructura y de equipos especializados junto al desconocimiento de las mismas,
hace poco probable la utilización de las diferentes técnicas en las PYMES.

La investigación de operaciones se ocupa de la modelación cuantitativo (matemático)

de sistemas reales de administración complejos y que permitan tomar una decisión
óptima, utilizando tanto técnicas y metodologías científicas como experimentales.

La IO se aplica a problemas que se refieren a la conducción y coordinación de

operaciones (o actividades) dentro de una organización, aplicándose a la
manufactura, transportes, la construcción, telecomunicaciones, planeación financiera,
salud, etc, es decir, para todo o cualquier tipo de generación de algún producto,
entendiéndose por un bien o servicio.

Categorías de problemas:
Problemas determinísticos: Son aquellos en que toda la información necesaria
para obtener una solución se conoce con certeza.
Problema estocástico: Son aquellos en que parte de la información necesaria
no se conoce con certeza, sino más bien se comporta de una manera
probabilística.

1
Tipos de decisiones:
Decisiones estratégicas: Una decisión de una sola vez que involucra políticas
con consecuencia a largo plazo para la organización. Ej. Expansión de líneas
de producción, Políticas de administración de inventarios.
Decisiones operacionales: Una decisión que implica aspectos de planificación
de corto plazo que, generalmente, se deben hacer repetidamente. Ej.
Programación de la producción.

Pasos de la investigación de operaciones:

Observación cuidadosa y definición del problema, incluyendo la toma de
datos.
Construcción del modelo científico (generalmente matemático) que es una
abstracción de la realidad, aquí se propone la hipótesis de que el modelo es
una buena representación de la realidad, para que así las conclusiones o
soluciones sean válidas para el problema real.
Realización de experimentos para probar la hipótesis
Validación del modelo.
Conclusiones.
Definición del
Modelo

Desarrollo de
un Modelo
Matemático

Resolución
de un Modelo
Matemático

Solución

Modelo Implementa-
Modificado ción

NO ¿Es válida la SI
solución?

La IO apunta a la solución más efectiva del todo, no de un componente o elemento

en particular, es por ello que busca una mejor solución (solución óptima) para el

2
problema en cuestión. Se dice una mejor solución y no la mejor solución, porque
puede haber varias mejores soluciones (empate), en estos casos prevalece el juicio
del tomador de decisiones en la elección final.

Las hipótesis que se plantean son:

Método que represente el sistema real
Las soluciones y conclusiones son válidas para el problema real

Según Ackoff y Sasiene, las características esenciales de la IO, expresadas en estas

definiciones son:
Su orientación de sistemas
El uso de equipos multidisciplinarios
La aplicación del método científico a problemas de control

Para atacar de una buena forma problemas reales de IO se necesita grupos

interdisciplinarios, así se tienen diferentes enfoques o perspectivas de solución.

La IO se base, generalmente, en lo cuantitativo, pero esto no significa que siempre

sea así. De esta manera, los modelos de IO se representan a través de ecuaciones,
que aunque puedan resultar complicadas desde el punto de vista matemático, tienen
una estructura matemática fundamental muy sencilla.
U f X i , Yi
sa :
f ( xi , yi )
Donde:
U : utilidad o valor de la ejecución del sistema. Se le denomina función objetivo
xi : variable o constante no controlable, pero que afecta a U, se le denomina
variables exógenas al modelo.
yi : son variables controlables, se les denomina variables endógenas.

Además, se requiere de una o más ecuaciones o inecuaciones para expresar el

hecho de que algunas variables controlables o todas, pueden manejarse solo dentro
de ciertos límites o rangos.

Luego, se resuelve el modelo matemático, encontrando los valores de las variables

controlables que optimizan el sistema bajo estudio. La solución del sistema puede
obtenerse mediante la simulación del mismo por medio de análisis matemático.

Los valores de optimización de la solución, mejora la ejecución del sistema solo si el

modelo es una buena representación del mismo, por lo tanto, debe probarse la
correspondencia del modelo a la realidad y valorar la solución.

Las principales etapas que se describen, se deben entender como guías para la
selección y adopción del problema y su solución. Pueden ser evolutivas iterativas
dependiendo de la información disponible.

3
Las tareas principales que se deben, en general, ejecutar en cada etapa son:
Identificar, analizar, evaluar, ordenar, y priorizar los elementos que la componen. La
secuencia descrita en el punteo no es, por lo tanto, imperativa.

Una manera de resumir las etapas usuales (no secuenciales) de un estudio de IO es

el siguiente:
Definición del problema de interés y recolección de datos relevantes.
Formulación de un modelo matemático que representa el problema.
Desarrollo de un procedimiento basado en computación para derivar una
solución al problema a partir del modelo.
Prueba del modelo y mejoramiento, según sea necesario.
Preparación para la aplicación del modelo descrito por la administración.
Puesta en marcha.

1.2.- DEFINICIÓN DEL PROBLEMA Y RECOLECCIÓN DE DATOS

Generalmente, los problemas están descritos de una manera vaga y muy general,
lleno de datos que sirven, pero algunos son innecesarios, por lo menos, para el
objetivo que se quiere cumplir, por ello, lo primero que se debe hacer al enfrentarse a
un problema es el estudio del sistema relevante y realizar un resumen bien definido
de lo que se pretende analizar, esto incluye objetivos apropiados, restricciones,
interrelaciones del área bajo estudio con otras áreas de la organización, cursos de
acción posibles, límites de tiempo para tomar la decisión correspondiente, etc. Este
proceso de definir el problema es crucial, ya que de ello depende el tipo y calidad de
la solución que se obtenga.

Se debe definir en forma clara y explicita, para obtener una respuesta correcta a
partir del problema correcto; debe existir un acuerdo completo de entre las personas
que participen en el estudio, además de una medida clara y explícitamente
establecida, de efectividad que esté en armonía con los objetivos o metas globales
de la organización.

El equipo de IO o analistas de operaciones son los que plantean soluciones en un

sentido de asesoría a los reales tomadores de decisiones, pero estos deben apoyar
de igual forma a este equipo.

La IO se encarga del bienestar de toda la organización o estudio, no del bien de un

departamento específico o elemento en particular, buscando soluciones óptimas
globales y no soluciones subóptimas.

En organizaciones con fines de lucro, generalmente, se usa la maximización de la

ganancia a largo plazo, evitando problemas de suboptimización, obviamente
considerando el valor del dinero en el tiempo, lo de largo plazo proporciona la
flexibilidad de las actividades que no se traducen inmediatamente en ganancias
(ejemplo investigación y desarrollo), pero siempre hay que tener en cuenta que no es

4
el único tipo de objetivo a cumplir, esto dependerá del criterio a satisfacer por los
demandantes del estudio (ejemplo una empresa).

Generalmente hay 5 elementos involucrados en las decisiones sociales en un país:

Los dueños (accionistas, etc.) que desean obtener ganancias (dividendos,
valuación de las acciones, etc.).
Los empleados que desean un empleo seguro con sueldos razonables.
Los clientes que quieren un producto confiable a un precio justo.
Los vendedores que piensan en la integridad y el precio justo de venta para
los productos que manejan.
El gobierno, por ende la Nación, que quiere el pago de impuestos justos y que
se tome en cuenta el interés nacional.

Hay que tener cuidado al recolectar los datos, ya que generalmente son datos
insuficientes o a veces los datos proporcionados son obsoletos, por ello, hay que
revisar que la base de datos recolectada sea actualizada a los objetivos del estudio.

1.3.- FORMULACIÓN DE UN MODELO MATEMÁTICO

Los encargados del estudio deberán decidir sobre el modelo mas adecuado para
representar la esencia del sistema en estudio, recordando siempre que es sólo “una
aproximación de un sistema real”.

El modelo expresará el problema de “elegir valores para las variables de decisión

que optimicen una función objetiva, sujetos al cumplimiento de restricciones dadas”.
Tiene la ventaja de ser conciso, comprensible, explicitar las relaciones causa-efecto,
clasificar los datos importantes para el análisis, y facilitar el manejo posibilitando el
uso de computadores.

Posee algunas desventajas ya que un modelo es sólo una aproximación de un

sistema real para hacerlo manejable y debe ser validado y probado para mejorar su
exactitud de predicción. Su construcción es evolutiva o iterativa, debiendo
comenzarse en forma sencilla y se va mejorando, hasta lograr un equilibrio deseado
entre precisión y manejo.

El análisis hecho previamente hay que ordenarlo y presentarlo de la manera más

conveniente, generalmente, es por medio de un modelo matemático, para ello existe
o se definen las variables de decisión (x1, x2,…, xn), que son a las cuales les
buscaremos los mejores valores que den por resultado la solución óptima.

Pasos generales en la construcción de modelos matemáticos:

Identificación de los datos del problema
Identificación de las variables de decisión
Identificación de la función objetivo
Identificación de las restricciones

5
La función planteada sea maximizar o minimizar se llama función objetivo, todas las
limitaciones que se tengan para llevar a cabo cursos de acciones diferentes se
llaman restricciones (generalmente planteadas como desigualdades). Toda constante
de modelo incluida en la función objetivo o en las restricciones se llaman parámetros
del modelo.

En la vida real (problemas) los valores de los parámetros se deben estimar, a

diferencia de los problemas teóricos en que éstas son dadas; es por ello, que la
estimación del parámetro (bajo un criterio de incertidumbre) debe someterse a un
análisis de sensibilidad para ver de que forma cambiaría la solución (si es que
cambian) debido a la estimación misma.

Hay que dejar en claro que para la solución de un problema no existe una
formulación única de un modelo, para un mismo problema pueden existir varios
modelos útiles.

Identificación de la función objetivo.- lo más común puede ser: maximizar las

ganancias a largo plazo o minimizar las pérdidas a largo plazo, pero puede ser
también mantener estables las ganancias, maximizar la participación del mercado,
diversificar la producción, mantener la estabilidad en los precios maximizar las
condiciones del trabajo, etc. Generalmente, se puede hacer en tres etapas:
Establecer el objetivo en forma verbal
Descomponer el objetivo en una suma, diferencia o producto de cantidades
individuales.
Expresar las cantidades individuales matemáticamente, utilizando las
variables de decisión y otros datos conocidos en el problema.

Identificación de las restricciones.- Las restricciones son condiciones que las

variables de decisión deben satisfacer para constituir una solución aceptable, que
limitan el espacio de búsqueda de la solución al problema, las que pueden provenir
de interrelaciones entre subsistemas, plazos o límites de tiempo, costos o beneficios
y en su forma de medirlos , y de los efectos posibles en las diferentes partes
involucradas; además, de la empresa misma como: los dueños (accionistas, los
empleados, los clientes, los vendedores, el gobierno y la nación. Por lo general,
surgen de:
Limitaciones físicas
Restricciones impuestas por la administración
Restricciones externas
Relaciones implicadas entre variables
Restricciones lógicas sobre variables individuales.

Uno de los modelos relativamente más sencillos de resolver son los de programación
lineal, que se pueden usar para:
Mezcla de productos que maximice la ganancia
Diseño de terapia de radiación que combata de manera efectiva un tumor y a
la vez minimice el daño al tejido sano circundante.

6
 Asignación de acres a distintas cosechas para maximizar el rendimiento total
neto.
Combinación de métodos de control de contaminación que logren estándar de
calidad del aire a un costo mínimo, etc.

El modelo matemático analiza mejorar las variables relevantes y su causa-efecto. Al

recordar que el modelo es una abstracción de la realidad capaz de predecir sucesos
de acuerdo a las condiciones de entrada, debe existir una alta correlación entre la
predicción del modelo y lo que ocurre en la vida real.

Si en el estudio se contempla más de un objetivo es necesario transformar y

combinar las medidas respectivas en una medida compuesta de efectividad llamada
medida global de efectividad.

1.4.- OBTENCIÓN DE UNA SOLUCIÓN A PARTIR DE UN MODELO

El estudio de IO consiste en desarrollar un procedimiento (o programa) para derivar
una solución al problema a partir del modelo planteado, es decir, la solución óptima.

Determinar las expresiones cuantitativas limitantes o restricciones.- representa lo

disponible o posible a disposición del sistema en estudio. Se expresan en función de
los parámetros y de las variables de decisión. En general, a mayor cantidad de
restricciones mayores costos en la realidad.

Es necesario determinar si el modelo formulado (o descrito) se ajusta o no a algún

modelo matemático conocido. Lo que permitiría dada la naturaleza y complejidad del
modelo identificado, usar o no una solución.

De esta manera, la solución se puede obtener a partir de: analítica, obtenida a partir
del conjunto de ecuaciones o funciones que miden efectividad (criterio) o
disponibilidad (restricciones); simulada o estadística, cuando la complejidad es alta o
no existen funciones matemáticas que representen a unas restricciones o
limitaciones; y heurística, cuando existan decisiones cualitativas o de experiencia que
no pueden cuantificarse. Estas soluciones serán satisfactorias, pero no óptimas (sólo
cercanas a estas) o Mixtas por combinación de las anteriores.

Herbert propone el término satisfacer en vez de optimizar, ya que como la

optimización depende de las fronteras y condiciones de entrada, lo que a veces se
aleja de lo real (el modelo), entonces con el satisfacer se busca una solución lo
suficientemente buena para el problema que se tiene; Según Samuel Elion optimizar
es la ciencia de lo absoluto, satisfacer es el arte de lo factible (solución subóptima).

Obtención o deducción de la solución del modelo.- En general, esta etapa no es la

parte más principal, por ejemplo: si se trabajó bien en las etapas anteriores y se tiene
un modelo matemático conocido, entonces se tiene un algoritmo ya establecido. Se
estudiarán varios algoritmos establecidos para modelos analíticos. Si el modelo

7
pertenece a los demás tipos, el concepto de optimalidad (u óptimo) no está bien
estructurado y sólo obtendremos una solución buena o satisfactoria, que se debe
analizar y mejorar (si se puede) en los pasos que sigan.

Siempre se debe recordar que un modelo es una abstracción de un problema real

(teoría versus realidad), por lo que habrá que revisar o ajustar los parámetros del
modelo del sistema lo que se llama “análisis posoptimal” o de “sensibilidad”.

El encontrar la solución a un problema de IO, independiente de que sea óptima o sub

óptima, se hace necesario realizar un análisis posóptimo que es un análisis de
sensibilidad para determinar qué parámetros del modelo son los más críticos
(parámetros sensibles) al determinar la solución.

Los parámetros sensibles del modelo son aquellos cuyos valores no se pueden
cambiar sin que la solución óptima cambie.

Algunos parámetros del modelo representan políticas de decisión (como asignación

de recursos), si es así, existe alguna flexibilidad sobre los valores asignados a estos
parámetros.

El análisis posóptimo, al igual que la prueba del modelo, incluye la obtención de un

conjunto de soluciones que comprende una serie de aproximaciones, cada vez
mejores al curso de acción ideal. Estas aproximaciones (iteraciones) se repiten hasta
que las mejoras a la solución sean demasiado pequeñas para justificar su
continuación.

1.5.- PRUEBA DEL MODELO

La prueba del modelo matemático es similar a la prueba de un programa, ya que una
vez hecho siempre se encuentran fallas (pequeñas o no) las que se van mejorando
hasta un nivel aceptable o válido. A este proceso se le llama validación del modelo.

La forma en cómo se lleva a cabo esta validación dependerá de la complejidad del

problema y del modelo utilizado.

Hay que tener cuidado con el empleo de las unidades, es decir, que sean
dimensionalmente consistentes.

Un modelo es válido, si independiente de sus inexactitudes de representación, puede

reproducir en forma confiable el funcionamiento del sistema real bajo estudio.

Se utilizan datos pasados (valores de variables de decisión y para metas) como

entradas, el modelo produce resultados los que se comparan con las salidas
obtenidas del pasado.

8
Por supuesto que no hay garantías de que el comportamiento futuro sea similar al
pasado; si el sistema es nuevo no hay datos históricos, por lo que para probarse,
deberá usarse simulación, o arriesgarse haciendo operar el sistema y el modelo (con
o sin cambios).

Una vez hecho el modelo se usan técnicas (a veces) retrospectivas, sobre la

estimación de comportamientos pasados para ver “qué hubiera pasado si se
hubiesen tomado tales medidas”, sirve para analizar desempeños hipotéticos o áreas
que no funcionan muy bien.

Las condiciones reales pueden cambiar mucho, haciendo que el modelo sea no
válido (ej. Parámetros muy diferentes, renovación de las máquinas con tecnología
diferente, etc.), por lo que, se deben establecer los controles adecuados para
determinar cualquier cambio significativo del sistema real (procedimientos
sistemáticos, controles estadísticos, etc.)

1.6.- PREPARACIÓN PARA LA APLICACIÓN DEL MODELO

Una vez validado el modelo se debe implementar un sistema bien documentado para
aplicar el modelo según lo establecido por la administración, esto debe incluir el
modelo y el procedimiento de solución (análisis posóptimo) y los procedimientos
operativos para su implementación.

Se ejecuta la solución deducida a partir del modelo. Se explica a los ejecutivos y se

documenta, usando los procedimientos que se utilizan en el sistema real. Se debe
definir normas estándares y observar las respuestas y conductas del sistema a los
cambios; conviene que la administración superior participe en todas las etapas del
estudio de I.O. para lograr la implementación de los resultados al sistema real.

9
 CAPÍTULO II: PROGRAMACIÓN LINEAL

2.1.- INTRODUCCIÓN
La aplicación de la programación lineal se está ampliando muy rápidamente a todas
las áreas del quehacer, tanto a nivel ingenieril como de otras especialidades.

En la vida real, las organizaciones operan con recursos escasos y todas ellas tienen
que tomar decisiones sobre cómo asignar estos recursos, continuamente la dirección
debe asignar estos recursos escasos para alcanzar las metas de la organización.

El tipo más común de aplicación abarca el problema general de asignar recursos

limitados entre actividades competitivas de la mejor manera posible (forma óptima),
este problema incluye elegir el nivel de ciertas actividades que compiten por recursos
escasos necesarios para realizarlas. Los niveles de actividad elegidos dictan la
cantidad de cada recurso que consumirá cada una de ellas.

La programación lineal utiliza el modelo matemático para describir el problema. El

adjetivo lineal significa que usa funciones lineales (de orden 1) y la palabra
programación es sinónimo de planeación. Así la programación lineal trata de la
planeación de las actividades para obtener un resultado óptimo, esto es, el resultado
que mejor alcance la meta especificada entre todas las alternativas de solución.

Existe un método de solución eficiente para este tipo de problemas llamado Método
Simplex y existen en el mercado programas computacionales que se apoyan en
ellos, tales como: Lindo, Lingo, AMPL, GAMS, OPL, POM, etc.

Cuando los problemas planteados tienen implicadas dos variables, la solución se

puede desarrollar por el MÉTODO GRÁFICO, donde se grafican todas las
restricciones, quedando un área achurada llamada área o zona o región de solución
factible (ASF o ZSF o RSF), esto significa que cualquier punto de esa área es
factible, es decir, debe satisfacer todas las restricciones (pudiese ser una solución),
pero no todas ellas son la mejor solución, y eso es lo que se busca, el óptimo. Para
esto, se debe graficar además la función objetivo y desplazarla hacia arriba o abajo
según sea el objetivo (del estudio) de maximizar o minimizar, hasta tocar en forma
tangente algún punto de la RSF.

Observación: siempre se trabaja en el primer cuadrante debido a la condición de no

negatividad ( X j 0, j 1,...,n) .

En el planteamiento del modelo de programación lineal se debe distinguir entre

recursos, actividad, nivel de actividad, medida global de efectividad.

Notación:
Z : valor de la medida global de efectividad.

10
xj : nivel de la actividad j (para j = 1, 2, …., n)
cj : incremento en Z que resulta al aumentar una unidad en el nivel de la
actividad j
bi : cantidad del recurso i disponible para asignar a las actividades (para i = 1, 2,
…, m)
aij : cantidad del recurso i consumido por cada unidad de la actividad j.

Los valores xj son las variables de decisión y los valores de c j, bi , y aij son las
constantes de entada al modelo (parámetros del modelo).

Formato Estándar del Modelo:

Consumo de recurso por unidad de actividad Cantidad
Recurso actividades de recurso
1 2 n disponible
1 a11 a12 a1n b1
2 a21 a22 a2n b2

m am1 am2 amn bm

Contribución a
Z por unidad c1 c2 cn
de actividad

Características de la Programación Lineal:

El problema debe establecerse numéricamente (cuantificación).
Deben haber varias alternativas o caminos de solución.
Se debe plantear un criterio de optimización el que debe traducirse en una
función lineal de un cierto número de variables decisionales y poder maximizar
o minimizar este criterio. Por lo general, la utilidad es el concepto más
utilizado, pero este no está relacionado linealmente con el volumen de ventas,
pero el concepto mas correcto, con respecto a las ventas, es la Contribución
Total, es decir:
Contribución Total = (Precio de Venta por unidad – Costo Variable por
unidad)*Volumen de Venta por unidad
Cuando utilicemos este concepto de utilidad en el contexto de la PL, no
referiremos a la contribución.
Dichas variables deben satisfacer un determinado número de restricciones
lineales expresadas generalmente en forma de desigualdades.
Ninguna de estas variables de decisión pueden tomar valores negativos, así
en términos de linealidad están fundamentadas en ciertos supuestos, los que
se nombran a continuación.

Supuestos de la programación lineal:

De proporcionalidad.- la contribución de cada actividad al valor de la función
objetivo Z es proporcional al nivel de actividad x j como lo representa el término

11
 cjxj en la función objetivo, como también, la contribución de cada actividad al
lado izquierdo de cada restricción funcional es proporcional al nivel de la
actividad xj en la forma en que lo representa el término a ijxj en la restricción.
Es una suposición sobre las actividades individuales que se considera
independiente de las otras. Así se presenta en situaciones tales que la división
de efectividad y el uso de recursos sea en cada caso, proporcional al nivel en
que cada actividad se ejecuta.
De aditividad.- cada función en un modelo de programación lineal (ya sea
función objetivo o en las restricciones) es la suma de las contribuciones
individuales de las actividades respectivas. Se refiere al efecto de llevar a
cabo actividades en conjunto. Así el aporte a la optimización del objetivo por
una parte, el consumo de recursos y el aporte al requerimiento en cada
actividad por la otra, debe ser medible de manera tal que resulte factible
sumar independientemente el consumo de todas las actividades consideradas.
De divisibilidad.- las variables de decisión en un modelo de programación
lineal pueden tomar cualquier valor, incluyendo valores no enteros, que
satisfagan las restricciones funcionales y de no negatividad. Como cada
variable de decisión representa el nivel de alguna actividad, se supondrá que
las actividades se pueden realizar a niveles fraccionales. (cuando los valores a
tomar por las variables de decisión no pueden ser fracciones, entonces es
parte de la programación entera). Se refiere a que las unidades de cada
actividad se pueden dividir en cualquier nivel fraccional, para que se permitan
valores no enteros de las variables de decisión.
De certidumbre.- se supone que los valores asignados a cada parámetro de
un modelo de programación lineal son constantes conocidas.

Limitaciones de la Programación Lineal:

Es frecuente que el nivel de las actividades deben ser números enteros, sin
embargo no se puede garantizar que la solución final estará compuesta por
ellos.
Los precios de cada actividad y sus consumos o aportes asociados al recurso
total disponible o requerimiento final respectivamente, toman valores
constantes para una solución determinada, es por ello, que se acostumbra a
denominar los parámetros del problema. No obstante en muchas ocasiones,
sus valores no son absolutos y solo se tienen datos aproximados, debido a
que los módulos de la programación lineal son usados para seleccionar un
curso de acción futuro, por lo tanto, estos coeficientes deben ser estimados de
acuerdo a pronósticos. El análisis de sensibilidad de la programación lineal
permite manejar este tipo de casos.
Los parámetros que entran a jugar en los problemas de programación lineal
deben ser de tipo determinístico, en consecuencia, no resulta factible
considerar casos en que ellos varían aleatoriamente.
Otra limitación es su naturaleza estática, es decir, las soluciones de
maximización de utilidades generalmente son aplicables a corto plazo, debido
a la hipótesis de la linealidad y al énfasis puesto sobre los factores de
producción considerados como fijos, ya que los precios no se mantienen

12
 invariables en el largo plazo y los coeficientes tecnológicos aumentan
proporcionalmente al requerirse la producción de una unidad más.

Por otra parte, la necesidad de trabajar con un nivel fijo de recursos significa que la
solución típica de la programación lineal está también confinado a problemas de
corto plazo.

Es recomendable hacer un análisis de sensibilidad después de encontrar el punto

óptimo para encontrar los parámetros sensibles.

Un error generalmente cometido en análisis de problemas de programación lineal es

que se trata de plantear un modelo con demasiados detalles de la realidad, lo que lo
transforma en un problema complejo y a veces con una solución muy alejada de lo
efectivo, por ello, lo que se necesita es que exista una correlación relativamente alta
entre la predicción del modelo y lo que de hecho pasaría en el problema real.

2.2.- RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN

LINEAL (PPL) MEDIANTE EL MÉTODO GRÁFICO (DOS VARIABLES
DECISIONALES)
El método de solución gráfica es aplicable sólo a problemas simples que no excedan
de dos variables. No obstante, dos variables no son suficientes para describir o
representar problemas reales, pero éste método proporciona importantes ideas de
los procedimientos de solución de P.L.

Este método gráfico se muestra de mejor manera a través de un ejemplo: una

pequeña empresa de muebles fabrica dos productos: mesas y silla, que se deben
procesar a través de los departamentos de ensamble y acabado. Ensamble tiene 60
horas disponibles y acabado puede manejar a lo máximo 48 horas de trabajo. La
fabricación de una mesa requiere de 4 horas de ensamble y dos horas de acabado.
Cada silla requiere de dos horas de ensamble y cuatro horas de acabado.

Si la utilidad es de $8 u.m. por mesa y de $6 u.m. por silla. El problema es determinar

la mejor combinación posible de mesas y sillas para producir, para así vender y
obtener la máxima utilidad.

Hay dos limitaciones (restricciones) en el problema: El tiempo disponible de

ensamble y de acabado.

Resumen de Información:
Mesa (u) Silla (u) Horas Directas
Disponibles (hr)
Ensamble 4 (hr) 2 (hr) 60
Acabado 2 (hr) 4 (hr) 48
Utilidad u.m. $8 $6

13
Planteamiento del Problema

Definición de variables de Decisión: cantidad de sillas y mesas

Xm: cantidad de mesas a producir (u)
Xs cantidad de sillas a producir (u)

Restricciones:

1. Depto. Ensamble:

4X m 2X s 60

2. Depto. Acabado

2X m 4X s 48

3. No Negatividad

Xm 0
Xs 0

Función Objetivo:
Max
U 8X m 6X s

Gráfica: Se dibuja sobre el gráfico las restricciones de No Negatividad, según la

figura siguiente:
Xs

Xm

14
Cada una de las restricciones se grafican, considerando inicialmente la desigualdad
como una igualdad.

Así, se grafica la primera restricción como la ecuación:

4 X m 2 X s 60
Si : X m 0 Xs 30
Si : X s 0 Xm 15

Las dos coordenadas anteriores se señalan en la gráfica y se unen con una línea
recta, pero el signo de la desigualad incluye a todos los pares ordenados que están a
la izquierda de dicha recta. La siguiente figura representa dicha situación:

Xs
Restricción 1

Xm

Para la segunda ecuación, se efectúa el mismo desarrollo, es así:

2 X m 4 X s 48
Si : X m 0 Xs 12
Si : X s 0 Xm 24

Las dos coordenadas anteriores se señalan en la gráfica y se unen con una línea
recta, pero el signo de la desigualad incluye a todos los pares ordenados que están a
la izquierda de dicha recta. La siguiente figura representa dicha situación:

15
 Xs

Restricción 2

Xm

La intersección de las dos inecuaciones, combinada a la ecuación de no negatividad,

genera la región de soluciones factible (RSF), como se indica en la figura. La región
achurada indica que todos los puntos que están en los bordes y dentro de a región
factible, satisfacen simultáneamente todas las restricciones del PPL.

Restricción 1 Xs

Restricción 2

RSF

Xm

El problema es encontrar uno o más puntos (o soluciones) en la RSF, de manera tal

que maximice la función objetivo original. La solución óptima se debe graficar, a
través de toda la región de soluciones. Así, cada línea de isoganancias se obtiene

16
haciendo la función objetivo igual a un valor arbitrario, por ejemplo, se elegimos
igualar la utilidad a $48 (u.m.), esta se gráfica (con línea segmentada) de igual
manera que las inecuaciones anteriores. Esta línea de isoganancias representa
todas las cantidades posibles de mesas y sillas que producirán una utilidad total de
$48 (u.m.). El problema, finalmente, se resume en encontrar la línea de isoganancia
que tenga la mayor utilidad y que este sobre la región de soluciones factibles. Lo
anterior se realiza, moviendo la línea de isoganancia en forma paralela a una línea
de isoganancia arbitraria, hasta que alcance el último punto de la RSF.

De esta manera, el último punto factible es el identificado con la letra D, por lo cual,
es el punto óptimo se encuentra por la intersección de las restricciones 1 y 2, así:
4Xm 2X s 60
2Xm 4X s 48
Xs 6 (u) sillas
Xm 12 (u) mesas

El valor de la contribución máxima es:

max
U 8X m 6X s
U $132 (u.m)

Restricción 1 Xs

U=$132 (u.m.)

Restricción 2

U=$48 (u.m.)

RSF

Xm

Ejemplo 2:
Una pequeña fábrica de muebles, elabora únicamente dos productos: Escritorios y
Sillas. Este fabricante tiene cuatros secciones: sección corte, en la cual se procesan
silla y escritorios; sección armado, en la cual se ensamblan las sillas y escritorios;

17
sección tapicería, en la cual sólo se incluye el tapiz de las sillas y sección cubiertas,
en la cual se fabrican dichas cubiertas y se colocan en los escritorios. Durante el
siguiente periodo de producción, hay 27.000 minutos disponibles para cada una de
las secciones y este tiempo no se puede alterar dentro de los parámetros del
problema. En cada una de las secciones, se ha establecido que los tiempos
estándares fijos que se necesitan para procesar cada silla son los siguientes: 15; 12;
18,75 minutos, para las secciones de corte, armado y tapicería, respectivamente; en
cambio, para el proceso de cada escritorio se requiere de: 40; 50; 56,25 minutos,
para las secciones de corte, armado y cubierta, respectivamente. Las contribuciones
a la utilidad y a los costos fijos de cada silla son de $25 (u.m.) y para cada escritorio
es de $75 (u.m.).

Se acepta que los costos indirectos totales de los cuatros departamentos son de
$20.500 (u.m.) y los costos totales en mano de obra para todos los departamentos es
de $13.500 (u.m.), resultando un costo fijo total de $34.000 (u.m.). Se supone que la
materia prima es un costo variable y que no hay costos adicionales. El costo de la
materia prima por cada silla es de $5 (u.m.) y de cada escritorio es de $25 (u.m.). El
precio de venta a que se deberá ofrecer toda la producción es de $30 (u.m.) por cada
silla y $100 (u.m) por cada escritorio (sin considerar el costo indirecto). Se pide
maximizar la contribución a la utilidad.

Resumen de la información:
Sección Silla (min) Escritorio (min) Disponibilidad (min)
Corte 15 40 27.000
Armado 12 50 27.000
Tapicería 18,75 - 27.000
Cubierta - 56,25 27.000
Contribución
$ 25 $ 75
a la utilidad (u.m.)
Costo Materia
$5 $ 25
Prima (u.m)
Precio Venta (u.m) $ 30 $ 100
Costo Indirecto: $ 20.500 (u.m.)
Costo Mano de Obra: $ 13.500 (u.m.)
Costo Fijo Total: $ 34.000 (u.m.)

Planteamiento del Problema:

1.- Definición de variables de decisión:
Xs: cantidad de sillas a producir (unidad)
Xe: cantidad de mesas a producir (unidad)

2.- Expresión algebraica de las restricciones:

Corte:
15 X s 40 X e 27.000

18
Armado:
12 X s 50 X e 27.000

Tapicería:
18,75 X s 27.000

Cubierta:
56,25 X e 27.000

No Negatividad:
Xs 0
Xe 0

3.- Expresión algebraica de la función objetivo:

max
U 25 X s 75 X e

Representación Gráfica:
Xe
Restricción 5

Restricción 3

Restricción 1

675
Restricción 2

540 E
Restricción 4
480
C
400

F
Restricción 5
A B
Xs
1.200 1.440 1.800 2.250

U* = $30.000 U* = $47.500

El punto que optimiza el objetivo expresado, se localiza de acuerdo a un análisis de

pendiente (que llamaremos M) de las rectas que la originan y de la función objetivo:

Corte
15 27.000 3
Xe *Xs Contribuci ón M 0,375
40 40 8

19
Armado
12 27.000 6
Xe *Xs Contribuci ón M 0,240
50 50 25
Tapicería
18,75 27.000
Xe *Xs Contribuci ón M
0 0
Cubierta
0 27.000
Xe * Xs Contribuci ón M 0
56,25 56,25

Función Objetivo:
25 U 1
Xe *Xs Contribuci ón M 0.333
75 75 3

Podemos observar que la pendiente de la f.o. esta entre la sección corte y armado
(en valor absoluto), así:
pend _ corte 0,375 pend _ f .o. 0,333 pend _ armado 0,240

Por otra parte, como se aprecia, la f.o. crece mientras más se aleja del origen, se
puede ver que el punto D cumple con las restricciones impuestas por ele problema y
optimiza, en este caso, la contribución a la utilidad. En general, no se requiere
analizar el valor de las pendientes de todas las rectas que intervienen, sino que
mediante una inspección ocular se puede determinar cuales de todas las
restricciones se deben analizar para detectar el óptimo:

De esta manera:
U $47.500(u.m)
X s* 1.000 (u) sillas
X m* 300 (u) escritorios

En el siguiente cuadro se presenta la relación de venta, costo y utilidad (no su

contribución) en los vértices de la RSF:
A B C D E F
(0; 0) (1.440; 0) (0; 480) (1.000; 300) (250; 480) (1.440; 135)
Costo
34.000 34.000 34.000 34.000 34.000 34.000
Fijo
Materia
0 7.200 12.000 12.500 13.250 10.575
Prima
Costo
34.000 41.200 46.000 46.500 47.250 44.575
Total
Venta
0 43.200 48.000 60.000 55.500 56.700
Total
Utilidad
(34.000) 2.000 2.000 13.500 8.250 12.125
Total

20
Se puede apreciar que si utilizamos el concepto de contribución o utilidad, de igual
manera, el punto D es el de máximo beneficio.

2.2.2.- Análisis De Casos Excepcionales

2.2.2.1.- Solución No Acotada

a.- con recursos ilimitados, se obtienen ganancias ilimitadas, es decir, las variables
de decisión crecen arbitrariamente, lo cual indica que el problema esta mal planteado
matemáticamente.
Ejemplo:
Max Z 3 X 1 3 X 2
s.a :
X1 X2 1
X1 2X 2 4
X1 0; X 2 0

X2

c a

RSF
c
X1

La función objetivo crece sin encontrar ninguna restricción que la acote, esto implica
que el problema está mal planteado. Se debe replantear las restricciones.

b.- no todas las variables crecen arbitrariamente.-

Ejemplo:
Max Z 5X1 4 X 2
s.a :
X1 2
X1 X2 0
X1 0; X 2 0

21
 X2

c
a

RSF

c
X1

No es necesario que todas las variables crezcan indefinidamente para que la

solución sea no acotada, basta que una restricción esté mal formulada.

2.2.2.2.- Acotamiento
Las variables crecen arbitrariamente, donde el punto de soluciones factibles es la
línea de restricción, generando que el valor de la función objetivo sea constante.
Max Z X1 3X 2
s.a :
X1 X2 1
2 X1 6X 2 10
X1 0; X 2 0

X2

c a

RSF
c
X1

Este tipo de problema indica un error en la formulación matemática.

22
2.2.2.3.- Inconsistencia
No existe una RSF única, producto de las restricciones existentes.

Sea el siguiente problema lineal:

Max Z 4 X1 X2
s.a :
X1 X2 2
3X1 3X 2 9
X1 0; X 2 0

X2
c

RSF 2

RSF 1 c
X1

Se debe a que, principalmente, las restricciones son inconsistentes, lo cual provoca

que no exista la certeza absoluta de que los problemas de programación lineal
tengan soluciones factibles.

2.2.2.4.- No Factibilidad

Para este caso, el problema necesario para definir este tipo de problema es el
siguiente programa matemático:
Max Z X1 2 X 2
s.a :
X1 X2 2
X1 3X 2 3
X1 0; X 2 0

23
 X2

c a

RSF 2

RSF 1
c
X1

RSF 3

Las soluciones no son factibles en este caso, ya que no respetan las condiciones o
restricciones de no negatividad.

Nota: en la práctica no podemos asegurar que las restricciones sean consistentes y

la solución acotada.

2.3.- FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL

Veamos este tópico a través de un ejemplo demostrativo:

Problema 1: un inversionista con ayuda de CORFO pretende invertir en el cultivo de

palta, pomelo, naranja y mango en el valle de Azapa (Arica), persiguiendo dos
objetivos esenciales:
1.- reducir el desempleo rural
2.- aumentar las exportaciones.

Se sabe que la producción promedio de cada árbol está dado por:

Tipo de Producción Promedio anual Observación
árbol (unidades/árbol) (kg/árbol)
Palta 350 150 Una vez al año
Pomelo 230 200 Una vez al año
Mango 150 50 Una vez al año
naranja 400 150 Una vez al año

El precio promedio en el mercado mundial a precios de 2004 fue de:

Palta : 10 ($/kg)
Pomelo : 4 ($/kg)
Mango : 15 ($/kg)
Naranja : 7 ($/kg)

24
Existe una extensión de 250.000 mt 2 de tierra propicia para el cultivo de estos
productos. Supóngase que los ingenieros agrónomos han determinado que las
siguientes extensiones son necesarias para el cultivo de esos productos.
Tipo de árbol extensión mínima de cultivo por árbol
Palta 4 mt2
Pomelo 5 mt2
Mango 3 mt2
Naranja 6 mt2

Afortunadamente, no existen problemas de agua pues hay buenas napas

subterráneas (pozos), como de un canal de regadío, que aseguran la existencia de
este líquido por los próximos 20 años. El costo total por sembrar cada árbol es:
Palta : 2,0 ($)
Pomelo : 0,5 ($)
Mango : 1,0 ($)
Naranja : 1,5 ($)

Estos costos ya incluyen la compra del árbol más su cuidado y mantenimiento anual
inicial. Cada árbol empieza a ser productivo aproximadamente a los tres años de ser
plantado. Cada árbol requiere:
Palta : 36 (h-h) de cuidado al año.
Pomelo : 72 (h-h) de cuidado al año.
Mango : 50 (h-h) de cuidado al año.
Naranja : 10 (h-h) de cuidado al año.

El inversionista pretende invertir $20.000.000 pensando en exportar toda su

producción a partir del tercer año. El desempleo en el Valle de Azapa se ha calculado
en 500 personas y el inversionista y CORFO han delineado que este proyecto
cumpla al menos con contratar 200 personas en forma continua (para que CORFO
apoye el proyecto). Bajo estas circunstancias cuántos árboles de palta, pomelo,
mango y naranja deberán sembrarse con objeto de maximizar el valor de la futura
exportación anual.

Desarrollo

1.- resumen de la información entregada (a criterio de cada persona para

comprender el problema inicial)

2.- planteamiento matemático del problema:

a.- definición de las variables de decisión

sea:
Xp : número de árboles de palta a ser plantados
Xl : número de árboles de pomelo a ser plantados
Xm : número de árboles de mango a ser plantados
Xn : número de árboles de naranjo a ser plantados
Pi : precio de la fruta (i = p, l, m, n)

25
b.- planteamientos de las restricciones
1.- Tierra
4 X p 5 X l 3X m 6 X n 250.000

2.- Horas hombre

36 X p 72 X l 50 X m 10 X n 200 * 7,5 * 5 * 52

3.- Capital
2X p 0,5 X l X m 1,5 X n 20.000.000

4.- No negatividad
Xi 0 i p, l, m, n

c.- Función Objetivo

VPE = volumen de producción esperado

= cantidad promedio por cada árbol por el número de árboles plantados

Max Z = 150*10*Xp + 200*4*Xl + 50*15*Xm + 150*7*Xn

Max
Z 1.500 Xp 800 Xl 750 Xm 1.050 Xn
s.a :
4 Xp 5 Xl 3 Xm 6 Xn 250.000
36 Xp 72 Xl 50 Xm 10 Xn 390.000
2 Xp 0,5 Xl Xm 1,5 Xn 20.000.000
X i 0 i p, l , m, n y enteras

Problema 2: Una fábrica de bebidas tiene plantas ubicadas en Concepción,

Santiago, Antofagasta, Puerto Montt y Arica. La empresa “El Botellón” fabrica
botellas de vidrio desechables (subsidiaria) y tiene plantas ubicadas en San
Bernardo, Chillán e Iquique.

La demanda mensual de botellas desechables se pronostica en:

Planta de Bebidas Demanda Mensual en Botellas
Santiago 2.000.000
Concepción 500.000
Puerto Montt 100.000
Antofagasta 400.000
Arica 100.000

26
Las botellas abiertas se retornan a la fundidora de vidrio, en donde se convierten a
materia prima y de ahí se mandan a las fábricas de botellas. Así la producción
máxima mensual de botellas es:
Planta de Bebidas Capacidad Mensual en Botellas
San Bernardo 1.500.000
Chillán 1.000.000
Iquique 750.000

El costo por miles de botellas desde las plantas de botellas a las plantas de bebidas
es:
DE \ A San Bernardo Chillán Iquique
Santiago 5 20 15
Concepción 20 15 2
Puerto Montt 25 2 10
Antofagasta 75 50 40
Arica 45 80 60

Bajo estas condiciones ¿qué programa de distribución mensual de botellas se

debería establecer a fin de satisfacer la demanda mensual en las fábricas de bebidas
sin exceder la producción mensual y todo al costo mínimo?

Desarrollo

Variables de decisión.-
Xij : cantidad de botellas (en miles) producidas en la planta i (San Bernardo, Chillán e
Iquique) y enviadas a la planta embotelladora j (Santiago, Concepción, Puerto Montt,
Antofagasta y Arica) en el mes.

Función Objetivo
3 8

Min C ij * X ij Z
i 1 j 4
i = 1,2,3 planta de botellas
j = 4,5,6,7,8 planta de bebidas

Min
Z= 5X14 + 20X15 + 25X16 + 75X17 + 45X18 +
20X24 + 15X25 + 2X26 + 50X27 + 80X28 +
15X34 + 2X35 + 10X36 + 40X37 + 60X38

Restricciones:

No Negatividad
xij 0

27
De Demanda
X 14 X 24 X 34 2.000
X 15 X 25 X 35 500
X 16 X 26 X 36 100
X 17 X 27 X 37 400
X 18 X 28 X 38 100

De Oferta
X 14 X 15 X 16 X 17 X 18 1.500
X 24 X 25 X 26 X 27 X 28 1.000
X 34 X 35 X 36 X 37 X 38 750

Problema 3: Un barco dispone de tres bodegas para la carga: una proa, una popa y
una de centro. La capacidad máxima de bodega es:
Bodega Capacidad en peso (ton) Máximo en Volumen (pie3)
Proa 2.000 100.000
Centro 3.000 135.000
Popa 1.500 30.000

Las cargas que deben ser transportadas pudiendo ser la cantidad total o parcial, son
las siguientes:
Mercadería Carga disponible (ton) Volumen unitario (pie3/ton) Utilidad ($/ton)
A 6.000 60 6.000
B 4.000 50 8.000
C 2.000 25 5.000

A fin de asegurar la estabilidad del barco, el peso en cada bodega debe ser
proporcional a su capacidad en toneladas. ¿Cómo debe ser distribuida la carga a fin
de asegurar una utilidad máxima?

Desarrollo

Variables de decisión
Xip : cantidad de carga de mercadería i, a ser llevados a proa
Xic : cantidad de carga de mercadería i, a ser llevados a centro
Xipp: cantidad de carga de mercadería i, a ser llevados a popa
i = A, B, C

Restricciones:

No Negatividad
X ip , X ic , X ipp 0

28
De capacidad máxima de bodegas
X Ap X Bp X Cp 2.000
X Ac X Bc X Cc 3.000
X App X Bpp X Cpp 1.500

Del volumen máximo de bodegas

60 X Ap 25 X Bp 25 X Cp 100.000
60 X Ac 50 X Bc 25 X Cc 135.000
60 X App 50 X Bpp 25 X Cpp 30.000

De las mercaderías a las bodegas

X Ap X Ac X App 6.000
X Bp X Bc X Bpp 4.000
X Cp X Cc X Cpp 2.000

De proporcionalidad a la capacidad
( X Ap X Bp X Cp ) ( X Ac X Bc X Cc ) ( X App X Bpp X Cpp )
2.000 3.000 1.500

Función Objetivo

Max
Z = 6000(XAp + XAc + XApp) + 8000(XBp + XBc + XBpp) + 5000(XCp + XCc + XCpp)

2.4.- MÉTODO SIMPLEX DE LA PROGRAMACIÓN LINEAL

El método simplex comienza con la siguiente estructura:
Forma canónica
Opt
 
Z C X (a )
s.a :
  
A X b (b)

x 0 (c )

(a) función lineal llamada función objetivo, donde el concepto de optimización puede
ser maximizar (para nuestro caso) o minimizar
(b) restricciones de desigualdad
(c) restricciones de no negatividad

29
 
X : vector columna con n componentes, se le denomina vector de actividades (n
componentes que son las variables de decisión)
x1
x2

X

xn n 1


C : vector renglón con n componentes, se le denomina vector de precios o costos
unitarios (contribuciones unitarias)

C c1 , c2 , ... , c3 1 n


b : vector columna con m componentes, se le denomina vector disponibilidad de
recursos
b1
b2

b

bm m 1


0 : vector columna de n ceros
0
0

0

0 n 1


A : matriz de m renglones y de n columnas, se le denomina matriz de coeficientes
tecnológicos
a11 a12 a1n
a21 a22 a2 n

A

am1 am 2 amn m n

aij: coeficientes tecnológicos, elementos de la matriz A con i = 1,2,…,m ; j = 1,2,…,n;

representa la cantidad de recurso j que necesita por unidad de la actividad i.

30
Matricialmente el problema de programación lineal se puede expresar como:
Optimizar
x1
x2
Z= c1 , c2 , ... , c3 1 n *

xn n 1

s.a:
a11 a12 a1n x1 b1
a21 a22 a2 n x2 b2
* ó

am1 am 2 amn m n
xn n 1
bm m 1

x1 0
x2 0

xn n 1
0 n 1

2.4.1.- Reglas De Programación Lineal

Regla 1.-
a.- maximizar C X es equivalente a minimizar C X .
b.- minimizar C X c*x es equivalente a maximizar C X .

Regla 2.-
a.- la desigualdad A X b es equivalente a la desigualdad A X b.
b.- la desigualdad A X b es equivalente a la desigualdad A X b.

Regla 3.-
Toda igualdad de la forma A X b , se puede descomponer como la intersección de
dos desigualdades A X b y A X b.

Regla4.-
a.- Toda desigualdad de la forma A X b , se puede convertir en igualdad, mediante
la adición del vector columna Y de m componentes no negativos, llamada variable de
holgura

31
 y1 0
y2 0

Y

ym m 1
0 m 1

b.- Toda desigualdad de la forma A X b , se puede convertir en igualdad mediante

la resta del vector columna H de m componentes no negativos, llamada variable
superfluas o de exceso.
h1 0
h2 0

H

hm m 1
0 m 1

Regla 5.-
Una variable no restringida, la cual toma toda clase de valores: negativos, ceros y
positivos, se puede escribir como la diferencia de dos variables no negativas

Ejemplos de cada regla.-

R1:
max
Z 3x1 8 x2
min
Z 3x1 8 x2

R2.-
3 x1 8 x2 20

3 x1 8 x2 20

R3.-
10 x1 3x2 7

10 x1 3x2 7
10 x1 3x2 7

32
R4 (a).-
10 x1 x2 5
7 x1 2 x2 1
x1 , x2 0

10 x1 x2 y1 5
7 x1 2 x2 y2 1
x1 , x2 0
y1 , y2 0

R5.-
x1 : variable no restrigida
x1 x2 x3

x2 x3 x1 0
x2 x3 x1 0
x2 x3 x1 0

Ejemplo.-
Convertir el problema de programación lineal a la forma canónica
Min
Z 3x1 4 x2 x3 (a)
s.a :
0,5 x1 2 x2 3
(b), (c)
x2 x3 4
x1 0, x2 0, x3 no restingida (d), (e), (f)

Desarrollo

La función objetivo queda por R1:

Max U = -Z = -3x1 + 4x2 – x3

Las restricciones quedan por R2:

0.5x1 2 x2 3 de (b)
x4 x2 0 de (e)

Entonces la restricción (c) queda por R3:

x 2 x3 4 x 2 x3 4 x 4 x3 4
x2 x3 4 x2 x3 4 x4 x3 4

33
La restricción (f) queda por R5:
x 4 x5 x6 4
x3 = x5 – x6 
x 4 x5 x6 4

Reemplazando, y acomodando a la forma canónica queda:

Max U = -Z = -3x1 + 4x2 – x5 + x6
S.A.
0.5x1 2 x4 3
x 4 x5 x 6 4
x4 x5 x6 4
x1 , x 4 , x5 , x6 0

2.4.2.- Terminología Básica

a.- Región de Soluciones Factibles (RSF): es el conjunto convexo, en el cual se
encuentran todas las soluciones factibles.
b.- Solución del Problema: se llama solución a cualquier especificación de valores
para las variables de decisión (X1, X2,…, Xn) sin importar si es una solución deseable
o, incluso, admisible.
c.- Solución Factible: es aquel vector columna XT = (X1, X2 ,…, Xn) que satisface
todas las restricciones
d.- Solución Básica: es una solución que está en el vértice, la cual puede ser factible
o no.
e.- Solución Básica Factible: es una solución factible que se encuentra en un vértice.
f.- Solución Óptima: es una solución básica factible que tiene el valor más favorable
de la función objetivo.

El conjunto de todas las soluciones factibles de un problema de programación lineal

es un conjunto convexo (se exige que, tanto la función objetivo como las
restricciones sean funciones convexas). Cuando una solución óptima existe, está en
una esquina o punto extremo del conjunto convexo de soluciones factibles, los
puntos extremos del conjunto convexo de soluciones factibles son las soluciones
básicas factibles.

Por ejemplo:

A B

34
La solución básica factible (S.B.F) está en los vértices ABC.

Por lo tanto, una solución óptima a un problema de programación lineal (PPL)

estará contenida en el conjunto de soluciones básicas factibles.

Existe un número finito de S.B.F. y, por lo tanto, teóricamente es posible concebir

una solución óptima, entonces para obtener la solución de un PPL habrá que ver en
teoría qué valor tiene la función objetivo y seleccionar la mejor. Esto puede
convertirse en una tarea bastante ardua, s se tiene en cuenta que una región factible
proveniente de un PPL con n incógnitas y m restricciones puede tener un número
máximo de:
n n!
puntos extremos
m m!(n m)!

Dónde n > m, para que exista un espacio de soluciones factibles mayor que un sólo
punto, es decir, que las restricciones sean linealmente independientes (l.i.)

Por ejemplo: Si n = 50 y m = 30
50 50!
= 4.7129 * 1013 puntos extremos a analizar
30 30!(50 30)!

Las técnicas más eficientes aplicadas para resolver conjunto de ecuaciones

simultáneas son los procedimientos iterativos. El método simplex también utiliza un
método iterativo de solución, el cual consiste en examinar las soluciones básicas
factibles. En cada iteración, el método simplex pasa de una solución factible inicial a
otra solución factible y, finalmente, en un número finito de pasos (iteraciones) llega a
una solución básica factible óptima. Como la función objetivo (Z) debe ser mejorada
(o por lo menos, no empeorada) en cada paso, el número de soluciones básicas
factibles que debe ser examinado antes de encontrar una solución óptima es mucho
más reducido que el número total de soluciones básicas factibles que existe.

2.4.3.- Teoría del Problema Del Programación Lineal

Max
 
Z C X
s.a :
  
A X b

x 0

La estructura más conveniente para la manipulación algebraica y la identificación de

las soluciones factibles en un vértice es lo que se llama Forma Aumentada del
Problema, el cual consiste en que el problema original ó canónico (contiene sólo las
variables decisionales), se aumente el número de variables, específicamente, de
holgura necesarias para aplicar el método simplex.

35
Para obtener la forma aumentada del problema, se introduce el vector columna de
las variables de holgura.
Xn 1
Xn 2

Xs

Xn m

De manera que las restricciones se conviertan en

X X
A, I b ; 0
Xs Xs

Donde:

I : matriz identidad, de orden ( m m )

0 : vector nulo que ahora tiene n+m elementos

2.4.4.- Obtención de una Solución Básica Factible

El objetivo del método simplex es obtener una sucesión de SBF mejoradas hasta
alcanzar la solución óptima. Una de las características claves del método simplex
tiene que ver con la forma en que se obtiene cada nueva SBF, después de identificar
sus variables básicas y no básicas. Dadas estas variables, la solución básica que
X
resulta de la solución de las m ecuaciones: A , I b , en las que n variables
Xs
X
de entre todas las (n + m) elementos de : , se igualan a cero. Cuando se
Xs
eliminan estas n variables igualándolas a cero queda un conjunto de m ecuaciones
con m incógnitas (variables básicas).

Este sistema de ecuaciones se puede denotar por BX B b , donde:
X B1
X B2

XB

X Bm m 1


X B : vector de variables básicas el cual se obtiene de eliminar las variables no
x
básicas de
xs

36
B: es la matriz de base
B11 B12  B1m
B21 B22  B2 m
B 

Bm1 Bm 2  Bmm m m

La cual se obtiene al eliminar las columnas correspondientes a los coeficientes de las

variables no básicas de A , I .

El método Simplex introduce solo variables básicas, tales que B sea no singular, de
manera que B-1 siempre exista, es decir:
B 1BX B B 1b
IX B B 1b

La solución para las variables básicas es:

X B B 1b

Por lo tanto, para

 obtener el valor óptimo de la función objetivo debemos reemplazar
los valores de X B en la función objetivo.

Sea C B el vector cuyos elementos son los coeficientes de la función objetivo,
incluyendo los ceros para las variables de holgura, que corresponden a los
elementos de X B . El valor de la función objetivo para esta solución básica es
entonces:

Z CB X B CB B 1b

2.4.4.1.-Forma Matricial
Cuando se inicia el método simplex, la forma matricial del conjunto de ecuaciones es
el siguiente:
Z
1 -C 0 0
X
0 A I b
XS

Luego, las operaciones algebraicas realizadas por el método simplex se expresan en

forma matricial, pre-multiplicando ambos lados del conjunto original de ecuaciones
por la matriz apropiada. Esta matriz tiene el mismo número de elementos que la
matriz idéntica. En particular, después de cualquier iteración tenemos:
Z CB B 1b
XB B 1b

37
El segundo miembro de estas ecuaciones se ha convertido en:
Z 1 CB B 1 0 CB B 1 b
*
XB 0 B-1 b B 1b

Por lo tanto, las operaciones algebraicas en ambos miembros del conjunto original de
ecuaciones han sido equivalentes, se usa esta misma matriz, que pre- multiplicada el
lado derecho original para pre-multiplicar el lado izquierdo. En consecuencia:
 Z  
1 CBB-1 1 C 0
1 CB B 1 A C CB B 1
0 B-1 0 A 1
0 B-1 A B-1

La forma matricial deseada del conjunto de ecuaciones después de cualquier

iteración es:
Z
1 CB B 1 A C CB B 1 CB B 1b
x
0 B-1 A B-1 B 1b
xs

La ventaja del Tableau es que ordena y automatiza este procedimiento. Por lo tanto,
la forma de Tableau para cualquier iteración es la siguiente:
Utilidad neta Precios sombra
Variables de Variables de
decisión holgura
X1 X2  Xn Xn 1 Xn 2 Xn m Valores de
Z
variables base
Variables
1 C B B -1 A C C B B-1 CB X B
básicas
X B1 0
X B2 0
  B 1A B 1 B-1 b
X Bm 0

2.4.5.- Pasos del método simplex

Paso 1:
Dado cualquier P.L. transformece por medio de las reglas de equivalencia 1,2,3,5 al
P.L. canónico:
Max : Z CX
s.a. :
AX b
x 0

38
Paso 2:
Rescribir la F.O. de la siguiente manera:
Z CX 0

Paso 3:
Aplicar la regla de equivalencia 4, para convertir todas las desigualdades (variables
de holgura) en igualdades.

Con estos tres primeros pasos, la forma canónica queda convertida en:
Max : Z- CX 0
s.a.
AX Y b
X 0
Y 0

Donde Y: vector de variables de holgura.

El PPL de manera de un sistema de ecuaciones:

Z C1 x1 C2 x2 C n xn 0 * xn 1 0 * xn 2 0 * xn m 0
a11 x1 a12 x 2   a1n x n xn 1 b1
a 21 x1 a 22 x 2 xn 2 b2
   
a m1 x1 am2 x2 a mn x n xn m bm
x1 0 ; x2 0 x n 0 variables de decision
Xn 1 0, x n 2  X n m 0 variables de holgura

Este paso es necesario, pues la adición de las variables de holgura crea la primera
base B que resulta ser la matriz identidad. A su vez, se genera el primer punto
extremo de la región de factibilidad cuyas coordenadas están dadas por el vector b.

Paso 4:
Construir la tabla con los coeficientes del programa, como se muestra a continuación:

Forma condensada:
Z X1 X2  Xn Xn 1 Xn 2 Xn m

1 C B B -1 A C C B B-1 C B xB
x B1 0
xB 2 0
  B 1A B 1 B-1 b
x Bm 0

39
Forma extensa:
Z x1 x2  xn xn 1 xn 2  xn m

1 z1 c1 z2 c2  zn cn zn 1 cn 1 zn 2 cn 2  zn m cn m Z0

AB1 0 Y11 Y12 Y1n Y1( n 1) Y1( n 2) Y1( n m) x B1

AB 2 0 Y21 Y22 Y2 n Y2( n 1) Y2( n 2) Y2( n m) xB 2
        
ABm 0 Ym1 Ym 2 Ymn Ym ( n 1) Ym ( n 2) Ym ( n m)
x Bm

Vectores que integran la base actual Identificación del punto extremo asociado a la base actual

Cada columna de la matriz A y la inversa B se le denomina a1 , a2 ,, an m

Paso 5:
Seleccionar como vector de entrada aquel cuyo costo reducido (utilidad neta o precio
sombra) z j c j sea el más negativa, si no hay ningún candidato de entrada, es decir,
todas las z j c j 0, j A , entonces la solución X B es óptima; en caso de
empate, este se rompe arbitrariamente.

Paso 6:
Una vez seleccionada la columna a j que entrará a la nueva base, se selecciona el
vector de salida aBr de la base actual, utilizando la siguiente regla:
X Br X Bk
min / Ykj 0
Yrj k Ykj

En el caso que todas las Ykj del denominador sean negativos, se tiene una solución
no acotada.

Paso 7:
La intersección en el Tableau de la columna que entra y la fila que sale, determina el
elemento pivote Yrj , con el objetivo de convertir a la columna a j en el vector unitario,
es decir, ceros en toda la columna y un uno en la r-ava componente (el mismo pivote
Yrj ). Regrese al paso 5.
Nota: z j c j nos indica la utilidad ganada al introducir una unidad.

Ejemplo:
Max : Z 5000 X 1 3000 X 2
s.a.
3X1 5X 2 15
5X 1 2X 2 10
X1 0 ; X2 0

40
Resolución:
1º: Método Gráfico
X2

R2
R3

R1

(x1*,x2*)=(20/19;45/19)
Z*= $ 235.000/19

RSF

R3
X1

2º: Método Simplex

Paso 2 y 3
Max : Z 5000 X 1 3000 X 2 0
s.a.
3X1 5X 2 X 3 15
5X1 2 X 2 X 4 10
X1 0 ; X2 0
X3 0 ; X4 0

Paso 4: Tableau:
Tableau 0:
Z X1  X2 X3 X4
1 -5.000 -3.000 0 0 0
X3 0 3 5 1 0 15
X4 0 5 2 0 1 10 

Paso 5: El menor valor fila

Paso 6: El menor valor columna X3 =15/3=5; X4 =10/5=2
Paso 7: Pivote

Tableau 1:
Z X1 X2 X3 X4
1 0 -1.000 0 1.000 10.000
X3 0 0 19/5 1 -3/5 9
X1 0 1 2/5 0 1/5 2

41
 Tableau 2:
z x1 x2 x3 x4 Z*
1 0 0 5.000/19 16.000/19 235.000/19
x2 0 0 1 5/19 -3/19 45/19
x1 0 1 0 -2/19 5/19 20/19

La solución básica factible óptima es:

20 45
X1 (u) X2 (u)
19 19
X3 0 X4 0

235000
Z $ (um )
19

2.4.6.- Interpretación Económica

El método simplex comienza con una producción cero para ambos productos y una
solución básica factible inicial, pero que no es muy rentable, entonces se introduce el
producto 1 a la solución, debido a que tenía la contribución más grande sobre la
utilidad ($5.000 um). Así, es un método de pasos ascendentes y que se mueve en la
dirección de la utilidad neta más grande (gradiente de la función objetivo) y que
mejora en cada estado.

En este caso, se introdujo el producto 1 tanto como fue posible hasta alcanzar la
restricción nº 2, que fue la más importante y limitó la cantidad de X1 a dos unidades,
es así que al producir estas dos unidades de X1 , la utilidad se incrementó de 0 a
$10.000 u.m.

Luego se realiza un cálculo si se puede mejorar aún más la utilidad introduciendo

algo del segundo producto. Este cálculo requirió una sustitución entre el producto 1 y
el producto 2. Conforme se incrementa X 2 , se produce menos del producto 1, debido
a que las restricciones limitan las cantidades disponibles de recursos.

El efecto neto sobre la utilidad de incrementar el producto 2 y disminuir el producto 1

se representa por el cálculo de z 2 c2 , el cual indicó que la utilidad se podría mejorar
en $1.000 um por unidad de X 2 producida. En seguida, se encontró que un máximo
de 2,37 unidades de X 2 deberían ser introducidas a la solución, debido a la
combinación de las restricciones, lo cual aumentó de 0 a 2,37 unidades de X 2 y
disminuyo de 2 a 1,05 unidades de X1 . El efecto neto de estos cambios en X1 y X 2
fue una utilidad de $12.368,4. En este punto, el método simplex determinó que no
era posible mejorar más la utilidad.

42
Ejemplo:
Max : Z 8X1 6X 2 Max : Z 8X1 6X 2 0
s.a. s.a.
4X1 2X 2 60 4X1 2X 2 X3 60
2X 1 4X 2 48 2X 1 4X 2 X4 48
X1 0 ; X2 0 X1 0 ; X2 0
X3 0 ; X4 0

Tableau 0:
Z X1  X2 X3 X4
1 -8  -6 0 0 0
X3 0 4 2 1 0 60 
X4 0 2 4 0 1 48

Paso 5: El menor valor fila

Paso 6: El menor valor columna X3 =60/4=15; X4 =48/2=24
Paso 7: Pivote

Tableau 1:
Z X1 X2 X3 X4
1 0 -2  2 0 120
X1 0 1 1/2 1/4 0 15
X4 0 0 3 3 -1/2 1 18 

Tableau 2:
Z X1 X2 X3 X4 Z*
1 0 0 5/3 2/3 132
X1 0 1 0 1/3 -1/6 12
X2 0 0 1 -1/6 1/3 6

La solución es:
x1 12(u) x2 6(u) Z $132(u.m)

Ejemplo:
Min : Z 3x1 5 x2
s.a.
x1 4
x2 6
3x1 2 x2 18
x1 , x2 0

43
El PPL de manera canónico es:
Max : U Z 3x1 5 x2 Max : U 3x1 5 x2 0
s.a. s.a.
x1 4 x1 x3 4
x2 6 x2 x4 6
3x1 2 x2 18 3x1 2 x2 x5 18
x1 , x2 0 x1 , x2 , x3 , x4 , x5 0

Tableau 0:
U X1 X2 X3 X4 X5 Z0
1 -3  5 0 0 0 0
X3 0 1 0 1 0 0 4
X4 0 0 1 0 1 0 6
X5 0 -3 -2 0 0 1 -18 

En este caso, al evaluar el primer tableau, tenemos que la tercera restricción tiene
asignado un recurso negativo (-18), por ende, el valor de x5, siendo una variable de
holguras, tiene una valor negativo asignado inicialmente, violando la restricción
general de no negatividad. Debido a lo anterior, es que surgen dos métodos,
basados en el método simplex para solucionar este tipo de problemas (conocidos de
penalización sobre la función objetivo), los cuales son: Método de la Gran M y el
Método de Doble Fase.

2.5.- METODO DE LA GRAN M

Éste método consisten en modificar el problema original y transformarlo a la forma
canónica, lo cual se logra agregando un nuevo vector, conocido como variable
artificial W, a las restricciones que generan el problema de negatividad en las
variables de holgura (por lo general, ocurren las restricciones de igualdad y mayor-
igual). Estas variables penalizan a la función objetivo con un costo de MW, donde M
es un valor positivo arbitrario muy elevado. Como el método simplex siempre trata de
mejorar la función objetivo, por ello es que éste tratará de sacar a W de la base
cuanto antes posible. Cuando W sale de la base, esto se traduce en que se ha
retornado al problema original y cuya solución óptima estará garantizada por el
método simplex. Si durante la operación se llegará a una solución óptima en que W
tiene un valor positivo, entonces implica que el problema original no tiene solución (o
la solución es infactible).

Nota: hay que tener presente que cuando la función objetivo es una maximización, la
variable artificial la penalizará con un valor negativo (-MW), en cambio, para una
función objetivo de minimización, la variable artificial la penalizara con un valor
positivo (+MW).

44
Ejemplo:
max
z 4 X1 X2
s.a :
3X1 X2 3
4 X1 3X 2 6
X1 2 X 2 4
X1, X 2 0

La forma estándar del modelo simplex queda:

max
z 4X1 X2
s.a :
3X 1 X2 3
4X1 3X 2 X3 6
X1 2X 2 X4 4
X1, X 2 , X 3 , X 4 0

Pero la restricción 1 y 2 no tienen variables que desempeñen la función de variable

holgura, es decir, en la primera no existe variable y en la segunda hay una variable
superflua, por lo cual, para solucionar dicho problema, se le adicionan dos variables
artificiales w1 y w2:
3X 1 X2 W1 3
4X1 3X 2 X3 W2 6

Entonces, el PPL queda:

max
z 4X1 X2 MW1 MW2
s.a :
3X 1 X2 W1 3
4X1 3X 2 x3 W2 6
X1 2X 2 X4 4
X 1 , X 2 , X 3 , X 4 ,W1 , W2 0

Tenemos tres ecuaciones y seis incógnitas, por ello, la base inicial debe incluir 6-3=3
variables básicas con valor distinto a cero e igual número de no básicas con valor
igual a cero. Para ello, la función objetivo debe contener el mismo número de
variables que no están en la base, pero la función objetivo esta constituida por cuatro

45
variables, por lo cual, será necesario sustituir los términos de w1 y w2 para obtener la
forma canónica adecuada; lo anterior, se efectúa reemplazando dichos términos
partir de las restricciones que poseen dichas variables w1 y w2. Para nuestro caso,
corresponde a la restricción 1 y 2:
W1 3 3X 1 X2
W2 6 4X1 3X 2 X3

Por lo tanto, la función objetivo queda como:

Z 4X1 X2 M (3 3 X 1 X 2 ) M (6 4 X 1 3 X 2 X3)
Z 4X1 X2 3M 3MX 1 MX 2 6M 4MX 1 3MX 2 MX 3
Z X 1 (4 7 M ) X 2 (1 4M ) MX 3 9M

Z (4 7M ) X 1 (1 4M ) X 2 MX 3 9M

Finalmente, el PPL queda de la siguiente manera:

max
z (4 7 M ) X 1 (1 4M ) X 2 MX 3 9M
s.a :
3X 1 X2 W1 3
4X1 3X 2 X3 W2 6
X1 2X 2 X4 4
X 1 , X 2 , X 3 , X 4 , W1 , W2 0

El tableau inicial queda:

Z X1 X2 X3 W1 W2 X4
1 -(4+7M)  -(1+4M) M 0 0 0 -9M
W1 0 3 1 0 1 0 0 3
W2 0 4 3 -1 0 1 0 6
X4 0 1 2 0 0 0 1 4

Z X1 X2 X3 W1 W2 X4
1 0 (1-5M)/3  M (4+7M)/3 0 0 4-2M
X1 0 1 1/3 0 1/3 0 0 1
W2 0 0 5/3 -1 -4/3 1 0 2
X4 0 0 5/3 0 -1/3 0 1 3

Z X1 X2 X3 W1 W2 X4
1 0 0 1/5 (8+5M)/5 -(1-5M)/5 0 18/5
X1 0 1 0 1/5 3/5 -1/5 0 3/5
X2 0 0 1 -3/5 -4/5 3/5 0 6/5
X4 0 0 0 1 1 -1 1 1

46
La solución óptima es:
X1 3/ 5
XB X2 6/5 W1 0
X W
XN X4 1 W2 0
X3 0
Z $18 / 5(um)

2.6.- METODO DE DOBLE FASE

Al igual que el método de la gran M, este método cumple con los mismos objetivos
que el anterior, pero de la siguiente manera. Sea el siguiente problema original (en
este caso usaremos la minimización para la función objetivo, aunque el método es
independiente si es maximización, sólo hay que interpretar bien el sentido de las
reglas a utilizar):
min
Z C X
s.a. :
A X b
X 0

Introducimos las variables artificiales al problema original:

min
Z C X
s.a. :
A X Y W b
X 0, Y 0,W 0

FASE I:
Se resuelve el siguiente problema.
min
W Wi
i 1

s.a. :
A X Y W b
X 0, Y 0,W 0

47
La solución óptima en esta fase debe ser W = 0. Si se tiene que W > 0, el problema
no tiene solución.

Si la primera fase es efectivamente óptima, se pasa a la siguiente fase.

FASE II:
Se toma toda la tabla óptima anterior, ignorando únicamente las columnas asociadas
a los W i y el renglón de costos reducidos z j c j , sustituyendo este renglón por la
función objetivo inicial:

min
Z C X
s.a. :
B 1 AX B 1Y B 1b
X 0, X 0

Ejemplo:
min : Z 4X1 X2
s.a :
3X 1 X2 3
4X1 3X 2 6
X1 2X 2 4
X1, X 2 0
Fase I:
min
W W1 W2
s.a. :
3X 1 X2 W1 3
4X1 3X 2 X3 W2 6
X1 2X 2 X4 4
X 1 , X 2 , X 3 , X 4 ,W1 ,W2 0

Al igual que el método de la gran M, la solución debe estar constituida de tres

variables, entonces:
W W1 W 2
W (3 3 X 1 X 2 ) (6 4 X 1 3 X 2 X3)
W 7X1 4X 2 X3 9
W 7X1 4X 2 X3 9

48
El problema estándar queda:
min
W 7X1 4X 2 X 3 9
s.a. :
3X 1 X2 W1 3
4X1 3X 2 X3 W2 6
X1 2X 2 X4 4
X 1 , X 2 , X 3 , X 4 ,W1 ,W2 0

La tabla inicial queda:

W X1 X2 X3 W1 W2 X4
1 7 4 -1 0 0 0 9
W1 0 3 1 0 1 0 0 3
W2 0 4 3 -1 0 1 0 6
X4 0 1 2 0 0 0 1 4

W X1 X2 X3 W1 W2 X4
1 0 5/3  -1 -7/3 0 0 2
X1 0 1 1/3 0 1/3 0 0 1
W2 0 0 5/3 -1 -4/3 1 0 2
X4 0 0 5/3 0 -1/3 0 1 3
W X1 X2 X3 W1 W2 X4
1 0 0 0 -1 -1 0 0
X1 0 1 0 1/5 3/5 -1/5 0 3/5
X2 0 0 1 -3/5 -4/5 3/5 0 6/5
X4 0 0 0 1 1 -1 1 1

Por lo tanto, como W=0, el problema tiene solución factible y pasamos a la fase II.

FASE II:
Las variables artificiales han servido a su propósito y se deben eliminar en todos los
cálculos siguientes. Lo anterior significa que las ecuaciones de la tabla óptima de la
fase I se pueden escribir como:
1 3
X1 X3
5 5
3 6
X2 X3
5 5
X3 X4 1

Las ecuaciones anteriores son exactamente equivalentes a la forma estándar del

problema original (antes de agregar las variables artificiales). Por lo tanto, el
problema original se puede rescribir como:

49
min
z 4X1 X2
s.a. :
1 3
X1 X3
5 5
3 6
X2 X3
5 5
X3 X4 1
X1, X 2 , X 3 , X 4 0

Se puede apreciar que la fase I nos proporciona una solución básica inicial
preparada para el problema original. Es decir, queda 4(variables) - 3(restricciones) =
1 variable asignado con valor cero, es decir, X3 = 0 y la solución básica factible inicial
está constituida por X1 ,X2 y X4.

Pero, para terminar de resolver el problema, nuevamente debemos sustituir las

variables X1 y X2 en la función objetivo (tal como se efectúo en el método de la Gran
M), utilizando la primera y segunda ecuación, entonces:
Z 4X1 X2
3 1 6 3 12 4 6 3
Z 4( X3) ( X3) X3 X3
5 5 5 5 5 5 5 5
1 18
z X3
5 5

El problema estándar final:

min
1 18
Z X3
5 5
s.a. :
1 3
X1 X3
5 5
3 6
X2 X3
5 5
X3 X4 1
X1, X 2 , X 3, X 4 0

Por lo tanto, la tabla inicial de la fase II se convierte en:

Z X1 X2 X3 X4
1 0 0 1/5  0 18/5
X1 0 1 0 1/5 0 3/5
X2 0 0 1 -3/5 0 6/5
X4 0 0 0 1 1 1

50
 Z X1 X2 X3 X4
1 0 0 0 -1/5 17/5
X1 0 1 0 0 -1/5 2/5
X2 0 0 1 0 3/5 9/5
X3 0 0 0 1 1 1

La solución óptima es:

X1 2/5
XB X2 9/5
X
XN X3 1
X4 0
Z $17 / 5(um)

2.7.- CASOS ESPECIALES DE PPL MEDIANTE TABLEAU

Como hemos analizado hasta ahora, el desarrollo y resolución de PPL, mediante
tablas no es complejo pero si algo trabajoso. En este punto veremos, al igual como lo
vimos en el punto 2.2.2, dónde efectuamos un estudio desde la perspectiva del
método gráfico, ahora los casos especiales que informa la resolución de distintos
problemas a través de los tableau.

La utilidad de lo anterior, es que nos permitirá analizar distintos casos que no son
previsibles cuando se resuelve cualquier problema particular.

2.7.1.- Problema Con Soluciones Óptimas No acotado

Existen problemas de programación lineal, cuyas soluciones óptimas no son
números finitos, sino por el contrario es el infinito, lo cual quiere indicar que,
dependiendo de la función objetivo (minimización o maximización), no existe ninguna
restricción que acote su crecimiento o, que es lo mismo, crece de manera indefinida
sin violar ninguna restricción o cuando menos en una dirección determinada. Así, se
dice que el espacio de soluciones y el valor óptimo de la función objetivo es no
acotado.

Veamos el siguiente problema lineal:

Máx Z 4X1 4X 2
s.a. :
2 X1 2X 2 2
X1 2X 2 4
X1, X 2 0

51
Su representación gráfica es la siguiente:
X2

c a

RSF
c
X1

Hemos visto que a medida que crece la función objetivo paralelamente hacia la
derecha, su valor crece o incrementa, pero la RSF no es un conjunto cerrado o
acotado por el lado derecho, por lo cual, la función objetivo no tiene limite y, por
ende, su valor es infinito.

Ahora, como podemos identificar dicho estudio con el método simplex. Sea el
problema de programación lineal canónico:
Max : Z CX
s.a. :
AX b
x 0

En cualquier iteración del método simplex, el vector que entra a la base es el

asociado a la variable Xk, entonces si todas las Yik 0, i 1,, m , la solución del
problema lineal es no acotado.

Retomemos el ejemplo ya resuelto por el método gráfico:

Máx Z 4 X 1 4 X 2
s.a. :
2 X1 2X 2 2
X1 2X 2 4
X1, X 2 0

52
Aplicando las reglas ya descritas, el tablau inicial del problema es:
Z X1 X2 X3 X4
1 -4 -4  0 0 0
X3 0 -2 2 1 0 2
X4 0 -1 2 0 1 4

Z X1 X2 X3 X4
1 -8  0 2 0 4
X2 0 -1 1 1/2 0 1
X4 0 1 0 -1 1 2

Z X1 X2 X3 X4
1 0 0 -6 8 20
X2 0 0 1 -1/2 1 3
X1 0 1 0 -1 1 2

Como se puede apreciar, en esta tercera iteración X3 debe entrar a la base, pero
Y13 1 / 2 0 y Y23 1/ 2 0 .

Por lo tanto, no es posible aplicar la regla de selección que indica que variable debe
salir de la base óptima.

2.7.2.- Problema Con Soluciones Óptimas Múltiples

A diferencia del problema anterior, existen otro tipo de problemas que no tienen una
única solución óptima, sino que al contrario, tienen un infinito número de soluciones
óptimas, pero acotadas en una región determinada para las cuales la solución
respectiva generará el mismo valor en la función objetivo, por lo general, para que
esto ocurra estos son conjuntos cerrados en segmentos de rectas o en rigor
matemático se refiere a combinaciones lineales convexas, en el cual deben existir
puntos extremos que permitirán acotar el limite de los trazos existentes de la región
de soluciones factibles. Cuando hablamos de estos casos se dice que la función
objetivo es paralela a una restricción de enlace, es decir, una restricción que se
satisface en el sentido de la igualdad a través de la solución óptima.

Veamos ahora el siguiente problema lineal:

Máx Z 5 X 1 2 X 2
s.a. :
6X1 10 X 2 30
10 X 1 4X 2 20
X1, X 2 0

53
La representación gráfica es la siguiente:
X2

b
c

RSF

B c
X1

Como se aprecia, la función objetivo tiene un valor máximo (óptimo) cuando coincide
con el trazo AB de la RSF. Como se ha dicho, la solución óptima sigue estando en un
punto extremo (vértice), solo que la gran diferencia es que son dos puntos óptimos a
conocer, el punto A y B. Es necesario recordar el concepto de la combinación lineal
convexa entre dos puntos A y B, ya que cualquier punto perteneciente a la recta AB
también es óptima, es decir, como existen infinitos puntos también existen infinitos
puntos óptimos que generan el mismo valor de la función objetivo.

Matemáticamente, se tiene que si XA es el vector asociado al punto A y XB es el

vector asociado al punto B, entonces:
X X A (1 ) X B , 0 1
es también un punto óptimo.

Nuevamente debemos indicar cuales serán las condiciones que nos permitirán
identificar soluciones múltiples óptimas mediante el método simplex. Sea el problema
de programación lineal canónico:
Max : Z CX
s.a. :
AX b
x 0

54
Si existe un vector asociado a Xk que no esté en la base óptima, cuyo costo reducido
z k ck 0 , el resto de los zi ci 0 y todas Yik 0, i 1,, m , entonces el problema
de programación lineal tiene soluciones múltiples y la base es óptima.

Retomemos el ejemplo ya visto en este caso:

Máx Z 5 X 1 2 X 2
s.a. :
6 X1 10 X 2 30
10 X 1 4X 2 20
X1, X 2 0

Aplicando las reglas ya descritas, el tablau inicial del problema es:

Z X1 X2 X3 X4
1 -5  -2 0 0 0
X3 0 6 10 1 0 30
X4 0 10 4 0 1 20 

Z X1 X2 X3 X4
1 0 0 0 1/2 10
X3 0 0 38/5 1 -3/5 18 
X1 0 1 0 0 1/10 2

Como z 2 c2 0 y la variable X2 no esta en la base, ya que B=(X2,X1) y todas las

z j c j 0, i A , se tiene una solución óptima múltiple. De esta manera, un punto
extremo óptimo es el siguiente:
X1 2
X2 0
X1
X3 18
X4 0
Z $10(um)

Para determinar cual sería el otro punto extremo, se deberá introducir a la base la
variable X2, asi:
Z X1 X2 X3 X4
1 0 0 0 1/2 10
X2 0 0 1 5/38 -3/38 45/19
X1 0 1 0 -1/19 5/38 20/19

Esta tableau también es óptima y corresponde a un punto extremo X̂ , cuyos

componentes son los siguientes:

55
 X1 20 / 19
X2 45 / 19
X2
X3 0
X4 0
Z $10(um)

Como ya se explicó, existe una combinación lineal convexa entre los puntos X1 y X2
que también es óptima, es decir, se genera el mismo valor de la función objetivo. La
expresión matemática que define dicha expresión, asociada a un X * es:
2 20 / 19
0 45 / 19
X* X 1 (1 )X 2 (1 ) , 0 1
18 0
0 0
la cual genera un punto óptimo de un conjunto de puntos óptimos existentes.

2.7.3.- Problema Sin Soluciones o Infactible

Como se ha explicado anteriormente, el método de penalización o el método de
doble fase permiten identificar cuándo un problema de programación lineal no tiene
solución.

Por lo general, si las restricciones no se pueden satisfacer en forma simultánea, se

dice que el problema no tiene solución; esta situación no ocurre cuando las
restricciones son:

1. del tipo , ya que las variables de holgura siempre generarán una RSF y, por
lo tanto, existirá una solución factible óptima,
2. del tipo efectivamente generan variables artificiales W que por su
estructura no nos garantizan una solución factible al modelo inicial y aunque
se efectúen las provisiones necesarias para que exista un solución óptima, es
decir, que efectivamente W = 0, si no existe una RSF el problema no tendrá
solución.

Veamos el siguiente caso de problema lineal:

Máx
Z 2 X1 2 X 2
sa :
X1 X 2 2
X1 X2 4
X1, X 2 0

56
La representación gráfica es la siguiente:
X2
c
a b

RSF 2

RSF 1 c
X1

Como se puede observar, no existen valores de X 1 y X2 que puedan estar

simultáneamente en ambas regiones sombreadas.

Veamos ahora cómo identificamos esta condición por medio del método de
penalización de Gran M, presentando primero el PPL estándar y el tableau original:
Máx
Z 2X1 2X 2 MW 0
sa :
X1 X 2 X3 2
X1 X2 X4 W 4
X1, X 2 0

Z X1 X2 X3 X4 W
1 -2 -2 0 0 M 0
X3 0 1 1 1 0 0 2
W 0 1 1 0 -1 1 4

Z X1 X2 X3 X4 W
1 -2-M  -2-M 0 M 0 -4M
X3 0 1 1 1 0 0 2
W 0 1 1 0 -1 1 4

57
 Z X1 X2 X3 X4 W
1 0 0 2+M M 0 4-2M
X1 0 1 1 1 0 0 2
W 0 0 0 -1 -1 1 2

Como vemos, la solución óptima al problema modificado, se obtiene en el último

tableau, pero como la variable artificial no es nula, sino que W = 2, el problema
original no tiene solución factible.

2.7.4.- Problema Con Soluciones Degeneradas

Como se ha explicado otras veces, al existir un empate al momento de decidir que
vector entra a la base, este se puede romper de manera arbitraria sin tener un efecto
considerable en el número de iteraciones del método simplex. En cambio, un empate
en el vector de salida no se puede decidir de manera arbitraria porque se puede
ocasionar un ciclaje tal que nunca se obtenga la solución óptima, es así que en la
siguiente iteración una o mas variables básicas serán obligadamente iguales a cero,
basta recordar que en los ejemplo vistos de programación lineal, siempre las
variables tomaron valores estrictamente positivos. De esta manera, esta condición
revela que el modelo tiene cuando menos una restricción redundante.

Veamos el siguiente ejemplo:

Max
Z 3X1 9 X 2
sa :
X1 4X 2 8
X1 2X 2 4
X1, X 2 0

La resolución mediante el método simplex es:

Z X1 X2 X3 X4
1 -3 -9  0 0 0
X3 0 1 4 1 0 8
X4 0 1 2 0 1 4

Z X1 X2 X3 X4
1 -3/4  0 9/4 0 18
X2 0 1/4 1 ¼ 0 2
X4 0 1/2 0 -1/2 1 0

Z X1 X2 X3 X4
1 0 0 3/2 3/2 18
X2 0 0 1 ½ -1/2 2
X1 0 1 0 -1 2 0

58
Podemos ver en este caso que en la segunda iteración ya se obtuvo el valor óptimo
de la función objetivo, pero sus vectores básicos no son los últimos; en cambio, en la
última iteración los vectores básicos son los últimos, pero la solución no mejoro. En
esta caso se puede apreciar que la primera restricción es redundante (vista de
manera gráfica), por lo cual, se dice que el punto esta mas que determinado o
sobredeterminado, ya que solo son necesarias las restricciones de negatividad y la
segunda restricción. Lamentablemente, no existe ninguna técnica confiable que nos
permita identificar restricciones redundantes a partir del tableau, sólo se puede
apreciar por el método gráfico, como se ve a continuación del ejemplo anterior.
X2

( Red
unda
nte)
RSF
c
X1

Como vimos anteriormente, las iteraciones uno y dos generaron una suerte de
ciclaje, ya que a partir de un estado común (valor objetivo iguales) se obtuvieron
soluciones distintas. Pero que pasa cuando son más de dos variables, la respuesta
es más compleja ya que el ciclaje o reciclaje, efectivamente, se vuelve más notorio,
ya que a partir del tableau inicial y después de sucesivas iteraciones aplicando el
método simplex, podemos volver nuevamente al tableau inicial sin poder llegar a la
solución óptima. Las técnicas utilizadas para solucionar el ciclaje generan una
reducción drástica en los cálculos y, por ende, en los tiempos de ejecución, pero una
técnica que mejora esta causa es la Regla Lexicográficas.

59
 CAPITULO III: DUALIDAD Y ANÁLISIS DE SENSIBILIDAD

3.1.- DUALIDAD
Uno de los descubrimientos más importantes durante el desarrollo inicial de la
programación lineal fue el concepto de dualidad y sus importantes ramificaciones,
éste reveló que asociado a todo problema de programación lineal existe otro
problema lineal llamado Dual. Las relaciones entre el problema dual y el original
(llamado primal) son útiles en una gran variedad de situaciones. Por ejemplo la
solución óptima del problema dual es la que proporciona los precios sombra, otro
aspecto importante de la teoría de la dualidad es la interpretación y realización del
análisis de sensibilidad; dado que algunos o todos los valores de los parámetros que
se emplean en el modelo original son sólo estimaciones de las condiciones futuras,
es necesario investigar el efecto que tendría sobre la solución óptima en caso que
prevalecieran otras condiciones e incluso ciertos valores de estos parámetros (como
la cantidad de recursos ) pueden representar decisiones de la gerencia en cuyo caso
su elección debe ser el punto más importante de la investigación y se puede estudiar
a través del análisis de sensibilidad.

3.1.1.- Formulación del Problema Dual.

Para construir, tanto el problema primal y dual, ambos problemas se construyen con
los mismos vector ya conocidos, es decir, de costos o precios (C), vector de recursos
(b) y coeficientes tecnológicos (A). De esta manera, asociada a la estructura de un
P.P.L. primal de la siguiente forma:
Max.
 
Z C X
s.a. Problema Primal
  
A X b

X 0

Entonces, el P.P.L. dual se define como determinar las variables duales w1 , w2 ,, wm ,
por lo cual, se define la siguiente estructura:
Min
 
G bT W
s.a. Problema Dual
  
AT W CT

W 0

60
Donde:

C T : Vector columna con n componentes transpuesta del vector C, vector de
disponibilidad de recursos duales.

W : Vector columna con m componentes; vector de actividades de variables duales.

AT : Transpuesta de la matriz A, es decir, matriz de n m elementos, matriz de
coeficientes tecnológicos.
G: Función objetivo dual, escalar.

b T : Vector de precios unitarios duales transpuesta del vector b; vector reglón con m
componentes

0 : Vector columna con m ceros.
Formas de Dualidad

Habíamos visto que:

Max Z C X Min G bT W
s.a. s.a.
1.-
A X b AT W CT
X 0 W 0

Otras formas serían:

Min Z C X Max G bT W
s.a. s.a.
2.-
A X b AT W CT
X 0 W 0

Veamos, por ejemplo, como se demuestra el PPL dual a partir del PPL primal:
Max - Z C X
s.a.
A X b
X 0

Aplicando la definición de dualidad,

Min - G bT W
s.a.
AT W CT
W 0

61
Que es equivalente a:
Max G bT W
s.a.
AT W CT
W 0

Max Z C X Min G bT W
s.a. s.a.
3.- A X b AT W CT
X 0 W no restringida

Max Z C X Min G bT W
s.a. s.a.
4.-
A X b AT W CT
X 0 W 0

Resumiendo, podemos formular el problema dual de cualquier problema primal,

según la siguiente tabla:
Problema de Maximización Problema de Minimización
Si la restricción es: La variable asociada es:
0
0
= irrestricta
Si la variable es: La restricción correspondiente es:
0
0
irrestricta =

Ejemplo:
Dado el siguiente problema primal
Max Z 3 X1 8 X 2 2X3 4X 4
s.a.
X1 X2 2X3 3X 4 5
X1 X2 -1
X3 - X 4 46
X1, X 2 , X 3 , X 4 0

62
Encuentre el problema dual asociado:
3
1 1 2 3 5
8
A 1 1 0 0 b -1 CT
2
0 0 1 1 46
4
1 1 0
1 1 0
AT bT 5 1 46 C 3 8 2 4
2 0 1
3 0 1

El PPL dual de forma matricial:

W1
Min G 5 - 1 46 W2
W3
s.a.
1 1 0 3
W1
1 1 0 8
W2
2 0 1 2
W3
3 0 1 4

El PPL dual de forma extensa:

Min G 5W1 W2 46W3
s.a.
W1 W2 3
W1 W2 8
2W 1 W3 2
3W1 W3 4
W1 , W2 , W3 0

Usos del problema Dual:

a) Resolver problemas lineales que tienen más restricciones que actividades

63
Ejemplo:
Max Z 2X1 4X 2
s.a.
X1 X2 6 Min G 6W1 8W2 2W3 8W4 6W5 8W6
2 X1 X2 8 s.a.
3 X1 2 X 2 2 W1 2W2 3W3 6W4 3W5 4W6 2
6 X1 8 X 2 8 W1 W2 2W3 8W4 4W5 W6 4
3 X1 4 X 2 6 W1 ,W2 ,W3 ,W4 ,W5 ,W6 0
4 X1 X 2 8
X1, X 2 0
b) Hacer interpretaciones económicas de las soluciones óptimas de los P.L.L.

c) Generar métodos como el Dual Simplex para el análisis de sensibilidad de los

P.L.L.

d) Generar nuevos algoritmos para la solución de problemas de redes de

optimización

Un resultado interesante que permite centrar la atención, respecto a la relación entre

ambos problemas y muestra que las denominaciones primal y dual son sólo
arbitrarias, es la siguiente:

Teorema 1: Dado un problema primal (P), el dual del problema dual es el problema
primal.

Para demostrar esta condición, utilizando el problema primal (P) original, se tiene que
el problema dual (D) asociado es:
Min G bT W
s.a.
AT W CT
W 0

Transformemos este problema a maximización y multiplicando por (-1):

Max - G bT W
s.a.
AT W CT
W 0

64
Ahora, apliquemos el dual a este problema
Min - Z C X
s.a.
A X b
X 0

El cual es equivalente a:
Max Z C X
s.a.
A X b
X 0

3.1.2.- Teoremas de Dualidad

Estos teoremas se basan en la siguiente estructura:
Max Z C X Min G bT W
s.a. s.a.
A X b AT W CT
X 0 W 0

Teorema Nº2: Teorema Débil de Dualidad:

Si el problema primal es de maximización y el problema dual de minimización,
entonces X y W son soluciones factibles del problema primal y dual,
respectivamente. Entonces se cumple que:
Z CX bT W G

Dem:
T
Si X es factible para (P), entonces A X b , y premultiplicando por W 0:
T T
W AX W b.

Si W es factible para (D), entonces AT W C T , y premultiplicando por X 0:

T T
X AT X XTC

Luego:
 T 
CX W AX bTW Z G

65
El valor de la función objetivo de cualquier solución factible del problema de
maximización, es una cota inferior del valor óptimo del problema de minimización, el
cual es análogo para el caso contrario.

Quiere decir que para cualquier par de soluciones factibles X ,W del primal y dual,
la función objetivo del primal es siempre menor o igual a la función objetivo del dual.

Corolario 1: Si el problema primal no tiene solución factible (infactible) y el problema

dual tiene al menos una, entonces el dual tiene solución óptima no acotada. Por el
contrario si el problema dual no tiene solución factible (infactible) y el problema primal
tiene al menos una, entonces tiene una solución óptima no acotada.

Corolario 2: Ambos problemas dual y primal no tienen solución

Teorema Nº3: Teorema Fundamental de Dualidad

Dados un par de problemas Primal-Dual, si uno de ellos admite solución óptima,
entonces el otro también la admite y los respectivos valore son óptimos y sus
respectivas funciones objetivos óptimas son iguales, es decir, si X* es óptimo para el
problema primal y W* es óptimo para el problema dual, entonces:

Z CX * bT W * G

3.1.4.- Solución Del Problema Dual

La solución de un P.P.L. primal por el método simplex resuelve implícitamente el
problema dual.

Supongamos el siguiente problema primal (P):

Max Z CX
s.a.
P
AX b
X 0

Supongamos que la matriz A puede ser subdividida en:

A B| N
B = Matriz de vectores básicos
N = Matriz de vectores no básicos

Entonces el P.P.L. Primal anterior queda como:

Max Z C B X B C N X N
s.a.
BX B NX N b
XB 0; XN 0

66
La solución de este problema existe, pero el problema consistirá en hacer X N = 0 (ya
que es no básica) y resolver el vector XB en términos de la base B, quedando así:
X B B 1b
Z C BX B

Z C B B-1b

La función objetivo Dual está definida como:

G bT W WT b

En condiciones de optimalidad (según el teorema fundamental) se cumple que:

Zˆ Gˆ
Cˆ B Bˆ 1b Wˆ T b

De esta manera, w es el vector dual óptimo, cuyo valor es:

Wˆ T Cˆ B Bˆ 1

1
Dentro del Tableau del P.P.L. primal CB B corresponde al valor de los costos
reducidos de las variables de holgura.

Ejemplo:
Hallar el valor de las variables duales óptimas y su función objetivo del P.P.L:
Max Z 4 X1 3 X 2
s.a.
2 X 1 3 X 2 18 ( P)
4 X 1 2 X 2 10
X1, X 2 0

Formular el problema dual

Min G 18W1 10W2
s.a.
2W1 4W2 4 D
3W1 2W2 3
W1 , W2 0

67
La última tabla para el primal queda como:
Z X1 X2 X3 X4 Z0
1 2 0 0 3/2 15
X3 0 -4 0 1 -3/2 3
X2 0 2 1 0 1/2 5

La solución óptima para el primal es:

X1* 0 X*2 5 X*3 3 X*4 0

Así, la solución óptima para el problema dual es:

Wˆ T Cˆ B Bˆ 1

W1* Z3 C3 0

W2* Z4 C4 3/ 2

Luego, comprobaremos si la solución dual es factible y óptima. Comprobando en las

restricciones duales se tiene:
20 4 3/ 2 6 4
30 2 3/ 2 3 3
0 0 ; 3/2 0
Gˆ 18 0 10 3 / 2 15 Zˆ

Las soluciones óptimas de un par de problemas primal-dual satisfacen otra relación

que es muy útil en la interpretación económica de las soluciones. Esta relación se
puede formular para un par cualquiera de problemas primal-dual lineales, pero sólo
consideraremos la definición inicial de la relación de dualidad, es decir para:
Max Z CX Min G b TW
s.a. s.a.
AX b AT W CT
X 0 W 0

Teorema Nº4: Teorema de Holguras Complementarias Débil

Dado los problemas Primal y Dual estándares, una condición necesaria y suficiente
para X y W sean óptimas, respectivamente de (P) y (D) es:
T
W (b A X ) 0
T
X ( AT W C T ) 0

68
Demostración:
Sea:
v b AX 0 variables de holgura del problema primal
u AT W CT 0 variables de holgura del problema dual

Sea X W un par de soluciones del primal y dual, entonces la condición del teorema
se puede expresar como:
T
v W 0
T
u X 0

De manera tal, que:

v b AX 0
u AT W CT 0

De esta manera, como X es el primal factible, entonces multiplicando W 0 en la

restricción A X b :
T T
W AX W b

T
Dado que v W 0 , se obtiene:
T T
W AX W b

De manera analoga, se obtiene:

T
X AW CX

Y comparando ambas ecuaciones, se obtiene que:

 T 
CX W AX bTW
Z(X ) G (W )

Producto de lo anterior, se tienen los siguientes resultados:

a. W 0 implica AX b
b. A X b implica W 0
c. X 0 implica AT W CT
d. AT W CT implica X 0

Pero que pasa en el caso que W 0 AX b , o que X 0 AT W C T . El siguiente

teorema soluciona dicha situación.

69
Teorema Nº5: Teorema de Holguras Complementarias
Dado los problemas Primal y Dual estándares, tienen soluciones factibles, entonces
existen soluciones óptimas X y W , tal que:
T
(b A X ) W 0
T
( AT W C T ) X 0

Producto de lo anterior, se tienen los siguientes resultados:

a. si (b-A X ) 0 implica W 0
b. si W 0 implica b-A X 0
c. si ( AT W CT ) 0 implica X 0
d. si X 0 implica AT W CT 0

3.1.5.- Interpretación Económica De Las Variables Duales

Se ha visto que:
Wˆ T Cˆ B Bˆ 1

Como B-1 es la inversa de la base óptima del problema primal, entonces

multipliquemos por la base óptima dicha ecuación:
Wˆ T B Cˆ B Bˆ 1Bˆ

Wˆ T Bˆ Cˆ B

Como B̂ esta compuesta por m columnas a j de A, la igualdad anterior puede

expresarse en términos de los componentes a j de la base.
Wˆ T aj C j B
Bj

De esta manera:
Cˆ B Bˆ 1a CB
j j
Y
j
Cˆ BY CB z CB
j j j j

La igualdad anterior es equivalente a la definición de z j dada con anterioridad y que

era:
z j Wˆ T a j , j B

70
Si se toma el vector de recursos b y se incrementa en b , de tal forma que la base
óptima B̂ no cambie, por lo cual, la nueva solución xB seguirá siendo óptima, siempre
y cuando se cumpla que:
Xˆ B Bˆ 1 b b 0

De esta manera, producto de lo anterior, tampoco cambian los costos

reducidos z j c j , es decir:

z c Cˆ B Bˆ 1a j C j j A
j j
En cambio, la función dual ha sufrido una variación, pues ahora se tendrá:

Gˆ Wˆ T b

Gˆ ' Wˆ T b b WˆT
b W
ˆT b
Zˆ
Gˆ ' Zˆ Wˆ T b
Gˆ ' Zˆ '

Zˆ ' Zˆ Wˆ T b
Nota: b es un cambio unitario en el vector recursos, relacionado con w, que es el
precio sombra.

La igualdad anterior indica que un pequeño incremento en el vector recursos ha

cambiado el valor óptimo de la función objetivo dual, y por lo tanto, el valor óptimo de
la función objetivo primal. Este cambio es Wˆ T b.

Si el cambio en el vector recurso b es û (unitario), la función objetivo cambiará en w

unidades, es decir, que si la componente b i 1,, n de b, sufre un cambio
i
unitario, la función objetivo sufrirá un cambio wi (la i-ésima del vector dual).

Nota: es importante notar que la interpolación económica es válida únicamente para

cambios en b, ya que estos no afectan, por lo general, la estructura de la base
óptima. Este tipo de interpolación de variables duales se conoce con el nombre de
precio sombra.

Ejemplo:

Si en el problema anterior b 2 se convierte de 10 a 11 unidades (cambio unitario), el

nuevo valor de la función objetivo será:

71
Tenemos que los valores, obtenidos del primal son:
W* 0 X* 3 X* 0
1 3 1
W* 3/ 2 X* 5 Z* 15
2 2

Luego, la variación de la función objetivo es:

b 11 10 1
2
3 33
Zˆ ' Zˆ W b 15 1 16 .5
2 2 2 2

¿Qué sucede, si cambio ahora b2 de 10 a 9 unidades?

b 9 10 1
2
3 27
Zˆ ' Zˆ W b 15 ( 1) 13 .5
2 2 2 2

¿Qué sucede si se aumenta el recurso b 1 de 18 a 19 unidades?

No sucede nada, porque el precio sombra no esta ocupando todo el recurso.

Entonces, si se aumenta (o decrece) el recurso 2, se mejora (o empeora) la función

objetivo, en cambio, si se mejora el recurso 1 sólo se tendrá más holgura para dicho
recurso.

Hay que indicar que la interpretación económica es válida solamente para cambios
unitarios en el vector b, ya que estos no afectan a la base óptima.

Los cambios que no sean unitarios (en los distintos recursos), se estudiarán en el
análisis de sensibilidad y programación paramétrica, el cual se verá más adelante.

3.1.6.- Método Simplex Dual

El método simplex dual fue desarrollado para solucionar directamente el problema
dual. Se basa en el método simplex primal y opera, según el siguiente
procedimiento:

Dado el siguiente problema primal-dual:

Max Z C X Min G bT W
s.a. s.a.
A X b AT W CT
X 0 W 0

72
Paso1:
Construya el tableau cero, siguiendo las mismas reglas vistas para el método
simplex, es decir, que aparezca la matriz identidad y que los costos reducidos, en
este caso, sean mayores o iguales a cero, es decir:
z c 0 , j A
j j

Paso2:
Revisar todos los X , i 1,, m :
Bi
1. Si todos los X 0 , entonces el tableau actual es óptimo y, por ende, la solución
Bi
es óptima.
2. Si uno o más X 0 , entonces se selecciona el vector br que debe abandonar la
Bi
base, utilizando la siguiente expresión:
X br Min X ;X 0
i 1,, m Bi Bi

Paso 3
El vector xk de entrada a la base, debe satisfacer la siguiente regla, la cual es:

zk ck z c
j j
Max ,Y 0
Yrk j 1,, n Y rj
rj

Paso 4
La columna xk se convierte en el vector unitario, cuyo pivote Yrk es igual a uno.
Dichos cambio se efectúan con operaciones matriciales elementales. Regrese al
paso 2 hasta que se cumplan las condiciones de optimalidad.

Ejemplo:
Resolver usando el Simplex Dual:
Min G 18W1 10W 2
s.a.
2W1 4W2 4
3W1 2W2 3
W1, W2 0

Notemos que el problema se puede resolver utilizando los métodos de la gran M o

Doble Fase, como lo explicamos anteriormente. Veamos el método simplex dual y
luego efectuemos una comparación entre ellos.

73
 Max H -G -18W - 10W
1 2
s.a.
- 2W - 4W W -4
1 2 3
- 3W - 2W W -3
1 2 4
W ,W ,W ,W 0
1 2 3 4

H W1 W2 W3 W4 H0
1 18 10  0 0 0
W3 0 -2 -4 1 0 -4 
W4 0 -3 -2 0 1 -3

H W1 W2 W3 W4 H0
1 13 0 5/2  0 -10
W2 0 1/2 1 -1/4 0 1
W4 0 -2 0 -1/2 1 -1 

H W1 W2 W3 W4 H0
1 3 0 0 5 -15
W2 0 3/2 1 0 -1/2 3/2
W3 0 4 0 1 -2 2

La solución al problema dual es:

W2 3/ 2
WB W3 2
W
WN W1 0
W4 0
G H 15

La diferencia entre el método dual simpleX y los dos de penalización, radica en que,
primero no se utilizan variables artificiales y, segundo existen menos iteraciones,
pero la desventaja es que exige la condición de factibilidad dual, es decir,
z c 0, j A
j j

3.1.7.- Transformación de Tabla Óptima Primal a una Tabla Óptima Dual

Como se ha explicado anteriormente, tanto el PPL primal como el dual están
relacionados a través de:

74
 Max Z CX Min G bT W
s.a. s.a.
AX b AT W CT
X 0 W 0

De esta manera, existe una relación directa entre el tableau óptimo primal y dual, el
cual se puede obtener con el siguiente procedimiento:

Paso 1
Las variables no básicas de la tabla óptima primal pasan a ser las variables básicas
de la tabla dual. Asigne las variables duales, respetando el orden en que aparecen
en la tabla primal, comenzando por las variables de holgura.

Paso 2
El valor de las variables básicas duales corresponde al valor de los costos reducidos
de las variables no básicas del problema primal, comenzando por las variables de
holgura.

Paso 3
Los costos reducidos de las variables duales no básicas corresponden al valor de las
variables básicas del problema primal.

Paso 4
Para obtener los Yj de las variables no básicas del problema dual, se pasa a
columna las filas (asociada a las variables básicas) los valores relacionados a las
variables no básicas del primal, comenzando por las variables de holgura y
multiplicando por (-1).

Paso 5
El valor óptimo de la función dual es el mismo que el valor óptimo del problema
primal en el tableau óptimo.

Ejemplo:
Max Z 4X 3X Min G 18W 10W
1 2 1 2
s.a. s.a.
2X 3X 18 2W 4W 4
1 2 1 2
4X 2X 10 3W 2W 3
1 2 1 2
X ,X 0 W ,W 0
1 2 1 2

75
 Tableau Primal
W3 W4 W1 W2
Z X1 X2 X3 X4 Z0
1 2 0 0 3/2 15
X3 0 -4 0 1 -3/2 3
X2 0 2 1 0 1/2 5

Tableau Dual
G W1 W2 W3 W4 G0
1 3 0 0 5 15
W2 0 3/2 1 0 -1/2 3/2
W3 0 4 0 1 -2 2

Ejemplo:
Dado el siguiente problema dual, resolver el problema primal asociado mediante el
método simplex y a partir de esta obtenga la tabla óptima del problema dual.
Min G 2W1 W2
s.a.
3W1 W2 3
(Pr oblema _ Dual )
4W1 3W2 6
W1 2W2 3
W1 , W2 0

Desarrollo:
El problema primal asociado al dual anterior es:
Max Z 3X1 6X 2 3X 3
s.a.
3X1 4X 2 X3 2 (Pr oblema _ Pr imal )
X1 3X 2 2X 3 1
X1 , X 2 , X 3 0

Aplicando la forma estándar:

Max - 3X1 - 6X 2 - 3X 3 0
s.a.
3X1 3X 2 2X 3 X4 2
X1 3X 2 2X 3 X5 1
X1 , X 2 , X 3 , X 4 , X 5 0

76
 Tableau Primal
Z X1 X2 X3 X4 X5 Z0
1 -3 -6  -3 0 0 0
X4 0 3 4 1 1 0 2
X5 0 1 3 2 0 1 1 
1 -1  0 1 0 2 2
X4 0 5/3 0 -5/3 1 -4/3 2/3 
X2 0 1/3 1 2/3 0 1/3 1/3
1 0 0 0 3/5 6/5 12/5
X1 0 1 0 -1 3/5 -4/5 2/5
X2 0 0 1 1 -1/5 3/5 1/5

Tableau Dual
G W1 W2 W3 W4 W5 G0
1 0 0 2/5 1/5 0 -12/5
W1 0 1 0 -3/5 1/5 0 3/5
W2 0 0 1 4/5 -3/5 0 6/5
W5 0 0 0 1 -1 1 0

3.2.- ANÁLISIS DE SENSIBILIDAD Y PROGRAMACIÓN

PARAMÉTRICA (ANÁLISIS POST-OPTIMAL)
Una vez resuelto el problema de programación lineal, puede ocurrir que se pueda
hacer variar los parámetros más relevantes del P.P.L., lo cual dará origen a un nuevo
problema, pero será necesario en este caso resolver el problema desde el principio.
La respuesta es no, afortunadamente, ya que existe el método de análisis de
sensibilidad, el cual comienza utilizando la solución óptima del problema original
hasta encontrar la solución óptima del problema nuevo. Los cambios que pueden
ocurrir para estos objetivos son los siguientes:

1.- Cambios en el vector b.

2.- Cambios en el vector C.
3.- Cambios en la matriz A.
4.-Cambios en el vector X.
5.-Cambio en el número de restricciones.

Los tres primeros cambios pueden ocurrir, tanto de manera continua o discreta, en
cambio, los dos últimos sólo pueden ocurrir de manera continua. El cambio discreto
significa hacer variar una o varias componentes del problema original y
reemplazarlos por nuevas cantidades. Para el cambio continuo, dónde el análisis de
sensibilidad se llama programación
  paramétrica, sufren cambios descritos por:
b b , -
 
C C , -
aj aj , - , j A

77
Donde:
  
b, C , a j : Vectores con las mismas dimensiones que los vectores b , C , A
, , : escalares que pueden tomar cualquier valor real.

3.2.1.- Análisis De Sensibilidad Para Cambios Discretos


3.2.1.1.-Cambios Del Vector b :
Supongamos que el siguiente P.P.L. original, cuya solución óptima se conoce, es:
Max Z C X
s.a.
Problema Original (PO)
A X b
X 0
  
Se produce un cambio discreto en el vector b , cuyo nuevo valor será b b , donde
b es un vector de m componentes. El nuevo problema a resolver es:
Max Z C X
s.a.
Problema Nuevo (PN)
A X b b
X 0

Como se comienza de la solución óptima del PO, sabemos que B 1 es la inversa de

la base óptima B del problema original, entonces la solución al PO es:
XB B 1b
y
Z CB X B
 
Al cambiar b a b b el vector X B cambia a uno nuevo X̂ B dado por:
Xˆ
B B 1b b .

Si Xˆ B 0 , entonces será la nueva solución óptima del problema nuevo y el valor

de la función objetivo será Z CB Xˆ B .
Si Xˆ B 0 , entonces no será factible y se utilizará el método dual simplex para
restaurar la factibilidad y, de hecho, la optimalidad del problema nuevo. El simplex
dual se debe aplicar sobre la tabla óptima del problema original cambiando: X B
por X̂ B .

78
Ejemplo:
Suponga que se quiere producir un volumen X de un producto químico A, el cual se
vende a $ 5/litro y otro volumen Y de otro producto químico B, a un precio de $3/litro.
Existen dos restricciones, siendo las más importantes: personal y costo de
producción. La primera tiene un máximo de 15 personas, mientras que la segunda
tiene un máximo de $10/hora de trabajo. Los coeficientes tecnológicos son los
siguientes:
Recurso\Producto Producto Químico A Producto Químico B
Personal 3 5
Costo de producción 5 2

Sea
X1: número de litros del producto químico A.
X2: número de litros del producto químico B.

El programa lineal y tableau inicial y óptimos son los siguientes:

Max Z 5X1 3X 2
s.a.
3X1 5X 2 15 ( PO)
5X1 2X 2 10
X1, X 2 0

Z X1 X2 X3 X4 Z0
1 -5  -3 0 0 0
X3 0 3 5 1 0 15
X4 0 5 2 0 1 10 
1 0 -1  0 1 10
X3 0 0 19/5 1 -3/5 9 
X1 0 1 2/5 0 1/5 2
1 0 0 5/19 16/19 235/19
X2 0 0 1 5/19 -3/19 45/19
X1 0 1 0 -2/19 5/19 20/19

X 45 / 19
2
X X 20 / 19
X* B 1 Z* 235/19
X X 0
N 3
X 0
4

5 / 19 3 / 19
B 1
2 / 19 5 / 19

79
a.- Supongamos que producto del mercado laboral, nuevas restricciones al empleo y
la situación macroeconómica, se debe reducir a 5 el número de empleados y la el
costo de producción a $5/hora.

El nuevo vector de disponibilidad de recursos es:

15 10 5
b b
10 5 5

El nuevo programa lineal a resolver es:

Max : Z 5X 3X
1 2
s.a.
3X 5X 5 ( PN )
1 2
5X 2X 5
1 2
X ,X 0
1 2

No es necesario resolver el problema desde el principio, sino que utilizaremos el

análisis de sensibilidad, con el cual, determinamos si el nuevo vector Xˆ B B 1 b b
es factible o no. Si no es así, habrá que restablecer la factibilidad y la optimalidad,
utilizando el simplex dual, a partir de la tabla óptima del PO. Sea:
5 / 19 3 / 19 5 10 / 19
Xˆ B B 1b b 0
2 / 19 5 / 19 5 15 / 19

Por lo tanto, el nuevo vector es:

X 10 / 19
X̂ B 2 es óptimo
X 15 / 19
1

El nuevo valor de la función objetivo es:

X2 10 / 19
Z CBX̂ B C2 C1 3 5
X1 15 / 19
Z * 105 / 19 $5.53

Hay que notar que una reducción en ambas restricciones, por si redujo la producción
de cada producto químico y, por ende, la utilidad esperada.

b.- Supongamos ahora, que el personal se reduce a 10 personas, pero se produce

un incremento en el costo máximo por hora de producción, siendo este de $20. El
nuevo escenario sería:

80
 Max : Z 5X 3X
1 2
s.a.
3X 5X 10 ( PN )
1 2
5X 2X 20
1 2
X ,X 0
1 2

Utilizando el análisis de sensibilidad, se tiene que:

5 / 19 3 / 19 10 10 / 19
Xˆ B B 1 b b 0
2 / 19 5 / 19 20 80 / 19

Por lo tanto, el nuevo vector es:

10 / 19
X̂ B no es óptimo
80 / 19

Por lo tanto, el necesario utilizar simplex dual para restaurar la factibilidad y obtener
la optimalidad. De esta manera, utilizando el tableau óptima del PO y reemplazando
los valores de la columna X B por X̂ B , se tiene:
Z X1 X2 X3 X4 Z0
1 0 0 5/19 16/19  235/19
X2 0 0 1 5/19 -3/19 -10/19 
X1 0 1 0 -2/19 5/19 80/19
1 0 16/3 80/57 0 50/3
X4 0 0 -19/3 -5/3 1 10/3
X1 0 1 -5/3 1/3 0 10/3

La nueva solución es:

X1= 10/3 litros de producto químico A por hora.
X2= 0 litros de producto químico B por hora.

El nuevo valor de la función objetivo es:

X4 10 / 3
Z CBX̂ B C4 C1 0 5
X1 10 / 3
Z * 50 / 3 $16,67

Es fácil ver que el hecho de sólo producir producto químico A, implica:

10
3 5 0 10
3
Obreros, lo cual genera que la holgura X3=0, mientras que la otra restricción:

81
 10 50
5 20 20
3 3

50 10
X 20 -
4 3 3


3.2.1.2.-Cambios En El Vector C :
Supongamos nuevamente el siguiente problema original:

Max Z CX
s.a.
   Pr oblema Origina l
A*X b

X 0

  
El cambio discreto en el vector C , será un nuevo valor C C , donde C es un
vector de n componentes. El problema nuevo a resolver es:
  
Max Z (C C)X
s.a.
   Pr oblema Nuevo
A*X b

X 0

Sea B 1 la inversa de la base óptima asociada al problema original. Entonces, al

generar el incremento de C, se tiene que los z j c j cambian a z c j c j , o sea:

z c c C B B 1a j cj cj WTaj cj cj
j j j
Donde a j es la columna de la matriz A.

Se sabe que en condiciones de optimalidad z c c 0, j A , no en B y

j j j

z c c 0, j B, entonces, si se cumplen estas dos condiciones, el

j j j
vector X B asociado a la tabla óptima del problema original permanece óptimo y al
nuevo valor de la función objetivo será:
Ẑ C C X
B B B

En caso contrario, es decir, z c c 0, se deberá hacer primero

j j j

z c c 0, j B , mediante operaciones matriciales elementales y después

j j j

82
obtener las condiciones de optimalidad, z j c
j
0, j A mediante el método
simplex primal.

Ejemplo:
a.- Sigamos con el ejemplo del caso anterior:
Max Z 5X 3X
1 2
s.a.
3X 5X 15 Pr oblema Original
1 2
5X 2X 10
1 2
X ,X 0
1 2

Supongamos que el precio unitario del producto químico B, se reduce a $3 a $1 por

lo tanto, el problema original queda:
Max Z 5X X
1 2
s.a.
3X 5X 15 ( PN )
1 2
5X 2X 10
1 2
X ,X 0
1 2

Por lo tanto C C 5 3 0 0 0 2 0 0 5 1 0 0

Como la única componente de C que cambio es c 2, entonces indica que sólo cambia
el costo reducido z2 c2 es:
5 16 5
z2 c2 c2 W T a2 c2 c2 1 3 1 2 0,
19 19 2

Pero sabemos que en condiciones de optimalidad z c c 0 , ya que j=2 está

2 2 2
en la base original óptima del problema original, por lo tanto, hay que reemplazar el
valor del costo reducido asociado a dicha variable y mediante operaciones
matriciales elementales se debe restablecer la factibilidad, a partir de la siguiente
tabla óptima del problema original:
Z X1 X2 X3 X4 Z0
1 0 2 5/19 16/19 235/19
X2 0 0 1 5/19 -3/19 45/19
X1 0 1 0 -2/19 5/19 20/19

83
Al restablecer la factibilidad, la tabla queda de la siguiente forma:
Z X1 X2 X3 X4 Z0
1 0 0 -5/19  22/19 145/19
X2 0 0 1 5/19 -3/19 45/19 
X1 0 1 0 -2/19 5/19 20/19

La cual no es óptima, ya que z3 c3 0 . Utilizando el método simplex primal, se

obtiene la nueva solución:
Z X1 X2 X3 X4 Z0
1 0 1 0 1 10
X3 0 0 19/5 1 -3/5 9
X1 0 1 2/5 0 1/5 2

La solución óptima para este nuevo problema es:

X 9
3
X X 2
X* B 1
X X 0
N 2
X 0
4
Z* 10

Se concluye que se deja de producir del bien 2, ya que sus costos son mayores que
sus ganancias, por lo cual, sólo se produce del bien 1, el cual está limitado por la
restricción 1 (cuello de botella).

b.- Sigamos con el ejemplo del caso anterior, pero ahora supongamos que el precio
unitario del producto químico A y B, se reducen de $5 a $1 y $3 a $1,
respectivamente, entonces el problema nuevo queda:
Max Z X X
1 2
s.a.
3X 5X 15 ( PN )
1 2
5X 2X 10
1 2
X ,X 0
1 2

Por lo tanto C C 5 3 0 0 4 2 0 0 1 1 0 0

Las componentes de C que cambian son c 1 y c2, generando que cambien los costos
reducidos z1 c1 z 2 c2 , entonces:

84
 5 16 3
z1 c1 c1 W T a1 c1 c1 1 5 1 4 0
19 19 5
5 16 5
z2 c2 c2 W T a2 c2 c2 1 3 1 2 0,
19 19 2

Como sabemos que el vector X1 y X2 están en la base óptima, entonces se deben

cumplir las condiciones de optimalidad z c c 0 z c c 0 , ya que
1 1 1 2 2 2
j=1,2 están en la base original óptima del problema original, por lo tanto,
reemplazando dichos valores y mediante operaciones matriciales elementales se
debe restablecer la factibilidad, quedando la siguiente tabla inicial del PO:
Z X1 X2 X3 X4 Z0
1 4 2 5/19 16/19 235/19
X2 0 0 1 5/19 -3/19 45/19
X1 0 1 0 -2/19 5/19 20/19

Al restablecer la factibilidad e indirectamente la optimalidad, la tabla nueva queda:

Z X1 X2 X3 X4 Z0
1 0 0 3/19 2/19 65/19
X2 0 0 1 5/19 -3/19 45/19
X1 0 1 0 -2/19 5/19 20/19

De esta manera, el tableau del PN es óptimo, con los siguientes resultados:

X 45 / 19
2
X X 20 / 19
X* B 1
X X 0
N 3
X 0
4
Z* 65 / 19 3,42

De esta manera, la reducción de los precios unitarios, genero que la utilidad final se
redujera de $12,37 a $3,42, ya que no variaron las producciones de los productos
químicos A y B.

c.- Supongamos ahora el siguiente problema:

Max Z 3X 5X
1 2
s.a.
X 4 Pr oblema Original
1
3X 2X 18
1 2
X ,X 0
1 2

85
El cual presenta el siguiente tableau óptimo:
Z X1 X2 X3 X4 Z0
1 9/2 0 0 5/2 45
X3 0 1 0 1 0 4
X2 0 3/2 1 0 1/2 9

Supongamos que el precio unitario de la primera actividad es $6, por lo tanto, el

problema nuevo queda:
Max Z 6X 5X
1 2
s.a.
X 4 ( PN )
1
3X 2X 18
1 2
X ,X 0
1 2

Por lo tanto, el vector queda:

C C 3 5 0 0 3 0 0 0 6 5 0 0

Como la única componente de C que cambio es c 1, entonces indica que sólo cambia
el costo reducido z c es:
1 1
5 1 15 3
z1 c1 c1 W T a1 c c 0 6 6 0,
1 1 2 3 2 2

Pero sabemos que en condiciones de optimalidad z c c 0 , ya que j=1 no está

1 1 1
en la base original óptima del problema original, por lo tanto, no es necesario
restablecer la optimalidad, quedando la siguiente tabla óptima del PN:
Z X1 X2 X3 X4 Z0
1 3/2 0 0 5/2 45
X3 0 1 0 1 0 4
X2 0 3/2 1 0 1/2 9

Por lo tanto, ya es óptimo, lo cual quiere decir que en incremento del precio unitario
de $3 a $6 sobre la primera actividad (que no es básica) no ha generado un cambio
en la solución óptima del PO, siendo la misma para el PN, es decir:
X 4
3
X X 9
X* B 2
X X 0
N 1
X 0
4
Z* 45

86
Lo anterior se explica de manera sencilla, como X 1 no es básica, su nivel de
utilización es de cero, pero el incremento de su precio unitario no es lo
suficientemente atractivo para que su utilización se incremente del valor cero.

d.- Utilizando el problema anterior, ahora supongamos que el precio unitario de la

primera actividad es $10, por lo tanto, el problema original queda:
Max Z 10 X 5X
1 2
s.a.
X 4 ( PN )
1
3X 2X 18
1 2
X ,X 0
1 2

Por lo tanto, el vector queda:

C C 3 5 0 0 7 0 0 0 10 5 0 0

Como la única componente de C que cambio es c 1, entonces indica que sólo cambia
el costo reducido z c es:
1 1
5 1 15 5
z1 c1 c1 W T a1 c1 c1 0 10 10 0,
2 3 2 2

En este caso, la condición indica que si z c c 0 no es óptimo y como j=1 no

1 1 1
está en la base óptima original, por lo tanto, hay que aplicar el método simplex para
obtener la optimalidad del PN. Así:
Z X1 X2 X3 X4 Z0
1 -5/2  0 0 5/2 45
X3 0 1 0 1 0 4 
X2 0 3/2 1 0 1/2 9
Z X1 X2 X3 X4 Z0
1 0 0 5/2 5/2 55
X1 0 0 0 1 0 4
X2 0 0 1 -3/2 1/9 3

Por lo tanto, es óptimo, lo cual quiere decir que en incremento del precio unitario de
$3 a $10 sobre la primera actividad (que no es básica) ha generado un cambio en la
solución óptima, la cual es:
X 4
1
X X 3
X* B 2
X X 0
N 3
X 0
4
Z* 45

87
Lo anterior significa que como X 1 no es básica, su nivel de utilización es de cero,
pero el incremento de su precio unitario es lo suficientemente atractivo para que su
nivel de utilización se incremente de su valor cero a 4 unidades, pero a su vez se
reduce el nivel de utilización del producto dos de 9 a 3 unidades, lo bueno es que
dicho cambio incrementa la utilidad de $45 a $55.

3.2.1.3.- Cambio En El Coeficiente Tecnológico a j Cuando J No Es Básico:

En el caso que se trate de una variable básica, se recomienda que se resuelva el
nuevo problema desde el principio, aunque existen métodos de análisis de
sensibilidad para este caso, estos son demasiados complejos.

Si ocurre un cambio discreto en uno o varios coeficientes tecnológicos, asociado a

las variables no básicas, se tiene que si un cambio en los componentes del vector
aj, j N (no básico), ocasiona un cambio en el término z j c , j
j
N , puesto
que:
z c C B 1a c
j j B j j

Si el vector a j se cambia a una nueva â j , el nuevo término será:

zˆ cˆ W T aˆ j cj
j j

Mientras este término sea zˆ j cˆ j 0, j N , la solución óptima asociada en el

problema original sigue siendo óptima

En caso contrario, es decir, zˆ j cˆ j 0, j N , hay que aplicar el método simplex

para obtener una nueva solución óptima del problema nuevo, teniendo cuidado de
que el vector Yj del tableau óptimo del problema original sea actualizado por otro
Yˆ j B 1aˆ j

Ejemplo:
a.- Volvamos a utilizar el siguiente problema original:
Max Z 3X 5X
1 2
s.a.
X 4 Pr oblema Original
1
3X 2X 18
1 2
X ,X 0
1 2

88
El cual presenta el siguiente tableau óptimo:
Z X1 X2 X3 X4 Z0
1 9/2 0 0 5/2 45
X3 0 1 0 1 0 4
X2 0 3/2 1 0 1/2 9

Supongamos que ocurre un cambio tecnológico en la primera actividad, donde se

cambia de 1 a 2, con respecto a la primera restricción y se cambia de 3 a 2, con
respecto a la segunda, por lo tanto, el problema nuevo queda:
Max Z 3X 5X
1 2
s.a.
2X 4 ( PN )
1
2X 2X 18
1 2
X ,X 0
1 2
donde:
1 2
a aˆ
1 3 1 2

Como sólo se cambio el vector a 1, entonces sólo cambia el costo reducido z c de

1 1
la siguiente manera:
5 2
zˆ cˆ W T aˆ1 c 0 3 5 3 2 0,
1 1 1 2 2

Como zˆ cˆ1 0 , y j=1 no está en la base original óptima del problema original, por lo
1
tanto, reemplazando este valor en el tableau del PO, el problema queda:
Z X1 X2 X3 X4 Z0
1 2 0 0 5/2 45
X3 0 1 0 1 0 4
X2 0 3/2 1 0 1/2 9

El tableau es óptimo y la solución del PO sigue siendo óptima para el PN, así:
X 4
3
X X 9
X B 2
X X 0
N 1
X 0
4
Z 45

89
b.- Supongamos nuevamente que ocurre un cambio tecnológico en la primera
actividad, donde se cambia de 1 a 10, con respecto a la primera restricción y se
cambia de 3 a 1, con respecto a la segunda, por lo tanto, el problema nuevo queda:

Max Z 3X 5X
1 2
s.a.
10X 4 ( PN )
1
1X 2X 18
1 2
X ,X 0
1 2
donde:
1 10
a aˆ
1 3 1 1

Como sólo se cambió el vector a1, entonces se modifica el costo reducido z c de la

1 1
siguiente manera:
5 10 5 1
zˆ cˆ W T aˆ1 c 0 3 3 0,
1 1 1 2 1 2 2

Como zˆ cˆ1 0 , y j=1 no está en la base óptima original del problema original, por lo
1
tanto, hay que aplicar el método simplex, pero actualizando el vector Y1 del tableau
original por otro nuevo Yˆ1 , dado por:
1 0 10 10
Yˆ j B 1aˆ j
0 1/ 2 1 1/ 2

El tableau del PN, luego de actualizar el término z c y la columna Y1 es:

1 1
Z X1 X2 X3 X4 Z0
1 -1/2  0 0 5/2 45
X3 0 10 0 1 0 4 
X2 0 1/2 1 0 1/2 9

Como no es óptimo, por lo cual, hay que aplicar el método simplex para regresar a la
optimalidad, quedando el siguiente tableau final del PN:
Z X1 X2 X3 X4 Z0
1 0 0 1/20 5/2 181/5
X1 0 1 0 1/10 0 2/5
X2 0 0 1 -1/20 1/2 44/5

90
La nueva solución óptima del PN es:
X 2/5
1
X X 44 / 5
X B 2
X X 0
N 3
X 0
4
Z 181 / 5 36 ,2

Xj
3.2.1.4.- Adiciones De Nuevas Actividades :
La adición de nuevas variables X j crea un nuevo término de costos reducidos
z c y una nueva columna Yj en la tableau. Si asociado a la nueva actividad X j se
j j
conoce su precio unitario c j y su vector de coeficientes tecnológicos a j , los nuevos
elementos se calculan como:
zj cj WTa j Cj

Yj B 1a j

Si el nuevo Z j C j 0, la nueva variable Xj no debe entrar a la base y su valor de

utilización es cero.

Si Z j C j 0 , se introduce el vector Yj en la tabla y se aplica el método simplex hasta

obtener la optimalidad.

Ejemplo:
a.- Volvamos a utilizar el siguiente problema original:
Max Z 3X 5X
1 2
s.a.
X 4 Pr oblema Original
1
3X 2X 18
1 2
X ,X 0
1 2

El cual presenta el siguiente tableau óptimo:

Z X1 X2 X3 X4 Z0
1 9/2 0 0 5/2 45
X3 0 1 0 1 0 4
X2 0 3/2 1 0 1/2 9

91
Supongamos que ahora se crea un nuevo producto X 5, entonces la pregunta es si
conviene producir dicha actividad, cuyo precio unitario es de $7 y su vector de
coeficientes tecnológicos asociado a la primera y segunda restricción es de 1 y 2,
respectivamente, por lo tanto, el problema nuevo queda:
Max Z 3X 5X 7X
1 2 5
s.a.
2X X 4 ( PN )
1 5
2X 2X 2X 18
1 2 5
X ,X , X 0
1 2 5
donde :
1
a
5 2

El nuevo elemento genera un nuevo costo reducido z c de la siguiente manera:

5 5
5 1
z c W T a5 c 0 7 5 7 2 0,
5 5 5 2 2

Como z c 0 , hay que calcular la columna Y5 del nuevo tableau dado por:
5 5
1 0 1 1
Y5 B 1a5
0 1/ 2 2 1

El nuevo tableau queda de la siguiente manera, luego de ingresar los costos

reducidos y el vector columna asociado, y sobre el cual hay que aplicar el método
simplex primal:
Z X1 X2 X5 X3 X4 Z0
1 9/2 0 -2  0 5/2 45
X3 0 1 0 1 1 0 4 
X2 0 3/2 1 1 0 1/2 9

El tableau final del PN, luego de restablecer la optimalidad de este problema, queda
finalmente::
Z X1 X2 X5 X3 X4 Z0
1 13/2 0 0 2 5/2 53
X5 0 1 0 1 1 0 4
X2 0 1/2 1 0 -1 1/2 5

Es óptimo este tableau, lo cual indica que la solución óptima del PO cambia,
generando que el PN tenga la siguiente solución óptima:

92
 X 4
5
X 5
X 2
X B X 0
X 1
N X 0
3
X 0
4
Z 53

La nueva solución indica que la actividad X 5 se debe producir a un nivel de 4

unidades, la actividad X2 se debe reducir de 9 a 5 unidades y dejar de producir la
actividad X1, lo cual genera un incremento en la utilidad de $45 a $53.

b.- Utilizando el mismo problema anterior, supongamos que ahora el nuevo producto
X5 tiene un precio unitario de $4 y su vector de coeficientes tecnológicos asociado a
la primera y segunda restricción es de 10 y 4, respectivamente. Por lo tanto, el
problema nuevo queda:
Max Z 3X 5X 4X
1 2 5
s.a.
2X 10 X 4 ( PN )
1 5
2X 2X 4X 18
1 2 5
X ,X , X 0
1 2 5
donde:
10
a
5 4

El nuevo costo reducido z c es el siguiente:

5 5
5 10
z c W T a5 c 0 4 10 4 6 0 ,
5 5 5 2 4

Como z5 c5 0 , el tableau óptimo del problema original es óptimo del problema

nuevo y X5 debe ser igual a cero. Para objetivos prácticos, se puede calcular la
columna Y5 del nuevo tableau dado por:
1 0 10 10
Yj B 1a j
0 1/ 2 4 2

De esta manera, el nuevo tableau óptimo queda:

Z X1 X2 X5 X3 X4 Z0
1 2 0 6 0 5/2 45
X3 0 1 0 10 1 0 4
X2 0 3/2 1 2 0 ½ 9

93
Esto quiere decir, que bajo las condiciones actuales, no se debe producir X 5 y la
solución óptima del PN es la misma del PO, es decir:
X 4
3
X 9
X 2
X B X 0
X 1
N X 0
5
X 0
4
Z 45

Como punto aparte, conviene explicar claramente el significado de z j c j , que tiene

dos interpretaciones:
1. z j c j es la reducción (aumento) del valor de la función objetivo en el caso de
maximización (minimización), al aumentar en una unidad el valor de la actividad
X j , j N (no básica), o bien
2. z j c j es el valor de cj debe aumentar (disminuir), en el caso de maximización
(minimización), para que X j , j N se convierta de una actividad no básica a
básica.

En este caso, se debe evaluar los cambios de los siguientes términos:

Zˆ Z (z j cj)
cˆ j cj (z j cj)

3.2.1.5.- Adición De Nuevas Restricciones:

Si al añadir k nuevas restricciones del tipo:
n
aij X j bi , i m 1,, m k
j 1

al problema original, la solución óptima X B asociada al problema original las

satisface, entonces XB es también óptima solución del problema nuevo.

En caso contrario, si XB viola alguna de las restricciones habrá que restablecer la

factibilidad del problema nuevo y obtener su optimalidad vía método simplex dual.

Al ser necesario la aplicación del método simplex dual, cada una de las k
restricciones se deben añadir en el tableau óptimo del problema original con sus
correspondientes variables de holgura. Todos los vectores unitarios asociado al
tableau óptimo del PO deben restablecerse por medio de operaciones elementales

94
matriciales. De esta manera, el método dual simplex se debe aplicar hasta obtener
una solución óptima.

Ejemplo:
a.- Retomemos nuevamente el siguiente problema:
Max Z 5X1 3X 2
s.a.
3X1 5X 2 15 ( PO)
5X1 2X 2 10
X1, X 2 0

Z X1 X2 X3 X4 Z0
1 0 0 5/19 16/19 235/19
X2 0 0 1 5/19 -3/19 45/19
X1 0 1 0 -2/19 5/19 20/19

La solución óptima del PO es:

X 45 / 19
2
X X 20 / 19
X B 1
X X 0
N 3
X 0
4
Z 235/19

Supongamos que la nueva restricción es:

X2 1

Reemplazando el valor de la variable X2:

45
1
19

Es obvio que la solución óptima del problema original viola la nueva restricción, ya
que no es menor o igual que uno. Entonces, el problema nuevo a resolver es:
Max Z 5X1 3X 2
s.a.
3X1 5X 2 15
( PN )
5X1 2X 2 10
X 1
2
X1 , X 2 0

95
Agregando las variables de holgura, se tiene que:
Max Z 5X1 3X 2
s.a.
3X1 5X 2 X 3 15
5X1 2X 2 X4 10
X X5 1
2
X1, X 2 , X , X , X 0
3 4 5

De esta manera, el tableau óptimo del problema original queda:

Z X1 X2 X3 X4 X5 Z0
1 0 0 5/19 16/19 0 235/19
X2 0 0 1 5/19 -3/19 0 45/19
X1 0 1 0 -2/19 5/19 0 20/19
X5 0 0 1 0 0 1 1

Como el vector columna de Y2 no es el vector unitario, por medio de operaciones

matriciales elementales se vuelve a generar la identidad (factibilidad):
Z X1 X2 X3 X4 X5 Z0
1 0 0 5/19  16/19 0 235/19
X2 0 0 1 5/19 -3/19 0 45/19
X1 0 1 0 -2/19 5/19 0 20/19
X5 0 0 0 -5/19 3/19 1 -26/19 

Aplicando el método dual simplex, se obtiene el tableau óptimo:

Z X1 X2 X3 X4 X5 Z0
1 0 0 0 1 1 11
X2 0 0 1 0 0 1 1
X1 0 1 0 0 1/5 -2/5 8/5
X3 0 0 0 1 -3/5 -19/5 26/5

La nueva solución óptima es:

X 1
2
X 8/5
X 1
X B X 26 / 5
X 3
N X 0
4
X 0
5
Z 11

b.- Supongamos que la nueva restricción es:

X 2 10

96
Reemplazando nuevamente el valor de X2:
45
10
19

Es obvio analizar que la solución óptima del problema original no viola la nueva
restricción, ya que es menor o igual que diez, por lo cual, la solución óptima del
problema original sigue siendo óptima para el problema nuevo. Para analizar este
suceso, veamos como queda el problema nuevo, aunque no es necesario efectuar
este análisis:
Max Z 5X1 3X 2
s.a.
3X1 5X 2 15
( PN )
5X1 2X 2 10
X 10
2
X1, X 2 0
Agregando las variables de holgura, se tiene que:
Max Z 5X1 3X 2
s.a.
3X1 5X 2 X3 15
5X1 2X 2 X4 10
X X 5 10
2
X1 , X 2 , X , X , X 0
3 4 5

De esta manera, el tableau óptimo del problema nuevo queda:

Z X1 X2 X3 X4 X5 Z0
1 0 0 5/19 16/19 0 235/19
X2 0 0 1 5/19 -3/19 0 45/19
X1 0 1 0 -2/19 5/19 0 20/19
X5 0 0 1 0 0 1 10

Como el vector columna de Y2 no es el vector unitario, por medio de operaciones

matriciales elementales se vuelve a generar la identidad (factibilidad):
Z X1 X2 X3 X4 X5 Z0
1 0 0 5/19 16/19 0 235/19
X2 0 0 1 5/19 -3/19 0 45/19
X1 0 1 0 -2/19 5/19 0 20/19
X5 0 0 0 -5/19 3/19 1 145/19

La nueva solución óptima es la misma que la original, a excepción de la variable de

holgura X5 que se agrega a las variables del problema, quedando finalmente:

97
 X 45 / 19
2
X 20 / 19
X 1
X B X 145 / 19
X 5
N X 0
3
X 0
4
235
Z 12,37
19

3.2.2.- Cambios Continuos Y Programación Paramétrica

Como vimos anteriormente, los cambios continuos pueden en tres elementos del
problema primal:
1. Parametrización o cambio continuo en el vector C,
2. Parametrización o cambio continuo en el vector b,
3. Parametrización o cambio continuo en un vector tecnológico no básico a j , j N .

Ya vimos cambios específicos en los parámetros del modelo, en cambio, el enfoque

paramétrico hace variar de manera continua uno o más parámetros sobre el intervalo
(o intervalos).

3.2.2.1.- Cambio Continuo En El Vector C

El problema nuevo a resolver es:
MAX
Z (C )X
sa : ( PN )
AX b
X 0

Donde:
C: vector con n componentes, que representa el precio unitario actual.
: vector con n componentes, que representa el porcentaje de aumento de precios.
C : vector paramétrico que indica los cambios continuos, con .

El estudio se restringirá al caso de en que 0 , puesto que para el caso de 0,

todos los resultados que se obtengan serán análogos.

De esta manera, cuando el vector paramétrico C varia, también lo hacen los

costos reducidos z j c j , j A . Para analizar esta variación, se establecerá que B0
es la base óptima asociada al problema original cuando 0 , es decir:

98
 MAX
Z CX
sa : ( PO)
AX B
X 0

De esta manera, el nuevo valor de los z j cj, j A , denotado por zˆ j cˆ j :

zˆ j cˆ j (C B 0 B0 ) B0 1a j (c j j ), j A
zˆ j cˆ j C B 0 B0 1a j B0 B0 1a j cj j C B 0 B0 1a j cj B0 B0 1a j j

zˆ j cˆ j zj cj ( B0
1
B0 a j j ), j A

Donde CB0 y son las componentes de C y asociada a la base óptima B0.

Ahora, debemos preguntarnos si existe algún valor crítico de , por ejemplo , tal
que para valores mayores que la base óptima B0 dejaría de ser óptima.

Sabemos que la optimalidad, para cualquier valor de se obtiene cuando

zˆ j cˆ j 0, j A y, además sabemos que z j c j 0, j , por que B0 es óptimo para
0 , por lo cual, sólo nos queda analizar el segundo término de zˆ j cˆ j , es decir:

B0 B0 1a j j

De esta manera:
1
1. Si B 0 B0 a j 0, j A , entonces la base óptima B0, asociada al tableau
j

óptimo del problema original, sigue siendo óptimo para cualquier valor de 0.
1
2. Si para algún j A existiese un valor correspondiente a B 0 B0 a j j 0,
entonces existe un valor crítico para , denotado por , el cuál se calcula de la
siguiente manera:
* ( z k ck )
1
B 0 B0 a j j

*
(z j cj)
Mín 1
/ B0 B0 1a j j 0
j N
B0 B0 a j j

*
Para el cual B0 deja de ser óptimo para valores de y la solución óptima seria:
Zˆ B 0 (C B 0 B0 ) X B0

*
Pero que pasa cuando , la respuesta indica que es necesario reoptimizar el
tableau óptimo correspondiente a 0 , generando dos casos:

99
a. Cuando dada por la ecuación anterior, tiene un valor mínimo único:
i. Si Yik 0, i 1,, m , entonces No existe un óptimo finito para valores de
* *
, es decir, en este caso el problema lineal para valores , tiene
como solución óptima el infinito.
ii. Si Yik 0, i 1,, m , el método simplex se aplica de la manera usual hasta
obtener una nueva solución óptima, con la salvedad de que todos los valores
z j c j , j A deben de actualizarse y la base asociada a esta nueva solución
óptima es B1
Se debe volver a analizar, en este sentido, si existe un valor crítico de en
este caso , de manera tal que B1 sigue siendo óptima para el rango de
* * **
. En este caso, el valor de es:

**
(z j cj)
Mín 1
/ B1 B1 1 a j j 0
j N
B1 B1 a j j

b. Cuando dada por la ecuación anterior, no tiene un valor mínimo único:

En este caso, es necesario hacer varios cambios en la base, utilizando para ello el
método simplex hasta corroborar que no existe ciclaje, en cuyo caso, según lo
explicado en el caso a, se aplica aquí, o bien demostrar que no existe una solución
*
óptima finita para valores de .

Ejemplo:
Considere el siguiente problema nuevo
max Z 3 6 X 1 2 2 X2 5 5 X3
s.a. :
X1 2X 2 X3 430
( PN )
3X1 2X 3 460
X1 4X 2 420
X 1 0, X 2 0, X 3 0

Para este caso:

C c1 c2 c3 3 2 5
1 2 3 6 2 5

Para =0, se vuelve al problema original:

max Z 3X1 2X 2 5X 3
s.a. :
X1 2X 2 X3 430
( PN )
3X1 2X3 460
X1 4X 2 420
X1 0, X 2 0, X 3 0

100
El Tableau inicial y óptimo, respectivamente, del problema original es el siguiente:
Z X1 X2 X3 X4 X5 X6 Z*
1 -3 -2 -5 0 0 0 0
X2 0 1 2 1 1 0 0 430
X3 0 3 0 2 0 1 0 460
X6 0 1 4 0 0 0 1 420

Z X1 X2 X3 X4 X5 X6 Z*
1 4 0 0 1 2 0 1350
X2 0 -1/4 1 0 1/2 -1/4 0 100
X3 0 3/2 0 1 0 1/2 0 230
X6 0 2 0 0 -2 1 1 20

Para =0, los resultados óptimos son los siguientes:

X2 100
X3 230
XB X6 20
X
XN X1 0
X4 0
X5 0
Z 1.350

Además, los elementos necesarios a reconocer son:

1/ 2 1/ 4 0
1
B0 0 1/ 2 0
2 1 1
VB0 X2 X3 X6
VN 0 X1 X4 X5

Es así, que es necesario calcular si existe un valor crítico *, de manera tal, que la
base óptima no cambie:

*
(z j cj)
Mín 1
/ B0 B0 1a j j 0
j N0
B0 B0 a j j

De esta manera, hay que analizar:

B0 B0 1a j j 0, j 1,4,5

B0 B0 1a j j 2 3 6 B0 1 Y1 Y4 Y5 1 4 5

101
Para cada caso se tiene que:
1/ 2 1/ 4 0 1 1 0
1
B0 B0 a N 0 N0 2 5 0 0 1/ 2 0 3 0 1 6 0 0
2 1 1 1 0 0
1 1 0
1
B0 B0 a N 0 N0 1 3 0 3 0 1 6 0 0 8 1 3 6 0 0
1 0 0

B0 B0 1 a N 0 N0 14 1 3

Es fácil ver ahora que:

B0 B0 1 a1 1 14 0
B0 B0 1a 4 4 1 0
B0 B0 1 a5 5 3 0

De esta manera, el único elemento que es relevante es la variación asociada a X 4,

por lo tanto, nuestro candidato genera el valor crítico de *, es cual es:
* ( z 4 c4 ) 1
1
1
B 0 B0 a 4 4 1

De esta manera, el rango de esta acotado por 0 1 , los cuales generan las
siguientes soluciones óptimas.
X2 100
X3 230
XB X6 20
X
XN X1 0
X4 0
X5 0
X2 100
Zˆ B 0 (C B 0 B0 ) X B0 c2 2 c3 3 c6 6 X3 2 2 5 5 0 230
X6 20

Zˆ B0 200 200 1.150 1.150 1.350 950

Por ejemplo, si =1/2, se tiene que

1
Zˆ B 0 1.350 950 1.825
2

102
Se puede analizar si existe algún otro rango de , el cual genera el intervalo
* * **
. Para efectuar este análisis, del tableau óptimo cuando =0, se
actualizan los costos reducidos z j c j , j N , para *=1:
*
zˆ1 cˆ1 z1 c1 ( B0 B0 1 a1 1 ) 4 1(14) 18
zˆ4 cˆ4 z4 c4 *
( B0 B0 1a4 4 ) 1 1( 1) 0
zˆ5 cˆ5 z5 c5 *
( B0 B0 1a5 5 ) 2 1(3) 5

El valor de la función objetivo en el tableau, se obtiene también cuando =1, es decir:

Zˆ B 0 1.350 950 1 2.300 .

Analizando los elementos anteriores, se puede apreciar que X4 debe entrar a la base
del problema original y aplicando el método simplex se obtiene el nuevo tableau
óptimo, según se muestra a continuación:
Z X1 X2 X3 X4 X5 X6 Z*
1 18 0 0 0 5 0 2300
X2 0 -1/4 1 0 1/2 -1/4 0 100
X3 0 3/2 0 1 0 1/2 0 230
X6 0 2 0 0 -2 1 1 20

Z X1 X2 X3 X4 X5 X6 Z*
1 18 0 0 0 5 0 2300
X4 0 -1/2 2 0 1 -1/2 0 200
X3 0 3/2 0 1 0 ½ 0 230
X6 0 1 4 0 0 0 1 420

**
Los resultados óptimos para el rango de que esta acotado por 1 1 son:.
X4 200
X3 230
XB X6 420
X
XN X1 0
X2 0
X5 0
X4 100
Zˆ B 0 (C B 0 B0 ) X B0 c4 4 c3 3 c6 6 X3 0 5 5 0 230
X6 20
Zˆ B0 1.150 1.150

103
Los elementos necesarios a reconocer en este rango son:
1 1/ 2 0
B1 1 0 1/ 2 0
0 1 1
VB1 X4 X3 X6
VN1 X1 X2 X5
**
Sólo falta calcular si efectivamente existe un valor crítico , de manera tal que acote
las soluciones y la función, a través de:
B1 1 B 1a j j 0, j 1,2,5

B1 1 B 1a j j 4 3 6 B1 1 Y1 Y2 Y5 1 2 5

Para cada caso se tiene que:

1 1/ 2 0 1 2 0
B1 B1 1 a N 1 N1 0 5 0 0 1/ 2 0 3 0 1 6 2 0
0 1 1 1 4 0
1 2 0
1 5 15 5
B1 1 B a N1 N1 0 0 3 0 1 6 2 0 0 6 2 0
2 2 2
1 4 0
27 5
B1 B1 1a N 1 N1 2
2 2

Es fácil ver ahora que:

27
B1 B1 1a1 1 0
2
1
B1 B1 a2 2 2 0
5
B1 1 B 1 a5 5 0
2

Por lo cual, ninguno cumple la condición que: B1 1B 1a j j 0, j 1,2,5 ,

indicando que **
es igual a infinito, es decir que 1 .

104
Finalmente, se puede concluir que la solución óptima es:
Para el rango entre 1 1
X2 100
X3 230
XB X6 420
X
XN X1 0
X4 0
X5 0
Zˆ B0 1.350 950

Para el rango entre 1

X4 200
X3 230
XB X6 420
X
XN X1 0
X2 0
X5 0
Zˆ B0 1.150 1.150

3.2.2.2.- Cambio Continuo En El Vector b

El problema a resolver es el siguiente:
max Z CX
s.a :
( PN )
AX b
X 0
donde:
b : vector paramétrico que indica los cambios continuos en la disponibilidad de
recursos b, con
: vector de m componentes

Este estudio estará restringido solo para 0 , puesto que para el caso de 0 ,
todos los resultados que se obtienen son análogos. Sea B0, la base óptima asociada
al problema original, es decir, cuando = 0.
max Z CX
s.a :
( PO)
AX b
X 0

105
Un cambio en el parámetro b hace variar el XB0 y el valor de la función objetivo
en el problema original. Sabemos que:
XB B 1b

Si efectivamente en b ocurre un cambio paramétrico:

Xˆ B 0 B0 1 (b )
Zˆ B 0 C B 0 Xˆ B 0

Debemos determinar si existe algún valor crítico de , tal que para valores mayores
de , la sabe B0 dejaría de ser óptima:
1. Si Xˆ B0 1 (b ) 0 , para cualquier valor de , entonces la base
B0

sigue siendo óptima.

2. Si alguna componente de Xˆ B0 B0 1 (b ) 0 , B0 deja de ser óptima y el

valor de * se determina mediante la siguiente relación:
Xˆ B 0 B0 1b B0 1 X B0 B0 1
* X B 0i
min 1
/ B0 1 i 0
i 1,, m B0 i
Donde:
X B 0i : es la i-ésima componente, i=1,…,m del vector básico XB0
i : es la i-ésima componente, i=1,…,m del vector
*
: el rango asociado sería 0 .

*
Cuando , se puede obtener una nueva solución factible, utilizando el método
simplex dual, una vez actualizado Xˆ B 0 y Z * el tableau óptimo del problema original.
Cuando se efectúa la operación respectiva, se obtiene una nueva solución óptima
Xˆ B1 , la cual esta asociada a una nueva base B 1, lo cual nos permite, nuevamente,
obtener un segundo valor crítico de , siendo éste por lo tanto, el rango asociado
* * **
sería .

Ejemplo:
Consideremos el siguiente caso de programación lineal paramétrica:
max Z 3 X1 2 X 2 5 X 3
s.a. :
X1 2X2 X3 430 100
( PN )
3 X1 2X3 460 200
X1 4X2 420 400
X 1 0, X 2 0, X 3 0

106
Dónde:
b1 430 1 100
b b2 460 , 2 200
b3 420 3 400

Si =0, se tiene el problema original:

max Z 3 X 1 2 X 2 5 X 3
s.a. :
X1 2X2 X3 430
( PO)
3 X1 2X3 460
X1 4X2 420
X 1 0, X 2 0, X 3 0

De esta manera, aplicando los conceptos ya utilizados, se forma la base inicial y

mediante el método simplex se obtiene el tableau óptimo del problema original:
Z X1 X2 X3 X4 X5 X6 Z*
1 4 0 0 1 2 0 1350
X2 0 -1/4 1 0 1/2 -1/4 0 100
X3 0 3/2 0 1 0 1/2 0 230
X6 0 2 0 0 -2 1 1 20

Los resultados óptimos para este caso son:

X2 100
X3 230
XB X6 20
X
XN X1 0
X4 0
X5 0
Z 1.350

La base óptima, las variables básicas y no básicas que constituyen el problema son:
1/ 2 1/ 4 0
B0 1 0 1/ 2 0
2 1 1
VB0 X2 X3 X6
VN 0 X1 X4 X5

De esta manera, el valor de * queda determinado por:

107
 * X B 0i
min 1
/ B0 1 i 0
i 1,, m B0 i
1/ 2 1/ 4 0 100 100
B0 1 0 1/ 2 0 200 100
2 1 1 400 0

Como B0 1 3 100 0 , efectivamente existe un valor crítico de *, siendo este:

* X B 0i 230
2,3
B0 1 i 100

Es así que para el rango de 0 2,3 , la solución óptima esta estructurada como:
X2 1/ 2 1 / 4 0 430 100
ˆ
X B0 X3 B0 1 (b ) B0 1b B0 1
0 1 / 2 0 460 100
X6 2 1 1 420 0
X2 100 100
Xˆ B 0 X3 230 100
X6 20

La función objetivo viene dada por 0 2,3 , entonces:

X2 100 100
Zˆ B 0 CB 0 Xˆ B 0 c2 c3 c6 X 3 2 5 0 230 100
X6 20
Zˆ B0 1.350 300

Que pasa para valores de 2,3 , se deberá actualizar el vector XB0 y la función
objetivo para =2,3, generando que:
X2 100 100 2,3 330
Xˆ B 0 X3 230 100 2,3 0
X6 20 20
Zˆ B0 1.350 300 2,3 660

De esta manera, al tableau actualizado se le aplica el método simplex dual, pero en

este caso, aunque ningún XBi es negativo, se debe obligar a X3=0 a salir de la base
inicial:
Z X1 X2 X3 X4 X5 X6 Z*
1 4 0 0 1 2 0 660

108
 X2 0 -1/4 1 0 1/2 -1/4 0 330
X3 0 3/2 0 1 0 1/2 0 0 
X6 0 2 0 0 -2 1 1 20
Lamentablemente, al aplicar el método simplex dual, no es posible determinar el
vector de entrada, ya que todos los Y3 j 0 , lo cual indica que el problema
paramétrico no tiene solución para cualquier valor de 2,3 .

3.2.2.3.- Cambio Continuo En Una Columna Tecnológica No Básica a j De A

El nuevo problema a resolver es:
Max
Z CX
sa : ( PN )
Aˆ X b
X 0

 difiere de la matriz A, únicamente en una columna no básica (la columna j), dónde:
aˆ j a j j, j N
Con a j A y y j vector columna de m componentes.

El análisis se restringirá sólo para el caso de 0 , ya que para 0 , todos los

resultados obtenidos serán análogos.

Hay que aclarar que, a diferencia de los dos casos anteriores, una vez obtenido el
valor crítico de (por ejemplo , el análisis no se puede volver a realizar para
*
valores de , ya que en este caso â j se convierte de un vector no básico
* *
(0 ) a un vector básico ( ). Dicho este comentario, se continuará el
estudio paramétrico de esta variable.

Sea B0 la base óptima asociada al problema original, es decir, 0:

Max
Z CX
sa ( PO)
AX b
X 0

El cambio paramétrico en el vector â j ocasiona que los costos reducidos se

modifiquen de z j cj 0, j a zˆ j cˆ j , de la siguiente manera:

109
zˆ j cˆ j C B 0 B0 1aˆ j cj, j N
zˆ j cˆ j C B 0 B0 1 (a j j ) cj C B 0 B0 1a j C B 0 B0 1 j cj

zˆ j cˆ j C B 0 B0 1a j cj C B 0 B0 1 j

zˆ j cˆ j zj cj C B 0 B0 1 j , j N

De esta manera, se tiene que:

1. Si zˆ j cˆ j 0 y para cualquier valor de 0 , entonces B0 sigue siendo óptima
para el nuevo problema.
2. Si zˆ j cˆ j 0 para algún valor de j N , entonces existe un , el cual se
determina por la siguiente relación (como se ha efectuado en los casos
anteriores):
*
zj cj
Mín 1
/ C B 0 B0 1 j 0
j 1,, m C B 0 B0 j
*
En este caso, B0 es óptima solamente para el rango de 0 y nada se puede
*
decir para valores de .

Ejemplo:
Resuelva el siguiente PPL:
max Z 3X 1 2X 2 5X 3
s.a. :
(1 )X1 2X 2 X3 430
( PN )
(3 )X1 2X 3 460
X1 4X 2 420
X1 0, X 2 0, X 3 0

Donde el vector tecnológico paramétrico â1 es:

aˆ1 a1 1

1 1
aˆ1 3 1
1 0

Para =0, el problema original es el siguiente:

110
 max Z 3X1 2 X 2 5X 3
s.a. :
X1 2X 2 X3 430
( PO)
3X1 2X 3 460
X1 4X 2 420
X1 0, X 2 0, X 3 0
El tableau asociado es:
Z X1 X2 X3 X4 X5 X6 Z*
1 4 0 0 1 2 0 1350
X2 0 -1/4 1 0 1/2 -1/4 0 100
X3 0 3/2 0 1 0 1/2 0 230
X6 0 2 0 0 -2 1 1 20

Los resultados óptimos para este caso son:

X2 100
X3 230
XB X6 20
X
XN X1 0
X4 0
X5 0
Z 1.350

Como existe un cambio paramétrico, asociado a la variable X1 en sus actividades

tecnológicas, ocasiona que los costos reducidos z1 c1 sufran cambios y, por ende,
debemos determinar si existe un valor crítico de , entonces debemos evaluar la
siguiente expresión:
zˆ1 cˆ1 z1 c1 C B 0 B0 1 1

Entonces:
z1 c1 4
1/ 2 1/ 4 0 1 1
1
C B 0 B0 1 2 5 0 0 1/ 2 0 1 1 2 0 1 1
2 1 1 0 0

De esta manera, el :
* 4
4
1

111
Los costos reducidos, asociados a X1 y 0 4 son:
zˆ1 cˆ1 4 ( 1) 4

Finalmente, se puede decir que para valores de , en el rango de 0 4 , la

solución óptima para el problema nuevo es:
X2 100
X3 230
XB X6 20
X
XN X1 0
X4 0
X5 0
Z 1.350

Por ejemplo, si =4, entonces:

zˆ1 cˆ1 0

El tableau asociado seria:

Z X1 X2 X3 X4 X5 X6 Z*
1 0 0 0 1 2 0 1350
X2 0 -1/4 1 0 1/2 -1/4 0 100
X3 0 3/2 0 1 0 1/2 0 230
X6 0 2 0 0 -2 1 1 20

¿Qué sucede con este tableau óptimo?. Lamentablemente, al tratar de ingresar X1 a

la base, se genera un problema, producto de ingresar una variable que no era básica
a ser básica.

112
 CAPITULO III: PROBLEMA DE TRANSPORTE,
TRANSBORDO Y ASIGNACIÓN

3.1.- MODELO DE TRANSPORTE

En este capítulo nos referiremos al modelo de transporte estándar, aunque existen
variantes, los cuales complejizan este problema, no es el objetivo introductoria de
este capítulo.

En estricto rigor, el modelo de transporte busca determinar el mejor plan de envíos

desde uno o más centros de oferta (producción de algún producto) hacia los centros
de consumo (demanda por dicho producto), es así, que se cuenta con la siguiente
información:
1. Nivel de oferta en cada origen y cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercadería entre las fuentes y los
destinos.
3. Un supuesto fuerte es que existe una única mercadería o producto.

Hay que tener presente que cada destino puede absorber, a través de su demanda,
la producción de los distintos orígenes, por lo cual, el objetivo principal es determinar
la cantidad óptima que se debe enviar desde cada origen a cada destino, de manera
tal que el costo total de transporte sea mínimo.

La siguiente figura representa el modelo de transporte como una red con “m” centros
de oferta, que tienen que surtir a “n” centros de consumo, dónde cada nodo
representa un origen o destino y los arcos indican una conexión entre un origen y
destino indica que se puede transportar un producto.
“m” Centros de “n” Centros de
Oferta Demanda
(Origen) (Destino)
C11, X11
1 1

2 2
C22, X22

Ci1, Xi1

Ci2, Xi2
i j
Cij, Xij
Cin, Xin

Cmj, Xmj
m n
Cmn, Xmn

113
Donde:

ai : Capacidad de oferta del origen i

bJ : Demanda del centro de consumo i
CiJ : Costo de enviar una unidad de producto del origen i al destino j
XiJ : Cantidad de productos a enviar desde el origen i al centro de consumo j

3.1.1.- Estructura de Transporte

E problema se reduce a determinar cuantas unidades de producto deben enviarse
desde el origen i al centro de consumo j, tal que se minimicen los costos de
transporte, se satisfaga la demanda del centro de consumo j y no se exceda la
capacidad de oferta del origen i.

El problema de transporte (PT), modelado usando P.L. queda como:

m n
Min Z C X
i 1 j 1 ij ij
s.a.
n
X ai , i 1,  , m,
j 1 ij
m
X bj, j 1,  , n
i 1 ij
X ij 0, i, j

El primer conjunto de restricciones indica que la suma de envíos a distintos destinos,

no puede exceder el nivel de producción de cada origen y el segunda conjunto de
restricciones indica que la suma de recepciones de los distintos orígenes, no puede
ser menor que el nivel de demanda de de cada destino.

Este problema indica que:

m n
ai bj
i 1 j 1
lo cual, nos permite definir el siguiente teorema.

Teorema 1: Una condición necesaria y suficiente para que el problema de transporte,

tenga solución es que la oferta sea igual a la demanda:
m n

ai bj
i 1 j 1

114
Con esto, el problema a resolver es:
m n
Min Z C X
i 1 j 1 ij ij
s.a.
n
X ai , i 1,, m,
j 1 ij
m
X bj, j 1,, n
i 1 ij
X ij 0, i, j
A esta última estructura de programación lineal (PT) se le conoce como estructura de
transporte.

Si escribiésemos el Problema de Transporte de forma condensada, sería:

Min
Z CX
sa : PT
AX d
X 0

Donde:
XT X 11 X 12  X 1n X 21 X 22  X 2 n  X m1 X m 2  X mn
C C11 C12  C1n C21 C22  C2 n  Cm1 Cm 2  Cmn
T
d a1 a2  am b1 b2  bn
1 0 0  0 0
0 1 0  0 0
0 0 1  0 0 m renglones
A m n renglones
     
0 0 0  0 1
I I In I n I n n renglones
nn
 
m n columnas

El vector 1 y el vector 0 de la matriz A son vectores fila conteniendo,

respectivamente, n unos y n ceros, y In es la matriz identidad de n n componentes,
tal como se muestra a continuación:
1 1 1 1  1

n componentes
0 0 0 0  0
  
n componentes

115
 1 0  0 0
0 1  0 0
In n componentes
    
0 0  0 1
  
n componentes

Esta estructura y dos propiedades sobre la matriz A, permiten el desarrollo de un

nuevo algoritmo, llamado de transporte, que resuelve este tipo de problema de
manera más eficiente (menos tiempo e iteraciones) que el método simplex. De
acuerdo a lo ya estudiado, podemos analizar que la aplicación del método simplex
generaría un sin fin de iteraciones, partiendo de una base inicial y llegando a la
solución óptima, pero por la cantidad de variables puede resultar engorroso este
desarrollo. Pero mediante ciertos trucos que permiten simplificar este problema lineal
y mediante la simplificación del cambio de las variables básicas, le permitio a Dr.
Dantzig desarrollar el algoritmo de transporte.

3.1.2.- Algoritmo de Transporte

Como hemos mencionado, lo que se quiere resolver es:
m n
Min Z C X
i 1 j 1 ij ij
s.a.
n
X ai , i 1,, m,
j 1 ij
m
X bj, j 1,, n
i 1 ij
X ij 0, i, j

Este problema se facilita, como indicamos anteriormente, si se establecen dos

matrices: una de costos y la otra de flujos, tal como se muestra a continuación:
1 2 3  n Oferta
1 C11 C12 C13  C1n a1
2 C 21 C 22 C 23  C 2n a2
3 C31 C32 C33  C3n a3
Matriz de costos
      
      
m C m1 C m 2 C m3  C mn am
Demanda b1 b2 b3  bn

116
 1 2 3  n Oferta
1 X 11 X 12 X 13  X 1n a1
2 X 21 X 22 X 23  X 2n a2
3 X 31 X 32 X 33  X 3n a3
Matriz de flujos
      
      
m X m1 X m2 X m3  X mn am
Demanda b1 b2 b3  bn

Nota: Este algoritmo también se conoce como Stepping Stone Algorithm o Algoritmo
de Saltando Piedras.

En el caso que la oferta total sea mayor que la demanda total, entonces se tendrá:
m n
a b
i j
i 1 j 1

Para solucionar este conflicto, se introduce un Centro de Consumo Artificial, cuya

demanda estará dado por:
m n
bn 1 a b
i 1 i j 1 j

Los costos unitarios hacia ese centro de consumo b n+1 serán todos ceros, es decir, la
matriz de costos asociada quedará:
1 2 3  n n 1 Oferta
1 C11 C12 C13  C1n 0 a
1
2 C 21 C 22 C 23  C 2n 0 a
2
3 C31 C32 C33  C3n 0 a
3
       
       
m C m1 C m 2 C m3  C mn 0 a
n
Demanda b1 b2 b3  bn bn 1

Por otro lado, si la demanda total excede a la oferta total, es decir:

n n
bj ai
j 1 i 1

Entonces, se añade un Centro de Oferta Artificial, cuya oferta será:

a b a
m 1 j i

117
Los costos unitarios hacia ese centro d oferta a n+1, serán todos ceros, es decir, la
matriz de costos queda:

1 2  n Oferta
1 C11 C 21  C1n a1
2 C12 C 22  C 2n a2
    
m C m1 C m 2  C mn an
m 1 0 0  0 am 1
Demanda b1 b2  bn

Una vez que el problema de transporte está balanceado, ya sea agregando centros
de demanda o centros de oferta ficticios o artificiales, se asegura que cumple con la
condición necesaria y suficiente para que el problema tenga solución.

Con lo anterior, se requiere que dicha solución inicial que sea básica (SBFI) y
factible. Para obtener dicha solución básica factible inicial, se utilizan distintos
mecanismos para su obtención, siendo en nuestro caso tres: Método de la Esquina
Noroccidental, Método del Mínimo Costo y Método de Vogel.

3.1.2.1.- Método Del Extremo Noroccidental (MEN)

El punto de partida es un matriz con orígenes, destinos, ofertas y demandas de un
problema balanceado, como se muestra a continuación:
1 2 3  n Oferta
1 a1
2 a2
3 a3
   
   
m am
Demanda b1 b2 b3  bn

Para obtener una solución básica factible se empieza a construir una matriz de flujos
de la siguiente manera:

Paso 1:
En la posición (1,1), que es la esquina N-0 de la matriz ( de ahí su nombre), se
asigna el siguiente flujo a dicha posición:

118
X 11 Min a1 , b1
aˆ1 a1 X11

bˆ b1 X 11
1

Si se estuviera en una posición cualesquiera (i, j):

X ij Min ai , b j

aˆ i ai X ij

bˆ b X ij
j i

Paso 2:
Ocurrirá que una de los componentes, ya sea demanda u oferta será igual a cero,
por lo cual:
Si â 0 , pasar a la posición (2,1) y hacer X 21 Min a2 , bˆ1 Min a , b X .
1 2 1 11
Si b̂ 0 , pasar a la posición (1,2) y hacer X Min aˆ1, b Min a X , b
1 12 2 1 11 2

Esta condición de manera general, posición (i, j) indica que:

1. Si aˆi 0 ( ) , descender a la posición (i+1, j) y hacer X i i, j Min ai 1 , bˆ j .

2. Si bˆ 0 ( ) , avanzar a la posición (i, j+1) y hacer X Min aˆi , b

j i, j 1 j 1

Paso 3:
Continuar con la misma lógica hasta llegar a la posición (m, n). La matriz de flujos
que se obtenga será factible y básica para el problema de transporte.

Ejemplo:
Se tiene tres plantas, las cuales abastecen a 5 regiones; como se indica a
continuación:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 16 19 16 60
3 18 15 18 20 M 90
Demanda 30 40 70 40 60

Nota: La letra M indica que la planta 3 no abastece a la región 5, dónde es un valor

muy alto (Penalización).

Solución:
Se debe analizar si la demanda es igual a la oferta, es decir:

119
 ai bj
i j

40 60 90 30 40 70 40 60
190 240

Como existe una mayor demanda que oferta, implica que de acuerdo a nuestras
definiciones, es necesario agregar un centro de oferta artificial (m+1=3+1=4), así la
matriz queda con un Centro de Oferta Artificial 4 y una oferta a4=50 y los costos
asociados a cada centro de demanda es igual a cero, entonces la matriz de costos
asociada es la siguiente:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

Con la matriz anterior, nos permite buscar nuestro objetivo, el cual es obtener la
matriz de flujos, siendo inicialmente igual a:
1 2 3 4 5 Oferta
1 40
2 60
3 90
4 50
Demanda 30 40 70 40 60

A continuación, se obtendrá la solución básica falible inicial, aplicando la MEN:

Iteración 1:
Paso 1:
X 11 Min a1 , b1 Min 40,30 30
aˆ1 40 30 10

bˆ 30 30 0
1

De esta manera, el centro de consumo 1 ha sido abastecido completamente y con el

resto del centro de demanda 1, se puede abastecer a otro mercado.

Paso 2:
Como bˆ1 0 , se pasa a la posición (1,2), entonces:

120
 X12 Min aˆ1, b2 (10,4) 10
aˆˆ1 10 10 0
bˆ2 40 10 30

De acá en adelante, no se indicarán los pasos 1 y 2, ya que estos se traslapan:

Iteración 2: Como aˆˆ1 0 , se pasa a la posición (2,2):

X 22 Min a 2 , bˆ2 60 ,30 30
aˆ 60 30 30
2
ˆ
bˆ 30 30 0
2

ˆ
Iteración 3: Como bˆ2 0 , entonces pasa a la posición (2,3)

X 23 Min aˆ 2 , b3 Min 30,70 30

aˆˆ 30 30 0
2
bˆ 70 30 40
3

Iteración 4: Como ∠2 0 , entonces pasa a la posición (3,3)

X 33 Min a3 , bˆ3 90,40 40
aˆ 90 40 50
3
ˆˆ
b 40 40 0
3

ˆ
Iteración 5: Como bˆ3 0 , entonces pasa a la posición (3,4)
X 34 Min aˆ3 , b4 50 ,40 40

aˆˆ 50 40 10
3
bˆ 40 40 0
4
Iteración 6: Como bˆ4 0 , entonces pasa a la posición (3,5)
X 35 Min aˆˆ3 , b5 10,60 10
ˆ
aˆˆ 10 10 0
3
bˆ 60 10 50
5

ˆ
Iteración 7: Como aˆˆ 3 0 , entonces pasa a la posición (4,5)

121
X 45 Min a 4 , bˆ5 50,50 50
aˆ 50 50 0
4
ˆ
bˆ 50 50 0
5

Notemos que la posición (4, 5) es efectivamente la última posición.

La solución básica factible inicial de la matriz de flujos es:

1 2 3 4 5 Oferta
1
1 30 10 2 0 0 0 40
3
2 0 30 30 4 0 0 60
5 6
3 0 0 40 40 10 7 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60

Costo MEN:
C X 20 * 30 19 *10 20 * 30 13 * 30 18 * 40 20 * 40 M *10 0 * 50 $3.300 10 M
ij ij
i j

Los números sobre las flechas indican las iteraciones de MEN. La solución inicial es
básica, ya que hay m n 1 4 5 1 8 flujos que X ij 0 y el resto, es decir,
m n m n 1 4 5 8 12 flujos son iguales acero X ij 0 . Lo anterior indica que
se satisfacen las restricciones de oferta y las restricciones de demanda y además, la
solución inicial es no-degenerada, porque hay exactamente m n 1 flujos en la
base que son positivos.

Aunque este método es sencillo, tiene como desventaja que la SBFI de la región de
soluciones del PT, se encuentra demasiado alejado de la solución óptima, es decir,
desde este punto hasta la solución óptima se requerirán varias iteraciones, lo cual
puede ser costoso desde el punto de uso del computador. La cusa principal de este
problema es que este método no toma en cuenta el costo, sólo la oferta y la
demanda.

Del ejemplo anterior, se puede analizar que existe un valor extremadamente elevado
(10M), el cual no favorece para nada el costo del transporte, asociado a la solución
inicial del problema

122
3.1.2.2.- Método De Vogel
Este método, que nos entrega una solución básica factible inicial para el algoritmo de
transporte, nos proporciona una solución más cercana al punto óptimo.

Los pasos a seguir son los siguientes:

Paso 1:
Construya la matriz de costos y flujos asociados al problema balanceado y vaya al
paso 3.

Paso 2:
Utilice el remanente de la matriz de costos y flujos una vez que estos últimas se
hayan asignado.

Paso 3:
Se entiende por diferencia de fila (de columna) a la diferencia entre los dos números
más pequeños que hay en la fila (columna). Calcule todas las diferencias de filas o
columnas de la matriz de costos.

Paso 4:
Seleccione aquella fila o columna con mayor diferencia. Los empates se rompen de
manera arbitraria.

Paso 5:
Seleccione el costo más pequeño en la matriz de costos, ya sea en la fila o columna
seleccionada en el paso anterior. Designe a esta posición como Cij.

Paso 6:
En la matriz de flujo, hágase X ij Min ai , b j , donde la posición (i,j) fue identificada
en el paso anterior.

Hágase la oferta ai igual a:

aˆi ai X ij
y la demanda bj igual a:
b̂ b X ij
j i
Paso 7:
1. Si aˆ 0 , llénese la fila i de la matriz de flujos con ceros, a excepción de la
i
posición (i,j) y elimínese esa fila de cualquier consideración futura en la matriz de
costos.
2. Si bˆ 0 , llénese la columna j de la matriz de flujos con ceros, a excepción de la
j
posición (i,j) y elimínese a esa columna de cualquier consideración futura en la
matriz de costos.
Regrese al paso 2

123
Ejemplo
Resolvamos el mismo problema anterior, pero utilizando el método de Vogel:
Iteración 1:
Matriz de Costos y Flujos:
1 2 3 4 5 Oferta 1 2 3 4 5 Oferta
1 20 19 14 21 16 40 1 40
2 15 20 13 19 16 60 2 60
3 18 15 18 20 M 90 3 90
4 0 0 0 0 0 50 4 50
Demanda 30 40 70 40 60 Demanda 30 40 70 40 60
Paso 3:
1 2 3 4 5 Oferta Diferencia
1 20 19 14  21 16  40 2
2 15  20 13  19  16  60 2
3 18  15  18  20 M 90 3
4 0  0  0  0  0  50 0
Demanda 30 40 70 40 60
Diferencia 15 15 13 19 16
Rojo: mínimos por fila . Azul: mínimos por columna .
Paso 4:
Se selecciona la columna cuatro por tener la mayor diferencia que es 19.
Paso 5:
El costo más pequeño corresponde a Cij C 44 0 .
Paso 6:
X 44 min( a4 , b4 ) min( 50,40) 40
a 4 a4 X 44 50 40 10 b 4 b4 X 44 40 40 0
Paso 7:
Como b 4 0 , todos los elementos de la columna 4, a excepción de X44, se hacen
igual a cero y la columna 4 se elimina para cualquier consideración futura.

Iteración 2:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

124
 1 2 3 4 5 Oferta
1 0 40
2 0 60
3 0 90
4 40 50
Demanda 30 40 70 40 60
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:

1 2 3 4 5 Oferta Diferencia
1 20 19 14  16  40 2
2 15  20 13  16  60 2
3 18  15  18  M 90 3
4 0  0  0  0  10 0
Demanda 30 40 70 0 60
Diferencia 15 15 13 16
Paso 4:
Se selecciona la columna cinco por tener la mayor diferencia que es 16.
Paso 5:
El costo más pequeño corresponde a Cij C 45 0 .
Paso 6:
X 45 min( aˆ 4 , b5 ) min(10,60) 10

aˆ 4 aˆ 4 X 45 10 10 0 b 5 b5 X 45 60 10 50
Paso 7:
Como aˆˆ 4 0 , todos los elementos de la fila 4 se hacen cero, a excepción de X 45 y la
fila 4 se elimina para cualquier consideración futura.

Iteración 3:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 40
2 0 60
3 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60

125
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:
1 2 3 4 5 Oferta Diferencia
1 20 19  14  16  40 2
2 15  20 13  16  60 2
3 18  15  18  M 90 3
4  0
Demanda 30 40 70 0 50
Diferencia 3 4 1 0
Paso 4:
Se selecciona la columna dos por tener la mayor diferencia que es 4.
Paso 5:
El costo más pequeño corresponde a Cij C32 15 .

Paso 6:
X 32 min( a3 , b2 ) min( 90,40) 40
aˆ3 a3 X 32 90 40 5 0 bˆ2 b2 X 32 40 40 0
Paso 7:
Como bˆ2 0 , todos los elementos de la columna 2 se hacen cero, a excepción de
X32 y la columna 2 se elimina para cualquier consideración futura.

Iteración 4:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 0 40
2 0 0 60
3 40 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:
1 2 3 4 5 Oferta Diferencia
1 20 14  16  40 2
2 15  13  16  60 2
3 18  18  M 50 0
4  0
Demanda 30 0 70 0 50

126
 Diferencia 3 1 0
Paso 4:
Se selecciona la columna uno por tener la mayor diferencia que es 3.
Paso 5:
El costo más pequeño corresponde a Cij C 21 15 .
Paso 6:
X 21 min( a2 , b1 ) min( 60,30) 30
aˆ a X
2 2 21 60 30 3 0 bˆ b X
1 1 30 30 0
21
Paso 7:
Como bˆ1 0 , todos los elementos de la columna 1 se hacen cero, a excepción de
X21 y la columna 1 se elimina para cualquier consideración futura.

Iteración 5:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 0 0 40
2 30 0 0 60
3 0 40 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:
1 2 3 4 5 Oferta Diferencia
1 14  16  40 2
2 13  16  30 3
3 18  M 50 M-18
4  0
Demanda 0 0 70 0 50
Diferencia 1 0
Paso 4:
Se selecciona la fila tres por tener la mayor diferencia que es M-18.
Paso 5:
El costo más pequeño corresponde a Cij C33 18 .
Paso 6:
X 33 min( aˆ3 , b3 ) min( 50,70) 50
aˆ3 aˆ3 X 33 50 50 0 bˆ3 b3 X 33 70 50 20

127
Paso 7:
Como aˆˆ3 0 , todos los elementos de la fila 3 se hacen cero, a excepción de X 33 y la
fila 3 se elimina para cualquier consideración futura.

Iteración 6:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 0 0 40
2 30 0 0 60
3 0 40 50 0 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:
1 2 3 4 5 Oferta Diferencia
1 14  16  40 2
2 13  16  30 3
3 0
4  0
Demanda 0 0 20 0 50
Diferencia 1 0
Paso 4:
Se selecciona la fila dos por tener la mayor diferencia que es 3.
Paso 5:
El costo más pequeño corresponde a Cij C 23 13 .
Paso 6:
X 23 min( aˆ 2 , bˆ3 ) min( 30,20) 20
aˆ 2 aˆ 2 X 23 30 20 10 bˆ3 bˆ3 X 23 20 20 0
Paso 7:
Como bˆ3 0 , todos los elementos de la columna 3 se hacen cero, a excepción de X 23
y la columna 3 se elimina para cualquier consideración futura.

Iteración 7:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:

128
 1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

1 2 3 4 5 Oferta
1 0 0 0 0 40
2 30 0 20 0 60
3 0 40 50 0 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:
1 2 3 4 5 Oferta Diferencia
1 16  40 16
2 16  10 16
3 0
4  0
Demanda 0 0 0 0 50
Diferencia 0
Paso 4:
Se selecciona la fila uno o dos (arbitrariamente se rompe este empate) por tener la
mayor diferencia que es 16.

Paso 5:
El costo más pequeño corresponde a Cij C15 16 .
Paso 6:
X 15 min( a1 , bˆ5 ) min( 40,50) 40
aˆ1 a1 X 15 40 40 0 bˆ5 bˆ5 X 15 50 40 10
Paso 7:
Como aˆ1 0 , todos los elementos de la fila 1 se hacen cero, a excepción de X 15 y la
fila 1 se elimina para cualquier consideración futura.

Iteración 8:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:

129
 1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 0 0 0 40 40
2 30 0 20 0 60
3 0 40 50 0 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60
Paso 3:
Se calcula nuevamente las diferencias por fila y columna de la matriz de costo:
1 2 3 4 5 Oferta Diferencia
1 0
2 16  10 16
3 0
4  0
Demanda 0 0 0 0 10
Diferencia 0
Paso 4:
Se selecciona la fila dos por tener la mayor diferencia que es 16.
Paso 5:
El costo más pequeño corresponde a Cij C 25 16 .
Paso 6:
X 25 min( aˆ 2 , bˆ5 ) min(10,10) 10
ˆ
aˆˆ 2 aˆ 2 X 25 10 10 0 bˆ5 bˆ5 X 25 10 10 10
Paso 7:
ˆ
Como aˆˆ1 0 bˆ5 0 , todos los elementos de la fila 2 y la columna 5 se hacen cero, a
excepción de X25 y la fila 1 y la columna 5 se eliminan para cualquier consideración
futura.

Iteración 9:
Paso 2:
Notemos que efectivamente la iteración anterior fue la última, por lo cual, se obtiene
la Matriz de Costos (sin tarjar) y La Matriz de Flujos final:
Matriz de Costos:

130
 1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

Matriz de Flujos:
1 2 3 4 5 Oferta
1 0 0 0 0 40 40
2 30 0 20 0 10 60
3 0 40 50 0 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60

Para calcular el costo del Método de Vogel se multiplican los flujos y costos
respectivos, correspondiente a la SBFI, obteniendo el siguiente valor:
C X 40 *16 30 *15 20 *13 10 *16 40 *15 50 *18 40 * 0 10 $3.010
ij ij
i j

3.1.2.4.- Método del Costo Mínimo

Este método, que nos entrega una solución básica factible inicial para el algoritmo de
transporte, nos proporciona una solución cercana al punto óptimo.

Los pasos a seguir son los siguientes:

Paso 1:
Construya la matriz de costos y flujos asociados al problema balanceado y vaya al
paso 3.

Paso 2:
Utilice el remanente de la matriz de costos y flujos una vez que estas últimas se
hayan asignado.

Paso 3:
Seleccione el costo más pequeño en la matriz de costos, ya sea en fila o columna.
Designe a esta posición como Cij.

Paso 4:
En la matriz de flujo, hágase X ij Min ai , b j , donde la posición (i,j) fue identificada
en el paso anterior.
Hágase la oferta ai igual a:

131
 aˆi ai X ij
Hágase la demanda bj igual a:
b̂ b X ij
j i

Paso 5:
3. Si aˆ 0 , llénese la fila i de la matriz de flujos con ceros, a excepción de la
i
posición (i,j) y elimínese esa fila de cualquier consideración futura en la matriz de
costos.
4. Si bˆ 0 , llénese la columna j de la matriz de flujos con ceros, a excepción de la
j
posición (i,j) y elimínese a esa columna de cualquier consideración futura en la
matriz de costos.

Regrese al paso 2

Ejemplo
Resolvamos el mismo problema anterior, pero utilizando el método de Vogel:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

Iteración 1:
Paso 1:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

Paso 3:
El costo más pequeño de la matriz, corresponde completamente a la fila 4, por lo
cual, se elije arbitrariamente la posición (4,5): Cij C 45 0 .
Paso 4:
X 45 min( a4 , b5 ) min( 50,60) 50
aˆ a X
4 4 44 50 50 0 bˆ b X
5 5 60 50 1045
Paso 5:
Como aˆ 4 0 , todos los elementos de la fila 4, a excepción de X45, se hacen igual a
cero y la fila 4 se elimina para cualquier consideración futura.

132
Iteración 2:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 40
2 60
3 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60
Paso 3:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4  0
Demanda 30 40 70 40 10
El costo más pequeño de la matriz, corresponde a la posición (2,3): Cij C 23 13 .
Paso 4:
X 23 min( a2 , b3 ) min( 60,70) 60
aˆ 2 a2 X 23 60 60 0 bˆ3 b3 X 23 70 60 10
Paso 5:
Como aˆ 2 0 , todos los elementos de la fila 2, a excepción de X 23, se hacen igual a
cero y la fila 2 se elimina para cualquier consideración futura.

Iteración 3:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta

133
 1 40
2 0 0 60 0 0 60
3 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60

Paso 3:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 0
3 18 15 18 20 M 90
4  0
Demanda 30 40 10 40 10
El costo más pequeño de la matriz, corresponde a la posición (1,3): Cij C13 14 .
Paso 4:
X13 min( a1 , bˆ3 ) min( 40,10) 60

a1 a1 X 13 40 10 3 0 bˆ 3 bˆ3 X 23 10 10 0
Paso 5:
ˆ
Como bˆ3 0 , todos los elementos de la columna 3, a excepción de X 13, se hacen
igual a cero y la columna 3 se elimina para cualquier consideración futura.

Iteración 4:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 10 40
2 0 0 60 0 0 60
3 0 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60
Paso 3:
1 2 3 4 5 Oferta
1 20 19 21 16 30
2 0
3 18 15 20 M 90
4  0
Demanda 30 40 0 40 10

134
El costo más pequeño de la matriz, corresponde a la posición (3,2): Cij C32 15 .
Paso 4:
X 32 min( a3 , b2 ) min( 90,40) 40

a 3 a3 X 32 90 40 5 0 b 2 b2 X 32 40 40 0
Paso 5:
Como bˆ2 0 , todos los elementos de la columna 2, a excepción de X 32, se hacen
igual a cero y la columna 2 se elimina para cualquier consideración futura.

Iteración 5:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 10 40
2 0 0 60 0 0 60
3 40 0 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60
Paso 3:
1 2 3 4 5 Oferta
1 20 21 16 30
2 0
3 18 20 M 50
4  0
Demanda 30 0 0 40 10
El costo más pequeño de la matriz, corresponde a la posición (1,5): Cij C15 16 .
Paso 4:
X15 min( a1 , bˆ5 ) min( 30,10) 10
ˆ
aˆ1 a1 X 15 10 10 10 bˆ5 bˆ5 X 15 30 10 2 0
Paso 5:
ˆ
Como bˆ5 0 , todos los elementos de la columna 5, a excepción de X 15, se hacen
igual a cero y la columna 5 se elimina para cualquier consideración futura.

Iteración 6:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:

135
 1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 10 10 40
2 0 0 60 0 0 60
3 40 0 0 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60

Paso 3:
1 2 3 4 5 Oferta
1 20 21 20
2 0
3 18 20 50
4  0
Demanda 30 0 0 40 0
El costo más pequeño de la matriz, corresponde a la posición (3,1): Cij C31 16 .
Paso 4:
X 31 min( aˆ3 , b1 ) min( 50,30) 30
aˆˆ aˆ X
3 3 31 50 30 2 0 1 bˆ b X
1 30 30 0
31
Paso 5:
Como bˆ1 0 , todos los elementos de la columna 1, a excepción de X 31, se hacen
igual a cero y la columna 1 se elimina para cualquier consideración futura.

Iteración 7:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 0 10 10 40
2 0 0 60 0 0 60
3 30 40 0 0 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60

136
Paso 3:
1 2 3 4 5 Oferta
1 21 20
2 0
3 20 20
4  0
Demanda 0 0 0 40 0
El costo más pequeño de la matriz, corresponde a la posición (3,4): Cij C34 20 .
Paso 4:
X 34 min( aˆˆ3 , b4 ) min( 20,40) 20
ˆ
aˆˆ 3 aˆˆ 3 X 31 20 20 0 bˆ4 b4 X 34 40 20 2 0
Paso 5:
ˆ
Como aˆˆ 3 0 , todos los elementos de la fila 3, a excepción de X34, se hacen igual a
cero y la fila 3 se elimina para cualquier consideración futura.

Iteración 8:
Paso 2:
Al regresar, la matriz de costos y flujos quedan de la siguiente manera:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60
1 2 3 4 5 Oferta
1 0 0 10 10 40
2 0 0 60 0 0 60
3 30 40 0 20 0 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60

Paso 3:
1 2 3 4 5 Oferta
1 21 20
2 0
3 0
4  0
Demanda 0 0 0 20 0
El costo más pequeño de la matriz, corresponde a la posición (1,4): Cij C14 21 .

Paso 4:
X 14 min( aˆ1 , bˆ4 ) min( 20,20) 0

137
 ˆ
aˆˆ1 aˆ1 X14 20 20 0 bˆ4 bˆ4 X 14 20 20 0

Paso 5:
ˆ
Como aˆˆ 0 bˆ4 0 , todos los elementos de la fila 1 y columna 4, a excepción de
1
X14, se hacen igual a cero y la fila 1 y columna 4 se elimina para cualquier
consideración futura.

Iteración 9:
Paso 2:
Notemos que efectivamente la iteración anterior fue la última, por lo cual, se obtiene
la Matriz de Costos (sin tarjar) y La Matriz de Flujos final:
Matriz de Costos:

1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

Matriz de Flujos:
1 2 3 4 5 Oferta
1 0 0 10 20 10 40
2 0 0 60 0 0 60
3 30 40 0 20 0 90
4 0 0 0 0 50 50
Demanda 30 40 70 40 60

Para calcular el costo del Método de Costo Mínimo, se multiplican los flujos y costos
respectivos, correspondiente a la SBFI, obteniendo el siguiente valor:
C X 10 *14 20 * 21 10 *16 60 *13 30 *18 40 *15 20 * 20 50 * 0 $3.040
ij ij
i j

3.1.2.4.- Algoritmo De Transporte

La metodología para aplicar el algoritmo de transporte para obtener la solución
óptima es la siguiente:

Paso 1:
Balancear el problema de transporte, a fin de cumplir la condición necesaria y
suficiente para obtener una solución óptima, es decir:

138
 m n
ai bj
i 1 j 1

Paso 2:
Generar una solución inicial que sea básica y factible, utilizando, ya sea: Método de
Vogel o Método De Extremo NorOccidental o Método de Mínimo Costo.

Paso 3:
Construir una matriz de costos C ij , asociada a la solución básica factible que se
tenga, donde:
C C , Si X está en la base
ij ij ij
C 0 , Si X no está en la base
ij ij

Paso 4:
Con esta matriz de costos, calcular el valor de todas las variables duales:
u , con i 1,...., m v , con j 1,....., n
i j
Utilizando la expresión:
ui v j Cij 0 i 1,..., m ; j 1,..., n

Como hay m n variables (m variables ui, n variables vj) y solamente m n 1

ecuaciones ui v j Cij 0 (existe sólo un grado de libertad). Esto equivale a dar un
valor arbitrario (se recomienda el valor cero) a cualquiera de las variables duales y
así queda por resolver un sistema de m n 1 ecuaciones con m n 1 variables.

Paso 5:
Los parámetros zij cij se calculan por medio de la ecuación zij cij (ui v j ) cij .
Como estamos usando el PT como minimización, si todos los Zij Cij 0, i, j , la
solución actual es óptima. En caso contrario, si Zij Cij 0, i, j , se elije el valor más
positivo, correspondiente a X ij , correspondiente a la variable de flujo X ij para debe
entrar a la base.
Para seguir la coherencia general de la programación, el PT será aplica mediante
reglas de maximización, lo cual: si todos los Zij Cij 0, i, j , la solución actual es
óptima. En caso contrario, si Zij Cij 0, i, j , se elije el valor más negativo,
correspondiente a la variable de flujo X ij para debe entrar a la base.

Paso 6:

139
Si la variable X ij entra a la base con un cierto valor positivo , la oferta ai y la
demanda b j se desequilibran en un valor , a menos de que exista un mecanismo
de compensación.

Veamos como se produce este desequilibrio, antes de conocer el mecanismo.

Supongamos que para el problema de transporte se tiene la siguiente solución

básica factible:
Matriz de Flujos Inicial:
1  j  n Oferta
1 X 11 X1 j a1
 
i X in ai
 
m X m1 X mn am
Demanda b1  b j  bn

Tengamos presente que los cinco flujos generan una solución básica factible inicial
(m+n-1=5), ya que:
X 11 X ij a1
X in ai
X m1 X mn am
X 11 X m1 b1
X1 j bj
X in X mn bn
X 11 0, X 1 j 0, X in 0, X m1 0, X mn 0

Supongamos que zij cij , es la más negativa y por lo tanto, X ij entra a la nueva
base con un determinado valor 0 , ( X ij , entra a la base por que z ij cij 0 ).

Tabularmente se tiene lo siguiente:

140
 1  j  n Oferta
1 X 11 X1 j a1
 
i / X ij X in ai
 
m X m1 X mn am
Demanda b1  bj  bn

Si 0 , esta nueva solución ya no es básica, porque m+n=6 elementos en la base y

no m+n-1=5, como debiese ser. También la solución no es, ya que por un lado la
oferta del origen i es mayor que ai, siendo:
X a a
in i i
y por el otro lado, la demanda del destino j es mayor que bj, siendo:
X b b .
1j j j

Existe un desequilibrio que únicamente puede desaparecer si se resta o suma

unidades en ciertos puntos de la matriz de flujos; lo anterior, permite construir un
circuito, tal como se indica a continuación:
1  j  n Oferta
1 X 11 X1 j a1
 
i X in ai
 
m X m1 X mn am
Demanda b1  bj  bn

Se puede apreciar, que dependiendo de las posiciones de la matriz de flujos, se ha

sumado el valor de en otras posiciones y se ha restado el valor de en otras
posiciones, para mantener el equilibrio entre la oferta y demanda.
De acuerdo a lo anterior, se ha regenerado la factibilidad, más no lo básico del
efecto, es decir:
X 11 X ij a1
X in ai
X m1 X mn am
X 11 X m1 b1
X1 j bj
X in X mn bn

141
Para que esta solución sea básica, es decir, que solamente están m+n-1 elementos
en la base, debe ser lo suficientemente grande como para reducir el valor de uno o
varios flujos básicos a cero. Si analizamos la matriz anterior, vemos que si
aumenta, los siguientes flujos disminuyen: X , X , X , por lo tanto:
1j in m1

min X ,X ,X
1j in m1

Este circuito es único, por lo cual, el paso 6 se puede resumir como sigue:

6.a.- Construya el circuito único que contiene a la variable Xij que entra a la base.

Nota: Un reglón o una columna pueden tener más de dos celdillas en el circuito, pero
no pueden ser consecutivas más de dos de ellas.

6.b.- X ij , donde es el mínimo de los vectores básicos en el circuito que

disminuyen su valor a medida que aumenta.

Ejemplo:
Sea el problema de transporte, que tiene tres orígenes con capacidad de 40, 60 y 90
unidades, respectivamente y cinco destinos con demandas de 30, 40, 70, 40 y 60
unidades, respectivamente y los costos unitarios están dados en la siguiente tabla:
Matriz de Costos:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 No surte 90
Demanda 30 40 70 40 60

Por razones técnicas, el origen 3 no puede abastecer al destino 5.

Iteración 1:
El problema esta desbalanceado, puesto que la oferta total es menor que la
demanda total en 50 unidades. Como se muestra a continuación:
4 5
a 190 b 240
i 1i j 1 j
De esta manera, para balancear el problema se debe crear un centro de oferta
artificial a5, el cual tiene una oferta de 50 unidades y cuyos costos son
C 4 j 0, j ,,5 . El problema ya balanceado, genera la siguiente matriz de costos:
1 2 3 4 5 Oferta
1 20 19 14 21 16 40
2 15 20 13 19 16 60
3 18 15 18 20 M 90
4 0 0 0 0 0 50
Demanda 30 40 70 40 60

142
Paso 2: Utilizando el Método de Vogel, se obtiene la solución básica factible inicial,
con un costo de $3.010. La matriz de flujos asociada es:
1 2 3 4 5 Oferta
1 0 0 0 0 40 40
2 30 0 20 0 10 60
3 0 40 50 0 0 90
4 0 0 0 40 10 50
Demanda 30 40 70 40 60

Paso 3:
Se construye la matriz de costos C ij , donde:
C 15 16 C 32 15
C 21 15 C 33 18
C 23 13 C 44 0
C 25 16 C 45 0

El resto de los C ij 0 . A continuación, hay que asociar las variables duales ui a los
orígenes ( i 1,,4 ) y las vj a los destinos ( j 1,,5 ), generándose la siguiente
matriz de costos actualizada:
1 2 3 4 5
1 0 0 0 0 16 u1
2 15 0 13 0 16 u2
3 0 15 18 0 0 u3
4 0 0 0 0 0 u4
v1 v2 v3 v4 v5

Paso 4:
Se generan las ecuaciones: ui v j Cij 0 i 1,..., m ; j 1,..., n

De esta manera:
C15 u1 v5 0
C 21 u 2 v1 0
C 23 u2 v3 0
C 25 u2 v5 0
C 32 u3 v2 0
C 33 u3 v3 0
C 44 u4 v4 0
C 45 u4 v5 0

143
Se puede analizar que se puede, específicamente, utilizar tanto u2 o v5, las cuales
están tres veces en las ecuaciones anteriores y por conveniencia asignaremos en
este caso u2=0.

Las ecuaciones anteriores, nos permiten conocer v1, v3 y v5:

C 21 u 2 v1 0 v1 C 21 15
C 23 u2 v3 0 v3 C 23 13
C 25 u2 v5 0 v5 C 25 16

Conocidos las variables duales v1, v3 y v5, se calculan ahora u1, u3, u4, v2 y v4:
C15 u1 v5 0 u1 C15 v5 16 16 0
C 33 u3 v3 0 u3 C 33 v3 18 13 5
C 45 u4 v5 0 u4 C 45 v5 0 16 16
C 32 u3 v2 0 v2 C 32 u3 15 5 10
C 44 u 4 v4 0 v4 C 44 u 4 0 ( 16) 16

En resumen:
u1 0 , v1 15
u2 0 , v2 10
u3 5 , v3 13
u4 16 , v4 16
v5 16

Paso 5:
Utilizando la formula: z c C (u v ), i, j N , se obtienen los indicadores de
ij ij ij i j
optimalidad:
z c C (u v ) 20 (0 15) 5
11 11 11 1 1
z c C (u v ) 19 (0 10) 9
12 12 12 1 2
z c C (u v ) 14 (0 13) 1
13 13 13 1 3
z c C (u v ) 21 (0 16 ) 5
14 14 14 1 4
z c C (u v ) 20 (0 10) 10
22 22 22 2 2
z c C (u v ) 19 (0 16) 3
24 24 24 2 4
z c C (u v ) 18 (5 15) 2
31 31 31 3 1
z c C (u v ) 20 (5 16 ) 1
34 34 34 3 4
z c C (u v ) M (5 16 ) M 21
35 35 35 3 5

144
z c C (u v ) 0 ( 16 15) 1
41 41 41 4 1
z c C (u v ) 0 ( 16 10) 6
42 42 42 4 2
z c C (u v ) 0 ( 16 13) 3
43 43 43 4 3

Si z c 0, indica que la solución es óptima, pero dos elementos son

ij ij
negativos, por lo cual se elije el más negativo, es decir: z c 2 0, por lo
31 31
tanto, X31 entra a la base.

Pase 6:
El circuito queda representado, tabularmente, en la matriz de flujos:
1 2 3 4 5 Oferta
1 40 40
2 30- 20+ 10 60
3 40 50- 90
4  40 10 50
Demanda 30 40 70 40 60

El valor que debe tomar debe ser el mínimo de los flujos que disminuyen al
aumentar , es decir:
Min X ,X Min 30,50 30
21 33

La nueva solución al PT en la Matriz de Flujos es:

1 2 3 4 5 Oferta
1 40 40
2 50 10 60
3 30 40 20 90
4 40 10 50
Demanda 30 40 70 40 60

El costo asociado a la nueva solución es:

CT 3.010 X 31 ( z31 c31 ) 3.010 30 ( 2) $2.950
Volver al paso 3.

Iteración 2:
Paso 3:
Se construye la matriz de costos C ij , donde:
C 15 16 C 32 15
C 23 13 C 33 18
C 25 16 C 44 0
C 31 18 C 45 0

145
El resto de los C ij 0 . A continuación, hay que asociar las variables duales ui a los
orígenes ( i 1,,4 ) y las vj a los destinos ( j 1,,5 ), generándose la siguiente
matriz de costos actualizada:
1 2 3 4 5
1 0 0 0 0 16 u1
2 0 0 13 0 16 u2
3 18 15 18 0 0 u3
4 0 0 0 0 0 u4
v1 v2 v3 v4 v5

Paso 4:
Se generan las ecuaciones: ui v j Cij 0 i 1,..., m ; j 1,..., n . De esta manera:

C15 u1 v5 0
C 23 u2 v3 0
C 25 u2 v5 0
C 31 u3 v1 0
C 32 u3 v2 0
C 33 u3 v3 0
C 44 u 4 v4 0
C 45 u4 v5 0

En este caso se puede utilizar u3, la cual está tres veces en las ecuaciones
anteriores, entonces u3=0.

Las ecuaciones anteriores, nos permiten conocer v1, v2 y v3:

C 31 u3 v1 0 v1 C 31 18
C 32 u3 v2 0 v2 C 32 15
C 33 u3 v3 0 v3 C 33 18

Conocidos las variables duales v1, v2 y v3, se calculan ahora u1, u2, u4, v4 y v5:
C15 u1 v5 0 u1 C15 v5 16 21 5
C 23 u2 v3 0 u2 C 23 v3 13 18 5
C 25 u2 v5 0 v5 C 25 u2 16 ( 5) 21
C 44 u 4 v4 0 v4 C 44 u 4 0 ( 21) 21
C 45 u4 v5 0 u4 C 45 v5 0 (21) 21

En resumen:

146
u1 5 , v1 18
u2 5 , v2 15
u3 0 , v3 18
u4 21 , v4 21
v5 21
Paso 5:
Utilizando la formula: z c C (u v ), i, j N , se obtienen los indicadores de
ij ij ij i j
optimalidad:
z c C (u v ) 20 ( 5 18) 7
11 11 11 1 1
z c C (u v ) 19 ( 5 15) 9
12 12 12 1 2
z c C (u v ) 14 ( 5 18) 1
13 13 13 1 3
z c C (u v ) 21 ( 5 21) 5
14 14 14 1 4
z c C (u v ) 15 ( 5 18) 2
21 21 21 2 1
z c C (u v ) 20 ( 5 15) 10
22 22 22 2 2
z c C (u v ) 19 ( 5 21) 3
24 24 24 2 4
z c C (u v ) 20 (0 21) 1
34 34 34 3 4
z c C (u v ) M (0 21) M 21
35 35 35 3 5
z c C (u v ) 0 ( 21 18) 3
41 41 41 4 1
z c C (u v ) 0 ( 21 15) 6
42 42 42 4 2
z c C (u v ) 0 ( 21 18) 3
43 43 43 4 3

Si z c 0 , indica que la solución es óptima, pero un solo elemento es negativo,

ij ij
por lo cual: z c 1 0 , por lo tanto, X34 entra a la base.
34 34

Pase 6:
El circuito queda representado, tabularmente, en la matriz de flujos:
1 2 3 4 5 Oferta
1 40 40
2 50+ 10- 60
3 30 40 20- 90
4  40- 10+ 50
Demanda 30 40 70 40 60

El valor que debe tomar debe ser el mínimo de los flujos que disminuyen al
aumentar , es decir:

147
 Min X ,X ,X Min 10,20,40 10
25 33 44

La nueva solución al PT en la Matriz de Flujos es:

1 2 3 4 5 Oferta
1 40 40
2 60 60
3 30 40 10 10 90
4 30 20 50
Demanda 30 40 70 40 60
El costo asociado a la nueva solución es:
CT 2.950 X 34 ( z31 c31 ) 2.950 10 ( 1) $2.940
Volvemos al paso 3:

Tercera Iteración:
Paso 3:
Se construye la matriz de costos C ij , donde:
C 15 16 C 33 18
C 23 13 C 34 20
C 31 18 C 44 0
C 32 15 C 45 0

El resto de los C ij 0 . A continuación, hay que asociar las variables duales ui a los
orígenes ( i 1,,4 ) y las vj a los destinos ( j 1,,5 ), generándose la siguiente
matriz de costos actualizada:
1 2 3 4 5
1 0 0 0 0 16 u1
2 0 0 13 0 0 u2
3 18 15 18 20 0 u3
4 0 0 0 0 0 u4
v1 v2 v3 v4 v5

Paso 4:
Se generan las ecuaciones: ui v j Cij 0 i 1,..., m ; j 1,..., n . De esta manera:

C15 u1 v5 0
C 23 u2 v3 0
C 31 u3 v1 0
C 32 u3 v2 0
C 33 u3 v3 0
C 34 u3 v4 0
C 44 u 4 v4 0

148
C 45 u4 v5 0

En este caso se puede utilizar u3, la cual está cuatro veces en las ecuaciones
anteriores, entonces u3=0.

Las ecuaciones anteriores, nos permiten conocer v1, v2, v3 y v4:

C 31 u3 v1 0 v1 C 31 18
C 32 u3 v2 0 v2 C 32 15
C 33 u3 v3 0 v3 C 33 18
C 34 u3 v4 0 v4 C 34 20

Conocidos las variables duales v1, v2, v3 y v4, se calculan ahora u1, u2, u4 y v5:
C15 u1 v5 0 u1 C15 v5 16 20 4
C 23 u2 v3 0 u2 C 23 v3 13 18 5
C 44 u4 v4 0 u4 C 44 v4 0 (20) 20
C 45 u4 v5 0 v5 C 45 u4 0 ( 20) 20

En resumen:
u1 4 , v1 18
u2 5 , v2 15
u3 0 , v3 18
u4 20 , v4 20
v5 20

Paso 5:
Utilizando la formula: z c C (u v ), i, j N , se obtienen los indicadores de
ij ij ij i j
optimalidad:
z c C (u v ) 20 ( 4 18) 6
11 11 11 1 1
z c C (u v ) 19 ( 4 15) 8
12 12 12 1 2
z c C (u v ) 14 ( 4 18) 0
13 13 13 1 3
z c C (u v ) 21 ( 4 20) 5
14 14 14 1 4
z c C (u v ) 15 ( 5 18) 2
21 21 21 2 1
z c C (u v ) 20 ( 5 15) 10
22 22 22 2 2
z c C (u v ) 19 ( 5 20 ) 4
24 24 24 2 4
z c C (u v ) 16 ( 5 20 ) 1
25 25 25 2 5

149
z c C (u v ) M (0 20) M 20
35 35 35 3 5
z c C (u v ) 0 ( 20 18) 2
41 41 41 4 1
z c C (u v ) 0 ( 20 15) 5
42 42 42 4 2
z c C (u v ) 0 ( 20 18) 2
43 43 43 4 3

Si z c 0, i , j N , indica que la solución anterior es óptima

ij ij

Finalmente, se puede resumir que la nueva solución al PT (Matriz de Flujos) es:

1 2 3 4 5 Oferta
1 0 0 0 0 40 40
2 0 0 60 0 0 60
3 30 40 10 10 0 90
4 0 0 0 30 20 50
Demanda 30 40 70 40 60
El costo de la solución es: CT $2.940

De manera esquemática, el problema de transporte es:

Origen Destino

Oferta Demanda
1 30

40 1
16, 40

2 40

60 2 13, 60 15, 40

18, 30
3 70
18, 10
90 3
20, 10
4 40
0, 30
50 4
0, 20
Artificial
5 60

Notemos que la oferta total era de 190 unidades y de demanda total de 240
unidades, por lo cual, existe una demanda insatisfecha de 50 unidades y de acuerdo
al problema de transporte, la manera óptima de no satisfacer esta demanda es
dejando insatisfecho a los centro de consumo 4 en 30 unidades (flujo X44) y al centro
de consumo 5 en 20 unidades (flujo X45).

150
3.1.3.- Problemas de Transporte Degenerados
Como hemos visto, siempre los m+n-1 vectores básicos eran siempre mayores que
cero, pero se puede dar el caso que durante alguna iteración del algoritmo de
transporte se obtenga una solución básica, factible y degenerada, es decir, de los
m+n-1 vectores de la base, uno o mas de dichos vectores básicos obtenga el valor
cero.

Lo anterior puede acarrear que no se pudiera construir las ecuaciones necesarias

para generar la nueva base o, de manera práctica, en la matriz de flujos no se podría
construir un circuito único que se pueda cerrar. Para solucionar dicha situación, ya
que se puede confundir en las distintas iteraciones cuales son las variables básicas
que tienen valor cero, con respecto a las variables no básicas que efectivamente
tienen valor cero, se plantea lo siguiente:
Asigne de forma y manera arbitraria un valor (para representar el cero) a
cualquiera de los elementos que se hayan anulado y que se requieren para
mantener los m+n-1 componentes de la base. Este valor sólo es útil para
distinguir los ceros de las variables básicas con respecto a las variables no
básicas. La aplicación del algoritmo de transporte se mantiene igual.

151
 Apéndice
Resumen Método Simplex Revisado

-Inicialización: Igual que el método Simplex original

-Paso iterativo:

Determine la variable básica que entra; igual que el método Simplex original.

Determine la variable básica que sale; igual que el método original excepto, que se
calculan únicamente los miembros requeridos para esto (los coeficientes de la
variable básica que entra en todas las ecuaciones, menos la cero) y después el
segundo miembro de cada ecuación para cada coeficiente estrictamente positivo.

Ejemplo:
Min : Z 3X1 5 X 2
s.a.
x1 4
x2 12
3x1 2x2 18
X1 0 ; X2 0

Max :
Z 3X1 5 X 2
s.a.
x1 x3 4
2x2 x4 12
3x1 2x2 x5 18
Xi 0 : i 1,5

Solución:

1 0 1 0 0
C = (3,5) A, I 0 2 0 1 0
3 0 0 0 1

152
 4 x3
x1
b 12 ; x ; xS x4
x2
18 x5

Iteración 0:

X3 1 0 0
1
xB X4 B 0 1 0 B
X5 0 0 1
4 1 0 0 4 4
b 12 xB 0 1 0 12 12
18 0 0 1 18 18
4
CB 0 0 0 Z 0 0 0 12 0
18

Iteración 1:
x3 1 0 0 1 0 0
1
xB x2 B 0 2 0 B 0 1/2 0
x5 0 2 1 0 -1 1
x3 1 0 0 4 4
xB x2 0 1/2 0 12 6
x5 0 -1 1 18 6
4
Z 0 5 0 6 30
6

Iteración 2:
x3 1 1/ 3 1/ 3 4 2
xB x2 0 1/ 2 0 12 6
x1 0 1/ 3 1/ 3 18 2
CB 0 5 3
2
Z 0 5 3 6 36 Z 36
2

Ejercicio en la iteración 2:

153
 1 1/ 3 1/ 3 1 0 0 0
1
B A 0 1/ 2 0 0 2 0 1
0 1/ 3 1/ 3 3 2 1 0
1 1/3 1/ 3
1
CB B 0 5 3 0 1/2 0 0 3/ 2 1
0 - 1/3 1/ 3
0 0
1
CB B A C 0 5 3 0 1 3 3 0 0
1 0

Z
1 0 0 0 3/ 2 1 X1 36
0 0 0 1 1/ 3 1/ 3 X 2 2
0 0 1 0 1/ 2 0 X3 6
0 1 0 0 1/ 3 1/ 3 X4 2
X5

Z 36

Método Alternativo:

Como B (y por tanto B-1) cambian tan poco de una iteración a otra, resulta más
eficiente obtener:

BN1 EBA1

BN1 : matriz nueva de B -1

B A1 : matriz de B -1 de la iteración anterior
E : matriz identidad, excepto su m - ésima columna reemplazad a por el vector.
a'
n1 ik ; Si i r
n2 a'
n ; donde rk
 i 1
; Si i r
nm a'
rk

xK : Variable que entra a la base

a ik : Coeficiente de x K en la ecuación i actual para i 1,2,, m
r : Número de la ecuación que tiene la variable básica que sale.

154
Ejemplo:
Iteración 1
Z x1 x2 x3 x4 x5
1 -3 -5 0 0 0 0
x3 0 1 0 1 1 0 4
x4 0 0 2 0 0 0 12
x5 0 3 2 0 0 1 18

X3
xB X4
X5
0 1 0 0
1/ 2 E 0 1/2 0
1 0 -1 1
1 0 0 1 0 0 1 0 0
1
B N 0 1/ 2 0 0 1 0 0 1/ 2 0
0 1 1 0 0 1 0 1 1

1 0 0 4 4
1
xB B b 0 1 / 2 0 12 6
0 1 1 18 6
1 0 0 1 -
1
C B B ANB C NB 0,5,0 0 1 / 2 0 0 - 3, 3,
0 1 1 3 -
1 0 0
1
CB B 0,5,0 0 1 / 2 0 0,5 / 2,0
0 1 1

Iteración 2:
Z x1 x2 x3 x4 x5
1 -3 - 0 5/2 0
x3 0 1 - 1 0 0 4
x2 0 0 - 0 1/2 0 6
x5 0 3 - 0 -1 1 6

155
 1 0 1/ 3 1 0 0 1 1/ 3 1/ 3
1
B N 0 1 0 0 1/ 2 0 0 1/ 2 0
0 0 1/ 3 0 1 1 0 1/ 3 1/ 3
1/ 3 1/ 3
1
CB B 0,5,3 1/ 2 0 ,3 / 2,1
1/ 3 1/ 3
1 1/ 3 1/ 3 4 2
1
xB B b 0 1/ 2 0 12 6
0 1/ 3 1/ 3 18 2
2
1
Z CB B B 0,5,3 6 36
2

Z x1 x2 x3 x4 x5
1 - - - 3/2 1 36
x3 0 - - 1 1/3 -1/3 2
x2 0 - - 0 ½ 0 6
x1 0 - - 0 -1/3 1/3 2
Las soluciones son:
X 1 12 u X2 6 u Z $132(um)

156