Manual IO 2020

Prévia do material em texto

m
um
ub
et
o8
@
gm
ai
l.c
om
m
um
ub
et
o8
@
gm
ai
l.c
om
– ? ? ? –
Alberto Chicafo Mulenga
Maputo, Moçambique
13 de Outubro de 2020
m
um
ub
et
o8
@
gm
ai
l.c
om
i
Prefácio
Este livro, com a denomicação Investigação Operacional - uma abordagem introdutória, é
um resumo de conteúdos que são leccionados nos cursos de licenciatura de diversas áreas
do conhecimento como Administração e Gestão de Empresas, Contabilidade e Auditoria,
Economia, Engenharia, Estat́ıstica, Informática, Matemática, entre outras. Esta versão
basicamente tem conteúdos relacionados à Programação linear. Assim, a definição da
investigação operacional sua caracterização, os métodos gráfico e simplex com as variantes
do método simplex de duas fases, método simplex de Grande M e o método simplex dual-
simplex, dualidade em programação linear, análise de sensibilidade em programação linear,
programação linear inteira, problemas de transporte e afectação, constituem os conteúdos
deste livro. Estes temas actualmente constituem os fundamentos da programação linear
onde o objectivo principal é a optimização das soluções empresariais no processo de
tomada de decisão tanto na alocação de recursos como para a minimização dos custos em
posśıveis investimentos sem deixar de lado a noção de solução viável. Em cada caṕıtulo,
são apresentados os conceitos teóricos com exemplos ilustrativos fazendo um total de
67 exemplos. No fim de cada caṕıtulo é apresentada uma lista de exerćıcios propostos
com indicação de soluções num total de 71 exerćıcios. No final do livro, estão algumas
referências que os interessados poderão ler para aprofundar os seus conhecimentos.
Alberto Mulenga
Maputo, 13 de Outubro de 2020
Typeset by LATEX 2ε
m
um
ub
et
o8
@
gm
ai
l.c
om
Conteúdo
Lista de Figuras v
Lista de Tabelas vii
1 Introdução 1
1.1 Definição de Investigação Operacional . . . . . . . . . . . . . . . . . . 1
1.2 Caracteŕısticas da investigação operacional . . . . . . . . . . . . . . . 4
1.3 Técnicas da investigação operacional . . . . . . . . . . . . . . . . . . 7
2 Programação linear 9
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Formulação dos problemas de programação linear . . . . . . . 10
2.1.2 Definição geral dos problemas de programação linear . . . . . 16
2.1.3 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Resolução dos problemas de programação linear pelo método gráfico . 22
2.2.1 Domı́nio das soluções admisśıveis . . . . . . . . . . . . . . . . 22
2.2.2 Procedimento do método gráfico . . . . . . . . . . . . . . . . . 30
2.2.3 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . 33
2.3 Resolução dos problemas de programação linear pelo método simplex 35
2.3.1 Variáveis de folga e de excesso . . . . . . . . . . . . . . . . . . 35
2.3.2 Procedimento do método simplex . . . . . . . . . . . . . . . . 38
2.3.3 Método simplex de duas fases . . . . . . . . . . . . . . . . . . 45
2.3.4 Método simplex de grande M . . . . . . . . . . . . . . . . . . 55
2.3.5 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . 64
ii
m
um
ub
et
o8
@
gm
ai
l.c
om
CONTEÚDO iii
3 Dualidade em programação linear 69
3.1 Transformação do problema primal para dual . . . . . . . . . . . . . 69
3.2 Interpretação económica das variáveis duais . . . . . . . . . . . . . . 73
3.3 Relações entre os valores óptimos do primal e do dual . . . . . . . . . 76
3.4 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4 Análise de sensibilidade em programação linear 89
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1.1 Propriedades operacionais entre o primal e dual . . . . . . . . 90
4.1.2 Método simplex dual - simplex . . . . . . . . . . . . . . . . . 94
4.2 Variação nas quantidades dos recursos . . . . . . . . . . . . . . . . . 100
4.3 Variação nos coeficientes da função objectivo . . . . . . . . . . . . . . 107
4.4 Variações nos coeficientes das actividades . . . . . . . . . . . . . . . . 111
4.5 Adição de uma nova variável . . . . . . . . . . . . . . . . . . . . . . . 114
4.6 Adição de uma nova restrição . . . . . . . . . . . . . . . . . . . . . . 116
4.7 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5 Programação linear inteira 125
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2 Método de bifurcação e limite . . . . . . . . . . . . . . . . . . . . . . 129
5.3 Método de corte de Gomory . . . . . . . . . . . . . . . . . . . . . . . 143
5.4 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6 Problemas de transporte e afectação 154
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.1.1 Formulação de um problema de transporte . . . . . . . . . . . 155
6.1.2 Métodos para a resolução dos problemas de transporte . . . . 160
6.2 Cálculo da primeira aproximação de solução . . . . . . . . . . . . . . 160
6.2.1 Método do canto noroeste . . . . . . . . . . . . . . . . . . . . 160
6.2.2 Método de custo mı́nimo (lúcro máximo) . . . . . . . . . . . . 164
6.2.3 Método de aproximação de Vogel . . . . . . . . . . . . . . . . 168
6.3 Teste e melhoramento de solução . . . . . . . . . . . . . . . . . . . . 175
6.3.1 Método de MODI para o teste de optimidade de solução . . . 176
m
um
ub
et
o8
@
gm
ai
l.c
om
CONTEÚDO iv
6.3.2 Método de Stepping Stone para o teste de optimidade de solução177
6.3.3 Procedimento para o melhoramento de solução . . . . . . . . . 177
6.4 Problemas de afectação e o método Húngaro . . . . . . . . . . . . . . 186
6.5 Exerćıcos propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7 Programação dinâmica 203
7.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.2 Recursividade progressiva e regressiva . . . . . . . . . . . . . . . . . . 208
7.3 Aplicações da programação dinâmica . . . . . . . . . . . . . . . . . . 218
7.4 Dificuldades da programação dinâmica . . . . . . . . . . . . . . . . . 218
7.5 Exerćıcios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Bibliografia 222
m
um
ub
et
o8
@
gm
ai
l.c
om
Lista de Figuras
1.1 Enfoques da investigação operacional . . . . . . . . . . . . . . . . . . 3
2.1 Domı́nio solução de sistema de inequações . . . . . . . . . . . . . . . 23
2.2 Domı́nio solução e pontos máximo e mı́nimo de F(x) . . . . . . . . . 24
2.3 Ilustração da resolução de um problema de maximização . . . . . . . 26
2.4 Ilustração da resolução de um problema de minimização . . . . . . . 29
2.5 Gráfico do exemplo 2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6 Gráfico do exemplo 2.10 . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1 Dominio solução de um problema de programação linear inteira . . . 127
5.2 Árvore binária ou decisão do exemplo 5.2 . . . . . . . . . . . . . . . . 134
5.3 Árvore binária para o exemplo 5.3 . . . . . . . . . . . . . . . . . . . . 137
5.4 Gráfico da primeira aproximação de solução do problema de programção
linear inteira, exemplo 5.4 . . . . . . . . . . . . . . . . . . . . . . . . 138
5.5 Gráficos dos subropblemas 1 e 2 do exemplo 5.4 . . . . . . . . . . . . 139
5.6 Gráficos dos subproblemas 1.1 e 1.2 do exemplo 5.4 . . . . . . . . . . 140
5.7 Gráfico da primeira aproximação do exemplo 5.5 . . . . . . . . . . . . 141
5.8 Gráficos dos subproblemas 1 e 2 do exemplo 5.5 . . . . . . . . . . . . 142
6.1 Diagrama de um problema de transporte . . . . . . . . . . . . . . . . 156
6.2 Representação da rede de transporte do exemplo 6.1 . . . . . . . . . . 159
6.3 Exemplos de alguns circuitos de avaliação. . . . . . . . . . . . . . . 176
6.4 Exemplificação de circuito de melhoramento de solução do exemplo 6.11179
7.1 Representação da rede do exemplo 7.1 . . . . . . . . . . . . . . . . . 205
v
m
um
ub
et
o8
@
gm
ai
l.c
om
LISTA DE FIGURAS vi
7.2 Elementos de um estágio nos problemas de programação dinâmica . . 206
7.3 Fluxo de informação que passa no estágio 2 . . . . . . . . . . . . . . 207
7.4 Fluxo de informação que passa nos estágios 1, 2 e 3 . . . . . . . . . . 207
7.5 Rede das posśıveis rotas do exemplo 7.2 . . . . . . . . . . . . . . . . . 209
7.6 Resolução pela recursividade regressiva do exemplo 7.2 . . . . . . . . 211
7.7 Diagrama do exemplo de abastecimento de água ao ponto P . . . . . 213
7.8 Diagrama do exemplo 7.5 do candidato . . . . . . . . . . . . . . . . . 216
m
um
ub
et
o8
@
gm
ai
l.c
om
Lista de Tabelas
1.1 Modelos de investigação operacional . . . . . . . . . . . . . . . . . . . 8
2.1 Análise qualitativa da informação do problema das lámpadas . . . . . 11
2.2 Relacionamento da informação do problema de alfaiate . . . . . . . . 14
2.3 Relacionamento da informação do problema de dieta . . . . . . . . . 15
2.4 Informação do problema de adubo . . . . . . . . . . . . . . . . . . . . 16
2.5 Cálculo do ponto máximo e mı́nimo de F(x) = 1x1 − 2x2 + 4 . . . . . 24
2.6 Estrutura básica de uma tabela simplex inicial . . . . . . . . . . . . . 38
2.7 Estrutura de uma tabela terminal simplex . . . . . . . . . . . . . . . 40
2.8 Variáveis auxiliares para os métodos de duas fases e de grande M . . 46
3.1 Régras de transformação de um problema primal para dual . . . . . . 70
3.2 Resumo da informação do problema primal . . . . . . . . . . . . . . . 74
3.3 Comparação das soluções dos problemas duais . . . . . . . . . . . . . 80
4.1 Tabela simplex inicial e terminal para ilustrar as propriedades usadas
na análise de sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . 90
4.2 Variação das quantidades dos recursos . . . . . . . . . . . . . . . . . 100
4.3 Variação dos coeficientes da função objectivo . . . . . . . . . . . . . . 107
4.4 Análise da adição de uma variável no modelo . . . . . . . . . . . . . . 114
5.1 Exemplo de um problema de programação linear inteira . . . . . . . . 126
5.2 Identificação da solução óptima inteira entre todas posśıveis . . . . . 128
5.3 Decomposição de um número misto em parte inteira e uma fracção
própria no método de Gomory . . . . . . . . . . . . . . . . . . . . . . 145
vii
m
um
ub
et
o8
@
gm
ai
l.c
om
LISTA DE TABELAS viii
6.1 Teste de optimidade de solução pelo método de Steppig Stone, circuitos
do exemplo 6.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
m
um
ub
et
o8
@
gm
ai
l.c
om
Caṕıtulo 1
Introdução
1.1 Definição de Investigação Operacional
O nome “Investigação Operacional (IO)”, apareceu pela primeira vez durante a Se-
gunda Guerra Mundial, quando equipas de investigadores procuravam desenvolver
métodos para resolver determinados problemas de operações militares. Precisamente
na Inglaterra, entre 1939-1945, pela necessidade militar de solucionar problemas rela-
cionados a estratégias loǵıstico-tácticas tais como: melhor distribuição de radares, di-
mensionamento de frotas, alimentação dos tropas, manutenção e inspecção de aviões
entre outras actividades. O sucesso destas aplicações levou o mundo académico e
empresarial a procurar utilizar as técnicas criadas em problemas de administração.
Segundo Ackoff e Sasieni (1968), por volta de 1950 a investigação operacional ou
Operations Research (Britânico), Management Science (Americano) e Pesquisa Ope-
racional (Brasileiro), já era reconhecida como objecto de estudo nas universidades e
no mundo académico.
Churchman (1971), no seu livro intitulado conceitos básicos dos sistemas e orga-
nizações, considerou a investigação operacional, como a aplicação de instrumentos,
técnicas e métodos cient́ıficos a problemas referentes ao funcionamento de um sistema,
permitindo que os encarregados do seu controle, alcancem soluções óptimas para tais
problemas. Segundo Richard (1974), a investigação operacional é uma aplicação
1
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
sistemática da abordagem cient́ıfica à investigação de problemas operacionais exis-
tentes ou previstos que requerem decisões pelos administradores. Actualmente, a
investigação operacional é considerada como o ataque da ciência moderna a proble-
mas complexos, como consequência da administração de grandes sistemas de homens,
máquinas, materiais e dinheiro.
De um modo geral, a investigação operacional tem em vista trabalhar com facto-
res inter-relacionados, aplicando sobre estes um conjunto de diferentes métodos ou
técnicas quantitativas para com um bom censo posśıvel resolver os problemas empre-
sariais ao ńıvel da administração.
A investigação operacional pode ser definida como:
1. A arte de dar respostas óptimas a problemas que tratados de outra forma teriam
respostas piores. (Uso da informação para a tomada de decisão).
2. O bom censo expresso em termos quantitativos.(Partindo da solução matemática
procura se tomar uma decisão viável).
3. Ciência da preparação das decisões. (Uso do método cient́ıfico para a tomada
de decisão).
4. A aplicação do método cient́ıfico à direcção de uma empresa ou projecto, vi-
sando a optimização de suas decisões ou poĺıticas, etc. (Uso do método ci-
ent́ıfico justificado pelo emprego de técnicas quantitativas para a tomada de
decisão viável).
A abordagem mais caracteŕıstica da investigação operacional, consiste em procurar
desenvolver um modelo cient́ıfico do sistema em estudo, incorporando a medição
ou quantificação de factores, tendo em conta as alternativas de decisão, as restrições
impostas pelos recursos dispońıveis para alcançar um determinado objectivo. Deve-
se estar bem claro de que o objectivo da investigação operacional é ajudar ao gestor
a estabelecer suas linhas de acção de maneira cient́ıfica, como resultado do emprego
do método quantitativo, para equacionar e solucionar os problemas existentes ao
ńıvel empresarial ou qualquer outro grau de uma organização.
Mulenga 2 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
A investigação operacional tem sido vista pelos gestores e outros utilizadores sob
dois enfoques diferentes quanto à abordagem, mas coerentes e complementares na
aplicação do processo de resolução de problemas empresariais.
(a) Enfoque clássico – busca da solução óptima. O investigador nesta abor-
dagem tem um conjunto de variáveis quantitativas, ele faz relações funcionais ou
sistema de equações, resolve e obtém uma solução óptima.
(b) Enfoque actual – busca de solução viável. O investigador nesta aborda-
gem usa modelos para a identificação correcta do problema. Aqui, são consideradas
tanto variáveis quantitativas como qualitativas, o investigador relaciona as variáveis
e produz modelos económico-matemáticos. Dos modelos derivam – se alternativas de
solução e finalmente é escolhida uma destas alternativas como solução viável para o
problema.
Figura 1.1: Enfoques da investigação operacional
Pela natureza da investigação operacional muitas definições de investigação operacio-
nal podem ser feitas, muitas delas estarão correctas se tiverem argumentos aceitáveis.
Deve-se salientar que históricamente o sucesso da investigação operacional sempre fi-
Mulenga 3 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
cou relacionado com:
• A aplicação do método cient́ıfico.
• A abordagem por equipa e inter - disciplinar.
• O envolvimento no controlo e organização dos problemas dos sistemas consti-
tuidos por pessoas, máquinas, recursos para a obtenção de soluçõesóptimas.
1.2 Caracteŕısticas da investigação operacional
As principais caracteŕısticas da investigação operacional são:
•Abordagem por equipa: consiste no uso de conhecimentos cient́ıficos por equipes
inter-disciplinares, isto é, formação de conjuntos e subconjuntos de equipes entre o
pessoal técnico, treinado, mestres, especialistas, etc. de várias áreas de conhecimento
para fazer um esforço conducente a determinação da melhor forma de utilização de
recursos limitados. Esta caracteŕıstica multi-disciplinar de resolver os problemas or-
ganizacionais deu um novo enfoque a investigação operacional – a visão sistémica dos
problemas.
• Visão sistémica: o estudo da Investigação Operacional consiste em construir
um modelo de um sistema real existente como meio de analisar e compreender o
comportamento de uma determinada situação. Esta visão é actualmente a mais
importante da tendência da administração. O método da visão sistémica também
consiste em considerar a empresa ou cada parte da mesma como um sistema com
várias variáveis inter-relacionadas. O sistema aqui considerado pode existir ou pode
estar em concepção. No primeiro caso, o objectivo do estudo tem sido de analisar o
desempenho do sistema para escolher um curso de acções no sentido de aprimorá-lo.
No segundo caso, o objectivo é identificar a melhor estrutura do futuro sistema.
• Uso de modelos matemáticos mais formais: a Investigação Operacional
através das técnicas estat́ısticas ou quantitativas em geral procura-se no processo
de análise de decisão perceber a estrutura real em análise pela representação de
Mulenga 4 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
informações e suas inter-relações procurando sempre criar um modelo matemático
padrão das relações e respectivas soluções dos problemas empresariais,
• Busca da solução óptima: consiste em seleccionar a alternativa que melhor
conduzirá a maximização dos lúcros ou minimização dos custos como primeira visão
dos administradores sem precisar saber os ńıveis de satisfação das diferentes especi-
ficidades da organização.
• Emprego de simulação sobre os modelos: consiste em imitar o funciona-
mento de um sistema real, que não pode ser compreendido tal como está, recorrendo
a uma representação adequada para fins experimentais ou de estudo do sistema real,
desde que o sistema real seja determińıstico e não estocástico.
O desenvolvimento dos computadores digitais, face a sua velocidade de processa-
mento, capacidade de armazenamento e recuperação de informações, constituiu um
imenso progresso da Investigação Operacional. Outro facto que actualmente con-
tribúı para o uso intensivo de modelos em análise de decisões é a disseminação dos
micro-computadores, que se tornaram unidades de processamentos descentralizados
dentro das empresas, o que leva aos profissionais da investigação operacional num
trabalho conjunto com os informáticos a desenvolverem softwares apropriados e mo-
delos mais versáteis, rápidos e interactivos.
Apesar das fases não serem seguidas rigosamente, em geral, e segundo Andrade
(1998) e Taha (2007), um trabalho de Investigação Operacional, deve desenvolver-se
seguindo as seguintes fases:
1. Definição do problema
2. Construção do modelo
3. Solução do modelo
4. Validação do modelo
5. Implementação da solução
Mulenga 5 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
1. Definição do problema. A definição do problema baseia-se em três aspectos
principais: a descrição exacta dos objectivos do estudo; a identificação das alterna-
tivas de decisão existentes; o reconhecimento das limitações, restricções e exigências
do sistema. A descrição dos objectivos é uma das actividades mais importantes em
todo o processo do estudo, pois, a partir dela é que o modelo é concebido.
2. Construção do modelo. Consiste na elaboração de um modelo para a solução
do problema, relacionando todas as informações ou variáveis associadas ao problema.
O modelo elaborado pode estar na forma padrão já conhecida ou completamente nova
por conceber.
3. Solução do modelo. Como a solução do problema pode ser obtida por ter-
ceiros, nesta fase é necessário analisar todos os procedimentos mais adequados, em
termos do método proposto, rapidez de processamento e precisão da resposta para
a solução do problema e escolhar aquela alternativa que satisfaz os objectivos or-
ganizacionais. Deve-se tomar atenção que mesmo sabendo o conceito e significado
de solução viável, para muitos tomadores de decisão a tendência de chamar solução
óptima é patente.
4. Validação do modelo. Nesta fase do processo de solução, verifica-se a vali-
dade do modelo. Um modelo é válido se ele for capaz de fornecer uma previsão
aceitável do comportamento do sistema. Um método comum para testar a validade
de um sistema é analisar seu desempenho com dados passados do sistema e verificar
se ele consegue reproduzir o comportamento que o sistema apresentou.
5. Implementação da solução. A implementação, por ser uma actividade que
altera uma situação existente, é uma das etapas cŕıticas do estudo. É conveniente
que seja controlada pela equipa responsável, pois, eventualmente os valores da nova
solução quando levados à práctica, podem demonstrar a necessidade de correcções
nas relações funcionais do modelo como um todo, exigindo a reformulação do modelo
em algumas das suas partes.
Mulenga 6 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
1.3 Técnicas da investigação operacional
A descrição sobre o conjunto das técnicas que compõem a investigação operacional,
não tem uma uniformidade. Assim, encontram-se técnicas designadas como teorias,
métodos ou modelos e vice-versa. Além disso, em cada uma das categorias, uma
determinada técnica aparece com vários t́ıtulos diferentes; várias técnicas diferentes
podem aparecer com o mesmo t́ıtulo, e mesmo o nome investigação operacional apa-
rece inserido numa outra categoria, por exemplo métodos quantitativos.
Entre muitos autores, destacam-se Quesnay (1759), Walras (1874), Markov (1856
– 1922), von Neumann (1937), Kantorovich (1939), Wicks e Yewdale (1971), Ackoff
(1971), Duckworth (1972), etc., que contribúıram significativamente na divisão da
Investigação Operacional em diversas categorias.
O critério usado na sucinta descrição foi o de tratar em separado, quando posśıvel,
as várias técnicas, teorias, métodos e modelos que precisamente são discutidas em
muitas áreas do conhecimento cient́ıfico.
1. Estat́ıstica matemática: que inclui a teoria das probabilidades e estat́ıstica.
2. Teoria de informação e apoio à decisão: inclui os tópicos relacionados com a
análise de decisão, teoria de jogos, problemas das filas de espera, gestão de estoques,
planeamento e controlo de projectos, etc.
3. Programação matemática: inclui a programação linear, inteira, dinâmica, não
linear, problemas de transporte e distribuição ou afectação de recursos, etc.
4. Simulação e método de Monte Carlo: que inclui a análise da dinâmica in-
dustrial, análise de redes, etc.
Mesmo considerando que a análise quantitativa é importante para a tomada de de-
cisão, é necessário esclarecer aos utilizadores das técnicas ou métodos quantitativos,
que nem todos os problemas são suscept́ıveis de solução pelas técnicas quantitativas.
Uma aplicação bem-sucedida dos métodos quantitativos, requer uma interacção entre
as ciências matemáticas e as ciências do comportamento, pois, o sistema em estudo
Mulenga 7 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
interage com seres humanos, e:
• Nem todos factores de um dado problema podem ser quantificados quando se
tem variáveis qualitativas.
• Variáveis nãocontroláveis podem dificultar ao máximo o processo de modelação
do problema, fazendo com que os modelos sejam menos perfeitos.
• O uso de números e de equações, dá uma aparência de exactidão cient́ıfica e esta
tendência pode desviar o sentido da solução viável e mesmo de interpretação
da solução matemática.
• O desejo de confrontar demais os métodos quantitativos pode ser perigoso, pois,
chega-se a soluções matemáticas que carecem de uma interpretação social.
Tabela 1.1: Modelos de investigação operacional
Modelo Optimização linear Apoio à decisão
Ferramenta operacional Matemática Teoria de informação
Enfoque desejado Solução exacta Solução viável
Objectivo final Solução óptima Satisfazer os interesses
da organização
Mulenga 8 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Caṕıtulo 2
Programação linear
2.1 Introdução
Deśıgna - se por programação linear (PL), um conjunto de técnicas que permitem
resolver os problemas de optimização, num sistema de recursos limitados, sendo li-
neares, quer a função objectivo, quer as restrições.
A importância especial da programação linear, resulta não só das potencialidades dos
seus algoŕıtmos de resolução e da sua grande diversidade de aplicação, mas também,
da sua génese de estar directamente relacionada com o desenvolvimento dos próprios
conceitos fundamentais das teorias de optimização das soluções de problemas empre-
sariais. Os principais desenvolvimentos teóricos da programação linear são devidos
a Kantorovich (1939) e a um grupo de cient́ıstas americanos que lançaram as bases
da programação linear entre 1939 à 1951, onde Dantzig (1947)1. publicou o método
simplex e von Neuman (1947) desenvolveu a teoria da dualidade.
A programação linear lida-se com problemas que dizem respeito à atribuição e a
distribúıção de recursos entre as diversas tarefas ou actividades que devem ser rea-
lizadas. Normalmente, os recursos dispońıveis não são suficientes para que todas as
actividades sejam executadas no ńıvel desejado. Assim, o que se procura, é encon-
1George Dantzig (1914-2005), Matemático de Oregon - Estados Unidos da America
9
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
trar a melhor distribuição posśıvel dos recursos, de forma a atingir um valor óptimo
objectivo que pode ser a maximização dos lúcros ou a minimização dos custos.
Assim, um problema de programação linear é caracterizado por três elementos básicos:
1. Variáveis de decisão: todo o problema de programação linear deve ter
variáveis de decisão, que são o centro das atenções na resolução do problema.
2. Função objectivo: os problemas empresariais são formulados em função de
um objectivo que mode ser de maximização dos lúcros ou minimização dos
custos. Em programação linear o objectivo é expresso em termos das variáveis
de decisão.
3. Um conjunto de restrições: como as empresas utilizam recursos para pro-
duzir quantidades de produtos, é evidente que haja restrições relacionadas à
utilização destes recursos, tanto em relação às quantidades dispońıveis como
em relação a forma de emprego.
Os estudos de programação linear permitem responder questões como:
• “... sendo conhecidas certas condições de produção, qual é a quantidade de um
determinado produto, entre vários, que se deve produzir para obter o maior
lúcro posśıvel?”
• “... sendo impostas algumas especificações, qual é a composição da mistura que
corresponde ao custo mı́nimo?”
• “... estando impostas as condições de trabalho, como repartir o conjunto de
mão-de-obra entre as diferentes tarefas e especialidades dos funcionários, com
o objectivo de minimizar as despesas ou maximizar a eficiência?”
2.1.1 Formulação dos problemas de programação linear
Exemplo 2.1. Uma companhia de montagem de lámpadas, usa dois modelos para
a montagem: o modelo actual automático e o modelo antigo com acessoria. Cada
pessoa no modelo actual requer 1 hora de trabalho se vier do departamento de corte
Mulenga 10 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
e 3 horas se vier do departamento de verificação. No modelo antigo, cada pessoa ne-
cessita de 2 horas de trabalho, se vier do departamento de corte e 4 horas de trabalho
se for do departamento de verificação. O número máximo de horas de trabalho para
o departamento de corte é de 32, enquanto no departamento de verificação é de 84
horas. Se a companhia recebe um lúcro de 50 unidades de medida (u.m.) por cada
lámpada vinda do modelo actual e 80 unidades de medida por cada lâmpada vinda
do modelo antigo, quantas lḿpadas devem ser produzidas em cada modelo de modo
que a companhia maximize o lúcro?
Resolução
Este é um exemplo t́ıpico de um problema de programação linear. Para tornar claro,
as relações entre o objectivo e as restrições, é necessário apresentar esta informação
numa tabela. O método usado para a formulação dos problemas de programação
linear tem uma determinada lógica, ainda que esta não seja rigorosamente seguida,
começando pela análise qualitativa da informação ou problema.
Análise qualitativa do problema. Esta análise depende da experiência adqui-
rida anteriormente, isto é, a sensibilidade de analisar e relacionar a informação que
geralmente apresenta-se uma tabela.
Tabela 2.1: Análise qualitativa da informação do problema das lámpadas
Departamento Horas de trabalho por pessoa Número máximo de
modelo actual modelo antigo horas de trabalho
De corte 1 2 32
De verificação 3 4 84
Lúcro unitário 50 80 -
Identificação das caracteŕısticas dos problemas de programação linear.
Nesta etapa, depois de relacionar a informação na Tabela 2.1, começa-se a iden-
Mulenga 11 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
tificação dos elementos fundamentais de um modelo de programação linear.
Variáveis de decisão: seja x1 o número de lámpadas produzidas no modelo ac-
tual por dia e x2 o número de lámpadas produzidas no modelo antigo por dia.
Função objectivo: o objectivo da companhia é decidir quantas lámpadas são ne-
cessárias produzir por dia para cada modelo, de modo que ela tenha o máximo lúcro
diário. A função lúcro deste problema ou função objectivo é: Lucro = 50x1 + 80x2.
Repare que a função lúcro está ligada aos valores monetários do problema e estão na
última linha da Tabela 2.1.
Conjunto de restrições: restrições são inequações ou equações que representam as
relações entre as quantidades produzidas, o número de horas necessárias para produ-
zir uma unidade de cada produto considerando a disponibilidade máxima do recurso.
Assim, tem-se:
• A restrição para o departamento de corte: 1x1 + 2x2 ≤ 32
• A restrição para o departamento de verificação: 3x1 + 4x2 ≤ 84
• Como não podem ser produzidas quantidades negativas de lámpadas, adiciona-se
as restrições de não negatividade: x1 ≥ 0 e x2 ≥ 0 ou usualmente x1, x2 ≥ 0.
Elaboração do modelo económico matemático: consiste na indicação das relações
entre as variáveis de decisão, a função objectivo e as restrições como um todo. Par-
tindo das situações anteriores, escreve-se o modelo matemático do problema de pro-
gramação linear. Note que, modou-se de L para Z por conveniência.
maximizar Z = 50x1 + 80x2
sujeito à

1x1 + 2x2 ≤ 32
3x1 + 4x2 ≤ 84
x1, x2 ≥ 0
Qualquer par de valores de x1 e x2 que satisfaz todas as restrições do modelo é uma
solução posśıvel ou admisśıvel.
Mulenga 12 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Caso 1. Se x1 = 0 e x2 = 0 o valor de Z será, Z = 50× 0 + 80× 0 = 0. Como não
viola nenhuma das restrições, esta é uma solução posśıvel.
Caso 2. O par de valores x1 = 2 e x2 = 5 também é uma solução posśıvel, póıs, não
viola nenhumadas restrições incluindo as de não negatividade. Para verificar basta
substituir em cada uma das restrições:
Na primeira restrição: 1× 2 + 2× 5 = 12 < 32, verdadeiro.
Na segunda restrição: 3× 2 + 4× 5 = 26 < 84, verdadeiro.
O lúcro posśıvel para esta solução é: Z = 50× 2 + 80× 5 = 500 unidades de medida.
Caso 3. O par de valores x1 = 8 e x2 = 13 tem Z = 1440. As restrições de
não negatividade são satisfeitas porque os valores são positivos. Mas, deve-se ve-
rificar também as restrições relativas aos recursos. Na primeira restrição tem-se:
r1 = 1× 8 + 2× 13 = 8 + 26 = 34 < 32 não é verdadeiro, mas na segunda restrição
tem-se: r2 = 3 × 8 + 4 × 13 = 24 + 52 = 76 < 84 é veradeiro. Como a primeira
restrição não é satisfeita o par (8, 13) com Z = 1440, não é solução viável.
Variando os valores a atribuir as variáveis de decisão, pode-se encontrar outra solução
admisśıvel, entretanto o objectivo da optimização linear é encontrar entre todas as
soluções posśıveis, uma solução óptima posśıvel. Para que o processo não seja por
tentativas, existem métodos espećıficos que são usados para encontrar as soluções
óptimas. Para o exemplo 2.1, a solução óptima é: x1 = 20, x2 = 6 com Zmax = 1480.
Ora vejamos a verificação nas restrições:
Primeira restrição r1 = 1× 20 + 2× 6 = 20 + 12 = 32(= 32) o máximo do rescurso 1.
Segunda restrição r2 = 3× 20 + 4× 6 = 60 + 24 = 84(= 84) o máximo do recurso 2.
Na função objectivo Zmax = 50× 20 + 80× 6 = 1000 + 480 = 1480.
No exemplo 2.1, assumiu-se que tanto a função objectivo como as restrições são
todas lineares. Intrinsecamente são utilizadas duas proposições.
Proposição 1. Proporcionalidade – nos modelos de programação linear, a con-
Mulenga 13 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
tribuição das variáveis de decisão na função objectivo e nas restrições é directamente
proporcional aos valores que as variáveis assumem.
Proposição 2. Aditividade – a contribuição total de todas as variáveis na função
objectivo e em cada restrição é igual a soma das contribuições individuais de cada
variável.
Exemplo 2.2. Um alfaiate tem dispońıvel 16 m2 de algodão, 11 m2 de seda e
15 m2 de lâ. A confecção de um fato necessita de 2 m2 de algodão, 1 m2 de seda e
1 m2 de lã, e um vestido gasta 1, 2 e 3 m2 dos mesmos tecidos, respectivamente. Se
um fato é vendido à 30 unidades de medida (u.m.) e um vestido por 50 u.m., quantas
unidades de cada artigo fato ou vestido deve o alfaiate confeccionar de modo a obter
maior lúcro?
Tabela 2.2: Relacionamento da informação do problema de alfaiate
Tecidos Artigos Quantidade
fato vestido Dispońıvel
Algodão 2 1 16
Seda 1 2 11
Lã 1 3 15
Preço de venda 30 50 -
O modelo económico matemático correspondente é:
maximizar Z = 30x1 + 50x2
sujeito à

2x1 + 1x2 ≤ 16
1x1 + 2x2 ≤ 11
1x1 + 3x2 ≤ 15
x1, x2 ≥ 0
Mulenga 14 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Exemplo 2.3. Um indiv́ıduo pretende fazer uma selecção de um conjunto de 5 ali-
mentos básicos. Por forma a conseguir estruturar uma dieta que, do ponto de vista
nutritivo, tenha como normas mı́nimas de calorias e vitaminas, respectivamente de
70 e 50 unidades, gastando o mı́nimo posśıvel. Os preços de venda dos alimentos,
bem como a sua composição em elementos nutritivos são dados pelo seguinte quadro.
Tabela 2.3: Relacionamento da informação do problema de dieta
Elemento alimentos básicos
nutritivo A B C D E
Calorias 1 0 1 1 2
Vitaminas 0 1 0 1 1
Custo unitário 2 20 3 11 12
O modelo económico matemático correspondente ao problema é:
minimizar W = 2x1 + 20x2 + 3x3 + 11x4 + 12x5
sujeito à

1x1 + 0x2 + 1x3 + 1x4 + 2x5 ≥ 70
0x1 + 1x2 + 0x3 + 1x4 + 1x5 ≥ 50
x1, x2, x3, x4, x5 ≥ 0
Exemplo 2.4. Um agricultor precisa de 100 kg de Azoto, 120 kg de Fósforo e 120 kg
de Potássio, para adubar a sua plantação. Ele tem duas possibilidades no mercado,
sendo uma na forma ĺıquida em tambores que contém 50 kg de Azoto, 20 kg de
Fósforo e 10 kg de Potássio ao preço de 30 u.m cada; outra empresa fornece adubo
em sacos, contendo 10, 20 e 40 kg de Azoto, Fósforo e Potássio, respectivamente, ao
preço de 20 u.m cada saco. Quantas embalagens de cada fonte deverá o agricultor
comprar para suprir as suas necessidades pelo menor custo.
Mulenga 15 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Tabela 2.4: Informação do problema de adubo
Composição Possibilidades do mercado Necessidades
do abudo tambor saco mı́nimas
Azoto 50 10 100
Fóstoro 20 20 120
Potássio 10 40 120
Custo unitário 30 20 -
O modelo matemático correspondente é:
minimizar W = 30x1 + 20x2
sujeito à

50x1 + 10x2 ≥ 100
20x1 + 20x2 ≥ 120
10x1 + 40x2 ≥ 120
x1, x2 ≥ 0
2.1.2 Definição geral dos problemas de programação linear
Os problemas de optimização linear (programação linear), podem ser representados
na forma:
maximizar Z = c1x1 + c2x2 + ...+ cmxm
sujeito à

a11x1 + a12x2 + ...+ a1mxm ≤ b1
a21x1 + a22x2 + ...+ a2mxm ≤ b2
...
an1x1 + an2x2 + ...+ anmxm ≤ bn
x1, x2, ..., xm ≥ 0
Mulenga 16 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Admite-se que, em lugar de maximizar, haja minimizar, e em lugar de menor ou igual
(≤) seja maior ou igual (≥) ou mesmo igual (=).
Assim, para os problemas com restrições onde existe um recurso máximo dispońıvel
usa-se o sinal (≤) e para as restrições onde no recurso existe uma quantida mı́nima
desejável usa-se o sinal (≥). Se uma ou mais restrições apresentar o sinal de igualdade
(=), esta pode ser substituida por duas inequações, em seguida uma das inequações
deverá ser multiplicada por (-1), caso seja necessário, para satisfazer a função objec-
tivo.
Por exemplo: 2x1 + 3x2 = 4 equivale a escrever o sistema
 2x1 + 3x2 ≤ 42x1 + 3x2 ≥ 4
2.1.3 Exerćıcios propostos
Exerćıcio 2.1. Um padeiro dispõe de 150, 90 e 150 unidades dos ingredientes A, B
e C respectivamente. Cada pão necessita de 1 unidade de A, 1 de B e 2 de C, e um
bolo precisa de 5, 2 e 1 unidades de A, B e C, respectivamente. Se um pão é vendido
à 35 u.m., e um bolo é vendido à 80 u.m. Como deve o padeiro distribuir a matéria
prima dispońıvel de modo a obter o maior lúcro? Elabore o modelo matemático
correspondente a este problema de programação linear.
Exerćıcio 2.2. Cada kg do alimento A custa 85 u.m. e contém 2 unidades de
protéına, 6 unidades de hidrato de carbono e 1 unidade de gordura. O alimento
B que se pode comprar a 45 u.m. por kg, contém 1, 1 e 3 unidades, de proteina,
hidratos de carbono e gordura, respectivamente. Supondo que as necessidades sema-
nais mı́nimas de uma pessoa são 8 unidades de protéına, 12 unidades de hidrato de
carbono e 9 unidades de gordura. Elabore o modelo económico matemático de forma
que a pessoa economize os seus gastos.
Exerćıcio 2.3. Certa empresa fabrica 2 produtos P1 e P2. O lúcro por unidade
de P1 é de 100 unidades de medida e o lúcro unitário de P2 é de 150 unidades de
medida. A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas
Mulenga 17 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
para fabricar uma unidade de P2. O tempo mensal dispońıvel para essas actividades
é de 120 horas. As demandas esperadas para os dois produtos levaram a empresa a
decidir que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades
de P1 e 30 unidades de P2 por mês. Elabore o modelo do sistema de produção mensal
que maximiza o lúcro da empresa.
Exerćıcio 2.4. A empresa Sementes de Moçambique (SEMOC), pretende semear
arroz e milho, dispondo para tal de áreas que não excedem, respectivamente, 3 e 4
hectares nos arredores de Boane. Por outro lado, as suas disponibilidades em tra-
balho são apenas de 9horas diárias. Admitindo que, por cada hectare semeado de
arroz é necessário 1 hora de trabalho e por cada hectare de milho são necessárias 2
horas. Sabendo que por cada hectare de arroz semeado o lúcro é de 5 u.m. e por
cada hectare de milho 2 u.m, formule o problema como um problema de programação
linear.
Exerćıcio 2.5. Dois páıses A e B, emprestam dinheiro a outro pais C. Por cada
X unidades monetárias concedidas pelo pais A, este cobra anualmente do pais C,
uma tonelada de cortiça, 5 toneladas de trigo e 3 toneladas de peixe. Por cada Y
unidades monetárias concedidas pelo páıs B, são cobrados anualmente ao páıs C, uma
tonelada de cortiça, 2 toneladas de trigo e 8 toneladas de peixe. Anualmente o pais
C não tem dispońıveis mais de 20 toneladas de cortiça, 100 toneladas de trigo e 120
toneladas de peixe. Sabendo que por cada unidade monetária emprestada, o páıs C
recebe do páıs A 500 espingardas e do páıs B 300 metralhadoras, formule o problema
de programação linear que maximiza o número de armas que C pode adquirir por
este processo.
Exerćıcio 2.6. Uma companhia de aluguel de camiões possúı dois tipos de camiões:
o tipo A com 2 m3 de espaço refregerado e 4 m3 de espaço não refregerado e o tipo
B com 3 m3 de espaço refregerado e 3 m3 de espaço não refregerado. Uma fábrica
de produtos aliment́ıcios precisou transportar 9 m3 de produto refregerado e 12 m3
de produto não refrigerado. Quantos camiões de cada tipo devem ser alugados de
modo a minimizar o custo total, se o aluguel de um camião do tipo A é de 30 u.m
Mulenga 18 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
por km e do tipo B é de 40 u.m por km. Formule o problema de programação linear
da fábrica que necessita de transportar os seus produtos.
Exerćıcio 2.7. Uma pequena manufatura produz dois modelos de carteiras es-
colares. O modelo padrão e o modelo de luxo dessas carteiras. Cada unidade do
modelo padrão requer 3 horas de lixação e 1 hora de polimento. Cada unidade do
modelo de luxo exige 1 hora de lixação e 4 horas de polimento. A fábrica dispõe de
2 lixadores e 3 polidores, cada pessoa trabalha 40 horas semanais. As margens de
lúcro são 24 e 32 unidades monetárias, respectivamente, para cada unidade padrão e
de luxo. Não existem restrições de demanda para ambos os modelos. Elabore o mo-
delo de programação linear que permita calcular a produção semanal que maximiza
a margem total de lúcro do fabricante.
Exerćıcio 2.8. Uma fábrica de imóveis dispõe de 6 placas de madeira e 28 ho-
ras que poderá utilizar para fabricar biombos decorativos. No passado, houve dois
modelos de biombos que se venderam bastante bem, pelo que o fabricante já restrin-
girá a esses dois modelos. Segundo as suas estimativas, cada biombo do modelo I,
requer 2 placas de madeira e 7 horas de mão – de – obra, enquanto que um biombo
do modelo II, requer uma placa de madeira e 8 horas de mão – de – obra. Os biombos
são produzidos a um custo unitário de 80 e 50 meticais cada. O biombo do modelo
1 é mais carro por isso é vendido à 120 meticais, enquanto o biombo do modelo II é
vendido à 80 meticais. Usando as informações do texto, elabore o modelo económico
matemático como um problema de programação linear.
Exerćıcio 2.9. Uma fábrica de tintas produz dois tipos de tinta: uma tinta para
interiores e outra tinta para exteriores. Para isso, a fábrica recorre a dois tipos de
matéria prima A e B, que possúı 25 e 35 unidades de medida respectivamente, em
stock que não poderá ser reforçado ao longo do processo. Para produzir um litro de
tinta interior é necessário uma unidade de medida da matéria prima A e três unida-
des de matéria prima B. Para produzir um litro da tinta exterior é necessário duas
unidades da matéria prima A e 4 unidades de B. Um estudo de mercado indica que a
procura de tinta interior não excede em mais de 1 unidade de medida a tinta exterior.
Mulenga 19 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
O preço de venda da tinta interior é de 30.00 meticais por litro e da tinta exterior
de 45.00 meticais por litro. Formule o problema como um problema de programação
linear.
Número 2.10. Uma cĺınica de amagrecimento Peso Certo, SA pretende criar um
programa de perda de peso que garante a ingestão, pelos seus clientes de alimentos
que atinjam um máximo de 1500 calorias diárias. Para que a alimentação seja bem
consolidada, exige-se uma nutrição equilibrada que preveja ńıveis mı́nimos de in-
gestão de proteinas, hidratos de carbono, gorduras, vitaminas e fósforo. Estes ńıveis
correspondem de acordo com uma tabela de prescrição cĺınica de autoria dos invs-
tigadores da cĺınica, à 50; 35; 22; 25 e 30 pontos respectivamente. A cĺınica prevê
uma alimentação nacional à base de quatro tipos de refeições oferecidas quatro ve-
zes por dia, podem ser repetidas ou misturadas se assim for decidido. As refeições
apresentam um ı́ndice de sensão de fome diário, calculado com base cient́ıfica que
corresponde aos seguintes valores: 0.6, 0.5, 0.4 e 0.5. Adicionalmente, apresenta-se
uma classificação em função dos tipos de elementos nutrientes exigidos.
Refeição Proteinas Hidratos de carbono Gorduras Vitaminas Fósforo
Verde 6 8 5 7 4
Branca 9 11 9 10 16
Azul 10 12 14 8 12
Vermelha 12 8 10 11 8
Usando as informações apresentadas, formule o problema de programação linear de
modo que se saiba que refeições devem ser oferecidas aos clientes por forma a garantir
uma alimentação equilibrada e racional que permita uma perda de peso, seja saudável
e consolidada. (Nota. use x1 = verde, x2 = branca, x3 = azul e x4 = vermelha).
Mulenga 20 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Respostas dos exerćıcios 2.1.3
maximizar Z = 35x1 + 80x2
2.1) sujeito à

1x1 + 5x2 ≤ 150
1x1 + 2x2 ≤ 90
2x1 + 1x2 ≤ 150
x1, x2 ≥ 0
minimizar W = 85x1 + 45x2
2.2) sujeito à

2x1 + 1x2 ≥ 8
6x1 + 1x2 ≥ 12
1x1 + 3x2 ≥ 9
x1, x2 ≥ 0
maximizar Z = 100x1 + 150x2
2.3) sujeito à

2x1 + 3x2 ≤ 120
1x1 + 0x2 ≤ 40
0x1 + 1x2 ≤ 30
x1, x2 ≥ 0
maximizar Z = 5x1 + 2x2
2.4) sujeito à

1x1 + 2x2 ≤ 9
1x1 + 0x2 ≤ 3
0x1 + 1x2 ≤ 4
x1, x2 ≥ 0
maximizar Z = 500x1 + 300x2
2.5) sujeito à

1x1 + 1x2 ≤ 20
5x1 + 2x2 ≤ 100
3x1 + 8x2 ≤ 120
x1, x2 ≥ 0
minimizar W = 30x1 + 40x2
2.6) sujeito à

2x1 + 3x2 ≥ 9
4x1 + 3x2 ≥ 12
x1, x2 ≥ 0
maximizar Z = 24x1 + 32x2
2.7) sujeito à

3x1 + 1x2 ≤ 80
1x1 + 4x2 ≤ 120
x1, x2 ≥ 0
maximizar Z = 40x1 + 30x2
2.8) sujeito à

2x1 + 1x2 ≤ 6
7x1 + 8x2 ≤ 28
x1, x2 ≥ 0
Mulenga 21 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
maximizar Z = 30x1 + 45x2
2.9) sujeito à

1x1 + 2x2 ≤ 25
3x1 + 4x2 ≤ 35
1x1 − 1x2 ≤ 1
x1, x2 ≥ 0
min W = 0.6x1 + 0.5x2 + 0.4x3 + 0.5x4
2.10) s.à

6x1 + 9x2 + 10x3 + 12x4 ≥ 50
8x1 + 11x2 + 12x3 + 8x4 ≥ 35
5x1 + 9x2 + 14x3 + 10x4 ≥ 22
7x1 + 10x2 + 8x3 + 11x4 ≥ 25
4x1 + 16x2 + 12x3 + 8x4 ≥ 30
x1, x2, x3, x4 ≥ 0
2.2 Resolução dos problemas de programação li-
near pelo método gráfico
O método gráfico pode ser aplicado para resolver os problemas de programação linear
de forma eficiente, apenas quando a função objectivo e o conjunto das restrições tiver
duas variáveis de decisão. Para compreender o procedimento de resolução, vai-se
começar por introduzir a noção de domı́nio ou conjunto solução de um sistema de
inequações.
2.2.1 Domı́nio das soluções admisśıveis
Dado um sistema de inequações, para encontrar o domı́nio solução, deve-se represen-
tar cada uma das inequações no sistema de coordenadas rectangulares de Descartes,
em seguida indicar a intersecção de todos os semi-planos que satisfazem as inequações.
É precisamentea área intersecção de todos os semi-planos, o conjunto ou domı́nio
solução do sistema de inequações.
Exemplo 2.5. Encontrar o domı́nio solução dos sistemas de inequações.
a)

1x1 ≥ 0
1x2 ≥ 0
1x1 + 1x2 ≥ 2
b)
 1x1 + 1x2 ≥ 1−1x1 + 1x2 ≤ 1 c)
 1x1 ≤ 21x1 + 1x2 ≥ 2
Mulenga 22 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Resolução
Ver a Figura 2.1, onde cada recta tem associada a ela uma secta que indica o semi-
plano onde a desigualdade é verdadeira.
(a) (b) (c)
Figura 2.1: Domı́nio solução de sistema de inequações
Exemplo 2.6. Determinar o conjunto solução do sistema e calcular o valor máximo
e mı́nimo da função F(x) = 1x1−2x2+4 sobre o poĺıgono convexo dado pelo sistema.
1x1 + 1x2 ≤ 4
−1x1 − 2x2 ≤ 2
−1x1 + 1x2 ≤ 2
1x1 + 0x2 ≤ 3
x1, x2 ≥ 0
Resolução
Ver a Figura 2.2, onde cada recta tem associada a ela uma secta que indica o semi-
plano onde a desigualdade é verdadeira.
Os pontos A, B, C, D e E são chamados pontos extremos do poĺıgono.
As coordenadas de cada ponto foram obtidas resolvendo o sistema de duas equações
de rectas que passam por cada um dos pontos. Para determinar o valor da função
F(x), precisamos conhecer as coordenadas de cada ponto, para isso, foi necessário
resolver um sistema de duas equações com duas variáveis. Assim teremos:
Mulenga 23 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
(a) Dominio solução (b) Pontos extremos
Figura 2.2: Domı́nio solução e pontos máximo e mı́nimo de F(x)
• Ponto A = r5 ∩ r6 = (x1 = 0 ∩ x2 = 0)
• Ponto B = r4 ∩ r6 = (x1 = 3 ∩ x2 = 0)
• Ponto C = r1 ∩ r4 = (1x1 + 1x2 = 4 ∩ x1 = 3)
• Ponto D = r1 ∩ r3 = (1x1 + 1x2 = 4 ∩ −1x1 + 1x2 = 2)
• Ponto E = r3 ∩ r5 = (−1x1 + 1x2 = 2 ∩ −1x1 − 2x2 = 2)
Resolvendo os sistemas de equações tem-se as coordenadas de cada ponto.
Tabela 2.5: Cálculo do ponto máximo e mı́nimo de F(x) = 1x1 − 2x2 + 4
Ponto Coordenadas Substituição Valor de F(x)
A (0,0) F(x) = 1×0 - 2×0 + 4 4
B (3,0) F(x) = 1×3 - 2×0 + 4 7
C (3,1) F(x) = 1×3 - 2×1 + 4 5
D (1,3) F(x) = 1×1 - 2×3 + 4 -1
E (0,2) F(x) = 1×0 - 2×2 + 4 0
Mulenga 24 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Segundo os valores da função F(x), o ponto máximo é o ponto B com F(x)max = 7
e o ponto mı́nimo é o ponto D com F(x)min = −1.
Observações:
1. Devido as condições de não negatividade para as variáveis de decisão nos modelos
de programação linear, a recta 3 na Figura 2.2, não pertence ao domı́nio solução.
2. Para obter as coordenadas dos pontos é necessário resolver um sistema de duas
equações com duas varáveis, para tal, qualquer método já conhecido serve.
3. O ponto máximo ou mı́nimo na resolução dos problemas de programação linear
pelo método gráfico depende da função objectivo e não da sua aparente posição ge-
ográfica.
Exemplo 2.7. Usando o método gráfico resolver o problema de programação li-
near.
maximizar Z = 3x1 + 2x2
Sujeito à

−3x1 + 4x2 ≤ 12
2x1 + 1x2 ≤ 14
2x1 − 3x2 ≤ 6
x1, x2 ≥ 0
Resolução
O primeiro passo é considerar que temos um sistema de equações em vez de ine-
quações como está representado no sistema e designar as equações por rectas.
maximizar Z = 3x1 + 2x2
Sujeito à

−3x1 + 4x2 = 12 r1
2x1 + 1x2 = 14 r2
2x1 − 3x2 = 6 r3
x1 = 0, x2 = 0 r4, r5
Mulenga 25 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
O segundo passo é calcular as coordenadas de dois pontos para cada recta, por exem-
plo para a recta 1, se x1 = 0 então x2 =
12
4
= 3, por outro lado se x2 = 0, então
x1 =
12
−3
= −4, assim em diante todos os pontos das rectas são obtidos.
Para a função objectivo, se x1 = x2 = 0 o valor da função objectivo será Z = 0,
este é o mı́nimo valor que esta função pode atingir já que ela não pode ter valores
negativos em programação linear devido a não negatividade das variáveis de decisão.
Assim sendo, se Z = 0 então 3x1 + 2x2 = 0, o que resulta na igualdade x2 = −
3
2
x1.
Desta recta, se x1 = 0 então x2 = 0, se x1 = 2, então x2 = −
3
2
× 2 = −3.
Em seguida estão apresentados todos os pontos das rectas no sistema de coorde-
nadas rectangulares incluindo a recta da função objectivo.
r1 : x1 x2
0 3
-4 0
r2 : x1 x2
0 14
7 0
r3 : x1 x2
0 -3
3 0
rz : x1 x2
0 0
2 -3
x2 = −
3
2
x1
Figura 2.3: Ilustração da resolução de um problema de maximização
Mulenga 26 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
O terceiro passo, é depois de traçar cada recta, escolher um ponto em um dos semi-
planos P(x̃1, x̃2) e substituir na inequação corresponde. Se a desigualdade for verda-
deira colocar a seta virada para este lado, caso contrário, a seta deverá ficar virada
para o outro semi-plano. Por exemplo para a recta 2, tendo-se escolhido o ponto
P(2,1), tem-se r2 = −3× 2 + 4× 1 = −2 < 12. Como esta desigualdade é veradeira
a seta está virada para o simi-plado onde se encontra o ponto P(2,1) na Figura 2.3.
O quarto passo é identificar o ponto máximo ou mı́nimo. Para os problemas de maxi-
mização, deve-se traçar rectas paralelas à recta da função objectivo e deslocar até ao
último ponto da área tracejada. Este ponto é o ponto máximo da função objectivo.
Em seguida deve-se resolver o sistema de equações de rectas que intersectam neste
ponto para determiner os valores de x1 e x2. Conhecidos estes valores substitui-se na
função objectivo e finalmente apresenta-se a solução do problema.
Pmax = r1 ∩ r2 −3x1 + 4x2 = 12+2x1 + 1x2 = 14 / ∗ (−4) →
 −3x1 + 4x2 = +12−8x1 − 4x2 = −56 somando as equações
 −11x1 = −44− →
 x1 = 42a−equacao →
 x1 = 42x1 + 1x2 = 14 →
 x1 = 4x2 = 6
Zmax = 3x1 + 2x2 = 3× 4 + 2× 6 = 24, a solução é: x1 = 4, x2 = 6, Zmax = 24
Exemplo 2.8. Uma pessoa precisa de 10, 12, e 12 unidades dos produtos qúımicos
A, B e C, respectivamente para o seu jardim. Um produto ĺıquido contém 5, 2 e 1
unidades de A, B e C, respectivamente por litro; um produto em pó contém 1, 2 e 4
unidades de A, B e C, respectivamente por caixa. Se o produto ĺıquido custa 3 u.m.
por litro e o produto em pó custa 2 u.m. por caixa.
a) Formule o problema como um problema de programação linear.
b) Resolva o problema pelo método gráfico de modo a determinar quantos litros e
caixas devem ser compradas para minimizar o custo e satisfazer as necessidades?
Mulenga 27 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Resolução
A seguinte tabela resume os dados do problema.
Prod.Qúımicos unidades por litro unidades por caixa min. necessário
Produto A 5 1 10
Produto B 2 2 12
Produto C 1 4 12
Preço por u.m. 3 2 –
O modelo matemático é:
minimizar W = 3x1 + 2x2
Sujeito à

5x1 + 1x2 ≥ 10
2x1 + 2x2 ≥ 12
1x1 + 4x2 ≥ 12
x1, x2 ≥ 0
minimizar W = 3x1 + 2x2 rw : x2 = −
3
2
x1
Sujeito à

5x1 + 1x2 = 10; r1
2x1 + 2x2 = 12; r2
1x1 + 4x2 = 12; r3
x1 = 0, x2 = 0; r4, r6
r1 : x1 x2
0 10
2 0
r2 : x1 x2
0 6
6 0
r3 : x1 x2
0 3
12 0
rw : x1 x2
0 0
2 -3
Mulenga 28 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Figura 2.4: Ilustração da resolução de um problema de minimização
Para os problemas de minimização a recta da função objectivo deve ser traçada até ao
primeiro ponto da área tracejada como ilustra a Figura 2.4. Neste caso, a intersecção
é entre as rectas 1 e 2, portanto Pmin = r1 ∩ r2 5x1 + 1x2 = 102x1 + 2x2 = 12 / : (−2) →
 +5x1 + 1x2 = +10−1x1 − 1x2 = −6 somando as 2 equações 4x1 = 4− →
 x1 = 11a−equacao →
 x1 = 1x2 = 10− 5× 1 = 5
O valor da função objectivo é: Wmin = 3× 1 + 2× 5 = 13.
Resposta. A pessoa deve comprar 1 litro do produto ĺıquido e 5 caixas do pro-
duto em pô e terá um custo mı́nimo de 13 unidades monetárias.
Mulenga 29 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
InvestigaçãoOperacional
2.2.2 Procedimento do método gráfico
As régras gerais para a resolução dos problemas de programação linear pelo método
gráfico, resumem-se nos passos:
Passo 1. Dado um problema de programação linear, deve-se relacionar a informação
contida no texto. Se necessário fazer uma tabela auxiliar para identificar as princi-
pais caracteŕısticas dos problemas de programação linear. As variáveis de decisão,
a função objectivo se é de maximização ou minimização e no fim o conjunto das
restrições.
Passo 2. Escrever o modelo económico matemático do problema conforme as in-
formações obtidas no passo 1 sem esquecer das restrições de não negatividade.
Passo 3. Calcular as coordenadas de dois pontos para cada recta incluindo a recta
da função objectivo e representar num sistema de eixos (atenção trocar x1 por x2 não
é permetido), indicando por uma secta a região solução para as inequações.
Passo 4. Traçar a recta da função objectivo e deslocar com rectas paralelas até ao
ponto máximo ou mı́nimo conforme o problema (ponto óptimo). Resolver o sistema
das rectas que intersectam no ponto óptimo. Note, que um problema de programação
linear pode ter um, dois ou mais pares de valores de (x1, x2), com o mesmo valor da
função objectivo. Um caso especial desta multiplicidade de soluções é quando a recta
da função objectvo é paralela a uma das rectas das restrições, neste caso a solução é
dada para um intervalo de valores de x1 e x2.
Passo 5. Usando as coordenadas do passo 4, calcular o valor da função objec-
tivo, apresentar e interpretar a solução em função do enunciado do problema original.
Exemplo 2.9. Usando o método gráfico resolva o seguinte problema de programação
linear.
Mulenga 30 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
maximizar Z = 3x1 + 6x2
sujeito à

2x1 + 2x2 ≤ 8
4x1 + 2x2 ≤ 12
0x1 + 3x2 ≤ 9
x1, x2 ≥ 0
Resolução
r1 : x1 x2
0 4
4 0
r2 : x1 x2
0 6
3 0
r3: x2 ≤ 3 rz: x2 = −
1
2
x1
rz : x1 x2
0 0
2 -1
Figura 2.5: Gráfico do exemplo 2.9
Pmax = r1 ∩ r3, portanto deve-se resolver o sistema 2x1 + 2x2 = 8 / : 20x1 + 3x2 = 9 / : 3 →
 x1 + x2 = 4x2 = 3 →
 x1 = 4− 3 = 1x2 = 3
Zmax = 3x1 + 6x2 = 3× 1 + 6× 3 = 21. A solução é: x1 = 1, x2 = 3, Zmax = 21.
Mulenga 31 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Exemplo 2.10. Usando o método gráfico resolva o seguinte problema de pro-
gramação linear.
minimizar W = 30x1 + 12x2
sujeito à

2x1 + 2x2 ≥ 6
2x1 + 2x2 ≤ 8
3x1 + 1x2 ≥ 4
x1, x2 ≥ 0
Resolução
Para a função objectivo: 30x1 + 12x2 = 0,→ x2 = −
30
12
x1 → x2 = −
5
2
x1.
r1 : x1 x2
0 3
3 0
r2 : x1 x2
0 4
4 0
r3 : x1 x2
0 4
4/3 0
rw : x1 x2
0 0
1 -5/2
Figura 2.6: Gráfico do exemplo 2.10
Mulenga 32 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Pmin = r1 ∩ r3 2x1 + 2x2 = 6 / : (−2)3x1 + 1x2 = 4 →
 −1x1 − 1x2 = −3+3x1 + 1x2 = 4
Depois de somar os coeficientes das duas equações, tem-se x1 =
1
2
, substituindo na
2a equação, tem-se x2 = 4− 3 ∗
1
2
=
5
2
.
O valor da função objectivo é: Wmin = 30×
1
2
+ 12× 5
2
= 45
Solução: x1 =
1
2
; x2 =
5
2
; Wmin = 45
2.2.3 Exerćıcios propostos
Exerćıcio 2.11. Uma carpintaria deseja estabelecer um programa diário de produção
dos seus artigos. Actualmente, a carpintaria faz apenas dois produtos: mesas e
armários, ambos de um só modelo. Para efeitos de simplificação, vamos considerar
que a carpintaria tem limitações em somente dois recursos: a madeira e a mão-de-
obra, cujas disponibilidades diárias são 12 m2 e 8 homens por hora (H.h), respecti-
vamente. O processo de produção é tal que, para fazer 1 mesa a fábrica gasta 2 m2
de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de
madeira 1 H.h de mão-de-obra. Além disso, o fabricante sabe que cada mesa dá uma
margem de contribúıção para o lúcro de 4 u.m, e cada armário, de 1 u.m.
a) Formule o modelo de programação linear que descreve este problema.
b) Usando o método gráfico, resolva o problema do fabricante de modo a encontrar
o programa de produção que maximiza a margem total de lúcro.
Resposta: x1 = 4; x2 = 0; Zmax = 16 u.m.
Exerćıcio 2.12. Uma indústria fabrica dois produtos A e B que utilizam três
matérias primas: madeira, quandidades de matéria prima em plástico e compos-
tos de aço. No estoque do armazém da fábrica estão dispońıveis 24 m2 de madeira,
37 unidades de plástico e 18 quilos de aço. O produto A requer 1, 3 e 2 unidades de
Mulenga 33 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
medida de cada uma das metérias primas madeira, plástico e aço respectivamente.
O produto B requer 3, 4 e 1 unidades de medida das mesmas matérias prima, res-
pectivamente. Se A é vendido por 20 u.m e B por 30 u.m, quantas unidades de cada
produto devem zer produzidas de modo a obter o máximo rendimento bruto. Elabore
o modelo e resolva-o gráficamente.
Resposta: x1 = 3; x2 = 7; Zmax = 270 u.m.
Exerćıcio 2.13. A companhia Cervejas de Moçambique precisa, de 90, 120 e 260
mil caixas de cerveja de alta, média e baixa qualidades, respectivamente. Existem
duas fábricas: a cerveja 2M que produz por dia 10, 30 e 40 mil caixas de alta, média
e baixa qualidades e a cerveja Laurentina que produz por dia 20, 10 e 30 mil caixas,
respectivamente. Se o custo operacional de cada fábrica for de 20 u.m por dia, du-
rante quantos dias deve funcionar cada fábrica de modo a se minimizar o custo total
e satisfazer as necessidades da companhia.
Resposta: x1 = 5; x2 = 2; Wmin = 140 u.m.
Exerćıcio 2.14. Um paciente de um determinado hospital necessita no mı́nimo de 84
unidades da substância 1 e 120 unidades de substância 2 por dia. Estas substâncias
são adquidas em dois tipos de medicamentos designados A e B. Um medicamento
do tipo A tem 10 unidades de substância 1 e 8 unidades de substância 2. O medi-
camento do tipo B contém 2 unidades da substância 1 e 4 unidades de substância
2. Sabendo que uma unidade do medicamento A custa 3 u.m e de B custa 1 u.m,
quantas unidades de cada medicamento A ou B, que o paciente deve comprar para
tomar por dia de modo que ele melhore e minimize o seu dinheiro. Qual é o valor
mı́nimo que ele vai gastar por dia.
Resposta: x1 = 4, x2 = 22, Wmin = 34 u.m.
Exerćıcio 2.15. Usando o método gráfico, resolva as seguintes aĺıneas dos pro-
blemas de programação linear.
Mulenga 34 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
maximizar Z = 5x1 + 5x2
a) sujeito à

2x1 + 1x2 ≤ 10
1x1 + 2x2 ≤ 8
x1, x2 ≥ 0
minimizar W = 10x1 + 30x2
b) sujeito à

2x1 + 2x2 ≥ 16
1x1 + 1x2 ≥ 12
1x1 + 2x2 ≥ 14
x1, x2 ≥ 0
maximizar Z = 25x1 + 30x2
c) sujeito à

2x1 + 2x2 ≤ 10
1x1 + 3x2 ≤ 10
1x1 + 2x2 ≤ 6
x1, x2 ≥ 0
minimizar W = 5x1 + 2x2
d) sujeito à

1x1 + 1x2 ≥ 6
6x1 + 3x2 ≥ 18
2x1 + 3x2 ≥ 12
x1, x2 ≥ 0
Respostas
a) x1 = 4, x2 = 2, Zmax = 30
b) x1 = 14, x2 = 0, Wmin = 140
c) x1 = 4, x2 = 1, Zmax = 130
d) x1 = 0, x2 = 6, Wmin = 12
2.3 Resolução dos problemas de programação li-
near pelo método simplex
O método simplex é um algoŕıtmo proposto por Dantzig (1947), para resolver os pro-
blemas de programação linear. Para uma aplicação correcta do método, é necessário
a introdução no modelo ora elaborado com apenas variáveis de decisão, variáveis
auxiliares.
2.3.1 Variáveis de folga e de excesso
Na resolução dos problemas de programação linear pelo método gráfico usou-se os si-
nais ≤ e ≥ nas inequações das restrições para definir a região ou domı́nio das soluções
e resolveu-se os problemas assumindo que todas variáveis eram não negativas. Nesta
Mulenga 35 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
secçãosão introduzidas duas variáveis auxiliares: as variáveis de folga e de excesso,
associadas com as restrições da forma ≤ e ≥ respectivamente.
Variável de folga. Introduz-se uma variável de folga, para cada restrição do tipo
≤ no primeiro membro da inequação e transfoma-se esta em equação. Por exemplo,
na restrição 6x1 + 4x2 ≤ 24, temos. 6x1 + 4x2 ≤ 24x1, x2 ≥ 0 →
 6x1 + 4x2 + x3 = 24x1, x2, x3 ≥ 0 →
 x3 = 24− 6x1 − 4x2x1, x2, x3 ≥ 0
A variável x3 é a variável de folga, ela representa a quantidade do recurso que não foi
utilizado, isto é, representa a diferença entre a quantidade do recurso máximo dis-
pońıvel (b = 24) e a quantidade de recusro que foi utilizado (6x1 +4x2) nas diferentes
actividades.
Variável de excesso. Restrições do tipo ≥, normalmente referem-se a quantidade
mı́nima necessária que deve ser utilizada na combinação de diferentes actividades. A
introdução de uma variável de excesso numa inequação, transforma esta em equação. 2x1 + 3x2 ≥ 80x1, x2 ≥ 0 →
 2x1 + 3x2 − x3 = 80x1, x2, x3 ≥ 0 →
 x3 = 2x1 + 3x2 − 80x1, x2, x3 ≥ 0
As variáveis de excesso representam o excesso da quantidade do recurso obtido pela
combinação das actividades em relação ao recurso mı́nimo necessário. Para este caso
x3 é variável de excesso.
Para que seja claro entre um problema com variáveis só de decisão e com variáveis
auxiliares, são definidas as designações. Um problema está na forma canónica, se
tiver só variáveis de decisão e todas desigualdades forem do mesmo sinal. Assim,
para maximização deverá ter ≤, enquanto, para minimização ≥. Um problema está
na forma padrão quando todas as inequações são transformadas em igualdades por
uma adição de uma variável auxiliar que pode ser de folga (+xi) ou de excesso (−xi).
Mulenga 36 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Exemplo 2.11. Escrever os seguintes problemas de programação linear na forma
padrão.
maximizar Z = 30x1 + 50x2
a) sujeito à

2x1 + 1x2 ≤ 16
1x1 + 2x2 ≤ 11
1x1 + 3x2 ≤ 15
x1, x2 ≥ 0
minimizar W = 3x1 + 2x2
b) sujeito à

5x1 + 1x2 ≥ 10
2x1 + 2x2 ≥ 12
1x1 + 4x2 ≥ 12
x1, x2 ≥ 0
Resolução
Como os problemas estão na forma canónica, basta acrescentar as variáveis de folga
ou de excesso.
a) max Z = 30x1+50x2+0x3+0x4+0x5
suj à

2x1 + 1x2 + 1x3 + 0x4 + 0x5 = 16
1x1 + 2x2 + 0x3 + 1x4 + 0x5 = 11
1x1 + 3x2 + 0x3 + 0x4 + 1x5 = 15
x1, x2, x3, x4, x5 ≥ 0
b) min W = 3x1 + 2x2 + 0x3 + 0x4 + 0x5
suj à

5x1 + 1x2 − 1x3 + 0x4 + 0x5 = 10
2x1 + 2x2 + 0x3 − 1x4 + 0x5 = 12
1x1 + 4x2 + 0x3 + 0x4 − 1x5 = 12
x1, x2, x3, x4, x5 ≥ 0
Observação
• Note que para cada restrição só temos uma variável de folga ou excesso, e nesta
restrição tem coeficiente 1 e zeros nas outras restrições ao longo da coluna.
• Como as variáveis de excesso e de folga são apenas auxiliares, elas não contri-
buem na função objectivo, por isso, tem coeficiente zero.
• Todas as variáveis de decisão e auxiliares são não negativas.
Mulenga 37 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
2.3.2 Procedimento do método simplex
O método simplex pode ser descrito como um procedimento matricial para resolver
problemas de programação linear na forma padrão.
Actualmente o método simplex é uma das ferramentas fundamentais de resolução
dos problemas de programação linear nos diversos casos em que eles se apresentam.
Neste caṕıtulo, são apresentadas três variantes. O método simplex directo que per-
mite resolver apenas os problemas de maximização na sua forma canónica, em seguida
serão apresentados o método simplex de duas fases e o método simplex de Grande M.
O método simplex dual-simplex será apresentado mais tarde no caṕıtulo 4. Deve-se
salientar que, em qualquer uma das variantes pode se destacar 4 etapas fundamentais
do método simplex.
1. Tabela simplex inicial. A tabela simplex inicial de um problema de ma-
ximização de programação linear como apresentado na subsecção 2.1.2 é como se
segue.
Tabela 2.6: Estrutura básica de uma tabela simplex inicial
variáveis básicas x1 x2 ... xm xm+1 xm+2 ... xm+n recursos
xm+1 a11 a12 ... a1m 1 0 ... 0 b1
xm+2 a21 a22 ... a2m 0 1 ... 0 b2
... ... ... ... ... ... ... ... ... ...
xm+n an1 an2 ... anm 0 0 ... 1 bn
Z −c1 −c2 ... −cm 0 0 ... 0 0
• Da tabela inicial, nota-se que as variáveis básicas (base) são todas variáveis de
folga e tem 1 ao longo da linha em que estão;
• Os coeficientes ci, são opostos da função objectivo e são importantes na in-
dicação da coluna pivô, por isso, são chamados indicadores da coluna pivô;
Mulenga 38 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
• O elemento no canto inferior direito é zero, ele corresponde ao valor da função
objectivo inicial.
2. Determinação do elemento pivô. Um elemento pivô de uma tabela simplex
é obtido da seguinte forma.
• Escolhe-se na linha dos coeficientes da função objectivo, o menor elemento
negativo (max) ou o maior elemento positivo (min), e a coluna que contém este
elemento chama-se coluna pivô: cp = min{−cj};
• Divide-se cada termo independente (recurso), pelo correspondente elemento
positivo da coluna pivô. A linha que apresentar o menor quociente positivo é
chamada linha pivô: lp = min
{
bi
aij
}
para aij > 0 e aij ∈ cp;
• O elemento que situa-se no cruzamento entre a linha pivô e a coluna pivô é
chamado elemento pivô: ep = cp × lp.
Se a tabela não tiver nenhum indicador negativo (max) ou positivo (min), esta é uma
tabela terminal e não tem pivô.
3. Cálculo da nova tabela simplex. Seja T1 a tabela simplex com n linhas
e m+n colunas, cujo elemento pivô é aij da matrix A. Uma nova tabela T2 é calcu-
lada a partir da tabela T1, usando operações elementares sobre as linhas da matriz
A de tal forma que apareça um ”1”na posição pivô e zeros ”0”nas outras posições
da coluna pivô, isto é:
• Divide-se cada elemento da linha pivô lp da tabela T1 pelo elemento pivô aij,
obtendo-se a correspondente linha na tabela T2 (l′p). l
′
p =
1
aij
∗ lp. Observe que
na posição do elemento pivô terá sempre “1” depois desta divisão.
• Se a coluna pivô de T1 é denotada por xi, então a correspondente coluna de T2,
será denotada também por xi e não é permetida a troca da ordem das linhas
na nova tabela.
Mulenga 39 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
• Cada uma das outras linhas l′k da tabela T2 é obtida somando da linha lk o
produto−akjl′p, onde o−akj é o elemento akj da coluna pivô com sinal contrário.
Isto é: l′k = lk − akj × l′p, para k = 1, 2, . . . , n.
4. Interpretação da tabela terminal. Depois de tantas repetições das etapas (2)
e (3), chega-se a uma tabela terminal, a qual não tem nenhum indicador da coluna
pivô negativo (max) ou positivo (min).
Tabela 2.7: Estrutura de uma tabela terminal simplex
Base x1 x2 ... xm xm+1 xm+2 ... xm+n recursos
x1 1 0 ... a1m∗ a1(m+1)∗ a1(m+2)∗ ... 0 b1∗
x2 0 1 ... a2m∗ a2(m+1)∗ a2(m+2)∗ ... 0 b2∗
... ... ... ... ... ... ... ... ... ...
xm+n 0 0 ... anm∗ an(m+1)∗ an(m+2)∗ ... 1 bn∗
Z 0 0 ... cm∗ cm+1∗ cm+2∗ ... 0 z*
Na Tabela 2.7 o sinal (*) indica de que os valores já não são os mesmos da tabela
inicial 2.6. Também pode notar de que as variáveis que estão na base foram trocadas.
Este é resultado das iterações que foram feitas.
• z∗ – é o valor óptimo da função objectivo;
• xi – tem um valor diferente de zero se estiver marcado por 1 numa única posição
da coluna correspondente e zeros nas restantes linhas e diz-se que xi está na
base. É o caso das variáveis x1, x2, ..., xm+n.
• xi - é igual a zero se não estiver na base, apresentando óbviamente um ci 6= 0.
• Assim, a solução seria: x1 = b∗1, x2 = b∗2,..., xm+n = b∗n, Zmax = z∗ e todas
variáveis que estão fora da basesão iguais a zero.
Mulenga 40 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Exemplo 2.12. Resolva o seguinte problema de programação linear pelo método
simplex.
maximizar Z = 1x1 + 9x2 + 1x3
sujeito à

1x1 + 2x2 + 3x3 ≤ 9
3x1 + 2x2 + 2x3 ≤ 15
x1, x2, x3 ≥ 0
Resolução
O problema já está na forma canônica, portanto, vai-se introduzir as variáveis de
folga.
maximizar Z = 1x1 + 9x2 + 1x3 + 0x4 + 0x5
sujeito à

1x1 + 2x2 + 3x3 + 1x4 + 0x5 = 9
3x1 + 2x2 + 2x3 + 0x4 + 1x5 = 15
x1, x2, x3, x4, x5 ≥ 0
Tabela 1
Base x1 x2 x3 x4 x5 Bi
x4 1 2 3 1 0 9; (9/2=4.5, min) J
x5 3 2 2 0 1 15 (15/2=7.5)
Z -1 -9 -1 0 0 0
min N
Como o elemento pivô é a12 = 2 na linha 1, coluna 2, mostra-se em seguida as
operações que foram feitas para a coluna 2 de x2 e todas outras colunas seguem as
mesmas equações das linhas.
Linha 1: l′p = (1/2)× lp =
1
2
× 2 = 1
Linha 2: l′2 = l2 − 2× l′p = 2− 2× 1 = 0
Linha 3: l′3 = l3 + 9× l′p = −9 + 9× 1 = 0
Mulenga 41 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Tabela 2
Base x1 x2 x3 x4 x5 Bi Transformação
x2 1/2 1 3/2 1/2 0 9/2 l
′
p = (1/2)× lp
x5 2 0 -1 -1 1 6 l
′
2 = l2 − 2× l′p
Z 7/2 0 25/2 9/2 0 81/2 l′3 = l3 + 9× l′p
Solução
Zmax =
81
2
, x1 = 0 , x2 =
9
2
, x3 = x4 = 0, x5 = 6
Os valores da função objectivo e das variáveis de folga podem ser obtidos substi-
tuindo os valores de x1, x2 e x3 na função objectivo e nas restrições.
• Função objectivo: Zmax = 1x1 + 9x2 + 1x3 = 1× 0 + 9×
9
2
+ 1× 0 = 81
2
• Restrição 1: x4 = 9− 1x1 − 2x2 − 3x3 = 9− 1× 0− 2×
9
2
–1× 0 = 9− 9 = 0
• Restrição 2: x5 = 15–3x1–2x2 − 2x3 = 15–2× 0− 2×
9
2
− 2× 0 = 15− 9 = 6
Desta verificação, significa que para produzir 4.5 unidades de x2 foram utilizadas
completamente 9 uniddaes de recurso 1 e 9 unidades de recurso 2, não sendo utiliza-
das 6 unidades que correspondem a diferença 15-9=6 unidades do recurso 2.
Exemplo 2.13. Usando o método simplex resolva o seguinte problema de pro-
gramação linear.
maximizar Z = 6x1 + 4x2
sujeito à

4x1 + 6x2 ≤ 12
6x1 + 2x2 ≤ 24
2x1 + 1x2 ≤ 10
x1, x2 ≥ 0
Mulenga 42 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Resolução
Introduzindo as variáveis de folga tem-se.
maximizar Z = 6x1 + 4x2 + 0x3 + 0x4 + 0x5
sujeito à

4x1 + 6x2 + 1x3 + 0x4 + 0x5 = 12
6x1 + 2x2 + 0x3 + 1x4 + 0x5 = 24
2x1 + 1x2 + 0x3 + 0x4 + 1x5 = 10
x1, x2, x3, x4, x5 ≥ 0
Tabela 1
Base x1 x2 x3 x4 x5 Bi
x3 4 6 1 0 0 12 (12/4=3, min)J
x4 6 2 0 1 0 24 (24/6=4)
x5 2 1 0 0 1 10 (10/2=5)
Z -6 -4 0 0 0 0
N
Repare que na tabela inicial, a coluna pivô é a coluna 1, e como tem o valor mı́nimo
na primeira linha, o elemento pivô foi escolhido na primeira linha. Como o elemento
pivô está na primeira linha, começa-se por esta linha a transformar e só depois as
outras linhas.
Tabela 2
Base x1 x2 x3 x4 x5 Bi Transformação
x1 1 3/2 1/4 0 0 3 l
′
p = (1/4)× lp
x4 0 -7 -3/2 1 0 6 l
′
2 = l2 − 6× l′p
x5 0 -2 -1/2 0 1 4 l
′
3 = l3 − 2× l′p
Z 0 5 3/2 0 0 18 l′4 = l4 + 6× l′p
Mulenga 43 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Solução x1 = 3, x2 = 0, x3 = 0, x4 = 6, x5 = 4, Zmax = 18.
Verificando o valor da função objectivo: Z = 6x1 + 4x2 = 6 × 3 + 4 × 0 = 18, o
que confirma o valor que está na tabela óptima.
Exemplo 2.14. Resolva o seguinte problema de programação linear pelo método
simplex.
maximizar Z = 8x1 + 6x2
sujeito à

6x1 + 3x2 ≤ 9
2x1 + 2x2 ≤ 4
1x1 + 2x2 ≤ 8
x1, x2 ≥ 0
Resolução
Tabela 1
Base x1 x2 x3 x4 x5 Bi
x3 6 3 1 0 0 9 (9/6=1.5)J
x4 2 2 0 1 0 4 (4/2=2)
x5 1 2 0 0 1 8 (8/1=8)
Z -8 N -6 0 0 0 0
Por comodidade, em vez de escrever sempre l′p vai-se escrever o número da linha em
que estiver o elemento pivô, por exemplo l′1.
Mulenga 44 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Tabela 2
Base x1 x2 x3 x4 x5 Bi Transformação
x1 1 1/2 1/6 0 0 3/2 l
′
1 = (1/6)× l1 (3)
x4 0 1 -1/3 1 0 1 l
′
2 = l2 − 2× l′1 (1) J
x5 0 3/2 -1/6 0 1 13/2 l
′
3 = l3 − 1× l′1 (13/3)
Z 0 -2N 4/3 0 0 12 l′4 = l4 + 8× l′1
Tabela 3
Base x1 x2 x3 x4 x5 Bi Transformação
x1 1 0 1/3 -1/2 0 1 l
′
1 = l1 − (1/2)× l′2
x2 0 1 -1/3 1 0 1 l
′
2 = l2
x5 0 0 1/3 -3/3 1 5 l
′
3 = l3 − 3/2× l′2
Z 0 0 2/3 2 0 14 l′4 = l4 + 2× l′2
Solução x1 = 1, x2 = 1, x3 = 0, x4 = 0, x5 = 5, com Zmax = 14
2.3.3 Método simplex de duas fases
O processo iterativo do método simplex sempre exige uma solução básica inicial onde
para cada linha existe uma variável básica, a partir da qual se procura melhorar até
uma solução óptima. Nos problemas de maximização esta solução básica inicial era
formada pelas variáveis de folga, já que as restrições eram do tipo (≤). Quando as
restrições são do tipo (≥) ou (=), não existe essa solução básica inicial, como se
ilustra no exemplo a seguir:
minimizar W = 5x1 + 2x2
sujeito à

1x1 + 1x2 ≥ 5
6x1 + 1x2 ≥ 18
2x1 + 3x2 ≥ 12
x1, x2 ≥ 0
Mulenga 45 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Introduzindo as varáveis de excesso, tem-se a seguinte tabela.
Base x1 x2 x3 x4 x5 Bi
x3(-) 1 1 -1 0 0 5
x4(-) 6 1 0 -1 0 18
x5(-) 2 3 0 0 -1 12
W -5 -2 0 0 0 0
Nesta tabela, as variáveis de excesso x3, x4 e x5 tem valores negativos se pretender-
mos ler a solução inicial deste exemplo (x3 = −5, x4 = −18, x5 = −12), violando a
condição de não negatividade. Para não violar esta restrição, diz-se que esta tabela
é preliminar e não básica porque não possue solução básica.
Para resolver este tipo de problemas são introduzidas algumas modificações nas
equações das restrições em seguida pode se usar duas variantes do método simplex:
o método simplex de duas fases, e o método simplex de grande M.
Tabela 2.8: Variáveis auxiliares para os métodos de duas fases e de grande M
Tipo de inequação Tipo de variável Variável
≤ variável de folga xi
= variável artificial ai
≥ variável de excesso + artificial −xi + ai
Procedimento do método simplex de duas fases
Para resolver os problemas de programação linear pelo método simplex de duas fases
segue-se os seguintes passos:
Mulenga 46 acm@2020
m
um
ub
et
o8
@
gm
ai
l.c
om
Investigação Operacional
Passo 1. Para cada restrição, introduzir as variáveis de folga, excesso e artificiais
conforme a Tabela 2.8 indica.
Passo 2. Escrever uma nova função objectivo, segundo os passos:
• Para cada variável xi, deve-se somar os coeficientes das restrições que possuem
alguma variável artificial e multiplicar por (-1) o resultado, por exemplo para
a coluna de x1 teria c
′
1 = −1(a11 + a21 + a31) = −(a11 + a21 + a31).
• As colunas das váriaveis artificiais ficam com zeros, para garantir que a tabela
inicial tenha solução básica.
• Na função objectivo, também somam-se os recursos das restrições onde introduziu-
se alguma variável artificial e multiplicar o resultado por (-1) como está exem-
plificado, Za = −(b1 + b2 + b3).
• A esta função objectivo é designada Za, portanto é uma função maximizante.
Passo 3. Organizada a tabela inicial, as variáveis artificiais e de folga se existirem
estarão na base. E esta é a tabela básica da primeira fase.
Passo 4. Resolver o problema pelo método simplex, tomando-se como função objec-
tivo a última linha da função de maximização até que na linha Za, haja nas colunas
de xi, ∀ci = 0, nas colunas de ai, ∀ci = 1 e Za = 0. Este é o fim da primeira fase.
Como na última linha o valor da função objectivo artificial é igual a zero, a pri-
meira fase termina. Em seguida as variáveis artificiais e a linha Za são retiradas, a
tabela que fica dá o ińıcio da segunda fase.
• Para os problemas de maximização, se existir algum elemento negativo na linha
indicadora de pivô, as iterações devem continuar até obter a solução óptima.
• Para os problemas