intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Ôn thi Cao học môn Toán kinh tế (Trần Ngọc Hội) – Bài giải Qui hoạch tuyến tính

Chia sẻ: Lee KenVil | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
872
lượt xem 462
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một trại chăn nuôi sử dụng 3 loại thực phẩm I, II, III. Lượng chất dinh dưỡng Albumin, chất ÔN THI CAO HỌC béo, chất đạm cho gia súc trong 1 ngày cũng như tỉ lệ các chất này trong 3 loại thức ăn được cho trong bảng sau:

Chủ đề:

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

Lưu

Nội dung Text: Ôn thi Cao học môn Toán kinh tế (Trần Ngọc Hội) – Bài giải Qui hoạch tuyến tính

  1. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội 2. Một trại chăn nuôi sử dụng 3 loại thực phẩm I, II, III. Lượng chất dinh dưỡng Albumin, chất ÔN THI CAO HỌC béo, chất đạm cho gia súc trong 1 ngày cũng như tỉ lệ các chất này trong 3 loại thức ăn được cho MÔN TOÁN KINH TẾ trong bảng sau: Chất Lượng cần Tỉ lệ có trong thực phẩm (GV: Trần Ngọc Hội - 2011) dinh dưỡng trong ngày I II III Albumin Ít nhất 20kg 20% 10% 10% Chất béo Đúng 10kg 30% 40% 20% BÀI GIẢI Chất đạm Không quá 15kg 5% 30% 30% PHẦN I: QUI HOẠCH TUYẾN TÍNH Giá 1kg của từng loại thực phẩm I, II, III lần lượt là 80, 120, 90 (ngàn). Cần lập kế hoạch mua các loại thực phẩm theo đúng yêu cầu trong ngày sao cho tổng chi phí thấp nhất. a) Lập mô hình bài toán. 1. Một xí nghiệp sản xuất đồ gỗ sản xuất 4 loại bàn A, B, C, D. Xí nghiệp có hai phân xưởng: Phân xưởng mộc và phân xưởng trang trí. Số giờ công có thể huy động được cho hai phân xưởng b) Mô hình bài toán thay đổi thế nào nếu có yêu cầu lượng Albumin không vượt quá hai tương ứng lần lượt là 1000 và 2500. Số gỗ quý có thể mua được là 350m3. Suất tiêu hao gỗ và lao lần lượng chất đạm? động đối với mỗi loại bàn và mỗi lọai công việc, cũng như lãi cho 1 bàn mỗi loại được cho trong Giải. Gọi x1, x2, x3 (kg) lần lượt là lượng thực phẩm loại I, II, III cần mua. Điều kiện: xj ≥ 0 bảng sau: (j = 1, 2, 3). Khi đó Bàn A B C D 1) Chi phí mua thực phẩm là: f(x) = 80x1 + 120x2 + 90x3 (đv: ngàn). Công việc 2) Lượng Albumin có được là: 0,2x1 + 0,1x2 + 0,1x3 (kg). 0,08m3/4h 0,12m3/6h 0,3m3/9h 0,21m3/12h Mộc Ta phải có 0,2x1 + 0,1x2 + 0,1x3 ≥ 20. Trang trí 1h 2h 3h 4h 3) Lượng chất béo có được là: 0,3x1 + 0,4x2 + 0,2x3 (kg). Ta phải có 0,3x1 + 0,4x2 + 0,2x3 = 10. Lãi 250000đ 350000đ 380000đ 850000đ 4) Lượng chất đạm có được là: 0,05x1 + 0,3x2 + 0,3x3 (kg). Lập mô hình bài toán tìm kế họach sản xuất để tổng số lãi thu được lớn nhất. Ta phải có 0,05x1 + 0,3x2 + 0,3x3 ≤ 15. Giải. Gọi x1, x2, x3, x4 lần lượt là số bàn loại A, B, C D cần sản xuất. Điều kiện: xj ≥ 0 (j= 1, 2, 3, a) Ta có mô hình bài toán: 4). Khi đó (1) f(x) = 80x1 + 120x2 + 90x3 min ⎧0, 2x1 + 0,1x 2 + 0,1x 3 ≥ 20 1) Tiền lãi thu được là: f(x) = 25x1 + 35x2 + 38x3 + 85x4 (đv: mười ngàn). ⎪ 2) Lượng gỗ được sử dụng là: 0,08x1 + 0,12x2 + 0,3x3+ 0,21x4 (m3). (2) ⎨0, 3x1 + 0, 4x2 + 0, 2x3 = 10 Ta phải có 0,08x1 + 0,12x2 + 0,3x3+ 0,21x4 ≤ 350. ⎪0, 05x + 0, 3x + 0, 3x ≤ 15 ⎩ 3) Số giờ công lao động được sử dụng ở phân xưởng mộc là: 1 2 3 4x1 + 6x2+ 9x3+ 12x4 (h) (3) x j ≥ 0 (j = 1, 3) Ta phải có 4x1 + 6x2+ 9x3+ 12x4 ≤ 1000. b) Nếu có thêm yêu cầu lượng Albumin không vượt quá hai lần lượng chất đạm thì ta phải có: 4) Số giờ công lao động được sử dụng ở phân xưởng trang trí là: 0,2x1 + 0,1x2 + 0,1x3 ≤ 2(0,05x1 + 0,3x2 + 0,3x3) ⇔ 0,1x1 – 0,5x2 – 0,5x3 ≤ 0. x1 + 2x2+ 3x3+ 4x4 (h) Do đó ta có mô hình bài toán: Ta phải có x1 + 2x2+ 3x3+ 4x4 ≤ 2500. (1) f(x) = 80x1 + 120x2 + 90x3 min Vậy ta có mô hình bài toán: ⎧0, 2x1 + 0,1x 2 + 0,1x 3 ≥ 20 (1) f(x) = 25x1 + 35x2 + 38x3 + 85x4 max ⎪0, 3x + 0, 4x + 0, 2x = 10 ⎧0, 08x1 + 0,12x 2 + 0, 3x 3 + 0, 21x 4 ≤ 350 ⎪ 1 2 3 (2) ⎨ ⎪ 0, 05x1 + 0, 3x 2 + 0, 3x 3 ≤ 15 (2) ⎨4x1 + 6x 2 + 9x 3 + 12x 4 ≤ 1000 ⎪ ⎪ x + 2x + 3x + 4x ≤ 2500 ⎪0,1x1 − 0, 5x 2 − 0, 5x 3 ≤ 0 ⎩ ⎩1 2 3 4 (3) xj ≥ 0 (j = 1, 3) (3) xj ≥ 0 ( j = 1, 4) 1 2 Printed with FinePrint trial version - purchase at www.fineprint.com
  2. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội ⎧ x1 + 2x 2 ≤ 25000 3. Để sản xuất 3 loại sản phẩm A, B, C cần dùng 4 loại nguyên liệu I, II, III, IV. Lượng dự trữ ⎪ x + 2x ≥ 10000 nguyên liệu, định mức tiêu hao nguyên liệu, tiền lãi cho 1 đơn vị sản phẩm được cho trong bảng ⎪1 2 sau: ⎪2x1 + 3x 2 + 7x 3 ≤ 30000 ⎪ (2) Nguyên liệu Lượng Định mức tiêu hao nguyên liệu(kg) cho 1đv ⎨ ⎪4x1 + x 3 ≤ 35000 dự trữ (tấn) A B C ⎪4x1 + x 3 ≥ 15000 I 25 1 2 0 ⎪ ⎪ x 2 + 4x 3 ≤ 40000 II 30 2 3 7 ⎩ III 35 4 0 1 (3) xj ≥ 0 (j = 1, 3) IV 40 0 1 4 Tiền lãi cho 1đv 6 7 8 4. Hai kho I và II có nhiệm vụ cung cấp sắt cho hai công trường xây dựng A và B. Kho I có khả Cần lập kế hoạch sản xuất để không bị động về nguyên liệu và tổng lãi đạt cao nhất. năng cung cấp 60 tấn, kho II có khả năng cung cấp 40 tấn. Công trường A cần ít nhất 50 tấn, công trường B cần ít nhất 30 tấn. Cước phí vận chuyển (đv: ngàn đồng) 1tấn sắt từ các kho đến các a) Lập mô hình bài toán. công trường được cho trong bảng sau: b) Mô hình bài toán thay đổi thế nào nếu trong lượng nguyên liệu dự trữ có 10 tấn loại I và A B 15 tấn loại III sắp hết hạn sử dụng? I 40 10 Giải. Gọi x1, x2, x3 lần lượt là số đơn vị sản phẩm loại A, B, C cần sản xuất. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó II 20 30 1) Tiền lãi thu được là: f(x) = 6x1 + 7x2 + 8x3. Lập mô hình bài tóan tìm kế hoạch vận chuyển sao cho đảm bảo được nhu cầu xây dựng mà chi 2) Lượng nguyên liệu I cần sử dụng là: x1 + 2x2 (kg). phí vận chuyển đạt thấp nhất. Ta phải có x1 + 2x2 ≤ 25000 (25000kg = 25tấn). Giải. Gọi 3) Lượng nguyên liệu II cần sử dụng là: 2x1 + 3x2+ 7x3 (kg). • x1, x2 (tấn) lần lượt là lượng sắt cần chuyển từ kho I đến hai công trường A, B. Ta phải có 2x1 + 3x2+ 7x3 ≤ 30000 (30000kg = 30tấn). 4) Lượng nguyên liệu III cần sử dụng là: 4x1 + x3 (kg). • x3, x4 (tấn) lần lượt là lượng sắt cần chuyển từ kho II đến hai công trường A, B. Ta phải có 4x1 + x3 ≤ 35000 (35000kg = 35tấn). 5) Lượng nguyên liệu IV cần sử dụng là: x2 + 4x3 (kg). Điều kiện: xj ≥ 0 (j= 1, ..., 4). Khi đó Ta phải có x2 + 4x3 ≤ 40000 (40000kg = 40tấn). 1) Chi phí vận chuyển là: f(x) = 40x1 + 10x2 + 20x3 + 30x4 (ngàn đồng). 2) Lượng sắt kho I xuất ra là: x1 + x2 (tấn). a) Ta có mô hình bài toán: Ta phải có x1 + x2 ≤ 60. (1) f(x) = 6x1 + 7x2 + 8x3 max 3) Lượng sắt kho II xuất ra là: x3 + x4 (tấn). ⎧ x1 + 2x 2 ≤ 25000 Ta phải có x3 + x4 ≤ 40. ⎪2x + 3x + 7x ≤ 30000 ⎪1 4) Lượng sắt công trường A nhận được là: x1 + x3 (tấn). 2 3 (2) ⎨ 4x1 + x 3 ≤ 35000 Ta phải có x1 + x3 ≥ 50. ⎪ 5) Lượng sắt công trường B nhận được là: x2 + x4 (tấn). ⎪ x 2 + 4x 3 ≤ 40000 ⎩ Ta phải có x2 + x4 ≥ 30. (3) xj ≥ 0 (j = 1, 3) Ta có mô hình bài toán: b) Nếu trong lượng nguyên liệu dự trữ có 10 tấn loại I và 15 tấn loại III sắp hết hạn sử dụng thì ta (1) f(x) = 40x1 + 10x2 + 20x3 + 30x4 min nhất thiết phải sử dụng hết lượng này, nghĩa là ta cần thêm điều kiện: ⎧ x1 + x 2 ≤ 60 x1 + 2x2 ≥ 10000 và 4x1 + x3 ≥ 15000. ⎪ x + x ≤ 40 ⎪3 4 (2) ⎨ Ta có mô hình bài toán: x1 + x 3 ≥ 50 ⎪ (1) f(x) = 6x1 + 7x2 + 8x3 max ⎪ x 2 + x 4 ≥ 30 ⎩ (3) xj ≥ 0 (j = 1, 4) 3 4 Printed with FinePrint trial version - purchase at www.fineprint.com
  3. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội (Trong mỗi ô, số liệu ở góc trái là chi phí sản xuất, ở góc phải là năng suất). Yêu cầu sản lượng tối thiểu của Tiêu và Điều lần lượt là 6 tấn và 5 tấn. Lập mô hình bài toán xác định diện tích trồng 5. Có hai khu vườn A và B với diện tích lần lượt là 30ha và 40ha. Người ta dự định trồng ba các loại cây trên sao cho chi phí sản xuất đạt thấp nhất. loại cây I, II và III sao cho tỉ lệ sản lượng khi thu hoạch ba loại cây đó là I:II:III = 2:1:4. Biết rằng Giải. Gọi năng suất (tấn/ha) mỗi loại cây trên hai khu vườn được cho trong bảng sau: • x1, x2 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất I. I II III • x3, x4 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất II. A131 B122 • x5, x6 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất III. a) Lập mô hình bài toán xác định diện tích trồng các loại cây trên hai khu vườn trên để sản Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó lượng đạt được cao nhất. b) Mô hình bài toán sẽ thay đổi thế nào nếu có yêu cầu sản lượng cây loại I ít nhất 10 tấn? 1) Chi phí sản xuất là f(x) = 1,4x1 + 2,1x2 + 1,3x3 + 2,4x4 + 1,6x5 + 1,8x6. Giải. Gọi 2) Diện tích trồng trên khu đất I là x1 + x2 (ha). Ta phải có x1 + x2 ≤ 30. • x1, x2, x3 (ha) lần lượt là diện tích trồng cây loại I, II, III trên khu vườn A. 3) Diện tích trồng trên khu đất II là x3 + x4 (ha). • x4, x5, x6 (ha) lần lượt là diện tích trồng cây loại I, II, III trên khu vườn B. Ta phải có x3 + x4 ≤ 40. Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó 4) Diện tích trồng trên khu đất III là x5 + x6 (ha). Ta phải có x5 + x6 ≤ 50. 1) Diện tích trồng cây trên khu vườn A là x1 + x2 + x3 (ha). 5) Sản lượng Tiêu thu được là 8x1 + 7x3 + 10x5 (tạ). Ta phải có x1 + x2 + x3 ≤ 30. Ta phải có 8x1 + 7x3 + 10x5 ≥ 60 (6tấn = 60tạ). 2) Diện tích trồng cây trên khu vườn B là x4 + x5 + x6 (ha). 6) Sản lượng Điều thu được là 7x2 + 11x4 + 6x6 (tạ). Ta phải có x4 + x5 + x6 ≤ 40. Ta phải có 7x2 + 11x4 + 6x6 ≥ 50 (5tấn = 50tạ). 3) Sản lượng cây loại I thu được là x1 + x4 (tấn). Ta có mô hình bài toán: 4) Sản lượng cây loại II thu được là 3x2 + 2x5 (tấn). (1) f(x) = 1,4x1 + 2,1x2 + 1,3x3 + 2,4x4 + 1,6x5 + 1,8x6 max 5) Sản lượng cây loại III thu được là x3 + 2x6 (tấn). ⎧ x1 + x 2 ≤ 30 Theo yêu cầu, tỉ lệ sản lượng ba loại cây là I:II:III = 2:1:4 nên ta phải có ⎪ x + x ≤ 40 ⎧ x1 − 6x2 + x 4 − 4x5 = 0 x1 + x4 3x 2 + 2x5 x3 + 2x 6 ⎪3 = = ⇔⎨ 4 ⎪ ⎩2x1 − x3 + 2x4 − 2x 6 = 0 2 1 4 (2) ⎨ x5 + x 6 ≤ 50 và sản lượng đạt max khi và chỉ khi sản lượng cây loại I đạt max. ⎪8x + 7x + 10x ≥ 60 ⎪1 3 5 Ta có mô hình bài toán: ⎪7x 2 + 11x 4 + 6x 6 ≥ 50 (1) f(x) = x1 + x4 max ⎩ ⎧ x1 + x 2 + x 3 ≤ 30 (3) xj ≥ 0 (j = 1, 6) ⎪ x + x + x ≤ 40 ⎪4 5 6 (2) ⎨ x1 − 6x 2 + x 4 − 4x5 = 0 7. Công ty Y dự định trồng hai loại cây Tiêu và Điều trên ba khu đất I, II, III có diện tích lần ⎪ lượt là 50, 60, 70 (ha). Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ha) được cho trong bảng ⎪2x1 − x 3 + 2x 4 − 2x 6 = 0 ⎩ sau: (3) xj ≥ 0 (j = 1, 6) Khu đất Tiêu Điều I 1,2 2,2 9 8 6. Công ty X dự định trồng hai loại cây Tiêu và Điều trên ba khu đất I, II, III có diện tích lần II 1,4 2,3 lượt là 30, 40, 50 (ha). Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ha) được cho trong bảng 7 11 sau: III 1,8 2 10 6 Khu đất Tiêu Điều (Trong mỗi ô, số liệu ở góc trái là chi phí sản xuất, ở góc phải là năng suất). Tiền vốn huy động I 1,4 2,1 8 7 được cho sản xuất là 180 (triệu đồng). Tiền lãi mỗi tạ Tiêu, Điều lần lượt là 2 và 2,5 (triệu đồng). II 1,3 2,4 Lập mô hình bài toán xác định diện tích trồng các loại cây trên sao cho tiền lãi đạt cao nhất. 7 11 III 1,6 1,8 10 6 5 6 Printed with FinePrint trial version - purchase at www.fineprint.com
  4. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội b) f (x) = 2x1 + 3x2 − 5x 3 → max Giải. Gọi • x1, x2 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất I. ⎧ ⎪4x1 + x 2 − 2x 3 ≤ −12; • x3, x4 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất II. ⎪ 1 ⎪ ⎨−2x1 + x 2 + x3 ≤ 8; • x5, x6 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất III. 2 ⎪ Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó 3 ⎪ ⎪−2x1 + 2 x2 + x3 = 20. ⎩ 1) Chi phí sản xuất là 1,2x1 + 2,2x2 + 1,4x3 + 2,3x4 + 1,8x5 + 2x6. Ta phải có 1,2x1 + 2,2x2 + 1,4x3 + 2,3x4 + 1,8x5 + 2x6 ≤ 180. xj ≥ 0 (j = 1, 3) 2) Diện tích trồng trên khu đất I là x1 + x2 (ha). ĐS: VN vì PATU của bài toán mở rộng là: (0,2,7,0,0,10) Ta phải có x1 + x2 ≤ 50. 3) Diện tích trồng trên khu đất II là x3 + x4 (ha). c) f (x) = − x1 − 2x 2 − 3x 3 + x 4 → min Ta phải có x3 + x4 ≤ 60. ⎧ x1 + 2x 2 + 3x3 = 22; 4) Diện tích trồng trên khu đất III là x5 + x6 (ha). ⎪ ⎨2x1 + x 2 + 5x 3 = 25; Ta phải có x5 + x6 ≤ 70. 5) Sản lượng Tiêu thu được là 9x1 + 7x3 + 10x5 (tạ). ⎪ x + 2x + x + x = 20. ⎩1 2 3 4 Tiền lãi thu được từ Tiêu là 2(9x1 + 7x3 + 10x5) (triệu đồng). xj ≥ 0 (j = 1, 4) 6) Sản lượng Điều thu được là 8x2 + 11x4 + 6x6 (tạ). Tiền lãi thu được từ Điều là 2,5(8x2 + 11x4 + 6x6) (triệu đồng). ĐS: x0 = (7,6,1,0); f(x0) = −22. 7) Tổng tiền lãi thu được là 2(9x1 + 7x3 + 10x5) + 2,5(8x2 + 11x4 + 6x6) (triệu đồng). Ta có mô hình bài toán: d) f (x) = −3x1 + x 2 + 3x 3 − x 4 → min (1) f(x) = 18x1 + 20x2 + 14x3 + 27,5x4 + 20x5 + 15x6 max ⎧1, 2x1 + 2, 2x 2 + 1, 4x 3 + 2, 3x 4 + 1, 8x5 + 2x 6 ≤ 180 ⎧ x1 + 2x 2 − x 3 + x 4 = 2; ⎪ x + x ≤ 50 ⎪ ⎨2x1 − 6x2 + 3x3 + 3x4 = 9; ⎪1 2 (2) ⎨ x 3 + x 4 ≤ 60 ⎪ x − x + x − x = 6. ⎪ ⎩1 2 3 4 ⎪ x 5 + x 6 ≤ 70 ⎩ xj ≥ 0 (j = 1, 4) (3) xj ≥ 0 (j = 1, 6) ĐS: x = (3,2,5,0); f(x0) = 8 0 8. Giải các bài toán QHTT sau bằng phương pháp đơn hình: e) f (x) = 2x1 − 2x2 + 3x 3 → min ⎧2x1 + 2x 2 − x 3 ≤ 1; a) f (x) = x1 − 4x 2 − 3x3 → min ⎪ ⎨ ⎪ x1 − x2 − 3x3 ≥ 1. ⎧2x1 + x 2 − 2x3 ≤ 16; ⎩ ⎪ xj ≥ 0 (j = 1, 3) ⎨ −4x1 + 2x3 ≤ 8; ⎪ x + 2x − x ≤ 12. ĐS: VN vì PATU của bài toán mở rộng là: (1/2,0,0,0,0,1/2) ⎩1 2 3 xj ≥ 0 (j = 1, 3) f) f (x) = x1 + 2x 2 − x 3 → max ĐS: Vô nghiệm ⎧− x1 + 4x 2 − 2x3 ≤ 6; ⎪ ⎨ x1 + x2 + 2x3 ≥ 6; ⎪2x − x + 2x = 4. ⎩1 2 3 xj ≥ 0 (j = 1, 3) ĐS: x = (14/5, 12/5, 2/5); f(x0) = 36/5 0 7 8 Printed with FinePrint trial version - purchase at www.fineprint.com
  5. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội A chứa vectơ cột đơn vị e1 (cột 4), không chứa các vectơ cột đơn vị e2, e3 nên bài toán chưa có g) f (x) = x1 + 2x 2 − x 3 → max dạng chuẩn. Ta đưa vào các ẩn giả xj ≥ 0 (j = 6, 7) và lần lượt cộng x6, x7 vào vế trái của các phương trình ràng buộc thứ 2, thứ 3 để xây dựng bài toán mở rộng dạng chuẩn: ⎧4x1 − 4x2 + 2x 3 ≥ −6; (1 '') g(x) = − x1 − 2x 2 + x 3 + Mx 6 + Mx7 → min ⎪ ⎨ x1 + x2 + 2x3 ≥ 6; ⎧−4x1 + 4x 2 − 2x 3 + x4 = 6; ⎪ ⎩2x1 − x 2 + 2x3 = 4. ⎪ (2 '') ⎨ x1 + x 2 + 2x 3 − x5 + x6 = 6; ⎪2x − x + 2x + x = 4. xj ≥ 0 (j = 1, 3) ⎩1 2 3 7 Giải. Chuyển về bài toán min bằng cách đặt g(x) = −f(x) = − x1 − 2x2 + x3 (3 '') xj ≥ 0 (j = 1, 7) Ta có bài toán: Khi đó bài toán có (1) g(x) = − x1 − 2x 2 + x 3 → min - Ẩn cơ bản thứ 1 là x4; - Ẩn cơ bản thứ 2 là x6; ⎧4x1 − 4x 2 + 2x 3 ≥ −6; - Ẩn cơ bản thứ 3 là x7. ⎪ (2) ⎨ x1 + x 2 + 2x3 ≥ 6; Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: ⎪ ⎩2x1 − x 2 + 2x 3 = 4. −1 −2 Hệ An Cbản Phương 1 0 0 An3 λi số An BảngI X1 X2 x3 x4 x5 (3) xj ≥ 0 (j = 1, 3) −4 −2 0 x4 6 4 1 0 Biến đổi bài toán trên về dạng chính tắc bằng cách đưa và ẩn phụ x4 ≥ 0, x5 ≥ 0: λ2 = 6/2 =3 −1 M x6 6 1 1 2 0 λ3 = 4/2 =2* −1 M x7 4 2 0 0 2 g(x) = − x1 − 2x 2 + x 3 → min g(x) −1 0 0 1 2 0 ⎧4x1 − 4x 2 + 2x 3 − x 4 = − 6; −M 10M 3M 0 4M* 0 ⎪ ⎨ x1 + x 2 + 2x 3 − x5 = 6; λ1 = 10/3 −2 0 x4 10 3 0 1 0 BảngII ⎪2x − x + 2x = 4. λ2 = 2/2 = 1* −1 −1 M x6 2 0 0 2 ⎩1 2 3 −1/2 1 x3 2 1 1 0 0 xj ≥ 0 (j = 1, 5) g(x) 0 2 2 3/2 0 0 −M −M 2M 2M* 0 0 Vế phải của phương trình ràng buộc thứ 1 âm nên ta đổi dấu hai vế phương trình này và được bài −1/2 0 x4 7 0 0 1 3/2 toán sau: BảngIII (1 ') g(x) = − x1 − 2x 2 + x 3 → min −2 −1/2 −1/2 x2 1 1 0 0 −1/4 1 x3 5/2 0 1 0 3/ 4 ⎧−4x1 + 4x 2 − 2x 3 + x4 = 6; g(x) ⎪ 3/4 ½ 11/4* 0 0 0 (2 ') ⎨ x1 + x 2 + 2x 3 − x5 = 6; ⎪2x − x + 2x = 4. 0 x4 26/3 0 0 2/3 1 4/3 ⎩1 2 3 −2 −2/3 x2 8/3 0 1 2/3 0 (3 ') xj ≥ 0 (j = 1, 5) BảngIV −1 −1/3 x1 10/3 1 0 4/3 0 g(x) Ma trận hệ số ràng buộc là: −26/3 −11/3 5/3* 0 0 0 ⎛ −4 4 −2 1 0 ⎞ 0 0 0 x5 13/2 0 0 1/2 3/4 1 A = ⎜ 1 1 2 0 −1 ⎟ 1 0 −2 x2 7 0 1 1 1/2 0 ⎜ ⎟ ⎜ 2 −1 2 0 0 ⎟ 0 1 −1 x1 11/2 1 0 3/2 1/4 0 BảngV ⎝ ⎠ g(x) −39/2 −9/2 −5/4 0 0 0 9 10 Printed with FinePrint trial version - purchase at www.fineprint.com
  6. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội (1 ') f (x) = 5x1 + 10x2 + 7x3 − Mx6 − Mx7 → max Trong Bảng V ta thấy Δj ≤ 0 với mọi j = 1, 2,..., 5, nên bài toán mở rộng min có một phương án tối ⎧ x1 + 2x 2 + 2x 3 + x4 = 30; ưu là phương án cơ bản ban đầu x định bởi: 0 ⎪ ⎧ x5 = 13 / 2; (2 ') ⎨ x1 + 2x 2 + x 3 + x 6 = 25; ⎪x ⎪ ⎩2x1 + x 2 + x 3 − x5 + x7 = 40. = 7; ⎪2 ⎨ ⎪ x1 = 11 / 2; (3 ') xj ≥ 0 (j = 1, 7) ⎪x3 = x 4 = x 6 = x7 = 0. ⎩ Khi đó bài toán có g(x ) = −39 / 2. 0 - Ẩn cơ bản thứ 1 là x4; vớ i - Ẩn cơ bản thứ 2 là x6; Bài toán mở rộng g (x) → min có phương án tối ưu là x = (11/2, 7, 0, 0, 13/2, 0, 0), trong đó 0 - Ẩn cơ bản thứ 3 là x7. các ẩn giả x6, x7 đều bằng 0 nên bài toán g (x) → min có phương án tối ưu là x0 = (11/2, 7, 0) với g(x0) = −39/2 (ta bỏ đi các ẩn phụ x4 = 0, x5 = 13/2). Ta giải bài toán bằng phương pháp đơn hình mở rộng. Kết luận: Bài toán max đã cho có phương án tối ưu là x0 = (11/2, 7, 0) với f(x0) = − g(x0) = 39/2. Lập bảng đơn hình: Hệ An Phương 5 10 7 0 0 λi số cơ án x1 X2 x3 x4 x5 h) f (x) = 5x1 + 10x 2 + 7x3 → max bả n ⎧ x1 + 2x 2 + 2x3 ≤ 30; λ1 = 30/2 0 30 1 2 2 1 0 x4 ⎪ −M λ2= 25/2* 2 25 1 1 0 0 BảngI x6 ⎨ x1 + 2x2 + x3 = 25; −M −1 λ3 = 40/1 40 2 1 1 0 x7 ⎪2x + x + x ≥ 40. ⎩1 2 3 f(x) −5 −10 −7 0 0 0 xj ≥ 0 (j = 1, 3) −65M −3M −3M* −2M M 0 0 5 0 0 1 1 0 BảngII x4 Giải. Biến đổi bài toán trên về dạng chính tắc bằng cách đưa và ẩn phụ x4 ≥ 0, x5 ≥ 0: λ2= (25/2)/(1/2) =25 10 25/2 1/2 1 1/2 0 0 x2 (1) f (x) = 5x1 + 10x 2 + 7x 3 → max −M −1 λ3= (55/2)/(3/2) =55/3* 55/2 0 1/2 0 x7 3/ 2 f(x) −2 ⎧ x1 + 2x 2 + 2x3 + x4 = 30; 0 125 0 0 0 ⎪ −55M/2 −3M/2* −M/2 M 0 0 (2) ⎨ x1 + 2x 2 + x3 = 25; λ1 = 5/1=5* 0 5 0 0 1 0 x4 1 ⎪ ⎩2x1 + x 2 + x3 − x5 = 40. BảngIII λ2= (10/3)/(1/3)=10 10 10/3 0 1 1/3 0 1/3 x2 −2/3 λ3 = (55/3)/(1/3)=55 (3) xj ≥ 0 (j = 1, 5) 5 55/3 1 0 1/3 0 x1 f(x) −2* 0 125 0 0 0 Các vế phải của phương trình ràng buộc trong (2) đều không âm. 7 5 0 0 1 1 0 x3 Ma trận hệ số ràng buộc là: −1/3 10 5/3 0 1 0 1/3 x2 BảngIV ⎛ 1 2 2 1 0⎞ 0 0 −1/3 −2/3 5 50/3 1 0 0 x1 A = ⎜ 1 2 1 0 0⎟ 1 0 f(x) 0 135 0 0 0 2 ⎜ ⎟ ⎜ 2 1 1 0 −1 ⎟ 0 1 ⎝ ⎠ Trong Bảng IV ta thấy Δj ≥ 0 với mọi j = 1, 2,..., 5, nên bài toán mở rộng max có một phương án A chứa vectơ cột đơn vị e1 (cột 4), không chứa các vectơ cột đơn vị e2, e3 nên bài toán chưa có tối ưu là phương án cơ bản ban đầu x định bởi: 0 dạng chuẩn. Ta đưa vào các ẩn giả xj ≥ 0 (j = 6, 7) và lần lượt cộng x6, x7 vào vế trái của các phương trình ràng buộc thứ 2, thứ 3 để xây dựng bài toán mở rộng dạng chuẩn: 11 12 Printed with FinePrint trial version - purchase at www.fineprint.com
  7. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội ⎧x3 = 5; 2) Lượng nguyên liệu N1 cần sử dụng là: 0,5x1 + 0,2x2 + 0,3x3+ 0,6x4 (kg). Ta phải có 0,5x1 + 0,2x2 + 0,3x3+ 0,6x4 ≤ 600. ⎪x = 5 / 3; ⎪2 3) Lượng nguyên liệu N2 cần sử dụng là: 0,1x1 + 0,4x2 + 0,2x3+ 0,5x4 (kg). ⎨ ⎪ x1 = 50 / 3; Ta phải có 0,1x1 + 0,4x2 + 0,2x3+ 0,5x4 ≤ 800. Ta có mô hình bài toán: ⎪x4 = x 5 = x 6 = x7 = 0. ⎩ (1) f(x) = 0,8x1 + 0,3x2 + 0,38x3+ 0,4x4 max 0,5x1 + 0,2x 2 + 0,3x 3 + 0,6x 4 ≤ 600 ⎧ f (x ) = 135. 0 (2) vớ i ⎨ ⎩0,1x1 + 0,4x 2 + 0,2x 3 + 0,5x 4 ≤ 800 Bài toán mở rộng f (x) → max có phương án tối ưu là x = (50/3, 5/3, 5, 0, 0, 0, 0), trong đó 0 (3) xj ≥ 0 ( j = 1, 4) các ẩn giả x6, x7 đều bằng 0 nên bài toán đã cho có phương án tối ưu là x0 = (50/3, 5/3, 5) với f(x0) = 135 (ta bỏ đi các ẩn phụ x4 = 0, x5 = 0). Biến đổi bài toán trên về dạng chính tắc bằng cách đưa vào 2 ẩn phụ x5 ≥ 0, x6 ≥ 0: (1 ') f (x) = 0, 8x1 + 0, 3x 2 + 0, 38x 3 + 0, 4x 4 → max i) f (x) = −3x1 + x 2 + 3x 3 − x 4 → min ⎧0,5x1 + 0,2x 2 + 0,3x 3 + 0,6x4 + x5 = 600; (2 ') ⎨ ⎧ x1 + 2x2 − x3 + x4 = 2; ⎩0,1x1 + 0,4x 2 + 0,2x 3 + 0,5x4 + x6 = 800. ⎪ ⎨2x1 − 6x 2 + 3x 3 + 3x4 = 9; (3 ') xj ≥ 0 (j = 1, 6) ⎪ x − x + x − x = 6. ⎩1 Các vế phải của phương trình ràng buộc trong (2’) đều không âm. Ma trận hệ số ràng buộc là: 2 3 4 ⎛ 0, 5 0, 2 0, 3 0, 6 1 0 ⎞ xj ≥ 0 (j = 1, 4) A=⎜ ⎟ ⎝ 0,1 0, 4 0, 2 0, 5 0 1 ⎠ ĐS: x0 = (3,2,5,0); f(x0) = 8 A chứa đủ 2 vectơ cột đơn vị e1 (cột 5), e2 (cột 6) nên bài toán đã có dạng chuẩn, trong đó: - Ẩn cơ bản thứ 1 là x5; j) f (x) = 3x1 − x 2 + 2x 3 + x 4 → max - Ẩn cơ bản thứ 2 là x6. ⎧2x1 − x 2 + 4x 3 + x4 = 10; Ta giải bài toán bằng phương pháp đơn hình. ⎪ ⎨ −3x1 + 2x 2 + x 3 − 2x 4 = 8; Hệ An Phương 0,8 0,3 0,38 0,4 0 0 ⎪4x − x − 2x = 4. λi số cơ bản án x1 x2 x3 x4 x5 x6 ⎩1 2 3 λ1 = 600/0,5* 0 600 0,2 0,3 0,6 1 0 x5 0, 5 xj ≥ 0 (j = 1, 4) λ2 = 800/0,1 0 800 0,1 0,4 0,2 0,5 0 1 x6 Bảng I ĐS: x0 = (28,108,0,62,); f(x0) = 38. − 0,8* − 0,3 − 0,38 − 0,4 f(x) 0 0 0 0,8 1200 1 0,4 0,6 1,2 2 0 x1 9. Một xí nghiệp sản xuất 4 mặt hàng: H1, H2, H3, H4. Nguyên liệu cần dùng là N1, N2, mà lượng −0,2 0 680 0 0,36 0,14 0,38 1 x6 Bảng II tối đa xí nghiệp có thể huy động được lần lượt là 600kg và 800kg. Định mức tiêu hao mỗi loại f(x) 960 0 0,02 0,1 0,56 1,6 0 nguyên liệu đối với mỗi mặt hàng cũng như tiền lãi cho 1 đơn vị hàng hóa mỗi loại được cho Trong Bảng II ta thấy Δj ≥ 0 với mọi j = 1, 2,.., 6, nên bài tóan max đang xét có một phương án tối trong bảng sau: ưu là phương án cơ bản ban đầu x1 định bởi: Suất tiêu hao(kg) Hàng H1 H2 H3 H4 ⎧ x1 = 1200; Nguyên liệu ⎪ ⎨ x 6 = 680; N1: 600kg 0,5 0,2 0,3 0,6 ⎪ x = x = x = x = 0. N2: 800kg 0,1 0,4 0,2 0,5 ⎩2 3 4 5 Tiền lãi (ngàn) 0,8 0,3 0,38 0,4 với f(x1) = 960. Bỏ đi các ẩn phụ, ta được phương án tối ưu của bài toán max ban đầu là x0 = (x1, Hãy tìm phương án sản xuất mỗi mặt hàng bao nhiêu đơn vị để tổng tiền lãi thu được cao nhất. x2, x3, x4) = (1200, 0, 0, 0) với f(x0) = 960. Giải. Gọi x1, x2, x3, x4 lần lượt là số đơn vị mặt hàng H1, H2, H3, H4 cần sản xuất. Điều kiện: xj ≥ 0 (j = 1, ..., 4). Khi đó Kết luận: Để tiền lãi đạt cao nhất cần sản xuất 1200 đơn vị mặt hàng H1, không sản xuất các mặt hàng khác. Khi đó tổng tiền lãi thu được là 960 ngàn. 1) Tiền lãi thu được là: f(x) = 0,8x1 + 0,3x2 + 0,38x3+ 0,4x4 (ngàn). 13 14 Printed with FinePrint trial version - purchase at www.fineprint.com
  8. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: 10. Giải bài toán tương tự như trong bài 9 với một số bổ sung sau: Hệ An Phương 0,8 0,3 0,5 0,4 0 0 0 - Tổng số sản phẩm mặt hàng H1 và H2 không ít hơn 1000. λi Số cơ bản án - Tiền lãi cho 1 đơn vị mặt hàng H3 không phải là 0,38 mà là 0,5. x1 x2 x3 x4 x5 x6 x7 Giải. Tương tự như bài 9, trong đó yêu cầu tổng số sản phẩm mặt hàng H1 và H2 không ít hơn λ1 = 600/0,5 0 600 0,5 0,2 0,3 0,6 1 0 0 x5 1000 được thể hiện bởi điều kiện: x1 + x2 ≥ 1000. λ2= 800/0,1 0 800 0,1 0,4 0,2 0,5 0 1 0 Bảng I x6 Ta có bài toán: −M λ3 = 1000/1* 1000 1 0 0 0 0 1 x8 1 (1) f(x) = 0,8x1 + 0,3x2 + 0,5x3+ 0,4x4 max f(x) −0,8 − 0,3 − 0,5 − 0,4 0 0 0 0 ⎧0,5x1 + 0,2x 2 + 0,3x 3 + 0,6x 4 ≤ 600 −1000M −M* −M 0 0 0 0 M ⎪ (2) ⎨0,1x1 + 0,4x 2 + 0,2x 3 + 0,5x 4 ≤ 800 −0,3 λ1 = 100/0,5* 0 100 0 0,33 0,6 1 0 0, 5 x5 ⎪ x + x ≥ 1000 ⎩1 λ2= 700/0,1 0 700 0 0,3 0,2 0,5 0 1 0,1 Bảng II x6 2 −1 0,8 1000 1 1 0 0 0 0 x1 (3) xj ≥ 0 ( j = 1, 4) f(x) − 0,5 − 0,4 − 0,8* 0 800 0 0,5 0 Biến đổi bài toán trên về dạng chính tắc bằng cách đưa vào 3 ẩn phụ x5 ≥ 0, x6 ≥ 0, x7 ≥ 0: −0,6 λ1 = 200/0,6 0 200 0 1,2 2 0 1 0, 6 x7 −0,2 λ2= 680/0,14 0 680 0 0,36 0,14 0,38 1 0 Bảng III x6 (1 ') f (x) = 0, 8x1 + 0, 3x 2 + 0, 5x 3 + 0, 4x 4 → max λ3= 1200/0,6 0,8 1200 1 0,4 0,6 1,2 2 0 0 x1 ⎧0,5x1 + 0,2x2 + 0,3x3 + 0,6x4 + x5 = 600; f(x) − 0,02* 960 0 0,02 0,56 1,6 0 0 ⎪ (2 ') ⎨0,1x1 + 0,4x 2 + 0,2x3 + 0,5x4 + x6 = 800; −1 0,5 1000/3 0 1 2 10/3 0 10/6 x3 ⎪ x + x − x = 1000. −2/3 −7/30 0 1900/3 0 0,5 0 0,1 1 Bảng IV x6 ⎩1 2 7 −1 0,8 1000 1 1 0 0 0 0 X1 (3 ') xj ≥ 0 (j = 1, 7) f(x) 2900/3 0 0 0 0,6 5/3 0 1/30 Trong Bảng IV ta thấy Δj ≥ 0 với mọi j = 1, 2,..., 7, nên bài toán mở rộng max có một phương án Các vế phải của phương trình ràng buộc trong (2’) đều không âm. tối ưu là phương án cơ bản ban đầu x định bởi: 1 Ma trận hệ số ràng buộc là: ⎛ 0, 5 0, 2 0, 3 0, 6 1 0 0 ⎞ 0 ⎧x3 = 1000 / 3; A = ⎜ 0,1 0, 4 0, 2 0, 5 0 1 0 ⎟ 0 ⎜ ⎟ ⎪x = 1900 / 3; ⎜1 0 0 0 −1 ⎟ 1 ⎪6 1 0 ⎝ ⎠ ⎨ ⎪ x1 = 1000; A chứa 2 vectơ cột đơn vị e1 (cột 5), e2 (cột 6), còn thiếu vectơ cột đơn vị e3 nên bài toán chưa có dạng chuẩn. Ta đưa vào ẩn giả x8 ≥ 0 và cộng x8 vào vế trái của các phương trình ràng buộc thứ 3, ⎪x2 = x 4 = x5 = x7 = x 8 = 0. ⎩ để xây dựng bài toán mở rộng dạng chuẩn: f (x1 ) = 2900 / 3. vớ i (1 '') f (x) = 0, 8x1 + 0, 3x 2 + 0, 5x 3 + 0, 4x4 − Mx8 → max Bài toán mở rộng f (x) → max có phương án tối ưu là x = (1000, 0, 1000/3, 0, 0, 1900/3, 0, 0) 1 ⎧0,5x1 +0,2x 2 + 0,3x3 + 0,6x4 + x5 = 600; trong đó ẩn giả x8 = 0 nên bài toán max ban đầu có phương án tối ưu là x1 = (1000, 0, 1000/3, 0) ⎪ (2 '') ⎨0,1x1 +0,4x 2 + 0,2x 3 + 0,5x 4 + x6 = 800; với f(x1) = 2900/3 (ta bỏ đi các ẩn phụ x5, x6 và x7). ⎪ x +x - x + x =1000. Kết luận: Để tiền lãi đạt cao nhất cần sản xuất 1000 đơn vị mặt hàng H1, 1000/3 đơn vị mặt hàng ⎩1 2 7 8 H3, không sản xuất các mặt hàng khác. Khi đó tổng tiền lãi thu được là 2900/3 ngàn. (3 '') xj ≥ 0 (j = 1, 8) 11. Xí nghiệp dùng các tấm kim loại kích thước 60cm×100cm để sản xuất 3 loại bán thành phẩm Khi đó bài toán có là các tấm kim loại T1, T2, T3. Có 4 phương thức cắt P1, P2, P3, P4. Số lượng bán thành phẩm cần - Ẩn cơ bản thứ 1 là x5; trong sản xuất; số lượng bán thành phẩm có được cũng như lượng thừa sau khi cắt một tấm theo - Ẩn cơ bản thứ 2 là x6; mỗi cách được cho trong bảng sau: - Ẩn cơ bản thứ 3 là x8. 15 16 Printed with FinePrint trial version - purchase at www.fineprint.com
  9. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội 420 6 6 7 10 -1 -1 -1 Bán thành phẩm Phương thức cắt Luợng bán thành phẩm cần có P1 P2 P3 P4 Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào T1 3 4 5 10 240 Cột có giá lớn nhỏ nhất ứng với x4 vậy biến đưa vào là : x4 T2 2 0 1 0 100 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1 T3 1 2 1 0 80 Lượng thừa (cm2) 200 400 200 0 Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 0 24 3/10 2/5 1/2 1 -1/10 0 0 80 X4 M 100 0 1 0 0 -1 0 50 X9 2 Hãy tìm phương án cắt sao cho lượng bán thành phẩm cần trong sản xuất đuợc đảm bảo mà tổng M 80 1 2 1 0 0 0 -1 80 X10 số lượng thừa là ít nhất. F(x) 0 -400 -200 0 0 0 0 -200 Giải. Gọi x1, x2, x3, x4 lần lượt là số tấm kim loại được cắt theo phương thức P1, P2, P3, P4. Điều 180 3 2 2 0 0 -1 -1 kiện: xj ≥ 0 (j= 1, ..., 4). Khi đó Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào 1) Tổng lượng thừa: f(x) = 200x1 + 400x2 + 200x3 (cm2). Cột có giá lớn nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2 2) Lượng bán thành phẩm T1 thu được: 3x1 + 4x2 + 5x3+ 10x4. Ta phải có 3x1 + 4x2 + 5x3+ 10x4 ≥ 240. Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 3) Lượng bán thành phẩm T2 thu được: 2x1 + x3. 0 9 0 2/5 7/20 1 -1/10 3/20 0 45/2 X4 200 50 1 0 1/2 0 0 -1/2 0 - X1 Ta phải có 2x1 + x3 ≥ 100. M 30 0 1/2 0 0 1/2 -1 15 X10 2 4) Lượng bán thành phẩm T3 thu được: x1 + 2x2 + x3. F(x) 10000 0 -100 0 0 -100 0 -400 Ta phải có x1 + 2x2 + x3 ≥ 80. 30 0 2 1/2 0 0 1/2 -1 Ta có bài toán: Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào (1) f(x) = 200x1 + 400x2 + 200x3 min Cột có giá lớn nhỏ nhất ứng với x2 vậy biến đưa vào là : x2 ⎧3x1 + 4x 2 + 5x 3 + 10x 4 ≥ 240 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 3 ⎪ (2) ⎨2x1 + x 3 ≥ 100 Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 0 3 0 0 1/4 1 -1/10 1/20 1/5 - ⎪ x + 2x + x ≥ 80 X4 ⎩1 200 50 1 0 1/2 0 0 -1/2 0 - X1 2 3 400 15 0 1 1/4 0 0 1/4 -1/2 - X2 (3) x j ≥ 0 (j = 1, 4) F(x) 16000 0 0 0 0 0 0 -200 0 0 0 0 0 0 0 0 Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (50, 15, 0, 3); f(x0) = 16000. Do đó để tổng số lượng thừa là ít nhất, số tấm kim loại được cắt theo phương thức P1, P2, P3, P4 lần lượt là 50, 15, 0, Phương án tối ưu của bài toán mở rộng là : (50,15,0,3,0,0,0,0,0,0) 2 Giá trị hàm mục tiêu đạt được là : F(x) = 16000 3. Khi đó tổng số lượng thừa là 1600cm . Sau đây là lời giải tham khảo từ chương trình máy tính: 12. Có ba loại thức ăn I, II, III dùng trong chăn nuôi. Mức yêu cầu cần phải có đủ các chất cho gia Bài toán ở dạng chuẩn: súc trong một ngày đêm và giá mỗi đơn vị thức ăn mỗi loại được cho trong bảng sau: Chất Lượng yêu cầu Lượng chất (đv: g) có trong 1đv thức ăn mỗi loại F(x) = 200x1 + 400x2 + 200x3 + Mx8 + Mx9 + Mx10 => MIN trong 1 ngày đêm I II III Albumin Ít nhất 200g 0,3 0,8 2 Các ràng buộc: Chất béo Không quá 100g 3 0 0,4 3x1 + 4x2 + 5x3 + 10x4 - x5 = 240 Chất đạm Đúng 150g 1 10 0 2x1 + x3 - x6 = 100 Giá 1đv thức ăn (ngàn đồng) 0,8 1,5 3 x1 + 2x2 + x3 - x7 = 80 Hãy xác định lượng thức ăn cần dùng mỗi loại sao cho tổng chi phí thấp nhất mà vẫn đảm bảo được mức yêu cầu cho gia súc về các chất trong 1 ngày đêm. Trong đó: Giải. Gọi x1, x2, x3 lần lượt là số đơn vị thực phẩm loại I, II, III cần mua. Điều kiện: xj ≥ 0 (j = 1, x5, x6, x7 là biến phụ 2, 3). Khi đó x8, x9, x10 là biến giả x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0 1) Chi phí mua thực phẩm: f(x) = 0,8x1 + 1,5x2 + 3x3 (ngàn đồng). 2) Lượng Albumin có được: 0,3x1 + 0,8x2 + 2x3 (g). Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Ta phải có 0,3x1 + 0,8x2 + 2x3 ≥ 200. M 240 3 4 5 -1 0 0 24 X8 10 M 100 2 0 1 0 0 -1 0 - X9 3) Lượng chất béo có được: 3x1 + 0,4x3 (g). M 80 1 2 1 0 0 0 -1 - X10 Ta phải có 3x1 + 0,4x3 ≤ 100. F(x) 0 -200 -400 -200 0 0 0 0 17 18 Printed with FinePrint trial version - purchase at www.fineprint.com
  10. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội 3 94 11/100 0 1 -1/2 0 - X3 4) Lượng chất đạm có được: x1 + 10x2 (g). 0 312/5 739/250 0 0 1/5 1 - X5 Ta phải có x1 + 10x2 = 150. 15/10 15 1/10 1 0 0 0 - X2 Ta có bài toán: F(x) 609/2 -8/25 0 0 -3/2 0 (1) f(x) = 0,8x1 + 1,5x2 + 3x3 min 0 0 0 0 0 0 ⎧0,3x1 + 0,8x 2 + 2x 3 ≥ 200 Phương án tối ưu của bài toán mở rộng là : (0,15,94,0,312/5,0,0) ⎪ (2) ⎨3x1 + 0, 4x 3 ≤ 100 Giá trị hàm mục tiêu đạt được là : F(x) = 609/2 ⎪ x + 10x = 150 ⎩1 2 13. Một nông trường sử dụng 3000ha để trồng 3 loại nông sản A, B, C có thông số sau: (3) xj ≥ 0 (j = 1, 3) Nông Chi phí sản xuất cho 1ha Giá trị sản lượng thu được trên 1ha sản (ngàn đồng) Vốn (ngàn đồng) Lao động (ngàn đồng) A 300 500 2.000 Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (0, 15, 94); f(x0) = 609/2. Do đó để tổng chi B 350 400 1.500 phí thấp nhất, số đơn vị thực phẩm loại I, II, III cần mua lần lượt là 0, 15, 94. Khi đó tổng chi phí C 400 450 2.500 là 609/2 (ngàn đồng). Khả năng của nông trường về vốn là 1200 triệu đồng, về lao động là 1600triệu đồng. Ngoài ra, để đảm bảo hợp đồng đã ký kết, cần trồng ít nhất 600ha nông sản A. Hãy xác định diện tích trồng Sau đây là lời giải tham khảo từ chương trình máy tính: mỗi loại nông sản để tổng giá trị sản lượng thu được là cao nhất. Bài toán ở dạng chuẩn: Giải. Gọi x1, x2, x3 (ha) lần lượt là diện tích trồng các loại nông sản A, B, C. Điều kiện: xj ≥ 0 (j = 1, 2, 3). Khi đó F(x) = 8/10x1 + 15/10x2 + 3x3 + Mx6 + Mx7 => MIN 1) Tổng giá trị sản lượng thu được: f(x) = 2x1 + 1,5x2 + 2,5x3 (triệu). Các ràng buộc: 2) Tổng diện tích trồng: x1 + x2 + x3 (ha). Ta phải có x1 + x2 + x3 ≤ 3000. 3/10x1 + 8/10x2 + 2x3 - x4 = 200 3x1 + 4/10x3 + x5 = 100 3) Diện tích trồng nông sản A: x1 (ha). x1 + 10x2 = 150 Ta phải có x1 ≥ 600. 4) Chi phí về vốn: 300x1 + 350x2 + 400x3 (ngàn). Trong đó: Ta phải có 300x1 + 350x2 + 400x3 ≤ 1200000 (1200triệu = 1200000ngàn). x4, x5 là biến phụ 5) Chi phí về lao động: 500x1 + 400x2 + 450x3 (ngàn). x6, x7 là biến giả Ta phải có 500x1 + 400x2 + 450x3 ≤ 1600000 (1600triệu = 1600000ngàn). x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0 Ta có bài toán: Lamda Ci Xi Yi X1 X2 X3 X4 X5 (1) f(x) = 2x1 + 1,5x2 + 2,5x3 max M 200 3/10 8/10 2 -1 0 250 X6 ⎧ x1 + x 2 + x 3 ≤ 3000 ⎧ x1 + x 2 + x 3 ≤ 3000 0 100 3 0 4/10 0 1 - X5 M 150 1 0 0 0 15 X7 10 ⎪ x ≥ 600 ⎪ x ≥ 600 ⎪1 ⎪1 F(x) 0 -4/5 -3 0 0 -3/2 (2) ⇔⎨ ⎨ 350 13/10 54/5 2 -1 0 300x1 + 350x 2 + 400x 3 ≤ 1200000 ⎪3x1 + 3, 5x 2 + 4x 3 ≤ 12000 ⎪ Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào ⎪500x1 + 400x 2 + 450x 3 ≤ 1600000 ⎪5x1 + 4x 2 + 4, 5x 3 ≤ 16000 ⎩ ⎩ Cột có giá lớn nhỏ nhất ứng với x2 vậy biến đưa vào là : x2 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 3 (3) x j ≥ 0 (j = 1, 3) Lamda Ci Xi Yi X1 X2 X3 X4 X5 Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (600,0,2400); f(x0) = 7200. Do đó để tổng M 188 11/50 0 -1 0 94 X6 2 giá trị sản lượng thu được là cao nhất, diện tích trồng các loại nông sản A, B, C lần lượt là 600, 0, 0 100 3 0 2/5 0 1 250 X5 2400 (ha). Khi đó tổng giá trị sản lượng thu được là 7200 (triệu đồng). 15/10 15 1/10 1 0 0 0 - X2 F(x) 45/2 -13/20 0 0 0 -3 188 11/50 0 2 -1 0 Sau đây là lời giải tham khảo từ chương trình máy tính: Bài toán ở dạng chuẩn: Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá lớn nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 F(x) = 2x1 + 3/2x2 + 5/2x3 - Mx8 => MAX Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1 Các ràng buộc: Lamda Ci Xi Yi X1 X2 X3 X4 X5 19 20 Printed with FinePrint trial version - purchase at www.fineprint.com
  11. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Do chiến lược tiếp thị, công ty phải có ít nhất 30 lần quảng cáo trên truyền hình trong 1 tháng. x1 + x2 + x3 + x4 = 3000 Hãy xác định số lần quảng cáo trên mỗi phương tiện sao cho số người dự kiến tiếp nhận quảng x1 - x5 = 600 cáo là cao nhất. 3x1 + 7/2x2 + 4x3 + x6 = 12000 Giải. Gọi x1, x2, x3 lần lượt là số lần quảng cáo trên truyền hình, phát thanh và báo. Điều kiện: xj 5x1 + 4x2 + 9/2x3 + x7 = 16000 ≥ 0 (j = 1, 2, 3). Khi đó Trong đó: 1) Dư kiến tổng số người tiếp nhận quảng cáo: x4, x5, x6, x7 là biến phụ f(x) = 15x1 + 9x2 + 30x3 (ngàn người). x8 là biến giả 2) Số lần quảng cáo tối đa trên truyền hình là 60, tối thiểu là 30 nên x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0 x1 ≤ 60 và x1 ≥ 30. Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 3) Số lần quảng cáo tối đa trên phát thanh là 90 nên x2 ≤ 90. 0 3000 1 1 1 1 0 0 0 3000 X4 4) Số lần quảng cáo tối đa trên báo là 26 nên x3 ≤ 26. -M 600 0 0 0 -1 0 0 600 X8 1 0 12000 3 7/2 4 0 0 1 0 4000 X6 5) Chi phí quảng cáo: 1,5x1 + 0,5x2 + x3 (triệu đồng). 0 16000 5 4 9/2 0 0 0 1 3200 X7 Ta phải có 1,5x1 + 0,5x2 + x3 ≤ 100. F(x) 0 -3/2 -5/2 0 0 0 0 -2 Ta có bài toán: -600 -1 0 0 0 1 0 0 (1) f(x) = 15x1 + 9x2 + 30x3 max Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào ⎧ x1 ≤ 60 Cột có giá trị nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 ⎪ x ≥ 30 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2 ⎪1 ⎪ (2) ⎨ x 2 ≤ 90 Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 0 2400 0 1 1 1 0 0 2400 X4 1 ⎪ x ≤ 26 2 600 1 0 0 0 -1 0 0 - X1 ⎪3 0 10200 0 7/2 4 0 3 1 0 2550 X6 ⎪1,5x1 + 0,5x 2 + x3 ≤ 100 ⎩ 0 13000 0 4 9/2 0 5 0 1 26000/9 X7 F(x) 1200 0 -3/2 0 -2 0 0 -5/2 (3) x j ≥ 0 (j = 1, 3) 0 0 0 0 0 0 0 0 Giải bài toán trên bằng PP đơn hình ta được PATU x0 = (30, 58, 26); f(x0) = 1752. Do đó để số Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào người dự kiến tiếp nhận quảng cáo là cao nhất, số lần quảng cáo trên truyền hình, phát thanh và Cột có giá trị nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1 báo lần lượt là 30, 58, 26. Khi đó số người dự kiến tiếp nhận quảng cáo là 1752000 người. Lamda Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Sau đây là lời giải tham khảo từ chương trình máy tính: 5/2 2400 0 1 1 1 1 0 0 - X3 2 600 1 0 0 0 -1 0 0 - X1 Bài toán ở dạng chuẩn: 0 600 0 -1/2 0 -4 -1 1 0 - X6 0 2200 0 -1/2 0 -9/2 1/2 0 1 - X7 F(x) = 15x1 + 9x2 + 30x3 - Mx9 => MAX F(x) 7200 0 1 0 5/2 1/2 0 0 0 0 0 0 0 0 0 0 Các ràng buộc: Phương án tối ưu của bài toán mở rộng là : (600,0,2400,0,0,600,2200,0) x1 + x4 = 60 Giá trị hàm mục tiêu đạt được là : F(x) = 7200 x1 - x5 = 30 x2 + x6 = 90 x3 + x7 = 26 3/2x1 + 1/2x2 + x3 + x8 = 100 14. Một công ty muốn quảng cáo một loại sản phẩm trong 1 tháng với tổng chi phí 100triệu đồng. Các phương tiện được chọn để quảng cáo là: Truyền hình, Phát thanh và Báo với các số liệu sau: Trong đó: Phương tiện Chi phí mỗi lần quảng cáo Số lần quảng cáo tối đa Dự kiến số người tiếp nhận trong 1 (triệu đồng) trong 1 tháng lần quảng cáo x4, x5, x6, x7, x8 là biến phụ x9 là biến giả Truyền hình 1,5 60 15.000 x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0, x8 >=0 (1phút/lần) Phát thanh 0,5 90 9.000 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 (1 phút/lần) 0 60 1 0 0 1 0 0 0 0 X4 Báo 1 26 30.000 -M 30 0 0 0 -1 0 0 0 X9 1 (1/2trang/lần) 0 90 0 1 0 0 0 1 0 0 X6 0 26 0 0 1 0 0 0 1 0 X7 0 100 3/2 1/2 1 0 0 0 0 1 X8 21 22 Printed with FinePrint trial version - purchase at www.fineprint.com
  12. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội a) f (x) = 2x1 + 3x 2 − 5x3 → max F(x) 0 -9 -30 0 0 0 0 0 -15 -30 -1 0 0 0 1 0 0 0 ⎧ ⎪4x1 + x 2 − 2x3 ≤ −12 Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá trị nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 ⎪ 1 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2 ⎪ ⎨ −2x1 + x 2 + x 3 ≤ 8 2 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 ⎪ 0 30 0 0 0 1 1 0 0 0 X4 3 ⎪ ⎪ −2x1 + 2 x 2 + x3 = 20 15 30 1 0 0 0 -1 0 0 0 X1 ⎩ 0 90 0 1 0 0 0 1 0 0 X6 0 26 0 0 0 0 0 1 0 X7 1 x1 ≥ 0, x 2 ≤ 0 0 55 0 1/2 1 0 3/2 0 0 1 X8 F(x) 450 0 -9 0 -15 0 0 0 -30 Giải. Bài toán đối ngẫu: 0 0 0 0 0 0 0 0 0 g(y) = −12y1 + 8y 2 + 20y 3 → min Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào ⎧4y1 − 2y 2 − 2y 3 ≥ 2 Cột có giá trị nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 ⎪ Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 4 1 3 ⎪ ⎨ y1 + y 2 + y 3 ≤ 3 2 2 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 ⎪ 0 30 0 0 0 1 1 0 0 0 X4 ⎪−2y1 + y 2 + y 3 = −5 15 30 1 0 0 0 -1 0 0 0 X1 ⎩ 0 90 0 1 0 0 0 1 0 0 X6 y1 ≥ 0, y 2 ≥ 0 30 26 0 0 1 0 0 0 1 0 X3 0 29 0 1/2 0 0 0 -1 1 X8 3/2 Các cặp ràng buộc đối ngẫu như sau: F(x) 1230 0 -9 0 0 0 30 0 -15 0 0 0 0 0 0 0 0 0 4x1 + x2 − 2x3 ≤ −12 y1 ≥ 0 Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào y2 ≥ 0 1 Cột có giá trị nhỏ nhất ứng với x5 vậy biến đưa vào là : x5 −2x1 + x 2 + x 3 ≤ 8 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 5 2 3 y3 tuỳ ý Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 −2x1 + x 2 + x3 = 20 0 32/3 0 -1/3 0 1 0 0 2/3 -2/3 X4 2 15 148/3 1 1/3 0 0 0 0 -2/3 2/3 X1 x1 ≥ 0 4y1 − 2y 2 − 2y 3 ≥ 2 0 90 0 1 0 0 0 1 0 0 X6 30 26 0 0 1 0 0 0 1 0 X3 x2 ≤ 0 1 3 0 58/3 0 0 0 1 0 -2/3 2/3 X5 1/3 y1 + y 2 + y 3 ≤ 3 F(x) 1520 0 0 0 0 0 20 10 -4 2 2 0 0 0 0 0 0 0 0 0 −2y1 + y 2 + y 3 = −5 x3 tuỳ ý Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào Cột có giá trị nhỏ nhất ứng với x2 vậy biến đưa vào là : x2 b) f (x) = −3x1 + x 2 + 3x 3 − x 4 → min Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 5 ⎧ x1 + 2x2 − x 3 + x 4 = 2 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 0 30 0 0 0 1 1 0 0 0 X4 ⎪ ⎨2x1 − 6x 2 + 3x 3 + 3x 4 ≤ 9 15 30 1 0 0 0 -1 0 0 0 X1 0 32 0 0 0 0 -3 1 2 -2 X6 ⎪x − x + x − x ≥ 6 30 26 0 0 1 0 0 0 1 0 X3 ⎩1 2 3 4 9 58 0 1 0 0 3 0 -2 2 X2 x1 ≥ 0, x 2 ≤ 0, x4 ≤ 0 F(x) 1752 0 0 0 0 12 0 12 18 0 0 0 0 0 0 0 0 0 Giải. Bài toán đối ngẫu: Phương án tối ưu của bài toán mở rộng là : (30,58,26,30,0,32,0,0,0) Giá trị hàm mục tiêu đạt được là : F(x) = 1752 15. Lập các bài toán đối ngẫu của các bài toán QHTT sau và xác định các cặp ràng buộc đối ngẫu: 23 24 Printed with FinePrint trial version - purchase at www.fineprint.com
  13. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội g(y) = 2y1 + 9y 2 + 6y 3 → max d) f (x) = −3x1 + x 2 + 3x 3 − x 4 → min ⎧ y1 + 2y 2 + y 3 ≤ −3 ⎪ ⎧ x1 + 2x 2 − x 3 + x4 ≥ 2 ⎪2y1 − 6y 2 − y 3 ≥ 1 ⎪ ⎨ ⎨2x1 − 6x 2 + 3x 3 + 3x 4 ≤ 9 ⎪ − y1 + 3y 2 + y 3 = 3 ⎪x − x + x − x = 6 ⎪ ⎩ y1 + 3y 2 − y 3 ≥ −1 ⎩1 2 3 4 x1 ≤ 0, x 2 ≥ 0, x 4 ≥ 0 y 2 ≤ 0, y 3 ≥ 0 Giải. Bài toán đối ngẫu: Các cặp ràng buộc đối ngẫu như sau: g(y) = 2y1 + 9y 2 + 6y 3 → max x1 + 2x 2 − x 3 + x4 = 2 y1 tuỳ ý ⎧ y1 + 2y 2 + y 3 ≥ −3 ⎪2y − 6y − y ≤ 1 2x1 − 6x 2 + 3x3 + 3x4 ≤ 9 y2 ≤ 0 ⎪1 2 3 ⎨ x1 − x 2 + x 3 − x4 ≥ 6 y3 ≥ 0 − y1 + 3y 2 + y 3 = 3 ⎪ x1 ≥ 0 y1 + 2y 2 + y 3 ≤ −3 ⎪ y1 + 3y 2 − y 3 ≤ −1 ⎩ x2 ≤ 0 2y1 − 6y 2 − y 3 ≥ 1 y1 ≥ 0, y 2 ≤ 0 − y1 + 3y 2 + y 3 = 3 x3 tuỳ ý Các cặp ràng buộc đối ngẫu như sau: x4 ≤ 0 y1 + 3y 2 − y 3 ≥ −1 x1 + 2x 2 − x 3 + x 4 ≥ 2 y1 ≥ 0 c) f (x) = x1 + 2x2 − x3 → max 2x1 − 6x 2 + 3x3 + 3x4 ≤ 9 y2 ≤ 0 ⎧ − x1 + 4x 2 − 2x3 ≤ 6 x1 − x 2 + x 3 − x4 = 6 y3 tuỳ ý ⎪ ⎨ x1 + x2 + 2x3 ≥ 6 x1 ≤ 0 y1 + 2y 2 + y 3 ≥ −3 ⎪2x − x + 2x = 4 ⎩1 x2 ≥ 0 2y1 − 6y 2 − y 3 ≤ 1 2 3 x 2 ≥ 0, x 3 ≤ 0 − y1 + 3y 2 + y 3 = 3 x3 tuỳ ý Giải. Bài toán đối ngẫu: x4 ≥ 0 y1 + 3y 2 − y 3 ≤ −1 g(y) = 6y1 + 6y 2 + 4y 3 → min ⎧ − y1 + y 2 + 2y 3 = 1 16. Với bài toán QHTT đã cho và phương án tối ưu tương ứng hãy lập bài toán đối ngẫu và tìm ⎪ PATU của bài toán đối ngẫu (không giải trực tiếp bằng phương pháp đơn hình): ⎨4y1 + y 2 − y 3 ≥ 2 a) f (x) = 2x1 + x 2 − x 3 − x 4 → max vôùi phöông aùn toái öu x0 = (3, 3, 1 ,0) ⎪ −2y + 2y + 2y ≤ −1 ⎩ ⎧ x1 − x2 + 2x3 − x4 = 2; 1 2 3 y1 ≥ 0, y 2 ≤ 0 ⎪ ⎨2x1 + x 2 − 3x3 + x4 = 6; Các cặp ràng buộc đối ngẫu như sau: ⎪ x + x + x + x = 7. ⎩1 2 3 4 − x1 + 4x2 − 2x3 ≤ 6 y1 ≥ 0 xj ≥ 0 ( j = 1, 4) x1 + x2 + 2x3 ≥ 6 y2 ≤ 0 Giải. Bài toán đối ngẫu của bài toán trên là: 2x1 − x 2 + 2x3 = 4 y3 tuỳ ý − y1 + y 2 + 2y 3 = 1 x1 tuỳ ý x2 ≥ 0 4y1 + y 2 − y 3 ≥ 2 x3 ≤ 0 −2y1 + 2y 2 + 2y 3 ≤ −1 25 26 Printed with FinePrint trial version - purchase at www.fineprint.com
  14. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội (1 ') g(y) = 2y1 + 6y 2 + 7y 3 → min c) f (x) = 2x1 + 3x 2 + 2x 3 + 3x 4 → min vôùi phöông aùn toái öu x0 = (0, 5, 11, 3) ⎧ y1 + 2y 2 + y 3 ≥ 2; ⎪ − y + y + y ≥ 1; ⎧− x1 + x2 + 2x3 − x4 = 24 ⎪1 2 3 (2 ') ⎪x + x + 2x ≥ 22 ⎨ ⎪2y1 − 3y 2 + y 3 ≥ −1; ⎪2 3 4 ⎨ ⎪ − y1 + y 2 + y 3 ≥ −1. x2 + x 4 ≥ 8 ⎩ ⎪ ⎪x2 + x3 ≤ 20 (3 ') y j (j = 1, 3) tuøy yù. ⎩ x j ≥ 0 (j = 1, 4) Theo giả thiết, bài toán đã cho có PATU là x 0 = (3, 3, 1 ,0) . Bây giờ ta tìm PATU y 0 = (y1 , y 0 , y 0 ) của bài toán đối ngẫu. 0 Giải. Bài toán đối ngẫu của bài toán trên là: 2 3 2 ⎧0 ⎪ y1 = 11 (1 ') g(y) = 24y1 + 22y 2 + 8y 3 + 20y 4 → max ⎧ x1 = 3 > 0; 0 ⎧ y1 + 2y 0 + y 0 = 2 0 ⎪ 2 3 ⎪ ⎧− y1 ≤ 2; Do ⎨ x 0 = 3 > 0; nên ta có ⎪− y 0 + y 0 + y 0 = 1 ⇔ ⎪ y 0 = 7 ⎨1 ⎨2 ⎪ y + y + y + y ≤ 3; 2 2 3 11 ⎪0 ⎪1 ⎩ x 3 = 1 > 0. ⎪0 ⎪ 2 3 4 (2 ') 2y1 − 3y 0 + y 0 = −1 ⎨ 6 ⎩ ⎪0 2y1 + y 2 + y 4 ≤ 2; 2 3 ⎪ y 3 = 11 ⎪ ⎩ ⎪− y1 + 2y 2 + y 3 ≤ 3; ⎩ Vậy PATU của bài toán đối ngẫu là y0 = (2/11, 7/11, 6/11) với g(y0) = 8. (3 ') y 2 ≥ 0, y 3 ≥ 0, y 4 ≤ 0. Theo giả thiết, bài toán đã cho có PATU là x 0 = (0, 5, 11, 3) . 351 b) f (x) = −3x1 − 4x 2 − x 3 − 2x 4 + x 5 → min vôùi phöông aùn toái öu x 0 = ( , , ,0,0) 222 Bây giờ ta tìm PATU y 0 = (y1 , y 0 , y 3 , y 0 ) của bài toán đối ngẫu. 0 0 2 4 ⎧ x1 + 2x 2 − 3x 3 + x 4 − 5x5 = 5 1) Thế phương án x vào bất phương trình ràng buộc thứ 4: x 2 + x3 ≤ 20 ta thấy không xảy ra 0 ⎪ ⎨2x1 + 3x 2 − 5x 3 + 2x 4 − 7x 5 = 8 dấu đẳng thức (5 + 11 < 20) nên ta có y 0 = 0. 4 ⎪3x + x − 2x + 6x + 2x = 6 ⎧0 1 ⎩1 2 3 4 5 ⎪ y1 = 2 ⎧ x0 = 5 > 0; ⎧ y1 + y 2 + y 0 + y 0 = 3 ⎧ y1 + y 2 + y 3 = 3 0 0 0 0 0 xj ≥ 0 (j = 1, 5) 2 3 4 ⎪0 ⎪0 ⎪0 ⎪0 2) Do ⎨ x3 = 11 > 0; nên ta có ⎨2y + y 0 + y 0 = 2 ⇔ ⎨2y1 + y 2 = 2 ⇔ ⎨y2 = 1 0 Giải. Bài toán đối ngẫu của bài toán trên là: 1 2 4 ⎪0 ⎪0 ⎪0 ⎪ ⎩ x4 = 3 > 0. 3 ⎩− y1 + 2y 2 + y 3 = 3 ⎩ − y1 + 2y 2 + y 3 = 3 0 0 0 0 ⎪y0 = (1 ') g(y) = 5y1 + 8y 2 + 6y 3 → max 3 2 ⎩ ⎧ y1 + 2y 2 + 3y 3 ≤ −3; Vậy PATU của bài toán đối ngẫu là y0 = (1/2, 1, 3/2, 0) với g(y0) = 46. ⎪2y + 3y + y ≤ −4; ⎪1 2 3 ⎪ (2 ') ⎨ −3y1 − 5y 2 − 2y 3 ≤ −1; d) f (x) = 3x1 + x2 + 2x 3 − x 4 − 2x 5 → max vôùi phöông aùn toái öu x0 = (0, 15, 6, 2, 0) ⎪ y + 2y + 6y ≤ −2; ⎪1 2 3 ⎧−5x1 + x2 − x3 − 2x4 + 8x5 ≥ 5 ⎪−5y1 − 7y 2 + 2y 3 ≤ 1. ⎩ ⎪ 23 3 ⎪− x1 + 3x2 − x3 − 6x4 + 20x5 ≥ 20 (3 ') y j (j = 1, 3) tuøy yù. ⎪2 2 ⎪ 351 ⎨ 17 3 3 15 Theo giả thiết, bài toán đã cho có PATU là x 0 = ( ,, ,0,0) . ⎪− 4 x1 + x2 − 4 x3 − 2 x4 + 6x5 ≤ 2 222 ⎪ Bây giờ ta tìm PATU y 0 = (y1 , y 0 , y 0 ) của bài toán đối ngẫu. 0 ⎪3 x + 1 x ≤ 3 2 3 ⎪2 1 2 3 ⎧ x1 = 3 / 2 > 0; 0 ⎧ y1 + 2y 2 + 3y 3 = −3 ⎩ ⎧ y1 = −27 0 0 0 0 ⎪0 ⎪0 ⎪0 xj ≥ 0 (j = 1, 5) Do ⎨ x 2 = 5 / 2 > 0; nên ta có ⎨2y1 + 3y 0 + y 0 = −4 ⇔ ⎨ y 2 = 18 2 3 ⎪0 ⎪ ⎪0 ⎩ x 3 = 1 / 2 > 0. ⎩ y 3 = −4 ⎩−3y1 − 5y 2 − 2y 3 = −1 0 0 0 Giải. Bài toán đối ngẫu của bài toán trên là: Vậy PATU của bài toán đối ngẫu là y0 = (−27, 18, −4) với g(y0) = −15. 27 28 Printed with FinePrint trial version - purchase at www.fineprint.com
  15. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội 15 c) f (x) = 2x1 + 5x 2 + 2x3 − 3x4 + 2x5 → max d) f (x) = −4x1 + 4x2 + 2x3 − 3x4 − x5 → max (1 ') g(y) = 5y1 + 20y 2 + y 3 + 3y 4 → min 2 ⎧ x1 − 2x 4 + 3x5 ≥ 12 ⎧ x1 − 2x4 + 3x5 ≥ 6 ⎪ ⎪ 23 17 3 ⎧ ⎨2x1 + 4x 2 + x 3 − x4 + 3x5 = 34 ⎨2x1 + 4x2 + x3 − x4 + 2x5 = 25 ⎪−5y1 − 2 y 2 − 4 y 3 + 2 y 4 ≥ 3; ⎪ x − 2x + x − x ≤ −16 ⎪3x + 2x − x + x ≥ 8 ⎩1 ⎩1 ⎪ 2 4 5 2 4 5 ⎪ y1 + 3y 2 + y 3 ≥ 1; x j ≥ 0 ( j = 1, 5) x j ≥ 0 (j = 1, 5) ⎪ 3 3 1 ⎪ (2 ') ⎨− y1 − y 2 − y 3 + y 4 ≥ 2; Giải. Trước hết, ta dùng phương pháp đơn hình để giải các bài toán đã cho tìm phương án tối ưu 2 4 2 x0. Sau đó, dùng phương pháp như trong Bài 16 để tìm phương án tối ưu y0 của bài toán đối ngẫu. ⎪ 3 ⎪ Kết quả như sau: ⎪−2y1 − 6y 2 − 2 y 3 ≥ −1; a) x0 = (0, 0, 12, 4), y0 = (3/2, 0, 2), f(x0) = g(y0) = 52. ⎪ ⎪8y1 + 20y 2 + 6y 3 ≥ −2. b) x0 = (0, 6, 5, 0), y0 = (−3, 4, 0), f(x0) = g(y0) = 45 ⎩ (3 ') y1 ≤ 0, y 2 ≤ 0, y 3 ≥ 0, y 4 ≥ 0. c) Bài toán đã cho vô nghiệm nên bài toán đối ngẫu cũng vô nghiệm. Theo giả thiết, bài toán đã cho có PATU là x = (0, 15, 6, 2, 0) . 0 d) x0 = (0, 3, 9, 0, 2), y0 = (−1, 2, −2), f(x0) = g(y0) = 28. Bây giờ ta tìm PATU y 0 = (y1 , y 0 , y 3 , y 0 ) của bài toán đối ngẫu. 0 0 2 4 0 1) Thế phương án x vào bất phương trình ràng buộc thứ 2 của bài toán đã cho: 18. Lập các bài toán đối ngẫu và giải các bài toán đối ngẫu bằng phương pháp đơn hình. Dùng 23 3 kết quả trên để suy ra nghiệm của các bài toán đã cho (không giải trực tiếp bằng phương pháp đơn x1 + 3x 2 − x 3 − 6x 4 + 20x5 ≥ 20 − hình): 2 2 Giải. Trước hết ta lập các bài toán đối ngẫu: ta thấy không xảy ra dấu đẳng thức (3.15 −(3/2).6 – 6.2 > 20) nên ta có y 0 = 0. 2 a) f (x) = 27x1 + 50x 2 + 18x 3 → max ⎧ x0 = 15 > 0; 2 ⎧ x1 + 2x 2 + x 3 ≤ 2; ⎪ 2) Do ⎨ x0 = 6 > 0; nên ta có ⎪ 3 ⎨−2x1 + x 2 − x 3 ≤ 4; ⎪0 x4 = 2 > 0. ⎩ ⎪ x + 2x − x ≤ −2. ⎩1 2 3 ⎧0 ⎧0 ⎪ y1 + 3y 0 + y 0 = 1 ⎪ y1 + y 0 = 1 x1 ; x2 tuøy yù; x3 ≤ 0. ⎧ y 1 = −1 0 2 3 3 ⎪ ⎪ ⎪ 0 30 30 10 ⎪ 0 30 10 ⎪0 có bài toán đối ngẫu là ⎨ − y1 − y 2 − y 3 + y 4 = 2 ⇔ ⎨ − y 1 − y 3 + y 4 = 2 ⇔ ⎨ y 3 = 2 g(y) = 2y1 + 4y 2 − 2y 3 → min 2 4 2 4 2 ⎪ ⎪ ⎪0 ⎩y4 = 5 30 30 ⎧ y1 − 2y 2 + y 3 = 27; ⎪ ⎪ −2y1 − 6y 2 − y 3 = −1 −2y1 − y 3 = −1 0 0 0 ⎪ ⎪ ⎪ 2 2 ⎩ ⎩ ⎨2y1 + y 2 + 2y 3 = 50; Vậy PATU của bài toán đối ngẫu là y0 = (–1, 0, 2, 5) với g(y0) = 25. ⎪ y − y − y ≤ 18. ⎩1 2 3 y j ≥ 0(j = 1, 3). 17. Giải các bài toán QHTT sau bằng phương pháp đơn hình. Lập các bài toán đối ngẫu và dùng b) f (x) = 4x1 + 2x 2 + 2x 3 + 3x 4 → min kết quả trên để suy ra nghiệm của bài toán đối ngẫu (không giải trực tiếp bằng phương pháp đơn ⎧ x1 + 2x 3 + x 4 ≥ 40 hình): ⎪ ⎨ x1 + 4x2 + x 3 − 2x 4 ≥ 32 ⎪ −2x + 3x − 3x − 2x ≤ 69 a) f (x) = x1 + 3x 2 + 4x 3 + x 4 → min b) f (x) = 4x1 + 5x2 + 3x 3 + 2x 4 → min ⎩ 1 2 3 4 ⎧ x1 − 2x 2 + 2x 4 ≥ 8 ⎧2x1 + x2 + 3x3 ≤ 21 x j ≥ 0 ( j = 1, 4) ⎪ ⎪ ⎨−3x 2 + x 3 − 4x 4 ≤ 18 ⎨ x1 + 2x2 + 3x3 − x 4 ≥ 27 có bài toán đối ngẫu là ⎪−3x + x + 2x − x ≥ 20 ⎪ − x + 4x + 2x + 2x ≥ 8 ⎩ ⎩1 1 2 3 4 2 3 4 xj ≥ 0 (j = 1, 4) x j ≥ 0 ( j = 1, 4) 29 30 Printed with FinePrint trial version - purchase at www.fineprint.com
  16. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội g (y) = 40y1 + 32y 2 + 69y 3 → max 2 13 g(y) = y1 − y 2 + 5y 4 → min 3 3 ⎧ y1 + y 2 − 2y 3 ≤ 4; ⎪4y + 3y ≤ 2; ⎧ ⎪2 3 ⎪2 2 ⎨ ⎪ y1 + y 2 − y 3 ≥ 1; ⎪2y1 + y 2 − 3y 3 ≤ 2; 3 3 ⎪ ⎪ y1 − 2y 2 − 2y 3 ≤ 3. ⎩ ⎪5y1 + 3y 2 − 7y 3 ≥ −2; ⎪ y1 ≥ 0, y 2 ≥ 0, y 3 ≤ 0. ⎨− y 2 + y 3 ≥ −2; c) f (x) = 5x1 + 2x 2 + 3x 3 + 4x 4 → min ⎪5 5 ⎪− y1 − y 2 + 3y 3 ≥ −1; ⎧2x1 + x 2 − 4x 4 ≥ 14 ⎪3 3 ⎪− x + 2x − 3x + x ≥ 13 ⎪4 13 ⎪1 2 3 4 ⎪ − y1 − y 2 + 7y 3 ≥ −5. ⎨ ⎪− x 2 + 2x3 ≥ 0 ⎩3 3 ⎪ x1 + x2 + x3 − 3x 4 ≥ 10 y j ≥ 0 (j = 1, 3) ⎩ x j ≥ 0 (j = 1, 4) Ta dùng phương pháp đơn hình để giải các bài toán đối ngẫu tìm phương án tối ưu y0. Sau đó, dùng phương pháp như trong Bài 16 để tìm phương án tối ưu x0 của bài toán đã cho (chú ý rằng có bài toán đối ngẫu là bài toán đã cho chính là bài toán đối ngẫu của bài toán đối ngẫu). Kết quả như sau: g (y) = 14y1 + 13y 2 + 10y 4 → max a) Bài toán đối ngẫu vô nghiệm nên bài toán đã cho cũng vô nghiệm. ⎧2y1 − y 2 + y 4 ≤ 5; b) y0 = (3/4, 1/2, 0), x0 = (0, 3, 20, 0), g(y0) = f(x0) = 46. ⎪ ⎪ y1 + 2y 2 − y 3 + y 4 ≤ 2; c) y0 = (1/2, 6, 21/2, 0), x0 =(0, 21, 11, 2), g(y0) = f(x0) = 85. ⎨ ⎪−3y 2 + 2y 3 + y 4 ≤ 3; d) y0 = (1, 5, 3), x0 =(6, 0, 5, 2, 0), g(y0) = f(x0) = − 6. ⎪−4y1 + y 2 − 3y 4 ≤ 4. ⎩ -------------------------------------------- y j ≥ 0 (j = 1, 4) MỘT SỐ ĐỀ THI CAO HỌC THAM KHẢO (TRƯỜNG ĐH KINH TẾ - LUẬT TP HCM) d) f (x) = x1 − 2x2 − 2x 3 − x 4 − 5x5 → max ⎧2 5 4 2 f(x) = – 4x1 – 3x2 → min Bài 1 (2005). Giải bài toán: ⎪ 3 x1 + 5x2 − 3 x4 − 3 x5 ≤ 3 ⎧2 x1 + 2 x2 ≤ 12 ⎪ ⎪ ⎪2 5 13 13 ⎨ x1 + 2 x2 ≤ 8 ⎨ x1 + 3x 2 − x3 − x 4 − x5 ≤ − ⎪4 x ≤ 16 3 3 3 3 ⎪ ⎩1 ⎪ − x1 − 7x 2 + x3 + 3x 4 + 7x5 ≤ 5 x j ≥ 0, j = 1, 2 ⎪ ⎩ f ( x) = 3 x1 − 2 x2 + 6 x3 + 4 x4 − 2 x5 → max Bài 2 (2007). a) Giải bài toán: xj ≥ 0 ( j = 1, 5) ⎧ x1 + 3 x3 = 36 ⎪ ⎨ x2 + 2 x3 + 4 x4 = 52 ( P) có bài toán đối ngẫu là ⎪4 x + 2 x + x = 60 ⎩3 4 5 x j ≥ 0, j = 1,5 b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D). 31 32 Printed with FinePrint trial version - purchase at www.fineprint.com
  17. Ôn thi Cao học – Toán kinh tế – Bài giải Qui hoạch tuyến tính Trần Ngọc Hội Bài 3 (2008). Giải bài toán: f ( x ) = − x1 − 2 x2 + x3 → min ⎧− x1 + 4 x2 − 2 x3 ≤ 6 ⎪ ⎨ x1 + x2 + 2 x3 ≥ 6 ⎪2 x − x + 2 x = 4 ⎩1 2 3 x j ≥ 0, j = 1, 2,3. f ( x) = 12 x1 + 15 x2 + 20 x3 → min Bài 4 (2009). a) Giải bài toán: ⎧ x1 + x2 + x3 ≥ 2 ⎪ ⎨ x1 + x2 + 2 x3 ≥ 3 ( P) ⎪x + 2x + 2x ≥ 3 ⎩1 2 3 x j ≥ 0, j = 1, 2,3. b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D). Bài 5 (2010 – Đợt 1). a) Giải bài toán: f ( x) = −2 x1 + x2 + x4 → min ⎧ x1 + x2 − x3 ≤ 15 ⎪ ⎨ x1 + x2 + x3 + x4 = 27 ( P) ⎪ 2 x − x − x ≤ 18 ⎩1 2 3 x j ≥ 0, j = 1, 2, 3, 4. b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm dạng chuẩn của bài toán (D). Bài 6 (2010 – Đợt 2). a) Giải bài toán: f ( x ) = −2 x1 + 3x2 + x3 − x4 − x5 → max ⎧3x1 − 2 x2 + x3 + 4 x4 = 8 ⎪ ⎨7 x1 − 3 x2 + 5 x4 + 2 x5 = 15 ( P) ⎪4 x − 2 x + 3x + x = 8 ⎩1 2 4 5 x j ≥ 0, j = 1, 2, 3, 4,5. b) Lập bài toán đối ngẫu (D) của bài toán (P) và tìm phương án tối ưu của bài toán (D). ------------------------------------ 33 Printed with FinePrint trial version - purchase at www.fineprint.com
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2