Μερικά προβλήματα γραμμικού προγραμματισμού

Ο γραμμικός προγραμματισμός είναι ένα σημαντικό εργαλείο Στην "Επιχειρησιακή Έρευνα" ένα σχετικά νέο κλάδο της μαθηματικής επιστήμης. Βέβαια, στα μαθηματικά, δεν εννοούμε τον προγραμματισμό με την έννοια που έχει στην πληροφορική. Με τον όρο προγραμματισμό εννοούμε την ανακάλυψη αλγορίθμου για τη βελτιστοποίηση ενός προβλήματος κέρδους (κέρδος με την ευρύτερη έννοια, όχι μόνο χρηματικό) ή ελαχιστοποίησης για προβλήματα ζημιών (με την ευρύτερη έννοια της ζημίας, όχι μόνο χρηματική). Συχνά οι μαθητές στις εξετάσεις αντιμετωπίζουν προβλήματα όπου καλούνται να σχηματίσουν μια εξίσωση. Ομαθητής πρέπει πρώτα να μεταφράσει τις συνθήκες του προβλήματος από τη φυσική γλώσσα στη μαθηματική και στη συνέχεια να λύσει τις προκύπτουσες εξισώσεις και ανισώσεις. Μέσα από την κατάσταση που περιγράφει το πρόβλημα, ο μαθητής πρέπει να βρει κάποιες συγκεκριμένες ποσότητες έχοντας σαν δεδομένες κάποιες άλλες. Είναι σημαντικό να γνωρίζουμε τον τρόπο λύσης τέτοιων προβλημάτων τα οποία εμφανίζονται πολύ συχνά στη βιομηχανία και την οικονομία, όπου χρειάζεται να γνωρίζουμε συγκεκριμένους δείκτες, να υπολογίζουμε ποσότητες, να αναλύουμε την κατάσταση μιας εταιρείας, κ.λ.π.. Μια τέτοια ανάλυση μας βοηθά να κατανοήσουμε καλύτερα την τρέχουσα κατάσταση. Το επόμενο βήμα είναι να σχεδιάσουμε τις μελλοντικές δραστηριότητες. Εδώ υπάρχουν πολυάριθμες εναλλακτικές δυνατότητες, αλλά πρέπει να είμαστε σε θέση να επιλέξουμε τη βέλτιστη από αυτές ανάλογα με το αποτέλεσμα που επιθυμούμε να επιτύχουμε. Η διατύπωση και η λύση τέτοιων εξισώσεων αποτελεί το αντικείμενο του μαθηματικού προγραμματισμού.

Μερικά προβλήματα γραμμικού προγραμματισμού

Επιλογή της θέσης των λουτρών

Μία κωμόπολη έχει 100 κατοίκους και το γειτονικό χωριό 50. Επιλέξτε μια θέση για την κατασκευή των λουτρών πάνω στο δρόμο που συνδέει τις δύο κοινότητες, έτσι ώστε η απόσταση που θα διανύουν οι 150 κάτοικοι για να πάνε στα λουτρά να είναι η ελάχιστη.

Στη γλώσσα των μαθηματικών: Έστω ότι η απόσταση μεταξύ των δύο χωριών είναι α Km και ότι τα λουτρά βρίσκονται σε απόσταση x Km από την κωμόπολη. Επομένως, ισχύει  0 ≤ x ≤ α . Οι 100 κάτοικοι της κωμόπολης πρέπει να περπατήσουν 100x km για να πάνε στα λουτρά ενώ οι κάτοικοι του χωριού 50(α - x) Km. Επομένως, η συνολική απόσταση που διασχίζουν οι κάτοικοι είναι:

s = 100 x + 50 (α − x).

Άρα αρκεί να βρούμε την ελάχιστη τιμή της εξίσωσης  s = 100 x + 50 (α − x),  όταν $$0\le x\le \mathrm{\alpha \; <span\; style="font-family:\; Times,\; "Times\; New\; Roman",\; serif;">,\; ό\pi o\upsilon \; \tau o\; \alpha \; \epsilon ί\nu \alpha \iota \; \sigma \tau \alpha \theta \epsilon \rho ό.</span>}$$$$\mathrm{<span\; style="font-family:\; Times,\; "Times\; New\; Roman",\; serif;">\; \Pi \alpha \rho \alpha \tau \eta \rho oύ\mu \epsilon \; ό\tau \iota \; \tau o\; s\; \pi \alpha ί\rho \nu \epsilon \iota \; \tau \eta \nu \; \epsilon \lambda ά\chi \iota \sigma \tau \eta \; \tau \iota \mu ή\; ό\tau \alpha \nu \; \pi \alpha ί\rho \nu \epsilon \iota \; \tau \eta \nu \; \epsilon \lambda ά\chi \iota \sigma \tau \eta \; \tau \iota \mu ή\; \tau o\; x,\; ά\rho \alpha \; \gamma \iota \alpha \; x\; =\; 0,\; \tau o</span>}$$
$$\mathrm{<span\; style="font-family:\; Times,\; "Times\; New\; Roman",\; serif;">s\; =\; 50\alpha ,\; \delta \eta \lambda \alpha \delta ή\; \tau \alpha \; \lambda o\upsilon \tau \rho ά\; \theta \alpha \; \chi \tau \iota \sigma \tau oύ\nu \; \sigma \tau \eta \nu \; \kappa \omega \mu ό\pi o\lambda \eta . </span>}$$

$$\mathrm{<span\; style="font-family:\; Times,\; "Times\; New\; Roman",\; serif;">{\rm O}\; \kappa \alpha \lambda ύ\tau \epsilon \rho o\varsigma \; \tau \rho ό\pi o\varsigma \; \gamma \iota \alpha \; \nu \alpha \; \phi \tau ά\sigma \epsilon \tau \epsilon \; \sigma \tau o\; \sigma \tau \alpha \theta \mu ό</span>}$$

$$\mathrm{<span\; style="font-family:\; Times,\; "Times\; New\; Roman",\; serif;"> </span>}$$

Ο κύριος Σμιθ πρέπει να φτάσει στο σιδηροδρομικό σταθμό το συντομότερο δυνατό. Έχει τη δυνατότητα είτε να καλέσει ταξί το οποίο θα έρθει σε 24 min και θα τον μεταφέρει στο σταθμό με ταχύτητα 30 Km/h είτε να περπατήσει με ταχύτητα 6 Km/h. ποια μέθοδος είναι προτιμότερη αν ο σταθμός απέχει: (α) 2 Km , (β) 3 Km , (γ) 5 Km ;

Για να συγκρίνουμε καλύτερα την κίνηση του πεζου και του αυτοκινήτου, θα εισάγουμε στο πρόβλημά μας ακόμη ένα πρόσωπο, τη σύζυγο του κ. Σμιθ. Ας υποθέσουμε λοιπόν ότι ο κ. Σμιθ άρχισε να περπατα για το σταθμό και ότι, μόλις βγήκε από το σπίτι, η σύζυγος του πρόσεξε ότι είχε ξεχάσει το εισητήριο του. Τότε, κάλεσε αμέσως ταξί, περίμενε να έρθει και ξεκίνησε να συναντήσει το σύζυγό της. Ας υπολογίσουμε το χρόνο που χρειάζεται για να τον προλάβει. Τη χρονική στιγμή t μετά την αναχώρισή του, ο κ. Σμιθ θα βρίσκεται σε απόσταση 6t Km από το σπίτι του. Αν t > 24 min = 2/5 h, το ταξί θα διανύσει 30(t - (2/5)) Km. Το ταξί θα προλάβει τον κ. Σμιθ όταν

6t = 30(t - (2/5)), δηλαδή όταν t = 1/2 h.

Αν το περπάτημα μέχρι το σταθμό διαρκέσει λιγότερο από 1/2 h, η σύζυγος του κ. Σμιθ δεν θα τον προλάβει. Διαφορετικά, θα τον συναντήσει και θα τον πάει στο σιδηροδρομικό σταθμό. Ο κ. Σμιθ μπορεί να περπατήσει 3 Km σε 1/2 h. Συνεπώς καταλήγουμε στο εξής συμπέρασμα:

Αν η απόσταση του σταθμού είναι μικρότερη των 3 Km (περίπτωση (α)), ο κ. Σμιθ είναι προτιμότερο να περπατήσει. Αν η απόσταση ισούται με 3 Km, το περπάτημα και η μετακίνηση με ταξί είναι ισοδύναμα, ενώ στην περίπτωση (γ) είναι προτιμότερο να πάρει ταξί.

Κατά τη λύση του προβλήματος πραγματοποιήσαμε ορισμένες σιωπηλές παραδοχές: η κίνηση του πεζού και του ταξί είναι ομαλές, η κλήση και η αναχώριση του ταξί είναι στιγμιαίες, κ.τ.λ. Επιπλέον, υποθέσαμε ότι ο σημαντικότερος πόρος για τον κ. Σμιθ είναι ο χρόνος. Για να επιλέξουμε μία από τις ισοδύναμες επιλογές του κ. Σμιθ στην περίπτωση (β) πρέπει να συνυπολογίσουμε και το κόστος μετακίνησης ή την άνεση οπότε πράττουμε αναλόγως.