Simplex Revisado

Este método também é conhecido como ``o Método Simplex Revisado''. A notação matricial oferece:

• Clareza conceitual sobre o material que conhecemos;
• Precisão e eficiência computacional; e
• Acesso simplificado a novos conteúdos, como análise de sensibilidade.

Configuração—Problema Padrão de Igualdade

É dada uma matriz , juntamente com os vetores e .

Assumimos sempre que tem linhas linearmente independentes, o que requer .

Interpretação Geométrica

Rotule as colunas da matriz :

Dado algum , reconheça:

Isso é uma combinação linear das colunas de . Portanto, resolver em significa expressar o vetor dado como uma combinação linear das colunas em . Cada coluna está em , e temos colunas para escolher (com ). Para uma solução básica, escolha quaisquer colunas linearmente independentes, chame-as de base (realmente uma base para , o espaço que contém o lado direito dado ), e use apenas essas. Isso é uma ``solução básica (SB) para ''; pode haver várias dessas.

Cada componente no vetor indica a recompensa (se ) ou penalidade (se ) por incluir a coluna na representação.

Dicionário Simplex

Escolha quaisquer colunas linearmente independentes de . Registre seus subscritos em um conjunto . Chame isso de base. Permute/agrupando colunas selecionadas em uma matriz quadrada (tamanho ). Decomposição simbólica:

leva a

Acompanhe o objetivo:

Novo dicionário:

Esta é uma estrutura algébrica contendo símbolos juntamente com vários números. Substituindo determina os valores numéricos de em uma solução básica para . É bom quando isso é viável, mas a derivação acima não requer isso.

Versatilidade

Imagine escolher quaisquer valores para os elementos do vetor . Este dicionário mostra os componentes de que você deve usar para satisfazer e o valor de que resulta quando você o faz (viabilidade é ignorada). Escolher dá a solução básica e o valor objetivo .

Otimização e Melhorabilidade

Suponha que , então é viável. Considere o vetor linha :

• Se cada componente , todo vetor não nulo subtrairá uma quantidade positiva de . Assim, é o único maximizador.
• Se cada componente , nenhum vetor não nulo pode adicionar uma quantidade positiva a . Assim, é um maximizador, mas talvez não seja único.
• Se algum componente , um valor positivo do componente fará aumentar. A melhoria é possível, então vamos pivotar.

Seleção de Pivot

Suponha que temos um dicionário viável e a linha de coeficientes de custo tem uma entrada negativa. Identifique a coluna associada de e chame-a de . Note que . Escolher de modo que e para todos os outros leva a . Acompanhe os valores dos coeficientes básicos atuais:

Para muitos , isso terá entradas diferentes de zero. Escolha o menor onde uma ou mais entradas mudam para 0: essas entradas identificam as colunas elegíveis para sair. Chame o valor de sorte de .

Atualização

Troque a coluna de entrada na base; a coluna de saída escolhida fora; atualize o vetor de coeficientes usando , e outros coeficientes da fórmula anterior.

Implementação Eficiente

Nunca se calcula realmente a partir de . Em vez disso, resolvemos sistemas lineares da seguinte forma:

• Para gerar coeficientes objetivos, introduza para reorganizar , como , ou seja, . Encontre resolvendo um sistema linear.
• Na atualização de coeficientes, encontre resolvendo o sistema .

O Método Simplex Revisado, Passo a Passo

Contexto

O Método Simplex Revisado trabalha com problemas desta forma:

Aqui, uma matriz de forma é dada, juntamente com vetores (coluna) . Assumimos que tem linhas linearmente independentes (portanto ).

Inicialização

Você precisa de uma base viável para começar. (Tente adivinhar uma; use um passo auxiliar ``Fase Um'' se a adivinhação falhar.) Deixe ser o conjunto de subscritos que definem a base atual; deixe ser o conjunto que contém os subscritos não básicos.

Partição

Use os conjuntos de subscritos e para selecionar colunas de e suas respectivas linhas de , :

A matriz tem forma . Ela é certamente invertível porque as colunas de com índices em devem ser linearmente independentes. O dicionário é:

A BFS atual tem blocos , .

Seleção da Coluna de Entrada

Escaneie em busca de entradas negativas. Para encontrar :

• Encontre (um vetor linha) resolvendo o sistema .
• Construa .

Se nenhuma entrada for negativa, a BFS atual é ótima. Pare. Se existirem entradas negativas, escolha uma. Ela rotula uma ``coluna de entrada'' adequada que tem um índice original . A própria coluna é , com coeficiente .

Seleção da Coluna de Saída

Defina o coeficiente não básico , mantendo todas as outras variáveis não básicas em 0. Isso dá ao vetor exatamente uma entrada não nula, com:

Observe os coeficientes da base atual mudarem à medida que aumenta:

onde é encontrado resolvendo . Deixe denotar o menor para o qual tem uma entrada zero. Cada entrada zero em identifica uma coluna na base atual que pode sair. Escolha uma; use como um símbolo para o índice de saída. Então, a coluna de saída é . (Se nunca desenvolver uma entrada zero, enviar prova que o problema é ilimitado. Relate esse fato e pare.)

Atualização

Os índices e são números de colunas. No início, e . Troque esses dois. Depois, volte ao problema original e faça as novas matrizes de blocos , , e os vetores de custo , . Atualize a BFS notando que ; entradas para aparecem na fórmula anterior; e . Volte ao ``Seleção da Coluna de Entrada''.

Exemplo

Aqui estão alguns pivôs do RSM usando a regra de Bland para o problema:

Configuração da Solução

Uma BFS simples vem de escolher , então , dando:

Primeira Iteração

• Selecione a variável de entrada usando os coeficientes objetivos .

  -- Resolva para em , ou seja, . Fácil: . -- Escreva e escaneie o vetor

  . Selecione para entrar (Regra de Bland). Assim, , , .

• Selecione a variável de saída, observando que , então . -- Resolva para em , ou seja, . Fácil: .

• Monitore:

À medida que aumenta, é o menor valor onde adquire um componente zero. (A menor escolha garante que permaneça viável.) A variável rotula esse slot, então ela sairá. Escreva , então , .

Segunda Iteração

• Selecione a variável de entrada: -- Resolva para em , ou seja, , ou seja, . Obtenha , , : . -- Escreva e escaneie o vetor . Selecione para entrar (Regra de Bland). Assim, , , .
• Selecione a variável de saída, observando que : -- Resolva para em , ou seja, , ou seja, . A linha do meio dá , depois e . Assim, .
• Monitore:

À medida que aumenta, é o menor valor onde adquire um componente zero. A variável rotula esse slot, então ela sairá. Escreva , , .

Terceira Iteração

• Selecione a variável de entrada: -- Resolva para em , ou seja, , ou seja,

  . Obtenha , depois , depois : .

  • Escreva e escaneie o vetor

  Todos os componentes são positivos, então a BFS atual é o ÚNICO MAXIMIZADOR! Para relatar, lembre-se do vetor de solução completo mostrado explicitamente na parte 3(a) da Segunda Iteração acima.