Quy hoạch tuyến tính | Đại học Sư phạm Hà Nội
Quy hoạch tuyến tính | Đại học Sư phạm Hà Nội với những kiến thức và thông tin bổ ích giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học vào thực tiễn cuộc sống.
Môn: Nhập môn lý thuyết ma trận
Trường: Đại học Sư Phạm Hà Nội
Thông tin:
Tác giả:
Preview text:
Chương 2 Quy hoạch tuyến tính
2.1 Bài toán Quy hoạch tuyến tính
2.1.1 Bài toán dạng tổng quát
Bài toán quy hoạch tuyến tính có dạng min (hoặc max) f (x) = cT x Aix = bi, i ∈ I1, Aix ≥ bi, i ∈ I2, Aix ≤ bi, i ∈ I3, xj ≥ 0, j ∈ J1, xj ≤ 0, j ∈ J2, xj ∈ R, j ∈ J3, trong đó
A là ma trận cấp m × n, c, x ∈ Rn, b ∈ Rm, A là dòng thứ , i i của ma trận A I , ,
là các tập chỉ số rời nhau và I1 ∪ I2 ∪ I3 = I := {1, . . . , m}, 1 I2 I3 J , ,
là các tập chỉ số rời nhau và J1 ∪ J2 ∪ J3 = J := {1, . . . , n}. 1 J2 J3 41
2.1.2 Bài toán dạng chính tắc và dạng chuẩn tắc
Cho A là ma trận cấp m × n; c ∈ Rn, và b ∈ Rm. Bài toán quy hoạch tuyến tính dạng chính tắc max f (x) = cT x Ax = b, x ≥ 0. dạng chuẩn tắc max f (x) = cT x Ax ≤ b, x ≥ 0.
Ở đây, ký hiệu x ≥ 0 được hiểu là tất cả các thành phần của x là các số thực không âm.
Chúng ta luôn có thể đưa một bài toán dạng tổng quát về dạng chính tắc hoặc chuẩn tắc.
Ví dụ 2.1. Đưa bài toán sau về dạng chính tắc f(x) = x1 − 2x 2 → min x1 + x2 ≥ 3 x1 − 2x 2 ≤ 2 x1 ≤ 0. Đặt x với với t2, t3 ≥ 0; 1 = −t1 t1 ≥ 0; x2 = t2 − t3 g(t) = −f(x) = −x ; 1 + 2x2 = t1 + 2t2 − 2t3
t4 = (x1 + x2) − 3 = (−t1 + t2 − t3) − 3;
t5 = 2 − (x1 − 2x2) = t1 + 2t2 − 2t3 + 2.
Ta có bài toán dạng chính tắc
g(t) = t1 + 2t2 − 2t3 → max
−t1 + t2 − t3 − t4 = 3
−t1 − 2t2 + 2t3 + t5 = 2 tj ≥ 0, j = 1,2,3,4
Ví dụ 2.2. Đưa bài toán sau về dạng chuẩn tắc f(x) = 2x 1 − x2 → min x1 + x2 = 3 x1 − 2x 2 ≤ 2 x1 ≥ 0,x2 ≥ 0. 42
Ta đưa về bài toán dạng chuẩn tắc g(x) = −2x1 + x 2 → max x1 + x2 ≤ 3 −x 1 − x2 ≤ −3 x1 − 2x 2 ≤ 2 x1 ≥ 0, x2 ≥ 0. 2.2 Ví dụ
2.2.1 Bài toán lập kế hoạch sản suất
Một nhà máy sản xuất n sản phẩm H là cj.
1, H2, . . . , Hn với giá bán 1 đơn vị sản phẩm Hj
Để sản xuất các sản phẩm trên, nhà máy cần dùng m nguyên liệu K1, K2, . . . , Km với trữ lượng của nguyên liệu K là i bi đơn vị.
Để sản xuất 1 đơn vị sản phẩm H đơn vị nguyên liệu Ki. j , cần sử dụng aij
Nhà máy cần lập kế hoạch sản xuất để tổng giá trị của các sản phẩm là lớn nhất.
Gọi số đơn vị sản phẩm Hj được sản xuất là xj. Hiển nhiên xj ≥ 0 với mọi j = 1, 2, . . . , n.
Tổng giá trị của các sản phẩm là n X f (x) = cjxj. j=1 n Số đơn vị nguyên liệu P K . Do đó, i được sử dụng là aijxj j=1 n X aijxj ≤ bi. j=1 Chúng ta có bài toán n X max f (x) = cjxj j=1 n
X aijxj ≤ bi, ∀i = 1,2,...,m, j=1
xj ≥ 0, ∀j = 1, 2, . . . , n. 43 Bài toán vận tải
Có m kho hàng K1, K2, . . . , Km với trữ lượng hàng lần lượt là a1, a2, . . . , am.
Cần chuyển hàng tới n điểm tiêu thụ hàng hóa T1, T2, . . . , Tn với nhu cầu là b1, b2, . . . , bn.
Giá thành vận chuyển từ K đến là i Tj cij/đơn vị hàng.
Giả sử rằng chúng ta có điều kiện cân bằng thu phát (tức là tổng nhu cầu bằng tổng trữ lượng).
Cần lên phương án vận chuyển hàng sao cho tất cả các nơi tiêu thụ đều nhận được đủ hàng và
tổng chi phí vận chuyển là nhỏ nhất.
Gọi số đơn vị hàng được chuyển từ kho K là xij. i đến nơi tiêu thụ Tj
Hiển nhiên xij ≥ 0 với mọi i = 1, 2, . . . , m và j = 1, 2, . . . , n.
Tổng chi phí vận chuyển là m X n X f (x) = cijxij. i=1 j=1 Chúng ta có bài toán m X n X min f (x) = cijxij i=1 j=1 n X xij = ai, ∀i = 1,2,...,m, j=1 m X xij = bj, ∀j = 1,2,...,n, i=1
xij ≥ 0, ∀i = 1, 2, . . . , m, ∀j = 1, 2, . . . , n. 44
2.3 Cấu trúc tập phương án của bài toán quy hoạch tuyến tính
Chúng ta xét bài toán quy hoạch tuyến tính dạng chính tắc max f (x) = cT x Ax = b, (P) x ≥ 0,
trong đó A là ma trận cấp m × n, c, x ∈ Rn, và b ∈ Rm.
Tập phương án của bài toán được ký hiệu là X.
Mệnh đề 2.3. Tập phương án X là một tập lồi.
Véctơ cột thứ j của ma trận A được ký hiệu là Aj. Đặt J := {1, . . . , n}.
Với mỗi điểm x ≥ 0, ký hiệu n o J+(x) = j ∈ J | xj > 0 .
Chú ý 2.4. Với mọi x ∈ X, chúng ta có đẳng thức n X X b = x j j Aj = xjA . j=1 j∈J+(x)
Có thể dễ thấy rằng nếu 0 ∈ X thì x := 0 là một phương án cực biên của bài toán (P). 45
Định lý 2.5. Giả sử ¯x = 0 là một phương án của bài toán (P). Khi đó, ¯x là một phương án n o
cực biên của (P) khi và chỉ khi hệ véctơ Aj | j ∈ J+(¯x) độc lập tuyến tính.
Chứng minh. Trước hết chúng ta chứng minh điều kiện cần bằng phương pháp phản chứng: n o Giả sử ¯
x là phương án cực biên của X nhưng hệ
Aj | j ∈ J+(¯x) phụ thuộc tuyến tính.
Khi đó tồn tại các số thực αj, với j ∈ J+(¯x), không đồng thời bằng 0, sao cho X αjAj = 0. j∈J+(¯x)
Chọn α ∈ Rn với αj = 0 nếu j /∈ J+(¯x). Hiển nhiên α = 0.
Với t > 0, chúng ta xét hai véctơ x1 = ¯x + tα và x2 = ¯x − tα.
Ta có x1 = x2 và ¯x = 1 x1 + 1x2. 2 2 Từ n X n X n X n X x1 j j j Aj = (¯ xj + tαj)Aj = ¯ xjA + t αjA = b, j=1 j=1 j=1 j=1
suy ra Ax1 = b. Tương tự, chúng ta có Ax2 = b. Để ý rằng, x1 = x2 j j = 0 với mọi j /
∈ J+(¯x). Chúng ta có thể chọn được số dương t để x1j > 0
và x2j > 0 với mọi j ∈ J+(¯x). Với t đã chọn, các điểm x1, x2 là các phương án của bài toán (P).
Do đó ¯x không phải là phương án cực biên của bài toán (P), mâu thuẫn với giả thiết. Chúng
ta có điều phải chứng minh.
Tiếp theo chúng ta chứng minh điều kiện đủ. Giả sử ¯x = (1 − λ)y + λz với y, z thuộc vào X
và λ ∈ (0, 1). Dễ dàng kiểm tra được yj = zj = 0 với mọi j /∈ J+(¯x). Do đó, chúng ta có X X X b = ¯ x j j Aj = yjAj = zjA . j∈J+(¯x) j∈J+(¯x) j∈J+(¯x)
Kết hợp các đẳng thức đó với sự độc lập tuyến tính của hệ {Aj | j ∈ J+(¯x)}, chúng ta thu được ¯x với mọi j = yj = zj
j ∈ J+(¯x). Như vậy, y = z = ¯x. Từ đó, kết luận được ¯x là điểm cực biên của X.
Hệ quả 2.6. Mỗi phương án cực biên của bài toán (P) có không quá m thành phần dương.
Phương án cực biên ¯x của (P) được gọi là không suy biến nếu nó có đúng m thành phần
dương. Ngược lại, phương án cực biên ¯x được gọi là suy biến.
Áp dụng phần chứng minh điều kiện cần trong việc chứng minh Định lý 2.5, chúng ta thu
được các kết quả sau đây.
Hệ quả 2.7. Giả sử ¯x ∈ X là không phải là một phương án cực biên của bài toán (P). Khi đó
tồn tại hai phương án x1, x2 sao cho ¯
x = 1 x1 + 1x2 và J+(x1) ⊊ J+(¯ x). 2 2 46
Ví dụ sau đây được thiết kế để minh họa cho Định lý 2.5. Ví dụ 2.8. Xét bài toán
max f (x) = 2x1 + 3x2 − x3 + x4 x1 + 2x2 + 2x3 + x4 = 3 2x1 + 4x2 + x3 + 3x4 = 6 x ≥ 0.
Sử dụng Định lý 2.5, chúng ta dễ dàng tìm được tất cả các phương án cực biên của bài toán, T 9 T đó là: 3 3 x1 = (3; 0; 0; 0)T , x2 = 0; ; 0; 0 , x3 = 0; 0; ; . 2 5 5
Kết quả sau đây là nền tảng của thuật toán đơn hình giải bài toán quy hoạch tuyến tính.
Định lý 2.9. Nếu bài toán (P) có phương án thì sẽ có phương án cực biên. Nếu bài toán (P)
có phương án tối ưu thì sẽ có một phương án cực biên là tối ưu.
Chứng minh. Lấy x0 là một phương án tùy ý của (P). Nếu x0 = 0 thì hiển nhiên x0 là một
phương án cực biên. Nếu x0 = 0 không phải là một phương án cực biên, thì áp dụng Hệ quả 2.7,
tồn tại phương án x1 có thành phần dương ít hơn so với x0. Do số thành phần dương của một
phương án là một số không âm, nên cứ tiếp tục như vậy, chúng ta sẽ tìm được một phương án cực biên.
Tiếp theo, giả sử ¯x là một phương án tối ưu của (P). Nếu ¯x = 0 thì hiển nhiên ¯x là một
phương án cực biên tối ưu. Nếu ¯x = 0 không phải là cực biên, thì áp dụng Hệ quả 2.7, tồn tại
phương án x1 có thành phần dương ít hơn so với ¯x, và phương án x2 sao cho ¯x = 1x1 + 1 x2. Dễ 2 2
dàng kiểm tra được x1, x2 cũng là các phương án tối ưu. Như vậy, chúng ta có được phương án
tối ưu x1 có thành phần dương ít hơn so với ¯x. Do số thành phần dương của một phương án là
một số không âm, nên cứ tiếp tục như thế, chúng ta sẽ tìm được một phương án cực biên tối ưu.
Ví dụ 2.10. Chúng ta cùng giải bài toán đã được xem xét ở Ví dụ 2.8. Dễ thấy rằng tập
phương án X là đóng và bị chặn, hàm mục tiêu f liên tục nên bài toán có phương án tối ưu.
Do đó, nó phải có phương án cực biên là tối ưu. Tính được 9 6
f (x1) = 6, f (x2) = ; f (x3) = . 2 5
Do đó x1 là phương án cực biên tối ưu của bài toán đã cho.
Định lý 2.11. Số phương án cực biên của (P) là hữu hạn. 47 2.4 Thuật toán đơn hình
2.4.1 Cơ sở lý luận của phương pháp đơn hình
Chúng ta xét bài toán quy hoạch tuyến tính (P) ở dạng chính tắc max f (x) = cT x Ax = b, (P) x ∈ Rn+
trong đó A là ma trận cấp m × n, b ∈ Rm, c ∈ Rn, x ∈ Rn.
Giả sử rằng bài toán (P) có tất cả phương án cực biên không suy biến (tức là tất cả các
phương án cực biên đều có đúng m thành phần dương).
Do đó, trong ma trận A có m cột lập thành một ma trận khả nghịch cấp m, ký hiệu là B.
Các cột còn lại lập thành ma trận N cấp m × (n − m).
Các chỉ số của các cột ứng với B và N lập thành hai tập J và JN. B
Các hệ số trong c và ẩn x ứng với các cột của B lập thành các véctơ tương ứng là c và B xB thuộc Rm.
Các ẩn trong x được gọi là các B ẩn cơ sở.
Các hệ số trong c và ẩn x ứng với các cột của N lập thành các véctơ c và thuộc Rn−m. N xN
Các ẩn trong x được gọi là các N ẩn phi cơ sở.
Hệ phương trình Ax = b được viết lại dưới dạng BxB + NxN = b.
Điều này tương đương với x −1 −1 B = B b − B NxN. (2.1)
Chúng ta xét ¯x ∈ Rn với ¯xN = 0 và ¯xB = B−1b.
Nếu ¯xB ≥ 0 thì ¯x là một phương án chấp nhận được của (P), hơn thế nữa nó còn là một phương án cực biên. Chúng ta có f (x) = cT x = cTBxB + cTNxN = cT 1 B B− − b − B 1NxN + cTNxN
= cTBB−1b + cTN − cTBB−1N xN T = f (¯ x) + cN − (B−1N)T cB xN . Ký hiệu ∆ T
N := cN − (B−1N ) cB ∈ Rn−m.
Các thành phần của véctơ ∆ được gọi là N
ước lượng của các ẩn phi cơ sở đối với cơ sở B. 48 Khi đó, f (x) = f (¯ x) + ∆TN xN . (2.2) Tình huống 1. ∆ . N ≤ 0
Công thức (2.2) suy ra f(x) ≤ f(¯x) với mọi x ∈ X. Do đó ¯x là một phương án tối ưu của bài toán (P).
Dấu hiệu tối ưu: Nếu ∆N ≤ 0 thì ¯x là một phương án tối ưu của bài toán (P).
Khi đó x ∈ Rn là một phương án tối ưu của bài toán (P) khi và chỉ khi + x và k = 0 nếu k ∈ JN ∆k < 0, x và ∆ k ≥ 0 nếu k ∈ JN k = 0, x −1 −1 B = B b − B NxN.
Hai trường hợp đặc biệt: Nếu ∆ thì k < 0 với mọi k ∈ JN ¯
x là phương án tối ưu duy nhất của bài toán (P).
Nếu ∆k = 0 với mọi k ∈ JN thì mọi phương án của bài toán đều là phương án tối ưu.
Tình huống 2. Tồn tại chỉ số k để ∆k > 0 0. 0 ∈ JN
Trong tình huống này, chúng ta chưa thể kết luận được gì về tính tối ưu của phương án ¯x đối với bài toán (P).
Chúng ta đi tìm một phương án cực biên x1 sao cho f(x1) > f(¯x).
Chúng ta chọn x1k = θ với θ là số thực dương, và x1 N ∪ { 0}. 0 k = 0 với mọi k / ∈ J k
Do công thức (2.1), chúng ta thu được
x1j = (B−1b)j − (B−1N)jk . θ, ∀j ∈ J 0 B . (2.3)
Theo công thức (2.2) chúng ta có f (x1) = f (¯ x) + ∆k θ. 0
•Tình huống 2a. Nếu (B−1N)jk ≤ 0 với mọi j ∈ JB. 0
Khi đó x1 là phương án của bài toán (P) với mọi θ > 0.
Dễ dàng thấy rằng f(x1) → +∞ khi θ → +∞.
Dấu hiệu hàm mục tiêu không bị chặn trên ở trên tập phương án:
Nếu tồn tại chỉ số k ∈ JN sao cho ∆k > 0 và (B−1N)jk ≤ 0 với mọi j ∈ JB, thì hàm
mục tiêu f không bị chặn trên ở trên tập phương án X. 49
Ta có hướng tăng vô hạn h ∈ Rn xác định bởi a nếu jk j ∈ JB hj = −1 nếu j = k 0 nếu j / ∈ JB ∪ {k}.
Thật vậy, với mọi số thực dương θ ta có ¯x − θh ∈ X và f(¯x − θh) = f(¯x) + θ∆ . k
•Tình huống 2b. Tồn tại j ∈ J để (B−1N)jk > 0 0. B Khi đó chúng ta chọn (B−1b) θ = min j | j ∈ J > 0 . (2.4) (B−1N ) B , (B−1N )jk0 jk0 Giả sử (B−1b) θ = j0
với chỉ số j0 ∈ JB. Xác định phương án x1 với (B−1N )j0k0 θ nếu j = k 0
(B−1b)j − (B−1N) . θ nếu j ∈ J x1 jk0 B \ {j0} j = 0 nếu j = j 0 0 nếu j / ∈ (JB ∪ {k0}) .
Hiển nhiên, J+(x1) ⊂ (JB ∪ {k0}) \ {j0}. 50
Ví dụ 2.12. Chúng ta xét bài toán sau
max f (x) = 2x1 − x2 + 2x3 + x4 + mx5 x1 + x3 + x4 − x5 = 6
x1 + x2 − x3 + 2x4 − 2x5 = 10 x ≥ 0.
(a) Giải bài toán đã cho với m = −4.
(b) Giải bài toán đã cho với m = 3. Giải Ma trận cơ sở 1 0 x 2
B gồm các cột A1 và A2, tức là B = . Ta có x 1 , c , 1 1 B = x B = 2 −1 2 x 1 1 −1 3 N = , c 1, x x . −1 2 −2 N = N = 4 m x5 Tính được 1 0 6 1 1 −1 B−1 = , B−1b = và B−1N = . Do đó −1 1 4 −2 1 −1 (x B−1N x x ∈ X ⇔ B = (B−1b) − ( ) N x ≥ 0 x1 = 6 − (x3 + x4 − x5) ⇔ x2 = 4 − (−2x3 + x4 − x 5) x ≥ 0
Do đó, chúng ta có phương án cực biên xuất phát x0 = (6; 4; 0; 0; 0)T .
a) Xét bài toán đã cho với m = −4. 2 4 −2 Do c và T nên . N = 1 (B−1N ) cB = 1 ∆N = 0 −4 −1 −3
Ta có f(x0) = 8 và f(x) = 8 − 2x3 − 3x5 ≤ 8 với mọi phương án x. Do đó x0 là phương án
cực biên tối ưu của bài toán.
Tập phương án tối ưu của bài toán Sol(P) = x ∈ X | f(x) = 8 = x ∈ X | x3 = x5 = 0
= x ∈ R5+ | x3 = x5 = 0, x1 = 6 − x4, x2 = 4 − x4 n o
= (6 − t; 4 − t; 0; t; 0)T | 0 ≤ t ≤ 4 . 51
b) Xét bài toán đã cho với m = 3. 2 4 −2 Do c và T nên . N = 1 (B−1N ) cB = 1 ∆N = 0 3 −1 4
Ta có f(x0) = 8 và f(x) = 8 − 2x với mọi phương án x. 3 + 4x5
Chúng ta giữ x3 = 0 và tăng x5. Dễ dàng nhận thấy x5 có thể tiến ra +∞. Với phương án
x(t) = (6 + t; 4 + t; 0; 0; t), trong đó t ≥ 0, chúng ta có f x(t) = 8 + 4t. Từ đó có thể kết luận
rằng hàm mục tiêu f không bị chặn trên ở trên tập phương án X.
Ví dụ 2.13. Chúng ta xét bài toán sau
max f (x) = 2x1 − x2 + 2x3 + 2x4 − 4x5 x1 + x3 + x4 − x5 = 6
x1 + x2 − x3 + 2x4 − 2x5 = 10 x ≥ 0. Giải Ma trận cơ sở 1 0 x 2
B gồm các cột A1 và A2, tức là B = . Ta có x 1 , c , 1 1 B = x B = 2 −1 2 x 1 1 −1 3 N = , c 2 , x x . −1 2 −2 N = N = 4 −4 x5 Tính được 1 0 6 1 1 −1 B−1 = , B−1b = và B−1N = . Do đó −1 1 4 −2 1 −1 (x B−1N x x ∈ X ⇔ B = (B−1b) − ( ) N x ≥ 0 x1 = 6 − (x3 + x4 − x5) ⇔ x2 = 4 − (−2x3 + x4 − x 5) x ≥ 0
Chúng ta có phương án cực biên xuất phát x0 = (6; 4; 0; 0; 0)T . 2 4 −2 Do c T N = 2 và (B−1N ) c nên B = 1 ∆N = 1 . −4 −1 −3
Ta có f(x0) = 8 và f(x) = 8 − 2x với mọi phương án x. 3 + x4 − 3x5 Chúng ta giữ x
. Dễ dàng nhận thấy x4 ≤ 4. Chọn 3 = x5 = 0 và tăng x4 x4 = 4 và được
phương án x1 = (2; 0; 0; 4; 0). Vì các cột A1 và A4 độc lập tuyến tính nên x1 là một phương án
cực biên. Do f(x1) = 12 > f(x0) nên x1 là phương án cực biên tốt hơn x0. 52
Tiếp theo, chúng ta kiểm tra tính tối ưu của phương án cực biên x1. Ma trận cơ sở 1 1 x 2
B gồm các cột A1 và A4, tức là B = . Ta có x 1 , c , 1 2 B = x B = 4 2 −1 x 0 1 −1 2 N = , c 2 , x x . 1 −1 −2 N = N = 3 −4 x5 Tính được 2 −1 2 −1 3 0 B−1 = , B−1b = và B−1N = . Do đó −1 1 4 1 −2 −1 (x B−1N x x ∈ X ⇔ B = (B−1b) − ( ) N x ≥ 0 x1 = 2 − (x2 + 3x3) ⇔ x4 = 4 − (x2 − 2x3 − x 5) x ≥ 0 −1 0 −1 Do c và T nên . N = 2 (B−1N ) cB = 2 ∆N = 0 −4 −2 −2
Ta có f(x1) = 12 và f(x) = 12 − x2 − 2x5 ≤ 12 với mọi phương án x. Do đó x1 là phương
án cực biên tối ưu của bài toán.
Tập phương án tối ưu của bài toán Sol(P) = x ∈ X | f(x) = 12 = x ∈ X | x2 = x5 = 0
= x ∈ R5+ | x2 = x5 = 0, x1 = 2 − 3x3, x4 = 4 + 2x3 2 =
(2 − 3t; 0; t; 4 + 2t; 0)T | 0 ≤ t ≤ . 3 53
2.4.2 Thuật toán đơn hình với cơ sở có sẵn
Trong mục này, chúng ta giả sử rằng trong A có sẵn m cột lập thành ma trận đơn vị cấp m
và b ≥ 0. Thuật toán đơn hình gốc này có thêm bước biến đổi hệ phương trình Ax = b thành
một hệ phương trình tương đương để sao cho cơ sở B tại mỗi bước luôn là một ma trận đơn vị cấp m.
Ví dụ 2.14. Chúng ta xét bài toán sau f(x) = x1 + 2x2 → max x1 + x2 ≤ 8 2x1 + x2 ≤ 13, x ≥ 0.
Đưa bài toán đã cho về dạng chính tắc f(x) = x1 + 2x2 → max x1 + x2 + x3 = 8 2x x x 1 + 2 + 4 = 13, x ≥ 0.
Phương án cực biên xuất phát 1 0 0
x0 = (0; 0; 8, 13)T . Ma trận cơ sở B = , c , 0 1 B = 0 x 1 2 1 x 1 x 3 , , , 1 . Tính được . B = N = c x ∆ x N = N = N = 4 1 1 2 x2 2 Ta có f(x0) = 0 và f(x) = x . Chúng ta giữ 1 + 2x2
x1 = 0 và tăng x2 = 8. Khi đó ta có
phương án x1 = (0; 8; 0; 5)T . Biến đổi hệ phương trình Ax = b về dạng (x1 + x2 + x3 = 8 x1 − x3 + x4 = 5. Phương án cực biên 1 0 2 x
x1 = (0; 8; 0, 5)T . Ma trận cơ sở B = , c , x 2 , 0 1 B = 0 B = x4 1 1 1 x −1 N = , c , x 1 . Tính được ∆ . 1 −1 N = 0 N = x N = 3 −2
Ta có f(x1) = 16 và f(x) = f(x1) − x
. Từ đó suy ra x1 là phương án tối ưu duy nhất 1 − 2x3 của bài toán. 54
Ví dụ 2.15. Chúng ta xét bài toán sau f(x) = 3x1 + x2 → max x1 + 2x2 ≤ 10 4x1 + x2 ≤ 26, x ≥ 0.
Đưa bài toán đã cho về dạng chính tắc f(x) = x1 + 2x2 → max x1 + 2x2 + x3 = 10 4x x x 1 + 2 + 4 = 26, x ≥ 0.
Phương án cực biên xuất phát 1 0 0
x0 = (0; 0; 10, 26)T . Ma trận cơ sở B = , c , 0 1 B = 0 x 1 4 3 x 3 x 3 1 B = , N = , c , x . Tính được ∆ . x N = N = N = 4 2 1 1 x2 1 Ta có f(x0) = 0 và f(x) = 3x . Chúng ta giữ 1 + x2
x2 = 0 và tăng x1 = 13 . Khi đó ta có 2
phương án x1 = (13 ; 0; 7; 0)T . Biến đổi hệ phương trình Ax = b về dạng 2 2 (7 x x 4 2 + x3 − 14 4 = 7 2 x1 + 1x x . 4 2 + 14 4 = 13 2 Phương án cực biên 1 0 0 x
x1 = (13/2; 0; 7/2; 0)T . Ma trận cơ sở B = , c , x 3 , 0 1 B = 3 B = x1 −1/4 7/4 0 x −3/4 N = , c , x 4 . Tính được ∆ . 1/4 1/4 N = 1 N = x N = 2 1/4
Ta có f(x1) = 39/2 và f(x) = f(x1) − 3/4x . Chúng ta giữ 4 + 1/4x2 x4 = 0 và tăng x2 = 2.
Khi đó ta có phương án x2 = (6; 2; 0; 0)T . Biến đổi hệ phương trình Ax = b về dạng (x2 + 4/7x3 − 1/7x4 = 2 x1 − 1/7x3 + 2/7x4 = 6. Phương án cực biên 1 0 1 x
x2 = (6; 2; 0; 0)T . Ma trận cơ sở B = , c , x 2 , 0 1 B = 3 B = x1 −1/7 4/7 0 x −5/7 N = , c , x 4 . Tính được ∆ . 2/7 −1/7 N = 0 N = x N = 3 −1/7
Ta có f(x2) = 20 và f(x) = f(x2) − 5/7x
. Từ đó suy ra x2 là phương án tối ưu 4 − 1/7x3 duy nhất của bài toán. 55 2.4.3 Bảng đơn hình
Ví dụ 2.16. Chúng ta xét bài toán sau
f(x) = −x2 − 2x3 + x4 → max x1 + x3 − 4x (P) 4 = 3, x2 − 3x3 + x 4 = 2, x ≥ 0.
Phương án cực biên xuất phát x0 = (3, 2, 0, 0)T . xB cB x x1 x2 x3 x4 0 −1 −2 1 x 0 3 1 0 1 1 −4 x2 −1 2 0 1 −3 1 −2 0 0 −5 2 x 0 11 1 4 −11 0 1 x 1 2 0 1 −3 1 4 2 0 −2 1 0
Dấu hiệu hàm mục tiêu không bị chặn trên xuất hiện. Bài toán không có phương án tối ưu.
Với phương án xt = (11 + 11t; 0; t; 2 + 3t), trong đó t ≥ 0, ta có f(xt) = 2 + t. 56
Ví dụ 2.17. Chúng ta sẽ giải bài toán sau bằng thuật toán đơn hình gốc
f(x) = −2x1 + 5x2 − x3 → max −x1 + x2 + x (P) 3 = 1, 2x x x 1 + 2 + 4 = 4, x ≥ 0
Phương án cực biên xuất phát x0 = (0, 0, 1, 4)T . xB cB x x1 x2 x3 x4 −2 5 −1 0 x3 −1 1 −1 1 1 0 x 0 4 2 1 0 1 4 −1 −3 6 0 0 x 5 1 2 −1 1 1 0 x 0 3 3 0 −1 1 4 5 3 0 −6 0 x 5 2 0 1 2/3 1/3 2 x1 −2 1 1 0 −1/3 1/3 8 0 0 −5 −1
Dấu hiệu tối ưu xuất hiện. Bài toán gốc đạt giá trị tối ưu f(x∗) = 8 với phương án tối ưu
x∗ = (1, 2, 0, 0). Hơn thế nữa, có thể khẳng định x∗ là phương án tối ưu duy nhất. 57
Ví dụ 2.18. Xét bài toán sauf(x)=8x1+4x2+5x 3 → max x1 + 2x2 + x3 ≤ 2, 2x1 + x3 ≤ 3, x2 + x 3 ≤ 5, xj ≥ 0, j = 1, 2, 3.
Trước hết, chúng ta đưa bài toán đã cho về dạng chính tắc f(x) = 8x1 + 4x 2 + 5x3 → max x1 + 2x2 + x3 + x4 = 2, 2x 1 + x3 + x5 = 3, x2 + x3 + x 6 = 5, xj ≥ 0, j = 1, . . . , 6.
Phương án cực biên xuất phát x0 = (0, 0, 0, 2, 3, 5)T . xB cB x x1 x2 x3 x4 x5 x6 8 4 5 0 0 0 x 0 2 1 2 1 1 0 0 4 x 0 3 5 2 0 1 0 1 0 x 0 5 0 1 1 0 0 1 6 0 8 4 5 0 0 0 x 0 1/2 0 4 2 1/2 1 -1/2 0 x 8 3/2 1 0 1/2 0 1/2 0 1 x 0 5 0 1 1 0 0 1 6 12 0 4 1 0 -4 0 x 4 1/4 0 1 1/4 1/2 -1/4 0 2 x 8 3/2 1 0 1/2 0 1/2 0 1 x 0 19/4 0 0 3/4 -1/2 1/4 1 6 13 0 0 0 -2 -3 0
Dấu hiệu tối ưu xuất hiện. Bài toán gốc đạt giá trị tối ưu f(x∗) = 13 với phương án tối ưu
x∗ = 3 , 1 , 0, 0, 0, 19 . Hơn thế nữa, 2 4 4 3 − t 1 − t 19 − 3t Sol(P) = , , t, 0, 0, | 0 ≤ t ≤ 1 . 2 4 4 58