2-nocoes-convexidade

Prévia do material em texto

18 
2- NOÇÕES DE CONVEXIDADE E FORMULAÇÃO MATEMÁTICA DE 
PROBLEMAS DE PROGRAMAÇÃO LINEAR 
2.1 – Noções de Convexidade 
2.1.1 - Combinação Convexa de pontos 
 
Considere C um conjunto contendo os pontos x1 e x2 e α ∈ [0,1]. Diz-se que o 
ponto b = αx1 + (1 -α)x2 é o resultado de uma combinação convexa de x1 e x2. Além 
disso, se fizer-se α + (1- α) terá como resultado o número 1. Pode-se estender esta 
definição para um conjunto de pontos:, 
Diz que o ponto 
b x x x
i n
n
n
i
= + + +
≥ =
�
�
�
��
α α α
α
1
1
2
2
0 1 2
....
( , ,..., )
é uma combinação convexa dos pontos 
x1, x2,...,xn. Então, 
α1 + α2 + ........ + αn = α i
i
n
=
� =
1
1 
Teorema 2.1.1: 
Sejam os pontos u1 e u2 , pertencentes ao ℜℜℜℜn, e u3 um ponto qualquer entre u1 e u2. 
Para algum 0 ≤ α ≤ 1 tem-se: 
α ( u1 - u2) = u3- u2. 
 u3=α u1 + (1-α ) u2 (1). 
 Como cada coeficiente de (1) é maior ou igual a 0, e a soma deles é igual a 1, 
então u3 é uma combinação convexa de u1 e u2. 
2.1.2- Conjuntos Convexos 
 Um subconjunto C∈ Rn é chamado convexo, se e somente se, para quaisquer 
pontos u1 e u2 pertencentes a C qualquer combinação convexa 
b = α 1 u1+α 2 u2 
também pertencer a C. Em outras palavras, se C é convexo, então 
u C
u C
u u C
1
2
1 21
∈
∈
�
�
�
��
	 + − ∈α α( ) (0 ≤ α ≤ 1). 
Portanto, um conjunto C é considerado convexo se todos os pontos do segmento 
de uma reta que une dois pontos de C também pertencem a C. 
 19 
 2.1.3- Ponto Extremo (ou Vértice) 
 Seja C um conjunto convexo. Diz-se que u∈ C é um ponto extremo de C se 
não for possível expressá-lo como uma combinação convexa de quaisquer outros dois 
pontos distintos pertencentes ao conjunto C. 
2.1.4- Intersecção de Conjuntos Convexos 
 Sejam A e B dois conjuntos convexos. Seja S o conjunto intersecção, ou seja, 
S = A ∩∩∩∩ B. Se dois pontos p e q pertencem a S, então o segmento pq pertence a S. 
 Portanto, todos os pontos pertencentes a S satisfazem a condição de 
convexidade. É imediato concluir que a intersecção de um número finito de conjuntos 
convexos é um conjunto convexo. 
 
2.2 – Formulação Matemática de P.P.L’S em R2 
 
 A formulação matemática para os Problemas de Programação Linear é uma 
idealização da realidade, pois emprega símbolos matemáticos para representar as 
variáveis do sistema real. Essas variáveis são relacionadas por equações lineares que 
expressam as restrições do problema através de sistemas lineares e da função 
matemática a ser otimizada, que também é linear. 
 A solução consiste em encontrar valores adequados das variáveis de decisão que 
otimizem o desenvolvimento do sistema, segundo o critério desejado (maximizar ou 
minimizar). 
 A formulação matemática consiste em: 
i) Identificar as variáveis de decisão e determinar a grandeza a ser otimizada, 
expressando-a como uma função matemática (função objetivo). 
ii) Identificar todas as exigências, restrições e limitações estipuladas, expressando-as 
matematicamente (restrições). 
iii) Expressar todas as condições implícitas. Tais condições não são estipuladas 
explicitamente no problema relativo à situação física sendo assim, modeladas. 
Exemplo 2.1: 
Uma pessoa em dieta necessita ingerir pelo menos: 
 - 20 unidades de vitamina A; ( Vitamina A ≥ 20) 
 20 
 - 10 unidades de vitamina B; ( Vitamina B ≥ 10) 
 - 2 unidades de vitamina C. ( Vitamina C ≥ 2) 
 Ela deve conseguir estas vitaminas a partir de dois tipos diferentes de alimentos 
A1 e A2. A quantidade de vitaminas que esses produtos contém por unidade e o preço de 
cada um estão na tabela: 
 Vitamina A Vitamina B Vitamina C Preço Unitário 
Alimento A1 4 1 1 30 u.m. 
Alimento A2 1 2 0 20 u.m. 
 Qual a programação de compras dos alimentos A1 e A2 que essa pessoa deve 
fazer para cumprir sua dieta a menor custo possível? 
 
Resolução: 
Variáveis de decisão: 
x1: quantidade de alimento A1 a ser comprado. 
x2: quantidade de alimento A2 a ser comprado. 
Função objetivo: 
 z = 30x1 + 20x2 
 
Conjunto de restrições: 
 4x1 + x2 ≥ 20 
 x1 + 2x2 ≥ 10 
 x1 ≥ 2 
 x2 ≥ 0 
Problema: 
 min z = 30x1 + 20x2 
s.a 4x1 + x2 ≥ 20 
 x1 + 2x2 ≥ 10 
 x1 ≥ 2 
 x2 ≥ 0 . 
 
Exemplo 2.2: 
Um fabricante de artigos de plásticos possui um estoque de 1200 caixas de 
envôlucos transparentes em uma de suas fábricas e outras 1000 caixas em uma segunda 
 21 
fábrica. O fabricante recebeu pedidos deste produto provenientes de três diferentes 
varejistas nas quantidades de 1000, 700 e 500 caixas respectivamente. Os custos 
unitários de expedição desde as fábricas até os varejistas são os seguintes: 
 
 Varejista 1 Varejista 2 Varejista 3 
Fábrica 1 14 13 11 
Fábrica 2 13 13 12 
 
 Determine o programa de expedição que atenda todas as demandas a partir do 
estoque disponível a um custo mínimo. 
 
Resolução: 
Variáveis de decisão: 
xij : número de caixas a serem expedidas da fábrica i para o varejista j. 
 i = 1, 2 , j = 1, 2, 3. 
Função objetivo: 
 z = 14 x11 + 13 x12 + 11 x13 + 13 x21 + 13 x22 + 12 x23 
Conjunto de restrições: 
 x11 + x12 + x13 = 1200 
 x21 + x22 + x23 = 1000 
 x11 + x21 = 1000 
 x12 + x22 = 700 
 x13 + x23 = 500 
 xij ≥ 0 , i = 1, 2 ; j = 1,2,3. 
Problema: 
 min z = 14 x11 + 13 x12 + 11 x13 + 13 x21 + 13 x22 + 12 x23 
 s.a. x11 + x12 + x13 = 1200 
 x21 + x22 + x23 = 1000 
 x11 + x21 = 1000 
 x12 + x22 = 700 
 x13 + x23 = 500 
 xij ≥ 0 , i = 1, 2 ; j = 1,2,3. 
 
 22 
 
 
Exemplo 2.3: 
Uma pequena indústria produz artigos A1 e A2 que são vendidos a 200 u.m. e 
300 u.m., respectivamente. Na sua produção são utilizados três tipos de matérias-
primas, P1, P2 e P3, que são gastas da seguinte forma: 
- 2 unidades de P1 para fabricar 1 unidade de A1; 
- 4 unidades de P2 para fabricar 1 unidade de A1; 
- 1 unidade de P1 para fabricar 1 unidade de A2; 
- 1 unidade de P3 para fabricar 1 unidade de A2. 
 Por razões econômicas, as matérias-primas P1, P2 e P3, estão disponíveis no 
máximo em 20, 32 e 10 unidades, respectivamente. 
 O dono da empresa deseja saber as quantidades dos produtos A1 e A2 que devem 
ser produzidos para que a receita bruta seja a menor possível. 
 
Resolução: 
Variáveis de decisão: 
x1: quantidade do produto A1 a ser produzida; 
x2: quantidade do produto A2 a ser produzida. 
Função objetivo: 
 z = 200 x1 + 300 x2 
 
Conjunto de restrições: 
 2 x1 + x2 ≤ 20 
 4 x1 ≤ 32 
 x2 ≤ 10 
 x1 , x2 ≥ 0 
Problema: 
 min z = 200 x1 + 300 x2 
 2 x1 + x2 ≤ 20 
 4 x1 ≤ 32 
 x2 ≤ 10 
 x1 , x2 ≥ 0. 
 23 
2.3- Resolução Gráfica dos Problemas de Programação Linear no ℜℜℜℜ 2 
 
 A resolução de Problemas de Programação Linear no ℜ2, pode ser determinada 
graficamente se o problema tem: 
- Solução única; 
- Múltiplas soluções; 
- Solução ilimitada; 
- Infactível (não tem solução). 
 Para isso determina-se inicialmente a região de factiblidade do problema, ou 
seja, a região determinada pelas restrições. A seguir, utiliza-se as curvas de nível e o 
vetor gradiente da função objetivo para determinar o sentido em que a função cresçe 
ou diminui mais rapidamente. 
 Veja alguns exemplos: 
Exemplo 2.3.1 (Solução única):Curva de Nível 
 max z = 2 x1 + x2 Solução ótima 
s.a -x1 + x2 ≤ 1 x2 ≤ 2 
 x1 ≤ 3 
 x2 ≤ 2 
 x1 e x2 ≥ 0 x1 ≤ 3 x1 
 vetor gradiente 
 
 
Exemplo 2.3.2 (Múltiplas soluções): 
max z = x1 + x2 
s.a x1 ≤ 3 
 x2 ≤ 4 x2≤4 
 2x1 + 2x2 ≤ 9 2x1 + 2x2≤9 
 x1 e x2 ≥ 0 
x* = α x1 + (1 - α) x2 (0 ≤ α ≤ 1). x1≤3 
 
 
 
 x2 Infinitas Soluções 
x1 
x2 -x1+x2 ≤ 1 
 24 
x2 Exemplo 2.3.3 (Solução Ilimitada): 
max z = x1 + 2 x2 x1+2x2 ≥ 10 x1 ≥ 2 
 4 x1 + x2 ≥ 20 
 x1 + 2 x2 ≥ 10 soluções ilimitadas 
 x1 ≥ 2 
 x1 e x2 ≥ 0 
 4x1+x2 ≥ 20 x1 
 
 
 Este problema não possui solução ótima finita, pois o valor da função pode 
crescer indefinidamente dentro da região de factibilidade. Dizemos que este é um 
problema ilimitado. 
 
 x2 
Exemplo 2.3.4 (Infactível): 
min. z = x1 + x2 -2x1+x2 ≥ 20 
s.a -2 x1+ x2 ≥ 20 
 x1 - x2 ≥ 2 x1-x2 ≥ 2 
 x1 , x2 ≥ 0 
 x1 
 
 
 
 Neste problema, o conjunto de pontos viáveis é um conjunto vazio, pois não há 
região no plano que satisfaça as quatro restrições. Diz-se que este é um problema 
inviável ou infactível. 
 
 
2.4– Formulação Geral de um Problema de Programação Linear 
 
Nessa seção, será definida um Problema de Programação Linear (P.P.L.) em sua 
forma geral, padrão e canônica, necessárias para a definição de um método para 
resolução desses problemas a ser visto no capítulo 3. 
. 
 25 
2.4.1- Diferentes formas de um Problema de Programação Linear 
 
2.4.1.1 Forma Geral 
 Diz-se que um Problema de Programação Linear está na forma geral se este se 
encontrar na seguinte forma: 
 Max (ou Min) z = c1x1 + c2x2 +…+ cnxn ; 
 s.a. 
 a11x1 + a12x2 + ... + a1nxn ≤ b1 
 . 
 . 
 . 
 ap1x1 + ap2x2 + ... + apnxn ≤ bp 
 a(p+1)1x1 + a(p+1)2x2 + ... + a(p+1)nxn ≥ b(p+1) 
 . 
 . 
 . 
 aq1x1 + aq2x2 + ... + aqnxn ≥ bq 
 a(q+1)1x1 + a(q+1)2x2 + ... + a(q+1)nxn = b(q+1) 
 . 
 . 
 . 
 am1x1 + am2x2 + ... + amnxn = bm 
 x1, ..., xp’ ≥ 0 
 x(p’+1), , xq’ ≤ 0 
 xq’, ..., xn : irrestrita, onde 1 ≤ p ≤ m , 1 ≤ p’ ≤ q’ ≤ n, 1≤q≤m 
 
Exemplo 2.4.1: 
 max z = 5x1+3x2+x3+2x4-4x5 
 s.a.: x1+5x2-3x3 - x4+7x5 ≤ 10 
 3x1-2x2+5x3+ x4+4x5 ≥ 15 
 x1+7x2 - x3+2x4+3x5 ≥ 20 
 5x1+2x2+2x3+3x4- x5 = 8 
 x1≥0, x2≥0, x3≤0, x4 : irrestrita, x5 : irrestrita 
 
 
2.4.1.2- Forma Canônica 
 
 Dizemos que um Problema de Programação Linear está na forma Canônica ou 
na forma de Desigualdade do tipo “≤” se este se encontrar na seguinte forma: 
 Max. (ou Min.) z = c1x1 + c2x2 +…+ cnxn ; 
 s.a.: a11x1 + a12x2 + ... + a1nxn ≤ b1 
 .... 
 am1x1 + am2x2 + ... + amnxn ≤ bm 
 
 
 26 
Na forma matricial: 
 max (ou min) z = cTx 
 s.a. Ax ≤ b 
 x ≥ 0 
onde x,c ∈ ℜn, b ∈ ℜm , A ∈ ℜmxn 
 
Exemplo 2.4.2: Max z 2x1 + 3x2 
 s.a. 5x1 + x2 ≤ 0 
 3x1 + 2x2 ≤ 0 
 x1 + 4x2 ≤ 0 
 x1, x2 ≥ 0 
 
2.4.1.3- Forma Padrão 
Dizemos que um Problema de Programação Linear está na forma Padrão ou na 
forma standard se este se encontrar na seguinte forma matricial: 
max (ou min) z = cTx 
 s.a. Ax = b 
 x ≥ 0 
onde x,c ∈ ℜn, b ∈ ℜm , A ∈ ℜmxn 
 
2.4.5- Transformação de PPL´s gerais na forma padrão. 
Para transformar um Problema de Programação Linear (que se apresenta em 
forma de um sistema de inequações e equações lineares) em um sistema de somente 
equações lineares, deve-se fazer: 
2.4.5.1) Se bi < 0: 
 Deve-se multiplicar a linha i do sistema por (-1). 
 
Exemplo 2.4.3: 
 Max. 5x1 + 3x2 ≈ Max. 5x1 + 3x2 
 sa 2x1 + x2 ≤ 8 sa 2x1 + x2 ≤ 8 
 -x1 + 2x2 ≤ -3 (bi < 0) x1 - 2x2 ≥≥≥≥ 3 
 x1, x2 ≥ 0 x1, x2 ≥ 0 
 
2.4.5.2) Se xi no modelo for livre de sinal ou irrestrito: 
 xi é qualquer ou livre de sinal 	 xi ≥ 0 ou xi ≤ 0. 
 27 
 Escreve-se xi em função de xi’ e xi” , ou seja: 
 xi = xi’ - xi” com xi’ ≥ 0 e xi” ≥ 0. 
 
Exemplo 2.4.4: 
 Max. 5x1 + 3x2 ≈ Max. 5x1 + 3(x2’ – x2’’) 
 sa 2x1 + x2 ≥ 8 sa 2x1 + (x2’ – x2’’) ≥ 8 
 x1 + 2x2 ≥ 3 x1 - 2(x2’ – x2’’) ≥ 3 
 x1 ≥ 0, x2 livre x1, x2’, x2’’ ≥ 0 
 x2 = x2’ – x2’’ 
Observação: 
 Se xi’ = xi” 	 xi =0. 
 Se xi’ > xi” 	 xi > 0. 
 Se xi’ < xi” 	 xi < 0. 
 
2.4.5.3) Ocorrência de xi ≤ 0: 
 Troca-se xi por - xi’, onde xi’ ≥ 0. 
 
Exemplo 2.4.5: 
 Max. 5x1 + 3x2 ≈ Max. 5x1 – 3x2’ 
 sa 2x1 + x2 ≥ 8 sa 2x1 – x2’ ≥ 8 
 x1 + 2x2 ≥ 3 x1 – 2x2’ ≥ 3 
 x1 ≥ 0, x2 ≤ 0 x1, x2, x2’ ≥ 0 
 x2 = – x2’ 
 
2.4.5.4) Se: :: 
 
Soma-se xn+i no membro da esquerda da linha i do sistema e considera-se o 
novo n = n + i (variável de folga), com xn+i ≥ 0. 
 
 
 
 
i
n
1j
jij bxa ≤�
= 
 28 
Exemplo 2.4.5: 
 Max. 5x1 + 3x2 ≈ Max. 5x1 + 3x2 
 sa 2x1 + x2 ≤ 8 sa 2x1 + x2 + x3 = 8 
 -x1 + 2x2 ≤-3 x1 - 2x2 + 0x3 + x4 = 3 
 x1, x2 ≥ 0 x1, x2 ,x3, x4 ≥ 0 
2.4.5.5) Se i
n
1j
jij bxa ≥�
=
 
 
 Subtrair-se xn+i no membro da esquerda da linha i e considerar-se o novo n 
= n + j (variável de excesso), com xn+i ≥ 0. 
 
Exemplo 2.4.6: 
 Max. 5x1 + 3x2 ≈ Max. 5x1 + 3x2 
 sa 2x1 + x2 ≥ 8 sa 2x1 + x2 - x3 = 8 
 x1 + 2x2 ≥ 3 x1 -2x2 - 0x3 - x4 = 3 
 x1, x2 ≥ 0 x1, x2 ,x3, x4 ≥ 0 
 
2.4.5.6) Maximizar uma função objetivo é equivalente a minimizar o seu simétrico, ou 
seja: 
 Máx. z = cTx 	 Min. -z = -cTx.