Tpicos Especiais IIPesquisa Operacional o conhecimento que leva otimizaoAEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Prof. Dr. Ualison Rbula de Oliveira

1

1

Currculo Resumido do ProfessorUalison Rbula de Oliveira Doutor em Engenharia (nfase em Engenharia de Produo) pela UNESP, Mestre em Sistemas de Gesto da Qualidade pela UFF, Especialista em Gesto Empresarial, Finanas Empresariais, Administrao Estratgica, Gesto de Recursos Humanos, Graduado em Engenharia Mecnica e em Administrao de Empresas. Possui 15 anos de experincia profissional em Finanas Corporativas adquirida em instituio financeira de grande porte. Atualmente presta consultoria nas reas de FINANAS, GESTO DE PROCESSOS e QUALIDADE. professor em disciplinas com foco em Finanas em cursos de PsGraduao e professor em disciplinas com foco em Gesto de Processos e Qualidade em cursos de Graduao. No ano de 2009 teve sua Tese de Doutorado (tema versa sobre Flexibilidade de Manufatura em Montadora de Veculos) eleita pela Associao Brasileira de Engenharia de Produo como uma das duas melhores Teses de Doutorado em Engenharia de Produo de todo o Brasil.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

2

Objetivo da disciplina PESQUISA OPERACIONAL aplicada produo

Introduzir as idias mais importantes em Pesquisa Operacional, as quais so fundamentais e permanentes; Lecionar a disciplina em nvel que se possa entender e apreciar a fora e as limitaes inerentes a Pesquisa Operacional; Preparar e motivar futuros especialistas em Pesquisa Operacional; Apresentar e aplicar, de forma prtica, tcnicas de Pesquisa Operacional.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

3

Bibliografia recomendada para acompanhamento das aulas

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

4

Sumrio1. INTRODUO A PESQUISA OPERACIONAL Pesquisa operacional: histria e conceitos; Mtodo da Pesquisa Operacional; Tipos bsicos de modelo de PO. 2. PROGRAMAO LINEAR Generalidades; Problemas de programao linear; Obtendo funo objetivo e as restries; Soluo de um problema de PL - Mtodo Grfico; Problemas interessantes que podem ser resolvidos por programao linear; Soluo de problemas de PL - Mtodo Simplex; Uso de Softwares (lindo, solver, QM for windows e Linprog).AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 5

Sumrio3. CASOS PARTICULARES DO SIMPLEX Mltiplas solues; Soluo ilimitada; Problema da degenerao. 4. ANLISE ECONMICA 5. DUALIDADE E INTERPRETAO ECONMICA 6. ANLISE DE SENSIBILIDADE Mudana nos coeficientes da funo objetivo; Mudana no lado direito das inequaes; Uso de softwares. 7. ALGORTIMOS PARTICULARES EM PROGRAMAO LINEAR Problema de transporte; Redes; Programao inteira e mista.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 6

Introduo O termo Pesquisa Operacional uma traduo (brasileira) direta do termo em ingls Operational Research, que em Portugal foi traduzido por Investigao Operacional e nos pases de lngua hispnica, por Investigacion Operativa (ARENALES et al, 2007); No Brasil a pesquisa operacional teve incio com o Primeiro Simpsio Brasileiro de Pesquisa Operacional, realizado em 1968 no ITA, em So Jos dos Campos, SP, sendo seguida, pela criao da SOBRAPO (sociedade Brasileira de Pesquisa Operacional); Resumidamente, Lachtermacher (2007) define que a Pesquisa Operacional procura determinar como melhor projetar e operar um sistema, usualmente sob condies que requerem a alocao de recursos escassos; Surgiu na Inglaterra em 1934 e em 1941 foi utilizada pela Marinha Inglesa para solucionar problemas de tomada de deciso em operaes de guerra, tais como melhoria na probabilidade de destruio de submarinos;AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 7

IntroduoA BATALHA DO ATLANTICO Vrios escritrios de Pesquisa Operacional foram implantados no exercito ingls; Um dos esforos empreendidos pelas equipes eram relativos as ameaas dos submarinos alemes, que atacavam os navios mercantes antes que atravessassem o Atlntico; Esta disputa entre submarinos alemes e navios que protegiam os navios mercantes ficou conhecida como Batalha do Atlntico A questo era: como garantir suprimento de necessidades atravs do Atlntico, dede os Estados Unidos da Amrica at a Inglaterra?AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 8

Introduo A BATALHA DO ATLANTICO Navios navegando sozinhos eram alvos fceis; A soluo encontrada foi o deslocamento em comboios; Para proteg-los, navios de guerra acompanhavam a viagem; Entretanto, um nmero no adequado para esta proteo significou, muitas vezes, perdas enormes; Em 1942, para um comboio de 40 navios mercantes, eram necessrios cerca de 6 navios de guerra para sua proteo; O problema era que no havia um nmero suficiente de navios de guerra para proteger todos os navios mercantes, ou seja, o nmero de navios de guerra era limitado; O desafio que se colocava era: pode-se diminuir o nmero de perdas de navios mercantes sem que ocorra um aumento demasiado nos navios de proteo (navios de guerra)? A nica varivel que podia ser alterada era o nmero de navios no comboio; Uma equipe de pesquisadores estudou o problema e verificou que o tamanho do comboio tinha a ver com o nmero de perdas.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 9

IntroduoA BATALHA DO ATLANTICO: dados de 1941 a 1942 Um nmero menor que 45 navios no comboio tinha uma perda mdia de 2,6%; Um nmero maior que 45 navios no comboio tinha uma perda mdia de 1,7%; O nmero de navios afundados continuava praticamente o mesmo, para um nmero praticamente igual de navios de proteo; QUAL A EXPLICAO PARA ESSE FATO? RESPOSTA: A questo era o permetro de defesa necessrio para a defesa do comboio.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

10

IntroduoA BATALHA DO ATLANTICO: Anlise da situao Comboio 1 possui uma rea igual a 100 km2 e um raio de 5,64 km. Logo o seu permetro igual a 35,45 km; Permetro = 2r e rea = r2; Comboio 2 possui uma rea igual a 200 km2 e um raio de 7,87 km. Logo o seu permetro igual a 50,13 km; Relaes importantes: rea 2 / rea 1 = 2 e Permetro 2 / Permetro 1 = 1,41, ou seja, a razo do permetro do crculo (regio a ser defendida) e sua rea (navios a serem protegidos) diminui com o aumento do raio.11

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

IntroduoA BATALHA DO ATLANTICO: constatao importante Um comboio maior era melhor; Um nmero maior de navios poderiam ser protegidos sem um aumento demasiado nos navios de proteo; Um exemplo claro de MELHOR UTILIZAO DE RECURSOS; Este tem sido um exemplo de busca de uma utilizao tima para recursos limitados.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

12

Introduo OUTRO EXEMPLO: O PROBLEMA DO VIAJANTE Cada semana um vendedor tem que visitar clientes em quatro cidades distintas; Ele viaja de carro e deseja viajar o menor nmero de quilmetros possvel; A sua inteno visitar cada uma das cidades uma vez e depois voltar para casa; Ele conhece as distncias entre as cidades e usando esta informao ele quer estabelecer a rota que MINIMIZA a distncia viajada; Atravs desse exemplo pretende-se diferenciar os mtodos heursticos dos mtodos otimizantes; Uma soluo heurstica leva a uma boa soluo. No necessariamente a tima. Um exemplo de soluo heurstica poderia ser viajar sempre para a cidade mais prxima que o viajante se encontra no momento; Uma soluo tima leva a melhor soluo. No caso do viajante, a rota de menor distncia em quilmetros.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 13

IntroduoA soluo heurstica seria visitar as cidades com a menor distncia do ponto de sada. Nesse caso, partir-seia da cidade A para a cidade C, indo depois para a cidade B, dando seguimento para a cidade D, seguida pela cidade E, retornando a cidade ponto de partida (A). Assim, o trajeto seria ACBDEA, perfazendo 230 km de percurso.

km 60

40 km

m

90

80 k

km

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

30

70

km

km

50 km

40 km

14

Introduo A soluo tima seria visitar as cidades na seguinte seqncia: ABCDEA, o que perfazer ia 200 km. Para o caso de cinco cidades o nmero de combinaes necessrias para serem testadas para encontrar a melhor (tima) rota seria 24. Se o nmero de cidades fossem onze o nmero de combinaes seria de 3.628.800 combinaes; O nmero de combinaes pode ser calculado por (n1)!

km 60

40 km

m

90

80 k

km

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

30

70

km

km

50 km

40 km

15

Introduo A aplicao de modelos matemticos na resoluo de problemas uma caracterstica inerente a Pesquisa Operacional, aplicando conceitos matemticos para representar de forma visvel os eventos; Segundo Machline et al. (1994) muitas decises so complexas, porque envolvem objetivos mltiplos, permitem numerosos cursos de ao, produzem resultados incertos, so baseados em dados duvidosos ou tem de ser tomadas em grupo. Nesse aspecto que se justifica a utilizao da Pesquisa Operacional, uma vez que esta implica em uma anlise detalhada dos componentes do problema, alinhando-os em uma estrutura lgica para que ento, seja aplicada uma metodologia adequada ao tipo de problema, a ento, o resultado encontrado ser avaliado em uma tomada de deciso; Atualmente a Pesquisa Operacional tem sido utilizada pelas empresas para otimizar recursos, maximizar lucros, minimizar custos, maximizar receitas, entre outros aspectos relacionados.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 16

IntroduoEm resumo, pode-se concluir que a Pesquisa Operacional: Serve para a anlise quantitativa de problemas gerenciais; Resolver problemas complexos; Tomar decises importantes; Discutir a incerteza;

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

17

Mtodo da Pesquisa Operacional A partir da observao de fenmenos, processos ou sistemas, buscam-se leis que os regem. Essas leis, se passveis de serem descritas por relaes matemticas, do origem aos modelos matemticos; A Pesquisa Operacional trata de problemas de deciso e faz uso de modelos matemticos que procuram representar (em certo sentido, imitar) o problema real; A soluo do modelo matemtico apia o processo de tomada de deciso; No prximo slide ilustrado um problema de Pesquisa Operacional que resolvido por meio de modelos matemticos.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 18

Mtodo da Pesquisa Operacional Z da Gota fabrica 2 tipos de brinquedos de madeira: soldados e trens. Aps recuperao da crise mundial de 2008, a empresa de Z da Gota no consegue mais cumprir seus pedidos, haja vista a limitao de horas de mo-de-obra capacitada, que no suficiente para atender a enorme demanda por seus produtos; Sabe-se que a fabricao desses brinquedos requer dois tipos de mo-de-obra: carpintaria e acabamento. A cada semana, Z da Gota pode obter qualquer quantidade de matria-prima, mas tem a disposio somente 100 horas de acabamento e 80 horas de carpintaria; Diante dessa situao, Z da Gota precisa tomar uma deciso que envolve quais produtos produzir e em quais quantidades, de forma a maximizar seu lucro; O quadro no prximo slide informa dados importantes para essa tomada de deciso.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 19

Mtodo da Pesquisa Operacional

Soldado Preo de venda R$ 27,00 Custo da matria-prima R$ 10,00 Custo da mo-de-obra R$ 14,00 Tempo para acabamento 2 horas Tempo para carpintaria 1 hora Demanda 40 por semana Tempo total disponvel de carpintaria Tempo total disponvel de acabamento

Trem R$ 21,00 R$ 9,00 R$ 10,00 1 hora 1 hora Ilimitado 80 horas 100 horas

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

20

Mtodo da Pesquisa Operacional Um estudo de Pesquisa Operacional consiste em construir um modelo da situao fsica. A complexidade de um sistema real resulta do grande nmero de variveis que comandam as operaes de uma determinada situao fsica, onde, geralmente, uma pequena frao dessas variveis domina as operaes do sistema (por exemplo, a quantidade de madeira utilizada por Z da Gota no exemplo anterior no relevante); Assim, a simplificao do sistema real em termos de um modelo enxuto, identificando apenas as variveis relevantes (dominantes) e as relaes entre elas, o recomendado para a correta tomada de deciso;

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

21

Mtodo da Pesquisa Operacional

Em geral, no h regras fixas para determinar o nvel de abstrao, onde a validade do modelo depende, principalmente, da criatividade, insight e imaginao dos analistas de PO.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

22

Mtodo da Pesquisa Operacional RAZES PARA SE MODELAR Modelos nos foram a ser explcitos em relao a nossos objetivos; Modelos nos foram a identificar e registrar os tipos de decises que influenciam esses objetivos; Modelos nos foram a identificar e registrar interaes e concesses entre essas decises; Modelos nos foram a pensar cuidadosamente sobre variveis a serem includas e suas definies em termos que sejam quantificveis; Modelos nos foram a considerar que dados so pertinentes para a quantificao dessas variveis e a determinar suas interaes; Modelos nos foram a reconhecer restries (limitaes) nos valores que estas variveis quantificadas podem assumir; Modelos permitem a comunicao de nossas idias e percepes para facilitar o trabalho em equipe.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 23

Mtodo da Pesquisa OperacionalEM UM ESTUDO DE PESQUISA OPERACIONAL OCORREM, NORMALMENTE, AS SEGUINTES FASES: 1. 2. 3. 4. 5. 6. Formulao (ou definio) do problema; Construo do modelo matemtico; Obteno de uma soluo a partir do modelo; Teste do modelo e avaliao da soluo obtida; Estabelecimento de controle sobre a soluo; Implantao da soluo;

A NOSSA DISCIPLINA BASEIA-SE NA APLICAO DA PESQUISA OPERACIONAL A UMA GRANDE VARIEDADE DE PROBLEMAS QUE PODEM SER REPRESENTADOS POR CASOS TPICOSAEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 24

Mtodo da Pesquisa OperacionalFORMULAO DO PROBLEMA Para se obter a soluo de um problema, torna-se necessrio formul-lo em um modelo matemtico de modo a tornar possvel a utilizao da Pesquisa Operacional; Em conseqncia, o primeiro passo consiste em estudar o sistema e estabelecer de uma maneira bem definida o problema a ser considerado. Para isso vrios elementos devem ser determinados, exatamente tais como os objetivos a atingir, as restries que devem ser consideradas, o inter-relacionamento entre o setor a ser estudado e outros setores da organizao, as possveis linhas de ao alternativas, etc.; O resultado obtido dessa formulao extrai como componentes a funo objetivo (a funo f) e as variveis que limitam o sistema, ou seja, as restries.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 25

Mtodo da Pesquisa OperacionalCONSTRUO DO MODELO MATEMTICO Os modelos so representaes idealizadas (abstrata) dos problemas; geralmente fazem-se aproximaes e hipteses simplificadoras para que sejam resolvveis. Nessa fase do estudo, faz-se a construo do modelo. Um modelo deve especificar as expresses quantitativas para o objetivo e as restries do problema em termos de suas variveis de deciso. Existem vrios tipos bsicos de modelos, sendo que o modelo matemtico o modelo universal da Pesquisa Operacional; Os smbolos matemticos so usados para representar as variveis, as quais so ento representadas por funes matemticas apropriadas para descrever as operaes do sistema. A soluo do modelo ento procurada pela manipulao matemtica apropriada.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

26

Mtodo da Pesquisa OperacionalCONSTRUO DO MODELO MATEMTICO A estrutura bsica dos modelos de PO assume a forma: Z = f (x1, x2, x3, ...., xn; y1, y2, y3, ....yn) Onde: Z = funo objetivo (medida de eficincia do sistema); x1, x2, x3, xn = sistemas de variveis que so sujeitas ao controle; y1, y2, y3, yn = sistemas de variveis que no no sujeitas ao controle;

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

27

Mtodo da Pesquisa OperacionalCONSTRUO DO MODELO MATEMTICO Variveis de deciso e parmetros: As variveis de deciso so as incgnitas para serem determinadas da soluo do modelo. Os parmetros representam as variveis controladas do sistema. No exemplo da fbrica de brinquedos de Z da Gota, SOLDADO representado pela varivel X1 e TREM representado pela varivel X2; o parmetro, neste exemplo, leva em considerao o nvel de produo; Limitaes ou restries: Para considerar as limitaes fsicas do sistema, o modelo deve incluir restries que limitam os valores possveis das variveis de deciso. Isto , usualmente, expresso em forma de inequaes matemticas. Continuando com o exemplo do Z da Gota, X1 e X2 representam o tipo do produto a ser produzido (soldado ou trem) e a inequao 2X1 + 1X2 < 100 representa a limitao do sistema quanto ao insumo horas de acabamento.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 28

Mtodo da Pesquisa OperacionalCONSTRUO DO MODELO MATEMTICO Funo Objetivo: Define a medida de efetividade do sistema como uma funo matemtica de suas variveis de deciso. Por exemplo, se o objetivo do sistema maximizar o lucro total, a funo objetivo deve especificar o lucro em termos das variveis de deciso. No caso do exemplo da empresa de brinquedos de madeira de Z da Gota, a funo objetivo deve procurar maximizar o lucro. Assim, essa funo seria representada pela seguinte equao: MAX Z = 3X1 + 2X2

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

29

Mtodo da Pesquisa OperacionalOBTENO DE UMA SOLUO A PARTIR DO MODELO A partir da combinao da funo objetivo com as inequaes de restries, inicia-se o processo para obteno de uma soluo tima do modelo. TESTE DO MODELO E AVALIAO DA SOLUO OBTIDA O critrio indicado para julgar a validade de um modelo verificar se ele prediz ou no os efeitos relativos das linhas de ao alternativas com suficiente preciso de maneira a permitir uma deciso. ESTABELECIMENTO DE CONTROLE SOBRE A SOLUO Quando uma soluo for usada repetidamente, esta soluo s permanecer vlida para o problema real enquanto o modelo respectivo permanecer vlido. IMPLANTAO DA SOLUO A ltima fase de um estudo de pesquisa operacional consiste em implantar a soluo final.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 30

Tipos bsicos de modelo de Pesquisa Operacional Teoria da deciso; Modelos seqenciais (seqncia e coordenao); Modelos de alocao; Modelos de designao; Modelos de competio; Tcnicas clssicas de otimizao; Modelos de substituio (reposio); Modelos de estoque (teoria dos estoques); Modelos de filas; Tcnicas de simulao; Modelos de programao dinmica; Modelos de rotas.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

31

Programao Linear Sem dvida alguma a Programao Linear (PL) uma das tcnicas mais utilizadas em Pesquisa Operacional, quando a abordagem problemas de otimizao; Os problemas de PL buscam a distribuio eficiente de recursos limitados para atender um determinado objetivo, em geral, maximizar lucros ou minimizar custos; Em se tratando de PL, esse objetivo expresso atravs de uma funo linear, denominada de funo objetivo; necessrio, tambm, que se defina quais atividades que consomem recursos e em que propores os mesmos so consumidos. Essas informaes so apresentadas em forma de equaes, mais precisamente as inequaes lineares, sendo uma para cada recurso; Ao conjunto dessas inequaes, denomina-se restries do modelo

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

32

Programao Linear Normalmente se tem inmeras maneiras de distribuir os recursos escassos entre as diversas atividades em estudo, bastando para com isso que essas distribuies estejam coerentes com as restries do modelo. No entanto, o que se busca em um problema de PL a funo objetivo, isto , a maximizao do lucro ou a minimizao dos custos. A esta soluo d-se o nome de soluo tima. Assim, a Programao Linear se incube de achar a soluo tima de um problema, uma vez definido o modelo linear, ou seja, a funo objetivo e as restries lineares; Nos prximos slides ser abordada a soluo do problema da fbrica de brinquedos de Z Gota.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

33

Programao Linear Sabendo que a matria-prima necessria obtida sem problemas, Z da Gota tem como objetivo maximizar o lucro semanal (Receitas Custos); Formula-se, ento, matematicamente a situao de Z da Gota com o objetivo de maximizar o lucro de sua empresa, levantando-se, EM PRIMEIRO MOMENTO, as variveis de deciso. Nesse caso: X1 = nmero de soldados produzidos X2 = nmero de trens produzidos a cada semana Em qualquer modelo de PL, o decisor quer maximizar ou minimizar alguma funo das variveis de deciso. No caso estudado, Maximizar o lucro o objetivo de Z da Gota. Como lucro igual a Receitas Custos, observa-se que: LUCRO DE CADA SOLDADO = 27 (14 + 10) = 3, onde 27 a receita, 14 e 10 so os custos com mo-de-obra e matria-prima, respectivamente; LUCRO DE CADA TREM = 21 (10 + 9) = 2AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 34

Programao Linear Diante do exposto, o objetivo de Z da Gota escolher X1 e X2 para maximizar a Funo Objetivo, ou seja, escolher as quantidades ideais do produto X1 (SOLDADOS) e do produto X2 (TREM) que otimizaro o resultado da funo MAX Z = 3X1 + 2X2. Essa , exatamente, a SEGUNDA FASE em um modelo de simulao.

Varivel usualmente utilizada em PO

FUNO OBJETIVO: MAX Z = 3X1 + 2X2AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 35

Programao Linear O TERCEIRO PASSO compreender e definir as restries. Se X1 e X2 aumentam, o resultado da funo objetivo de Z da Gota ser sempre maior. Entretanto isso no ocorre por conta das limitaes de recursos, ou seja, da restrio das horas de mo-de-obra de carpintaria e acabamento, descritas abaixo: - 100 horas de acabamento esto disponveis (Restrio 1); - 80 horas de carpintaria esto disponveis (Restrio 2); - A demanda de soldados de 40 unidades semanais (Restrio 3); - No h limitaes de matria-prima. O PRXIMO PASSO expressar as restries 1, 2 e 3 em termos das variveis de deciso X1 e X2 (prximos slides).

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

36

Programao LinearRESTRIO 1: no h mais de 100 horas de acabamento Ento, o total de horas de acabamento por semana tem que ser igual a soma das horas de acabamento disponibilizadas para a produo de soldados mais as horas de acabamento disponibilizadas para a produo de Trem. J que o consumo de horas de acabamento de duas horas por soldado e de uma hora por Trem, essa restrio expressa pela seguinte inequao:

RESTRIO 1: 2X1 + 1X2 100

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

37

Programao LinearRESTRIO 2: no h mais de 80 horas de carpintaria Ento, o total de horas de carpintaria por semana tem que ser igual a soma das horas de carpintaria disponibilizadas para a produo de soldados mais as horas de carpintaria disponibilizadas para a produo de Trem. J que o consumo de horas de carpintaria de uma hora por soldado e de uma hora por Trem, essa restrio expressa pela seguinte inequao:

RESTRIO 2: 1X1 + 1X2 80RESTRIO 3: a demanda mxima de soldados de 40 semanal Assim o nmero mximo de soldados que podem ser vendidos por semana de 40 soldados. Para trem no h limitao da demanda. Essa restrio expressa pela seguinte inequao:

RESTRIO 3: X1 40AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 38

Programao LinearCONJUNTO DAS RESTRIES 2X1 + X2 100 X1 + 1X2 80 X1 40 Restries para o problema de PL do Z da Gota que usualmente representam a quantidade de recursos disponveis.

Restries AdicionaisCoeficientes tecnolgicos que refletem a quantia usada de insumos para diferentes produtos. Para completar a formulao do problema, cria-se restries adicionais para viabilizar a soluo, conforme segue: X1 0 X2 039

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Programao Linear

RESUMINDO MAX Z = 3X1 + 2X2 sujeito : 2X1 + X2 100 X1 + 1X2 80 X1 40 X1 0 X2 0

ObservaoTodo expoente X sem nmero possui uma unidade (1) oculta na equao/inequao

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

40

Programao LinearEXERCCIO SOBRE FORMULAO MATEMTICA: MAXIMIZARUma marcenaria produz mesas e cadeiras de um nico modelo, utilizando dois insumos: trabalho e madeira. Para produzir uma mesa so necessrias 10 horas de mo-de-obra e para uma cadeira, 02 horas de mo-de-obra. Cada mesa requer 10 unidades de madeira e cada cadeira, 05 unidades. Durante um perodo de tempo, a marcenaria dispe de 200 horas de mo-de-obra e 260 unidades de madeira. Se cada mesa gera um lucro de R$ 200,00 e cada cadeira fornece um lucro de R$ 90,00, QUAL A PRODUO QUE MAXIMIZA O LUCRO NAQUELE PERODO?

Resolva o exerccio anterior considerando que o lucro de cada mesa seja de R$ 600,00 e o lucro de cada cadeira de R$ 90,00.

Resolva o exerccio anterior considerando que o lucro de cada mesa seja de R$ 200,00 e o lucro de cada cadeira de R$ 180,00.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 41

Programao LinearEXERCCIO SOBRE FORMULAO MATEMTICA: MAXIMIZARUma empresa pode fabricar dois produtos (1 e 2). Na fabricao do produto 1 a empresa gasta nove horas-homem e trs horas-mquina. Na fabricao do produto 2 a empresa gasta uma hora-homem e uma hora-mquina. Sendo X1 e X2 as quantidades fabricadas dos produtos 1 e 2 e sabendo-se que a empresa dispe de 18 horas-homem e12 horasmquina e ainda que os lucros dos produtos so R$4,00 e R$1,00 respectivamente, quanto deve a empresa fabricar de cada produto para obter o maior lucro possvel? Uma empresa de informtica produz dois modelos de impressoras, A e B. O custo de produzir uma unidade de A R$ 300,00 e uma unidade de B R$ 400,00. Devido a restries de oramento, a empresa pode gastar por semana no mximo R$ 12.000,00. A capacidade de mo-deobra da empresa permite fabricar por semana, no mximo, 35 impressoras. Se cada unidade de A d uma margem de contribuio de R$ 60,00 e cada unidade de B d uma margem de R$ 70,00, qual a produo semanal que maximiza a margem de contribuio da empresa?AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 42

Programao LinearEXERCCIO SOBRE FORMULAO MATEMTICA: MINIMIZARUma determinada empresa automobilstica fabrica carros de luxo e caminhonetes. A empresa acredita que os mais provveis clientes so homens e mulheres com altos rendimentos. Para abordar estes grupos, a empresa decidiu por uma campanha de propagandas na TV, onde comprou vrias inseres de 1 minuto no horrio nobre do comercial de dois tipos de programa: Novela e Futebol. Cada comercial durante o programa de Novela visto por 7 milhes de mulheres e 2 milhes de homens com grande poder aquisitivo. Cada comercial durante a transmisso de Futebol visto por 2 milhes de mulheres e 12 milhes de homens com grande poder aquisitivo. Um minuto de comercial durante o programa de Novela custa R$ 50.000,00 e durante a transmisso de futebol custa R$ 100.000,00. A empresa gostaria que pelo menos 28 milhes de mulheres e 24 milhes de homens de grande poder aquisitivo assistissem sua propaganda. Diante dessas informaes, obter a programao matemtica que ir permitir a empresa atender as suas necessidades de propagando ao menor custo possvel.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 43

Programao LinearEXERCCIO SOBRE FORMULAO MATEMTICA: MAXIMIZARUma empresa fabrica carros e caminhonetes. Cada veculo precisa ser trabalhado nas sees de pintura e montagem. Se a seo de pintura trabalhar s com caminhonetes, 40 por dia podem ser pintados. Se estiver trabalhando somente com carros, 60 por dia sua capacidade. Se a seo de montagem estiver trabalhando somente com caminhonetes, 50 podem ser montados por dia. O mesmo nmero possvel para carros se este for o nico produto da linha. Cada caminhonete contribui com R$ 3.000,00 para o lucro da empresa e cada carro R$ 2.000,00. Obter a formulao matemtica que determinar a programao de produo que maximizar o lucro da empresa.

Supondo que a empresa do exemplo anterior, por necessidades dos vendedores, tem de produzir pelo menos 30 caminhonetes e 20 carros diariamente, qual ser a nova formulao do problema?AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 44

Programao LinearEXERCCIO SOBRE FORMULAO MATEMTICA: MAXIMIZARUma empresa produz dois produtos A e B em quantidades X e Y. Toda a produo vendida. Os custos unitrios de produo de A e B so R$ 8,00 e R$ 5,00, respectivamente, e os correspondentes preos de venda so R$ 10,00 e R$ 7,00. Os custos unitrios de transporte de A e B so respectivamente R$ 0,40 e R$ 0,60. Se a empresa pretende arcar com um custo de produo mensal de no mximo R$ 5.000,00 e um custo de transporte mensal de no mximo R$ 300,00, quais os valores de X e Y que maximizam a margem de contribuio mensal?

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

45

Soluo de um problema de PL Mtodo Grfico Um problema de Programao Linear (PL) s pode ser resolvido GRAFICAMENTE desde que o modelo, em estudo, apresente duas variveis (X1 , X2); O mtodo grfico resulta na regio de soluo para um problema de PL que atende ao conjunto de restries e satisfaz a funo objetivo; Vamos utilizar e exerccio 4 (quatro) do slide 42 como exemplo para soluo de um problema de PL pelo mtodo grfico:Uma empresa pode fabricar dois produtos (1 e 2). Na fabricao do produto 1 a empresa gasta nove horas-homem e trs horas-mquina. Na fabricao do produto 2 a empresa gasta uma hora-homem e uma hora-mquina. Sendo X1 e X2 as quantidades fabricadas dos produtos 1 e 2 e sabendose que a empresa dispe de 18 horas-homem e12 horas-mquina e ainda que os lucros dos produtos so R$4,00 e R$1,00 respectivamente, quanto deve a empresa fabricar de cada produto para obter o maior lucro possvel?

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

46

Soluo de um problema de PL Mtodo GrficoFuno Objetivo: MAX Z = 4X1 + 1X2 (funo do lucro)Sujeito s seguintes restries:

9X1 + X2 18 (restrio de horas homem) 3X1 + X2 12 (restries de horas mquina) X1 0 X2 0

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

47

Soluo de um problema de PL Mtodo Grfico

Primeiro precisamos saber, dado as restries, quais as possveis combinaes dos produtos que se pode fabricar. Isso , precisamos verificar qual ou quais as reas que satisfazem as restries, pois a empresa s pode dispor dos recursos "disponveis".

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

48

Soluo de um problema de PL Mtodo Grfico20 18 16 14 12 10 8 6 4 2 0 -1 -0 . 5 0 0.5 1 1.5 2 2.5 3 3.5 4

H-H 9x1 + x2 18

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

49

Soluo de um problema de PL Mtodo Grfico20 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3 4 5

H-M 3x1 + x2 12

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

50

Soluo de um problema de PL Mtodo Grfico Como a empresa no pode violar nenhuma das restries precisamos saber a rea onde as duas restries so vlidas, isso , a interseo das duas regies de restrio, chamada de conjunto de possibilidades ou conjunto vivel.20 18 16 14 12 10 8 6 4 2 0 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5 4

20 18 16 14

H-H 9x1 + x2 1812 10 8 6 4 2 0 -1 0 1 2

H-M 3x1 + x2 12

3

4

5

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

51

Soluo de um problema de PL Mtodo Grfico20 18 16 14 1220 18 16 14 12 10 8 6 4 2 0 -1 -0 .5 0 0. 5 1 1. 5 2 2 .5 3 3. 5 4

H-H 9x1 + x2 18

Conjunto Vivel

10 8 6 4 2 0 -1 0 1 2

20 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3 4 5

H-M 3x1 + x2 12

3

4

5

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

52

Soluo de um problema de PL Mtodo Grfico Resta agora maximizar o Lucro, que representado pela funo objetivo MAX Z = 4 X1 + X2. Como o lucro uma constante para cada uma das combinaes da X1 e X2, ou seja, das restries, quanto maior os insumos (menor restries) maior ser o lucro. Assim diferentes retas paralelas representam diferentes possibilidades de lucro, conforme exemplifica-se a seguir:20 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3 4 5

LUCRO = 4 X1 + X2

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

53

Soluo de um problema de PL Mtodo Grfico20 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3 4 5

Logo, deve-se fabricar X1 = 1 e X2 = 9, onde o lucro mximo R$ 13,00. Esses valores so fixados diretamente do grfico. Veja o que acontece com as restries nesses valores! No h sobras de insumos!AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 54

Soluo de um problema de PL Mtodo GrficoEXERCCIO SOBRE MTODO GRFICOSolucionar os exerccios 1, 2, 3, 5 e 6 da seo anterior por meio do mtodo grfico, DESENHANDO OS GRFICOS COM AUXLIO DE RGUA.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

55

Soluo de um problema de PL Mtodo SIMPLEX Nas formulaes anteriores, problemas com mais de duas variveis no poderiam ser solucionados com o mtodo grfico. Desta forma necessrio o estudo de outro mtodo para a busca de solues; Nessa seo ser apresentado mais um procedimento geral para resoluo de problemas de programao linear, denominado MTODO SIMPLEX e que foi desenvolvido em 1947 por Dantzig; O Mtodo Simplex um mtodo interativo utilizado para achar, algebricamente, a soluo tima de um problema de PL. TEOREMAS BSICOS DO MTODO SIMPLEX: Teorema 1: O conjunto de todas as solues compatveis do modelo de programao linear um conjunto convexo cujos vrtices (pontos extremos) correspondem a solues bsicas viveis; Teorema 2: Se a funo objetivo possui um mximo (ou mnimo) finito, ento pelo menos uma soluo tima um ponto extremo do conjunto convexo do teorema 1.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 56

Soluo de um problema de PL Mtodo SIMPLEXPROCEDIMENTOS DO MTODO SIMPLEX: Sabe-se que a soluo tima do modelo uma soluo bsica do sistema, ou seja, um ponto extremo do polgono gerado pelas restries; Para ser iniciado necessrio conhecer uma soluo compatvel bsica (soluo inicial) do sistema, isto , um dos pontos do polgono gerado; O Mtodo Simplex verifica se a presente soluo tima. Se for o processo est encerrado. Se no for tima, porque um dos pontos adjacentes fornece um valor maior que o inicial; Neste caso, o Mtodo Simplex faz ento a mudana do ponto por um outro ponto que mais aumente o valor da funo objetivo; O processo finaliza quando se obtm um ponto extremo onde todos os outros pontos extremos fornecem valores menores para a funo objetivo;AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 57

Soluo de um problema de PL Mtodo SIMPLEXPROCEDIMENTOS DO MTODO SIMPLEX: Como fazer, algebricamente, a mudana de um ponto extremo para outro? Achar, portanto, a prxima soluo bsica exige a escolha de uma varivel bsica para deixar a base atual, tornando-se no bsica, e a escolha de uma varivel no bsica para entrar na base em sua substituio;D Supondo o seguinte problema para maximizao: Max Z = 10X1 + 12X2 Sujeito a: X1 + X2 100 2X1 + 3X2 270 X1 0 A X2 0 C

B58

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXSabe-se que a soluo tima do modelo est em uma das vrtices, ou seja, um ponto extremo do polgono ABCD.Utilizando o mtodo grfico, observa-se a soluo no ponto C.

SIMPLEX1200 1000 1000 1140 1080

D C

RECEITA

800 600 400 200 0 0 ZA ZB ZC VRTICES DA REA DE SOLUO ZD

A

BAEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 59

Soluo de um problema de PL Mtodo SIMPLEX Como observa-se no exemplo do slide anterior, a soluo tima est no ponto C, que possui lucro de R$ 1140,00. Os outros pontos, possuem lucros menores, sendo que o ponto A possui lucro igual a Zero. Os resultados anteriores foram obtidos por meio da soluo grfica. Entretanto, caso no possamos utilizar o mtodo grfico, como fazer para descobrir o ponto (vrtice) com o maior lucro? O MTODO SIMPLEX, COMPREENDE OS SEGUINTES PASSOS:1. Transformar a funo objetivo em uma equao com resultado igual a zero; 2. Organizar as equaes/inequaes (inclusive a funo objetivo) em forma de tabela, acrescentando nessas equaes/inequaes as variveis de folga; 3. Definir a varivel que entra na base que melhore rapidamente o valor de Z; 4. Definir a varivel que sai da base, sendo que essa ser aquela que primeiro se anula com a entrada da varivel escolhida no item anterior; 5. Definir o elemento piv; 6. Calcular a nova soluo, utilizando os dados da linha piv; 7. Repetir os itens de 3 a 6, caso a soluo tima no seja a atual;AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 60

Soluo de um problema de PL Mtodo SIMPLEXRetornando questo de maximizao que foi solucionada pelo mtodo grfico, vamos resolv-lo, agora, pelo mtodo SIMPLEX: Max Z = 10X1 + 12X2 Sujeito a: X1 + X2 100 2X1 + 3X2 270 X1 0 X2 0 PASSO 1 Z 10X1 12X2 = 0 PASSO 2 Z 10X1 12X2 + 0X3 + 0X4 = 0 X1 + X2 + 1X3 + 0X4 100 2X1 + 3X2 + 0X3 + 1X4 270Z 1 0 0 X1 X2 X3 0 1 0 X4 0 0 1 B 0 B/X 0

-10 -12 1 2 1 3

100 100 270 9061

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEX

PASSO 5 PASSO 3 linha piv

Z 1PASSO 4

X1

X2

X3 0 1 0

X4 0 0 1

B 0

B/X 0

0

2

3

0

1

270

-10 -12 1 2 1 3

pelo elemento piv

0 0

100 100 270 90

3= nova linha piv0 0,67 1 0 0,33 9062

Elemento PIV

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXPASSO 6 O sexto passo o mais complexo de todos, motivo pelo qual sua obteno exige um alto grau de ateno e cuidado. Esse passo envolve reescrever cada uma das linhas da tabela obtida no passo 2, por meio de um procedimento matemtico que utiliza a nova linha piv:0 0,67 1 0 0,33 90

Aps obter os resultados da multiplicao, some-os com os valores das linhas originais da primeira tabela, conforme ilustrado abaixo:0 0,67 10

0 0,33 904 1080

X (12) = 8 12 0

Para tanto, multiplica-se os X2 elementos da nova linha piv pelo coeficiente da varivel que -12 entra, com sinal trocado, fazendo-se isso para cada nova 1 linha a ser criada. A linha que 3 entra a do passo 3:

+ primeira linha original

1 -10 -12 01 -2 0 0

04

0108063

igual a nova linha, ou seja...

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXPASSO 6 (continuao) Repete-se os procedimentos do slide anterior para as demais linhas da tabela que ainda no foram transformadas pelo processo de multiplicao do piv, ou seja: X2 0 0,67 1 0 0,33 900

Aps executar esse procedimento para todas as linhas, desenvolve-se uma nova tabela, conforme abaixo:Z 1 0 0 X1 -2 0,33 0,67 X2 0 0 1 X3 0 1 0 X4 4 -0,33 0,33 B 1080 10 90

X (-1) = -0,67 -1 01 1 1

-12

-0,33 -90

1 3

+ segunda linha original0 0 100

A soluo acima no a soluo tima, pois ainda existe nmero negativo na primeira linha; igual a nova linha, ou seja... Assim, repete-se todo o procedimento, encontrando-se uma nova linha piv, ou seja, iniciase o PASSO 7. AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 64

0 0,33 0

1 -0,33 10

Soluo de um problema de PL Mtodo SIMPLEXPASSO 7 Repete-se os de 3 a 6, anteriormente descritos, porm, agora, com a nova tabela.

linha piv

Z 1 0 0

X1 -2 0,33 0,67

X2 0 0 1

X3 0 1 0

X4 4

B

B/X

0

0,33 0

1

-0,33 10

1080 -540 30 1350

pelo elemento piv 0,33 = nova linha piv

-0,33 10 0,33 90

1

0

3

-1

30

Elemento PIVAEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 65

Soluo de um problema de PL Mtodo SIMPLEXPASSO 7 (continuao)0 1 0 3 -1 30

0

1

0X (2) =

3

-1

30

X (-0,67) =

X10 2 0 6 -2 60

0

-0,67

0

-2

0,67 -20

-2 0,33 0,67

+ terceira linha da segunda tabela

00

0,670

11

0-2

0,331

9070

+ primeira linha da segunda tabela

igual a nova linha, ou seja... culminando no resultado final, ou seja... Z X1 X2 X3 X4 B

1

-2

0

0

4

1080

igual a nova linha, ou seja...1 0 0 6 2 1140

1 0 0

0 1 0

0 0 1

6 3 -2

2 -1 1

1140 30 7066

Dado que no existem nmeros negativos na primeira linha, encontrou-se a soluo tima, com Z = 1140; 30 unidades de X1 e 70 unidades de X2, sendo esse o resultado final.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXConfrontando o resultado do SIMPLEX com a soluo grfica, abaixo, observa-se exatido dos procedimentos aqui adotados!SIMPLEX1200 1140 1000 1080

D

CRECEITA

1000 800 600 400 200 0 0 ZA

ZB ZC VRTICES DA REA DE SOLUO

ZD

A

BAEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 67

Soluo de um problema de PL Mtodo SIMPLEXNOVO EXEMPLO:

Max Z = 2X1 + 3X2 + X3 Sujeito a: X1 + X2 + X3 40 2X1 + X2 X3 20 3X1 + 2X2 X3 30 X1 0 X2 0 X3 0 Observe que para esse exemplo no possvel utilizar a soluo grfica!

PASSO 1 Z 2X1 3X2 X3 = 0 PASSO 2 Z 2X1 3X2 X3 + 0X4 + 0X5 + 0X6 = 0 X1 + X2 + X3 + 1X4 + 0X5 + 0X6 40 2X1 + X2 X3 + 0X4 + 1X5 + 0X6 20 3X1 +2X2 X3 + 0X4 + 0X5 + 1X6 30Z 1 0 0 0 X1 -2 1 2 3 X2 -3 1 1 2 X3 -1 1 -1 -1 X4 0 1 0 0 X5 0 0 1 0 X6 0 0 0 1 B 0 40 20 3068

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXNOVO EXEMPLO (continuao):Z 1 0 0 0 X1 -2 1 2 3 X2 -3 1 1 2 X3 -1 1 -1 -1 X4 0 1 0 0 X5 0 0 1 0 X6 0 0 0 1 B 0 40 20 30 B/X 0 40 20 150 3 2

linha piv-1 0 0 1 30

pelo elemento piv 2 = nova linha piv0 1,5 1 -0,5 0 0 0,5 15

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

69

Soluo de um problema de PL Mtodo SIMPLEXNOVO EXEMPLO (continuao):0 1,5 1 -0,5 0 0 0,5 15

20X2

1-3 1 1

1,5

1

-0,5

0

0

0,5

15

X (3) =0 4,5 3 -1,5 0 0 1,5 45

X (-1) =0 -1,5 -1 0,5 0 0 -0,5 -15

+ primeira linha original1 -2 -3 -1 0 0 0 0

+ segunda linha original0 1 1 1 1 0 0 40

igual a nova linha, ou seja...1 2,5 0 -2,5 0 0 1,5 45

igual a nova linha, ou seja...0 -0,5 0 1,5 1 0 -0,5 25

2

+ terceira linha original0 1,5 1 -0,5 0 0 0,5 15

3

0

2

1

-1

0

1

0

20

X (-1) =0 -1,5 -1 0,5 0 0 -0,5 -150

igual a nova linha, ou seja...0,5 0 -0,5 0 1 -0,570

5

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXNOVO EXEMPLO (continuao): linha pivZ 1 0 0 0 X1 2,5 -0,5 0,5 1,5 X2 0 0 0 1 X3 -2,5 1,5 -0,5 -0,5 X4 0 1 0 0 X5 0 0 1 0 X6 1,5 -0,5 -0,5 0,5 B 45 25 5 15 B/X -18 16,7 -10 -300 -0,5 0 1,5 1 0 -0,5 25

pelo elemento piv 1,5 = nova linha piv0 -0,33 0 1 0,67 0 -0,33 16,7

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

71

Soluo de um problema de PL Mtodo SIMPLEXNOVO EXEMPLO (continuao):0 -0,33 0 1 0,67 0 -0,33 16,7

20X3

1-2,5

-0,33

0

1

0,67

0

-0,33 16,7

X (2,5) =0 -0,83 0 2,5 1,67 0 -0,83 41,7

X (-0,5) =0 -0,17 0 0,5 0,34 0 -0,17 8,34

+ primeira linha original1 2,5 0 -2,5 0 0 1,5 45

+ segunda linha original0 0,5 0 -0,5 0 1 -0,5 5

1,5 -0,5 -0,5

igual a nova linha, ou seja...1 1,67 0 0 1,67 0 0,67 86,7

igual a nova linha, ou seja...0 0,33 0 0 0,34 1 -0,67 13,34

0

-0,33

0

1

0,67

0

-0,33 16,7

+ terceira linha original

3

0

1,5

1

-0,5

0

0

0,5

15

X (-0,5) =0 -0,17 0 0,5 0,34 0 -0,17 8,340

igual a nova linha, ou seja...1,34 1 0 0,34 0 0,34 23,3472

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Soluo de um problema de PL Mtodo SIMPLEXNOVO EXEMPLO (continuao):

Z 1Dado que no existem nmeros negativos na primeira linha, encontrou-se a soluo tima, com Z = 86,67; 0 unidades de X1,23,3 unidades de X2 e 16,7 unidades de X3, sendo esse o resultado final.

X1 1,67 -0,33 0,34 1,34

X2 0 0 0 1

X3 0 1 0 0

X4 1,67 0,67 0,34 0,34

X5 0 0 1 0

X6 0,67

B 86,7

0 0 0

-0,33 16,7 -0,67 13,3 0,34 23,3

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

73

Soluo de um problema de PL Mtodo SIMPLEXO MTODO SIMPLEX, PARA PROBLEMAS DE MINIMIZAOSe a funo objetivo for de minimizao, devemos multiplic-la por menos um (-1), obtendo uma funo equivalente para maximizao, nesse caso MAX (-Z). Assim, a funo objetivo ser resolvida com sinal contrrio, onde se mantm inalteradas as demais inequaes (ou equaes), resolvendo-se o problema de modo convencional. Determinado (-Z), troca-se o sinal. Dessa forma, Minimizar Z = 3X1 4X2 + X3, resolve-se assim:

MAX (-Z) = 3X1 + 4X2 X3AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 74

Soluo de um problema de PL Mtodo SIMPLEXEXERCCIO SOBRE MTODO SIMPLEXSolucionar os exerccios 1, 2 e 3 da seo anterior por meio do Mtodo SIMPLEX. Alm desses trs exerccios, resolver, tambm, os abaixo relacionados: Max Z = 2X1 + 3X2 + 4X3 Sujeito a: X1 + X2 + X3 100 2X1 + X2 210 X1 80 X1 0 X2 0 X3 0 Um fabricante de fantasias tem em estoque 32m de brim, 22m de seda e 30m de cetim e pretende fabricar dois modelos de fantasias. O primeiro modelo (M1) consome 4m de brim, 2m de seda e 2m de cetim. O segundo modelo (M2) consome 2m de brim, 4m de seda e 6m de cetim. Se M1 vendido a R$ 6.000,00 a unidade e M2 vendido a R$ 10.000,00, quantas peas de cada tipo o fabricante deve fazer para obter a receita mxima?75

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Uso de Softwares em Pesquisa Operacional

Eu no agento mais esse tal de SIMPLEX!

SOFTWARES A SEREM ABORDADOS LINPROG QM for WINDOWS LINDO SOLVER (Suplemento do EXCEL)

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

76

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

77

Uso de Softwares em Pesquisa OperacionalRESOLVER O PROBLEMA DO Z DA GOTA PELO LINPROG Z da Gota fabrica 2 tipos de brinquedos de madeira: soldados e trens. Aps recuperao da crise mundial de 2008, a empresa de Z da Gota no consegue mais cumprir seus pedidos, haja vista a limitao de horas de mo-de-obra capacitada, que no suficiente para atender a enorme demanda por seus produtos; Sabe-se que a fabricao desses brinquedos requer dois tipos de mo-de-obra: carpintaria e acabamento. A cada semana, Z da Gota pode obter qualquer quantidade de matria-prima, mas tem a disposio somente 100 horas de acabamento e 80 horas de carpintaria; Diante dessa situao, Z da Gota precisa tomar uma deciso que envolve quais produtos produzir e em quais quantidades, de forma a maximizar seu lucro; O quadro no prximo slide informa dados importantes para essa tomada de deciso.

MAX Z = 3X1 + 2X2 sujeito : 2X1 + X2 100 X1 + X2 80 X1 40 X1 0 X2 078

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

79

Uso de Softwares em Pesquisa OperacionalOUTRO EXEMPLO: MAX Z = 5X1 + 2X2 sujeito : X1 3 X2 4 X1+ 2X2 9 X1 0 X2 0

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

80

Uso de Softwares em Pesquisa Operacional

QM for WINDOWS

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

81

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

82

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

83

Uso de Softwares em Pesquisa OperacionalResolver o problema anterior (resolvido pelo LINPROG) pelo QM MAX Z = 5X1 + 2X2 sujeito : X1 3 X2 4 X1+ 2X2 9 X1 0 e X2 0

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

84

Uso de Softwares em Pesquisa OperacionalComo o problema anterior de duas variveis, o QM for Windows, o soluciona graficamente

Como o problema anterior de duas variveis, o QM for Windows, o soluciona graficamente

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

85

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

86

Uso de Softwares em Pesquisa OperacionalLINDO (Linear Interactive and Discrete Optimizer) foi desenvolvido por Linus Schrage em 1986. Trata-se de um programa de computador que pode ser usado para resolver problemas de programao linear. Para ilustrar seu uso, vamos usar o exemplo do Z da Gota, discutido anteriormente e que foi sintetizado na seguinte formulao:

Lindo.lnk MAX Z = 3X1 + 2X2 sujeito : 2X1 + X2 100 X1 + X2 80 X1 40 X1 0 X2 087

Lindo.lnk

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Uso de Softwares em Pesquisa Operacional

Para usar o LINDO, siga os seguintes passos:1. Digite o ttulo do exerccio (use sempre o sinal de exclamao no ttulo); 2. Digite a funo objetivo; 3. Digite as restries, imediatamente abaixo da sigla st; 4. Termine com a palavra end

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

88

Uso de Softwares em Pesquisa Operacional

Aps digitar todos os termos da funo, clique nesse boto para resolver o problema.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

89

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

90

Uso de Softwares em Pesquisa OperacionalRepetindo os procedimentos para o exerccio 4 do slide 75: Max Z = 2X1 + 3X2 + 4X3 Sujeito a: X1 + X2 + X3 100 2X1 + X2 210 X1 80 X1 0 X2 0 X3 0

Lindo.lnk

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

91

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

92

Uso de Softwares em Pesquisa OperacionalEXERCCIOS COM UTILIZAO DE SOFTWARE

PARTE 1Como eu sou um bom aluno, agora eu vou solucionar os exerccios 1, 2, 3, 4, 5, 6, 7, 8 e 9 que constam nos slides 41 a 45 com auxlio dos softwares LINPROG, QM e LINDO. Alm desses exerccios, eu tambm vou resolver os exerccios 4 e 5 do slide 75. Primeiro vou resolver todos pelo LINPROG. Depois, resolvo todos pelo QM for WINDOWS e, por ltimo vou resolver todos pelo LINDO. O professor vai ficar feliz da vida comigo!

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

93

Uso de Softwares em Pesquisa OperacionalSOLVER Dentre as ferramentas que vm ganhando cada vez mais adeptos para a soluo de problemas de programao linear, as Planilhas Eletrnicas so as preferidas, pois, alm da facilidade de utilizao, esto presentes em praticamente todas as empresas modernas; Dentre as planilhas, as mais utilizadas so o EXCEL da Microsoft, a Lottus da IBM e o Quattro-Pro da Corel. Todas essas planilhas dispem, basicamente, das mesmas ferramentas, diferindo apenas na forma do comando empregado. Em nossa disciplina, estaremos focalizando a utilizao da Planilha EXCEL da Microsoft, por ser a mais popular no Brasil; Presumi-se que o estudante tenha um conhecimento bsico de operao de uma planilha no EXCEL. Caso contrrio, recomendamos cursos de extenso de curta durao, curso de frias, cursos na modalidade EAD, entre outros, todos relacionados com EXCEL, para suprir essa carncia;AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 94

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

95

Uso de Softwares em Pesquisa OperacionalSOLVER O sucesso da soluo de um problema de programao linear com utilizao do SOLVER est na maneira como as clulas so organizadas, preparadas e como elas se ligam com a funo objetivo e com as restries do sistema; Primeiramente, deve-se designar um clula para representar cada uma das seguintes entidades: Funo objetivo (MAX ou MIN Z); Variveis de deciso (X1, X2, X3...Xn); Para cada restrio: # Uma para o lado esquerdo da restrio LHS (left hand side); # Uma para o lado direito da restrio RHS (right hand side); O prximo slide apresenta uma das possveis maneiras de se representar um problema de Programao Linear no SOLVER, seguindo as orientaes anteriores;AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 96

Uso de Softwares em Pesquisa OperacionalPREPARANDO A PLANILHA EXCEL PARA O SOLVER

EXEMPLO MAX Z = 3X1 + 2X2 Sujeito X1 + 2X2 6 2X1 + X2 8 -X1 + X2 1 X2 2 X1 0 X2 0

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

97

Uso de Softwares em Pesquisa OperacionalSOLVER Aps prepararmos a Planilha Excel, alimentando-a com os dados que se deseja resolver um problema de PL, precisamos mostrar ao EXCEL quais so as clulas que representam a funo objetivo, as variveis de deciso, as restries do modelo e, finalmente, mandar o EXCEL, por meio do SOLVER, resolver para ns; ANTES, porm, precisamos definir como as clulas se comunicam, para solucionar o problema de maximizao, levando em considerao as variveis de restrio, desenvolvendo frmulas entre elas, conforme tabela abaixo:

B6 D10 D11 D12 D13

=(B3*B4) + (C3*C4) =(B10*$B$4+C10*$C$4 =(B11*$B$4+C11*$C$4 =(B12*$B$4+C12*$C$4 =(B13*$B$4+C13*$C$4

Funo Objetivo LHS da 1 restrio LHS da 2 restrio LHS da 3 restrio LHS da 4 restrio98

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

99

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

100

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

101

Uso de Softwares em Pesquisa OperacionalDEMONSTRAO DE OUTRO EXEMPLO COM O SOLVER

EXEMPLO Max Z = 2X1 + 3X2 + X3 Sujeito a: X1 + X2 + X3 40 2X1 + X2 X3 20 3X1 + 2X2 X3 30 X1 0 X2 0 X3 0AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 102

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

103

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

104

Uso de Softwares em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

105

Uso de Softwares em Pesquisa OperacionalEXERCCIOS COM UTILIZAO DE SOFTWARE

PARTE 2Como eu quero tirar uma boa nota na AV1, agora eu vou solucionar os exerccios 1, 2, 3, 4, 5, 6, 7, 8 e 9 que constam nos slides 41 a 45 com auxlio SOLVER. Alm desses exerccios, eu tambm vou resolver os exerccios 4 e 5 do slide 75. Eu vou tirar DEZ!

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

106

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE ORAMENTO DE CAPITAL Uma empresa de petrleo est considerando 5 diferentes oportunidades de investimento. O Fluxo de Caixa e o Valor Presente Lquido das alternativas so dadas na tabela a seguir: ALTERNATIVAS ALT. 1 ALT. 2 ALT.3 ALT.4 ALT.5 Investimento na data zero (ANO 0) 11 53 5 5 29 Investimento na data um (ANO 1) 3 6 5 1 34 VPL 13 16 16 14 39 A empresa possui R$ 40.000.000,00 para investir hoje e no prximo ano ter R$ 20.000.000,00; A empresa pode comprar qualquer frao de cada investimento. Dessa forma os investimentos e o VPL so ajustados proporcionalmente. Por exemplo, se a empresa compra 20% da alternativa 3 (ALT. 3), ento apenas R$ 1MM necessrio nos anos 0 e 1. Nessa situao, o VPL seria de R$ 3,2MM (16MM x 20%)AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 107

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE ORAMENTO DE CAPITAL A empresa em questo quer MAXIMIZAR o VPL obtido para as ALTERNATIVAS de 1 a 5. Diante dessa situao, tome as seguintes providncias: 1. Formule o problema, definindo sua funo objetivo e inequaes de restries; 2. Resolva o problema utilizando qualquer um dos quatro softwares utilizados em nossa disciplina; 3. Informe a resposta final, interpretando-a. Assuma que qualquer recurso no usado no ANO 0 no poder ser utilizado no ANO 1.

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

108

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO ORAMENTO DE CAPITAL O primeiro passo consiste em definir as variveis de deciso. Para esse caso, a empresa precisa determinar a frao de cada investimento para aquisio: Xi = frao do investimento i comprado pela empresa. (i = 1;2;3;4;5) O segundo passo consiste em desenvolver a funo objetivo. Nesse caso o objetivo maximizar o VPL dos investimentos: VPL total = VP1 + VP2 + VP3 + VP4 + VP5, ou seja: MAX Z = 13X1 + 16X2 + 16X3 + 14X4 + 39X5

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

109

Exemplos Relevantes em Pesquisa Operacional 1. 2. 3. SOLUO: OTIMIZAO ORAMENTO DE CAPITAL O terceiro passo consiste em levantar as restries do problema, que so as seguintes: A empresa no pode investir mais do que R$ 40.000.000,00 hoje: A empresa no pode investir mais do que R$ 20.000.000,00 no primeiro ano; A empresa no pode comprar mais que 100% de cada investimento; 11X1 + 53X2 + 5X3 + 5X4 + 29X5 40 3X1 + 6X2 + 5X3 + X4 + 34X5 20 X1 1 X2 1 X3 1 X4 1 X5 1 X1, X2, X3, X4,X5 0 A resposta, para esse problema : X1 = X2 = X3 = 1 (100%) X2 = 0,201 (20,10%) X5 = 0,288 (28,80%) Z = R$ 57.449.000,00110

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Exemplos Relevantes em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

111

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE PROGRAMAO DO TRABALHO Uma empresa de entregas necessita de diferentes nmeros de funcionrios durante os diferentes dias da semana. Os nmeros de funcionrios necessrios mostrado na tabela ao lado:Dia da semana Dia Dia Dia Dia Dia Dia Dia 1 2 3 4 5 6 7 = segunda-feira = tera-feira = quarta-feira = quinta-feira = sexta-feira = sbado = domingo N funcionrios necessrios 17 13 15 19 14 16 11

As leis do sindicato asseguram que os funcionrios devem trabalhar 5 dias consecutivos e 2 dias de folga; A empresa trabalha apenas com funcionrios de tempo integral; Formular o problema de tal modo que a empresa possa minimizar o nmero de empregados de tempo integral que precisam ser contratados. Aps, resolv-lo em qualquer software.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 112

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE PROGRAMAO DO TRABALHOX1 SEG X1 X2 X3 X4 X5 X6 X7 >17 >13 >15 >19 >14 >16 >11113

X2 TER

X3 QUAR

X4 QUIN

X5 SEX

X6 SAB

X7 DOM

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE PROGRAMAO DO TRABALHO A empresa em questo quer MINIMIZAR os custos com pagamento de salrios, minimizando o nmero de funcionrios a serem contratados; As variveis de deciso estaro relacionadas ao nmero de empregados que iniciam seu trabalho a cada dia, ou seja: - Xi = nmero de empregados que comeam a trabalhar no dia i; - i = 1, 2, 3.....7 -1 = segunda, 2 = tera, ....7 = domingo; - Por exemplo: X1 = nmero de empregados que comeam a trabalhar na segunda-feira. A funo objetivo, ser a seguinte: MIN Z = X1 + X2 + X3 + X4 + X5 + X6 + X7AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 114

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO PROGRAMAO DO TRABALHO Quanto as restries, necessrio garantir o nmero mnimo de funcionrios todos os dias, onde na segunda-feira, por exemplo, de pelo menos 17 funcionrios; Quem trabalha na segunda-feira? Todos funcionrios, exceto os que iniciam suas atividades na tera e quarta-feira; Dessa forma, o nmero de empregados que trabalham na segunda-feira expresso da seguinte forma: X1 + X4 + X5 + X6 + X7AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 115

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE PROGRAMAO DO TRABALHO No caso das restries, a empresa deve ter um mnimo de funcionrios trabalhando de segunda a domingo, culminando na seguinte combinao de inequaes de restries: X1 + X4 + X5 + X6 + X7 17 (seg) X1 + X2 + X5 + X6 + X7 13 (ter) X1 + X2 + X3 + X6 + X7 15 (quar) X1 + X2 + X3 + X4 + X7 19 (quin) X1 + X2 + X3 + X4 + X5 14 (sex) X2 + X3 + X4 + X5 + X6 16 (sb) X3 + X4 + X5 + X6 + X7 11 (dom)X1 SEG X1 X2 X3 X4 X5 X6 X7 >17 >13 >15 >19 >14 >16 >11 X2 TER X3 QUAR X4 QUIN X5 SEX X6 SAB X7 DOM

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

116

Exemplos Relevantes em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

117

Exemplos Relevantes em Pesquisa OperacionalX1 SEG X1 X2 X3 X4 X5 X6 X7 8 0 4 0 >17 19 0 4 0 >13 16 4 0 >15 17 0 >19 21 >14 21 >16 18 7 X2 TER 7 5 X3 QUAR 7 5 1 X4 QUIN 7 5 1 8 X5 SEX 7 5 1 8 0 5 1 8 0 4 1 8 0 4 0 >11 13 X6 SAB X7 DOM

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

118

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE MISTURA Uma fabricante de sorvete deseja produzir 100kg de sorvete, cuja receita a seguinte:EXIGNCIA Gordura Slidos de Leite (no gordurosos) Total de slidos do leite Acar Total de slidos gua Estabilizador Emulsificador SIGLA GORD SLNG TSL AC TS AG EST EMU MNIMO 10 10,5 20,5 11 37,5 58,5 0,37 0,10 MXIMO 16 13 25 17 41,5 62,5 0,37 0,10

Como objetivo, estabelea a formulao matemtica do problema que minimize o custo de produo.AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira 119

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE MISTURA As seguintes matrias-primas esto disponveis:NOME Creme 40% Creme 38% Leite 3,2% Leite 4,0% Leite condensado G Leite condensado M Manteiga Slidos secos whey Sacarose Garapa Estabilizador Emulsificador gua % GORD 40 38 3,2 4,0 8 5 %SLNG 5,4 5,6 8,7 8,6 20 28 92 95 %TSL 45,4 43,6 11,9 12,6 28 28 97 95 % AC % TS 45,4 43,6 11,9 12,6 28 28 97 95 100 67 80 % AG 54,6 56,4 88,1 87,4 72 72 3 5 33 20 100 CUSTO 27 26 3 3 7 3 15 10 10 9 55 78 0

100 67

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

120

Exemplos Relevantes em Pesquisa OperacionalEXEMPLO DE OTIMIZAO DE MISTURA Para esse problema, o primeiro passo consiste em determinar as variveis de deciso. Nesse caso, elas sero as quantidades de cada tipo de matria prima que podero fazer parte do sorvete, ou seja:

Variveis de deciso: X1 = Quantidade em Kg de Creme 40% X2 = Quantidade em Kg de Creme 38% .... X12= Quantidade em Kg de emulsificador X13 = Quantidade em Kg de gua

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

121

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO DE MISTURA O segundo passo consiste em desenvolver a funo objetivo. Nesse caso o objetivo minimizar o custo de produo de sorvete; MIN Z = 27X1 + 26X2 + 3X3 + 3X4 + 7X5 + 3X6 + 15X7 + 10X8 + 10X9 + 9X10 +55X11 + 78X12 + 0X13 O terceiro passo consiste em desenvolver as inequaes de restries, que ser a quantidade mnima e mxima de cada ingrediente que faz parte da receita do sorvete, que nesse caso somam 15 restries;EXIGNCIA Gordura Slidos de Leite (no gordurosos) Total de slidos do leite Acar Total de slidos gua Estabilizador Emulsificador SIGLA GORD SLNG TSL AC TS AG EST EMU MNIMO 10 10,5 20,5 11 37,5 58,5 0,37 0,10 MXIMO 16 13 25 17 41,5 62,5 0,37 0,10

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

122

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO DE MISTURA GORDURA:0,40X1 + 0,38X2 + 0,032X3 + 0,04X4 + 0,08X5 + 0,05X7 10 0,40X1 + 0,38X2 + 0,032X3 + 0,04X4 + 0,08X5 + 0,05X7 16

SLIDOS DE LEITE (NO GORDUROSOS):0,054X1 + 0,056X2 + 0,087X3 + 0,086X4 + 0,20X5 + 0,28X6 + 0,92X7 + 0,95X8 10,5 0,054X1 + 0,056X2 + 0,087X3 + 0,086X4 + 0,20X5 + 0,28X6 + 0,92X7 + 0,95X8 13EXIGNCIA Gordura Slidos de Leite (no gordurosos) Total de slidos do leite Acar Total de slidos gua Estabilizador Emulsificador SIGLA GORD SLNG TSL AC TS AG EST EMU MNIMO 10 10,5 20,5 11 37,5 58,5 0,37 0,10 MXIMO 16 13 25 17 41,5 62,5 0,37 0,10

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

123

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO DE MISTURA TOTAL DE SLIDOS NO LEITE:0,454X1 + 0,436X2 + 0,119X3 + 0,126X4 + 0,28X5 + 0,28X6 + 0,97X7 + 0,95X8 20,5 0,454X1 + 0,436X2 + 0,119X3 + 0,126X4 + 0,28X5 + 0,28X6 + 0,97X7 + 0,95X8 25

ACCAR:X9 + 0,67X10 11 X9 + 0,67X10 17EXIGNCIA Gordura Slidos de Leite (no gordurosos) Total de slidos do leite Acar Total de slidos gua Estabilizador Emulsificador SIGLA GORD SLNG TSL AC TS AG EST EMU MNIMO 10 10,5 20,5 11 37,5 58,5 0,37 0,10 MXIMO 16 13 25 17 41,5 62,5 0,37 0,10

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

124

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO DE MISTURA TOTAL DE SLIDOS:0,454X1 + 0,436X2 + 0,119X3 + 0,126X4 + 0,28X5 + 0,28X6 + 0,97X7 + 0,95X8 + X9 + 0,67X10 + 0,80X11 37,5 0,454X1 + 0,436X2 + 0,119X3 + 0,126X4 + 0,28X5 + 0,28X6 + 0,97X7 + 0,95X8 + X9 + 0,67X10 + 0,80X11 41,5

GUA:0,546X1 + 0,564X2 + 0,881X3 + 0,874X4 + 0,72X5 + 0,72X6 + 0,03X7 + 0,05X8 + 0,33X10 + 0,20X11 + X13 58,5 0,546X1 + 0,564X2 + 0,881X3 + 0,874X4 + 0,72X5 + 0,72X6 + 0,03X7 + 0,05X8 + 0,33X10 + 0,20X11 + X13 62,5EXIGNCIA Gordura Slidos de Leite (no gordurosos) Total de slidos do leite Acar Total de slidos gua Estabilizador Emulsificador SIGLA GORD SLNG TSL AC TS AG EST EMU MNIMO 10 10,5 20,5 11 37,5 58,5 0,37 0,10 MXIMO 16 13 25 17 41,5 62,5 0,37 0,10

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

125

Exemplos Relevantes em Pesquisa OperacionalSOLUO: OTIMIZAO DE MISTURA ESTABILIZADOR:X11 = 0,37

EMULSIFICADOR:X12 = 0,10

PESO:X1 + X2 + X3 + X4 + X5 + X6 + X7 +X8 + X9 + X10 + X11 + X12 + X13 =100EXIGNCIA Gordura Slidos de Leite (no gordurosos) Total de slidos do leite Acar Total de slidos gua Estabilizador Emulsificador SIGLA GORD SLNG TSL AC TS AG EST EMU MNIMO 10 10,5 20,5 11 37,5 58,5 0,37 0,10 MXIMO 16 13 25 17 41,5 62,5 0,37 0,10

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

126

Exemplos Relevantes em Pesquisa Operacional

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

127

Exemplos Relevantes em Pesquisa OperacionalFUNO OBJETIVO COEFICIENTES DAS VARIVEISX1 27 X2 26 X3 3 X4 3 X5 7 X6 3 X7 15 X8 10 X9 10 X10 9 X11 55 X12 78 X13 0

ITENS UTILIZADOS RESPOSTA (Z) RESTRIES Gordura Gordura SLNG SLNG TSL TSL Aucar Aucar TS TS gua gua Estabilizador Emulsificardor Peso

19,088 934,08

0

0 59,123

0

0

0 4,6155 16,704

0

0,37

0,1

0

LHS0,400 0,400 0,054 0,054 0,454 0,454 0,380 0,380 0,056 0,056 0,436 0,436 0,032 0,032 0,087 0,087 0,119 0,119 0,040 0,040 0,086 0,086 0,126 0,126 0,080 0,080 0,200 0,200 0,280 0,280 0,280 0,280 0,280 0,280 0,050 0,050 0,920 0,920 0,970 0,970 0,950 0,950 0,950 0,950 1,000 1,000 0,454 0,454 0,546 0,546 0,436 0,436 0,564 0,564 0,119 0,119 0,881 0,881 0,126 0,126 0,874 0,874 0,280 0,280 0,720 0,720 0,280 0,280 0,720 0,720 0,970 0,970 0,030 0,030 0,950 0,950 0,050 0,050 1,000 1,000 0,670 0,670 0,670 0,670 0,330 0,330 0,800 0,800 0,200 0,200 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 1,000 10 10 10,5 10,5 20,5 20,5 16,704 16,704 37,5 37,5 62,4 62,4 0,37 0,1 100

RHS10,00 16,00 10,50 13,00 20,50 25,00 11,00 17,00 37,50 41,50 58,50 62,50 0,37 0,10 100,00

AEDB Pesquisa Operacional Prof. Dr. Ualison Rbula de Oliveira

128

EXEMPLO DE OTIMIZAO DE MISTURAMicrosoft Excel 11.0 Relatrio de resposta Planilha: [MISTURA SORVETE.xls]Problema Sorvete Relatrio criado: 2/2/2010 16:08:29 Clula de destino (Mn) Clula Nome $B$8 RESPOSTA (Z) X1 Clulas ajustveis Clula Nome $B$6 ITENS UTILIZADOS X1 $C$6 ITENS UTILIZADOS X2 $D$6 ITENS UTILIZADOS X3 $E$6 ITENS UTILIZADOS X4 $F$6 ITENS UTILIZADOS X5 $G$6 ITENS UTILIZADOS X6 $H$6 ITENS UTILIZADOS X7 $I$6 ITENS UTILIZADOS X8 $J$6 ITENS UTILIZADOS X9 $K$6 ITENS UTILIZADOS X10 $L$6 ITENS UTILIZADOS X11 $M$6 ITENS UTILIZADOS X12 $N$6 ITENS UTILIZADOS X13 Restries Clula $O$11 $O$12 $O$13 $O$14 $O$15 $O$16 $O$17 $O$18 $O$19 $O$20 $O$21 $O$22 $O$23 $O$24 $O$25

Valor original 1342,684614

Valor final 934,0815986

Valor original 0 36,95213379 0 0 0 0 9,16378316 0 0 24,0358209 0,37 0,1 29,37826215

Valor final 19,08771952 0 0 59,12280475 0 0 0 4,615475725 16,70399999 0 0,37 0,1 0

Nome Gordura LHS Gordura LHS SLNG LHS SLNG LHS TSL LHS TSL LHS Aucar LHS Aucar LHS TS LHS TS LHS gua LHS gua LHS Estabilizador LHS Emulsificardor LHS Peso LHS

Valor da clula 10 10 10,5 10,5 20,5 20,5 16,70399999 16,70399999 37,5 37,5 62,4 62,4 0,37 0,1 100

Frmula $O$11>=$P$11 $O$12=$P$13 $O$14=$P$15 $O$16=$P$17 $O$18=$P$19 $O$20=$P$21 $O$22