SUMÁRIO

ORIGEM DA PESQUISA OPERACIONAL 01I MODELAGEM MATEMÁTICA 04

1.1- Introdução .................................................................................................................. 041.2- Metodologia da PO ................................................................................................... 061.3- O Modelo de Programação Linear............................................................................. 071.4- Exemplos de Formulação de Modelos....................................................................... 101.5- Problemas Propostos ................................................................................................. 171.6- Solução Gráfica ......................................................................................................... 19

II FUNDAMENTOS MATEMÁTICOS 292.1- Matriz ......................................................................................................................... 292.2- Sistema de Equações Lineares ................................................................................... 302.3- Vetores no Plano e no Espaço ................................................................................... 322.4- Combinação Linear .................................................................................................... 332.5- Independência Linear ................................................................................................ 332.6- Solução Básica Viável ............................................................................................... 332.7- Combinação Convexa ................................................................................................ 342.8- Conjunto Convexo ..................................................................................................... 34

III MÉTODO SIMPLEX 353.1- Introdução .................................................................................................................. 353.2- Teoremas Fundamentais do Método Simplex ........................................................... 353.3- Redução de Um Problema de Programação Linear à Forma Padrão ........................ 363.4- Forma Canônica de Um Sistema ............................................................................... 383.5- Conceitos Básicos do Método Simplex ..................................................................... 393.6- Desenvolvimento do Método Simplex ...................................................................... 473.7- Procedimento do Método Simplex ............................................................................ 503.8- Análise das Soluções ................................................................................................. 503.9- Análise Econômica .................................................................................................... 513.10- Método do M Grande............................................................................................... 573.11- Método das Duas Fases ........................................................................................... 58

IV DUALIDADE 604.1- Introdução .................................................................................................................. 604.2- Estudo da Dualidade .................................................................................................. 604.3- Relações Entre Primal e Dual .................................................................................... 664.4- Resumo Para Transformação Primal-Dual ................................................................ 66

V ANÁLISE DE SENSIBILIDADE 675.1- Introdução .................................................................................................................. 675.2- Variações nos Coeficientes da FO ............................................................................. 685.3- Variações nas Quantidades dos Recursos................................................................... 705.4- Acréscimo de Variável .............................................................................................. 725.5- Acréscimo de Restrição.............................................................................................. 75

VI PROBLEMAS DE TRANSPORTES 796.1- Introdução................................................................................................................... 796.2- Modelagem do Problema de Transportes .................................................................. 796.3- Algoritmo do Problema de Transporte ...................................................................... 81 6.3.1- Obtenção da Solução Básica Inicial ................................................................ 82 6.3.2- Algoritmo da “Stepping-Stone”....................................................................... 87 6.3.3- Cálculo da Solução Ótima Através do Problema Dual.................................... 89

VII PROGRAMAÇÃO INTEIRA 927.1- Introdução 92

1

7.2- Algoritmo de Bifurcação e Limite 92 7.2.1- Limite 94 7.2.2- Considerações 94 7.2.3- Diagrama Esquemático 94ANEXO 1- ESTUDO DE CASO: COMPOSIÇÃO DE FERTILIZANTES 95ANEXO 2- RESOLUÇÃO POR COMPUTADOR 103

2

ORIGEM E APLICAÇÕES DA PESQUISA OPERACIONAL

A Pesquisa Operacional (PO) é uma ciência aplicada, formada por um conjunto de

técnicas que visa a determinação das melhores condições de aproveitamento dos recursos em uma situação na qual estejam sob restrições, como a econômica, a material, a humana e a temporal.

Sob o ponto de vista histórico, seu nome é relativamente novo, de origem militar, sendo usado pela primeira 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ções estritamente militar.

Basicamente, as razões disto eram fundadas nos fatos da existência de armamentos relativamente novos, mas sem o suficiente uso que permitisse medir a eficiência máxima dos mesmos e na necessidade urgente de alocar recursos escassos às várias operações militares e às atividades dentro de cada operação, de modo eficaz.

Aplicando uma abordagem científica no tratamento de problemas estratégicos e táticos, foram resolvidos, com sucesso, problemas como a determinação do número mínimo de aviões ingleses a serem mantidos em condições de fazer frente aos ataques alemães, a distribuição e localização dos meios de defesa antiaérea ao longo da ilha, a determinação da melhor profundidade para explodir as bombas lançadas dos aviões contra os submarinos inimigos, entre outros.

Os cientistas chamados para fazer pesquisa em operações militares (daí o nome Pesquisa Operacional), após a guerra desenvolveram diversas outras aplicações. Depois de 1950, a PO invadiu a área industrial e encontrou seu aliado natural: o Computador. Depois do computador, a PO se expandiu de uma maneira extraordinária e problemas cada vez mais complexos e com grande número de variáveis e equações puderam ser solucionados.

Na década de sessenta tinha a mesma divulgação e fascínio também obtidos por outras técnicas, tal como a Gestão pela qualidade Total os tem obtido nas décadas de oitenta e noventa. Hoje, o campo de atuação da PO é bastante amplo, se estendendo desde o setor industrial, na produção de matérias-primas e bens de consumo, até o setor de serviços e às aplicações de interesse social como as relacionadas à saúde e à educação.

Existem diversas áreas em que a PO vem sendo aplicada com sucesso para racionalizar recursos, reduzir custos e aumentar lucros. Dentre elas temos:

Dosagem (ou Mistura)o Alimentaçãoo Formulação de Raçõeso Fábrica de Aduboso Ligas Metálicaso Petróleoo Minérios, etc.

Transporteo Tamanho da Frota

3

Investimentos Financeiroso Análise de Riscos de Créditoo Projeto de Investimentos, etc.

Alocação de Recursoso Fábricaso Fazendas (agropecuária), etc.

Localizaçãoo Localização Industrialo Localização de Centrais Telefônicaso Localização de Escolas, etc.

Estoques, etc.

o Roteamento, etc

Os problemas de Misturas tem em comum o objetivo de se minimizar o custo do produto obtido pela mistura de diversas matérias-primas com diferentes custos e diferentes composições (química ou nutricional). As restrições se referem à participação dos componentes (ou nutrientes) no produto final. Este problema é aplicado na pecuária para formular dietas de ruminantes a um custo mínimo atendendo exigências de proteínas e minerais e utilizando animais e alimentos disponíveis em uma determinada região. Assim como é aplicado em dietas de animais, é aplicado também na alimentação de pessoas utilizando alimentos disponíveis e um público específico, como por exemplo em hospitais, spas, escolas (merenda infantil), etc.

Na indústria de fertilizantes a PO tem sido utilizada para formular diferentes tipos de composição a fim de otimizar o uso do nitrogênio, fósforo e potássio que variam conforme as necessidades de cada cultura (algumas culturas absorvem determinados elementos da própria natureza, outras necessitam recebê-las ). Ver estudo de caso no Anexo I.

Na indústria siderúrgica é aplicada a PO, por exemplo, para determinar quais minérios devem ser carregados no alto-forno de modo a se produzir, ao menor custo, uma liga de aço dentro de determinadas especificações de elementos químicos. Já na indústria petrolífera, pode-se querer definir qual deve ser a mistura de petróleo a ser enviada para uma torre de craqueamento para produzir seus derivados (gasolina, óleo, etc.) a um custo mínimo e considerando que os petróleos são de diversas procedências e possuem composições diferentes.

Na manufatura pode-se querer definir qual deve ser a composição de produtos a serem fabricados por uma empresa de modo que se atinja o lucro máximo, sendo respeitadas as limitações ou exigências do mercado comprador e a capacidade de produção da fábrica.

Os problemas de transporte têm em comum o objetivo de minimizar o custo de todo o volume de transporte, obedecendo às necessidades de recebimento do destino e da capacidade de envio da fonte. Este problema é aplicado, por exemplo, em fábricas que desejam transportar mercadorias para seus depósitos localizados em postos distintos a um custo mínimo. O mesmo estudo de transporte pode ser feito para transportar produtos de armazéns para mercados varejistas ou para transportar carros de locadoras de automóveis que estão com excesso de carros, para outras que estão com déficit em decorrência dos contratos de locação permitirem que sejam os automóveis devolvidos em locais diferentes daqueles onde foram originalmente alugados. Os problemas de transporte podem também ser aplicados para roteirização de coleta de lixo em uma cidade ou para planejar abastecimento de aviões a um custo mínimo, obedecendo a sua demanda de combustível e a disponibilidade dos fornecedores. Apresentamos apenas algumas aplicações dos problemas de transporte, existindo ainda uma infinidade delas.

Uma das áreas mais recentes em que a PO vem sendo aplicada é em Investimentos Financeiros. Nesta área pode-se aplicar a PO para fazer análise de riscos de créditos, para projetar investimentos, etc. Pode-se, por exemplo, querer saber quais ações devem compor uma carteira de investimento de modo que o lucro seja máximo e sejam respeitadas as previsões de lucratividade e as restrições governamentais.

4

Os problemas de Alocação de Recursos são muito comuns em PO. Problemas desse tipo dizem respeito à atribuição e distribuição de recursos entre diversas tarefas ou atividades que devem ser realizadas. Normalmente, os recursos disponíveis não são suficientes para que todas as atividades sejam executadas no nível mais elevado que se possa desejar. Assim, o que se procura, nesses casos, é encontrar a melhor distribuição possível dos recursos entre as diversas tarefas ou atividades, de forma a atingir um valor ótimo do objetivo estabelecido.

As indústrias dos mais diversos setores utilizam estes problemas para fazer uma programação de produção, ou seja, saber qual a quantidade a produzir de um determinado produto, entre vários, para se obter o maior lucro possível ou o menor custo possível e obedecendo as limitações do sistema em estudo, como por exemplo, matéria-prima, mão-de-obra, demanda de mercado, maquinário disponível, etc.

Na agricultura pode-se saber que alimentos devem ser plantados de modo que o lucro seja máximo e sejam respeitadas as características do solo, do mercado, do comprador e dos equipamentos disponíveis. Pode-se também querer saber qual quantidade de terra deve-se destinar a cada atividade (plantação, pecuária, etc.) de modo a ter o melhor retorno financeiro, respeitando as limitações de cada atividade.

Os problemas de localização possuem também importantes aplicações práticas nos mais diversos setores. Nestes problemas desejamos saber onde implantar fábricas, escolas, hospitais, centrais telefônicas, etc, de modo a atender economicamente a demanda específica e as limitações impostas por cada situação. No caso de localização industrial, por exemplo, podemos saber onde devem ser localizadas as fábricas e os depósitos de um novo empreendimento industrial de modo que os custos de entrega do produto aos varejistas sejam minimizados. No caso de localização de escolas, podemos querer planejar a localização de escolas de 1º Grau em áreas urbanas, de forma que sejam minimizadas as distâncias totais percorridas pelo conjunto de alunos.

Na Indústria da Construção Civil a PO é utilizada para reduzir seções transversais de estruturas como vigas e pilares. Essas seções devem ser a mínima possível de forma que sejam atendidas as restrições de carga e normativas. É utilizada para otimizar o traçado de cabos em vigas de concreto protendido, para reduzir pêras no corte de barras de ferro nas obras, etc.

Os problemas de Corte são problemas muito interessantes da PO. Esses problemas, além de minimizar as perdas nos cortes de barras, minimizam também perdas na fabricação de bobinas, chapas, tecidos, papéis, móveis, etc.

Seria possível ainda citar inúmeros exemplos de aplicação da PO nas mais diversas áreas, como estoques, meio ambiente, ecologia, saúde, etc. Na realidade, não existe situações em que sistemas humanos ou sistemas homem-máquina realizem trabalhos e a PO não possa ser utilizada para assegurar a eficácia dos aspectos de programação daqueles trabalhos.

Pesquisas que vem sendo efetuadas em empresas que têm utilizado a PO como ferramenta, mostram que a redução de custos se enquadra facilmente na faixa de 1% e 5%, existindo casos onde chegam até a 15%. Em indústrias como as siderúrgicas e petrolíferas, onde o custo de produção chegam na ordem de US$ 300 milhões anuais esses percentuais apresentados apresentam uma economia considerável.

A PO é uma ciência multidisciplinar, em constante evolução, que conta hoje com o desenvolvimento e utilização de diversos softwares e com sociedades nacionais e internacionais (SOBRAPO, INFORMS, etc) que promovem simpósios científicos,

5

premiações, mantém “sites”, geram publicações, etc, possibilitando a reciclagem e atualização dos conhecimentos e aplicações da PO.

Capítulo IMODELAGEM MATEMÁTICA

1.1- INTRODUÇÃO

O processo de tomar decisões gerenciais, em bases racionais, pressupõe a existência de uma ciência da gestão. Essa ciência corresponde à expressão em inglês Management Science, que se caracteriza pelo uso de abordagens científicas na avaliação de alternativas de ações. Certamente, o ato de refletir, avaliar conseqüências e decidir é um distintivo do ser humano, mas a criação de metodologias para promover o gerenciamento de decisões é um processo recente, datável da 2ª Guerra Mundial.

Como parte do esforço de guerra, foram desenvolvidas experiências que consistiam em propor problemas operacionais bélicos a grupos integrados por especialistas em domínios de conhecimentos diversificados, desde agrimensores a neurologistas, de físicos a engenheiros, de estatísticos a médicos, e assim por diante. De um modo geral, esses técnicos eram pessoas de notório saber, mas distantes do dia-a-dia militar. Portanto, a ação de tais grupos não consistia em fazer guerra, mas fazer pesquisa com fundamentos científicos, destinada a orientar ações militares. Essa modalidade metodológica foi, mais tarde, denominada de Pesquisa Operacional e abreviada por PO. (Pizzolato, 2004)

Em estudos de Pesquisa Operacional, o uso de modelos faz parte de sua própria essência. Trata-se de um recurso adotado para problemas complexos que desafiam a criatividade humana. Parte-se do princípio que, se o problema é simples, não são necessários muitos estudos para sua solução, basta usar a experiência, a intuição, o saber comum etc. À medida em que a complexidade do problema torna-se crescente, sua solução pode ultrapassar o ambiente local, mas podem existir especialistas capazes de resolvê-lo; logo, o mais apropriado e pragmático seria a convocação destes. Entretanto, há problemas cujo grau de dificuldade ultrapassa as limitações da mente humana, sendo impensável a possibilidade de identificar-se um técnico com a capacidade ou competência para dar uma solução satisfatória. Assim, em casos associados a problemas de alta complexidade, mas com elevado potencial de retorno do investimento, justifica-se a contratação de uma equipe, a mobilização dos recursos necessários e o desenvolvimento de um projeto de Pesquisa Operacional. Estudos desse tipo envolvem a construção de um modelo, que simplifica a realidade, porém preservando as relações essenciais de causa e efeito sobre o problema. Cria-se, portanto, um modelo simbólico, usando-se relações matemáticas que descrevem o problema em estudo. A Figura 1 ilustra o procedimento. (Pizzolato, 2004)

6

Pode-se dizer que, ao se construir um modelo, passa-se do mundo real ao virtual, mediante simplificações que viabilizam essa elaboração conceitual e sua avaliação subseqüente. O processo de construção de um modelo exige a mobilização de uma equipe que deve: avaliar a natureza do problema; interrogar pessoas envolvidas; levantar dados; identificar o problema e o que constitui a sua essência; entender relações de causa e efeito etc. Essa etapa compõe a fase inicial da metodologia e pode ser extremamente instrutiva em si mesma, na medida em que ela envolve uma radiografia descritiva do problema. Essa radiografia poderá salientar aspectos correntemente desprezados, assim como elementos indevidamente valorizados, tanto do problema em si, como dos procedimentos em uso.

Em uma fase posterior, o modelo deverá ser resolvido e sua solução validada. Validar significa avaliar se a solução do modelo corresponde, de fato, a uma solução consistente. A questão deve ser colocada porque, diante das simplificações adotadas, alguma relação importante pode ter sido ignorada ou alguma variável de decisão esquecida. Igualmente, a validação permite detectar o uso de dados numéricos equivocados. A validação pode ser feita de vários modos, em função do problema em estudo, mas, basicamente, consiste em comparar as decisões correntes com as decisões determinadas pelo modelo, como também avaliar com espírito crítico o significado prático das soluções propostas. Nesse processo de validação, os ganhos potenciais decorrentes da implementação das decisões sugeridas pelo modelo podem ser quantificados.

Caso a solução do modelo não passe nos testes de validação, deve-se rever as hipóteses, o modelo adotado, ou os dados utilizados. Esse processo de alterar e testar prossegue até a validação efetiva do modelo. A partir desse ponto o modelo passa a ser considerado útil e as decisões por ele preconizadas estarão em condições de serem implementadas.

O maior atrativo de um modelo é em situações que vão se repetir no futuro, como é o caso de gerenciar a operação cotidiana de um sistema, objeto de revisões periódicas. Um exemplo desse caso seria o problema de uma fábrica de rações animais que, como apontado por Lóss (1981), propiciou a primeira aplicação prática da PO no Brasil, efetuada pelo Professor Rui Leme no início dos anos 60. O modelo busca selecionar os possíveis ingredientes das rações de modo a minimizar os custos das matérias-primas adquiridas, mas sem prejuízo da qualidade desejada do produto. A existência de um modelo bem ajustado permite, semanalmente, a seleção mais econômica dos ingredientes comprados. Obviamente, o esforço e o custo em elaborar o modelo serão distribuídos por todas as vezes que o modelo voltar a ser aplicado.

No caso alternativo de um projeto elaborado com um propósito único, sem similar previsível, o custo de elaboração do modelo poderá não ter retorno econômico. Seria o caso de um modelo em que somente os custos do projeto sejam considerados e não os custos de sua operação. Nesse caso, seu atrativo pode ser menor e não ser justificável em termos econômicos, mas podendo, entretanto, ter um interesse acadêmico relevante, como demonstração de erudição acadêmica. Exemplo desse caso poderia ser o projeto estrutural de uma viga em balanço, ou do dimensionamento de um reservatório, em que se busca

7

minimizar o peso, o custo ou o emprego de material. Nesses caso, os ganhos do estudo se manifestarão uma única vez. (Pizzolato, 2004)

1.2- A METODOLOGIA DA PODiante do exposto, e obedecendo ao esquema sugerido pela Figura 1, um projeto de

Pesquisa Operacional pode ser decomposto em cinco estágios ou etapas, a saber:

1. Identificação do problema;2. Construção do modelo;3. Determinação da solução do modelo;4. Teste e validação da solução proposta;5. Implementação da solução.

Aplicações Práticas1

Caso 1: Produção de Rações.Entre rações para frangos, galinhas, suínos, bovinos, eqüinos, peixes, camarões, coelhos, avestruzes, codornas, animais domésticos etc, todo produtor de rações tende a manter ampla linha de produtos. O grande desafio é ter qualidade e baixos custos, pois o criador também pode produzir suas próprias rações. Com isso, sabe-se que todo produtor de rações dispõe de um modelo de otimização, única forma de reduzir custos e garantir qualidade. Assim, a função objetivo consiste em minimizar custos, enquanto que as restrições estabelecem qualidade de acordo com as características nutricionais apropriadas. Suponha que o produtor produza R tipos de rações e considere M tipos de insumos, desde derivados de produtos agrícolas até suplementos naturais e sintéticos. As variáveis de decisão indicarão a quantidade de cada insumo a ser aplicado em cada ração. O modelo exige um bloco de restrições para garantir a quantidade e a qualidade de cada tipo de ração R. Tipicamente, esse modelo possui um grande número de restrições. A validação da solução é um processo continuado de aperfeiçoamento do modelo do qual nenhum produtor pode prescindir. Certamente, a fase de validação e a implementação são mais relevantes no estágio preliminar de teste da metodologia.

Caso 2: Comercialização de Petróleo.O mercado spot de petróleo corresponde a um mercado onde qualquer empresa do ramo oferece lotes de petróleo de um dado tipo, a um certo preço e determinada data de entrega. Como todos atores do ramo tomam conhecimento da oferta ao mesmo tempo, a decisão de comprar deve ser tomada rapidamente. Para tanto, muitas empresas, inclusive a Petrobrás, desenvolveram modelos matemáticos que avaliam a vantagem econômica da compra. Além de recomendar ou não a compra, o modelo pode sugerir que, caso o lote seja adquirido, um outro lote de petróleo, disponível em certa data futura, deixou de ser interessante e deve ser oferecido no mesmo mercado spot. Trata-se de um modelo que pode oferecer imensas reduções de custo para a empresa. A validação de um modelo desse tipo consiste em acompanhar e medir, a posteriori, a qualidade das decisões tomadas pelo modelo. Esse 1 Casos retirados do livro 2ª Edição do Professor Nélio D. Pizzolato que está em fase de edição.

8

modelo foi útil na época que a empresa era grande importadora, declinando hoje a sua importância.

Caso 3: Localização de Escolas.Esse tema tem sido objeto de muito interesse, tanto teórico como prático em vários países. Uma variante mais simples do problema consiste em avaliar a atual localização das escolas. Para essa, os cinco estágios poderiam ser assim descritos: (i) Formulação do problema: a atual localização das escolas, com suas atuais capacidades, é satisfatória?; (ii) Construção do modelo: baseia-se em duas simplificações: primeiro, a distribuição da população é discretizada em setores censitários, como definidos pelo IBGE, e toda a população habita um ponto central do setor denominado centróide e, segundo, todo aluno prefere a escola mais próxima de sua residência; (iii) Solução: usando recursos aritméticos elementares, o modelo identifica para cada centróide a escola mais próxima, determinando a demanda por cada escola e compara esta com sua capacidade, apontando escassez ou excesso de vagas; (iv) Validação: consiste em visitar as escolas e a região, confirmar a demanda prevista pelo modelo e constatar se a escassez ou excesso estão de acordo com a percepção local; e (v) Implementação: uma vez validado, o modelo passa a ser considerado útil e sua implementação consiste em tomar as medidas apropriadas, como ampliar algumas escolas, reduzir a capacidade de outras e, eventualmente, propor a construção de novas.

1.3- O MODELO DE PROGRAMAÇÃO LINEARAtualmente, na Engenharia de Produção, um dos grandes desafios para o

profissional desta área é usar com maior eficiência possível os recursos disponíveis para serem alcançados objetivos estabelecidos, isto conduz aos problemas de otimização denominados “Problemas de Programação”. Os Problemas de Programação tratam de determinar distribuições ótimas de recursos limitados (mão-de-obra, matéria-prima, máquinas, etc.) para satisfazer objetivos dados (maximizar ou minimizar alguma quantidade numérica, tal como um lucro ou custo).

Um Problema de Programação é dito “Problema de Programação Linear” quando o objetivo a ser alcançado e as limitações dos recursos (restrições) são expressas como funções matemáticas lineares. Uma vez obtido o modelo linear, constituído pela função objetivo (linear) e pelas restrições (lineares), os algoritmos matemáticos da programação linear se incubem de processar a escolha da solução ótima, ou seja, uma solução que satisfaça simultaneamente todas as restrições do problema e otimize a FO.

O problema geral da Programação Linear pode ser descrito da seguinte forma: Dado um conjunto de “m” desigualdades ou equações lineares em “n” variáveis, queremos determinar valores não-negativos dessas variáveis que satisfarão as restrições e maximizarão ou minimizarão alguma função linear das variáveis. Matematicamente, temos:

Max (ou Min) Z= C1 x1 + C2 x2 + ...+ Cn xn

Sujeito aai1 x1 + ai2 x2 + ...+ ain xn bi , para i=1,2, ..., m

xj ≥ 0 , para j = 1,2,...,n

9

≤=≥

onde para cada restrição um e somente um dos sinais ≥ , = , ≤ vale, mas o sinal varia de uma restrição para outra.

Na construção do modelo matemático, no caso um modelo linear, não há regra fixa para esse trabalho, mas podemos sugerir um roteiro que ajuda a ordenar o raciocínio.Roteiro:

a) Quais as variáveis de decisão?Aqui o trabalho consiste em explicitar as decisões que devem ser tomadas e

representar as possíveis decisões através de variáveis chamadas variáveis de decisão. Se o problema é de programação da produção, as variáveis de decisão são as quantidades a produzir no período, se for um problema de programação de investimento, as variáveis vão representar as decisões de investimento, isto é, quanto investir em cada oportunidade de investimento, e em que período. Nas descrições sumárias de sistemas, isso fica claro quando lemos a questão proposta, isto é, a pergunta do problema. Normalmente assume-se que todas essas variáveis possam assumir somente valores não-negativos. b) Qual o objetivo?

Aqui devemos identificar o objetivo da tomada de decisão. Eles aparecem geralmente na forma da maximização de lucros ou receitas, minimização de custos, perdas, etc.

A função objetivo é a expressão que calcula o valor do objetivo (lucro, custo, receita, perda, etc.) em função das variáveis de decisão.

c) Quais as restrições? Cada restrição imposta na descrição do sistema deve ser expressa como uma relação

linear (igualdade ou desigualdade), montadas com as variáveis de decisão. Por exemplo, em um problema de programação da produção a disponibilidade de mão-de-obra e de matéria-prima representam restrições do problema que devem ser expressas por uma relação linear com as variáveis de decisão.

É importante enfatizar que todas as expressões mencionadas devem estar de acordo com a hipótese principal da PL, que diz respeito à linearidade propriamente dita, ou seja, todas as relações entre variáveis devem ser lineares. Isso implica a proporcionalidade das contribuições envolvidas (por exemplo, a contribuição individual de cada variável é estritamente proporcional a seu valor), assim como a aditividade dessas contribuições (por exemplo, a contribuição total de todas as variáveis é igual à soma das contribuições individuais, independentemente dos valores das variáveis).

Para facilitar a compreensão da modelagem matemática através da formulação de programação linear vamos introduzir neste ponto uma série de exemplos simples. Nos exemplos que serão apresentados não se deve ter preocupação com a solução dos problemas e sim apenas com sua modelagem, uma vez que este é o objetivo do presente capítulo.Exemplo Inicial:

Uma marcenaria possui 60m2 de madeira e dispõe de 40H.h para mão-de-obra para fabricar mesas e cadeiras, ambos de um só modelo. O processo de produção é tal que, para fazer 1 mesa a marcenaria gasta 7m2 de madeira e 3H.h de mão-de-obra. Para fazer uma

10

cadeira, a marcenaria gasta 4m2 de madeira e 5H.h de mão-de-obra. Os preços de venda da mesa e da cadeira são, respectivamente, R$ 1000,00 e R$ 500,00. Qual é o plano de produção para que a marcenaria maximize o rendimento obtido com as vendas? Construa o modelo de programação linear para esse caso. Solução:

a) Quais as variáveis de decisão?O que deve ser decidido é o plano de produção, isto é, quais as quantidades que devem ser produzidas de mesa e cadeira.

Portanto as variáveis de decisão serão x1 e x2 onde,x1 quantidade de mesa a produzirx2 quantidade de cadeira a produzir

b) Qual o objetivo?O objetivo é maximizar o rendimento obtido com as vendas, que pode ser calculado:

Rendimento devido à venda de mesa:1000 x1 rendimento por unidade de mesa vendida x quantidade de mesa produzida. Rendimento devido à venda de cadeira:500x2rendimento por unidade de cadeira vendida x quantidade de cadeira produzida. Rendimento total obtido com as vendas:Z = 1000 x1 + 500 x2

Objetivo: maximizar Z = 1000 x1 + 500 x2

c) Quais as Restrições?As restrições impostas pelo sistema são:

Disponibilidade de mão-de-obra para a produção: 40 H.h♦Mão-de-obra necessária para produzir mesas:3x1 mão-de-obra necessária para produzir uma mesa x quantidade de mesa produzida.♦Mão-de-obra necessária para produzir cadeiras:5x2 mão-de-obra necessária para produzir uma cadeira x quantidade de cadeira produzida.►Total de mão-de-obra necessária para a produção: 3x1 + 5x2

Resttrição descritiva da situação: 3x1 + 5x2≤ 40

Disponibilidade de madeira para a produção: 60 m2

♦Madeira necessária para produzir mesas:7x1 madeira necessária para produzir uma mesa x quantidade de mesa produzida.♦Madeira necessária para produzir cadeiras:4x2 madeira necessária para produzir uma cadeira x quantidade de cadeira produzida.►Total de madeira necessária para a produção: 7x1 + 4x2

Restrição descritiva da situação: 7x1 + 4x2≤ 60

11

Restrições ImplícitasComo as quantidades a produzir de mesa e cadeira devem ser positivas ou nulas,

temos as seguintes restrições de não-negatividade:x1≥0 quantidade a produzir de mesa deve ser maior ou igual a zero;x2≥0 quantidade a produzir de cadeira deve ser maior ou igual a zero;

RESUMO DO MODELO MATEMÁTICOMax Z= 1000 x1 + 500 x2 (Função Objetivo)Sujeito a

3x1 + 5x2≤ 40 (Restrições técnicas)7x1 + 4x2≤ 60x1 ≥0 (Restrições de não-negatividade)

x2≥0

1.4- EXEMPLOS DE FORMULAÇÃO DE MODELOS

Exemplo 1: Consideremos uma fábrica com três tipos de máquinas A, B e C, que podem produzir quatro produtos 1, 2, 3, 4. Cada um dos produtos tem que passar por alguma operação em cada um dos três tipos de máquinas (máquina de tornear, perfurar e laminar, por exemplo). A tabela abaixo mostra os tempos necessários de cada máquina para fazer a operação em cada produto, o total de funcionamento das máquinas por semana e o lucro obtido sobre a renda de uma unidade de cada um dos produtos. Considera-se que os lucros são diretamente proporcionais ao número de unidades vendidas. Sabendo-se que queremos determinar a produção semanal para cada produto de modo a maximizar os lucros, formule o problema de programação linear.

Produtos Tempo total Tipo de máquina 1 2 3 4 utilizado por semana

A 1,5 1 2,4 1 2000B 1 5 1 3,5 8000C 1,5 3 3,5 1 5000

Unidade de lucro 5,24 7,3 8,54 4,18

Suponha que xj seja o número de unidades do produto j produzidas por semana. Devem então ser calculados os valores de x1, x2, x3 e x4 que maximizem o lucro. Desde que o tempo disponível pela máquina seja limitado, não se pode aumentar arbitrariamente a saída de cada um dos produtos. A produção precisa ser distribuída entre os produtos 1, 2, 3 e 4 de modo que os lucros sejam maximizados sem exceder o número máximo de horas de máquinas disponíveis em cada um dos grupos de máquinas.

Modelo:FOMax Z = 5,24x1 + 7,3x2 + 8,54x3 + 4,18x4 (lucro semanal) S.A..1,5x1 + x2 + 2,4x3 + x4 ≤ 2000 horas (máquina do tipo A) x1 +5 x2 + x3 + 3,5x4 ≤ 8000 horas (máquina do tipo B) 1,5x1 + 3x2 + 3,5x3 + x4 ≤ 5000 horas (máquina do tipo C)

12

x1, x2, x3, x4 ≥0

Exemplo 2: DietaPara uma boa alimentação o corpo necessita de vitaminas e proteínas. A necessidade

mínima de vitaminas é de 32 unidades por dia e a de proteínas é de 36 unidades por dia. Uma pessoa tem disponível carne e ovos para se alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de proteínas. Cada unidade de ovo contém 8 unidades de vitaminas e 6 unidades de proteínas . Qual a quantidade diária de carne e ovos que deve ser consumida para suprir as necessidades de vitaminas e proteínas com o menor custo possível? Sabe-se que cada unidade de carne custa 3 unidades monetárias e cada unidade de ovo custa 1 unidade monetária.Modelo:FOMin Z = 3x1 + x2 (custo) S.A..4x1 + 8x2 ≥ 32 (vitaminas) 6x1 + 6x2 ≥ 36 (proteínas) x1, x2 ≥0

Exemplo 3: Investimentos Financeiros:Seja um investidor que dispõe de $ 10.000 e várias opções de investimento. O investidor pretende maximizar seu capital ao final de um ano, levando em conta os investimentos potenciais. No investimento A cada real aplicado hoje produz uma renda trimestral de $ 0,04 e devolve o principal ao final de um ano. No investimento B cada real aplicado hoje retorna $ 1,40 ao final de um ano. O investimento C estará disponível ao início do 3o trimestre e cada real aplicado retornará $ 1,25 ao final do ano. Sabe-se que qualquer real não investido pode ser mantido em fundos de renda fixa que remuneram o investidor em $ 0,03 por trimestre.

Por outro lado, o investidor deseja diversificar e evitar concentrar suas aplicações no melhor investimento. Assim, nenhuma alternativa deverá aplicar mais do que $ 5.000.Solução:Definindo-se:XA = investimento em A;XB = investimento em B;XC = investimento em C;R1, R2, R3 e R4 = recursos aplicados em fundos de renda fixa no início de cada trimestre correspondente.

Todos esses investimentos podem ser visualizados num eixo horizontal em escala trimestral, onde a seta para baixo indica uma aplicação e a seta para cima o retorno de caixa. O símbolo H registra o horizonte do estudo, ou final do 4o trimestre.

13

Nesse modelo, a função objetivo, equação (0), indica o montante ao final do 4o ano. A restrição (1) indica as três possibilidades de aplicação dos recursos hoje disponíveis, a saber: investimento A, investimento B e conta corrente. A restrição (2) mostra a aplicação em fundos de renda fixa ao início do 2o trimestre, sendo que a disponibilidade de recursos consiste na renda do investimento A mais o investimento R1 acrescido de juros. A restrição (3) representa o 3º trimestre e permite aplicar no investimento C e em fundos de renda fixa, sendo que os recursos disponíveis consistem nos juros do investimento A, mais o investimento R2 acrescido de sua renda. Para o início do 4o trimestre o único investimento possível é R4 e os recursos disponíveis são a renda do investimento A, mais a renda da aplicação em fundos de renda fixa do período anterior. Finalmente, as restrições seguintes referem-se à limitação dos nvestimentos e à não negatividade das variáveis.

Exemplo 4: Modelo de MisturasO dono de um aviário precisa fabricar uma ração especial para as suas galinhas, de

forma a atender às necessidades mínimas. A produção desejada desta ração é de 90 kg e a mistura deve ser formada por dois ingredientes básicos: o milho e o farelo de arroz, que custam $ 0,90 e $ 0,30 por kg respectivamente. Além disso, sabe-se que a ração precisa ter pelo menos 7% de proteína e 3% de fibra na sua composição, de forma a atender as necessidades diárias das aves.

A partir da tabela com a composição porcentual de fibra e proteína do milho e do farelo de arroz, pede-se formular um modelo de Programação Linear para atender as necessidades diárias a um custo mínimo.

14

Composição de cada ingrediente

Solução: As variáveis de decisão do modelo são as seguintes:X1 = quantidade de milho (kg)X2 = quantidade de farelo de arroz (kg)A produção diária da mistura deve ser de 90 kg, ou seja, em termos matemáticos:

Sabe-se também que a mistura deve ter pelo menos 7% de proteína e 3% de fibra. Portanto, a soma das quantidades de proteína de cada ingrediente deve exceder 7% da quantidade total, enquanto que a quantidade de fibra deve ser pelo menos superior a 3%, ou seja:

E, finalmente, o dono do aviário deseja produzir a mistura de forma a gastar o mínimo possível. Assim, o modelo completo seria:

Exemplo 5: Planejamento da ProduçãoDurante os próximos seis meses, o Artesanato Amazônia Ltda. deve atender os

seguintes compromissos de sua seção de malharia:

Jan. 4.000 peças Abr. 1.000 peçasFev. 2.000 peças Mai. 4.000 peçasMar. 5.000 peças Jun. 2.000 peças

Ao final de dezembro, há 500 peças em estoque e a empresa só tem capacidade para produzir 3.000 peças mensais. Entretanto, usando horas-extras, a empresa pode produzir até 600 peças a mais que sua capacidade nominal.

O custo variável de produzir uma peça é de $ 3 por peça e o custo de produzir em horas extras é de $ 3,40 por peça. Além disso, peças que ficam em estoque de um mês para outro provocam um custo aproximado de $ 0,25 por peça.

Pede-se um modelo de Programação Linear que satisfaça a demanda, mas minimizando os custos de produção.

Solução: Defina Xt , Yt e It ,para t =1,2,...6, para indicarem respectivamente a produção regular,em horas-extras e o estoque ao final do mês t.

15

Exemplo 6: Processos QuímicosA empresa Petro dispõe de duas fontes de petróleo bruto, denominadas Óleo A e Óleo

B, vendidos em barris (bbl), que ela pode adquirir para processamento. O Óleo A custa $ 28,00/bbl e o Óleo B $ 22,00/bbl, sendo que as quantidades disponíveis são de 10.000 bbl/dia e 7.000 bbl/dia respectivamente.

Esses óleos podem passar por dois processos sucessivos, nos quais não há perdas em volume: primeiro uma destilação que agrupa os óleos em suas frações leves e pesadas, as quais podem ser vendidas ou processadas novamente. O segundo processo é um craqueamento que ostransforma em dois produtos finais: gasolina e diesel. As Tabelas abaixo indicam as proporções resultantes dos dois processos.

% das frações por tipo de óleo % de gasolina e diesel por fração

Sabe-se que as frações leves podem ser vendidas por $ 20/bbl e as pesadas por $ 27/bbl; a gasolina é vendida por $ 35/bbl, enquanto que o diesel é vendido por $ 30/bbl.

Solução:As variáveis de decisão são as seguintes:OLEOA = óleo do tipo A comprado;OLEOB = óleo do tipo B comprado;FLEVE = frações leves produzidas;FPESADA = frações pesadas produzidas;LVENDIDA = volume das frações leves vendidas;PVENDIDA = volume das frações pesadas vendidas;LCRACK = volume das frações leves craqueadas;PCRACK = volume das frações pesadas craqueadas;GASOLINA = volume de gasolina produzido;DIESEL = volume de diesel produzido

O inter-relacionamento das varáveis anteriores pode ser melhor visualizado por um diagrama.

16

Com as variáveis de decisão acima, o modelo torna-se:

O modelo acima tem 10 variáveis e 8 equações. Pode-se notar que duas variáveis podem ser suprimidas, a saber: FLEVE e FPESADA, o que reduziria o sistema em duas variáveis e duas equações, mas esta redução não é obrigatória, além de obscurecer as relações descritivas. Para resolver o sistema, deve-se escrever todas as variáveis do lado esquerdo, com os segundos membros iguais a zero.

Exemplo 7: A Companhia Veloz deseja determinar quantas unidades produzir durante os meses de junho, julho, agosto e setembro, meses de pico de demanda, para um de seus produtos líderes. Ela dispõe dos seguintes dados:

Junho Julho Agosto SetembroDemanda prevista 800 1.000 900 800Capacidade produtiva Regular 700 700 700 700 Horas extras 50 50 50 50 Subcontratação 150 150 130 120Estoque inicial em junho 100 unidadesCustos de produção Normal $ 40,00/unidade Horas extras $ 50,00/unidade Subcontratação $ 70,00/unidade Manutenção do estoque $ 2,00/unidade/mês

Solução

Definição das variáveis de decisãox11 – quanto produzir em junho – horas normaisx12 – quanto produzir em junho – horas extrasx13 – quanto produzir em junho – subcontrataçõesx21 – quanto produzir em julho – horas normaisx22 – quanto produzir em julho – horas extras

17

x23 – quanto produzir em julho – subcontrataçõesx31 – quanto produzir em agosto – horas normaisx32 – quanto produzir em agosto – horas extrasx33 – quanto produzir em agosto – subcontrataçõesx41 – quanto produzir em setembro – horas normaisx42 – quanto produzir em setembro – horas extrasx43 – quanto produzir em setembro – subcontratações

O custo de manutenção dos estoques em junho será:EMjun x $2,00/unidade x mês e EMjun= (EI)jun + (EF)jun

2Sabe-se ainda que:Como P = D+EF-EI, teremos EF= EI+P-D P = Produção

EF= Estoque FinalEI = Estoque Inicial

A tabela a seguir auxilia o cálculo:Mês EI Produção Demanda EFJunho 100 x11+ x12+ x13 800 x11+ x12+ x13-700Julho x11+ x12+ x13-700 x21+ x22+ x23 1.000 x11+ x12+ x13+

x21+ x22+ x23- 1.700Agosto x11+ x12+ x13+

x21+ x22+ x23- 1.700x31+ x32+ x33 900 x11+ x12+ x13+

x21+ x22+ x23 +x31+ x32+ x33 –2.600

Setembro x11+ x12+ x13+ x21+ x22+ x23 +x31+ x32+ x33 –2.600

x41+ x42+ x43 800 x11+ x12+ x13+ x21+ x22+ x23 +x31+ x32+ x33 +x41+ x42+ x43 –3.400

Custo do EstoqueO custo mensal do estoque é:Cjun=(EI)jun + (EF)jun x $2,00/unidade x mês 2Somando-se para os quatro meses, tem-se:Cestoque= ½ (EIjun+EFjun+ EIjul+EFjul+ EIago+EFago+ EIset+EFset) x $2,00

Como EFjun= EIjul etc.Cestoque= ½ (EIjun+2EIjun+ 2EIago+2EIset+EFset) x $2,00 = EIjun+2EIjun+ 2EIago+2EIset+EFset

Substituindo-se pelas expressões da tabela anterior tem-se:Cestoque=100 + 2(x11+ x12+ x13-700)+ 2(x11+ x12+ x13+ x21+ x22+ x23- 1.700) ++ 2(x11+ x12+ x13+ x21+ x22+ x23 +x31+ x32+ x33 –2.600) + (x11+ x12+ x13+ x21+ x22+ x23 +x31+ x32+ x33 +x41+ x42+ x43 –3.400)

Deduzindo-se tem-se:Cestoque= 7x11+ 7x12+ 7x13+ 5x21+5x22 + 5x23 + 3x31+ 3x32+ 3x33 +x41+ x42+ x43 –13.300

18

Custo de ProduçãoCprodução = 40(x11+ x21+ x31+ x41) + 50(x12+ x22+ x32+ x42)+ 70(x13+ x23+ x33+ x43)

Custo TotalCtotal= Cprodução+Cestoque

Após a redução, tem-se:F.O. = Ctotal =47x11+ 57x12+77x13+ 45x21+55x22 + 75x23 + 43x31+ 53x32+ 73x33 +

+41x41+51x42+ 71x43 –13.300

Função Objetivo

MIN Ctotal =47x11+ 57x12+77x13+ 45x21+55x22 + 75x23 + 43x31+ 53x32+ 73x33 ++41x41+51x42+ 71x43 –13.300

RestriçõesO EF deve ser maior ou igual a zero.x11+ x12+ x13-7000oux11+ x12+ x13 700x11+ x12+ x13+ x21+ x22+ x23 1.700x11+ x12+ x13+ x21+ x22+ x23 +x31+ x32+ x33 2.600x11+ x12+ x13+ x21+ x22+ x23 +x31+ x32+ x33 +x41+ x42+ x43 3.400

x11700x1250x13150x21700x2250x23150

Exemplo 8: Ver ANEXO 1- ESTUDO DE CASO

1.5- PROBLEMAS PROPOSTOS

PROBLEMA 01

Um carpinteiro possui 6 peças de madeira e dispõe de 28 horas de trabalho para confeccionar biombos ornamentais. Dois modelos venderam muito bem no passado, de maneira que ele se limitou a esses dois tipos. Ele estima que o modelo I requer 2 peças de madeira e 7 h de trabalho, enquanto o modelo II necessita de 1 peça de madeira e 8 horas de trabalho. Os preços de venda são, respectivamente, R$ 220,00 e R$ 105,00. Faça um modelo linear que ajude o carpinteiro a decidir quantos biombos de cada modelo devem ser confeccionados se desejar maximizar o rendimento obtido com as vendas.

19

x31700x3250x33 130x41700x4250x43120

x110x120x130x210x220x230

x310x320x33 0x410x420x430

A solução do sistema, com a utilização do software LINDO, leva à seguinte solução: Mínimo custo = $ 150.380,00Variáveis: x11=700 x12=50x13=70 x21 =700 x22= 50 x23=150 x31

=700 x32=50x33 =130 x41=700 x42=50 x43=50

PROBLEMA 02

Seja uma máquina de fazer copos com dois moldes diferentes. Com o primeiro deles são fabricados 100 caixas de copos para suco em 6 hs; com o segundo, são fabricadas 100 caixas de copos para coquetel em 5 hs. A máquina opera 60 hs por semana e a capacidade do depósito é de 15.000 m3. Uma caixa de copos para suco mede 10 m3; uma caixa de copos para coquetel mede 20 m3. O lucro pela venda de uma caixa de copo é de $5(copos para suco) e de $4.5(copos para coquetel). O único freguês disponível não aceita comprar mais de 800 caixas por semana de copos para suco e compra tudo que for produzido de copos para coquetel. Formule um modelo linear para ajudar o fabricante a decidir quantas caixas por semana de cada tipo de copo devem ser produzidas para maximizar o lucro.

PROBLEMA 03

Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas:A(Arrendamento)–Destinar certa quantidade de alqueires para a plantação de cana-de-açúcar, a uma usina local, que se encarrega da atividade e paga pelo aluguel da terra $300,00 por alqueire por ano.P (Pecuária)- Usar outra parte para a criação de gado de corte. A recuperação das pastagens requer adubação (100Kg/Alq) e irrigação (100.000 litros de água/Alq) por ano. O lucro estimado nessa atividade é de $ 400,00 por alqueire por ano.S(Plantio de Soja)- Usar uma terceira parte para o plantio de soja. Essa cultura requer 200Kg por alqueire de adubos e 200.000 litros de água/Alq para irrigação por ano. O lucro estimado nessa atividade é de $500,00/ alqueire no ano.Disponibilidade de recursos por ano:12.750.000 litros de água14.000 Kg de adubo100 alqueires de terraQuantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno? Construa o modelo de decisão.

PROBLEMA 04

O açougue de um povoado prepara tradicionalmente suas almôndegas, misturando carne bovina magra e carne de porco. A carne bovina contém 80% de carne e 20% de gordura e custa R$0,80 o Kg; a carne de porco contém 68% de carne e 32% de gordura e custa R$0,60 o Kg. Quanto de carne bovina e quanto de carne de porco deve o açougue utilizar por Kg de almôndegas se desejar minimizar seu custo e conservar o teor de gordura da almôndega não superior a 25%?

PROBLEMA 05

Um fazendeiro está criando porcos para vender e deseja determinar as quantidades dos tipos de alimentos disponíveis que devem ser dadas a cada porco para atingir certos requerimentos nutricionais, a um custo mínimo. O número de unidades de cada tipo de ingrediente nutricional básico contido em um quilograma de cada tipo de alimento é dado na tabela que segue, juntamente com os requerimentos nutricionais diários e custos dos alimentos. Construa um modelo que ajude o fazendeiro a decidir a alimentação ideal a se recomendada aos porcos.Ingredientes Nutricionais

Milho Tancagem Alfava Requerimento mínimo diário (g/Kg de ração)

Carboidratos(g/Kg)Proteínas (g/Kg)Vitaminas (g/Kg)

903010

208020

406060

200180150

Custos ($/Kg) 21 18 15

20

PROBLEMA 06

Uma excurcionista planeja fazer uma viagem acampando. Há cinco itens que a excurcionista deseja levar consigo, mas estes, juntos, excedem o limite de 60 Kg que ela supõem ser capaz de carregar. Para ajudar a si própria no processo de seleção ela atribuiu valores, por ordem crescente de importância, a cada um dos itens segundo a tabela.Item 1 2 3 4 5Peso (Kg) 52 23 35 15 7Valor 100 60 70 15 15Faça um modelo linear para o problema para ajudar a excurcionista a decidir que itens devem ser conduzidos de forma a maximizar o valor total e sem exceder as restrições de peso.

PROBLEMA 07

Suponhamos que possuímos barras de 6 m de comprimento que devem ser convenientemente cortadas para obtermos barras menores, nos seguintes tamanhos:50 barras de 2m60 barras de 3m90 barras de 4 mDesenvolva um modelo linear que determine como deverão ser os cortes de forma a minimizar as perdas.

PROBLEMA 08

Uma agencia de correios requer números diferentes de empregados em dias diferentes da semana. O número de empregados em horário integral necessários em cada dia é dado na tabela abaixo. As regras do sindicato estabelecem que cada empregado em horário integral deve trabalhar cinco dias consecutivos, e então receber dois dias livres. A agência de correios quer satisfazer as suas necessidades diárias usando apenas empregados em horário integral. Formule um programa linear que a agência possa usar para minimizar o número de empregados em horário integral que deve ser contratado.

No de EmpregadosDia 1 = Segunda Feira 17Dia 2 = Terça feira 13Dia 3 = Quarta Feira 15Dia 4 = Quinta Feira 19Dia 5 = Sexta feira 14Dia 6 = Sábado 16Dia 7 = Domingo 11

1.6- SOLUÇÃO GRÁFICA

Os problemas de programação linear que envolvem apenas duas variáveis podem ser resolvidos graficamente. A interpretação geométrica dos problemas de programação linear é muito importante uma vez que o exame dos tipos de negócio que podem ocorrer em casos simples envolvendo somente duas variáveis fornece um vasto aprofundamento no que pode ocorrer em um caso mais geral com qualquer número de variáveis.

De início, vamos achar uma interpretação geométrica e a solução para o seguinte problema de programação linear.

21

Observação: Para formular este problema corretamente é preciso perceber que a decisão a ser feita não é o número de empregados que trabalha em cada dia, e sim o número de empregados que começa a trabalhar em cada dia da semana.

(1)

Max Devemos achar, primeiramente, os conjuntos de números (x1, x2), que são soluções viáveis para o problema. Introduzimos um sistema de coordenada x1x2 e notamos que qualquer conjunto de números (x1, x2) é um ponto no plano x1x2. Todos os pontos (x1, x2) que se encontram à direita ou no eixo x2 têm . Igualmente, todos os pontos que se encontram acima do eixo x1 têm . Segue-se que qualquer ponto que se encontrar no primeiro

quadrante tem e assim satisfaz às restrições não-negativas. Qualquer ponto que for uma solução viável deve-se encontrar no primeiro quadrante.

Para determinar o conjunto de pontos do primeiro quadrante que satisfaça às restrições, devemos interpretar geometricamente inequações tais como . Se

o sinal de igualdade vingar, isto é, , temos a equação para uma linha reta, e qualquer ponto na linha reta que satisfaça a equação. Considere agora o ponto (0,0), isto é, a origem. Observamos que 3(0) + 5(0) = 0 < 15, tal que a origem também satisfaz a inequação. De fato, qualquer ponto que se encontre abaixo ou na linha

satisfaz . Entretanto, nenhum ponto que se encontre acima da linha satisfaz

a inequação. Sendo assim, o conjunto de pontos que satisfaz a inequação consiste em todos os pontos no plano x1x2 que se encontram abaixo ou na linha

. Os pontos que satisfazem as restrições não-negativas e estas inequações são todos os pontos do primeiro quadrante que se encontram abaixo ou sobre a linha

. Precisamente da mesma maneira, vemos que todos os pontos que

satisfazem e as restrições não-negativas são todos os pontos do primeiro

quadrante abaixo sobre a linha

Fig. 1.1

O conjunto de pontos que satisfazem tanto como , assim como as restrições não-negativas, é o conjunto de pontos na região sombreada da Fig.1.1.

22

Qualquer ponto nesta região é uma solução viável, e somente os pontos nesta região são soluções viáveis.

Ainda não dissemos nada sobre a função objetivo. Para resolver o problema de programação linear, devemos achar o ponto, ou pontos, na região de soluções viáveis que dêem o maior valor da função objetivo. Agora para qualquer valor fixo de z, é uma linha reta. Qualquer ponto nesta linha dará o mesmo valor de z. Para cada valor de z diferente, obtemos uma linha diferente. É importante notar que todas as linhas que correspondem a diferentes valores de z são paralelas. Isto acontece porque a inclinação de

qualquer linha é e independente de z. Em nosso problema, c1,c2

são fixos e as linhas, paralelas.Devemos agora ser capazes de ver a solução de um problema. Queremos achar a

linha com o maior valor de z que tem pelo menos um ponto em comum com a região de soluções viáveis. As linhas paralelas na Fig.1.1 representam a função objetivo para os três valores diferentes de z. É claro que z1 não é o valor máximo de z, pois a linha pode ser movida para cima, aumentando, em conseqüência, z, enquanto alguns de seus pontos ainda estão na região das soluções viáveis. Por outro lado, embora z3>z2 e z1, a linha correspondente a z3 não tem nenhum ponto em comum com a região de soluções viáveis; em conseqüência, nenhuma solução viável pode levar a um valor tão grande de z. Vemos assim que z2 é o valor máximo de z, e a solução viável que nos leva a esse valor de z é o canto A da região de soluções viáveis.

A figura mostra que os valores das variáveis para a solução ótima são aproximadamente x1 = 1, x2 = 2,4. Para determinar os valores exatos, notamos que o ponto que representa a solução ótima é a interseção das linhas e . Resolvendo estas duas equações simultaneamente, achamos que x1 = 1,053 e x2 = 2,368. A substituição desses valores na função objetivo mostra que o valor máximo do z é 12,37.

23

x2

x1

A

B

0

Z1 Z2 Z3

Fig. 1.2

Vamos considerar agora o problema:

(2)

Max Este problema é o mesmo que o que acabou de ser resolvido, exceto para uma função objetivo levemente diferente. A região de soluções viáveis é a mesma que a para o problema anterior. A Fig. 1.2 mostra as linhas da função objetivo de (2) para três valores diferentes de Z.

Obviamente, Z2 é o valor máximo do Z. Agora, entretanto, a linha que representa a função objetivo se encontra ao longo de um dos lados do polígono de soluções viáveis. Isto significa que não há valores únicos de x1,x2 que maximizem Z; qualquer ponto do lado AB do polígono dá a solução ótima de Z.. Note que o canto que era ótimo para o problema prévio e também ótimo para este problema. Usando estes valores de x1,x2, achamos que Max Z = 5,0. Para este problema, duas extremidades, assim como qualquer ponto sobre a linha que liga estes dois pontos, são soluções ótimas. Quando um problema de programação linear tem mais de uma solução ótima, dizemos que há uma alternativa ótima; fisicamente, isto significa que os recursos podem ser combinados de mais de uma maneira para maximizar o lucro.

24

x2

x1

Z1

Z2

Z3

0

A1

Fig 1.3

Como um exemplo de um problema para o qual a função objetivo será considerada minimizada:

(3)

Min A interpretação geométrica do problema é dada na Fig. 1.3

O valor mínimo de Z é Z2. Este mínimo é achado em um ponto único, o ponto de interseção A das linhas e . Resolvendo estas duas equações

simultaneamente, vemos que a solução ótima é , e Min Z = 4.

Os problemas de programação linear envolvendo três variáveis também podem ser apresentados geometricamente; entretanto, sua solução gráfica é mais difícil. Como ilustração, vamos resolver graficamente o seguinte problema em três variáveis:

(4)

Max

A região que representa as soluções viáveis é o poliedro sombreado na figura 1.4. recordemos que uma equação em três variáveis, tal como 4x1+6x2+3x3=24, é um plano. Quando o sinal de igualdade é substituído por uma inequação (<), o conjunto de pontos que satisfazem esta inequação é a coleção de todos os pontos que se encontram ou acima ou abaixo do plano. O conjunto de pontos (x1,x2,x3) que, quando substituído na função objetivo, leva ao valor dado de z, se encontra no plano z = 0,5x1+6x2+5x3. Quando z varia, obtém-se uma série de planos paralelos. O plano que representa o maior valor de z que tem pelo menos um ponto em comum com a região de soluções viáveis dá o Max Z. O ponto ou pontos da região de soluções viáveis que se encontram neste plano são soluções viáveis.

Fig. 1.4

25

Vê-se que a solução ocorre no vértice A do poliedro de soluções viáveis. Neste ponto, os planos 4x1+6x2+3x3=24 e x1+1,5x2+3x3=12 se interceptam. Entretanto, x1=0 em A. Assim, pela solução simultânea de 6x2+3x2=24 e 1,5x2+3x3=12, x2 e x3 são achados e

; a solução ótima é x1=0; , e Max .

Alguns casos excepcionais:Os exemplos da seção anterior ilustram o que pode ser chamado problemas de

programação linear “bem comportados”.Agora queremos mostrar que há casos excepcionais que precisam ser levados em

consideração se uma técnica geral para solução de problemas de programação linear for desenvolvida.

Vamos estudar o seguinte problema

(5)

Max

A região de soluções viáveis é a região sombreada da Fig. 1.5. As linhas que representam a função objetivo para vários valores de Z são também desenhadas.

26

x2

x1

0Z = 4

Z = 6Z = 10

Fig. 1.5

Encontramos um novo fenômeno. A linha que representa a função objetivo pode ser movida sempre paralela a si mesma na direção de aumento de Z, e ainda tem alguns pontos na região de soluções viáveis. Assim, Z pode aumentar arbitrariamente, e o problema não tem valor máximo do Z. Em tal caso dizemos que o problema tem uma solução ilimitada.

Não esperamos que qualquer problema de programação linear represente alguma situação prática de ter uma solução ilimitada, pois isto implicaria, por exemplo, a viabilidade de um lucro infinito. Entretanto, a limitação de recursos e a impossibilidade de se aumentar os lucros são precisamente as razões para nosso interesse no uso de programação linear. Não obstante, ocasionalmente ocorre um erro na formulação de um problema real que leva a uma solução ilimitada (o autor cometeu tal erro).

x2

Z3

Z2

Z1

Fig. 1.6

x1

0

No exemplo acima, ambas as variáveis podem crescer arbitrariamente quando z aumenta. Entretanto, uma solução ilimitada não implica necessariamente que todas as variáveis possam ser aumentadas arbitrariamente quando z tende ao infinito. Pode-se ver isto na solução do problema

(6)

Max

Este problema é representado graficamente na Fig 1.6.Já notamos que o conjunto de variáveis que maximizam a função objetivo não

precisa ser necessariamente único. Agora veremos que, embora z tenha um valor máximo finito, há soluções que dão este z máximo que tem valores arbitrariamente grandes das variáveis. Isto é ilustrado pelo seguinte exemplo.

27

(7)

Max ,

que está resolvido graficamente na Fig. 1.7. Este problema não é completamente normal, pois há soluções com variáveis arbitrariamente grandes que levam a valores ótimos do Z. O valor máximo do Z é 4. Além disso, qualquer ponto (x1,x2) que se encontre no lado da região de soluções viáveis.

x2

Z2=4

Fig. 1.7Z3

Z1

0 x1

Entretanto, não há nenhuma garantia automática de que todos os problemas da programação linear têm soluções viáveis. O próximo problema, mostrado graficamente na figura 1.8, não tem solução, pois as restrições são incompatíveis:

(8)

Max ,

não há nenhum ponto (x1,x2) que satisfaça ambas as restrições.As restrições podem ser compatíveis e ainda assim não haver solução viável porque

nenhum ponto que satisfaz as restrições também satisfaz as restrições não-negativas. O problema seguinte, ilustrado geometricamente na Fig. 1.9, dá um exemplo de tal caso.

28

(9)

Max ,

x2

Fig. 1.8

o x1

x2

o x1

Fig. 1.9

29

Qualquer ponto na área sombreada satisfaz as restrições inequações. Entretanto, como nenhuma solução tem , não há solução viável.

O leitor não deve achar que os exemplos apresentados nesta seção são de interesse somente hipotético e nunca ocorrem no mundo real. Enquanto realmente não esperamos que qualquer problema prático propriamente formulado exiba tal comportamento, um problema que envolve um grande número de variáveis e restrições dificulta extremamente o estudo da compatibilidade, a existência de uma solução viável, e a certeza da não-existência de uma solução ilimitada. Por causa destas possibilidades de erro na formulação dos problemas, os casos excepcionais discutidos nesta seção podem ocorrer na prática. Assim, a técnica computacional delineada para a solução de um problema de programação linear deve ser o bastante para revelar a existência de uma solução ilimitada ou a ausência de uma solução viável. Seria bem ruim se tivéssemos que averiguar se o problema possui um máximo e um mínimo finitos antes que pudéssemos processar o computador.

30

Capítulo II FUNDAMENTOS MATEMÁTICOS

2.1- MATRIZ

Definição: É um conjunto ordenado de números, de forma retangular, e é escrito no seguinte formato:

a11 a12 a13 ....... a1n

A= a21 a22 a23 ....... a2n

a31 a32 a33 ....... a3n

: : : : : : : :am1 am2 am3 ....... amn

Representação da matriz: A= [ aij ]m x n

ColunaLinha

Representação de um elemento da matriz: aij

Matriz Quadrada: Se m=n (no de linhas = no de colunas) temos uma matriz quadrada de dimensão “n”.

a11 a12 ....... a1n

An= a21 a22 ....... a2n

: : : : : : an1 an2 ....... ann

Diagonal Secundária Diagonal Principal (i+j) = n+1 aij, onde i=j

Matriz Linha e Matriz Coluna: (vetores)

a11 B= [ b11 b12 b13 ....... b1n ]linha

31

Um elemento da matriz

Coluna

Linha

Dimensão da matriz

a21

A=a31

: :am1

coluna

2.2- SISTEMA DE EQUAÇÕES LINEARESEquações Lineares de “n” variáveis:a1 x1 + a2 x2 + a3 x3 + .........+ an xn = bonde a1, a2, a3 ,....., an e b são constantes reais.

Sistema de Equações Lineares: É um conjunto de equações lineares.a11 x1 + a12 x2 + a13 x3 + .........+ a1n xn = b1

a21 x1 + a22 x2 + a23 x3 + .........+ a2n xn = b2

: : : : :am1 x1 + am2 x2 + am3 x3 + .........+ amn xn = bm

onde aij e bk são constantes reais para i,k=1, ....,m e j= 1,...,n

O sistema linear pode ser escrito como uma equação matricial:A X = B

a11 a12 ....... a1n

A= a21 a22 ....... a2n

(mxn) : : : : : : am1 am2 ....... amn

x1 b1

x2 b2

X= : B= :(nx1) : (mx1) :

xn bm

Matriz Aumentada: [A / B]

a11 a12 ....... a1n b1

A= a21 a22 ....... a2 b2

(mxn) : : : : : : : :am1 am2 ....... amn bm

32

Uma forma de resolver um sistema linear, é achar um outro sistema mais simples equivalente ao original. Isso se faz aplicando sucessivamente uma série de operações sobre as equações.

Operações Elementares:

Multiplicar uma equação por um escalar diferente de zero; Somar a uma equação um múltiplo de outra equação.

Exemplo:

2x + 4y + z = 10 x + y = 3 x + 2y = 5

MÉTODO DE GAUSS-JORDAN:1. Colocar na forma de matriz aumentada:

2 4 1 10

1 1 0 31 2 0 5

2. Utilizando as propriedades elementares nas linhas da matriz aumentada, vamos procurar deixar a matriz na forma escalonada reduzida:

Matriz escalonada reduzida:a) Todas as linhas nulas ocorrem abaixo das linhas não nulas;b) O primeiro elemento não nulo de cada linha não nula é igual a 1 (chamado

de pivô);c) O pivô da linha i+1 ocorre à direita do pivô da linha i, para i=1,...,m-1;d) Se uma coluna contém um pivô, então todos os seus outros elementos são

iguais a zero.Obs: Se uma matriz satisfaz as propriedades (a), (b), e (c), mas não necessariamente

(d), dizemos que ela é uma matriz escalonada.

2.3-VETORES NO PLANO E NO ESPAÇOVetor magnitude Representação:

direção sentido

orientação indica a direção e o sentido do vetorcomprimento representa a magnitude do vetorObservações:

Dois vetores são iguais se eles possuem o mesmo comprimento, a mesma direção e o mesmo sentido, mesmo se possuírem origens em pontos diferentes;

Se um vetor W= V diz-se que W é um múltiplo escalar do outro; Dois vetores não nulos são paralelos(ou colineares) se, e somente se, um é múltiplo

escalar do outro.

33

A

B

AB

extremida

origem

Componentes do vetor V no plano:

2.4 - COMBINAÇÃO LINEAR

Definição:Um vetor V do Rn é uma combinação linear dos vetores V1,...,Vk , se a equação vetorial

x1 V1 + x2 V2 +.....+ xk Vk =V

possuir solução, ou seja, se existirem escalares x1, ...., xk que satisfazem a equação acima. Neste caso, dizemos também que V pode ser escrito como uma combinação linear de V1, ..., Vk.

2.5- INDEPENDÊNCIA LINEAR

Definição:Dizemos que um conjunto S={ V1, ..., Vk} de vetores é linearmente independente (L.I.) se a equação vetorial

xo v1

v2 V (v1, v2)

OV

34

y

As coordenadas de V são iguais as componentes de OV

Componentes do vetor V no espaço:

Cada par de eixo determina um plano coordenado. Temos três planos coordenados:XYXZYZ

x

y

z

v3

v1

v2

V= (v1, v2, v3)Componentes de V

x1 V1 + x2 V2 +.....+ xk Vk = 0 só possuir a solução trivial, ou seja, se a única forma de escrever o vetor nulo como combinação linear dos vetores V1, ..., Vk é aquela em que todos os escalares são iguais a zero. Caso contrário, isto é, se a equação acima possuir solução não trivial, dizemos que o conjunto S é linearmente dependente (L.D.).

Observações: Se dois vetores V1 e V2 no R2 são L.D., então um deles é um múltiplo escalar do outro. Portanto, eles são paralelos. E reciprocamente, se eles são L.I., então um não é múltiplo escalar do outro e portanto não são paralelos. Se três vetores V 1, V2 e V3 do R3 são L.D., então um deles é uma combinação linear dos outros dois, ou seja, um deles é uma soma de múltiplos escalares dos outros dois. Portanto, eles são coplanares, isto é, são paralelos a um mesmo plano. E reciprocamente, se eles são L.I., então nenhum deles é combinação linear dos outros dois. Portanto eles não são coplanares.

2.6- SOLUÇÃO BÁSICA VIÁVELVamos supor o seguinte sistema:a11 x1 + a12 x2 + a13 x3 + .........+ a1n xn = b1

a21 x1 + a22 x2 + a23 x3 + .........+ a2n xn = b2

: : : : :am1 x1 + am2 x2 + am3 x3 + .........+ amn xn = bm

Forma Matricial: A X = B

a11 a12 ....... a1n

a21 a22 ....... a2n

: : : : : : am1 am2 ....... amn

Suponhamos que m n e que o posto da matriz P(A)=m (posto da matriz A é o número máximo de colunas L.I. em A).

Obtém-se uma solução básica viável para o sistema acima fazendo-se (n-m) das variáveis “x” iguais a zero e determinando-se uma solução não-negativa para as variáveis “x” restantes, admitindo-se que os “m” vetores correspondentes às variáveis “x”, que não foram igualadas a zero, são L.I.

O conjunto de variáveis, que inicialmente não são feitas iguais a zero, é chamado conjunto de variáveis básicas. Se uma ou mais das variáveis básicas tornarem-se iguais a zero, a solução básica será dita degenerada. Se todas as variáveis básicas forem positivas, a solução básica será dita não-degenerada (factível ou compatível).

2.7- COMBINAÇÃO CONVEXAConsidere um conjunto de vetores V={ V1, V2, ..., Vn } todos pertencentes a Rm

v1

35

x1 b1

x2 = b2

: : : : xn bm

v2

V1= : V={ V1, V2, ..., Vn } Rm

: j , j=1,2,...,n vm

j são constantes reais que satisfazem as relações:1 + 2 + .....+ n = 1j 0 para j= 1,2,...,n

então o vetor b = 1 V1 + 2 V2 +.....+ n Vn é uma combinação convexa dos vetores V1, V2, ..., Vn.

2.8- CONJUNTO CONVEXOUm conjunto X de vetores é convexo se, para dois vetores quaisquer X1, X2 pertencentes ao conjunto, o segmento de reta entre estes vetores também pertence ao conjunto, ou seja, X1 XX2 X

Exemplos Gráficos

Um vetor P é um ponto extremo de um conjunto convexo se não se puder expressá-lo como uma combinação convexa de dois vetores de conjunto, isto é, um ponto extremo não pode estar situado sobre o segmento de reta entre dois outros vetores quaisquer do conjunto. Um ponto extremo é ponto da fronteira do domínio, pois caso contrário, ele estaria entre dois outros pontos quaisquer. Nem todo ponto limite de um conjunto convexo é necessariamente um ponto extremo. Alguns pontos limites podem-se situar entre dois outros pontos limites.

Capítulo IIIMÉTODO SIMPLEX

3.1- INTRODUÇÃO

O Método Simplex é um procedimento geral para resolver um Problema de Programação Linear. Foi desenvolvido em 1947 pelo matemático norte-americano George B. Dantzig e consiste em um método iterativo que percorre os pontos extremos do conjunto de soluções compatíveis do problema. Este método é formado por um grupo de critérios para escolha de soluções básicas que melhorem o desempenho do modelo, e também de um teste de otimalidade.

Para ser iniciado, é necessário se conhecer uma solução compatível básica (chamada solução inicial) do sistema. Posteriormente, é verificado se a presente solução é ótima. Se for, o processo está encerrado. Se não for ótima, é porque um dos pontos

36

Matematicamente o segmento de reta entre X1 e X2 é o conjunto de todas as combinações convexas de X1 e X2. X1 + (1- )X2 X 0 1

extremos adjacentes ao ponto extremo inicialmente adotado fornece para a função objetivo um valor melhor do que o atual. Para melhorar o valor da função objetivo, a mesma deve ser aumentar ou diminuir, conforme o problema seja de maximização ou minimização respectivamente.

O Método Simplex faz então a mudança do ponto inicial para o ponto extremo adjacente que melhore o valor da função objetivo. O procedimento adotado para o ponto extremo inicial é repetido para este segundo ponto extremo. O processo finaliza quando, estando num ponto extremo, todos os pontos extremos a ele adjacentes, fornecem valores piores para a função objetivo.

Algebricamente, um ponto extremo adjacente é uma solução compatível básica incluindo todas as variáveis básicas anteriores, com exceção de apenas uma delas. Achar, portanto, a próxima solução compatível básica (ponto extremo adjacente) exige a escolha de uma variável não-básica para entrar na base em sua substituição.

O Método Simplex compreenderá, portanto, os seguintes passos: 1) Achar uma solução compatível básica inicial.2) Verificar se a solução atual é ótima. Se for, pare. Caso contrário, siga para o passo 3.3) Determinar a variável não básica que deve entrar na base.4) Determinar a variável básica que deve sair da base.5) Achar a nova solução compatível básica, e voltar ao passo 2.

3.2. TEOREMAS FUNDAMENTAIS DO MÉTODO SIMPLEX

O Método Simplex baseia-se em três teoremas fundamentais:Teorema 1: “O conjunto de todas as soluções compatíveis do modelo de programação linear é um conjunto convexo.”

Teorema 2: “Toda solução compatível básica do sistema Ax=b é um ponto extremo do conjunto das soluções compatíveis”

Teorema 3: a) “Se a função objetivo possui um máximo (mínimo) finito, então pelo menos uma solução ótima é um ponto extremo do conjunto convexo.”

b) “Se a função objetivo assume o máximo (mínimo) em mais de um ponto extremo, então ela toma o mesmo valor para qualquer combinação convexa desses pontos extremos.”

3.3- REDUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR À FORMA PADRÃO

Os modelos de programação linear, para serem devidamente solucionados por intermédio do algoritmo simplex que será apresentado, devem apresentar o seguinte formato padrão:

A função objetivo de maximização (opcional); Todas as variáveis de decisão não-negativas; Constantes do lado direito não-negativas; Restrições de igualdade.Caso isso não aconteça, deve-se procurar um modelo equivalente que possua essas

características, para então usar o simplex.a) Função Objetivo de Minimização

37

A minimização de uma função f(x) é matematicamente análoga à maximização da negativa desta função (-f(x)).Exemplo: MIN z=c1x1+ c2x2+...+ cnxn

É equivalente a:MAX Z = -c1x1- c2x2-...-cnxn

Com z = -ZDessa forma: MIN z = -MAX(-Z)

Essa é uma das formas de resolver os problemas de minimização utilizando o mesmo algoritmo dos problemas de maximização. Caso se queira resolver diretamente, devemos alterar o critério de entrada das variáveis na base.

b) Problema da Variável LivreEntende-se por variável livre as variáveis sem qualquer restrição de sinal, isto é, podem assumir valores positivos, negativos ou zero. Para contornarmos este problema, devemos lembrar que um número qualquer sempre pode ser escrito como a diferença de dois números positivos.

Exemplo: MAX z = x1+2x2+x3

SA x1+x2+x310

2x1+3x220

x1 0 , x2 livre , x3 0

Fazendo x2 = x'2 - x''2, com x'2 0 e x''2 0 e substituindo no modelo anterior, tem-se o modelo equivalente:

MAX z = x1+2(x'2 - x''2)+x3

SA x1+ x'2 - x''2+x310

2x1+3(x'2 - x''2)20

x1 0 , x'2 0, x''2 0, x3 0

Onde todas as variáveis são não-negativas. A solução deste modelo, resolve o anterior.

c) Ocorrência de bi<0Basta multiplicarmos a restrição i por (-1) pois os coeficientes a ij podem ter qualquer sinal.

d) Transformação de Desigualdades em Igualdades Para a utilização do algoritmo simplex é necessário que todas as desigualdades do conjunto de restrições sejam transformadas em igualdade e que se conheça uma solução inicial viável, não- negativa. Na forma padrão, apenas as restrições de não-negatividade (das variáveis) são desigualdades.

Variáveis de Folga e ExcessoOutras restrições de desigualdade são transformadas em equações por meio de variáveis de folga ou de excesso (muitas vezes se fala em variáveis de folga mesmo quando se trata de variáveis de excesso) que são sempre não-negativas.

38

ai1x1 + .... + ainxn bi ai1x1 + .... + ainxn + si = bi

si 0 (folga)ou

ai1x1 + .... + ainxn bi ai1x1 + .... + ainxn - si = bi

si 0 (excesso)

A variável de folga é numericamente igual a diferença entre os valores à direita e à esquerda da desigualdade e representa o desperdício acarretado pela parte do sistema modelada pela restrição em pauta.

A variável de excesso é numericamente igual a diferença entre os valores à esquerda e à direita da desigualdade e representa um excesso das variáveis de entrada nesta parte do sistema modelada pela restrição em pauta.

Geração de Solução Inicial ViávelDepois de serem transformadas todas as restrições lineares (com valores não negativos

nos termos à direita das desigualdades) em igualdades, pela introdução das variáveis de folga e de excesso, onde necessário, adiciona-se uma nova variável chamada variável artificial, à esquerda de todas as restrições que não contenham uma variável de folga a fim de formar uma base inicial. Em conseqüência , todas as equações representando as restrições, ou conterão variáveis de folga ou variáveis artificiais. Obtém-se uma solução inicial não negativa para este novo conjunto de restrições, fazendo-se cada variável de folga e cada variável artificial igual ao valor do lado direito da equação, na qual a variável em questão aparece , e igualando-se a zero todas as outras variáveis, inclusive as de excesso.

Custos de Penalização (Coeficiente das Variáveis na Função Objetivo)A introdução de variáveis de folga ou excesso não altera a natureza das restrições e

tampouco a função objetivo. Assim tais variáveis são incorporadas a função objetivo com coeficientes de valor nulo. As variáveis artificiais, contudo, mudam a natureza das restrições. Tendo em vista que estas variáveis são adicionadas a apenas um dos membros de uma igualdade, o novo e o velho sistema de equações representando restrições são equivalentes apenas se , e somente se, as variáveis artificiais tiverem valor zero. A fim de assegurar tal alocação de valores na solução ótima ( em contraste com a solução inicial), as variáveis artificiais são incorporadas à função objetivo ponderadas por coeficientes positivos de valores elevados nos problemas de minimização e por coeficientes negativos de valores elevados nos problemas de maximização. Estes coeficientes designados por M e –M, são subentendidos como grandes números positivos e representam uma penalidade severa em que se incorre ao se fazer a alocação de uma unidade das variáveis artificiais.

Nos cálculos manuais os custos de penalização podem ser traduzidos por M. Em cálculos computacionais deve-se atribuir a M um valor numérico, usualmente um número três a quatro vezes maior em magnitude que qualquer outro existente no programa.

Coeficiente das variáveis artificiais na função objetivo +M (problemas de minimização) -M (problemas de maximização)

RESUMO

39

Restriçãotipo

Ajuste narestrição

Ajuste na Função ObjetivoProblema de Maximização Problema de Minimização

≤ Adicionar uma variável de folga (si)

Adicionar variável de folga (si) com coeficiente 0

Adicionar uma variável de folga (si) com coeficiente 0

= Adicionar uma variável artificial (Ai)

Subtrair variável artificial (Ai) com coeficiente M

Adicionar variável artificial (Ai) com coeficiente M

≥ Subtrair uma variável de excesso (si) e adicionar uma variável artificial (Ai)

Adicionar variável de excesso (si) com coeficiente 0 e subtrair variável artificial (Ai) com coeficiente M

Adicionar variável de excesso (si) com coeficiente 0 e adicionar variável artificial (Ai) com coeficiente M

3.4. FORMA CANÔNICA DE UM SISTEMAO método de Gauss-Jordan é um método numérico para solução de sistemas

lineares que explicita os valores de algumas variáveis em função do termo independente e, possivelmente em função de outras variáveis. Se um sistema, como aquele da forma padrão apresentado, contém equações linearmente independentes e tem m n, podemos a partir de uma base qualquer dada, fazer operações com linhas para obter um sistema equivalente com os coeficientes das variáveis básicas iguais a um. Por exemplo suponhamos que as m primeiras colunas do sistema padrão formam uma base (isto é, as m primeiras colunas são LI), então podemos por o sistema (isto é, obter um sistema equivalente) na forma

_ _ _x1 +a1m+1xm+1 + .... + a1nxn = b1

_ _ _ x2 +a2m+1xm+1 + .... + a2nxn = b2

. : : . _: : _ _ xm +amm+1xm+1 + .... + amnxn = bm

onde as barras denotam novos valores para os coeficientes. O sistema acima é então dito ser o sistema da forma padrão na forma canônica em relação à base formada pelas colunas 1,2,...,m. Note que ao fazer xm+1 ,....., xn iguais a zero obtemos diretamente a solução básica.

3.5. CONCEITOS BÁSICOS DO MÉTODO SIMPLEXVamos apresentar a conceituação básica do Método Simplex através de um pequeno

exemplo.

a) Formulação do Problema

Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente, a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, vamos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são mostradas na tabela a seguir:

RECURSO DISPONIBILIDADEMadeira 12m²

40

Mão-de-obra 8 H.h

O processo de produção é tal que, para fazer 1 mesa a fábrica gasta 2m² de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3m² de madeira e 1 H.h de mão-de-obra.

Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $4, e cada armário, de $1. O problema do fabricante é encontrar o programa de produção que maximiza a margem de contribuição total para o lucro.

Como se trata de um problema extremamente simples, preparado apenas para demonstração dos fundamentos do Método Simplex, podemos resolvê-lo usando apenas algumas considerações qualitativas. Para isso, inicialmente, vamos criar o modelo de programação linear para o problema proposto.

b) Montagem do ModeloComo variáveis de decisão, vamos considerar

quantidade a produzir de mesa: x1

quantidade a produzir de armário: x2

Com essa definição de variáveis, podemos escrever as relações matemáticas que formam o modelo.

Assim, para a função-objetivo, temos:

Margem de contribuição total Z = 4.x1 + 1.x2

Para as restrições,a relação lógica existente é:

Utilização de recurso Disponibilidade de recurso

Assim, temos:

Para madeira: 12

Utilização de madeira Disponibilidadepara os dois produtos de madeira

Para Mão-de-obra: 8

Utilização da mão-de-obra Disponibilidade para os dois produtos de mão-de-obra

41

O modelo completo é:

c) Solução do Modelo Utilizando Raciocínio Lógico

Inicialmente, vamos observar que o conjunto das restrições forma um sistema de desigualdades lineares e, dessa forma, existem infinitas combinações de valores de x1 e x2

que satisfazem as restrições.

Para descobrirmos aquela que produz o maior valor para o objetivo, vamos partir de um par de valores para x1 e x2 e tentar, através de um raciocínio lógico, encontrar um par de valores que fornece um lucro maior.

Como ponto de partida vamos tomar a seguinte combinação

x1 = 0x2 = 0Z = 0

Que é uma solução possível para o problema é fácil verificar. Obviamente não é a melhor, já que o fabricante nada produz. Porém, vamos observar o seguinte:

Cada mesa que produzirmos aumenta o lucro de $4; Cada armário que produzirmos aumenta o lucro de $1.

Como o objetivo é maximizar o lucro, vamos começar a nossa análise pela produção de mesa, mantendo a produção de armário no nível zero. Em termos matemáticos, isso significa que:

x1 deve ser positiva x2 continua igual a zero.

Bem, com a conclusão acima, precisamos saber agora qual o valor que x1 deve tomar.

Novamente, lembrando que nosso objetivo é maximizar o lucro e já que cada mesa produzida aumenta o lucro de $4, é razoável que procuremos dar a x1 o maior valor possível. Para descobrirmos esse valor, vamos voltar às restrições:

42

Achar x1 e x2, de forma a:

MAXIMIZAR Z = 4.x1 + 1.x2

2.x1 + 3.x2 122.x1 + 1.x2 8x1 0 x2 0

Como x2 = 0, e como queremos o maior valor possível para x1, vamos reescrever as restrições somente em termos de x1:

2.x1 = 122.x1 = 8

Assim, se considerarmos apenas o recurso madeira, poderíamos fazer 6 mesas, ou:

Por outro lado, se considerarmos apenas o recurso de mão-de-obra, poderíamos fazer 4 mesas, ou seja:

Como para fazer uma mesa gastam-se simultaneamente os dois recursos, é evidente que o maior valor possível para x1 é 4, já que não teríamos mão-de-obra suficiente para fazermos 6 mesas.

Concluindo, já temos uma segunda programação da produção que dá um lucro melhor que a primeira:

x1 = 4 mesasx2 = 0 armários

O lucro que se obtém com esta produção é:

Z = 4 x 4 + 1 x 0 = 16

A solução é viável, já que as restrições foram respeitadas:2 x 4 + 3 x 0 = 82 x 4 + 1x 0 = 8

Assim, recapitulando, partimos de uma solução viável ( x1 = 0 e x2 = 0) para outra solução (x1 = 4 e x2 = 0), que dá um lucro maior, usando os seguintes critérios:

Começamos a produção pelo produto que mais contribui para o lucro; nesse caso, a variável que se torna positiva é a que tem maior coeficiente em Z.

Escolhido o produto, sua produção foi estabelecida no maior valor possível, ou seja, deu-se à variável o maior valor positivo possível.

A pergunta que se faz necessária agora é a seguinte: Esta solução encontrada é a melhor de todas ou teremos ainda que encontrar outra?

Para responder a essa pergunta, podemos usar os mesmos critérios anteriores, porém com pequena alteração.

Neste exemplo, seria natural que procurássemos produzir armários, já que seu nível de produção é zero e temos ainda madeira sobrando. No entanto, é importante lembrar que toda a mão-de-obra disponível foi alocada à produção de mesas. Como necessitamos de

43

mão-de-obra para produzir armários, a única forma de conseguirmos isso é através da redução do número de mesas a produzir, de maneira a liberarmos recursos. Conseqüentemente, para podermos produzir armários, duas alterações deverão ser feitas no programa de produção:

O número inicialmente encontrado para a produção de mesas deve diminuir. Isso provoca diminuição do lucro total.

A produção de armários, inicialmente nula, poderá então tornar-se positiva. Isso provoca aumento do lucro total.

Ora, já que temos simultaneamente duas alterações no lucro total, uma redução e um aumento, o nosso primeiro critério pode ser adaptado. Nesse caso, a variável x2 (produção de armários) deverá se tornar positiva se o resultado das modificações no lucro total for positivo.

Ou seja, se:

AUMENTO EM Z PROVOCADO EPLO AUMENTO DE x2

– DIMINUIÇÃO EM Z PROVOCADA PELA DIMINUIÇÃO DE x1

CONTRIBUIÇÃO LÍQUIDA PARA O LUCRO DADA POR x2

A modificação no critério é esta: não se faz positiva a variável apenas porque tem um coeficiente positivo na função-objetivo, mas se sua contribuição líquida, calculada pela expressão anterior, for positiva. vamos calcular isso:

Visto que o recurso totalmente alocado é a mão-de-obra, vamos considerar de novo a segunda equação:

2.x1 + 1.x2 = 8Como o primeiro recurso tem folga, não precisamos nos preocupar com a primeira

equação.Para calcularmos a redução que ocorre em x1, para liberar recursos visando a

aumentar a produção de x2, vamos dar a seguinte variação no valor da variável x2:x2 = 0 passa para x2 = 1

Levando na equação acima:2.x1 + 1 x 1 = 8

donde: = 3,5

Logo, um aumento de 1 na variável x2 exige uma redução de 0,5 no valor da variável x1 (4 – 3,5 = 0,5).

A variação do,lucro L pode ser calculada da seguinte forma:

Variação em Z = 4 x (variação em x1) + 1 x (variação em x2)Logo:

Variação em Z = 4 x (–0,5) + 1 x 1 = –1

44

Ou seja, a contribuição líquida para o lucro, por unidade produzida de armário, é –1. Conseqüentemente, nesse nosso exemplo, não é vantajoso produzir armários, e assim a solução ótima encontrada é:

x1 = 4x2 = 0Z = 16

d) Solução do Modelo por Sistema de Equações LinearesPodemos resolver nosso modelo de programação linear por algum método de resolução de equações lineares. O processo que vamos analisar aqui é bastante intuitivo e tem por finalidade, apenas, apresentar a filosofia básica do Método Simplex, que será mostrado a seguir:

a) Introdução das variáveis de folga

Para transformarmos as desigualdades lineares das restrições em equações lineares, de forma que possam ser aplicados os métodos de solução destas últimas, vamos recordar, conforme já vimos anteriormente, que as restrições do problema têm a seguinte estrutura lógica:

Utilização de recurso Disponibilidade de recurso

Se introduzirmos o conceito de FOLGA DE RECURSO, podemos escrever a relação acima da seguinte forma:

UTILIZAÇÃO + FOLGA = DISPONIBILIDADE

Isso significa que:UTILIZAÇÃO < DISPONIBILIDADE Implica FOLGA > 0UTILIZAÇÃO = DISPONIBILIDADE Implica FOLGA = 0

Assim, a folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de cada produto. desse modo, vamos chamar:

x3 = folga de madeirax4 = folga de mão-de-obra

Introduzindo a variável x3 para a primeira desigualdade e x4 para a segunda, temos nosso sistema transformado:

maximizar Z = 4.x1 + 1.x2 + 0.x3 + 0.x4

sujeito a: 2.x1 + 3.x2 + 1.x3 = 12 2.x1 + 1.x2 + + 1.x4 = 8 x1, x2, x3, x4 0

45

Nosso problema se transformou em achar a solução do sistema de equações lineares que maximiza o lucro Z. Como nesse caso o número de incógnitas (n = 4) é superior ao número de equações (m = 2), o sistema de equações é indeterminado, apresentando assim infinitas soluções.

No entanto, como todas as variáveis, incluindo as de folga, devem ser positivas ou nulas, e como, em termos de decisão no problema, atribuir o valor zero a uma variável significa não produzir um dos produtos (se a variável for natural do problema) ou usar toda a disponibilidade de recursos (se a variável for de folga), podemos achar soluções para o sistema de equações dando arbitrariamente valor zero a duas variáveis ( n – m = 4 – 2 = 2) e calculando o valor das outras duas pelo sistema restante;

Temos, dessa forma, que resolver:

sistemas de equações lineares

OBS.: Variando as variáveis feitas zero teremos diferentes soluções básicas. No total teremos:

Uma vez resolvido um sistema, usamos os valores encontrados para as variáveis na função-objetivo, achando assim o lucro L.

As variáveis que tiveram valor atribuído 0 serão chamadas variáveis não-básicas; as variáveis cujos valores foram encontradas pela solução dos sistemas de equações (valores positivos), variáveis básicas e o conjunto das variáveis básicas, base.

b) Solução dos sistemas de equações

1- Variáveis não-básicas: x1 = 0x2 = 0

temos as variáveis básicas:x3 = 12x4 = 8Z = 0

2- Variáveis não-básicas:x1 = 0x3 = 0

temos as variáveis básicas:x2 = 4x4 = 4

dando o lucro: Z = 4

46

3- Variáveis não-básicas:x1 = 0x4 = 0

temos as variáveis básicas: x2 = 8

x3 = –12

Como x3 < 0, a solução obtida é INVIÁVEL.

4- Variáveis não-básicas:x2 = 0x3 = 0

temos as variáveis básicas: x1 = 6x4 = –4

Como x4 < 0, a solução obtida é INVIÁVEL.

5- Variáveis não-básicas:x2 = 0x4 = 0

temos as variáveis básicas:x1 = 4x3 = 4

dando o lucro: Z = 16

6- Variáveis não-básicas:x3 = 0x4 = 0

temos as variáveis básicas:x1 = 3x2 = 2

dando o lucro: Z = 14

Comparando todas as soluções encontradas por esse processo, achamos a mesma solução ótima obtida anteriormente, ou seja:

x1 = 4x2 = 0x3 = 4

x4 = 0 dando um lucro Z = 16

47

Essas seis soluções encontradas podem ser visualizadas em um gráfico, conforme mostra a figura 3.6.As duas soluções inviáveis encontradas (sistemas 3 e 4) correspondem a pontos que se encontram fora da região viável, conforme mostra a figura 3.6.

Sistema 3: 8x1 = 0 X2

x2 = 8 7

6

5Sistema 2:x1 = 0 4x2 = 4

3

2

1

Sistema 1:x1 = 0 0 1 2 3 4 5 6x2 = 0

Sistema 5:x1 = 4x2 = 0

Fig. 3.6. Representação gráfica das soluções obtidas

3.6. DESENVOLVIMENTO DO MÉTODO SIMPLEXA solução algébrica anterior mostrou que a resolução de um problema de

programação linear consiste basicamente em resolver sistemas de equações lineares e calcular o valor da função objetivo. Comparando os diversos valores obtidos para a função objetivo, escolheremos como solução do problema o resultado do sistema de equações que forneceu o maior valor.

Esse procedimento, apesar de correto, é bastante trabalhoso, já que temos de resolver todos os sistemas para podermos escolher o que dá o maior valor para a função objetivo.

Basta um pequeno problema real de programação linear, onde poderíamos ter, por exemplo, 10 equações e 15 variáveis, para inviabilizarmos o processo, já que o número de sistemas de equações que deveríamos resolver seria muito elevado.

Assim, para termos condições de resolver um problema de programação linear, precisamos de uma sistemática que nos diga:

qual o sistema de equações que deve ser resolvido; que o próximo sistema a ser resolvido fornecerá uma solução melhor que os

anteriores;

48

Sistema 6:x1 = 3x2 = 2

Sistema 4:x1 = 6x2 = 0

como identificar uma solução ótima, uma vez que a tenhamos encontrado.

Essa sistemática é o Método Simplex e as regras que o método utiliza para atender às três questões são, basicamente, os critérios que desenvolvemos nos itens anteriores.

Vamos voltar ao nosso pequeno problema, já com as variáveis de folga:

MAX Z= 4x1+ 1x2 + 0x3 + 0x4

S.A. 2x1+ 3x2 + 1x3 = 122x1+ 1x2 + + 1x4 = 8 x1, x2, x3, x4 0

Vamos montar um quadro (tableau) para ordenarmos as operações, colocando nele apenas os coeficientes das variáveis. No caso da função objetivo, vamos realizar a seguinte transformação:de: Z= 4x1+ 1x2

para: -Z + 4x1+ 1x2 = 0

Quadro 1 (Tableau 1)

BASE x1 x2 x3 x4 bi

x3

x4

2 3 1 02 1 0 1

128

-Z 4 1 0 0 0

A última coluna corresponde aos termos independentes das equações, e a última linha contém os coeficientes das variáveis na função objetivo. Nessa última linha teremos sempre a contribuição que cada variável dá para o lucro total Z, por unidade, em cada iteração do processo de solução. Essa última linha será chamada de função objetivo transformada.

Caso se queira reproduzir as equações, basta multiplicar os coeficientes na matriz pelas respectivas variáveis, mostradas acima do quadro.

a)Solução InicialA solução inicial para o problema será sempre obtida fazendo as variáveis originais do

modelo (no caso x1 e x2 ) iguais a zero e achando o valor das demais.Assim, fazendo x1 = x2 =0 (variáveis não-básicas), obtemos do tableau 1 :

x3 =12x4 = 8Z = 0

As variáveis básicas estão indicadas na 1ª coluna do tableau para facilitar o acompanhamento das operações.

b) Segunda solução Como a primeira solução claramente não é a melhor, vamos procurar outra que dê um valor

maior para Z. Para fazermos isso, vamos nos basear no tableau 1, na primeira solução, e aplicar os critérios desenvolvidos no item 5 (Conceitos Básicos do Método Simplex ). Como já foi visto, essa segunda solução também deverá ter duas nulas e duas variáveis positivas. O problema é descobrir:

49

Das duas variáveis básicas(nulas) na primeira solução, qual deverá se tornar positiva? Das duas variáveis básicas (positivas) na primeira solução, qual deverá ser anulada?

Qual variável deverá se tornar positiva?

Vamos observar que na última linha do tableau 1 temos os coeficientes da função objetivo que mostram a contribuição para o lucro Z de cada unidade produzida de mesa (x1) e de armário (x2).

Assim, aplicando o primeiro critério de que devemos produzir primeiro o produto que mais contribui para o lucro, vamos começar a produção pela variável x1, já que sua contribuição unitária para o lucro (4) é maior que a contribuição de x2, igual a (1).

Logo, a variável que deverá se tornar positiva é x1.

Qual variável deverá ser anulada?A resposta a essa pergunta será obtida pela aplicação do 2º critério discutido anteriormente,

onde procuramos descobrir qual o maior valor que podemos atribuir a x1.A partir do Quadro 1, vamos examinar as duas equações, da mesma forma que fizemos

anteriormente, incluindo porém as variáveis de folga.

1ª Equação: 2x1 + 1x3 = 12O maior valor possível para x1 será 6, quando x3 for igual a zero. Observe que um valor maior que esse faria x3 se tornar negativo, o que não é permitido.

2ª Equação: 2x1 + 1x4 = 8O maior valor possível para x1, com base somente nessa equação, será 4, quando x4 for igual a 0.

Analisando simultaneamente as duas equações, percebemos que o maior valor possível para x 1 é 4 e, assim, descobrimos que a variável que se anulará é x4.

Observe que essa análise pode ser feita diretamente no Quadro 1, através da divisão dos elementos da coluna b pelos correspondentes elementos da coluna x1.O menor quociente indica, pela linha em que ocorreu, qual a variável básica que deve ser anulada. Assim, como o menor quociente é dado pela divisão 8/2 =4, a variável básica a ser anulada é x4, que é a variável positiva na atual solução, cujo valor foi encontrado na 2ª linha.

Assim temos: x2 =0x4 = 0

e o sistema restante deve ser resolvido para acharmos o valor de x1 e x3 . A solução desse sistema será feita utilizando o tableau 1 com as equações completas e usando as operações válidas com as linhas da matriz.

1ª operação: dividir a 2ª linha por 2

Tableau 2

BASE x1 x2 x3 x4 bi

x3

x1

2 3 1 01 1/2 0 1/2

124

50

-Z 4 1 0 0 0

2ª operação: multiplicar a 2ª linha nova do tableau 2 por -2 e somar com a 1ª linha do mesmo quadro, colocando o resultado na 1ªlinha.Tableau 3 BASE x1 x2 x3 x4 bi

x3

x1

0 2 1 -11 1/2 0 1/2

44

-Z 4 1 0 0 0

3ª operação: Vamos fazer o mesmo procedimento com a 3ªlinha, de forma a atualizar as contribuições que cada variável não-básica daria para o lucro, caso viesse a se tornar básica. Para isso, vamos multiplicar a 2ª linha do tableau3 por -4 e somar com a 3ªlinha, substituindo esta pelo resultado obtido. Tableau 4 BASE x1 x2 x3 x4 bi

x3

x1

0 2 1 -11 1/2 0 1/2

44

-Z 0 -1 0 -2 -16

Como a última linha (função objetivo transformada) mostra as contribuições líquidas para o Z, caso as variáveis x2 e x4 venham a ter seus valores aumentados de 0 para 1 e como estas contribuições têm seus valores com sinais trocados com relação ao quadro original, concluímos que a solução encontrada

x1 =4 x2 = 0 x3 = 4 x4 = 0

e Z=16 (valor da última linha e última coluna com sinal trocado)

é a solução ótima.3.7- PROCEDIMENTO DO MÉTODO SIMPLEX:

Passo1: Transformar o modelo na forma padrão;Passo 2: Montar um quadro (tableau) para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientes da função objetivo transformada;Passo 3: Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais e achando valores positivos para as variáveis de folga.Passo 4: Localize o número mais negativo (se o problema for de MIN) ou o número mais positivo (se o problema for de MAX) da última linha do quadro simplex, excluída a última coluna, e chame a coluna em que este número aparece de coluna de trabalho. Se existir mais de um candidato a número mais negativo (MIN) ou mais positivo (MAX), escolha um;Passo 5: Forme o quociente da divisão de cada elemento da última coluna pelo número positivo correspondente da coluna de trabalho que está na mesma linha (excluindo-se a

51

última linha do quadro). Sai da base a variável que corresponder a menor razão dentre àquelas encontradas.Passo 6: Use operações elementares sobre as linhas a fim de converter o elemento pivô em 1 e, em seguida, reduzir a zero todos os outros elementos da coluna de trabalho;Passo 7: Substitua a variável x existente na linha pivô e primeira coluna pela variável x da primeira linha e coluna pivô. Esta nova primeira coluna é o novo conjunto de variáveis básicas;Passo 8: Repita os passos 4 a 7 até a inexistência de números negativos(problemas de MIN) ou números positivos (problemas de MAX) na última linha, excluindo-se desta apreciação a última coluna;Passo 9: A solução ótima é obtida atribuindo-se a cada variável da primeira coluna o valor da linha correspondente, na última coluna. Às demais variáveis é atribuído o valor zero. O valor ótimo da função objetivo, associado a z, é o negativo do número resultante na última linha, última coluna.

Idéia geral do método:a) Os coeficientes das variáveis não básicas na linha da FO(custos reduzidos) são

necessários para selecionar a variável a entrar na base ou constatar a otimalidade do “tableau”.

b) Os termos independentes são necessários na seleção da variável a sair da base de modo a evitar que a nova base seja infactível e também ao final do método já que são os valores das variáveis básicas.

c) Os coeficientes da coluna a entrar na base, servirão na seleção da variável a deixar a base e também necessários na determinação das operações de linhas que constituirão o pivotamento.

3.8- ANÁLISE DAS SOLUÇÕES

a)Problema de DegeneraçãoNo desenvolvimento do Simplex, a linha pivô é a restrição que apresenta o menor

quociente não negativo, na divisão dos termos independentes pelos coeficientes positivos da variável que entra.

Pode ocorrer que haja mais de um resultado nessas condições. Devemos escolher arbitrariamente um deles para calcular a solução. Entretanto, essa solução apresentará variáveis básicas com valor nulo. A saída de uma variável básica nula provoca o aparecimento de outra variável básica nula na solução seguinte, sem alteração do valor do objetivo.

Neste caso, a solução é chamada degenerada. Se os coeficientes da função objetivo retornam negativos em alguma iteração, o caso não apresenta dificuldade. O problema aparece quando as iterações levam a circuitos, sem caracterizas a solução ótima. Embora o caso seja muito raro, há maneiras de soluciona-lo. Entretanto, ao nível desta exposição esse método não tem interesse.

Chamaremos de solução básica factível qualquer solução básica cujo valor das variáveis sejam não-negativas.

b)Problema da Solução Ilimitada

52

Quando a variável que entra na base não possui em sua coluna nenhum coeficiente positivo o problema possui solução ilimitada. Os programas de computador, neste caso, apresentam a última solução básica antes que a solução se torne ilimitada.

c)Caso de Soluções MúltiplasSe na solução ótima o coeficiente de uma variável não básica é zero, ele poderá

entrar na base sem alterar o valor do objetivo, gerando outra solução ótima. Neste caso, qualquer combinação linear dessas duas soluções também será solução ótima. Neste caso teremos soluções múltiplas.

3.9- ANÁLISE ECONÔMICAA análise econômica baseia-se nos coeficientes das variáveis, na função objetivo

final. Vamos lembrar que:1. O quadro final de um modelo de programação linear apresenta variáveis básicas e

não básicas.2. A função objetivo está escrita em termos das variáveis não básicas.3. O valor das variáveis básicas estão na coluna b. O valor das variáveis não-básicas é

zero.4. O coeficiente da variável não básica na função objetivo mede a tendência do

objetivo com aquela variável. È um valor marginal, indica a variação proporcional no objetivo para pequenos aumentos ou diminuições na variável. Para simplificar o raciocínio, vamos supor sempre aumentos ou diminuições unitárias na variável.Posteriormente, em análise de sensibilidade podemos verificar até quantas unidades podemos aumentar ou diminuir da variável, sem alterar a informação contida em seu coeficiente. Esses coeficientes são chamados preços de oportunidade (preços relativos ao programa desenvolvido).

5. No quadro final, a solução é ótima. Um aumento de zero para 1 na variável não básica prejudica o objetivo. (lucros diminuem, custos aumentam, etc.).

Para fazermos a análise econômica do último exemplo trabalhado, vamos interpretar os coeficientes das variáveis fora da base (no caso os coeficientes de x2 e x4) e os coeficientes da última linha do Tableau final.

Análise para x4:Como x4 está fora da base, seu valor na solução ótima é zero. Vamos passar seu valor

para 1 e calcular as variações que devem ocorrer nas variáveis básicas.a) Cálculo da variação em x3:A relação entre x4 e x3 aparece na primeira equação do Tableau final:

x3 - x4 = 4Com x4 = 1, temos: x3 = 4 + 1 ou x3

novo = 5 A variação em x3 é:

Δ x3 = x3novo - x3 = 5-4= 1

Δ x3 =1

b) Cálculo da variação em x1: A relação entre x1 e x4 aparece na segunda equação do Tableau final:

53

x1 + ½ x4 = 4Com x4 = 1, temos: x1 = 4 – ½ .1 ou x1

novo = 3,5 A variação em x1 é:

Δ x1 = x1novo – x1 = 3,5 - 4= -1/2

Δ x1 = -1/2

c) Cálculo da variação em Z:Z = 4x1 + 1x2

Δ Z = 4.( Δ x1)+1(Δ x2) = 4(-1/2 )+ 0Δ Z = -2

Resumindo, temos:Para Δx4 = 1, encontramos: Δx3= 1

Δx1= -1/2Δ Z = -2

Comparando os valores acima com os coeficientes de x4 no Tableau final do Método Simplex, podemos concluir:1. As variações nos valores das variáveis básicas podem ser obtidas diretamente do

Tableau tomando-se os coeficientes da variável não-básica em teste, com os sinais trocados.

2. A variação no valor da FO é o valor obtido na linha (-Z) correspondente à variável não-básica em teste.

Análise para x2:

Com essas duas regras, podemos obter diretamente as variações na solução básica para uma variação unitária de x2.

Para Δx2 = 1, encontramos: Δx3= -2Δx1= -1/2Δ Z = -1

Δ Z = 4.( Δ x1)+1(Δ x2) = 4(-1/2 )+ 1(1) = -2+1 = -1Δ Z = -1

Resumindo:a) Se aumentarmos x4 em uma unidade, ou seja, se diminuirmos em uma unidade a

disponibilidade do recurso mão-de-obra, podemos concluir que:1. As variações nos valores das variáveis básicas podem ser obtidas

diretamente do quadro, tomando-se os coeficientes da variável não-básica em teste, com os sinais trocados.

2. A variação no valor da função objetivo é o valor obtido na última linha do tableau, correspondente à variável não-básica em teste.

b) Se diminuirmos x4 em uma unidade, ou seja, se aumentarmos em uma unidade a disponibilidade do recurso mão-de-obra, podemos concluir que:

54

1. As variações nos valores das variáveis básicas podem ser obtidas diretamente do quadro, tomando-se os coeficientes da variável não-básica em teste, sem troca dos sinais.

2. A variação no valor da função objetivo é o valor obtido na última linha do tableau, correspondente à variável não-básica em teste, com o sinal trocado.

Interpretação Econômica dos Resultados

A solução ótima do problema representa um plano de produção da mesa e do armário:

x1 = 4 Significa que deve ser produzida 4 unidades de mesa;x2 = 0 Significa que não deve ser produzida nenhuma unidade de armário.Esse plano de produção dará uma margem de contribuição total de Z = R$ 16,00

A utilização dos recursos está programada da seguinte forma:Madeira: x3 = 4 Significa que há uma sobra de 4m2 de madeira;Mão-de-obra: x4 = 0 Significa utilização total do recurso mão-de-obra disponível, já que a sobra desse recurso é zero(não tem sobra no recurso mão-de-obra);

Interpretação dos coeficientes de x2:Passando o valor de x2 de 0 para 1, estamos dizendo que vamos aumentar o nível de produção do armário em uma unidade e isso implicará nos seguintes resultados:a) Δx3 = -2 Significa que a sobra do recurso madeira cai de 2 unidades, ou seja, se

eu fabricar uma unidade do armário, em vez de sobrar 4m2 de madeira, sobrará apenas 2m2 desse recurso;

b) Δx1 = -1/2 Significa que o nível de produção da mesa cai de ½ unidade;c) ΔZ = -1 Como resultado dessas variações nos níveis de produção dos dois

produtos (mesa e armário), obtivemos uma variação de -1 no valor da função objetivo, isto é, a margem de contribuição total para o lucro cai de R$ 16,00 para R$15,00.

Interpretação dos coeficientes de x4:Passando o valor de x4 de 0 para 1, estamos impondo uma sobra de 1 unidade no recurso mão-de-obra ou reduzindo a sua disponibilidade original de 8 unidades para 7 unidade. Como resultado, obtivemos o seguinte::a) Δx3 = 1 Significa que a sobra do recurso madeira aumenta de 1 unidades, ou seja,

passa de 4m2 para 5m2;b) Δx1 = -1/2 Significa que o nível de produção da mesa cai de ½ unidade;c) ΔZ = -2 Como resultado dessas variações nos níveis de produção da mesa,

obtivemos uma variação de -2 no valor da função objetivo, isto é, a margem de contribuição total para o lucro cai de R$ 16,00 para R$ 14,00.

Conclusões:Comparando os dois valores para a variação de Z (-1 e -2), percebemos que entre

passar a fabricar um unidade do armário e reduzir em uma unidade a disponibilidade do recurso mão-de-obra, é melhor passar a fabricar uma unidade do armário, pois causa uma queda menor no valor da função objetivo.

55

O recurso madeira, por exemplo, por apresentar folga na solução ótima, não causa qualquer variação no valor da FO, quando tem sua disponibilidade reduzida em 1 unidade.

Os valores na última linha do quadro simplex, devido aos significados mostrados acima, são chamados preços de oportunidade ou custo reduzido.

A pergunta que se deve fazer, nesse ponto de nossa análise é a seguinte: “ Até que valor podemos aumentar ou diminuir a disponibilidade de cada recurso?”

Observe que, em qualquer dos dois casos, algumas variáveis sofrem um aumento e outras sofrem uma redução. O limite para a variação na disponibilidade de um recurso é o momento em que uma variável atinge o valor zero, já que não podemos ter variáveis negativas na solução do nosso problema. Esta variável sairia da base, exigindo o cálculo de nova solução. Um estudo completo nesse sentido será feito em Análise de Sensibilidade.

Exemplo 2:No programa de produção para o próximo período, a empresa Beta Ltda., escolheu

três produtos P1, P2 e P3. O quadro abaixo mostra os montantes solicitados por unidade na produção.Produto Contribuição

(lucro por unidade)Horas de Trabalho Horas de uso de

máquinasDemanda máxima

P1P2P3

2.1001.200600

646

1262

800600600

Os preços de venda foram fixados por decisão política e as demandas foram estimadas tendo em vista esses preços. A firma pode obter um suprimento de 4.800 horas de trabalho durante o período de processamento e pressupõe-se usar três máquinas que podem prover 7.200 horas de trabalho. Estabelecer um programa ótimo de produção para o período.Solução:

Modelo Linear:Variáveis de decisão: x1 quantidade a produzir de P1

x2 quantidade a produzir de P2x3 quantidade a produzir de P3

Objetivo maximizar o lucro = 2100x1 + 1200x2 + 600x3

Sujeito às restrições:6x1 + 4x2 + 6x3 ≤ 480012x1 + 6x2 + 2x3 ≤ 7200x1 ≤ 800x2 ≤ 600x3 ≤ 600x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Forma Padrão:Max Z= 2100x1 + 1200x2 + 600x3

6x1 + 4x2 + 6x3 +x4 = 480012x1 + 6x2 + 2x3 + x5 = 7200x1 + x6 = 800x2 + x7 = 600

56

x3 + x8= 600

Variáveis de folga:x4 sobra de recurso horas de trabalhox5 sobra de recurso horas de máquinax6 sobra de recurso mercado de P1x7 sobra de recurso mercado de P2x8 sobra de recurso mercado de P3

O quadro final pelo método Simplex é o seguinte:

Base x1 x2 x3 x4 x5 x6 x7 x8 bi

x3

x1

x6

x2

x8

01000

00010

10000

0,2-0,0330,033

00,2

-0,10,1-0,1

00,1

00100

-0,2-0,470,47

10,2

00001

120280520600480

-Z 0 0 0 -50 -150 0 -100 0 -1.380.000

Solução:Produzir no período:280 unidades de P1600 unidades de P2120 unidades de P3

Recursos disponíveis após o programa:520 unidades do mercado de P1480 unidades do mercado de P3

O preço de oportunidade do recurso “horas de trabalho” (coeficiente de x4 no quadro = 50) indica que:- Se conseguirmos mais uma hora de trabalho aos custos correntes poderemos aumentar nosso lucro em 50, isto é, poderemos obter nova solução ótima com lucro de 1.380.050.- Se uma hora a mais de trabalho acarreta o pagamento de adicional extra, o valor 50 indica o limite máximo desse adicional.Por exemplo: se o adicional for de 20, a nova hora de trabalho implicará uma nova solução com lucro de 30 a mais que o anterior, portanto o lucro de 1.380.030.- Se houver falta de uma hora de trabalho, o lucro fica diminuído em 50, caso não haja alteração no custo. Se essa falta for, por exemplo, pela ausência de um funcionário que não terá hora descontada, acrescentar esse valor ao prejuízo causado pela ausência do funcionário.

O preço de oportunidade do recurso “horas de máquina” (coeficiente de x5 no quadro = 150) indica que:

57

- Uma hora a menos de máquina, o que equivale a fazer x5 = 1, acarreta uma diminuição no lucro de 150. A nova solução ótima nesse caso teria lucro de 1.379.850 desde que não haja alteração nos custos correntes.- Contratar mais de uma hora de máquina aos custos correntes significa um acréscimo de 150 no lucro. Se esse contrato implica adicional extra, ele deve ser descontado. No caso de aluguel de hora máquina de terceiros para o programa, o preço de oportunidade 150 indica o máximo que podemos pagar pelo aluguel além de nosso custo corrente. - Em termos de manutenção e substituição de máquinas, o preço de oportunidade oferece informação para o cálculo do prejuízo devido à quebra e manutenção de uma máquina operando no programa. Se há uma probabilidade de 80% de que uma máquina necessite de uma hora para conserto durante o programa, então, há uma expectativa de: 150 x 0,8 = 120 de prejuízo com esse evento (quebra de máquina) no programa, além dos custos pela manutenção.

O preço de oportunidade do recurso “mercado de P1” (coeficiente x6 no quadro=0) indica que esse recurso não é escasso. O mesmo ocorre com o preço de oportunidade do recurso “mercado de P3”. Isto pode nos levar a rever o investimento no mercado desses dois produtos. Uma diminuição desses investimentos com conseqüente diminuição do mercado não afetará nossas vendas, causando um aumento no lucro. Outra maneira de aumentar o lucro neste caso é aumentar o preço de venda dos produtos P1 e P3. isto diminui os mercados correspondentes sem afetar as vendas, desde que o mercado não diminua aquém da produção.

O preço de oportunidade de uma unidade do recurso “mercado de P2” (coeficiente de x7 no quadro = 100) indica que:

- O aumento de uma unidade nesse mercado, aos custos correntes, acarreta um aumento de 100 no lucro, isto é, a nova solução teria lucro de 1.380.100.- Da mesma forma, o cancelamento de uma unidade na compra de um cliente implica um prejuízo de 100, além do custo normal da unidade desse recurso.- Se o departamento de marketing da empresa estimar em 80 o investimento adicional para aumentar em uma unidade o mercado do produto P2, esse investimento nos traria um retorno líquido de 100-80 = 20, passando o lucro para 1.380.020. Por investimento adicional entendemos o valor além do custo normal de vendas por unidade nesse mercado.

As análises efetuadas nos exemplos apresentados mostram o grau de sua relevância para a tomada de decisão. A PO constitui uma grande aliada do tomador de decisão, se bem utilizada e interpretada. Os modelos e seus resultados podem ser utilizados como ferramentas consistentes para a avaliação e divulgação de diferentes políticas empresariais.

3.10- MÉTODO DO M GRANDESeja o exemplo a seguir

MAX z = x1+x2+x3

SA 2x1+x2-x310

x1+x2+2x320

58

2x1+x2+3x3=60

x1 0 , x20 , x3 0

Forma Padrão:

-z + x1 + x2 + x3 + 0x4 - 0x5 - M6 x6 - M7 x7 = 0

2x1 + x2 - x3 + x4 = 10

x1 + x2 + 2x3 -x5 + x6 = 20

2x1 + x2 + 3x3 +x7= 60

A medida que Z é maximizada, as variáveis artificiais x6 e x7 deixam a base, devido ao grande valor de M6 e M7.

O quadro inicial fica então:

BASE x1 x2 x3 x4 x5 x6 x7 bi

x4 2 1 -1 1 0 0 0 10x6

x7

1 1 2 0 -1 1 02 1 3 0 0 0 1

2060

-Z 1 1 1 0 0 -M6 -M7 0

Na primeira fase da solução, a finalidade não será maximizar o objetivo, e sim eliminar as variáveis artificiais x6 e x7, retornando assim ao problema original. Podemos escolher para entrar na base uma variável com qualquer coeficiente na função objetivo, desde que a entrada dessa variável provoque a saída de uma variável artificial.

Para isto basta verificar se na divisão dos termos independentes pelos coeficientes de uma variável não básica, o menor resultado positivo está na linha da variável artificial básica. Se isso é verdade, a variável artificial deixa a base, independente do coeficiente na função objetivo da variável que entra. Caso nenhuma das variáveis não básicas possa fazer o papel de expulsar a variável artificial da base, o problema não tem solução básica, e portanto não tem solução.

OBS: Mesmo que no quadro inicial os coeficientes na função objetivo sejam todos negativos ou nulos (problema de maximização), a solução não é ótima, pois o problema original estará alterado pela presença da variável artificial.

O quadro final fica então:

BASE x1 x2 x3 x4 x5 bi

x2 2 1 0 0,75 0 22,5x3

x5

0 0 1 -0,25 0 1 0 0 0,25 1

12,527,5

-Z -1 0 0 -0,5 0 -35

Solução ótima: Z= 35 x2=22,5 x3=12,5 x5=27,5 x1=x4=0

59

3.11- MÉTODO DAS DUAS FASESConsideremos o mesmo exemplo do item anterior:

MAX z = x1+x2+x3

SA 2x1+x2-x310

x1+x2+2x320

2x1+x2+3x3=60

x1 0 , x20 , x3 0

Forma Padrão:

2x1 + x2 - x3 + x4 = 10

x1 + x2 + 2x3 -x5 + x6 = 20

2x1 + x2 + 3x3 +x7= 60

Passo1: Para iniciarmos este método, temos que construir uma função objetivo artificial W, formada pela soma das variáveis auxiliares.

W= x6 + x7

Passo 2: A função W deve ser escrita em termos das variáveis originais e comporá o novo objetivo a ser minimizado.

x6 = -x1 - x2 - 2x3 +x5 + 20

x7 = - 2x1 - x2 - 3x3 + 60

MIN W = -3x1 - 2x2 - 5x3 +x5 + 80

Função objetivo transformada: -W-3x1 - 2x2 - 5x3 +x5 = -80

Passo 3: Monta-se o quadro de solução de forma exatamente igual à sistemática do método simplex, colocando-se a função objetivo artificial na última linha.

O quadro inicial fica então:

BASE x1 x2 x3 x4 x5 x6 x7 bi

x4 2 1 -1 1 0 0 0 10x6

x7

1 1 2 0 -1 1 02 1 3 0 0 0 1

2060

-Z 1 1 1 0 0 0 0 0-W -3 -2 -5 0 1 0 0 -80

Passo 4: Aplica-se o método simplex normalmente, usando como função objetivo a ser minimizada a última linha. Quando a solução ótima for atingida, dois casos podem ocorrer:

60

1) W = 0: neste caso foi obtida uma solução básica do problema original e o processo de solução deve continuar, desprezando-se as variáveis artificiais e os elementos da última linha. É o início da fase 2 do processo.

2) W 0: neste caso o problema original não tem solução viável, o que significa que as restrições devem ser inconsistentes.

Fase 1: Minimizar WQuadro finalBASE x1 x2 x3 x4 x5 x6 x7 bi

x1 1 1/2 0 3/8 0 0 1/8 45/4x3

x5

0 0 1 -1/4 0 0 1/40 -1/2 0 -1/8 1 -1 5/8

25/265/4

-Z 0 1/2 0 -1/8 0 0 -3/8 -95/4-W 0 0 0 0 0 21/5 1 0

Fase 2: Maximizar ZQuadro inicial BASE x1 x2 x3 x4 x5 bi

x1 1 1/2 0 3/8 0 45/4x3

x5

0 0 1 -1/4 0 0 -1/2 0 -1/8 1

25/265/4

-Z 0 1/2 0 -1/8 0 -95/4

Passo 5: Aplica-se o método simplex normalmente no quadro inicial da fase 2 para maximizar Z.Quadro finalBASE x1 x2 x3 x4 x5 bi

x2 2 1 0 0,75 0 22,5x3

x5

0 0 1 -0,25 0 1 0 0 0,25 1

12,527,5

-Z -1 0 0 -0,5 0 -35

Solução ótima: Z= 35 x2=22,5 x3=12,5 x5=27,5 x1=x4=0

Capítulo IVDUALIDADE

4.1- INTRODUÇÃO

61

Todo problema de Programação Linear, a que chamaremos “Primal”, possui um segundo problema associado chamado “Dual”; ambos são completamente inter-relacionados, de forma que a solução ótima de um fornece informações completas sobre o outro.

A Teoria da Dualidade encontra hoje importantes aplicações no desenvolvimento de métodos computacionais para a resolução de problemas de programação matemática e, também, para interpretações físicas e econômicas de problemas reais.

Problemas duais podem resultar da interpretação de alguma situação sob pontos de vistas opostos. Como exemplo introdutório ao estudo da dualidade, pode-se mencionar a situação de um carpinteiro.

4.2- ESTUDO DA DUALIDADE

Suponha que um carpinteiro fabrique apenas mesas e cadeiras, ambos de um só modelo, e que a quantidade usada de cada recurso para fabricação de cada produto, bem como a disponibilidade desse recurso e o preço de venda dos produtos fabricados, segue a tabela abaixo:Recurso Mesa Cadeira DisponibilidadeMadeira 7 m2 4 m2 60 m2

Mão-de-obra 3 H.h 5 H.h 40 H.hPreço de Venda 1.000,00 500,00 O carpinteiro deseja saber qual o plano de produção que maximiza o rendimento obtido com as vendas.

Este problema é descrito matematicamente pelo seguinte modelo linear:Max Z = 1000x1 + 500x2 (receita total)S.A. 3x1 + 5x2 ≤ 40 (Mão-de-obra disponível)

7x1 + 4x2 ≤ 60 (Madeira disponível)x1 , x2 ≥ 0 (Quantidade de mesas e cadeiras)

Podemos analisar este mesmo problema de outro ângulo: Vamos supor que este carpinteiro deseje saber qual o preço mínimo que pode ser

atribuído aos recursos (horas de trabalho e madeira) que lhe pertencem, ou seja, ele quer saber qual o preço intrínseco de seus recursos.

Para se estabelecer o preço, o carpinteiro poderia fazer a seguinte pergunta: “Quais os preços mínimos que, se o mercado desse para a minha mão-deo-bra e para minha madeira, me fazem ficar indiferente entre vender esses recursos ou usá-los para fazer e vender mesas e cadeiras? Se o mercado desse preços altos aos recursos certamente o carpinteiro os venderia, pois seria mais interessante vender e lucrar com os recursos do que fazer e vender mesas e cadeiras. Mas se o mercado desse preços tão baixos aos recursos e o carpinteiro pudesse lucrar mais fazendo e vendendo mesas e cadeiras, ele certamente não venderia seus recursos.

Esta segunda visão do problema do carpinteiro é descrito matematicamente pelo seguinte modelo:

Primeiro, o mercado deverá oferecer o mínimo pelo total de recursos do carpinteiro. Chamando de y1 o preço dado por 1 H.h de mão-de-obra e de y2 o preço dado por 1 m2 de madeira, tem-se a seguinte F.O.:

Min W = 40y1 + 60y2 (preço total dado aos recursos)

62

Segundo, o mercado não poderá oferecer preços tão baixos, pois o carpinteiro não venderia seus recursos, assim, o mercado deve oferecer preços tais que o valor dos recursos não sejam inferior ao preço de venda, então tem-se as seguintes restrições:

S.A. 3y1 + 7y2 ≥ 1000 (mesa)5y1 + 4y2 ≥ 500 (cadeira)

Finalmente os preços não devem ser negativos pois as condições acima perderiam o significado.

Resumindo temos:Min W = 40y1 + 60y2 (preço total dado aos recursos)S.A. 3y1 + 7y2 ≥ 1000 (mesa)

5y1 + 4y2 ≥ 500 (cadeira)y1 , y2 ≥ 0

Observe que o problema de determinação de preços é formado a partir do problema de alocação de recursos e vice-versa, mediante as seguinte regras:

1. Cada restrição, em um problema, corresponde a uma variável no outro (a i-ésima linha de coeficientes tecnológicos em um problema, corresponde a i-ésima coluna de coeficientes tecnológicos do outro problema);

2. Os elementos do lado direito das restrições (termos independentes) em um problema, são os coeficientes da F.O. do outro problema;

3. Se o objetivo de um problema é maximizar, o do outro será minimizar, e vice-versa;

4. O problema de maximização tem restrições com sentido “≤”, e o problema de minimização tem restrições com sentido “≥”; caso essas condições não ocorram, podemos multiplicar a restrição cujo sinal está trocado por “-1” e obter a restrição com o sinal adequado;

5. As variáveis de ambos os problemas são não-negativas.Pela dualidade de visão que esses problemas representam e pela simetria da formação, eles são denominados Par Primal-Dual Simétrico.

Exemplo:Primal: Max Z = 2x1 + 3x2 + x3 Variáveis Duais Associadas:

S.A. 3x1 + 4x2 + 2x3 ≤ 10 y1

2x1 + 6x2 + x3 ≤ 20 y2

x1 – x2 – x3 ≤ 30 y3

x1 , x2 , x3 ≥ 0

Dual: Min W = 10y1 + 20y2 + 30y3

S.A. 3y1 + 2y2 + y3 ≥ 2 4y1 + 6y2 – y3 ≥ 3 2y1 + y2 – y3 ≥ 1y1 , y2 , y3 ≥ 0

63

Observe que o dual, obtido a partir de um dual, retorna ao primal.A partir dessa definição, são verdadeiras as seguintes propriedades:

1. Se uma restrição primal é do tipo “=”, a variável dual correspondente será sem restrição de sinal;

2. Se a variável primal for sem restrição de sinal, a restrição do dual correspondente será do tipo “=”.

Exemplo: Primal: Max Z = 2x1 + 3x2 + x3 Variáveis Duais Associadas:

S.A. x1 + x2 ≤ 10 y1

2x1 + 4x2 - x3 = 20 y2

x1 , x2 , x3 ≥ 0

Dual: Min W = 10y1 + 20y2

S.A. y1 + 2y2 ≥ 2 y1 + 4y2 ≥ 3 - y2 ≥ 1y1≥ 0 y2 irrestrita

Para sabermos como a solução ótima de um primal pode fornecer informações sobre o seu dual e vice-versa, precisamos conhecer as relações existentes entre as soluções dos dois problemas. As principais relações existentes são apresentadas a seguir.

1. Propriedade Fraca da Dualidade“Se (x1 , x2 ,..., xn ) é uma solução viável para o primal (problema de maximização) e (y1 , y2 ,..., ym ), uma solução viável para o dual (problema de minimização), então, o valor que a solução do primal dá a sua FO não pode ser maior do que o valor que a solução do dual dá a sua FO”. (Z ≤ W).

2. Teorema da Dualidade“Se existe uma solução ótima para o problema primal ou para seu dual, então o outro problema tem uma solução ótima e as duas funções objetivo apresentam o mesmo valor ótimo.” (Max Z = Min W)Em tais situações temos que: a) os valores das variáveis de decisão do primal são encontradas na última linha do

último quadro simplex para o dual, nas colunas associadas às variáveis de folga e às variáveis de excesso (pegar os valores absolutos de tais posições).

b) Os valores das variáveis de folga e de excesso do primal são encontrados na última linha do último quadro simplex para o dual, nas colunas associadas às variáveis de decisão (pegar os valores absolutos de tais posições).

Como o primal é dual do próprio dual, vale o mesmo raciocínio para acharmos a solução do dual a partir da solução ótima do primal.

3. Propriedade da Ilimitação“Se um problema tem solução viável, mas o ótimo é ilimitado, então seu dual não admite solução viável”.

4. Propriedade de Folga Complementar

64

“Dada uma solução ótima do primal e uma do seu dual, sempre que uma folga ocorre na p-ésima restrição de um dos problemas, a p-ésima variável do outro problema é zero e, reciprocamente, se a q-ésima variável de uma solução ótima de um dos problemas é positiva, a q-ésima restrição do outro é satisfeita com folga zero”

Para se enxergar mais claramente as relações apresentadas vamos resolver o primal e o dual do problema do carpinteiro.

Solução do PRIMAL Max Z = 1000x1 + 500x2 (receita total)

S.A. 3x1 + 5x2 ≤ 40 (Mão-de-obra disponível)7x1 + 4x2 ≤ 60 (Madeira disponível)x1 , x2 ≥ 0 (Quantidade de mesas e cadeiras)

Forma Padrão:Max Z = 1000x1 + 500x2 + 0x3 + 0x4

S.A. 3x1 + 5x2 + x3 = 40 7x1 + 4x2 + x4 =60

x1 , x2 , x3 , x4 ≥ 0 FO transformada: -Z +1000x1 + 500x2 + 0x3 + 0x4 = 0

Tableau Inicial – Tableau 1BASE x1 x2 x3 x4 bi

x3 3 5 1 0 40x4

-Z7 4 0 1

1000 500 0 0

60

0

Tableau Final - Tableau 2BASE x1 x2 x3 x4 bi

x3 0 23/7 1 -3/7 100/7x1

-Z1 4/7 0 1/7

0 -500/7 0 -1000/7

60/7

-60000/7

Vamos identificar no Tableau Final a solução do dual conforme explicado. Variáveis de decisão do primal Variáveis de folga do primal

BASE x1 x2 x3 x4 bi

x3 0 23/7 1 -3/7 100/7x1 1 4/7 0 1/7 60/7

65

Solução ótima do primal: Z= 60000/7 x1=60/7 x2=0 x3=100/7 x4=0Solução ótima do dual:W=60000/7 y1=0 y2=1000/7 y3=0 y4=500/7

-Z0 -500/7 0 -1000/7 -60000/7

y3 y4 y1 y2 W Valor da FO do dual

valor das variáveis de decisão do problema dual valor das variáveis de excesso (considerar o valor absoluto)do problema dual (considerar o valor absoluto)

Solução do DUAL Min W = 40y1 + 60y2 (preço total dado aos recursos)

S.A. 3y1 + 7y2 ≥ 1000 (mesa)5y1 + 4y2 ≥ 500 (cadeira)y1 , y2 ≥ 0

Forma padrão:Min W = 40y1 + 60y2 - 0y3 - 0y4 + M5 y5 + M6 y6

S.A. 3y1 + 7y2 - y3 + y5 = 10005y1 + 4y2 - y4 + y6 = 500 y1 , y2 , y3 , y4 , y5 , y6 ≥ 0

Tableau InicialBase y1 y2 y3 y4 y5 y6 bi

y5 3 7 -1 0 1 0 1000y6 5 4 0 -1 0 1 500-W 40 60 0 0 M5 M6 0

Aplicando o Método do M Grande a fim de eliminar as variáveis artificiais e aplicando o Método Simplex, obtemos o seguinte Tableau Final com a solução ótima do Dual.

Tableau FinalBase y1 y2 y3 y4 bi

y4 -23/7 0 -4/7 1 500/7y2 3/7 1 -1/7 0 1000/7-W 100/7 0 60/7 0 -60000/7

Vamos identificar no Tableau Final a solução do pirmal conforme explicado.

Variáveis de decisão do dual Variáveis de excesso do dual

BASE y1 y2 y3 y4 bi

y4 -23/7 0 -4/7 1 500/7y2 3/7 1 -1/7 0 1000/7

66

Solução ótima do primal: Z= 60000/7 x1=60/7 x2=0 x3=100/7 x4=0Solução ótima do dual:W=60000/7 y1=0 y2=1000/7 y3=0 y4=500/7

-W100/7 0 60/70 0 -60000/7

x3 x4 x1 x2 Z Valor da FO do primal

valor das variáveis de decisão do problema primal valor das variáveis de folga do problema primal

Concluímos, dessa forma, que dado um problema de programação linear, podemos escolher entre solucionar o modelo primal ou o dual correspondente, uma vez que a solução de um pode ser obtida a partir do outro. A escolha leva em consideração o esforço computacional que, em geral, está associado ao número de restrições. O problema dual, assim como o primal, gera uma interpretação econômica dos resultados ótimos obtidos. Por exemplo, o valor de y1= 0, representa o valor de oportunidade do recurso mão-de-obra. O resultado é coerente, já que o recurso mão-de-obra não é escasso (x3 = 100/7). Já o valor de y2= 1000/7, representa o valor de oportunidade do recurso madeira, isto é, cada m2 de madeira tem capacidade de gerar uma receita de R$ 142,86. O valor de y2 representa a capacidade da unidade do recurso madeira gerar receita neste programa.

Na função objetivo dual, cada parcela mede, então, o valor de oportunidade dos recursos envolvidos na produção (estoque x valor de oportunidade unitário do recurso). A função objetivo dual mede, portanto, a capacidade de o estoque de recursos gerar receita.

É de fundamental importância o entendimento da Teoria da Dualidade em Programação Linear uma vez que ela nos fornece elementos para um melhor entendimento do problema através de uma nova interpretação (dual) do mesmo e de relações bem definidas entre essa nova interpretação e a formulação original. Podemos dizer que em aplicações de PL à Pesquisa Operacional, um problema só está bem formulado quando seu dual for também analisado.

EXEMPLO 2: PRIMAL: MAX z = 2x1+x2

SA x1+5x210

x1+3x26

2x1+2x28

x1 0 , x2 0

Tableau FinalBASE x1 x2 x3 x4 x5 bi

x3 0 4 1 0 -1/2 6x4

x1

0 2 0 1 -1/2 1 1 0 0 1/2

24

-Z 0 -1 0 0 -1 -8

67

Solução ótima do primal: Z= 8 x1=4 x2=0 x3=6 x4=2 x5=0Solução ótima do dual:W=8 y1=0 y2=0 y3=1 y4=0 y5=1

DUAL: MIN W = 10y1+6y2+8y3

SA y1+y2+2y3 2

y1+3y2+2y31

y1 0 , y2 0, y3 0

Tableau FinalBASE y1 y2 y3 y4 y5 bi

y5 -4 -2 0 -1 1 1y3 0,5 0,5 1 -0,5 0 1

-Z 6 2 0 4 0 -8

4.3- RELAÇÕES ENTRE PRIMAL E DUAL Dual

Primal

Tem soluções viáveis Sem soluções viáveis

Ótima Ilimitado Inviável

Tem soluções viáveis

Ótima Possível Impossível ImpossívelIlimitado Impossível Impossível Possível

Sem soluções viáveis

Inviável Impossível Possível Possível

4.4- RESUMO PARA TRANSFORMAÇÃO PRIMAL-DUAL1- Restrições de DesigualdadePRIMAL DUALMIN Z= CTX MAX W= BTYS.A. AX B S.A. AT Y CCom X 0 Com Y 02- Restrições de IgualdadePRIMAL DUALMIN Z= CTX MAX W= BTYS.A. AX = B S.A. AT Y CCom X 0 Com Y livre

MAX Z= CTX MIN W= BTYS.A. AX = B S.A. AT Y CCom X 0 Com Y livre

Capítulo VANÁLISE DE SENSIBILIDADE

5.1- INTRODUÇÃO

68

Solução ótima do primal: Z= 8 x1=4 x2=0 x3=6 x4=2 x5=0Solução ótima do dual:W=8 y1=0 y2=0 y3=1 y4=0 y5=1

O objetivo da Programação Matemática, mais do que simplesmente determinar valores para variáveis de modo a maximizar uma função objetivo e a satisfazer restrições de um modelo matemático, é dar ao analista um melhor entendimento do problema em estudo.

A solução ótima de um problema é calculada com base nos dados do modelo, que podem sofrer variações ditadas por várias razões, como por exemplo:

Os dados foram estimados; Novas informações ou possibilidades aparecem após a formulação do

modelo.Dessa forma, é importante pesquisar a estabilidade da solução adotada, em face

dessas variações.A análise de sensibilidade, ou análise pós-ótima, é um conjunto de técnicas que, de

forma bastante simples (em PL) nos fornece informações sobre a sensibilidade da solução ótima a alterações na formulação do problema.

Analisaremos em nossos estudos os seguintes casos:1. Variações nos coeficientes da FO;2. Variações nas quantidades dos recursos;3. Acréscimo de variável;4. Acréscimo de restrição.

Com essas análises, poderemos responder perguntas do tipo “Dentro de que intervalo pode o preço de venda do produto x variar sem afetar a solução ótima?”, “Como seria afetada a decisão ótima se a disponibilidade do recurso b fosse reduzida de k unidades?”, “Seria interessante fabricar um determinado produto que hoje não faz parte da minha programação de produção?”.

Nossa abordagem será sempre na seguinte linha. Conhecidos o tableau inicial do problema original (não modificado) e o tableau final (ótimo) do mesmo, procuraremos descobrir como uma modificação no tableau inicial modifica o tableau final supondo que os mesmos pivotamentos que transformaram o tableau inicial original no tableau final original são feitos sobre o tableau inicial modificado. A figura a seguir ilustra o que dissemos.

Para enxergar mais claramente a essência das técnicas de Análise de Sensibilidade e ganhar a intuição criadora vamos vê-las de através do exame de exemplos.

O problema exemplo é:MAX Z = 3x1 + 5x2

S.A. x1 ≤ 4 x2 ≤ 6

69

Tableau Original Inicial Tableau Modificado Inicial

Tableau Original Final(ótimo)

Tableau Modificado Final(ótimo ou não)

Método Simplex(Seqüência de Pivotamentos)

Mesma Seqüência de Pivotamentos

Alterações

Comparação

3x1 + 2x2 ≤ 18 x1 , x2 ≥ 0

Forma Padrão:-Z+ 3x1 + 5x2 + 0x3 + 0x4+ 0x5 (FO Transformada) x1 + x3 = 4 x2 + x4 = 63x1 + 2x2 + x5 = 18 x1 , x2 , x3 , x4 , x5 ≥ 0

Seja o seguinte Tableau Inicial para o problema: BASE -Z x1 x2 x3 x4 x5 bi

x3 0 1 0 1 0 0 4x4 0 0 1 0 1 0 6x5 0 3 2 0 0 1 18-z 1 3 5 0 0 0 0

Tableau 1- Tableau Original Inicial

e o Tableau Final após a aplicação do Método Simplex

BASE -Z x1 x2 x3 x4 x5 bi

x3 0 0 0 1 2/3 -1/3 2x2 0 0 1 0 1 0 6x1 0 1 0 0 -2/3 1/3 2-z 1 0 0 0 -3 -1 -36

Tableau 2- Tableau Original Final

5.2- VARIAÇÕES NOS COEFICIENTES DA FO

Consideremos o Tableau Original Inicial (Tableau 1) e o Tableau Original Final(Tableau 2) do exemplo apresentado.

Tomemos o coeficiente de x1 assinalado com no tableau inicial. Se mudássemos o coeficiente original (3) do Tableau inicial para (3+δ), onde δ é uma quantidade qualquer e fizéssemos os mesmos pivotamentos que fizemos para obter o Tableau Final, obteríamos o mesmo resultado final para o coeficiente de x1, porém acrescido de δ, ou seja, (0+δ). Portanto o que acrescentarmos a um coeficiente da FO no Tableau inicial, será o acréscimo que obteremos no tableau final após os pivotamentos. O tableau final ficaria:BASE -Z x1 x2 x3 x4 x5 bi

x3 0 0 0 1 2/3 -1/3 2x2 0 0 1 0 1 0 6x1 0 1 0 0 -2/3 1/3 2-z 1 δ 0 0 -3 -1 -36

Tableau 3- Tableau resultante das modificaçõesComo x1 é variável básica no tableau final, e as colunas com variáveis básicas

deverão ser um vetor identidade, devemos fazer δ=0 restabelecendo, assim, a forma canônica do tableau . Para isso, pivotamos no coeficiente 1 da coluna de x1 (isto é, multiplicamos a 3ª linha por –δ e somamos à linha da FO para tornar nulo o coeficiente de x1 na linha da FO), obtendo

BASE -Z x1 x2 x3 x4 x5 bi

70

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

x3 0 0 0 1 2/3 -1/3 2x2 0 0 1 0 1 0 6x1 0 1 0 0 -2/3 1/3 2-z 1 0 0 0 -3+(2δ/3) -1-(δ/3) -36-2δ

Tableau 4- Tableau Resultante na Forma Canônica

Agora, com o Tableau na forma canônica podemos afirmar que se todos os coeficientes da linha da FO forem não-positivos (excetuamos como sempre o de –Z) o tableau é ótimo, ou seja, o Tableau 4 será ótimo se

-3 + 2/3 δ ≤ 0 δ≤9/2-1 - 1/3 δ ≤ 0 δ≥ -3Portanto:

Como δ é um acréscimo, para obter o intervalo de variação do coeficiente de x1 para o qual o tableau 4 é ótimo, temos que somar o valor original do coeficiente, ou seja, Z = 3x1 + 5x2

Z* = (3+δ)x1 + 5x2

(3-3 = 0) ≤ Coef. de x1 ≤ (3 + 9/2 = 15/2)

Assim, se o coeficiente de x1 na FO for qualquer número entre zero e 15/2 (incluindo esses valores extremos) a solução ótima encontrada para o problema original permanecerá ótima para o problema modificado. Note que apesar de a solução ótima para o original permanecer ótima para o problema modificado ( pelo acréscimo de uma quantidade δ Є [-3 , 9/2] ao coeficiente de x1 na FO) o valor ótimo da FO irá variar em função de δ uma vez que Z*=36+2δ. E se alterássemos o coeficiente de x1 na FO de δ para Є [-3 , 9/2]? Neste caso, o Tableau 4 não mais será ótimo e precisaremos aplicar o Método Simplex para obter a nova solução ótima. Mesmo nesse último caso, onde precisamos de usar o Método Simplex para obter o novo ótimo, o esforço computacional é usualmente menor do que resolver o problema modificado a partir do tableau modificado inicial.

No caso que acabamos de analisar, o coeficiente alterado correspondia a uma variável básica no tableau original final. Quando o coeficiente alterado corresponde a uma variável que é não-básica no tableau original final, a análise se torna ainda mais fácil. Suponhamos que o coeficiente de x4 na FO fosse alterado de zero para δ (como x4 é uma variável de folga, isso poderia, num problema real, corresponder ao surgimento de uma oportunidade de vender o recurso excedente por δ $/unid). Como vimos anteriormente, o impacto no tableau resultante das modificações (tableau inicial modificado submetido aos mesmos pivotamentos que produziram o tableau original final a partir do tableau original inicial) será um acréscimo de δ unidades no coeficiente de x4 quando comparado com o tableau original final. A linha da FO seria portanto,

BASE -Z x1 x2 x3 x4 x5 bi

x3 0 0 0 1 2/3 -1/3 2x2 0 0 1 0 1 0 6x1 0 1 0 0 -2/3 1/3 2-z 1 0 0 0 -3+δ -1 -36

71

-3 ≤ δ ≤ 9/2

Linha 1Linha 2Linha 3Linha da FO

e o tableau estaria na forma canônica permitindo uma análise imediata. O tableau seria ótimo quando tivéssemos (-3+δ) ≤ 0 ou seja δ≤ 3. Interpretando a necessidade de modificação como o surgimento de uma oportunidade de vender o recurso correspondente à linha 2. Essa análise responderia a pergunta: “Qual o menor preço para o recurso da linha 2 acima do qual passa a ser interessante a venda dele?” Como o coeficiente de x4 na FO era o zero inicialmente, δ irá representar o novo preço para o recurso. Apenas para valores de δ acima de 3 é que a atividade x4 (fazer sobrar recurso para venda) passa a ser lucrativa (forma x4 candidata para entrar na base). Para qualquer valor de δ inferior a 3 a solução com x4 não-básica (e, portanto, uma solução que usa todo o recurso da linha 2) é ótima.

O mesmo tipo de análise pode ser feita quando queremos saber o efeito de variar simultaneamente mais de um coeficiente da FO. A única dificuldade é que ficamos com um sistema de desigualdades (que restringem as variações dos coeficientes) mais complicado.

5.3- VARIAÇÕES NAS QUANTIDADES DOS RECURSOS

Se no Tableau inicial original (Tableau 1) mudarmos o termo independente da primeira linha de 4 para 4+δ, o tableau inicial fica:

BASE -Z x1 x2 x3 x4 x5 bi

x3 0 1 0 1 0 0 4 + δx4 0 0 1 0 1 0 6x5 0 3 2 0 0 1 18-z 1 3 5 0 0 0 0

Tableau 5- Tableau Inicial com modificação em termo independente

Se fizermos a mesma seqüência de pivotamentos que fizemos para obter o tableau final do problema original, não haverá mudanças (em relação ao tableau original final, Tableau 2) a não ser a coluna dos termos independentes . Podemos, para maior clareza no que segue, representar δ por uma coluna no lado direito do tableau, assim BASE -Z x1 x2 x3 x4 x5 bi δ

x3 0 1 0 1 0 0 4 1x4 0 0 1 0 1 0 6 0x5 0 3 2 0 0 1 18 0 -z 1 3 5 0 0 0 0 0

Tableau 6- Representação da modificação como uma coluna no lado direito

Note que a coluna de δ é idêntica à coluna de x3 e como fazemos apenas operações com linhas, duas linhas idênticas no tableau inicial permanecem idênticas após os pivotamentos. Portanto, no tableau, após os pivotamentos teremos: BASE -Z x1 x2 x3 x4 x5 bi δ

x3 0 0 0 1 2/3 -1/3 2 1x2 0 0 1 0 1 0 6 0x1 0 1 0 0 -2/3 1/3 2 0-z 1 0 0 0 -3 -1 -36 0

72

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

Conseqüentemente, para que a base ótima do problema original permaneça factível (variáveis básicas não-negativas) para o problema modificado, basta que 2+δ≥0, ou seja, δ≥-2. Assim, podemos concluir que quando alteramos um b i no tableau inicial, se a variável básica que, nesse tableau, corresponde ao bi for também básica no tableau final, então um aumento (positivo) nesse bi não desfaz a factibilidade da base ótima para o problema original. Se a modificação for um decréscimo no bi, então para que a base ótima para o problema original permaneça factível, o valor absoluto desse decréscimo não deve ser superior ao valor de bi no tableau original final.

Vejamos agora o que acontece quando mudamos o valor de um bi que corresponde a uma variável no tableau inicial que é não-básica no tableau original final.

Suponhamos que o termo independente da segunda linha do tableau original inicial fosse mudado para 6+δ teríamos então no tableau inicial.

BASE -Z x1 x2 x3 x4 x5 bi δx3 0 1 0 1 0 0 4 0x4 0 0 1 0 1 0 6 1x5 0 3 2 0 0 1 18 0 -z 1 3 5 0 0 0 0 0

Fazendo os mesmos pivotamentos do problema original obteríamos:

BASE -Z x1 x2 x3 x4 x5 bi δx3 0 0 0 1 2/3 -1/3 2 2/3x2 0 0 1 0 1 0 6 1x1 0 1 0 0 -2/3 1/3 2 -2/3-z 1 0 0 0 -3 -1 -36 -3

Ou seja, para que a base ótima do problema original permaneça factível:2+ 2/3 δ ≥ 0 δ≥ -36+ δ ≥ 0 δ≥ -6 ou -3 ≤ δ ≤ 32- 2/3 δ ≥ 0 δ≥ 3

Concluímos então que para valores de δ Є [-3, 3] a solução ótima do problema modificado é diferente da solução ótima do problema original (exceto para δ=0), mas a base (isto é, a coluna ou as variáveis que compõem a base) ótima do problema original é também ótima para o problema modificado.

Pode-se fazer o mesmo tipo de análise acima considerando-se variações simultâneas de mais de um bi. Como no caso do estudo de sensibilidade para os coeficientes da FO, o único problema é que as expressões (o sistema de desigualdades) limitando a variação simultânea dos bi’s torna-se mais complicado. Isso será verdade sempre que sempre que a linha do bi modificado tiver uma variável de folga (se a variável for de “excesso” as colunas serão idênticas mas com os sinais trocados antes e depois dos pivotamentos).5.4- ACRÉSCIMO DE VARIÁVEL

Algumas vezes precisamos adicionar uma coluna a um problema de PL que já foi resolvido. Por exemplo, após resolver um problema de programação de produção podemos

73

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

estar interessados em saber se a possibilidade de fabricar um novo produto pode melhorar o valor FO.

Examinemos, inicialmente, o tableau inicial e o final de um problema qualquer de PL para identificar alguns aspectos importantes para a análise.

Sendo “m” o número de linhas (equações de restrição) do problema e “n” o número de colunas (variáveis) do problema, temos:

BASE -Z x1 xn-m xn-m-1 xn bi

xn-m+1 b1

A I xn bm

-Z 1 0 0 0 Tableau Inicial

BASE -Z x1 xn-m xn-m-1 xn bi

xB1 b1

A Q xBm bm

-Z1 -y1* -ym* -Z

Tableau Final

Podemos identificar no tableau inicial duas submatrizes. A primeira, a matriz A que corresponde aos coeficientes das variáveis não-básicas (no tableau inicial) nas linhas das restrições. Note que estamos supondo que o problema parte de uma base constituída por variáveis de folga. No tableau final (após a aplicação do Método Simplex) as colunas de A passam a formar uma nova sub-matriz A . A segunda é uma matriz identidade, I, formada pelos coeficientes das variáveis inicialmente básicas (variáveis de folga), que após os pivotamentos do Método Simplex se tornam a matriz Q do tableau final.

Considerando o tableau 1 (inicial) e o Tableau 2(final) do exemplo apresentado, temos as seguintes submatrizes identificadas:

A = após o método simplex A =

I = após o método simplex Q =

74

Coeficientes não-básicos

Multiplicadores do Simplex

1 00 13 2

0 00 11 0

1 0 0 0 1 0 0 0 1

1 2/3 -1/30 1 00 -2/3 1/3

Multiplicadores do Simplex: [0 -3 -1]

O que nos diz a matriz Q? Ora, se em cada linha e em cada coluna de I temos apenas um elemento não zero que é 1, a matriz Q espelha os pivotamentos que foram feitos durante a execução do Método Simplex. Assim, se quisermos saber como fica no tableau final uma coluna qualquer do tableau inicial, basta multiplicar a coluna pela matriz Q.

Exemplo: Consideremos nosso problema exemplo.Vamos verificar como fica no tableau final (Tableau 2) a coluna de x1 do Tableau

inicial (Tableau 1).Coluna de x1 do tableau inicial (Tableau 1): 1

03

Coluna de x1 do tableau final (Tableau 2):

Q . 1 = 1 0 0 = 3 3

Já sabemos, então, como obter os coeficientes de uma nova coluna (correspondente a uma nova variável acrescentada ao problema original) nas linhas das restrições do tableau final sem para isto ter que resolver o problema modificado a partir do tableau inicial modificado. Falta-nos agora obter o coeficiente da nova variável na linha da FO no tableau final. Para isto, basta multiplicar o vetor linha [-y1* , , -ym*, 1] pela nova coluna.Exemplo: Consideremos nosso problema exemplo.Vamos verificar como o coeficiente de x1 na linha da FO do tableau inicial(Tableau 1) fica no tableau final (Tableau 2).[-y1* -y2* -y3* FO] [0 -3 -1 1] . = 0

O que confere com o encontrado no Tableau 2Seja agora o seguinte exemplo:O que acontece se acrescentarmos ao problema exemplo a variável x6 com coeficientes conforme abaixo?

Linha 1Linha 2Linha 3

75

1 2/3 -1/30 1 00 -2/3 1/3

001

1033

FOAnálise:

BASE -Z x1 x2 x3 x4 x5 x6 bi

x3 0 1 0 1 0 0 2 4x4 0 0 1 0 1 0 3 6x5 0 3 2 0 0 1 6 18-z 1 3 5 0 0 0 15 0

Tableau Modificado Inicial

Como ficaria esta nova coluna no Tableau Modificado Final?a)Identificar Q vendo no tableau original final as colunas correspondentes as variáveis básicas do tableau original inicial.b) Multiplicar a nova coluna pela matriz Q

Q . 2 = 2 3 3 = 6 6

c) Coeficiente na linha da FO[-y1* -y2* -y3* FO] [0 -3 -1 1] . = 0-9-6+15 = 0

Assim temos o seguinte tableau modificado final:

BASE -Z x1 x2 x3 x4 x5 x6 bi

x3 0 0 0 1 2/3 -1/3 2 2x2 0 0 1 0 1 0 3 6x1 0 1 0 0 -2/3 1/3 0 2-z 1 0 0 0 -3 -1 0 -36

Tableau Modificado Final

Como o custo reduzido é não positivo podemos concluir que o tableau modificado final permanece ótimo, ou seja, a nova variável não é básica nesse tableau. Note que, por acaso, o custo reduzido é zero e, portanto, se pode dar valor positivo à nova variável obtendo nova solução ótima. Se ao invés de 15 o coeficiente da nova coluna na FO fosse 18, digamos, o custo reduzido seria positivo indicando que deve-se aplicar o Método Simplex para tentar restabelecer a otimalidade do tableau.

A nova coluna entraria na base e para determinar a variável a sair da base, precisaríamos dos outros elementos da coluna nova no tableau modificado final. Teríamos então a seguinte situação:

BASE -Z x1 x2 x3 x4 x5 x6 bi

x3 0 0 0 1 2/3 -1/3 2 2x2 0 0 1 0 1 0 3 6

76

2 361

Linha 1Linha 2Linha 3Linha da FO

230

1 2/3 -1/30 1 00 -2/3 1/3

23615

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

x1 0 1 0 0 -2/3 1/3 0 2-z 1 0 0 0 -3 -1 3 -36

Tableau Modificado Final

Aplicando o Método Simplex, pivotamos no elemento assinalado, o que faz x6 entrar na base e x3 sair dela. Faça o pivotamento e veja se o tableau fica ótimo. Se não ficar, prossiga até que ou se torne ótimo, ou indique que o problema é ilimitado.

5.5- ACRÉSCIMO DE RESTRIÇÃO

Podemos, após resolver um problema de PL, querer acrescentar uma restrição ao modelo inicial. Isto pode se dar porque esquecemos de uma restrição quando formulamos o modelo, porque queremos explorar alguma condição sugerida pelo problema concreto, etc.

É claro que se o Método Simplex aplicado ao problema original terminar com uma indicação de que o problema é infactível, não há porque querer acrescentar uma restrição. Abaixo ilustraremos como acrescentar uma restrição no caso de o tableau final do problema original indicar uma solução ótima e, através de outro exemplo, quando o tableau final indicar que o problema original não tem ótimo finito. É importante notar que em ambos exemplos a restrição adicional é ativa na solução do problema modificado. Caso não seja, o mesmo procedimento irá indicar que a solução do problema original permanece ótimo após o acréscimo da restrição ou que permanece sem ótimo finito. No de a restrição adicionada tornar o problema infactível, o Método Simplex Dual irá indicar isso.

Uma nova restrição pode alterar a viabilidade da solução se ela não for redundante. O procedimento para essa análise é o seguinte:

1) Testar se a nova restrição é satisfeita para a atual solução ótima. Em caso afirmativo, a nova restrição é redundante.

2) Se não for satisfeita, ela deve ser introduzida no sistema e novos cálculos são necessários.

Vamos exemplificar introduzindo uma nova restrição no problema exemplo apresentado.Seja a seguinte restrição adicionada: x1 + x2 ≤ 7

Teste para verificar se a restrição é redundante: x1 + x2 ≤ 7 2 + 6 = 8 > 7 (a nova restrição não é redundante)

Logo, a solução atual deixará de ser ótima com a entrada da nova restrição, e novas iterações deverão ser feitas. Vamos acrescentar a nova restrição no tableau original final com sua correspondente variável de folga. Assim, vem:

BASE -Z x1 x2 x3 x4 x5 x6 bi

x3 0 0 0 1 2/3 -1/3 0 2x2 0 0 1 0 1 0 0 6x1 0 1 0 0 -2/3 1/3 0 2x6 0 1 1 0 0 0 1 7-z 1 0 0 0 -3 -1 0 -36

77

Linha 1Linha 2Linha 3Linha 4 (nova restrição)Linha da FO

Sem o tableau na forma canônica nada podemos afirmar sobre a otimalidade ou factibilidade. Para por na forma canônica pivotamos sobre x2 na segunda linha e sobre x1 na terceira linha, obtendo o tableau abaixo: BASE -Z x1 x2 x3 x4 x5 x6 bi

x3 0 0 0 1 2/3 -1/3 0 2x2 0 0 1 0 1 0 0 6x1 0 1 0 0 -2/3 1/3 0 2x6 0 0 0 0 -1/3 -1/3 1 -1-z 1 0 0 0 -3 -1 0 -36

Podemos agora ver que a base formada por { x3 , x2 , x1 , x6 }não é factível, uma vez que temos um valor negativo na última coluna. Como temos o tableau na forma canônica e factibilidade dual ( custos reduzidos não-positivos), podemos aplicar o Método Dual-Simplex para restabelecer a factibilidade primal (termos independentes não-negativos), cujas diferenças com relação ao Método Simplex se resume nas regras de entrada e saída de variáveis da base, que são as seguintes:

a) Variável que sai: é a variável básica com o valor mais negativo. Empates podem ser resolvidos arbitrariamente. Se todas as variáveis básicas tiverem valores positivos, a solução é ótima;

b) Variável que entra: é escolhida entre as variáveis fora da base, da seguinte forma:b.1) dividir os coeficientes da linha da FO pelos correspondentes coeficientes negativos da equação da variável que sai.b.2) a variável que entra é a que tem o menor valor absoluto entre os quocientes encontrados.Quando não houver coeficientes negativos na linha da variável que sai da base, o problema não tem solução viável.

Aplicando o Dual-Simplex no nosso exemplo, vem: x6 variável que sai da base x5 variável que entra da basePivotando, portanto sobre x5 na linha da nova restrição, temos:

BASE -Z x1 x2 x3 x4 x5 x6 bi

x3 0 0 0 1 1 0 -1 3x2 0 0 1 0 1 0 0 6x1 0 1 0 0 -1 0 1 1x5 0 0 0 0 1 1 -3 3-z 1 0 0 0 -2 0 -3 -33

O tableau agora é factível (variáveis básicas não-negativas) com a seguinte solução ótima:

x1 = 1 x3 = 3 x5 = 3 Z = 33x2 = 6 x4 = 0 x6 = 0

Note que acrescentamos ao problema original, além de uma restrição, uma nova variável x6

que é a variável de folga da restrição adicional. Se a restrição tivesse o sentido da desigualdade “≥” o procedimento seria exatamente o mesmo após multiplicarmos a restrição por -1, invertendo o sentido da desigualdade. Se a restrição fosse de igualdade, o

78

Linha 1Linha 2Linha 3Linha 4 (nova restrição)Linha da FO

Linha 1Linha 2Linha 3Linha 4 (nova restrição)Linha da FO

procedimento também seria o mesmo e x6 seria vista como uma variável artificial que seria eliminada do problema assim que se tornasse não-básica.

Vamos agora ao seguinte exemplo:MAX Z = 3x1 + 2x2

S.A. -2x1 + x2 ≤ 3 x1 - x2 ≤ 4 x1 , x2 ≥ 0

Seja o seguinte tableau original final do problema:

BASE -Z x1 x2 x3 x4 bi

x3 0 0 -1 1 2 11x1 0 1 -1 0 1 4-Z 1 0 5 0 -3 -12

O problema, portanto, não admite ótimo finito. Vejamos agora o que acontece se acrescentarmos a restrição 2x1 + 3x2 ≤ 12 a este problema. Adicionando a variável de folga x5 e agregando a nova restrição ao tableau temos:

BASE -Z x1 x2 x3 x4 x5 bi

x3 0 0 -1 1 2 0 11x1 0 1 -1 0 1 0 4x5 0 2 3 0 0 1 12-Z 1 0 5 0 -3 0 -12

Restabelecendo a forma canônica temos:

BASE -Z x1 x2 x3 x4 x5 bi

x3 0 0 -1 1 2 0 11x1 0 1 -1 0 1 0 4x5 0 0 5 0 -2 1 4-Z 1 0 5 0 -3 0 -12

O que mostra ser a solução factível, mas não ótima. Aplicando o Simplex Primal, em uma iteração obtemos:

BASE -Z x1 x2 x3 x4 x5 bi

x3 0 0 0 1 8/5 1/5 59/5x1 0 1 0 0 3/5 1/5 24/5x2 0 0 1 0 -2/5 1/5 4/5-Z 1 0 0 0 -1 -1 -16

Que demonstra a otimalidade da solução.Após essas análises de sensibilidade estudadas, observamos que o trabalho da

equipe de P.O. não está nem mesmo perto de estar concluído depois de o método simplex ter sido aplicado com sucesso para identificar uma solução ótima para o modelo. Na verdade, os valores dos parâmetros usados no modelo normalmente são apenas estimados com base numa previsão de condições futuras. Os dados obtidos para desenvolver estas estimativas freqüentemente são um tanto crus ou inexistentes, de modo que os parâmetros na formulação original podem representar pouco mais que rápidas regras práticas fornecidas por pessoal de linha pressionado. Eles podem mesmo representar

79

Linha 1Linha 2Linha da FO

Linha 1Linha 2Linha 3 (nova restrição)Linha da FO

Linha 1Linha 2Linha 3Linha da FO

Linha 1Linha 2Linha 3Linha da FO

superestimativas, ou subestimativas deliberadas para proteger os interesses dos estimadores.

Portanto, a gerência ou grupo de pesquisa operacional manterá um ceticismo saudável quanto aos números originais saindo do computador e, em muitos casos, irá vê-los apenas como um ponto de partida para futuras análises do problema.

Por estas e outras razões é importante se proceder uma análise de sensibilidade para investigar o efeito do método simplex sobre a solução ótima se os parâmetros assumirem outros valores possíveis.

Capítulo VI PROBLEMAS DE TRANSPORTES

6.1- INTRODUÇÃO

80

A estruturação do problema de transportes é uma aplicação interessante de programação linear e de grande relevância para a Engenharia de Produção. A Pesquisa Operacional estuda esses problemas com o objetivo de minimizar custos de transporte e desenvolver modelos computacionais de fácil resolução.

Um problema típico de Transporte pode ser descrito como se segue: Quantidades dadas de um determinado produto são disponíveis em cada uma de um determinado número de origens (por exemplo, armazéns). Desejamos remeter quantidades específicas do produto a cada um de um determinado número de destinos (por exemplo, mercados varejistas). É conhecido o custo de embarque de uma unidade do produto de qualquer uma origem para qualquer um destino. Considerando-se que é possível embarcar de qualquer uma das origens para qualquer um dos destinos, estamos interessados em determinar os itinerários (rotas) de custo mínimo das origens (armazéns) aos destinos (mercados varejistas).

Dizemos que um sistema de transporte está equilibrado quando a somatória das quantidades de produtos ofertados em cada origem é igual a somatória das quantidades de produtos demandados em cada destino.

Para solucionar um problema de transporte, ou seja, para encontrarmos os itinerários otimizados (de menor custo) das origens para os destinos, devemos, inicialmente, modelar o problema matematicamente. Após esta modelagem, devemos proceder a aplicação do algoritmo de transporte.

6.2- MODELAGEM DO PROBLEMA DE TRANSPORTES

Suponhamos a existência de “m” origens de um produto, cada uma podendo fornecer a quantidade “ai”, com o índice i = 1,2,...., m. Por outro lado, existem “n” destinos, cada um demandando uma quantidade “bj”, com j = 1,2,...., n. Sabe-se que o custo de transportar uma unidade do produto da origem “i” para o destino “j” é “Cij”. O objetivo do problema é determinar o número de unidades “xij” do produto, que devem ser transportados de cada origem “i” para cada destino “j”, de forma a minimizar o custo total de transporte. Estruturando o problema de forma diagramática, temos:

Considerando que é possível embarcar de qualquer uma das origens (armazéns) para qualquer um dos destinos (mercados varejistas), que o número total de unidades transportadas, a partir da origem i deve ser igual à oferta ai da origem; e que o número de unidades transportadas para o destino j deve ser igual à sua demanda b j, temos o seguinte modelo matemático:

Função Objetivo: (função matemática que expressa o objetivo de minimizar os custos)

81

Oferta (ai) a1

a2

.

.

.

am

Origens (i) Destinos (j)

1 1

2 2. .. .. .. .m n

b1

b2

.

.

.

.

. bn

Demanda (bj)

x11C11

x12C12x1nC1n

x21C21 x22C22

x2nC2n

xm1Cm1 xm2Cm2

xmnCmn

MIN Z= C11x11 + C12x12 + .... + C1n1x1n + C21x21 +C22x22 + .... + C2nx2n +.... + Cm1xm1 +Cm2xm2

+.... + Cmnxmn

ou seja, m n

MIN Z= Cij . xij

i=1 j=1

Restrições: Restrições em relação a oferta:x11 + x12 + ... +x1n = a1

x21 + x22 + ... +x2n = a2

.

.

xm1 + xm2 + ... +xmn = am

ou seja, n

xij = ai para i=1, 2, ... , mj=1

Restrições em relação a demanda:x11 + x21 + ... +xm1= b1

x12 + x22 + ... +xm2 = b2

.

x1n + x2n + ... +xmn = bm

ou seja, m

xij = bi para j=1, 2, ... , ni=1

Restrições implícitas:xij 0IMPORTANTE: Para que o problema tenha solução, a seguinte equação de balanço deve ser verificada:m n

ai = bji=1 j=1

Para solucionar o problema de transporte costuma-se representar seus dados conforme segue no Quadro 1.

Destinos ji 1 2 . . . . . n

Ofertaai

1x11

C11

x12

C12

. . . . . x1n

C1n a1

2 x21

C21

x22

C22

. . . . . x2n

C2n a2

.

...

.

.. . . . .

...

.

.xm1 xm2 . . . . . xmn

82

Origens

m Cm1 Cm2 Cmn am

Demandabj b1

b2 . . . . .bn

Quadro 1 – Representação dos dados dos problemas de transporte

6.3- ALGORITMO DO PROBLEMA DE TRANSPORTE

O algoritmo de transporte consiste em um método iterativo que compreende basicamente os seguintes passos:

1. Encontrar uma solução básica inicial;2. Verificar se a solução encontrada é ótima. Se for, pare. Caso contrário siga para o

passo 3;3. Determinar uma nova solução básica compatível e voltar ao passo 2.

Para facilitar o entendimento do algoritmo faremos seu estudo baseado em um exemplo prático, conforme segue:

Exemplo: Determinar, a partir dos dados apresentados no quadro abaixo, o plano para destinação de remessas de ervilhas enlatadas de três armazéns a três centros consumidores, de tal forma que o custo total de transporte seja minimizado.

Destinos (centros consumidores)j

i 1 2 3Oferta

ai

1C11=8 C12=5 C13=6

a1=120

2C21=15 C22=10 C23=12

a2=80

3C31=3 C32=9 C33=10

a3=80Demanda

bj

b1=150b2=70 b3=60

6.3.1- Obtenção da solução básica inicialObter uma solução básica inicial. Para calcularmos a solução básica inicial existem

diversos algoritmos matemáticos, dentre os quais destacam-se o Método do Canto Noroeste, o Método do Mínimo Custo e o Método de Vogel.

83

Orig

ens

(arm

azén

s)

Obs: Para iniciar a solução do problema deve-se primeiramente verificar se o sistema está equilibrado, caso não esteja deve-se proceder seu equilíbrio para então iniciar a sua solução.Para que o problema de transporte tenha solução, a seguinte equação de equilíbrio deve ser verificada: m n

ai = bji=1 j=1

No caso desta equação não ser satisfeita, significa que o sistema não está equilibrado. Caso isso ocorra, deve-se criar uma origem ou destino fictício para que o balanceamento possa ocorrer.

EXEMPLO DE UM PROBLEMA NÃO EQUILIBADO

Uma companhia locadora de automóveis se defronta com um problema de alocação resultante dos contratos de locação que permitem sejam os automóveis devolvidos em localidades outras que aquelas onde foram originalmente alugados. No presente momento há duas agências de locação (origens) com, respectivamente 15 e 13 carros excedentes e quatro outras agências (destinos) necessitando de 9, 6, 7, e 9 carros, respectivamente. Os custos unitários de transporte entre as locadoras são os seguintes:

Restabelecendo o Equilíbrio, temos:

84

ij

1 2 3 4 Oferta (ai)

Demanda(bj)

1

2

C11=45 C12=17 C13=21 C14=30a1=15

C21=14 C22=18 C23=19 C24=31a2= 13

b1=9 b2=6 b3= 7 b4= 9

Destinos (locadoras com déficit)

Ori

gen

s (l

oca

do

ras

com

exc

esso

)

x11 x12 x13 x14

x21 x22 x23 x24

Verificação da Equação de Equilíbrio:m n oferta demandaΣ ai = Σ bj 15+13 = 9+6+7+9

i=1 j=1 28 < 31 Sistema não-equilibrado!

ij

1 2 3 4 Oferta (ai)

Demanda(bj)

1

2

3

C11=45 C12=17 C13=21 C14=30a1=15

C21=14 C22=18 C23=19 C24=31a2= 13

b1=9 b2=6 b3= 7 b4= 9

Destinos (locadoras com déficit)

Ori

ge

ns

(lo

cad

ora

s c

om

exc

esso

)

(fictícia)

C31=0 C32=0 C33=0 C34=0a3= 3

Solução ótima encontrada após aplicação do Algoritmo de “Stepping-Stone” (será estudado no item 6.3.2):

O fato de haver alguma alocação positiva proveniente da origem fictícia indica que nem todas as demandas podem ser satisfeitas. Em particular, o destino 4 receberá automóveis a menos do que necessita.

Método do Canto Noroeste

Passo 1: Comece pela célula do canto superior esquerdo do quadro chamada célula (1,1), e aloque o valor máximo possível para x11, com o cuidado de não violar as restrições de oferta e demanda, ou seja, será alocado a x11 o menor valor entre a1 e b1.

ji 1 2 3

Ofertaai

1 120 a1=120

2 a2=80 3 a3=80

Demandabj b1=150 b2=70 b3=60

85

ij

1 2 3 4 Oferta (ai)

Demanda(bj)

1

2

3

a1=15

a2= 13

b1=9 b2=6 b3= 7 b4= 9

Destinos (locadoras com déficit)

Ori

gen

s (l

oca

do

ras

com

exc

esso

)

x11=0 x12 =6 x13=3 x14= 6

x21=9 x22 =0 x23=4 x24=0

(fictícia)a3= 3

x31=0 x32 =0 x33 =0 x34=3

(linha eliminada)

Passo 2: “Elimine” a linha ou coluna já completamente atendida, ou seja, se a1<b1, “elimine” todas as células da linha 1; se a1>b1, “elimine” todas as células da coluna 1; se a1=b1, então “elimine” apenas as células da coluna 1 ou as células da linha 1. Em seguida, subtraia o valor alocado da oferta a1 e da demanda b1.

Passo 3: Passe para a célula adjacente da linha ou coluna “não eliminada”. Se tanto a linha quanto a coluna adjacente já foram eliminadas, caminhe diagonalmente para a célula mais próxima. Em seguida faça a alocação conforme explicado no passo 1 e a eliminação da linha ou coluna conforme o passo 2. Repita esse passo até que todas as linhas e colunas tenham sido atendidas.

ji 1 2 3

ofertaai

1 120 120 0

2 80

3 80

bj

15030

70 60

ji 1 2 3

ofertaai

1 120 120 0

2 30 80 50

3 80

bj

150300

70 60

ji 1 2 3

ofertaai

1 120 120 0

2 30 50 80 50 0

3 80

bj

150300

7020

60

ji 1 2 3 ai

1 120 120

2 30 50 80 50 0

3 20 60 80 60 0

bj

150300

70200

600

86

Assim, a partir dessa solução (x11=120; x21=30; x22=50; x32=20; x33=60; x12=x13=x23=x31=0), pode-se chegar a o seguinte custo total de distribuição (não necessariamente o custo ótimo):

z = 8 x 120 + 15 x 30 + 10 x 50 + 9 x 20 + 10 x 60 = 2.690,00

Para verificar se este é o custo ótimo ou, caso, não seja, achá-lo, é necessário aplicar o Algoritmo de “Stepping-Stone” que veremos no item 6.3.2.

Método do Mínimo Custo

Os passos para aplicação deste método são idênticos aos passos do Método do Canto Noroeste, porém, iniciando a escolha da célula pela àquela como mínimo custo e caminhando sempre para o “próximo” mínimo custo.

j i 1 2 3 ai

18 5

706

50 a1=120 50 0

215

7010 12

10 a2=80 70

33

809 10

a3=80 0

bj

b1=15070 0

b2=700

b3=6010 0

O custo total de distribuição obtido para essa solução é dado por: 5 x 70 + 6 x 50 + 15 x 70 + 12 x 10 + 3 x 80 = 2060, que é inferior (e portanto “melhor”) que a solução obtida pelo Método do Canto Noroeste.

87

Método de Vogel

Normalmente, produz melhores soluções e, freqüentemente, a solução ótima. São previstos os seguintes passos:

Passo 1: Calcule os valores dos resíduos de cada uma das linhas e colunas, subtraindo o menor valor Cij do segundo menor o valor de Cij naquela linha ou coluna;

Passo 2: Escolha a linha ou coluna com o maior valor do resíduo (se houver empate, escolha arbitrariamente) e aloque o máximo possível de unidade à célula de menor Cij

daquela linha ou coluna;

Passo 3: “Elimine” a linha ou coluna já completamente atendida e retorne ao passo 1, recalculando os valores dos resíduos;

Passo 4: Termine quando “sobrar” apenas uma linha ou coluna, balanceando-a.

ji 1 2 3 ai

Resíduoda linha

18

70

5 6

50 120 50 0

6-5=16-5=16-5=1

215 10

70

12

10 80 70

12-10=212-10=212-10=2

33

80

9 10

80 0

9-3=6

*maior resíduo

bj

15070 0 70 0 60 10 0

Resíduoda coluna

8-3=515-8=7*maior resíduo

9-5=410-5=510-5=5

10-6=412-6=612-6=6 *maior resíduo

2ª eliminação

O custo total de distribuição correspondente é z = 8 x 70 + 6 x 50 + 10 x 12 + 10 x 70 + 3 x 80 = 1920, que é melhor que as soluções obtidas pelos métodos anteriores.

88

3ª eliminação

1ª eliminação

Conforme fica observado na apresentação dos métodos para cálculo de solução básica inicial, podemos encontrar uma solução (solução básica inicial de “boa qualidade”) ou mais afastada, conforme o método escolhido. O melhor método, conforme demonstrado, é o método de Vogel, o qual freqüentemente já nos fornece a solução ótima do problema de transporte. No entanto, é importante que fique claro que qualquer um dos métodos apresentados para o cálculo da solução básica inicial permitirá que, após a aplicação do algoritmo matemático de programação linear específico, o resultado final do problema de transporte (custo ótimo de distribuição) seja o mesmo.

A vantagem de se utilizar um método de cálculo da solução básica inicial mais preciso está no fato de se fazer menos iterações no algoritmo matemático de programação linear para cálculo do custo ótimo, reduzindo-se o tempo de processamento dos cálculos.

6.3.2- Algoritmo de “Stepping-Stone”

O Método “Stepping-Stone” consiste em uma seqüência de passos (algoritmo) que sempre chega à solução ótima a partir de uma solução inicial.

A partir da solução básica inicial encontrada, este método pesquisará se alguma melhor solução pode ser obtida.

Consideremos o quadro abaixo com a solução básica inicial encontrada a partir do Método do Canto Noroeste:

ji 1 2 3 ai

1c11=8

x11=120c12=5 c13=6

a1=120

2c21=15

x21=30c22=10

x22=50c23=12

a2=80

3c31=3 c32=9

x32=20c33=10

x33=60 a3=80

bj b1=150 b2=70 b3=60

Cada célula vazia (no caso, 9 – (m + n –1) células) representa uma variável não-básica que poderia entrar na base (para entrar, a contribuição específica da variável não-básica deve implicar a redução do custo total).

Calculando essas contribuições para a célula x12:

1. Aloque 1 unidade a x12. Assim,não é mais 70, mas 71 o total de unidades da coluna 2.2. Para não violar a restrição da coluna 2, uma unidade deverá ser subtraída ou de x22 (50) ou de x32 (20). Subtraia 1 de x22, que passa a ter 49 unidades, e a coluna 2 com um total de 70, novamente.

89

3. Agora, a linha 2 totaliza 79 e não mais 80, o que pode ser corrigido com a adição de uma unidade a x21 (30 31).4. A coluna 1 fica então com um total de 151, o que pode ser corrigido com a subtração de uma unidade de x11.5. A linha 1 é automaticamente corrigida em função do passo anterior.

Em outras palavras, deve-se determinar para cada variável não-básica um “caminho fechado” (closed-loop) para que se obtenha a eventual contribuição específica à função objetivo.

Para determinar-se o caminho:a) Adote um sentido (ou horário ou anti-horário);b) Há somente um caminho fechado para cada célula vazia;c) Os extremos do caminho (a menos da variável não-básica) devem ser células ocupadas;d) Células ocupadas podem ser “puladas”, assim como um caminho pode apresentar “cruzamentos”;e) Exatamente uma adição e uma subtração devem aparecer em cada linha e coluna do caminho traçado.

Assim, para a variável x12:x12 x22 x21 x11 x12

+1 –1 +1 –1

Atribuindo os valores de custo pertinentes:*C12 = C12 – C22 + C21 – C11 = 5 – 10 + 15 – 8 = 2

Realizando os cálculos devidos para todas as células vazias:Variável Caminho Fechado Contribuiçãox12 x12 x22 x21 x11 x12 +2x13 x13 x33 x32 x22 x21 x11 x13 +2x23 x23 x33 x32 x22 x23 +1x31 x31 x21 x22 x32 x31 –11

Assim, a variável que entra será aquela que contribui com a menor redução no valor da função objetivo, que no caso diz respeito à variável x31. O valor a ser alocado a esta célula deverá ser o máximo, de tal forma que nenhuma célula do caminho fechado fique com valores negativos.Já para a variável que sai, esta deverá ser aquela, com sinal negativo no caminho fechado, com alocação inicial de menor valor absoluto. No caso, para o caminho referente a x31:

x31 x21 x22 x32

Sinal no caminho fechado + – + –Alocação inicial 0 30 50 20

Portanto, x32 deverá ser a variável que sai.Assim sendo, deverá realocar-se o valor da variável que sai pelo “caminho fechado”

da variável que entra.x31 = 0 + 20 = 20x21 = 30 – 20 = 10

90

x22 = 50 + 20 = 70x32 = 20 – 20 = 0O novo quadro resultante é apresentado a seguir:

j i 1 2 3

Ofertaai

1 120=x11 120

2 10=x21

70=x22

80

3 20=x31 60=x33

80

Demandabj 150 70 60

Para verificar a possibilidade de existência de melhores soluções, calcule novamente, a partir dos novos caminhos fechados, os valores das contribuições das variáveis não-básicas. Se todas essas contribuições forem positivas, a solução ótima foi encontrada.

6.3.3- Cálculo da Solução Ótima Através do Problema Dual

A solução ótima de um problema de transporte pode ser também encontrada a partir do Problema Dual. Da mesma forma como o Método de “Stepping-Stone”, o método através do problema dual consiste em uma seqüência de passos (algoritmo) que sempre chega à solução ótima a partir de uma solução inicial.

A partir da solução básica inicial encontrada, este método pesquisará se alguma melhor solução pode ser obtida.Consideremos o quadro abaixo com a solução básica inicial encontrada a partir do Método do Canto Noroeste:

j i 1 2 3 ai

1c11=8

x11=120c12=5 c13=6

a1=120

2c21=15

x21=30c22=10

x22=50c23=12

a2=80

3c31=3 c32=9

x32=20c33=10

x33=60 a3=80

bj b1=150 b2=70 b3=60

Onde ui é a variável dual correspondente as restrições das origens e vj é a variável dual correspondente as restrições dos destinos.

Assim como no Método de “Stepping-Stone”, cada célula vazia (no caso, 9 – (m + n –1) células) representa uma variável não-básica que poderia entrar na base (para entrar, a contribuição específica da variável não-básica deve implicar a redução do custo total).

91

ui

u1

u2

u3

vj v1 v2 v3

Para calcular essas contribuições atribui-se o valor zero a um dos elementos ui ou vj

(qualquer um dos dois) e calcula-se o valor restante para ui ou vj de sorte que, para cada variável básica, ui + vj = Cij. Em seguida, calcula-se para cada variável não-básica, a quantidade Cij-ui-vj (contribuição específica). Se todas essas quantidades forem não-negativas, a solução presente é ótima. Caso contrário, a solução corrente não é ótima.

Calculando-se ui e vj com relação às células das variáveis básicas do quadro acima e escolhendo-se arbitrariamente u2=0, tem-se:Cij = ui + vj

Célula (2,1): C21 = u2 + v1, 15 = 0 + v1, ou v1=15Célula (2,2): C22 = u2 + v2, 10 = 0 + v2, ou v2=10 Célula (1,1): C11 = u1 + v1, 8 = u1 + 15, ou u1= -7Célula (3,2): C32 = u3 + v2, 9 = u3 + 10, ou u3= -1Célula (3,3): C33 = u3 + v3, 10 = -1 + v3, ou v3= 11

Calculando-se Cij-ui-vj para cada uma das células referente às variáveis não-básicas do quadro, tem-se:Célula (1,2): C12-u1-v2 = 5-(-7)-10 = +2Célula (1,3): C13-u1-v3 = 6-(-7)-11 = +2Célula (2,3): C23-u2-v3 = 12-0-11 = +1Célula (3,1): C31-u3-v1 = 3-(-1)-15 = -11

Tendo em vista que, pelo menos um dos valores Cij-ui-vj é negativo, a solução corrente não é ótima e se pode obter uma solução melhor aumentando-se a alocação da célula possuidora do maior valor negativo, no caso, a célula (3,1). O valor a ser alocado a esta célula deverá ser o máximo, de tal forma que nenhuma célula do caminho fechado correspondente fique com valores negativos.

Para a variável que sai o procedimento é o mesmo de “Stepping-Stone”, esta deverá ser aquela, com sinal negativo no caminho fechado, com alocação inicial de menor valor absoluto. No caso, para o caminho referente a x31:

x31 x21 x22 x32

Sinal no caminho fechado + – + –Alocação inicial 0 30 50 20

Portanto, x32 deverá ser a variável que sai.Assim sendo, deverá realocar-se o valor da variável que sai pelo “caminho fechado”

da variável que entra.x31 = 0 + 20 = 20x21 = 30 – 20 = 10x22 = 50 + 20 = 70x32 = 20 – 20 = 0

O novo quadro resultante é apresentado a seguir:j

i 1 2 3Oferta

ai

92

1 120=x11 120

2 10=x21

70=x22

80

3 20=x31 60=x33

80

Demandabj 150 70 60

Para verificar a possibilidade de existência de melhores soluções, atribui-se novamente o valor zero a um dos elementos ui ou vj, calcula-se os outros ui e vj e, em seguida, os valores de Cij-ui-vj (contribuição específica). Se todas essas contribuições forem positivas, a solução ótima foi encontrada.

É importante observar que qualquer dos métodos utilizados, seja “Stepping-Stone” ou através do Problema Dual, a solução ótima encontrada no final do problema de transportes é a mesma.

No planejamento de uma rede de distribuição, a “função transporte” agrega o valor “lugar” ao produto, ou seja, disponibiliza o produto no local onde o mercado o exige. Não adianta nada, do ponto de vista do mercado, o fornecedor dispor de um bom produto que não é encontrado pelo cliente no momento que ele deseja.

Assim, no processo geral de produção e comercialização do produto, o sistema transporte tem um papel fundamental e indispensável e, desta forma, deve ser cuidadosamente planejado com o objetivo de atingir o que se espera dele, com o menor acréscimo no custo final do produto.

Capítulo VII PROGRAMAÇÃO INTEIRA

7.1- INTRODUÇÃO

Um problema de Programação Inteira é um problema de Programação Linear com o requisito adicional de que o valor de todas as variáveis sejam números inteiros. Resolve-se o problema de Programação Linear através de algum método estudado, se a solução for inteira, então este é o resultado do problema de Programação Inteira. Caso contrário vamos usar o algoritmo de Bifurcação e Limite.

7.2- ALGORITMO DE BIFURCAÇÃO E LIMITE

Se a primeira solução contém uma variável não inteira, por exemplo:

xj variável não inteiraentão,

i1 < xj < i2 onde i1 e i2 são inteiros, consecutivos e não-negativos.

93

Dois novos modelos de Programação Inteira são então criados aumentando o problema de Programação Inteira Original com as restrições:

xj ≤ i1 e xj ≥ i2

Este processo chama-se bifurcação e tem o efeito de contrair a região viável de um modo que elimina de considerações posteriores a solução corrente não inteira para xj preservando ainda todas as possíveis soluções inteiras do problema original.

Exemplo:Problema 1:

MAX Z = 10x1 + x2

S.A. 2x1 + 5x2 ≤ 11 x1 , x2 ≥ 0 e inteiros

Resolvendo pelo Método Simplex temos: BASE -Z x1 x2 x3 bi

x3 0 2 5 1 11-z 1 10 1 0 0

BASE -Z x1 x2 x3 bi

x1 0 1 2,5 0,5 5,5-z 1 0 -24 -5 -55

Solução Ótima:x1 =5,5 x2 = 0 Z=55

Como x1 =5,5 não é inteira, então vem:5 < x1 = 5,5 < 6x1 ≤ 5x1 ≥ 6

Problema 2:MAX Z = 10x1 + x2

S.A. 2x1 + 5x2 ≤ 11x1 ≤ 5

x1 , x2 ≥ 0 e inteiros

Problema 3:MAX Z = 10x1 + x2

S.A. 2x1 + 5x2 ≤ 11x1 ≥ 6

x1 , x2 ≥ 0 e inteiros

Como no Problema 2 x2 = 0,2, vem:

94

Solução Ótima:x1 =5 x2 = 0,2 Z=50,2

Solução Ótima:Não possui solução viável

0 < x2 = 0,2 < 1x2 ≤ 0x2 ≥ 1Problema 4:

MAX Z = 10x1 + x2

S.A. 2x1 + 5x2 ≤ 11x1 ≤ 5x2 ≤ 0

x1 , x2 ≥ 0 e inteiros

Problema 5:MAX Z = 10x1 + x2

S.A. 2x1 + 5x2 ≤ 11x1 ≤ 5x2 ≥ 1

x1 , x2 ≥ 0 e inteiros

Como essas aproximações são inteiras não é mais necessário bifurcações adicionais.

7.2.1- LimiteA bifurcação continua até ser obtida uma primeira aproximação inteira. O valor da

FO referente a esta primeira aproximação inteira torna-se um limite inferior (problema de maximização) para o problema e, todos os modelos, cujas primeiras aproximações, inteiras ou não, conduzam a valores da FO menores que o limite inferior, são descartados.

7.2.2- ConsideraçõesBifurca-se sempre a partir do modelo de programação que se revela mais próximo

do ótimo. Quando há um certo número de candidatos a posteriores bifurcações, escolhe-se a que apresentar o maior valor de Z, se a função objetivo for a maximizar, ou a de menor valor de Z, se a função objetivo for a minimizar.

São acrescentadas restrições adicionais, uma de cada vez. Se a primeira aproximação envolver mais de uma variável não inteira, as novas restrições serão impostas sobre a variável que está mais longe de se tornar inteira, isto é, a variável cuja parte decimal estiver mais próxima de 0,5. Em caso de empate, escolhe-se arbitrariamente uma das variáveis.

Exemplo: Se obtemos em um problema o resultado x1 =2,55, x2 = 1,5 com Z = 12,75, como x2 está mais afastado de uma solução inteira que x1 utiliza-se x2 para gerar as bifurcações x2 ≤ 1 e x2 ≥ 2.7.2.3- Diagrama Esquemático

Um diagrama esquemático (árvore) pode ser gerado a partir da resolução do problema pelo algoritmo de Bifurcação e Limite retratando os resultados obtidos.

95

Solução Ótima:x1 =5 x2 = 0 Z=50

Solução Ótima:x1 =3 x2 = 1 Z=31

DIAGRAMA DO EXEMPLO APRESENTADO

1

Exercício Proposto:

Resolva o seguinte problema de programação inteira pelo algoritmo de Bifurcação e Limite e desenvolva seu diagrama:

MAX Z = 3x1 + 4x2

S.A. 2x1 + x2 ≤ 62x1 + 3x2 ≤ 9

x1 , x2 ≥ 0 e inteiros

ANEXO 1

Estudo de Caso: Composição de Fertilizantes

96

Z =55(5,5 ; 0) 3

2

z = 50,2

(5 ; 0,2)

x1 ≤ 5

x1 ≥ 6

Sol. não-viável

x2 ≤ 0

x2 ≥ 1

4

5

z = 50

(5 ; 0)

z = 31

(3 ; 1)