2.

1 Formulación y aplicación de modelos de programación

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

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

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

Para construir un modelo es necesario primero definir las variables en función de las cuales será
establecido. Luego, se procede a determinar matemáticamente cada una de las dos partes que
constituyen un modelo: a) la medida de efectividad que permite conocer el nivel de logro de los
objetivos y generalmente es una función(ecuación) llamada función objetivo; b) las limitantes del
problema llamadas restricciones que son un conjunto de igualdades o desigualdades que
constituyen las barreras y obstáculos para la consecución del objetivo. Un modelo siempre debe
ser menos complejo que el problema real, es una aproximación abstracta de la realidad con
consideraciones y simplificaciones que hacen más manejable el problema y permiten evaluar
eficientemente las alternativas de solución.

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

Por otro lado, existen obstáculos que deben evitarse al usar modelos matemáticos. Un modelo es,
necesariamente, una idealización abstracta del problema, por lo que casi siempre se requieren
aproximaciones y suposiciones de simplificación si se quiere que el modelo sea manejable
(susceptible de ser resuelto). Por lo tanto, debe tenerse cuidado de que el modelo sea siempre
una representación válida del problema. El criterio apropiado para juzgar la validez de un modelo
es el hecho de si predice o no con suficiente exactitud los efectos relativos de los diferentes cursos
de acción, para poder tomar una decisión que tenga sentido. En consecuencia, no es necesario
incluir detalles sin importancia o factores que tienen aproximadamente el mismo efecto sobre
todas las opciones. Ni siquiera es necesario que la magnitud absoluta de la medida de efectividad
sea aproximadamente correcta para las diferentes alternativas, siempre que sus valores relativos
(es decir, las diferencias entre sus valores) sean bastante preciso. Entonces, todo lo que se
requiere es que exista una alta correlación entre la predicción del modelo y lo que ocurre en la
vida real. Para asegurar que este requisito se cumpla, es importante hacer un número
considerable de pruebas del modelo y las modificaciones consecuentes. Aunque esta fase de
pruebas se haya colocado después en el orden del libro, gran parte del trabajo de validación del
modelo se lleva a cabo durante la etapa de construcción para que sirva de guía en la obtención del
modelo matemático.

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

Resolver un modelo consiste en encontrar los valores de las variables dependientes, asociadas a
las componentes controlables del sistema con el propósito de optimizar, si es posible, o cuando
menos mejorar la eficiencia o la efectividad del sistema dentro del marco de referencia que fijan
los objetivos y las restricciones del problema. La selección del método de solución depende de las
características del modelo. Los procedimientos de solución pueden ser clasificados en tres tipos: a)
analíticos, que utilizan procesos de deducción matemática; b) numéricos, que son de carácter
inductivo y funcionan en base a operaciones de prueba y error; c) simulación, que utiliza métodos
que imitan o, emulan al sistema real, en base a un modelo. Muchos de los procedimientos de
solución tienen la característica de ser iterativos, es decir buscan la solución en base a la repetición
de la misma regla analítica hasta llegar a ella, si la hay, o cuando menos a una aproximación.

PRUEBA DEL MODELO

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

desarrollo de un programa de computadora grande. Cuando se completa la primera
versión, es inevitable que contenga muchas fallas. El programa debe probarse de manera
exhaustiva para tratar de encontrar y corregir tantos problemas como sea posible.
Eventualmente, después de una larga serie de programas mejorados, el programador (o
equipo de programación) concluye que el actual da, en general, resultados
razonablemente válidos.
Aunque sin duda quedarán algunas fallas ocultas en el programa (y quizá nunca se
detecten, se habrán eliminado suficientes problemas importantes como para que sea
confiable utilizarlo. De manera similar, es inevitable que la primera versión de un modelo
matemático grande tenga muchas fallas. Sin duda, algunos factores o interpelaciones
relevantes no se incorporaron al modelo y algunos parámetros no se estimaron
correctamente.
Esto no se puede eludir dada la dificultad de la comunicación y la compresión de todos los
aspectos y sutilezas de un problema operacional complejo, así como la dificultad de
recolectar datos confiables. Por lo tanto, antes de usar el modelo debe probarse
exhaustivamente para intentar identificar y corregir todas las fallas que se pueda. Con el
tiempo, después de una larga serie de modelos mejorados, el equipo de IO concluye que
el modelo actual produce resultados razonablemente válidos. Aunque sin duda quedarán
algunos problemas menores ocultos en el modelo (y quizá nunca se detecten), las fallas
importantes se habrán eliminado de manera que ahora es confiable usar el modelo. Este
proceso de prueba y mejoramiento de un modelo para incrementar su validez se conoce
como validación del modelo.
Debido a que el equipo de IO puede pasar meses desarrollando todas las piezas
detalladas del modelo, es sencillo "no ver el bosque por buscar los árboles”. Entonces,
después de completar los detalles ("los árboles") de la versión inicial del modelo, una
buena manera de comenzar las pruebas es observarlo en forma global ("el bosque") para
verificar los errores u omisiones obvias.
El grupo que hace esta revisión debe, de preferencia, incluir por lo menos a una persona
que no haya participado en la formulación. Al examinar de nuevo la formulación del
problema y comprarla con el modelo pueden descubrirse este tipo de errores. También es
útil asegurarse de que todas las expresiones matemáticas sean consistentes en las
dimensiones de las unidades que emplean. Además, puede obtenerse un mejor
conocimiento de la validez del modelo variando los valores de los parámetros de entrada
y/o de las variables de decisión, y comprobando que los resultados del modelo se
comporten de una manera factible. Con frecuencia, esto es especialmente revelador
cuando se asignan a los parámetros o a las variables valores extremos cercanos a su
máximo o a su mínimo.
Un enfoque más sistemático para la prueba del modelo es emplear una prueba
retrospectiva. Cuando es aplicable, esta prueba utiliza datos históricos y reconstruye el
pasado para determinar si el modelo y la solución resultante hubieran tenido un buen
desempeño, de haberse usado. La comparación de la efectividad de este desempeño
hipotético con lo que en realidad ocurrió, indica si el uso del modelo tiende a dar mejoras
significativas sobre la práctica actual. Puede también indicar áreas en las que el modelo
tiene fallas y requiere modificaciones.
Lo que, es más, el emplear las alternativas de solución y estimar sus desempeños
históricos hipotéticos, se pueden reunir evidencias en cuanto a lo bien que el modelo
predícelos efectos relativos de los diferentes cursos de acción. Cuando se determina que
el modelo y la solución no son válidos, es necesario iniciar nuevamente el proceso
revisando cada una de las fases de la metodología de la investigación de operaciones.
ESTABLECIMIENTO DE CONTROLES SOBRE LA SOLUCION
Una solución establecida como válida para un problema, permanece como tal siempre y
cuando las condiciones del problema tales como: las variables no controlables, los
parámetros, las relaciones, etc., no cambien significativamente. Esta situación se vuelve
más factible cuando algunos de los parámetros fueron estimados aproximadamente. Por
lo anterior, es necesario generar información adicional sobre el comportamiento de la
solución debido a cambios en los parámetros del modelo. Usualmente esto se conoce
como análisis de sensibilidad. En pocas palabras, estafase consiste en determinar los
rangos de variación de los parámetros dentro de los cuáles no cambia la solución del
problema.
IMPLANTACION DE LA SOLUCION
El paso final se inicia con el proceso de "vender" los hallazgos que se hicieron a lo largo
del proceso a los ejecutivos o tomadores de decisiones. Una vez superado este
obstáculo, se debe traducir la solución encontrada a instrucciones y operaciones
comprensibles para los individuos que intervienen en la operación y administración del
sistema. La etapa de implantación de una solución se simplifica en gran medida cuando
se ha propiciado la participación de todos los involucrados en el problema en cada fase de
la metodología. Preparación para la aplicación del modelo Esta etapa es crítica, ya que es
aquí, y sólo aquí, donde se cosecharán los beneficios del estudio. Por lo tanto, es
importante que el equipo de IO participe, tanto para asegurar que las soluciones del
modelo se traduzcan con exactitud a un procedimiento operativo, como para corregir
cualquier defecto en la solución que salga a la luz en este momento. El éxito de la puesta
en práctica depende en gran parte del apoyo que proporcionen tanto la alta administración
como la gerencia operativa.
Es más probable que el equipo de IO obtenga este apoyo si ha mantenido a la
administración bien informada y ha fomentado la guía de la gerencia durante el estudio.
La buena comunicación ayuda a asegurar que el estudio logre lo que la administración
quiere y por lo tanto merezca llevarse a la práctica. También proporciona a la
administración el sentimiento de que el estudio es suyo y esto facilita el apoyo parala
implantación. La etapa de implantación incluye varios pasos. Primero, el equipo de
investigación de operaciones de una cuidadosa explicación a la gerencia operativa sobre
el nuevo sistema que se va a adoptar y su relación con la realidad operativa. En seguida,
estos dos grupos comparten la responsabilidad de desarrollar los procedimientos
requeridos para poner este sistema en operación.
La gerencia operativa se encarga después de dar una capacitación detallada al personal
que participa, y se inicia entonces el nuevo curso de acción. Si tiene éxito, el nuevo
sistema se podrá emplear durante algunos años. Con esto en mente, el equipo de IO
supervisa la experiencia inicial con la acción tomada para identificar cualquier
modificación que tenga que hacerse en el futuro.
A la culminación del estudio, es apropiado que el equipo de investigación de operaciones
documento su metodología con suficiente claridad y detalle para que el trabajo sea
reproducible. Poder obtener una réplica debe ser parte del código de ética profesional del
investigador de operaciones. Esta condición es crucial especialmente cuando se estudian
políticas gubernamentales en controversia

2.2 Método gráfico

El método grafico se utiliza para la solución de problemas de PL, representando geométricamente
a las restricciones, condiciones técnicas y el objetivo.

El modelo se puede resolver en forma geométrica si solo se tiene 2 variables. Para modelos con 3
o más variables el método grafico es impráctico o imposible. Cuando los ejes son relacionados con
las variables del problema, el método es llamado método gráfico en actividad. Cuando se
relacionan las restricciones tecnológicas se denomina método grafico en recursos.

*PL.- es una técnica mediante la cual se toman decisiones reduciendo el problema bajo estudio a
un modelo matemático general.
Maximizar y Minimizar.

Podemos maximizar y minimizar por el método grafico nuestros problemas y nos lleva a un
resultado exacto al igual que el simplex solo que este es aún más fácil, pues como al principio
mandas en la ecuación a X cero y después Y así te da el primer punto a graficar y así con las demás
ecuaciones, el punto donde se intersectan dos o más líneas de las ecuaciones es el punto solución,
este se sustituye debidamente cada número en Su variable en la función objetivo para dar la
comprobación. Así el espacio debajo del punto de intersección es para maximización y se presenta
el resultado por ejemplo Z=10, para la minimización es lo mismo solo se toma el punto solución
como lo más y el resultado de igual solo que se representaría –Z=10 y la zona factible cabe en la
parte mayor de la gráfica.

Pasos necesarios para realizar el método.

1. Graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las
restricciones en forma simultánea.

2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles.

3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer

término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta.

4. Trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se
considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada.

5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las
restricciones y por consiguiente, representa un punto factible.

6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución

óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo.

7. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de
valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el
valor de la función objetivo.

2.3 Método simplex

Objetivo del Método Simplex: El alumno analizará los fundamentos de la programación lineal, así
como el procedimiento gráfico y el respectivo procedimiento del Método Simplex.

El Método Simplex es un procedimiento iterativo el cual permite mejorar la solución a cada paso.
Este proceso concluye cuando no es posible seguir mejorando la solución.

Este método se puede considerar como un método algebraico para resolver problemas de
programación lineal el cual involucra dos o más variables.

El Método Simplex fue creado en el año de 1947. Su primera aplicación fue después del verano de
1947 cuando se resolvió un problema de programación de 9 restricciones y 27. Usando calculadora
de escritorio se requirieron 120 días, en la actualidad y un programa para resolver el Método
Simplex será cosa de minutos.

El Método Simplex como herramienta de programación lineal constituye una de las mejores
formas para obtener la solución más óptima en programación lineal.
En este método utilizaremos las desigualdades <, >, ≥ y ≤.

Conceptos utilizados en el Método Simplex

1. Variable de decisión. Con estas variables se hace referencia al conjunto de variables cuya
magnitud se desea determinar.

2. Restricciones. Están constituidas por el conjunto de desigualdades que limitan los valores que
puedan tomar las variables de desigualdad.

3. Función objetivo. Es una función matemática que relaciona las variables de decisión.

4. Linealidad. Se refiere a que la relación entre las variables de la función objetiva y restricciones
deben ser lineales.

5. Desigualdades. Las desigualdades utilizadas para representar las restricciones deben ser
cerradas.

6. Condición de no negatividad. En la programación lineal las variables de decisión solo pueden

tomar valores mayores o iguales que cero.

2.3.1 Método algebraico

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso
concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la
función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro
vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o
de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de
aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en la siguiente propiedad: si la función objetivo, no toma su valor
máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual aumenta. El
método del simplex fue creado en 1947 por el matemático George Dantzig. El método del simplex
se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres
o más variables. El álgebra matricial y el proceso de eliminación de Gauss-Jordán para resolver un
sistema de ecuaciones lineales constituyen la base del método simplex. Con miras a conocer la
metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:
Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la
solución óptima. La solución óptima viene dada por el valor de Z en la columna de los valores
solución, en nuestro caso: 33.

En la misma columna se puede observar el vértice donde se alcanza, observando las filas
correspondientes a las variables de decisión que han entrado en la base: D (3,12)

* Si en el problema de maximizar apareciesen como restricciones inecuaciones de la forma: ax + b

y c; multiplicándolas por - 1 se transforman en inecuaciones de la forma - ax - by - c y estamos en
el caso anterior * Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo
proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable
cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las
iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos.

2.3.2 La tabla simplex

La resolución de programas lineales mediante el método Simplex implica la realización de gran
cantidad de cálculos, sobre todo cuando el número de variables y/o restricciones es relativamente
elevado. Sin embargo, estos cálculos no son complejos y pueden realizarse en modo sistemático
utilizando una forma tabular. Así surgen las conocidas como tablas del Simplex, que no son más
que una forma de organizar los cálculos. Sobre las tablas del Simplex comentar que su interés es
totalmente pedagógico, ya que en los casos reales la magnitud de los problemas que suele
aparecer hace que nadie las utilice de forma directa para resolverlos. En tales casos, ha de
recurrirse al uso del computador.

Para aplicar el método Simplex en forma de tabla a un problema de la forma:

Observar la forma en que se construye esta tabla:

• En la primera fila de la tabla se colocan los coeficientes de las variables en la función objetivo.

• En las tres primeras columnas aparecen los coeficientes de las variables básicas en la función
objetivo, las variables básicas iniciales y el vector de términos independientes de las restricciones,
respectivamente.

• La parte central de la tabla está formada por la matriz de coeficientes A.

• Los elementos de la penúltima fila son los productos escalares del vector de la primera columna
con los vectores de la tabla que quedan encima de cada uno de esos elementos.

Finalmente, en la última fila aparece la diferencia de las filas primera y penúltima.

Cada tabla del Simplex está asociada a una solución básica factible. De forma que, una vez
construida la tabla inicial, deben establecerse las reglas que permitan obtener las tablas asociadas
a las siguientes soluciones básicas, así como saber la solución básica que lleva asociada cada tabla.
Además, es necesario saber cuándo una tabla corresponde a la solución óptima, esto último se
consigue analizando los signos de la última fila de la tabla:
Si todos los elementos de la última fila de la tabla son mayores o iguales que cero, el óptimo ha
sido alcanzado. Cuando alguno de los elementos de la última fila es negativo, el valor óptimo
puede mejorarse y por tanto debe construirse una nueva tabla de la manera siguiente:

Se selecciona de la última fila el elemento negativo de mayor valor absoluto. La variable

correspondiente al índice del zi seleccionado es la que pasará a ser básica.

• Para saber a qué variable básica sustituye, se dividen los valores de la tercera columna entre los
valores positivos de la columna de A seleccionada en el paso anterior (la que corresponde al
elemento negativo de mayor valor absoluto). En caso de no existir valores positivos, puede
asegurarse que el problema no tiene óptimo finito.

• De todos los cocientes calculados se selecciona el mínimo, el elemento de la matriz A que ha

servido para construir ese valor mínimo es el que actuará como pívot y la variable de la segunda
columna de la tabla en la posición de la fila del pívot es la que deja de ser básica.

• Mediante transformaciones elementales de filas sobre el bloque central de la tabla (el bloque de
fondo amarillo en la tabla) se llega a transformar en 1 el pívot y anular los restantes elementos de
la correspondiente columna. Las únicas transformaciones que son permitidas son:

Multiplicar por constantes la fila que contiene el pívot.

Sumar o restar a una fila un múltiplo de la fila que contiene el pívot.

• Intercambiar las variables básicas en la segunda columna al mismo tiempo que se modifica el
correspondiente elemento de la primera columna.

• Calcular los nuevos valores de las dos últimas filas de la tabla de acuerdo a las instrucciones ya
indicadas. Se repiten todos estos procesos y se van transformando las tablas hasta que el test de
parada sea positivo (todos los elementos de la última fila mayores o iguales que cero) en cuyo caso
se tiene:

•El óptimo se alcanza en el punto cuyas coordenadas son nulas excepto las correspondientes a las
variables básicas, cuyos valores aparecen en la tercera columna de la tabla óptima.

• El valor de la función en el óptimo es el que aparece en el último elemento deesa misma

columna Todas las tablas que se van obteniendo tienen dos características en común: los
elementos de la tercera columna son todos ellos mayores o iguales que cero, salvo el último (el
que indica el valor de la función objetivo) que pudiera ser negativo. Por otro lado, las columnas de
A asociadas a las variables básicas siempre forman una matriz identidad.

Analizando más en profundizar cada una de las etapas expuestas, se puede comprobar la
correspondencia con el método Simplex enunciado de una forma más teórica anteriormente. Por
supuesto, la mejor manera de comprender la resolución mediante tablas es con ejemplos
particulares; a continuación, se exponen dos de estos ejemplos.
2.4 Método dual
Todo problema de programación lineal tiene asociado con él otro problema de programación
lineal llamado DUAL. El problema inicial es llamado PRIMO y el problema asociado (sombra) es
llamado el problema PRIMO. Los dos juntos son llamados problemas duales ya que ambos están
formados por el mismo conjunto de datos. La solución básica factible óptima de estos problemas
es tal que una puede fácilmente ser usada para la solución de la otra.

La dimensión del problema de programación lineal influencia la elección del cálculo del primo o
del dual. Si el primo tiene más ecuaciones que variables, es frecuentemente más fácil obtener la
solución del dual ya que menor número de iteraciones son requeridas. Además, si el primo tiene
solución, el dual tendrá solución. Una vez que el problema dual es formulado, el procedimiento de
solución es exactamente el mismo que para cualquier problema de programación lineal.

Mecánicamente el dual es formulado partiendo del problema primo en la siguiente forma: Si el

primo es un problema de Maximización, el dual es un problema de Minimización y viceversa.

1. Los coeficientes de la función objetivo del primo se convierten en las restricciones constantes de
las ecuaciones del dual.

2. Las restricciones de las ecuaciones del primo se convierten en los coeficientes de la función
objetivo del dual.

3. Los coeficientes de las variables del dual en las ecuaciones restrictivas son obtenidas sacando la
transpuesta de la matriz de coeficientes del primo (los arreglos de los coeficientes en las columnas
del primo se convierten en los coeficientes de las filas en el dual y viceversa).4. Los signos de la
desigualdad son invertidos.5. Las Xn variables del primo son remplazadas por Wm variables en el
dual.
2.5 Método dual-simplex
La solución de un problema dual permite obtener interesantes resultados, relativo al análisis de
sensibilidad de los términos independientes. Más concretamente, para los rangos de los términos
independientes para los que se mantiene la base óptima, la solución dual nos permite conocer el
precio sombra de la restricción, que será la variación de la función objetivo por unidad
incrementada del término independiente de la restricción.
2.6 Análisis de resultados
Los resultados se analizaron en términos de la media de los errores agrupados por tipo de
instancias y en forma global, para cada valor utilizado de y. El error se calcula como:
https://es.scribd.com/doc/143333682/Investigacion-de-Operaciones

http://www.itsmante.edu.mx/wp-content/uploads/2017/11/ANTOLOGIA-INVESTIGACI%C3%93N-
DE-OPERACIONES-I.pdf

https://www.academia.edu/15806834/UNIDAD_II_PROGRAMACION_LINEAL