Một số bài toán đơn hình

Chia sẻ: huonggiang08

Tài liệu tham khảo Một số bài toán đơn hình có kèm lời giải giúp các bạn học và ôn toán tốt hơn

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Một số bài toán đơn hình

 

  1. Page 1 Bai toan đơn hinh ̀ ́ ̀ Câu1: 4 ̉ Điêm x1 + x2 + x3  min x1 − x4 − 2 x6 = 5   x 2 + 2 x 4 − 3 x5 + x 6 = 3  x3 + 2 x 4 − 5 x5 + 6 x 6 = 5 xj ≥ 0 ,j = 1..6  Bài toán có dạng chuẩn, các biến cố độc lập x1,x2,x3 nên phương án cực biên x▫ = (5;3;5;0;0;0) cơ sở jo = {A1;A2;A3} 0.5 Bảng đơn hình Hệ số jo Cơ sở jo Phương 1 1 1 0 0 0 ́ an x1 x2 x3 x4 x5 x6 1 x1 5 1 0 0 -1 0 -2 0.25 1 x2 3 0 1 0 2 -3 1 0.25 1 x3 5 0 0 1 2 -5 6 0.25 f(x) 13 0 0 0 3 -8 5 0.25 1 x1 6.7 1.0 0.0 0.3 -0.3 -1.7 0.0 0.25 1 x2 2.2 0.0 1.0 -0.2 1.7 -2.2 0.0 0.25 0 x6 0.8 0.0 0.0 0.2 0.3 -0.8 1.0 0.25 f(x) 8.8 0.0 0.0 -0.8 1.3 -3.8 0.0 0.25 1 x1 7.1 1 0.2 0.3 0 -2.1 0 0.25 0 x4 1.3 0 0.6 -0.1 1 -1.3 0 0.25 0 x6 0.4 0 -0.2 0.2 0 -0.4 1 0.25 f(x) 7.1 0 -0.8 -0.7 0 -2.1 0 0.25 Vậy phương án tối ưu của bài toán là (7,1;0;0;1,3;0;0,4) Minf(x)=7.1 Câu 2: 2 x1 + 4 x 2 + x3 + x 4 → Max x1 + 3 x 2 + x4 ≤ 4  2 x1 + x 2 ≤3  x 2 + 4 x3 + x 4 ≤ 3  x j ≥ 0; j := 1..; 4 Đưa về bai toan dang chuân sau: ̀ ́ ̣ ̉ − 2 x1 − 4 x 2 − x3 − x 4 → Min x1 + 3 x 2 + x 4 + x5 = 4  2 x1 + x 2 + x6 = 3  0.25  x 2 + 4 x3 + x 4 + x7 = 3 0.25 x j ≥ 0; j := 1..;7 Bảng đơn hình
  2. Page 2 hệ số jo cơ sở jo Phương -2 -4 -1 -1 0 0 0 ́ an x1 x2 x3 x4 x5 x6 x7 0 x5 4 1 3 0 1 1 0 0 0.25 0 x6 3 2 1 0 0 0 1 0 0 x7 3 0 1 4 1 0 0 1 0.25 f(x) 0 2 4 1 1 0 0 0 0.25 -4 x2 1.3 0.3 1.0 0.0 0.3 0.3 0.0 0.0 0.25 0 x6 1.7 1.7 0.0 0.0 -0.3 -0.3 1.0 0.0 0 x7 1.7 -0.3 0.0 4.0 0.7 -0.3 0.0 1.0 0.25 f(x) -5.3 0.7 0.0 1.0 -0.3 -1.3 0.0 0.0 0.25 -4 x2 1.3 0.3 1.0 0.0 0.3 0.3 0.0 0.0 0 x6 1.7 1.7 0.0 0.0 -0.3 -0.3 1.0 0.0 0.25 -1 x3 0.4 -0.1 0.0 1.0 0.2 -0.1 0.0 0.3 0.25 f(x) -5.75 0.75 0 0 -0.5 -1.25 0 -0.25 0.25 -4 x2 1 0 1 0 0.4 0.4 -0.2 0 -2 x1 1 1 0 0 -0.2 -0.2 0.6 0 0.25 -1 x3 0.5 0 0 1 0.15 -0.1 0.05 0.25 0.25 -6.5 0.0 0.0 0.0 -0.4 -1.1 -0.5 -0.3 0.25 Vậy phương án tối ưu của bài toán là x= (1;1;0.5;0.0;0;0) 0.25 Maxf(x)=6.5 0.25 Câu3. ̉ ̀ ́ Giai bai toan QHTT sau: f ( x ) = 2 x1 − 8 x 2 + x3 → Min 6 x1 + 8 x 2 − 2 x3 ≤ 1  2 x1 − 8 x 2 + x3 ≤ 3 − x − 5 x − x ≤ 2  1 2 3 f ( x ) → Min 6 x1 + 8 x 2 − 2 x 3 + x 4 =1  0.25 2 x1 − 8 x 2 + x3 + x5 = 3 − x − 5 x − x + x6 = 2  1 2 3 x j ≥ 0; j = 1;.. 6 0.25 Bảng đơn hình hệ số jo cơ sở jo Phương 2 -8 1 0 0 0 ́ an x1 x2 x3 x4 x5 x6 0 x4 1 6 8 -2 1 0 0 0.25 0 x5 3 2 -8 1 0 1 0 0.25 0 x6 2 -1 -5 -1 0 0 1 0.25 f(x) 0 -2 8 -1 0 0 0 0.25 1 x2 0.13 0.75 1.00 -0.25 0.13 0.00 0.00 0.25 0 x5 4 8 0 -1 1 1 0 0.25 0 x6 2.63 2.75 0.00 -2.25 0.63 0.00 1.00 0.25 f(x) -1 -8 0 1 -1 0 0 0.25 Do ∆3 > 0 va x j 3 ≤ 0 ∀j ∈ J 0 Nên bai toan không giai đươc ̀ ́ ̉ 1.5 Câu 9: 1 f ( x) = 2 x1 + 4 x 2 + x3 − 3x 4 → Min 2 2 x1 + 2 x 2 + 3 x3 + 3x 4 ≤ 50  4 x1 + 8 x 2 + 2 x3 + 3x 4 = 80 4 x + 4 x + x + 2 x = 40  1 2 3 4 x j ≥ 0; j = 1;..; 4
  3. 1 Page 3 f ( x) = 2 x1 + 4 x 2 + x3 − 3x 4 → Min 2 2 x1 + 2 x 2 + 3 x3 + 3x 4 ≤ 50  4 x1 + 8 x 2 + 2 x3 + 3x 4 = 80 4 x + 4 x + x + 2 x = 40  1 2 3 4 x j ≥ 0; j = 1;..; 4 Đưa về bai toan: ̀ ́ 1 f ( x ) = 2 x1 + 4 x 2 + x3 − 3x 4 → Min 2 2 x1 + 2 x 2 + 3 x3 + 3 x 4 + x5 = 50  4 x1 + 8 x 2 + 2 x3 + 3 x 4 + x g 2 = 80  4 x1 + 4 x 2 + x3 + 2 x 4 + x g 3 = 40 x j ≥ 0; j = 1;..; 4 x5 ≥ 0 ̀ ́ ̣ Bai toan phu: P ( x; x g ) = x g1 + x g 2 → Min 2 x1 + 2 x 2 + 3 x3 + 3 x 4 + x5 = 50 0.25  4 x1 + 8 x 2 + 2 x3 + 3 x 4 + x g 2 = 80  4 x1 + 4 x 2 + x3 + 2 x 4 + x g 3 = 40 0.25 x j ≥ 0; j = 1;..;4 x5 ≥ 0 ; x g1 ≥ 0; x g 2 ≥ 0 Bảng đơn hình 2 4 0.5 -3 0 0 0 hệ số jo cơ sở jo Phương 0 0 0 0 0 1 1 ́ an x1 x2 x3 x4 x5 xg2 xg3 0 x5 50 2 2 3 3 1 0 0 1 xg2 80 4 8 2 3 0 1 0 1 xg3 40 4 4 1 2 0 0 1 P(x) 120 8 12 3 5 0 0 0 0 x5 30 1 0 2.5 2.25 1 0 0 x2 10 0.5 1 0.25 0.375 0 0 1 xg3 0 2 0 0 0.5 0 1 P(x) 0 2 0 0 0.5 0 0 0 x5 30 0 0 2.5 2 1 4 x2 10 0 1 0.25 0.25 0 2 x1 0 1 0 0 0.25 0 0 0.5 P(x) 0 0 0 0 0 0 f(x) 40 0 0 0.5 4.5 0 0 x5 30 -8 0 2.5 0 1 4 x2 10 -1 1 0.25 0 0 -3 x4 0 4 0 0 1 0 f(x) 40 -18 0 0.5 0 0 x3 12 -3.2 0 1 0 0.4 x2 7 -0.2 1 0 0 -0.1 x4 0 4 0 0 1 0 f(x) 34 -16.4 0 0 0 -0.2 Phương an tôi ưu: x= ( 0;7;12;0;0) ́ ́
  4. Page 4 Min f(x)=34 ́ ́ Cach khac: hệ số jo cơ sở jo Phương 2 4 0.5 -3 0 1 1 ́ an x1 x2 x3 x4 x5 xg1 xg2 0 x5 50 2 2 3 3 1 0 0 0.25 1 xg1 80 4 8 2 3 0 1 0 1 xg2 40 4 4 1 2 0 0 1 0.25 P(x) 120 6 8 2.5 8 0 0 0 0.25 0 x5 30 1 0 2.5 2.25 1 0.25 4 x2 10 0.5 1 0.25 0.38 0 1 xg2 0 2 0 0 0.5 0 0.25 f(x) 40 2 0 0.5 5 0 0.25 0 x5 30 -8 0 2.5 0 1 4 x2 10 -1 1 0.25 0 0 0.25 -3 x4 0 4 0 0 1 0 0.25 f(x) 40 -18 0 0.5 0 0 0.25 0.5 x3 12 -3.2 0 1 0 0.4 4 x2 7 -0.2 1 0 0 -0.1 0.25 -3 x4 0 4 0 0 1 0 0.25 f(x) 34 -16.4 0 0 0 -0.2 0.25 Vậy phương án tối ưu của bài toán là ( 0 ; 7 ; 12 ; 0 ; 0) 0.25 Max f(x) = 34 0.25 Câu 10: f ( x ) = 2 x1 + 3 x 2 − 5 x 3 → Max  − 4 x1 + x 2 + 2 x3 ≥ 12   1 − 2 x1 + x 2 + x3 ≤ 8  2  3 − 2 x1 + 2 x 2 + x3 = 20  x j ≥ 0; j = 1;..; 3 p ( x ) = −2 x1 − 3 x 2 + 5 x3 → Min  − 4 x1 + x 2 + 2 x3 − x 4 + x g1 = 12   1 − 2 x1 + x 2 + x 3 + x 5 = 8  2  3 − 2 x1 + 2 x 2 + x 3 + x g 2 = 20  x j ≥ 0; j = 1;..; 3 -2 -3 5 0 0 0 0 hệ số jo cơ sở jo Phương 0 0 0 0 0 1 1 ́ an x1 x2 x3 x4 x5 xg1 xg2 1 xg1 12 -4 1 2 -1 0 1 0 0 x5 8 -2 0.5 1 0 1 0 0 1 xg2 20 -2 1.5 1 0 0 0 1 P(x) 32 -6 2.5 3 -1 0 1 1
  5. Page 5 0 x3 6 -2 0.5 1 -0.5 0 0.5 0 0 x5 2 0 0 0 0.5 1 0 1 xg2 14 0 1 0 0.5 0 1 P(x) 14 0 1 0 0.5 0 1 Do ∆2 > 0; x j 2 > 0 ∀j Bài toán không giải đươc Bài 11 f ( x) = 4 x1 + x 2 + x3 + 3 x 4 → Min 2 x 2 + x3 + x 4 = 16 2 x 2 + x3 + x 4 = 16 4 x2 + 2 x5 ≤ 8 4 x2 + 2 x5 + x 6 = 8 x1 + x 2 + 2 x 4 + x5 = 2 x1 + x 2 + 2 x 4 + x5 =2 xj ≥ 0 hệ số jo cơ sở jo Phương 4 1 1 3 0 0 ́ an x1 x2 x3 x4 x5 x6 1 x3 16 0 2 1 1 0 0 0 x6 8 0 4 0 0 2 1 4 x1 2 1 1 0 2 1 0 24 0 5 0 6 4 0 x3 15 -0.5 1.5 1 0 -0.5 0 10 x6 8 0 4 0 0 2 1 2 x4 1 0.5 0.5 0 1 0.5 0 2 18 -3 2 0 0 1 0 x3 12 -2 0 1 -3 -2 0 x6 0 -4 0 0 -8 -2 1 x2 2 1 1 0 2 1 0 14 -5 0 0 -4 -1 0
  6. Page 6
  7. Page 7
  8. Page 8 12 40
  9. Page 9
  10. Page 10
Theo dõi chúng tôi
Đồng bộ tài khoản