Prévia do material em texto
Autores: Prof. Fernando Eduardo Peres Prof. Mauricio Martins do Fanno Colaboradores: Prof. Flávio Celso Müller Martin Prof. Fábio Gomes da Silva Prof. Jorge Rodolfo Beingolea Garay Pesquisa Operacional Professores conteudistas: Fernando Eduardo Peres/Maurício Martins do Fanno Prof. Ms. Fernando Eduardo Peres, nascido na Cidade de Santos, no Estado de São Paulo, é formado em Matemática (Licenciatura e Bacharelado) e Pedagogia. É pós‑graduado em Administração de Sistemas de Informação, Formação Didática do Ensino Superior e mestre em Administração de Empresas. Atua como professor do Ensino Superior desde 1986 em diversas faculdades e universidades, lecionando disciplinas voltadas à formação de engenheiros e administradores, tanto na área da Matemática como da Administração. Na UNIP, ministra aulas desde 1996, das disciplinas de Tecnologia da Informação, Gestão da Informação e Pesquisa Operacional. Prof. Maurício Martins do Fanno, nascido na cidade de São Paulo, no Estado de São Paulo, é formado em Engenharia Mecânica pela Faculdade de Engenharia Industrial (FEI) e é pós‑graduado em Formação Didática do Ensino Superior. Desempenhou funções de Gerente e Diretor em diversas empresas nacionais, nas áreas de Engenharia, Manutenção e Produção. É professor do Ensino Superior desde 1986 e atua em diversas faculdades e universidades, lecionando disciplinas voltadas à formação de administradores, tanto na área da Matemática como de Administração. Na UNIP, ministra aulas desde 1993, das disciplinas Estatística, Administração da Produção e Materiais e Pesquisa Operacional. © Todos os direitos reservados. Nenhuma parte desta obra pode ser reproduzida ou transmitida por qualquer forma e/ou quaisquer meios (eletrônico, incluindo fotocópia e gravação) ou arquivada em qualquer sistema ou banco de dados sem permissão escrita da Universidade Paulista. Dados Internacionais de Catalogação na Publicação (CIP) P437p Peres, Fernando Eduardo Pesquisa operacional / Fernando Eduardo Peres, Maurício Martins do Fanno. ‑ São Paulo: Editora Sol, 2015. 84 p. il. Nota: este volume está publicado nos Cadernos de Estudos e Pesquisas da UNIP, Série Didática, ano XXI, n. 2‑147/15, ISSN 1517‑9230. 1. Pesquisa operacional. 2. Modelagem do problema. 3.Função objetivo. I. Título. CDU 65.012.122 CENTRO UNIVERSITÁRIO PLANALTO DO DISTRITO FEDERAL – UNIPLAN Reitoria Reitor: Prof. Yugo Okida Vice-Reitor: Prof. Fábio Nogueira Carlucci Pró-Reitor Acadêmico: Prof. Humberto Venderlino Richter Pró-Reitor Administrativo: Prof. Robson do Nascimento Sumário Pesquisa Operacional APRESENTAçãO ......................................................................................................................................................7 INTRODUçãO ...........................................................................................................................................................8 Unidade I 1 HISTóRICO DA PESqUISA OPERACIONAL .............................................................................................. 11 2 OBJETIVOS E METODOLOGIA DA PESqUISA OPERACIONAL ........................................................... 15 3 MODELAGEM E FORMAS DE REPRESENTAçãO DE PROBLEMAS ................................................. 17 4 CAMPOS DE APLICAçãO DA PO: TÉCNICAS E MÉTODOS ................................................................ 20 Unidade II 5 MODELAGEM DO PROBLEMA ..................................................................................................................... 25 6 TIPOS DE SOLUçãO ........................................................................................................................................ 27 6.1 Solução gráfica ...................................................................................................................................... 27 6.2 Solução pelo algoritmo Simplex .................................................................................................... 32 6.3 Solução computacional – utilizando ferramenta Solver do MS Excel® ........................ 49 Unidade III 7 PROBLEMAS ENVOLVENDO MINIMIzAçãO DA FUNçãO OBJETIVO ........................................... 61 7.1 Algoritmo Simplex ............................................................................................................................... 61 7.2 Solução computacional ..................................................................................................................... 70 8 APLICAçõES TíPICAS ...................................................................................................................................... 75 7 APrEsEntAçãO Prezado aluno, Este texto foi produzido para apresentar os principais conceitos da Pesquisa Operacional (PO), campo do conhecimento destinado a solucionar problemas com a utilização de modelos matemáticos. Profissionalmente ou mesmo pessoalmente, estamos sempre tomando decisões, ou seja, avaliando, entre diversas opções, a mais adequada. Na maioria das vezes, essas decisões são tomadas por meio de ações reflexas condicionadas ou simplesmente por hábito. É assim, por exemplo, que dirigimos nosso automóvel todos os dias. Não “pensamos” no que fazer antes de cada movimento que fazemos no trânsito. Este material e a Pesquisa Operacional (PO) não se preocupam, no entanto, com essas decisões reflexas, e sim com as decisões conscientes, aquelas nas quais há um método racional de solução. José Celso Contador (1998) afirma que uma decisão consciente é formalizada em seis etapas: • formulação do problema e fixação do objetivo; • construção do modelo ou modelagem do problema; • validação do modelo; • obtenção da solução; • avaliação da solução; • implantação, acompanhamento e manutenção da solução. Evidentemente, um processo tão formal como o mencionado é necessário quando trabalhamos com problemas complexos, mas de modo geral, ainda que de uma maneira mais intuitiva, menos formal, usamos essas etapas mesmo quando trabalhamos com problemas mais simples, seja no campo das decisões qualitativas, seja no das quantitativas. Decisões qualitativas envolvem fatos que não são quantificáveis; por exemplo, a decisão de um gerente industrial de aumentar a produção porque supõe ou pressente que o mercado irá melhorar. Essas decisões não são objeto do nosso estudo nesta disciplina. Decisões quantitativas envolvem fatos quantificáveis, ou seja, situações que podem ser mensuradas e atribuídos valores numéricos a ela. Por exemplo, uma empresa que tem as fontes de matéria‑prima e os clientes dispersos geograficamente pode decidir, por meio de um modelo matemático, qual é a melhor localização para suas atividades industriais, que torne os custos logísticos os mínimos possíveis. O tratamento desses modelos matemáticos é o objetivo da PO. 8 Os tradicionais textos sobre Pesquisa Operacional apresentam fundamentação matemática extremamente complexa. Todavia, pretendemos apresentar o assunto de modo que apenas os conhecimentos elementares de Matemática sejam requeridos. Dessa forma, nenhuma demonstração matemática faz parte do escopo deste trabalho. Churchman, Ackoff e Arnoff (apud CONTADOR, 1998) conceitua Pesquisa Operacional como “a aplicação de instrumentos, técnicas e métodos científicos a problemas relativos ao funcionamento de um sistema, permitindo a obtenção de soluções ótimas para esses problemas”, e ressalta que ela é caracterizada pela utilização de modelos matemáticos para orientar os executivos na tomada de decisões a respeito de operações sob seu controle, estando inserida na Teoria dos Sistemas. Observe a ênfase na caracterização de sistemas e de aspectos matemáticos. Essa caracterização é importante porque cada sistema é parte de um sistema mais amplo e pode ser composto por sistemas menos amplos. Nem todos os sistemas são passiveis de serem tratados pela PO, sendo, portanto, uma das mais importantes e a primeira das atribuiçõesde quem trabalha com Pesquisa Operacional a delimitação das fronteiras dos sistemas a serem estudados, assegurando a aplicabilidade da PO a ele. Ackoff e Sassieni, também citados por Contador (1998) consideram a PO como a aplicação do método científico, por equipes interdisciplinares, a problemas relativos ao controle de sistemas organizacionais, com a finalidade de obter soluções que satisfaçam aos objetivos da organização como um todo. Esses autores, portanto, evidenciam que a PO tem caráter de conciliadora dos objetivos conflitantes das diversas funções dentro de uma organização. Em resumo, portanto, podemos dizer que a PO busca a solução ótima que atende aos objetivos conflitantes dos diversos setores de uma organização, tendo em mente o objetivo corporativo. Logo, é a utilização de modelos matemáticos e simulações para a correta alocação de recursos, permitindo a condução e a coordenação das operações em uma organização. Assim sendo, este texto pretende apresentar as principais técnicas e ferramentas estudadas em PO, capacitando o Administrador a tomar decisões de maneira mais racional e objetiva, por meio do uso de modelos previamente estudados. Esperamos que, com este material, você tenha a oportunidade de aprender os conceitos básicos de Pesquisa Operacional e torne‑se apto para continuar os estudos nessa área quando necessário for. IntrOduçãO Grande parte da ciência da Administração é dedicada à correta aplicação dos recursos disponíveis. Raramente, para não usarmos a palavra nunca, teremos a quantidade de recursos que sonhamos para um empreendimento qualquer. Eles serão sempre reduzidos, e mais: só poderemos afirmar que somos ou seremos bem‑sucedidos nessa arte se os recursos aplicados se multiplicarem em ganhos de capital que proporcionarem mais recursos para novas empresas. 9 Numa organização qualquer, frequentemente estarão à disposição várias oportunidades de aplicação desses recursos, algumas apresentando mais retorno, outras, menos retorno; algumas mais adequadas às nossas capacidades, outras, menos adequadas; algumas que implicam em mais riscos e outras, em menos riscos. qual das alternativas escolher pode ser um dilema difícil. Você, como administrador, frequentemente terá de decidir entre essas várias opções. Como fazer? Muitas das vezes, decidiremos com base em nossa intuição, experiência, ou, como dizem os americanos, em nosso feeling. Será que isso é suficiente? Possivelmente, não! Mesmo nas vezes em que formos bem‑sucedidos, temos de levar em conta o risco que corremos com esse processo. Ferramentas objetivas, matemáticas, metodológicas não substituirão a intuição, mas poderão ser importantes complementos a ela. A Pesquisa Operacional atua exatamente nesse campo. Ela criou e cria ferramentas, processos e modelos que permitirão tornar nossas decisões o mais lógicas e racionais possíveis. Imagine que você tenha dois produtos diferentes para lançar no mercado. Cada um deles tem um potencial de vendas, um custo de fabricação, uma margem de lucro, a necessidade de publicidade e competências produtivas. Você dispõe de certa quantia em dinheiro para fazer o negócio acontecer, digamos, só para efeito de raciocínio, de R$ 10 milhões. Você aplicaria toda a quantia no produto A ou no produto B? Parte no A e parte no B? quanto no A e quanto no B? Perceba que essas perguntas só têm respostas dentro de um contexto real, no qual você poderia utilizar sua experiência e intuição. Contudo, mesmo nesse contexto, perceba o risco que correrá seja qual for a sua decisão. Não ficaria mais fácil para você se técnicas estudadas, testadas e aplicadas em outros casos dessem pelo menos uma indicação do melhor caminho a seguir? Nesta disciplina, tentaremos aprender justamente algumas dessas ferramentas. Como elas foram desenvolvidas e como podem ser utilizadas. Veremos como elas servem para tomar decisões, para mediar conflitos entre os objetivos particulares de cada função da empresa e os objetivos corporativos, e como aplicar melhor todos os nossos recursos, não só capital, mas também recursos humanos, tecnológicos, materiais ou científicos. Evidentemente, esse material tem como ambição abrir uma porta à sua curiosidade, não explorar totalmente as instalações. Não temos tempo suficiente para isso, mas uma introdução a esse tema pode atiçar sua curiosidade sobre uma área frequentemente relegada a segundo plano pelos administradores, transformando‑se numa oportunidade profissional para você. Veremos o histórico da Pesquisa Operacional e seus conceitos básicos e também uma das mais importantes das ferramentas da PO, a Programação Linear. Vamos então ao trabalho! 11 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Unidade I IntrOduçãO à PEsquIsA OPErAcIOnAl A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de problemas reais. Tendo como foco a tomada de decisões, aplica conceitos e métodos de várias áreas científicas na concepção, planejamento ou operação de sistemas. A Pesquisa Operacional é usada para avaliar linhas de ação alternativas e encontrar as soluções que melhor servem aos objetivos dos indivíduos ou organizações (SOBRAPO, 2010). O objetivo desta primeira unidade é mostrar a gênese e evolução da Pesquisa Operacional na Segunda Guerra Mundial até os dias de hoje, mostrando como essa ciência objetiva introduzir elementos de objetividade e racionalidade nos processos de tomada de decisão, sem descuidar, no entanto, dos elementos subjetivos e de enquadramento organizacional que caracterizam os problemas. Pretende‑se mostrar também como os grandes desenvolvimentos técnicos e metodológicos, a partir da segunda metade do século XX, com o apoio de meios computacionais de crescente capacidade e disseminação, nos permitem trabalhar enormes volumes de dados sobre as atividades, não apenas das empresas, mas também de instituições do setor público dentro e fora da área econômica. Face ao seu caráter multidisciplinar, a Pesquisa Operacional é uma disciplina científica de características horizontais, com suas contribuições estendendo‑se por praticamente todos os domínios da atividade humana, da Engenharia à Medicina, passando pela Economia e a Gestão Empresarial, sendo especialmente importante na Administração, como ferramenta objetiva de decisões. 1 HIstórIcO dA PEsquIsA OPErAcIOnAl O termo pesquisa operacional parece ter surgido no início da década de 1940, coincidindo com a Segunda Guerra Mundial, que geralmente é citada como a responsável pelo surgimento da PO. Alguns autores, como Sobral e Peci consideram a PO como sinônimo da Abordagem quantitativa, umas das abordagens estudadas nas Teorias da Administração. Outros autores, mesmo reconhecendo que a utilização do termo PO é relativamente recente, chegam a colocar o uso de técnicas de pesquisa operacional em tempos muito mais remotos. Parece ser bem documentado o uso dessas técnicas já no século XVI, e alguns autores chegam a citar o famoso incêndio da frota romana em Siracusa, provocada por espelhos solares ajustados por Arquimedes, como um exemplo do uso de pesquisa operacional, mesmo sem esse nome. O certo é que a gênese e o desenvolvimento inicial da PO estão fortemente ligados aos esforços aliados na Segunda Grande Guerra. A necessidade de alocar de forma eficiente os parcos recursos disponíveis 12 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 fez com que os exércitos americano e britânico convocassem elevado número de cientistas para lidar com as complexidades dos problemas táticos e estratégicos envolvidos. Na prática, como afirmam Hillier e Lieberman (2013), lhes foi solicitada a realização de pesquisas sobre operações (militares). Ellenrieder, citado por Contador (1998), comenta esse momento da seguinte forma: Sob o ponto de vista histórico, o nome PO é relativamente novo, de origem militar, sendo usado pelaprimeira vez na Grã‑Bretanha, durante a Segunda Guerra Mundial. No começo desse conflito, os organismos responsáveis pela defesa daquele país utilizaram o concurso de especialistas tais como físicos, biólogos, matemáticos para assessorar e contribuir no estudo e solução de certos problemas que, geralmente, se consideravam de atribuição estritamente militar. Basicamente, as razões disto eram fundadas no fato de existirem armamentos relativamente novos, mas sem o suficiente uso que permitisse medir sua eficiência máxima. Em agosto de 1940, o Chefe do comando Antiaéreo daquele país solicitou a colaboração do professor P.M.S. Blackett da Universidade de Manchester, prêmio Nobel de Física, para estudar a coordenação dos equipamentos de radar com um novo aparelho que indicava a elevação e rumo dos canhões, tendo por objetivo abater aviões nazistas que bombardeavam Londres. Para realizar seu trabalho, Blackett reuniu uma equipe com treino científico, mas não necessariamente especialista em eletrônica. Seu grupo incluía três fisiólogos, dois físico‑matemáticos, um astrofísico, um oficial militar, um topógrafo, um físico geral e dois matemáticos. Essa equipe foi batizada pelos contemporâneos como “o Circo de Blackett”, que, apesar do nome depreciativo, demonstrou ser altamente eficiente na tarefa para a qual foi criada. O sucesso de Blackett e de seu “circo” estimulou a formação de equipes mistas de especialistas nos diversos campos do conhecimento vinculados aos problemas relativos às operações militares, táticas ou estratégicas. Assim foram resolvidos, com sucesso, problemas referentes à detecção de navios e submarinos inimigos por meio do uso de radar em aeroplanos, e a determinação da melhor profundidade para explodir as bombas lançadas dos aviões contra os submarinos, entre outros. As equipes de “analistas operacionais”, como eles foram chamados naquela época, começaram a se expandir na Grã‑Bretanha e logo, no Canadá, na Austrália e nos Estados Unidos. Observação Perceba como a correta administração de recursos exíguos está na origem da Pesquisa Operacional. Épocas de guerra são momentos em que os recursos nunca são os suficientes e os resultados são fundamentais. 13 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Não alcançar resultados significa morte, destruição de seres humanos e propriedades. No fundo, não muito diferentes das falências e fracassos das organizações. A Pesquisa Operacional nasceu e foi vital em muitos aspectos no esforço de guerra, resolvendo problemas de logística, operações, transportes, entre outros, da mesma maneira que a utilizamos hoje nas organizações econômicas. Terminada a guerra, o sucesso da PO nos aspectos bélicos motivou interesse no mundo dos negócios que passava a apresentar crescente complexidade e especialização. A explosão econômica a partir da reconstrução mundial contribui de maneira particularmente importante para a crescente convicção de muitos executivos de que as técnicas de PO aplicavam‑se não só aos aspectos bélicos como também aos de contexto organizacional. Dois fatores, em especial, foram responsáveis pelo rápido crescimento da PO. Em primeiro lugar, o desenvolvimento rápido das técnicas gestadas durante a guerra. O Método Simplex, por exemplo, já havia sido desenvolvido por Dantzig em 1947. No final da década de 1950, já estavam bem desenvolvidas as ferramentas padrão da PO, como programação linear, teoria das filas e teoria do inventário. saiba mais O conhecido filme Gênio Indomável (Good Will Hunting) foi baseado numa lenda urbana tida como parte da vida de Dantzig, um estudante realmente brilhante. É um filme que vale a pena ser visto. O segundo fator importante para a generalização da PO é a extraordinária explosão da tecnologia no terreno das telecomunicações e da cibernética, ocorridas a partir dessa época, mas em especial a partir da década de 1980. Atualmente milhões de pessoas ao redor do mundo dispõem de computadores pessoais do mais diversos tipos (desde desktops até tablets), capazes de realizar milhões de operações matemáticas em segundos, conectadas permanentemente aos seus pares pela internet. O desenvolvimento e o uso da PO provocou um impressionante aumento na eficiência das organizações, resultando em contribuição notável para o aumento da produtividade da economia de diversos países. O quadro que veremos em seguida foi retirado da obra Introdução à pesquisa operacional, dos renomados estudiosos Frederick Hillier e Gerald Lieberman, editada continuamente nos últimos 40 anos, e mostra o impacto financeiro (economia anual) do uso de técnicas da PO em diversas organizações. A essas economias de muitos milhões de dólares adicionam‑se benefícios adicionais não mensuráveis, tão ou mais significativos, tais como melhoria no atendimento aos clientes, maior controle gerencial e outros benefícios intangíveis. 14 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Quadro 1 – Aplicações da PO e resultados obtidos nas organizações Organização Natureza da aplicação Economia anual (US$) Federal Expres Planejamento logístico de despachos Não estimada Continental Airlines Otimizar a realocação de tripulações quando ocorrem desajustes nos horários de voo. 40 milhões Swift & Company Aumentar as vendas e melhorar o desempenho na fabricação 12 milhões Memorial Sloan‑Kettering Cancer Center Procedimentos de tratamentos radioterápicos 459 milhões United Airlines, Programar turnos de trabalho nas centrais de reserva e nos balcões em aeroporto 6 milhões Welch´s Otimizar o uso e a movimentação de matéria‑prima 150 mil Sansung Eletronics Desenvolver métodos de redução de tempo de fabricação e níveis de estoque 200 milhões mais receitas Pacific Lumber Company Gestão de ecossistemas florestais a longo prazo 398 milhões VPL* Procter & Gamble Redesenho do sistema de produção e distribuição 200 milhões Canadian Pacific Reilway Planejamento de rotas para frete rodoviário 100 milhões United Airlines, Realocação de aeronaves quando ocorrem problemas Não estimada U.S. Military Planejamento logístico da operação Tempestade no Deserto Não estimada Air New zealand Alocação da tripulação de voo 6,7 milhões Taco Bell Programar a escala de funcionários nas lojas da rede 13 milhões Waste Management Desenvolvimento de um sistema de gerenciamento de rotas para coleta e eliminação de lixo 100 milhões Bank Hapoalim Group Desenvolvimento de um sistema de apoio à tomada de decisões para analistas de investimentos 31 milhões mais receitas Sears Programação e rotas de veículos para as frotas de entrega e atendimento domiciliar 42 milhões Conoco‑Phillips Avaliação de projetos de exploração petrolífera Não estimada Workers Compensation Gestão de pedidos de benefícios por invalidez e reabilitação de alto risco 4 milhões Westinghouse Avaliar projetos de pesquisa e desenvolvimento Não estimada Merrill Lynch Gestão de riscos de liquidez parra as linhas de crédito rotativo 4 bilhões mais liquidez PSA Peugeot Citroen Orientar o processo de projeto para plantas de montagem de veículos eficientes 130 milhões mais lucros KeyCorp Aumentar a eficiência do serviço dos caixas de banco 20 milhões General Motors Aumentar a eficiência das linhas de produção 90 milhões Deere & Company Controle de estoque por meio das cadeias de suprimentos 1 bilhão menos estoques Time Inc. Gerenciamento dos canais de distribuição para revistas 3,5 milhões mais lucros Bank One corporetion Gestão de linhas de crédito e taxas de juros para cartões de crédito 75 milhões mais lucros Merrill Lynch Análise para estabelecimentos de preços para o fornecimento de serviços financeiros 50 milhões mais receitas AT&T Projeto e operação de call centers 750 milhões mais lucros *VPL: Valor presente líquido Fonte: Hillier e Lieberman (2013, p. 4). 15 Re vi sã o: C ris tin a - Di ag ra m aç ão: M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal 2 ObjEtIvOs E MEtOdOlOgIA dA PEsquIsA OPErAcIOnAl Conforme o próprio nome indica e como ficou claro na leitura do item anterior, estamos tratando de uma pesquisa sobre operações, ou seja, a aplicação na resolução de problemas que envolvam o direcionamento e a coordenação de operações (atividades) nas organizações. A natureza dessas operações é muito diversa. Aplica‑se a PO numa gama extraordinariamente grande de áreas, tais como manufaturas, armazenamento e transporte, planejamento financeiro e de crédito, assistência médica e hospitalar, serviços públicos e muitas outras. Observe também que o termo pesquisa sugere o uso do método cientifico na investigação dos problemas empresariais. Assim, temos um processo que se inicia na observação e formulação do problema, inclusive com a coleta de dados relevantes. A partir daí, monta‑se um modelo científico, tipicamente matemático, que explique e equacione a “alma” do problema. Hipoteticamente, esse modelo construído é uma representação fiel e viável do problema estudado representando suas características fundamentais e apresentando conclusões (as soluções do modelo matemático) válidas para a situação real. Essa hipótese deve ser validada. Essa validação é feita por meio da experimentação prática do modelo, verificando‑se sua adequação e, eventualmente, introduzindo‑se modificações que o tornem mais próximo da realidade e da eficiência desejada. Como a pesquisa operacional trata da gestão prática das organizações, é necessário também que ela forneça conclusões positivas e inteligíveis para o tomador de decisão. Hillier e Lieberman (2013, p. 2) observam que uma característica importante da PO é seu ponto de vista abrangente: [...] a PO adota um ponto de vista organizacional. Dessa forma, tenta solucionar os conflitos de interesses entre as unidades da organização da maneira que seja (encontrada) a melhor solução para a organização como um todo. Isso não implica que o estudo de cada problema deva considerar explicitamente todos os aspectos da organização; ao contrário, os objetivos devem ser consistentes com aqueles de toda a organização. Ackoff e Sasieni (apud CONTADOR, 1998) também procuram ressaltar que a PO tem por finalidade conciliar os objetivos conflitantes das diversas funções da organização e, para tanto, segundo Contador (1998), usam as atitudes dos departamentos de produção, de vendas, de finanças e de pessoal nas fases de planejamento da linha de produtos e de programação para ilustrar esses conflitos. O departamento de produção busca produzir a maior quantidade possível de bens a um custo menor possível. Isso será facilitado se produzir continuamente um mesmo produto. No caso de mais de um produto, o departamento defenderá a produção do volume total em um único momento, com o maior lote possível, economizando nos tempos de preparação e treinamento, alcançando alta eficiência, mas aumentando os estoques. Assim, o departamento de produção prefere uma política de estoques elevados e uma linha de produtos limitada. 16 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 O departamento de vendas também deseja estoques elevados, para que tenha condições de entregar tudo o que o cliente venha a requisitar, mas também busca vender o máximo possível cada cliente e, assim, dedicar‑se a uma linha de produtos extensa, com grande variedade de mix. Perceba que os departamentos de vendas e produção entram em conflito no que se refere à extensão do mix de produtos: o primeiro defendendo uma grande variedade e o departamento de produção insistindo na redução da variedade. O departamento financeiro deseja, continuamente, minimizar o capital necessário para as operações da empresa, e uma das maneiras mais fáceis é reduzir estoques e, consequentemente, o dinheiro empatado. A visão financeira julga também que os estoques devem oscilar proporcionalmente com o volume de vendas. Todavia, se o nível de vendas baixa, o departamento de pessoal e também o de produção não desejam reduzir a produção e demitir colaboradores, pois ações desse tipo desperdiçam o capital que foi utilizado no recrutamento, seleção e treinamento, acarreta despesas com indenizações, prejudica a moral da organização e, em eventual aumento de vendas, obrigam a necessidade de seleção de novos funcionários. O departamento de pessoal deseja, portanto, manter o nível de produção constante, o que, no momento em que as vendas caem, gera estoques. Os departamentos de finanças e pessoal discordam fortemente em relação à política de estocagem. Por conseguinte, como observa Contador (1998): [...] é responsabilidade do dirigente estabelecer a política de estoques que, segundo algum critério válido, melhor satisfaça aos interesses da empresa como um todo, e não aos interesses de qualquer dos departamentos que lhe estejam subordinados. A tarefa de integração exige que todo o sistema seja considerado; isto é a essência do trabalho do dirigente. No que, em muitos casos, pode ser auxiliado pela PO. Observação Perceba, portanto, que essa solução de conflitos conduz a outra característica da PO: a tentativa de se encontrar uma melhor solução, chamada de solução ótima para o modelo que representa o problema considerado. Hillier e Lieberman (2013, p. 2) afirmam: “Dissemos uma melhor solução e não a melhor solução, pois pode haver várias soluções, cada uma delas sendo considerada a melhor”. Essas características mencionadas levam naturalmente a outra. A PO não é tarefa para um único indivíduo, que nunca teria todas as habilidades necessárias. A Pesquisa Operacional exige equipes multifuncionais compostas por indivíduos treinados em Estatística, Administração, Matemática, Teorias Comportamentais, entre outras especialidades. 17 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal 3 MOdElAgEM E FOrMAs dE rEPrEsEntAçãO dE PrOblEMAs Para obter soluções ótimas, a Pesquisa Operacional se vale de modelagens, ou seja, estabelece modelos, normalmente matemáticos que representam a realidade estudada. Modelos são representações da realidade, mas a esta normalmente envolve tal complexidade e quantidade tão grande de variáveis que não é possível – e nem teria utilidade alguma – um modelo que leve em conta toda essa complexidade e número de variáveis. Dessa forma, em Pesquisa Operacional, consideramos um modelo matemático simplificado. Mendes (2013) define um modelo matemático como uma representação ou interpretação simplificada da realidade, ou a interpretação de um fragmento de um sistema, segundo uma estrutura de conceitos mentais ou experimentais. Portanto, um modelo pode ser mais ou menos complexo dependendo da realidade que representa. Contador (1998) afirma que podemos, em geral, construir modelos que são muito mais simples do que a realidade e, ainda assim, conseguir empregá‑los para prever e explicar fenômenos com alto grau de precisão. Ele afirma ainda que o “truque” é achar as variáveis certas e a relação correta entre elas. Ackoff e Sasieni (apud CONTADOR, 1998, p. 4) resumem modelo como sendo uma representação simplificada da realidade devendo satisfazer a duas condições fundamentais: Ser simples de entender, resolver e aplicar. Fornecer uma representação completa e realista do problema real, incorporando apenas os elementos necessários para caracterizar sua essência. Três modelos são normalmente utilizados na maioria das ciências e, portanto, na Pesquisa Operacional: modelos icônicos; modelos analógicos e modelos simbólicos. Nos modelos icônicos, as características relevantes dos objetos reais são representadas como se parecem, mas normalmente com mudança de escala; são, portanto, imagens, daí o termo icônico. Um modelo de um carro de Fórmula 1, em escala 1:30, colocado num túnel de vento, é o exemplo da modelagem à qual nos referimos. Os modelos analógicosusam um conjunto de propriedades para representar outro conjunto de propriedade. O desenho das linhas do metrô ou então o diagrama unifilar de uma instalação hidráulica são exemplos desse tipo de modelo. Os modelos simbólicos usam letras, números e outros símbolos para representar as variáveis e suas relações. Redundam, portanto, em expressões matemáticas, geralmente equações e inequações. A fórmula do movimento de um corpo em queda livre é um exemplo desse modelo 18 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 É fácil de entender que os modelos icônicos são os mais difíceis de serem utilizados, enquanto os modelos simbólicos são os mais fáceis. Frequentemente, os três tipos são empregados em sequência; os dois primeiros, para uma primeira abordagem e consequente construção do último, que é então, utilizado a partir daí como ferramenta rotineira para determinado problema. Na Pesquisa Operacional, procura‑se sempre que possível estabelecer modelos simbólicos, não só porque são mais fáceis de manipular como também porque produzem quase sempre resultados mais exatos que os modelos icônicos e analógicos (CONTADOR, 1998). Um exemplo simples de modelo simbólico poderia ser o seguinte: Sueli faz bonecas artesanais de pano. Cada uma das bonecas custa para ser feita, considerando materiais e mão de obra, R$ 18,00, e ela as vende por R$ 30,00. Além disso, ela tem um custo fixo de R$ 96,00 por mês. qual o modelo matemático que representa o lucro dessa operação? Considerando x o número de bonecas vendidas ao longo de um mês, o modelo matemático seria o seguinte: L = (30 – 18) . x – 96 Perceba que poderíamos responder a questões a partir desse modelo. Vejamos exemplo: Caso Sueli venda 15 bonecas, qual será o lucro mensal dela? L = (30 – 18) . 15 – 96 = 84 quantas bonecas, no mínimo, Sueli deverá vender por mês para não ter prejuízo? Não ter prejuízo significa um lucro maior ou igual a zero; portanto: 0 30 18 96 12 96 12 96 96 12 8≤ −( ) − ∴− ≤ − ∴ ≥ ∴ ≥ ∴ ≥ . x x x x x bonecas Evidentemente, os problemas de Pesquisa Operacional não são tão elementares assim, são dotadas de uma maior complexidade, em especial pela introdução de restrições. Mendes (2013) estabelece as seguintes etapas básicas para um projeto de Pesquisa Operacional: • formulação do problema; • construção do modelo; • obtenção da solução. 19 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal O mesmo autor apresenta um exemplo que deixa mais claro o processo e as dificuldades envolvidas: Considere que você tenha duas filhas em famílias diferentes: Débora Helena e Denise Maria. Se você pudesse, planejaria sair com as duas ao mesmo e a todo tempo. No entanto, isso não é possível, pois não aceitariam sair com você juntas. E sair todo dia também não dá. Você não tem dinheiro (entre outras coisas) para fazer isso. Para garantir a sua felicidade, considerando esses problemas desagradáveis, você precisa decidir quantas vezes ao mês sair com cada uma. Vamos chamar de x1 a quantidade de vezes que você vai sair com a Débora por semana e x2 a quantidade de vezes que você vai sair com a Denise, também por semana. Essas variáveis (x1 e x2) são chamadas variáveis de decisão. São valores que representam o cerne do problema e que podemos escolher (decidir) livremente. Veja que você pode sair quantas vezes quiser com cada uma das suas filhas. Entretanto, existem alguns problemas: Débora é “metida” e gosta de lugares caros. Um passeio com ela custa R$ 180,00. Já Denise, é mais simples, gosta de passeios mais baratos. Sair com ela custa só R$ 100,00. Por último, você tem um limite de gastos: no máximo R$ 800,00 por semana. Como fazer para garantir que não se endivide? Perceba que, se você sai com Débora x1 vezes por semana, gastará 180x1 reais por semana. Com Denise gastará 100x2 reais por semana. Portanto, os seus gastos semanais limitados a R$ 800,00 seguem o seguinte modelo matemático: 180x1 + 100x2 ≤ 800 Essa é a função objetivo, aquilo que você tem que alcançar, balanceando os passeios com uma e com a outra. Perceba que existem inúmeras soluções possíveis para essa inequação, e qualquer uma seria válida se não tivéssemos restrições impostas. lembrete Inequação é uma sentença matemática, com uma ou mais incógnitas, expressas por uma desigualdade, diferenciando‑se de uma equação que representa uma igualdade. Incógnitas de uma inequação ou equação são valores desconhecidos para os quais a sentença é verdadeira. Nesse caso as restrições seriam nos tempos gatos nos passeios. Débora é mais sossegada, um passeio com ela dura apenas 2 horas, já Denise, mais agitada, usa 4 horas do seu precioso tempo, e você só tem 20 horas semanais disponíveis para esses passeios. Essas restrições matematicamente seriam expressas da seguinte forma: 2x1 + 4x2 ≤ 20 20 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Claro está que o número de passeios é um valor maior ou igual a zero, não existe um número de passeios negativo. Portanto, temos mais duas restrições: x1 ≥ 0 e x2 ≥ 0 Sua decisão será a obtenção do valor máximo do número de saídas com ambas as filhas e matematicamente corresponde à resolução do sistema de inequações: 180x1 + 100x2 ≤ 800 2x1 + 4x2 ≤ 20 x1 ≥ 0 e x2 ≥ 0 Evidentemente, essa solução é um pouco mais complexa do que as soluções de um sistema convencional de equações. Na unidade II, veremos como esses sistemas são resolvidos. 4 cAMPOs dE APlIcAçãO dA PO: técnIcAs E MétOdOs A Pesquisa Operacional serve, fundamentalmente, para resolver problemas. Existe um problema quando alguém: • deseja algo (objetivo); • dispões de alternativas para alcançá‑lo, com diferentes probabilidades; • tem dúvidas quanto à linha de ação a escolher. Esses problemas são muito frequentes em administração, seja ela em organizações públicas ou privadas. Dentre as muitas áreas que podem ser citadas, elencamos: • análise de investimentos; • programação da produção; • planejamento estratégico; • controle de projetos; • alocação de recursos; • manutenção de equipamentos; • seleção de equipamentos. 21 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Hillier e Lieberman (2013) mencionam o interessante exemplo de aplicação reproduzido a seguir, envolvendo a conhecida empresa de transporte FedEx. Exemplo de Aplicação da Pesquisa Operacional: A Federal Expres (FedEx) é a maior empresa de transporte expresso do mundo. Todos os dias, ela entrega 6,5 milhões de documentos, pacotes e outros itens nos Estados Unidos e em mais de 220 países e territórios ao redor do mundo. Em alguns casos, pode‑se garantir a entrega dessas remesas até as 10h30 da manhã seguinte. As mudanças envolvidas no fornecimento desse serviço são estarrecedoras. Esses milhões de embarque diários têm que ser classificados um a um e direcionados para o local geral correto (usualmente por via aérea) e, então, devem ser entregues no destino exato (normalmente utilizando‑se veículo motorizado) em um período surpreendentemente curto. Como tudo isso é possível? A pesquisa operacional (PO) é o motor tecnológico que propulsiona a empresa. Desde sua fundação em 1973, a PO ajudou na tomada de suas principais decisões de negócios, inclusive investimento em equipamentos, estrutura de rotas, cronograma, finanças e localização de suas instalações. Após ter literalmente creditada à PO a salvação da empresa durante seus primeiros anos, tornou‑se habitual ter a PO representada nas reuniões de diretoria semanais, e, de fato, vários dos diretores atuais provêm do destacado grupo de PO da FedEx. A FedEx acaba sendo reconhecida como uma empresa de nível mundial. Rotineiramente ela se encontra no topo da lista anual das Empresas Mais Admiradas da Fortune Magazine. Ela também foi a primeira vencedora (em 1991)do prêmio hoje conhecido com INFORMS Prize, que é concedido anualmente para a integração efetiva e repetida da PO na tomada de decisão organizacional de maneira pioneira, variada, inovadora e duradoura. Fonte: Hillier e Lieberman (2013, p. 5). saiba mais Assista ao filme Náufrago (Cast Away), que mostra a complexidade das operações da FedEx e a obcessão por alcançar resultados. A Pesquisa Operacional utiliza muitos modelos diferentes. Podemos citar como principais os seguintes: • programação matemática (linear, não linear, inteira, dinâmica, geométrica e estocástica); • teoria das filas; 22 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 • teoria dos estoques; • simulação; • teoria dos grafos (que inclui PERT e COM); • teoria dos jogos; • teoria da decisão; • amostragem; • regressões; • análise discriminante; • séries temporais. Neste material, nos ateremos ao principal desses modelos, a Programação Linear, que veremos na unidade seguinte. lembrete Programação linear nos remete ao modelo matemático linear, ou seja, a funções de 1º grau. Em Administração, esse modelo é o que se adapta à maior parte dos casos práticos. Muitos casos, mesmo que não sigam rigorosamente o modelo linear, podem ser aproximados para ele sem grandes perdas de precisão. Outros modelos matemáticos, como os exponenciais, quadráticos ou logarítmicos, são mais raros, mas apresentam características de aplicabilidade similar. resumo O termo pesquisa operacional parece ter surgido no início da década de 1940, coincidindo com a Segunda Guerra Mundial, que geralmente é citada como a responsável pelo surgimento da PO. A necessidade de alocar de forma eficiente os parcos recursos disponíveis fez com que os exércitos americano e britânico convocassem elevado número de cientistas para lidar com a complexidade dos problemas táticos e estratégicos envolvidos. Foi o professor PMS Blackett da Universidade de Manchester e seu grupo que estimularam a formação de equipes mistas de especialistas nos diversos campos do conhecimento vinculados aos problemas relativos às operações militares, táticas ou estratégicas. Terminada a guerra, o sucesso da PO nos aspectos bélicos motivou interesse no mundo dos negócios que passava a apresentar crescente complexidade e especialização. 23 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal A explosão econômica a partir da reconstrução mundial contribuiu de maneira particularmente importante na crescente convicção de muitos executivos de que as técnicas de PO aplicavam‑se não só aos aspectos bélicos como também ao contexto organizacional. O desenvolvimento e o uso da PO provocaram um impressionante aumento na eficiência das organizações, resultando em contribuição notável para o aumento da produtividade da economia de diversos países. Hoje, aplica‑se PO numa gama extraordinária de grandes de áreas, tais como, manufaturas, armazenamento e transporte, planejamento financeiro e de crédito, assistência médica e hospitalar, serviços públicos e muitas outras. Portanto, a solução de problemas faz uso da PO, na tentativa de encontrar uma melhor solução, chamada como solução ótima para o modelo que representa o problema considerado. Modelos são representações da realidade, que envolve complexidade e às vezes uma quantidade muito grande de variáveis. Na Pesquisa Operacional, procura‑se, sempre que possível, estabelecer modelos simbólicos, não só porque são mais fáceis de manipular como também porque produzem quase sempre resultados mais exatos que os modelos icônicos e analógicos. Exercícios Questão 1. A Pesquisa Operacional (PO) é uma ciência aplicada voltada para a resolução de problemas reais, tendo como foco : A) a representação de dados. B) a tomada de decisões. C) a gestão de qualidade. D) evitar a avaliação de linhas de ação alternativas. E) as formulações estatísticas. Resposta correta: alternativa B. Análise das alternativas A) Alternativa incorreta. Justificativa: esta ação corretiva não faz parte da Pesquisa Operacional, verifica apenas a conformidade do produto e corresponde a processos de gestão de qualidade e não de tomada de decisão. 24 Unidade I Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 B) Alternativa correta. Justificativa: esta ciência aplica conceitos e métodos de várias áreas científicas na concepção, planejamento ou operação de sistemas, com foco na tomada de decisões. C) Alternativa incorreta. Justificativa: esta ação não faz parte da Pesquisa Operacional e refere‑se às ações corretivas de um processo de qualidade. D) Alternativa incorreta. Justificativa: a Pesquisa Operacional é usada na avaliação de linhas de ação alternativas e não para evitá‑las ou excluí‑las. E) Alternativa incorreta. Justificativa: a utilização de formulações estatísticas é uma forma de representar formalmente uma informação. É possível considerá‑la como uma ferramenta e não propriamente um objetivo ou função da Pesquisa Operacional. Questão 2. Três modelos são normalmente utilizados na maioria das ciências e, portanto, na Pesquisa Operacional: modelos icônicos, modelos analógicos e modelos simbólicos. Identifique a definição correta para modelos analógicos: A) Modelo no qual as características relevantes dos objetos reais são representadas como se parecem, mas normalmente com mudança de escala. B) Modelo no qual se usam letras, números e outros símbolos para representar as variáveis e suas relações. Redundam, portanto, em expressões matemáticas, geralmente equações e inequações. C) Modelo no qual se usa um conjunto de propriedades para representar outro conjunto de propriedade. O desenho das linhas do metrô ou então o diagrama unifilar de uma instalação hidráulica são exemplos desse tipo de modelo. D) Modelo que redunda em expressões matemáticas: a fórmula do movimento de um corpo em queda livre é um exemplo desse modelo. E) Modelo que se apresenta como uma sentença matemática, com uma ou mais incógnitas, expressas por uma desigualdade, diferenciando‑se de uma equação que representa uma igualdade. Incógnitas de uma inequação ou equação são valores desconhecidos para os quais a sentença é verdadeira. Resolução desta questão na plataforma. 25 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Unidade II Programação Linear A Programação Linear (PL) é, segundo Contador (1998), um dos mais nobres modelos da Pesquisa Operacional. Dos modelos da Pesquisa Operacional aos problemas organizacionais, a Programação Matemática é responsável por cerca de 60%. Desse percentual, grande parte deve‑se à PL. O objetivo desta unidade, portanto, é apresentar a PL, de maneira prática e utilitária, evitando conceituações matemáticas mais elaboradas. Contador (1998) estima que um curso de PL medianamente avançado cumpre um total de 45 horas efetivas de aula, ou seja, um semestre de três horas‑aulas semanais, o que não nos é disponibilizado, motivo pelo qual não nos aprofundaremos nas considerações matemáticas mais complexas. 5 modeLagem do ProbLema Para apresentar os conceitos da Programação Linear, utilizaremos um exercício adaptado, apresentado originalmente pelo professor Contador (1998), a partir dos trabalhos do professor Zaccarelli, cujo enunciado é o seguinte: Uma fábrica produz CPUs de dois tamanhos diferentes, grandes e pequenas, que apresentam lucros unitários de respectivamente $500 e $200. Ela deseja saber quantas unidades de cada um desses aparelhos deverá fazer para que o lucro obtido pela operação seja máximo. As capacidades de produção da fábrica são as seguintes: • 6 gabinetes grandes por hora; • 15 gabinetes pequenos por hora; • 24 placas‑mãe por hora; • 20 placas de vídeo por hora; Cada CPU grande é composta por: • 1 gabinete grande; • 3 placas‑mãe; • 2 placas devídeo; 26 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Cada CPU pequena é composta por: • 1 gabinete pequeno; • 1 placa‑mãe; • 1 placa de vídeo; Podemos resumir esses dados na seguinte tabela: Tabela 1 Componentes Cpu grande Cpu pequena produção horária Gabinete grande 1 6 Gabinete pequeno 1 15 Placa‑mãe 3 1 24 Placa de vídeo 2 1 20 Modelar o problema significa definir: • as variáveis de entrada; • a Função Objetivo; • as restrições, para, a partir delas, montar um sistema de equações e inequações. No nosso caso temos: Variáveis de entrada = o número de CPUs a serem produzidas, ou seja: x1 = número de CPUs grandes a serem montadas. x2 = número de CPUs pequenas a serem produzidas. O objetivo é maximizar o lucro, portanto a Função Objetivo é: FO = lucro = 500x1 + 200x2 As restrições são relativas à capacidade produtiva de cada componente: gabinete grande: x1 ≤ 6 gabinete pequeno: x2 ≤ 15 placas‑mãe: 3x1 + x2 ≤ 24 placas de vídeo: 2x1 + x2 ≤ 20 27 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Evidentemente, o modelo de PL impõe outra restrição lógica, pois não se pode produzir uma quantidade negativa de CPUs; portanto: x1 ≥ 0 e x2 ≥ 0 Os valores de x1 e x2 que maximizam o lucro dessa operação serão obtidos pela resolução desse sistema de equações e inequações, ou seja, os valores que atendem simultaneamente a todas elas. Existem alguns métodos de solução: • Método Gráfico, aplicável a problemas com duas variáveis de entrada; • Método Simplex, método geral, aplicável a problemas com qualquer quantidade de variáveis de entrada; • Método Computacional, aplicável a um tipo específico de problema, mas com qualquer quantidade de variáveis de entrada. 6 TiPos de soLução 6.1 solução gráfica A solução gráfica consiste em plotar todas as restrições em um único diagrama ortogonal no qual o eixo horizontal representará as quantidades produzidas de CPUs grandes e o eixo vertical, as quantidades produzidas de CPUs pequenas: x2 = CPUs pequenas x1 = CPUs grandes121086420 10 5 15 20 25 Figura 1 28 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Lembrete Sistema de Coordenadas no plano cartesiano ou espaço cartesiano é um esquema reticulado necessário para especificar pontos num determinado “espaço” com dimensões. Cartesiano é um adjetivo que se refere ao matemático francês e filósofo Descartes que, entre outras coisas, desenvolveu uma síntese da álgebra com a geometria euclidiana. O plano cartesiano contém dois eixos perpendiculares entre si. A localização de um ponto P no plano cartesiano é feita pelas coordenadas do plano (abscissa e ordenada – x e y). Nos quadrantes I e III, os sinas de x, y são os mesmos (+,+) e (‑,‑), respectivamente, já nos quadrantes II e IV, os sinas de x, y são opostos (‑,+) e (+,‑), respectivamente. Observe que utilizaremos o primeiro quadrante do sistema cartesiano, ou seja, valores de ambos os eixos positivos. Isso porque não teria sentido a produção de uma quantidade negativa de CPUs. Assim, teoricamente, qualquer ponto nesse diagrama ortogonal seria solução para o nosso problema. No entanto, veremos que, devido às restrições, pouco a pouco reduziremos os resultados possíveis. A primeira restrição é a dos gabinetes grandes: não é possível a produção de mais do que seis gabinetes por hora nem a produção de uma quantidade negativa de gabinetes, ou seja: 0 ≤ x1 ≤ 6 Graficamente, teríamos: 29 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal x2 = CPUs pequenas gabinete grande: x1 > 0 e x1 < 6 x1 = CPUs grandes121086420 10 5 15 20 25 Figura 2 Perceba que só podem ser aceitos como soluções para esse problema os pontos coordenados à esquerda da reta desenhada. Restrição semelhante ocorre com os gabinetes pequenos: 0 ≤ x2 ≤ 15 x2 = CPUs pequenas gabinete grande: x1 > 0 e x1 < 6 gabinete pequeno: x2 > 0 e x2 < 15 x1 = CPUs grandes121086420 10 5 15 20 25 Figura 3 Perceba que só podem ser aceitos como soluções para esse problema os pontos coordenados abaixo da reta desenhada. 30 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Até esse momento, as restrições já reduziram as soluções possíveis aos pontos coordenados circunscritos pelos eixos e pelas duas retas desenhadas. Em sequência, temos as restrições da quantidade de placas‑mãe produzidas, ou seja: 3x1 + x2 ≤ 24 Observe que, se x1 for igual a zero, x2 deverá ser menor ou igual a 24 para manter a inequação e, se x2 for igual a zero, x1 deverá ser menor ou igual a 8. Note as resoluções a seguir: Em 3x1 + x2 ≤ 24, se x1 = 0, tem‑se 3 × 0 + x2 ≤ 24 → x2 ≤ 24 Em 3 24 0 3 0 24 24 3 81 2 2 1 1 1x x se x tem se x x x+ ≤ = − + ≤ → ≤ → ≤, , Portanto, a inequação tem dois pontos característicos pelos quais podemos traçar a reta que a caracteriza: (0; 24) e (8; 0). Graficamente temos: x2 = CPUs pequenas gabinete grande: x1 > 0 e x1 < 6 gabinete pequeno: x2 > 0 e x2 < 15 3x1 + x2 < 24 x1 = CPUs grandes121086420 10 5 15 20 25 Figura 4 Perceba que qualquer ponto coordenado à direita desta reta não é permitido, pois desobedeceria a inequação. Retiramos mais um “pedaço” do campo de soluções permitidas. A última restrição é a da placa de vídeo. Seguindo o mesmo raciocínio das placas‑mãe, determinamos a reta característica: 2x1 + x2 ≤ 20; se x1 = 0 → 2 × 0 + x2 ≤ 20→x2 → ≤ 20 2 20 0 2 0 20 20 2 101 2 2 1 2 2x x se x x x x+ ≤ = → + ≤ → ≤ → ≤; 31 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Os pontos característicos que definem a reta são (0;20) e (10;8), e graficamente: x2 = CPUs pequenas gabinete grande: x1 > 0 e x1 < 6 gabinete pequeno: x2 > 0 e x2 < 15 2x1 + x2 < 20 3x1 + x2 < 24 x1 = CPUs grandes121086420 10 5 15 20 25 Figura 5 Mais uma parte das soluções possíveis foi retirada, restando um polígono de soluções possíveis. Veja a seguir: x2 = CPUs pequenas gabinete grande: x1 > 0 e x1 < 6 gabinete pequeno: x2 > 0 e x2 < 15 2x1 + x2 < 20 3x1 + x2 < 24 x1 = CPUs grandes121086420 10 5 15 20 25 A B C D E Figura 6 Qualquer ponto desta área sombreada (em amarelo) é solução para o problema, continuando a existir, portanto, infinitas soluções, mas somente uma delas apresenta lucro máximo. É fácil entender qual é a solução ótima. Em cada lado do polígono, há um recurso que é utilizado ao máximo. Como num vértice há dois recursos utilizados ao máximo simultaneamente, a solução ótima estará num dos vértices do polígono. Este é o teorema fundamental da Programação Linear. 32 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Para ficar mais claro: no lado (aresta) definido pelos pontos BC, estamos produzindo o máximo possível de gabinetes. Já no ponto C, além de estarmos produzindo o máximo de gabinetes possíveis, estamos também produzindo o máximo possível de placas de vídeo. Antes tínhamos infinitas soluções possíveis, mas com esse teorema restaram apenas seis soluções que podem ser ótimas e, por tentativas, podemos definir qual é essa solução ótima. Veja a tabela a seguir: Tabela 2 VÉRTICE Cpu GRANDE Cpu pEQuENA LuCRO x1 x2 500x1+200x2 A 0 0 0 + 0 = 0 B 0 15 0 + 3.000 = 3.000 C 2,5 15 1.250 + 3.000 = 4.250 D 4 12 200 + 2.400 = 4.400 E 5 6 3.000 + 1.200 = 4.200 F 5 0 3.000 + 0 = 3.000 Portanto, o ponto de máximo lucro é o ponto D. Consequentemente, deve‑se montar quatro CPUs grandes por hora e doze pequenas por hora, o que gerará um lucro de $ 4.400,00 por hora. Para se atingir esse lucro máximo, serão produzidos: • 4 gabinetes grandes por hora; • 12 gabinetes pequenos por hora; • 24 placas‑mãe por hora; • 20 placas de vídeo porhora. observação Sobrarão, por hora, dois gabinetes grandes e três pequenos. Não haverá sobras de placas‑mãe e placas de vídeo. 6.2 solução pelo algoritmo simplex Perceba que esse processo gráfico tem muitas limitações, a começar pelo fato de que só pode ser usado para duas variáveis de entrada. Foi necessário o desenvolvimento de um método mais completo para realizar esses cálculos, que é conhecido como Simplex. 33 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal O Método Simplex, ao contrário do Método Gráfico, trabalha com equações, e não com inequações. Desse modo, as inequações devem ser transformadas em equações, e isso é feito com a adição de variáveis. Vamos, portanto, determinar as variáveis que podem aparecer em um problema desse tipo. Utilizaremos as definições estabelecidas por Contador (1998): • Variável de entrada é a aquela que deve ser otimizada e surge naturalmente do enunciado do problema. No caso do exercício das CPUs, que continuaremos usar como exemplo, as variáveis de entrada são o número de CPUs grandes (x1) e o número de CPUs pequenas (x2). • Termo independente é o valor numérico de uma restrição e, por convenção, é colocado à direita do sinal da inequação. No nosso exemplo, são as quantidade limitantes produzidas para cada componente. • Variável de folga ou residual, utilizada quando a desigualdade for do tipo ≤, é uma variável não negativa, somado ao lado esquerdo da desigualdade, e numericamente igual à diferença entre o termo independente e os valores à esquerda da desigualdade. Corresponde, numa determinada solução, à parcela não aproveitada de recursos. No nosso exemplo, são as eventuais sobras de componentes (gabinetes ou placas) • Variável de excesso, utilizada quando a desigualdade for do tipo ≥, é uma variável negativa, subtraída do lado esquerdo da desigualdade e numericamente igual à diferença entre o valor do termo independente e o valor das variáveis que estão à esquerda da desigualdade. No nosso exemplo, não existirão valores desse tipo, pois é um problema de maximização. • Variável artificial é uma variável adicionada à esquerda em todas as restrições que não contenham uma variável de folga, sendo utilizada, portanto, nas restrições que se apresentam originalmente com sinal ≥ ou =. A variável artificial é necessária porque a solução inicial do Simplex é obtida igualando a zero todas as variáveis de entrada e todas as de excesso, o que corresponde a fazer cada variável de folga e cada variável artificial igual ao valor do termo independente da equação da qual a variável em questão aparece. No nosso exemplo, não existem variáveis desse tipo, visto serem inequações do tipo ≤. Dessa forma, no nosso exemplo, as inequações seriam transformadas em equações, da seguinte forma: Inequações: gabinete grande: x1 ≤ 6 gabinete pequeno: x2 ≤ 15 placas‑mãe: 3x1 + x2 ≤ 24 placas de vídeo: 2x1 + x2 ≤ 20 34 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Equações: gabinete grande: 1x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 = 6 gabinete pequeno: 0x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15 placas‑mãe: 3x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 = 24 placas de video: 2x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 = 20 Importante notar que na frente de cada variável colocamos seu coeficiente correspondente, mesmo quando não há necessidade, por ser zero ou um. Fizemos isso, para evidenciar os coeficientes que serão utilizados no algoritmo Simplex. Esse equacionamento tem seis valores desconhecido (as incógnitas x1; x2; x3; x4; x5; x6) e apenas quatro equações (as relacionadas anteriormente). Logo, o sistema de equações é indeterminado, tem infinitas soluções viáveis, e não apenas uma. Lembre‑se de que, em Matemática, só conseguimos resolver um sistema de equações quando o número delas for igual ao número de incógnitas. Nesse caso, portanto, temos infinitas soluções viáveis (as soluções mostradas na área hachurada do gráfico mostrado anteriormente). A solução ótima será pesquisada atribuindo valores arbitrários a um número de incógnitas igual ao número total delas subtraído pelo número de equações. No nosso exemplo, atribuiremos valores arbitrários a duas incógnitas (resultado da subtração de seis incógnitas por duas equações). Essa resolução exige conhecimentos matemáticos que de modo geral não são do domínio de alunos da graduação de Administração; por conseguinte, iremos apresentá‑la de forma descritiva, utilizando o problema das CPUs como ilustração e apresentando o método passo a passo. 1º passo: estabelecer a planilha do algoritmo Lembrete Um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas; cada uma delas pode ser executada mecanicamente num período de tempo finito e com uma quantidade de esforço finita. O conceito de algoritmo é frequentemente ilustrado pelo exemplo de uma receita culinária, embora muitos algoritmos sejam mais complexos. Eles podem repetir passos (fazer iterações) ou necessitar de decisões (tais como comparações ou lógica) até que a tarefa seja completada. Um algoritmo corretamente executado não resolverá um problema se estiver implementado incorretamente ou se não for apropriado ao problema. 35 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal É uma planilha de diversas linhas e colunas, na qual é reservada uma coluna para cada variável e mais quatro colunas de cálculos. Acompanhe a planilha para o nosso exemplo e o significado de cada coluna: Tabela 3 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b A coluna base contém as variáveis que estão sendo consideradas numa determinada tentativa. No nosso caso, teremos quatro variáveis em cada tentativa. Para as outras duas será atribuído o valor zero. As seis colunas seguintes são reservadas para cada uma das variáveis envolvidas. No nosso caso as duas variáveis de entrada (x1 e x2) e as quatro variáveis residuais (x3, x4, x5 e x6). A antepenúltima coluna é reservada para os termos independentes das equações (no nosso exercício as restrições de produção). A penúltima coluna é destinada a receber uma divisão entre as variáveis independentes, e a coluna de trabalho (veremos essa coluna mais adiante, durante a descrição do processo). A última coluna relacionará a variável que entrará e a que sairá na próxima tentativa. Existe um conjunto de linhas reservadas para cada tentativa: uma linha para cada equação e uma linha de controle (no caso, denominada lucro, nosso objetivo). Tabela 4 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 Gabinete pequeno x4 Placa‑mãe x5 Placa de vídeo x6 Controle/lucro 36 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 A planilha mostrada anteriormente está preparada para se atribuir o valor zero para as variáveis x1 e x2. É nossa primeira tentativa. Ao igualar as variáveis de entrada a zero, automaticamente igualamos as variáveis residuais ou de folga ao termo independente. Veja como exemplo a primeira equação: Em x1 + x3 = 6, se x1 = 0, então x3 = 6 O mesmo ocorre nas demais equações e variáveis. 2ª passo: início do preenchimento da planilha Colocamos em cada uma das linhas os coeficientes das equações citadas anteriormente. A tabela fica da seguinte forma: Tabela 5 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pelacoluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 1 0 0 15 Placa‑mãe x5 3 1 0 0 1 0 24 Placa de vídeo x6 2 1 0 0 0 1 20 Controle/lucro Na linha de controle, colocamos o lucro respectivo com sinal trocado, ou seja ‑500 para CPU grande, – 200 para CPU pequena e zero para as demais colunas: 37 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Tabela 6 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 1 0 0 15 Placa‑mãe x5 3 1 0 0 1 0 24 Placa de vídeo x6 2 1 0 0 0 1 20 Controle/lucro –500 –200 0 0 0 0 0 Como dissemos, nessa primeira tentativa atribuímos valor zero às variáveis x1 e x2. Na segunda tentativa, entraremos na tabela com uma delas e sair com uma das que fizeram parte na primeira tentativa (x3, x4, x5 e x6). Isso é feito da seguinte maneira: • localizar a coluna que apresentar o maior valor negativo na linha de controle, no nosso caso a coluna x1, que apresenta o valor ‑500. Essa coluna passa a ser denominada coluna de trabalho (ela irá variar de tentativa para tentativa). Costuma‑se assinalar a coluna por um retângulo. Essa variável é a que entrará na próxima tentativa. Colocamos essa informação na última coluna; • dividir o termo independente pelo valor correspondente na coluna de trabalho. Na linha de gabinete grande, por exemplo, dividiremos 6 por 1, obtendo o valor 6 que será colocado na penúltima coluna; • a variável que sairá na tentativa seguinte é aquela que corresponder à linha que apresentar menor valor positivo na coluna de termo independente; no exemplo, o valor 6 correspondente à variável x3; • O coeficiente que estiver no cruzamento da linha que sairá com a coluna de trabalho chama‑se pivô ou elemento pivotal e vai nos servir para os cálculos seguintes. Veja como deve ficar a planilha: 38 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Tabela 7 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 1 0 0 15 Placa‑mãe x5 3 1 0 0 1 0 24 Placa de vídeo x6 2 1 0 0 0 1 20 Controle/lucro –500 –200 0 0 0 0 0 Coluna de trabalho pivô 3º passo: determinação da tentativa seguinte Para a segunda tentativa, substituiremos a linha x3 na base, dando lugar à linha x1 que deve entrar. Todas as outras linhas, inclusive a de controle, devem permanecer com a base inalterada. Os valores da linha que entra são obtidos pela divisão dos valores da linha que sai pelo valor do pivô. Nesse caso, como o valor do pivô é 1, os valores permanecerão os mesmos. Tabela 8 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 39 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 Gabinete pequeno x4 Placa‑mãe x5 Placa de vídeo x6 Controle/lucro Os valores das demais linhas, inclusive do termo independente, é obtido pela chamada regra do retângulo. Antes de aprendermos a usar a regra do retângulo, notemos que nas colunas que também são linhas (no nosso exemplo, no momento, as colunas x1, x4, x5 e x6) aparecerão apenas números zero ou um. Quando uma coluna cruza com uma linha correspondente à mesma variável, o valor será um. Veja a seguir: Tabela 9 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 1 0 0 15 Placa‑mãe x5 3 1 0 0 1 0 24 Placa de vídeo x6 2 1 0 0 0 1 20 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 Gabinete pequeno x4 1 Placa‑mãe x5 1 Placa de vídeo x6 1 Controle/lucro 40 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 E, quando uma coluna cruza com uma linha correspondente a outra variável, o valor será zero. Veja novamente: Tabela 10 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 1 0 0 15 Placa‑mãe x5 3 1 0 0 1 0 24 Placa de vídeo x6 2 1 0 0 0 1 20 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 0 Placa‑mãe x5 0 0 1 0 Placa de vídeo x6 0 0 0 1 Controle/lucro 0 0 0 0 Apenas os valores das colunas referentes às variáveis que estão assumindo valor zero (que estão “fora”) e da coluna do termo independente é que deverão ser calculados pela regra do retângulo. Para entendermos a regra do retângulo, utilizaremos o quadro a seguir, com as linhas e colunas numeradas à semelhança do Excel: 41 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Tabela 11 A B C D E F G H I J K 1 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir 2 Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo 3 x1 x2 x3 x4 x5 x6 b 4 5 Gabinete grande x3 1 0 1 0 0 0 6 6 Gabinete pequeno x4 0 1 0 1 0 0 15 7 Placa‑mãe x5 3 1 0 0 1 0 24 8 Placa de vídeo x6 2 1 0 0 0 1 20 9 Controle/lucro –500 –200 0 0 0 0 0 10 11 CPU grande x1 1 0 1 0 0 0 6 12 Gabinete pequeno x4 0 1 0 0 13 Placa‑mãe x5 0 0 1 0 14 Placa de vídeo x6 0 0 0 1 15 Controle/lucro 0 0 0 0 Queremos calcular o valor da célula D12. Para isso, usaremos o retângulo definido pelo pivô (célula C5) e pelo valor correspondente anterior (célula D6). O valor pedido será obtido pela formulação: Novo valor = Valor anterior – (produtos dos elementos da diagonal oposta) ÷ pivô No nosso exemplo, seria: D12 = D6 – (C6 × D5) ÷ C5, ou seja, 1 – (0 × 0) ÷ 1 = 1 Para fixar esse conceito, façamos agora o cálculo do termo independente correspondente à placa‑mãe. Veja a tabela a seguir: 42 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Tabela 12 A B C D E F G H I J K 1 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir 2 Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo 3 x1 x2 x3 x4 x5 x6 b 4 5 Gabinete grande x3 1 0 1 0 0 0 6 6 Gabinete pequeno x4 0 1 0 1 0 0 15 7 Placa‑mãe x5 3 1 0 0 1 0 24 8 Placa de vídeo x6 2 1 0 0 0 1 20 9 Controle/lucro –500 –200 0 0 0 0 0 10 11 CPUgrande x1 1 0 1 0 0 0 6 12 Gabinete pequeno x4 0 1 1 0 0 13 Placa‑mãe x5 0 0 1 0 14 Placa de vídeo x6 0 0 0 1 15 Controle/lucro 0 0 0 0 Observe, em amarelo, o retângulo definido, valor correspondente ao desejado na base anterior e o pivô. O cálculo é feito utilizando‑se a formulação vista, ou seja: I13 = I7 – (C7 × I5) ÷ C5, ou seja, 24 – (3 × 6) ÷ 1 = 6 Os demais valores são calculados de modo idêntico, ficando a planilha do seguinte modo: 43 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Tabela 13 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 Gabinete pequeno x4 0 1 0 1 0 0 15 Placa‑mãe x5 0 1 –3 0 1 0 6 Placa de vídeo x6 0 1 –2 0 0 1 8 Controle/lucro 0 –200 500 0 0 0 3.000 Repetimos então os cálculos feitos na tentativa anterior, passo a passo. O resultado será: Tabela 14 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 44 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 CPU grande x1 1 0 1 0 0 0 6 ∞ Entra Gabinete pequeno x4 0 1 0 1 0 0 15 15 x2 Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai Placa de vídeo x6 0 1 –2 0 0 1 8 8 x3 Controle/lucro 0 –200 500 0 0 0 3.000 Podemos partir então para a terceira tentativa, substituindo primeiro a linha de x5 por x2: Tabela 15 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 ∞ Entra Gabinete pequeno x4 0 1 0 1 0 0 15 15 x2 Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai Placa de vídeo x6 0 1 –2 0 0 1 8 8 x5 Controle/lucro 0 –200 500 0 0 0 3.000 CPU grande x1 Gabinete pequeno x4 CPU pequena x2 0 1 –3 0 1 0 6 Placa de vídeo x6 Controle/lucro 45 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Em seguida, preenchemos os valores das colunas que não estão zeradas na tentativa: Tabela 16 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 ∞ Entra Gabinete pequeno x4 0 1 0 1 0 0 15 15 x2 Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai Placa de vídeo x6 0 1 –2 0 0 1 8 8 x5 Controle/lucro 0 –200 500 0 0 0 3.000 CPU grande x1 1 0 0 0 Gabinete pequeno x4 0 0 1 0 CPU pequena x2 0 1 –3 0 1 0 6 Placa de vídeo x6 0 0 0 1 Controle/lucro 0 0 0 0 46 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Calculemos, então, pela regra do retângulo, os valores correspondentes às três colunas restantes: Tabela 17 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 ∞ Entra Gabinete pequeno x4 0 1 0 1 0 0 15 15 x2 Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai Placa de vídeo x6 0 1 –2 0 0 1 8 8 x5 Controle/lucro 0 –200 500 0 0 0 3.000 CPU grande x1 1 0 1 0 0 0 6 Gabinete pequeno x4 0 0 3 1 –1 0 9 CPU pequena x2 0 1 –3 0 1 0 6 Placa de vídeo x6 0 0 1 0 –1 1 2 Controle/lucro 0 0 –100 0 200 0 4.200 47 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Por fim, calculemos quem entra e quem sai para a próxima tentativa: Tabela 18 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 ∞ Entra Gabinete pequeno x4 0 1 0 1 0 0 15 15 x2 Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai Placa de vídeo x6 0 1 –2 0 0 1 8 8 x5 Controle/lucro 0 –200 500 0 0 0 3.000 CPU grande x1 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 0 3 1 –1 0 9 3 x2 CPU pequena x2 0 1 –3 0 1 0 6 –2 Sai Placa de vídeo x6 0 0 1 0 –1 1 2 2 x6 Controle/lucro 0 0 –100 0 200 0 4.200 48 Unidade II Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Essas tentativas serão repetidas sucessivamente e tantas vezes quantas necessárias até que, na linha de controle, todos os números sejam positivos ou nulos. No nosso exemplo, só será necessária mais uma tentativa: Tabela 19 Base Variável de entrada Variável residual Termo indepen- dente Termo independente dividido pela coluna de trabalho Variável a incluir ou a excluir Cpu grande Cpu pequena Gabinete grande Gabinete pequeno placa-mãe placa de vídeo x1 x2 x3 x4 x5 x6 b Gabinete grande x3 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 1 0 1 0 0 15 ∞ x1 Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai Placa de vídeo x6 2 1 0 0 0 1 20 10 x3 Controle/lucro –500 –200 0 0 0 0 0 CPU grande x1 1 0 1 0 0 0 6 ∞ Entra Gabinete pequeno x4 0 1 0 1 0 0 15 15 x2 Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai Placa de vídeo x6 0 1 –2 0 0 1 8 8 x5 Controle/lucro 0 –200 500 0 0 0 3.000 CPU grande x1 1 0 1 0 0 0 6 6 Entra Gabinete pequeno x4 0 0 3 1 –1 0 9 3 x3 CPU pequena x2 0 1 –3 0 1 0 6 –2 Sai Placa de vídeo x6 0 0 1 0 –1 1 2 2 x6 Controle/lucro 0 0 –100 0 200 0 4.200 CPU grande x1 1 0 0 0 1 –1 4 Gabinete pequeno x4 0 0 0 1 2 –3 3 CPU pequena x2 0 1 0 0 –2 3 12 Gabinete grande x3 0 0 1 0 –1 1 2 Controle/lucro 0 0 0 0 100 100 4.400 49 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Observe a última coluna da última tentativa. Ela nos oferece a alternativa ótima para esse problema de programação linear: Tabela 20 Variável Item Qtd. Programa de produção: x1 CPUs grandes. 4 x2 CPUs pequenas. 12 Sobras (recursos residuais) x3 Gabinetes grandes 2 x4 Gabinetes pequenos 3 x5 Placas‑mãe 0 x6 Placas de vídeo 0 6.3 solução computacional – utilizando ferramenta solver