Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 102 vistas

    Reglas de Equivalencia

    Cargado por

    Duck Antony Villalobos
    Este documento presenta las reglas de equivalencia y el método simplex para resolver problemas de programación lineal. Explica cómo transformar problemas de programación lineal a la forma canónica mediante reglas de equivalencia, y cómo aplicar el método simplex iterativamente para encontrar la solución óptima mediante la selección de variables de entrada y salida que generen una nueva base en cada iteración.

    Copyright:

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

    Reglas de Equivalencia

    Cargado por

    Duck Antony Villalobos
    102 vistas17 páginas
    Este documento presenta las reglas de equivalencia y el método simplex para resolver problemas de programación lineal. Explica cómo transformar problemas de programación lineal a la forma canónica mediante reglas de equivalencia, y cómo aplicar el método simplex iterativamente para encontrar la solución óptima mediante la selección de variables de entrada y salida que generen una nueva base en cada iteración.

    Descripción original:

    Algebra

    Título original

    3. Reglas de equivalencia

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta las reglas de equivalencia y el método simplex para resolver problemas de programación lineal. Explica cómo transformar problemas de programación lineal a la forma canónica mediante reglas de equivalencia, y cómo aplicar el método simplex iterativamente para encontrar la solución óptima mediante la selección de variables de entrada y salida que generen una nueva base en cada iteración.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    102 vistas17 páginas

    Reglas de Equivalencia

    Cargado por

    Duck Antony Villalobos
    Este documento presenta las reglas de equivalencia y el método simplex para resolver problemas de programación lineal. Explica cómo transformar problemas de programación lineal a la forma canónica mediante reglas de equivalencia, y cómo aplicar el método simplex iterativamente para encontrar la solución óptima mediante la selección de variables de entrada y salida que generen una nueva base en cada iteración.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 17

    Reglas de equivalencia

    a) La inecuación 𝐴𝑥 ≤ 𝑏 puede ser escrita como


    − 𝐴𝑥 ≥ −𝑏
    Ej.
    5𝑥1 + 3𝑥2 ≤ 6
    es equivalente a:
    −5𝑥1 − 3𝑥2 ≥ −6
    La inecuación 𝐴𝑥 ≥ 𝑏
    Regla 1 a)
    − 𝐴𝑥 ≤ −𝑏
    es equivalente a

    Ej.
    6𝑥1 − 3𝑥2 ≥ −8
    es equivalente a:
    −6𝑥1 + 3𝑥2 ≤ 8
    a) La expresión m𝑎𝑥 𝑧 = 𝑐𝑥 es equivalente a:
    m𝑖𝑛 −𝑧 = −𝑐𝑥

    Ej.

    𝑚𝑎𝑥 𝑧 = 4𝑥1 − 3𝑥2 es equivalente a:

    Regla 2 b)
    𝑚𝑖𝑛 −𝑧 = −4𝑥1 + 3𝑥2

    La expresión m𝑖𝑛 𝑧 = 𝑐𝑥 es equivalente a:


    m𝑎𝑥 −𝑧 = −𝑐𝑥

    Ej.

    𝑚𝑖𝑛 𝑧 = 4𝑥1 − 2𝑥2 + 3𝑥3 es equivalente a:


    𝑚𝑎𝑥 −𝑧 = −4𝑥1 + 2𝑥2 − 3𝑥3
    Toda igualdad del tipo 𝐴𝑥 = 𝑏 puede ser escrita
    como la intersección de dos desigualdades de la
    forma: 𝐴𝑥 ≤ 𝑏 y 𝐴𝑥 ≥ 𝑏

    Regla 3 Ej.
    4𝑥1 + 3𝑥2 = 7 𝑒𝑠 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎:
    4𝑥1 + 3𝑥2 ≤ 7

    y
    4𝑥1 + 3𝑥2 ≥ 7
    a) Toda desigualdad del tipo 𝐴𝑥 ≤ 𝑏 puede ser
    escrita como una igualdad con la adición de un
    Regla 4 vector y ≥ 0 llamado de holgura

    Ej.
    4𝑥1 + 3𝑥2 + 6𝑥3 ≤ 7 𝑒𝑠 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎:
    4𝑥1 + 3𝑥2 + 6𝑥3 + 𝑦 = 7
    b) Toda desigualdad del tipo 𝐴𝑥 ≥ 𝑏 puede ser
    escrita como una igualdad sustrayendo un
    Regla 4 vector y ≥ 0 llamado superfluro

    Ej.
    2𝑥1 + 6𝑥2 ≥ 10 𝑒𝑠 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎:
    2𝑥1 + 6𝑥2 − 𝑧 ≥ −10
    Método Simplex
    Dado cualquier problema de programación lineal
    transfórmese por medio de la reglas de
    equivalencia al programa lineal canónico.

    Regla 1 Ej.
    max 𝑧 = 𝑐𝑥
    S.a.
    𝐴𝑥 ≤ 𝑏
    𝑥 ≥ 0, 𝑏 ≥ 0
    Reescriba la función objetivo de la siguiente forma
    Regla 2 igualamos a la función objetivo (fo) a 0
    𝑧 − 𝑐𝑥 = 0
    Aplicando las reglas de equivalencia permitidas
    convierta todas las desigualdades en igualdades
    este paso requerirá el uso de variables de holgura.
    Regla 3 max 𝑧 − 𝑐𝑥 = 0
    S.a.
    𝐴𝑥 + 𝑥ҧ = 0
    𝑥 ≥ 0, 𝑥ҧ ≥ 0
    𝑚𝑎𝑥 𝑧 = 5𝑥1 + 4𝑥2

    S.a.
    6𝑥1 + 3𝑥2 ≤ 7
    4𝑥1 + 10𝑥2 ≤ 3
    𝑥1 , 𝑥2 ≥ 0

    Ej. 𝑚𝑎𝑥 𝑧 − 5𝑥1 − 4𝑥2 + 0 𝑥3 +0 𝑥4 = 0


    6𝑥1 + 3𝑥2 + 𝑥3 = 7
    4𝑥1 + 10𝑥2 + 𝑥4 = 3
    𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
    𝑥3
    𝑥ҧ 𝑥
    4
    Regla 4
    z 𝒙𝟏 𝒙𝟐 𝒙𝒎 𝒙𝒎+𝟏 … 𝒙𝒎+𝒏

    1 𝐶𝐵 𝐵−1 𝐴 − 𝐶 𝐶𝐵 𝐵−1 𝐶𝐵 𝑥𝐵
    • Constrúyase una tabla
    con los coeficiente del 𝑎𝐵1 .
    programa lineal como .
    se muestra en la sgte. 𝑎𝐵2 .
    tabla .
    𝐴𝐵−1 𝐵 −1 𝑥𝐵
    . 0
    . .
    𝑎𝐵𝑚 .
    .
    𝑚𝑎𝑥 𝑧 − 5𝑥1 − 4𝑥2 + 0 𝑥3 +0 𝑥4 = 0
    6𝑥1 + 3𝑥2 + 𝑥3 = 7 Z 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒
    4𝑥1 + 10𝑥2 + 𝑥4 = 3 1 -5 -4 0 0 0
    𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
    𝒙𝟑 0 6 3 1 0 7

    𝒙𝟒 0 4 10 0 1 3
    Selecciónese como vector de entrada aquel 𝑧𝑗 − 𝑐𝑗 ,
    con el valor más negativa.

    Si no hay ningún candidato de entrada es decir 𝑧𝑗 −


    Regla 5 𝑐𝑗 > 0 ∀𝑗 𝑒𝑛 𝐴 la solución 𝑥𝐵 mostrada en esa tabla
    es optima en el caso en el que exista en el caso que
    exista un empate entre variables vectores que
    pueden ser candidatas se rompe el empate
    arbitrariamente.
    Una vez seleccionada la columna 𝑎𝑗 que entrara a la

    Regla 6 nueva base selecciónese el vector de salida 𝑎𝑟 de la


    base actual con la siguiente regla.

    𝑥𝐵𝑟 𝑥𝐵𝑘
    = 𝑚𝑖𝑛𝑘 /𝑦 > 0
    𝑦𝑘𝑗 𝑦𝑘𝑦 𝑘𝑦
    La intersección en la tabla de la columna que entra
    y la que sale determina el elemento pivote 𝑦𝑟𝑗
    aplíquese operaciones matriciales elementales en

    Regla 7 el pivote 𝑦𝑟𝑗 con el objeto de convertir a la


    columna 𝑎𝑗 en un vector unitario es decir 0en toda
    la columna y en 1 en la entrada componente que
    resulta ser el 𝑦𝑟𝑗 regrese entonces al paso 5 este
    paso genera una nueva base un nuevo pivote
    extremo y un nuevo valor de la función objetivo.
    Método Simplex

    También podría gustarte