Apostila de Pesquisa Operacional - Parte I

Prévia do material em texto

UNIVERSIDADE SÃO FRANCISCO 
 
 
 
 
 
 
 
DISCIPLINA 
 
 
 
PESQUISA OPERACIONAL 
Parte I 
 
 
 
 
 
Adalberto Nobiato Crespo 2018 Versão 6 
2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
 
SUMÁRIO 
 
1 PESQUISA OPERACIONAL ................................................................................. 5 
1.1 Introdução .............................................................................................. 5 
 
2 SISTEMA DE INEQUAÇÕES LINEARES .......................................................... 8 
2.1 Sistema de Inequações Lineares com Variáveis não Negativas ........... 9 
2.2 Sistema de Equações Lineares na Forma Canônica ........................... 10 
2.3 Conjuntos Convexos ............................................................................ 11 
 
3 PROGRAMAÇÃO LINEAR .................................................................................. 13 
3.1 Conceitos e Definições ........................................................................ 13 
3.2 Áreas de Aplicação da Programação Linear ....................................... 13 
3.3 Metodologia para Resolução de um Problema de PL .......................... 14 
3.4 Exemplos de Problemas de Programação Linear ................................ 15 
3.5 Primeira Lista de Exercícios – Modelagem Matemática ...................... 18 
3.6 Resolução pelo Método Gráfico........................................................... 24 
3.7 Segunda Lista de Exercícios – Resolução pelo Método Gráfico ......... 26 
3.8 Problema Geral de Programação Linear ............................................. 28 
3.9 Problema de Programação Linear na Forma Padrão .......................... 29 
 
4 O MÉTODO SIMPLEX ......................................................................................... 30 
4.1 Teoremas Fundamentais ..................................................................... 30 
4.2 Soluções de um Problema de Programação Linear ............................ 30 
4.3 Passos do Método Simplex ................................................................. 33 
4.4 Análise Econômica do Problema de Programação Linear ................... 37 
4.5 Casos Especiais .................................................................................. 40 
4.6 Problemas de Minimização .................................................................. 41 
4.7 Obtenção da Solução Inicial ................................................................ 44 
4.8 Maximização com Restrições do Tipo Maior ou Igual ( ≥ ) .................. 45 
4.9 Restrição do Tipo Igual ( = ) ................................................................ 52 
4.10 O Problema da Variável Livre ou Variável Não Negativa .................... 53 
4.11 Terceira Lista de Exercícios – Método Simplex ................................... 55 
 
5 DUALIDADE .......................................................................................................... 59 
5.1 Teorema Básico da Dualidade ............................................................ 63 
5.2 Problemas PRIMAL e DUAL na Forma Canônica ............................... 64 
5.3 Interpretação Econômica do DUAL ..................................................... 68 
5.4 Quarta Lista de Exercícios – Dualidade ............................................... 74 
 
4 
 
6 MODELOS ESPECIAIS – O Problema do Transporte ................................... 77 
6.1 Oferta Igual a Demanda ...................................................................... 78 
6.2 Oferta Maior que a Demanda .............................................................. 80 
6.3 Oferta Menor que a Demanda ............................................................. 82 
6.4 Quinta Lista de Exercícios – Problema do Transporte ......................... 84 
 
7 Trabalho.................................................................................................................. 85 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5 
 
1 PESQUISA OPERACIONAL 
1.1 Introdução 
A pesquisa operacional surgiu durante a Segunda Guerra Mundial, resultado de estudos realizados 
por equipes interdisciplinares de cientistas contratados para resolver problemas militares de ordem 
estratégica e tática. 
A pesquisa operacional abrange um conjunto de técnicas com o objetivo de estudar e solucionar 
problemas envolvendo as seguintes áreas: 
 Teoria dos Jogos; 
 Teoria das Filas; 
 Processos Estocásticos; 
 Simulação; 
 PERT/CPM; 
 Teoria dos Grafos; 
 Programação Dinâmica; 
 Programação Não Linear; 
 Programação Linear. 
Em linhas gerais, a pesquisa operacional consiste na descrição de um sistema organizado com o 
auxílio de um método e através da experimentação com o modelo, na descoberta da melhor maneira 
de operar o sistema. 
Pesquisa operacional é um método científico de tomada de decisões. 
 
Tomada de Decisão 
Pode-se entender a tomada de decisão como o processo de identificar um problema ou uma 
oportunidade e selecionar uma linha de ação para resolvê-lo. Um problema ocorre quando o 
estado atual de uma situação é diferente do estado desejado. Uma oportunidade ocorre quando as 
circunstâncias oferecem a chance de o indivíduo/organização ultrapassar seus objetivos e/ou metas. 
Vários fatores afetam a tomada de decisão, tais como: 
 - Tempo disponível para a tomada de decisão; 
- A importância da decisão; 
- O ambiente; 
- Certeza/Incerteza e Risco; 
- Conflito de interesses. 
 
 
6 
 
Processo de Modelagem 
Quando os gerentes se veem diante de uma situação na qual uma decisão precisa ser tomada, entre 
uma série de alternativas conflitantes e concorrentes, duas opções básicas se apresentam: 
 1 – Usar a sua intuição gerencial para tomar a decisão; 
2 – Realizar um processo de modelagem da situação e realizar simulações dos diversos 
cenários de maneira a estudar mais profundamente o problema para tomar a melhor 
solução. 
Até recentemente, a primeira opção se constituía na única alternativa viável, visto que não existiam 
nem dados sobre os problemas e nem poder computacional para resolvê-los. 
Acredita-se que as duas opções devem ser utilizadas conjuntamente, para melhorar ainda mais o 
processo de tomada de decisão. 
 
A Tomada de Decisão, o Processo de Modelagem e o Decisor 
Diversas são as vantagens que podem ser citadas quando o decisor utiliza um processo de 
modelagem para a tomada de decisão: 
 Os modelos forçam os decisores a tornarem explícitos seus objetivos; 
 Os modelos forçam a identificação e o armazenamento das diferentes decisões que 
influenciam os objetivos; 
 Os modelos forçam a identificação e o armazenamento dos relacionamentos entre as 
decisões; 
 Os modelos forçam a identificação das variáveis do problema e suas quantificações; 
 Os modelos forçam o reconhecimento de limitações; 
 Os modelos permitem a comunicação de suas ideias e seu entendimento para facilitar 
o trabalho de grupo. 
Dadas essas características, os modelos podem ser utilizados como ferramentas consistentes para a 
avaliação e a divulgação de diferentes políticas nas empresas. 
 
O Processo de Resolução de um Problema 
O processo de resolução de um problema apresenta algumas etapas consecutivas que podem, 
entretanto, serem repetidas dependendo da situação. Cada uma das etapas é essencial para o 
processo. Contudo, a identificação do problema, que pode parecer a mais simples é a mais 
importante das etapas. 
A Figura 1 representa as etapas do processo de resolução de um problema. 
 
7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Identificação do 
Problema 
Formulação do 
ModeloAnálise dos 
Cenários 
Interpretação dos 
Resultados 
Implementação e 
Monitoramento 
Figura 1 – Processo de Resolução de um Problema 
 
8 
 
2 SISTEMA DE INEQUAÇÕES LINEARES 
Um sistema de inequações lineares é um sistema do tipo: 
 
 𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 
 𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 +⋯+ 𝑎2𝑛𝑥𝑛 ≤ 𝑏2 
 𝑎31𝑥1 + 𝑎32𝑥2 + 𝑎33𝑥3 +⋯+ 𝑎3𝑛𝑥𝑛 ≤ 𝑏3 
 .................................................................... 
 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + 𝑎𝑚3𝑥3 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 
 
Este sistema pode ser representado como: 
∑𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 (𝑖 = 1, 2, 3, ……𝑚)
𝑛
𝑗=1
 
 (𝑗 = 1, 2, 3, …… . 𝑛) 
Na forma matricial este sistema tem a seguinte forma: AX = B, onde: 
 - a matriz A é a matriz dos coeficientes; 
 - a matriz X é a matriz das variáveis do sistema; 
 - a matriz B é a matriz dos termos independentes do sistema. 
 
Para uma linha i qualquer do sistema tem-se a equação: 
 𝑎𝑖1𝑥1 + 𝑎𝑖2𝑥2 + 𝑎𝑖3𝑥3 +⋯+ 𝑎𝑖𝑛𝑥𝑛 ≤ 𝑏𝑖 ou seja 
∑𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 
𝑛
𝑗=1
 
Cada uma das inequações do sistema pode ser transformada numa equação da seguinte forma: 
a) Se a desigualdade for do tipo ≤ 
∑𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 é 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎 ∑𝑎𝑖𝑗𝑥𝑗 + 𝑥𝑛+𝑖 = 𝑏𝑖 𝑑𝑒𝑠𝑑𝑒 𝑞𝑢𝑒 𝑥𝑛+𝑖 ≥ 0
𝑛
𝑗=1
 
𝑛
𝑗=1
 
Nota: Neste caso a variável xn+i é conhecida como variável de folga da equação i. 
b) Se a desigualdade for do tipo ≥ 
∑𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 é 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎 ∑𝑎𝑖𝑗𝑥𝑗 − 𝑥𝑛+𝑖 = 𝑏𝑖 𝑑𝑒𝑠𝑑𝑒 𝑞𝑢𝑒 𝑥𝑛+𝑖 ≥ 0
𝑛
𝑗=1
 
𝑛
𝑗=1
 
Nota: A variável xn+i é conhecida como variável de excesso da equação i. 
 
9 
 
Exemplo 2.1: 
Seja o sistema: 
 𝑥1 + 3𝑥2 − 𝑥3 ≤ 4 𝑥1 + 3𝑥2 − 𝑥3 + 𝑥4 = 4 
 2𝑥1 − 4𝑥2 + 𝑥3 ≤ 6 este sistema equivale a 2𝑥1 − 4𝑥2 + 𝑥3 + 𝑥5 = 6 
 3𝑥1 + 3𝑥2 + 𝑥3 ≥ 7 3𝑥1 + 3𝑥2 + 𝑥3 − 𝑥6 = 7 
 
A variável 𝒙𝟒 é uma variável de folga da primeira equação do sistema; 
A variável 𝒙𝟓 é uma variável de folga da segunda equação do sistema; 
A variável 𝒙𝟔 é uma variável de folga da terceira equação do sistema. 
Desde que 𝑥4 ≥ 0; 𝑥5 ≥ 0; 𝑥6 ≥ 0, tem-se: 
As variáveis 𝒙𝟒; 𝒙𝟓; 𝒙𝟔 são variáveis básicas do sistema; 
As variáveis 𝒙𝟏; 𝒙𝟐; 𝒙𝟑 são variáveis não básicas do sistema. 
Observação: Não existem restrições de sinal nas variáveis 𝒙𝟏; 𝒙𝟐; 𝒙𝟑. 
 
2.1 Sistema de Inequações Lineares com Variáveis não Negativas 
Um sistema de inequações lineares com variáveis não negativas são sistemas onde algumas 
variáveis, ou todas as variáveis, têm restrições de sinal. 
Exemplo 2.2: 
Seja o sistema de inequações lineares: 
 𝑥1 + 2𝑥2 + 𝑥3 + 𝑥4 ≤ 8 
 3𝑥1 + 𝑥2 − 𝑥3 − 𝑥4 ≥ 12 
 4𝑥1 + 3𝑥2 + 3𝑥3 + 𝑥4 ≤ 10 onde x1 ≥ 0; x2 é 𝑞𝑢𝑎𝑙𝑞𝑢𝑒𝑟; x3 ≥ 0; x4 ≥ 0 
 
Deseja-se transformar o sistema de inequações lineares num sistema de equações lineares 
equivalente, que tenha todas as suas variáveis não negativas. 
Colocando as variáveis de folga em cada uma das equações, tem-se o seguinte sistema: 
 𝑥1 + 2𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 8 
 3𝑥1 + 𝑥2 − 𝑥3 − 𝑥4 − 𝑥6 = 12 
 4𝑥1 + 3𝑥2 + 3𝑥3 + 𝑥4 + 𝑥7 = 10 
 
Onde x1 ≥ 0; x2 é 𝑞𝑢𝑎𝑙𝑞𝑢𝑒𝑟; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0; x6 ≥ 0; x7 ≥ 0 
Resta resolver o problema da variável 𝒙𝟐 que continua sendo sem restrição de sinal. 
 
Observação: Qualquer número real pode ser obtido pela diferença de dois números positivos. 
10 
 
Logo, pode-se fazer a variável 𝒙𝟐 = 𝒙𝟐
′ − 𝒙𝟐
′′ onde 𝒙𝟐
′ ≥ 0 𝒆 𝒙𝟐
′′ ≥ 0, isto é, fazendo a variável 
𝒙𝟐 como a diferença entre dois números positivos. 
Desta forma, tem–se o seguinte sistema de equações lineares: 
 𝑥1 + 𝟐𝒙𝟐
′ − 𝟐𝒙𝟐
′′ + 𝑥3 + 𝑥4 + 𝑥5 = 8 
 3𝑥1 + 𝒙𝟐
′ − 𝒙𝟐
′′ − 𝑥3 − 𝑥4 − 𝑥6 = 12 
 4𝑥1 + 𝟑𝒙𝟐
′ − 𝟑𝒙𝟐
′′ + 3𝑥3 + 𝑥4 + 𝑥7 = 10 
Onde x1 ≥ 0; 𝑥2
′ ≥ 0; 𝑥2
′′ ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0; x6 ≥ 0; x7 ≥ 0 
Observe que todas as variáveis estão com restrição de sinal. 
Observação: Com a utilização de variáveis de folga e fazendo 𝒙𝒋 = 𝒙𝒋
′ − 𝒙𝒋
′′ (𝑥𝑗
′ ≥ 0; 𝑥𝑗
′′ ≥ 0) 
para todas as variáveis sem restrição de sinal, sempre é possível transformar qualquer 
sistema de inequações lineares num sistema de equações lineares equivalente, com 
todas as variáveis não negativas. 
Exercício: 
Converta o seguinte sistema de inequações lineares num sistema de equações lineares com variáveis 
não negativas. 
 
 6𝑥1 + 4𝑥2 − 3𝑥3 + 𝑥4 ≥ 2 
 -7𝑥1 − 5𝑥2 + 3𝑥3 − 2𝑥4 ≤ 5 
 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 10 
 𝑥2 ≤ −1 onde x1 ≥ 0; e x3 ≥ 0; 
 
2.2 Sistema de Equações Lineares na Forma Canônica 
Seja o sistema de inequações lineares: 
 𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 
 𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 +⋯+ 𝑎2𝑛𝑥𝑛 ≤ 𝑏2 
 𝑎31𝑥1 + 𝑎32𝑥2 + 𝑎33𝑥3 +⋯+ 𝑎3𝑛𝑥𝑛 ≤ 𝑏3 
 .................................................................... 
 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + 𝑎𝑚3𝑥3 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 
 
Com o emprego das variáveis de folga sempre é possível transformar o sistema de inequações 
lineares num sistema de equações lineares. 
Diz-se que um sistema de equações lineares está na forma canônica quando apresenta as seguintes 
características: 
 
 
11 
 
a) Todas as variáveis 𝒙𝒊 são não negativas; 
b) Todos os termos independentes 𝒃𝒊 são não negativos; 
c) Tem uma solução básica. 
Exemplo 2.3: 
 𝑥1 + 3𝑥2 − 𝑥3 ≤ 4 
 2𝑥1 − 4𝑥2 + 𝑥3 ≤ 6 
 3𝑥1 + 3𝑥2 + 𝑥3 ≤ 7 
 
Com a colocação das variáveis de folga 𝒙𝟒; 𝒙𝟓; 𝒙𝟔 o sistema de inequações lineares pode ser 
transformado numa sistema equações lineares da seguinte forma: 
 𝑥1 + 3𝑥2 − 𝑥3 ≤ 4 𝑥1 + 3𝑥2 − 𝑥3 + 𝑥4 = 4 
 2𝑥1 − 4𝑥2 + 𝑥3 ≤ 6 este sistema equivale a 2𝑥1 − 4𝑥2 + 𝑥3 + 𝑥5 = 6 
 3𝑥1 + 3𝑥2 + 𝑥3 ≤ 7 3𝑥1 + 3𝑥2 + 𝑥3 + 𝑥6 = 7 
 
Uma solução básica do sistema de equações pode ser obtida da seguinte forma: 
Variáveis não básicas { 
 𝑥1 = 0
 𝑥2 = 0
𝑥3 = 0
 
Com isso as variáveis básicas do sistema têm como solução: 
 Variáveis básicas { 
 𝑥4 = 4
 𝑥5 = 6
𝑥6 = 7
 
Observe que todas as variáveis 𝒙𝒊 são não negativas; 
 
Exercício: Transforme o sistema de inequações lineares num sistema de equações lineares na forma 
canônica e ache uma solução básica para o sistema. 
 𝑥1 + 𝑥2 − 𝑥3 ≤ 4 
 3𝑥1 − 5𝑥2 + 2𝑥3 ≤ 6 
 3𝑥1 + 𝑥2 + 4𝑥3 ≥ −5 
 
2.3 Conjuntos Convexos 
Um conjunto A é convexo se para quaisquer 2 pontos 𝑥1 𝑒 𝑥2 de A, todos os pontos da forma 
𝜆𝑥1 + (1 − 𝜆)𝑥2 pertencem ao conjunto A, para 0 ≤ λ ≤ 1. Ou seja, quaisquer 2 pontos do 
conjunto A pode ser ligado por uma reta totalmente contida no conjunto A. 
Em resumo, um conjunto A éum conjunto convexo se para quaisquer dois pontos 𝑥1 e 𝑥2 do 
conjunto podem ser ligados por uma reta totalmente contida no conjunto. 
12 
 
Exemplo 2.4: 
 
 
 
 
 
 
Ponto Extremo de um Conjunto Convexo 
Seja C um conjunto convexo. Um ponto x é um ponto extremo do conjunto C se x estiver situado na 
borda do conjunto C. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Convexo Não Convexo Não Convexo Convexo 
13 
 
3 PROGRAMAÇÃO LINEAR 
3.1 Conceitos e Definições 
A programação Linear – PL é uma das técnicas da Pesquisa Operacional. A programação linear é 
uma técnica de planejamento que se originou no final da década de quarenta e, com o surgimento 
do computador, na década de cinquenta, encontrou o seu aliado natural, tendo então, um 
desenvolvimento acelerado e sendo também muito difundida e utilizada. 
Os problemas que a programação linear resolve referem-se a distribuição eficiente de recursos 
limitados entre atividades competitivas, com a finalidade de atender a um determinado objetivo, por 
exemplo maximizar lucros ou minimizar custos. O objetivo do problema será expresso por uma 
função linear a qual se dá o nome de Função Objetivo. 
O problema de programação linear deve dizer quais são as atividades que consomem cada recurso 
disponível e em que proporção é feita esse consumo. Essas informações serão fornecidas por 
equações ou inequações lineares, uma para cada recurso disponível. Ao conjunto dessas equações 
ou inequações lineares dá-se o nome de Restrições do Modelo. 
Geralmente existem inúmeras maneiras de distribuir os escassos recursos entre as diversas 
atividades, bastando para isso que essas distribuições sejam coerentes com as equações de consumo 
de cada recurso, ou seja, que elas satisfaçam as restrições do problema. Entretanto, deseja-se achar a 
distribuição de recursos que satisfaça as restrições do problema, e que alcance o objetivo desejado, 
isto é, que Maximize o Lucro ou Minimize o Custo. A essa solução dá-se o nome de Solução 
Ótima. 
Uma vez obtido o Modelo Linear, constituído pela Função Objetivo e pelas Restrições Lineares, 
a programação linear se incumbe de achar a sua Solução Ótima. Se o problema a ser resolvido tiver 
apenas duas atividades então a solução pode ser obtida pelo Método Gráfico. Se o problema tiver 
mais do que duas atividades, como acontece na maioria das vezes, só é possível achar a solução 
ótima com técnicas apropriadas. 
 
3.2 Áreas de Aplicação da Programação Linear 
A programação linear é uma técnica de planejamento que tem sido aplicada nas mais diversas áreas, 
tais como: 
 Alimentação – quais os alimentos que as pessoas (ou animais) devem utilizar, de modo que o 
custo seja mínimo e os mesmos possuam os nutrientes nas quantidades adequadas, e que também 
atendem a outros requisitos, tais como variedade entre refeições, aspecto, paladar, etc; 
 Rotas de Transporte – qual deve ser o roteiro de transporte de veículos de carga de modo que 
 entreguem toda a carga no menor tempo e no menor custo total; 
14 
 
 Manufatura – qual deve ser a composição de produtos a serem fabricados por uma empresa de 
modo que se atinja o lucro máximo, sendo respeitadas as limitações ou exigências do mercado 
comprador e a capacidade de produção da fábrica; 
 Siderurgia – quais minérios devem ser carregados no alto-forno de modo a se produzir, ao 
menor custo, uma liga de aço dentro de determinadas especializações de elementos químicos; 
 Petróleo – qual deve a mistura de petróleo a ser enviada para uma torre de craqueamento para 
produzir seus derivados (gasolina, óleo) a um custo mínimo? Os petróleos são de diversas 
procedências e possuem composições diferentes; 
 Agricultura – quais os alimentos que devem ser plantados de modo que o lucro seja máximo e 
sejam respeitadas as características do solo, do mercado comprador e dos equipamentos 
disponíveis; 
 Carteira de Investimentos – quais são as ações que deve compor uma carteira de 
 investimentos de modo que o lucro seja máximo e sejam respeitadas as previsões de 
 lucratividade e as restrições governamentais; 
 Mineração – em que sequencia deve-se lavrar blocos de minério abaixo do solo, dados a sua 
composição, o posicionamento e os custos de extração; 
 Localização Industrial – onde devem ser localizadas as fábricas e os depósitos de um novo 
empreendimento industrial de modo que os custos de entrega do produto aos varejistas sejam 
minimizados. 
 
3.3 Metodologia para Resolução de um Problema de PL 
Metodologia de Resolução 
Diante de um problema de programação linear, consideram-se as seguintes orientações para 
resolvê-lo: 
- Estabelece-se Função Objetivo do problema isto é, a função que se quer maximizar ou 
minimizar; 
- Transformam-se as restrições impostas pelo problema num sistemas de inequações lineares; 
- Se o problema tem apenas duas atividades, traça-se o gráfico da região correspondente às 
restrições, determinando as coordenadas dos vértices da região; 
- Calcula-se o valor da Função Objetivo em cada um dos vértices; 
- O maior desses valores é o Valor Máximo e o menor desses valores é o Valor Mínimo da 
função objetivo; 
- Volta-se ao problema e determina-se a sua Solução Ótima. 
 
15 
 
Nota: Se o problema tiver mais de duas atividades a ser produzida, utiliza-se a técnica apropriada 
para achar a Solução Ótima. 
 
3.4 Exemplos de Problemas de Programação Linear 
Exemplo 3.1 - O Problema da Confecção de Calças e Camisas 
Uma fabrica que confecciona calças e camisas dispõe de 9 homens/hora de trabalho num dia. Para 
fazer uma calça utiliza-se 1 homem/hora e para fazer uma camisa utiliza-se 2 homens/hora. O 
fabricante sabe que vende no máximo 3 calças e 4 camisas num dia. O lucro numa calça é de 
R$50,00 e numa camisa de R$20,00. Quantas calças e quantas camisas devem ser fabricadas por 
dia, para se obter lucro Máximo? 
 
Modelagem do problema: 
Restrições do mercado: 3 calças por dia 
 4 camisetas por dia 
Disponibilidade de mão de obra: Calça: 1 homem/hora 
 Camisa: 2 homens/hora 
Lucro nas vendas: Calça: R$ 50,00 
 Camisa: R$ 20,00 
Variáveis do problema: 𝑥1 - número de calças a serem fabricadas 
 𝑥2 - número de camisas a serem fabricadas 
Modelo matemático: 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 ------------------> Função Lucro ou Função objetiva 
 𝑥1 ≤ 3 50𝑥1: Lucro na fabricação de calças 
 𝑥2 ≤ 4 Restrições do problema 20𝑥2: Lucro na fabricação de camisas 
 𝑥1 + 2 𝑥2 ≤ 9 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
 
Obtido o Modelo Linear constituído pela Função Objetivo e pelas Restrições do Problema, a 
Programação Linear se incumbe de achar a solução ótima do problema. 
 
 
 
 
16 
 
Exemplo 3.2 – O Problema do Sapateiro 
Um sapateiro faz 6 sapatos por dia, se fizer somente sapatos, e 5 cintos por dia, se fizer somente 
cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade de couro para 
fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o 
lucro unitário por sapato é de R$ 50,00 e o do cinto é de R$ 20,00. 
 
Modelagem do problema: 
Restrições de produção: 6 sapatos/dia 
 5 cintos/dia 
Disponibilidade de couro: 6 unidades 
Utilização do couro: Sapato: 2 unidades de couro 
 Cinto: 1 unidade de couro 
Lucro nas vendas: Sapato: R$ 50,00 
 Cinto: R$ 20,00 
Variáveis do problema: 𝑥1 - quantidade de sapatos/dia 
 𝑥2 - quantidade de cintos/dia 
Modelo Matemático: 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 -----------------> Função objetiva 
 𝑥1 ≤ 6 
 𝑥2 ≤ 5 Restriçõesdo problema 
 2𝑥1 + 𝑥2 ≤ 6 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
 
Obtido o Modelo Linear constituído pela Função Objetivo e pelas Restrições do Problema, a 
Programação Linear se incumbe de achar a solução ótima do problema. 
 
Exemplo 3.3 - O Problemas do Vendedor de Frutas 
Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. O vendedor 
tem um pedido fixo de 200 caixas de laranjas a R$ 20,00 de lucro por caixa e pelo menos 100 
caixas de pêssegos a R$10,00 de lucro por caixa. Alem disso, o vendedor vende no máximo 200 
caixas de tangerinas a R$ 30,00 de lucro por caixa. De que forma deverá ele carregar o caminhão 
para obter o lucro máximo? Construa o modelo matemático. 
 
17 
 
Modelagem do problema: 
Restrições de consumo: 200 caixas de laranja (fixo) 
 100 caixas de pêssego (no mínimo) 
 200 caixas de tangerina (no máximo) 
Disponibilidade de transporte: 800 caixas 
Lucro por caixa: Laranja: R$ 20,00/caixa ----> R$ 4.000,00 
 Pêssego: R$ 10,00 
 Tangerina: R$ 30,00 
Variáveis do problema 𝑥1 quantidade de caixas de pêssegos 
 𝑥2 quantidade de caixas de tangerinas 
Modelo Matemático: 
𝑀𝑎𝑥 𝑍 = 10𝑥1 + 30𝑥2 + 4000 ----------------->Função objetiva 
 𝑥1 ≥ 100 
 𝑥2 ≤ 200 Restrições do problema 
 𝑥1 + 𝑥 2 ≤ 600 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
 
Obtido o Modelo Linear constituído pela Função Objetivo e pelas Restrições do Problema, a 
Programação Linear se incumbe de achar a solução ótima do problema. 
 
 
 
 
 
 
 
 
 
 
18 
 
3.5 Primeira Lista de Exercícios – Modelagem Matemática 
 
Construa o Modelo Matemático dos problemas seguintes. 
 
1 - Um desenhista faz quadros artesanais para vender em uma feira que acontece todas as noites. O 
desenhista faz desenhos grandes e pequenos e vende os quadros por R$ 50,00 e R$ 20,00 
respectivamente. O desenhista só consegue vender 4 desenhos grandes e 3 desenhos pequenos 
por noite. O desenho grande é feito em 1 hora (grosseiro) e o desenho pequeno é feito em 2 
horas (detalhado). Além disso, o desenhista desenha durante 8 horas por dia antes de ir para a 
feira. 
Construa o modelo matemático com o objetivo de maximizar o lucro do desenhista. 
 
2 - Uma empresa fabrica 2 produtos: P1 e P2. 
O lucro por unidade de P1 é de R$ 100,00 e o lucro por unidade de P2 é de R$ 150,00. A 
empresa necessita de 2 horas para fabricar uma unidade de P1 e de 3 horas para fabricar uma 
unidade de P2. O tempo mensal disponível para estas atividades é de 120 horas. As demandas 
esperadas indicam que a fabricação de P1 não deve ultrapassar 40 unidades e P2 não deve 
ultrapassar 30 unidades por mês. 
Construa o modelo de fabricação com o objetivo de maximizar o lucro da empresa. 
 
3 – Um fabricante de móveis dispõe de 6 placas de madeira que poderá utilizar para fabricar 
biombos decorativos. O fabricante dispõe de 28 horas disponíveis para fabricar os biombos de 
modelos B1 e B2. O modelo B1 requer 2 placas de madeira e 7 horas de mão de obra, enquanto 
que o modelo B2 requer 1 placa de madeira e 8 horas de mão de obra. O modelo B1 está sendo 
vendido a R$ 120,00 e o modelo B2 está sendo vendido a R$ 80,00. Quantos biombos de cada 
modelo deverão ser fabricados para se obter uma receita máxima? 
 
4 – Uma pequena firma de manufatura produz os produtos A, B C e D. Cada unidade de cada 
produto precisa passar pela linha de produção, pelo polimento e pela montagem. Na tabela 1 
indicam-se os tempos (em horas) necessários à fabricação de uma unidade de cada um dos tipos 
de produtos. 
 A firma dispõe semanalmente um máximo de 480 horas de funcionamento da linha de 
produção, 400 horas do setor de polimento e 400 horas do setor de montagem. Os lucros 
unitários associados aos quatro tipos de produtos estão indicados na tabela 2. A firma se 
comprometeu com um cliente de fornecer semanalmente 50 unidades do produto A e 100 
unidades de qualquer combinação entre os produtos B e C. 
 A firma pode vender semanalmente qualquer quantia dos produtos A; B e C, mas só pode 
vender no máximo 25 unidades do produto D. Quantas unidades de cada produto deverão ser 
produzidas semanalmente, de modo a garantir o cumprimento dos compromissos assumidos e a 
maximizar o lucro total? 
 
Tabela 1 
Produtos Horas de Produção Horas de Polimento Horas de Montagem 
A 
B 
C 
D 
3 
2 
2 
4 
1 
1 
2 
3 
2 
1 
2 
1 
 
 
 
19 
 
Tabela 2 
Produtos Lucro unitário em Reais 
A 
B 
C 
D 
6 
4 
6 
8 
 
5 – Uma determinada empresa está interessada em maximizar o lucro mensal proveniente de quatro 
produtos P1, P2, P3 e P4. Para fabricar esses quatro produtos, a empresa utiliza dois tipos de 
máquinas M1 e M2 e dois tipos de mão de obra MO1 e MO2. A tabela 1 abaixo indica a 
disponibilidade das máquinas. A tabela 2 indica a disponibilidade de mão de obra. A tabela 3 
indica o número de máquina-hora necessário para se produzir uma unidade de cada produto. A 
tabela 4 indica o número de homem-hora necessário para se produzir uma unidade de cada 
produto. A tabela 5 contém informações do setor comercial sobre o potencial de vendas dos 
produtos e o lucro unitário de cada produto. 
 
Tabela 1 
Máquinas Tempo Disponível 
(máquina-hora / mês) 
M1 
M2 
80 
20 
 
Tabela 2 
Mão de Obra Tempo Disponível 
(homem-hora / mês) 
MO1 
MO2 
120 
160 
 
Tabela 3 
Máquinas P R O D U T O S 
P1 P2 P3 P4 
M1 
M2 
5 
2 
4 
6 
8 
- 
9 
8 
 
Tabela 4 
Mão de Obra P R O D U T O S 
P1 P2 P3 P4 
MO1 
MO2 
2 
7 
4 
3 
2 
- 
8 
7 
 
Tabela 5 
Produtos Potencial de Vendas 
(Unidade / mês) 
Lucro Unitário 
Em Reais 
P1 
P2 
P3 
P4 
70 
60 
40 
20 
10,00 
8,00 
9,00 
7,00 
 
 
 
 
 
 
 
 
 
20 
 
6 - Uma metalúrgica deseja maximizar sua receita bruta. A tabela abaixo ilustra a proporção de cada 
material na mistura para a obtenção das ligas passíveis de fabricação. O preço está cotado em 
Reais por tonelada da liga fabricada. Também em toneladas estão expressas as restrições de 
disponibilidade de matéria-prima. Formular o modelo de Programação Matemática. 
 
 Liga de Baixa 
 Resistência 
Liga de Alta 
 Resistência 
Disponibilidade de 
 Matéria Prima - Toneladas 
Cobre 
Zinco 
Chumbo 
0,50 
0,25 
0,25 
0,20 
0,30 
0,50 
16 
11 
15 
Preço de Venda 
 por Tonelada 
R$ 3.000,00 R$ 5.000,00 
 
7 - Uma grande fábrica de móveis dispõe em estoque de 250 metros de tábuas, 600 metros de 
pranchas e 500 metros de painéis de conglomerado. A fábrica normalmente oferece uma linha 
de móveis composta por um modelo de escrivaninha, uma mesa de reunião, um armário e uma 
prateleira. Cada tipo de móvel consome certa quantidade de matéria prima, conforme a tabela 
abaixo. A escrivaninha é vendida por R$ 100,00; a mesa por R$ 80,00; o armário por R$ 
120,00; e a prateleira por R$ 20,00. Construa um modelo de Programação Linear que maximize 
a receita com a venda dos móveis. 
 
 Quantidade de Material Gasto por Produto 
 
Escrivaninha 
 
Mesa 
 
Armário 
 
Prateleira 
Disponibilidade de 
Recurso – metros 
Tábua 
Prancha 
Painéis 
1 
0 
3 
1 
1 
2 
1 
1 
4 
4 
2 
0 
250 
600 
500 
Valor de 
Venda em 
Reais 
 
100 
 
80 
 
120 
 
20 
 
 
8 - Considere a situação de decidir sobre o número de unidades a serem produzidas por certo 
fabricante de dois diferentes tipos de produto. Os lucros por unidade do produto 1 e do produto 
2 são, respectivamente, R$ 2,00 e R$ 5,00. Cada unidade do produto 1 requer 3 horas de 
máquina e 9 unidades de matéria-prima, enquanto o produto 2 requer 4 horas de máquina e 7 
unidadesde matéria-prima. Os tempos máximos disponíveis de horas de máquina e de matéria-
prima são 200 horas e 300 unidades, respectivamente. Formule o problema de forma a 
maximizar o lucro total. 
 
 
9 - Uma fábrica produz bolas de couro e de plástico. A bola de couro necessita de 5 homens/hora 
para a confecção e tem um lucro unitário de $20. A bola de plástico necessita de 2 homens/hora 
e seu lucro unitário é de $15. Há disponibilidade de 100 homens/hora por dia nesta fábrica. Um 
problema com fornecedores limitou o estoque de couro e plástico, de modo que é possível 
confeccionar no máximo 15 bolas de couro e 30 bolas de plástico. Considerando que este é um 
problema de maximização de lucros com 2 variáveis de decisão, assinale a alternativa que 
melhor representa o modelo do problema de modo a encontrar a produção ótima do fabricante. 
 
 
 
 
 
 
 
 
21 
 
10 - Uma firma produz mesas e cadeiras. Os lucros unitários são respectivamente $20 e $24. Cada 
mesa requer 3 homens/hora na montagem e 4 homens/hora no acabamento. Cada cadeira 
precisa de 6 homens/ hora na montagem e 2 homens/hora no acabamento. O departamento de 
montagem tem capacidade de 60 homens/hora e o de acabamento 32 homens/hora por semana. 
Modele o problema visando o lucro máximo. 
Considerando que este é um problema de maximização de lucros com 2 variáveis de decisão, 
assinale a alternativa que melhor representa o modelo do problema de modo a encontrar a 
produção ótima do fabricante. 
 
11 - Um fazendeiro dispõe de 400 alqueires cultiváveis com milho, trigo ou soja. Cada alqueire de 
milho necessita de $2000, para preparação do terreno, 20 homens/dia de trabalho e gera um 
lucro de $600. Cada alqueire de trigo envolve custos de $2400, 30 homens/dia e lucro de $800. 
Cada alqueire de soja exige $1400, 24 homens/dia e lucro $400. O fazendeiro dispõe de 
$900.000 para gastos com a preparação do terreno e de 100 homens/dia para o trabalho. 
Modele o problema de forma a encontrar a melhor alocação de terras para o fazendeiro. 
Considerando que este é um problema de maximização de lucros com 3 variáveis de decisão, 
assinale a alternativa que melhor representa o modelo do problema de modo a encontrar a 
produção ótima do fazendeiro. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
22 
 
Respostas dos Exercícios 
 
1 – x1 : Quantidade de desenhos grande 
 x2 : Quantidade de desenhos pequenos 
 Max Lucro = 50x1 + 20x2 
 x1 ≤ 4 
 x2 ≤ 3 
 x1 + 2x2 ≤ 8 
 x1  0 
 x2  0 
 
2 – x1 : Quantidade do produto P1 
 x2 : Quantidade do produto P2 
 Max Lucro = 100x1 + 150x2 
 x1 ≤ 40 
 x2 ≤ 30 
 2x1 + 3x2 ≤ 120 
 x1  0 
 x2  0 
 
3 – x1 : Quantidade de Biombos do modelo B1 
 x2 : Quantidade de Biombos do modelo B2 
 Max Lucro = 120x1 + 80x2 
 2x1 + x2 ≤ 6 
 7x1 + 8x2 ≤ 28 
 x1  0 
 x2  0 
 
4 – x1 : Quantidade do produto A 
 x2 : Quantidade do produto B 
x3 : Quantidade do produto C 
 x4 : Quantidade do produto D 
 Max Z = 6x1 + 4x2 + 6x3 + 8x4 
 3x1 + 2x2 + 2x3 + 4x4 ≤ 480 
 x1 + x2 + 2x3 + 3x4 ≤ 400 
 2x1 + x2 + 2x3 + x4 ≤ 400 
 x1  50 
 x2 + x3  100 
 x4 ≤ 25 
 x1  0; x2  0; x3  0; x4  0 
 
5 – x1 : Quantidade do produto P1 
 x2 : Quantidade do produto P2 
x3 : Quantidade do produto P3 
 x4 : Quantidade do produto P4 
 Max Z = 10x1 + 8x2 + 9x3 + 7x4 
 5x1 + 4x2 + 8x3 + 9x4 ≤ 80 
 2x1 + 6x2 + 8x4 ≤ 20 
 2x1 + 4x2 + 2x3 + 8x4 ≤ 120 
 7x1 + 3x2 + 7x4 ≤ 160 
 x1 ≤ 70 
 x2 ≤ 60 
 x3 ≤ 40 
 x4 ≤ 20 
x1  0 
 x2  0 
 x3  0 
 x4  0 
 
 
 
 
 
 
 
 
 
 
6 - x1: Quantidade da liga de baixa 
resistência 
 x2: Quantidade da liga de alta resistência 
 Max Z = 3.000x1 + 5.000x2 
 0,5x1 + 0,2x2 ≤ 16 
 0,25x1 + 0,3x2 ≤ 11 
 0,25x1 + 0,5x2 ≤ 15 
 x1  0 
 x2  
0 
 
23 
 
7 – x1 : Quantidade de Escrivaninha 
 x2 : Quantidade de Mesa 
x3 : Quantidade de Armário 
 x4 : Quantidade de Prateleira 
 Max Z = 100x1 + 80x2 + 120x3 + 20x4 
 x1 + x2 + x3 + 4x4 ≤ 250 
 x2 + x3 + 2x4 ≤ 600 
 3x1 + 2x2 + 4x3 + ≤ 400 
 x1  0 
 x2  0 
 x3  0 
 x4  0 
 
8 – x1 : Quantidade do produto 1 
 x2 : Quantidade do produto 2 
 Max Lucro Z = 2x1 + 5x2 
 3x1 + 4x2 ≤ 200 
 9x1 + 7x2 ≤ 300 
 x1  0 
 x2  0 
 
 
9 - x1 = quantidade de bolas de couro 
x2 = quantidade de bolas de plástico 
 Max Z = 20x1+15x2 
 5x1+ 2x2  100(mão de obra) 
 x1  15 (mat. prima – couro) 
 x2  30 (mat. prima – 
plástico) 
 x1  0; x2  0 
 
 
 10 - x1 = quantidade de mesas 
 x2 = quantidade de cadeiras 
 Max Z = 20x1+ 24x2 
 3x1+ 6x2  60
 (montagem) 
4x1+ 2x2  32
 (acabamento) 
 x1  0; x2  0 
 
11 - x1 = quantidade alqueires de milho 
x2 = quantidade alqueires de trigo 
x3 = quantidade alqueires de soja 
Max L = 600x1+ 800x2 + 400x3 
 (investimento) 2000x1+ 2400x2 + 1400x3  
900000 
 (mão de obra) 20x1+ 30x2 + 24x3  100 
 (terra) x1+ x2 + x3  400) 
 x1  0; x2  0; x3  0 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
24 
 
3.6 Resolução pelo Método Gráfico 
Quando o problema de programação linear constar de apenas duas atividade, por exemplo a 
produção de dois produtos, então a solução ótima pode ser obtida pelo método gráfico. 
 
Passos para a Solução Gráfica: 
Passo 1 - Num sistema de coordenadas, desenhe a região variável num sistema de coordenadas que 
 depende exclusivamente das inequações das restrições; 
Passo 2 - Descubra os pontos fronteiras da região variável; 
Passo 3 - Teste o valor da função objetiva em cada um dos pontos fronteiras da região viável; 
Passo 4 - O ponto que resultar no maior valor da função objetiva será o resultado do problema 
 (caso de maximização); 
Passo 5 - O ponto que resultar no menor valor da função objetiva será o resultado do problema 
 (caso de minimização). 
 
Exemplo 3.4: 
Seja o modelo matemático da confecção de calças e camisas. 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 ------------------> Função objetiva 
 𝑥1 ≤ 3 
 𝑥2 ≤ 4 Restrições do problema 
 𝑥1 + 2 𝑥2 ≤9 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
Passo 1 - Num sistema de coordenadas, desenhe a região variável num sistema de coordenadas que 
depende exclusivamente das inequações das restrições; 
 
 
 
 
 
 
 
 
 
 
F 
( calças) 
E(0,4) D(1,4) 
C(3,3) 
B(3,0) 
A(0,0) 
x2 
3 2 1 
1 
2 
3 
4 
x1 
Região Viável 
( camisas) x1 = 3 
x2 = 4 
x1 + 2x2 = 9 
x1 = 0 
x2 = 0 
25 
 
𝑥1 + 2𝑥2 = 9 
P/ 𝑥1 = 3 → 𝑥2 = 3 
P/ 𝑥2 = 4 → 𝑥1 = 1 
Para saber que lado da equação deve ser considerado, substituir 2 pontos quaisquer na inequação e 
ver se satisfaz a desigualdade da inequação: 
𝑥1 = 0 ; 𝑥2 = 0 → 0 + 2.0 = 0 ≤ 9 → 𝑠𝑎𝑡𝑖𝑠𝑓𝑎𝑧 𝑎 𝑑𝑒𝑠𝑖𝑔𝑢𝑎𝑙𝑑𝑎𝑑𝑒 → 𝐿𝑎𝑑𝑜 𝑑𝑒 𝑏𝑎𝑖𝑥𝑜 
Passo 2 - Descubra os pontos fronteiras da região variável; 
 A (0,0) ; B (3,0) ; C (3,3) ; D (1,4) ; E(0,4) ; G(3,4) 
Passo 3 - Teste o valor da função objetiva em cada um dos pontos fronteiras da região viável; 
 Ponto: A (0,0) ==> Z = 0 
 Ponto: B (3,0) ==> Z = 150 
 Ponto: C (3,3) ==> Z = 210 ===> Solução Ótima 𝑥1 = 3 𝑒 𝑥2 = 3 
 Ponto: D (1,4) ==> Z = 130 
 Ponto: E(0,4) ==> Z = 80 
 Ponto: G(3,4) ==> Z = 280 Mas o ponto G está fora da região viável 
Passo 4 - O ponto que resultar no maior valor da função objetiva será o resultado do problema. 
 Solução Ótima ==> fabricar 3 calças e 3 camisas obtendo um lucro de Z=210. 
 
Exercício 1: 
Resolva pelo Método Gráfico o problema do sapateiro. 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 =======> Função objetiva 
 𝑥1 ≤ 6 
 𝑥2 ≤ 5 Restrições do problema 
 2𝑥1 + 𝑥2 ≤ 6 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
Exercício 2: 
Resolva pelo Método Gráfico o problema do vendedor de frutas. 
𝑀𝑎𝑥 𝑍 = 10𝑥1 + 30𝑥2 + 4000 ========>Função objetiva 
 𝑥1 ≥ 100 
 𝑥2 ≤ 200 Restrições do problema 
 𝑥1 + 𝑥 2 ≤ 600 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
26 
 
3.7 Segunda Lista de Exercícios – Resolução pelo Método Gráfico 
Resolva pelo Método Gráfico os seguintes problemas de programação linear: 
 
1 - Um desenhista faz quadros artesanais para vender em uma feira que acontece todas as noites. O 
desenhista faz desenhos grandes e pequenos e vende os quadros por R$ 50,00 e R$ 20,00 
respectivamente. O desenhista só consegue vender 4 desenhos grandes e 3 desenhos pequenos 
por noite. O desenho grande é feito em 1 hora (grosseiro) e o desenho pequeno é feito em 2 
horas (detalhado). Além disso, o desenhista desenha durante 8 horas por dia antes de ir para a 
feira. Como o desenhista deve proceder para obter o maior lucro. 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
2 - Uma empresa fabrica 2 produtos: P1 e P2. 
O lucro por unidade de P1 é de R$ 100,00 e o lucro por unidade de P2 é de R$ 150,00. A 
empresa necessita de 2 horas para fabricar uma unidade de P1 e de 3 horas para fabricar uma 
unidade de P2. O tempo mensal disponível para estas atividades é de 120 horas. As demandas 
esperadas indicam que a fabricação de P1 não deve ultrapassar 40 unidades e P2 não deve 
ultrapassar 30 unidades por mês. 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
 3 - Considerem o seguinte o problema de LP 
 
 
 
 
 
 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Se a função objetivo fosse alterada para 2x1+6x2, qual seria a solução ótima? 
c) Quantos pontos extremos existem? 
 
4 - Encontre a solução ótima do seguinte o problema de programação linear. 
Existe sobra de recursos na solução ótima? 
 
 𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2 
 4𝑥1 + 6𝑥2 ≤ 60 
 𝑥1 + 𝑥2 ≥ 12 
 𝑥1 ≥ 0 
 𝑥2 ≥ 0 
 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
 
 
 
0, 
2446 
1242 
33 Z
21
21
21
21




xx
xx
xx
xxMax
Resposta: 
{
𝑥1 = 3
 𝑥2 = 1,5
 Z = 13,5 
Resposta: 
{
𝑥1 = 15
 𝑥2 = 0 
 Z = 30 
27 
 
5 – Encontre a solução ótima do seguinte problema de programação linear. 
 Existe sobra de recursos na solução ótima? 
 Max Z = 2x1 + 3x2 
 - x1 + 2x2 ≤ 4 
 x1 + 2x2 ≤ 6 
 x1 + 3x2 ≤ 9 
 x1  0 
 x2  0 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
6 – Encontre a solução ótima do seguinte problema de programação linear. 
 Existe sobra de recursos na solução ótima? 
 Max Z = 2x1 + 3x2 
 x1 + 3x2 ≤ 9 
 - x1 + 2x2 ≤ 4 
 x1 + x2 ≤ 6 
 x1  0 
 x2  0 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
7 – Encontre a solução ótima do seguinte problema de programação linear. 
 Existe sobra de recursos na solução ótima? 
 Min Z = 10x1 + 12x2 
 x1 + x2 ≤ 20 
 x1 + x2  10 
 5x1 + 6x2  54 
 x1  0 
 x2  0 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
8 – Encontre a solução ótima do seguinte problema de programação linear. 
 Existe sobra de recursos na solução ótima? 
 Minimizar o Custo Z = 7x1 + 9x2 
 - x1 + x2 ≤ 2 
 x1 ≤ 5 
 x2 ≤ 6 
 3x1 + 5x2  15 
 5x1 + 4x2  20 
 x1  0 
 x2  0 
a) Resolva graficamente o problema e encontre a solução ótima. 
b) Verifique se existe alguma sobra de recursos na solução ótima. 
c) Identifique uma solução não viável do problema e explique porque é não viável. 
 
Resposta: 
{
𝑥1 = 6
 𝑥2 = 0
 Z = 12 
Resposta: 
{
𝑥1 = 4,5
 𝑥2 = 1,5
 Z = 13,5 
Resposta: 
{
𝑥1 = 6
 𝑥2 = 4
 Z = 108 
Resposta: 
{
𝑥1 = 5
 𝑥2 = 6
 Z = 89 
28 
 
3.8 Problema Geral de Programação Linear 
De uma maneira geral, um problema de programação linear – PPL consiste em achar os valores das 
variáveis 𝑥1; 𝑥2; 𝑥3; … ; 𝑥𝑛 que maximize a função objetivo 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 +𝑐3𝑥3 + …+ 𝑐𝑛𝑥𝑛 
sabendo-se que as variáveis 𝑥1; 𝑥2; 𝑥3; … ; 𝑥𝑛 devem satisfazer um sistema de inequações lineares 
da seguinte forma: 
𝑀𝑎𝑥 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + 𝑐3𝑥3 + …+ 𝑐𝑛𝑥𝑛 
 𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 
 𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 +⋯+ 𝑎2𝑛𝑥𝑛 ≤ 𝑏2 Modelo A 
 𝑎31𝑥1 + 𝑎32𝑥2 + 𝑎33𝑥3 +⋯+ 𝑎3𝑛𝑥𝑛 ≤ 𝑏3 
 .................................................................... 
 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + 𝑎𝑚3𝑥3 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 
 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0;…… . . ; 𝑥𝑛 ≥ 0 
Na forma compacta tem-se: 
 𝑀𝑎𝑥 𝑍 = ∑ 𝑐𝑗𝑥𝑗
𝑛
𝑗=1 sujeito às restrições 
 ∑ 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 (𝑖 = 1, 2, 3, ……𝑚)
𝑛
𝑗=1 
 𝑥𝑗 ≥ 0 (𝑗 = 1, 2, 3, …… . 𝑛) 
O modelo acima está associado a uma empresa que tem m recursos disponíveis para a realização de 
n atividades (fabricação de produtos, por exemplo). 
 
Tem-se então, para j = 1, 2, 3, ....n e para i = 1, 2, 3, .... m: 
𝒃𝒊: quantidade do recurso i disponível para as n atividades (bi ≥ 0). 
𝒙𝒋: nível de produção da atividade j. São as variáveis do problema. 
𝒄𝒋 :lucro unitário obtido na produção da atividade j. 
𝒂𝒊𝒋: quantidade do recurso i consumida na produção de uma unidade da atividade j. 
As m restrições do Modelo A informam que o total do recurso i gasto nas n atividades tem que ser 
menor ou no máximo igual à quantidade bi disponível daquele recurso. 
As restrições 𝑥𝑗 ≥ 0 ( j = 1, 2, 3, ....n) eliminam a possibilidade de resultados negativos. 
Observa-se que a Função Lucro Z a ser maximizada representa o lucro total da empresa na 
produção das n atividades (produtos). 
 
29 
 
3.9 Problema de Programação Linear na Forma Padrão 
Um problema de programação linear está Forma Padrão quando apresenta as seguintes 
características: 
a) A função objetivo é de maximização; 
b) As restrições são todas com sinal de menor ou igual ( ≤ ); 
c) As constantes de todas as restrições são não negativas (𝑏𝑖 ≥ 0); 
d) As variáveis são todas não negativas (𝑥𝑗 ≥ 0). 
 
Problema na Forma Padrão: 
 
𝑀𝑎𝑥 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + 𝑐3𝑥3 + …+ 𝑐𝑛𝑥𝑛 
 𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 
 𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 +⋯+ 𝑎2𝑛𝑥𝑛 ≤ 𝑏2 
 𝑎31𝑥1 + 𝑎32𝑥2 + 𝑎33𝑥3 +⋯+ 𝑎3𝑛𝑥𝑛 ≤ 𝑏3 
 .................................................................... 
 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + 𝑎𝑚3𝑥3 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 
 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0;…… . . ; 𝑥𝑛 ≥ 0 
 
Exemplo 3.5: 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 
 𝑥1 ≤ 6 
 𝑥2 ≤ 5 Problema na Forma Padrão 
 2𝑥1 + 𝑥2 ≤ 6 
 𝑥1 ≥ 0 
 𝑥2 ≥ 0 
 
Qualquer problema de programação linear pode ser transformado num problema de programação 
linear na Forma Padrão. 
 
 
 
 
 
 
30 
 
4 O MÉTODO SIMPLEX 
4.1 Teoremas Fundamentais 
Teorema 1: O conjunto de todas as soluções compatíveis do modelo de programação linear é um 
conjunto convexo. 
Teorema 2: Toda solução compatível básica do sistema de equações lineares AX = B, é um ponto 
extremo do conjunto das soluções compatíveis, isto é um ponto extremo do conjunto 
convexo tratado no teorema 1. 
Teorema 3: 
a) Se a função objetivo possui um valor máximo (ou valor mínimo) finito, então pelo 
menos uma solução ótima é um ponto extremo do conjunto convexo do teorema 1. 
b) Se a função objetivo assume o valor máximo (ou o valor mínimo) em dois pontos 
extremos do conjunto convexo, então ela assume o mesmo valor para qualquer ponto 
situado na reta formada por esses dois pontos. 
 
4.2 Soluções de um Problema de Programação Linear 
A solução de um Problema de Programação Linear pode ser considerada como: 
- Solução Viável: é uma solução em que todas as restrições do problema são satisfeitas, é uma 
solução que encontra dentro da região viável; 
- Solução Inviável: é uma solução em que pelo menos uma das restrições do problema não é 
satisfeita, é uma solução que está fora da região viável. 
- Solução Ótima: é uma solução viável que maximiza a Função Objetivo, isto é, é uma solução 
que está na fronteira da região viável e que traz o maior valor para a função 
objetivo.. 
Exemplo 4.1: 
Seja o problema de programação linear referente à confecção de calças e camisas. 
Modelo Matemático: 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 =========> Função objetiva 
 𝑥1 ≤ 3 
 𝑥2 ≤ 4 Restrições do problema 
 𝑥1 + 2 𝑥2 ≤ 9 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
O problema está na Forma Padrão. 
 
31 
 
Graficamente tem-se a seguinte região viável 
 
 
 
 
 
 
 
 
 
 
x1 : representa o número de calças a serem fabricadas. 
x2 : representa o número de camisas a serem fabricadas. 
Colocando as variáveis de folga o problema passa para a Forma Canônica. 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 
 𝑥1 + 𝑥3 = 3 Forma Canônica 
 𝑥2 + 𝑥4 = 4 
 𝑥1 + 2𝑥2 + 𝑥5 = 9 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0 
 
 
 
O Método Simplex compreende as seguintes etapas: 
i. Achar uma solução compatível básica inicial, ou seja, achar uma forma canônica inicial para o 
sistema de equações; 
ii. Verificar se a solução atual é ótima. Se a solução for ótima, pare. Caso contrário siga para o 
passo iii; 
iii. Determinar a variável não básica que deve entrar na base; 
iv. Determinar a variável básica que deve sair da base; 
v. Achar a nova solução compatível básica e voltar ao passo ii. 
Observação: O problema na Forma Canônica já fornece uma base óbvia e portanto é uma solução 
básica inicial, equivalente ao ponto A(0,0) na solução gráfica. 
 Fazendo as variáveis não básicas 𝑥1 = 0 𝑒 𝑥2 = 0 obtém-se uma solução básica 
 inicial 𝑥3 = 3; 𝑥4 = 4 𝑒 𝑥5 = 9. 
 As variáveis não básicas sempre têm solução igual a zero. 
 
XB:Variáveis 
básicas 
XN:variáveis 
não básicas 
F 
( calças) 
E(0,4) D(1,4) 
C(3,3) 
B(3,0) 
A(0,0) 
x2 
3 2 1 
1 
2 
3 
4 
x1 
Região Viável 
( camisas) x1 = 3 
x2 =4 
x1 + 2x2 = 9 
x1 = 0 
x2 = 0 
32 
 
Análise no ponto A(0,0): 
variáveis do problema: {
𝑥1 = 0
𝑥2 = 0
 variáveis de folga: {
𝑥3 = 3
𝑥4 = 4
𝑥5 = 9
 Lucro: Z = 0 
Variáveis não básicas: 𝑥1; 𝑥2. Variáveis básicas: 𝑥3; 𝑥4; 𝑥5. 
Esta solução tem a seguinte interpretação: 
Se for fabricado zero calças e zero camisas, o lucro será zero e existirá folga em todos o recursos, 
porque não foram gastos. É uma solução básica viável. 
 
Análise no ponto B(3,0): 
variáveis do problema: {
𝑥1 = 3
𝑥2 = 0
 variáveis de folga: {
𝑥3 = 0
𝑥4 = 4
𝑥5 = 6
 Lucro: Z = 150 
Variáveis não básicas: 𝑥2; 𝑥3. Variáveis básicas: 𝑥1;𝑥4; 𝑥5. 
Esta solução tem a seguinte interpretação: 
Se forem fabricadas três calças e zero camisa, o lucro será Z = 150 e não existirá folga no primeiro 
recurso. É uma solução básica viável. 
 
Análise no ponto C(3,3): 
variáveis do problema: {
𝑥1 = 3
𝑥2 = 3
 variáveis de folga: {
𝑥3 = 0
𝑥4 = 1
𝑥5 = 0
 Lucro: Z = 210 
Variáveis não básicas: 𝑥3; 𝑥5. Variáveis básicas: 𝑥1; 𝑥2; 𝑥4. 
Esta solução tem a seguinte interpretação: 
Se forem fabricadas três calças e três camisas, o lucro será Z = 210 e existirá folga de uma unidade 
no segundo recurso. É uma solução básica viável. 
 
Análise no ponto D(1,4): 
variáveis do problema: {
𝑥1 = 1
𝑥2 = 4
 variáveis de folga: {
𝑥3 = 2
𝑥4 = 0
𝑥5 = 0
 Lucro: Z = 130 
Variáveis não básicas: 𝑥4; 𝑥5. Variáveis básicas: 𝑥1; 𝑥2; 𝑥3. 
Esta solução tem a seguinte interpretação: 
Se forem fabricadas uma calça e quatro camisas, o lucro será Z = 120 e existirá folga de duas 
unidades no primeiro recurso. É uma solução básica viável. 
 
 
33 
 
Análise no ponto E(0,4): 
variáveis do problema: {
𝑥1 = 0
𝑥2 = 4
 variáveis de folga: {
𝑥3 = 3
𝑥4 = 0
𝑥5 = 1
 Lucro: Z = 80 
Variáveis não básicas: 𝑥1; 𝑥4. Variáveis básicas: 𝑥2; 𝑥3; 𝑥5. 
Esta solução tem a seguinte interpretação: 
Se forem fabricadas zero calça e quatro camisas, o lucro será Z = 80 e existirá folga de três 
unidades no primeiro recurso e uma unidade no terceiro recurso. É uma solução básica viável. 
 
Análise no ponto F(3,4): 
variáveis do problema: {
𝑥1 = 3
𝑥2 = 4
 variáveis de folga: {
𝑥3 = 0
𝑥4 = 0
 𝑥5 = −2
 Lucro: Z = 230 
Variáveis não básicas: 𝑥3; 𝑥4. Variáveis básicas: 𝑥1; 𝑥2; 𝑥5. 
Esta solução tem a seguinte interpretação: 
Se forem fabricadas três calças e quatro camisas, o lucro será Z = 230 e haverá falta de duas 
unidades no terceiro recurso. É uma solução básica inviável. 
Esta solução é inviável porque se forem fabricadas 3 calças e 4 camisas são necessários 11 
homens/hora por dia, o que ultrapassa a quantidade de recurso disponível. 
 
 
 
 
 
 
 
4.3 Passos do Método Simplex 
O Método Simplex é uma técnica para se achar algebricamente a solução ótima de um problema de 
programação linear. Desde que exista uma solução ótima para um problema de programação linear, 
o método simplex sempre conseguirá obter esta solução. 
Sabe-se que a solução ótima de um problema de programação linear é uma solução compatível 
básica do sistema equações, ou seja, a solução está num dos pontos extremos da região viável. 
O método simplex para ser iniciado necessita conhecer uma solução compatível básica do sistema 
chamada solução inicial. 
O método simplex verifica se a presente solução é ótima. Se for, então o processo está encerrado. 
Conclusão: 
 A Solução Ótima Viável está no ponto C(3,3), porque é a melhor combinação de produção. 
Fabricar três calças e três camisas obtém-se o Lucro Máximo Z = 210 e ainda existirá uma 
folga de uma unidade no segundo recurso. 
Esta sobra de recurso poderá ser vendida ou atribuída a uma outra linha de produção. 
34 
 
Se não for ótima, é porque um dos pontos extremos adjacentes da região viável fornece um valor 
maior para a função objetivo. O método simplex faz a mudança para o próximo ponto adjacente e 
verifica se a solução é ótima. 
E assim por diante. 
 
Passos do Método Simplex 
Passo 1: Introduza as variáveis de folga no problema de programação linear. 
Passo 2: Monte o quadro de coeficientes das equações, incluindo-se a função objetivo com os sinais 
trocados. 
Passo 3: Crie a solução básica inicial, geralmente atribuindo-se valor zero às variáveis originais do 
problema. Identifique as variáveis básicas e não básicas. 
Passo 4: Determine a variável que entra na base: 
a) A variável que tem o maior coeficiente negativo na linha da função objetivo 
transformada deve entrar na base. Esta variável identifica a coluna pivô. 
 b) Quando não houver mais coeficiente negativo na linha da função objetivo, a solução 
 encontrada é ótima. 
Passo 5: Determine a variável que sai da base: 
 a) Divida os termos independentes pelos respectivos coeficientes positivos da variável que 
 entra na base. 
 b) O menor quociente positivo indica, pela equação em que ocorreu, a variável que deve sair 
da base. Esta variável identifica a linha pivô. Se não existir o menor quociente positivo 
então pare, o problema não tem solução ótima finita. 
Passo 6: No quadro dos coeficientes, o cruzamento da linha pivô com a coluna pivô defini o 
elemento pivô. Monte o novo quadro dos coeficientes, utilize transformações 
elementares nos coeficientes da linha pivô e faça o elemento pivô igual a 1. 
Passo 7: Substitua no novo quadro dos coeficientes a variável que entra na base e a variável que sai 
da base. 
Passo 8: Utilize transformações elementares nas outras linhas e faça os coeficientes da coluna pivô 
iguais a zero. 
Passo 9: Transforme a matriz dos coeficientes e encontre a nova solução básica. 
Passo 10: Identifique a nova solução básica identificando as variáveis básicas e as variáveis não 
básicas. Volte ao passo 4. 
 
 
 
35 
 
Exemplo 4.2: 
Seja o problema de programação linear referente à confecção de calças e camisas. 
Modelo Matemático: 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 =========> Função objetiva 
 𝑥1 ≤ 3 
 𝑥2 ≤ 4 Restrições do problema 
 𝑥1 + 2 𝑥2 ≤ 9 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
O problema está na Forma Padrão. 
Colocando-se as variáveis de folga o problema passa para a Forma Canônica. 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 
 𝑥1 + 𝑥3 = 3 Forma Canônica 
 𝑥2 + 𝑥4 = 4 
 𝑥1 + 2𝑥2 + 𝑥5 = 9 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0 
 
 
Montagem dos quadros do Método Simplex 
 
 x1 x2 x3 x4 x5 Z 
Base -50 -20 0 0 0 0 
x3 1 0 1 0 0 3 
x4 0 1 0 1 0 4 
x5 1 2 0 0 1 9 
 
O coeficiente na função objetivo mais negativo é -50, logo a variável x1 entra na base. 
O 𝑀𝑖𝑛 { 
3
1
; 
9
1
 } = 3. Logo a variável que sai da base é x3. 
 
 
 
 
 
 
 
XB: Variáveis 
Básicas 
XN: Variáveis 
não Básicas 
XN = {
𝑥1 = 0
𝑥2 = 0
 XB = {
𝑥3 = 3
𝑥4 = 4
𝑥5 = 9
 Z = 0 
 
Esta solução equivale ao ponto A na região viável. 
Entra na Base 
Sai 
 da 
Base 
36 
 
Montagem do novo quadro. 
 
 x1 x2 x3 x4 x5 Z 
Base 0 -20 50 0 0 150 
x1 1 0 1 0 0 3 
x4 0 1 0 1 0 4 
x5 0 2 -1 0 1 6 
 
O coeficiente na função objetivo mais negativo é -20, logo a variável x2 entra na base. 
O 𝑀𝑖𝑛 { 
4
1
; 
6
2
 } = 3. Logo a variável que sai da base é x5. 
 
Montagem do novo quadro. 
 x1 x2 x3 x4 x5 Z 
Base 0 0 40 0 10 210 
x1 1 0 1 0 0 3 
x4 0 0 1/2 1 -1/2 1 
x2 0 1 -1/2 0 1/2 3 
 
Como não existem mais coeficientes negativos na função objetivo então a solução é ótima. 
 
Exemplo 4.3: 
Seja o problema de programação linear referente ao problema do sapateiro. 
Modelo Matemático: 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 ==========> Função objetiva 
 𝑥1 ≤ 6 
 𝑥2 ≤ 5 Restrições do problema 
 2𝑥1 + 𝑥2 ≤ 6 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
O problema está na Forma Padrão. 
Colocando-se as variáveis de folga o problema passa para a Forma Canônica. 
 
 
Sai 
 da 
Base 
XN = {
𝑥2 = 0
𝑥3 = 0
 XB = {
𝑥1 = 3
𝑥4 = 4
𝑥5 = 6
 Z = 150 
 
Estasolução equivale ao ponto B na região viável. 
Entra na Base 
XN = {
𝑥3 = 0
𝑥5 = 0
 XB = {
𝑥1 = 3
𝑥2 = 3
𝑥4 = 1
 Z = 210 
 
Esta solução equivale ao ponto C na região viável. 
37 
 
𝑀𝑎𝑥 𝑍 = 50𝑥1 + 20𝑥2 
 𝑥1 + 𝑥3 = 6 Forma Canônica 
 𝑥2 + 𝑥4 = 5 
 2𝑥1 + 𝑥2 + 𝑥5 = 6 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0 
 
 
 
Montagem dos quadros do Método Simplex 
 
 x1 x2 x3 x4 x5 Z 
Base -50 -20 0 0 0 0 
x3 1 0 1 0 0 6 
x4 0 1 0 1 0 5 
x5 2 1 0 0 1 6 
 
O coeficiente na função objetivo mais negativo é -50, logo a variável x1 entra na base. 
O 𝑀𝑖𝑛 { 
6
1
; 
6
2
 } = 3. Logo a variável que sai da base é x5. 
 
Montagem do novo quadro. 
 x1 x2 x3 x4 x5 Z 
Base 0 5 0 0 25 150 
x3 0 -1/2 1 0 -1/2 3 
x4 0 1 0 1 0 5 
x1 1 1/2 0 0 1/2 3 
 
Como não existem mais coeficientes negativos na função objetivo então a solução é ótima. 
 
4.4 Análise Econômica do Problema de Programação Linear 
A interpretação econômica baseia-se nos coeficientes das variáveis na função objetiva final. 
1. O quadro final do Simplex num modelo de programação linear apresenta variáveis básicas e 
variáveis não básicas. 
2. A função objetiva está escrita em termos das variáveis não básicas. 
XB: Variáveis 
Básicas 
XN: Variáveis 
não Básicas 
XN = {
𝑥1 = 0
𝑥2 = 0
 XB = {
𝑥3 = 6
𝑥4 = 5
𝑥5 = 6
 Z = 0 
 
Entra na Base 
Sai 
 da 
Base 
XN = {
𝑥2 = 0
𝑥5 = 0
 XB = {
𝑥1 = 3
𝑥3 = 3
𝑥4 = 5
 Z = 150 
 
38 
 
3. Os valores das variáveis básicas estão representados na coluna dos termos independentes. 
Os valores das variáveis não básicas são sempre iguais a zero. 
4. O coeficiente da variável não básica na função objetiva mede a proporção da contribuição da 
variável na função objetiva (lucro no caso de maximização ou custo no caso de 
minimização). Indica a variação proporcional na função objetiva para o acréscimo ou 
diminuição de uma unidade na variável. 
5. No quadro final do simplex, a solução é ótima. Um aumento de zero para 1 unidade na 
variável não básica prejudica a função objetivo (lucros diminuem, custos aumentam). 
6. Alterações no lucro podem significar alterações em duas outras variáveis: receita e custo. 
7. O acréscimo de uma unidade em um dos recursos pode gerar ou não em acréscimos na 
função lucro. 
8. Acréscimo ou decréscimo em um dos coeficientes da função objetivo pode alterar a solução 
ótima do problema. 
 
Exemplo 4.4: 
Resolva pelo método simplex o seguinte problema de programação linear. 
Modelo Matemático: 
𝑀𝑎𝑥 𝑍 = 30𝑥1 + 40𝑥2 ========> Função objetiva 
 𝑥1 ≤ 24 
 𝑥2 ≤ 16 Restrições do problema 
 𝑥1 + 2 𝑥2 ≤ 40 
 𝑥1 ≥ 0 Restrições naturais 
 𝑥2 ≥ 0 
O problema está na Forma Padrão. 
Colocando-se as variáveis de folga o problema passa para a Forma Canônica. 
𝑀𝑎𝑥 𝑍 = 30𝑥1 + 40𝑥2 
 𝑥1 + 𝑥3 = 24 Forma Canônica 
 𝑥2 + 𝑥4 = 16 
 𝑥1 + 2𝑥2 + 𝑥5 = 40 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0 
 
 
 
 
 
 
XB: Variáveis 
Básicas 
XN: Variáveis 
não Básicas 
39 
 
Montagem dos quadros do Método Simplex 
 
 x1 x2 x3 x4 x5 Z 
Base -30 -40 0 0 0 0 
x3 1 0 1 0 0 24 
x4 0 1 0 1 0 16 
x5 1 2 0 0 1 40 
 
O coeficiente na função objetivo mais negativo é -40, logo a variável x2 entra na base. 
O 𝑀𝑖𝑛 { 
16
1
; 
40
2
 } = 16. Logo a variável que sai da base é x4. 
 
Montagem do novo quadro. 
 
 x1 x2 x3 x4 x5 Z 
Base -30 0 0 40 0 640 
x3 1 0 1 0 0 24 
x2 0 1 0 1 0 16 
x5 1 0 0 -2 1 8 
 
O coeficiente na função objetivo mais negativo é -30, logo a variável x1 entra na base. 
O 𝑀𝑖𝑛 { 
24
1
; 
8
1
 } = 8. Logo a variável que sai da base é x5. 
 
Montagem do novo quadro. 
 
 x1 x2 x3 x4 x5 Z 
Base 0 0 0 -20 30 880 
x3 0 0 1 2 -1 16 
x2 0 1 0 1 0 16 
x1 1 0 0 -2 1 8 
 
O coeficiente na função objetivo mais negativo é -20, logo a variável x4 entra na base. 
O 𝑀𝑖𝑛 { 
16
2
; 
16
1
 } = 8. Logo a variável que sai da base é x3. 
XN = {
𝑥1 = 0
𝑥2 = 0
 XB = {
𝑥3 = 24
𝑥4 = 16
𝑥5 = 40
 Z = 0 
 Sai 
 da 
Base 
Entra na Base 
XN = {
𝑥1 = 0
 𝑥4 = 0
 XB = {
 𝑥2 = 16
 𝑥3 = 24
𝑥5 = 8
 Z = 640 
 
Sai 
 da 
Base 
Entra na Base 
XN = {
𝑥4 = 0
 𝑥5 = 0
 XB = {
𝑥1 = 8
 𝑥2 = 16
 𝑥3 = 16
 Z = 880 
 
Sai 
 da 
Base 
Entra na Base 
40 
 
Montagem do novo quadro. 
 x1 x2 x3 x4 x5 Z 
Base 0 0 10 0 20 1040 
x4 0 0 1/2 1 -1/2 8 
x2 0 1 -1/2 0 1/2 8 
x1 1 0 1 0 0 24 
 
Como não existem mais coeficientes negativos na função objetivo então a solução é ótima. 
 
4.5 Casos Especiais 
A seguir serão apresentados alguns casos que podem ocorrer nos problemas de programação linear 
e que ainda não foram considerados 
 
Problema de Minimização 
Resolveu-se até agora modelos com funções objetivos a serem maximizadas. Quando a função 
objetivo tiver que ser minimizada deve-se transformar o problema de minimização num problema 
de maximização. Sabe-se que achar o mínimo de uma função é equivalente a achar o máximo do 
simétrico desta função. 
Graficamente tem-se a seguinte ilustração: 
 
 
 
 
 
 
 
 
 
 
Empate na Variável que Entra na Base 
Quando houver empate na escolha da variável que entra na base, deve-se tomar a decisão arbitrária. 
A única implicação envolvida é pode-se escolher um caminho mais longo ou mais curto para se 
chegar à solução ótima. 
No método gráfico, isto equivale a caminhar por um ponto ou por outro ponto na região viável. 
XN = {
𝑥3 = 0
 𝑥5 = 0
 XB = {
 𝑥1 = 24
𝑥2 = 8
𝑥4 = 8
 Z = 1040 
 
Sai 
 da 
Base 
 z1 
y1 
x1 
- f(x) 
f(x) 
x 
Mínimo de f(x): y1 
 
Máximo de –f(x): z1 
 
Observe que as distâncias: z1 = y1 
 
Conclusão: 
Mínimo de f(x) = Máximo – f(x) 
41 
 
Empate na Variável que Sai na Base - Degeneração 
Quando houver empate na escolha da variável que sai da base, deve-se também tomar a decisão 
arbitrária. Quando isto acontece, uma das variáveis básicas terá o valor nulo. A saída de uma 
variável básica nula provoca o aparecimento de outra variável básica nula na solução seguinte, sem 
alteração do valor na função objetivo. Neste caso a solução é chamada degenerada. Se os 
coeficientes da função objetivo retornam não negativos em alguma iteração, o caso não apresenta 
dificuldade. O problema aparece quando eventualmente se entrar em circuitos sem caracterizar a 
solução ótima. Pode ser que o problema não tenha solução. 
Solução Infinita 
Isto ocorre quando a variável que entra na base não possui coeficiente positivo nas equações de 
restrições do problema. 
Graficamente tem-se uma das seguintes situações: 
 
 
 
 
 
 
 
4.6 Problemas de Minimização 
Quando a função objetivo tiver que ser minimizada deve-se transformar o problema de minimização 
num problema de maximização. Sabe-se que achar o mínimo de uma função é equivalente a achar o 
máximo do simétrico desta função. 
Minimizar Z equivale a Maximizar –Z. 
Exemplo 4.5: 
Resolva pelo método simplex o seguinte problema de programação linear. 
Modelo Matemático: 
𝑀𝑖𝑛 𝑍 = −𝑥1 − 𝑥2 − 𝑥3 + 11 =====> Função objetiva 
 - 𝑥1 + 𝑥2 − 2𝑥3 ≥ −2 
 𝑥1 − 2𝑥2 + 𝑥3 ≥ −1 Restrições do problema 
 𝑥1≥ 0 
 𝑥2 ≥ 0 Restrições naturais 
 𝑥3 ≥ 0 
O problema não está na Forma Padrão. 
x2 
Região viável 
infinita 
x1 
x2 
Região viável 
infinita 
x1 
42 
 
Altera-se a função objetiva de Minimização para Maximização e as restrições de ≥ para ≤. 
𝑀𝑎𝑥 − 𝑍 = 𝑥1 + 𝑥2 + 𝑥3 − 11 =======> Função objetiva 
 𝑥1 − 𝑥2 + 2𝑥3 ≤ 2 
 - 𝑥1 + 2𝑥2 − 𝑥3 ≤ 1 Restrições do problema 
 𝑥1 ≥ 0 
 𝑥2 ≥ 0 Restrições naturais 
 𝑥3 ≥ 0 
O problema está na Forma Padrão. 
Colocando-se as variáveis de folga o problema passa para a Forma Canônica. 
𝑀𝑎𝑥 − 𝑍 = 𝑥1 + 𝑥2 + 𝑥3 − 11 
 𝑥1 − 𝑥2 + 2𝑥3 + 𝑥4 = 2 Forma Canônica 
 −𝑥1 + 2𝑥2 − 𝑥3 +𝑥5 = 1 
 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0; 
 
 
Montagem dos quadros do Método Simplex 
 
 x1 x2 x3 x4 x5 - Z 
Base -1 -1 -1 0 0 -11 
x4 1 -1 2 1 0 2 
x5 -1 2 -1 0 1 1 
 
Observe que somente os coeficientes das variáveis na função objetivo é que trocam de sinal. 
O coeficiente na função objetivo mais negativo é -1, qualquer das variáveis pode entrar da base. 
O 𝑀𝑖𝑛 { 
2
1
 } = 2. Logo a variável que sai da base é x4. 
Montagem do novo quadro. 
 
 x1 x2 x3 x4 x5 - Z 
Base 0 -2 1 1 0 -9 
x1 1 -1 2 1 0 2 
x5 0 1 1 1 1 3 
 
O coeficiente na função objetivo mais negativo é -2, logo a variável x2 entra da base. 
XB: Variáveis 
Básicas 
XN: Variáveis 
não Básicas 
XN = {
𝑥1 = 0
𝑥2 = 0
𝑥3 = 0
 XB = {
𝑥4 = 2
𝑥5 = 1
 -Z = -11 
 
Sai 
 da 
Base 
Entra na Base 
XN = {
𝑥2 = 0
𝑥4 = 0
𝑥5 = 0
 XB = {
𝑥1 = 2
𝑥5 = 3
 -Z = -9 
 Sai 
 da 
Base 
Entra na Base 
43 
 
O 𝑀𝑖𝑛 { 
3
1
 } = 3. Logo a variável que sai da base é x5. 
Montagem do novo quadro. 
 x1 x2 x3 x4 x5 - Z 
Base 0 0 3 3 2 -3 
x1 1 0 3 2 1 5 
x2 0 1 1 1 1 3 
 
Como não existem mais coeficientes negativos na função objetivo então a solução é ótima. 
Observe que Max –Z = -3, isto implica que Min Z = 3. 
Observação: No primeiro quadro, se outra variável fosse inserida na base poderia gerar mais 
quadros até se chegar à mesma solução ótima. 
 
Exemplo 4.6: 
Resolva pelo método simplex o seguinte problema de programação linear. 
Modelo Matemático: 
𝑀𝑖𝑛 𝑍 = 3𝑥1 − 4𝑥2 + 𝑥3 =======> Função objetiva 
 𝑥1 + 𝑥2 + 𝑥3 ≤ 10 
 2𝑥1 + 𝑥2 − 𝑥3 ≤ 20 Restrições do problema 
 𝑥1 ≥ 0 
 𝑥2 ≥ 0 Restrições naturais 
 𝑥3 ≥ 0 
O problema não está na Forma Padrão. 
Altera-se a função objetiva de Minimização para Maximização. 
𝑀𝑎𝑥 − 𝑍 = −3𝑥1 + 4𝑥2 − 𝑥3 
 𝑥1 + 𝑥2 + 𝑥3 ≤ 10 
 2 𝑥1 + 𝑥2 − 𝑥3 ≤ 20 
 𝑥1 ≥ 0 
 𝑥2 ≥ 0 
 𝑥3 ≥ 0 
O problema está na Forma Padrão. 
 
 
 
 
XN = {
𝑥3 = 0
𝑥4 = 0
𝑥5 = 0
 XB = {
𝑥1 = 5
𝑥2 = 3
 -Z = -3 
 Z = 3 
44 
 
Colocando-se as variáveis de folga o problema passa para a Forma Canônica. 
𝑀𝑎𝑥 − 𝑍 = −3𝑥1 + 4𝑥2 − 𝑥3 
 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 10 Forma Canônica 
 2𝑥1 + 2𝑥2 − 𝑥3 +𝑥5 = 20 
 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0; 
 
Montagem dos quadros do Método Simplex 
 
 x1 x2 x3 x4 x5 - Z 
Base 3 -4 1 0 0 0 
x4 1 1 1 1 0 10 
x5 2 1 -1 0 1 20 
 
O coeficiente na função objetivo mais negativo é -4, logo a variável x2 entra na base. 
O 𝑀𝑖𝑛 { 
10
1
 ; 
20
1
} = 10. Logo a variável que sai da base é x4. 
 
Montagem do novo quadro. 
 x1 x2 x3 x4 x5 - Z 
Base 7 0 5 4 0 40 
x2 1 1 1 1 0 10 
x5 1 0 -2 -1 1 10 
 
Como não existem mais coeficientes negativos na função objetivo então a solução é ótima. 
 
4.7 Obtenção da Solução Inicial 
Sempre é possível transformar um modelo de programação linear num sistema equações lineares na 
forma padrão. Acontece que para se iniciar o método simplex é necessário tem o modelo de 
programação linear na forma canônica, ou seja, apresentando uma solução básica compatível. 
Os modelos desenvolvidos até agora têm todas as restrições do tipo menor ou igual ( ≤ ) e todos os 
termos independentes bi maiores ou iguais a zero ( ≥ ). Assim, sempre é tem-se uma base inicial 
óbvia compatível, formada pelas variáveis de folga. 
A seguir será os vários casos de dificuldades e como é possível achar uma solução compatível 
básica inicial quando o modelo de programação linear não estiver na forma canônica. 
XB: Variáveis 
Básicas 
XN: Variáveis 
não Básicas 
XN = {
𝑥1 = 0
𝑥2 = 0
𝑥3 = 0
 XB = {
𝑥4 = 10
𝑥5 = 20
 -Z = 0 
 
Sai 
 da 
Base 
Entra na Base 
XN = {
𝑥1 = 0
𝑥3 = 0
𝑥4 = 0
 XB = {
𝑥2 = 10
𝑥5 = 10
 - Z = 40 
 Z = - 40 
45 
 
4.8 Maximização com Restrições do Tipo Maior ou Igual ( ≥ ) 
Supõem-se um modelo de programação linear em que todos os termos independentes bi sejam ≥ 0. 
Se algum dos bi for negativo pode-se multiplicar toda a equação por -1 para transformá-lo em 
positivo. 
A dificuldade surge quando o modelo de programação linear apresenta uma restrição do tipo maior 
ou igual ( ≥ ) ou do tipo igual ( = ) com o termo bi positivo. 
 
Exemplo 4.7: 
Seja o problema de programação linear: 
𝑀𝑎𝑥 𝑍 = 5𝑥1 + 2𝑥2 ========> Função objetiva 
 𝑥1 ≤ 3 
 𝑥2 ≤ 4 Restrições do problema 
 𝑥1 + 2 𝑥2 ≥ 9 
 𝑥1 ≥ 0 
 𝑥2 ≥ 0 Restrições naturais 
 
Graficamente corresponde à seguinte região viável: 
 
 
 
 
 
 
 
 
 
 
Observe que o modelo não está na forma padrão porque a 3ª. Restrição é do tipo ≥. 
Colocando as variáveis de folga tem-se o seguinte modelo: 
𝑀𝑎𝑥 𝑍 = 5𝑥1 + 2𝑥2 
 𝑥1 + 𝑥3 = 3 
 𝑥2 + 𝑥4 = 4 
 𝑥1 + 2 𝑥2 − 𝑥5 = 9 
 𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0; 𝑥4 ≥ 0; 𝑥5 ≥ 0 Sistema A 
Xn = {
𝑥1 = 0
𝑥2 = 0
 XB = {
𝑥3 = 3
𝑥4 = 4
𝑥5 = −9
 Z = 0 
 
F 
( 
Região Viável 
( x1 = 3 
x2 = 4 
x1 + 2x2 = 9 
x1 = 0 
x2 = 0 
E(0,4) D(1,4) 
C(3,3) 
B(3,0) 
A(0,0) 
x2 
3 2 1 
1 
2 
3 
4 
x1 
46 
 
Nota: Este modelo não está na forma canônica porque o sistema equações lineares não apresenta 
uma solução básica compatível. Observe que 𝑥5 = −9 é uma solução negativa o que é 
incompatível, pois todas as variáveis devem ser positivas. Logo, esta solução é incompatível. 
Solução: 
Para se obter uma forma canônica para o modelo, isto é, uma solução básica compatível, pode-se 
acrescentar uma variável artificial x6 na equação em questão. Esta variável tomará o lugar de 𝒙𝟓 na 
solução básica inicial, e assim o problema fica resolvido. 
Se a 3ª. equação inicialmente fosse uma igualdade deveria também ser colocada uma variável 
artificial.