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

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
Nội dung trích xuất từ tài liệu:
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 Ví dụ 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 giá tinh tôi ưu cua PACB xuât phat x0 ́ ́ ́ ̉ ́ ́ ∆ j ≤ 0, ∀j = 1,..., n ́ thì x0 là PATƯ + Nêu Ta có giá trị tôi ưu là f(x0). Bai toan kêt thuc. ́ ̀ ́ ́ ́ ∆k ∆k ́ ̀ ̣ mà > 0 thì x0 không phai là 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 mà ajk ≤ 0, với ∀i=1,…,m ∀j ∈ J o ́ ̀ ̣ ̣ Thì bai toan không giai được vì ham muc tiêu không bị chăn. ̀ ́ ̉ ̀ ̣ ̣ + Nêu với môi ∆ s > 0 đêu có it nhât ajs > 0 thì 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 > ...