Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 49 visualizações

    2.3.4.3 - Método Simplex - Casos Especiais

    Enviado por

    Mónica S.
    1. O documento discute três casos especiais que podem ocorrer no método simplex: soluções múltiplas, soluções degeneradas e soluções ilimitadas. 2. Uma solução múltipla ocorre quando existe um coeficiente nulo na função objetivo, associado a uma variável não básica, indicando que há mais de uma solução ótima. 3. Uma solução degenerada ocorre quando uma variável básica tem valor zero, indicando que a solução é definida pela interseção de mais de duas restrições

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd

    2.3.4.3 - Método Simplex - Casos Especiais

    Enviado por

    Mónica S.
    49 visualizações13 páginas
    1. O documento discute três casos especiais que podem ocorrer no método simplex: soluções múltiplas, soluções degeneradas e soluções ilimitadas. 2. Uma solução múltipla ocorre quando existe um coeficiente nulo na função objetivo, associado a uma variável não básica, indicando que há mais de uma solução ótima. 3. Uma solução degenerada ocorre quando uma variável básica tem valor zero, indicando que a solução é definida pela interseção de mais de duas restrições

    Título original

    2.3.4.3_Método Simplex - Casos Especiais

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    1. O documento discute três casos especiais que podem ocorrer no método simplex: soluções múltiplas, soluções degeneradas e soluções ilimitadas. 2. Uma solução múltipla ocorre quando existe um coeficiente nulo na função objetivo, associado a uma variável não básica, indicando que há mais de uma solução ótima. 3. Uma solução degenerada ocorre quando uma variável básica tem valor zero, indicando que a solução é definida pela interseção de mais de duas restrições

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    49 visualizações13 páginas

    2.3.4.3 - Método Simplex - Casos Especiais

    Enviado por

    Mónica S.
    1. O documento discute três casos especiais que podem ocorrer no método simplex: soluções múltiplas, soluções degeneradas e soluções ilimitadas. 2. Uma solução múltipla ocorre quando existe um coeficiente nulo na função objetivo, associado a uma variável não básica, indicando que há mais de uma solução ótima. 3. Uma solução degenerada ocorre quando uma variável básica tem valor zero, indicando que a solução é definida pela interseção de mais de duas restrições

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    de 13

    Método Simplex

    Casos Especiais

    1. Soluções múltiplas

    (Exercício 1.6)

    Nota: Escolha aleatória da coluna pivô


    (regra de entrada)
    Método Simplex
    Casos Especiais

    1. Soluções múltiplas

    Evidência em termos do algoritmo do Simplex: existência, no quadro ótimo,


    de um coeficiente nulo na linha da função objetivo, associado a uma
    variável não básica.

    Para obter outra solução, igualmente ótima, fazer entrar a variável F3 na base!
    Método Simplex
    Casos Especiais

    1. Soluções múltiplas

    Evidência em termos gráficos:


    retas paralelas à reta
    correspondente à função
    objetivo (evidência antecipada
    por se ter restrições com
    coeficientes iguais, ou múltiplos,
    aos coeficientes correspondentes
    da função objetivo)
    Método Simplex
    Casos Especiais

    2. Solução degenerada

    Evidência em termos do algoritmo do Simplex: existência de uma variável


    básica com o valor zero (variável degenerada)

    A degenerescência pode surgir na solução ótima (solução ótima


    degenerada) ou numa fase intermédia (solução admissível degenerada).
    Método Simplex
    Casos Especiais

    2. Solução (ótima) degenerada

    Max 𝑍 = 3𝑥1 + 4𝑥2


    s.a.: 𝑥1 + 𝑥2 ≤ 9
    2𝑥1 + 3𝑥2 ≤ 18
    𝑥1 , 𝑥2 ≥ 0

    Empate do rácio de saída;


    escolha arbitrária
    Método Simplex
    Casos Especiais

    2. Solução (ótima) degenerada

    Max 𝑍 = 3𝑥1 + 4𝑥2


    s.a.: 𝑥1 + 𝑥2 ≤ 9
    2𝑥1 + 3𝑥2 ≤ 18
    𝑥1 , 𝑥2 ≥ 0

    A variável básica 𝑥2 apresenta o valor nulo na solução final.


    Aparecendo esta variável associada à 2ª restrição, dizemos que foi
    esta restrição que provocou a degenerescência.
    Método Simplex
    Casos Especiais

    2. Solução (ótima) degenerada

    Evidência em termos gráficos:


    O ponto que traduz a solução
    ótima é definido pela
    interseção de mais do que
    duas restrições.
    Método Simplex
    Casos Especiais

    2. Solução (admissível) degenerada

    Max 𝑍 = 3𝑥1 + 4𝑥2


    s.a.: 𝑥1 + 𝑥2 ≤10
    2𝑥1 + 3𝑥2 ≤ 18
    𝑥1 ≤ 8
    𝑥2 ≤ 6
    𝑥1 , 𝑥2 ≥ 0

    Empate do rácio de saída;


    escolha arbitrária
    (significa que a próxima solução, admissível ou ótima, será degenerada)
    Método Simplex
    Casos Especiais

    2. Solução (admissível) degenerada

    Max 𝑍 = 3𝑥1 + 4𝑥2


    s.a.: 𝑥1 + 𝑥2 ≤10
    2𝑥1 + 3𝑥2 ≤ 18
    𝑥1 ≤ 8
    𝑥2 ≤ 6
    𝑥1 , 𝑥2 ≥ 0

    0
    A menor razão é = 0
    2
    (se o coeficiente de x1 na segunda restrição fosse negativo, o problema de degenerescência estaria
    ultrapassado, por não ser considerado este quociente; neste caso, a degenerescência prolongar-se-á para a
    solução seguinte)
    Método Simplex
    Casos Especiais

    2. Solução (admissível) degenerada

    Max 𝑍 = 3𝑥1 + 4𝑥2


    s.a.: 𝑥1 + 𝑥2 ≤10
    2𝑥1 + 3𝑥2 ≤ 18
    𝑥1 ≤ 8
    𝑥2 ≤ 6
    𝑥1 , 𝑥2 ≥ 0

    A degenerescência será, agora, ultrapassada!


    Método Simplex
    Casos Especiais

    2. Solução (admissível) degenerada

    Evidência em termos gráficos:


    As soluções admissíveis
    degeneradas identificam-se
    pelo facto de o ponto que as
    traduz (neste caso, (0,6)) ser
    definido pela interseção de
    mais do que duas restrições.
    Método Simplex
    Casos Especiais

    3. Solução ilimitada

    Max 𝑍 = 𝑥1 + 𝑥2
    s.a.: 𝑥1 ≤10
    𝑥1 − 3𝑥2 ≤ 15
    𝑥1 −𝑥2 ≤20
    𝑥1 , 𝑥2 ≥ 0

    A coluna pivô é constituída apenas por valores não positivos.


    Método Simplex
    Casos Especiais

    3. Solução ilimitada

    Evidência em termos gráficos:


    Existência de uma região de
    possibilidades ilimitada.

    Você também pode gostar