Bài tập Đối ngẫu có lời giải Bài 1 Cho bài toán gốc: f[X] = x1 + 3x2 + 2x3 → min 2x1 + x2 + x3 + x4 ≥ 2 x1 – 2x2 – x3 + 3x4 ≥ 5 –x1 – x2 + x3 + x4 ≥ 1 xj ≥ 0 [j 1,4]= 1] Viết bài toán đối ngẫu. 2] Hãy cho biết nếu giải bằng đơn hình thì bài toán nào ít biến hơn. 3] Hãy tổng quát hóa nhận xét trên. 1] Bài toán đối ngẫu. g[Y] = 2y1 + 5y2 + y3 → max 2y1 + y2 – y3 ≤ 1 y1 – 2y2 – y3 ≤ 3 y1 – y2 + y3 ≤ 2 y1 + 3y2 + y3 ≤ 0 yi ≥ 0 [i 1,3]= 2] Bài toán gốc: có 4 biến, thêm 3 biến phụ để chuyển về dạng chính tắc, thêm 3 biến giả để chuyển về dạng chuẩn. Vậy phải dùng 10 biến. Bài toán đối ngẫu: có 3 biến, thêm 4 biến bù để chuyển về dạng chính tắc. Bài toán chính tắc cũng là bài toán chuẩn. Vậy phải dùng 7 biến. Suy ra, nếu giải bằng đơn hình thì bài toán đối ngẫu dùng ít biến hơn. 3] Tổng quát hóa nhận xét trên: Xét cặp bài toán đối ngẫu có dạng: f [X] CX minAX BX 0= →≥≥ Tg[Y] BY maxA Y CY 0= →≤≥ Trong đó A là ma trận cấp m×n và C ≥ 0. Bài toán gốc [min]: có n biến, thêm m biến phụ để chuyển về dạng chính tắc, thêm m biến giả để chuyển về dạng chuẩn. Vậy phải dùng [n + 2m] biến. Bài toán đối ngẫu [max]: có m biến, thêm n biến bù để chuyển về dạng chính tắc. Bài toán chính tắc cũng là bài toán chuẩn. Vậy phải dùng [m + n] biến. Suy ra, nếu giải bằng đơn hình thì bài toán đối ngẫu dùng ít biến hơn. Bài 2 Xét bài toán QHTT sau: f[X] = x1 + 3x2 + 2x3 + x4 → min 2x1 + x2 + x3 ≥ 2 x1 + x2 + 2x3 ≥ 5 2x1 + 2x2 + 3x3 ≥ 1 xj ≥ 0 [j 1,4]= 1] Hãy chứng tỏ rằng nếu X* là phương án tối ưu thì thành phần thứ 2 và thành phần thứ 4 phải bằng 0. 2] Hãy cho nhận xét. 1] Bài toán đối ngẫu của bài toán trên là: g[Y] = 2y1 + 5y2 + y3 → max 2y1 + y2 + 2y3 ≤ 1 y1 + y2 + 2y3 ≤ 3 y1 + 2y2 + 3y3 ≤ 2 0y1 + 0y2 + 0y3 ≤ 1 yi ≥ 0 [i 1,3]= Nếu bài toán gốc có phương án tối ưu thì bài toán đối ngẫu cũng có phương án tối ưu. Gọi xj và yi là các thành phần của hai phương án tối ưu. Xét cặp điều kiện đối ngẫu: x4 ≥ 0 và 0y1 + 0y2 + 0y3 ≤ 1 Do 0y1 + 0y2 + 0y3 = 0 ≠ 1 nên theo đònh lý độ lệch bù yếu, ta phải có x4 = 0. Xét cặp điều kiện đối ngẫu: x2 ≥ 0 và y1 + y2 + 2y3 ≤ 3 Xét ràng buộc I và II của bài toán đối ngẫu, ta có: y1 + y2 + 2y3 ≤ 2y1 + y2 + 2y3 ≤ 1 ⇒ y1 + y2 + 2y3 ≠ 3 Do y1 + y2 + 2y3 ≠ 3 nên theo đònh lý độ lệch bù yếu, ta phải có x2 = 0. 2] Xét bài toán min với các biến không âm. a] Nếu: • Hàm mục tiêu có xuất hiện biến xj. • Các ràng buộc không chứa xj. Lúc này thì phương án tối ưu, nếu có, phải thỏa điều kiện xj = 0. b] Nếu: • Hệ số cp và cq trong hàm mục tiêu thỏa điều kiện cp < cq. • Hai véctơ cột Ap và Aq thỏa điều kiện Ap ≥ Aq. Lúc này thì phương án tối ưu, nếu có, phải thỏa điều kiện xq = 0. Khi bài toán có các trường hợp đặc biệt này thì ta có thể bỏ bớt biến của bài toán trước khi giải. Bài 3 Xét bài toán sau: Một cửa hàng bán lẻ hiện có 10,2 Kg bánh và 3 Kg kẹo dùng để gói thành các gói quà để bán. Chi tiết của các gói quà cho bởi bảng sau: Gói quà Nguyên liệu A B C Bánh [10g] 6 7 8 Kẹo [10g] 4 3 1 Giá bán [trăm đồng] 34 38 36 1] Cửa hàng này phải đóng bao nhiêu gói mỗi loại để bán được nhiều tiền nhất? 2] Nếu một người đến hỏi mua hết số bánh kẹo nêu trên thì phải trả giá bao nhiêu mỗi ký bánh, kẹo để cửa hàng đồng ý bán và số tiền bỏ ra là ít nhất? 1] Ta mô hình bài toán của cửa hàng thành bài toán QHTT sau: Gọi x1, x2, x3 là số gói quà loại A, B, C được đóng gói. Theo ý nghóa thực tế ta có xj ≥ 0 [j 1,3]= [bỏ qua điều kiện nguyên của biến số]. Lấy đơn vò tiền là trăm đồng thì doanh thu của cửa hàng là: f[X] = 34x1 + 38x2 + 36x3 Theo yêu cầu bài toán là doanh thu cao nhất, ta ghi f[X] → max. Do số bánh bò hạn chế nên: 6x1 + 7x2 + 8x3 ≤ 1.020 Do số kẹo bò hạn chế nên: 4x1 + 3x2 + x3 ≤ 300 Vậy ta có bài toán QHTT: f[X] = 34x1 + 38x2 + 36x3 → max 6x1 + 7x2 + 8x3 ≤ 1.020 4x1 + 3x2 + x3 ≤ 300 xj ≥ 0 [j 1,3]= Thêm ẩn bù, giải bài toán trên bằng đơn hình thì ta có được lời giải như sau: Xmax = [0, 36, 96, 0, 0] với fmax = 4.824 Vậy, khi cửa hàng dùng số bánh kẹo trên để đóng 36 gói loại B và 96 gói loại C thì doanh thu sẽ cao nhất và bằng 482.400 đồng. 2] Gọi y1, y2 là giá [tính theo đơn vò trăm đồng] mỗi 10g bánh, kẹo thì: • y1 ≥ 0, y2 ≥ 0. • Tổng số tiền người mua bỏ ra là g[Y] = 1.020y1 + 300y2. Theo yêu cầu số tiền bỏ ra mua là thấp nhất, ta ghi g[Y] → min. • Để cửa hàng đồng ý bán hết bánh kẹo thì số tiền thu được ứng với số bánh, kẹo có trong mỗi gói quà không được thấp hơn giá bán gói quà. Vậy: 6y1 + 4y2 ≥ 34 7y1 + 3y2 ≥ 38 8y1 + y2 ≥ 36 Tóm lại, bài toán QHTT của người đi mua là: g[Y] = 1.020y1 + 300y2 → min 6y1 + 4y2 ≥ 34 7y1 + 3y2 ≥ 38 8y1 + y2 ≥ 36 y1 ≥ 0, y2 ≥ 0 Đây chính là bài toán đối ngẫu của bài toán đã giải. Vậy, theo đònh lý độ lệch bù yếu, ta có: x2 = 36 ≠ 0 ⇒ 7y1 + 3y2 = 38 [1] x3 = 96 ≠ 0 ⇒ 8y1 + y2 = 36 [2] Giải hệ phương trình [1],[2] ta có Y* = [8/25, 13/25]. Đây chính là phương án tối ưu của bài toán đối ngẫu. Lưu ý đến đơn vò tính và 8/25 = 0,32; 13/25 = 0,52 thì ta có lời giải thực tế như sau: Nếu người mua trả giá 3.200 đ/Kg bánh và 5.200 đ/Kg kẹo thì cửa hàng sẽ đồng ý bán. Số tiền bỏ ra mua 10,2 Kg bánh và 3Kg kẹo là thấp nhất và bằng 482.400 đồng. Bài 4 Hãy chứng tỏ rằng có thể tìm phương án tối ưu của bài toán QHTT tùy ý bằng cách giải một hệ gồm các phương trình tuyến tính và các bất phương trình tuyến tính. Vì mọi bài toán QHTT đều đưa được về dạng chính tắc nên ta xét bài toán chính tắc. Bài toán chính tắc và bài đối ngẫu của nó là cặp bài toán đối ngẫu không đối xứng. Xét hệ gồm các phương trình tuyến tính và các bất phương trình tuyến tính: TAX BX 0A Y CCX BY=≥≤= Nghiệm X, Y của hệ này chính là phương án của bài toán min và bài toán max thỏa điều kiện f[X] = g[Y]. Vậy X, Y là phương án tối ưu của bài toán min và bài toán max. Bài tập Đối ngẫu LẬP BÀI TOÁN ĐỐI NGẪU VÀ TÌM LỜI GIẢI Bài 1 Cho bài toán QHTT: f[X] = x1 + 3x2 + 2x3 + x4 → max 2x1 + x2 + x3 – x4 ≤ 2 x1 + x2 – 2x3 + 2x4 ≤ 5 2x1 – 2x2 + 3x3 ≤ 1 xj ≥ 0 [j 1,4]= Cho biết một phương án tối ưu của bài toán trên là X* = [0, 3, 7/3, 10/3]. Hãy viết bài toán đối ngẫu và cho biết lời giải của bài đối ngẫu. Bài 2 Cho bài toán QHTT: f[X] = x2 – 3x3 + x4 + 2x5 → min x1 + x2 + x3 + x4 = 6 –2x1 – x2 + 2x3 + x5 = 4 2x1 + x2 + x3 ≤ 2 xj ≥ 0 [j 1,5]= 1] Giải bài toán trên. Phương án tối ưu, nếu có, có duy nhất không? 2] Hãy viết bài toán đối ngẫu và cho biết lời giải của bài đối ngẫu. Phương án tối ưu của bài đối ngẫu, nếu có, có duy nhất không? Bài 3 Cho bài toán QHTT: f[X] = –x2 – x3 + 2x4 → max x1 – x2 + 2x3 + x4 = 1 –3x1 + x2 – 3x3 ≤ 2 2x1 – 2x2 + x3 ≤ 4 xj ≥ 0 [j 1,4]= 1] Giải bài toán trên. 2] Hãy viết bài toán đối ngẫu và cho biết lời giải của bài đối ngẫu. Bài 4 Cho bài toán QHTT: f[X] = 3x1 + x2 + 2x3 – x4 → max 2x1 + x2 + x3 ≤ 2 x1 + x2 + 2x3 ≤ 5 2x1 + 2x2 + 3x3 ≤ 1 xj ≥ 0 [j 1,4]= 1] Hãy chứng tỏ nếu X* là phương án tối ưu thì thành phần thứ 1 và thành phần thứ 4 phải bằng 0. 2] Hãy cho nhận xét. MÔ HÌNH THỰC TẾ VÀ BÀI TOÁN ĐỐI NGẪU Bài 5 Một nhà hàng hiện có 10,2 Kg hương liệu A và 3 Kg hương liệu B. Khi pha thêm hai hương liệu này vào thực phẩm thì sẽ làm tăng hương vò, do đó làm tăng giá bán. Các cách phối hợp hai hương liệu này và hiệu quả kinh tế thu được cho bởi bảng sau: Cách pha Hương liệu I II II A [10 g] 6 7 8 B [10 g] 4 3 2 Giá bán tăng thêm [ngàn đồng] 34 38 36 Ngoài cách pha chế, nhà hàng cũng có thể bán hương liệu A và B với giá 2.000đ và 3.000đ mỗi gói 10g. 1] Cửa hàng sẽ chọn giải pháp như thế nào để hiệu quả thu được là cao nhất? 2] Một người muốn mua hương liệu để tự pha chế thì phải trả giá mỗi loại gói 10g là bao nhiêu thì nhà hàng mới có thể bán? 3] Giá hương liệu trên thò trường là bao nhiêu thì cửa hàng không thể dùng cách pha chế hương liệu để làm tăng hiệu quả kinh tế? Bài tập QHTT có lời giải Bài 1 Hãy lập mô hình toán của bài toán sau [không yêu cầu giải]: Một doanh nghiệp đồ gỗ sản xuất bàn, ghế, tủ. Số bàn ghế phải theo tỷ lệ 1:6. Doanh nghiệp hiện có 120 triệu đồng vốn và số lao động tương đương 1000 ngày công. Đònh mức tiêu hao các yếu tố sản xuất, lợi nhuận của từng sản phẩm cho bởi bảng sau. Lập kế hoạch sản xuất sao cho tổng lợi nhuận là lớn nhất. Sản phẩm Yếu tố sản xuất Bàn Ghế Tủ Lao động [ngày công] 2 0,5 3 Chi phí [ngàn đồng] 200 50 350 Lợi nhuận [ngàn đồng] 40 10 60 Gọi x1, x2, x3 là số lượng bàn, ghế, tủ được sản xuất. Theo ý nghóa thực tế, ta có: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 và x1, x2, x3 là số nguyên. Lấy đơn vò tiền là chục ngàn đồng, ta tính được tổng lợi nhuận là: f[X] = 4x1 + x2 + 6x3 Theo yêu cầu của bài toán là tìm phương án sao cho tổng lợi nhuận lớn nhất, ta có f[X] → max. Tổng số ngày công lao động dùng để sản xuất là 2x1 + 0,5x2 + 3x3. Do số ngày công tối đa là 1.000 nên: 2x1 + 0,5x2 + 3x3 ≤ 1.000 hay 4x1 + x2 + 6x3 ≤ 2.000 Lấy đơn vò tiền là ngàn đồng thì tổng chi phí sản xuất là 200x1 + 50x2 + 350x3. Do có 120 triệu đồng [= 120.000 ngàn đồng] vốn nên: 200x1 + 50x2 + 350x3 ≤ 120.000 hay 4x1 + x2 + 7x3 ≤ 2.400 Tỉ lệ bàn ghế là 1:6 nên: 6x1 = x2 hay 6x1 – x2 = 0 Vậy, mô hình toán của bài toán trên là: f[X] = 4x1 + x2 + 6x3 → max 4x1 + x2 + 6x3 ≤ 2.000 4x1 + x2 + 7x3 ≤ 2.400 6x1 – x2 = 0 xj ≥ 0, xj nguyên [j 1,3]= Bài 2 Hãy lập mô hình toán của bài toán sau [không yêu cầu giải]: Người ta cần có đúng 400 đoạn sắt dài 0,9m; 500 đoạn dài 0,8m; 150 đoạn dài 0,6m. Để có được các thanh sắt này, người ta phải cắt những thanh sắt có sẵn dài 2m. Vậy, phải cắt như thế nào để số sắt bò dư ra là ít nhất. Trước hết, ta xét xem mỗi thanh sắt 2m có bao nhiêu cách cắt thành các đoạn con và số sắt dư ra, tính bằng dm, sau mỗi lần cắt: Các cách cắt thanh sắt 2m 1 2 3 4 5 6 7 8 9 10 11 Số đoạn 0,9m 2 1 1 0 0 0 0 0 1 0 0 Số đoạn 0,8m 0 1 0 1 2 0 1 0 0 1 0 Số đoạn 0,6m 0 0 1 2 0 3 1 2 0 0 1 Số sắt dư [dm] 2 3 5 0 4 2 6 8 11 12 14 Gọi xj [j 1, 11]= là số lần cắt thanh sắt 2m theo cách thứ j. Theo ý nghóa thực tế, ta có xj ≥ 0 và xj là số nguyên [j 1, 11]=. Tổng số sắt dư ra sau khi cắt là: f[X] = 2x1 + 3x2 + 5x3 + 4x5 + 2x6 + 6x7 + 8x8 + 11x9 + 12x10 + 14x11 Yêu cầu của bài toán là tổng số sắt dư ra là ít nhất nên ta có f[X] → min. Tổng số thanh sắt 0,9m cắt được là 2x1 + x2 + x3 + x9. Do cần đúng 400 thanh nên ta có ràng buộc: 2x1 + x2 + x3 + x9 = 400 Tổng số thanh sắt 0,8m cắt được là x2 + x4 + 2x5 + x7 + x10. Do cần đúng 500 thanh nên ta có ràng buộc: x2 + x4 + 2x5 + x7 + x10 = 500 Tổng số thanh sắt 0,6m cắt được là x3 + 2x4 + 3x6 + x7 + 2x8 + x11. Do cần đúng 150 thanh nên ta có ràng buộc: x3 + 2x4 + 3x6 + x7 + 2x8 + x11 = 150 Vậy, mô hình toán của bài toán trên là: f[X]= 2x1 + 3x2 + 5x3 + 4x5 + 2x6 + 6x7 + 8x8 + 11x9 + 12x10 + 14x11 → min 2x1 + x2 + x3 + x9 = 400 x2 + x4 + 2x5 + x7 + x10 = 500 x3 + 2x4 + 3x6 + x7 + 2x8 + x11 = 150 xj ≥ 0, xj là số nguyên [j 1, 11]= Bài 3 Một doanh nghiệp có thể sản xuất 3 loại sản phẩm, ký hiệu là A, B, C. Đònh mức hao phí nguyên liệu, vốn, lao động [giờ công] và lợi nhuận thu được tính cho 1 đơn vò sản phẩm mỗi loại cho trong bảng sau đây: Sản phẩm Các yếu tố sản xuất A B C Mức huy động tối đa Nguyên liệu [kg] 2 3 3 150 Vốn [triệu đồng] 1 3 5 120 Lao động [giờ công] 4 8 1 100 Lợi nhuận [triệu đồng] 2 3 5 Doanh nghiệp sẽ sản xuất bao nhiêu đơn vò sản phẩm mỗi loại sao cho trong phạm vi số nguyên liệu, vốn, giờ công huy động được, doanh nghiệp đạt lợi nhuận cao nhất. Hãy lập mô hình toán của bài toán trên rồi giải và cho biết lời giải của bài toán thực tế. Gọi x1, x2, x3 là số đơn vò sản phẩm A, B và C được sản xuất. Theo ý nghóa thực tế, ta có xj ≥ 0 và xj là số nguyên [j 1,3]=. Lấy đơn vò tiền là triệu đồng thì ta tính được tổng lợi nhuận là: f[X] = 2x1 + 3x2 + 5x3 Yêu cầu của bài toán là tìm phương án sản xuất tối ưu. Trong trường hợp này là tìm phương án sao cho tổng lợi nhuận cao nhất nên ta có f[X] → max. Tổng số nguyên liệu, tính theo Kg, dùng để sản xuất là 2x1 + 3x2 + 3x3. Do mức huy động tối đa là 150 nên ta có: 2x1 + 3x2 + 3x3 ≤ 150 Tổng số vốn, tính theo triệu, đầu tư vào sản xuất là x1 + 3x2 + 5x3. Do mức huy động tối đa là 120 nên ta có: x1 + 3x2 + 5x3 ≤ 120 Tổng số lao động, tính theo giờ công, dùng để sản xuất là 4x1 + 8x2 + x3. Do mức huy động tối đa là 100 nên ta có: 4x1 + 8x2 + x3 ≤ 100 Vậy, mô hình toán của bài toán trên là: f[X] = 2x1 + 3x2 + 5x3 → max 2x1 + 3x2 + 3x3 ≤ 150 x1 + 3x2 + 5x3 ≤ 120 4x1 + 8x2 + x3 ≤ 100 xj ≥ 0, xj là số nguyên [j 1,3]= Bỏ qua điều kiện nguyên của ẩn số thì bài toán trên là bài toán QHTT. Để giải ta đưa về dạng chính tắc bằng cách đổi dấu hàm mục tiêu và thêm vào 3 ẩn phụ: –2x1 – 3x2 – 5x3 → min 2x1 + 3x2 + 3x3 + x4 = 150 x1 + 3x2 + 5x3 + x5 = 120 4x1 + 8x2 + x3 + x6 = 100 xj ≥ 0 [j 1,6]= Bài toán chính tắc này là bài toán chuẩn. Phương án cực biên xuất phát là X= [0, 0, 0, 150, 120, 100] với hệ ẩn cơ bản x4, x5, x6. Các bảng đơn hình: -2 -3 -5 0 0 0 Hệ số ACB PACB x1 x2 x3 x4 x5 x6 0 x4 150 2 3 3 1 0 0 0 x5 120 1 3 5 0 1 0 0 x6 100 4 8 1 0 0 1 B.1 0 2 3 5 0 0 0 0 x4 78 7/5 6/5 0 1 -3/5 0 -5 x3 24 1/5 3/5 1 0 1/5 0 0 x6 76 19/5 37/5 0 0 -1/5 1 B.2 -120 1 0 0 0 -1 0 0 x4 50 0 -29/19 0 1 -10/19 -7/19 -5 x3 20 0 4/19 1 0 4/19 -1/19 -2 x1 20 1 37/19 0 0 -1/19 5/19 B.3 -140 0 -37/19 0 0 -18/19 -5/19 Xét bảng 3, do ∆j ≤ 0 [j 1,6]= nên phương án cực biên đang xét là phương án tối ưu của bài toán chuẩn. Ta có: X* = [20, 0, 20, 50, 0, 0] Bỏ đi các ẩn phụ, ta có phương án tối ưu của bài toán xuất phát: Xmax = [20, 0, 20] với fmax = 140 Từ lời giải này, ta có lời giải của bài toán thực tế như sau: Khi doanh nghiệp sản xuất 20 đơn vò sản phẩm A, 20 đơn vò sản phẩm C thì lợi nhuận thu được là cao nhất và bằng 140 triệu đồng. Bài 4 Theo hợp đồng đã ký, một nhà máy sản xuất giấy sẽ phải cung cấp 240 tấn giấy loại A và 140 tấn giấy loại B. Nhà máy hiện có 3 dây chuyền sản xuất giấy. Các chi tiết về mỗi lần sử dụng một dây chuyền sản xuất như sau: • Dây chuyền I: Chi phí 6 triệu. Sản xuất được 1 tấn giấy loại A và 1 tấn giấy loại B, đồng thời tạo ra 2 tấn chất thải. • Dây chuyền II: Chi phí 12 triệu. Sản xuất được 2 tấn giấy loại A và 3 tấn giấy loại B, đồng thời tạo ra 5 tấn chất thải. • Dây chuyền III: Chi phí 10 triệu. Sản xuất được 4 tấn giấy loại A và 1 tấn giấy loại B, đồng thời tạo ra 1 tấn chất thải. Được biết, lượng chất thải trong quá trình sản xuất không được vượt quá 200 tấn. Nhà máy muốn thực hiện hợp đồng với tổng chi phí sản xuất thấp nhất. 1] Lập bài toán ứng với mô hình trên. 2] Giải bài toán trên để tìm kế hoạch sản xuất tối ưu và hiệu quả kinh tế thu được. 1] Gọi x1, x2, x3 là số lần áp dụng dây chuyền sản xuất I, II và III. Theo ý nghóa thực tế, ta có xj ≥ 0 và xj là số nguyên [j 1,3]=. Lấy đơn vò tiền là triệu đồng thì ta tính được tổng chi phí sản xuất là: f[X] = 6x1 + 12x2 + 10x3 Yêu cầu của bài toán là tìm phương án sản xuất sao cho tổng chi phí sản xuất thấp nhất nên ta có f[X] → min. Số tấn giấy loại A sản xuất được là x1 + 2x2 + 4x3. Do phải cung ứng 240 tấn nên ta có: x1 + 2x2 + 4x3 ≥ 240 Số tấn giấy loại B sản xuất được là x1 + 3x2 + x3. Do phải cung ứng 120 tấn nên ta có: x1 + 3x2 + x3 ≥ 120 Số tấn chất thải tạo ra trong quá trình sản xuất là 2x1 + 5x2 + x3. Do lượng chất thải không được vượt quá 200 tấn nên ta có: 2x1 + 5x2 + x3 ≥ 200 Vậy, mô hình toán của bài toán trên là: f[X]= 6x1 + 12x2 + 10x3 → min x1 + 2x2 + 4x3 ≥ 240 x1 + 3x2 + x3 ≥ 120 2x1 + 5x2 + x3 ≤ 200 xj ≥ 0, xj là số nguyên [j 1,3]= 2] Bỏ qua điều kiện nguyên của ẩn số thì bài toán trên là bài toán QHTT. Để giải, ta đưa về dạng chính tắc bằng cách thêm ẩn phụ và ẩn phụ: 6x1 + 12x2 + 10x3 → min x1 + 2x2 + 4x3 – x4 = 240 x1 + 3x2 + x3 – x5 = 120 2x1 + 5x2 + x3 + x6 = 200 xj ≥ 0 [j 1,6]= Bài toán M liên kết: 6x1 + 12x2 + 10x3 + Mx7 + Mx8 → min x1 + 2x2 + 4x3 – x4 + x7 = 240 x1 + 3x2 + x3 – x5 + x8 = 120 2x1 + 5x2 + x3 + x6 = 200 xj ≥ 0 [j 1,8]= Bài toán chuẩn này có phương án cực biên xuất phát là: X= [0, 0, 0, 0, 0, 200, 240, 120] với hệ ẩn cơ bản x7, x8, x6. Các bảng đơn hình: 6 12 10 0 0 0 M M Hệ số ACB PACB x1 x2 x3 x4 x5 x6 x7 x8 M x7 240 1 2 4 -1 0 0 1 0 M x8 120 1 3 1 0 -1 0 0 1 0 x6 200 2 5 1 0 0 1 0 0 0 -6 -12 -10 0 0 0 0 0 B.1 M 360 2 5 5 -1 -1 0 0 0 10 x3 60 1/4 1/2 1 -1/4 0 0 1/4 0 M x8 60 3/4 5/2 0 1/4 -1 0 -1/4 1 0 x6 140 7/4 9/2 0 1/4 0 1 -1/4 0 600 -7/2 -7 0 -5/2 0 0 5/2 0 B.2 M 60 3/4 5/2 0 1/4 -1 0 -5/4 0 10 x3 48 1/10 0 1 -3/10 1/5 0 3/10 -1/5 12 x2 24 3/10 1 0 1/10 -2/5 0 -1/10 2/5 0 x6 32 2/5 0 0 -1/5 9/5 1 1/5 -9/5 768 -7/5 0 0 -9/5 -14/5 0 9/5 14/5 B.3 M 0 0 0 0 0 0 0 -1 -1 Xét bảng 3, do ∆j ≤ 0 [j 1,8]= nên phương án cực biên đang xét là phương án tối ưu của bài toán M. Ta có: XminM = [0, 24, 48, 0, 0, 32, 0, 0] Do các ẩn giả x7 = x8 = 0 nên bài toán chính tắc có phương án tối ưu là: X* = [0, 24, 48, 0, 0, 32] Bỏ đi các ẩn phụ, ta có phương án tối ưu của bài toán xuất phát: Xmin = [0, 24, 48] với fmin = 768. Từ lời giải này, ta có lời giải của bài toán thực tế như sau: Khi nhà máy sử dụng 24 lần dây chuyền sản xuất II và 48 lần dây chuyền sản xuất III thì cung cấp đủ giấy theo hợp đồng với tổng chi phí sản xuất thấp nhất và bằng 768 triệu đồng. Bài tập QHTT LẬP MÔ HÌNH [không yêu cầu giải] Bài 1 Một doanh nghiệp sản xuất bàn và ghế để bán. Mỗi chiếc bàn khi bán sẽ lời được 200 ngàn còn ghế thì 50 ngàn. Theo điều tra thò trường thì có thể bán được ngay 125 bàn và không thể bán được quá 1500 ghế. Ngoài ra, mỗi chiếc bàn bán được thì phải bán kèm theo ít ra là 4 chiếc ghế. Tìm phương án sản xuất tối ưu? Bài 2 Để vận chuyển 120 hành khách và 50 tấn hàng người ta dùng 2 loại xe A và B. Mỗi chiếc xe loại A chở được 15 hành khách và 4 tấn hàng với chi phí vận chuyển là 120 ngàn đồng; mỗi chiếc xe loại B chở được 12 hành khách và 5 tấn hàng với chi phí vận chuyển là 110 ngàn đồng. Vậy dùng xe như thế nào là tốt nhất? Bài 3 Để sơn 120m2 mặt tiền và 100m2 phòng khách người ta dùng sơn màu đỏ và màu xanh. Mỗi lon sơn màu đỏ giá 50 ngàn, sơn được 2m2 mặt tiền và 4m2 phòng khách. Mỗi lon sơn màu xanh giá 55 ngàn, sơn được 3m2 mặt tiền và 3m2 phòng khách. Vậy mua sơn như thế nào là tốt nhất? Bài 4 Người ta muốn pha một loại vàng tây gồm 75% vàng, 12,5% bạc, 12,5% đồng. Các nguyên liệu hiện có là vàng loại A, vàng loại B, vàng loại C và vàng bạc đồng. Chi tiết các loại vàng cùng với giá cả [đơn vò tiền/gam] được cho bởi bảng: Vàng Loại A Loại B Loại C Vàng Bạc Đồng Vàng 92,5% 90% 50% 100% - - Bạc 5% 10% 25% - 100% - Đồng 2,5% - 25% - - 100% Giá cả 5.200 4.900 2.700 6.000 100 1 Hãy cho biết cách pha trộn có giá thành thấp nhất? Bài 5 Một doanh nghiệp sản xuất ra một loại sản phẩm từ hai phân xưởng. Trong một tuần, phân xưởng I sản xuất được tối đa 70 sản phẩm còn phân xưởng II sản xuất được tối đa 100 sản phẩm. Để sản xuất một sản phẩm, phân xưởng I cần 10 giờ công và chi ra 20.000đ cho các chi phí khác, còn phân xưởng II cần 5 giờ công và chi ra 30.000đ cho các chi phí khác. Trong một tuần, doanh nghiệp có thể sử dụng tối đa 100 triệu đồng vốn, 600 giờ công và phải sản xuất tối thiểu 110 sản phẩm. Tìm phương án sản xuất tối ưu. Bài 6 Một công ty bỏ ra 100 triệu để quảng cáo 1 tháng trên tivi, báo, đài. Bắt buộc phải quảng cáo trên tivi ít nhất là 30 lần. Dữ liệu về quảng cáo cho bởi bảng sau: Phương tiện quảng cáo Chi phí Số lần quảng cáo tối đa trong một tháng Dự kiến số người tiếp nhận quảng cáo mỗi lần Tivi 1,5 triệu / phút 60 150.000 Báo 1 triệu / ¼ trang 26 50.000 Đài 500 ngàn / phút 90 10.000 Hãy tìm phương án quảng cáo tối ưu? Bài 7 Một người bỏ ra 100 triệu đồng để cho vay trong 1 năm. Có 3 cách cho vay như sau: • Gởi tiết kiệm không kỳ hạn với lãi suất 3,2% / năm. • Gởi tiết kiệm có kỳ hạn với lãi suất 8,5% / năm. • Cho tư nhân vay với lãi suất 14%. Để giảm thiểu rủi ro, người này được tư vấn rằng: • Không nên cho tư nhân vay quá 20% số vốn. • Phải gởi tiết kiệm ít ra là 30% vốn. • Tỉ lệ tiết kiệm không kỳ hạn trên tiết kiệm có kỳ hạn không quá 1/3. Lập kế hoạch cho vay sao cho tổng lợi nhuận thu được là lớn nhất? Bài 8 Người ta cần có đúng 200 đoạn sắt dài 0,9m; 150 đoạn dài 0,7m. Để có được các thanh sắt này, người ta phải cắt những thanh sắt có sẵn dài 2,2m. Vậy, phải cắt như thế nào để số thanh sắt 2,2m được sử dụng là ít nhất? Bài 9 Người ta cần có đúng 100 tấm thép hình vuông có cạnh 4dm; 120 tấm thép hình vuông có cạnh 3dm. Để có được các tấm thép này, người ta phải cắt những tấm thép hình chữ nhật dài 1,2m và rộng 0,9m. Giá một tấm thép hình chữ nhật là 1.200.000đ và mỗi mét vuông thép vụn thì bán được 200.000đ. Vậy, phải cắt như thế nào là ít tốn tiền nhất? Bài 10 Hãng hàng không Vietnam Airline có nhu cầu vận chuyển 1500 hành khách và 150 tấn hàng hóa tại sân bay Nội Bài. Giả sử có hai loại máy bay có thể sử dụng với khả năng vận chuyển mỗi loại như sau: • Máy bay loại A: Một máy bay có thể chở 180 hành khách và 40 tấn hàng hóa với chi phí tương ứng là 350 triệu đồng. • Máy bay loại B: Một máy bay có thể chở 200 hành khách và 20 tấn hàng hóa với chi phí tương ứng là 320 triệu đồng. Hãy tìm phương án sử dụng số máy bay mỗi loại sao cho thỏa mãn yêu cầu vận chuyển với tổng chi phí ít nhất? Bài 11 Một doanh nghiệp có 3 xưởng may I, II, III cùng sản xuất áo vét và quần. Do trình độ công nhân, khả năng tổ chức, trang bò kỹ thuật ở mỗi xưởng là khác nhau nên hiệu quả của đồng vốn là khác nhau. Cụ thể, cứ mỗi đơn vò tiền đầu tư thì mỗi xí nghiệp sẽ cho ra lượng sản phẩm sau: • Xí nghiệp I: 35 áo vét, 45 quần. • Xí nghiệp II: 40 áo vét, 42 quần. • Xí nghiệp III: 43 áo vét, 30 quần. Suất tiêu hao nguyên liệu và lao động, tức là lượng vải và số giờ công để sản xuất một sản phẩm, cho bởi bảng. Doanh nghiệp hiện có 10.000m vải và huy động được 52.000 giờ công. Theo hợp đồng đã ký thì phải cung cấp 1.500 bộ quần áo. Số hàng hóa lẻ bộ thì quần dễ bán. Hãy cho biết kế hoạch đầu tư vào mỗi xưởng sao cho: • Tổng số vốn đầu tư là thấp nhất. Đây là tiêu chí hàng đầu. • Hoàn thành kế hoạch sản xuất. • Không gặp khó khăn khi tiêu thụ sản phẩm. • Không bò động về vải và lao động. Xưởng Sản phẩm I II III Áo vét 3,5m 20giờ công 3,8m 18giờ công 3,6m 19giờ công Quần 1,2m 3giờ công 1,1m 4giờ công 1,3m 3giờ công Bài 12 Một bà nội trợ muốn có 5 Kg nhân thòt để làm bánh đãi tiệc. Nhân bánh làm từ thòt heo. Bà nội trợ này muốn tỷ lệ chất đạm và mỡ trong nhân bánh là ngang nhau. Bà đi hỏi và được biết: Nạc dăm Ba rọi Đùi Mông Nạt 60% 35% 68% 65% Mỡ 35% 60% 25% 22% Giá [ngàn/Kg] 75 65 60 62 Bà nội trợ này sẽ đi chợ như thế nào? GIẢI BÀI TOÁN QHTT Bài 13 f[X] = x1 + x2 → max x1 – x2 ≥ –2 x1 – 2x2 ≤ 2 x1 + x2 ≤ 4 x1 ≥ 0, x2 ≥ 0 Bài 14 f[X] = x2 – 3x3 + x4 + 2x5 → min x1 + x2 + x3 + x4 = 6 –2x1 – x2 + 2x3 + x5 = 2 2x1 + x2 + 2x3 ≤ 2 xj ≥ 0 [j 1,5]= LẬP MÔ HÌNH VÀ GIẢI BÀI TOÁN QHTT Bài 15 Một doanh nghiệp sản xuất hiện có 1000Kg acid và 600Kg chất tẩy màu, các nguyên liệu và yếu tố sản xuất khác có số lượng lớn, muốn sản xuất hai loại giấy được gọi tên là A và B. Một tấn giấy A cần dùng 50Kg acid và 10Kg chất tẩy màu; một tấn giấy B cần dùng 25Kg acid và 30Kg chất tẩy màu. Giả sử mỗi tấn giấy A sản xuất được sau khi bán sẽ cho một khoảng lợi nhuận là 15 triệu đồng còn mỗi tấn giấy B thì 10 triệu đồng. Doanh nghiệp sẽ sản xuất bao nhiêu giấy A, giấy B [trong khuôn khổ số nguyên liệu hiện có] thì tổng lợi nhuận thu được là lớn nhất? 1] Lập mô hình bài toán trên. 2] Giải để tìm phương án sản xuất tối ưu. Bài 16 Một doanh nghiệp sản xuất bàn và ghế. Để làm ra một chiếc bàn phải tốn 500 ngàn vật liệu và 2 ngày công, còn ghế thì 50 ngàn vật liệu và 0,25 ngày công. Doanh nghiệp hiện có 150 triệu tiền vốn và huy động được 1.200 ngày công. Điều tra thò trường thì doanh nghiệp này biết rằng không thể bán được quá 400 bàn và có thể bán được ngay 1.500 ghế. Mỗi chiếc bàn bán được thì lời 120 ngàn còn ghế thì lời 10 ngàn. Tìm phương án sản xuất tối ưu. 1] Lập mô hình bài toán trên. 2] Giải để tìm phương án sản xuất tối ưu. Bài 17 Một doanh nghiệp có thể sản xuất 3 loại sản phẩm, ký hiệu là S1, S2 và S3. Năng xuất của doanh nghiệp đối với mỗi loại sản phẩm là S1: 50 đơn vò sản phẩm mỗi giờ; S2: 25 đvsp/giờ; S3: 75 đvsp/giờ. Trong một tuần, doanh nghiệp chỉ sản xuất tối đa là 45 giờ. Ngoài ra, trong một tuần, doanh nghiệp chỉ tiêu thụ được không quá 600 đơn vò sản phẩm S1, 800 đvsp S2, 1200 đvsp S3. Giá bán mỗi đơn vò sản phẩm S1 là 40.000đ, một đvsp S2 là 120.000đ và một đvsp S3 là 30.000đ. 1] Lập mô hình bài toán QHTT tìm kế hoạch sản xuất của xí nghiệp trong một tuần cho doanh thu cao nhất? 2] Dựa vào suy luận kinh tế trực tiếp, căn cứ vào giá bán, năng lực sản xuất, năng xuất lao động [sản phẩm/giờ sản xuất], hãy tìm kế hoạch sản xuất tối ưu cho bài toán phần 1]? 3] Bỏ qua điều kiện nguyên ở các biến số, hãy dùng phương pháp đơn hình giải bài toán ở phần 1], tìm kế hoạch sản xuất tối ưu? Bài 18 Khi pha thêm các kim loại A, B, C vào hợp kim thì sẽ làm tăng chất lượng và do đó sẽ làm tăng giá bán. Có 3 cách pha: • Cách 1: Pha thêm 3Kg kim loại A, 200g kim loại B, 40Kg kim loại C sẽ làm 1 tấn hợp kim tăng giá bán lên 288 ngàn. • Cách 2: Pha thêm 4Kg kim loại A, 300g kim loại B, 30Kg kim loại C sẽ làm 1 tấn hợp kim tăng giá bán lên 240 ngàn. • Cách 3: Pha thêm 1Kg kim loại A sẽ làm 1 tấn hợp kim tăng giá bán lên 12 ngàn. Một nhà máy luyện kim hiện có là 4,8 tấn kim loại A, 340Kg kim loại B và 44 tấn kim loại C. Hãy tìm kế hoạch sản xuất tối ưu cho nhà máy và hiệu quả kinh tế khi áp dụng kế hoạch sản xuất này? Bài tập Vận tải có lời giải Bài 1 Cho bài toán vận tải: A = [33, 39, 12] B = [15, 15, 19, 21, 14] C = 8 11 7 6 106 12 12 5 125 14 7 8 15 1] Giải bài toán trên. 2] Phương án tối ưu có duy nhất không, tại sao? Đây là bài toán cân bằng thu phát. Dùng phương pháp chi phí thấp nhất để thành lập phương án cực biên xuất phát rồi giải tiếp, ta có các bảng vận tải sau: 8 − 0 11 [3] + 7 19 6 [1] 10 14 -8 6 + 3 12 − 15 12 5 21 12 -6 5 12 14 7 8 15 -5 0 6 -1 -1 2 B.1 Tại bảng 1 thì θo = 0 nên phương án cực biên tại bảng 2 cũng chính là phương án cực biên tại bảng 1. Lưu ý rằng, trong bảng 2 thì ô [r, s], tức là ô [1, 2], sẽ trở thành ô chọn còn ô [g, h], tức là ô [1, 1] sẽ trở thành ô loại: 8 11 + 0 7 – 19 6 10 14 0 6 + 3 12 – 15 12 5 21 12 -1 5 – 12 14 7 * + 8 15 0 5 11 7 4 10 B.2 Tại bảng 2 thì ∆ij ≤ 0 ∀[i, j] nên phương án cực biên đang xét là phương án tối ưu. Ta có: Xmin = 0 0 19 0 143 15 0 21 012 0 0 0 0 với zmin = 636 2] Vì ô [3, 3] là ô loại và ∆33 = 0 nên ta xem ô [3, 3] là ô [r, s], thêm ô này vào tập ô chọn và ô chọn giả, tìm vòng, lập bảng 3: 8 11 12 7 7 6 10 14 0 6 15 12 3 12 5 21 12 -1 5 14 7 12 8 15 0 5 11 7 4 10 B.3 Do độ giảm hàm mục tiêu từ bảng 2 xuống bảng 3 là θo∆rs = 0 nên phương án cực biên tại bảng 3 cũng là phương án tối ưu: X′min = 0 12 7 0 1415 3 0 21 00 0 12 0 0 Phương án tối ưu X′min khác phương án tối ưu Xmin tại bảng 2. Vậy, bài toán không duy nhất phương án tối ưu. Bài 2 Giải bài toán vận tải: A = [39, 12, 20] B = [24, 33, 62] C = 4 3 65 2 78 3 5 Do 39+12+20=71 < 24+33+62=119 nên đây là bài toán vận tải mà kho có ít hàng hơn. Ta lập thêm một kho giả có lượng hàng bò thiếu là 119–71 = 48. Chi phí vận chuyển một đơn vò hàng từ kho giả ra mọi cửa hàng đều bằng 0. Lúc này ta có bài toán cân bằng thu phát. Dùng phương pháp chi phí thấp nhất để thành lập phương án cực biên xuất phát rồi giải tiếp, ta có các bảng vận tải sau: 4 + 18 3 − 21 6 -4 5 2 12 7 -3 8 3 [1] + 5 − 20 -5 0 − 6 0 0 + 42 0 0 -1 0 B.1 4 24 3 15 6 -3 5 2 12 7 -2 8 3 6 5 14 -3 0 0 0 48 2 1 0 2 B.2 Tại bảng 2 thì ∆ij ≤ 0 ∀[i, j] nên phương án cực biên đang xét là phương án tối ưu. Bỏ đi kho giả, ta có: Xmin = 24 15 00 12 00 6 14 với zmin = 253 Bài 3 Giải bài toán vận tải sau đây với yêu cầu cửa hàng thứ 2 và thứ 4 nhận đủ hàng: A = [15, 25, 35] B = [10, 20, 30, 60] C = 1 3 6 96 8 2 73 9 3 6 Do kho ít hàng hơn nên ta thêm một kho giả [kho thứ 4] có lượng hàng chênh lệch là 45. Theo điều kiện cửa hàng thứ 2 và thứ 4 nhận đủ hàng nên ô [4, 2] và [4, 4] là ô cấm. Vậy, ta điều chỉnh c42 và c44 thành M [M là số dương đủ lớn]. Lúc này ta có bài toán cân bằng thu phát. Dùng phương pháp chi phí thấp nhất để thành lập phương án cực biên xuất phát rồi giải tiếp, ta có các bảng vận tải sau: 1 3 + 15 6 9 − 0 -9 6 8 2 7 25 -7 3 9 3 6 35 -6 0 10 M – 5 0 30 M [6] + -M-6 -M-6 -6 -M-6 0 B.1 1 3 15 6 9 M-3 6 8 2 7 25 M-7 3 9 3 6 35 M-6 0 10 M 5 0 30 M 0 0 0 M 0 M B.2 Tại bảng 2 thì ∆ij ≤ 0 ∀[i, j] nên phương án cực biên đang xét là phương án tối ưu của bài toán M. Do phải phân phối hàng vào ô cấm [4, 2] nên bài toán có ô cấm vô nghiệm do không có phương án. Bài 4 Hãy lập mô hình toán của bài toán sau [không yêu cầu giải]: Người ta cần trồng 4 giống lúa trên 3 thửa ruộng. Do đặc điểm của mỗi giống lúa và mỗi thửa ruộng là khác nhau nên chi phí trồng lúa trên 1 ha là khác nhau và được cho bởi bảng: Giống lúa Thửa ruộng L1 L2 L3 L4 R1 2 3 2 3 R2 3 3 × 2 R3 1 4 3 × Được biết, diện tích mỗi thửa ruộng lần lượt là 30ha, 60ha và 45ha còn tổng diện tích cần trồng mỗi giống lúa lần lượt là 28ha, 12ha, 10ha và 20ha. Ngoài ra, người ta cũng biết rằng trên thửa ruộng 2 không trồng được giống lúa thứ 3, trên thửa ruộng 3 không trồng được giống lúa 4. Hãy cho biết phải phân phối đất trồng như thế nào để tổng chi phí là thấp nhất. Quan niệm mỗi thửa ruộng là một trạm phát và diện tích thửa ruộng là lượng hàng có tại trạm phát, ta có A = [30, 60, 45]. Quan niệm mỗi giống lúa là một trạm thu và diện tích cần trồng là lượng hàng mà trạm thu cần nhận, ta có B = [28, 12, 10, 20]. Từ bảng chi phí trồng các giống lúa ta có ma trận C. Do thửa ruộng 2 không trồng được giống lúa thứ 3 và trên thửa ruộng 3 không trồng được giống lúa 4 nên ô [2, 3] và [3, 4] là ô cấm. Ta gán c23 = M, c34 = M với M là một số dương đủ lớn. Gọi xij là số ha đất trên thửa ruộng thứ i dùng để trồng giống lúa thứ j. Ta có xij ≥ 0 [i 1,3; j 1,4]= =. Vậy, bài toán trên có mô hình toán là bài toán vận tải có ô cấm sau: A = [30, 60, 45] B = [28, 12, 10, 20] C = 2 3 2 33 3 M 21 4 3 M Bài 5 Một doanh nghiệp cần mua gỗ cho các xưởng sản xuất bàn ghế từ một số đòa phương. Nhu cầu gỗ cho nhà máy đặt tại Bình Dương là 250m3, tại quận 12 là 125m3, tại Thủ Đức là 100m3. Hiện nay trại gỗ tại Di Linh đang bán 300 m3 gỗ, tại Đắc Lắc đang bán 80m3 gỗ và tại Kontum đang bán 120m3 gỗ. Được biết giá gỗ tại Di Linh là thấp nhất còn tại Đắc Lắc và Kontum là cao ngang nhau. Phí vận chuyển [chục ngàn/m3] cho bởi bảng: Xưởng tại Bình Dương Xưởng tại quận 2 Xưởng tại Thủ Đức Trại gỗ Di Linh 20 40 35 Trại gỗ Đắc Lắc 15 45 40 Trại gỗ Kontum 18 50 45 Hãy tìm cách mua gỗ và vận chuyển sao cho tổng chi phí vận chuyển là thấp nhất. Quan niệm mỗi trại gỗ là một trạm phát và số m3 gỗ đang bán là lượng hàng có tại trạm phát, ta có A = [300, 80, 120]. Quan niệm mỗi xưởng là một trạm thu và nhu cầu gỗ của mỗi xưởng là lượng hàng mà trạm thu cần nhận, ta có B = [250, 125, 100]. Từ bảng chi phí vận chuyển ta có ma trận C. Do giá gỗ tại Di Linh thấp nhất nên doanh nghiệp sẽ ưu tiên mua hết gỗ tại Di Linh. Vậy, yêu cầu của bài toán là trạm phát 1 phải phát hết hàng. Gọi xij là số m3 gỗ chở từ trạm phát thứ i về trạm thu thứ j. Ta có xij ≥ 0 [i 1, 3; j 1,4]= =. Vậy, bài toán trên có mô hình toán là bài toán vận tải sau đây với yêu cầu tram phát 1 phải phát hết: A = [300, 80, 120] B = [250, 125, 100] C = 20 40 3515 45 4018 50 45 Do trạm phát nhiều hàng hơn nên ta thêm một trạm thu giả [trạm thu thứ 4] nhận lượng hàng chênh lệch là 25. Theo yêu cầu trạm phát 1 phát hết hàng nên ô [1, 4] sẽ là ô cấm. Vậy, ta điều chỉnh c14 thành M [M là số dương đủ lớn]. Lúc này ta có bài toán vận tải cân bằng thu phát. Dùng phương pháp chi phí thấp nhất để thành lập phương án cực biên xuất phát. Theo cách giải đã biết, ta có: Xmin = 75 125 100 080 0 0 095 0 0 25 với zmin = 12.910 Vậy kế hoạch mua gỗ tối ưu là: • Mua tại Di Linh 75m3 gổ, tại Đắc Lắc 80m3 gỗ, tại Kontum 95m3 gỗ để cung cấp xưởng sản xuất tại Bình Dương. • Mua tại Di Linh 125m3 gỗ cho xưởng sản xuất tại quận 2. • Mua tại Di Linh 100m3 gỗ cho nhà xưởng sản xuất tại quận Thủ Đức. Tổng chi phí vận chuyển thấp nhất là 129 triệu 1 trăm ngàn đồng. Bài 6 Một xí nghiệp may có 50 thợ tay nghề cấp 1, 30 thợ tay nghề cấp 2 và 40 thợ tay nghề cấp 3 đứng may áo trên 40 máy may loại 1, 60 máy may loại 2, 20 máy may loại 3. Năng suất [số lượng áo/giờ] của mỗi người thợ thuộc một cấp tay nghề khi sử dụng một loại máy may cho bởi bảng sau: Máy may loại 1 loại 2 loại 3 Thợ cấp 1 7 8 9 Thợ cấp 2 6 7 8 Thợ cấp 3 4 6 7 Tìm cách phân công thợ sao cho tổng năng suất là cao nhất. Quan niệm mỗi cấp thợ là một trạm phát và số thợ là lượng hàng có tại trạm phát, ta có A = [50, 30, 40]. Quan niệm mỗi loại máy may là một trạm thu và số thợ đứng máy là lượng hàng mà trạm thu cần nhận, ta có B = [40, 60, 20]. Từ bảng năng suất ta có ma trận C. Gọi xij là số thợ có tay nghề cấp i được phân công đứng trên máy may loại j. Ta có xij ≥ 0 [i 1, 3; j 1,3]= = [bỏ qua điều kiện nguyên]. Vậy, bài toán trên có mô hình toán là bài toán vận tải max sau đây: A = [50, 30, 40] B = [40, 60, 20] C = 7 8 96 7 84 6 7 Theo cách giải đã biết, ta tìm được phương án tối ưu của bài toán trên là: Xmax = 30 0 2010 20 00 40 0 với zmax = 830 Vậy, cách phân công thợ tối ưu là: • Phân công 30 thợ tay nghề cấp 1 đứng may trên 30 máy may loại 1. • Phân công 20 thợ tay nghề cấp 1 đứng may trên 20 máy may loại 3. • Phân công 10 thợ tay nghề cấp 2 đứng may trên 10 máy may loại 1. • Phân công 20 thợ tay nghề cấp 2 đứng may trên 20 máy may loại 2. • Phân công 40 thợ tay nghề cấp 2 đứng may trên 40 máy may loại 2. Với cách phân công này thì năng suất sẽ đạt tối đa và bằng 830 áo trong 1 giờ. Bài tập Vận tải GIẢI BÀI TOÁN VẬN TẢI Bài 1 Giải bài toán vận tải sau: A = [218, 210, 105, 12] B = [123, 142, 115, 165] C = 12 65 74 2816 67 72 3317 63 73 2918 68 77 30 Bài 2 Cho bài toán vận tải: A = [50, 40, 20] B = [40, 30, 20, 20] C = 5 1 3 41 2 1 33 4 5 6 Giải bài toán và cho biết phương án tối ưu có duy nhất không, tại sao? Bài 3 Cho bài toán vận tải max sau: A = [50, 30, 40] B = [40, 60, 20] C = 7 8 96 7 84 6 7 Giải bài toán và cho biết phương án tối ưu có duy nhất không, tại sao? Bài 4 Cho bài toán vận tải sau: A = [40, 50, 60] B = [25, 35, 45] C = 7 8 62 7 89 6 7 Giải bài toán trên với yêu cầu là kho 1 phải phát hết và kho 2 không được phát vào cửa hàng 3. Bài 5 Cho bài toán vận tải sau: A = [40, 50] B = [25, 35, 30] C = 7 8 62 7 8 1] Viết bài toán trên thành bài toán QHTT. Bài toán có bao nhiêu biến, bao nhiêu ràng buộc? 2] Viết bài toán đối ngẫu của bài toán QHTT trên với ký hiệu biến là u1, u2, v1, v2, v3. 3] Phát biểu đònh lý độ lệch bù yếu với cặp bài toán đối ngẫu trên. Bài 6 Cho bài toán vận tải sau: A = [40, 65] B = [25, 35, 40] C = 7 8 62 7 8 Với yêu cầu kho 1 phải phát hết hàng, hãy viết bài toán trên thành bài toán QHTT. LẬP MÔ HÌNH [không yêu cầu giải] Bài 7 Đại hội thế vận diễn ra cùng ngày tại 4 đòa điểm. Người ta cần chở đến các một số thiết bò từ 3 nơi cung cấp. Các dữ liệu về lượng hàng cần chuyên chở và khoảng cách giữa các đòa điểm được cho bởi bảng: Thu Phát 15 10 17 18 20 160 50 100 70 23 100 200 30 120 10 50 40 30 50 Do đặc điểm của các phương tiện vận chuyển và yêu cầu về thời gian nên không thể chở hàng đi xa quá 150Km. Tìm phương án vận chuyển tối ưu. Bài 8 Một cửa hàng bán gạo cần phân phối gạo từ 3 kho đến 4 đại lý. Số bao gạo có trong mỗi kho và số bao gạo mà mỗi đại lý có thể nhận cho bởi bảng: Thu Phát 170 150 210 160 120 4 1 1 2 230 5 4 2 3 310 6 2 3 1 Được biết, đại lý I yêu cầu được nhận không dưới 145 bao gạo. Lập kế hoạch phân phối tối ưu. LẬP MÔ HÌNH VÀ GIẢI Bài 9 Công ty trang trại Cao Nguyên dự đònh trồng 02 loại cây cà phê & tiêu trên 3 khu đất A, B, C có diện tích tương ứng là: 50, 60, 40 [ha]. Do đặc điểm của các khu đất khác nhau nên chi phí sản xuất [triệu đồng/ha] và năng suất [tạ/ha] khác nhau và cho ở bảng sau: Khu đất Cà phê Tiêu A 2 9 1,8 6 B 2,2 10 1,6 5 C 2,5 12 1,5 4 [Số liệu ở góc bên trái, phía trên của mỗi ô là chi phí SX; ở góc bên phải phía dưới của mỗi ô là năng suất] Yêu cầu sản lượng của cà phê tối thiểu là 500 tạ và tiêu tối thiểu là 420 tạ. Hãy xác đònh phương án phân phối đất trồng sao cho đảm bảo yêu cầu về sản lượng với chi phí thấp nhất. Bài 10 Một công ty xây dựng muốn mua sắt để xây dựng các khu nhà tại quận 2, quận Thủ Đức, quận Bình Thạnh từ các nhà máy Luyện cán thép tại Biên Hoà, Bình Dương và quận Tân Bình. Nhu cầu sắt xây khu nhà tại quận 2 là 1250 tấn, tại Thủ Đức là 500 tấn và tại Bình Thạnh là 650 tấn. Công ty mua được tại Nhà máy thép Biên Hoà 800 tấn, tại Bình Dương mua được 900 tấn và tại Tân Bình mua được 1200 tấn. Phí vận chuyển [tấn/chục ngàn] cho bởi bảng sau: Khu nhà q.2 Khu nhà Thủ Đức Khu nhà Bình Thạnh Nhà máy tại Biên Hoà 3 2 8 Nhà máy tại Bình Dương 7 6 12 Nhà máy tại Tân Bình 4 5 3 Biết rằng hiện nay không thể chở sắt từ quận Tân Bình về quận 2. Lập phương án vận chuyển sắt sao cho các khu xây dựng nhận đủ sắt và tổng chi phí vận chuyển là thấp nhất. Bài 11 Một trang trại có 3 mảnh đất đònh dùng để trồng 4 loại cây. Lợi nhuận thu được khi trồng mỗi loại cây trên mỗi loại đất, diện tích mỗi mảnh đất, diện tích đònh trồng mỗi loại cây cho bởi bảng sau. Lập kế hoạch phân phối đất trồng sao cho tổng lợi nhuận thu được là lớn nhất, biết rằng trên mảnh đất thứ 2 không được trồng loại cây thứ 2. Lợi nhuận [đơn vò tiền/ha] Loại cây 1 Loại cây 2 Loại cây 3 Loại cây 4 Diện tích mảnh đất [ha] Mảnh đất 1 22 25 20 18 250 Mảnh đất 2 30 32 25 28 1.400 Mảnh đất 3 29 28 25 23 350 Tổng diện tích trồng [ha] 500 400 600 500 1. Giới thiệu bài toán quy hoạch tuyến tính 1.1 Các mô hình 1.1.1 Sản xuất với tài nguyên bò hạn chế Doanh nghiệp hiện có 400m3 gỗ và 50 tấn acid. Sản xuất giấy A, B. Giá bán 4tr.đ/tấn, 5tr.đ/tấn. Mức tiêu hao gỗ [m3/tấn] và acid [tấn/tấn]: Sản phẩm Nguyên liệu A B Gỗ 1,2 1,4 Acid 0,1 0,25 Sản xuất sao cho tổng doanh thu là lớn nhất? Đặt biến Gọi x1, x2 là số tấn giấy A và B được sản xuất. Theo thực tế thì x1 ≥ 0 và x2 ≥ 0. Hàm mục tiêu Gọi f là tổng doanh thu [tr.đ]: f[X] = 4x1 + 5x2 Theo đề bài thì f[X] → max. Các ràng buộc Gỗ: 1,2x1 + 1,4x2 ≤ 400 Acid: 0,1x1 + 0,25x2 ≤ 50 Mô hình toán 1 21 21 21 2f [X] 4x 5x max 1,2x 1,4x 400 0,1x 0, 25x 50 x 0, x 0= + →+ ≤+ ≤≥ ≥ 1.1.2 Sản xuất để cung ứng Xẻ gỗ để đóng bàn, ghế. Mỗi lần dùng 1m3 gỗ. Cách I đóng được 4 bàn, 6 ghế. Tiền công 1,2tr.đ Cách II 2 bàn, 15 ghế. Tiền công 1,1tr.đ. Cách III 3 bàn, 9 ghế. Tiền công 1,4tr.đ. Giá 1m3 gỗ là 4.000.000đ. Phải sản xuất để cung cấp 31 bàn, 90 ghế. Kế hoạch xẻ gỗ để tổng chi phí thấp nhất? Đặt biến x1, x2, x3 là số lần xẻ gỗ theo cách I, II, III. x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 và x1, x2, x3 là số nguyên. Hàm mục tiêu Gọi f là tổng chi phí [tr.đ]: f[X] = 5,2x1 + 5,1x2 + 5,4x3 Theo đề bài thì f[X] → min. Các ràng buộc 4x1 + 2x2 + 3x3 ≥ 31 6x1 + 15x2 + 9x3 ≥ 90 Mô hình toán 1 2 31 2 31 2 31 2 3 1 2 3f [X] 5,2x 5,1x 5,4x min 4x 2x 3x 31 6x 15x 9x 90 x 0, x 0, x 0, x , x , x là số nguyên= + + →+ + ≥+ + ≥≥ ≥ ≥