Bài toán về quy hoạch tuyến tính

11 QUY HOẠCH TUYẾN TÍNH Bài toán quy hoạch tuyến tính là bài toán tối ưu hoá hàm mục tiêu với các ràng buộc là những biểu thức tuyến tính theo các biến số và các tham số. 2 1-BÀI TOÁN VỀ LẬP KẾ HOẠCH SẢN XUẤT Một nhà máy sx giấy có hai loại nguyên liệu là gổ và acid với số lượng tương ứng là 5580 m3 và 450 tấn. Để sx ra ba loại giấy A, B, C thì cần tiêu hao nguyên liệu theo bảng định mức sau : 0.120.150.1Acid (tấn) 1.61.81.5Gỗ (m3) CBA Sản phẩmNguyên liệu Biết rằng lợi nhuận tương ứng cho từng loại giấy A, B, C là 4 ; 5 ; 4.3 triệu đồng. Hãy lập kế hoạch sx sau cho lợi nhuận đạt được tối đa. 23 MÔ HÌNH BÀI TOÁN
Gọi x1, x2, x3 là số giấy A, B, C cần sx. Ta có : xj ≥ 0.
Theo định mức thì lượng nguyên liêu tiêu hao là : 1.5 * x1 + 1.8 * x2 + 1.6 * x3 ≤ 5,580 (m3) 0.1 * x1 + 0.15 * x2 + 0.12 * x3 ≤ 450 (tấn)
Lợi nhuận thu được theo kế hoạch là : Z = 4 * x1 + 5 * x2 + 4.3 * x3 phải đạt cực đại. Ta được mô hình sau : Tìm x1, x2, x3 sao cho : Z = 4 * x1 + 5 * x2 + 4.3 * x3 ⇒Max Các ràng buộc : 1.5 * x1 + 1.8 * x2 + 1.6 * x3 ≤ 5,580 (m3) 0.1 * x1 + 0.15 * x2 + 0.12 * x3 ≤ 450 (tấn) xj ≥ 0. (j = 1, 2, 3) 4 MÔ HÌNH TỔNG QUÁT BÀI TOÁN CỰC ĐẠI
Giả sử có m loại nguyên liệu với lượng tồn trử thứ i (i=1,2,3,m) là bi .
Cần sản xuất n sản phẩm với lượng nguyên liệu thứ i dùng để sx sản phẩm thứ j (j = 1,2,3 n) là aij .
Lợi nhuận của một đơn vị sản phẩm loại j là cj .
Xác định xj sao cho lợi nhuận đạt cực đại. Ta có mô hình bài toán cực đại tổng quát sau : n1,2,3,...,j0xj m)1,2,3,...,(ibixj*aij xj)*cjMaximize(Z n 1j n 1j =∀≥ =≤ = ∑ ∑ = = 35 2-BÀI TOÁN VỀ KHẨU PHẦN : Để có thể tái tạo lại sức lao động, người ta cần ít nhất 70 g protit, 30 g lipit và 420 g gluxit. Hàm lượng các chất trên có trong 1 g thức ăn A và B như sau : 0.10.1Lipit (g) 0.60.7Gluxit (g) 0.20.1Protit (g) BA Thức ănChất dinh dưỡng Biết giá của mỗi g thức ăn A và B là 4 đ và 6 đ. Hãy xác định cách mua thức ăn tối ưu. 6 MÔ HÌNH BÀI TOÁN
Gọi x1, x2 là số thức ăn A, B cần mua. Ta có : xj ≥ 0. (j =1,2)
Hàm lượng các dưỡng chất tối thiểu theo yêu cầu là : Protit : 0.1 * x1 + 0.2 * x2 ≥ 70 (g) lipit : 0.1 * x1 + 0.1 * x2 ≥ 30 (g) Gluxit : 0.7 * x1 + 0.6 * x2 ≥ 420 (g)
Tổng chi phí cần phải mua là : Z = 4 * x1 + 6 * x2 phải đạt cực tiểu . Ta được mô hình sau : Tìm x1, x2 sao cho : Z = 4 * x1 + 6 * x2 ⇒ Min Các ràng buộc : 0.1 * x1 + 0.2 * x2 ≥ 70 (g) 0.1 * x1 + 0.1 * x2 ≥ 30 (g) 0.7 * x1 + 0.6 * x2 ≥ 420 (g) xj ≥ 0. (j = 1, 2) 47 MÔ HÌNH TỔNG QUÁT BÀI TOÁN CỰC TIỂU
Giả sử cơ thể cần bổ sung m loại dưỡng chất với nhu cầu tối thiểu là bi (i=1,2,3,m) .
Cần mua n loại thức ăn trong đó lượng dưỡng chất có trong một đơn vị thức ăn thứ j là aij (j = 1,2,3 n).
Chi phí của một đơn vị thức ăn loại j là cj.
Xác định xj sao cho tổng chi phí đạt cực tiểu. Ta có mô hình bài toán cực tiểu tổng quát sau : n1,2,3,...,j0xj m)1,2,3,...,(ibixj*aij xj)*cjMinimize(Z n 1j n 1j =∀≥ =≥ = ∑ ∑ = = 8 Bài tập 1 : Nhân dịp tết Trung Thu, xí nghiệp bánh kẹo Vinabico muốn sản xuất ba loại bánh đậu xanh, thập cẩm và bánh dẽo. Giả sử số đường và đậu trong kho của xí nghiệp hiện có là 500 kg và 300 kg (các nguyên liệu khác không hạn chế). Mức tiêu hao đường và đậu cũng như số tiền lãi khi bán một chiếc bánh cho từng loại được cho ở bảng sau : 70 40 1,8 40 0 1,7 60 80 2 1- Nguyên liệu sử dụng : - Đường (g) - Đậu (g) 2- Lợi nhuận đơn vị (1000 đ) : Bánh dẽoBánh thập cẩmBánh đậu xanhChỉ tiêu Yêu cầu : Xác lập mô hình toán nhằm hổ trợ việc xác định lợi nhuận tối đa. 59 Bài 2 : Một xí nghiệp dệt hiện có ba loại sợi : Cotton, Kate và Polyeste với khối lượng tương ứng là 3 ; 2,5 và 4,2 tấn. Các tư liệu sản xuất khác và lao động có số lượng lớn. Mức tiêu hao ba loại nguyên liệu trên để sản xuất 1m vải loại A, B và C cho ở bảng sau : Đơn vị tính : gam Biết lợi nhuận thu được khi bán 1m vải loại A, B, C lần lượt là 3.500, 4.800, 2.500 đồng. Hãy xây dựng mô hình tối đa hóa lợi nhuận cho xí nghiệp. 100100100Polyeste 100200100Kate 100200200Cotton CBA 10 Bài 3 : Một nông trường phải quyết định phương án phân bổ việc sử dụng 3000 ha đất để gieo trồng ba loại nông sản A, B và C với các thông số kỷ thuật như sau : Nông trường có thể chuẩn bị được số tiền làm vốn cho sản xuất là 1,2 tỷ và thuê lao động là 1,6 tỷ. Ngoài ra để đảm bảo nhu cầu hợp đồng về sản lượng thì phải gieo trồng ít nhất 600 ha nông sản A. Hãy xây dựng mô hình toán hổ trợ việc phân bổ sử dụng đất nhằm đạt mục tiêu tối đa hóa giá trị sản lượng sản phẩm. 2000 1500 2500 500 400 450 300 350 400 A B C Lao độngVốn Ước giá trị sản lượng thu được trên 1 ha (1000 đ) Chi phí sản xuất cho 1 ha (1000 đ) Loại nông sản 611 Bài 4 : Để nuôi một loại gia súc, trong một ngày và đêm cần có khối lượng tối thiểu các chất đạm, đường và khoáng tương ứng là 80g, 120g và 6g. Tỷ lệ % các chất trên có trong các loại thức ăn A, B, C như sau : Biết rằng giá 1kg thức ăn loại A, B, C tương ứng là 2.000 , 3.000 , 2.500 đồng. Hãy lập mô hình xác định phương án mua thức ăn tối ưu. Dưỡng chấtThức ăn 32025C 14020B 23010A KhoángĐườngĐạm 12 PHƯƠNG PHÁP TÌM NGHIỆM : PHƯƠNG PHÁP ĐỒ THỊ Xét mô hình : Max (Z = 5 * x1 + 3 * x2) 6 * x1 + 2 * x2 ≤ 36 5 * x1 + 5 * x2 ≤ 40 2 * x1 + 4 * x2 ≤ 28 x1, x2 ≥ 0 Trên hệ trục tọa độ (x1,x2), dựa vào các ràng buộc, vẽ các đường thẳng : 6 * x1 + 2 * x2 = 36 5 * x1 + 5 * x2 = 40 2 * x1 + 4 * x2 = 28 713 6.x1+2.x2 = 36 2.x1+4.x2 = 28 5.x1+5.x2 = 40 x1 14 6.x1+2.x2 = 36 2.x1+4.x2 = 28 5.x1+5.x2 = 40 x1 Tìm miền xác định của ràng buộc 1 : 6.x1 + 2.x2 ≤ 36 815 6.x1+2.x2 = 36 2.x1+4.x2 = 28 5.x1+5.x2 = 40 x1 Tìm miền xác định của ràng buộc 2 : 5.x1 + 5.x2 ≤ 40 16 6.x1+2.x2 = 36 2.x1+4.x2 = 28 5.x1+5.x2 = 40 x1 Tìm miền xác định của ràng buộc 1 và 2 : 917 6.x1+2.x2 = 36 2.x1+4.x2 = 28 5.x1+5.x2 = 40 x1 Tìm miền xác định của ràng buộc 3 : 2.x1 + 4.x2 ≤ 28 18 6.x1+2.x2 = 36 2.x1+4.x2 = 28 5.x1+5.x2 = 40 x1 Tìm miền xác định của ràng buộc 1, 2 và 3 : 10 19 x1 Vẽ đường thẳng thể hiện hàm mục tiêu Z = 5.x1 + 3.x2 và tịnh tiến đến các điểm cực : Z = 5.x1+3.x2 20 x1 Z = 5.x1+3.x2 Xác định nghiệm tối ưu của mô hình : 11 21 x1 Z = 5.x1+3.x2 Xác định nghiệm tối ưu của mô hình : x1=5 ; x2=3 22 2- Bài toán cực tiểu : Xét mô hình Min (Z = 2 * x1 + 4 * x2) 2 *x1 + x2 ≥ 14 x1 + x2 ≥ 12 x1 + 3 * x2 ≥ 18 x1 , x2 ≥ 0 Trên hệ trục tọa độ (x1,x2), dựa vào các ràng buộc, vẽ các đường thẳng : 2 * x1 + x2 = 14 x1 + x2 = 12 x1 + 3 * x2 = 18 12 23 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 24 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Tìm miền xác định của ràng buộc 1 : 2.x1 + x2 ≥ 14 13 25 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Tìm miền xác định của ràng buộc 2 : x1 + x2 ≥ 12 26 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Tìm miền xác định của ràng buộc 1 và 2 : 14 27 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Tìm miền xác định của ràng buộc 3 : x1 + 3.x2 ≥ 18 28 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Tìm miền xác định của ràng buộc 1, 2 và 3 : 15 29 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Vẽ đường thẳng thể hiện hàm mục tiêu : Z = 2.x1 + 4.x2 và tịnh tiến đến các điểm cực : Z = 2.x1+ 4.x2 30 x1+3.x2 = 18 2.x1+ x2 = 14 x1+ x2 =12 Z = 2.x1+ 4.x2 Xác định nghiệm tối ưu của mô hình : x1 = 9 ; x2 = 3 16 31 PHƯƠNG PHÁP TÌM NGHIỆM : THUẬT TOÁN ĐƠN HÌNH 1-Bài toán cực đại : Xét mô hình : Max (Z = 5 * x1 + 3 * x2) 6 * x1 + 2 * x2 ≤ 36 5 * x1 + 5 * x2 ≤ 40 2 * x1 + 4 * x2 ≤ 28 x1, x2 ≥ 0 Để thuận lợi cho việc tìm nghiệm, ta thêm các biến bù si để các bất phương trình thành các phương trình : 6 * x1 + 2 * x2 + s1 = 36 5 * x1 + 5 * x2 + s2 = 40 2 * x1 + 4 * x2 + s3 = 28 Trong đó : (si có hệ số cj = 0). Lập bảng đơn hình : 32 Trong bảng ta có :
Các ẩn tương ứng với vector cột đơn vị là các ẩn cơ bản (s1, s2, s3). Các ẩn còn lại là ẩn không cơ bản (x1, x2).
Một nghiệm khả dĩ của bài toán là nghiệm thoả mản các ràng buộc mà ở đó các ẩn không cơ bản bằng không. Với bảng đơn hình đầu tiên, ta xác định được lời giải cơ bản (phương án ban đầu) như sau : x1 = x2 = 0 ; s1 = 36 s2 = 40 s3 = 28 và giá trị hàm mục tiêu bằng không. 5 3 0 0 0Cj – Zj 0 0 0 0 0 0Zj = ∑Cb.aij 36 40 28 6 2 1 0 0 5 5 0 1 0 2 4 0 0 1 0 0 0 s1 s2 s3 x1 x2 s1 s2 s3 Hằng số bi5 3 0 0 0Hệ số (Cb)Ẩn CB 17 33 TÌM PHƯƠNG ÁN TỐI ƯU 1-Kiểm tra tính tối ưu : Xét hàng giá trị tham khảo Cj-Zj
Nếu các giá trị của hàng tham khảo đều ≤ 0 ⇒ Phương án hiện tại tối ưu.
Nếu tồn tại một giá trị tham khảo > 0 ⇒ Phương án hiện tại chưa tối ưu. 2-Tìm phương án thay thế :
Để đạt đến giá trị tối ưu của hàm mục tiêu, cần xem xét một phương án khác bằng cách đưa một biến mới vào trong phương án ban đầu và đồng thời loại bỏ một trong những biến trong lời giải củ.
Một phương pháp thay thế biến là dựa vào phần tử xoay. Cách xác định phần tử xoay như sau : o Dựa vào cột có giá trị tham khảo (Cj - Zj) lớn nhất (Cột xoay). o Dựa vào hàng có tỷ (bi / aij ) bé nhất (Hàng xoay). 34 5 3 0 0 0Cj – Zj 0 0 0 0 0 0Zj = ∑Cb.aij 36 40 28 6 2 1 0 0 5 5 0 1 0 2 4 0 0 1 0 0 0 s1 s2 s3 x1 x2 s1 s2 s3 Hằng số bi5 3 0 0 0Hệ số (Cb)Ẩn CB
Với cách xác định trên, a11 chính là phần tử xoay, s1 là biến đưa ra và x1 là biến đưa vào thay thế cho s1.
Chia hàng xoay cho giá trị xoay. Biến đổi các số hạng của trục xoay thành 0 bằng phương pháp khử : 18 35 0 4/3 - 5/6 0 0Cj – Zj 30 5 5/3 5/6 0 0Zj = ∑Cb.aij 6 10 16 1 1/3 1/6 0 0 0 10/3 - 5/6 1 0 0 10/3 -1/3 0 1 5 0 0 x1 s2 s3 x1 x2 s1 s2 s3 Hằng số bi5 3 0 0 0Hệ số (Cb)Ẩn CB
Với bảng biến đổi trên, ta xác định được một phương án mới tốt hơn (giá trị hàm mục tiêu bằng 30) tương ứng các nghiệm x2 = s1 = 0, x1 =6 s2 = 10 s3 = 16 .
Hàng tham khảo (Cj – Zj) vẫn còn chứa giá trị tham khảo dương. Do đó phương án vừa tìm được chưa tối ưu. Ta tiếp tục xác định phần tử xoay để thay thế biến.
Dựa vào cách xác định phần tử xoay ở trên, ta tìm được giá trị a22 là phần tử xoay. Vậy biến loại khỏi phương án là s2 và thay thế bằng biến x2.
Chia hàng xoay cho giá trị xoay. Biến đổi các số hạng của trục xoay thành 0 bằng phương pháp khử ta được bảng : 36 0 0 - 1/2 - 2/5 0Cj – Zj 34 5 3 1/2 2/5 0Zj = ∑Cb.aij 5 3 6 1 0 1/4 -1/10 0 0 1 -1/4 3/10 0 0 0 1/2 -1 1 5 3 0 x1 x2 s3 x1 x2 s1 s2 s3 Hằng số bi5 3 0 0 0Hệ số (Cb)Ẩn CB
Ta nhận thấy các giá trị ở hàng tham khảo đều nhỏ hơn hay bằng không. Do đó, đây là phương án tối ưu.
Giá trị hàm mục tiêu tối ưu bằng 34 đơn vị, và hệ nghiệm của bài toán là : x1 = 5 và x2 = 3. 19 37 Bài 5 : Giải các bài toán sau theo phương pháp đơn hình : 1- Max (Z = 6.x1 + 5.x2 + 20.x3) 2.x1 + 2.x2 + 7.x3 ≤ 13 2.x1 + x2 + 6.x3 ≤ 9 x1,x2,x3 ≥ 0 (ĐS : x*(0,3,1) ; Z = 35) 2- Max (Z = x1 + 2.x2 + x3 + x4) 2.x1 + x2 + x3 + x4 ≤ 11 2.x2 + x3 + x4 ≤ 11 3.x1 + x2 + x3 ≤ 8 x1,x2,x3,x4 ≥ 0 (ĐS : X*(1,6 ; 3,2 ; 0 ; 4,6) ; Z = 12,6) 38 2- Bài toán cực tiểu : Xét mô hình Min (Z = 2 * x1 + 4 * x2) 2 *x1 + x2 ≥ 14 x1 + x2 ≥ 12 x1 + 3 * x2 ≥ 18 x1 , x2 ≥ 0 Để lập bảng đơn hình, ta thêm các biến bù si và các biến nhân tạo Ai để các bất phương trình thành các phương trình . 2 * x1 + x2 - s1 + A1 = 14 x1 + x2 - s2 + A2 = 12 x1 + 3 * x2 - s3 + A3 = 18 Trong đó : si có Cj = 0 và Ai có Cj = M (M : là số đủ lớn để loại bỏ Ai ra khỏi hệ). Sau đó lập bảng đơn hình : 20 39 4M-2 5M-4 - M - M - M 0 0 0Zj - Cj 44M4M 5M -M -M -M M M MZj =∑Cb.aij 14 12 18 2 1 -1 0 0 1 0 0 1 1 0 -1 0 0 1 0 1 3 0 0 -1 0 0 1 M M M A1 A2 A3 x1 x2 s1 s2 s3 A1 A2 A3 Hằng số bi 2 4 0 0 0 M M MHệ sốẨn CB
Với bảng đơn hình đầu tiên, ta xác định được lời giải cơ bản : x1 = x2 = s1 = s2 = s3 = 0 ; A1 = 14 A2 = 12 A3 =18 và giá trị hàm mục tiêu bằng 44M.
Hàng tham khảo còn chứa một số giá trị tham khảo dương nên phương án này chưa tối ưu. Để tìm phương án tối ưu, ta sử dụng các bước giống như ở bài toán cực đại.
Xác định phần tử xoay : * Dựa vào cột có giá trị tham khảo (Zj-Cj) lớn nhất. * Dựa vào hàng có tỷ (bi / aij ) bé nhất. 40 4M-2 5M-4 - M - M - M 0 0 0Zj - Cj 44M4M 5M -M -M -M M M MZj =∑Cb.aij 14 12 18 2 1 -1 0 0 1 0 0 1 1 0 -1 0 0 1 0 1 3 0 0 -1 0 0 1 M M M A1 A2 A3 x1 x2 s1 s2 s3 A1 A2 A3 Hằng số bi 2 4 0 0 0 M M MHệ sốẨn CB
Ta thấy a32 là phần tử xoay. x2 là biến đưa vào và A3 là biến đưa ra.
Chia hàng xoay cho giá trị xoay. Biến đổi các số hạng của trục xoay thành 0 bằng phương pháp khử 21 41 (7M-2)/3 0 - M - M (2M-4)/3 0 0 (-5M+4)/3Zj - Cj 14M+24(7M+4)/3 4 - M - M ( 2M-4)/3 M M (-2M+4)/3Zj =∑Cb.aij 8 6 6 5/3 0 -1 0 1/3 1 0 - 1/3 2/3 0 0 -1 1/3 0 1 - 1/3 1/3 1 0 0 -1/3 0 0 1/3 M M 4 A1 A2 x2 x1 x2 s1 s2 s3 A1 A2 A3 Hằng số bi 2 4 0 0 0 M M MHệ sốẨn CB
Với bảng biến đổi trên, ta xác định được một phương án mới tốt hơn (giá trị hàm mục tiêu bằng 14M +24 < 44M) tương ứng các nghiệm x1 = s1 = s2 = s3 = 0 , x2 = 6 A1 = 8 A2 = 6 .
Hàng tham khảo (Zj – Cj) vẫn còn chứa giá trị tham khảo dương. Do đó phương án vừa tìm được chưa tối ưu. Xác định phần tử xoay để thay thế biến.
Giá trị a11 là phần tử xoay. Vậy biến loại khỏi phương án là A1 và thay thế bằng biến x1.
Chia hàng xoay cho giá trị xoay. Biến đổi các số hạng của trục xoay thành 0 bằng phương pháp khử ta được bảng : 42 0 0 (2M-2)/5 - M (M- 6)/5 (2-7M)/5 0 (6-6M)/5Zj - Cj 2 4 (2M-2)/5 - M (M- 6)/5 (2-2M)/5 M (6-M)/5Zj =∑Cb.aij 24/5 14/5 22/5 1 0 -3/5 0 1/5 3/5 0 - 1/5 0 0 2/5 -1 1/5 -2/5 1 - 1/5 0 1 1/5 0 -6/15 -1/5 0 6/15 2 M 4 x1 A2 x2 x1 x2 s1 s2 s3 A1 A2 A3 Hằng số bi 2 4 0 0 0 M M MHệ sốẨn CB
Với bảng biến đổi trên, ta xác định được một phương án mới tốt hơn (14M +136)/5 < 14M +24) tương ứng các nghiệm s1 = s2 = s3 = A1 = A3 = 0 , x1 = 24/5 x2 = 22/5 A2 = 14/5 .
Hàng tham khảo (Zj – Cj) vẫn còn chứa giá trị tham khảo dương. Do đó phương án vừa tìm được chưa tối ưu. Xác định phần tử xoay để thay thế biến.
Giá trị a23 là phần tử xoay. Vậy biến loại khỏi phương án là A2 và thay thế bằng biến s1.
Chia hàng xoay cho giá trị xoay. Biến đổi các số hạng của trục xoay thành 0 bằng phương pháp khử ta được bảng : 5 13614M + 22 43 0 0 0 - 1 -1 - M - M+1 - M+1Zj - Cj 302 4 0 -1 -1 0 1 1 Zj =∑Cb.aij 9 7 3 1 0 0 - 3/2 1/2 0 3/2 - 1/2 0 0 1 - 5/2 1/2 -1 5/2 - 1/2 0 1 0 1/2 -1/2 0 -1/2 1/2 2 0 4 x1 s1 x2 x1 x2 s1 s2 s3 A1 A2 A3 Hằng số bi2 4 0 0 0 M M MHệ sốẨn CB
Ta nhận thấy các giá trị ở hàng tham khảo đều nhỏ hơn hay bằng không. Do đó, đây là phương án tối ưu.
Giá trị hàm mục tiêu tối ưu bằng 30 đơn vị, và hệ nghiệm của bài toán là : x1 = 9 và x2 = 3. 44 Bài 6 : Giải bài toán sau theo phương pháp đơn hình : Min (Z = 4.x1 + 3.x2 + 4.x3) 2.x1 + 3.x2 + 4.x3 ≥ 81 x1 + 2.x2 + 2.x3 ≥ 79 3.x1 + 2.x2 + x3 ≥ 89 x1,x2,x3 ≥ 0 ĐS : x*(5 ; 37 ; 0) ; Z = 131 23 45
Để thuận tiện cho việc tính toán, ta có thể sử dụng phần mềm QM để giải.
Giao diện của phần mềm QM : 46 Di chuyển con trỏ đến option cần chọn : Linear Programming. (Có thể chọn ký tự A), ta được giao diện sau : 24 47 Chọn New (N) và khai báo các thông số cần thiết của mô hình c ần giải (Sử dụng số lie äu của ví dụ 1 ở slide 12) : 48
Chọn Run (R ) để nhận kết quả
Dùng phím mủi tên lên và xuống để xe m các kết quả hiển thị : 25 49 DIỄN GIẢI CÁC KẾT XUẤT TỐI ƯU TRONG BẢNG ĐƠN HÌNH 1- Gía trị hàm mục tiêu (Z) Giá trị của hàm mục tiêu trong bảng kết xuất cho biết giá trị tối ưu (lớn nhất hay nhỏ nhất) của hàm mục tiêu và đáp ứng tất cả các yêu cầu của các ràng buộc được mô tả của bài toán. 2- Biến quyết định (Variables) Mức độ của các biến quyết định là số đơn vị của các biến được chọn trong giải pháp tối ưu. 50
Chi phí rút giảm (Còn gọi là chi phí mờ) của một biến quyết định nào đó cho biết giá trị đánh đổi của hàm mục tiêu khi biến quyết định này được lựa chọn đưa vào thay thế cho một biến quyết định khác trong giải pháp tối ưu.
Chi phí rút giảm của một hoạt động nào đó có thể xem như là một chi phí cơ hội khi đưa hoạt động này vào giải pháp tối ưu.
Trong giải pháp tối ưu, thông thường một trong hai giá trị : mức độ của hoạt động hoặc chi phí mờ của hoạt động này phải bằng 0 – có nghĩa là nếu mức độ của hoạt động là khác 0 thì chi phí mờ của hoạt động này phải bằng 0 và ngược lại. Tuy nhiên trong một số trường hợp đặc biệt, cả hai giá trị này có thể đồng thời bằng 0. 3- Chi phí rút giảm (Reduced Cost) 26 51 Xét ví dụ s au : DN có 3 loại nguyên liệu C1, C2, C3 với số lượng trong kho lần lượt là : 36, 28, 8 đơn vị dùng để sản xuất 2 loại sản phẩm A và B với mức tiêu hao nguyên liệu đơn vị và lợi nhuận đơn vị cho ở bảng sau : 35Lợi nhuận đơn vị 2 2 1 4 2 1 Mức tiêu hao nguyên liệu : -C1 -C2 -C3 BAChỉ tiêu Xác định số sản phẩm A và B cần sản xu ất để tối đa ho ùa lợi nhuận trong điều kiện hạn chế về nguy ên vật liệu. 52 Biến x2 có Reduced Cost bằng 2 ⇒ Trong giải pháp tối ưu, nếu thay x1 bằng x2 thì cứ một đơn vị thay đổi sẽ chịu một chi phí mờ bằng 2 đơn vị (tức làm giảm lợi nhuận của hàm mục tiêu 2 đơn vị) (Why?) Sử dụng phần mềm QM, ta có kết xuất sau : 27 53
Một biến quyết định có giá trị tối ưu khi chi phí rút giảm bằng không.
Chi phí rút giảm đo lường độ bền vững của giải pháp : Chi phí này có giá trị càng lớn thì độ bền vững của giải pháp càng cao và ngược lại .
Giá trị chi phí rút giảm sẽ thay đổi khi có sự thay đổi lớn trong giải pháp tối ưu. Một số chú ý khi sử dụng chi phí rút giảm 54
Mức nới lỏng của bài toán Max cho biết phần tài nguyên thừa không sử dụng hết.
Mức nới lỏng của bài toán Min cho biết mức độ sử dụng thực tế vượt quá yêu cầu.
Với bài toán Max trong ví dụ trên, ta có : 4- Mức nới lỏng của các ràng buộc (Slack / Surplus)
Nguyên liệu 1 thừa 4 đơn vị
Nguyên liệu 2 thừa 12 đơn vị
Nguyên liệu 3 đã sử dụng hết. 28 55
Ý nghĩa chung : chỉ tiê u này cho biết mức độ thay đổi trong giá trị của hàm mục tiê u ứng với thay đổi một đơn vị trong giới hạn của một ràng buộc . • Đối với bài toán cực đại hóa : giá mờ dương thể hiện cho mức độ tăng lên của giá trị hàm mục tiêu ứng với sự gia tăng một đơn vị trong giới hạn của các ràng buộc này; hoặc là mức độ giảm đi của giá trị hàm mục tiê u ứng với sự giảm một đơn vị trong giới hạn của các ràng buộc này. • Đối với bài toán cực tiểu hóa : Giá mờ âm thể hiện cho mức độ giảm của giá trị hàm mục tiê u ứng với sự giảm một đơn vị trong giới hạn của các ràng buộc này; hoặc là mức độ tăng lên của giá trị hàm mục tiêu ứng với sự tăng lên một đơn vị trong giới hạn của các ràng buộc này. 5- Giá mờ (Shadow Price) 56 Ví dụ : Xét bài toán Max trên ta có kết quả sau :
Ràn buộc 3 có giá mờ bằng 5 tức là nếu tăng nguyên liệu 3 thêm một đơn vị sẽ làm tăng gía trị hàm mục tiêu thêm 5 đơn vị hoặc ngược lại.
Ràn buộc 1 và 2 có giá mờ bằng 0 tức là nếu tăng thêm hoặc giảm đi nguyên liệu 1 và 2 một đơn vị thì giá trị hàm mục tiêu cũng không đổi. (Why?) 29 57
Chỉ số này giúp DN quyết định mua thêm hoặc bán bớt lượng nguyên liệu hiện có.
Với ví dụ trên, DN có thể bán nguyên liệu 3 với giá thị trường cộng thêm 5 đơn vị. Nguyên liệu 1 và 2 có thể bán theo giá thị trường. Chú ý : Việc đưa ra quyết định dựa vào giá trị Shadow Price trong bảng tối ưu chỉ đúng trong phạm vi lân cận của giá trị bi hiện tại. (Xem phần phân tích khoản của tham số bi) 58 6- Khoảng biến thiên các hệ số (Cj) của các hoạt động : Nếu các hệ số Cj của các hoạt động biến thiên trong khoảng (lower limit-upper limit) thì :
Không làm thay đổi : Thành phần và giá trị của các hoạt động (xj) trong giải pháp tối ưu, mức lơi lỏng (Slack/Surplus) và khoảng biến thiên của các ràng buộc bi (RHS ranges).
Có thể làm thay đổi : Chi phí mờ (Reduced Cost), giá mờ (Shadow Price), và khoảng biến thiên hệ số Cj của các hoạt động (Objective Cofficient Ranges). 30 59 Nếu giá trị các ràng buộc (bi) biến thiên trong khoảng Lower Limit-Upper Limit thì :
Không làm thay đổi : Thành phần các hoạt động (xj), các giá mờ (Shadow Price), chi phí mờ (Reduced Cost) và khoảng biến thiên của các hệ số Cj (Objective Coefficient Ranges).
Có thể làm thay đổi : Mức độ của các hoạt động trong giải pháp tối ưu (xj), mức lơi lỏng (Slack/Surplus) và khoảng biến thiên của các ràng buộc bi (RHS Range). 7- Khoảng biến thiên các ràng buộc (bi) : 60 BÀI TOÁN ĐỐI NGẪU : Xét bài toán lập kế hoạch sản xuất n1,2,3,...,j0xj m)1,2,3,...,(ibiaij.xj cj.xj)Max(Z n 1j n 1j =∀≥ =≤ = ∑ ∑ = = Trong đó : - aij : Mức tiêu hao yếu tố sản xuất thứ i để sản xuất một đơn vị sản phẩm loại j. - bi : Lượng yếu tố sản xuất loại i hiện có. - cj : Giá bán đơn vị sản phẩm loại j. - xj : Số sản phẩm loại j cần sản xuất. 31 61 Giả sử DN muốn bán số yếu tố sản xuất hiện có. Khi đó, DN nên bán với giá là bao nhiêu ?
Gọi yi là giá bán một đơn vị yếu tố sản xuất loại i (i=1,2,,m). Giá bán không thể âm nên : yi ≥ 0.
Số tiền thu được khi bán các yếu tố sản xuất để sản xuất ra một đơn vị sản phẩm loại j là : m)1,2,3,...,(iaij.yi m 1i =∑ =
DN chỉ bán các yếu tố sản xuất khi số tiền thu được không được ít hơn số tiền bán một đơn vị sản phẩm loại j : min⇒∑ = m 1i bi.yi cj≥∑ = m 1i aij.yi
Người mua các yếu tố sản xuất của DN mong muốn mua với chi phí thấp nhất : 62 Ta được mô hình : Xác định yi (i=1,2,,m) sao cho : ),...,2,1(0 miyi =≥ min⇒∑ = m 1i bi.yi ),...,2,1( njcj =≥∑ = m 1i aij.yi 32 63 Ta có được một cặp bài toán như sau : n)1,2,3,...,j0xj m)1,2,3,...,(ibiaij.xj cj.xj)Max(Z n 1j n 1j =≥ =≤ = ∑ ∑ = = ( Bài toán gốc (Premal) : m)1,2,3,...,(i0yi =≥ )bi.yiMin(Z m 1i ∑ = = n)1,2,3,...,(jcjaij.yi m 1i =≥∑ = Bài toán đối ngẫu (Dual) : 64 Ví dụ : Ta có bài to án gốc như sau : Max (Z = 50.x1 + 80.x2) 2.x1 + 3.x2 ≤ 100 x1 + 4.x2 ≤ 60 x1,x2 ≥ 0 Ta được bài toán đối ngẫu như sau : Min (Z = 100.y1 + 60.y2) 2.y1 + y2 ≥ 50 3.y1 + 4.y2 ≥ 80 y1,y2 ≥ 0 33 65 Bài 7 : Tìm mô hình đối ngẫu của các bài toán sau : 1- Max (Z = 6.x1 + 5.x2 + 20.x3) 2.x1 + 2.x2 + 7.x3 ≤ 13 2.x1 + x2 + 6.x3 ≤ 9 x1,x2,x3 ≥ 0 2- Max (Z = x1 + 2.x2 + x3 + x4) 2.x1 + x2 + x3 + x4 ≤ 11 2.x2 + x3 + x4 ≤ 11 3.x1 + x2 + x3 ≤ 8 x1,x2,x3,x4 ≥ 0 66 BÀI TOÁN ĐỐI NGẪU : Xét bài toán xây dựng khẩu phần thức ăn n)1,2,3,...,j0xj m)1,2,3,...,(ibiaij.xj cj.xj)Min(Z n 1j n 1j =≥ =≥ = ∑ ∑ = = ( Trong đó : - aij : Lượng dưỡng chất i trong một đơn vị thức ăn j. - bi : Nhu cầu lượng dưỡng chất i. - cj : Giá mua đơn vị thức ăn loại j. - xj : Số thức ăn loại j cần mua. 34 67 Ở góc độ nhà sản xuất thức ăn : Cần định giá bán các nguyên liệu dùng để sản xuất thức ăn với giá bao nhiêu để tối đa hóa lợi nhuận ?
Gọi yi là giá bán một đơn vị dưỡng chất loại i (i=1,2,,m). Giá bán không thể âm nên : yi ≥ 0.
Số tiền thu được khi bán các dưỡng chất hiện có với mong muốn là : n)1,2,3,...,(jcjaij.yi m 1i =≤∑ = ∑ = = m 1i bi.yi)ZMax(
Người mua các thức ăn của nhà sản xuất với mong muốn chi phí bỏ ra càng thấp càng tốt : 68 Ta có mô hình : Xác định yi (i = 1,2,,m) sao cho : m)1,2,3,...,(i0yi =≥ )( ∑ = = m 1i bi.yiZMax n)1,2,...,(jcjaij.yi m 1i =≤∑ = 35 69 Ta có được một cặp bài toán như sau : n)1,2,3,...,(j0xj m)1,2,3,...,(ibiaij.xj cj.xj)Min(Z n 1j n 1j =≥ =≥ = ∑ ∑ = = Bài toán gốc : m)1,2,3,...,(i0yi =≥ )bi.yiMax(Z m 1i ∑ = = n)1,2,3,...,(jcjaij.yi m 1i =≤∑ = Bài toán đối ngẫu : 70 Ví dụ : Ta có bài to án gốc như sau : Min (Z = 100.x1 + 60.x2) 2.x1 + x2 ≥ 50 3.x1 + 4.x2 ≥ 80 x1,x2 ≥ 0 Ta được bài toán đối ngẫu như sau : Max (Z = 50.y1 + 80.y2) 2.y1 + 3.y2 ≤ 100 y1 + 4.y2 ≤ 60 y1,y2 ≥ 0 36 71 Bài 8 : Tìm mô hình đối ngẫu của các bài toán sau : Min (Z = 4.x1 + 3.x2 + 4.x3) 2.x1 + 3.x2 + 4.x3 ≥ 81 x1 + 2.x2 + 2.x3 ≥ 79 3.x1 + 2.x2 + x3 ≥ 89 x1,x2,x3 ≥ 0 72 CÁC ĐỊNH LÝ ĐỐI NGẪU
Định lý đối ngẫu 1 : Bài toán đối ngẫu có phương án tối ưu khi bài toán gốc có phương án tối ưu và các giá trị tối ưu của hai phương án là bằng nhau.
Định lý đối ngẫu 2 : Gọi x* và y* là phương án tối ưu của bài toán gốc và bài toán đối ngẫu thì : m)1,2,3,...,(i0bi)-*.xa.(* y n 1j jiji ==∑ = n)1,2,3,...,(j0)c.ya.(*x j m 1i iijj ==−∑ = * 37 73 Ví dụ : Xét bài toán gốc sau : Min (Z = x1 + 3.x2 + 3.x3) x1 + 2.x2 ≥ 2 3.x1 + x2 + x3 ≥ 4 4.x3 ≥ 1 x1 + x3 ≥ 2 xj ≥ 0 (j = 1,2,3) Ta được bài toán đối ngẫu sau : Max (Z = 2.y1 + 4.y2 + y3 + 2.y4) y1 + 3.y2 + y4 ≤ 1 2.y1 + y2 ≤ 3 y2 + 4.y3 + y4 ≤ 3 yi ≥ 0 (i = 1,2,3,4) 74
Giải bài toán đối ngẫu ta được hệ nghiệm : y*(1,0,3/4,0)
Định lý đối ngẫu 2 cho ta hệ : x1.(y1 + 3.y2 + y4 - 1) = 0 (hiển nhiên) x2.(2.y1 + y2 – 3) = 0 → x2 = 0 x3.(y2 + 4.y3 + y4 – 3) = 0 (hiển nhiên) y1.(x1 + 2.x2 – 2) = 0 → x1 + 2.x2 – 2 = 0 → x1 = 2 y2.(3.x1 + x2 + x3 – 4) = 0 (hiển nhiên) y3.(4.x3 – 1) = 0 → x3 = 1/4 y4.(x1 + x3 – 2) = 0 (hiển nhiên)
Ta được hệ nghiệm của bài toán gốc : x*(2,0,1/4) 38 75 Bài 9 : Có mô hình bài toán gốc sau : Min (Z = 4.x1 + 3.x2 + 4.x3) 2.x1 + 3.x2 + 4.x3 ≥ 81 x1 + 2.x2 + 2.x3 ≥ 79 3.x1 + 2.x2 + x3 ≥ 89 x1,x2,x3 ≥ 0 1-Tìm mô hình bài toán đối ngẫu. 2- Tìm nghiệm của bài toán đối ngẫu, từ đó suy ra nghiệm của bài toán gốc. y*(0; 1/4; 5/4) ; x*(5; 37; 0) ; Z = 131 76 Bài 10 : Cho mô hình sau (bài toán go ác) : Min (Z = 2.x1 + x2 + 2.x3) 2.x1 + x2 + x3 ≥ 7 x1 + x2 + x3 ≥ 6 2.x1 + x3 ≥ 5 x1,x2,x3 ≥ 0 Yêu cầu : 1- Tìm mô hình bài to án đối ngẫu của mo â hình trên. 2- Xác định hệ nghiệm của bài to án đối ngẫu, từ đó suy ra hệ nghiệm của bài toán gốc. y*(0; 1; 1/2) ; x*(5/2; 7/2; 0) Z = 17/2