4- Dualidade em Programação Linear
Transcrição
4- Dualidade em Programação Linear
4- Dualidade em Programação Linear 4.1- Introdução Considere o problema clássico da dieta: (problema primal): Quer-se consumir quantidades de determinados alimentos de tal forma a satisfazer as necessidades mínimas de nutrientes exigidas a um custo mínimo dispendido, problema este ilustrado pelo quadro seguinte. alimentos proteínas (g) sais minerais (g) custo (R$) a1 3 2 25 a2 4 3 35 a3 5 4 50 a4 3 3 33 a5 6 3 36 necessidades mín. de nutrientes 42 24 (4.1) Considerando-se: aij : percentual do componente i presente no alimento j; xj : quantidade do componente j presente na dieta a ser feita; cj : preço por grama de cada ingrediente; bi : quantidade mínima de cada ingrediente a ser consumida na dieta. aj: coluna j da matriz do sistema; Então, o Modelo Primal pode ser sistematizado da seguinte forma: minimizar 25 x1 + 35 x2 + 50 x3 + 33 x4 + 36 x5 sujeito a : 3 x1 + 2 x1 + x1 ; 4 x2 + 3 x2 + x2 ; 5 x3 + 3 x4 + 6 x5 ≥ 42 4 x3 + 3 x4 + 3 x5 ≥ 24 x3 ; x4 ; x5 ≥ 0 4.2- Formulação do modelo dual Suponha que um vendedor de pílulas e sais minerais propõe substituir a dieta de alimentos expressa de acordo com o quadro (4.1), por uma dieta de pílulas, com as seguintes condições: 1- a pílula de uma unidade (g) de proteína custará w1 ; 2- “ “ “ “ “ “ “ sais minerais “ w2 ; 3- os preços w1 e w2 serão fixados arbitrariamente; 4- o vendedor garante que as pílulas terão preços iguais ou mais baratos que qualquer alimento; 5- o vendedor pretende , é claro, maximizar sua renda de modo a satisfazer a necessidade da dieta; 59 Para o problema posto, tem-se o modelo visto a seguir: maximizar 42 w1 + 24 w2 sujeito a: 3 w1 + 4 w1 + 5 w1 + 3 w1 + 6 w1 + w1 ; 2 w2 ≤ 25 3 w2 ≤ 35 4 w2 ≤ 50 3 w2 ≤ 33 3 w2 ≤ 36 w2 ≥ 0 (4.2) A cada modelo de Programação Linear, contendo coeficientes aij, bi e cj, corresponde um outro modelo, formado por esses mesmos coeficientes, porém dispostos de maneira diferente. Ao modelo original, visto em 4.1, dá-se o nome de “ Modelo Primal”, enquanto qua ao outro modelo visto em (4.2),denomina-se de “Modelo Dual”. Sobre estes dois modelos estão relacionadas propriedades que estabelecem que: a) se a função objetivo do primal é de minimização, então a função objetivo do dual é de maximização; b) os termos independentes das restrições do dual são coeficientes da função objetivo do primal; c) os coeficientes da função objetivo do dual são os termos independentes das restrições do primal; e) o número de variáveis do dual é igual ao número de restrições do primal; f) o número de restrições do dual é igual ao número de variáveis do primal; g) a matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal; Definição 4.1: Dado um Problema de Programação Linear (PP): min ctx ; c,x ∈ ℜn s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm x ≥0 O dual de (PP) é expresso por: (PD): max btw ; b,w ∈ ℜm s.a. Atx ≤ b; At∈ℜnxm, c∈ℜn w ≥0 4.3- Propriedades Propriedade 4.3.1: “O dual do dual é o primal”. Demonstração: 60 Seja o problema primal: t n (PP): min c x ; c,x ∈ ℜ s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm x ≥0 Pela definição 4.1, o seu dual é: t m (PD): max b w ; b,w ∈ ℜ t t nxm s.a. A x ≤ b; A ∈ℜ , c∈ℜn w ≥0 Vamos determinar o dual de PD. Para isso, vamos transformá-lo num problema de minimização e vamos também mudar o tipo de desigualdade da restrição para poder utilizar a definição 4.1. Então, temos: (PD): -min -btw ; b,w ∈ ℜm s.a. -Atw ≥- c; At∈ℜnxm, c∈ℜn w ≥0 Logo, o dual de PD é: t m (PD’): ): -max -c u ; c,u ∈ ℜ s.a. -Au ≤ -c; A∈ℜmxn, b∈ℜm w ≥0 que é equivalente a: (PD’’): min ctu ; c,u ∈ ℜn mxn m s.a. Au ≥ b; A∈ℜ , b∈ℜ u ≥0 que é equivalente ao problema primal (PP). Propriedade 4.3.2: “Se a restrição k do primal é de igualdade, então a variável wk do dual é irrestrita. Demonstração: Seja o problema primal: (PP): min ctx ; c,x ∈ ℜn s.a. Ax = b; A∈ℜmxn, b∈ℜm x ≥0 que pode ser transformado na forma: min ctx ; c,x ∈ ℜn s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm Ax ≤ b x ≥0 ou min ctx ; c,x ∈ ℜn 61 s.a. Ax ≥ b; A∈ℜ -Ax ≥ -b x ≥0 Sejam, então, A= A , b= -A mxn , b∈ℜ b m -b e w = 1 w 2 w ... O dual, por definição, será: t 2m (PD): max b w ; b , w ∈ ℜ t t nx2m n s.a. A x ≥ c; A ∈ℜ , c∈ℜ w ≥0, ou seja (PD): max (b b ) w1 w2 ‘ s.a. A w1 -A w2 ≥c w1, w2 ≥ 0 ou, ainda, t 1 t 2 PD): max b w - b w s.a. Atw1 – At w2 ≥ 0; At∈ℜnxm, c∈ℜn w1, w2 ≥ 0 ou (PD): max bt (w1 - w2 ) s.a. At (w1 – w2 ) ≥ 0 w1, w2 ≥ 0 Substituindo w1 – w2 por u, teremos que u = w1 – w2, u é livre de sinal, pois w1 ≥ 0 e w2 ≥ 0 . Portanto, a forma final do problema dual de (PP), será: (PD): max btu ; b,u ∈ ℜm s.a. Atu ≤ b; At∈ℜnxm, c∈ℜn u é irrestrito. Nas propriedades que seguem, as demonstrações são análogas àquela vista para a propriedade 4.3.2 e não serão vistas aqui. Propriedade 4.3.3: “Se a restrição k do primal é do tipo maior ou igual, então a variável wk do dual é não positiva”. Propriedade 4.3.4: 62 “Se a variável xp do primal é sem restrição de sinal, então a restrição p do dual é de igualdade”. Propriedade 4.3.5: “Se a variável xp do primal é não-positiva, então a restrição p do dual é do tipo maior ou igual”. O quadro visto a seguir estabelece a relação direta entre as propriedades relativas aos problemas Primal e Dual: Primal (Min.) restrição k é ≤ restrição k é = restrição k é ≥ xk ≥ xk é qualquer xk ≤ Dual (min.) → Dual (Max.) wk ≤ 0 wk é qualquer wk ≥ 0 restrição k é ≤ restrição k é = restrição k é ≥ Primal (max.) ← 4.4- Teoremas Básicos da Dualidade Os teoremas que serão vistos a seguir estarão baseados nos seguintes pares de problemas: Problema Primal (PP) Problema dual (PD) minimizar z = cTx maximizar d = wTb Ax = b sujeito a ⇔ sujeito a ATw ≤ c; x≥0 onde A ∈ ℜmxn; x, c ∈ ℜn; b, w ∈ ℜm, AT ∈ ℜnxm e obviamente poderão ser estendidos para qualquer outra definição de pares primal e dual diferentes destes. Teorema 4.4.1: Nas hipóteses dos problemas primal e dual serem factíveis é válido que a função objetivo dual é um limitante inferior para a função objetivo primal, ou seja, wTb ≤ cTx para x primal factível e w dual factível. Prova: Para uma solução primal factível x tem-se que o sistema de soluções está satisfeito, isto é, Ax = b , enquanto que AT w ≤ c , para w dual factível. Assim: wTb = wT Ax ≤ cT x . Portanto wTb ≤ cTx e o resultado segue. 63 Assim, a função dual fornece um limitante inferior à função primal, que deseja-se minimizar. Isto sugere que deve-se escolher w ∈ ℜ m tal que forneça o maior limitante inferior para a função objetivo primal, por isso, é interessante tentar-se maximizar a função dual. Teorema 4.4.2: Se B é a base relacionada à solução ótima de (PP) então o vetor multiplicador wT = cBTB-1 é a solução ótima de (PD). Prova: Considerando-se a partição de A = [B,N] , foi visto que pode-se escrever: B−1Bx B + B −1Nx N = B −1b Bx B + Nx N = b c BT x B + c NT x N = z c BT x B + c NT x N = z c BT B−1Bx B + c BT B −1Nx N = c BTB −1b (I) c BT x B + c NT x N = z (II) Subtraindo-se (I) de (II) : ( c BT - wTB) xB + (c NT - wTN) xN = z - wTb. Se x é uma solução básica factível então: xB = B-1b; xN = 0; c BT - wTB = 0 e existe alguma componente de custo relativo não básico (c NT - wTN)i < 0 . Assim (xN)i é uma variável não básica candidata a entrar na base. Se x é uma solução ótima para o problema (PP), então: -1 xB = B b; xN = 0; c BT - wTB = 0 e (c NT - wTN) ≥ 0 (hipótese). Assim , de c BT - wTB = 0 e (c NT - wTN) ≥ 0 pode-se concluir que: wT[B,N] ≤ [c BT , c NT ] wTA ≤ cT AT w ≤ c. Portanto, wT = cBTB-1 é uma solução básica factível Dual. Como B é a T base ótima de (PP), não é mais possível haver troca de base, então wT = cB B-1 é a solução ótima de (PD), e a prova está completa. Teorema 4.4.3: ( Teorema fundamental da dualidade em P.L.) Considere os pares de problemas (PP) e (PD). Se um dos problemas tiver solução ótima, então o outro também terá solução ótima. Considerando-se x* ∈ ℜn, a solução ótima do problema primal (PP) e w* ∈ ℜm, a solução ótima do problema dual (PD), então a seguinte igualdade é válida: cTx* = (w*)Tb. Prova: A primeira parte do teorema está demonstrada no teorema 5.4.2. Resta demonstrar que: cTx* = (w*)Tb. Mas cTx* = c BT xB = c BT B-1b = (w*)Tb. Como cTx ≥ cTx* = (w*)Tb ≥ wTb pelo teorema 5.4.1, então pode-se concluir que x* é a solução ótima de (PP) e w* é a solução ótima de (PD). 64 Observação: Viu-se que, se x é uma solução básica factível então: xB = B-1b; xN = 0; c BT - wTB = 0 e se existe alguma componente de custo T relativo não básico (c NT - w N)i < 0 , (xN)i era candidata a entrar na base. Isto quer dizer que, existe alguma componente wi infactível pois a T restrição (c NT - w N)i < 0 está sendo violada. O método dual-Simplex a ser visto baseia-se nesta infactibilidade para efetuar troca de soluções, ou seja, parte da infactibilidade das componentes wi e vai efetuando trocas de base até acabar com todas estas infactibilidades. Quando isto ocorrer é porque xB = B-1b; xN = 0; c BT - wTB = 0 e (c NT - wTN) ≥ 0 e os dois problemas (PP) e (PD) estarão resolvidos, com x sendo uma solução ótima para o problema (PP) w uma solução ótima para o problema (PD). Corolário 4.4.1: Se um dos problemas tiver solução ótima finita o outro também terá. Teorema 4.4.4: Se um dos problemas é ilimitado o outro é infactível. Este teorema pode ser ilustrado com o seguinte exemplo: ( PP ) minimizar z = -3x1 + 2x2 − x 1 + 2 x 2 ≥ −4 sujeito a x 1 − x 2 ≥ −3 x1, x 2 ≥ 0 Determinando-se (PD) e resolvendo-se (PP) e (PD) geometricamente, ilustra-se o resultado desejado. Teorema 4.4.5: Se um dos problemas é infactível o outro é ilimitado ou infactível. O exemplo a seguir ilustra esse resultado: (PP) minimizar z = -x1 - x2 − x1 − x 2 ≥ 1 sujeito a: − x1 + x 2 ≥ 1 x1, x 2 ≥ 0 Determinando-se (PD) e resolvendo-se (PP) e (PD) geometricamente, temse o resultado esperado. 4.4.1- Quadro resumo de Corolários e Teoremas Básicos da Dualidade 65 Dual Primal Tem solução factível Não tem solução factível Tem solução Não tem solução factível factível Mín z = Máx d Min z = max d = Pode ocorrer 4.5- Folgas Complementares A resolução de um Problema de Programação Pinear pode ser obtida resolvendo-se o sistema conjunto: cTx - wTb = 0; Ax = b, x ≥ 0 ; T A w ≤ c ⇔ AT w + wF = 0, wF ≥ 0. A primeira equação cTx - wTb = 0, pode ser escrita por: cTx - wT Ax = 0 ⇔ (cT - wT A) x = 0. Esta equação relaciona as variáveis de folga do problema dual wF com as variáveis primais x, onde wF = cT - wT A. Para wF dual factível e x primal factível tem-se wF ≥ 0 e x ≥ 0. Logo, (cT - wT A) x = 0 ⇔ (c iT - wT ai) xi = 0 para i = 1,...,n; qual é equivalente à seguinte relação de complementariedade: (c iT - wT ai) > 0 xi = 0; (c iT - wT ai) = 0 xi > 0. Assim, para x e w soluções ótimas de (PP) e (PD), respectivamente, se a i-ésima restrição do dual for inativa ((c iT - wT ai) > 0 ) então a correspondente variável primal será nula ( caso contrário cTx ≤ wTb ). Se a i-ésima variável primal for positiva então a correspondente restrição dual será ativa ((c iT - wT ai) = 0). Esta propriedade é conhecida na literatura como “condições das folgas complementares” , que são condições necessárias e suficientes que interrelacionam soluções factíveis e estabelecem um critério para atingir a otimalidade do PPL. Estas podem ser enunciadas no seguinte teorema. Teorema 4.5.1: ( Teorema das folgas complementares) Considerando-se x* e w* soluções factíveis de (PP) e (PD) respectivamente, então, se x* e w* são soluções ótimas para (PP) e (PD) tem-se: • o valor ótimo da variável w*i do dual é igual ao coeficiente na linha dos custos relativos ótima, da variável de folga x*n+i do primal, isto é, w*i = r*n+i (i=1,...,m); • o valor da variável de folga w*m+j do dual é igual ao coeficiente de custo relativo ótimo, xj do primal, isto é, w*m+j = r*j (j=1,...,n). 66 Este teorema tem o seu nome devido ao fato das variáveis de folga do dual e as variáveis de folga do primal estarem ligadas entre si. Porisso é que se diz que as soluções do primal e do dual são “complementares” entre si. Corolário 4.5.1: • (wF*)i = 0 quando x n* + i > 0 (i = 1, 2,…, m) isto é, se na solução ótima do primal, a variável de folga xn+i* for básica, então a variável do dual (wF*)i é não básica. • (wF*)m+j = 0 quando xj* > 0 (j = 1, 2,…,n), isto é, se na solução ótima do primal, a variável xj* for básica, então a variável de folga do dual (w F* )m+i é não básica. Na próxima seção será visto em detalhes o método Dual-Simplex. 4.6- O Método Dual - Simplex O método Dual-Simplex é aplicado na situação em que a solução inicial do primal é infactível, porém os elementos da função objetivo são todos nãonegativos. O método procura alcançar a factibilidade primal, transfornando as variáveis xj negativas em não negativas, mas preservando a factibilidade dual, ou seja, mantendo os coeficientes de custo relativo não negativos. 4.6.1- Resumo do método 67 Suponha que em uma iteração corrente o quadro do método apresente as seguintes características: a) Todos os elementos do vetor custo relativo são não-negativos, ou seja, (rN)j ≥ 0, j = 1, 2,…, n. Esta condição é denominada de otimalidade primal ou solução dual factível. b) Exista pelo menos um elemento (xB)i < 0 , ou seja, a condição de não negatividade das variáveis primais não é atendida. Diz-se que a solução é primal infactível. Antes de definir-se completamente os passos do método dual-simplex, ilustremo-lo com o seguinte exemplo. Exemplo 4.6.1: Seja o problema de programação linear primal: Min = 3 w1 + 4 w2 + 9 w3 s.a w1 + w3 ≥ 5 w2 + 2 w3 ≥ 2 w1, w2, w3 ≥ 0 Problema dual: Max z = 5 x1 + 2 x2 ≤ 3 x1 x2 ≤ 4 x1 + 2 x2 ≤ 9 x1 e x2 ≥ 0 Resolvendo o primal pelo método dual-simplex: Forma padrão: Min = 3 w1 + 4 w2 + 9 w3 s.a w1 + w3 - w4 =5 w2 + 2 w3 - w5 = 2 w1,…, w5 ≥ 0 Para iniciarmos o método devemos ter-se bi < 0 então multiplicando-se por (-1), as equações do sistema, tem-se:: Min = 3 w1 + 4 w2 + 9 w3 s.a - w1 - w3 + w4 = -5 - w2 - 2 w3 + w5 = -2 w1,…, w5 ≥ 0 Quadro 1: w1 w2 w3 w4 w5 0 -1 1 0 -5 w1 -1 -1 -2 0 1 -2 w5 0 3 4 9 0 0 0 1) Variável que sai da base: 68 b4 = ε= min { -5, -2} = -5 w4 sai da base (a linha pivô é a linha 1). 2) Variável que entra na base: −3 −4 −9 0 0 Min = w1 entra na base e o elemento pivô da , , , , =3 −1 0 −1 1 0 eliminação gaussiana e a11 = -1. 3) Pivoteamento em torno de a11: Quadro 2: w1 w2 w3 w4 w5 0 1 -1 0 5 w1 1 -1 -2 0 1 -2 w5 0 0 4 6 3 0 -15 1) Variável que sai na base: w5 = -2 sai da base (linha pivô 2). 2) Variável que entra na base: 0 −4 −6 −3 0 w3 entra na base (elemento pivô: a23 = -2). Min = , , , , =3 0 −1 − 2 0 1 3) Pivoteamento em torno de a22: Quadro 3: w1 w2 w3 w4 w5 -1 1/2 4 w1 1 -1/2 0 0 -1/2 1 w3 0 1/2 1 0 1 0 3 3 -21 Portanto, como não há nenhum bi < 0, o quadro é ótimo, com w* = (4, 0,1,0,0) e z* = 21. Vamos resolver o Problema dual e comparar sua solução com o Problema primal. Forma padrão: Max z = 5 x1 + 2 x2 z - 5 x1 - 2 x2 = 0 x1 + x3 = 3 x2 + x4 = 4 x1 + 2 x2 + x5 = 9 x1, x2, x3, x4, x5 ≥ 0 Quadro 1: x1 x2 x3 x4 x5 b x3 1 0 1 0 0 3 x4 0 1 0 1 0 4 x5 1 2 0 0 1 9 -z -5 -2 0 0 0 0 1) Variável que entra na base: x1 entra pois o seu coeficiente na função objetivo é mais negativo. 2) Variável que sai da base: 69 ε = mínimo { 3/1, 4/0, 9/1} = 3. Portanto x3 sai da base. O elemento pivô é a11 = 1. 3) Pivoteamento em torno de a11, obtendo o quadro 2: x1 x4 x5 -z x1 1 0 0 0 x2 0 1 2 -2 x3 1 0 -1 5 x4 0 1 0 0 x5 0 0 1 0 b 3 4 6 15 1) Variável que entra na base: x2 entra pois o seu coeficiente de custo relativo é negativo. 2) Variável que sai da base: ε = mínimo { 3/0, 4/1, 6/2} = 3. Portanto x5 sai da base. O elemento pivô é a31 = 2. 3) Pivoteamento em torno de a31, obtendo o quadro 3: x1 x2 x3 x1 x4 x5 -z 1 0 0 0 0 0 1 0 1 1/2 -1/2 4 x x5 4 0 0 1 -1/2 0 1/2 0 1 b 3 1 3 21 4.6.2- Definição dos passos do método Dual-Simplex Considere D = { w ∈ ℜ m tal que ATw ≤ c }. Considere também uma partição da matriz A = [B,N] e uma solução corrente w . Teorema 4.6.2.1: w é um vértice de D se e somente se existirem m restrições ativas em w , com os gradientes linearmente independentes, isto é, com uma base B ∈ℜ mxm , associada a estas m restrições ativas, isto é, w é dual factível. Definição 4.6.2.1: Se alguma restrição dual associada a uma coluna não-básica for ativa, istp T é, a Nj w = c Nj , dizemos que w é dual degenerada ou a partição A = [B,N] é dual degenerada. 70 Teorema 4.6.2.2: Se o problema primal tiver solução ótima então existirá pelo menos um vértice ótimo. As provas dos teoremas vistos são deixadas como exercício pois são análogas às demonstrações feitas para o problema primal. 4.6.3- Direções duais factíveis Suponha conhecida uma partição dual factível, isto é, ( w )=c BT B-1 e que esta seja uma partição não degenerada. -1 ∃ B tal que Se quiser-se determinar uma nova solução w = w + ε d com ε ≥ 0, então deve-se satisfazer: AT ( w + ε d) ≤ c ⇔ BT( w + ε d) ≤ cB. Desde que , BT( w ) = cB BT d ≤ 0. Isto é equivalente a, a BTi d ≤ 0 , para i = 1,...,m. Note que, há duas possibilidades: a BTi ( w + ε d) = cB i ; (sempre estará satisfeita) i) a BTi d = 0 ii) a BTi d ≤ 0 a BTi ( w + ε d) ≤ cB i ; Assim, a nova solução deixará de ser ativa apenas para as restrições em que ii) ocorra. A estratégia dual-simplex consiste em definir a direção d de tal forma que apenas uma restrição deixe de ser ativa, para se obter a nova solução. Para isto, a direção é definida da seguinte maneira: BT dj = - ej; assim, a j-ésima restrição deixará de ser ativa na nova solução. Para esta escolha tem-se que: dj = - (BT)j-1 , onde (BT)j-1 é a j-ésima linha de B-1. Teorema 4.6.3.1: Para j =1,...,m; as direções dj são linearmente independentes e definem uma base para o conjunto de direções factíveis de D. 4.6.4- Definição do tamanho do passo ε. Como a solução é não degenerada, segue que ∃ε > 0 tal que: a NT j ( w + εd) ≤ cN j ; para i = 1,...,n-m e esta equação será sempre satisfeita desde que: 71 c Nj − a NT j w ε≤ com a NT j d > 0. a NT j d Assim, se escolher-se: ε= c Nr − a NTr w a NTr r d = min{ c Nj − a NT j w a NT j d j / a NT j d j > 0 } ; a r-ésima restrição não básica torna-se ativa enquanto que uma das restrições básicas deixa de ser ativa. Por exemplo, se j = k, então a k-ésima restrição não básica torna-se inativa. 4.6.5- Acréscimo da função objetivo dual. Da forma que foi definida d tem-se que esta direção é uma direção de subida, isto é, de acréscimo da função o bjetivo dual. Para a solução corrente tem-se : d = bT w . Para a nova solução terá-se: d = bT ( w + ε dk ) = d + ε bT dk. Note que, à solução básica primal associada à partição básica vale: x B = B-1b; e k-ésima componente de x B é: -1 k k T x Bk = (B ) b = - ( d ) b; Então, d = d - ε x Bk . Assim, se x Bk < 0, a função dual tem um acréscimo linear com a taxa x Bk . Desta forma, a infactibilidade da solução básica primal produz uma direção de subida para a função objetivo dual. 4.6.6- Os passos do método Dual-Simplex. Passo 1: Determine uma solução básica dual ( w )= c BT B-1 e calcule a solução básica primal B xB = b. Passo 2: Se xB ≥ 0, pare, pois não é mais possível obter acréscimos para a função objetivo dual. Caso contrário: Seleção da variável a deixar a base: Escolha uma das variáveis negativas, de preferência a mais negativa: (xB)k = min { (xB)i tal que (xB)i < 0}. Assim, a variável básica corresponde à linha k sai da base e a linha k é a linha pivô. 72 Passo 3: Determine dk tal que: BT dk = - ek; Passo 4: Seleção da variável a entrar na base: Determine r tal que: c Nj − a NT j w c Nr − a NTr w ε= = min{ / a NT j d j > 0 } T r T j a Nr d a Nj d Se a NT j dk ≤ 0, par j = 1,...,n-m; então o problema dual é ilimitado e então o problema dual é infactível. Pare. Caso contrário vá para o passo seguinte. Passo 5: Atualize a partição básica trocando-se a k-ésima coluna de B pela r-ésima coluna de N , efetuando pivoteamento em ark e volte ao passo 1. Observação: Se o problema dual for de minimização, há duas formas de tratá-lo. A primeira é aquela que consiste na conversão do problema para maximização. A outra, consite em inverter o critério de escolha da variável a entrar na base 4.7- Exercícios propostos 4.7.1) Dado o PPL primal: minimizar z = x1 - x2 + x3 x1 ≤ 9 sujeito a x1 + x 2 + x 3 ≤ 2 ; x1, x 2 , x 3 ≥ 0 Pede-se: a) resolva o PPL primal pelo método simplex, identifique a solução dual; 73 b) determine o PPL dual, resolva-o pelo método dual-simplex e identifique a solução primal; c) Verifique que as soluções dos dois problemas satisfazem as condições do teorema das folgas complementares. 4.7.2) Resolva o seguinte PPL primal : maximizar z = 5x1 + 6x2 x1 + 3 x 2 ≤ 5 sujeito a: 4 x1 + 9 x 2 ≤ 12 ; x1, x 2 ≥ 0 Suponha que façamos a seguinte mudança na função objetivo: maximizar (5-3u)x1 + (6-4u)x2 ; u ≥ 0. Determine a solução ótima do modelo em função de u. 4.7.3) Dado o PPL primal em função de f : maximizar z = 2 x1 + 3 x2 + 3x3 x1 + 2x 2 + 2x 3 ≤ 12 sujeito a 2x1 + 4 x 2 + x 3 ≤ f ; x1, x 2 , x 3 , f ≥ 0 Pede-se: a) determine o valor máximo de f para que a base ótima não se altere. b) Para valores de f maiores que aquele obtido em 2.1) resolva o problema pelo método dual-simplex até que não se consiga mais melhorar a função objetivo primal. 4.7.4) Utilize o método dual-simplex para resolver o PPL abaixo em função de λ : maximizar z = 2x1 + 3x2 x1 + 2x 2 ≤ 13 sujeito a: x1 + x 2 ≤ 5 + 2λ ; x1, x 2 ≥ 0; λ ≤ 2 BIBLIOGRAFIA [1] SWOKOWSKI, Earl W. Cálculo com Geometria Analítica. Vol. 1 e 2, Editora McGraw – Hill, 1994. [2] CALLIOLI, Carlos A., DOMINGUES, Hygino H., COSTA, Roberto C. F. Álgebra Linear e Aplicações. Atual Editora, 1993. [3] MACULAN, Nelson (Filho), PEREIRA, Mário Veiga Ferraz, Programação Linear, Editora Atlas, 1980. 74 [4] LUENBERGER, David G., Edition, 1989. Linear and Nonlinear Programming, Second [5] BAZARAA, Mokhtar S., JARVIS, John J. Linear Programming and Network Flows, John Wiley & Sons, 1977. [6] PUCCINI, Abelardo de Lima, PIZZOLATO, Nelio Domingues, Programação Linear, Livros Técnicos e Científicos Editora S.A., 1987. [7] RAMALHETE, Manuel, GUERREIRO, Jorge, Programação Linear, Volume 1. McGraw - Hill, 1984. MAGALHÃES, Alípio, [8] YOSHIDA, Luzia Kazuko, Programação Linear. Atual Editora, 1987. Métodos Quantitativos, [9] BALBO, Antonio Roberto; BAPTISTA, Edméa Cássia. Tópicos de Otimização e Programação Matemática I – Curso de Especialização em Matemática Aplicada e Computacional. Depto de Matemática – Fac. de Ciências – UNESP de Bauru, 1996. 75
Documentos relacionados
3- O MÉTODO SIMPLEX 3.1- Introdução O Método
ii) Verificar se a solução atual é ótima. Se for, pare. Caso contrário, siga para o passo iii). iii) Determinar a variável não básica que deve entrar na base; iv) Determinar a variável básica que d...
Leia mais