Exemplo ( Algoritmo Dual do Simplex ) IO

Exemplo ( Algoritmo Dual do Simplex ) IO
Minimizar:
          z = 10x1 + 5x2
Sujeito a:
       20x1 + 50x2 ≥  200
         50x1 + 10x2 ≥ 150
        30x1 + 30x2 ≥ 210
x1,x2 ≥0


Dado a forma assumida por este problema, pode aplicar-se imediatamente o algoritmo do dual do simplex com efeito, a estandardização do problema seguido da MULTIPLICAÇÃO DE TODAS AS EQUAÇÕES  por (-1) conduz a uma forma canónica em que se identifica uma solução básica não admissível do primal a satisfazer o critério óptimo tal como é exigido pelo algoritmo dual do simplex.

1º Quadro do Algoritmo Dual do Simplex

Aplicando o algoritmo dual do simplex selecciona-se em primeiro lugar o vector a sair da base; esta selecção é feita através do critério

                                     

min{ xi0 | xi0 <0}

pelo que, neste caso, x2 sai da base pois

X2=min{ -200, -150, -210}

O vector a entrar na base é determinado por:

min{ Zj-Cj / xsj | xsj < 0}

min{ -10/-30, -5/30} = 5/30

devendo portanto o vector x2 entrar na base, aplicando o método de Gauss- Jordan, tornando x52=-30 como elemento redutor, tem-se 0 2º quadro do algoritmo dual do Simplex

Como a solução obtida não é admissível aplicam-se de novo os critérios de saída e entrada, verificando que  S2 sai da base sendo substituído por x1, obtendo-se após condensação, a nova solução que se apresenta no quadro seguinte: 

A solução obtida é admissível, tratando-se da solução óptima do problema primal

Alteração dos coeficientes da Função Óptima (IO)

Alteração dos coeficientes da Função Óptima

~C = Cl + ΔCl

exemplo= alteração de C2 de 3 para 5

FO
    Z=6x1+3x2

novo
~C= C2+ΔC2
2= 3+2=5

* Implica no quadro óptimo do simplex, alteração apenas nas linhas Zj e (cz-zj), por outras palavras a solução do primal mantém-se (admissível), podendo ser alterada a solução dual associada

* Existe a premibilidade de critério do óptimo deixar de ser respeitada, isto é a solução dual associada pode tornar-se não admissível e consequentemente a solução primal deixar de ser óptima.

- Verifica-se alteração da inclinação das rectas de nivel da Função Óptima

- Solução Óptima pode ser obtida noutro ponto extremo de K

- Solução Óptimo pode mudar mas não afecta a admissibilidade da solução original que era dada-

X*b = B^-1* b

e que para a  X*b  original se verifica o critério do óptimo

cj-zj=∑i Ci... xij=<0

Continuação da Dualidade- Interpretação Económica Parte I

Pós - optimização e analise de sensibilidade Parte I

* Estudar variações dos parâmetros de modelo matemático ( frequente na vida real) e do seu impacto no comportamento da solução do problema

* Muitas vezes um modelo de programação linear é frequentemente alterado

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 

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

Regime Forçado sinusoidal: Análise de circuitos em corrente e alternada sinusoidal

Grandezas ( v(t) e a i(t) ) são sinusoidais
x(t) = xm * cos(wt+α)
xm= amplitude ou valor máximo
w= frequência angular

α= fase na origem

Um complemento de estudo sobre Regime Forçado Sinusoidal:

https://dspace.ist.utl.pt/bitstream/2295/61017/1/AS%20regime%20for?ado%20sinusoidal.pdf