Μετάβαση στο περιεχόμενο
Topos Uranos
Ελληνικά

Ανισώσεις στο επίπεδο και γραμμικός προγραμματισμός

Περίληψη

Το μάθημα αυτό μεταφέρει στο επίπεδο τη μελέτη των ανισώσεων. Αποδεικνύει ότι μια ευθεία χωρίζει το επίπεδο σε δύο ημιεπίπεδα, σε καθένα από τα οποία η γραμμική παράσταση που την ορίζει διατηρεί το πρόσημό της, και από αυτό συνάγει τη μέθοδο του σημείου ελέγχου. Περιγράφει την περιοχή λύσεων ενός συστήματος γραμμικών ανισώσεων ως τομή ημιεπιπέδων, με τις κορυφές της, και αποδεικνύει ότι είναι κυρτή· μελετά έπειτα τις περιοχές που οριοθετούνται από κωνικές τομές. Κλείνει με τον γραμμικό προγραμματισμό: την αναζήτηση του μεγίστου ή του ελαχίστου μιας γραμμικής συνάρτησης σε μια πολυγωνική περιοχή, της οποίας το θεμελιώδες θεώρημα εξασφαλίζει ότι σε ένα κυρτό φραγμένο πολύγωνο και τα δύο επιτυγχάνονται σε κορυφές και ότι, σε μια μη φραγμένη περιοχή με κάποια κορυφή, κάθε βέλτιστη τιμή που υπάρχει επιτυγχάνεται επίσης σε μία από αυτές, και με προβλήματα παραγωγής, διατροφής και μεταφοράς.

Μαθησιακοί στόχοι

  1. Να παριστάνεται το σύνολο λύσεων μιας γραμμικής ανίσωσης με δύο μεταβλητές ως ημιεπίπεδο, ανοικτό ή κλειστό, με τη βοήθεια ενός σημείου ελέγχου.
  2. Να προσδιορίζεται η περιοχή λύσεων ενός συστήματος γραμμικών ανισώσεων, οι κορυφές της και το αν είναι φραγμένη ή μη φραγμένη, και να αιτιολογείται η κυρτότητά της.
  3. Να περιγράφονται με ανισότητες περιοχές που οριοθετούνται από ευθείες και κωνικές τομές, και να παριστάνονται οι περιοχές που περιγράφονται έτσι.
  4. Να διατυπώνονται και να λύνονται προβλήματα γραμμικού προγραμματισμού με δύο μεταβλητές με το θεώρημα των κορυφών και τις ευθείες στάθμης, διακρίνοντας τη μοναδική βέλτιστη λύση, τις πολλαπλές βέλτιστες λύσεις και την απουσία βέλτιστης λύσης.

Τα ημιεπίπεδα

Στο μάθημα για την εξίσωση της ευθείας είδαμε ότι κάθε ευθεία είναι το σύνολο των σημείων που ικανοποιούν μια εξίσωση Ax+By+C=0Ax + By + C = 0, όπου τα AA και BB δεν είναι και τα δύο μηδέν: αν B≠0B \neq 0, λύνοντας την εξίσωση παίρνουμε y=−ABx−CBy = -\frac{A}{B}x - \frac{C}{B}, ευθεία με κλίση −AB-\frac{A}{B}· αν B=0B = 0, η εξίσωση ανάγεται στην x=−CAx = -\frac{C}{A}, κατακόρυφη ευθεία. Αν αντί για την ισότητα ζητηθεί μια ανισότητα, το σύνολο λύσεων παύει να είναι καμπύλη και γίνεται περιοχή. Στο μάθημα για τις εξισώσεις και τις ανισώσεις πρώτου βαθμού, μια γραμμική ανίσωση με έναν άγνωστο είχε ως λύση ένα διάστημα της πραγματικής ευθείας· με δύο αγνώστους, η λύση είναι ένα ημιεπίπεδο.

Έστω rr μια μη κατακόρυφη ευθεία και έστω P=(x0,y0)P = (x_0, y_0) ένα σημείο. Θα λέμε ότι το PP βρίσκεται πάνω από την rr αν η y0y_0 είναι μεγαλύτερη από την τεταγμένη του σημείου της rr με τετμημένη x0x_0, και κάτω από αυτήν αν είναι μικρότερη. Αν η rr είναι κατακόρυφη, μιλάμε με τον ίδιο τρόπο για τα σημεία που βρίσκονται δεξιά και αριστερά της. Καθένα από αυτά τα δύο σύνολα είναι ένα ανοικτό ημιεπίπεδο με σύνορο την rr· αν του προστεθεί η ευθεία, είναι ένα κλειστό ημιεπίπεδο.

ΘεώρημαΤα ημιεπίπεδα

Έστω rr η ευθεία Ax+By+C=0Ax + By + C = 0, όπου τα AA και BB δεν είναι και τα δύο μηδέν, και έστω E(x,y)=Ax+By+CE(x, y) = Ax + By + C. Η παράσταση EE έχει σταθερό πρόσημο σε κάθε πλευρά της rr: είναι θετική σε όλα τα σημεία του ενός από τα δύο ανοικτά ημιεπίπεδα και αρνητική σε όλα τα σημεία του άλλου. Ακριβέστερα, αν B>0B > 0, είναι θετική πάνω από την rr και αρνητική κάτω από αυτήν· αν B<0B < 0, αντίστροφα· και αν B=0B = 0, είναι θετική δεξιά της rr όταν A>0A > 0, και αριστερά της όταν A<0A < 0.

Απόδειξη

  1. Ax0+By1+C=0\dato{q}{A x_0 + B y_1 + C = 0}

    Έστω P=(x0,y0)P = (x_0, y_0) ένα σημείο που δεν ανήκει στην rr, και ας υποθέσουμε πρώτα ότι B≠0B \neq 0. Η κατακόρυφη ευθεία που διέρχεται από το PP τέμνει την rr σε ένα μοναδικό σημείο Q=(x0,y1)Q = (x_0, y_1), του οποίου η τεταγμένη προκύπτει αν λύσουμε ως προς yy την εξίσωση της rr· το σημείο QQ ικανοποιεί αυτή την εξίσωση.

  2. E(x0,y0)=(Ax0+By0+C)−(Ax0+By1+C)=B⋅(y0−y1)E(x_0, y_0) = \resaltar{(A x_0 + B y_0 + C) - (A x_0 + B y_1 + C)} = \dato{dif}{\resaltar{B \cdot (y_0 - y_1)}}

    Αφαιρούμε αυτό το μηδέν από την τιμή της EE στο PP: οι όροι με x0x_0 και οι σταθεροί όροι απαλείφονται, και μένει ένα γινόμενο.

  3. B>0→(E(x0,y0)>0↔y0>y1)B > 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow y_0 > y_1 \right)

    Αν B>0B > 0, σύμφωνα με τον κανόνα των προσήμων που μελετήθηκε στο μάθημα για τους πίνακες προσήμων και τις ανισώσεις, το γινόμενο έχει το πρόσημο της y0−y1y_0 - y_1: είναι θετικό όταν το PP βρίσκεται πάνω από την rr και αρνητικό όταν βρίσκεται κάτω από αυτήν.

  4. B<0→(E(x0,y0)>0↔y0<y1)B < 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow y_0 < y_1 \right)

    Αν B<0B < 0, το γινόμενο έχει το αντίθετο πρόσημο από εκείνο της y0−y1y_0 - y_1: η παράσταση είναι αρνητική πάνω από την rr και θετική κάτω από αυτήν.

  5. E(x0,y0)=(Ax0+C)−(Ax1+C)=A⋅(x0−x1)E(x_0, y_0) = \resaltar{(A x_0 + C) - (A x_1 + C)} = \resaltar{A \cdot (x_0 - x_1)}

    Αν B=0B = 0, τότε A≠0A \neq 0 και η rr είναι η κατακόρυφη ευθεία x=x1x = x_1, με x1=−CAx_1 = -\frac{C}{A}. Επαναλαμβάνουμε τον υπολογισμό με το σημείο της rr που έχει την τεταγμένη του PP.

  6. A>0→(E(x0,y0)>0↔x0>x1)A > 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow x_0 > x_1 \right)

    Αν A>0A > 0, η παράσταση είναι θετική ακριβώς όταν x0>x1x_0 > x_1, δηλαδή δεξιά της rr· αν A<0A < 0, αριστερά της. Σε όλες τις περιπτώσεις το πρόσημο της EE σε ένα σημείο εξαρτάται μόνο από την πλευρά της rr στην οποία βρίσκεται το σημείο.

Το θεώρημα λέει περισσότερα από όσα χρησιμοποιούνται στην πράξη: δεν χρειάζεται να θυμόμαστε ποιο πρόσημο αντιστοιχεί σε κάθε πλευρά, γιατί αρκεί να γνωρίζουμε το πρόσημο της EE σε ένα μόνο σημείο μιας πλευράς για να το γνωρίζουμε σε όλα. Αυτή είναι η μέθοδος του σημείου ελέγχου.

Για να παραστήσουμε μια ανίσωση Ax+By+C>0Ax + By + C > 0, ή με <<, ≥\ge ή ≤\le, χαράσσουμε την ευθεία Ax+By+C=0Ax + By + C = 0 και υπολογίζουμε την τιμή της παράστασης σε ένα σημείο ελέγχου που δεν ανήκει σε αυτήν, συνήθως την αρχή των αξόνων. Αν το σημείο ικανοποιεί την ανίσωση, το σύνολο λύσεων είναι το ημιεπίπεδο που το περιέχει· αν δεν την ικανοποιεί, είναι το άλλο. Αν η ανισότητα είναι αυστηρή, η ευθεία δεν ανήκει στο σύνολο λύσεων και σχεδιάζεται διακεκομμένη· αν δεν είναι, ανήκει σε αυτό και σχεδιάζεται συνεχής.
ΠαράδειγμαΈνα ημιεπίπεδο με το σημείο ελέγχου

Να παρασταθεί το σύνολο λύσεων της ανίσωσης 2x−3y+6>02x - 3y + 6 > 0.

Απόδειξη

  1. 2x−3y+6=0,(0,2),(−3,0)2x - 3y + 6 = 0, \quad (0, 2), \quad (-3, 0)

    Χαράσσουμε την ευθεία-σύνορο από τα σημεία τομής της με τους άξονες: με x=0x = 0 παίρνουμε y=2y = 2, και με y=0y = 0, x=−3x = -3.

  2. 2⋅0−3⋅0+6=6>02 \cdot 0 - 3 \cdot 0 + 6 = \resaltar{6} > 0

    Η αρχή των αξόνων δεν ανήκει στην ευθεία. Υπολογίζουμε σε αυτήν την τιμή της παράστασης: η τιμή είναι θετική, οπότε η αρχή ικανοποιεί την ανίσωση.

  3. 2x−3y+6>0↔y<23x+22x - 3y + 6 > 0 \leftrightarrow \resaltar{y < \frac{2}{3}x + 2}

    Το σύνολο λύσεων είναι το ημιεπίπεδο που περιέχει την αρχή των αξόνων. Το θεώρημα το επιβεβαιώνει: αφού B=−3<0B = -3 < 0, η παράσταση είναι θετική κάτω από την ευθεία.

  4. 2⋅(−3)−3⋅0+6=02 \cdot (-3) - 3 \cdot 0 + 6 = \resaltar{0}

    Η ανισότητα είναι αυστηρή: τα σημεία της ευθείας, όπως το (−3,0)(-3, 0), μηδενίζουν την παράσταση και δεν την ικανοποιούν. Η ευθεία-σύνορο εξαιρείται και σχεδιάζεται διακεκομμένη.