1.2. Phương pháp đồ thịPhương pháp đồ thị có ý nghĩa minh họa và giúp hiểu bản chất vấn đề.Bước 1: Vẽ miền các phương án khả thi [còn gọi là miền ràng buộc] là tập hợp các phươngán khả thi [các phương án, nếu nói một cách ngắn gọn]. Mỗi phương án được thể hiện qua bộ số[x1, x2], thoả mãn tất cả các ràng buộc đã có kể cả điều kiện không âm của các biến [xem hìnhII.1].– Trước hết chúng ta vẽ đường thẳng có phương trình là 4x1 + 2x2 = 60 bằng cách xác địnhhai điểm thuộc đường thẳng: [x1 = 0, x2 = 30] và [x1 = 15, x2 = 0].Đường thẳng này chia mặt phẳng làm hai nửa mặt phẳng. Một phần gồm các điểm [x1, x2]thoả mãn: 4x1 + 2x2 ≤ 60, phần còn lại thoả mãn: 4x1 + 2x2 ≥ 60. Ta tìm được nửa mặt phẳng thoảmãn: 4x1 + 2x2 ≤ 60.– Tương tự, có thể vẽ đường thẳng có phương trình là 2x1 + 4x2 = 48 bằng cách xác địnhhai điểm thuộc đường thẳng là [x1 = 0, x2 = 12] và [x1 = 24, x2 = 0]. Sau đó tìm nửa mặt phẳngthoả mãn: 2x1 + 4x2 ≤ 48.x230124x1 + 2x2 = 60A8B2x1 + 4x2 = 484OC361524x1Hình II.1. Phương pháp đồ thị giải bài toán quy hoạch tuyến tính– Lúc này, giao của hai nửa mặt phẳng tìm được trên đây cho ta tập hợp các điểm [x1, x2]thoả mãn các ràng buộc. Tuy nhiên, để thoả mãn điều kiện không âm của các biến, ta chỉ xét cácđiểm nằm trong góc phần tư thứ nhất. Vậy miền các phương án khả thi [nói vắn tắt hơn, miềnphương án] là miền giới hạn bởi tứ giác OABC [còn gọi là tập lồi đa diện vì là miền tạo nên bởigiao của các nửa mặt phẳng].Bước 2: Trong miền [OABC] ta tìm điểm [x1, x2] sao choz = 8x1 + 6x2 đạt giá trị lớn nhất.Cách 1. Dùng đường đồng mức. Tùy theo giá trị của x1, x2 mà z có những mức giá trị khácnhau.17 – Vẽ đường đồng mức: 8x1 + 6x2 = c ở mức c = 24, [ta có thể chọn giá trị c bất kỳ, nhưngchọn c = 24 là bội số chung của 6 và 8 để việc tìm tọa độ các điểm cắt hai trục tọa độ thuận lợihơn]. Dễ dàng tìm được hai điểm nằm trên đường đồng mức này là [x1 = 0, x2 = 4] và [x1 = 3, x2 =0]. Các điểm nằm trên đường đồng mức này đều cho giá trị hàm mục tiêu z = 24.– Tương tự, có thể vẽ đường đồng mức thứ hai: 8x1 + 6x2 = 48 đi qua hai điểm [x1 = 0, x2 =8] và [x2 = 0, x1 = 6]. Chúng ta nhận thấy, nếu tịnh tiến song song đường đồng mức lên trên theohướng của véc tơ pháp tuyến n [8, 6] thì giá trị của hàm mục tiêu z = 8x1 + 6x2 tăng lên.Vậy giá trị z lớn nhất đạt được khi đường đồng mức đi qua điểm B[12, 6] [tìm được x1 =12, x2 = 6 bằng cách giải hệ phương trình 4x1 + 2x2 = 60 và 2x1 + 4x2 = 48].Do đó, trong các phương án khả thi thì phương án tối ưu là [x1 = 12, x2 = 6]. Tại phương ánnày, giá trị hàm mục tiêu là lớn nhất zmax = 8 × 12 + 6 × 6 = 132.Nhận xét. Phương án tối ưu [nếu có] của một BTQHTT với miền phương án D, là một tậplồi đa diện có đỉnh, luôn đạt được tại ít nhất một trong các đỉnh của D. Các đỉnh này còn được gọilà các điểm cực biên của tập lồi đa diện D [chính xác hơn, điểm cực biên là điểm thuộc tập lồi đadiện, mà không thể tìm được một đoạn thẳng nào cũng thuộc tập lồi đa diện nhận điểm đó là điểmtrong]. Nhận xét trên đây là một định lý toán học [xem thêm chương VI] đã được chứng minhmột cách tổng quát. Nói một cách hình ảnh, muốn đạt được phương án tối ưu cho các BTQHTTthì cần phải “mạo hiểm” đi xét các điểm cực biên của miền phương án.Cách 2. Từ nhận xét trên, đối với BTQHTT có phương án tối ưu và có miền phương án Dlà tập lồi đa diện có đỉnh, ta có thể tìm phương án tối ưu bằng cách so sánh giá trị của hàm mụctiêu tại các điểm cực biên của D. Quay lại ví dụ 1, ta có giá trị z tại O[0, 0]: z [0, 0] = 0, tại A[0,12]: z[0, 12] = 72, tại C[15, 0]: z[15, 0] = 120 và tại B[12, 6]: z[12, 6] = 132 [đạt zmax].Nhận xét. Xét BTQHTT có phương án tối ưu và có miền phương án D là tập lồi đa diện cóđỉnh. Để tìm phương án tối ưu, ta xuất phát từ một điểm cực biên nào đó và tìm cách cải thiệnhàm mục tiêu bằng cách đi tới điểm cực biên kề tốt hơn. Tiếp tục như vậy cho tới khi tìm đượcphương án tối ưu. Quy trình giải này bao gồm hữu hạn bước do số điểm cực biên là hữu hạn.Đối với BTQHTT trong ví dụ 1, quy trình giải được minh hoạ như sau:O[0, 0]→A[0, 12] → B[12, 6] dừngz=0z = 72z = 132hoặc:O[0, 0]z=0→C[15, 0] → B[12, 6] dừngz = 120z = 132Quy trình giải BTQHTT tổng quát có sơ đồ khối giản lược như trình bày trên hình II.2. Trongsơ đồ trên, vì mục đích trình bày vấn đề đơn giản, chúng ta không đề cập tới các trường hợp khiBTQHTT có miền phương án là tập rỗng [lúc đó ta không tìm được phương án cực biên xuất phát]cũng như khi ta không tìm được điểm cực biên kề tốt hơn mặc dù điều kiện tối ưu chưa thoả mãn [lúcđó hàm mục tiêu z không bị chặn].18 Sơ đồ khốiBắt đầuNhập dữ liệuTìm điểm cực biênxuất phátKiểm tra điều kiệntối ưuSaiTìm điểmcực biên kềtốt hơnĐúngIn và lưu trữ kết quảDừngHình II.2. Sơ đồ khối giải BTQHTT2. Phương pháp đơn hình2.1. Tìm hiểu quy trình tính toánPhương pháp đơn hình là phương pháp số giải BTQHTT theo sơ đồ trên. Để giải ví dụ đãcho, trước hết chúng ta cần đưa BTQHTT về dạng chính tắc bằng các biến bù không âm x3 và x4như sau:Max z = 8x1 + 6x2 + 0x3 + 0x4với các ràng buộc4x1 + 2x2 + x32x1 + 4x2= 60+ x4 = 48x1, x2, x3, x4 ≥ 0.Chú ý. BTQHTT có dạng chính tắc là BTQHTT với các biến không âm, các ràng buộc códấu “=”, hệ số vế phải của các ràng buộc không âm. Ngoài ra, mỗi phương trình bắt buộc phải cómột biến đứng độc lập với hệ số +1.Cách lập và biến đổi các bảng đơn hình19 Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như trong bảngII.1. Trước hết, cần điền số liệu của bài toán đã cho vào bảng đơn hình bước 1:– Cột 1 là cột hệ số hàm mục tiêu ứng với các biến cơ sở đã chọn. Phương án xuất phát cóthể chọn là x1 = x2 = 0 [đây chính là điểm gốc toạ độ O[0, 0] trên hình II.1], do đó x3 = 60, x4 =48. Như vậy tại bước này chúng ta chưa bước vào sản xuất, nên trong phương án chưa có đơn vịsản phẩm loại I hay loại II nào được sản xuất ra [chỉ “sản xuất” ra các lượng nguyên liệu dư thừa,ta cũng nói là các “sản phẩm” loại III và IV], và giá trị hàm mục tiêu z tạm thời bằng 0.Bảng II.1. Các bảng đơn hình giải BTQHTTHệ số hàmmục tiêu cjBiến cơ sởPhương ánc1 = 8c2 = 6c3 = 0c4 = 0x1x2x3x4Bảng đơn hình bước 10x36042100x4482401z0 = 0z1 = 0z2 = 0z3 = 0z4 = 0Δ1 = 8Δ2 = 6Δ3 = 0Δ4 = 0Hàng zHàng Δj = cj – zjBảng đơn hình bước 28x11511/21/400x41803–1/21z0 = 120z1 = 8z2 = 4z3 = 2z4 = 0Δ1 = 0Δ2 = 2Δ3 = –2Δ4 = 0Hàng zHàng Δj = cj – zjBảng đơn hình bước 38x112101/3–1/66x2601–1/61/3z0 = 132865/32/300–5/3–2/3Hàng zHàng Δj = cj – zjCác biến bù có giá trị lớn hơn 0 có nghĩa là các nguyên liệu loại tương ứng chưa được sửdụng hết. Ta gọi các biến x3 và x4 là các biến cơ sở vì chúng có giá trị lớn hơn 0 còn x1 và x2 làcác biến ngoài cơ sở vì chúng có giá trị bằng 0. Với bài toán có hai ràng buộc, tại mỗi bước chỉ cóhai biến cơ sở.– Cột 2 là cột các biến cơ sở. Trong cột 3 [cột phương án] cần ghi các giá trị của các biếncơ sở đã chọn.– Các cột tiếp theo là các cột hệ số trong các điều kiện ràng buộc tương ứng với các biếnx1, x2, x3 và x4 của bài toán đã cho.Phân tích bảng đơn hình bước 1– Hệ số ứng với biến x1 trên hàng thứ nhất là a11 = 4 có nghĩa là tỷ lệ thay thế riêng giữamột đơn vị sản phẩm loại I và một đơn vị sản phẩm loại III là 4 [giải thích: xét phương trình [hay20 ràng buộc] thứ nhất 4x1 + 2x2 + x3 = 60, x1 tăng một đơn vị thì x3 phải giảm bốn đơn vị nếu giữnguyên x2]. Tương tự ta có thể giải thích được ý nghĩa của các hệ số aij khác cho trên hàng 1 vàhàng 2 trong bảng đơn hình bước 1.– Chúng ta xét hàng z của bảng đơn hình. Để tính z1, cần áp dụng công thứcz1 = [cột hệ số của hàm mục tiêu]× [cột hệ số của biến x1] = 0×4 + 0×2 = [giá một đơn vị sảnphẩm loại III]×[tỷ lệ thay thế riêng loại I / loại III] + [giá một đơn vị sản phẩm loại IV]×[tỷ lệthay thế riêng loại I / loại IV] = tổng chi phí phải bỏ ra khi đưa thêm một đơn vị sản phẩm loại Ivào phương án sản xuất mới = 0. Các giá trị zj, với j = 1, 2, 3, 4, được tính tương tự và chính làcác chi phí khi đưa thêm một đơn vị sản phẩm loại xj vào phương án sản xuất mới. Còn z0 là giátrị của hàm mục tiêu đạt được tại phương án đang xét: z0 = [cột hệ số của hàm mục tiêu]× [cộtphương án] = 0×60 + 0 × 48 = 0.– Trên hàng Δj cần ghi các giá trị Δj , j = 1, 2, 3, 4, tính theo công thức Δj = cj –zj = lợinhuận / đơn vị sản phẩm – chi phí / đơn vị sản phẩm. Vậy Δj là "lãi biên" / một đơn vị sản phẩmkhi đưa một thêm một đơn vị sản phẩm loại xj vào phương án sản xuất mới. Nếu Δj > 0 thì hàmmục tiêu còn tăng được khi ta đưa thêm các sản phẩm loại j vào phương án sản xuất mới. Có thểchứng minh được Δj chính là đạo hàm riêng ∂z / ∂x j của hàm mục tiêu z theo biến xj . Như vậy,x1 tăng lên 1 thì z tăng lên 8 còn x2 tăng lên 1 thì z tăng lên 6 .Do Δ1 và Δ2 đều lớn hơn 0 nên vẫn còn khả năng cải thiện hàm mục tiêu khi chuyển sang[hay “xoay sang”] một phương án cực biên kề tốt hơn [quay lại nhận xét ở mục 1.2, phần giải bàitoán bằng phương pháp đồ thị: điểm cực biên kề của điểm O[0, 0] có thể là A[0, 12] hay C[15,0]].Thủ tục xoay [pivotal procedure]Bước 1: Chọn cột xoay là cột bất kỳ có Δj > 0. Lúc đó biến xj tương ứng với cột xoay đượcchọn làm biến cơ sở mới do xj tăng kéo theo hàm mục tiêu tăng. ở đây ta chọn đưa x1 vào làmbiến cơ sở mới.Bước 2: Chọn hàng xoay để xác định đưa biến nào ra khỏi tập các biến cơ sở [vì tại mỗibước số biến cơ sở là không thay đổi]. Để chọn hàng xoay, ta thực hiện quy tắc “tỷ số dương bénhất” bằng cách lấy cột phương án [60, 48]T chia tương ứng cho cột xoay [4, 2]T để chọn tỷ số bénhất. Một điều cần chú ý là ta chỉ xét các tỷ số có mẫu số dương.Vì Min {60/4, 48/2} = 60/4 đạt được tại hàng đầu, nên hàng xoay là hàng đầu [hàng tươngứng với biến x3]. Do đó cần đưa x3 ra khỏi tập các biến cơ sở.Bước 3: Chọn phần tử xoay nằm trên giao của hàng xoay và cột xoay.Bước 4: Xoay sang bảng đơn hình mới, xác định các biến cơ sở mới để điền vào cột biếncơ sở, đồng thời thay các giá trị trong cột hệ số hàm mục tiêu. Sau đó, tính lại các phần tử củahàng xoay bằng cách lấy hàng xoay cũ chia cho phần tử xoay để có hàng mới tương ứng.Bước 5: Các phần tử còn lại của bảng đơn hình mới tính theo quy tắc “hình chữ nhật”:[1]mới = [1]cũ – [2]cũ× [4]cũ/[3]cũ, trong đó [3] là đỉnh tương ứng với phần tử xoay [xem hình I.3].21 [2][3]Chẳng hạn: nếu [1]cũ = 4,[2]cũ = 2,[3]cũ = phần tử xoay = 4, [4]cũ = 2 thì[1]mới = 4 – 2×2/4 =3[4][1]Hình II.3. Quy tắc hình chữ nhậtGiải thích. Các bước xoay trên đây chỉ là phép biến đổi tương đương hệ phương trình4x1 + 2x2 + x3 = 60[2.1]2x1 + 4x2 + x4 = 48[2.2]x1 + [1/2]x2 + [1/4]x3 = 15[2.1’]0x1 + 3x2 – [1/2]x3 + x4 = 18[2.2’]để có hệbằng cách lấy phương trình [2.1] chia cho 4 [phần tử xoay] để có [2.1’], rồi lấy [2.2] trừ bớt 2×[2.1]/4 để có [2.2’]. Đây chính là nội dung của bước 4 và bước 5. Còn việc thực hiện bước 3 sẽđảm bảo rằng giá trị của các biến cơ sở mới không âm [x1 = 15,x4 = 18].Áp dụng thủ tục xoay cho các phần tử nằm trên hàng 1 và 2 của bảng đơn hình bước 1, sauđó tính các giá trị trên hàng zj và Δj tương tự như khi lập bảng đơn hình bước 1, chúng ta sẽ nhậnđược bảng đơn hình bước 2.Phân tích bảng đơn hình bước 2Bảng bước 2 có thể được phân tích tương tự như bảng bước 1. Cần chú ý rằng lúc này tađang ở vị trí của điểm C[15, 0] vì x1 = 15 còn x2 = 0 [xem hình II.1]. Tại điểm này giá trị của hàmmục tiêu là z0 = 120 đã được cải thiện hơn so với bước 1. Ta thấy Δ2 = 2 > 0 nên còn có thể cảithiện hàm mục tiêu bằng cách đưa biến x2 vào làm biến cơ sở mới. Thực hiện các bước xoay sangphương án cực biên kề tốt hơn, chúng ta sẽ có bảng đơn hình bước 3.Phân tích bảng đơn hình bước 3Tại bảng đơn hình bước 3 ta thấy điều kiện tối ưu đã được thoả mãn [Δj ≤ 0, ∀j = 1,4 ] nênkhông còn khả năng cải thiện phương án. Phương án tối ưu đã đạt được tại x1 = 12, x2 = 6, x3 = 0,x4 = 0, tức là tại điểm cực biên B[12, 6] với giá trị zmax = 132 [xem thêm hình II.1].Một số chú ý– Điều kiện tối ưu cho các BTQHTT dạng Max là Δj ≤ 0, ∀j .– Đối với các BTQHTT cần cực tiểu hoá hàm mục tiêu thì điều kiện tối ưu [hay tiêu chuẩndừng] là Δj ≥ 0, ∀j [nếu ∃ j* sao cho Δ j* < 0 thì cần tiếp tục cải thiện hàm mục tiêu bằng cáchchọn cột j* làm cột xoay].22 – Trong thực tiễn giải các BTQHTT dạng tổng quát có thể xảy ra trường hợp không tìmđược phương án xuất phát [tức là không có phương án khả thi]. Lúc này có thể kết luận mô hìnhđã thiết lập có các điều kiện ràng buộc quá chặt chẽ, cần xem xét nới lỏng các điều kiện này.– Trong trường hợp ta tìm được cột xoay mà không tìm được hàng xoay thì kết luận hàmmục tiêu không bị chặn trên [đối với các BTQHTT dạng Max] hoặc không bị chặn dưới [đối vớicác BTQHTT dạng Min].Trong các trường hợp trên cũng phải dừng lại và kết luận mô hình quy hoạch tuyến tính đãthiết lập không phù hợp với thực tế.2.2. Khung thuật toán đơn hìnhSau đây là khung thuật toán của phương pháp đơn hình được phát biểu cho BTQHTT cựcđại hóa dạng chính tắc.Bước khởi tạo– Tìm một phương án cực biên ban đầu.– Tính Δj = cj – zj, ∀j = 1,n , trong đó n là số biến của bài toán đang xét.Các bước lặpBước 1: Kiểm tra điều kiện tối ưu. Nếu điều kiện tối ưu Δj = cj – zj ≤ 0, ∀j = 1,n đã đượcthoả mãn thì in / lưu trữ kết quả của bài toán và chuyển sang bước kết thúc.Bước 2: Nếu tồn tại một chỉ số j sao cho Δj > 0 thì tiến hành thủ tục xoay gồm năm bướcđã biết, tính lại các Δj, ∀j = 1,n và quay lại bước 1 [Chú ý: Trong trường hợp ta tìm được cộtxoay mà không tìm được hàng xoay thì kết luận hàm mục tiêu không bị chặn, in / lưu trữ kết quảcủa bài toán và chuyển sang bước kết thúc].Bước kết thúc. Dừng.3. Cơ sở toán học của phương pháp đơn hình3.1. Phát biểu bài toán quy hoạch tuyến tính dạng chính tắcXét BTQHTTdạng sau đây [với các ràng buộc đều có dấu =]:Max [Min] z = c1x1 + c2x2 + ... + cnxnvới hệ điều kiện ràng buộc⎧a11 x1 + a12 x 2 + ... + a1n x n = b1⎪⎪a21 x1 + a22 x 2 + ... + a2n x n = b2⎨a x + a x + ... + a x = bm2 2mn nm⎪ m1 1⎪x ≥ 0, ∀j = 1,n.⎩ jChúng ta sử dụng các ký hiệu sau [T là ký hiệu chuyển vị]:– Véc tơ hệ số hàm mục tiêu c = [c1, c2, …, cn]T ∈ Rn,– Véc tơ quyết định x = [x1, x2, …, xn]T ∈ Rn,– Véc tơ hệ số vế phải b = [b1, b2, …, bm]T ∈ Rm,23 – Ma trận hệ số các điều kiện ràng buộc⎡ a11⎢aA = ⎢ 21⎢ ...⎢⎣am1a12a22...am 2... a1n ⎤... a2n ⎥⎥ ∈ Rm×n,... ... ⎥⎥... amn ⎦trong đó aj = [a1j, a2j, …,amj]T là véc tơ cột j của ma trận A, ∀j = 1,n .Với các ký hiệu trên, BTQHTT được viết ngắn gọn là:Max z = cTx, với x ∈ D = {x∈ Rn: Ax = b, x ≥ 0}.[2.3]BTQHTT trên đây được gọi là BTQHTT dạng chuẩn tắc nếu hạng của A bằng m và b ≥ 0[các tọa độ của b đều không âm]. Ngoài ra, nếu A có m véc tơ cột là các véc tơ đơn vị độc lậptuyến tính thì BTQHTT dạng chuẩn tắc trở thành BTQHTT dạng chính tắc. Trong trường hợpBTQHTT dạng chính tắc, không làm giảm tính tổng quát, chúng ta luôn có thể coi m véc tơ cột aj, ∀j = n − m + 1,n là các véc tơ đơn vị độc lập tuyến tính,Ví dụ 2. Chúng ta xét lại ví dụ 1 của chương này.Max z = 8x1 + 6x2 + 0x3 + 0x4với các ràng buộc4x1 + 2x2 + x32x1 + 4x2= 60+ x4 = 48x1, x2, x3, x4 ≥ 0.Đây là BTQHTT dạng chính tắc. Giả sử ma trận A được phân rã theo khối dưới dạng A =[NB] với B là ma trận khả nghịch. Chúng ta sẽ sử dụng các ký hiệu sau:J = {1, 2, ..., n} là tập các chỉ số, JB = {j: aj là véc tơ cột của B} là tập chỉ số các biến cơ sở, JN = J\ JB = {j : aj là véc tơ cột của N} là tập các chỉ số các biến ngoài cơ sở. Lúc đó, có thể viết véc tơ[TTquyết định dưới dạng x = x N , x B]T[TTvà véc tơ hệ số hàm mục tiêu c = cN , cB]T.Trong ví dụ 2, ta có: JN = {1, 2}, JB = {3, 4}. Dễ dàng thấy, phương án ban đầux =[xTNT, xB]T= [0, 0, 60, 48]T, trong đó xN = [x1, x2]T = [0, 0]T và xB = [x3, x4]T =[60, 48]T. Véc tơ hệ số hàm mục tiêu là c =[cTNT, cB]T= [8, 6, 0, 0]T với cN = [8 6]T,cB = [0 0]T. Các véc tơ cột của ma trận ràng buộc A là:⎡4 ⎤⎡2 ⎤⎡1 ⎤⎡0 ⎤a1 = ⎢ ⎥ , a2 = ⎢ ⎥ , a3 = ⎢ ⎥ , a4 = ⎢ ⎥ .⎣2 ⎦⎣4 ⎦⎣0 ⎦⎣1 ⎦⎡4 2 ⎤Vậy A = [a1, a2, a3, a4] = [N B] với N = ⎢⎥,B=⎣2 4 ⎦24⎡1 0 ⎤⎢0 1 ⎥ .⎣⎦ ⎡x ⎤Cần chú ý rằng: Ax = b ⇔ [N B] ⎢ N ⎥ = b ⇔ NxN + BxB = b⇔ BxB = b ⇔ xB = B–1b.⎣xB ⎦Phương án cực biênĐối với BTQHTT [2.3] dạng chính tắc luôn có thể tìm được một phương án xuất phát x =[0, 0, …, 0, b1, b2, …, bm]T, trong đó n – m tọa độ đầu tiên đều bằng 0. Đây là một phương án cựcbiên. Một cách tổng quát, xét một phân rã tùy ý của ma trận A = [N B] với B là ma trận vuôngđược tạo nên từ m véc tơ cột độc lập tuyến tính của A, N là ma trận được tạo nên từ các véc tơ cộtcòn lại. Lúc đó, một phương án cực biên của BTQHTT tương ứng với sự phân rã trên của A là[TTmột phương án có dạng x = x N , x B]Ttrong đó xN = 0, xB ≥ 0. Ma trận B được gọi là ma trận cơsở tương ứng với x [có thể xem thêm về vấn đề phương án cực biên trong chương VI]. Như vậy,một phương án cực biên không có quá m tọa độ dương. Phương án cực biên có đúng m tọa độdương được gọi là phương án cực biên không suy biến, nếu trái lại, đó là phương án cực biên suybiến.3.2. Công thức số gia hàm mục tiêuXét BTQHTT [2.3] dạng chính tắc, giả sử x là phương án cực biên tương ứng với phân rãA = [N B], với B là ma trận cơ sở, còn x là một phương án khác. Đặt Δx = x – x là véc tơ sốgia các biến quyết định. Chúng ta tìm cách thiết lập công thức số gia hàm mục tiêu:cT x – cTx = cT[ x – x] = cTΔx.⎡ Δx ⎤Ta thấy ngay A x = Ax = b nên AΔx = 0. Ký hiệu Δx = ⎢ N ⎥ , ta có AΔx = 0 ⇔ [N⎣ Δx B ⎦⎡ Δx ⎤B] ⎢ N ⎥ = 0 ⇔ NΔxN + BΔxB = 0 ⇔ BΔxB = –NΔxN ⇔ ΔxB = B–1NΔxN.⎣ Δx B ⎦⎡ Δx ⎤ TTTTTTVậy cTΔx = [cN ,cB ] ⎢ N ⎥ = cN ΔxN + cB ΔxB = cN ΔxN – cB B–1NΔxNΔx B ⎦⎣TTTTTT= [ cN – cB B–1N]ΔxN = [ cN – cB B–1N]ΔxN + [ cB – cB B–1B]ΔxB⎡ Δx ⎤TTTT= [ cN – cB B–1N, cB – cB B–1B] ⎢ N ⎥ .⎣ Δx B ⎦TTTTĐặt Δ = [ cN – cB B–1N, cB – cB B–1B] = [ΔN, ΔB], thì cTΔx = Δ×Δx. Đây chính là công thứcsố gia hàm mục tiêu cần thiết lập.Quay lại ví dụ 2, trong bảng đơn hình bước 1, chúng ta có:−1−1⎡⎡1 0 ⎤ ⎡4 2 ⎤⎡1 0 ⎤ ⎡ 1 0 ⎤ ⎤Δ = ⎢[8,6] − [0,0] ⎢⎥ ⎢⎥ , [0,0] − [0,0] ⎢0 1 ⎥ ⎢0 1 ⎥ ⎥⎢⎣0 1 ⎦ ⎣ 2 4 ⎦⎣⎦ ⎣⎦⎥⎣⎦= [8, 6, 0, 0] = [Δ1, Δ2, Δ3, Δ4].25 Nhận xét. Có thể chứng minh được rằng Δ j =∂z, ∀j = 1, n. Chẳng hạn, tương ứng với∂x jbảng đơn hình bước 2 ta có: Δz = z[x + Δx] –z[x] = cT[x + Δx] – cTx = cTΔx = Δ Δx = Δ1Δx1 +Δ2 Δx 2+Δ4 Δx 4=0 Δx 1+2 Δx 2+[–2]Δx3+0 Δx 4 .[rằng,Δ3 Δx 3+]Rõràng∂z∂z∂z∂z= Δ1 = 0 ,= Δ2 = 2 ,= Δ3 = −2 ,= Δ4 = 0 .∂x1∂x 2∂x 3∂x 43.3. Tiêu chuẩn tối ưuTTXét phương án cực biên x của BTQHTT [2.3] dạng chính tắc: x = x N , x BT[tương ứngvới phân rã A = [N B], với B là ma trận cơ sở]. Lúc này, ∀ x ∈ D ta có:cT x ≤ cTx ⇔ cT x – cTx ≤ 0 ⇔ cTΔx ≤ 0.Vậy tiêu chuẩn để x là phương án tối ưu là: cTΔx ≤ 0, ∀Δx ⇔ Δ×Δx ≤ 0, ∀Δx⎡ Δx ⎤⇔ [ΔN, ΔB] ⎢ N ⎥ = ΔNΔxN + ΔBΔxB ≤ 0,∀Δx ⇔ ΔNΔxN ≤ 0,∀Δx [do ΔB = 0].⎣ Δx B ⎦Định lý 1. Xét BTQHTT [2.3] dạng chính tắc. Điều kiện đủ để một phương án cực biên x =[xTNT, xB]T[tương ứng với phân rã A = [N B], với B là ma trận cơ sở] là phương án tối ưu là ΔNTT= cN – cB B–1N ≤ 0. Ngược lại, nếu x là phương án cực biên tối ưu không suy biến thì ta cũng cóTTΔN = cN – cB B–1N ≤ 0.Chứng minhĐiều kiện đủ. Nếu ΔN ≤ 0, thì ΔNΔxN ≤ 0, ∀ x ∈ D, [chú ý rằng xN = 0 luôn đúng, nên cũngluôn có ΔxN = x N – xN ≥ 0]. Do ΔB = 0 nên ΔNΔxN + ΔBΔxB ≤ 0, ∀Δx hay Δ × Δx ≤ 0,∀Δx. VậycT x ≤ cTx, ∀ x ∈ D. Do đó x là phương án tối ưu.Điều kiện cần. Sử dụng phương pháp chứng minh phản chứng, giả sử x là phương án cựcbiên tối ưu không suy biến và điều kiện ΔN ≤ 0 không được thoả mãn. Lúc đó tồn tại chỉ số j* ∈JN sao cho Δj* > 0. Xét phương án x = x + Δx. Chúng ta sẽ chỉ ra cách xây dựng x sao cho x làphương án khả thi thỏa mãn cT x > cTx hay cTΔx < 0, từ đó suy ra x không phải là phương án tốiưu.Thật vậy, chọn ΔxN sao cho: Δxj = 0, ∀j ∈ JN, j ≠ j* và Δxj* = θ > 0.⎡ Δx ⎤Chọn ΔxB sao cho: AΔx = 0 ⇔[N B] ⎢ N ⎥ = 0 ⇔ NΔxN + BΔxB = 0 ⇔ BΔxB = –NΔxN⎣ Δx B ⎦⇔ ΔxB = –B–1NΔxN ⇔ ΔxB = –B–1θaj*.⎡4 2 ⎤ ⎡ Δx 1 ⎤⎡4 2 ⎤ ⎡ θ ⎤⎡4 ⎤Trong ví dụ 2, ta thấy: N Δ x N = ⎢⎥ × ⎢ Δx ⎥ = ⎢ 2 4 ⎥ × ⎢0 ⎥ = θ× ⎢2 ⎥ = θ× a 1 ,⎣2 4 ⎦ ⎣ 2 ⎦⎣⎦ ⎣ ⎦⎣ ⎦với j* = 1.26 Để x là phương án khả thi, cần phải có x ≥ 0. Dễ thấy x N ≥ 0 theo cách xây dựng ΔxN.Còn x B = xB + ΔxB = xB – B–1θaj* . Để x B ≥ 0 phải chọn θ theo quy tắc tỷ số dương bé nhất [nhưđã biết ở mục 2.1 khi mô tả thủ tục xoay].Trường hợp 1: B–1aj* ≤ 0. Lúc này, khi thực hiện “quy tắc tỷ số dương bé nhất” [lấy cộtphương án chia cho cột aj*] ta không nhận được một tỷ số nào có mẫu số dương. Để x B ≥ 0,chúng ta có thể chọn θ > 0 và lớn tuỳ ý. Do đó cTΔx = θ Δj* → +∞ khi chọn θ → +∞. Điều nàychứng tỏ phương án x không phải là phương án tối ưu và BTQHTT [2.3] dạng chính tắc có hàmmục tiêu không bị chặn trên.Trường hợp 2: Véc tơ B–1aj* có tọa độ dương. Để cho dễ hiểu, xét lại ví dụ 1 và bảng đơnhình II.1 [bước 2]. Do x1 và x4 là các biến cơ sở và j* = 2 nên:⎡4 0 ⎤⎡ 1 / 4 0⎤⎡ 1 / 4 0 ⎤ ⎡ 2 ⎤ ⎡1 / 2 ⎤–1–1B= ⎢⎥ ⇒ B = ⎢ −1 / 2 1 ⎥ ⇒ B aj* = ⎢ −1 / 2 1 ⎥ × ⎢4 ⎥ = ⎢ 3 ⎥ .⎣⎦ ⎣ ⎦ ⎣⎣2 1 ⎦⎣⎦⎦⎡15 ⎤⎡1 / 2 ⎤Vậy: x B = xB + ΔxB = xB – B–1θaj* = ⎢ ⎥ – θ× ⎢⎥≥0⇔⎣18 ⎦⎣ 3 ⎦⎧15 − [1 / 2]θ ≥ 0⎪⎨≥ 0.⎪18 − 3θ⎩⎧ 15 18 ⎫,Chọn θ = Min ⎨⎬ = 6 theo “quy tắc tỷ số dương bé nhất” sẽ đảm bảo x B ≥ 0.⎩1 / 2 3 ⎭Do x là phương án cực biên không suy biến nên xB > 0 kéo theo θ > 0. Cuối cùng, ta cóc Δx = Δ×Δx = ΔNΔxN + ΔBΔxB = ΔNΔxN = Δj* Δxj* = θ×Δj* > 0. Do đó, phương án x không thể làphương án tối ưu [đpcm].TNhận xét– Nếu tồn tại chỉ số i* ∈ JB sao cho xi* = 0 [như đã biết, phương án cực biên x lúc này đượcgọi là phương án cực biên suy biến], thì từ điều kiện x B = xB + ΔxB = xB – B–1θaj* ≥ 0 có thể xảyra trường hợp chọn được θ = 0. Do đó cTΔx = θΔj* = 0, tức là hai phương án x và x cho cùng mộtgiá trị hàm mục tiêu. Trong các trường hợp như vậy có thể xảy ra hiện tượng xoay vòng: Chẳnghạn, khi chuyển từ x sang x , rồi lại chuyển từ x sang một phương án x nào đó mà vẫn chưa cảithiện được giá trị của hàm mục tiêu. Sau đó, lại có thể xảy ra việc chuyển từ x về x. Như vậy quátrình giải BTQHTT theo thuật toán đơn hình sẽ bị “treo” tại vòng lặp x → x → x → x. Để khắcphục hiện tượng xoay vòng có thể áp dụng một số thủ tục tính toán. Cách đơn giản nhất là ápdụng quy tắc tỷ số dương bé nhất với sự bổ sung sau: Nếu có nhiều chỉ số ứng với tỷ số dương bénhất, thì chọn ngẫu nhiên một trong các chỉ số đó để xác định hàng xoay tương ứng.– Trong quá trình giải BTQHTT [2.3] dạng chính tắc khi xuất phát từ một phương án cựcbiên, bằng thủ tục xoay ta luôn chuyển từ phương án cực biên này sang phương án cực biên kháccho tới khi các dấu hiệu dừng được thỏa mãn [tức là khi tiêu chuẩn tối ưu được thỏa mãn hay khikết luận được BTQHTT đã cho có hàm mục tiêu không bị chặn trên].3.4. Thuật toán đơn hình cho bài toán quy hoạch tuyến tính dạng chính tắcXét BTQHTT dạng chính tắc:Max z = c1x1 + c2x2 + ... + cnxn + cn+1xn+1 + ... + cn+mxn+m27