Πολλά είναι τα προβλήματα που καλούμαστε να αντιμετωπίσουμε στην καθημερινότητά μας, και που χρίζουν την ανάγκη προσδιορισμού αυτών, μέσω του Γραμμικού Στοχαστικού Προγραμματισμού. Βασικό εργαλείο των προβλημάτων του Γραμμικού Στοχαστικού Προγραμματισμού που χρησιμοποιείται για την υπολογιστική τους επίλυση είναι οι μέθοδοι του Γραμμικού και του Μη Γραμμικού Προγραμματισμού. Στο 1ο κεφάλαιο της παρούσας Διπλωματικής Εργασίας, υπενθυμίζονται οι βασικές ιδιότητες και μέθοδοι επίλυσης των Γραμμικών και Μη Γραμμικών προβλημάτων, όπως αυτές χρησιμοποιούνται από τον Στοχαστικό Προγραμματισμό. Στο 2ο κεφάλαιο, παρουσιάζεται μια σειρά από Γραμμικά μοντέλα Στοχαστικού Γραμμικού Προγραμματισμού ενός σταδίου συζητώντας τις θεωρητικές τους ιδιότητες, σχετικές με την υπολογιστική τους δυνατότητα, μία από τις οποίες αποτελεί η κυρτότητά τους. Στο 3ο, και τελευταίο κεφάλαιο, ακολουθείται μια αντίστοιχη παρουσίαση των Γραμμικών Στοχαστικών μοντέλων πολλαπλών σταδίων, τονίζοντας τις ιδιότητες αυτές που επιτρέπουν την κατασκευή προσεγγιστικών μεθόδων επίλυσης. / There are various special problem formulations to be dealt with in our daily life, and our conclusion is that a basic toolkit of Linear and Nonlinear Programming methods cannot be waived if we want to deal with the computational solution of Stochastic Linear Programming problems. In chapter 1, basic properties of Linear Problems and Non Linear Problems, as well as their solution methods, are reminded, as they are used in the Stochastic Linear Programming. In chapter 2, various Single-stage Stochastic Linear Programming (SLP) models are presented and their theoretical properties are discussed, which are relevant for their computational tractability, as convexity statements. Conclusions are presented in chapter 3, followed by an analogous discussion of Multi-stage SLP models, focussed, among others, on properties allowing for the construction of particular approximation methods for computing solutions.

In the rapidly changing world of today, people have to make decisions under some degree of uncertainty. At the same time, the development of computing technologies enables people to take uncertain factors into considerations while making their decisions.Stochastic programming techniques have been widely applied in finance engineering, supply chain management, logistics, transportation, etc. Such applications often involve a large, possibly infinite, set of scenarios. Hence the resulting programstend to be large in scale.The need to solve large scale programs calls for a combination of mathematical programming techniques and sample-based approximation. When using sample-based approximations, it is important to determine the extent to which the resulting solutions are dependent on thespecific sample used. This dissertation research focuses on computational evaluation of the solutions from sample-based two-stage/multistage stochastic linear programming algorithms, with a focus on the effectiveness of optimality tests and the quality ofa proposed solution.In the first part of this dissertation, two alternative approaches of optimality tests of sample-based solutions, adaptive and non-adaptive sampling methods, are examined and computationally compared. The results of the computational experiment are in favor of the adaptive methods. In the second part of this dissertation, statistically motivated bound-based solution validation techniques in multistage linear stochastic programs are studied both theoretically and computationally. Different approaches of representations of the nonanticipativity constraints are studied. Bounds are established through manipulations of the nonanticipativity constraints.

Durant les dernières décennies, des réseaux de logistiques inverses ont été lancésdans plusieurs pays industrialisés dans l’objectif de préserver l’environnement. La mise enplace et la gestion de cette logistique concernent les différents niveaux, stratégique, tactique etopérationnel existants dans le cadre de la logistique directe pour tout système de productionde biens industriels. Pour améliorer ce type de réseau, la modélisation et la simulation sontdes outils efficaces. Après avoir présenté un état de l’art de ce domaine, notre étude sefocalise sur la planification de certains sous-ensembles (appelés maillons) de cette chaineinverse (i.e. collecte-tri, désassemblage) au niveau tactique, c'est-à-dire à moyen terme. Lebut de ce travail est donc de proposer un modèle générique en programmation linéaire dans uncontexte multi-produit et multi-période, qui cherche à maximiser le profit total du maillonétudié et qui prend en compte l’incertitude sur la qualité des produits traités. Le modèlelinéaire en nombres entiers (déterministe, stochastique et évaluation stochastique) est ainsiformulé autour d’un profit contraint par les capacités du maillon, l’évolution des stocksentrants et sortants et la livraison des produits traités aux clients, avec une politique delivraison sans déclassement ou avec déclassement des produits. / During the last decades, reverse logistics networks have been launched in severalindustrialized countries with the aim of preserving the environment. The implementation andmanagement of the reverse logistics concerns the different levels (strategic, tactical andoperational) existing in the framework of forward logistics for any production system. Toimprove this type of network, modeling and simulation are effective tools. After presenting astate of the art in this domain, our study focuses on the planning of two sub-systems of thereverse logistics chain (i.e. collection-sorting and disassembly) on the tactical level that is tosay the medium term. The aim of this work is to propose a generic model by linearprogramming in a multi-product and multi-period context, which searches for maximizingthe total profit of the sub-system studied, taking into account the uncertainty of the productssupplied. The integer linear model (deterministic, stochastic and stochastic assessment) is thusformulated around a profit constrained by the sub-system capacity, the evolution of incomingand outgoing inventory and the delivery of products to customers: a delivery policyauthorizing the quality degrading of products or not.

[pt] Nesta dissertação será apresentado como fundos de pensão na modalidade benefícios definidos podem recorrer à programação linear inteira mista para resolver problemas de ALM. Devemos considerar que a legislação brasileira determina que participantes e patrocinadores devam pagar contribuição extraordinária em caso de déficit ou, em caso de superávit persistente, parte do excesso contributivo deve ser devolvido aos participantes. Esse aspecto legal particular requer o uso de técnicas de programação inteira. Com o objetivo de modelar a ocorrência de eventos de desequilíbrio nos fundos de pensão foi necessária a introdução de variáveis inteiras para proceder a contagem do número de ocorrências desses eventos. Um exemplo simples, porém realista, foi introduzido para mostrar como os gestores de um fundo de pensão não só determinam a menor contribuição necessária à operação do fundo de pensão, mas também devem investir os recursos garantidores a fim de assegurar essa contribuição mínima. / [en] In this dissertation we discuss how defined benefit plans can use mixed integer linear programming to solve an ALM problem. We must consider that Brazilian pension fund regulations commands that participants and sponsors alike are to pay an extra contribution in case of deficit, or, in case of a persistent superavit, part of the exceeding contribution should return to its participants. This particular legal aspect forces us to use integer programming techniques. In order to model this lack of balance, an integer variable was considered so as to count how many times it occurs. A simple but realistic example is presented to show how pension fund managers may not only plan their operation to get the minimal possible contribution but also invest money to support it.

Πολλά είναι τα προβλήματα απόφασης τα οποία μπορούν να μοντελοποιηθούν ως προβλήματα γραμμικού προγραμματισμού. Πολλές όμως είναι και οι καταστάσεις όπου δεν είναι λογικό να υποτεθεί ότι οι παράμετροι του μοντέλου καθορίζονται προσδιοριστικά. Για παράδειγμα, μελλοντικές παραγωγικότητες σε ένα πρόβλημα παραγωγής, εισροές σε μία δεξαμενή που συνδέεται με έναν υδροσταθμό παραγωγής ηλεκτρικού ρεύματος, απαιτήσεις στους διάφορους κόμβους σε ένα δίκτυο μεταφορών κλπ, είναι καταλληλότερα μοντελοποιημένες ως αβέβαιες παράμετροι, οι οποίες χαρακτηρίζονται στην καλύτερη περίπτωση από τις κατανομές πιθανότητας. Η αβεβαιότητα γύρω από τις πραγματοποιημένες τιμές εκείνων των παραμέτρων δεν μπορεί να εξαλειφθεί πάντα εξαιτίας της εισαγωγής των μέσων τιμών τους ή μερικών άλλων (σταθερών) εκτιμήσεων κατά τη διάρκεια της διαδικασίας μοντελοποίησης. Δηλαδή ανάλογα με την υπό μελέτη κατάσταση, το γραμμικό προσδιοριστικό μοντέλο μπορεί να μην είναι το κατάλληλο μοντέλο για την περιγραφή του προβλήματος που θέλουμε να λύσουμε. Σε αυτή τη διπλωματική υπογραμμίζουμε την ανάγκη να διευρυνθεί το πεδίο της μοντελοποίησης των προβλημάτων απόφασης που παρουσιάζονται στην πραγματική ζωή με την εισαγωγή του στοχαστικού προγραμματισμού. / There are many practical decision problems than can be modeled as linear programs. However, there are also many situations that it is unreasonable to assume that the coefficients of model are deterministically fixed. For instance, future productivities in a production problem, inflows into a reservoir connected to a hydro power station, demands at various nodes in a transportation network, and so on, are often appropriately modeled as uncertain parameters, which are at best characterized by probability distributions. The uncertainty about the realized values of those parameters cannot always be wiped out just by inserting their mean values or some other (fixed) estimates during the modelling process. That is, depending on the practical situation under consideration, the linear deterministic model may not be the appropriate model for describing the problem we want to solve. In this project we emphasize the need to broaden the scope of modelling real life decision problems by inserting stochastic programming.