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ế - Bài giảng Quy hoạch tuyến tính

Chia sẻ: Tran Thi Thuy Linh | Ngày: | Loại File: PDF | Số trang:0

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

Nhằm phục vụ nhu cầu ôn thi đầu vào cao học kinh tế, mời các bạn cùng tham khảo nội dung Bài giảng Quy hoạch tuyến tính thuộc tài liệu ôn thi cao học môn Toán kinh tế dưới đây. Nội dung tài liệu giới thiệu đến các bạn những nội dung về quy hoạch tuyến tính. Hy vọng đây là tài liệu tham khảo hữu ích cho các bạn.

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ế - Bài giảng Quy 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. 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: a) Lập mô hình bài toán. 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 bảng sau: 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 (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). Mộc 0,08m3/4h 0,12m3/6h 0,3m3/9h 0,21m3/12h 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). Lãi 250000đ 350000đ 380000đ 850000đ Ta phải có 0,3x1 + 0,4x2 + 0,2x3 = 10. 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. 4) Lượng chất đạm có được là: 0,05x1 + 0,3x2 + 0,3x3 (kg). 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 1) Tiền lãi thu được là: f(x) = 25x1 + 35x2 + 38x3 + 85x4 (đv: mười ngàn). ⎧0, 2x1 + 0,1x 2 + 0,1x 3 ≥ 20 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. 4) Số giờ công lao động được sử dụng ở phân xưởng trang trí là: 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ó: x1 + 2x2+ 3x3+ 4x4 (h) 0,2x1 + 0,1x2 + 0,1x3 ≤ 2(0,05x1 + 0,3x2 + 0,3x3) ⇔ 0,1x1 – 0,5x2 – 0,5x3 ≤ 0. Ta phải có x1 + 2x2+ 3x3+ 4x4 ≤ 2500. Do đó ta có mô hình bài toán: Vậy ta có mô hình bài toán: (1) f(x) = 80x1 + 120x2 + 90x3 min (1) f(x) = 25x1 + 35x2 + 38x3 + 85x4 max ⎧0, 2x1 + 0,1x 2 + 0,1x 3 ≥ 20 ⎪0, 3x + 0, 4x + 0, 2x = 10 ⎧0, 08x1 + 0,12x 2 + 0, 3x 3 + 0, 21x 4 ≤ 350 ⎪ 1 2 3 ⎪ (2) ⎨ (2) ⎨4x1 + 6x 2 + 9x 3 + 12x 4 ≤ 1000 ⎪ 0, 05x 1 + 0, 3x 2 + 0, 3x 3 ≤ 15 ⎪ x + 2x + 3x + 4x ≤ 2500 ⎪⎩0,1x1 − 0, 5x 2 − 0, 5x 3 ≤ 0 ⎩ 1 2 3 4 (3) xj ≥ 0 ( j = 1, 4) (3) xj ≥ 0 (j = 1, 3) 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 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ữ ⎧ x1 + 2x 2 ≤ 25000 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 ⎪ x + 2x ≥ 10000 sau: ⎪ 1 2 ⎪⎪2x1 + 3x 2 + 7x 3 ≤ 30000 Nguyên liệu Lượng Định mức tiêu hao nguyên liệu(kg) cho 1đv (2) ⎨ dự trữ (tấn) A B C ⎪4x1 + x 3 ≤ 35000 I 25 1 2 0 ⎪4x1 + x 3 ≥ 15000 ⎪ II 30 2 3 7 ⎪⎩ x 2 + 4x 3 ≤ 40000 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 a) Lập mô hình bài toán. 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 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à 15 tấn loại III sắp hết hạn sử dụng? A B 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 I 40 10 (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). Ta phải có 2x1 + 3x2+ 7x3 ≤ 30000 (30000kg = 30tấn). • 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. 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). a) Ta có mô hình bài toán: 2) Lượng sắt kho I xuất ra là: x1 + x2 (tấn). (1) f(x) = 6x1 + 7x2 + 8x3 max Ta phải có x1 + x2 ≤ 60. 3) Lượng sắt kho II xuất ra là: x3 + x4 (tấn). ⎧ x1 + 2x 2 ≤ 25000 ⎪2x + 3x + 7x ≤ 30000 Ta phải có x3 + x4 ≤ 40. ⎪ 1 2 3 4) Lượng sắt công trường A nhận được là: x1 + x3 (tấn). (2) ⎨ 4x ⎪ 1 + x 3 ≤ 35000 Ta phải có x1 + x3 ≥ 50. ⎪⎩ x 2 + 4x 3 ≤ 40000 5) Lượng sắt công trường B nhận được là: x2 + x4 (tấn). Ta phải có x2 + x4 ≥ 30. (3) xj ≥ 0 (j = 1, 3) 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 Ta có mô hình bài toán: 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: (1) f(x) = 40x1 + 10x2 + 20x3 + 30x4 min x1 + 2x2 ≥ 10000 và 4x1 + x3 ≥ 15000. ⎧ x1 + x 2 ≤ 60 ⎪ x + x ≤ 40 ⎪ 3 4 Ta có mô hình bài toán: (2) ⎨ ⎪ x 1 + 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 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 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 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 các loại cây trên sao cho chi phí sản xuất đạt thấp nhất. 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: Giải. Gọi I II III • x1, x2 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất I. A 1 3 1 • x3, x4 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất II. B 1 2 2 • 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 lượng đạt được cao nhất. Điều kiện: xj ≥ 0 (j= 1, ..., 6). Khi đó 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). • 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. Ta phải có x1 + x2 ≤ 30. 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). 1) Diện tích trồng cây trên khu vườn A là x1 + x2 + x3 (ha). Ta phải có x5 + x6 ≤ 50. Ta phải có x1 + x2 + x3 ≤ 30. 5) Sản lượng Tiêu thu được là 8x1 + 7x3 + 10x5 (tạ). 2) Diện tích trồng cây trên khu vườn B là x4 + x5 + x6 (ha). Ta phải có 8x1 + 7x3 + 10x5 ≥ 60 (6tấn = 60tạ). Ta phải có x4 + x5 + x6 ≤ 40. 6) Sản lượng Điều thu được là 7x2 + 11x4 + 6x6 (tạ). 3) Sản lượng cây loại I thu được là x1 + x4 (tấn). Ta phải có 7x2 + 11x4 + 6x6 ≥ 50 (5tấn = 50tạ). 4) Sản lượng cây loại II thu được là 3x2 + 2x5 (tấn). Ta có mô hình bài toán: 5) Sản lượng cây loại III thu được là x3 + 2x6 (tấn). (1) f(x) = 1,4x1 + 2,1x2 + 1,3x3 + 2,4x4 + 1,6x5 + 1,8x6 max 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ó ⎧ x1 + x 2 ≤ 30 x1 + x4 3x 2 + 2x5 x3 + 2x 6 ⎧ x1 − 6x2 + x 4 − 4x5 = 0 ⎪ x + x ≤ 40 = = ⇔⎨ ⎪⎪ 3 4 2 1 4 ⎩2x1 − x3 + 2x4 − 2x 6 = 0 (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 Ta có mô hình bài toán: ⎪ 1 3 5 (1) f(x) = x1 + x4 max ⎪⎩7x 2 + 11x 4 + 6x 6 ≥ 50 ⎧ x1 + x 2 + x 3 ≤ 30 (3) xj ≥ 0 (j = 1, 6) ⎪ x + x + x ≤ 40 ⎪ 4 5 6 (2) ⎨ x ⎪ 1 − 6x 2 + x 4 − 4x 5 = 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 ⎪⎩2x1 − x 3 + 2x 4 − 2x 6 = 0 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 sau: (3) xj ≥ 0 (j = 1, 6) Khu đất Tiêu Điều I 1,2 2,2 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 9 8 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 II 1,4 2,3 7 11 sau: III 1,8 2 Khu đất Tiêu Điều 10 6 I 1,4 2,1 (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 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 Giải. Gọi b) f (x) = 2x1 + 3x2 − 5x 3 → max • 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 • x5, x6 (ha) lần lượt là diện tích trồng Tiêu, Điều trên khu đất III. ⎨−2x1 + x 2 + x3 ≤ 8; ⎪ 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. 4) Diện tích trồng trên khu đất III là x5 + x6 (ha). ⎧ x1 + 2x 2 + 3x3 = 22; ⎪ Ta phải có x5 + x6 ≤ 70. ⎨2x1 + x 2 + 5x 3 = 25; 5) Sản lượng Tiêu thu được là 9x1 + 7x3 + 10x5 (tạ). ⎪ x + 2x + x + x = 20. Tiền lãi thu được từ Tiêu là 2(9x1 + 7x3 + 10x5) (triệu đồng). ⎩ 1 2 3 4 6) Sản lượng Điều thu được là 8x2 + 11x4 + 6x6 (tạ). xj ≥ 0 (j = 1, 4) 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: (1) f(x) = 18x1 + 20x2 + 14x3 + 27,5x4 + 20x5 + 15x6 max d) f (x) = −3x1 + x 2 + 3x 3 − x 4 → min ⎧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 ⎪ (2) ⎪ 1 ⎨ 2 ⎨2x1 − 6x2 + 3x3 + 3x4 = 9; ⎪ 3x + 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 a) f (x) = x1 − 4x 2 − 3x3 → min ⎪⎧2x1 + 2x 2 − x 3 ≤ 1; ⎨ ⎧2x1 + x 2 − 2x3 ≤ 16; ⎪⎩ x1 − x2 − 3x3 ≥ 1. ⎪ ⎨ −4x1 + 2x3 ≤ 8; xj ≥ 0 (j = 1, 3) ⎪ 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; xj ≥ 0 (j = 1, 3) ⎪2x − x + 2x + x = 4. ⎩ 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 Ta có bài toán: (3 '') xj ≥ 0 (j = 1, 7) Khi đó bài toán có (1) g(x) = − x1 − 2x 2 + x 3 → min - Ẩn cơ bản thứ 1 là x4; ⎧4x1 − 4x 2 + 2x 3 ≥ −6; - Ẩn cơ bản thứ 2 là x6; ⎪ - Ẩ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. Hệ An Cbản Phương −1 −2 1 0 0 An3 số An X1 X2 x3 x4 x5 λi BảngI (3) xj ≥ 0 (j = 1, 3) 0 x4 6 −4 4 −2 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: M x6 6 1 1 2 0 −1 λ2 = 6/2 =3 M x7 4 2 −1 2 0 0 λ3 = 4/2 =2* g(x) = − x1 − 2x 2 + x 3 → min g(x) 0 1 2 −1 0 0 ⎧4x1 − 4x 2 + 2x 3 − x 4 = − 6; 10M 3M 0 4M* 0 −M ⎪ ⎨ x1 + x 2 + 2x 3 − x5 = 6; 0 x4 10 −2 3 0 1 0 λ1 = 10/3 BảngII ⎪2x − x + 2x = 4. M x6 2 −1 2 0 0 −1 λ2 = 2/2 = 1* ⎩ 1 2 3 1 x3 2 1 −1/2 1 0 0 xj ≥ 0 (j = 1, 5) g(x) 2 2 3/2 0 0 0 2M −M 2M* 0 0 −M 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 toán sau: 0 x4 7 −1/2 0 0 1 3/2 BảngIII (1 ') g(x) = − x1 − 2x 2 + x 3 → min −2 x2 1 −1/2 1 0 0 −1/2 1 x3 5/2 3/ 4 0 1 0 −1/4 ⎧−4x1 + 4x 2 − 2x 3 + x4 = 6; ⎪ g(x) ½ 11/4* 0 0 0 3/4 (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 x2 8/3 0 1 2/3 0 −2/3 (3 ') xj ≥ 0 (j = 1, 5) −1 x1 10/3 1 0 4/3 0 −1/3 BảngIV Ma trận hệ số ràng buộc là: g(x) −26/3 0 0 −11/3 0 5/3* ⎛ −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 0 0 −9/2 −5/4 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 ưu là phương án cơ bản ban đầu x định bởi: 0 ⎧ x1 + 2x 2 + 2x 3 + x4 = 30; ⎪ ⎧ x5 = 13 / 2; (2 ') ⎨ x1 + 2x 2 + x 3 + x 6 = 25; ⎪x ⎪ ⎪ 2 = 7; ⎩2x1 + x 2 + x 3 − x5 + x7 = 40. ⎨ ⎪ x1 = 11 / 2; (3 ') xj ≥ 0 (j = 1, 7) ⎪⎩ x 3 = x 4 = x 6 = x7 = 0. Khi đó bài toán có với g(x ) = −39 / 2. 0 - Ẩn cơ bản thứ 1 là x4; 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ứ 2 là x6; - Ẩ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 số cơ án x1 X2 x3 x4 x5 λi h) f (x) = 5x1 + 10x 2 + 7x3 → max bản ⎧ x1 + 2x 2 + 2x3 ≤ 30; 0 x4 30 1 2 2 1 0 λ1 = 30/2 ⎪ −M x6 25 1 2 1 0 0 λ2= 25/2* BảngI ⎨ x1 + 2x2 + x3 = 25; −M x7 40 2 1 1 0 −1 λ3 = 40/1 ⎪2x + x + x ≥ 40. ⎩ 1 2 3 f(x) 0 −5 −10 −7 0 0 xj ≥ 0 (j = 1, 3) −65M −3M −3M* −2M 0 M 0 x4 5 0 0 1 1 0 BảngII 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: 10 x2 25/2 1/2 1 1/2 0 0 λ2= (25/2)/(1/2) =25 (1) f (x) = 5x1 + 10x 2 + 7x 3 → max −M x7 55/2 3/ 2 0 1/2 0 −1 λ3= (55/2)/(3/2) =55/3* ⎧ x1 + 2x 2 + 2x3 + x4 = 30; f(x) 125 0 0 −2 0 0 ⎪ −55M/2 −3M/2* 0 −M/2 0 M (2) ⎨ x1 + 2x 2 + x3 = 25; 0 x4 5 0 0 1 0 λ1 = 5/1=5* 1 ⎪ ⎩2x1 + x 2 + x3 − x5 = 40. BảngIII 10 x2 10/3 0 1 1/3 0 1/3 λ2= (10/3)/(1/3)=10 −2/3 λ3 = (55/3)/(1/3)=55 (3) xj ≥ 0 (j = 1, 5) 5 x1 55/3 1 0 1/3 0 f(x) 125 0 0 −2* 0 0 Các vế phải của phương trình ràng buộc trong (2) đều không âm. 7 x3 5 0 0 1 1 0 Ma trận hệ số ràng buộc là: 10 x2 5/3 0 1 0 −1/3 1/3 BảngIV ⎛ 1 2 2 1 0⎞ 0 0 5 x1 50/3 1 0 0 −1/3 −2/3 A = ⎜⎜ 1 2 1 0 0 ⎟⎟ 1 0 f(x) 135 0 0 0 2 0 ⎜ 2 1 1 0 −1 ⎟ 0 1 ⎝ ⎠ 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ó 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 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). ⎪x Ta phải có 0,5x1 + 0,2x2 + 0,3x3+ 0,6x4 ≤ 600. ⎪ 2 = 5 / 3; 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: ⎪⎩ x 4 = x 5 = x 6 = x7 = 0. (1) f(x) = 0,8x1 + 0,3x2 + 0,38x3+ 0,4x4 max f (x ) = 135. 0 ⎧ 0,5x 1 + 0,2x 2 + 0,3x 3 + 0,6x 4 ≤ 600 với (2) ⎨ ⎩ 0,1x + 0,4x + 0,2x + 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 1 2 3 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 (3) xj ≥ 0 ( j = 1, 4) 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; ⎧ x1 + 2x2 − x3 + x4 = 2; (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 2 3 4 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à: xj ≥ 0 (j = 1, 4) ⎛ 0, 5 0, 2 0, 3 0, 6 1 0 ⎞ A=⎜ ⎟ ĐS: x0 = (3,2,5,0); f(x0) = 8 ⎝ 0,1 0, 4 0, 2 0, 5 0 1 ⎠ 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 đó: j) f (x) = 3x1 − x 2 + 2x 3 + x 4 → max - Ẩn cơ bản thứ 1 là x5; - Ẩ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. số cơ bản án x1 x2 x3 x4 x5 x6 λi ⎩ 1 2 3 0 x5 600 0, 5 0,2 0,3 0,6 1 0 λ1 = 600/0,5* xj ≥ 0 (j = 1, 4) 0 x6 800 0,1 0,4 0,2 0,5 0 1 λ2 = 800/0,1 Bảng I ĐS: x0 = (28,108,0,62,); f(x0) = 38. f(x) 0 − 0,8* − 0,3 − 0,38 − 0,4 0 0 0,8 x1 1200 1 0,4 0,6 1,2 2 0 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 x6 680 0 0,36 0,14 0,38 −0,2 1 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 sau: 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 Suất tiêu hao(kg) Hàng H1 H2 H3 H4 ưu là phương án cơ bản ban đầu x1 định bởi: Nguyên liệu ⎧ x1 = 1200; ⎪ N1: 600kg 0,5 0,2 0,3 0,6 ⎨ x 6 = 680; N2: 800kg 0,1 0,4 0,2 0,5 ⎪ x = x = x = x = 0. Tiền lãi (ngàn) 0,8 0,3 0,38 0,4 ⎩ 2 3 4 5 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. 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, 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 x2, x3, x4) = (1200, 0, 0, 0) với f(x0) = 960. (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 1) Tiền lãi thu được là: f(x) = 0,8x1 + 0,3x2 + 0,38x3+ 0,4x4 (ngàn). hàng khác. Khi đó tổng tiền lãi thu được là 960 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: - Tổng số sản phẩm mặt hàng H1 và H2 không ít hơn 1000. Hệ An Phương 0,8 0,3 0,5 0,4 0 0 0 - Tiền lãi cho 1 đơn vị mặt hàng H3 không phải là 0,38 mà là 0,5. Số cơ bản án x1 x2 x3 x4 x5 x6 x7 λi 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 0 x5 600 0,5 0,2 0,3 0,6 1 0 0 λ1 = 600/0,5 1000 được thể hiện bởi điều kiện: x1 + x2 ≥ 1000. 0 x6 800 0,1 0,4 0,2 0,5 0 1 0 λ2= 800/0,1 Bảng I Ta có bài toán: −M x8 1000 1 1 0 0 0 0 1 λ3 = 1000/1* (1) f(x) = 0,8x1 + 0,3x2 + 0,5x3+ 0,4x4 max f(x) 0 −0,8 − 0,3 − 0,5 − 0,4 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 x5 100 0 −0,3 0,33 0,6 1 0 0, 5 λ1 = 100/0,5* ⎪ x + x ≥ 1000 ⎩ 1 2 0 x6 700 0 0,3 0,2 0,5 0 1 0,1 λ2= 700/0,1 Bảng II 0,8 x1 1000 1 1 0 0 0 0 −1 (3) xj ≥ 0 ( j = 1, 4) 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: f(x) 800 0 0,5 − 0,5 − 0,4 0 0 − 0,8* 0 x7 200 0 −0,6 0, 6 1,2 2 0 1 λ1 = 200/0,6 0 x6 680 0 0,36 0,14 0,38 −0,2 1 0 λ2= 680/0,14 Bảng III (1 ') f (x) = 0, 8x1 + 0, 3x 2 + 0, 5x 3 + 0, 4x 4 → max 0,8 x1 1200 1 0,4 0,6 1,2 2 0 0 λ3= 1200/0,6 ⎧0,5x1 + 0,2x2 + 0,3x3 + 0,6x4 + x5 = 600; f(x) 960 0 0,02 − 0,02* 0,56 1,6 0 0 ⎪ (2 ') ⎨0,1x1 + 0,4x 2 + 0,2x3 + 0,5x4 + x6 = 800; 0,5 x3 1000/3 0 −1 1 2 10/3 0 10/6 ⎪ x + x − x = 1000. 0 x6 1900/3 0 0,5 0 0,1 −2/3 1 −7/30 Bảng IV ⎩ 1 2 7 0,8 X1 1000 1 1 0 0 0 0 −1 (3 ') xj ≥ 0 (j = 1, 7) f(x) 2900/3 0 0 0 0,6 5/3 0 1/30 Các vế phải của phương trình ràng buộc trong (2’) đều không âm. 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 tối ưu là phương án cơ bản ban đầu x định bởi: Ma trận hệ số ràng buộc là: 1 ⎛ 0, 5 0, 2 0, 3 0, 6 1 0 0 ⎞ 0 A = ⎜⎜ 0,1 0, 4 0, 2 0, 5 0 1 0 ⎟⎟ 0 ⎧x3 = 1000 / 3; ⎜ 1 ⎪x = 1900 / 3; ⎝ 1 0 0 0 0 −1 ⎟⎠ 1 ⎪ 6 ⎨ 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ó ⎪ x1 = 1000; 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, ⎪⎩ x 2 = x 4 = x5 = x7 = x 8 = 0. để xây dựng bài toán mở rộng dạng chuẩn: với f (x1 ) = 2900 / 3. (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) Khi đó bài toán có 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 - Ẩn cơ bản thứ 1 là x5; 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 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 Bán thành phẩm Phương thức cắt Luợng bán thành phẩm cần có 420 6 6 7 10 -1 -1 -1 P1 P2 P3 P4 T1 3 4 5 10 240 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 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 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda 0 X4 24 3/10 2/5 1/2 1 -1/10 0 0 80 M X9 100 2 0 1 0 0 -1 0 50 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 X10 80 1 2 1 0 0 0 -1 80 số lượng thừa là ít nhất. F(x) 0 -200 -400 -200 0 0 0 0 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. Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda 3) Lượng bán thành phẩm T2 thu được: 2x1 + x3. 0 X4 9 0 2/5 7/20 1 -1/10 3/20 0 45/2 200 X1 50 1 0 1/2 0 0 -1/2 0 - Ta phải có 2x1 + x3 ≥ 100. M X10 30 0 2 1/2 0 0 1/2 -1 15 4) Lượng bán thành phẩm T3 thu được: x1 + 2x2 + x3. F(x) 10000 0 -400 -100 0 0 -100 0 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 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda ⎪ x + 2x + x ≥ 80 0 X4 3 0 0 1/4 1 -1/10 1/20 1/5 - ⎩ 1 2 3 200 X1 50 1 0 1/2 0 0 -1/2 0 - 400 X2 15 0 1 1/4 0 0 1/4 -1/2 - (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: F(x) = 200x1 + 400x2 + 200x3 + Mx8 + Mx9 + Mx10 => MIN 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 trong 1 ngày đêm I II III Các ràng buộc: Albumin Ít nhất 200g 0,3 0,8 2 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 Trong đó: được mức yêu cầu cho gia súc về các chất trong 1 ngày đêm. 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ụ x8, x9, x10 là biến giả 2, 3). Khi đó 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). Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda 2) Lượng Albumin có được: 0,3x1 + 0,8x2 + 2x3 (g). M X8 240 3 4 5 10 -1 0 0 24 Ta phải có 0,3x1 + 0,8x2 + 2x3 ≥ 200. M X9 100 2 0 1 0 0 -1 0 - 3) Lượng chất béo có được: 3x1 + 0,4x3 (g). M X10 80 1 2 1 0 0 0 -1 - F(x) 0 -200 -400 -200 0 0 0 0 Ta phải có 3x1 + 0,4x3 ≤ 100. 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 4) Lượng chất đạm có được: x1 + 10x2 (g). 3 X3 94 11/100 0 1 -1/2 0 - 0 X5 312/5 739/250 0 0 1/5 1 - Ta phải có x1 + 10x2 = 150. 15/10 X2 15 1/10 1 0 0 0 - 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 Vốn (ngàn đồng) Lao động (ngàn đồ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, để Sau đây là lời giải tham khảo từ chương trình máy tính: đả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 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 F(x) = 8/10x1 + 15/10x2 + 3x3 + Mx6 + Mx7 => MIN (j = 1, 2, 3). Khi đó Các ràng buộc: 1) Tổng giá trị sản lượng thu được: f(x) = 2x1 + 1,5x2 + 2,5x3 (triệu). 2) Tổng diện tích trồng: x1 + x2 + x3 (ha). 3/10x1 + 8/10x2 + 2x3 - x4 = 200 Ta phải có x1 + x2 + x3 ≤ 3000. 3x1 + 4/10x3 + x5 = 100 x1 + 10x2 = 150 3) Diện tích trồng nông sản A: x1 (ha). Ta phải có x1 ≥ 600. Trong đó: 4) Chi phí về vốn: 300x1 + 350x2 + 400x3 (ngàn). x4, x5 là biến phụ Ta phải có 300x1 + 350x2 + 400x3 ≤ 1200000 (1200triệu = 1200000ngàn). x6, x7 là biến giả 5) Chi phí về lao động: 500x1 + 400x2 + 450x3 (ngàn). x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0 Ta phải có 500x1 + 400x2 + 450x3 ≤ 1600000 (1600triệu = 1600000ngàn). Ci Xi Yi X1 X2 X3 X4 X5 Lamda Ta có bài toán: M X6 200 3/10 8/10 2 -1 0 250 (1) f(x) = 2x1 + 1,5x2 + 2,5x3 max 0 M X5 X7 100 150 3 1 0 10 4/10 0 0 0 1 0 - 15 ⎧ x1 + x 2 + x 3 ≤ 3000 ⎧ x1 + x 2 + x 3 ≤ 3000 ⎪ x ≥ 600 ⎪ x ≥ 600 F(x) 0 -4/5 -3/2 -3 0 0 ⎪ 1 ⎪ 1 350 13/10 54/5 2 -1 0 (2) ⎨ ⇔ ⎨ ⎪ 300x 1 + 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 Cột có giá lớn nhỏ nhất ứng với x2 vậy biến đưa vào là : x2 ⎪⎩500x1 + 400x 2 + 450x 3 ≤ 1600000 ⎪⎩5x1 + 4x 2 + 4, 5x 3 ≤ 16000 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) Ci Xi Yi X1 X2 X3 X4 X5 Lamda M X6 188 11/50 0 2 -1 0 94 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 0 X5 100 3 0 2/5 0 1 250 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, 15/10 X2 15 1/10 1 0 0 0 - 2400 (ha). Khi đó tổng giá trị sản lượng thu được là 7200 (triệu đồng). F(x) 45/2 -13/20 0 -3 0 0 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: 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 Bài toán ở dạng chuẩn: Cột có giá lớn 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 F(x) = 2x1 + 3/2x2 + 5/2x3 - Mx8 => MAX Ci Xi Yi X1 X2 X3 X4 X5 Lamda Các ràng buộc: 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 x1 - x5 = 600 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 3x1 + 7/2x2 + 4x3 + x6 = 12000 cáo là cao nhất. 5x1 + 4x2 + 9/2x3 + x7 = 16000 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 Trong đó: ≥ 0 (j = 1, 2, 3). Khi đó 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ụ x8 là biến giả f(x) = 15x1 + 9x2 + 30x3 (ngàn người). x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0 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 ≤ 60 và x1 ≥ 30. Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda 0 X4 3000 1 1 1 1 0 0 0 3000 3) Số lần quảng cáo tối đa trên phát thanh là 90 nên x2 ≤ 90. -M X8 600 1 0 0 0 -1 0 0 600 4) Số lần quảng cáo tối đa trên báo là 26 nên x3 ≤ 26. 0 X6 12000 3 7/2 4 0 0 1 0 4000 5) Chi phí quảng cáo: 1,5x1 + 0,5x2 + x3 (triệu đồng). 0 X7 16000 5 4 9/2 0 0 0 1 3200 F(x) 0 -2 -3/2 -5/2 0 0 0 0 Ta phải có 1,5x1 + 0,5x2 + x3 ≤ 100. -600 -1 0 0 0 1 0 0 Ta có bài toán: (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 Cột có giá trị nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 ⎧ x1 ≤ 60 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2 ⎪ x ≥ 30 ⎪⎪ 1 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda (2) ⎨ x 2 ≤ 90 0 X4 2400 0 1 1 1 1 0 0 2400 2 X1 600 1 0 0 0 -1 0 0 - ⎪ x ≤ 26 0 X6 10200 0 7/2 4 0 3 1 0 2550 ⎪ 3 0 X7 13000 0 4 9/2 0 5 0 1 26000/9 ⎪⎩1,5x1 + 0,5x 2 + x3 ≤ 100 F(x) 1200 0 -3/2 -5/2 0 -2 0 0 0 0 0 0 0 0 0 0 (3) x j ≥ 0 (j = 1, 3) 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 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ố Cột có giá trị nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 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à 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. Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 Lamda 5/2 X3 2400 0 1 1 1 1 0 0 - Sau đây là lời giải tham khảo từ chương trình máy tính: 2 X1 600 1 0 0 0 -1 0 0 - Bài toán ở dạng chuẩn: 0 X6 600 0 -1/2 0 -4 -1 1 0 - 0 X7 2200 0 -1/2 0 -9/2 1/2 0 1 - 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ụ Truyền hình 1,5 60 15.000 x9 là biến giả (1phút/lần) x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0, x8 >=0 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 X4 60 1 0 0 1 0 0 0 0 Báo 1 26 30.000 -M X9 30 1 0 0 0 -1 0 0 0 (1/2trang/lần) 0 X6 90 0 1 0 0 0 1 0 0 0 X7 26 0 0 1 0 0 0 1 0 0 X8 100 3/2 1/2 1 0 0 0 0 1 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 F(x) 0 -15 -9 -30 0 0 0 0 0 a) f (x) = 2x1 + 3x 2 − 5x3 → max -30 -1 0 0 0 1 0 0 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 Cột có giá trị nhỏ nhất ứng với x1 vậy biến đưa vào là : x1 ⎪4x1 + x 2 − 2x3 ≤ −12 ⎪ Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 2 ⎪ 1 ⎨ −2x1 + x 2 + x 3 ≤ 8 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 ⎪ 2 0 X4 30 0 0 0 1 1 0 0 0 ⎪ 3 ⎪⎩ −2x1 + 2 x 2 + x3 = 20 15 X1 30 1 0 0 0 -1 0 0 0 0 X6 90 0 1 0 0 0 1 0 0 0 X7 26 0 0 1 0 0 0 1 0 0 X8 55 0 1/2 1 0 3/2 0 0 1 x1 ≥ 0, x 2 ≤ 0 F(x) 450 0 -9 -30 0 -15 0 0 0 0 0 0 0 0 0 0 0 0 Giải. Bài toán đối ngẫu: 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 Cột có giá trị nhỏ nhất ứng với x3 vậy biến đưa vào là : x3 ⎧4y1 − 2y 2 − 2y 3 ≥ 2 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 Ci 0 Xi X4 Yi 30 X1 0 X2 0 X3 0 X4 1 X5 1 X6 0 X7 0 X8 0 ⎪ 2 2 15 X1 30 1 0 0 0 -1 0 0 0 ⎪⎩−2y1 + y 2 + y 3 = −5 0 X6 90 0 1 0 0 0 1 0 0 30 X3 26 0 0 1 0 0 0 1 0 y1 ≥ 0, y 2 ≥ 0 0 X8 29 0 1/2 0 0 3/2 0 -1 1 F(x) 1230 0 -9 0 0 -15 0 30 0 Các cặp ràng buộc đối ngẫu như sau: 0 0 0 0 0 0 0 0 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 4x1 + x2 − 2x3 ≤ −12 y1 ≥ 0 Cột có giá trị nhỏ nhất ứng với x5 vậy biến đưa vào là : x5 1 y2 ≥ 0 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 5 −2x1 + x 2 + x 3 ≤ 8 2 Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 3 y3 tuỳ ý 0 X4 32/3 0 -1/3 0 1 0 0 2/3 -2/3 −2x1 + x 2 + x3 = 20 15 X1 148/3 1 1/3 0 0 0 0 -2/3 2/3 2 0 X6 90 0 1 0 0 0 1 0 0 x1 ≥ 0 4y1 − 2y 2 − 2y 3 ≥ 2 30 X3 26 0 0 1 0 0 0 1 0 0 X5 58/3 0 1/3 0 0 1 0 -2/3 2/3 x2 ≤ 0 1 3 F(x) 1520 0 -4 0 0 0 0 20 10 y1 + y 2 + y 3 ≤ 3 0 0 0 0 0 0 0 0 0 2 2 x3 tuỳ ý −2y1 + y 2 + y 3 = −5 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 Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 5 b) f (x) = −3x1 + x 2 + 3x 3 − x 4 → min Ci Xi Yi X1 X2 X3 X4 X5 X6 X7 X8 ⎧ x1 + 2x2 − x 3 + x 4 = 2 0 X4 30 0 0 0 1 1 0 0 0 ⎪ ⎨2x1 − 6x 2 + 3x 3 + 3x 4 ≤ 9 15 X1 30 1 0 0 0 -1 0 0 0 0 X6 32 0 0 0 0 -3 1 2 -2 30 X3 26 0 0 1 0 0 0 1 0 ⎪x − x + x − x ≥ 6 9 X2 58 0 1 0 0 3 0 -2 2 ⎩ 1 2 3 4 F(x) 1752 0 0 0 0 0 0 0 0 0 12 0 0 0 12 0 18 0 x1 ≥ 0, x 2 ≤ 0, x4 ≤ 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 y 2 ≤ 0, y 3 ≥ 0 x1 ≤ 0, x 2 ≥ 0, x 4 ≥ 0 Các cặp ràng buộc đối ngẫu như sau: Giải. Bài toán đối ngẫu: g(y) = 2y1 + 9y 2 + 6y 3 → max x1 + 2x 2 − x 3 + x4 = 2 y1 tuỳ ý ⎧ y1 + 2y 2 + y 3 ≥ −3 2x1 − 6x 2 + 3x3 + 3x4 ≤ 9 y2 ≤ 0 ⎪2y − 6y − y ≤ 1 ⎪ 1 2 3 x1 − x 2 + x 3 − x4 ≥ 6 y3 ≥ 0 ⎨ ⎪ 1− y + 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 x3 tuỳ ý − y1 + 3y 2 + y 3 = 3 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 2 3 x2 ≥ 0 2y1 − 6y 2 − y 3 ≤ 1 x 2 ≥ 0, x 3 ≤ 0 x3 tuỳ ý − y1 + 3y 2 + y 3 = 3 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 ⎩ 1 2 3 ⎧ x1 − x2 + 2x3 − x4 = 2; 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ỳ ý x1 tuỳ ý − y1 + y 2 + 2y 3 = 1 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 ⎧ y1 + 2y 2 + y 3 ≥ 2; 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) ⎪ − 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. ⎨ ⎪ x 2 + x 4 ≥ 8 (3 ') y j (j = 1, 3) tuøy yù. ⎪⎩x2 + x3 ≤ 20 Theo giả thiết, bài toán đã cho có PATU là x 0 = (3, 3, 1 ,0) . x j ≥ 0 (j = 1, 4) Bây giờ ta tìm PATU y 0 = (y10 , y 02 , y 03 ) của bài toán đối ngẫu. Giải. Bài toán đối ngẫu của bài toán trên là: ⎧ 0 2 ⎧ x10 = 3 > 0; ⎪ y1 = 11 (1 ') g(y) = 24y1 + 22y 2 + 8y 3 + 20y 4 → max ⎧ y10 + 2y 02 + y 03 = 2 ⎪ ⎪ ⎧− y1 ≤ 2; Do ⎨ x 02 = 3 > 0; nên ta có ⎪− y 0 + y 0 + y 0 = 1 ⇔ ⎪ y 0 = 7 ⎨ 1 2 3 ⎨ 2 ⎪ y + y + y + y ≤ 3; ⎪ 0 11 ⎪ 1 ⎩ x 3 = 1 > 0. ⎪ 0 ⎪ 2 3 4 2y − 3y 0 + y 0 = −1 (2 ') ⎨ ⎩ 1 2 3 ⎪ 0 6 2y + y + y ≤ 2; ⎪⎩ y 3 = 11 ⎪ 1 2 4 ⎪⎩− 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. 3 5 1 Theo giả thiết, bài toán đã cho có PATU là x 0 = (0, 5, 11, 3) . 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) 2 2 2 Bây giờ ta tìm PATU y 0 = (y10 , y 02 , y 30 , y 04 ) của bài toán đối ngẫu. ⎧ x1 + 2x 2 − 3x 3 + x 4 − 5x5 = 5 1) Thế phương án x0 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 ⎪ ⎨2x1 + 3x 2 − 5x 3 + 2x 4 − 7x 5 = 8 dấu đẳng thức (5 + 11 < 20) nên ta có y 04 = 0. ⎪3x + x − 2x + 6x + 2x = 6 ⎩ 1 2 3 4 5 ⎧ 0 1 xj ≥ 0 (j = 1, 5) ⎧ x02 = 5 > 0; ⎧ y10 + y 20 + y 03 + y 04 = 3 ⎧ y10 + y 20 + y 30 = 3 ⎪ y1 = 2 ⎪ 0 ⎪ ⎪ ⎪ Giải. Bài toán đối ngẫu của bài toán trên là: 2) Do ⎨ x3 = 11 > 0; nên ta có ⎨2y 0 + y 0 + y 0 = 2 ⇔ ⎨2y10 + y 20 = 2 ⇔ ⎨ y 20 = 1 1 2 4 ⎪ 0 ⎪ 0 ⎪ 0 ⎪ ⎩ x4 = 3 > 0. ⎩− y1 + 2y 2 + y 3 = 3 0 0 ⎩ − y1 + 2y 2 + y 3 = 3 0 0 3 (1 ') g(y) = 5y1 + 8y 2 + 6y 3 → max ⎪ y 03 = ⎩ 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; ⎪ y + 2y + 6y ≤ −2; 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) ⎪ 1 2 3 ⎧−5x1 + x2 − x3 − 2x4 + 8x5 ≥ 5 ⎪− ⎩ 5y 1 − 7y 2 + 2y 3 ≤ 1. ⎪ 23 ⎪− 3 (3 ') y j (j = 1, 3) tuøy yù. x1 + 3x2 − x3 − 6x4 + 20x5 ≥ 20 ⎪⎪ 2 2 3 5 1 ⎨ 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 2 2 2 ⎪ Bây giờ ta tìm PATU y 0 = (y10 , y 02 , y 03 ) của bài toán đối ngẫu. ⎪3 x + 1 x ≤ 3 ⎧ x10 = 3 / 2 > 0; ⎧ y10 + 2y 20 + 3y 30 = −3 ⎧ y10 = −27 ⎪⎩ 2 1 2 3 ⎪ 0 ⎪ 0 ⎪ 0 Do ⎨ x 2 = 5 / 2 > 0; nên ta có ⎨2y1 + 3y 02 + y 03 = −4 ⇔ ⎨ y 2 = 18 xj ≥ 0 (j = 1, 5) ⎪ 0 ⎪ ⎪ 0 ⎩ x 3 = 1 / 2 > 0. ⎩−3y1 − 5y 2 − 2y 3 = −1 ⎩ y 3 = −4 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 2 4 5 ⎩ 1 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 = (y10 , y 02 , y 30 , y 04 ) của bài toán đối ngẫu. 1) Thế phương án x0 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 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 02 = 0. Giải. Trước hết ta lập các bài toán đối ngẫu: a) f (x) = 27x1 + 50x 2 + 18x 3 → max ⎧ x02 = 15 > 0; ⎪ ⎧ x1 + 2x 2 + x 3 ≤ 2; 2) Do ⎨ x03 = 6 > 0; nên ta có ⎪ ⎪ 0 ⎨−2x1 + x 2 − x 3 ≤ 4; ⎩ x4 = 2 > 0. ⎪ x + 2x − x ≤ −2. ⎧ 0 ⎧ 0 ⎩ 1 2 3 ⎪ y1 + 3y 02 + y 03 = 1 ⎪ y1 + y 03 = 1 ⎧ y10 = −1 x1 ; x2 tuøy yù; x3 ≤ 0. ⎪ ⎪ ⎪ 0 3 0 3 0 1 0 ⎪ 0 3 0 1 0 ⎪ 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 ⎪ 3 0 ⎪ 3 0 ⎩y4 = 5 ⎧ y1 − 2y 2 + y 3 = 27; ⎪⎩ − 2y 0 1 − 6y 0 2 − y 3 = − 1 ⎪⎩ −2y 0 1 − y 3 = − 1 ⎪ 2 2 ⎨2y1 + y 2 + 2y 3 = 50; Vậy PATU của bài toán đối ngẫu là y = (–1, 0, 2, 5) với g(y0) = 25. 0 ⎪ 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 hình): ⎧ x1 + 2x 3 + x 4 ≥ 40 ⎪ ⎨ x1 + 4x2 + x 3 − 2x 4 ≥ 32 a) f (x) = x1 + 3x 2 + 4x 3 + x 4 → min b) f (x) = 4x1 + 5x2 + 3x 3 + 2x 4 → min ⎪ −2x + 3x − 3x − 2x ≤ 69 ⎩ 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 2 3 4 ⎩ 1 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 ⎧ y1 + y 2 − 2y 3 ≤ 4; 3 3 ⎪4y + 3y ≤ 2; ⎧ ⎪ 2 3 ⎪2 ⎨ 2 ⎪2y1 + y 2 − 3y 3 ≤ 2; ⎪ y1 + y 2 − y 3 ≥ 1; ⎪ 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 ⎪ 1 2 3 4 13 ⎨ ⎪ − 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 Bài 1 (2005). Giải bài toán: f(x) = – 4x1 – 3x2 → min ⎪ 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 ⎪ ⎩ Bài 2 (2007). a) Giải bài toán: f ( x) = 3 x1 − 2 x2 + 6 x3 + 4 x4 − 2 x5 → max xj ≥ 0 ( j = 1, 5) ⎧ x1 + 3 x3 = 36 ⎪ có bài toán đối ngẫu là ⎨ x2 + 2 x3 + 4 x4 = 52 ( P) ⎪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. Bài 4 (2009). a) Giải bài toán: f ( x) = 12 x1 + 15 x2 + 20 x3 → min ⎧ 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