( 0.5 pontos) No método dual simplex não há o problema da ciclagem.
◯ Certo. ◯ Errado.
◯ Certo. ◯ Errado.
Passo 1
O enunciado diz: “No método dual simplex não há o problema da ciclagem.” Preciso decidir se isso é correto ou errado.
Informações relevantes do enunciado: há uma afirmação sobre o comportamento do método dual simplex em relação à ciclagem (ou seja, se a ciclagem acontece ou não nele).
Informações relevantes do enunciado: há uma afirmação sobre o comportamento do método dual simplex em relação à ciclagem (ou seja, se a ciclagem acontece ou não nele).
Passo 2
Vamos entender o que é “ciclagem”. Vou explicar devagar e com jeitinho:
Definição de ciclagem: ciclagem é a situação em que o algoritmo do simplex (primal ou dual) retorna repetidamente a mesma sequência de bases (mesmas soluções básicas) sem progresso, ou seja, faz pivôs infinitamente sem melhorar a solução ou sem terminar. Isso acontece quando há degenerescência.
O que é degenerescência? Seja uma solução básica factível dada por uma base . Se alguma variável básica tem valor zero nessa solução, dizemos que a solução é degenerada. Em termos práticos, ao fazer um pivô numa solução degenerada, o valor da função objetivo pode não mudar e a nova base pode representar a mesma ou outra solução com algumas coordenadas zero — daí a possibilidade de voltar a uma base já vista e entrar num ciclo.
Definição de ciclagem: ciclagem é a situação em que o algoritmo do simplex (primal ou dual) retorna repetidamente a mesma sequência de bases (mesmas soluções básicas) sem progresso, ou seja, faz pivôs infinitamente sem melhorar a solução ou sem terminar. Isso acontece quando há degenerescência.
O que é degenerescência? Seja uma solução básica factível dada por uma base
Passo 3
Como a ciclagem aparece no simplex “primal”:
- No simplex primal, escolhemos uma variável não básica para entrar na base e uma básica para sair. Se a regra de escolha de saída (razão mínima) vier a ter empates por causa de variáveis básicas com valor zero, o pivô pode não alterar o valor da solução básica (degenerescência).
- Com escolhas inadequadas, é possível voltar a uma base anterior — daí a ciclagem. Historicamente, exemplos mostraram que o método primal pode ciclar se usarmos a regra ingênua de escolha de pivô.
Passo 4
O método dual simplex e a possibilidade de ciclagem:
- O dual simplex é uma variante do simplex que mantém a solução dual factível e procura tornar a solução primal factível, realizando pivôs que trocam variáveis que violam viabilidade primal.
- A mecânica de pivôs do dual simplex é muito parecida, do ponto de vista combinatório, com a do primal: existem escolhas de variável que entra/saí da base e podem ocorrer empates na regra de escolha (por exemplo, quando múltiplas escolhas minimizam alguma razão ou quando há degenerescência).
- Portanto, a mesma fonte de problema — degenerescência — também existe no dual simplex. Logo, nada impede que ele entre em um ciclo: existem contraexemplos e discussões na literatura mostrando que o dual simplex pode ciclar se não adotarmos uma regra anti-ciclagem apropriada.
Passo 5
Como se evita a ciclagem (importante porque muitos pensam que “dual simplex não cicla” — mas cicla sim sem precaução):
- Regras anti-ciclagem conhecidas: a regra de Bland (escolher a variável de menor índice que satisfaz a condição de entrada/saída) e a regra lexicográfica. Essas regras garantem que não haverá retorno infinito às mesmas bases.
- Essas regras podem ser aplicadas tanto ao simplex primal quanto ao dual simplex. Ou seja, o fato de o dual simplex não ciclar não é uma propriedade automática do método — é consequência de adotar uma regra de pivô que previne ciclagem.
Passo 6
Resumindo e respondendo à afirmação:
- A afirmação “No método dual simplex não há o problema da ciclagem” sugere que o dual simplex é imune à ciclagem por construção. Isso é falso: o dual simplex também pode ciclar na presença de degenerescência se usarmos regras de pivô inadequadas. Para garantir ausência de ciclagem é preciso adotar regras anti-ciclagem (como Bland), que funcionam para ambos os métodos.
Resposta
Errado.