Thesis (D.P.H.)--University of Michigan.

Thesis (M.S.W.)--Smith College School for Social Work, Northampton, Mass., 2009. / Includes bibliographical references (p. 65-68).

Thesis (M.S.)--Brigham Young University. Dept. of Microbiology and Molecular Biology, 2005. / Includes bibliographical references.

Thèse (Ph.D.)--Université Laval, 2004. / Titre de l'écran-titre (visionné le 29 novembre 2004). Bibliogr.

Dissertation (D.P.H.)--University of Michigan.

Thesis (M.S.)--University of Florida, 2004. / Typescript. Title from title page of source document. Document formatted into pages; contains 65 pages. Includes Vita. Includes bibliographical references.

Thesis (Ph.D.)--McMaster University, 2004. / Advisor: John P. Capone. Includes bibliographical references (p. 179-[208]). Available also online.

Το πρώτο κεφάλαιο περιλαμβάνει μια ιστορική αναδρομή σχετικά με τη γέννηση και την ανάπτυξη της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Επίσης παρουσιάζεται το χρονικό των μεγαλυτέρων ανακαλύψεων: ο αλγόριθμος Simplex (Dantzig-1949), ο ελλειψοειδής αλγόριθμος (Khachian-1979) και ο αλγόριθμος εσωτερικών σημείων (Karmarkar-1983). Στη συνέχεια - δεύτερο κεφάλαιο - γίνεται η θεωρητική θεμελίωση της μεθόδου Simplex, συμπεριλαμβάνοντας τόσο την γεωμετρική-εποπτική παρουσίαση της μεθόδου, όσο και την αυστηρή αλγεβρική τεκμηρίωσή της μέσω θεωρημάτων. Το τρίτο κεφάλαιο αφιερώθηκε στον αλγόριθμο των ελλειψοειδών, στη μέθοδο δηλαδή που ουσιαστικά απέδειξε ότι τα προβλήματα του γραμμικού προγραμματισμού μπορούν να λυθούν σε πολυωνυμικό χρόνο. Στο τέταρτο κεφάλαιο παρουσιάζεται η πιο σύγχρονη τάση στον τομέα επίλυσης προβλημάτων γραμμικού προγραμματισμού: οι μέθοδοι εσωτερικού σημείου. Συγκεκριμένα αναπτύσσεται ο αλγόριθμος του Karmakar, η κατηγορία των μεθόδων ομοπαραλληλικής αλλαγής κλίμακας και ο πρωτεύοντας-δυϊκός αλγόριθμος εσωτερικού σημείου. Τέλος, στο πέμπτο κεφάλαιο περιλαμβάνεται η παρουσίαση της έννοιας της υπολογιστικής πολυπλοκότητας αλγορίθμων, η πλήρης ανάλυση της πολυπλοκότητας των αλγορίθμων Simplex και εσωτερικού σημείου του Karmakar, καθώς και η σύγκριση των δύο αλγορίθμων. / The first chapter includes a historical retrospection in respect of the birth and growth of Operational Research and Linear Programming. Furthermore, the chronicle of the biggest discoveries is presented: the Simplex algorithm (Dantzig-1949), the ellipsoid algorithm (Khachian-1979) and the interior point algorithm (Karmarkar-1983). Thereafter -in the second chapter- the theoretical foundation of Simplex method is presented, including both the geometric- supervisory presentation and the strict algebraic documentation of the method via theorems. The third chapter refers to the ellipsoid algorithm, namely the method that proved that the problems of linear programming can be solved in polynomial time. In the fourth chapter, the most contemporary tendency in the field of solving problems of linear programming, is presented: the methods of interior point. Particularly, the algorithm of Karmakar and the primal-dual algorithm of interior point are expounded. Finally, the fifth chapter includes the presentation of the concept of computational complexity of algorithms, the complete analysis of complexity of algorithms Simplex and interior point of Karmakar, as well as the comparison of the two algorithms.

Made available in DSpace on 2014-06-11T19:30:50Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-23Bitstream added on 2014-06-13T20:40:36Z : No. of bitstreams: 1 righetto_e_dr_ilha.pdf: 923323 bytes, checksum: f390d9baa00b45f3196dda419f801f19 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho apresenta-se uma estratégia de programação linear especializada para resolver, de forma eficiente, o problema de planejamento da expansão de sistemas de transmissão de energia elétrica usando o algoritmo de busca em vizinhança variável (VNS). O modelo matem´atico para este problema é um modelo de programação linear inteira mista. A solução deste modelo através de metaheurísticas, dependendo do sistema elétrico sob análise, pode exigir a solução de centenas de milhares de problemas de programação linear (PL) que exigem elevado esforço computacional e consomem a maior parte do tempo de CPU exigido pela metaheurística. A ideia fundamental deste artigo consiste em identificar soluções básicas adequadas para iniciar o processo de solução do problema de planejamento da transmissão e os inúmeros problemas de PL exigidos pela metaheurística, fazendo que os problemas de PL sejam resolvidos de forma eficiente computacionalmente. A solução básica adequada consiste na definição uma base dual factível específica para o problema que permite que novos problemas de PL resultantes das alterações de alguns parâmetros do problema de planejamento possam ser resolvidos usando um algoritmo dual simplex canalizado. A metodologia proposta foi validada e testada em um sistema de médio porte / This paper presents a linear programming expert strategy to solve efficiently the energy transmission network expansion planning problem using the variable neighborhood search algorithm (VNS). The mathematical model used is a mixed integer linear programming problem. Solution of this model using different metaheuristics, depending on the electrical system under analysis, may require hundreds of thousands of linear programming problems (LP) which require high computational effort and consume almost all of the CPU time required by the metaheuristic. The basic idea of this paper is to identify appropriate basic solutions which help to start the process and speed up the solution of the many subsequent subproblems generated during a typical run, solving the LP problems efficiently. The starting basic solution is defined as an appropriate dual feasible basis for the specific problem, new LP problems resulting from changes in some parameters of the planning problem are solved using a bounded dual simplex algorithm. The proposed methodology was validated and tested in a system of medium size

Made available in DSpace on 2014-06-11T19:30:52Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-04-29Bitstream added on 2014-06-13T19:00:51Z : No. of bitstreams: 1 hashimoto_shm_dr_ilha.pdf: 3505990 bytes, checksum: 86eb5da27160760afefec6614a16a090 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / O problema de planejamento de sistemas de transmissão é um problema de programação não-linear inteira mista (PNLIM) quando é usado o modelo DC. Praticamente todos os algoritmos usados para resolver este problema utilizam uma subrotina de programação linear (PL) para resolver problemas de PL resultantes do algoritmo de solução do problema de planejamento. Às vezes a resolução desses problemas de PL representa o maior esforço computacional dos algoritmos de planejamento. A particularidade desses problemas de PL é que, na solução ótima, apenas algumas restrições de desigualdade estão ativas. Este trabalho considera a formulação e a implementação computacional de vários algoritmos de PL resultantes, ou seja, os algoritmos propostos fazem modificações nos problemas de PL resultantes dos modelos de transportes e DC de maneira que apresentam uma única restrição de igualdade, a equação de balanço de potência ativa, e muitas restrições de desigualdade. É usado um algoritmo dual simplex canalizado e uma estratégia de relaxação para resolver esses problemas de PL que inicia o processo de otimização com uma única restrição de igualdade e, em cada passo, é adicionada a restrição mais violada. Portanto, a lógica de trabalho é parecida com a proposta apresentada por Brian Stott para o planejamento da operação de sistemas elétricos. Os resultados encontrados mostram um desempenho superior do algoritmo quando comparados com métodos do tipo primal simplex. / The transmission network planning problem is a non linear integer mixed programming problem (NLIMP) which used the DC model. Most of the algorithms used to solve this problem use a linear programming subroutine (LP) to solve LP problems resulting from planning algorithms. Sometimes the resolution of these LP problems represents a major computational effort of planning algorithms. The particularity of these LP problems in optimal solution is that only some inequality constraints are binding. This work considers the formulation and the computational implementation of algorithms several of the LP problems resulting, i.e., the proposed algorithms make modifications in the LP problems resulting of the transports and DC models so that present an only equality constraint, only one equality constraint, the power flow equation, and many inequality constraints. It is used a dual simplex algorithm and a relaxation strategy to solve these LP problems_ which start the optimization process with only one equality constraint and, in each step, the most unfeasible constraint is added. Then, the logic used is similar to the proposal presented in Brian Stott for electric systems operation planning. The results show a higher performance of the algorithm when compared to primal simplex methods.