Bài giảng Phương pháp tối ưu trong kinh tế: Chương 1 - Nguyễn Phương

Chia sẻ: _ _ | Ngày: | Loại File: PPT | Số trang:38

Thêm vào BST

Báo xấu

3
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Phương pháp tối ưu trong kinh tế - Chương 1: Bài toán quy hoạch tuyến tính" cung cấp cho người đọc các nội dung: Vấn đề thực tiễn dẫn đến bài toán quy hoạch tuyến tính (QHTT), thiết lập mô hình bài toán, các dạng của bài toán QHTT, phương pháp đồ thị, phương pháp đơn hình, phương pháp đơn hình mở rộng, sử dụng Excel giải bài toán QHTT. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phương pháp tối ưu trong kinh tế: Chương 1 - Nguyễn Phương

Chương 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYỄN PHƯƠNG Khoa Khoa Học Dữ Liệu trong Kinh Doanh Trường Đại Học Ngân Hàng TPHCM Blog: https://nguyenphuongblog@wordpress.com Email: nguyenphuong0122@gmail.com 1
NỘI DUNG 1. Vấn đề thực tiễn dẫn đến bài toán quy hoạch tuyến tính (QHTT) – Thiết lập mô hình bài toán 2. Các dạng của bài toán QHTT 3. Phương pháp đồ thị 4. Phương pháp đơn hình 5. Phương pháp đơn hình mở rộng 6. Sử dụng Excel giải bài toán QHTT 2
1.THIẾT LẬP MÔ HÌNH BÀI Ví dụ 1: (Bài toán lập kế hoạch sản xuất) TOÁN Một xí nghiệp có thể sản xuất ra một loại sản phẩm theo 3 phương pháp khác nhau, kí hiệu PP1, PP2, PP3. Các loại nguyên liệu để sản xuất, kí hiệu N1, N2, N3. Biết rằng số nguyên liệu để sản xuất hiện có, định mức tiêu hao các loại nguyên liệu và số lượng sản phẩm sản xuất ra trong một giờ theo các phương pháp cho ởĐịnh mức tiêu hao trong một Nguyên Số lượng bảng sau: Liệu hiện có giờ (đơn vị) PP1 PP2 PP3 N1 250 4 5 3 N2 350 2 4 1 Hãy lập mô hình bài toán tìm kế hoạch sản 6 N3 450 3 xuất sao cho xí 4 nghiệp sản xuất được nhiều sản10 Sản lượng (đơn vị/giờ) phẩm nhất. 12 9 3
Cách lập mô hình bài toán: Bước 1: Đặt ẩn và điều kiện cho ẩn (ràng buộc dấu). Căn cứ vào yêu cầu của bài toán, xác định số ẩn, đơn vị tính và điều kiện cho ẩn. Bước 2: Lập hàm mục tiêu f(x). Căn cứ vào các ẩn đã đặt, xác định hàm mục tiêu “yêu cầu tối ưu”. Bước 3: Lập các ràng buộc. Căn cứ vào các ẩn đã đặt, xác định các ràng buộc “yêu cầu kỹ thuật”. Bước 4: Viết mô hình bài toán. Sau khi phân tích, ta lập mô hình bài toán dưới dạng sau: -Hàm mục tiêu. -Các ràng buộc. -Các điều kiện. 4
Ví dụ 2: (Bài toán xác định khẩu phần thức ăn) Để sinh sống trong một ngày đêm, mỗi người cần ít nhất 70g Protit, 30g Lipit và 420g Gluxit. Hàm lượng các chất trên có trong 1g thức ăn A và B như sau: Thức ăn Chất dinh dưỡng A B Protit (g) 0,1 0,2 Lipit (g) 0,2 0,3 Gluxit (g) 0,6 0,4 Ngoài ra, biết giá của mỗi gam thức ăn A và B tương ứng là 40đ và 60đ. Hãy lập mô hình bài toán xác định khối lượng thức ăn cần mua trong ngày sao cho tổng chi phí để mua các loại thức ăn là thấp nhất. 5
Ví dụ 3: (Bài toán phân bổ vốn đầu tư) Một nhà đầu tư có 2 tỉ đồng, muốn đầu tư vào 4 lĩnh vực: chứng khoán, công trái, gởi tiết kiệm và bất động sản. Biết lãi suất hàng năm của các lĩnh vực đầu tư như sau: Lĩnh vực đầu tư Lãi suất hàng năm (%) Chứng khoán 20 Công trái 12 Gởi tiết kiệm 10 Bất động sản 15 Ngoài ra, để giảm thiểu mức rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 40% tổng vốn đầu tư, còn đầu tư vào công trái và gởi tiết kiệm phải ít nhất là 25% tổng vốn đầu tư và tiền gởi tiết kiệm phải ít nhất là 100 triệu đồng. Nếu người này muốn đầu tư toàn bộ số tiền trên thì nên đầu tư vào các lĩnh vực trên như thế nào để thu được lợi nhuận 6
Ví dụ 4: (Bài toán cắt nguyên vật liệu) Một xí nghiệp may mặc cần sản xuất ít nhất 2000 chiếc quần và ít nhất 1000 cái áo. Mỗi tấm vải có 6 cách cắt cho ở bảng sau: Cách Quần Áo cắt 1 90 35 2 80 55 3 70 70 4 60 90 5 120 0 6 0 100 Hãy tìm phương án cắt sao cho tổng số tấm vải sử dụng là ít nhất. 7
2.CÁC DẠNG CỦA BÀI TOÁN 2.1 Dạng tổng quát QHTT Tìmx = (x1,x 2 ,x n ) sao cho Hàm f (x) = c1x1 + c 2x 2 + L + c n x n max(min) (2.1) mục tiêu a11x1 + a12x 2 + L + a1n x n [ , , =] b1 a 21x1 + a 22x 2 + L + a 2n x n [ , , = ] b2 Ràng Hệ (2.2 buộc D ràng ) chính buộc am1x1 + a m 2x 2 + L + a mn x n [ , , = ] bm x i 0, , x i 1 k 0 (2.3) Ràng buộc dấu 8
 Một vectơ x = (x1, x2,..., xn) thỏa mãn điều kiện (2.2) và (2.3) được gọi là một phương án (P.A) của bài toán quy hoạch tuyến tính (QHTT).  Tập các P.A của bài toán được gọi là miền ràng buộc hay miền xác định. Ký hiệu là D.  Phương án làm hàm mục tiêu tối ưu được gọi là phương án tối ưu (P.A.T.Ư) hay nghiệm của bài toán, ký hiệu là x* .  Bài toán được gọi là giải được hay có lời giải hay có nghiệm nếu nó có ít nhất một P.A.T.Ư.  Bài toán không giải được hay vô nghiệm nếu D = hay nó có P.A nhưng không có PA.T.Ư. 9
2.2 Dạng chính tắc Bài toán QHTT dạng tổng quát được gọi là bài toán QHTT dạng chính tắc nếu thỏa các điều kiện sau: Các hệ số bên phải của các ràng buộc chính không âm. Ràng buộc chính gồm tất cả các phương trình. Các biến không âmx j 0, j = 1, 2,K ,n. Mô hình bài toán QHTT dạng chính tắc: f (x) = c1x1 + c 2x 2 + L + c n x n max(min) a11x1 + a12x 2 + L + a1n x n = b1 a 21x1 + a 22x 2 + L + a 2n x n = b2 D am1x1 + a m 2x 2 + L + a mn x n = bm xi 0 (i = 1 ) ,n 10
a11 a12 L a1n 1j a Ma a21 a22 L a2 n a2 j A= , Aj = , Cột hệ trận L L L L L số thứ hệ số am1 am 2 L amn amj j Ví dụ: f (x) = x1 − 2x 2 + x 3 min f (x) = x1 + 3x 2 + x 3 max x1 + x 2 + 2x 3 = 14 x1 + 3x 2 + 2x 3 = 14 x1 + 2x 2 + x 3 = 9 x1 + 2x 2 + 5x 3 = 9 xj 0, ( j = 1 3) , xj 0, ( j = 1 3) , 11
Biến đổi bài toán QHTT về dạng chính tắc:  Nếu ràng buộc thứ i có dạng aijxj ≤ bi thì thêm vào một ẩn phụ xn+1 0, sao cho aijxj + xn+1 = bi.  Nếu ràng buộc thứ i có dạng aijxj bi thì thêm vào một ẩn phụ xn+1 0, sao cho aijxj – xn+1 = bi.  Nếu ẩn xj ≤ 0 thì được thay bằng x/j = – xj 0.  Nếu ẩn xj không ràng buộc về dấu thì thay xj bằng hai ẩn phụ x/j và x//j sao cho xj = x/j – x//j, với x/j 0, x//j 12
Ví dụ: f ( x ) = x + 3 x − 2 x min 1 2 3 3 x1 + x2 − 2 x3 7 2 x1 − 4 x2 + x3 = 12 4 x1 + 3x2 − 8 x3 10 x1 0 x3 0 Ví dụ: f ( x ) = 3 x1 + 4 x2 + 4 x3 max 3 x1 + 4 x2 + x3 7 2 x1 − 4 x2 + x3 6 x1 + 2 x2 + x3 4 x2 0 x3 0 13
2.3 Dạng chuẩn Bài toán QHTT dạng chính tắc (n ẩn, m ràng buộc chính) được gọi là bài toán QHTT dạng chuẩn nếu thỏa hệ số các biến trong các ràng buộc chính lập nên ma trận đơn vị cấp m. a11 a12 L a1n 1 0 L 0 a21 a22 L a2 n 0 1 L 0 A= , Im = , L L L L L L L L am1 am 2 L amn 0 0 L 1 - Các ẩn có các cột hệ số tạo thành ma trận đơn vị được gọi là ẩn cơ bản (ACB). - Các ẩn còn lại gọi là ẩn không cơ bản, hay ẩn tự do. - Một phương án mà các ẩn không cơ bản bằng 0, được gọi là phương án cơ bản (PACB). - Một phương án cơ bản có ít nhất một ẩn cơ bản bằng 0 được gọi là phương án cơ bản suy biến. 14
Ví dụ: Cho bài toán QHTT: f ( x) = x2 − x5 min x1 + x2 −2 x5 = 1 3 x2 + x3 + x5 = 3 −2 x2 + x4 + x5 = 2 xj 0 j = 1,5 Ta có ma trận hệ số của hệ ràng buộc: 1 1 0 0 2 A 0 3 1 0 1 0 2 0 1 1 chứa I3 nên bài toán quy hoạch tuyến tính trên có dạng chuẩn. 15
3. PHƯƠNG PHÁP HÌNH HỌC Xét bài toán QHTT có 2 biến. ax+by=c tăng ax+byc O Giảm 16
ax+by= m (đường mức) tăng O a Giảm b N(a,b) 17
Các bước giải bt QHTT bằng PP đồ thị Bước 1: Xác định tập phương án và các phương án cơ bản. Biểu diễn các ràng buộc trên mặt phẳng tọa độ, từ đó xác định tập phương án D và tọa độ các đỉnh (phương án cơ bản). Bước 2: Biểu diễn đường mức của hàm mục tiêu. Từ điểm M0 bất kỳ thuộc tập phương án, vẽ vecto (a,b) và vẽ đường thẳng đường mức (d) là đường thẳng qua M0 vuông góc với vecto (a,b). Bước 3: Giải bài toán Cho đường mức (d) di chuyển theo hướng của vecto (a,b) nếu là bài toán max, hay di chuyển ngược hướng với vecto (a,b) nếu là bài toán min. 18
Ví dụ: Giải bài toán QHTT f ( x ) = x1 + 2 x2 max − x1 + 2 x2 6 x1 + x2 4 x1 0 x2 0 bằng phương pháp hình học. 19
x2 E O x1 Dịch chuyển đường mức theo chiều của vecto pháp tuyến (1,2), điểm cuối cùng đường mức còn cắt miền ràng buộc là EVậy PATU là x* = (2/3;10/3) và giá trị tối ưu của hàm mục (2/3;10/3) tiêu f(x* ) = 22/3 20