Tài liệu Phương pháp số giải bài toán quy hoạch lồi và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRƯƠNG TUẤN HƯNG PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN QUY HOẠCH LỒI VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRƯƠNG TUẤN HƯNG PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN QUY HOẠCH LỒI VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số : 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC (Xác nhận) TS. Vũ Vinh Quang THÁI NGUYÊN - 2018 iii Mục lục Lời cảm ơn v Bảng ký hiệu 1 Mở đầu 2 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN 4 1.1 Mô hình tổng quát của bài toán quy hoạch tuyến tính . . . 4 1.1.1 1.1.2 1.2 1.3 Mô hình tổng quát . . . . . . . . . . . . . . . . . . 4 Phân loại bài toán tối ưu . . . . . . . . . . . . . . . 5 Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . 6 Một số phương pháp giải cơ bản . . . . . . . . . . . . . . . 8 1.3.1 1.3.2 Thuật toán hình học . . . . . . . . . . . . . . . . . 8 Thuật toán đơn hình . . . . . . . . . . . . . . . . . 9 1.3.3 1.3.4 Thuật toán đơn hình mở rộng . . . . . . . . . . . . 15 Phương pháp giải bài toán quy hoạch tuyến tính tổng quát trên phần mềm MATLAB . . . . . . . . 16 Chương 2. BÀI TOÁN QUY HOẠCH LỒI, CÁC THUẬT TOÁN 18 2.1 Mô hình bài toán quy hoạch lồi tổng quát . . . . . . . . . 18 2.2 2.1.1 Khái niệm về tập lồi, hàm lồi . . . . . . . . . . . . 18 2.1.2 2.1.3 Khái niệm về Gradient và đạo hàm theo hướng . . 20 Bài toán quy hoạch lồi tổng quát, điều kiện tối ưu . 21 Cực tiểu hàm lồi một biến . . . . . . . . . . . . . . . . . . 22 2.2.1 Thuật toán chia đôi . . . . . . . . . . . . . . . . . 22 iv 2.3 2.2.2 Thuật toán mặt cắt vàng . . . . . . . . . . . . . . . 24 Mô hình bài toán quy hoạch lồi với ràng buộc tuyến tính . 26 2.3.1 2.3.2 2.4 Mô hình tổng quát . . . . . . . . . . . . . . . . . . 26 Thuật toán Frank-Wolfe . . . . . . . . . . . . . . . 26 Mô hình bài toán quy hoạch lồi với ràng buộc phi tuyến . 29 2.4.1 Mô hình tổng quát . . . . . . . . . . . . . . . . . . 29 2.4.2 Thuật toán Gradient . . . . . . . . . . . . . . . . . 29 Chương 3. MỘT SỐ ỨNG DỤNG THIẾT KẾ TỐI ƯU 3.1 3.2 32 Mô hình bài toán sản xuất sản phẩm . . . . . . . . . . . . 32 Mô hình bài toán xác định thiết diện tối ưu của giàn chịu lực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Kết luận 39 Tài liệu tham khảo 40 v Lời cảm ơn Trước hết, tôi xin bày tỏ lòng kính trọng và lòng biết ơn sâu sắc tới thầy giáo TS. Vũ Vinh Quang, người thầy tận tình hướng dẫn, chỉ bảo và cung cấp những tài liệu rất hữu ích để tôi có thể hoàn thành luận văn. Xin cảm ơn lãnh đạo Trường Đại học Khoa học - Đại học Thái nguyên đã tạo điều kiện giúp đỡ tôi về mọi mặt trong suốt quá trình học tập và thực hiện luận văn. Tôi xin bày tỏ lòng biết ơn tới các thầy, cô giáo giảng dạy lớp K10Y đã truyền đạt kiến thức, và phương pháp nghiên cứu khoa học trong suốt những năm học vừa qua. Xin chân thành cảm ơn các anh chị em học viên cao học K10Y và các bạn đồng nghiệp đã động viên, khích lệ tôi trong quá trình học tập, nghiên cứu. Tôi xin bày tỏ lòng biết ơn sâu sắc đến gia đình, người thân, những người luôn động viên, khuyến khích và giúp đỡ về mọi mặt để tôi có thể hoàn thành công việc nghiên cứu. vi Lời cam đoan Tôi xin cam đoan: Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy giáo hướng dẫn TS. Vũ Vinh Quang. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tác giả, tên công trình, thời gian, địa điểm công bố. Tôi xin chịu trách nhiệm với lời cam đoan của mình 1 Bảng ký hiệu R Rn Tập số thực Không gian vectơ thực n chiều X Vectơ trong không gian Rn f (X) → max f (X) → min Bài toán tìm cực đại Bài toán tìm cực tiểu CT D Vectơ chuyển vị của C Miền phương án ∇f |x| Vectơ đạo hàm hướng Giá trị tuyệt đối của x |X| x∈D Số phần tử của tập X x thuộc D x∈ /D AT x không thuộc D Ma trận chuyển vị của ma trận A xopt Là điểm để hàm f (x) đạt giá trị tối ưu f val Exitf lag Giá trị min của hàm mục tiêu Số nguyên thông báo kết thúc tính toán lb(lower bound) ub(upper bound) Giới hạn dưới Giới hạn trên linprog bintprog Lệnh để lấy nghiệm không âm Lệnh để lấy nghiệm nguyên có giá trị 1 hoặc 0 QHT T Quy hoạch tuyến tính 2 Mở đầu Mô hình bài toán quy hoạch phi tuyến tính nói chung và quy hoạch lồi nói riêng là một mô hình quan trọng trong lớp các bài toán tối ưu hóa, có rất nhiều ứng dụng trong các bài toán cơ học và vật lý. Về mặt lý thuyết, đã có rất nhiều các tài liệu đã trình bày các thuật toán lý thuyết giải mô hình các bài toán này trên mô hình tổng quát. Tuy nhiên việc nghiên cứu và cài đặt chi tiết các thuật toán và ứng dụng vào một số mô hình đối với một bài toán cụ thể trong cơ học và vật lý là chưa nhiều người đề cập đến. Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật toán cơ bản giải bài toán quy hoạch lồi có ràng buộc, tìm hiểu chi tiết các bước mô tả thuật toán, xây dựng sơ đồ khối và cài đặt các thuật toán trên ngôn ngữ lập trình cụ thể. Trên cơ sở các thuật toán đã nghiên cứu và cài đặt, luận văn xây dựng mô hình ứng dụng của một số bài toán trong cơ học và vật lý xác định mô hình tối ưu trong thiết kế. Nội dung của luận văn dự kiến gồm có 3 chương, phần phụ lục được cấu trúc như sau: Chương 1: Trình bày một số kiến thức cơ bản bao gồm mô hình tổng quát của bài toán quy hoạch tuyến tính, các thuật toán: Hình học, đơn hình, đơn hình mở rộng và phương pháp giải bài toán quy hoạch tuyến tính tổng quát trên phần mềm MATLAB. Chương 2: Trình bày các kiến thức và thuật toán liên quan đến bài toán quy hoạch lồi bao gồm mô hình bài toán quy hoạch lồi tổng quát, các thuật toán giải bài toán cực tiểu hàm lồi một biến, mô hình bài toán quy hoạch lồi với ràng buộc tuyến tính, thuật toán Frank−Wolfe. Mô hình bài toán quy hoạch lồi với ràng buộc phi tuyến, thuật toán 3 Gradient. Chương 3: Trình bày một số mô hình bài toán ứng dụng trong thực tế: Mô hình bài toán sản xuất sản phẩm và mô hình bài toán xác định thiết diện tối ưu của giàn chịu lực. Phần phụ lục đưa ra một số chương trình nguồn trên môi trường MATLAB giải bài toán cực trị hàm lồi. Thái Nguyên, tháng 5 năm 2018 Tác giả luận văn Trương Tuấn Hưng 4 Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN Nội dung chính của chương 1 trình bày mô hình tổng quát của bài toán quy hoạch tuyến tính, các thuật toán: Hình học, đơn hình, đơn hình mở rộng, và phương pháp giải bài toán quy hoạch tuyến tính tổng quát trên phần mềm MATLAB. Các kết quả là những kiến thức quan trọng được ứng dụng trong các chương sau của luận văn. Các kiến thức được tham khảo trong các tài liệu [1, 2]. 1.1 Mô hình tổng quát của bài toán quy hoạch tuyến tính 1.1.1 Mô hình tổng quát Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các quá trình . . . Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các bài toán cực trị, người ta sẽ đạt được hiệu quả kinh tế cao. Điều này phù hợp với mục đích của các vấn đề đặt ra trong thực tế hiện nay. Bài toán tối ưu tổng quát được phát biểu như sau: Cực đại hóa (cực tiểu hóa) hàm: f (X) → max(min) 5 Với các điều kiện: gi (X) = bi , i ∈ J1 ; (1.1) gj (X) ≤ bj , j ∈ J2 ; (1.2) gk (X) ≥ bk , k ∈ J3 ; (1.3) x1 , x2 , ..., xn ≥ 0. (1.4) Trong đó f (X) được gọi là hàm mục tiêu. Các điều kiện (1.1) được gọi là ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức. Các điều kiện (1.4) được gọi là ràng buộc về dấu. X = (x1 , x2 , ..., xn ) là vectơ thuộc không gian Rn . Tập các vectơ X thỏa mãn hệ ràng buộc lập nên một miền D được gọi là miền phương án (hay miền chấp nhận được), mỗi điểm X ∈ D gọi là một phương án. Một phương án X ∗ ∈ D làm cho hàm mục tiêu f (X) đạt max (min) được gọi là phương án tối ưu. 1.1.2 Phân loại bài toán tối ưu Dựa trên mô hình tổng quát, người ta thường phân loại lớp các bài toán tối ưu như sau: • Qui hoạch tuyến tính: là những bài toán mà hàm mục tiêu f (X)và tất cả các hàm ràng buộc gi (X), gj (X), gk (X) là tuyến tính. • Qui hoạch phi tuyến: là những bài toán một trong hàm mục tiêu f (X) hoặc các hàm ràng buộc gi (X) , gj (X) , gk (X) là phi tuyến. • Qui hoạch lồi: Là các bài toán qui hoạch mà các hàm mục tiêu f (X) là lồi trên tập các ràng buộc D lồi. • Qui hoạch lõm: Là các bài toán qui hoạch mà các hàm mục tiêu f (X) là lõm trên tập các ràng buộc D lõm. • Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên thì ta có qui hoạch nguyên. 6 • Qui hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời các hàm mục tiêu khác nhau. • Trong các lĩnh vực kinh tế kỹ thuật thì qui hoạch phi tuyến, qui hoạch tuyến tính là những bài toán thường gặp. 1.2 Bài toán quy hoạch tuyến tính Từ một số các mô hình trong thực tế, ta có mô hình tổng quát cho bài toán quy hoạch tuyến tính như sau: Xác định các biến xj (j = 1, 2, ..., n) sao cho: F (x) = n X cj xj → max(min); j=1 n X aij xj ≥ bi (i ∈ I1 ⊂ M ) ; (1.5) aij xj = bi (i ∈ I2 = M \I1 ) ; (1.6) j=1 n X j=1 lbj ≤ xj ≤ ubj , (j ∈ J ⊂ N ). (1.7) Với M = {1, 2, ..., m}, N = {1, 2, ..., n} . Vectơ X = (x1 , x2 , ..., xn ) thỏa mãn các điều kiện (1.5) - (1.7) được gọi là một phương án của bài toán. Tập các nghiệm thỏa mãn hệ ràng buộc được gọi là miền phương án, ký hiệu là D. Phương án thỏa mãn điều kiện để hàm mục tiêu đạt max (min) được gọi là phương án tối ưu. Dạng chính tắc: F (x) = n X cj xj → min; j=1 n X aij xj = bi (i ∈ M ) ; j=1 xj ≥ 0(j ∈ N ). 7 Dạng chuẩn tắc: F (x) = n X cj xj → min; j=1 n X aij xj ≥ bi (i ∈ M ) ; j=1 xj ≥ 0(j ∈ N ). Sử dụng các ký hiệu vectơ và ma trận, mô hình bài toán quy hoạch tuyến tính tổng quát được biểu diễn như sau: f (X) = C T X → max(min); AX = b, AX ≥ b; lb ≤ X ≤ ub. Trong đó: X = (x1 , x2 , ...,  xn ), C= (c1 , c2 , ..., cn )    a11 a12 ... a1n a11 a12 ... a1n x1        a21 a22 ... a2n   a21 a22 ... a2n   x2  ; X =  ; A =   A=   ...   ...  ...        a a ... amn a a ... a xn  m1 m2  mn  m1  m2   b1 b1 lb1 ub1          b2   b2   lb2   ub2         b=  ...  ; b =  ...  ; lb =  ...  ; ub =  ...          bm bm lbn ubn Một số phép biến đổi cơ bản: a/ Nếu hàm mục tiêu dạng max thì có thể chuyển về dạng min bằng cách đổi dấu hàm mục tiêu. b/ Một ràng buộc bất đẳng thức có thể chuyển về ràng buộc đẳng thức bằng cách thêm các ẩn giả với hệ số tương ứng bằng 0 trong hàm mục tiêu. c/ Một biến không ràng buộc dấu được thay thế bằng 2 biến có ràng buộc dấu. 8 1.3 1.3.1 Một số phương pháp giải cơ bản Thuật toán hình học Xét bài toán: f (x1 , x2 ) = c1 x1 + c2 x2 → M ax; a11 x1 + a12 x2 ≤ b1 ; a21 x1 + a22 x2 ≤ b2 ; ... an1 x1 + an2 x2 ≤ bn ; x1 ≥ 0; x2 ≥ 0. Nhận xét 1.3.1 1. Vì các ràng buộc của bài toán luôn luôn là các nửa mặt phẳng, do đó miền phương án luôn luôn là một đa giác lồi (là giao của các nửa mặt phẳng). 2. Xét đường thẳng f = m được gọi là đường mức. Hiển nhiên khi đường mức chuyển động song song trong miền phương án thì điểm chạm cuối cùng của đường mức với miền luôn luôn là 1 trong các đỉnh của đa giác (Hoặc 1 cạnh của đa giác). Đấy chính là phương án tối ưu cần tìm. Xuất phát từ nhận xét trên, chúng ta có thuật toán hình học gồm các bước như sau : Thuật toán: Bước 1: Vẽ miền phương án D là đa giác lồi bằng cách xác định miền giao của các nửa mặt phẳng trong hệ ràng buộc. Bước 2: Xác định tọa độ của các đỉnh đa giác: Giả sử là các điểm A1 , A2 , ..., Ak . Bước 3: Xác định phương án tối ưu fmax = max{f (A1 ), f (A2 ), ..., f (Ak )}. Chú ý 1.3.2 Trong trường hợp khi miền phương án không phải là miền kín thì tùy thuộc vào hướng di chuyển của đường mức, chúng ta sẽ xác định được phương án tối ưu của bài toán. 9 1.3.2 Thuật toán đơn hình Mô tả thuật toán gốc Cơ sở của phương pháp này được Dantzig công bố năm 1947 có tên gọi là phương pháp đơn hình. Xuất xứ tên gọi như vậy vì những bài toán đầu tiên được giải bằng phương pháp đó có các ràng buộc dạng: n X xj = 1, xj > 0 (j = 1, 2, ..., n). j=1 Mà tập các điểm thoả mãn các ràng buộc trên là một đơn hình trong không gian n chiều. Tư tưởng chung Phương pháp đơn hình dựa trên hai nhận xét sau: • Nếu bài toán QHTT có phương án tối ưu thì có ít nhất một đỉnh của D là phương án tối ưu. • Đa diện lồi D có một số hữu hạn đỉnh. Như vậy phải tồn tại một thuật toán hữu hạn. Thuật toán gồm 2 bước như sau: Bước 1: Tìm 1 phương án cực biên. Bước 2: Kiểm tra điều kiện tối ưu đối với phương án đó. + Nếu điều kiện tối ưu được thoả mãn thì phương án đó là tối ưu, nếu không ta chuyển sang phương án cực biên mới sao cho làm tốt hơn giá trị hàm mục tiêu. + Kiểm tra điều kiện tối ưu đối với phương án mới. Người ta thực hiện một dãy các thủ tục như vậy cho đến khi nhận được phương án tối ưu, hoặc đến tình huống bài toán không có phương án tối ưu. Cơ sở lý thuyết Xét bài toán QHTT dưới dạng chính tắc: f (x) = C T X ⇒ min . AX = b; X ≥ 0. 10 Trong đó A = (aij )n.m , X = (x1 , x2 , ..., xn ) , C = (c1 , c2 , ..., cn ), giả sử rằng hạng của ma trận A là m . Giả sử X là một phương án cực biên nào đó. Ta ký hiệu: J ∗ = {j|xj > 0} (1.8) . Vì các vectơ Aj , j ∈ J ∗ là độc lập tuyến tính nên |J ∗ | ≤ m. Định nghĩa 1.3.3 Phương án cực biên X được gọi là không suy biến nếu |J ∗ | = m, suy biến nếu |J ∗ | < m. Ta chọn một hệ thống m vectơ độc lập tuyến tính {Aj , j ∈ J} sao cho J ⊇ J ∗ . Hệ thống đó là cơ sở của X , các vectơ Aj , j ∈ J và biến xj , j ∈ J được gọi là các vectơ và các biến cơ sở tương ứng. Các vectơ và các biến Aj , xj , (j ∈ / J) gọi là các vectơ và các biến phi cơ sở. Nếu X không suy biến thì tồn tại một cơ sở duy nhất, đó là J = J ∗ . Mọi vectơ Ak phi cơ sở có thể biểu diễn dưới dạng tổ hợp tuyến tính của các vectơ cơ sở: X Ak = zjk Aj . (1.9) j∈J Trong các hệ số zjk được xác định duy nhất bởi việc giải hệ phương trình: ajk = X zjk aij , (i = 1, 2, ..., m). (1.10) j∈J Bài toán QHTT được gọi là không suy biến nếu tất cả các phương án cực biên của nó đều không suy biến. Giả sử bài toán không suy biến và ta đã tìm được một phương án cực biên X = (x1 , x2 , ..., xm , 0, ..., 0) và cơ sở của nó A1 , A2 , ..., Am . Đối với phương án cực biên này ta có: m X j=1 xj Aj = b, xj > 0, (j = 1, 2, ..., m). (1.11) 11 Với giá trị hàm mục tiêu: m X cj xj = z0 , xj > 0, (j = 1, 2, ..., m). (1.12) j=1 Ta tính các đại lượng sau: m X zjk cj = zk . (1.13) j=1 Ký hiệu: ∆k = zk − ck = m X zjk cj − ck . (1.14) j=1 Định lý 1.3.4 Nếu đối với các phương án cực biên X = (x1 , x2 , ..., xm , 0, ..., 0) mà các điều kiện sau được thỏa mãn: ∆k ≥ 0, ∀k = 1, 2, ..., n. (1.15) thì X là phương án tối ưu. Nhận xét 1.3.5 1. Trong (1.9) nếu Aj là một vectơ cơ sở khi đó tồn tại chỉ một hệ số zij = 1, tất cả các hệ số khác đều bằng 0 và ta có: ∆j = cj − cj = 0, j ∈ J. Và trong thực tế để kiểm tra điều kiện tối ưu của phương án cực biên X ta chỉ kiểm tra: ∆k ≥ 0, ∀k ∈ /J 2. Người ta có thể chứng minh rằng nếu bài toán không suy biến thì (1.15) cũng là điều kiện cần của bài toán tối ưu. Định lý 1.3.6 Nếu tồn tại một chỉ số k sao cho ∆k < 0 thì ta có thể tìm được ít nhất một phương án X 0 mà đối với nó Z 0 > Z. Trong thực tế Dantzig đã chứng minh rằng số các bước lặp sẽ giảm đáng kể nếu ta thay vectơ Ak bởi vectơ As thỏa mãn ∆s = min {∆k |∆k < 0} k và khi đó vectơ Ar được xác định theo công thức:   xj xr θs = min |zjs > 0 = zjs zrs (1.16) 12 Ta có phương án cực biên mới X 0 mà các thành phần của nó có dạng:  x  xj − r z 0 js , j 6= r x0j = xr zrs (1.17)   ,j = r zrs Với cơ sở của nó là: Aj , j ∈ J 0 = J\ {r} ∪ {s} . (1.18) Xuất phát từ cơ sở lý thuyết trên, chúng ta có thuật toán sau đây. Thuật toán đơn hình Bước 1: Tìm một phương án cực biên xuất phát X và cơ sở của nó Aj , j ∈ J Bước 2: P + Xác định các số zjk bởi hệ thống: Ak = zjk Aj . j∈J + Đối với mỗi k ∈ / J tính các ước lượng: ∆k = m X zjk cj − ck . j=1 • Nếu (∀k ∈ / J) , ∆k ≥ 0 ⇒ x là nghiệm tối ưu. Thuật toán dừng. • Nếu X không phải là nghiệm tối ưu: o (∃k ∈ / J) , ∆k < 0 và zjk ≤ 0, ∀j ∈ J ⇒ bài toán QHTT không có nghiệm tối ưu. Thuật toán dừng. o Đối với mỗi k ∈ / J sao cho ∆k < 0 đều tồn tại j ∈ J : zjk > 0 ⇒ chọn ∆s = min {∆k |∆k < 0} , đưa  cơ sở.  vectơ As vào xr xj Bước 3: Xác định: θs = min |zjs > 0 = . Đưa vectơ Ar ra zrs zrs khỏi cơ sở. Bước 4: Xác định phương án cực biên mới X 0 với cơ sở: J 0 = J\ {r} ∪ {s} . . Quay trở lại bước 2. Công thức đổi cơ sở, bảng đơn hình Ta xét các công thức chuyển từ phương án cực biên X với cơ sở J, sang phương án cực biên X 0 với cơ sở J 0 . Xuất phát từ công thức (1.17) 13 cho phép tính các thành phần của X 0 . Ta cần thiết lập công thức tính 0 các số zjk .. Ta có:  As = X zij Aj ⇒ Ar = j∈J  X  1  As −  z A js j .  zrs (1.19) j∈J j6=r Mặt khác: Ak = X (zjk Aj + zrk Ar ). (1.20) j∈J Thay biểu thức của Ar từ (1.19) vào (1.20) ta có:  Ak = X zjk Aj + j∈J Ak = X  zrk  As − ; z A js j  zrs  j∈J j6=r X j∈J j6=r   zsk zrk zjs Aj + . zjk Aj − zrs zrs Đây là công thức biểu diễn Ak qua cơ sở mới J 0 = J\ {r} ∪ {s}. Khi đó ta có:  zrk   zjs , j 6= r z − jk 0 zrs zjk = zrk   ,j = r zrs 0 Sau khi có zjk ta tính: 0 ∆k = X 0 zjk cj − ck . (1.21) j∈J Để dễ tính toán, tại mỗi bước lặp ta thiết lập bảng đơn hình (Bảng 1.1) - Sử dụng các phương pháp biến đổi theo thuật toán sau - Nếu tất cả các số trong hàng cuối (trừ F ) đều ≥ 0 , nghĩa là ∆k ≥ 0, ∀k, khi đó X là phương án tối ưu. Thuật toán dừng. - Nếu hàng cuối (không kể F ) tồn tại số âm mà mọi số trong cột tương ứng đều ≤ 0 thì bài toán không tồn tại phương án tối ưu. Ngược lại: 14 Cơ cj Phương c1 A1 c2 . . . cj . . . cr . . . cm . . . ck . . . cs . . . cn A2 . . . Aj . . . Ar . . . Am . . . Ak . . . As . . . An sở án c1 A1 x1 1 0... 0... 0... 0... z1k z1s z1n c2 A2 x2 0 1 0 0 0 z2k z2s z2n . . . . . . . . . . . . . . . . . . . . . . cj Aj xj 0 0 1 0 0 zjk zjs zjn . . . . . . . . . . . . . . . . . . . . . . cr Ar xr 0 0 0 1 0 zrk zrs zrn . . . . . . . . . . . . . . . . . . . . . . cm Am xm 0 0 0 0 1 zmk zms zmn F 0 0... 0... 0... 0... δk δs δn Bảng 1.1: Bảng lặp đơn hình + Chọn cột s sao cho: ∆s = min {∆k |∆k < 0}, cột gọi là cột xoay. Vectơ được đưa vào cơ sở.   xj xr + Chọn hàng r mà tỉ số: θr = = min |zjs > 0 . Hàng r gọi xrs zjs là hàng xoay. Vectơ Ar bị đưa ra khỏi cơ sở. Phần tử zrs > 0 là giao của cột xoay và dòng xoay gọi là phần tử trục. Các phần tử zjs , j 6= r gọi là phần tử xoay. Theo các công thức (1.17), (1.18), (1.21), bảng đơn hình mới suy được từ bảng đơn hình cũ bằng cách thay cr , Ar trong hàng xoay bằng . Sau đó thực hiện các phép biến đổi dưới đây: 1) Chia mỗi phần tử ở hàng xoay cho phần tử trục, kết quả thu được gọi là hàng chuẩn. 2) Đối với các hàng còn lại thực hiện biến đổi theo công thức Hàng mới = Hàng cũ tương ứng – Hàng chuẩn × Phần tử xoay. Toàn thể phép biến đổi trên gọi là phép quay xung quanh trục zrs . Sau khi thực hiện phép xoay ta có một phương án mới và một cơ sở mới, tiến hành kiểm tra điều kiện tối ưu.