NHỮNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

Chia sẻ: Tran Thi | Ngày: | Loại File: DOC | Số trang:19

Thêm vào BST

Báo xấu

2.644
lượt xem 357
download

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

Tại sân bay Tân Sơn Nhất có nhu cầu vận chuyển 1200 hành khách và 120 tấn hàng bằng máy bay. Giả sử có 2 loại máy bay có thể sử dụng với khả năng vận chuyển của mỗi loại như sau: Máy bay loại A: 01 máy bay có thể chở 150 hành khách và 20 tấn hàng với chi phí tương ứng 240 triệu đồng.

Chủ đề:

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

Lưu

Nội dung Text: NHỮNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

CHƯƠNG I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1/ MỘT SỐ VÍ DỤ DẪN ĐẾN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH: 1.1.1. Bài toán vận chuyển: Tại sân bay Tân Sơn Nhất có nhu cầu vận chuyển 1200 hành khách và 120 t ấn hàng bằng máy bay. Giả sử có 2 loại máy bay có thể sử dụng với khả năng vận chuyển của mỗi loại như sau: Máy bay loại A: 01 máy bay có thể chở 150 hành khách và 20 tấn hàng với chi phí tương ứng 240 triệu đồng. Máy bay loại B: 01 máy bay chở có thể chở 180 hành khách và 16 tấn hàng với chi phí tương ứng là 220 triệu đồng. Hãy lập mô hình tìm phương án sử dụng số máy bay mỗi loại sao cho phải thỏa mãn yêu cầu vận chuyển với tổng chi phí ít nhất. Lập mô hình: Gọi x1 là số lượng máy bay loại A Gọi x2 là số lượng máy bay loại B Tổng chi phí (triệu đồng): Z = 240 x1 + 220x2 Đảm bảo về hành khách: 150 x1 + 180x2 = 1200 Đảm bảo về hàng hóa: 20 x1 + 16 x2 = 120 Đảm bảo thực tế: x1,x2 ≥ 0 Giải bài toán: Z = 240 x1 + 220x2 → min (*) 150 x1 + 180 x2 = 1200   20 x1 + 16 x2 = 120  x ≥ 0; j = 1, 2 () j Giải hệ phương trình trên  x1 = 2, x2 = 5 thay x1 và x2 vào (* ) → Z = 1580 1.1.2/ Bài toán khẩu phần thức ăn : Để nuôi một loại gia súc người ta sử dụng 3 loại thức ăn A, B, C. Tỷ l ệ % theo khối lượng các chất dinh dưỡng P1, P2 có trong các loại thức ăn như sau : Thức ăn Chất dinh dưỡng P1 P2 A 20 10 B 10 10 C 10 20 Yêu cầu trong khẩu phần thức ăn của loại gia súc này:
- Chất dinh dưỡng P1 phải có ít nhất là 70g và nhiều nhất là 80g - Chất dinh dưỡng P2 có ít nhất là 90g - Giá 1kg thức ăn A,B,C tương ứng là 2.000đ, 1.000đ, 2.000đ Yêu cầu : Hãy lập mô hình bài toán xác định khố i lượng thức ăn cần mua sao cho tổng chi phí ít nhất. Lập mô hình bài toán : Gọi x1, x2, x3 tương ứng là số g thức ăn A, B, C cần mua - Tổng chi phí Z = 2x1 + x2 + 2x3 - Hàm lượng các chất dinh dưỡng P1: 0,2x1 + 0,1x2 + 0,1x3 thuộc [ 70,80] (g) P2: 0,1 x1 + 0,1x2 + 0,2 x3 ≥ 90 (g) x j ≥ 0 ( j = 1, 2,3) Bài toán: Tìm xj (j= 1,2,3) sao cho Z = 2x1+ x2 + 2x3 → min 2 x1 + x 2 + 2 x3 ≥ 700 2 x + x + x ≤ 800 1 2 3  x1 + x 2 2 x3 ≥ 900 x1 , x 2 , x3 ≥ 0  1.1.3/ Bài toán thời gian thi công ngắn nhất: Để đảm bảo hoàn thành kế hoạch, đơn vị sửa chữa và bảo dưỡng đường nhựa A cần gấp rút hoàn thành 50km sơn vạch mặt đường, trong đó số km đường được sơn kẻ vạch của đường cấp I không nhỏ hơn 20% tổng chiều dài được sơn kẻ vạch của đường cấp II và cấp III. Đơn vị A chỉ có 1 dây chuyền ( người, máy) để làm việc này. Trong khi đ ể thời gian hoàn thành 1km đường cấp I, II, III tương ứng là 12 ngày, 8 ngày và 6 ngày. Định mức tiền sơn cho 1km đường cấp I, II, III tương ứng là 30, 20 và 15 triệu đồng, trong khi kinh phí dành cho công việc này trong thời gian tới chỉ còn 120 (triệu đồng). Hãy lập mô hình xác định chiều dài sơn kẻ vạch cho mỗi cấp đường sao cho tổng thời gian thực hiện là ngắn nhất, đồng thời đảm bảo về kinh phí mua sơn. Lập mô hình: Gọi x1, x2, x3 là chiều dài (km) dự định thực hiện trong tương ứng cấp đường loại I, II, III khi đó. Mục tiêu thời gian: Z = Yêu cầu khối lượng: Yêu cầu chủng loại: Yêu cầu kinh phí Điều kiện tất yếu: x1, x2, x3 ≥ 0 Bài toán:
1.2/ ĐỊNH NGHĨA VÀ CÁC DẠNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.2.1/ Định nghĩa: Bài toán quy hoạch tuyến tính dạng tổng quát: tìm (x1, x2, …, xn) sao cho n ∑c x j → min (max) (1) f (x) = c1x1+ c2x2 + cnxn = j j =1 Với điều kiện n ≤   ∑   aij x j  bi (i = 2,.., m)(2) = 1, j =1  ≥    ≥  0    0  j =(1, 2,..., n)(3) ≤ x j   Tùyý    + Các bi gọi là các hệ số tự do + Các cj gọi là hệ số hàm mục tiêu ( hệ số) + aij gọi là hệ số các ràng buộc chung + f(x) gọi là hàm mục tiêu + Hệ (*) gọi là hệ ràng buộc (2) gọi là ràng buộc chung (có m ràng buộc) (3) gọi là ràng buộc biến (có n ràng buộc) Vector x = (x1, x2, … xn) gọi là phương án (P.A) nếu x thỏa (*) tập hợp tất cả các phương án gọi là miền ràng buộc kí hiệu là D - Một phương án làm cho hàm mục tiêu đạt cực tiểu ( ứng với bài toán tìm min của f (min f) hoặc cực đại (max f) gọi là phương án tối ưu được ký hiệu là xopt Nghĩa là: BT min: ∀ x ∈ D : f (x) ≥ f (xopt) BT max: ∀ x ∈ D : f (x) ≤ f (xopt) Giải bài toán quy hoạch tuyến tính là tìm các phần tử tối ưu (nếu có) + Hai bài toán quy hoạch tuyến tính gọi là tương đương nhau nếu chúng có chung phần tử tối ưu. Mệnh đề : Quan hệ giữa max f và min f  f ( x ) ⇒ max  g ( x ) = − f ( x ) ⇒ min  x ∈ D ⇔  x ∈ D  
1.2.2/ Biểu diễn bài toán quy hoạch tuyến tính dưới dạng ma trận: Gọi  a11 a12 ... a1n  a  A =  21   ...    am1 amn   là ma trận cấp m*n các hệ số các ràng buộc chung x1 , CT = (c1, c2, …,cn) X= … xn b1 B= …. bm Lúc đó bài toán quy hoạch tuyến tính được phát biểu Tìm x = ( x1, x2, …, xn) sao cho f(x) = CT x → min (max) thỏa mãn: A.X  B ≥ X≥0 ; trong  ≤ = 1.2.3/ Các dạng của bài toán quy hoạch tuyến tính và các quy tắc biến đổi. 1.2.3.1: Dạng chính tắc n f ( x) = ∑ c j x j → min ( max ) j =1 n  ∑ aij x j = bi (i = 1, 2..., m)  j =1 x ≥ 0 ( j = 1, 2,..., n ) j
Ta nhận xét rằng, bất kỳ bài toán quy hoạch tuyến tính nào cũng có thể đưa về dạng chính tắc nhờ các quy tắc biến đổi sau: • Nếu ràng buộc có dạng : n ∑ x j ≥bi a ij j=1 thì ta đưa về dạng tương đương : n ∑a x j − x n +1 = bi ij j =1 với xn+1 ≥ 0 là ẩn phụ) • Nếu ràng buộc có dạng : n ∑ xj ≤ i a b ij j=1 thì ta đưa về dạng tương đương n ∑a x j + xn +1 = bi ij j =1 với xn+1 ≥ 0 là ẩn phụ) Chú ý: - Hệ số của ẩn phụ trong hàm mục tiêu f(x) là 0. - Nếu biến xj ≤ 0 thì ta thay bằng xj’ : xj’ = - xj (xj’ ≥ 0) - Nếu biến xj không ràng buộc về dấu ta thay bằng hiệu của 2 biến không, tức là đặt xj = xj’ - xj’’ với xj’ ≥ 0, xj’’ ≥ 0 Chú ý rằng: Đây không phải là biến phụ nên phải tính lại hàm mục tiêu theo các biến mới. Các ví dụ: đưa các bài toán QHTT sau về dạng chính tắc 1/ f(x) = -2x1 +3x2 - 2x3 → min 2 x1 + x 2 − 2 x3 = 2  3 x1 + x3 = −3 x , x , x ≥ 0 1 2 3 Ví dụ 1 này là dạng chính tắc vì xảy ra dấu = và x1, x2, x3 ≥ 0
2/ f(x) = x1 + x2 + x3 - 2x4 → max  x1 − x2 + 2 x3 ≥ 2  5 x1 − x2 − 3 x3 = 3 x , x , x , x ≤ 0 1 2 3 4 Giải Ví dụ 2: VD2 không phải là chính tắc vì vi phạm 2 chỗ: ≥ 2; x1, x2, x3, x4 ≤0 Ta có: f(x) = x1 + x2 + x3 - 2x4 + 0 . x5 → max  x1 − x2 + 2 x3 − x5 = 2  (1) 5 x1 − x2 − 3 x3 = 3 x1 = - x1’ ; x2 = -x2’ ; x3 = -x3’, x4 = -x4’ (với x1’, x2’, x3’, x4’ ≥ 0) Ta thay x1, x2, x3, x4 vào (1)  x1 '+ x2 '−2 x3 '+ x5 ' = 2  − 5 x1 '+ x2 '+3 x3 ' = 3 Tìm x1, x2, x3, x4, x5, x1’, x2’, x3’, x4’ (x5 là ẩn phụ) 3/ f(x) = - x1 + 2x2 +1/3 x3 - 2x4 → min Tìm x1, x2, x3, x4  x1 − x2 − 3 x3 = −7  x + 2 x − x 4 ≤ −2 2 3   x1 + x3 + 2 x 4 = 1 / 2  x1 , x2 , x3 , x4 ≥ 0  Giải VD3 : VD3 này không phải chính tắc vì vi phạm một chỗ là ≤ -2 f (x) = -x1 + 2x2 + 1/3 x3 - 2x4 + 0 . x5 → min
x1 − x2 −3 x3 = −7 x + 2 x − x 4 + x = 2 2 3 5  x1 + x3 + 2 x 4 =1 / 2   Tìm x1, x2, x3, x4, x5 ≥0, (x5 là ẩn phụ) 4/ f(x) = x1 + 3x2 -2x3 → min Tìm x1, x2, x3, x2’, x2’’, x3’, x4, x5 3 x1 + x2 − 2 x3 ≤ 7 − 2 x − 4 x + x =12  2 2 3  4 x1 + 3 x2 −8 x3 ≥10 x1 ≥ 0, x3 ≤ 0  Giải bài 4: Để đưa bài toán trên về dạng chính tắc, ta phải đưa những ràng buộc bất phương trình về phương trình, đồng thời mọi ẩn số phải không âm. Có nghĩa là ràng buộc thứ nhất được cộng thêm ẩn phụ x4 ≤ 0, ràng buộc thứ 3 được trừ đi một ẩn phụ x5 ≥ 0 Thay x3 = - x3’ (x3’ ≥ 0) x2 = x2’-x2’’(x2 ≥0, x2’’ ≥0) vậy bài toán trở thành f(x) = x1 + 3x3 + 2x3’ → min 3 x1 + x2 + 2 x3 '+x4 = 7  − 2 x1 − 4 x2 − x3 ' =12 (1) 4 x +3 x +8 x '−x =10 1 2 3 5 Thay x2 vào (1) ta có 3x1 + x2 '− x2 ' '+ 2 x3 '+ x4 = 7   − 2 x1 − 4 x2 '+ 4 x2 ' '− x3 = 12  4 x + 3x '− 3x ' '+ 8 x '− x = 10 1 2 2 3 5 x1, x2’, x2’’, x3’ ≥ 0; x4, x5 ≥ 0 (x4, x5 là ẩn phụ) 1.2.3.2/ Dạng chuẩn (chuẩn tắc ) : Bài toán quy hoạch tuyến tính là dạng chuẩn BT QHTT dạng chính tắc thỏa các điều kiện sau:
- Các bi bên vế phải của các ràng buộc chung ≥ 0 - Mỗi ràng buộc chung có biến cơ sở tương ứng. Biến cơ sở là biến có hệ số là +1 ở một ràng buộc chung và hệ số là 0 ở các ràng buộc còn lại. (Tức là các biến cơ sở sẽ tạo thành một ma trận đơn vị). - Các biến không cơ sở ( không phải là biến cơ sở) gọi là biến tự do Ví dụ 1: Xem xét bài toán sau đây đã chuẩn tắc không, tìm phương án cơ bản ban đầu f = x1 + 2x2 + x3 + x4 → min  x1 + x2 − x3 = 7(1)   2 x2 + x3 + x4 = 5(2)  x ≥ 0; j = (1,2,3, 4) j Bài toán này là dạng chuẩn tắc vì phương trình (1,2) đều xảy ra dấu bằng, ràng buộc biến xj ≥0 - Hệ số hàm mục tiêu : c1 = 1, c2 = 2, c3 = 1, c4 = 1 - Ràng buộc chung : m = 2 - Ràng buộc biến : n = 4 - Hệ số ràng buộc chung : a11 = 1, a12 = 1, a13 = 1, a21 = 0, a22 = 1, a23 = 1, a24 = 1 - Các hệ số tự do: b1 = 7, b2 = 5 Ta có hệ số ma trận A= x1 x2 x3 x4 1 1 -1 0 0 2 1 1 Ta có x1, x4 là biến cơ sở ; x2, x3 là biến tự do Vậy phương án cơ bản ban đầu : x2 = x3 = 0 thay vào (1) và (2) của hệ trên ta được x1 = 7, x4 = 5. Phương án cơ bản ban đầu x = (7,0,0,5) Ví dụ 2 : f(x) = x2 - x5 → min
 x1 + x2 − 2 x5 = 1(1)   3x2 − x3 + x5 = − 3(2)   − 2 x2 + x4 + x5 = 2(3)  x j ≥ 0; j = (1, 2,...,5)  Đây chưa phải là bài toán dạng chuẩn: Phương trình trên có hệ số tự do bi = -3 nên ta nhân 2 vế với -1  x1 + x2 − 2 x5 = 1(1)  − 3x + x − x = 3(2) 235   − 2 x2 + x4 + x5 = 2(3)  x j ≥ 0; j = (1,5)  - Hệ số hàm mục tiêu : c1 = 1, c2 = -1 - Ràng buộc chung : m = 3 - Ràng buộc biến : n = 5 - Hệ số ràng buộc chung: a11 = 1, a12 = 1, a13 = 1, a14 = 1, a15 = -2, a21 = 0, a22 = -3, a23 = 1, a24 = 0, a25 = -1, a31 = 0; a32 = -2, a33 = 0, a34 = 1, a35 = 1 - Các hệ số tự do: b1 = 1, b2 = 3, b3 = 2 - Ràng buộc biến: xj≥0 Ta có hệ số ma trận: x1 x2 x3 x4 x5 A= 1 1 0 0 -2 0 -3 1 0 -1 0 -2 0 1 1 Ta có x1, x3, x4 là biến cơ sở x2, x5 là biến tự do Thay x2 = x5 = 0 vào (3) → x4 = 2 Thay x2, x5 = 0 vào (2) → x3 = 3 Thay x2, x5 = 0 vào (1) → x1 =1 Vậy phương án cơ bản ban đầu là: x = (1,0,3,2,0)
1.3/ Giải bài toán quan hệ tuyến tính 2 biến bằng phương pháp hình học : Trong trường hợp bài toán QHTT có 2 biến ta có thể giải bằng phương pháp hình học, ta áp dụng kết quả sau đây : 1/ Đường thẳng ax + by = c chia mặt phẳng tọa độ thành 2 miền, một miền là tập tất cả điểm M(x,y) thỏa ax + by > c một miền là tập tất cả các điểm M(x,y) : ax + by < c 2/ Cho đường thẳng ax + by = m, m ∈ ℜ là tập hợp các đường thẳng song song với nhau mà ta gọi là đường mức (tương ứng với giá trị của mức m) ( đ ường mức có pháp vector n = (a,b)) Nếu ta duy chuyển một đường thẳng trong họ (một đường mức) đến một đường thẳng khác trong họ theo hướng của vector n =(a,b) thì giá trị tương ứng của m tăng, còn theo hướng ngược lại thì giá trị tương ứng của m giảm. Trong thực hành giải bài toán ta áp dụng : + Vẽ pháp vector n = (a,b) chính là vector OC với C(a,b). Vẽ đường mức (d) đi qua O ⊥ với vector n. + Dịch chuyển song song các đường mức theo hướng vector n = (a,b) thì giá trị mức sẽ tăng ( ứng với bài toán fmax) và theo hướng ngược lại mức sẽ giảm (ứng với bài toán fmin) + Dịch chuyển (d) cho đến khi nào việc dịch chuyển tiếp theo không làm (d) cắt D nữa thì dừng. Khi đó các điểm OFD nằm trên đường mức cuối cùng này là lời giải cần tìm. Ví dụ 1 : f(x) = 2x1 + x2 → max  2 x1 + x2 ≥ 2 − x + 2x ≤ 6 1 2   5 x1 − x2 ≤ 15  x1 , x2 ≥ 0;  Xopt = (4,5), fmax = 13 Ví dụ 2: Cũng như VD 1 nhưng fmin Đs: X0pt1 = (0,2), Xopt2 = (1,0), fmin = 2 Ví dụ 3: f(x) = 3x1 + 4x2 → min  2 x1 − 3 x2 ≥ 2   − x1 + x2 ≥ 1 x , y ≥ 0 1 1 D = θ , bài toán vô nghiệm
Ví dụ 4: f(x) = 3x1 + 4x2 → max  2 x1 − 3x2 ≥ 2   − x1 + x2 ≤ 1 x , y ≥ 0 1 1 Để hiểu rõ hơn ý nghĩa của việc giải bài toán bằng ph ương pháp hình h ọc ta xét ví dụ thực tế sau đây: Ví dụ (5): Một công ty có 2 phân xưởng P1, P2 cùng sản xuất 2 loại sản phẩm A, B. Số đơn vị sản phẩm các loại được sản xuất ra và chi phí mỗi giờ hoạt đông P1, P2 như sau: Phân xưởng 1 Phân xưởng 2 Sản phẩm A 250 250 Sản phẩm B 100 200 Chi phí 600.000 1.000.000 Công ty nhận được yêu cầu đặt hàng là 5.000 đơn vị sản phẩm A và 3.000 đơn vị sản phẩm B. Hãy tìm cách phân phối thời gian cho mỗi phân xưởng hoạt động sao cho thỏa mãn yêu cầu đặt hàng và chi phí ít nhất. Gọi x1, x2 lần lượt là số giờ cần bố trí cho P1, P2 hoạt động.
1.4/ Phương pháp đơn hình 1.4.1/ Cơ sở của phương pháp đơn hình: Tập lồi: Tập G ∈ ℜ n được gọi là tập lồi nếu 2 điểm x, y thuộc G thì cả đoạn [x, y] cũng thuộc G Tập lồi: Không là tập lồi: Điểm cực biên : Điểm x ∈ G được gọi là điểm cực biên của G nếu trong G không một đoạn thẳng nào nhận x là điểm trong. Trở lại ví dụ ** ta thấy D có 3 điểm cực biên A 1, A2, A3 ta gọi chúng là phương án cực biên (pacb) ( phương án cơ sở, phương án cơ bản). Nhận xét : Vì tính quan trọng của phương án cực biên ta thấy để giải toán quan hệ tuyến tính ta chỉ cần xét trên tập hữu hạn các phương án cực biên. Cơ sở của phương pháp đơn hình : Để tìm phương án tối ưu của bài tập quan hệ tuyến tính ta chỉ cần xét những phương án cơ bản. Xuất phát từ một phương án cơ bản ban đầu x o nào đó. Ta tìm cách đánh giá nó. Nếu nó chưa phải là phương án tối ưu thì ta tìm cách chuyển sang một phương án cơ bản mới x1 tốt hơn. Quá trình này được lập lại chừng nào còn có khả năng thực hiện sự di chuyển ấy và vì số phương án cơ bản là hữu hạn nên sau một s ố hữu hạn bước lặp hoặc sẽ thu được phương án tối ưu của bài toán hoặc sẽ kết luận vì hàm mục tiêu không bị chặt. Ta giả sử bài toán đang ở dạng (chuẩn- fmin)
n f ( x ) =∑ j x j → in a m j=1 n ∑  aij x j = bi (i =1, m)  j =1 x ≥ 0, b ≥ 0 j i 1.4.2/Bảng đơn hình Hệ Hệ ẩn P.án c1 c2 ..... cm cm+1 cs ...... cn số cơ cơ bản bản x1 x2 ... xm xm+1 xs ..... xn c1 x1 b1 a11 a12 a1n c2 x2 b2 .... ... ..... cr xr br ar1 ar2 arm arn .... ..... ...... cm xm bm am1 am2 amm amm+1 amn ∆1 ∆2 ∆m ∆m +1 ∆m +n f(xo) f(x) Trong n ẩn ta có x1, x2, ..., xm : các ẩn cơ bản xm+1, ..,xn : các ẩn không cơ bản. Giá trị của f(x0) được tính như sau: f(x0) = c1b1+ .....+cmbm Các hệ số kiểm tra được tính bằng công thức sau n ∆ j = ∑a j aij − ci (i = 1, m) j =1 Chú ý rằng 1=2=…m =0. 1.4.3/ Thuật toán đơn hình chi tiết : (sau khi có bảng đơn hình) Bước 1: - Kiểm tra tính tối ưu của phương án : - Nếu j < 0 với mọi j (j=1,n) thì phương án tương ứng là tối ưu - Ngược lại : nếu tồn tại (có ít nhất 1) j > 0 thì chuyển sang bước 2
Bước 2: - Nếu có một j >0 mà với mọi aij ≤ 0 ( ∀ i =1,m) nghĩa là mọi phần tử trên cột xj đều không dương. Ngừng thuật toán. Kết luận bài toán không giải được - Nếu với mỗi j > 0 đều có ít nhất một aij > 0 thì chuyển sang bước 3 Bước 3: ( chọn ẩn đưa vào, ẩn đưa ra khỏi hệ ẩn cơ bản) - Ẩn xs là ẩn đưa vào nếu s = max{j >0}. - Ẩn đưa ra xr bi br λ = min (ars ≥ 0 ) = ais ars Phần tử ars nằm trên cột xs ( ứng với ẩn đưa vào) và dòng x r (ứng với ẩn đưa ra) gọi là phần tử trục ( lưu ý rằng ars >0). Sau khi xác định được ần đưa vào và đưa ra ta chuyển sang bước 4. Bước 4: (Cải tiến : tìm phương án cơ bản mới tốt hơn) Xây dựng bảng đơn hình mới tương ứng với hệ ẩn cơ bản mới thu được từ hệ ẩn cơ bản trước bằng cách thay xr bởi xs ( trên cột hệ số ta thay cr bởi cs) - Để thu được dòng xs (mới được đưa vào) ta chia dòng xr cho ars - Bảng đơn hình mới : Trên dòng xs cũ thì ars = 1 các phân tử còn lại bằng 0, s = 0. Các phần tử còn lại (kể cả dòng j) ta tính theo quy tắc hình chữ nhật ajk (mới) = ajk (cũ) ark. ajs ars Cột k cột s Dòng r ark ars chia nhân Dòng j zjk? ajs Sau đó quay lại bước 1 Cứ tiếp tục chạy thuật toán như trên theo thứ tự bước 1 -> bước 2->bước 3-> bước 4->bước 1->,,,vv. Và trả lời yêu cầu bài toán. Ví dụ 1: Giải bài toán quan hệ tuyến tính sau: f(x) = 6x1 + x2 + x3 + 3x4 + x5 - 7x6 + 6x7 → min
 − x1 + x 2 − x 4 + x6 + x7 = 3 − 2x + x − 4x + 2x − x = 9  1 3 4 6 7   4 x1 + 2 x 4 + x5 − 3x6 = 2  x j ≥ 0; ( j = 1,7 )  Bài toán có dạng chuẩn với phương án cơ bản ban đầu x0 = (0,3,9,0,2,0,0) có các ẩn cơ bản x2, x3, x5 (n=7, m=3) ta có bảng đơn hình. Hệ số Hệ ẩn P.án 6 1 1 3 1 -7 6 cơ x1 x2 x3 x4 x5 x6 x7 bản 1 x2 3 -1 1 0 -1 0 [1] 1 1 x3 9 -2 0 1 -4 0 2 -1 1 x5 2 4 0 0 2 1 -3 0 f(x) 14 -5 0 0 -6 0 7 -6 Với f(x0) = C1b1 + c2b2 + c3b3 = 1.3 + 1.9 + 1.2 = 14 2 = 3 = 5 = 0 (vì x2, x3, x5 là ẩn cơ bản) 2 = 1 * 1 + 1 * 0 + 1 * 0 - 1 = 0 4 = 1 * (-1) + 1 * (-4) + 1*2 - 3 = - 6 6 = 1*1+1*2+1*(-3) - (-7) = 7 7 = 1*1+1*(-1) + 1*0 -6 = -6 Ta đã có đầy đủ thông tin trên bảng đơn hình, nên ta bắt đầu dùng thuật toán đơn hình với bước bắt đầu là bước 1 Bước 1: Ta thấy có 6 = 7 > 0 chuyển sang bước 2 Bước 2: Ta thấy 6 > 0 có a16, a26 > 0 chuyển sang bước 3 Bước 3: Chọn ẩn đưa vào ta đi tìm các cột có j >0, tuy nhiên ở ví dụ này chỉ có 6 > 0 nên x6 là ẩn đưa vào. Chọn ẩn đưa ra : Ta có : a16 =1, a26 = 2, (a16, a26 >0) 3 9  3 λ = min  ;  = suy ra x2 là ẩn cơ bản bị loại khỏi hệ ẩn cơ bản phần tử a16 = 1 1 2  1 được đóng khung ars = a16 = 1 chuyển sang bước 4 Bước 4: Xây dựng bảng đơn hình mới Hệ số Hệ ẩn P.án 6 1 1 3 1 -7 6 cơ X1 X2 X3 X4 X5 X6 X7 bản -7 X6 3 -1 1 0 -1 0 1 1 1 X3 3 0 -2 1 -2 0 0 -3 1 X5 11 1 3 0 -1 1 0 3 f(x) -7 2 -7 0 1 0 0 -13
Ta thay x2 bằng x6 với hệ số của x6 là -7 ta cần tính lại 8*4 = 32 đại lượng trong bảng mới theo các công thức trong bước 4. Sau khi tính toàn bộ các giá trị trong bảng đơn hình mới ta quay lại bước 1: Ta thấy 1 > 0; 4 > 0 suy ra bước 2. Tại 4 = 1 > 0 có tất cả a14, a24, a34 suy ra ngừng thuật toán. Kết luận bài toán đã cho không có phương án tối ưu: Ví dụ 2: Giải bài toán quan hệ tuyến tính sau: f(x) = x1+ 4x2 - x3 - x4 + x5 + 3x6 → min  2 x1 − x 2 + 5 x3 + x 4 = 1 2x + 4x − 2x + x = 2 1 2 3 5   x1 + 2 x 2 + x3 + x6 = 5  x j ≥ 0; ( j = 1,6)  Bài toán có dạng chuẩn , với phương án cơ bản ban đầu x0 = (0,0,0,1,2,5) Các ẩn cơ bản x4, x5, x6 ( n = 6, m = 3) Ta có bảng đơn hình: Hệ số Hệ ẩn P.án 1 4 -1 -1 1 3 cơ bản x1 x2 x3 x4 x5 x6 -1 x4 1 2 -1 5 1 0 0 1 x5 2 2 [4] -2 0 1 0 3 x6 5 1 2 1 0 0 1 f(x) 16 2 7 -3 0 0 0 Với f(x0) = c1b1 + c2b2 + c3b3 = (-1) * 1 + 1 * 2 + 3 * 5 = 16 4 = 5 = 6 = 0 (vì x4, x5, x6 là ẩn cơ bản) 1 = (-1) * 2 + 1 * 2 + 3 * 1 - 1 = - 2 + 2 + 3 - 1 = 2 2 = (-1) * (-1) + 1 * 4 + 3 * 2 - 4 = 1 + 4 + 6 - 4 = 7 3 = ( -1) * 5 + 1 * (-2) + 3 * 1 - (-1) = - 5 -2 + 3 + 1 = - 3 Ta đã có đầy đủ thông tin trên bảng đơn hình, nên ta bắt đầu dùng thuật toán đơn hình với bước đầu là bước 1. Bước 1 : Có 2 = 7 > 0 chuyển sang bước 2 Bước 2 : Ta thấy có 2 >0 và có a22 và a32 >0 chuyển sang bước 3 Bước 3 : Chọn ẩn đưa vào :
- Ta đi tìm các cột j >0; tuy nhiên ở bài này có 2 > 0 nên x2 là ẩn đưa vào - Chọn ẩn đưa ra : Ta có a22 = 4, a32 = 2 (a22, a32 > 0) γ = min  2 , 5  = 2 → x5 là ẩn cơ bản bị loại khỏi hệ ẩn cơ bản   4 2 4 Phần tử a22 = 4 được đóng khung ars = a22 = 4 chuyển sang bước 4 Bước 4: Xây dựng đơn hình mới Hệ số Hệ ẩn P.án 1 4 -1 -1 1 3 cơ X1 X2 X3 X4 X5 X6 bản -1 X4 3/2 5/2 0 9/2 1 ¼ 0 4 X2 ½ ½ 1 -1/2 0 ¼ 0 3 X6 4 0 0 2 0 -1/2 1 F(x) 25/2 -3/2 0 1/2 0 -7/4 0 - Chọn ẩn đưa vào: ta có 3 > 0; lại có a13 và a33 > 0 → chọn x3 là ẩn đưa vào  6 4 6 - Chọn ẩn đưa ra: γ = min  → x4 là ẩn đưa ra. phần tử a13 là phần tử , = 18 2  18 đóng khung; vậy ars = a13 = 9/2 Hệ số Hệ ẩn P.án 1 4 -1 -1 1 3 cơ X1 X2 X3 X4 X5 X6 bản -1 X3 1/3 5/9 0 1 2/9 1/18 0 4 X2 2/3 7/9 1 0 1/9 5/18 0 3 X6 10/3 -10/9 0 0 -4/9 -11/18 1 f(x) 37/3 -16/9 0 0 -1/9 -16/9 0 1= (-1) * 5/9 + 4 * 7/9 + 3 * (-10)/9 - 1= - 16/9 4= - (-1) * 2/9 + 4 * 1 /9 +3 * (-4/9) - (-1) = - 1/9 5= (-1) * 1/18 + 4 * 5/18 + 3 * (-11/18) - 1 = - 16/9  10  21 Vậy bài toán có phần tử tối ưu là xopt =  0, , ,0,0,  ; f(min) =37/3  3 33 Chú ý : Bài toán dạng chuẩn f max. Cách 1 : ( gián tiếp : đưa về dạng chuẩn f → min) BT1 f → Max  g=-f → min BT2 X∈D X∈D Nếu xopt là phần tử tối ưu của bài tập 1 ⇔ x cũng là phần tử tối ưu của bài toán 2. Và giá trị của hàm mục tiêu là fmax = - gmin. Cách 2: (Trực tiếp)
Thuật toán cũng giống như thuật toán ở dạng f → min. Chỉ thay đổi Bước 1: Nếu j ≥ 0 ∀ j thì phương án là tối ưu Bước 2: Nếu có một j < 0 mà ∀ aij ≤ 0 ⇒ ngừng thuật toán kết luận bài toán không giải được. Bước 3: Chọn ẩn đưa vào: s = min j, j < 0 (ẩn đưa vào ẩn cơ bản là ẩn có j âm bé nhất) Ví dụ: f = - x1 + 4x2 + 2x3 - x4 ⇒ max 2 x1 − x2 + x3 = 4  3 x1 + x2 + x4 = 7  x ≥ 0; ( j = 1,4 ) j Giải: f = -x1 + 4x2 + 2x3 - x4 → min 2 x1 − x3 + x3 = 4  3 x1 + x2 + x4 = 7  x ≥ 0; ( j = 1,4 ) j - Hệ số mục tiêu: c1= - 1; c2 = 4; c3 = 2; c4 = - 1 - Hệ số tự do: b1 = 4, b2 = 7 - Ràng buộc chung m = 2 - Ràng buộc biến n = 4 - Hệ số của các ràng buộc chung: a11 = 2, a12 = - 1, a13 = 1, a21 = 3, a22 = 1, a23 = 1 G = - f → min → x1 - 4x2 - 2x3 + x4 → min fmax = - gmin (x0) = (0,0,4,7) Hệ số Hệ ẩn P.án 1 -4 -2 1 cơ X1 X2 X3 X4 bản -2 X3 4 2 -1 1 0 1 X4 7 3 1 0 1 f(x) -1 -2 -1 0 0 j 1 2 3 4 Đáp số: xopt của bài toán II : x = (0,7,11,0), gmin = - 50 Cách 2: Tính trực tiếp
Hệ số Hệ ẩn cơ P.án -1 4 2 -1 bản cơ bản X1 X2 X3 X4 2 X3 4 2 -1 1 0 -1 X4 7 3 1 0 1 F(x) 1 2 -7 0 0 2 X3 11 5 0 1 1 4 X2 7 3 1 0 0 f(x) 50 23 0 0 7 ⇒ xopt = (0,7,11,0) ; fmax = 50 1.5/ Thuật toán đơn hình giải bài toán QHTT dạng tổng quát Khi xây dựng thuật toán đơn hình ta giả thiết là đã biết một phương án cơ bản tức là bài toán có dạng chuẩn. Tuy nhiên trong thực tế không phải bài toán quan hệ tuyến tính nào cũng có dạng chuẩn. Đó là lý do người ta cần một thuật toán giải đ ược bài toán QHTT dạng tổng quát. 1.5.1/ Đưa bài toán QHTT dạng tổng quát về dạng chuẩn (bài toán M) Nếu bài toán QHTT (dạng chính tắc, bi ≥ 0) không có ngay phương án cơ bản ban đầu thì ta thêm một số biến giả vào để có ngay phương án cơ bản ban đầu. Bài toán có biến giả gọi là bài toán (M). Ví dụ: Cho bài toán gốc (p) f = x1 - 2x2 +3x3 + x4 → min 4 x1 + x2 + 2 x3 + 2 x4 = 1   x1 − 2 x2 + 5 x3 − 4 x4 = 6  x ≥ 0; ( j = 1,4 ) j Hãy viết bài toán M