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 "

Chia sẻ: Chehuyen Huyen | Ngày: | Loại File: DOC | Số trang:17

Thêm vào BST

Báo xấu

778
lượt xem 205
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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 của không gian lời giải. -Áp dụng kết quả này điểm tìm giá trị của hàm mục tiêu bằng cách so sánh giá trị của các đỉnh của không gian lời giải. Bài giải : So sánh giá trị tại 3 đỉnh A,B,C: Đỉnh A (18;0)  fminA = 2 × 18 + 3 × 0 = 36 Đỉnh B (8,4;4,8)  fminB = 2 × 8,4 + 3 × 4,8 = 31,2 Đỉnh C (3;12)  fminC = 2 × 3 + 3 × 12 = 42  x1  8,4  fmin=fC=31,2    x 2  4,8 1.3.2.Gỉai bằng phương pháp đơn hình: Nếu ta giải bài toán này theo phương pháp đơn hình thì phải có tới 8 ẩn, thay vì vậy, ta sẽ biến đổi bài toán gốc về dạng bài toán đối ngẫu, sau đó giải bài toán đối ngẫu đó theo phương pháp đơn hình, như thế sẽ dễ dàng và nhanh hơn. Cách giải như sau: f(x) = 2x1 + 3x2 → min g(y) = 90y1 + 48y2 +1.5y3 → max
5 x1  10 x 2  90  5 y1  4 y 2  0.5 y3  2  4 x1  3 x 2  48    0.5 x  1,5  10 y1  3 y 2  0 y3  3  1 x1, x2  0 y1, y2  0 ( bài toán gốc ) ( bài toán đối ngẫu ) Lúc này, ta giải bài toán đối ngẫu bằng phương pháp đơn hình: g(y) =90y1 + 48y2 + 1.5y3 + 0y4 + 0y5 → max 5 y1  4 y 2  0.5 y 3  y 4  2   10 y1  3 y 2  y 5  3 y1, y2  0 Ta có bảng đơn hình: 90 48 2 0 0 Cơ Hệ số P.án y1 y2 Y3 y4 y5 sở
1 A4 0 2 5 4 1 0 2 A5 0 3 10 3 0 0 1 3 -90 -48 - 0 0 2 1 5 1 1 A4 0 0 1 - 2 2 2 2 3 3 1 A1 90 1 0 0 10 10 10 3 0 -21 - 0 9 2 1 1 2 1 A2 48 0 1 - 5 5 5 5 6 3 3 4 A1 90 1 0 - - 25 50 25 25 27 42 24 0 0 10 5 5 6 1  phương án tối ưu của bài toán đối ngẫu: y = ( , ,0) 25 5 6 1 156 và giá trị tối ưu: g(y) = 90 × + 4 × + 1,5 × 0 = 25 5 5 -1  phương án tối ưu của bài toán gốc: x = c.B 5 4 ^-1 1  3  4 x = ( 90, 48 ) ×   = ( 90, 48 ) ×  25 ×  10 10 3   5    3 4   25 35   42 24  = ( 90, 48 ) ×  10  1   =  5 , 5   25 5   42 24 156  giá trị tối ưu của bài toán gốc: f(x) = 2 × +3× = 5 5 5 Kết quả này phù hợp với kết quả của cách giải bài toán bằng phương pháp giải trên. 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)
Trong toán học, Bài toán vận tải (tiếng Anh: transportation problem) là một dạng của bài toán quy hoạch tuyến tính. Bài toán vận tải có thể biểu diễn như một đồ thị hai phía, có hướng. Nó có thể ứng dụng vào nhiều vấn đề khác nhau. Giải thuật đơn hình trên bài toán vận tải cũng đơn giản hơn. Biểu diễn đồ thị của bài toán vận tải 2.1.Phát biểu và lập mô hình bài toán: Có m kho hàng với lượng hàng dự trữ tương ứng là a1,a2,..,am và n nơi tiêu thụ với yêu cầu tương ứng là b1,b2,…,bn đơn vị hàng hóa.Đơn giá cước phí vận chuyển từ kho i đến nơi tiêu thụ j là cij (i=1…m, j=1…n) đơn vị tiền tệ.Hãy lập kế hoạch vận chuyển hàng sao cho: a)-Tổng chi phí vận chuyển nhỏ nhất. b)-Các kho phát hết hàng . c)-Các nơi tiêu thụ nhận đủ hàng Gọi xij (i=1…m, j=1…n) là lượng hàng vận chuyển từ kho i đến nơi tiêu thụ j. m n Tổng chi phí vận chuyển: f=  c ij xij i 1 j 1 n Lượng hàng phát từ kho i: x j 1 ij , i=1…m. m Lượng hàng nhận về nơi tiêu thụ j: x i 1 ij , j=1…n. Như vậy ,bài toán vận tải được phát biểu như sau:
m n Tìm các số xij (i=1…m, j=1…n) sao cho f=  c ij xij  min i 1 j 1  n   xij  a i , i  1...m   jn 1  Trong đó   xij  b j , j  1...n (1-1)  j 1  xij  0, i  1...m, j  1...n   Bài toán vận tải là bài toán Qui hoạch tuyến tính dạng chính tắc có m × n ẩn số, m + n phương trình ràng buộc trong đó mỗi ẩn số xuất hiện đúng hai lần với hệ số bằng 1.Sự khai triển chi tiết của hệ phương trình rang buộc trong (1- 2) cho rõ điều này. i = 1: x11+x12+…+x1n = a1 i = 2: x21+x22+…+x2n = a2 … … i = m: xm1+xm2+…+xmn = am (1- 2) j = 1: x11 + x21 +…+ xm1 = b1 j = 2: x12 + x22 +…+ xm2 = b2 … … … … j = n: x1n + x2n +…+ xmn= bn Gọi A là ma trận có(m+n dòng, m×n cột) các hệ số của các ẩn xij trong hệ phương trình ràng buộc ta có: Cột A11 A1n A21 A2n Am1 Am+n       1 1 ... 1 0 0 ... 0 ... 0 0 ... 0   dòng 1 0 0 ... 0 1 1 ... 1 ... 0 0 ... 0    ... ... ...    0 0 ... 0 0 0 ... 0 ... 1 1 ... 1   dòng m A=  (1- 1 0 ... 0 1 0 ... 0 ... 1 0 ... 0   dòng m 1   0 1 ... 0 0 1 ... 0 ... 0 1 ... 0  ... ... ...    0  0 ... 1 0 0 ... 1 ... 0 0 ... 1    dòng m  n 3)
Ngoài ra, đặt Aij là cột hệ số của ẩn xij (i=1…m,j=1…n) thì các thành phần của Aij hầu hết bằng 0, trừ hai số 1 ở dòng thứ I và dòng thứ m+j: Là các vecto trong không gian R m+n 0  dòng 1 ...   1   dòng i   ... 0  dòng m Aij =   (1- 4) 0  dòng m 1 ...   1   dòng m  j ...   0    dòng m  n Là các vecto trong không gian Rm+n Mỗi phương án của bài toán vận tải là một ma trận cấp m×n : X = x i j   2.1.3. Cân bằng cung cầu  Tổng số hàng dự trữ ở m điểm phát (cung) là , tổng số nhu cầu của n điểm thu (cầu)là . Nếu "cung" và "cầu" bằng nhau ta nói rằng cân bằng cung cầu.  Nếu cung nhiều hơn cầu thì một số hàng hóa sẽ được để lại ở các điểm phát. Ta biểu diễn việc này bằng cách bổ sung một điểm thu giả Bn + 1 với cước phí ci,n + 1 = 0 với mọi i=1,...,n.  Như vậy bài toán vận tải luôn được đưa về bài toán thỏa mãn điều kiện cân bằng cung cầu. Ví dụ: Có 3 điểm phát và 4 điểm thu, số hàng ở các điểm phát, nhu cầu ở các điểm thu, cước phí vận chuyển cho trong bảng sau:
Bảng dữ liệu và phương án X[i,j] của bài toán vận tải Bảng trên đây được gọi là bảng vận tải 2.2.Xét ví dụ cụ thể: m n Giải bài toán không cân bằng thu phát có  ai > i 1 b j 1 j thu 85 75 70 60 45 phát 80 8 2 5 4 12 110 7 5 6 8 10 90 4 11 10 9 6 120 6 3 12 7 5 2.3.Gỉai ví dụ trên.Trong khi giải ví dụ này hãy lập nhiều phương án ban đầu khác nhau Bài tâp: Cho bài toán vận tải không cân bằng thu phát.Đây là bài toán không cân bằng thu phát, nên khi giải bài toán này ta thêm vào môt trạm thu giả. Ta có bảng như sau; Bảng 1:
85 75 70 60 45 65 80 8 2 5 4 12 0 110 7 5 6 8 10 0 90 4 11 10 9 6 0 120 6 3 12 7 5 0 Ta xây dựng phương án ban đầu như sau; Bảng 2: 85 75 70 60 45 65 80 8 2 5 4 12 0 75 5 110 7 5 6 8 10 0 70 40 90 4 11 10 9 6 0 85 5 120 6 3 12 7 5 0 55 40 25 Bảng 3: 8 2 5 4 12 0 R1= 0 x x 7 5 6 8 10 0 R2=-3
x x 4 11 10 9 6 0 R3=-4 x x 6 3 12 7 5 0 R4=-3 x x x S1=0 S2=-2 S3=-3 S4=-4 S5=-2 S6=3 Bảng 4: 8 0 2 0 10 3 X (4)---- ------------ -------- -- (3)x 4 0 1 5 0 0 x x 0 3 0 -1 5 1 x x 3 6 0 0 0 -2 ------------ x x *(1)------ - ----- -------- (2)x Ta có: Vc ={75;55}
Vl = {5;0} Xi*j* = min{55;75 } =55 X’12=75-55= 20 X’14= 5+55= 60 X’42= 0+55=55 X’44= 55-55=0 Bảng 5: 85 75 70 60 45 65 80 8 2 5 4 12 0 20 60 110 7 5 6 8 10 0 70 40 90 4 11 10 9 6 0 85 5 120 6 3 12 7 5 0 55 40 25 Bảng 6: 8 2 5 4 12 0 R1=0 x x 7 5 6 8 10 0 R2=-1 x x 4 11 10 9 6 0 R3=-2 x x
6 3 12 7 5 0 R4=-1 x x x S1=-2 S2=-2 S3=-5 S4=-4 S5=-4 S6=1 Bảng7: 6 0 0 0 8 1 x x 4 2 0 3 5 0 x x 0 7 3 3 0 -1 x x (2)----- ------- (1)* - 3 0 2 2 0 0 x X(3)----- -------- -- (4)x Ta có: Vc = { 5;25 } Vl = {0;40 } Xi*j* = min{5;25}= 5 X’35= 5-5 =0 X’36= 0+5 =5 X’45= 40+5 = 45
X’46= 25-5 =20 Bảng 8: 85 75 70 60 45 65 80 8 2 5 4 12 0 20 60 110 7 5 6 8 10 0 70 40 90 4 11 10 9 6 0 85 5 120 6 3 12 7 5 0 55 45 20 Bảng 9: 8 2 5 4 12 0 R1=0 x x 7 5 6 8 10 0 R2=-1 x x 4 11 10 9 6 0 R3=-1 x x 6 3 12 7 5 0 R4=-1
x x x S1=-3 S2=-2 S3=-5 S4=-4 S5=-4 S6=1 Bảng 10: 5 0 0 0 8 1 x x 3 2 0 3 5 0 x x 0 8 4 4 1 0 x x 2 0 6 2 0 0 x x x Tất cả các cij ≥ 0 suy ra; phương án tối ưu của bài toán là; X= (0;20;0;60;0;0;0;0;70;0;0;40;85;0;0;0;0;5;0;55;0;0;45;20) Giá trị Z = 20.2 + 60. 4 + 70.6 + 40.0 + 85.4 + 5.0 +55.3 + 45.5 + 20.0 = 1430