Toán học - Phương pháp đơn hình

Nội dung text: Toán học - Phương pháp đơn hình

1. PHƯƠNG PHÁP ĐƠN HÌNH 1
2. Các định lí cơ bản Ta gọi Là ước lượng của biến xk theo cơ sở J0 Định lí1: ( Dấu hiệu tối ưu của phương án cực biên) 0 Nếu đối với phương án cực biên x với cơ sở J0 của bài toán dạng chuẩn mà k 0 (k J0 ) đối với bài toán f(x) min thì x0 là phương án tối ưu 2
3. Định lí2: ( Dấu hiệu bài toán không giải được ) 0 Nếu đối với phương án cực biên x với cơ sở J0 của bài toán dạng chính tắc mà tồn tại k > 0 mà xjk 0 (k J0 ) đối với bài toán f(x) min hoặc: tồn tại k<0 mà xjk 0 (k J0 ) đối với bài toán f(x) max Thì bài toán ko giải được 3
4. Định lí3: ( Dấu hiệu điều chỉnh PACB) 0 Nếu đối với phương án cực biên x với cơ sở J0 của bài toán dạng chính tắc mà với mỗi k >0 đều tồn tại xjk > 0 đối với bài toán f(x) min thì ta có thể điều chỉnh PACB x0 để chuyển sang một PACB mới tốt hơn 4
5. 2. Phương pháp đơn hình cho bài toán QHTT: A. Thuật toán đơn hình cho bài toán QHTT dạng chuẩn: 5
6. Ví dụ Bảng đơn hình xuất phát Hệ số Ẩn cơ P Án 2 3 3 8 4 bản x1 x2 x3 x4 x5 8 x4 16 0 2 0 1 7 3 x3 4 0 5 1 0 2 2 x1 8 1 1 0 0 2 6 f(x0) 156 0 30 0 0 62
7. Hệ số Ẩn cơ Ph Án 2 3 3 8 4 bản x1 x2 x3 x4 x5 8 x4 16 0 2 0 1 7 3 x3 4 0 5 1 0 2 2 x1 8 1 1 0 0 2 f(x0) 156 0 30 0 0 62 8 x4 2 0 -31/2 -7/2 1 0 4 x5 2 0 5/2 1/2 0 1 2 x1 4 1 -4 -1 0 0 f(x’0) 32 0 -125 -31 0 0 Phương án tối ưu là x0 = (4,0,0,2,2); f(x0) = 32 7
8. a. Trường hợp bài toán min: Thuật toán: Bước 1: lập bảng đơn hình xuất phát. Hệ số Cơ sở Phương án c1 c2 cr . cm cm+1 cs cn c1 x1 b1 1 0 0 0 x1m+1 x1s x1n c2 x2 b2 0 1 0 0 x2m+1 x2s x2n cr xr br 0 0 1 0 xr n+1 xrs xr n cm xm bm 0 0 0 1 xm m+1 xms xmn f(x) f(x0) 0 0 0 0 8
9. Bước 2: Đánh giá tính tối ưu của PACB xuất phát x0 + Nếu thì x0 là PATƯ Ta có giá trị tối ưu là f(x0). Bài toán kết thúc. + Nếu tồn tại mà > 0 thì x0 không phải là PATƯ chuyển sang bước 3. Bước 3: Kiểm tra tính không giải được của bài toán. + Nếu tồn tại một s > 0 mà ajk 0, với i=1, ,m Thì bài toán không giải được vì hàm mục tiêu không bị chặn. + Nếu với mỗi s > 0 đều có ít nhất ajs > 0 thì chuyển sang bước 4. 9
10. Bước 4: điều chỉnh PACB. + Chọn vectơ đưa vào cơ sở. Tìm v= max{ j| j >0 j= 1,2, n} gọi xv là ấn thay thế (ẩn cơ bản mới) Tính Khi đó xr gọi là ẩn bị loại. Phần tử arv gọi là phần tử trục xoay. Lập bảng đơn hình mới nối tiếp vào bảng đơn hình cũ Tính lại hệ số mới và quay về bước 2 10
11. -Cách tính hệ số mới thực hiện như sau: -Cột r chuyển sang cột s các cột khác giữ nguyên - Chia tất cả các phần tử của hàng r cho phần tử trục ta được một hàng mới gọi là hàng chuẩn -Muốn có hàng i mới i 0 ta lấy phần tử trên hàng i cũ trừ đi tích của hàng chuẩn với aiv -Muốn có hàng cuối gồm f(x0) và j ta tính tương tự như trên hay tính như bước 1 -Sau bảng đơn hình mới ta có PACB mới x’0. Đối với x’0 quay trở lại bước 1 và lặp lại quá trình sau hữu hạn bước ta có kết luận bài toán. 11
12. b) Trường hợp bài toán Max: Bài toán 1: f(x) max. Giải bài toán 2: g(x) = - f(x) min gmin = g(x*) thì bài toán 1 có PATƯ là x* và fmax = - g(x*) Chú ý: f(x)max = - g(x)min 12
13. Ví dụ: 13
14. Bảng đơn hình xuất phát Hệ Ẩn cơ P Án -1 3 -3 1 0 0 0 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 0 x7 6 1 5 -5 0 0 0 1 -f(x0) 12 5 0 0 0 -1 0 0 -1 x1 3 1 3/4 -3/4 1/4 -1/4 0 0 0 x6 0 x7 -f(x0) 14
15. Hệ Ẩn cơ P Án -1 3 -3 1 0 0 0 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 0 x7 6 1 5 -5 0 0 0 1 -f(x0) 12 5 0 0 0 -1 0 0 -1 x1 3 1 3/4 -3/4 1/4 -1/4 0 0 0 x6 8 0 7/4 -7/4 1/4 -1/4 1 0 15
16. Hệ Ẩn cơ P Án -1 3 -3 1 0 0 0 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 0 x7 6 1 5 -5 0 0 0 1 -f(x0) 12 5 0 0 0 -1 0 0 -1 x1 3 1 3/4 -3/4 1/4 -1/4 0 0 0 x6 8 0 7/4 -7/4 1/4 -1/4 1 0 0 x7 3 0 17/4 -17/4 -1/4 1/4 0 1 -f(x0) 16
17. Hệ Ẩn cơ P Án -1 3 -3 1 0 0 0 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 0 x7 6 1 5 -5 0 0 0 1 -f(x0) 12 5 0 0 0 -1 0 0 -1 x1 3 1 3/4 -3/4 1/4 -1/4 0 0 0 x6 8 0 7/4 -7/4 1/4 -1/4 1 0 0 x7 3 0 17/4 -17/4 -1/4 1/4 0 1 -f(x0) -3 0 -15/4 15/4 -5/4 1/4 0 0 Do 3 > 0 x3 =(-3/4;-7/4;-17/4) < 0 nên bài toán có hàm mục tiêu ko giải được 17
18. Giải bài toán QHTT sau Bảng ĐH xuất phát Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 14 1 -8 0 0 1 -5 x3 2 0 -3 1 0 -1 1 x4 3 0 -2 0 1 -2 f(x0) 0 -9 0 0 1 18
19. Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 14 1 -8 0 0 1 -5 x3 2 0 -3 1 0 -1 1 x4 3 0 -2 0 1 -2 f(x0) 21 0 -9 0 0 1 4 x5 14 1 -8 0 0 1 -5 x3 1 x4 f(x’0) 19
20. Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 14 1 -8 0 0 1 -5 x3 2 0 -3 1 0 -1 1 x4 3 0 -2 0 1 -2 f(x0) 21 0 -9 0 0 1 4 x5 14 1 -8 0 0 1 -5 x3 16 1 -11 1 0 0 1 x4 f(x’0) 20
21. Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 14 1 -8 0 0 1 -5 x3 2 0 -3 1 0 -1 1 x4 3 0 -2 0 1 -2 f(x0) 21 0 -9 0 0 1 4 x5 14 1 -8 0 0 1 -5 x3 16 1 -11 1 0 0 1 x4 31 2 -18 0 1 0 f(x’0) 21
22. Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 14 1 -8 0 0 1 -5 x3 2 0 -3 1 0 -1 1 x4 3 0 -2 0 1 -2 f(x0) 21 0 -9 0 0 1 4 x5 14 1 -8 0 0 1 -5 x3 16 1 -11 1 0 0 1 x4 31 2 -18 0 1 0 f(x’0) 7 -1 -1 0 0 0 Phương án tối ưu cần tìm là: x*=(0,0,16,31,14) với f(x*)= 7 22
23. Thuật toán đơn hình mở rộng Mục đích: Giải bài toán QHTT có ẩn giả. Bài toán này xuất hiện khi chuyển bài toán dạng chính tắc về bài toán dạng chuẩn bằng cách đưa vào ẩn giả để tạo ma trận đơn vị. 23
24. Ví dụ: Giải bài toán QHTT sau Trong ma trận các hệ số đã có A1 là véc tơ đơn vị nên chỉ cần đưa vào 2 ẩn giả là x6 và x7 ứng với 2 phương trình cuối ta có bài toán phụ sau 24
25. Hệ Ẩn cơ P Án 0 0 0 0 0 1 1 số bản x1 x2 x3 x4 x5 x6 x7 0 x1 3 1 -4 2 -5 9 0 0 1 x6 6 0 1 -3 4 -5 1 0 1 x7 1 0 1 -1 (1) -1 0 1 F(x, w) 0 2 -4 5 -6 0 0 0 x1 8 1 1 -3 0 4 0 1 x6 2 0 -3 (1)1 0 -1 1 10 x4 1 0 1 -1 (1) -1 0 1 F(x, w) 0 -3 1 0 -1 0 26
26. 0 0 0 0 0 1 1 Hệ Ẩn cơ P Án 2 6 -5 1 4 1 1 số bản x1 x2 x3 x4 x5 x6 x7 0 x1 8 1 1 -3 0 4 0 1 x6 2 0 -3 (1) 0 -1 1 1 x4 1 0 1 -1 (1) -1 0 F(x, w) 0 -3 1 0 -1 0 2 0 x1 14 1 -8 0 0 (1) -5 0 x3 2 0 -3 1 0 -1 1 0 x4 3 0 -2 0 1 -2 F(x, w) 0 0 0 0 0 0 -9 0 0 1 f(x) 27
27. 0 0 0 0 0 1 1 Hệ Ẩn cơ P Án 2 6 -5 1 4 0 0 số bản x1 x2 x3 x4 x5 x6 x7 2 0 x1 14 1 -8 0 0 (1) -5 0 x3 2 0 -3 1 0 -1 1 0 x4 3 0 -2 0 1 -2 F(x, w) 0 0 0 0 0 0 -9 0 0 1 f(x) 4 0 x5 14 1 -8 0 0 1 -5 0 x3 16 1 -11 1 0 0 1 0 x4 31 2 -18 0 1 0 f(x) 7 -1 -1 0 0 0 28
28. Bài tập : Giải bài toán QHTT sau Đưa vào các ẩn phụ x4,x5 0 để đưa bài toán về dạng chính tắc. Đưa vào 2 ẩn giả x6, x7 0 đồng thời nhân 2 vế của ràng buộc 1,3 trong ràng buộc dấu sao cho vế phải không âm để được bài toán chuẩn 29
29. Giải bài toán phụ sau Việc tính toán thể hiện trong bảng dưới đây 30
30. Hệ Ẩn cơ P Án 0 0 0 0 0 1 1 số bản 7 1 -4 0 0 0 0 x1 x2 x3 x4 x5 x6 x7 0 x4 20 6 -4 -5 1 0 0 0 1 x6 8 1 (2) 1 0 0 1 0 1 x7 8 -3 2 1 0 -1 0 1 F(x, w) -2 4 2 0 -1 0 0 0 0 x4 36 8 0 -3 1 0 0 1 0 x2 4 1/2 1 (½) 0 0 0 0 1 x7 0 -4 0 0 0 -1 1 F(x, w) -4 0 0 0 -1 0 f(x) -13/2 0 9/2 0 0 0 31
31. Hệ Ẩn cơ P Án 0 0 0 0 0 1 1 số bản 7 1 -4 0 0 0 0 x1 x2 x3 x4 x5 x6 x7 0 0 x4 36 8 0 -3 1 0 0 1 0 x2 4 1/2 1 (½) 0 0 0 0 1 x7 0 -4 0 0 0 -1 1 F(x, w) -4 0 0 0 -1 0 f(x) -13/2 0 9/2 0 0 0 0 0 x4 60 11 6 0 1 0 0 -4 0 x3 8 1 2 1 0 0 0 0 1 x7 0 -4 0 0 0 -1 1 f(x) -32 -11 -9 0 0 0 0 Phương án tối ưu là x0 = (0,0,8); f(x0) = - 32 32