universidad autÓnoma san franciscorepositorio.uasf.edu.pe/bitstream/uasf/97/1/tu joa-lbio... ·...
TRANSCRIPT
UNIVERSIDAD AUTÓNOMA SAN FRANCISCO
ESCUELA DE POSGRADO
JIMMY OJEDA ARNICA
Arequipa – Perú
2017
LINEAMIENTOS BÁSICOS DE
INVESTIGACIÓN DE OPERACIONES
1
INTRODUCCIÓN
El Texto Universitario “Lineamientos Básicos de Investigación de Operaciones”,
trata de presentar en forma detallada y práctica, los conceptos y la importancia
de los fundamentos generales de la Programación Lineal en la Investigación de
Operaciones, que pueden tener aplicación práctica en la toma de decisiones de
las instituciones y personas naturales dedicadas al trabajo industrial, procesos,
proyectos, seguridad, etc., que son absoluta e imprescindiblemente necesarios
para la marcha de las entidades en general y para el logro de sus objetivos de
desarrollo en particular.
Sirve para dar a conocer al público en general y a los estudiosos en particular,
que la investigación de operaciones, basa sus análisis y verificaciones, en los
razonamientos lógicos y matemáticos de las actividades de la carrera
profesional, de acuerdo a los diversos procedimientos que debe seguir cada uno
de ellos.
Los conceptos generales de esta ciencia aplicada, permiten que después de una
visión más orgánica de cada parte de los métodos cuantitativos, puedan hacer
sus propias síntesis y enfoques, como es propio de un estudio de nivel
universitario, con sentido de investigación, posibilitando a la vez el estricto
cumplimiento de cada principio, en su aplicación sustentada.
Dentro de la finalidad de esta publicación, está la de poder manejar la
matemática básica y su aplicación didáctica, académica, científica y profesional,
pues la matemática es universal y a la vez particular, porque fuera de los
lineamientos generales y universales, cada especialidad tiene un código que
norma sus actividades, leyes y costumbres propias, que difieren unas de otras,
y de acuerdo a las necesidades técnicas y pedagógicas particulares.
2
El objetivo de esta disciplina es que las personas dedicadas a la producción
empresarial, aprendan a reconocer los problemas tipo de la Investigación de
Operaciones, de modo que sepa a qué técnico recurrir en cada caso, para un
adecuado estudio y solución del mismo.
Como su nombre lo indica, la Investigación de Operaciones (IO), o Investigación
Operativa, es la investigación de las operaciones a realizar para el logro óptimo
de los objetivos de un sistema o la mejora del mismo. Esta disciplina brinda y
utiliza la metodología científica en la búsqueda de soluciones óptimas, como
apoyo en los procesos de decisión, en cuanto a lo que se refiere a la toma de
decisiones óptimas y en sistemas que se originan en la vida real.
Cuando una persona se enfrenta por vez primera con el término Investigación de
Operaciones, no suele ser conocedora de las características específicas de esta
ciencia ni de su objeto de estudio. Además, la Investigación Operativa puede
tener componentes muy diversos dependiendo de su área de aplicación
concreta: Administración de Empresas, Ingeniería u otras. El objeto de estudio
de la Investigación Operativa es la toma científica de decisiones mediante el
empleo de técnicas cuantitativas. Es importante tener esta definición clara y, de
esta forma, nos daremos cuenta de la amplitud de campo de la Investigación
Operativa (IO).
3
ÍNDICE
CAPÍTULO I: DEFINICIÓN Y SIGNIFICADO DE INVESTIGACIÓN DE OPERACIONES ......... 5
A. INVESTIGACIÓN DE OPERACIONES ................................................................................. 5 B. FASES DE LA INVESTIGACIÓN OPERACIONAL ............................................................... 6
1. Formulación del Problema ................................................................................................ 6 2. Construcción del Modelo del Sistema ............................................................................... 7 3. Cálculo de la solución a través del modelo ....................................................................... 8
C. HISTORIA DE LA INVESTIGACIÓN DE OPERACIONES .................................................... 9 1. Objetivos .......................................................................................................................... 10 2. Aspectos que estudia la I.O. ........................................................................................... 11 3. Orígenes de la I.O. .......................................................................................................... 11 4. Desarrollo ........................................................................................................................ 11
CAPÍTULO II: PROGRAMACIÓN LINEAL ................................................................................ 12
A. INTRODUCCIÓN A LA PROGRAMACIÓN ......................................................................... 12 B. PROGRAMACIÓN LINEAL ................................................................................................. 13
1. Test del modelo y de la solución ..................................................................................... 15 2. Establecimiento de controles de solución ....................................................................... 15 3. Implementación y seguimiento ........................................................................................ 15 4. Aplicaciones .................................................................................................................... 15
C. MÉTODO SIMPLEX ............................................................................................................ 24 1. Objetivo ........................................................................................................................... 25 2. Características ................................................................................................................. 26 3. Preparando el modelo para adaptarlo al método Simplex .............................................. 26 4. Tipo de optimización ....................................................................................................... 27 5. Cambio de signo de los términos independientes .......................................................... 29 6. Normalización de las restricciones .................................................................................. 30 7. Desarrollando el método Simplex ................................................................................... 32 8. Problema de aplicación ................................................................................................... 37 9. Ejemplo práctico .............................................................................................................. 39
D. MÉTODO SIMPLEX DOS FASES....................................................................................... 42 E. IDENTIFICANDO CASOS ANÓMALOS Y SOLUCIONES ................................................................... 45
1. Ejemplo de aplicación ..................................................................................................... 47 F. INTERPRETACIÓN GRÁFICA DEL MÉTODO SIMPLEX ................................................................... 54
Ejemplo método gráfico ....................................................................................................... 55 G. COMPARACIÓN DEL MÉTODO GRÁFICO Y EL MÉTODO SIMPLEX ................................................. 58 H. SOLVER .............................................................................................................................. 62
1. ¿Qué es Solver?.............................................................................................................. 62 2. Complemento SOLVER para Excel (2013 y posteriores) ............................................... 62 3. Ejemplo de uso de Solver ............................................................................................... 66
I. DUALIDAD EN PROGRAMACIÓN LINEAL ......................................................................... 70 1. Relaciones entre problemas primales y duales .............................................................. 70
J. ANÁLISIS DE SENSIBILIDAD ............................................................................................. 74
CAPÍTULO III: MODELOS DE PERT-CPM ................................................................................ 84
PERT ....................................................................................................................................... 84 CPM ......................................................................................................................................... 84 ASPECTOS GENERALES PERT ............................................................................................ 85 ASPECTOS GENERALES CPM ............................................................................................. 85 TERMINOLOGIA PERT/CPM ................................................................................................. 86 ESTRUCTURA DE RED .......................................................................................................... 87
1. Características ................................................................................................................. 87
4
2. Diagrama de red .............................................................................................................. 88 ANALISIS DE UNA RED PERT/CPM ...................................................................................... 91
1. Sharp Company ........................................................................................................... 91 2. Cálculos básicos de la programación.......................................................................... 92 3. Importancia de conocer la fecha de término ................................................................... 92 4. Ruta critica ....................................................................................................................... 93 5. Para el caso de la Sharp Company................................................................................. 93 6. Revisión hacia delante .................................................................................................... 94 7. Definición de terminación y notación............................................................................... 94 8. Revisión hacia atrás ........................................................................................................ 97 9. Definición de términos y notación ................................................................................... 97 10. Tiempo de holgura (flotante) ......................................................................................... 99 11. Resumen de los Cálculos Pert/CPM ........................................................................... 100 12. Incertidumbre en una red PERT/CPM......................................................................... 101 13. Comentarios ................................................................................................................ 103 14. Variabilidad en los Tiempos de las Actividades .......................................................... 103 15. Variabilidad en la fecha de terminación del proyecto.................................................. 106
CONCLUSIONES...................................................................................................................... 109
CUESTIONARIOS .................................................................................................................... 110
REFERENCIAS ......................................................................................................................... 111
A. BIBLIOGRÁFICAS .................................................................................................................. 111 B. DIGITALES ........................................................................................................................... 112
5
CAPÍTULO I: DEFINICIÓN Y SIGNIFICADO DE INVESTIGACIÓN DE
OPERACIONES
A. INVESTIGACIÓN DE OPERACIONES
La Investigación de Operaciones (IO) o Investigación Operativa es una rama
de las matemáticas que hace uso de modelos matemáticos y algoritmos con
el objetivo de ser usado como apoyo a la toma de decisiones. Se busca que
las soluciones obtenidas sean significativamente más eficientes (en tiempo,
recursos, beneficios, costos, etc.) en comparación a aquellas decisiones
tomadas en forma intuitiva o sin el apoyo de una herramienta para la toma de
decisiones.
Los modelos de Investigación de Operaciones son frecuentemente usados
para abordar una gran variedad de problemas de naturaleza real en ingeniería
y ciencias sociales, lo que ha permitido a empresas y organizaciones
importantes beneficios y ahorros asociados a su utilización.1
La investigación de operaciones puede definirse como un método científico de
resolución de problemas, la cual brinda las herramientas suficientes para que
con base en abstracciones de la realidad se puedan generar y resolver
modelos matemáticos con el objetivo de elaborar un análisis y concluir de los
mismos para así poder sustentar cuantitativamente las decisiones que se
tomen respecto a la situación problema.
1 http://www.investigaciondeoperaciones.net/
6
Otra de las muchas definiciones que de la investigación de operaciones se
encuentran es la siguiente:
"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 a fin de que se produzcan soluciones
que mejor sirvan a los objetivos de toda organización."
Ackoff, R. L. y Sasieni M. W. Fundamentals of Operations Research, John
Wiley & Sons, 1968.
“Un elemento principal de la investigación de operaciones es el modelado
matemático. Aunque la solución del modelo matemático establece una base
para tomar una decisión, se deben tener en cuenta factores intangibles o no
cuantificables, por ejemplo, el comportamiento humano, para poder llegar a
una decisión final”
TAHA, Hamdy. Investigación de Operaciones. Pearson, 2004.
B. FASES DE LA INVESTIGACIÓN OPERACIONAL
Un estudio en Investigación Operacional acostumbra involucrar seis fases:
1. Formulación del problema.
2. Construcción del modelo.
3. Cálculo de la solución a través del modelo.
4. Test del modelo y de la solución.
5. Establecimiento de controles de la solución.
6. Implantación y seguimiento.
Que pueden ser descritas como sigue:
1. Formulación del Problema
7
En esta fase, el administrador del sistema y el responsable por el estudio
en I.O. deben discutir, en el sentido de colocar el problema de manera clara
y coherente, definiendo los objetivos a alcanzar.
2. Construcción del Modelo del Sistema
Los modelos que interesan en I.O. son modelos matemáticos, esto es,
modelos formados por un conjunto de ecuaciones e inecuaciones.
Un modelo es una representación de un sistema real, que puede existir o
ser un proyecto a ser ejecutado. En el primer caso, el modelo pretende
reproducir el funcionamiento del sistema. En el segundo caso, el modelo es
utilizado para definir la estructura ideal del sistema. La confiabilidad de la
solución obtenida a través del modelo depende de la validez del modelo en
la representación del sistema real. La validez del modelo es la confirmación
de que el realmente representa el sistema real. La diferencia entre la
solución real y la solución propuesta por el modelo depende directamente
de la precisión del modelo en describir el comportamiento original del
sistema.
Un problema simple puede ser representado por modelos también simples
y de fácil solución. Ahora, los problemas más complejos requieren modelos
más elaborados, cuya solución puede ser bastante complicado.
En un modelo matemático, son incluidos tres conjuntos principales de
elementos:
Variables de decisión y parámetros: variables de decisión son las
incógnitas a ser determinadas por la solución del modelo. Parámetros
son valores fijos en el problema.
Restricciones: de modo a llevar en cuenta las limitaciones físicas del
sistema, el modelo debe incluir restricciones que limitan las variables de
decisión a sus valores posibles (o viables).
Función Objetivo: es una función matemática que define la cualidad de
la solución en función de las variables de decisión.
8
Para ilustrar mejor a los conjuntos arriba mencionados, consideremos el
siguiente ejemplo.
Ejemplo: Una empresa de comida canina produce dos tipos de raciones:
Tobi y Rex. Para la elaboración de las raciones son utilizados cereales y
carne. Se sabe que:
La ración Tobi utiliza 5 Kg de cereales y 1 Kg de carne, y la ración Rex
utiliza 4 kg de carne y 2 kg de cereales.
El paquete de ración Tobi cuesta S/. 20 y el paquete de ración Rex
cuesta S/. 30.
El kg de carne cuesta S/. 4 y el kg de cereales cuesta S/. 1.
Están disponibles por mes 10 000 kg de carne y 30 000 kg de cereales.
Se desea saber cuál es la cantidad de cada ración a producir de modo que
maximice el lucro.
En este problema las variables de decisión son las cantidades de ración de
cada tipo que van a ser producidas.
Los parámetros dados son los precios unitarios de compra y venta, además
de las cantidades de carne y cereales utilizadas en cada tipo de ración. Las
restricciones son los límites de carne y cereales y la función objetivo es una
función matemática que determine el lucro en función de las variables de
decisión y que debe ser maximizada.
3. Cálculo de la solución a través del modelo
Es realizado a través de técnicas matemáticas específicas. La formulación
del modelo depende directamente del sistema a ser representado. La
función objetivo y las funciones de restricciones pueden ser lineales o no
lineales.
9
Las variables de decisión pueden ser continuas o discretas (por ejemplo,
enteras) y los parámetros pueden ser determinísticos o probabilísticos.
El resultado de esa diversidad de representaciones de sistemas es el
desenvolvimiento de diversas técnicas de optimización, de tal forma que se
pueda resolver cada tipo de modelo existente. Estas técnicas incluyen,
principalmente: programación lineal, programación entera, programación
dinámica, programación estocástica y programación no lineal.
C. HISTORIA DE LA INVESTIGACIÓN DE OPERACIONES
La Investigación de Operaciones o Investigación Operativa es una disciplina
donde las primeras actividades formales se dieron en Inglaterra en la Segunda
Guerra Mundial, cuando se encarga a un grupo de científicos ingleses el
diseño de herramientas cuantitativas para el apoyo a la toma de decisiones
acerca de la mejor utilización de materiales bélicos. Se presume que el
nombre de Investigación de Operaciones fue dado aparentemente porque el
equipo de científicos estaba llevando a cabo la actividad de Investigar
Operaciones (militares).
Una vez terminada la guerra las ideas utilizadas con fines bélicos fueron
adaptadas para mejorar la eficiencia y la productividad del sector civil. Una de
las áreas principales de la Investigación de Operaciones es la Optimización o
Programación Matemática. La Optimización se relaciona con problemas de
minimizar o maximizar una función (objetivo) de una o varias variables, cuyos
valores usualmente están restringidos por ecuaciones y/o desigualdades.
Hoy en día el uso de modelos de optimización es cada vez más frecuente en
la toma de decisiones. Este mayor uso se explica, principalmente, por un
mejor conocimiento de estas metodologías en las diferentes disciplinas, la
creciente complejidad de los problemas que se desea resolver, la mayor
disponibilidad de software y el desarrollo de nuevos y mejores algoritmos de
solución.
10
Un modelo de Investigación de Operaciones requiere necesariamente de una
abstracción de la realidad, además de identificar los factores dominantes que
determinan el comportamiento del sistema en estudio. En este sentido, un
modelo es una representación idealizada de una situación real o un objeto
concreto.2
1. Objetivos
Si el objetivo de una empresa es generar un cierto beneficio mediante la
realización de una cierta obra, el objetivo de la I.O. es que dicha empresa o
sistema opere eficientemente, de modo de optimizar el beneficio.
El objetivo de la I.O. se logra utilizando el método científico para:
Formular el problema
Construir un modelo que lo represente
2 http://www.investigaciondeoperaciones.net/historia_de_la_investigacion_de_operaciones.html
11
Obtener una solución de él
Verificar y modificar las hipótesis mediante una experimentación
adecuada.
Para poder llevar a cabo esto es necesario conocer, profundamente el
Sistema:
Conocer el funcionamiento
Posibilidades del personal (entrenamiento)
2. Aspectos que estudia la I.O.
Programación lineal (modelos de transporte y asignación)
Teoría de inventarios
Teoría de colas (esperas)
Programación no lineal
Programación dinámica, etc.
Simulación (métodos)
3. Orígenes de la I.O.
Es un enfoque científico a la toma de decisiones
Nace en la 2º Guerra Mundial (1937) (ingleses-USA)
A partir de 1951 ya estaban en la industria, empresas, etc. y de ahí ha
seguido desarrollándose.
4. Desarrollo
Información estadística (estandarizado de archivos).
Intercambio de opiniones (ingenieros, economistas, etc.).
Uso científico de los datos (no usar la intuición).
La rapidez basada en el uso de las computadoras.
12
CAPÍTULO II: PROGRAMACIÓN LINEAL
A. INTRODUCCIÓN A LA PROGRAMACIÓN
Durante la Segunda Guerra Mundial, un grupo de científicos fue convocado
en Inglaterra para estudiar problemas de estrategia y de táctica asociados con
la defensa del país.
El objetivo era decidir sobre la utilización más eficaz de recursos militares
limitados.
La convocación de este grupo marcó la primera actividad formal de
investigación operacional.
Los resultados positivos conseguidos por el equipo de investigación
operacional inglesa motivaron a los Estados Unidos a que se inicien
actividades semejantes. A pesar de ser Inglaterra donde se originó la
Investigación Operacional, su propagación se debe principalmente al equipo
de científicos liderada por George B. Dantzig, de los Estados
Unidos, convocada durante la Segunda Guerra Mundial. Al resultado de este
esfuerzo de investigación, concluido en 1947, se dio el nombre de Método
Simplex.
Con el fin de la guerra, la utilización de técnicas de programación atrajo el
interés de diversas otras áreas. La naturaleza de los problemas encontrados
es bastante amplio y compleja, exigiendo, por tanto, un abordamiento que
permita reconocer los múltiplos aspectos involucrados. Una característica
importante de la investigación operacional y que facilita el proceso de análisis
y de decisión es la utilización de modelos. Ellos permiten la experimentación
de la solución propuesta. Esto significa que una decisión puede ser más bien
avaluada y verificada antes de ser efectivamente implementada. La economía
obtenida y la experiencia adquirida por la experimentación justifican el uso de
Investigación Operacional.
13
Con el aumento de la velocidad de procesamiento y cantidad de memoria de
los computadores actuales, tuvimos un gran progreso en Investigación
Operacional. Este progreso es debido también a la larga utilización de
microcomputadoras, que se convirtieron en unidades muy separadas dentro
de empresas. Eso en realidad hace que los modelos desenvueltos por los
profesionales de Investigación Operacional sean más rápidos y versátiles,
además de ser también interactivos, posibilitando la participación del usuario
durante el proceso de cálculo.
Investigación Operacional es un método científico de toma de decisiones. En
líneas generales, consiste en la descripción de un sistema organizado con
auxilio de un modelo, y a través da experimentación con el modelo, en el
descubrimiento de la mejor manera de operar el sistema.
B. PROGRAMACIÓN LINEAL
Un modelo de Programación Lineal (PL) considera que las variables de
decisión tienen un comportamiento lineal, tanto en la función objetivo como
restricciones del problema. En este sentido, la Programación Lineal es una de
las herramientas más utilizadas en la Investigación Operativa debido a que
por su naturaleza se facilitan los cálculos y en general permite una buena
aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Deterministas
(MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que
los parámetros asociados al modelo son conocidos con certeza absoluta, a
diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto
de los parámetros tienen una distribución de probabilidad asociada. Los
cursos introductorios a la Investigación Operativa generalmente se enfocan
sólo en Modelos Deterministas.
14
Supuestos Básicos de la Programación Lineal: Linealidad, Modelos
Deterministas, Variables reales, No Negatividad.3
Programación Lineal es utilizada para analizar modelos donde las
restricciones y la función objetivo son lineales; programación entera se aplica
a modelos que poseen variables enteras (o discretas); programación dinámica
es utilizada en modelos donde el problema completo puede ser descompuesto
en subproblemas menores; programación estocástica es aplicada a una clase
especial de modelos donde los parámetros son descritos por funciones de
probabilidad; finalmente, programación no lineal es utilizada en modelos que
contienen funciones no lineales.
Una característica presente en casi todas las técnicas de programación
matemática es que la solución óptima del problema no puede ser obtenida en
un único paso, sino iterativamente. Inicialmente se escoge una solución inicial
(que generalmente no es la solución óptima).
3 http://www.programacionlineal.net/programacion_lineal.html
15
Un algoritmo es especificado para determinar, a partir de esta, una nueva
solución, que generalmente es superior o anterior. Este paso es repetido hasta
que la solución óptima sea alcanzada (suponiendo que ella existe).
1. Test del modelo y de la solución
Este test es realizado con datos empíricos del sistema. Si hubiera datos
históricos, ellos serán aplicados en el modelo, generando un desempeño
que puede ser comparado al desempeño observado en el sistema. Si el
desvió verificado no fuese aceptable, la reformulación o mismo el abandono
del modelo será inevitable. Caso no haya datos históricos, los datos
empíricos serán anotados con el sistema funcionando sin interferencia,
hasta que el test pueda ser realizado.
2. Establecimiento de controles de solución
La construcción y experimentación con el modelo identifican parámetros
fundamentales para la solución del problema.
Cualquier cambio en los parámetros deberá ser controlado para
garantizar la validez de la solución adoptada.
3. Implementación y seguimiento
En esta fase, la solución será presentada
4. Aplicaciones
a. Problema de la Dieta
(Stigler, 1945). Consiste en determinar una dieta de manera eficiente, a
partir de un conjunto dado de alimentos, de modo de satisfacer
requerimientos nutricionales. La cantidad de alimentos a considerar, sus
características nutricionales y los costos de éstos, permiten obtener
diferentes variantes de este tipo de modelos.
16
Por ejemplo:
Leche (lt.) Legumbre (1
porción)
Naranjas
(Unidad)
Requerimientos
nutricionales
Niacina 3.2 4.9 0.8 13
Tiamina 1.12 1.3 0.19 15
Vitamina C 32 0 93 45
Costo 2 0.2 0.25
Variables de Decisión:
X1: Litros de Leche utilizados en la Dieta
X2: Porciones de Legumbres utilizadas en la Dieta
X3: Unidades de Naranjas utilizadas en la Dieta
Función Objetivo: (Minimizar los Costos de la Dieta) Min 2X1 + 0,2X2 +
0,25X3
Restricciones: Satisfacer los requerimientos nutricionales
Niacina: 3,2X1 + 4,9X2 + 0,8X3 >= 13
Tiamina: 1,12X1 + 1,3X2 + 0,19X3 >=15
Vitamina C: 32X1 + 0X2 + 93X3 >= 45
No Negatividad: X1>=0; X2>=0; X3>=0
La solución Óptima es X1=0, X2=11,4677, X3=0,483871, con Valor Óptimo
V(P)=2,4145.
Se puede verificar en el siguiente enlace la solución4
4 http://www.programacionlineal.net/resolucion.html
17
b. Problema de Dimensionamiento de Lotes
(Wagner y Whitin, 1958). Consiste en hallar una política óptima de
producción para satisfacer demandas fluctuantes en el tiempo, de
modo de minimizar los costos de producción e inventario, considerando
la disponibilidad de recursos escasos.
Considere que una fábrica puede elaborar hasta 150 unidades en cada
uno de los 4 periodos en que se ha subdividido el horizonte de
planificación y se tiene adicionalmente la siguiente información:
Periodos Demandas
(Unidades)
Costo Producción
(US$/Unidad)
Costo de inventario
(US$/Unidad)
1 130 6 2
2 80 4 1
3 25 8 2.5
4 195 9 3
Adicionalmente considere que se dispone de un Inventario Inicial de 15 unidades
y no se acepta demanda pendiente o faltante, es decir, se debe satisfacer toda
la demanda del período.
Variables de Decisión:
Xt: Unidades elaboradas en el período t (Con t =1,2,3,4)
It: Unidades en inventario al final del período t (Con t =1,2,3,4)
Función Objetivo: (Minimizar los Costos de Producción e Inventarios) Min 6X1
+ 4X2 + 8X3 + 9X4 + 2I1 + 1I2 + 2,5I3+ 3I4
18
Restricciones:
Capacidad de Producción por Período: Xt <= 150 (Con t =1,2,3,4)
Satisfacer Demanda Período 1: X1 + I0 - I1 = 130 (I0 = 15)
Satisfacer Demanda Período 2: X2 + I1 - I2 = 80
Satisfacer Demanda Período 3: X3 + I2 - I3 = 125
Satisfacer Demanda Período 4: X4 + I3 - I4 = 195
No Negatividad: Xt >=0, It >=0
Solución Óptima utilizando Solver de MS Excel
X1=115, X2=150, X3=100, X4=150, I1=0, I2=70, I3=45, I4=0. Valor Óptimo
V(P)=3.622,5
Para ver una aplicación de esta herramienta, se puede consultar la referencia 5
c. Problema de Transporte
(Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947)
El problema consiste en decidir cuántas unidades trasladar desde ciertos
puntos de origen (platas, ciudades, etc.) a ciertos puntos de destino
(centros de distribución, ciudades, etc.) de modo de minimizar los costos
de transporte, dada la oferta y demanda en dichos puntos. Se suponen
conocidos los costos unitarios de transporte, los requerimientos de
demanda y la oferta disponible.
Por ejemplo, suponga que una empresa posee dos plantas que elaboran
un determinado producto en cantidades de 250 y 400 unidades diarias,
respectivamente. Dichas unidades deben ser trasladadas a tres centros
de distribución con demandas diarias de 200, 200 y 250 unidades,
respectivamente.
5 http://www.investigacionoperativa.com/programacion_lineal.html
19
Los costos de transporte (en $/unidad) son:
Se requiere formular un modelo de Programación Lineal que permita
satisfacer los requerimientos de demanda al mínimo costo.
Variables de Decisión:
Xij: Unidades transportadas desde la planta i (i=1, 2) hasta el centro de
distribución j (j=1, 2, 3)
Función Objetivo: Minimizar el costo de transporte entre las plantas y los
centros de distribución dado por:
Minimizar 21X11 + 25X12 + 15X13 + 28X21 + 13X22 + 19X23
Restricciones:
Satisfacer los requerimientos de Demanda de los Centros de Distribución:
X11+ X21 = 200
X12 + X22 = 200
X13 + X23 = 250
Sujeto a la Oferta o Capacidad de Producción de las Plantas:
X11+ X12 + X13 = 250
X21 + X22+ X23 = 400
20
No Negatividad:
Xij>= 0 i=1,2 y j=1,2,3
El siguiente diagrama permite una visualización de la situación anterior:
A continuación una descripción de la implementación computacional y resolución
del problema anterior utilizando el complemento Solver de Microsoft Excel:
1. Abrir una Planilla de Cálculo de Excel. Asegúrese de tener instalado el
complemento Solver. Luego construya una planilla como la de la imagen de
referencia. Se han marcado con amarillo las celdas cambiantes (variables de
decisión) y con color azul la celda de la función objetivo.
21
Notar que algunas celdas en la imagen anterior consideran fórmulas:
F7=SUMA(C7:E7)
F8=SUMA(C7:E7)
C9=SUMA(C7:C8)
D9=SUMA(D7:D8)
E9=SUMA(E7:E8)
2. Ingrese la función objetivo, celdas cambiantes y restricciones en la ventana
de Parámetros de Solver. Seleccione también la opción Convertir variables
sin restricciones en no negativas. Si utiliza las mismas celdas de la imagen
anterior, usted debería obtener lo siguiente:
22
3. Seleccione Resolver. Obtendrá la solución al problema y podrá requerir los
Informes de Solver. Finalmente presione Aceptar para obtener el o los
informes de interés.
23
Finalmente, se obtienen los informes de confiabilidad (o sensibilidad) los cuales
entregan información relevante en cuanto a los precios sombra asociados a las
restricciones, intervalos de variación de garantizan la validez del precio sombra,
intervalo de variación para los coeficientes de la función objetivo, etc.
24
Referencia: http://www.investigacionoperativa.com/programacion_lineal.html
C. MÉTODO SIMPLEX
El Método Simplex es un método analítico de solución de problemas de
programación lineal capaz de resolver modelos más complejos que los
resueltos mediante el método gráfico sin restricción en el número de
variables.6
El método Simplex es un procedimiento iterativo que permite mejorar la
solución de la función objetivo en cada paso. El proceso concluye cuando no
es posible continuar mejorando dicho valor, es decir, se ha alcanzado la
solución óptima (el mayor o menor valor posible, según el caso, para el que
se satisfacen todas las restricciones).
6 https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/
25
Partiendo del valor de la función objetivo en un punto cualquiera, el
procedimiento consiste en buscar otro punto que mejore el valor anterior.
Como se verá en el método Gráfico, dichos puntos son los vértices del
polígono (o poliedro o polícromo, si el número de variables es mayor de 2) que
constituye la región determinada por las restricciones a las que se encuentra
sujeto el problema (llamada región factible). La búsqueda se realiza mediante
desplazamientos por las aristas del polígono, desde el vértice actual hasta uno
adyacente que mejore el valor de la función objetivo. Siempre que exista
región factible, como su número de vértices y de aristas es finito, será posible
encontrar la solución.
El método Simplex se basa en la siguiente propiedad: si la función objetivo Z
no toma su valor máximo en el vértice A, entonces existe una arista que parte
de A y a lo largo de la cual el valor de Z aumenta.
Será necesario tener en cuenta que el método Simplex únicamente trabaja
con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o
igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto
habrá que estandarizar las restricciones para que cumplan estos requisitos
antes de iniciar el algoritmo del Simplex. En caso de que después de éste
proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad),
o no se puedan cambiar, será necesario emplear otros métodos de resolución,
siendo el más común el método de las Dos Fases.7
1. Objetivo
Encontrar la mejor distribución posible de los recursos escasos entre las
diversas actividades o tareas, de tal forma que se pueda alcanzar un valor
óptimo del objetivo establecido.
7 http://www.phpsimplex.com/teoria_metodo_simplex.htm
26
2. Características
Existencia de un Objetivo que pueda ser explicitado en términos de las
variables de decisión del problema.
Existencia de Restricciones a la aplicación de recursos, tanto en la
disponibilidad cuanto en el modo de utilización.
Pasos a seguir:
3. Preparando el modelo para adaptarlo al método Simplex
La forma estándar del modelo de problema consta de una función objetivo
sujeta a determinadas restricciones:
Definición de las variables
Relaciones Matemáticas
de las Restricciones
¿Qué queremos saber?
Ecuación de la función
objetivo
¿A qué condiciones
debemos obedecer?
Modelo completo
¿Cómo el objetivo puede
ser escrito en términos de
las variables?
27
Función objetivo: c1·x1 + c2·x2 + ... + cn·xn
Sujeto a: a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0
El modelo debe cumplir las siguientes condiciones:
1. El objetivo consistirá en maximizar o minimizar el valor de la función
objetivo (por ejemplo, incrementar ganancias o reducir pérdidas,
respectivamente).
2. Todas las restricciones deben ser ecuaciones de igualdad (identidades
matemáticas).
3. Todas las variables (xi) deben tener valor positivo o nulo (condición de
no negatividad).
4. Los términos independientes (bi) de cada ecuación deben ser no
negativos.
Hay que adaptar el problema modelado8, a la forma estándar para poder
aplicar el algoritmo del Simplex.
4. Tipo de optimización
Como se ha comentado, el objetivo del método consistirá en optimizar el
valor de la función objetivo. Sin embargo, se presentan dos opciones:
obtener el valor óptimo mayor (maximizar) u obtener el valor óptimo menor
(minimizar).
8 http://www.phpsimplex.com/teoria_modelado_problemas.htm
28
Además, existen diferencias en el algoritmo entre el objetivo de
maximización y el de minimización en cuanto al criterio de condición de
parada para finalizar las iteraciones y a las condiciones de entrada y salida
de la base.
Así:
Objetivo de maximización
Condición de parada: cuando en la fila Z no aparece ningún valor negativo.
Condición de entrada a la base: el menor valor negativo en la fila Z (o el
de mayor valor absoluto entre los negativos) indica la variable Pj que entra
a la base.
Condición de salida de la base: una vez obtenida la variable entrante, la
variable que sale se determina mediante el menor cociente P0/Pj de los
estrictamente positivos.
Objetivo de minimización
Condición de parada: cuando en la fila Z no aparece ningún valor positivo.
Condición de entrada a la base: el mayor valor positivo en la fila Z indica
la variable Pj que entra a la base.
Condición de salida de la base: una vez obtenida la variable entrante, la
variable que sale se determina mediante el menor cociente P0/Pj de los
estrictamente negativos.
No obstante, es posible normalizar el objetivo del problema con el fin de
aplicar siempre los mismos criterios en lo referente a la condición de
parada del algoritmo y a las condiciones de entrada y salida de las
variables de la base.
29
De esta forma, si el objetivo es minimizar la solución, se puede cambiar el
problema a otro equivalente de maximización simplemente multiplicando
la función objetivo por "-1". Es decir, el problema de minimizar Z es
equivalente al problema de maximizar (-1)·Z. Una vez obtenida la solución
será necesario multiplicarla también por (-1).
Ventajas: No hay que preocuparse por nuevos criterios de parada,
condición de entrada y salida de la base ya que se mantienen.
Inconvenientes: En el caso de que la función tenga todos los coeficientes
de sus variables básicas positivos, y además las restricciones sean del
tipo de desigualdad "≤", al hacer el cambio dichos coeficientes quedan
negativos cumpliéndose la condición de parada en la primera iteración (en
la fila del valor de la función objetivo todos los valores son positivos o
cero). Obteniéndose en este caso por defecto un valor óptimo para la
función igual a 0.
Solución: Realmente no existe este problema dado que para que la
solución sea superior a 0 es necesario que alguna restricción tenga
impuesta la condición "≥" (y se trataría de un modelo para el método de
las Dos Fases). En el caso planteado, la solución real debe ser cero.
5. Cambio de signo de los términos independientes
También se ha dicho que los términos independientes (bi) de cada ecuación
deben ser no negativos para poder emplear el método Simplex. A tal fin, si
alguna de las restricciones presenta un término independiente menor que 0
habrá que multiplicar por "-1" ambos lados de la inecuación (teniendo en
cuenta que esta operación también afecta al tipo de restricción).
Ventajas: Con ésta simple modificación de signos en las restricciones
correspondientes se posibilita la aplicación del método Simplex al problema
modelado.
30
Inconvenientes: Puede resultar que en las restricciones donde tengamos que
modificar los signos de las constantes, los tipos de desigualdad fueran "≤"
(quedando tras la operación del tipo "≥") siendo necesario desarrollar el
método de las Dos Fases. Este inconveniente no es controlable, aunque
podría ocurrir el caso contrario y resultar beneficioso si los términos
independientes negativos se presentan en todas aquellas restricciones con
desigualdad de tipo "≥". Si existe alguna restricción del tipo "=" no supondría
ninguna ventaja ni desventaja puesto que siempre sería de necesaria
aplicación el método de las Dos Fases.
6. Normalización de las restricciones
Otra de las condiciones del modelo estándar del problema es que todas las
restricciones sean ecuaciones de igualdad (también llamadas restricciones
de igualdad), por lo que hay que convertir las restricciones de desigualdad o
inecuaciones en dichas identidades matemáticas.
La condición de no negatividad de las variables (x1,..., xn ≥ 0) es la única
excepción y se mantiene tal cual.
Restricción de tipo "≤"
Para normalizar una restricción con una desigualdad del tipo "≤", hay que
añadir una nueva variable, llamada variable de holgura xs (con la
condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con
coeficiente cero en la función objetivo, y sumando en la ecuación
correspondiente (que ahora sí será una identidad matemática o ecuación
de igualdad).
a11·x1 + a12·x2 ≤ b1 a11·x1 + a12·x2 + 1·xs = b1
31
Restricción de tipo "≥"
En caso de una desigualdad del tipo "≥", también hay que añadir una
nueva variable llamada variable de exceso xs (con la condición de no
negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en
la función objetivo, y restando en la ecuación correspondiente.
Surge ahora un problema con la condición de no negatividad con esta
nueva variable del problema. Las inecuaciones que contengan una
desigualdad de tipo "≥" quedarían:
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs = b1
Al realizar la primera iteración con el método Simplex, las variables
básicas no estarán en la base y tomarán valor cero. En este caso la nueva
variable xs, tras hacer cero a x1 y x2, tomará el valor -b1 y no cumpliría la
condición de no negatividad. Es necesario añadir otra nueva variable xr,
llamada variable artificial, que también aparecerá con coeficiente cero en
la función objetivo y sumando en la restricción correspondiente.
Quedando entonces de la siguiente manera:
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs + 1·xr = b1
Restricción de tipo "="
Al contrario de lo que cabría pensar, para las restricciones de tipo "="
(aunque ya son identidades) también es necesario agregar variables
artificiales xr. Como en el caso anterior, su coeficiente será cero en la
función objetivo y aparecerá sumando en la restricción correspondiente.
a11·x1 + a12·x2 = b1 a11·x1 + a12·x2 + 1·xr = b1
En el último caso se hace patente que las variables artificiales suponen
una violación de las leyes del álgebra, por lo que será necesario asegurar
que dichas variables artificiales tengan un valor 0 en la solución final.
32
De esto se encarga el método de las Dos Fases y por ello siempre que
aparezcan este tipo de variables habrá que realizarlo.
En la siguiente tabla se resume según la desigualdad el tipo de variable
que aparece en la ecuación normalizada, así como su signo:
Tipo de desigualdad Tipo de variable que aparece
≥ - exceso + artificial
= + artificial
≤ + holgura
7. Desarrollando el método Simplex
Una vez estandarizado el modelo puede ocurrir que sea necesario aplicar el
método Simplex o el método de las Dos Fases.
Véase en la figura la forma de actuación para llegar a la solución del
problema modelado.
33
34
A continuación, se explican paso a paso los puntos de cada método, concretando
los aspectos a tener en cuenta.
a. Método Simplex
Construcción de la primera tabla:
Las columnas de la tabla están dispuestas de la siguiente forma: la
primera columna de la tabla contiene las variables que se encuentran en
la base (o variables básicas), esto es, aquellas que toman valor para
proporcionar una solución; la segunda columna recoge los coeficientes
que dichas variables básicas tienen en la función objetivo (esta columna
es llamada Cb); la tercera muestra el término independiente de cada
restricción (P0); a partir de ésta aparece una columna por cada una de las
variables de decisión y holgura presentes en la función objetivo (Pj). Para
tener una visión más clara de la tabla, se incluye una fila que contiene los
títulos de cada una de las columnas.
Sobre esta tabla se agregan dos nuevas filas: una de ellas, que lidera la
tabla, donde aparecen los coeficientes de las variables de la función
objetivo, y una última fila que recoge el valor la función objetivo y los
costes reducidos Zj - Cj.
Los costes reducidos muestran la posibilidad de mejora en la solución Z0.
Por este motivo también son llamados valores indicadores.
Se muestra a continuación el aspecto general de la tabla del método
Simplex:
35
Todos los valores incluidos en la tabla vendrán dados por el modelo del
problema salvo los valores de la fila Z (o fila indicadora). Estos se obtienen
de la siguiente forma: Zj = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P0 = bi y
C0 = 0, y en caso contrario Pj = aij.
Se observa, al realizar el método Simplex, que en esta primera tabla
ocupan la base todas las variables de holgura y por ello (todos los
coeficientes de las variables de holgura son 0 en la función objetivo) el
valor inicial de Z es cero.
Por este mismo motivo tampoco es necesario realizar los cálculos de los
costes reducidos en la primera tabla, pudiéndose determinar directamente
como el cambio de signo de los coeficientes de cada variable en la función
objetivo, esto es, -Cj.
Condición de parada:
Se cumple la condición de parada cuando la fila indicadora no contiene
ningún valor negativo entre los costes reducidos (cuando el objetivo es la
maximización), esto es, no existe posibilidad de mejora.
Una vez cumplida la condición de parada, el valor de cada variable que
logra la solución óptima se encuentra en la columna P0, indicándose en
la base a qué variable corresponde dicho valor.
36
Si una variable no aparece en la base, significa que su valor es cero. De
la misma forma el valor óptimo de la función objetivo (Z) se encuentra en
la columna P0, fila Z.
Si no se cumple la condición de parada es necesario realizar una iteración
más del algoritmo, esto es, determinar la variable que se vuelve básica y
la que deja de serlo, encontrar el elemento pivote, actualizar los valores
de la tabla y comprobar si se cumple nuevamente la condición de parada.
Es también posible determinar que el problema no se encuentra acotado
y su solución siempre resultará mejorable. En tal caso no es necesario
continuar iterando indefinidamente y se puede finalizar el algoritmo. Esta
situación ocurre cuando en la columna de la variable entrante a la base
todos los valores son negativos o nulos.
Elección de la variable que entra a la base:
Cuando una variable se vuelve básica, es decir, entra en la base,
comienza a formar parte de la solución. Observando los costes reducidos
en la fila Z, se decide que entra a la base la variable de la columna en la
que éste sea el de menor valor (o de mayor valor absoluto) entre los
negativos.
Elección de la variable que sale de la base:
Una vez obtenida la variable entrante, se determina que sale de la base
la variable que se encuentre en aquella fila cuyo cociente P0/Pj sea el
menor de los estrictamente positivos (teniendo en cuenta que esta
operación se hará únicamente cuando Pj sea superior a 0).
Elemento pivote:
El elemento pivote de la tabla queda marcado por la intersección entre la
columna de la variable entrante y la fila de la variable saliente.
37
Actualización de la tabla:
Las filas correspondientes a la función objetivo y a los títulos
permanecerán inalteradas en la nueva tabla. El resto de valores deberán
calcularse como se explica a continuación:
En la fila del elemento pivote cada nuevo elemento se calcula como:
Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote.
En el resto de las filas cada elemento se calcula:
Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en
Columna Pivote * Nuevo Elemento Fila Pivote).
De esta forma se consigue que todos los elementos de la columna de la
variable entrante sean nulos salvo el de la fila de la variable saliente cuyo
valor será 1. (Es análogo a utilizar el método de Gauss-Jordan para
resolver sistemas de ecuaciones lineales).
8. Problema de aplicación
La Industria Maximuebles fabrica 2 tipos de productos: sillas y mesas.
Los productos presentan los siguientes márgenes de contribución:
Margen de contribución unitaria: sillas=S/.10 y mesas=S/.8
Los productos son procesados por 2 departamentos: Montado y acabado.
Al pasar por esos departamentos, cada unidad consume un número
determinado de horas indicado:
38
Departamento Sillas Mesas Capacidad Máxima
Montado 3 horas 3 horas 30 horas
Acabado 6 horas 3 horas 48 horas
Objetivo: Calcular la cantidad de cada producto para maximizar el margen
de contribución.
Usando el método simplex
P1, P2, …, Pn=Pasos a seguir.
P1: Introducción de las variables de holgura – una para cada ecuación.
P2: Armado del cuadro de coeficientes, incluyendo la FO con los signos
cambiados.
P3: Creación de la solución básica inicial, generalmente dando el valor
de 0 a las variables originales.
P4: Variable que entra en la base:
Aquel que tenga el mayor valor negativo en la fila de la FO transformada.
Cuando no hay más coeficientes negativos en la fila de la FO, la solución
encontrada es óptima.
P5: Variable que sale de la base:
Dividir los términos independientes por los respectivos coeficientes positivos
de la variable que entra.
El menor cociente indica, por la ecuación que ocurre, la variable que debe
salir.
P6: Transformar la matriz, encontrándose la nueva base.
Operaciones:
1. En la variable que ingresó, divida toda la fila por el primer número para
obtener 1.
39
2. En la variable que quedó multiplique por el primer número negativo de la
variable que entró y sume con toda la fila.
3. En la función objetivo multiplique por el primer número negativo de la
variable que ingresó y sume con toda la fila.
9. Ejemplo práctico
MODELO COMPLETO:
Variables: x1=silla y x2=mesa
Función Objetivo (FO):
MAXIMIZAR margen de contribución total
Max 𝟏𝟎𝒙1+𝟖𝒙𝟐, MCT silla + MCT mesa
Restricciones:
Montado 𝟑𝒙𝟏+𝟑𝒙𝟐≤𝟑𝟎
Acabado 6𝒙𝟏+𝟑𝒙𝟐≤48
𝒙1, 𝒙2≥𝟎
Paso 1
COLOCACIÓN DE LAS VAR HOLGURA:
Maximizar 𝐌𝐂𝐓=𝟏𝟎𝒙𝟏+𝟖𝒙𝟐
Restricciones (s.a):
Montado 𝟑𝒙𝟏+𝟑𝒙𝟐+𝒙𝟑 =𝟑𝟎
Acabado 6𝒙𝟏+𝟑𝒙𝟐 +𝒙𝟒=𝟒𝟖
𝒙𝟏, 𝒙𝟐, 𝒙𝟑, 𝒙𝟒 ≥ 𝟎
Regla: Una variable de holgura para cada inecuación.
Paso 2 y 3
Armado del cuadro de coeficientes, incluyendo la FO con los signos cambiados
40
Creación de la solución básica inicial, generalmente dando el valor de 0 a las
variables originales.
Asuma x1 y x2 igual a 0, x3=30, x4=48, MCT=0
Paso 4
Paso 5
41
Paso 6
42
D. MÉTODO SIMPLEX DOS FASES
El método de las Dos Fases se utiliza cuando aparecen variables artificiales
en la forma canónica o estándar del problema.
43
La primera fase trata de resolver el problema auxiliar Z' de minimizar la suma
de las variables artificiales y conseguir que sea cero (con objeto de evitar
incongruencias matemáticas). Una vez resuelto este primer problema, y
siempre y cuando el resultado sea el esperado, se reorganiza la tabla
resultante para utilizarla en la segunda fase sobre el problema original.
En caso contrario el problema no es factible, es decir, no tiene solución y no
será necesario continuar con la segunda fase.9
Fase 1
Esta primera fase es muy similar al método Simplex, con la excepción de la
construcción de la primera tabla, además de la necesidad de estudiar el
resultado obtenido para determinar si se desarrolla la segunda fase.
En tal caso, la última tabla de esta fase será, con algunas modificaciones, la
utilizada como tabla inicial para la segunda fase.
Construcción de la primera tabla:
Se elabora de manera análoga a la tabla inicial del método Simplex, pero
con algunas diferencias.
Como se ha comentado, en esta primera fase se resuelve un problema
auxiliar (la minimización de la suma de las variables artificiales) con una
función objetivo auxiliar. Por lo tanto en la primera fila de la tabla, donde
se muestran los coeficientes de las variables de la función objetivo,
aparecerán todos los términos a cero excepto los coeficientes de variables
artificiales. El valor de cada uno de estos coeficientes es "-1" debido a que
se está minimizando la suma de dichas variables (recuerde que minimizar
Z' es igual que maximizar (-1)·Z').
9 http://www.phpsimplex.com/teoria_metodo_simplex.htm
44
La otra diferencia para la primera tabla radica en que ahora sí es necesario
calcular la fila Z (o fila indicadora).
Siendo Zj = Σ(Cbi·Pj) - Cj para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y
en caso contrario Pj = aij.
Condición de parada y paso a la fase 2:
La condición de parada es la misma que en el método Simplex normal.
Esto es, cuando en la fila indicadora ninguno de los valores de los costes
reducidos es negativo (ya que tal y como se ha planteado el objetivo es la
maximización de (-1)·Z').
Cumplida la condición de parada es necesario determinar si es posible
pasar a la segunda fase para obtener la solución óptima del problema
original. Esto se hace observando el resultado obtenido en la primera fase:
si su valor es 0, significa que el problema original tiene solución y es
posible calcularla, en caso contrario indica que se trata de un problema no
factible y no tiene solución.
45
Fase 2
La segunda fase del método de las Dos Fases se desarrolla exactamente
igual que el método Simplex, con la salvedad de que antes de iniciar las
iteraciones hay que eliminar las columnas correspondientes a las
variables artificiales, y reconstruir la tabla inicial.
Eliminar Columna de variables artificiales:
Si hemos llegado a la conclusión de que el problema original tiene
solución, debemos preparar nuestra tabla para la segunda fase. Este paso
es muy sencillo, se trata únicamente de eliminar las columnas
correspondientes a las variables artificiales.
Construcción de la tabla inicial:
La tabla inicial en este caso se mantiene casi igual a la última tabla de la
primera fase. Únicamente habrá que modificar la fila de la función objetivo
por la del problema original y calcular nuevamente la fila Z (de la misma
forma que en la primera tabla de la fase 1).
A partir de este punto, todas las iteraciones hasta llegar a la solución
óptima del problema no presentan ninguna diferencia con el método
Simplex.
E. Identificando casos anómalos y soluciones
Solución óptima: cuando se cumple la condición de parada y no hay
variables artificiales en la base con valor positivo (los valores se indican en la
columna P0), se ha conseguido la optimización. El valor Z0 actual es la
solución óptima del problema, cumpliéndose para las variables que se
encuentran en la base. Si se trata de un problema de minimización, el valor
óptimo obtenido se multiplicará por "-1".
46
Infinitas soluciones: cumplida la condición de parada, si alguna variable de
decisión no básica tiene un valor 0 en la fila Z, significa que existe otra solución
que aporta el mismo valor óptimo para la función objetivo. Es este caso el
problema admite infinitas soluciones, estando todas ellas comprendidas
dentro del segmento (o porción del plano, región del espacio, etc.
dependiendo del número de variables del problema) definido por A·X1 + B·X2
= Z0. Mediante una nueva iteración y haciendo que la variable de decisión que
tiene el 0 en la fila Z entre en la base se obtendrá otra solución diferente para
el mismo valor óptimo.
Solución ilimitada (no acotada): si toda la columna de la variable que entra
a la base tiene todos sus elementos negativos o nulos se trata de problema
no acotado, es decir, que tiene solución ilimitada. No hay valor óptimo
concreto para la función objetivo sino que a medida que se aumenta el valor
de las variables también se incrementa el valor Z sin violar ninguna restricción.
No existe solución: cuando ningún punto satisface todas las restricciones del
problema se produce la infactibilidad no existiendo ninguna solución posible
para él. En este caso, una vez terminadas todas las iteraciones del algoritmo,
existen en la base variables artificiales cuyo valor es superior a cero.
Empate de variable entrante: cuando se produce un empate en la condición
de decisión de la variable entrante se puede optar por cualquiera de ellas sin
que esto afecte a la solución final. Por contra si influye en el número de
iteraciones necesarias para obtener dicha solución. Se aconseja optar a favor
de las variables básicas ya que ellas son las que formarán parte de la solución
óptima.
Empate de variable saliente: se puede nuevamente optar por cualquiera de
ellas. Sin embargo, a fin de no alargar el problema y evitar la entrada en un
bucle infinito (caso degenerado), se discrimina a favor de las variables de
decisión haciendo que permanezcan en la base. En el caso de estar en la
primera fase del método de las Dos Fases, se optará por sacar de la base las
variables artificiales.
47
Curiosidad en la Fase 1: al finalizar la fase 1, si el problema original tiene
solución, todas las variables artificiales en la fila indicadora deben tener el
valor "1".
¿El elemento pivote puede ser nulo?: No, el elemento pivote siempre será
estrictamente positivo ya que únicamente se realizan los cocientes entre
valores no negativos y mayores que cero (ante un problema de maximización).
1. Ejemplo de aplicación
Una compañía de transporte tiene 3 tipos de camiones, el tipo A tiene 𝟐𝒎𝟑 de
espacio refrigerado y 3𝒎𝟑 de espacio no refrigerado. B tiene 𝟐𝒎𝟑 de esp.
Refrigerado y 1𝒎𝟑 de esp. No refrigerado y el C tiene 𝟑𝒎𝟑 de espacio refrigerado
y 5𝒎𝟑 de espacio no refrigerado. El cliente quiere transportar un producto que
necesita de 𝟐𝟎𝒎𝟑 de área refrigerada y el área no refrigerada sea igual a 𝟏𝟎𝒎𝟑.
La compañía calcula entre 1700 litro de combustible para un viaje con el camión
A, 750 l para el camión B y C 800 l. ¿Cuántos camiones de cada tipo deben ser
usados en el transporte del producto con el menor consumo posible?
PPL:
𝑥1 →Cantidad a ser transportada por camión tipo A
𝑥2 →Cantidad de camión tipo B
𝑥3 →Cantidad de camión tipo C
FO: 𝑚𝑖𝑛 𝐶 = 1700𝑥1 + 750𝑥2 + 800𝑥3
Restricciones:
2𝑥1 + 2𝑥2 + 5𝑥3 ≥ 20 →Disp. Mínimo de espacio.
3𝑥1 + 1𝑥2 + 5𝑥3 = 10 →Disp. Espacio no refrigerado.
Variables de no negativo.
Solución
48
Repare que las restricciones tienen signos de (=) y (≥), en este caso es
necesario realizar transformaciones lineales en estas ecuaciones.
En la restricción del tipo (≥) es equilibrada con una variable de exceso, o sea:
𝟐𝒙𝟏 + 𝟐𝒙𝟐 + 𝟓𝒙𝟑 − 𝒙𝟒 = 𝟐𝟎
La segunda restricción ya está equilibrada.
PPL: 𝒎𝒊𝒏 𝑪 = 𝟏𝟕𝟎𝟎𝒙𝟏 + 𝟕𝟓𝟎𝒙𝟐 + 𝟖𝟎𝟎𝒙𝟑
𝟐𝒙𝟏 + 𝟐𝒙𝟐 + 𝟓𝒙𝟑 − 𝒙𝟒 = 𝟐𝟎
𝟑𝒙𝟏 + 𝟏𝒙𝟐 + 𝟓𝒙𝟑 = 𝟏𝟎
𝒙𝟏, 𝒙𝟐, 𝒙𝟑, 𝒙𝟒 ≥ 𝟎
VB x1 x2 x3 x4 b
? 3 1 5 0 10
? 2 2 5 -1 20
• No hay una matriz identidad para una solución inicial ¿Por qué?
• Repare que en la primera restricción del tipo (=) no hay variable de
holgura, pues la restricción dice que debe ser utilizado exactamente 10𝑚3
de espacio no refrigerado.
• En la segunda restricción del tipo (≥), la variable auxiliar tiene coeficiente
-1.
Paso 1: Variable artificial
49
PPL: 𝒎𝒊𝒏 𝑪 = 𝟏𝟕𝟎𝟎𝒙𝟏 + 𝟕𝟓𝟎𝒙𝟐 + 𝟖𝟎𝟎𝒙𝟑
𝟐𝒙𝟏 + 𝟐𝒙𝟐 + 𝟓𝒙𝟑 − 𝒙𝟒 + 𝑨𝟏 = 𝟐𝟎
𝟑𝒙𝟏 + 𝟏𝒙𝟐 + 𝟓𝒙𝟑 + 𝑨𝟐 = 𝟏𝟎
𝒙𝟏, 𝒙𝟐, 𝒙𝟑, 𝒙𝟒, 𝑨𝟏, 𝑨𝟐 ≥ 𝟎
Técnica de la variable artificial:
VB x1 x2 x3 x4 A1 A2 b
A1 2 2 5 -1 1 1 20
A2 3 1 5 0 0 0 10
• Repare que ya tenemos la matriz identidad que está siendo formada por
las variables artificiales A1 y A2.
• La suma original entre 𝑥1 y 𝑥2 y 𝑥3 igual a 10, se mantendrá solo si la
variable artificial A2 fuera igual a 0. Lo mismo para A1.
• Tenemos que librarnos de A1 y A2, pero ¿cómo conseguir eso?
• Necesito que A1=0 y A2=0.
• Conozco el método simplex para max y min, entonces vamos comenzar
a minimizar la suma A1+A2
Resumiendo:
Organizar una función que sea la suma de las variables artificiales.
Minimice la función utilizando el método Simplex.
Alcanzado el óptimo, o el mínimo de la suma es nulo y está libre de las
variables artificiales.
Caso en que el mínimo de la suma no sea nulo, se concluye que el
sistema de ecuaciones no tiene solución.
50
Este es el primer paso del método.
Función artificial =suma de las variables artificiales.
Min F(A)=A1+A2
VB x1 x2 x3 x4 A1 A2 b
A1 2 2 5 -1 1 0 20
A2 3 1 5 0 0 1 10
F(A) 0 0 0 0 -1 -1 0
• Analizando el cuadro, ¿podemos iniciar el cálculo?
• Acertó, quien dijo que NO.
• En el cuadro estamos leyendo F(A)=0, lo que es errado. Esto sucede
porque las variables artificiales están en la base, pero no tienen
coeficientes nulos en la ecuación de la función.
• Es necesario transformar.
La transformación lineal es realizada de la siguiente manera: Sume a las
ecuaciones que tienen variables artificiales y así se obtendrá coeficientes nulos
para las variables artificiales, que son VB, y el valor de la función será 30.
VB x1 x2 x3 x4 A1 A2 b
A1 2 2 5 -1 1 0 20
51
A2 3 1 5 0 0 1 10
F(A) 0 0 0 0 -1 -1 0
Suma 2+3+0 2+1+0 5+5+0 -1 1+0-1 0+1-1 20+10+0
F(A) 5 3 10 -1 0 0 30
El cuadro está pronto para el cálculo.
Entra en la base x3, pues es el más positivo que estamos a minimizar.
Como: 20/5=4 y 10/5=2
Sale A2, el menor cociente.
Dividir la fila A2 entre 5: L2/5→ 𝐿2
L2 × −5 + 𝐿1 → 𝐿1.
VB x1 x2 x3 x4 A1 A2 b
A1 -1 1 0 -1 1 -1 10
A2 3/5 1/5 1 0 0 1/5 2
F(A) -1 1 0 -1 0 -2 10
Solución no óptima, pues hay coeficientes positivos en la ecuación de la función.
Entra x2 en la base.
Como 10/1=1, 2/(1/5)=10, en este caso escogemos aleatoriamente uno de ellos,
vamos a escoger A1.
52
VB x1 x2 x3 x4 A1 A2 b
x2 -1 1 0 -1 1 -1 10
x3 4/5 0 1 1/5 -1/5 2/5 0
F(A) 0 0 0 0 -1 -1 0
Solución no óptima, pues hay coeficientes positivos en la ecuación de la función.
Entra x2 en la base.
Como 10/1=1, 2/(1/5)=10, en este caso escogemos aleatoriamente uno de ellos,
vamos a escoger A1.
Solución óptima.
Min F(A) implica variables artificiales con valor nulo.
La base óptima de la solución del sistema de ecuaciones. de la forma
padrón. Va ser utilizada para la optimización de la función objetivo.
• Ya reparó que en la ecuación final de la función artificial es igual al del
cuadro inicial, esto sólo ocurre porque el mínimo de F(A) es 0 y todas las
variables artificiales son variables NB.
Paso 2: optimizar la función objetivo
• Del PPL tenemos:
Min 𝐶 = 1700𝑥1 + 750𝑥2 + 800𝑥3
• El 2do paso del método consiste en minimizar esta función, aplicando el
método Simplex en la base óptima obtenida al final del primer paso.
53
VB x1 x2 x3 x4 A1 A2 b
x2 -1 1 0 -1 1 -1 10
x3 4/5 0 1 1/5 -1/5 2/5 0
F(0) -1700 -750 -800 0 0 0 0
• ¿El cuadro está pronto?: NO.
• De X2=10 y X3=0, entonces
• 𝑀𝑖𝑛 𝐶 = 1700 × 0 + 750 × 10 + 800 × 0 = 7500
• Pero, en el cuadro se lee F (0)=0, lo que esta errado. Esto ocurre porque
las variables x1, x2, x3 están en la base pero no tienen coeficiente nulo
en la función.
• Es necesario transformar linealmente la ecuación de la función.
• Unir los coeficientes a anularse a las coordenadas unitarias de las
respectivas VB, coloque a la izquierda de esta VB el simétrico del
coeficiente que tiene en F (0).
• Multiplique las ecuaciones por los valores situados a la izquierda y
sumarlo a la ecuación de la función.
VB x1 x2 x3 x4 b
x2=750 -1 1 0 -1 10
X3=800 4/5 0 1 1/5 0
F(0) -1700 -750 -800 0 0
54
Suma 750*1+800*0-750 750*0+800*1-800 750*1+800*0.2+0 750*10+800*0+0
F(0) 0 0 -590 7500
Solución óptima: pues todos los coeficientes son no negativos (min).
La solución óptima es única, pues solo las VB tienen coeficiente nulo en la
ecuación de la función.
F. Interpretación gráfica del Método Simplex
El método Gráfico o método Geométrico permite la resolución de problemas
sencillos de programación lineal de manera intuitiva y visual. Este método se
encuentra limitado a problemas de dos o tres variables de decisión ya que no
es posible ilustrar gráficamente más de 3 dimensiones.
Aunque en la realidad rara vez surgen problemas únicamente con dos o tres
variables de decisión resulta, sin embargo, muy útil esta metodología de
resolución. Al reproducir gráficamente las situaciones posibles como son la
existencia de una solución óptima única, soluciones óptimas alternativas, la
no existencia de solución y la no acotación, constituye una ayuda visual para
interpretar y entender el algoritmo del método Simplex (bastante más
sofisticado y abstracto) y los conceptos que lo rodean.
Las fases del procedimiento de resolución de problemas mediante el método
Gráfico son las siguientes:
Dibujar un sistema de coordenadas cartesianas en el que cada variable de
decisión esté representada por un eje.
𝑋 = (𝑥2𝑥3𝑥1) = (
1000)
𝐶∗ = 750 ∗ 10 + 800 ∗ 0 = 7500
55
Establecer una escala de medida para cada uno de los ejes adecuada a su
variable asociada.
Dibujar en el sistema de coordenadas las restricciones del problema,
incluyendo las de no negatividad (que serán los propios ejes). Notar que una
inecuación define una región que será el semiplano limitado por la línea recta
que se tiene al considerar la restricción como una igualdad, mientras que si
una ecuación define una región que es la propia línea recta.
La intersección de todas las regiones determina la región factible o espacio
de soluciones (que es un conjunto convexo). Si esta región es no vacía, se
continuará con el paso siguiente. En caso contrario, no existe ningún punto
que satisfaga simultáneamente todas las restricciones, por lo que el problema
no tendrá solución, denominándose no factible.
Determinar los puntos extremos o vértices del polígono o poliedro que forma
la región factible. Estos puntos serán los candidatos para la solución óptima.
Evaluar la función objetivo en todos los vértices y aquél (o aquellos) que
maximicen (o minimicen) el valor resultante determinaran la solución óptima
del problema.
Se proporciona un ejemplo del método Gráfico para comprender con mayor
facilidad su desarrollo y aplicación.
Ejemplo método gráfico
Resolver mediante el método Gráfico el siguiente problema:
Maximizar Z = f(x,y) = 3x + 2y
sujeto a: 2x + y ≤ 18
2x + 3y ≤ 42
56
3x + y ≤ 24
x ≥ 0 , y ≥ 0
1. Inicialmente se dibuja el sistema de coordenadas asociando a un eje la
variable "x" y al otro la "y" (generalmente se asocia 'x' al eje horizontal e
'y' al vertical), como se puede ver en la figura.
2. Se marca en dichos ejes una escala numérica apropiada a los valores que
pueden tomar las variables de acuerdo a las restricciones del problema.
Para ello en cada restricción se hacen nulas todas las variables excepto
la correspondiente a un eje concreto, determinándose así el valor
adecuado para dicho eje. Este proceso se repite para cada uno de los
ejes.
3. A continuación se representan las restricciones. Comenzando con la
primera, se dibuja la recta que se obtiene al considerar la restricción como
igualdad. Aparece representada como el segmento que une A con B y la
región que delimita ésta restricción viene indicada por el color AMARILLO.
Se repite el proceso con las demás restricciones, quedando delimitadas
la región de color AZUL y ROJO para la segunda y tercera restricción
respectivamente.
4. La región factible es la intersección de las regiones delimitadas tanto por
el conjunto de restricciones, como por las condiciones de no negatividad
de las variables, es decir, por ambos ejes de coordenadas. Dicha región
factible está representada por el polígono O-F-H-G-C, de color VIOLETA.
57
Como existe una región factible, se procede a determinar sus puntos extremos,
o vértices del polígono que representa. Estos vértices son los puntos candidatos
a soluciones óptimas. En este ejemplo son los puntos O-F-H-G-C de la figura.
Finalmente, se evalúa la función objetivo (3x + 2y) en cada uno de esos puntos
(resultado que se recoge en la tabla siguiente). Como el punto G proporciona el
mayor valor a la función Z y el objetivo es maximizar, tal punto constituye la
solución óptima: Z = 33 con x = 3 e y = 12.
Punto extremo Coordenadas (x,y) Valor objetivo (Z)
O (0,0) 0
C (0,14) 28
G (3,12) 33
H (6,6) 30
F (8,0) 24
58
G. Comparación del método Gráfico y el método Simplex
Las sucesivas tablas construidas durante el método Simplex van
proporcionando el valor de la función objetivo en los distintos vértices de la
región factible, ajustándose, a la vez, los coeficientes de las variables iniciales
y de holgura.
En la tabla inicial se ha calculado el valor de la función objetivo en el vértice
O, cuyas coordenadas (0,0) se corresponden con el valor que tienen las
variables básicas, siendo el resultado 0.
59
La variable que entra a la base en el método Simplex determina hacia qué
nuevo vértice se realiza el desplazamiento. En este ejemplo, como entra P1
(correspondiente a 'x'), el desplazamiento se lleva a cabo por la arista OF
hasta llegar al vértice F, donde se calcula el valor que toma la función Z. Este
paso se produce en la segunda iteración del método Simplex, mostrado en la
Tabla II. En ella se ha calculado el valor que corresponde al vértice F
obteniéndose un valor Z = 24 para la función.
60
Se realiza un nuevo desplazamiento por la arista FH, hasta llegar a H (datos
en la Tabla III). En esta tercera iteración se calcula el valor de la función en el
vértice H, obteniéndose Z = 30.
Se continúa el proceso a través de la arista HG, hasta llegar al vértice G. Los
datos obtenidos se reflejan en la Tabla IV. En este punto acaba el proceso,
pudiéndose comprobar que la solución no mejora al desplazarse por la arista
GC hasta el vértice C (no supera el valor actual de la función).
61
El valor máximo de la función objetivo es 33, y corresponde a los valores x =
3 e y = 12 (coordenadas del vértice G).
Con el método Gráfico es necesario calcular el valor de la función objetivo en
todos los vértices de le región factible, mientras que el método Simplex acaba
en cuanto halla el valor óptimo.
62
H. SOLVER
1. ¿Qué es Solver?
El Solver hace parte de un conjunto de programas, algunas veces llamado
de herramientas del análisis hipotética. Con el Solver Ud. puede localizar un
valor inicial para una fórmula en una celda llamada de celda de destino (en
una planilla). El Solver trabaja con un grupo de celdas relacionadas directa
o indirectamente con la fórmula en la celda de destino. El Solver ajusta los
valores variables que Ud. especifica en las celdas – llamadas de celdas
ajustables – para producir el resultado en la celda de destino. Ud. puede
aplicar restricciones, para restringir los valores que el Solver podrá usar en
el modelo y las restricciones al mismo tiempo pueden afectar la fórmula del
destino. Podremos visualizar mejor a través de ejemplos.
Si tienes la necesidad de realizar un pronóstico que involucra más de una
variable, puedes utilizar Solver en Excel. Este complemento ayudará a
analizar escenarios de negocio multivariables y de optimización.
2. Complemento SOLVER para Excel (2013 y posteriores)
Solver es un complemento de Excel que nos ayuda a trabajar con modelos
de negocio y nos permite resolver problemas lineales y no lineales.
Solver está incluido dentro de Excel pero se encuentra desactivado de
manera predeterminada.
Seguimos las capturas de pantalla:
En la figura 1 observamos que en datos no existe el complemento Solver
(puntero del mouse), entonces debemos activar o habilitar.
63
Figura 1
En la Figura 2 vamos a archivo
Figura 2
En la Figura 3 escogemos opciones
Figura 3
64
En la Figura 4, escogemos complementos
Figura 4
En la Figura 5 hacemos clic a ir
Figura 5
65
En la Figura 6 seleccionamos Solver y aceptar.
Figura 6
En la Figura 7 vemos el complemento ya añadido
Figura 7
En la Figura 8 podemos ver los parámetros que se necesitan, según las
condiciones del algún problema a resolver.
66
Figura 8
3. Ejemplo de uso de Solver
El ejemplo es el siguiente. Tengo un establecimiento de venta de pizzas que
ofrece dos tipos de pizza tradicionales, Pepperoni ($30) y Vegetariana ($35)
además de la pizza especial Suprema ($45). No sabemos cuál es el potencial
de ingresos del establecimiento y tampoco el énfasis que se debería de dar
a cada tipo de pizza para maximizar las ventas.
Antes de realizar el análisis debemos considerar las siguientes condiciones.
Dada nuestra capacidad de producción solamente podemos elaborar 150
pizzas al día. Otra condición es que no podemos exceder de 90 pizzas
tradicionales (Pepperoni y Vegetariana) y además, al no haber muchos
vegetarianos en el área, estimamos vender un máximo de 25 pizzas
vegetarianas al día. Otra condición a considerar es que solamente podemos
comprar los ingredientes necesarios para producir 60 pizzas Suprema por
día.10
10 https://exceltotal.com/utilizando-excel-solver/
67
Con esta información elaboraré la siguiente hoja de Excel:
Observa que en los datos están representadas todas las reglas de negocio
del establecimiento. Para cada tipo de pizza he colocado el total de pizzas a
vender (por ahora en cero), el subtotal de cada una, así como el total de
ventas que está formado por la suma de los subtotales. Además bajo el título
Restricciones he colocado las condiciones previamente mencionadas.
Algo muy importante es establecer las equivalencias para las restricciones.
Por ejemplo, una restricción es que el total de pizzas no puede exceder de
150, pero Excel no necesariamente sabe lo que significa “Total de pizzas”,
así que he destinado una celda para especificar que el total de pizzas es la
suma de las celdas B2+B6+B10. Lo mismo sucede para explicar lo que
significa Pizzas Tradicionales.
Los datos ya están listos para utilizar Solver, así que debes ir a la ficha Datos
y hacer clic en el comando Solver donde se mostrará el cuadro de diálogo
68
Parámetros de Solver.
En nuestro ejemplo lo que queremos maximizar son las ventas totales por lo
que en el cuadro de texto Establecer objetivo está especificada la celda
$E$1 y por supuesto seleccioné la opción Máx. El otro parámetro importante
son las celdas de variables que en nuestro ejemplo son las pizzas a vender
para cada uno de los diferentes tipos.
Finalmente observa cómo en el cuadro de restricciones están reflejadas las
condiciones de venta del establecimiento. Pon especial atención a la manera
en que se han utilizado las equivalencias que son las celdas $E$10 y $E$11.
69
Todo está listo para continuar. Solamente debes hacer clic en el botón
Resolver y Excel comenzará a calcular diferentes valores para las celdas
variables hasta encontrar el valor máximo para las ventas totales. Al término
del cálculo se mostrará el cuadro de diálogo Resultados de Solver.
Solamente haz clic en Aceptar para ver los resultados en la hoja de Excel.
70
Excel ha hecho los cálculos para saber que, con las restricciones
establecidas, tendremos un valor máximo de venta total de $5,525. Ahora
fácilmente podrías cambiar los valores de las restricciones y volver a efectuar
el cálculo con Solver para observar el comportamiento en las ventas.
I. DUALIDAD EN PROGRAMACIÓN LINEAL
Los problemas abordados hasta entonces se consideran problemas primales
dado que tienen una relación directa con la necesidad del planteamiento, y
sus resultados responden a la formulación del problema original; sin embargo
cada vez que se plantea y resuelve un problema lineal, existe otro problema
ínsitamente planteado y que puede ser resuelto, es el considerado problema
dual, el cual tiene unas importantes relaciones y propiedades respecto al
problema primal que pueden ser de gran beneficio para la toma de decisiones.
Los problemas primales y duales se encuentran ligados por una serie de
relaciones, saber la existencia de estas puede ser considerado de gran
utilidad para la resolución de problemas que parecen no factibles, o que no
pueden ser resueltos mediante un método en particular.
1. Relaciones entre problemas primales y duales
El número de variables que presenta el problema dual se ve determinado
por el número de restricciones que presenta el problema primal.
El número de restricciones que presenta el problema dual se ve
determinado por el número de variables que presenta el problema primal.
Los coeficientes de la función objetivo en el problema dual corresponden
a los términos independientes de las restricciones (RHS), que se ubican
del otro lado de las variables.
71
Los términos independientes de las restricciones (RHS) en el problema
dual corresponden a los coeficientes de la función objetivo en el problema
primal.
La matriz que determina los coeficientes técnicos de cada variable en
cada restricción corresponde a la transpuesta de la matriz de coeficientes
técnicos del problema primal.
El sentido de las igualdades y desigualdades se comporta según la tabla de
TUCKER, presentada a continuación.11
Ejemplo:
1. Max.: 𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3
Sujeto a:
8𝑥1 + 6𝑥2 + 19𝑥3 ≤ 19
5𝑥1 + 2𝑥2 + 3𝑥3 ≤ 10 → (Primal)
𝑥1, 𝑥2, 𝑥3 ≥ 0
11 https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/dualidad-en-programaci%C3%B3n-lineal/
72
Min. 𝑤 = 19𝑦1 + 10𝑦2
Sujeto a:
8𝑦1 + 5𝑦2 ≥ 3
6𝑦1 + 2𝑦2 ≥ 4 → (Dual)
19𝑦1 + 3𝑦2 ≥ 5
𝑦1, 𝑦2 ≥ 0
2. Max.: 𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3
Sujeto a:
8𝑥1 + 6𝑥2 + 19𝑥3 ≤ 19
(*) 5𝑥1 + 2𝑥2 + 3𝑥3 = 10 → (Primal)
𝑥1, 𝑥2, 𝑥3 ≥ 0
Tomando la igualdad (*)
Si a=b → a ≥ b ^ b ≤ a
5𝑥1 + 2𝑥2 + 3𝑥3 = 10 <==> {5𝑥1 + 2𝑥2 + 3𝑥3 ≤ 105𝑥1 + 2𝑥2 + 3𝑥3 ≥ 10
→ {5𝑥1 + 2𝑥2 + 3𝑥3 ≤ 10
−5𝑥1 − 2𝑥2 − 3𝑥3 ≤ −10
Luego tenemos lo siguiente:
Max.: 𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3
Sujeto a:
8𝑥1 + 6𝑥2 + 19𝑥3 ≤ 19
5𝑥1 + 2𝑥2 + 3𝑥3 ≤ 10
−5𝑥1 − 2𝑥2 − 3𝑥3 ≤ −10
73
Y la forma Dual:
Min.: 𝑤 = 19𝑢1 + 10𝑢2 − 10𝑢3
Sujeto a:
8𝑢1 + 5𝑢2 − 5𝑢3 ≥ 3
6𝑢1 + 2𝑢2 + 2𝑢3 ≥ 4
19𝑢1 + 3𝑢2 − 3𝑢3 ≥ 5
𝑢1, 𝑢2, 𝑢3 ≥ 0
Definamos:
𝑢1 = 𝑦1
𝑢1 − 𝑢3 = 𝑦2
∴
Min.: 𝑤 = 19𝑦1 + 10𝑦2
Sujeto a:
8𝑦1 + 5𝑦2 ≥ 3
6𝑦1 + 2𝑦2 ≥ 4
19𝑦1 + 3𝑦2 ≥ 5
𝑦1 ≥ 0, pero 𝑦2 no tiene restricción de signo
74
J. ANÁLISIS DE SENSIBILIDAD
El análisis de sensibilidad o postoptimal para los modelos de Programación
Lineal, tiene por objetivo identificar el impacto que resulta en los resultados
del problema original luego de determinadas variaciones en los parámetros,
variables o restricciones del modelo, sin que esto pase por resolver el
problema nuevamente.12
Min.: –𝑍 − 𝑥1 − 0.8𝑥2 − 1.2𝑥3 = 0
Sujeto a:
𝑥1 + 𝑥2 + 2𝑥3 + 𝑥4 = 200𝑥1 + 2𝑥2 + 𝑥3 + 𝑥5 = 160
𝑥1, … . . , 𝑥5 ≥ 0
𝑥1, 𝑥2 → 𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑑𝑒 𝐻𝑜𝑙𝑔𝑢𝑟𝑎
En forma matricial:
Min.: −𝑍 + 𝐶. �⃗� = 0
Sujeto a: 𝐴�⃗� = �⃗⃗�
Donde:
𝐶 = (−1;−0.8;−1.2; 0; 0)
�⃗⃗� = (2001600
)
𝐴 = (1 1 21 2 1
1 00 1
)
Haciendo el Cuadro Simplex:
12 http://www.programacionlineal.net/sensibilidad.html
75
S.O. (120, 0, 40, 0, 0)
𝑍 = −1𝑥120 − 1.2𝑥40 = −168
= (−1.2; −1) (40120
)
Definimos una Matriz 𝐵 = (�⃗�3, �⃗�1)
Esta Matriz se forma con las columnas de la Matriz A original, considerando
las variables básicas finales en el orden vertical (𝑥3𝑥1)
O sea:
𝐵 = (2 11 1
)
𝐵−1 = (1 −1−1 2
)
Definamos �⃗⃗�, como el vector de los coeficientes b finales en orden vertical:
�⃗⃗� = (40120
)
76
Hagamos un cálculo:
𝐵−1 𝑏 = (1 −1−1 2
)
(
40⏞200
120⏟160
𝑂𝑟𝑖𝑔𝑖𝑛𝑎𝑙)
= (40120
)
Entonces:
�⃗⃗� = 𝐵−1𝑏
𝑆𝑖𝑒𝑚𝑝𝑟𝑒 𝑠𝑒 𝑐𝑢𝑚𝑝𝑙𝑒𝑏 → 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙
�⃗⃗� → 𝑓𝑖𝑛𝑎𝑙
(No depende de C)
Ahora:
𝐵−1 𝐴 = (1 −1−1 2
) (1 1 21 2 1
1 00 1
) = (0 −1 11 3 0
1 −1−1 2
)
Entonces:
𝐴 = 𝐵−1𝐴 → (𝐴 → 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙
𝐴 → 𝑓𝑖𝑛𝑎𝑙)
Se define:
𝛿 = (𝐶3, 𝐶1)
El vector 𝛿 se forma considerando los coeficientes C originales
correspondientes a las variables básicas finales en el orden vertical:
Luego:
𝛿 = (−1.2; −1)
77
Hagamos el cálculo: 𝐶 = 𝐶
𝐶 − 𝛿 𝐵−1 𝐴 =? ? ?
𝐶—(1.2; −1) (0 −1 11 3 0
1 −1−1 2
)
= (−1; −0.8; −1.2; 0; 0) − (−1; −1.8; −1.2; −0.2; 0.3)
= (0, 1, 0, 0.2, 0.8) = 𝐶𝑓𝑖𝑛𝑎𝑙 = 𝐶
Entonces:
𝐶 = 𝐶 − 𝛿 𝐵−1 𝐴 → (𝐶 → 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙
𝐶 → 𝑓𝑖𝑛𝑎𝑙)
(No depende de b)
También:
𝑍𝑂𝑝𝑡𝑖𝑚𝑜 = 𝛿�⃗⃗�
El Análisis de Sensibilidad permite, basado en la solución del PPL original,
encontrar la solución de un problema modificado por cambios discretos en los
parámetros del problema original.
a) Cambio en b
𝑏 → 𝑏 + ∆𝑏
Como 𝐶 no cambia, entonces la solución sigue siendo óptima siempre
que sea factible.
La condición de factibilidad sería:
Nuevo �̅� = �̿� = 𝐵−1(𝑏 + ∆𝑏)
= 𝐵−1𝑏 + 𝐵−1∆𝑏
�̿� = �̅� + 𝐵−1∆𝑏
78
Si �̿� ≥ 0 → está bien (sigue siendo factible)
Si no es así, entonces la solución no sigue siendo factible
Ejemplo:
1. ¿Cuánto puede variar b1 para que la solución siga siendo la misma? En
nuestro problema anterior b1 = 200
∆𝑏 = (∆𝑏1∆𝑏2
) = (∝0)
�̿� = (40120
) + (1 −1−1 2
) (∝0) = (
40+∝120−∝
) ≥ 0
Entonces:
40 ≤∝≤ 120160 ≤ 𝑏1 ≤ 320
¿Qué sucede si No se cumple la condición de factibilidad?
i) Cambia �⃗⃗� 𝑝𝑜𝑟 �̿� en el último cuadro Simplex
ii) Multiplicar por (-1) las filas con coeficientes b negativo
iii) Agregar las variables artificiales necesarias
iv) Hacer una Fase I para eliminar las variables artificiales
v) Hacer una Fase II
Si esto fuese demasiado largo, conviene hacer el problema desde el principio.
Sea ∝= 200
→ �̿� = (240−80
)
79
FASE II
f.o. –𝑍 − 𝑥1 − 0.8𝑥2 − 1.2𝑥3 = 0
De la 1ra. Ecuación del último cuadro (eliminado x6)
𝑥1 + 2𝑥2 + 𝑥3 + 𝑥5 = 160
∴
𝑀𝑖𝑛.−𝑍 + 0.2𝑥1 + 1.6𝑥2 + 1.2𝑥5 = 192
Como todos los coeficientes son positivos, estaremos en la solución óptima:
→ 𝑆.𝑂.= (0,0,160,80,0)𝑍𝑜𝑝𝑡. = −192
¿Cuánto varia Z, cuando se cumple la condición de factibilidad?
Antiguo 𝑍𝑜𝑝𝑡. = 𝛿. �̅�
Nuevo 𝑍𝑜𝑝𝑡. = 𝛿. �̅� = 𝛿. (�̅� + 𝐵−1∆𝑏)
= 𝛿. �̅� + 𝛿𝐵−1∆𝑏⏟ ∆𝑧
𝑍𝑜𝑝𝑡. = 𝑍𝑜𝑝𝑡. + ∆𝑧
80
b) Cambio en C
𝐶 → 𝐶 + ∆𝐶
→ 𝛿 → 𝛿 + ∆𝛿 (𝛿 𝑑𝑒𝑝𝑒𝑛𝑑𝑒 𝑑𝑒 𝐶)
𝑛𝑢𝑒𝑣𝑜 𝐶̅ = 𝐶̿ = (𝐶 + ∆𝐶) − (𝛿 + ∆𝛿 )𝐵−1𝐴
= 𝐶 − 𝛿𝐵−1𝐴 + ∆𝐶 − 𝐴𝛿𝐵−1𝐴
𝐶̿ = 𝐶̅ + ∆𝑐 − ∆𝛿𝐵−1𝐴
Ahora sí:
𝐶̿ ≥ 0, la solución sigue siendo óptima ya que los cambios en C no
implican en los cambios en b.
Si algún componente de 𝐶̿ < 0, habrá que continuar con la Fase II
Antiguo 𝑍𝑜𝑝𝑡𝑖𝑚𝑜 = 𝛿. �̅�
Nuevo 𝑍𝑜𝑝𝑡𝑖𝑚𝑜 = (𝛿 + ∆𝛿)�̅�
= 𝛿�̅� + ∆𝛿�̅�⏟∆𝑧
𝑍𝑜𝑝𝑡. = 𝑍𝑜𝑝𝑡. + ∆𝑧
Ejemplo: (del ejemplo anterior)
Supongamos que 𝐶2 (−0.8) → −2
∆𝐶 = (0,−1.2, 0, 0, 0)
∆𝛿 = (0,0)
∴
𝐶̿ = 𝐶̅ + ∆𝐶 = (0,1,0,0.2,0.8) + (0,−1.2,0,0,0) = (0,−0.2, 0, 0.2, 0.8) ≥ 0
Como hay un 𝐶̿ < 0
Fase II:
81
c) Cambio en A
Los cambios en la Matriz A pude ser originados de 3 formas:
- Cambios en los coeficientes 𝑎𝑖𝑗
- Nuevas filas (se agregan restricciones)
- Nuevas columnas (se agregan variables)
Los dos primeros cambios son más difíciles de analizar y en general es
preferible a nuestro nivel resolver el nuevo problema.
Aquí analizaremos el 3er. caso:
Supongamos que a nuestro problema le agregamos nuevas variables (en
nuestro ejemplo 𝑥6 + 𝑥 +⋯) con sus respectivos C, al finalizar el cuadro
Simplex sus coeficientes Ci estarán dados por:
𝐶�̅� = 𝐶𝑖 − 𝛿𝐵−1�⃗�𝑖
82
Si 𝐶�̅� ≥ 0 entonces la solución seguirá siendo óptima (𝐶𝑖, … 𝐶5 ≥ 0). En
caso contrario se agregan nuevas columnas al último cuadro simplex y se
continúa con la Fase II.
Por ejemplo:
Agregamos 𝑥6 (𝑐6 = 𝛽) �⃗�6 = (21.5)
𝑐6 = 𝛽 − (1.2, −1) (1 −1−1 2
) (21.5)
= 𝛽 − (−1.2, −1) (0.51)
𝑐6 = 𝛽—(−1.6) = 𝛽 + 1.6 ≥ 0 𝑠𝑖 𝛽 ≥ −1.6
Si 𝛽 + 1.6 ≤ 0 → habrá que hacer Fase II (𝛽 ≤ −1.6)
Así: 𝛽 = −2 → 𝑐6 = −0.4
83
84
CAPÍTULO III: MODELOS DE PERT-CPM
Se han resuelto con éxito diversos problemas industriales, y administrativos con
la ayuda de modelos y técnicas cuantitativas los cuales se conocen como redes.
Estos problemas incluyen la construcción de una presa; la determinación de la
ruta de transporte más económica o más corta entre dos lugares; la construcción
de un avión; la planeación, programación y control de la construcción de armas
militares; la determinación política de flujo máximo y de expansión óptima para
un sistema de gasoductos; el implante de un nuevo sistema de computación; y
el diseño, introducción y comercialización de un producto nuevo. Aquí
centraremos el estudio en problemas que pueden clasificarse como
administración de proyectos.13
PERT
Program Evaluations and Review Technique. (Técnica de revisión y evaluación
de programas)
CPM
Critical Path Method (Metodode la ruta crítica).
Veremos en forma específica como se utiliza el PERT para determinar:
1. Fecha general esperada de terminación de un proyecto.
2. Fechas necesarias de inicio o término de tareas específicas que conforman
un proyecto.
3. Identificar las tareas críticas.
Veremos en forma específica como se utiliza el CPM para determinar la forma
en que puede reducirse el tiempo general de terminación de un proyecto.
13 xa.yimg.com/kq/groups/21880819/649259048/name/index.doc
85
ASPECTOS GENERALES PERT
PERT se desarrolló en la década de 1950 y se utilizó en forma amplia en la
administración de proyectos militares de investigación y desarrollo.
Su primera aplicación importante fue en el proyecto de los misiles Polaris para la
U.S. Navy.
El PERT fue desarrollado específicamente por el Departamento de la Defensa
de los Estados Unidos de Norteamérica para dar apoyo a la planeación,
programación y control de una gran cantidad de trabajos (actividades) asociados
con el proyecto.
PERT también se ha implementado y utilizado en la industria de la construcción,
empresas industriales, instalaciones de activos fijos, el diseño de plantas, la
planeación y la administración de programas de investigación y desarrollo, etc.
Una característica principal del PERT es que puede manejar las incertidumbres
que existen en los pronósticos de tiempos para determinar diversas tareas
ASPECTOS GENERALES CPM
CPM fue desarrollado independientemente de PERT, pero está estrechamente
relacionado con éste, se refiere básicamente a los intercambios entre el costo de
un proyecto y su fecha de terminación.
Se aboca a la reducción del tiempo necesario parta concluir una tarea o
actividad, utilizando más trabajadores y/o recursos, lo cual, en la mayoría de los
casos significa mayores costos.
Con CPM, se supone que el tiempo necesario para concluir las diversas
actividades del proyecto se conoce con certidumbre, al igual que la cantidad de
recursos que se utilizan.
86
Al principio ambas técnicas se utilizan en forma independiente, pero, en la
actualidad, ha desaparecido en gran medida la distinción de uso entre PERT y
CPM. La mayoría de las versiones computarizadas de las técnicas incluyen
opciones para manejar incertidumbres en los tiempos de las actividades, así
como también análisis de intercambios de tiempos y costos. Además gran parte
de la literatura actual se refiere a la técnica en forma colectiva como PERT/CPM.
TERMINOLOGIA PERT/CPM
Definición de actividades y relación de procedencia
La primera parte del proceso PERT/CPM consiste en identificar todas las tareas
o actividades asociadas con el proyecto y sus interrelaciones. Veamos un
ejemplo, un proyecto de un ajuste general de un motor.
Código de
actividad
Descripción de la actividad Predecesores
inmediatos
A Sacar y desarmar motor ------
B Limpiar y pintar la base A
C Rebobinar la armadura A
D Reemplazar anillos A
E
Ensamblar e instalar el motor en la base
B, C, D.
Para el ejemplo se requieren de 5 actividades; es evidente que el número de
actividades variará según el tipo de proyecto.
En cualquier caso, el punto clave es tener, en esta etapa de planeación, una lista
precisa y exhaustiva de actividades (y las relaciones correctas de precedencia
entre ellas).
87
Además cabe destacar en el ejemplo anterior se tiene una columna de
“Predecesores inmediatos”. Para cada actividad determinada, deben terminarse
todas las precedentes inmediatas antes que poder comenzar esa actividad. En
el ejemplo, las actividades B, C y D no pueden comenzar sino hasta que la
actividad A se haya terminado.
ESTRUCTURA DE RED
Una vez que se ha elaborado una lista completa y precisa de actividades y de
sus predecesoras, es posible ilustrar en forma gráfica sus relaciones. Antes del
desarrollo de PERT se utilizaban diagramas de barras que fueron diseñados por
H.L. Gantt, y a los que con frecuencia se denominaba grafica o carta Gantt.
Ejemplo
1. Características
Conceptualmente correcta
Poco clara la relación de precedencia (ejemplo ¿las actividades E y F
dependen de B o D? ¿La actividad D depende de que se termine A y C,
sólo A, solo C o ninguna de ellas?
1 3 4 5 2 6 7 8 9
A
C
D
E
F
G
H
B
TIEMPO (SEMANAS)
ACTIVIDADES
88
2. Diagrama de red
Ejemplo
a. Características
La red consta de diversos círculos (1 al 6) e interconectadotes por flechas
(A, B, C, D y E). En terminología de redes, los círculos se denominan nodos,
y las flechas que los conectan se denominan ramas o arcos. En una red
particular como la PERT/CPM, las flechas o ramas representan actividades
y los círculos o nodos se denominan eventos. Las actividades implican
tiempo y por lo general consumen recursos como mano de obra, material o
dinero. Los eventos no consumen ni tiempo ni recursos sino que, más bien,
sirven como “puntos de referencia del proyecto y representan los puntos
lógicos de conexión para asociar las diversas actividades.
Si realizamos una comparación de la carta Gantt y la red, vemos claramente
que en esta última las precedencias están representadas apropiadamente.
3
2 5 6
4
REBOBINAR LA
ARMADURA
FICTICIA
ENSAMBLAR
E INSTALAR
EL MOTOR
EN LA BASE
SACAR
Y
DESARMAR
LIMPIAR
Y PINTAR
D
C A
B
E 1
FICTICIA
Reemplazar
Los anillos
89
b. Elaboración de la red
(Observando la tabla en que se listan las actividades y sus relaciones de
precedencia, y el diagrama de red podemos inferir que su elaboración es
bastante simple. ¡CORRECTO!)
No existe procedimiento secreto para elaborar con éxito una red adecuada;
sin embargo, existen diversas reglas que deben tomarse en cuenta, al igual
que algunas “sugerencias” que pueden facilitar la tarea de elaborar la red.
1. Antes de que pueda comenzar una actividad, todas las actividades
precedentes deben haber terminado.
2. Las flechas indican sólo precedencia lógica; ni su longitud ni su dirección
tienen significado.
3. Cada flecha (actividad) debe comenzar y terminar en un nodo de evento.
4. Ningún par de nodos de la red puede estar directamente conectado por
más de una flecha.
5. Cuando se enumeran los nodos es aconsejable, y en particular en una red
grande, utilizar múltiplos de 10 para que sea fácil incorporar cualquier
cambio o adicionen futuros.
6. Todas las flechas de la red deben estar dirigidas, más o menos, de
izquierda a derecha.
7. La clasificación de las actividades no debe ser más detallado que lo que
se requiere para representar un plan de acción lógico y claramente
definido.
Uno de los errores comunes que se cometen en la lógica de las redes es
colocar las actividades en la red con base en algún sentido del tiempo.
Ejemplo:
90
c. Actividades ficticias
Si observamos el diagrama anterior tenemos dos actividades ficticias, las
cuales se representan por flechas punteadas, estas consumen cero tiempo
y cero recursos. Se utilizan las actividades ficticias para mostrar relaciones
correctas entre actividades y/o para evitar tener que conectar en forma
directa dos nodos a través de más de una flecha.
3 2 4
7
PONER LA
DIRECCION EN
INSERTAR LOS
CHEQUES EN
PONER EN
EL CORREO
EXAMINAR LAS
FACTURAS
ELABORAR
LOS CHEQUES
1
COLOCAR LAS
ESTAMPILLAS
6 5
DIAGRAMA SECUENCIAL DE RED PARA PAGAR FACTURAS
3
2
4
7
PONER
DIRECCION EN
SOBRES
INSERTAR CHEQUES EN
SOBRES
PONER
SOBRE CORREO EXAMINAR LAS FACTURAS
ELABORAR
CHEQUES
1
PONER
ESTAMPILLA
6
5
ARTIFICIAL
ARTIFICIAL
91
ANALISIS DE UNA RED PERT/CPM
1. Sharp Company
Código de
actividad
Descripción de la
actividad
Predecesores
inmediatos
Tiempo esperado
para terminar
(semanas)
A Diseñar producto --- 6
B Diseñar el envase --- 2
C Ordenar y recibir los
materiales para el
producto
A
3
D Ordenar y recibir los
materiales para el
envase
B
3
E Fabricar el producto C 4
F Fabricar el envase D 3
G Envasar el producto E 6
92
H Prueba de mercado
del producto
F
4
I Prueba de mercado
del envase
G, H
1
J Entregar a los
distribuidores
I 2
2. Cálculos básicos de la programación
Una vez elaborada la red PERT/CPM, puede concentrarse la atención en
determinar la fecha esperada de terminación para el proyecto y el programa
de actividades.
3. Importancia de conocer la fecha de término
Competencia entre varias empresas
Si se opera en base a incentivos por fecha de término.
93
Si sumamos todos los tiempos esperados de las actividades de la tabla, se
tiene 34 semanas como duración del proyecto.
4. Ruta critica
Se calcula la duración del proyecto determinando la ruta crítica (camino
crítico) para la red.
Toda red tiene dos o más rutas, una o más de las cuales serán críticas.
Analicemos el caso de la Sharp Company
Las actividades A, C, E, G, I y J forman una ruta que conecta los nodos 1, 2,
3, 4, 8, 9 y 10 de la red.
Las actividades B, D, F, H, I y J, forman una ruta que conecta los nodos 1,
5, 6, 7, 8, 9 y 10 de la red.
Puesto que la terminación de un proyecto requiere que se terminen todas las
rutas de la red, la duración de la ruta más larga de la red es la ruta crítica.
5. Para el caso de la Sharp Company.
La ruta ACEGIJ requiere 22 semanas (RUTA CRITICA)
La ruta BDFHIJ requiere 15 semanas.
Si se demora cualquier actividad sobre la ruta crítica, se demora el proyecto
completo. Por lo tanto, las actividades que se encuentran sobre la ruta crítica,
se les llama actividades críticas.
¿Cómo reducir el tiempo total del proyecto? en este caso son 22 semanas.
Se deben reducir la duración de una o más de las actividades críticas.
Veamos en forma general, para cualquier red:
(1) Identificar todas las rutas de la red.
94
(2) Calcular la duración de cada una de ellas.
(3) Elegir la ruta más larga (critica).
Este procedimiento es muy poco eficiente de analizar una red.
Otro método más eficiente es calcular límites de tiempo para cada actividad
tiempos:
Próximos de iniciación
Lejanos de iniciación
Próximos de terminación
Lejanos de terminación
Y a partir de estos datos calcular la ruta crítica.
Los límites de los tiempos próximos de iniciación y próximos de
terminación se pueden calcular haciendo una revisión hacia adelante de
la red.
Los límites de los tiempos lejanos de iniciación y de terminación se
determinan utilizando una revisión hacia atrás en la red.
6. Revisión hacia delante
Cálculo de los tiempos próximos de iniciación y próximos de terminación.
7. Definición de terminación y notación
a. Tiempo próximo de iniciación
El tiempo próximo de iniciación de una actividad es el tiempo más próximo
posible en que una actividad puede comenzar, el cual se denotara por ESij
donde i y j representan el nodo inicial y final asociados con la actividad.
95
b. Tiempo próximo de terminación
El tiempo próximo de terminación para cada actividad, el cual se denota
por EFij, es el tiempo próximo de iniciación más el tiempo que se requiere
para completar la actividad.
Ejemplo para la actividad A de la Sharp Company.
EF12 = ES12 + D12
En donde D12 = 6, el tiempo esperado para la actividad. Si el tiempo
próximo de la iniciación de la actividad A es 0, es decir, ES12 = 0, entonces
EF12 = 0 + 6 = 6.
En la red se utiliza la siguiente clave:
En la red se tendría la siguiente apariencia
96
El procedimiento normal para analizar una red consiste en comenzar en
el nodo inicial y suponer que se tiene un tiempo inicial de cero.
Se supone que todas las actividades comienzan tan pronto como es
posible, es decir, tan pronto como han terminado todas las actividades
precedentes asociadas.
Como en nuestro caso (caso Sharp) las actividades A y B no tiene
predecesoras, ES12 = 0 y ES15 = 0; por lo tanto, sus correspondientes
tiempos de terminación son EF15 = 0 + 2 = 2 y EF12 = 0 + 6 = 6.
Una vez calculado el tiempo próximo de terminación para la actividad A,
puede calcularse el tiempo próximo de iniciación de la actividad C; la
actividad C no puede comenzar sino hasta que la actividad A ha sido
terminada. Ídem para la actividad D.
El tiempo más próximo de iniciación de la actividad C, ES23, es igual al
tiempo más próximo de terminación de la actividad A, que es EF12 = 6.
El tiempo más próximo de terminación para la actividad C es su tiempo
próximo de iniciación más su tiempo de duración, o EF23 = ES23 + D23 = 6
+ 3 = 9.
Para la actividad D los tiempos próximos de iniciación y de terminación
son:
ES56 = EF15 = 2
EF56 = ES56 + D56 = 2 + 3 =5
Realizamos el análisis completo hacia adelante
97
En los casos en que existen varias actividades precediendo a otra, el
tiempo más próximo de iniciación para esta actividad es igual al mayor de
los tiempos próximos de terminación para todas las actividades
precedentes.
8. Revisión hacia atrás
Calculo de los tiempos lejanos de iniciación y lejanos de terminación.
Este análisis permitirá responder preguntas como
¿Cuánto puede demorarse cada actividad, si es que es posible?
¿Qué tan tarde puede comenzarse una actividad específica sin prolongar
la duración total del proyecto?
9. Definición de términos y notación
a. Tiempo más lejano de iniciación
El tiempo más lejano de iniciación para una actividad, LSij es el tiempo más
lejano o más tarde en el que una actividad puede comenzar sin demorar la
fecha de terminación del proyecto.
98
b. Tiempo más lejano de terminación
El tiempo más lejano de terminación para una actividad, LFij es el tiempo
más lejano de iniciación más el tiempo que dura la actividad Dij
En forma simbólica, estas relaciones son: LFij = LSij + Dij sin embargo es
más apropiado LSij = LFij – Dij.
Para nuestro caso (caso Sharp)
Para comenzar los cálculos, se comienza con el evento final (el nodo 10
en nuestro caso) y se fija el tiempo más lejano de terminación para la
última actividad como el tiempo total de duración calculado en la revisión
hacia adelante, LF9 10 = 22.
Debido a que se requieren dos días para terminar la actividad J, el tiempo
más lejano de iniciación para la actividad J es igual al tiempo más lejano
de terminación menos el tiempo de duración
LS9 10 = LF9 10 – D9 10
LS9 10 = 22 – 2 = 20
Para la actividad I, el tiempo más lejano de terminación es 20, LF89 = 20
y el tiempo más lejano de iniciación es
LS89 = LF89 – D89
LS89 = 20 – 1 = 19
Continuando con el análisis
99
Si un nodo determinado tiene más de una actividad que sale de él,
entonces el tiempo más lejano de terminación para cada actividad que
entra al nodo es igual al menor valor de los tiempos más lejanos de
iniciación para todas las actividades que salen del nodo.
10. Tiempo de holgura (flotante)
Después de que se han determinado los límites de tiempo para toda la red,
puede determinarse el tiempo de holgura para cada actividad.
Se define como tiempo de holgura como la longitud de tiempo en la que
puede demorarse una actividad sin ocasionar que la duración del proyecto
general exceda su tiempo programado de terminación.
La cantidad de tiempo de holgura de una actividad se calcula tomando la
diferencia entre sus tiempos más lejanos de iniciación y más próximos de
iniciación, o entre su tiempo más lejano de terminación y el tiempo más
próximo de terminación.
En forma de ecuación:
Fij = LSij – Esij
O
Fij = LFij – EFij
100
Ejemplo
Para la actividad B
F15 = LF15 – EF15 = 9 – 2 = 7
O
F15 = LS15 – ES15 = 7 – 0 = 7
11. Resumen de los Cálculos Pert/CPM
Identificar todas las tareas o actividades asociadas con el proyecto.
Identificar las relaciones de precedencias inmediatas para todas las
actividades.
Dibujar la red básica para el proyecto, mostrando todas las relaciones de
precedencia.
Estimar el tiempo esperado de duración para cada actividad.
Empleando una revisión hacia adelante de la red, calcular el tiempo
próximo de iniciación y el tiempo próximo de terminación para cada
actividad.
Utilizando el término esperado de terminación del proyecto, calculado en
la revisión hacia adelante en la red, usar el procedimiento de revisión
hacia atrás para calcular el tiempo más lejano de iniciación y el tiempo
más lejano de terminación para cada actividad.
101
Calcular el tiempo de holgura asociado a cada actividad.
Identificar la ruta crítica para la red. Las actividades críticas son las que
tienen un tiempo holgura de cero.
12. Incertidumbre en una red PERT/CPM
Estimación de los tiempos de las actividades
Al aplicar PERT/CPM a proyectos de construcción y mantenimiento, es
posible contar con estimaciones bastante precisas de los tiempos de las
actividades ya que es probable que se disponga de datos históricos y
dado que la tecnología que se utiliza es más o menos estable.
En los proyectos del tipo investigación y desarrollo, en los que la
tecnología cambia con rapidez y los productos no son comunes, es
posible que sea difícil contar con estimaciones precisas de los tiempos de
las actividades.
Con el fin de tener en cuenta la incertidumbre, las personas que
desarrollaron PERT permitieron a los usuarios utilizar tres estimadores para
los tiempos de cada una de las actividades:
El tiempo más probable (tm):
El tiempo que se requiere para terminar la actividad bajo condiciones
normales.
El tiempo pesimista (tp):
El tiempo máximo que se necesitaría para terminar la actividad si se
encontraran demoras considerables en el proyecto.
El tiempo optimista (to):
El tiempo mínimo que se requiere para terminar la actividad si todo ocurre
en forma ideal.
102
Utilizando estas tres estimaciones, puede calcularse un tiempo esperado
para la duración de una actividad de acuerdo con la siguiente formula:
Veamos que ocurre con el tiempo con el caso Sharp en el cual se
proporcionan tres estimaciones de los tiempos que se requieren para
terminar cada una de las actividades del proyecto.
Tabla:
Código de
la actividad
Tiempo
optimista(to)
Tiempo mas
probable(tm)
Tiempo
pesimista(tp)
A 3.0 5.5 11.0
B 1.0 1.5 5.0
C 1.5 3.0 4.5
D 1.2 3.2 4.0
E 2.0 3.5 8.0
F 1.8 2.8 5.0
G 3.0 6.5 7.0
H 2.0 4.2 5.2
I 0.5 0.8 2.3
J 0.8 2.1 2.8
Si utilizamos la actividad F como ejemplo, estos datos indican que se
estima que la actividad “fabricar envases” requerirá entre 1.8 semanas
(estimación optimista) y 5.0 semanas (estimación pesimista), siendo su
estimación más probable 2.8 semanas. El valor que sería probable que
ocurriera si la actividad se repitiera varias veces en el tiempo esperado.
te = to + 4tm + tp
6
103
13. Comentarios
A pesar que en la mayoría de las aplicaciones de PERT/CPM, las
actividades no se repiten un número grande de veces; más bien, por lo
general ocurren solo una vez. te sigue siendo el mejor estimador único del
tiempo que se requiere para una actividad y es el que tradicionalmente se
utiliza.
14. Variabilidad en los Tiempos de las Actividades
Si aplicamos la fórmula para te a las tres estimaciones para cada actividad
de la tabla anterior, los te resultantes son iguales a los valores de “tiempo
esperado de terminación”, que vimos al principio en el caso Sharp.
te = 1.8 + 4(2.8) + 5.0
6 = 3.0
104
Código de
actividad
Tiempo
esperado
para terminar
(semanas)
A 6
B 2
C 3
D 3
E 4
F 3
G 6
H 4
I 1
J 2
Antes de continuar debemos respondernos algunas interrogantes
¿Qué se gana al hacer tres estimaciones?
¿Por qué no simplemente estimar los valores esperados y hacer los
cálculos de PERT/CPM con base en éstos?
La respuesta es:
Se necesita saber qué tan confiables son las estimaciones de los
tiempos esperados.
Lo cual se puede hacer teniendo las tres estimaciones.
Si el tiempo requerido para terminar una actividad es muy grande,
entonces tendremos menos confianza en el tiempo esperado que si el
intervalo fuera menor.
105
Por ejemplo: si las tres estimaciones para la actividad “fabricar el
producto” fueran 2, 3 y 4 en vez de 1.8, 2.8 y 5.0 en ambos casos el
tiempo promedio sería 3.0 días; pero en el primer caso tendríamos más
confianza en que estas cifras modificadas fueran más precisas puesto
que tiene menor variabilidad. Un intervalo amplio de las estimaciones
representa una mayor incertidumbre y, por ello, menor confianza en el
tiempo esperado que se calcula.
A menor confianza, la probabilidad de terminar el proyecto hacia una
fecha dada se reduce.
La ventaja de tener tres estimaciones de tiempos es que puede
calcularse la dispersión de los tiempos de las actividades y puede
utilizarse esta información para evaluar la incertidumbre de que el
proyecto se termine de acuerdo con el programa.
Se utiliza la varianza como medida para describir la dispersión o
variación de las estimaciones de los tiempos de las actividades.
La fórmula de la varianza es:
Si la aplicamos al caso Sharp se tiene:
Código de la
actividad
Varianza
t2
A 1.78
B 0.44
C 0.56
D 0.22
106
E 1.00
F 0.28
G 0.44
H 0.28
I 0.09
J 0.11
A partir de estos datos, se tiene, que la actividad A tiene un mayor grado
de incertidumbre que la J. (1.78 comprada con 0.11).
15. Variabilidad en la fecha de terminación del proyecto
Al calcular la ruta crítica se utilizaron los tiempos esperados de duración
para los tiempos de las actividades; lo que se obtuvo fue una duración
esperada para el proyecto.
Como es probable que cada actividad varíe en duración en vez de ser fija.
El tiempo de terminación del proyecto será variable, y en particular si
existen variaciones considerables en las actividades de la ruta crítica.
Es “probable” que el tiempo de duración del proyecto varíe positivamente
como negativamente.
La influencia en el tiempo de duración del proyecto no solo es de las
actividades de la ruta crítica, sino que se puede generar otra ruta crítica
debido a la variabilidad de las actividades.
Puesto que la varianza de una actividad da una medida de la variación en
la incertidumbre, puede utilizarse para calcular la variación total en el
tiempo esperado del término del proyecto.
107
Al calcular el tiempo esperado de terminación del proyecto, se toman las
varianzas (t2), de las actividades que forman la ruta crítica. Al igual que
con una calcular la varianza del tiempo de terminación del proyecto (t2)
simplemente se suman las varianzas (t2) de las actividades que forman
la ruta crítica.
Caso Sharp: recordemos que la ruta crítica era la que incluía las
actividades A, C, E, G, I y J, con un tiempo esperado de terminación de
22 semanas.
La varianza del proyecto es:
2 = tA2 + tC
2 + tE2 + tG
2 + tI2 + tJ
2
2 = 1.78 + 0.56 + 1.00 + 0.44 + 0.09 + 0.11
2 = 3.98 semanas
Sabemos de la estadística básica que la desviación estándar es igual a la
raíz cuadrada de la varianza ; por tanto, la desviación estándar para la
terminación del proyecto es
= (2)1/2 = (3.98)1/2 2 semanas
En estadística, se sabe que los tiempos de terminación de un proyecto no
están descritos por una distribución beta sino que siguen una distribución
aproximadamente normal o en forma de campana.
(En el desarrollo del PERT se utilizaron una distribución beta para
describir las variaciones en los tiempos de actividades)
108
Si hacemos una gráfica se tiene.
Utilizando la distribución normal podemos hacer planteamientos de
probabilidades con respecto a fecha de término del proyecto; dada una
fecha específica de terminación, puede calcularse la probabilidad de que
el proyecto se termine en esa fecha o antes.
Ejemplo se desea saber cuál es la probabilidad de que el proyecto termine
antes de 6 meses (26 semanas).
Primero
Convertir 26 semanas a un valor de Z. (X = 26, = 22 y = 2)
Segundo
Con el valor Z = 2 y una tabla de distribución normal, se encuentra que la
probabilidad asociada es 0.9772. La probabilidad de que el proyecto se
termine en 26 semanas o menos es 0.9772; por tanto, se puede tener
bastante confianza en que el proyecto pueda terminarse hacia esa fecha.
109
CONCLUSIONES
La Investigación Operativa es el procedimiento científico que está auxiliado por
modelos y técnicas matemáticas, servible para diseñar y operar a los problemas
complejos de la dirección y administración de grandes sistemas que forman una
organización compleja en las cuales las decisiones son muy importantes y
difíciles de elegir, ya que la eficacia de una decisión sobreguardará la
supervivencia y desarrollo de ésta, al contrario, estaría en camino hacia el
fracaso.
Ante la necesidad de administrar y distribuir, de manera eficiente, materiales
escasos a las distintas operaciones en las que las empresas se ven reflejadas,
es necesario aplicar las técnicas de la investigación de operaciones. Las técnicas
desarrolladas han contribuido a empujar la rápida carrera que llevaba la
investigación de operaciones, e incluso muchas de las técnicas hubiesen
alcanzado un grado de desarrollo extraordinario.
Es por todos conocido el rápido desarrollo que han experimentado, durante el
anterior y presente siglo, el tamaño y la complejidad de las organizaciones
humanas. Por ejemplo, el tamaño de las empresas modernas, implica que las
decisiones administrativas pueden tener un efecto sobre grandes cantidades de
capital y gran número de personas. Los errores pueden ser tremendamente
costosos y una sola decisión equivocada puede requerir años para rectificarse.
Debe observarse que la naturaleza de las operaciones es inmaterial, por lo cual
la Investigación de Operaciones se aplica a las industrias de fabricación, a los
transportes, a la construcción, a las telecomunicaciones (teoría de colas,
telegráfico), a los negocios financieros, a los servicios públicos y, por supuesto,
a las Fuerzas Armadas.
110
CUESTIONARIOS
CAPÍTULO I
1. ¿Defina investigación de operaciones?
2. Mencione otra definición de IO
3. La Investigación de Operaciones (IO) o Investigación Operativa es una
rama de...
4. Fases de la investigación operacional
5. ¿Qué es formulación del problema?
6. En un modelo matemático ¿Cuáles son los principales elementos atomar
en cuenta?
7. Responder. Una de las áreas principales de la Investigación de
Operaciones es la...
8. Objetivos de la investigación operacional
9. Aspectos que estudia la IO
10. Orígenes de la IO
CAPÍTULO II
1. ¿Cómo se dividen los Modelos Matemáticos?
2. Programación Lineal es utilizada para analizar modelos donde las
restricciones y la función objetivo son...
3. La función que tenemos que maximizar o minimizar se denomina
4. Un problema de Programación Lineal consiste en
5. Los problemas de Programación Lineal no tienen solución cuando
6. ¿Qué pares de puntos pertenecen al semiplano dado por la ecuación 3x-
5y>2?
(4,2); (-3,4).
(-2,1); (5,2).
(-3,-3); (-1,-2).
(-3,-2); (-4,-1).
111
7. ¿Dónde se encuentra la solución óptima en un problema de Programación
Lineal?
8. ¿Qué es el método simplex?
9. Objetivo del método simplex
10. Características del método simplex
11. ¿Cuándo se utiliza el método simplex de dos fases?
12. Explique las fases 1 y dos del método simplex de dos fases
13. Explique el método gráfico
14. ¿Qué es Solver?
15. ¿El complemento Solver viene activado por defecto?
CAPÍTULO III
1. ¿Explique sobre PERT y CPM?
2. Defina PERT
3. Defina CPM
4. ¿En qué década se desarrolló PERT?
5. ¿En qué se utilizó PERT?
6. Aspectos generales de CPM
7. Menciones la terminología PERT, CPM
8. Ventajas PERT y CPM
9. Mencione limitaciones del CPM
10. Explique qué es estructura de red
11. ¿Qué es un diagrama de red?
12. Explique actividades ficticias
REFERENCIAS
A. Bibliográficas
112
Ing. Víctor Calle Vivanco – Investigación Operativa (Curso A Distancia de
la Universidad Peruana los Andes) – Primera Edición – 2005.
Raffo lecca – Investigación de Operaciones – Primera Edición – Lima-Perú
– 1997
B. Digitales
https://www.fing.edu.uy/inco/cursos/io/archivos/teorico/todo.pdf
https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-
industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/
http://www.investigaciondeoperaciones.net/metodo_simplex_2_fases.html
https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-
industrial/investigaci%C3%B3n-de-operaciones/dualidad-en-
programaci%C3%B3n-lineal/
http://www.programacionlineal.net/sensibilidad.html
xa.yimg.com/kq/groups/21880819/649259048/name/index.doc
http://www.monografias.com/trabajos59/investigacion-
operaciones/investigacion-operaciones2.shtml
http://catedraisdefe.etsit.upm.es/wiki/index.php/La_investigaci%C3%B3n_
de_operaciones
http://www.monografias.com/trabajos24/pert-cpm/pert-cpm.shtml
113