Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/13250
Title: Το λήμμα του Farkas στη γραμμική βελτιστοποίηση
Other Titles: Farkas lemma in linear optimization
Authors: Μάντζιος, Αλέξανδρος
Keywords: Γραμμικός προγραμματισμός
Γραμμική βελτιστοποίηση
Λήμμα Farkas
Keywords (translated): Linear programming
Linear ortimization
Farkas' lemma
Abstract: Ο γραμμικός προγραμματισμός ή αλλιώς η γραμμική βελτιστοποίηση είναι ο κλάδος των Μαθηματικών που ασχολείται με την βελτιστοποίηση γραμμικών συναρτήσεων c 1 x 1 + c 2 x 2 + . . . + c n x n (c^2 x) κάτω από γραμμικούς ανισωτικούς περιορισμούς της μορφής α i1 x 1 + α i2 x 2 + . . . + α in x n ≤ b i (Ax ≤ b) Η σπουδαιότητα του συγκεκριμένου κλάδου φαίνεται στο γεγονός ότι αποτελεί ερ- γαλείο επιχειρήσεων προκειμένου αυτές να καταφέρουν να ελαχιστοποιήσουν τα έξοδά τους ή να μεγιστοποιήσουν τα κέρδη Κύριος εκπρόσωπος του γραμμικού προγραμματισμού είναι ο Αμερικανός μαθημα- τικός George B Dantzig ο οποίος αποτελεί τον εμπνευστή του αλγόριθμου simplex ενός από τους πιο διαδεδομένους τρόπους επίλυσης προβλημάτων γραμμικού προγραμματι- σμού Η παρούσα εργασία πραγματεύεται κυρίως το θεωρητικό υπόβαθρο πάνω στο οποίο στηρίζονται οι τρόποι επίλυσης τέτοιων προβλημάτων Ειδικότερα ασχολείται με το πότε και το γιατί μπορεί κανείς να γνωρίζει αν ένα πρόβλημα γραμμικού προγραμματισμού έχει λύσεις και όχι με το πώς αυτό λύνεται Στο παραπάνω ερώτημα έρχεται να απαντήσει το λήμμα του Farkas το οποίο διευ- κρινίζει ποτέ ένα σύστημα της μορφής Ax ≤ b έχει λύσεις Στο τελευταίο κεφάλαιο της εργασίας και αφού σε προηγούμενα κεφάλαια έχουν οριστεί οι έννοιες του γραμμικού προγραμματισμού της δυικότητας καθώς και έννοιες κυρτής ανάλυσης αναγκαίες για την κατανόηση του θεωρητικού υποβάθρου της εργασίας παρουσιάζεται εκτενώς το λήμμα του Farkas και αποδεικνύεται με δύο διαφορετικούς τρόπους
Abstract (translated): Linear programming or linear optimization is the part of mathematics which deals with optimization of linear functions such as c 1 x 1 + c 2 x 2 + . . . + c n x n (c^2 x) subjected to linear inequalities α i1 x 1 + α i2 x 2 + . . . + α in x n ≤ b i (Ax ≤ b) The importance of this particular part of mathematics is recognized by the fact that many companies use linear programming in order to reduce the cost or increase the profit A main representative of linear programming is the American mathematician George B Dantzig who developed the Simplex algorithm. This particular algorithm is the most widespread way to solve linear problems This thesis is represented the theoretical base of this kind of problems. Particularly this thesis answers questions about when and under what conditions a linear system Ax ≤ b has a solution In the the first chapters defined basic terms of linear programming ,duality and convex analysis which are crucial for the reader to understand the theoretical base of the thesis finally in last chapter is represented the Farkas lemma and two proofs of that
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Diplomatiki_Alexandros_Mantzios.pdf382.92 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.