Phương pháp đơn hình

Chia sẻ: Nguyen Van Thuy | Ngày: | Loại File: PPT | Số trang:32

Thêm vào BST

Báo xấu

780
lượt xem 191
download

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

Có một số phương pháp khác nhau để giải bài toán Qui hoạch tuyến tính : phương pháp hình học , phương pháp phân tích sự biến động của hàm mục tiêu và phương pháp đơn hình . Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà với mỗi Dk 0 đều tồn tại xjk 0 đối với bài toán f(x) ® min thì ta có thể điều chỉnh PACB x0 để chuyển sang một PACB mới 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: Phương pháp đơn hình

PHƯƠNG PHÁP ĐƠN HÌNH 1
Các định lí cơ bản ∆ k = ∑ c j x jk − ck Ta gọi j∈J 0 Là ước lượng của biến xk theo cơ sở J0 Định lí1: ( Dấu hiệu tối ưu của phương án cực biên) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chuẩn mà ∆ k≤ 0 (∀k∉J0 ) đối với bài toán f(x) ⇒ min thì x0 là phương án tối ưu 2
Định lí2: ( Dấu hiệu bài toán không giải được ) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà tồn tại ∆ k > 0 mà xjk ≤ 0 (∀k∉J0 ) đối với bài toán f(x) ⇒ min hoặc: tồn tại ∆ k
Định lí3: ( Dấu hiệu điều chỉnh PACB) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà với mỗi ∆ k >0 đều tồn tại xjk > 0 đối với bài toán f(x) → min thì ta có thể điều chỉnh PACB x0 để chuyển sang một PACB mới tốt hơn 4
2. Phương phap đơn hinh cho bai toan QHTT: ́ ̀ ̀ ́ A. Thuât toan đơn hinh cho bai toan QHTT dang chuân: ̣ ́ ̀ ̀ ́ ̣ ̉ 5
f ( x ) = 2 x1 + 3 x2 + 3 x3 + 8 x4 + 4 x5 → min Ví dụ 2x + x + 7 x5 = 16 0 2 0 1 7  2 4  5x2 + x3 + 2 x5 = 4 Ta cã A =  0 5 1 0 2     x1 + x2 + 2 x5 = 8  1 1 0 0 2    x j ≥ 0 ( j = 1,..., 5 ) Bảng đơn hình xuất phát Hệ số Ẩn cơ P Án 2 3 3 8 4 bản x1 x2 x3 x4 x5 8 x4 16 0 2 0 1 7 3 x3 4 0 5 1 0 2 2 x1 8 1 1 0 0 2 6
Hệ số Ẩn cơ Ph Án 2 3 3 8 4 bản x1 x2 x3 x4 x5 8 x4 16 0 2 0 1 7 3 4 0 5 1 0 2 x3 2 8 1 1 0 0 2 x1 156 0 30 0 0 62 f(x0) 8 x4 2 0 -31/2 -7/2 1 0 4 0 5/2 1/2 0 1 2 x5 2 4 1 -4 -1 0 0 x1 32 0 -125 -31 0 0 f(x’0) Phương án tối ưu là x0 = (4,0,0,2,2); f(x0) = 32 7
a. Trường hợp bai toan min: ̀ ́ ̣ ́ Thuât toan: Bước 1: lâp bang đơn hinh xuât phat. ̣ ̉ ̀ ́ ́ Hệ số Cơ sở Phương án c1 c2 …..cr ………. cm cm+1 …..cs…..cn c1 x1 b1 1 0 0 0 x1m+1 x1s x1n c2 x2 b2 0 1 0 0 x2m+1 x2s x2n … … … … cr xr br 0 0 1 0 xr n+1 xrs xr n … … … cm xm bm … x∆ m+1 ∆∆ 0 0 0 1 xmss xmn n m m+1 0 0 0 0 f(x) f(x0) 8
Bước 2: Đanh giá tinh tôi ưu cua PACB xuât phat x0 ́ ́ ́ ̉ ́ ́ ∆ j ≤ 0, ∀j = 1,..., n ́ thì x0 là PATƯ + Nêu Ta có giá trị tôi ưu là f(x0). Bai toan kêt thuc. ́ ̀ ́ ́ ́ ∆k ∆k ́ ̀ ̣ mà > 0 thì x0 không phai là PATƯ ̉ + Nêu tôn tai chuyên sang bước 3. ̉ Bước 3: Kiêm tra tinh không giai được cua bai toan. ̉ ́ ̉ ̉ ̀ ́ + Nêu tôn tai môt ∆ s > 0 mà ajk ≤ 0, với ∀i=1,…,m ∀j ∈ J o ́ ̀ ̣ ̣ Thì bai toan không giai được vì ham muc tiêu không bị chăn. ̀ ́ ̉ ̀ ̣ ̣ + Nêu với môi ∆ s > 0 đêu có it nhât ajs > 0 thì chuyên sang ́ ̃ ̀ ́ ́ ̉ bước 4. 9
Bước 4: điêu chinh PACB. ̀ ̉ + Chon vectơ đưa vao cơ sở. ̣ ̀ Tim ∆ v= max{∆ j| ∆ j >0 ∀j= 1,2,..n} gọi xv là ấn thay thế (ẩn cơ ̀ bản mới) ́ Tinh br bi = min ∀i : aiv > 0 arv aiv Khi đó xr gọi là ẩn bị loại. Phần tử arv gọi là phần tử trục xoay. Lập bảng đơn hình mới nối tiếp vào bảng đơn hình cũ Tính lại hệ số mới và quay về bước 2 10
-Cách tính hệ số mới thực hiện như sau: -Cột r chuyển sang cột s các cột khác giữ nguyên - Chia tất cả các phần tử của hàng r cho phần tử trục ta được một hàng mới gọi là hàng chuẩn -Muốn có hàng i mới i ≠ 0 ta lấy phần tử trên hàng i cũ trừ đi tích của hàng chuẩn với aiv -Muốn có hàng cuối gồm f(x0) và ∆ j ta tính tương tự như trên hay tính như bước 1 -Sau bảng đơn hình mới ta có PACB mới x’0. Đối với x’0 quay trở lại bước 1 và lặp lại quá trình sau hữu hạn bước ta có kết luận bài toán. 11
b) Trường hợp bai toan Max: ̀ ́ Bai toan 1: f(x) → max. ̀ ́ ̉ ̀ ́ Giai bai toan 2: g(x) = - f(x) → min gmin = g(x*) thì bai toan 1 có PATƯ là x* và fmax = - g(x*) ̀ ́ Chú ý: f(x)max = - g(x)min 12
f ( x ) = x1 − 3 x2 + 3 x3 − x4 → max Ví dụ: 4x + 3 x − 3 x + x4 ≥ 12 1 2 3   -x1 + x2 − x3 ≤ 5   x1 + 5 x2 − 5 x3 ≤ 6  x j ≥ 0 ( j = 1,..., 4 ) g(x) =-f ( x ) = −x1 + 3 x2 − 3 x3 + x4 → min ⇔ f(x) → max 4x + 3 x − 3x + x4 − x5 = 12 1 2 3    -x1 + x2 − x3 =5 +x6   x1 + 5 x2 − 5 x3 + x7 = 6  x j ≥ 0 ( j = 1,..., 7 ) 13
Bảng đơn hình xuất phát Hệ Ẩn cơ P Án -1 3 -3 1 0 00 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 5 -5 0 0 0 1 0 x7 6 1 -1 x1 3 1 3/4 -3/4 1/4 -1/4 0 -1 0 0 -f(x0) 12 5 0 0 0 0 0 x6 0 x7 -f(x0) 14
Hệ Ẩn cơ P Án -1 3 -3 1 0 00 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 5 -5 0 0 0 1 0 x7 6 1 -1 x1 3 1 3/4 -3/4 1/4 -1/4 0 -1 0 0 -f(x0) 12 5 0 0 0 0 0 x6 8 0 7/4 -7/4 1/4 -1/4 1 0 15
Hệ Ẩn cơ P Án -1 3 -3 1 0 00 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 5 -5 0 0 0 1 0 x7 6 1 3 1 3/4 -3/4 1/4 -1/4 0 0 -1 x1 -f(x0) 12 5 0 0 0 -1 0 0 0 x6 8 0 7/4 -7/4 1/4 -1/4 1 0 3 0 17/4 -17/4 -1/4 1/4 0 1 0 x7 -f(x0) 16
Hệ Ẩn cơ P Án -1 3 -3 1 0 00 số bản x1 x2 x3 x4 x5 x6 x7 1 x4 12 4 3 -3 1 -1 0 0 0 x6 5 -1 1 -1 0 0 1 0 5 -5 0 0 0 1 0 x7 6 1 3 1 3/4 -3/4 1/4 -1/4 0 0 -1 x1 -f(x0) 12 5 0 0 0 -1 0 0 0 x6 8 0 7/4 -7/4 1/4 -1/4 1 0 3 0 17/4 -17/4 -1/4 1/4 0 1 0 x7 -3 0 -15/4 15/4 -5/4 1/4 0 0 -f(x0) Do ∆ 3 > 0 x3 =(-3/4;-7/4;-17/4) < 0 nên bài toán có hàm m ục tiêu ko giải được 17
Giải bài toán QHTT sau f ( x ) = 2 x1 + 6 x2 − 5 x3 + x4 + 4 x5 →min x −8 x + x5 =14 1 2   -3x2 + x3 − x5 = 2   + x4 − 2 x5 = 3 -2x2   x j ≥ 0 ( j =1,..., 5 ) Bảng ĐH xuất phát Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 14 x1 1 -8 0 0 1 0 -3 1 0 -1 -5 2 x3 0 0 1 -2 -2 1 3 x4 18 0 -9 0 0 1 f(x0)
Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 1 -8 0 0 1 14 -5 0 -3 1 0 -1 2 x3 1 0 0 1 -2 -2 3 x4 21 0 -9 0 0 1 f(x0) 4 14 1 -8 0 0 1 x5 -5 x3 1 x4 f(x’0) 19
Hệ số Ẩn cơ Ph Án 2 6 -5 1 4 bản x1 x2 x3 x4 x5 2 x1 1 -8 0 0 1 14 -5 0 -3 1 0 -1 2 x3 1 0 0 1 -2 -2 3 x4 21 0 -9 0 0 1 f(x0) 4 14 1 -8 0 0 1 x5 -5 16 1 -11 1 0 0 x3 1 x4 f(x’0) 20