Bài giảng Mô hình hóa, mô phỏng và tối ưu hóa trong quá trình hóa học - Chương: Phương pháp đơn hình
MÔ HÌNH – MÔ PHỎNG –
TỐI ƯU HÓA
PHƯƠNG PHÁP ĐƠN HÌNH
PHƯƠNG PHÁP ĐƠN HÌNH (SIMPLEX METHOD)
Năm 1947, nhà toán học George Bernard Danzig đưa ra
phương pháp đơn hình, ý tưởng cơ bản của phương
pháp là bắt đầu xét từ một phương án cực biên ban đầu
(phương án cơ bản chấp nhận được), ta xem nó có là
phương án tốt nhất hay chưa, nếu chưa là phương án tốt
nhất ta lần lươt xét đến các phương án cực biên liền kề
sao cho làm tăng giá trị hàm mục tiêu. Quá trình tiến
hành đến lúc thu được phương án tối ưu hoặc giá trị
hàm mục tiêu không hữu hạn
PHƯƠNG PHÁP ĐƠN HÌNH (SIMPLEX METHOD)
Phương pháp đơn hình có bốn bước:
• Bước 1. Thành lập một phương án cực biên.
• Bước 2. Xét xem phương án cực biên hiện hành đã là phương án
tối ưu hay chưa bằng dấu hiệu tối ưu. Nếu phương án cực biên
này là phương án tối ưu thì kết thúc. Ngược lại, nếu bài toán có
phương án mới tốt hơn thì sang bước 3.
• Bước 3. Xây dựng một phương án cực biên mới sao cho giá trị
hàm mục tiêu lớn hơn hoặc bằng giá trị hàm mục tiêu của phương
án cực biên trước đó.
• Bước 4. Quay về bước 2.
Thuật toán giải bài toán max
Bước lặp thứ nhất (bảng đơn hình thứ nhất)
1) Lập bảng đơn hình xuất phát
Vẽ bảng đơn hình và ghi vào đó các thành phần sau của bài toán
dạng chuẩn
· Dòng 1. Ghi các ẩn của bài toán (kể cả ẩn phụ)
· Dòng 2. Ghi các hệ số của các ẩn trong hàm mục tiêu
· Cột 1: Ghi tương ứng các hệ số của các ẩn cơ bản trong hàm mục
tiêu, ta gọi cột này là cột hệ số cơ bản.
· Cột 2. Ghi các ẩn cơ bản của bài toán theo thứ tự từ ẩn cơ bản thứ
nhất đến ẩn cơ bản cuối cùng, ta gọi cột này là cột ẩn cơ bản.
· Cột 3. Ghi các số hạng tự do của hệ ràng buộc chính theo thứ tự từ
trên xuống dưới, ta gọi cột này là cột phương án.
· Cột 4. Ghi ma trận điều kiện A của bài toán.
Thuật toán giải bài toán max
Tính hệ số ước lượng Δj của các ẩn xj (j=1,2,.. ,n ) và ghi tương
ứng vào dòng dưới cột 4, với Δj được tính theo công thức sau:
Δj =(cột1) (Aj ) – (hsxj)
(hsxj : hệ số của ẩn xj trong hàm mục tiêu).
Chú ý.
Nếu xj là ẩn cơ bản thì Δj = 0.
Tính trị số fo = (cột1) x (cột 3) và ghi dưới cột 3.
Thuật toán giải bài toán max
2) Xác định
Với bảng đơn hình vừa lập được thì phương án cơ bản xuất phát
x0 của bài toán được xác định như sau:
Cho các ẩn ở cột 2 nhận giá trị tương ứng ở cột 3, các ẩn còn lại
nhận giá trị 0.
Trị số của hàm mục tiêu tại phương án cơ bản xuất phát x0 là
f(xo)= fo
Thuật toán giải bài toán max
3) Đánh giá tính tối ưu của phương án cơ bản xuất phát
· Dấu hiệu tối ưu. Nếu hệ số ước lượng của các ẩn đều
không âm, Δj ≥0 j thì phương án cơ bản xuất phát x0 là
phương án tối ưu của bài toán.
Thuật toán kết thúc với kết luận: Bài toán có PATU là x0 và
GTTU là f (x0) .
· Dấu hiệu của bài toán không có PATU. Nếu có ẩn không
cơ bản xk có hệ số ước lượng âm và cột điều kiện Ak của ẩn
đó có các thành phần đều không dương, Δk<0 và aij ≤ 0, i thì
bài toán không có phương án tối ưu.
Thuật toán kết thúc với kết luận: Bài toán không có PATU.
Nếu không xảy ra cả hai trường hợp trên thì thuật toán tiếp tục
trong bước lặp thứ hai
Thuật toán giải bài toán max
Bước lặp thứ hai (Bảng đơn hình thứ hai)
1) Tìm ẩn đưa vào
Trong tất cả các Δj<0 ta chọn Δv<0 nhỏ nhất (ta đánh dấu * cho Δv<0
nhỏ nhất trong bảng). Khi đó, xv là ẩn mà ta sẽ đưa vào hệ ẩn cơ bản.
Cột Av được gọi là cột chủ yếu.
2) Tìm ẩn đưa ra
Thực hiện phép chia lần lượt các số của cột phương án cho các số
dương của cột chủ yếu và ghi các thương số λi đó vào cột cuối cùng.
Xác định λr= min{λi } (Ta đánh dấu * cho λr nhỏ nhất trong bảng). Khi
đó xr là ẩn mà ta đưa ra khỏi hệ ẩn cơ bản. Dòng có chứa xr được gọi
là dòng chủ yếu. Số dương nằm trên dòng chủ yếu và cột chủ yếu
được gọi là hệ số chủ yếu.
Chú ý. Nếu cột chủ yếu chỉ có một số dương thì số dương đó là hệ số
chủ yếu, dòng có số dương đó là dòng chủ yếu, ẩn nằm trên dòng chủ
yếu là ẩn được đưa ra.
Thuật toán giải bài toán max
3) Lập bảng đơn hình thứ hai
· Cột 2: Thay ẩn đưa ra bằng ẩn đưa vào, các ẩn cơ bản còn lại
giữ nguyên. Dòng có ẩn đưa vào gọi là dòng chuẩn.
· Cột 1: Thay hệ số của ẩn đưa ra bằng hệ số của ẩn đưa vào,
các hệ số của các ẩn cơ bản còn lại giữ nguyên.
Các thành phần còn lại được xác định theo dòng như sau
· Dòng chuẩn = Dòng chủ yếu chia cho hệ số chủ yếu.
· Dòng thứ i = Dòng thứ i (cũ) – aiv.dòng chuẩn. (aiv: số nằm trên
giao của dòng i và cột chủ yếu).
Các hệ số ước lượng và trị số của hàm mục tiêu trong bảng thứ
hai được tính và ghi như bảng thứ nhất.
4) Xác định và đánh giá phương án cơ bản thứ hai (như bước
lặp thứ nhất)
Thuật toán giải bài toán max
Giải
Bài toán trên có dạng chính tắc với các vế phải của các phương trình ràng buộc
trong (2) đều không âm.
Thuật toán giải bài toán max
Vì A chứa đủ 3 cột đơn vị e1 (cột 1), e2 (cột
3), e3 (cột 6) nên bài toán có dạng chuẩn
trong đó:
· Ẩn cơ bản thứ nhất: x1
· Ẩn cơ bản thứ hai:
· Ẩn cơ bản thứ ba:
x3
x6
Thuật toán giải bài toán max
c x1
x2
-5
6
x3
4
0
1
0
0
x4
-1
-2
1
x5
-6
-9
(3)
1
x6
0
0
0
1
0
ꢀi
b
2
1
0
0
0
2
4
0
x1
x3
x6
32
30
36
184
2
3
0
25
1
0
fo = 2.32 + 4.30 =184 .
Δ1 = Δ3 = Δ6 = 0
Δ2= 2.6 + 4.2 + 0.3+ 5 = 25
Δ4 = 2.(-2) + 4.1+ 0.0 +1 =1
Δ5 = 2.(-9) + 4.3+ 0.1+ 6 = 0
Trong bảng trên ta thấy Δj ≥0,j =1,..,6 nên bài toán có
PATU là x0 = (32,0,30,0,0,36) và fo =184 .
Thuật toán giải bài toán min
BÀI TOÁN MIN
Giải tương tự bài toán max với chú ý sau
· Điều kiện tối ưu: Δj ≤ 0, j
· Điều kiện không có PATU: Δk > 0 và aik ≤0, i
· Ẩn được chọn đưa vào: Ẩn ứng với Δk >0 lớn nhất.
BÀI TOÁN MAX
Dấu hiệu tối ưu. Δj ≥0, j
Dấu hiệu không có PATU. Δk<0 và aij ≤ 0, i.
Trong tất cả các Δj<0 Ẩn được chọn đưa vào: ta chọn
Δv<0 nhỏ nhất.
Thuật toán giải bài toán min
Giải
Bài toán trên có dạng chính tắc với vế phải của phương trình ràng buộc chính thứ hai
là – 9. Đổi dấu hai vế của phương trình này, ta đưa về bài toán sau
Thuật toán giải bài toán min
Vì A chứa đủ 3 cột đơn vị e1 (cột 2), e2 (cột 3), e3 (cột 5) nên
bài toán có dạng chuẩn trong đó:
· Ẩn cơ bản thứ nhất:
· Ẩn cơ bản thứ hai:
· Ẩn cơ bản thứ ba:
x2
x3
x5
Thuật toán giải bài toán min
c x1
6
x2
1
1
0
0
0
x3
1
0
1
0
0
x4
3
X5
1
X6
-7
ꢀi
b
1
1
1
x2
x3
x5
15
9
-1
-1
0
0
15
-2
0
2
4
2
1
26
-5
-2
0
Trong bảng 1 ta thấy tồn tại Δ6 = 3 > 0 và trên cột tương ứng có a13 =1 > 0 (
a23 = -2 và a23 = -3) nên ta chọn ẩn đưa ra là x6 , ẩn đưa vào là x2 , hệ số
chủ yếu là a13 =1.
Thuật toán giải bài toán min
c X1
6
x2
1
1
2
3
0
x3
1
0
1
0
0
0
1
0
0
x4
3
x5
1
0
0
1
0
0
0
1
0
x6
-7
ꢀi
b
1
1
1
x2
x3
x5
15
9
-1
-2
4
-1
0
15
2
2
26
15
39
47
-19
-5
-1
-4
1
-2
-1
-2
-1
1
-7
1
X6
X3
x5
1
-5
Tính các dòng ở bảng 2 bằng công thức sau:
Dòng chuẩn (dc) = dòng chủ yếu, d2 = d2 + 2dc,
d3 = d3 + 3dc.
Trong bảng 2 ta thấy tồn tại Δ4 =1 > 0 mà a14≤0 i = 1,2,3 nên bài toán min
đang xét vô nghiệm.
Thuật toán giải bài toán MAX
Bài toán trên có dạng chính tắc với vế phải của phương trình ràng buộc
trong (2) đều không âm. Ma trận hệ số ràng buộc là
A chứa đủ 3 cột đơn vị e1 (cột 1), e2 (cột 4), e3
(cột 5) nên bài toán có dạng chuẩn trong đó:
· Ẩn cơ bản thứ nhất: x1
· Ẩn cơ bản thứ hai: x4
· Ẩn cơ bản thứ ba: x5
Thuật toán giải bài toán MAX
c x1
-2
1
x2
6
x3
4
x4
-2
0
x5
3
0
0
1
0
ꢀi
B
-2
-2
3
x1
x4
x5
52
60
36
2
(4)
2
52/4*
60/2
0
4
1
0
3
0
0
-116 0
-9
-16* 0
Trong bảng 1 ta thấy tồn tại Δj < 0: Δ2 =-9 và Δ3 =-16 và trên cột
tương ứng có hệ số > 0 nên ta chọn ẩn đưa vào là x3 do (Δ3 =-
16 âm nhỏ nhất),
khi đó trên cột tương ứng có các hệ số dương là a13 =4; a23 = 2
nên ta lập các tỉ số ꢀ1=52 / 4, ꢀ2= 60 / 2 . Ta chọn ꢀ1= 52 / 4
nhỏ nhất và ẩn đưa ra là x1 , hệ số chủ yếu là a13 = 4 .
Sau đó biến đổi bảng I bằng các phép biến đổi sau:
dc = dcy/4 ,
d2 = d2 - 2dc,
d3 = d3.
Thuật toán giải bài toán MAX
c x1
-2
1
x2
6
x3
4
x4
-2
0
x5
3
0
0
1
0
0
ꢀi
B
-2
-2
3
x1
x4
x5
52
60
36
2
(4)
2
52/4*
60/2
0
4
1
0
3
0
0
-116 0
-9
½
-16* 0
4
x3
13
¼
1
0
13/(1/
2)
-2
3
x4
x5
34
36
92
-1/2 (3)
0
0
0
1
0
0
0
1
0
0
0
1
0
34/3*
36/3
0
4
3
-1
0
4
6
3
x3
x2
x5
22/3 1/3
-1/6 0
34/3 -1/6 1
1/3
-1
0
1
0
2
½
0
310/3 23/6 0
1/3
Tải về để xem bản đầy đủ
64 trang
25520
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mô hình hóa, mô phỏng và tối ưu hóa trong quá trình hóa học - Chương: Phương pháp đơn hình", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mo_hinh_hoa_mo_phong_va_toi_uu_hoa_trong_qua_trinh.pdf
