Programação Linear Aplicada · Capítulo 3

Cap. 3
Modelo matemático para PL e o método Simplex

Estrutura matemática dos modelos de Programação Linear, soluções básicas viáveis, transformação de restrições e desenvolvimento do método Simplex.

Objetivos do capítulo

Ao final deste capítulo, espera-se que o estudante seja capaz de:

1. Da situação real ao modelo de Programação Linear

A Pesquisa Operacional utiliza modelos como representações simplificadas de situações reais de decisão. Antes de escolher um algoritmo, é necessário definir o que se pretende decidir, qual critério será usado para comparar alternativas e quais limitações devem ser respeitadas.

O modelo matemático deve permanecer ligado ao significado operacional de suas variáveis e parâmetros. Uma solução numericamente correta só é útil quando representa adequadamente o problema que motivou sua construção.

1.1 Forma geral de um modelo de Programação Linear

\[ \text{Maximizar ou minimizar}\qquad Z=\sum_{j=1}^{n} c_jx_j \] sujeito a \[ \sum_{j=1}^{n} a_{ij}x_j \begin{cases} \le\\ =\\ \ge \end{cases} b_i, \qquad i=1,\ldots,m \] \[ x_j\ge0,\qquad j=1,\ldots,n. \]
SímboloInterpretação
\(x_j\)Variáveis de decisão.
\(c_j\)Contribuição unitária de cada variável para a função objetivo.
\(a_{ij}\)Coeficientes técnicos das restrições.
\(b_i\)Disponibilidades, limites ou requisitos associados às restrições.
Ideia-chave. Modelar significa traduzir uma decisão real para uma estrutura matemática, mantendo claro o significado das grandezas utilizadas.

2. Quando um problema pode ser tratado como Programação Linear?

A Programação Linear pressupõe relações lineares. Na prática, algumas condições ajudam a avaliar se a representação é adequada ao problema.

Linearidade

A função objetivo e as restrições são combinações lineares das variáveis.

Proporcionalidade

A contribuição de uma variável varia proporcionalmente ao seu nível de atividade.

Aditividade

O efeito total resulta da soma das contribuições individuais, sem interação entre variáveis.

Divisibilidade

As variáveis podem assumir valores fracionários quando a natureza do problema permitir.

Certeza

Os coeficientes são tratados como conhecidos e constantes durante a análise.

Não negatividade

Na formulação usual, as variáveis assumem valores não negativos.

Essas hipóteses funcionam também como um teste de adequação. Se o consumo de um recurso não variar de forma proporcional à atividade, ou se houver interação relevante entre decisões, a representação linear pode exigir aproximações ou outro tipo de modelo.

3. Região viável, convexidade e soluções básicas

O conjunto de valores que satisfaz simultaneamente todas as restrições e as condições de não negatividade constitui a região viável. Em duas variáveis, essa região pode ser representada geometricamente.

Uma propriedade fundamental é a convexidade. Para um problema linear com solução ótima finita, existe pelo menos uma solução ótima em um ponto extremo da região viável. Essa propriedade fornece a base geométrica para o método Simplex.

3.1 Forma matricial

Depois de transformadas as restrições em equações, o sistema pode ser representado por:

\[ A\,x=b,\qquad x\ge0. \]

3.2 Solução básica

Em um sistema com \(m\) equações independentes, selecionam-se \(m\) variáveis para formar a base. As demais são consideradas não básicas e recebem valor zero. Se \(B\) representa a matriz formada pelas colunas básicas, então:

\[ Bx_B=b \] e, quando \(B\) é inversível, \[ x_B=B^{-1}b. \]
Quando todos os componentes de \(x_B\) são não negativos, a solução básica é também viável. Sob as condições usuais, ela corresponde a um ponto extremo da região viável.

4. Preparação do modelo para o método Simplex

O método Simplex é um procedimento iterativo que percorre soluções básicas viáveis adjacentes, procurando melhorar o valor da função objetivo. Para iniciar o processo no caso mais simples, as desigualdades do tipo \(\le\) são convertidas em igualdades com variáveis de folga.

4.1 Variáveis de folga

Uma restrição do tipo

\[ a_1x_1+a_2x_2\le b \]

é transformada em:

\[ a_1x_1+a_2x_2+f=b, \qquad f\ge0. \]

A variável \(f\) representa a parcela do recurso que não foi utilizada. Para \(m\) restrições do tipo \(\le\), pode-se escrever:

\[ Ax+If=b, \qquad x\ge0,\quad f\ge0. \]

Se \(x=0\), resulta \(f=b\). Quando \(b\ge0\), as próprias variáveis de folga formam uma base inicial natural.

Base inicial usual. Variáveis de decisão não básicas: \(x_1=\cdots=x_n=0\). Variáveis de folga básicas: \(f=b\).

5. Quadro do Simplex e etapas de uma iteração

O quadro organiza os coeficientes das restrições, as variáveis básicas, os termos independentes e os indicadores usados para verificar se uma nova troca de base pode melhorar a função objetivo.

5.1 Critério de otimalidade

Para uma formulação de maximização escrita com a linha \(C_j-Z_j\), um valor positivo indica que existe potencial de melhoria. Assim:

\[ C_j-Z_j\le0 \quad\text{para todo }j \] caracteriza a condição de otimalidade, na convenção utilizada neste capítulo.

5.2 Sequência operacional

1
Calcular os valores de \(C_j-Z_j\) para as colunas do quadro.
2
Se todos forem menores ou iguais a zero, a solução básica atual é ótima para o caso considerado.
3
Escolher a variável que entra na base, usualmente associada ao maior valor positivo de \(C_j-Z_j\).
4
Aplicar o teste da razão mínima somente às linhas para as quais o coeficiente da coluna de entrada é positivo.
\[ \theta_i=\frac{b_i}{a_{ip}}, \qquad a_{ip}>0. \]
5
A menor razão não negativa determina a variável que sai da base. A interseção da linha com a coluna de entrada é o pivô.
6
Normalizar a linha pivô e zerar os demais elementos da coluna pivô.
7
Recalcular o quadro e repetir o processo até satisfazer o critério de otimalidade.
Por que somente \(a_{ip}>0\)? Ao aumentar a variável que entra na base, apenas coeficientes positivos nessa coluna impõem um limite superior ao crescimento sem tornar negativa uma variável básica. Coeficientes nulos não restringem esse aumento; coeficientes negativos não fornecem, nessa etapa do Simplex primal, uma razão que preserve a viabilidade.

6. Exemplo: mesas e cadeiras

Considere o modelo:

\[ \max Z=50x_1+40x_2 \] sujeito a \[ \begin{aligned} 4x_1+2x_2&\le40\\ 2x_1+3x_2&\le30\\ x_1,x_2&\ge0. \end{aligned} \]

6.1 Conversão para igualdades

\[ \begin{aligned} 4x_1+2x_2+f_1&=40\\ 2x_1+3x_2+f_2&=30\\ x_1,x_2,f_1,f_2&\ge0. \end{aligned} \]

A solução básica inicial é:

\[ (x_1,x_2,f_1,f_2)=(0,0,40,30), \qquad Z=0. \]

6.2 Primeira iteração

A variável \(x_1\) possui a maior contribuição positiva para a melhoria da função objetivo no quadro inicial e entra na base. O teste da razão é:

\[ \frac{40}{4}=10, \qquad \frac{30}{2}=15. \]

A menor razão é \(10\); portanto, \(f_1\) sai da base. A primeira nova solução básica é:

\[ x_1=10,\qquad x_2=0,\qquad Z=500. \]

6.3 Iteração seguinte e solução ótima

A variável \(x_2\) passa a entrar na base e \(f_2\) sai. Ao final do processo, obtém-se:

\[ x_1=5,\qquad x_2=10, \qquad Z^*=650. \]
Cada pivoteamento representa uma troca de base e, geometricamente, uma passagem para uma solução básica viável adjacente.

7. Quando a base inicial não aparece naturalmente

O procedimento estudado neste capítulo funciona de forma direta quando as restrições são do tipo \(\le\), os termos independentes são não negativos e as variáveis de folga fornecem uma base inicial viável.

Nem todo modelo apresenta essa estrutura. Uma restrição do tipo \(\ge\), por exemplo, é convertida em igualdade pela subtração de uma variável de excesso:

\[ a_1x_1+a_2x_2\ge b \] torna-se \[ a_1x_1+a_2x_2-e=b, \qquad e\ge0. \]
Diferentemente da variável de folga, a variável de excesso aparece com coeficiente \(-1\) e não fornece, por si só, a coluna identidade necessária para uma base inicial viável.

O tratamento sistemático dessas situações — incluindo variáveis de excesso, variáveis artificiais, Método Simplex em Duas Fases, dualidade e Dual-Simplex — é desenvolvido no Capítulo 4.

Referências utilizadas no capítulo

Livro

ANDRADE, Eduardo Leopoldino de

Introdução à Pesquisa Operacional: métodos e modelos para análise de decisões. Rio de Janeiro: LTC. Referência conceitual para modelagem e apoio à decisão.

Livro

HILLIER, Frederick S.; LIEBERMAN, Gerald J.

Introdução à Pesquisa Operacional. 9. ed. Porto Alegre: AMGH, 2013. Referência para formulação de PL e método Simplex.

O conteúdo foi reorganizado para separar a formulação e o Simplex primal, tratados neste capítulo, dos procedimentos de inicialização especiais e da dualidade, desenvolvidos no capítulo seguinte.

← Capítulo 2