Apostila - Métodos e Modelos Quantitativos de Decisão

Prévia do material em texto

Me´todos e modelos quantitativos de Decisa˜o 1
Departamento de Administrac¸a˜o
Profo Pedro Henrique Melo Albuquerque
12 de Julho de 2011
Conteu´do
Conteu´do i
1 Introduc¸a˜o. 3
1.1 Conceito. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Histo´ria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Modelagem de problemas gerenciais. . . . . . . . . . . . . . . . . . . 9
1.2.1 O processo de modelagem . . . . . . . . . . . . . . . . . . . . 9
1.3 Modelagem com planilhas. . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Otimizac¸a˜o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Incerteza. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Aplicac¸o˜es avanc¸adas de simulac¸o˜es. . . . . . . . . . . . . . . . . . . . 13
1.7 Previso˜es. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8 Exerc´ıcios: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Modelagem com planilhas. 15
2.1 Modelos anal´ıticos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Planilhas eletroˆnicas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Func¸o˜es no Excel. . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Programac¸a˜o Linear. 23
3.1 Programac¸a˜o Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 Varia´veis de folga. . . . . . . . . . . . . . . . . . . . . . . . . . 25
i
ii CONTEU´DO
3.1.2 Varia´veis de excesso. . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3 Varia´veis livres . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Formulac¸a˜o dos problemas . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Exemplo de formulac¸a˜o. . . . . . . . . . . . . . . . . . . . . . 29
3.3 Soluc¸a˜o gra´fica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Me´todo simplex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.2 Empate para a varia´vel ba´sica entrando. . . . . . . . . . . . . 43
3.4.3 Empate para a varia´vel ba´sica saindo (Degenerac¸a˜o). . . . . . 43
3.4.4 Varia´vel ba´sica saindo inexistente - Z Ilimitado. . . . . . . . . 44
3.5 Restric¸o˜es na forma de igualdade. . . . . . . . . . . . . . . . . . . . . 45
3.5.1 Restric¸o˜es na forma: Maior ou igual. . . . . . . . . . . . . . . 47
3.5.2 Problemas de minimizac¸a˜o. . . . . . . . . . . . . . . . . . . . 48
3.6 Resoluc¸a˜o atrave´s do Solver. . . . . . . . . . . . . . . . . . . . . . . . 52
3.7 Problemas de alocac¸a˜o de recursos. . . . . . . . . . . . . . . . . . . . 55
3.8 Exerc´ıcios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4 Ana´lise de sensibilidade e o problema dual. 67
4.1 Interpretac¸a˜o econoˆmica do problema dual. . . . . . . . . . . . . . . . 78
4.1.1 Prec¸o-Sombra . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.2 Custo reduzido . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Problemas t´ıpicos de programac¸a˜o linear. 85
5.1 Ana´lise Envolto´ria de Dados . . . . . . . . . . . . . . . . . . . . . . . 85
5.2 Teoria dos jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.1 Estrate´gias o´timas . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3 Financ¸as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.4 Gesta˜o de pessoas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4.1 Restric¸o˜es de nu´mero de funciona´rios por dia. . . . . . . . . . 100
CONTEU´DO iii
5.4.2 Modelo matema´tico. . . . . . . . . . . . . . . . . . . . . . . . 101
5.5 Produc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.6 Restric¸o˜es de armazenamento. . . . . . . . . . . . . . . . . . . . . . . 103
5.7 Restric¸o˜es de vendas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.8 Marketing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.9 Modelos de redes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.9.1 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.9.2 Problemas de transporte . . . . . . . . . . . . . . . . . . . . . 107
5.9.3 Problemas de atribuic¸a˜o. . . . . . . . . . . . . . . . . . . . . . 113
5.10 Exerc´ıcios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6 Programac¸a˜o Inteira. 123
6.1 Soluc¸a˜o gra´fica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.2 Exemplo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2.1 Soluc¸a˜o no Excel. . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2.2 Soluc¸a˜o no Lindo. . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7 Programac¸a˜o na˜o-linear. 133
7.1 Maximizac¸a˜o de receita . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.2 Ajuste de curvas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.2.1 Ana´lise de regressa˜o . . . . . . . . . . . . . . . . . . . . . . . 138
7.3 Localizac¸a˜o de instalac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . 141
7.4 Tamanho do lote econoˆmico . . . . . . . . . . . . . . . . . . . . . . . 143
7.5 Soluc¸a˜o gra´fica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7.6 Soluc¸a˜o anal´ıtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.6.1 Exemplo de formulac¸a˜o de um problema de programac¸a˜o na˜o-
linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.6.2 Mı´nimos globais e locais de uma func¸a˜o . . . . . . . . . . . . . 148
7.6.3 Revisa˜o de ca´lculo - Derivada . . . . . . . . . . . . . . . . . . 149
7.6.4 Multiplicadores de Lagrange . . . . . . . . . . . . . . . . . . . 150
iv CONTEU´DO
7.6.5 Condic¸o˜es de Kuhn – Tucker . . . . . . . . . . . . . . . . . . . 152
7.7 Soluc¸a˜o usando Solver . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.8 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8 Simulac¸a˜o de Monte Carlo. 159
8.1 Varia´veis aleato´rias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.1.1 Espac¸o Amostral . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.1.2 Eventos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2 Varia´veis aleato´rias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.3 Distribuic¸o˜es de probabilidade . . . . . . . . . . . . . . . . . . . . . . 165
8.3.1 Func¸o˜es densidade de probabilidade . . . . . . . . . . . . . . . 168
8.4 Medidas de incerteza . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4.1 Me´dia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4.2 Moda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4.3 Mediana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4.4 Variaˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.4.5 Desvio-Padra˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.5 Teorema do limite central . . . . . . . . . . . . . . . . . . . . . . . . 177
8.6 Gerac¸a˜o de nu´meros aleato´rios . . . . . . . . . . . . . . . . . . . . . . 178
8.7 Simulac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.8 Exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
8.8.1 Simulac¸a˜o de Monte Carlo . . . . . . . . . . . . . . . . . . . . 186
8.9 Componentes de simulac¸a˜ono Excel . . . . . . . . . . . . . . . . . . 187
8.9.1 XLSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.9.2 RiskSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.9.3 Crystal Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
8.10 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
9 Problemas avanc¸ados de simulac¸a˜o. 197
9.1 Simulac¸a˜o parametrizada . . . . . . . . . . . . . . . . . . . . . . . . . 197
CONTEU´DO v
9.2 Volatilidade e dependeˆncia estat´ıstica . . . . . . . . . . . . . . . . . . 199
9.2.1 Tipos de volatilidade . . . . . . . . . . . . . . . . . . . . . . . 200
9.2.2 Ca´lculo da volatilidade histo´rica . . . . . . . . . . . . . . . . . 201
9.2.3 Dependeˆncia estat´ıstica . . . . . . . . . . . . . . . . . . . . . . 201
9.3 Carteiras de investimentos correlacionados . . . . . . . . . . . . . . . 203
9.3.1 Simulac¸o˜es para formac¸a˜o de portfolios . . . . . . . . . . . . . 205
9.4 Testes de hipo´teses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10 Previso˜es. 215
10.1 Previso˜es causais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
10.2 Regressa˜o Linear e Se´ries Temporais . . . . . . . . . . . . . . . . . . 216
10.2.1 Regressa˜o Linear . . . . . . . . . . . . . . . . . . . . . . . . . 216
10.2.2 Se´ries temporais . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.3 Suavizac¸a˜o Exponencial . . . . . . . . . . . . . . . . . . . . . . . . . 224
10.4 Simulac¸a˜o de Monte Carlo em previso˜es . . . . . . . . . . . . . . . . . 226
11 PERT/CPM. 227
11.1 Construc¸a˜o da rede do projeto . . . . . . . . . . . . . . . . . . . . . . 229
11.2 Caminho cr´ıtico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11.3 Programando um projeto com PERT/CPM . . . . . . . . . . . . . . 233
11.4 Lidando com atividades com durac¸o˜es incertas . . . . . . . . . . . . . 237
.1 Revisa˜o de matema´tica. . . . . . . . . . . . . . . . . . . . . . . . . . 239
.1.1 Prioridades de operac¸a˜o. . . . . . . . . . . . . . . . . . . . . . 239
.1.2 Multiplicac¸a˜o de frac¸o˜es. . . . . . . . . . . . . . . . . . . . . . 240
.1.3 Divisa˜o de frac¸o˜es. . . . . . . . . . . . . . . . . . . . . . . . . 241
.1.4 Radiciac¸a˜o e Potenciac¸a˜o. . . . . . . . . . . . . . . . . . . . . 242
.1.5 Desigualdades . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
.1.6 Exerc´ıcios de revisa˜o de ca´lculo. . . . . . . . . . . . . . . . . . 243
Bibliografia 259
vi CONTEU´DO
Lista de Figuras
2.1 Caixa-Preta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Diagrama de influeˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Exemplo Excel 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1 Regia˜o de soluc¸o˜es via´veis. . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Soluc¸a˜o o´tima. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Todos os pontos do segmento de reta sa˜o soluc¸o˜es. . . . . . . . . . . . 34
3.4 Soluc¸o˜es ilimitadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Semi-retas contendo todos os pontos. . . . . . . . . . . . . . . . . . . 35
3.6 Na˜o ha´ soluc¸a˜o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 Algoritmo para soluc¸a˜o anal´ıtica. . . . . . . . . . . . . . . . . . . . . 36
3.8 Modelagem do problema da Wyndor Glass Co. no Excel. . . . . . . . 53
3.9 Func¸a˜o Solver no Excel. . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.10 Paraˆmetros para o Solver do Excel. . . . . . . . . . . . . . . . . . . . 54
3.11 Opc¸o˜es do Solver no Excel. . . . . . . . . . . . . . . . . . . . . . . . . 55
3.12 Resultados obtido pelo Solver. . . . . . . . . . . . . . . . . . . . . . . 55
8.1 Exemplo de func¸a˜o de distribuic¸a˜o acumulada (FDA). . . . . . . . . . 169
8.2 Func¸a˜o massa de probabilidade para a Binomial. . . . . . . . . . . . . 171
8.3 Func¸a˜o distribuic¸a˜o acumulada para a Binomial. . . . . . . . . . . . . 171
8.4 Func¸a˜o massa de probabilidade para a Geome´trica. . . . . . . . . . . 171
8.5 Func¸a˜o distribuic¸a˜o acumulada para a Geome´trica. . . . . . . . . . . 171
8.6 Func¸a˜o massa de probabilidade para a Poisson. . . . . . . . . . . . . 172
vii
viii LISTA DE FIGURAS
8.7 Func¸a˜o distribuic¸a˜o acumulada para a Poisson. . . . . . . . . . . . . . 172
8.8 Func¸a˜o massa de probabilidade para a Uniforme Discreta. . . . . . . 173
8.9 Func¸a˜o distribuic¸a˜o acumulada para a Uniforme Discreta. . . . . . . . 173
8.10 Func¸a˜o massa de probabilidade para a Uniforme Cont´ınua. . . . . . . 174
8.11 Func¸a˜o distribuic¸a˜o acumulada para a Uniforme Cont´ınua. . . . . . . 174
8.12 Func¸a˜o massa de probabilidade para a Exponencial. . . . . . . . . . . 175
8.13 Func¸a˜o distribuic¸a˜o acumulada para a Exponencial. . . . . . . . . . . 175
8.14 Func¸a˜o massa de probabilidade para a Normal. . . . . . . . . . . . . 175
8.15 Func¸a˜o distribuic¸a˜o acumulada para a Normal. . . . . . . . . . . . . . 175
8.16 Exemplo de histograma. . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.17 Exemplo de tabela aleato´ria. . . . . . . . . . . . . . . . . . . . . . . . 179
9.1 Fronteira de Markowitz. . . . . . . . . . . . . . . . . . . . . . . . . . 207
11.1 Rede do projeto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11.2 Rede do projeto com tempos ES e EF. . . . . . . . . . . . . . . . . . 235
11.3 Rede do projeto com tempos LS e LF. . . . . . . . . . . . . . . . . . 237
11.4 Distribuic¸a˜o Beta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Lista de Tabelas
4.1 Relac¸a˜o entre Dual e Primal. . . . . . . . . . . . . . . . . . . . . . . . 76
5.1 Exemplo de dados para ana´lise envolto´ria. . . . . . . . . . . . . . . . 89
9.1 Distribuic¸a˜o normal padra˜o. . . . . . . . . . . . . . . . . . . . . . . . 210
9.2 Distribuic¸a˜o uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
11.1 Caminhos poss´ıveis para conclusa˜o do projeto. . . . . . . . . . . . . . 232
1
2 LISTA DE TABELAS
Cap´ıtulo 1
Introduc¸a˜o.
3
4 CAPI´TULO 1. INTRODUC¸A˜O.
1.1 Conceito.
Os problemas da tomada de decisa˜o sa˜o comuns em uma infinidade de a´reas tanto
pu´blicas quanto privadas e desde tempos remotos o homem tenta resolveˆ-los apoiando-
se nas informac¸o˜es dispon´ıveis.
Geralmente, os problemas de tomada de decisa˜o possuem pelo menos uma das
caracter´ısticas a seguir:
• Os crite´rios de resoluc¸a˜o do problema sa˜o, no mı´nimo, dois que conflitam entre
si.
• Tanto os crite´rios como as alternativas na˜o esta˜o claramente definidos, e as
consequeˆncias da escolha de uma determinada alternativa, com relac¸a˜o a pelo
menos um crite´rio na˜o sa˜o devidamente compreendidas.
• A soluc¸a˜o do problema depende de um conjunto de pessoas, cada uma com
seu pro´prio ponto de vista, muitas vezes conflitante com o das demais pessoas.
• As restric¸o˜es do problema na˜o esta˜o bem definidas, podendo existir du´vidas a
respeito do que e´ crite´rio e do que e´ restric¸a˜o.
• Alguns dos crite´rios sa˜o quantifica´veis, enquanto outros somente o sa˜o por
meio de ju´ızos de valor efetuados sobre uma escala.
• A escala para um determinado crite´rio pode ser cardinal, verbal ou ordinal,
dependendo dos dados dispon´ıveis e da pro´pria natureza dos crite´rios.
1.1.1 Histo´ria
Historicamente, os administradores veˆm considerando a modelagem para a tomada
de decisa˜o de maneiras diferentes.
Inicialmente, as deciso˜es eram tomadas com base na intuic¸a˜o (feeling) do ad-
ministrador, entretanto, o homem como ser limitado na˜o e´ capaz de avaliar mu´ltiplasvaria´veis em um problema.
A tomada de decisa˜o para resoluc¸a˜o de problemas, ate´ a primeira metade
do se´culo XX, utilizava basicamente a esperanc¸a matema´tica para a tomada de
deciso˜es em condic¸o˜es aleato´rias; pore´m, em muitas situac¸o˜es, observava-se que o
risco associado ao procedimento era inaceita´vel.
Com o fim da Segunda Guerra Mundial, em func¸a˜o da experieˆncia obtida
pelas Forc¸as Aliadas sobre problemas log´ısticos-militares, um grande nu´mero de
1.1. CONCEITO. 5
organizac¸o˜es de pesquisa dedicou-se a` ana´lise e a preparac¸a˜o de deciso˜es, usando a
enta˜o recente Pesquisa Operacional.
A partir disso, surge a necessidade imediata de otimizar custos, gastos e lucros.
Com esse objetivo, desenvolveram-se diversos me´todos estritamente matema´ticos
para que se encontre a soluc¸a˜o o´tima de um problema.
Esses me´todos fazem parte da otimizac¸a˜o cla´ssica e muitos deles ainda sa˜o
utilizados atualmente em uma se´rie de aplicac¸o˜es tais como alocac¸a˜o de carga, esta-
belecimento de caminho mı´nimo, otimizac¸a˜o de inventa´rio, etc.
Histo´ria da pesquisa operacional
Ao longo da histo´ria e´ frequente encontrar colaborac¸a˜o entre cientistas e as forc¸as
armadas com o mesmo objetivo: Tomar a decisa˜o o´tima em uma batalha.
De fato, muitos estudiosos consideram o nascimento da Pesquisa Opera-
cional no se´culo 3 a.c., durante a 2o Guerra Pu´nica1, com a ana´lise e soluc¸a˜o que
Arquimedes propoˆs para a defesa da cidade de Siracusa, sitiada pelos romanos.
Entre as suas invenc¸o˜es esta˜o a catapulta e um sistema de espelhos que in-
cendiava os barcos inimigos focando e intensificando a luz do sol nas velas desses
barcos.
Leornado DaVinci participou, em 1503, como engenheiro na guerra contra
Prisa devido ao seu conhecimento sobre te´cnicas para realizar bombardeios, con-
struc¸a˜o de navios, ve´ıculos blindados, canho˜es, catapultas, e outros aparatos be´licos.
Outro antecedente do uso da Pesquisa Operacional vem de F.W. Lanchester,
que fez um estudo matema´tico sobre a poteˆncia bal´ıstica dos adversa´rios.
Ele desenvolveu, a partir de um sistema de equac¸o˜es diferenciais a Lei do
quadrado de Lanchester, de modo que e´ poss´ıvel determinar o resultado de uma
batalha militar com base no conhecimento a priori de algumas informac¸o˜es.
Thomas Edison fez uso da Pesquisa Operacional, contribuindo na guerra
contra os submarinos, com suas grandes ide´ias, como escudos contra torpedos para
os navios.
Do ponto de vista matema´tico, nos se´culos XVII e XVIII, Newton, Leibniz,
1As Guerras Pu´nicas consistiram numa se´rie de treˆs guerras que opuseram a Repu´blica Romana
e a Repu´blica de Cartago, cidade-estado fen´ıcia, no per´ıodo entre 264 a.C. e 146 a.C.. Tanto Roma
quanto a Cartago disputavam a hegemonia do Mar Mediterraˆneo, como meio de transporte de
mercadorias. As guerras tiveram como origem a rivalidade entre Roma e Cartago, que se assumia
como um centro econoˆmico, pol´ıtico e militar da regia˜o do Mar Mediterraˆneo ocidental. Ao fim
das Guerras Pu´nicas, Cartago foi totalmente destru´ıda.
6 CAPI´TULO 1. INTRODUC¸A˜O.
Bernoulli e Lagrange, trabalharam na obtenc¸a˜o de ma´ximos e mı´nimos condi-
cionados a certas func¸o˜es.
O matema´tico franceˆs Jean Baptiste Joseph Fourier esboc¸ou me´todos que an-
tecedem a Programac¸a˜o Linear moderna. E ao final do se´culo XVIII, Gaspar
Monge definiu os precedentes do me´todo gra´fico, grac¸as ao seu desenvolvimento
da Geometria Descritiva.
Janos Von Neumann publicou uma obra intitulada “Teoria dos Jogos”, essa
forneceu os princ´ıpios matema´ticos para Programac¸a˜o Linear. Em 1947, ele viu
a semelhanc¸a entre os problemas de Programac¸a˜o Linear e da teoria de matriz
que ele pro´prio desenvolveu.
Em 1939, o matema´tico russo L. Kantorovich, em associac¸a˜o com o matema´tico
holandeˆs T. Koopmans, desenvolveu a teoria matema´tica chamada Programac¸a˜o
Linear, grac¸as a esse estudo esse foi recompensado com o preˆmio Nobel.
Nos u´ltimos 30 anos, George Joseph Stigler apresentou um problema partic-
ular, conhecido como dieta especial ideal ou mais comumente conhecido como o
problema da dieta, que foi motivado grac¸as a uma preocupac¸a˜o do exe´rcito E.U.A.
para garantir alguns pedidos nutricionais ao menor custo para suas tropas.
Foi resolvido com um me´todo heur´ıstico em que a soluc¸a˜o so´ difere em algumas
unidades contra a soluc¸a˜o moderna, gerada pelo Me´todo Simplex.
Entre 1941 e 1942, Kantorovich e Koopmans estudaram de forma indepen-
dente, o problema de transporte pela primeira vez, esse tipo de problema foi enta˜o
denominado como o problema da Koopmans-Kantorovich. Para sua soluc¸a˜o, eles us-
aram me´todos geome´tricos que esta˜o relacionados com a teoria de Minkowski sobre
convexidade.
Mas em geral, na˜o se considera o nascimento da cieˆncia chamada Pesquisa
Operacional ate´ a II Guerra Mundial, durante uma batalha contra a Inglaterra, a
forc¸a a´rea alema˜ subjugou os ingleses em um ataque ae´reo r´ıgido, uma vez que os
ingleses tinham uma forc¸a a´rea fraca, apesar da vasta experieˆncias em combate.
O governo britaˆnico, em busca de algum me´todo para defender seu pa´ıs, convo-
cou va´rios cientistas de va´rias disciplinas, para tentar resolver o problema de obter
o ma´ximo de benef´ıcio para os radares.
Grac¸as ao seu trabalho em determinar a localizac¸a˜o o´tima de antenas eles
tiveram uma melhor distribuic¸a˜o de sinais dobrando assim a efica´cia do sistema de
defesa ae´rea.
Para perceber a escala desta nova disciplina, a Inglaterra criou um outro grupo
de mesma natureza, a fim de obter melhores resultados na disputa.
Semelhantemente, o Estados Unidos da Ame´rica (E.U.A.), quando entrou na
1.1. CONCEITO. 7
guerra em 1942, criou o projeto SCOOP (Scientific Computation of Optimum Pro-
grams), onde estava trabalhando George Bernard Dantzig, que em 1947 desenvolveu
o algoritmo Simplex.
Durante a Guerra Fria, a antiga Unia˜o Sovie´tica (URRS), exclu´ıda do Plano
Marshall, queria controlar as comunicac¸o˜es terrestres, incluindo rotas fluviais, em
Berlim.
A fim de evitar a entrega da cidade, e sua submissa˜o a uma parte da zona
comunista alema˜, Inglaterra e Estados Unidos decidiram abastecer a cidade, ou por
meio de comboios escoltados (que seriam capazes de dar origem a novos confron-
tos) ou por meio de transporte ae´reo, quebrando ou evitando em qualquer caso, o
bloqueio de Berlim.
A segunda opc¸a˜o foi escolhida, iniciando o Luftbru¨cke (transporte ae´reo) em
25 de junho de 1948. Este foi outro dos problemas em que trabalhou o grupo
SCOOP, em dezembro do mesmo ano, puderam transportar 4.500 toneladas dia´rias,
e apo´s estudos de Pesquisa Operacional o abastecimento pode chegar entre 8.000
a 9.000 toneladas dia´rias, em marc¸o de 1949. Esta cifra foi o mesmo que teria
sido transportado por via terrestre, dessa forma os sovie´ticos decidiram suspender
o bloqueio a 12 de maio de 1949.
Apo´s a segunda Guerra Mundial, a produc¸a˜o de recursos nos Estados Unidos
(energia, armamentos, e todo o tipo de material) foi gerenciada atrave´s de modelos
de otimizac¸a˜o, em espec´ıfico, a Programac¸a˜o Linear.
Ao mesmo tempo, em que a doutrina de Pesquisa Operacional estava sendo
desenvolvida, as te´cnicas de computac¸a˜o e de computadores tambe´m estavam se
desenvolvendo, grac¸as a isso o tempo de resoluc¸a˜o dos problemas diminu´ıram.
O primeiro resultado destas te´cnicas foi dada no ano de 1952, quando um
computador foi usado no National Bureau of Standars de forma a obter a soluc¸a˜o
do problema.
O sucesso no tempo de resoluc¸a˜o foi ta˜o animador que foi imediatamente uti-
lizado para todos os tipos de problemas militares, como determinar a altura ideal
que deveriam voar os avio˜es para localizar os submarinos inimigos, gesta˜o moneta´ria
para a log´ıstica e armamento, inclusive para determinar a profundidade que se deve
enviar os mı´sseispara alcanc¸ar os submarinos inimigos de forma a causar o nu´mero
de v´ıtimas o maior poss´ıvel, isso foi traduzido em um aumento de cinco vezes na
efica´cia da Forc¸a Ae´rea.
Durante os anos 50 e de´cada de 60, cresceu o interesse e desenvolvimento
na Pesquisa Operacional, devido a` sua aplicac¸a˜o no espac¸o do come´rcio e da
indu´stria.
8 CAPI´TULO 1. INTRODUC¸A˜O.
Tomemos por exemplo, o problema do ca´lculo do plano ideal de transporte de
areia de construc¸a˜o para as obras de edificac¸a˜o da cidade de Moscou, que tinha 10
pontos de origem e 230 pontos de destino.
Para resolver isso, foi utilizado o computador Strena, que levou 10 dias no meˆs
de junho de 1958, e tal soluc¸a˜o contribuiu para uma reduc¸a˜o de 11% das despesas
em relac¸a˜o aos custos originais.
Anteriormente, esses problemas foram apresentados em uma disciplina con-
hecida como Pesquisa de Empresas ou Ana´lise da sociedade, que na˜o dispo˜e de
me´todos ta˜o eficazes como os desenvolvidos durante a Segunda Guerra Mundial
(por exemplo, o Me´todo Simplex).
Com base nessas aplicac¸o˜es de guerra a Pesquisa Operacional pode solu-
cionar problemas dos mais diversos tipos, como problemas relacionados a nutric¸a˜o do
gado, a distribuic¸a˜o de campos de cultivo na agricultura, o transporte de mercado-
rias, a localizac¸a˜o, a distribuic¸a˜o do pessoal, e redes, os problemas de fila, grafos,
etc..
Durante anos a Pesquisa Operacional auxilou empresas e ind´ıduos na reduc¸a˜o
de seus custos, abaixo algumas empresas que foram auxiliadas pelos me´todos da
Pesquisa Operacional:
1.2. MODELAGEM DE PROBLEMAS GERENCIAIS. 9
Organizac¸a˜o Aplicac¸a˜o Ano Resultado
IBM Integrac¸a˜o nacional da rede de in-
vento´rios.
1990 $250 milho˜es
economizados
U.S. Military
Airlift Com-
mand
Otimizac¸a˜o do resgate de soldados na
operac¸a˜o “Desert Storm”
1992 Vito´ria
American Air-
lines
Restruturac¸a˜o do formato das areon-
aves
1992 $500 milho˜es
economizados
New Haven
Health Dept.
Modelagem de um programa efetivo de
combate a AIDS
1993 33% menos
conta´gios
AT&T Desenvolvimento de um sistema de Call
Center para vendas a clientes
1993 $750 milho˜es
Delta Airlines Maximizac¸a˜o do lucro atrave´s da mod-
elagem das rotas
1994 $100 milho˜es
Hewlett-Packard Modelagem dos equipamentos produzi-
dos
1998 $280 milho˜es em
lucro
1.2 Modelagem de problemas gerenciais.
Embora a maioria dos administradores reconhec¸a os benef´ıcios dos modelos, os
gerentes-gerais muitas vezes veˆm o processo de modelagem como uma “arte ob-
scura” a ser praticada somente por matema´ticos e estat´ısticos.
Posteriormente, com o advento do computador pessoal e o aumento do poder
computacional tem-se acesso a` softwares que modelam, estimam e realizam pre-
viso˜es; esse fa´cil acesso e a utilizac¸a˜o desses softwares gerenciais levam tambe´m a
um problema que deve ser evitado: S´ındrome da caixa preta.
S´ındrome da caixa preta: A s´ındrome da caixa preta ocorre quando o
tomador de decisa˜o na˜o se preocupa ou ignora como o modelo funciona, preocupando-
se somente com resultados.
Esse tipo de atitude pode levar ao uso incorreto dos modelos; nesse caso os
riscos e erros associados a` tomada de decisa˜o sa˜o ignorados ou mesmo subestimados,
levando assim a uma infereˆncia erroˆnea.
1.2.1 O processo de modelagem
O processo de modelagem pode ser sumarizado da seguinte forma:
10 CAPI´TULO 1. INTRODUC¸A˜O.
Quando uma situac¸a˜o envolve alternativas conflitantes ou competitivas, ela e´
analisada pelo gerente, que enta˜o:
• Chega a deciso˜es para resolver os conflitos;
• As deciso˜es sa˜o implementadas.
• A organizac¸a˜o experimenta as consequeˆncias na forma de resultados, nem to-
dos moneta´rios.
A figura abaixo define o que chamamos de processo de modelagem:
Observe que esse diagrama pode ser divido em duas partes: A parte superior
representa o modelo simbo´lico enquanto a parte inferior representa o mundo real.
• Modelo simbo´lico: O modelo simbo´lico tem como objetivo aproximar a
realidade e na˜o explica´-la completamente.
• Mundo real: O mundo real e´ aquele enfrentado pelos gerentes que teˆm de
decidir como lidar com uma situac¸a˜o desafiadora, como a destinac¸a˜o de re-
cursos para tarefas concorrentes, a programac¸a˜o de atividades ou o projeto de
estrate´gia de marketing.
1.3. MODELAGEM COM PLANILHAS. 11
Para se tomar uma decisa˜o gerencial atrave´s de me´todos quantitativos o mundo
real deve ser descrito atrave´s de um modelo quantitativo, esse modelo e´ analisado de
modo a gerar alguns resultados ou concluso˜es que emanam somente do modelo, ou
seja, sem considerar as abstrac¸o˜es feitas previamente.
Em seguida, da´-se a interpretac¸a˜o dos resultados baseados no modelo nova-
mente na situac¸a˜o do mundo real, levando em conta o que foi deixado de fora durante
a fase anterior de abstrac¸a˜o do modelo simbo´lico.
Quando incrementado pela intuic¸a˜o, e experieˆncia do gerente o processo de
modelagem leva a melhores deciso˜es e insights que influenciam o aprendizado.
1.3 Modelagem com planilhas.
As planilhas eletroˆnicas podem ser usadas para se modelar problemas gerenciais dos
mais diversos tipos. Algumas vantagens do uso de planilhas eletroˆnicas sa˜o:
• Fa´cil acesso.
• Fa´cil utilizac¸a˜o.
• Na˜o requer conhecimento de programac¸a˜o.
Entretanto, as planilhas eletroˆnicas possuem algumas desvantagens, quais se-
jam:
• Geralmente na˜o sa˜o gratuitas.
• Limitam-se apenas aos modelos nela dispon´ıveis.
• Podem induzir a s´ındrome da caixa preta.
Apesar das desvantagens, as planilhas eletroˆnicas sa˜o usadas amplamente pelos
tomadores de deciso˜es. Ale´m das planilhas eletroˆnicas como o Excel, temos outros
softwares que podem ser utilizados na tomada de decisa˜o, como:
• Lindo: Utilizado em programac¸a˜o matema´tica.
• R: Utilizado em programac¸a˜o matema´tica e ana´lise estat´ıstica.
• Maple: Utilizado em programac¸a˜o matema´tica e ana´lise matema´tica.
12 CAPI´TULO 1. INTRODUC¸A˜O.
1.4 Otimizac¸a˜o.
Uma das abordagens na tomada de decisa˜o e´ otimizar alguma func¸a˜o. Geralmente,
deseja-se Maximizar: Lucros, Retornos, Clientes e deseja-se Minimizar: Riscos,
Incerteza e Volatilidade.
Em diversas a´reas do mundo real existe a escassez de um certo produto ou
mate´ria prima devido a sua dificuldade de produc¸a˜o, obtenc¸a˜o, ou outras razo˜es.
Devido a escassez surgem problemas para se empregar melhor estes recursos
escassos de forma eficiente e eficaz. Busca-se, portanto, maximizar ou minimizar
uma quantidade, chamada objetivo, que depende de um ou mais recursos escassos.
A a´rea que estuda a otimizac¸a˜o de recursos e´ denominada Programac¸a˜o
Matema´tica. Nela a quantidade a ser maximizada ou minimizada e´ descrita como
uma func¸a˜o matema´tica dos recursos (varia´veis de decisa˜o) escassos.
As relac¸o˜es entre as varia´veis sa˜o formalizadas atrave´s de restric¸o˜es do prob-
lema expressas como equac¸o˜es e/ou inequac¸o˜es matema´ticas.
De uma maneira geral, os problemas de Programac¸a˜o Matema´tica podem
ser representados da seguinte forma:
Otimizar :Z = f(x1, . . . , xn)
g1(x1, . . . , xn) ≤ (=,≥)b1
g2(x1, . . . , xn) ≤ (=,≥)b2
.
.
.
gm(x1, . . . , xn) ≤ (=,≥)bm
Onde, xj representa as quantidades das varia´veis utilizadas (j = 1, . . . , n),
bi representa a quantidade dispon´ıvel de um determinado recursos (i = 1, . . . ,m),
f(x1, . . . , xn) e´ a func¸a˜o objetivo, gi(x1, . . . , xn) func¸o˜es utilizadas nas restric¸o˜es do
problema (i = 1, . . . ,m), n e´ o nu´mero de varia´veis de decisa˜o e m e´ o nu´mero de
restric¸o˜es do modelo.
Nos problemas de programac¸a˜o operacional, as restric¸o˜es podem ser iguais (=)
a uma determinada constante, menores ou iguais (≤) ou maiores ou iguais (≥) a um
determinado valor.
1.5. INCERTEZA. 13
1.5 Incerteza.
Em problemas de tomada de decisa˜o,frequentemente nos deparamos com situac¸o˜es
em que essa tomada de decisa˜o se baseia em fenoˆmenos envolvidos em incerteza.
Essa incerteza e´ causada pelas fontes de variac¸a˜o que escapam ao nosso cont-
role, ou a` inconsisteˆncia dos fenoˆmenos naturais.
Em lugar de lidar com esta variabilidade qualitativamente, podemos incorpora´-
la num modelo matema´tico e, deste modo, trabalhar com ela quantitativamente.
Isso geralmente pode ser feito se o fenoˆmeno em estudo apresentar algum
grau de regularidade, de modo que sua variac¸a˜o possa ser descrita por um modelo
probabil´ıstico.
Modelos probabil´ısticos, podera˜o ser usados para se modelar a incerteza na
tomada de decisa˜o, o valor esperado e a variabilidade do evento em estudo podem
ser calculada fornecendo-nos dados u´teis na tomada de decisa˜o.
1.6 Aplicac¸o˜es avanc¸adas de simulac¸o˜es.
A te´cnica de simulac¸a˜o tem sido, ha´ muito tempo, um importante instrumento do
tomador de decisa˜o, quer simulando o voo de um avia˜o num tu´nel de vento, quer
simulando projetos de fa´bricas com modelos de ma´quinas em escala, quer simulando
linhas de comunicac¸a˜o com um organograma da organizac¸a˜o.
Com o advento do computador digital de alta velocidade com o qual e´ poss´ıvel
conduzir experimentos simulados, esta te´cnica se tornou cada vez mais importante
para o decisor.
Simulac¸o˜es utilizam um conhecimento a priori de como o evento de interesse se
comporta, com base nesse conhecimento podemos induzir modificac¸o˜es no sistema
e estudar como o evento se altera.
Simulac¸o˜es tambe´m sa˜o utilizadas para se fazer previsa˜o do evento em estudo.
1.7 Previso˜es.
Previsa˜o (forecast) e´ o processo de estimac¸a˜o em situac¸o˜es desconhecidas, ou seja,
deseja-se saber o que acontecera´ em um tempo futuro, ou o que pode acontecer
quando varia´veis explicativas sa˜o alteradas.
Chamamos de varia´veis explicativas aquelas varia´veis que nos ajudam a descr-
14 CAPI´TULO 1. INTRODUC¸A˜O.
ever o processo de interesse.
A previsa˜o pode se referir a estimativa de se´ries temporais, dados transversais
ou longitudinais.
• Se´ries temporais: Conjunto de dados indexados no tempo.
• Dados transversais: Dados obtidos em um momento espec´ıfico do tempo.
• Dados longitudinais: Conjunto de dados observados ao longo do tempo.
Risco e incerteza sa˜o fundamentais para previsa˜o de eventos.
A previsa˜o e´ usada na pra´tica para o planejamento de demanda dos clientes
por uma empresa de manufatura, por exemplo.
1.8 Exerc´ıcios:
1. Quais as vantagens e desvantagens de representar o modelo real atrave´s de um
modelo quantitativo ?
2. O que e´ a s´ındrome da caixa preta ? No que essa s´ındrome pode incorrer ?
3. Descreva o processo de modelagem de um tomador de decisa˜o.
4. O que sa˜o planilhas eletroˆnicas ? Como elas podem ser utilizadas ?
5. Descreva uma situac¸a˜o em que deseja-se otimizar algum fator.
6. Como a incerteza pode ser modelada em um problema de gesta˜o ?
7. Deˆ um exemplo de como as simulac¸o˜es podem auxiliar na tomada de decisa˜o.
8. O que sa˜o dados de se´ries temporais ? Cite 3 exemplos.
9. O que sa˜o dados longitudinais ? Cite 3 exemplos.
10. O que sa˜o dados transversais ? Cite 3 exemplos.
Cap´ıtulo 2
Modelagem com planilhas.
Anteriormente, apresentamos algumas ideias e fundamentos lo´gicos ba´sicos para a
modelagem, visualizamos tambe´m como a criac¸a˜o de um modelo e´ realizada atrave´s
de um processo iterativo.
Nessa parte do texto, nos concentraremos em criar planilhas para alguns mod-
elos determin´ısticos atrave´s de alguns exemplos.
Os exemplos que apresentaremos sa˜o compostos de poucos dados, entretanto,
isso na˜o e´ uma limitac¸a˜o ja´ que as planilhas eletroˆnicas sa˜o capazes de lidar com
milhares de observac¸o˜es.
Suponha, por exemplo, que estejamos administrando uma empresa de tortas.
Essa empresa gera seu lucro combinando dois ingredientes ba´sicos: Frutas e massa
congelada para a criac¸a˜o de tortas de mac¸a˜.
Essas tortas sa˜o preparadas, embaladas, entregues, etc.. Em seguida, essas
tortas sa˜o vendidas em supermercados locais.
Nesse caso estamos interessados em criar um modelo no Excel para explorar
as opc¸o˜es dispon´ıveis quanto a tomada de decisa˜o.
Os esta´gios do processo sa˜o:
1. Estudar o ambiente e enquadrar a situac¸a˜o.
2. Formulac¸a˜o.
3. Construc¸a˜o do modelo.
4. Avaliac¸a˜o do modelo.
5. Documentar e auditar o modelo.
15
16 CAPI´TULO 2. MODELAGEM COM PLANILHAS.
Antes de proceder com a gerac¸a˜o do modelo e´ necessa´rio que o ambiente em
questa˜o seja estudado, para que enta˜o os fatores explicativos sejam conhecidos.
Com base na breve introduc¸a˜o sobre essa empresa, podemos construir um
“esboc¸o” do processo de obtenc¸a˜o dos lucros.
Esse “esboc¸o” pode ser visualizado atrave´s do diagrama da caixa-preta:
Figura 2.1: Caixa-Preta
Como o diagrama de caixa-preta mostra, conhecemos as varia´veis que podem
explicar o lucro dessa empresa de tortas.
Essas varia´veis sa˜o conhecidas como varia´veis explicativas, covaria´veis ou
ainda varia´veis independentes.
Entretanto, e´ claro que nem todas as varia´veis foram listadas, ja´ que listar
todas as varia´veis referentes a um determinado processo e´ um trabalho a´rduo e com
um baixo retorno, nesse caso listamos somente as mais essenciais a explicac¸a˜o do
lucro.
Outra forma de descrever esse processo e´ atrave´s do diagrama de influeˆncia:
Figura 2.2: Diagrama de influeˆncia
2.1. MODELOS ANALI´TICOS. 17
Note que as varia´veis explicativas, podem estar correlacionadas, ou seja, elas
podem possuir a capacidade de explicar umas as outras.
Ambos os diagramas podem ser gerados no Excel, ou mesmo no Paint presente
no sistema operacional Windows.
No caso do Excel basta excluir as linhas de grade e utilizar a ferramenta para
desenho do pro´prio Excel para gerar esses diagramas.
Esses diagramas sa˜o u´teis para se descrever o processo gerencial que se de-
seja modelar, eles sa˜o enta˜o nosso primeiro “modelo”; modelos visuais, meramente
descritivos.
2.1 Modelos anal´ıticos.
Os modelos anal´ıticos sa˜o modelos matema´ticos que teˆm uma “forma fechada” , ou
seja, usam-se equac¸o˜es matema´ticas para descrever as mudanc¸as em um sistema,
esse sistema sera´ descrito por covaria´veis.
Por exemplo, no caso da empresa que fabrica torta, suponha por exemplo, que
tenhamos chegado ao seguinte modelo que explica o Lucro:
L(x1, x2) = −1000 + 27.2x1 − 17x22(2.1)
onde L(x1, x2) e´ o lucro obtido, x1 representa o nu´mero de tortas vendidas, x2
a quantidade de impostos pagos.
Esse e´ um exemplo de modelo anal´ıtico e atrave´s dessa formulac¸a˜o matema´tica
podemos “prever” por exemplo qual seria o lucro esperado se tive´ssemos vendidos
1234 tortas e pago 300 reais de impostos.
Gerado o modelo, precisamos documentar qual foi o me´todo utilizado para
criac¸a˜o desse modelo e explicitar quais sa˜o as varia´veis que compo˜em o modelo tais
como L(x1, x2), x1 e x2.
Finda a etapa de documentac¸a˜o, e´ necessa´rio auditar o modelo, ou seja, re-
sponder a algumas perguntas como:
• Qua˜o “bom” o modelo explica o processo ?
• Esse modelo e´ estatisticamente significante ?
• Ha´ varia´veis que podem ser retiradas do modelo ?
18 CAPI´TULO 2. MODELAGEM COM PLANILHAS.
• Ha´ varia´veis que deveriam ser adicionadas ao modelo ?
No processo de auditoria o modelo e´ avaliado, sua consisteˆncia e poder de
explicac¸a˜o sa˜o averiguados.
Os modelos anal´ıticos sa˜o u´teis na tomada de decisa˜o, uma vez que podemos
avaliar o efeito de cada uma das varia´veis explicativas no modelo.
Os modelos formados devem -ao ma´ximo- manter a simplicidade principal-
mente nos esta´gios iniciais da modelagem. Modelos que tentam explicar todos os
fatores sa˜o -em geral- pouco robustos.
Devemos enta˜o seguir o princ´ıpio da Navalha de Occam (tambe´m conhecidocomo princ´ıpio da parcimoˆnia):
Definic¸a˜o 2.1.1 .
O princ´ıpio da parcimoˆnia afirma que a explicac¸a˜o de fenoˆmenos deve assumir
apenas as premissas estritamente necessa´rias.
Evitando ao ma´ximo aumentar o nu´mero de varia´veis explicativas.
O princ´ıpio e´ frequentemente designado pela expressa˜o latina Lex Parsimoniae
(Lei da Parcimoˆnia).
Esse princ´ıpio tambe´m pode ser entendido como: “A soluc¸a˜o mais simples e´
-geralmente- a melhor.”
Dentre os modelos anal´ıticos, podemos citar:
• Regressa˜o linear. (Usado geralmente com dados transversais).
• Modelos longitudinais. (Usado com dados longitudinais).
• Modelos de se´ries temporais. (Usado com se´ries de dados indexados no tempo).
No exemplo da func¸a˜o lucro em 9.1 temos um exemplo de modelo de regressa˜o
linear.
2.2 Planilhas eletroˆnicas.
As planilhas eletroˆnicas possuem uma caracter´ıstica muito importante. Essa carac-
ter´ıstica e´ denominada escalabilidade:
2.2. PLANILHAS ELETROˆNICAS. 19
Definic¸a˜o 2.2.1 .
Escalabilidade: E´ o grau em que um aplicativo ou componente de computa-
dor pode ser expandido em tamanho, volume, ou nu´mero de usua´rios servidos, e
continuar a exercer sua func¸a˜o corretamente.
Essas implementac¸o˜es evitam que o software se torne obsoleto ou deixe de
atender a`s necessidades do usua´rio.
Diariamente novos modelos e me´todos sa˜o desenvolvidos para a tomada de
decisa˜o, e o software que o tomador de decisa˜o utiliza como suporte a sua ana´lise deve
possui a capacidade de se adaptar rapidamente as novas propostas de modelagem.
No caso do Excel e´ poss´ıvel introduzir novos componentes (plugins) que in-
corporam novas funcionalidade e permite ao analista um maior leque de opc¸o˜es de
ana´lise.
Entre esse plugins podemos citar:
• Solver: Utilizado em pesquisa operacional.
• XLSim: Utilizado em simulac¸o˜es.
• RiskSim: Utilizado em simulac¸o˜es e ana´lise de risco.
• Crystal Ball: Utilizado em modelagem, previsa˜o e simulac¸a˜o.
2.2.1 Func¸o˜es no Excel.
O Excel funciona como uma calculadora. Bastando apenas informar os dados e a
func¸a˜o que deseja-se utilizar, e enta˜o o software calcula o que foi pedido.
Por exemplo, podemos somar dois valores e guardar o resultado em uma ce´lula
espec´ıfica.
20 CAPI´TULO 2. MODELAGEM COM PLANILHAS.
Figura 2.3: Exemplo Excel 1
Esse conjunto de dados e´ conhecido como tabela de dados. E deve ser obtida
antes da formac¸a˜o do modelo anal´ıtico, uma vez que sera´ insumo para a criac¸a˜o dos
modelos.
Suponha que desejamos somar o valor da ce´lula A1 com o valor da ce´lula B1
basta clicar onde voceˆ gostaria que o resultado aparecesse e digitar = A1 +B1.
Apo´s esse comando, no local escolhido surgira´ o valor 13.
Entretanto, podemos usar func¸o˜es e nomes de intervalos. Por exemplo, suponha
que queremos somar todos os valores da coluna A. Basta escolher o local onde o
resultado deve aparecer e digitar: = SOMA(A1 : A5).
Outra func¸a˜o importante e´ a func¸a˜o SOMARPRODUTO. Ela realiza a mul-
tiplicac¸a˜o de dois vetores (colunas) e soma os resultados.
No nosso exemplo, podemos utiliza´-la da seguinte maneira: Escolha o lo-
cal onde o resultado deve surgir, digite nessa ce´lula = SOMARPRODUTO(A1 :
A5;B1 : B5) devera´ surgir enta˜o o valor 1141. Resultante da operac¸a˜o:
1× 12 + 2× 45 + 3× 67 + 4× 87 + 5× 98 = 1141
2.3 Exerc´ıcios
1. Uma determinada empresa aluga carros. O processo inicializa-se com a compra
de um carro, esse carro e´ enta˜o “segurado” evitando assim qualquer perda em
caso de acidentes ou roubo. Finalmente, apo´s um per´ıodo de 5 anos esse carro
e´ considerado obsoleto e na˜o integra mais a frota.
Utilizando o diagrama de caixa-preta e o diagrama de influeˆncia crie um mod-
elo que possa explicar o lucro obtido por essa empresa. Ha´ covaria´veis cor-
2.3. EXERCI´CIOS 21
relacionadas nesse modelo ?
2. Uma questa˜o bastante comum em organizac¸o˜es e´ como avaliar seus funciona´rios
em relac¸a˜o a produtividade/eficieˆncia. Suponha uma empresa que venda
roupas e assesso´rios. Um funciona´rio e´ produtivo e eficiente se consegue vender
o ma´ximo poss´ıvel no meˆs, possui poucas faltas, e´ pontual e bem avaliado pelos
clientes.
Construa um modelo que estime a produtividade/eficieˆncia de determinado
funciona´rio na empresa. Utilize os diagrama de caixa-preta e influeˆncia para
descrever esse modelo.
3. Utilizando o modelo anal´ıtico em 9.1, encontre:
(a) O custo fixo da fa´brica.
(b) O valor da torta.
(c) Supondo que o imposto esta´ fixo no valor de 350 reais, qual o nu´mero
mı´nimo de tortas devem ser vendidas para que na˜o se obtenha preju´ızo ?
(d) Quais outras varia´veis explicativas poderiam ser inclu´ıdas nesse modelo
?
4. O que e´ o princ´ıpio da parcimoˆnia e como deve ser utilizado na gerac¸a˜o de
modelos ?
5. Descreva:
(a) Um exemplo em que podemos utilizar um modelo de regressa˜o linear.
(b) Um exemplo em que podemos utilizar modelos longitudinais.
(c) Um exemplo em que podemos utilizar modelos de se´ries temporais.
6. O que e´ escalabilidade e como essa propriedade pode ser u´til na gerac¸a˜o de
modelos em planilhas eletroˆnicas ?
7. Utilizando o Excel e os dados abaixo referentes a um conjunto de 10 domic´ılios:
22 CAPI´TULO 2. MODELAGEM COM PLANILHAS.
Renda Peso
238.43 0.1
541.04 0.05
578.21 0.5
985.74 0.1
325.17 0.03
784.45 0.1
569.65 0.02
365.35 0.07
845.98 0.01
327.25 0.02
Calcule:
(a) A soma da renda utilizando a func¸a˜o SOMA.
(b) A me´dia da renda (descubra qual a func¸a˜o).
(c) A me´dia ponderada pelo peso utilizando a func¸a˜o SOMAPRODUTO.
Cap´ıtulo 3
Programac¸a˜o Linear.
O conceito de otimizac¸a˜o e´ atualmente bem enraizado, como princ´ıpio subjacente a
ana´lise da decisa˜o complexa ou problemas de alocac¸a˜o, oferece tambe´m uma certa
elegaˆncia filoso´fica que muitas vezes oferece um indispensa´vel grau de simplicidade
operacional.
Usando essa otimizac¸a˜o “filoso´fica”, uma das abordagens para resoluc¸a˜o de
problemas de decisa˜o, envolvendo a selec¸a˜o de valores para um nu´mero de varia´veis
inter-relacionadas, focando a atenc¸a˜o em um u´nico objetivo destinado a quantificar
a performance e medir a qualidade da decisa˜o.
Esse objetivo e´ maximizar (ou minimizar, dependendo da formulac¸a˜o) sujeito
a restric¸o˜es que podem limitar a selec¸a˜o dos valores das varia´veis de selec¸a˜o.
Se um aspecto de um problema pode ser isolado e ser caracterizado por um
objetivo, seja ele lucro ou perda em um ambiente de nego´cios, velocidade ou a
distaˆncia em um problema f´ısico, o retorno esperado no ambiente de investimentos de
risco, ou bem-estar social no contexto do planejamento governamental, a otimizac¸a˜o
pode fornecer um quadro adequado para ana´lise.
Entretanto, ha´ poucas situac¸o˜es em que e´ poss´ıvel representar toda a complex-
idade do problema, representando todas as complexas interac¸o˜es entre as varia´veis,
restric¸o˜es e modelando objetivos adequados quando confrontados em um problema
de decisa˜o complexo.
Assim, como todas as te´cnicas de ana´lise quantitativa, otimizac¸a˜o em especial,
deve ser considerada apenas como uma aproximac¸a˜o, e na˜o como um “modelo real”.
Habilidade em modelagem, para capturar os elementos essenciais de um prob-
lema, e bom senso na interpretac¸a˜o dos resultados sa˜o necessa´rios para obter con-
cluso˜es u´teis.
23
24 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Otimizac¸a˜o, enta˜o, deve ser considerada como uma ferramenta de contextual-
izac¸a˜o e ana´lise e na˜o como uma me´todo que produz a soluc¸a˜o exata, mas sim uma
aproximac¸a˜o da soluc¸a˜o real.
Habilidade e bom senso, no que diz respeito a` formulac¸a˜o do problema e in-
terpretac¸a˜o dos resultados, e´ reforc¸ada por meio da experieˆncia pra´tica e concreta
ale´m de uma profunda compreensa˜o da teoria.
Na formulac¸a˜o do problema frequentemente surgemtrades-off entre os obje-
tivos e as restric¸o˜es que tornam a construc¸a˜o do modelo matema´tico suficientemente
completas para capturar, com precisa˜o, a descric¸a˜o do problema e a construc¸a˜o de
um modelo trata´vel.
Devemos enta˜o aprender a identificar e capturar os aspectos importantes de
um problema, principalmente atrave´s de exemplos e experieˆncia, e´ preciso aprender
a distinguir os modelos na˜o-trata´veis e trata´veis atrave´s do estudo da teoria e da
te´cnica dispon´ıvel, de maneira que sera´ poss´ıvel estender a teoria existente a novas
situac¸o˜es.
Nesse cap´ıtulo, no entanto, estamos preocupados com o desenvolvimento, ana´lises
e comparac¸a˜o de algoritmos para a soluc¸a˜o geral de subclasses de otimizac¸a˜o de
problemas.
Entre as poss´ıveis a´reas de aplicac¸o˜es temos:
• Administrac¸a˜o da produc¸a˜o.
• Ana´lise de investimentos.
• Alocac¸a˜o de recursos limitados.
• Planejamento regional.
• Log´ıstica.
• Custo de transporte.
• Localizac¸a˜o da rede de distribuic¸a˜o.
• Alocac¸a˜o de recursos em marketing entre diversos meios de comunicac¸a˜o.
3.1 Programac¸a˜o Linear
Um problema de programac¸a˜o linear e´ um problema matema´tico no qual a func¸a˜o
objetivo e´ linear e as restric¸o˜es consistem de igualdades e desigualdades lineares.
3.1. PROGRAMAC¸A˜O LINEAR 25
A forma exata dessas restric¸o˜es podem diferir de um problema para outro, mas
como mostraremos abaixo, todo problema de programac¸a˜o linear pode ser transfor-
mado na seguinte forma padra˜o:
(3.1)
Maximize: Z = c1x1 + c2x2 + · · ·+ cnxn
Sujeito a a11x1 + a12x2 + · · ·+ a1nxn = b1
a21x1 + a22x2 + · · ·+ a2nxn = b2
...
am1x1 + am2x2 + · · ·+ amnxn = bm
para x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.
onde os bi´s, ci´s e aij´s sa˜o constantes reais fixas, e os xi´s sa˜o nu´meros reais
a serem determinados.
No´s sempre assumimos que cada equac¸a˜o e´ multiplicada por menos um, se
necessa´rio, tal que cada bi ≥ 0.
Caso a func¸a˜o objetivo seja Minimizar ao inve´s de Maximizar multiplicamos a
func¸a˜o objetivo por -1 (menos um).
Podemos escrever esse problema de forma mais compacta atrave´s da notac¸a˜o
matricial:
(3.2)
Maximize: cTx
Sujeito a Ax = b
para x ≥ 0.
Aqui x e´ um vetor coluna n-dimensional, cT e´ um vetor linha n-dimensional,
A e´ uma matriz m× n e b e´ um vetor coluna m-dimensional.
O vetor de desigualdades x ≥ 0 significa que cada componente de x e´ na˜o-
negativo.
Antes de apresentarmos alguns exemplos no qual a programac¸a˜o linear surge
naturalmente, indicaremos como as va´rias formas de problemas de programac¸a˜o
linear podem ser convertidas na forma padra˜o.
3.1.1 Varia´veis de folga.
Considere o problema:
26 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
(3.3)
Maximize: Z = c1x1 + c2x2 + · · ·+ cnxn
Sujeito a a11x1 + a12x2 + · · ·+ a1nxn ≤ b1
a21x1 + a22x2 + · · ·+ a2nxn ≤ b2
...
am1x1 + am2x2 + · · ·+ amnxn ≤ bm
para x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.
nesse caso o conjunto de restric¸o˜es e´ determinado inteiramente por desigual-
dades lineares.
O problema pode enta˜o se expresso pela forma padra˜o da seguinte maneira:
(3.4)
Maximize: Z = c1x1 + c2x2 + · · ·+ cnxn
Sujeito a a11x1 + a12x2 + · · ·+ a1nxn + y1 = b1
a21x1 + a22x2 + · · ·+ a2nxn + y2 = b2
...
am1x1 + am2x2 + · · ·+ amnxn + ym = bm
para x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0
e y1 ≥ 0, y2 ≥ 0, . . . , ym ≥ 0.
As novas varia´veis positivas yi introduzidas para converter as desigualdades
em igualdades sa˜o chamadas de varia´veis de folga (slack variables).
Considerando enta˜o o problema com n+m varia´veis desconhecidas x1, x2, . . . , xn, y1, y2, . . . , ym
o problema toma a forma padra˜o.
A matriz m × (n + m) que descreve agora as restric¸o˜es atrave´s de equac¸o˜es
lineares e´ uma forma especial [A, I], ou seja, as suas colunas podem ser particionadas
em dois conjuntos; o primeiro com n colunas que formam a matriz original A e a
segunda com m colunas que e´ uma matriz identidade m×m.
3.1.2 Varia´veis de excesso.
Caso as desigualdades sejam maiores ou iguais (≥) ao inve´s de menores ou iguais
(≤) ter´ıamos o seguinte:
ai1x1 + ai2x2 + · · ·+ ainxn ≥ bi
e´ equivalente a fazer:
3.1. PROGRAMAC¸A˜O LINEAR 27
ai1x1 + ai2x2 + · · ·+ ainxn − yi = bi
com yi ≥ 0. Varia´veis, como yi que convertem maior ou igual em igualdade
sa˜o chamadas de varia´veis de excesso (surplus variables).
Note que se multiplicarmos a restric¸a˜o por −1, e adicionarmos varia´veis de
folga e/ou varia´veis de excesso, qualquer conjunto de desigualdades lineares pode
ser convertido na forma padra˜o se as varia´veis desconhecidas forem na˜o-negativas.
3.1.3 Varia´veis livres
Caso um problema de programac¸a˜o linear esteja escrito na forma padra˜o exceto
pelo fato de que uma ou mais varia´veis desconhecidas sejam livres, ou seja, possam
assumir valores reais (incluindo valores negativos) o problema pode ser transformado
na forma padra˜o atrave´s de duas te´cnicas simples.
Para descrever a primeira te´cnica, suponha que em 3.3, por exemplo, a restric¸a˜o
x1 ≥ 0 na˜o esteja presente e enta˜o x1 e´ livre para assumir quaisquer valores tanto
positivo quanto negativo.
Enta˜o escrevemos:
x1 = u1 − v1
onde exige-se que u1 ≥ 0 e v1 ≥ 0. Se substituirmos u1 − v1 para todo x1 no
problema 3.3, a linearidade das restric¸o˜es e´ preservada e todas as varia´veis sa˜o enta˜o
na˜o-negativas.
O problema e´ enta˜o expresso em termos de n + 1 varia´veis desconhecidas, a
saber: u1, v1, x2, x3, . . . , xn.
Ha´ obviamente um certo grau de redundaˆncia introduzida por essa te´cnica, no
entanto, uma vez que uma constante foi adicionada a u1 e v1 na˜o muda x1 (isto e´, a
representac¸a˜o do valor de x1 na˜o e´ u´nica). Todavia, isso na˜o compromete o me´todo
Simplex1 para soluc¸a˜o.
Uma segunda abordagem para converter na forma padra˜o quando x1 na˜o possui
restric¸o˜es de sinal e´ eliminar x1 juntamente com uma das equac¸o˜es de restric¸a˜o.
Tome uma das m equac¸o˜es em 3.3 o qual possui coeficiente na˜o-nulo para x1.
Por exemplo,
1O me´todo Simplex sera´ o me´todo utilizado para resolver os problemas de programac¸a˜o linear.
28 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
ai1x1 + ai2x2 + · · ·+ ainxn = bi
onde ai1. Enta˜o x1 pode ser expresso como uma combinac¸a˜o linear das outras
varia´veis mais uma constante.
Se a expressa˜o for substitu´ıda por todos os valores de x1 em todo local em 3.3,
obtemos um novo problema so´ que dessa vez apenas com as varia´veis x2, x3, . . . , xn.
Ale´m disso, a i-e´sima equac¸a˜o, usada para determinar x1 e´ agora identicamente
igual a zero e pode ser eliminada do problema.
Esse esquema de substituic¸a˜o e´ va´lido desde qualquer combinac¸a˜o de varia´veis
na˜o-negativas x2, x3, . . . , xn leve a um fact´ıvel x1.
Como resultado dessa simplificac¸a˜o, obtemos um problema de programac¸a˜o
linear na forma padra˜o com n− 1 varia´veis e m− 1 restric¸o˜es.
O valor da varia´vel x1 pode ser determinado apo´s a soluc¸a˜o, substituindo os
valores de x2, x3, . . . , xn que descrevem x1.
Exemplo
Considere o problema de programac¸a˜o linear:
(3.5)
Maximize: x1 + 3x2 + 4x3
Sujeito a x1 + 2x2 + x3 = 5
2x1 + 3x2 + x3 = 6
para x1 ∈ <, x2 ≥ 0, x3 ≥ 0.
Uma vez que x1 e´ livre, resolvemos a primeira restric¸a˜o em relac¸a˜o a x1, ob-
tendo:
x1 = 5− 2x2 − x3
Substituindo o valor de x1 na func¸a˜o objetivo e na segunda restric¸a˜o obtemos
o problema de programac¸a˜o linear equivalente:
(3.6)
Maximize: 5 + x2 + 3x3
Sujeito a x2 + x3 = 4
para x2 ≥ 0, x3 ≥ 0.
3.2. FORMULAC¸A˜O DOS PROBLEMAS 29
O qual e´ o problema na forma padra˜o. Apo´s a resoluc¸a˜o do problema encon-
tramos x2 = 4, x3 = 0 e enta˜o o valor de x1 pode ser encontrado x1 = 5−2×4−0 =
−3.
3.2 Formulac¸a˜o dos problemas
A formulac¸a˜o dos problemas de programac¸a˜o linear em sua forma matema´tica passa
primeiramente pela interpretac¸a˜o do problema.
Uma vezentendido o problema e´ necessa´rio escreveˆ-lo em sua forma matema´tica,
para enta˜o soluciona´-lo.
3.2.1 Exemplo de formulac¸a˜o.
A Wyndor Glass Co. produz vidros de alta qualidade, incluindo janelas e portas de
vidro. Ela tem treˆs fa´bricas. Na Fa´brica 1 sa˜o feitas as esquadrias e ferragens de
alumı´nio; as esquadrias de madeira sa˜o feitas na Fa´brica 2 e a Fa´brica 3 e´ usada
para produzir o vidro e montar os produtos.
Por causa do decl´ınio da receita, a alta gereˆncia decidiu reformular a linha
de produtos. Diversos produtos na˜o-lucrativos esta˜o sendo tirados de linha e isso
ira´ liberar a capacidade de produc¸a˜o para se encarregar de um ou dos dois novos
produtos potenciais que teˆm estado em demanda.
Um destes produtos propostos (produto 1) e´ uma porta de vidro de 2,40m,
com esquadria de alumı´nio.
O outro produto (produto 2) e´ uma janela (1,20m x 1,80m) de duas folhas
e esquadria de madeira. O departamento de Marketing concluiu que a companhia
poderia vender tantos destes dois produtos quantos pudessem ser produzidos pela
capacidade dispon´ıvel.
Entretanto, como ambos os produtos estariam competindo com a mesma ca-
pacidade de produc¸a˜o na Fa´brica 3, na˜o fica claro qual combinac¸a˜o entre os dois
produtos seria mais lucrativa.
Por isso a gereˆncia pediu ao departamento de me´todos quantitativos que es-
tudasse a questa˜o. Depois de alguma investigac¸a˜o, o departamento de me´todos
quantitativos determinou:
1. A percentagem de capacidade de produc¸a˜o de cada fa´brica que estaria dispon´ıvel
para estes produtos.
30 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
2. As percentagens requeridas por produto para cada unidade produzida por
minuto.
3. O lucro unita´rio de cada produto.
Essas informac¸o˜es esta˜o resumidas na tabela abaixo:
Fa´brica Tx. de prod. unita´ria (P1) Tx. de prod. unita´ria (P2) Capacidade dispon´ıvel
1 1 0 4
2 0 2 12
3 3 2 18
Lucro R$3 R$5 -
Onde Tx. de prod. unita´ria (P1) representa a capacidade usada por taxa de
produc¸a˜o unita´ria do produto 1 e Tx. de prod. unita´ria (P2) representa a capacidade
usada por taxa de produc¸a˜o unita´ria do produto 2.
Como toda a capacidade que for usada por um produto na fa´brica 3 torna-se
na˜o dispon´ıvel para o outro, o departamento de me´todos quantitativos reconheceu
imediatamente que se tratava de um problema de programac¸a˜o linear do tipo cla´ssico
de “composto de produto”, e a seguir encarregou-se de sua formulac¸a˜o e soluc¸a˜o.
O primeiro passo na formulac¸a˜o do problema e´ identificar qual a pergunta
que se quer responder. Nesse caso estamos interessados na quantidade do produto
1 e do produto 2 que devemos produzir.
Ou seja, fazemos x1 e x2 representando o nu´mero de unidades do produto 1 e
do produto 2 por minuto.
Em seguida, precisamos definir qual o objetivo que se quer atingir. No
caso da Wyndor Glass Co. estamos interessados em maximizar o lucro, enta˜o a
func¸a˜o objetivo e´ escrita como:
Z = 3x1 + 5x2
Entretanto, para atingir esse objetivo, e´ necessa´rio que certas restric¸o˜es sejam
seguidas. Logo, o u´ltimo passo na formulac¸a˜o do problema de pesquisa operacional
e´ a formulac¸a˜o das restric¸o˜es.
Note que na tabela apresentada cada unidade do produto 1 e 2 por min-
uto e usa-se 1 por cento na fa´brica 1, considerando que apenas 4 por cento esta˜o
dispon´ıveis.
Essa restric¸a˜o e´ expressa matematicamente pela desigualdade x1 ≤ 4. Similar-
mente, a fa´brica 2 impo˜e a restric¸a˜o de que 2x2 ≤ 12. A percentagem da capacidade
3.3. SOLUC¸A˜O GRA´FICA 31
da fa´brica 3 consumida pela escolha de x1 e x2 como as taxas de produc¸a˜o dos novos
produtos seria 3x1 + 2x2 ≤ 18.
Como as taxas de produc¸a˜o na˜o podem ser negativas, e´ necessa´rio restringir
as varia´veis de decisa˜o para que sejam na˜o-negativas, ou seja x1 ≥ 0 e x2 ≥ 0.
Resumindo, na linguagem matema´tica da programac¸a˜o linear, o problema e´
encontrar x1 e x2 de modo que:
(3.7)
Maximize: Z = 3x1 + 5x2
Sujeito a x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
para x1 ≥ 0, x2 ≥ 0.
3.3 Soluc¸a˜o gra´fica
No caso da Wyndor Glass Co. o problema e´ muito pequeno possuindo apenas duas
varia´veis de decisa˜o e, portanto, apenas duas dimenso˜es, portanto, podemos resolver
o problema de maneira gra´fica.
O procedimento de resoluc¸a˜o gra´fica envolve construc¸a˜o de um gra´fico bidi-
mensional com x1 e x2 como os eixos.
O primeiro passo e´ identificar os valores de (x1, x2) que sa˜o via´veis devido as
restric¸o˜es. Isto e´ feito atrave´s da elaborac¸a˜o de cada linha que limita o intervalo de
valores admiss´ıveis para uma restric¸a˜o.
Para comec¸ar, note que as restric¸o˜es na˜o-negativas x1 ≥ 0 e x2 ≥ 0 requer que
(x1, x2) esteja contido no primeiro quadrante (lado positivo dos eixos).
Em seguida, precisamos observar que a restric¸a˜o x1 ≤ 4 significa que (x1, x2)
na˜o pode permitir valores a direita da reta de x1 = 4.
Isso e´ representado na figura abaixo, onde a a´rea sombreada conte´m os u´nicos
valores de (x1, x2) , que ainda sa˜o permitidos.
32 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Similarmente, a restric¸a˜o 2x2 ≤ 12 (ou equivalentemente x2 ≤ 6) implica que
a reta 2x2 ≤ 12 deve ser adicionada a` fronteira da regia˜o via´vel (fact´ıvel).
A u´ltima restric¸a˜o, 3x1 + 2x2 ≤ 18 requer que a reta 3x1 + 2x2 = 18 deva ser
adicionada. A regia˜o de soluc¸o˜es fact´ıveis e´ enta˜o dada por:
Figura 3.1: Regia˜o de soluc¸o˜es via´veis.
Qualquer ponto na regia˜o fact´ıvel e´ uma soluc¸a˜o via´vel, entretanto, estamos
interessados na soluc¸a˜o o´tima. A soluc¸a˜o que maximiza Z = 3x1 + 5x2.
O u´ltimo passo e´ escolher o ponto na regia˜o via´vel (ou regia˜o fact´ıvel) que
maximiza a valor de Z = 3x1 + 5x2.
Para descobrir como encontrar esses valores de (x1, x2) de forma eficiente,
utilize tentativa e erro.
3.3. SOLUC¸A˜O GRA´FICA 33
Tente, por exemplo, Z = 10 = 3x1 + 5x2 para ver se ha´ na regia˜o fact´ıvel,
valores de (x1, x2), que fornec¸am um valor de Z maior que 10.
Ao desenhar a reta 3x1 + 5x2 = 10, voceˆ pode ver que ha´ poucos pontos que
esta˜o dentro da regia˜o de interesse.
Uma vez escolhido o primeiro “chute” o processo continua e devemos tentar
um pro´ximo valor (maior do que 10) para Z, por exemplo, Z = 20 = 3x1 + 5x2.
Novamente, ao trac¸armos o segmento de reta 3x1 + 5x2 = 20 averiguamos
quais os pontos esta˜o contidos na regia˜o de interesse de modo que o valor ma´ximo
admiss´ıvel de Z deva ser pelo menos 20.
Agora, observe que as duas retas constru´ıdas sa˜o paralelas. Isso na˜o e´ co-
incideˆncia, uma vez que qualquer reta constru´ıda desta forma tem a forma Z =
3x1 + 5x2 para a escolha do valor de Z, o que implica que 5x2 = −3x1 + Z ou,
equivalentemente
x2 = −3
5
x1 +
1
5
Z
Esta u´ltima equac¸a˜o e´ a forma matema´tica da func¸a˜o objetivo, note que a
inclinac¸a˜o da linha e´ de −3/5 (uma vez que cada unidade de aumento no x1 diminui
x2 em 3/5), ao passo que o intercepto da reta se da´ no eixo x2 e´ de
1
5
Z.
O fato que a inclinac¸a˜o da reta e´ fixada em −3/5 significa que todas as retas
constru´ıdas desta forma sa˜o paralelas.
Novamente, comparando as retas 10 = 3x1 + 5x2 e 20 = 3x1 + 5x2, notamos
que a reta que fornece o maior valor de Z (Z = 20), e´ mais para cima e mais distante
da origem do que a outra reta (Z = 10).
Enta˜o, a soluc¸a˜o o´tima estara´ mais acima da reta que fornece Z = 20. Pode-se
mostrar que a soluc¸a˜o o´tima sera´ um dos pontos de ve´rtice do regia˜o de soluc¸o˜es
fact´ıveis (pontos em vermelho).
Nesse caso, procuramos um ponto que seja ve´rtice da regia˜o fact´ıvel e que a
func¸a˜o objetivo a tangencia. Observe que:
34 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Enta˜o, a soluc¸a˜o o´tima e´ dada por (x1 = 2, x2 = 6) que fornece o ma´ximo
valor de Z fact´ıvel (Z = 36).
Entre as poss´ıveis soluc¸o˜es temos:
Figura 3.2: Soluc¸a˜o o´tima.
Figura 3.3: Todos os pontos do segmentode reta sa˜o soluc¸o˜es.
3.4. ME´TODO SIMPLEX. 35
Figura 3.4: Soluc¸o˜es ilimitadas.
Figura 3.5: Semi-retas contendo todos
os pontos.
Finalmente e´ poss´ıvel que na˜o haja soluc¸a˜o, nesse caso:
Figura 3.6: Na˜o ha´ soluc¸a˜o.
3.4 Me´todo simplex.
O me´todo Simplex foi criado pelo matema´tico americano George Dantzig em 1947,
e´ o algoritmo mais popular para resoluc¸a˜o nume´rica de problemas de programac¸a˜o
linear.
36 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Esse algoritmo tem importaˆncia tal que o jornal Computing in Science and
Engineering listou esse algoritmo como um dos 10 grandes algoritmos do se´culo.
A ideia ba´sica desse algoritmo e´ dada pelo seguinte fluxograma:
Figura 3.7: Algoritmo para soluc¸a˜o anal´ıtica.
Para a resoluc¸a˜o do problema de programac¸a˜o linear atrave´s do me´todo Sim-
plex o problema deve estar escrito na forma de maximizac¸a˜o, ou seja:
(3.8)
Maximize: Z = c1x1 + c2x2 + · · ·+ cnxn
Sujeito a a11x1 + a12x2 + · · ·+ a1nxn ≤ b1
a21x1 + a22x2 + · · ·+ a2nxn ≤ b2
...
am1x1 + am2x2 + · · ·+ amnxn ≤ bm
para x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.
Os passos do me´todo Simplex podem ser escritos como:
1. Encontre uma soluc¸a˜o compat´ıvel ba´sica inicial.
2. Verificar se a soluc¸a˜o atual e´ o´tima:
(a) Caso seja o´tima, PARE!
3.4. ME´TODO SIMPLEX. 37
(b) Caso contra´rio siga para o passo 3. 2
3. Determinar a varia´vel na˜o-ba´sica que deve entrar na base. Colocar na base a
varia´vel na˜o-ba´sica com maior coeficiente negativo na func¸a˜o objetivo.
4. Determinar a varia´vel ba´sica que deve sair da base. 3
5. Encontrar a nova soluc¸a˜o compat´ıvel ba´sica e voltar ao passo 2.
3.4.1 Exemplo
Suponha o caso da Wyndor Glass Co.. O problema e´ escrito da seguinte forma
matema´tica:
(3.9)
Maximize: Z = 3x1 + 5x2
Sujeito a x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
para x1 ≥ 0, x2 ≥ 0.
Se ao inve´s de maximizar tive´ssemos uma minimizac¸a˜o seria necessa´rio trans-
formar esse problema para a forma canoˆnica. Nesse caso, bastaria multiplicar a
func¸a˜o objetivo por −1.
E´ necessa´rio agora transformar as inequac¸o˜es em equac¸o˜es atrave´s das varia´veis
de folga:
(3.10)
Maximize: Z = 3x1 + 5x2
Sujeito a x1 + y1 = 4
2x2 + y2 = 12
3x1 + 2x2 + y3 = 18
para x1 ≥ 0, x2 ≥ 0, y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.
Como ponto de partida podemos usar a soluc¸a˜o via´vel (x1 = 0, x2 = 0).
2No caso do problema de programac¸a˜o linear de maximizac¸a˜o, basta escrever a func¸a˜o objetivo
em termos das varia´veis na˜o-ba´sicas.
Se todos os coeficientes dessas varia´veis sa˜o na˜o-negativos a soluc¸a˜o atual e´ o´tima
3Devemos tirar da base a varia´vel ba´sica que se anula mais rapidamente quando a varia´vel que
entra aumentar de valor.
38 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Definic¸a˜o 3.4.1 Observe que esta soluc¸a˜o pode ser lida imediatamente porque cada
equac¸a˜o tem apenas uma varia´vel ba´sica, que tem um coeficiente igual 1, e esta
varia´vel ba´sica na˜o aparece em nenhuma outra equac¸a˜o. Esse formato e´ conhecido
como forma pro´pria da eliminac¸a˜o de Gauss.
Note que nesse sistema temos 5 varia´veis e 3 equac¸o˜es. Nesse caso, dizemos que
possu´ımos dois graus de liberdade na soluc¸a˜o do sistema, uma vez que quaisquer
duas varia´veis podem ser escolhidas para serem iguais a qualquer valor arbitra´rio a
fim de resolver as treˆs equac¸o˜es em termos das treˆs varia´veis restantes.
O me´todo Simplex usa o zero para este valor arbitra´rio. As varia´veis con-
sideradas zero sa˜o denominadas de varia´veis na˜o-ba´sicas enquanto as demais sa˜o
denotadas como varia´veis ba´sicas.
Nesse caso, temos as varia´veis ba´sicas y1 = 4, y2 = 12, y3 = 18 e as varia´veis
na˜o-ba´sicas x1 = 0, x2 = 0.
A base e´ formada enta˜o por:

y1 y2 y3
1 0 0
0 1 0
0 0 1

E´ conveniente considerar e manipular a equac¸a˜o da func¸a˜o objetivo ao mesmo
tempo que as novas equac¸o˜es de restric¸a˜o. Por isso, antes de comec¸ar o me´todo
Simplex, o problema e´ escrito mais uma vez de maneira equivalente, como:
(3.11)
Maximize: Z
Sujeito a Z − 3x1 − 5x2 = 0
x1 + y1 = 4
2x2 + y2 = 12
3x1 + 2x2 + y3 = 18
para x1 ≥ 0, x2 ≥ 0, y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.
O pro´ximo passo e´ montar a tabela com os valores das varia´veis ba´sicas e
varia´veis na˜o-ba´sicas:
3.4. ME´TODO SIMPLEX. 39
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 -3 -5 0 0 0 0
y1 0 1 0 1 0 0 4
y2 0 0 2 0 1 0 12
y3 0 3 2 0 0 1 18
A primeira linha representa os coeficientes da func¸a˜o Z − 3x1 − 5x2 = 0 , as
demais linhas dessa tabela sa˜o os coeficientes das varia´veis de decisa˜o nas restric¸o˜es.
Uma vez que cada equac¸a˜o conte´m apenas uma varia´vel ba´sica, a qual tem
um coeficiente +1, cada varia´vel ba´sica e´ igual a constante do lado direito de sua
equac¸a˜o.
Assim, a soluc¸a˜o ba´sica via´vel inicial para o exemplo e´ dada por (x1, x2, y1, y2, y3) =
(0, 0, 4, 12, 18). A seguir, precisamos determinar se essa e´ a soluc¸a˜o o´tima, ou na˜o.
Dizemos que a soluc¸a˜o atual e´ o´tima se e somente se cada coeficiente na
primeira linha for na˜o-negativo, ou seja, todos precisam ser maiores ou iguais
a zero.
Como ainda ha´ coeficientes negativos, precisamos obter outra soluc¸a˜o ba´sica
via´vel. Para isso precisamos transformar uma varia´vel na˜o-ba´sica em uma varia´vel
ba´sica e uma varia´vel ba´sica em uma varia´vel na˜o-ba´sica.
Agora a questa˜o que surge e´ qual varia´vel deve entrar na base ? A resposta
e´ incluir a varia´vel que mais contribui para a func¸a˜o objetivo (aquela que possui
o maior coeficiente negativo na primeira linha). Note que nesse caso a varia´vel
de decisa˜o que mais contribui para a func¸a˜o objetivo e´ a varia´vel x2, ja´ que seu
coeficiente e´ igual a −5.
Marque a coluna abaixo da varia´vel selecionada, essa coluna sera´ denominada
coluna pivoˆ:
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 -3 -5 0 0 0 0
y1 0 1 0 1 0 0 4
y2 0 0 2 0 1 0 12
y3 0 3 2 0 0 1 18
A outra questa˜o que surge e´ qual varia´vel deve deixar a base. Nesse caso
a varia´vel que deve deixar a base e´ aquela que se anula mais rapidamente com a
entrada da varia´vel escolhida, nesse caso, y2.
Para isso, cada coeficiente na coluna pivoˆ, que seja estritamente positivo,divide
o valor do lado direito do respectivo coeficiente. Identificando qual equac¸a˜o possui
40 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
o menor valor dessa raza˜o. Aquela varia´vel ba´sica que possuir o menor valor sera´ a
varia´vel a deixar a base.
Note que devemos calcular a raza˜o apenas para y2 e y3 ja´ que sa˜o as u´nicas
com coeficientes estritamente positivos. As respectivas razo˜es sa˜o 12
2
= 6 e 18
2
= 9.
A varia´vel y2 e´ a que possui a menor raza˜o, ou seja, e´ a varia´vel que primeiro alcanc¸a
zero a medida que a varia´vel ba´sica que entra e´ aumentada.
Assim como temos uma coluna pivoˆ, teremos tambe´m uma linha pivoˆ:
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 -3 -5 0 0 0 0
y1 0 1 0 1 0 0 4
y2 0 0 2 0 1 0 12
y3 0 3 2 0 0 1 18
O nu´mero que e´ a intersec¸a˜o da linha pivoˆ com a reta pivoˆ e´ denominado
nu´mero pivoˆ. Nesse caso, o nu´mero pivoˆ e´ 2.
Agora precisamos definir uma nova soluc¸a˜o ba´sica via´vel a partir da construc¸a˜o
de um novo quadro Simplex abaixo do atual.
As treˆs primeiras colunas na˜o sa˜o modificadas com excec¸a˜o de que a varia´vel
ba´sica (x2) saindo na primeira coluna e´ substitu´ıda pela varia´vel ba´sica entrando.
O coeficiente da nova varia´vel ba´sica deve enta˜o ser alterado para +1. Para
isso, dividimos toda a linha pivoˆ pelo nu´mero pivoˆ, de modo que a nova linha pivoˆ
e´ igual a antiga linha pivoˆ dividido pelo nu´mero pivoˆ.
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z
y1
x2 0 0 1 0
1
2
0 6
y3
As demais linhas devera˜o ser modificadas tal que a nova linha sera´ igual
a antiga linha menos o coeficiente da coluna pivoˆ multiplicadopela nova
linha pivoˆ.
Para a primeira linha temos:
[−3,−5, 0, 0, 0, 0]− (−5)
[
0, 1, 0,
1
2
, 0, 6
]
=
[
−3, 0, 0, 0, 5
2
, 30
]
Para a segunda linha temos:
3.4. ME´TODO SIMPLEX. 41
[1, 0, 1, 0, 0, 4]− (0)
[
0, 1, 0,
1
2
, 0, 6
]
= [1, 0, 1, 0, 0, 4]
A terceira linha e´ a linha pivoˆ, e por isso na˜o e´ necessa´rio modifica´-la, ja´ que
dividimos toda a linha pelo nu´mero pivoˆ.
Para a quarta e u´ltima linha da tabela temos:
[3, 2, 0, 0, 1, 18]− (+2)
[
0, 1, 0,
1
2
, 0, 6
]
= [3, 0, 0,−1, 1, 6]
Obtendo assim o seguinte quadro Simplex:
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 -3 0 0 5
2
0 30
y1 0 1 0 1 0 0 4
x2 0 0 1 0
1
2
0 6
y3 0 3 0 0 -1 1 6
Uma vez que cada varia´vel ba´sica e´ igual ao lado direito de sua equac¸a˜o, a
nova soluc¸a˜o ba´sica via´vel e´ (x1, x2, y1, y2, y3) = (0, 6, 4, 0, 6) com valor da func¸a˜o
objetivo Z = 30.
Precisamos agora saber se essa e´ a soluc¸a˜o o´tima. Como a primeira linha
ainda possui um coeficiente negativo (−3), significa ainda na˜o encontramos a soluc¸a˜o
o´tima.
Novamente, a questa˜o que surge e´ qual varia´vel deve entrar na base. Devemos
incluir x1 ja´ que a varia´vel que mais contribui para a func¸a˜o objetivo uma vez que
seu coeficiente e´ igual a −3.
Marcamos a coluna pivoˆ:
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 -3 0 0 5
2
0 30
y1 0 1 0 1 0 0 4
x2 0 0 1 0
1
2
0 6
y3 0 3 0 0 -1 1 6
Agora, encontramos a linha pivoˆ dividindo o lado direito da equac¸a˜o pelos
coeficientes estritamente positivos. As razo˜es para y1 e y3 sa˜o respectivamente
4
1
= 4
e 6
3
= 2. Escolhemos a linha que possui a menor raza˜o, nesse caso a linha referente
a y3:
42 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 -3 0 0 5
2
0 30
y1 0 1 0 1 0 0 4
x2 0 0 1 0
1
2
0 6
y3 0 3 0 0 -1 1 6
Usando o nu´mero pivoˆ 3, calculamos a nova linha pivoˆ fazendo (a nova linha
pivoˆ igual a antiga linha pivoˆ dividida pelo nu´mero pivoˆ 3):
1
3
[3, 0, 0,−1, 1, 6] =
[
1, 0, 0,−1
3
,
1
3
, 2
]
As demais linhas sa˜o constru´ıdas de maneira que a nova linha sera´ igual
a antiga linha menos o coeficiente da coluna pivoˆ multiplicado pela nova
linha pivoˆ, ou seja:
Para a primeira linha temos:
[
−3, 0, 0, 5
2
, 0, 30
]
− (−3)
[
1, 0, 0,−1
3
,
1
3
, 2
]
=
[
0, 0, 0,
3
2
, 1, 36
]
Para a segunda linha temos:
[1, 0, 1, 0, 0, 4]− (−1)
[
1, 0, 0,−1
3
,
1
3
, 2
]
=
[
0, 0, 1,
1
3
,−1
3
, 2
]
Ja´ a terceira linha na˜o sofre modificac¸o˜es, uma vez que o coeficiente da coluna
pivoˆ e´ igual a zero, ou seja:
[
0, 1, 0,
1
2
, 0, 6
]
− (0)
[
1, 0, 0,−1
3
,
1
3
, 2
]
=
[
0, 1, 0,
1
2
, 0, 6
]
Finalmente, obtemos a seguinte tabela Simplex:
Varia´vel ba´sica Z x1 x2 y1 y2 y3 Lado direito
Z 1 0 0 0 3
2
1 36
y1 0 0 0 1
1
3
−1
3
2
x2 0 0 1 0
1
2
0 6
x1 0 1 0 0 −13 13 2
3.4. ME´TODO SIMPLEX. 43
Consequentemente, a nova soluc¸a˜o ba´sica via´vel e´ (x1, x2, y1, y2, y3) = (2, 6, 2, 0, 0)
com valor da func¸a˜o objetivo igual Z = 36. Ao avaliarmos os coeficientes da primeira
linha, vemos que todos sa˜o positivos, indicando assim que o valor o´timo foi atingido.
3.4.2 Empate para a varia´vel ba´sica entrando.
Na primeira parte do me´todo Simplex precisamos escolher a varia´vel na˜o-ba´sica que
tenha o maior coeficiente negativo na primeira linha da tabela.
Essa varia´vel sera´ a varia´vel ba´sica entrando. Agora suponhamos que duas ou
mais varia´veis na˜o-ba´sicas estejam empatadas por terem o maior coeficiente nega-
tivo.
Por exemplo, isso ocorreria na primeira iterac¸a˜o para o problema da Wyndor
Glass Co. se sua func¸a˜o objetivo se tornasse Z − 3x1 − 3x2 = 0.
Nesse caso, a selec¸a˜o pode ser feita arbitrariamente. A soluc¸a˜o o´tima sera´
encontrada eventualmente, na˜o importando a varia´vel empatada escolhida, e na˜o ha´
um me´todo conveniente para predizer antecipadamente que escolha nos conduziria
a` soluc¸a˜o o´tima mais rapidamente.
No exemplo aconteceu do me´todo Simplex alcanc¸ar a soluc¸a˜o o´tima em treˆs
iterac¸o˜es com x1 como varia´vel ba´sica entrando inicial, contra duas interac¸o˜es se x2
fosse escolhida inicialmente.
3.4.3 Empate para a varia´vel ba´sica saindo (Degenerac¸a˜o).
Agora suponha que duas ou mais varia´veis ba´sicas empatem para ser a varia´vel
ba´sica saindo. Sera´ que importa qual delas e´ escolhida ? Teoricamente sim, e de um
modo muito cr´ıtico, por causa da seguinte sequeˆncia de eventos que poderia ocorrer.
Primeiro que todas as varia´veis ba´sicas empatadas cheguem a zero simultane-
amente quando for aumentada a varia´vel ba´sica entrando.
Portanto, a ou as na˜o-escolhidas para varia´vel ba´sica saindo tambe´m teria ou
teriam um valor de zero (assim chamadas de varia´veis ba´sicas degeneradas) na nova
soluc¸a˜o ba´sica via´vel (degenerada).
Segundo, se uma dessas varia´veis ba´sicas degeneradas retiver seu valor de zero
ate´ que seja escolhida numa iterac¸a˜o subsequente para ser a varia´vel ba´sica saindo, a
varia´vel ba´sica entrando correspondente tambe´m tera´ que permanecer zero (uma vez
que na˜o pode ser aumentada sem tornar a varia´vel ba´sica saindo negativa), tendo
assim o valor de Z que permanecer imuta´vel.
44 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR.
Terceiro, se Z pode permanecer o mesmo em lugar de aumentar a cada iterac¸a˜o,
enta˜o o me´todo Simplex pode ficar dando “voltas”, repetindo a mesma sequeˆncia de
soluc¸o˜es periodicamente em vez de eventualmente aumentar Z na direc¸a˜o da soluc¸a˜o
o´tima.
De fato foram constru´ıdos exemplos artificialmente e eles realmente se viram
envolvidos nesse c´ırculo vicioso perpe´tuo.
Felizmente, embora esse c´ırculo vicioso perpe´tuo seja teoricamente poss´ıvel,
raramente ocorre na pra´tica. Ainda mais foram constru´ıdas regras especiais de
desempate, de modo que esses c´ırculos viciosos sa˜o sempre evitados.
Para nossos propo´sitos, vamos simplesmente fazer esse desempate arbitrari-
amente e proceder sem nos preocuparmos com varia´veis ba´sicas degeneradas que
possam resultar.
3.4.4 Varia´vel ba´sica saindo inexistente - Z Ilimitado.
Outro problema que pode ocorrer durante o me´todo Simplex e´ o caso em que nen-
huma varia´vel esteja qualificada para ser a varia´vel ba´sica saindo.
Isso ocorreria se a varia´vel ba´sica entrando pudesse ser aumentada indefinida-
mente sem dar valores negativos a qualquer das varia´veis ba´sicas atuais.
Na forma tabular, isso significa que todo o coeficiente na coluna pivoˆ (excluindo
a primeira linha) e´ negativo ou zero. Isso pode ser ilustrado na tabela abaixo:
Varia´vel ba´sica Z x1 x2 y1 Lado direito
Z 1 -3 -5 0 0
y1 0 1 0 1 4
Isso significa que as restric¸o˜es na˜o previnem o aumento do valor da func¸a˜o
objetivo Z indefinidamente na direc¸a˜o favora´vel (positiva ou negativa).
Por isso o me´todo Simplex iria parar com a mensagem de que Z e´ ilimitado.
Uma vez que nem a programac¸a˜o linear descobriu um modo de ter lucros infinitos,
a mensagem real para problemas pra´ticos e´ que deve ter havido algum engano!
Provavelmente o modelo foi formulado de maneira erroˆnea, quer pela omissa˜o
de restric¸o˜es relevantes, quer por teˆ-las estabelecido incorretamente. E´ tambe´m
prova´vel que possa ter ocorrido um erro computacional.
3.5. RESTRIC¸O˜ES NA FORMA DE IGUALDADE. 45
3.5 Restric¸o˜es na forma de igualdade.
Para resolver os problemas pelo me´todo Simplex e´ necessa´rio que o problema esteja
escrito na forma de maximizac¸a˜o, ou seja:
(3.12)
Maximize: Z = c1x1 + c2x2 + · · ·+ cnxn
Sujeito a a11x1 + a12x2 + · · ·+ a1nxn ≤ b1
a21x1 + a22x2 + · · ·+ a2nxn ≤ b2
...
am1x1 + am2x2 + · · ·+ amnxn ≤ bm
para x1 ≥ 0, x2 ≥ 0, . . . ,