Pesquisa Operacional - 170 Aplicações em Estratégia, Finanças, Logística, Produção, Marketing e Vendas, 2ª edição

Autor(es): COLIN, Emerson C.
Visualizações: 459
Classificação: (0)
Este livro contempla de maneira ampla a disciplina de Pesquisa Operacional e oferece ao leitor uma nova abordagem às suas ferramentas de tomada de decisão e solução de problemas, uma vez que explora desde a contextualização e evolução histórica da matéria até o aprofundamento de conceitos-chave e termos mais utilizados. A obra divide-se em quatro partes: programação linear; programação inteira e programação dinâmica; programação não linear; teoria dos jogos e métodos heurísticos. Em todas elas, o autor trata de aplicações em áreas funcionais como compras, estratégia, finanças, logística, marketing, entre outras. Por fim, a riqueza de orientações práticas fica evidente com mais de 170 aplicações apresentadas ao longo da obra, divididas entre exercícios e exemplos aplicados à realidade de grandes empresas brasileiras, como Embratel, Petrobras e Sabesp, entre outras. A preocupação do autor foi enriquecer o conteúdo com diversos métodos e técnicas aplicados por meio de ferramentas do Excel. Livro destinado a estudantes de graduação em Administração, Engenharia de Produção e Matemática Aplicada, além de pós-graduação e cursos de MBA na disciplina. O enfoque em aplicações técnicas torna o texto adequado também a profissionais de Marketing, Finanças e Vendas, entre outros, que poderão se beneficiar da orientação prática da obra.

• O acesso aos materiais suplementares é gratuito. Basta que o leitor se cadastre em nosso site (www.grupogen.com.br), faça seu login e clique em GEN-IO, no menu superior do lado direito.

É rápido e fácil. Caso haja alguma mudança no sistema ou dificuldade de acesso, entre em contato conosco (gendigital@grupogen.com.br).
 

32 capítulos

Formato Comprar item avulso Adicionar à Pasta

1 - Criação e Evolução Histórica

PDF Criptografado

1

Criação e Evolução Histórica

S

em dúvida alguma a Programação Linear é uma das principais descobertas da matemática aplicada. Levando em consideração os benefícios econômicos gerados ao ser humano, é provável que a PL seja a maior descoberta da matemática aplicada de todos os tempos. Em termos econômicos, ela é comparável às maiores descobertas, como a divisão do trabalho, o motor a vapor, a produção em massa e a tecnologia da informação.

1.1 GEORGE DANTZIG E O ALGORITMO SIMPLEX

É intrigante notar que, embora a matemática seja uma ciência relativamente madura desde pelo menos o século XVIII, a PL da forma como a conhecemos foi iniciada apenas após a Segunda Guerra

Mundial, especialmente por George B. Dantzig (1914-2005).1

Entre 1941 e 1945 Dantzig trabalhou no Pentágono, órgão de defesa americano, como especialista em planejamento e programação de atividades militares, época em que trabalhava intensivamente com calculadoras de mesa (Dantzig, 1991, pp. 19-31). Posteriormente, continuou trabalhando na mesma organização em outras funções como conselheiro em matemática da Força Aérea.

 

2 - Conceitos-chave, Suposições e Termos Utilizados

PDF Criptografado

2

Conceitos-chave, Suposições e

Termos Utilizados

O

s conceitos apresentados neste capítulo também servem para outros capítulos que tratam de programação matemática. Embora acreditemos que boa parte dos leitores conheça os tópicos descritos a seguir, utilizamos o capítulo tanto para recordar os leitores já experientes, como para instruir os que ainda não tiveram a oportunidade de trabalhar com o assunto.

2.1 CONCEITOS-CHAVE DA PROGRAMAÇÃO LINEAR

Em linhas gerais, a programação linear trata do problema de alocação ótima de recursos escassos para a realização de atividades. Por ótimo entendemos que não haja outra solução que seja melhor do que a oferecida (pode haver outras tão boas quanto). Recursos escassos representam nossa realidade de existência finita de recursos, por mais abundantes que sejam. Atividades se relacionam com algum interesse que tenhamos na fabricação de produtos, na mistura de substâncias, no atendimento ao público, no transporte e armazenagem de mercadorias etc.

 

3 - Modelagem de Problemas de Programação Linear

PDF Criptografado

3

Modelagem de Problemas de

Programação Linear

M

esmo com um gigantesco arcabouço teórico existente, na prática, modelagem e identificação do problema acontecem de forma empírica e pessoal. Quando um problema no mundo real é identificado, a identificação acontece mais pela experiência e vivência do modelador do que, por exemplo, se o problema atende às suposições da PL.

Lamentavelmente, não há um algoritmo que nos ajude a transformar um problema do mundo real num modelo. Por outro lado, é nesse ponto que a habilidade do tomador de decisões é colocada à prova. Mesmo que o tomador de decisões não tenha familiaridade com técnicas de PL, a simples identificação do problema e a consciência da possibilidade do uso da PL para resolvê-lo permitem que ele procure meios adequados para que o problema seja resolvido. Possivelmente, a melhor forma para que o tomador de decisões identifique e modele problemas é conhecendo exemplos de aplicações de modelos em problemas análogos aos seus.

 

4 - Solução de Problemas de Programação Linear

PDF Criptografado

4

Solução de Problemas de Programação Linear

C

omo comentamos anteriormente, a solução de problemas de programação linear é feita por meio de algoritmos, e em especial pelo algoritmo simplex. Didaticamente, há uma grande conveniência na apresentação de soluções gráficas para o problema de duas variáveis: ela permite um entendimento mais claro sobre o que está acontecendo e facilita a introdução de alguns conceitos. Por esse motivo, começaremos o capítulo com a apresentação de uma solução gráfica e a seguir introduziremos o método simplex.

4.1 SOLUÇÃO GRÁFICA DE PROBLEMAS COM DUAS VARIÁVEIS

A solução gráfica do problema de programação linear pode ser feita em três passos: (1) identificação da região viável, (2) determinação das curvas de nível e (3) identificação do ponto ótimo.

4.1.1 Três Passos para a Obtenção da Solução Ótima

Identificação da região viável

Na solução gráfica com duas variáveis, utiliza-se o plano cartesiano, com os dois eixos (abscissa e ordenada) representados por duas variáveis do problema. Utilizaremos o exemplo do mix de produção

 

5 - Criação e Solução de Problemas no Computador

PDF Criptografado

5

Criação e Solução de Problemas no

Computador

N

as aplicações reais, como observamos nos capítulos anteriores, o número de equações e variáveis dos modelos de programação linear cresce rapidamente, de modo que a solução manual

é impraticável. Na verdade, de uma forma geral, modelos oferecem maior auxílio na tomada de decisões na medida em que a complexidade do sistema em análise cresce. Em outras palavras, quanto mais complexo o sistema que o tomador de decisões está interessado em analisar, maior será o benefício gerado pelo uso de modelos de programação matemática.

Existe uma infinidade de softwares que resolvem problemas de programação linear. Para os nossos objetivos, podemos considerar dois grandes grupos: os de grande flexibilidade, utilizados como suplementos de planilhas eletrônicas, e os de baixa flexibilidade, representando todos os outros.

Se o modelo é rodado diversas vezes como uma rotina operacional, ele não precisa de flexibilidade e em geral deve ser dedicado. Por outro lado, se cada modelo vai ser usado uma ou poucas vezes, em geral ele demanda maior flexibilidade. Usualmente, problemas estratégicos sugerem o uso de planilhas, enquanto problemas operacionais requerem o uso de softwares dedicados. Em sua pesquisa com

 

6 - Dualidade na Programação Linear

PDF Criptografado

6

Dualidade na Programação Linear

T

odo problema de programação linear possui outro problema de programação linear associado a ele, denominado problema dual. O problema original é denominado primal. Surpreendentemente, um pode ser transformado no outro, e cada um deles possui características distintas, embora ambos possuam a mesma solução ótima. Se, por exemplo, o problema primal é de minimização, o dual é de maximização. Se o primal possui n variáveis e m restrições, o dual possui m variáveis e n restrições, e assim por diante.

Considerando a observação do Capítulo 4 de que é melhor resolver problemas com mais variáveis do que restrições, a propriedade da dualidade é muito conveniente.

Em essência, a dualidade leva a dois resultados importantes. O primeiro resultado é relacionado à facilidade de solução do problema. Como o dual pode se transformar no primal e vice-versa, pode-se escolher para resolver o mais fácil dos dois. Existem diversos métodos de solução de problemas de PL e softwares que se beneficiam dessas propriedades. Um segundo resultado é que a dualidade permite um entendimento mais profundo do problema em questão. O entendimento mais profundo será útil na análise de sensibilidade e em determinados tipos de problemas.

 

7 - Análise de Sensibilidade

PDF Criptografado

7

Análise de Sensibilidade

O

termo análise de sensibilidade é relativamente comum em ambientes empresariais.1 Ele sempre está associado a análises relacionadas com variações em parâmetros de modelos quantitativos. Por exemplo, na avaliação da rentabilidade futura de um projeto, ou de uma empresa, são feitas análises de sensibilidade em parâmetros como taxa de juros e crescimento do PIB (Produto

Interno Bruto), ou seja, estuda-se como a rentabilidade do projeto muda de acordo com diferentes cenários de taxas de juros e crescimento do PIB.

Da mesma forma, no caso da programação linear, a análise de sensibilidade está relacionada com a análise de efeitos ocasionados no modelo caso seus parâmetros mudem. Depois do algoritmo simplex e da solução oferecida por ele, a análise de sensibilidade é provavelmente o que existe de mais importante na programação linear. Ela é fundamental quando o tomador de decisão está interessado em avaliar como mudanças no modelo (e no mundo real que ele representa) podem afetar a solução.

 

8 - Programação de Metas

PDF Criptografado

8

Programação de Metas

A

programação de metas é mais uma parte do rico acervo de solução de problemas reais da programação linear. Ela é especialmente útil em ambientes em que o tomador de decisões se vê forçado a resolver um problema que possui múltiplos objetivos. Por esse motivo, algumas vezes, a programação de metas é classificada como pertencendo à otimização linear de múltiplos objetivos.

Esse mesmo tipo de problema pode ser resolvido por outras técnicas probabilísticas, mas no caso em que as decisões são determinísticas a programação de metas é uma das ferramentas mais poderosas.

Sistemas de gestão convencionais possuem diversos objetivos que de certa forma são conflitantes, como, por exemplo, maximizar o lucro e a satisfação de clientes o mesmo tempo. Mesmo tendências mais recentes em termos de gestão, como a utilização dos balanced scorecards1 (boletins balanceados) e a gestão baseada em valor, possuem diversos objetivos (ou metas) que convivem no mesmo ambiente, ainda que sejam conflitantes.

 

9 - Modelos de Rede

PDF Criptografado

9

Modelos de Rede

M

odelos de rede são extremamente convenientes, tanto do ponto de vista teórico como computacional. Eles são estruturas simples de entender e possuem propriedades que são modeláveis de maneira relativamente fácil. Além disso, redes podem ser utilizadas para modelar uma infinidade de problemas reais de grande importância. A combinação entre simplicidade e poder de obtenção da solução ótima em problemas reais faz com que as redes sejam um estudo importante da programação matemática.

Tipicamente, redes são estudadas como um assunto à parte da programação linear devido à existência de algoritmos mais eficientes para resolver problemas dessa natureza. Como os algoritmos não são o nosso foco, o capítulo pode parecer estranho num primeiro momento. O intuito é mostrar que uma grande diversidade de casos reais pode ser enxergada como uma rede, e, na verdade, muitos deles são equivalentes do ponto de vista matemático.

Adicionalmente vamos apresentar um algoritmo simples e poderoso para a criação de árvores geradoras, estruturas essas que não podem ser formuladas como problemas de programação linear.

 

10 - Análise por Envoltória de Dados: DEA

PDF Criptografado

10

Análise por Envoltória de Dados: DEA

E

m termos de programação matemática, a análise por envoltória de dados (DEA — Data

Envelopment Analysis), também chamada de análise de fronteiras, é considerada uma técnica relativamente nova. Ao mesmo tempo, também é considerada um dos sucessos recentes da

Programação Linear e, em termos mais amplos, da Pesquisa Operacional.

Toda essa reputação é oriunda de sua relativa simplicidade e da ampla aplicabilidade em diversos problemas encontrados no mundo real. Praticamente qualquer empresa que possua múltiplas unidades (denominadas UTDs — Unidades de Tomada de Decisão) que operem de forma similar e que esteja preocupada com a uniformização do desempenho das unidades pode se beneficiar com a técnica. Exemplos reais de aplicações de grande sucesso podem ser encontrados em bancos de varejo, redes de postos de gasolina, hospitais, programas sociais, empresas de energia, entidades de ensino, lojas de departamento, redes de farmácia, classes de aula, times de futebol, agências dos correios etc.

 

11 - Outros Tópicos em Programação Linear

PDF Criptografado

11

Outros Tópicos em Programação Linear

A

programação linear foi um dos temas mais estudados de toda a matemática aplicada no século

XX. Um livro dedicado ao assunto possivelmente deixaria de conter vários tópicos importantes. Não haveria condições de se fazer uma revisão completa do assunto nos 10 capítulos precedentes, e dessa forma tentamos nos concentrar nos tópicos que aparentemente são mais poderosos em termos de aplicabilidade em organizações.

Esta seção faz uma breve revisão de tópicos adicionais não tratados anteriormente, mas que podem ser importantes nalgumas situações. A bibliografia oferece fontes adicionais para interessados em aprofundamentos.

11.1 NOTAÇÃO MATRICIAL NA PROGRAMAÇÃO LINEAR

A representação matricial de problemas de programação linear é bastante difundida e comum em textos sobre o assunto. Ela possui benefícios inegáveis, como elegância, concisão e maior adequação a cálculos computacionais, mas é mais difícil de entender e requer maior nível de abstração. Por consequência, sempre que possível, tentamos evitá-la, tendo em vista objetivos e público-alvo do livro.

 

12 - Casos em Programação Linear

PDF Criptografado

12

Casos em Programação Linear

N

este livro, a abordagem referente aos casos é um pouco diferente das tipicamente usadas em livros de Pesquisa Operacional. Em geral, muitos dos casos apresentados nos livros da área se assemelham mais a problemas grandes do que a casos reais.

Aqui, procuramos ir além dos problemas grandes, apresentando e discutindo pontos que dificultam a utilização de modelos de PO no mundo real e até como entender as percepções do executivo que não é especialista no assunto. A visão ingênua de colocar a técnica acima do problema foi evitada ao máximo. São discutidas questões como dificuldades de implantação, resultados limitados alcançados por modelos, preparação da administração da empresa para o entendimento de modelos, forma de comunicar resultados, sugestões para desdobramento de implantações bem-sucedidas etc.

É possível que o leitor acostumado com livros tradicionais, ou que seja um pouco mais “purista” no sentido de não misturar matemática com outras questões de administração, estranhe a abordagem.

 

13 - Criação e Criadores das Programações Inteira e Dinâmica

PDF Criptografado

13

Criação e Criadores das Programações Inteira e Dinâmica

A

criação da programação inteira foi uma consequência da incapacidade da PL de oferecer soluções viáveis para alguns problemas importantes. As primeiras propostas de metodologias que tratavam do problema com variáveis inteiras eram mais adaptações do método simplex do que novas teorias. O principal arquiteto dos primórdios da programação inteira foi Ralph E. Gomory.

13.1 RALPH GOMORY E AS ORIGENS DA PROGRAMAÇÃO INTEIRA

Em 1957, Gomory trabalhava como um consultor da Marinha dos EUA. Numa das frequentes viagens que fazia a Washington, ele se deparou com um grupo de pessoas que apresentou um modelo de programação linear de uma Força-tarefa da Marinha. Um dos participantes do grupo comentou que seria interessante se eles tivessem respostas como números inteiros, tendo em vista que uma resposta do tipo “1,3 avião de carga” não significava nada.

Esta observação chamou a atenção de Gomory, que começou então a procurar uma solução para aquele tipo de problema. Retornando ao seu escritório, ele passou uma semana pensando no problema e não conseguiu nada além de uma montanha de papéis escritos. Na tarde do oitavo dia ele já não tinha mais ideias para serem testadas, embora ainda acreditasse que de uma forma ou de outra o problema deveria ter solução. Foi então que perguntou a si mesmo: “Supondo que eu tenha que resolver o problema de qualquer forma, qual seria a primeira coisa que eu deveria fazer?” A resposta, quase que imediata, foi que o primeiro passo seria resolver o problema (de maximização) por programação linear, e se a resposta fosse por exemplo 7¼, então a resposta inteira ótima não poderia exceder 7.

 

14 - Modelagem de Problemas de Programação Inteira

PDF Criptografado

14

Modelagem de Problemas de

Programação Inteira

A

modelagem de problemas de PI é parecida com a modelagem de problemas de PL. A diferença fica por conta de que pelo menos parte das variáveis é de números inteiros. Em termos de programação matemática, há duas classes importantes de números inteiros: os inteiros genéricos (1, 2, 3, ...) e os inteiros 0 e 1. Os números 0-1 representam fenômenos do tipo sim e não, presença e ausência, verdadeiro e falso, aberto e fechado etc.

Em programação inteira, problemas são classificados da seguinte forma:

●●

●●

●●

Problema de programação inteira pura: Todas as variáveis são inteiros genéricos;

Problema de programação inteira mista (ou programação linear inteira): Parte das variáveis é de inteiros e parte é de variáveis contínuas (como na PL);

Problemas de programação inteira com variáveis 0-1: Todas as variáveis assumem valores 0 ou 1.

Em tese, um problema de PI pode ser visto como um problema de PL mais uma restrição de que as variáveis devem ser inteiras. A ideia associada a esse conceito nos leva à definição de uma relaxação de PL. A relaxação de PL de um problema de PI é o problema de PI com a omissão das restrições de que as variáveis devem ser inteiras. Como vimos anteriormente no desenvolvimento histórico da PI, esse conceito é extremamente importante, pois define limitantes da solução do problema de PI. Em outras palavras, para um problema de maximização

 

15 - Algoritmos de Programação Inteira

PDF Criptografado

15

Algoritmos de Programação Inteira

E

xistem vários algoritmos para resolver problemas de programação inteira. O primeiro deles, possivelmente o mais intuitivo de todos, é o arredondamento das soluções não inteiras para o inteiro mais próximo. Embora a solução ótima possa ser encontrada por esse algoritmo, é bastante improvável que isso aconteça. O arredondamento do valor das variáveis pode ocasionar tanto uma inviabilidade (não atendimento das restrições) como uma solução não ótima. Isso não quer dizer que o arredondamento nunca deva ser feito; dependendo do problema em questão, o arredondamento pode ser uma solução barata, simples e adequada. Só quando o arredondamento não pode ser aplicado devemos usar outras abordagens.

Em linhas gerais, podemos classificar os algoritmos de PI como genéricos e específicos. Algoritmos genéricos foram criados para resolver qualquer problema que possa ser formulado na forma padrão da programação inteira. A generalidade obviamente tem seu preço: algoritmos específicos, em geral, são mais eficientes, pois se beneficiam de particularidades dos problemas para os quais foram criados. Os algoritmos específicos algumas vezes são desenvolvidos diretamente para a solução de um problema e, outras vezes, são derivações melhoradas de algoritmos genéricos.

 

16 - Solução de Problemas no Computador

PDF Criptografado

16

Solução de Problemas no Computador

A

modelagem de problemas de programação inteira no computador é equivalente ao que já estudamos na programação linear. Na verdade, a modelagem é a mesma da programação linear, com a inclusão de restrições de variáveis inteiras. Além disso, pela maior complexidade desse tipo de problema, o Solver precisa ser parametrizado apropriadamente para que uma solução adequada seja alcançada.

16.1 MODELAGEM DE VARIÁVEIS INTEIRAS E PARAMETRIZAÇÃO DO SOLVER

16.1.1 Microsoft Excel versão 11

A introdução de restrições de variáveis inteiras é feita na caixa Adicionar restrição, conforme Figura

16.1. Selecionam-se as variáveis com valores inteiros para a introdução na caixa Referência de célula.

As duas últimas opções da caixa de edição central, denominadas “núm” e “bin”, representam variáveis inteiras e binárias, respectivamente.1 A opção Restrição não precisa ser preenchida manualmente; o

Solver introduz automaticamente os termos “número” e “binario” (sic).

 

17 - Programação Dinâmica

PDF Criptografado

17

Programação Dinâmica

A

Programação Dinâmica (PD) é uma técnica extremamente versátil, pois pode ser utilizada para resolver problemas com variáveis inteiras ou contínuas, lineares ou não lineares, com horizonte de tomada de decisão finito ou infinito, determinísticos ou estocásticos, ou ainda uma combinação desses tipos de problemas.1

Embora problemas com características temporais (ou de decisões sequenciais) tenham sido resolvidos anteriormente com outras técnicas, a PD é especialmente útil para esse fim, como veremos ao longo do capítulo. Todavia, a versatilidade da PD tem um preço: diferentemente das técnicas estudadas até agora, a formulação e a solução do problema são bastante particularizadas. Formulações têm características distintas, e a modelagem se aproxima ainda mais de uma arte. Richard Bellman chamou isso de “instabilidade”. Por esse motivo, boa parte do aprendizado passa necessariamente por uma grande exposição à solução de diferentes problemas.

 

18 - Casos em Programações Inteira e Dinâmica

PDF Criptografado

18

Casos em Programações Inteira e Dinâmica

T

odos os casos apresentados no livro são relatos de situações reais, quer tenham sido vividas pelo autor, quer tenham sido relatadas por outros autores. Como alguns deles foram objetos de consultoria sujeita a cláusulas de confidencialidade, eventualmente dados foram transformados e referências às verdadeiras empresas foram omitidas.

18.1 AUMENTO DE RECEITAS E PRODUTIVIDADE NA REDE DE TELEVISÃO NBC

18.1.1 Visão Geral do Problema e da NBC1

A rede de televisão norte-americana NBC (National Broadcasting Company) é uma subsidiária da GE (General Electric) e trabalha com dois negócios principais: produção de conteúdo e operação de estações de TV aberta e redes de TV a cabo. A empresa possui aproximadamente 6.000 empregados no mundo e sua programação é vista em mais de 100 países. A empresa possui várias afiliadas como: (1) 13 estações de transmissão UHF e VHF próprias, (2) 220 estações afiliadas, (3) CNBC: rede de TV a cabo especializada em notícias de negócios, (4) MSNBC: Serviço de notícias pela internet, (5)

 

Carregar mais


Detalhes do Produto

Livro Impresso
eBook
Capítulos

Formato
PDF
Criptografado
Sim
SKU
BPPD000247353
ISBN
9788597014471
Tamanho do arquivo
22 MB
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
Formato
PDF
Criptografado
Sim
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
SKU
Em metadados
ISBN
Em metadados
Tamanho do arquivo
Em metadados