TIỂU LUẬN MÔN TOÁN CHUYÊN ĐỀ QUY HOẠCH TUYẾN TÍNH Xây dựng một khẩu phần ăn đảm bảo được yêu cầu về m loại chất dinh dưỡng,với giá rẻ nhất

Có n loại thực phẩm TP1,TP2,…,TPn.Gía tiền của một đơn vị khối lượng các loại thực phẩm này lần lượt là c1,c2,…,cn.Trong n loại thực phẩm này có chứa m chất dinh dưỡng DD1,DD2,…,DDn.Lượng chất dinh dưỡng loại i có trong một đơn vị khối lượng thực phẩm loại j là aij.Lượng chất dinh dưỡng loại i tối thiểu cần thiết cho một khẩu phần ăn là bi.
Nội dung trích xuất từ tài liệu:
TIỂU LUẬN MÔN TOÁN CHUYÊN ĐỀ QUY HOẠCH TUYẾN TÍNH " Xây dựng một khẩu phần ăn đảm bảo được yêu cầu về m loại chất dinh dưỡng,với giá rẻ nhất " TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HỒ CHÍ MINH KHOA CƠ BẢN   Bài tiểu luận Môn: QUI HOẠCH TUYẾN TÍNH Đề tài: ĐỀ SỐ 1 GVHD: ThS Nguyễn Đình Tùng Lớp học phần : 211301204 Nhóm : I Năm học :2008-2009 TP.Hồ Chí Minh, ngày 22 tháng 5 năm 2009 1.Bài toán khẩu phần ăn: ....................................................................................... 3 1.1.Phát biểu và lập mô hình bài toán: .................................................................. 3 1.2.Xét ví dụ cụ thể:................................................................................................ 4 1.3.Giải ví dụ trên bằng nhiều phương pháp khác nhau ...................................... 4 2.Bài toán vận tải không cân bằng thu phát(cung lớn hơn cầu) ........................... 8 2.1.Phát biểu và lập mô hình bài toán: .................................................................. 9 2.2.Xét ví dụ cụ thể:.............................................................................................. 12 TIỂU LUẬN MÔN TOÁN CHUYÊN ĐỀ QUY HOẠCH TUYẾN TÍNH Đề tài 1 1.Bài toán khẩu phần ăn: 1.1.Phát biểu và lập mô hình bài toán: 1.1.1.Phát biểu: Có n loại thực phẩm TP1,TP2,…,TPn.Gía tiền của một đơn vị khối lượng các loại thực phẩm này lần lượt là c1,c2,…,cn.Trong n loại thực phẩm này có chứa m chất dinh dưỡng DD1,DD2,…,DDn.Lượng chất dinh dưỡng loại i có trong một đơn vị khối lượng thực phẩm loại j là aij.Lượng chất dinh dưỡng loại i tối thiểu cần thiết cho một khẩu phần ăn là bi. Bài toán đặt ra là:Xây dựng một khẩu phần ăn đảm bảo được yêu cầu về m loại chất dinh dưỡng,với giá rẻ nhất. 1.1.2.Lập mô hình : Gọi xj là lượng thực phẩm loại j có trong khẩu phần.Khi đó: Gía tiền phải trả cho khẩu phần này là f = c1x1 + c2x2 +…+ cnxn. n Lượng chất dinh dưỡng loại I có trong khẩu phần này là: a j 1 ij x j. Từ đây ta có bài toán:Tìm giá trị nhỏ nhất của hàm f = c1x1 + c2x2 +…+ cnxn Với điều kiện: n a j 1 ij x j  b j , j  1, n x j  0, j  1, n Thông thường bài toán này còn thêm ràng buộc về khối lượng khẩu phần thức ăn không vượt quá một lượng nào đó,tức là: x1 + x2 +…+ xn ≤ M 1.2.Xét ví dụ cụ thể: Một nhà quản lý trại gà dự định mua 2 loại thức ăn để trộn ra khẩu phần tốt và giá rẻ. Mỗi đơn vị thức ăn loại 1 giá 2 đồng có chứa : 5g thành phần A. 4g thành phần B 0,5.thành phần C Mỗi đơn vị thức ăn loại 2 giá 3 đồng có chứa : 10g thành phần A 3g thành phần B Không có chứa thành phần C Trong một tháng một con gà cần tối thiểu 90g thành phần A,48g thành phần B và 1,5g thành phần C. Hãy tìm số lượng mỗi loại thức ăn cần mua để có thể đảm bảo đủ nhu cầu tối thiểu về dinh dưỡng cho một con gà với giá rẻ nhất. Lập mô hình bài toán: Gọi x1,x2 lần lượt là số lượng đơn vị thực phẩm loại 1 và loại 2 cần cho một con gà trong một tháng. Hàm mục tiêu của bài toán này là hàm cực tiểu giá mua Min f = 2x1 + 3x2 Thành phần A: 5x1 + 10x2 ≥ 90 Thành phần B: 4x1 + 3x2 ≥ 48 Thành phần C: 0,5x1 ≥1,5 x1 ,x2 ≥ 0 1.3.Giải ví dụ trên bằng nhiều phương pháp khác nhau 1.3.1.Giải bằng phương pháp đồ thị 1.3.1.1.Phương pháp dùng đường đẳng lợi (iso-profit line) hay đường đẳng phí (iso-cost line): Hàm mục tiêu Min f = 2x1 + 3x2 Ràng buộc 5x1 + 10x2 ≥ 90 (1) 4x1 + 3x2 ≥ 48 (2) 0,5x1 ≥ 1,5 (3) x1 ≥0 (4) x2 ≥0 (5) Trong mặt phẳng tọa độ Ox1x2,ta vẽ các đường thẳng: (D1): 5x1 + 10x2 = 90 (D2): 4x1 + 3x2 = 48 (D3): 0,5x1 = 1,5 (D4): x1 =0 (D5): x2 =0 Dùng đường thẳng đề xác định fmin.Đường thẳng chi phí càng gần gốc O,f càng nhỏ. Đường thẳng phí qua điểm B cho ta fmin.Tọa độ điểm B là nghiệm của hệ phương trình 5 x1  10 x 2  90  x1  8,4    4 x1  3 x 2  48  x2  4,8 f = fmin = 2 ×1 + 3 × 2 = 2 × 8,4 + 3,84 = 31,2  x1  8,4 Vậy lời giải tối ưu là :   x 2  4,8 1.3.1.2.Phương pháp dùng điểm đỉnh (Corner Point,Extreme Point): -Các điểm đỉnh là giao điểm của các ràng buộc nằm trong không gian lời giải gọi là các đỉnh của không gian lời giải. -Một kết quả quan trọng trong lý thuyết qui hoạch tuyến tính là: Nếu bài toán QHTT có lời giải tối ưu thì lời giải sẽ nằm trên các đỉnh ...