UNIVERSIDADE REGIONAL INTEGRADA DO ALTO URUGUAI E DAS
MISSÕES – URI
CAMPUS SANTO ÂNGELO
Disciplina: Programação Matemática1
Prof: Msc. Regiane Klidzio
1
Este material didático foi adaptado a partir do material didático oferecido pelo Prof Maurílio Tiecker.
2
CONTEÚDO
1. MODELOS DE PROGRAMAÇÃO LINEAR _____________________________________________ 4
1.1 Introdução ____________________________________________________________________________4
1.2 Programação linear _____________________________________________________________________4
1.3 O que é um modelo _____________________________________________________________________5
1.3.1 Tipos de modelos _____________________________________________________________________ 5
1.3.2 Estrutura dos modelos _________________________________________________________________ 6
1.3.3 Características dos modelos _____________________________________________________________ 6
1.3.4 Formulação dos modelos _______________________________________________________________ 6
1.4 Etapas para a construção dos modelos de otimização ___________________________________________7
1.5 Exemplos de formulação de modelos matemáticos _____________________________________________8
1.5.1 Problema da dieta ____________________________________________________________________ 8
1.5.2 Problema do carpinteiro ________________________________________________________________ 9
2. RESOLUÇÃO GRÁFICA DOS PPL __________________________________________________ 13
2.1 Introdução ___________________________________________________________________________13
2.2 Passos para aplicação do método gráfico ___________________________________________________13
2.3 Exemplos ____________________________________________________________________________13
2.3.1 Exemplo 1 _________________________________________________________________________ 13
2.3.2 Exemplo 2 _________________________________________________________________________ 16
2.3.3 Exemplo 3 _________________________________________________________________________ 17
2.4 Exemplos de anomalias _________________________________________________________________18
3. PROGRAMAÇÃO LINEAR _________________________________________________________ 21
3.1 Introdução ___________________________________________________________________________21
3.2 Desenvolvimento do modelo matemático ___________________________________________________21
3.3 Interpretação do modelo ________________________________________________________________22
3.4 Tipos de soluções______________________________________________________________________22
3.5 Propriedades _________________________________________________________________________23
4. O MÉTODO SIMPLEX_____________________________________________________________ 24
4.1 Desenvolvimento do método _____________________________________________________________24
4.1.1 Problema da forma geral ______________________________________________________________ 24
4.1.2 Problema na forma canônica ___________________________________________________________ 25
4.2 Algoritmo do método simplex ____________________________________________________________27
4.2.1 Regra de partida _____________________________________________________________________ 28
4.2.2 Regra de parada _____________________________________________________________________ 28
4.2.3 Processo iterativo ____________________________________________________________________ 28
5. CASOS ESPECIAIS DO MÉTODO SIMPLEX _________________________________________ 31
5.1 Empate na entrada _____________________________________________________________________32
5.2 Empate na saída _______________________________________________________________________32
5.3 Função objetivo ilimitada _______________________________________________________________33
Programação Matemática
3
5.4 Soluções ótimas múltiplas _______________________________________________________________33
5.5 Outras formas de modelo ________________________________________________________________33
5.5.1 Problemas de minimização ____________________________________________________________ 33
5.5.2 Modificações nas restrições ____________________________________________________________ 34
6. VALOR MARGINAL (PREÇO SOMBRA) _____________________________________________ 40
7. PROBLEMA DUAL _______________________________________________________________ 42
7.1 Exemplo 1 ___________________________________________________________________________42
7.2 Exemplo 2 ___________________________________________________________________________42
8. REFERÊNCIAS BIBLIOGRÁFICAS _________________________________________________ 46
Programação Matemática
4
1. MODELOS DE PROGRAMAÇÃO LINEAR
1.1 Introdução
Durante a Segunda Guerra Mundial, um grupo de cientistas foi convocado na Inglaterra para
estudar problemas de estratégia e de tática associados com a defesa do país. O objetivo era decidir sobre
a utilização mais eficaz de recursos militares limitados. A convocação deste grupo marcou a primeira
atividade formal de pesquisa operacional.
Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os
Estados Unidos a iniciarem atividades semelhantes. Apesar de ser creditada à Inglaterra a origem da
Pesquisa Operacional, sua propagação deve-se principalmente à equipe de cientistas liderada por George
B. Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste
esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex.
Com o fim da guerra, a utilização de técnicas de pesquisa operacional atraiu o interesse de
diversas outras áreas. A natureza dos problemas encontrados é bastante abrangente e complexa, exigindo
portanto uma abordagem que permita reconhecer os múltiplos aspectos envolvidos. Uma característica
importante da pesquisa operacional e que facilita o processo de análise e de decisão é a utilização de
modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser
mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experiência
adquirida pela experimentação justificam a utilização da Pesquisa Operacional.
Com o aumento da velocidade de processamento e quantidade de memória dos computadores
atuais, houve um grande progresso na Pesquisa Operacional. Este progresso é devido também à larga
utilização de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com
que os modelos desenvolvidos pelos profissionais de Pesquisa Operacional sejam mais rápidos e
versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do
processo de cálculo.
1.2 Programação linear
A Pesquisa Operacional é um conjunto de técnicas matemáticas que visa fornecer soluções para o
problema em que existam restrições (recursos limitados ou necessidades mínimas a serem atingidas) com
o objetivo de se obter resultados ótimos. Programação linear, programação inteira, programação
dinâmica, programação estocástica e programação não- linear são exemplos de técnicas matemáticas em
Programação Linear.
A Programação Linear é uma das técnicas da Pesquisa Operacional das mais utilizadas em se
tratando de problemas de otimização. Essa técnica visa fundamentalmente encontrar a melhor solução
para problemas que tenham modelos representados por expressões lineares. A grande aplicabilidade e
simplicidade que a caracterizam devem-se à linearidade do modelo (BREGALDA, 1983).
A tarefa da Programação Linear consiste na maximização ou minimização de um função linear
denominada função objetivo, respeitando-se um sistema linear de igualdades ou desigualdades que
recebem o nome de restrições do modelo (BREGALDA, 1983). Capital, mão-de-obra, fatores de
produção ou então exigências e condições que devem ser cumpridas no problema são exemplos de
restrições.
Programação Matemática
5
 As restrições do modelo determinam uma região denominada conjunto de soluções viáveis.
 A melhor solução entre as soluções viáveis, isto é, aquela que maximiza ou minimiza a
função objetivo denomina-se solução ótima.
Assim, o objetivo da Programação Linear consiste na determinação da solução ótima.
Para a resolução de um PPL (Problema de Programação Linear) dois passos são
fundamentalmente necessários: modelagem do problema e aplicação do método em busca da solução do
modelo. No caso do PPL, o método mais utilizado é o Simplex que examinaremos mais adiante
(BREGALDA, 1983).
Hoje, além de ser o método de Programação Matemática mais aplicado na solução de modelos
matemáticos de otimização, o Método Simplex é de grande importância teórica e parte fundamental de
diversos outros métodos de otimização.
1.3 O que é um modelo
Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto
aguardando execução. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de
modo a aumentar sua produtividade. No segundo caso, o modelo é utilizado para definir a estrutura ideal
do sistema.
Segundo Puccini (1989), um modelo é uma idealização ou uma visão simplificada da realidade. A
partir dessa idealização, o modelo emprega símbolos matemáticos para representar as variáveis de
decisão do sistema real. Essas variáveis são relacionadas por funções matemáticas que expressam o
funcionamento do sistema. A solução consiste em encontrar valores adequados das variáveis de decisão
que otimizem o desempenho do sistema, segundo o critério desejado.
A confiabilidade da solução obtida através do modelo depende da validação do modelo na
representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o
sistema real. A diferença entre a solução real e a solução proposta pelo modelo depende diretamente da
precisão do modelo em descrever o comportamento original do sistema.
Um problema simples pode ser representado por modelos também simples e de fácil solução. Já
problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante
complicada.
1.3.1 Tipos de modelos
Dependendo da maneira como o processo de decisão é abordado pelo analista e da própria
natureza da decisão, podemos identificar diferentes tipos de modelo, como:
Modelos conceituais: Relacionam de maneira sequencial e lógica as informações e as fases do
processo de decisão, de modo a permitir o desenvolvimento controlado e consistente com os objetivos
que se tem em mente;
Modelos matemáticos (ou simbólicos): Baseiam-se na pressuposição de que todas as
informações e variáveis relevantes do problema de tomada de decisão podem ser quantificadas. Isso nos
leva a utilizar símbolos matemáticos para representá-las e a usar funções matemáticas para descrever as
ligações entre elas e a operação do sistema. Esses modelos são classificados em modelos de otimização e
modelos de simulação.
Programação Matemática
6
Modelos heurísticos: São construídos quando a complexidade do problema é de tal ordem que a
utilização de relações matemáticas torna-se impraticável ou extremamente dispendiosa. Esses modelos
baseiam-se em regras empíricas ou intuitivas que, dada determinada solução para o problema, permitem o
avanço para outra solução mais aprimorada. São basicamente procedimentos de busca inteligente de
estados do processo de decisão sempre em direção ao aumento do valor do critério escolhido. Os modelos
construídos com base nas técnicas de inteligência artificial são modelos heurísticos (ANDRADE, 2009).
Exemplos: problema da mochila, problema do caixeiro viajante, problema de roteamento de veículos.
1.3.2 Estrutura dos modelos
Em um modelo matemático, são incluídos três conjuntos principais de elementos:
1) Variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem
determinadas pela solução do modelo. Parâmetros são valores fixos no problema;
2) Restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir
restrições que limitam as variáveis de decisão a seus valores possíveis (ou viáveis);
3) Função objetivo: é uma função matemática que define a qualidade da solução em função das
variáveis de decisão.
1.3.3 Características dos modelos
a) Um critério de escolha das variáveis de decisão é constituído por uma função linear das
variáveis. Esta função é denominada função objetivo e seu valor deve ser otimizado (maximizado ou
minimizado).
b) As relações de interdependência entre as variáveis de decisão se expressam por um conjunto
de equações e/ou inequações lineares. Essas relações são denominadas restrições.
c) As variáveis de decisão do modelo são não negativas, ou seja, positivas ou nulas (PUCCINI,
1989).
1.3.4 Formulação dos modelos
Para a formulação dos modelos as três características já citadas devem ser observadas, segundo a
seguinte ordem:
1) Definir claramente as variáveis de decisão: são as incógnitas a serem determinadas pela
solução do modelo. Elas representam os recursos ou o que realmente queremos determinar com a solução
do problema.
2) Determinar a equação da função objetivo: é uma função matemática que define a qualidade
da solução em função das variáveis de decisão. É onde expressamos, exatamente, a meta que queremos
obter com a solução do nosso problema.
3) Determinar o conjunto de restrições: devem existir uma ou mais restrições que reúnam
limites ou possíveis valores das variáveis de decisão. O modelo deve incluir restrições que limitam as
variáveis de decisão a seus valores possíveis ou viáveis (PUCCINI, 1989).
A função objetivo e as restrições devem ser expressas em termos das variáveis de decisão.
Programação Matemática
7
1.4 Etapas para a construção dos modelos de otimização
Segundo Andrade (2009), a construção dos modelos de otimização geralmente envolve as
seguintes etapas:
1) Definição do problema:
A definição do problema baseia-se em três aspectos principais:



descrição exata dos objetivos do estudo;
identificação das alternativas de decisão existentes;
reconhecimento das limitações, restrições e exigências do sistema.
A descrição dos objetivos é uma das atividades mais importantes em todo o processo do estudo,
pois a partir dela é que o modelo é concebido. Da mesma forma, é essencial que as alternativas de decisão
e as limitações existentes sejam todas explicitadas, para que as soluções obtidas ao final do processo
sejam válidas e aceitáveis.
2) Identificação das variáveis relevantes:
 As variáveis de decisão para as quais o analista procura valores ótimos;
 Variáveis exógenas ou não controláveis2 que servem de base para a definição de restrições ou
de variáveis endógenas.
 Variáveis endógenas ou controláveis3 que, dependendo dos valores de outras, muitas vezes
entram na formação da função objetivo ou das restrições que o analista deve especificar.
A variável de decisão é, sem dúvida, uma variável controlável especial por indicar a decisão.
3) Formulação da função objetivo:
A função objetivo reflete o critério de otimização das variáveis de decisão e deve ser escrita em
forma matemática.
4) Formulação das restrições:
 Em grande número de modelos de otimização as variáveis são sujeitas a algumas restrições,
que devem ser escritas na forma matemática.
 A relação entre as variáveis também deve ser formulada matematicamente.
2
São os fatores ou dados externos fornecidos ao modelo e que representam as hipóteses levantadas ou as condições que devem
ser respeitadas.
3
São geradas pelo próprio modelo durante o processo de solução, sendo dependente dos dados fornecidos, das hipóteses
estabelecidas e da própria estrutura do modelo.
Programação Matemática
8
5) Escolha do método matemático de solução:
 Tendo definido o problema, devemos escolher um método matemático adequado para a
solução do modelo.
 A escolha do método é feita tendo em vista o tipo de modelo matemático criado e as análises
e questões às quais o modelo deve fornecer subsídios.
6) Aplicação do método de solução:
 O método de solução é simplesmente um exercício matemático que pode ser realizado
manualmente ou por computador.
 Em ambos os casos, será necessário um conhecimento do algoritmo, seja para desenvolver o
processo de cálculo, seja para acompanhar a solução do computador e entender suas mensagens.
7) Avaliação da solução:
 Tendo encontrado a solução, esta deve ser verificada e avaliada à luz das expectativas e
experiências do analista, antes de ser efetivamente implementada.
 Vale lembrar que, a maioria das decisões deve ser tomada em um ambiente de risco e
incerteza e que grande parte dos modelos de otimização é determinística4.
 Assim, deve-se obter uma estimativa de risco por meio de uma análise de sensibilidade pósotimização.
1.5 Exemplos de formulação de modelos matemáticos
1.5.1 Problema da dieta
Um nutricionista precisa estabelecer uma dieta, contendo, pelos menos, 10 unidades de vitamina
A, 30 unidades de vitamina B e 18 unidades de vitamina C. Essas vitaminas estão contidas em
quantidades variadas em cinco elementos chamados s1, s2, s3, s4 e s5. O quadro apresenta o número de
unidades das vitaminas A, B e C em cada unidade desses cinco alimentos como o seu custo por unidade.
Calcular a quantidade dos cinco alimentos que deve ser incluída na dieta diária, a fim de garantir os teores
de cada vitamina e com o menor custo possível.
A
B
C
Custo
s1
0
2
3
4
s2
1
1
1
2
s3
5
0
0
1
s4
4
3
9
10
4
s5
3
2
0
5
Um modelo determinístico pode ser definido como um modelo cujas respostas não possuem um componente aleatório.
Assim, para um dado conjunto de parâmetros, uma entrada E* produz sempre uma saída S*. Isso pode ser verdade mesmo que
o modelo compute uma probabilidade.
Programação Matemática
9
Solução:
a) Variáveis de decisão:
x1 = quantidade do alimento s1 a ser incluído na dieta diária
x2 = quantidade do alimento s2 a ser incluído na dieta diária
x3 = quantidade do alimento s3 a ser incluído na dieta diária
x4 = quantidade do alimento s4 a ser incluído na dieta diária
x5 = quantidade do alimento s5 a ser incluído na dieta diária
b) Função objetivo:
Deve-se determinar os valores das variáveis de decisão de modo a minimizar o custo.
Custo do alimento s1 = 4x1
Custo do alimento s2 = 2x2
Custo do alimento s3 = x3
Custo do alimento s4 = 10x4
Custo do alimento s5 = 5x5
Z = 4x1 + 2x2 + x3 + 10x4 + 5x5 ou Min custo = 4x1 + 2x2 + x3 + 10x4 + 5x5
c) Restrições:
Necessidade de vitamina A = x2 + 5x3 + 4x4 +3x5  10
Necessidade de vitamina B = 2x1 + x2 + 3x4 +2x5  30
Necessidade de vitamina C = 3x1 + x2 + 9x4  18
Restrição de não negatividade: x1, x2, x3, x4, x5  0
d) Modelo:
Min custo = 4x1 + 2x2 + x3 + 10x4 + 5x5
x2 + 5x3 + 4x4 +3x5  10
2x1 + x2 + 3x4 +2x5  30
3x1 + x2 + 9x4  18
x1, x2, x3, x4, x5  0
1.5.2 Problema do carpinteiro
Um carpinteiro dispõe de 90, 80 e 50 metros das madeiras A, B e C. Uma escrivaninha requer 2, 1
e 1 metro da madeira A, B e C respectivamente e um armário requer 1, 2 e 1 metro respectivamente. Se a
escrivaninha é vendida por 120 u.m. e o armário por 100 u.m., quantas escrivaninhas e quantos armários
precisam ser fabricados para ter maior rendimento.
Solução:
a) Variáveis de decisão:
x1 = quantidade de escrivaninhas a serem fabricadas
x2 = quantidade de armários a serem fabricados
b) Função objetivo:
Maximizar o rendimento.
Custo da escrivaninha = 120x1
Custo do armário = 100x2
Z = 120x1 + 100x2 ou Max rendimento = 120x1 + 100x2
Programação Matemática
10
c) Restrições:
Disponibilidade da madeira A = 2x1 + x2  90
Disponibilidade da madeira B = x1 + 2x2  80
Disponibilidade da madeira C = x1 + x2  50
Restrição de não negatividade: x1, x2  0
d) Modelo:
Max rendimento = 120x1 + 100x2
2x1 + x2  90
x1 + 2x2  80
x1 + x2  50
x1, x2  0
Lista de Exercícios 1
1) A padaria Aurora confecciona biscoitos salgado e doce; o biscoite salgada dá um lucro de 400 u.m. por
caixa e o doce um lucro de 300 u.m. por caixa. Os biscoitos são processados em três operações principais:
mistura, cozimento e embalagem. O tempo disponível para cada operação é de 7,4 horas; 13 horas e 4,5
horas respectivamente. Para cada caixa de biscoito, os tempos necessários em cada operação são: salgado:
10 minutos, 20 minutos e 5 minutos; doce: 15 minutos, 20 minutos e 3 minutos respectivamente. A
padaria pode fabricar no máximo 200 caixas de biscoitos, independente do tipo. Quantas caixas de cada
tipo devem fazer para ter o maior lucro?
2) Uma fábrica produz dois artigos utilizando os mesmo recursos de pessoal máquinas e matérias-primas.
Estes recursos são limitados num certo período. Os recursos necessários à fabricação de cada unidade dos
artigos e as disponibilidades bem com os lucros unitários relativos a cada artigo são dados no quadro
seguinte:
Recursos
Mão de obra I
Mão de obra II
Equipamento I
Equipamento II
Matéria prima I
Matéria prima II
Lucro unitário (u.m.)
A
10
20
30
12
15
5
B
10
20
10
10
9
10
8
Disponibilidade
30 horas
70 horas
80 horas
130 horas
120 toneladas
100 toneladas
Quais as quantidades que devem ser produzidas para obter lucro máximo?
3) Uma empresa fabrica os produtos A e B cujos os mercados absorvem 100 e 80 unidades
respectivamente. No processo de produção usam-se as matérias primas I e II. Cada unidade de A consome
2 unidades da matéria prima I e 4 da matéria prima II. Cada unidade de B consome 3 unidades da matéria
prima I e 3 da matéria prima II. Estão disponíveis 200 unidades de matéria prima I e 240 unidades de
matéria prima II. Os lucros unitários são de 20 e 25 u.m. para A e B respectivamente. Qual deve ser o
esquema de produção visando-se obter lucro máximo?
Programação Matemática
11
4) Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a manufatura das rações
são utilizados cereais e carne. Sabe-se que:
 a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg
de cereais;
 o pacote de ração Tobi custa $20 e o pacote de ração Rex custa $30;
 o kg de carne custa $4 e o kg de cereais custa $1;
 estão disponíveis por mês 10000 kg de carne e 30000 kg de cereais.
Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro.
5) Uma fábrica produz tampas de dois tamanhos utilizando uma chapa de dimensões 1 x 0,40. Na
estamparia existem 3 tipos d matrizes que podem ser utilizadas par ao corte; sabe-se que as tampas tem
diâmetros de 0,2 e 0,4 respectivamente. A fábrica deve produzir pelo menos 400 tampas pequenas e 300
tampas grandes para atender a compromissos já contratados qual deve ser o esquema de produção para
atender a estes compromissos e gastar a menor quantidade de chapas?
6) Uma metalúrgica deseja maximizar sua receita bruta. A tabela a seguir ilustra a proporção de cada
material na mistura para a obtenção das ligas passiveis 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 e obter a solução ótima para que a
metalúrgica possa maximizar sua receita bruta.
Metais
Cobre
Zinco
Chumbo
Receita bruta
Liga especial de
baixa resistência
0,5
0,25
0,25
R$ 3.000
Liga especial de alta
resistência
0,2
0,3
0,5
R$ 5.000
Disponibilidade de
matéria-prima
16 ton
11 ton
15 ton
7) 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,
2 e 5 unidades monetárias. 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 unidades de 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 otimizar o lucro total.
8) Para fazer um determinado serviço usam-se dois equipamentos A e B. Dispõe-se de 4 unidades de A e
10 unidades de B e apenas 24 homens para operá-los. O equipamento A necessita de 4 homens para ser
operado e o equipamento B de apenas 2 homens. O equipamento A é 3 vezes mais eficiente que o B.
Quantos equipamentos de cada tipo devemos usar para obter a maior eficiência?
Programação Matemática
12
9) Uma empresa fabril está interessada em maximizar o lucro mensal proveniente de quatro de seus
produtos designados por I, II, III e IV. Para fabricar esses produtos ela utiliza dois tipos de máquinas M1
e M2 e dois tipos de mão de obra MO1 e MO2 com as seguintes disponibilidades:
Máquinas
M1
M2
Tempo disponível
(máquina-hora/mês)
800
200
Mão de obra
Tempo disponível
(homem-hora/mês)
12000
16000
MO1
MO2
O setor técnico da empresa fornece os seguintes quadros de produtividade:
a) Número de máquina-hora para produzir uma unidade de cada produto:
Produtos
Máquinas
I
II
III
IV
M1
5
4
8
9
M2
2
6
8
b) Número de homem-hora para produzir uma unidade de cada produto:
Produtos
Mão de obra
I
II
III
MO1
2
4
2
MO2
7
3
-
IV
8
7
O setor comercial da empresa fornece as seguintes informações:
Produtos
Potencial de vendas
Lucro unitário
(unidade/mês)
($/unidade)
I
70
10,00
II
60
8,00
III
40
9,00
IV
20
7,00
Deseja-se saber a produção mensal dos produtos I, II, III e IV para que o lucro mensal da empresa,
proveniente desses quatro produtos, seja máximo. Formule um modelo de programação linear que
expresse o objetivo e as restrições dessa empresa.
10) 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. A escrivaninha é vendida por 100
unidades monetárias, a mesa por 80 unidades monetárias, o armário por 120 unidades monetárias e a
prateleira por 20 unidades monetárias. Pede-se exibir um modelo de programação linear que maximize a
receita com as vendas dos móveis.
Tábua
Prancha
Painéis
Valor de revenda
Quantidade de material em metros consumidos
por unidade de produtos
Escrivaninha
Mesa
Armário
1
1
1
0
1
1
3
2
4
100
80
120
Programação Matemática
Disponibilidade
de recursos
Prateleira
4
2
0
20
250
600
500
13
2. RESOLUÇÃO GRÁFICA DOS PPL
2.1 Introdução
Nesta seção vamos apresentar como encontrar graficamente a solução ótima, se existir para alguns
casos de Problemas de Programação Linear (PPL). Em geral, apenas os problemas que envolvem duas
variáveis de decisão são resolvidos graficamente. Um problema com três variáveis de decisão também
pode ser resolvido graficamente, embora, na maioria das vezes, isso não seja fácil. A partir de quatro
variáveis de decisão a resolução só é possível algebricamente.
Dado um PPL, uma solução viável é um vetor que especifica o valor de cada variável de decisão
tal que, se as variáveis são substituídas por estes valores, então todas as restrições serão satisfeitas.
Uma solução ótima é uma solução viável que maximiza ou minimiza a função objetivo sobre o
conjunto das soluções viáveis.
Para um PPL envolvendo até três variáveis de decisão, o conjunto das soluções viáveis pode ser
identificado como uma região do espaço cartesiano tridimensional e, assim, o PPL pode ser resolvido
graficamente.
2.2 Passos para aplicação do método gráfico
1º passo: construir um sistema de eixos cartesianos para as variáveis de decisão;
2º passo: identificar os valores das variáveis de decisão que satisfaçam todas as restrições;
3º passo: determinar a solução.
2.3 Exemplos
2.3.1 Exemplo 1
A empresa Nova Linha produz artigos de vidro de alta qualidade: janelas e portas, em três seções
de produção:



Seção 1: seção de serralharia para produzir as estruturas de alumínio.
Seção 2: seção de carpintaria para produzir as estruturas de madeira.
Seção 3: seção de vidro e montagem para produzir o vidro e montar as portas e janelas.
Devido à diminuição dos lucros, o gerente decidiu reorganizar a produção, e propõe produzir
apenas 2 produtos que têm uma melhor aceitação entre os clientes. Estes produtos são:


Produto 1: uma porta de vidro com estrutura de alumínio.
Produto 2: uma janela grande com estrutura de madeira.
O Departamento de Marketing concluiu que a empresa pode vender muito bem esses dois
produtos, tendo em conta a capacidade de produção disponível. Como ambos os produtos partilham a
capacidade de produção da seção 3, o gerente solicitou ao Departamento de Investigação Operacional da
Programação Matemática
14
empresa a resolução deste problema. Esse departamento formulou o problema, utilizando os seguintes
dados:
 A capacidade de produção por minuto de cada seção a ser utilizada na produção destes
produtos.
 A capacidade de produção por minuto de cada seção a ser utilizada para produzir uma unidade
de cada produto.
 Os lucros unitários para cada produto em Euros.
Estes dados estão resumidos na seguinte tabela:
Seção
1
2
3
Lucro unitário
Capacidade utilizada por
unidade de produção
Produto 1
Produto 2
1
0
3
3
0
2
2
5
Pede-se:
a) Formular o modelo de programação linear que maximize o lucro.
b) Determinar a solução ótima pelo método gráfico.
Solução:
a) Variáveis de decisão:
x1 = número de unidades do produto 1 produzidos por minuto
x2 = número de unidades do produto 2 produzidos por minuto
b) Função objetivo:
Maximizar o lucro.
Lucro unitário do produto 1 = 3x1
Lucro unitário do produto 2 = 5x2
Z = 3x1 + 5x2 ou Max lucro = 3x1 + 5x2
c) Restrições:
Capacidade disponível da seção 1 = x1  4
Capacidade disponível da seção 2 = 2x2  12
Capacidade disponível da seção 3 = 3x1 + 2x2  18
Restrição de não negatividade: x1, x2  0
d) Modelo:
Max lucro = 3x1 + 5x2
x1  4
2x2  12
3x1 + 2x2  18
x1, x2  0
Programação Matemática
Capacidade
disponível
4
12
18
15
e) Representação gráfica:
1º passo: construir um sistema de eixos cartesianos x1 e x2.
2º passo: identificar os valores de x1 e x2 que satisfaçam todas as restrições.
 Condições de não negatividade: os pontos x1 e x2 estão situados nos 1º quadrante
 Restrições:
x1  4
 x1 = 4 e x2 = 0 (estão situados à esquerda ou sobre a reta x1 = 4)
2x2  12
 x1 = 0 e x2 = 6 (estão situados abaixo ou sobre a reta x2 = 6)
3x1 + 2x2  18  x1 = 6 e x2 = 9 (estão situados abaixo ou sobre a reta 3x1 + 2x2 = 18)
 Sistema cartesiano:
3º passo: determinar a solução. A função objetivo Z = 3x1 + 5x2 define um reta que pode ser
deslocada paralelamente no sentido do seu gradiente (garantindo o crescimento de Z) até se tornar
tangente à região admissível. Os pontos de tangência obtidos (um, nenhum ou uma infinidade)
correspondem aos pontos da região admissível (viável) que otimizam a função objetivo. Entre os pontos:
(0,2); (0,4); (0,6); (4,0); (4;3) e (2,6). O ponto ótimo é (2,6) onde Z = 36, pois a função objetivo é
maximizar o lucro.
Programação Matemática
16
2.3.2 Exemplo 2
Encontre o ponto ótimo e a solução ótima para o seguinte PPL:
Min Z = 2x1 + 5x2 sujeito a
x1 + x2  6
-x1 - 2x2  -18
x1, x2  0
Representação gráfica:
1º passo: construir um sistema de eixos cartesianos x1 e x2.
2º passo: identificar os valores de x1 e x2 que satisfaçam todas as restrições.
 Condições de não negatividade: os pontos x1 e x2 estão situados nos 1º quadrante
 Restrições:
x1 + x2  6
 x1 = 6 e x2 = 0 e x1 = 0 e x2 = 6
x1 + 2x2  18
 x1 = 18 e x2 = 9
OBS:
1. Nesse tipo de inequação (x1 + x2  6), sempre haverá dois pontos.

Sistema cartesiano:
vetor gradiente
região viável
3º passo: determinar a solução. Entre os pontos: (6,0); (0,6); (18,0) e (0,9).
Para calcular a solução ótima basta substituir o ponto ótimo na função objetivo 2x1 + 5x2.
O ponto ótimo é (6,0) e a solução ótima é Z = 12, pois a função objetivo é minimizar Z.
Importante:
 O conjunto de pontos que satisfazem todas as restrições é chamado de região viável
(admissível) ou conjunto de pontos viáveis (admissíveis).
 Se a função objetivo é de maximização o vetor gradiente cresce a partir da origem (0,0).
 Se a função objetivo é de minimização o vetor gradiente decresce em direção a origem (0,0).
Programação Matemática
17
2.3.3 Exemplo 3
Encontre o ponto ótimo e a solução ótima para o seguinte PPL:
Max Z = x1 + 3x2 sujeito a
x1 + x2  6
-x1 + 2x2  8
x1, x2  0
Representação gráfica:
1º passo: construir um sistema de eixos cartesianos x1 e x2.
2º passo: identificar os valores de x1 e x2 que satisfaçam todas as restrições.
 Condições de não negatividade: os pontos x1 e x2 estão situados nos 1º quadrante
 Restrições:
x1 + x2  6
 x1 = 6 e x2 = 0 e x1 = 0 e x2 = 6
-x1 + 2x2  8
 x1 = 0 e x2 = 4
OBS:
1. Nesse tipo de inequação (x1 + x2  6), sempre haverá dois pontos.

Sistema cartesiano:
vetor gradiente
região viável
3º passo: determinar a solução. Nesse caso, a solução ótima é obtida mediante a solução do
sistema linear.
x1 + x2 = 6
-x1 + 2x2 = 8
Para calcular a solução ótima basta substituir o ponto ótimo na função objetivo x1 + 3x2.
O ponto ótimo é (4/3,14/3) e a solução ótima é Z = 15,33; pois a função objetivo é maximizar Z.
Programação Matemática
18
2.4 Exemplos de anomalias
Apresentam-se a seguir os problemas de PL que apresentam anomalias (irregularidades) tais
como:
a) Problema ilimitado, não admite ótimo;
b) Problema limitado;
c) Problema com duas soluções ótimas ou mais, uma infinidade de soluções;
d) Problema infactível, não admite soluções.
Programação Matemática
19
Lista de Exercícios 2
1) Encontre o ponto ótimo e a solução ótima dos seguintes PPL:
a) Max Z = 3x1 + x2 sujeito a
x1 4
x2 10
4x1 + 2x2 24
x1, x2 0
b) Max Z = 3x1 + 5x2 sujeito a
2x1 + x2 2
x1 + 3x2 3
x1, x2 0
c) Min Z = 30x1 + 20x2 sujeito a
4x1 + x2 20
x1 + 2x2 10
x1 2
x1, x2 0
d) Max Z = 2x1 + 3x2 sujeito a
x1 + x2 50
2x1 20
3x2 30
2x1 + 3x2 70
x1, x2 0
e) Min Z = 2x1 + 3x2 sujeito a
x1 + 3x2 9
-x1 + 2x2 4
x1 + x2 6
x1, x2 0
f) Max Z = 2x1 + x2 sujeito a
-x1 + x2 1
x1 3
x2 2
x1, x2 0
g) Max Z = 2x1 + x2 sujeito a
-2x1 + x2 2
2x1 + x2 4
x1, x2 0
Programação Matemática
20
h) Min Z = 2x1 + x2 sujeito a
x1 1
x2 2
x1 - x2 2
x1, x2 0
i) Min Z = x1 sujeito a
-x1 + x2 2
x2 5
x1, x2 0
j) Min Z = x1 + x2 sujeito a
-2x1 + x2 2
x1 - 2x2 2
x1, x2 0
Programação Matemática
21
3. PROGRAMAÇÃO LINEAR
3.1 Introdução
O método simplex parte de uma solução inicial do problema, verificando se a mesma é ótima ou
não para o problema. Se não for ótima, então o simplex faz uma mudança de vértice (ou de ponto) que
seja adjacente ao ponto já pesquisado; verifica se este é ótimo; se for, está encerrada a pesquisa e tem-se o
ponto ótimo do problema; senão, parte para outro ponto adjacente a este e repete o mesmo processo.
Logo, o método simplex parte de uma solução inicial e faz uma pesquisa entre os pontos extremos
adjacentes de modo que possa aumentar o valor da função objetivo.
A Programação Linear usa um modelo matemático para descrever o problema. O termo linear
significa que todas as funções matemáticas do modelo são lineares. O termo programação não se refere a
programação de computadores, mas é um sinônimo de planejamento; é usado para indicar uma certa
lógica de procedimento a ser seguido.
Assim, a PL compreende o planejamento de atividades para atingir um resultado ótimo, isto é,
para atingir um resultado que alcance o objetivo especificado da melhor maneira possível entre todas as
alternativas viáveis prescritas no modelo matemático.
3.2 Desenvolvimento do modelo matemático
A forma geral de um PPL tem o seguinte modelo: determinar os valores das variáveis de decisão
x1, x2, ..., xn que maximiza a função linear:
Z = c1x1 + c2x2 + ... + cnxn
sujeito às restrições:
a11x1 + a12x2 + ... + a1nxn  b1
a21x1 + a22x2 + ... + a2nxn  b2
.
.
.
.
.
.
.
.
.
.
.
.
am1x1 + am2x2 + ... + amnxn  bm
x1, x2, ..., xn 0
Neste modelo aij, bi e cj são constantes dadas.
O modelo STANDART considera que:
 Em problemas de maximização:
 Todas as restrições são do tipo ;
 Todas as variáveis de decisão (x1, x2, ..., xn) são  0;
 Todos os termos bi (b1, b2, ..., bm) são  0.

Em problemas de minimização:
 Todas as restrições são do tipo ;
Programação Matemática
22
 Todas as variáveis de decisão (x1, x2, ..., xn) são  0;
 Todos os termos bi (b1, b2, ..., bm) são  0.
3.3 Interpretação do modelo
Dado n atividades competitivas, as variáveis de decisão (x1, x2, ..., xn) representam o nível destas
atividades.
Por exemplo, se cada atividade é a produção de certo produto então xj (j = 1, 2, ..., n) é o número
de unidades do j-ésimo produto a ser fabricado durante um certo período de tempo.
 A função objetivo Z é a medida de efetividade escolhida. Por exemplo: o lucro;
 Os coeficientes cj são os acréscimos no valor de Z, resultantes dos acréscimos unitários em xj;
 O número de recursos (que são limitados) é m, tal que as primeiras m desigualdades lineares
são correspondentes às restrições na disponibilidade destes recursos;
 A constante bi é a quantidade do recurso i disponível para a realização das m atividades;
 A constante aij é a quantidade do recurso i consumida por unidades da atividade j.
Deste modo, verificamos que o lado esquerdo das inequações representa o uso de casa recurso.
As restrições do tipo xj  0 (j = 1, 2, ..., n) que são as de não negatividade evitam a possibilidade
de se produzir, por exemplo, uma quantidade negativa de um certo produto.
A tabela a seguir resume os dados apresentados:
Recursos
1
2
.
.
.
m
Z/unidade
variável de decisão
Uso do recurso por unidade de atividade
1
2
... n
a11
a21
.
.
.
am1
c1
x1
a12
a22
.
.
.
am2
c2
x2
... a1n
... a2n
.
.
.
... amn
... cm
... xm
Quantidade
disponível do recurso
b1
b2
.
.
.
bm
3.4 Tipos de soluções
 Solução viável ou factível: é qualquer especificação de valores para as variáveis de decisão
que atenda a todas as restrições do problema. Correspondem aos pontos internos ou sobre os lados do
polígono das soluções viáveis;
 Solução ótima: solução viável que fornece o valor ótimo da função objetivo;
 Solução tipo vértice: corresponde a um vértice do polígono;
 Solução adjacente: duas soluções tipo vértice são adjacentes se o segmento que as une é um
dos lados do polígono;
 Valor ótimo: é o valor que a solução ótima fornece a função objetivo.
Programação Matemática
23
Considerações:
Em PPL, pode ocorrer que:



Haja uma só solução ótima;
Haja mais de uma solução (soluções múltiplas). Na prática, isto significa que o problema teria
uma infinidade de soluções ótimas. Quando acontecer tal fato, deve-se desconfiar do modelo,
pois encontrar um problema real com diferentes soluções ótimas é ideia;
Não existem soluções. Isto ocorre quando não existe solução viável ou quando as restrições
não impedem o crescimento de Z indefinidamente (região viável aberta).
3.5 Propriedades
Demonstra-se matematicamente que:
 Se existir uma única solução ótima ela corresponde a um vértice;
 O número de soluções tipo vértice é finito;
 Se um vértice fornece um valor para Z melhor que os valores obtidos pelos vértices que lhe
são adjacentes, então ela é ótima.
O método simplex consiste em pesquisar os vértices do polígono indo de um vértice para o seu
adjacente até encontrar aquele que forneça o valor ótimo para Z.
Programação Matemática
24
4. O MÉTODO SIMPLEX
O Método Simplex é uma técnica utilizada para se determinar, numericamente, a solução ótima de
um modelo de Programação Linear. Este método é um algoritmo.
Entende-se por algoritmo um processo em que se repete (processo iterativo) um procedimento
sistemático até chegar a um resultado
Em cada etapa, do início ao fim, o procedimento é uma iteração.
O algoritmo deve ter uma regra de partida (ou inicialização), um processo iterativo e uma regra
de parada, isto é, a partir de uma solução inicial procura-se atingir novas soluções (através de um
processo iterativo), procurando-se saber se atingiu a solução desejada determinando o ponto de parada. Se
a solução for ótima, então para, senão for, recomeça o processo.
4.1 Desenvolvimento do método
Para iniciar o método, deve-se colocar o problema sob forma mais conveniente que a forma geral.
Assim, se tivermos um problema na forma geral, precisamos colocá-lo na forma canônica para então
aplicarmos o método.
4.1.1 Problema da forma geral
Um PPL apresenta-se na forma geral quando ele é modelado ficando da seguinte forma:
Z = c1x1 + c2x2 + ... + cnxn
sujeito às restrições:
a11x1 + a12x2 + ... + a1nxn  b1
a21x1 + a22x2 + ... + a2nxn  b2
.
.
.
.
.
.
.
.
.
.
.
.
am1x1 + am2x2 + ... + amnxn  bm
x1, x2, ..., xn 0
Exemplo:
Max Z = 3x1 + 5x2
x1  4
x2  6
3x1 + 2x2  18
x1, x2 0
Programação Matemática
25
4.1.2 Problema na forma canônica
Colocar um problema na forma canônica significa deixá-lo em condições de aplicar o método
simplex, ou seja, ter uma solução básica inicial que nos permitirá iniciar a resolução do primeiro tableau
(quadro) do simplex. Cada restrição do problema terá uma variável na base do simplex. Na solução inicial
as variáveis básicas serão compostas pelas variáveis de folga e/ou artificial tendo em vista que as
variáveis de excesso nunca estarão na base devido às restrições de não negatividade. Neste caso, sempre
que acrescentarmos uma variável de excesso à restrição devemos acrescentar também uma variável
artificial.
Para colocarmos um problema na forma canônica basta acrescentarmos a ele as variáveis de folga
e/ou variáveis de excesso e artificiais e/ou variáveis artificiais. Assim,
 Acrescentam-se variáveis artificiais quando temos restrições de igualdade do tipo (=);
 Acrescentam-se variáveis de folga quando temos restrições de desigualdade do tipo ()
transformando as restrições de desigualdade em restrições de igualdade;
 Acrescentam-se variáveis de excesso e artificiais quando temos restrições de desigualdade
do tipo () transformando as restrições de desigualdade em restrições de igualdade.
Descreve-se a seguir cada um dos casos apresentados.
Se tivermos um problema com uma restrição de igualdade, basta apenas acrescentar uma variável
artificial à restrição para que esta restrição tenha variável básica e, assim, fique na forma desejada
(canônica). Indicaremos uma variável artificial por .
Exemplo: x1 + x2 = 4
Solução: x1 + x2 +
=4
Se tivermos um problema com uma restrição de desigualdade do tipo (), basta apenas acrescentar
uma variável de folga à restrição para que esta restrição tenha variável básica e, assim, fique na forma
desejada (canônica). Indicaremos uma variável de folga por , sendo i igual ao índice da última
variável do problema mais 1.
Exemplo: x1 + x2  4
Solução: x1 + x2 +
=4
Se tivermos um problema com uma restrição de desigualdade do tipo (), precisamos acrescentar
uma variável de excesso. Indicaremos uma variável de excesso por - , sendo i igual ao índice da
última variável do problema mais 1. Para resolver o problema de negatividade, acrescenta-se além da
variável de excesso uma variável artificial.
Exemplo: x1 + x2  4
Solução: x1 + x2 -
+
=4
Exemplo:
Max Z = 3x1 + 5x2
x1  4
x2  6
3x1 + 2x2  18
x1, x2 0
Programação Matemática
26
Solução:
O novo modelo do problema será:
Max Z -3x1 - 5x2 + 0x3 + 0x4 + 0x5 = 0
x1 + x3 = 4
x2 + x4 = 6
3x1 + 2x2 + x5 = 18
x1, x2, x3, x4, x5 0
Este é ponto de partida do método simplex.
O novo sistema tem 5 variáveis 2 a mais que o número de restrições. Ao representar este sistema
em forma de matriz aumentada será fácil identificar uma solução básica inicial viável em que as
variáveis básicas serão as variáveis de folga e as variáveis de decisão serão as variáveis não básicas.
Esta solução básica inicial é o ponto de partida do método simplex.
x1 x2 x3 x4 x5 b
1 0 1 0 0 4
0 1 0 1 0 6
3 2 0 0 1 18
Variáveis básicas: x3 = 4, x4 = 6 e x5 = 18
Variáveis não básicas: x1 = 0 e x2 = 0
A função objetivo vale zero, pois está em função de x1 e x2.
Qual é a ideia básica do simplex?
A partir de uma solução básica inicial vai-se procurando uma nova solução básica que de um
maior valor para a função objetivo até chegar à solução ótima. Cada nova solução básica é obtida da
anterior substituindo uma variável não básica que “entra” na nova base no lugar de uma que “sai” da base.
A cada nova solução básica deve-se atualizar o valor da função objetivo Z.
Lista de Exercícios 3
1) Escreva os problemas de PL na forma canônica:
a) Max Z = 2x1 + x2 sujeito a
-x1 + x2 = 1
x1 3
x2 2
x1, x2 0
c) Max Z = x2 sujeito a
-x1 + x2 1
x2 2
x1, x2 0
b) Max Z = 2x1 + x2 sujeito a
-2x1 + x2 2
2x1 + x2 = 4
x1, x2 0
d) Min Z = 2x1 + x2 sujeito a
x1 1
x2 2
x1 - x2 2
x1, x2 0
Programação Matemática
27
e) Max Z = 2x1 + x2 sujeito a
x1 3
x2 2
x1 - x2 1
x1, x2 0
i) Min Z = x1 + x2 sujeito a
-2x1 + x2 2
x1 - 2x2 2
x1, x2 0
f) Min Z = x1 sujeito a
-x1 + x2 2
x2 5
x1, x2 0
j) Max Z = x1 + x2 sujeito a
-2x1 + x2 2
x1 - 2x2 2
x1 + x2 4
x1, x2 0
g) Max Z = x1 + 2x2 sujeito a
x1 - x2 0
-3x1 + 3x2 6
x1, x2 0
k) Max Z = x2 sujeito a
-x1 + x2 1
x1 3
x2 2
x1, x2 0
h) Max Z = x1 + 2x2 sujeito a
4x1 + x2 20
x1 + 2x2 20
x1 + 2x2 10
x1 2
x1, x2 0
l) Max Z = 3x1 - x2 sujeito a
2x1 + x2 2
x1 + 3x2 3
x2 4
x1, x2 0
4.2 Algoritmo do método simplex
No primeiro caso, vamos aplicar o método simplex em problemas de PL que exigem o acréscimo
das variáveis de folga. Os demais casos são tratados como casos especiais do método simplex que serão
estudados na próxima seção.
Para um problema na forma Standart, coloque as restrições sob a forma de igualdade
acrescentando variáveis de folga e faça Z = 0. Em seguida, construa um quadro inicial do tipo:
Quadro
inicial
EQ.
Z
1
.
.
.
m
V.B.
xn+1
.
.
.
xn+m
x1
-c1
a11
.
.
.
am1
x2
-c2
a12
.
.
.
am2
...
...
...
...
...
...
...
Variáveis de folga
xn
xn+1 ...
xn+m
-cn
0
...
0
a1n
1
...
0
.
.
...
.
.
.
...
.
.
.
...
.
amn
0
...
1
b
0
b1
.
.
.
bm
Para efetuar uma iteração analise o quadro e:
 Identifique a coluna do elemento mais negativo na equação Z;
 Divida os 2os membros de cada equação de restrição (coluna b) pelos elementos positivos
da coluna selecionada. O que der menor quociente será o pivô;
 A variável da linha do pivô “sai” da base e a variável da coluna do pivô “entra” na base;
Programação Matemática
28
 Efetue operações elementares de modo que a coluna da variável que “entra” fique com a
mesma configuração da coluna da variável que “sai”;
 O pivô deve ficar igual a 1 e os demais elementos da coluna do pivô devem ficar igual a
zero. Para isto deve-se multiplicar a linha do pivô por um número múltiplo da linha do pivô e somar com
a linha que se deseja modificar.
 PARE, quando todos os elementos da linha da função objetivo forem maiores que zero.
Caso contrário, continue o processo.
4.2.1 Regra de partida
Introduzimos as variáveis de folga (x3, x4 e x5) em cada uma das restrições. As variáveis de
decisão (x1 e x2) são não básicas e, portanto, iguais a zero. Enquanto que, as variáveis de folga são as
variáveis básicas iniciais.
Tomamos como exemplo o seguinte problema na forma canônica:
Max Z -3x1 - 5x2 + 0x3 + 0x4 + 0x5 = 0
x1 + x3 = 4
x2 + x4 = 6
3x1 + 2x2 + x5 = 18
x1, x2, x3, x4, x5 0
Para a solução do problema usa-se uma tabela. Em vez de trabalhar com as equações, trabalha-se
com os coeficientes das variáveis e os termos independentes da seguinte forma:
Quadro
inicial
EQ.
Z
1
2
3
V.B.
x3
x4
x5
x1
-3
1
0
3
x2
-5
0
1
2
x3
0
1
0
0
x4
0
0
1
0
x5
0
0
0
1
b
0
4
6
18
Na coluna V.B. (variável básica) está indicada a variável básica correspondente a cada operação
de restrição. A linha Z leva em conta a forma canônica: Z -3x1 - 5x2 = 0.
Neste caso a solução básica é: x1 = 0, x2 = 0, x3 = 4, x4 = 6 e x5 = 18.
É possível assinalar sempre uma matriz base (matriz identidade) para o sistema de restrições.
4.2.2 Regra de parada
A solução básica será ótima se, e somente se, na equação da função objetivo Z do quadro simplex
todo o coeficiente é  0. Pare. Caso contrário, repita o processo para obter uma nova solução básica.
Observe que, no quadro inicial temos na equação Z dois coeficientes negativos indicando que a
solução não é ótima. Então usa-se o processo iterativo.
4.2.3 Processo iterativo
Este processo visa a mudança de base, isto é, uma das variáveis não básicas (x1 ou x2) deve
“entrar” no lugar de uma das variáveis básicas (x3, x4 ou x5) que “sai”.
Programação Matemática
29

Determinação da variável que “entra” na base:
Deve ser aquela variável que mais rapidamente aumenta o valor de Z, quando Z começar a crescer
a partir de seu valor inicial zero. De acordo com o exemplo, Z -3x1 - 5x2 = 0, usa-se a variável que tiver o
coeficiente negativo maior na equação Z. Neste caso, x2 representado pelo coeficiente -5.

Determinação da variável que “sai” da base:
Que variável deve sair para a entrada de x2? Observe que, a variável x2 ao entrar na base passará a
ter um valor positivo. Aquela que “sair” da base passará a ter valor zero, pois ficará sendo não básica.
Nestes termos, quais das variáveis básicas (x3, x4 ou x5) sairá da base com a entrada de x2?
A regra é: divide-se os 2os membros (coluna b) das equações de restrições pelos coeficientes
positivos da coluna da variável que “entra” na base. O que der menor quociente será chamado de pivô. A
linha e a coluna a que pertencem serão designados, respectivamente, de linha e coluna do pivô. Então, a
variável que representa a coluna do pivô “entra” na base e a variável que se refere a linha do pivô “sai” da
base.
Vejamos no quadro simplex como fica:
EQ.
Z
1
2
3
Quadro
inicial
V.B.
x3
x4
x5
Entra
x2
-5
0
1
2
x1
-3
1
0
3
x3
0
1
0
0
x4
0
0
1
0
x5
0
0
0
1
b
0
4
6
18
quociente
6/1 = 6 (sai)
18/2 = 9
Pivô
OBS: 1. Não se consideram no cálculo dos quocientes, os elementos da coluna da variável que “entra” na
base que tenham valores iguais a zero ou negativos. 2. De acordo com o quadro simplex, x2 “entra” na
base e x4 “sai” da base. O pivô é o coeficiente localizado na interseção da variável que “entra” na base
(coluna do pivô) com a variável que “sai” da base (linha do pivô). Neste caso, o pivô é 1.

Determinação da nova solução básica:
Uma vez escolhidas a variável que “entra” e a que “sai” da base faz-se a mudança de base, onde a
coluna da variável que “entra” deve ficar com a configuração da coluna da variável que “sai”, isto é, o
elemento pivô deve ficar igual a 1 e todos os demais elementos da coluna devem ficar iguais a zero. Em
seguida, efetuam-se operações elementares convenientes.
Com as operações realizadas, o novo quadro ficaria:
Quadro I
EQ.
Z
1
2
3
V.B.
x3
x2
x5
Entra
x1
-3
1
0
3
x2
0
0
1
0
x3
0
1
0
0
x4
5
0
1
-2
x5
0
0
0
1
b
30
4
6
6
quociente
4/1 = 4
6/3 = 2
Pivô
Foi atingido o valor ótimo de Z? Não, pois ainda temos um coeficiente negativo na linha Z que se
refere a variável não básica x1.
Programação Matemática
30
Assim, novamente aplica-se o método gerando-se um novo quadro.
Quadro
II
EQ.
Z
1
2
3
V.B.
x3
x2
x1
x1
0
0
0
1
x2
0
0
1
0
x3
0
1
0
0
x4
3
2/3
1
-2/3
x5
1
-1/3
0
1/3
b
36
2
6
2
quociente
-
Como não existe nenhum coeficiente negativo na equação Z, atingimos o valor ótimo. Pare!
Solução: x1 = 2, x2 = 6, x3 = 2, x4 = 0, x5 = 0 e Z = 36.
Observações importantes:
1. Em cada nova solução fica sempre caracterizada a matriz identidade, embora as colunas não estejam
necessariamente nesta ordem.
1 0 0
0 1 0
0 0 1
2. As variáveis de folga são sempre básicas no quadro inicial.
3. Na linha da função objetivo (Z) os coeficientes das variáveis básicas são sempre iguais a zero.
Lista de Exercícios 4
1) Aplicando o método simplex resolva os seguintes exercícios:
a) Max Z = x1 + 5x2 sujeito a
2x1 + x2 10
x1 + 2x2 10
x1, x2 0
b) Max Z = 5x1 + 2x2 sujeito a
x1 3
x2 4
x1 + 2x2 9
x1, x2 0
c) Max Z = x1 + 3x2 sujeito a
x1 + 2x2 10
x2 4
x1, x2 0
d) Max Z = 5x1 + 7x2 sujeito a
2x1 + 3x2 12
3x1 + x2 12
x1, x2
0
e) Max Z = 5x1 + 2x2 sujeito a
x1 3
x2 12
x1 + 2x2 9
x1, x2 0
f) Max Z = 2x1 + x2 sujeito a
-x1 + 2x2 4
3x1 + 5x2 15
2x1 - 3x2 6
x1, x2 0
g) Max Z = 5x1 + 3x2 sujeito a
3x1 + 5x2 15
5x1 + 2x2 10
x1, x2 0
Programação Matemática
31
5x1 + 3x2
x1 + x2
x1, x2
h) Max Z = 6x1 + 10x2 sujeito a
3x1 + 5x2 15
5x1 + 2x2 10
x1, x2 0
270
200
0
k) Max Z = 200x1 + 50x2 sujeito a
3x1 + 2x2 20
4x1 12
2x1 + 5x2 18
x1, x2 0
i) Max Z = 20x1 + 25x2 sujeito a
2x1 + 3x2 200
4x1 + 3x2 240
x1 100
x2 80
x1, x2 0
l) Max Z = 5x1 + 8x2 sujeito a
10x2 30
10x1 + 20x2 70
20x1 + 10x2 80
30x1 + 10x2 130
12x1 + 9x2 120
15x1 + 10x2 100
x1, x2 0
j) Max Z = 400x1 + 300x2 sujeito a
10x1 + 15x2 444
20x1 + 20x2 780
5. CASOS ESPECIAIS DO MÉTODO SIMPLEX
Programação Matemática
32
Nesta seção apresentam-se alguns casos especiais que podem ocorrer nos PPL, tais como:




Empate na entrada;
Empate na saída;
Função objetivo ilimitada;
Soluções ótimas múltiplas.
Estas situações podem ocorrer em nosso modelo Standart, isto é, aquele que considera: problema
de maximização, todas as restrições do tipo () e todas as variáveis de decisão maiores ou iguais a zero.
5.1 Empate na entrada
Quando houver empate na escolha da variável que “entra” na base deve-se tomar a decisão
arbitrariamente. A única consequência é que se pode escolher um caminho mais curto para chegar à
solução ótima.
Por exemplo, se a função objetivo fosse Z = 3x1 + 3x2 no quadro inicial teríamos os coeficientes -3
e -3 para x1 e x2 havendo empate na escolha da variável que “entra” na base. Neste caso, se escolhermos
x1 para “entrar” na base, a solução ótima será atingida com uma iteração a mais do que se escolhêssemos
x2 para “entrar” na base.
5.2 Empate na saída
Quando houver empate entre 2 ou mais variáveis básicas para “sair” da base pode ocorrer que:
 Todas as variáveis básicas empatadas chegam à zero simultaneamente, à medida que a
variável que entra aumente de valor, logo, as variáveis que não são escolhidas para sair da base também
terão um valor zero na nova solução chamada degenerada.
 Quando se escolhe uma variável degenerada para sair da base na nova iteração a ser feita a
que entrar no lugar dela continua igual a zero e o valor de Z não se altera. Se é possível que Z continue
com o mesmo valor, em lugar de aumentar a cada iteração, é possível também formar-se um ciclo (loop),
repetindo-se a mesma sequencia de soluções. Embora teoricamente isto possa vir a ocorrer, na prática não
se encontra nenhum problema que recaísse neste loop.
Em consequência, escolhe-se arbitrariamente a variável que sai quando houver empate na saída.
Exemplo:
Max Z = 5x1 + 2x2 sujeito a
x1 3
x2 4
4x1 + 3x2 12
x1, x2 0
EQ.
Z
V.B.
-
Entra
x1
-5
x2
-2
x3
0
x4
0
Programação Matemática
x5
0
b
0
quociente
-
33
Quadro
inicial
1
2
3
x3
x4
x5
1
0
4
0
1
3
1
0
0
0
1
0
0
0
1
3
4
12
3/1 = 3 (sai)
12/4 = 3 (sai)
No quadro inicial, há empate na saída entre x3 e x5. Escolhemos x3. Neste caso, x5 fica igual a zero
no quadro I. Como ainda temos coeficiente negativo na equação Z faz-se uma nova iteração. Em seguida,
escolhemos x5 para sair da base e a variável x2 entra no lugar de x5. Se tivéssemos escolhido x5 para sair
no quadro inicial chegaríamos ao mesmo resultado, mas com uma iteração a menos.
Solução final: x1 = 3, x2 = 0, x3 = 0, x4 = 4, x5 =0 e Z = 15.
OBS:
1. Quando uma das variáveis básicas é igual a zero diz-se que a solução é degenerada.
5.3 Função objetivo ilimitada
Quando nenhuma variável pode sair da base, isto é, quando todos os coeficientes da coluna da
variável que deve entrar na base são negativos ou iguais a zero tem-se uma função objetivo ilimitada. Isto
significa que a variável que entra poderia aumentar indefinidamente sem diminuir o valor das variáveis
básicas presentes na solução. Nesta hipótese, pode-se concluir ter havido algum erro na formulação do
modelo matemático ou algum erro de cálculo ao aplicar o simplex.
5.4 Soluções ótimas múltiplas
Quando um problema tiver mais de uma solução ótima ao menos uma das variáveis não básicas
tem coeficiente zero na equação Z, pois ao se aumentar qualquer destas variáveis não se alteraria o valor
de Z. Estas novas soluções podem ser encontradas com novas iterações, escolhendo cada vez uma
variável que entra.
Exemplo:
Max Z = 3x1 + 2x2 sujeito a
x1 4
x2 6
3x1 + 2x2 18
x1, x2 0
No quadro II verifica-se que x3, que é a variável não básica tem coeficiente zero na equação Z.
Assim, tem-se a solução ótima com Z = 18, x1 = 4 e x2 = 3.
No entanto, se fizermos uma iteração extra, fazendo x3 “entrar” na base, encontrar-se-á uma nova
solução ótima, que não altera a linha do Z. Esta nova solução é: Z = 18, x1 = 2 e x2 = 6.
Poderíamos ainda colocar na base x4, que também tem coeficiente zero na linha do Z, no lugar de
x3 e com mais uma iteração extra, obteríamos a seguinte solução ótima: Z = 18, x1 = 4 e x2 = 3.
5.5 Outras formas de modelo
5.5.1 Problemas de minimização
Programação Matemática
34
A melhor maneira de aplicar o mesmo algoritmo é transformar o problema de minimização em um
problema de maximização. Assim, minimizar Z é equivalente a maximizar –Z.
Por exemplo: Min Z = 2x1 – 7x2 equivale a Max -Z = -2x1 + 7x2.
5.5.2 Modificações nas restrições
Num problema Standart com todas as restrições do tipo () há uma solução básica inicial óbvia, na
qual as variáveis de folga são as variáveis básicas (na base) e as variáveis de decisão são as variáveis não
básicas.
Em termos gráficos, esta solução básica inicial corresponde à origem, ou seja, x1 = 0 e x2 = 0.
Quando houver restrições de igualdade (=) ou restrições de desigualdade do tipo () esta solução
básica inicial não poderá ser obtida só com a introdução das variáveis de folga. Para estes casos, aplica-se
o método de duas fases.
O método de duas fases consiste em:
1ª fase: resolver o sistema onde aparece a função objetivo artificial W até excluir a variável
artificial da base, obtendo-se W = 0.
2ª fase: prosseguir com o algoritmo simplex, excluindo a linha da função objetivo artificial (FOA)
e a coluna que contém a variável artificial.
Restrições de igualdade
 Para obter a solução básica inicial introduz-se uma variável artificial em cada restrição de
igualdade.
 Cria-se uma FOA W igual a soma das variáveis artificiais, onde W deve ser minimizada.
 Combina-se W convenientemente com as equações de restrições que contém variáveis
artificiais de modo a eliminá-las na equação W.
 Monta-se o quadro inicial do problema, incluindo a FOA W e a função objetivo Z.
 Desenvolve-se a 1ª fase do método de duas fases até W = 0. Neste ponto, as variáveis
artificiais terão saído da base, constituindo o final da 1ª fase.
 Eliminando a linha da FOA e as colunas das variáveis artificiais, inicia-se a 2ª fase do método
de duas fases, prosseguindo com o algoritmo do método simplex.
OBS:
1. Se houver mais de uma variável artificial para completar a solução básica inicial, a FOA W será a soma
dessas variáveis artificiais. Neste caso, deve-se combinar convenientemente a equação de –W com as
equações de restrições que contém as variáveis artificiais para montar o primeiro quadro da 1ª fase do
método de duas fases.
2. Para o mínimo de W ser zero, todas as variáveis artificiais terão que ser nulas. Se o mínimo de W for
diferente de zero é porque o sistema de equações original não tem solução compatível.
Exemplo:
Max Z = 3x1 + 5x2 sujeito a
x1 4
Programação Matemática
35
2x2 12
3x1 + 2x2 = 18
x1, x2 0
Como o problema apresenta uma restrição de igualdade deve ser resolvido inserindo uma variável
artificial nessa restrição. Ficando:
Max Z -3x1 - 5x2 = 0
x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + = 18
x1, x2, x3, x4,
0
O método consiste em, inicialmente, introduzir uma função objetivo artificial W formada pela
variável artificial inserida a ser minimizada. Assim:
Min W =
Como
não pode ser negativa, seu valor mínimo será zero, então W também será igual a zero e
terá atingido seu valor mínimo. Então, a função objetivo artificial é essa:
–W +
=0
Para fazer com que
tenha coeficiente = zero na equação da função objetivo artificial faz-se:
Eq. da função objetivo artificial – Eq. da restrição que contém a variável artificial ( )
–W +
=0
– (3x1 + 2x2 +
= 18)
–W – 3x1- 2x2 = -18
Na 1ª fase, além da FOA é mantida a função objetivo Z para que tenhamos o seu valor.
1ª fase:
Quadro
inicial
1ª fase:
Quadro I
1ª fase:
Quadro
II
EQ.
–W
Z
1
2
3
–W
Z
1
2
3
–W
Z
1
2
3
V.B.
x3
x4
x1
-3
-3
1
0
3
x2
-2
-5
0
2
2
x3
0
0
1
0
0
x4
0
0
0
1
0
0
0
0
0
1
b
-18
0
4
12
18
quociente
4/1 = 4 (sai)
18/3 = 6
Como não pode ser negativa o seu valor mínimo será igual a zero. Assim, se achar o mínimo de
W igual a zero ter-se-á excluído da base a variável artificial .
Programação Matemática
36
Com W = 0, chegamos ao fim da 1ª fase. Agora é que entramos na região viável do problema
original.
Eliminando a linha da função objetivo artificial e a coluna da variável artificial
na 2ª fase.
2ª fase:
Quadro
inicial
2ª fase:
Quadro I
EQ.
Z
1
2
3
Z
1
2
3
V.B.
x1
x2
x3
x4
b
, prosseguimos
quociente
Restrições de desigualdade do tipo maior ou igual
Quando houver restrição do tipo () introduz-se uma variável de excesso na restrição.
Exemplo: 3x1 + 2x2  18 acrescentando-se uma variável de excesso ficaria 3x1 + 2x2 + x3 = 18.
Mas para termos uma variável básica nesta equação acrescenta-se também uma variável
artificial. Assim, esta restrição é escrita da seguinte forma: 3x1 + 2x2 + x3 + = 18.
Tanto em restrições de igualdade como em restrições de desigualdade do tipo () aplica-se o
método de duas fases, explicado anteriormente.
Exemplo:
Max Z = 3x1 + 5x2 sujeito a
x1 4
2x2 12
3x1 + 2x2 18
x1, x2 0
Introduziremos variáveis de folga para restrições do tipo () e uma variável de excesso e artificial
para a restrição do tipo (), o modelo fica:
Max Z -3x1 - 5x2 = 0
x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 – x5 + = 18
x1, x2, x3, x4, x5,
0
O método consiste em, inicialmente, introduzir uma função objetivo artificial W formada pela
variável artificial inserida a ser minimizada. Assim:
Min W =
Como
não pode ser negativa, seu valor mínimo será zero, então W também será igual a zero e
terá atingido seu valor mínimo. Então, a função objetivo artificial é essa:
–W +
=0
Programação Matemática
37
Para fazer com que
tenha coeficiente = zero na equação da função objetivo artificial faz-se:
Eq. da função objetivo artificial – Eq. da restrição que contém a variável artificial ( )
–W +
=0
– (3x1 + 2x2 – x5 +
= 18)
–W – 3x1- 2x2 + x5 = -18
1ª fase:
Quadro
inicial
1ª fase:
Quadro I
1ª fase:
Quadro
II
EQ.
–W
Z
1
2
3
–W
Z
1
2
3
–W
Z
1
2
3
V.B.
x3
x4
x1
-3
-3
1
0
3
x2
-2
-5
0
2
2
x3
0
0
1
0
0
x4
0
0
0
1
0
x5
1
0
0
0
-1
0
0
0
0
1
b
-18
0
4
12
18
quociente
4/1 = 4 (sai)
18/3 = 6
Como W = 0, fim da 1ª fase.
Eliminando a linha da função objetivo artificial e a coluna da variável artificial
na 2ª fase.
2ª fase:
Quadro
inicial
2ª fase:
Quadro I
2ª fase:
Quadro
II
EQ.
Z
1
2
3
Z
1
2
3
Z
1
2
3
V.B.
x1
x2
x3
x4
Em resumo:
Tipo de restrição
Variável a acrescentar
Programação Matemática
b
, prosseguimos
quociente
38

=

Folga
Artificial
Excesso e artificial
Lista de exercícios 5
1) Aplique o método de duas fases nos casos especiais a seguir:
a) Max Z = x1 + 3x2 sujeito a
x1 + 2x2 10
x2 = 4
x1, x2 0
b) Max Z = x1 + 2x2 sujeito a
-x1 + 3x2 9
x1 - 2x2 0
2x1 + x2 10
2x1 + x2 5
x1, x2 0
c) Max Z = x1 + 3x2 sujeito a
4x1 + x2 30
10x1 + 2x2 10
x1, x2 0
d) Max Z = 5x1 + 2x2 sujeito a
x1 = 3
x2 4
x1 + 2x2 = 9
x1, x2 0
e) Max Z = 2x1 + 3x2 sujeito a
x1 + x2 10
2x1 + x2 16
x1, x2 0
f) Max Z = 3x1 – x2 – 2x3 sujeito a
-4x1 + x2 + 2x3 3
x1 – 3x2 + x3 11
-2x1 + x3 = 4
x1, x2, x3 0
2) O quadro abaixo representa uma das iterações do método simplex para um problema Standart. Pede-se:
a) Identifique as variáveis básicas;
Programação Matemática
39
b) Identifique a solução correspondente, isto é, os valores das variáveis e de Z;
c) A solução é ótima? Por quê?
EQ.
Z
1
2
3
4
V.B.
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
-4
1
0
7/2
2
x4
5
0
1/2
-3/2
-1
x5
0
0
0
1
0
x6
0
0
0
0
1
b
1280
80
40
40
20
3) Cada um dos quadros abaixo representa o final de uma iteração de um problema de maximização.
Identifique se a solução é ótima, ou degenerada ou se o problema apresenta soluções ótimas múltiplas.
Justifique a sua resposta.
a)
EQ.
Z
1
2
V.B.
x1
x2
x1
0
1
0
x2
0
0
1
x3
2
1
2
x4
0
2
1
b
2
1
EQ.
Z
1
2
V.B.
x1
x2
x1
0
1
0
x2
0
0
1
x3
-3
1
2
x4
1
2
1
b
0
5
b)
Programação Matemática
40
6. VALOR MARGINAL (PREÇO SOMBRA)
O método simplex além de encontrar a solução ótima proporciona outra informação valiosa para a
análise posterior do problema denominado de valor marginal ou preço sombra.
O preço sombra do recurso i ( ) mede o valor marginal deste recurso, isto é, quanto varia a
função objetivo pelo acréscimo unitário do recurso i.
O método simplex mostra que este preço sombra corresponde ao coeficiente da i-ésima variável de
folga na equação Z do quadro final do simplex.
Seja o problema:
Max Z = 3x1 + 5x2 sujeito a
x1 4
2x2 12
3x1 + 2x2 18
x1, x2 0
cujo o quadro final do simplex foi:
EQ.
Z
1
2
3
V.B.
x3
x2
x1
x1
0
0
0
1
x2
0
0
1
0
x3
0
1
0
0
x4
3/2
1/3
1/2
-1/3
x5
1
-1/3
0
1/3
b
36
2
6
2
Assim, conforme o exemplo tem-se: = 0; = 3/2 e = 1. Isso significa que, se aumentarmos
em uma unidade a disponibilidade do recurso 1 não haverá contribuição para melhorar o valor de Z; por
outro lado, se aumentarmos em uma unidade a disponibilidade do recurso 2, os lucros da função objetivo
aumentam 3/2 u.m..
O preço sombra representa então o preço unitário (máximo) que se está disposto a pagar com a
finalidade de aumentar a disponibilidade de um determinado recurso em uma unidade.
Pode-se demonstrar também, que o valor ótimo da função objetivo será igual ao somatório dos
preços sombras ( ) multiplicado pelas disponibilidades dos recursos (bi), isto é,
Seguindo o exemplo tem-se:
Programação Matemática
41
Lista de exercícios 6
1) Dados os problemas a seguir com os seus respectivos quadros de solução ótima, determine a variação
da função objetivo de cada problema quando aumentarmos em uma unidade a disponibilidade do recurso
1, a disponibilidade do recurso 2 e a disponibilidade do recurso 3.
a) Max Z = 3x1 + 5x2 sujeito a
x1 5
2x2 13
3x1 + 2x2 19
x1, x2 0
EQ.
Z
1
2
3
V.B.
x3
x2
x1
x1
0
0
0
1
x2
0
0
1
0
x3
0
1
0
0
x4
3/2
1/3
1/2
-1/3
x5
1
-1/3
0
1/3
b
38,5
2
6
2
x2
0
0
0
1
x3
0
1
3/2
-3/2
x4
0
0
1
0
x5
1
0
-1/2
1/2
b
18
4
3
3
x2
0
0
1
0
x3
0
1
0
0
x4
3
1/6
1
-2/3
x5
1
-1/3
0
1/3
b
36
2
6
2
b) Max Z = 3x1 + 2x2 sujeito a
x1 4
x2 6
3x1 + 2x2 18
x1, x2 0
EQ.
Z
1
2
3
V.B.
x1
x4
x2
x1
0
1
0
0
c) Max Z = 3x1 + 5x2 sujeito a
x1 4
x2 6
3x1 + 2x2 18
x1, x2 0
EQ.
Z
1
2
3
V.B.
x3
x2
x1
x1
0
0
0
1
Programação Matemática
42
7. PROBLEMA DUAL
Problema na forma primal:
Max Z = c1x1 + c2x2 + ... + cnxn sujeito às restrições:
a11x1 + a12x2 + ... + a1nxn  b1
a21x1 + a22x2 + ... + a2nxn  b2
.
.
.
.
.
.
.
.
.
.
.
.
am1x1 + am2x2 + ... + amnxn  bm
x1, x2, ..., xn 0
Problema na forma dual:
Min Z = b1y1 + b2y2 + ... + bmym sujeito às restrições:
a11y1 + a21y2 + ... + am1ym c1
a12y1 + a22y2 + ... + am2ym c2
.
.
.
.
.
.
.
.
.
.
.
.
a1ny1 + a2ny2 + ... + amnym cn
y1, y2, ..., ym 0
Observe que:


Se o primal tem n variáveis de decisão e m restrições;
O dual terá n restrições e m variáveis de decisão.
7.1 Exemplo 1
Primal
Dual
Max Z = 5x1 + 3x2 sujeito a
6x1 + 2x2 36
5x1 + 5x2 40
2x1 + 4x2 28
x1, x2 0
Min Z = 36y1 + 40y2 + 28y3 sujeito a
6y1 + 5y2 + 2y3 5
2y1 + 5y2 + 4y3 3
y1, y2, y3 0
7.2 Exemplo 2
Primal
Max Z = x1 + x2 sujeito a
-x1 + x2 + x3 2
-2x1 + x2 - x3 1
x1, x2, x3 0
Dual
Min Z = 2y1 + y2 sujeito a
-y1 - 2y2 1
y1 + y2 1
y1 - y2 0
y1, y2 0
A teoria da dualidade demonstra que:
Programação Matemática
43
1) O valor ótimo de Z (chamaremos de Z*) é igual ao valor ótimo de W (W*) onde:
onde
e
são os valores do último quadro do simplex.
2) As variáveis de decisão do primal correspondem às variáveis de folga do dual; as variáveis de
folga do primal correspondem às variáveis de decisão do dual.
3) Os valores ótimos das variáveis de decisão do dual correspondem aos valores dos coeficientes
das variáveis de folga do primal no quadro final do simplex.
4) Se na solução ótima encontrada uma variável de decisão do primal tem valor  de zero, a
variável de folga correspondente (ou de excesso) do dual será igual a zero; se uma variável de
folga (ou de excesso) do primal tem valor  de zero, a variável de decisão correspondente do
dual será igual a zero.
Exemplo:
Primal
Dual
Max Z = 5x1 + 2x2 sujeito a
x1 3
x2 4
x1 + 2x2 9
x1, x2 0
Variáveis de folga: x3, x4, x5
Quadro
inicial
Quadro
final
EQ.
Z
1
2
3
Z
1
2
3
Min Z = 3y1 + 4y2 + 9y3 sujeito a
y1 + y3 5
y2 + 2y3 2
y1, y2, y3 0
Variáveis de excesso: -y4, -y5
V.B.
x3
x4
x5
x1
x4
x2
-y4
x1
-5
1
0
1
0
1
0
0
-y5
x2
-2
0
1
2
0
0
0
1
y1
x3
0
1
0
0
4
1
1/2
-1/2
Solução primal: Z* = 21, x1 = 3, x2 = 3, x3 = 0, x4 = 1, x5 = 0
Solução dual: W* = 21, y1 = 4, y2 = 0, y3 = 1, y4 = 0, y5 = 0
Z* = W* = 21
Z* = c1 . x1 + c2 . x2 = 5 . 3 + 2 . 3 = 21
W* = b1 . y1 + b2 . y2 + b3 . y3 = 3 . 4 + 4 . 0 + 9 . 1 = 21
Programação Matemática
y2
x4
0
0
1
0
0
0
1
0
y3
x5
0
0
0
1
1
0
-1/2
1/2
b
0
3
4
9
21
3
1
3
44
OBS:
1. A solução de um problema primal fornece a solução do dual e vice-versa. Isto é importante porque:
a) possibilita que problemas de minimização sejam resolvidos em termos de maximização;
b) para problemas didáticos com apenas 3 variáveis de decisão, o dual terá apenas duas variáveis.
Lista de exercícios 7
1) Qual é a solução dual dos problemas a seguir dada a solução primal:
a) Max Z = 3x1 + 2x2 sujeito a
x1 4
x2 6
3x1 + 2x2 18
x1, x2 0
Quadro
final
EQ.
Z
1
2
3
V.B.
x1
x4
x2
x1
0
1
0
0
x2
0
0
0
1
x3
0
1
3/2
-3/2
x4
0
0
1
0
x5
1
0
-1/2
1/2
b
18
4
3
3
V.B.
x3
x2
x1
x1
0
0
0
1
x2
0
0
1
0
x3
0
1
0
0
x4
3
1/6
1
-2/3
x5
1
-1/3
0
1/3
b
36
2
6
2
b) Max Z = 3x1 + 5x2 sujeito a
x1 4
x2 6
3x1 + 2x2 18
x1, x2 0
Quadro
final
EQ.
Z
1
2
3
2) Os problemas a seguir estão na forma primal. Encontre a solução na forma primal utilizando o método
simplex e a seguir escreva-a na forma dual:
a) Max Z = x1 + 2x2 sujeito a
-x1 + x2 2
x1 + 2x2 8
x1, x2 0
Programação Matemática
45
b) Max Z = -x1 + 4x2 sujeito a
-x1 + 2x2 5
3x1 + 4x2 8
x1, x2 0
3) Os problemas a seguir estão na forma primal. Encontre a solução na forma dual utilizando o método
simplex e a seguir escreva-a na forma primal:
a) Min Z = 10x1 + 4x2 sujeito a
x1 1
2x1 + x2 3
x1, x2 0
b) Min Z = 4x1 + 6x2 + 18x3 sujeito a
x1 + 3x3 3
x2 + 2x3 2
x1, x2, x3 0
c) Min Z = 10x1 + 6x2 + 8x3 sujeito a
x1 + x2 + 2x3 2
5x1 + 3x2 + 2x3 1
x1, x2, x3 0
Programação Matemática
46
8. REFERÊNCIAS BIBLIOGRÁFICAS
ANDRADE, E. L. de. Introdução à pesquisa operacional: métodos e modelos para análise de decisões.
4. ed., Rio de Janeiro: LTC, 2009.
BREGALDA, P.; BORNSTEIN, C. Introdução à programação linear. Rio de Janeiro: Campus, 1983.
BRONSON, R. Pesquisa Operacional. São Paulo: McGraw-Hill, 1985.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. Rio de Janeiro: Campus,
1988.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões: para cursos de administração,
economia e ciências contábeis. 3. ed., Rio de Janeiro: Elsevier, 2007.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. 4. ed. São Paulo: Pearson
Prentice Hall, 2009.
PRADO, Darci. Programação linear. Belo Horizonte: DG, 1999.
PUCCINI, A. de L.; PIZZOLATO, N. D. Programação linear. 2. ed. Rio de Janeiro: LTC, 1989.
TAHA, H. A. Pesquisa Operacional. 8. ed., São Paulo: Pearson Prentice Hall, 2008.
WAGNER, H. M. Pesquisa operacional. 2. ed., Rio de Janeiro: Prentice Hall do Brasil, 1986.
Programação Matemática