Introducción a la Investigación de Operaciones
Introducción a la Investigación de Operaciones
En este curso ofrecí un gran esfuerzo ya que muchos de estos temas lo vi en la licenciatura de una forma
muy sencilla, gracias al Ing. Oscar López pude aprende todos estos métodos.
Muchos de estos temas se me dificultaban a un principio pero una vez logrando poder entender el tema
todo se me fue de una manera más fácil. Por ello es de suma importancia practicar todos los temas y no
dar por entendido cuando aún no se tiene firme conocimiento de ello.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 1 | 228
TEMARIO
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 2 | 228
CAPITULO 1 INTRODUCCION A LA INVESTIGACION DE OPERACIONES
Introducción.
Como su nombre lo dice, la investigación de operaciones significa “hacer investigación sobre las
operaciones”. Entonces, la investigación de operaciones se aplica a problemas que se refieren a la
conducción y coordinación de operaciones (o actividades) dentro de una organización.
El siguiente paso es la construcción de un modelo científico (por lo general matemático) que intenta
abstraer la esencia del problema real. En este punto se propone la hipótesis de que el modelo es una
representación lo suficientemente precisa de las características esenciales de la situación como para que
las conclusiones (soluciones) obtenidas sean válidas también para el problema real.
Después, se llevan a cabo los experimentos adecuados para probar esta hipótesis, modificarla si es
necesario y eventualmente verificarla. (Con frecuencia este paso se conoce como la validación del
modelo.) Entonces, en cierto modo, la investigación de operaciones incluye la investigación científica
creativa de las propiedades fundamentales de las operaciones.
Sin embargo, existe más que esto. En particular, la IO se ocupa también de la administración práctica de
la organización. Así, para tener éxito, deberá también proporcionar conclusiones claras que pueda usar
el tomador de decisiones cuando las necesite.
Una característica más de la IO es su amplio punto de vista. Como quedó implícito en la sección anterior,
la IO adopta un punto de vista organizacional, de esta manera, intenta resolver los conflictos de intereses
entre los componentes de la organización de forma que el resultado sea el mejor para la organización
completa.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 3 | 228
Esto no significa que el estudio de cada problema deba considerar en forma explícita todos los aspectos
de la organización sino que los objetivos que se buscan deben ser consistentes con los de toda ella.
Una característica adicional es que la IO intenta encontrar una mejor solución (llamada solución óptima)
para el problema bajo consideración. (Decimos una mejor solución y no la mejor solución porque pueden
existir muchas soluciones que empaten como la mejor.) En lugar de contentarse con mejorar el estado
de las cosas, la meta es identificar el mejor curso de acción posible. Aun cuando debe interpretarse con
todo cuidado en términos de las necesidades reales de la administración, esta “búsqueda de la
optimizar” es un aspecto importante dentro de la investigación de operaciones.
Todas estas características llevan de manera casi natural a otra. Es evidente que no puede esperarse que
un solo individuo sea un experto en todos los múltiples aspectos del trabajo de investigación de
operaciones o de los problemas o de los problemas que se estudian; se requiere un grupo de individuos
con diversos antecedentes y habilidades.
Este debe incluir individuos con antecedentes firmes en matemáticas, estadística y teoría de
probabilidades, al igual que en economía, administración de empresas, ciencias de la computación,
ingeniería, ciencias físicas, ciencias del comportamiento y, por supuesto, en las técnicas especiales de IO.
El equipo también necesita tener la experiencia y las habilidades necesarias para permitir la
consideración adecuada de todas las ramificaciones del problema a través de la organización.
Para llegar a hacer un uso apropiado de la IO, es necesario primero comprender la metodología para
resolver los problemas, así como los fundamentos de las técnicas de solución para de esta forma saber
cuándo utilizarlas o no en las diferentes circunstancias.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 4 | 228
¿Qué es la Investigación de Operaciones?
Como toda disciplina en desarrollo, la investigación de operaciones ha ido evolucionando no sólo en sus
técnicas y aplicaciones sino en la forma como la conceptualizan los diferentes autores, en la actualidad
no existe solamente una definición sino muchas, algunas demasiado generales, otras demasiado
engañosas, aquí seleccionamos dos de lasmás aceptadas y representativas.
“La investigación de Operaciones es la aplicación, por grupos interdisciplinarios, del método científico a
problemas relacionados con el control de las organizaciones o sistemas (hombre – máquina), a fin de que
se produzcan soluciones que mejor sirvan a los objetivos de la organización”.
1. Una organización es un sistema formado por componentes que se interaccionan, unas de estas
interacciones pueden ser controladas y otras no.
2. En un sistema la información es parte fundamental, ya que entre las componentes fluye
información que ocasiona la interacción entre ellas. También dentro de la estructura de los
sistemas se encuentran recursos que generan interacciones. Los objetivos de la organización se
refieren a la eficacia y a la eficiencia con que las componentes pueden controlarse, el control es
un mecanismo de autocorrección del sistema que permite evaluar los resultados en términos de
los objetivos establecidos.
3. La complejidad de los problemas que se presentan en las organizaciones ya no encajan en una
sola disciplina del conocimiento, se han convertido en multidisciplinario por lo cual para su
análisis y solución se requieren grupos compuestos por especialistas de diferentes áreas del
conocimiento que logran comunicarse con un lenguaje común.
4. La investigación de operaciones es la aplicación de la metodología científica a través de modelos
matemáticos, primero para representar al problema y luego para resolverlo.
“La Investigación de Operaciones es el ataque de la ciencia moderna a los complejos problemas que
surgen en la dirección y en la administración de grandes sistemas de hombres, máquinas, materiales y
dinero, en la industria, en los negocios, en el gobierno y en la defensa.
Su actitud diferencial consiste en desarrollar un modelo científico del sistema tal, que incorpore
valoraciones de factores como el azar y el riesgo y mediante el cual se predigan y comparen los
resultados de decisiones, estrategias o controles alternativos.
Su propósito es el de ayudar a la gerencia a determinar científicamente sus políticas y acciones”.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 5 | 228
En relación a ésta definición deben destacarse los siguientes aspectos:
1. Generalmente se asocian los conceptos de dirección y administración a las empresas de tipo
lucrativo, sin embargo, una empresa es un concepto más amplio, es algo que utiliza hombres,
2. máquinas, materiales y dinero con un propósito específico; desde este punto de vista, se
considera como empresa desde una universidad hasta una armadora de automóviles.
3. Para tratar de explicar el comportamiento de un sistema complejo, el científico debe
representarlo en términos de los conceptos que maneja, lo hace expresando todos los rasgos
principales del sistema por medio de relaciones matemáticas. A esta representación formal se le
llama modelo.
4. La esencia de un modelo es que debe ser predictivo, lo cual no significa predecir el futuro, pero si
ser capaz de indicar muchas cosas acerca de la forma en que se puede esperar que un sistema
opere en una variedad de circunstancias, lo que permite valorar su vulnerabilidad. Si se conocen
las debilidades del sistema se pueden tomar cursos de acción agrupados en categorías:
A) Efectuar cambios que lleven a la empresa o parte de ella a una nueva ruta;
B) Realizar un plan de toma de decisiones;
C) Instalar estrategias que generen decisiones.
Cuando se aplica alguno de estos remedios, la investigación de operaciones nos ayuda a
determinar la acción menos vulnerable ante un futuro incierto.
5. El objetivo global de la investigación de operaciones es el de apoyar al tomador de decisiones, en
cuanto a cumplir con su función basado en estudios científicamente fundamentados.
La parte innovadora de la IO es sin duda alguna su enfoque modelístico, producto de sus creadores
aunado a la presión de supervivencia de la guerra o la sinergia generada al combinarse con diferentes
disciplinas, una descripción del enfoque es el siguiente.
1. Se define el sistema real donde se presenta el problema. Dentro del sistema interactúan
normalmente un gran número de variables.
2. Se seleccionan las variables que norman la conducta o el estado actual del sistema, llamadas
variables relevantes, con las cuales se define un sistema asumido del sistema real.
3. Se construye un modelo cuantitativo del sistema asumido, identificando y simplificando las
relaciones entre las variables relevantes mediante la utilización de funciones matemáticas.
4. Se obtiene la solución al modelo cuantitativo mediante la aplicación de una o más de las técnicas
desarrolladas por la IO.
5. Se adapta e imprime la máxima realidad posible a la solución teórica del problema real obtenida
en el punto 4, mediante la consideración de factores cualitativos o no cuantificables, los cuales
no pudieron incluirse en él.
6. Se implanta la solución en el sistema real. La investigación de operaciones obtiene la solución del
problema real indirectamente, y no como normalmente se intentaría pasando del problema real
a la solución real.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 6 | 228
Metodología de la Investigación de Operaciones.
La mayor parte de los problemas prácticos con los que se enfrenta el equipo IO están descritos
inicialmente de una manera vaga. Por consiguiente, la primera actividad que se debe realizar es el
estudio del sistema relevante y el desarrollo de un resumen bien definido del problema que se va a
analizar.
Esto incluye determinar los objetivos apropiados, las restricciones sobre lo que se puede hacer, las
interrelaciones del área bajo estudio con otras áreas de la organización, los diferentes cursos de acción
posibles, los límites de tiempo para tomar una decisión, etc.
Este proceso de definir el problema es crucial ya que afectará en forma significativa la relevancia de las
conclusiones del estudio.
Un estudio de IO busca soluciones óptimas globales y no soluciones subóptimas aunque sean lo mejor
para uno de los componentes. Entonces, idealmente, los objetivos que se formulan deben coincidir con
los de toda la organización. Sin embargo, esto no siempre es conveniente.
Muchos problemas interesan nada más a una parte de la organización, de manera que el análisis sería
innecesariamente besado si lo objetivos fueran muy generales y si se prestara atención especial a todos
los efectos secundarios sobre el resto de la organización.
En lugar de ello, los objetivos usados en un estudio deben ser tan específicos como sea posible, siempre
y cuando contemplen las metas principales del tomador de decisiones y mantengan un nivel razonable
de consistencia con los objetivos de los altos niveles.
Las condiciones fundamentales para que exista un problema es que se establezca una diferencia entre lo
que es (situación actual) y lo que debe ser (situación deseada u objetivo) y además exista cuando menos
una forma de eliminar o disminuir esa diferencia.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 7 | 228
Para formular un problema se requiere;
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.
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 llamada restricciones que son un conjunto de igualdades o
desigualdades que constituyen las barreras y obstáculos para la consecución del objetivo.
Un modelo 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.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 8 | 228
o Una ventaja obvia es que el modelo matemático describe un problema en forma mucho más
concisa.
o Esto tiende a hacer que toda la estructura del problema sea más comprensible y ayude a relevar
las relaciones importantes entre causa y efecto.
o De esta manera, indica con más claridad que datos adicionales son importantes para el análisis.
o También facilita simultáneamente el manejo del problema en su totalidad y el estudio de todas
sus interpelaciones.
o 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. S
o in duda, existe una amplia disponibilidad de paquetes de software para muchos tipos de
modelos matemáticos, para micros y minicomputadoras.
Por otro lado, existen obstáculos que deben evitarse al usar modelos matemáticos.
o 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).
o Por lo tanto, debe tenerse cuidado de que el modelo sea siempre una representación válida del
problema.
o 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.
o En consecuencia, no es necesario incluir detalles sin importancia o factores que tienen
aproximadamente el mismo efecto sobre todas las opciones.
o 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 precisos.
o Entonces, todo lo que se requiere es que exista una alta correlación entre la predicción del
modelo y lo que ocurra en la vida real.
o Para asegurar que este requisito se cumpla, es importante hacer un número considerable de
pruebas del modelo y las modificaciones consecuentes.
Resolver un modelo consistente 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.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 9 | 228
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.
o El programa debe probarse de manera exhaustiva para tratar de encontrar y corregir tanto
problemas como sea posible.
o 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.
o De manera similar, es inevitable que la primera versión de un modelo matemático grande tenga
muchas fallas.
o Por lo tanto, antes de usar el modelo debe probarse exhaustivamente para intentar identificar y
corregir todas las fallas que se pueda.
o 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.
o 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
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 10 | 228
modelo. Este proceso de prueba y mejoramiento de un modelo para incrementar su validez se
conoce como validación del modelo.
o Debido a que el equipo de IO puede pasar meses desarrollando todas las piezas detalladas el
modelo, es sencillo “no ver el bosque para buscar los árboles”.
o Entonces, después de completar los detalles (“árboles2) 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.
o 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.
o También es útil asegurarse de que todas las expresiones matemáticas sean consistentes en las
dimensiones de las unidades que se emplean.
o 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.
o Con frecuencia, esto es especialmente revelador cuando se asignan los parámetros o a las
variables valores extremos cercanos a su máximo o mínimo.
o Un enfoque más sistemático para la prueba del modelo es emplear una prueba retrospectiva.
o 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.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 11 | 228
Establecimiento de controles sobre la solución.
Una solución establecida como válida para un problema, permanece como tal siempre y cuando las
condiciones del problema tales como:
Esta situación se vuelve más factible cuando algunos modelos de los parámetros fueron estimados
aproximadamente.
En pocas palabras, esta fase consiste en determinar los rangos de variación de los parámetros del
modelo. Usualmente esto se conoce como análisis de sensibilidad.
En pocas palabras, esta fase consiste en determinar los rangos de variación de los parámetros dentro de
los cuales con cambia la solución del problema.
Implantación de la solución.
El paso final se iniciará con el proceso de “vender” los hallazgos que se hicieron a lo largo del proceso a
los ejecutivos o tomadores de las decisiones.
Una vez superado éste obstáculo, se debe traducir la solución encontrada a instrucciones y operaciones
comprensibles para los individuos que intervienen en la operación y administración del sistema.
Preparación para la aplicación del modelo. Esta etapa es crítica, ya que es 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.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 12 | 228
El éxito de la puesta en práctica depende en gran parte del apoyo que proporcionen tanto la alta
administración como la gerencia operativa.
Es más probable que el equipo de IO obtenga este apoyo si ha mantenido a la administración bien
informada y ha fomentado la guía de la gerencia durante el estudio.
La buena comunicación ayuda a asegurar que el estudio logre lo que la administración quiere y por lo
tanto merezca llevarse a la práctica.
También proporciona a la administración el sentimiento de que el estudio es suyo y esto facilita el apoyo
para la implantación.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 13 | 228
4. Casi nunca se realizan análisis costo-beneficio de la implantación de soluciones definidas por
medio de la IO, en ocasiones los beneficios potenciales se ven superados por los costos
ocasionados por el desarrollo e implantación de un modelo.
1) Planeación de la Producción.
2) Asignación de personal
3) Transporte
4) Inventarios
5) Dietas
6) Mercado
7) Estrategias de Inversión.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 14 | 228
(1.1) INTRODUCCION A LA INVESITIGACION DE OPERACIONES (POWER POINT)
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 15 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 16 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 17 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 18 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 19 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 20 | 228
CAPITULO 2 PROGRAMACION LINEAL, MODELADO Y METODO SIMPLEX
Introducción.
Muchas personas clasifican el desarrollo de la programación linean entre los avances científicos más
importantes de mediados del siglo XX, su impacto desde 1950 ha sido extraordinario.
En la actualidad es una herramienta de uso normal que ha ahorrado miles o millones de pesos a muchas
compañías o negocios, incluyendo empresas medianas en los distintos países industrializados del mundo,
su aplicación a otros sectores de la sociedad se está ampliando con rapidez.
Una proporción muy grande de los cálculos científicos en computadoras está dedicada al uso de la
programación lineal.
¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar?
Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignar recursos
limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima).
Con más precisión, este problema incluye elegir el nivel de ciertas actividades que compiten por escasos
recursos necesarios para realizarlas.
Después, los niveles de actividad elegidos dictan la cantidad de cada recurso que consumirá cada una de
ellas.
La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va :
No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las
actividades eligiendo niveles de las mismas.
La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo lineal
significa que todas las funciones matemáticas del modelo deben ser funciones lineales.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 21 | 228
En este caso, la palabra programación no se refiere a programación en computadoras; en esencia es un
sinónimo de planeación.
Así, la programación lineal trata la planeación de actividades para obtener un resultado óptimo, esto es,
el resultado que mejor alcance la meta especificada (según el modelo matemático) entre todas las
alternativas de solución.
Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la programación lineal
tiene muchas otras posibilidades, de hecho, cualquier problema cuyo modelo matemático se ajuste al
formato general del modelo de programación lineal es un problema de programación lineal.
Los términos clave son recursos y actividades, en donde m denota el número de distintos tipos de
recursos que se pueden usar y n denota el número de actividades bajo consideración.
o dinero
o tipos especiales de maquinaria,
o equipos,
o vehículos y
o personal.
En cualquier aplicación de programación lineal, puede ser que todas las actividades sean de un tipo
general (como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual a las
alternativas específicas de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a ciertas
actividades. La cantidad disponible de cada recurso está limitada, de forma que deben asignarse con
todo cuidado.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 22 | 228
La determinación de esta asignación incluye elegir los niveles de las actividades que lograrán el
mejor valor posible de la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de un modelo
de programación lineal.
Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de
asignación de recursos de actividades.
El modelo establece el problema en términos de tomar decisiones sobre los niveles de las actividades,
por lo que x1, x2, ..., xn se llaman variables de decisión.
Los valores de cj, bi y aij (para i = 1,2,.., m y j = 1, 2, ..., n) son las constantes de entrada al modelo.
Ahora se puede formular al modelo matemático para este problema general de asignación de recursos a
actividades.
En Datos necesarios para un modelo de programación lineal que maneja la asignación de recursos a
actividades particulares, este modelo consiste en elegir valores de x1, x2, ..., xn para:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 23 | 228
Proporcionalidad.
o En consecuencia, esta suposición elimina cualquier exponente diferenta a 1 para las variables en
cualquier término de las funciones ( ya sea la función objetivo o la función en el lado izquierdo
de las restricciones funcionales) en un modelo de programación lineal.
Aditividad.
o Esta suposición garantiza que la contribución total tanto a la función objetivo como a las
restricciones, es igual a la suma de las contribuciones individuales.
o Cada función en un modelo de programación lineal (ya sea la función objetivo o el lado izquierdo
de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades
respectivas.
Divisibilidad.
o Las variables de decisión en un modelo de programación lineal pueden tomar cualquier valor,
incluyendo valores no enteros, que satisfagan las restricciones funcionales y de no negatividad.
o Como cada variable de decisión representa el nivel de alguna actividad, se supondrá que las
actividades se pueden realizar a niveles fraccionales.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 24 | 228
Modelo Determinístico.
o El modelo de PL involucra únicamente tres tipos de parámetros: Cj, aij y bi; de ahí se sencillez y
su gran aplicación.
o Cuando el valor de los parámetros tiene un cierto riesgo o incertidumbre, puede utilizarse la
programación paramédica, la programación estocástica, o realizarse un análisis de sensibilidad.
Modelo Estático.
o En algunos modelos matemáticos se han empleado con éxito las ecuaciones diferenciales, para
inducir la variable tiempo en ellos.
o En este sentido, puede decirse que la PL utiliza un modelo estático, ya que la variable tiempo no
se involucra formalmente.
o Debido a la forma que se plantea el modelo de PL, o encuentra la solución óptima o declara que
ésta no existe.
o Cuando no es posible obtener una solución óptima y se debe tomar alguna, se recurre a otra
técnica más avanzada que la PL, la cuál se denomina programación lineal por metas.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 25 | 228
7) No venda un modelo como la perfección máxima.
8) Uno de los primeros beneficios de la modelación reside en el desarrollo del modelo.
9) Un modelo es tan bueno o tan malo como la información con la que trabaja.
10) Los modelos no pueden reemplazar al tomador de decisiones.
Como su nombre lo indica, la formulación directa estriba en pasar directamente del sistema asumido al
modelo de PL. Para tal efecto, se propone el siguiente orden:
o definir el objetivo,
o definir las variables de decisión,
o enseguida las restricciones estructurales y
o finalmente establecer las condiciones técnicas.
Definir el Objetivo:
o Son las incógnitas del problema, básicamente consisten en los niveles de todas las Actividades
que pueden llevarse a cabo en el problema a formular, estas pueden ser de tantos tipos
diferentes como sea necesario, e incluir tantos subíndices como sea requerido.
o Son los diferentes requisitos que debe cumplir cualquier solución para que pueda llevarse a cabo.
o En cierta manera son las limitantes en los valores de los niveles de las diferentes actividades
(variables).
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 26 | 228
Algunos de los tipos de problemas que se pueden formular son:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 27 | 228
(2.1) PROBLEMA DE MAXIMIZACION
RMC es una pequeña empresa que produce diversos productos químicos. En un procesos de producción
en particular se utilizan tres materias primas para elaborar dos productos: un aditivo para combustible y
una base disolvente. El aditivo para combustible se vende a empresas petroleras y se utiliza en la
producción de gasolina y de otros combustibles relacionados. La base disolvente se vende a varias
empresas químicas y se utiliza tanto para productos de limpieza para el hogar como industriales. Para
formar el aditivo para combustible y la base disolvente se mezclan las tres materias primas según
aparece en la tabla 7.1.
Esta tabla muestra que una tonelada de aditivo para combustible es una mezcla de 2/5 de tonelada de la
materia prima 1 y 3/5 de tonelada de la materia prima 3.Una tonelada de base disolvente es una mezcla
de ½ tonelada de la materia prima 1 ,1/5 de tonelada de la materia prima 2 y 3/10 de tonelada de la
materia prima 3.
La producción de RMC está limitada por la disponibilidad de las tres materias primas. Para el periodo de
producción actual, RMC tiene disponibles las cantidades siguientes de cada una de las materias primas.
Debido al deterioro y la naturaleza del proceso de producción, cualquier materia prima que no se utilice
para producción actual resulta inútil y debe descartarse.
El departamento de control de calidad ha analizado las cifras de producción, asignando todos los costos
correspondientes y para ambos productos llego a precios que resultaran en una contribución a la
utilidad de $40 dólares por cada tonelada de aditivo para combustible producido y de $ 30 dólares por
cada tonelada de base disolvente producida. La administración de RMC después de un análisis de la
demanda potencial, ha concluido que los precios establecidos aseguraran la venta de todo el aditivo para
combustible y de toda la base disolvente que se produzca.
El problema de RMC es determinar cuántas toneladas de cada producto deberá producir para maximizar
la contribución total a la utilidad. Si usted estuviera a cargo de la programación de la producción de RMC
¿Qué decisión tomaría?, es decir ¿Cuántas toneladas de aditivo para combustible y cuantas toneladas de
base disolvente produciría usted para el periodo actual de producción?
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 28 | 228
Tabla 7.1
Necesidades de materia prima por tonelada para el problema RMC
Contribución a la
Producto Materia Prima 1 Materia Prima 2 Materia Prima 3 utilidad por cada
Ton de producto
Aditivo para
2/5 0 3/5 $US 40
combustible
Base disolvente 1/2 1/5 3/10 $US 30
Cantidades
disponibles para la 20 Ton 5 Ton 21 Ton
producción
Método grafico
1
Para MP1 Sí X1=0 X ₂ ≤20 X2=40 (0,40)
2
2
Sí X1=0 X ₁ ≤20 X1=50 (50,0)
5
1
Para MP2 Sí X1=0 X ₂ ≤5 X2=25 (0,25)
5
3 1 3 2
Para MP3 X + X ≤ 21
5 10
3
Sí X1=0 X ₂ ≤21 X2=70 (0,70)
10
3
Sí X1=0 X ₁ ≤21 X1=45 (45,0)
5
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 29 | 228
A (0,0) 0
B (35,0) 1400
C (25,25) 1750
D (0,25) 750
La solución óptima para este problema nos remite que la empresa deberá de producir 25 toneladas
de aditivo de y 20 toneladas de base disolvente para lograr una máxima utilidad de 1600 dólares.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 30 | 228
(2.2) PROBLEMA DE MINIMIZACION
El Rancho Holiday Meal Turkey está considerando comprar dos marcas diferentes de alimento para pavo
y mezclarlos para ofrecer una buena dieta de bajo costo para sus aves. Cada alimento contiene en
proporciones variables, algunos de los tres ingredientes nutricionales esenciales para pavos de engorda.
Por ejemplo cada libra de la marca 1 contienen 5 onzas del ingrediente A, 4 onzas del ingrediente B y 0.5
onzas del ingrediente C. Cada libra de la marca 2 contiene 10 onzas del ingrediente A, 3 onzas del
ingrediente B, pero nada del ingrediente C. La marca 1 de alimento cuesta al rancho 2 centavos de dólar
por libra; en tanto que la marca 2 de alimento le cuesta 3 centavos de dólar por libra. El propietario del
rancho desea utilizar la PL para determinar la dieta con un costo mínimo que cumpla con el requisito
mínimo de ingesta mensual de cada ingrediente nutricional.
5 x ₁+10 x ₂ ≥ 90
Min Z = 40X1 + 30X2
X1 = Nº Libras de la Ingrediente A
Sujeto a:
marca 1 de
alimento
4 x ₁+3 x ₂ ≥ 48 5 x ₁+10 x ₂ ≥ 90 Ingrediente A
comprado
Ingrediente B 4 x ₁+3 x ₂ ≥ 48 Ingrediente B
Min Z = 2X1 + 3X2
X2 = Nº de libras de 0.5 x 1 ≥ 1.5 Ingrediente C
la marca 2 de 0.5 x 1 ≥ 1.5
Ingrediente C
alimentos X ₁ ≥0 No NegatividadX ₂ ≥ 0 No
comprado X ₁ ≥0X ₂ ≥ 0 Negatividad
No Negatividad
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 31 | 228
Método grafico
Para Ingrediente A si X1 = 5 X 1 +10 X 2 ≥90 X 2 =9 (0,9)
si X2 = 0 5 X 1 +10 X 2 ≥90 X 1 =18 (18,0)
Para Ingrediente B si X1 =0 4 X 1 +3 X 2≥ 48 X 2 =16 (0,16)
si X2 = 0 4 X 1 +3 X 2≥ 48 X 1 =12 (12,0)
Para Ingrediente C si X2 =0 0.5 X 1 ≥ 1.5 X 1= 3 (3,0)
La solución óptima para este problema nos remite que El Rancho Holiday Meal Turkey deberá
comprar 8.4 del primer alimento para pavo y 4.8 del segundo alimento y con ello lograr una
minimización utilidad de 31.2 dólares por libras.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 32 | 228
(2.2.1) PROBLEMARIO DE MAXIMIZACION Y MINIMIZACION
X1 ≤100
Sujeto a:
X2 ≤80 1X1 ≤100
X1
1X2 ≤80
Max 5X1+5X2
2X1+4X2
X2 2X1+4X2 ≤400
≤400
X1+X2≥0
X1+X2≥0
Método grafico
Para MP1 Sí X1=0 X ₁ ≤100 X2=100 (100,0)
Para MP2 Sí X2=0 X ₂ ≤80 X1=100 (0,80)
Para MP3 Si X 1 =0 2 X 1 +4 X 2 ≤ 400 X 2=100 (0,100)
Si X 2 =0 2 X 1 +4 X 2 ≤ 400 X 1=200 (200,0)
La solución óptima para este problema nos remite que el punto C es lo idóneo obteniendo 55 del
punto A y 100 del B dando como resultado 510 del total.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 33 | 228
2.- Compañía Flair Furniture
La compañía Flair Furniture fabrica mesas y sillas de bajo precio. El proceso de fabricación de cada una es
similar, ya que ambas requieren cierto número de horas de trabajo de carpintería, así como cierto
número de horas de trabajo en el departamento de pintura y barnizado. Cada mesa requiere de 4 horas
de carpintería y 2 horas en el taller de pintura y barnizado. Cada silla requiere de 3 horas de carpintería y
1 hora en la pintura y barnizado. Durante el periodo de producción actual están disponibles 240 horas de
tiempo de carpintería, asi como 100 horas de tiempo de pintura y barnizado. Cada mesa vendida genera
una utilidad de $70; cada silla fabricada se vende con una utilidad $50.
El problema de Flair Furniture es determinar la mejor combinación posible de mesas y sillas a fabricar,
con la finalidad de alcanzar la utilidad máxima. La empresa desea que esta situación de mezcla de
producción se formule como un problema de PL.
Empezamos con un resumen de la información necesaria para formular y resolver este problema (véase
la tabla 7.2) .Esto nos ayuda a entender el problema que se enfrenta.
tabla 7.2
Horas requeridas para producir 1 unidad Horas disponibles esta
Departamento Mesas(T) Sillas (C) semana
Carpintería 4 3 240
Pintura y barnizado 2 1 100
Utilidad por unidad $70 $50
4 X 1 +3 X 2 ≤240
Max 70X1+50X2
X1 = Nº hrs
requeridas para Sujeto a:
mesas 2 X 1 +1 X 2 ≤ 100 4 X 1 +3 X 2 ≤240
Max 70X1+50X2 2 X 1 +1 X 2 ≤ 100
X2 Nº hrs
requeridas para
silla X1 ≥ 0 X1 ≥ 0
X2 ≥ 0 X2 ≥ 0
Método grafico
Para HRM Sí X1=0 3 X 2 ≤240 X 2 =80 (0,80)
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 34 | 228
Sí X2=0 4 X 1 ≤240 X 1 =60 (60,0)
Para HRS Sí X1=0 X 2 ≤100 X 2 =100 (0,100)
Sí X2=0 2 X 1 ≤ 10 0 X 1 =50 (50,0)
La solución óptima para este problema nos remite que el punto B es lo idóneo, donde el
requerimiento de mesas es de 50 y el de sillas 100, dando un total de 8500 de utilidad neta.
MAX 2X1+6X2
SUJETO A
2X1+4X2 12
6X1+4X2 24
X1,X2 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 35 | 228
X2 = Sujeto a
2X1 +4X2 12
X1,X2 0 6X1+4X2 24
X1,X2 0
Método grafico
Sí X1=0 4 X 2 ≤12 X 2 =3 (0,3)
MP1
Sí X2=0 2 X 1 ≤ 12 X 1 =6 (6,0)
Sí X1=0 4 X 2 ≤24 X 2 =6 (0,6)
MP2
Sí X2=0 6 X 1 ≤ 24 X 1 =4 (4,0)
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 36 | 228
Punt Coordenada Unidad
o
A (0,0) 0
B (4,6) 30
C (3,1.25) 12.75
D (3,6) 27
A) La solución óptima es D
2 X 1 +4 X 2 ≤ 1 2
Max 2x1+6x2
X1 6 X 1 + 4 X 2 ≤24 Sujeto a
Max 2x1+6x2 2X1 +4X2 12
X2 6X1+4X2 24
X1,X2 0
X1,X2 0
B) La solución óptima es B
C) A,B,C y D
4.- PROBLEMA
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 37 | 228
Par es un pequeño fabricante de equipo y accesorios para golf cuyo distribuidor lo convenció de que
existe un Mercado tanto para la bolsa de golf de precio medio, conocida como modelo Estándar, como
para la bolsa de golf de precio elevado conocida como modelo Deluxe.
El distribuidor tiene tanta confianza en el mercado que si Par puede fabricar las bolsas a un precio
competitivo, el distribuidor está de acuerdo en adquirir todas las bolsas que Par pueda fabricar en los
siguientes tres meses. Un análisis cuidadoso de los requerimientos de fabricación dieron como resultado
la tabla siguiente que muestra las necesidades de tiempo de producción para las cuatro operaciones de
manufactura requeridas y la estimación por parte del departamento de contabilidad de la contribución a
la utilidad por bolsa
El director de manufactura estima que durante los siguientes tres meses estarán disponibles 630 horas
de tiempo de corte y teñido, 600 horas de tiempo de costura, 708 horas de tiempo de terminado y 135
horas de tiempo de inspección y empaque para la producción de las bolsas de golf
a) Si la empresa desea maximizar la contribución total a la utilidad ¿Cuántas bolsa de cada modelo
deberá fabricar?
b) ¿Qué contribución a la utilidad puede obtener Par de estas cantidades de producción?
c) ¿Cuántas horas de producción se programaran para cada operación?
d) ¿Cuál es el tiempo de holgura de cada operación?
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 38 | 228
X2 ≥ 0
Método grafico
Sí X1=0 1 X 2 ≤ 630 X 2 =630 (0,630)
Corte 7
Sí X2=0 X ≤630 X 1 =900 (900,0)
10 1
5
Sí X1=0 X ≤ 600 X 2 =720 (0,720)
6 2
Costura
1
Sí X2=0 X ≤600 X 1 =600 (600,0)
2 1
2
Sí X1=0 X ≤708 X 2 =1062 (0,1062)
Terminado 3 2
Sí X2=0 1 X 1 ≤ 780 X 1 =708 (600,0)
1
Sí X1=0 X ≤135 X 2 =540 (0,540)
Inspección y 4 2
Tanque 1
Sí X2=0 X ≤135 X 1 =1350 (1350,0)
10 1
B) $7668 de utilidad
C)
Corte y Teñido (7/10)(540) + 252 = 630
Costura (1/2) (540) + (5/6) (252) = 480 600 120
Terminando (540) + (2/3) (252) = 708
Inspección y Empaque (1/10) (540) + (1/4) (252) = 117 135 18
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 39 | 228
D)
Terminado 120 horas
Inspección y empaque 18 horas
Suponga que la administración de Par (problema15) se encuentra con la siguiente situación
E)
a) El departamento de contabilidad revisa su estimación de contribución a la utilidad para la bolsa
Deluxe a 18 dólares por bolsa.
Tiempo de producción (horas)
Producto Corte y teñido costura terminado Inspección y Utilidad por
empaque bolsa
Estándar 7/10 1/2 1 1/10 $10
Deluxe 1 5/6 2/3 1/4 $18
b) Aparece disponible la nueva materia prima de bajo costo para la bolsa estándar y la contribución
a la utilidad por bolsa estándar puede incrementarse a 20 dólares por bolsa(suponga que la
contribución a la utilidad de la bolsa Deluxe es el valor original de 9 dólares)
MAX 10X1+9X2
SUJETO A:
7
X +1 X 2 ≤630 CORTE
10 1
1 5
X + X 2 ≤ 600 COSTURA
2 1 6
2 1 1
1 X 1 + X 2 ≤780 Term . X + X 2 ≤ 135
3 10 1 4
INSP
2 1 1
1 X 1 + X 2 ≤780 Term . X + X 2 ≤ 135
3 10 1 4
INSP
X1 ≥ 0
X2 ≥ 0
5.- PROBLEMA
Para un cliente nuevo, a Innis se la ha autorizado invertir hasta 1,200,000 dólares en dos fondos de
inversión:
o un fondo de acciones y
o un fondo de mercado de dinero.
Cada unidad del fondo de acciones cuesta 50 dólares con una tasa de rendimiento anual de 10%;
Cada unidad del fondo de mercado de dinero cuesta 100 dólares con una tasa de rendimiento anual de
4%.
El cliente desea minimizar el riesgo, pero quiere tener un ingreso anual sobre la inversión de por lo
menos $ 60,000 dólares.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 41 | 228
De acuerdo con el sistema de medición de riesgo de Innis cada unidad adquirida en el fondo de acciones
tienen un índice de riesgo de 8 y cada unidad adquirida en el fondo de mercado de dinero tienen un
índice de riesgo de 3. El índice de riesgo más elevado asociado con el fondo de acciones indica
simplemente que se trata de la inversión más riesgosa.
El cliente de Innis también ha especificado que se inviertan por lo menos 300,000 dólares en el fondo del
mercado de dinero.
¿Cuántas unidades de cada uno de los fondos deberá adquirir Innis para el cliente, si el objetivo es
minimizar el índice de riesgo total para esta cartera?
50 X 1 +100 X 2 ≤1200000
MIN Z=8 X 1+3 X 2
X1= Fondo de
Sujeto a
Acciones 5 X 1 +4 X 2 ≥60000 50 X 1 +100 X 2 ≤1200000
MIN Z=8 X 1+3 X 2 5 X 1 +4 X 2 ≥60000
X2=Fondo de
Mercado de X 2 ≥ 3000
diner X 2 ≥ 3000
X 1 ≥ 0X 2 ≥ 0
X 1 ≥ 0X 2 ≥ 0
Método Gráfico:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 42 | 228
Punt Coordenada Unidad
o
A (4000,10000) 62,000
B (18000,3000) 153,000
C (9600,3000) 85,800
6.- PROBLEMA
Considere el PL
MIN 2X1 +2 X2
SUJETO A
1X1 +3 X2 12
3X1 +1 X2 13
1X1 - 1 X2 = 3 a).-Muestre la región factible
X1 , X2 0 b).-¿Cuáles son los puntos extremos de la región factible
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 43 | 228
3 x 1+ x 2 ≤13 SUJETO A :
x 1+ 3 x 2 ≤12 … C 1
Min z= 2X1 + 2X2 x 1−x 2=3 3 x 1+ x 2 ≤13…C2
X2 x 1−x 2=3…C3
x1 ¿ ≥ 0 x1 ¿ ≥ 0
no negatividad
x2 ≥ 0 x2 ≥ 0
Método Grafico:
Para C 1 …. Si x 1=0 … ..3 x 2=12… x 2=4 … ( 0,4 )
Si x 2=0 … .. x 1=12 … ( 12,0 )
Para C 2 … . Si x 1=0 … x 2=13 … ( 0,13 )
13 13
Si x 2=0 … ..3 x1 =13 … x 1= …
3 ( 3 )
,0
Para C 3 … . SI x 1=0 , … x 2=3 … ( 0,3 )
Si x 2=0 … .. x 1=3 … ( 3,0 )
A(12,0)
B(3.4,2.9)
C(0,13)
c) Por lo tanto el punto optimo para minimizar es (0,13) que nos da una utilidad de 26.
8.- PROBLEMA
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 44 | 228
Greentree Kennels Proporciona alojamiento para una noche para mascotas. Una característica particular
de Greentree es la calidad del cuidad que reciben las mascotas, incluyendo una excelente alimentación.
La comida para perros de la perrera se elabora mezclando dos alimentos de marca para perros a fin de
obtener lo que la perrera identifica como una dieta para perros bien balanceada. Los datos para las dos
comidas para perros son los siguientes
Si Greentree desea asegurarse de que los perros reciben por lo menos 5 onzas de proteínas y como
mínimo 3 onzas de grasas cada día ¿Cuál es la mezcla de costo mínimo de los dos alimentos para perros
.30 X 1 +.20 X 2 ≥5
Método Gráfico:
Para C 1 …. Si x 1=0 … ..20 x2 =5 … ( 0,1 )
Si x 2=0 … ..30 x1 =5 … (1.5,0 )
Para C 2 … . Si x 1=.30 … x 2=3 … ( 0 ,.9 )
Si x 2=0 … ..15 x1 =3 … x 1=… (.45,0 )
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 45 | 228
Punt Coordenada Unidad
o
A (0,25) 1.25
B (20,0) 1.2
C (15,2.5) 1.03
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 46 | 228
9.-PROBLEMA
Los administradores de Healtech Foods están considerando desarrollar un nuevo bocadillo bajo en
grasas.
Se trata de una mezcla de dos tipos de cereales, cada uno de ellos con distintas características en fibras,
grasas y proteínas.
La tabla siguiente muestra estas características por onza de cada tipo de cereal.
Note que cada onza de cereal A proporciona dos gramos de fibra dietética y que cada onza del cereal B
da 1.5 gramos de fibra dietética, por lo que si Healtech fuera a desarrollar el nuevo producto utilizando
una mezcla formada de 50% de cereal A y 50%de cereal B.
Los requisitos nutricionales de Healtech exigen que cada onza del nuevo alimento tenga por lo menos
1.7 gramos de fibra dietética, no más de 2.8 gramos de grasas y no más de 3.6 gramos de proteínas.
El costo del cereal A es de $0.02 por onza y el del B es de $ 0.025 por onza.
Healtech desea determinar cuánto de cada cereal es necesario para producir una onza del nuevo
producto al menor costo posible.
a) Formule el modelo de PL
b) Resuelva el problema utilizando el procedimiento de solución grafica
c) ¿Cuáles son los valores de las variables de holgura y de excedente
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 47 | 228
X 1 ≥ 0X 2 ≥ 0
Método Gráfico:
Para C 1 …. Si x 1=0 … ..1.5 x2 =1.7 … ( 0,2.55 )
Si x 2=0 … ..2 x 1=1.7 … ( 3.4,0 )
Para C 2 … . Si x 1=0 … 3 x 2=2.8 … ( 0,8.4 )
Si x 2=0 … ..2 x 1=2.8 … x 1=… ( 5.6,0 )
Para C 3 … . Si x 1=0 … ..3 x 2=3.6 … ( 0,10.8 )
Si x 2=0 … ..4 x 1=3.6 … ( 14.4,0 )
Para C 4 … . Si x 1=0 … 1 x2 =1… ( 0,1 )
Si x 2=0 … ..1 x 1=1 … x 1=… ( 1,0 )
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 48 | 228
10.-PROBLEMA
Una multinacional farmacéutica desea fabricar un compuesto nutritivo a base de dos productos
A y B.
El compuesto tiene que tener, al menos, 25g de proteínas, 6g de grasas y 30g de azúcares.
e) costo del producto A es de 0.6 u.m./g. y el de B es de 0.2 u.m./g.
¿Cuántos gramos de cada producto debe tener el compuesto para que el costo total sea mínimo?
%Proteinas % grasas % azúcar Costo
Producto A 30 1 10 0.6
Producto B 5 7 10 0.2
Requerido en el 25g 6g 30g
compuesto
30 X 1 +5 X 2 ≥25
MIN Z=0.6 X 1+ 0.2 X 2
1 X 1 +7 X 2 ≥6 Sujeto a:
X1= A 30 X 1 +5 X 2 ≥25
MIN Z=0.6 X 1+ 0.2 X 2 1 X 1 +7 X 2 ≤6
X2=B 10 X 1 +10 X 2 ≥30 10 X 1 +10 X 2 ≤30
X 1 ≥ 0X 2 ≥ 0
X 1 ≥ 0X 2 ≥ 0
Método Gráfico:
Para C 1 …. Si x 1=0 … ..5 x 2=25 … ( 0,125 )
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 49 | 228
Si x 2=0 … ..1 x 1=25 … ( 25,0 )
Para C 2 … . Si x 1=0 … 7 x 2=6 … ( 0,42 )
Si x 2=0 … ..21 x 1=6 … ( 126,0 )
Para C 3 … . Si x 1=0 … ..10 x 2=30 … ( 0,300 )
Si x 2=0 … ..10=30 … ( 300,0 )
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 50 | 228
(2.3) MODELADO
Selección de medios de comunicación
o Los problemas de selección de medio de comunicación pueden abordarse con PL desde dos
enfoques.
El objetivo sería maximizar la exposición de la audiencia o
Minimizar los costos de publicidad
o Los modelos de Programación Lineal se han utilizado en el campo de la publicidad como una
ayuda en la decisión para seleccionar una mezcla de medios de comunicación efectiva.
o Algunas veces la técnica se emplea en la asignación de un presupuesto fijo o limitado, que
podría incluir, comerciales de radio o televisión, anuncios en periódicos, correo directo,
anuncios en revistas, etc.
o En otras aplicaciones el objetivo es maximizar la exposición de la audiencia.
o Pueden surgir restricciones sobre la mezcla de medios de comunicación permitida a través de
requerimientos de contratos, disponibilidad de medios limitada o políticas de la compañía.
El club Win Big Gambling promueve el juego en giras de una ciudad grande del Medio Oeste de Estados
Unidos a los casinos de Bahamas. El club tiene un presupuesto de hasta $ 8000 semanales para
anuncios locales. El dinero se asignara entre cuatro medios de comunicación: spots en televisión,
anuncios en periódicos y dos tipos de comerciales en radio. La meta de Win Big es llegar a la audiencia de
mayor potencial más grande posible, usando los diferentes medios de comunicación.
La siguiente tabla presenta el número de jugadores potenciales expuestos mediante un anuncio, en cada
uno de los cuatro medios. También proporciona el costo por anuncio colocado y el máximo número de
ellos que se puede comprar por semana.
Las condiciones contractuales de Win Big requieren que se coloquen al menos cinco spots de radio cada
semana. Para asegurar una campaña promocional de amplio espectro, la gerencia también insiste en que
no se gasten más de $ 1,800 por semana en los comerciales por radio.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 51 | 228
Al formular esto como PL el primer paso es entender cabalmente el problema. Algunas veces hacer
preguntas del tipo ¿Qué sucedería si? Ayuda a comprender la situación. En este ejemplo ¿Qué ocurriría si
exactamente se usaran cinco anuncios de cada tipo? ¿Cuánto costaría esto? ¿a cuántas personas
llegaría? Sin duda ayuda la disponibilidad de las hojas de cálculo para obtener soluciones ya que se
escriben las formular para calcular el costo y el número de personas expuestas. Una vez que se entiende
la situación se formula el modelo.
X1 X2 X3 X4 RHS Dual
Maximize 5000 8500 2400 2800
Constraint 1 1 0 0 0 <= 12 0
Constraint 2 0 1 0 0 <= 5 2718,75
Constraint 3 0 0 1 0 <= 25 0
Constraint 4 0 0 0 1 <= 20 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 52 | 228
Constraint 5 0 0 290 380 <= 1800 2,025862
Constraint 6 800 925 290 380 <= 8000 6,25
Constraint 7 0 0 1 1 >= 5 0
Solution-> 1,96875 5 6,206897 0 $67.240,3
2.-Investigación de mercados
El siguiente ejemplo ilustra como los encuestadores estadísticos llegan a decisiones estratégicas con PL
Management Sciences Associates (MSA) es una empresa de investigación de mercados con sede en
Washington D.C. que realiza encuestas al consumidor. Uno de sus clientes es el servicio de prensa
nacional que periódicamente levanta encuestas políticas sobre cuestiones de interés general. En una
encuesta para el servicio de prensa, MSA determina que debe llenar varios requisitos para obtener
conclusiones estadísticas validas acerca de un aspecto sensible de las nuevas leyes de inmigración
estadounidense:
2. Encuestar al menos 1,000 hogares, cuyos jefes de familia tengan 30 años de edad o menos
3. Encuestar al menos 6000 hogares cuyos jefes de familia tengan entre 31 y 50 años de edad.
4. Asegurar que al menos el 15% de los encuestados en total, vivan en un estado de la frontera
con México
5. Asegurar que no más de 20% de los encuestados que tienen 51 años de edad o más, tengan esa
edad y vivan en un estado de la frontera con México.
MSA decide que todas las encuestas deberían realizarse en persona y estima que los costos por llegar a
la gente en cada categoría de edad y región son las siguientes:
MSA quiere cumplir los cinco requisitos del muestreo al menor costo posible
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 53 | 228
Al formular esto como un programa lineal, el objetivo es minimizar el costo.
X1= C.F +30 7.5 X 1 +6.9 X 2 +6.8 X 3 +7.2 X 4 + 5.5 X 5+ 6.1 X 6 ≥ 2300
Min Z=7.5 X 1 +6.9 X 2 +6.8 X 3+7.2 X 4 +5.5 X
X2= S.F +30
SUJETOA A:
X3= C.F 31- X 1 + X 2 ≥ 1000 7.5 X 1 +6.9 X 2 +6.8 X 3 +7.2 X 4 + 5.5 X 5+ 6.1 X 6
50 X 1 + X 2 ≥ 1000
Min Z=7.5 X 1 +6.9 X 2 +6.8 X 3+7.2 X 3 + X 4 ≥ 6000
X4= S.F 31- X 3 + XX44≥+5.5
6000X 5 +6.1 X 6 X1+X2+X3≥0.15(X1+X2+X3+X4+X
50 5+X6)
X1+X2+X3≥ 0.15(X1+X2+X3+X4+X (hogares de la frontera)
X5= C.F +51 5+X6)
X 5 ≥ .2(X 5 + X 6 ) ≥0
(hogares de la frontera)
X6= S.F +51 X1 , X2 , X3 , X4 , X5 , X6≥ 0
X 5 ≥ .2(X 5 + X 6 ) ≥0
X1 , X2 , X3 , X4 , X5 , X6≥ 0
X1 X2 X3 X4 X5 X6 RHS Dual
Minimize 7,5 6,9 6,9 7,2 5,5 6,1
Constraint 1 1 1 1 1 1 1 >= 2300 0
Constraint 2 1 1 0 0 0 0 >= 1000 -6,9
Constraint 3 0 0 1 1 0 0 >= 6000 -6,9
Constraint 4 85 -15 85 -15 85 15 >= 0 0
Constraint 5 0 0 0 0,8 0 0,2 <= 0 0
-
Constraint 6 1 0 0 0 0 0 >= 0 0,6000
004
Constraint 8 0 1 0 0 0 0 >= 0 0
NEW Constraint 8 0 0 1 0 0 0 >= 0 0
-
NEW Constraint 9 0 0 0 1 0 0 >= 0 0,2999
999
NEW Constraint
0 0 0 0 1 0 >= 0 -5,5
10
NEW Constraint
0 0 0 0 0 1 >= 0 -6,1
11
-3,31E- 1000,0
Solution-> 6000 0 0 0 $48.300,
06 02
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 54 | 228
LOS COSTOS TOTALES DE LAS ENCUESTAS SERIAN DE $48,300
3.-Mezcla de productos
Fifth Avenue Industries, un conocido fabricante local de ropa para caballero, produce cuatro variedades
de corbatas. Una es más costosa de seda pura, otra está hecha de poliéster, otra más es una mezcla de
poliéster y algodón y la cuarta es una mezcla de seda y algodón.
La empresa tienen contrataos fijos con varias cadenas de tiendas por departamentos para comercializar
sus corbatas.
Los contratos requieren que Fifth Avenue Industries surta una cantidad minima de cada corbata, pero
permitirán una demanda mayor , si la empresa elige cumplir esa demanda.
(Dicho sea de paso, la mayoría de las corbatas no llevan etiqueta de Fifth Avenue, sino etiquetas propias
de las tiendas).
La tabla siguiente resume la demanda del contrato para cada uno de los cuatro estilos de corbata, el
precio de venta por corbata y los requerimientos de tela para cada variedad.
La meta de Fifth Avenue es maximizar su ganancia mensual. Debe decidir la política para la mezcla de
productos.
Demanda
Precio de Mínimo de Material
Variedad de mensual. Requerimientos
venta por contrato requerido por
corbatas Contrato de materiales
corbatas mensual corbata(yardas)
(máximo)
Toda de seda 19.24 5,000 7,000 0.125 100% seda
Toda de
8.70 10,000 14,000 0.08 100% poliéster
poliéster
Mezcla
50% poliéster-
1,poliéster y 9.52 13,000 16,000 0.10
50% algodón
algodón
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 55 | 228
Mezcla 2,
60% seda-40%
seda y 10.64 5,000 8,500 0.11
algodón
algodón
X1 X2 X3 X4 RHS Dual
Maximize 16,24 8,22 8,77 8,66
Constraint 1 0,125 0 0 0,066 <= 1200 129,92
Constraint 2 0 0,08 0,05 0 <= 3000 0
Constraint 3 0 0,05 0 0,044 <= 1600 0
Constraint 4 1 0 0 0 >= 5000 0
Constraint 5 1 0 0 0 <= 7000 0
Constraint 6 0 1 0 0 >= 10000 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 56 | 228
Constraint 7 0 1 0 0 <= 14000 8,22
Constraint 8 0 0 1 0 >= 13000 0
Constraint 9 0 0 1 0 <= 16000 8,77
Constraint 0 0 0 1 >= 5000 0
10
Constraint 0 0 0 1 <= 8500 8,53E-02
11
Constraint 1,00E+00 0 0 0 >= 0 0
12
Constraint 0 1 0 0 >= 0 0
13
Constraint 0 0 1 0 >= 0 0
14
Constraint 0 0 0 1 >= 0 0
15
Solution-> 5112 14000 16000 8500 $412.028,89
PARA MAXIMIZAR SUS GANANCIAS DEBE DE AUNMENTAR EN SEDA A 5112 PIEZAS, ENPOLIESTER
14000, EN LA MEZCLA DE POLIESTER Y ALGODÓN 16000 Y EN LA DE SEDA Y ALGODÓN 85000. CON
UNA GANANCIA NETA DE $412,028.89
4.-Programación de la producción
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 57 | 228
Greenberg Motors Inc. Fabrica dos motores eléctricos distintos para venta regulada por un contrato con
Drexel Corp., un fabricante conocido de electrodomésticos pequeños para cocina.
Su modelo GM3A se encuentra en muchos procesadores de alimentos Drexel y su modelo GM3B se usa
en el ensamble de licuadoras.
Tres veces al año, el funcionario de compras de Drexel contrata a Irwin Greenberg, el fundador de
Greenberg Motors y coloca una orden mensual para los siguientes cuatro meses.
La demanda de Drexel de motores varía cada mes según sus propios pronósticos de ventas, capacidad de
producción y posición financiera.
Greenberg acaba de recibir la orden para enero-abril y debe iniciar su propio plan de producción de
cuatro meses.
1.-La compañía debe cumplir la demanda de cada uno de los productos cada mes. Además la compañía
desea tener 450 unidades del GM3A y 300 unidades del GM3B en inventario al final de abril, pues se
espera que la demanda de mayo sea algo más alta que la de los meses anteriores.
2.-Hay costos por almacenar o mantener para cualquier inventario que quede al final del mes. De
manera que producir demasiadas unidades adicionales de cualquier producto quizás no sea deseable.
El costo mensual por almacenar asignado al GM3A es de $0.36 por unidad, mientras que el costo
mensual por almacenar para el GM3B es de $0.26 por unidad
3.-La compañía ha podido mantener la política de que no haya despidos y quiere continuar así. Esto es
más fácil si las horas de mano de obra no fluctúan demasiado de un mes a otro. Se recomienda
mantener un programa de producción que requiera entre 2,240 y 2,560 horas de mano de obra al mes.
El GM3A requiere 1.3 horas de mano de obra por unidad, en tanto que el GM3B requiere tan solo de 0.9
horas.
4.-Las limitaciones de almacén no pueden excederse sin incurrir en costos adicionales. Hay lugar al final
del mes nada más para 3300 unidades de GM3A y GM3B combinados.
Aunque estos factores algunas veces están en conflicto, Greenberg ha encontrado que la PL es una
herramienta efectiva para establecer un programa de producción que minimizara el costo total.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 58 | 228
Los costos de producción actualmente son de $20 por unidad para el GM3A y $15 por unidad para el
GM3B. Sin embargo cada uno debería aumentar 10% el 1º de marzo cuando entre en vigencia el nuevo
contrato laboral.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 59 | 228
Variable Función objetivo Restricciones Modelo
A1-IA1=800
Ai= GM3A en mes
IA1+A2-IA2=700 MIN Z=20 A 1+20 A 2+ 22 A 3+22 A 4 +15 B 1+
A1=GM3A Enero SUJETO A :
A2=GM3A Febrero IA2+A3-IA3=1000
A1-IA1=800
A3=GM3A Marzo IA3+A4-IA4=1100 IA1+A2-IA2=700
A4=GM3A Abril B1-IB1=1000 IA2+A3-IA3=1000
IA3+A4-IA4=1100
IB1+B2-IB2=1200
Bi= GM3B en mes B1-IB1=1000
B1=GM3B Enero IB2+B3-IB3=1400 IB1+B2-IB2=1200
B2=GM3B Febrero IB3+B4-IB4=1400 IB2+B3-IB3=1400
B3=GM3B Marzo IA4=450 IB3+B4-IB4=1400
B4=GM3B Abril IA4=450
IB4=300 IB4=300
IAi= GM3A en Inv.F 1.3.A1+0.9B1 2240 1.3.A1+0.9B1 2240
MIN Z=20 A 1+20 A 2+ 22 A 3+22 A 4 +15 B 1+15 B 2+.36 B 3+16.5 B 4 +.36
2+0.9B2 2240
IA2+0.9B
1+.36 IA 2+.36 IA 3+.36 IA 4+.26 I
IA1=GM3A Enero 1.3.A 1.3.A 2 2240
IA2=GM3A Febrero 1.3.A3+0.9B3 2240 1.3.A3+0.9B3 2240
IA3=GM3A Marzo 1.3.A4+0.9B4 2240 1.3.A4+0.9B4 2240
IA4=GM3A Abril 1.3.A1+0.9B1 2560 1.3.A1+0.9B1 2560
1.3.A2+0.9B2 2560 1.3.A2+0.9B2 2560
1.3.A3+0.9B3 2560 1.3.A3+0.9B3 2560
IBi= GM3B en Inv.F 1.3.A4+0.9B4 2560 1.3.A4+0.9B4 2560
IB1=GM3B Enero IA1+IB13300 IA1+IB13300
IB2=GM3B Febrero IA2+IB23300 IA2+IB23300
IB3=GM3B Marzo IA3+IB33300 IA3+IB33300
IA4+IB43300
IB4=GM3B Abril IA4+IB43300
A1+A2+A3+A4+B1+B2+B3+B4+IA1+I
A1+A2+A3+A4+B1+B2+B3+B4+IA1+I
A2+IA3+IA4+IB1+IB2+IB3+IB4≥0
A2+IA3+IA4+IB1+IB2+IB3+IB4≥0
A1 A2 A3 A4 B1 B2 B3 B4 IA1 IA IA3 IA IB IB2 IB IB RHS Dual
2 4 1 3 4
MINIMIZA 20 20 22 22 15 15 16,5 16, 0,36 0, 0,36 0, 0, 0,26 0, 0,
R 5 36 36 26 26 26
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 60 | 228
RESTRICCI 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 = 800 -
ON 1 21,43
11
RESTRICCI 0 1 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 = 700 -
ON 2 21,79
11
RESTRICCI 0 0 1 0 0 0 0 0 0 1 -1 0 0 0 0 0 = 1000 -22
ON 3
RESTRICCI 0 0 0 1 0 0 0 0 0 0 1 -1 0 0 0 0 = 1100 -22,36
ON 4
RESTRICCI 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 = 1000 -
ON 5 15,99
08
RESTRICCI 0 0 0 0 0 1 0 0 0 0 0 0 1 -1 0 0 = 1200 -16,24
ON 6
RESTRICCI 0 0 0 0 0 0 1 0 0 0 0 0 0 1 -1 0 = 1400 -16,5
ON 7
RESTRICCI 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 -1 = 1400 -
ON 8 16,74
92
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 = 450 -22,72
ON 9
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 300 -
ON 10 17,00
92
RESTRICCI 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 0 0 0 > 2240 0
ON 11 =
RESTRICCI 0 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 0 0 > 2240 0
ON 12 =
RESTRICCI 0 0 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 0 > 2240 0
ON 13 =
RESTRICCI 0 0 0 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 > 2240 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 61 | 228
ON 14 =
RESTRICCI 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 0 0 0 < 2560 1,100
ON 15 = 9
RESTRICCI 0 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 0 0 < 2560 1,377
ON 16 = 8
RESTRICCI 0 0 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 0 < 2560 0
ON 17 =
RESTRICCI 0 0 0 1,3 0 0 0 0,9 0 0 0 0 0 0 0 0 < 2560 0,276
ON 18 = 9
RESTRICCI 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 < 3300 0
ON 19 =
RESTRICCI 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 < 3300 0
ON 20 =
RESTRICCI 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 < 3300 0
ON 21 =
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 < 3300 0
ON 22 =
RESTRICCI 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 > 0 0
ON 23 =
RESTRICCI 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 > 0 0
ON 24 =
RESTRICCI 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 > 0 0
ON 25 =
RESTRICCI 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 > 0 0
ON 26 =
RESTRICCI 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 > 0 0
ON 27 =
RESTRICCI 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 > 0 0
ON 28 =
RESTRICCI 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 > 0 0
ON 29 =
RESTRICCI 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 > 0 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 62 | 228
ON 30 =
RESTRICCI 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 > 0 0
ON 31 =
RESTRICCI 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 > 0 -
ON 32 = 0,151
1
RESTRICCI 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 > 0 0
ON 33 =
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 > 0 0
ON 34 =
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 > 0 -
ON 35 = 0,010
8
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 > 0 0
ON 36 =
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 > 0 -
ON 37 = 0,010
8
RESTRICCI 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 > 0 0
ON 38 =
SOLUCION 1276, 223,0 1757, 792,3 10 2522, 77,77 17 476,9 0 757,6 45 0 1322, 0 30 16929
923 768 692 077 00 222 76 00 231 923 0 222 0 4,9
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 63 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 64 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 65 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 66 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 67 | 228
Método Simplex.
En la solución gráfica observamos que la solución óptima está asociada siempre con un punto extremo
del espacio de soluciones.
El método simplex emplea un proceso iterativo que principia en un punto extremo factible,
normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que
se llega por último al punto óptimo.
Existen reglas que rigen la solución del siguiente punto extremo del método simplex:
El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un
punto extremo adyacente. La elección específica de un punto a otro punto depende de los coeficientes
de la función objetivo hasta encontrar el punto óptimo. Al aplicar la condición de optimidad a la tabla
inicial seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser una de
las variables artificiales.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 68 | 228
c. Se determina la nueva solución básica factible construyendo una nueva tabla en la forma
apropiada de eliminación de Gauss, debajo de la que se tiene.
7. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el
renglón entre el número pivote, entonces:
Renglón pivote nuevo = renglón pivote antiguo / número pivote
8. Para completar la primera iteración es necesario seguir usando la eliminación de Gauss para
obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar
este cambio se utiliza la siguiente fórmula:
Renglón nuevo = renglón antiguo – (coeficiente de la columna pivote X renglón pivote nuevo)
9. Cuando el coeficiente es negativo se utiliza la fórmula:
Renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo)
Tabla Simplex.
Sujeto a:
X2 >=0
Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el proceso iterativo hasta encontrar
la solución óptima si es que está existe.
Tabla Óptima:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 69 | 228
BASE Z X1 X2 S1 S2 S3 SOLUCION RAZON
Z 1 0 0 0 2 0 500
S1 0 0 0 1 -2 3 90
X1 0 1 0 0 1 -2 10
X2 0 0 1 0 0 1 120
Solución: Z = $500
Fabricando
X1 = 10
X2 = 120
Sobrante de
S1 = 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 70 | 228
(2.4.1) PROBLEMARIO DE SIMPLEX
Problema 1
MAX Z=6X1+ 10X2
SUJETO A:
6X1+2X2 ≤ 36
X1 ≤8
X2 ≤12
X1,X2≥0
Teniendo el modelo de P.L. vamos a sacar las variables de holgura; S 1, S2, S3.
Una vez teniendo las variables de holgura vamos a pasar igual a Z con cero todos los miembros
que se encuentren después de Z pasan con su valor contrario.
Z - 6X1 - 10X2 + S1 + S2 + S3 = 0
MAX Z=6X1+ 10X2
6X1+2X2 + S1 = 36
6X1+2X2 + S1 =36
X1 + S2 =8
X1 + S2 =8
X2 +S3 =12
X2 +S3 =12
Tabla inicial
Base Z X1 X2 S1 S2 S3 Solución
Z 1 -6 -10 0 0 0 0
S1 0 6 2 1 0 0 36
S2 0 1 0 0 1 0 8
S3 0 0 1 0 0 1 12
Una vez colocadas las variables se procede a saber cuál es la fila que sale y la columna que entra.
La columna se toma por el valor más bajo, en este caso es -10, así que entra X 2
Base Z X1 X2 S1 S2 S3 Solución
Z 1 -6 -10 0 0 0 0
S1 0 6 2 1 0 0 36
S2 0 1 0 0 1 0 8
S3 0 0 1 0 0 1 12
ENTRA
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 71 | 228
Para conocer la fila que se seleccionara para salir tomaremos el valor de Solución de las holguras
y lo dividiremos entre la columna que entra, a el valor de la columna recibirá el nombre de
pivote.
Tabla inicial
Base Z X1 X2 S1 S2 S3 Solución
Z 1 -6 -10 0 0 0 0
S1 0 6 2 1 0 0 36 36/2 = 18
S2 0 1 0 0 1 0 8 8/0= ∞
12/1 = 12
S3 0 0 1 0 0 1 12
SALE
Teniendo ya los valores, se selecciona el mas bajo. Para este caso seria 12.
Tabla 1
Pasamos a hacer la Tabla 1. La cual es básicamente idéntica en cuanto a los nombres de las
columnas Z, X1, X2…S3.
Cambiará el nombre de S3 por X2, en la columna Base
Base Z X1 X2 S1 S2 S3 Solución
Z
S1
S2
X2
Base Z X1 X2 S1 S2 S3 Solución
Z
S1
S2
X2 0 0 1 0 0 1 12
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 72 | 228
1-(-10)(0)= 1
y así sucesivamente con cada valor de la fila y cada fila hasta llenar toda la tabla
Base Z X1 X2 S1 S2 S3 Solución
Z 1 -6 0 0 0 10 120
S1
S2
X2 0 0 1 0 0 1 12
VALORES DE Z VALORES DE S1
FORMULA VALOR FORMULA VALOR
1-(-10)(0) 1 0-(2)(0) 0
-6-(-10)(0) -6 6-(2)(0) 6
-10-(-10)(1) 0 2-(2)(1) 0
1-(-10)(0) 0 1-(2)(0) -1
0-(-10)(0) 0 0-(2)(0) 0
0-(-10)(1) 10 0-(2)(1) -2
0-(-10)(12) 120 36-(2)(12) 12
VALORES DE S2
FORMULA VALOR
0-(2)(0) 0
6-(2)(0) 6
2-(2)(1) 0
1-(2)(0) -1
0-(2)(0) 0
0-(2)(1) -2
36-(2)(12) 12
Base Z X1 X2 S1 S2 S3 Solución
Z 1 -6 0 0 0 10 120
S1 0 6 0 1 0 -2 12
S2 0 1 0 0 1 0 8
X2 0 0 1 0 0 1 12
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 73 | 228
Hacemos la misma acción que en la tabla inicial buscando el valor más bajo de la columna, aquí
seria X1. Entra
El valor mas bajo de las filas que seria S 1, que es quien sale.
Tabla 1
Base Z X1 X2 S1 S2 S3 Solución
Z 1 -6 0 0 0 10 120
S1 0 6 0 1 0 -2 12 2 SALE
S2 0 1 0 0 1 0 8 8
X2 0 0 1 0 0 1 12
ENTRA
Tabla 2
Tabla 2
Base Z X1 X2 S1 S2 S3 Solución
Z 1 0 0 1 0 8 132
X1 0 1 0 1/6 0 - 1/3 2
S2 0 1 0 1/6 1 1/3 6
X2 0 0 1 0 0 1 12
La tabla 2 muestra a Z con valores positivo, por ende se dice que es óptima y se toma como que
debe de terminar ahí.
DE HABER TENIDO VALORES NEGATIVOS SE HARIA UNA SIGUIEN TABLA Y ASI SUCESIVAMENTE
HASTA QUE Z QUEDE POSITIVO
En esta caso se dice que:
SOLUCION
X1=2
X2=12
Z=132
Problema 2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 74 | 228
MIN Z=2X1 - 3X2
SUJETO A:
X1+X2 ≤ 15
X1+2X2 ≤20
X1,X2≥0
Teniendo el modelo de P.L. vamos a sacar las variables de holgura; S 1, S2, S3.
Una vez teniendo las variables de holgura vamos a pasar igual a Z con cero todos los miembros
que se encuentren después de Z pasan con su valor contrario.
MIN Z=2X1 - 3X2 Z -2 X1 + 3X2 + S1 + S2 = 0
X1+X2 + S1 =15
X1+2X2 + S2 =20 X 1 + X 2 + S1 =15
X1 + 2X2 + S2 =20
Tabla inicial
Tabla inicial
Base Z X1 X2 S1 S2 Solución
Z 1 2 3 0 0 0
S1 0 1 1 1 0 15
S2 0 1 2 0 1 20
Una vez colocadas las variables se procede a saber cuál es la fila que sale y la columna que entra.
La columna se toma por el valor más ALTO, en este caso es 3, así que entra X 2
Tabla inicial
Base Z X1 X2 S1 S2 Solución
Z 1 2 3 0 0 0
S1 0 1 1 1 0 15
S2 0 1 2 0 1 20
ENTRA
Para conocer la fila que se seleccionara para salir tomaremos el valor de Solución de las holguras
y lo dividiremos entre la columna que entra, a el valor de la columna recibirá el nombre de
pivote.
Tabla inicial
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 75 | 228
Base Z X1 X2 S1 S2 Solución
Z 1 2 3 0 0 0
S1 0 1 1 1 0 15 15/1=15
S2 0 1 2 0 1 20 20/2=10 SALE
Teniendo ya los valores, se selecciona el más bajo. Para este caso seria 10.
Tabla 1
Pasamos a hacer la Tabla 1. La cual es básicamente idéntica en cuanto a los nombres de las
columnas Z, X1, X2…S3.
Cambiará el nombre de S2 por X2, en la columna Base
De X2 partiremos para poder dar los demás valores.
Tomando los valores de S2 como base los dividiremos entre el pivote que es 2.
Cada valor se divide entre el pivote que corresponde a su columna y se coloca en su lugar.
Tabla 1
Base Z X1 X2 S1 S2 Solución
Z
S1
X2 0 1/2 1 0 1/2 10
Tabla 1
Base Z X1 X2 S1 S2 Solución
Z 1 1/2 0 0 -1 1/2 -30
S1 0 1/2 0 1 - 1/2 5
X2 0 1/2 1 0 1/2 10
Hacemos la misma acción que en la tabla inicial buscando el valor más bajo de la columna, aquí
seria X1. Entra
El valor mas bajo de las filas que seria S 1, que es quien sale.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 76 | 228
Tabla 1
Base Z X1 X2 S1 S2 Solución
Z 1 1/2 0 0 -1 1/2 -30 -60
S1 0 1/2 0 1 - 1/2 5 10 SALE
X2 0 1/2 1 0 1/2 10 20
ENTRA
Tabla 2
Tabla 2
Base Z X1 X2 S1 S2 Solución
Z 1 0 0 -1 -1 -35
X1 0 1 0 2 -1 10
X2 0 0 1 -1 1 5
La tabla 2 muestra a Z con valores NEGATIVOS, por ende se dice que es óptima y se toma como
que debe de terminar ahí.
DE HABER TENIDO VALORES POSITIVOS SE HARIA UNA SIGUIEN TABLA Y ASI SUCESIVAMENTE
HASTA QUE Z QUEDE NEGATIVO
En esta caso se dice que:
SOLUCION
X1=10
X2=5
Z=-35
EL PRODUCTO X1 DEBE MINIMIZACE A 10 MIENTRAS QUE EL X2 A 5 PARA QUE SUS GASTOS SEAN DE
MENOS 35
Problema 3
MIN Z=2X1 - 3X2
SUJETO A:
X1+X2 ≤ 4
X1+X2 ≤6
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 77 | 228
X1,X2≥0
Z - X1 + 3X2 + S1 + S2 = 0
MIN Z=2X1 - 3X2
X1+X2 + S1 =4 X1+X2 + S1 =4
X1-X2 + S2 =6 X1-X2 + S2 =6
Tabla inicial
Base Z X1 X2 S1 S2 Solución
Z 1 -2 3 0 0 0
S1 0 1 1 1 0 15 4
S2 0 1 -1 0 1 20 6
Tabla 1
Base Z X1 X2 S1 S2 Solución
Z 1 -5 0 -3 0 -12
x2 0 1 1 1 0 4
S2 0 2 0 1 1 10
SOLUCION
S2=10 SI=0
X2=4
Z=-12
Problema 4
MAX Z=6X1+5X2+4X3
SUJETO A:
2X1+2X2 29≤ 90
X1+3X2+2X3 ≤150
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 78 | 228
2X1+X2+2X3 ≤120
X1,X2≥0
ENTRAR
BASE Z X1 X2 X3 S1 S2 S3 SOLUCION
Z 1 -6 -5 -4 0 0 0 0 0
S1 0 2 2 1 1 0 0 90 45
S2 0 1 3 2 0 1 0 150 150
S3 0 2 1 2 0 0 1 120 60
TABLA 1
BASE Z X1 X2 X3 S1 S2 S3 SOLUCION
Z 1 0 1 -1 3 0 0 270 -270
X1 0 1 1 0,5 0,5 0 0 45 90
S2 0 0 2 1,5 -0,5 1 0 105 70
S3 0 0 -1 1 -1 0 1 30 30
TABLA 2
BASE Z X1 X2 X3 S1 S2 S3 SOLUCION
Z 1 0 0 0 2 0 1 300
X1 0 1 1,5 0 1 0 -0,5 30
S2 0 0 3,5 0 1 1 -1,5 60
X3 0 0 -1 1 -1 0 1 30
Problema 5
MIN Z=3X1 - 8X2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 79 | 228
SUJETO A:
4X1+X2 ≤ 13
2X1+X2 ≤6
X1,X2≥0
Z - 3X1 + 8X2 + S1 + S2 = 0
MIN Z=3X1 - 8X2
4X1+X2 + S1 =13
4X1+X2 + S1 =13
2X1-3X2 + S2 =6
2X1-3X2 + S2 =6
Tabla Inicio
BASE Z X1 X2 S1 S2 SOLUCION
Z 1 3 -8 0 0 0
S1 0 4 1 1 0 13 13/4=3.25
S2 0 2 3 0 1 6 6/2=3
Tabla 1
BASE Z X1 X2 S1 S2 SOLUCION
Z 1 0 -12,5 0 -1,5 -9
S1 0 0 -5 1 -2 1
X1 0 1 1,5 0 0,5 3
SOLUCION
Z= -9
S1= 1
X1= 3
Problema 6
La empresa Alfa Textil se dedica a la fabricación de manteles de mesas. Fabrica 2 modelos; el redondo y
el rectangular. El mantel redondo consume 2 mts 2 de tela y el rectangular 3 mts 2. Además de ser
cortados y cocidos a mano tarea que lleva una hora para manteles rectangular y dos horas para
redondos. Por ultimo a los manteles rectangulares se les debe de colocar esquineros de repuesto.
Semanalmente se disponen 600 mts 2 de telas; 600 esquineros y 500 horas de corte y costura. Los
márgenes de ganancia de $8 manteles redondos y $10 manteles rectangulares ¿Cuál es la combinación
que optimiza mis ganancias?
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 80 | 228
MAX Z=8X1+10X2
SUJETO A: MAX Z= 8X1+10X2+S1+S2+S3
2X1+3X2 ≤ 600 2X1+ 3X2 +S1 = 600
2X1+1X2 ≤500 2X1+ 1X2 +S2 =500
X1+4X2 ≤600 X1+ 4X2 +S3=600
X1,X2≥0
TABLA INICIAL
BASE Z X1 X2 S1 S2 S3 SOLUCION
Z 1 -8 -10 0 0 0 0 0
S1 0 2 3 1 0 0 600 200
S2 0 2 1 0 1 0 500 500
S3 0 0 4 0 0 1 600 150,00
TABLA 1
BASE Z X1 X2 S1 S2 S3 SOLUCION
Z 1 -8 0 0 0 2 1/2 1500
S1 0 2 0 1 0 - 3/4 150 75
S2 0 2 0 0 1 - 1/4 350 175
X2 0 0 1 0 0 1/4 150 #¡DIV/0!
TABLA 2
BASE Z X1 X2 S1 S2 S3 SOLUCION
Z 1 0 0 3 1 0 2300
X1 0 1 0 - 1/4 3/4 0 225
S2 0 0 0 -2 2 1 400
X2 0 0 1 0 0 1/4 150
SOLUCION
Z= 23000
X1= 225
X2= 150
Problema 7
Z- X1- X2-3X3-2X4+S1+S2+S3
X1+2X2-3X3-2X4+S1 =8
Investigación de Operaciones 2X1+3X2-1X3-3X4 +S2 = 3
Material educativo de apoyo -X1 +3X3+2X4 +S3=3
Ing. Teresita de Jesús Marín Rojas P á g i n a 81 | 228
MAX Z=X1+X2+3X3+2X4
SUJETO A:
X1+2X2-3X3-2X4 = 8
2X1+3X2-1X3-3X4 = 3
-X1 +3X3+2X4=3
X1,X2,X3,X4≥0
BASE Z X1 X2 X3 X4 S1 S2 S3 Solución
Z 1 -1 -1 -3 -2 0 0 0 0
S1 0 1 2 -3 5 1 0 0 8
S2 0 2 3 -1 3 0 1 0 3
S3 0 -1 0 1 2 0 0 1 0
*NO ES HAY SOLUCION YA QUE AL SACAR LOS VALORES DE SALIDA ESTOS SON NEGATIVOS.
Problema 8
MAX Z=60X1+30X2+20X3 MAX Z=60X1+30X2+20X3+S1+S2+S3+S4
SUJETO A: SUJETO A:
8X1 +6X2 -X3 ≤ 48 8X1 +6X2 -X3 +S1 =48
4X1 +2X2-1.5X3 ≤20 4X1 +2X2-1.5X3 +S2 =20
2X1+1.5X2 .5X3≤8 2X1+1.5X2 .5X3 +S3 =8
X2 ≤5 X2 +S4 =5
X1,X2,X3,X4≥0
TABLA INICIAL
BASE Z X1 X2 X3 S1 S2 S3 S4 SOLUCION
Z 1 -60 -30 -20 0 0 0 0 0
S1 0 8 6 1 1 0 0 0 48 6
S2 0 4 2 1,5 1 1 0 0 20 5
S3 0 2 1,5 0,5 0 0 1 0 8 4
S4 0 0 1 0 0 0 0 1 5 #¡DIV/0!
TABLA 1
BASE Z X1 X2 X3 S1 S2 S3 S4 SOLUCION
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 82 | 228
Z 1 0 15 -5 0 0 30 0 240
S1 0 0 0 -1 1 0 -4 0 16 -16
S2 0 0 -1 0,5 1 1 -2 0 4 8
X1 0 1 0,75 0,25 0 0 0,5 0 4 16
S4 0 0 1 0 0 0 0 1 5 #¡DIV/0!
TABLA 2
BASE Z X1 X2 X3 S1 S2 S3 S4 SOLUCION
Z 1 0 5 0 10 10 10 0 280
S1 0 0 -2 0 3 2 -8 0 24
X3 0 0 -2 1 2 2 -4 0 8
X1 0 1 1,25 0 -0,5 -0,5 1,5 0 2
S4 0 0 1 0 0 0 0 1 5
SOLUCION
Z= 280
X1= 2 ECENARIO
X3=8 SILLAS
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 83 | 228
MIN Z=4X1+ X2
3X1+X2 =3
4X1+3X2 ≥6
X1+2X2 ≤4
X1,X2 ≥0
MIN Z=4X1+ X2
3X1+X2 +R1 =3 Se agregan variables artificiales (R) si son ≤ o =
4X1+3X2-X3 +R2 =6 Aparte de las V. A. se agregan V.H. estas pasaran con su
X1+2X2 +X4=4 valor contrario (X3 que entra pasa a ser –X3)
En el caso de ≤4 queda con sus valores normales ya que
cumple con la restricciones
Z-4X1- X2-0X3-MR1-MR2+0X4=0
Z-4X1- X2-0X3-100R1-100R2+0X4=0
3X1+X2 +R1 =3
M debe de tener un valor
4X1+3X2-X3 +R2 =6
grande, en este caso se
X1+2X2 +X4 =4
escoge 100
BASICA Z X1 X2 X3 R1 R2 X4 SOLUCION
Z 1 -4 -1 0 -100 -100 0 0
R1 0 3 1 0 1 0 0 3
R2 0 4 3 -1 0 1 0 6
X4 0 1 2 0 0 0 1 4
Transformar Z
Z nueva = Z actual –((Coeficiente R (-100))(Fila R1+Fila R2))
=(1,-4,-1,0,-100,0,0)-((-100)(0,7,4,-1,1,1,0,9)
(0,700, 400,-100,100, 100, 0,900)
=(0,696,399,-100,0,0,0,900)
TABLA SOLUCIO
1 BASICA Z X1 X2 X3 R1 R2 X4 N
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 84 | 228
Z 1 0 167 -100 -232 0 0 204
X1 0 1 1/3 0 1/3 0 0 1 3
1,2
R2 0 0 1 2/3 -1 -1 1/3 1 0 2 SALE
X4 0 0 1 2/3 0 - 1/3 0 1 3 1,8
ENTRA
Se selecciona la columna que entra basándose en el máximo positivo, en este caso sería X 2 como
columna pivote. Partiendo de esa columna sus valores se divide por las soluciones y se
selecciona el valor más bajo.
Con esto se puede construir las siguientes tablas por método simplex.
TABLA SOLUCIO
2 BASICA Z X1 X2 X3 R1 R2 X4 N
-100
Z 1 0 0 1/5 -98 2/5 1/5 0 3 3/5
X1 0 1 0 1/5 3/5 - 1/5 0 3/5 3
X2 0 0 1 - 3/5 - 4/5 3/5 0 1 1/5 -2
X4 0 0 0 1 1 -1 1 1 1 SALE
ENTRA
SOLUCIO
TABLA 3 BASICA Z X1 X2 X3 R1 R2 X4 N
Z 1 0 0 0 -98 3/5 -100 - 1/5 3 2/5
X1 0 1 0 0 2/5 0 - 1/5 2/5
X2 0 0 1 0 - 1/5 0 3/5 1 4/5
X3 0 0 0 1 1 -1 1 1
SOLUCION
Z=3 2/5
X1= 2/5 Se toman los valores de la última columna y se
X2=1 4/5 obtiene los resultados.
X3=1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 85 | 228
(2.6) METODO DE LAS DOS FACES
MIN. Z=4X1+X2
SUJETO A:
3X1+X2=3
4X1+3X2≥6
X1+2X2≤4
X1, X2≥0
Fase 1
MIN. Z=R1+R2
Z-R1-R2+0X1+0X2+0X3+0X4=0
SUJETO A :
3X1+X2+ R1 =3 La función objetivo se reescribe
4X1+3X2-X3+ R2 =6 cambiando los valores, agregando
X1+2X2+X 4=4 Valores e igualándolos a cero.
X1+2X2X1, X2, X3, X4, R1, R2 ≥0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 86 | 228
X4 0 1 2 0 0 0 1 4
ENTRA
Se selecciona el mayor positivo como columna pivote y sus valores son divididos entre el valor de
la solución para así conocer el valor más bajo de la fila y saber cuál es la que sale. En este caso la
columna pivote será X1 y R1 .
Se siguen los pasos para la creación de una nueva tabla donde X1 va a ser sustituido por X1.
Mediante método simples se llena la tabla
Primero los valor de la fila de R1 se dividen entre el pivote de la fila correspondiente
Luego se pasa con Z en donde Z actual menos el pivote de la fila por el valor de la fila entrante.
Esta misma operación se para para las demás filas
SOLUCIO
TABLA 1 BASICA Z X1 X2 X3 R1 R2 X4 N
Z 1 0 1 2/3 -1 -2 1/3 0 0 2
X1 0 1 1/3 0 1/3 0 0 1 3
R2 0 0 1 2/3 -1 -1 1/3 1 0 2 1,2SALE
X4 0 0 1 2/3 0 - 1/3 0 1 3 1,8
ENTRA
Como antes se vuelven a encontrar la columna que entra y la columna que sale
Será necesario la reacion de una nueva tabla hasta que los valores de la fila de Z sean todos
negativos.
Fase 2
Rescribir el modelo
MIN. Z=4X1+X2
SUJETO A:
X 1+ 1/5X3 =3/5
X2-3/5X3 =6/5
X3+X4=1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 87 | 228
X1+ 1/5X3 =3/5
X2-3/5X3 =6/5
X3+X4 =1
Se pasa al llenado de la tabla preliminar
TABLA BASICA Z X1 X2 X3 X4 SOLUCION
PRELIMINA
R Z 1 -4 -1 0 0 0
X1 0 1 0 1/5 0 3/5
X2 0 0 1 - 3/5 0 1 1/5
X4 0 0 0 1 1 1
Z= 1 -4 -1 0 0 0
0 -4 0 -4/5 0 -12/5
0 0 -1 3/5 0 -6/5
Z= 1 4 -1 0 0 0
0 4 1 1/5 0 18/5
1 0 0 1/5 0 18/5
SOLUCION
Se saca las conclusiones de la tabla con la que
Z=3 2/5
los valores de la fila de son ceros y negativo y es
aquí donde se da por concluido el método de
Investigación de Operaciones las dos faces
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 88 | 228
X1= 2/5
X2=1 4/5
X3=1
CAPITULO 3 PROGRAMACION DUAL
DEFINICIÓN DEL PROBLEMA DUAL
Los dos problemas están estrechamente relacionados en el sentido de que la solución óptima de uno
proporciona automáticamente la solución óptima al otro.
En la mayoría de los tratamientos de PL, el dual se define para varias formas del primal según el sentido
de la optimización (maximización o minimización), los tipos de ¿ y el signo de las variables (no negativas
o irrestrictas).
Este capítulo ofrece una definición única que abarca de manera automática todas las formas del primal.
Nuestra definición del problema dual requiere expresar el problema primal en la forma de ecuación
(todas las restricciones son ecuaciones con lado derecho no negativo, y todas las variables son no
negativas). Este requerimiento es consistente con el formato de la tabla inicial simplex. De ahí que
cualesquier resultados obtenidos a partir de la solución óptima primal se aplican directamente al
problema dual asociado.
Las ideas clave para construir el dual a partir del primal se resumen como sigue:
Encontrar el óptimo de un problema de optimización, es solo una parte del proceso de solución. Muchas
veces nos interesaría saber cómo varía la solución si varía alguno de los parámetros del problema que
frecuentemente se asumen como determinísticos, pero que tienen un carácter intrínsecamente
aleatorio. Más específicamente nos interesaría saber para qué rango de los parámetros que determinan
el problema sigue siendo válida la solución encontrada.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 89 | 228
Otro aspecto interesante es el tema de dualidad. Dualidad resulta de buscar relaciones que permitan
obtener información adicional de un problema de optimización general. Esto, traducido a PL nos
conduce a relaciones primal-dual. Además veremos algunos teoremas útiles de dualidad y el concepto de
precio sombra.
Acerca de Dualidad
Todo problema de optimización (primal), tiene un problema asociado (dual) con numerosas propiedades
que los relacionan y nos permiten hacer un mejor análisis de los problemas. A continuación se describen
los resultados que se ocuparan en la resolución de los problemas.
Relaciones Primal-Dual
Estas relaciones nos permiten pasar de un problema de primal a su dual en forma bastante algorítmica,
tanto para problemas de minimización como de maximización.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 90 | 228
DUALIDAD EN PROGRAMACION LINEAL
Relaciones primal-dual
Asociado a cada problema lineal existe otro problema de programación lineal denominado problema
dual (PD) , que posee importantes propiedades y relaciones notables con respecto al
problema lineal original, problema que para diferencia del dual se denomina entonces como problema
primal (PP).
El problema dual tiene tantas variables como restricciones tiene el programa primal.
El problema dual tiene tantas restricciones como variables tiene el programa primal
Los coeficientes de la función objetivo del problema dual son los términos independientes de las
restricciones o RHS del programa primal.
Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función
objetivo del problema primal.
La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema
primal.
El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del
mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del
sentido de las restricciones del mismo problema. ( Ver tabla de TUCKER)
Si el programa primal es un problema de maximización, el programa dual es un problema de
minimización.
El problema dual de un problema dual es el programa primal original.
Tabla de TUCKER
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 91 | 228
Los problemas duales simétricos son los que se obtienen de un problema primal en forma canónica y
‘normalizada’, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los
problemas de minimización, y desigualdades menor o igual para los problemas de maximización.
Máx Z(x) = ct x
s.a:
Ax≤b
x≥0
El problema dual ( dual simétrico ) es :
Mín G(λ) = λ b
s.a:
λA≥c
λ≥0
Los restantes tipos de combinaciones de problemas, se conocen con el nombre de duales asimétricos.
Como por ejemplo:
Máx Z(x) = ct x
s.a:
Ax=b
x≥0
El problema dual ( dual asimétrico ) es :
Mín G(λ) = λ b
s.a:
λA≥c
λ >< 0, es decir, variables libres.
PREGUNTAS: RESPUESTAS:
¿Por qué se plantea el programa dual? a) Por una parte permite resolver problemas lineales
donde el número de restricciones es mayor que el
número de variables. Gracias a los teoremas que
expondremos a continuación la solución de unos de los
problemas (primal o dual) nos proporciona de forma
automática la solución del otro programa.
¿Qué significado tiene su solución? b) La dualidad permite realizar importantes
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 92 | 228
interpretaciones económicas de los problemas de
programación lineal.
¿La solución del dual se puede obtener desde el c) La dualidad permite generar métodos como el
primal? método dual del simplex de gran importancia en el
análisis de postoptimización y en la programación
lineal paramétrica.
s.a:
x1+ x2 + 2 x3 + x4 + 3 x5 ≥ 4
2 x1 - x2 + 3 x3 + x4 + x5 ≥ 3
x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x4 ≥ 0 , x5 ≥ 0
Dado que se trata de un programa lineal en forma canónica, ello nos proporciona un dual en forma
simétrica como el siguiente:
Max G(λ) = 4 λ1 + 3 λ2
s.a:
λ1 + 2 λ2 ≤ 2
λ1 - λ2 ≤ 3
2 λ1 + 3 λ2 ≤ 5
λ1 + λ2 ≤ 2
3 λ1 + λ2 ≤ 3
λ1 ≥ 0 , λ2 ≥ 0
Este problema solo tiene dos variables y cinco restricciones por tanto se pueden resolver gráficamente:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 93 | 228
Vértice solución es el punto (4/5,3/5) con un valor de la función objetivo de 5.
x1 +3x5 =4
2 x1 + x5 = 3
La solución de este sistema es : x1 = 1 y x5 = 1, lo cual nos proporciona un valor de la función objetivo de
Z(x) = 5, idéntico a la solución del dual
Máx Z(x) = ct x
s.a:
Ax≤b
x≥0
L(x,λ) = c x + λ ( b - Ax )
Donde λ = ( λ1, λ2,....,λm ) representa el vector de los multiplicadores de Lagrange asociados a las
restricciones.
∂L
=c−λ A ≤ 0
∂X
∂L
X =( c−λ A ) X=0
∂X
x≥0
∂L
λ= λ(b− AX)=0
∂λ
x≥0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 94 | 228
Asociado a este programa primal tenemos otro problema lineal denominado DUAL (posteriormente
explicaremos las relaciones entre ambos):
Mín G(λ) = λ b
s.a:
λA≥c
λ≥0
L(λ,x) = λ b + ( c - λA ) x
en donde el vector x = ( x1, x2, ..., xn ) representa los multiplicadores asociados a las restricciones del
dual.
∂L
=b− AX ≥ 0
∂λ
∂L
λ= λ(b− AX)=0
∂λ
λ≥0
∂L
=c−λ A ≤ 0
∂X
∂L
X =( c−λ A ) X=0
∂X
x≥0
Como puede observarse, ambas condiciones de optimalidad son las mismas para los dos problemas.
A la misma consideración se puede llegar sin más que comparar la función de Lagrange de los dos
problemas y ver que son iguales:
L(x,λ) = c x + λ ( b - Ax )
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 95 | 228
L(λ,x) = λ b +( c - λA )x = λ b + cx-λAx = cx + λ( b - Ax )
Por lo tanto, asociado a todo problema de programación lineal existe otro problema de programación
lineal denominado programa dual que tiene importantes relaciones con el problema original
denominado programa primal.
Como acabamos de ver, es evidente, que el programa dual de un programa dual proporciona el
programa primal original.
VARIABLES VARIABLES
∂L ∂L
=c−λ A ≤ 0 =b− AX ≥ 0
∂X ∂λ
∂L ∂L
X =( c−λ A ) X=0 λ= λ(b – AX )≥ 0
∂X ∂λ
x≥0 x≥0
MULTIPLICADORES MULTIPLICADORES
∂L ∂L
=b− AX ≥ 0 =c−λ A ≤ 0
∂λ ∂X
∂L ∂L
λ= λ(b – AX )≥ 0 X =( c−λ A ) X=0
∂λ ∂X
x≥0 x≥0
Teoremas de dualidad.
Teorema de existencia.
La condición necesaria y suficiente para que un problema de programación lineal tenga solución es que,
tanto el conjunto de oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no
sean vacíos, es decir, que ambos problemas sean factibles.
∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 96 | 228
Una vez analizadas las condiciones que han de cumplirse para que exista solución óptima, vamos a ver
los diferentes casos posibles:
Teorema de la Dualidad.
La condición necesaria y suficiente para que exista solución óptima del primal ( x* ), es que exista una
solución óptima para el dual ( λ* ) y que valor de la función objetivo de ambos programas sea igual, es
decir Z(x*) = G(λ*). ∃ x* ←→ ∃ λ* / Z(x*) = G(λ*)
La condición necesaria y suficiente para que (x*, λ*) sean soluciones óptimas del programa primal y dual,
es que satisfagan las condiciones de holgura complementaria:
( c - λ* A ) x* = 0
λ* ( b - A x* ) = 0
Relaciones entre las soluciones del programa primal y del programa dual.
Como se ha comentado con anterioridad, tanto el programa primal como el programa dual son dos
formas de abordar el mismo problema, y por lo tanto, si tienen solución, tienen la misma solución.
Entonces, cabe preguntarse cuál es la relación entre las soluciones de ambos problemas.
n
Σ (cj - a1j λ1 - a2j λ2 -.... - amj λm ) xj = 0
j=1
m
Σ λi(bi - ai1 x1 - ai2 x2 -.... - ain xn) = 0
i=1
Dado que (x*, λ*) son óptimos, debe cumplirse que cada términos del sumatorio sea cero. En particular,
y recurriendo a las variables auxiliares (de holgura) sabemos que:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 97 | 228
por tanto las relaciones anteriores equivalen a :
λjh xj = 0
xih λi = 0
En consecuencia tenemos:
1.- Si una restricción del primal es no saturada, entonces la variable de dual asociada debe ser nula.
2.- Si una variable de primal es positiva, entonces la correspondiente restricción del dual es una
restricción saturada, es decir, se verifica como una igualdad.
Tomando esto en consideración, así como los teoremas de la dualidad, podemos establecer las
siguientes relaciones entre las soluciones de primal y del dual.
1.- Por el teorema de la dualidad, y si ambos problemas tienen solución, entonces se verifica que:
Z(x*) = G(λ*)
c x* = λ* b
como
cx* = cB B-1 b
se tiene que : λ* = cB B-1
Por tanto, conociendo la solución óptima del programa primal, se puede determinar el valor de las
variables duales en su solución óptima. (Véase el ejemplo anterior, resuelto gráficamente)
En base al Teorema de holgura complementaria, existe una relación entre el comportamiento de las
variables de un problema y su dual:
xB = B-1 b = b* ≥ 0.
Además por ser óptima deberá verificar que:
wj = cj - zj ≤ 0 ∀ j.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 98 | 228
Para las variables de holgura del programa primal ( x h ), sus respectivos coeficientes en la función
objetivo son cero, y los vectores asociados a estas variables son los vectores de la base canónica, es
decir, un vector de ceros excepto en la i-esima posición que toma el valor 1.
Por tanto, los rendimientos marginales de las variables de holgura serán:
Por tanto conociendo estas relaciones podemos determinar la solución de ambos problemas de forma
inmediata.
Valor de la variables principales del dual λ* serán iguales a los rendimientos marginales de las variables
de holgura del problema primas pero cambiadas de signo. wi h = - λi .
Valor de las variables de holgura del dual λh* se corresponden con los rendimientos marginales de las
variables principales del primal.
En particular, para las variables no básicas, de las que se obtienen las variables básicas del dual se tiene:
wj = cj - zj ≤ 0 , ∀j
Conviene no perder de vista la relación entre las variables básicas de un problema con las no básicas de
su dual. Es decir, si una variable de primal es básica, la variable de dual asociada a ella será una variable
no básica, y por la misma razón si una variable de primal es no básica, la correspondiente variable de
dual será una variable básica.
Por último, aunque parezca superfluo recordarlo, el valor de la función objetivo de ambos problemas es
el mismo.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 99 | 228
Conviene notar que si establecemos las relaciones entre las tablas óptimas de los dos problemas,
veremos que el valor que aparece en las respectivas tablas optimas es el mismo pero cambiado de
signo, ello se debe a que en un problema estamos maximizando y en el otro estamos minimizando, y
para este problema de minimización realizamos la transformación de mínimo a máximo, cambiando el
signo de la función, por ello a la hora de comparar los valores de ambos problemas no se puede hacer
directamente desde una tabla a la otra.
Con el fin de comprobar las relaciones entre las soluciones de los dos problemas (primal y dual), vamos a
plantear las tablas óptimas de los problemas planteados con anterioridad.
Problema Primal:
Min Z(x) = 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5
s.a:
x1+ x2 + 2 x3 + x4 + 3 x5 ≥ 4
2 x1 - x2 + 3 x3 + x4 + x5 ≥ 3
x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x4 ≥ 0 , x5 ≥ 0
Max G(λ) = 4 λ1 + 3 λ2
s.a:
λ1 + 2 λ2 ≤ 2
λ1 - λ2 ≤ 3
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 100 | 228
2 λ1 + 3 λ2 ≤ 5
λ1 + λ2 ≤ 2
3 λ1 + λ2 ≤ 3
λ1 ≥ 0 , λ2 ≥ 0
λ1 ←→ x1h
λ2 ←→ x2h
λ1h ←→ x1
λ2h ←→ x2
λ3h ←→ x3
λ4h ←→ x4
λ5h ←→ x5
A’ = B-1 A
xB = B-1 b
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 101 | 228
Max [- Z(x)] = -2 x1 - 3 x2 - 5 x3 - 2 x4 - 3 x5
Con el objeto de no tener que realizar todas estas transformaciones en cada problema conviene tener
una serie de reglas para escribir el problema dual conociendo el primal.
1. Función objetivo:
(a) El dual de un problema de maximización es un problema de minimización.
(b) El dual de un problema de minimización es un problema de maximización.
4. Las matrices tecnológicas del primal y dual son traspuestas entre sí.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 102 | 228
A cada restricción de un problema viene asociado una variable del otro.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 103 | 228
(3.1) PROBLEMAS DE DUAL
Regla 2. Como X3 ≥ 0 en el Modelo Primal entonces habrá una restricción en el Modelo Dual del tipo ≤.
-Y2 ≤ -1
Regla 6. Como en el Modelo Primal se tiene una restricción del tipo ≥ entonces la variable Y 1 en el
Modelo Dual será del tipo ≥ 0.
Y1 ≥ 0
Regla 7. Como en el Modelo Primal se tiene una restricción del tipo = entonces la variable Y 2 en el
Modelo Dual será una variable no restringida.
Y2 No restringida
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 104 | 228
PROBLEMA 2. Obtener el Modelo Dual a partir del Modelo Primal.
Regla 2. Como en el Modelo Primal hay dos restricciones del tipo ≤ entonces en el Modelo Dual habrá
dos variables del tipo ≥0.
Y1 ≥ 0
Y2 ≥ 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 105 | 228
PROBLEMA 3. Obtener el Modelo Dual a partir del Modelo Primal.
Regla 2. Como la primera restricción en el Modelo Primal es del tipo ≤ entonces en el Modelo Dual
Y1≥0
Regla 4. Como la segunda restricción en el Modelo Primal es de igualdad, entonces en el Modelo Dual
Y2 es una variable no restringida.
Regla 3. Como la tercera restricción en el Modelo Primal es del tipo ≥, entonces en el Modelo Dual
Y3 ≤ 0.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 106 | 228
PROBLEMA 4. Obtener el Modelo Dual a partir del Modelo Primal.
Regla 5. Como en el Modelo Primal mi variable X 2 ≤ 0 por lo tanto en el Modelo Dual su primer
restricción es del tipo ≤.
Y1 - Y2 + Y3 ≤ 3
Regla 7. Como en el Modelo Primal mi variable es de no restricción, por lo tanto en el Modelo Dual su
tercera restricción es del tipo =.
Y1 =4
Regla 2. Como la primera restricción en el Modelo Primal es del tipo ≤ entonces mi variable en el Modelo
Dual es
Y1≥0
Regla 3. Como la segunda restricción en el Modelo Primal es del tipo ≥, entonces mi variable en el
Modelo Dual
Y2 ≤ 0.
Regla 4. Como la tercera restricción en el Modelo Primal es de igualdad, entonces en el Modelo Dual
Y3 es una variable no restringida.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 107 | 228
PROBLEMA 5. Obtener el Modelo Dual a partir del Modelo Primal.
Regla 7. Como en el Modelo Primal mi variable es de no restricción, por lo tanto en el Modelo Dual su
segunda restricción es del tipo =.
4Y1 - 2Y2 = 3
Regla 5. Como en el Modelo Primal mi variable X3 ≤ 0 por lo tanto en el Modelo Dual su tercer restricción
es del tipo ≤.
2Y1 -Y2 ≤ -1
Regla 4. Como mis restricciones en el Modelo Primal son del tipo ≤, entonces en el Modelo Dual mis
variables serán ≥ 0.
Y1 ≥ 0
Y2 ≥ 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 108 | 228
Problema 6
Regla 3. Como la segunda restricción en el Modelo Primal es del tipo ≥, entonces mi variable en el
Modelo Dual será ≤
Y1 + 2Y2 + 3Y3 ≤ 3
-Y1 + Y2 - Y3 ≤ 9
Regla 6. Como en el Modelo Primal se tiene restricciones de ≥ 0 por lo tanto en el Modelo Dual mis
variables serán del tipo ≥ 0.
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 109 | 228
Problema 7
Regla 2. Como la primera variable en el Modelo Primal es del tipo ≥0 entonces mi restricción en el
Modelo Dual es ≤
4Y1 + 3Y2 ≤ 2
Regla 5. Como en el Modelo Primal mi restricción es X 1 ≥ 0 por lo tanto en el Modelo Dual su primer
variable es del tipo ≤.
Y1 ≤ 0
Problema 8
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 110 | 228
Puesto que tenemos 3 restricciones en el Modelo Primal habrá 3 variables en el Modelo Dual.
Min Z= 2Y1 + 12Y2 + 12Y3
Regla 6. Como en el Modelo Primal mi variable X 1, X2 ≥ 0 por lo tanto en el Modelo Dual su restricción es
del tipo ≥ 0.
Y1 + 5Y2 + 3Y3 ≥ 5
Y2 + 3Y3 ≥ 3
Regla 2. Como la primera variable en el Modelo Primal es del tipo ≥0 entonces mi restricción en el
Modelo Dual es ≤
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
X1 X2 RHS Dual
Maximize 5 3
Constraint 1 1 0 <= 2 3,875
Constraint 2 5 2 <= 12 0
Constraint 3 3 8 <= 12 0,375
Constraint 4 1 0 >= 0 0
Constraint 5 0 1 >= 0 0
Solution-> 2 0,75 $12,25
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 111 | 228
Problema 9
Regla 2. Como la primera variable en el Modelo Primal es del tipo ≥ 0 entonces mi restricción en el
Modelo Dual es ≤
W1 + W2 + 2W3 + 3W4 ≤ 5
Regla 3. Como la tercera variable el Modelo Primal es ≤ 0, entonces mi restricción en el Modelo Dual ≥
W3 + W 4 ≥ 5
Regla 6. Como en el Modelo Primal se tiene restricciones de ≥ 0 por lo tanto en el Modelo Dual mis
variables serán del tipo ≥ 0
W1 ≥ 0
W2 ≥ 0
W3 ≥ 0
W4 ≥ 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 112 | 228
Problema 10
Regla 6. Como en el Modelo Primal mi variable X 1, X2 ≥ 0 por lo tanto en el Modelo Dual su restricción es
del tipo ≥ 0.
Y1 + Y3 ≥ 3
Y2 + Y3 -Y4≥ 2
Regla 3. Como mi restricción en el Modelo Primal es del tipo ≤, entonces mi variable en el Modelo Dual ≥
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
Y4 ≥ 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 113 | 228
CAPITULO 4 PROGRAMACION ENTERA
Programación lineal entera
Así pues decimos que un problema es de programación lineal entera, cuando prescindiendo de las
condiciones de integridad, el problema resultante es un problema de programación lineal.
Enteros puros: son aquellos en que todas las variables únicamente pueden tomar valores enteros.
también se distinguen dentro de estos los problemas totalmente enteros como aquellos en que tanto las
variables como todos los coeficientes que intervienen en el problema han de ser enteros.
Mixtos: son aquellos en los que hay al mismo tiempo variables continuas y variables que sólo pueden
tomar valores enteros.
Binarios: las variables sólo pueden tomar los valores cero o uno.
Atendiendo al criterio del tipo de problema:
Directo: Si el problema de decisión involucra variables enteras.
Codificado: Cuando se trata de un problema que contiene además de
aspectos cuantitativos, alguna consideración de tipo cualitativos, y por ello para tratar este tipo de
aspectos se requiere el uso de variable enteras o binarias.
Transformado: Cuando el problema no incluye variables enteras, pero para ser tratado analíticamente
requiere el uso de variable enteras “artificiales”.
Métodos de resolución
Aunque en un principio pueda parecer que los problemas lineales enteros son más fáciles de resolver
que los continuos, dado que el número de soluciones factibles a analizar, cuando el conjunto de
oportunidades está acotado, es finito, éste número suele ser lo suficientemente grande (en un problema
binario con n variables el número de soluciones factibles a estudiar es 2n ) como para que resulte
imposible su comparación.
Complejidad
12
242
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 114 | 228
4 16 12
5 32 16
10 1.024 992
15 32.768 31.744
20 1.048.576 1.015.808
25 33.554.432 32.505.856
50 1,1259E+15 1,1259E+15
100 1,2677E+30 1,2677E+30
200 1,6069E+60 1,6069E+60
500 3,2734E+150 3,2734E+150
1000 1,0715E+301 1,0715E+301
Así pues, la mayoría de los métodos de resolución comienzan su ejecución con la resolución del
problema lineal asociado (en adelante PLA) consistente en eliminar las condiciones de integridad,
obteniéndose en consecuencia un problema de programación lineal que puede ser resuelto mediante el
algoritmo del simplex.
La resolución del PLA en primer lugar, tiene una ventaja y es que si la solución a dicho problema verifica
las condiciones de integridad de las variables, esta será la solución al problema entero, con lo cual no
será necesario aplicar ninguna técnica especial para resolverlo.
Si la solución al PLA no verifica las condiciones de integridad , lo que ocurre la mayoría de las veces,
entonces habrá que utilizar algún método que nos permita resolver el problema entero.
Algo que no debemos hacer, es caer en la tentación de redondear la solución obtenida al PLA a valores
enteros y tomarla como válida, pues si bien esto puede ser aceptable en aquellos problemas en el que
los valores de las variables son muy grandes y en consecuencia el error puede ser mínimo, en general
nos puede generar dos graves problemas que son:
a) La solución obtenida por redondeo no es la óptima e incluso puede ser muy diferente de ella, como
ocurre con el siguiente problema
s.a.
2x1 + x2 ≤ 2
3x1 + 4x2 ≤ 6
x1 ≥ 0 , x2 ≥ 0 x1, x2 ∈{0,1}
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 115 | 228
2x1 + x2 ≤ 2
3x1 + 4x2 ≤ 6
1≥ x1 ≥ 0 , 1≥ x2 ≥ 0
se obtiene como solución
b)
Max F(X) = 8x1 + 10x2
s.a.
4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24
x1≥0,x2≥0, x1,x2∈Z+
s.a.
4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24
x1≥0,x2≥0
Unicamente se trataran los dos métodos, que consideramos más representativos y además pioneros en
la resolución de problemas enteros, como son los métodos de corte (algoritmo fraccional de Gomory) y el
de ramificación y acotación (Branch and Bound).
El método de ramificación y acotación, más conocido por su nombre en inglés Branch and Bound, recibe
su nombre precisamente por las dos técnicas en las que basa su desarrollo, que son la ramificación y la
acotación.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 116 | 228
El método de ramificación y acotación comienza por resolver el PLA, de modo que si la solución al PLA
verifica las condiciones de integridad, entonces también es la solución al problema entero, en caso
contrario se comienza con la ramificación del problema.
La ramificación consiste en dividir cada problema en dos nuevos subproblemas, obtenidos mediante la
imposición de restricciones excluyentes que dividen el conjunto de oportunidades del problema original
en dos partes, pero eliminando en ambas partes la solución no entera del problema original.
Cuando en la solución al PLA una variable que ha de ser entera xi toma el valor xbi no entero, entonces
se generan a partir de dicho valor dos restricciones xi ≤ [xbi] y xi ≥ [xbi]+1 (siendo [xbi] la parte entera
por defecto de xbi ), que añadidas cada uno por separado al problema original, da lugar a dos nuevos
subproblemas. Vamos a explicar este proceso a traves de un ejemplo particular:
s.a.
2x1 + x2 ≤ 8
x2 ≤ 5
x1,x2 ≥ 0 y enteras
la solución al PLA, prescindiendo de la condición de que las variables han de ser enteras es
x1 = 1,5, x2 =5 y F(x) = 31
como dicha solución no verifica las condiciones de integridad se elige la variable x1 que no es entera y a
partir de ella se generan dos restricciones x1 ≤ 1 y x1 ≥ 2 que añadidas cada una de ellas al problema
original dan lugar a dos nuevos subproblemas que serían los siguientes:
Subproblema 1 Subproblema 2
Max F(x) = 4x1 + 5x2 (1.1) Max F(x) = 4x1 + 5x2 (1.2)
s.a. s.a.
2x1 + x2 ≤ 8 2x1 + x2 ≤ 8
x2 ≤ 5 x2 ≤ 5
x1 ≤ 1 x1 ≥ 2
x1,x2 ≥ 0 x1,x2 ≥ 0
de este modo se han eliminado todas las posibles soluciones no enteras del conjunto de oportunidades
tales que 1< x1 < 2.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 117 | 228
El proceso se repite con cada uno de los dos subproblemas obtenidos, los cuales darán lugar a otros dos
subproblemas cada uno de ellos y así sucesivamente hasta que en todos los subproblemas tengan
solución entera o infactible.
La acotación se basa en el hecho de que dado que los conjuntos de oportunidades del subproblema 1.1.
(S11) y del subproblema 1.2 (S12) son a su vez subconjuntos del conjunto de oportunidades del
problema 1 (S1) la solución óptima de los dos subproblemas siempre será inferior (problema de máximo
o superior para problemas de mínimo) que la solución óptima del problema 1 por ser los conjuntos de
elección menores.
Así pues, el proceso de acotación consiste, para problemas de máximo, en tomar como cota inferior
aquella solución entera con mayor valor de la función objetivo obtenida y dado que cualquier otro
subproblema con solución no entera sabemos que al ramificarlo nos dará como resultado valores de la
función objetivo menores o iguales, nos permite descartar como subproblemas a ramificar todos
aquellos que tengan como solución óptima un valor de la función inferior a la cota establecida.
De este modo se reduce el número de subproblemas a ramificar y por lo tanto el tiempo necesario para
la resolución de los problemas enteros.
Ejemplo
s.a.
4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24
x1≥0,x2≥0, x1,x2∈Z+
s.a.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 118 | 228
4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24
x1≥0,x2≥0
se obtiene la solución x1 = 2, x2 = 8/3, f(x) = 128/3, dado que ésta solución no es entera se ramifica a
partir de la variable x2 del siguiente modo
Subproblema 1 Subproblema 2
Max F(X) = 8x1 + 10x2 Max F(X) = 8x1 + 10x2
s.a. s.a.
4x1 + 6x2 ≤ 24 4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24 8x1 + 3x2 ≤ 24
x2 ≥ 3 x2 ≤ 2
x1≥0,x2≥0 x1≥0,x2≥0
solución x1=1,5, x2=3,F(x)=42 solución x1=2,5, x2=2,F(x)=38
como la solución del subproblema 1, tiene el mayor valor de la función objetivo y no es entera
ramificaremos este subproblema a partir de la variable x1, del siguiente modo:
dado que de todos los subproblemas todavía no ramificados (subproblemas 2, 1.1 y 1.2) el que tiene una
mayor solución factible no entera es el subproblema 1.1, ramificaremos este subproblema a partir de la
variable x2, es decir
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 119 | 228
Dado que ya conocemos una solución entera x1=0, x2=4,F(x)=40, ésta solución actuará como cota
inferior y solamente deberán ser ramificados aquellos subproblemas con soluciones factible no enteras
que tengan un valor para la función objetivo que 40. Como el único subproblema por ramificar es el
subproblema 2 y la función objetivo vale 38, el proceso se dá por terminado, siendo por tanto la solución
óptima al problema entero
x1 = 0, x2 = 4, F(x) = 40
Metodo de Gomory
El método presentado de ramifica y acota tiene el inconveniente de que en cada paso se tiene que
resolver dos nuevos programas asociados. Esto hace que el número de operaciones sea grande, aunque
en ocasiones puede ser que uno de los dos problemas no tenga solución.
En el método que vamos a presentar a continuación se reduce el tamaño de la región factible pero sin
dividirla, para esto, se va añadiendo una restricción en cada iteración.
Estas iteraciones “cortan” la región factible, de tal manera que la nueva región debe contener la solución
entera óptima de nuestro modelo, si es que existe. El algoritmo del método se presenta a continuación.
Paso 1. Se resuelve el modelo sin tomar en cuenta la restricción de que las variables sean enteras.
Paso 2. Si la solución óptima cumple la condición de ser entera, ésta es la solución del modelo. Si no, se
toma uno de los renglones de la tabla símplex óptima con lado derecho no entero. A este renglón le
llamamos renglón fuente.
Paso 3. Escribimos los coeficientes del renglón fuente como una combinación de un número entero y
una parte fraccionaria positiva entre cero y uno.
Paso 4. Pasamos todos los coeficientes fraccionarios del lado izquierdo, los enteros los pasamos al lado
derecho. Ahora hacemos que el lado izquierdo sea mayor o igual a cero.
Paso 5. Escribimos esta desigualdad en forma de igualdad al sumar la variable de superávit y la añadimos
a nuestra tabla símplex óptima. Resolvemos por el método dual símplex. Regresamos al paso 2.
Ejemplo
Resolvemos el problema utilizando el método símplex tabular sin tomar en cuenta las restricciones de
que las variables sean enteras. La tabla óptima se presenta a continuación:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 120 | 228
Paso 1. Buscamos el primer renglón asociado a la variable básica que no cumpla con la condición de ser
entera. En este caso es el renglón asociado a la variable x1. Este renglón representa la ecuación:
Paso 3. Hacemos que el lado izquierdo de la igualdad sea mayor o igual a cero.
Aquí la variable artificial s1 se renombró como la variable x3. Resolvemos este problema por método
símplex y repetimos los pasos 1 a 3.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 121 | 228
Donde obtenemos la solución:
x1 = 8
x2 = 0
Zmáx = 16
La cual es la solución óptima entera.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 122 | 228
MAX Z=3X1+ 2X2
X1+X2 ≤5,5 (4.1) PROBLEMARIO DE PROGRAMACION LINEAL
X2 ≤3,5
Problema 1
X1,X2 Є ENTERO
X1,X2 ≥0
SOLUCIO
TABLA BASICA Z X1 X2 S1 S2 N
INICIAL Z 1 -3 -4 0 0 0
S1 0 1 1 1 0 5,5 5,5
S2 0 0 1 0 1 3,5 3,5 SALE
ENTRA
SOLUCIO
TABLA 1 BASICA Z X1 X2 S1 S2 N
Z 1 -3 0 0 4 14
S1 0 1 0 1 -1 2 2 SALE
X2 0 0 1 0 1 3,5 #¡DIV/0!
ENTRA
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 123 | 228
S1 0 1 0 1 -1 2
X2 0 0 1 0 1 3,5
SOLUCION
Z= 20
X1=2
X2=3,5
Tenemos X2 ≤ 3 y X2 ≥ 4
TABLA 1
Modelo 1 Modelo 2
Max Z=3X1+ 2x2 Max Z=3X1+ 2x2
Sujeto a: Sujeto a:
X1+X2 ≤5,5 X1+X2 ≤ 5,5
X2 ≤3,5 X2 ≤ 3,5
X2 ≤3 X2 ≥ 4
X1,X2 ≥0 X1,X2 ≥ 0
Z= 19.5 NO FACTIBLE
X1=2.5
X2=3
Tenemos X2 ≤ 3 y X2 ≥ 4
Tenemos X1 ≤ 2 y X1 ≥ 3
TABLA 1.1
Modelo 1 Modelo 2
Max Z=3X1+ 2x2 Max Z=3X1+ 2x2
Sujeto a: Sujeto a:
X1+X2 ≤ 5,5 X1+X2 ≤ 5,5
X2 ≤ 3,5 X2 ≤ 3,5
X2 ≤ 3 X2 ≥ 4
X1 ≤ 2 X1 ≥ 3
X1,X2 ≥ 0 X1,X2 ≥ 0
Z= 18 Z= 20
X1=2 X1=2
X2=3 X2=3,5
Problema 2
TABLA 1
Modelo 1 Modelo 2
Max Z=3X1+ 2x2 Max Z=3X1+ 2x2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 125 | 228
Sujeto a: Sujeto a:
X 1+ ≤2 X 1+ ≤2
X2 ≤ 2 X2 ≤ 2
X1 + X2 ≤ 3,5 X1 + X2 ≤ 3,5
X2 ≤ 1 X2 ≥ 2
X1,X2 ≥0 X1,X2 ≥0
Z=8 Z=8
X1 = 2 X1 = 2
X2 = 1,5 X2 = 1
SOLUCION
Z= 41,25
X1=3,75
X2=2,25
Problema 3
La compañía X fabrica mesas y sillas. Una mesa requiere una hora de trabajo y 9 pies de tablas de
madera y una silla requiere una hora de trabajo y 5 pies de tablas.
Actualmente la compañía dispone de seis horas de trabajo y cuarenta y cinco pies de madera. Cada mesa
contribuye con 8 dlls de la utilidad y cada silla con 5 dlls.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 126 | 228
Emule y resuelva un modelo de programación lineal entero para maximizar la utilidad.
X1,X2 Є
X1,X2 ≥0
Tenemos X1 ≤ 3 y X1 ≥ 4
TABLA 1
Modelo 1 Modelo 2
Max Z = 81+ 5x2 Max Z = 81+ 5x2
sujeto a: sujeto a:
x1+ x2 ≤ 6 x1+ x2 ≤ 6
9X1 +5X2 ≤ 45 9X1 +5X2 ≤ 45
X1 ≤ 3 X1 ≥ 4
X1,X2 ≥0 X1,X2 ≥0
Z =39 Z = 41
X1 = 3 X1 = 4
X2 = 3 X2 = 1,8
Tenemos X1 ≤ 3 y X1 ≥ 4
Tenemos X2 ≤ 1 y X2 ≥ 2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 127 | 228
TABLA 1.1
Modelo 1 Modelo 2
Max Z = 81+ 5x2 Max Z = 81+ 5x2
sujeto a: sujeto a:
x1+ x2 ≤ 6 x1+ x2 ≤ 6
9X1 +5X2 ≤ 45 9X1 +5X2 ≤ 45
X1 ≥ 4 X1 ≥ 4
X2 ≥ 1 X2 ≥ 2
X1,X2 ≥ 0
X1,X2 ≥ 0
Z =41, 44 Z = 42
X1 = 4, 55 X1 = 4
X2 = 1 X2 = 2
Tenemos X2 ≤ 2 y X2 ≤ 2
Tabla 2
Max Z = 81+ 5x2 Max Z = 81+ 5x2
sujeto a: sujeto a:
x1+ x2 ≤ 6 x1+ x2 ≤ 6
9X1 +5X2 ≤ 45 9X1 +5X2 ≤ 45
X2 ≤ 2 X2 ≥ 3
X1,X2 ≥0 X1,X2 ≥0
Z =41 Z = 39
X1 = 3,88 X1 = 3
X2 = 2 X2 = 3
Tenemos X2 ≤ 2 y X2 ≤ 2
Tenemos X1 ≤ 3 y X1 ≥ 4
TABLA 2.1
Modelo 1 Modelo 2
Max Z = 81+ 5x2 Max Z = 81+ 5x2
sujeto a: sujeto a:
x1+ x2 ≤ 6 x1+ x2 ≤ 6
9X1 +5X2 ≤ 45 9X1 +5X2 ≤ 45
X1 ≤ 3 X1 ≥ 4
X2 ≤ 2 X2 ≤ 2
X1,X2 ≥ 0 X1,X2 ≥ 0
Z = 34 Z = 42
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 128 | 228
X1 = 3 X1 = 4
X2 = 2 X2 = 2
MAX Z = 4X1+ 5X2
SUJETO A:
2X1+ X2 ≤ 8
X2 ≤ 5
X1,X2 Є
X1,X2 ≥0 SOLUCION
Z= 31
X1=1,5
X2=5
Variabl Value
e
X1 4
X2 2
Z 42
Problema 4
Tenemos X1 ≤ 1 y X1 ≥ 2
TABLA 1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 129 | 228
Modelo 1 Modelo 2
Max Z = 4X1+ 5x2 Max Z = 4X1+ 5x2
sujeto a: sujeto a:
2x1+ x2 ≤ 8 2x1+ x2 ≤ 8
X2 ≤ 5 X2 ≤ 5
X1 ≤ 1 X1 ≤ 1
X1,X2 ≥ 0 X1,X2 ≥ 0
Z = 20 Z = 28
X1 = 1 X1 = 2
X2 = 5 X2 = 4
X1,X2 ≥ 0 X1,X2 ≥ 0
Z = 42,67 Z = 40
X1 = 2 X1 = 0
X2 = 2,66 X2 = 4
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 130 | 228
Variable Value
X1 0 SOLUCION
X2 4 Z= 20,8
Solution value 40 X1=2,8
X2=1,6
Problema 6
X1,X2 Є
X1,X2 ≥0 Tenemos X1 ≤ 2 y X1 ≤ 3
TABLA 1
Modelo 1 Modelo 2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 131 | 228
Max Z = 4X1+ 6x2 Max Z = 4X1+ 6x2
sujeto a: sujeto a:
2x1+ 4x2 ≤ 12 2x1+ 4x2 ≤ 12
4x1+ 3x2 ≤ 16 4x1+ 3x2 ≤ 16
X1 ≤ 2 X1 ≤ 3
X1,X2 ≥ 0 X1,X2 ≥ 0
Z = 20 Z = 18
X1 = 2 X1 = 3
X2 = 2 X2 = 0
Tenemos X2 ≤ 1 y X2 ≤ 2
TABLA 2
Modelo 1 Modelo 2
Max Z = 4X1+ 6x2 Max Z = 4X1+ 6x2
sujeto a: sujeto a:
2x1+ 4x2 ≤ 12 2x1+ 4x2 ≤ 12
4x1+ 3x2 ≤ 16 4x1+ 3x2 ≤ 16
X2 ≤ 1 X2 ≤ 2
X1,X2 ≥ 0 X1,X2 ≥ 0
Z = 19 Z = 20
X1 = 3,25 X1 = 2
X2 = 1 X2 = 2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 132 | 228
Variable Value
X1 2
X2 2
Solution value 20
Supóngase que usted desea comprar un nuevo carro, al analizar las posibles modelos desea considerar
los siguientes atributos de cada uno:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 133 | 228
Maximizar la tasa de efectivo
En ambos ejemplos hay objetivos en conflicto y en muchas ocasiones no pueden ser logrados en forma
directa o simultánea.
La solución se encuentra en utilizar una de las técnicas de Programación por metas desarrollada por A.
Charles y W. Cooper. A fin de entender esta técnica en la tabla inferior se definen ciertos términos.
Objetivo. Refleja los deseos del tomador de decisiones (ej. Max o Min. algún criterio).
Nivel de aspiración. Es un valor específico asociado con un deseo o un nivel de logro de un objetivo.
Meta. Es un objetivo con un nivel de aspiración
Desviación de la meta. Es la diferencia entre lo que se logra y lo que se deseaba alcanzar. Pueden ser
categorizados como sub-logros o sobre-logros de las metas.
Esta técnica resuelve problemas de optimización con varios objetivos, aun y cuando éstos estén en
conflicto. Puede ser usada para toma de decisiones en distribución de recursos, planeación financiera,
distribución de presupuestos, decisiones de mercado y otras.
El algoritmo utilizado provee una alternativa donde las desviaciones de las diferentes metas se
minimizan.
Existen diversas técnicas para las medir las desviaciones de las metas y para ponderar y/o priorizar cada
una de ellas. En el presente curso estudiaremos la técnica más sencilla y la más ampliamente utilizada.
En Programación Lineal todas y cada una de las restricciones deben cumplirse, en Programación por
Metas las metas pueden o no cumplirse.
La Función Objetivo determinará aquella alternativa que primeramente satisfaga todas y cada una de las
restricciones fijas o rígidas del modelo y segundo que cumplan de mejor forma todas las metas.
Ventajas
Limitaciones:
Tanto las variables de decisión de la función objetivo como las de las restricciones deben de ser lineales
Las variables deben de ser continuas.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 134 | 228
No existe una forma sistémica para llevar a cabo el análisis de sensibilidad.
Las Variables de decisión deben ser no-negativa.
No siempre se logra satisfacer todas las metas
Variables de desviación:
Reflejan la desviación positiva o negativa del valor logrado con respecto a la meta.
Deben ser no-negativas.
Cuando el valor requerido para que la meta se cumpla es positivo se denomina desviación «faltante» (
d −¿ ¿
i )
Cuando el valor requerido para que la meta se cumpla es negativo se denomina desviación «sobrante» (
d +¿¿
i )
Existen diversas técnicas para las medir las desviaciones de las metas y para ponderar y/o priorizar cada
una de ellas. En el presente curso estudiaremos la técnica más sencilla y que es a la vez la más
ampliamente utilizada.
Los pesos se asignan de acuerdo a lo que el tomador de decisiones considere sea la penalización por la
desviación (por unidad) con respecto a la meta. Los pesos pueden indicar penalizaciones monetarias o
cualquier otra medida que se relacione a la meta. La meta más importante recibe el mayor peso.
Sea F(x) una representación matemática de un objetivo y Bi el nivel de aspiración asociado al objetivo,
entonces las metas pueden ser de tres tipos:
F(x) ≤ Bi
F(x) ≥ Bi
F(x) = Bi
Sea cual sea la forma, la transformación a programación por metas se logra añadiendo una variable de
−¿ ¿ +¿¿
desviación faltante d i y sustrayendo una variable de desviación de excedente (d i )
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 135 | 228
d ¿¿ ¿
+¿=B i¿
3. F(x) = Bi F ( X )+ d−¿−d i ¿
i
−¿ ¿ +¿¿
Al resolver el modelo, cualquier alternativa factible tiene como resultado que d i = 0 ó (d i ) = 0, o
ambas son igual a cero (0).
Aquellas restricciones rígidas, propias del sistema (que no se consideran metas) no sufren ninguna
transformación. Estas restricciones deben ser cumplidas en su totalidad para que una alternativa pueda
sean considerada factible y sea evaluada por la función objetiva.
Ejemplos.
I . Meta del tipo ≥. II. Meta del tipo
Supóngase que desea obtener una ganancia mínima Supóngase que se desea limitar los costos a un valor
determinada. determinado.
Tomemos una función de utilidad de la forma: 5*X1 + Tomemos la función de costos 100*X1 + 200*X2.
7*X2.
Si el nivel de aspiración establece que los costos no
Si el nivel de aspiración es lograr al menos ¢ 10,000, se deben sobrepasar de ¢ 5,000. Se tiene la siguiente
tiene la siguiente transformación: transformación:
La obtención de la meta se logrará en la medida que La obtención de la meta se logrará en la medida que
d −¿ ¿
1 sea pequeño. d +¿¿
1 sea pequeño.
O sea, la técnica buscará la alternativa que logre La técnica encontrará la alternativa que minimice
−¿ ¿ +¿¿
minimizar tanto el valor de d 1 como el valor global simultáneamente el valor de d 1 y el valor de la
de la Función Objetivo, y al mismo tiempo tratará de función Objetivo, y al mismo tiempo tratará que la
cumplir la meta lo más posible. meta se cumpla lo más posible.
III. Meta del tipo =. IV. Meta de intervalo.
Si se desea cumplir con una igualdad. Supóngase que se tiene un producto que tiene que ser
producido, y existe una producción mínima y otra
Supóngase se desea invertir una cantidad determinada máxima.
de recurso, con un nivel de aspiración de digamos
30,000 colones. Se realiza la siguiente transformación: Para este caso 25 X1 50. Esta meta pueden
reescribirse como:
100*X1 + 50*X2 = 30,000
+ ¿¿
−¿−d1 ¿
100*X1 + 50*X2 +d 1 = 30,000 X1 25 y X1 50
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 136 | 228
+ ¿¿
−¿−d 1 ¿
X1+ d 1 = 25 y
+ ¿¿
−¿−d 2 ¿
X1+ d 2 = 50
PROBLEMA 1
La compañía Harrison Electric, localizada en el área antigua de Chicago, fabrica dos productos que son
populares con los restauradores de casas: candelabros y ventiladores de techo de estilo antiguo. Tanto
los candelabros como los ventiladores requieren un proceso de producción de dos pasos, que implica
cableado y ensamble. Se requieren 2 horas para cablear cada candelabro y 3 para cablear un ventilador
de techo. El ensamble final de los candelabros y los ventiladores requiere de 6 y 5 horas,
respectivamente. La capacidad de producción es tal que solamente están disponibles 12 horas de
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 137 | 228
cableado y 30 horas de ensamble. Si cada candelabro producido reditúa a la empresa $7 y cada
ventilador $6, la decisión de mezcla de producción de Harrison se formula con PL, como sigue:
Modelo de PL
Maximizar lautilidad=$ 7 x 1 +$ 6 x2
Sujeta a :
2 x1 +3 x 2 ≤ 12...(horas de cableado)
6 x 1+ 5 x 2 ≤30...(horas de ensamble)
x1 , x2 ≥ 0
En este problema vemos que La gerencia de La compañía tenía un solo objetivo por ejemplo...las
utilidades.
Sin embargo suponga que la firma se va a mudar a otro lugar durante cierto período de producción y
considera que la maximización de las utilidades no es la única meta que se desea alcanzar y se extiende a
metas múltiples igualmente importantes.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 138 | 228
Meta Descripción Variables de desviación Prioridad Ecuaciones Objetivo
(restricciones)
d −¿ ¿ + ¿=30 ¿
Meta 1 Generar una utilidad de $30 si es posible 1 = Resultado por debajo de la utilidad objetivo P1 7 x 1+ 6 x 2 +d −¿−d 1 ¿
1
durante el periodo de producción. que es $30 Restricción de meta de utilidad
d +¿¿
1 = Resultado por arriba de la utilidad objetivo
−¿ ¿
d 1 = Tiempo ocioso del depto. de cableado
+¿=12¿
Meta 2 Utilizar por completo las hrs disponibles P2 2 x1 +3 x 2+ d−¿−d 1
Restricc
¿
1
en el depto. de cableado. (subutilización) ión de hrs de cableados
d +¿¿
1 = Tiempo extra del depto. de cableado
(sobreutilización)
d −¿ ¿ + ¿=30 ¿
Meta 3 Evitar el tiempo extra en el depto. de 1 = Tiempo ocioso del depto. de ensamble P3 6 x 1+ 5 x 2 +d−¿−d 1 ¿
1
ensamble. (subutilización) Restricción de hrs de ensamble
d +¿¿
1 = Tiempo extra del depto. de ensamble
(sobreutilización)
d −¿ ¿ +¿=7¿
Meta 4 Satisfacer el requisito contractual de 1 = Resultado por debajo de la meta de P4 x 2+ d−¿−d 1 ¿
Restricción de
1
fabricar por lo menos 7 ventiladores de ventiladores de techo ventiladores de techo
techo.
d +¿¿
1 = Resultado por arriba de la meta de
ventiladores de techo
7 x 1+ 6 x 2 +d −¿−d 1 ¿ Meta 1
1
+¿=12¿
2 x1 +3 x 2+ d−¿−d 1 ¿ Meta 2
1
+ ¿=30 ¿
6 x 1+ 5 x 2 +d−¿−d 1 ¿ Meta 3
1
+¿=7¿
x 2+ d−¿−d 1 ¿ Meta 4
1
+¿ ,¿
−¿ ,d ¿
4
+¿ ,d ¿
−¿ ,d 4 ¿
3
+¿ ,d ¿
3
−¿ ,d ¿
2
+ ¿,d 2 ¿
−¿ ,d1 ¿
x ,x d
Investigación
1 2, 1 de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 139 | 228
Wt(d+) Prty(d+) Wt(d-) Prty(d-) X1 X RHS
2
Goal/Cnstrnt 0 0 1 1 7 6 = 30
1
Goal/Cnstrnt 0 0 1 2 2 3 = 12
2
Goal/Cnstrnt 1 3 0 0 6 5 = 30
3
Goal/Cnstrnt 0 0 1 4 0 1 = 7
4
Item
Decision variable analysis Value
X1 0 Numero de candelabro a producir
X2 6 Numero de ventiladores a producir
Priority analysis Nonachievement
Priority 1 0
Priority 2 0
Priority 3 0
0,99999997019767
Priority 4
8
Constraint Analysis RHS d+ (row i) d- (row i)
Goal/Cnstrnt 1 30 6 0 La meta 1 se cumple totalmente y se supera en 6 unidades
Goal/Cnstrnt 2 12 6 0 La meta 2 se cumple totalmente y se supera en 6 unidades
Goal/Cnstrnt 3 30 0 0 La meta 3 se cumple totalmente
Goal/Cnstrnt 4 7 0 1 La meta 4 no se cumple por 1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 140 | 228
PROBLEMA 2
Un fabricante de Oklahoma elabora dos productos: teléfonos con altavoz(x1) y teléfonos digitales sencillos(x2).Se formulo el siguiente modelo de
programación por metas para encontrar el número de cada uno que se debe producir cada día y satisfacer así las metas de la empresa:
Sean:
x 1=nº de telefonos con altavoz producidos x 2=nº de telefonos digitales sencillos producidos
+¿ ¿
+¿ +P d ¿
−¿+ P3 d 3 4 1
¿
−¿+P2 d 2 ¿
Minimizar P1 d 1
Sujeto a: Wt(d+) Prty(d+) Wt(d-) Prty(d- X1 X RH
−¿−d 1
2 x1 + 4 x 2+ d
+¿=80¿
¿ ) 2 S
1
−¿−d2
+ ¿=320¿
¿ Goal/Cnstrnt 1 4 1 1 2 4 = 80
8 x 1+ 10 x 2 +d2 1
+ ¿=240 ¿
−¿−d3 ¿
8 x 1+ 6 x2 +d3 Goal/Cnstrnt 0 0 1 2 8 10 = 320
todas las Xi , di≥ 0 2
Goal/Cnstrnt 1 3 0 0 8 6 = 240
Item 3
Decision variable analysis Value
X1 15 Número de teléfonos con altavoz producidos
X2 20 Número de teléfonos digitales sencillos producidos
Priority analysis Nonachievement
Priority 1 0
Priority 2 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 141 | 228
Priority 3 0
Priority 4 30
Constraint Analysis RHS d+ (row i) d- (row i)
Goal/Cnstrnt 1 80 30 0 La primer meta se cumple y se excede de 30
Goal/Cnstrnt 2 320 0 0 La segunda meta se cumple totalmente
Goal/Cnstrnt 3 240 0 0 La tercera meta se cumple
PROBLEMA 3
Top Ad, una nueva agencia de publicidad con 10 empleados, firmó un contrato para promover un nuevo producto, la agencia puede hacer
publicidad por radio y televisión.
La siguiente tabla proporciona la cantidad de personas alcanzadas diariamente por cada tipo de anuncio publicitario, así como los requerimientos
de costos y mano de obra.
Radi Televisió
o n
Exposición (en millones de 4 8
personas)/min
Costo(en miles de dólares)/min 8 24
Empleados asignados /min 1 2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 142 | 228
Función Objetivo Restricciones
X 1 sea losminutos asignados a la Radio 4 x1 +8 x 2 ≤ 45
+¿¿
−¿+d 2 ¿
Minimizar la desviacion=2 d 1
X 2 sea losminutos asignados a la Television 8 x 1+ 24 x 2 ≤ 100
x1 , x2 ≥ 0
Minimizar Z =2 d−¿+d 2 ¿
1
Sujeto a:
+ ¿=45 ¿
4 x1 +8 x 2 +d−¿−d 1 ¿ Meta 1
1
+ ¿=100¿
Meta 2
8 x 1+ 24 x 2+ d−¿−d 1 ¿
1 (límite de personal)
x 1+ 2 x 2 ≤ 10 (límite de radio)
x1 ≤ 6
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 143 | 228
todas las Xi , di ≥ 0
Item
Decision variable Value
analysis
X1 5 Los minutos asignados a los anuncios de radio
X2 2,5 Los minutos asignados a los anuncios de televisión
Priority analysis Nonachievement
Priority 1 9,9999996026357
Constraint Analysis RHS d+ (row d- (row
i) i)
Goal/Cnstrnt 1 45 0 5 La meta 1 no se alcanzó por 5 millones de personas
Goal/Cnstrnt 2 100 0 0 La meta 2 se cumple totalmente
Goal/Cnstrnt 3 10 0 0
Goal/Cnstrnt 4 6 0 1 No se cumple
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 144 | 228
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 145 | 228
PROBLEMA 4
La administración de Suncoats Office Supplies establece metas, es decir cuotas mensuales para el tipo de
clientes que se contactan. La estrategia de contacto con clientes de Suncoats determina que en las cuatro
siguientes semanas, la fuerza de ventas formada por 4 personas debe efectuar 200 contactos con clientes
que hayan adquirido productos de la empresa(4), además de hacer 120 contactos con clientes
nuevos(5). La finalidad de esta ultima meta es asegurarse de que la fuerza de ventas investigue nuevas
fuentes de ventas.
Tomado en consideración tiempos de viaje y de espera, así como el tiempo directo de venta y
demostración Suncoats ha asignado 2 horas de esfuerzo de la fuerza de ventas para cada contacto con
un cliente anterior. Los contactos con nuevos clientes tienden a ser más largos y requieren de 3 horas
cada uno. Normalmente un vendedor trabaja 40 horas a la semana, es decir 160 en un horizonte de
planeación de 4 semanas; según un programa de trabajo normal, los 4 vendedores tendrán disponible (4)
(160)=640 horas de la fuerza de ventas para contactos con clientes.
La administración si fuera necesario está dispuesta a utilizar algo de tiempo extraordinario, pero también
aceptara una solución que utilice menos de las 640 horas programadas. Sin embrago la administración
desea de a lo largo de las 4 semanas , el tiempo extraordinario y la subutilización de la fuerza de trabajo se
limite a no mas de 40 horas. Así en referencia al tiempo extraordinario, la meta de la administración es
no utilizar más de 640+40=680 horas para las ventas(1); y en cuento al uso de la mano de obra, la
meta de administración es utilizar por lo menos 640-40=600 horas de la fuerza de ventas(2).
Además de las metas de contactos con los clientes, Sunncoats estableció una meta en relación con el
volumen de ventas. Con base en su experiencia Suncoats estima que cada cliente anterior contactado
generara ventas por $ 250 dólares y cada cliente nuevo generara $125 dólares de ventas. La
administración desea generar ingresos por ventas de por lo menos $70000 dólares para el mes
siguiente(3).
Dada la pequeña fuerza de ventas de Suncoaats y el breve lapso involucrado la administración decidió que
la meta de tiempo extraordinario y la meta de uso de la mano de obra sean de prioridad 1.Tambien
concluyo en que la meta de $70000 dólares debe ser de prioridad 2 y que las dos metas de contactos con
clientes deben ser de prioridad 3.
Sin embargo suponga que la administración cree que generar nuevos clientes es vital para el éxito a largo
plazo de la empresa y que la meta 5 debe tener doble peso que la 4 .
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 146 | 228
Meta Descripción Variables de desviación Prioridad Ecuaciones Objetivo (restricciones)
d −¿ ¿ +¿=680¿
Meta 1 No utilizar más de 640+40=680 horas 1 = Resultado por debajo de la meta de P1 2 x1 +3 x 2+ d−¿−d 1 ¿
1
para las ventas 600 hrs
d +¿¿
1 = Resultados por arriba de la meta de
600 hrs
d −¿ ¿ +¿=600¿
Meta 2 La meta de administración es utilizar 2 = Resultado por debajo al valor de la ,eta P1 2 x1 +3 x 2+ d−¿−d 1 ¿
1
por lo menos 640-40=600 horas de la de 600 hrs
fuerza de ventas
d +¿¿
2 = Resultado por arriba al valor de la ,eta
de 600 hrs
d −¿ ¿ + ¿=70,000¿
Meta 3 Generar ingresos por ventas de por lo 3 = Resultado por debajo al valor de la P2 250 x 1+125 x 2+ d−¿−d 1 ¿
1
menos $70000 dólares para el mes meta de $70,000 dolares
siguiente
d +¿¿
3 = Resultado por arriba al valor de la meta
de $70,000 dolares
d −¿ ¿ +¿=200¿
Meta 4 Visitar 200 contactos con clientes que 4 = Resultado por debajo al valor de la P3 x 1+ d−¿−d 1 ¿
1
hayan adquirido productos de la meta por de 200 contactos con clientes
empresa anteriores
d +¿¿
4 = Resultado por arriba al valor de la meta
por de 200 contactos con clientes anteriores
d −¿ ¿ +¿=120¿
Meta 5 Visitar 120 contactos con clientes 5 Resultado por debajo de un valor de la P3 x 2+ d−¿−d 1 ¿
1
nuevos meta de 120 contactos con clientes nuevos
d −¿ ¿
5 Resultado por arriba de un valor de la
meta de 120 contactos con clientes nuevos
2 x1 +3 x 2+ d−¿−d 1 ¿ Meta 1
1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 147 | 228
+¿=600¿
2 x1 +3 x 2+ d−¿−d 1 ¿ Meta 2
1
+ ¿=70,000¿ Meta 3
250 x 1+125 x 2+ d−¿−d 1 ¿
1 Meta 4
+¿=200¿
x 1+ d−¿−d1 ¿ Meta 5
1
+¿=120¿
−¿−d ¿
x 2+ d 1 1
todas las Xi , di ≥ 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 148 | 228
Goal/Cnstrnt 4 200 50 0 La cuarta meta se cumple y se excede
Goal/Cnstrnt 5 120 0 60 La quinta meta no se cumple
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 149 | 228
CAPITULO 6 MODELO DE TRANSPORTE Y ASIGNACION
Si observamos cualquier tipo de industria, empresa o negocio, podemos llegar a la conclusión de que en
cualquier actividad de las mencionadas se encuentra presente el transporte de bienes o productos desde
los centros de producción denominados orígenes a los centros de consumo llamados destinos: por lo que
el llevar a cabo esta actividad de manera óptima, es decir, al menor costo posible, nos representará
ventajas económicas y competitivas. El transporte de bienes o productos, materia prima, equipos, etc.,
está inmerso en la tendencia actual de la globalización, por ejemplo, los productos textiles que se
manufacturan en un país, se etiquetan en otro y tienen una distribución a nivel internacional como
productos terminados.
En la construcción de todo modelo es necesario contar con información, por esto suponemos que
conocemos los costos unitarios de transporte desde cada uno de los orígenes a cada uno de los destinos
del problema de transporte, así como la oferta y demanda de cada centro. Utilizamos el término oferta (
a ) como la cantidad de bienes o productos disponibles en cada origen, centro de producción, fábrica o
taller, es decir, del centro de producción, y el término demanda ( d ) lo asociamos con la cantidad de
bienes o productos que cada destino requiere.
Con la información anterior es evidente que las variables de decisión son la cantidad de productos que se
envían del origen i al destino j, lo cual denotamos por xij. Los costos unitarios por transportar un
producto del i-ésimo origen al j-ésimo destino se denotan como cij. Entonces, la función objetivo
asociada al problema de transporte representa el costo total de transporte.
La función objetivo se obtiene de la suma de todos los productos del costo unitario por el número de
bienes enviados desde cada origen a cada destino, es decir:
m n
Min z =∑ ∑ c ij x ij
i=1 j=1
Sujeto a
n
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 150 | 228
Para este modelo se supone que existe el equilibrio entre la oferta y la demanda, es decir, que se cumple
la igualdad:
m n
∑ ai=∑ d j
i=1 j=1
Si no se cumple esta igualdad, se anexa un origen o destino artificial, según sea el caso, donde se
producirá o recibirá, según corresponda el exceso de productos, ya sea para la oferta en el primer caso o
para la demanda en el segundo.
También está presente en este modelo la condición de no negatividad, expresada como a continuación
se presenta:
Sujeto a
n
∑ x ij =a i con i=1,2 , … … . , n
j=1
Este modelo tiene como objetivo minimizar el costo total de transportar los productos desde cada origen
a cada destino, satisfaciendo la demanda en todo momento. De manera esquemática, el problema de
transporte se puede representar como en la figura .
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 151 | 228
X11
Origen 1 Destino 1
X12
X1j
X21
X22
Origen 2 Destino 2
X2j
Xi1 Xi2
Xi3
Origen i Destino j
Algoritmo de transporte
El modelo de transporte es un caso particular de programación lineal, sin embargo, su solución por los
métodos que hasta el momento hemos estudiado, representa una gran inversión de tiempo y poder de
cómputo, motivo por lo que se han propuesto otros métodos para resolver el problema de transporte.
Estudiaremos los siguientes: Método de la esquina noroeste, Método de aproximación de Vogel y
Método de Modi, para resolver los modelos asociados al problema de transporte.
Cualquiera que sea el método por el cual se resuelva el problema de transporte, primero es necesario
construir lo que denominaremos Tabla inicial; en ésta se concentra la información de los costos unitarios
de transporte de todos los orígenes a todos los destinos, así como la oferta y la demanda de cada uno de
ellos; sobre la tabla inicial, se opera para determinar el valor de las variables de decisión.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 152 | 228
7. En la fila demanda se coloca la demanda requerida asociada al destino en cada columna.
Con estos siete pasos se obtiene la tabla inicial del problema de transporte.
EJEMPLO:
Una empresa dedicada a la importación y distribución de computadoras cuenta con socios en Inglaterra y
Alemania como países proveedores, y tres puntos de distribución, identificados como Región 1, Región 2
y Región 3. Por su parte, Inglaterra tiene disponibles 7200 computadoras, mientras que en Alemania la
existencia alcanza las 5300. Se sabe que la Región 1 requiere de 5500 computadoras, mientras que tanto
Región 2 como Región 3 necesitan 3500 computadoras cada una. Los costos de transporte unitarios
asociados desde cada origen a cada destino, se muestran en la siguiente tabla:
Se desea conocer de qué país y en qué cantidad deben enviarse las computadoras a cada Región, al menor
costo posible.
Utilizando los datos del ejemplo 1, se tiene la siguiente tabla inicial:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 153 | 228
Región 1 Región 2 Región 3 (oferta)
12 7 10
Inglaterra 7200
Alemania 8 11 9 5300
En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades
posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este
mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la
cantidad asignada a la celda.
Primera Asignación
Región 1 Región 2 Región 3 (oferta)
i-R1 (5500)(12) 12 66000 7 10
Inglaterra
I-R2 5500
(1700)(7) 1700
11900 7200
A-R2 (1800)(11) 19800
8 11 9
A-R3 (3500)(9)
Alemania 31500
1800 3500 5300
Costo de transporte $129,200
(Demanda) 5500 3500 3500 12500
Se selecciona la casilla vacía y se procede a poner sus signos empezando de más a menos. No se debe
de tener casillas vacías alrededor.
Una vez asignado los valores estos se pasan a una tabla donde se multiplican x1 positivo o negativo
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 154 | 228
Si el valor es positivo
se procede a seguir a
la siguiente casilla
vacía
Región (ofert
Región 1 Región 2
3 a)
1
12 7
Inglaterr 550 170 0
7200
a 0 men 0
más
os
8 11 9 1x8 8
180 350 (-1)x11 (-11)
Alemania Men 5300
más 0 0
os 1x7 7
(Demand (-1)x12 (-12)
5500 3500 3500 12500
a) -8
Reasignación
Región (ofert
Región 1 Región 2
3 a)
1
12 7
Inglaterr 370 350 0
7200
a 0 men 0
más
os
0+1800 1800
8 11 9
180 350 1800-1800 0
Alemania men 5300
0 más 0 1700+1800 3500
os
(Demand 5500-1800 3700
5500 3500 3500 12500
a)
Como en este caso hay una casilla vacía e una columna solo podemos brincarla en fila por
ello brincamos a I-R1 en vez de A-R3
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 157 | 228
(6.1.1) PROBLEMARIO DE ESQUINA NOROESTE
Problema 1
Con esta información queremos hallar la combinación que minimiza los costos de transporte, es decir,
debemos decidir cuántas computadoras de cada una de las plantas deben ser transportadas a cada uno
de los destinos, de tal manera que el costo total de transporte sea mínimo.
Podemos proporcionar una representación en red del problema, lo cual nos ayudaría significativamente
a comprenderlo. Colocamos dos columnas de círculos, la columna alineada a la izquierda representa
cada una de las plantas productoras (fuentes), mientras que la columna de la derecha representa cada
uno de los destinos; dentro de cada círculo se coloca la cantidad de oferta o demanda, según
corresponda. Las f lechas indican las diferentes conexiones que se pueden realizar, el costo se coloca
sobre esta f lecha. A continuación presentamos el esquema asociado con el ejemplo.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 158 | 228
Morelia Sonora Veracruz (Oferta)
50 150 80
Guadalajara 3,000
Primera Asignación
Morelia Sonora Veracruz (Oferta) G-Mo 2500*50 125000
50 150 80 G-Son 500*150 75000
Guadalajara 2,500 500 3,000 Tl- Son 2250*200 450000
Tl-Ver 1750*70 122500
60 225 200 1,75 70 Costo de transporte $772,500
Toluca 4,000
0 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 159 | 228
Reasignación
Morelia Sonora Veracruz (Oferta)
50 150 80
Guadalajara 250 2750 3,000 0+2250 2250
menos más
2250-2250 0
60 200 70
Toluca 2250 1,750 4,000 2250+500 2750
más menos
2500-2250 250
(Demanda) 2,500 2,750 1,750 7,000
Problema 2
Una empresa dispone de tres fábricas que producen el mismo bien. Las cantidades disponibles de ese
bien en cada fábrica es de 25, 35 y 30 unidades, respectivamente. La empresa debe proveer a cuatro
tiendas que demandan 10, 18, 20 y 42 unidades del producto, respectivamente. Los costes unitarios de
transporte del bien vienen dados por la siguiente tabla:
D1 D2 D3 D4
E1 3 2 5 4 25
E2 4 1 7 6 35
E3 7 8 3 5 30
10 18 20 42 90
Se desea determinar cómo han de realizarse los envíos a las tiendas de manera que se minimice el costo
total de transporte.
D1 D2 D3 D4 (Oferta)
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 160 | 228
3 2 5 4
E1 25
4 1 7 6
E2 35
7 8 3 5
E3 30
(Demanda) 10 18 20 42 90
E1 3 2 5 4
25
10 15
E2 4 1 7 6
35
3 20 12
7 8 3 5
E3 30
30
(Demanda) 10 18 20 42 90
Se hace el cálculo del costo de transporte
E1D1 (10)(3) 30
E1D2 (15)(2) 30
E2D2 (3)(1) 3
E2D3 (20)(7) 140
E2D4 (12)(6) 72
E3D4 (30)(5) 15
COSTO TOTAL DE TRANSPORTE $425
E1 3 (-) 2 (+) 5 4
25
10 15
E2 4 (+) 1 (-) 7 6
35
3 20 12
7 8 3 5
E3 30
30
(Demanda) 10 18 20 42 90
(1)(5) 5
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 161 | 228
(-1)(7) -7
(1)(1) 1
(-1)(2) -2
-3
Se hace un circuito en la celda no básica E1D4.
D1 D2 D3 D4 Oferta
E1 3 (-) 2 5 (+) 4
25
10 15
E2 4 (+) 1 7 (-) 6
35
3 20 12
7 8 3 5
E3 30
30
(Demanda) 10 18 20 42 90
(1)(4) 4
(-1)(6) -6
(1)(1) 1
(-1)(2) -2
-3
E1 (-) 3 (+) 2 5 4
25
10 15
E2 4 (-) 1 7 6
35
(+) 3 20 12
7 8 3 5
E3 30
30
(Demanda) 10 18 20 42 90
(1)(4) 4
(-1)(3) -3
(1)(2) 2
(-1)(1) -1
2
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 162 | 228
E1 (-) 3 (+) 2 5 4
25
10 15
E2 4 (-) 1 7 (+) 6
35
3 20 12
7 8 3 (-) 5
E3 (+) 30
30
(Demanda) 10 18 20 42 90
(1)(7) 7
(-1)(3) -3
(1)(2) 2
(-1)(1) -1
(1)(6) 6
(-1)(5) -5
6
E1 3 2 5 4
25
10 15
E2 4 (-) 1 7 (+) 6
35
3 20 12
7 8 3 (-) 5
E3 (+) 30
30
(Demanda) 10 18 20 42 90
(1)(8) 8
(-1)(1) -1
(1)(6) 6
(-1)(5) -5
8
E1 3 2 5 4
25
10 15
E2 4 1 (-) 7 (+) 6 35
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 163 | 228
3 20 12
7 8 3 (-) 5
E3 (+) 30
30
(Demanda) 10 18 20 42 90
(1)(3) 3
(-1)(7) -7
(1)(6) 6
(-1)(5) -5
-3
Como el resultado es negativo quiere decir que no hay una solución óptima, por lo tanto tenemos que
hacer una reasignación en la celda no básica E3D3.
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 1 (-) 7 (+) 6
35
3 20 12
7 8 3 (-) 5
E3 (+) 30
30
(Demanda) 10 18 20 42 90
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 1 7 6
35
3 32
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 164 | 228
E1D1 (10)(3) 30
E1D2 (15)(2) 30
E2D2 (3)(1) 3
E2D4 (32)(6) 192
E3D3 (20)(3) 60
E3D4 (10)(5) 50
COSTO TOTAL DE TRANSPORTE $365
E1 3 (-) 2 5 4
25
10 15 (+)
E2 4 (+) 1 7 (-) 6
35
3 32
7 8 (-) 3 (+) 5
E3 30
20 10
(Demanda) 10 18 20 42 90
(1)(5) 5
(-1)(2) -2
(1)(1) 1
(-1)(6) -6
(1)(5) 5
(-1)(3) -3
0
D1 D2 D3 D4 Oferta
E1 3 (-) 2 5 4
25
10 15 (+)
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 165 | 228
E2 4 (+) 1 7 (-) 6
35
3 32
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
(1)(4) 4
(-1)(2) -2
(1)(1) 1
(-1)(6) -6
-3
D1 D2 D3 D4 Oferta
E1 (-) 3 (+) 2 5 4
25
10 15
E2 4 (-) 1 7 6
35
(+) 3 32
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
(1)(7) 7
(-1)(3) -3
(1)(2) 2
(-1)(1) -1
2
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 1 7 (-) 6
35
3 (+) 32
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 166 | 228
7 8 (-) 3 (+) 5
E3 30
20 10
(Demanda) 10 18 20 42 90
(1)(7) 7
(-1)(6) -6
(1)(5) 5
(-1)(3) -3
3
D1 D2 D3 D4 Oferta
E1 (-) 3 (+) 2 5 4
25
10 15
E2 4 (-) 1 7 (+) 6
35
3 32
7 8 3 (-) 5
E3 (+) 20 30
10
(Demanda) 10 18 20 42 90
(1)(7) 7
(-1)(3) -3
(1)(2) 2
(-1)(1) -1
(1)(6) 6
(-1)(5) -5
6
Se hace un circuito en la celda no básica E3D2.
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 (-) 1 7 (+) 6
35
3 32
7 8 3 (-) 5
E3 (+) 20 30
10
(Demanda) 10 18 20 42 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 167 | 228
(1)(8) 8
(-1)(1) -1
(1)(6) 6
(-1)(5) -5
8
Como el resultado es negativo quiere decir que no hay una solución óptima, por lo tanto tenemos que
hacer una reasignación en la celda no básica E1D4.
D1 D2 D3 D4 Oferta
E1 3 (-) 2 5 (+) 4
25
10 15
E2 4 (+) 1 7 (-) 6
35
3 32
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 1 7 6
35
18 17
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 168 | 228
E1D4 (15)(4) 60
E2D2 (18)(1) 18
E2D4 (17)(6) 102
E3D3 (20)(3) 60
E3D4 (10)(5) 50
COSTO TOTAL DE TRANSPORTE $320
Se hace un circuito en la celda no básica E1D2.
D1 D2 D3 D4 Oferta
E1 3 2 5 (-) 4
25
10 (+) 15
E2 4 (-) 1 7 (+) 6
35
18 17
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
(1)(2) 2
(-1)(4) -4
(1)(6) 6
(-1)(1) -1
3
D1 D2 D3 D4 Oferta
E1 3 2 (+) 5 (-) 4
25
10 15
E2 4 1 7 6
35
18 17
7 8 (-) 3 (+) 5
E3 30
20 10
(Demanda) 10 18 20 42 90
(1)(5) 5
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 169 | 228
(-1)(4) -4
(1)(5) 5
(-1)(3) -3
3
E1 (-) 3 2 5 (+) 4
25
10 15
E2 4 1 7 (-) 6
35
(+) 18 17
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
(1)(4) 4
(-1)(3) -3
(1)(4) 4
(-1)(6) -6
-1
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 1 7 (-) 6
35
18 (+) 17
7 8 (-) 3 (+) 5
E3 30
20 10
(Demanda) 10 18 20 42 90
(1)(7) 7
(-1)(6) -6
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 170 | 228
(1)(5) 5
(-1)(3) -3
3
E1 (-) 3 2 5 (+) 4
25
10 15
E2 4 1 7 6
35
18 17
7 8 3 (-) 5
E3 (+) 20 30
10
(Demanda) 10 18 20 42 90
(1)(7) 7
(-1)(3) -3
(1)(4) 4
(-1)(5) -5
3
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
10 15
E2 4 (-) 1 7 (+) 6
35
18 17
7 8 3 (-) 5
E3 (+) 20 30
10
(Demanda) 10 18 20 42 90
(1)(8) 8
(-1)(1) -1
(1)(6) 6
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 171 | 228
(-1)(5) -5
8
Como el resultado es negativo quiere decir que no hay una solución óptima, por lo tanto tenemos que
hacer una reasignación en la celda no básica E2D1.
D1 D2 D3 D4 Oferta
E1 (-) 3 2 5 (+) 4
25
10 15
E2 4 1 7 (-) 6
35
(+) 18 17
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
25
E2 4 1 7 6
35
10 18 7
7 8 3 5
E3 20 30
10
(Demanda) 10 18 20 42 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 172 | 228
E2D4 (7)(6) 42
E3D3 (20)(3) 60
E3D4 (10)(5) 50
COSTO TOTAL DE TRANSPORTE $310
Como en el cálculo de las celdas no básicas son positivas por lo tanto se ha encontrado la solución óptima
para este problema.
Problema 3
Una empresa produce un único artículo en tres plantas, A1, A2 y A3. La capacidad de producción
mensual de la empresa esta limitada a 1500 unidades mensuales en cada una de las plantas. La empresa
tiene cuatro clientes mayoristas cuyas demandas mensuales son 1000, 1200, 1500 y 1000 unidades
respectivamente.
El beneficio unitario que le proporciona su producto, considerados los costes de producción y el precio
de venta, es de 110 unidades. Los costos de envío a los 4 clientes mayoristas que la empresa tiene vienen
dados por la siguiente tabla.
1 2 3 4
A1 30 10 25 20
A2 15 25 30 10
A3 20 30 15 20
El objetivo de la empresa es organizar la producción en cada uno de los meses para obtener el máximo
beneficio.
Problema 4
Sarah Mahan presidente de Mahan Concrete Company tienen plantas en tres localizaciones y está
actualmente trabajando en tres grandes proyectos de construcción, ubicados en diferentes sitios.
El costo del embarque por cada carga de camión de concreto, capacidades de planta y requerimientos de
proyecto se muestran a continuación:
Formule una solución inicial factible para el problema de transportación de Mahan utilizando la regla de
la esquina Noroeste.
Luego evalué cada ruta de embarque no utilizada (cada celda vacía) al aplicar el método del escalón y
calcule todos los índices de mejoramiento
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 173 | 228
Revise que exista el número adecuado de celdas ocupadas para una solución normal
Primera asignación
Cantidad de
Desde HACIA
la fabrica
Proyecto A Proyecto B Proyecto C
$1
40 30 $4 $11 70
Planta 1 0
$1
$5 $8 50
Planta 2 2
20 30
$9 $7 30 $6 30
Planta 3
Requerimientos del
40 50 60 150
proyecto
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 174 | 228
P2-PC (30)(8) 240
P3-PC (30)(6) 180
Costo de transporte $1,040
Cantidad de
Desde HACIA
la fabrica
Proyecto A Proyecto B Proyecto C
$1
40 30 $4 $11 70
Planta 1 0
menos mas
$1
$5 $8 50
Planta 2 2
20 mas 30 menos
$9 $7 30 $6 30
Planta 3
Requerimientos del
40 50 60 150
proyecto
1x11 11
(-1)x4 (-4)
1x5 5
(-1)x8 (-8)
4
Cantidad de
Desde HACIA
la fabrica
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 175 | 228
0
menos mas
$1
$5 $8 50
Planta 2 2
mas 20 menos 30
$9 $7 30 $6 30
Planta 3
Requerimientos del
40 50 60 150
proyecto
1x12 12
(-1)x5 (-5)
1x4 4
(-1)x10 (-10)
1
Cantidad de
Desde HACIA
la fabrica
Proyecto A Proyecto B Proyecto C
$1
40 30 $4 $11 70
Planta 1 0
$1
$5 $8 50
Planta 2 2
20 menos 30 mas
$9 $7 30 $6 30
Planta 3
mas menos
Requerimientos del
40 50 60 150
proyecto
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 176 | 228
1x7 7
(-1)x6 (-6)
1x8 8
(-1)x5 (-5)
4
Como en la primera asignación nos salen índices positivos hemos llegado a la solución óptima.
(6.2) VOGEL
Método de Vogel
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 177 | 228
a. La penalidad es el valor absoluto de la diferencia de los dos costos menores por cada fila
y cada columna.
4. Seleccionar la penalidad mayor de todas las calculadas y ubicar la celda con el menor costo de la
fila o columna de la penalidad seleccionada (los empates entre penalidades de mayor valor se
rompen arbitrariamente). En la celda de menor costo ubicada, asignar tantas unidades como sea
posible y ajustar la oferta y demanda correspondientes.
5. Cancelar la fila o columna que se haya satisfecho. Si sólo queda una fila o columna sin asignación,
distribuir las cantidades restantes de la oferta en las celdas disponibles. En caso contrario, volver
al paso 3.
6. Toda vez concluida la asignación de todas las unidades disponibles, calcular el costo del modelo
de transporte e interpretar la solución.
7. Calcular los costos marginales de las celdas no básicas. Si se tienen costos marginales mayores o
iguales a cero, la solución es óptima. En otro caso, se requiere ajustar la asignación con otra
tabla.
EJEMPLO:
Una empresa dedicada a la importación y distribución de computadoras cuenta con socios en Inglaterra y
Alemania como países proveedores, y tres puntos de distribución, identificados como Región 1, Región 2
y Región 3. Por su parte, Inglaterra tiene disponibles 7200 computadoras, mientras que en Alemania la
existencia alcanza las 5300. Se sabe que la Región 1 requiere de 5500 computadoras, mientras que tanto
Región 2 como Región 3 necesitan 3500 computadoras cada una. Los costos de transporte unitarios
asociados desde cada origen a cada destino, se muestran en la siguiente tabla:
Se desea conocer de qué país y en qué cantidad deben enviarse las computadoras a cada Región, al menor
costo posible.
Utilizando los datos del ejemplo 1, se tiene la siguiente tabla inicial:
8 11 9
Alemania 5300
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 178 | 228
Región
Región 1 Región 2 (oferta) Penalidad
3
12 7 10 Se selecciona los
Inglaterra 7200 10-7=3
dos menores
8 11 9 valores tanto en la
Alemania 5300 9-8=1
fila como en la
(Demanda columna y se restan
5500 3500 3500 12500
)
Región (oferta
Región 2 Región 3 Penalidad
1 )
12 7 10 Se selecciona la
Inglaterra 7200 10-7=3
penalidad más
8 11 9 alta, si hay
Alemania 5300 9-8=1
empate se
analizan los
(Demanda) 5500 3500 3500 12500
costos de menor
Penalidad 12-8=4 11-7=4 10-9=1 número.
Región (oferta
Región 2 Región 3 Penalidad Asignamos al
1 )
12 7 10
costo mínimo en
Inglaterra 3500 7200 10-7=3 este caso 7. Se
asigna la
8 11 9
Alemania 5300 9-8=1 cantidad siempre
y cuando no se
5500 3500 3500 12500 salga de la oferta
(Demanda)
Penalidad 12-8=4 11-7=4 10-9=1
Región
Región 1 Región 2 (oferta) Penalidad
3
12 7 10
Inglaterra 3500 7200 12-10=2
8 11 9
Alemania 5300 9-8=1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 179 | 228
Se toman
nuevas
penalidades
ignorando los
valores de lo
que ya se
seleccionó.
Región
Región 1 Región 2 (oferta) Penalidad
3
12 7 10
Inglaterra 3500 7200 12-10=2
8 11 9
Alemania 5300 9-8=1
Región
Región 1 Región 2 (oferta) Penalidad
3 Se asigna al
12 7 10 costo mínimo la
Inglaterra 200 3500 7200 12-10=2
mayor cantidad
530 8 11 9 siempre y
Alemania 5300 9-8=1
0 cuando no
sobrepase la
5500 3500 3500 12500
(Demanda) oferta.
Penalidad 12-8=4 10-9=1
12 7 350 10
Inglaterra 200 3500 7200 12-10=2
0
530 8 11 9
Alemania 5300 9-8=1
0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 180 | 228
Se asigna el
costo
mínimo a la
columna
vacía.
(6.2.1) PROBLEMARIO
Problema 1
La siguiente tabla indica el número de El ingeniero del área de entrega estima que los costos
computadoras requeridas y el lugar donde de transporte
deben ser entregadas. por unidad de cada una de las plantas a cada uno de
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 181 | 228
los destinos es el siguiente:
Ciudad Cantidad Morelia Sonora Veracruz
Morelia 2500 Guadalajara $50 $150 $80
Sonora 2750 Toluca $60 $200 $70
Veracruz 1750
Con esta información queremos hallar la combinación que minimiza los costos de transporte, es decir,
debemos decidir cuántas computadoras de cada una de las plantas deben ser transportadas a cada uno
de los destinos, de tal manera que el costo total de transporte sea mínimo.
Podemos proporcionar una representación en red del problema, lo cual nos ayudaría significativamente
a comprenderlo. Colocamos dos columnas de círculos, la columna alineada a la izquierda representa
cada una de las plantas productoras (fuentes), mientras que la columna de la derecha representa cada
uno de los destinos; dentro de cada círculo se coloca la cantidad de oferta o demanda, según
corresponda. Las f lechas indican las diferentes conexiones que se pueden realizar, el costo se coloca
sobre esta f lecha. A continuación presentamos el esquema asociado con el ejemplo.
60 200 70
Toluca 4,000
(Oferta Penalidad
Morelia Sonora Veracruz
)
Guadalajar 50 2750 150 80 3,000 80-50=30
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 182 | 228
a
60 200 70
Toluca 4,000 70-60=10
7
60 200
Toluca 2,250 1,750 0 4,000
Penalidad
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 183 | 228
Guadalajara 250 2750
Toluca 2250 1750
Problema 2
Una empresa dispone de tres fábricas que producen el mismo bien. Las cantidades disponibles de ese
bien en cada fábrica es de 25, 35 y 30 unidades, respectivamente. La empresa debe proveer a cuatro
tiendas que demandan 10, 18, 20 y 42 unidades del producto, respectivamente. Los costes unitarios de
transporte del bien vienen dados por la siguiente tabla:
D1 D2 D3 D4
E1 3 2 5 4 25
E2 4 1 7 6 35
E3 7 8 3 5 30
10 18 20 42 90
Se desea determinar cómo han de realizarse los envíos a las tiendas de manera que se minimice el costo
total de transporte.
D1 D2 D3 D4 (Oferta) Penalidad
3 2 5 4
E1 25 1
4 1 7 6
E2 35 3
7 8 3 5
E3 20 30 2
(Demanda) 10 18 42 90
Penalidad 1 1 1
D1 D2 D3 D4 (Oferta) Penalidad
3 2 5 4
E1 25 1
4 1 7 6
E2 18 25 3
7 8 3 5
E3 20 10 2
(Demanda) 10 42 90
Penalidad 1 1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 184 | 228
D1 D2 D3 D4 (Oferta) Penalidad
3 2 5 4
E1 25 25 1
4 1 7 6
E2 10 18 7 7 2
7 8 3 5
E3 20 10 10 2
(Demanda) 42 90
Penalidad 1
Problema 3
Sarah Mahan presidente de Mahan Concrete Company tienen plantas en tres localizaciones y está
actualmente trabajando en tres grandes proyectos de construcción, ubicados en diferentes sitios.
El costo del embarque por cada carga de camión de concreto, capacidades de planta y requerimientos de
proyecto se muestran a continuación:
Formule una solución inicial factible para el problema de transportación de Mahan utilizando la regla de
la esquina Noroeste.
Luego evalué cada ruta de embarque no utilizada (cada celda vacía) al aplicar el método del escalón y
calcule todos los índices de mejoramiento
Revise que exista el número adecuado de celdas ocupadas para una solución normal
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 185 | 228
Requerimientos del proyecto 40 50 60 150
Proyecto Penalidad
Proyecto A Proyecto B (Oferta)
C
$10 5 $4 $11
Planta 1 20
0
$12 $5 $8
Planta 2 50 3
$9 $7 $6
Planta 3 30 1
(Demanda
20 60 150
)
Penalidad 1 1 2
$12 $5 $8
Planta 2 50 3
$9 $7 $6
Planta 3 20 10 1
(Demanda
60 150
)
Penalidad 1 2
$12 $5 5 $8
Planta 2
0
$9 $7 $6
Planta 3 20 10 1
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 186 | 228
(Demanda
10 150
)
Penalidad 1 2
$12 $5 5 $8
Planta 2
0
$9 $7 1 $6
Planta 3 20 1
0
(Demanda
150
)
Penalidad
Problema 4
$8 $5 $6 120
Fabrica A
Fabrica B $15 $10 $14 80
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 187 | 228
$3 $9 $10 80
Fabrica C
Requerimientos de
150 80 50 280
almacén
Almacén
Almacén 1 Almacén 2 (Oferta) Penalidad
3
$8 $5 $6 120 1
Fabrica A
80 $3 $9 $10
Fabrica C
(Demanda
150 80 50 280
)
Penalidad 5 4 4
(Oferta
Almacén 1 Almacén 2 Almacén 3 Penalidad
)
$8 $5 50 $6 70 1
Fabrica A
80 $3 $9 $10
Fabrica C
(Demanda
70 80 280
)
Penalidad 7 5
(Oferta
Almacén 1 Almacén 2 Almacén 3 Penalidad
)
70 $8 $5 50 $6
Fabrica A
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 188 | 228
80 $3 $9 $10
Fabrica C
(Demanda
80 280
)
Penalidad 5
80 $3 $9 $10
Fabrica C
(Demanda
280
)
(6.3) MODI
El Método de Modi nos ofrece la oportunidad de calcular costos marginales basados en los valores de las
variables de decisión del modelo, pero aunado a esto también nos indica la celda no básica en la cual se
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 189 | 228
deben realizar los ajustes para obtener una mejor solución. Es por esta razón que después de presentar
los métodos de la esquina noroeste y de Vogel, cerramos este capítulo con el Método de Modi.
Método de Modi
A partir de una tabla inicial con la primera solución factible calculada por cualquier método (esquina
noroeste o Vogel):
Paso 1.
Paso 2.
o Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor negativo.
o Crear un circuito con todos los vértices en celdas de variables básicas.
o Es decir, encontrar la trayectoria de la variable “no básica” que entrará a la solución.
Paso 3.
o Ajustar el valor de xij en las celdas del circuito, comenzando por sumar la variable θ a la celda
seleccionada en el Paso 2, en el sentido de las manecillas del reloj, y alternando una resta y suma
de θ en cada celda de la trayectoria hasta regresar a la celda primera, resolver una desigualdad
(x ≥ 0) para θ y ajustar la solución.
o En todo caso volver al Paso 1.
EJEMPLO:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 190 | 228
Una empresa dedicada a la importación y distribución de computadoras cuenta con socios en Inglaterra
y Alemania como países proveedores, y tres puntos de distribución, identificados como Región 1, Región
2 y Región 3. Por su parte, Inglaterra tiene disponibles 7200 computadoras, mientras que en Alemania la
existencia alcanza las 5300. Se sabe que la Región 1 requiere de 5500 computadoras, mientras que tanto
Región 2 como Región 3 necesitan 3500 computadoras cada una. Los costos de transporte unitarios
asociados desde cada origen a cada destino, se muestran en la siguiente tabla:
Se desea conocer de qué país y en qué cantidad deben enviarse las computadoras a cada Región, al
menor costo posible.
Utilizando los datos del ejemplo 1, se tiene la siguiente tabla inicial:
8 11 9 La solución inicial
Alemania 5300 obtenida al problema de
las computadoras con el
(Demanda) 5500 3500 3500 12500 método de la esquina
Noroeste se muestra en
la siguiente tabla
Primera Asignación
Región 1 Región 2 Región 3 (oferta) I-R1 (5500)(12) 66000
12 7 10 I-R2 (1700)(7) 11900
Inglaterra 5500 1700 7200 A-R1 (1800)(11) 19800
8 11 9 A-R2 (3500)(9) 31500
Alemania 1800 3500 5300 Costo de $129,200
transporte
(Demanda) 5500 3500 3500 12500
Para determinar si es óptima esta solución inicial, o bien para hacerla óptima se aplicara el
método MODI.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 191 | 228
Los multiplicadores (ui vj) Los costos marginales estas Utilizando el valor calculado de
Resolviendo el
esta asociados a todas las Se obtiene asociados a toda celda no los multiplicadores encontraos los
sistema suponiendo
celdas básicas y su expresión el sistema básica (no llena en la primera costos marginales de la primera
es;
ui = 0
asignación) con la expresión solución factible
Celda (i,j) ui + vi = cij u1 = 0
u1 + v1 = 12
Celda (i,j) u1 + v1 = c11 Celda (i,j): c.m. = Cij – ui – Vj
u1 + v2 = 7
Celda (i,j) u1 + v2 = c12 0 + v1 = 12 Celda (1,3): c.m. = C13 – u1 – V3 Celda (1,3): c.m. = 10 – 0 – 5 = 5
u2 + v2 = 11
Celda (i,j) u2 + v2 = c22 0 + v2 = 7 Celda (2,1): c.m. = C21 – u2 – V1 Celda (2,1): c.m. = 8 – 4 -12 = -8
u2 + v3 = 9
Celda (i,j) u2 + v3 = c23 u2 + 7 = 11…. u2 = 4
4 + v3 = 9……. v3 = 5
Pasó 2: Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor negativo y crear un circuito con todos los vértices en celdas de
variables básicas, el más simple posible, es decir, encontrar la trayectoria de la variable “no básica” que entrara a ala solución.
Para este caso la más negativa es la Celda (2,1), por lo que el circuito es:
Primera Asignación
Región 1 Región 2 Región 3 (oferta)
5500 12 1700 7 10
Inglaterra 7200
8 11 9
Alemania 1800 3500 5300
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 192 | 228
Paso 3: Ajustar el valor de xij en las celdas del circuito, comenzando por sumar la variable θ a la celda seleccionada en el Paso 2, en el sentido
de las manecillas del reloj, y alternar una resta y suma de θ en cada celda de la trayectoria hasta regresar a la celda primera. Resolver para θ y
ajustar la solución. En todo caso volver al Paso 1.
Ahora se plantea el
sistema de
Primera asignación desigualdades para Segunda asignación
obtener el valor de θ
y ajustar los valores:
Región 1 Región 2 Región 3 (oferta) Región 1 Región 2 Región 3 (oferta)
12 7 10 θ≥0 12 7 10
Inglaterra 5500- 1700+ 7200 Inglaterra 3700 3500 7200
5500−θ≥ 0
8 11 9 8 11 9
Alemania 1800- 3500 5300 1700+θ ≥ 0 Alemania 3500 5300
1800−θ≥ 0
(Demanda) 5500 3500 3500 12500 (Demanda) 5500 3500 3500 12500
El valor máximo
posible de θ que
resuelve el sistema es:
θ = 1800
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 193 | 228
Para determinar si es óptima esta solución inicial, o bien para hacerla óptima, se aplicará el Método de Modi:
Paso 2. Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor negativo. Crear un circuito con todos los vértices en celdas de
variables básicas (el más simple posible). Es decir, encontrar la trayectoria de la variable “no básica” que entrará a la solución.
Para este caso la celda con mayor valor negativo es C(1,3), por lo que el circuito es
Ahora se plantea el
sistema de
desigualdades para
Tercera asignación
Segunda asignación obtener el valor de
θ y ajustar los
valores:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 195 | 228
Optimal cost = $104.300 Región 1 Región 2 Región 3
I-R2 (3500)(7) 24500
Inglaterra 200 3500 3500
I-R3 (3500(10) 35000
Alemania 5300
A-R1 (5300)(8) 42400
Costo de transporte $104,300
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 196 | 228
(6.3.1) PROBLEMARIO DE MODI
Problema 1
Con esta información queremos hallar la combinación que minimiza los costos de transporte, es decir,
debemos decidir cuántas computadoras de cada una de las plantas deben ser transportadas a cada uno
de los destinos, de tal manera que el costo total de transporte sea mínimo.
Podemos proporcionar una representación en red del problema, lo cual nos ayudaría significativamente
a comprenderlo. Colocamos dos columnas de círculos, la columna alineada a la izquierda representa
cada una de las plantas productoras (fuentes), mientras que la columna de la derecha representa cada
uno de los destinos; dentro de cada círculo se coloca la cantidad de oferta o demanda, según
corresponda. Las f lechas indican las diferentes conexiones que se pueden realizar, el costo se coloca
sobre esta f lecha. A continuación presentamos el esquema asociado con el ejemplo.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 197 | 228
Para determinar su es óptima esta solución inicial o bien para hacerla optima, se aplicara el Método Modi.
Paso 1: Calcular los multiplicadores (ui y vj) y los costos marginales (c.m.).
Los multiplicadores (ui y vj) están Se obtiene el sistema: Resolviendo el sistema, Los costos marginales están Utilizando el valor calculado de los
asociados a toda celda básica y su suponiendo u1=0 asociados a toda celda no básica multiplicadores, encontramos los
expresión es: (No llena en la asignación) con la costos marginales de la primera
expresión: solución factible:
Paso 2: Si existe por lo menos un costo marginal negativo tomar la celda con mayor valor negativo. Crear un circuito con todos los vértices en
celdas de variables básicas (el más simple posible). Es decir, encontrar la trayectoria de la variable “No básica” que entrara a la solución.
E1 3 (- θ) 2 5 (+θ) 4
25
10 15
E2 4 (+θ) 1 7 (-θ) 6
35
3 20 12
7 8 3 5
E3 30
30
(Demanda) 10 18 20 42 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 198 | 228
Paso 3: Ajustar el valor de xij en las celdas del circuito, comenzando por sumar la variable θ a la celda seleccionada en el Paso 2, en el sentido de
las manecillas del reloj, y alternar una resta y suma de θ en cada celda de la trayectoria hasta regresar a la celda primera. Resolver para θ y ajustar
la solución. En todo caso volver al Paso 1.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 199 | 228
Los multiplicadores (ui y vj) están Se obtiene el sistema: Resolviendo el sistema, Los costos marginales están Utilizando el valor calculado de los
asociados a toda celda básica y su suponiendo u1=0 asociados a toda celda no básica multiplicadores, encontramos los
expresión es: (No llena en la asignación) con la costos marginales de la primera
expresión: solución factible:
Paso 2: Si existe por lo menos un costo marginal negativo tomar la celda con mayor valor negativo. Crear un circuito con todos los vértices en
celdas de variables básicas (el más simple posible). Es decir, encontrar la trayectoria de la variable “No básica” que entrara a la solución. Para este
caso la celda (3,3) por lo que el circuito es:
D1 D2 D3 D4 Oferta
E1 3 (- θ) 2 5 (+θ) 4
3 12 25
10
E2 4 (+θ) 1 (- θ) 7 6
15 35
20
7 8 (+ θ) 3 (-θ) 5
E3 30 30
(Demanda) 10 18 20 42 90
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 200 | 228
Paso 3: Ajustar el valor de xij en las celdas del circuito, comenzando por sumar la variable θ a la celda seleccionada en el Paso 2, en el sentido de
las manecillas del reloj, y alternar una resta y suma de θ en cada celda de la trayectoria hasta regresar a la celda primera. Resolver para θ y ajustar
la solución. En todo caso volver al Paso 1.
Primera asignación Ahora se plantea el segunda asignación
sistema de
desigualdades para
obtener el valor de θ y
ajustar los valores:
D1 D2 D3 D4 Oferta D1 D2 D3 D4 Oferta
E1 3 - 2 5 +θ 4 θ≥0 E1 3 2 5 4
25
θ 12 25 10 15
10 3 20−θ ≥0 E2 4 1 7 6
35
E2 4 + 1 - 7 6 15+θ ≥ 0 18 17
θ θ 35 3−θ ≥0 7 8 3 5
15 20 E3 3 30
12+θ ≥ 0 27
7 8 + 3 -θ 5 (Demand 42
E3
θ 30
30 30−θ≥ 0 10 18 20 90
a)
(Demand 42
10 18 20 90
a)
El valor máximo
posible de θ que
resuelve el sistema es:
θ=3
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 201 | 228
E1D1 (10)(3) 30
E1D4 (15)(4) 60
E2D2 (18)(1) 18
E2D3 (17)(7) 119
E3D3 (3)(3) 9
E3D4 (27)(5) 135
COSTO TOTAL DE TRANSPORTE $371
Para determinar si es óptima esta solución inicial, o bien para hacerla óptima, se aplicará el Método de Modi:
Paso 1: Calcular los multiplicadores (ui y vj) y los costos marginales (c.m.).
Los multiplicadores (ui y vj) están Se obtiene el sistema: Resolviendo el sistema, Los costos marginales están Utilizando el valor calculado de los
asociados a toda celda básica y su suponiendo u1=0 asociados a toda celda no básica multiplicadores, encontramos los
expresión es: (No llena en la asignación) con la costos marginales de la primera
expresión: solución factible:
Paso 2: Si existe por lo menos un costo marginal negativo tomar la celda con mayor valor negativo. Crear un circuito con todos los vértices en
celdas de variables básicas (el más simple posible). Es decir, encontrar la trayectoria de la variable “No básica” que entrara a la solución.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 202 | 228
D1 D2 D3 D4 Oferta
E1 (-θ) 3 2 5 (+θ) 4
25
10 15
E2 (+θ) 4 (+θ) 1 (-θ) 7 6
35
18 17
7 8 (+θ ) 3 (-θ) 5
E3 30
3 27
(Demanda) 10 18 20 42 90
Paso 3: Ajustar el valor de xij en las celdas del circuito, comenzando por sumar la variable θ a la celda seleccionada en el Paso 2, en el sentido de
las manecillas del reloj, y alternar una resta y suma de θ en cada celda de la trayectoria hasta regresar a la celda primera. Resolver para θ y ajustar
la solución. En todo caso volver al Paso 1.
Primera asignación Ahora se plantea el segunda asignación
sistema de desigualdades
para obtener el valor de θ
y ajustar los valores:
D1 D2 D3 D4 Oferta D1 D2 D3 D4 Oferta
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 203 | 228
Se hace el cálculo del costo de transporte
Para determinar si es óptima esta solución inicial, o bien para hacerla óptima, se aplicará el Método de Modi:
Paso 1: Calcular los multiplicadores (ui y vj) y los costos marginales (c.m.).
Los multiplicadores (ui y vj) están Se obtiene el sistema: Resolviendo el sistema, Los costos marginales están Utilizando el valor calculado de los
asociados a toda celda básica y su suponiendo u1=0 asociados a toda celda no básica multiplicadores, encontramos los
expresión es: (No llena en la asignación) con la costos marginales de la primera
expresión: solución factible:
Paso 2: Si existe por lo menos un costo marginal negativo tomar la celda con mayor valor negativo. Crear un circuito con todos los vértices en
celdas de variables básicas (el más simple posible). Es decir, encontrar la trayectoria de la variable “No básica” que entrara a la solución. Para este
caso la celda (2,4) por lo que el circuito es:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 204 | 228
D1 D2 D3 D4 Oferta
E1 3 2 5 4
25
25
E2 4 1 (-θ) 7 (+θ) 6
35
10 18 7
7 8 (+θ) 3 (-θ) 5
E3 30
13 17
(Demanda) 10 18 20 42 90
Paso 3: Ajustar el valor de xij en las celdas del circuito, comenzando por sumar la variable θ a la celda seleccionada en el Paso 2, en el sentido de
las manecillas del reloj, y alternar una resta y suma de θ en cada celda de la trayectoria hasta regresar a la celda primera. Resolver para θ y ajustar
la solución. En todo caso volver al Paso 1.
Primera asignación Ahora se plantea el segunda asignación
sistema de
desigualdades para
obtener el valor de θ
y ajustar los
valores:
D1 D2 D3 D4 Oferta D1 D2 D3 D4 Oferta
E1 3 2 5 4 θ≥0 E1 3 2 5 4
25 25
25 25
E2 4 1 (-θ) 7 (+θ) 6
35 17−θ ≥0 E2 4 1 7 6
35
10 18 7 10 18 7
7 8 (+θ 3 (-θ) 5 13+θ ≥ 0 7 8 3 10 5
E3 20 30
E3 ) 17 30 7−θ ≥0
13 (Demanda) 42
10 18 20 90
(Demanda) 10 18 20 42 90 El valor máximo
posible de θ que
resuelve el sistema
es:θ = 7
Se hace el cálculo del costo de transporte
E1D4 (25)(4) 100
E2D1 (10)(4) 40
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 205 | 228
E2D2 (18)(1) 18
E2D4 (7)(6) 42
E3D3 (20)(3) 60
E3D4 (10)(5) 50
COSTO TOTAL DE TRANSPORTE $310
Como en el cálculo de las celdas no básicas son positivas por lo tanto se ha encontrado la solución óptima para este problema.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 206 | 228
Problema 2
Una empresa dispone de tres fábricas que producen el mismo bien. Las cantidades disponibles de ese
bien en cada fábrica es de 25, 35 y 30 unidades, respectivamente. La empresa debe proveer a cuatro
tiendas que demandan 10, 18, 20 y 42 unidades del producto, respectivamente. Los costes unitarios de
transporte del bien vienen dados por la siguiente tabla:
D1 D2 D3 D4
E1 3 2 5 4 25
E2 4 1 7 6 35
E3 7 8 3 5 30
10 18 20 42 90
Se desea determinar cómo han de realizarse los envíos a las tiendas de manera que se minimice el costo
total de transporte.
D1 D2 D3 D4 (Oferta)
3 2 5 4
E1 25
4 1 7 6
E2 35
7 8 3 5
E3 30
(Demanda) 10 18 20 42 90
PROBLEMA 3
Una empresa produce un único artículo en tres plantas, A1, A2 y A3. La capacidad de producción
mensual de la empresa esta limitada a 1500 unidades mensuales en cada una de las plantas. La empresa
tiene cuatro clientes mayoristas cuyas demandas mensuales son 1000, 1200, 1500 y 1000 unidades
respectivamente.
El beneficio unitario que le proporciona su producto, considerados los costes de producción y el precio
de venta, es de 110 unidades. Los costos de envío a los 4 clientes mayoristas que la empresa tiene vienen
dados por la siguiente tabla.
1 2 3 4
A1 30 10 25 20
A2 15 25 30 10
A3 20 30 15 20
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 207 | 228
El objetivo de la empresa es organizar la producción en cada uno de los meses para obtener el máximo
beneficio.
PROBLEMA 4
Sarah Mahan presidente de Mahan Concrete Company tienen plantas en tres localizaciones y está
actualmente trabajando en tres grandes proyectos de construcció n, ubicados en diferentes sitios.
El costo del embarque por cada carga de camió n de concreto, capacidades de planta y
requerimientos de proyecto se muestran a continuació n:
Formule una solució n inicial factible para el problema de transportació n de Mahan utilizando la
regla de la esquina Noroeste.
Luego evalué cada ruta de embarque no utilizada(cada celda vacía) al aplicar el método del escaló n
y calcule todos los índices de mejoramiento
Revise que exista el nú mero adecuado de celdas ocupadas para una solució n normal
Cantidad
Desde HACIA de la
fabrica
Proyecto A Proyecto B Proyecto C
$1
$4 $11 70
Planta 1 0
$1
$5 $8 50
Planta 2 2
$9 $7 $6 30
Planta 3
Requerimientos del
40 50 60 150
proyecto
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 208 | 228
Solución Inicial obtenida en el Metodo de Esquina Noroeste
Cantidad de
Desde HACIA
la fabrica
P1-PA (40)(10) 400
Proyecto A Proyecto B Proyecto C P1-PB (30)(4) 120
P2-PB (20)(5) 100
$1
40 30 $4 $11 70 P2-PC (30)(8) 240
Planta 1 0 P3-PC (30)(6) 180
Costo de transporte $1,040
$1
$5 $8 50
Planta 2 2
20 30
Para determinar si es óptima esta solución inicial,
$9 $7 30 $6 30 o bien para hacerla óptima, se aplicará el Método
Planta 3
de Modi:
Requerimientos del
40 50 60 150
proyecto
Los multiplicadores (ui,vj) Se obtiene el sistema: Resolviendo el sistema, Los costos marginales están Utilizando el valor calculado de
están asociados a toda celda suponiendo u1=0: asociados a toda celda no básica, los multiplicadores,
básica y su expresión es: (no llena en la primera encontramos los costos
asignación) con la expresión: marginales de la primera
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 209 | 228
solución factible:
Celda (i,j); ui + vj = cij u1 + v1 = 10 u1= 0 Celda (i,j); c.m. = cij - ui - vj Celda (1,3); c.m. = 11-0-7=4
Celda (1,1); u1 + v1 = c11 u 1 + v2 = 4 0 + v1 = 10 Celda (1,3); c.m. = c13 – u1 – v3 Celda (2,1); c.m. = 12-1-10=1
Celda (1,2); u1 + v2 = c12 u 2 + v2 = 5 0 + v2 = 4 Celda (2,1); c.m. = c21 – u2 – v1 Celda (3,1); c.m. = 9-(-1)-4=6
Celda (2,2); u2 + v2 = c22 u 2 + v3 = 8 u2 + 4 = 5 …. u2 = 1 Celda (3,1); c.m. = c31 – u3 – v1 Celda (3,2); c.m. = 7-(-1)-4=4
Celda (2,3); u2 + v3 = c23 u 3 + v3 = 6 1 + v3 = 8 …. V3 = 7 Celda (3,2); c.m. = c32 – u3 – v2
Celda (3,3); u3 + v3 = c33 u3 + 7 = 6 … u3 = -1
Como obtuvimos valores positivos en los costos marginales podemos decir que la asignación inicial es óptima.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 210 | 228
(6.4) Modelo de asignación
Una de las actividades más comunes en los negocios es la asignación de la persona “ideal” para la
eficiente realización de una tarea en particular; sin embargo, la manera de realizar esta asignación
presenta ciertas dificultades implícitas, por ejemplo, ¿quién es la persona indicada para cada tarea?, ¿es
mínimo el costo de esta asignación?, así como ¿qué tipo de información soporta la asignación realizada?
En general, la asignación tiene que ver con personas, pero también se utiliza para asignar plantas
industriales, vehículos e incluso periodos de tiempo con tareas específicas.
La importancia de presentar y resolver el modelo de asignación radica en que se busca optimizar algún
objetivo como:
Debido a que el modelo de asignación es un caso particular del modelo de transporte; habitualmente, el
primero se resolvía con las herramientas del segundo, pero dadas las características del modelo de
asignación, la inversión en cálculos y tiempo de cómputo era demasiado alta. En consecuencia, dos
matemáticos húngaros desarrollaron un algoritmo para resolver de manera eficiente el modelo de
asignación, siendo éste conocido como el
Método Húngaro.
Como para todo problema de programación lineal, es necesario definir las variables de decisión del
problema y en este caso particular del modelo de asignación, las variables son:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 211 | 228
El costo total y las restricciones del modelo están dados por las funciones:
El modelo de asignación recién presentado es similar al modelo de transporte y bien podría resolverse
con las mismas herramientas, pero, como ya lo hicimos notar, utilizaremos para resolverlo el Método
Húngaro. En este sentido cabe mencionar que para este método se utiliza una representación tabular del
problema de asignación en lugar del modelo matemático, razón por la cual presentamos directamente el
algoritmo general.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 212 | 228
c. Los costos cubiertos por una sola línea permanecen iguales.
d. Volver al paso 4.
El modelo de asignación recién presentado es similar al modelo de transporte y bien podría resolverse
con las mismas herramientas, pero, como ya lo hicimos notar, utilizaremos para resolverlo el Método
Húngaro. En este sentido cabe mencionar que para este método se utiliza una representación tabular del
problema de asignación en lugar del modelo matemático, razón por la cual presentamos directamente el
algoritmo general.
Supón que a tres personas A, B y C se les deben asignar las tareas TI, TII y TIII. Sabiendo que los costos de
asignar a la persona A en las tareas TI, TII y TIII, son $11, $9 y $7, respectivamente; de igual forma para B,
los costos son $9, $6 y $12, para TI, TII y TIII; mientras que para C los costos son de $8, $12 y $6 para las
mismas tareas, determina la asignación para obtener el costo mínimo.
TI TII TIII
A $11 $9 $7
B $9 $6 $12
C $8 $12 $6
2. Identificar el costo menor por fila y restarlo a todos los elementos de la fila correspondiente.
3. En la tabla que resulte del punto anterior, identificar el costo menor por columna y restarlo a todos los
elementos de la columna correspondiente.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 213 | 228
4. Identificar los ceros de asignación que son únicos en su fila y columna (puede haber más ceros en la
fila o columna, pero sólo uno es de asignación
TI TII TIII
A $2 $2 $0
B $1 $0 $6
C $0 $6 $0
Para esta tabla se observa que los ceros de asignación están en las celdas (1,3), (2,2) y (3,1); para mostrar
con más claridad la posición de los ceros de asignación, el Método Húngaro permite intercambiar
columnas o filas para intentar encontrar una diagonal principal con todas las entradas igual a cero, como
a continuación se muestra:
TIII TII TI
A $0 $2 $2
B $6 $0 $1
C $0 $6 $0
Donde se intercambió la columna de TI por la de TIII. Así, se observa que la posición de los ceros de
asignación indica la tarea que le corresponde a cada candidato de asignación.
Como el número de ceros de asignación es igual al número de tareas, tres en este caso, termina el
método pues se ha determinado la asignación óptima, pero falta indicar el costo de tal asignación.
Para calcular el costo del modelo, recuperamos de la tabla original los costos asociados a la asignación
propuesta y sumamos para obtener el costo total, es decir,
EJEMPLO:
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 214 | 228
La más conocida técnica de solución para el problema de asignación pura es el método húngaro,
desarrollado a partir del teorema que demostró el matemático húngaro König en 1916. Este método
utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los
costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos.
En cada iteración del método húngaro, se reduce la matriz de tal manera que haya al menos un cero en
cada renglón y columna, comprobando con el teorema de König si se ha alcanzado la solución óptima. Si
el número mínimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces
existe una asignación óptima (no necesariamente única).
La siguiente matriz contiene los costos para operar n=4 máquinas, por n=4 personas así calificadas en su
empresa. Optimice la asignación idónea.
i/j M M2 M3 M4
1
P1 1 4 6 3
P2 9 7 10 9
P3 4 5 11 7
P4 8 7 8 5
Paso 1 .Seleccione en cada renglón i de la matriz, el menor costo C i j, (menor C i j = U i ), luego réstelo en
cada elemento del renglón.
M Costo menor en
i/j M2 M3 M4
1 cada fila
P1 1 4 6 3 1
P2 9 7 10 9 7
P3 4 5 11 7 4
P4 8 7 8 5 5
Matriz con costo menor
En cada fila restado a cada elemento
i/j M1 M2 M3 M4
P1 0 3 5 2
P2 2 0 3 2
P3 0 1 7 3
P4 3 2 3 0
Pasó 2. Seleccione en cada columna j de la matriz resultante en el paso 1, el costo menor C i j, (menor
Cij=Vj) y réstelo en cada elemento de la misma columna.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 215 | 228
Matriz con costo menor
En cada fila restado a cada elemento Matriz con costo menor
i/j M1 M2 M3 M4 En cada columna restado a cada elemento
P1 0 3 5 2 i/j M1 M2 M3 M4
P1 0 3 2 2
P2 2 0 3 2
P3 0 1 7 3 P2 2 0 0 2
P4 3 2 3 0 P3 0 1 4 3
P4 3 2 0 0
Costo menor 0 0 3 0
en cada
columna
Paso 3.Sombree los renglones y/o columnas de la matriz, de tal modo que sean los mínimos necesarias
para cubrir todos los ceros.
i/j M1 M2 M3 M4
P1 0 3 2 2
P2 2 0 0 2
P3 0 1 4 3
P4 3 2 0 0
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 216 | 228
Se tiene la solución óptima cuando el mínimo necesario de renglones y columnas sombreadas para cubrir
los ceros es n. En este problema el mínimo es n =4.
i/j M1 M3 M2 M4
i/j M M2 M3 M4
P1 0 1 2 1
1
P1 0 2 1 1 P2 3 0 0 2
P3 0 3 0 2
P2 3 0 0 2
P4 4 0 2 0
P3 0 0 3 2
P4 4 2 0 0 i/j M M2 M3 M4
1
P1 1 4 6 3
P2 9 7 10 9
P3 4 5 11 7
Entonces la asignación óptima es la que muestra la tabla siguiente: P4 8 7 8 5
PRBLEMA 1
Supón que a tres personas A, B y C se les deben asignar las tareas TI, TII y TIII. Sabiendo que los costos de
asignar a la persona A en las tareas TI, TII y TIII, son $11, $9 y $7, respectivamente; de igual forma para B,
los costos son $9, $6 y $12, para TI, TII y TIII; mientras que para C los costos son de $8, $12 y $6 para las
mismas tareas, determina la asignación para obtener el costo mínimo.
TI TII TIII
A $1 $9 $7
1
B $9 $6 $12
C $8 $12 $6
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 217 | 228
Paso 1 seleccionar los costos más bajos de cada renglón y restárselo a todos los elementos del mismo
renglón para generar una nueva tabla.
TI TII TIII
A $4 $5 $0
B $3 $0 $6
C $2 $6 $0
Paso 2 Seleccionar los costos más bajos de cada columna y restarlos al los elementos de la respectiva
columna para generar una nueva tabla.
TI TII TIII
A $2 $5 $0
B $1 $0 $6
C $0 $6 $0
Podemos observar que esta solución es optima debido a que el numero de renglones y columnas
subrayadas en la matriz es igual a n, en este caso N=3
PROBLEMA 2
i/j A A A A A
1 2 3 4 5
C 3 8 12 10 3
1
C 8 7 2 9 7
2
C 6 4 2 7 5
3
C 8 4 2 3 5
4
C 9 10 6 9 10
5
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 218 | 228
Paso 1 seleccionar los menores costos de cada renglón y restárselos a los elementos del mismo renglón
para obtener una nueva tabla
i/j A A A A A
1 2 3 4 5
C 0 5 9 7 0
1
C 6 5 0 7 5
2
C 4 2 0 5 3
3
C 6 2 0 1 3
4
C 3 4 0 3 4
5
Paso 2 Seleccionar los menores costos de cada columna y restárselos a los elementos de la misma
columna para obtener una nueva tabla
Paso 3 Sombrear los renglones y columnas de tal manera que se cubran todos los ceros, como consejo es
recomendable empezar sombreando los renglones o columnas con mayor numero de ceros a fin de cubrir
todos los ceros existentes.
i/j A A A A A
1 2 3 4 5
C 0 3 9 6 0
1
C 6 3 0 6 5
2
C 4 0 0 4 3
3
C 6 0 0 0 3
4
C 3 2 0 2 4
5
Paso 4 Verificar si la suma de renglones y columnas sombreadas es igual o menor a N, en este caso N=5
de ser igual la solución seria optima de no ser así proseguir con el paso 5
Paso 5 Seleccionar de los elementos no sombreados el de menor valor y restárselo a los elementos no
sombreados y sumar en las intersecciones de los renglones y columnas sombreadas.
i/j A A A A A
1 2 3 4 5
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 219 | 228
C 0 3 11 6 0
1
C 4 1 0 4 3
2
C 4 0 2 4 3
3
C 6 0 2 0 3
4
C 1 0 0 0 2
5
Paso 6 Sombrear los renglones y columnas de tal manera que se cubran todos los ceros, como consejo es
recomendable empezar sombreando los renglones o columnas con mayor numero de ceros a fin de cubrir
todos los ceros existentes.
i/j A A A A A
1 2 3 4 5
C 0 3 11 6 0
1
C 4 1 0 4 3
2
C 4 0 2 4 3
3
C 6 0 2 0 3
4
C 1 0 0 0 2
5
Paso 7 Verificar si la suma de renglones y columnas sombreadas es igual o menor a N, en este caso N=5
de ser igual la solución sería optima de no ser así proseguir con el paso 5
En este Caso la solución a pesar de que existan 5 renglones o columnas subrayados aun no se presenta
factibilidad es por esto que deberemos seguir intentando hasta encontrar una solución factible.
i/j A A A A A
1 2 3 4 5
C 0 6 14 6 0
1
C 1 1 0 1 0
2
C 1 0 2 1 0
3
C 6 3 5 0 3
4
C 1 3 3 0 2
5
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 220 | 228
Paso 7 Verificar si la suma de renglones y columnas sombreadas es igual o menor a N, en este caso N=5
de ser igual la solución sería optima de no ser así proseguir con el paso 5
En este Caso la solución a pesar de que existan 5 renglones o columnas subrayados aun no se presenta
factibilidad es por esto que deberemos seguir intentando hasta encontrar una solución factible.
i/j A A A A A
1 2 3 4 5
C 0 7 14 7 0
1
C 1 2 0 2 0
2
C 0 0 1 1 0
3
C 5 3 4 0 3
4
C 0 3 2 0 2
5
En este momento podemos decir que la solución es la optima mediante la asignación arriba graficada.
De este modo la asignación se verá representada por el siguiente costo en congruencia con la tabla de
costos.
i/j A A A A A
1 2 3 4 5
C 3 8 12 10 3
1
C 8 7 2 9 7
2
C 6 4 2 7 5
3
C 8 4 2 3 5
4
C 9 10 6 9 10
5
PROBLEMA 3
Suponga que la situación analizada en el ejemplo 5.4-1 se amplía a cuatro niños y cuatro tareas.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 221 | 228
Tarea
Niñ 1 2 3 4
o
1 $1 $4 $6 $3
2 $9 $7 $10 $9
3 $4 $5 $11 $7
4 $8 $7 $8 $5
Paso 1 seleccionar los menores costos de cada renglón y restárselos a los elementos del mismo renglón para obtener
una nueva tabla
Tarea
Niñ 1 2 3 4
o
1 $0 $3 $5 $2
2 $2 $0 $3 $2
3 $0 $1 $7 $3
4 $3 $2 $3 $0
Paso 2 Seleccionar los menores costos de cada columna y restárselos a los elementos de la misma columna para
obtener una nueva tabla
Paso 3 Sombrear los renglones y columnas de tal manera que se cubran todos los ceros, como consejo es
recomendable empezar sombreando los renglones o columnas con mayor numero de ceros a fin de cubrir todos los
ceros existentes.
Tarea
Niñ 1 2 3 4
o
1 $0 $3 $2 $2
2 $2 $0 $0 $2
3 $0 $1 $4 $3
4 $3 $2 $0 $0
Paso 4 Comenzamos a asignar por los sitios donde exista menor número de 0, y tachamos los demás 0 de la columna
y renglón que lo acompañen, así sucesivamente hasta lograr las 4 asignaciones, de no existir una forma de realizar 4
asignaciones en los 0 se deberá realizar un paso más.
Paso 5 Seleccionar de los elementos no sombreados el de menor valor y restárselo a los elementos no sombreados y
sumar en las intersecciones de los renglones y columnas sombreadas.
Tarea
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 222 | 228
Niñ 1 2 3 4
o
1 $0 $2 $2 $1
2 $3 $0 $1 $2
3 $0 $0 $4 $2
4 $4 $2 $1 $0
Paso 6 Comenzamos a asignar por los sitios donde exista menor número de 0, y tachamos los demás 0 de la columna
y renglón que lo acompañen, así sucesivamente hasta lograr las 4 asignaciones, de no existir una forma de realizar 4
asignaciones en los 0 se deberá realizar un paso más.
Paso 7 Seleccionar de los elementos no sombreados el de menor valor y restárselo a los elementos no sombreados y
sumar en las intersecciones de los renglones y columnas sombreadas.
Tarea
Niñ 1 2 3 4
o
1 $0 $2 $1 $1
2 $3 $0 $0 $2
3 $1 $1 $4 $3
4 $4 $2 $0 $0
Paso 8 Comenzamos a asignar por los sitios donde exista menor número de 0, y tachamos los demás 0 de la columna
y renglón que lo acompañen, así sucesivamente hasta lograr las 4 asignaciones, de no existir una forma de realizar 4
asignaciones en los 0 se deberá realizar un paso más.
Paso 9 Seleccionar de los elementos no sombreados el de menor valor y restárselo a los elementos no sombreados y
sumar en las intersecciones de los renglones y columnas sombreadas.
Tarea
Niñ 1 2 3 4
o
1 $0 $2 $2 $2
2 $3 $0 $1 $3
3 $0 $0 $4 $3
4 $3 $1 $0 $0
Paso 10 Comenzamos a asignar por los sitios donde exista menor número de 0, y tachamos los demás 0 de la
columna y renglón que lo acompañen, así sucesivamente hasta lograr las 4 asignaciones, de no existir una forma de
realizar 4 asignaciones en los 0 se deberá realizar un paso más.
Paso 11 Seleccionar de los elementos no sombreados el de menor valor y restárselo a los elementos no sombreados y
sumar en las intersecciones de los renglones y columnas sombreadas.
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 223 | 228
Tarea
Niñ 1 2 3 4
o
1 $0 $2 $1 $1
2 $3 $0 $0 $2
3 $0 $0 $4 $2
4 $3 $2 $0 $0
• Ejemplo 1: Un joven ingeniero de una compañía ha sintetizado un nuevo fertilizante hecho a partir de
dos materias primas. Al combinar cantidades de las materias primas básicas x1 y x2, la cantidad de
fertilizante que se obtiene viene dada por Q = 4x1 + 2x2 −0.5x2 1 −0.25x2 2. Se requieren 480 euros por
unidad de materia prima 1 y 300 euros por cada unidad de materia prima 2 que se empleen en la
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 224 | 228
fabricación del fertilizante (en estas cantidades se incluyen los costos de las materias primas y los costos
de producción). Si la compañía dispone de 24000 euros para la producción de materias primas, plantear
el problema para determinar la cantidad de materia prima de forma que se maximice la cantidad de
fertilizante. Las variables de decisión del problema son:
- El coste no puede exceder el presupuesto que la empresa tiene asignado para el fertilizante, 480x 1 +
300x2 ≤ 24000
- No negatividad de las cantidades: x1 ≥ 0, x2 ≥ 0 Por tanto
• Ejemplo 2: Una empresa produce frigoríficos y ha firmado un contrato para suministrar al menos 150
unidades en tres meses, 50 unidades al final del primer mes, 50 al final del segundo y 50 al final del
tercero. El coste de producir una cantidad de frigoríficos en cualquier mes es su cuadrado. La empresa
puede producir si lo desea más frigoríficos de los que necesita en cualquier mes y guardarlos para el
siguiente, siendo el coste de almacenaje de 12 euros por unidad al mes. Suponiendo que no hay
inventario inicial, formular el programa adecuado para determinar el número de frigoríficos que deben
producirse cada mes, para minimizar el coste total. Las variables de decisión del problema son:
x1 : número de frigoríficos a producir en el primer mes
x2 : número de frigoríficos a producir en el segundo mes
x3 : número de frigoríficos a producir en el tercer mes
El objetivo es minimizar los costos, Costo total= Costo de producción + Costo de almacenaje del segundo
mes + Costo de almacenaje del tercer mes
Costo de producción = x21 + x22 + x23
Costo de almacenaje del segundo mes = 12(x 1 −50)
Costo de almacenaje del tercer mes = 12(x 1 + x2 −50)
Por tanto, Z(x1,x2,x3) = x21 + x22 + x23 + 12(x1 −50) + 12(x1 + x2 −50)
Por tanto
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 225 | 228
Min Z(x1,x2,x3) = x21 + x22 + x23 + 12(x1 −50) + 12(x1 + x2 −50)
s.a.
x1 ≥ 50
x1 −50 + x2 ≥ 50
x1 + x2 −100 + x3 ≥ 50
x2 ≥ 0, x3 ≥ 0
Como en Programación lineal la función f(x 1,,x2,...,xn) es la función objetivo del P.N.L. y gi(x 1,x2,...,xn)
(≤,=,≥)bi, i = 1,...,m son las restricciones del mismo. Además se supone que estas funciones son
diferenciables.
Notar que las características y propiedades de los P.N.L. son distintas a las de P.L. y los algoritmos de
optimización son también diferentes a los utilizados en P.L.
⋄ Sin restricciones: Estos problemas son un programa matemático para los que las variables de decisión
no están restringidas. Su formulación es de la siguiente forma:
Este tipo de problemas aparecen de forma natural en distintas áreas de la ciencia tales como Estadística
y Econometría. Otro aspecto importante de este tipo es que, en ocasiones, un P.N.L. con restricciones se
puede resolver a partir de un sin restricciones.
Ejemplo: Se poseen los siguientes datos sobre una población animal, y a lo largo de cinco años. Se quiere
ajustar a un modelo y = aebt
ti 1 2 4 5 8
yi 4 4 6 11 22
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 226 | 228
Mina;b F(a; b):
Notemos que el método de mínimos cuadrados responde a una formulación no lineal sin restricciones;
esto es, La función y = ax + b se ajusta a los datos (xi,yi), i = 1,...,n minimizando la expresión
Notemos que los problemas con restricciones de desigualdad permiten reflejar la realidad en términos
matemáticos mejor que los problemas con restricciones de igualdad, ya que no “limitan” tanto la
elección de los valores de las variables de decisión.
Los problemas con restricciones de igualdad suelen considerarse como poco realistas debido a lo
restrictivo de su planteamiento. Sin embargo, el estudio de ellos se considera interesante ya que es de
utilidad en distintas áreas de conocimiento como Economía, Estadística...
Ejemplo: Una compañía planea gastar 10000 euros en publicidad. Se sabe que un minuto de publicidad
en televisión cuesta 3000 euros y 1000 euros en la radio. Si la empresa compra x minutos de publicidad
en televisión e y minutos en la radio, su ingreso, en euros, está dado por −2x 2 −y2 + xy + 8x + 3y. ¿Cómo
puede la empresa maximizar sus ingresos? Las variables de decisión del problema son:
El objetivo es maximizar los ingresos, Z(x,y) = −2x 2 −y2 + xy + 8x + 3y Restricciones del problema:
- Gastar 10000 euros en publicidad en los dos medios, 3000x + 1000y = 10000.
Por tanto Ma Z(x,y) = −2x2 −y2 + xy + 8x + 3y
s.a. 3000x + 1000y = 10000
Ejemplo: Una compañía petrolífera debe determinar cuántos barriles de petroleó hay que extraer en los
próximos dos años. Si la compañía extrae x 1 millones de barriles durante un año, se podrá vender cada
barril a 30-x1 euros. Si extrae x2 millones de barril durante el segundo año, se podrá vender cada barril a
35-x2 euros. El costo para extraer x 1 millones de barriles en el primer año es de x 2 1 millones de euros y el
costo para extraer x2 millones de barriles durante el segundo año es de 2x 22 millones de euros. Se puede
obtener como máximo un total de 20 millones de barriles de petroleó, y se puede gastar como máximo
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 227 | 228
250 millones de euros en la extracción. Formular el P.N.L. para ayudar a la empresa a maximizar sus
ganancias para los próximos dos años.
Las variables de decisión del problema son:
Este problema es un problema no lineal con restricciones de desigualdad (no lineal y lineal).
Investigación de Operaciones
Material educativo de apoyo
Ing. Teresita de Jesús Marín Rojas P á g i n a 228 | 228