Ο Γραμμικός Προγραμματισμός (ΓΠ) είναι ένα σημαντικός τομέας της επιχειρησιακής έρευνας. Ο αλγόριθμος simplex είναι ένας από τους δέκα αλγόριθμους με τη μεγαλύτερη επιρροή στον 20ο αιώνα και η πιο ευρέως χρησιμοποιούμενη μέθοδος για την επίλυση γραμμικών προβλημάτων. Ο κύριος στόχος της διατριβής αυτής είναι η μελέτη της υπολογιστικής συμπεριφοράς δύο αλγορίθμων τύπου simplex: (i) του αναθεωρημένου αλγόριθμου simplex, και (ii) του πρωτεύοντα – δυϊκού αλγόριθμου simplex εξωτερικών σημείων. Επίσης, οι Κάρτες Γραφικών (Graphical Processing Units – GPUs) έχουν γίνει δημοφιλείς και έχουν εφαρμοστεί για την επίλυση γραμμικών προβλημάτων. Οι αλγόριθμοι τύπου simplex και οι διαφορετικές μέθοδοι στους αλγορίθμους αυτούς υλοποιούνται τόσο στη CPU όσο και στη GPU.Οι preconditioning τεχνικές είναι σημαντικές στην επίλυση γραμμικών προβλημάτων, καθώς βελτιώνουν την υπολογιστική συμπεριφορά των αλγορίθμων. Η κλιμάκωση είναι η πιο ευρέως διαδεδομένη preconditioning τεχνική στους αλγόριθμους γραμμικού προγραμματισμού και χρησιμοποιείται για τη μείωση του βαθμού κατάστασης του πίνακα των περιορισμών, για τη βελτίωση της υπολογιστικής συμπεριφοράς των αλγορίθμων και για τη μείωση του αριθμού των επαναλήψεων που απαιτούνται για την επίλυση των γραμμικών προβλημάτων. Δέκα τεχνικές κλιμάκωσης μελετώνται και συγκρίνονται υπολογιστικά. Επίσης, προτείνουμε υλοποίησης των μεθόδων αυτών σε GPUs. Τα υπολογιστικά αποτελέσματα δείχνουν ότι υπάρχει μία επιτάχυνση της τάξης του 7 για όλες τις τεχνικές κλιμάκωσης που υλοποιήθηκαν σε GPUs.Η επιλογή του στοιχείου περιστροφής σε κάθε επανάληψη είναι ένα σημαντικό βήμα στους αλγορίθμους τύπου simplex. Καλές επιλογές της εισερχόμενης μεταβλητής μπορεί να οδηγήσουν σε πιο γρήγορη εύρεση της βέλτιστης λύσης, ενώ κακές επιλογές οδηγούν σε περισσότερες επαναλήψεις και χειρότερους χρόνους εκτέλεσης ή ακόμα και με εύρεση της βέλτιστης λύσης του γραμμικού προβλήματος. Έξι κανόνες περιστροφής υλοποιήθηκαν για τον αναθεωρημένο αλγόριθμο simplex. Επίσης, προτείνουμε υλοποιήσεις των κανόνων αυτών σε GPUs. Τα υπολογιστικά αποτελέσματα δείχνουν ότι μόνο η μέθοδος Steepest Edge Rule είναι κατάλληλη για υλοποίηση σε GPUs.Ο υπολογισμός της αντιστρόφου της βάσης είναι το πιο χρονοβόρο βήμα στους αλγορίθμους τύπου simplex. Το βήμα αυτό δε χρειάζεται να γίνεται εξαρχής σε κάθε επανάληψη, αλλά σχήματα ανανέωσης της βάσης μπορούν να εφαρμοστούν για την επιτάχυνση της διαδικασίας. Μελετούμε και υλοποιούμε πέντε μεθόδους υπολογισμού τη αντιστρόφου. Στη συνέχεια, προτείνουμε υλοποίησης σε GPUs για δύο από αυτές τις μεθόδους. Τα υπολογιστικά αποτελέσματα δείχνουν ότι η μέθοδος Modification of the Product Form of the Inverse είναι ταχύτερη των υπόλοιπων μεθόδων τόσο στη CPU όσο και στη GPU και η επιτάχυνση που επιτυγχάνεται είναι 19 για το βήμα της ανανέωσης της βάσης και 5 για το συνολικό χρόνο του αλγορίθμου.Τέλος, προτείνουμε δύο αποδοτικές υλοποιήσεις σε GPUs του αναθεωρημένου αλγόριθμου simplex και ενός πρωτεύονται – δυϊκού αλγόριθμου simplex εξωτερικών σημείων. Και οι δύο υλοποιήσεις έχουν γίνει στο MATLAB χρησιμοποιώντας το MATLAB's Parallel Computing Toolbox. Τα υπολογιστικά αποτελέσματα σε τυχαία αραιά και πυκνά γραμμικά προβλήματα παρουσιάζονται. Τα αποτελέσματα δείχνουν ότι οι προτεινόμενες υλοποιήσεις στη GPU είναι καλύτερες από τον αλγόριθμο εσωτερικών σημείων του MATLAB.