Μαθήματα Ευρετικής :Μέρος έκτο (Δεν λύνονται όλα με εξισώσεις!!! )

 Έχουμε συνδυάσει τα μαθηματικά προβλήματα με εξισώσεις .Συνήθως«μεταγλωττίζουμε» τα δεδομένα με την χρήση μεταβλητών σε εξισώσεις και από εκεί και πέρα η λύση είναι τετριμμένη. Δεν οδηγούν όμως όλα τα προβλήματα σε εξισώσεις .

Όπως για παράδειγμα κάποια προβλήματα βελτιστοποίησης.Δείτε ένα παράδειγμα:

« Ο Οδοντίατρος Παπαδόπουλος φτάνει στο ιατρείο του,εκεί διαπιστώνει ότι τον περιμένουν 5 ασθενείς του, χωρίς ραντεβού . Οι ασθενείς είναι οι Α ,Β,Γ ,Δ και ο Ε  .Έχουν έρθει ταυτόχρονα και δεν υπάρχει σειρά. Για τον καθένα τους ο Παπαδόπουλος γνωρίζει πόση ώρα θα χρειαστεί για την θεραπεία του.

-Για την  θεραπεία  του  ασθενή Α  θα απαιτηθούν           20 λεπτά .

-Για την θεραπεία  του  ασθενή  Β   >>>          >>>          10 λεπτά .

-Για την θεραπεία  του  ασθενή  Γ   >>>          >>>          30 λεπτά .

-Για την θεραπεία  του  ασθενή  Δ    >>>          >>>          15 λεπτά .

-Για την θεραπεία  του  ασθενή  Ε     >>>          >>>          20 λεπτά .

Το ερώτημα που τίθεται είναι με ποια σειρά θα δεχτεί ο Παπαδόπουλος τους ασθενείς  έτσι ώστε ο  χρόνος που θα περιμένουν συνολικά οι  5 ασθενείς να είναι ελάχιστος .»

Μια προσέγγιση θα ήταν να τους βάλει στην τύχη για παράδειγμα θα μπορούσε να τους δεχτεί  με την σειρά Α,Β,Γ,Δ,Ε  τότε ο συνολικός χρόνος αναμονής θα είναι :

Ο Α θα εξυπηρετηθεί αμέσως ,ο Β θα περιμένει 20 λεπτά ,ο Γ θα περιμένει 20+10=30 λεπτά , ο Δ θα περιμένει 20+10+30=60 λεπτά, ο Ε θα περιμένει 20+10+30+15=75 λεπτά άρα ο συνολικός χρόνος αναμονής είναι 20+30+60+75=185 λεπτά . Είναι όμως ο λιγότερος δυνατός; Μπορούμε να διατάξουμε  5 ασθενείς με 6!=1x2x3x4x5x6=720 τρόπους.Προφανώς και είναι πάρα πολλές οι επιλογές για να τις δοκιμάσουμε μια-μια .Πρέπει να προσεγγίσουμε το πρόβλημα διαφορετικά.

 Ας υποθέσουμε ότι έχουμε ν ασθενείς  A1,A2,…Aν  και οι χρόνοι θεραπείας τους είναι αντίστοιχα t1,t2,t3,…,tν  τότε οι χρόνοι αναμονής του καθένα θα είναι:

    Α1:0                               λεπτά

   Α2:t1                               λεπτά

   A3: t1+t2                        λεπτά

   A4: t1+t2+ t3                  λεπτά

      .

      .

    Αν: t1+t2+ t3+….tν-1   λεπτά   (προσθέτουμε κατά μέλη)

                (ν-1)t₁+(ν-2)t₂+(ν-3)t₃+…..2t_ν-2+t_ν-1    (1)

 Το παραπάνω άθροισμα  ο μεγαλύτερος συντελεστής είναι  ο (ν-1) άρα με αυτόν πρέπει να πολλαπλασιάσουμε τον μικρότερο χρόνο ,με τον αμέσως μικρότερο συντελεστή (ν-2) τον δεύτερο μεγαλύτερο χρόνο και ούτω καθεξής .

Άρα στο συγκεκριμένο παράδειγμα  όπου το πλήθος των ασθενών είναι ν=5θα έχουμε τον ελάχιστο συνολικό χρόνο ως εξής :

Οι χρόνοι διατάσσονται  από τον μικρότερο προς το μεγαλύτερο  10,15,20,20,30 άρα η (1) γίνεται:

(5-1)x10+(5-2)x15+(5-3)x20+(5-4)x20=4x10+3x15+2x20+1x20=40+45+40+20=145 λεπτά

και η σειρά των ασθενών θα είναι Β,Δ,Α,Ε,Γ .