Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 0 vistas

    EVALUACION 2

    Cargado por

    Rofeflex

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    EVALUACION 2

    Cargado por

    Rofeflex
    0 vistas8 páginas

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    0 vistas8 páginas

    EVALUACION 2

    Cargado por

    Rofeflex

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 8

    Método Grafico

    El método gráfico es un procedimiento de solución de problemas de


    programación lineal, muy limitado en cuanto al número de variables (2 si es un
    gráfico 2D y 3 si es 3D) pero muy rico en materia de interpretación de
    resultados e incluso análisis de sensibilidad. Este consiste en representar cada
    una de las restricciones y encontrar en la medida de lo posible el polígono
    (poliedro) factible, comúnmente llamado el conjunto solución o región factible,
    en el cual por razones trigonométricas en uno de sus vértices se encuentra la
    mejor respuesta

    Problema de única solución.


    Problema de múltiples soluciones.
    Problema de solución indeterminadas.
    Problema sin solución.

    Una solución óptima única:


    Método Simplex

    método simplex es usado especialmente para explorar la relación de dualidad


    La función objetivo debe ser de maximización.
    Las variables de decisión no negativas.
    Las restricciones son del tipo ≤

    Factibilidad
    En Programación Lineal una Solución Básica Factible (SBF) es aquella que
    además de pertenecer a la región o área factible del problema se puede
    representar a través de una solución factible en la aplicación del Método
    Simplex satisfaciendo las condiciones de no negatividad.
    Vértice
    Si esto lo llevamos al poliedro solución, la solución básica factible
    corresponderá a uno de los vértices del dominio de factibilidad cuya
    coordenada o solución se puede representar a través de un conjunto de
    restricciones activas para el modelo.
    Base
    Conjunto de variables básicas.
    Forma estándar
    Es la igualación de las restricciones del modelo planteado, así como el
    aumento de variables de holgura, o bien la resta de variables de exceso.
    Forma canónica
    La forma canónica en método simplex es usado especialmente para explorar la
    relación de dualidad, donde un problema de programación lineal se encuentra
    en la forma canónica si se cumple las siguientes condiciones:

    Para el caso de la forma canónica de maximización:


    La función objetivo debe ser de maximización.
    Las variables de decisión no negativas.
    Las restricciones son del tipo ≤
    Para el caso de la forma canónica de minimización.
    La función objetivo es minimizada
    Las restricciones son del tipo ≥
    Las variables de decisión son no negativas.

    Variables de entrada
    Estas suelen encontrarse en un criterio que se conoce como “Condición de
    optimalidad”, en un modelo, ya sea de maximización o minimización, y se
    refiere a la variable no básica en el renglón “z” con el coeficiente más
    negativo, si se trata de una maximización, o el coeficiente más positivo, si se
    trata de una minimización, la cual, en la tabla de solución anterior, a excepción
    de la primera tabla, esta variable era una variable básica.

    Variables de salida
    Esta variable es un punto extremo que se encuentra en un criterio conocido
    como “condición de factibilidad”, en un modelo, ya sea de optimización o
    minimización, y se refiere a la variable básica asociada con la mínima razón no
    negativa con el coeficiente más negativo, si se trata de una maximización, o el
    coeficiente más positivo, si se trata de una minimización, la cual, en la tabla de
    solución siguiente, pasará a ser variable no básica.

    Espacio de soluciones en forma de ecuación:


    Para estandarizar, la representación algebraica del espacio de soluciones de
    programación lineal se forma bajo dos condiciones: 1. Todas las restricciones
    (excepto las de no negatividad) son ecuaciones con lado derecho no negativo.
    2. Todas las variables son no negativas.

    Conversión de desigualdades a ecuaciones


    En las restricciones (≤), el lado derecho se puede imaginar como
    representando el límite de disponibilidad de un recurso, y en ese caso el lado
    izquierdo representaría el uso de ese recurso limitado por parte de las
    actividades (variables) del modelo. La diferencia entre el lado derecho y el lado
    izquierdo de la restricción (≤) representa, por consiguiente, la cantidad no
    usada u holgura del recurso.
    Para convertir una desigualdad (≤) en ecuación, se agrega una variable de
    holgura al lado izquierdo de la restricción.
    Reddy Mikks produce pinturas para interiores y exteriores, M1 y M2. La tabla
    siguiente proporciona los datos básicos del problema.

    Una encuesta de mercado indica que la demanda diaria de pintura para


    interiores no puede ser mayor que 1 tonelada más que la de pintura para
    exteriores. También, que la demanda máxima diaria de pintura para interiores
    es de 2 toneladas. Reddy Mikks desea determinar la mezcla óptima (la mejor)
    de productos para exteriores y para interiores que maximice la utilidad diaria
    total.
    La restricción asociada con el uso de la materia prima M1 está dada como:

    6𝑥1 +4𝑥2 ≤ 24

    Si se define 𝑠1 como la holgura, o cantidad no usada, de M1, la restricción se


    puede convertir en la siguiente ecuación:

    6𝑥1 +4𝑥2 +𝑠1 ≤ 24,𝑠1 ≥ 0


    Una restricción (≥) establece, normalmente, un límite inferior para las
    actividades del modelo de programación lineal. Como tal, la cantidad por la
    que el lado izquierdo es mayor que el límite mínimo (lado derecho) representa
    un excedente.
    La conversión de (≥) a (=) se logra restando una variable de excedencia, del
    lado izquierdo de la desigualdad. Por ejemplo, en el siguiente problema de la
    dieta:
    En Granjas Modelo se usa diariamente un mínimo de 800 libras (lb) de un
    alimento especial, que es una mezcla de maíz y soya, con las composiciones
    siguientes:
    Las necesidades dietéticas del alimento especial son un mínimo de 30% de
    proteínas y un máximo de 5% de fibras. Granjas Modelo desea determinar las
    proporciones de alimento que produzcan un costo diario mínimo.
    La restricción que representa los requisitos mínimos de alimento está dada
    como:

    X1 +𝑥2 ≥800
    Si se define a S1 como una variable de excedencia se puede convertir la
    restricción en la ecuación siguiente:

    X1 +𝑥2 −𝑆1 =800, 𝑆1 ≥ 0


    Es importante observar que las variables de holgura y de excedencia, s1 y S1,
    siempre son no negativas. El único requisito que queda es que el lado derecho
    de la ecuación que resulte sea no negativo. Esta condición se puede satisfacer
    siempre, si es necesario multiplicando ambos lados de la ecuación resultante
    por –1. Por ejemplo, la restricción

    −𝑥1 +𝑥2 ≤−3


    equivale directamente a la ecuación

    −𝑥1 +𝑥2 +𝑠1 =−3, 𝑠1 ≥0


    Ahora se multiplican ambos lados por –1, y se obtiene un lado derecho no
    negativo, que es lo que se busca; esto es,

    X1 −𝑥2 −𝑠1 = 3
    Dualidad
    La dualidad en la programación lineal es importante tanto del lado teórico
    como del lado práctico. Para cada modelo lineal se puede escribir el modelo
    dual asociado. Veremos que resolviendo uno de los modelos se obtiene la
    solución de ambos; en la tabla optima del modelo resuelto aparece también la
    solución óptima del dual asociado. Algunas razones por las que conviene tener
    en cuenta la dualidad son las siguientes:
    1. Teniendo en cuenta que el número de iteraciones del algoritmo simplex
    depende más del número de restricciones del modelo que del número de
    variables, y dado que resolviendo un modelo lineal se obtiene también la
    solución del dual asociado, se puede elegir el modelo que conviene resolver
    para obtener la solución de ambos.
    2. La dualidad permite hacer la interpretación económica del problema lineal.
    Veremos que la solución del problema dual da información acerca de la
    solución del primal.
    3. Teniendo en cuenta las propiedades de la dualidad se construye un nuevo
    algoritmo, el simplex dual, que es más eficaz que el simplex para calcular la
    solución optima de algunos modelos lineales. además, este nuevo algoritmo se
    aplica en el análisis de sensibilidad y la programación entera que se presentan
    en temas posteriores.
    Relaciones de dualidad.

    Holgura complementaria
    Las condiciones de holgura complementaria permiten calcular la solución
    optima del dual a partir de la solución ´optima del primal y viceversa. Dichas
    condiciones son consecuencia del siguiente teorema
    Teorema 1

    Dadas dos soluciones factibles 𝑥∗ 𝑒 𝑦∗ para el primal y dual respectivamente,


    son óptimas si y solo si se verifica

    x∗𝑻(𝑨𝑻𝒚 −𝒄) +𝒚∗𝑻(𝒃−𝑨𝒙 ) = 𝟎


    ∗ ∗

    La interpretación de este resultado proporciona las condiciones de holgura


    complementaria. Recordemos que en todos los casos se tienen en cuenta las
    formas primal y dual simétricas
    Interpretación de las condiciones

    Dadas soluciones optimas 𝑥∗ 𝑒 𝑦∗ del primal y del dual, respectivamente, las


    restricciones de ambos problemas se pueden escribir de la siguiente forma:

    (𝒃 −𝑨𝒙 ) ≥ 𝟎
    ∗

    A𝑻𝒚 −𝒄 ≥𝟎
    ∗

    Por otra parte, las soluciones óptimas para el primal y el dual, 𝑥∗ 𝑒 𝑦∗ , son

    las desigualdades anteriores por 𝑥∗𝑇 𝑒 𝑦∗𝑇, respectivamente, se tienen las


    vectores que no tienen componentes negativas. Por tanto, si premultiplicamos

    desigualdades

    x∗𝑻(𝑨𝑻𝒚 − 𝒄 ) ≥ 𝟎
    ∗

    y∗𝑻(𝒃 −𝑨𝒙∗) ≥ 𝟎

    La tesis del teorema de holgura complementaria asegura que la suma de los


    dos primeros miembros de las desigualdades anteriores es cero y, teniendo en
    cuenta que los dos sumandos son mayores o iguales que cero, podemos
    concluir que los dos sumandos deben ser cero simultáneamente, es decir

    x∗𝑻(𝑨𝑻𝒚 − 𝒄 ) = 𝟎
    ∗

    y∗𝑻(𝒃 −𝑨𝒙 ) = 𝟎
    ∗

    En las dos ecuaciones anteriores se tiene el producto de dos factores no


    negativos igualado a cero; si uno de los factores no es cero debe ser cero el
    otro. así, se pueden extraer las siguientes conclusiones que permiten calcular
    la solución de un problema conocida la del otro.
    Si una variable primal es estrictamente positiva, la correspondiente restricción
    dual se verifica con igualdad, no requiere variable de holgura positiva. Es decir,
    x > 𝟎 ⇒ 𝑨𝑻𝒚 −𝒄=𝟎
    ∗ ∗

    Si una restricción primal no se verifica con igualdad, la correspondiente


    variable dual toma el valor cero. Es decir

    𝒙 < 𝒃 ⇒ 𝒚∗=𝟎
    ∗

    Si una variable dual es estrictamente positiva, la correspondiente restricción


    primal se verifica con igualdad. Es decir,

    y > 𝟎 ⇒ 𝑨𝑻𝒙 −𝒃=𝟎


    ∗ ∗

    Si una restricción dual no se verifica con igualdad, la correspondiente variable


    primal tomara el valor cero. Es decir,

    A𝑻𝒚 > 𝒄 ⇒𝒙 = 𝟎
    ∗ ∗

    También podría gustarte