Phương pháp biến đổi Jordan-Gauss và đơn hình trong Excel. Giải bài toán sản xuất bằng phương pháp bảng đơn giản
Phương pháp Gauss-Jordan được thiết kế để giải các hệ tuyến tính phương trình đại số(SLAU). Nó là một sửa đổi của phương pháp Gauss. Nếu phương pháp Gauss được thực hiện theo hai giai đoạn (tiến và lùi), thì phương pháp Gauss-Jordan cho phép bạn giải hệ thống trong một giai đoạn. Chi tiết và ứng dụng trực tiếp của phương pháp Gauss-Jordan được mô tả trong các ví dụ.
Trong tất cả các ví dụ, $A$ biểu thị ma trận hệ thống, $\widetilde(A)$ biểu thị ma trận hệ thống mở rộng. Bạn có thể đọc về dạng ma trận ghi SLAE.
Ví dụ số 1
Giải SLAE $ \left\( \begin(aligned) & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end(aligned ) \right.$ bằng phương pháp Gauss-Jordan.
Hãy chuyển từ ma trận cuối cùng mà chúng tôi nhận được sang hệ thống:
$$ \left\( \begin(căn chỉnh) & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2; \\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1.
Đơn giản hóa hệ thống kết quả, chúng ta có:
$$ \left\( \begin(aligned) & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end(aligned) \right. $$
Giải pháp hoàn chỉnh không có lời giải thích nó trông như thế này:
Mặc dù phương pháp chọn phần tử phân giải này khá chấp nhận được nhưng tốt hơn là chọn các phần tử đường chéo của ma trận hệ thống làm phần tử phân giải. Chúng ta sẽ xem xét phương pháp này dưới đây.
Lựa chọn các phần tử phân giải trên đường chéo chính của ma trận hệ thống.
Vì phương pháp giải này hoàn toàn giống với phương pháp trước (ngoại trừ việc lựa chọn các yếu tố kích hoạt), chúng tôi sẽ bỏ qua phần giải thích chi tiết. Nguyên tắc chọn phần tử kích hoạt rất đơn giản: ở cột đầu tiên, chúng tôi lấy phần tử của hàng đầu tiên, ở cột thứ hai, chúng tôi lấy phần tử của hàng thứ hai, ở cột thứ ba, chúng tôi lấy phần tử của hàng thứ ba, v.v. TRÊN.
Bước đầu tiên
Trong cột đầu tiên, chọn phần tử của hàng đầu tiên, tức là chúng ta có phần tử 4 làm phần tử giải quyết. Tôi hiểu rằng chọn số 2 có vẻ thích hợp hơn, vì số này vẫn nhỏ hơn 4. Để số 2 ở cột đầu tiên chuyển về vị trí đầu tiên, chúng ta hãy hoán đổi phần tử đầu tiên. và hàng thứ hai:
$$ \left(\begin(array) (ccc|c) 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end(array) \ right)\rightarrow \left(\begin(array) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(mảng ) \right)$$
Vì vậy, phần tử kích hoạt được biểu thị bằng số 2. Tương tự như trước, chia hàng đầu tiên cho 2, sau đó đặt lại các phần tử của cột đầu tiên về 0:
$$ \left(\begin(array) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(array) \ right) \begin(array) (l) I:2 \\\phantom(0) \\ \phantom(0) \end(array) \rightarrow \left(\begin(array) (ccc|c) 1 & - 2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end(array) \right) \begin(array) (l) \phantom(0 ) \\ II-4\cdot I\\ III+3\cdot I \end(array) \rightarrow \left(\begin(array) (ccc|c) 1 & -2& 5/2 & -13/2\ \0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end(mảng) \right). $$
Bước thứ hai
Bước thứ hai yêu cầu loại bỏ các phần tử của cột thứ hai. Chúng tôi chọn phần tử của dòng thứ hai làm phần tử phân giải, tức là. 1. Yếu tố kích hoạt đã có bằng một, vì vậy chúng tôi sẽ không trao đổi bất kỳ dòng nào. Nhân tiện, nếu chúng ta muốn hoán đổi các hàng, chúng ta sẽ không chạm vào hàng đầu tiên vì nó đã được sử dụng ở bước đầu tiên. Nhưng dòng thứ hai và thứ ba có thể dễ dàng hoán đổi cho nhau. Tuy nhiên, tôi nhắc lại, trong tình huống này không cần phải hoán đổi các dòng vì phần tử phân giải đã tối ưu - nó bằng một.
$$ \left(\begin(array) (ccc|c) 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/ 2 \end(array) \right) \begin(array) (l) I+2\cdot II \\ \phantom(0)\\ III-5\cdot II \end(array) \rightarrow \left(\begin (mảng) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end(mảng) \Phải). $$
Bước thứ hai đã hoàn thành. Hãy chuyển sang bước thứ ba.
Bước thứ ba
Bước thứ ba yêu cầu loại bỏ các phần tử của cột thứ ba. Là phần tử phân giải, chúng tôi chọn phần tử của dòng thứ ba, tức là. 37/2. Hãy chia các phần tử của hàng thứ ba cho 37/2 (để phần tử phân giải trở thành bằng 1), sau đó đặt lại các phần tử tương ứng của cột thứ ba về 0:
$$ \left(\begin(array) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37 /2 \end(array) \right) \begin(array) (l) \phantom(0)\\ \phantom(0)\\ III:\frac(37)(2) \end(array) \rightarrow \ left(\begin(array) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end(array) \right) \begin(array) (l) I+2\cdot III\\II+3/2\cdot III\\ \phantom(0) \end(array) \rightarrow \left(\begin(array) ( ccc|c) 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end(array) \right). $$
Câu trả lời nhận được: $x_1=-2$, $x_2=1$, $x_3=-1$. Giải pháp hoàn chỉnh không có lời giải thích trông như thế này:
Tất cả các ví dụ khác trên trang này sẽ được giải chính xác theo cách thứ hai: chúng ta sẽ chọn các phần tử đường chéo của ma trận hệ thống làm phần tử giải.
Trả lời: $x_1=-2$, $x_2=1$, $x_3=-1$.
Ví dụ số 2
Giải SLAE $ \left\( \begin(aligned) & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27; \\ & -3x_1-2x_2-2x_3-10x_4=1. \end(aligned) \right.$ bằng phương pháp Gauss-Jordan.
Hãy viết ma trận mở rộng của hệ thống này: $\widetilde(A)=\left(\begin(array) (cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end(array) \right)$.
Chúng ta sẽ chọn các phần tử đường chéo của ma trận hệ thống làm phần tử phân giải: ở bước đầu tiên chúng ta sẽ lấy phần tử của hàng đầu tiên, ở bước thứ hai chúng ta sẽ lấy phần tử của hàng thứ hai, v.v.
Bước đầu tiên
Chúng ta cần đặt lại các phần tử tương ứng của cột đầu tiên. Hãy lấy phần tử của dòng đầu tiên làm phần tử phân giải, tức là 3. Theo đó, dòng đầu tiên sẽ phải chia cho 3 để phần tử phân giải bằng một. Và sau đó đặt lại tất cả các thành phần của cột đầu tiên, ngoại trừ phần cho phép:
$$ \left(\begin(array)(cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\ \ -3 & -2 & -2 & -10 & 1\end(array)\right) \begin(array) (l) I:3\\ \phantom(0)\\\phantom(0)\\\ phantom(0)\end(array) \rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end(array)\right) \begin(array) (l) \phantom(0) \\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end(array) \rightarrow\\ \rightarrow\left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & - 5 & -5\end(mảng)\right). $$
Bước thứ hai
Chúng tôi tiến hành zeroing các phần tử tương ứng của cột thứ hai. Chúng tôi đã đồng ý lấy phần tử của dòng thứ hai làm phần tử phân giải, nhưng chúng tôi không thể thực hiện điều này vì phần tử bắt buộc bằng 0. Kết luận: chúng ta sẽ trao đổi các dòng. Không thể chạm vào dòng đầu tiên vì nó đã được sử dụng ở bước đầu tiên. Sự lựa chọn không phong phú: hoặc chúng ta hoán đổi dòng thứ hai và thứ ba, hoặc chúng ta hoán đổi dòng thứ tư và thứ hai. Vì dòng thứ tư chứa (-1) nên hãy để dòng thứ tư tham gia “trao đổi”. Vì vậy, trao đổi dòng thứ hai và thứ tư:
$$ \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end(mảng)\right)\rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4 \end(mảng)\right) $$
Bây giờ mọi thứ đều bình thường: phần tử độ phân giải bằng (-1). Nhân tiện, việc thay đổi vị trí của các đường là không thể, nhưng chúng ta sẽ thảo luận vấn đề này trong ví dụ số 3 tiếp theo. Hiện tại, chúng tôi chia hàng thứ hai cho (-1), sau đó đặt lại các phần tử của cột thứ hai. Xin lưu ý rằng trong cột thứ hai, phần tử nằm ở hàng thứ tư đã bằng 0 nên chúng ta sẽ không chạm vào hàng thứ tư.
$$ \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(array)\right) \begin(array) (l) \phantom(0)\\II:(-1) \\\phantom(0)\\\phantom(0)\end(array) \rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(mảng)\right) \begin(mảng) (l) I-1/3\cdot II\\ \phantom(0) \\III-2\cdot II\\\phantom(0)\end(array) \rightarrow\\ \rightarrow\left(\begin( mảng)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(mảng)\right). $$
Bước thứ ba
Hãy bắt đầu xử lý cột thứ ba. Chúng tôi đã đồng ý lấy các phần tử đường chéo của ma trận hệ thống làm phần tử phân giải. Đối với bước thứ ba, điều này có nghĩa là chọn phần tử nằm ở hàng thứ ba. Tuy nhiên, nếu chúng ta chỉ lấy phần tử 7 làm phần tử phân giải thì toàn bộ dòng thứ ba sẽ phải chia cho 7. Đối với tôi, việc chia cho (-2) đơn giản hơn. Do đó, hãy hoán đổi dòng thứ ba và thứ tư, khi đó phần tử phân giải sẽ trở thành (-2):
$$ \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(mảng)\right) \rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end(mảng)\right) $$
Phần tử độ phân giải - (-2). Chia hàng thứ ba cho (-2) và đặt lại các phần tử tương ứng của cột thứ ba:
$$ \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & - 3 & -4\\ 0 & 0 & 7 & -9 & -25\end(array)\right) \begin(array) (l) \phantom(0)\\ \phantom(0) \\III:( -2)\\\phantom(0)\end(array)\rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end(mảng)\right) \begin(mảng) (l) I-2 /3\cdot III\\ \phantom(0) \\ \phantom(0)\\IV-7\cdot III\end(array)\rightarrow\\ \rightarrow\left(\begin(array)(cccc|c ) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & - 39\end(mảng)\phải). $$
Bước thứ tư
Hãy chuyển sang zeroing cột thứ tư. Phần tử kích hoạt nằm ở dòng thứ tư và bằng số$-\frac(39)(2)$.
$$ \left(\begin(array)(cccc|c) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & -39\end(array)\right) \begin(array) (l) \phantom(0)\\ \phantom(0) \\ \phantom(0) \\IV:\left(-\frac(39)(2)\right) \end(array)\rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end(mảng)\right) \begin(mảng) (l ) I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom(0) \end(array)\rightarrow\\ \rightarrow\left(\begin(array)(cccc |c) 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\end (mảng)\phải). $$
Quyết định đã kết thúc. Câu trả lời là: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Giải pháp hoàn chỉnh mà không cần giải thích:
Trả lời: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.
Ví dụ số 3
Giải SLAE $\left\(\begin(aligned) & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4 +14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_4-21x_5=- 9. \end(aligned)\right.$ bằng phương pháp Gauss-Jordan Nếu hệ thống không chắc chắn, hãy chỉ ra. giải pháp cơ bản.
Các ví dụ tương tự được thảo luận trong chủ đề “Các giải pháp tổng quát và cơ bản của SLAEs”. Trong phần thứ hai của chủ đề được đề cập ví dụ này giải quyết bằng phương pháp Gaussian. Chúng ta sẽ giải nó bằng phương pháp Gauss-Jordan. Chúng tôi sẽ không chia nhỏ giải pháp ra từng bước vì điều này đã được thực hiện trong các ví dụ trước.
$$ \left(\begin(array)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end(array)\right) \begin(array) (l) \phantom(0) \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I \\ V+2\cdot I\\VI+4\cdot I \end(array) \rightarrow \left(\begin(array)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\ \\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(array)\right) \begin(array) (l) \phantom(0) \\ II:5 \\ \ phantom(0)\\ \phantom(0)\\ \phantom(0) \\ \phantom(0)\end(array) \rightarrow \\ \left(\begin(array)(ccccc|c) 1 & - 2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(array)\right) \ bắt đầu (mảng) (l) I+2\cdot II \\ \phantom(0)\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \ kết thúc (mảng) \rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2 /5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & - 4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right). $$
Tôi tin rằng một trong những phép biến đổi được thực hiện vẫn cần có lời giải thích: $IV:3$. Tất cả các phần tử của dòng thứ tư hoàn toàn chia hết cho ba, do đó, vì lý do đơn giản hóa, chúng tôi chia tất cả các phần tử của dòng này thành ba. Hàng thứ ba trong ma trận được chuyển đổi trở thành số 0. Hãy gạch bỏ dòng số 0:
$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(mảng)\right) $$
Đã đến lúc chúng ta chuyển sang bước thứ ba, tại đó các thành phần của cột thứ ba sẽ được đặt lại. Tuy nhiên, phần tử đường chéo (hàng thứ ba) bằng 0. Và việc thay đổi vị trí của các dòng sẽ không có tác dụng gì. Chúng ta đã sử dụng dòng thứ nhất và dòng thứ hai rồi nên không thể chạm vào chúng. Nhưng chẳng ích gì khi chạm vào dòng thứ tư và thứ năm, bởi vì vấn đề phần tử độ phân giải bằng 0 sẽ không biến mất.
Trong tình huống này, vấn đề có thể được giải quyết một cách cực kỳ đơn giản. Chúng tôi không thể xử lý cột thứ ba? Được rồi, hãy chuyển sang số bốn. Có thể ở cột thứ tư phần tử của hàng thứ ba sẽ không bằng 0. Tuy nhiên, cột thứ tư cũng gặp phải vấn đề tương tự như cột thứ ba. Phần tử hàng thứ ba trong cột thứ tư bằng 0. Và việc thay đổi vị trí của các dòng một lần nữa sẽ không mang lại kết quả gì. Chúng tôi cũng không thể xử lý cột thứ tư? Được rồi, hãy chuyển sang số năm. Nhưng ở cột thứ năm, phần tử của hàng thứ ba thậm chí không bằng 0. Nó bằng một, khá tốt. Vì vậy, phần tử phân giải ở cột thứ năm bằng 1. Phần tử phân giải đã được chọn nên chúng ta sẽ tiến hành các phép biến đổi tiếp theo của phương pháp Gauss-Jordan:
$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right) \begin(array) (l) I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom(0)\\ IV+III\\ V+ 2 \cdot III \end(array) \rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1 / 5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end(array)\right) \rightarrow \\ \rightarrow\left|\text(Xóa 0 hàng)\right|\rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(array)\ bên phải )$$
Chúng ta đã rút gọn ma trận hệ thống và ma trận hệ thống mở rộng về dạng từng bước. Thứ hạng của cả hai ma trận đều bằng $r=3$, tức là. bạn cần chọn 3 biến cơ bản. Số ẩn số là $n=5$, vì vậy chúng ta cần chọn $n-r=2$ biến tự do. Vì $r< n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":
Trên “bậc thang” có các phần tử từ cột số 1, số 2, số 5. Do đó, các biến cơ bản sẽ là $x_1$, $x_2$, $x_5$. Các biến tự do tương ứng sẽ là $x_3$, $x_4$. Chúng ta sẽ di chuyển cột số 3 và số 4, tương ứng với các biến tự do, ra ngoài dòng, đồng thời tất nhiên không quên đổi dấu của chúng.
$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(array)\right)\rightarrow \left(\begin(array)(ccc|ccc) 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end(mảng)\right) . $$
Từ ma trận cuối cùng, chúng ta thu được nghiệm tổng quát: $\left\(\begin(aligned) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5 )x_4; \\ & x_2=\frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\ trong R; \\ & x_5=4. \end(aligned)\right.$. Chúng tôi tìm ra giải pháp cơ bản bằng cách lấy các biến miễn phí bằng 0, tức là $x_3=0$, $x_4=0$:
$$ \left\(\begin(aligned) & x_1=-\frac(99)(5);\\ & x_2=\frac(3)(5);\\ & x_3=0;\\ & x_4= 0;\\ & x_5=4 \end(căn chỉnh)\phải $$.
Vấn đề đã được giải quyết, việc còn lại là viết ra câu trả lời.
Trả lời: Giải pháp chung: $\left\(\begin(aligned) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5)x_4;\\ & x_2=\frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4.\end(aligned)\right.$, giải pháp cơ bản: $\left\(\begin(aligned) & x_1=-\frac(99)(5);\\ & x_2=\frac(3) (5);\\ & x_3=0;\\ & x_4=0;\\ & x_5=4.\end(căn chỉnh)\right.$.
Với điều kiện là không có biến “0 hàng” (hạn chế bình đẳng) và biến “tự do” (tức là các biến không tuân theo yêu cầu về tính không âm).
2. Trong trường hợp tồn tại các ràng buộc đẳng thức và các biến “tự do”, hãy tiến hành như sau.
Chọn phần tử phân giải trong “hàng 0” và thực hiện bước loại bỏ Jordan đã sửa đổi, sau đó cột phân giải này bị gạch bỏ. Chuỗi hành động này được tiếp tục cho đến khi bảng đơnít nhất còn lại một "0 hàng" (trong trường hợp này bảng bị thu gọn).
Nếu cũng có các biến tự do thì cần phải làm cho các biến này trở thành cơ bản. Và sau khi biến tự do trở thành cơ bản, trong quá trình xác định phần tử giải quyết khi tìm kiếm phương án tham chiếu và phương án tối ưu dòng đã cho không được tính đến (nhưng được chuyển đổi).
Suy thoái trong bài toán quy hoạch tuyến tính
Xét phương pháp đơn hình, chúng ta giả sử rằng bài toán lập trình tuyến tính là không suy biến, tức là mỗi kế hoạch tham khảo chứa chính xác 
thành phần tích cực, trong đó 
– số ràng buộc trong bài toán. Trong kế hoạch hỗ trợ suy biến, số lượng thành phần tích cực hóa ra ít hơn số lượng hạn chế: một số biến cơ bản tương ứng với kế hoạch hỗ trợ nhất định có giá trị bằng 0. Sử dụng cách giải thích hình học cho trường hợp đơn giản nhất, khi 
(số lượng biến không cơ bản là 2), dễ dàng phân biệt bài toán suy biến với bài toán không suy biến. Trong bài toán suy biến, tại một đỉnh của khối đa diện có điều kiện có nhiều hơn hai đường thẳng cắt nhau, được mô tả bằng phương trình có dạng 
. Điều này có nghĩa là một hoặc nhiều cạnh của đa giác điều kiện bị co lại thành một điểm.
MỘT 
chịu thuế khi 
Trong bài toán suy biến, có hơn 3 mặt phẳng cắt nhau tại một đỉnh 
.
Với giả định rằng bài toán không suy biến, chỉ có một giá trị 
, qua đó xác định được chỉ số của vectơ điều kiện rút ra từ cơ sở (rút ra từ số biến cơ bản). Trong bài toán suy biến 
có thể đạt được trên nhiều chỉ mục cùng một lúc (đối với một số hàng). Trong trường hợp này, trong sơ đồ tham chiếu được tìm thấy, một số biến cơ bản sẽ bằng 0.
Nếu bài toán quy hoạch tuyến tính trở nên suy biến, thì với việc lựa chọn sai vectơ các điều kiện dẫn xuất từ cơ sở, có thể xảy ra chuyển động vô hạn dọc theo các cơ sở của cùng một mặt phẳng tham chiếu. Cái gọi là hiện tượng đi xe đạp. Mặc dù vòng lặp là một hiện tượng cực kỳ hiếm gặp trong các bài toán quy hoạch tuyến tính thực tế nhưng không thể loại trừ khả năng của nó.
Một trong những phương pháp chống suy biến là biến đổi bài toán bằng cách thay đổi “nhỏ” vectơ vế phải của hệ ràng buộc về số lượng 
, sao cho bài toán trở nên không suy biến, đồng thời, để sự thay đổi này không thực sự ảnh hưởng đến phương án tối ưu của bài toán.
Các thuật toán được triển khai phổ biến hơn bao gồm một số quy tắc đơn giản giúp giảm khả năng xảy ra hoặc khắc phục vòng lặp.
Để biến 
cần phải được thực hiện cơ bản. Hãy xem xét một tập hợp các chỉ mục 
, bao gồm những 
, nhờ đó nó đạt được 
. Rất nhiều chỉ số 
, với điều kiện này được thỏa mãn, chúng tôi biểu thị nó bằng 
. Nếu như 
gồm một phần tử thì vectơ điều kiện bị loại khỏi cơ sở 
(Biến đổi 
được thực hiện không cơ bản).
Nếu như 
bao gồm nhiều hơn một phần tử thì một tập hợp được hình thành 
, bao gồm 
, trên đó nó đạt được 
. Nếu như 
bao gồm một chỉ số 
, thì biến được suy ra từ cơ sở 
. Ngược lại, một tập hợp được hình thành 
vân vân.
Trong thực tế, quy tắc này nên được sử dụng nếu chu kỳ đã được phát hiện.
Để cho phép applet chạy trên máy tính của bạn, bạn cần thực hiện như sau - nhấp vào Bắt đầu>Bảng điều khiển>Chương trình>Java. Trong cửa sổ Java Bảng điều khiển chọn tab Bảo mật, nhấp vào nút Chỉnh sửa Danh sách Trang, nút thêm và chèn đường dẫn đến trang này từ trường trống thanh địa chỉ browser. Tiếp theo, bấm OK, rồi khởi động lại máy tính.
Để khởi chạy applet, nhấp vào nút "Simplex". Nếu nút "Simplex" không hiển thị phía trên dòng này thì Java chưa được cài đặt trên máy tính của bạn.
Sau khi nhấn vào nút “Simplex”, cửa sổ đầu tiên xuất hiện để nhập số biến và số ràng buộc của bài toán theo phương pháp đơn hình.
Sau khi nhấn nút “ok”, một cửa sổ xuất hiện để nhập dữ liệu còn lại của tác vụ phương pháp đơn giản: chế độ hiển thị ( số thập phân hoặc thông thường), loại tiêu chí nhiệm vụ min hoặc max, đầu vào các hệ số của hàm mục tiêu và các hệ số của hệ giới hạn có dấu “<”, “ ≥” hoặc “=”, giới hạn dạng x i ≥ 0 thì không cần phải nhập, đưa chúng vào tài khoản trong thuật toán của nó.
Sau khi nhấn nút “Giải” sẽ xuất hiện cửa sổ kết quả giải bài toán trên .Cửa sổ bao gồm hai phần; ở phần trên có trường văn bản chứa mô tả về cách giảm vấn đề ban đầu thành hình thức kinh điển, được sử dụng để biên dịch bảng đơn giản đầu tiên. Ở cuối cửa sổ, trong một bảng có các tab, có các bảng đơn giản của mỗi lần lặp với một phần nhỏ trương Văn bản bên dưới chỉ ra cột cho phép, hàng cho phép và các thông tin khác, giúp chương trình mang tính giáo dục. Trong tab có bảng tối ưu (cuối cùng) trong trường văn bản, kết quả được đưa ra giải pháp tối ưu nhiệm vụ.
Gửi bất kỳ lỗi nào bạn nhận thấy và nhận xét về applet tới: [email được bảo vệ] hoặc gọi 8 962 700 77 06, chúng tôi sẽ rất biết ơn bạn.
Chương trình phương pháp M
Chương trình giải quyết vấn đề vận chuyển
Đây là giải pháp thủ công (không phải applet) cho hai vấn đề sử dụng phương pháp đơn giản (tương tự như giải pháp applet) với giải thích chi tiếtđể hiểu thuật toán giải bài toán. Bài toán thứ nhất chỉ chứa dấu bất đẳng thức “<” (bài toán có cơ sở ban đầu), bài toán thứ hai có thể chứa dấu “ ≥”, “<” hoặc “=" (bài toán có cơ sở ban đầu). cơ sở nhân tạo), chúng được giải quyết khác nhau.
Phương pháp đơn giản, giải bài toán dựa trên cơ sở ban đầu
1)Phương pháp đơn giản cho một bài toán có cơ sở ban đầu (tất cả các dấu của ràng buộc bất đẳng thức " ≤ ").
Hãy viết vấn đề vào kinh điển hình thức, tức là chúng ta viết lại các giới hạn bất đẳng thức dưới dạng đẳng thức, thêm vào bảng cân đối kế toán biến:
Hệ này là hệ có một cơ sở (cơ sở s 1, s 2, s 3, mỗi cơ sở chỉ đưa vào một phương trình của hệ với hệ số 1), x 1 và x 2 là các biến tự do. Các bài toán cần giải bằng phương pháp đơn hình phải có hai tính chất sau:
- Hệ ràng buộc phải là hệ phương trình có cơ sở;
-các số hạng tự do của tất cả các phương trình trong hệ phải không âm.
Hệ thu được là một hệ có cơ sở và các số hạng tự do của nó không âm nên có thể áp dụng phương pháp đơn hình. Hãy tạo bảng đơn giản đầu tiên (Lặp lại 0), tức là bảng hệ số của hàm mục tiêu và hệ phương trình các biến tương ứng. Ở đây “BP” có nghĩa là cột các biến cơ bản, “Giải pháp” có nghĩa là cột bên phải của các phương trình hệ thống. Giải pháp này không tối ưu vì có các hệ số âm trong hàng z.
lần lặp 0
BP |
Giải pháp | Thái độ | |||||
Để cải thiện giải pháp, chúng tôi chuyển sang lần lặp tiếp theo và thu được bảng đơn giản sau. Để làm điều này bạn cần chọn bật cột, I E. một biến sẽ được đưa vào cơ sở ở lần lặp tiếp theo. Nó được chọn bởi hệ số âm tuyệt đối lớn nhất trong hàng z (trong bài toán cực đại) - trong lần lặp ban đầu, đây là cột x 2 (hệ số -6).
Sau đó chọn kích hoạt chuỗi, I E. một biến sẽ rời khỏi cơ sở ở lần lặp tiếp theo. Nó được chọn theo tỷ lệ nhỏ nhất của cột “Quyết định” với các phần tử dương tương ứng của cột độ phân giải (cột “Tỷ lệ”) - trong lần lặp ban đầu, đây là hàng s 3 (hệ số 20).
yếu tố cho phép nằm ở giao điểm của cột phân giải và hàng phân giải, ô của nó được tô màu, bằng 1. Do đó, ở lần lặp tiếp theo, biến x 2 sẽ thay thế s 3 trong cơ sở. Lưu ý rằng mối quan hệ không được tìm kiếm trong chuỗi z; dấu gạch ngang “-” được đặt ở đó. Nếu có các quan hệ tối thiểu giống hệt nhau thì bất kỳ quan hệ nào trong số chúng đều được chọn. Nếu tất cả các hệ số trong cột độ phân giải nhỏ hơn hoặc bằng 0 thì nghiệm của bài toán là vô hạn.
Hãy điền vào bảng sau “Lặp lại 1”. Chúng ta sẽ lấy nó từ bảng “Iteration 0”. Mục tiêu của các phép biến đổi tiếp theo là biến cột độ phân giải x2 thành cột đơn vị (với cột 1 thay vì phần tử độ phân giải và số 0 thay vì các phần tử còn lại).
1) Tính hàng x 2 của bảng “Lặp 1”. Đầu tiên, chúng ta chia tất cả các thành viên của hàng phân giải s 3 của bảng “Lặp 0” cho phần tử phân giải (nó bằng 1 trong trong trường hợp này) của bảng này, ta được hàng x 2 trong bảng “Lặp lại 1”. Bởi vì phần tử phân giải trong trường hợp này bằng 1 thì hàng s 3 của bảng “Lặp 0” sẽ trùng với hàng x 2 của bảng “Lặp 1”. Hàng x 2 của bảng Iteration 1 ta được 0 1 0 0 1 20, các hàng còn lại của bảng Iteration 1 sẽ được lấy từ hàng này và các hàng của bảng Iteration 0 như sau:
2) Tính toán hàng z của bảng “Lặp lại 1”. Thay cho -6 ở hàng đầu tiên (hàng z) trong cột x2 của bảng Lặp 0, phải có số 0 ở hàng đầu tiên của bảng Lặp 1. Để làm điều này, nhân tất cả các phần tử của hàng x 2 của bảng "Lặp 1" 0 1 0 0 1 20 với 6, ta được 0 6 0 0 6 120 và cộng hàng này với hàng đầu tiên (z - row) của bảng "Lặp 0" -4 -6 0 0 0 0, ta được -4 0 0 0 6 120. Số 0 xuất hiện ở cột x 2, mục tiêu đã đạt được. Các phần tử của cột độ phân giải x 2 được tô màu đỏ.
3) Tính toán hàng s 1 của bảng “Lặp lại 1”. Thay cho hàng 1 trong 1 hàng của bảng “Lặp lại 0” phải có số 0 trong bảng “Lặp lại 1”. Để làm điều này, nhân tất cả các phần tử của hàng x 2 của bảng "Lặp 1" 0 1 0 0 1 20 với -1, được 0 -1 0 0 -1 -20 và thêm hàng này với s 1 - hàng của bảng "Lặp lại 0" 2 1 1 0 0 64, chúng ta nhận được hàng 2 0 1 0 -1 44. Trong cột x 2, chúng ta nhận được 0 cần thiết.
4) Tính hàng s 2 của bảng “Lặp lại 1”. Ở vị trí thứ 3 trong hàng thứ 2 của bảng "Lặp lại 0" phải có 0 trong bảng "Lặp lại 1". Để làm điều này, nhân tất cả các phần tử của hàng x 2 của bảng “Lặp lại 1” 0 1 0 0 1 20 với -3, được 0 -3 0 0 -3 -60 và thêm hàng này với s 2 - hàng của bảng “Lặp lại 0” 1 3 0 1 0 72, ta được hàng 1 0 0 1 -3 12. Trong cột x 2 thu được số 0 bắt buộc trong bảng “Lặp lại 1” đã trở thành một đơn vị. , nó chứa một số 1 và số còn lại là 0.
Các hàng của bảng “Lặp lại 1” được lấy theo quy tắc sau:
Dòng mới = Dòng cũ– (Hệ số cột phân giải hàng cũ)*(Hàng phân giải mới).
Ví dụ: đối với chuỗi z, chúng ta có:
Chuỗi z cũ (-4 -6
0
0
0
0)
-(-6)*Dòng phân giải mới -(0-6
0
0
-6
-120)
=Chuỗi z mới(-4
0
0
0
6
120)
.
Đối với các bảng sau, việc tính toán lại các thành phần của bảng cũng được thực hiện tương tự nên chúng ta bỏ qua.
lần lặp 1
| Giải pháp | Thái độ | ||||||
Giải cột x 1, giải hàng s 2, s 2 bỏ cơ sở, x 1 vào cơ sở. Theo cách tương tự, chúng ta thu được các bảng đơn còn lại cho đến khi chúng ta thu được một bảng có tất cả các hệ số dương trong hàng z. Đây là dấu hiệu của một bảng tối ưu.
Lặp lại 2
| Giải pháp | Thái độ | ||||||
Giải cột s 3, giải hàng s 1, s 1 ra khỏi cơ sở, s 3 vào cơ sở.
Lặp lại 3
| Giải pháp | Thái độ | ||||||
Trong hàng z, tất cả các hệ số đều không âm nên thu được nghiệm tối ưu x 1 = 24, x 2 = 16, z max = 192.
Phương pháp đơn giản, giải quyết vấn đề bằng cơ sở nhân tạo
2) Hãy giải bài toán bằng cơ sở nhân tạo (ít nhất một dấu ràng buộc bất đẳng thức “ ≥” hoặc “=”).
Viết bài toán dưới dạng chính tắc (dạng hệ phương trình yêu cầu sử dụng phương pháp đơn hình), để làm được điều này ta đưa vào hai biến x 3 ≥ 0 và x 4 ≥ 0, ta được:
Hệ thống hạn chế chỉ đưa ra một biến cơ bản cho phép x 4, chỉ đưa vào một biến duy nhất ở phương trình thứ ba có hệ số 1 nên ta thêm biến nhân tạo R 1 ≥ 0 và R 2 ≥ 0 vào phương trình thứ nhất và thứ hai để có thể áp dụng phương pháp đơn hình, các phương trình ràng buộc hệ thống phải là một hệ thống có cơ sở, tức là trong mỗi phương trình phải có một biến có hệ số 1, biến này chỉ có trong một phương trình của hệ, trong trường hợp của chúng ta là R 1, R 2 và x 4. Chúng tôi đã nhận được cái gọi là nhiệm vụ M:
Hệ thống này là hệ có cơ sở trong đó R 1, R 2 và x 4 là các biến cơ bản và x 1, x 2 và x 3 là các biến tự do, các số hạng tự do của mọi phương trình đều không âm. Vì vậy có thể sử dụng phương pháp đơn hình để giải bài toán. Hãy viết ra bảng đơn giản ban đầu:
lần lặp 0
| Giải pháp | Thái độ | |||||||
| -16 | ||||||||
Dòng "Đánh giá" đã được thêm vào bảng dành cho các vấn đề có cơ sở nhân tạo. Nó có được bằng cách tính tổng các hệ số tương ứng của các hàng với các biến nhân tạo (R) có dấu ngược lại. Nó sẽ có mặt trong bảng miễn là có ít nhất một trong các biến nhân tạo có trong cơ sở. Dựa trên hệ số âm modulo lớn nhất của dòng “Đánh giá”, cột phân giải được xác định khi nó nằm trong bảng. Khi hàng "Đánh giá" rời khỏi bảng (không có biến nhân tạo nào trong cơ sở), cột giải quyết sẽ được xác định bởi hàng z, như trong bài toán với cơ sở ban đầu. Trong bảng này, cột phân giải là x 2, được chọn dựa trên điểm âm tuyệt đối lớn nhất (-7). Hàng phân giải R 2 được chọn dựa trên tỷ lệ nhỏ nhất của cột “Giải” với các phần tử dương tương ứng của cột phân giải, như trong bài toán không có biến nhân tạo. Điều này có nghĩa là ở lần lặp tiếp theo, biến x2 sẽ chuyển từ free sang basic và biến R2 sẽ chuyển từ basic sang free. Chúng ta viết bảng đơn giản sau:
Giải cột x 1, giải hàng R 1, R 1 bỏ cơ sở, x 1 vào cơ sở. Sau đó, không còn biến nhân tạo nào trong cơ sở nên không có dòng “Đánh giá” trong bảng sau:
lặp lại 2
| Giải pháp | Thái độ | |||||||
Tiếp theo, cột độ phân giải được chọn theo hàng z. Trong hàng z, tất cả các hệ số đều không âm ngoại trừ hệ số cho biến nhân tạo R 1, hệ số này không ảnh hưởng đến tính tối ưu khi các biến nhân tạo rời khỏi cơ sở. Từ đó thu được nghiệm tối ưu x 1 = 6/5; x 2 = 3/5; z tối đa = 72/5.
Các trường hợp đặc biệt khi sử dụng phương pháp đơn hình
1) Khi xét một đường thẳng (nếu xét bài toán quy hoạch tuyến tính hai chiều và trong trường hợp chung siêu phẳng) biểu diễn hàm mục tiêu song song với đường thẳng (siêu phẳng) tương ứng với một trong các ràng buộc của bất đẳng thức (mà ở điểm tối ưu được thỏa mãn là đẳng thức chính xác) hàm mục tiêu chấp nhận điều tương tự giá trị tối ưu trên một tập hợp các điểm nhất định trên ranh giới của miền lời giải khả thi. Những giải pháp này được gọi là giải pháp tối ưu thay thế. khả dụng các giải pháp thay thế có thể được xác định từ bảng đơn giản tối ưu. Nếu hàng z của bảng tối ưu chứa hệ số 0 của các biến không cơ bản thì sẽ có các giải pháp thay thế.
2) Nếu trong cột phân giải của bảng đơn tất cả các hệ số đều nhỏ hơn hoặc bằng 0 thì không thể chọn hàng phân giải, trong trường hợp này giải pháp là không giới hạn.
3) Nếu các ràng buộc của một bài toán quy hoạch tuyến tính không nhất quán (nghĩa là chúng không thể được thỏa mãn đồng thời) thì bài toán không có lời giải khả thi. Tình huống này không thể xảy ra nếu tất cả các bất đẳng thức tạo nên hệ giới hạn đều thuộc loại “<” với vế phải không âm, bởi vì trong trường hợp này, các biến bổ sung có thể tạo thành một giải pháp khả thi. Đối với các loại ràng buộc khác, các biến nhân tạo được sử dụng. Nếu bài toán có lời giải thì trong bảng tối ưu không có biến nhân tạo (R i) làm cơ sở. Nếu họ ở đó thì vấn đề không có giải pháp.
Nếu phát biểu bài toán chứa các hạn chế có dấu ≥ thì chúng có thể rút gọn về dạng ∑a ji b j bằng cách nhân cả hai vế của bất đẳng thức với -1. Chúng ta hãy giới thiệu m biến bổ sung x n+j ≥0(j =1,m) và chuyển đổi các ràng buộc về dạng đẳng thức
(2)
Chúng ta hãy giả sử rằng tất cả ban đầu biến nhiệm vụ x 1 , x 2 ,..., x n – không cơ bản. Khi đó các biến bổ sung sẽ là biến cơ bản và lời giải cụ thể cho hệ ràng buộc có dạng
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)
Vì trong trường hợp này giá trị của hàm mục tiêu F 0 = 0 nên chúng ta có thể biểu diễn F(x) như sau:
F(x)=∑c i x i +F 0 =0 (4)
Bảng đơn giản ban đầu (bảng đơn giản 1) được biên soạn dựa trên phương trình (2) và (4). Nếu các biến bổ sung x n+j được đặt trước dấu “+”, như trong (2), thì tất cả các hệ số đứng trước các biến x i và số hạng tự do b j được đưa vào bảng đơn mà không thay đổi. Khi cực đại hóa hàm mục tiêu, các hệ số được nhập vào hàng dưới cùng của bảng đơn có dấu ngược nhau. Các số hạng tự do trong bảng đơn xác định lời giải của bài toán.
Thuật toán để giải quyết vấn đề như sau:
Bước 1. Các thành viên của cột thành viên miễn phí được xem. Nếu tất cả chúng đều dương thì một giải pháp cơ bản có thể chấp nhận được đã được tìm thấy và người ta nên chuyển sang bước 5 của thuật toán, tương ứng với việc tìm giải pháp tối ưu. Nếu bảng đơn ban đầu có số hạng tự do âm thì lời giải không hợp lệ và bạn nên chuyển sang bước 2.
Bước thứ 2. Để tìm ra một giải pháp có thể chấp nhận được, nó được thực hiện và cần phải quyết định biến nào không cơ bản sẽ đưa vào cơ sở và biến nào cần loại bỏ khỏi cơ sở.
Bảng 1.
| biến cơ bản | Thành viên miễn phí bị hạn chế | Các biến không cơ bản | |||||
| x 1 | x 2 | ... | xl | ... | x n|||
| xn+1 | b 1 | số 11 | số 12 | ... | một 1l | ... | một 1n |
| xn+2 | b 2 | 21 | số 22 | ... | một 2l | ... | một 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | một r1 | một r2 | ... | một rl | ... | arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | một m1 | một m2 | ... | một ml | ... | một phút |
| F(x)tối đa | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Để thực hiện điều này, hãy chọn bất kỳ phần tử phủ định nào của cột số hạng tự do (đặt b 2 dẫn đầu hoặc phân giải. Nếu không có phần tử phủ định nào trong hàng có số hạng tự do phủ định thì hệ thống ràng buộc không nhất quán và vấn đề không có giải pháp.
Đồng thời, biến đổi dấu đầu tiên khi NP xl được chọn tăng sẽ bị loại khỏi BP. Đây sẽ là x n+r, chỉ số r của nó được xác định từ điều kiện
những thứ kia. biến có tỷ lệ nhỏ nhất của số hạng tự do với phần tử của cột đầu được chọn. Mối quan hệ này được gọi là quan hệ đơn giản. Chỉ nên xem xét các mối quan hệ đơn giản tích cực.
Đường thẳng tương ứng với biến x n+r được gọi là dẫn đầu hoặc cho phép. Phần tử của bảng đơn a rl, nằm ở giao điểm của hàng đầu và cột đầu, được gọi là phần tử đầu hoặc phần tử phân giải. Việc tìm kiếm phần tử dẫn đầu kết thúc công việc với mỗi bảng đơn giản thông thường.
Bước thứ 3. Một bảng đơn giản mới được tính toán, các phần tử của bảng này được tính toán lại từ các phần tử của bảng đơn giản bước trước và được đánh dấu bằng số nguyên tố, tức là b" j , a" ji , c" i , F" 0 . Các phần tử được tính toán lại bằng công thức sau:
Đầu tiên, bảng đơn giản mới sẽ điền vào hàng và cột dẫn đầu trong bảng đơn giản trước đó. Biểu thức (5) có nghĩa là phần tử a"rl thay cho phần tử đứng đầu bằng nghịch đảo của phần tử trong bảng đơn trước đó. Các phần tử của hàng a ri được chia cho phần tử đứng đầu và các phần tử của hàng a ri được chia cho phần tử đứng đầu. cột a jl cũng được chia cho phần tử đứng đầu nhưng lấy dấu ngược lại. Các phần tử b"r và c"l đều được tính theo nguyên tắc tương tự.
Phần còn lại của công thức có thể được viết dễ dàng bằng cách sử dụng .
Hình chữ nhật được xây dựng theo bảng đơn cũ theo cách mà một trong các đường chéo của nó được hình thành bởi các phần tử được tính toán lại (a ji) và phần tử dẫn đầu (a rl) (Hình 1). Đường chéo thứ hai được xác định duy nhất. Để tìm phần tử mới a" ji, tích của các phần tử có đường chéo đối diện chia cho phần tử đứng đầu được trừ khỏi phần tử a" ji (điều này được biểu thị bằng dấu “-” bên cạnh ô). Phần tử b" j, (j≠r) và c"i được tính lại theo cách tương tự. (i≠l).
Bước thứ 4. Việc phân tích bảng đơn giản mới bắt đầu bằng bước đầu tiên của thuật toán. Hành động tiếp tục cho đến khi tìm thấy giải pháp cơ bản khả thi, tức là. tất cả các phần tử của cột float phải dương.
Bước thứ 5. Chúng tôi tin rằng một giải pháp cơ bản có thể chấp nhận được đã được tìm ra. Chúng ta xét các hệ số của đường hàm mục tiêu F(x) . Một dấu hiệu về tính tối ưu của bảng đơn là tính không âm của các hệ số đối với các biến không cơ bản trong hàng F.
Cơm. 1. Quy tắc hình chữ nhật
Nếu trong số các hệ số của hàng F có hệ số âm (ngoại trừ số hạng tự do), thì bạn cần chuyển sang một giải pháp cơ bản khác. Khi tối đa hóa hàm mục tiêu, cơ sở bao gồm một trong các biến không cơ bản (ví dụ x l), cột tương ứng với giá trị tuyệt đối tối đa của hệ số âm c l ở hàng dưới cùng của bảng đơn. Điều này cho phép bạn chọn biến có mức tăng dẫn đến cải thiện hàm mục tiêu. Cột tương ứng với biến xl gọi là cột dẫn đầu. Đồng thời, biến x n+r đó bị loại khỏi cơ sở, chỉ số r của biến đó được xác định bởi quan hệ đơn giản tối thiểu:
Hàng tương ứng với x n+r được gọi là hàng đầu, và phần tử của bảng đơn a rl, đứng ở giao điểm của hàng đầu và cột đầu, được gọi là yếu tố hàng đầu.
Bước thứ 6. theo các quy tắc được nêu ở bước 3. Quá trình này tiếp tục cho đến khi tìm được giải pháp tối ưu hoặc kết luận rằng giải pháp đó không tồn tại.
Trong quá trình tối ưu hóa giải pháp, nếu tất cả các phần tử trong cột đầu tiên đều không dương thì không thể chọn hàng đầu tiên. Trong trường hợp này, hàm trong miền nghiệm khả thi của bài toán không bị giới hạn ở trên và F max ->&∞.
Nếu ở bước tiếp theo của quá trình tìm kiếm cực trị, một trong các biến cơ bản trở thành bằng 0 thì nghiệm cơ bản tương ứng được gọi là suy biến. Trong trường hợp này, cái gọi là vòng lặp xảy ra, đặc trưng bởi thực tế là tần số nhất định sự kết hợp tương tự của BP bắt đầu lặp lại (giá trị của hàm F được giữ nguyên) và không thể chuyển sang một giải pháp cơ bản mới được chấp nhận. Vòng lặp là một trong những nhược điểm chính của phương pháp đơn giản, nhưng nó tương đối hiếm. Trong thực tế, trong những trường hợp như vậy, họ thường từ chối nhập cơ sở biến có cột tương ứng với giá trị tuyệt đối tối đa của hệ số âm trong hàm mục tiêu và chọn ngẫu nhiên một giải pháp cơ sở mới.
Ví dụ 1. Giải bài toán
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Sử dụng phương pháp đơn hình và đưa ra cách giải thích hình học của quá trình giải.
Một giải thích đồ họa về giải pháp cho vấn đề được trình bày trong Hình. 2. Giá trị lớn nhất của hàm mục tiêu đạt được tại đỉnh của ODZP có tọa độ . Hãy giải quyết vấn đề bằng cách sử dụng bảng đơn giản. Hãy nhân ràng buộc thứ hai với (-1) và đưa vào các biến bổ sung để đưa các bất đẳng thức về dạng đẳng thức, sau đó
Chúng tôi lấy các biến ban đầu x 1 và x 2 là không cơ bản và coi x 3, x 4 và x 5 bổ sung là cơ bản và soạn một bảng đơn giản (bảng đơn giản 2). Lời giải tương ứng với bảng đơn. 2, không hợp lệ; phần tử hàng đầu được phác thảo và lựa chọn theo bước 2 của thuật toán trước. Bảng đơn giản sau đây. 3 xác định một nghiệm cơ bản có thể chấp nhận được; đỉnh của ODZP trong Hình 1 tương ứng với nó. 2 Phần tử chủ đạo được phác thảo và lựa chọn theo bước 5 của thuật toán giải bài toán. Bàn 4 tương ứng với phương án tối ưu của bài toán nên: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F tối đa = 20.
Cơm. 2. Giải pháp đồ họa nhiệm vụ
Đọc thêm:
|
Định lý (về việc chọn phần tử phân giải)
Nếu một số cột của hàng z có phần tử âm thì cột phân giải phải được chọn là cột có tích lớn nhất giá trị tuyệt đối hệ số ở hàng z và tỷ lệ đơn hình tối thiểu cột này.
Bằng chứng:
Hãy để phần tử là phần tử cho phép. Do bước loại bỏ Jordan đã được sửa đổi, số hạng tự do trong hàng z sẽ là số bằng . Vì và , dấu ngoặc đơn trong biểu thức này sẽ luôn dương. Và vì giá trị của hàm luôn bằng số hạng tự do nên dấu ngoặc này thể hiện phần cộng của hàm thu được do bước thực hiện.
Mức tăng mà chức năng nhận được ở mỗi bước càng lớn thì càng cần ít bước (tức là tính toán) để đạt được mức tối ưu. Độ lớn của mức tăng này phụ thuộc vào giá trị tuyệt đối của hệ số và giá trị của tỷ lệ đơn hình nhỏ nhất. Tức là cột phân giải sẽ là cột có tích lớn nhất này.
Ví dụ: quy hoạch tuyến tính:
Hãy tìm cực đại của hàm số
dưới những hạn chế
Giải pháp: Hãy tạo một bảng Jordan.
Vì các thành viên miễn phí đều tích cực nên kế hoạch này mang tính hỗ trợ. Tuy nhiên, nó không tối ưu vì hệ số hàng z âm. Chúng tôi chọn từ chúng cái có tích lớn nhất có giá trị tuyệt đối và tỷ lệ đơn hình nhỏ nhất. Cột thứ ba được coi là có độ phân giải vì nó có giá trị lớn nhất giá trị tuyệt đối 8 và quan hệ đơn giản: tương ứng ( , vì vậy phần tử 1 ở cột thứ ba sẽ được giải quyết). Chúng ta thực hiện bước loại bỏ Jordan đã được sửa đổi và đi đến bảng sau.
Xét theo hệ số z-row thì bảng kết quả chưa đạt được nghiệm tối ưu. Chúng tôi lấy cột thứ hai có hệ số âm trong hàng z làm cột phân giải (chỉ cột đầu tiên mới có thể là hàng phân giải). Với phần tử 5 được tìm thấy, chúng ta thực hiện bước tiếp theo.
Trong hàng z, tất cả các hệ số đều dương; thiết kế thu được bằng cách đánh đồng các biến trên bằng 0 và các biến bên với số hạng tự do là tối ưu. Chúng tôi viết ra các giá trị của các ẩn số chính từ bảng: Chúng tôi tính giá trị tối đa của hàm trong ô cuối cùng của bảng:
Trong bảng cuối cùng, tất cả các yếu tố quyết định đều không âm. Điều này cho thấy rằng đối với các giá trị chưa biết thì hàm đạt cực đại
Người ta thường giả định rằng không có điểm nào trong tập kế hoạch bài toán mà tại đó mẫu số của hàm mục tiêu bằng 0. Không mất tính tổng quát, ta có thể giả sử rằng .
Trong bài toán quy hoạch tuyến tính phân số, cực trị của hàm mục tiêu đạt được tại đỉnh của đa diện nghiệm. Sự giống nhau này với lập trình tuyến tính cho phép giải các bài toán tuyến tính phân số bằng phương pháp Stiefel.
Các tính toán được trình bày dưới dạng bảng Jordan. Trong trường hợp này, hai dòng dưới được phân bổ cho hàm: ở dòng đầu tiên chúng ta viết các hệ số của tử số và ở dòng thứ hai - mẫu số. Nhiệm vụ ban đầu tương ứng với bảng 1:
| –x 1 | –x 2 | … | –xj | … | –x n | ||
| y 1 | Một 11 | Một 12 | … | Một 1 j | … | Một 1 N | Một 1 |
| … | ……………………………………… | … | |||||
| ừ tôi | tôi 1 | tôi 2 | … | một ij | … | một trong | tôi |
| … | ……………………………………… | … | |||||
| năm tháng | là 1 | là 2 | … | một mj | … | một phút | là |
| z 1 | –P 1 | –P 2 | … | –p j | … | –p n | |
| z 2 | –q 1 | –q 2 | … | –qj | … | –qn |
Bởi vì ừ tôi sự khác biệt giữa phần bên phải và bên trái của hệ thống hạn chế được chỉ ra:
ừ tôi= tôi–tôi 1 x 1 – tôi 2 x 2 –tôi 3 x 3 – … – một trong x n ³ 0.
Chúng ta sẽ gọi các biến tự do là các biến nằm ở hàng tiêu đề phía trên của bảng Jordan. Đưa ra các biến miễn phí giá trị 0, ta được lời giải cơ bản ban đầu: . Vectơ này không thể là một kế hoạch tham chiếu, bởi vì mẫu số của hàm mục tiêu trên đó bằng 0 ( z 2 = 0). Vì vậy, trong số những thành viên tự do của hệ thống hạn chế Một 1 ,…, là chắc chắn có số âm(nếu không thì giải pháp cơ bản sẽ là phương án tham khảo).
Sử dụng các bước loại bỏ Jordan đã sửa đổi, giống như khi giải một bài toán quy hoạch tuyến tính (xem), chúng ta tìm được sơ đồ ban đầu của bài toán. Kết quả là k bước chúng ta đến bảng 2:
| –y 1 | … | –xj | … | –x n | ||
| x 1 | b 11 | … | b 1 j | … | b 1 N | b 1 |
| .… | ……………………………………… | |||||
| ừ tôi | tôi 1 | … | b ij | … | thùng rác | tôi |
| …. | ……………………………………. | |||||
| năm tháng | b m 1 | … | b mj | … | b phút | b m |
| z 1 | f 1 | … | fj | … | fn | F |
| z 2 | g 1 | … | g j | … | g n | G |
Trong bảng 2 tất cả các thành viên miễn phí tôi là không âm, đảm bảo tính không âm của các biến cơ sở x 1 ,…, năm tháng. Ngoài ra (do mẫu số dương của hàm mục tiêu z 2 trên một bộ kế hoạch tham khảo). Sơ đồ tham chiếu ban đầu là một vectơ có tọa độ . Giá trị của hàm mục tiêu trên sơ đồ tham chiếu ban đầu là .
Lưu ý rằng nếu tại một trong các bước loại bỏ Jordan, bất kỳ điều khoản miễn phí nào b tôi sẽ âm và tất cả các yếu tố khác Tôi hàng thứ sẽ không âm thì vấn đề sẽ không có giải pháp do thiếu kế hoạch.
Chúng ta hãy xem hàm mục tiêu thay đổi như thế nào khi chuyển từ sơ đồ tham chiếu này sang sơ đồ tham chiếu khác. Hóa ra dấu hiệu của sự khác biệt giữa giá trị mới và giá trị cũ của hàm trùng với dấu của định thức. Nếu như. Bởi vì Vì khối đa diện nghiệm chỉ chứa một số hữu hạn các phương án hỗ trợ, nên với một số bước hữu hạn chúng ta sẽ đi đến phương án hỗ trợ tối ưu.
Quá trình này chỉ có thể bị cản trở bởi tính không giới hạn của các giải pháp đa diện. Trong trường hợp này, hàm mục tiêu có thể có cái gọi là cực trị tiệm cận (trong trường hợp này là cực đại). Giá trị cực đại tiệm cận của một bài toán quy hoạch tuyến tính phân số là giới hạn trên chính xác của hàm mục tiêu trên một tập hợp các kế hoạch, không đạt được trên bất kỳ kế hoạch nào. Trong trường hợp bài toán có cực đại tiệm cận, trong lĩnh vực kế hoạch, luôn có thể tìm thấy một kế hoạch (không phải kế hoạch tham chiếu) trong đó hàm mục tiêu lấy một giá trị tùy ý gần với mức tối đa tiệm cận.
Phương pháp Stiefel cho phép bạn tìm không chỉ mức tối đa mà còn tìm mức tối đa tiệm cận của một bài toán quy hoạch tuyến tính phân số. Chúng ta hãy xem xét kỹ hơn quá trình chuyển đổi từ kế hoạch này sang kế hoạch khác và tìm hiểu. Chọn phần tử phân giải trong j cột thứ, chúng ta phải được hướng dẫn bởi nguyên tắc của quan hệ đơn hình tối thiểu. Những thứ kia. yếu tố kích hoạt trong j Cột -th phải nằm trong hàng mà quan hệ đơn hình là dương và tối thiểu.
Bởi vì sau khi tìm được sơ đồ tham chiếu ban đầu, tất cả các vế phải tôi trở thành không âm thì phần tử phân giải j Cột thứ có thể là một trong những phần tử tích cực của nó (). Nếu ở mỗi bước của giai đoạn tìm kiếm kế hoạch tham chiếu tối ưu có (ít nhất một) phần tử dương trong cột độ phân giải đã chọn, thì bài toán đó có mức tối đa (có thể nhiều hơn một).
Tuy nhiên, nếu tại một trong các bước một số ước tính nhỏ hơn 0 và tất cả các phần tử j cột thứ. Sau đó, trong cột này, được hướng dẫn bởi nguyên tắc quan hệ đơn giản tối thiểu, phần tử phân giải không thể được chọn. Tăng giá trị của biến miễn phí xj từ 0 đến (xem Bảng 2), chúng tôi luôn nằm trong vùng quy hoạch. Điều này là do thực tế là sự gia tăng của biến xj không gây ra sự thay đổi từ dấu sang âm cho bất kỳ biến cơ bản nào.
Hãy ký hiệu bằng M giới hạn mà tại đó, tăng đơn điệu, hàm mục tiêu có xu hướng: . Con số này là mức tối đa tiệm cận.
| 2 |
