Teoria de Decisão I

AULA 10: Exercícios pré avaliação

Profa. Luciane Alcoforado

PPGEC/UFF

Objetivos

Verifique ao final desta aula se você é capaz de:

1- Aplicar o método simplex e gráfico a um problema de programação linear;

2- Analisar situações envolvendo problemas de programação linear.

Lembrete: O primeiro passo do Simplex

Reescrever o problema na forma padrão:

Função objetivo deve ser de minimização
As restrições devem estar na forma \(Ax=b\)
Os vetores \(x\) e \(b\) devem ser positivos.

Formulário do Algoritmo Simplex

Será fornecido nas avaliações.

\(Bx_B=b\) ou \(x_B = B^{-1}b\);

\(B^{T}\lambda = c_B\) ou \(\lambda = B^{T^-1}c_B\)

\(C'_{N_i}=c_{N_i}-\lambda^T a_{N_i}\);

\(By=a_k\) ou \(y=B^{-1}a_k\)

\(\epsilon_z=\frac{x_{Bz}}{y_z}\)

Exercício 1:

Explique como obter e indique a solução ótima com base no gráfico.

Exercício 2

Apresente o problema do exercício 1 na forma padrão.

Exercício 3

Apresente a formulação das duas fases do método simplex duas fases, considerando o seguinte problema: (não precisa resolver, mostre apenas a formulação na forma padrão)

\(min\) \(z=-3x_1+4x_2+x3\)

Sujeito a:

\(1x_1+1x_2+3x_3\ge6\)

\(1x_1+1x_2+x_3\le30\)

\(-1x_1+0x_2+2x_3\ge10\)

\(x_1,x_2,x_3\ge0\)

Exercício 4

Suponha a seguinte iteração do algoritmo simplex.

iteração 1: \(I_N=\{1,2,3\}\) e \(I_B=\{4,5,6\}\)

A=cbind(a1=c(1,1,2), a2=c(3,2,5), a3=c(0,1,-2), a4=c(1,0,0), a5=c(0,1,0), a6=c(0,0,1))
ct=c(-1,-2,3,0,0,0)
b=c(20,30,4)
IN=c(1,2,3);IB=c(4,5,6)
B=A[,IB]

xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))
xB

Qual o valor da solução corrente, ou seja, qual o valor de cada variável \(x_1,...,x_6\)?

cB=ct[IB]; cN=ct[IN]
lambda = solve(t(B))%*%cB
lambda

     [,1]
[1,]    0
[2,]    0
[3,]    0

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo #analise

[1] -1 -2  3

Com base nos custos relativos acima, analise se a solução corrente é ótima. Caso não seja, qual variável deve entrar na base na próxima iteração?

A[,IN[k]]

[1] 3 2 5

y = solve(B)%*%A[,IN[k]]
y

xB

Considerando os valores dos vetores \(y\) e \(x_B\) obtidos acima, obtenha o tamanho de passo \(\epsilon\) e justifique qual a variável que deve deixar a base.

Exercício 5

Resolva passo a passo o algoritmo simplex até finalizar a primeira fase para o seguinte problema:

\(max\) \(z=5x_1+5x_2+5x_3\)

Sujeito a:

\(7x_1+1x_2+2x_3\ge10\)

\(1x_1+1x_2+3x_3\ge5\)

\(2x_1+3x_2+5x_3\ge10\)

\(x_1,x_2,x_3\ge0\)

Explique como iniciaria a primeira iteração da segunda fase quanto ao particionamento, ou seja, informe quais índices estarão em \(I_N\) e \(I_B\) na primeira iteração da segunda fase.