Bài giảng toán tin 5

Một số ứng dụng của bài toán tối ưu Những năm gần đây, nhiều bài toán thực tế được giải quyết bằng phương pháp mô hình hóa toán học rất thành công. Trong số các mô hình toán học đã được áp dụng có nhiều mô hình tối ưu, được giải quyết thông qua các bài toán tối ưu kinh điển.
Nội dung trích xuất từ tài liệu:
Bài giảng toán tin 5 Do yrj ≠ 0 nên từ đây suy ra An–m+1, …, An–m+r–1, An–m+r+1, …, An, Aj là hệ véc tơ độc lậptuyến tính. Theo định lý 12 (về đặc trưng của điểm cực biên) thì x là điểm cực biên. Ngoài ra, tacũng có: ⎡ λej ⎤ pTx = ⎡ pN pB ⎤ × ⎢ T −1 ⎦ b − λy ⎥ = λp j + pB b − λp B y j = p x + λ(p j − p B B A j ) . T T T T T ⎣ ⎣ i⎦ Do λ > 0 và p j − pB B −1 A j > 0 nên p T x > p T x . Điều này mâu thuẫn với tính chất của điểm Tcực biên x (đã xác định bởi pT x = Max{pTxj: j = 1, ..., k}). Vậy điều chúng ta đã giả sử: ∃ z ∈ Dvà z ∉ Λ là sai. Nói cách khác D ⊂ Λ (đpcm). Hệ quả 15a. Tập lồi đa diện D = {x: Ax = b, x ≥ 0} khác rỗng, với A là ma trận cấp m×n và có hạngbằng m, có hướng cực biên khi và chỉ khi D là không giới nội. Chứng minh (dành cho bạn đọc tìm hiểu) có thể được suy ra ngay từ định lý 16.2.3. Điều kiện tối ưu trong phương pháp đơn hình giải bài toán quy hoạch tuyến tính Định lý 16 (điều kiện tối ưu). Xét BTQHTT: Min z = cTx, với x ∈ D = {x ∈ Rn: Ax = b, x ≥ 0} khác rỗng, trong đó A làma trận cấp m×n và có hạng bằng m. Giả sử x1, ..., xk là các điểm cực biên của D và d1, ..., du làcác hướng cực biên của D. Điều kiện cần và đủ để BTQHTT có phương án tối ưu là cTdj ≥ 0,∀j = 1,u . Ngoài ra, nếu BTQHTT thỏa mãn điều kiện trên thì phương án tối ưu đạt được tại ít nhấtmột điểm cực biên. Chứng minh Theo định lý 15, BTQHTT được phát biểu lại như sau: k u Min cTx = cT( ∑ λ j x j + ∑ μ j d j ), j =1 j =1 k ∑λ = 1(6.3), λj ≥ 0, ∀j = 1,k (6.4) và μj ≥ 0, ∀j = 1,u (6.5).trong đó, j j =1 Bởi vậy, nếu BTQHTT có phương án tối ưu với hàm mục tiêu bị chặn dưới, thì cTdj ≥ 0,∀j = 1,u (Nếu trái lại, ∃ j sao cho cTdj < 0. Lúc đó do có thể chọn μj > 0 và lớn tùy ý, sẽ có ngaycTx → – ∞). Ngược lại, nếu cTdj ≥ 0, ∀j = 1,u thì muốn đạt giá trị Min cTx chỉ cần cho μj =0, ∀j = 1,u và chọn phương án tối ưu tại điểm cực biên xi xác định bởi cT xi = Min{ cTxj : j = 1, ...,k} (đpcm).150 Tiêu chuẩn tối ưu và thuật toán Xét BTQHTT như cho trong giả thiết của định lý 16. Theo định lý này chúng ta sẽ tìmkiếm phương án tối ưu x trong các điểm cực biên (trong trường hợp BTQHTT có phương án).Từ định lý 12 ta thấy, điểm cực biên x được cho bởi x T = ( x N , x B ) = ( b T, 0) trong đó b = B– T T1 b ≥ 0, tương ứng với việc A phân rã thành A = [N B]. Giả sử x = ( x N , x B ) ∈ D, lúc đó ta có: T TNx N + Bx B = b ⇔ x B = B −1 b − B −1Nx N . ( ) ( ) cT x = cN x N + cB x B = cB B −1 b + cN − cB B −1N x N = cT x + cN − cB B −1N x N . T T T T T T T Do đó,Vậy cTx ≥ cT x nếu cN − cB B −1N ≥ 0 (do xN ≥ 0). T T Ngược lại, giả sử điều kiện cN − cB B −1N ≥ 0 không được thỏa mãn, tức là ∃ j ∈ JN sao cho T T ⎡ ej ⎤cj − cB B −1 A j < 0. Đặt yj = B–1Aj và dj = ⎢ T ⎥ . Xét điểm: ⎣−y j ⎦ x = x + λdj . (6.9) ( ) cT x = cT x + λ cj − cB B −1 A j . T Lúc đó ta có: (6.10) Dễ thấy cTx < cT x nếu chọn λ > 0. Xét hai trường hợp sau đây: Trường hợp 1: yj ≤ 0. Do Ax = A( x + λdj) = A x + λAdj = A x = b nên x sẽ là phương án(khả thi) nếu x ≥ 0. Điều này luôn xảy ra vì x = x + λdj với λ > 0 và dj ≥ 0. Từ (6.10) ta thấy hàmmục tiêu cTx không bị chặn dưới. Trường hợp 2: Điều kiện yj ≤ 0 không thỏa mãn. Đặt b = B–1b = x B , chọn λ theo quy tắc: ⎧b ⎫b ⎪ ⎪λ = M in ⎨ i : y ij > 0 ⎬ = r ≥ 0 , trong đó yij là tọa độ thứ i của yj . 1≤ i ≤ m y ⎪ y rj ⎪ ij ⎩ ⎭ Ký hiệu các biến cơ sở ứng với ma trận cơ sở B là x B1 , x B 2 ,..., x B m , thì ta có: br x B i = bi − y ij , ∀i = 1,m yrj x = x + λdj ⇔ x j = br / y r j x i = 0, ∀i ≠ j, i ∉ {B 1 ,...,B m } ≡ J B . Dễ thấy x là điểm cực biên có nhiều nhất m tọa độ dương. Nếu b > 0 thì λ > 0 và do đóc x < cT x . Vậy nếu x là phương án cực biên không suy biến thì x là phương án cực biên tốt hơn Tx. Chú ý. Trong phần này chúng ta đã nghiên cứu một cách khá chi tiết cơ sở (giải tích lồi)của phương pháp đơn hình. Trong các BTQHTT cỡ trung bình, phương pháp đơn hình luôn tỏ rarất hiệu quả. Tuy nhiên trong các BTQHTT cỡ lớn (với số biến lớn và nhiều ràng buộc), có thể sửdụng một phương pháp khác: đó là phương ...