Στην παρούσα Διπλωματική Εργασία, παρουσιάζεται η πολύ γνωστή μέθοδος Simplex. Με τη βοήθεια της μεθόδου Simplex, μπορούμε να επιλύσουμε προβλήματα γραμμικού προγραμματισμού, ακέραιου γραμμικού προγραμματισμού καθώς και διάφορες παραλλαγές των παραπάνω. Ειδικότερα για τον ακέραιο γραμμικό προγραμματισμό, παρουσιάζονται κάποιες από τις πιο γνωστές μεθόδους αναζήτησης, οι οποίες ανήκουν στην οικογένεια μεθόδων “Branch And Bound”. Επίσης κάποιες τεχνικές αναζήτησης των βέλτιστων λύσεων στο δένδρο που δημιουργείται από τις προηγούμενες τεχνικές. Τα παραπάνω υλοποιήθηκαν σε ένα λογισμικό με γραφικό περιβάλλον (GUI), το οποίο είναι συμβατό με τις περισσότερες εκδόσεις του Λειτουργικού Συστήματος, Windows της Microsoft και χωρίς να χρειάζονται κάτι επιπλέον σε έναν Προσωπικό Υπολογιστή. / This thesis presents the well-known method Simplex. With method Simplex, we can solve problems of linear programming, integer linear programming and several variants of the above. Especially for the integer linear programming, presented some of the most known search methods, which belong to the family of methods "Branch And Bound". Also presented some search techniques for optimal solutions in the tree, generated by the same techniques. These were implemented in a software with graphical interface (GUI), which is compatible with most versions of the Microsoft Windows OS, with a simple installation.

This thesis documents the optimized design of a touch screen using infrared technology as a three dimensional problem. The framework is fundamentally built on laser diode technology and introduces mirrors for signal reflection. The rising popularity of touch screens are credited to the naturally intuitive control of display interfaces, extensive data presentation, and the improved manufacturing process of various touch screen implementations. Considering the demands on touch screen technology, the design for a large scaled touch panel is inevitable, and signal reduction techniques become a necessity to facilitate signal processing and accurate touch detection. The developed research model seeks to capture realistic touch screen design limitations to create a deploy-able configuration. The motivation of the problem stems from the significant reduction of representation achieved by combinatorial group theory. The research model is of difficulty NP-complete. Additional exclusive-or functions for uniqueness, strengthening model search space, symmetry eliminating constraints, and implementation constraints are incorporated for enhanced performance. The computational results and analysis of objectives, valuing the emphasis on diodes and layers are evaluated. The evaluation of trade-off between diodes and layers is also investigated.

In this thesis, a resource allocation problem in OFDMA is studied for the energy efficiency of wireless network. The objective is to minimize the total energy consumption which includes transmission energy consumption, and circuit energy consumption at both transmitter and receiver with required per user’s rate constraint. For problem solution, a heuristic algorithm with low computational complexity and suboptimal solution is proposed, developed in two steps with an increasing order of complexity. Besides, a bounding scheme based on model linearization of formulated nonlinear system model is also proposed to give lower and upper bounds for both small- and large-scale OFDMA network for further algorithm performance evaluation, while the implemented exhaustive search is only capable to provide the optimal solution for small-scale instance for algorithm performance evaluation. Numerical results show that the proposal heuristic algorithm can achieve near-optimal performance with applicable computational complexity even for large-scale networks, and that the bounds from the bounding scheme are very tight for both small- and large-scale OFDMA networks.

Temos, nagrinėjamos šioje disertacijoje, buvo doktorantūros studijų Vilniaus universiteto Matematikos ir informatikos fakultete objektas. Pateikti tyrimai yra susiję su sudėtinių skaičių egzistavimu tokiose sekose kaip fiksuoto skaičiaus laipsnių sveikųjų dalių seka bei tiesinė rekurentinė seka, sudaryta iš sveikųjų skaičių. Disertaciją sudaro įvadas, 3 skyriai, išvados ir literatūros sąrašas. Pirmame skyriuje nagrinėjami sudėtiniai skaičiai racionaliųjų skaičių laipsnių sveikųjų dalių sekoje bei yra įrodoma, kad sekoje [ξ(5/4)^n], n=1,2,..., kur ξ yra bet koks teigiamas skaičius, yra be galo daug sudėtinių skaičių. Be to, įrodoma, kad yra be galo daug tokių natūraliųjų skaičių n, kad ([ξ(5/4)^n]; 6006)>1, čia 6006 = 2•3•7•11•13. Įrodoma panašių rezultatų pastumtoms kai kurių kitų racionaliųjų skaičių sekoms. Pavyzdžiui, tas pats įrodoma sveikųjų skaičių, esančių arčiausiai ξ(5/3)^n bei ξ(7/5)^n, n=1,2,..., sekoms. Vėlgi nurodomos atitinkamos galimų daliklių aibės. Antrame skyriuje nagrinėjami sudėtiniai skaičiai antros eilės tiesinėse rekurentinėse sekose bei įrodoma, kad kiekvienai tokiai sveikųjų skaičių porai (a; b), kad b≠0 ir (a; b)≠(±2; -1), egzistuoja tokie du natūralieji tarpusavyje pirminiai skaičiai x_1, x_2, kad sekoje, apibrėžtoje lygtimi x_{n+1}=ax_n+bx_{n-1}, n=2,3,..., visų narių moduliai yra sudėtiniai skaičiai. Trečiame skyriuje egiptietiškų trupmenų kontekste nagrinėjamos skaičių, užrašomų tam tikru tiesiniu pavidalu, aibės. Ieškoma, kokie skaičiai... [toliau žr. visą tekstą] / The topics examined in this thesis were the subject of my research as a PhD student at the Faculty of Mathematics and Informatics of Vilnius University. The presented investigation concerns the existence of composite numbers in some special sequences, such as the sequence of integer parts of powers of a fixed number and a linear recurrence sequence consisting of integer numbers. The thesis consists of the introduction, 3 sections, conclusions and bibliography. In Section 1 we consider composite numbers in the sequences of integer parts of powers of rational numbers and prove that the sequence [ξ(5/4)^n], n=1,2,..., where ξ is an arbitrary positive number, contains infinitely many composite numbers. Furthermore, it is shown that there are infinitely many positive integers n such that ([ξ(5/4)^n]; 6006)>1, where 6006 = 2•3•7•11•13. Similar results are obtained for shifted powers of some other rational numbers. In particular, the same is proved for the sets of integers nearest to ξ(5/3)^n and to ξ(7/5)^n, n=1,2,.... The corresponding sets of possible divisors are also described. In Section 2 we consider composite numbers in the binary linear recurrence sequences and prove that for every pair of integer numbers (a; b), where b≠0 and (a; b)≠(±2; -1), there exist two positive relatively prime composite integers x_1, x_2 such that the sequence given by x_{n+1}=ax_n+bx_{n-1}, n=2,3,..., consists of composite terms only, i.e., the absolute value of each term is a composite integer... [to full text]

No description available.

The topics examined in this thesis were the subject of my research as a PhD student at the Faculty of Mathematics and Informatics of Vilnius University. The presented investigation concerns the existence of composite numbers in some special sequences, such as the sequence of integer parts of powers of a fixed number and a linear recurrence sequence consisting of integer numbers. The thesis consists of the introduction, 3 sections, conclusions and bibliography. In Section 1 we consider composite numbers in the sequences of integer parts of powers of rational numbers and prove that the sequence [ξ(5/4)^n], n=1,2,..., where ξ is an arbitrary positive number, contains infinitely many composite numbers. Furthermore, it is shown that there are infinitely many positive integers n such that ([ξ(5/4)^n]; 6006)>1, where 6006 = 2•3•7•11•13. Similar results are obtained for shifted powers of some other rational numbers. In particular, the same is proved for the sets of integers nearest to ξ(5/3)^n and to ξ(7/5)^n, n=1,2,.... The corresponding sets of possible divisors are also described. In Section 2 we consider composite numbers in the binary linear recurrence sequences and prove that for every pair of integer numbers (a; b), where b≠0 and (a; b)≠(±2; -1), there exist two positive relatively prime composite integers x_1, x_2 such that the sequence given by x_{n+1}=ax_n+bx_{n-1}, n=2,3,..., consists of composite terms only, i.e., the absolute value of each term is a composite integer... [to full text] / Temos, nagrinėjamos šioje disertacijoje, buvo doktorantūros studijų Vilniaus universiteto Matematikos ir informatikos fakultete objektas. Pateikti tyrimai yra susiję su sudėtinių skaičių egzistavimu tokiose sekose kaip fiksuoto skaičiaus laipsnių sveikųjų dalių seka bei tiesinė rekurentinė seka, sudaryta iš sveikųjų skaičių. Disertaciją sudaro įvadas, 3 skyriai, išvados ir literatūros sąrašas. Pirmame skyriuje nagrinėjami sudėtiniai skaičiai racionaliųjų skaičių laipsnių sveikųjų dalių sekoje bei yra įrodoma, kad sekoje [ξ(5/4)^n], n=1,2,..., kur ξ yra bet koks teigiamas skaičius, yra be galo daug sudėtinių skaičių. Be to, įrodoma, kad yra be galo daug tokių natūraliųjų skaičių n, kad ([ξ(5/4)^n]; 6006)>1, čia 6006 = 2•3•7•11•13. Įrodoma panašių rezultatų pastumtoms kai kurių kitų racionaliųjų skaičių sekoms. Pavyzdžiui, tas pats įrodoma sveikųjų skaičių, esančių arčiausiai ξ(5/3)^n bei ξ(7/5)^n, n=1,2,..., sekoms. Vėlgi nurodomos atitinkamos galimų daliklių aibės. Antrame skyriuje nagrinėjami sudėtiniai skaičiai antros eilės tiesinėse rekurentinėse sekose bei įrodoma, kad kiekvienai tokiai sveikųjų skaičių porai (a; b), kad b≠0 ir (a; b)≠(±2; -1), egzistuoja tokie du natūralieji tarpusavyje pirminiai skaičiai x_1, x_2, kad sekoje, apibrėžtoje lygtimi x_{n+1}=ax_n+bx_{n-1}, n=2,3,..., visų narių moduliai yra sudėtiniai skaičiai. Trečiame skyriuje egiptietiškų trupmenų kontekste nagrinėjamos skaičių, užrašomų tam tikru tiesiniu pavidalu, aibės. Ieškoma, kokie skaičiai... [toliau žr. visą tekstą]

The focus of this dissertation is solution strategies for stochastic mixed-integer programs with special structures. Motivation for the methods comes from the relatively sparse number of algorithms for solving stochastic mixed-integer programs. Two stage models with finite support are assumed throughout. The first contribution introduces the nodal decision framework under private information restrictions. Each node in the framework has control of an optimization model which may include stochastic parameters, and the nodes must coordinate toward a single objective in which a single optimal or close-to-optimal solution is desired. However, because of competitive issues, confidentiality requirements, incompatible database issues, or other complicating factors, no global view of the system is possible. An iterative methodology called the nodal decomposition-coordination algorithm (NDC) is formally developed in which each entity in the cooperation forms its own nodal deterministic or stochastic program. Lagrangian relaxation and subgradient optimization techniques are used to facilitate negotiation between the nodal decisions in the system without any one entity gaining access to the private information from other nodes. A computational study on NDC using supply chain inventory coordination problem instances demonstrates that the new methodology can obtain good solution values without violating private information restrictions. The results also show that the stochastic solutions outperform the corresponding expected value solutions. The next contribution presents a new algorithm called scenario Fenchel decomposition (SFD) for solving two-stage stochastic mixed 0-1 integer programs with special structure based on scenario decomposition of the problem and Fenchel cutting planes. The algorithm combines progressive hedging to restore nonanticipativity of the first-stage solution, and generates Fenchel cutting planes for the LP relaxations of the subproblems to recover integer solutions. A computational study SFD using instances with multiple knapsack constraint structure is given. Multiple knapsack constrained problems are chosen due to the advantages they provide when generating Fenchel cutting planes. The computational results are promising, and show that SFD is able to find optimal solutions for some problem instances in a short amount of time, and that overall, SFD outperforms the brute force method of solving the DEP.

This dissertation discusses two independent topics. The first part of the dissertation relates three theories of international economics (comparative advantage, competitive advantage, and competitiveness), and formulates the thesis that incorporating them in the form of readily available individual competitiveness indicators in OR/MS models offers promise to enhance decision-support for the strategic planning of global supply chains in general, and for locating facilities in particular. The objectives of this research were to relate each of these theories and to describe their interrelationships; to describe measures provided by two well-known annual competitiveness reports; and to illustrate application of the theories as a means of supporting the thesis of the research, and justifying the research questions we pose for future research. While this research discusses topics relative to the broader background of global supply chain design, it illustrates applications associated with facility location, a component of the global supply chain design. In the last chapter of the first part of the dissertation, we provide a vision to foster future research that will enhance the profitability of international enterprises under NAFTA. The second part of the dissertation deals with the DSCR model with capacity expansion and contraction. The strategic dynamic supply chain reconfiguration (DSCR) problem is to prescribe the location and capacity of each facility, select links used for transportation, and plan material flows through the supply chain, including production, inventory, backorder, and outsourcing levels. The objective is to minimize total cost. The configuration must be dynamically redesigned over time to accommodate changing trends in demand and/or costs by opening facilities, expanding and/or contracting their capacities, and closing facilities. The problem involves a multi-period, multi-product, multi-echelon supply chain. Research objectives are alternative formulations of DSCR and tests that identify the computational characteristics of each model to determine if one offers superior solvability in comparison with the others. To achieve the first objective, we present an initial MIP model, a refined model that relates decision variables according to a convenient structure, and branch and price (B&P) schemes for the refined model. We found that the network-based formulation offered superior solvability compared to the traditional formulation.

In this research, a decision support model for coordinating sustainable product and supply chain design decisions is developed using a multi-stage hierarchical approach. The model evaluates alternate product designs and their corresponding supply chain configurations to identify the best product design and the corresponding supply chain configuration that maximizes the economic, environmental and societal benefits. The model considers a total life-cycle approach and incorporates closed-loop flow among multiple product lifecycles. In the first stage, a mixed integer linear programming model is developed to select for each product design an optimal supply chain configuration that maximizes the profit. In the subsequent stages, the economic, environmental and societal multiple life-cycle analysis models are developed which assess the economic, environment and the societal performance of each product design and its optimal supply chain configuration to identify the best product design with highest sustainability benefits. The decision support model is applied for an example problem to illustrate the procedure for identifying the best sustainable design. Later, the model is applied for a real-time refrigerator case to identify the best refrigerator design that maximizes economic, environmental and societal benefits. Further, sensitivity analysis is performed on the optimization model to study the closed-loop supply chain behavior under various situations. The results indicated that both product and supply chain design criteria significantly influence the performance of the supply chain. The results provided insights into closed-loop supply chain models and their behavior under various situations. Decision support models such as above can help a company identify the best designs that bring highest sustainability benefits, can provide a manager with holistic view and the impact of their design decisions on the supply chain performance and also provide areas for improvement.

En 1993, Conway et Schneeberger fournirent un critère simple permettant de déterminer si une forme quadratique donnée représente tous les entiers positifs ; le théorème des 15. Dans ce mémoire, nous nous intéressons à un problème analogue, soit la recherche d’un critère similaire permettant de détecter si une forme quadratique en trois variables représente tous les entiers impairs. On débute donc par une introduction générale à la théorie des formes quadratiques, notamment en deux variables, puis on expose différents points de vue sous lesquels on peut les considérer. On décrit ensuite le théorème des 15 et ses généralisations, en soulignant les techniques utilisées dans la preuve de Bhargava. Enfin, on démontre deux théorèmes qui fournissent des critères permettant de déterminer si une forme quadratique ternaire représente tous les entiers impairs. / In 1993, Conway and Schneeberger gave a simple criterion allowing one to determine whether a given quadratic form represents all positive integers ; the 15-theorem. In this thesis, we investigate an analogous problem, that is the search for a similar criterion allowing one to detect if a quadratic form in three variables represents all odd integers. We start with a general introduction to the theory of quadratic forms, namely in two variables, then, we expose different points of view under which quadratic forms can be considered. We then describe the 15-theorem and its generalizations, with a particular emphasis on the techniques used in Bhargava’s proof of the theorem. Finally, we give a proof of two theorems which provide a criteria to determine whether a ternary quadratic form represents all odd integers. / Les calculs numériques ont été effectués à l'aide du logiciel SAGE.