Simplex (TP2 – Pesquisa Operacional)

Implementação do Método Simplex usando tableau, com versão Duas Fases (Fase 1 com artificiais e pré-ajuste ortodoxo) e geração/validação de certificados de otimalidade, inviabilidade e ilimitabilidade.

Estrutura do repositório

Simplex/
├─ src/
│  ├─ Simplex.jl         # Solver CLI (lê entrada, resolve e escreve saída)
│  └─ Certificador.jl    # Verifica, no terminal, os certificados (provas)
└─ examples/
	 ├─ entrada/           # Arquivos de entrada (example01.txt … example12.txt)
	 ├─ gabaritos/         # Saídas de referência do enunciado
	 └─ saida/             # Saídas geradas pelo solver (sol_exampleXX.txt)

Formato da entrada (forma padrão)

Arquivos em examples/entrada/ seguem:

n m
c1 c2 … cm
a1,1 a1,2 … a1,m b1
a2,1 a2,2 … a2,m b2
…
an,1 an,2 … an,m bn

Interpretação: maximizar c^T x, sujeito a A x = b e x ≥ 0. A e b podem conter valores negativos (o solver usa Duas Fases quando necessário).

Como executar (Windows PowerShell)

Executar um arquivo de entrada e gravar a respectiva saída:

julia .\src\Simplex.jl .\examples\entrada\example01.txt .\examples\saida\sol_example01.txt

Executar em lote todos os arquivos de examples/entrada:

$inDir = '.\examples\entrada'
$outDir = '.\examples\saida'
Get-ChildItem $inDir -Filter 'example*.txt' | Sort-Object Name | ForEach-Object {
	$name = $_.BaseName
	$in = $_.FullName
	$out = Join-Path $outDir ("sol_" + $name + ".txt")
	julia '.\src\Simplex.jl' $in $out
}

Como executar (Linux/Ubuntu 20.04)

Pré-requisito: ter o Julia instalado e disponível no PATH.

Executar um arquivo de entrada e gravar a respectiva saída:

julia ./src/Simplex.jl ./examples/entrada/example01.txt ./examples/saida/sol_example01.txt

Executar em lote todos os arquivos de examples/entrada:

for f in ./examples/entrada/example*.txt; do
  name=$(basename "$f" .txt)
  out="./examples/saida/sol_${name}.txt"
  julia ./src/Simplex.jl "$f" "$out"
done

Formato da saída do solver

O solver escreve um arquivo de texto com uma linha de status e, quando aplicável, o valor de z:

• Ótimo: primeira linha otima e segunda linha com z (3 casas decimais)
• Inviável: primeira linha inviavel
• Ilimitado: primeira linha ilimitada
• Erro: primeira linha erro

Observação: Para conferir certificados detalhados (y ou direção d) e checagens numéricas (Ax≈b, A' y≈c, etc.), utilize o Certificador abaixo.

Certificador (provas no terminal)

O script src/Certificador.jl lê a entrada, resolve o problema e imprime no terminal a verificação do certificado correspondente:

• Ótimo: verifica primal (Ax=b, x≥0), dual (A' y ≥ c) e dualidade forte (|c·x − b·y|≃0)
• Inviável: aceita A' y ≥ 0 e b·y < 0 ou A' y ≤ 0 e b·y > 0
• Ilimitado: verifica A d = 0, d ≥ 0 e c·d > 0

Exemplos de uso:

# Ótimo
julia .\src\Certificador.jl .\examples\entrada\example01.txt

# Inviável
julia .\src\Certificador.jl .\examples\entrada\example05.txt

# Ilimitado
julia .\src\Certificador.jl .\examples\entrada\example12.txt

No Linux/Ubuntu 20.04:

# Ótimo
julia ./src/Certificador.jl ./examples/entrada/example01.txt

# Inviável
julia ./src/Certificador.jl ./examples/entrada/example05.txt

# Ilimitado
julia ./src/Certificador.jl ./examples/entrada/example12.txt

Notas

• O solver utiliza Duas Fases automaticamente quando não há base identidade evidente ou quando b possui componentes negativas.
• As operações de álgebra linear (transpor, produto, resolução de sistemas) são implementadas em src/Simplex.jl (Gauss-Jordan com pivotamento parcial).
• As saídas em examples/saida/ podem ser comparadas com examples/gabaritos/ (status/valores). Para uma checagem completa dos certificados, use o Certificador.

Autor

Davi Oliveira Sad — Pesquisa Operacional (TP2)