• Author / Uploaded
• JoseMiguelVeizagaJustiniano

Citation preview

Ciencias Empresariales 

Investigación de Operaciones 

www.upds.edu.bo  www.updsfacebook  INDICE 

UNIVERSIDAD PRIVADA DOMINGO SAVIO  SANTA CRUZ – BOLIVIA  PROGRAMA ANALITICO  IDENTIFICACIÓN  Carreras 

: 

Ingeniería de Sistemas  Ingeniería Comercial 

I. 

Materia 

: 

Investigación de Operaciones 

Carga Horaria  Nivel 

:  : 

60 hrs  Sexto Semestre 

Pre­requisitos 

: 

Estadística II 

JUSTIFICACION 

Toda  organización  empresarial  día  a  día  se  enfrenta  a  la  toma  de  decisiones  (en  lo  que se refiere a la  administración  de sus recursos)   para  desarrollar cada una  de  las  actividades que relacionan a la misma con el medio en el que se desenvuelve; es en  este sentido que  de la administración óptima de los recursos dependerá  el  éxito o el  retraso  de  la  organización,  por  lo  que  contar  con  herramientas  científicas  para  plantear, desarrollar y resolver problemas de optimización permitirá  a  la organización  una mejor toma de decisiones.  II. 

OBJETIVO DE LA MATERIA 

Proporcionar  al  estudiante  las  herramientas  básicas  y  técnicas  necesarias,  para  el  planteamiento,  desarrollo  y  solución  de  modelos  matemáticos  que  expresen  la  Optimización de  los  recursos  (humanos,  materiales  y  económicos)  inherentes  a  toda  organización  empresarial;  coadyuvando  en  la  toma  decisiones  con  fundamentos  científicos y racionales.  III. 

OBJETIVOS ESPECÍFICOS 

El alumno al concluir el curso podrá:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

1 

Ciencias Empresariales 

a) 

Investigación de Operaciones 

Formular  situaciones  reales  como  modelos  matemáticos  de  optimización 

y/o 

asignación 

de 

recursos 

en 

organizaciones 

empresariales.  b) 

Establecer  una  buena comprensión  y  adquirir destreza en el desarrollo  de problemas de optimización de recursos. 

IV. 

c) 

Analizar y resolver problemas de optimización, a través de la aplicación 

d) 

de modelos matemáticos.  Interpretar y diferenciar los distintos tipos de modelos y soluciones. 

UNIDADES PROGRAMÁTICAS 

UNIDAD 1  INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES  Objetivos de la unidad:  ­ 

Analizar  los  orígenes,  precursores  y  evolución  de  la  Investigación  de 

­ 

operaciones (I.O.).  Conceptualizar y clasificar los distintos modelos matemáticos de optimización. 

­ 

Comprender  y  aplicar  la  metodología  que  emplea  la  I.O.  para  la  solución  de  problemas de optimización.  1.1  Introducción  1.2  Origen de la Investigación de Operaciones (I.O.)  1.3  Precursores y estudiosos de la I.O.  1.4  Noción, Concepto y alcance de la I.O.  1.5  Modelos matemáticos de decisión y su clasificación  1.5.1 Concepto de modelo  1.5.2 Clasificación de los modelos matemáticos de decisión  a)  b) 

Modelos Determinísticos  Modelos Estocásticos (Probabilísticos) 

c)  d) 

Modelos Estáticos  Modelos Dinámicos 

1.6  Metodología de la Investigación de Operaciones  1.7  Aplicaciones de la I.O.  1.8  Beneficios con la aplicación de la I.O.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

2 

Ciencias Empresariales 

Investigación de Operaciones 

UNIDAD 2  FORMULACIÓN DEL MODELO DE PROGRACMACIÓN LINEAL  Objetivos de la unidad:  ­ 

Comprender  y  aplicar  el  procedimiento  para  formular  un  Modelo  de  Programación Lineal (M.P.L.) 

­ 

Desarrollar  las  diferentes  formas  de  presentación  de  un  Modelo  de  Programación Lineal (M.P.L.) 

2.1  Introducción  2.2  Concepto de Programación Lineal  2.3  Procedimiento para Formular un M.P.L.  2.3.1 Definición de Variables  2.3.2 Función Objetivo  2.3.3 Restricciones Estructurales o Funcionales  2.3.4 Restricciones de No negatividad  2.4  Formas de presentación de un M.P.L.  2.4.1 Formulación Canónica  2.4.2 Formulación Estándar  2.5  Planteamiento de los recursos por unidad de actividad  2.6  Problemas de aplicación  UNIDAD 3  SOLUCIÓN DEL MODELO DE PROGRAMACIÓN LINEAL  Objetivos de la unidad:  ­  ­ 

Analizar, representar é interpretar el método gráfico para resolver un M.P.L.  Analizar la teoría del Método Simplex 

­ 

Aplicar los métodos de resolución Simplex, de las M’s y de las dos fases para  determinar la solución óptima.  3.1  Introducción  3.2  Método Gráfico  3.2.1 Fundamentos y mecánica del método gráfico  3.2.2 Región Factible (Solución Básica Factible)  3.2.3 Solución Óptima  3.2.4 Casos Especiales  3.3  Método Simplex

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

3 

Ciencias Empresariales 

Investigación de Operaciones 

3.3.1 Teoría del Método Simplex  3.3.2 Definición Matricial del problema de P.L.  3.3.3 Planteamiento del Algoritmo Simplex  3.4  Solución Óptima del problema de P.L.  3.4.1 Método Simplex  3.4.2 Método de las M’s  3.4.3 Método de las Dos Fases  3.4.4 Casos Especiales  UNIDAD 4  TEORIA DE LA DUALIDAD  Objetivos de la unidad:  ­ 

Analizar y comprender la Teoría de la Dualidad. 

­ 

Plantear y resolver problemas de P.L. mediante el método Dual­Simplex 

4.1  Introducción  4.2  Formulación matemática del problema Dual  4.3  Comparación Primal ­ Dual  4.4  Interpretación Económica del problema Dual  4.5  Solución de problemas duales  4.5.1 Método Dual ­ Simplex  UNIDAD 5  ANALISIS DE SENSIBILIDAD  Objetivos de la unidad:  ­ 

Analizar  y  aplicar  los cambios en  los parámetros y determinar como afectan 

­ 

en los resultados finales.  Establecer controles y rangos de validez para las soluciones. 

5.1  Introducción  5.2  Cambios Discretos  5.2.1 Cambios en el vector b  5.2.2 Cambios en el vector c  5.2.3 Cambios en los coeficientes tecnológicos  5.3  Cambios Continuos  5.4.1 Cambios continuos en el vector b

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

4 

Ciencias Empresariales 

Investigación de Operaciones 

5.4.2 Cambios continuos en el vector c 

UNIDAD 6  MODELO DE TRANSPORTE Y ASIGNACIÓN  Objetivos de la unidad:  ­  ­ 

Establecer é identificar los problemas de transporte de recursos.  Analizar, formular y resolver problemas de transporte. 

­ 

Analizar, formular y resolver problemas de asignación de recursos 

6.1  Introducción  6.2  Problema de Transporte  6.2.1 El Modelo de Transporte  6.2.2 Algoritmo del Modelo de Transporte  6.2.3 Balanceo de problemas de transporte  6.3  Solución del Modelo de Transporte  6.3.1 Método de la Esquina Noroeste  6.3.2 Método de Aproximación de Vogel  6.3.3  Método del Costo Mínimo  6.4  Problema de Asignación  6.4.1 Formulación del modelo  6.3.2 Solución del modelo (Método Húngaro)  UNIDAD 7  TEORIA DE REDES  Objetivos de la unidad:  ­ 

Establecer é identificar los problemas de optimización mediante la teoría de  redes. 

­ 

Analizar, formular y resolver problemas de redes, aplicando los métodos de  la ruta más corta, el flujo máximo y árbol de extensión mínima. 

­ 

Analizar,  formular  y  resolver  problemas  de  planeamiento  de  actividades  mediante CPM y PERT 

7.1  Introducción  7.2  Definición de Red  7.3  Problema del Árbol de extensión mínima

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

5 

Ciencias Empresariales 

Investigación de Operaciones 

7.4  Problema de la Ruta mas corta  7.5  Problema del Flujo máximo  7.6  Redes de Planeamiento  7.6.1 Proceso de Planificación por red  7.6.2 Representación de la red  7.7  CPM. y PERT  7.7.1 Representación de la red  7.7.2 La Ruta Crítica  7.7.3 Diferencias entre CPM y PERT 

V. 

METODOLOGÍA DE LA ENSEÑANZA 

La metodología que se empleará es de objetivos por unidad, con exposiciones teórico  prácticas;  apoyados  estos  por  material  visual  (  acetatos  )  preparado  para  la  interpretación  gráfica  de  los  diferentes  conceptos  desarrollados  en  clase.  Además  la  realización de trabajos de investigación individual y por grupos (desarrollo de ejercicios  prácticos), que permitan una mayor comprensión por parte del alumno.  VI. 

SISTEMA DE EVALUACIÓN  Materia tipo C ( Sistema Modular ) 

VII. 

Examen parcial 

40 puntos 

Actividad Académica 

20 puntos 

Examen final  TOTAL 

40 puntos  100 puntos 

BIBLIOGRAFÍA  BASICA:  1. 

Taha, Hamdy A., Investigación de Operaciones una introducción (Sexta  edición), Prentice Hall, 1998 

2. 

Terrazas  Pastor,  Rafael,  Modelos  Lineales  de  Optimización  (tercera  edición), Etreus Impresores , 2005 

3. 

Lieberman  Hiller,  Frederik,  Introducción  a  la  Investigación  de  Operaciones.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

6 

Ciencias Empresariales 

Investigación de Operaciones 

LAS ORIENTACIONES METODOLÓGICAS  1.  Introducción.  La  asignatura  de  Investigación  de  Operaciones  se  constituye  en  una  de  las  asignaturas  importantes dentro del ciclo profesional en el ámbito de las ciencias administrativas y de ingeniería,  esto  por  la  relación  de  coherencia  temática  que  presenta  con  otras  asignaturas  de  la  malla  curricular como Administración, Costos, Producción, Proyectos y específicamente con asignaturas  que  sirvan  de  base  para  la  toma  de  decisiones  en  los  distintos  niveles  de  las  Organizaciones  empresariales privadas y/o estatales.  La  resolución  de  sistemas  de  inecuaciones  y  las  operaciones  con  matrices,  además  de  los  conceptos básicos de administración, costos y producción son un requisito básico de conocimiento  previo para la asignatura de Investigación de Operaciones.  El  nivel  de  profundidad  y  complejidad  que  abarca  el  desarrollo  del  módulo  esta  enfocado  a  desarrollar competencias básicas y complementarias; en cuanto se refiere a la toma de decisiones,  proporcionando al estudiante los elementos científicos para el análisis, solución é interpretación de  problemas de aplicación práctica.  1.1. Objetivos Generales  Desarrollar  habilidades  cognitivas  desde  un  enfoque  científico  para  la  solución  de  problemas  relacionados con los distintos ámbitos de las organizaciones empresariales, encaminados éstos  a respaldar la toma de decisiones.  Desarrollar  las  capacidades  de  abstracción  y  síntesis  por  medio  de  la  aplicación  del  razonamiento  matemático  a  través  de  los  distintos  métodos  de  solución  de  problemas,  interpretación de resultados y toma de decisiones.  Los objetivos planteados están orientados a profundizar las siguientes competencias:  ·  Formular matemáticamente los problemas.  ·  Resolver problemas planteados matemáticamente.  ·  Analizar é interpretar los resultados obtenidos.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

7 

Ciencias Empresariales 

Investigación de Operaciones 

2.­ DESARROLLO.  2.1.­ NÚCLEOS TEMÁTICOS.  PRIMER ENCUENTRO  UNIDAD 1 INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES  Objetivos de la unidad:  ­ 

Analizar los orígenes, precursores y evolución de la Investigación de operaciones (I.O.). 

­ 

Conceptualizar y clasificar los distintos modelos matemáticos de optimización. 

­ 

Comprender y aplicar la metodología que emplea la I.O. para la solución de problemas  de optimización.  1.6  Introducción  1.7  Origen de la Investigación de Operaciones (I.O.)  1.8  Precursores y estudiosos de la I.O.  1.9  Noción, Concepto y alcance de la I.O.  1.10  Modelos matemáticos de decisión y su clasificación  1.5.1  Concepto de modelo  1.5.2  Clasificación de los modelos matemáticos de decisión  a) 

Modelos Determinísticos 

b)  c) 

Modelos Estocásticos (Probabilísticos)  Modelos Estáticos 

d)  Modelos Dinámicos  1.6  Metodología de la Investigación de Operaciones  1.7  Aplicaciones de la I.O.  1.8  Beneficios con la aplicación de la I.O.  UNIDAD 2: 

FORMULACIÓN DEL MODELO DE PROGRACMACIÓN LINEAL 

Objetivos de la unidad:  ­ 

Comprender  y  aplicar  el  procedimiento  para  formular  un  Modelo  de  Programación  Lineal (M.P.L.)

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

8 

Ciencias Empresariales 

­ 

Investigación de Operaciones 

Desarrollar  las  diferentes  formas  de  presentación  de  un  Modelo  de  Programación  Lineal (M.P.L.) 

2.5  Introducción  2.6  Concepto de Programación Lineal  2.7  Procedimiento para Formular un M.P.L.  2.3.1  Definición de Variables  2.3.2 Función Objetivo  2.3.3 Restricciones Estructurales o Funcionales  2.3.4 Restricciones de No negatividad  2.8  Formas de presentación de un M.P.L.  2.4.1  Formulación Canónica  2.4.2 Formulación Estándar  2.5  Planteamiento de los recursos por unidad de actividad  2.6  Problemas de aplicación  SÍNTESIS  En el desarrollo de las unidades 1 y 2 que corresponden al primer encuentro se presentan:  ·  Definiciones  y  conceptos  teóricos  relacionados  con  las  bases  de  la  Investigación  de  operaciones.  ·  El  análisis  de  las  etapas  de  formulación  de  un  Modelo  de  Programación  Lineal  y  sus  diferentes formas de presentación.  ·  Las  aplicaciones  prácticas  de  la  formulación  de  los  distintos  modelos  de  programación  lineal, paso a paso.  SEGUNDO ENCUENTRO  UNIDAD 3: 

SOLUCIÓN DEL MODELO DE PROGRAMACIÓN LINEAL 

Objetivos de la unidad:  ­  ­ 

Analizar, representar é interpretar el método gráfico para resolver un M.P.L.  Analizar la teoría del Método Simplex 

­ 

Aplicar los métodos de resolución Simplex, de las M’s y de las dos fases para determinar  la solución óptima.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

9 

Ciencias Empresariales 

Investigación de Operaciones 

3.5  Introducción  3.6  Método Gráfico  3.2.1  Fundamentos y mecánica del método gráfico  3.2.2  Región Factible (Solución Básica Factible)  3.2.3 Solución Óptima  3.2.4 Casos Especiales  3.7  Método Simplex  3.3.1 Teoría del Método Simplex  3.3.2 Definición Matricial del problema de P.L.  3.3.3 Planteamiento del Algoritmo Simplex  SINTESIS  En el desarrollo de los temas que corresponde  al segundo  encuentro presentan:  ·  Definiciones  de  las  distintas  características  que  presenta  los  métodos  de  solución  de  M.P.L.  ·  Los algoritmos de resolución de los distintos métodos (gráfico y analíticos)  ·  Aplicaciones de los métodos en formulados en las unidades 1 y 2.  TERCER ENCUENTRO  3.8  Solución Óptima del problema de P.L.  3.4.1 Método Simplex  3.4.2 Método de la M  3.4.3 Método de las Dos Fases  3.4.4 Casos Especiales  UNIDAD 4: 

TEORIA DE LA DUALIDAD 

Objetivos de la unidad:  ­  ­ 

Analizar y comprender la Teoría de la Dualidad.  Plantear y resolver problemas de P.L. mediante el método Dual­Simplex 

4.1  Introducción  4.2  Formulación matemática del problema Dual

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

10 

Ciencias Empresariales 

Investigación de Operaciones 

4.3  Comparación Primal ­ Dual  4.4  Interpretación Económica del problema Dual  4.5  Solución de problemas duales  4.5.1  Método Dual ­ Simplex  UNIDAD 5: 

ANALISIS DE SENSIBILIDAD 

Objetivos de la unidad:  ­ 

Analizar  y  aplicar  los  cambios  en  los  parámetros  y  determinar  como  afectan  en  los  resultados finales. 

­ 

Establecer controles y rangos de validez para las soluciones. 

5.1  Introducción  5.2  Cambios Discretos  5.2.1  Cambios en el vector b  5.2.2  Cambios en el vector c  5.2.3 Cambios en los coeficientes tecnológicos  5.3  Cambios Continuos  5.4.1 Cambios continuos en el vector b  5.4.2 Cambios continuos en el vector c  SINTESIS  En el desarrollo de los temas que corresponde  al tercer encuentro se presenta:  ·  La solución  de un M.P.L.  por  medio de los métodos  de  penalización  (método de  la M y  métodos de las dos fases)  ·  La formulación, análisis é interpretación del modelo dual y su interpretación económica.  ·  El análisis de sensibilidad, variando los recursos para obtener una nueva solución a partir  de la solución ya obtenida.  CUARTO ENCUENTRO  UNIDAD 6: 

MODELO DE TRANSPORTE Y ASIGNACIÓN 

Objetivos de la unidad:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

11 

Ciencias Empresariales 

Investigación de Operaciones 

­ 

Establecer é identificar los problemas de transporte de recursos. 

­ 

Analizar, formular y resolver problemas de transporte. 

­ 

Analizar, formular y resolver problemas de asignación de recursos 

6.5  Introducción  6.6  Problema de Transporte  6.6.1  El Modelo de Transporte  6.6.2  Algoritmo del Modelo de Transporte  6.6.3  Balanceo de problemas de transporte  6.7  Solución del Modelo de Transporte  6.3.1  Método de la Esquina Noroeste  6.3.2 Método de Aproximación de Vogel  6.3.3  Método del Costo Mínimo  6.8  Problema de Asignación  6.4.1  Formulación del modelo  6.3.2 Solución del modelo (Método Húngaro)  SINTESIS  En el desarrollo de los temas que corresponde  al cuarto encuentro se presenta:  ·  Definición y planteamiento del modelo de transporte y asignación.  ·  Aplicación de los métodos (M.E.N., M.C.M. y M.A.V.) para obtener una  solución básica  factible inicial.  ·  Optimización de la solución básica factible inicial, é interpretación de la solución óptima.  ·  Aplicaciones del modelo de asignación y transbordo.  METODOLOGIA DE ESTUDIO PARA EL ESTUDIANTE  La  sugerencia  metodológica  de  estudio  que  puede  conducirle  a  una  interesante  experiencia  de  aprendizaje en la asignatura, considera importante los siguientes principios:  1º  Lectura de las definiciones, conceptos y características de los algoritmos presentados en  el texto guía.  2º  Analizar los ejemplos resueltos en el texto guía, mediante la revisión y verificación de los  resultados.  3º 

Resolver  los  ejercicios  planteados,  que  se  encuentran  a  continuación  de  los  ejemplos 

resueltos.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

12 

Ciencias Empresariales 

Investigación de Operaciones 

Lectura de conceptos,  definiciones y  características de los  algoritmos  Leer, para estudio  comparativo  TAHA 

No 

Analizar, revisar y  verificarlos ejemplos  ¿Entendió los ejemplos  resueltos? 

Si 

Resolver tarea 

Asistir al encuentro del  día sábado. El docente  realizará las  aclaraciones y  profundizará el tema

NUCLEO TEMATICO PARA ESTUDIO INDEPEDIENTE  A través de interacción por plataforma (foro, tareas y chat) y clases practicas a acordar,  se  proporcionará  orientación  y  pautas    el  estudio  de  los  temas  que  contempla  este  núcleo  temático.  UNIDAD 7: 

TEORIA DE REDES 

Objetivos de la unidad:  ­ 

Establecer é identificar los problemas de optimización mediante la teoría de redes. 

­ 

Analizar, formular y resolver problemas de redes, aplicando los métodos de la ruta  más corta, el flujo máximo y árbol de extensión mínima. 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

13 

Ciencias Empresariales 

Investigación de Operaciones 

7.8  Introducción  7.9  Definición de Red  7.10  Problema del Árbol de extensión mínima  7.11  Problema de la Ruta mas corta  7.12  Problema del Flujo máximo  2.2.­ BIBLIOGRAFÍA COMENTADA  1.  El  Libro  de  texto  de  Investigación  de  Operaciones, cuyo  autor  es  el  Ing.  John  Walter  Soria  Martínez., es el resultado de siete años de interacción y experiencia continua en la enseñanza  de  las  matemáticas  y  de  la  ingeniería,  adecuándose  a  las  características  heterogéneas  de  conocimientos  previos  de  estudiantes  que  buscan  su  profesionalización  en  aulas  de  nuestra  Universidad.  Presenta  ejemplos  de  fácil  comprensión  y  aplicaciones  básicas  que  van  gradualmente  incrementando  su  complejidad  hasta  alcanzar  un  nivel  intermedio,  que  proporcionan  al  estudiante  bases  sólidas  que  le  permitan  alcanzar  un  mayor  logro  en  la  comprensión  de  los  temas.  2.  Terrazas  Pastor,  Rafael,  “ Modelos  Lineales  de  Optimización  (tercera  edición)” ,  Etreus  Impresores , 2005  Este  libro  sustenta  la  base  teórica  fundamental  de  la  asignatura,  proporcionando  de  manera  clara  los  esquemas  de  las  características,  algoritmos  y  ejemplos  que  presentan  los  distintos  temas considerados en el desarrollo de la asignatura.  3.  Taha,  Hamdy  A.,  “Investigación  de  Operaciones  una  introducción  (Sexta  edición)” ,  Prentice Hall, 1998  Este libro sustenta también la base teórica fundamental y nos proporciona parte de los ejemplos  que se desarrollan en la asignatura, además de ofrecernos el software “TORA” que nos permite  resolver los ejercicios haciendo uso de la computadora.  2.3.­ MATERIAL EXPLICATIVO

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

14 

Ciencias Empresariales 

Investigación de Operaciones 

El  texto  guía  incluye  ejercicios  de  aplicación  práctica,  con  un  nivel  básico  simple  que  gradualmente se incrementa su complejidad.  2.4.­EJEMPLIFICACIÓN  ·  Una aplicación práctica y relevante de la Investigación de Operaciones, específicamente  de la programación lineal es: Si suponemos que se producen tres productos (A, B y C)  en una fábrica, los cuales proporcionan utilidades diferentes (UA, UB y UC); conocemos  también que los recursos (Materia prima, Mano de obra, maquinaria, etc) disponibles son  limitados. También se tiene información respecto a la demanda máxima o mínima de los  tres productos.  ¿Usted  como  responsable  de  la  empresa  debe  decidir  cuantas  unidades  de  cada  producto (A, B y C) deben producirse para que su utilidad total sea máxima?  Análisis cualitativo del problema  Si bien en este tipo de problemas se pueden tomar decisiones respaldadas por la experiencia,  en muchos de los casos esas decisiones tienen un grado muy elevado de incertidumbre. Debido  a  que muchas de nuestras  decisiones pueden ocasionar grandes  pérdidas,  entonces  debemos  recurrir  a  la  aplicación  de  algunas  herramientas  científicas  que  nos  permitan  reducir  la  incertidumbre;  es  en  este  sentido  que  la  I.O.  nos  proporciona  métodos  y  técnicas  para  tomar  decisiones que tengan un menor grado de incertidumbre.  2.5.­ MÉTODOS A UTILIZAR  Encuentro físico  El docente realizará una evaluación diagnóstica cualitativa del núcleo temático correspondiente  al encuentro, por medio de preguntas y respuestas orales.  A través de exposición magistral consolidará los elementos más relevantes del núcleo temático;  así mismo, profundizará las extensiones de los temas tratados.  Planteará  ejemplos  representativos  que  contribuyan  a  la  comprensión  profunda  del  tema.  La  resolución de dichos ejemplos se realizará en forma grupal cooperativo o individual.  Encuentro virtual  El estudiante y  el  docente dispondrán de dos  sesiones  semanales,  cada sesión con tiempo  de  duración de dos horas  para interactuar mediante la plataforma (foro, tarea y chat).  El  docente  planteará  ejemplos  representativos  para  realizar  seguimiento  del  estudio  independiente  del  estudiante;  así  mismo,  responderá  a  las  consultas  de  los  estudiantes

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

15 

Ciencias Empresariales 

Investigación de Operaciones 

atendiendo dudas referentes al texto guía, las tareas y/o  prácticos planteados. 

3.­  CONCLUSIONES  La segunda unidad del texto Guía presenta un menú de ejercicios propuestos (práctico 1), las  unidades  3,  4  y 5  son  aplicadas  en  parte  del  grupo  de  ejercicios  del  práctico 1.Los ejercicios  propuestos  para  la  unidad  7,  serán  complementados  por  el  docente  durante  el  desarrollo  del  curso; los cuales  deberán ser resueltos  en  los  plazos y términos  señalados en  plataforma del  sistema.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

16 

Ciencias Empresariales 

Investigación de Operaciones 

UNIDAD 1 

INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES  1.1 

Intr oducción 

El término de Investigación de operaciones muy a menudo es asociado con la aplicación  de  técnicas matemáticas que permiten representar y  analizar por medio de un  modelo,  problemas reales que implican la toma de decisiones.  El  campo  de  estudio  de  la  I.O.  (llamada  también  Ciencia  de  la  Administración),  aparentemente  es  nuevo,  pero  éste  data  desde  la  segunda  guerra  mundial;  pero  su  impacto social es tremendo, contándose actualmente con aplicaciones que van desde el  aspecto  laboral  hasta  el plano  criminal,  pasando  por  los  sistemas de  salud,  transporte,  sistemas  financieros,  sistemas  de  comercialización,  pólución,  todos  los  ámbitos  de  la  Industria en general, además de otros.  En la actualidad la  I.O. no solo  se aplica en  los ámbitos privados,  si no  tambien en el  sector de los servicios públicos gubernamentales, tanto en los países desarrollados como  los  países  en  vías de  desarrollo;  alcanzando  una  presencia  relevante  debido  al  avance  tecnológico  en  el  desarrollo  de  los  computadores,  que  permiten  resolver  algoritmos  complejos.  1.2  Or igen de la Investigación de Oper aciones  En el siglo pasado, las organizaciones industriales de U.S.A. y el Reino Unido estaban  constituidas  por  un  número  reducido  de  empleados  los  que  ocupaban  espacios  muy  pequeños, los cuales eran dirigidos por una sola persona.  Todo este  panorama  cambia  en  el  periodo  de  la  Primera  revolución  industrial,  la  cuál  trajo consigo el desarrollo de la energía, las maquinarias y los equipos. Al mecanizarse  la  producción  ocurrió  la  segmentación  funcional  y  geográfica  de  la  administración;  consecuentemente  vino  la  división  del  trabajo  y  aparecieron  las  responsabilidades  de

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

17 

Ciencias Empresariales 

Investigación de Operaciones 

producción, finanzas, mercado, personal, ingeniería é investigación y desarrollo.  Específicamente se puede señalar que la I.O. surge durante la Segunda Guerra mundial,  con los intentos de asignar de manera óptima los recursos que contaban los frentes a las  operaciones militares. Posteriormente como resultado de la revolución industrial, ha ido  cobrando  cada  vez  mayor  importancia,  dado  el  crecimiento  y  la  complejidad  de  las  nuevas organizaciones.  Desde  un  principio  los  científicos  y  matemáticos  se  han  interesado  por  desarrollar  el  concepto  de  optimización,  intentado  encontrar  la  mejor  solución  a  un  determinado  problema; entonces podemos decir que la idea de optimizar proviene de la antigüedad,  donde  la  riqueza  de  las  naciones  ha  estado  determinada  por  su  capacidad  de  crear  y  utilizar bienes ú objetos que sean útiles al ser humano.  A partir del crecimiento industrial, la gestión y asignación óptima de los recursos a las  actividades  se  torna  mas  compleja  y  difícil;  ésta  necesidad  hace  que  se  encamine  la  búsqueda  de  un  instrumento  científico  más  eficiente  que  apoye  el  manejo  organizacional y sobre  todo que  ayude a una eficiente  y  eficaz toma de decisiones.  Es  en  este  contexto  que  la  investigación  de  operaciones  y  el  concepto  de  optimización  comienzan a jugar un rol muy importante en el mundo moderno.  Fue el doctor “George Dantzig” que el año 1947,  resumiendo los trabajos de muchos  de sus antecesores, reconoce la estructura matemática de muchos problemas de logística  militar y desarrolla el “método simplex”, lo cuál dio inicio a la programación lineal.  Finalmente  en  los  años  50,  la  optimización  y  la  investigación  de  operaciones  reciben  otro impulso con el advenimiento de la era espacial, donde los problemas de trayectoria  óptima  de  los  proyectiles,  son  tratados  a  través  de  la  programación  dinámica  y  el  principio  del  máximo;  extendiéndose  rápidamente  su  utilización  a  la  ingeniería  y  economía.  1.3 

Pr ecur sores y estudiosos de la Investigación de Oper aciones 

La  investigación  de  operaciones  ha  ido  evolucionando  y  desarrollándose  a  través  del  tiempo  gracias  al  aporte  realizado  por  muchos  estudiosos  y  científicos  que  se  han

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

18 

Ciencias Empresariales 

Investigación de Operaciones 

constituido en los precursores é impulsores de ésta fundamental herramienta. Entre los  precursores más importantes se pueden destacar a:  PRECURSORES Y ESTUDIOSOS DE LA INVESTIGACIÓN DE  OPERACIONES  PRECURSORES 

FECHA 

APORTE 

Lagrange 

1736 – 1813  Teoría de los multiplicadores 

Euler 

1703 – 1783  Cálculo de variaciones 

Gauss 

1777 – 1855 

Taylor 

1881 

Estudio de tiempos 

Gilbreth 

1885 

Estudio de movimientos 

Erlang 

1908 

Teoría de colas 

Brandeis 

1910 

Teoría de la administración científica 

Lanchester 

1915 

Simulación 

Kantarovich 

1930 – 1950 

Teoría de mínimos cuadrados y  La teoría del control 

Estudio sistemático del problema de  Asignación de recursos 

Dantzig 

1947 

Programación lineal 

Shannon 

1948 

Teoría de la información 

Bellman 

1955 

Programación dinámica 

Dantzig – Fulkerson – Jonson 

1955 

Redes de optimización 

Gomory – Land – Doig – Everreth  Von Neumann 

Programación entera  1974 

Teoría de juegos y dualidad 

Kuhn – Tucker 

Programación no lineal 

Rafia 

Análisis de decisiones 

Arrow – Karlin – Scarf ­ Whitin 

Inventarios 

Fuente: Modelos Lineales de Optimización (Rafael Terrazas P.) 

1.4 

Natur aleza y alcance de la Investigación de Oper aciones 

Para  poder  definir  la  Investigación  de  Operaciones,  es  necesario  analizar  cinco  elementos  importantes  y  esenciales  que  constituyen  la  esencia  de  la  I.O.,  estos  son:  Sistemas, Modelos, Optimización, Decisión y Método Científico.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

19 

Ciencias Empresariales 

Investigación de Operaciones 

ELEMENTOS ESENCIALES DE LA I.O.  SISTEMA 

MODELO 

METODO  CIENTIFICO 

DECISIÓN 

OPTIMIZACIÓN 

Si relacionamos  estos cinco  elementos desde un  enfoque del  Mundo  Real  y  el Mundo  Ideal, donde se hace una abstracción del Sistema, para luego de un proceso de análisis  encontrar soluciones óptimas a los problemas del mundo real  y  apoyar  con la  toma de  decisiones; se tiene el siguiente esquema: 

RELACION INTEGRAL ENTRE LOS ELEMENTOS  ESENCIALES DE LA I.O.  MUNDO REAL  IDEAL  SISTEMA  (Pr oblema) 

Intuición 

MUNDO  Por  Abstr acción 

MODELO  (Matemático)

METODO  CIENTIFICO 

Análisis 

DECISIÓN  (Acción a tomar ) 

OPTIMIZACIÓN  (Resultados)  Por  Inter pr etación 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

20 

Ciencias Empresariales 

1.5 

Investigación de Operaciones 

Concepto de la Investigación de Operaciones 

La  investigación  de  operaciones  (ó  Investigación  Operativa),  es  un  procedimiento  ó  enfoque que permite resolver problemas relacionados con la optimización y la toma de  decisiones en los diferentes campos de aplicación, tales como: la industria, la economía,  el comercio, la política, la educación, la salud, la defensa, etc.  En  conclusión  la  Investigación  de  oper aciones  es  la  aplicación  por  grupos  interdisciplinarios  del  método  científico  en  el  análisis  y  solución  de  problemas  relacionados con el control de las organizaciones del mundo real (Industria, economía,  comercio,  educación,  defensa,  etc);  que  deben  ser  concebidos  como  sistemas  y  entidades  complejas  que  manejas  recursos  (humanos,  materiales,  equipos,  útiles,  información,  etc).  Estos  sistemas  son  representados  en  el  mundo  ideal  por  modelos  matemáticos, cuyo  análisis  y  solución busca  la  optimización  de  resultados  que  deben  ser interpretados y comprometidos para ofrecer apoyo a la toma de decisiones.  1.6 

Modelos matemáticos de Decisión y su Clasificación 

1.6.1  Concepto de Modelo  Se  entiende  por  modelo  a  la  representación  simplificada  é  idealizada,  de  manera  cualitativa  o  cuantitativa  de  un sistema  real;  de  acuerdo  a  los objetivos de estudio  del  sistema.  En esencia un modelo es una imagen de un sistema, y en función a las interrogantes que  se plantean los sistemas pueden presentar diversos modelos.  La I.O. se centra en manejar Modelos Matemáticos que permitan interaccionar variables  (de entrada y salida) mediante relaciones funcionales y/o ecuaciones, de tal forma que la  solución del modelo permita encontrar la combinación óptima de resultados en cuanto a  las variables que intervienen.  1.6.2  Clasificación de  los Modelos matemáticos de decisión  La  I.O.  al  centrar  su  interés  en  los  modelos  matemáticos  de  decisión,  considera  la  siguiente clasificación de los mismos:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

21 

Ciencias Empresariales 

Investigación de Operaciones 

a)  Modelo  Estático: Es  aquel que  representa  a un sistema, de  manera que  las  variables  y  relaciones  funcionales, no  sufren  alteraciones  debido  a  cambios  en el tiempo.  b)  Modelo Dinámico: Es aquel que representa a un sistema, de manera que el  tiempo juega un rol muy importante.  c)  Modelos  Deter minísticos:  Son  aquellos  que  no  incluyen  propiedades  relacionadas con fenómenos aleatorios, como ser: La programación lineal, la  programación  entera,  el  modelo  de  transporte,  la  teoría  de  localización  o  redes, etc.  d)  Modelos Pr obabilísticos: Son  aquellos que incluyen variables o  relaciones  funcionales  que  dependen  de  fenómenos  aleatorios,  como  ser:  Las  cadenas  de  Markov,  la  teoría  de  juegos,  las  líneas  de  espera,  los  modelos  de  simulación, etc.  Las soluciones de los diferentes modelos pueden ser de tipo analítico o numérico. 

CLASIFICACIÓN DE LOS MODELOS  MATEMÁTICOS DE DESICIÓN  Estáticos  Dependencia con el  Tiempo 

Dinámicos  Determinísticos  MODELOS  MATEMÁTICOS 

Naturaleza de las  Variables 

Probabilísticos  Analíticos  Tipo de Solución  Numéricos

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

22 

Ciencias Empresariales 

Investigación de Operaciones 

Fuente: Modelos Lineales de Optimización (Rafael Terrazas P.) 

1.7  Metodología de la Investigación de Oper aciones  La  metodología  que  utiliza  la  I.O.  como  herramienta  para  resolver  problemas  sistémicos,  se  basa  en  la  metodología  científica  (propuesta  por  Sir  Francis  Bacon  en  1620), que consta de cuatro pasos, los cuales son:  1° 

Obser vación de un sistema físico 

2° 

For mulación de una Hipótesis (modelo matemático) 

3°  4° 

Pr edicción del comportamiento del sistema (obtención de soluciones)  Experimentación para probar la Validez de las hipótesis

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

23 

Ciencias Empresariales 

Investigación de Operaciones 

METODOLOGÍA DE LA INVESTIGACIÓN  DE OPERACIONES  Definición y For mulación del Pr oblema  Definición de los objetivos, alternativas y  escenarios 

Constr ucción del Modelo ( INPUT )  ( Modelo matemático )  Es la definición de una función económica  y sus restricciones 

OBSERVACIÓN 

F ORMULACIÓN 

Deducción de la Solución ( OUTPUT )  Hallar la Solución Óptima del modelo  ( Por medios analíticos y/o numéricos ) 

PREDICCIÓN 

Validación (Pr ueba) del modelo  Utilizar datos pasados  Permitiendo operar al modelo

Contr oles sobre la Solución  Interpretación de los resultados  (Análisis de Sensibilidad o cambios en parámetros) 

Implementación del Modelo  Toma de decisiones para la operación y  control del Modelo ­ Retroalimentación  Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

24 

Ciencias Empresariales 

Investigación de Operaciones 

Fuente: Modelos Lineales de Optimización (Rafael Terrazas P.) 

1.8 

Aplicaciones de algunos modelos de la I.O. ·  Pr ogramación Lineal: Tiene sus aplicaciones en problemas relacionados con la  optimización  de  mezclas,  manufacturación  de  productos,  recursos  humanos,  finanzas, mantenimiento de inventarios, marketing, etc. ·  Modelos  de  Transpor te:  Se  utiliza  cuando  un  producto  determinado  se  tiene  que  distribuir  desde  puntos  de  oferta  (orígenes)  hacia  punto  de  demanda  (destinos), donde se pretende encontrar un plan de distribución óptimo. ·  Modelos  de  Asignación:  Se  utiliza  para  diseñar  planes  de  asignación  de  recursos y trabajos óptimos. ·  Teor ía  de  Redes:  Es  muy  utilizado  en  la  planificación  y  programación  de  proyectos, programación de horarios, etc. ·  Pr ogramación  Entera:  Es  utilizado  en  el  estudio  para  la  localización  de  proyectos. ·  Pr ogramación Dinámica: Utilizado en la programación de etapas múltiples. ·  Sistema  de  Inventar ios:  Se  utiliza  en  el  manejo  y  almacenamiento  de  productos. ·  Modelos  de  Simulación:  Son  utilizados  cuando  se  tiene  dificultad  para  establecer relaciones analíticas aceptables desde el punto de vista computacional  o cuando el problema es netamente probabilístico. 

1.9 

Beneficios de la aplicación de un pr oyecto de I.O ·  Incr ementa  la  posibilidad  de  tomar   mejores  decisiones:  Generalmente  las  organizaciones que no aplican la I.O. en la toma de decisiones, éstas lo hacen de  forma  intuitiva,  ignorando  la  mayor  parte  de  las  veces  las  interrelaciones  que  existen entre cada uno de los componentes del sistema. ·  Mejora la coor dinación entr e los múltiples componentes de la organización:  La I.O. genera un nivel mayor de ordenamiento; es decir que logra integrar en su  estudio  el  mecanismo  de  coordinación,  para  evitar  que  los  componentes  del

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

25 

Ciencias Empresariales 

Investigación de Operaciones 

sistema aisladamente unos de otros. ·  Mejora  el  contr ol  del  sistema:  Al  establecer procedimientos  sistemáticos que  supervisan las operaciones que se llevan acabo en la organización. ·  Per mite  obtener   un  sistema  mejorado:  Al  lograr  que  éste  opere  con  costos  mas  bajos,  interaccionando  de  manera  mas  fluida;  a  demás  de  minimizar  los  cuellos  de  botella,  logrando  una  mejor  coordinación  entre  los  elementos  más  importantes del sistema.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

26 

Ciencias Empresariales 

Investigación de Operaciones 

UNIDAD 2 

FORMULACIÓN DEL MODELO DE PROGRAMACIÓN LINEAL 

2.1 

Intr oducción 

Uno  de  los  modelos  más  importantes  y  de  mayor  aplicación  en  la  I.O.  es  la  PROGRAMACIÓN  LINEAL;  siendo  ésta  técnica  del  modelado  matemático  diseñada  para  optimizar  el  empleo  de  recursos  limitados,  presentando  como  característica  principal el manejo de ecuaciones y relaciones funcionales de tipo lineal.  La  Programación  lineal  tiene  su  aplicación  práctica  en  cualquier  tipo  de  actividad  comercial  y/o  de  producción,  desde  la  publicidad,  planificación  de  la  producción,  finanzas y otros; buscando optimizar los ingresos, utilidades, costos, ventas, etc.  2.2  Concepto de Pr ogr amación Lineal  La P.L. es un modelo de programación matemática que busca lograr la mejor asignación  de  los  r ecur sos  limitados  (Restr icciones)  hacia  actividades  que  se  encuentran  en  competencia (Var iables de decisión), de tal forma que se pueda lograr la optimización  (Maximización  o  minimización)  de  una  función  económica  (Función  objetivo)  y  cuyo resultado servirá para apoyar una futura toma de decisión.  2.3  Pr ocedimiento para For mular  un M.P.L.  Luego  de  leer  el  enunciado  del  problema  las  veces  que  sean  necesarias  hasta  comprender  completamente;  se recomienda  seguir  en general  los siguientes pasos para  formular un Modelo de Programación Lineal.  2.3.1  Definición de Var iables  Son  la  base  fundamental  del  M.P.L.,  que  por  lo  general  son  identificados  una  vez  conocido  el  objetivo  (o  el  fin)  para  el  cual  está  diseñado  el  problema.  Es  muy  importante tomar en cuenta las unidades correspondientes a cada variable identificada,

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

27 

Ciencias Empresariales 

Investigación de Operaciones 

representándose por  x 1 ,  x 2  ,  x 3  ,...,  x n  Nota:  En muchos casos, identificar  y definir las variables de decisión es la etapa más  difícil;  pero  una  vez  que  se  definen  las  mismas,  el  resto  del  proceso  fluye  de  modo  natural.  2.3.2  Definición de la Función Objetivo  Se  debe  definir  la  ecuación  económica  que  debe  ser  optimizada  (maximizar  o  minimizar); siendo ésta ecuación la que cuantifica el valor máximo o mínimo, debiendo  estar  planteada  en  función  a  las  variables  de  decisión  identificadas  en  el  sistema.  Se  denota como: 

F . O . :  Optimizar 

Z  =  c 1 x 1  + c 2  x 2  + ...  + c n  x n 

Donde:  c n  = Coeficiente de costo o ganancia  2.3.3.  Restr icciones Estr uctur ales (o funcionales)  Son  ecuaciones  o  desigualdades  (=,  ≥  ó  ≤),  que  se  plantean  en  función    a  la  disponibilidad  de cada uno de  los  recursos  limitados con  los que  cuenta  una empresa;  por  ejemplo:  mano  de  obra,  materia  prima,  capital  de  operaciones,  sistemas  de  inventarios, etc. Las restricciones estructurales  se representan de la siguiente manera:

ìa 11 x 1  ± a 12 x 2  ± ... ± a 1 n x n  £ = ³ b 1  ¬ R 1  ïa  x  ± a  x  ± ... ± a  x  £ = ³ b  ¬ R  ï 2 n  n  2  2  Sujeto a ( s.  a .) :  í 21  1  22  2  M M M M ï M  ïîa m 1 x 1  ± a m 2 x 2  ± ... ± a mn x n  £ = ³ b m  ¬ R m  Donde:  a  mn  =  Cantidades que se consumen en cada actividad 

b m 

=  Disponibilidad o requerimiento de los recursos (lados derechos) 

R m 

=  Restricciones estructurales o funcionales

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

28 

Ciencias Empresariales 

Investigación de Operaciones 

2.3.4  Restr icciones de No Negatividad  Todas  las  variables  de  decisión  identificadas  en  un  sistema,  no  deben  asumir  valores  negativos en el resultado final; es decir: 

No  negativos  :  x 1 , x 2 ,...,  x n  ³  0  Ejemplo: Proceso de formulación del Modelo de Programación Lineal  El banco Ganadero dispone de 18 millones de dólares para ofrecer préstamos  de riesgo  alto  y  riesgo  medio,  cuyos  rendimientos  son  del  14%  y  7%  respectivamente;  por  otro  lado  se  conoce  que  se  debe  dedicar  al  menos  4  millones  de  dólares  a  préstamos  de  riesgo  medio  y  que  el dinero  invertido  en  alto  y  medio  riesgo  debe  estar  a  lo  sumo  a  razón  de 4  a 5.  Formular  un  M.P.L.  que  permita determinar  ¿cuánto debe dedicarse  a  cada uno de los tipos de préstamos para maximizar el beneficio?  Var iables de decisión x 1  =  Cantidad de dinero dedicada a préstamos de riesgo alto [millones de $us] x 2  =  Cantidad de dinero dedicada a préstamos de riesgo medio [millones de $us] 

Función Objetivo 

F .O    . :  Max .  z  = 0 . 14 x 1  + 0 . 07 x 2  [millones de $us.]  Restr icciones Estr uctur ales

ì x 1  +  x 2  £ 18  [ millones  de $ us .]  ï Sujeto  a  (s . a . ) :  í x 2  ³ 4  [ millones  de $ us .]  ï5 x  - 4 x  £ 0  [ millones  de $ us .]  2  î 1  Restr icciones de No Negatividad 

No negativos :  x 1 ; x 2  ³ 0 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

29 

Ciencias Empresariales 

2.4 

Investigación de Operaciones 

Planteamiento de los recur sos por  unidad de actividad 

Suponiendo que se tiene un número “m” de recursos limitados que se pueden asignar a  un número “n” de actividades. La estructura que muestra el siguiente cuadro,  proporciona los elementos necesarios (datos) para que un M.P.L. maneje la asignación  de recursos por unidad de actividad: 

Recur sos 

1  2  M 

m  Contr ibución a Z por  

Actividad 

Cantidad de r ecur sos 

1        2        3…….. …n  

disponibles 

a  11  a 12  ...  a 1 n  a 21  a 22  ...  a 2 n  M  M M a m 1  a m 2  ...  a mn 

b 1  b 2 

c 1 

c 2 

... 

M 

b n 

c n 

unidad de actividad   Donde:  Recursos disponibles  : i  =  1 , 2 ,...,  m 

; 

Actividades  : j  =  1 , 2 ,...,  n 

Z  : Función objetivo que debe maximizarse o minimizarse 

x j  : Nivel de actividad j (Variable de decisión)  c j  : Coeficiente costo o ganancia para la actividad j­ésima (parámetro)  a  ij  : Cantidad del recurso i que consume cada unidad de la actividad j   b i  : Cantidad disponible del recurso i para asignar a las actividades j  2.5 

For mas de pr esentación de un M.P.L. 

2.5.1  For mulación canónica  La formulación canónica tiene las siguientes características: ·  La función objetivo es Maximizar ·  Las restricciones estructurales son del tipo “menor o igual que” ( ≤ ) ·  Las variables de decisión son mayores o iguales a cero ( ≥ )  Ejemplo: 

F .O    . :  Max .  z  = 2 x 1  + 3 x 2 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

30 

Ciencias Empresariales 

Investigación de Operaciones 

ì x 1  +  x 2  £ 3  î5 x 1  - 4 x 2  £ 2 

S . a . :  í

No negativos :  x 1 ³ 0 ;  x 2  ³ 0  2.5.2  For mulación Mixta  La formulación mixta tiene las siguientes características: ·  La función objetivo es Maximizar o Minimizar ·  Las restricciones estructurales son “menor  o igual” o “mayor  o igual”  ( ≤ o ≥  ) ·  Las variables de decisión son mayores o iguales a cero ( ≥ )  Ejemplo: 

F .O    . :  Min .  z  = x 1  + 4 x 2  + 2 x 3  ì x 1  + 5 x 2  + 4 x 3  £ 9  î 3 x 1  + 2 x 2  + x 3  ³ 1 

S . a . :  í

No negativos :  x 1 ;  x 2  ;  x 3  ³ 0  2.5.3  For mulación Estandar   La formulación estandar tiene las siguientes características: ·  La función objetivo es Maximizar o Minimizar ·  Las restricciones estructurales son del tipo “igual que” ( = ) ·  Las variables de decisión son mayores o iguales a cero ( ≥ ) ·  Los elementos del lado derecho de cada ecuación son positivos  Ejemplo: 

F .O    . :  Max .  z  = 2 x 1  + 3 x 2  + 0 h 1  - 0 s 2  = 3  ì x 1  +  x 2  + h 1  ï S . a . :  í5 x 1  + 4 x 2  - s 2  = 2  ï 2 x  + x  = 4  2  î 1 

No  negativos :  x 1 ;  x 2  ; h 1  ; s 2  ³ 0  2.6 

EJ ERCICIOS DE FORMULACIÓN

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

31

Ciencias Empresariales 

Investigación de Operaciones 

PROBLEMA DE UN TALLER DE CARPINTERIA  Supongamos  que  un  taller  de  carpintería  dispone  de  determinadas  piezas  para  la  elaboración  de  dos  productos  finales.  El  taller  dispone  de  8  “piezas  pequeñas”  y  6  1) 

“piezas grandes”, que son utilizadas para elaborar sillas (usando 2 piezas pequeñas y 1  pieza grande) y mesas (usando 2 piezas de cada tipo). Nos interesa decidir cuántas sillas  y mesas se debe fabricar de modo que se obtenga la máxima utilidad, dado que se tiene  un beneficio neto de $us. 15 por cada silla y de $us. 20 por cada mesa fabricada.  FORMULACIÓN:  Primero  identificamos  cuales  son  los  recursos  con  los  que  se  dispone y cuales son las actividades que deben realizar  RECURSOS  Piezas pequeñas 

ACTIVIDADES  Fabricar sillas 

Piezas grandes 

Fabricar mesas 

Recursos 

Piezas por unidad de  Disponobilidad  de piezas  Sillas  Mesas 

Piezas pequeñas [ Pza. / u ]  Piezas grandes [ Pza. / u ] 

2  1 

2  2 

Utilidad  [ $us. / u ] 

15 

20 

1º 

8  [ Pzas. ]  6    [ Pzas. ] 

Var iables de decisión x 1  =  Número de sillas a fabricar [ u. ] x 2  =  Número de mesas a fabricar [ u. ] 

2º 

Función Objetivo 

F . O . :  Max .  z  = 15 x 1  + 20 x 2  [ $us .]  é $us. ù é $us.  ù ê u  * u ú + ê u  * u ú = [$us. ]  ë û ë û

3º 

Restr icciones Estr uctur ales

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

32 

Ciencias Empresariales 

Investigación de Operaciones 

Pzas. pequeñas :  2 x 1 + 2  x 2  £ 8  Pzas . grandes  :  x 1  + 2  x 2  £ 6  é Pzas. ù é Pzas.  ù ê u  * u ú + ê u  * u ú = [Pzas. ]  ë û ë û 4º 

Restr icciones de No Negatividad 

No  negativos :  x 1 ³ 0 ;  x 2  ³ 0  Resumen: 

F . O . :  Max .  z  = 15 x 1  + 20 x 2  [ $us .]  ì 2  x 1  + 2  x 2  £ 8  î x 1  + 2  x 2  £ 6 

S . a . : í

No negativos :  x 1 ³ 0 ;  x 2  ³ 0  2) 

PROBLEMA DE MEZCLAS (EMPRESA MONOPOL) 

La  empresa  de pinturas  MONOPOL, produce pinturas  tanto para interiores como para  exteriores, a partir de dos materias primas M1 y M2. La siguiente tabla proporciona los  datos básicos del problema: 

Materia Prima 

Toneladas de Materia Prima 

Disponibilidad 

por tonelada de Pintura para 

Máxima Diaria 

Exteriores 

Interiores 

(Toneladas) 

M1 

6 

4 

24 

M2 

1 

2 

6 

5 

4

Utilidad por Tonelada  (1000 $us.) 

Una encuesta de mercado restringe la demanda máxima diaria de pintura para interiores  a 2 toneladas. Además, la demanda diaria de pintura para interiores no puede exceder a  la  pintura  para  exteriores  por  más  de  1  tonelada.  La  empresa  MONOPOL  quiere  determinar  la  mezcla  de  productos  óptima  de  pintura  para  interiores  y  para  exteriores 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

33 

Ciencias Empresariales 

Investigación de Operaciones 

que maximice la utilidad total diaria.  FORMULACIÓN:  En  este  caso  no  es  necesario  el  cuadro  de  disponibilidad  de  recursos y actividades, ya que en el planteamiento del problema se tiene como datos.  RECURSOS  Materia prima M1 

ACTIVIDADES  Producir pintura para exteriores 

Materia prima M2  Restricciones de Demanda 

Producir pintura para interiores 

1º 

Var iables de decisión x 1  =  Cantidad de pintura para exteriores a producir [ Tn. / día  ] x 2  =  Cantidad de pintura para interiores a producir [ Tn. / día  ] 

2º 

Función Objetivo 

F .O    . :  Max .  z  = 5 x 1  + 4 x 2  é Miles $us.  Tn ù é Miles $us.  Tn ù é Miles $us. ù ê Tn .  * día ú + ê Tn .  * día ú = ê día  ú ë û ë û ë û

3º 

Restr icciones Estr uctur ales  Materia prima M1: 

6  x1 +  4  x 2  £ 24 

é Tn.  M 1  Tn  ù é Tn.  M 1  Tn  ù é Tn.  M 1 ù ê Tn .  *  día  ú + ê Tn .  *  día  ú = ê día  ú ë û ë û ë û

Materia prima M2: 

x1 +  2  x 2  £ 6 

é Tn.  M  2  Tn  ù é Tn.  M  2  Tn  ù é Tn.  M  2 ù ê Tn .  *  día  ú + ê Tn .  *  día  ú = ê día  ú ë û ë û ë û

Relación de Demanda:  Demanda de pintura p/ext.: 

4º 

x 2 £  x 1  + 1 

é Tn .  ù día úû êë

x 2 £  2 

é Tn .  ù êë día úû

Restr icciones de No Negatividad 

No negativos  :  x 1 ³  0  ;  x 2  ³ 0 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

34 

Ciencias Empresariales 

Resumen:

Investigación de Operaciones 

F  . O . :  Max .  z  = 5 x 1 + 4 x 2  [Miles $us . / día ]  ì 6 x 1  +  4 x 2  ï ï x 1  + 2 x 2  S . a . :  í ï - x 1  + x 2  ïî x 2 

£ 24  £

6 

£

1 

£

2 

No  negativos  :  x 1 ³  0  ;  x 2  ³ 0  3)  PROBLEMA DE LA DIETA  Una persona debe cumplir una dieta que le exige consumir por semana al menos 1 Kg.  de carbohidratos y ½ Kg. de proteínas. Para ello cuenta con dos tipos de alimentos (A) y  (B)  que  están  constituídos  exclusivamente  por  carbohidratos  y  proteínas.  El  alimento  tipo (A) contiene 90% (en peso) de carbohidratos y el resto de proteínas, mientras que el  alimento tipo (B) contiene 60% de carbohidratos y el resto de proteínas; se sabe que el  alimento tipo (A) cuesta 20 $us. / Kg. y el alimento tipo (B) 40 $us. / Kg.  ¿Qué  cantidad  de  cada  alimento  deberá  consumir  la  persona  para  que  el  costo  de  su  dieta sea mínimo?  NUTRIENTES  Carbohidratos  Proteínas 

Nutrientes 

ALIMENTOS  Tipo (A)  Tipo (B)  Kg. de alimentos  Tipo (A)  Tipo (B) 

Requerimiento  Mínimo 

Carbohidratos [ Kg. carb. / Kg. ] 

0.9 

0.6 

1  [ Kg. carb. / sem. ] 

Proteínas [ Kg. prot.  / Kg. ] 

0.1 

0.4 

0.5 [ Kg. prot. / sem. ] 

20 

40 

Costo  [ $us. / Kg. ]  1º 

Var iables de decisión x 1  =  Cantidad de alimento tipo (A) a consumir [ Kg. / sem. ] x 2  =  Cantidad de alimento tipo (B) a consumir [ Kg. / sem. ] 

2º 

Función Objetivo 

F . O . :  Min .  z  = 20 x 1  + 40 x 2  [ $us . / sem .] 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

35 

Ciencias Empresariales 

Investigación de Operaciones 

é $us.  Kg . ù é $us.  Kg . ù é $us. ù * * ê ú+ê ú=ê ú ë Kg .  sem . û ë Kg .  sem . û ë sem . û

3º 

Restr icciones Estr uctur ales 

Carbohidratos : 

0 . 9 x1 + 0 . 6  x 2  ³ 1 

é Kg. carb .  Kg . ù é Kg. carb .  Kg . ù é Kg. carb . ù *  + *  = ê sem . úû êë Kg .  sem . úû êë sem .  úû ë Kg . 

Proteínas 

: 

0 . 1 x1 + 0 . 4  x 2  ³ 0 . 5 

é Kg. prot .  Kg . ù é Kg. prot .  Kg . ù é Kg. prot . ù *  + *  = ê sem . úû êë Kg .  sem . úû êë sem .  úû ë Kg . 

4º 

Restr icciones de No Negatividad 

No negativos :  x 1 ³ 0 ;  x 2  ³ 0  Resumen: 

F . O . :  Min .  z  = 20 x 1  + 40 x 2  [ $us . / sem .]  ì 0 . 9  x 1  + 0 . 6  x 2  ³ 1  î 0 . 1 x 1  + 0 . 4  x 2  ³ 0 . 5 

S . a . : í

No  negativos  :  x 1 ³  0  ;  x 2  ³ 0  4)  PROBLEMA DE INVERSIONES FINANCIERAS (BANCO BISA)  El Banco BISA tiene un capital de 500000 $us. para invertir en dos tipos de acciones A  y  B.  El  tipo  A  tiene  bastante  riesgo  siendo  el  interés  anual  del  10%  y  el  tipo  B  es  bastante  seguro  con  un  interés  anual  del  7%.  La  política  de  inversiones  del  banco  considera invertir como máximo 300000  $us. en  las acciones con bastante riesgo (tipo  A)  y  como  mínimo  100000  $us.  en  las  acciones  mas  seguras  (tipo  B),  además  por  regulaciones  del  mercado  el  banco  debe  invertir  en  las  acciones  tipo  A  por  lo  menos  tanto  como  en  las  del  tipo  B.  ¿Usted  como  gerente  comercial  de  valores  del  banco  deberá  proponer  al  directorio  cómo  invertir  los  500000  $us.  para  maximizar  sus  intereses anuales?

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

36

Ciencias Empresariales 

Investigación de Operaciones 

CONDICIONES DE INVERSION  Inversión de Capital 

Tipo (A) 

Políticas de inversión 

Tipo (B)  Inversión en acciones 

Condiciones de  Inversión en $us. 

1º 

INVERSION EN ACCIONES 

Límites de  Inversión en $us. 

Tipo (A) 

Tipo (B) 

Inversión de Capital 

1 

1 

500000 

Inv. Acciones Tipo (A) 

1 

― 

300000 

Inv. Acciones Tipo (B) 

― 

1 

100000 

Interés anual  [ % ] 

10 

7 

Var iables de decisión x 1  =  Monto de dinero a invertir en acciones tipo (A) [ $us.] x 2  =  Monto de dinero a invertir en acciones tipo (B) [ $us.] 

2º 

Función Objetivo 

F . O . :  Max .  z  = 0 . 1 x 1  + 0 . 07 x 2  [ $us .]  3º 

Restr icciones Estr uctur ales  :

x1  +  x 2  £ 500000  [$us . ] 

Inv. Acciones Tipo (A):

x1  £ 300000  [$us . ] 

Inv. Acciones Tipo (B):

x2  ³ 100000  [$us . ] 

Relacion de inversión  :

x1  ³  x 2 

Inversión de capital 

4º 

[$us . ] 

Restr icciones de No Negatividad 

No  negativos :  x 1 ³ 0 ;  x 2  ³ 0  Resumen: 

F . O . :  Max .  z  = 0 . 1 x 1  + 0 . 07 x 2  [ $us .] 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

37 

Ciencias Empresariales 

Investigación de Operaciones 

ì x 1  +  x 2  £ 500000  ï £ 300000  ï x  S . a . : í 1  x 2  ³ 100000  ï ïî x 1  - x 2  ³ 0  No  negativos  :  x 1 ³  0  ;  x 2  ³ 0  2.7 

EJ ERCICIOS PROPUESTOS (PRACTICO Nº 1) 

1.  La  empresa  de  confecciones  “IMAGEN”  produce  camisas  y  trajes  de  vestir  para  varones.  Cada  camisa  requiere  2  hrs.  Hombre  y  1  hora  de  maquinado;  cada  traje  requiere 10 hrs. Hombre y 4 horas de maquinado. Para la confección de una camisa  se  requiere  1  metro  de  tela  y  para  un  traje  3  metros  de  tela.  Ambas  telas  son  diferentes.  Se dispone  semanalmente de 80  metros  de tela para camisa  y  90  metros  de tela para trajes.  Se  trabaja 5 días  a  la semana  con 10 operarios y 4 maquinas de  costura. Las utilidades son: 20 Bs. / camisa y 80 Bs. / traje. Cual es el mejor plan de  producción para la empresa.  2.  Un  agropecuario  tiene  20  hectáreas  de  tierra  en  el  norte  que  piensa  sembrar  la  próxima temporada. No ha podido decidir que sembrar porque tiene limitaciones con  el dinero y el personal. Para sembrar arroz los gastos son 4500 Bs./ha. y se requiere  80 hrs.– hombre/ha.; para sembrar maíz se requiere 3800 Bs./ha. y 85 hrs. – hombre /  ha.  el  agropecuario  cuenta con  85000  Bs.  para  cubrir  los  gastos de  producción  y  3  personas que  trabajan durante 60 días hábiles, 10  hrs. diarias.  Por cada  hectárea  de  maíz se gana 5000 Bs. y por cada ha. de arroz se gana 5800 Bs. Formular un modelo  para decidir el uso de la tierra y los recursos.  3.  Un nutricionista desea controlar la cantidad de grasa de los alimentos que consumen  los enfermos en el “HOSPITAL J APONES”. Todas las comidas deben tener 5 % o  menos  de  grasa.  El  plato  del  día  consiste  en  arroz  y  pollo.  El  pollo  tiene  12  %  de  grasa y el arroz 1 %. Cada enfermo consume un total de 400 gramos de alimento en  el  almuerzo.  El  kilo  de  pollo  preparado  cuesta  11  Bs.  y  el  arroz  preparado  con  verduras  cuesta  12  Bs.  Determinar  la  cantidad  optima  de  arroz  y  pollo  que  debe  servirse a cada enfermo a un costo mínimo.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

38

Ciencias Empresariales 

Investigación de Operaciones 

4.  Un agricultor posee 200 cerdos que consumen 90 libras de comida especial todo los  días. El alimento se prepara con las siguientes composiciones:  ALIMENTO 

CALCIO  PROTEINA  FIBRA 

COSTO ($US. / LB.) 

Maíz 

0.001 

0.09 

0.02 

0.20 

Harina de Soya (Lb.) 

0.002 

0.60 

0.06 

0.60 

Determine  la  mezcla  de  alimento  con  el  mínimo  costo  por  día,  si  los  requisitos  diarios de alimento para los cerdos son:  a)  Cuando menos 0.1 % de calcio  b)  Por lo menos 30 % de proteínas  c)  Máximo 5 % de fibra  5.  La  empresa  de confecciones  “ROMY”  fabrica  ropa  industrial:  camisas  y  overoles  para  las  diferentes  empresas.  Cada  camisa  requiere  2  hrs.–hombre  y  cada  overol  requieren 10 hrs.– hombre. Para la confección de una camisa se requiere 1 metro de  tela  y  para  un  overol  3  metros  de  tela.  Ambas  telas  son  diferentes.  Se  dispone  semanalmente de 120 metros de tela para camisas y 300 metros de tela para overoles.  Se trabaja 5 días a la semana con 10 operarios. Las utilidades son de 20 Bs. / camisa  y 80 Bs. / overol. ¿Cuál es el mejor plan de producción para la empresa?.  6.  Muebles  “HURTADO”  fabrica  3  clases  de sillones  cada  una  requiere  una  técnica  diferente de fabricación. El sillón de lujo requiere 35 hrs. de mano de obra, 9 hrs. de  maquinado  y  produce una utilidad de 25 $us.; el  sillón estándar  requiere 30 hrs.  de  mano  de  obra,  7  hrs.  de  maquinado  y  produce  una  utilidad  de  20  $us.;  el  sillón  económico  requiere 25 hrs. de mano de obra,  5 horas de  maquinado y produce una  utilidad de 12 $us. Se dispone 1800 hrs. de mano de obra y 450 hrs. de maquinado  cada mes. La demanda mensual llega máximo 20 und. para los modelos de lujo y 25  para  los  modelos  estándar.  Formule  un  modelo  para  determinar  el  mejor  plan  de  producción.  7.  La  empresa  “K­RROS”  fabrica  dos  modelos  de  carritos  a  motor  para  niños,  utilizando como materia prima el hierro y la madera, para lo cual se destina 28 hrs.  en  fabricar  una  und.  del  modelo  estándar  y  16  hrs.  para  el  modelo  sencillo.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

39 

Ciencias Empresariales 

Investigación de Operaciones 

Actualmente  se  tiene  disponible  7200  hrs.  para  la  producción  de  estos  modelos.  Existe un pedido de 16 und. del modelo sencillo. En el siguiente cuadro se detalla los  insumos e ingresos para cada modelo:  MODELO 

HIERRO  MADERA  REQUISITOS  (Lb.) 

(m 2 ) 

DE MOTOR 

Sencillo 

950 

65 

Estándar 

4000  645300 

Disponibilidad 

COSTO  PRECIO  UNITARIO  DE VENTA  (Bs.) 

(Bs.) 

1 

1010 

1460 

120 

1 

1205 

2100 

22790 

450 

Elaborar  un  modelo  de  Programación  Lineal  para  determinar  el  mejor  plan  de  producción.  8.  La compañía de investigaciones “EL PAHUICHI”  tiene un capital de 10 millones  de  $us.  para  invertir.  El  objetivo  principal  consiste  en  maximizar  el  retorno  de  la  inversión para el próximo año.  Existen 4 alternativas  de  inversión según el cuadro.  Se ha establecido que por lo menos el 30 % deberá ser colocado en las alternativas 1  y 2, no más del 40 % en las alternativas 3 y 4. Se debe invertir todo los 10 millones  disponibles.  Formular  un  modelo  de  Programación  Lineal  que  permita  estimar  la  cantidad de dinero a invertir en cada alternativa.  N° 

ALTERNATIVA DE  INVERSION 

RETORNO  ESPERADO (% ) 

INVERSION MAXIMA  (MILLONES $US.) 

1 

Vivienda tipo Chalet 

6 

7 

2 

Vivienda Semi Lujo 

8 

5 

3 

Vivienda Sencilla 

9 

4 

4 

Lotes 

12 

2 

9.  María  requiere  regular  su  alineación,  actualmente  dispone  los siguientes  alimentos  para consumo: torta de chocolate, helado de chocolate, soda coca­cola, empanada de  queso.  Cada  porción  de  torta  cuesta  3  Bs.,  el  vaso  de  helado  cuesta  4  Bs.,  cada  botella de soda personal cuesta  3 Bs. y cada empanada cuesta 1 Bs. Cada  día debe  ingerir por lo menos 50 calorías, 6 onzas de chocolate, 12 onzas de azúcar y 8 onzas  de  grasa.  El  contenido  nutritivo  por  unidad  de  cada  alimento  se  muestra  en  la  siguiente tabla:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

40 

Ciencias Empresariales 

Investigación de Operaciones 

ALIMENTO  CALORIAS 

CHOCOLATE 

AZUCAR 

GRASA 

(ONZAS) 

(ONZAS) 

(ONZAS) 

Torta 

40 

3 

4 

2 

Helado 

20 

2 

4 

2 

Soda 

15 

0 

3 

0 

Empanada 

50 

0 

2 

3 

Formular  un  modelo  lineal  que  permita  responder  a  los  requerimientos  alimenticios diarios a un costo mínimo.  10. El  gerente  de  personal  de  la  empresa  de  seguridad  “LIDER”  debe  elaborar  un  programa  de  vigilancia  de  modo  que  se  satisfagan  los  requerimientos  que  se  muestran en el Cuadro Nº 1. Los guardias trabajan turnos de 8 hrs., todos los días hay  6 turnos. En él Cuadro Nº 2, se dan los horarios de entrada y salida de cada turno. El  gerente  de  personal  de  dicha  empresa  quiere  determinar  cuantos  guardias  deberán  trabajar  en  cada  turno  con  el  objeto  de  minimizar  él  número  total  de  guardias  que  satisfaga los requerimientos de personal.  CUADRO Nº 1 

CUADRO Nº 2 

REQUERIMIENTO DE PERSONAL  TURNOS 

PROGRAMACION 

DE 

N°  TIEMPO 

MINIMO  DE  GUARDIAS 

Media noche  → 4 am. 

5 

4 am. 

→ 8 am. 

7 

8 am. 

Medio día 

15 

Medio día 

→ 4 pm. 

7 

4 pm. 

→ 8 pm. 

12 

8 pm. 

Media noche 

9

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

41 

TURNO  Ciencias Empresariales 

UNIDAD 3 

MÉTODOS DE SOLUCIÓN DE UN 

HORA  ENTRADA – SALIDA 

1 

Investigación de Operaciones  Media noche  → 8 am. 

2 

4 am. 

Medio día 

3 

8 am. 

→ 4 pm. 

4 

Medio día 

→ 8 pm. 

5 

4 pm. 

Media noche 

6 

8 pm. 

→ 4 am.

M.P.L.  El objetivo de esta unidad es estudiar los métodos de solución y las propiedades que son  propias  de  la  solución  de  un  M.P.L.;  que  pueden  determinarse  de  forma  gráfica  y/o  analítica. Existen  varios métodos que permiten  llegar a la  solución de  un problema  de  programación lineal, entre los cuales tenemos a los métodos:  a) 

Método Gráfico 

b) 

Método Simplex 

c) 

Métodos de Penalización 

a)  ALGORITMO DEL MÉTODO GRÁFICO  Es uno de los métodos más simples, que tiene 2 características especiales:  i) 

Solo sirve para resolver problemas en dos dimensiones (a lo sumo tres). 

ii) 

La  aplicación  y  solución  mediante  este  método,  permite  importantes  interpretaciones de tipo geométrico y conceptual en relación a la teoría de la  P.L. 

PROCEDIMIENTO:  Paso 1:  M.P.L. 

Graficar  en un sistema de coordenadas cada una de las restricciones del 

Paso 2: 

Reemplazar  un  punto  por  encima  y  por  debajo  de  la  recta,  para 

determinar el sentido que indica la desigualdad.  Paso 3: 

La intersección de todas las rectas y el dominio de las restricciones con el 

primer cuadrante del sistema de coordenadas, daran lugar a la formación de 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

42 

Ciencias Empresariales 

Investigación de Operaciones 

un conjunto o espacio solución denominado REGIÓN F ACTIBLE   Paso 4: Graficar la F UNCIÓN OBJ ETIVO,  reemplazando  con un  valor arbitrario  la función objetivo Z  Paso 5:  Para  hallar  la  Solución  Óptima,  se  desplazará  paralelamente  la  recta  Z  obtenida en el paso 4, hasta intersectar con un punto de intersección de las  restricciones; esto según:  a)  Si  se trata  de Maximizar, se debe  encontrar el punto más alejado del 

origen.  b)  Si  se  trata  de  Minimizar ,  se  debe  encontrar el  punto  más cercano al 

origen .  Paso 6: Interpretar los resultados obtenidos  a.1) 

INTERPRETACION DE LA SOLUCIÓN GRÁFICA  Solución  Óptima:  Son  los  valores  de  las  variables  y  el  valor  de  la  función 

objetivo Restr icciones  Activas: Son  aquellas que pasan por  el punto óptimo  y  hacen uso  total de los recursos  Restr icciones Inactivas: Son aquellas que no pasan por el punto óptimo, pero sí  delimitan la región factible y hacen uso parcial de los recursos.  Restr icciones Redundantes: Son aquellas que no delimitan la región factible, por  lo tanto no influyen en la solución óptima.  EJ EMPLOS:  1)  Aplicar  el  algoritmo  del  método  gráfico  para  resolver  el  problema  del  taller  de  carpintería, cuyo modelo de programación lineal formulado es: 

F . O . :  Max .  z  = 15 x 1  + 20 x 2  [ $us .] 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

43 

Ciencias Empresariales 

Investigación de Operaciones 

  Pzas .  pequeñas  ì 2  x 1  + 2  x 2  £ 8  K R1  î x 1  + 2  x 2  £ 6  K R 2  Pzas .  grandes 

S . a . : í

No negativos :  x 1 ³ 0 ;  x 2  ³ 0  Donde: x 1  =  Número de sillas a fabricar [ u. ] x 2  =  Número de mesas a fabricar [ u. ] 

SOLUCIÓN GRÁFICA ·  Primeramente  las  restricciones  (desigualdades)  las  representamos  como  igualdades  solo  para  poder  encontrar  los  puntos  que  nos  permitan  trazar  las  rectas  que  representan a las restricciones en un sistema cartesiano. 

R1  : 2 x 1  + 2 x 2  = 8 

R 2 :  x 1  +  2 x 2  = 6 

x1  =  0 Þ x 2  = 4  ® P 1 ( 0 , 4 )  x 2  = 0 Þ x 1  = 4  ® P 2 ( 4 , 0 )  x1  = 0 Þ x 2  = 3 ® P 1 ( 0 , 3 )  x 2  = 0 Þ x 1  = 6  ® P 2 ( 6 , 0 )  ·  Luego  verificamos  la  solución  de  cada  una  de  las  desigualdades  para  delimitar  la  Región Factible. 

R1  : 2 x 1  + 2 x 2  £ 8 

R 2 : x 1  + 2 x 2  £ 6 

( 0 , 0 ) Þ  0 + 0  £ 8  SI  ( 0 , 5 ) Þ 0 + 10  £ 8  NO  ( 0 , 0 ) Þ 0 + 0  £ 6  SI  ( 0 , 4 ) Þ 0 + 8 £ 6  NO  ·  Una vez ubicada la región factible, asignamos un valor arbitrario a “z” en la función  objetivo  para  luego  trazar  la  recta  que  representa  a  dicha  función,  con  la  cual  encontraremos el punto óptimo.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

44

Ciencias Empresariales 

Investigación de Operaciones 

En Max .  z  = 15 x 1  + 20 x 2  Si  z  = 30  Þ 15 x 1 + 20 x 2  = 30 

x1  =  0 Þ x 2  = 1 . 5 ® P 1 ( 0 , 1 . 5 )  x 2  = 0 Þ x 1  = 2  ® P 2 ( 2 , 0 ) 

Solución óptima:  

x 1 =  2 [ u .]  sillas  x 2  = 2 [ u .] mesas 

R / en  z  = 15 x 1  + 20 x 2  z  = 15 ( 2 ) + 20 ( 2 )  z  = 70 [ $us. ] 

Tipos de r estr icciones: · 

R1    y  R 2 

Son  restricciones  activas,  ya  que  ambas  pasan  por  el  punto

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

45 

Ciencias Empresariales 

Investigación de Operaciones 

óptimo. ·  No tiene restricciones inactivas ni redundantes.  El  taller  de  carpintería  debe  fabricar  2  sillas  y  2  mesas, 

Inter pr etación: 

obteniendo una utilidad máxima de 70 $us., haciendo uso total de sus recursos.  2) 

Resuelva  el  problema  de  Pinturas  Monopol  por  el  método  gráfico  y  analice  sus  resultados.  Siendo: x 1  =  Cantidad de pintura para exteriores a producir [ Tn. / día  ] x 2  =  Cantidad de pintura para interiores a producir [ Tn. / día  ]

F  . O . :  Max .  z  = 5 x 1 + 4 x 2  [Miles $us . / día ]  ì 6 x 1  +  4 x 2  ï ï x 1  + 2 x 2  S . a . :  í ï - x 1  + x 2  ïî x 2 

£ 24  K  R 1  £

6  K R 2 

£

1  K R 3 

£

2  K R 4 

M  1  M  2  R .  Demanda  Demanda  Ext  . 

No  negativos  :  x 1 ³  0  ;  x 2  ³ 0  SOLUCIÓN GRÁFICA 

R1  : 6 x 1  + 4 x 2  = 24  R 2 : x 1  + 2 x 2  = 6  x1  =  0 Þ x 2  = 6  ® P 1 ( 0 , 6 )  x 2  = 0 Þ x 1  = 4  ® P 2 ( 4 , 0 )  x1  =  0 Þ x 2  = 3 ® P 1 ( 0 , 3 )  x 2  = 0 Þ x 1  = 6  ® P 2 ( 6 , 0 ) 

R 3 : - x 1  + x 2  = 1 

R 4 : x 2  =  2 

x1 =  0 Þ x 2  = 1 ® P 1 ( 0 , 1 )  x 2  = 0 Þ x 1  = - 1 ® P 2 ( - 1 , 0 ) 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

46 

Ciencias Empresariales 

Investigación de Operaciones 

Verificando las soluciones individuales: 

R1  : 6 x 1  + 4 x 2  £ 24 

R 2 : x 1  + 2 x 2  £ 6 

( 0 , 0 ) Þ  0 + 0  £ 24  SI  ( 5 , 0 ) Þ 30 + 0  £ 24  NO  ( 0 , 0 ) Þ  0 + 0  £ 6  SI  ( 7 , 0 ) Þ 7 + 0  £ 6  NO 

R 3 : - x 1  + x 2  £ 1 

R 4 :  x 2  £  2 

( 0 , 0 ) Þ  - 0 + 0  £ 1  SI 

( 0 , 0 ) Þ  0  £ 2  SI 

( 0 , 2 ) Þ - 0 + 2  £ 1  NO 

( 0 , 4 ) Þ 4  £ 2  NO 

Función Objetivo: 

En Max .  z  = 5 x 1  + 4 x 2 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

47 

Ciencias Empresariales 

Investigación de Operaciones 

Si  z  = 20  Þ 5 x 1 + 4 x 2  = 20 

x1  =  0 Þ x 2  = 5 ® P 1 ( 0 , 5 )  x 2  = 0 Þ x 1  = 4  ® P 2 ( 4 , 0 )  Solución óptima: 

x1  = 3 [ Tn . / día ]  Pintura exterior  x 2  = 1 . 5 [ Tn . / día ]  Pintura interior  R / en  z  = 5 x 1  + 4 x 2  z  = 5 ( 3 ) + 4 ( 1 . 5 )  z  = 21 [ Miles  $us. / día ]  Tipos de r estr icciones: · 

R1    y  R 2 

Son  restricciones  activas,  ya  que  ambas  pasan  por  el  punto 

óptimo. · 

R 3  y  R 4 

Son  restricciones  inactivas,  ya  que  ambas  delimitan  la  región 

factible, pero no pasan por el punto óptimo. ·  No tiene restricciones redundantes.  Inter pr etación:  La  empresa  de  Pinturas  Monopol  deberá  producir  3  Tn./día  de  pintura  para  exteriores  y  1.5  Tn./día  de  pintura  para  interiores,  obteniendo de esta manera una utilidad máxima de 21000 $us./día.; haciendo uso  total  de  sus  materias  primas  M1  ,  M2  y  no  cubriendo  totalmente  con  las  restricciones de demanda.  3) 

PROBLEMA DE LA DIETA x 1  =  Cantidad de alimento tipo (A) a consumir [ Kg. / sem. ] x 2  =  Cantidad de alimento tipo (B) a consumir [ Kg. / sem. ] 

F . O . :  Min .  z  = 20 x 1  + 40 x 2  [ $us . / sem .] 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

48 

Ciencias Empresariales 

Investigación de Operaciones 

ì 0 . 9  x 1  + 0 . 6  x 2  ³ 1  î 0 . 1 x 1  + 0 . 4  x 2  ³ 0 . 5 

S . a . : í

No negativos :  x 1 ³ 0 ; x 2  ³ 0 

Solución óptima: 

x1 = 0 . 33 [ Kg . / sem  .]  Alimento  Tipo A  x 2  =1 . 17 [ Kg . / sem  .]  Alimento  Tipo B  R / en  z  = 20 x 1  + 40 x 2  z  = 20 ( 0 . 33 ) + 40 ( 1 . 17 )  z  » 53 . 4 [ $us. / sem .]  Tipos de r estr icciones:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

49

Ciencias Empresariales 

· 

R1    y  R 2 

Investigación de Operaciones 

Son  restricciones  activas,  ya  que  ambas  pasan  por  el  punto 

óptimo. ·  No tiene restricciones inactivas ni restricciones redundantes.  Inter pr etación: 

La  persona  para  cumplir  con  su  dieta  deberá  consumir 

0.33  Kg.  / sem.  del  alimento Tipo  (A)  y  1.17  Kg.  /  sem.  del  alimento Tipo  (B),  con lo que alcanzará un costo mínimo de 53.4 $us. / sem. , logrando satisfacer sus  necesidades mínimas de carbohidratos y proteínas.  a.2) 

TIPOS DE SOLUCIÓN GRÁFICA DE UN MODELO DE P.L.  Los M.P.L. con dos variables suelen clasificarse según el tipo de solución gráfica  que presenta, en: · FACTIBLES:  Si  existe  el  conjunto de  soluciones  o  valores  que  satisfacen  las  restricciones. Estas a su vez pueden ser:  x2 

x1 

x1 

Solución única  acotada

x2 

x2 

x1 

Solución múltiple  F.O. 

F.O. 

Solución no  F.O.

·  NO FACTIBLES: Cuando no existe  el conjunto de soluciones que  cumplen  las restricciones; es decir que algunas restricciones son inconsistentes  x2 

b) 

MÉTODO SIMPLEX  x1 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

50

Ciencias Empresariales 

Investigación de Operaciones 

Es un método analítico (o algebraico) que utiliza las operaciones con filas (desarrolladas  en  matrices)  para  obtener  la  solución  a  los  modelos  de  programación  lineal.  Previamente  a  desarrollar  el  algoritmo del  método  simplex,  debemos  conocer  algunas  reglas básicas de transformación.  b.1)  REGLAS DE TRANSFORMACIÓN DE UN M.P.L.  Antes de desarrollar el algoritmo del método simplex, debemos considerar las siguientes  reglas de transformación para las restricciones que considera un M.P.L.:  1° 

Para  convertir  las  inecuaciones  (desigualdades)  en  igualdades,  se  deben  añadir  variables de compensación, pudiendo ser éstas:  i)  De Holgur a ( h i ): Se utilizan cuando las restricciones son del tipo

( £ )

ii)  Supér fluas o de exceso ( Si ): Se utilizan cuando las restricciones son del tipo

( ³ ) Ejemplo:  Si a 11  x 1  +  a 12  x 2  £ b 1  , 

entonces 

se 

transforma 

como: 

entonces 

se 

transforma 

como: 

a 11  x 1  + a 12  x 2  + h  = b 1  1

Si a 11  x 1  +  a 12  x 2  ³ b 1  , 

a 11  x 1  + a 12  x 2  - S  = b 1  1

2° 

Si las restricciones son del tipo ( = ), entonces ésta equivale a dos restricciones del  tipo ( £ ) y

( ³ )

Ejemplo:  Si 

a 11  x 1  +  a 12  x 2  = b 1  , 

entonces 

se 

transforma 

como:

ì a  11  x 1  +  a 12  x 2  £ b 1  í î a 11  x 1  + a 12  x 2  ³ b 1  O 

también 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

como:

51 

Ciencias Empresariales 

Investigación de Operaciones 

ì a  11  x 1  +  a 12  x 2  £ b 1  í î - a 11  x 1  - a 12  x 2  £ - b 1  3° 

La Función Objetivo, se transforma según las siguientes equivalencias:

Max Z  º  Min  (- Z  ) Max  (- Z  ) º Min  Z  Ejemplo: 

Exprese en sus formas Canónica y Estandar el M.P.L. siguiente: 

F .O    . :  Min .  z  = 6 x 1  - 2 x 2  + 3 x 3  ì x 1  +  x 2  + x 3  £ 15  ï S . a . : í 2 x 1  - x 3  ³ 12  ï x 2  = 2  î

No negativos :  x 1 ³ 0 ; x 2  ³ 0 ; x 3  ³ 0  b.2) 

ALGORITMO DEL MÉTODO SIMPLEX 

Es un algoritmo que aplica un procedimiento iterativo de solución, de forma sistemática  considerando tres fases fundamentales:  i) 

FASE INICIAL  Paso 1: Colocar el Modelo de Programación Lineal en su forma estandar.  Paso 2: Plantear la tabla inicial o solución inicial (iteración 0) 

ii) 

FASE DE CONTROL  Paso 3: Verificar si los coeficientes de la F.O. son todos positivos. ·  Si son positivos, entonces pare (es la solución) ·  Si no, vaya al siguiente paso.  Paso 4: Realizar un cambio de base, aplicando la “regla de entrada y salida de la

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

52

Ciencias Empresariales 

Investigación de Operaciones 

base” (encontrar el pivote) ·  Regla de entr ada: Se elige como variable que entra a la base, aquella  variable nó básica  que tenga el valor mas negativo en la fila de “Z”  (se obtiene la columna pivote) ·  Regla de salida: Se elige la variable básica   que  tenga menor radio  ( r  ), llamándose ésta, fila pivote. ·  Para el cálculo de ( r  ), se tiene la siguiente expresión: 

r  =

Lados  _ Derechos  valores  _  de  _  la  _  columna 

_  pivote 

Nota: Se debe ignorar aquellos valores de la columna pivote que son “negativos o  cero”  iii) 

FASE ITERATIVA  Paso 5: Aplicar operaciones elementales de fila y columna, para obtener ceros en  la columna pivote (aplicar Gauss­Jordan)  Paso 6: Volver a la fase de control 

Ejemplo: 

Aplicando el algoritmo simplex, determine la solución del M.P.L. siguiente: 

F .O    . :  Max .  z  = 5 x 1  + x 2  ì x 1  +  x 2  £ 5  K  R 1  ï S . a . : í x 1  £ 3  K R 2  ï x  + 3 x  £ 12  K R  2  3  î 1 

No negativos :  x 1 ³ 0 ; x 2  ³ 0  SOLUCIÓN: 

PASO 1: 

F .O    . :  Max .  z  = 5 x 1  + x 2  + 0 h 1  + 0 h 2  + 0 h 3 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

53 

Ciencias Empresariales 

Investigación de Operaciones 

= 5  ì x 1  +  x 2  + h 1  ï S . a . : í x 1  + h 2  = 3  ï x  + 3 x  + h 3  = 12  2  î 1 

No negativos :  x 1 ; x 2 ; h 1 ; h 2 ; h 3  ³ 0  PASO 2:  Iteración 0: 

F  . O . :  Max .  z - 5 x 1 - x 2  - 0 h 1  - 0 h 2  - 0 h 3  = 0  C.P. x1 

x2 

h1 

h2 

h 3 

L.D. 

ρ 

z 

­5 

­1 

0 

0 

0 

0 

N.S.C. 

h 1 

1 

1 

1 

0 

0 

5 

5/1=5 

h 2 

1 

0 

0 

1 

0 

3 

3/1=3 

h 3 

1 

3 

0 

0 

1 

12 

12/1=12 

F.P. 

NOTA: Los pasos 3 y 4 son realizados en la misma tabla de iteración 0  PASO 5: 

Iteración 1:  x1 

x2 

h1 

h2 

h 3 

L.D. 

ρ 

z 

0 

­1 

0 

5 

0 

15 

N.S.C. 

h 1 

0 

1 

1 

­1 

0 

2 

2/1=2 

x 1 

1 

0 

0 

1 

0 

3 

N.S.C. 

h 3 

0 

3 

0 

­1 

1 

9 

9/3=3 

NOTA: El paso 6 se realiza en la misma tabla de iteración 1  Iteración 2:  x1 

x2 

h1 

h2 

h 3 

L.D. 

z 

0 

0 

1 

4 

0 

17 

x 2 

0 

1 

1 

­1 

0 

2 

x1 

1 

0 

0 

1 

0 

3 

h 3 

0 

0 

­3 

2 

1 

3 

ρ 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

54

Ciencias Empresariales 

Investigación de Operaciones 

Como todos los valores de la fila z son positivos (caso maximizar), entonces se encontró la  solución é interpretamos dicha solución.  SOLUCIÓN BÁSICA  SOLUCIÓN ÓPTIMA 

x1  = 3 [ u ]  x 2  = 2 [ u ]  h 3  = 3 [ u ]  Abundante 

SOLUCIÓN NO BÁSICA 

h1  = 0 ü ý Escasos  h 2  = 0 þ

z = 17 [ u . m .]  Inter pr etación: 

Se  deben  producir  3  unidades  de 

x1   

y  2  unidades  de 

x 2  , 

obteniéndose un beneficio de 17 unidades monetarias.  c) 

MÉTODOS DE PENALIZACIÓN 

Para  resolver  problemas  que  incluyen  otros  tipos  de  restricciones  como  (  ≥  y/o  =  ),  se  emplean  los  llamados  Métodos  de  Penalización,  que  consideran  las  características  siguientes:  i) 

Para las restricciones ( ≥ y/o = ) se añaden variables artificiales (que sirven  como  artificio  matemático)  que  facilitan  la  solución  de  problemas  de  este  tipo. 

ii) 

Generalmente  si el  problema  tiene  solución  factible,  éstas  se  convierten  en  variables no básicas con valor final igual a cero. 

iii) 

c.1) 

La  iteración  cero  o  paso  inicial  debe  ser  corregida  en  función  de  las  modificaciones que se hagan en la función objetivo. 

Método de la “ M ”: Este  método  introduce  variables  artificiales  que  son  penalizadas en la función objetivo, para obligarlas a un nivel cero durante el curso  de las iteraciones simplex. El valor que se considera como “M” es un valor positivo  suficientemente grande. 

Pr ocedimiento: El método de la “M” utiliza el siguiente procedimiento:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

55 

Ciencias Empresariales 

Paso 1: 

Investigación de Operaciones 

Colocar el M.P.L. en su forma estandar , añadiendo: ·  Variables de holgura ( h i  ) a las restricciones del tipo ≤ ·  Variables artificiales ( a  i  ) a las restricciones del tipo = ·  Variables superfluas ( s i  ) y artificiales ( a i  ) a las restricciones del tipo ≥ 

Paso 2: 

En  la F.O. las  variables de holgura ( h  i  )  y superfluas ( s  i  ) tienen coeficiente  cero (0). Las variables artificiales ( a  i  ) se  las penaliza con un valor grande, (­  M) en el caso de maximizar  y (+M) en el caso de minimizar . 

Paso 3: 

Las variables básicas que corresponden a la tabla inicial (Iteración cero) deben  incluir  a  las  variables  artificiales,  pero  sus  coeficientes  en  la  F.O.  no  son  cero  sino  “M”, por  lo que deberán volverse cero utilizando operaciones elementales  de filas, considerando aquellas filas que incluyen a estas variables. 

Paso 4: 

Obtenida la  tabla  con la  F.O. corregida, se continúa  con los pasos  del  simplex  hasta obtener el resultado óptimo. 

Ejemplo: 

Aplicando el método de la M, determine la solución del M.P.L. siguiente: 

F .O    . :  Min .  z  = 5 x 1  + x 2  ì x 1  +  x 2  = 5  K  R 1  ï S . a . : í x 1  £ 3  K R 2  ï x  + 3 x  ³ 12  K R  2  3  î 1 

No negativos :  x 1 ³ 0 ; x 2  ³ 0  SOLUCIÓN:  Paso 1: 

F .O    . :  Min .  z  = 5 x 1  + x 2  + Ma 1  + 0 h 2  - 0 S 3  + Ma 3  = 5  ® R1  ì x 1  +  x 2  + a 1  ï S . a . : í x 1  + h 2  = 3  ® R 2  ï x  + 3 x  - S 3  + a 3  = 12  ® R 3  2  î 1 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

56 

Ciencias Empresariales 

Investigación de Operaciones 

No  negativos  :  x 1 ; x 2 ; a 1 ; h 2 ; S 3 ; a 3  ³  0 

Paso  2:  Corregimos  la  función  objetivo  despejando  las  variables  artificiales  de  las  restricciones que las contienen: 

R1  :  a 1  = 5 - x 1  - x 2  R 2  :  a 3  = 12 - x 1  - 3 x 2  + S 3  Reemplazamos  a1    y  a 3  en la F.O.: 

Min.  z  = 5 x 1  + x 2  + M ( 5 - x 1  - x 2 ) + 0 h 2  - 0 S 3  + M ( 12 - x 1  - 3 x 2  + S 3 )  Min.   z  = ( 5 - 2 M ) x 1 + ( 1 - 4 M ) x 2  + 0 h 2  + MS 3  + 17 M  Min.   z + ( 2 M  - 5 ) x 1 + ( 4 M  - 1 ) x 2  - 0 h 2  - MS 3  = 17 M  Iteración 0:

C.P. 

x1 

x2 

a1 

h2 

S3 

a3 

L.D. 

ρ 

z 

2M­5 

4M­1 

0 

0 

­M 

0 

17M 

N.S.C. 

a1 

1 

1 

1 

0 

0 

0 

5 

5/1=5 

h2 

1 

0 

0 

1 

0 

0 

3 

N.S.C. 

a3 

1 

3 

0 

0 

­1 

1 

12 

12/3=4 

X1 

x2 

a1 

h2 

S 3 

a3 

L.D. 

ρ 

z 

(2M­14)/3 

0 

0 

0 

(M­1)/3 

(1­4M)/3 

M+4 

N.S.C. 

a1 

2/3 

0 

1 

0 

1/3 

­1/3 

1 

1/(2/3)=1.5 

h2 

1 

0 

0 

1 

0 

0 

3 

3/1=3 

x 2 

1/3 

1 

0 

0 

­1/3 

1/3 

4 

4/(1/3)=12 

Iteración 1:

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

57 

F.P.

Ciencias Empresariales 

Investigación de Operaciones 

Iteración 2: x1 

x2 

a1 

h2 

S3 

a3 

L.D. 

ρ 

z 

0 

0 

7­M 

0 

2 

­(M+20)/3 

11 

N.S.C. 

x 1 

1 

0 

3/2 

0 

1/2 

­1/2 

3/2 

1.5/0.5=3 

h2 

0 

0 

­3/2 

1 

­1/2 

1/2 

3/2 

N.S.C. 

x 2 

0 

1 

­1/2 

0 

­1/2 

1/2 

7/2 

N.S.C. 

X1 

x2 

a1 

h2 

S3 

a3 

L.D. 

ρ 

z 

­4 

0 

1­M 

0 

0 

­(M+14)/3 

5 

S3 

2 

0 

3 

0 

1 

­1 

3 

h2 

1 

0 

0 

1 

0 

0 

3 

x 2 

1 

1 

1 

0 

0 

0 

5 

Iteración 3:

Como todos los valores de la fila z son negativos (caso minimizar), entonces se encontró la  solución é interpretamos dicha solución.  SOLUCIÓN BÁSICA 

SOLUCIÓN NO BÁSICA 

SOLUCIÓN ÓPTIMA 

x2  = 5 [ u ] 

x1  = 0  No  producir 

h 2  = 3 [ u ] ü ý Abundantes  S 3  = 3 [ u ] þ

a 1  = 0 ü ý V . artificial es  a 2  = 0 þ

z = 5 [ u . m .]  Inter pr etación: 

Se  deben  producir  5  unidades  de 

x 2  y  ninguna  unidad  de  x1   , 

obteniéndose  un  beneficio  de  5  unidades  monetarias.  Además  se  tienen  los  recursos  correspondientes  a  las  restricciones 

R 2  y  R 3  como 

abundantes,  ya  que 

h 2  y  S 3  se encuentran en la base.  c.2) 

Método de las Dos Fases:  Este  método  trabaja  también  con  variables  artificiales,  pero no  considera  la  introducción  de  un  valor  grande  “M”;  ya  que

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

58 

Ciencias Empresariales 

Investigación de Operaciones 

computacionalmente,  la  consideración  de  éste  valor  “M”  puede  hacer  que  la  solución  verdadera  se  distorsione;  es  por  esto  que  el  método  de  las  dos  fases  resulta mas eficiente.  Algor itmo:  El método de las dos fases utiliza el siguiente procedimiento:  FASE 1:  Considera cinco pasos  Paso 1: 

Se formula el M.P.L. en la forma estandar, añadiendo: ·  Variables de holgura ( h i  ) a las restricciones del tipo ≤ ·  Variables artificiales ( a  i  ) a las restricciones del tipo = ·  Variables superfluas ( s i  ) y artificiales ( a i  ) a las restricciones del tipo ≥ 

Paso 2: 

En la F.O. las variables de holgura y superfluas tienen coeficiente cero (0) ,  pero las variables artificiales tienen como coeficiente uno (1)  Nota: Si el problema tiene solución factible, las variables artificiales deben  ser cero en la tabla final (variables no básicas). 

Paso 3: 

Se  construye  una  F.O.  adicional  (  z  0  )  que  solo  tome  en  cuenta  a  las  variables artificiales. 

Paso 4: 

Las var iables básicas en la tabla inicial ( o iteración cero ) deben incluir a  las  var iables  ar tificiales  (  ya  que  éstas  forman  la  matriz  identidad  ),  pero  sus coeficientes en la F.O. no son cero sino uno; por lo que estos coeficientes  deben transformarse a cero operando con filas que incluyen a éstas variables  y que luego deben sumarse a la fila de  ( z 0  ). 

Paso 5: 

Obtenida la tabla corregida en la F.O., se procede a iterar siguiendo los pasos  del  simplex  hasta  llegar  a  que  la  F.O.  sea  cero,  garantizando  que  las  variables artificiales desaparezcan de la base (es decir que sean cero). 

FASE 2:  Considera dos pasos:  Paso 1: 

Se  toma  en  cuenta  la  última  tabla  de  la  fase  1,  eliminando  las  columnas

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

59 

Ciencias Empresariales 

Investigación de Operaciones 

correspondientes  a  las  var iables  ar tificiales;  y  se  introducen  los  valores  originales de la F.O. Se presentará el problema de que las var iables básicas  finales no tienen coeficientes cero en la F.O., esto se corrige con operaciones  elementales de filas.  Paso 2: 

Se  verifica  la  optimidad  viendo  si  todos  los  coeficientes  de  la  F.O.  son  mayores  o  iguales  a  cero  (caso  Maximizar);  si  esto  no  ocurre,  entonces  se  procede a iterar con los pasos del simplex. 

Ejemplo: 

Aplicando  el  método  de  las  Dos  Fases,  determine  la  solución  del  M.P.L. 

siguiente: 

F .O    . :  Min .  z  = 2 x 1  + 6 x 2  =  2  K  R 1  ì x 1  î 2 x 1  + 2 x 2  ³ 5  K R 2 

S . a . : í

No negativos :  x 1 ³ 0 ; x 2  ³ 0  SOLUCIÓN: Si maximizamos en vez de minimizar, entonces debemos transformar la F.O.  según las reglas de transformación vistas anteriormente, obteniendo: 

F .O    . :  Min .  z  = 2 x 1  + 6 x 2  F . O . :  Max . ( - z ) = -2 x 1  - 6 x 2  Ahora podemos aplicar el algoritmo de las dos fases:  FASE 1  Paso 1 y 2: 

Expresamos el M.P.L. en su forma estandar 

F .O    . :  Max . ( - z ) = -2 x 1  - 6 x 2  - 1 a 1  - 0 S 3  - 1 a 2  + a 1  = 2  ® R1  ì x 1  î 2 x 1  + 2 x 2  - S 2  + a 2  = 5  ® R 2 

S . a . : í

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

60 

Ciencias Empresariales 

Investigación de Operaciones 

No  negativos  :  x 1 ; x 2 ; a 1 ; S 2 ; a 2  ³ 0  Paso  3:  Construimos  la  F.O.  adicional  (  z  0  )  que  considera  solo  a  las  variables  artificiales 

F  . O . :  Max . ( - z 0 ) = -1 a 1  - 1 a 2  F . O . :  Max . ( - z 0 ) + 1 a 1  + 1 a 2  = 0  Paso 4: 

Iteración 0  x1 

x2 

a1 

S2 

a2 

L.D. 

z0 

0 

0 

1 

0 

1 

0 

a1 

1 

0 

1 

0 

0 

2 

a2 

2 

2 

0 

­1 

1 

5 

Corregimos la fila  ( z 0  ), mediante operaciones elementales de filas  (­1) a1 

: 

­1 

0 

­1 

0 

0 

­2 

(­1) a2 

: 

­2 

­2 

0 

1 

­1 

­5 

z0 

: 

0 

0 

1 

0 

1 

0 

z0  Corregido  : 

­3 

­2 

0 

1 

0 

­7 

Luego la tabla con los valores de la F.O. corregida (fila z 0), será: 

x1 

x2 

a1 

S2 

a2 

L.D. 

ρ 

z0 

­3 

­2 

0 

1 

0 

­7 

N.S.C. 

a1 

1 

0 

1 

0 

0 

2 

2 

a2 

2 

2 

0 

­1 

1 

5 

5/2

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

61 

Ciencias Empresariales 

Paso 5: 

Investigación de Operaciones 

Iteración 1:  x1 

x2 

a1 

S2 

a2 

L.D. 

ρ 

z0 

0 

­2 

3 

1 

0 

­1 

N.S.C. 

x 1 

1 

0 

1 

0 

0 

2 

N.S.C. 

a2 

0 

2 

­2 

­1 

1 

1 

1/2 

x1 

x2 

a1 

S2 

a2 

L.D. 

ρ 

z0 

0 

0 

1 

0 

1 

0 

x 1 

1 

0 

1 

0 

0 

2 

x 2 

0 

1 

­1 

­1/2 

1/2 

1/2 

Iteración 2: 

NOTA: La condición de parada es la misma que en el método simplex normal;  la  diferencia estriba en  que pueden  ocurrir  dos  situaciones  cuando  se produce  la  parada: ·  Si la F.O. toma un valor cero  ( z 0 =  0 ) , significa que el problema original  tiene solución y se pasa a la fases 2. ·  Si  la F.O.  toma un  valor distinto de cero ( z 0 ¹  0 )  ,  entonces significa que  el modelo no tiene solución.  Como todos los valores de la fila z  0  son positivos y el valor de la F.O. es cero,  entonces el modelo tiene solución y se pasa a la fase 2.  FASE 2  Paso 1: Introducimos los valores originales de la F.O. en la tabla final de la fase 1 (sin  tomar en cuenta las columnas que corresponden a las variables artificiales) y corregimos  mediante operaciones con filas dichos valores.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

62 

Ciencias Empresariales 

Investigación de Operaciones 

F  . O . :  Max . ( - z ) + 2 x 1 + 6 x 2  + 0 S 3  = 0  Iteración 3:  x1 

x2 

S2 

L.D. 

­z 

2 

6 

0 

0 

x 1 

1 

0 

0 

2 

x 2 

0 

1 

­1/2 

1/2 

Corregimos la fila  ( ­ z ), mediante operaciones elementales de filas  (­2) x1 

: 

­2 

0 

0 

­4 

(­6) x2 

: 

0 

­6 

3 

­3 

(­z) 

: 

2 

6 

0 

0 

(­z) Corregido 

: 

0 

0 

3 

­7 

Iteración 4:  x1 

x2 

S2 

L.D. 

­z 

0 

0 

3 

­7 

x 1 

1 

0 

0 

2 

x 2 

0 

1 

­1/2 

1/2

Como todos los valores de la fila z son positivos (caso maximizar), entonces se encontró la  solución é interpretamos dicha solución.  SOLUCIÓN BÁSICA 

SOLUCIÓN NO BÁSICA 

SOLUCIÓN ÓPTIMA 

x1  =  2 [ u ]  x 2  = 1 / 2 [ u ] 

S 2 = 0  Escaso 

z = 7 [ u . m .]  Inter pr etación: 

Se  deben  producir  2  unidades  de  x1   y  0.5  unidades  de 

x 2 

obteniéndose un beneficio de 7 unidades monetarias. Teniendo como escaso el recurso 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

63 

Ciencias Empresariales 

Investigación de Operaciones 

correspondiente a la restricción 

R 2  . 

TIPOS  DE  SOLUCIONES  QUE  SE  PRESENTAN  EN  LA  SOLUCIÓN  ANALÍTICA DE UN M.P.L.  La interpretación de la solución analítica de un M.P.L. presenta los siguientes casos:  i) 

Solución No Factible:  Se  presenta  cuando  alguna  de  las  variables  artificiales  añadidas, nó desaparecen de la base; conociéndose esto como solución no factible. 

F .O    . :  Max  . Z  = 2 x 1  + 6 x 2 

Ejemplo: 

=  2  ì x 1  î 2 x 1  + 2 x 2  ³ 5 

S . a . :  í

No negativos :  x 1 ³ 0 ; x 2  ³ 0 

ii) 

x 1 

x 2 

a  1 

S 2 

a  2 

L . D . 

z 

M+4 

0 

2M+6 

M 

0 

12­M 

x 2 

1 

1 

1 

0 

0 

2 

a 2 

­1 

0 

­2 

­1 

1 

1 

Solución Óptima No Acotada: Se conoce también como solución infinita y se presenta cuando en una

F .O    . :  Max  . Z  = 2 x 1  + 6 x 2 

Ejemplo: 

=  2  ì x 1  î 2 x 1  + 2 x 2  ³ 5 

S . a . :  í

No negativos :  x 1 ³ 0 ; x 2  ³ 0  x 1 

x 2 

a  1 

S 2 

a  2 

L . D . 

ρ 

z 

0 

0 

M­4 

­3 

M+3 

7 

N.S.C. 

x 1 

1 

0 

1 

0 

0 

2 

N.S.C. 

x 2 

0 

1 

­1 

­1/2 

1/2 

1/2 

N.S.C.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

64 

Ciencias Empresariales 

ii) 

Investigación de Operaciones 

Solución Óptima Múltiple:  Se  reconoce  cuando  una  variable  no  básica  tiene  coeficiente cero en la función objetivo. 

F .O    . : Max . Z  = 5 x 1  + 5 x 2 

Ejemplo: 

ì x 1  +  x 2  £ 5  £ 3  î x 1 

S . a . :  í

No negativos :  x 1 ³ 0 ; x 2  ³ 0  x 1 

x 2 

h 1 

h 2 

L . D . 

ρ 

z 

0 

0 

5 

0 

25 

N.S.C. 

x 2 

0 

1 

1 

­1 

2 

N.S.C. 

x 1 

1 

0 

0 

1 

3 

3/1=3 

x 1 

x 2 

h 1 

h 2 

L . D . 

z 

0 

0 

5 

0 

25 

x 2 

1 

1 

1 

0 

5 

h 2 

1 

0 

0 

1 

3

iv)  Soluciones  Cíclicas  y  Degener adas:  Estas  soluciones  se  presentan  cuando  se  tiene  un  empate  para  elegir  la  variable  de  entrada,  empate  que  se  rompe  arbitrariamente;  pero  cuando  se  tiene  empate  en  el  radio  ( r  )  a  veces  elegir  arbitrariamente  puede  conducir  a  un  Ciclaje .  Es  decir  que  luego  de  varias  iteraciones se repite la solución inicial, sin lograr obtener la solución óptima.  Este tipo de casos generalmente se presenta en problemas con soluciones factibles  básicas  degeneradas;  es  decir  en  aquellas  que  tengan  por  lo  menos  un  lado  derecho igual a cero. 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

65 

Ciencias Empresariales 

Investigación de Operaciones 

UNIDAD 4 

TEORIA DE LA DUALIDAD  4.1 

Intr oducción 

Los  problemas  de  P.L.  pueden  ser  propuestos  de  una  manera  diferente;  un  planteamiento  en  base  ya  no a la  asignación de recursos,  sino  a la  utilización  de  los  mismos.  Este  tipo  de  razonamiento  tiene  relación  con  lo  que  se  llama  Interpretación 

Dual.  4.2  Definición  La dualidad es una técnica matemática alternativa y complementaria a la programación  lineal,  ya que en algunos casos permite simplificar la  resolución de un M.P.L.;  siendo  útil cuando: ·  Se  tienen  que  resolver  problemas  lineales  que  tienen  más  restricciones que  variables. ·  Se  quiere profundizar  en  la  interpretación  económica  del  problema primal,  analizando  conceptos  como  el  de:  variable  dual,  precio  sombra  o  valor  marginal  de  los  recursos  consumidos,  además  propiedades  como  la  de  holgura complementaria y consumo de recursos limitados.  Nota  Todos  los  modelos  matemáticos  de  programación  lineal  conocidos  hasta  ahora  se  conocen como programas primales.  Una  aplicación  importante    de  la  teoría  de  la  dualidad  es,  que  puede  resolverse  el  problema dual directamente con el método simplex,  con  la finalidad de identificar una  solución  óptima  para  el  problema  primal.  A  demás  la  teoría  de  la  dualidad  juega  un  papel importante en el análisis de sensibilidad.  4.3 

For mulación del Dual 

Las características de transformación del Pr imal al Dual son las siguientes:  i) 

Si  la  F.O.  del  modelo  pr imal  es  Maximizar ,  entonces  la  F.O.  en  el

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

66 

Ciencias Empresariales 

Investigación de Operaciones 

modelo dual será de Minimizar  y viceversa.  ii) 

Cada restr icción del modelo pr imal genera una var iable en el modelo  dual. 

iii) 

Cada var iable del modelo pr imal genera una r estr icción en el modelo  dual. 

iv) 

La  F.O.  del  modelo  dual,  se  genera  a  partir  de  las  var iables  de  cada  r estr icción  y  tienen  como  coeficiente  a  los  lados  der echos  de  las  r estr icciones del modelo pr imal. 

v) 

Si  alguna  restr icción  del  modelo  pr imal  estuviese  definido  con  la  igualdad, entonces ésta genera una var iable sin r estr icción de signo en  el modelo dual. 

4.4 

Comparación del modelo PRIMAL con el DUAL  PRIMAL 

EQUIVALE 

DUAL 

Función Objetivo  Max Z 

→

Función Objetivo  Min Z 0 

Min Z 

→ 

Max Z 0 

Restr icciones  Si   R i  ≤  b i  Si   R i  =  b i 

→ →

Si   R i  ≥  b i 

→ 

Var iables 

Var iables  Y i  ≥  0  Y i  S.R.S.  Y i  ≤  0  Restr icciones 

Si X j  ≥  0 

→

R j  ≥  c j 

Si X j  S.R.S.  Si X j  ≤  0 

→ → 

R j  =  c j  R j  ≥  c j

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

67 

Ciencias Empresariales 

4.5 

Investigación de Operaciones 

Tabla r esumen de tr ansfor mación  Pr oblema Pr imal  (x i ) 

4.6 

Pr oblema Dual (y i ) 

Signo de la 

F.O.  Pr imal 

F.O. Dual 

Tipo de Restr icción 

Var iable 

Max. Z  Min. Z 

Min.  Z  0  Max. Z 0 

≥ 

S.R.S.  S.R.S.

≤ 

Inter pr etación económica de las var iables duales  i) 

Pr ecios  Sombra:  Son  también  conocidos  como  precios  duales  y  se  define  como  el  valor  por  unidad  de  recurso  adicional  que  se  quiere  utilizar. 

Otras interpretaciones son: ·  Exactamente  cuánto debe  estar  dispuesto  a  pagar  una  compañía  por  hacer disponibles los recursos adicionales. ·  ¿Es conveniente pagar a los trabajadores una   cuota de tiempo extra  para incrementar la producción? ·  Analizar si vale la pena incrementar mas tiempo de uso de máquina a  un costo de “x” o más $us. por unidad producida.  ii) 

Mientras  que  la  utilidad total de  todas  las  actividades  sea  menor  que  el  valor de los recursos, entonces la solución primal y dual correspondientes  no pueden ser óptimas. 

iii) 

Solo se llega a la utilidad máxima, cuando los recursos se han explotado  completamente,  lo  cual  sucede  cuando  el  valor  de  los  recursos  (Z  0)  excede  a la utilidad (Z ). 

EJ EMPLOS: En cada uno de los M.P.L. siguientes, realice la transformación del  Modelo Primal al Modelo Dual. 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

68 

Ciencias Empresariales 

Investigación de Operaciones 

1)  Modelo Pr imal: 

F .O    . :  Max .  z  = 5 x 1  + 12 x 2  + 4 x 3  ì x 1  + 2 x 2  + x 3  £ 10  K  R 1  î 2 x 1  - x 2  + 3 x 3  = 8  K R 2 

S . a . : í

No  negativos  :  x 1 ;  x 2  ;  x 3  ³  0  Pr imal Estándar : 

F  . O . :  Max .  z  =  5 x 1 + 12 x 2  + 4 x 3  + 0 h 1  - Ma 2  = 10  ¬  y1  ì x 1  + 2 x 2  + x 3  + h 1  í + a 2  = 8  ¬ y 2  î 2 x 1  - x 2  + 3 x 3  No  negativos  :  x 1  ;  x 2  ;  x 3  ;  h 1  ;  a 2  ³ 0 

S . a . : 

- 

-

-

-

R1 

R 2 

R 3 

R 4 

Modelo Dual: 

Finalmente el Dual: 

Min .  z 0  = 10 y 1  + 8 y 2  ì y 1  + 2 y 2  ³ 5 K R 1  ï S . a . :  í 2 y 1  - y 2  ³ 12 K R 2  ïî y 1  + 3 y 2  ³ 4 K R 3  y 1  + 0 y 2  ³ 0 K R 4  y 1  ;  y 2  S . R . S . 

F . O . :  Min .  z 0  = 10 y 1  + 8 y 2  ì y 1  + 2 y 2  ³ 5 K R 1  ï S . a . :  í2 y 1  - y 2  ³ 12 K R 2  ïî y 1  + 3 y 2  ³ 4 K R 3  y 1  ³ 0  ;  y 2  S . R . S . 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

69 

Ciencias Empresariales 

Investigación de Operaciones 

2)  Convierta al Modelo Dual el Modelo Primal siguiente: 

F .O    . :  Min .  z  = 15 x 1  + 12 x 2  ì x 1  +  2 x 2  ³ 3  K  R 1  î 2 x 1  + 4 x 2  £ 5  K R 2 

S . a . : í

No negativos :  x 1 ³ 0 ; x 2  ³ 0  3)  Realice  la  transformación del M.P.L.  (de pinturas Monopol) al  Dual, encuentre  la  solución  óptima  del  modelo  Dual  y  realice  un  análisis  comparativo  de  ésta  solución con la última tabla de la solución del primal.  Siendo:

x 1  =  Cantidad de pintura para exteriores a producir [ Tn. / día  ] x 2  =  Cantidad de pintura para interiores a producir [ Tn. / día  ] 

Modelo Pr imal:

ì 6 x 1  +  4 x 2  ï x  + 2 x  ï 1  2  S . a . :  í ï - x 1  + x 2  ïî x 2 

F  . O . :  Max .  z = 5 x 1 + 4 x 2  [Miles $us . / día ]  £ 24  K  R 1  £ 6  K R 2  £ 1  K R 3  £

2  K R 4 

M  1  M  2  R .  Demanda  Demanda  Ext  . 

No  negativos :  x 1 ³ 0 ;  x 2  ³ 0  Pr imal Estándar : 

F  . O . :  Max .  z  =  5 x 1 + 4 x 2  + 0 h 1  + 0 h 2  + 0 h 3  + 0 h 4  = 24  ¬ ì 6 x 1  + 4 x 2  + h 1  ïï x 1  + 2 x 2  + h 2  = 6  ¬ S . a . :  í - x 1  + x 2  + h 3  = 1  ¬ ï ïî x 2  + h 4  = 2  ¬ No  negativos  :  x 1  ;  x 2  ;  h 1  ;  h 2  ;  h 3  ;  h 4  ³ 0 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

y1  y 2  y 3  y 4 

70 

Ciencias Empresariales 

Investigación de Operaciones 

- 

-

-

-

-

-

R1 

R 2 

R 3 

R 4 

R 5 

R 6 

Modelo Dual: 

F . O . :  Min .  z 0  =  24 y 1  + 6 y 2  + y 3  + 2 y 4  ³ 5 K R 1  ì 6 y 1  + y 2  + y 3  S . a . :  í 4 y  + 2 y  + y  + y  ³ 4 K R  1  2  3  4  2  î y 1  ³ 0 K R 3  y 2  ³ 0 K R 4  y 3  ³ 0 K R 5  y 4  ³ 0 K R 6  y 1  ;  y 2  ;  y 3  ;  y 4  S . R . S .  Finalmente el Dual: 

F .O    . :  Min .  z 0  = 24 y 1  + 6 y 2  + y 3  + 2 y 4  ³ 5  ì 6 y 1  +  y 2  + y 3  î 4 y 1  + 2 y 2  + y 3  + y 4  ³ 4 

S . a . : í

No  negativos  :  y 1 ;  y 2  ;  y 3  ;  y 4  ³  0  Aplicando el software TORA se obtienen los siguientes resultados:  Solución del modelo Dual  Tabla final: Aplicando el Método de la M, se obtiene en 4 iteraciones  Iteración 4:  y1 

y2 

y3 

y4 

S1 

a1 

z 0 

0 

0 

­5/2 

­1/2 

­3 

­97 

­1/2  ­98.5 

21 

h1 

1 

0 

­0.38  ­0.13  ­0.25  0.25  0.13  ­0.13 

3/4 

h2 

0 

1 

1.25  0.75 

1/2

0.5 

S2 

a2 

­0.5  ­0.75  0.75 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

L.D. 

71 

Ciencias Empresariales 

Investigación de Operaciones 

SOLUCIÓN BÁSICA 

SOLUCIÓN  NO  BÁSICA 

SOLUCIÓN 

ÓPTIMA 

y3  = 0 Escasa demanda  y 4  = 0 Escasa demanda  S 1  = 0 Escasa M 1  S 2  = 0 Escasa M 2 

y1  = 0 . 75 [ Miles $ us / Tn . M 1 ]  y 2  = 0 . 5 [ Miles $ us / Tn . M 2 ]  z = 21 [ Miles $ us . / día ]  Inter pr etación: 

Los 

valores 

obtenidos 

de 

las 

variables 

duales 

y1  = 0 . 75 [ Miles $ us / Tn . M 1 ] ;  y2  = 0 . 5 [ Miles $ us / Tn . M 2 ]  nos  indican  el  precio  unidad  adicional  de  materia  prima  M1  y  M2  que  se  deben  pagar,  obteniendo  como  en  el  caso  del  primal  una  utilidad  de 

21000[   $us.  / día ] .  Solución del modelo Pr imal  Tabla final: Aplicando el Método de Simplex, se obtiene en 3 iteraciones  x1 

x2 

h1 

h2 

h3 

h4 

L.D. 

z 

0 

0 

3/4 

1/2 

0 

0 

21 

x1 

1 

0 

1/4 

­1/2 

0 

0 

3 

x2 

0 

1 

­1/8 

3/4 

0 

0 

3/2 

h3 

0 

0 

3/8 

­5/4 

1 

0 

5/2 

h4 

0 

0 

1/8 

­3/4 

0 

1 

1/2 

SOLUCIÓN BÁSICA 

SOLUCIÓN NO BÁSICA 

SOLUCIÓN 

ÓPTIMA 

x1  = 3 [ Tn . / día ]  p / ext.  x 2  = 3 / 2 [ Tn . / día ]  p / int .  h 3  = 5 / 2  Abundante  Dem .  h 4  = 1 / 2  Abundante  Dem . 

h1  = 0 ü ý Escasos  h 2  = 0 þ

z = 21[    Miles $ us . / día ] 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

72 

Ciencias Empresariales 

Investigación de Operaciones 

Inter pr etación: La empresa de Pinturas Monopol deberá producir 3 Tn./día de pintura para  exteriores  y  1.5 Tn./día de pintura para interiores,  obteniendo de esta manera una utilidad  máxima  de  21000  $us./día.;  haciendo  uso  total  de  sus  materias  primas  M1  ,  M2  y  no  cubriendo totalmente con las restricciones de demanda.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

73 

Ciencias Empresariales 

Investigación de Operaciones 

UNIDAD 5 

ANÁLISIS DE SENSIBILIDAD  5.1 

Intr oducción 

En  aplicaciones  prácticas,  no  solamente  interesa  la  solución  del  problema  propuesto,  sino también se desea saber como cambia esta solución si las condiciones iniciales del  problema se modifican; es decir si cambian los coeficientes de la función objetivo, los  coeficientes de los recursos y la cantidad de recursos disponibles.  En  este  sentido  el  análisis  de  sensibilidad,  convierte  a  la  solución  estática  de  la  programación lineal en un instrumento dinámico que evalúa las condiciones cambiantes  del problema.  Por  lo  tanto  el  Análisis  de  Sensibilidad  adquiere  mayor  utilidad  como  instrumento  administrativo, ya que los negocios y las industrias están sometidos a cambios continuos  que  dan  lugar  a  una  subsiguiente  re­evaluación  del  sistema  actual,  logrando  de  esta  manera la prueba de Factibilidad y Optimalidad.  5.2  Tipos de cambios en un M.P.L.  El  análisis  de  sensibilidad  considera  dos  tipos  de  cambios  en  un  M.P.L.  (Discretos  y  Continuos); los cambios que consideraremos en los ejemplos a analizar en la materia se  tratan de cambios discretos, los cuales se pueden realizar en:  i) 

Cambios en el vector  “ b ”:  Los  cambios  en  los  parámetros  de  los  recursos  disponibles  (  b  i  ),  se  realizan  a  partir  de  la  tabla  final  del  Simplex, desarrollando los cálculos en base a las siguientes expresiones:

B - 1 * (b + D ) ³ 0 

x B = B -1  * b 

z =  C B  * x B  Donde: 

B - 1

= 

Matriz  inversa,  formada  por  las  columnas  de  los  precios

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

74 

Ciencias Empresariales 

Investigación de Operaciones 

duales 

b 

= 

Matriz formada por la disponibilidad de los recursos

D 

= 

Incremento en la disponibilidad de un recurso 

x B 

=  Matriz (corregida) formada por la columna de las variables  básicas 

C B 

= 

Matriz  (corregida)  formada  por  la  fila  de  los  coeficientes 

que corresponden a las variables básicas.  ii) 

Cambios en el vector  “ C ”:  Los  cambios  en  los  coeficientes  de  las  variables básicas en la función objetivo, se realizan mediante las siguientes  expresiones:

Z *  - C  = y * * ( A - C ) 

A*  = B - 1  * A 

Donde: 

C  A  y * 

= 

Matriz formada por  los coeficientes de la función objetivo 

=  = 

Matriz formada por los coeficientes de las restricciones  Precios sombra (o precios duales) 

EJ EMPLOS: Realice el análisis de sensibilidad para siguientes problemas.  11. La  empresa  de confecciones  “ROMY”  fabrica  ropa  industrial:  camisas  y  overoles  para  las  diferentes  empresas.  Cada  camisa  requiere  2  hrs.–hombre  y  cada  overol  requieren 10 hrs.– hombre. Para la confección de una camisa se requiere 1 metro de  tela  y  para  un  overol  3  metros  de  tela.  Ambas  telas  son  diferentes.  Se  dispone  semanalmente de 120 metros de tela para camisas y 300 metros de tela para overoles.  Se trabaja 5 días a la semana con 10 operarios. Las utilidades son de 20 Bs. / camisa  y 80 Bs. / overol. ¿Cuál es el mejor plan de producción para la empresa?. 

CONF ECCIONES “ ROMY ”  x1  =  Cantidad de Camisas a producir [u / sem.]  x2  =  Cantidad de Overoles a producir [u / sem.]

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

75 

Ciencias Empresariales 

Investigación de Operaciones 

F .O    . :  Max Z  = 20 x 1 + 80 x 2  [ Bs. / sem.] ì2 x 1  + 10 x 2  £ 400  Mano de Obra  ï S . a . :  í x 1  £ 120  Tela para Camisas  ï 3 x 2  £ 300  Tela para Overoles î

No negativos : x 1 ³ 0 ; x 2  ³ 0  Resolviendo el M.P.L. la solución óptima es: 

x1 

x2 

h1 

h2 

h3 

L.D. 

z 

0 

0 

8 

4 

0 

3680 

x2 

0 

1 

0.1 

­ 0.2 

0 

16 

x1 

1 

0 

0 

1 

0 

120 

h3 

0 

0 

­ 0.3 

0.6 

1 

252 

SOLUCIÓN BÁSICA 

SOLUCIÓN NÓ BASICA 

x1  =  120 [u / sem.]  Camisas  x2  =    16 [u / sem.]  Overoles 

h1  =  0 [h­h / sem.]  Escasa M.O.  h2  =    0  [m  /  sem.]    Escasa  Tela 

p/Camisas 

h3  =  252 [m / sem.]  Abundante Tela p/Overoles  SOLUCIÓN ÓPTIMA: z  =  3680 [ Bs. / sem.]   Utilidad máxima  Cambios  en  la  disponibilidad  de  los  r ecur sos  (vector  “b” ):  Primeramente  debemos  determinar  los  límites  entre  los  cuales  podemos  variar  el  recurso  que  nos  permita  mejorar la  solución  obtenida  anteriormente, para  luego modificar  el recurso  y  calcular  los nuevos valores óptimos.

B - 1

*

(b + D ) 

³ 0 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

76 

Ciencias Empresariales 

Investigación de Operaciones 

é 0. 1  - 0 . 2  0 ù é400 + Dù ê 0  1  0 úú * êê 120  úú ³ 0  ê êë- 0 . 3  0 . 6  1 úû êë 300  úû ì 0 . 1 ( 400 + D ) - 0 . 2 ( 120 ) + 0 ( 300 ) ³ 0 K ( 1 )  ï 0 ( 400 + D ) + 1 ( 120 ) + 0 ( 300 ) ³ 0 K ( 2 )  í ï - 0 . 3 ( 400  + D ) + 0 . 6 ( 120 ) + 1 ( 300 ) ³ 0 K ( 3 )  î

De  (1 ) :  D  ³ -160  De  ( 3 ) :  D ³ 840  Luego  encontramos  el  conjunto  solución  del  sistema  de  desigualdades  por  el  método  gráfico 

D  ³ - 160 D  ³ 840

: 

­ 160 

:  840 

C . solución  :  ­ 160 

840

- 160 £ D £ 840  - 160  + 400  £ D + 400  £ 840  + 400  240  £ D + 400  £ 1240  Este  último  resultado  nos  indica  que  el  recurso  Mano  de  Obra  se  puede  variar  desde 

240  horas­hombre hasta  1240  horas­hombre, lo cual permitirá que la nueva solución  sea factible y óptima.  Una vez obtenidos los límites de variación, entonces podemos realizar los cambios que  veamos conveniente  para  obtener  una  nueva  solución,  haciendo uso  mas  adecuado  de  los recursos que tenemos como abundantes. 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

77 

Ciencias Empresariales 

Investigación de Operaciones 

En este sentido si incrementamos el número de operarios de 10 a 15, entonces la nueva  disponibilidad de M.O. será de 600 [ h­h / sem.].

é días  ù é hr . ù é h - h ù 5 ê * 8 ê * 15 [operarios  ] = 600 ê ú ú ú ë sem . û ë día  û ë sem . û Con  esta  nueva  disponibilidad  procedemos  a  calcular  la  nueva  solución,  mediante  la  expresión: 

x B

=

B -1

*

b 

é x 2 ù é 0 . 1  - 0 . 2  0 ù é 600 ù ê ú ê 1  0 úú * êê120 úú ê x 1  ú = ê 0  êë h 3  úû êë - 0 . 3  0 . 6  1 úû êë 300 úû

Þ

é x 2  ù é 36 ù ê ú ê ú ê x 1  ú = ê120 ú êë h 3  úû êë192 úû

NUEVA SOLUCIÓN BÁSICA 

x1  =  120 [u / sem.]  Camisas.  x2  =    36 [u / sem.]  Overoles  h3  =  192 [m / sem.]  Abundante Tela p/Overoles  Con  estos  valores  de  la  nueva  solución  básica,  calculamos  nueva  utilidad,  mediante: 

z=

C B  *

x B 

é1 20 ù z =  [20  80  0 ]* êê 36  úú êë192 úû

Þ

z  = 5280  [Bs . / sem . ] 

Inter pr etación: Como podemos ver la nueva solución básica tiene un incremento de la  fabricación de overoles de 16 a 36 unidades y una reducción en la abundancia (de 252  metros a 192 metros) de la tela para los mismos; habiéndose incrementado también las  utilidades de 3680 a 5280 [ Bs./sem.].  2.  La  empresa  de  pinturas  MONOPOL,  produce  pinturas  tanto  para  interiores  como

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

78 

Ciencias Empresariales 

Investigación de Operaciones 

para  exteriores,  a  partir  de  dos  materias  primas  M1  y  M2.  La  siguiente  tabla  proporciona los datos básicos del problema: 

Materia Prima 

Toneladas de Materia Prima  por tonelada de Pintura para 

Disponibilidad  Máxima Diaria 

Exteriores 

Interiores 

(Toneladas) 

M1 

6 

4 

24 

M2 

1 

2 

6 

5 

4

Utilidad por Tonelada  (1000 $us.) 

Una  encuesta  de  mercado  restringe  la  demanda  máxima  diaria  de  pintura  para  interiores  a  2  toneladas.  Además,  la  demanda  diaria  de  pintura  para  interiores  no  puede  exceder  a  la  pintura  para  exteriores  por  más  de  1  tonelada.  La  empresa  MONOPOL  quiere  determinar  la  mezcla  de  productos  óptima  de  pintura  para  interiores y para exteriores que maximice la utilidad total diaria.  EMPRESA MONOPOL  Siendo:

x 1  =  Cantidad de pintura para exteriores a producir [ Tn. / día  ] x 2  =  Cantidad de pintura para interiores a producir [ Tn. / día  ]

F  . O . :  Max .  z  = 5 x 1 + 4 x 2  [Miles $us . / día ]  ì 6 x 1  +  4 x 2  ï ï x 1  + 2 x 2  S . a . :  í ï - x 1  + x 2  ïî x 2 

£ 24  K  R 1  £

6  K R 2 

£

1  K R 3 

£

2  K R 4 

M  1  M  2  R .  Demanda  Demanda  Ext  . 

No  negativos  :  x 1 ³  0  ;  x 2  ³ 0 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

79 

Ciencias Empresariales 

Investigación de Operaciones 

Resolviendo el M.P.L. la solución óptima es:  x1 

x2 

h1 

h2 

h3 

h4 

L.D. 

z 

0 

0 

3/4 

1/2 

0 

0 

21 

x1 

1 

0 

1/4 

­1/2 

0 

0 

3 

x2 

0 

1 

­1/8 

3/4 

0 

0 

3/2 

h3 

0 

0 

3/8 

­5/4 

1 

0 

5/2 

h4 

0 

0 

1/8 

­3/4 

0 

1 

1/2 

SOLUCIÓN BÁSICA  ÓPTIMA 

x1  = 3 [ Tn . / día ]  p / ext.  x 2  = 3 / 2 [ Tn . / día ]  p / int .  h 3  = 5 / 2  Abundante  Dem .  h 4  = 1 / 2  Abundante  Dem . 

SOLUCIÓN NO BÁSICA 

SOLUCIÓN 

h1  = 0 ü ý Escasos  h 2  = 0 þ

z = 21 [ Miles $ us . / día ]  Inter pr etación: La empresa de Pinturas Monopol deberá producir 3 Tn./día de pintura para  exteriores  y  1.5  Tn./día de pintura para interiores,  obteniendo de esta manera una utilidad  máxima  de  21000  $us./día.;  haciendo  uso  total  de  sus  materias  primas  M1  ,  M2  y  no  cubriendo totalmente con las restricciones de demanda.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

80 

Ciencias Empresariales 

Investigación de Operaciones 

UNIDAD 6 

MODELO DE TRANSPORTE Y ASIGNACIÓN  6.1 

Intr oducción 

En  el  ámbito  de  la  I.O.  existen  problemas  de  P.L.  que  por  su  naturaleza  presentan  características  especiales,  ya  que  manejan  muchas  variables,  donde  a  veces  éstas  se  presentan como variables dobles.  Si  bien  este  tipo  de  problemas  pueden  ser  resueltos  por  los  algoritmos  clásicos,  estos  métodos pueden resultar ineficientes y largos por la misma naturaleza del problema; de  manera que se han desarrollado algoritmos especiales que pueden llevarnos al resultado  óptimo de manera más rápida y más ordenada, lo cuál permite una mejor interpretación  de  los  resultados obtenidos. Uno de  los  modelos que se emplea con  mucha  frecuencia  principalmente en problemas de distribución, es el de Transporte y Asignación .  6.2.  Modelo de tr anspor te  Es un modelo de la I.O. que se interesa por la distribución de un determinado producto  desde  puntos  de  Ofer ta  (llamados  también  Orígenes)  hacia  puntos  de  Demanda  (llamados  también  Destinos); cuyo objetivo principal es de encontrar el  mejor plan de  distribución  (embarque  óptimo),  que  minimice  el  costo  total  de  transportar  los  productos, satisfaciendo los requerimientos de Oferta y Demanda.  6.2.1  For mulación matemática del modelo de tr anspor te  El modelo de transporte matemáticamente se puede formular de la siguiente manera: 

F .O . :  Min  Z  = C 11 x 11  + C 12 x 12  + L + C mn x mn 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

81 

Ciencias Empresariales 

S . a . : 

Investigación de Operaciones 

ì x 11  +  ï ï x 21  + ï M ï ï x m 1  + ï í ï x  + ï 11  ï x 12  + ï ï M ï x 1 n  + î

No negativos 

: 

x 12  + L  + x 1 n  = a 1  x 22  + L + x 2 n  = a 2  M

M

M

Restricciones de Oferta 

x m  2  + L + x mn  = a m  x 21  + L + x m 1  = b 1  x 22  + L + x m  2  = b 2  M

M

M

Restricciones de Demanda

x 2 n  + L + x mn  = b n  X  i  j  ³  0  ;  " i  j 

Donde: 

Z 

= 

X  i  j  = 

Función costo de transporte total, a ser minimizada  Nº  de  unidades  del  producto  a  transportar  del  origen  “  i  ”  la 

destino “ j ”  ( i  =  1 ,  2  , K , m  ) 

; 

(  j  =  1 ,  2  , K ,  n  ) 

C  i  j  = 

Costo unitario de transportar el producto del origen “ i ” la destino 

a  i 

= 

Oferta y/o capacidad del i­ésimo origen. 

b  j 

= 

Oferta y/o Requerimiento j­ésimo desatino. 

m  n 

=  = 

Número de orígenes y/o Ofertas  Número de destinos y/o Demandas 

“ j ” 

6.2.2  Matr iz de Costos del modelo de tr anspor te  La formulación anterior puede ser expresada como una matriz de costos de transporte ,  de la siguiente manera: 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

82

Ciencias Empresariales 

Investigación de Operaciones 

D E S T I N O S  Oferta  1  O  R  I  G  E  N  E  S 

1 

2 

C11  X11 

2 

C12  C22 

. 

X22  . 

. 

. 

. 

. 

Demanda 

Cm1 

C1n 

a 1 

C2n 

a 2 

X1n 

X21  . 

Xm1 

n 

… 

X12  C21 

m 

… 

…  X2n 

. 

. 

. 

. 

. 

. 

. 

. 

Cm2  Xm2 

… 

Cmn  Xmn 

b2 

… 

bn

b1 

a m 

SOLUCIÓN DEL MODELO DE TRANSPORTE  Para  determinar  la  solución  óptima  al  modelo  de  transporte,  se  deben  considerar  las  siguientes etapas:  ETAPA 1:Balancear el modelo (es decir que la oferta debe ser igual a la demanda)

å

a  i  = å b j 

Si se presenta el desbalance, se debe considerar:  a)  Si la  Oferta  >  Demanda  → Añadir una Demanda artificial  donde: Demanda artificial =

å

a  i  -  å b j 

b)  Si la  Demanda  >  Oferta  → Añadir una Oferta artificial 

donde: Oferta artificial =

å

b j  -  å a i 

Nota: En ambos casos los costos deben ser igual a cero 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

83 

Ciencias Empresariales 

Investigación de Operaciones 

ETAPA 2:Establecer  una  solución  básica  factible  inicial,  utilizando  alguno  de  los  métodos siguientes:  a)  b) 

Método de la Esquina Nor­oeste (M.E.N.)  Método del Costo Menor (M.C.M.) 

c) 

Método de Aproximación de Vogel  (M.A.V.) 

ETAPA 3:Hallar  la  solución óptima utilizando  el  algoritmo de  transporte,  empezando  con  la  solución  de  inicio  dada;  esta  etapa  incluye  la  verificación  de  la  optimalidad del problema.  Para  determinar  la  solución  óptima,  se  utiliza  el  Algoritmo  Húngaro,  cuyo  procedimiento es:  PASO 1: Balancear el problema; es decir que:  N° de Or ígenes = N° de Destinos  i) Si 

N° de Orígenes N° de Destinos 

→     Añadir columnas ficticias con costo 

igual a cero  iii) Si se quiere penalizar un Origen y/o destino 

→      Se utiliza como costo asociado 

M  PASO 2: Construir una nueva matriz de costos, donde aparezca por lo menos un Cero  en cada fila y columna (restar los valores menores de cada fila y/o columna 

con los demás  valores correspondientes de cada fila y/o columna ).  PASO 3: Probar una asignación tentativa en las posiciones con costo igual a cero; si ésta  es posible entonces el problema concluye, de lo contrario ir al paso 4.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

84 

Ciencias Empresariales 

Investigación de Operaciones 

PASO 4: Prueba de optimalidad: Trazar el Mínimo Número de líneas que tachen a  todos los ceros de la matriz.  a) 

METODO DE LA ESQUINA NOR­OESTE (M.E.N.) 

PASO 1:  En  la  Posición  a  11  de  la  matriz  de  costos  se  asigna  el  valor  de  x 11  ,  donde

x11  =  Mínimo 

(a 1  y  b 1  ) 

PASO 2:  Determinar  los  nuevos  valores  corregidos  de  la  Oferta  y  la  Demanda (a  1  y  b 1  ) ; analizando posteriormente:  a) 

Si aˆ 1  corregido  es  cero,  entonces  pasar  a  la  posición a  21  ,  donde x 21  =  Mínimo 

b) 

(a 

2 

) 

y  b ˆ1   . 

Si bˆ 1   corregido  es  cero,  entonces  pasar  a  la  posición a  12  ,  donde x12  =  Mínimo 

(a ˆ 1  y  b 2  ) . 

PASO 3:  Se continua con el procedimiento, desde la posición asignada hasta llegar a  la posición (m  ;  n )  b)  METODO DEL COSTO MENOR (M.C.M.)  Este método encuentra una solución inicial mejor que la anterior, ya que toma en cuenta  las rutas más económicas del modelo.  PASO 1: Se  asigna  tanto como se pueda a la posición que tenga el costo mas bajo por  unidad (los empates se rompen arbitrariamente)  PASO 2: Se tacha las filas o columnas satisfechas; se ajusta la cantidad de la Oferta y la  Demanda  conforme  a ello.  Si  tanto  una  fila  como  una columna  se  satisfacen  simultáneamente, solo se tacha uno de ellos.  PASO  3:Se  busca siempre  la posición no  tachada  con  el  costo  mas bajo por unidad  y  repetimos el proceso hasta que quede exactamente una fila y una columna no  tachadas.

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

85 

Ciencias Empresariales 

c) 

Investigación de Operaciones 

METODO DE APROXIMACIÓN DE VOGEL (M.A.V.) 

Este  método  es  una  versión  mejorada  del  método  de  costo  menor;  éste  generalmente  produce mejores soluciones iniciales. El procedimiento es el siguiente:  PASO 1: En  la  matriz  de  costos,  calcular  las  diferencias  de  costo  mínimas,  tanto  para  filas como para columnas (esto se consigue restando los dos valores menores  de costo).  PASO 2: Seleccionar la fila y/o columna con mayor diferencia y ubicar el costo mínimo  correspondiente  a  esta  fila  y/o  columna.  La  posición

(i ,  j ) 

donde  se 

 

encuentre este costo será la variable (x ij  ) a tomar en cuenta.  PASO 3: En la posición (i ,  j )  calcular x ij  =  Mínimo 

(a 

i 

aˆ i  =  a i  - x ij 

← 

Oferta 

bˆ j  =  b j  - x ij 

← 

Demanda 

y  b j  ) ; luego actualizar: 

PASO 4: Si  aˆ i  =  0  (oferta corregida), entonces eliminar esta fila del análisis.  Si  bˆ j  =  0  (demanda corregida), entonces eliminar esta columna del análisis.  PASO 5: Repetir los pasos anteriores hasta que no sea posible calcular las diferencias.  EJ EMPLO:  Se  quiere distribuir  un  producto  desde  3  almacenes  (A1, A2,  A3)  a  dos  tiendas  (T1, T2 ). Se sabe que llevar el producto del almacén A2, a la tienda T2 no es  posible por problemas de ruta. Se desea establecer el plan de embarque que proporcione  el  mínimo  costo  de  transporte;  los  costos  unitarios,  las  ofertas  y  demandas  de  cada  almacén  y  tienda,  se 

muestran  en  la  tabla  de 

costos siguiente: 

TIENDA 

A 

A1 

T1 

T2 

2 

5 

Oferta  30

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

86 

Ciencias Empresariales 

Investigación de Operaciones 

L 

A2 

5 

M* 

40 

A3 

4 

3 

20 

Demanda 

50 

30 

M  A  C  E  N 

ETAPA 1: 

M* = Penalización con un costo “M”   BALANCEAR muy grande, por problemas de ruta EL 

MODELO 

S a i = 90  ( Oferta ) ; S b j  = 80  ( Demanda  )  Como  la  oferta  es  mayor  a  la  demanda,  entonces  debemos  aumentar  una  demanda  artificial,  que  en  nuestro  caso  será  una  tienda  artificial 

TA  =  S a i  - S b j  Þ TA  = 10 . Luego la tabla de costos balanceada será:  TIENDA 

Oferta 

T1 

T2 

TA 

A1 

2 

5 

0 

30 

A2 

5 

M* 

0 

40 

A3 

4 

3 

0 

20 

Demanda 

50 

30 

10 

A  L  M  A  C  E  N  ETAPA 2: 

SOLUCIÓN BÁSICA FACTIBLE INICIAL 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

87 

Ciencias Empresariales 

a) 

Investigación de Operaciones 

METODO DE LA ESQUINA NOR­OESTE (M.E.N.)  TIENDA  T1  A 

A1 

L  M  A 

A2 

T2 

Oferta 

TA 

2 

5 

0 

5 

M* 

0 

30

20 

30 

40 

20

C  4 

E 

3  10 

A3 

0  10 

20 

N  Demanda 

50 

30 

10 

SOLUCIÓN BÁSICA FACTIBLE INICIAL  Variables Básicas  Variables No Básicas 

x11   =  30  x 21  = 20  x 22  = 20  x 32  = 10  x 33  = 10 

x12   =  0  x 13  = 0  x 23  = 0  x 31  = 0 

COSTO DE TRANSPORTE: z = 190  + 20 M  [u . m . ]  b) 

METODO DEL COSTO MENOR (M.C.M.)  TIENDA  T1  A  L 

A1 

2  20 

T2 

Oferta 

TA  5 

0  10

30 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

88 

Ciencias Empresariales 

Investigación de Operaciones 

M 

5  A2 

A 

30 

C 

40 

10 4 

E  N 

3 

0 

20 

A3 

Demanda 

0 

M* 

50 

20 

30 

10 

SOLUCIÓN BÁSICA FACTIBLE INICIAL  Variables Básicas 

Variables No Básicas 

x11   =  20  x 13  = 10  x 21  = 30  x 22  = 10  x 32  = 20 

x12   =  0  x 23  = 0  x 31  = 0  x 33  = 0 

z =  250 + 10 M  [u . m . ] 

COSTO DE TRANSPORTE: c) 

METODO DE APROXIMACIÓN DE VOGEL (M.A.V.)  TIENDA  T1  A  L 

A1 

2  5 

A2 

E 

A3 

5 

0 

M* 

0 

30 

Demanda 

3 

0  20 

20  50 

30 

30 

40 

10 4 

N 

Oferta 

TA 

10 

20

M  A  C 

T2 

10 

SOLUCIÓN BÁSICA FACTIBLE INICIAL  Variables Básicas 

Variables No Básicas 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

89 

Ciencias Empresariales 

x11   =  20  x 12  = 10  x 21  = 30  x 23  = 10  x 32  = 20 

Investigación de Operaciones 

x13   =  0  x 22  = 0  x 31  = 0  x 33  = 0  z = 300  [u . m . ] 

COSTO DE TRANSPORTE:

ETAPA 3:  Hallar  la  solución  óptima,  aplicando  el  algoritmo  de  verificación  y  búsqueda  del  óptimo.  Éste  procedimiento  es  iterativo  y  trabaja  bajo  los  principios del método simplex.  PASO 1: 

Calcular el valor de las variables duales  u i  (para las ofertas) y  v j  (para las  demandas). Este cálculo se realiza formando un sistema de ecuaciones con  las variables duales y los costos para todas las variables básicas, utilizando  la siguiente relación: 

u i  + v j  = c ij 

Nota:  Como  se  tiene  m  +  n  –  1  variables  básicas  y  m  +  n   incógnitas,  entonces  se  tiene  un  grado  de  libertad,  por  lo  que  se  asigna  un  valor  arbitrario  generalmente  a  la  variable  dual  con  mayor  número  de  asignaciones y se obtiene las otras resolviendo el sistema de ecuaciones. 

PASO 2: 

(

)

Calcular el parámetro zij  - c ij  = c ij  - u i  + v j  para todas las variables  no básicas, analizando: 

PASO 3: 

i) 

Si z ij  - c ij  ³ 0 ; " ij  Þ La solución hallada es óptima. 

ii) 

Si  z ij  - c ij  £ 0 ;  Para algún

( i,  j ) Þ  seguir con el paso 3 

REGLA DE ENTRADA:  Introducir como variable básica aquella  X ij  que  tenga el valor de  zij  - c ij  mas negativo. 

PASO 4: 

MECANISMO  DE  COMPENSACIÓN:   Al  elegir  la  variable  de  entrada  ésta tomará un valor + l que descompensará la oferta y/o demanda, por lo

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

90 

Ciencias Empresariales 

Investigación de Operaciones 

que se construye un circuito cerrado de compensación, sumando y restando

l  a las variables básicas.  PASO 5: 

REGLA DE SALIDA:  Se elige aquella variable básica que tenga el menor  valor rotulado con - l en el mecanismo de compensación. 

PASO 6: 

Repetir el procedimiento desde el PASO 1, hasta hallar la solución óptima

( z ij  - c ij  ³ 0 )  EJ EMPLO:  Determine  la  solución  óptima  para  el  problema  de  los 3  almacenes  y  2  tiendas, tomando como S.B.F.I. la obtenidos por el métodos del costo menor (M.C.M.)  SOLUCIÓN BÁSICA FACTIBLE INICIAL  Variables Básicas 

Variables No Básicas 

x11   =  20  x 13  = 10  x 21  = 30  x 22  = 10  x 32  = 20 

x12   =  0  x 23  = 0  x 31  = 0  x 33  = 0  z =  250 + 10 M  [u . m . ] 

COSTO DE TRANSPORTE: ITERACIÓN 1:  TIENDA  T1  A  L  M  A 

A1  A2 

5 

0 

5 

M* 

0 

+ λ 4 

u i 

30 

u1  = 0 

40 

u2  = 3 

20 

u 3  = 6­M 

10  3 

0 

A3 

N 

Oferta  TA 

2 

20 ­ λ 

C  E 

T2 

Demanda 

50  30 + λ 

20  30  10 ­ λ 

v j 

v1  = 2 

v2  = M­3 

10 

v3  = 0 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

91 

Ciencias Empresariales 

Investigación de Operaciones 

VARIABLES NO BÁSICAS 

VARIABLES BÁSICAS 

zij  - c ij  = c ij  - ( u i  + v j )

u i  + v j  = c ij  Si u 1 = 0  u 1  + v 1  = 2  ® v 1  = 2  u 1  + v 3  = 0  ® v 3  = 0  u 2  + v 1  = 5  ® u 2  = 3  u 2  + v 2  = M  ® v 2  = M  - 3  u 3  + v 2  = 3  ® u 3  = 6 - M 

z 12 - c 12  = 5 - (0 + M  - 3 ) = 8 - M  ¬ V . entra  z 23  - c 23  = 0 - (3 + 0 ) = - 3  z 31  - c 31  = 4 - (6 - M  + 2 ) = M  - 4  z 33  - c 33  = 0 - (6 - M  + 0 ) = M  - 6  Variable que entra 

    :  x12

Variable que sale 

:  x 22  porque  10 - l  = 0  Þ l = 10 

Con  el  valor  de l  = 10 procedemos  a  corregir  los  valores  de  las  variables  básicas  relacionadas con el circuito y se obtiene:  ITERACIÓN 2:  TIENDA  T1  A  L  M  A  C  E 

A1  A2 

T2  2 

5 

0 

5 

M* 

0 

10 + λ  10  4 

Oferta 

u i 

30 

u1  = 0 

40 

u2  = 3 

20 

u3  = ­ 2 

TA 

10 ­ λ  3 

0 

A3 

N  Demanda 

50  40 ­ λ 

30 

v j 

v1  = 2 

v2  = 5 

VARIABLES BÁSICAS 

+ λ

10 

v3  = 0  VARIABLES NO BÁSICAS 

20 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

92 

Ciencias Empresariales 

Investigación de Operaciones 

zij  - c ij  = c ij  - ( u i  + v j )

u i  + v j  = c ij  Si u 1 = 0  u 1  + v 1  = 2 ® v 1  = 2  u 1  + v 2  = 5 ® v 2  = 5  u 1  + v 3  = 0 ® v 3  = 0  u 2  + v 1  = 5  ® u 2  = 3  u 3  + v 2  = 3 ® u 3  = - 2  z 22 - c 22  = M  - (3 + 5 ) = M  - 8  z 23  - c 23  = 0 - (3 + 0 ) = - 3 ¬ V . entra  z 31  - c 31  = 4 - (- 2 + 2 ) = 4  z 33  - c 33  = 0 - (- 2 + 0 ) = 2  Variable que entra 

:  x 23 

Variable que sale 

    porque  10 - l  = 0  Þ l = 10  :  x13

Con  el  valor  de l  = 10 procedemos  a  corregir  los  valores  de  las  variables  básicas  relacionadas con el circuito y se obtiene:  ITERACIÓN 3:  TIENDA  T1  A  L  M  A  C  E 

A1 

T2  2 

5 

0 

5 

M* 

0 

3 

0 

A2 

Oferta 

u i 

30 

u1  = 0 

40 

u2  = 3 

20 

u3  = ­ 2 

TA 

10 

20 4  A3 

N  Demanda 

v j 

50  30 

v1  = 2 

30 

v2  = 5 

10 

v3  = ­ 3  VARIABLES NO BÁSICAS 

VARIABLES BÁSICAS 

u i  + v j  = c ij 

10

20 

zij  - c ij  = c ij  - ( u i  + v j  ) 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

93 

Ciencias Empresariales 

Investigación de Operaciones 

Si u 1 = 0  u 1  + v 1  = 2 ® v 1  = 2  u 1  + v 2  = 5 ® v 2  = 5  u 2  + v 1  = 5 ® u 2  = 3  u 2  + v 3  = 0  ® v 3  = - 3  u 3  + v 2  = 3 ® u 3  = - 2 

z 13 - c 13  = 0 - (0 - 3 ) = 3  z 22  - c 22  = M  - (3 + 5 ) = M  - 8  z 31  - c 31  = 4 - (- 2 + 2 ) = 4  z 33  - c 33  = 0 - (- 2 - 3 ) = 5 

Como todos los valores de  zij  - c ij  son positivos, entonces se tiene la solución óptima  del modelo.  SOLUCIÓN ÓPTIMA  Variables Básicas 

Variables No Básicas 

x11   =  20  x 12  = 10  x 21  = 30  x 23  = 10  x 32  = 20 

x13   =  0  x 22  = 0  x 31  = 0  x 33  = 0  z = 300  [u . m . ] 

COSTO DE TRANSPORTE: INTERPRETACIÓN GRÁFICA:  ALMACEN 

TIENDA  20 

A1 

10 

T1 

10

T2 

30 A2  20  A3 

TA 

EJ ERCICIO:La  empresa  “BOLSEMILLAS  S.A.”  envia  camiones cargados de  grano  desde 3 silos de almacenamiento (S1, S2, S3 ) a 4 molinos (M1, M2, M3, M4). La oferta  y demanda en camiones cargados, junto con los costos de transporte (en cientos de $us  por camión) en las diferentes rutas se muestra en cuadro de costos siguiente: 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

94 

Ciencias Empresariales 

Investigación de Operaciones 

MOLINOS  M1  M2  M3  M4  S 

Oferta 

S1 

10 

2 

20 

11 

15 

S2 

12 

7 

9 

20 

25 

S3 

4 

14 

16 

18 

10 

Demanda 

5 

15 

15 

15 

I  L  O  S 

6.3  MODELO DE ASIGNACIÓN  El  problema  de  asignación  es  un  caso  particular  del  modelo  de  transporte,  el  cual  presenta dos características a ser tomadas en cuenta:  i) 

Las variables de decisión  X ij  solo toman valores de 1 o 0, transformándose  en variables binarias de aceptación o no aceptación. 

ii) 

Las ofertas y demandas son todas iguales a 1, por lo que  a  i  =  b j  = 1

El modelo de asignación consiste en asignar “ m ” centros de oferta a “ n ” centros de  demanda, debiendo realizarse la asignación uno a uno, con el objetivo de minimizar el  costo total asociado.  6.3.1  For mulación matemática del modelo de asignación  DESTINOS  O  R 

1 

2 

C11 

C12 

.  . 

C21  .  . 

C22  .  . 

. 

. 

. 

Cm1 

Cm2 

1 

1 

1  2 

I  G  E  N  E 

m 

…  …  … 

… 

n  C1n 

1 

C2n  .  . 

1 

. 

. 

Cmn

1 

S  Demanda 

… 

Oferta 

.  . 

1 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

95 

Ciencias Empresariales 

Investigación de Operaciones 

Para  determinar  la  solución  óptima,  se  utiliza  el  Algoritmo  Húngaro,  cuyo  procedimiento es:  PASO 1: Balancear el problema; es decir que:  N° de Or ígenes = N° de Destinos  i) Si  cero 

N° de Orígenes N° de Destinos 

→     Añadir columnas ficticias con costo 

igual a cero  iii) Si se quiere penalizar un Origen y/o destino 

→      Se utiliza como costo asociado 

M  PASO 2: Construir una nueva matriz de costos, donde aparezca por lo menos un Cero  en cada fila y columna (restar los valores menores de cada fila y/o columna 

con los demás  valores correspondientes de cada fila y/o columna ).  PASO 3: Probar una asignación tentativa en las posiciones con costo igual a cero; si ésta  es posible entonces el problema concluye, de lo contrario ir al paso 4.  PASO  4:  Prueba  de  optimalidad:  Trazar  el  Mínimo  Número  de  líneas  que  tachen  a  todos los ceros de la matriz.  PASO  5:  Seleccionar  el valor  más  pequeño  que no  este  cruzado  por  las  líneas;  éste  valor restar de todo elemento no tachado y sumar a todo elemento intersectado  por una línea horizontal y vertical.  PASO 6: Volver al paso 3 hasta encontrar la asignación óptima.  EJ EMPLO:  El gerente de una empresa de servicios integrales, debe tomar la decisión  de  asignar  a  3  de  sus  empleados  (Fabiola,  Wilson  y  Javier)  la  realización  de  3  tareas

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

96 

Ciencias Empresariales 

Investigación de Operaciones 

(Podar  el césped, pintar la  cochera y lavar  automóviles)  en  el domicilio de un cliente.  Los  costos  de  realizar  cada  una  de  las  actividades  por  parte  de  los  tres  empleados  se  muestra ne la tabla de costos siguiente:  PODAR 

PINTAR 

LAVAR 

FABIOLA 

15 

10 

9 

WILSON 

9 

15 

10 

JAVIER 

10 

12 

8 

Todos  los  valores  de  costo  están  dados  en  dólares.  Tomando  como  base  esta  información ¿Cuál deberá ser la asignación óptima que debe realizar el gerente para que  el costo sea el mínimo?  PODAR  PINTAR  LAVAR  Mínimo 

FABIOLA 

15 

10 

9 

9 

WILSON 

9 

15 

10 

9 

JAVIER 

10 

12 

8 

8 

ITERACIÓN 1:  PODAR  PINTAR  LAVAR  F 

6 

1 

0 

W 

0 

6 

1 

J 

2 

4 

0 

Mínimo 

0 

1 

0 

ITERACIÓN 2:  PODAR  PINTAR  LAVAR  F 

6 

0 

0 

W 

0 

5 

1 

J 

2 

3 

0

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

97 

Ciencias Empresariales 

Investigación de Operaciones 

Como  es  posible  asignar  a  cada  uno  de  los  empleados  una  sola  tarea,  entonces  es  la  solución con costo mínimo.  COSTO [$us.]  10 

EMPLEADO  FABIOLA 

TAREA  PINTAR 

WILSON 

PODAR 

9 

JAVIER 

LAVAR 

8  27 [$us.] 

COSTO TOTAL DE ASIGNACIÓN: 

v  Si suponemos que no se obtuvo la solución en el paso 3 (anterior solución), entonces  procedemos a optimizar realizando los pasos 4, 5 y 6.  ITERACIÓN 2: 

ITERACIÓN 3:  PODAR  PINTAR  LAVAR 

PODAR  PINTAR  LAVAR  F 

6 

0 

0 

F 

9 

0 

3 

W 

0 

5 

1 

W 

0 

2 

1 

J 

2 

3 

0 

J 

2 

0 

0 

NOTA: El valor elegido (3) se suma a los valores intersectados por una línea horizontal  y  una línea vertical  (6 y  0); los valores que no  están afectados por una intersección se  mantienen,  mientras  que  los  valores  que  no  están  atravesados  por  ninguna  línea  son  restados  con  el  valor  elegido  (3)  como  se  muestra  en  el  cuadro  correspondiente  a  la  Iteración 3. Posteriormente se procede a la asignación.  v  Como podemos observar, verificamos que la solución obtenida  anteriormente es la  solución óptima.  EJ ERCICIO:  El  jefe  de  producción  de  la  empresa  “MUEBLES  FÁTIMA”  debe  asignar la utilización de cuatro máquinas a cuatro operarios que requieren el uso de las  mismas. Los tiempos en minutos registrados del uso de cada máquina para realizar cada  uno de los trabajos, se muestran en el siguiente cuadro:  OP1 

OP2 

OP3 

OP4

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

98 

Ciencias Empresariales 

Usted 

como 

Investigación de Operaciones 

M1 

10 

5 

9 

18 

M2 

13 

19 

6 

12 

M3 

18 

9 

12 

17 

M4 

11 

6 

14 

19 

profesional 

entendido  en el  tema.  ¿Cuál  deberá  ser  la  asignación que  minimice el  tiempo  total  de  uso de las máquinas?  6.4  EL MODELO DE TRANSBORDO  Este modelo reconoce que en la vida real, tal vez resulte más económico enviar a través  de  nodos  intermedios  o  transitorios,  antes  de  llegar  al  punto  de  destino  final.  Este  concepto es más general que el propuesto por el modelo de transporte regular, donde los  envíos directos solo están permitidos entre puntos de origen y destino.  Para convertir un modelo de transbordo en un modelo de transporte regular , se utiliza  el concepto de Amortigüador ,  considerando que las  cantidades de oferta  y  la demanda  en los diferentes nodos se calculan de la siguiente manera: ·  Oferta en un nodo puro de oferta  ·  Oferta en un nodo puro de transbordo  ·  Oferta de un nodo de transbordo y demanda 

=  =  = 

Oferta original Amortigüador Amortiguador

·  Demanda de un nodo puro de demanda 

=  ·  Demanda de un nodo de transbordo y demanda =  Amortigüador

Demanda original Demanda  original 

·  Demanda de un nodo puro de transbordo 

Amortigüador  

i) 

= 

+ 

Nodo  pur o  de  Ofer ta:  Es  aquel  nodo  del  cual  salen  las  cantidades  (  nodo 

origen) 

1 

Nodo  pur o  de  demanda:  Es  aquel  nodo  al  cual  llegan  las  cantidades  ( nodo  destino )  ii) 

2

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

99 

Ciencias Empresariales 

Investigación de Operaciones 

Nodo de tr ansbor do:  Es aquel nodo al cual llegan y salen las cantidades ( nodo 

iii) 

intermedio)  3 

NOTA:  El  valor  del  amortigüador  debe  ser  suficientemente  grande  para  permitir  que  todas  las  ofertas  pasen  por  cualquiera  de  los  nodos  de  transbordo,  hasta  llegar  a  la  demanda final. Generalmente se considera que sea igual a la sumatoria de la oferta; es  decir: 

B = SOferta  EJ EMPLO: Una compañía de distribución tiene dos plantas (P­1, P­2), dos almacenes  mayoristas (A1, A2) y dos  tiendas  de  venta  al menudeo  (T1, T2 ). En la red  adjunta  se  presentan  las  capacidades  de  las  plantas,  las  demandas  de  las  tiendas  y  los  costos  de  transporte por unidad [$us./u.].  1  100 

6  A1 

P­1 

150 

T1 

4  1 

3 

5 

1

3  200 

P­2 

2  A2 

8 

T2 

150 

Primeramente identificamos los tipos de nodos que se presentan en la red ·  Nodos puros de oferta 

: 

·  Nodos puros de demanda 

: 

·  Nodos puros de transbordo 

: 

P­1 , P­2 T2 A1 , A2 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

100 

Ciencias Empresariales 

Investigación de Operaciones 

: 

·  Nodos de transbordo y demanda 

T1 

Ahora construimos la tabla de costos de transporte, identificando los orígenes, destinos  y el valor del amortigüador ·  Orígenes 

: 

P - 1 , P - 2 , A 1 , A 2 , T 1 

·  Destinos 

: 

A1 , A 2 , T 1 , T  2 

·  Valor del amortigüador 

B  =  300

: 

DESTINOS  Oferta  A1  O 

E  N  E  S 

T1 

T2 

P­1 

1 

4 

M 

M 

100 

P­2 

3 

2 

M 

M 

200 

A1 

0 

1 

6 

M 

300 

A2 

3 

0 

5 

8 

300 

M 

M 

0 

1 

R  I  G 

A2 

T1 

Demanda 

300  300 

300 

450 

150 

Mediante el M.E.N. se tiene la solución básica factible inicial (S.B.F.I.) 

DESTINOS  Oferta  A1  O  R  I 

P­1  P­2 

T2 

1 

4 

M 

M 

100 

3 

2 

M 

M 

200 

1 

6 

M 

300 

5 

8 

300 

0 

1 

200  A1 

N 

A2 

S 

T1 

100 

G  E  E 

A2 

T1 

0  300 

0  3  M 

0

0 

300 

M  150 

150 

300 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

101

Ciencias Empresariales 

Investigación de Operaciones 

Demanda 

300 

300 

450 

150 

SOLUCIÓN BÁSICA FACTIBLE INICIAL  Variables Básicas 

x11   = 100  x 21  = 200  x 31  = 0  x 32  = 300  x12   =  0  x 13  = 0  x 14  = 0  x 22  = 0 

Variables No Básicas 

x 42  = 0  x 43  = 300  x 53  = 150  x 54  = 150 

x 23  = 0  x 24  = 0  x 33  = 0  x 34  = 0 

x 41  = 0  x 44  = 0  x 51  = 0  x 52  = 0  z  =  2650 [$us. ] 

COSTO DE TRANSPORTE:

Luego aplicamos la etapa de optimalidad para obtener la solución óptima. 

DESTINOS  A1  O 

P­1  P­2 

G 

A1 

E  E  S 

1 

T1 

A2  T1 

3  200 ­ λ 

+ λ 

M 

M 

100 

u1  = 1 

2 

M 

M 

200 

u2  = 3 

6 

M 

300 

u3  = 0 

5 

8 

300 

u3  = ­ 1 

300 

u3  = ­ 6 

0 

1  150

Demanda 

300 

300 

450 

150 

v j 

v1  = 0 

v2  = 1 

v3  = 6 

v3  = 7 

u i  + v j  = c ij 

u i 

4 

0  1  0 + λ  300 ­ λ  3  0  0  300  M  M  150 

VARIABLES BÁSICAS 

Oferta  T2 

100 

R  I 

N 

A2 

VARIABLES NO BÁSICAS 

zij  - c ij  = c ij  - ( u i  + v j )

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

102 

Ciencias Empresariales 

Investigación de Operaciones 

z 12 - c 12  = 2  z 13  - c 13  = M  - 7  z 14  - c 14  = M  - 8  z 22  - c 22  = - 2  ¬ V . entra  z 23  - c 23  = M  - 9  z 24  - c 24  = M  - 10  z 33  - c 33  = 0  z 34  - c 34  = M  - 7  z 41  - c 41  = 4  z 44  - c 44  = 2  z 51  - c 51  = M  + 6  z 52  - c 52  = M  + 5 

Si  v 1 =  0  u 1  + v 1  = 1 ® u 1  = 1  u 2  + v 1  = 3 ® u 2  = 3  u 3  + v 1  = 0 ® u 3  = 0  u 3  + v 2  = 1 ® v 2  = 1  u 4  + v 2  = 0  ® u 4  = - 1  u 4  + v 3  = 5  ® v 3  = 6  u 5  + v 3  = 0  ® u 5  = - 6  u 5  + v 4  = 1 ® v 4  = 7  Variable que entra 

:  x 22 

Variable que sale 

:  x 21  porque  200 - l  = 0  Þ l = 200 

Con  el  valor  de l  = 200 procedemos  a  corregir  los  valores  de  las  variables  básicas  relacionadas con el circuito y se obtiene: 

DESTINOS  Oferta  A1  O  R 

P­1 

I 

P­2 

G 

A1 

A2  1 

T1 

T2 

4 

M 

M 

100 

2 

M 

M 

200 

1 

6 

M 

300 

5 

8 

300 

100 

E 

3  0  200 

100  3 

A2 

N  E 

T1 

S 

Demanda 

200 

M 

0 

0 

300 

M 

0  150 

300 

300 

450 

1  150

300 

150 

Siendo esta  última tabla la  solución óptima que nos da un costo de transporte  mínimo 

 

igual a z  =  2250 [$us. ] , representamos gráficamente ésta solución: 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

103 

Ciencias Empresariales 

Investigación de Operaciones 

100  100 

150  A1 

P­1 

1  100 

200 

T1 

300 

1 

150  1 

5 

200 

P­2 

A2 

150 

T2 

2 

EJ ERCICIO:  Dos  fábricas  de  automóviles  F1  y  F2  están  conectadas  a  tres  distribuidores D1, D2 y D3 , por medio de dos centros de tránsito T1 y T2 de acuerdo a  la  red  adjunta.  Las  cantidades  de  oferta  en  las  fábricas  F1  y  F2  son  de  1000  y  1200  automóviles, las cantidades de demanda en las distribuidoras D1, D2 y D3 son de 800,  900 y 500 automóviles respectivamente. El costo de envió por automóvil (en cientos de  dólares) entre los pares de nodos, se muestra en los eslabones (arcos) de conexión de la  red.  D1 

800 

8  1000 

3  F1

T1 

6 

4  7  2  1200 

5 D2 

900 

4 

F2 

3 

T2  5 

9  D3 

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

500 

104 

Ciencias Empresariales 

Investigación de Operaciones 

ÍNDICE  PROGRAMA ANAL ITICO..................................................................................................................1  I.  JUSTIFICACION ............................................................................................................................... 1  II.  OBJETIVO DE LA MATERIA ......................................................................................................... 1  III.  OBJETIVOS ESPECÍFICOS ..................................................................................................... 1  IV.  UNIDADES PROGRAMÁTICAS .............................................................................................. 2  V.  METODOLOGÍA DE LA ENSEÑANZA........................................................................................ 6  VII.  BIBLIOGRAFÍA............................................................................................................................. 6  BASICA: ................................................................................................................................................... 6  LAS ORIENTACIONES METODOLÓGICAS .................................................................................................7  1.  Introducción............................................................................................................................................. 7  1.1. Objetivos Generales.............................................................................................................................. 7  2.­ DESARROLLO. ........................................................................................................................................... 8  2.1.­ NÚCLEOS TEMÁTICOS....................................................................................................................... 8  2.2.­ BIBLIOGRAFÍA COMENTADA ........................................................................................................... 14  2.3.­ MATERIAL EXPLICATIVO ................................................................................................................. 14  2.4.­EJEMPLIFICACIÓN............................................................................................................................. 15  2.5.­ MÉTODOS A UTILIZAR ..................................................................................................................... 15  3.­  CONCLUSIONES................................................................................................................................. 16  UNIDAD 1 ..........................................................................................................................................17  INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES ..................................................17  1.1  Introducción .................................................................................................................................. 17  1.2  Origen de la Investigación de Operaciones................................................................................. 17  1.3  Precursores y estudiosos de la Investigación de Operaciones ................................................... 18  1.4  Naturaleza y alcance de la Investigación de Operaciones.......................................................... 19  1.5  Concepto de la Investigación de Operaciones ............................................................................ 21  1.6  Modelos matemáticos de Decisión y su Clasificación ............................................................... 21  1.6.1  Concepto de Modelo........................................................................................................... 21  1.6.2  Clasificación de  los Modelos matemáticos de decisión .................................................. 21  1.7  Metodología de la Investigación de Operaciones ....................................................................... 23  1.8  Aplicaciones de algunos modelos de la I.O. ............................................................................... 25  1.9  Beneficios de la aplicación de un proyecto de I.O ..................................................................... 25  UNIDAD 2 ..........................................................................................................................................27  FORMULACIÓN DEL MODELO DE PROGRAMACIÓN LINEAL ...............................................27  2.1  Introducción .................................................................................................................................. 27  2.2  Concepto de Programación Lineal............................................................................................... 27  2.3  Procedimiento para Formular un M.P.L...................................................................................... 27  2.3.1  Definición de Variables...................................................................................................... 27  2.3.2  Definición de la Función Objetivo .................................................................................... 28  2.3.3.  Restricciones Estructurales (o funcionales) ...................................................................... 28  2.3.4  Restricciones de No Negatividad....................................................................................... 29  2.4  Planteamiento de los recursos por unidad de actividad.............................................................. 30  2.5  Formas de presentación de un M.P.L. ......................................................................................... 30  2.5.1  Formulación canónica ........................................................................................................ 30  2.5.2  Formulación Mixta ............................................................................................................. 31  2.5.3  Formulación Estandar......................................................................................................... 31  2.6  EJERCICIOS DE FORMULACIÓN .......................................................................................... 31  2.7  EJERCICIOS PROPUESTOS (PRACTICO Nº 1) .................................................................... 38  UNIDAD 3 ..........................................................................................................................................42  MÉTODOS DE SOLUCIÓN DE UN M.P.L......................................................................................42  UNIDAD 4 ..........................................................................................................................................66

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

105 

Ciencias Empresariales 

Investigación de Operaciones 

TEORIA DE L A DUALIDAD.............................................................................................................66  4.1  Introducción .................................................................................................................................. 66  4.2  Definición...................................................................................................................................... 66  4.4  Comparación del modelo PRIMAL con el DUAL..................................................................... 67  4.5  Tabla resumen de transformación................................................................................................ 68  4.6  Interpretación económica de las variables duales....................................................................... 68  UNIDAD 5 ..........................................................................................................................................74  ANÁLISIS DE SENSIBILIDAD ........................................................................................................74  5.1  Introducción .................................................................................................................................. 74  5.2  Tipos de cambios en un M.P.L. ................................................................................................... 74  UNIDAD 6 ..........................................................................................................................................81  MODELO DE TRANSPORTE Y ASIGNACIÓN .............................................................................81  6.1  Introducción .................................................................................................................................. 81  6.2.  Modelo de transporte .................................................................................................................... 81  6.2.1  Formulación matemática del modelo de transporte.......................................................... 81  6.2.2  Matriz de Costos del modelo de transporte....................................................................... 82  6.3  MODELO DE ASIGNACIÓN .................................................................................................... 95  6.3.1  Formulación matemática del modelo de asignación......................................................... 95  6.4  EL MODELO DE TRANSBORDO............................................................................................ 99

Dirección de Educación a Distancia _UPDS_ Modalidad Cursos por Encuentros 

106