›
›

Bài giảng Toán tài chính - Chương 5B: Quy hoạch tuyến tính hai biến + …

pdf 78 trang Đức Chiến 04/01/2024 200
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán tài chính - Chương 5B: Quy hoạch tuyến tính hai biến + …", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_tai_chinh_chuong_5b_quy_hoach_tuyen_tinh_hai.pdf

Nội dung text: Bài giảng Toán tài chính - Chương 5B: Quy hoạch tuyến tính hai biến + …

  1. QUY HOẠCH TUYẾN TÍNH CHƯƠNG HAI BIẾN + 5B
  2. VÍ DỤ 1 Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền lãi cho một bánh mỗi loại được cho trong bảng sau: Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho không bị động về nguyên liệu mà lãi đạt được cao nhất.
  3. VÍ DỤ 1 Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập cẩm, bánh dẻo cần phải sản xuất. Điều kiện: xj ≥ 0 = 1,2,3 Tiền lãi thu được (ngàn đồng) f x f x1, x 2 , x 3 3 x 1 2 x 2 2,5 x 3 Lượng đường sử dụng và điều kiện: 0,04x1 0,06 x 2 0,05 x 3 500 Lượng đậu sử dụng và điều kiện: 0,07x1 0,02 x 3 300
  4. VÍ DỤ 1 Vậy ta có mô hình bài toán: f x f x1, x 2 , x 3 3 x 1 2 x 2 2,5 x 3 max 0,04x 0,06 x 0,05 x 500 1 2 3 0,07x1 0,02 x 3 300 xj 0 j 1,2,3 Đây là bài toán quy hoạch tuyến tính 3 biến, tìm giá trị lớn nhất của hàm mục tiêu.
  5. VÍ DỤ 2 Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng đạm, đường, khoáng cho một loại gia súc tương ứng là 90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại được cho trong bảng sau: Hãy lập mô hình toán học của bài toán xác định khối lượng thức ăn mỗi loại phải mua để tổng số tiền chi cho mua thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi ngày.
  6. VÍ DỤ 3 Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau: Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao động tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.
  7. VÍ DỤ 4 Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả sử, đối với: Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m ván Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất.
  8. BÀI TOÁN QHTT TỔNG QUÁT 1 f x c1 x 1 c 2 x 2 cn x n min (max) 2a x a x a x b i 1,2, , m i1 1 i 2 2 in n i 0 3x 0 j 1,2, , n j tuy y (1) Hàm f(x) gọi là hàm mục tiêu (2) là hệ ràng buộc chính (3) là hệ ràng buộc dấu (2) Và (3) gọi chung là hệ ràng buộc của bài toán
  9. DẠNG MA TRẬN CỦA BÀI TOÁN QHTT Xét bài toán QHTT dạng: f x c1 x 1 c 2 x 2 cn x n min (max) a11 x 1 a 12 x 2 a 1n x n b 1 a21 x 1 a 22 x 2 a 2n x n b 2 am1 x 1 a m 2 x 2 a mn x n b m x j 0
  10. DẠNG MA TRẬN CỦA BÀI TOÁN QHTT Đặt: a11 a 12 a 1n b1 x 1 c 1 a a a b x c A 21 22 2n b 2 x 2 c 2 am1 a m 2 a mn bm x n c n Ta có dạng ma trận của bài toán QHTT: f cT x min max Ax b x 0
  11. BÀI TOÁN DẠNG CHÍNH TẮC: n f x  cj x j min (max) • Các ràng buộc j 1 chính đều là n phương trình aij x j bi (i 1,m) • Các ẩn đều j 1 không âm xj 0 (j 1,n) Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia
  12. BÀI TOÁN DẠNG CHUẨN TẮC n f x c x min (max) • Các hệ số tự do bi  j j j 1 không âm (b ≥ 0) i n • Trong ma trận hệ số aij x j bi (i 1,m) có đủ m vecto cột j 1 đơn vị: e1, e2, ,em xj 0 (j 1,n) 1 0 0 0 1 0 e e e 1 2 m 0 0 1
  13. VÍ DỤ 5 Bài toán sau có dạng chính tắc: 260x1 120 x 2 600 x 3 max 2x1 x 2 3 x 3 500 100x1 40 x 2 250 x 3 40000 6x1 x 2 x1, x 2 , x 3 0
  14. VÍ DỤ 6 Xét bài toán QHTT sau: f x 2 x1 4 x 2 x 3 6 x 4 max x1 x 4 x 5 12 12x1 x 3 x 6 3 x x x x 6 1 2 3 4 xj 0 j 1,2, ,6 Bài toán trên có dạng chính tắc hay chuẩn tắc
  15. VÍ DỤ 6 Ma trận hệ số tự do: • Ma trận hệ số A: 12 1 0 0 1 1 0 A 12 0 1 0 0 1 b 3 6 1 1 1 1 0 0 e3 e1 e2 • Ẩn cơ bản thứ nhất là x5. • Ẩn cơ bản thứ 2 là x6. • Ẩn cơ bản thứ 3 là x2.
  16. CÁC LOẠI PHƯƠNG ÁN Định nghĩa. Vec tơ ∈ thỏa tất cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được. Định nghĩa. Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ nhất (nếu là bài toán min) thì được gọi là phương án tối ưu (PATU).
  17. VÍ DỤ 7 Cho bài toán QHTT: f x 120 x1 100 x 2 max 2x1 3 x 2 8 5x1 3 x 2 15 x1 0, x 2 0 Trong các phương án sau phương án nào là phương án chấp nhận được. 1 2 1 2 u1 u 2 u 3 u 4 2 2 3 1
  18. PHƯƠNG ÁN CƠ BẢN Trong bài toán chính tắc. Xét phương án x x1, x 2 , , xn Hệ vectơ liên kết với phương án A Aj| x j 0 Trong đó Aj là vec tơ cột thứ j trong ma trận hệ số Amn Định nghĩa. Phương án cơ bản nếu hệ vecto liên kết với phương án độc lập tuyến tính Ẩn xj gọi là cơ bản nếu > 0
  19. PACB TRONG BÀI TOÁN CHUẨN TẮC Cho ẩn cơ bản thứ k bằng hệ số tự do thứ k, còn các ẩn không cơ bản bằng 0, nghĩa là: x1 0; x 2 6; x 3 0; x 4 0; x 5 12; x 6 3 Ta được một phương án cơ bản x = (0,6,0,0,12,3) . Phương án này không suy biến vì có đủ 3 thành phần dương. Đây là phương án cơ bản ban đầu của bài toán. Tổng quát, trong bài toán QHTT dạng chuẩn bất kì, khi cho ẩn cơ bản thứ k bằng hệ số tự do thứ k ( k = 1,2, ,m ), còn các ẩn không cơ bản bằng 0, ta được phương án cơ bản ban đầu của bài toán. Nếu sắp xếp lại ta có dạng sau. 0 x b1, b 2 , , bm ,0,0, ,0
  20. ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC Bước 1. Kiểm tra ràng buộc chính • Ràng buộc dạng nhỏ hơn: • ai1 x 1 a i 2 x 2 a in x n b i • Ta cộng thêm ẩn phụ: ai1 x 1 a i 2 x 2 a in x n x n k b i • Ràng buộc dạng lớn hơn: ai1 x 1 a i 2 x 2 a in x n b i • Ta trừ đi ẩn phụ: ai1 x 1 a i 2 x 2 a in x n x n k b i
  21. ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC Bước 2. Kiểm tra điều kiện dấu các ẩn số Nếu có ẩn dạng: x i 0 ta đổi biến: xi x i Nếu ẩn xi có dấu tùy ý ta đổi biến: xi x i x i Chú ý: Các ẩn mới và các ẩn phụ đều không âm. Hệ số của các ẩn phụ trong hàm mục tiêu là 0. Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ được PATU của bài toán dạng tổng quát đã cho.
  22. VÍ DỤ 8 Đưa bài toán sau về dạng chính tắc: f x 2 x1 4 x 2 x 3 min 4x1 6 x 2 3 x 3 12 7x1 x 3 3 2x1 3 x 2 5 x 3 6 x1 0, x 2 0
  23. VÍ DỤ 8 Đáp án: f x 2 x1 4 x 2 x 3 x 3 min 4x1 6 x 2 3 x 3 x 3 x 4 12 7x1 x 3 x 3 x 5 3 2x1 3 x 2 5 x 3 x 3 6 x 0, x 0, x 0, x 0 1 2 3 3 x 0, x 0 4 5
  24. PHƯƠNG PHÁP HÌNH HỌC (ĐỒ THỊ) Sinh viên tham khảo thêm lý thuyết sách College Mathematics for Busines – Raymond A. Barnett Chương 5 phần Linear Programing Chỉ dùng cho bài toán quy hoạch tuyến tính 2 biến
  25. PHƯƠNG PHÁP ĐỒ THỊ Xét bài toán quy hoach tuyến tính : 2 f x  cj x j min max j 1 2  aij x j b i j 1
  26. PHƯƠNG PHÁP ĐỒ THỊ Biểu diễn các ràng buộc lên đồ thị Oxy. Xác định phần được giới hạn bởi các ràng buộc là tập phương án. Xác định các điểm cực biên (đỉnh) của tập phương án thỏa mãn các ràng buộc. Xác định giá trị của hàm mục tiêu tại các điểm cực biên. So sánh và suy ra phương án tối ưu
  27. VÍ DỤ 9. BÀI TOÁN KẾ HOẠCH SẢN XUẤT Một nhà sản xuất lều sử dụng trên các vùng núi có 2 dòng sản phẩm: tiêu chuẩn và thám hiểm. Mỗi lều tiêu chuẩn yêu cầu 1 giờ công lao động từ bộ phận cắt và 3 giờ công từ bộ phận lắp ráp. Mỗi lều thám hiểm đòi hỏi 2 giờ công lao động từ bộ phận cắt và 4 giờ làm việc từ bộ phận lắp ráp. Số giờ lao động tối đa có sẵn mỗi ngày trong các phòng cắt và lắp ráp lần lượt là 32 và 84. Nếu công ty thu được mức lợi nhuận $50 cho mỗi lều tiêu chuẩn và 80$ cho mỗi lều thám hiểm, thì mỗi ngày nên sản xuất bao nhiêu lều mỗi loại để tối đa hóa tổng lợi nhuận hàng ngày (giả sử rằng tất cả các lều có thể được bán)?
  28. MÔ HÌNH BÀI TOÁN Gọi x, y lần lượt là số lều tiêu chuẩn và thám hiểm f x, y 50x 80 y P max x 2y 32 3x 4y 84 x 0, y 0
  29. TẬP PHƯƠNG ÁN x 2y 32 3x 4y 84 x 0,y 0 •Ta có thể tính toán được lợi nhuận tại từng điểm nằm trong miền khả thi (feasible region) hay tập phương án •Tại (x,y)=(12,10) ta có P=1400 •Tại (x,y)=(23,2) ta có P=1310
  30. ĐƯỜNG ĐẲNG LỢI Gán cho P một giá trị cố định và vẽ đồ thị P=50x+80y trên hệ trục tọa độ Oxy ta có được một đường thẳng. Đường này có tên là constant profit line hay đường đẳng lợi. Mọi điểm thuộc tập phương án và nằm trên đường này đều cho ta một kế hoạch sản xuất và có cùng lợi ích P như nhau. Với mỗi giá trị khác nhau của P ta có một đường đẳng lợi khác song song với đường đẳng lợi còn lại, vì có chung hệ số góc. Để thuận tiện ta đưa phương trình đường đẳng lợi về dạng: 5 P P 50 x 80 y y x 8 80
  31. ĐƯỜNG ĐẲNG LỢI 5 P y x 8 80 Pmax y max Lợi nhuận lớn nhất sẽ nằm tại điểm mà đường đẳng lợi xa nhất so với gốc tọa độ nhưng vẫn còn nằm trong miền khả năng. Trong ví dụ này thì nó chính là điểm (20,6) Profit max: P=20.50+6.80=1480 Nhận xét. PATU nằm tại các điểm góc (corner points) của tập phương án
  32. VÍ DỤ 10 Đối với tập phương án như hình vẽ (A) Cho P = x + y. Vẽ đồ thị các đường đẳng lợi thông qua các điểm (5, 5) và (10, 10). Đặt đường thẳng dọc theo đường có lợi nhuận nhỏ hơn và trượt theo hướng tăng lợi nhuận, mà không làm thay đổi độ dốc của nó. Giá trị tối đa của P là bao nhiêu? Giá trị tối đa này xảy ra ở đâu? (B) Lặp câu (A) cho P = x + 10y. (C) Lặp câu (A) cho P = 10x + y
  33. CÁC ĐỊNH LÝ Định lý 1. Nếu bài toán quy hoạch tuyến tính có PATU thì PATU là một trong các PACB của tập phương án. Định lý 2. (Về sự tồn tại phương án tối ưu) A) Nếu tập phương án của bài toán QHTT bị chặn thì cả bài toán min và max đều có PATU B) Nếu tập phương án không bị chặn và các hệ số của hàm mục tiêu đều dương thì bài toán min có PATU nhưng bài toán max không có PATU C) Nếu tập phương án của bài toán rỗng thì cả bài toán min và max đều không có PATU
  34. TÌM PATU BẰNG PP ĐỒ THỊ
  35. VÍ DỤ 11A Z max = 28 Z min = 15
  36. VÍ DỤ 11B Z min = 160 Không có max
  37. VÍ DỤ 12 Giải bài toán QHTT sau: f x1, x 2 x 1 x 2 min 2x1 x 2 2 1 x1 x 2 2 2 x1 x 2 5 3 x1 0, x 2 0
  38. VÍ DỤ 13 Biểu diễn đồ thị các bất đẳng thức lên hệ trục tọa độ ta được miền các phương án là hình ngũ giác ABCDE. C Các điểm có tọa độ như sau A(0,0); B(0,2); C(1,4); D(4,1); E(2,0) là các B D điểm cực biên. lần lượt thay các cực A E biên vào hàm mục tiêu ta có f(A) = 0; f(B) = 2; f(C) = 3; f(D) = -3; f(E) = -2. Vậy phương án tối ưu x*=(4,1) tại đó hàm mục tiêu đạt giá trị Min
  39. VÍ DỤ 14 Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu 100 mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ chính quyết định sản lượng kế hoạch. Thợ rèn có 2000 công, thợ sắt có 3000 công, thợ mộc có 1500 công. Định mức lao động của mỗi loại tàu được cho trong bản: 100 mã lực 50 mã lực Thợ sắt (3000) 150 70 Thợ rèn (2000) 120 50 Thợ mộc 80 40 Hỏi xí nghiệp nên(1500)đóng tàu mỗi loại bao nhiêu để đạt tổng số mã lực cao nhất?
  40. VÍ DỤ 14 Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã lực cần đóng Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2 max Điều kiện: 150x1 70x 2 3000 120x1 50x 2 2000 80x1 40x 2 1500 x1 0, x 2 0
  41. VÍ DỤ 15 Một xí nghiệp có thể sử dụng tối đa 510 giờ máy cán, 360 giờ máy tiện, 150 giờ máy mài để chế tạo 3 loại sản phẩm A, B, C. Để chế tạo một đơn vị sản phẩm A cần 9 giờ máy cán, 5 giờ máy tiện, 3 giờ máy mài; 1 đơn vị sản phẩm B cần 3 giờ máy cán, 4 giờ máy tiện; 1 đơn vị sản phẩm C cần 5 giờ máy cán. 3 giờ máy tiện, 2 giờ máy mài. Mỗi sản phẩm A trị giá 48 ngàn đồng, mỗi sản phẩm B trị giá 16 ngàn đồng, mỗi sản phẩm C trị giá 27 ngàn đồng. Vấn đề đặt ra là xí nghiệp cấn chế tạo bao nhiêu đơn vị sản phẩm mỗi loại để tổng giá trị sản phẩm xí nghiệp thu được là lớn nhất, với điều kiện không dùng quá số giờ hiện có của mỗi loại máy.
  42. VÍ DỤ 16 Một xí nghiệp điện cơ sản xuất quạt điện các loại. Cần cắt từ một tấm tôn các cánh quạt điện theo 3 kiểu A, B, C. Có 6 mẫu cắt khác nhau theo bảng sau: Mẫu cắt Kiểu cánh quạt 1 2 3 4 5 6 A 2 1 1 0 0 0 B 0 1 0 2 1 0 C 0 0 1 0 2 3
  43. PHƯƠNG PHÁP ĐƠN HÌNH Simplex method Xuất phát từ một PACB đầu tiên, tìm cách đánh giá PACB ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang một PACB mới tốt hơn. Quá trình được lặp lại vì số PACB là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì hàm mục tiêu không bị chặn hoặc sẽ tìm được phương án tối ưu. Do nhà toán học George Benard Danzig đưa ra năm 1947
  44. PHƯƠNG PHÁP ĐƠN HÌNH 1) Tìm một phương án cực biên (phương án cơ bản) 2) Xét xem PACB này đã là PATU hay chưa. Nếu đã tối ưu thì kết thúc. Ngược lại chuyển sang bước 3. 3) Tìm phương án cực biên liền kề tốt hơn PACB đang xét 4) Quay về bước 2.
  45. VÍ DỤ 17 Xét bài toán dạng chuẩn tắc f x x1 2x2 3x3 2x4 min 2x1 3x2 x3 4 x1 x2 x4 5 x j 0 Ta có: 2 3 1 0 4 A B 1 1 0 1 5
  46. VÍ DỤ 17 f x x1 2x2 3x3 2x4 2 3 1 0 4 A B 1 1 0 1 5 Ẩn cơ bản: x3, x4 Phương án cơ bản: x1=x2=0; x3=4; x4=5 x0 0,0,4,5 f x0 2 Ta có: 2x1 3x2 x3 4 x3 4 2x1 3x2 x1 x2 x4 5 x4 5 x1 x2 x j 0 x j 0
  47. VÍ DỤ 17 Ta đánh giá f(x) như sau: f x x1 2x2 3x3 2x4 f x x1 2x2 3 4 2x1 3x2 2 5 x1 x2 0 f x 2 3x1 9x2 f x 1x1 2 x2 Bài toán min nên với f x 2 3x1 9x2 Ta chưa đánh giá được giá trị nhỏ nhất của f f x 2 3x1 9x2 A
  48. VÍ DỤ 17 Thử chọn x1, x4 làm ẩn cơ bản. Cho x2, x3=0 ta có 2x1 4 x1 2 x1 x4 5 x4 3 Phương án cơ bản: x0 2,0,0,3 Ta có: 3 1 x 2 x x 1 2 2 2 3 2x1 3x2 x3 4 5 1 x1 x2 x4 5 x4 3 x2 x3 2 2 x j 0 x j 0
  49. VÍ DỤ 17 Ta đánh giá f(x) như sau: f x x1 2x2 3x3 2x4 9 3 f x 4 x x 2 2 2 3 Dễ thấy: f x 4 Vậy phương án tối ưu: x* 2,0,0,3
  50. CHÚ Ý 0 Tổng quát ta có: f x f x  k xk Ẩn không cơ bản xk 0 Với x0 là phương án cơ bản + Nếu bài toán min thì ta cần Delta dương + Nếu bài toán max thì ta cần Delta âm Trong PP đơn hình phía sau thì Delta trong bảng đơn hình ngược dấu với Delta ở đây.
  51. PHƯƠNG PHÁP ĐƠN HÌNH
  52. BẢNG ĐƠN HÌNH n  Cách tính Delta một cột:  Lấy hệ số cột ngoài cùng bên trái bảng Δ j ciaij c j   Nhân với hệ số cột cần tính i 1  Trừ đi giá trị trên đầu cột cần tính n f x c b  Cách tính giá trị f(x):  i i  Lấy cột hệ số nhân cột P. Án i 1
  53. DẤU HIỆU VỀ PHƯƠNG ÁN TỐI ƯU 0 1. Nếu ∆k ≤ 0 thì x là phương án tối ưu. 2. Nếu tồn tại một ∆k > 0 mà ajk ≤ 0 thì bài toán không có phương án tối ưu. 3. Nếu tất cả ∆k > 0 và tồn tại ajk > 0 thì ta có thể tìm được phương án tốt hơn trong trường hợp bài toán không suy biến.
  54. CÁC BƯỚC THỰC HIỆN
  55. CÁC BƯỚC THỰC HIỆN Nhớ phép biến đổi sơ cấp trên dòng đối với ma trận. Tương tự như khi đi tìm hạng của ma trận khi biến đổi về dạng bậc thang.
  56. VÍ DỤ 18 2 4 3 1 0 0 52 A 4 2 3 0 1 0 b 60 3 0 1 0 0 1 36
  57. VÍ DỤ 18 f x 5x1 4x2 5x3 2x4 x5 3x6 Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản 5 4 5 2 1 3 2 4 3 1 0 0 52 A 4 2 3 0 1 0 b 60 3 0 1 0 0 1 36
  58. VÍ DỤ 18 f x 5x1 4x2 5x3 2x4 x5 3x6 Ẩn cơ x1 x2 x3 x4 x5 x6 Hệ số PA bản 5 4 5 2 1 3 2 x4 52 2 4 3 1 1 0 1 x5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 2 4 3 1 0 0 52 A 4 2 3 0 1 0 b 60 3 0 1 0 0 1 36
  59. VÍ DỤ 18 f x 5x1 4x2 5x3 2x4 x5 3x6 Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản 5 4 5 2 1 3 2 X4 52 2 4 3 1 1 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0 2 52 2 4 0 f x 1 60 272 2 1 2 4 6 3 36 3 0
  60. VÍ DỤ 18 f x 5x1 4x2 5x3 2x4 x5 3x6 Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản 5 4 5 2 1 3 2 X4 52 2 4 3 1 1 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0 2 2 2 4 1 1 4 5 12 1 1 2 4 6 3 3 3 0 2 4 3 1 0 0 52 A 4 2 3 0 1 0 b 60 3 0 1 0 0 1 36
  61. ĐÁNH GIÁ Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản 5 4 5 2 1 3 2 X4 52 2 4 3 1 1 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0 Giá trị lớn nhất nằm ở cột x1 52 : 2 16 60 : 4 15 Giá trị nhỏ nhất nằm ở hàng x6 36 :3 12 Vậy đưa biến x1 vào thay cho biến x6
  62. BẢNG MỚI Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản 5 4 5 2 1 3 2 X4 52 2 4 3 1 0 0 1 X5 60 4 2 3 0 1 0 3 x6 36 3 0 1 0 0 1 272 12 6 7 0 0 0 2 X4 28 0 4 7/3 1 0 -2/3 1 X5 12 0 2 5/3 0 1 -4/3 5 x1 12 1 0 1/3 0 0 1/3 128 0 6 3 0 0 -4 Chia hàng mới để có hệ số 1 tại vị trí xoay Biến đổi trên dòng để các hàng còn lại là 0 Tính lại các giá trị Delta và giá trị f(x0)
  63. BẢNG MỚI Đưa biến x2 vào thay biến x5 Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản 5 4 5 2 1 3 2 X4 28 0 4 7/3 1 0 -2/3 1 X5 12 0 2 5/3 0 1 -4/3 5 x1 12 1 0 1/3 0 0 1/3 128 0 6 3 0 0 -4 2 X4 4 0 0 -1 1 -2 2 4 X2 6 0 1 5/6 0 1/2 -2/3 5 x1 12 1 0 1/3 0 0 1/3 92 0 0 -2 0 -3 0 PATU: x0=(12,6,0,4,0,0) f min = 92
  64. PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý 1) Đối với bài toán có hàm f(x) max thì có thể chuyển về giải bài toán với hàm g(x) = −f(x) min (Chú ý là fmax = −gmin) hoặc cũng có thể giải trực tiếp với dấu hiệu tối ưu là k ≥ 0, dấu hiệu để điều chỉnh phương án là k 0 vào cơ sở cũng cải tiến được phương án.
  65. PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý 3) Trường hợp bài toán suy biến thì θ0 có thể bằng 0, khi θ0 = 0 vẫn thực hiện thuật toán một cách bình thường, nghĩa là vectơ ứng với θ0 vẫn bị loại khỏi cơ sở. Dấu hiệu xuất hiện phương án cực biên suy biến là θ0 đạt tại nhiều chỉ số, khi đó vectơ loại khỏi cơ sở được chọn trong số những vectơ ứng với θ0 theo quy tắc ngẫu nhiên.
  66. PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý Khi áp dụng thuật toán cần lưu ý hai trường hợp: 0 Phương án cực biên x có cơ sở J0 là cơ sở đơn vị, lúc đó ma trận hệ số phân tích của [ A | b] theo cơ sở đơn vị là chính nó nên ta có thể lập ngay được bảng đơn hình. Bài toán dạng chuẩn là bài toán cho ngay một phương án cực biên với cơ sở là đơn vị, nên từ bài toán ta có thể lập được bảng đơn hình ứng với phương án cực biên ấy. Nếu J0 không phải là cơ sở đơn vị thì để lập bảng đơn hình trước hết cần phải tìm ma trận hệ số phân tích theo J0. Để làm điều này ta viết ma trận mở rộng [A | b] sau đó thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận, biến đổi sao cho các vectơ cơ sở trở thành các vectơ đơn vị khác nhau. Khi đó ma trận mở rộng sẽ trở thành ma trận hệ số phân tích.
  67. VÍ DỤ 19 Cho bài toán: f x 2 x1 6 x 2 8 x 3 5 x 4 min x1 2 x 2 3 x 3 x 4 8 2x1 x 2 x 3 5 x 4 2 4x 7 x 8 x 2 x 20 1 2 3 4 xj 0 j 1,2,3,4 Chứng tỏ rằng vecto x0 = (8, 0, 0, 0) là phương án cực biên. Dùng vectơ trên giải bài toán theo phương pháp đơn hình
  68. VÍ DỤ 19 Dễ thấy rằng x0 thỏa mãn mọi ràng buộc của bài toán, các ràng buộc là độc lập tuyến tính, vậy x0 là phương án cực biên không suy biến. Trước hết phải đưa bài toán về dạng chính tắc. f x 2 x1 6 x 2 8 x 3 5 x 4 min x1 2 x 2 3 x 3 x 4 8 2x1 x 2 x 3 5 x 4 x 5 2 4x 7 x 8 x 2 x x 20 1 2 3 4 6 xj 0 j 1,2,3,4,5,6
  69. VÍ DỤ 19 Từ x0 suy ra phương án cực biên không suy biến của bài toán dạng chính tắc: x= (8, 0, 0, 0, 18, 12) với cơ sở là J0 = {A1, A5, A6} không phải là cơ sở đơn vị. Vì vậy để lập được bảng đơn hình ứng với phương án cực biên x ta phải tìm ma trận hệ số phân tích của ma trận điều kiện của bài toán dạng chính tắc qua cơ sở J0 . Chú ý rằng vế phải của ma trận hệ số phân tích phải trùng với các thành phần cơ sở của phương án cực biên.
  70. VÍ DỤ 19 Quá trình biến đổi trên ma trận như sau: 1 2 3 1 0 0 8 1 2 3 1 0 0 8 2 1 1 5 1 0 8 0 5 5 3 1 0 18 4 7 8 2 0 1 20 0 1 4 2 0 1 12 Dựa trên ma trận hệ số phân tích ta lập bảng đơn hình.
  71. f x 2 x1 6 x 2 8 x 3 5 x 4 min Hệ số Ẩn cơ PA X1 X2 X3 X4 X5 X6 bản -2 -6 8 -5 0 0 -2 X1 8 1 2 -3 1 0 0 0 X5 18 0 5 -5 -3 1 0 0 x6 12 0 1 -4 2 0 1 -16 0 2 -2 3 0 0 -2 X1 2 1 3/2 -1 0 0 -1/2 0 X5 36 0 13/2 -11 0 1 3/2 -5 x4 6 0 1/2 -2 1 0 1/2 -34 0 1/2 4 0 0 -3/2 Ta có 3 = 4 > 0, nhưng aj3 < 0 (j J), bài toán không có phương án tối ưu.
  72. VÍ DỤ 20. BÀI TOÁN ĐẶT ẨN PHỤ Giải bài toán sau bằng phương pháp đơn hình 1 f x 2 x 3 x x x min 1 2 32 4 Với hệ ràng buộc: 1 x x x x 18 1 2 32 4 x 4 x 8 x 8 2 3 4 2x 2 x 3 x 20 2 3 4 xj 0 j 1,2,3,4
  73. VÍ DỤ 20. BÀI TOÁN ĐẶT ẨN PHỤ Trước hết đưa bài toán về dạng chính tắc bằng cách cộng vào ràng buộc (2) và (3) hai biến phụ x5 và x6. Ta có: 1 f x 2 x 3 x x x min 1 2 32 4 Với hệ ràng buộc mới: 1 x x x x 18 1 2 32 4 x 4 x 8 x x 8 2 3 4 5 2x 2 x 3 x x 20 2 3 4 6 xj 0 j 1,2,3,4,5,6 Phương án tương ứng là tối ưu: x0 = (0, 0, 16, 4, 40, 0) Giá trị tối ưu của hàm mục tiêu là: f = –18.
  74. VÍ DỤ 21. BÀI TOÁN ĐẶT ẨN PHỤ Đây là bài toán dạng chuẩn tắc phương pháp đơn hình
  75. BÀI TOÁN ẨN GIẢ
  76. QUAN HỆ HAI BÀI TOÁN . Nếu bài toán M vô nghiệm thì bài toán ban đầu vô nghiệm. . Nếu bài toán M có nghiệm (x1,x2, ,xn,0, ,0) thì (x1,x2, ,xn) là nghiệm bài toán ban đầu . Nếu bài toán M có nghiệm (x1,x2, ,xn,xn+1, ,xn+m) và có ít nhất 1 trong các ẩn giả >0 thì bài toán ban đầu vô nghiệm . Thuận lợi: có thể xây dựng ngay phương án cơ bản ban đầu thông qua đặt các ẩn giả.
  77. VÍ DỤ 22.
  78. VÍ DỤ 22. Ta có bài toán. f x x1 2x2 x3 Mx6 Mx7 min Đây là bài toán dạng chuẩn tắc nên ta có thể áp dụng ngay phương pháp đơn hình để giải.