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

Chia sẻ: Tranthai Minh | Ngày: | Loại File: XLS | Số trang:10

3
1.539
lượt xem
388
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:
Lưu

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
Đồng bộ tài khoản