Trabalho - Simplex - Programação Linear e Inteira 2020-2

Nome: Frederico Guilherme Madeira Vaz Matrícula: 17.2.8224 Disciplina: Programação Linear e Inteira – ENP012 Professor: Alexandre Xavier Trabalho Simplex 1) Crie exemplos e resolva pelo método simplex: a) Um exemplo em que a solução ótima é única. Min f(x1, x2) = − x1 − x2 s.a: 2 x1 + x2 ≤ 8 x1 + 2x2 ≤ 7 x2 ≤ 3 x1 e x2 ≥ 0 Transformando condições em equações: Onde: As variáveis inseridas são chamadas de variáveis de folga. S1 ≥ 0, S2 ≥ 0, S3 ≥ 0. Então: F=-x1-x2. A função F contém apenas variáveis não básicas. Portanto, o valor da função F para essa base pode ser encontrada. A solução é ótima, pois não existe nenhum outro custo relativo negativo, ou seja, não podemos diminuir mais a função objetivo. Portanto, a solução ótima é: x* = (x1, x2, x3, x4, x5) = (3, 2, 0, 0, 1). A solução ótima é Z = -5 X1 = 3 X2 = 2 b) Um exemplo em que haja infinitas soluções ótimas. Min f(x1, x2) = − x1 − x2 s.a: x1 + x2 ≤ 6 x1 − x2 ≤ 4 −x1+ x2 ≤ 4 x1 ≥ 0, x2 ≥ 0 Transformando condições em equações: Onde: As variáveis inseridas são chamadas de variáveis de folga. S1 ≥ 0, S2 ≥ 0, S3 ≥ 0. Então: Existe uma base em nosso sistema. Podemos começar a resolver nosso problema. F=-x1-x2. A função F contém apenas variáveis não básicas. Portanto, o valor da função F para essa base pode ser encontrada. Encontramos o valor da função F correspondente à base inicial. A variável que vai sair da base é P3 e a que entra P2. Não há coeficientes negativos na linha destacada. Portanto, o valor mínimo da função F foi encontrado. O coeficiente é zero na posição 4 na linha destacada. Não há uma variável básica na coluna 4. Isso nos permite encontrar outra solução em que F = -6. Como S ≥ 0 para todas variáveis não básicas, segue que a solução atual é ótima. f(x)=− 6 +0x4 + x3 ≥− 6, para todo x4 ≥ 0 e x3 ≥ 0. f(x) = − 6, para todo x4 > 0 e x3 = 0, ou seja, a solução básica pode ser alterada com valores não nulos para x4, sem que a função objetivo se altere. Há valores infinitos de X1, X2 para o valor ótimo Z = -6, que estão contidos no segmento da linha -1 X1-1 X2 = -6 que satisfaça as restrições do problema. Uma é: X1 = 5 X2 = 1 Portanto, o problema tem múltiplas soluções ótimas, as quais podem ser determinadas por se atribuir valores diferentes a x4. c) Um exemplo em que a solução seja ilimitada. Minimizar f(x1, x2) = − x1 − x2 s.a: x1 − x2 ≤ 4 −x1 + x2 ≤ 4 x1 ≥ 0, x2 ≥ 0. Transformando condições em equações: Onde: As variáveis inseridas são chamadas de variáveis de folga. S1 ≥ 0, S2 ≥ 0. Então: F=-x1-x2 A variável que vai sair da base é P3 e a que entra P1. Nota-se que não há coeficientes positivos na linha destacada. Logo, temos então que, se aumentamos o valor da variável x2, a função objetivo decresce (custo relativo negativo). Note que x2 pode crescer indefinidamente, já que a direção simplex não tem componentes positivas (direções deste tipo são chamados raios da região factível). Assim, o problema não tem solução ótima. d) Um exemplo com a solução degenerada. Min f(x1, x2) = − x1 − x2 s.a: x1 + x2 ≤ 6 x1 − x2 ≤ 4 −x1+ x2 ≤ 4 x1 ≥ 0, x2 ≥ 0 Transformando condições em equações: Onde: As variáveis inseridas são chamadas de variáveis de folga. S1 ≥ 0, S2 ≥ 0, S3 ≥ 0. Então: Existe uma base em nosso sistema. Podemos começar a resolver nosso problema. F=-x1-x2. A função F contém apenas variáveis não básicas. Portanto, o valor da função F para essa base pode ser encontrada. Encontramos o valor da função F correspondente à base inicial. Logo, encontramos um valor mínimo da função F. A função F contém apenas variáveis não básicas. Portanto, o valor da função F para essa base pode ser encontrada. Não há coeficientes negativos na linha destacada. Portanto, o valor mínimo da função F foi encontrado. O coeficiente é zero na posição 4 na linha destacada. Não há uma variável básica na coluna 4. Isso nos permite encontrar outra solução em que F = -6. Como S ≥ 0 para todas variáveis não básicas, segue que a solução atual é ótima. f(x)=− 6 +0x4 + x3 ≥− 6, para todo x4 ≥ 0 e x3 ≥ 0. f(x) = − 6, para todo x4 > 0 e x3 = 0, ou seja, a solução básica pode ser alterada com valores não nulos para x4, sem que a função objetivo se altere. Do ponto de vista geométrico, ambas as soluções são pontos do espaço, ou seja, formam um segmento de linha. Qualquer ponto (qualquer solução) neste segmento de linha também será uma solução. Portanto, o problema tem múltiplas soluções ótimas, as quais podem ser determinadas por se atribuir valores diferentes a x4. Contudo, se a solução básica ótima fosse degenerada (alguma variável básica nula), então com o aumento de x4, poderia ocorrer que uma variável básica nula ficasse negativa, de modo que x4 não poderia assumir valores diferentes de zero. Neste caso, o problema não apresenta múltiplas soluções ótimas, apesar de um custo relativo nulo na otimalidade. Em resumo, se na otimalidade os custos relativos são todos positivos, podemos afirmar que o problema tem solução ótima única. A existência de custos relativos nulos é condição necessária para múltiplas soluções ótimas, mas não é suficiente. 2) Crie exemplos e resolva pelo método simplex das duas fases: a) Um exemplo em que a solução é inviável ao fim da primeira fase. Min f(x1, x2) = − x1 − x2 s.a: -1 X1 + 1 X2 ≤ 4 1 X1 -2 X2 ≤ 2 x1 e x2 ≥ 0 Transformando condições em equações: A variável que vai sair da base é P4 e a que entra P1. Há um coeficiente positivo na posição 1 da linha destacada. Não há coeficientes positivos na coluna 1. Portanto, a função F diminui ilimitadamente. b) Um exemplo em que a solução é ótima após uma ou mais iterações da segunda fase. Min f(x1, x2) = − x1 − x2 s.a: -2 X1 + 1 X2 ≤ 4 2 X1 -1 X2 ≤ 2 1 X2 ≤ 3 x1 e x2 ≥ 0 A variável que vai sair da base é P4 e a que entra P1. Não há coeficientes negativos na linha destacada. Portanto, o valor mínimo da função F foi encontrado. A solução ótima é Z = -11 / 2 X1 = 5 / 2 X2 = 3