Πρέπει να λύσω ένα πρόβλημα γραμμικού προγραμματισμού με χρήση του αυξητικού αλγορίθμου…
- User
Πρέπει να λύσω ένα πρόβλημα γραμμικού προγραμματισμού με χρήση του αυξητικού αλγορίθμου Seidel. Ο αλγόριθμος seidel έχει τις εξής προϋποθέσεις:
- Πρόβλημα της μορφής: minf(x) H_i(x) ≤ 0, i = 1, 2, . . . , n.
- Υπάρχει μοναδική βέλτιστη λύση, εφόσον το πρόβλημα είναι εφικτό.
- Το αρχικό πρόβλημα και όλα τα υποπροβλήματα στη διάρκεια του αλγορίθμουείναι φραγμένα. Ο ψευδοκώδικας του αλγορίθμου είναι ο εξής: Είσοδος:
- Περιορισμοί - Γραμμικές ανισότητες (μη-αυστηρές) H_1, . . . , H_n
- Αντικειμενική συνάρτηση ελαχιστοποίησης f(x) (γραμμική) (Περιέχουν d μεταβλητές - Ικανοποιούν τις υποθέσεις φραγμένης εφικτής περιοχής & μοναδικής λύσης (αν υπάρχει) ). ΄Εξοδος: Σημείο x∗ ∈ R^d που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H_1, . . . , H_n , εφόσον το πρόβλημα είναι εφικτό, αλλιώς τυπώνει “Ανέφικτο”.
- Αρχικοποίηση: Βρες τη βέλτιστη κορυφή x∗{d+1} ∈ C{d+1}. Αν C_{d+1} = ⊘, τερμάτισε και τύπωσε “Ανέφικτο”.
- Για i = d + 2, . . . , n, υπολόγισε το σημείο x∗i ∈ C_i, διακρίνοντας 2 περιπτώσεις. Σε κάθε περίπτωση, αν C_i = ⊘, τερμάτισε και τύπωσε “Ανέφικτο”. Αν το x∗{i−1} ικανοποιεί τον περιορισμό H_i(x) τότε x∗_{i−1} = x∗_i. Αλλιώς υπολόγισε το x∗_i ως λύση ενός νέου προβλήματος ελαχιστοποίησης με περιορισμούς H′1, . . . , H′{i−1} και d − 1 μεταβλητές. Κάθε H′_jαντιστοιχεί στη σύζευξη του H_j και του H_i = 0. Μπορείς να γράψεις τον αλγόριθμο αυτόν βήμα προς βήμα σε python?
- Assistant
Ο αυξητικός αλγόριθμος Seidel για τη λύση προβλημάτων γραμμικού προγραμματισμού μπορεί να υλοποιηθεί σε Python, κάνοντας χρήση βιβλιοθηκών όπως NumPy για γραμμική άλγεβρα και scipy.optimize για γραμμικό προγραμματισμό. Ακολουθεί μια υλοποίηση βήμα προς βήμα του αλγορίθμου:
import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην αΤx ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) if not is_feasible(A, b): return "Ανέφικτο" res = linprog(c=f, A_ub=A, b_ub=b, bounds=(None, None), method='highs') if not res.success: return "Ανέφικτο" x_star = res.x for i in range(d + 1, n): H_i = H[i] if np.dot(H_i[0], x_star) <= H_i[1]: continue A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) for j in range(d): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(None, None), method='highs') if res.success and np.dot(H_i[0], res.x) <= H_i[1]: x_star = res.x break else: return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([1, 1]), 5), (np.array([2, 1]), 6), (np.array([1, 0]), 3), (np.array([0, 1]), 4), ] f = np.array([1, 1]) result = seidel_algorithm(H, f) print(result)Σημείωση:
- Αυτή η υλοποίηση υποθέτει ότι οι περιορισμοί και η αντικειμενική συνάρτηση είναι έγκυροι και σωστά δομημένοι.
- Η βιβλιοθήκη
scipy.optimize.linprogχρησιμοποιείται για να λύσει τα γραμμικά προγράμματα, ελέγχοντας την εφικτότητα των περιορισμών και βρίσκοντας τη λύση ελαχιστοποίησης. - Η μέθοδος
highsείναι μία από τις υποστηριζόμενες μεθόδους τουlinprogκαι είναι συνήθως αποτελεσματική για μεγάλα συστήματα ανισοτήτων.
- User
if np.dot(H_i[0], x_star) <= H_i[1]: File "<array_function internals>", line 200, in dot TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'
- Assistant
Ο τύπος σφάλματος που αναφέρθηκε υποδεικνύει ότι κάποια τιμή είναι
Noneόπου δεν θα έπρεπε. Αυτό μπορεί να προκύψει αν κάποιο στοιχείο του πίνακαHδεν έχει την αναμενόμενη μορφή ή αν η λύση από τηνlinprogπεριέχει μη αναμενόμενες τιμές.Για παράδειγμα, θα πρέπει να διασφαλίσουμε ότι όλες οι τιμές του πίνακα
Hείναι σωστές και ότι η λύση από τοlinprogεπιστρέφει ένα έγκυρο διάνυσμα. Παρακάτω είναι μια ενημερωμένη υλοποίηση που περιλαμβάνει επιπλέον έλεγχο για να διασφαλίσει ότι όλα τα δεδομένα και οι λύσεις είναι έγκυρες.import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην αΤx ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) feasible, x_star = is_feasible(A, b) if not feasible: return "Ανέφικτο" res = linprog(c=f, A_ub=A, b_ub=b, bounds=(None, None), method='highs') if not res.success: return "Ανέφικτο" x_star = res.x for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: x_star = candidate found_feasible = True break if not found_feasible: return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([1, 1]), 5), (np.array([2, 1]), 6), (np.array([1, 0]), 3), (np.array([0, 1]), 4), ] f = np.array([1, 1]) result = seidel_algorithm(H, f) print(result)Αλλαγές και έλεγχοι:
- Ενημερώθηκε η συνάρτηση
is_feasibleώστε να επιστρέφει επίσης την λύσηxαπό τοlinprog. - Προστέθηκε έλεγχος για την επιστροφή λύσης
x_starαπό τοlinprogπριν χρησιμοποιηθεί. - Εξασφαλίστηκε ότι σε κάθε βήμα το πρόγραμμα ελέγχει αν είναι δυνατή η λύση.
- Το ανέφικτο αποτέλεσμα ελέγχεται ξεκάθαρα αν δεν μπορεί να βρεθεί καμία εφικτή λύση.
- Ενημερώθηκε η συνάρτηση
- User
Αρχική λύση για τους πρώτους d + 1 περιορισμούς
A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(None, None), method="highs") x_star = res.x if x_star == None: return Noneεπιστρέφει None
- Assistant
Κατά την αναζήτηση της αρχικής λύσης χρησιμοποιώντας τους πρώτους (d+1) περιορισμούς, είναι σημαντικό να επαληθεύουμε την επιτυχία της λύσης του γραμμικού προγραμματισμού πριν συνεχίσουμε. Αν η λύση δεν είναι εφικτή, θα πρέπει να επιστρέφουμε "Ανέφικτο".
Στην ακόλουθη ενημερωμένη υλοποίηση του αλγορίθμου, επιβεβαιώνουμε σαφώς την επιτυχία της κλήσης του
linprogκαι χειριζόμαστε όλα τα πιθανά σφάλματα:import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην αΤx ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(None, None), method="highs") if not res.success: return "Ανέφικτο" x_star = res.x # Βασική ανακύκλωση του αυξητικού αλγορίθμου for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(None, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([1, 1]), 5), (np.array([2, 1]), 6), (np.array([1, 0]), 3), (np.array([0, 1]), 4), ] f = np.array([1, 1]) result = seidel_algorithm(H, f) print(result)Εξήγηση των αλλαγών:
- Αφαιρέθηκε το ανεκγέγραφο "if x_star == None: return None" επειδή το
res.successέλεγχε την επιτυχία και όχι το ίδιο το διάνυσμα λύσης. - Επιστρέφει "Ανέφικτο" εάν η αρχική λύση για τους πρώτους
d+1περιορισμούς δεν είναι εφικτή. - Σε κάθε βήμα ελέγχεται η εφικτότητα της νέας λύσης πριν γίνει αποδεκτή.
Δοκιμή: Ο παραπάνω κώδικας δοκιμάζεται με ένα σύνολο περιορισμών
Hκαι μια αντικειμενική συνάρτησηf. Το αποτέλεσμα εκτυπώνεται και πρέπει να είναι είτε μια έγκυρη λύση είτε το μήνυμα "Ανέφικτο" εάν δεν υπάρχουν εφικτές λύσεις. - Αφαιρέθηκε το ανεκγέγραφο "if x_star == None: return None" επειδή το
- User
επιστρέφει "Ανέφικτο"
- Assistant
Είναι σημαντικό να επιβεβαιώσουμε ότι τα δεδομένα εισόδου δεν παράγουν μια ανέφικτη περιοχή εφικτών λύσεων. Επίσης, μερικές φορές το πρόβλημα μπορεί να είναι αριθμητικά ασταθές ή να υπάρχουν προβλήματα με τη μορφή των περιορισμών.
Παρακάτω είναι μια ενημερωμένη και πιο λεπτομερής υλοποίηση του αλγορίθμου με επιπλέον εκτυπώσεις για να βοηθήσουμε στην αποσφαλμάτωση του χρόνου εκτέλεσης:
import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην αΤx ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(None, None), method="highs") if not res.success: print("Αρχική λύση ανέφικτη.") return "Ανέφικτο" x_star = res.x # Βασική ανακύκλωση του αυξητικού αλγορίθμου for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(None, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: print("Ανεύρεση ανέφικτη στο βήμα", i) return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([1, 1]), 5), (np.array([2, 1]), 6), (np.array([1, 0]), 3), (np.array([0, 1]), 4), ] f = np.array([1, 1]) result = seidel_algorithm(H, f) print(result)Εξηγήσεις τροποποιήσεων:
-
Επιπλέον ενδιάμεσες εκτυπώσεις: Προστέθηκαν εκτυπώσεις για να διαγνώσουμε πότε το σύστημα κρίνεται ανέφικτο. Αυτό βοηθά στην κατανόηση οποιωνδήποτε ζητημάτων που μπορεί να προκύψουν στη διαδικασία εύρεσης λύσης.
-
Προσεκτικός έλεγχος της πιο εφικτής λύσης έως το τρέχον βήμα: Σε κάθε βήμα ελέγχουμε αν το σύνολο των περιορισμών είναι εφικτό και αν όχι, εκτυπώνουμε που ακριβώς αποτυγχάνει η διαδικασία.
-
Προσεκτικός έλεγχος της επαναληπτικής διαδικασίας: Βεβαιωνόμαστε ότι το
x_starενημερώνεται μόνο αν υπάρχει εφικτή λύση για το τρέχον σύνολο περιορισμών.
Δοκιμή:
Βεβαιωθείτε ότι οι περιορισμοί εισαγωγής έχουν νόημα και ελέγξτε αν υπάρχει κάποια ανεπαρκής ή απρόσιτη περιοχή που προκαλεί το ανέφικτο αποτέλεσμα.
-
- User
max{−3x1 + 12x2} υπό τους περιορισμούς: x1 − 2x2 ≥ 1 2x1 − 3x2 ≥ 6 −x1 + 3x2 ≤ 0 −x1 + 6x2 ≤ 12 4x1 − 9x2 ≤ 27 x1, x2 ≥ 0. Μπορείς να το φέρεις στη μορφή minf(x) H_i(x) ≤ 0, i = 1, 2, . . . , n. και να το εφαρμόσεις στον παραπάνω αλγόριθμο;
- Assistant
Φυσικά! Ας μεταφέρουμε πρώτα το πρόβλημα στη μορφή που απαιτείται για τον αλγόριθμο:
-
Αντικειμενική συνάρτηση: Το πρόβλημα απαιτεί μεγιστοποίηση της συνάρτησης ( −3x_1 + 12x_2 ). Θα μετατρέψουμε αυτό το μέγιστο σε ελάχιστο πολλαπλασιάζοντας το κατά -1: [ \text{min} \ f(x) = 3x_1 - 12x_2 ]
-
Περιορισμοί: Πρέπει να φέρουμε όλους τους περιορισμούς στη μορφή ( \leq 0 ):
[ \begin{cases} x_1 - 2x_2 \geq 1 & \Rightarrow -x_1 + 2x_2 \leq -1 \ 2x_1 - 3x_2 \geq 6 & \Rightarrow -2x_1 + 3x_2 \leq -6 \ -x_1 + 3x_2 \leq 0 \ -x_1 + 6x_2 \leq 12 \ 4x_1 - 9x_2 \leq 27 \ x_1 \geq 0 & \Rightarrow -x_1 \leq 0 \ x_2 \geq 0 & \Rightarrow -x_2 \leq 0 \ \end{cases} ]
Τώρα τα δεδομένα μας είναι στη μορφή ( H_i(x) \leq 0 ) χρειάζονται.
Ας εφαρμόσουμε τώρα τον αλγόριθμο Seidel:
import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην α^T x ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(None, None), method="highs") if not res.success: print("Αρχική λύση ανέφικτη.") return "Ανέφικτο" x_star = res.x # Βασική ανακύκλωση του αυξητικού αλγορίθμου for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(None, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: print("Ανεύρεση ανέφικτη στο βήμα", i) return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ] f = np.array([3, -12]) result = seidel_algorithm(H, f) print("Optimal solution:", result)Σημεία που πρέπει να σημειωθούν:
- Το πρόβλημα αντικειμενικής συνάρτησης έχει αντιστραφεί έτσι ώστε να γίνει ελαχιστοποίηση. Η νέα αντικειμενική συνάρτηση είναι (3x_1 - 12x_2).
- Όλοι οι περιορισμοί έχουν μετατραπεί στη μορφή (H_i(x) \leq 0).
- Το πρόβλημα δίνεται στον αλγόριθμο Seidel για να αποδοθεί η βέλτιστη λύση.
Με τη χρήση του παραπάνω κώδικα, μπορείτε να υπολογίσετε το σημείο που ελαχιστοποιεί την αντικειμενική συνάρτηση και ικανοποιεί όλους τους δοθέντες περιορισμούς.
-
- User
αντί για (12,4) που είναι το βέλτιστο, επιστρέφει "Ανέφικτο"
- Assistant
Το πρόβλημα μπορεί να οφείλεται στην εσφαλμένη διαμόρφωση των περιορισμών ή στην αριθμητική σταθερότητα της μεθόδου. Ας επανεξετάσουμε τους περιορισμούς και ας διασφαλίσουμε ότι η προσέγγιση μας είναι σωστή.
Παρακάτω επαναλαμβάνω την υλοποίηση με πιο προσεκτική διαχείριση των περιορισμών και επιπλέον εκτυπώσεων για διαγνωστικούς σκοπούς:
import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην α^T x ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(0, None), method="highs") if not res.success: print("Αρχική λύση ανέφικτη.") return "Ανέφικτο" x_star = res.x # Βασική ανακύκλωση του αυξητικού αλγορίθμου for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(0, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: print("Ανεύρεση ανέφικτη στο βήμα", i) return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ] f = np.array([3, -12]) result = seidel_algorithm(H, f) print("Optimal solution:", result)Ας εξετάσουμε με περισσότερη λεπτομέρεια τα επιμέρους βήματα:
Διευκρινίσεις σχετικά με τον κώδικα
-
Περιορισμοί στη μορφή
H_i(x) ≤ 0: Όλες οι ανισότητές έχουν μορφοποιηθεί έτσι ώστε οι περιορισμοί να είναι της μορφής ( \alpha^T x ≤ c ). -
Έλεγχος εφικτότητας πριν από την αρχική λύση: Για την αρχική ομάδα
d + 1περιορισμών, ελέγχουμε αν η λύση είναι εφικτή σύμφωνα με τις απαιτήσεις μας. -
Επανειλημμένη αναθεώρηση περιορισμών: Κατά την αναπτυξιακή διαδικασία, αναθεωρούμε συνεχώς τη βάση περιορισμών προκειμένου να διατηρήσουμε μια εφικτή λύση.
-
Εντοπισμός και εκτύπωση βημάτων: Εκτυπώσεις κατά την εφανιζόμενη αναπτυξιακή διαδικασία βοηθούν στη διάγνωση πιθανοτήτων σφαλμάτων.
Αν συνεχίζετε να αντιμετωπίζετε προβλήματα, μπορεί να είναι χρήσιμο να προσομοιώσετε βήμα-βήμα τον αλγόριθμο με έναν απλούστερο παράδειγμα για να εντοπίσετε πού παρουσιάζεται η δυσκολία.
-
- User
“Optimal solution:” “Ανέφικτο”
- Assistant
Ευχαριστώ για την ενημέρωση. Το γεγονός ότι ο αλγόριθμος επιστρέφει συνεχώς "Ανέφικτο" μπορεί να προκαλείται είτε από ένα πρόβλημα στη διαμόρφωση του πίνακα περιορισμών, είτε από αριθμητικά θέματα στο
linprog.Για να βρούμε τη ρίζα του προβλήματος, θα αναλύσω το σύνολο περιορισμών και τη χρήση του
linprogβήμα προς βήμα. Αρχικά, ας εξετάσουμε ένα πιο λεπτομερές παράδειγμα για την κατανόηση του τι πραγματικά συμβαίνει στο περιβάλλον τουlinprog.import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): """ Εφαρμογή του αυξητικού αλγορίθμου Seidel για προβλήματα γραμμικού προγραμματισμού. Παράμετροι: H: Λίστα από γραμμικές ανισότητες της μορφής (α, b) όπου α είναι ο συντελεστής και b είναι η σταθερά στην α^T x ≤ b. f: Διάνυσμα συντελεστών της γραμμικής αντικειμενικής συνάρτησης ελαχιστοποίησης. Επιστρέφει: Λύση x που ελαχιστοποιεί την f(x) και ικανοποιεί τους περιορισμούς H, ή μήνυμα "Ανέφικτο". """ def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(0, None), method="highs") if not res.success: print("Αρχική λύση ανέφικτη.") return "Ανέφικτο" x_star = res.x print(f"Αρχική λύση: {x_star}") # Βασική ανακύκλωση του αυξητικού αλγορίθμου for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i print(f"Έλεγχος περιορισμού {i}: {H_i}") if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) print(f"Subset περιορισμοί {j}: {subset_constraints}, {subset_b}, εφικτό: {feasible}") if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(0, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: print("Ανεύρεση ανέφικτη στο βήμα", i) return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ] f = np.array([3, -12]) result = seidel_algorithm(H, f) print("Optimal solution:", result)Εξήγηση των παραπάνω εκτυπώσεων:
- Η αρχική λύση εκτυπώνεται ώστε να επιβεβαιώσουμε ότι το πρώτο σύστημα περιορισμών είναι εφικτό.
- Για κάθε περιορισμό, εκτυπώνεται η αναλυτική εξέταση των προσωρινών λύσεων.
- Αναλύονται διεξοδικά τα υποσύνολα περιορισμών για οποιαδήποτε ασυμφωνία.
Ας δούμε τα αποτελέσματα αυτών των εκτυπώσεων για να κατανοήσουμε ποια σημεία του κώδικα πρέπει να εξεταστούν περαιτέρω. Εάν το πρόβλημα εξακολουθεί να εμφανίζεται, μπορεί να προδιαγράψουμε διαφορετικό τρόπο προσέγγισης ή να εξετάσουμε εναλλακτικές αριθμητικές μεθόδους.
- User
import numpy as np from scipy.optimize import linprog
def seidel_algorithm(H, f): def is_feasible(A, b): # Έλεγχος αν το σύστημα γραμμικών ανισοτήτων Ax ≤ b είναι εφικτό. res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method="highs") return res.success, res.x
d = len(f) n = len(H) if n < d: raise ValueError("“Number of constraints must be at least the number of variables.”") # Αρχική λύση για τους πρώτους d + 1 περιορισμούς A = np.array([H[i][0] for i in range(d+1)]) b = np.array([H[i][1] for i in range(d+1)]) res = linprog(c=f, A_ub=A, b_ub=b, bounds=(0, None), method="highs") if not res.success: return "“Ανέφικτο”" x_star = res.x # Βασική ανακύκλωση του αυξητικού αλγορίθμου for i in range(d + 1, n): H_i = H[i] # Έλεγχος εάν η λύση x_star ικανοποιεί τον περιορισμό H_i if np.dot(H_i[0], x_star) <= H_i[1]: continue # Δημιουργία νέων περιορισμών A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(0, None), method="highs") if res.success: x_star = res.x found_feasible = True break if not found_feasible: return "Ανέφικτο" return x_starΠαράδειγμα
H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ]
f = np.array([3, -12])
result = seidel_algorithm(H, f) print("“Optimal solution:”", result) Μπορούμε να βελτιώσουμε αυτόν τον κώδικα για να μη έχει ως αποτέλεσμα "Ανέφικτο" συνεχώς;
- Assistant
Ας βελτιώσουμε την υλοποίηση προσθέτοντας επιπλέον διαγνωστικές εκτυπώσεις και αλλαγές στον τρόπο προσέγγισης των υποπροβλημάτων, ώστε να διασφαλίσουμε ότι δεν υπάρχουν αριθμητικές ασταθείς καταστάσεις. Θα ελέγξουμε συγκεκριμένα τα διανύσματα των περιορισμών και τα υποπροβλήματα κατά τη διάρκεια της επαναληπτικής διαδικασίας.
Επίσης, θα χρησιμοποιήσουμε
bounds=(0, None)για να διασφαλίσουμε ότι οι παρακάτω μεταβλητές είναι μη αρνητικές.import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): def is_feasible(A, b): res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχικό υποσύνολο περιορισμών A = np.array([H[i][0] for i in range(d + 1)]) b = np.array([H[i][1] for i in range(d + 1)]) # Αρχική λύση res = linprog(c=f, A_ub=A, b_ub=b, bounds=(0, None), method="highs") if not res.success: return "Ανέφικτο" x_star = res.x # Επαναληπτική διαδικασία for i in range(d + 1, n): H_i = H[i] if np.dot(H_i[0], x_star) <= H_i[1]: continue A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(0, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ] f = np.array([3, -12]) result = seidel_algorithm(H, f) print("Optimal solution:", result)Ας προσθέσουμε διαγνωστικές εκτυπώσεις για καλύτερη κατανόηση:
import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): def is_feasible(A, b): res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχικό υποσύνολο περιορισμών A = np.array([H[i][0] for i in range(d + 1)]) b = np.array([H[i][1] for i in range(d + 1)]) # Αρχική λύση res = linprog(c=f, A_ub=A, b_ub=b, bounds=(0, None), method="highs") if not res.success: print("Initial infeasibility") return "Ανέφικτο" x_star = res.x print(f"Initial feasible solution: {x_star}") # Επαναληπτική διαδικασία for i in range(d + 1, n): H_i = H[i] if np.dot(H_i[0], x_star) <= H_i[1]: continue A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) print(f"Subset {j}: Constraints: {subset_constraints}, Bounds: {subset_b}, Feasible: {feasible}") if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(0, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: print(f"Infeasibility found at constraint {i}") return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ] f = np.array([3, -12]) result = seidel_algorithm(H, f) print("Optimal solution:", result)Με αυτές τις εκτυπώσεις μπορείτε να παρακολουθήσετε τα αποτελέσματα κάθε βήματος του αλγορίθμου Seidel και να εντοπίσετε ακριβώς πού και γιατί αποτυγχάνει.
- User
“Initial infeasibility” “Optimal solution:” “Ανέφικτο”
- Assistant
Αν αντιμετωπίζουμε συνεχή προβλήματα με την "Αρχική λύση ανέφικτη" αυτό σημαίνει είτε ότι οι αρχικοί περιορισμοί δεν δημιουργούν ένα εφικτό σύνολο, είτε μπορεί να υπάρχει κάποιο αριθμητικό πρόβλημα.
Για να επιβεβαιώσουμε τη λογική του προβλήματος, μπορούμε να λύσουμε το πρόβλημα χρησιμοποιώντας το κλασικό πεδίο γραμμικού προγραμματισμού που δεν απαιτεί τις ίδιες συνθήκες.
Ας ελέγξουμε πρώτα αν το πρόβλημα είναι εφικτό χωρίς την αυξητική προσέγγιση:
import numpy as np from scipy.optimize import linprog # Η αρχική μορφή του προβλήματος μεγιστοποίησης c = np.array([-3, 12]) # Περιορισμοί στη μορφή A_ub x <= b_ub. Θα δεχθούμε ότι όλοι οι περιορισμοί είναι ενεργοί. A_ub = np.array([ [-1, 2], [-2, 3], [-1, 3], [-1, 6], [4, -9], [-1, 0], [0, -1] ]) b_ub = np.array([-1, -6, 0, 12, 27, 0, 0]) # Όλες οι μεταβλητές είναι μη-αρνητικές bounds = [(0, None), (0, None)] # Λύση του προβλήματος result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method="highs") print("Optimal solution (direct call):", result.x if result.success else "Ανέφικτο") print("Optimal value:", -result.fun if result.success else "N/A")Αυτός ο κώδικας λύνει το ίδιο πρόβλημα χρησιμοποιώντας τη συνάρτηση
linprogαπευθείας χωρίς την αυξητική προσέγγιση.Αν το αποτέλεσμα του
linprogυποδεικνύει ότι το πρόβλημα είναι εφικτό και επιστρέφει την βέλτιστη λύση, τότε μπορούμε να ξαναδούμε πώς υλοποιείται ο αλγόριθμος Seidel.Ωστόσο, αν ο απλός τρόπος αποδεικνύει ότι το πρόβλημα είναι ανέφικτο, μπορούμε να εξετάσουμε ξανά τους περιορισμούς μας.
Αν το πρόβλημα είναι εφικτό με το
linprogΑναθεώρηση του Αλγόριθμου Seidel
Ας επανεκτιμήσουμε τον αλγόριθμο Seidel για να βεβαιωθούμε ότι είναι σωστά υλοποιημένος:
import numpy as np from scipy.optimize import linprog def seidel_algorithm(H, f): def is_feasible(A, b): res = linprog(c=np.zeros(A.shape[1]), A_ub=A, b_ub=b, method='highs') return res.success, res.x d = len(f) n = len(H) if n < d: raise ValueError("Number of constraints must be at least the number of variables.") # Αρχικό υποσύνολο περιορισμών A = np.array([H[i][0] for i in range(d + 1)]) b = np.array([H[i][1] for i in range(d + 1)]) # Αρχική λύση res = linprog(c=f, A_ub=A, b_ub=b, bounds=(0, None), method="highs") if not res.success: print("Initial infeasibility") return "Ανέφικτο" x_star = res.x print(f"Initial feasible solution: {x_star}") # Επαναληπτική διαδικασία for i in range(d + 1, n): H_i = H[i] if np.dot(H_i[0], x_star) <= H_i[1]: continue A_new = np.vstack([A, H_i[0]]) b_new = np.hstack([b, H_i[1]]) found_feasible = False for j in range(d + 1): subset_constraints = np.delete(A_new, j, 0) subset_b = np.delete(b_new, j) feasible, candidate = is_feasible(subset_constraints, subset_b) print(f"Subset {j}: Constraints: {subset_constraints}, Bounds: {subset_b}, Feasible: {feasible}") if feasible and np.dot(H_i[0], candidate) <= H_i[1]: res = linprog(c=f, A_ub=subset_constraints, b_ub=subset_b, bounds=(0, None), method='highs') if res.success: x_star = res.x found_feasible = True break if not found_feasible: print(f"Infeasibility found at constraint {i}") return "Ανέφικτο" return x_star # Παράδειγμα H = [ (np.array([-1, 2]), -1), (np.array([-2, 3]), -6), (np.array([-1, 3]), 0), (np.array([-1, 6]), 12), (np.array([4, -9]), 27), (np.array([-1, 0]), 0), (np.array([0, -1]), 0) ] f = np.array([3, -12]) result = seidel_algorithm(H, f) print("Optimal solution:", result)Βεβαιωθείτε ότι οι αρχικοί περιορισμοί και η διαδικασία εν γένει λειτουργούν όπως αναμένεται. Εάν η
linprogμπορεί να βρει μια εφικτή λύση, τότε το αυξητικό μέρος μπορεί να χρειαστεί να επανεξεταστεί ή να διορθωθεί.Εάν το πρόβλημα παραμένει, τα δεδομένα εισόδου μπορεί να χρειάζονται επιπλέον επιβεβαίωση ή αναθεώρηση.