INVESTIGACION OPERATIVA

INTRODUCION A LA INVESTIGACION DE OPERACIONES

Como toda disciplina en desarrollo, la investigación de operaciones ha ido

evolucionando no sólo en sus técnicas y aplicaciones sino en la forma como la
conceptualizan los diferentes autores, en la actualidad no existe solamente una
definición sino muchas, algunas demasiado generales, otras demasiado engañosas,
aquí seleccionamos dos de las mas aceptadas y representativas.

LA DEFINICIÓN DE CHURCHMAN, ACKOFF Y ARNOFF: LA INVESTIGACIÓN DE

OPERACIONES ES LA APLICACIÓN, POR GRUPOS INTERDISCIPLINARIOS,
DEL MÉTODO CIENTÍFICO A PROBLEMAS RELACIONADOS CON EL CONTROL
DE LAS ORGANIZACIONES O SISTEMAS (HOMBRE-MÁQUINA), A FIN DE QUE
SE PRODUZCAN SOLUCIONES QUE MEJOR SIRVAN A LOS OBJETIVOS DE LA
ORGANIZACIÓN.

De ésta definición se pueden destacar los siguientes conceptos:

1. Una organización es un sistema formado por componentes que se interaccionan,

unas de estas interacciones pueden ser controladas y otras no.
2. En un sistema la información es una parte fundamental, ya que entre las
componentes fluye información que ocasiona la interacción entre ellas. También
dentro de la estructura de los sistemas se encuentran recursos que generan
interacciones. Los objetivos de la organización se refieren a la eficacia y eficiencia
con que las componentes pueden controlarse, el control es un mecanismo de
autocorrección del sistema que permite evaluar los resultados en términos de los
objetivos establecidos.
3. La complejidad de los problemas que se presentan en las organizaciones ya no
encajan en una sola disciplina del conocimiento, se han convertido en
multidisciplinario por lo cual para su análisis y solución se requieren grupos
compuestos por especialistas de diferentes áreas del conocimiento que logran
comunicarse con un lenguaje común.
4. La investigación de operaciones es la aplicación de la metodología científica a
través modelos matemáticos, primero para representar al problema y luego para
resolverlo. La definición de la sociedad de investigación de operaciones de la Gran
Bretaña es la siguiente:
La investigación de operaciones es el ataque de la ciencia moderna a los
complejos problemas que surgen en la dirección y en la administración de grandes
sistemas de hombres, máquinas, materiales y dinero, en la industria, en los
negocios, en el gobierno y en la defensa. Su actitud diferencial consiste en
desarrollar un modelo científico del sistema tal, que incorpore valoraciones de
factores como el azar y el riesgo y mediante el cual se predigan y comparen los
resultados de decisiones, estrategias o controles alternativos. Su propósito es el de
ayudar a la gerencia a determinar científicamente sus políticas y acciones.

1
 INVESTIGACION OPERATIVA

ENFOQUE DE LA INVESTIGACIÓN DE OPERACIONES:

la parte innovadora de la IO es sin duda alguna su enfoque modelístico, producto de

sus creadores aunado a la presión de supervivencia de la guerra o la sinergía
generada al combinarse diferentes disciplinas, una descripción del enfoque es la
siguiente. (Ver la figura 11).

1. Se define el sistema real en donde se presenta el problema. Dentro del sistema

interactuan normalmente un gran numero de variables.
2. Se seleccionan las variables que norman la conducta o el estado actual del
sistema, llamadas variables relevantes, con las cuales se define un sistema
asumido del sistema real.
3. Se construye un modelo cuantitativo del sistema asumido, identificando y
simplificando las relaciones entre las variables relevantes mediante las utilización
de funciones matemáticas.
4. Se obtiene la solución al modelo cuantitativo mediante la aplicación de una o mas
de las técnicas desarrolladas por la IO.
5. Se adapta e imprime la máxima realidad posible a la solución teórica del problema
real obtenida en el punto 4, mediante la consideración de factores cualitativos o no
cuantificables, los cuales no pudieron incluirse en el modelo. Además se ajusta los
detalles finales vía el juicio y la experiencia del tomador de decisiones.
6. Se implanta la solución en el sistema real.

2
 INVESTIGACION OPERATIVA

METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES

DEFINICIÓN DEL PROBLEMA Y RECOLECCIÓN DE DATOS

La mayor parte de los problemas prácticos con los que se enfrenta el equipo IO están
descritos inicialmente de una manera vaga. Por consiguiente, la primera actividad que
se debe realizar es el estudio del sistema relevante y el desarrollo de un resumen bien
definido del problema que se va a analizar. Esto incluye determinar los objetivos
apropiados, las restricciones sobre lo que se puede hacer, las interrelaciones del área
bajo estudio con otras áreas de la organización, los diferentes cursos de acción
posibles, los límites de tiempo para tomar una decisión, etc. Este proceso de definir el
problema es crucial ya que afectará en forma significativa la relevancia de las
conclusiones del estudio. ¡Es difícil extraer una respuesta "correcta" a partir de un
problema "equivocado"!

Por su naturaleza, la investigación de operaciones se encarga del bienestar de toda la

organización, no sólo de algunos de sus componentes. Un estudio de IO busca
soluciones óptimas globales y no soluciones subóptimas aunque sean lo mejor para
uno de los componente. Entonces, idealmente, los objetivos que se formulan debe
coincidir con los de toda la organización. Sin embargo, esto no siempre es
conveniente. Muchos problemas interesan nada más a una parte de la organización,
de manera que el análisis sería innecesariamente besado si los objetivos fueran muy
generales y si se prestara atención especial a todos los efectos secundarios sobre el
resto de la organización. En lugar de ello, los objetivos usados en un estudio deben
ser tan específicos como sea posible, siempre y cuando contemplen las metas
principales del tomador de decisiones y mantengan un nivel razonable de consistencia
con los objetivos de los altos niveles.

Las condiciones fundamentales para que exista un problema es que se establezca

una diferencia entre lo que es (situación actual) y lo que debe ser (situación deseada u
objetivo) y además exista cuando menos una forma de eliminar o disminuir esa
diferencia. Los componentes de un problema son: a) el tomador de decisiones o
ejecutivo; b) los objetivos de la organización; c) el sistema o ambiente en el que se
sitúa el problema; d) Los cursos de acción alternativos que se pueden tomar para
resolverlo.

Para formular un problema se requiere; a) identificar las componentes y variables

controlables y no controlables del sistema; b) identificar los posibles cursos de acción,
determinados por las componentes controlables; c) definir el marco de referencia dado
por las componentes no controlables; d) definir los objetivos que se busca alcanzar y
clasificarlos por orden de importancia; e) identificar las interpelaciones importantes
entre las diferentes partes del sistema y encontrar las restricciones que existen.

FORMULACIÓN DE UN MODELO MATEMÁTICO

3
 INVESTIGACION OPERATIVA

Una vez definido el problema del tomador de decisiones, la siguiente etapa consiste
en reformularlo de manera conveniente para su análisis. La forma convencional en
que la investigación de operaciones realiza esto es construyendo un modelo
matemático que represente la esencia del problema. Antes de analizar como formular
los modelos de este tipo, se explorará la naturaleza general de los modelos y, en
particular, la de los modelos matemáticos.

El modelo matemático está constituido por relaciones matemáticas (ecuaciones y

desigualdades) establecidas en términos de variables, que representa la esencia el
problema que se pretende solucionar.

Para construir un modelo es necesario primero definir las variables en función de las
cuales será establecido. Luego, se procede a determinar matemáticamente cada una
de las dos partes que constituyen un modelo: a) la medida de efectividad que permite
conocer el nivel de logro de los objetivos y generalmente es una función (ecuación)
llamada función objetivo; b) las limitantes del problema llamadas restricciones que son
un conjunto de igualdades o desigualdades que constituyen las barreras y obstáculos
para la consecución del objetivo.

Un modelo siempre debe ser menos complejo que el problema real, es una
aproximación abstracta de la realidad con consideraciones y simplificaciones que
hacen más manejable el problema y permiten evaluar eficientemente las alternativas
de solución.

Los modelos matemáticos tienen muchas ventajas sobre una descripción verbal del
problema. Una ventaja obvia es que el modelo matemático describe un problema en
forma mucho más concisa. Esto tiende a hacer que toda la estructura del problema
sea más comprensible y ayude a revelar las relaciones importantes entre causa y
efecto. De esta manera, indica con más claridad que datos adicionales son
importantes para el análisis. También facilita simultáneamente el manejo del problema
en su totalidad y el estudio de todas sus interpelaciones. Por último, un modelo
matemático forma un puente para poder emplear técnicas matemáticas y
computadoras de alto poder, para analizar el problema. Sin duda, existe una amplia
disponibilidad de paquetes de software para muchos tipos de modelos matemáticos,
para micro y minicomputadoras.

Por otro lado, existen obstáculos que deben evitarse al usar modelos matemáticos. Un
modelo es, necesariamente, una idealización abstracta del problema, por lo que casi
siempre se requieren aproximaciones y suposiciones de simplificación si se quiere que
el modelo sea manejable (susceptible de ser resuelto). Por lo tanto, debe tenerse
cuidado de que el modelo sea siempre una representación válida del problema. El
criterio apropiado para juzgar la validez de un modelo es el hecho de si predice o no
con suficiente exactitud los efectos relativos de los diferentes cursos de acción, para
poder tomar una decisión que tenga sentido. En consecuencia, no es necesario incluir
detalles sin importancia o factores que tienen aproximadamente el mismo efecto sobre
todas las opciones. Ni siquiera es necesario que la magnitud absoluta de la medida de
efectividad sea aproximadamente correcta para las diferentes alternativas, siempre
que sus valores relativos (es decir, las diferencias entre sus valores) sean bastante

4
 INVESTIGACION OPERATIVA

preciso. Entonces, todo lo que se requiere es que exista una alta correlación entre la
predicción del modelo y lo que ocurre en la vida real. Para asegurar que este requisito
se cumpla, es importante hacer un número considerable de pruebas del modelo y las
modificaciones consecuentes. Aunque esta fase de pruebas se haya colocado
después en el orden del libro, gran parte del trabajo de validación del modelo se lleva
a cabo durante la etapa de construcción para que sirva de guía en la obtención del
modelo matemático.

OBTENCIÓN DE UNA SOLUCIÓN A PARTIR DEL MODELO

Resolver un modelo consiste en encontrar los valores de las variables dependientes,

asociadas a las componentes controlables del sistema con el propósito de optimizar, si
es posible, o cuando menos mejorar la eficiencia o la efectividad del sistema dentro
del marco de referencia que fijan los objetivos y las restricciones del problema.

La selección del método de solución depende de las características del modelo. Los
procedimientos de solución pueden ser clasificados en tres tipos: a) analíticos, que
utilizan procesos de deducción matemática; b) numéricos, que son de carácter
inductivo y funcionan en base a operaciones de prueba y error; c) simulación, que
utiliza métodos que imitan o, emulan al sistema real, en base a un modelo.

Muchos de los procedimientos de solución tienen la característica de ser iterativos, es

decir buscan la solución en base a la repetición de la misma regla analítica hasta
llegar a ella, si la hay, o cuando menos a una aproximación.

PRUEBA DEL MODELO

El desarrollo de un modelo matemático grande es análogo en algunos aspectos al

desarrollo de un programa de computadora grande. Cuando se completa la primera
versión, es inevitable que contenga muchas fallas. El programa debe probarse de
manera exhaustiva para tratar de encontrar y corregir tantos problemas como sea
posible. Eventualmente, después de una larga serie de programas mejorados, el
programador (o equipo de programación) concluye que el actual da, en general,
resultados razonablemente válidos. Aunque sin duda quedarán algunas fallas ocultas
en el programa (y quizá nunca se detecten, se habrán eliminado suficientes problemas
importantes como para que sea confiable utilizarlo.

De manera similar, es inevitable que la primera versión de un modelo matemático

grande tenga muchas fallas. Sin duda, algunos factores o interpelaciones relevantes
no se incorporaron al modelo y algunos parámetros no se estimaron correctamente.
Esto no se puede eludir dada la dificultad de la comunicación y la compresión de todos
los aspectos y sutilezas de un problema operacional complejo, así como la dificultad
de recolectar datos confiables. Por lo tanto, antes de usar el modelo debe probarse
exhaustivamente para intentar identificar y corregir todas las fallas que se pueda. Con
el tiempo, después de una larga serie de modelos mejorados, el equipo de IO
concluye que el modelo actual produce resultados

5
 INVESTIGACION OPERATIVA

razonablemente válidos. Aunque sin duda quedarán algunos problemas menores

ocultos en el modelo (y quizá nunca se detecten), las fallas importantes se habrán
eliminado de manera que ahora es confiable usar el modelo. Este proceso de prueba
y mejoramiento de un modelo para incrementar su validez se conoce como
validación del modelo.

Debido a que el equipo de IO puede pasar meses desarrollando todas las piezas
detalladas del modelo, es sencillo "no ver el bosque por buscar los árboles". Entonces,
después de completar los detalles ("los árboles") de la versión inicial del modelo, una
buena manera de comenzar las pruebas es observarlo en forma global ("el bosque")
para verificar los errores u omisiones obvias. El grupo que hace esta revisión debe, de
preferencia, incluir por lo menos a una persona que no haya participado en la
formulación. Al examinar de nuevo la formulación del problema y comprarla con el
modelo pueden descubrirse este tipo de errores. También es útil asegurarse de que
todas las expresiones matemáticas sean consistentes en las dimensiones de las
unidades que emplean. Además, puede obtenerse un mejor conocimiento de la
validez del modelo variando los valores de los parámetros de entrada y/o de las
variables de decisión, y comprobando que los resultados del modelo se comporten de
una manera factible. Con frecuencia, esto es especialmente revelador cuando se
asignan a los parámetros o a las variables valores extremos cercanos a su máximo o
a su mínimo.

Un enfoque más sistemático para la prueba del modelo es emplear una prueba
retrospectiva. Cuando es aplicable, esta prueba utiliza datos históricos y reconstruye
el pasado para determinar si el modelo y la solución resultante hubieran tenido un
buen desempeño, de haberse usado. La comparación de la efectividad de este
desempeño hipotético con lo que en realidad ocurrió, indica si el uso del modelo tiende
a dar mejoras significativas sobre la práctica actual. Puede también indicar áreas en
las que el modelo tiene fallas y requiere modificaciones. Lo que es más, el emplear las
alternativas de solución y estimar sus desempeños históricos hipotéticos, se pueden
reunir evidencias en cuanto a lo bien que el modelo predice los efectos relativos de los
diferentes cursos de acción.

Cuando se determina que el modelo y la solución no son válidos, es necesario iniciar

nuevamente el proceso revisando cada una de las fases de la metodología de la
investigación de operaciones.

ESTABLECIMIENTO DE CONTROLES SOBRE LA SOLUCION

Una solución establecida como válida para un problema, permanece como tal siempre
y cuando las condiciones del problema tales como: las variables no controlables, los
parámetros, las relaciones, etc., no cambien significativamente. Esta situación

se vuelve más factible cuando algunos de los parámetros fueron estimados

aproximadamente. Por lo anterior, es necesario generar información adicional sobre el
comportamiento de la solución debido a cambios en los parámetros del modelo.

6
 INVESTIGACION OPERATIVA

usualmente esto se conoce como análisis de sensibilidad. En pocas palabras, esta

fase consiste en determinar los rangos de variación de los parámetros dentro de los
cuales no cambia la solución del problema.

IMPLANTACION DE LA SOLUCION

El paso final se inicia con el proceso de "vender" los hallazgos que se hicieron a lo
largo del proceso a los ejecutivos o tomadores de decisiones. Una vez superado éste
obstáculo, se debe traducir la solución encontrada a instrucciones y operaciones
comprensibles para los individuos que intervienen en la operación y administración del
sistema. La etapa de implantación de una solución se simplifica en gran medida
cuando se ha propiciado la participación de todos los involucrados en el problema en
cada fase de la metodología. Preparación para la aplicación del modelo

Esta etapa es crítica, ya que es aquí, y sólo aquí, donde se cosecharán los beneficios
del estudio. Por lo tanto, es importante que el equipo de IO participe, tanto para
asegurar que las soluciones del modelo se traduzcan con exactitud a un
procedimiento operativo, como para corregir cualquier defecto en la solución que salga
a la luz en este momento.

El éxito de la puesta en práctica depende en gran parte del apoyo que proporcionen
tanto la alta administración como la gerencia operativa. Es más probable que el equipo
de IO obtenga este apoyo si ha mantenido a la administración bien informada y ha
fomentado la guía de la gerencia durante el estudio. La buena comunicación ayuda a
asegurar que el estudio logre lo que la administración quiere y por lo tanto merezca
llevarse a la práctica. También proporciona a la administración el sentimiento de que
el estudio es suyo y esto facilita el apoyo para la implantación.

La etapa de implantación incluye varios pasos. Primero, el equipo de investigación de

operaciones de una cuidadosa explicación a la gerencia operativa sobre el nuevo
sistema que se va a adoptar y su relación con la realidad operativa. En seguida, estos
dos grupos comparten la responsabilidad de desarrollar los procedimientos requeridos
para poner este sistema en operación. La gerencia operativa se encarga después de
dar una capacitación detallada al personal que participa, y se inicia entonces el nuevo
curso de acción. Si tiene éxito, el nuevo sistema se podrá emplear durante algunos
años. Con esto en mente, el equipo de IO supervisa la experiencia inicial con la acción
tomada para identificar cualquier modificación que tenga que hacerse en el futuro.

A la culminación del estudio, es apropiado que el equipo de investigación de

operaciones documento su metodología con suficiente claridad y detalle para que el
trabajo sea reproducible. Poder obtener una réplica debe ser parte del código de ética
profesional del investigador de operaciones. Esta condición es crucial especialmente
cuando se estudian políticas gubernamentales en controversia.

7
 INVESTIGACION OPERATIVA

LOS MODELOS EN LA INVESTIGACIÓN DE OPERACIONES

Un modelo es una representación ideal de un sistema real y de la forma como opera o

funciona.

El objetivo de un modelo es analizar el comportamiento del sistema, o bien predecir su

comportamiento futuro. Se hacen las suposiciones y restricciones necesarias para
representar las porciones más relevantes del mismo.

Un modelo de decisión debe considerarse como un vehículo para resumir un

problema de decisión, en forma tal de que haga posible la identificación y evaluación
sistemática de todas las alternativas de decisión del problema.

CLASIFICACIÓN DE MODELOS

a) Modelo Determinanticos: Cuando se conoce los datos de manera puntual y la

forma del resultado, no hay de incertidumbre. Es decir, todos los datos son
conocidos. Se aplica a los siguientes tipos de problemas de: Programación lineal,
programación entera, programación no lineal, teoría de redes, transporte, de
asignación, programación por metas, teoría de inventarios, etc.
b) Modelo Probabilístico o Estocástico: Cuando no se conoce el resultado
esperado, sino su probabilidad y existe por lo tanto incertidumbre. Se aplica a los
siguientes tipos de problemas, como: Cadenas de Markov, teoría de juegos, líneas
de espera, inventarios con demanda probabilística, etc.

MODELO MATEMÁTICO

Un modelo matemático es producto de la abstracción de un sistema real, eliminando

las complejidades y haciendo suposiciones pertinentes; se aplica una técnica
matemática y se obtiene una representación simbólica del mismo.

Un modelo matemático consta al menos de tres elementos o condiciones básicos:

Variables de decisión y parámetros

Las variables de decisión son incógnitas que deben ser determinadas a partir de la
solución del modelo. Los parámetros representan los valores conocidos del sistema o
bien que se pueden controlar.

Las variables de decisión se representan por: X1, X2, X3,…, Xn ó Xi , i = 1, 2, 3, …, n

Función Objetivo

La función objetivo es una relación matemática entre las variables de decisión,

parámetros y una magnitud que representa el objetivo o producto del sistema. Es la

8
 INVESTIGACION OPERATIVA

medición de la efectividad en función de las variables. Determina lo que se va

optimizar (Maximizar o Minimizar).

Por ejemplo, si el objetivo del sistema es minimizar los costos de operación, la función
objetivo debe expresar la relación entre el costo y las variables de decisión.

La solución ÓPTIMA se obtiene cuando el valor del costo sea mínimo; para un
conjunto de valores factibles de las variables. Es decir, hay que determinar las
variables x1, x2, x3,..., xn que optimicen el valor de Z = f(x1, x2, x3,..., xn) sujeto a las
restricciones de la forma

g(x1, x2, x3,..., xn) <-b.

Donde:x1, x2, x3,..., xn son las variables de decisión;

Z es la función objetivo,

f es una función matemática.

Restricciones

Las restricciones son relaciones entre las variables de decisión y magnitudes que dan
sentido a la solución del problema y las acotan a valores factibles.

Las restricciones del modelo limitan el valor de las variables de decisión. Son los
recursos disponibles limitados. Incluye la Restricción de No Negatividad de las
Variables de decisión, o sea: Xi ≥ 0.

Por ejemplo, si una de las variables de decisión representa el número de empleados

de un taller, es evidente que el valor de esa variable no puede ser negativo. O
también, si una de las variables es la cantidad de mesas a fabricar, su valor solamente
podrá ser igual a 0 (cero) o mayor que cero, o sea positivo.

ESPACIO EUCLIDIANO

Espacio bidimensional o tridimensional en el que se cumplen los axiomas de Euclides.

También llamado espacio cartesiano.

 Por dos puntos diferentes sólo se puede trazar una única línea recta.
 Todo segmento rectilíneo se puede prolongar indefinidamente.
 Con un centro y un radio dado sólo se puede trazar una única circunferencia.
 Todos los ángulos rectos son iguales.

Si una recta corta a otras dos formando a un lado ángulos internos, y la suma de estos
es menor que dos rectos, las dos rectas prolongadas indefinidamente se encontrarán
de ese lado.

9
 INVESTIGACION OPERATIVA

VECTORES LINEALMENTE INDEPENDIENTES

Geométricamente, dos vectores son independientes si no tienen la misma dirección

(con sentidos idénticos u opuestos). Tres vectores son independientes si y solo si no
están contenidos en el mismo plano vectorial, o sea si ninguno de ellos es una
combinación lineal de los otros dos (en cuyo caso estaría en el plano generado por
estos vectores) en otras palabras este debe generar un volumen. El espacio generado
por un sistema de vectores es el conjunto de todas las combinaciones lineales de
estos vectores.

Determinante

El espacio generado por un sistema de vectores es el conjunto de todas las

combinaciones lineales de estos vectores. Utilizado comúnmente para dar como
resultado a áreas o volúmenes

Conjunto convexo

En otras palabras, en un conjunto convexo se puede ir de cualquier punto a cualquier

otro en vía recta, sin salir del mismo.

Conjunto Convexo Conjunto No Convexo

10
 INVESTIGACION OPERATIVA

PROGRAMACION MATEMATICA

PROGRAMACION LINEAL

Definición: Se entiende por P. Lineal a:

Maximizar o Minimizar Optimiza: Z=CX

Sujeto a:

Restricciones AX ≤ b

X≥0 Condiciones de no negatividad

Donde la función lineal Z se llama Función Objetivo (F.O)

DIVERSAS FORMAS DE REPRESENTACION DEL MODELO DE

PROGRAMACION LINEAL

Forma Canónica:

Es forma canónica si el objetivo Es MAXIMIZAR – restricciones de forma “menor o

igual que”

[]
x1
x2
Opt Z=(C 1 , C 2 , … . , Cn )
⋮
xn

Vector de precios o Costos Unitarios

Sujeta a:

Vector de
disponibilidad
de recursos

11
 INVESTIGACION OPERATIVA

Matriz de coeficientes Tecnológicos

[ ][]
x1 0
x2 0
≥ Vector columna de ceros, NO negatividad
⋮ ⋮
xn 0

Otra forma:
n

∑ C i xi
i=1

n
opt Z=∑ aij x i ≤b i ; j=1 ; n
i =1

x i ≥ 0 , i=1 ; m

Forma Estandarizada:

Es forma estandarizada si el objetivo es MAXIMIZAR – restricciones de forma “igual

que”

Max Z=Cx

Sa: Ax=b

x≥0

Ejemplo:

Max Z=7 x 1 +9 x 2 + x3

S.a.

3 x 1+ x 2 +6 x 3=100

x 1++ 8 x3 =60

4 x1 +2 x 2+ x 3 =40

x1 , x2 , x3 ≥ 0

12
 INVESTIGACION OPERATIVA

Forma Mixta:

Es forma mixta si el obj. Es MAXIMIZAR o MINIMIZAR – restricciones de forma

“igual que o menor “igual que” ó “mayor o igual que”

Ejemplo:

Max Z=4 x 1 +7 x 2

6 x 1+ x2 ≤ 10

x 1+ 20 x 2 ≥200

x 1 , x 2 ,≥ 0

TRANSFORMACIONES DE UN PROGRAMA LINEAL DE UNA FORMA A OTRA

Proposición: Un P. Lineal expresado en forma estándar o mixta se puede

transformar a la forma canónica y viceversa.

Reglas:

Max. Cx Min. (- Cx)

Min. Cx Max. (-CX)

Ejemplo:

Min . Z=16 x 1−5 x 2 es equivalente a

Max . (−Z )=−16 x 1 +5 x 2

Regla 2:

Ax ≤ b es equivalente a:− Ax ≥−b

Ax ≥ b ≡−Ax ≤−b

Ejemplo:

3 x 1+ 4 x 2−3 x 3 ≤ 1000

13
 INVESTIGACION OPERATIVA

−3 x 1−4 x 2 +3 x 3 ≥−1000

Regla 3:

Ax=b ; se descompone como :

Ax ≤ b ˄ Ax ≥ b

Ejemplo:

14 x 1−3 x 2=7 ; es equivalente a :

14 x 1−3 x 2 ≤ 7 ˄14 x 1−3 x 2 ≥ 7

Regla 4. AX  b puede convertirse en igualdad mediante la adición de un vector Y,

llamado de Holgura.

[ ][]
y1 0
y2 0
y= ≥
⋮ ⋮
yn 0

Regla 5: AX  b puede convertirse en igualdad por la resta de un vector Z, llamado

Superfluo.

[ ][]
z1 0
z2 0
Z= ≥
⋮ ⋮
zn 0

Ejemplos:

Ejemplo 1:

14 x 1−3 x 2 ≤ 10

12 x1 + 4 x 2 ≤ 12

es equivalente a

14 x 1−3 x 2+ x3 =10

12 x1 + 4 x 2+ x 4 =12

x3 ≥ 0 , x4 ≥ 0

donde el vector de holgura es :

14
 INVESTIGACION OPERATIVA

[ ][]
x3 0
≥
x4 0

Ejemplo 2:

16 x 1−8 x 2 ≥ 5

7 x 1+ 3 x 2 ≥10

es equivalente a

16 x 1−8 x 2−x 3=5

7 x 1+ 3 x 2−x 4 =10

x3 ≥ 0 , x4 ≥ 0

donde el vector superfluo es :

[ ][]
x3 0
≥
x4 0

Ejemplo 3: Expresar el siguiente P.L en forma canónica:

Max Z=4 x 1 +3 x2

S.a.

x 1+ 3 x 2 ≥10

2 x1 +6 x 2=20

x 1 , x 2 ,≥ 0

Solución:

(1° restricción):
−x 1−3 x 2 ≤−10

(2° restricción):

2 x1 +6 x 2 ≤20

2 x1 +6 x 2 ≥20

Deducido a:

2 x1 +6 x 2 ≤20

15
 INVESTIGACION OPERATIVA

−2 x 1−6 x 2 ≤−20

Si AX = b Se descompone como: AX  b  –AX  –b

Regla 6: (Condiciones de No negatividad)

Una variable no restringida, o sea aquella que puede tomar toda clase de valores +,
0 y -, puede escribirse como la diferencia de dos variables no–negativas.

Ejemplo:

Expresar el siguiente programa en forma canónica.

Max Z=3 x 1 +2 x2

S.a.

x 1+ x2 ≤100

4 x1 +7 x 2 ≤ 300

x 1 , ≥ 0 ; x 2 sin restriccion

Solución:
, ,,
x 2=x 2−x 2 ≥ 0

Entonces el problema puede darse:

, ,,
Máx. Z = 3 x 1+2 x 2−2 x 2

, ,,
x 1+ x2 −x2 ≤ 100
, ,,
4 x1 +7 x 2−7 x 2 ≤300
, ,,
x 1 , x 2 , x 2 ≥0

Proposición: Transformación de la forma canónica a la estandarizada.

Una restricción del tipo “menor o igual que” como se indicó anteriormente puede
ser transformada en una expresión de tipo “igual que” agregando una variable no–
negativa al primer miembro. Esta variable se llama variable de Holgura.

a i1 x 1+ ai 2 x 2 +…+ a¿ x n ≤ bi

16
 INVESTIGACION OPERATIVA

a i1 x 1+ ai 2 x 2 +…+ a¿ x n+ a¿+1 x n +1=bi

Nota: El recurso b toma otro valor si la variable de holgura no es cero.

Ejemplo:

Min Z=3 x 1−4 x 2+ x 3

S.a.

0.5 x 1+ 2 x 2 ≥3

x 2−x 3=4

x 1 , x 2 ≥ 0 ; x 3 no restringida

Solución:

a) Función Objetivo:
Max h=−Z=−3 x 1 +4 x 2−x 3

b) 1era Restricción:

−0.5 x 1−2 x 2 ≤−3

c) 2da Restricción:

x 2−x 3 ≤ 4 x 2−x 3 ≤ 4

x 2−x 3 ≥ 4−x 2−x 3 ≤−4

Luego se tiene:

Max h=−3 x 1 +4 x2 −x3

S.a.

−0.5 x 1−2 x 2 ≤−3

x 2−x 3 ≤ 4

−x 2+ x3 ≤−4

x 1 , x 2 ≥ 0 ; x 3 irrestricta

17
 INVESTIGACION OPERATIVA

Reemplazando:

x 3=x 4 −x5

Max h=−3 x 1 +4 x2 −(x 4 −x5 )

S.a.

−0.5 x 1−2 x 2 ≤−3

x 2−( x 4−x 5)≤ 4

−x 2+(x ¿ ¿ 4−x 5 )≤−4 ¿

x1 , x2 , x5 , x5 ≥ 0

18
 INVESTIGACION OPERATIVA

METODOS PARA SOLUCIONAR PROGRAMAS LINEALES

MÉTODO ALGEBRAICO:

Forma general de un P.L. Es:

Max Z=C1 x1 +C 2 x 2 +… C n x n +0 x n+1 +0 x n+2 +…+ 0 x n +n

S.a.

a 11 x 1 +a 12 x 2+ …+a1 n x n+ x n +1=b1

a 12 x 1+ a22 x 2 +…+a 2 n x n + x n+2=b2.

a m 1 x 1+ am 2 x2 + …+amn x n+ x n +m=b m

x j ≥ 0 ; j=1 , 2 ,… … … ,n+ m
n
Opt . Z=∑ c1 x 1
i=1

S.a.

Ax ≥ b

x≥0

Variable de Holgura:

Es aquella que se introduce para convertir una restricción bajo el signo “menor o
igual que” en una ecuación.

V.H: xn+1, xn+2,, xn+m

Nivel de Holgura:

• Es el valor general asumido por la variable de holgura Al programa con n

variable y m restricciones se le ha agregado m variables de holgura, una
para cada restricción.

• En un sistema de n+m variables y m ecuaciones, él número de soluciones

básicas se puede obtener de acuerdo con él calculo combinatorio:

(n+m)! (n+m)!
C n+m
m = =
m !(n+m−m)! m! n!

19
 INVESTIGACION OPERATIVA

(n+ m)!
Esto significa que habría que resolver veces el sistema de ecuaciones
m! n !
asignando el valor cero a n variables y hallando en cada caso la solución, para
(n+ m)!
luego elegir la mejor de las soluciones básicas.
m! n !

Ejemplo: solucionar algebraicamente el simple P.L

Max Z=3 x 1 +4 x2

S.a.

x 1+ 2 x 2 ≤1000 … … … … .(1)

3 x 1+2 x 2 ≤ 1800 … … … … … (2)

x 2 ≤ 400 … … … … … … …(3)

x1 , x2 ≥ 0

Solución Algebraica:

Agregando a cada restricción su correspondiente variable de holgura se tiene:

Max Z=3 x 1 +4 x2 +0 x 3 +0 x 4 +0 x 5

S.a.

x 1+ 2 x 2 + x 3+ 0 x 4 +0 x5 =1000 … … … …(1)

3 x 1+2 x 2 +0 x3 + x 4 + 0 x 5 =1800 … … … …(2)

x 2+ 0 x3 +0 x 4 + x 5=400 … … … … … … ..(3)

x j ≥ 0 , j=1 , 5

Para encontrar él número de soluciones básicas aplicamos la fórmula del cálculo

combinatorio:

5 5!
C 3=
2! 3 !

Soluciones básicas:

m=3 ecuaciones

n−m=5−3 variables deben ser cero

20
 INVESTIGACION OPERATIVA

n=5 variables

Si las variables son x1, x2, x3, x4, x5 entonces existen 10 soluciones básicas y
también 10 grupos de 2 variables deben ser cero (variables son básicas).

(1) x1,x2 = 0(2)

(2) x1,x3 = 0(3)

(3) x1,x4 = 0

(4) x1,x5 = 0(5)

(5) x2,x3 = 0(6)

(6) x2,x4 = 0

(7) x2,x5 = 0(8)

(8) x3,x4 = 0(9)

(9) x3,x5 = 0

(10) x4,x5 = 0

En cada una de ellas podemos enumerar también todas las soluciones posibles de
variables básicas.

1) (x3, x4, x5) 2) (x1, x3, x5)

3) (x2, x4, x5) 4) (x1, x3, x4)

5) (x2, x3, x5) 6) (x1, x2, x5)

7) (x2, x3, x4) 8) (x3, x2, x4)

9) (x1, x4, x5) 10) (x1, x2, x3)

 Podemos seleccionar una de estas soluciones, por ejemplo (x3, x4, x5)

x1 = 0 y x2 = 0 entonces:

x3 = 1000

x4 = 1800 z = 0 la solución corresponde al punto (1)

x5 = 400

21
 INVESTIGACION OPERATIVA

Reemplazando:

Max Z=3 ( 0 ) +4 ( 0 ) +0 x 3+ 0 x 4 + 0 x5

S.a.

0+ 0+ x 3+ 0 x 4 + 0 x 5 =1000

0+ 0+0 x3 + x 4 + 0 x 5 =1800

0+ 0 x 3 +0 x 4 + x 5=400

 Si seleccionamos otro juego de variables básicas (x2, x3, x4) x1 = 0 y x5 = 0

entonces:

x2 = 400
x3 = 200 z = 600 la solución corresponde al punto (2)
x4 = 1000

 Si tomamos (x2, x4, x5) y x1 = 0 y x3 = 0 entonces

x2 = 500

x4 = 800 x5 viola la condición de no negatividad

x5 = –100

Aunque z = 2000

Z = 3x1 + 4x2 = 3(0) + 4(500)=2000

Esta solución aunque básica, no representa una solución factible del problema.

 Consideremos solamente, soluciones básicas factibles al buscar la solución

óptima.

 Para (x1, x2, x5) y x3 = 0 y x4 = 0 entonces

x1 = 400

x2 = 300 z = 3x1+4x2+0x5 = 2400

x5 = 100

ALGORITMO ALGEBRAICO

22
 INVESTIGACION OPERATIVA

Método algebraico: Esquema (Maximizaciónón ())

1er Paso: (formulaciónón del problema)

a) Formular en forma precisa la FO.

b) Convertir las inecuaciones en ecuaciones añadiendo las variables de
holgura.

2do Paso: (Diseño del PL)

a) Considere el estado en que se programe solo las variables de holgura es

decir solo para (z=0).

3er Paso: (Revisión del programa general)

a) Identifique la variable que entra al programa, para ello identifique en la FO la

variable con mayor coeficiente positivo si la hay.
b) Determine el máximo nivel de la variable que ingresa al programa, para ello
determine la capacidad limitante.
c) Obtenga las ecuaciones del nuevo programa de la ecuación de la
capacidad limitante, despeje la variable que ingresa al programa y remplace
esta ecuación en las restantes ecuaciones del PL.

4to Paso: (Verificaciónón del Óptimo)

a) Sustituya la ecuación limitante obtenida en el paso (3c) en la FO si todos

los coeficientes son negativos el problema ha sido resuelto y diremos que
la soluciónón es óptima.
b) De otro modo revise el programa haciendo ingresar en el programa la
variable cuyo coeficiente positivo es el mayor.

5to Paso: Repita 3b, 3c y 4 hasta alcanzar el óptimo.

Ejemplo:

1)

Ma x Z=3 x 1 +4 x 2

S.a.

x 1+ 2 x 2 + x 3=1000 … … … … .(1)

3 x 1+2 x 2 + x 4=1800 … … … … …(2)

x 2+ x5 =400 … … … … … … …(3)

x j ≥ 0 , j=1 , 5

23
 INVESTIGACION OPERATIVA

2)

(1) Sea x1 = x2 = 0 entonces z=0

X3 = 1000(1)

X4 = 1800(2)

X5 = 400 (3)

3)

a) z = 3x1 + 4x2

 La variable con mayor coeficiente es x2.

 x2 ingresa al proceso.

b) La capacidad limitante es: Si x2 ingresa al programa entonces

En (1) si x1 = x3 = 02x2 = 1000x2 = 500

En (2) si x1 = x4 = 02x2 = 1800x2 = 900

En (3) si x1 = x5 = 0x2 = 400

c) La capacidad limitante esta en (3) entonces x2 = 400 es la más restrictiva.

4)

En (3) despejamos la variable x2 = 400 – x5 entonces lo remplazamos en (1)

x 1+ 2 ( 400−x 5 ) + x 3=1000

x 1+ 800−2 x 5 + x3 =1000

x 1+ x3 −2 x 2=200

3 x 1+2 ( 400−x 5 ) + x 4 =1800

3 x 1+ 800−2 x 5+ x 4=1800

3 x 1+ x 4 −2 x5 =1000

24
 INVESTIGACION OPERATIVA

NOTA: El máximo número que puede producirse, es el mejor de los 3 valores

calculados, 400; ya que al reemplazar el valor de x2 en alguna de las ecuaciones
(1), (2) o (3) (se viola la condición de no negatividad o la igualdad).

Luego en (2):

En la Función Objetivo:

Z=x 1+ 4 ( 400−x 5 )

Z=3 x1 +1600−4 x 5

Z=3 x1 +1600−4 x 5

Como existe un coeficiente positivo no estamos en lo óptimo, luego tenemos el

nuevo modelo.

Max Z=1600+3 x 1−4 x 5

S.a.

x 2+ x5 =400 … … … … .( 4)

x 1+ x3 −2 x 5=200 … … … … …(5) (n)

3 x 1+ x 4 −2 x5 =200 … … … … … … …(6)

x j ≥ 0 , j=1 , 5

Luego la segunda solución es: x1 = x5 = 0 variables no básicas

x2 = 400

x3 = 200 variables básicas entonces z = 1600

x4 = 1000

La solución básica correspondiente a esta iteración equivale al punto (2) para el

cual x2 = 400 y x1 = 0, según 4a) la solución que se obtenga no es óptima.

5)

Repetir el procedimiento anterior.

2da Iteración

a) El mayor coeficiente positivo en la F.O. de (n) es 3 con respecto a la

variable x1 entonces x1 es la variable que ingresa (Nota: En (4) no hay x1).

25
 INVESTIGACION OPERATIVA

b) Luego en (5) x3 = x5 = 0, entonces x1 = 200 (se toma el menor como

capacidad limitante) en (6) x4 = x5 = 0, entonces x1 = 1000/3 entonces la
capacidad limitante es para x1 = 200 y se obtiene de la ecuación (5).

Luego x1 en (5) x1 = 200 – x3 + 2x5 reemplazamos en (6)

3 ( 200−x3 +2 x 5 ) + x 4−2 x 5=1000

600−3 x 3 +6 x 5 + x 4−2 x 5=1000

−3 x 3+ x 4−4 x 5=400

Luego reemplazamos x1 en la Función objetivo.

Max Z=2200−3 x 3+ 2 x 5

S.a.

x 2+ x5 =400 … … … … .( 7)

x 1+ x3 −2 x 5=200 … … … … …(8)

−3 x 3+ x 4 +4 x 5=400 … … … … … … … (9)

x j ≥ 0 , j=1 , 5

Según el paso 4a) la FO no nos permite alcanzar el óptimo.

 Repetir el proceso en la FO: z = 2200 – 3x3 + 2x5

 Hacemos ingresar la variable x5 que tiene el mayor coeficiente positivo;

De (7) si x2 = entonces x5 = 400

De (8) si x1 = x3 = 0 entonces x5 = –100 (se descarta el valor negativo)

De (9) si x3 = x4 = 0 entonces x5 = 100

La capacidad limitante es para x5 = 100

 Luego despejamos la variable x5 en la ecuación (9).

400 3 1
x 5= + x − x … … … .(∞ )
4 4 3 4 4

 Remplazando () en (7).

26
 INVESTIGACION OPERATIVA

3 1
x 2+ 100+ x3 − x 4=400
4 4

3 1
x 2+ x 3− x 4 =300
4 4

4 x 2+3 x 3−x 4 =1200 … … … … … ..(10)

 Remplazando () en (8).

( 3
4
1
x 1+ x3 −2 100+ x 3− x 4 =200
4 )
2 x1 −x3 + x 4 =800 … … … … … ..(11)

Luego remplazamos x5 en la Función Objetivo.

Como todos los coeficientes de las variables de la F.O. son negativos entonces esta
función nos permite hallar el óptimo; entonces el modelo es:

3 1
Max Z=2400− x − x 4
2 3 2

S.a.

−3 x 3+ 4 x 5 + x 4=400 … … … … . ( 9 ) (se mantiene)

4 x 2+3 x 3−x 4 =1200 … … … … …(10)

2 x1 −x3 + x 4 =800 … … … … … … …(11)

x j ≥ 0 , j=1 , 5

Por lo tanto:

x3 = x4 = 0 en la FO. Son variables de holgura (y están en la función optima),

entonces,

En (9) 4x5 = 400x5 = 100

En (10) 4x2 =1200x2 = 300

En (11) 2x1 = 800x1 = 400

Por lo tanto z = 2400

Respuesta: Se debe producir

27
 INVESTIGACION OPERATIVA

– 400 unidades

– 300 unidades

Para alcanzar una utilidad máxima de $ 2400.

28
 INVESTIGACION OPERATIVA

MÉTODO GEOMETRICO

Ejemplo 1:

Una Compañía Manufacturera fabrica los productos 1 y 2; y es suficientemente

afortunada como para vender todo lo que puede producir actualmente.

Cada producto requiere un tiempo de manufacturación en los 3 departamentos y la

disponibilidad de una cantidad fija de horas–hombre por semana en cada
departamento; tal como se muestra en el cuadro siguiente:

Tiempo de manufacturación

Producto Dpto. A Dpto. b Dpto. c

1 2 1 2

2 2 2 4

H-H disponibles por 160 120 280

semana

La ganancia por cada unidad del producto 1 es S/. 100 y el producto de 2 es

S/.1.50.

El método geométrico consiste en delinear sobre el primer cuadrante (debido a la

condición de no negatividad) la región de soluciones factibles; y luego graficando
sobre ella la función objetivo, se ubica el programa o programas óptimos.

Solución: Sean:

x1 = número de unidades del producto 1

x2 = número de unidades del producto 2

Por lo tanto el Programación Lineal es:

Max Z= x1 +1.5 x 2

S.a.

2 x1 +2 x 2 ≤ 160 … … . (1 )

x 1+ 2 x 2 ≤120 … … . ( 2 )

4 x1 +2 x 2 ≤ 280 … … . ( 3 )

x1 , x2 ≥ 0

29
 INVESTIGACION OPERATIVA

Graficando:

Aplicando los mismos conceptos a la segunda y tercera restricción y superponiendo

las 3 gráficas, tenemos que la zona en la cual se cumplen simultáneamente las tres
restricciones, es la región sombreada que se indica en la figura (5).

Sea z=0, entonces la pendiente de la función es:

30
 INVESTIGACION OPERATIVA

x 2 −1
x 1+ 1.5 x 2=0 ,m= =
x 1 1.5

Por lo tanto, la FO, Z representa una familia de rectas paralelas con pendiente
−1
m= , tal como se muestra en la figura 6.
1.5

Graficando la F.O en la Fig. (5) se obtiene la Fig. (7).

Las líneas discontinuas representan

diferentes valores de la función Z que se
desea maximizar.

31
 INVESTIGACION OPERATIVA

La recta Z=100 y la región sombreada tienen, en este caso, un punto en común, B,

cuyas coordenadas son: x1 = 40; x2 = 40

Este punto es la solución del problema, y el valor óptimo de la F.O es: Z= 100

DEFINICIONES:

Con el propósito de aclarar las definiciones, consideraciones con el siguiente

ejemplo:

Max Z=3 x 1 +4 x2

S.a.

( a ) x 1 +2 x 2 ≤1000

( b ) 3 x 1+ 2 x 2 ≤ 1800

( c ) x2 ≤ 400

x1 , x2 ≥ 0

Gráficamente:

32
 INVESTIGACION OPERATIVA

Región Factible: Es aquella que cumple con todas las restricciones y las
condiciones de no–negatividad.

Para nuestro ejemplo, la región sombreada de la Fig. (8) representa la región

factible; dada que cumple con las condiciones (2) y (3).

Observe que la región factible se caracteriza por ser convexa.

Solución factible: Es cualquier punto situado en la región factible.

Solución Básica: Es aquella que se encuentra en la intersección de rectas o

hiperplanos o en la intersección con los ejes coordenados. Para nuestro Ejemplo,
los puntos 1, 2, 3,...,10 de la Fig. (8) son soluciones básicas. Agregando a la
ecuación (2) las correspondientes variables de holgura se tiene:

Max Z=3 x 1 +4 x2 +0 x 3 +0 x 4 +0 x 5

S.a.

( a ) x 1 +2 x 2 + x 3=1000

( b ) 3 x 1+ 2 x 2 + x 4=1800

33
 INVESTIGACION OPERATIVA

( c ) x2 + x 5=400

x j ≥ 0 ,1 , … … … , 5

En este caso

n= 5 (variables)

m= 3 (restricciones)

Obtenemos una solución básica haciendo (5–3=2) variables iguales a cero.

x 1=0

x 2=0

x 1=0

Variables no basicas

x 2=0

Por lo tanto:

x 2=400 Variables básicas o de holgura,

x 3=200 x 4 =1000

Y así sucesivamente se obtendrían otras soluciones básicas. En los puntos

3,4,...,10.

DIVERSOS TIPOS DE RESTRICCIONES

Restricciones de “mayor o igual” o de límite mínimo.

Ejemplo 2:

Min Z=x 1 +3 x 2

S.a.

6 x 1+ 3 x 2 ≥ 8 … … … .(1)

2 x1 + 9 x 2 ≥… … …..(2)

34
 INVESTIGACION OPERATIVA

x1 , x2 ≥ 0 ,

z=0 z=1.65

Solución punto A:

x1 = 1.35, x2 = 0., Z = S/. 1.65

Restricciones de “igual que”:

Los problemas reales presentan generalmente en forma simultánea restricciones de

límite mínimo o igualdades.

La igualdad, vuelve, al problema muy restrictivo, ya que la solución debe no solo

estar en el campo común a las restricciones, sino, además encontrarse sobre la
línea que representa la igualdad.

Min Z=2 x 1+ 3 x 2

S.a.

x 1+ x2 ≥ 4 … … … … … … .(1)

6 x 1+ 2 x 2=8 … … … … … … .(2)

x 1+ 5 x 2 ≥ 4 … … … … … …. (3)

x 1 ≤ 3 … … … … … … .(4)

x 2 ≤ 3 … … … … … … .(5)

x1 , x2 ≥ 0 ,

35
 INVESTIGACION OPERATIVA

La solución debe encontrarse en el segmento AB, trazando la FO, encontramos que

el punto mínimo esta en B donde: x1 = 8/7, x2 = 4/7, Z = S/. 4

Un Ejemplo Numérico: El Problema del Carpintero

Maximizar :Z =5 x 1 +3 x 2

sujeta a :

2 x1 + x 2 ≤ 40

x 1+ 2 x 2 ≤5

x1 , x2 ≥ 0

36
INVESTIGACION OPERATIVA

37
 INVESTIGACION OPERATIVA

Por ejemplo, en el problema del carpintero, la región factible convexa proporciona

los puntos extremos con las coordenadas que figuran en la siguiente Tabla:

Valor de la Función Objetivo en cada Esquina o Punto Extremo

Coordenadas de los Puntos Función de los
Elecciones del Decisor
Extremos Ingresos Netos
Cantidad de Mesas o Sillas X1, X2 5 X1 + 3 X2
No fabricar ninguna mesa ni
0, 0 0
silla
Fabricar todas la mesas
20, 0 100
posibles
Fabricar todas las sillas
0, 25 75
posibles
Fabricar una combinación de
10, 20 110
productos

Dado que el objetivo es maximizar, de la tabla anterior surge que el valor óptimo es
110, el cual se obtiene si el carpintero sigue la estrategia óptima de X1=10 y X2=20.

38
 INVESTIGACION OPERATIVA

MÉTODO SIMPLEX

ALGORITMO DEL MÉTODO SIMPLEX

Paso 1: Dado cualquier P.L. transfórmese por medio de las reglas de equivalencia
al P.L. canónico.

M ax Z > Cx

S.a.

Ax ≤ b

X≥0

Paso 2: Rescríbase la F.O. de la siguiente manera

Z – Cx = 0

Paso 3: Conviértase todas las desigualdades a igualdades usando variables de

holgura; entonces la forma canónica se convierte en:

Max Z – Cx = 0

Ax + ẋ = b ẋ = vector de variables de holgura

X ≥ 0, ẋ≥0

Escribiendo en forma desarrollada

Z- C1X1 – C2X2 - … CnXn = 0

a11X1 + a12X2 +… + a1nXn + Xn+1 = b1

a21X1 + a22X2 +… + a2nXn + Xn+2 = b2

………………………………………………..

amX1 + am2X2 +… + amnXn + Xn+m = bm

X1 ≥ 0, X2 ≥ 0… Xn≥ 0

Xn+1≥ 0,…, Xn + m≥ 0

39
 INVESTIGACION OPERATIVA

La adición de las variables de holgura crea la primera base B, que resulta de la

matriz identidad. Esto, a su vez, genera el primer punto extremo de la región de
factibilidad

4: Constrúyase una tabla con los coeficientes del P.L.

z x1, x2, ..., xn Xn+1, xn+2, ..., xn+m

1 CBB-1A-C CBB-1 CBXB

aB1
aB2
. 0 B-1A B-1 XB
.
.
aBm

Paso 5: Seleccione como vector de entrada aquel cuya Z j - Cj sea la más negativa.
Si no hay candidato de entrada, es decir que todas las Zj - Cj >=0 para todo j en A,
la solución xB mostrado en la tabla es óptimo. En caso que exista un empate entre
varios vectores, rómpase el empate arbitrariamente.

Paso 6: Una vez seleccionado la columna a j que entrará a la nueva base,

selecciónese el vector de salida ar de base actual usando:

XB Xb
=min{ ¿ Y k > 0}
Yr Yk

Forma desarrollada del tablero Simplex

Z x1, x2, ..., xn Xn+1, xn+2, ..., xn+m

1 Zn+1-Cn+1 Zn+2-Cn+2 ... Zn+m-Cn+m Z0

Z1-C1 Z2-C2 ... Zn-Cn

aB1 0 Y11 Y12 ... Y1n Y1,n+1 Y1,n+2 ... Y1,n+m XB1
aB2 0 Y21 Y22 ... Y2n Y2,n+1 Y2,n+2 ... Y2,n+m XB2
. . ................. ................. .
. . ................. ................. .
. . ................. ................. .
aBm 0 Ym1 Ym2 ... Ymn Ym,n+1 Ym,n+2 ... Ym,n+m XBm

40
 INVESTIGACION OPERATIVA

NOTA:

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

En caso de que exista un empate entre varios vectores candidatos hay que aplicar
las reglas lexicográficas para romper el empate; una decisión arbitraria puede
causar que el proceso cicle continuamente sin alcanzar la solución óptima.

Paso 7: La intersección en el tablero de la columna que entra con la columna que

sale determina el elemento pivot yrj.

Aplíquese operaciones matriciales elementales en el pivot y rj con el objeto de

convertir a la columna aj en el vector unitario er. Es decir, ceros en toda la columna
y uno en la r-ava componente, que resulta ser yrj. Regrese al paso 5.

Por ejemplo:

si la columna seleccionada al entrar a la base es a 2 y la fila a salir es a 7 hágase el

elemento y72 del tablero igual a uno y al resto de componentes de la columna a 2,
ceros (incluyendo a Z2 - C2) mediante el uso de operaciones elementales
matriciales.

Este paso genera una nueva base B, un nuevo punto extremo x B y un nuevo valor
de la F.O (Z).

Operaciones Matriciales Elementales.

Estas operaciones afectan únicamente a las filas de la matriz. Existen tres clases
de operaciones de este tipo:

a) Multiplicar o dividir una fila de una matriz por un escalar diferente de cero.
b) Añadir o restar de una fila el múltiplo de otra.
c) Intercambiar dos filas.

41
 INVESTIGACION OPERATIVA

INICIO

Dado un Condicion de
Programa Optimalidad Sí
Lineal Zj -C j >=0

Transformese por medio de reglas de No

equivalencia a la forma canonica
Max Z=CX Seleccionese como vector de
AX<=b entrada aquel cuyo Zj -C j sea
el mas negativo.
X>=0

Seleccionese el vector de
Re-escribase la FO. de la salida a r de la base actual:
siguiente manera: X Br =min{ X Bk |Y kj >0}
Z-C X=0 Y rj k Y kj .

Conviertese todas las desigualdades en Aplique operaciones matriciales

elementales en el Pivot Yrj con el
igualdades agregando variables de holgura
Max Z-CX=0 objeto de convertir la columna aj
en un vector unitario
AX+X=b
X>=0,X>=0

La solucion XB
Construyase un tablero con
mostrada es Optima.
los coeficientes del PL.
FIN

Ejemplo: Resuelva por el método Simplex el siguiente problema:

El Dueño de una planta produce únicamente dos tipos de cerveza: blanca y

negra. Existen tecnologías bastante diferentes para la elaboración de cada uno de
los tipos de cerveza, obviamente cada tipo de tecnología a un costo diferente el
dueño de la planta no sabe cual deba ser su producción óptima semanal de cada
producto , y por lo tanto se decide a identificar dos variables de decisión.

X1: miles de litros de cerveza blanca a producir en una semana .

X2: miles de litros de cerveza negra a producir en una semana .

El precio al mayoreo de 1000 litros de cerveza blanca es $ 5 000 , mientras que

el precio al mayoreo de 1000 litros de cerveza negra es de $ 3 000.

Un estudio de tiempos y movimientos ha demostrado que para producir mil litros de

cerveza blanca se requiere un total de 3 obreros en el proceso de producción, en
cambio se requiere 5 obreros para producir 1000 litros de cerveza negra,
supongamos que la planta tiene un total de 15 obreros, también se sabe que para
producir 1000 litros de cerveza blanca es de $ 500, mientras que 1000 litros de
cerveza negra le cuesta al dueño $200 su capital no le permite gastar más de
$1000 semanales en la producción de X1, X2.

42
 INVESTIGACION OPERATIVA

¿Cuáles deben ser los niveles de producción semanal de cerveza blanca y cerveza
negra que maximicen el ingreso por concepto de venta semanal?

Solución:

Max z = 5000 x1 + 3000x2

S.a.: 3x1 + 5x2 ≤ 15 (restricción de mando de obra)

5x1 + 2x2 ≤ 10 (restricción de costos de producción) ; x1, x2 ≥ 0

Paso 1:

El Problema lineal es Canónico.

Paso 2:

Generar Z – 5000x1 – 3000x2 = 0

Paso 3: Generar la siguiente estructura:

Max − Z−5000x 1 −3000x2 =0

Sa: 3x1 +5x 2 +x3 =15
5x1 +2x 2 +x 4 =10
x1 ,x 2 ,x 3 ,x 4 ≥0 ; x 3 ,x 4 variables de holgura

x3 = Es la diferencia entre el nº de obreros que se van a utilizar en la producción

óptima y los que hay disponibles.

x4 = Es la diferencia entre el capital que se va a gastar semanalmente en la

producción óptima y el capital disponible.

Paso 4: Tablero:

Z X1 x2 x3 x4 Z0

1 –5000 –3000 0 0

Vectore a3 0 3 5 1 0 15
s
en la a4 0 5 2 0 1 10
base

43
 INVESTIGACION OPERATIVA

B−1 =
[ 10 01 ] , x =[ xx ]=[1510 ] , z =0
B
3

4
0

A=[
5 2]
−1 3 5 −1
B , C B =( z −c , z −c )=(0 , 0),
B 3 3 4 4

C B B−1 A−C=(z 1 −c 1 , z 2−c2 )=(−5000 ,−3000 ), B=(a3 ,a 4 ),

[]
x3

x=
[ ]
xB
xN
=
x4
x1
x2
x
, xN = 1 =
x2
0
0 [ ][]

[]
x3

x=
[ ]xB
xN
x
x1
x2
x
= 4 , xN = 1 = 0
x2 0 [ ][]

Paso 5: Indica que hay que seleccionar todas las Z j - Cj < 0 para toda columna j en
A que no pertenezca a la base actual B. Las únicas columnas que no pertenecen
son a1 y a2. Se debe seleccionar al más negativo de estas Zj - Cj

Zj - Cj = Min {–5000, –3000} = –5000 à entra a1 , j=1

Por lo que la columna a entrar a la nueva base es a 1. Para ver que vector ar debe
salir de la base actual se aplica el paso 6. Los únicos candidatos a salir están dados
por la regla:

XB Xb
=min{ ¿ Y k > 0}
Yr Yk

Sabiendo que j=1 se tiene:

xB
yr 1
r
= min {153 ,105 }=min {5 , 2}=2 ⇒a
k
4 sale de la base a 3 a 4

Sabiendo que el vector a1 es el que debe entrar y a4 el que va salir, el pivot queda
determinado. El pivot en este caso es el elemento y21=5, tal como se muestra

44
 INVESTIGACION OPERATIVA

Z x1 x2 x3 x4 Z0

1 -5000 -3000 0 0 0

Vectores a3 0 3 5 1 0 15
en la Pivot y21=5
base 10
5 2
a4 0 0 1

• Para encontrar la nueva base hay que convertir la columna a1 en una columna
unitaria e2, con un uno en la segunda componente y ceros en el resto de la
columna, incluyendo Zj - Cj. Esto se logra con operaciones matriciales
elementales :

Z x1 x2 x3 x4 Z0

1 0 -1000 0 1000 10000

Vectores a3 0 0 19/ 5 1 -3/5 9

en la columna a1 en una columna unitaria e2
base
1 2/5
a4 0 0 2
1/5

 Se ha terminado una iteración completa del método Simplex. En esta

iteración, el proceso se ha movido de un punto extremo con componentes x 1=0,
x2=0, x3=15 y x4=10, correspondientes a la base B=(a3,a4) y en donde la F.O. es
igual a cero, a otro punto extremo con componentes x1=2, x2=0, x3=9 y x4=0,
correspondiente a la nueva base B=( a3,a1) y a un nuevo valor de la F.O. de
10 000.

 Sin embargo como Z2 - C2=-1000 < 0, es negativo, el valor de la F.O. puede aún
mejorarse. Repitiendo otra iteración del método Simplex, se tiene que a2 entra a
la nueva base y que:

{ }
9 2
xB
yr 2
r
= min 19
5
,
2
5
k

min {1945 , 102 }=1945

k

45
 INVESTIGACION OPERATIVA

Z x1 x2 x3 x4 Z0

1 0 -1000 0 1000 10000

Vectores a3 0 0 19/ 5 1 -3/5 9

en la
Nuevo pivot
base a4 0
1 2/5 0 1/5 2

Z x1 x2 x3 x4 Z0

1 0 0 5000/19 1600/19 235000/19

Vectores A2 0 0 1 5/19 -3/19 45/19

en la
base A1
Columna a2 en una columna unitaria e1
1 0
0 -2/19 25/19 20/19

La nueva solución o punto extremo correspondiente a la nueva base B=(a 2, a1), que
por cierto ya es óptima porque tiene todas las Zj - Cj >= 0, es:

20
X1 = =1.052 miles de botellas de serveza blanca
19

45
X2 = =2.368 miles de botellas de serveza negra
19

X3 = 0 exceso de obreros.

X4 = 0 exceso de capital semanal

235000
Z= =$ 12368.42de utilidad semanal
19

SOLUCIONES ÓPTIMAS NO ACOTADAS

Se tiene el siguiente P.L. en su forma canónica

Max Z =4X1 + 4 X 2
s.a:
-2X1 + 2 X 2≤2
-X1 + 2X2≤4
X1 ≥0,X2 ≥0

46
 INVESTIGACION OPERATIVA

PROPOSICION

Supóngase el problema lineal en forma canónica

Supóngase que en cualquier iteración del método simplex, el vector que entra a la
base es ak. Entonces si todas las Yik  0, i  1,  , m, soluciónes del
P.L es no acotado.

Max Z  CX
s.a : AX  b
X0

Gráficamente:

(1)

(2)

PROPOSICION

Supóngase el problema lineal en forma canónica

Max Z=CX
s. a: AX≤b
X≥0

47
 INVESTIGACION OPERATIVA

Supóngase que en cualquier iteración del método simplex, el vector que entra a la

base es ak. Entonces si todas las

Y ik ≤0, ∀ i=1, ⋯ ,m,
soluciónes del P.L es no acotado.

ALGORITMO

Paso 1. Supóngase un problema lineal en forma canónica.

Max Z  CX
s.a : AX  b
X0

Paso 2. En cualquier Iteración del Método Simplex, el vector que entra a la base es
el ak.

Paso 3. Si todos los Yik son menores que cero para todo i=1-m la solución del P.L.
es no acotado, ir al paso4, caso contrario continuar con el algoritmo del método
simplex.

Paso 4. Fin.

DIAGRAMA DE FLUJO
Inicio
Dado el P. L. en su
forma canónica

Aplicar el algoritmo
del Método simplex

En cualquier iteración del MS el

vector que entra a la base es a k

Todos los (Y ik <0)

no si
para todo i=1-m

Continuar con Imprimir:

Algoritmo del "Solución No
Método Simplex Acotada"

EJEMPLO fin

Resuélvase por el método simplex el siguiente P.L.

Max Z =4X1 +4 X 2
s.a:
-2X1 +2 X 2≤2
-X1 +2X2≤4
X1 ≥0,X2 ≥0
48

Z -4X1 −4 X 2−0 X 3 −0 X 4 =0
-2X1 +2 X 2 +X 3 =2
 Xi≥0, ∀ i=1-4

INVESTIGACION OPERATIVA

Tablero Inicial

Z X1 X2 X3 X4 z
Z=0
1 -4 -4 0 0 0

X3 0 -2 2 1 0 2

X4 0 -1 2 0 1 4 Z=8

Nota:

En la segunda Iteración X3 debe entrar, pero como los Y13 = -1/2 <0 y Y23 = -1<0, y
por lo tanto la regla de selección del vector que debe salir de la base no se puede
llevar a cabo. Nótese también que esa misma condición se encuentra en el tablero
inicial, si en vez de introducir X2 a la base se introduce X 1. Por tal motivo se cumple
el algoritmo dado y el problema tiene solución no acotada.

Se tiene el siguiente tablero que aún no es óptimo y se debe seleccionar el nuevo

vector de entrada que es X3.

Como todos los Yi3 < 0, i=1-2 se concluye que la solución del problema es no
acotado.

SOLUCIONES ÓPTIMAS MULTIPLES

ALGORITMO

Matemáticamente se tiene que si XA es el vector del punto A y XB es el vector del

punto B entonces se define lo siguiente:

X   X A  1   X B   0,1

Es también óptima. La siguiente proposición da las condiciones que permiten

identificar soluciones óptimas múltiples en un tablero del método simplex.

AX  b, X  0

49
 INVESTIGACION OPERATIVA

PROPOSICION

Dado el problema lineal en forma canónica, Máx Z=cX, sujeto a.

Si existe un vector ak que no este en la base cuyo correspondiente z k - ck = 0, y

todas las Yik > 0, i=1, ..., m entonces el programa lineal tiene soluciones óptimas
múltiples y la base es óptima.

Paso1. Dado el problema en forma canónico:

Max Z=CX
s . a: AX≤b
X≥0

Paso2. Aplicar el algoritmo del método simplex al programa lineal.

Paso3. Si existe un vector ak original que no está en la base cuyo correspondiente

Zk-Ck = 0 y todos los Y ik > 0 para todo i=1-m, entonces el problema lineal tiene
soluciones óptimas múltiples y la base es óptima, ir al paso4, caso contrario la
solución encontrada es óptima

[Link]

50
 INVESTIGACION OPERATIVA

DIAGRAMA DE FLUJO

Inicio

Dado el P. L. en su
forma canónica

Aplicar el Método Simplex

Verificar vectores a k
originales

Existe un vector
original que no está en la
no base y su correspondiente si
z k-c k=0 y todos los Y ik
>0,
La solución para todo i=1-m Imprimir:
encontrada es "Soluciónes
óptima Multiples"

fin

EJERCICIO

Resuelva por el método simplex el siguiente P.L.

Max Z =5 X 1 +2 X 2
s.a:
6X1 +10 X 2 ≤30
10X 1 + 4X 2≤20
X1 ≥0,X 2 ≥0

Z - 5 X 1 −2 X 2−0 X 3 −0 X 4 =0 :
6X1 +10 X 2 + X 3 =30
10X1 + 4X 2 + X 4 =20
Xi≥0, ∀ i=1-4

51
 INVESTIGACION OPERATIVA

Primera Iteración

Z X1 X1 X1 X1 z

1 0 0 0 ½ 10

a3 0 0 38/5 1 -6 18

a1 0 1 2/5 0 1/10 2

Tablero Inicial

Z X1 X2 X3 X4 z

1 -5 -2 0 0 0

a3 0 6 10 1 0 30

a4 0 10 4 0 1 20

Como Z2-C2=0 y a2 no está en la base B=( a 3-a1) y todas las Yi2>0, i en B se tiene
una solución óptima múltiple. Sea un punto extremo óptimo el siguiente:

[] []
X1
2
X2 0
X= =
X3 18
X4 0

Da un valor óptimo de Z=10, que se verifica en el tablero anterior en la primera

iteración.

Para ver cuál sería el otro punto extremo se introduce a 2 a la base y queda el
siguiente tablero.

Z X1 X2 X3 X4 z

1 0 0 0 1/2 10

a2 0 0 1 5/38 -38/980 90/38

a1 0 1 0 0 125/950 20/38

52
 INVESTIGACION OPERATIVA

El tablero anterior también es óptimo y corresponde a un punto extremo cuyas

componentes son:

 X1   20 
X 2   19
 90 
X̂     38
X3
   0 
X 4   
 0 
Cuyo valor de la función objetivo también es 10. Entonces cualquier combinación
lineal X y también es óptimo, dando el mismo valor de la función objetivo.
Matemáticamente se representa como la siguiente expresión que también es un
punto óptimo.

 20 
2  19 
0  90 

x     1     0   1
18  38 
  0
0 0
 

[ ][ ] [ ][ ]
X1 2 X1 20/19

[ ]
xB
XN
=
X3
X2
X4
=
18
0
0
Y
[ ]
xB
XN
=
X2
X3
X4
=
90/38
0
0

PROBLEMAS DE MINIMIZACION

A continuación se verá qué tipo de problema se desarrollan en un programa

de minimización. Donde se eliminan los problemas triviales que son de la forma
siguiente:

Min Z = C X
s. a :
AX ≤ b
X≥ 0
b ≥ 0

53
 INVESTIGACION OPERATIVA

Estos tipos de problemas tienen como solución óptima:

X = (X B, XN)
X = ( 0,⋯,0, 0,⋯,0 )

Como se puede ver gráficamente a continuación la solución óptima es no hacer

nada.

igual al vector 0. Este tipo de problemas tienen la siguiente representación

canónica:

Min Z  C X
s. a :
AX  b
X  0

EJEMPLO

Por el Método Simplex conduce a resolver lo siguiente.

Min Z = -3 X1 + 5 X2
s. a :
X1 ≤ 4
X2 ≤ 6
3 X1 + 2X2 ≥ 18
X1 ≥ 0, X2 ≥0 54
 INVESTIGACION OPERATIVA

El problema se puede reescribir.

Max (-Z )= 3 X 1 - 5 X 2
s. a :
X1 ≤ 4
X2 ≤ 6
3 X1 + 2X 2 ≥ 18
X1 ≥ 0, X2 ≥0
F. C:
Max h = (-Z )= 3 X1 - 5 X 2
s. a :
X1 ≤ 4
X2 ≤ 6
- 3 X1 - 2X2 ≤ - 18
X1 ≥ 0, X2 ≥0

Agregando variables de Holgura lo llevamos al tablero del Método Simplex y

tenemos lo siguiente

H X1 X2 X3 X4 X5 Z

1 -3 5 0 0 0 0

a3 0 1 0 1 0 0 4

a4 0 0 1 0 1 0 6

a5 0 -3 -2 0 0 1 -18

55
 INVESTIGACION OPERATIVA

Cuando Z = 0 tenemos la solucion siguiente:

[ ][ ]
X3
4
X4 6

[ ] X
XB −18
= 5 =
XN X1 0
X2 0

MÉTODO PENAL

Min Z  C X  M W
s. a :
AX - Y  W  b
X  0
Y  0
w  0
Es también optima al P.O.
Min Z  C X
s. a :
AX  b
X  0  el vector W  0
Donde:

W=Vector de variables artificiales y penalizado.

M=Vector de valores positivos arbitrarios muy elevados.

Efectuaremos el Algoritmo del Método Penal juntamente con su ejemplo:

Algoritmo

Paso 1: Dado el P.L. de la siguiente forma:

Optimizar z = CX

56
 INVESTIGACION OPERATIVA

s.a : AX ≤ B

X≥0

Convertirlo a la forma Estándar

Paso 2: Verificamos si el PL no viola las condiciones de no negatividad y de

factibilidad.

Si es Si ir al Paso 5; Caso contrario continuar con el Paso 3.

W es un vector de variables artificiales s de holgura y penalizar a la FO con un

costo –MW en caso de Maximización o +MW en caso de minimización.

Paso 3:

Agregar un vector W a cada restricción en donde no existan variable de holgura

Donde: M es un vector de valores positivos arbitrarios muy elevados (M>>> 0).

Paso 4:

Restablecer la base, se quiere que la base B esté compuesta de las variables de

holgura y artificiales, se necesita que W sea un vector unitario tipo e n . Para esto se
convierte ZW1 – CW1 en cero, mediante el uso de operaciones matriciales
elementales; haciendo así que la solución inicial es factible y básica.

Paso 5:

Aplicar el método Simplex hasta que W salga de la base ..

Paso 6

Visualizaremos el último tablero Simplex, en donde verificaremos la condición de

optimalidad.

Paso 7

Observar si existe un W en la base, de ser así no hay solución óptima ir al paso

8.

57
 INVESTIGACION OPERATIVA

Caso contrario no exista un W en la base, osea W=0 y se ha retornado al

problema original, cuya solución óptima está garantizada por el Método Simplex.

Paso 8

FIN

Ejemplo

Min Z = -3 X1 + 5 X2
Max h = -Z = 3 X1 - 5 X2
s. a : s. a :
X1 ≤ 4 X1 + X3 = 4
X2 ≤ 6 X2 + X4 = 6
3 X1 + 2X2 ≥ 18 3 X1 + 2X 2 - X 5= 18
Xi ≥ 0, ∀ i=1-5
X1 ≥ 0, X2 ≥0

Introduciendo la variable artificial W1 tenemos :

Max h  - Z  3 X 1 - 5 X 2 - MW1
s. a :
X1  X3  4
X2  X4  6
3 X 1  2X 2 - X 5  W1  18
X i  0,  i  1 - 5 W1  0

58
 INVESTIGACION OPERATIVA

Llevando al tablero Simplex tenemos:

Introduciendo la variable artificial W1 tenemos :
Max h  - Z  3 X1 - 5 X 2 - MW1
s. a :
X1  X3  4
X2  X4  6
3 X1  2X 2 - X 5  W1  18
X i  0,  i  1 - 5 W1  0

H X1 X2 X3 X4 X5 W1 Z
1 -3 5 0 0 0 M 0
X3 0 1 0 1 0 0 0 4
X4 0 0 1 0 1 0 0 6
XW1 0 3 2 0 0 -1 1 18

H X1 X2 X3 X4 X5 W1 Z
1 -3 5 0 0 0 M 0
X3 0 1 0 1 0 0 0 4
X4 0 0 1 0 1 0 0 6
XW1 0 3 2 0 0 -1 1 18

Tablero transformado

H X1 X2 X3 X4 X5 W1 Z
1 -3-3M 5-2M 0 0 M 0 -18M
X3 0 1 0 1 0 0 0 4
X4 0 0 1 0 1 0 0 6
XW1 0 3 2 0 0 -1 1 18

¿Cuál es la diferencia con el Método Simplex?

Min Z  - 3 X1  5 X 2
s. a :
X1  4
X2  6
3 X1  2X 2  18
X1  0, X 2  0

59
 INVESTIGACION OPERATIVA

De aquí en adelante aplicamos el Método Simplex

Primera Iteración

Vector que ingresa a la base X2.

Vector que sale de la base Xw1

H X1 X2 X3 X4 X5 W1 Z
1 0 5-2M 3+3M 0 M 0 12-6M
X1 0 1 0 1 0 0 0 4
X4 0 0 1 0 1 0 0 6
XW1 0 0 2 -3 0 -1 1 6

De aquí en adelante aplicamos el Método Simplex

Primera Alteración:

Vector que ingresa a la base X2.

Vector que sale de la base Xw1

H X1 X2 X3 X4 X5 W1 Z
1 0 5-2M 3+3M 0 M 0 12-6M
X1 0 1 0 1 0 0 0 4
X4 0 0 1 0 1 0 0 6
XW1 0 0 2 -3 0 -1 1 6

Ultimo tablero

H X1 X2 X3 X4 X5 W1 Z
1 0 0 21/2 0 5/2 M-5/2 -3
X1 0 1 0 1 0 0 0 4
X4 0 0 0 3/2 1 ½ -½ 3
X2 0 0 1 -3/2 0 -½ ½ 3

¿Por qué se dice que el tablero es óptimo?

Ahora en el último tablero óptimo se verifica si el vector W sigue en la base:

H X1 X2 X3 X4 X5 W1 Z
1 0 0 21/2 0 5/2 M-5/2 -3
X1 0 1 0 1 0 0 0 4
X4 0 0 0 3/2 1 ½ -½ 3
X2 0 0 1 -3/2 0 -½ ½ 3

60
 INVESTIGACION OPERATIVA

 X1  4
X4  3

 XB  X2   3
   X   0
XN  3  
 X5  0
W  0
 1  
h   Z  3
Z3
 Como Z j  C j  0 y W1  0 el problema es óptimo

Problemas No Solubles

Los PL no tienen solución cuando sus restricciones son inconsistentes.

Veamos la aplicación, con el ejemplo:

Max Z = 2 X1 + 2 X2
s. a :
X1 + X2 ≤ 2
X1 + X 2 ≥ 4
X1 ≥ 0, X2 ≥0
Por el Método Penal tenemos:
Max Z = 2 X1 + 2 X2 -0X 3 +0X 4 -MW1
s. a :
X 1 + X2 + X3 = 2
X1 + X 2 -X 4 +W 1 = 4
Xi ≥ 0, ∀ i=1-4 W 1≥0

Tablero Inicial

Como W1 está en la base, se debe restablecer la base convirtiéndolo en un vector

unitario e3.

61
 INVESTIGACION OPERATIVA

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

Aplicando el algoritmo del M. Penal en el tablero siguiente:

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

1ra Iteración

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

Vector que ingresa a la base X1.

Vector que sale de la base es X3.

Z X1 X2 X3 X4 X5 Z
1 0 0 2+M M 0 4-2M
X1 0 1 1 1 0 0 2
W1 0 0 0 -1 -1 1 2

Como los (Zj – Cj) >=0 entonces se cumple el criterio de Optimalidad pero W 1 no
sale de la base (W1 =2) por lo tanto el problema no tiene solución.

62
 INVESTIGACION OPERATIVA

MÉTODO DOBLE FASE

Es igual al M. Penal, soloque primero se introducen las variables artificiales al

Problema Original.

Min Z  C X
s. a :
AX  b
X  0
Quedando como :
Min Z  C X
s. a :
AX - Y  W  b
X  0, Y  0, W  0

Algoritmo

Paso 1:

Dado el P.L. de la siguiente forma:

Min Z  CX
sujeta a :
AX  b
X0
Paso 2:

Si el PL puede resolverse por el M. Simplex, entonces seguir con los pasos del
algoritmo del M. Simplex, e ir al paso7. Caso contrario seguir al paso3

Paso 3:

p
Min  Wi
i 1
Min Z  CX
s. a :
sujeta a :
AX - Y  W  b AX  b
X  0, Y  0, W  0 X0
La solución Opt. De la I Fase debe ser cuando W=0

63
 INVESTIGACION OPERATIVA

Paso 4:

Si Obtenemos las condiciones de Optimalidad Zj-Cj >0 en la Fase I y W>0 el

problema original no tiene solución, ir al paso 6.

Paso 5:

Supóngase que la Fase I es óptimo es decir W=0, y que la base asociada al tablero
es B, aplicar la II Fase.

II Fase:

Se aplica el M. Simplex para resolver el siguiente modelo:

Min Z= C X

s.a
−1 −1 −1
B AX−B Y =B b

X≥0;Y≥0

Paso 6:

Fin

64
 INVESTIGACION OPERATIVA

PROBLEMAS DEGENERADOS Y REGLAS LEXICOGRAFICAS

Anteriormente se dijo que al existir un Empate para decidir que vector entra a la
base esto se decide arbitrariamente sin ningún efecto en el número de iteraciones
del método simplex. En cambio un empate en el vector de salida no puede decidirse
arbitrariamente porque puede ocasionar un ciclaje.

II Fase:

Se aplica el Método Simplex para resolver el siguiente modelo:

EJERCICIO DE MÉTODO SIMPLEX:

1. Minimizar:

Z = 6X1 + 4X2 + 2X1

C.S.R.

6X1 + 2X2 + 6X1 ≥ 6

6X1 + 4X2 = 12

2X1 + 2X2 ≤ 2

Xj ≥ 0; j = 1, 2,3

Minimizar Z = 6X1 + 4X2 + 2X1 + 2X3 + MX5 + M6

C.S.R.

6X1 + 2X2 + 6X3 - X4 + X5 =6

6X1 + 4X2 X6 = 12

2X1 - 2X2 X7 = 2

Las Variables Básicas Son X5 = 6, X6 = 12, X7 = 2

CJ. 6 4 2 0 M M 0 b/a
V.B B X1 X2 X3 X4 X5 X6 X7
M X5 6 6 2 6 -1 1 0 0 1
M X6 12 6 4 0 0 0 1 0 2
0 X7 2 2 -2 0 0 0 0 1 1
ZJ - CJ 18M 12M-6 6M-4 6M-2 -M 0 0 0

65
 INVESTIGACION OPERATIVA

CJ. 6 4 2 0 M M 0 b/a
V.B B X1 X2 X3 X4 X5 X6 X7
6 X1 1 1 2 1 -1/6 1/6 0 0 3 2
M X6 6 0 4 -6 0 -1 1 0 3
0 X7 0 0 -2 -2 1/3 -1/3 0 1 NO
ZJ - CJ 6M+6 0 2M-2 -6M+4 M-1 - 0 0
2M+1

CJ. 6 4 2 0 M M 0
V.B b X1 X2 X3 X4 X5 X6 X7
6 X1 0 1 1/3 2 -1/3 1/3 0 0
4 X2 3 0 2 -3 ½ -1/2 1 0
0 X7 8 0 -8/3 -10 5/3 -5/3 0 1
ZJ - CJ 12 0 0 -2 0 -M -M+1 0

Solución optima:

Variables de decisión.

X1 = 0, X2 = 3, X3 = 0, Z = 12

Variables de holgura: X4 = 0, X7 = 8

Variables artificiales: X5 = 0, X6 =0.

66
 INVESTIGACION OPERATIVA

MÉTODO SIMPLEX REVISADO

La solución práctica de problemas reales que utilizan modelos de programación

lineal, presentan la gran dificultad de que tienen mucha información que debe
almacenarse en la computadora. Por ejemplo un problema con 10 000 variables de
decisión y 500 restricciones. En este caso la matriz A tendría 5 millones de
componentes quizá muchas de ellas cero. Requiriendo así capacidad de memoria
para almacenar toda la información requerida en la solución, se consumiría mucho
tiempo en el acceso de esa información para el cálculo de los diferentes pasos del
Método Simplex.

Bajo tales problemas se han desarrollado métodos que aprovechando las

propiedades básicas de la estructura del Método Simplex, permiten la solución de
problemas lineales bastante grandes, sin requerir del almacenamiento de toda esa
información y sin incrementar el tiempo de cómputo.

DOS DE ESOS MÉTODOS SON

 Método Simplex Revisado

 Método de Descomposición Lineal

METODO SIMPLEX REVISADO

Elementos que se utilizan en el Método Simplex.

En cada iteración se tiene que:

 El vector básico está dado por:

VECTOR BÁSICO XB = B-1 b

Donde:

B: Es la base correspondiente a esa iteración.

 El valor de la función objetivo es:

Z = C B XB

67
 INVESTIGACION OPERATIVA

Zj - cj = CB B-1aj-cj, j en A

En cada iteración el único elemento indispensable es: B-1

 Porque se pueden calcular:

X , Z, z - c
B j j

La diferencia entre el método simplex revisado y el método simplex, es que en

el primero, es necesario almacenar en cada iteración un tablero de m por m,
mientras que en el segundo método, cada tablero es de m por n, conteniendo
muchísima más información que en el primer proceso.

EJEMPLO MÉTODO SIMPLEX REVISADO

 Paso 1:

Máx. Z = CX

sa: AX £ b

X³0

Máx. Z = 3X1 + 2X2 + 5X3

Sujeto a:

X1 + 2X2 + X3 £ 430

3X1 + 2X3 £ 460

X1 + 4X2 £ 420

X1, X2, X3 ³ 0

68
 INVESTIGACION OPERATIVA

ALGORITMO Y EJEMPLO MÉTODO SIMPLEX REVISADO

Paso 1: El formato del tablero original es:

Z X1 X2 X3 X4 X5 X6

1 -3 -2 -5 0 0 0 0

X4 0 1 2 1 1 0 0 430

X5 0 3 0 2 0 1 0 460

X6 0 1 4 0 0 0 1 420

 Paso 1.1

Del tablero obtenemos lo siguiente

[ ] [ ]
1 2 1 1 0 0
C N =[ 3 2 5 ]
A= 3 0 2 B= 0 1 0
1 4 0 0 0 1

[] [] [ ]
X1
X= X2
X4 430
X S= X 5 b= 460
X3
X6 420

C B= [ 0 0 0]

Paso 2: Establecer Básicas y no Básicas

[ ]
X1
No básicas X= X2
X3

[]
X4
X B= X 5
X6
69
 INVESTIGACION OPERATIVA

Básicas

Paso 3: Hallar la B-1 actual

[ ]
1 0 0
−1
B= 0 1 0 =B
0 0 1

Paso 4:

• Hallar XB y Z

[ ] [ ][ ] [ ]
X4 1 0 0 430 430
−1
X B =B b X B= X 5 = 0 1 0 460 = 460
X6 0 0 1 420 420

[ ][ ]
1 0 0 430
Z=C B B−1 b=[ 0 0 0 ] 0 1 0 460 =0
0 0 1 420
Paso 5:

• verificar la optimalidad hallando:

Zj - cj = CB B-1aj-cj, j en N

Si todos zj - cj ³ 0 la solución XB es óptima. (Fin de iteración)

Caso contrario el vector que entra a la base será el más negativo: Xj

[ ][ ]
Zj - cj = CB B-1 aj-cj,
1 0 0 1 2 1
J en N = [0 0 0 ] 0 1 0 3 0 2 − [3 2 5 ]
0 0 1 1 4 0

= [−3 −2 −5 ]

70
 INVESTIGACION OPERATIVA

El vector de entrada será x 3

Paso 6: Hallar el vector que sale de la base Xr.

Hallando

XB i
Min [ Yij > 0 ]
Y ij

[]
Y 1J
Y 2J
Y 3J −1
Y j= . =B a j
.
.
Y mJ

El vector de salida se determina por medio de la siguiente relación:

= [ XB i Yi3 > 0 ]
Y i3

Z X1 X2 X3 X4 X5 X6
1 -3 -2 -5 0 0 0 0
a4 0 1 2 1 1 0 0 430
a5 0 3 0 2 0 1 0 460
a6 0 1 4 0 0 0 1 420
Donde:

[ ] [ ][ ] [ ]
Y 13 1 0 0 1 1
−1
Y 3 = Y 23 =B a3 = 0 1 0 2 = 2
Y 33 0 0 1 0 0

Por lo tanto

71
 INVESTIGACION OPERATIVA

[ 430 460
1
,
2
=230
] y X5 sale de la base.

Paso 7: para seguir la iteración

Ir al paso 2, distinguiendo B-1, Z, XB en cada iteración.

[]
X1
 No básicas X = X 2
X5

[]
X4
 básicas X S= X 3
X6

Paso 3

 Hallar la B-1 actual

[ ] [ ]
1 1 0 1 −1 /2 0
−1
B= 0 2 0 ⇒ B = 0 1 /2 0
0 0 1 0 0 1

 Paso 4:

 Hallar XB y Z

[ ][
X B=B−1 b
][ ] [ ]
X4 1 −1/2 0 430 200
X B= X 3 = 0 1/ 2 0 460 = 230
X6 0 0 1 420 420

C B= [ 3 5 0 ]

[]
100
−1
Z=C B B b=C B X B=[ 2 5 0 ] 230 =1350
20 72
 INVESTIGACION OPERATIVA

 Paso 5:

• Verificar la optimalidad hallando:

Zj - cj = CB B-1aj-cj, j en N

Si todos zj - cj ³ 0 la solución XB es óptima. (Fin de iteración)

Caso contrario el vector que entra a la base será el más negativo: Xj

zj - cj = CB B-1 aj-cj,

j en N

[ ][ ]
1/2 −1 /4 0 1 1 0
= [ 2 5 0 ] 0 1/2 0 3 0 1 −[ 3 0 0 ]
−2 1 1 1 0 0

=[ 4 1 2]

 Por lo que la solución Z , XB es óptima

[ ][ ][ ]
XB X2¿ X1 ¿ 10 ¿ 0¿
X= = X6 ¿ ¿ X6 ¿ ¿ = 10 ¿ ¿ 0¿ ¿
XN X3¿ X4 ¿ 230 ¿ 0¿
Z = 1350

EJEMPLOS DE MÉTODO SIMPLEX REVISADO

1) Resolver el modelo Reddy Mikks empleando el método revisado.
El modelo Reddy Mikks (en forma estándar) se resume aquí. Por conveniencia,
utilizamos x1 y x3 en vez de xE y x1. Las holguras se representan con x1, x4, x3, x y
x6.

Maximizar Z= 3X1 +2X2

Sujeta a X1+2X2+X3 =6

73
 INVESTIGACION OPERATIVA

2X1+X2 +X4 =8
-X1+X2 +X5 =1
X2 +X6 = 2

X 1, X2,…, X6 ≥ 0

Solución inicial

Xb= (x3, x4, x5, x6)T

Cb= (0, 0, 0,0)

B= (P3, P4, P5, P6)= I

B-1= I

Primera iteración

Paso 1: calcular de zj - Cj para los vectores no básicos P1 y P2.

Y= CB B-1= (0,0,0,0)I = (0,0,0,0)

(Z1- C1, Z2, C2)= Y(P1, P2) –(C1, C2)

( )
12
¿(0 , 0 ,0 , 0) 2 1 ¿(3 ,2)
−1 1
01

¿(−3 ,−2)

En t términos de la tabla simplex del capitulo 3, los cálculos se representan como:

(Observe que Zj – Cj automáticamente son igual a cero para todas las variables
básicas.) Así, P1 es el vector entrante.

Paso 2: determinación del vector saliente considerado que P1entra en la base.

()
6
8
X B = B-1b = Ib =b=
1
2

()
1
2
α 1= B-1P1 =IP1= P1 =
−1
0

74
 INVESTIGACION OPERATIVA

En términos de la tabla, los cálculos para los pasos 1 y 2 se pueden resumir

de la siguiente manera:

Así,

6 8
Ѳ=min( , ,−,−, ¿)=4 ,¿ Corresponde a x4
1 2

En consecuencia, P4 es el vector saliente.

Paso 3: determinación de la base inversa siguiente. Como P 1 remplaza a P4 y

α1= (1, 2, -1, 0) T, tenemos.

( )( )
−1 −1
2 2
+1 /2 1
ε= = 2 Y
−
−1
( )
2
1
2
0 /2 0

B-1sig – EB-1 EI = E = ¿

La nueva base esta asociada con el vector básico.

XB = (x3, x1, x5, x6)

CB= (0, 3, 0, 0)

Segunda Iteración

Paso 1: calcular de Zj – Cj para los vectores no básicos P2 y P4

75
 INVESTIGACION OPERATIVA

( )
1
1− 0 0
2
1
-1 0 00
CBB = (0,3, 0, 0) 2 = - (0, 3/2, 0, 0)
1
0 10
2
0001

()
20
11
(Z2 -C2, Z4 –C4) = (0,3/2, 0,0) = (2,0) = (-1/2, 3/2)
10
10

Así es el vector entrante.

Paso2: determinación del vector saliente, considerando que P2 entra en la base.

() ()
6 2
8 4
XB = B-1 b = ¿ =
1 5
2 2

()
3
2
1
α2 = ¿ = 2
3
3
1

Los cálculos de los pasos 1 y 2 se pueden resumir en forma tabular como sigue:

76
 INVESTIGACION OPERATIVA

Así

Ѳ = min {32/2 1/24 3/25 21 } = 4/3

Correspondiente a [Link] consecuencia, P3 es el vector saliente.

Paso 3: determinación de la base inversa siguiente como P2reemplaza a P3 y α2=

(3/2,1/2, 3/2, 1) T, tenemos.

()
+1

() 3
2

()
−
1

()
2 2

E=
( 2)
3 3
−1
−( )
3 3
2 −1
−2/3
( 32 )
−1

()
3
2

( )( )
2 1
000 1− 0 0
3 2
−1 1
100 0 00
B-1sig= 3 2
−1 0 10 1
0 10
−2 2
001
3 0001

77
 INVESTIGACION OPERATIVA

( )
2 1
− 00
3 3
−1 2
00
= 3 3
−11 1 0
−2
1/3 0 1
3

La nueva base está asociada con el vector básico.

XB= (X2, X1, X5, X6)

CB= (2, 3, 0, 0)

Tercera Iteración

Paso1: calculo de Zj – Cj para P1 y P4

( )
2 1
− 00
3 3
−1 2
-1 00
CB B (2,3, 0,0) 3 3 = (1/3, 4/3, 0, 0)
−11 1 0
−2
1/3 0 1
3

()
10
01
(z3-C3, z4 –C4) = (1/3, 4/3, 0, 0) = (0, 0)= (1/3, 4/3)
00
00

Como todas las Zj - Cj ≥ 0, la ultima base es optima.

Solución optima

78
 INVESTIGACION OPERATIVA

( )( ) ( )
2 1
− 00 4
3 3

()
X2 6 3
−1 2
X1 -1 − 00 8 10
=B b= 3 3 =
X5 1 3
−11 1 0
X6 2 3
−2
1 /3 0 1 2 /3
3

()
4
3
10
Z= CB XB = (2, 3, 0, 0) = 38/3
3
3
2 /3

2) EJEMPLO

1 0 1 0 0 4
0 2 0 1 0 12
C=3 5, A I =3 2 0 0 1, b = 18

X3
X1 X4
X= X 2, XS = X 5

Iteración 0

X3 1 0 0
X4 0 1 0
XB = X 5, B=0 0 1 = B-1, así

X3 1 0 0 4 4
X4 0 1 0 12 12
X 5 =0 0 1 18 = 18

79
 INVESTIGACION OPERATIVA

4
12
CB = 0 0 0 así Z = 0 0 0 18 =0

Iteración 1

1 0 0
X3 1 0 0
1
X2 0 2 0 0 0
2
XB = X 5, B=0 2 1, B-1 = 0 −1 1

1 0 0
X3 4 4
1
X2 0 0 12 6
2
Así X5 =0 −1 1 18 = 6

4
6
CB = 0 5 0 así Z = 0 5 0 6 = 30

Iteración 2

X3 1 0 0 1 1
3
−1
3

X2 0 2 0 0
1
2
0
−1 1
= X 1, B=0 2 3, 0
XB B-1 = 3 3

X3 1 1
3
−1
3 4 2
X2 0
1
2
0 12 6
−1 1
Así X1 =
0 3 3 18 = 2

2
6
CB = 0 5 3 así Z = 0 5 3 2 = 36

80
 INVESTIGACION OPERATIVA

Considérese el último conjunto de ecuaciones que se obtiene en la iteración 2 para

el problema de Wyndor Glass.

1 −1
1 3
1
3 1 0 0 0
0 2
0 0 2 0 1
−1 1
0 3 2
B-1A = 3 3 =1 0
1 −1
1 3 3
1
0 2
0
−1 1
CBB-1 = 0 5 3 3
0 0 1
3 3 = 2

0 0
0 1
B-1 A –C = 0 5 31 0 -3 5 =0 0
CB

Como ya se encontraron

XB = B-1b y Z = CBB-1b, estos resultados dan las siguientes ecuaciones:

Z
X1
1 0 0 0 3/ 2 1 X2 36
0 0 0 1 1/ 3 −1/ 3 X 3 2
0 0 1 0 1/ 2 0 X4 6
0 1 0 0 −1/ 3 1/ 3 X 5 = 2

3) EJEMPLO
Aplíquese el método revisado al problema de la Windor glass. Las variables
básicas iniciales son las variables de holgura.

X3
X4
XB = X5

81
 INVESTIGACION OPERATIVA

INTERACCIÓN 1 Como la matriz inicial B-1 = I, no es necesario ningún

calculo

A fin de obtener los números requeridos para identificar la variable básica

entrante

X2 (- C2 = -5 < -3 = - C1) y la variable básica que sale X4 ( a12 = 0 , b2/a22 = 12/2 <
18/2= b3/a32 , por lo que r =2 ). Así el nuevo conjunto de variables básicas es

X3
X2
XB = X5

Para obtener la nueva B-1

−a 12 /a 22 0
1 /a 22 1/ 2
η = −a 32 /a 22 = −1

Entonces

1 0 0 1 0 0 1 0 0
0 1 /2 0 0 1 0 0 1 /2 0
B-1 = 0 −1 1 0 0 1 =0 −1 1

E B-1 antigua

De manera que

X3 1 0 0 4 4
X2 0 1 /2 0 12 6
X5 =0 −1 1 18 = 6

Para probar si esta solución es óptima se calculan los coeficientes de las variables
no básicas (X1 y X4) en la ecuación (0).

82
 INVESTIGACION OPERATIVA

1 0 0 1 −
0 1 /2 0 0 −
CBB-1 A –C = 0 5 00 −1 1 3 − -3 − =3 −

− 0 −
− 1/ 2 −
CBB-1 = 0 5 0 − −1 − =− 5/ 2 −

Realizando nada más las partes relevantes de la multiplicación de matrices, se

tiene de manera que los coeficientes de X1 y X4 son -3 y 5/2 respectivamente
como X1 tiene coeficiente negativo, esta solución no es óptima.

INTERACCIÓN 2

Con estos coeficientes de las variables no básicas, la siguiente iteración comienza

por identificar X1 como la variable básica entrante. Para determinar la variable
básica que sale se deben calcular los otros coeficientes de X1 :

1 0 0 1 − 1 −
0 1 /2 0 0 − 0 −
B-1 A = 0 −1 1 3 − =3 −

Se usa la columna del lado derecho de la solución básica actual ( el valor de X B)

que se acaba de obtener en la iteración 1, las razones 4/1 > 6/3 indica que X 5 es la
variable básica que sale y el nuevo conjunto de variable básica es

X3 −a ´ 11 /a 31 −1/ 3
X2 −à 21 /a 31 0
XB = X 1 η = 1/a 31 = 1/ 3

Por lo cual, la nueva B-1 es

1 0 −1/ 3 1 0 0 1 1 /3 −1/ 3
0 1 0 0 1 /2 0 0 1/ 2 0
B-1 = 0 0 1/ 3 0 −1 1 = 0 −1/3 1/ 3

Entonces

83
 INVESTIGACION OPERATIVA

X3 1 1 /3 −1/ 3 4 2
X2 0 1/ 2 0 12 6
X1 = 0 −1/3 1/ 3 18 = 2

− 1/ 3 −1 /3
− 1/ 2 0
CBB-1 = 0 5 3 − −1/ 3 1 /3 =− 3 /2 1

Como ambos coeficientes (3/2 y 1) son no negativos, la solución actual ( X 1=2,

X2=6, X3 = 2 , X4 = 0 , X5 = 0) es óptima.

84
 INVESTIGACION OPERATIVA

BIBLIOGRAFIA

PRAWDA WITENBERG, Juan. Métodos y modelos de investigación de

[Link] 1. Editorial Limusa 1.995

RÍOS INSUA, Sixto; RÍOS INSUA David; MATEOS, Alfonso; MARTÍN,

[Link]ón lineal y aplicaciones. Editorial Alfaomega S.A. 1.997

SHAMBLIN, James E.; STEVENS Jr. G. T. Investigación de operaciones: Un

enfoque fundamental. Editorial McGraw-Hill Interamericana, México.

SOLOW, Daniel; KAMLESH, Mathur. Investigación de operaciones. Editorial

Prentice – Hall Hispanoamericana S.A., México.

STEPHEN B. Bergen. Apuntes de los cursos de investigación de operaciones

de la Universidad se Stanford. Universidad Tecnológica de Pereira .

TAHA, Handy A. Investigación de operaciones: Una introducción. Editorial

Prentice Hall, México. Sexta edición 1.998

VARELA, Jaime Enrique. Introducción a la investigación de operaciones.

Editorial Fondo Educativo Interamericano S.A., Colombia. Primera edición 1.982

85