Trabalho - Pesquisa Operacional 1

Grupo 2

Akane; Allan; Luana; Olivia

Slide 1 - Questão 1[6.57]

Problema »

500 acres a serem plantados ...

LAVOURA	TRABALHADORES.DIA	CAPITAL...	LUCRO...
Trigo	6	100	60
Milho	8	150	100
Soja	10	120	80

Modelagem »

(P.L.) $$ \begin{equation} \begin{array}{*{4}{z}} % {zzzr} works too Max Z & =60x_1 & +100x_2 & +80x_3 & &\\ s.a.& 6x_1 & +8x_2 & +10x_3 & \leq & 5000\\ & 100x_1 & +150x_2 & +120x_3 & \leq & 80000\\ & x_1 & +x_2 & +x_3 & \leq & 500\\ & x_i \geq 0 & i=1,2,3 \end{array} \end{equation} $$

(P.L.) - forma padrão $$ \begin{equation} \begin{array}{*{4}{z}} % {zzzr} works too Max Z & =60x_1 & +100x_2 & +80x_3 & & & &\\ s.a.& 6x_1 & +8x_2 & +10x_3 & +x_4 & & & = & 5000\\ & 100x_1 & +150x_2 & +120x_3 & & +x_5 & & = & 80000\\ & x_1 & +x_2 & +x_3 & & & +x_6 & = & 500\\ & x_i \geq 0 & i=1,2,3,4,5,6 \end{array} \end{equation} $$

Slide 2 - Problema Dual Associado

Interpretação do (P.D.) »

(P.D.) $$ \begin{equation} \begin{array}{*{4}{z}} % {zzzr} works too Min \phi & = & 5000\lambda_1 & +80000\lambda_2 & +500\lambda_3 & &\\ s.a.& 6\lambda_1 & +100\lambda_2 & +\lambda_3 & \geq & 60\\ & 8\lambda_1 & +150\lambda_2 & +\lambda_3 & \geq & 100\\ & 10\lambda_1 & +120\lambda_2 & +\lambda_3 & \geq & 80\\ & \lambda_i \geq 0 & i=1,\cdot,3 \end{array} \end{equation} $$

Slide 3 - B) Análise de Sensibilidade

Tablô inicial e Solução ótima do (PL) »

width

Slide 4 - Alteração Parâmetro "c"

1)Variáveis não-básicas »

\[c_1 = 60 \rightarrow c'_1=150 \]

Verificando o "range":
$$ \begin{equation} c_{B}B^{-1}a_1 - c_1 = \begin{bmatrix} 0 & 0 & 100 \end{bmatrix}^{T} \begin{pmatrix} -2\\ -50\\ 1 \end{pmatrix} - (60 + \Delta) \geq 0 \rightarrow \Delta \leq -40 \end{equation} $$ Verificando o impacto no custo relativo: $$ \begin{equation} c_{B}B^{-1}a_1 - c_1 = \begin{bmatrix} 0 & 0 & 100 \end{bmatrix}^{T} \begin{pmatrix} -2\\ -50\\ 1 \end{pmatrix} - 150 = -50 \rightarrow \leq 0 \end{equation} $$

Slide 5 - Alteração Parâmetro "c"

1)Cont. Variáveis não-básicas »

Slide 6 - Alteração Parâmetro "c"

2)Variáveis básicas »

$$ c_4 \rightarrow c'_4=-100$$
$$ \begin{equation} c_{B}B^{-1}a_i - c_i = \begin{bmatrix} c'_4 & c_5 & c_2 \end{bmatrix}^{T} y_i -c_i \end{equation} $$

$$(z_1-c_1):$$ $$ \begin{equation} c_{B}B^{-1}a_1 - c_1 = \begin{bmatrix} 0+\Delta & 0 & 100 \end{bmatrix}^{T} \begin{pmatrix} -2\\ -50\\ 1 \end{pmatrix} - 60 \geq 0 \rightarrow \Delta \leq 20 \end{equation} $$ $$(z_3-c_3):$$ $$ \begin{equation} c_{B}B^{-1}a_3 - c_3 = \begin{bmatrix} 0+\Delta & 0 & 100 \end{bmatrix}^{T} \begin{pmatrix} 2\\ -30\\ 1 \end{pmatrix} - 80 \geq 0 \rightarrow \Delta \geq -10 \end{equation} $$ $$(z_6-c_6):$$ $$ \begin{equation} c_{B}B^{-1}a_6 - c_6 = \begin{bmatrix} 0+\Delta & 0 & 100 \end{bmatrix}^{T} \begin{pmatrix} -8\\ -150\\ 1 \end{pmatrix} - 0 \geq 0 \rightarrow \Delta \leq 12.5 \end{equation} $$

Slide 7 - Alteração Parâmetro "c"

2) Variáveis básicas » Novo tablô e nova solução

Base.Var	x1	x2	x3	x4	x5	x6	RHS
Z	40	0	-180	0	0	100	50000
x4	-2	0	2	1	0	-8	1000
x5	-50	0	-30	0	1	-150	5000
x2	1	1	1*	0	0	1	500

Base.Var	x1	x2	x3	x4	x5	x6	RHS
Z	220	180	0	0	0	280	140000
x4	-4	-2	0	1	0	-10	0
x5	-20	30	0	0	1	-120	20000
x3	1	1	1	0	0	1	500

Slide 8 - Parâmetro "b"

Alteração no capital disponível »

$$ b_2=80.000 \rightarrow b'_2=50.000$$

$$ Range: \begin{equation} b' = \begin{pmatrix} 5000\\ 80000+\Delta\\ 500 \end{pmatrix} \rightarrow \end{equation} $$ $$ \begin{equation} b' = B^{-1}b' = \begin{bmatrix} 1 & 0 & -8\\ 0 & 1 & -150\\ 0 & 0 & 1 \end{bmatrix} \begin{pmatrix} 5000\\ 80000+\Delta\\ 500 \end{pmatrix} \geq 0 \end{equation} $$ $$ \begin{equation} = \begin{pmatrix} 1000\\ \Delta+5000\\ 500 \end{pmatrix} \geq -5000 \end{equation} $$

Solução Infactível:

$$ \begin{equation} b' = B^{-1}b' = \begin{bmatrix} 1 & 0 & -8\\ 0 & 1 & -150\\ 0 & 0 & 1 \end{bmatrix} \begin{pmatrix} 5000\\ 50000\\ 500 \end{pmatrix} = \begin{pmatrix} 1000\\ -25000\\ 500 \end{pmatrix} < 0 \end{equation} $$

Slide 9 - Cont. Alteração Parâmetro "b"

width

Slide 10 - Acréscimo de atividade

Estrutura do novo problema »

(P.L.) $$ \begin{equation} \begin{array}{*{4}{z}} % {zzzr} works too Max Z & = 60x_1 & +100x_2 & +80x_3 & + 100x_p & &\\ s.a.& 6x_1 & +8x_2 & +10x_3 & +10x_p & \leq & 5000\\ & 100x_1 & +150x_2 & +120x_3 & + 10x_p & \leq & 80000\\ & x_1 & +x_2 & +x_3 & +x_p & \leq & 500\\ & x_i \geq 0 & i=1,2,3,p \end{array} \end{equation} $$

Outras alterações/ impactos »

$$c_p = 150$$ $$a_p = \begin{pmatrix} 10\\ 10\\ 1\\ \end{pmatrix} $$

Verificando se $$(z_p - c_p) \geq 0$$: $$c_{B}B^{-1}a_p - c_p =$$ $$ \begin{equation} =\begin{bmatrix} c_{4} & c_{5} & c_{2} \end{bmatrix}^{T} \begin{bmatrix} 1 & 0 & -8\\ 0 & 1 & -150\\ 0 & 0 & 1 \end{bmatrix} \begin{pmatrix} 10\\ 10\\ 1 \end{pmatrix} - 150 = -50 < 0 \end{equation} $$

Slide 11 - Acréscimo de atividade

Novo tablô e solução »

Base.Var	x1	x2	x3	xp	x4	x5	x6	RHS
Z	40	0	20	-50*	0	0	100	50000
x4	-2	0	2	2	1	0	-8	1000
x5	-50	0	-30	-140	0	1	-150	5000
x2	1	1	1	1	0	0	1	500

Base.Var	x1	x2	x3	xp	x4	x5	x6	RHS
Z	90	50	70	0	0	0	150	75000
x4	-4	-2	0	0	1	0	-10	0
x5	90	140	110	0	0	1	-10	75000
xp	1	1	1	1	0	0	1	500

Slide 12 - Acréscimo de restrição

Novo (P.L.) e ajustes »

\[ \begin{equation} \begin{array}{*{4}{z}} % {zzzr} works too Max Z & =60x_1 & +100x_2 & +80x_3 & &\\ s.a.& 6x_1 & +8x_2 & +10x_3 & \leq & 5000\\ & 100x_1 & +150x_2 & +120x_3 & \leq & 80000\\ & x_1 & +x_2 & +x_3 & \leq & 500\\ & & & x_3 & \geq & 10\\ & x_i \geq 0 & i=1,2,3 \end{array} \end{equation} \]

Ajustes: \[ -x_3 \leq -10 \] \[ -x_3 + s_7 = -10\]

Slide 13 - Acréscimo Restrição