Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex

Docente: Mestre Leonardo Muteia,MBA

Ano: 2024

Método Simplex

3.1 Apresentação

O Método Simplex é um procedimento matricial para resolver problemas de programação

linear expressos na forma padrão ou standard.

Optimizar: Z = CTX
Sujeito a: AX = B
Com: X0

Onde B  0 e se conhece uma solução básica admissível X0.

O Método Simplex é formado por um conjunto de critérios para a escolha de soluções

básicas que melhorem o desempenho do modelo, e também de um teste de optimalidade.

Tal como já foi referido, o método começa com uma solução básica admissível X0 e vai,
sucessivamente, localizando outras soluções básicas (sempre admissíveis)
correspondentes a melhores valores da função objectivo, até que seja encontrada uma
solução óptima.

Estas outras soluções básicas subsequentes são calculadas com a troca de variáveis básicas
por não básicas, gerando novas soluções.

Agora, os critérios para a escolha de vectores e consequentemente das variáveis que

entram e saem para a formação da nova base constituem o centro do Simplex.

1ª Parte:
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Teste de Optimalidade
Consiste em avaliar o efeito da permuta de uma variável básica por outra não básica, com
a consequente formação de nova solução.

Se a entrada de uma variável não básica puder melhorar o desempenho do sistema, a

solução testada não é óptima.

Mas esta avaliação só é possível quando a função objectiva está escrita somente em
termos das variáveis não básicas.

Exemplo1:
Maximizar Z  3 x1  5 x2
2 x1  4 x2  10
6 x  x  20
 1 2
sujeito a : 
 1x  x 2  30
 x1  0 ; x2  0

Acrescentando as variáveis de folga fica:

2 x1  4 x2  x3  10
6 x  x  x  20
 1 2 4

 x1  x2  x5  30
 x1  0 ; x2  0 ; x3  0 ; x4  0 ; x5  0

A função objectivo está escrita na forma: MAX Z = 3x1 + 5x2

1  0  0  10 
Solução básica inicial : 0 x3  1  x4  0 x5  20
     
0 0 1  30 

A função objectivo está escrita com as variáveis não básicas.

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Vamos reescrever agora, a função objectivo com todas as variáveis à esquerda:

Z  3x1  5x2  Z  3x1  5x2  0

Coeficientes negativos à esquerda indicam que o valor de Z pode ser aumentado com a
entrada da variável na base, e na proporção de seu coeficiente.

Quer dizer:

A solução testada só será óptima quando as variáveis não básicas não apresentarem
coeficientes negativos.

2ª parte:

Cálculo da nova solução básica

a) Variável que entra na base:

Entra na base a variável com coeficiente negativo de maior valor absoluto. A ideia é de
melhorar rapidamente o valor de Z.

Examinando a função objectivo:

Z  3x1  5x2  Z  3x1  5x2  0

Entraria a variável x2 pois cada unidade a mais em x2 aumenta Z em 5 unidades.

b) Variável que sai:

Sai a variável que primeiro se anula com a entrada da variável escolhida no item anterior,
no caso x2, que entra com maior valor possível.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

A variável que sai pode ser descoberta dividindo-se os termos da direita das restrições
pelos coeficientes positivos da variável que entra.

O menor valor indica que a variável básica dessa linha é a que primeiro se anula e sairá da
base.

2 x1  4 x2  x3  10  10  4  2,5  x3 sai

6 x1  x2  x4  20  20  1  20
 x  x  x  30  30  (1)   30
 1 2 5

entra

A última divisão (30/(-1)) não pode ser considerada, pois daria valor negativo para a
variável na próxima base, o que não é possível. Portanto sai a variável da primeira linha,
no caso x3.

c) Elemento Pivot:
A coluna da variável que entra e a linha da variável que sai identificam um elemento
comum chamado pivot.

A linha da variável que sai é também linha pivot. No caso, a primeira linha é a pivot e o
coeficiente 4 de x2 é o elemento pivot.

d) Calcular a nova solução

d1. Organizar a função objectivo e as restrições numa tabela:

Z X1 X2 X3 X4 X5 b
1 -3 -5 0 0 0 0
0 2 4 1 0 0 10  Sai (linha pivot)
0 6 1 0 1 0 20
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

0 1 -1 0 0 1 30

 entra

d2 . Dividir a linha pivot pelo valor do elemento pivot, obtendo uma nova linha
com pivot unitário.

Linha pivot: 0 2 4 1 0 0 10
Dividindo por 4: 0 0,5 1 0,25 0 0 2,5 novo pivot

D3. Reescrever cada uma das outras linhas da seguinte maneira:

1° Multiplicar os elementos da nova linha pivot pelo coeficiente da variável

que entra da outra linha, com sinal trocado.

2° Somar termo a termo com os elementos da outra linha.

Por exemplo, coeficiente da variável que entra (x2) na primeira linha é (-5).

Nova linha pivot: 0 0,5 1 0,25 0 0 2,5

(vezes) X 5: 0 2,5 5 1,25 0 0 12,5
+ primeira linha: 1 -3 -5 0 0 0 0
 =Nova 1ª linha 1 -0,5 0 1,25 0 0 12,5

O coeficiente da variável que entra (x2) na terceira linha é 1. Então:

Nova linha pivot: 0 0,5 1 0,25 0 0 2,5

(vezes) X (-1): 0 -0,5 -1 -0,25 0 0 -2,5
+ terceira linha: 0 6 1 0 1 0 20
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

 =Nova 3ª linha 0 5,5 0 -0,25 1 0 17,5

O coeficiente da variável que entra na 4ª linha é (-1). Então:

Nova linha pivot: 0 0,5 1 0,25 0 0 2,5

(vezes) X 1: 0 0,5 1 0,25 0 0 2,5
+ quarta linha: 0 1 -1 0 0 1 30
 =Nova 4ª linha 0 1,5 0 0,25 0 1 32,5

Reescrevendo a nova tabela com os resultados obtidos tem-se:

Z X1 X2 X3 X4 X5 b
1 -0,5 0 1,25 0 0 12,5
0 0,5 1 0,25 0 0 2,5
0 5,5 0 -0,25 1 0 17,5
0 1,5 0 0,25 0 1 32,5

De onde se conclui a nova solução:

 x1  0
Variáveis não básicas : 
 x3  0
 x2  2,5

Variáveis básicas :  x4  17,5
 x  32,5
 5
Valor de Z  12,5

A função objectivo na nova solução está escrita em termos das variáveis não básicas x 1 e x3 .
As variáveis básicas têm coeficientes nulos.

A solução obtida tem Z = 12.5, contra Z = 0 da solução inicial.

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Esta solução é melhor, mas ainda não é óptima, pois o coeficiente de x1 na f.o. é negativo.

Cálculo da nova solução:

- Variável que entra: x1 (coeficiente negativo de maior valor absoluto na f.o.)

- Variável que sai: Dividir os termos independentes pelos coeficientes positivos de x1:

2,5 : 0,5 = 5
17,5 : 5,5 = 3,18  menor valor: sai a variável dessa linha no caso x4
32,5 : 1,5 = 21,67

Nova linha pivot = 3ª linha

Elemento pivot = 5,5

Nova linha pivot = linha pivot dividida por 5,5

Linha pivot: 0 5,5 0 -0,25 1 0 17,5

Dividindo por 5,5: 0 1 0 -0,045 0,18 0 3,18 novo pivot

O coeficiente da variável que entra (x1) na 1ª linha é –0,5. Então:

Nova linha pivot: 0 1 0 -0,045 0,18 0 3,18

(vezes) X 0,5: 0 0,5 0 -0,022 0,09 0 1,59
+ 1ª linha: 1 -0,5 0 1,25 0 0 12,5
 =Nova 1ª linha 1 0 0 1,227 0,09 0 14,09

O Coeficiente da variável que entra (x1) na segunda linha é 0,5. Então:

Nova linha pivot: 0 1 0 -0,045 0,18 0 3,18

(vezes) X -0,5: 0 -0,5 0 0,022 -0,09 0 -1,59
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

+ 2ª linha: 0 0,5 1 0,25 0 0 2,5

 =Nova 2ª linha 0 0 1 0,272 -0,09 0 0,91

O Coeficiente da variável que entra (x1) na quarta linha é 1,5. Então:

Nova linha pivot: 0 1 0 -0,045 0,18 0 3,18

(vezes) X -1,5: 0 -1,5 0 0,067 -0,27 0 -4,77
+ 4ª linha: 0 1,5 0 0,25 0 1 32,5
 =Nova 4ª linha 0 0 0 0,317 -0,27 1 27,73

Reescrevendo a nova tabela com os resultados obtidos tem-se:

Z X1 X2 X3 X4 X5 b
1 0 0 1,227 0,09 0 14,09
0 0 1 0,272 -0,09 0 0,91
0 1 0 -0,045 0,18 0 3,18
0 0 0 0,317 -0,27 1 27,73

A nova solução é que por sinal é óptima:

Variáveis não básicas Variáveis básicas Valor de Z

X3 = 0 X1 = 3,18 Z = 14,09
X4 = 0 X2 = 0,91
X5 = 27,73
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Exemplo 2:

“Uma marcenaria deseja estabelecer uma programação diária de produção. Actualmente, a

oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeitos de
simplificação, vamos considerar que a marcenaria tem limitações em somente dois recursos:
madeira e mão-de-obra, cujas disponibilidades diárias são mostradas na tabela a seguir:

Recurso Disponibilidade
Madeira 12m3
Mão-de-obra 8 H/h

O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2m2 de madeira e 2H/h
de mão-de-obra. Para fazer um armário, a fábrica gasta 3m3 de madeira e 1H/h de mão-de-
obra.
Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de
$4 e cada armário de $1.

Encontrar o plano de produção que maximiza a margem de contribuição total para o lucro.”

Roteiro da resolução

a. Quais são as variáveis de decisão?

 O que deve ser decidido é o plano óptimo de produção. Assim, as variáveis de

decisão serão x1 e x2, onde

x1 : quantidade a produzir de mesas

x2 : quantidade a produzir de armários

b. Qual é o objectivo?

 O objectivo é maximizar o lucro!

i. Lucro devido a mesas: 4x1

ii. Lucro devido a armários: 1x2
iii. Objectivo: Maximizar L = 4x1 + 1x2

c. Quais são as restrições?

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Para as restrições, a relação lógica existente é:

 Utilização de recursos ≤ Disponibilidade

Madeira: 2x1 + 3x2 ≤ 12
Mão-de-obra: 2x1 + x2 ≤ 8
Com x1, x2  0

Modelo completo é:
L  4 x1  x 2  Max

2 x1  3x 2  12

Sujeito a 2 x1  x 2  8
x , x  0
 1 2

3.2 Desenvolvimento do Método Simplex

1º Passo: Determinar a função z-transformada (função Objectivo transformada)

L  4 x1  x2  L  4 x1  x2  0
2º Passo: Introduzir as variáveis de folga:

2 x1  3x 2  x3  12

2 x1  x 2  x4  8
x , x , x , x  0
 1 2 3 4
3º Passo: Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis
com os respectivos sinais e, na primeira linha, incluir os coeficientes da função
objectivo transformada.

Base x1 x2 x3 x4 b
L -4 -1 0 0 0
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

x3 2 3 1 0 12
x4 2 1 0 1 8

4º Passo: Estabelecer uma solução básica inicial (SBI), usualmente atribuindo valor zero às
variáveis originais e achando valores positivos para as variáveis de folga.

 x3  12

x1  x 2  0   x 4  8 (var iáveis básicas )
L  0


5º Passo: Como próxima variável a entrar na base, escolher a variável não básica que oferece,
na última linha, a maior contribuição para o aumento da função objectivo (ou seja,
tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem
coeficientes nulos ou positivos nesta linha, a solução actual é óptima. Se alguma
dessas variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida
na base sem aumentar o valor da função objectivo. Isso quer dizer que temos uma
solução óptima, com o mesmo valor da função objectivo.

Base x1 x2 x3 x4 B q
L -4 -1 0 0 0
x3 2 3 1 0 12 12/2 = 6
x4 2 1 0 1 8 8/2 = 4
Entra

6º Passo: Para escolher a variável que deve deixar a base, deve-se realizar o seguinte
procedimento:

a. Dividir os elementos da última coluna pelos correspondentes elementos

positivos da coluna da variável que vai entrar na base. Caso não haja elemento
algum positivo nesta coluna, o processo deve parar, já que a solução seria
ilimitada.

b. O menor quociente indica a equação cuja respectiva variável básica deverá ser
anulada, tornando-se variável não básica.

7º Passo: Usando operações válidas com as linhas da matriz, transformar o quadro de cálculos
de forma a encontrar a nova solução básica. A coluna da nova variável básica
deverá se tornar um vector identidade, onde o elemento 1 aparece na linha
correspondente à variável que está sendo anulada.

1ª Operação: Dividir a terceira linha por 2 (L3 = L3/2)

Base x1 x2 x3 x4 b
L -4 -1 0 0 0
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

x3 2 3 1 0 12
X1 1 1/2 0 1/2 4

2ª Operação: Multiplicar a terceira linha por (-2) e somar com a segunda linha do mesmo
quadro, colocando o resultado na segunda linha (L2 = L2 – 2L3)

Base x1 x2 x3 x4 b
L -4 -1 0 0 0
x3 0 2 1 -1 4
X1 1 1/2 0 1/2 4

3ª Operação: Multiplicar a terceira linha por (4) e somar com a primeira linha do mesmo
quadro, colocando o resultado na primeira linha (L1 = L1 + 4L3)

Base x1 x2 x3 x4 b
L 0 1 0 2 16
x3 0 2 1 -1 4
X1 1 1/2 0 1/2 4

8º Passo: Retornar ao 5º passo para iniciar outra iteração.

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

3.3. O Método Simplex em Duas Fases

O Método Simplex utiliza uma solução básica inicial viável para começar o processo
iterativo, trabalhando sempre dentro do domínio de admissibilidade. Nos casos discutidos até
então, a solução xi = 0, para i = 1, ..., n era uma solução viável, já que todas as restrições
apresentadas foram do tipo (≤). Quando as restrições são do tipo ( = ) ou (  ), esta solução
não existe!

Seja o exemplo abaixo:

Z  10 x1  4 x2  5 x3  Minimizar

8 x1  3x2  4 x3  10

Sujeito a : 4 x1  3x2  8
x , x , x  0
 1 2 3

Como tem-se uma restrição do tipo (  ), a variável de folga deve ter coeficiente negativo,
tendo o significado de uma variável de excesso. O problema transformado é:

Z  10 x1  4 x2  5 x3  Mimimizar

8 x1 3x2  4 x3  x4  10

Sujeito a : 4 x1  3x2  x5  8
x , x , x , x , x  0
 1 2 3 4 5

Onde x4 é uma variável de excesso e x5 é uma variável de folga.

Note que, pelo processo de solução anterior, a variável de excesso (x4) passaria a ter valor
negativo na solução inicial (-10), o que não é permitido. Assim, a solução x 1 = x2 = x3 = 0 é
inviável.

É necessário então encontrar uma solução viável para que o método Simplex possa ser
iniciado.
A forma de se resolver isto é introduzindo novas variáveis. Estas variáveis são chamadas de
variáveis artificiais, e representadas por ai. Será colocada uma variável artificial em cada
restrição do modelo, ou
seja:
8 x1 + 3 x2 + 4 x3 – x4 + a1 = 10
4 x1 + 3 x2 + x5 + a2 = 8
x1, x2, x3, x4, x5, a1, a2 0
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Como pode-se perceber, o problema com as restrições acima não é o mesmo problema, a não
ser que todas as variáveis ai sejam iguais a zero.
Desta forma, podemos resolver o problema em duas fases: na primeira fase, substituímos a
função objectivo original por uma função objectivo auxiliar:

Zaux = - a1 – a2 = 12 x1 + 6 x2 + 4 x3 – x4 + x5 – 18

Nesse momento, aplicamos o método Simplex de forma a maximizar a função objectivo

auxiliar, com as restrições contendo as variáveis auxiliares. A função objectivo auxiliar será
maximizada quando todas as variáveis ai forem iguais a zero, já que não podem conter
valores negativos.

A primeira fase do problema, que consiste na maximização da função objectivo auxiliar,

fornecerá uma solução viável para o problema original. A segunda fase consiste em resolver o
problema original tomando como solução inicial os valores obtidos pela primeira fase para as
variáveis xi .

a) Solução inicial

Para resolver o problema, monta-se o quadro de forma semelhante à sistemática, colocando-se

a função objectivo artificial na última linha. O quadro do exemplo fica:

Base x1 x2 x3 x4 x5 a1 a2 b
a1 8 3 4 -1 0 1 0 10
a2 4 3 0 0 1 0 1 8
Z” = -Z 10 4 5 0 0 0 0 0
Zaux -12 -6 -4 1 -1 0 0 -18

Obs. Como a função objectivo é de minimização, ele foi transformado em um problema de

maximização através da multiplicação de todos os coeficientes por (-1).
A seguir, aplica-se o método Simplex normalmente, usando como função objectivo a última
linha.
Quando a solução óptima for atingida, dois casos podem ocorrer:

zaux = 0: neste caso foi obtida uma solução básica do problema original e o processo
de solução deve continuar, desprezando-se as variáveis artificiais e os elementos da
última linha.
É o início da segunda fase do processo.

zaux 0: neste caso o problema original não tem solução viável, o que significa que
as restrições devem ser inconsistentes.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

b) Fase 1 - Primeira iteração

Variável a entrar na base: x1 (coluna com maior valor negativo na última linha)
Variável a sair da base: a1 (o quociente 10/8 é o menor quociente entre a última coluna e a
coluna da variável x1, que vai entrar na base)

L1 L1 / 8
L2 L2 - 4 L1
L3 L3 - 10 L1
L4 L4 + 12 L1

Base x1 x2 x3 x4 x5 a1 a2 b
x1 1 3/8 ½ -1/8 0 1/8 0 5/4
a2 0 3/2 -2 ½ 1 -1/2 1 3
Z” = -Z 0 ¼ 0 5/4 0 -5/4 0 -12.5
Zaux 0 -3/2 2 -1/2 -1 3/2 0 -3

c) Fase 1 - Segunda iteração

Variável a entrar na base: x2 (coluna com maior valor negativo na última linha)
Variável a sair da base: a2 (o quociente 3/(3/2) é o menor quociente entre a última coluna e a
coluna da variável x2, que vai entrar na base)

L2 2 L2 / 3
L1 L1 - 3 L2 / 8
L3 L3 - L2 / 4
L4 L4 + 3 L2 / 2

Base x1 x2 x3 x4 x5 a1 a2 b
x1 1 0 1 -1/4 -1/4 ¼ -1/4 ½
x2 0 1 -4/3 1/3 2/3 -1/3 2/3 2
Z” = -Z 0 0 1/3 7/6 -1/6 -7/6 1/6 -13
Zaux 0 0 0 0 0 1 1 0

Como na última linha o valor da função objetivo artificial é zero, a primeira fase terminou e a
solução encontrada é a solução básica inicial para a segunda fase.
Removendo a última linha e as colunas referentes às variáveis artificiais, o quadro se torna

Base x1 x2 x3 x4 x5 b
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

x1 1 0 1 -1/4 -1/4 ½
x2 0 1 -4/3 1/3 2/3 2
Z” = -Z 0 0 1/3 7/6 -1/6 -13

e) Fase 2 - Primeira iteração

Variável a entrar na base: x5 (coluna com maior valor negativo na última linha)
Variável a sair da base: x2 (o quociente 2/(2/3) é o menor quociente entre a última coluna e a
coluna da variável x2, que vai entrar na base)

Base x1 x2 x3 x4 x5 b
x1 1 3/8 ½ -1/8 0 5/4
x2 0 3/2 -2 ½ 1 3
Z” = -Z 0 1/4 0 5/4 0 -12.5

e) Solução ótima encontrada

Como todos os valores da última linha (função z-transformada) são positivos ou nulos,
concluímos que a solução encontrada é óptima, ou seja:
x1 = 1,25
x2 = 0
z = -z' = 12,5
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Exemplo:
Numa fábrica há oito trabalhadores e três máquinas, e fabricam-se dois tipos de produtos: O
produto A que ocupa 1 hora de trabalho manual e 0,5 horas de trabalho de máquina, e o
produto B que ocupa 1,8 horas de trabalho manual e 0,6 horas de trabalho de máquina. Tendo
em conta que se obtém 60 € de lucro com a venda de uma unidade de produto A e 100 € com
a venda de uma unidade de produto B, formule em programação linear, o problema de
determinação do maior lucro que é possível obter num dia de trabalho (8 horas). (20)

Variáveis:
X1 → quantidade do produto A (em unidades) (5)
X2 → quantidade do produto B (em unidades)

Restrições:
8 trabalhadores e 3 máquinas, a trabalhar durante 8 horas. Isto significa que para o trabalho
manual dispomos ao todo de 8× 8 horas, já que temos 8 trabalhadores e cada um deles está a
trabalhar 8 horas. Para o trabalho de máquinas temos disponíveis 3×8 horas, já que são 3
máquinas a trabalhar cada uma delas 8 horas.
Função objectivo:
Obter o lucro máximo (em euros) com a produção de A e de B (em unidades)
Lucro  60 x1  100 x 2  Max
(10 +5)
1x1  1.8 x 2  64 (trabalho manual efectuado pelos Ws)

Sujeito a : 0.5 x1  0.6 x 2  24 (trabalho das máquinas)
 x , x  0 (condições de não  negativida de)
 1 2

3.4. O Problema da Solução básica Inicial

Exemplo:
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Z  x1  x2  x3  Max

2 x1  x2  x3  10
 x  x  2 x  20
 1 2 3
Sujeito a 
2 x1  x2  3 x3  60
 xi  0

a) Acrescentando as variáveis de folga:

2 x1  x2  x3  x4  10

 x1  x2  2 x3  x5  20
2 x  x  3 x  60
 1 2 3

Não há uma solução básica inicial SBI por causa da segunda e terceira restrições.

b) Acrescentar na 2ª e 3ª restrições as variáveis auxiliares a2 e a3:

2 x1  x2  x3  x4  10

 x1  x2  x3  x5  a2  20
2 x  x  3x  a3  60
 1 2 3

 x4  10

Tem-se agora uma solução básica inicial a2  20 com as restantes variáveis nulas.
a  60
 3

O retorno ao modelo original deve ser feito com a eliminação das variáveis auxiliares e a
manutenção da solução básica. Isto pode ser feito de duas maneiras:

3.4.1 Método do M grande

Escrevemos a função objectivo, acrescentando as variáveis auxiliares com coeficientes –M2 e

–M3, sendo M2 e M3 números grandes.

Z = x1 + x2 + x3 – M2a2 – M3a3

À medida que Z é maximizada, as variáveis a2 e a3 deixam a base, devido ao grande valor de

M 2 e M3 .

Zaux = x1 + x2 + x3 – M2a2 – M3a3

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

2 x1  x2  x3  x4  10

Sujeito a  x1  x2  x3  x5  a2  20
2 x  x  3x  a3  60
 1 2 3

O quadro inicial fica então:

Z x1 x2 x3 x4 x5 a2 a3 b
1 -1 -1 -1 0 0 M2 M3 0
0 2 1 -1 1 0 0 0 10
0 1 1 2 0 -1 1 0 20
0 2 1 3 0 0 0 1 60

Solução:

Variáveis básicas Variáveis não básicas Valor de Z original

 x4  10  x1  0
 x  0
VB a2  20  2
a  60 VNB  Z=0
 3  x3  0
 x5  0

Cálculo da nova solução:

 Variável que entra: x3 – as 3 variáveis têm coeficientes iguais. Escolhe-se uma

delas.
 Variável que sai: a2 – menor quociente 20 : 2 = 10
 LP: 3ª Linha
 Pivôt: 2
 NLP = LP/2 : 0 0.5 0.5 1 0 -0.5 0.5 0 10

Nova linha pivot: 0 0.5 0.5 1 0 -0.5 0.5 0 10

(vezes) x 1: 0 0.5 0.5 1 0 -0.5 0.5 0 10
+ 1ª linha: 1 -1 -1 -1 0 0 M2 M3 0
 =Nova 1ª linha 1 -0.5 -0.5 0 0 -0.5 M2 M3 10

Cálculo da nova 2ª Linha

Nova linha pivot: 0 0.5 0.5 1 0 -0.5 0.5 0 10

(vezes) x 1: 0 0.5 0.5 1 0 -0.5 0.5 0 10
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

+ 2ª linha: 0 2 1 -1 1 0 0 0 10
 =Nova 2ª linha 0 2.5 1.5 0 1 -0.5 0.5 0 20

Cálculo da nova 4ª Linha

Nova linha pivot: 0 0.5 0.5 1 0 -0.5 0.5 0 10

(vezes) x -3: 0 -1.5 -1.5 -3 0 1.5 -1.5 0 -30
+ 4ª linha: 0 2 1 3 0 0 0 1 60
 =Nova 4ª linha 0 0.5 -0.5 0 0 1.5 -1.5 1 30

Novo quadro:

Z x1 x2 x3 x4 x5 a2 a3 b
1 -0.5 -0.5 0 0 -0.5 M2 M3 10
0 2.5 1.5 0 1 -0.5 0.5 0 20
0 0.5 0.5 1 0 -0.5 0.5 0 10
0 0.5 -0.5 0 0 1.5 -1.5 1 30

Solução: (sombreado na tabela)

Cálculo da nova solução:

 Variável que entra: x5

 Variável que sai: a3

 LP: 4ª Linha
 Pivôt: 1,5

Nova linha pivot: 0 0.333 -0.333 0 0 1 -1 0.667 20

(vezes) x 0.5: 0 0.167 -0.167 0 0 0.5 -0.5 0.333 10
+ 1ª linha: 1 -0.5 -0.5 0 0 -0.5 M2 M3 10
 =Nova 1ª linha 1 -0.333 -0.667 0 0 0 M2 M3 20

Cálculo da nova 2ª Linha:

Nova linha pivot: 0 0.333 -0.333 0 0 1 -1 0.667 20

(vezes) x 0.5: 0 0.167 -0.167 0 0 0.5 -0.5 0.333 10
0.5
+ 2ª linha: 0 2.5 1.5 0 1 -0.5 0 20
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

 =Nova 2ª linha 0 2.667 1.333 0 1 0 0 0.333 30

Cálculo da nova 3ª Linha:

Nova linha pivot: 0 0.333 -0.333 0 0 1 -1 0.667 20

(vezes) x 0.5: 0 0.167 -0.167 0 0 0.5 -0.5 0.333 10
0.5
+ 3ª linha: 0 0.5 0.5 1 0 -0.5 0 10
 =Nova 3ª linha 0 0.667 0.333 1 0 0 0 0.333 20

Novo quadro:

Z x1 x2 x3 x4 x5 a2 a3 b
1 -0.333 -0.667 0 0 0 M2 M3 20
0 2.667 1.333 0 1 0 0 0.333 30
0 0.667 0.333 1 0 0 0 0.333 20
0 0.333 -0.333 0 0 1 -1 0.667 20

Solução (sombreado na tabela)

Agora a solução básica é formada por variáveis originais! Pode-se abandonar as variáveis
auxiliares, todas nulas. O quadro fica então:

Z x1 x2 x3 x4 x5 b
1 -0.333 -0.667 0 0 0 20
0 2.667 1.333 0 1 0 30
0 0.667 0.333 1 0 0 20
0 0.333 -0.333 0 0 1 20

Cálculo da solução óptima:

 Variável que entra: x2

 Variável que sai: x4
 LP: 2ª Linha
 Pivôt: 1.333

Cálculo da nova 1ª Linha:

Nova linha pivot: 0 2 1 0 0.75 0 22.5

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

(vezes) x 0.667: 0 1.333 0.667 0 0.5 0 15

+ 1ª linha: 1 -0.333 -0.667 0 0 0 20
 =Nova 1ª linha 1 1 0 0 0.5 0 35

Cálculo da nova 3ª Linha:

Nova linha pivot: 0 2 1 0 0.75 0 22.5
(vezes) x -0.333: 0 -0.667 -0.333 0 -0.25 0 -7.5
+ 3ª linha: 0 0.667 0.333 1 0 0 20
 =Nova 3ª linha 0 0 0 1 -0.25 0 12.5

Cálculo da nova 4ª Linha:

Nova linha pivot: 0 2 1 0 0.75 0 22.5

(vezes) x 0.333: 0 0.667 0.333 0 0.25 0 7.5
+ 4ª linha: 0 0.333 -0.333 0 0 1 20
 =Nova 3ª linha 0 1 0 0 0.25 1 27.5

Novo quadro:

Z x1 x2 x3 x4 x5 b
1 1 0 0 0.5 0 35
0 2 1 0 0.75 0 22.5
0 0 0 1 -0.25 0 12.5
0 1 0 0 0.25 1 27.5

Solução:

Variáveis básicas Variáveis não básicas Valor de Z original

 x2  22,5  x1  0
 VNB 
VB  x3  12,5  x4  0 Z = 35
 x  27,5
 5

A solução é óptima!
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Exercícios
Resolva os seguintes problemas
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

1. Z  3 x1  2 x2  x3  min imizar

3 x1  x2  3 x3  6
3 x  2 x  6
 1 2
Sujeito a : 
 x1  x2  1
 xi  0

2. Z  3 x1  2 x2  Min

2 x1  x2  10

Sujeito a :  x1  5 x2  15
 x 0
 i

3. Z  x1  x2  2 x3  Max

 x1  2 x2  10

Sujeito a : 3 x1  4 x2  x3  20
 x  0, x  0, x livre
 1 3 2

4. Simplex Z  2 x1  4 x2  5 x3  Min

 x1  2 x2  10 x3  600
 x  x  x  50
 1 2 3
Sujeito a : 
2 x1  x3  100
 xi  0
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

3.5 O Problema da Degeneração

1. No Simplex a linha Pivôt é a restrição que apresenta o menor quociente não negativo na
divisão dos termos bi pelos coeficientes positivos da variável que entra na base.
2. pode ocorrer que haja mais de um resultado nessas condições.
3. Escolhemos um deles arbitrariamente para calcular a solução.
4. Só que essa solução apresentará variáveis básicas com valor nulo.
5. A saída de uma variável básica nula provoca o aparecimento de outra variável básica nula
na solução seguinte.
6. Neste caso, a solução diz-se Degenerada.

3.6. O Problema da Solução Ilimitada

Isto ocorre quando a variável que entra na base não possui em sua coluna nenhum coeficiente
positivo.

3.7. Soluções Múltiplas

Se na solução óptima o coeficiente de uma variável não básica é zero, ele poderá entrar na
base sem alterar o valor da função objectivo, gerando outra solução óptima. Neste caso,
qualquer combinação linear dessas duas soluções também será uma solução óptima.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

3.8 A Ferramenta SOLVER do Excel

Diversas ferramentas para solução de problemas de optimização, comerciais ou acadêmicos,

sejam eles lineares ou não, foram desenvolvidas. Dentre as ferramentas disponíveis, este curso
se propõe a apresentar a ferramenta Solver, que acompanha o Microsoft Excel.
Apesar de a ferramenta Solver poder ser utilizada também para problemas de programação
não-linear, neste curso será apresentada apenas a sua utilização para a solução de problemas
de programação linear. A utilização para outros tipos de problemas segue o mesmo padrão,
sendo por isso intuitivo ao usuário o seu aprendizado.

3.5.1 Definindo e Resolvendo um Problema

Inicialmente, devemos definir o problema na planilha do Excel. Vamos resolver como
exemplo o problema da rações, do Capítulo 2. A formulação do problema é a seguinte:

maximizar z = 11 x1 + 12 x2

sujeito a: 1 x1 + 4 x2 10000
5 x1 + 2 x2 30000
x1, x2 0

Para definir o problema na planilha, devemos definir células para representar as variáveis de
decisão e uma célula para representar o valor da função objectivo. Além disso, as restrições
também devem ser definidas.

Abra um novo arquivo no Microsoft Excel e siga os seguintes passos:

1. na célula A1 digite "x1";

2. na célula B1 digite "0";
3. na célula A2 digite "x2";
4. na célula B2 digite "0".

As células A2 e B2 guardarão os valores das variáveis de decisão x1 e x2, respectivamente.

Vamos agora definir a função objectivo. As equações do Excel são sempre precedidas do sinal
de igualdade (=), que indica que nesta célula será efectuada uma conta. Preencha as células da
planilha conforme indicado a seguir:

 na célula A4 digite "Função objectivo";

 na célula B4 digite "=11*B1+12*B2".

Na célula B4 será calculado automaticamente o valor da função objectivo, a partir da função

fornecida.
Qualquer alteração nos valores das células B1 ou B2 fará com que o valor da função objectivo
seja recalculado.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Serão definidas agora as restrições do problema:

As células de restrição devem ser preenchidas da seguinte forma:

1. na célula A6 digite "Restrições";

2. na célula B6 digite "= B1+4*B2";
3. na célula C6 digite "<=";
4. na célula D6 digite "10000";
5. na célula B7 digite "= 5*B1+2*B2";
6. na célula C7 digite "<=";
7. na célula D7 digite "30000";
8. na célula B8 digite "=B1 ";
9. na célula C8 digite ">=";
10. na célula D8 digite "0";
11. na célula B9 digite "=B2";
12. na célula C9 digite ">=";
13. na célula D9 digite "0".

Após preenchidas as células, a planilha deve estar igual à apresentada na Figura

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Para optimizar a função objectivo, vamos utilizar a ferramenta Solver.

1. No menu Ferramentas, clique em Solver. A janela apresentada na Figura 5.2 se abrirá.

2. Na caixa "Definir célula de destino", seleccione a célula da função objectivo (B4)
clicando sobre ela, ou simplesmente digite B4.

Logo abaixo, é requerido que se escolha entre três opções: Máx, para maximizar a função
objectivo, Mín, para minimizar a função objectivo, e Valor, que faz com que a função
objectivo tenha determinado valor.

No nosso exemplo, como queremos maximizar a função objectivo, escolheremos a opção

Máx.

Na caixa "Células variáveis", devem ser inseridas as células ajustáveis, que contêm os valores
das variáveis de decisão. Deve-se inserir um nome ou uma referência para cada célula
ajustável, separando as células não-adjacentes por ponto-e-vírgula. As células ajustáveis
devem estar relacionadas directa ou indirectamente à célula que contém o valor da função
objectivo.

Podem ser especificadas até 200 células ajustáveis. Para que o Solver proponha
automaticamente as células ajustáveis com base na célula de destino, clique em Estimar.

Na caixa Submeter às restrições, devem ser inseridas as restrições do problema. Para inserir
uma restrição, siga os seguintes passos:

 clique no botão "Adicionar". A janela apresentada na Figura 5.3 se abrirá;

 a caixa "Referência de célula", seleccione a célula contendo a primeira restrição (B6);
 na caixa de selecção, escolha a opção que corresponde ao tipo de restrição, que pode ser
menor ou igual (<=), maior ou igual (>=), igual (=), valor inteiro (núm) ou valor binário
(bin).

No nosso caso a opção a ser escolhida é <=;

na caixa "Restrição", defina a célula que contém o valor limite da restrição, ou seja, D6;
clique em OK para adicionar a restrição;
repita estes passos até que todas as restrições estejam adicionadas.

Após serem adicionadas as restrições, a janela deve estar igual à janela da Figura 5.2, excepto
talvez pela presença dos cifrões ($), que indicam que a célula é fixa.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Figura 3.2 - Janela contendo os parâmetros da ferramenta Solver.

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

6. O PROBLEMA DA DUALIDADE

Modelo Inicial  Primal

Substituição  Dual

Primal:
 A função objectivo é de maximização.
 As restrições são todas do tipo .
 As variáveis são não negativas.

Ao modelo primal com es tas condições pode-se associar um outro modelo, chamado Dual,
constituído da seguinte forma:

1. Variáveis de decisão do Dual: a cada restrição do primal faz-se corresponder uma

variável yi.
2. Função objectivo: a f. O. Será de minimização. Cada uma de suas parcelas será o
produto da variável yi pelo termo da direita da restrição correspondente.
3. Restrições técnicas: Cada variável de decisão primal será uma restrição no Dual.
a. Termos da esquerda: Cada termo é o produto da variável dual yi pelo
coeficiente respectivo da variável de decisão primal.
b. Sinal: sinal do tipo .
c. Termo da direita: é o coeficiente da variável primal na f. O.
4. As variáveis yi são todas não negativas.

Exemplo:

Primal: Max Z = 2x1 + 3x2 + x3

3x1  4 x2  2 x3  10
2 x  6 x  x  20
 1 2 3

 x1  x2  x3  30
 xi  0

Dual: Min D = 10y1 + 20y2 + 30y3 (termos da direita)

3 y1  2 y2  1y3  2
4 y  6 y  y  3
 1 2 3

2 y1  y2  y3  1
 yi  0

Analogamente:

Modelo Primal:
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

a. f.o. de minimização
b. restrições do tipo 
c. Variáveis todas não negativas.

Modelo Dual:
a. f.o. de maximização
b. restrições do tipo 
c. variáveis todas não negativas.

Exemplo:

Primal: Min Z = 10x1 + 20x2 + 30x3

3x1  2 x2  x3  2
4 x  6 x  x  3
 1 2 3

2 x1  x2  x3  1
 xi  0

Dual: Max D = 2y1 + 3y2 + y3

3 y1  4 y2  2 y3  10
2 y  6 y  y  20
 1 2 3

 y1  y2  y3  30
 yi  0

Observação:

1. Se uma restrição primal é do tipo “=”, a variável dual correspondente será sem
restrição do sinal.
2. Se uma variável primal for sem restrição de sinal, a restrição do dual
correspondente será do tipo “=”.

Exemplo:

Primal: Max Z = 2x1 + 3x2 + x3

 x1  x2  10  y1

S .a. 2 x1  4 x2  x3  20  y2
x  0
 i

Dual: Min D = 10y1 + 20y2

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

 y1  2 y2  2
y  4y  3
 1 2
S .a. 

 2 y  1
 y1  0 e y2 livre

Analogia entre as soluções Primal e Dual

1. A cada solução básica admissível primal não óptima corresponde uma solução básica
não admissível dual.

2. A solução óptima primal corresponde à solução óptima dual com Z = D.

3. O coeficiente da variável de decisão na f. O. Primal é o valor da variável de folga

correspondente na solução dual.

4. O coeficiente da variável de folga da f.o. primal é o valor da variável de decisão

correspondente na solução dual.

Exemplo:

Primal: Max Z = x1 + 2x2 + 3x3

 x1  x2  x3  10
2 x  x  4 x  12
 1 2 3
s.a. 
 x1  3x2  x3  9
 xi  0

Dual: Min D = 10y1 + 12y2 + 9y3

 y1  2 y2  y3  1
y  y  3y  2
 1 2 3
s.a. 
 y1  4 y2  y3  3
 yi  0

Colocar as variáveis de folga no primal e no dual.

Primal: Max Z = x1 + 2x2 + 3x3

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

 x1  x2  x3  x4  10
2 x  x  4 x  x  12
 1 2 3 5
s.a. 
 x1  3x2  x3  x6  9
 xi  0

1º Quadro Simplex

Z X1 X2 X3 X4 X5 X6 b
1 -1 -2 -3 0 0 0 0
0 1 1 1 1 0 0 10
0 2 1 4 0 1 0 12
0 1 3 -1 0 0 1 9
 x3  10

S .B. A.  x4  12 Z 0
x  9
 5

Dual: Min D = 10y1 + 12y2 + 9y3 ou Max (- D) = -10y1 - 12y2 - 9y3

 y1  2 y2  y3  y4  1
 y  y  3y  y  2
 1 2 3 5
s.a. 
 y1  4 y2  y3  y6  3
 yi  0

1° Quadro Simplex:

D y1 y2 y3 y4 y5 y6 c
-1 10 12 9 0 0 0 0
0 1 2 1 -1 0 0 1
0 1 1 3 0 -1 0 2
0 1 4 -1 0 0 -1 3

 y6   3

S .B.N . A.  y4   1 D0
y   2
 5

A próxima solução básica admissível do primal, com a entrada da variável x3 (coeficiente –3)
e a saída da variável x5 (12 : 4=3) após o pivoteamento, será:

Z X1 X2 X3 X4 X5 X6 b
1 0,5 -1,25 0 0 0,75 0 9
0 0,5 0,75 0 1 -0,25 0 7
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

0 0,5 0,25 1 0 0,25 0 3

0 1,5 3,25 0 0 0,25 1 12

Solução:
X3 = 3 x4 = 7 x6 = 12 Z = 9

Usando a correspondência, pode-se montar o quadro dual correspondente:

 Coeficientes de xi → Valores de yFi

 Coeficientes de xFi → Valores de yi
 Valores de xi → coeficientes de yFi
 Valores de xFi → coeficientes de yi

D y1 y2 y3 y4 y5 y6 c
-1 7 0 12 0 0 3 -9
0 1 0 0,5
0 0 1 -1,25
1 0 0 0,75
Solução:
Y2 = 0,75 y4 = 0,5 y2 = -1,25 D=9

O terceiro quadro primal fornece a solução óptima.

Z X1 X2 X3 X4 X5 X6 b
1 1,077 0 0 0 0,846 0,385 13,615
0 0,154 0 0 1 -0,308 -0,231 4,231
0 0,385 0 1 0 0,231 -0,077 2,077
0 0,461 1 0 0 0,077 0,308 3,692

Solução:
X2 = 3.692 x3 = 2.077 x4 = 4.231 Z = 13.615

Montar o quadro dual:

D y1 y2 y3 y4 y5 y6 c
-1 4,321 0 0 0 3,692 2,077 -13,615
0 0 0 1 0 1,077
0 0 0 0 -1 0,846
0 1 1 0 0 0,385

Solução:

Y2=0.846 y3 = 0.385 y4 = 1.077 D = 13.615

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

A solução dual também é óptima!

Conclusão:
Dado um problema de PL, podemos sempre escolher entre solucionar o modelo primal ou o
modelo dual correspondente. A escolha leva em conta o esforço computacional, que depende
do número de restrições, variáveis artificiais, etc.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Exercício

1. Um pecuarista prepara ração a partir de três ingredientes, que contêm três nutrientes
indispensáveis na alimentação dos animais. O quadro mostra a composição, exigências e
custos dos elementos na mistura.

Nutrientes (% por kg de Ingredientes) Custo

Ingredientes Nutriente 1 Nutriente 2 Nutriente 3 ingredientes
em u.m./kg
1 50 20 10 200
2 20 30 30 150
3 10 20 50 240
Exigência
mínima
6 5 8
Em kg /saco
40kg

O objectivo é atender às exigências com o menor custo possível. Pede-se:

a. Construir o modelo Linear do problema, onde xi são as quantidades dos ingredientes

usados por kg de ração.

b. Construir o modelo dual correspondente.

c. Resolver o problema pelo método Simplex (sugestão: resolva o modelo dual, que

exige menos cálculos).

d. Construa o quadro final Primal e Dual.

e. O que representam as variáveis xFi ?

f. O que representam, no problema, as variáveis yFi ?

g. O que mede a função objectivo dual?

Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Modelo Dual: D = 600y1 + 500y2 + 800y3

50 y1  20 y2  10 y3  200

S .a.20 y1  30 y2  30 y3  150
10 y  20 y  50 y  240
 1 2 3

Solução Dual
D y1 y2 y3 y4 y5 y6 c
-1 0 325.38 0 1.54 26.15 0 4.230,77
0 1 0.23 0 0.02 -0.01 0 3.46
0 0 0.85 1 -0.02 0.04 0 2.69
0 0 -24.62 0 0.54 -1.85 1 70.77

2. Suponha que um problema de produção tenha como modelo:

L  x1  0,3x2  3 x3  Max

 x1  x2  x3  10
2 x  x  4 x  12
 1 2 3
S .a. : 
 x1  3 x2  x3  9
 xi  0

E que o quadro final de solução pelo Simplex seja:

L x1 x2 x3 x4 x5 x6 b
1 0.5 0.45 0 0 0.75 0 9
0 0.5 0.75 0 1 -0.25 0 7
0 0.5 0.25 1 0 0.25 0 3
0 1.5 3.25 0 0 0.25 1 12

Onde xi são as decisões de fabricação dos produtos Pi e xFi as sobras dos recursos Ri no
programa. O objectivo é maximizar o lucro devido a produção e comercialização dos
produtos.
Responder às perguntas:
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

Interpretação Económica do Dual

Considere-se o exemplo de programação da produção de dois bens P1 e P2, a partir dos

recursos R1 e R2. O quadro abaixo resume os dados.

Recurso R1 Recurso R2
Produtos Lucro por unidade
Uso por unidade Uso por unidade
P1 2 10 50
P2 3 5 90
Disponibilidade de
300 1.000
recursos

O modelo linear, onde x1 e x2 são as decisões de produção no período programado é:

Lucro  50 x1  90 x2  Max

2 x1  3x2  300

Sujeito a : 10 x1  5 x2  1000
x  0
 i

O quadro final de Simplex, onde xF1 e xF2 são as sobras dos recursos R1 e R2, é:
L x1 x2 x4 x5 b
1 10 0 30 0 9000
0 0.67 1 0.33 0 100
0 6.65 0 -1.65 1 500

O modelo Dual correspondente é:

D = 300y1 + 1000y2 → Min

2 y1  10 y2  50

Sujeito a : 3 y1  5 y2  90
y  0
 i
O quadro final, derivado da solução primal, é:
D y1 y2 y4 y5 c
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

-1 0 500 0 100 -9000

0 1 0 30
0 0 1 10

Interpretação:
1. O valor de y1 (30), foi obtido do coeficiente de xF1, e representa, portanto, o valor de
oportunidade do recurso R1, isto é, cada unidade de R1 tem capacidade de gerar um
lucro de 30.

2. O valor de y2 (0), foi obtido do coeficiente de xF2, indicando o valor de oportunidade

do recurso R2. O resultado é coerente, já que o recurso R2 não é escasso (xF2 = 500).

3. O valor de y1 é, portanto, o valor de oportunidade por unidade do recurso R1, isto é, a

capacidade da unidade do recurso gerar lucro, neste programa.

4. Na F.O. dual, cada parcela mede, então, o valor de oportunidade dos recursos
envolvidos na produção (estoque x valor de oportunidade unitário do recurso). A F.O.
dual mede, portanto, a capacidade de o estoque de recursos gerar lucros.

5. Na resolução óptima, este valor coincide com o lucro atribuído aos produtos pelo
mercado, isto é, o valor de oportunidade dos produtos no mercado.

6. Cada uma das restrições compara o valor de oportunidade atribuído aos produtos pelos
recursos, com o valor de oportunidade atribuído aos produtos pelo mercado.
7. Na primeira restrição, por exemplo 2y1 + 10y2 está indicando que o produto P1, que
usa duas unidades de R1 e 10 de R2, tem esse valor de oportunidade calculado em
termos desses produtos.

8. O lado esquerdo, 50, indica o valor de oportunidade atribuído pelo mercado. Este
valor é também chamado valor externo, em contraposição ao valor atribuído pelos
recursos, chamado valor interno.
Investigação Operacional I 2º ano de Contabilidade e Auditório - Método Simplex
Docente: Mestre Leonardo Muteia,MBA
Ano: 2024

9. Quando a remuneração do mercado (valor externo) cobre o valor interno, o produto é

fabricado ( a diferença yFi = 0, portanto xi é básico).

10. Se o valor de mercado for menor que o valor interno, o produto não será fabricado.
Isto quer dizer que existe uso alternativo para os recursos no programa, que é capaz de
gerar lucros e equivalente o seu valor de oportunidade.