Aplicações de Programação Linear

Aplicações de Programação Linear
em Otimização Estrutural

autores
Rodrigo Evangelista de Castro
Vinicius Maia Barreto de Oliveira

professores
Ronaldo Carvalho Batista
Francisco de Assis das Neves

COPPE / UFRJ
Programa de Engenharia Civil
Novembro de 1998

Índice

1 - Problema Simples

2 - Viga Protendida

3 - Pórtico Submetido a Colapso Plástico

1) Resolver o problema de maximização:

s.a.

a) Graficamente

O ponto que maximiza a função objetivo dentro das restrições impostas é (x1=8, x2=12), onde a região viável está compreendida pelos planos azuis, verdes e no semi-espaço delimitado pelo plano cinza que não contém a origem (ou que contém este ponto).

b) Usando a biblioteca interna de funções do Maple (Simplex)

{x1 = 8, x2 = 12}

c) Usando o método de Simplex via quadros

i) Forma Padrão

Variáveis não básicas: x₁= x₂=0

Variáveis básicas: x₃= 8

₄

₅

Logo apesar de o sistema estar na forma "padrão", ele não está na forma canônica, pois a soluçào básica não é compatível, já que x₅ é negativa. Deste modo, é necessária a inclusão de uma variável artificial x₆na equação (c), que tomará o lugar de x₅na base inicial. Chegando à seguinte formulação:

ii) Forma Canônica

A solução compatível básica será:

Variáveis não básicas: x₁=x₂=x_3;

Variáveis básicas: x₃=8; x₄=12; x₆=36.

Os sistemas na forma padrão e canônica só serão equivalentes se a variável artificial x₆ for nula. Ao se conseguir obter uma base a partir da forma canônica que não inclua x₆ esta condição será satisfeita.

iii) Primeiro passo - minimização da variável artificial

Como x₆ não pode ser negativa, então o seu valor mínimo será igual a zero, assim x₆ é excluída da base.

iv) Minimização da função auxiliar

		-f'	x₁	x₂	x₃	x₄	x₅	x₆	b
(0)	Base	1	0	0	0	0	0	-1	0
(1)	x₃	0	1	0	1	0	0	0	8
(2)	x₄	0	0	1	0	1	0	0	12
(3)	x₆	0	6	4	0	0	-1	1	36

Eliminando da função objetivo a variável básica x₆, vem:

		-f'	x₁	x₂	x₃	x₄	x₅	x₆	b
(0)	Base	1	6	4	0	0	-1	0	36
(1)	x₃	0	1	0	1	0	0	0	8
(2)	x₄	0	0	1	0	1	0	0	12
(3)	x₆	0	6	4	0	0	-1	1	36

Pivoteamento: (3) à (3) / 6
Escalonamento: (1) à (1) - (3)
(0)à (0) - 6.(3)

O maior positivo, x₁, entra na base, já que invertemos o sinal de f. A variável de menor razão (b_i/x_1i) positiva é a que sai da base, x₆.

		-f'	x₁	x₂	x₃	x₄	x₅	x₆	b
(0)	Base	1	0	0	0	0	0	-1	0
(1)	x₃	0	0	-2/3	0	0	1/6	-1/6	2
(2)	x₄	0	0	1	0	1	0	0	12
(3)	x₁	0	1	2/3	0	0	-1/6	1/6	6

Como houve empate, já que -f'à x₁=x₂=x₃=x₄=x₅=0 como os maiores positivos, escolheu-se arbitrariamente x5 para entrar na base e saindo o de f. A variável de menor razão (b_i/x_5i) positiva é a que sai da base, x₃.

		-f'	x₁	x₂	x₃	x₄	x₅	x₆	b
(0)	Base	1	0	0	0	0	0	-1	0
(1)	x₅	0	0	-4	0	0	1	-1	12
(2)	x₄	0	0	1	0	1	0	0	12
(3)	x₁	0	1	0	0	0	0	0	8

Logo o valor mínimo de f' foi zero.

O processo parou já que todas as variáveis da base estão escalonadas e pivoteadas, gerando a seguinte solução compatível básica, desprezando-se a variável artificial x₆.

Variáveis não-básicas: x₂= x₃= 0

₁

₄

₅

v) Minimização da função objetivo via quadros ( variável artificial já eliminada)

		-f'	x₁	x₂	x₃	x₄	x₅	b
(0)	Base	1	6	10	0	0	0	0
(1)	x₅	0	0	-4	0	0	1	12
(2)	x₄	0	0	1	0	1	0	12
(3)	x₁	0	1	0	0	0	0	8

		-f'	x₁	x₂	x₃	x₄	x₅	B
(0)	Base	1	0	10	0	0	0	-48
(1)	x₅	0	0	-4	0	0	1	12
(2)	x₄	0	0	1	0	1	0	12
(3)	x₁	0	1	0	0	0	0	8

Saindo a variável x₄ e entrando a x₂.

		-f'	x₁	X₂	x₃	x₄	x₅	B
(0)	Base	1	0	0	0	-10	0	-168
(1)	X₅	0	0	0	0	4	1	60
(2)	X₂	0	0	1	0	1	0	12
(3)	x₁	0	1	0	0	0	0	8

è Chegou-se assim à solução ótima, ou seja, x₁=8 e x₂=12 fornecem o mínimo valor de f=-6x₁-10x₂ ou máximo de f*=6x₁+10x₂.

2) Otimizar a viga contínua protendida quanto à sua protensão:

Determinar as variáveis de projeto F₀, Y₁ e Y₂, para duas combinações de carregamentos e limites de tensões normais.

Configuração e seção transversal

a) Combinação 1 de Carregamento:

carregamento ® F₀ + G

limites de tensões ® s_sup = 150 t/m²

s _inf = -1500 t/m²

restrições laterais ® 0,1 m £ Y_j £ 0,9 m j = 1, 2

i) Carga equivalente à protensão F₀

ii) Momentos nas seções de interesse: 1 - meio dos vãos; 2 - apoio intermediário

1. Devido à carga equivalente de protensão ( Q )

(positivo)

2. Devido à carga externa ( G = 2,0 t/m )

(negativo)

iii) Propriedades da viga

⁴

iv) Formulação geral das restrições das tensões normais limites

v) Formulação geral do problema de otimização

₀

restrições laterais das variáveis de projeto

( restrição de configuração do cabo )

vi) Linearização do problema de otimização

₀

F₀.Y_j ® X_j

através da substituição das propriedades da viga e separação das restrições vem:

MIN X0

SUBJECT TO

2) -3.3915 X0 + 4.4762 X1 - 2.2376 X2 £ -297.6275 (restrições de tensões)
3) -3.3915 X0 + 4.4762 X1 - 2.2376 X2 ³ -1947.6275
4) -1.1539 X0 - 4.4762 X1 + 2.2376 X2 £ 597.6275
5) -1.1539 X0 - 4.4762 X1 + 2.2376 X2 ³ -1052.3725
6) -0.0351 X0 - 8.9525 X1 + 4.4762 X2 £ 1045.2551
7) -0.0351 X0 - 8.9525 X1 + 4.4762 X2 ³ -604.7449
8) -4.5104 X0 + 8.9525 X1 - 4.4762 X2 £ -745.2551
9) -4.5104 X0 + 8.9525 X1 - 4.4762 X2 ³ -2395.2551
10) X1 - 0.9 X0 £ 0 (restrições laterais)
11) X1 - 0.1 X0 ³ 0
12) X2 - 0.9 X0 £ 0
13) X2 - 0.1 X0 ³ 0
14) X2 - X1 ³ 0
15) 0.5 X0 - 2 X1 + X2 ³ 0 (configuração parabólica do cabo)

vii) Solução via Método Simplex ( LINDO )

OBJECTIVE FUNCTION VALUE

1) 97.49889

VARIABLE VALUE REDUCED COST

X0     97.498886     0.000000
X1     9.749888     0.000000
X2     87.748993     0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 185.744675 0.000000
3) 1464.255249 0.000000
4) 557.426758 0.000000
5) 1092.573242 0.000000
6) 743.181152 0.000000
7) 906.818848 0.000000
8) 0.000000 0.130826
9) 1650.000000 0.000000
10) 77.999107 0.000000
11) 0.000000 -1.171221
12) 0.000000 0.585604
13) 77.999107 0.000000
14) 77.999107 0.000000
15) 116.998657 0.000000

NO. ITERATIONS= 4

que através das transformações inversas:

são finalmente encontrados os valores das variáveis de projeto originais

F₀ = 97.498886 t

Y₁ = 0,1 m

Y₂ = 0,9 m

b) Combinação 2 de Carregamento:

carregamento ® 0,8.F₀ + G + P
limites de tensões ® s_sup = 0 t/m²

s _inf = -1200 t/m²

restrições laterais ® 0,1 m £ Y_j £ 0,9 m j = 1, 2

i) Carga equivalente à protensão F₀

ii) Momentos nas seções de interesse: 1 - meio dos vãos; 2 - apoio intermediário

1. Devido à carga equivalente de protensão ( 0,8.Q )

(positivo)

2. Devido à carga externa ( E = G + P = 3,0 t/m )

(negativo)

iii) Propriedades da viga

⁴

iv) Formulação geral das restrições das tensões normais limites

v) Formulação geral do problema de otimização

₀

sujeita para: restrições das tensões normais limites

restrições laterais das variáveis de projeto

( restrição de configuração do cabo )

vi) Linearização do problema de otimização

₀

F₀.Y_j ® X_j

através da substituição das propriedades da viga e separação das restrições vem:

MIN X0

SUBJECT TO

2) -2.7132 X0 + 3.5804 X1 - 1.7902 X2 <= -671.4414
3) -2.7132 X0 + 3.5804 X1 - 1.7902 X2 >= -1871.4414
4) -0.9232 X0 - 3.5804 X1 + 1.7902 X2 <= 671.4414
5) -0.9232 X0 - 3.5804 X1 + 1.7902 X2 >= -528.5586
6) -0.0280 X0 - 7.1620 X1 + 3.5804 X2 <= 1342.8827
7) -0.0280 X0 - 7.1620 X1 + 3.5804 X2 >= 142.8827
8) -3.6084 X0 + 7.1620 X1 - 3.5804 X2 <= -1342.8827
9) -3.6084 X0 + 7.1620 X1 - 3.5804 X2 >= -2542.8827
10) X1 - 0.9 X0 <= 0
11) X1 - 0.1 X0 >= 0
12) X2 - 0.9 X0 <= 0
13) X2 - 0.1 X0 >= 0
14) X2 - X1 >= 0
15) 0.5 X0 - 2 X1 + X2 >= 0

vii) Solução via Método Simplex ( LINDO )

1) 219.6205

VARIABLE VALUE REDUCED COST

X0     219.620499     0.000000
X1     21.962049     0.000000
X2     197.658447     0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 199.648148 0.000000
3) 1000.351868 0.000000
4) 598.979797 0.000000
5) 601.020203 0.000000
6) 798.627991 0.000000
7) 401.372009 0.000000
8) 0.000000 0.163544
9) 1200.000122 0.000000
10) 175.696396 0.000000
11) 0.000000 -1.171303
12) 0.000000 0.585553
13) 175.696396 0.000000
14) 175.696396 0.000000
15) 263.544586 0.000000

NO. ITERATIONS= 4

que através das transformações inversas:

são finalmente encontrados os valores das variáveis de projeto originais

F₀ = 219.620499

Y₁ = 0,1 m

Y₂ = 0,9 m

c) Comprovação Gráfica:

Atribuindo um valor para uma das variáveis, Y₂=0,9, pode-se resolver o problema graficamente nas duas variáveis restantes: Y₁ e F₀. Este procedimento foi realizado no software matemático Maple encontrando as seguintes configurações:

i) Combinação 1 de carregamento ( X₀ - abcissas, X₁ - ordenadas )

ii) Combinação 2 de carregamento ( X₀ - abcissas, X₁ - ordenadas )

Para ambos os casos de carregamento, comprovou-se os resultados encontrados pela resolução do problema de programação linear com a solução gráfica apresentada.

3) Formular o problema de programação linear para o projeto de peso mínimo do pórtico abaixo contra o colapso plástico e encontrar a solução após atribuir valores a p e l :

Primeiramente será necessário explicitar os momentos {M} como uma função linear dos redundantes {N}. Usando o método das forças pode-se computar o vetor de momentos devidos às cargas aplicadas {M₀} além da matriz de momentos devidos a valores unitários dos redundantes [F_M]. A expressão para {M} é a seguinte:

₀

Desta forma o problema de otimização linear fica com o seguinte formato:

s.a. -[T] {M_p} £ {M₀} + [F_M]{N} £ [T] {M_p}

Sendo [T] a matriz formadas de 0 e 1 onde, se T_ij=0, o iésimo momento plástico não governa a seção j. Desta forma estas restrições acima impedem que os momentos atuantes excedam a capacidade limite dos membros.

Ainda é necessário se fazer uma transformação para evitar que as variáveis de projeto sejam negativas, assim soma-se um vetor com valores positivos ({N^U}) ao vetor dos redundantes de forma que o resultante {X} seja positivo.

Acima tem-se as localizações dos esforços redundantes além da representação física de M₀.

Os coeficientes da matriz [F_m] são mostrados abaixo e significam os momentos gerados no pórtico em função de um valor unitário dos redundantes.

Assim as restrições ficam da seguinte forma:

E a função objetivo:

Adotando valores para P e L (P=100 e L=10) e usando o lindo chega-se aos seguintes formulação de entrada para o lindo:

SUBJECT TO

2) X1 - MPa <= 10000
3) 0.5 X1 - 0.5 X2 + X3 + 0.5 X4 + 0.5 X5 - MPa <= 20500
4) X2 - MPa <= 10000
5) - 0.5 X1 + 0.5 X2 + X3 + 0.5 X4 + 0.5 X5 - MPa <= 22500
6) 0.5 X1 - 0.5 X2 + X3 - 0.5 X4 + 0.5 X5 - MPb <= 10500
7) X3 - MPb <= 10000
8) - 0.5 X1 + 0.5 X2 + X3 + 0.5 X4 - 0.5 X5 - MPb <= 12500
9) X4 - MPa <= 10000
10) 0.5 X4 - 0.5 X5 + X6 - MPa <= 9250
11) X5 - MPa <= 10000
12) -0.5 X4 + 0.5 X5 + X6 - MPa <= 15250
13) 0.5 X4 - 0.5 X5 + X6 - MPb <= 9250
14) X6 - MPb <= 10000
15) -0.5 X4 + 0.5 X5 + X6 - MPb <= 15250
16) X1 + MPa >= 10000
17) 0.5 X1 - 0.5 X2 + X3 + 0.5 X4 + 0.5 X5 + MPa >= 20500
18) X2 + MPa >= 10000
19) - 0.5 X1 + 0.5 X2 + X3 + 0.5 X4 + 0.5 X5 + MPa >= 22500
20) 0.5 X1 - 0.5 X2 + X3 - 0.5 X4 + 0.5 X5 + MPb >= 10500
21) X3 + MPb >= 10000
22) - 0.5 X1 + 0.5 X2 + X3 + 0.5 X4 - 0.5 X5 + MPb >= 12500
23) X4 + MPa >= 10000
24) 0.5 X4 - 0.5 X5 + X6 + MPa >= 9250
25) X5 + MPa >= 10000
26) -0.5 X4 + 0.5 X5 + X6 + MPa >= 15250
27) 0.5 X4 - 0.5 X5 + X6 + MPb >= 9250
28) X6 + MPb >= 10000
29) -0.5 X4 + 0.5 X5 + X6 + MPb >= 15250

Chegando aos seguintes resultados:

OBJECTIVE FUNCTION VALUE

1) 245000.0

VARIABLE VALUE

MPA 1750.000000
MPB 1750.000000

X1     8250.000000
X2     11750.000000
X3     10750.000000
X4     8250.000000
X5     11750.000000
X6     11750.000000

NO. ITERATIONS= 15

Como o vetor { N^U} foi tomado por elementos de valor igual a 10000 podemos encontrar os valores dos redundantes {N} subtraindo-se este valor dos valores de {X}.

X1 8250.000000 à N1= -1750.00

X2 11750.000000 à N2= 1750.00

X3 10750.000000 à N3= 750.00

X4 8250.000000 à N4= -1750.00

X5 11750.000000 à N5= 1750.00

X6 11750.000000 à N6= 1750.00