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

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

Thêm vào BST

Báo xấu

2.110
lượt xem 446
download

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ủ đề:

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

Lưu

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

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
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
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) ́ ́
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
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
Page 6
Page 7
Page 8 12 40
Page 9
Page 10