Ví dụ 5: Giải bài toán QHTT sau:
f(x) = 3x1 + x2 - 5x3 + 2x4 max
x1 3x2 | - + | 2x2 + 3x4 x4 | = 4 2 | |
x2 2x2 | + + | x3 - 2x4 x4 | 5 3 |
Có thể bạn quan tâm!
-
Bài Toán Quy Hoạch Tuyến Tính Ở Dạng Chuẩn Tắc -
Đưa Dạng Chính Tắc Về Dạng Chuẩn Tắc (Bài Toán M) -
Quy hoạch tuyến tính - 5 -
Hiện Tượng Xoay Vòng Và Cách Khắc Phục -
Một Xí Nghiệp Đồ Gỗ Dự Định Sản Xuất Bàn, Ghế Và Tủ. Biết Định Mức Tiêu Hao Các Yếu Tố Sản Xuất Khi Làm Ra 1 Sản Phẩm Cho Trong Bảng Sau: -
Bài Toán Quy Hoạch Tuyến Tính Đối Ngẫu
Xem toàn bộ 152 trang tài liệu này.
Dạng chuẩn của bài toán trên là:
xj 0 , (j = 1, 2, . . . , 4)
g(x) = - f(x) = - 3x1 - x2 + 5x3 - 2x4 min
x1 - 2x2 + 3x4 = 4
3x2 + x4 + x5 = 2 x2 + x3 - 2x4 - x6 = 5 2x2 + x4 + x7 = 3
xj 0 , (j = 1, 2, . . . , 7)
Có ma trận hệ số là:
1 2 0 3 0 0 0
0 3 0 1 1 0 0
0 | 1 | 1 | 2 | 0 | 1 | 0 |
0 | 2 | 0 | 1 | 0 | 0 | 1 |
A =
Có PACB xuất phát là: x = (4, 0, 5, 0, 2, 0, 3)
Lập bảng đơn hình:
Ẩn CB | PA | 3 | 1 | -5 | 2 | 0 | 0 | 0 | i | |
x1 | x2 | x3 | x4 | x5 | x6 | x7 | ||||
-3 | X1 | 4 | 1 | -2 | 0 | 3 | 0 | 0 | 0 | - |
0 | X5 | 2 | 0 | 3 | 0 | 1 | 1 | 0 | 0 | 2/3 |
5 | X3 | 5 | 0 | 1 | 1 | -2 | 0 | -1 | 0 | 5 |
0 | X7 | 3 | 0 | 2 | 0 | 1 | 0 | 0 | 1 | 3/2 |
g(x) | 13 | 0 | 12 | 0 | -17 | 0 | -5 | 0 |
| |
| ||||||||||
-3 | X1 | 16/3 | ||||||||
-1 | X2 | 2/3 | ||||||||
5 | X3 | 13/3 | ||||||||
0 | X7 | 5/3 | ||||||||
g(x) | 5 | 0 | 0 | 0 | -21 | -4 | -5 | 0 |
|
Kết luận:
PATƯ của bài toán là: x* = (16/3,2/3,13/3,0,0,0,5/3) Giá trị tối ưu của bài toán là: f(x*) = -g(x*) = - 5
1.3.2. Giải bài toán QHTT ở dạng chính tắc (Phương pháp đánh thuế)
Xét bài toán QHTT ở dạng chính tắc:
f(x) =
với hệ ràng buộc:
n
cjxjmin
j1
(1)
a x a x ... a x b
11 1 12 2 1n n 1
a x a x ... a x b
21 1 22 2 2 n n 2
(2)
.............................................
a x a x ... a x b
m1 1 m 2 2 mn n m
xj 0 , (j = 1, 2, . . . , n) (3)
Bài toán trên được gọi là bài toán ban đầu (bài toán xuất phát)
Giả thiết rằng bi 0 , (i = 1, 2, . . . , m) (nếu âm thì nhân 2 vế của ràng buộc i với -1) Ta sẽ chuyển bài toán xuất phát về bài toán mở rộng (gọi tắt là bài toán M)
f(x) =
cjxjMxn1 Mxn2 ... Mxnm min
n
j1
(1)
a x a x ... a x x b
11 1 12 2 1n n n1 1
a x a x ... a x x b
21 1 22 2 2 n n n2 2
(2)
...........................................................................
a x
a x
... a x
x b
m1 1 m 2 2 mn n n m m
xj 0 , (j = 1, 2, . . . , (m+n)) (3)
trong đó: M là số dương vô cùng lớn (lớn hơn bất cứ số cụ thể nào mà ta cần phải so sánh)
Các biến xn + i (i =1, 2, . . . , m) là các biến giả.
Bài toán mở rộng có dạng chuẩn tắc, ta áp dụng thuật toán đơn hình vào bài toán mở rộng. Trong khi thực hiện thuật toán đơn hình, ta tính các ước lượng j
j = aj + bj M
và trong bảng đơn hình, dòng ước lượng chứa j sẽ chia thành 2 dòng, dòng trên chứa hệ số aj, dòng dưới chứa hệ số bj. Ví dụ: 3 = 2M – 9 thì ở cột 3 dòng trên ghi -9, dòng dưới ghi 2.
Để xét dấu j và so sánh chúng với nhau, ta sử dụng quy tắc sau:
j
< 0 nếu j j
b bj | 0 0 | , , | a 0 aj _ tu |
b | 0 | , | a 0 |
bj | 0 | , | aj _ tu |
ú ý
j
> 0 nếu j j
ú ý
< nếu b
b , a a
m n
m n m n
b b , a , a _ tuú ý
m n m n
Kết thúc thuật toán đơn hình giải bài toán M, ta đi đến một trong các khả năng sau:
1) Nếu bài toán mở rộng không có PATƯ thì bài toán xuất phát cũng không có PATƯ
2) Nếu bài toán mở rộng có PATƯ mà các ẩn giả đều bằng 0, thì bỏ ẩn giả đi, ta còn lại PATƯ của bài toán xuất phát.
3) Nếu bài toán mở rộng có PATƯ mà trong đó, có ít nhất một ẩn giả mang giá trị dương, thì bài toán xuất phát không có PATƯ.
Chú ý: Mỗi khi một ẩn giả bị đưa ra khỏi hệ cơ bản thì sẽ không được đưa trở lại nữa, vì vậy có thể không cần chú ý tới các cột ứng với ẩn giả đó nữa, tức là ta không cần viết các giá trị trên cột chứa ẩn giả đó nữa.
Nếu bài toán ban đầu đã có một số véc tơ cột đơn vị, thì ta chỉ cần thêm các ẩn giả cần thiết, đủ để đưa bài toán ban đầu về dạng chuẩn tắc.
Ví dụ 6: Giải bài toán QHTT sau:
f(x) = 2x1 - x2 + 3x3 + x4 min
2x1 - x2 + 2x4 = 5 x1 + 2x2 + x3 - 3x4 = 2 x1 + 3x4 = 3
xj 0 , (j = 1, 2, . . . , 4)
Bài toán trên đã ở dạng chính tắc và ta thấy nó mới chỉ có một véc tơ cột đơn vị, tức là mới chỉ có một ẩn cơ bản. Do đó ta bổ xung thêm 2 ẩn giả x5, x6 vào để đưa về bài toán mở rộng như sau:
f(x) = 2x1 - x2 + 3x3 + x4 + Mx5 + Mx6 min 2x1 - x2 + 2x4 + x5 = 5
x1 + 2x2 + x3 - 3x4 = 2 x1 + 3x4 + x6 = 3 xj 0 , (j = 1, 2, . . . , 6)
Có ma trận hệ số là
2 1 0 2 1 0
A = 1 2 1 3 0 0
1 0 0 3 0 1
Có PACB ban đầu là: x = (0; 0; 2; 0; 5; 3)
Lập bảng đơn hình:
Ẩn CB | PA | 2 | -1 | 3 | 1 M M | i | |||
x1 | x2 | x3 | x4 x5 x6 | ||||||
M | X5 | 5 | 2 | -1 0 | 2 | 1 | 0 | 5/2 | |
3 | X3 | 2 | 1 | 2 1 | -3 | 0 | 0 | - | |
M | X6 | 3 | 1 | 0 0 | 3 | 0 0 | 1 | 1 | |
Lần 1 | aj | 6 | 1 | 7 | 0 | -10 | 0 | ||
bj | 8 | 3 | -1 | 0 | 5 | 0 | 0 | ||
M 3 1 | X5 X3 X4 | 3 5 1 | 4/3 | -1 2 0 | 0 1 0 | 0 0 | 1 0 0 | 9/4 5/2 3 | |
2 1/3 | |||||||||
1 | |||||||||
Lần 2 | aj bj | 16 3 | 13/3 4/3 | 7 -1 | 0 0 | 0 0 | 0 0 | ||
2 3 1 | X1 X3 X4 | 9/4 1/2 1/4 | 1 0 0 | -3/4 | 0 | 0 | - | ||
7/2 | 1 0 | 0 1 0 | 1/7 1 | ||||||
1/4 | |||||||||
Lần 3 | aj bj | 25/4 0 | 0 0 | 41/4 0 | 0 0 | ||||
0
|
| ||||||||
2 | X1 | 33/14 | - | ||||||
-1 | X2 | 1/7 | - | ||||||
1 | X4 | 3/14 | - | ||||||
Lần 4 | aj | 67/14 | 0 | 0 | -41/14 | 0 | |||
bj | 0 | 0 | 0 | 0 | 0 | ||||
Bài toán mở rộng có PATƯ là : (33/14,1/7,0,3/14,0,0)
Vì các ẩn giả đều x5, x6 đều bằng không nên chỉ việc bỏ đi ẩn giả còn lại là PATƯ của bài toán ban đầu.
Kết luận:
- PATƯ cần tìm là: x* = (33/14, 1/7, 0, 3/14)
- Giá trị hàm mục tiêu đạt được là : F(x*) = 67/14
Ví dụ 7: Giải bài toán QHTT sau:
f(x) = 3x1 - 2x2 + x4 max
2x1 | - x2 | + 3x4 | = 3 |
x1 | + 2x2 | + x3 | + 3x5 = 2 |
3x1 | -2x2 | + 2x4 | + x5 7 |
- x1 | + 2x2 | + x4 | = 9 |
xj 0 , (j = 1, 2, . . . , 5)
Dạng chuẩn của bài toán trên là:
g(x) = - 3x1 + 2x2 - x4 + Mx7 + Mx8 min 2x1 - x2 + 3x4 + x7 = 3
x1 + 2x2 + x3 + 3x5 = 2 3x1 -2x2 + 2x4 + x5 + x6 = 7
- x1 + 2x2 + x4 + x8 = 9
xj 0 , (j = 1, 2, . . . , 8); x6 ẩn phụ; x7, x8 ẩn giả
Có ma trận hệ số là
2 | 1 | 0 | 3 | 0 | 0 | 1 |
1 | 2 | 1 | 0 | 3 | 0 | 0 |
3 | 2 | 0 | 2 | 1 | 1 | 0 |
1 2 0 1 0 0 0 | ||||||
0
0
A =
0
1
Có PACB ban đầu là: x = (0, 0, 2, 0, 0, 7, 3, 9)
Lập bảng đơn hình:
Ẩn CB | PA | -3 | 2 | 0 | -1 | 0 | 0 | M | M | i | |
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | ||||
M | X7 | 3 | 2 | -1 | 0 | 3 | 0 | 0 | 1 | 0 | 1 |
0 | X3 | 2 | 1 | 2 | 1 | 0 | 3 | 0 | 0 | 0 | - |
0 | X6 | 7 | 3 | -2 | 0 | 2 | 1 | 1 | 0 | 0 | 7/2 |
M | X8 | 9 | -1 | 2 | 0 | 1 | 0 | 0 | 0 | 1 | 9 |
Lần 1 | 0 | 3 | -2 | 0 | 1 | 0 | 0 | 0 | 0 | ||
12 | 1 | 1 | 0 | 4 | 0 | 0 | 0 | 0 | |||
X4 | 1 | 2/3 | -1/3 | 0 | 1 | 0 | 0 | 0 | - | ||
X3 | 2 | 1 | 2 | 1 | 0 | 3 | 0 | 0 | 1 | ||
X6 | 5 | 5/3 | -4/3 | 0 | 0 | 1 | 1 | 0 | - | ||
X8 | 8 | -5/3 | 7/3 | 0 | 0 | 0 | 0 | 1 | 24/7 | ||
Lần 2 | -1 | 7/3 | -5/3 | 0 | 0 | 0 | 0 | 0 | |||
8 | -5/3 | 7/3 | 0 | 0 | 0 | 0 | 0 | ||||
X4 | 4/3 | ||||||||||
X2 | 1 | ||||||||||
X6 | 19/3 | ||||||||||
X8 | 17/3 |
|
| ||||||||
Lần 3 | 2/3 | 19/6 | 0 | 5/6 | 0 | 5/2 | 0 | 0 | |||
17/3 | -17/6 | 0 | -7/6 | 0 | -7/2 | 0 | 0 | ||||
