Một số phương pháp giải bài toán tối ưu hóa và qui hoạch tuyến tính
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (346.76 KB, 74 trang )
GiẢI BÀI TOÁN ĐƠN HÌNH
Cho bài toán đơn hình sau
Z=
4x1 + 6x2 +8x3 -> MAX
x1 + 2x2 – 3x3 ≤ 12
3x1 + x2 +x3 ≤ 4
2x1 + 2x2 +5x3 ≤ 5
xj ≥ 0 , j = 1,3
B1- chuyển về bài toán phụ
Z=
4x1 + 6x2 +8x3 -> MAX
x1 + 2x2 – 3x3 + x4
= 12
3x1 + x2 + x3 + + x5
=4
2x1 + 2x2 + 5x3 +
+ x6 = 5
xj ≥ 0 , j = 1,6
B2- Nhận xét vài câu như bên dưới:
Trong đó x4, x5, x6 là 3 biến phụ.
NX: BT phụ có dạng chuẩn, có 3 biến cơ sở là x4, x5, x6
Lập bảng đơn hình
20/4/2012
1
GiẢI BÀI TOÁN ĐƠN HÌNH
Z=
4x1 + 6x2 +8x3 + 0x4 + 0x5 +0x6 -> MAX
x1 + 2x2 – 3x3 + x4
= 12
3x1 + x2 + x3 + + x5
=4
2x1 + 2x2 + 5x3 +
+ x6 = 5
xj ≥ 0 , j = 1,6
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
20/4/2012
λ
2
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
0
0
12
4
5
->
0
λ
Δj
=
X
0 * 12 + 0 * 4 + 0 *5 = 0
20/4/2012
3
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
λ
0
Δj
=
0
0
0
X
1
3
4
-
4
->
-4
0 * 1 + 0 * 3 + 0 *4 = 0
20/4/2012
4
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
-4
Δj
=
0
0
0
X
2
1
2
-
6
->
λ
-6
0*2+0*1+0*2=0
20/4/2012
5
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
-4
-6
Δj
=
0
0
0
X
-3
1
5
-
8
->
λ
-8
0 * (-3) + 0 * 1 + 0 *5 = 0
20/4/2012
6
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
-4
-6
-8
0
0
0
Δj
λ
Tương tự làm cho
x4, x5, x6, sẽ cho
ra kết quả là 0 0 0
20/4/2012
7
GiẢI BÀI TOÁN ĐƠN HÌNH
Bài toán Max nên Với mọi denta j ≥ 0 thì bài toán mới tối ưu, bài toán chưa thỏa điều
kiện
-> xác định cột xoay
i
Cơ sở
Ci
Bi
x1
x2
x3
x4
x5
x6
λ
P/a
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
-4
-6
-8
0
0
0
Δj
BT Max -> cột xoay
là số âm nhỏ nhất
(hoặc số âm có trị
tuyệt đối lớn nhất)
20/4/2012
8
GiẢI BÀI TOÁN ĐƠN HÌNH
Đã có cột xoay -> tìm lamda để xác định dòng xoay
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
-4
-6
(-8)
0
0
0
Δj
=
20/4/2012
12
/
-3
->
-4
λ
Vì là số -4 (số
âm) nên sẽ ghi
vào dấu 9
GiẢI BÀI TOÁN ĐƠN HÌNH
Tìm lamda để xác định dòng xoay
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
1
x4
0
12
1
2
-3
1
0
0
2
x5
0
4
3
1
1
0
1
0
3
x6
0
5
2
2
5
0
0
1
0
-4
-6
(-8)
0
0
0
Δj
=
20/4/2012
4
/
1
->
λ
-
4
10
GiẢI BÀI TOÁN ĐƠN HÌNH
Tìm lamda để xác định dòng xoay
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
5
0
0
1
0
-4
-6
(-8)
0
0
0
Δj
=
20/4/2012
5
/
5
->
1
11
GiẢI BÀI TOÁN ĐƠN HÌNH
Dòn xoay sẽ là dòng có lamda dương nhỏ nhất
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
5
0
0
1
1
0
-4
-6
(-8)
0
0
0
Δj
số 1 là lamda
dương nhỏ nhất
20/4/2012
12
GiẢI BÀI TOÁN ĐƠN HÌNH
Đã xác định được dòng xoay -> tại sao phải xác định dòng xoay vào cột xoay ?
Thật ra xác định để biết được biến vào và biến ra cơ sở
ở đây biến vào là cột xoay (x3) và biến ra là dòng xoay (x6)
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
Δj
Ra khỏi cơ sở
20/4/2012
13
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
->
1
Δj
1
x4
0
2
x5
0
3
x3
8
Δj
=
20/4/2012
5
/
5
14
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
Δj
1
x4
0
2
x5
0
3
x3
8
1
Δj
=
20/4/2012
2
/
5
->
2/5
15
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
2/5
1
Δj
1
x4
0
2
x5
0
3
x3
8
Δj
=
20/4/2012
2
/
5
->
2/5
16
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
2/5
2/5
1
Δj
1
x4
0
2
x5
0
3
x3
8
Δj
=
20/4/2012
5
/
5
->
1
17
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
1
2/5
2/5
1
0
0
1/5
Δj
1
x4
0
2
x5
0
3
x3
8
Δj
làm tương tự để
có kết quả như
bảng
20/4/2012
18
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
-4
-6
(-8)
0
1
2/5
2/5
1
0
Δj
1
x4
0
2
x5
0
3
x3
8
0
1
(1)
Số0 ở đây bắt
0
buộc là số 0, vậy
ta phải tìm hệ số.
có hệ số sẽ tìm
được giá trị dòng
0 này 1/5
Δj
0
20/4/2012
=
1
-
?
*
1
->
1
hehe, hệ số là 1,
khỏe rồi.
19
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
0
0
1/5
Δj
1
x4
0
2
x5
0
3
x3
8
0
1
2/5
2/5
1
Δj
=
20/4/2012
1
-
1
*
2/5
->
3/5
nếu là hệ số 1, không
cần phải nhân cho
2/5. có thể trừ trực
tiếp cho 2/5
20
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
3/5
0
2/5
1
0
0
1/5
Δj
1
x4
0
2
x5
0
3
x3
8
1
2/5
Δj
=
20/4/2012
3
-
2/5
->
13/5
21
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
13/5
3/5
0
1
2/5
2/5
1
0
0
1/5
1
->
3
Δj
1
x4
0
2
x5
0
3
x3
8
Δj
=
20/4/2012
4
-
22
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
Δj
1
x4
0
2
x5
0
3
13/5
3/5
0
0
0
-1/5
3
x3
8
1
2/5
2/5
1
0
0
1/5
Δj
Tương tự làm sẽ có
kết quả như bảng
20/4/2012
23
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
-4
-6
(-8)
0
Δj
1
x4
0
0
2
x5
0
3
13/5
3/5
0
0
3
x3
8
1
2/5
2/5
1
0
0
1
(1)
Số0 ở đây bắt
0
buộc là số 0, vậy
ta phải tìm hệ số.
có 0hệ số sẽ
tìm
-1/5
được giá trị dòng
0 này 1/5
Δj
0
20/4/2012
=
-3
-
?
*
1
->
-3
hehe, hệ số là -3,
không khỏe chút
nào
24
GiẢI BÀI TOÁN ĐƠN HÌNH
i
Cơ sở
Ci
Bi
P/a
x1
x2
x3
x4
x5
x6
4
6
8
0
0
0
λ
1
x4
0
12
1
2
-3
1
0
0
-
2
x5
0
4
3
1
1
0
1
0
4
3
x6
0
5
2
2
(5)
0
0
1
(1)
0
-4
-6
(-8)
0
0
0
Δj
1
x4
0
0
2
x5
0
3
13/5
3/5
0
0
0
-1/5
3
x3
8
1
2/5
2/5
1
0
0
1/5
-3
*
Δj
=
20/4/2012
2
-
2/5
->
16/5
2 + 6/5 =16/5
cái này cộng trừ
phân số thôi
25
