Programação Linear

PROGRAMAÇÃO

LINEAR

SÉRIE PESQUISA OPERACIONAL

VOLUME 1

DARCI PRADO, Ph.D.

PROGRAMAÇÃO

LINEAR

SÉRIE PESQUISA OPERACIONAL

VOLUME 1

Rua Senador Milton Campos, 35, 7° andar

Vale do Sereno | Nova Lima | Minas Gerais | CEP: 34000-000

Tel.: (31) 3289-7200 | Fax: (31) 3289-7201

www.falconi.com

Ficha Catalográfica

P896p        PRADO, Darci Santos do

Programação Linear / Darci Santos do Prado. – 7. ed. – Nova Lima: FALCONI Editora, 2016. – (Série Pesquisa Operacional, vol. 1).

286 p.: il.

ISBN: 978-85-98254-97-5

1. Programação Linear – Planejamento – Gestão. I. Título.

CDD: 519.8

Capa: África São Paulo Publicidade Ltda.

Editoração eletrônica: Jeferson Teixeira Soares

Revisão do texto: Dila Bragança de Mendonça

Produção de ePub: Cumbuca Studio

Copyright © 1999-2015 by DARCI SANTOS DO PRADO

Direitos comerciais desta edição: FALCONI Editora

A meus pais

Alípio e Francisca (in memoriam),

e meus irmãos

Cláudio, Francisco, Nelson e Tereza

Sumário

Apresentação

Prefácio

NÍVEL BÁSICO

1 Conceitos básicos

1.1 O que é programação linear?

1.2 Aplicações da PL

1.3 A abordagem da PL

1.4 Vantagens do uso da PL

1.5 Modelos

1.6 Aspectos históricos

1.7 Áreas clássicas de aplicação

1.8 Tópicos da programação linear

1.9 Interface com o usuário

2 Modelando e resolvendo problemas simples pelo método gráfico (I)

2.1 Criando o modelo matemático

2.2 O método gráfico

2.3 Um conceito adicional de PL

2.4 Exercícios

3 Modelando e resolvendo problemas simples pelo método gráfico (II)

3.1 Um problema de minimização: formulação de ração

3.2 Criando o modelo matemático

3.3 Plotando o modelo matemático

3.4 Outro problema de minimização: liga de alumínio

3.5 Exercícios

4 Resolvendo problemas com o computador

4.1 Principais softwares

4.2 Exercícios

5 Modelos clássicos (I)

5.1 Alocação de recursos

5.2 Mistura ou dosagem

5.3 Fazendas

5.4 Carteira de investimentos

5.5 Exercícios

NÍVEL INTERMEDIÁRIO

6 Programação inteira mista

6.1 Um exemplo PIM

6.2 Uso do computador

6.3 Exercícios

7 A matriz MPS

7.1 A visualização completa da matriz MPS

8 Programação estruturada (I)

8.1 O que é um modelo estruturado?

8.2 O modelo multifábrica ou multiplanta

8.3 O modelo multiproduto

8.4 Exercícios

9 Modelos clássicos (II)

9.1 Problema do transporte

9.2 Localização industrial

9.3 Dosagem

9.4 Exercícios

NÍVEL AVANÇADO

10 Programação estruturada (II)

10.1 O modelo multiperíodo

10.2 Aplicabilidade dos modelos estruturados

10.3 Exercícios

11 Programação 0/1

11.1 Um exemplo inicial

11.2 Uso de programação 0/1

11.3 Exemplo da fábrica de fertilizantes

11.4 Uso do computador

11.5 Exercícios

12 Modelos clássicos (III)

12.1 Redes

12.2 O problema da designação de pessoas

12.3 O problema da designação de tarefas

12.4 O problema do corte

12.5 Exercícios

13 Interpretando e analisando os resultados

13.1 Análise de sensitividade

13.2 Custo reduzido

13.3 Análise econômica

13.4 Tipos de solução

13.5 Exercícios

MODELAGEM

14 A obtenção de um modelo de PL

14.1 Equipes especializadas

14.2 As etapas para o desenvolvimento de um modelo

15 Desenvolvimento de um modelo de PL

15.1 Criação: o modelo inicial simples (ou análise do problema)

15.2 Modelagem com Lingo: consolidação do modelo inicial

15.3 Modelagem com Lingo: elaboração de modelos intermediários e do modelo definitivo

15.4 Criação do sistema informatizado

Bibliografia

APÊNDICES

Apêndice A

Apêndice B

Apêndice C

Apêndice D

Apêndice E

Apêndice F

Apêndice G

Apêndice H

Apêndice I

Apêndice J

Apêndice K

Apêndice L

Apêndice M

Clique aqui e faça o download dos arquivos que compõem o livro

Apresentação

Muitos são os problemas de otimização na teoria e na prática. Um problema de otimização consiste em definir um objetivo a ser minimizado ou maximizado sujeito a um conjunto de restrições. Em uma linha clássica de problemas de otimização, são formulados o objetivo e as restrições por meio de equações matemáticas, gerando uma subárea da otimização que é a programação matemática. Nessa subárea, o grande destaque é a Programação Linear, na qual todas essas equações são lineares. O potencial dessa técnica é marcante pelo substancial número de aplicações.

Este livro procura motivar e mostrar esse potencial da Programação Linear nos processos de tomada de decisão, gerando soluções ótimas para problemas práticos encontrados na indústria, na área econômica e social. Por meio de modelos clássicos e estudos de casos, a técnica é introduzida de forma simples e direta, permitindo ao leitor obter resultados pelo do uso de softwares disponíveis no mercado.

O conteúdo do livro reflete a longa experiência do professor Darci, atuando no ensino e como consultor em empresas. Ele tem se dedicado durante anos à produção de textos didáticos, explorando ferramentas de auxílio à tomada de decisão, mostrando aos seus leitores a flexibilidade e aplicabilidade de modelos de otimização.

Belo Horizonte, abril de 2012

Geraldo Robson Mateus

Professor Titular – Departamento Ciência da Computação

Universidade Federal de Minas Gerais

Prefácio

A Programação Linear é uma técnica de planejamento considerada como das mais poderosas e capazes de produzir resultados expressivos em quase todo ramo da atividade humana. Seus benefícios são exatamente aqueles procurados por qualquer empresa: diminuição dos custos e aumento dos lucros. Em algumas empresas seu uso é frequente, e muitas vezes a encontramos embutida em rotinas diárias de planejamento por meio de aplicativos de informática.

O objetivo deste livro é apresentar este assunto com ênfase maior em modelagem (ou em aplicações práticas da Programação Linear), pois esta nos parece a mais apropriada ao público-alvo deste livro: estudantes de graduação e profissionais da indústria. Esperamos que, com a ajuda deste livro, o leitor esteja apto a modelar e resolver problemas reais de média complexidade.

Este livro é o resultado de uma longa experiência com o assunto, seja lecionando-o na Escola de Engenharia da UFMG (desde 1972), seja atuando como consultor na IBM, FDG, INDG ou DPI.

Agradecemos as preciosas ajudas de Jeferson Teixeira Soares. Agradecemos, também, a Flávio Pizzato, da Produttare Com. e Repr. Ltda., a cessão da cópia de demonstração do Lingo e por preciosas dicas de conversão, ao Dr. Luis Cláudio M. Montenegro, da UFMG, pelas sugestões e auxílio na solução de exercícios e a Cláudia Werneck, do IGA-MG, pela confecção de um mapa.

Darci Prado

Belo Horizonte – Minas Gerais

1ª edição – Janeiro 1999

7ª edição – Julho 2016

Capítulo 1

Conceitos básicos

1 Conceitos básicos

1.1 O que é programação linear?

A PL é uma técnica de planejamento que se originou no final da década de 1941 e, com o surgimento do computador na década de 1950, encontrou o seu aliado natural, tendo então um desenvolvimento acelerado e sendo também muito difundida. Costuma-se dizer também que a PL é um tópico da ciência pesquisa operacional, a qual contém outros tópicos tais como teoria das filas, simulação, teoria dos jogos, programação dinâmica, PERT/CPM, etc. Estudos estatísticos têm mostrado que a PL é hoje uma das técnicas mais utilizadas da pesquisa operacional. É comum ver aplicações de PL fazerem parte de rotinas diárias de planejamento das mais variadas empresas, tanto nas que possuem uma sofisticada equipe de planejamento como nas que simplesmente adquiriram um software para alguma função de planejamento.

Podemos conceituar a PL como a seguir:

A PL é uma técnica de otimização.

A PL é uma ferramenta utilizada para encontrar o lucro máximo ou o custo mínimo em situações nas quais temos diversas opções de escolha sujeitas a algum tipo de restrição ou regulamentação.

Portanto, a PL é uma técnica de planejamento baseada em matemática e economia.

É importante também esclarecer desde já que a palavra programação tem aqui o significado de planejamento. Fazemos isso para evitar a confusão com o termo programação de computadores, bastante utilizado atualmente na ciência da computação. Certamente a PL utiliza computadores para resolver seus problemas, mas é importante entender que a palavra programação tem significados diferentes nas duas ciências.

1.2 Aplicações da PL

Na prática a PL tem sido aplicada em áreas diversas como mostram os cenários seguintes:

Alimentação: Que alimentos as pessoas (ou animais) devem utilizar de modo que o custo seja mínimo, os nutrientes sejam nas quantidades adequadas e que também sejam atendidos outros requisitos tais como variedade entre as refeições, aspecto, gosto, etc.?

Rotas de transporte: Qual deve ser o roteiro de transporte de veículos de carga de modo que entreguem toda a carga no menor tempo e no menor custo total?

Manufatura: Qual deve ser a composição de produtos a serem fabricados por uma empresa de modo que se atinja o lucro máximo, sendo respeitadas as limitações ou as exigências do mercado comprador e a capacidade de produção da fábrica?

Siderurgia: Quais minérios devem ser carregados no alto-forno de modo a se produzir, ao menor custo, um determinado aço dentro de determinadas especificações de elementos químicos?

Petróleo: Qual deve ser a mistura de petróleo a ser enviada para uma torre de craqueamento para produzir seus derivados (gasolina, óleo, etc.) a um custo mínimo? Os petróleos são de diversas procedências e possuem composições diferentes.

Agricultura: Que alimentos devem ser plantados de modo que o lucro seja máximo e sejam respeitadas as características do solo, do mercado comprador e dos equipamentos disponíveis?

Carteira de investimentos: Quais ações devem compor uma carteira de investimentos de modo que o lucro seja máximo e sejam respeitadas as previsões de lucratividade e as restrições governamentais?

Mineração: Em que sequência devem-se lavrar blocos de minério abaixo do solo, dados sua composição, seu posicionamento e os custos de extração?

Localização industrial: Onde devem ser localizadas as fábricas e os depósitos de um novo empreendimento industrial de modo que os custos de entrega do produto aos varejistas sejam minimizados?

Os cenários acima são os mais conhecidos, mas a PL não se limita a eles. Seria possível citar aqui inúmeros outros cenários, mas isso desfocaria o objetivo deste momento. No final deste capítulo oferecemos uma visão ampliada das áreas de aplicação da PL.

1.3 A abordagem da PL

Para melhor entender como a PL aborda um problema real, vejamos alguns exemplos clássicos: alocação de pessoas, formulação de ração e transporte.

1.3.1 Alocação de pessoas em uma fábrica

Consideremos uma fábrica de rádios que possui duas linhas de produção:

Rádios standard

Rádios luxo

Com relação aos rádios standard, temos as seguintes informações:

A linha de produção comporta um máximo de 24 pessoas;

Cada rádio consome 1 homem/dia para ser produzido;

Cada rádio fornece um lucro de R$ 30,00.

Para os rádios luxo:

A linha de produção comporta um máximo de 32 pessoas;

Cada rádio consome 2 homens/dia para ser produzido;

Cada rádio fornece um lucro de R$ 40,00.

Além disso, devemos informar que a fábrica possui um total de 40 empregados a serem alocados nas duas linhas de produção. O objetivo do dono da fábrica é maximizar o lucro diário.

Analisando melhor os dados, podemos observar que:

As duas linhas podem receber um máximo de 56 pessoas, mas a fábrica possui somente 40 empregados. Assim, temos o desafio de alocar adequadamente as 40 pessoas nas duas linhas.

Os esquemas de produção em vigor implicam diferentes usos de mão de obra. Assim, o rádio standard exige uma menor quantidade de pessoal que o rádio luxo.

As lucratividades são diferentes, e a do modelo luxo é maior que a do modelo standard.

O problema acima é clássico na PL e se enquadra na categoria alocação de recursos. Além de ser bastante simples, pode ser resolvido com algumas tentativas manuais. Modelos reais obviamente são muito mais complexos e exigem o computador. Ao tentar resolver o problema acima por tentativas, poderíamos analisar as seguintes opções:

Produzir o máximo de modelos luxo (visto que fornece o maior lucro unitário): Assim, seriam colocadas 32 pessoas na linha luxo, e elas produziriam 16 rádios por dia. O pessoal restante (40 – 32 = 8 pessoas) seria colocado na linha standard para produzir 8 rádios por dia. O lucro obtido seria de 16 × 40 + 8 × 30 = R$ 880,00.

Produzir o máximo de modelos standard (visto que ele consome a menor quantidade de mão de obra por produção unitária). Assim, seriam colocadas 24 pessoas na linha standard, e elas produziriam 24 rádios por dia. O pessoal restante (40 – 24 = 16 pessoas) seria colocado na linha luxo para produzir 8 rádios por dia. O lucro obtido seria de 8 × 40 + 24 × 30 = R$ 1.040,00.

Certamente existem outras opções que poderiam ser analisadas, mas não é o objetivo deste capítulo. Pode-se também adiantar, conforme demonstraremos no próximo capítulo, que a solução deste problema (lucro máximo) é de R$ 1.040,00 para a produção diária de:

24 rádios standard;

8 rádios luxo.

O que esse exemplo tem de levemente inesperado é que a escolha recaiu sobre o modelo de menor lucro unitário. Na vida prática, quando não utilizamos ferramentas de otimização e não montamos o modelo de forma completa, geralmente temos a tendência de tomar uma decisão com base em fatores aos quais somos mais apegados, por exemplo, com base no