Pesquisa Operacional

Universidade Salgado de Oliveira – UNIVERSO BH

Engenharia de Produção

Pesquisa Operacional em Sistemas I

Notas de aula

Conteúdo

1 Pesquisa Operacional - Introdução 2

1.1 Conceito 2

1.2 Fases de um Estudo em P.O. 2

1.2.1 Formulação do Problema: 2

1.2.2 Construção do modelo do sistema: 2

1.2.3 Cálculo da solução através do modelo: 2

1.2.4 Teste do modelo e da solução: 3

1.2.5 Estabelecimento de controles da solução: 3

1.2.6 Implantação e acompanhamento: 3

1.3 Programação Matemática 3

1.3.1 Problemas de otimização 3

1.3.2 Programação Linear (PL) 3

1.3.3 Programação Inteira 4

1.3.4 Programação não-linear 4

1.3.5 Convenção da Solução 4

2. Programação Linear 4

2.1 Modelo em programação linear 4

2.2 Solução para Modelos de Programação Linear - Método gráfico 5

2.3 Solução para Modelos de Programação Linear – Método Simplex 5

2.3.1 Descrição do Método Simplex (Problemas de Maximização) 5

2.4 Exercícios. 7

3 Dualidade. 12

3.1 Montagem do Problema Dual 12

3.2 Propriedades 13

4 Análise de Sensibilidade. 13

4.1 Variação dos Recursos 14

4.2 Inclusão de uma nova variável 16

4.3 Mudança nos coeficientes das variáveis da função objetivo. 17

4.3.1 Variável básica. 17

4.3.2 Variável não básica. 19

5 Referências. 20

1 Pesquisa Operacional - Introdução

1.1 Conceito

Método científico de tomada de decisões. Consiste na descrição de um sistema organizado com o auxílio de um modelo, e através da experimentação com o modelo, na descoberta da melhor maneira de operar o sistema.

1.2 Fases de um Estudo em P.O.

1.2.1 Formulação do Problema:

O administrador e o responsável pelo estudo em P.O. deverão analisar o problema para obter uma formulação clara e coerente, definindo os objetivos a alcançar e quais os possíveis caminhos alternativos para que isso ocorra.

Levantar limitações técnicas do sistema e as relações com outros sistemas da empresa ou do ambiente externo.

Validar as possíveis soluções considerando esses obstáculos.

Estabelecer uma medida de eficiência para ordenar as soluções encontradas.

1.2.2 Construção do modelo do sistema:

Construir modelos formados por equações e inequações (modelos matemáticos).

Uma das equações serve para medir a eficiência do sistema para cada solução proposta (função objetivo ou função de eficiência). As outras equações descrevem as restrições ou limitações técnicas do sistema

As variáveis que compõem as equações são de dois tipos:

a) Variáveis controladas ou de decisão: seus valores estão sob o controle do administrador.

b) Variáveis não controladas: seus valores são arbitrados por sistemas fora do controle do administrador.

1.2.3 Cálculo da solução através do modelo:

É feito por meio de técnicas matemáticas específicas. A construção de um modelo deve considerar uma técnica para o cálculo da solução.

1.2.4 Teste do modelo e da solução:

É realizado com dados empíricos do sistema. Usar dados históricos para comparar o desempenho do modelo com o desempenho do sistema.

Reformular ou abandonar o modelo.

1.2.5 Estabelecimento de controles da solução:

Identificar parâmetros fundamentais para a solução do problema. Controlar a mudança desses parâmetros para garantir a validade da solução adotada.

Cálculo de nova solução ou reformulação do modelo.

1.2.6 Implantação e acompanhamento:

Apresentação da solução ao administrador sem usar a linguagem técnica do modelo.

Observar o comportamento do sistema com a solução adotada.

Ajustes.

1.3 Programação Matemática

1.3.1 Problemas de otimização

Maximização ou minimização de uma quantidade específica, chamada objetivo, que depende de um número finito de variáveis de entrada. Estas variáveis podem ser independentes umas das outras ou podem ser relacionadas por meio de uma ou mais restrições.

Um problema de programação matemática é um problema de otimização em que o objetivo e as restrições são expressos como funções matemáticas e relações funcionais.

Nesse contexto a palavra programação significa planejamento e não deve ser confundida com programação de computadores.

1.3.2 Programação Linear (PL)

Um problema de programação matemática é linear se a função objetivo e as restrições são equações/inequações lineares. Será a ênfase do nosso curso.

1.3.3 Programação Inteira

É um problema de programação linear com a restrição adicional de que os valores das variáveis de entrada são números inteiros.

1.3.4 Programação não-linear

É utilizada em modelos contendo funções não- lineares. Isto é, tanto a função objetivo como o conjunto de restrições podem ser funções de grau maior que 1.

1.3.5 Convenção da Solução

Nos problemas de programação matemática busca-se uma solução. Se existir mais de uma solução igualmente ótimas, qualquer uma delas serve. Não há preferência entre soluções igualmente ótimas se não houver preferência estipulada nas restrições.

Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução inicial (que geralmente não é a solução ótima). Um algoritmo é especificado para determinar, a partir desta, uma nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada (supondo que ela existe).

2. Programação Linear

2.1 Modelo em programação linear

A programação linear é uma das técnicas mais utilizadas na abordagem de problemas em pesquisa operacional. Justifica-se sua aplicação pela simplicidade do modelo envolvido e a disponibilidade de uma técnica de solução programável em computador.

O modelo matemático de programação linear é composto de uma função objetivo linear e de restrições técnicas representadas por um grupo de inequações também lineares. A função objetivo ou função de eficiência mede o desempenho do sistema. As restrições garantem que essas soluções estão de acordo com as limitações técnicas impostas pelo sistema.

A construção do modelo matemático é a parte mais complicada de nosso estudo. Não regra fixa para esse trabalho, mas podemos seguir um roteiro que ajuda ordenar o raciocínio. O roteiro contém as seguintes etapas:

Etapa 1: Definir as variáveis de decisão.

Explicitar as decisões que devem ser tomadas e representar as possíveis decisões por meio de variáveis de decisão.

Etapa 2: Definir o objetivo.

Identificar o objetivo da tomada de decisão. A função objetivo é a expressão que calcula o valor do objetivo em função das variáveis de decisão.

Etapa 3: Estabelecer as restrições.

Cada restrição imposta na descrição do sistema deve ser expressa como uma relação linear (igualdade ou desigualdade), formuladas com as variáveis de decisão.

As etapas 1 e 2 do roteiro podem ser executadas simultaneamente.

2.2 Solução para Modelos de Programação Linear - Método gráfico

Resolve modelos de programação linear com duas variáveis de decisão. Essa técnica consiste em representar num sistema de eixos ortogonais o conjunto das possíveis soluções do problema, isto é, representar o conjunto de pontos que obedecem ao grupo de restrições impostas pelo sistema. O desempenho do modelo é avaliado pela representação gráfica da função objetivo.

2.3 Solução para Modelos de Programação Linear – Método Simplex

O Método Simplex é composto por critérios de escolha de soluções básicas que melhorem o desempenho do modelo e de um teste de “otimalidade”. Assim, o problema deve apresentar uma solução básica inicial e as soluções básicas subseqüentes são calculadas com a troca de variáveis básicas por não básicas, gerando novas soluções.

2.3.1 Descrição do Método Simplex (Problemas de Maximização)

Passo 1: Transformação do modelo.

Transformar as restrições do problema de programação linear de inequações em equações com a introdução das variáveis de folga e transformar a função objetivo (z = 0).

Passo 2: Montar um quadro para calcular as soluções.

Montar um quadro 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. Acrescente uma coluna a esquerda para indicar quais são as variáveis básicas.

Passo 3: Escolher a solução inicial.

Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais (variáveis de decisão) e calculando valores positivos para as variáveis de folga. As variáveis igualadas a zero são as variáveis não-básicas e aquelas que os valores foram calculados são as variáveis básicas.

Verifique na última linha do quadro se os coeficientes das variáveis não - básicas não são negativos (maiores ou iguais a zero). Se isto ocorrer, a solução calculada é ótima, senão deve-se calcular outra solução.

Passo 4: Substituir uma variável na base.

Para determinar a substituição determine:

a) Variável que entra na base.

Observe a última linha do quadro e escolha a variável com coeficiente negativo de maior valor absoluto. Essa variável oferece a maior contribuição para o aumento da função objetivo e entrará na base.

b) Variável que sai da base.

Divida os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. O menor valor indica que a variável básica dessa linha sairá da base. Caso não haja elemento algum positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.

Passo 5: Calcular uma nova solução.

Calcular a nova solução básica do sistema empregando-se operações válidas com as linhas da matriz.

Passo 6: Teste de otimalidade.

Ao final do cálculo, verifique na última linha do quadro se os coeficientes das variáveis não básicas não são negativos (maiores ou iguais a zero). Se isto ocorrer, a solução calculada é ótima. Caso contrário, volte ao passo 4 para iniciar outra repetição.

2.4 Exercícios.

Construir o modelo matemático de programação linear dos sistemas descritos a seguir:

1. Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade couro para fabricar uma unidade de cinto. Saben¬do-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 unidades monetárias e o do cinto é de 2 unidades monetárias, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por hora.

2. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 u.m. e o lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal disponível para essas atividades é de 120 horas. As demandas esperadas para os 2 produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do sistema de produção mensal com o objetivo de maximizar o lucro da empresa.

3. Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita transportar 200 caixas de laranjas a 20 u.m. de lucro por caixa, pelo menos 100 caixas de pêssegos a 10 u.m. de lucro por caixa, e no máximo 200 caixas de tangerinas a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o caminhão para obter o lucro máximo? Construa o modelo do problema.

4. Uma rede de televisão local tem o seguinte problema: foi descoberto que o progra¬ma “A" com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 telespectadores, enquanto o programa "B", com 10 minutos de música e 1 minuto de propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana, o patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que não há verba para mais de 80 minutos de música. Quantas vezes por semana cada programa deve ser levado ao ar para obter o número máximo de telespectadores? Construa o modelo do sistema.

5. Um empresa fabrica 2 modelos de cintos de couro. O modelo M1, de melhor qualidade, requer o dobro do tempo de fabricação em relação ao modelo M2. Se todos os cintos fossem do modelo M2, a empresa poderia produzir 1.000 unidades por dia. A disponibilidade de couro permite fabricar 800 cintos de ambos os mode¬los por dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400 para M1 e 700 para M2. Os lucros unitários são de $ 4,00 para M1 e $ 3,00 para M2. Qual o programa ótimo de produção que maximiza o lucro total diário da empresa? Construa o modelo do sistema descrito.

6. Uma empresa, após um processo de racionalização de produção, ficou com disponibilidade de 3 recursos produtivos, R1, R2 e R3. Um estudo sobre o uso desses recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2. Levantando os custos e consultando o departamento de vendas sobre o preço de colocação no mercado, verificou-se que P1 daria um lucro de $ 120,00 por unidade e P2, $ 150,00 por unidade. O departamento de produção forneceu a seguinte tabela de uso de recursos.

Produto Recurso R1 por Recurso R2 por Recurso R3 por

unidade unidade unidade

P1 2 3 5

P2 4 2 3

Disponibilidade de recursos por mês 100 90 120

Que produção mensal de P1 e P2 traz o maior lucro para a empresa? Construa o modelo do sistema.

7. Um fazendeiro está estudando a divisão de sua propriedade nas seguintes ativida¬des 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 (100 kg/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 200 kg por alqueire de adubos e 200.000 Iitros 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 água.

14.000 kg de adubo.

100 alqueires de terra.

Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno? Construa o modelo de decisão.

8. O departamento de marketing de uma empresa estuda a forma mais econômica de aumentar em 30% as vendas de seus dois produtos P1 e P2.

As alternativas são:

a) Investir em um programa institucional com outras empresas do mesmo ramo. Esse programa requer um investimento mínimo de $ 3.000,00 e deve proporcionar um aumento de 3% nas vendas de cada produto, para cada $ 1.000,00 investidos.

b) Investir diretamente na divulgação dos produtos. Cada $ 1.000,00 investidos em P1 retomam um aumento de 4% nas vendas, enquanto que para P2 o retorno é de 10%.

A empresa dispõe de $ 10.000,00 para esse empreendimento. Quanto deverá destinar a cada atividade? Construa o modelo do sistema descrito.

9. Uma liga especial constituída de ferro, carvão, silício e níquel pode ser obtida usando a mistura desses minerais puros além de 2 tipos de materiais recuperados.

Material Recuperado 1- MR1- Composição:

ferro - 60%

carvão - 20%

silício - 20%

Custo por kg: $ 0,20

Material Recuperado 2 - MR2 - Composição:

ferro - 70%

carvão - 20%

silício - 5%

níquel- 5%

Custo por kg: $ 0,25

A liga deve ter a seguinte composição final:

Matéria-prima % mínima % máxima

Ferro 60 65

Carvão 15 20

Silício 15 20

Níquel 5 8

Os custos dos materiais puros são (por kg): ferro: $ 0,30; carvão: $ 0,20; silício: S 0,28; níquel: $ 0,50. Qual deverá ser a composição da mistura em termos dos materiais disponíveis, com menor custo por kg? Construa o modelo de decisão.

10. Uma rede de depósitos de material de construção tem 4 lojas que devem ser abastecidas com 50 m3 (loja 1),80 m3 (loja 2),40 m3 (loja 3) e 100 m3 (loja 4) de areia grossa. Essa areia pode ser carregada em 3 portos P1, P2 e P3, cujas distâncias às lojas estão no quadro (em km):

L1 L2 L3 L4

P1 30 20 24 18

P2 12 36 30 24

P3 8 15 25 20

O caminhão pode transportar 10 m3 por viagem. Os portos tem areia para suprir qualquer demanda. Estabelecer um plano de transporte que minimiza a distância total percorrida entre os portos e as lojas e supra as necessidades das lojas. Construa o modelo linear do problema.

11. Resolva o problema 1 pelo método gráfico. Qual a ociosidade de recursos na solução ótima?

12. Resolva o problema 2 pelo método gráfico. Qual a ociosidade de recursos na solução ótima?

13. Resolva o problema 3 pelo método gráfico.

14. Resolva o problema 4 pelo método gráfico.

15. Resolva o problema 5 pelo método gráfico. Existe disponibilidade de recursos na solução ótima?

Resolver graficamente os modelos de programação linear dos exercícios 16, 17 e 18.

16. Maximizar LUCRO = 2x1 + 3x2

Sujeito a:

− x1 + 2x2  4

x1 + 2x2  6

x1 + 3x2  9

x1  0; x2  0

17. Maximizar RECEITA = 0,3x1 + 0,5x2

Sujeito a:

2x1 + x2  2

x1 + 3x2  3

x1  0; x2  0

18. Minimizar CUSTO = 10x1 + 12x2

Sujeito a:

x1 + x2  20

x1 + x2  10

5x1 + 6x2  54

x1  0; x2  0

19. Resolva os problemas anteriores pelo método simplex.

3 Dualidade.

O termo dualidade refere-se ao fato de que cada modelo de programação linear consiste de duas formas. A primeira, ou original, é chamada de primal e a segunda forma do modelo é chamada de dual. Os modelos primal e dual são completamente inter-relacionados de tal maneira que a solução ótima de um fornece informações completas sobre o outro. Isto quer dizer que ao se calcular a solução ótima de uma das formas do modelo, é possível calcular a solução ótima do outro modelo.

Em determinadas situações, a quantidade de cálculos necessária para resolver um modelo linear pelo método Simplex pode ser reduzida. O modelo primal pode ser substituído por um modelo dual com solução mais rápida.

Observações:

a) Variáveis de decisão do modelo dual: indicam o valor do recurso por unidade.

b) Função objetivo: calcula o valor total do estoque de recursos.

c) O modelo dual permite determinar o valor mínimo, por exemplo, do estoque total pelo menos iguais aos lucros unitários fornecidos.

3.1 Montagem do Problema Dual

Seja o seguinte problema de programação linear, em forma literal:

O dual desse problema pode ser escrito da seguinte maneira:

Para modelos que as restrições são desigualdades do tipo ≤ , o modelo dual é construído a partir do primal da seguinte maneira:

1. Cada restrição em um problema corresponde a uma variável no outro.

2. Os elementos do lado direito das restrições em um problema são os coeficientes da função objetivo do outro problema.

3. Se o objetivo de um problema é maximizar, do outro será minimizar.

4. O problema de maximização tem restrições com sentido ≤ e o problema de minimização tem restrições com sentido ≥.

5. As variáveis de ambos os problemas são não negativas.

3.2 Propriedades

1. A solução ótima primal corresponde à solução ótima dual (Z = W).

2. O coeficiente da variável de decisão na função objetivo primal é o valor da variável de folga correspondente na solução dual.

Coeficiente de xi = valor de yFi

3. O coeficiente da variável de folga da função objetivo primal é o valor da variável de decisão correspondente na solução dual.

Coeficiente de xFi = valor de yi

4. O dual do modelo dual é o modelo primal.

Como conseqüência da propriedade 4 temos que

Coeficiente de yi = valor de xFi e Coeficiente de yFi = valor de xi

4 Análise de Sensibilidade.

Um modelo de programação linear inclui dados cujos valores dependem do mercado e do processo usado na elaboração dos produtos. Estes dados podem sofrer variações com o tempo ou com a inclusão de novas informações. É importante pesquisar a estabilidade da solução adotada, em face dessas variações.

A análise de sensibilidade ou de pós−otimização da solução ótima tem o objetivo de determinar as condições para as quais a solução ótima obtida é válida. O seguinte modelo servirá de exemplo para o estuda da análise de sensibilidade.

Variáveis de decisão:

x1: quantidade a produzir do produto P1.

x2: quantidade a produzir do produto P2.

x3: quantidade a produzir do produto P3.

Maximizar Lucro = x1 +2x2 +3x3

Restrições

x1 + x2 + x3 ≤ 10 (Recurso 1)

2x1 + x2 +4 x3 ≤ 12 (Recurso 2)

x1 + 3x2 − x3 ≤ 9 (Recurso 3)

x1 ≥ 0, x2 ≥ 0 e x3 ≥ 0

O Quadro inicial para aplicação do método SIMPLEX é

Base x1 x2 x3 f1 f2 f3 b

1 1 1 1 0 0 10

2 1 4 0 1 0 12

1 3 −1 0 0 1 9

Lucro −1 −2 −3 0 0 0 0

A aplicação do método SIMPLEX na solução gera o seguinte quadro

Base x1 x2 x3 f1 f2 f3 b

f1 0,154 0 0 1 −0,308 −0,231 4,231

x3 0,385 0 1 0 0,231 −0,077 2,077

x2 0,462 1 0 0 0,077 0,308 3,692

Lucro 1,077 0 0 0 0.846 0,385 13,615

4.1 Variação dos Recursos

Determinação do intervalo de variação do Recurso 1 que mantém a solução ótima.

No quadro inicial da resolução do SIMPLEX é possível indicar a variação do recurso 1 do seguinte modo

No quadro final a variação do Recurso 1 pode ser indicada assim

Para que a solução se mantenha ótima é preciso que

4,231 + Δ ≥ 0, logo Δ ≥ −4,231

Voltando a situação inicial, obteremos o seguinte intervalo

10 + (−4,231) = 5,769 → [5,769; +∞)

Qualquer valor maior ou igual a 5,679 mantém a solução ótima.

De maneira análoga é possível determinar o intervalo de variação do Recurso 2 que mantém a solução ótima. Do quadro inicial a variação do Recurso 2

No quadro final a variação pode ser indicada assim

Mas para que a solução seja ótima é necessário que:

4,231 – 0,308Δ ≥ 0, 2,077+0,231Δ ≥ 0 e 3,692+0,077Δ ≥ 0

Resolvendo as inequações temos que −8,991 ≤ Δ ≤ 13,737.

E o intervalo de variação do recurso 2 será:

12 − 8,991 = 3,009 e 12 + 13,737 = 25,737 → [3,009 ; 25,737]

Determinação do intervalo de variação do Recurso 3. Do quadro inicial

E do quadro final

Em que é necessário

4,231 − 0,231Δ ≥ 0; 2,077 – 0,077Δ ≥ 0 e 3,692 + 0,308Δ ≥ 0.

Resolvendo as inequações: −11,987 ≤ Δ ≤ 18,316.

E o intervalo de variação do recurso é [−2,98; 27,316]

4.2 Inclusão de uma nova variável

Suponha a fabricação de um novo produto P4, que usa os mesmos recursos dos outros três produtos já existentes e que não é possível aumentar a disponibilidade desses recursos. Isto significa que o produto P4 concorrerá em termos de recursos com os outros produtos. Qual deve ser o lucro mínimo de P4 para justificar sua fabricação?

É preciso incluir uma nova variável x4 (que indica a quantidade a produzir do produto P4) e a função objetivo fica

Lucro = x1 +2x2 +3x3+c4x4

O lucro unitário é o coeficiente c4 que precisamos calcular.

Suponha que um levantamento de dados indicou que a produção de P4 requer uma unidade do recurso 1, uma unidade do recurso 2 e duas unidades do recurso 3. Com estas informações é possível escrever as restrições da seguinte maneira

x1 + x2 + x3 + x4 ≤ 10 (Recurso 1)

2x1 + x2 +4 x3 + x4 ≤ 12 (Recurso 2)

x1 + 3x2 − x3 + 2x4 ≤ 9 (Recurso 3)

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 e x4 ≥ 0

A restrição gerada por essa nova variável no modelo dual pode ser escrita assim

y1 + y2 + 2y3 ≥ c4

Pelo quadro final do SIMPLEX, sabe-se que y1 = 0, y2 = 0,846 e y3 = 0,385. Substituindo esses valores na restrição do dual temos

0 + 0,846 + 2(0,385) ≥ c4

0,846 + 0,770 ≥ c4

1,616 ≥ c4 ou c4 ≤ 1,616

E o lucro unitário do novo produto seria de 1,616, isto é, para que a restrição do dual referente ao produto P4 seja uma sentença verdadeira deve-se ter

c4 ≤ 1,616

Observação: Se a solução do dual deixar de ser ótima a do primal também deixará de ser ótima.

Suponha c4 = 1,5 e verifique se a solução permaneceria ótima.

4.3 Mudança nos coeficientes das variáveis da função objetivo.

4.3.1 Variável básica.

Nessa seção serão estudados os intervalos de variação dos coeficientes das variáveis x2 e x3 de modo a não alterar a solução ótima.

A solução de um quadro se altera quando uma variável não básica entra na base. No caso do quadro final, a entrada das variáveis x1, f2 ou f3. Como o objetivo é maximizar o lucro, a solução permanecerá ótima se o aumento do lucro em consequência dessa inclusão pelo menos compensar a diminuição devido às alterações nas outras variáveis.

Assim, o intervalo de estabilidade para o coeficiente de x2 será determinado a partir da análise da entrada das variáveis não básicas.

Determinação do intervalo de estabilidade do coeficiente de x2.

a) Entrada de x1.

O quadro final, na coluna dos coeficientes de x1, mostra as alterações referentes às variáveis básicas do modelo se o valor de x1 aumentar de 0 para 1. Analisando o quadro concluímos que f1 diminui em 0,154, x3 diminui em 0,385 e x2 diminui em 0,462. Logo, se x1 aumenta de 0 para 1, o lucro aumentará de 1 × 1 = 1 unidade (o coeficiente de x1 é 1) e a diminuição devido as outras variáveis é dada por: 0,154× 0 + 0,385×3 + 0,462c2.

Como já vimos, o aumento do lucro deve pelo menos compensar a alteração das outras variáveis. Logo,

1,155 + 0,462c2 = 1

0,462c2 = 1 − 1,155

0,462c2 = − 0,155

c2 = − 0,155/0,462

c2 = − 0,335

b) Entrada de f2.

Supondo que f2 aumenta de 0 para 1, o lucro aumentará 0× 1 = 0 e a diminuição devido as outras variáveis é dada por: −0,308 × 0 + 0,231 × 3 + 0,077c2.

Como o aumento do lucro deve pelo menos compensar a alteração das outras variáveis,

0,693 + 0,077c2 = 0

0,077c2 = −0,693

c2 = −0,693/0,077

c2 = −9

c) Entrada de f3.

Supondo o aumento de f3 de 0 para 1, o aumento do lucro será 0× 1 = 0 e a diminuição devido as outras variáveis é dada por: −0,231 × 0 − 0,077 × 3 + 0,308c2.

Como o aumento do lucro deve pelo menos compensar a alteração das outras variáveis,

−0,231 + 0,308c2 = 0

0,308c2 = 0,231

c2 = 0,231/0,308

c2 = 0,75

Ordenando os valores encontrados em (a), (b), (c) e o coeficiente atual:

−9 ≤ −0,335 ≤ 0,75 ≤ 2

A partir dessa ordenação é possível concluir que a solução é estável para c2 ≥ 0,75 (observe que o coeficiente atual, 2, é maior que todos os outros valores encontrados).

Determinação do intervalo de estabilidade do coeficiente de x3.

De modo análogo, é possível determinar o intervalo para o coeficiente da variável x3.

a) Entrada de x1.

0,154 × 0 + 0,385c3 + 0,462 × 2 = 1

0,385c3 + 0,924 = 1

0,385c3 = 1 − 0,924

0,385c3 = 0,076

c3 = 0,076/0,385

c3 = 0,197

b) Entrada de f2.

−0,308 × 0 + 0,231c3 + 0,077 × 2 = 0

0,231c3 + 0,154 = 0

0,231c3 = −0,154

c3 = −0,154/0,231

c3 = −0,667

c) Entrada de f3.

− 0,231 × 0 − 0,077 c3 + 0,308 × 2 = 0

− 0,077 c3 + 0,616 = 0

− 0,077 c3 = − 0,616

c3 = 0,616/0,077

c3 = 8

Ordenando os valores encontrados em (a), (b), (c) e o coeficiente atual:

−0,667 ≤ 0,197 ≤ 3 ≤ 8

A partir dessa ordenação conclui-se que a solução é estável para 0,197 ≤ c3 ≤ 8 (observe que o coeficiente atual, 3, é um valor entre 0,197 e 8).

4.3.2 Variável não básica.

Usar o modelo dual com a restrição gerada pela variável de decisão.

Determinação do intervalo de estabilidade do coeficiente de x1.

A restrição do dual é y1 + 2y2 + y3 ≥ 1. Para estudar a variação do coeficiente usaremos a restrição da seguinte maneira

y1 + 2y2 + y3 ≥ 1 + Δ

Substituindo os valores

0 + 2 (0,846) + 0,385 ≥ 1 + Δ

1,692 + 0,385 ≥ 1 + Δ

2,077 ≥ 1 + Δ

Δ ≤ 2,077 − 1

Δ ≤ 1,077

Fazendo c1 = 1 + Δ

c1 ≤ 1 + 1,077

c1 ≤ 2,077

E a solução é estável para c1 ≤ 2,077.

5 Referências.

ANDRADE, E. L., Introdução à Pesquisa Operacional: Métodos e Modelos para Análise de Decisões. 3ª. Edição. LTC Editora. Rio de Janeiro, 2002.

BRONSON, R. .Pesquisa Operacional, McGraw Hill ,1985

GOLDBARG, M. C. & LUNA, H. P. L. Otimização Combinatória e Programação Linear, Campus, 2000.

PRADO, D. Programação Linear. Belo Horizonte, Ed. Desenvolvimento Gerencial, 1999.

SILVA, Ermes Medeiros et al.. Pesquisa Operacional. Atlas, 1998