Otimizacao/branchbound_about.html at master · jmmccota/Otimizacao

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

<!DOCTYPE html>

<head>

<title>Solver - BranchBound</title>

</head>

<body>

<a class="logo" style="font-size: 30px;">Branch-and-Bound<span>Programação Linear Inteira Mista</span></a>

</div>

</ul>

</div>

</div>

<ul>

<li><a href="index.html">Início</a></li>

<li class="parent"><a href="simplex.html">Simplex</a>

<ul>

<li>Simplex

<ul>

<li><a href="simplex.html">Começar</a></li>

<li><a href="simplex_about.html">Mais sobre o Modelo</a></li>

</ul>

</li>

</ul>

</li>

<li class="parent"><a href="branchbound.html">Branch-and-Bound</a>

<ul>

<li>Branch-and-Bound

<ul>

<li><a href="branchbound.html">Começar</a></li>

<li><a href="#">Mais sobre o Modelo</a></li>

</ul>

</li>

</ul>

</li>

<li class="parent"><a href="transporte.html">Transporte</a>

<ul>

<li>Transporte

<ul>

<li><a href="transporte.html">Começar</a></li>

<li><a href="transporte_about.html">Mais sobre o Modelo</a></li>

</ul>

</li>

</ul>

</li>

</ul>

</nav>

</div>

</div>

</header>

</div>

</div>

<h2 id="sec0">Introdução </h2>

<hr>

<p>

A programação Linear Inteira Mista tem uma grande vantagem em relação a Programação Inteira que é permitir que sejam incluídos

na análise os custos fixos, bem como diferentes níveis de custos variáveis para as instalações. Estes

problemas possuem soluções mais complexa em relação aqueles que utilizam a Programação Linear. Contudo

na Programação Linear, existem condições necessárias e suficientes de otimização teoricamente provadas

que podem ser utilizadas para testar eficientemente se uma dada solução viável é uma solução ótima

ou não.

</p>

<p>

A Programação Linear está preocupada com a maximização ou minimização de uma equação sobre certos critérios ou restrições.

Abaixo temos um exemplo:

</p>

<h4> Exemplo:</h4></div>

</center>

</div>

<p> Este problema pode ser resolvido pelo Método Simplex ou Simplex duas Fases. A solução ótima

se encontra abaixo: </p>

`x = (x_1,x_2,x_3) = (0.5,0,1.5)`

</center>

</blockquote>

</div>

<p>

Problemas como estes são utilizados em todas as empresas para minimizar o desperdício, maximizar lucro, ou otimizar a outros

aspectos do negócio . No entanto, algumas partes da solução pode ser limitada a números inteiros,

`x in Z^+`

</p>

<p>

Programação linear inteira mista é uma PL(Programação Linear) que existe alguma ou todas as variáveis não inteiras. Portanto

precisamos de encontrar uma nova solução ótima para evitarmos casos de números parciais. Simplesmente

com o arredondamento, a solução muitas vezes pode sair da região viável, comprometendo a otimalidade.

</p>

<br>

<h2 id="sec1">Resolvendo PLIM Usando Branch-Bound</h2>

<hr>

<p>

O problema com a resolução de PLIMs usando o método Simplex é que ele frequentemente retorna

partes de ` x = (x_1,x_2,x_3)` que não estão em forma de número inteiro.

</p>

<p>

Para resolver usando o Branch and Bound, primeiro resolvemos o problema usando o Relaxamento, o que significa resolvê-lo

pelo Simplex Revisado como se não houvesse restriç&odblac;es inteiras. Assim, obtemos:

` z = cx`.

</p>

<p>

Como o exemplo usado envolve um problema de maximização que engloba todas as soluç&odblac;es inteiras,

então esse é um limite superior da PLIM. Em seguida, escolhe-se uma variável

não inteira. Comumente, escolhe-se a variável mais fracionada, que esteja mais próxima

do valor mediano ou mais distante de um número inteiro.

</p>

<p>

Por exemplo, em ` x = (1.25, 3.45, 2.75, 5)`, escolhe-se ramificar em `x_2`, pois `0.45` está mais próximo

de `0.5` do que as outras fraç&odblac;es. A partir disso, criamos dois subproblemas ou dois

nodos de nossa árvore. Em um nó adicionamos a restrição `x_2

<=3`, na outra adicionamos `x_2>=4`. Seja `S` o conjunto solução viável do relaxamento: `S = {x: Ax

<=b\ e\ x>=0}`, temos que:

</p>

` S_1 = S \cap{x:x_j

<=\ lfloor\hat{x}_j\rfloor\} ` ` S_1=S \cap{x:x_j>= \ceil{hat{x}_j}} `

</center>

</blockquote>

</div>

<p>

Então, cada um dos nós devem ser resolvidos com suas novas restriç&odblac;es pelo método Dual

Simplex. Caso o problema seja inviável, então o nó é cortado por inviabilidade.

A solução ótima é encontrada quando todos os nós fracionários

são cortados.

</p>

</div>

</div>

</div>

</div>

</span>

</div>

<a class="logo" href="index.html">SIMO<span>Sistema Interativo para Métodos de Otimização</span></a>

</div>

<li><a href="faq.html">Dúvidas</a></li>

<li><a href="http://timoteo.cefetmg.br">CEFET-MG Campus Timóteo</a></li>

</ul>

</div>

</div>

</footer>

MathJax.Hub.Queue(["Typeset", MathJax.Hub]);

</script>

</body>

</html>

FilesExpand file tree

branchbound_about.html

Latest commit

History

branchbound_about.html

File metadata and controls