Tối ưu hóa phần 5

Chứng minh Trước hết, chúng ta sẽ chỉ rằng với hệ thống thế vị {ui, ∀i = 1,m , vj, ∀j = 1,n } thu được ứng với phương án vận tải {xij} đã cho, ta luôn có Δ ij = eij = cij − (u i + v j ) , ∀ô (i, j). Để cho dễ hiểu, chúng ta xét lại ví dụ 5 và bảng III.12. Lúc này, hệ thống thế vị được xác định từ hệ phương trình: ⎧u 1 + v 1 = 3 ⎪ ⎪u 2 + v 1 = 7 ⎪u 2 + v...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa phần 5 Chứng minh Trước hết, chúng ta sẽ chỉ rằng với hệ thống thế vị {ui, ∀i = 1,m , vj, ∀j = 1,n } thu được ứng với phương án vận tải {xij} đã cho, ta luôn có Δ i j = eij = cij − (u i + v j ) , ∀ô (i, j). Để cho dễ hiểu, chúng ta xét lại ví dụ 5 và bảng III.12. Lúc này, hệ thống thế vị được xác định từ hệ phương trình: ⎧u 1 + v 1 = 3 ⎪ ⎪u 2 + v 1 = 7 ⎪u 2 + v 2 = 5 ⎪ ⎨ ⎪u 2 + v 3 = 2 ⎪u + v = 4 ⎪3 3 u 3 + v 4 = 5. ⎪ ⎩ Bảng III.12. Tính hiệu suất các ô chưa sử dụng 3 2 7 6 5000 5000 7 5 2 3 6000 1000 4000 1000 2 (– 7) 5 (– 2) 4 5 2500 1000 1500 6000 4000 2000 1500 13500 Hệ phương trình gồm 6 phương trình và 7 ẩn, hạng của ma trận hệ số (như đã biết) là hạng T A = 6. Vậy hệ có vô số nghiệm phụ thuộc vào một tham số (tức là, các giá trị của các ẩn cơ sở xác định duy nhất khi cho ẩn ngoài cơ sở / ẩn tự do nhận một giá trị tùy ý). Giả sử v4 = 0 (ở đây v4 được coi là ẩn tự do), lúc đó ta có: ⎧u 3 = 5 − v 4 ⎧u 3 = 5 ⎪ ⎪ ⎪ v 3 = 4 − u 3 = −1 + v 4 ⎪u 3 = −1 ⎪u 2 = 2 − v 3 = 3 − v 4 ⎪u 2 = 3 ⎪ ⎪ ⇒ ⎨ ⎨ ⎪v 2 = 5 − u 2 ⎪v 2 = 5 ⎪v = 7 − u = 4 + v ⎪v = 4 ⎪1 ⎪1 2 4 u 1 = 3 − v1 = −1 − v 4 ⎪u 1 = −1. ⎪ ⎩ ⎩ Do đó, khi cho một thế vị chọn bất kỳ nhận một giá trị tùy ý thì luôn tính được các thế vị còn lại một cách duy nhất. Hơn nữa cij – (ui + vj) luôn không thay đổi dù thế vị đầu tiên chọn giá trị nào (hãy quan sát kỹ hệ phương trình trên để suy ra điều này). Như vậy có thể chọn v4 = 0 để việc tính toán được đơn giản. 77 Theo cách xây dựng y = (u1, u2, u3, v1, v2, v3, v4)T trên đây thì có y = (cBB– 1)T với B là ma trận cơ sở (gồm các cột véc tơ cơ sở của ma trận A). Theo tính chất của cặp bài toán đối ngẫu ta có: Δ ij = cij − cB B −1 A ij = cij − y T A ij . Chẳng hạn: Δ11 = c11 − (u 1 ,u 2 ,u 3 , v1 , v 2 , v 3 , v 4 )(1,0,0,1,0,0,0)T = c11 − (u 1 + v1 ). Một cách tổng quát, chúng ta có Δ i j = eij = cij − (u i + v j ) ứng với tất cả các ô (i, j). Từ đây, theo định lý 1 của chương II, và dựa theo lời chứng minh định lý 2 của chương III (cần thay BTG là bài toán Min, còn BTĐN là bài toán Max), chúng ta có thể chỉ ra được (bạn đọc hãy tự chứng minh): điều kiện cần và đủ để một phương án vận tải là tối ưu là hệ thống số thế vị tương ứng phải thỏa mãn: ⎧u i + v j ≤ cij ∀i = 1,m ∀j = 1,n ⎪ ⎨ ⎪u i + v j = cij ∀(i, j) : x i j > 0. ⎩ Đây chính là đpcm. Bài tập chương III Bài 1. Xét BTQHTT Max z = 2x1 + 5x2 + 8x3, với các điều kiện ràng buộc 6x1 + 8x2 + 4x3 ≤ 96 2x1 + x2 + 2x3 ≤ 40 5x1 + 3x2 + 2x3 ≤ 60 x1, x2, x3 ≥ 0. a. Giải bài toán trên bằng phương pháp đơn hình. b. Hãy viết bài toán đối ngẫu và tìm phương án tối ưu của nó. c. Hãy phát biểu ý nghĩa kinh tế của cặp bài toán đối ngẫu. Bài 2. Xét BTQHTT Max z = –2x1 – 6x2 + 5x3 – x4 – 4x5, với các điều kiện ràng buộc x1 – 4x2 + 2x3 – 5x4 + 9x5 = 3 x2 – 3x3 + 4x4 – 5x5 = 6 x2 – x3 + x4 – x5 = 1 x1, x2, x3, x4, x5 ≥ 0. a. Viết bài toán đối ngẫu. b. Áp dụng lý thuyết đối ngẫu, chứng minh rằng x* = (0, 0, 16, 31, 14) là phương án tối ưu của BTQHTT đã cho. 78 Bài 3. Xét BTQHTT Min z = x1 + x2 + x3 + x4 + x5, với các điều kiện ràng buộc 3x1 + 2x2 + x3 =1 5x 1 + x2 + x3 + x4 =3 2x1 + 5x2 + x3 + x5 = 4 x1, x2, x3, x4, x5 ≥ 0. a. Viết bài toán đối ngẫu. b. Cho biết bài toán gốc có phương án tối ưu là x* = (0, 1/2, 0, 5/2, 3/2). Hãy tìm phương án tối ưu của bài toán đối ngẫu. Bài 4. Xét BTQHTT Min z = 5x1 + 5x2, với các điều kiện ràng buộc λx1 + 5x2 ≥ 7 5x1 + λx2 ≥ 3. a. Viết bài toán đối ngẫu. b. Áp dụng lý thuyết đối ngẫu, tìm giá trị tối ưu của bài toán đối ngẫu và bài toán gốc tùy theo λ. Bài 5. Giải BTQHTT sau đây bằng thuật toán đơn hình đối ngẫu: Min z = 2x1 + 5x2, với các điều kiện ràng buộc 6x1 + 8x2 ≥ 96 2x1 + x2 ≥ 40 x 1 , x 2 ≥ 0. Bài 6. Giải BTQHTT sau đây bằng thuật toán đơn hình đối ngẫu: Min z = 3x1 + 4x2 + 2x3 + x4 + 5x5, với các điều kiện ràng buộc x1 – 2 ...