( 0.5 pontos) No método dual simplex não há o problema da ciclagem.
◯ 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).

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 B. 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.

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.

Exercícios relacionados