Tính chất chung của bài toán quy hoạch tuyến tính

Chia sẻ: Lan Lan | Ngày: | Loại File: PPT | Số trang:23

Thêm vào BST

Báo xấu

136
lượt xem 14
download

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

Giải hệ phương trình tuyến tính tổng quát Các bước giải: Lập bảng các hệ số cho hệ đã cho Xác nhận các ẩn cơ sở đã có 3. Tìm thêm ẩn cơ sở mới Chọn ẩn cơ sở xj (xj chưa là ẩn cơ sở) Chọn phần tử chủ yếu aịj trên cột j (điều kiện aij khác 0) Tính các hệ số cho bảng mới theo quy tắc hình chữ nhật.

Chủ đề:

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

Lưu

Nội dung Text: Tính chất chung của bài toán quy hoạch tuyến tính

BÀI 2
́ lai: Nhăc ̣ •Hệ phương trình tuyến tính: •Hệ cơ bản •Ẩn cơ bản
• Giải hệ phương trình tuyến tính tổng quát Các bước giải: 1. Lập bảng các hệ số cho hệ đã cho 2. Xác nhận các ẩn cơ sở đã có 3. Tìm thêm ẩn cơ sở mới Chọn ẩn cơ sở xj (xj chưa là ẩn cơ sở) Chọn phần tử chủ yếu aịj trên cột j (điều kiện aij khác 0) Tính các hệ số cho bảng mới theo quy tắc hình chữ nhật.
Ví du:̣ giaỉ hệ phương trinh: ̀ 2 x1 + x2 − 3x3 + x4 = 2 − x1 + 3 x2 + x3 − 2 x4 = −1
Ví du:̣ giaỉ hệ phương trinh: ̀ 2 x1 + 4 x2 + 2 x3 = 15 x1 + 5 x2 + 3 x3 = 17 4 x1 + 5 x2 + 4 x3 = 27
GIẢI: b x1 x2 x3 [2] 4 2 15 1 5 3 17 27 4 5 4 15/2 1 2 1 19/2 0 3 [2] -3 0 -3 0 11/4 1 1/2 0 19/4 0 3/2 1 -3 0 [-3] 0 1 0 0 9/4 0 0 1 13/4 0 1 0 1
Tìm nghiệm cơ bản không âm Thuật toán: 1. Làm bi>=0 với ∀I 2. Lập bảng hệ số 3. Xác nhận các ẩn cơ sở đã có Nếu là hệ cơ bản viết nghiệm cơ bản không âm Nếu hệ không cơ bản chuyển qua bước 4 4. Chọn ẩn cơ sở mới -Chọn xj. -Chọn phần tử chủ yếu -Xét �bk � br min � �= akj > 0 a arj kj
-Lấy arj làm phần tử chủ yếu -Tính các hệ số cho bảng mới theo quy tắc hình chữ nhật. -Lặp lại thuật toán từ bước 3.  chú ý: nếu như trong quá trình tìm nghiệm cơ bản không âm xuất hiện một dòng nào đó có hệ số tự do b i>0 và aij ≤0 với mọi j thì phương trình đó không có nghiệm không âm do đó cả hệ không có nghiệm không âm.
Ví dụ: tìm nghiệm cơ bản không âm của hệ phương trình tuyến tính sau: −2 x1 − x2 + 3x3 + x4 = 1 − x1 + 2 x2 + x3 + 2 x4 = 5
́ tinh 1. Cac ́ chât́ chung cua ̉ baì toan ́ QHTT : ́ * Tinh chât́ 1: sự tôn ̀ taị PACB cua ̉ baì toan. ́ ́ baì toan Nêu ́ QHTT có phương an ́ và hang ̣ cua ̉ ma trân ̣ hệ rang ̀ buôc ̣ băng ̀ n (n là số biên) ́ thì baì toan ́ có PACB. Hệ quả: Bài toán QHTT dạng chính tắc nếu có phương án thì sẽ có PACB.
́ * Tinh chât́ 2: sự tôn ̀ taị phương an ́ tôí ưu cua ̉ baì toan. ́ Baì toan ́ QHTT có PATƯ khi và chỉ khi nó có phương an ́ và trị số ham ̀ muc ̣ tiêu bị chăn ̣ dưới (trên) khi f(x) => ̣ phương an. min (max) trên tâp ́ Hệ quả:  Nếu bài tóan có PACB và thỏa điều kiện trên thì sẽ có PACB tối ưu.  Nếu bài toán QHTT dạng chính tắc có PATƯ thì sẽ có một PACB là PATƯ. ́ * Tinh chât́ 3: số phương an ́ cực biên cua ̉ baì toan ́ dang ̣ ́ tăc chinh ́ là hữu han. ̣
Ví dụ: tìm tất cả các phương án cực biên của bài toán QHTT có hệ ràng buộc: x1 + 2 x2 + 4 x4 = 4 3 x2 + x3 + 2 x4 = 3 xj 0, ∀j = 1,4
xB b x1 x2 x3 x4 x1 4 1 2 0 4 x3 3 0 3 1 2 x1 2 1 0 -2/3 8/3 x2 1 0 1 1/3 2/3 x4 ¾ 3/8 0 -1/4 1 x2 ½ -1/4 1 ½ 0 x4 1 ¼ ½ 0 1 x3 1 -1/2 2 1 0
2. Phương phap ́ đơn hinh̀ cho baì toan ́ QHTT: A. Thuâṭ toan ́ đơn hinh̀ cho baì toan ́ QHTT dang ̣ chuân: ̉ Ví dụ 1: Giaỉ baì toan ́ QHTT sau băng̀ phương phap ́ đơn ̀ hinh: f ( x ) = 2 x1 − x2 + 2 x3 + x4 min x1 + 2 x2 + x5 =2 −3 x1 + 4 x2 + x4 + x6 = 20 x1 + 2 x2 + x3 + 3x4 = 18 xj 0 ( j = 1,...,6 )
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 a1m+1 a1s a1n c2 x2 b2 0 1 0 0 a2m+1 a2s a2n … … … cr xr br … … … … 0 0 1 0 ar n+1 ars ar n cm xm bm … 0 0 0 1 am∆m+1 m+1 a ∆ sa ∆ n ms mn 0 0 0 0  ∆ j = f(x) (côṭ 1)f(x(Aj) 0) - cj f(x0) = (côṭ 1) * (côṭ 3) Chú y:́ nêu ́ xj là ân ̉ cơ ban ̉ thì ∆j =0
Bước 2: Đanh ́ giá tinh ́ tôí ưu cua ̉ PACB xuât́ phat́ x0 ́ + Nêu ∆k 0, ∀k thì x0 là PATƯ Ta có giá trị tôí ưu là f(x0). Baì toan ́ kêt́ thuc. ́ ∆k ∆k ́ tôn + Nêu ̀ taị mà > 0 thì x0 không phaỉ là PATƯ chuyên̉ sang bước 3. Bước 3: Kiêm ̉ tra tinh ́ không giaỉ được cua ̉ baì toan. ́ + Nêu ̀ taị môṭ ∆ k > 0 mà ajk 0, với ∀j J o (J0 là tâp ́ tôn ̣ chỉ số cơ sở cua ̉ phương an ́ x0) Thì baì toan ́ không giaỉ được vì ham ̀ muc ̣ tiêu không bị ̣ chăn. ∆k ́ với môĩ + Nêu ̀ có it́ nhât́ ajk > 0 thì chuyên > 0 đêu ̉ sang bước 4.
Bước 4: điêu ̀ chinh ̉ PACB. + Choṇ vectơ đưa vao ̀ cơ sở. ̀ max ∆ k với ∆ k > 0. Tim Giả sử max ∆ k = ∆ s thì vectơ As dược đưa vao ̀ cơ sở. o xj ́ Tinh θo = min a js o xr Giả sử: θ o = ( r �J o , ars > 0 ) ars thì vectơ Ar bị loaị khoỉ cơ sở, phân ̀ tử ars goị là phân ̀ tử truc ̣ cua ̉ bang. ̉
Bước 5: lâp ̣ bang ̉ đơn hinh ̀ thứ 2. Ở vị trí xr ghi xs và ghi cs thay cr ́ cac Tinh ́ dong ̀ trong bang ̉ mới (từ dong ̀ thứ ba trở đi) - Để tinh ́ dong ̀ ứng với vectơ đưa vao ̀ (ứng với xs) lây ́ ̀ ứng với vectơ loaị ra (ứng với xr) trong bang dong ̉ cũ ̀ tử truc. chia phân ̣ Dong ̀ nay ̀ được goị là dong ̀ chuân. ̉ - Để tinh ́ dong ̀ ứng với xj ta sử dung ̣ quy tăc ́ hinh ̀ chữ ̣ nhât. - Để tinh ́ dong ̀ cuôí trong bang ̉ ta cung ̃ sử dung ̣ quy tăc ́ ̀ chữ nhât. hinh ̣  Sau bảng đơn hình mới ta có PACB mới x1. Đối với x1 quay trở lại bước 1 và lặp lại quá trình sau hữu hạn
Ví dụ 2: f ( x ) = 6 x1 + x2 + x3 + 3 x4 + x5 − 7 x6 + 7 min -x1 + x2 − x4 + x6 = 15 2x1 − x3 + 2 x4 = −9 4x1 + 2 x4 + x5 − 3 x6 = 2 xj 0 ( j = 1,...,6 )
b) Trường hợp baì toan ́ Max: Baì toan ́ 1: f(x) max. ́ 1: Cach Giaỉ baì toan ́ 2: g(x) = - f(x) min gmin = g(x*) thì baì toan ́ 1 có PATƯ là x* và fmax = - g(x*)