Bài giảng Quy hoạch tuyến tính (Mới nhất)
1
Chương 1
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1.1 MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Ví dụ 1. Một xí nghiệp cần sản xuất 3 loại bánh: , và
. Lượng nguyên liệu đường, đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền
lãi cho một bánh mỗi loại được cho trong bảng sau:
Nguyên liệu Bánh đậu xanh Bánh thập cẩm
Bánh dẻo
Lượng dự trữ
Đường
Đậu
0,04kg
0,07kg
3000
0,06kg
0kg
0,05kg
0,02kg
2500
500kg
300kg
Lãi
2000
Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho không bị động
về nguyên liệu mà lãi đạt được cao nhất.
Giải
Gọi x1, x2 , x3 lần lượt là số bánh đậu xanh, bánh thập cẩm, bánh dẻo cần phải sản xuất.
Điều kiện: xj ≥ 0
1) Tiền lãi thu được là:
2) Lượng đường được sử dụng là: 0,04x1
Để không bị động về nguyên liệu thì:
3) Lượng đậu được sử dụng là: 0,07x1 0,02x3 (kg)
,
j =1,2,3. Khi đó
0,06x2
(ngàn).
+
+
0,05x3 (kg)
1 .
+
Để không bị động về nguyên liệu thì:
Vậy ta có mô hình bài toán
.
(1) f (x)
=
f (x1, x2 , x3)
=
3x1
+
≤
2x2 + 2,5x3 → max
(2) 0,04x1
0,07x1
+
+
0,06x1
0,02x3
+
≤
.
0,05x1
500
300
(3) xj
≥
0
,
j
=
1,2,3
Ta nói đây là bài toán quy hoạch tuyến tính 3 ẩn tìm max của hàm mục tiêu.
Ví dụ 2. Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng đạm, đường, khoáng
cho một loại gia súc tương ứng là 90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng
trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại được cho trong bảng sau:
Chất dinh dưỡng
Đạm
A
B
C
0,1g
0,3g
0,02g
3000
0,2g
0,4g
0,01g
4000
0,3g
0,2g
0,03g
5000
Đường
Khoáng
Giá mua
2
Hãy lập mô hình toán học của bài toán xác định khối lượng thức ăn mỗi loại phải mua để
tổng số tiền chi cho mua thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi
ngày.
Giải
Gọi x1, x2 , x3 lần lượt là khối lượng (g) thức ăn A, B, C cần mua.
Điều kiện: xj ≥ 0
Tổng khối lượng các chất dinh dưỡng có trong thức ăn cần mua là
Đạm: 0,1x1 0,2x2 0,3x3 (g)
Đường: 0,3x1 0,4x2 0,2x3 (g)
Khoáng: 0,02x1 0,01x2 0,03x3 (g)
, j =1,2,3. Khi đó
+
+
+
+
+
+
Để đáp ứng được nhu cầu dinh dưỡng tối thiểu mỗi ngày thì tổng khối lượng các chất dinh
dưỡng có trong thức ăn cần mua không thể nhỏ hơn các nhu cầu tối thiểu mỗi ngày về các
chất dinh dưỡng đó nên ta có các điều kiện:
0,1x1
0,3x1
+
+
0,2x2
0,4x2
+
+
0,3x3
0,2x3
≥
90
≥
130
0,02x1
Tổng số tiền phải chi để mua số thức ăn trên là
3x1 4x2 5x3 (đồng)
Yêu cầu bài toán là số tiền chi cho mua thức ăn ít nhất nên ta có điều kiện
3x1 4x2 5x3 min
Vậy ta có mô hình bài toán
+ 0,01x2 + 0,03x3 ≥10
+
+
+
+
→
(1) f (x)
(2) 0,1x1
0,3x1
=
+
+
f (x1, x2 , x3)
=
3x1
+
4x2
+
5x3
→
min
0,2x2
0,4x2
+
+
0,3x3
0,2x3
≥ 90
≥
130
0,02x1
(3) xj
+
0,01x2
+ 0,03x3 ≥10
≥
0
,
j
=
1,2,3.
Ví dụ 3. (CHLH 2009) Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là bàn,
ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giá bán mỗi sản phẩm mỗi loại
ước tính trong bảng sau:
Các yếu tố
Lao động (ngày công)
Chi phí sản xuất (ngàn đồng)
Giá bán (ngàn đồng)
Bàn
2
Ghế
1
Tủ
3
100
260
40
250
600
120
Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi loại cần phải sản xuất
sao cho không bị động trong sản xuất và tổng doanh thu đạt được cao nhất, biết rằng cơ sở
có số lao động tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất là 40
triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.
3
Giải
Gọi x1, x2 , x3 lần lượt là số bàn, ghế, tủ cần phải sản xuất. Ta có các điều kiện: x1, x2 , x3 ≥ 0
.
Tổng ngày công và chi phí dự định để sản xuất là:
2x1 + x2 + 3x3 (ngày công)
100x1 + 40x2 + 250x3 (ngàn đồng)
Để không bị động trong sản xuất ta có các điều kiện sau
2x1 + x2 + 3x3 ≤ 500
100x1 + 40x2 + 250x3 ≤ 40000
Theo tỉ lệ giữa số bàn và số ghế ta có điều kiện sau
6x1 = x2
Tổng doanh thu theo dự kiến là
260x1 +120x2 + 600x3 (ngàn đồng)
Để tổng doanh thu đạt được cao nhất ta có điều kiện
260x1 +120x2 + 600x3 → max
Như vậy, mô hình toán học của bài toán là
(1)
(2)
(3)
260x1 +120x2 + 600x3 → max
2x1 + x2 + 3x3 ≤ 500
100x1 + 40x2 + 250x3 ≤ 40000
6x1 = x2
x1, x2 , x3 ≥ 0
.
1.2 PHÂN LOẠI DẠNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1.2.1 Dạng tổng quát của bài toán quy hoạch tuyến tính
Bài toán QHTT dạng tổng quát với n ẩn là bài toán có dạng
(1) f (x) = c1x1 + c2 x2 +L+ cn xn → max(min)
≥
(2) ai1x1 + ai2 x2 +L+ ain xn ≤ b ,i =1,2,K,m
i
=
≥ 0
(3) xj ≤ 0 , j =1,2,K,n
tuy y
Trong đó
• 1) là hàm mụtiu.
• 2) là hệ ràng buộc chính
•
• (2) và (3) được gọi chung là hệ ràng buộc của bài toán.
4
Khi đó
• Mỗi vector x = (x1, x2 ,
của bài toán.
K
, xn ) thõa (2) và (3) được gọi là một phương án (PA)
• Mỗi phương án x thỏa (1), nghĩa là tại đó hàm mục tiêu đạt giá tị nhỏ nhất (lớn
nhất) trên tập các phương án được gọi là một phương án tối ưu (PATU) của bài
toán.
• Giải một bài toán QHTT là đi tìm một phương án tối ưu của nó hoặc chỉ ra rằng
bài toán vô nghiệm, nghĩa là bài toán không có PATU.
(1) f (x) = c1x1 + c2 x2 +L+ cn xn → max(min)
(2) ai1x1 + ai2 x2 +L+ ain xn = b ,i =1,2,K,m
i
(3) xj ≥ 0, j =1,2,K,n
Nhận xét. Bài toán QHTT dạng chính tắc là bài toán QHTT dạng tổng quát trong đó
•
• Các ẩn đều không âm.
Ví dụ. Bài toán sau có dạng chính tắc
(1) f (x) = 2x1 − 4x2 − x3 + 6x4 → min
x − 4x + x =12
1
2
4
(2) 12x − 3x + x + x = 3
1
2
3
4
x1 − x2 − x3 − x4 = −6
(3) xj ≥ 0, j =1,2,3,4
1.2.3 Dạng chuẩn của bài toán QHTT
Bài toán QHTT dạng chuẩn là bài toán QHTT dạng chính tắc
(1) f (x) = c1x1 + c2 x2 +L+ cn xn → max(min)
(2) ai1x1 + ai2 x2 +L+ ain xn = b ,i =1,2,K,m
i
(3) xj ≥ 0, j =1,2,K,n
Trong đó
• Các hệ số tự do đều không âm.
• Trong ma trận hệ số tự do có đủ m vector cột đơn vị: e1,e2 ,K,em
.
1
0
0
0
1
0
e1 =
,e1 =
,K,em =
0
0
1
Khi đó:
• Các ẩn ứng với các vector cột đơn vị được gọi là các ẩn cơ bản. Cụ thể ẩn ứng với
vector cột đơn vị ek là ẩn cơ bản thứ k.
5
• Một phương án mà các ẩn cơ bản đều bằng 0 được gọi là phương án cơ bản.
• Một phương án cơ bản có đủ m thành phần dương được gọi là không suy biến.
Ngược lại một phương án cơ bản có ít hơn m thành phần dương được gọi là suy
biến.
Ví dụ. Xét bài toán QHTT sau
(1) f (x) = 2x1 − 4x2 − x3 + 6x4 → min
x + x + x =12
1
4
5
(2) 12x + x + x = 3
1
3
6
x1 + x2 − x3 − x4 = 6
(3) xj ≥ 0, j =1,2,3,4,5,6
Ta thấy bài toán trên có dạng chính tắc, hơn nữa
Các hệ số tự do đều không âm
Ma trận hệ số ràng buộc A là
1 0 0 1 1 0
A = 12 0 1 0 0 1
1 1 −1 −1 0 0
Có chứa đầy đủ 3 vector cột đơn vị e1 (cột 5), e2 (cột 6), e3 (cột 2).
Do đó bài toán có dạng chuẩn, trong đó
• Ẩn cơ bản thứ nhất là x5
• Ẩn cơ bản thứ hai là x6
• Ẩn cơ bản thứ ba là x2
Nhận xét. Trong bài toán trên, khi cho ẩn cơ bản thứ k bằng hệ số tự do thứ k, còn các ẩn
không cơ bản bằng 0, nghĩa là cho x2 =15, x6 = 3, x2 = 6, x1 = 0, x3 = 0, x4 = 0 ta được một
phương án cơ bản của bài toán x = (0,6,0,0,12,3)
.
Phương án này không suy biến vì có đủ 3 thành phần dương. Ta gọi đây là phương án cơ
bản ban đầu của bài toán.
Chú ý. Tổng quát, trong bài toán QHTT dạng chuẩn bất kì, khi cho ẩn cơ bản thứ k bằng
hệ số tự do thứ k ( k =1,2,K,m ), còn các ẩn không cơ bản bằng 0, ta được một phương án
cơ bản của bài toán. Ta gọi đây là phương án cơ bản ban đầu của bài toán.
1.3 BIẾN ĐỔI DẠNG BÀI TOÁN QHTT
1.3.1 Dạng tổng quát về dạng chính tắc
Ta có thể biến đổi bài toán dạng tổng quát về dạng chính tắc bằng các bước sau
Bước 1. Kiểm tra hệ ràng buộc chính
1) Nếu có ràng buộc chính dạng ai1x1 + ai2 x2 +
buộc đó ẩn phụ n+k , nghĩa là ta thay ràng buộc ai1x1 + ai2 x2 +
toán bằng ràng buộc ai1x1 + ai2 x2 + + ain xn + xn+k = b
L+ ain xn ≤ b thì ta cộng vào vế trái ràng
i
x
L+ ain xn ≤ b trong bài
i
L
.
i
6
2) Nếu có ràng buộc chính dạng ai1x1 + ai2 x2 +L+ ain xn ≥ b thì ta trừ vào vế trái ràng
i
buộc đó ẩn phụ
xn+k , nghĩa là ta thay ràng buộc ai1x1 + ai2 x2 +L+ ain xn ≥ b trong bài
i
toán bằng ràng buộc ai1x1 + ai2 x2 +L+ ain xn − xn+k = b
.
i
Chú ý. Các ẩn phụ là các ẩn không âm và hệ số của các ẩn phụ đó trong hàm mục tiêu là 0.
Bước 2. Kiểm tra điều kiện dấu của ẩn số
′
′
1) Nếu có ẩn xj ≤ 0 thì ta thực hiện phép đổi ẩn số xj = −xj với xj ≥
2) Nếu có ẩn xj có dấu tùy ý thì ta thực hiện phép đổi ẩn số xj = xj − xj với
′′
0.
′′
′
′
xj , xj ≥ 0.
Chú ý. Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần tính giá trị của các ẩn
ban đầu và bỏ đi các ẩn phụ thì sẽ được PATU của bài toán dạng tổng quát đã cho.
Ví dụ. Biến đổi bài toán sau về dạng chính tắc
(1)
f
(
x
)
=
2
x1 −
x2 +
x1 + x3 ≥ 30
4x2 − x3 + 6x4 → min
4
7
2
x1 −
6
5
x3 ≤ 50
(2)
x1 +
3
x2 −
5
x3 = −25
(3) x1 ≥ 0, x2 ≤
Giải
0
Thêm vào bài toán ẩn phụ x4 ≥
trình x1 − x2 + x3 + x4 = 50
Thêm vào bài toán ẩn phụ x5 ≥
x1 + x3 − x5 = 30
0 để biến bất phương trình 4x1 − 6x2 + 5x3 ≤ 50 về phương
4
6
5
.
0
để biến bất phương trình 7x1 + x3 ≥ 30 về phương trình
7
.
′
′
Đổi biến x2 = −x2 với x2 ≥ 0
.
′′
′
′′
′
Đổi biến x3 = x3 − x3 với x3 , x3 ≥ 0
.
Ta đưa bài toán về dạng chính tắc
′
′
′′
(1) f (x) = 3x1 − 2x2 + 2,5(x3 − x3 ) → max
′
′
′′
4x1 + 6x2 + 5(x3 − x3 ) + x4 = 50
′
′′
(2) 7x + (x − x ) − x = 30
1
3
3
5
′
′
′′
2x − 3x − 5(x − x ) = −25
1
2
3
3
′
′
′′
(3) x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
1.3.2 Dạng chính tắc về dạng chuẩn
Từ bài toán dạng chính tắc ta có thể xây dựng bài toán dạng chuẩn như sau
1) Khi gặp hệ số tự do b < 0 ta đổi dấu hai vế của ràng buộc thứ i.
i
7
2) Khi ma trận hệ số ràng buộc A không chứa cột đơn vị thứ k là ek , ta đưa vào ẩn giả
xn+k ≥ 0 và cộng thêm ẩn giả xn+k vào vế trái phương trình ràng buộc thứ k để được
phương trình ràng buộc mới: ak1x1 + ak 2 x2 +L+ akn xn + xn+k = bk
3) Hàm mục tiêu mở rộng f (x) được xây dựng từ hàm mục tiêu ban đầu như sau
.
• Đối với bài toán min: f (x)
• Đối với bài toán max: f (x)
=
f (x)
f (x)
+
M ( an gia)
.
∑
=
−
M ( an gia)
.
∑
Trong đó M là đại lượng rất lớn, lớn hơn bất kì số nào cho trước.
Ví dụ 1. Biến đổi bài toán QHTT sau về dạng chuẩn
(1) f (x)
=
3x1
+
+
2x2
5x3
+
=
2x3 + x4 → min
4x
−
+
+
6x2
50
1
(2) 7x
x3
+ x4 = 0
1
2x1
3x2
−
5x3 = −25
(3) xj ≥ 0, j =1,K,4
Giải
Bài toán trên đã có dạng chính tắc, trong đó vế phải của phương trình ràng buộc thứ ba là
-25 < 0. Đổi dấu hai vế của phương trình này ta được −2x1 − 3x2 + 5x3 = 25
Và (2) trở thành
4x − 6x + 5x = 50
1
2
3
7x + x + x = 0
1
3
4
−2x1 − 3x2 + 5x3 = 25
Ma trận hệ số của ràng buộc là
4
−6 5 0 1 0
A = 7 0 1 1 0 0
−2 −3 5 0 0 1
Vì A còn thiếu 2 vector cột đơn vị là e1 và e3 nên bài toán chưa có dạng chuẩn.
Thêm vào bài toán hai ẩn giả x5 , x6 ≥ 0 và xây dựng bài toán mở rộng có dạng chuẩn như
sau
(1) f (x) = 3x1 + 2x2 + 2x3 + x4 + Mx5 + Mx6 → min
4x − 6x + 5x + x = 50
1
2
3
5
(2) 7x + x + x = 0
1
3
4
−2x1 − 3x2 + 5x3 + x6 = 25
(3) xj ≥ 0, j =1,,6
Ví dụ 2. Biến đổi bài toán QHTT sau về dạng chuẩn
(1) f (x) = 3x1 + 2x2 + 2x3 + x4 → max
8
4x − 6x + 5x = 50
1
2
3
(2) 7x + x + x = 0
1
3
4
2x1 + 3x2 − 5x3 = −25
(3) xj ≥ 0, j =1,K,4
Ta xây dựng bài toán mở rộng dạng chuẩn như sau
(1) f (x) = 3x1 + 2x2 + 2x3 + x4 − Mx5 − Mx6 → max
4x − 6x + 5x + x = 50
1
2
3
5
(2) 7x + x + x = 0
1
3
4
−2x1 − 3x2 + 5x3 + x6 = 25
(3) xj ≥ 0, j =1,,6
Chú ý.
• Ẩn phụ: Tổng quát chuyển thành chính tắc
• Ẩn giả: Chính tắc chuyển thành chuẩn
Ví dụ 3. Biến đổi bài toán QHTT sau về dạng chuẩn
(1) f (x) = 3x1 + 2x2 + 2x3 + x4 → min
−9x +15x ≤ 50
1
3
(2) −6x + 2x = −120
3
4
x1 + 3x2 −5x3 ≥ −45
(3) xj ≥ 0, j =1,K,4
Giải
Thêm vào bài toán 2 ẩn phụ x5 , x6 ≥ 0 ta được bài toán có dạng chính tắc như sau
(1) f (x) = 3x1 + 2x2 + 2x3 + x4 → min
−9x +15x + x = 50
1
3
5
(2) −6x + 2x = −120
3
4
x1 + 3x2 −5x3 − x6 = −45
(3) xj ≥ 0, j =1,K,6
.
Bài toán trên chưa có dạng chuẩn.
Ta thấy các vế phải của hai phương trình ràng buộc thứ 2 và 3 đều âm nên bằng cách đổi
dấu hai vế của các phương trình này ta được
−9x +15x + x = 50
1
3
5
(2) 6x − 2x =120
3
4
−x1 −3x2 + 5x3 + x6 = 45
Ma trận hệ số ràng buộc là
0
0
−9 15 0 1 0 0
A =
0
6 −2 0 0 1
−1 −3 5 0 0 1 0
9
Vì A còn thiếu một vector cột là e2 nên bài toán chưa có dạng chuẩn.
Thêm vào ràng buộc chính thứ hai ẩn giả x7 ≥ 0 ta được bài toán dạng chuẩn như sau
(1) f (x) = 3x1 + 2x2 + 2x3 + x4 + Mx7 → min
−9x +15x + x = 50
1
3
5
(2) 6x − 2x + x =120
3
4
7
−x1 −3x2 + 5x3 + x6 = 45
(3) xj ≥ 0, j =1,K,7
.
Chú ý. Quan hệ giữa bài toán xuất phát và bài toán mở rộng
Mối quan hệ giữa bài toán xuất phát (A) và bài toán mở rộng (B) như sau
• B vô nghiệm suy ra A vô nghiệm
• B có nghiệm có hai trường hợp:
1) Nếu mọi ẩn giả của PATU bằng 0 thì bỏ ẩn giả ta được PATU của A
2) Nếu có ít nhất một ẩn giả > 0 suy ra A không có PATU
Chương 2
PHƯƠNG PHÁP ĐƠN HÌNH
2.1 PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
DẠNG CHUẨN
2.1.1 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 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 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 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.
Tính hệ số ước lượng
4, với được tính theo công thức sau:
∆ j = (cot1)×(Aj ) − (hsxj )
Chú ý. Nếu xj là ẩn cơ bản thì ∆ j = 0
∆ của các ẩn xj ( j =1,2,K,n) và ghi tương ứng vào dòng dưới cột
j
∆
j
(
hsxj : hệ số của ẩn xj trong hàm mục tiêu).
.
Tính trị số f0 = (cot1)×(cot3) và ghi dưới cột 3.
2) Xác định phương án cơ bản xuất phát
10
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 (x0 ) = f0
.
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à aik ≤ 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
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
A được gọi là cột
v
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.
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)
11
2.1.2 Thuật toán giải 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.
Ví dụ 1. Giải bài toán QHTT sau
(1) f (x) = 2x1 −5x2 + 4x3 − x4 − 6x5 → max
x + 6x − 2x −9x = 32
1
2
4
5
(2) 2x + x + x + 3x = 30
2
3
4
5
3x2 + x5 + x6 = 36
(3) xj ≥ 0, j =1,K,6
.
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.
Ma trận hệ số của ràng buộc
1 6 0 −2 −9 0
A = 0 2 1 1 0 0
0 3 0 0 0 1
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: x3
• Ẩn cơ bản thứ ba: x6
Ta giải bài toán bằng phương pháp đơn hình
x1
2
1
0
0
0
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
2
4
0
32
30
x1
x3
x6
2
36
3
0
184
-25
1
0
f0 = 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
12
Trong bảng trên ta thấy ∆ j ≥ 0, j =1,K,6 nên bài toán có PATU là
x0 = (32,0,30,0,0,36) và f0 =184
.
Ví dụ 2. Giải bài toán QHTT sau
(1) f (x) = 6x1 + x2 + x3 + 3x4 + x5 − x6 → min
−x + x − x + x =15
1
2
4
6
(2) 2x − x + 2x = −9
1
3
6
4x1 + 2x4 + x5 −3x6 = 2
(3) xj ≥ 0, j =1,K,6
.
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
(1) f (x) = 6x1 + x2 + x3 + 3x4 + x5 − 7x6 → min
−x + x − x + x =15
1
2
4
6
(2) −2x + x − 2x = 9
1
3
6
4x1 + 2x4 + x5 −3x6 = 2
(3) xj ≥ 0, j =1,K,6
.
Ma trận hệ số của ràng buộc
−1 1 0 −1 0 1
A = −2 0 1 0 0 −2
4 0 0 2 1 −3
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: x2
• Ẩn cơ bản thứ hai: x3
• Ẩn cơ bản thứ ba: x5
Ta giải bài toán bằng phương pháp đơn hình
x1
6
x2
1
1
0
0
0
x3
1
0
1
0
0
x4
3
x5
1
0
0
1
0
x6
-7
(1)
-2
-3
3*
1
λi
1
1
1
15
9
-1
-2
4
-5
-1
-4
1
-1
0
15
x2
x3
x5
2
2
26
15
39
47
-19
-2
-1
-2
-1
-2
-7
1
1
2
3
0
0
1
0
0
0
0
1
0
x6
x3
x5
0
1
0
-5
0
13
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. Sau đó
tính các dòng ở bảng 2 bằng công thức sau
dc = dcy , d2 = d2 + 2dc, d3 = d3 + 3dc.
Trong bảng 2 ta thấy tồn tại ∆4 =1> 0 mà ai4 ≤ 0, i =1,2,3 nên bài toán min đang xét vô
nghiệm.
Ví dụ 3. Giải bài toán QHTT sau
(1) f (x) = −2x1 + 6x2 + 4x3 − 2x4 + 3x5 → max
x + 2x + 4x = 52
1
2
3
(2) 4x + 2x + x = 60
2
3
4
3x2 + x5 = 36
(3) xj ≥ 0, j =1,K,5
.
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 trong (2) đều
không âm.
Ma trận hệ số ràng buộc là
1 2 4 0 0
A = 0 4 2 1 0
0 3 0 0 1
Vì 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
Ta giải bài toán bằng phương pháp đơn hình
x1
-2
1
0
0
x2
6
2
4
3
x3
4
(4)
2
0
-16*
x4
-2
0
1
0
x5
3
0
0
1
0
λi
-2
-2
3
52
60
36
52/4*
60/2
x1
x4
x5
-116
0
-9
0
4
-2
3
13
34
36
92
1/4
-1/2 (3)
0
4
1/2
1
0
0
0
1
0
0
0
1
0
0
-1/6
1/3
-1
0
0
1
0
0
0
1
13.2
34/3*
36/3
x3
x4
x5
3
-1*
0
1
0
4
6
3
22/3 1/3
34/3 -1/6
2
x3
x2
x5
1/2
310/3 23/6
0
0
1/3
0
14
Trong bảng I ta thấy tồn tại các ∆ j < 0
:
∆2 = −9,∆3 = −16 và trên mỗi cột tương ứng có hệ
số dương. Ta chọn ∆3 = −16 âm nhỏ nhất và ẩn đưa vào là
có các hệ số dương là a13 = 4,a23 = 2 nên ta lập các tỉ số
x
3 , khi đó trên cột tương ứng
λ
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.
Biến đổi tương tự cho bảng II.
Trong bảng III ta thấy ∆ j ≥ 0,
x0 = (0,34 / 3,22 / 3,0,2) với
j
=1,2,K,5 nên bài toán đang xét có PATU là
f ( .
x0 ) = 310 / 3
2.2 PHƯƠNG PHÁP ĐƠN HÌNH MỞ RỘNG GIẢI BÀI TOÁN QUY HOẠCH
TUYẾN TÍNH DẠNG CHÍNH TẮC
Thuật toán đơn hình mở rộng giải bài toán QHTT dạng chính tắc tương tự như thuật toán
đơn hình giải bài toán QHTT dạng chuẩn nhưng có một số lưu ý như sau
1) Do hàm mục tiêu mở rộng là
) = ) − angia đối với bài toán max, nên trong bảng đơn hình ở cột hệ số có
thể có các hệ số phụ thuộc M. Khi đó ở dòng cuối các hệ số sẽ có dạng aM , do đó
f
(
x
) =
f
(
x
) +
(angia) đối với bài toán min và
∑
f
(
x
f
(
x
(
)
∑
+
b
người ta thường chia dòng cuối thành hai dòng nhỏ: Dòng trên ghi a và dòng dưới ghi b.
2) Vì M là một đại lượng dương rất lớn, nên khi so sánh các số hạng aM + b và cM + d ta
có quy tắc sau
a = c
b = d
aM + b = cM + d
a > 0
b
aM + b > 0
a = 0
b > 0
a > c
b,d
aM + b > cM + d
a = c
b > d
3) Trong bảng đơn hình đầu tiên các ẩn giả đều có trong ẩn cơ bản. Mỗi khi một ẩn giả bị
đưa ra khỏi hệ ẩn cơ bản thì không bao giờ ta đưa ẩn giả đó trở lại nữa, vì vậy trong
bảng đơn hình ta có thể bỏ đi các cột ứng với các ẩn giả.
Ví dụ 1. Giải bài toán QHTT sau
f(x) = 6x1 + 3x2 + 2x3 - 3x4
x1 + x2 + x3 - 2x4 = 4
- x1 + x4 10
→ min
≤
15
2x2 + x3 – 2x4 = 12
xj ≥ 0 (j = 1,2,3,4)
Giải
Đưa bài toán về dạng chuẩn:
f(x) = 6x1 + 3x2 + 2x3 - 3x4 + Mx6 + Mx7
x1 + x2 + x3 - 2x4 + x6 = 4
- x1 + x4 + x5 = 10
→ min
2x2 + x3 – 2x4 + x7 = 12
xj ≥ 0 (j = 1,2,3,4,5,6,7)
Giải bài toán mở rộng bằng phương pháp đơn hình
x1
6
x2
3
x3
x4
-3
-2
1
x5
0
0
1
0
0
2
1
x6
x5
x7
M
0
4
1
(1)
0
10
12
-1
0
-6
1
0
M
2
1
-2
2
-2
3
-3
3*
1
-4
-2
1
0
x2
x5
x7
3
0
4
10
4
1
1
0
1
0
0
0
0
1
0
0
-1
-2
-3
-2
-1
0
0
0
M
0
-1
1
(2)
-3
2*
0
0
0
-1
0
x2
x5
x4
3
0
8
8
1
0
1/2
-1/2
-1/2
0
-3
2
-1
-6
0
1
18
0
0
PATU: x = (0, 8, 0, 2), f(x) = 18.
Ví dụ 2. Giải bài toán quy hoạch tuyến tính sau:
f(x) = - 2x1 - x2 + x3 + x4 max
x1 + x2 + 2x3 - x4 = 2
- x2 - 7x3 + 3x4
- 3x3 + 2x4
→
≤
3
≤
7
xj 0, j = 1,2,3,4.
≥
Giải
Đưa bài toán về dạng chuẩn:
f(x) = - 2x1 - x2 + x3 + x4
→ max
x1 + x2 + 2x3 - x4 = 2
- x2 - 7x3 + 3x4 + x5 = 3
- 3x3 + 2x4 + x6 = 7
16
xj 0, j = 1,2,3,4,5,6.
≥
Giải bài toán mở rộng bằng phương pháp đơn hình
x1
-2
1
x2
-1
1
x3
1
x4
1
x5
0
0
1
0
0
x6
0
0
0
1
0
.
x1
x5
x6
-2
0
2
3
7
(2)
-7
-3
-5*
1
-1
0
-1
0
3
0
0
2
0
-1
1/2
5/2
3/2
3/2
2
1
x3
x5
x6
1
0
0
1
9
8
1/2
7/2
3/2
5/2
2
-1/2
-1/2
(1/2)
-3/2*
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
2
3
0
0
0
x3
x4
x5
1
0
1
11
20
20
31
1
5
4
0
0
3
3
0
1
7
6
0
0
PATU: x = (0, 0, 11, 20), f(x) = 31.
Chương 3
BÀI TOÁN ĐỐI NGẪU
3.1 Định nghĩa
Cho (P) là bài toán QHTT có dạng chính tắc như sau
f (x) = c1x1 + c2 x2 +L+ cn xn → max(min)
a11x1 + a12 x2 +L+ a1n xn = b
1
a21x1 + a22 x2 +L+ a2n xn = b2
KKK
am1x1 + am2 x2 +L+ amn xn = bm
xj ≥ 0, j =1,2,K,n.
Từ bài toán (P) ta lập được bài toán QHTT (D) như sau và ta gọi bài toán (D) là bài toán
đối ngẫu của bài toán (P)
f (y) = b y1 + b2 y2 +L+ bm ym → min(max)
1
a11 y1 + a21 y2 +L+ am1 ym ≥ (≤)c1
a12 y1 + a22 y2 +L+ am1 ym ≥ (≤)c2
KKK
a1n y1 + a2n y2 +L+ amn ym ≥ (≤)cn
17
Chú ý. Bài toán (D) được lập từ bài toán (P) theo nguyên tắc sau
1. Số ẩn của bài toán (D) bằng số ràng buộc chính của bài toán (P) và số ràng buộc chính
của bài toán (D) bằng số ẩn của bài toán (P).
2. Hệ số của ẩn yi trong hàm mục tiêu của bài toán (D) là số hạng tự do
buộc chính của bài toán (P).
b trong hệ ràng
i
3. Các hệ số của các ẩn và hệ số tự do trong ràng buộc chính thứ j của bài toán (D) là các
hệ số tương ứng của ẩn xj trong hệ ràng buộc chính và hàm mục tiêu của bài toán (P).
4. Nếu (P) là bài toán max thì (D) là bài toán min và hệ ràng buộc chính của bài toán (D)
là hệ bất phương trình với dấu
≥ . Nếu (P) là bài toán min thì (D) là bài toán max và hệ
ràng buộc chính của bài toán (D) là hệ bất phương trình với dấu
5. Các ẩn của bài toán (D) đều có dấu tùy ý.
3.2 Cách lập bài toán đối ngẫu
≤ .
Bài toán đối ngẫu được lập trực tiếp theo quy tắc sau, gọi là quy tắc đối ngẫu
(P)
(D)
f
(
x
) = c1x1
+
c2 x2 +L+ cn xn → max
f
(
y
) = b y1
+
b2 y2 +L+ bm ym → min
1
≥
≤ 0
ai1x1 + ai2 x2 +L+ ain xn ≤ b
yi ≥ 0
i
=
tuyy
≥ 0
≥
xj ≤ 0
a1 j y1 + a2 j y2 +L+ amj ym ≤ cj
=
tuyy
Ví dụ. Tìm bài toán đối ngẫu của bài toán sau
a)
(1) f (x) = 3x1 + 2x2 −5x3 + x4 → min
4x − 6x + 5x −5x ≤ 50
1
2
3
4
(2) 7x + x + x = 30
1
3
4
2x1 + 3x2 −5x3 ≥ −25
(3) x1 ≥ 0, x2 ≤ 0
.
b)
(1) f (x) = 2x1 + x2 −8x3 → max
7x + 4x + 2x ≤ 28
1
2
3
(2) 3x − x + 3x =10
1
2
3
2x1 + 3x2 − x3 ≥15
(3) x1, x2 , x3 ≥ 0
.
Giải
a) Bài toán đối ngẫu là
18
(1) g(y) = 50y1 + 30y2 − 25y3 → max
4y + 7y + 2y ≤ 3
1
2
3
−6y + 3y ≥ 2
1
3
(2)
5y1 + y2 −5y3 = −5
−5y1 + y2 =1
(3) y1 ≤ 0
b) Bài toán đối ngẫu là
(1) g(y) = 28y1 +10y2 +15y3 → min
, y2 tùy ý, y3 ≥ 0 .
7y + 3y + 2y ≥ 2
1
2
3
(2) 4y − y + 3y ≥1
1
2
3
2y1 + 3y2 − y3 ≥ −8
(3) y1 ≥ 0
, y3 ≤ 0 .
3.3 Cặp ràng buộc đối ngẫu
Trong một cặp ràng buộc đối ngẫu (P) và (D) như trong định nghĩa thì ta có n cặp ràng
buộc đối ngẫu như sau:
Trường hợp 1. f (x) = c1x1 + c2 x2 +L+ cn xn → max
xj ≥ 0 ↔ a1 j y1 + a2 j y2 +L+ amj ym ≥ cj , j =1,2,K,n
Trường hợp 2. f (x) = c1x1 + c2 x2 +L+ cn xn → min
xj ≥ 0 ↔ a1 j y1 + a2 j y2 +L+ amj ym ≤ cj , j =1,2,K,n
Ví dụ. Tìm bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của các bài toán QHTT
sau:
a)
(1) f (x) = x1 + 2x2 + 3x3 → min
2x + 3x − x = 2
1
2
3
x − x − 4x ≤ −3
1
2
3
(2)
x1 + x2 − 2x3 ≥ 6
3x1 + 5x2 − 7x3 ≤ 8
(3) x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
.
b)
(1) f (x) = x1 − 2x2 + 3x3 − 4x4 → max
5x + 6x + 7x +8x ≤ 9
1
2
3
4
(2) 10x −11x +12x −13x =14
1
2
3
4
−15x1 +16x2 −17x3 +18x4 ≥ −19
(3) x1, x2 , x3 ≥ 0
Giải
a) Bài toán đối ngẫu
.
19
(1) g(y) = 2y1 −3y2 + 6y3 +8y4 → max
2y + y + y + 3y ≤1
1
2
3
4
(2) 3y − y + y + 7y ≤ 2
1
2
3
4
y1 + 4y2 + 2y3 + 7y4 ≥ −3
(3) y2 , y4 ≤ 0, y3 ≥ 0 .
Hệ ràng buộc chính của bài toán (P) có 3 bất phương trình và bài toán (P) có 3 điều kiện về
dấu của ẩn số nên cặp bài toán đối ngẫu (P) và (D) có 6 cặp ràng buộc đối ngẫu
x1 − x2 − 4x3 ≤ −3 ↔ y2 ≤ 0
x1 + x2 − 2x3 ≥ 6 ↔ y3 ≥ 0
3x1 + 5x2 − 7x3 ≤ 8 ↔ y4 ≤ 0
x1 ≥ 0 ↔ 2y1 + y2 + y3 + 3y4 ≤1
x2 ≥ 0 ↔ 3y1 − y2 + y3 + 5y4 ≤ 2
x3 ≥ 0 ↔ y1 + 4y2 + 2y3 + 7y4 ≥ −3
b) Bài toán đối ngẫu
(1) g(y) = 9y1 +14y2 −19y3 → min
5y +10y −15y ≥1
1
2
3
6y −11y +16y ≥ −2
1
2
3
(2)
7y1 +12y2 −17y3 ≥ 3
8y1 −13y2 +18y3 = −4
(3) y1 ≥ 0, y2 tùy ý, y3 ≤ 0 .
Hệ ràng buộc chính của bài toán (P) có hai bất phương trình và bài toán (P) có ba điều kiện
về dấu của ẩn số nên cặp bài toán đối ngẫu (P) và (D) có 5 cặp ràng buộc đối ngẫu sau:
5x1 + 6x2 + 7x3 + 8x4 ↔ y1 ≥ 0
−15x1 +16x2 −17x3 +18x4 ≥ −19 ↔ y3 ≤ 0
x1 ≥ 0 ↔ 5y1 +10y2 −15y3 ≥1
x2 ≥ 0 ↔ 6y1 −11y2 +16y3 ≥ −2
x3 ≥ 0 ↔ 7y1 +12y2 −17y3 ≥ 3
3.4 Định lý đối ngẫu
Định lý độ lệch bù yếu. Điều kiện cần và đủ để phương án x0 của bài toán (P) và
phương án y0 của bài toán (D) đều là phương án tối ưu là trong các cặp ràng buộc đối
ngẫu của bài toán đó: Nếu một ràng buộc thỏa mãn phương án với dấu bất đẳng thức thực
sự thì ràng buộc còn lại phải thõa mãn phương án với dấu bằng.
Ứng dụng. Nhờ định lý độ lệch bù yếu, khi ta biết được một phương án tối ưu của một
trong hai bài toán của cặp bài toán đối ngẫu thì ta có thể tìm được tập phương án tối ưu của
bài toán còn lại. Ứng dụng này thường được sử dụng trong việc giải quyết các vấn đề của
bài toán QHTT.
Ví dụ 1. Cho bài toán quy hoạch tuyến tính sau
20
f(x) = x1 + 2x2 + 3x3 + 3x4
2x1 + x2 + x3 + 2x4
x1 + 2x2 + 3x3 + 4x4 = 18
→
max
≤
20
2x1 + x2 + 2x3 + x4
≥ 16
xj ≥ 0 (j = 1,2,3,4)
a. Giải bài toán trên
b. Hãy lập bài toán đối ngẫu của bài toán trên và giải bài toán đối ngẫu đó.
Giải
a. Đưa bài toán về dạng chuẩn:
f(x) = x1 + 2x2 + 3x3 + 3x4 – Mx7 – Mx8
2x1 + x2 + x3 + 2x4 + x5 = 20
→
max
x1 + 2x2 + 3x3 + 4x4 + x7 = 18
2x1 + x2 + 2x3 + x4 – x6 + x8 = 16
xj ≥ 0 (j = 1,2,3,4,5,6,7,8)
Giải bài toán mở rộng bằng phương pháp đơn hình
x1
1
x2
2
x3
3
x4
3
x5
0
1
0
0
0
x6
0
x5
x7
x8
0
20
18
16
2
1
1
2
0
-M
-M
1
2
(3)
2
-3
-5*
0
4
0
2
1
1
-3
-1
0
-1
-3
5/3
1/3
-2
-3
1/3
2/3
-5
0
1
x5
x3
x8
0
3
14
6
2/3
4/3
-5/3
1
1
0
0
0
0
1
0
0
0
0
1
0
-M
4
(4/3) -1/3
0
-1
0
0
0
0
-4/3* 1/3
0
5/3
11/4
7/4
-5/4
1
1
x5
x3
x1
0
3
1
9
5
0
0
1
0
3/4
3/4
-1/4
0
0
5/4
1/4
-3/4
0
1
3
0
.
18
0
PATU: x = (3, 0, 5, 0), f(x) = 18.
b. Bài toán đối ngẫu
g(y) = 20y1 + 18y2 + 16y3
2y1 + y2 + 2y3
→
min
≥
1
y1 + 2y2 + y3
y1 + 3y2 + 2y3
2y1 + 4y2 + y3
≥ 2
≥
≥
3
3
y1
≥ 0, y3 ≤ 0.
Tải về để xem bản đầy đủ
58 trang
27220
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Quy hoạch tuyến tính (Mới nhất)", để 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_quy_hoach_tuyen_tinh_moi_nhat.pdf
