-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsimplex_about.html
356 lines (338 loc) · 19.9 KB
/
simplex_about.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
<!DOCTYPE html>
<html lang="pt-br">
<head>
<!-- Meta -->
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Algoritmos de Pesquisa Operacional">
<!-- End of meta -->
<!-- Title -->
<title>Solver - Simplex</title>
<!-- End of title -->
<!-- Stylesheets -->
<link rel="stylesheet" type="text/css" href="css/style.css" />
<link rel="stylesheet" type="text/css" href="css/light.css" id="scheme" />
<link rel="stylesheet" type="text/css" href="css/responsive-nav.css" />
<link rel="stylesheet" type="text/css" href="css/font-awesome.min.css" />
<link rel="stylesheet" type="text/css" href="css/bootstrap.css">
<link rel="stylesheet" type="text/css" href="css/opensans.css">
<link rel="stylesheet" type="text/css" href="css/colors/green.css" id="colors" />
<!-- End of stylesheets -->
<link href="img/simplex/favicon.ico" rel="icon" type="image/x-icon" />
</head>
<body>
<!-- Header -->
<header>
<div class="top container">
<!-- Logo area -->
<div class="logo-left-bg"></div>
<div class="logo-left one-fourth">
<!-- Logo -->
<a class="logo">Simplex<span>Programação Linear</span></a>
<!-- End of logo -->
</div>
<!-- End of logo area -->
<!-- Top right -->
<div class="top-right three-fourth last-in-row">
<!-- Top bar -->
<div class="top-bar">
<!-- Social icons -->
<div class="top-social-icons">
<ul class="footer-social social-icons">
<li><a href="#"><i class="icon-facebook"></i></a></li>
<li><a href="https://github.com/jmmccota/Otimizacao"><i class="icon-github"></i></a></li>
</ul>
</div>
<!-- End of social icons-->
</div>
<!-- End of top bar -->
<!-- Main navigation -->
<nav id="nav">
<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="#">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="branchbound_about.html">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>
<!--<li><a href="contato.html">Contato</a></li>-->
</ul>
</nav>
<!-- End of main navigation -->
</div>
<!-- End of top right -->
</div>
</header>
<!-- End of header -->
<!-- Page Title -->
<div id="page-title">
<!--<h1 class="container">Simplex<span class="sub-title">Programação Linear</span>-->
</div>
<!-- End of page title -->
<!-- Content -->
<div id="content" class="clearfix">
<!-- Breadcumbs -->
<div class="breadcumbs">
</div>
<!-- End of breadcumbs -->
<!-- Container -->
<div class="container">
<div class="row">
<!--right-->
<div class="col-md-12" id="pagModelo">
<h2 id="sec0">Introdução </h2>
<hr>
<p>
A Programação Linear (PL) tem sido uma importante ferramenta de análise para grandes empresas pelo mundo. Em um breve resumo,
ela se propôe a otimizar recursos limitados para atividades que competem entre si.
</p>
<p>
A Programação Linear utiliza de um modelo matemático para descrever o problema proposto. Através desse modelo proposto, é
feita uma análise gráfica, mostrando qual será a região de soluções viáveis. Segue-se abaixo um exemplo
da região com as retas de restriçoes de um problema:
</p>
<div class="row">
<div class="col-md-6 col-sm-6 col-md-offset-3">
<div class="panel panel-primary secondary ">
<div class="panel-heading">
<h4> Exemplo:</h4></div>
<div class="panel-body">
<img src="img/simplex/img_solviavel.png" class="img-responsive">
</div>
</div>
</div>
</div>
<p> A determinação da solução ótima requer identificar a direção na qual a função objetivo z aumenta (maximização)
ou diminue (minimização). O ponto dentro da região viável onde z é maior (maximização) ou menor (minimização)
será a solução ótima.</p>
<p>Segue-se abaixo um exemplo:</p>
<div class="row">
<div class="col-md-6 col-sm-6">
<div class="panel panel-primary secondary ">
<div class="panel-heading">
<h4> Exemplo:</h4></div>
<div class="panel-body">
<img src="img/simplex/img_solviavel2.png" class="img-responsive">
</div>
</div>
</div>
<div class="col-md-6 col-sm-6">
<blockquote>
<p> Solução: </p>
<center>
A solução ótima se encontra no ponto C.
</center>
</blockquote>
</div>
</div>
<br>
<h2 id="sec1">Resolvendo PL Usando método Simplex </h2>
<p>O método Simplex não enumera todas as soluções básicas (pontos extremos), porém ele analisa algumas dessas
soluções selecionadas.</p>
<p>Abaixo é representado um modelo de PL com a região de soluções viável.</p>
<div class="col-md-6 col-sm-6">
<div class="panel panel-primary secondary ">
<div class="panel-heading">
<h4> Modelo de PL:</h4></div>
<div class="panel-body">
<img src="img/simplex/exemplo2.png" class="img-responsive">
</div>
</div>
</div>
<div class="col-md-6 col-sm-6">
<div class="panel panel-primary secondary ">
<div class="panel-heading">
<h4> Região de Soluções viável:</h4></div>
<div class="panel-body">
<img src="img/simplex/exemplo3.png" class="img-responsive">
</div>
</div>
</div>
<p>O método iterativo normalmente inicia no ponto de origem A. Logo após, é analisada se a utilização de
um ponto com x1 ou x2 maior que 0 poderia melhorar a função objetivo z. Analisando a função objetivo
podemos afirmar que sim.</p>
<p>O projeto Simplex exige que se melhore apenas uma variável por vez, analisando qual delas traria uma
maior taxa de melhora para a função objetivo. Para o exemplo citado, o valor da função objetivo aumentará
em 2 para cada unidade de x1 e 3 para cada unidade de x2. Portanto, a variável escolhida seria x2.
A figura mostra que x2 será aumentado até alcançar o ponto extremo B.</p>
<p>Logo após, o valor de x1 será aumentado até alcançar o ponto C que é o ótimo. Portanto, o método percorre
um caminho pelas bordas, até atingir um valor ótimo.
<p>Segue-se abaixo uma estrutura de representação para o método:</p>
<div class="row">
<div class=" col-md-10 col-sm-10 col-md-offset-1">
<div class="panel panel-primary secondary ">
<div class="panel-heading">
<h4> Estrutura do Simplex:</h4></div>
<div class="panel-body">
<img src="img/simplex/exemplo4.png" class="img-responsive">
</div>
</div>
</div>
</div>
<br>
<h2 id="sec2">Método Simplex de Grande-M</h2>
<p>
De acordo com o problema de PL, se houverem restrições do problema que demandem variáveis artificiais,
elas são adicionadaspara formar uma solução inicial semelhante é solução básica em que todas as variáveis são de folga.
Contudo, como essas variáveis não fazem parte do modelo original, elas recebem punições muito alta na função objetivo, forçando-as
a ter o valor 0 na solução ótima.
<p>Portanto, para o problema abaixo, é inserida variáveis artificiais para as 2 primeiras equações, e elas são inseridas com suas punições na função
objetivo (a soma delas é pelo fato do problema ser de minimização).</p>
<p>O valor de M a ser usado depende do problema, ele deve ser suficientemente grande em relação
aos coeficientes da função objetivo original.</p>
<div class="row">
<div class="col-md-6 col-sm-6">
<div class="panel panel-primary secondary ">
<div class="panel-heading"><h4> Modelo de PL:</h4></div>
<div class="panel-body">
<img src="img/exemplo5.png" class="img-responsive">
</div>
</div>
</div>
<div class="col-md-6 col-sm-6">
<div class="panel panel-primary secondary ">
<div class="panel-heading"><h4> Método Grande-M</h4></div>
<div class="panel-body">
<img src="img/exemplo6.png" class="img-responsive">
</div>
</div>
</div>
</div>
<br>
<h2 id="sec3">Método Simplex de Duas Fases</h2>
<p>No método do Simplex Grande-M, as punições M devem ser grandes em relação aos coeficientes da função objetivo, resultando
assim em erros significativos de arredondamento. O método do Simplex Duas Fases elimina essa constante M.</p>
<p>O método Duas Fases como o nome já diz, resolve o problema em duas fases:</p>
<ul>
<li>Fase I: Tenta achar uma solução básica inicial, e se ela for encontrada passa para a Fase II.</li>
<li>Fase II: É invocada para resolver o problema original.</li>
</ul>
<p> Como um resumo de atuação do método, temos:</p>
<div class="row">
<div class="col-md-8 col-sm-8 col-md-offset-2">
<div class="panel panel-primary secondary ">
<div class="panel-heading"><h4> Resumo do Método das Duas Fases</h4></div>
<div class="panel-body">
<img src="img/exemplo7.png" class="img-responsive">
</div>
</div>
</div>
</div>
<br>
<h2 id="sec3">Método Simplex Generalizado</h2>
<p>O Simplex generalizado é utilizado quando a solução básica inicial é não factível e não ótima.
As restrições do modelo devem ser somente da relação menor igual. </p>
<p>Este método combina o simplex primal com o simplex dual. Portanto, quando a solução é infactível, usa-se
as regras do simplex dual até reestabelecer a viabilidade ou certificar que não existe solução factível.
Quando a solução é factível, usa-se as regras do simplex primal.</p>
<p>Um facilitador no uso do Simplex generalizado, é que não existe a necessidade de uso de variáveis artificiais.</p>
<div class="row">
<div class="col-md-4 col-sm-4">
<div class="panel panel-primary secondary ">
<div class="panel-heading"><h4> Modelo de PL:</h4></div>
<div class="panel-body">
<img src="img/exemplo8.png" class="img-responsive">
</div>
</div>
</div>
<div class="col-md-4 col-sm-4">
<div class="panel panel-primary secondary ">
<div class="panel-heading"><h4> Apenas restrições menor igual</h4></div>
<div class="panel-body">
<img src="img/exemplo9.png" class="img-responsive">
</div>
</div>
</div>
<div class="col-md-4 col-sm-4">
<div class="panel panel-primary secondary ">
<div class="panel-heading"><h4>Inserção de variáveis de folga</h4></div>
<div class="panel-body">
<img src="img/exemplo10.png" class="img-responsive">
</div>
</div>
</div>
</div>
</div>
</div>
<!--/right-->
</div>
<!--/row-->
</div>
<!-- End of content -->
<div class="scroll-top-wrapper ">
<span class="scroll-top-inner">
<i class="glyphicon glyphicon-arrow-up"></i>
</span>
</div>
<!-- Footer -->
<footer>
<!-- Footer second row -->
<div class="footer-second-row">
<div class="container">
<!-- Logo area -->
<div class="logo-left-bg"></div>
<div class="logo-left one-fourth">
<!-- Logo -->
<a class="logo" href="index.html">SIMO<span>Sistema Interativo para Métodos de Otimização</span></a>
<!-- End of logo -->
</div>
<!-- End of logo area -->
<!-- Copyright and small menu -->
<div class="copyright-area three-fourth last-in-row">
<!--<span class="copyright">© Copyright 2016 by CEFET-MG. Todos os direitos reservados.</span>-->
<ul class="small-menu">
<!--<li><a href="faq.html">Dúvidas</a></li>-->
<li><a href="http://timoteo.cefetmg.br">CEFET-MG Campus Timóteo</a></li>
<!--<li><a href="contato.html">Contato</a></li>-->
</ul>
</div>
<!-- End of copyright and small menu -->
</div>
</div>
<!-- End of footer second row -->
</footer>
<!-- End of footer -->
<!-- Scripts -->
<script type="text/javascript" src="js/jquery/jquery-1.8.3.min.js"></script>
<script type="text/javascript" src="js/jquery/jquery-ui-1.10.3.custom.min.js"></script>
<script type="text/javascript" src="js/jquery/jquery.flexslider.js"></script>
<script type="text/javascript" src="js/jquery/jquery.fitvids.js"></script>
<script type="text/javascript" src="js/responsive-nav.js"></script>
<script type="text/javascript" src="js/jquery/jquery.touchSwipe.min.js"></script>
<!-- Scripts Configuration -->
<script type="text/javascript" src="js/custom.js"></script>
<!-- End of scripts configuration -->
<script type="text/javascript" src="js/ASCIIMathML.js"></script>
<script type="text/javascript" src="js/MathJax/MathJax.js?config=AM_HTMLorMML"></script>
<script>
MathJax.Hub.Queue(["Typeset", MathJax.Hub]);
</script>
<script type="text/javascript" src="js/analytics.js"></script>
<!-- End of scripts -->
</body>
</html>