Apostila programação linear

Apostila programação linear

(Parte 1 de 4)

TEXTO – BASE DAS AULAS DE PROGRAMAÇÃO LINEAR 4º. CICLO / MATEMÁTICA

Prof ª. Lúcia Stefani (Org.) UNIMONTE – SANTOS – SP

CAP. I – MODELOS DE PROBLEMAS DE PROGRAMAÇÃO LINEAR 1. Análise de investimentos

Neste modelo de P.L. desejamos maximizar uma função linear, chamada função objetiva a várias variáveis, respeitando-se um sistema linear de desigualdades, que recebem o nome de restrições. As restrições representam limitações nos recursos disponíveis (capital, mão de obra, recursos minerais, fatores de produção, etc.).

Numa marcenaria são fabricadas mesas e escrivaninhas; cada mesa é vendida com um lucro de 3 unidades monetárias (u.m.) e demora 2,5 horas para montagem, 3 horas para polimento e 1 hora para encaixotar; cada escrivaninha é vendida com lucro de 4 u.m. e requer 1 hora para montagem, 3 horas para polimento e 2 horas para encaixotar. A marcenaria dispõe de mão de obra de 20 horas para montagem, 30 horas para polimento e 16 horas para encaixotar. Quantas mesas e quantas escrivaninhas deve a marcenaria produzir, de maneira a obter lucro máximo?

Seja o nº. de mesas e o nº. de escrivaninhas. 1x2x O problema consiste em maximizar a função objetiva: L = 3 + 4 1x2x que atenda as seguintes restrições de mão de obra:

0e 0 )
)entoencaixotam(1621 )
)polimento(30 3 3 )
)montagem(20 1 5,2 )

xxd xxc xxb xxa

2. Problema da dieta

Neste modelo de P.L. procuramos a solução que minimiza uma função objetiva (chamada solução ótima). Cada restrição agora é dada em forma de desigualdade do tipo “maior ou igual”, já que a quantidade de nutrientes a serem consumidos não poderá ser menor que as quantias mínimas exigidas.

Um indivíduo preocupado com a sua saúde, deseja ingerir um mínimo diário de 36 unidades de vitamina A, 28 unidades de vitamina C e 32 unidades de vitamina D. Cada kg de carne custa 9 u.m. e contém 2 unidades de vitamina A, 2 de C e 8 de D; cada kg de peixe custa 12 u.m. e fornece 3 unidades de vitamina A, 2 de C e 2 de D. Qual a combinação de custo mínimo que garante as necessidades diárias?

Para equacionarmos o problema, vamos chamar de a quantidade de carne a ser

consumida e a quantidade de peixe; teremos que procurar a solução que minimiza a função objetiva:

C = 9 + 12 1x2x
E que atenda as restrições:
de)negativida (não0 e 0 )
)D vit.unid.(32 2 8 )
)C vit.unid.(28 2 2 )
)A vit.unid.(36 3 2 )

xxd xxc xxb xxa

OBSERVAÇÃO: a restrição de não negatividade é inerente a todos os problemas de P.L., pelo que não faremos mais referência a ela; graficamente significa que iremos trabalhar apenas no 1º. quadrante do plano cartesiano. CAP. I I – SOLUÇÃO GRÁFICA DE PROBLEMAS DE P. L.

Da Geometria Analítica sabemos que uma desigualdade é representada no plano cartesiano por um semi-plano (na figura 1 temos a representação gráfica da inequação 2x + 3y ≤ 6 ).

Como as restrições dos problemas de P.L. são dadas em forma de desigualdades, então a solução gráfica do conjunto de restrições será um polígono convexo (não necessariamente fechado) que recebe o nome de região de soluções viáveis ( R.S.V.).

A pergunta que surge de imediato é: Qual dos infinitos pontos da R.S.V. corresponde à solução ótima do problema de P.L.? Pode-se demonstrar que a solução ótima (se existir), será um ponto extremo da região.

EXEMPLO I : Max. L = 3 + 4sujeita às restrições 1x2x
(c)162
(b)3033
(a)205,2

x x x

Figura 2

A região de soluções viáveis é o polígono convexo OABCD; a solução ótima será um dos vértices do polígono. Para encontrarmos a solução ótima, vamos inicialmente analisar a equação da função objetiva L = 3 + 4. 1x2x No plano cartesiano essa equação representa uma família de retas paralelas; começamos traçando a reta que anula a função objetiva (reta que passa pela origem e que corresponde a um lucro 0, representando a situação mais desfavorável); em seguida vamos procurar o vértice do polígono pelo qual passa a reta paralela à reta traçada anteriormente, ponto esse que deve ser o mais afastado possível (visto que o problema é de maximização). Na figura 2 esse é o ponto B,

intersecção das restrições b e c; resolvendo-se o sistema de equações⎩⎨⎧

obtém-se o ponto B (4,6). Substituindo os valores de e de na função objetiva, teremos a

solução ótima: = 4 , = 6 e L = 36 u.m. Isso significa que a marcenaria deve fabricar 4 mesas e 6 escrivaninhas, obtendo assim um lucro máximo de 36 u.m.

OBSERVAÇÃO: Se substituirmos na função objetiva as coordenadas de qualquer outro vértice do polígono, iremos obter um valor de L menor que 36; além do mais, os valores de = 4 e = 6 satisfazem todas as restrições do problema, como pode ser observado por substituição direta. 1x 2x

EXEMPLO I :
MinC = 9 + 12 sujeita às restrições 1x2x
(c)3228
(b)2822
(a)3632

x x x

Figura 3

A R.S.V. é o polígono convexo aberto da figura 3. Para encontrarmos o vértice da solução ótima,vamos procurar o ponto extremo do polígono pelo qual passa a reta paralela à reta de equação C = 0 , reta essa que deve ficar o mais próxima possível da outra, visto que agora o problema é de minimização. Esse ponto é o ponto C da figura 3.

As coordenadas do ponto C obtêm-se resolvendo-se o sistema ⎩⎨⎧

onde iremos encontrar o ponto C (6 , 8) e o custo mínimo C = 150.

As coordenadas do ponto C (6 , 8) satisfazem todas as restrições do problema
EXEMPLO I :
MinC = 4 + 2 sujeita às restrições 1x2x

OBSERVAÇÃO: Qualquer outro ponto cujas coordenadas forem substituídas na função objetiva, irão produzir um custo superior a 150 u.m. ⎪⎩

(c)186
(b)142
(a)204

x x x

7 Figura 4

A análise da figura 4 mostra-nos que a reta da restrição b é paralela à reta C = 4 + 2= 0 isto significa que 1x 2x

ou seja, o problema possui infinitas soluções ótimas (dizemos que é um problema degenerado)

qualquer ponto do segmento de reta BC é solução ótima do problema proposto,

OBSERVAÇÃO: Tanto as coordenadas do ponto B (3, 8) como do C (6, 2) produzem na função objetiva um valor igual a 28 u.m., que é o custo mínimo. As coordenadas de qualquer outro ponto da R.S.V. vão produzir um custo superior a 28 u.m.

1) Max. L = 24 + 8sujeita às restrições R: = 4, = 4, L = 128

x x x

2) Max. L = 40+ 50x sujeita às restrições ⎪⎨5R: 1x= 3, 2x= 5, L = 370

x x x

3) Max. L = 40+ 30sujeita às restrições R:x= 4, = 5, L = 310

) Um fazendeiro pretende plantar hectares de arroz e hectares de feijão; cada hectare de

rroz dá um lucro de 50 u.m. e consome 6 homens-hora para plantio, 5 homens-hora para colheita e dá jardineiro necessita de 10, 12 e 12 unidades dos produtos químicos A, B e C respectivamente ara o seu jardim. Um produto líquido custa 30 u.m. e contém 5, 2 e 1 unidades de A, B e C spectivamente; um produto sólido custa 20 u.m. e contém 1, 2 e 4 unidades dos produtos x x x x

armazenagem?

2 homens-hora para armazenagem; cada hectare de feijão um lucro de 30 u.m. e consome 2 homens-hora no plantio, 5 para colheita e 4 para armazenagem. Qual a plantação que produz lucro máximo, se o fazendeiro possui um total de 36 homens-hora para plantio, 40 para colheita e 28 para R: 1x= 5 ha, 2x= 3 ha e L = 340 u.m.

5) Um p re químicos A, B e C respectivamente. Qual a combinação que produz custo mínimo, respeitando-se as necessidades do jardineiro?

R: 1x (líquido) = 1, 2x (sólido) = 5 e C = 130 u.m.

6) Min C = 120 + 60 sujeita às restriçõesR:= 2, = 9, C =

780 I – SOLUÇÃO ALGÉBRICA DE PROBLEMAS DE P. L. – MÉTODO SIMPLEX

. Resumo histórico O método gráfico para resolver problemas de P.L. restringe-se a no máximo 3 variáveis; na orge Dantzig revolucionou o mundo da atem

M.S.) vamos rever alguns conceitos de

. inição 1: Variáveis de folga

As restrições dos problemas de P.L. são dadas em forma de inequações lineares; cada x x x prática, os matemáticos, os economistas e os administradores enfrentam problemas com um número de variáveis bem superior a três, daí a necessidade de um método algébrico geral que permita resolver problemas com qualquer número de variáveis.

Em 1947, o economista norte-americano Ge

Mática Aplicada ao descobrir um método iterativo ao qual deu o nome de método SIMPLEX, nome derivado do problema proposto a Dantzig resolver.

Álgebra Linear, necessários ao bom entendimento do texto

Antes de apresentarmos o método SIMPLEX (

2 Def desigualdade do tipo “menor ou igual” transforma-se em equação linear se acrescentarmos uma variável não negativa chamada variável de folga (na prática, o valor da variável de folga representa a parte do recurso da restrição que não foi utilizada). Para cada restrição teremos uma variável de folga.

Definição 2: Solução compatível básica (S.C.B.)

(Parte 1 de 4)

Comentários