miércoles, 21 de junio de 2017

Método gráfico para resolver un problema de programación lineal de dos variables - 2 de 2

Ejemplo 2. Determinar la solución óptima del siguiente problema de programación lineal



Paso 1. Construcción de la región factible

En primer lugar trazamos los ejes coordenados con las variables x1 y x2 . Luego para poder graficar los semiplanos correspondientes a cada una de las restricciones debemos convertir las desigualdades en igualdades, porque la representación gráfica de una ecuación lineal con dos variables es una recta y graficarla es simple. Por tal motivo graficamos las rectas correspondientes a cada una de las restricciones del problema y después seleccionaremos el semiplano correspondiente a cada desigualdad.

La primera restricción del problema es 5x1 + 8x2 <= 50 , y para determinar el semiplano correspondiente, debemos graficar la recta 5x1 + 8x2 = 50 . Como sabemos, para poder graficar una recta es necesario conocer los dos puntos por donde debe pasar ésta, más aún si necesitamos saber en qué puntos corta la recta a los ejes coordenados, sólo debemos asignar el valor de cero a cada una de las variables, del siguiente modo:


De forma similar, si x2 = 0 al sustituir en la ecuación de la recta tenemos 5x1 + 8(0) = 50 , entonces x1 = 10 . Por tanto, tenemos el punto (x1, x2) = (10,0).
Finalmente podemos graficar la recta 5x1 + 8x2 = 50


Dado que la recta divide al plano cartesiano en dos semiplanos, ahora nuestro interés debe centrarse en determinar el semiplano que corresponde a la inecuación, es decir, cuál de los semiplanos creados por la ecuación corresponde a la restricción. Para tal fin, tomamos las siguientes condiciones generales, según el tipo de desigualdad que represente a la restricción:


Siguiendo esta condición, representamos la desigualdad 5x1 + 8x2 <= 50 correspondiente a la primera restricción del problema


De forma similar construimos los semiplanos de las otras dos restricciones

La segunda restricción del problema es 6x1 + 5x2 <= 60 , para determinar el semiplano correspondiente, debemos graficar la recta 6x1 + 5x2 = 60.
Si x1 = 0 , entonces x2 = 12. Por tanto, tenemos el punto (x1, x2)= (0,12).
Si x2 = 0 , entonces x1 = 10. Por tanto, tenemos el punto (x1, x2)= (10,0).
Finalmente podemos graficar la recta 6x1 + 5x2 = 60 y su respectivo semiplano 


La tercera restricción del problema es 8x1 - 5x2 <= 40 , para determinar el semiplano correspondiente, debemos graficar la recta 8x1 - 5x2 = 40.
Si x1 = 0 , entonces x2 = -8. Por tanto, tenemos el punto (x1, x2) = (0,-8).
Si x2 = 0 , entonces x1 = 5. Por tanto, tenemos el punto (x1, x2) = (5,0).
Finalmente podemos graficar la recta 8x1 - 5x2 = 40 y su respectivo semiplano


Una vez, graficadas las restricciones del problema, el siguiente paso importante es determinar la región factible, que representa el lugar geométrico donde se encuentra la solución óptima del problema lineal. En forma general la región factible, es determinada por la intersección de los semiplanos dentro del primer cuadrante, dado que las restricciones de no negatividad de las variables x1 ,x 2 >= 0 nos ubica en el primer cuadrante del plano cartesiano. Cabe aclarar que en algunos casos está intersección es vacía.
Siguiendo con el ejemplo, la región factible está limitada por el polígono, cuyos vértices son A, B, C y D como se muestra en la siguiente figura:


Paso 2: Determinación de la solución óptima.

La teoría nos muestra que la solución óptima se encuentra ubicada en uno de los vértices del polígono formado. Por tal motivo, una vez construida la región factible, debemos identificar los vértices del polígono que forma la región factible. Para esto debemos interceptar las rectas correspondientes a la primera y tercera restricción, es decir debemos resolver el siguiente sistema de ecuaciones:


La siguiente tabla muestra las coordenadas de los vértices y su respectivo valor en la función objetivo


Como la función objetivo es de maximización, al comparar los resultados en la función objetivo debemos elegir aquel punto que genere el mayor valor de la función objetivo, para este ejemplo el punto (0,25/ 4) genera el máximo valor. Por tal motivo se dice que el punto óptimo del problema lineal es el punto (0,25/ 4) y el valor máximo de la función objetivo es de 56.25.


Grafica de la función objetivo

A continuación vamos a graficar la función objetivo, con la finalidad de poder explicar la obtención del punto óptimo.

Dado que la función objetivo es Maximizar z = 4x1 + 9x2, podemos ver que dicha función objetivo es lineal, en otras palabras su representación geométrica es una recta, entonces para generar el lado derecho de la ecuación de la recta multiplicamos los coeficientes independientes obteniendo la recta 4x1 + 9x2 = 36

Ahora podemos graficar a la función Objetivo en forma similar a las ecuaciones de las restricciones:

Si x1 = 0 , entonces x2 = 4. Por tanto, tenemos el punto (x1,x2)=(0,4).
Si x2 = 0 , entonces x1 = 9. Por tanto, tenemos el punto (x1,x2)=(9,0).

Finalmente podemos graficar la recta objetivo 4x1 + 9x2 = 36.


Gráfica de la función objetivo en el punto óptimo

Una vez trazada la recta objetivo, debemos determinar la dirección que deberá seguir dicha recta para que la función objetivo aumente su valor. Para esto debemos hacer uso del concepto del gradiente, dado que este vector indica la dirección de crecimiento de una función de varias variables.

El gradiente de la función objetivo es determinado del siguiente modo


Este vector gradiente es perpendicular a la recta 4x1 + 9x2 = 36 y a partir de allí nos desplazaremos paralelamente siguiendo la dirección del vector gradiente, hasta que esta sea tangente a la región factible.

Dado que 4x1 + 9x2 = 36 tenemos como vector gradiente

Podemos ver que la recta con el mayor valor para z que intercepte la región factible, es aquella recta que pasa por el punto

dando como valor máximo 56.25.



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









  

No hay comentarios:

Publicar un comentario

       

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