To see the other types of publications on this topic, follow the link: LINEAR PROGRAMMING PROBLEM (LPP).
Dissertations / Theses on the topic 'LINEAR PROGRAMMING PROBLEM (LPP)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'LINEAR PROGRAMMING PROBLEM (LPP).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Espinoza, Daniel G. "On Linear Programming, Integer Programming and Cutting Planes." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/10482.
Full textAbstract:
In this thesis we address three related topic in the field of Operations Research.
Firstly we discuss the problems and limitation of most common solvers for linear programming, precision.
We then present a solver that generate rational optimal solutions to linear programming problems by solving a succession of (increasingly more precise) floating point approximations of the original rational problem until the rational optimality conditions are achieved.
This method is shown to be (on average) only 20% slower than the common pure floating point approach, while returning true optimal solutions to the problems.
Secondly we present an extension of the Local Cut procedure introduced by Applegate et al, 2001, for the Symmetric Traveling Salesman Problem (STSP), to the general setting of MIP problems.
This extension also proves finiteness of the separation, facet and tilting procedures in the general MIP setting, and also provides conditions under which the separation procedure is guaranteed to generate cuts that separate the current fractional solution from the convex hull of the mixed-integer polyhedron.
We then move on to explore some configurations for local cuts, realizing extensive testing on the instances from MIPLIB.
Those results show that this technique may be useful in general MIP problems, while the experience of Applegate et al, shows that the ideas can be successfully applied to structures problems as well.
Thirdly we present an extensive computational experiment on the TSP and Domino Parity inequalities as introduced by Letchford, 2000.
This work also include a safe-shrinking theorem for domino parity inequalities, heuristics to apply the planar separation algorithm introduced by Letchford to instances where the planarity requirement does not hold, and several practical speed-ups.
Our computational experience showed that this class of inequalities effectively improve the lower bounds from the best relaxations obtained with Concorde, which is one of the state of the art solvers for the STSP.
As part of these experience, we solved to optimality the (up to now) largest two STSP instances, both of them belong to the TSPLIB set of instances and they have 18,520 and 33,810 cities respectively.
2
Cregger, Michael L. "The general mixed-integer linear programming problem an empirical analysis /." Instructions for remote access. Click here to access this electronic resource. Access available to Kutztown University faculty, staff, and students only, 1993. http://www.kutztown.edu/library/services/remote_access.asp.
Full text
3
Hocking, Peter M. "Solving the binary integer bi-level linear programming problem /." Electronic version (PDF), 2004. http://dl.uncw.edu/etd/2004/hockingp/peterhocking.pdf.
Full text
4
Tinti, Laura. "Mixed Integer Linear Programming Models for a Stowage Planning Problem." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2018.
Find full textAbstract:
The aim of this thesis is to deepen the Containership Stowage Planning Problem (CSPP). In general terms, this problem consists of finding optimal plans for stowing containers into a containership, satisfying several restrictions. This topic has a lot of variations regarding the objective functions and the constraints required, depending on the situation taken into account. This dissertation is developed by referring to a real case, with its specific objective function and restrictions. In the first part of this thesis, an overview on the different approaches given by the literature is provided. After this outline, a Mixed Integer Linear Programming Model is proposed with the goal of finding feasible solutions for the CSPP. A consistent number of instances is generated to analyze how the model performs depending on the input parameters. The model is then tested by using CPLEX Solver in the mathematical programming and optimization modelling language AMPL. Finally, the importance of the stability of the vessel is underlined. Constraints concerning the ship stability are added to the model and, throughout other tests in AMPL, the computational results and the comparison to the results previously obtained are evaluated.
5
DASTMARD, SOHOF. "The Asymmetric Travelling Salesman Problem : A Linear Programming Solution Approach." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-157412.
Full textAbstract:
The travelling salesman problem is a well known optimization problem. The goal is to nd theshortest tour that visits each city in a given list exactly once. Despite the simple problem statementit belongs to the class of NP-complete problems. Its importance arises from a plethora of applicationsas well as a theoretical appeal. The asymmetric TSP is not as well researched as the symmetric TSP,in this paper we focus on a solution approach suitable for the asymmetric case. We demonstrate howa linear programming formulation can be used to solve the problem. We also show the limitationsof this solution approach and provide suggestions for improving it.i
6
Sariklis, Dimitrios. "Open Vehicle Routing Problem : description, formulations and heuristic methods." Thesis, London School of Economics and Political Science (University of London), 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.265252.
Full text
7
Tanksley, Latriece Y. "Interior point methods and kernel functions of a linear programming problem." Click here to access thesis, 2009. http://www.georgiasouthern.edu/etd/archive/spring2009/latriece_y_tanksley/tanksley_latriece_y_200901_ms.pdf.
Full textAbstract:
Thesis (M.S.)--Georgia Southern University, 2009.<br>"A thesis submitted to the Graduate Faculty of Georgia Southern University in partial fulfillment of the requirements for the degree Master of Science." Directed by Goran Lesaja. ETD. Includes bibliographical references (p. 76) and appendices.
8
Islam, Mohammad Tauhidul, and University of Lethbridge Faculty of Arts and Science. "Approximation algorithms for minimum knapsack problem." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009, 2009. http://hdl.handle.net/10133/1304.
Full textAbstract:
Knapsack problem has been widely studied in computer science for years. There exist several
variants of the problem, with zero-one maximum knapsack in one dimension being
the simplest one. In this thesis we study several existing approximation algorithms for the
minimization version of the problem and propose a scaling based fully polynomial time approximation
scheme for the minimum knapsack problem. We compare the performance of
this algorithm with existing algorithms. Our experiments show that, the proposed algorithm
runs fast and has a good performance ratio in practice. We also conduct extensive experiments
on the data provided by Canadian Pacific Logistics Solutions during the MITACS
internship program.
We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional)
minimum knapsack problem and compare its performance with a generalization of a greedy
algorithm for minimum knapsack in d dimensions. Our experiments show that the e-
approximation scheme exhibits good performance ratio in practice.<br>x, 85 leaves ; 29 cm
9
Adams, Warren Philip. "The mixed-integer bilinear programming problem with extensions to zero-one quadratic programs." Diss., Virginia Polytechnic Institute and State University, 1985. http://hdl.handle.net/10919/74711.
Full textAbstract:
This research effort is concerned with a class of mathematical programming problems referred to as Mixed-Integer Bilinear Programming Problems. This class of problems, which arises in production, location-allocation, and distribution-application contexts, may be considered as a discrete version of the well-known Bilinear Programming Problem in that one set of decision variables is restricted to be binary valued. The structure of this problem is studied, and special cases wherein it is readily solvable are identified. For the more general case, a new linearization technique is introduced and demonstrated to lead to a tighter linear programming relaxation than obtained through available linearization methods. Based on this linearization, a composite Lagrangian relaxation-implicit enumeration-cutting plane algorithm is developed. Extensive computational experience is provided to test the efficiency of various algorithmic strategies and the effects of problem data on the computational effort of the proposed algorithm.
The solution strategy developed for the Mixed-Integer Bilinear Programming Problem may be applied, with suitable modifications,. to other classes of mathematical programming problems: in particular, to the Zero-One Quadratic Programming Problem. In what may be considered as an extension to the work performed on the Mixed-Integer Bilinear Programming Problem, a solution strategy based on an equivalent linear reformulation is developed for the Zero-One Quadratic Programming Problem. The strategy is essentially an implicit enumeration algorithm which employs Lagrangian relaxation, Benders' cutting planes, and local explorations. Computational experience for this problem class is provided to justify the worth of the proposed linear reformulation and algorithm.<br>Ph. D.
10
de, Farias Ismael Jr. "A polyhedral approach to combinatorial complementarity programming problems." Diss., Georgia Institute of Technology, 1995. http://hdl.handle.net/1853/25574.
Full text
11
Likeman, Martin. "A study of centralised and distributed problem solving applied to water supply scheduling." Thesis, University of Reading, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.241628.
Full text
12
Grover, Samir. "Solving layout compaction and wire-balancing problem using linear programming on the Monsoon multiprocessor." Thesis, Connect to online version, 1995. http://0-wwwlib.umi.com.mercury.concordia.ca/cr/concordia/fullcit?pMQ90885.
Full text
13
Tang, Yuehao. "A mixed integer-linear programming model for solving the hydroelectric unit maintenance scheduling problem." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/31269.
Full textAbstract:
The unit maintenance scheduling problem is traditionally a challenging topic for electric
utilities. In general, the system operators schedule the generating units for maintenance
periodically. Research on the maintenance scheduling problem started in 1960's in the last
century and has continued until today. Although significant contributions were made as a results
of this continuous investigations, but many of those approaches were made in specific areas as
different systems have their own special characteristics, such as system reliability considerations.
According to the literature cited to-date, there is not one a successful case reported for
maintenance scheduling of a pure hydro or hydro-dominated generating system.
This thesis outlines an optimization modelling approach that is based on the linear
programming techniques to solve the maintenance scheduling problem for hydro systems. This
research focused on the potential use of mixed-integer/linear programming algorithms to solve
the maintenance scheduling problem for a large scale hydroelectric system. The objective was to
determine the best "timing" for each unit outage in the system. This thesis reformulated an
existing hydro scheduling model and concentrated on the set of constraints that could effectively
satisfy the maintenance scheduling requirements.
The case studies carried out revealed that the most appropriate mixed-integer
maintenance scheduling model would be formulated in such a way that it develops a
maintenance schedule that ensures that the plants are operated in a way to maximize system
efficiency and that head convergence have an influence on hydroelectric unit outage scheduling
algorithm. Integer programming methods are usually considered suitable for maintenance
scheduling problems, but in view of the complexities inherent in hydro models and in mixed-integer
programming algorithms, it was found that it is very difficult to generalize one
standardized approach to effectively handle this complex and large scale problem. Therefore, this
research has focused on two main points. One focused on decreasing the number of possible
binary variables in the model. The second focused on finding an appropriate algorithm that could
approximate and reasonably simplify the computational process and transforms non-linear
constraints into linear ones. It was also found that without specifically or delicately designing the
maintenance scheduling constraints, the problem will be hard to solve even by the latest
commercially available algorithms.<br>Applied Science, Faculty of<br>Civil Engineering, Department of<br>Graduate
14
Bucco, Guilherme Brandelli. "Construção de um modelo de programação linear para o University Timetabling Problem." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/101491.
Full textAbstract:
A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula.<br>The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.
15
Ng, Yik Lun. "Discriminative training of stream weights in a multi-stream HMM as a linear programming problem /." View abstract or full-text, 2008. http://library.ust.hk/cgi/db/thesis.pl?CSED%202008%20NG.
Full text
16
Hamilton, Daniel. "Decomposition and diet problems." Thesis, University of Edinburgh, 2010. http://hdl.handle.net/1842/3798.
Full textAbstract:
The purpose of this thesis is to efficiently solve real life problems. We study LPs. We study an NLP and an MINLP based on what is known as the generalised pooling problem (GPP), and we study an MIP that we call the cattle mating problem. These problems are often very large or otherwise difficult to solve by direct methods, and are best solved by decomposition methods. During the thesis we introduce algorithms that exploit the structure of the problems to decompose them. We are able to solve row-linked, column-linked and general LPs efficiently by modifying the tableau simplex method, and suggest how this work could be applied to the revised simplex method. We modify an existing sequential linear programming solver that is currently used by Format International to solve GPPs, and show the modified solver takes less time and is at least as likely to find the global minimum as the old solver. We solve multifactory versions of the GPP by augmented Lagrangian decomposition, and show this is more efficient than solving the problems directly. We introduce a decomposition algorithm to solve a MINLP version of the GPP by decomposing it into NLP and ILP subproblems. This is able to solve large problems that could not be solved directly. We introduce an efficient decomposition algorithm to solve the MIP cattle mating problem, which has been adopted for use by the Irish Cattle Breeding Federation. Most of the solve methods we introduce are designed only to find local minima. However, for the multifactory version of the GPP we introduce two methods that give a good chance of finding the global minimum, both of which succeed in finding the global minimum on test problems.
17
Snellings, Christopher. "Effective Network Partitioning to Find MIP Solutions to the Train Dispatching Problem." VCU Scholars Compass, 2013. http://scholarscompass.vcu.edu/etd/3285.
Full textAbstract:
Each year the Railway Applications Section (RAS) of the Institution for Operations Research and the Management Sciences (INFORMS) posits a research problem to the world in the form of a competition. For 2012, the contest involved solving the Train Dispatching Problem (TDP) on a realistic 85 edge network for three different sets of input data. This work is an independent attempt to match or improve upon the results of the top three finishers in the contest using mixed integer programming (MIP) techniques while minimizing the use of heuristics. The primary focus is to partition the network in a manner that reduces the number of binary variables in the formulation as much as possible without compromising the ability to satisfy any of the contest requirements. This resulted in the ability to optimally solve this model for RAS Data Set 1 in 29 seconds without any problem-specific heuristics, variable restrictions, or variable fixing. Applying some assumptions about train movements allowed the same Data Set 1 solution to be found in 5.4 seconds. After breaking the larger Data Sets 2 and 3 into smaller sub-problems, solutions for Data Sets 2 and 3 were 28% and 1% better, respectively, than those of the competition winner. The time to obtain solutions for Data Sets 2 and 3 was 90 and 318 seconds, respectively.
18
Umetani, Shunji, Mutsunori Yagiura, and 睦憲 柳浦. "RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM." 日本オペレーションズ・リサーチ学会, 2007. http://hdl.handle.net/2237/11724.
Full text
19
Neamatian, Monemi Rahimeh. "Fixed cardinality linear ordering problem, polyhedral studies and solution methods." Thesis, Clermont-Ferrand 2, 2014. http://www.theses.fr/2014CLF22516/document.
Full textAbstract:
Le problème d’ordre linéaire (LOP) a reçu beaucoup d’attention dans différents domaines d’application, allant de l’archéologie à l’ordonnancement en passant par l’économie et même de la psychologie mathématique. Ce problème est aussi connu pour être parmi les problèmes NP-difficiles. Nous considérons dans cette thèse une variante de (LOP) sous contrainte de cardinalité. Nous cherchons donc un ordre linéaire d’un sous-ensemble de sommets du graphe de préférences de cardinalité fixée et de poids maximum. Ce problème, appelé (FCLOP) pour ’fixed-cardinality linear ordering problem’, n’a pas été étudié en tant que tel dans la littérature scientifique même si plusieurs applications dans les domaines de macro-économie, de classification dominante ou de transport maritime existent concrètement. On retrouve en fait ses caractéristiques dans les modèles étendus de sous-graphes acycliques. Le problème d’ordre linéaire est déjà connu comme un problème NP-difficile et il a donné lieu à de nombreuses études, tant théoriques sur la structure polyédrale de l’ensemble des solutions réalisables en variables 0-1 que numériques grâce à des techniques de relaxation et de séparation progressive. Cependant on voit qu’il existe de nombreux cas dans la littérature, dans lesquelles des solveurs de Programmation Linéaire en nombres entiers comme CPLEX peuvent en résoudre certaines instances en moins de 10 secondes, mais une fois que la cardinalité est limitée, ces mêmes instances deviennent très difficiles à résoudre. Sur les aspects polyédraux, nous avons étudié le polytope de FCLOP, défini plusieurs classes d’inégalités valides et identifié la dimension ainsi que certaines inégalités qui définissent des facettes pour le polytope de FCLOP. Nous avons introduit un algorithme Relax-and-Cut basé sur ces résultats pour résoudre les instances du problème. Dans cette étude, nous nous sommes également concentrés sur la relaxation Lagrangienne pour résoudre ces cas difficiles. Nous avons étudié différentes stratégies de relaxation et nous avons comparé les bornes duales par rapport à la consolidation obtenue à partir de chaque stratégie de relâcher les contraintes afin de détecter le sous-ensemble des contraintes le plus approprié. Les résultats numériques montrent que nous pouvons trouver des bornes duales de très haute qualité. Nous avons également mis en place une méthode de décomposition Lagrangienne. Dans ce but, nous avons décomposé le modèle de FCLOP en trois sous-problèmes (au lieu de seulement deux) associés aux contraintes de ’tournoi’, de ’graphes sans circuits’ et de ’cardinalité’. Les résultats numériques montrent une amélioration significative de la qualité des bornes duales pour plusieurs cas. Nous avons aussi mis en oeuvre une méthode de plans sécants (cutting plane algorithm) basée sur la relaxation pure des contraintes de circuits. Dans cette méthode, on a relâché une partie des contraintes et on les a ajoutées au modèle au cas où il y a des de/des violations. Les résultats numériques montrent des performances prometteuses quant à la réduction du temps de calcul et à la résolution d’instances difficiles hors d’atteinte des solveurs classiques en PLNE<br>Linear Ordering Problem (LOP) has receive significant attention in different areas of application, ranging from transportation and scheduling to economics and even archeology and mathematical psychology. It is classified as a NP-hard problem. Assume a complete weighted directed graph on V n , |V n |= n. A permutation of the elements of this finite set of vertices is a linear order. Now let p be a given fixed integer number, 0 ≤ p ≤ n. The p-Fixed Cardinality Linear Ordering Problem (FCLOP) is looking for a subset of vertices containing p nodes and a linear order on the nodes in S. Graphically, there exists exactly one directed arc between every pair of vertices in an LOP feasible solution, which is also a complete cycle-free digraph and the objective is to maximize the sum of the weights of all the arcs in a feasible solution. In the FCLOP, we are looking for a subset S ⊆ V n such that |S|= p and an LOP on these S nodes. Hence the objective is to find the best subset of the nodes and an LOP over these p nodes that maximize the sum of the weights of all the arcs in the solution. Graphically, a feasible solution of the FCLOP is a complete cycle-free digraph on S plus a set of n − p vertices that are not connected to any of the other vertices. There are several studies available in the literature focused on polyhedral aspects of the linear ordering problem as well as various exact and heuristic solution methods. The fixed cardinality linear ordering problem is presented for the first time in this PhD study, so as far as we know, there is no other study in the literature that has studied this problem. The linear ordering problem is already known as a NP-hard problem. However one sees that there exist many instances in the literature that can be solved by CPLEX in less than 10 seconds (when p = n), but once the cardinality number is limited to p (p < n), the instance is not anymore solvable due to the memory issue. We have studied the polytope corresponding to the FCLOP for different cardinality values. We have identified dimension of the polytope, proposed several classes of valid inequalities and showed that among these sets of valid inequalities, some of them are defining facets for the FCLOP polytope for different cardinality values. We have then introduced a Relax-and-Cut algorithm based on these results to solve instances of the FCLOP. To solve the instances of the problem, in the beginning, we have applied the Lagrangian relaxation algorithm. We have studied different relaxation strategies and compared the dual bound obtained from each case to detect the most suitable subproblem. Numerical results show that some of the relaxation strategies result better dual bound and some other contribute more in reducing the computational time and provide a relatively good dual bound in a shorter time. We have also implemented a Lagrangian decomposition algorithm, decom-6 posing the FCLOP model to three subproblems (instead of only two subproblems). The interest of decomposing the FCLOP model to three subproblems comes mostly from the nature of the three subproblems, which are relatively quite easier to solve compared to the initial FCLOP model. Numerical results show a significant improvement in the quality of dual bounds for several instances. We could also obtain relatively quite better dual bounds in a shorter time comparing to the other relaxation strategies. We have proposed a cutting plane algorithm based on the pure relaxation strategy. In this algorithm, we firstly relax a subset of constraints that due to the problem structure, a very few number of them are active. Then in the course of the branch-and-bound tree we verify if there exist any violated constraint among the relaxed constraints or. Then the characterized violated constraints will be globally added to the model. (...)
20
Wilgenbus, Erich Feodor. "The file fragment classification problem : a combined neural network and linear programming discriminant model approach / Erich Feodor Wilgenbus." Thesis, North-West University, 2013. http://hdl.handle.net/10394/10215.
Full textAbstract:
The increased use of digital media to store legal, as well as illegal data, has created the need
for specialized tools that can monitor, control and even recover this data. An important task
in computer forensics and security is to identify the true le type to which a computer le
or computer le fragment belongs. File type identi cation is traditionally done by means
of metadata, such as le extensions and le header and footer signatures. As a result,
traditional metadata-based le object type identi cation techniques work well in cases where
the required metadata is available and unaltered. However, traditional approaches are not
reliable when the integrity of metadata is not guaranteed or metadata is unavailable. As
an alternative, any pattern in the content of a le object can be used to determine the
associated le type. This is called content-based le object type identi cation.
Supervised learning techniques can be used to infer a le object type classi er by exploiting
some unique pattern that underlies a le type's common le structure. This study builds
on existing literature regarding the use of supervised learning techniques for content-based
le object type identi cation, and explores the combined use of multilayer perceptron neural
network classi ers and linear programming-based discriminant classi ers as a solution to the
multiple class le fragment type identi cation problem.
The purpose of this study was to investigate and compare the use of a single multilayer
perceptron neural network classi er, a single linear programming-based discriminant classi-
er and a combined ensemble of these classi ers in the eld of le type identi cation. The
ability of each individual classi er and the ensemble of these classi ers to accurately predict
the le type to which a le fragment belongs were tested empirically.
The study found that both a multilayer perceptron neural network and a linear programming-
based discriminant classi er (used in a round robin) seemed to perform well in solving
the multiple class le fragment type identi cation problem. The results of combining
multilayer perceptron neural network classi ers and linear programming-based discriminant
classi ers in an ensemble were not better than those of the single optimized classi ers.<br>MSc (Computer Science), North-West University, Potchefstroom Campus, 2013
21
IUNG, ANDERSON MITTERHOFER. "APPLICATION OF FUZZY LINEAR PROGRAMMING TO THE PROBLEM OF PLANNING UNDER UNCERTAINTY THE EXPANSIUM OF THE TRANSMITION SYSTEM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2000. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=7459@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>CENTRO DE PESQUISA DE ENERGIA ELÉTRICA<br>Esta dissertação apresenta um aplicação de programação
linear fuzzy para o problema de planejamento da expansão
de redes de transmissão de potência sob considerações de
incertezas. A partir da modelagem dos conceitos vagos e
imprecisos, inerentes ao problema de planejamento, com a
utilização da teoria da lógica fuzzy é possível incorporar
as incertezas dentro do modelo do problema. Os conceitos
de programação linear fuzzy são utilizados para
transformar tanto a função objetivo como as restrições
fuzzy em funções crisp, que podem ser tradadas por métodos
tradicionais de programação matemática. Uma aplicação
desta teoria é realizada utilizando uma versão modificada
do sistema teste de Garver , onde as incertezas em relação
a previsão de demanda futura é considerada. Os resultados
obtidos mostram a capacidade da utilização dessa
metodologia para metodologia para problemas de
planejamento sob incertezas.<br>This thesis describes an application of fuzzy linear
programming in power transmission network expansion
planning under uncertainty. The utilization of fuzzy logic
theory, considering the modeling of vagueness and
imprecision (inherent in the planning problem), makes it
possible to incorporate the uncertainty within the model.
Fuzzy linear programming is used to transform both the
objective function and constraints (Fuzzy) into crisp
functions, which can be modeled by traditional methods of
mathematical programming. An application of this approach
is built by using a modified version of the Garver test
system which also takes into account the uncertainty in
the forecasted demand. The results obtained show the
capability of this methodology in planning problems under
uncertainty.
22
Amlie-Wolf, Alexandre. "A Swarm of Salesman: Algorithmic Approaches to Multiagent Modeling." Oberlin College Honors Theses / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1368052652.
Full text
23
Aslan, Murat. "The Cardinality Constrained Multiple Knapsack Problem." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12610131/index.pdf.
Full textAbstract:
The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce.
In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.
24
Goksoy, Eda. "Disassembly Line Balancing Problem With Fixed Number Of Workstations And Finite Supply." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612060/index.pdf.
Full textAbstract:
In this thesis, we consider a Disassembly Line Balancing Problem (DLBP) with fixed number of workstations. We aim to maximize the total value of the recovered parts.
We assume that there is a limited supply for the products to be disassembled. Different components can be obtained by disassembling different units of the product. Our aim is to assign the tasks to the workstations of the disassembly line so as to maximize the total value of the recovered parts. We present several upper and one lower bounding procedure. The results of our computational study have revealed the satisfactory behavior of our bounding mechanisms.
25
Remias, Michael George. "Computational studies of some fuzzy mathematical problems." Thesis, Curtin University, 2012. http://hdl.handle.net/20.500.11937/1147.
Full textAbstract:
In modelling and optimizing real world systems and processes, one usually ends up with a linear or nonlinear programming problem, namely maximizing one or more objective functions subject to a set of constraint equations or inequalities. For many cases, the constraints do not need to be satisfied exactly, and the coefficients involved in the model are imprecise in nature and have to be described by fuzzy numbers to reflect the real world nature. The resulting mathematical programming problem is referred to as a fuzzy mathematical programming problem.Over the past decades, a great deal of work has been conducted to study fuzzy mathematical programming problems and a large volume of results have been obtained. However, many issues have not been resolved. This research is thus undertaken to study two types of fuzzy mathematical programming problems. The first type of problems is fuzzy linear programming in which the objective function contains fuzzy numbers. To solve this type of problems, we firstly introduce the concept of fuzzy max order and non-dominated optimal solution to fuzzy mathematical programming problems within the framework of fuzzy mathematics. Then, based on the new concept introduced, various theorems are developed, which involve converting the fuzzy linear programming problem to a four objective linear programming problem of non-fuzzy members. The theoretical results and methods developed are then validated and their applications for solving fuzzy linear problems are demonstrated through examples.The second type of problems which we tackle in this research is fuzzy linear programming in which the constraint equations or inequalities contain fuzzy numbers. For this work, we first introduce a new concept, the α-fuzzy max order. Based on this concept, the general framework of an α-fuzzy max order method is developed for solving fuzzy linear programming problems with fuzzy parameters in the constraints. For the special cases in which the constraints consist of inequalities containing fuzzy numbers with isosceles triangle or trapezoidal membership functions, we prove that the feasible solution space can be determined by the respective 3n or 4n non-fuzzy inequalities. For the general cases in which the constraints contain fuzzy numbers with any other form of membership functions, robust numerical algorithms have been developed for the determination of the feasible solution space and the optimal solution to the fuzzy linear programming problem in which the constraints contain fuzzy parameters. Further, by using the results for both the first and second types of problems, general algorithms have also been developed for the general fuzzy linear programming problems in which both the objective function and the constraint inequalities contain fuzzy numbers with any forms of membership functions. Some examples are then presented to validate the theoretical results and the algorithms developed, and to demonstrate their applications.
26
Lu, Zhaosong. "Algorithm Design and Analysis for Large-Scale Semidefinite Programming and Nonlinear Programming." Diss., Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/7151.
Full textAbstract:
The limiting behavior of weighted paths associated with the semidefinite program (SDP) map $X^{1/2}SX^{1/2}$ was studied and some applications to error bound analysis and superlinear convergence of a class of
primal-dual interior-point methods were provided. A new approach for solving large-scale well-structured sparse SDPs via a saddle point mirror-prox algorithm with ${cal O}(epsilon^{-1})$ efficiency was developed based on exploiting sparsity structure and reformulating SDPs into smooth convex-concave saddle point problems. An iterative solver-based
long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) was developed. The search directions of
this algorithm were computed by means of a preconditioned iterative linear solver. A uniform bound, depending only on the CQP data, on
the number of iterations performed by a preconditioned iterative linear solver was established. A polynomial bound on the number of
iterations of this algorithm was also obtained. One efficient ``nearly exact' type of method for solving large-scale ``low-rank' trust region
subproblems was proposed by completely avoiding the computations of Cholesky or partial Cholesky factorizations. A computational study of this method was also provided by applying it to solve some large-scale nonlinear programming problems.
27
FalcÃo, Viviane Adriano. "Modelo de roteirizaÃÃo para a terraplenagem em obras rodoviÃrias aplicando programaÃÃo linear inteira." Universidade Federal do CearÃ, 2016. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=16588.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior<br>Planejar as atividades de distribuiÃÃo de materiais em obras de terraplenagem pode representar um ganho na obra como um todo. Alguns estudos afirmam que, para obter uma economia geral na construÃÃo, os planejadores devem desenvolver uma estratÃgia de forma a otimizar a utilizaÃÃo dos recursos. Uma das formas de fazer isso à minimizar a distÃncia total percorrida pelos veÃculos na movimentaÃÃo de terra entre as zonas de corte e aterro. Hà muitos estudos e trabalhos que focam a otimizaÃÃo da distribuiÃÃo de materiais entre zonas de corte e aterro, porÃm poucos aplicaram em projetos reais com a consideraÃÃo de mÃltiplos equipamentos, alÃm de nÃo terem feito uma anÃlise baseada na distÃncia entre estacas. Este trabalho teve como objetivo desenvolver um modelo de ProgramaÃÃo MatemÃtica que minimize a distÃncia percorrida pelos caminhÃes basculantes em atividades de distribuiÃÃo de materiais na terraplenagem. O modelo elaborado com princÃpios da ProgramaÃÃo Linear Inteira foi baseado no problema de roteamento, cujo objetivo à minimizar o caminho percorrido. O modelo foi aplicado em um estudo de caso utilizando o projeto da obra rodoviÃria PE099, onde se obteve a alocaÃÃo de corte e aterro Ãtima, de forma a minimizar a distÃncia percorrida pelos caminhÃes. Ao comparar o resultado obtido pelo modelo e o resultado fornecido pelo diagrama de massas obtÃm-se uma economia de 40% no momento de transporte e, por conseguinte, na distÃncia mÃdia de transporte percorrida. O modelo proposto considerou algumas lacunas da literatura, entre elas o fato de considerar o problema de roteamento com mÃltiplos veÃculos, aplicado em um projeto real. Utilizando esse modelo, engenheiros, planejadores e analistas tem uma importante ferramenta computacional que facilitarà a tomada de decisÃo.
28
Karabulut, Ozlem. "Multi Resource Agent Bottleneck Generalized Assignment Problem." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/3/12611790/index.pdf.
Full textAbstract:
In this thesis, we consider the Multi Resource Agent Bottleneck Generalized Assignment Problem. We aim to minimize the maximum load over all agents.
We study the Linear Programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our Branch and Bound algorithm while defining lower and upper bounds and branching schemes. We find that our Branch and Bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes.
To find approximate solutions, we define a tabu search algorithm and an &<br>#945<br>approximation algorithm. Our computational results have revealed that these procedures can find high quality solutions to large sized instances very quickly.
29
Arantes, Márcio da Silva. "Hybrid qualitative state plan problem and mission planning with UAVs." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05122017-083420/.
Full textAbstract:
This paper aims to present the thesis developed in the Doctoral Programin Computer Science and Computational Mathematics of the ICMC/USP. The thesis theme seeks to advance the state of the art by solving the problems of scalability and representation present in mission planning algorithms for Unmanned Aerial Vehicle (UAV). Techniques based on mathematical programming and evolutionary computation are proposed. Articles have been published, submitted or they are in final stages of preparation.These studies report the most significant advances in the representation and scalability of this problem. Mission planners worked on the thesis deal with stochastic problems in non-convex environments,where collision risks or failures in mission planning are treated and limited to a tolerated value. The advances in the representation allowed to solve violations in the risks present in the original literature modeling, besides making the models more realistic when incorporating aspects such as effects of the air resistance. Efficient mathematical modeling techniques allowed to advance from a Mixed Integer Nonlinear Programming (MINLP) model, originally proposed in the literature, to a Mixed Integer Linear Programming (MILP) problem. Modeling as a MILP led to problem solving more efficiently through the branch-and-algorithm. The proposed new representations resulted in improvements from scalability, solving more complex problems within a shorter computational time. In addition, advances in scalability are even more effective when techniques combining mathematical programming and metaheuristics have been applied to the problem.<br>O presente documento tem por objetivo apresentar a tese desenvolvida no Programade Doutorado em Ciência da Computação e Matemática Computacional do ICMC/USP. O tema da tese busca avançar o estado da arte ao resolver os problemas de escalabilidade e representação presentes em algoritmos de planejamento para missões com Veículos Aéreos Não Tripulados (VANTs). Técnicas baseadas em programação matemática e computação evolutiva são propostas. Artigos foram publicados, submetidos ou se encontram em fase final de elaboração. Esses trabalhos reportamos avanços mais significativos obtidos na representação e escalabilidade deste problema.Os planejadores de missão trabalhados na tese lidam com problemas estocásticos em ambientes não convexos, onde os riscos de colisão ou falhas no planejamento da missão são tratados e limitados a um valor tolerado. Os avanços na representação permitiram solucionar violações nos riscos presentes na modelagem original, além de tornar os modelos mais realistas ao incorporar aspectos como efeitos da resistência do ar. Para isso, técnicas eficientes de modelagem matemática permitiram avançar de um modelo de Programação Não-Linear Inteira Mista(PNLIM), originalmente proposto na literatura, para um problema de Programação Linear Inteira Mista (PLIM). A modelagem como um PLIM levou à resolução do problema de forma mais eficiente através do algoritmo branch-and-cut. As novas representações propostas resultaram em melhorias na escalabilidade, solucionando problemas mais complexos em um tempo computacional menor.Além disso,os avanços em escalabilidade mostraram-se mais efetivos quando técnicas combinando programação matemática e metaheurísticas foram aplicadas ao problema.
30
Alvianto, Priyanto Criss. "Shift Design and Driver Scheduling Problem." Thesis, KTH, Optimeringslära och systemteori, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-227263.
Full textAbstract:
Scheduling problem and shift design problems are well known NP-hard problems within the optimization area. Often time, the two problems are studied individually. In this thesis however, we are looking at the combination of both problems. More specifically, the aim of this thesis is to suggest an optimal scheduling policy given that there are no predefined shifts to begin with. The duration of a shift, along with the start and end time may vary. Thus we have proposed to split the problem into two sub-problems: weekly scheduling problem and daily scheduling problem. As there are no exact solution methods that are feasible, two meta-heuristics method has been employed to solve the sub-problems: Simulated Annealing (SA) and Genetic Algorithm (GA). We have provided proofs of concepts for both methods as well as explored the scalability. This is especially important as the number of employee is expected to grow significantly throughout the year. The results obtained has shown to be promising and can be built upon for further capabilities.<br>Schemaläggning och skiftdesignsproblem är välkända och välstuderade NP-svåra beslutsproblem inom optimeringsområdet. Oftast så studeras dessa problem enskilt, men i detta arbete så studeras en kombination av båda problemen. Mer specifikt är målet med detta arbete att föreslå ett förnuftigt handlingsätt till att skapa ett veckoschema där skift inte är predefinierade för alla veckor. Starttiden, sluttiden och varaktigheten av ett skift kan förändras från vecka till vecka. Därför har problemet delats upp till två delar: Veckoschemaläggnings- och dagsschemaläggningsproblem. Trots uppdelningen så är båda delproblem för komplexa för att lösas exakt. Därför har två metaheuristiska metoder använts som lösningsmetoder: Simulerad Glödgning och Genetisk Algoritm. I detta arbete bevisas båda lösningsmetoderna till att vara bra nog, och dessutom studeras även skalbarheten av modellen. Detta senare är särskilt viktigt eftersom antal anställda som ska schemaläggas förväntas att öka genomåren. De erhållna resultaten har visat sig vara lovande och bevisligen så kan modellen expanderas med er villkor
31
Šádová, Eva. "Optimalizace ideální stravy." Master's thesis, Vysoká škola ekonomická v Praze, 2007. http://www.nusl.cz/ntk/nusl-12418.
Full textAbstract:
The thesis describes a way of searching the best bill of fare for certain patient in hospital. The target is to set up and then to solve an optimization model. Criterion of performance is to minimize spending on selected foodstuff. The first part describes a theory of optimization models, the second is about nutrition and the third aims to solve a model and to interpret the results.
32
Ribas, Cibele Cristina Gomes Barboza. "Programação linear: abordagem para ensino médio." Universidade Tecnológica Federal do Paraná, 2014. http://repositorio.utfpr.edu.br/jspui/handle/1/968.
Full textAbstract:
CAPES<br>Este trabalho apresenta uma proposta ao professor de Ensino Médio que permite uma conexão entre os temas de Discussão de Sistemas Lineares e Programação Linear, sugerindo que o professor leve o aluno a pensar sobre as soluções de problemas e, principalmente, em não somente aceita-las, mas buscar novas e melhores.<br>This work presents a proposal to the teacher of secondary education that allows a connection between the topics of discussion Linear Systems and Linear Programming, suggesting that the teacher take the student to think about solutions to problems, and especially in not only accepts them but seek new and better.
33
Alexandre, Joana Fonseca. "Dimensionamento e escalonamento de pessoal em Call Centre." Master's thesis, Instituto Superior de Economia e Gestão, 2019. http://hdl.handle.net/10400.5/19832.
Full textAbstract:
Mestrado em Métodos Quantitativos para a Decisão Económica e Empresarial<br>Os problemas de escalonamento de pessoal têm sido abundantemente abordados ao longo do tempo, devido ao peso elevado dos custos com pessoal na estrutura de uma organização.
O projeto em desenvolvimento assenta na resolução de um problema de escalonamento com aplicação num call centre na área da saúde e visa a minimização dos custos incorridos e a consideração das preferências dos colaboradores em termos de dias e turnos de trabalho. O problema consiste na alocação dos seus colaboradores aos turnos existentes, de forma a cobrir a procura (volume de chamadas recebidas), respeitando as normas de funcionamento da organização e a legislação laboral.
Na resolução do problema, adaptaram-se dois modelos: um modelo de staffing e um de rostering. O primeiro pretende determinar o número de colaboradores necessários por turno e dia da semana de acordo com a variabilidade da procura. As soluções deste modelo representam os inputs para o segundo, onde se distribuem os colaboradores pelos diferentes turnos e dias de trabalho. Ambos são formalizados em programação linear inteira e resolvidos através de métodos exatos, com recurso ao OpenSolver. Os modelos são escritos por meio de macros em VBA.
Os modelos foram testados através de instâncias de pequenas dimensões, com diferentes níveis de procura, número e distribuição de turnos. Perante os resultados obtidos foi possível concluir que a distribuição dos enfermeiros pelos turnos varia consoante o número de turnos diários e o nível de procura considerado, dependendo também do número mínimo de enfermeiros a respeitar em cada turno de trabalho.<br>Staff scheduling problems have been abundantly addressed over time, from diverse perspectives. This can be justified by the high weight of personnel costs in the structure of an organization.
The project under development is based on the resolution of a scheduling problem applied to a call center, aiming both to minimize the costs incurred and to consider the preferences of employees in terms of days and shifts. The problem aims to allocate employees to existing shifts in way to cover demand, i.e. the volume of calls received, respecting the organization's operating norms and labor legislation.
In the problem solving, two models were adapted: a staffing model and a rostering model. The first one determines the number of employees required per shift and day of the week according to demand variability. The solutions of this model represent the inputs to the second, where the employees are distributed through different shifts and working days. Both are formalized in integer linear programming and solved through exact methods, using OpenSolver/Excel. The templates are generated by means of macros written in VBA.
The models were tested using small instances with different levels of demand, number and distribution of shifts. From the results obtained it was possible to conclude that the distribution of nurses by work shifts varies with the number of existing daily shifts and the level of demand considered and depends on the minimum number of nurses to be respected in each hour and work shift.<br>info:eu-repo/semantics/publishedVersion
34
Pereira, Dilson Lucas. "Formulações e algoritmos baseados em programação linear inteira para o problema quadrático da árvore geradora mínima = Formulations and algorithms based on linear integer programming for the quadratic minimum spanning tree problem." Universidade Federal de Minas Gerais, 2014. http://hdl.handle.net/1843/ESBF-9KHJA4.
Full textAbstract:
This work adresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery,where routes must be devised to fulfil the pickup and delivery requests of a setof customers. Each customer must be served by only one route, the load it receives isbrought from a central depot, to where the picked-up load is also taken. The capacityof the used vehicles must not be violated at any point of the routes. Heuristics and anexact algorithm are proposed to solve the problem. Initially, we devise some heuristicsbased on ideas of many metaheuristics, specially ILS, GRASP, and VND. Theseheuristics are tested in many instances and are compared to the best results of theliterature, obtaining results comparable to the best existing algorithms. Afterwards, aBranch-and-price method is developed, and in this context, we propose new strategiesto the resolution of the subproblem, an Elementary Resource Constrained ShortestPath Problem. Based on computational experiments, these strategies show considerablereduction on the computational time of the Column Generation resolution. Wepresent a strategy in which lower bounds obtained from the column generation are usedin the branching process. The Branch-and-price algorithm is tested and compared toa Branch-and-cut-and-price algorithm from the literature.<br>Este trabalho trata do Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas, onde devem ser desenvolvidas rotas para atender as demandas de coleta e entrega de um conjunto de consumidores. O problema é abordado de maneira heurística e exata. Inicialmente, são desenvolvidas algumas heurísticas híbridas baseadas em idéias de diversas metaheurísticas. Essas heurísticas são testadas em diversas instâncias e comparadas aos melhores resultados da literatura. Após isso, é desenvolvido um método exato Branch-and-price, nesse contexto, são propostas novas estratégias para a resolução do subproblema, um Problema de Caminho Elementar Mínimo com Restrição de Recursos. É apresentada também uma estratégia em que limites inferiores obtidos a partir da resolução do subproblema são utilizados no processo de decisão do branching. O algoritmo Branch-and-price é testado e comparado a um algoritmo Branch-and-cut-and-price da literatura.
35
Qiu, Feng. "Probabilistic covering problems." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47567.
Full textAbstract:
This dissertation studies optimization problems that involve probabilistic covering constraints. A probabilistic constraint evaluates and requires that the probability that a set of constraints involving random coefficients with known distributions hold satisfy a minimum requirement. A covering constraint involves a linear inequality on non-negative variables with a greater or equal to sign and non-negative coefficients. A variety of applications, such as set cover problems, node/edge cover problems, crew scheduling, production planning, facility location, and machine learning, in uncertain settings involve probabilistic covering constraints.
In the first part of this dissertation we consider probabilistic covering linear programs. Using the sampling average approximation (SAA) framework, a probabilistic covering linear program can be approximated by a covering k-violation linear program (CKVLP), a deterministic covering linear program in which at most k constraints are allowed to be violated. We show that CKVLP is strongly NP-hard. Then, to improve the performance of standard mixed-integer programming (MIP) based schemes for CKVLP, we (i) introduce and analyze a coefficient strengthening scheme, (ii) adapt and analyze an existing cutting plane technique, and (iii) present a branching technique. Through computational experiments, we empirically verify that these techniques are significantly effective in improving solution times over the CPLEX MIP solver. In particular, we observe that the proposed schemes can cut down solution times from as much as six days to under four hours in some instances. We also developed valid inequalities arising from two subsets of the constraints in the original formulation. When incorporating them with a modified coefficient strengthening procedure, we are able to solve a difficult probabilistic portfolio optimization instance listed in MIPLIB 2010, which cannot be solved by existing approaches.
In the second part of this dissertation we study a class of probabilistic 0-1 covering problems, namely probabilistic k-cover problems. A probabilistic k-cover problem is a stochastic version of a set k-cover problem, which is to seek a collection of subsets with a minimal cost whose union covers each element in the set at least k times. In a stochastic setting, the coefficients of the covering constraints are modeled as Bernoulli random variables, and the probabilistic constraint imposes a minimal requirement on the probability of k-coverage. To account for absence of full distributional information, we define a general ambiguous k-cover set, which is ``distributionally-robust." Using a classical linear program (called the Boolean LP) to compute the probability of events, we develop an exact deterministic reformulation to this ambiguous k-cover problem. However, since the boolean model consists of exponential number of auxiliary variables, and hence not useful in practice, we use two linear program based bounds on the probability that at least k events occur, which can be obtained by aggregating the variables and constraints of the Boolean model, to develop tractable deterministic approximations to the ambiguous k-cover set. We derive new valid inequalities that can be used to strengthen the linear programming based lower bounds. Numerical results show that these new inequalities significantly improve the probability bounds. To use standard MIP solvers, we linearize the multi-linear terms in the approximations and develop mixed-integer linear programming formulations. We conduct computational experiments to demonstrate the quality of the deterministic reformulations in terms of cost effectiveness and solution robustness. To demonstrate the usefulness of the modeling technique developed for probabilistic k-cover problems, we formulate a number of problems that have up till now only been studied under data independence assumption and we also introduce a new applications that can be modeled using the probabilistic k-cover model.
36
Souza, Estefano Alves de. "O problema de Monge-Kantorovich para duas medidas de probabilidade sobre um conjunto finito." Universidade de São Paulo, 2009. http://www.teses.usp.br/teses/disponiveis/45/45133/tde-04052009-162654/.
Full textAbstract:
Apresentamos o problema do transporte ótimo de Monge-Kantorovich com duas medidas de probabilidade conhecidas e que possuem suporte em um conjunto de cardinalidade finita. O objetivo é determinar condições que permitam construir um acoplamento destas medidas que minimiza o valor esperado de uma função de custo conhecida e que assume valor nulo apenas nos elementos da diagonal. Apresentamos também um resultado relacionado com a solução do problema de Monge-Kantorovich em espaços produto finitos quando conhecemos soluções para o problema nos espaços marginais.<br>We present the Monge-Kantorovich optimal problem with two known probability measures on a finite set. The objective is to obtain conditions that allow us to build a coupling of these measures that minimizes the expected value of a cost function that is known and is zero only on the diagonal elements. We also present a result that is related with the solution of the Monge-Kantorovich problem in finite product spaces in the case that solutions to the problem in the marginal spaces are known.
37
Hatami, Sara. "The Distributed and Assembly Scheduling Problem." Doctoral thesis, Universitat Politècnica de València, 2016. http://hdl.handle.net/10251/64072.
Full textAbstract:
[EN] Nowadays, manufacturing systems meet different new global challenges and
the existence of a collaborative manufacturing environment is essential to face
with. Distributed manufacturing and assembly systems are two manufacturing
systems which allow industries to deal with some of these challenges. This
thesis studies a production problem in which both distributed manufacturing
and assembly systems are considered. Although distributed manufacturing
systems and assembly systems are well-known problems and have been extensively
studied in the literature, to the best of our knowledge, considering
these two systems together as in this thesis is the first effort in the literature.
Due to the importance of scheduling optimization on production performance,
some different ways to optimize the scheduling of the considered problem are
discussed in this thesis.
The studied scheduling setting consists of two stages: A production and an
assembly stage. Various production centers make the first stage. Each of these
centers consists of several machines which are dedicated to manufacture jobs.
A single assembly machine is considered for the second stage. The produced
jobs are assembled on the assembly machine to form final products through a
defined assembly program.
In this thesis, two different problems regarding two different production
configurations for the production centers of the first stage are considered.
The first configuration is a flowshop that results in what we refer to as the
Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP).
The second problem is referred to as the Distributed Parallel Machine and
Assembly Scheduling Problem (DPMASP), where unrelated parallel machines
configure the production centers. Makespan minimization of the product on the
assembly machine located in the assembly stage is considered as the objective
function for all considered problems.
In this thesis some extensions are considered for the studied problems
so as to bring them as close as possible to the reality of production shops.
In the DAPFSP, sequence dependent setup times are added for machines in
both production and assembly stages. Similarly, in the DPMASP, due to
technological constraints, some defined jobs can be processed only in certain
factories.
Mathematical models are presented as an exact solution for some of the
presented problems and two state-of-art solvers, CPLEX and GUROBI are
used to solve them. Since these solvers are not able to solve large sized
problems, we design and develop heuristic methods to solve the problems. In
addition to heuristics, some metaheuristics are also designed and proposed to
improve the solutions obtained by heuristics. Finally, for each proposed problem,
the performance of the proposed solution methods is compared through
extensive computational and comprehensive ANOVA statistical analysis.<br>[ES] Los sistemas de producción se enfrentan a retos globales en los que el concepto
de fabricación colaborativa es crucial para poder tener éxito en el entorno
cambiante y complejo en el que nos encontramos. Una característica de los sistemas
productivos que puede ayudar a lograr este objetivo consiste en disponer
de una red de fabricación distribuida en la que los productos se fabriquen en
localizaciones diferentes y se vayan ensamblando para obtener el producto
final. En estos casos, disponer de modelos y herramientas para mejorar el
rendimiento de sistemas de producción distribuidos con ensamblajes es una
manera de asegurar la eficiencia de los mismos.
En esta tesis doctoral se estudian los sistemas de fabricación distribuidos
con operaciones de ensamblaje. Los sistemas distribuidos y los sistemas con
operaciones de ensamblaje han sido estudiados por separado en la literatura.
De hecho, no se han encontrado estudios de sistemas con ambas características
consideradas de forma conjunta.
Dada la complejidad de considerar conjuntamente ambos tipos de sistemas
a la hora de realizar la programación de la producción en los mismos, se ha
abordado su estudio considerando un modelo bietápico en la que en la primera
etapa se consideran las operaciones de producción y en la segunda se plantean
las operaciones de ensamblaje.
Dependiendo de la configuración de la primera etapa se han estudiado dos
variantes. En la primera variante se asume que la etapa de producción está
compuesta por sendos sistemas tipo flowshop en los que se fabrican los componentes
que se ensamblan en la segunda etapa (Distributed Assembly Permutation
Flowshop Scheduling Problem o DAPFSP). En la segunda variante
se considera un sistema de máquinas en paralelo no relacionadas (Distributed
Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambas
variantes se optimiza la fecha de finalización del último trabajo secuenciado
(Cmax) y se contempla la posibilidad que existan tiempos de cambio (setup)
dependientes de la secuencia de trabajos fabricada. También, en el caso
DPMASP se estudia la posibilidad de prohibir o no el uso de determinadas
máquinas de la etapa de producción.
Se han desarrollado modelos matemáticos para resolver algunas de las
variantes anteriores. Estos modelos se han resuelto mediante los programas
CPLEX y GUROBI en aquellos casos que ha sido posible. Para las instancias
en los que el modelo matemático no ofrecía una solución al problema se han
desarrollado heurísticas y metaheurísticas para ello.
Todos los procedimientos anteriores han sido estudiados para determinar
el rendimiento de los diferentes algoritmos planteados. Para ello se ha realizado
un exhaustivo estudio computacional en el que se han aplicado técnicas
ANOVA.
Los resultados obtenidos en la tesis permiten avanzar en la comprensión
del comportamiento de los sistemas productivos distribuidos con ensamblajes,
definiendo algoritmos que permiten obtener buenas soluciones a este tipo de
problemas tan complejos que aparecen tantas veces en la realidad industrial.<br>[CAT] Els sistemes de producció s'enfronten a reptes globals en què el concepte de
fabricació col.laborativa és crucial per a poder tindre èxit en l'entorn canviant
i complex en què ens trobem. Una característica dels sistemes productius
que pot ajudar a aconseguir este objectiu consistix a disposar d'una xarxa de
fabricació distribuïda en la que els productes es fabriquen en localitzacions
diferents i es vagen acoblant per a obtindre el producte final. En estos casos,
disposar de models i ferramentes per a millorar el rendiment de sistemes de
producció distribuïts amb acoblaments és una manera d'assegurar l'eficiència
dels mateixos.
En esta tesi doctoral s'estudien els sistemes de fabricació distribuïts amb
operacions d'acoblament. Els sistemes distribuïts i els sistemes amb operacions
d'acoblament han sigut estudiats per separat en la literatura però, en allò
que es coneix, no s'han trobat estudis de sistemes amb ambdós característiques
conjuntament. Donada la complexitat de considerar conjuntament ambdós
tipus de sistemes a l'hora de realitzar la programació de la producció en els
mateixos, s'ha abordat el seu estudi considerant un model bietàpic en la que
en la primera etapa es consideren les operacions de producció i en la segona es
plantegen les operacions d'acoblament.
Depenent de la configuració de la primera etapa s'han estudiat dos variants.
En la primera variant s'assumix que l'etapa de producció està composta per
sengles sistemes tipus flowshop en els que es fabriquen els components que
s'acoblen en la segona etapa (Distributed Assembly Permutation Flowshop
Scheduling Problem o DAPFSP). En la segona variant es considera un sistema
de màquines en paral.lel no relacionades (Distributed Parallel Machine and
Assembly Scheduling Problem o DPMASP). En ambdós variants s'optimitza
la data de finalització de l'últim treball seqüenciat (Cmax) i es contempla la
possibilitat que existisquen temps de canvi (setup) dependents de la seqüència
de treballs fabricada. També, en el cas DPMASP s'estudia la possibilitat de
prohibir o no l'ús de determinades màquines de l'etapa de producció.
S'han desenvolupat models matemàtics per a resoldre algunes de les variants
anteriors. Estos models s'han resolt per mitjà dels programes CPLEX
i GUROBI en aquells casos que ha sigut possible. Per a les instàncies en
què el model matemàtic no oferia una solució al problema s'han desenrotllat
heurístiques i metaheurísticas per a això. Tots els procediments anteriors han
sigut estudiats per a determinar el rendiment dels diferents algoritmes plantejats.
Per a això s'ha realitzat un exhaustiu estudi computacional en què s'han
aplicat tècniques ANOVA.
Els resultats obtinguts en la tesi permeten avançar en la comprensió del
comportament dels sistemes productius distribuïts amb acoblaments, definint
algoritmes que permeten obtindre bones solucions a este tipus de problemes
tan complexos que apareixen tantes vegades en la realitat industrial.<br>Hatami, S. (2016). The Distributed and Assembly Scheduling Problem [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64072<br>TESIS
38
Freiwat, Sami, and Lukas Öhlund. "Fuel-Efficient Platooning Using Road Grade Preview Information." Thesis, Uppsala universitet, Avdelningen för systemteknik, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-270263.
Full textAbstract:
Platooning is an interesting area which involve the possibility of decreasing the fuel consumption of heavy-duty vehicles. By reducing the inter-vehicle spacing in the platoon we can reduce air drag, which in turn reduces fuel consumption. Two fuel-efficient model predictive controllers for HDVs in a platoon has been formulated in this master thesis, both utilizing road grade preview information. The first controller is based on linear programming (LP) algorithms and the second on quadratic programming (QP). These two platooning controllers are compared with each other and with generic controllers from Scania. The LP controller proved to be more fuel-efficient than the QP controller, the Scania controllers are however more fuel-efficient than the LP controller.
39
Santiago, Claudio Prata. "On the nonnegative least squares." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31768.
Full textAbstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010.<br>Committee Chair: Earl Barnes; Committee Member: Arkadi Nemirovski; Committee Member: Faiz Al-Khayyal; Committee Member: Guillermo H. Goldsztein; Committee Member: Joel Sokol. Part of the SMARTech Electronic Thesis and Dissertation Collection.
40
Janiczková, Lucie. "Optimální rozmístění státem poskytovaných auditních služeb v rámci Moravskoslezského kraje." Master's thesis, Vysoká škola ekonomická v Praze, 2016. http://www.nusl.cz/ntk/nusl-205579.
Full textAbstract:
Municipalities in the Czech Republic deal with their budget, which among others consists of granted subsidies from the region, State, European Union or other organizations. Nowadays the budget transactions are not being under the control. In the future, it is appropriate to introduce some external view to control their spending. Establishment of an audit service for each municipality would be financially inevitable. Therefore it is suggested to provide the State audit services only in some municipalities and to share them with more municipalities within one region. Deployment of the audit centers and assigning municipalities lead to solving a linear problem which falls under the covering problem class. The establishment of audit centers is only illustrative, the employment of more shared state services could follow a similar principle.
41
Grey, Audley Bruce. "Unified solution of security-constrained unit commitment (SCUC) problem using a linear programming methodology : a dissertation presented to the faculty of the Graduate School, Tennessee Technological University /." Click to access online version, 2007. http://proquest.umi.com/pqdweb?index=88&did=1397913351&SrchMode=1&sid=1&Fmt=6&VInst=PROD&VType=PQD&RQT=309&VName=PQD&TS=1255446163&clientId=28564.
Full text
42
Khorbatly, Mohamad. "Optimisation numérique appliquée à la gestion de crise : Approche basée sur un algorithme hybride pour la résolution du problème intégré d'ordonnancement et d'allocation des ressources." Thesis, Normandie, 2018. http://www.theses.fr/2018NORMLH18/document.
Full textAbstract:
Les travaux présentes dans cette thèse s'inscrivent dans le cadre des méthodes d'évacuation des populations. Ils visent à étudier les capacités et modéliser le problème d'évacuation (blessés, sinistrés, enfants, personnes agées, etc.) dans une situation de crise (attentats terroristes, catastrophes naturelles, etc.) et développer des méthodes d'aide à la décision tout en proposant une meilleure planification et des plans optimaux d'évacuation des populations de la zone de crise vers les centres hospitaliers.Notre travail consiste à résoudre le problème d'évacuation de blessés dans des zones de crise avec une nouvelle vision qui consiste à optimiser le temps de transport et par conséquent sauver le maximum des personnes touchées par cette crise d'une façon dynamique, efficace et rapide pour minimiser la perte humaine<br>The work presented in this thesis is part of human evacuation methods. It aims to study the capacities, model the evacuation problem (wounded, victims, children, elderly, etc.) in a crisis situation (terrorist attacks, natural disasters, etc.) and to develops methods for decision making while proposing better planning and optimal evacuation plans for populations from the crisis zone to hospitals.Our job is to solve the wounded evacuation problem in crisis zone with a new vision that optimizes the transport time and thus saving the maximum of causalities in a dynamic, efficient and fast way in order to minimize human loss
43
Cabalka, Matouš. "Pokročilá optimalizace toků v sítích." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2018. http://www.nusl.cz/ntk/nusl-392835.
Full textAbstract:
The master’s thesis focuses on the optimization models in logistics with emphasis on the network interdiction problem. The brief introduction is followed by two overview chapters - graph theory and mathematical programming. Important definitions strongly related to network interdiction problems are introduced in the chapter named Basic concepts of graph theory. Necessary theorems used for solving problems are following the definitions. Next chapter named Introduction to mathematical programming firstly contains concepts from linear programming. Definitions and theorems are chosen with respect to the following maximum flow problem and the derived dual problem. Concepts of stochastic optimization follow. In the fifth chapter, we discuss deterministic models of the network interdiction. Stochastic models of the network interdiction follow in the next chapter. All models are implemented in programmes written in the programming language GAMS, the codes are attached.
44
Rychtář, Adam. "Transformace optimalizačních modelů s aplikacemi." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2016. http://www.nusl.cz/ntk/nusl-254409.
Full textAbstract:
The thesis deals with recent problems of waste management in the Czech Republic. In connection with the existing software implementation, the author focuses on the gradual development of advanced mathematical programming models, which generalize existing approaches. The author applies acquired knowledge in the areas of network flows, linear, integer, and stochastic programming. The important role is played by modifications and transformations of the discussed models. They are further used to obtain the experimental results for real-world input data by implementation in GAMS.
45
Steffan, Philippe. "An optimization model: minimizing flour millers’ costs of production by blending wheat and additives." Thesis, Kansas State University, 2012. http://hdl.handle.net/2097/14975.
Full textAbstract:
Master of Agribusiness<br>Department of Agricultural Economics<br>Jason Bergtold<br>ABSTRACT
Grands Moulins d'Abidjan (GMA) is a flour milling company operating in Côte d'Ivoire. It wishes to determine the optimal blend of wheat and additives that minimizes its costs of production while meeting its quality specifications. Currently, the chief miller selects the mix of ingredients. The management of the company would like to dispose of a scientific tool that challenges the decisions of the chief miller.
The thesis is about building and testing this tool, an optimization model.
GMA blends up to six ingredients into flour: soft wheat, hard wheat, gluten, ascorbic acid and two types of enzyme mixes. Quality specifications are summarized into four flour characteristics: protein content, falling number, Alveograph W and specific volume of a baguette after four hours of fermentation. GMA blending problem is transformed into a set of equations. The relationships between ingredients and quality parameters are determined with reference to grains science and with the help of linear regression.
The optimization model is implemented in Microsoft Office Excel 2010, in two versions. In the first one (LP for Linear Programming model), it is assumed that weights of additives can take any value. In the second one (ILP for Integer Linear Programming model), some technical constraints restrain the set of values that weights of additives can take.
The two models are tested with Premium Solver V11.5 from Frontline Systems Inc., against four situations that actually occurred at GMA in 2011 and 2012,.
The solutions provided by the model are sensible. They challenge the ones that were actually implemented. They may have helped GMA save money.
The optimization model can nevertheless be improved. The choice of relevant quality parameters can be questioned. Equations that link ingredients and quality parameters, and particularly those determined with the help of linear regression, should be further researched. The optimization model should also take into account some hidden constraints such as logistics that actually influence the decision of GMA chief miller. Finally, sensitivity analyses may also be used to provide alternative solutions.
46
TAVERNA, ANDREA. "ALGORITHMS FOR THE LARGE-SCALE UNIT COMMITMENT PROBLEM IN THE SIMULATION OF POWER SYSTEMS." Doctoral thesis, Università degli Studi di Milano, 2017. http://hdl.handle.net/2434/487071.
Full textAbstract:
Lo Unit Commitment Problem (UCP) è un problema di programmazione matematica dove un insieme di impianti termoelettrici deve essere programmato per soddisfare la domanda di energia e altri vincoli di sistema. Il modello è impiegato da decenni per supportare la pianificazione operazionale di breve termine dei sistemi elettrici.
In questo lavoro affrontiamo il problema di risolvere UCP lineari di larga-scala per realizzare simulazioni accurate di sistemi elettrici, con i requisiti aggiuntivi di impiegare capacità di calcolo convenzionali, ad esempio i personal computers, ed un tempo di soluzione di poche ore. Il problema, sotto le medesime condizioni, è affrontato abitualmente dal nostro partner industriale RSE S.p.A. (Ricerche Sistema Energetico), uno dei principali centri ricerche industriali su sistemi energetici in Italia.
L’ottimizzazione diretta di queste formulazioni con solutori generici è impraticabile. Nonostante sia possibile calcolare buone soluzioni euristiche, ovvero con un gap di ottimalità sotto il 10%, in tempi ragionevoli per UCP di larga scala, si richiedono soluzioni più accurate, per esempio con gap sotto l’1%, per migliorare l’affidabilità delle simulazioni ed aiutare gli esperti di dominio, che potrebbero non essere familiari con i dettagli dei metodi di programmazione matematica, a supportare meglio le loro analisi.
Tra le idee che abbiamo esplorato i seguenti metodi risultano i più promettenti: una mateuristica per calcolare efficientemente buone soluzioni e due metodi esatti di bounding: column generation e Benders decomposition. Questi metodi decompongono il problema disaccoppiando il commitment degli impianti termoelettrici, rappresentati da variabili discrete, e il loro livello di produzione, rappresentato da variabili continue.
I nostri esperimenti dimostrano che il modello possiede proprietà intrinseche come degenerazione e forma della funzione obbiettivo piatta che ostacolano o impediscono la convergenza in risolutori allo stato dell’arte. Tuttavia, i metodi che abbiamo sviluppato, sfruttando efficacemente le proprietà strutturali del modello, permettono di raggiungere soluzioni quasi ottime in poche iterazioni per la maggior parte delle istanze.<br>The Unit Commitment Problem (UCP) is a mathematical programming problem where a set of power plants needs to be scheduled to satisfy energy demand and other system-wide constraints. It has been employed for decades to support short-term operational planning of power plants.
In this work we tackle the problem of solving large-scale linear UCPs to perform accurate medium-term power systems simulations, with the additional requirements of employing conventional computing power, such as personal computers, and a solution time of a few hours. The problem, under such conditions, is routinely faced by our industry partner, the Energy Systems Development department at RSE S.p.A. (Ricerche Sistema Energetico), a major industrial research centre on power systems in Italy.
The direct optimization of these formulations via general-purpose solvers is impractical. While good heuristic solutions, that is with an optimality gap below 10%, can be found for large-scale UCPs in affordable time, more accurate solutions, for example with a gap below 1%, are sought to improve the reliability of the simulations and help domain experts, who may not be familiar with the details of mathematical programming methods, to better support their analysis.
Among the ideas we explored, the following methods are the most promising: a matheuristic to efficiently compute good solutions and two exact bounding methods: column generation and Benders decomposition. These methods decompose the problem by decoupling the commitment of thermal plants, represented by discrete variables, and their level of production, represented by continuous variables.
Our experiments proved that the model posses inherent properties as degeneracy and objective flatness which hinder or prevent convergence in state-of-the-art solvers. On the other hand, the methods we devised, by effectively exploiting structural properties of the model, allow to reach quasi-optimal solutions within a few iterations on most instances.
47
Froger, Aurélien. "Maintenance scheduling in the electricity industry : a particular focus on a problem rising in the onshore wind industry." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0011/document.
Full textAbstract:
L’optimisation de la planification de la maintenance des équipements de production d’électricité est une question importante pour éviter des temps d’arrêt inutiles et des coûts opérationnels excessifs. Dans cette thèse, nous présentons une classification multidimensionnelle des études de Recherche Opérationnelle portant sur ce sujet. Le secteur des énergies renouvelables étant en pleine expansion, nous présentons et discutons ensuite d’un problème de maintenance de parcs éoliens terrestres. Le problème est traité sur un horizon à court terme et l’objectif est de construire un planning de maintenance qui maximise le revenu lié à production d’électricité des éoliennes tout en prenant en compte des prévisions de vent et en gérant l’affectation de techniciens. Nous présentons plusieurs modélisations du problème basées sur la programmation linéaire. Nous décrivons aussi une recherche à grands voisinages basée sur la programmation par contraintes.Cette méthode heuristique donne des résultats probants.Nous résolvons ensuite le problème avec une approche exacte basée sur une décomposition du problème. Dans cette méthode, nous construisons successivement des plannings de maintenance optimisés et rejetons, à l’aide de coupes spécifiques, ceux pour lesquels la disponibilité des techniciens est insuffisante. Les résultats suggèrent que cette méthode est la mieux adaptée pour ce problème. Enfin, pour prendre en compte l’incertitude inhérente à la prévision de vitesses de vent, nous proposons une approche robuste dans laquelle nous prenons des décisions garantissant la réalisabilité du planning de maintenance et le meilleur revenu pour les pires scénarios de vent<br>Efficiently scheduling maintenance operations of generating units is key to prevent unnecessary downtime and excessive operational costs. In this work, we first present a multidimensional classification of the body of work dealing with the optimization of the maintenance scheduling in the operations research literature. Motivated by the recent emergence of the renewable energy sector as an Environmental priority to produce low-carbon power electricity, we introduce and discuss a challenging Maintenance scheduling problem rising in the onshore wind industry. Addressing the problem on a short-term horizon, the objective is to find a maintenance plan that maximizes the revenue generated by the electricity production of the turbines while taking into account wind predictions, multiple task execution modes, and technician-to-task assignment constraints. We start by presenting several integer linear Programming formulations of the problem. We then describe a constraint programming-based large neighborhood search which proves to be an efficient heuristic solution method. We then design an exact branch-and-check approach based on a decomposition of the problem. In this method, we successively build maintenance plans while discarding – using problem-specific cuts – those that cannot be performed by the technicians. The results suggest that this method is the best suited to the problem. To tackle the Inherent uncertainty on the wind speed, we also propose a robust approach in which we aim to take risk-averse decisions regarding the revenue associated with the maintenance plan and its feasibility
48
Oliveira, António Miguel Cardeira Ramos. "Problemas de transporte de mercadorias : aplicação ao caso da Força Aérea Portuguesa." Master's thesis, Instituto Superior de Economia e Gestão, 2014. http://hdl.handle.net/10400.5/7863.
Full textAbstract:
Mestrado em Contabilidade, Fiscalidade e Finanças Empresariais<br>Com este trabalho estuda-se parte do sistema logístico da Força Aérea Portuguesa (FA), tendo como objetivo a redução de custos resultantes das missões de transporte para o estrangeiro, auxiliando assim, a gestão financeira e a logística de planeamento. Várias entidades do seio da FA foram contactadas com o intuito de recolher informações acerca das missões de transporte e especificações técnicas das aeronaves utilizadas nestas mesmas missões. Entidades civis de transportes de mercadorias foram também contactadas de forma a criar mais cenários possíveis. Posteriormente foi desenvolvido um modelo de programação linear inteira, visando a minimização dos custos de transporte de mercadorias. Tal é possível através da otimização e rentabilização do espaço de carga de cada meio de transporte que possa ser utilizado em cada missão, quer sejam civis, militares, ou ambos. Obteve-se desta forma uma solução para possíveis missões futuras da FA, ao menor custo possível, tendo em vista o cumprimento das obrigações inerentes ao bom funcionamento das missões nos diferentes níveis, operacional, logístico e orçamental.<br>With this work is studied the Portuguese Air Force (FA) logistics system aiming the cost reduction resulting from the transport missions abroad, thus helping, the financial management and logistics planning. Several identities within the FA were contacted in order to gather information about transport missions and technical specifications of the aircraft used in these missions. Civilian transport entities were also contacted in order to create more possible scenarios. Later on an integer linear programming model was developed, aiming the costs minimization of goods transportation. This is achieved through the optimization and improvement of the cargo space of each means of transport that can be used in each mission, whether civil, military or both. Obtained in this manner a solution for possible FA future missions, at the lowest possible cost, in view of fulfil the proper functioning inherent obligations of the missions at different levels, operational, logistical and budgetary.
49
Barbosa, Davi Prates Oliveira. "Um modelo matemático de otimização da mistura de diferentes variedades de açúcar para atender ao padrão de qualidade de países importadores." Universidade Federal de Alagoas, 2016. http://www.repositorio.ufal.br/handle/riufal/1577.
Full textAbstract:
In this dissertation a mathematical model is developed to establish the weight ratio of sugar’s varieties in a mixture directed to the export of the product, where are filled some quality requirements. Currently, Brazil is one of the world's largest sugar exporters, with an export volume estimated at 32.6 million tons for the harvest 2019. To meet the quality requirements of importing countries, it is necessary to combine the sugar’s varieties with different characteristics. The proposed model presents an objective function that minimizes the total cost of the blend, respecting these minimum and maximum characteristics required for each export market. The mathematical model is designed as a Linear Programming problem. The results were presented from the analysis of a case study, where the data have been validated in the General Algebraic Modeling System software (GAMS).<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>Neste trabalho foi desenvolvido um modelo matemático com o objetivo de estabelecer a proporção mássica de variedades de açúcar numa mistura voltada à exportação do produto, onde são preenchidos alguns requisitos de qualidade. Atualmente, o Brasil é um dos maiores exportadores de açúcar do mundo, com um volume de exportação estimado em 32,6 milhões de toneladas para a safra 2019. Para atender às exigências de qualidade dos países importadores, faz-se necessário combinar as variedades de açúcar com características diferentes. O modelo proposto apresenta uma função objetivo que minimiza o custo total da mistura, respeitando essas características mínima e máxima exigidas por cada mercado importador. O modelo matemático foi concebido como um problema de Programação Linear. Os resultados foram apresentados a partir da análise de um estudo de caso, onde os dados foram validados no software General Algebraic Modeling System (GAMS).
50
Röhl, Stefan. "Ein linearer Programmierungsansatz zur Lösung von Stopp- und Steuerungsproblemen." Doctoral thesis, Humboldt-Universität zu Berlin, Wirtschaftswissenschaftliche Fakultät, 2001. http://dx.doi.org/10.18452/14586.
Full textAbstract:
Es wird ein Ansatz und ein Algorithmus zur Lösung von stochastischen Stoppproblemen vorgestellt, der auf einer dualen Formulierung zum klassischen Lösungsansatz für Stoppprobleme mittels Variationsungleichungen basiert. Unter bestimmten Voraussetzungen kann man für diese duale Formulierung ein äquivalentes unendlichdimensionales lineares Programm aufstellen, das die Momente des Aufenthaltsmaßes des stochastischen Prozesses bis zum Stoppzeitpunkt und die Momente der Verteilung des Prozesses zum Zeitpunkt des Stoppens als Variablen enthält. Für dieses unendlichdimensionale Problem werden endlichdimensionale Approximationen formuliert und gelöst, wobei die Momente nur bis zu einer endlichen Ordnung berücksichtigt werden. Die Güte der numerischen Resultate hängt davon ab, wie genau der Träger des Maßes zum Stoppzeitpunkt identifiziert werden kann. Aus diesem Grund wird ein Verfeinerungsalgorithmus entwickelt, mit dem diese Identifizierung in einer Reihe von Fällen gelingt und sich sehr genaue Ergebnisse erzielen lassen. Der für Stoppprobleme entwickelte Algorithmus kann auch bei der Ermittlung von optimalen Steuerungen für stetige stochastische Prozesse angewandt werden. Für einzelne Beispiele wird gezeigt, welche Resultate dabei erzielt werden können.<br>We present an approach to, and an algorithm for solving optimal stopping problems. The approach is based on a dual formulation of the classical method for solving stopping problems using variational inequalities. Under suitable conditions it is possible to express the dual formulation as an infinite-dimensional linear program. This linear program uses the moments of the occupation measure and the moments of the stopping measure as variables. We formulate and solve finite-dimensional approximations to this infinite-dimensional program by restricting the number of moments. The accuracy of the numerical results depend on how well the support of the stopping measure can be identified. To this end we develop an iterative procedure which works very well in many cases. In the second part of the dissertation we show how the algorithm, developed for stopping problems, can be used for solving stochastic control problems.