Resolução de Problemas de Prog Linear_PO Fametro

Prévia do material em texto

Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
1 
 
RESOLUÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR 
 
1. CONCEITOS BÁSICOS 
 Antes de sermos introduzidos ao Método Simplex, ferramenta que se utiliza para a 
resolução de problemas de alocação de recursos em Pesquisa Operacional, vamos apresentar 
algumas conceituações básicas. 
 
1.1. SOLUÇÃO DO MODELO 
 O conjunto das restrições forma um sistema de desigualdades lineares e, dessa 
maneira, existem infinitas combinações de valores de x1 e x2 que satisfazem à essas restrições. 
Para descobrir aquela que produz o melhor valor para o objetivo, vamos partir de um par de 
valores para x1 e x2 e tentar encontrar aquele que fornece o melhor resultado (ANDRADE, 
2004). 
 Exemplo: Maximizar Lucro = 4x1 + 1x2 
 x1 = Quantidade de mesas produzidas 
 x2 = Quantidade de armários produzidos 
 Restrições: 
 Madeira: 2x1 + 3x2 ≤ 12 
 Mão de obra: 2x1 + 1x2 ≤ 8 
 Não negatividade: x1 ≥ 0 
 x2 ≥ 0. 
 Solução 1: Começando por analisar a produção de mesas, podemos manter a produção 
de armários em nível zero. Voltando às restrições, fazendo x2 = 0 e considerando a utilização 
de todos os recursos, temos as seguintes relações: 
 Madeira Mão de obra 
 2x1 + 3x2 = 12 2x1 + 1x2 = 8 
 2x1 = 12 2x1 = 8 
 x1 = 6 x1 = 4 
 Para produzir mesa usam-se os dois recursos, mas é evidente que o maior valor 
possível para x1 é 4, já que não teríamos mão de obra suficiente para produzirmos 6 mesas. 
 Para esta solução teríamos o seguinte lucro: 
x1 = 4 mesas e x2 = 0 armários 
L = 4 × 4 + 1 × 0 = 16 
 Madeira: 2 × 4 + 3 × 0 = 8 Mão de obra: 2 × 4 + 1 × 0 = 8 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
2 
 
0
1
2
3
4
5
6
7
8
9
0 2 4 6 8
x 2
x1
Representação gráfica das restrições
Restrição 1
Restriçao 2
 Análise da solução: Ainda há madeira sobrando e a produção de armário é nula. 
Havendo a intenção de produzir também o outro produto, pode-se buscar outra solução mais 
satisfatória. 
 Solução 2: Como o 1° recurso tem folga, não precisamos nos preocupar com a 1ª 
equação. Tomando x2 = 1, temos: 
Mão de obra: 2x1 + 1 × 1 = 8 x1 = 3,5 
 Observe que a produção de 1 armário exige diminuição da quantidade de mesas 
produzidas em 0,5. Logo 
L = 4 × 3,5 + 1 × 1 = 15 
 Conclusão: Para esse modelo, não é vantajoso produzir armários. 
 
2. SOLUÇÃO GRÁFICA 
 A representação gráfica de uma equação linear com duas variáveis é uma reta. A 
representação gráfica de uma inequação linear com duas variáveis é um dos semiplanos 
definidos pela reta correspondente à equação (SILVA, 1998). 
 Exemplo: Representar graficamente a região de possíveis soluções para o modelo 
anterior. 
(a) Construir as retas correspondentes às equações obtidas pelas restrições. 
Madeira: 2x1 + 3x2 ≤ 12 2x1 + 3x2 = 12 (1) 
 Fazendo x1 = 0 temos x2 = 4, gerando o par (0, 4). 
 Fazendo x2 = 0 temos x1 = 6, gerando o par (6, 0). 
Mão de obra: 2x1 + 1x2 ≤ 8 2x1 + 1x2 = 8 (2) 
 Fazendo x1 = 0 temos x2 = 8, gerando o par (0, 8). 
 Fazendo x2 = 0 temos x1 = 4, gerando o par (4, 0). 
Sinalizando no gráfico: 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
3 
 
0
1
2
3
4
5
6
7
8
9
0 2 4 6 8
x 2
x1
Representação gráfica das áreas das restrições
Restrição 1
Restriçao 2
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7
x 2
x1
Família de retas paralelas definidas pela função 
objetivo
Solução 
ótima: x1 = 4, 
x2 = 0 e L = 16
(b) Sinalizar o sentido determinado pelas inequações das restrições e hachurar suas 
respectivas áreas. A área coincidente entre as duas áreas delimitadas é a região de 
soluções. 
 
 
 
 
 
 
 
 
 
 
 
 
(c) Avaliar o desempenho da função objetivo. 
Escolhemos um valor arbitrário para L = 4x1 + 1x2, por exemplo o valor 8, 
encontrando possíveis pontos (x1, x2) para esse lucro: 
 Fazendo x1 = 0, temos x2 = 8, gerando o par (0, 8). 
 Fazendo x2 = 0 temos x1 = 2, gerando o par (2, 0). 
Escolhendo um segundo valor para L, por exemplo 12, então: 
 Fazendo x1 = 0, temos x2 = 12, gerando o par (0, 12). 
 Fazendo x2 = 0 temos x1 = 3, gerando o par (3, 0). 
Escolhendo ainda um terceiro valor para L, por exemplo 16, então: 
 Fazendo x1 = 0, temos x2 = 16, gerando o par (0, 16). 
 Fazendo x2 = 0 temos x1 = 4, gerando o par (4, 0). 
Sinalizando no gráfico: 
 
 
 
 
 
 
 
 
 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
4 
 
Verificamos do gráfico que: 
 À medida que atribuímos valores a L, obtemos retas paralelas. 
 À medida que o valor de L aumenta, a reta se afasta da origem do sistema 
de eixos. 
Podemos concluir que pelo ponto P do gráfico teremos a paralela de maior valor 
que ainda apresenta um ponto na região de soluções. Portanto, o ponto P é a 
solução que maximiza L na região de soluções dadas. 
 
3. VARIÁVEIS DE FOLGA 
 Andrade (2004) afirma que para transformarmos as desigualdades lineares das 
restrições em equações lineares, de modo que possam ser aplicados os métodos de solução 
dessas equações, devemos considerar a seguinte estrutura: 
UTILIZAÇÃO DE RECURSO ≤ DISPONIBILIDADE 
 Se introduzirmos o conceito de FOLGA DE RECURSO, podemos escrever essa 
relação da seguinte maneira: 
UTILIZAÇÃO + FOLGA = DISPONIBILIDADE 
 Isto significa que 
 UTILIZAÇÃO < DISPONIBILIDADE implica FOLGA > 0. 
 UTILIZAÇÃO = DISPONIBILIDADE implica FOLGA = 0. 
 Assim, a folga de cada recurso pode ser representada por uma variável de modo 
exatamente igual à produção de cada produto. Voltando ao modelo anterior, vamos chamar 
 x3 = folga de madeira 
x4 = folga de mão de obra 
 Introduzindo x3 para a primeira desigualdade e x4 para a segunda, temos nosso sistema 
formado: 
 Maximizar L = 4x1 + 1x2 + 0x3 + 0x4 
 Sujeito a: 2x1 + 3x2 + 1x3 + = 12 
 2x1 + 1x2 + + 1x4 = 8 
 x1, x2, x3 e x4 ≥ 0 
 
4. SOLUÇÃO POR SISTEMA DE EQUAÇÕES LINEARES 
 Quando o número de incógnitas (n) é superior ao número de equações (m), o sistema 
de equações é indeterminado, apresentando infinitas soluções. Neste caso, as soluções são 
encontradas atribuindo arbitrariamente valor zero a n – m variáveis e calculando o valor das 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
5 
 
outras pelo sistema restante. Resolvido um sistema, utilizamos os valores encontrados para as 
variáveis na função objetivo, achando assim o lucro L (SILVA, 1998). 
 As variáveis às quais atribuímos valor 0 serão chamadas variáveis não-básicas, as 
variáveis cujos valores foram encontrados pela solução dos sistemas de equações (valores 
positivos), são as variáveis básicas e o conjunto das variáveis básicas é a base. 
 Exemplo: Encontrar a solução por sistemas de equações lineares para o modelo 
anterior. 
 Temos que n = 4 e m = 2. Assim, faremos combinações considerando n – m = 2 
variáveis nulas: 
(1) Variáveis não-básicas: x1 = 0 e x2 = 0 
Variáveis básicas: x3 = 12 e x4 = 8 
Lucro = 0 
(2) Variáveis não-básicas: x1 = 0 e x3 = 0 
Variáveis básicas: x2 = 4 e x4 = 4 
Lucro = 4 
(3) Variáveis não-básicas: x1 = 0 e x4 = 0 
Variáveis básicas: x2 = 8 e x3 = - 12 
Como x3 < 0, a solução é inviável. 
(4) Variáveis não-básicas: x2 = 0 e x3 = 0 
Variáveis básicas: x1 = 6 e x4 = - 4 
Como x4 < 0, a solução é inviável. 
(5) Variáveis não-básicas: x2 = 0 e x4 = 0 
Variáveis básicas: x1 = 4 e x3 = 4 
Lucro= 16 
(6) Variáveis não-básicas: x3 = 0 e x4 = 0 
Variáveis básicas: x1 = 3 e x2 = 2 
Lucro = 14 
 Comparando todas as soluções encontradas, achamos a mesma solução ótima obtida 
anteriormente, ou seja: 
x1 = 4, x2 = 0, x3 = 4, x4 = 0 e L = 16. 
 Essas seis soluções encontradas também podem ser visualizadas em um gráfico de 
equações lineares, como mostra a figura abaixo. Como se pode ver na figura, as duas soluções 
inviáveis encontradas (sistemas 3 e 4) correspondem a pontos que se encontram fora da região 
de soluções. 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
6 
 
0
1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6 7
x2
x1
Representação gráfica das soluções 
encontradas
 
 
 
 
 
 
 
 
 
 
 
 
5. O MÉTODO SIMPLEX 
 A solução algébrica anterior mostrou que a resolução de um problema de programação 
linear consiste basicamente em resolver sistemas de equações lineares e calcular o valor da 
função objetivo. Comparando os diversos valores obtidos para a função objetivo, escolhemos 
como solução do problema o resultado do sistema de equações que fornece o melhor valor. 
 Esse procedimento, apesar de correto, é bastante trabalhoso, já que temos de resolver 
todos os sistemas para podermos escolher o que fornece o melhor valor para a função 
objetivo. Basta um pequeno problema real de programação linear, no qual poderíamos ter, por 
exemplo, 10 equações e 15 variáveis, para inviabilizarmos o processo, já que o número de 
sistemas de equações que deveríamos resolver seria muito elevado (ANDRADE, 2004). 
 Assim, para termos condições de resolver um problema de programação linear, 
precisamos de uma sistemática que responda às seguintes questões: 
 Qual sistema de equações deve ser resolvido? 
 O próximo sistema a ser resolvido fornecerá uma solução melhor que os 
anteriores? 
 Como identificar uma solução ótima, uma vez que a tenhamos encontrado? 
 Essa sistemática é o Método Simplex e as regras que o método utiliza para atender a 
essas três questões são, basicamente, os critérios que desenvolvemos nos itens anteriores. 
 
5.1. CRITÉRIOS DO MÉTODO SIMPLEX 
 Andrade (2004) afirma que esse método é formado por um grupo de critérios para 
escolha de soluções básicas que melhorem o desempenho do modelo que testa a otimalidade. 
Sistema 3: 
x1 = 0 e x2 = 8 
Sistema 2: 
x1 = 0 e x2 = 4 
Sistema 1: 
x1 = 0 e x2 = 0 
Sistema 4: 
x1 = 6 e x2 = 0 
Sistema 5: 
x1 = 4 e x2 = 0 
Sistema 6: 
x1 = 3 e x2 = 2 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
7 
 
Para isso, o problema deve apresentar uma solução básica inicial. As 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. 
 Os critérios para escolha de vetores e consequentemente das variáveis que entram e 
que saem para a formação da nova base constituem o centro do simplex. 
 Suponhamos inicialmente que o modelo apresente uma solução básica inicial. Os 
modelos com restrições do tipo ≤ e com termos da direita não negativos têm solução básica 
formada pelas variáveis de folga. 
 Exemplo: 
 Maximizar Z = 3x1 + 5x2 
 Sujeito a: 2x1 + 4x2 ≤ 10 
 6x1 + 1x2 ≤ 20 
 1x1 + 1x2 ≤ 30 
 x1 ≥ 0, x2 ≥ 0 
 Acrescentando as variáveis de folga nas restrições 
 2x1 + 4x2 + 1x3 + + = 10 
 6x1 + 1x2 + + 1x4 + = 20 
 1x1 + 1x2 + + + 1x5 = 30 
 x1, x2, x3, x4 e x5 ≥ 0 
 Podemos visualizar uma solução formada pelas variáveis de folga. Basta fazer x1 = 0 e 
x2 = 0 e teremos: x3 = 10, x4 = 20 e x5 = 30. Neste caso a solução básica inicial será x1 = 0, x2 
= 0, x3 = 10, x4 = 20 e x5 = 30. 
 
5.2. DESCRIÇÃO DO MÉTODO 
 1ª Parte: Teste de otimalidade para a solução. 
 O método considera que enquanto a função objetivo apresentar variáveis não-básicas 
com coeficientes positivos, ela poderá ser aumentada, não sendo portanto a solução ótima. 
 Reescrevendo a função objetivo do exemplo anterior com todas as variáveis à 
esquerda temos: 
Z – 3x1 – 5x2 = 0 
 Os coeficientes positivos à direita são negativos à esquerda, portanto, os coeficientes 
negativos à esquerda indicam que o valor de Z pode ser aumentado com a entrada de uma das 
variáveis na base, e na proporção de seu coeficiente. Escrito dessa forma, a solução testada só 
será ótima quando as variáveis não-básicas não apresentarem coeficientes negativos 
(ANDRADE, 2004). 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
8 
 
 2ª Parte: Análise da solução básica inicial. 
 Voltemos ao nosso problema das mesas e armários a serem produzidos, já com as 
variáveis de folga: 
 Maximizar L = 4x1 + 1x2 + 0x3 + 0x4 
 Sujeito a: 2x1 + 3x2 + 1x3 = 12 
 2x1 + 1x2 + + 1x4 = 8 
 x1, x2, x3 e x4 ≥ 0 
 No caso da função objetivo, temos: 
L – 4x1 – 1x2 – 0x3 – 0x4 = 0 
 Podemos estabelecer uma notação matricial para esse modelo: 
 
 Montando um quadro para ordenarmos as operações, colocando nele somente os 
coeficientes das variáveis, temos (SILVA, 1998): 
QUADRO 1 
x1 x2 x3 x4 b 
2 3 1 0 12 
2 1 0 1 8 
-4 -1 0 0 0 
 
 A solução básica inicial para o problema será sempre obtida tornando-se as variáveis 
originais do modelo (no caso x1 e x2) iguais a zero e achando-se os valores das demais. 
 Assim, tornando x1 = x2 = 0 (variáveis não-básicas) obtemos o seguinte quadro: 
 
QUADRO 2 
BASE x1 x2 x3 x4 b 
x3 2 3 1 0 12 
x4 2 1 0 1 8 
L -4 -1 0 0 0 
 
onde vemos que x3 = 12, x4 = 8 (variáveis básicas) e L = 0. 
 Obviamente, essa solução não é a melhor, por isso vamos procurar outra que forneça 
um valor maior para L. Para fazermos isso, vamos nos basear na primeira solução do Quadro 
2 e aplicar os critérios de alternação nas variáveis não-básicas. Como já vimos, essa segunda 
solução também deverá ter duas variáveis nulas e duas positivas. 
 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
9 
 
 3ª Parte: Variáveis que entram e que saem da base. 
 A pergunta é, das duas variáveis não-basicas (nulas) na primeira solução, qual deverá 
se tornar positiva? E das duas variáveis básicas (positivas) qual deverá ser anulada? 
 Analisando a última linha do QUADRO 2, temos que o coeficiente da função objetivo 
que mais contribui para o lucro L é o da variável x1 (4). Logo, a variável que deverá se tornar 
positiva entrando na base é x1 (ANDRADE, 2004). 
 Para saber qual variável básica deverá sair da base tornando-se nula, devemos 
descobrir qual é o maior valor que podemos atribuir a x1. Examinando as equações das 
restrições em função de x1 e das variáveis básicas atuais temos: 
 Equação 1: 2x1 + 1x3 = 12 e Equação 2: 2x1 + 1x4 = 8. 
 Fazendo x3 = 0 e x4 = 0: 
 Equação 1 Equação 2 
 2x1 + 1x3 = 12 2x1 + 1x4 = 8 
 x1 = 6 x1 = 4 
 Já sabemos que o valor possível para x1 é 4, pois se trata da mão de obra existente. 
Assim, descobrimos que a variável que se anulará é x4. 
 Observe que essa análise pode ser feita diretamente no QUADRO 2 através da divisão 
dos elementos da coluna “b” pelos correspondentes elementos da coluna x1. O menor 
quociente indica, pela linha em que ocorreu, qual variável deverá ser anulada. 
 
 4ª Parte: Cálculo da nova solução básica. 
 Antes de iniciarmos o cálculo da nova solução básica, devemos ser introduzidos ao 
conceito de elemento pivô. No quadro da solução básica inicial, a linha da variável que sai da 
base é chamada linha pivô. No cruzamento da coluna da variável que entra com a linha pivô 
identificamos o coeficientechamado elemento pivô (ANDRADE, 2004). No quadro abaixo 
temos destacados a linha e o elemento pivô. 
 
QUADRO 3 
BASE x1 x2 x3 x4 b 
x3 2 3 1 0 12 
x4 2 1 0 1 8 
L -4 -1 0 0 0 
 
 
 O procedimento se inicia pela divisão da linha pivô pelo elemento pivô (2), resultando 
no quadro abaixo. 
 
Elemento pivô 
Linha pivô 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
10 
 
QUADRO 4 (1ª Operação) 
BASE x1 x2 x3 x4 b 
x3 2 3 1 0 12 
x1 1 
 
0 
 
4 
L -4 -1 0 0 0 
 
 Para atualizarmos as outras duas linhas, realizamos operações básicas de matrizes 
tomando a nova linha pivô como parâmetro. O objetivo é deixar não nulo apenas o 
coeficiente da variável que entra (ANDRADE, 2004). 
 Cálculo da nova 1ª linha: Multiplicar a nova 2ª linha do QUADRO 4 por – 2 e somar 
com a 1ª linha do mesmo quadro, colocando o resultado na primeira linha. 
 
 2ª linha×(-2): -2 -1 0 -1 -8 
 + 1ª linha: 2 3 1 0 12 
 Nova 1ª linha: 0 2 1 -1 4 
 
QUADRO 5 (2ª Operação) 
BASE x1 x2 x3 x4 b 
x3 0 2 1 -1 4 
x1 1 
 
0 
 
4 
L -4 -1 0 0 0 
 
 Cálculo da nova 3ª linha: Multiplicar a nova 2ª linha do QUADRO 4 por 4 e somar 
com a 3ª linha do mesmo quadro, colocando o resultado na terceira linha. 
 
 2ª linha×4: 4 2 0 2 16 
 + 3ª linha: -4 -1 0 0 0 
 Nova 3ª linha: 0 1 0 2 16 
 
QUADRO 6 (3ª Operação) 
BASE x1 x2 x3 x4 b 
x3 0 2 1 -1 4 
x1 1 
 
0 
 
4 
L 0 1 0 2 16 
 
 Como os coeficientes da última linha são todos positivos ou nulos, concluímos que a 
solução encontrada é ótima. 
 A nova solução é: 
 x1 = 4, x2 = 0, x3 = 4, x4 = 0 e L = 16. 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
11 
 
5.3. O PROBLEMA DA MINIMIZAÇÃO 
 Se a função objetivo for de minimização, devemos multiplicá-la por -1, obtendo uma 
função equivalente para maximização (SILVA, 1998). 
 Exemplo: 
 Minimizar Z = 3x1 – 4x2 + 1x3 
 Sujeito a: 1x1 + 1x2 + 1x3 ≤ 10 
 2x1 + 1x2 – 1x3 ≤ 20 
 x1, x2 e x3 ≥ 0 
 O modelo equivalente é: 
 Maximizar – Z = – 3x1 + 4x2 – 1x3 
 Sujeito a: 1x1 + 1x2 + 1x3 ≤ 10 
 2x1 + 1x2 – 1x3 ≤ 20 
 x1, x2 e x3 ≥ 0 
 Resolvido o modelo equivalente, teremos a solução do modelo original com a troca do 
sinal de Z. 
 
5.4. RESTRIÇÃO DO TIPO ≥ E = 
 Em todos os problemas vistos até aqui, a solução básica inicial era formada pelas 
variáveis de folga, já que as restrições eram do tipo ≤. Quando as restrições são do tipo = ou 
≥, não existe essa solução básica inicial. 
 Quando a restrição é do tipo ≥, a variável de folga é subtraída e seu valor é negativo , 
representando variáveis de excesso. Quando a restrição é do tipo =, não há acréscimo de 
variável de folga. Em ambos os casos, acrescentamos variáveis auxiliares ai com a formação 
de um novo modelo. A solução básica inicial do novo modelo é formada pelas variáveis de 
folga das restrições do tipo ≤ e pelas variáveis auxiliares ai (ANDRADE, 2004). 
 Esse procedimento de inserção de variáveis auxiliares faz o Método Simplex 
desdobrar-se em três fases: 
I. Criar uma função objetivo auxiliar Za formada pela soma dos coeficientes das 
variáveis reais e de folga. Os coeficientes das variáveis auxiliares também serão 
somados a Za, mas assumirão valor zero. Neste caso, o valor inicial da função 
objetivo auxiliar é a soma dos termos independentes das restrições. Obs: Somente 
os coeficientes das linhas com variáveis auxiliares serão incluídos. 
II. Monta-se o quadro de solução de modo exatamente igual à sistemática anterior, 
colocando-se a função objetivo auxiliar na última linha. Aplica-se o Método 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
12 
 
Simplex normalmente, tomando como função objetivo a última linha. Quando a 
solução ótima for atingida, dois casos podem ocorrer: 
a. Za = 0: Neste caso foi obtida uma solução básica do problema original e o 
processo de solução deve continuar (fase III). 
b. Za ≠ 0: Neste caso o problema original não tem solução viável, o que 
significa que as restrições devem ser inconsistentes. 
III. Ocorrendo Za = 0, aplica-se o Método Simplex ao quadro encontrado desprezando-
se as variáveis auxiliares e os elementos da última linha. 
 Exemplo: 
 Maximizar Z = 1x1 + 1x2 + 1x3 
 Sujeito a: 2x1 + 1x2 – 1x3 ≤ 10 
 1x1 + 1x2 + 2x3 ≥ 20 
 2x1 + 1x2 + 3x3 = 60 
 x1, x2 e x3 ≥ 0 
 Acrescentando as variáveis de folga: 
 2x1 + 1x2 – 1x3 + 1x4 = 10 
 1x1 + 1x2 + 2x3 + – 1x5 = 20 
 2x1 + 1x2 + 3x3 = 60 
 Acrescentando na segunda e terceira restrições as variáveis auxiliares a2 e a3: 
 2x1 + 1x2 – 1x3 + 1x4 = 10 
 1x1 + 1x2 + 2x3 + – 1x5 + 1a2 = 20 
 2x1 + 1x2 + 3x3 + + + 1a3 = 60 
onde x1, x2, x3, x4, x5, a2 e a3 ≥ 0. 
 Teremos agora uma solução básica inicial: x4 = 10, a2 = 20, a3 = 60 com as outras 
variáveis todas nulas. 
 
 FASE I: 
 Função objetivo: Z – 1x1 – 1x2 – 1x3 – 0x4 – 0x5 – 0a2 – 0a3 = 0 
 Função objetivo auxiliar: 1x1 + 1x2 + 2x3 + – 1x5 + 1a2 = 20 
 2x1 + 1x2 + 3x3 + + + + 1a3 = 60 
 Za – (3x1 + 2x2 + 5x3 + 0x5 – 1x5 + 0a2 + 0a3 = 80) 
 
 
 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
13 
 
 FASE II: 
QUADRO 7 
BASE x1 x2 x3 x4 x5 a2 a3 b 
x4 2 1 -1 1 0 0 0 10 
a2 1 1 2 0 -1 1 0 20 
a3 2 1 3 0 0 0 1 60 
Z -1 -1 -1 0 0 0 0 0 
Za -3 -2 -5 0 -1 0 0 -80 
 
 Variável que entra: x3 (maior coeficiente negativo em Za). 
 Variável que sai: a2 (menor resultado da divisão de b pelos coeficientes de x3). 
 
QUADRO 8: Divisão da 2ª linha por 2. 
BASE x1 x2 x3 x4 x5 a2 a3 b 
x4 2 1 -1 1 0 0 0 10 
x3 0,5 0,5 1 0 -0,5 0,5 0 10 
a3 2 1 3 0 0 0 1 60 
Z -1 -1 -1 0 0 0 0 0 
Za -3 -2 -5 0 -1 0 0 -80 
 
 Cálculo das novas linhas do quadro: 
 
 2ª linha: 0,5 0,5 1 0 -0,5 0,5 0 10 
 + 1ª linha: 2 1 -1 1 0 0 0 10 
 Nova 1ª linha: 2,5 1,5 0 1 -0,5 0,5 0 20 
 
 
 2ª linha×(-3): -1,5 -1,5 -3 0 1,5 -1,5 0 -30 
 + 3ª linha: 2 1 3 0 0 0 1 60 
 Nova 3ª linha: 0,5 -0,5 0 0 1,5 -1,5 1 30 
 
 
 2ª linha: 0,5 0,5 1 0 -0,5 0,5 0 10 
 + 4ª linha: -1 -1 -1 0 0 0 0 0 
 Nova 4ª linha: -0,5 -0,5 0 0 -0,5 0,5 0 10 
 
 
 2ª linha×5: 2,5 2,5 5 0 -2,5 2,5 0 50 
 + 5ª linha: -3 -2 -5 0 1 0 0 -80 
 Nova 5ª linha: -0,5 0,5 0 0 -1,5 2,5 0 -30 
 
 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
14 
 
QUADRO 9 
BASE x1 x2 x3 x4 x5 a2 a3 b 
x4 2,5 1,5 0 1 -0,5 0,5 0 20 
x3 0,5 0,5 1 0 -0,5 0,5 0 10 
a3 0,5 -0,5 0 0 1,5 -1,5 1 30 
Z -0,5 -0,5 0 0 -0,5 0,5 0 10 
Za -0,5 0,5 0 0 -1,5 2,5 0 -30 
 
 Variável que entra: x5 (maior coeficiente negativo em Za). 
 Variável que sai: a3 (menor resultado da divisão de b pelos coeficientes de x5). 
 
QUADRO 10: Divisão da 3ª linha por 1,5. 
BASE x1 x2 x3 x4 x5 a2 a3 b 
x4 2,5 1,5 0 1 -0,5 0,5 0 20 
x3 0,5 0,5 1 0 -0,5 0,50 10 
x5 0,333 -0,333 0 0 1 -1 0,667 20 
Z -0,5 -0,5 0 0 -0,5 0,5 0 10 
Za -0,5 0,5 0 0 -1,5 2,5 0 -30 
 
 Cálculo das novas linhas do quadro: 
 
 3ª linha×0,5: 0,166 -0,166 0 0 0,5 -0,5 0,333 10 
 + 1ª linha: 2,5 1,5 0 1 -0,5 0,5 0 20 
 Nova 1ª linha: 2,666 1,334 0 1 0 0 0,333 30 
 
 
 3ª linha×0,5: 0,166 -0,166 0 0 0,5 -0,5 0,333 10 
 + 2ª linha: 0,5 0,5 1 0 -0,5 0,5 0 10 
 Nova 2ª linha: 0,666 0,334 1 0 0 0 0,333 20 
 
 
 3ª linha×0,5: 0,166 -0,166 0 0 0,5 -0,5 0,333 10 
 + 4ª linha: -0,5 -0,5 0 0 -0,5 0,5 0 10 
 Nova 4ª linha: -0,334 -0,666 0 0 0 0 0,333 20 
 
 
 3ª linha×1,5: 0,499 -0,499 0 0 1,5 -1,5 1 30 
 + 5ª linha: -0,5 0,5 0 0 -1,5 2,5 0 -30 
 Nova 5ª linha: 0 0 0 0 0 1 1 0 
 
 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
15 
 
QUADRO 11 
BASE x1 x2 x3 x4 x5 a2 a3 b 
x4 2,666 1,334 0 1 0 0 0,333 30 
x3 0,666 0,334 1 0 0 0 0,333 20 
x5 0,333 -0,333 0 0 1 -1 0,667 20 
Z -0,334 -0,666 0 0 0 0 0,333 20 
Za 0 0 0 0 0 1 1 0 
 
 
 FASE III: 
QUADRO 12: Retirada das variáveis auxiliares e de Za. 
BASE x1 x2 x3 x4 x5 b 
x4 2,666 1,334 0 1 0 30 
x3 0,666 0,334 1 0 0 20 
x5 0,333 -0,333 0 0 1 20 
Z -0,334 -0,666 0 0 0 20 
 
 Variável que entra: x2 (maior coeficiente negativo em Z). 
 Variável que sai: x4 (menor resultado da divisão de b pelos coeficientes de x2). 
 
QUADRO 13: Divisão da 1ª linha por 1,334. 
BASE x1 x2 x3 x4 x5 b 
x2 2 1 0 0,75 0 22,5 
x3 0,666 0,334 1 0 0 20 
x5 0,333 -0,333 0 0 1 20 
Z -0,334 -0,666 0 0 0 20 
 
 Cálculo das novas linhas do quadro: 
 
 1ª linha×(-0,334): -0,668 -0,334 0 -0,25 0 -7,5 
 + 2ª linha: 0,666 0,334 1 0 0 20 
 Nova 2ª linha: 0 0 1 -0,25 0 12,5 
 
 
 1ª linha×0,333: 0,666 0,333 0 0,25 0 7,5 
 + 3ª linha: 0,333 -0,333 0 0 1 20 
 Nova 3ª linha: 1 0 0 0,25 1 27,5 
 
 
 1ª linha×0,666: 1,332 0,666 0 0,5 0 15 
 + 4ª linha: -0,334 -0,666 0 0 0 20 
 Nova 4ª linha: 1 0 0 0,5 0 35 
 
Pesquisa Operacional – Apostila III 
Prof.ª Alba Gonçalves 
16 
 
QUADRO 14 
BASE x1 x2 x3 x4 x5 b 
x2 2 1 0 0,75 0 22,5 
x3 0 0 1 -0,25 0 12,5 
x5 1 0 0 0,25 1 27,5 
Z 1 0 0 0,5 0 35 
 
 A nova solução é: 
 x1 = 0, x2 = 22,5, x3 = 12,5, x4 = 0, x5 = 27,5 e L = 35. 
 
EXERCÍCIOS 
1) Resolva os seguintes modelos de programação linear pelo Método Simplex: 
a) Maximizar Z = 3x1 + 5x2 
 Sujeito a: 1x1 ≤ 4 
 1x2 ≤ 6 
 3x1 + 5x2 ≤ 18 
 x1 e x2 ≥ 0 
b) Maximizar Z = 2x1 + 3x2 + 1x3 
 Sujeito a: 1x1 + 1x2 + 1x3 ≤ 40 
 2x1 + 1x2 – 1x3 ≤ 20 
 3x1 + 2x2 – 1x3 ≤ 30 
 x1, x2 e x3 ≥ 0 
c) Minimizar Z = 3x1 + 2x2 
 Sujeito a: 2x1 + 1x2 ≥ 10 
 1x1 + 5x2 ≥ 15 
 x1 e x2 ≥ 0 
d) Minimizar Z = 16x1 + 12x2 + 5x3 
 Sujeito a: 8x1 + 4x2 + 4x3 ≥ 16 
 4x1 + 6x2 ≥ 15 
 x1, x2 e x3 ≥ 0 
 
6. REFERÊNCIA BIBLIOGRÁFICA 
 ANDRADE, Eduardo Leopoldino de. Introdução à pesquisa operacional. 3ª ed. Rio 
de Janeiro: LTC, 2004. 
 SILVA, Ermes Medeiros, ET AL. Pesquisa Operacional. 3ª edição. São Paulo: Atlas, 
1998.