Pipoca Doce Digital

sábado, 19 de maio de 2012

Dualidade - Interpretação Económica( IO)

Problema dual

Unidades Monetárias:
u1,u2,u3: valor de recursos a empatar a produção de secretárias (restrição 1 dual) e estantes( restrição 2 dual)
restrição 1 do dual (secretárias)
2u1+4u2+u3-u4=6 (=) u4=(2u1+u2+u3)-6

Slack variáveis dual

u4,u5: custo de oportunidade

Análise de Pós-optimização, Continuação da Dualidade - Interpretação Económica Parte II

Análise de Pós-optimização Parte II

Abordado o impacto na solução óptima de alterações discretas nos parâmetros do modelo coeficientes da Função Óptima, termos de identidade, coeficientes da matriz, introdução de novas variáveis , introdução de novas restrições.

Analise de sensibilidade

Determinação de intervalos de variação para os parâmetros que não envolvam alteração da estrutura da solução óptima já encontrada.

Propriedades do Dual

Propriedades do Dual

* As componentes do vector U*=[u1, u2, ...,un] encontramos no quadro óptimo do primal na linha e nas colunas
Correspondentes a matriz identidade de partida, isto é nas colunas correspondentes a matriz da base óptima

* Na solução óptima os valores das variáveis do desvio do dual são simétricas dos elementos da linha c-z correspondentes apenas as variáveis do primal

Propriedades Fundamentais do Algoritmo Dual do Simplex

Propriedades Fundamentais

Resultado 1: O valor da função objectivo, Z, de qualquer solução admissível do primal, X=(x1,x2,...,xn), não excede o valor da Função Óptima de qualquer solução admissível do dual

Resultado 2: Se X*=(x1*, x2*,..., xn*) e U*=(u1,u2,...,un)
São soluções admissíveis para os problemas primal e dual respectivamente, tais que

∑j cj xj*= ∑i bi u1*

então X*, U*, são condições óptimas do primal e do dual

Resultado 3: Para qualquer par de problemas duais, a existência de solução óptima finita para um deles garante a existência da solução óptima finita para o outro e os valores das Funções Óptimas são iguais: Z*=U*

Resultado 4: Um problema de programação linear tem solução óptima só se existirem soluções admissíveis para os problemas primal e dual

Resultado 5: Se para algum dos problemas existir solução não limitada então possui soluções admissíveis

quinta-feira, 17 de maio de 2012

Dualidade

Algoritmo Dual do Simplex / Algoritmo Primal do Simplex

Primal: SBAP ------>.....----->SBAP------>SBAP X*
Dual: SBNAP ------>.....----->SBNAD------>SBAN U*

SBAP: Solução Básica admissível no problema primal
SBNAP: Solução Básica Não admissível no problema primal

SBAD: Solução Básica admissível no dual
SBNAD: Solução Básica Não admissível no dual

Como (cj-zj) >0 o critério do óptimo ainda não está satisfeito, logo continua-se a aplicar o algoritmo do simplex bj =>0, condição de admissibilidade no primal
(cj-zj) =< a condição de admissibilidade no dual

Algoritmo dual do Simplex

Passo 1: Construir o quadro do simplex correspondente a uma solução básica admissível no dual (com uma matriz identidade)

Passo 2: Se bj=>0, o algoritmo termina, estamos na presença de uma solução óptima finita para o problema dual consequentemente para o primal. O processo continua se existir algum bj <0

Passo 3: Escolher o vector a sair da base de acordo com o critério min bj<0 (escolher a linda do elemento redutor

Passo 4: Escolher o vector a entrar na base
cj-zj / aij, aij<0
Se todos os aij=>0, o processo termina.
Esta-se perante uma solução não limitada para o problema dual e consequentemente o problema primal não possui Soluções Admissíveis
O processo continua no caso de existir algum aij < 0

Passo 5: Actualizar o quadro do simplex usando operações do Gauss- Jordan