Kỹ thuật tối ưu trong TNN - Một số kỹ thuật cụ thể

Kỹ thuật tối ưu trong TNN- Một số kỹ thuật cụ thểQuy hoạch tuyến tính trong TNNContentsPhân tích độ nhạy5Dạng chung của bài toán tuyến tính1Hình thành bài toán tuyến tính2Phương pháp hình học 3Phương pháp bảng đơn hình4Ứng dụng QHTT trong QH&QLNN7Chương trình tuyến tính đối ngẫu6Company Logowww.themegallery.comDạng chung của LPDạng tổng quát Max or min: ràng buộc cj: Hệ số hàm mục tiêu aij: Hệ số trong các biểu thức ràng buộc bj: hệ số vế bên phải của biểu thức ràng buộc (RHS)Ví dụ: Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0Hai dạng cơ bản của LPDạng chuẩn tắc (standard form) Max/ Min Ràng buộc Ví dụTất cả các biểu thức ràng buộc là đẳng thức ngoại trừ những biểu thức ràng buộc không âm tương ứng với biến quyết địnhTất cả hệ số RHS của biểu thức ràng buộc là không âm, bj ≥ 0Biến quyết định xj là không âmHàm mục tiêu hoặc là Max hoặc MinHai dạng cơ bản của LP2. Dạng chính tắc (canonical form) MaxRàng buộcTất cả các biến quyết định xj là không âmTất cả các biểu thức ràng buộc thuộc loại bất đẳng thức ≤ Hàm mục tiêu là MaxHai dạng cơ bản của LP3. Chuyển một mô hình tuyến tính về dạng mong muốnMax f(x) = Min [-f(x)]Bất đẳng thức ràng buộc dạng ≥ có thể chuyển thành dạng ≤ , bằng cách nhân với (-1) vào cả hai vế của bất đẳng thứcMột phương trình đẳng thức có thể thay thế bởi hai bất đẳng thức có dấu ngược nhau. Ví dụ, một phương trình g(x) = b có thể được thay thế bởi g(x) ≤ b và g(x) ≥ bMột bất đẳng thức có dấu giá trị tuyệt đối có thể được thay thế bẳng hai bất đẳng thức không có dấu tuyệt đối. Ví dụ |g(x)| ≤ b, có thể thay thế bởi g(x) ≤ b và g(x) ≥ -b.Để chuyển biểu thức ràng buộc dạng bất đẳng thức về dạng đẳng thức:Ràng buộc thuộc loại ≤ , một biến bù không âm (slack variable), s, được cộng vào vế bên trái của biểu thức tương ứngRàng buộc thuộc loại ≥ một biến dư không âm (surplus variable), s, được trừ bởi vế bên trái của biểu thức tương ứngVí dụ: Max z = 5x1 + 7x2 Với ràng buộc 3x1 + 4x2 ≤ 15 2x1 + 3x2 ≥ 6 x1, x2 ≥ 0Hai dạng cơ bản của LPHình thành bài toán LPVí dụ 1:Hai loại cây trồng được trồng trên diện tích đất tối đa là 200 ha. Chi phí cho cây trồng 1 là 3 đơn vị (tiền tệ)/ha, trong khi cho cây trồng 2 là 1 đơn vị/haLợi nhuận đạt được từ cây trồng 1 là 5 đơn vị/ha và từ cây trồng 2 là 2 đơn vi/haTổng số tiền có sẵn phân bổ cho 2 loại cây trồng là: 300 đơn vịTìm diện tích tối ưu cho mỗi loại cây trồng 1 và 2 để lợi nhuận thực đạt được tối đa?Hình thành bài toán LPVí dụ 2:Một khu công nghiệp dự kiến xây dựng, yêu cầu tối thiểu 10,000 m3 nước trong suốt một thời kỳ cụ thể. Nguồn nước này được cung cấp bởi hai nguồn:Tầng ngậm nước ngầm vàHồ chứa trên sôngTổng nồng độ chất rắn hòa tan (TDS) trong tầng ngậm nước và hồ chứa lần lượt là 980 và 100 mg/l (g/m3)Nồng độ TDS cho phép tối đa đối với nguồn nước vào sử dụng là 500 mg/l Do khả năng giới hạn của giếng nước ngầm và công trình khai thác nước từ hồ chứa nên lượng nước có thể được lấy tối đa từ hai nguồn lần lượt là nước ngầm: 6000m3 và hồ chứa: 10000m3 Hiện nay, quyết định vận hành là dựa vào việc tối thiểu số lượng nước được lấy từ hồ chứa chất lượng tốt hơn (nồng độ TDS thấp hơn) để tối đa chất lượng nước tốt này cho sử dụng tương laiTìm quyết định vận hành đó.Hình thành bài toán LPVí dụ 3:Trong dự án quy hoạch đô thị của một thành phố, yêu cầu cấp nước cho thành phố tăng tối thiểu tới 150x106 l/ngày vào cuối năm 2020 để đối phó với sự tăng trưởng dân số trong vùng.Dự án đó nhận dạng có 3 nguồn cấp nước khác nhau, cụ thể:+ Từ một con sông chảy qua thành phố, với chi phí thấp, chất lượng nước tốt , nhưng khả năng khai thác trong tương lai lại thấp (nguồn 1)+ Từ nguồn nước ngầm, chất lượng nước kém hơn (nguồn 2)+ Từ một con sông cách xa thành phố, với chi phí đắt (nguồn 3)Số liệu chi tiết của 3 nguồn này được liệt kê như sau:Tổng độ cứng cho phép của nước cấp vào thành phố là 600mg/lTìm lượng nước cần lấy từ mỗi nguồn sao cho đáp ứng yêu cầu nước tương lai của thành phố với chi phí tối thiểu, trong khi vẫn duy trì chất lượng của nước trong giới hạn cho phépNguồn 1Nguồn 2Nguồn 3Chi phí (1000$/106l/ngày)51020Nguồn nước có sẵn (106l/ngày)25120100Độ cứng (mg/l)1001150350Giải LP bằng phương pháp hình họcTất cả những mô hình tuyến tính 2 chiều (2 biến quyết định) đều có thể giải được bằng phương pháp hình họcPhương pháp hình học cho một cái nhìn bên trong về hình dạng của những mô hình tuyến tính và việc đạt được nghiệmGiúp chúng ta hiểu phương pháp đơn hình tốt hơnDự án tướiLượng nước tối đa: 1800 acre-feet/nămYêu cầu tìm diện tích tưới cho mỗi loại cây trồng để lợi nhuận đạt được tối đa.Biến quyết địnhxA = Diện tích cây trồng A nên trồng (acres)?xB = Diện tích cây trồng B nên trồng (acres)?1,800 acre feet = 2,220,267 m3400 acre = 1,618,742 m2Cây trồng ACây trồng BYêu cầu nước (Acre feet/acre)32Lợi nhuận thực ($/acre)300500Diện tích tối đa (acres)400600Ví dụ 4Giải LP bằng phương pháp hình họcVí dụ 4246810246810xA (100 acres)xB (100 acres)xB 0xA 0Giải LP bằng phương pháp hình họcVí dụ 4246810246810xA (hundreds acres)xB (hundreds acres)xB 0xA 0Z=3600=300xA +500xBZ=2000=300xA +500xBZ=1000=300xA +500xB(200, 600)Giải LP bằng phương pháp hình họcNghiệm không bị chặn (Unounded Solution)246810246810xA (hundreds acres)xB (hundreds acres)xA> 0xA 0unboundedBỏ ràng buộc 2 và 3 của ví dụ 4, hàm mục tiêu có thể tăng và không bị chặnGiải LP bằng phương pháp hình họcVô nghiệm hay nghiệm không khả thi (Infeasibility)246810246810xA (hundreds acres)xB (hundreds acres)xB 0xA 3000xB > 0Thay đổi ràng buộc 3 tới >= 3000, khi đó, không có phần giao của những ràng buộc tồn tại và nghiệm khả thi không thể đạt đượcGiải LP bằng phương pháp hình họcĐa nghiệm (Multiple Optima)Thay đổi hệ số hàm mục tiêu tới 200, khi đó hàm mục tiêu có cùng độ dốc với ràng buộc 3 và đa nghiệm tồn tại.246810246810xA (hundreds acres)xB (hundreds acres)xB 0xA 0Z=1800=300xA +200xB3xA +2 xB m: hệ phương trình bất địnhPhương pháp bảng đơn hìnhNhững khái niệm: Ví dụ:Hệ pt tất định: Số biến, n = 4; số phương trình m = 2Nghiệm có thể đạt được bằng cách:Đặt (n-m) biến = 0; và giải hệ pt với m biến chưa biếtví dụ x1 = 0 và x2 = 0, giải hệ pt với x3 và x4 chưa biết, khi đó:Biến x1 và x2 gọi là biến tự doBiến x3 và x4 gọi là biến cơ sởMax z = 2x1 + x2Với rằng buộc x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0Max z = 2x1 + x2Với rằng buộc x1 + x2 + x3 = 200 3x1 + x2 + x4 = 300 x1, x2, x3, x4 ≥ 0Phương pháp bảng đơn hìnhBiến cơ sở và biến tự do(n-m) biến quyến định được đặt = 0 biến tự dom biến quyết định còn lại, và giá trị của nó đạt được bằng giải hệ m phương trình với m ẩn số biến cơ sởPhương án cơ sở Phương án cơ sở đạt đươc bằng cách đặt (n-m) biến chưa biết bằng 0 và tiến hành giải những đẳng thức rằng buộc cho m biến còn lại. 1 tập biến cơ sở đạt được sẽ tạo nên 1 PACS tương ứngPhương án cơ sở khả thi (phương án cơ sở chấp nhận đươc): là phương án cơ sở đat được ứng với biến cơ sở nhận các giá trị không âm (≥ 0)Số phương án cơ cở có thể có:Ví dụn = 4; m = 2Số phương án cơ sở tối đa = 6Phương pháp bảng đơn hìnhVề mặt hình học:Phương án cơ sở: Điểm giao của 2 đường thẳng: các điểm cực trịPhương án cơ sở khả thi: Điểm góc của không gian nghiệm khả thix1x2x1 + x2 = 2003x1 + x2 = 300Điểm tối ưu (50,150)Vùng nghiệm khả thiPhương pháp bảng đơn hìnhThuật toán đơn hình Thuật toán tìm kiếm nghiệm tối ưu của bài toán LP tuân theo 2 điều kiện cơ bản:Điều kiện tối ưu: Điều kiện này đảm bảo rằng những phương án “không xấu” (so với phương án hiện hành) từng được xét đếnĐiều kiện khả thi: Điều kiện này đảm bảo rằng, xuất phát từ một phương án cơ sở khả thi, chỉ những phương án cở sở khả thi được liệt kê trong suốt quá trình tính toánPhương pháp bảng đơn hìnhThuật toán đơn hình: Chọn phương án cơ sở khả thi xuất phát: xuất phát từ bất cứ phương án cơ sở khả thi nào (thường lấy tại gốc tọa độ)Di chuyển từ một phương án cơ sở khả thi tới phương án cơ sở khả thi khác, vẫn duy trì tính khả thi và cải thiện hàm mục tiêu cho đến khi điểm tối ưu tìm đượcDi chuyển từ một phương án cơ sở khả thi tới phương án cơ sở khả thi khác bằng việc thay thế một trong những biến cơ sở với một biến tự do và tính toán những thay đổi tương ứng trong biến cơ sởBiến đi vào: Biến cơ sở mới được thay thế cho biến cơ sở cũBiến đi ra: Biến cơ sở cũ được loại bỏ để cho biến cơ sở mới thay vàoPhương pháp bảng đơn hìnhThuật toán đơn hình: Lựa chọn biến đi vào và biến đi raBiến đi vào: Điều kiện tối ưu: lựa chọn một biến đi vào có tiềm năng để cải thiện giá trị hiện hành của hàm mục tiêu.Biến đi vào được lựa chọn từ biến tự do trong dòng chứa hàm mục tiêu có hệ số âm lớn nhất cho bài toán tìm Max và hệ số dương lớn nhất cho bài toán tìm Min Độ lớn của hệ số hàm mục tiêu trình bày tốc độ thay đổi của hàm mục tiêu đó nhờ thay đổi một đơn vị trong biết quyết địnhTrong trường hợp có 2 hoặc nhiều hơn một biến đều thỏa mãn điều kiện chọn biến đi vào, khi đó có thể chọn tùy ý một trong số những biến đóPhương pháp bảng đơn hìnhThuật toán đơn hình: Lựa chọn biến đi vào và biến đi raBiến đi ra: Dựa trên điều kiện khả thi: chỉ những phương án cơ sở khả thi được liệt kê trong suốt quá trình tính toán Biến đi ra: biến cơ sở trong đó tương ứng có tỷ sối là nhỏ nhất (cho cả bài toán tìm Max và Min) Với tất cả aik > 0 aik: hệ số trong biểu thức ràng buộc tương ứng với cột có chứa biến đi vào xk bi: hằng số bên phải (RHS) của các biểu thức ràng buộcTrong trường hợp 2 hoặc nhiều hơn một biến đều thỏa mãn điều kiện chọn biến đi ra, khi đó có thể chọn tùy ý một trong số những biến đóPhương pháp bảng đơn hìnhThuật toán đơn hình: Lựa chọn biến đi vào và biến đi raCột tương ứng với biến đi vào gọi là cột xoayDòng tương ứng với biến đi ra gọi là dòng xoayPhần tử được đặt tại giao của cột xoay và dòng xoay được gọi là phần tử xoayPhương pháp bảng đơn hìnhThuật toán đơn hình: Tìm phương án cơ sở khả thi mớiGiá trị của những phần tử mới trong bảng đơn hình tương ứng với biến cơ sở và biến tự do mới được tính toán bằng phương pháp vận hành dòng (phương pháp Gauss-Jordan) Nguyên lý: Chuyển bảng đơn hình đi vào một bảng mới có giá trị là 1 tại phần tử xoay và giá trị là 0 tại những vị trí khác trong cột tương ứng với biến cơ sở mới, bao gồm cả dòng hàm mục tiêuVận hành cho dòng xoay:Dòng xoay mới = (Dòng xoay hiện tại) / (phần tử xoay)Vận hành cho các dòng còn lại (bao gồm cả dòng hàm mục tiêu)Dòng mới = (Dòng hiện tại) – (Hệ số của cột xoay của dòng hiện tại) x (Dòng xoay mới)Vận hành GaussGọi aij trong dòng i và cột j là phần tử xoayGiá trị của phần tử được đặt tại dòng k và cột l, là akl có thể được tính toán bằng công thức sau:akl’ = (aklaij – akjail)/aijPhương pháp bảng đơn hìnhPhương pháp bảng đơn hìnhKiểm tra điều kiện tối ưuPhương án cơ sở khả thi hiện tại là tối ưu khi và chỉ khi mọi hệ số trong dòng hàm mục tiêu không âm (≥0) cho bài toán tìm Maxvà không dương (≤ 0) cho bài toán tìm MinPhương pháp bảng đơn hình: Các bước giảiChuyển LP gốc về dạng chuẩn tắc và thành lập bảng đơn hình.Hàm mục tiêu được chuyển như sau:Chọn phương án cơ sở khả thi xuất phát: nhận dạng ma trận đơn vị(2) Xét hệ số của dòng hàm mục tiêu z, Nếu tất cả các phần tử trong dòng hàm mục tiêu đó là không âm (≥0) cho bài toán tìm Max và không dương (≤0) cho bài toán tìm Min, dừng tính toán, nghiệm tối ưu đã tìm được. Ngược lại, sang bước 3.(3) Lựa chọn biến đi vào: biến tự do trong dòng hàm mục tiêu có hệ số âm lớn nhất cho bài toán tìm Max và hệ số dương lớn nhất cho bài toán tìm Min. Cột chứa chứa biến tự do gọi là cột xoay.(4) Xét hệ số của cột xoay: Nếu tất cả hệ số này là không dương (≤0), nghiệm này là không biên. Nếu có ít nhất một phần tử là dương (>0), sang bước 5(5) Tính toán: với aik > 0 Biến cơ sở tương ứng với min(i), được chọn là biến đi ra Dòng tương ứng với min(i) gọi là dòng xoay(6) Thiết lập bảng đơn hình mới dựa trên vận hành dòng (Gauss-Jordan) Lặp lại bước 1 cho đến khi tìm được phương án cơ sở tối ưu. Phương pháp bảng đơn hình: ví dụGiải ví dụ 4 bằng phương pháp đơn hình z - 300x1 - 500x2 - 0.x3 - 0.x4 - 0.x5 = 0x1 + x3 = 400 (Giới hạn về diện tích đất cho cây trồng 1)x2 + x4 = 600 (Giới hạn về diện tích đất cho cây trồng 2)3x1 + 2x2 +x5 = 1800 (Giới hạn về diện tích đất cho cả 2 cây trồng) x1, x2, x3, x4,x5 ≥ 0 (Biến quyết định không âm)Số biến, n = 4; Số phương trình m = 2Số biến tự do = 2; Số biến cơ sở = 2Phương án cơ sở khả thi xuất phát: x1 = 0 và x2 = 0; x3= 200 và x4 = 300Tên biến cơ sởHệ số củax1x2x3x4x5RHS (bi)bi/aikx310100400-x401010600600x5320011800900z-300-5000000Bảng đơn hình xuất phátz - 300x1 - 500x2 - 0.x3 - 0.x4 - 0.x5 = 0x1 + x3 = 400 (Giới hạn về diện tích đất cho cây trồng 1)x2 + x4 = 600 (Giới hạn về diện tích đất cho cây trồng 2)3x1 + 2x2 +x5 = 1800 (Giới hạn về diện tích đất cho cả 2 cây trồng) x1, x2, x3, x4,x5 ≥ 0 (Biến quyết định không âm)Phương pháp bảng đơn hình: ví dụTên biến cơ sởHệ số củax1x2x3x4x5RHS (bi)bi/aikx310100400400x201010600-x5300-21600200z-300005000300000Bảng đơn hình thứ 2z - 300x1 - 500x2 - 0.x3 - 0.x4 - 0.x5 = 0x1 + x3 = 400 (Giới hạn về diện tích đất cho cây trồng 1)x2 + x4 = 600 (Giới hạn về diện tích đất cho cây trồng 2)3x1 + 2x2 +x5 = 1800 (Giới hạn về diện tích đất cho cả 2 cây trồng) x1, x2, x3, x4,x5 ≥ 0 (Biến quyết định không âm)Phương pháp bảng đơn hình: ví dụTên biến cơ sởHệ số củax1x2x3x4x5RHS (bi)bi/aikx30012/3-1/3200x201010600x1100-2/31/3200z000300100360000Bảng đơn hình thứ cuối cùngz - 300x1 - 500x2 - 0.x3 - 0.x4 - 0.x5 = 0x1 + x3 = 400 (Giới hạn về diện tích đất cho cây trồng 1)x2 + x4 = 600 (Giới hạn về diện tích đất cho cây trồng 2)3x1 + 2x2 +x5 = 1800 (Giới hạn về diện tích đất cho cả 2 cây trồng) x1, x2, x3, x4,x5 ≥ 0 (Biến quyết định không âm)Phương pháp bảng đơn hình: ví dụPhương án nghiệm tối ưu:x1 = 200; x2 = 600; x3 = 200; x4 = 0, x= = 0Z = 360000Phương pháp bảng đơn hình: Biến nhân tạoMax z = 5x1 + 8x2Ràng buộc2x1 + 3x2 ≥ 153x1 + 5x2 ≤ 60x1 + x2 = 18x1, x2 ≥ 0Dạng chính tắcMax z = 5x1 + 8x2Ràng buộc2x1 + 3x2 – x3 = 153x1 + 5x2 + x4 = 60x1 + x2 = 18x1, x2, x3, x4 ≥ 0 Phương án cơ sở khả thi xuất phát? (Biến cơ sở xuất phát)Biến nhân tạoTrong bài toán LP mà biểu thức ràng buộc có dạng ≥, chúng ta phải tìm kiếm một phương án cơ sở khả thi xuất phát để ứng dụng thuật toán đơn hình thông thườngPhương pháp nhân tạo đơn giản là một phép lừa toán học thông qua những biến nhân tạo, nhằm tạo khả năng ứng dụng thuật toán đơn hình thông thường để giải quyết bài toán LP Cho những biểu thức rằng buộc có dạng ≥, những rằng buộc được viết như sau: Cho những biểu thức rằng buộc có dạng =, chúng được viết lại như sau: Ri: Biến nhân tạo không âm (≥ 0)Phương pháp bảng đơn hình: Biến nhân tạoPhương pháp bảng đơn hình: Biến nhân tạoVí dụMax z = 5x1 + 8x2Ràng buộc2x1 + 3x2 ≥ 153x1 + 5x2 ≤ 60x1 + x2 = 18x1, x2 ≥ 0Dạng chính tắcMax z = 5x1 + 8x2Ràng buộc2x1 + 3x2 – x3 + R1 = 153x1 + 5x2 + x4 = 60x1 + x2 + R2 = 18x1, x2, x3, x4, R1, R2 ≥ 0 Để giải bài toán có biến nhân tạo, ứng dụng phương pháp đơn hình 2 giai đoạn (two-phase simplex method)Giai đoạn 1: Ứng dụng phương pháp đơn hình để tìm Min của hàm mục tiêu sau: Ràng buộc: Những biểu thức ràng buộc của mô hình gốc dưới dạng chính tắc (bao gồm cả biến nhân tạo) K: tổng số biến nhân tạo trong mô hình,Giai đoạn 2: Bắt đầu từ phương án cơ sở khả thi đã nhận dạng trong giai đoạn 1, ứng dụng phương pháp đơn hình để tối ưu bài toán gốcTrong trường hợp giai đoạn 1 kết thúc (nghĩa là tối ưu cho giai đoạn 1 đã đạt được), mà giá trị của W ≠ 0, khi đó bài toán gốc là vô nghiệmPhương pháp bảng đơn hình: Biến nhân tạoGiai đoạn 1Ví dụ 5Max z = 5x1 + 8x2Ràng buộc2x1 + 3x2 ≥ 153x1 + 5x2 ≤ 60x1 + x2 = 18x1, x2 ≥ 0Tìm Min W = R1 + R2Ràng buộc2x1 + 3x2 – x3 + R1 = 153x1 + 5x2 + x4 = 60x1 + x2 + R2 = 18x1, x2, x3, x4, R1, R2 ≥ 0 Dạng chuẩn tắcMax z = 5x1 + 8x2Ràng buộc2x1 + 3x2 – x3 + R1 = 153x1 + 5x2 + x4 = 60x1 + x2 + R2 = 18x1, x2, x3, x4, R1, R2 ≥ 0 Ví dụ sử dụng phương pháp biến nhân tạoBGiai đoạn 1Giải ví dụ 5 sử dụng phương pháp biến nhân tạoBảng đơn hình xuất phát cho giai đoạn 1Tên biến CSHệ số củax1x2x3x4R1R2RHSbik/aiR123-10101515/3x43501006060/5R21100011818/1W34-100033Z-5-800000Biến đi vàoBiến đi raBGiai đoạn 1Giải Ví dụ 5 sử dụng phương pháp biến nhân tạoBảng đơn hình cuối cùng cho giai đoạn 1Tên biến CSHệ số củax1x2x3x4R1R2RHSbik/aix111000118x4020110/3-36x30-110-1221W0000-1-10Z0-3000590Tên biến CSHệ số củax1x2x3x4RHSbik/aix111001818/1x4020166/2x30-11021-Z0-30090Bảng đơn hình xuất phát cho giai đoạn 2Giai đoạn 2BGiai đoạn 2Ví dụ sử dụng phương pháp biến nhân tạoTên biến CSHệ số củax1x2x3x4RHSbik/aix1100-1/215x20101/23x30011/224Z0003/299Bảng đơn hình cuối cùng cho giai đoạn 2Phương án nghiệm tối ưu:x1 = 15; x2 = 3; Z = 99(1) Nghiệm suy thoáiMột phương án nghiệm cơ sở khả thi là suy thoái nếu một vài biến cơ sở của nó có giá trị bằng 0Sự hiện diện của nghiệm suy thoái chỉ ra rằng có tới hai hoặc nhiều hơn những phương án cơ sở cho giá trị hàm mục tiêu là như nhauSự hiện diện của nghiệm suy thoái có thể dẫn tới một vài bước lặp bổ sung mà giá trị hàm mục tiêu vẫn không được cải thiệnPhương pháp bảng đơn hình: Một số trường hợp đặc biệtLặpBCSx1x2x3x4RHS0X314108X412014Z-3-90001X21/411/402X41/20-1/210Z-3/409/40182 (Nghiệm tối ưu)X2011/2-1/22X110-120Z003/23/218Phương án nghiệm không khả thi (vô nghiệm): Trong bài toán có biến nhân tạo, nếu kết thúc của giai đoạn 1, tổng của các biến nhân tạo > 0, khi đó phương án là không khả thi.Phương pháp bảng đơn hình: Một số trường hợp đặc biệtBCSx1x2x3x4R1RHS (b)R1-20-1-111X2010101W-20-1-101Z-900101(3) Nghiệm không bị chặn (nghiệm không biên): Nghiệm không bị chặn có thể nhận dạng nếu tại bất cứ bước lặp nào, bất cứ ứng cử viên nào cho việc lựa chọn biến đi vào có hệ số là ≤ 0 trong những biểu thức rằng buộcPhương pháp bảng đơn hình: Một số trường hợp đặc biệtTên biến cơ sởHệ số củax1x2x3x4RHS (bi)bi/aikx31-11010-x4200140-z-1-2000Đa nghiệm: Nếu một trong những biến tự do có hệ số là 0 trong dòng hàm mục tiêu, đa nghiệm xuất hiện Phương pháp bảng đơn hình: Một số trường hợp đặc biệtLặpBCSx1x2x3x4RHS0X312105X411014Z-2-40001 (Nghiệm tối ưu)X21/211/205/2X41/20-1/213/2Z0020102 (Nghiệm thay thế)X2011-11X110-123Z002010Phân tích độ nhạyMục đích: Tìm hiểu ảnh hưởng của những thay đổi trong dữ liệu của mô hình tuyến tính gốc vào nghiệm tối ưuNhững thay đổi có thể diễn ra trongNhững hệ số của hàm mục tiêuGiá trị bên phải của những rằng buộcNhận dạng tình trạng của nguồn và giá bóng của chúng Trong nhiều bài toán LP, hệ số RHS trình bày giới hạn của nguồn, đặc biệt cho những ràng buộc loại ≤ Ràng buộc không chặt (ràng buộc lỏng) (non-binding constraints): Khi bài toán LP gốc đạt nghiệm tối ưu, trong phương án nghiệm tối ưu đó tồn tại một biến phụ có giá trị ≠ 0, biểu thức ràng buộc tương ứng với biến phụ đó gọi là ràng buộc không chặt Ràng buộc không chặt mang hàm ý nguồn là dư thừa Ngược lại là ràng buộc chặt (binding constraints): Ràng buộc chặt mang hàm ý nguồn là khan hiếm Phân tích độ nhạy – Tình trạng của nguồnTên biến cơ sởHệ số củax1x2x3x4RHS (bi)bi/aikx2013/2-1/2150x110-1/21/250z001/21/2250Bảng đơn hình cuối cùngTừ ví dụ 1z - 2x1 - x2 - 0.x3 - 0.x4 = 0(1) x1 + x2 + x3 = 200 (Giới hạn về diện tích đất)(2) 3x1 + x2 + x4 = 300 (Giới hạn về quỹ) x1, x2, x3, x4 ≥ 0 (Biến quyết định không âm)Phương án nghiệm tối ưu:x1 = 50; x2 = 150; x3 = 0; x4 = 0Z = 250Ràng buộc chặt: 1 và 2“Nguồn” được sử dụng hết Trên một đơn vị giá trị của nguồn (Per unit worth of resources hoặc shadow price hoặc dual price)Trên một đơn vị giá trị của nguồn: Giá bóng (Shadow price): z/bi : tạo khả năng để ưu tiên phân bổ quỹ tương lai tới những nguồn khácRàng buộc không chặt tương ứng với nguồn là dư thừa: Một sư tăng hoặc giảm của một đơn vị nguồn sẽ không có bất cứ ảnh hưởng nào vào quyết định phân bổ tối ưu hiện hành, z/bi = 0Ràng buộc chặt tương ứng với nguồn là khan hiếm, khi đó mỗi đơn vị giá trị của nguồn (Giá bóng) không phải là bằng 0, z/bi ≠ 0Ví dụ z/b1 = 2 Ý nghĩa: Một sự tăng nguồn 1 bởi một đơn vị, sẽ gây ra một sự tăng trong giá trị hàm mục tiêu là 2 đơn vịThông tin này có thể được sử dụng để ưu tiên phân bổ tài chính bổ sung cho việc mở rộng quy mô hoặc vận hành Phân tích độ nhạy – Giá bóngTên biến cơ sởHệ số củax1x2x3x4RH