viernes, 28 de septiembre de 2012

Modelos de programación lineal - Investigación de Operaciones

Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente:

"Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a una serie de restricciones, expresadas por inecuaciones lineales"

Así un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

La formulación del problema a ser solucionado por programación lineal sigue algunos pasos
básicos:
  • Debe ser definido el objetivo básico del problema, es decir la optimización a ser alcanzada. Por ejemplo maximizar ganancias, desempeños o bienestar social; minimizar costos, perdidas, tiempo. Tal objetivo será representado por una función objetivo, a ser maximizada o minimizada.
  • Para que esta función objetivo sea matemáticamente especificada, deben ser definidas las variables de decisión involucradas. Por ejemplo, número de máquinas, área a ser explorada, etc. Normalmente se asume que todas estas variables poseen solamente valores positivos.
  • Estas variables están sujetas a una serie de restricciones, normalmente representadas por inecuaciones. Por ejemplo, cantidad de equipos disponibles, tamaño del área a ser explorada, etc.
Todas las expresiones, deben estar de acuerdo con la hipótesis principal de la programación
lineal, es decir todas las relaciones entre las variables deben ser lineales. Esto implica
proporcionalidad de las cantidades envueltas.

A continuación desarrollamos algunos ejemplos que nos permitirá conocer un poco más
acerca de los problemas de programación lineal.

Problema 1.1.

Yemito es un aficionado de los juguetes electrónicos y planeando construir dos tipos de juguetes electrónicos (Ben10 y DinoRey). Él sabe que para construir un juguete Ben10 debe utilizar 9 sensores electrónicos y 3 horas de trabajo. Mientras que para construir un DinoRey utiliza 1 sensor electrónico y 1 hora de trabajo. Yemito pidió a su papá comprar los sensores electrónicos, pero éste sólo compro 18 sensores electrónicos. A la vez Yemito suele despertar a las 8:00 am y dormir a las 8:00 pm, por tal motivo dispone de 12 horas para trabajar en la construcción de los juguetes. Yemito tiene planeado vender estos juguetes en su escuela, obteniendo una utilidad de 4 dólares por cada juguete Ben10 y un dólar por cada juguete DinoRey. Por otro lado, sabiendo que Yemito logra vender todos los juguetes construidos se debe elaborar un modelo de programación lineal para optimizar sus utilidades.

Solución:

Para elaborar el modelo de programación lineal seguimos los siguientes pasos:

1. Definición de las variables de decisión:

En este caso estamos interesados en saber cuántos juguetes Ben10 y DinoRey debe construir, por tal motivo declaramos las variables de decisión de la siguiente forma:

x1 : Cantidad de juguetes Ben10 construidos
x2 : Cantidad de juguetes DinoRey construidos

Una vez declaradas las variables de decisión, debemos expresar la función objetivo utilizando dichas variables.

2. Elaboración de la función objetivo:

Dado que nuestro propósito es maximizar la utilidad total y sabemos que por la fabricación de un Ben10 tenemos una utilidad de 4 dólares, entonces la utilidad total generada por el modelo ben10 es de $ 4x1 , de igual forma el modelo DinoRey genera una utilidad de $1 x2 .
Por tanto si queremos obtener la utilidad total generada por la fabricación de los dos
juguetes tendremos z = 4x1 + x2 .
Como nuestro objetivo es maximizar la utilidad, tenemos la siguiente función objetivo:

Max z = 4x1 + x2 . 

3. Formulación de las restricciones tecnológicas:

Antes de construir las restricciones del problema, debemos tener presente las siguientes
observaciones:
  • No se puede utilizar lo que no se tiene. 
  • La cantidad utilizada debe ser menor o igual a la cantidad disponible


  • Restricción de sensores electrónicos
Sabemos que disponemos de 18 sensores electrónicos y que para fabricar un Ben10, se
necesita de 9 sensores electrónicos y para un DinoRey se necesita 1 sensor electrónico. Por tanto podemos decir que 9x1 + x2 <= 18 .


  • Restricción de horas de trabajo
De igual modo, se dispone de 12 horas de trabajo, pero para fabricar un Ben10 se
necesita 3 horas de trabajo y para un DinoRey se necesita 1 hora de trabajo. Por tanto
podemos decir que 3x1 + x2 <= 12 .


  • Restricciones de no negatividad
Dado que las variables de decisión sólo pueden tomar valores no negativos, es decir,
mayores o iguales a cero tenemos que x1 >= 0 y x2 >= 0 .

4. Modelo final:

Finalmente podemos expresar el modelo de programación lineal de la forma siguiente

Max z = 4x1 + x2

sujeto a:

9x1 + x2 <= 18

3x1 + x2 <= 12

x1, x2 >= 0


Observaciones:

Para determinar la función objetivo debe tomarse en cuenta lo siguiente:

  1. Si tenemos como datos solo costos ya sean de materia prima, mano de obra, uso de máquina, transporte, depreciación, etc. Nos indica indudablemente que la Función Objetivo (F.O.) será de MINIMIZACIÓN.
  2. Si el enunciado solo tiene datos económicos de ganancia, precio de venta o dinero a recibir por unidad producida la F.O. será de MAXIMIZACIÓN. 
  3. Si el enunciado tiene datos de costos y ganancias, entonces construimos la F.O. de la siguiente manera: GANANCIAS - COSTOS =UTILIDAD, la que tendrá como F.O. MAXIMIZAR.
  4. Si no se tiene ningún dato económico y solo se tienen tiempos, el tiempo se minimiza, si nos da solo producción, la producción se ha de maximizar, si el modelo corresponde a contratar personal, la función objetivo se debe minimizar.
  • Las restricciones o limitaciones en los modelos lineales se representan por desigualdades o igualdades: <= , >= , =
Muchos problemas tienen expresiones características que nos pueden anunciar que tipo de restricción debemos usar, por ejemplo:
Usar              |                      Para expresiones como:


<=                                        Cómo máximo, a lo más, disponibilidad, demanda máxima.

>=                                        Cómo mínimo, por lo menos, al menos, demanda mínima.
=                                           Total, proporción


  • Las restricciones deben tener las mismas unidades en tanto en su lado izquierdo como derecho. 
  • La no negatividad de algunas variables es muy importante para definir la solución de algunos modelos, por lo tanto se dice que todas las variables son >= 0.
A partir de ahora mostraremos una gran variedad de aplicaciones de modelos lineales con la finalidad de que se familiarice con los modelos de programación lineal. Para este fin se ha etiquetado a los problemas según su nivel de dificultad, por tal motivo al lado derecho de cada problema colocamos un icono que identificará el nivel de dificultad.  En la siguiente tabla se muestran los niveles de los problemas y sus respectivos iconos de  identificación.



Espero haber ayudado en algo. Hasta la próxima oportunidad!


2 comentarios:

  1. Respuestas
    1. Hola tapia patron, gracias por la visita y el aporte de tu comentario...
      Es muy grato el calificativo que le das a la página!!!...

      Mis mejores deseos!! Hasta cualquier momento!!!

      Eliminar

       

Etiquetas

Academy (23) Accediendo a datos con ADO .NET (31) Acceso a la red (30) Algoritmo (34) Algoritmos en JAVA (2) Ampliación de clases (2) APRENDA A PROGRAMAR COMO SI ESTUVIERA EN PRIMERO - Autores : IKER AGUINAGA (3) APRENDA A PROGRAMAR COMO SI ESTUVIERA EN PRIMERO - Autores : IKER AGUINAGA (10) Aprendiendo a desarrollar en Windows 8 (5) Aprendiendo UML en 24 Horas (Autor : Joseph Schmuller ) (30) Arquitectura (29) Arquitectura del Computador (3) Arquitectura del Computador - Historia de la informática (1) Asignación de direcciones IP (23) Aspectos fundamentales de bases de datos (5) Auditoría de la dirección (2) Auditoría de Sistemas (3) Auditoría Informática - Un enfoque práctico - Mario G . Piattini y Emilio del Peso (7) Avanzado (23) Base de Datos (67) Básico (23) Bios (29) Business Productivity Online Suite - BPOS (3) Capa de Red (22) Capa de Transporte (16) Capítulo 1 - Documentos HTML5 (6) Capítulo 10. API Web Storage (2) Capítulo 11. API IndexedDB (4) Capítulo 12. API File (1) Capítulo 2. Estilos CSS y modelos de caja (7) Capítulo 3. Propiedades CSS3 (4) Capítulo 4. Javascript (6) Capítulo 5. Video y audio (6) Capítulo 6. Formularios y API Forms (8) Capítulo 7. API Canvas (5) Capítulo 8. API Drag and Drop (2) Capítulo 9. API Geolocation (2) CCNA1 v5.0 (212) CCNA1 v6.0 (23) CCNA2 v5.0 (26) CCNA3 v5.0 (25) CCNA4 v5.0 (23) CD-ROM (3) Chapter 1 How does Xamarin.Forms fit in? (7) Chapter 2 Anatomy of an app (5) Cisco (314) Cloud Computing (3) CNNA v5.0 Routing & Switching (233) CNNA v6.0 Routing & Switching (2) Codigo (2) Computadora (32) Configuración (29) Configuración de un sistema operativo de red (21) Control (29) Creación de tipos de datos y tablas (3) Creación y Administración de bases de datos (3) Creando la Interface de la Aplicación Windows (50) Creating Mobile Apps with Xamarin.Forms (13) Cuenta (29) Curso (32) Curso Aprendiendo a Programar (25) Datos (3) Desarrollando en Windows 8 - AVANZADO (2) Desarrollando en Windows 8 - BÁSICO (3) Desarrollando en Windows 8 - INTERMEDIO (2) Desarrollo (2) Desarrollo .Net (21) Desarrollo avanzado de Windows Store Apps usando C# (1) Desarrollo basado en conceptos de Ingeniería de Software para Visual Studio (2) DESARROLLO DE APLICACIONES WINDOWS CON MICROSOFT .NET (37) DESARROLLO DE APLICACIONES WINDOWS CON MICROSOFT .NET (Autor: Luis Dueñas Huaroto) (29) Desarrollo en Microsoft Visual Studio (44) Desarrollo en Microsoft Visual Studio - AVANZADO (15) Desarrollo en Microsoft Visual Studio - BÁSICO (14) Desarrollo en Microsoft Visual Studio - INTERMEDIO (18) Desarrollo en Windows Phone 8 (13) Diagnostico (4) Diagrama (3) Diagramas de actividades (2) Diagramas de colaboraciones (2) Diagramas de secuencias (2) Digital (2) Diplomado (2) Disco (29) Disco Duro (4) Diseño de aplicaciones de Windows 8 en HTML 5 (7) Dispositivos Electrónicos (11) Doctorado (2) Ejemplos (3) Ejemplos de algoritmos (27) El camino hacia el CSS3 (3) El diseño web flexible (6) El elemento de diseño Canvas (3) El enfoque de los sistemas (3) El flujo de un programa (2) El gran libro de HTML5 - CSS3 y Javascript - Autor: Juan Diego Gauchat (55) El principio de organicidad (7) Electrónica (2) Elementos de un sistema (5) Empresas (2) Entrada y salida (4) Entropía y neguentropía (7) Estrategia (2) Estructura de un programa Java (12) Estructuras de almacenamiento (10) Estructuras de control (6) Estructuras de las tablas en SQL Server (2) Estructuras fundamentales de los datos (2) Ethernet (21) Evolución y Familias de los Microprocesadores (15) Exámen (23) Exploración de la red (23) Extensión de clases (4) Facebook (4) Familia Intel (15) Forefront (8) Función (3) Funciones de una red (12) Funciones de una red informática (1) Fundamentos de C# para absolutos principiantes (17) Fundamentos de programación en Java (50) Generaciones de la computadora (5) Gestión (3) Gestión de riesgos - Auditoría de Sistemas (1) GONZALO MARTÍNEZ (1) Grupos Facebook (1) Harvard (29) Historia de las computadoras (11) HTML5 y CSS3 - Autor: Christophe Aubry (99) HTML5 y CSS3 aplicadal texto (7) HTML5 y CSS3 para los formularios (15) Imágenes (2) Implementación de Windows 7 (11) Información (31) Informática (29) Ingeniería (4) Instalar (29) Inteligencia (2) Inteligencia de Negocios con SQL Server (3) Intermedio (23) Internet (29) Internet Explorer 9 (3) Introducción a ASP.NET 5 (8) Introducción a Java (7) Introducción a jQuery (8) Introducción a la Auditoría de Sistemas (2) Introducción a la teoría general de sistemas (Oscar Johansen Bertoglio) (39) Introducción a Networking (2) Introducción a Window Forms (5) Introducción al acceso a datos con ADO .NET (9) Investigación de Operaciones (12) Java (52) Jump Start de consultas en las bases de datos de Microsoft SQL Server 2012 (8) La definición de un Sistema (6) La evolución del HTML y del CSS (3) La nueva sintaxis HTML5 (12) LA QUINTA DISCIPLINA en la práctica (Autor : Peter Senge) (28) Las animaciones en CSS3 (5) Las transformaciones CSS3 (11) Las transiciones con CSS3 (8) Licenciamiento Microsoft (3) Local Area Network (LAN) - Red de Area Local (2) Lógico (2) Los elementos de la estructura en html5 (9) Los elementos multimedia: audio y vídeo (2) Los estilos de caja en CSS3 (13) Los nuevos selectores de CSS3 (6) Maestría (2) Mantenimiento de Mouse y Teclado (2) Manual de Microsoft SQL Server - Full Transact SQL (68) Manual de soporte técnico para escuelas sobre windows 7 (42) Marco Teorico de Investigación de Operaciones (6) Medios de Almacenamiento (11) Medios de Networking (2) Mejorando la Interface de las Aplicaciones Windows (26) Memoria Tipos y Clases (5) Método (2) Metodología (1) Microsoft (324) Microsoft Lync 2010 (7) Microsoft Silverlight 4.0 (2) Microsoft Virtual Academy (356) Modelo (2) Modelo OSI y TCP-IP (2) Modelos con poco grado de dificultad de Programación Lineal - Investigación de Operaciones (13) Modelos con razonable grado de dificultad de Programación Lineal - Investigación de Operaciones (10) Modelos de desafio de Programación Lineal - Investigación de Operaciones (5) Modelos difíciles de Programación Lineal - Investigación de Operaciones (5) Modelos Fáciles de Programación Lineal - Investigación de Operaciones (13) Modelos lineales con solver (3) Modulo (23) Movimiento (2) Mozilla (29) MS SQL Server (77) MS Virtualization para Profesionales VMware - Gestión (3) MS Virtualization para Profesionales VMware- Plataforma (4) MVA (263) Negocio (2) Nivel Avanzado Desarrollo .Net (6) Nivel Básico Desarrollo .Net (11) Nivel Intermedio Desarrollo .Net (8) Normas técnicas peruanas y su evolución - Auditoría de Sistemas (1) Nube Privada - Avanzado (6) Nube Privada - Básico (6) Nube Privada - Intermedio (6) Office 365 (3) Optimización de Escritorio (10) Optimización de Escritorio - Avanzado (4) Optimización de Escritorio - Básico (3) Optimización de Escritorio - Intermedio (3) ORACLE 10g - ADMINISTRACIÓN Y ANÁLISIS (3) Oracle 10g y el Grid Computing (3) Organización aleatoria y secuencial (1) Partes principales de la Mainboard (12) Perceptron (2) Perfil (2) Periféricos de Entrada / Salida (15) Pesi (2) PHP y MySQL - Manual de aprendizaje para crear un sitio web - Autor : Olivier ROLLET (79) Plan (2) Plataforma (29) PMBOK (24) PMBOK - Guía de los fundamentos para la dirección de proyectos (24) PMBOK - INFLUENCIA DE LA ORGANIZACIÓN Y CICLO DE VIDA DEL PROYECTO (6) PMBOK - Introducción (11) PMBOK - PROCESOS DE LA DIRECCIÓN DE PROYECTOS (5) Prevención - Herramientas e Instrumentos de Medida (9) Principios básicos de enrutamiento y switching (186) Proceso (2) Proceso de auditoría de sistemas informáticos (2) Programación en Android - Auor : Salvador Gómez Oliver (46) Programación paso a paso de C# - Autor : Nacho Cabanes (16) Protocolos y comunicaciones de red (17) Proyecto (2) Qué es un sistema (4) Red de Área Local Inalámbrica (WLAN) (4) Redes (30) Redes inalámbricas - WIRELESS - Conocimiento general (15) Redes neuronales (2) Redes y Comunicaciones (45) Reparación de Fuentes - UPS - Estabilizadores (10) Reparación de Impresoras (9) Reparación de Monitores (16) Router (29) Seguridad en la Nube (3) Seminario (23) Server (24) Sharepoint 2010 - Nivel Básico (6) Sharepoint 2010 - Niveles Avanzados (18) Sharepoint 2010 - Niveles Avanzados - Básico (8) Sharepoint 2010 - Niveles Avanzados - Intermedio (9) Sinergia y recursividad (4) Sistema (33) Sistema de Cableado Estructurado (9) Software (30) SOLUCIÓN GRÁFICA DE MODELOS DE PROGRAMACIÓN LINEALES - INVOPE (8) Soporte a Infraestructura (3) SQL (38) SQL Azure - Introducción (3) Subsistemas de control (4) Tablas (4) Tarjeta Principal del Sistema (10) Tarjetas de Interfaces (7) Tecnología (31) Tecnologías LAN (1) TEORÍA GENERAL DE SISTEMAS (1) Tic (2) Tipo (2) TML5 y CSS3 - Autor: Christophe Aubry (12) Trabajando con el Formulario (7) Un diseño HTML5/CSS3: dConstruct 2011 (3) Un diseño HTML5/CSS3: FlipThru (2) Un diseño HTML5/CSS3: The Cat Template (2) Usando Controles Windows Forms (12) Usando Herramientas de Datos de Visual Studio (6) Ventas (2) Virtualización Hyper - V Nivel Básico (5) Virtualización Hyper - V Nivel Intermedio (5) What’s New in Windows 8.1 Security (4) Window (29) Windows 7 Segunda Fase - AVANZADO (4) Windows 7 Segunda Fase - BÁSICO (6) Windows 7 Segunda Fase - INTERMEDIO (4) Windows 8 - Vista Previa (4) Windows 8.1 To Go (2) Windows Azure (3) Windows Phone 7 (2) Windows Server 2008 R2 (3) Windows Server 2012 - Gestión y Automatización (3) Windows Server 2012 R2 Essentials (7) Windows Server 2012: Almacenamiento (5) Windows Server 2012: Identidad y Acceso (4) Windows Server 2012: Revisión Técnica (7) Xamarin (1)

Páginas vistas en total según Google