Giáo trình Toán kinh tế - PGS.TS. Nguyễn Quảng

265 trang phuongnguyen 2140

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán kinh tế - PGS.TS. Nguyễn Quảng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_kinh_te_pgs_ts_nguyen_quang.pdf

Nội dung text: Giáo trình Toán kinh tế - PGS.TS. Nguyễn Quảng

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG TOÁN KINH TẾ (Dùng cho sinh viên hệ đào tạo đại học từ xa) Lưu hành nội bộ HÀ NỘI - 2007
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG TOÁN KINH TẾ Biên soạn : PGS.TS. NGUYỄN QUẢNG TS. NGUYỄN THƯỢNG THÁI
LỜI NÓI ĐẦU Nhằm đáp ứng nhu cầu giảng dạy và học tập môn học Toán kinh tế dành cho sinh viên hệ đào tạo đại học từ xa, Học viện Công nghệ Bưu chính Viễn thông (Học viện) tổ chức biên soạn tập Sách hướng dẫn học tập (Sách HDHT) môn học Toán kinh tế theo đúng chương trình đào tạo Cử nhân ngành Quản trị kinh doanh của Học viện. Tập sách được biên soạn trên cơ sở kế thừa, chọn lọc bổ sung tập giáo trình Toán chuyên ngành đã được Nhà xuất bản Bưu điện ấn hành vào tháng 9 năm 2003 và các bài giảng Toán kinh tế đã được sử dụng, giảng dạy cho chương trình đào tạo đại học chính quy ngành Quản trị Kinh doanh tại Học viện. Nội dung tập sách được cấu trúc gồm 7 chương: Chương 1. Các kiến thức mở đầu về phương pháp tối ưu Chương 2. Mô hình tối ưu tuyến tính Chương 3. Một số mô hình tối ưu tuyến tính khác Chương 4. Các bài toán tối ưu trên mạng. Chương 5. Phương pháp mô hình hoá và mô hình toán kinh tế. Chương 6. Lý thuyết Phục vụ đám đông Chương 7. Lý thuyết quản lý dự trữ. Để tạo điều kiện thuận lợi cho sinh viên có khả năng tự học, tự nghiên cứu, các tác giả không đi sâu vào các vấn đề lý luận và kỹ thuật toán học phức tạp, mà chỉ tập trung trình bày, giới thiệu những kiến thức cơ bản chủ yếu thiết thực và cập nhật, làm cơ sở cho việc học tập nghiên cứu phân tích kinh tế nói chung và học tập các môn chuyên ngành Quản trị kinh doanh. Ở cuối mỗi chương, sau phần khái quát và tóm tắt các vấn đề cơ bản, chủ yếu của lý thuyết, các tác giả đưa ra các bài tập mẫu và phân tích cách giải để người học có thể tự giải được những bài toán liên quan đến lý luận đã học. Phần bài tập cuối mỗi chương cũng sẽ giúp người học tự nghiên cứu, vận dụng các lý luận đã học vào phân tích, lý giải các nội dung thực tiễn liên quan. Mặc dù các tác giả đã đầu tư nghiên cứu chọn lọc biên soạn nghiêm túc để đáp ứng yêu cầu giảng dạy và học tập của môn học, nhưng chắc tập sách sẽ không tránh khỏi những thiếu sót nhất định. Các tác giả rất mong nhận được sự góp ý của bạn bè đồng nghiệp, bạn đọc và các bạn sinh viên để lần xuất bản sau được hoàn thiện hơn. CÁC TÁC GIẢ
Chương I: Một số kiến thức mở đầu CHƯƠNG I: MỘT SỐ KIẾN THỨC MỞ ĐẦU 1.1. ĐỐI TƯỢNG NGHIÊN CỨU CỦA MÔN HỌC 1.1.1. Tổng quan về tối ưu hoá. Trong hoạt động thực tiễn, nhất là trong quá trình quản lý, điều khiển hệ thống kinh tế - xã hội, chúng ta luôn mong muốn đạt được kết quả tốt nhất theo các tiêu chuẩn nào đó. Tất cả những mong muốn đó thường là lời giải của những bài toán tối ưu nào đó. Mỗi vấn đề khác nhau của thực tế dẫn đến các bài toán tối ưu khác nhau. Để giải các bài toán đó, một loạt các lý thuyết toán học ra đời để đặt cơ sở lý luận, đề đưa ra các giải pháp tìm lời giải, chứng minh tính hội tụ, tính khả thi của các bài toán thực tế v.v. Từ đó hình thành một lớp các phương pháp toán học giúp ta tìm ra lời giải tốt nhất cho các bài toán thực tế, gọi là các phương pháp tối ưu hóa. Lớp các phương pháp tối ưu hóa bao gồm nhiều lý thuyết toán học khác nhau, tiêu biểu là: Qui hoạch toán học, lý thuyết trò chơi, lý thuyết đồ thị v.v. Trong qui hoạch toán học, tiêu biểu là Qui hoạch tuyến tính, Qui hoạch phi tuyến, Qui hoạch động, Quy hoạch tham số, Qui hoạch nguyên v.v. Trong lý thuyết trò chơi, tiêu biểu là Lý thuyết lựa chọn quyết định, Bài toán trò chơi chiến lược, bài toán trò chơi vi phân v.v. Trong Lý thuyết đồ thị có các bài toán tối ưu trên mạng, bài toán PERT, Các bài toán đường đi v.v. Các lớp phương pháp toán học thuộc Lý thuyết tối ưu có thể biểu diễn bởi sơ đồ sau: Lý thuyết tối ưu Các phương pháp tối ưu Mô hình tối ưu Mô Mô Quy Lý Lý Mô hình hình ho ạch thuyết thuyết hình phục quản lý toán đồ thị trò chơi toán vụ đám dự trữ học kinh tế đông 1 1 2 3 Quy hoạch toán học Quy Quy Quy Quy hoạch hoạch phi hoạch hoạch tuyến tuyến động tham số tính 3
Chương I: Một số kiến thức mở đầu 3 Lý thuyết trò chơi Bài toán Bài toán Bài toán lựa chọn trò chơi trò chơi quyết chiến vi phân định lược 1.1.2. Bài toán tối ưu tổng quát. Bài toán quy hoạch toán học tổng quát được phát biểu như sau: Cực đại hóa (cực tiểu hóa) hàm f (x) → max (min) (1.1) Với các điều kiện: gi (x) ≤ (=, ≥ ) bi (i = 1, m ) (1.2) x ∈ X. ⊂ IRn . (1.3) Hàm f (x) cho ở (1 -1) gọi là hàm mục tiêu. Các hàm gi (x) (i = 1, m ) gọi là hàm ràng buộc. Tập hợp D = {x ∈ X | gi (x) ≤ (=, ≥) bi, i = 1,m} (1.4) Gọi là miền ràng buộc chấp nhận được. - Mỗi một bất đẳng thức, đẳng thức trong (1.2) gọi là một ràng buộc của bài toán (1.1) - (1.2) - (1.3) - Điểm x = (x1, x2, , xn) ∈ D gọi là một phương án của bài toán (1.1) - (1.2) - (1.3) hay là một giải pháp chấp nhận được. - Một phương án x* ∈ D làm cực đại (cực tiểu) hàm mục tiêu gọi là phương án tối ưu (hay lời giải hoặc phương án tốt nhất). Theo định nghĩa trên thì x* ∈ D là phương án tối ưu khi và chỉ khi f (x*) ≥ f (x), ∀x ∈ D, (đối với bài toán max) hay f (x*) ≤ f(x), ∀x ∈ D, (đối với bài toán min). Giá trị f(x*) gọi là giá trị tối ưu (tốt nhất) của hàm mục tiêu, hay là giá trị tối ưu của bài toán (1.1) - (1.2) - (1.3). 1.1.3. Phân loại các bài toán tối ưu. a - Nếu hàm mục tiêu f(x) và các ràng buộc gi (x) là hàm tuyến tính (bậc 1) thì bài toán (1.1) - (1.2) - (1.3) gọi là một Qui hoạch tuyến tính . (trường hợp riêng là bài toán vận tải). b - Nếu biểu thức hàm mục tiêu f(x) và các ràng buộc gi (x) (i = 1, m ) là hàm phụ thuộc tham số, thì bài toán (1.1) ÷ (1.3) gọi là qui hoạch tham số. 4
Chương I: Một số kiến thức mở đầu c - Nếu bài toán (1.1) ÷ (1.3) được xét trong quá trình nhiều giai đoạn hoặc trong quá trình thay đổi theo thời gian thì gọi là Qui hoạch động. d - Nếu bài toán (1.1) ÷ (1.3) mà hàm mục tiêu f(x) hoặc có ít nhất một trong các hàm gi (x), (i =1, m ) là phi tuyến thì gọi là Qui hoạch phi tuyến, trường hợp riêng là Qui hoạch lồi hoặc Qui hoạch lõm. Qui hoạch lồi (lõm) là Qui hoạch toán học mà hàm mục tiêu f(x) là lồi (lõm) trên tập hợp các ràng buộc D lồi (lõm). e - Nếu bài toán (1.1) ÷ (1.3) mà miền ràng buộc D là tập rời rạc thì gọi là Qui hoạch rời rạc. 1 n g - Nếu bài toán(1.1) ÷ (1.3) có các biến xi ∈ IR là thành phần i trong véc tơ x ∈ X ⊂ IR , chỉ nhận các giá trị nguyên, thì gọi là Qui hoạch nguyên. 1 h - Nếu bài toán (1.1) ÷ (1.3) mà các biến xi ∈ IR chỉ nhận các giá trị O hoặc 1, gọi là Qui hoạch Bul (xi là thành phần i của véc tơ x). i - Nếu bài toán (1.1) ÷ (1.3) mà trên miền D ta xét đồng thời nhiều mục tiêu khác nhau, gọi là Qui hoạch đa mục tiêu v.v. 1.1.4. Nội dung nghiên cứu của môn học. a. Quy hoạch tuyến tính. b. Bài toán vận tải. c. Bài toán tối ưu trên mạng. d. Mô hình kinh tế và mô hình toán kinh tế. e. Mô hình phục vụ đám đông. g. Mô hình quản lý dự trữ. 1.2. CƠ SỞ GIẢI TÍCH LỒI. 1.2.1. Không gian tuyến tính n chiều (Rn). a. Véc tơ n chiều. Một hệ thống được sắp , gồm n số thực, dạng x = (x1 x2, , xn), gọi là một véc tơ n chiều. Thí dụ: x = (4, 0, 5, 10, 15) là một véc tơ 5 chiều. Các số xi, i = 1, n , gọi là thành phần thứ i của véc tơ x. Hai véc tơ x =(x1, x2, , xn) và (y1, y2, , yn) gọi là bằng nhau, nếu xi = yi, (i =1, n ). Khi đó ta viết x ≡ y. Vậy x ≡ y ⇔ xi =yi, (i = 1, n ). Cho hai véc tơ x = (x1, x2, , xn) 1 y = (y1, y2, , yn) và α ∈ R . Ta định nghĩa phép cộng hai véc tơ x và y là véc tơ x+y, được xác định như sau: x+y= (x1+ y1, x2 + y2, , xn + yn) (1.5) Phép nhân véc tơ x với một số α ∈ R1 là véc tơ αx, được xác định như sau: 5
Chương I: Một số kiến thức mở đầu αx = (αx1, αx2, , αxn) (1.6) - Véc tơ θ = (0, 0, , 0) gồm các thành phần toàn là số 0, gọi là véc tơ không. * Các tính chất của phép cộng véctơ và nhân véctơ với một số. - Nếu x và y là hai véctơ n chiều thì x+y cũng là véc tơ n chiều. - Với mọi véc tơ n chiều x và y ta đều có: x+y =y+x. - Với mọi véc tơ n chiều x, y và z ta đều có: x + (y+z) = (x+y) +z. - Luôn tồn tại véctơ θ n chiều sao cho θ +x = x+θ =x. - Mỗi véctơ n chiều x luôn tồn tại véc tơ n chiều -x sao cho: x+ (-x)=(-x) +x =θ - ∀ k∈ R và với mọi véc tơ n chiều x thì kx cũng là véc tơ n chiều. - ∀ k∈ R và với mọi véc tơ n chiều x và y ta có: k (x+y) = kx+ky. - ∀ l, k∈R và với mọi véc tơ n chiều x ta luôn có: (k +l ) x = kx +lx. - ∀ l, k∈R và với mọi véc tơ n chiều x ta luôn có: k(lx) = (kl) x. - Mọi véc tơ n chiều ta luôn có: 1.x = x. b. Không gian tuyến tính n chiều Rn. Tập hợp tất cả các véc tơ n chiều, trong đó xác lập phép toán cộng Véc tơ và nhân véc tơ với một số thực như (1.5) và (1.6) và thoả mãn 10 tính chất nêu trên, gọi là một không gian tuyến tính n chiều. Ký hiệu IRn. 1.2.2. Một số tính chất đối với véc tơ trong Rn. a. Định nghĩa. Các véc tơ xi ∈ Rn, i = 1, m , gọi là độc lập tuyến tính nếu m i ∑ αi x = θ ⇔ αi = 0, ∀i = 1, m . i=1 m i - Nếu tồn tại ít nhất một số αj ≠ 0 , 1 ≤ j ≤ m, sao cho ∑ αi x = θ , thì ta nói rằng các i=1 véc tơ x ∈ Rn, i =1, m , là phụ thuộc tuyến tính. m i n i - Nếu tồn tại véc tơ x ∈ R , sao cho: x = ∑ αix , với ít nhất một αi ≠ 0, 1≤ i≤ m, thì x gọi i=1 là tổ hợp tuyến tính của các véc tơ xi, (i =1, m ). m m i - Nếu x = ∑ αi x với αi ≥ 0, i = 1, m , và ∑ αi = 1 thì x gọi là tổ hợp lồi của các véc tơ i=1 i=1 xi, i = 1, m . - Trong không gian véc tơ Rn, hệ n Véc tơ độc lập tuyến tính lập thành cơ sở của IRn. Giả sử C1, C2, , Cn là một cơ sở của Rn, khi đó ∀x ∈ Rn đều có thể biểu diễn tuyến tính một cách duy nhất qua các Véc tơ cơ sở. Ci, (i =1, n ). 6
Chương I: Một số kiến thức mở đầu n b. Cho hai véc tơ bất kỳ x, y∈ R , x = (x1, x2, xn) và y = (y1, y2, , yn) , ta gọi tích vô hướng của hai véc tơ x và y là một số thực, ký hiệu là , được xác định như sau: m = ∑ xi yi . i=1 - Độ dài của Véc tơ x ∈ Rn là số thực, ký hiệu x , được xác định như sau n 2 xx,x= =∑ x i i1= - Chú ý: Tích vô hướng hai véc tơ có các tính chất sau: n b1, = . (Tính giao hoán) ∀ x, y ∈ R . 1 2 1 2 1 2 n b2, = + , ∀ x , x , y ∈ R . (Tính phân phối đối với phép cộng). 1 n b3, = λ , ∀λ ∈ R , ∀ x, y ∈ R . n b4> ≥ 0 ∀x ∈ R , dấu bằng xảy ra khi x =θ . Với mỗi ∀x, y ∈ Rn, ta định nghĩa khoảng cách giữa hai véc tơ x, y, ký hiệu ρ (x, y) là số thực, được xác định như sau: n 2 ρ(x, y) = x − y = = Σ(xi − yi ) . i=1 Chú ý: Khoảng cách giữa hai véc tơ x, y ∈ Rn, chính là độ dài của véc tơ hiệu x+ (-1)y: = x - y. (Hiệu của hai Véc tơ). 1.2.3. Không gian Ơclít. Một không gian tuyến tính n chiều, trong đó xác định phép toán tích vô hướng, do đó xác định một khoảng cách giữa hai véc tơ, gọi là không gian Ơclít, ký hiệu IRn. 1.2.4. Tập Compact. a. Các định nghĩa. Dãy {xk} ⊂ |Rn, gọi là hội tụ đến điểm xo∈ IRn khi k→∞, nếu lim ρ(xk, xo) = 0. Khi đó ta k→∞ nói {xk} có giới hạn là xo khi k → ∞ , và viết: lim xk = xo . k →∞ - Một tập hợp S = {x∈IRn: ρ(x, a) ≤ r, a∈ IRn, r ∈ IR1}, gọi là một hình cầu tâm a, bán kính r trong IRn. - Hình cầu S nói trên, tạo thành một lân cận của điểm a, gọi là r -lân cận của a. - Cho tập hợp A ⊂ IRn, điểm x∈ A được gọi là điểm trong của A nếu ∃ε - lân cận của x nằm trọn trong A. - Điểm x ∈ A ⊂ IRn, được gọi là điểm biên của A, nếu mọi lân cận của x đều có chứa các điểm thuộc A và các điểm không thuộc A. - Cho tập hợp A ⊂ IRn, ta nói tập hợp A là giới nội nếu ∃ hình cầu chứa trọn nó, nghĩa là ∃ số thực r đủ lớn và điểm a∈ IRn sao cho ∀x∈ A ta đều có ρ(x, a) < r. 7
Chương I: Một số kiến thức mở đầu * Nhận xét. Từ định nghĩa của dãy hội tụ và tập giới nội, ta suy ra, một dãy {xk} ⊂ IRn, hội tụ bao giờ cũng giới nội. - Một tập hợp G ⊂ IRn được gọi là mở, nếu∀x∈ G, tồn tại một hình cầu tâm x chứa trọn trong G. - Một tập hợp F ⊂ IRn được gọi là đóng, nếu như mọi dãy hội tụ {xk}⊂ F ⊂ IRn, đều hội tụ đến một điểm xo ∈ F. * Nhận xét. Một tập hợp chứa mọi điểm biên của nó là một tập hợp đóng. b. Tập Compact. - Tập hợp C ⊂ IRn được gọi là tập hợp Compắct nếu từ mọi dãy vô hạn {xk}⊂ C, đều có thể trích ra một dãy con {xkn} hội tụ đến một phần tử thuộc C. - Một tập C là Compact khi và chỉ khi C đóng và giới nội. - Tập Compact M của tập đóng C cũng đóng trong C. - Tập con M đóng ⊂ C Compact cũng là tập Compact. - Hàm f(x) liên tục trên tập Compact C sẽ đạt giá trị lớn nhất, nhỏ nhất trên C. 1.2.5. Đường thẳng, đoạn thẳng, siêu phẳng. a. Định nghĩa đường thẳng và đoạn thẳng trong IRn. - Cho hai điểm a, b ∈ |Rn. Ta gọi đường thẳng qua a, b là tập hợp các điểm x ∈ IRn có dạng: x = λa + (1 - λ)b, λ ∈ IR1 - Nếu 0 ≤ λ ≤1 thì ta có đoạn thẳng nối hai điểm a, b, ký hiệu [a, b]. Chú ý - Trong không gian hai chiều IR2, phương trình bậc nhất ax + by = c, xác định một đường thẳng, một bất phương trình ax+by ≤ c hoặc ax+by ≥ c, xác định nửa mặt phẳng trong IRn. - Trong không gian ba chiều IR3, một phương trình bậc nhất ax+by+cz=d xác định một mặt phẳng, một bất phương trình bậc nhất ax+by+cz ≤ d hoặc ax + by + cz ≥ d xác định một nửa không gian. Ta mở rộng kết quả trên cho không gian IRn. b. Siêu phẳng trong IRn . n n - Siêu phẳng trong không gian IR là tập hợp tất cả các điểm x = ∈ IR , thoả mãn phương trình bậc nhất: a1 x1 + a2 x2 + + an xn = α. n n - Một bất phương trình bậc nhất dạng Σ ai xi ≤ α hoặc Σ ai xi ≥ α xác định một nửa không i=1 i=1 gian đóng trong IRn . 1.2.6. Tập hợp lồi . a. Định nghĩa. Tập hợp x ⊂ IRn được gọi là tập hợp lồi nếu cùng với việc chứa hai điểm x, y, nó chứa cả đoạn thẳng nối hai điểm ấy. Điều này có nghĩa là X = {z ∈ |Rn: z = λa + b, a, b∈ IRn, λ ∈ [0, 1]} 8
Chương I: Một số kiến thức mở đầu Ví dụ. Cả không gian IRn, nửa không gian |Rn, các đa giác trong |Rn, các khoảng , đoạn [a, b] trong IR1 là các tập hợp lồi. x x y x y A y B C Tập A: lồi Tập B và C: không lồi. b. Định lý 11. Giao của hai tập hợp lồi là tập hợp lồi. Chứng minh. Lấy hai điểm bất kỳ x, y ∈ A∩ B ⇒ x, y ∈ A và x, y ∈ B Vì A lồi nên [x, y] ⊂ A. B lồi nên [x, y] ⊂ B. => [x, y] ⊂ A ∩ B. Vậy A ∩ B lồi. Hệ quả 1. Giao của một số bất kỳ tập lồi là tập lồi. Hệ quả 2. Tập hợp các nghiệm của hệ bất phương trình bậc nhất dạng: a11x1 + a12x2 + + amxn ≤ b1 a21x1 + a22x2 + + a2nxn ≤ b2 am1x1 + am2x2 + + amnxn ≤ bm, là một tập hợp lồi, gọi là khúc lồi đa diện, trong |Rn. Chú ý . Một khúc lồi đa diện giới nội gọi là đa diện lồi, ký hiệu D. Giao của các tập hợp lồi chứa D ta gọi là bao lồi của D. Ký hiệu [D]. c. Điểm cực biên. Đỉnh của đa diện lồi hoặc khúc lồi gọi là điểm cực biên. Rõ ràng điểm cực biên x không thể là điểm trong của đoạn thẳng nối hai điểm nào đó thuộc D, nghĩa là không thể tồn tại hai điểm x1, x2∈ D sao cho x= λ x1+(1- λ )x2, λ ∈ (0, 1). 1.2.7. Hàm lồi . a. Định nghĩa. Một hàm f(x), xác định trên tập hợp lồi C ⊂ |Rn, được gọi là∀ hàm lồi nếu ∀ cặp điểm x1, x2 ∈ C và ∀ số λ ∈ [0, 1] ta luôn luôn có: 9
Chương I: Một số kiến thức mở đầu f( λx1 + (1 − λ)x 2 ) ≤ λ f(x1) + (1 - λ) f(x2) (1.7) Nếu trong (1.7) xảy ra dấu ≤ thì hàm f(x) gọi là hàm lồi chặt. Nếu trong (1.7) xảy ra dấu ≤ thì hàm f(x) gọi là hàm lõm, xảy ra dấu > thì hàm f(x) gọi là hàm lõm chặt. f(x) f(x2) λf(x1) + (1 -λ) f(x2) f(λx1 + (1 - λx2)) f(x1) 0 x' x x2 x Chú ý. Nếu hàm f (x) lồi trên tập C ⊂ IRn thì hàm - f (x) lõm trên tập C, ngược lại nếu f (x) lõm trên tập lồi C ⊂ IRn thì hàm - f (x) lồi trên tập hợp C. - Ta nói hàm f(x) xác định trên tập lồi C đạt cực tiểu tuyệt đối tại x*∈ C nếu f(x*) ≤ f(x), ∀x∈C, đạt cực đại tuyệt đối tại x* ∈c nếu f(x*) ≥ f(x), ∀x ∈ C. - Ta nói hàm f (x) xác định trên tập lồi C, đạt cực tiểu địa phương tại x*∈C nếu ∃ lân cận Bε của x* sao cho f(x) ≤ f(x), ∀x ∈ Bε . - Ta nói hàm f (x) xác định trên tập lồi C, đạt cực đại địa phương tại x*∈C, nếu ∃ lân cận Bε của x* sao cho f(x) ≥ f(x), ∀x ∈ Bε . b. Định lý 1.2. Mọi điểm cực trị địa phương của hàm lồi trên tập hợp lồi đều là điểm cực trị tuyệt đối. Chứng minh. Giả sử x* là cực tiểu địa phương nhưng không cực tiểu tuyệt đối trên tập C lồi, như vậy ∃ x1∈ C sao cho f (x*) ) f(x1). Xét tổ hợp lồi của hai điểm x* và x1: X = α x* + (1 - α) x1, 0 ≤ α ≤ 1. 1 Nếu α = 0 thì x ≡ x . Khi đó ∃ αo ≤ (0, 1) sao cho x≤ Bε , vớiε ∈ [0, αo) lấy δ1∈ (0, αo) 1 ta có: x(δ1)= (1-δ1) x* + δ1 x ∈ Bε . 1 1 Do f lồi nên có f ((1-δ1) x*+δ1x ) ≤ (1-δ1) f (x*) +δ1 f(x ). ((1-δ1) f (x*) +δ1 f(x*) = f (x*), điều này mâu thuẫn với hàm f (x*) đạt cực tiểu địa phương tại x*. Từ đó suy ra điều phải chứng minh. Hệ quả 1. Mọi điểm cực đại địa phương của hàm lõm trên tập hợp lồi đều là cực đại tuyệt đối. - Ta gọi đạo hàm theo hướng z của hàm f tại x là đại lượng: f(x+λ z) − f(x) δ=f(x,z) lim , nếu giới hạn này tồn tại. λ→0 λ 10
Chương I: Một số kiến thức mở đầu c - Bổ đề 1.1. Nếu hàm f (x) là hàm lồi khả vi trên C lồi. Khi đó ∀x∈ C và với mọi z sao cho x+z ∈ C thì δf (x, z) tồn tại và nghiệm đúng bất đẳng thức và đẳng thức sau: i) δf (x, z) ≤ f (x +z) - f (x). n δf (x) ii) δf (x, z) = Σ zi = . i=1 δx1 ⎛ δf (x) δf (x) δf (x) ⎞ Trong đó: Véc tơ Δ f (x) = ⎜ , , , ⎟ gọi là građient của hàm f(x) tại x, ⎝ δx1 δx2 δxn ⎠ z = (z1, z2 zn) 1.2.8. Một số tiêu chuẩn nhận biết hàm lồi. Cho x, z ∈IRn, đặt hàm số ϕ (λ) = f(x+λz), ∀ λ ∈[0, 1], (1.8) Định lý 1.3. Hàm f(x) là lồi trên IRn khi và chỉ khi hàm số ϕ (λ) là lồi với λ ∈[0, 1] và x, z ∈|Rn . Định lý 1.4. a. Hàm f(x) khả vi trên IRn là lồi khi và chỉ khi ∀ x, z ∈IRn cho trước, hàm ϕ'(λ) = không giảm theo λ. b. Hàm f(x) khả vi hai lần trên IRn là lồi khi và chỉ khi ∀ x, y∈IRn cho trước, dạng toàn phương là xác định không âm. Chú ý. Một dạng toàn phương là xác định không âm khi và chỉ khi ≥ 0, ∀z ∈ IRn . Hệ quả 1. 1 Một hàm bậc hai dạng f(x) = + , trong đó P = (p ij)nxn là ma trân đối 2 xứng cấp nxn, là một hàm lồi khi và chỉ khi ma trân P là xác định không âm. Chú ý. Để ma trận P là xác định không âm thì điều kiện cần và đủ là tất cả các định thức con chính của ma trận này không âm, nghĩa là: a 11 a 12 a 1 n a 11 a 12 a 21 a 22 a 2 n Δ1 = a11 ≥ 0 ; Δ2 = ≥ 0, , Δn = ≥ 0 a 21 a 22 a n 1 a n 2 a nn BÀI TẬP CHƯƠNG I. Bài 1. Một doanh nghiệp có 300 đơn vị nguyên liệu loại A, 500 đơn vị nguyên liệu loại B và 200 đơn vị nguyên liệu loại C để sản xuất 4 loại sản phẩm I, II, III, IV. Định mức nguyên liệu cần thiết và tiền lãi của sản xuất cho bởi bảng 1. Hãy lập kế hoạch sản xuất của xí nghiệp trên sao cho thu được lãi suất lớn nhất. Bảng 1 11
Chương I: Một số kiến thức mở đầu Hàng hoá I II III IV Nguyên liệu A: 300 12 5 15 6 B: 500 14 8 7 9 C: 280 17 13 9 12 Lãi (đơn vị tiền) 5 8 4 6 Bài 2. Cần sản xuất ít nhất 75 sản phẩm loại A, 58 sản phẩm loại B và 64 sản phẩm loại C. Người ta có thể áp dụng 3 cách sản xuất I, II, III, IV. Trong một đơn vị thời gian, năng suất và chi phí của từng cách sản xuất cho bởi bảng 2. Bảng 2 Cách sản xuất I II III Loại sản phẩm A ≥ 75 3 6 7 B ≥ 58 5 9 3 C ≥ 64 2 8 4 Chi phí (đơn vị tiền) 2 4 3 Hãy lập kế hoạch sản xuất sao cho chi phí nhỏ nhất mà vẫn đạt được các yêu cầu đặt ra. Bài 3. Một Công ty có ba xí nghiệp cùng loại: A, B, C có khả năng sản xuất được 3 loại sản phẩm: I, II, III. Biết rằng nếu đầu tư một đơn vị tiền vào xí nghiệp A trong một năm sẽ sản xuất được 1200 sản phẩm loại I, 800 sản phẩm loại II và 1050 sản phẩm loại III. Đầu tư vào xí nghiệp B một đơn vị tiền, được 1000 sản phẩm loại I, 740 sản phẩm loại II, 900 sản phẩm loại III. Đầu tư vào xí nghiệp C một đơn vị tiền thì sản xuất được 1100 sản phẩm loại I, 600 sản phẩm loại II, 1000 sản phẩm loại III. Định mức tiêu hao nguyên liệu và lao động của mỗi xí nghiệp trong sản xuất được cho ở bảng 3. Nguyên liệu, lao động hàng năm Công ty có thể cung cấp cho sản xuất ba loại sản phẩm này là 390.000 KG và 200.000 giờ công. Theo kế hoạch phải sản xuất ít nhất là 23.000 đơn vị sản phẩm loại I, 18.000 đơn vị sản phẩm loại II, và 21.000 đơn vị sản phẩm loại III. Hãy tìm một phương án đầu tư sao cho thu được các sản phẩm theo kế hoạch mà vốn đầu tư ít nhất. Bảng 3 Định mức hao phí ng. liệu (Kg/sản phẩm) và lao động (g/sản phẩm) Doanh I II III nghiệp Ng. liệu Lao động Ng. liệu Lao động Ng. liệu Lao động A 4 2 10 4 8 4, 5 B 4, 2 3 9 4, 5 7, 8 5 12
Chương I: Một số kiến thức mở đầu C 4, 5 2, 5 10, 5 5 8, 4 4 Bài 4. Một xí nghiệp quân đội có 4 loại máy: A, B, C, D, sản xuất ra 6 loại sản phẩm I, II, III, IV, V, VI. Số giờ của mỗi loại máy để sản xuất mỗi loại sản phẩm và giá tiền mỗi loại sản phẩm ghi ở bảng 4. Năng lực sản xuất của các l\mãy đều có hạn, nếu dùng quá sẽ bị hỏng. Giả sử trong 1 tuần, mỗi máy loại A, B, C, D tương ứng làm việc không quá 850, 700, 100 và 900 giờ. Hãy lập một phương án sản xuất để thu được sản phẩm mỗi loại lớn nhất mà vẫn bảo đảm an toàn cho máy móc và thiết bị. Bảng 4 Sản phẩm Loại Loại Loại Loại Loại Số giờ sản Loại I II III IV V VI xuất 1 sp trên máy. A 0, 01 0, 01 0, 01 0, 03 0, 03 0, 03 B 0, 02 0, 05 C 0, 02 0, 05 D 0, 03 0, 08 Giá 1 sản phẩm (đ/v tiền) 0, 40 0, 28 0, 32 0, 72 0, 64 0, 60 Bài 5. Một máy bay vận tải quân sự có trọng tải M. Cần chở n loại thiết bị bằng máy bay. Trọng lượng loại bưu kiện i, (i = 1, n ) là αi, có giá trị βi . Hãy tìm phương án chở mỗi loại thiết bị bao nhiêu đơn vị lên máy bay để trọng lượng tổng cộng không vượt quá tải trọng của máy bay mà đạt được tổng giá trị lớn nhất ? (Bài toán Qui hoạch nguyên). 13
Chương II: Quy hoạch tuyến tính CHƯƠNG II: QUY HOẠCH TUYẾN TÍNH 2.1. MỘT SỐ BÀI TOÁN THỰC TẾ DẪN TỚI MÔ HÌNH QUY HOẠCH TUYẾN TÍNH 2.1.1. Bài toán lập kế hoạch sản xuất. Giả sử một Công ty sản xuất n loại sản phẩm và phải sử dụng m loại nguyên liệu khác nhau. Gọi xj là sản lượng sản phẩm loại j, (j = 1,n ) mà Công ty sẽ sản xuất, cj là tiền lãi (hay giá) một đơn vị sản phẩm loại j, aij là chi phí nguyên liệu loại i, (i =1,m ), để sản xuất ra một đơn vị sản phẩm loại j, bi là lượng nguyên liệu loại i tối đa có thể có. Trong các điều kiện đã cho, hãy xác định sản lượng xj, j = 1,n sao cho tổng tiền lãi (hay tổng giá trị sản lượng hàng hoá) là lớn nhất với số nguyên liệu hiện có. Bài toán thực tiễn trên, có thể mô hình toán học như sau: n Tìm x = (x1, x2, , xn) ∈ IR , làm cực đại hàm mục tiêu: n f(x) = ∑ cj xj → max j =1 với các điều kiện: n ∑ aij xj ≤ bi, i = 1,m , j=1 xj ≥ 0, j = 1,n Bài toán trên là một bài toán Qui hoạch tuyến tính. 2.1.2. Bài toán vận tải. Có m kho hàng cùng chứa một loại hàng hoá, Ai , i = 1,m (Ai điểm phát thứ i). Lượng hàng ở kho Ai là ai, (i = 1,m ). Có n địa điểm tiêu thụ hàng Bj, nhu cầu tiêu thụ ở điểm Bj là bj, j = 1,n (Bi điểm thu thứ i). Biết rằng cước phí vận chuyển một đơn vị hàng hoá từ điểm phát Ai đến điểm thu Bj là cij. Hãy lập kế hoạch vận chuyển hàng hoá từ các địa điểm phát đến các địa điểm thu hàng sao cho tổng chi phí vận chuyển là nhỏ nhất. Nếu ta ký hiệu xij là lượng hàng vận chuyển từ điểm phát Ai, (i =1,m ) đến điểm thu Bj, với (j = 1,n ), thì ta có thể mô hình toán học bài toán thực tế như sau: nxm Tìm véc tơ x= (x1, x2, , xn+m) ∈ IR ,sao cho: m n F(x) = ∑ ∑ cij xij → min i=1 j =1 với các điều kiện: 14
Chương II: Quy hoạch tuyến tính n ∑ xij = ai, i = 1,m j=1 m ∑ xij = bi, j = 1, n i=1 xij ≥ 0, i = 1,m , j = 1, n Ngoài ra bài toán phải thoả mãn điều kiện: n m ∑ bj = ∑ ai (cân bằng thu và phát). j=1 i=1 Đây là một dạng của bài toán Quy hoạch tuyến tính. 2.1.3. Bài toán người bán hàng (Bài toán cái túi). Một cửa hàng cần phải vận chuyển một lượng hàng trên một chuyến nặng không được quá b kg. Có n loại đồ vật mà cửa hàng cần phải vận chuyển đi bán, mỗi đồ vật loại j, (j = 1, n ), có khối lượng aj kg. Và có giá trị là cj . Hãy xác định xem trong một chuyến hàng, cửa hàng cần đưa lên phương tiện vận chuyển các đồ vật nào để tổng giá trị các đồ vật thu được là lớn nhất. Nếu ta ký hiệu xj là số đồ vật loại j sẽ đưa lên phương tiện vận chuyển, ta có mô hình toán học bài toán như sau: n Tìm x = (x1, x2, ,xn) ∈|R sao cho: n f(x) = ∑ cj xj → max j=1 Với điều kiện: n ∑ aj xj ≤ b j=1 xj ≥ 0, j = 1, n xj - nguyên, j = 1, n Đây là bài toán Qui hoạch nguyên. 2.1.4. Bài toán lập kế hoạch đầu tư vốn cho sản xuất. Cần phải đầu tư vốn vào m xí nghiệp để sản xuất ra n loại sản phẩm. Do trang bị kỹ thuật - công nghệ và tổ chức sản xuất khác nhau nên hiệu quả của vốn đầu tư vào các xí nghiệp cũng khác nhau. Qua phân tích, người ta biết rằng khi đầu tư một đơn vị tiền vào xí nghiệp thứ i, i = 1, m , trong một năm sẽ sản xuất ra được bij đơn vị sản phẩm loại j, j = 1, n . Tổng số nguyên liệu và lao động hàng năm có thể cung cấp là A và C (tính theo giờ/công). Hãy xác định một kế hoạch đầu tư sao cho đảm bảo sản xuất được ít nhất Bj đơn vị sản phẩm loại j mà tổng số vốn đầu tư nhỏ nhất, biết rằng các định mức hao phí về nguyên liệu và lao động khi sản xuất ra một đơn vị sản phẩm loại j ở xí nghiệp i, i = 1, m , tương ứng là aij và cij, i = 1, m , j = 1, n . 15
Chương II: Quy hoạch tuyến tính Gọi vốn đầu tư vào xí nghiệp i là xi đơn vị tiền. Khi đó số lượng sản phẩm loại j sản xuất ở xí nghiệp i là bij xi và số nguyên liệu sử dụng ở xí nghiệp này để sản xuất ra các sản phẩm j là aij n bij xi .Vậy toàn bộ nguyên liệu sử dụng ở xí nghiệp i là ∑ aij bijxi và tổng số nguyên liệu sử j=1 m n dụng cho kế hoạch sản xuất chung là: ∑ ∑ aij bij xi. i=1 j=1 m n Tương tự, ta suy ra tổng số lao động sử dụng trong kế hoạch sản xuất là: ∑ ∑ cij bij xi i=1 j=1 m Tổng số vốn đầu tư, theo bài toán đặt ra, là ∑ xi và tổng số sản phẩm loại j sản xuất được i=1 m là ∑ bij xi . i=1 Theo mục tiêu của bài toán thực tế đặt ra thì bài toán có thể mô hình toán học như sau: m Tìm véc tơ x = (x1, x2 , , xn) ∈IR sao cho: m f(x) = ∑ xi → min i=1 với điều kiện: m n ∑ ∑ aij bij xi ≤ A i=1 j =1 m n ∑ ∑ cij bij xi ≤ C i=1 j =1 m ∑ bij xi ≥ Bj, j = 1, n i=1 xi ≥ 0, i = 1, m Đây là một dạng của bài toán Qui hoạch tuyến tính. 2.2. MÔ HÌNH BÀI TOÁN QUY HOẠCH TUYẾN TÍNH. 2.2.1. Bài toán quy hoạch tuyến tính tổng quát n Tìm x = (x1, x2 xi, xn) ∈IR . n Sao cho: f(x) = Σ Cj xj → max (min) (2.1) j = 1 Thỏa mãn điều kiện: n Σ aij xj (≤, = ≥ ) bi ( i=1, m ) (2.2) j = 1 xj≥ 0 (j = 1, n ) (2.3) 16
Chương II: Quy hoạch tuyến tính Để xây dựng cơ sở lý luận giải bài toán, chỉ cấn xét một trong hai dạng bài toán, chẳng hạn bài toán tìm giá trị lớn nhất (f → max ) của hàm mục tiêu, còn bài toán tìm giá trị bé nhất (f → min ) của hàm mục tiêu có thể chuyển đổi như sau: * Giữ nguyên hệ ràng buộc ( 2.2 ) và ( 2.3 ) n * Đưa hàm mục tiêu: f(x) = ∑ Cj xj → min j=1 n về f (x) = - f (x) = Σ ( - Cj ) xj → max, ta có mô hình bài toán: j = 1 n Tìm x = ( x1 , x2 , , xj , xn ) ∈IR n Sao cho: f (x) = Σ (- Cj ) xj → max (2.4) j = 1 n Thoả mãn điều kiện: Σ aij xj (≤, =, ≥ ) bi ( i = 1, m ) (2.5) j = 1 xi ≥ 0 ( j = 1, n ) (2.6) * Bổ đề: Nếu bài toán (2.4) ÷ (2.6) có xopt = x , thì bài toán (2.1) ÷ (2.3) với * f (x) → min cũng có xopt = x và fmin = - f max * Thật vậy, theo giả thiết (2.4) ÷ (2.6) có xopt = x với hàm mục tiêu n f (x) = Σ (-cj ). xj→ max , thì: j = 1 f (x) ≤ f (x*) ( ∀x∈D - tập các phương án ) n n n n * * ⇔ Σ (-cj ). xj ≤ Σ ( - cj ). x j ⇔ Σ cj. x j ≤ Σ cj xj j = 1 j = 1 j = 1 j = 1 * ⇔ f (x) ≥ f (x*) (∀x ∈ D) ⇔ x = xopt của (2.1)⎯(2.3) với f(x) → min. n n * * fmin = Σ cj x j = - Σ (-cj) x j = - f max ( đpcm ) j = 1 j = 1 Như vậy mọi bài toán (2.1) - (2.3) với f(x) → min có thể chuyển f (x) → max. 2.2.2. Dạng chuẩn tắc a- Dạng đầy đủ n Tìm x = (x1 , , xj , xn ) ∈ IR Sao cho: f(x) = c1x1 + +ci xi + + cn xn → max (2.7) 17
Chương II: Quy hoạch tuyến tính Thoả mãn a11 x1 + + a1i xi + +a1n xn ≤ b1 a21 x1 + + a21xi + +a2n xn ≤ b2 ai1 x1 + + aii xi + + ain xn ≤ b1 (2.8) am1 x1+ +ami xi + + amn xn ≤ bm xi ≤ 0 ( i = 1, n ) (2.9) b. Dạng rút gọn. n f(x) = Σ cixi → max j = 1 n Σ aii xi ≤ bi ( i= 1, m ) j = 1 xi ≥ 0 ( δ = 1, n ) Tính chất của hàm mục tiêu (2.7) và dạng bất phương trình của hệ ràng buộc (2.8) xuất phát từ ý nghĩa thực tiễn của bài toán đặt ra. Chẳng hạn như bài toán lập kế hoạch sản xuất để hiệu quả kinh tế tổng cộng lớn nhất, khi phải hạn chế chi tiết nguyên liệu sử dụng. Ngược lại, trong bài toán xác định vốn đầu tư cho sản xuất phải khai thác tối đa trang bị kỹ thuật - công nghệ để sao cho đạt được yêu cầu về giá trị sản phẩm làm ra mà vốn đầu tư ít nhất. 2.2.3 Dạng chính tắc a- Dạng đầy đủ n f (x) = Σ cixi → max (2.10) i = 1 n Σ aiixi = bi (i = 1, m ) (2.11) i = 1 xi ≥ 0 (i = 1, n ) (2.12) b. Dạng ma trận: Gọi ma trận hàng, gồm các phần tử là hệ số các ẩn trong hàm mục tiêu là C: C = [ c1 c2 cn] Ma trận cột: ⎡b1 ⎤ ⎡ x1 ⎤ ⎢ ⎥ b ⎢ x ⎥ B = ⎢ 2 ⎥ , x = ⎢ 2 ⎥ ⎢ ⎥ ⎢ ⎥ ⎣b m ⎦ ⎣ x n ⎦ 18
Chương II: Quy hoạch tuyến tính ⎡a11 a1n ⎤ ⎢a a ⎥ Ma trận hệ số các ẩn ở (2.11): A = ⎢ 21 2n ⎥ ⎢ ⎥ ⎢ ⎥ ⎣am1 amn ⎦ Khi đó bài toán (2.10) ÷ (2.12) có dạng ma trận: Tìm X sao cho: f(x) = C.X → max A.X = B X ≥ 0 c. Dạng véc tơ: Gọi véc tơ: c = ( c1 , c2 , , cn ) x = ( x1 , x2 , , xn ) ⎛ a ⎞ ⎜ 1 j ⎟ ⎜ Véc tơ cột lập bởi hệ số các ẩn ở (2.2) : A = a 2 j ⎟ ( j = 1, n ) 2 j ⎜ ⎟ ⎜ ⎟ ⎝ a mj ⎠ Véc tơ cột lập bởi hệ số tự do ở (3.5): ⎛ b ⎞ ⎜ 1 ⎟ ⎜ b2 ⎟ B = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝bm ⎠ Khi đó, bài toán trên có dạng véc tơ: Tìm X sao cho: f(x) = → max n Σ Aj xj = B j = 1 x ≥ 0 Trong đó: = cjxj - tích vô hướng của 2 véc tơ c và x. Như vậy, bài toán QHTT chính tắc có thể viết dưới dạng ma trận hoặc véc tơ. 2.3. CÁC PHÉP BIẾN ĐỔI DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 2.3.1. Ràng buộc: n Σ aij xj ≥ bi j = 1 n n Có thể đưa về ràng buộc: Σ ( -aij ) . xj ≤ - bi ⇔ Σ a'ij xj ≤ b'i bằng cách nhận j = 1 j = 1 2 vế của (2.7) với (-1) rồi đặt a'ij = - aij, b’i = -bi 19
Chương II: Quy hoạch tuyến tính 2.3.2. Đẳng thức: n Σ aij xj = bi j = 1 Có thể đưa về 2 ràng buộc bất đẳng thức: n n Σ aij xj ≤ bi Σ aij xj ≤ bi j = 1 j = 1 ⇔ n n Σ (- aij ) xj ≤ - bi Σ a'ij xj ≤ b'i j = 1 j = 1 Với a'ij = - aij , b'i = - bi . 2.3.3. Biến xj tự do có thể thay bởi hiệu của 2 biến không âm, bằng cách đặt: xj = x'j - x'n + j với x'j ≥ 0 , x'n + j ≥ 0 Trong đó: x'j = max { 0 ; xj } x'n + j = max { 0 ; - xj} 2.3.4. Một ràng buộc bất đẳng thức: n Σ aij xj ≤ bi có thể đưa về ràng buộc đẳng thức, bằng cách đưa vào biến phụ (hoặc là j = 1 biến bù) xn + i ≥ 0: n Σ aij xj + xn + i = bi j = 1 n Một ràng buộc dạng khác: Σ aij . xj ≥ bi có thể đưa về ràng buộc đẳng thức, bằng cách j = 1 đưa vào biến phụ xn + i ≥ 0: n Σ aij xj - xn + i = bi j = 1 n Vậy ta có: Σ aij xj + xn + i = bi j = 1 ⇔ n Σ aij xj ≤ bi xn + i ≥ 0 j = 1 n n Σ aijxj ≥ bi Σ aij xj - xn + i = bi j = 1 ⇔ j = 1 xn + i ≥ 0 20
Chương II: Quy hoạch tuyến tính 2.3.5. Định lý . n ≤ Nếu véc tơ x = (α1 , α2 , αn ) nghiệm đúng bất phương trình: Σ aij.xj bi thì véc j = 1 (≥) tơ X = (α1 , α2 , , αn , αn + 1 ) sẽ nghiệm đúng phương trình: n Σ aijxj x n + i = bi j = 1 + ()− xn + i ≥ 0 và ngược lại . Ví dụ 1: Đưa bài toán QHTT sau về dạng chính tắc: f(x) = 2x1 − 3x4 + x5 + 2x6 → max x1 + x2 − 3x4 + 2x6 = 5 2x2 − 3x3 + x4 + x5 ≤ 4 3x1 − x2 + 2x3 − 2x5 ≥ 3 xj ≥ 0 ( j = 1, 2, 5, 6) Trước hết đưa hệ ràng buộc dạng đẳng thức, bằng cách đưa vào 2 biến phụ. x7 ≥ 0 ; x8 ≥ 0, ta có: f(x) = 2x1 − 3x4 + x5 + 2x6 → max x1 + x2 − 3x4 + 2x6 = 5 2x2 − 3x3 + x4 + x5 + x7 = 4 3x1 − x2 + 2x3 − 2x5 = 3 xj ≥ 0 ( j: 1, 2, 5, 6, 7, 8) Xét ràng buộc dấu các ẩn, ta thấy x3 , x4 không ràng buộc về dấu (không ẩn), nên đặt: x3 = x'3 − x'9 Với x'3 ≥ 0 , x'9 ≥ 0 x4 = x'4 − x'10 Với x'4 ≥ 0 , x'10 ≥ 0 Bài toán có dạng: f(x) = 2x1 − 3 (x'4 − x'10) + x5 + 2x6 → max x1 + x2 − 3 (x'4 − x'10) + 2x6 = 5 2x2 − 3 (x'3 −x'9) + x4 + x5 + x7 = 4 3x1 − x2 + 2 (x'3 − x'9) − 2x5−x8 = 3 x'j ≥ 0 ( j = 3 ; 4 ; 9 ; 10 ) , xj ≥ 0 ( j = 1 ; 2 ; 5 ; 6 ; 7 ; 8) là bài toán QHTT chính tắc. Tuy nhiên, sau khi thực hiện các phép biến đổi, số biến của bài toán tăng lên, song nếu sử dụng linh hoạt các phép biến đổi đại số, số biến có thể giảm bớt, bài toán rút gọn hơn. Ví dụ 2: Đưa bài toán sau về dạng chuẩn tắc: f(x) = x1 + x2 + 2x3 + 7x4 + 5x5 → max 21
Chương II: Quy hoạch tuyến tính x1 + x2 + x4 + 5x5 = 22 (a) x1 + x2 + x3 + 2x4 + 4x5 = 25 (b) x1 +x3 +x5 = 9 (c) xj ≥ 0 ( j = 1,5 ) Áp dụng các phép biến đổi đại số hệ ràng buộc: Trừ từng vế của (b) cho (a), ta có: x3 + x4 − x5 = 3 Trừ từng vế của (b) cho (c), ta có: x2 + 2x4 + 3x5 = 16 (d) Trừ từng vế của (a) cho (d), ta có: x1 − x4 + 2x5 = 6 Vậy hệ ràng buộc: x1 + x2 + x4 + 5x5 = 22 x1 − x4 + 2x5 = 6 x + x + x + 2x + 4x = 25 x + 2x +3x = 16 1 2 3 4 5 ⇔ 2 4 5 x1 + x3 + x5 = 9 x3 + x4 − x5 = 3 x1 = 6 − (− x4 + 2x5 ) ≥ 0 x = 16 − ( 2x + 3x ) ≥ 0 ⇔ 2 4 5 x3 = 3 − ( x4 − x5 ) ≥ 0 Thay vào mục tiêu, cho kết quả: f(x) = 4x4 + 2x5 + 28 Bài toán tương đương với: f(x) = 4x4 + 2x5 + 28 → max - x4 + 2x5 ≤ 6 2x4 + 3x5 ≤ 16 x4 + x5 ≤ 3 xj ≥ 0 ( j = 4, 5) Đây là bài toán QHTT dạng chuẩn tắc, được rút gọn hơn. Như vậy, một bài toán QHTT ở dạng chuẩn, bằng phương pháp dùng biến phụ, ta luôn đưa được về bài toán ở dạng chính tắc. Đối với bài toán QHTT dạng chính tắc không giảm tính tổng quát, ta giả thiết rằng: i) Hệ ràng buộc (2.11) gồm m phương trình độc lập: Giả thiết này luôn được thực hiện, vì nếu ngược lại thì trong hệ có một hay một số phương trình là tổ hợp tuyến tính của các phương trình còn lại, thì loại khỏi hệ các phương trình này, để được hệ mới gồm các phương trình độc lập với nhau. ii) Ở vế phải của hệ ràng buộc (2.11): bi ≥ 0 ( i = 1, m ) Giả thiết này luôn thực hiện, vì ngược lại nếu ở phương trình thứ i: bi< 0 thì nhân 2 vế của phương trình này với -1, ta được phương trình mới tương đương. n Σ (- aii ) xi = b'i với b'i = − bi ≥ 0 j = 1 iii) Trong hệ ràng buộc (2.11), số phương trình m nhỏ thua số ẩn n: m < n 22
Chương II: Quy hoạch tuyến tính Giả thiết này đưa ra nhằm đảm bảo D ≠∅ của bài toán QHTT, vì ngược lại m ≥ n, thì hệ ràng buộc (2.11) luôn đưa về hệ gồm n, phương trình, n ẩn tương đương sẽ có nghiệm duy nhất (hệ tương thích) hoặc hệ vô nghiệm (hệ không tương thích), trong cả 2 trường hợp đó, việc giải bài toán là vô nghĩa. Vậy mọi bài toán QHTT luôn đưa về dạng chính tắc: n f (x) = Σ cjxj → max j = 1 n Σ aij .xj = bi (i = 1, m ) j = 1 xj ≥ 0 (j = 1, n ) Với: bi ≥ 0 (i = 1, m ) m 0 lập thành hệ độc lập tuyến tính. * Ta phân tích ý nghĩa định lý. Xét bài toán (2.10) ÷ (2.12) dạng véc tơ: 23
Chương II: Quy hoạch tuyến tính f(x) = → max n Σ Aj xj = B j = 1 X ≥ 0 ⎛a ⎞ ⎜ 1 j ⎟ ⎜a2 j ⎟ Trong đó: Aj =⎜ ⎟ ( j = 1, n ) ; c, = ( c1 , c2 , , cn ) ⎜ ⎟ ⎜ ⎟ ⎝amj ⎠ ⎛b ⎞ ⎜ 1 ⎟ ⎜b2 ⎟ B = ; x = ( x1 , x2 , , xn ) ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝bm ⎠ là các véc tơ cột và hàng. x = ( x1 , x2 , xj , xn ) − phương án cực biên ⇔ { Aj: j ∈J , xj > 0 } − hệ véc tơ độc lập tuyến tính. Vậy nhờ định lý, mà việc xem xét một phương án của bài toán QHTT có phải là phương án cực biên hay không , được thay thế bằng việc xem xét sự độc lập tuyến tính hay phụ thuộc tuyến của hệ véc tơ cột Aj , j∈ J. Xét ví dụ sau để làm rõ các khái niệm trên: Ví dụ. Cho bài toán QHTT: f(x) = 2x1 + x2 - 3x3 + 5x4 → max 3x1 + 4x2 - x3 + x4 = 11 x1 - 3x2 - x4 ≤ 0 - 2x1 + x3 + 3x4 = 9 xj ≥ 0 ( j = 1;4 ) Tìm một phương án cực biên của bài toán. Chẳng hạn, ta xét hệ 2 véc tơ: ( A2 , A4 ) , với: ⎛4 ⎞ ⎛1 ⎞ ⎜ ⎟ ⎜ ⎟ A2 = ⎜− 3⎟; A4 = ⎜−1⎟ là hệ độc lập tuyến tính, vì ma trận lập bởi A2 , A4 : ⎜ ⎟ ⎜ ⎟ ⎝0 ⎠ ⎝3 ⎠ ⎛ 4 1 ⎞ ⎜ ⎟ A =⎜− 3 −1⎟ có hạng: rank A = 2 ⎜ ⎟ ⎝ 0 3 ⎠ Vậy (A2 , A4 ) - hệ véc tơ cơ sở: J = {2 , 4} - tập chỉ số các véc tơ cơ sở x2, x4 - biến cơ sở x1, x3 - biến phi cơ sở, vì 1; 3 ∉ J và x1 = x3 = 0 24
Chương II: Quy hoạch tuyến tính Từ: - 2x1 + x3 + 3x4 = 9 ⇒ x4 = 3 > 0 Từ: 3x1 + 4x2 - x3 + x4 = 11 ⇒ x2 = 2 > 0 Với x1 = x3 = 0 ; x2 = 4 , x4 = 3 cũng thoả mãn: x1 - 3x2 - x4 ≤ 0 Vậy x = ( x1 , x2 , x3 , x4) = ( 0 , 2 , 0 , 3 ) là phương án cực biên. - Nếu đưa bài toán về dạng chính tắc, phải đưa vào biến phụ x5 ≥ 0 , bài toán có dạng: f (x) = 2x1 + x2 - 3x3 + 5x4 → max 3x1 + 4x2 - x3 + x4 = 11 x1 - 3x2 - x4 + x5 = 0 - 2x1 + x3 + 3x4 = 9 xj ≥ 0 ( j = 1;5 ) Tương tự xét như trên, hệ véc tơ ( A2 , A4 , A5 ) - độc lập tuyến tính là hệ véc tơ cơ sở của phương án cực biên (không suy biến): x = ( 0, 2 , 0 , 3 , 9 ) Vậy: x = ( 0 , 2 , 0 , 3 , 9 ) ⇔ cơ sở: ( A2 , A4 , A5 ) duy nhất. Người ta chứng minh được rằng: i. Đối với một phương án cực biên suy biến của bài toán QHTT. Có thể có nhiều cơ sở khác nhau. Song đối với phương án cực biên không suy biến chỉ có một cơ sở duy nhất. Ví dụ. Xét bài toán QHTT: f(x) = x1 + 4x2 - 5x3 + 2x4 → max x1 + 5x2 - 3x3 + x4 = 6 3x2 + 3x3- 2x4 = 3 7x1 - 2x3 = 7 xj ≥ 0 ( j = 1;4 ) Tìm một phương án cực biên suy biến và cơ sở của nó. Nếu lấy x3 = x4 = 0 , từ hệ ràng buộc ta có: x1 = x2 = 1 Vậy x = ( 1 , 1 , 0 , 0 ) là một phương án Với x1, x2 > 0 xét hệ véc tơ (A1,A2) ma trận A lập bởi A1, A2: ⎛1 5⎞ ⎜ ⎟ A = ⎜0 3⎟ có hạng A = 2 ⇒ ( A1 , A2 ) - hệ véc tơ độc lập tuyến tính. Do đó x = ( 1 , 1 , 0 ⎜ ⎟ ⎝7 0⎠ , 0 ) là một phương án cực biên. Hơn nữa số thành phần dương trong x là 2 < 3 = m. Vậy x = ( 1 , 1 , 0 , 0 ) là phương án cực biên suy biến. Xét hệ véc tơ ( A1 , A2 , A3 ) ma trận A lập bởi A1 , A2 , A3: ⎛1 5 − 3⎞ ⎜ ⎟ A = ⎜0 3 1 ⎟ ⇒ det A = 92 ≠ 0 ⎜ ⎟ ⎝7 0 − 2⎠ 25
Chương II: Quy hoạch tuyến tính Vậy hệ ( A1 , A2 , A3 ) - độc lập tuyến tính, là một cơ sở của x. Vậy đối với phương án cực biên suy biến x = ( 1 , 1 , 0 , 0 ) có 2 cơ sở khác nhau ( A1 , A2 , A3 ) và ( A1 , A2 , A4 ). * Điều kiện tồn tại lời giải của bài toán QHTT là. *- Tập các phương án: D ≠ φ *- Hàm mục tiêu bị chặn trên miền D. 2.5. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 2 BIẾN. 2.5.1 Biểu diễn hình học quy hoạch tuyến tính 2 biến Xét bài toán QHTT chuẩn tắc 2 biến. f(x) = c1x1 + c2 x2 → max ai1 x1 + ai2 x2 ≤ bi ( i = 1, m ) xj ≥ 0 ( j = 1,2 ) - Từ ý nghĩa hình học của siêu phẳng trong IR2: H = {x = (x1, x2 ): a1 x1 + a2 x2 = b} chia IR2 thành 2 nửa mặt phẳng: + D = {x = (x1, x2 ): a1 x1 + a2 x2 ≥ b} − D = {x = (x1, x2 ): a1 x1 + a2 x2 ≤ b} thì mỗi bất phương trình tuyến tính trong hệ ràng buộc ai1 x1 + ai2 x2 ≤ bi ( i=1, m ) sẽ xác định một nửa mặt phẳng . Vậy miền ràng buộc D, xác định bởi hệ ràng buộc là giao của m nửa mặt phẳng, sẽ là đa giác lồi hay khúc lồi (nếu D ≠ φ) hoặc không tồn tại (nếu D = Φ ) Để xác định nửa mặt phẳng (2.2)1, trước hết phải xác định đường thẳng : (Hi): ai1 x1 + ai2 x2 = bi ( i =1, m ) → Sau đó xác định véc tơ pháp tuyến của nó: ni = {ai1, ai2} ( i =1, m ) → thì phần nửa mặt phẳng ( Di ): ai1 x1 + ai2 x2 ≤ bi ( i =1, m ) sẽ nằm về phía ngược hướng với ni , → còn nửa mặt phẳng: (i = 1, m ) sẽ nằm về phía cùng hướng với ni (i = 1, m ), kể cả biên của (Hi). Minh hoạ hình học + Chú ý: Ngoài phương pháp xác định giữa mặt phẳng ( D i ) hoặc Di nêu trên, có thể xác định bằng cách: xét điểm góc tọa độ O (0,0) thuộc nửa mặt phẳng nào, nhờ thay toạ độ O (0,0) vào hệ ràng buộc hoặc ngược lại. 26
Chương II: Quy hoạch tuyến tính x 2 D + ( i ): ai1 x1 + ai2 x2 ≥ bi → ni = {ai1, ai2} ( D ): a x + a x ≤ b i i1 1 i2 2 i x1 0 (H ): a x + a x = b → i i1 1 i2 2 i - ni Hình 2.1: - Từ ý nghĩa hình học, đối với hàm mục tiêu: f(x) = c1x1 + c2 x2 ta xét phương trình đường thẳng: c1x1 + c2 x2 = α (*) với α ∈ IR1 Ta thấy: Khi α thay đổi, (*) sẽ xác định trên mặt phẳng toạ độ 0x1 x2 các đường thẳng song → song với nhau (vì cùng vuông góc với véc tơ pháp tuyến ni = {c1, c2}), gọi là các đường mức (mức giá trị α). Mỗi điểm x = ( x 1, x 2) ∈D, sẽ nằm trên đường mức với giá trị: ε = c1 x 1 + c2 x 2 Xem hình 2.2. Vậy theo ngôn ngữ hình học, có thể phát biểu bài toán (2.10) − ( 2.12 ) như sau: Trong số các đường mức (2.13) tìm đường mức với giá trị lớn nhất có thể: x2 n ={c1,c2} x c1 x +c2 2 = α - c x +c x = α 1 1 2 2 0 x1 Hình 2.2 27
Chương II: Quy hoạch tuyến tính = c * + c * với x* = ( * , * ) D αmax 1 x1 2 x2 x1 x2 ∈ khi đó x* = ( * , * ) = x với f (x) = x1 x2 opt max αmax 2.5.2. Phương pháp hình học giải bài toán QHTT 2 biến . a. Nhận xét: Hàm mục tiêu: f (x) = c1 x1 + c2 x2 có thể biểu diễn bằng dạng véc tơ, nhờ khái niệm của tính vô hướng: 2 f(x) = ( c , x ) với c = ( c1, c2 ) , x = ( x1, x2 ) ∈ IR Ta thấy: f(x) = c1 x1 + c2 x2 = α Khi dịch chuyển song song các đường mức (*) theo hướng véc tơ pháp tuyến → c = {c1, c2}, thì giá trị đường mức α (tức f (x)) sẽ tăng. Ngược lại, khi dịch chuyển theo hướng ngược lại của c , (hay cùng hướng với véc tơ đối của → → c là - c ), thì giá trị đường mức α (hay f(x) sẽ giảm ) . * * * Vậy để giải bài toán trên ta tìm x* = ( x1 , x2 ) ∈ D mà αmax = f (x ). Từ đó, ta có thể nêu các bước giải bài toán trên bằng phương pháp hình học như sau: b. Các bước giải bài toán . Để giải bài toán trên ta tiến hành: i - Xác định miền ràng buộc D của bài toán trong hệ trục toạ độ 0x1x2. ii – Vẽ đồ thị đường mức (*): c1x1 + c2 x2 = α với α nào đó, iii - Xác định véc tơ pháp tuyến c = {c1,c2} và dịch chuyển song song các đường mức (*) theo hướng của véc tơ c , cho đến vị trí tới hạn (vị trí tới hạn là vị trí mà đường mức vẫn còn cắt miền D, nhưng nếu tiếp tục dịch chuyển thì sẽ không cắt miền D nữa) iv - Điểm ( hoặc nhiều điểm ) của D nằm trên giao điểm của đường mức ở vị trí tới hạn với miền D, là lời giải của bài toán. Minh hoạ hình học (hình vẽ 2.3) x c 2 1 B x 1 * x2 +c 2 A x 2 * D = C α max c D * 0 x1 - c1x1+c2x2 =α Hình 2.3 28
Chương II: Quy hoạch tuyến tính c. Chú ý: Ở trên, để tiện lợi ta xét bài toán QHTT chuẩn tắc, đối với bài toán QHTT bất kỳ cũng có thể giải được bằng phương pháp hình học. Có thể xảy ra các trường hợp: i) - Miền D = ∅ tức các nửa mặt phẳng xác định bởi hệ ràng buộc. ai1x1 + ai2x2 ≤ bi(hoặc ai1x1 + ai2x2≥ bi) Không có điểm chung, thì bài toán vô nghiệm. ii) Miền D ≠ ∅: - Nếu D - đa giác lồi, thì có duy nhất 1 điểm cực biên là phương án tối ưu; hoặc có vô số phương án tối ưu, khi đó 2 điểm cực biên là các phương án tối ưu (theo tính chất bài toán QHTT). - Nếu D - khúc lồi (đa giác lồi không giới nội), thì bài toán có một phương án cực biên tối ưu, nếu miền D nằm về một phía của đường mức (2.4) cắt đường mức (2.4) tại 1 điểm, hoặc bài toán có vô số phương án tối ưu, nếu có 2 điểm cực biên là các phương án tối ưu, hoặc bài toán không có lời giải (f(x) không bị chặn). Có thể minh hoạ bằng một số ví dụ sau: 2.5.3 - Ví dụ: Ví dụ 1: Giải bài toán sau bằng phương pháp hình học: f(x) = 4x1 + 5x2 → max 2x1 + x2 ≤ 8 x1 + 2x2 ≥ 7 x2 ≤ 3 xj ≥ 0 ( j =1 , 2 ) Xác định miền ràng buộc D (hình vẽ 2.4) là đa giác lồi (tam giác ABC) x2 8 2x1 + x2 ≤ 8 n 3 A B x2 ≤ 3 D x1 + 2x2 ≥ 7 2 C 5/2 4 7 0 4x1 + 5x2=10 x1 Hình 2.4 29
Chương II: Quy hoạch tuyến tính Xét đường mức: 4x1 + 5x2 = 10 ( cho α = 10, dễ vẽ) 5 Dịch chuyển đường mức song song với nhau theo hướng n = {4; 5}, đỉnh B ( ;3 ) ∈D ở 2 trên đường mức cuối cùng là điểm cực biên tối ưu: 5 xopt = ( ;3 ) ⇔ 2 5 αmax = f(x) max = 4. + 5.3 = 25 2 Ví dụ 2: Giải bài toán sau bằng phương pháp hình học: f(x) = 4x1 + 3x2 → max x1 + x2 ≤ 4 - x1 + 3x2 ≤ 3 2x1 - x2 ≤ 2 xj ≥ 0 ( j = 1,2 ) Xác định miền ràng buộc D (hình vẽ 2.5) Ta thấy D = φ Vậy bài toán không có lời giải. Ví dụ 3: Giải bài toán sau bằng phương pháp hình học: x2 f(x) = 3x1 + 4x2 → min x1 + 2x2 ≥ 4 - x1 + x2 ≤ 2 - x1 + x2 ≤ 2 2x1 - 4x2 ≤ 12 x + x ≥ 4 xj ≥ 0 ( j = 1,2) 1 2 4 - x1 + 3x2 ≤ 3 1 x1≥ 0 0 -3 1 4 x1 -2 Hình 2.5: 30
Chương II: Quy hoạch tuyến tính Xác định miền ràng buộc D của bài toán: khúc lồi (hình vẽ 2.6) x2 Xét đường mức: x2≥ 0 3x1 + 4x2 = 4 - x + x ≤ 2 Dịch chuyển song song các đường 1 2 → → mức theo hướng ngược với n = {3;4} n = {3;4} 2 A Cắt D tại điểm A (0 ;2) là duy nhất. x1 + 2x2 ≥ 4 Vậy A (0;2) là điểm cực biên tối ưu: 1 x1≥ 0 Xopt = (0;2) ⇔ B C = f(x) = αmin min -2 4/3 4 6 x1 = 3.0 + 2.4 = 8 3x1 + 4x2=4 2x - 4x ≤ 1 1 2 Hình 2.6: Chú ý: Nếu ở bài toán trên, giữ nguyên miền ràng buộc, còn f(x) = 3x1 + 4x2 → max thì → bài toán sẽ vô nghiệm, bởi vì khi dịch chuyển song song các đường mức theo hướng n = {3 ; 4}, sẽ có vô số các đường thẳng song song với đường mức đi qua điểm cực biên C và có khoảng cách lớn tuỳ ý đến nó, tức f (x) → + ∞ (f(x) không bị chặn trên ) Ví dụ 4: Giải bài toán sau bằng phương pháp hình học: f(x) = 3x1 + 6x2 → min x1 + 2x2 ≥ 2 -2x1 + 3x2 ≤ 6 0 ≤ x1 ≤ 4 Xác định miền ràng buộc D của bài toán (hình 2.7) Xét đường mức: 3x1 + 6x2 = 18 → Dịch chuyển song song các đường mức theo hướng ngược với n = {3;6}, có 2 điểm A (0;1), F (2;0) nằm trên đường mức cuối cùng. Vậy có 2 điểm cực biên tối ưu ⇒ bài toán có vô số lời giải là mọi tổ hợp lồi của 2 điểm cực biên tối ưu trên, tức là vô số các điểm nằm trên đoạn thẳng [ AF ] cũng là phương án tối ưu (trường hợp đường mức cuối cùng trùng với một cạnh của miền D) 31
Chương II: Quy hoạch tuyến tính x2 x1=4 → n = {3;6} 2x1 + 3x2 ≤6 C 3 D 2 3x + 6x ≤6 B 1 2 1 x2 ≥ 0 x1 + 2x2 ≥ 2 2 D 0 F 4 E 6 x1 Hình 2.7 Qua phương pháp hình học, ta thấy rằng: - Nếu bài toán QHTT có phương án tối ưu, thì ít nhất 1 đỉnh của miền D là tối ưu. - Nếu miền D giới nội và khác rỗng, thì chắc chắn có phương án tối ưu. - Nếu miền D không giới nội, nhưng hàm mục tiêu bị chặn trên miền D, thì cũng chắc chắn có phương án tối ưu. 2.6. PHƯƠNG PHÁP ĐƠN HÌNH 2.6.1. Cơ sở lý luận của phương pháp a. Đường lối chung Xét bài toán quy hoạch tuyến tính chính tắc n f(X) = ∑ c j x j → min (max) (2.13) j=1 ⎧ n ___ a x = b (i = 1, m) ⎪∑ ¹i j i ⎨ j= (2.14) ⎪ ___ ⎩⎪x j ≥ 0(j = 1.n) ___ Với giả thiết m → min (max) ⎧ ⎛=⎞ ⎪ n ⎜ ⎟ ⎪∑ A1 x j ⎜≥⎟B j=1 ⎜ ⎟ ⎨ ⎝≤⎠ ⎪ ⎪ ___ ⎩x j ≥ 0(j = 1, n) 32
Chương II: Quy hoạch tuyến tính (0) 0 0 (0) Xuất phát từ một phương án cực biên x = (x 1, x n với cơ sở J0, ta tìm cách đánh giá x , nếu x(0) chưa tối ưu thì tìm cách chuyển sang phương án cực biên x(1) tốt hơn. Vì số phương án cực bkên là hữu hạn nên sau một số hữu hạn bước lập sẽ tìm được phương án cực biên tối ưu hoặc phát hiện bài toán không có lời giải. b. Ước lượng các biến (0) Giả sử x là một phương án cực biên, cơ sở J0. Gọi Δklà ước lượng của biến xk theo cơ sở J0 được xác định bởi: ___ Δk = ∑ c j z jk − c k (k = 1, n) j∈J 0 Trong đó zjk là hệ số phân tích của véctơ Ak qua véctơ cơ sở Aj (j ∈ J0) nghĩa: ___ -1 Ak = ∑zjkA¹, do đó zjk = A j Ak (j ∈ J0, k = 1, n ) j∈J0 Chú ý rằng ước lượng các biến cơ sở xj: Δj = 0 (∀j ∈ J0). Vì khi đó: ⎧1 nÕu k = j Zjk = ⎨ ⎩0 nÕu k ≠ j c. Dấu hiệu tối ưu (0) Nếu phương án cực biên x , cơ sở J0 của bài toán (2.13) - (2.15) có ∀Δk 0). (k ∉J0) thì X(0) là phương án tối ưu duy nhất. ()) Nếu phương án cực biên X , cơ sở J0 thoả mãn dấu hiệu tối ưu mà ∃Δk = 0. (k ∉ J0) thì bài toán có thể có phương án tối ưu khác ngoài X(0). d. Định lý cơ bản (0) Đối với phương án cực biên X , cơ sở J0 của bài toán (2.13) - (2.15) mà ∃Δk > 0 ( 0 ( 0 ( 0, (j ∉ J0) thì chuyển sang được phương án cực biên mới X(1) tốt hơn X(0); f [X(1)] f[X(0)]). 2.6.2. Thuật toán của phương pháp đơn hình Toàn bộ quá trình tính toán được sắp xếp theo một trình tự chặt chẽ đảm bảo hiệu quả của việc tìm lời giả của bài toán QHTT. Trình tự đó được gọi là thuật toán. Không mất tính tổng quát ta xét bài toán QHTT dạng chuẩn. n f (x) = ∑ c j x j → min j=1 33
Chương II: Quy hoạch tuyến tính ⎧ ⎪x 1 + a 1m+1 x m+1 + + a 1n x n = b1 ⎪ x 2 + a 2m+1 x m+1 + + a 2n x n = b 2 ⎪ ⎨ ⎪x + a x + + a x = b ⎪ m mim+1 m+1 mim n m ⎪ ___ ___ ⎩⎪x j ≥ 0(j = 1, n), b i ≥ 0(i = 1, m), m 0, (k ∉ J0) mà Zjk ≤ 0, (j ∈ J0) thì bài toán không có lời giải vì f[x] → - ∞, thuật toán kết thúc. Nếu mỗi Δk > 0, (k ∉ J0) mà ∃ Zjk > 0, (j ∉ J0) thì chuyển sang bước 3. Bước 3. Tìm véctơ đưa vào cơ sở và véctơ loại khỏi cơ sở. Giả sử: max { Δk > 0, (k ∉ J0) } = Δ, véctơ As được đưa vào cơ sở, tính: ⎧ x 0 ⎫ 0 ⎪ j ⎪ x r θ0 = min zjt > J0 ⎨ ; j∈ J 0 ⎬ , giả sử θ0 = , véctơ Ar loại khỏi cơ sở. Z Z ⎩⎪ js ⎭⎪ rs 34
Chương II: Quy hoạch tuyến tính Như vậy, J1 = {J0\{r}∪{S}}. Hệ số phân tích Zrs nằm tại giao của hãng r và cột s gọi là phần tử trục của phép biến đổi. (1) Bước 4. Biến đổi bảng, xây dựng phương án cực biên mới x với cơ sở J1. Trong bảng đơn (1) hình tương ứng với phương án cực biến x , cơ sở J1 ta thay cs, As vào vị trí của cr, Ar các cj, Aj (j ≠ r, j (1) ∈J0) được giữ nguyên. Các thành phần của x được tính theo công thức: ⎧ ⎪ nếu j ∉ J ⎪0 0 ⎪x (0) 2 ⎪ r nếu j ∈ J , j = r x j = ⎨ 0 Z ⎪ rs ⎪ (0) (0) x r ⎪x j − nZếujs j ∈ J0, j ≠ r ⎩⎪ Z rs Cơ sở J1 = {J0\{r}∪{S}: {J1} = {J0} = m (1) Hệ số phân tích Z jk (j ∈ J1, k ∉ J1) được xác định bởi công thức: (0) ⎧x rk nếu j ∈ J0, j = r ⎪ (1) ⎪ Z rs Z jk = ⎨ ⎪ Z rk Z − nZếu j ∈ J0, j ≠ r ⎪ jk js ⎩ Z rs Công thức này đúng cho cả các thành phần ở cột phương án và ở hàng ướclượng Δ1. (1) (0) (1) (1) Ta có: f[x ] = f[x ] - θΔ, hay f [x ] = ∑ c j x j j∈J1 1 1 1 Δ k = Δ k - θΔ, hay Δ k = ∑ c Þc Z jk − c k (k ∉J1) j∈Ji Xem X(1) đóng vai trò như X(0), lập lại quá trình trên từ bước hai trở đi sau một số hữu hạn lần hoặc phát hiện bài toán không có lời giải hoặc tìm được phương án tối ưu của bài toán. Chú ý khi thực hiện thuật toán: Đối với bài toán f(x) → max có thể giải trực tiếp bằng thuật toán đơn hình với véctơ A, được đưa vào cơ sở có Δs = min {Δk < 0,k ∉ J0} còn xác định véctơ loại khỏi cơ sở Ar và các thành phần (1) (1) x j , Z jk (j ∈J1, k ∉J1) được tính tương tự, hoặc cũng có thể chuyển thành bài toán: g(x) = - f(x) → min những chú ý rằng fmax = - gmin. 2.6.3. Phương pháp tìm phương án cực biên xuất phát - bài toán “M” Khi dùng thuật toán đơn hình giải bài toán QHTT chính tắc với giả thiết đã biết một phương án cực biên với cơ sở đơn vị tương ứng. Nhưng nhìn chung giả thiết này không phải bao giờ cũng có ngay. Vì vậy để áp dụng được thuật toán đơn hình cần phải có phương pháp tổng quát cho phép tìm được một phương án cực biên mà không phụ thuộc vào cấu trúc riêng biệt của bài toán. Một trong những phương pháp như vậy là phương pháp biến giả hay phương pháp tìm phương án cực biên xuất phát. a. Nội dung phương pháp 35
Chương II: Quy hoạch tuyến tính Xây dựng bài toán mới là bài toán biến giả hay bài toán “M” từ bài toán đang xét. Bài toán “M” có ngay phương án cực biên xuất phát và có đủ điều kiện áp dụng thuật toán đơn hình để giải, đồng thời từ kết quả của bài toán “M” đưa ra được kết luận cho bài toán đang xét. b. Xây dựng bài toán “M” Xét bài toán chính tắc: n f(x) = ∑ c j x j → min (2.16) j=1 n ⎧ (2.17) ⎪∑cxjj=− b(i i 1,m) ⎨ j1= ⎪x0(j1,n)≥= ⎩ j (2.18) ___ Bài toán (2.16) ÷ (2.18) gọi là bài toán đầu. Giả thiết bi ≥ 0 (i = 1, m) và ma trận các hệ số trong hệ ràng buộc (2.17): A = (aij)mxn không chứa véctơ đơn vị nào. Bài toán “M” được xây dựng như sau: ___ Thêm vào vế trái của phương trình thứ i (i = 1, m) trong hệ ràng buộc (2.17) một biến giả ___ xn+ i ≥ 0 (i = 1, m) . Hệ số của các biến giả xn+i trên hàm mục tiêu đều bằng M, với m là số dương lớn tuỳ ý (M > 0 ), bài toán “M” có dạng: ___ n m f( X ) = ∑ c j x j + M ∑ X n+i → min j=1 i=1 ⎧ n ⎪∑axjj+=− x ni+ b(i i 1,m) ⎨ j1= ⎪ ⎩x0(j1,n)j ≥= Bài toán “M” có ngay phương án cực biên xuất phát: __ (0) x = ( 0,0, ,0, b1, b2, , bm) với cơ sở J0 là: Em = (An+1, An+2, , An+m ); n sè J0={n+1, n+2, ,n + m} Do vậy áp dụng được thuật toán đơn hình để giải bài toán “M”. Từ cách xây dựng bài toán “M” như trên ta thấy: __ ⎡ ⎤ Nếu x = x , x , , x , 0,0, ,0 là phương án của bài toán “M” thì x = (x , x , , x ) ⎢ 1 2 n ⎥ 1 2 n ⎣⎢ n sè ⎦⎥ __ là phương án của bài toán ban đầu và ngược lại, đồng thời f(x) = f( x) . c. Mối quan hệ giữa bài toán “M” và bài toán ban đầu Nếu bài toán “M” có: 36
Chương II: Quy hoạch tuyến tính __ __* ⎡ ⎤ * * * * * * * X opt = X = x , x , x , 0,0, ,0 thì bài toán ban đầu có X = x = x , x , , x và ⎢ 1 2 n ⎥ opt ( 1 2 n ) ⎣⎢ m sè ⎦⎥ __* f( x ) = f(x*). __ __* * * * Nếu bài toán “M” có x opt = x = (x 1 , x 2 ,, , x n+m ) trong đó ∃ ít nhất một ___ * x n+i > 0(i = 1, m) thì bài toán ban đầu không có phương án nào (không giải được). Nếu bài toán “M” vô nghiệm thì bài toán ban đầu cũng vô nghiệm. d. Chú ý khi giải bài toán “M” Nếu bài toán ban đầu có nghiệm Xopt thì nghiệm này chỉ có thể nhận được sau ít nhất m + 1 bảng đơn hình khi giải bài toán “M”. Nếu trong ma trận hệ số trong hệ ràng buộc (1.17): A = (ajj)mxn đã chứa m1 véctơ đơn vị khác nhau (m1 α h Δk > Δh ⇔ ⎢ ⎣α k = α h ;β k > β h Ở mỗi bước cải tiến phương án cực biên, nếu một biến giả bị đưa ra khỏi cơ sở thì nó không thể quay lại cơ sở được nữa. Do đó ở bảng đơn hình ứng với phương án cực biên mới ta không cần tính toán với cột ứng với véctơ tương ứng với biến giả đó. Với bài toán f(x) → max bài toán “M” tương ứng có hàm mục tiêu là: __ n m f( x) = ∑∑c j x j − M x n+i → max (M >> 0) j==11i Các điều kiện còn lại tương tự bài toán f(x) → min 2.6.4. Các bài tập mẫu Bài 1. Giải bài toán sau bằng phương pháp đơn hình. f(x) = 2x3 + x4 → min ⎧ ⎪x 1 + 2x 3 + x 4 = 6 ⎪ ⎨x 2 + x 3 − 2x 4 = 2 ⎪ ___ ⎪ ⎩x j ≥ 0(j = 1,4) (0) Bài toán có dạng chuẩn, phương án cực biên xuất phát:X = (6,2,0,0) với cơ sở { A1, A2} = E2 Lập bảng đơn hình: 37
Chương II: Quy hoạch tuyến tính Cj Aj Phương 0 0 2 - 1 cơ sở án A1 A2 A3 A4 0 A 6 1 0 2 1 X(0) ↔ 1 0 A2 2 0 1 1 2 0 0 0 -2 1 X(1) ↔ -1 A4 6 1 0 2 1 0 A2 14 2 1 5 0 - 6 - 1 0 - 4 0 (1) (1) Từ bảng đơn hình tương ứng với phương án cực niên x ta thấy phương án x có Δk ≤ 0, (k = ___ 1,4) . Đặc biệt Δk ≤ 0 (k ∉ J1). Do đó bài toàn có nghiệm duy nhất: (1) (1) Xopt = X = (0,14,0,6) và fmin = f [X ] = - 6. Bài 2. Giải bài toán sau bằng phương pháp đơn hình f(x) = - x1+ 4x2 + 3x3 → max ⎧2x 1 + x 2 − 2x 3 + x 4 = 16 ⎪− 4x + 2x + x = 8 ⎪ 1 3 5 ⎨x + 2x − x + x = 12 ⎪ 1 2 3 6 ⎪ ___ ⎩x j ≥ 0(j = 1,6) Bài toán có ngay phương án cực biên xuất phát: (0) x = (0,0,0,16,8,12) với cơ sở {A4, A5, A6 } Lập bảng đơn hình: C1 A1 Phương - 1 4 3 0 0 0 Cơ sở Cơ sở án A1 A2 A3 A4 A5 A6 0 A 16 2 1 - 2 1 0 0 x (0) ↔ 4 0 A5 8 - 4 0 2 0 1 0 0 A6 12 1 2 -1 0 0 1 0 1 - 4 - 3 0 0 0 0 A4 10 3/2 0 -3/2 1 0 -1/2 (1) x ↔ 0 A5 8 - 4 0 3 0 1 0 4 A2 6 1/2 1 -1/2 0 0 1/2 24 3 0 - 50 0 2 0 A4 16 -3/2 0 0 1 3/4 -1/2 (2) x ↔ 3 A3 4 - 2 0 1 0 1/2 0 4 A 8 -1/2 1 0 0 1/4 1/2 2 44 -7 0 0 0 5/2 2 (2) Ta thấy trong bảng đơn hình ứng với phương án cực biên x , cơ sở J2 có Δ1 = - 7 < 0 đồng thời Zj1 < 0 ∀j ∈ J2 nên bài toán không có phương án tối ưu vì trị số hàm mục tiêu tăng vô hạn trên tập phương án. Bài 3. Giải bài toán sau bằng phương pháp đơn hình f(x) = - 5x1 - 2x2 - 10/3x3 → min 38
Chương II: Quy hoạch tuyến tính ⎧2x 1 + 4x 2 + 3x 3 ≥ 46 ⎪4x + 2x + 3x ≤ 38 ⎪ 1 3 5 ⎨3x + x ≤ 21 ⎪ 1 3 ⎪ ___ ⎩x j ≥ 0(j = 1,3) Đưa bài toán về dạng chính tắc đó cũng là bài toán dạng chuẩn: f(x) = - 5x1 - 2x2 - 10/3x3 → min ⎧2x 1 + 4x 2 + 3x 3 + x 4 = 46 ⎪4x + 2x + 3x + x = 38 ⎪ 1 3 5 5 ⎨3x + x + x = 21 ⎪ 1 3 6 ⎪ ___ ⎩x j ≥ 0(j = 1,6) Bài toán dạng chuẩn có ngay phương án cực biên xuất phát: (0) x = (0,0,0,46,38,21) với cơ sở đơn vị {A4, A5, A6} = E3. Lập bảng đơn hình. C1 A1 Phương -5 - 2-10/3 0 0 0 Cơ Cơ án A1 A2 A3 A4 A5 A6 sở sở 0 A 46 2 4 3 1 0 0 x (0) ↔ 4 0 A5 38 4 2 3 0 1 0 0 A6 21 3 0 1 0 0 1 0 5 2 10/3 0 0 0 0 A4 32 0 4 7/3 1 0 -2/3 (1) x ↔ 0 A5 10 0 2 5/3 0 1 -4/3 -5 A1 7 1 0 1/3 0 0 1/3 -35 0 2 5/30 0 -5/3 0 A 12 0 0 - 1 1 -2 2 x (2 ↔ 4 -2 A2 5 0 1 5/6 0 1/2 -4/6 -5 A1 7 1 0 1/3 0 0 1/3 -45 0 0 0 0 -1 -1/3 0 A4 18 0 -6/5 0 1 -7/5 6/5 (3 x ↔ -10/3 A5 6 0 6/5 1 0 3/5 -4/5 -5 A1 5 1 -2/5 0 0 -1/5 3/5 -45 0 0 0 0 - 1-1/3 ___ (2) Trong bảng đơn hình ứng với phương án cực biên x có Δk ≤ 0 (k = 1,6) nên: (2) Xopt = X = (7,5,0,12,0,0) 1 Do đó bài toán ban đầu có: x 0pt = (7,5,0) và fmin = -45 39
Chương II: Quy hoạch tuyến tính 2 Tuy nhiên trong bảng đơn hình với x 0pt có Δ3 = 0 (3 ∉ J0) và ∃Z23 = 5/6 > 0; Z33 = 1/3 > 0. (3) Ta đưa A3 vào cơ sở sẽ được phương án Xopt khác. X0pt = X = (5,0,6,18,0,0) nên bài toán có 2 thêm phương án tối ưu: x opt = (5,0,6). Vậy bài toán có vô số phương án tối ưu, tập phương án tối ưu có dạng: 1 2 {Xopt )={ λ x opt +(1 − λ ) x opt ;0 ≤ λ ≤ 1 }và fmin= -45 Bài 4. Giải bài toán bằng phương pháp đơn hình f(x) = - x1 +x2 → max ⎧− x 1 + x 3 + x 5 = 5 ⎪3x − x + 5x ≤ 10 ⎪ 1 4 5 ⎨x − x = 1 ⎪ 2 5 ⎪ ___ ⎩x j ≥ 0(j = 1,5) Đưa bài toán về dạng chính tắc với biến phụ x6 ≥ 0 f (x) = - x1 + x2 → max ⎧− x 1 + x 3 + x 5 = 5 ⎪3x = x + 5x + x = 10 ⎪ 1 4 5 6 ⎨x − x = 1 ⎪ 2 5 ⎪ ___ ⎩x j ≥ 0(j = 1,6) Bài toán có phương án cực biên xuất phát: (0) X = (0,1,5,0,0,10) với cơ sở {A3, A6, A2} = E3 Lập bảng đơn hình C1 Cơ A1 Phương - 1 1 0 0 0 0 sở Cơ sở án A1 A2 A3 A4 A5 A6 0 A 5 -1 0 1 0 1 0 x (0) ↔ 1 0 A6 10 3 0 0 -1 5 1 A2 1 0 1 0 0 -1 0 1 1 0 0 0 -1 0 0 A3 3 -8/4 0 1 1/5 0 -1/5 (1) x ↔ 0 A5 2 3/5 0 0 -1/5 1 1/5 1 A 3 3/5 1 0 -1/5 0 1/5 2 3 8/5 0 0 -1/5 0 1/5 0 A 15 -8 0 5 1 0 -1 x (2 ↔ 4 0 A5 5 -1 0 1 0 1 0 1 A2 6 -1 1 1 0 0 0 6 0 0 1 0 0 0 40
Chương II: Quy hoạch tuyến tính ___ (2) (2) Trong bảng đơn hình ứng với phương án x có Δk ≥ 0 (k = 1,6) nên x là phương án cực (2) biên tối ưu, trong đó Δ1 = Δ6 = 0 (1,6 ∉ J2) nhưng Zj1 < 0, Zj6 ≤ 0 (j ∈ J2) do đó: xopt = x = (2) (0,6,0,15,5) là phương án cực biên tối ưu duy nhất của bài toán ban đầu và fmax = f[x ] = 6. Bài 5. Cho bài toán f (x) = - 2x1 - x2 + x3 + x4 - 4x5 → max ⎧x 1 − x 3 + 4x 5 − 2x 5 ≥ −4 ⎪3x + 2x − x + x ≥ 24 ⎪ 1 2 3 4 ⎨5x + 3x + x + 2x − x = 46 ⎪ 1 2 3 4 5 ⎪ ___ ⎩x j ≥ 0(j = 1,5) a. Chứng tỏ x(0) = (0,2,0,20,0) là phương án cực biên, lợi dụng x(0) giải bài toán bằng phương pháp đơn hình. b. Dựa vào phương án x(0) tìm lời giải của bài toán khi hàm mục tiêu có dạng: f (x) = 5x1 + 2x2 + 4x3 + 4x4 - 2x5 → min Giải. a. Vì x(0) ∈ R5 thoả mãn mọi ràng buộc của bài toán, thoả mãn chặt các ràng buộc 2,3 và 3 (0) (0) (0) ràng buộc dấu: x 1 = x 3 = x 5 = 0 . Hệ 5 ràng buộc chặt này độc lập tuyến tính vì định thức của các matrận tạo bởi các véctơ này: 3 2 -1 1 0 5 3 1 2 -1 1 0 0 0 0 = - 1 ≠ 0 0 0 1 0 0 0 0 0 0 1 Nên x(0) là phương án cực biên của bài toán. Để giải bài toán này bằng phương pháp đơn hình, trước hết ta đưa bài toán về dạng chính tắc: f (x) = -2x1 - x2 + x3 + x4 + x5 → min ⎧x 1 − x 3 + 4x 5 − 2x 5 + x 6 = −4 ⎪3x + 2x − x + x + x = 24 ⎪ 1 2 3 4 7 ⎨5x + 3x + x + 2x − x = 46 ⎪ 1 2 3 4 5 ⎪ ___ ⎩x j ≥ 0(j = 1,7) Từ phương án cực biên X(0) của bài toán đã cho suy ra phương án cực biên của bài toán -(0) chính tắc là x = (0,2,0,20,0,2,0) với cơ sở {A2, A4, A6} và J0 = {2,4,6}. Ta tìm matrận hệ số ___ phân tích của véctơ Ak (k = 1,7) và véctơ B qua cơ sở J0 bằng phương pháp biến đổi sơ cấp trên các hàng của ma trận. 41
Chương II: Quy hoạch tuyến tính ⎡− 1 1 − 4 0 2 1 0 4 ⎤ h1→h1 +h 2 →h 2 ⎢ ⎥ 2h 2 −h3 →h3 ⎢ 3 2 − 1 1 0 0 1 24 ⎥ ⎯⎯→⎯⎯⎯ ⎣⎢ 5 3 1 2 - 1 0 0 46⎦⎥ ⎡− 1 1 − 4 0 2 1 0 4 ⎤ −h1 +h1→h1 −2h3 +h2 →h 2 ⎢ ⎥ 2h 2 −h3 →h3 ⎢ 3 2 − 1 1 0 0 1 24⎥ ⎯⎯→⎯⎯⎯ ⎣⎢ 1 1 − 3 0 1 0 2 2 ⎦⎥ ⎡− 2 0 − 1 0 1 1 − 2 2 ⎤ ⎢ ⎥ ⎢ 1 0 5 1 − 2 0 − 3 20⎥ ⎣⎢ 1 1 − 3 0 1 0 2 2 ⎦⎥ Lập bảng đơn hình ứng với phương án cực biên x(0) và áp dụng thuật toán đơn hình. Toàn bộ quá trình tính toán ở bảng C A -2 -1 3 1 -4 0 0 1 1 Phương Cơ Cơ án A A A A A A A sở sở 1 2 3 4 5 6 7 (0) x ↔ 0 A6 2 -2 0 -1 0 1 1 -2 1 A4 20 1 0 5 1 -2 0 -3 -1 A2 2 1 1 -3 0 1 0 2 18 2 0 5 0 1 0 -5 0 A6 6 -9/5 0 0 1/5 3/5 1 -13/5 3 A 4 1/5 0 10 1/5 -2/5 0 -3/5 x(1)↔ 5 -1 A2 14 8/5 1 3/5 -1/5 0 1/5 -2 -1 0 0 -1 3 0 -2 -4 A5 10 -3 0 0 1/3 1 5/3 -13/3 3 A5 8 -1 0 1 1/3 0 2/3 -7/3 (2) x ↔ -1 A2 16 1 1 0 2/3 0 1/3 -2/3 -32 -1 0 0 -2 0 -5 11 (2) Trong bảng đơn hình ứng với phương án cực biên X có Δ7 = 11 > 0 nhưng Zj7 < 0 (∀j∈J2) nên bài toán không có lời giải vì f(x) → - ∞ trên tập phương án. b. Trong trường hợp f (X) = 5X1 + 2X2 + 4X3 + 4X4 - 2X5 → min (0) Ta lập bảng đơn hình ứng với các ck mới và với x = (0,2,0,20,0,2,0). 42
Chương II: Quy hoạch tuyến tính C A 5 2 4 4 -2 0 0 1 1 Phương Cơ Cơ án A A A A A A A sở sở 1 2 3 4 5 6 7 x(0)↔ 2 A6 2 -2 0 -1 0 1 1 -2 4 A4 20 1 0 5 1 -2 0 -3 2 A2 2 1 1 -3 0 1 0 2 84 2 0 10 0 -4 0 -8 0 A 6 -9/5 0 0 1/5 3/5 1 -13/5 x(1)↔ 6 4 A 4 1/5 0 1 1/5 -2/5 0 -3/5 5 2 A 14 8/5 1 0 3/5 -1/5 0 1/5 2 -2 -1 0 0 -1 3 0 -2 -2 A5 10 -3 0 0 1/3 1 5/3 -13/3 (2) x ↔ 4 A5 8 -1 0 1 1/3 0 2/3 -7/3 2 A2 16 1 1 0 2/3 0 1/3 -2/3 44 -1 0 0 -2 0 0 -2 ___ (1) (1) (1) Bảng đơn hình tương ứng với phương án cực biên X có Δk ≤ 0 (k = 1,7) nên X opt = X = (0,14,4,0,0,6,0) và fmin = 44. Nhưng trong đó có Δ5 = 0 (5 ∉ J1) do đó đưa A5 vào cơ sở ta được phương án tối ưu khác: (2) (2) X opt = X = (0,16,8,0,10,0,0) với cơ sở {A5, A3, A2}. Vậy khi đó bài toán có vô số phương án tối ưu: (1) (2) {Xopt}={λ X opt +(1-λ) X opt ; 0 ≤ λ ≤ 1 } và fmin = 44 Bài 6. Giải bài toán bằng phương pháp đơn hình f (x) = 2x1 + x2 - x3 - x4 → min ⎧x 1 − x 2 + 2x 5 − 2x 4 = 2 ⎪3x + x − 3x + x = 6 ⎪ 1 2 3 4 ⎨x + x + x + x = 7 ⎪ 1 2 3 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,4) Vì trong matrận hệ số của các ẩn trong hệ ràng buộc không chứa véctơ đơn vị nào, ta lập bài toán “M” với các ẩn giả x5, x6, x7 ≥ 0 có dạng: __ f ( x ) = 2x1 + x2 - x3 - x4 + M (x5 + x6 +x7) → min ⎧x 1 − x 2 + 2x 5 − x 4 + x 5 = 2 ⎪2x + x − 3x + x x = 6 ⎪ 1 2 3 4 6 ⎨x + x + x + x + x = 7 ⎪ 1 2 3 4 7 ⎪ ___ ⎩x j ≥ 0 (j = 1,7);M >> 0 Bài toán “M” có phương án cực biên xuất phát: 43
Chương II: Quy hoạch tuyến tính ___()) x = (0,0,0,0,2,6,7) với cơ sở đơn vị: {A5,A6,A7} = E3 Lập bảng đơn hình C A 2 1 -1 -1 M M M 1 1 Phương Cơ Cơ A án 1 A A A A A A sở sở 2 3 4 5 6 7 M A5 2 1 -1 2 -1 1 0 0 __(0) x ↔ M A6 6 2 1 -3 1 0 1 0 M A7 7 1 1 1 1 0 0 1 15M 4M-2 M-1 1 M+1 0 0 0 __(1) 2 A 2 1 -1 2 -1 0 0 x 1 ↔ M A6 2 0 3 -7 3 1 0 M A7 5 0 2 -1 2 0 1 __(2) 7M+4 0 5M-3 -8M+5 5M-1 x ↔ 2 A1 8/3 1 0 -1/3 0 0 -1 A4 2/3 0 1 -7/3 1 0 M A3 11/3 0 0 11/3 0 1 11M+14 0 - 2 11M+8 0 0 __(3) 3 3 x ↔ 2 A1 3 1 0 0 0 -1 A4 3 0 1 0 1 -1 A3 1 0 0 1 0 2 0 - 2 0 0 ___ -(3) Bảng đơn hình ứng với phương án cực biên x có Δk ≤ 0 (k = 1,7) nên bài toán “M” có __ __(3) phương án tối ưu: x opt = x = (3,0,1,3,0,0,0) trong đó các ẩn giả x5 = x6 = x7 = 0. Vậy bài toán ban đầu có phương án tối ưu là: __ xopt = (3,0,1,3) và fmin = f( x opt) = 2 Bài 7. Giải bằng phương pháp đơn hình bài toán sau f(x)t = x1 - x2 +3x3 → min ⎧ ⎪− 2x 1 + x 2 + 3x 5 = 2 ⎪ ⎨x 1 + x 2 + 2x 3 = 1 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,3) Giải. Đưa về bài toán “M” có 2 ẩn giả x4, x5 ≥ 0, có dạng: ___ f( x ) = x1 - x2 +3x3 + M (x4 + x5) → min ⎧ ⎪− 2x 1 + x 2 + 3x 5 + x 4 = 2 ⎪ ⎨x 1 + x 2 + 2x 3 + x 5 = 1 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,5); M >> 0 44
Chương II: Quy hoạch tuyến tính __(0) Bài toán “M” có phương án cực biên xuất phát: x = (0,0,0,2,1) với cơ sở đơn vị {A4, A5 } = E2. Lập bảng đơn hình: C A 1 - 1 2 MM 1 1 Phương Cơ Cơ án A A A AA sở sở 1 2 3 4 5 __(0) x ↔ M A4 2 - 2 1 3 1 0 M A5 1 1 1 2 0 1 __(1) 3M -M-1 2M+1 5M-2 0 0 x ↔ M A 1/2 - 7/2 -1/2 0 1 4 M A 1/2 1/2 1/2 1 0 3 M + 2 − 7M − M + 4 0 0 2 2 2 __((1) ___ Bảng đơn hình ứng với phương án cực biên x có Δk ≤ 0 (k =1,5) nên bài toán “M” có: __ __(1) 1 1 x opt = x = 0,0, , ,0) . Nhưng có ẩn giả x4 = 1/2 > 0 nên bài toán đầu không có phương án tối 2 2 ưu (vô nghiệm) Bài 8. Giải bằng phương pháp đơn hình bài toán sau. f(x) = x1 - 2x2 - 4x3 → max ⎧2x 1 + 3x 2 − 4x 5 ≤ 2 ⎪− 3x − 5x + x ≤ - 3 ⎪ 1 2 3 ⎨x + x − x = 6 ⎪ 1 2 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,4) Giải. Đưa bài toán về dạng chính tắc với hai biến phụ x5, x6 ≥ 0 ta được: f(x) = x1 - 2x2 - 4x3 → max ⎧2x 1 + 3x 2 − 4x 5 + x 5 = 5 ⎪− 3x − 5x + x + x = - 3 ⎪ 1 2 3 6 ⎨x + x − x = 6 ⎪ 1 2 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) Trong ma trận hệ số của ẩn ở hệ ràng buộc của bài toán chính tắc đã có một véctơ đơn vị A5. Đưa về bài toán “M” với hai biến giả x7, x8 ≥ 0 ta được: 45
Chương II: Quy hoạch tuyến tính ___ f( x ) = x1 - 2x2 =- 4x3 - M (x7 + x8) → max ⎧2x 1 + 3x 2 − 4x 5 + x 5 = 5 ⎪− 3x + 5x + x + x + x = −3 ⎪ 1 2 3 6 7 ⎨x + x − x + x = 6 ⎪ 1 2 4 8 ⎪ ___ ⎩x j ≥ 0 (j = 1,8) Bài toán “M” có phương án cực biên xuất phát: __(0) x = (0,0,0,0,5,0,3,6) với cơ sở: {A5, A7, A8} = E3 Lập bảng đơn hình C A 2 A 1 -1 -1 M M M 1 1 Phương 1 Cơ Cơ án A A A A A A A A sở sở 1 2 3 4 5 6 7 7 __(0) 0 A5 5 2 3 -4 0 1 0 0 0 x ↔ -M A7 3 3 5 -1 0 0 -1 1 0 -M A8 6 1 1 0 -1 0 0 0 1 -9M 04M-4 -6M+2 M 0 M 0 0 __(1) 0 A5 16/5 1/5 0 -17/5 0 1 3/5 0 x ↔ -2 A2 3/5 3/5 1 -1/5 0 0 -1/5 0 -M A8 27/5 2/5 0 1/5 -1 0 1/5 1 -27+6 -2M+1 0 -M-2 M 0 -M-2 0 5 5 5 5 0 A5 3 0 -1/3 -50/15 0 1 2/3 __(2) 1 A1 1 1 5/3 -1/3 0 0 -1/3 x ↔ M A8 5 0 -2/3 1/3 -1 0 1/3 -5M+1 0 2M+11 M - 1 -M+1 0 -M-1 3 3 3 0 A5 53 0 -7 0 -10 1 4 __(3) 1 A1 6 1 1 0 -1 0 0 x ↔ 0 A3 15 0 -2 1 -3 0 1 6 0 3 0 0 0 0 0 A6 53/4 0 -7/4 0 -10/4 1/4 1 __(4) 1 A 6 1 1 0 - 1 0 0 x 1 ↔ 0 A3 7/4 0 -1/4 1 -2/4 -1/4 0 6 0 3 0 0 0 0 __(3) ___ Bảng đơn hình ứng với phương án x của bài toán “M” có Δk ≤ 0 (k = 1,8) nên __ __(3) x opt = x = (6,0,15,0,53,0,0,0) và các ẩn giả x7 = x8 = 0. Do đó bài toán ban đầu có: __(3) (1) x opt = (6,0,15,0) và fmax = 6. Nhưng trong bảng đơn hình ứng với x có Δ6 = 0 (6 ∉ J3) và Z36 = 1 > 0 do đó đưa A6 vào cơ sở ta được phương án tối ưu khác: 46
Chương II: Quy hoạch tuyến tính (4) x opt = (6,0,1/ 4,0,0,53 / 4,0,0) các ẩn giả x7 = x8 = 0 nên bài toán đầu có (2) x opt = (6,0,7 / 4,0) . Vậy khi đó bài toán có vô số phương án tối ưu: (1) (2) {Xopt} = {λ x opt + (1 − λ)x opt ;0 ≤ 1 } và fmax = 6 Bài 9. Giải và biện luận bài toán sau theo tham số λ f(x) = 5x1 + 2x2 + 5x3 → min ⎧ ⎪3λ(x 1 − 1) − x 2 + 4x 5 ≥ 2 - 3λ ⎪ ⎨λx 1 + x 2 + x 3 ≥ 3 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,3);λ ≠ 0 Giải. Đưa bài toán về dạng chính tắc với 2 biến phụ x4, x5 ≥ 0 sau đó đưa về bài toán “M” __ với ẩn giả x6 ≥ 0: f( x ) = 5x1 + 2x2 + 5x3 + Mx6 → min ⎧ ⎪3λ(x 1 − 1) − x 2 + 4x 5 + x 6 = 2 - 3λ ⎪ ⎨λx 1 + x 2 + x 3 + x 5 = 3 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,6);λ ≠ 0; M >> 0 __ (0) Bài toán “M” có ngay phương án cực biên xuất phát: x = (0,0,0,0,3,2) với cơ sở đơn vị: {A6, A5 } = E2. Lập bảng đơn hình C1 A1 Phương 5 2 5 0 0 M Cơ Cơ án A1 A2 A3 A4 A5 A6 sở sở __(3) M A6 2 3λ - 1 4 - 1 0 1 x ↔ 0 A5 3 λ 1 1 0 1 0 __(4) 2M 3Mλ-5 -M-2 4M-5 - M 0 0 x ↔ 5 A3 1/2 3λ/4 -1/4 1 -1/4 0 0 A5 5/2 λ/4 5/4 0 1/4 1 5/2 15λ-20 -13/4 0 -5/4 0 4 __(2) 5 A1 2/(3λ) 1 -1/(3λ) 4/(3λ) -1/(3λ) 0 x ↔ 0 A5 7/3 0 4/3 -1/3 1/3 1 10/(3λ) 0 -5- 6λ 20-15λ - 5 0 3λ 3λ 3λ (0) Trong bảng đơn hình ứng với x tồn tại: Δ1 = 3Mλ -5 và Δ3 = 4M -5 > 0. 4 (1) a. Nếu 0 ≠ λ Δ1 và Δ3 > 0. Đưa véctơ A3 vào cơ sở ta được phương án x = 3 (0,0,1/2,0,5/2,0) ẩn giả x6 = 0 nên bài toán ban đầu có xopt = (0,0,1/2) và fmin = 5/2. 47
Chương II: Quy hoạch tuyến tính 4 __(0) __(1) b. Nếu λ ≥ thì Δ1 ≥ Δ3 > 0 đưa véctơ A1 vào cơ sở cải tiến x → x ta được phương án 3 __(1) 10 x opt = (2/(3λ),0,0,0,7/3,0) ẩn giả x6 = 0 nên bài toán ban đầu có xopt = (2/(3λ),0,0)và fmin = 3λ 4 Kết luận: nếu 0 ≠ λ 0, đã bài toán về dạng chính tắc với biến phụ x4 ≥ 0, sau đó đưa về bài toán “M” với biến giả x5 ≥ 0. __ f( x ) = -2x1 - 5x2 + x3 - Mx5 → max ⎧ ⎪ax 1 − 2x 2 - x 4 + x 5 = 1 ⎪ ⎨x 1 + ax 2 + x 3 = 5 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,5); M >> 0 ___(0) Bài toán “M” có phương án cực biên xuất phát x = (0,0,5,0,1 với cơ sở đơn vị: {A5, A3 } = E2. Lập bảng đơn hình C1 A1 Phương - 2 - 5 1 0 - M Cơ Cơ án A1 A2 A3 A4 A5 sở sở __(0) -M A5 1 a - 2 0 - 1 0 x ↔ 1 A5 5 1 a 1 0 1 __(1) -M+5 - aM+3 2M + a + 5 0 M 0 - M A 1 - 5a 0 - 2 - a2 - a - 1 0 x ↔ 5 - 2 A 5 1 a 1 0 1 1 __(1) 0 (2+a2)M-2a+5 aM-3 M 0 x ↔ - 2 A1 1/2 1 - 2/a 0 -1/a 1 A5 5- 1/a 0 a + 2/a 1 1/a 5- 3/a 0 a + 6/a+5 0 3/a 48
Chương II: Quy hoạch tuyến tính (0) Trong bảng đơn hình ứng với phương án x : tồn tại Δ1 = - aM + 3 ⇔ 0 0 (a < 1/5) nên bài toán đầu không có phương án tối ưu. 1 1 (1) Nếu ≤ 5 ⇔ a ≥ , véctơ A5 được đưa ra khỏi cơ sở, ta được phương án x opt = (1/a,0,5- a 5 1/a,0,0) ẩn giả x5 =0, nên bài toán ban đầu có xopt = (1/a,0,5-1/a) và fmin = 5-3/a. Kết luận: Nếu a < 1/5 bài toán ban đầu vô nghiệm 1 Nếu a ≥ bài toán có: xopt = (1/a,0,5-1/a) và fmin=5-3/a. 5 2.7. ĐỐI NGẪU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH. 2.7.1 Các dạng bài toán đối ngẫu. a, Bài toán đối ngẫu không đối xứng Xét bài toán qui hoạch tuyến tính dạng chính tắc. n f(X) = ∑ cxj j → min (2.19) j=1 ⎧ n ⎪∑ axij j== b i ( i 1, m ) (2.20) ⎨ j=1 ⎪ ⎩xjnj ≥=0 ( 1, ) (2.21) Tương ứng với nó ta có bài toán đối ngẫu không đối xứng: n ϕ(Y) = ∑ byi i → max (2.22) j=1 ⎧ m ⎪∑ axij j≤= c j (1,) j n (2.23) ⎨ i=1 ⎪ ⎩yRj ∈=( i 1, m ) (2.24) b. Bài toán đối ngẫu đối xứng. Xét bài toán qui hoạch tuyến tính dạng chuẩn tắc. n f(X) = ∑ cxj j → min (2.25) j=1 ⎧ n ⎪∑ axij j≥= b i ( i 1, m ) (2.26) ⎨ j=1 ⎪ ⎩xjnj ≥=0 ( 1, ) (2.27) 49
Chương II: Quy hoạch tuyến tính Tương ứng với nó ta có bài toán đối ngẫu đối xứng. n ϕ(Y) = ∑ byi i → max (2.28) j=1 ⎧ m ⎪∑ axij j≤= c j ( j 1, n ) (2.29) ⎨ i=1 ⎪ ⎩yimj ≥=0 ( 1, ) (2.30) c. Bài toán đối ngẫu tổng quát Xét bài toán qui hoạch tuyến tính dạng tổng quát sau: n f(X) = ∑ cxj j → min j=1 ⎧ n ⎪∑ axij j=∈ b i () i I1 (2.31) ⎪ j=1 ⎪ n ⎪∑ axij j≥∈ b i ( i I2 ) (2.32) ⎪ j=1 ⎪ n ⎨ ∑ axij j≤∈ b i () i I3 (2.33) ⎪ j=1 ⎪ ⎪xRj ∈∈( jJ1 ) (2.34) ⎪xjJ≥∈0 ( ) (2.35) ⎪ j 2 ⎪ ⎩xjJj ≤∈0 (3 ) (2.36) Trong đó: Ii , Ji (i = 13, ) - Tập chỉ số các phương trình, bất phương trình và các ẩn. ⏐I1⏐+ ⏐I2⏐+⏐I3⏐= m , ⏐J1⏐+ ⏐J2⏐+⏐J3⏐= n Với ⏐Ii⏐,⏐Ji⏐- lực lượng của tập Ii, Ji (i = 13, ). Tương ứng với nó ta có bài toán đối ngẫu tổng quát sau: n ϕ(Y) = ∑ byi i → max (2.37) j=1 ⎧ m ⎪∑ ayij j=∈ c j ( j J1 ) (2.20) ⎪ i=1 ⎪ m ⎪∑ ayij j≤∈ c j () j J2 (2.38) ⎪ i=1 ⎪ m ⎨ ∑ ayij j≥∈ c j ( j J3 ) (2.39) ⎪ i=1 ⎪ ⎪yRj ∈∈( iI1 ) (2.40) ⎪yiI≥∈0 ( ) (2.41) ⎪ j 2 ⎪ ⎩yiIj ≤∈0 (3 ) (2.42) Chú ý: Khi thành lập bài toán đối ngẫu cần chú ý ma trận hệ số các ẩn trong hệ ràng buộc của hai bài toán là hai ma trận chuyển vị của nhau. 50
Chương II: Quy hoạch tuyến tính 2.7.2. Cặp ràng buộc đối ngẫu Gọi hai cặp ràng buộc (kể cả ràng buộc về dấu) trong hai bài toán đối ngẫu cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu. Chẳng hạn, với cặp bài toán đối ngẫu đối xứng có tất cả m+n cặp ràng buộc đối ngẫu sau: n ∑axij j≥=↔≥= b,(i1,m) i y i 0,(i1,m) j=1 n ∑axij j≥=↔∈= b,(i1,m) i y i R,(i1,m) i=1 m xj≥=↔ 0,(j 1,n)∑ aij ≤ c i ,(j = 1,n) i=1 2.7.3. Các tính chất của bài toán đối ngẫu. 1. Đối với hai phương án bất kỳ X,Y của một cặp bài toán đối ngẫu f(X)→ min ta luôn có: f(X) ≥ ϕ(Y) 2. Nếu đối với hai phương án X* , Y* của một cặp bài toán đối ngẫu mà f(X*) = ϕ(Y*) thì X* , Y* là hai phương án tối ưu. 2.7.4. Quan hệ của cặp bài toán đối ngẫu Định lý: Đối với một cặp bài toán đối ngẫu, bao giờ cũng chỉ xẩy ra 1 trong 3 trường hợp sau: • Cả hai bài toán cùng không có phương án, hiển nhiên cả hai bài toán đều không giải được. • Cả hai bài toán có phương án thì cả hai bài toán đều giải được. Khi đó với mọi cặp phương án tối ưu X* Y* ta luôn có: f(X*) = ϕ(Y*) . • Một trong hai bài toán không có phương án thì bài toán còn lại nếu có phương án thì cũng không có phương án tối ưu. 2.7.5. Các bài tập mẫu Bài 1. Hãy thiết lập bài toán đối ngẫu của bài toán sau: a. f(X) = x1-3x2+ 2x3 → min ⎧23xx12+= ⎪ ⎪−+xxx12332 − = ⎨5714xx+= ⎪ 13 ⎪ ⎩xjj ≥=013(,) b. f(X) = -3 x1-5x2 +4x3+x4 → max ⎧xxxx1234++ −≤6 ⎪ −++≤−32xxx234 5 ⎪ ⎨ ⎪234xx12+−≤ x 4 ⎪ ⎩⎪xjj ≥=014(,) 51
Chương II: Quy hoạch tuyến tính Giải a. Ta thấy bài toán qui hoạch tuyến tính dạng chính tắc có hàm mục tiêu f(X) → min, nên hàm mục tiêu trong bài toán đối ngẫu là ϕ(Y)→ max và hệ ràng buộc bài toán sẽ có dạng " ≤ ". Bài toán đã cho có 3 ràng buộc (không kể ràng buộc về dấu) với dấu "=" nên trong bài toán đối ngẫu sẽ có 3 biến: y1,y2, y3 và các biến này sẽ nhận các giá trị tuỳ ý. Theo định nghĩa bài toán đối ngẫu, ta có bài toán đối ngẫu không đối xứng sau: ϕ(Y) = 3y1 + 2y2 +14y3 → max ⎧251yy12−+ y 3 ≤ ⎪ ⎪yy12+≤−33 ⎨−+yy72 ≤ ⎪ 23 ⎪ ⎩yRii ∈=,(13 , ) b. Đây là bài toán qui hoạch tuyến tính dạng chuẩn tắc có hàm mục tiêu f(X)→max, nên hàm mục tiêu trong bài toán đối ngẫu là ϕ(Y) → min và hệ ràng buộc sẽ có dấu " ≥ ". Bài toán đã cho có 3 ràng buộc với dấu " ≤ " (không kể ràng buộc dấu) nên bài toán đối ngẫu sẽ có 3 biến y1, y2, y3 ≥ 0. Theo định nghĩa bài toán đối ngẫu, ta có bài toán đối ngẫu đối xứng sau đây: ϕ(Y) = 6y1-5y2+4y3 → min ⎧yy+≥−23 ⎪ 12 ⎪yyy123−+≥−35 ⎪ ⎨yy12+≥24 ⎪−+yy −31 y ≥ ⎪ 12 3 ⎪ ⎩yii ≥=013(,) Bài 2. Xét bài toán: f(X) = -2x1+x2-4x3→ min ⎧36xx12−+=− 2 x 4 8 ⎪ ⎪−+23xxx123 +≥ 9 ⎨ ⎪−+47510xxx234 + ≤ ⎪ ⎩xx13,,,≥≤∈00 x 4 x 2 R Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của hai bài toán. Giải Bài toán đối ngẫu. ϕ(Y) = -8y1+9y2+10y3→ max. 3y1 - 2y2 ≤ - 2 - 6y1 + 3y2 - 4y3 = 1 y2 + 7y3 ≤ - 4 2y1 + 5y3 ≥ 0 y1 ∈ R,, y2 ≥ 0, y3 ≤ 0 52
Chương II: Quy hoạch tuyến tính Các cặp ràng buộc đối ngẫu. 3x1-6x2+2x4 = 8 ↔ y1 ∈R -2x1+3x2+x3 ≥ 9 ↔ y2 ≥ 0 -4x2+7x3+5x4 ≤ 10 ↔ y3 ≤ 0 x1 ≥ 0 ↔ 3y1-2y2 ≤ -2 x2 ∈R ↔ -6y1+3y2-4y3 = 1 x3 ≥ 0 ↔ y2 +7y3 ≤ -4 x4 ≤ 0 ↔ 2y1+5y3 ≥ 0 Bài 3. Cho bài toán: f(X)= 7x1+6x2-12x3+x4 →max. 2x1 - 2x2 - 3x3 + 2x4 = 8 3x2 + 2x3 - 2x4 ≤ - 1 2x1 - 3x3 + x4 = 10 x3 ≥ 0 (j = 1,4) Lập bài toán đối ngẫu của bài toán trên và xác định các cặp ràng buộc đối ngẫu. Xét 2 véctơ X0 = (0,6,0,10), Y0 = (-3,0,7). Chứng tỏ rằng X0, Y0 là phương án tối ưu của cặp bài toán đối ngẫu. Giải Bài toán đối ngẫu có dạng: ϕ(Y) = 8y1- y2 + 10y3→ min ⎧22yy13+≥ 7 ⎪ −+22yy13 ≥ 6 ⎪ ⎨−+32yyy123 − 3 ≥− 12 ⎪22yyy−+≥ 1 ⎪ 123 ⎩⎪yRy123∈≥∈,,0 yR Các cặp ràng buộc đối ngẫu: 2x1-2x2-3x3+2x4 = 8 ↔ y1 ∈R 3x2 + 2x3 - 2x4 ≤ -1 ↔ y2 ≥ 0 2x1-3x3+x4 = 10 ↔ y3 ∈R x1 ≥ 0 ↔ y1 +2y3 ≥ 7 x2 ≥ 0 ↔ -2y1 +3y2 ≥ 6 x3 ≥ 0 ↔ -3y1 +2y2 -3y3 ≥ -12 x4 ≥ 0 ↔ 2y1-2y2+y3 ≥ -1 Theo tính chất 2 đối ngẫu, để chứng minh X0, Y0 là phương án tối ưu ta phải chứng minh: X0, Y0 là phương án của cặp bài toán đối ngẫu và f(X0)= ϕ (Y0). 53
Chương II: Quy hoạch tuyến tính Thật vậy, thay X0 = (0,6,0,10) vào tất cả các ràng buộc của bài toán gốc ta thấy X0 thoả mãn mọi ràng buộc của bài toán gốc. Suy ra X0 là phương án của bài toán gốc. Thay Y0 = (-3,7,0) vào các ràng buộc của bài toán đối ngẫu thấy thoả mãn suy ra Y0 là phương án của bài toán đối ngẫu. Mặt khác ta lại có: f(X0) = 7.0+6.6-12.0+10 = 46 ϕ(Y0) = 8.(-3)-0+10.7 = 46 Nên f(X0) = ϕ (Y0). Vậy X0, Y0 là phương án tối ưu của cặp bài toán đối ngẫu (tính chất 2). Bài 4. Cho bài toán. f(X) = -x1-5x2+4x3-2x4 →min ⎧ xxxx1234−+−≤4613 ⎪ ⎪ xx12++≤239 x 4 ⎨−−−+≤328xxxx ⎪ 1234 ⎪ ⎩ xjnj ≥=0( 1;) Dùng định lý đối ngẫu chứng tỏ bài toán đã cho giải được Giải Bài toán đối ngẫu: ϕ(Y) = 13y1+9y2+8y3→ max ⎧yy+−31 y ≤− ⎪ 13 3 ⎪−+42yyy123 −≤− 5 ⎪ ⎨yy13−≤4 ⎪632yy++≤− y 2 ⎪ 12 3 ⎪ ⎩yii ≤=013(,) Để chứng tỏ bài toán đã cho giải được ta cần chứng minh: - Bài toán gốc có phương án. - Bài toán đối ngẫu có phương án. Thật vậy Với bài toán gốc, xét véctơ X0 = (0,0,0,0). Thay vào hệ ràng buộc của bài toán ta được: x1-4x2+x3-6x4 = 0 <13 = VP. x1+2x2+3x4 = 0 <9 = VP. -3x1-x2-x3+2x4 = 0 < 8 = VP. xj = 0 (,)j = 14 thoả mãn Như vậy X0 là phương án của bài toán, tức là bài toán có phương án. 54
Chương II: Quy hoạch tuyến tính Với bài toán đối ngẫu, xét véctơ Y0 = (0,-3,0) thay vào hệ ràng buộc của bài toán đối ngẫu, ta được: y1+y2-3y3 = -3 <-1 = VP. - 4y1+2y2-y3 = -6 <-5 =VP y1-y3 = 0 < 4 =VP. - 6y1+3y2+2y3 = -9 <-2 =VP. y1 = 0 y2= -3 y3 = 0 thoả mãn yj ≤ 0 , (,)i = 13 . Như vậy Y0 là phương án của bài toán đối ngẫu, tức là bài toán đối ngẫu có phương án. Theo định lý về mối quan hệ của cặp bài toán đối ngẫu thì cả hai bài toán trên đều có phương án tối ưu, tức là bài toán gốc giải được. 2.8. CÁC ĐỊNH LÝ ĐỐI NGẪU VÀ Ý NGHĨA CẶP BÀI TOÁN ĐỐI NGẪU 2.8.1.Định lý 1 (đối ngẫu). Nếu 1 trong 2 bài toán đối ngẫu có lời giải thì bài toán kia cũng có lời giải và khi đó với mọi cặp phương án tối ưu X*, Y* ta luôn có: f(X*) = ϕ(Y*). Hệ quả 1. Điều kiện cần và đủ để cặp phương án X*, Y* của hai bài toán đối ngẫu tối ưu là: f(X*) = ϕ(Y*). 2. Điều kiện cần và đủ để cặp bài toán đối ngẫu giải được là mỗi bài toán có ít nhất một phương án. 2.8.2. Định lý 2 (về độ lệch bù). Điều kiện cần và đủ để 2 phương án X, Y của một cặp bài toán đối ngẫu tối ưu là trong các cặp ràng buộc đối ngẫu nếu một ràng buộc thoả mãn với dấu bất đẳng thức thực sự (lỏng) thì ràng buộc kia phải thoả mãn với dấu bằng(chặt). Hệ quả Nếu một ràng buộc là lỏng đối với một phương án tối ưu của bài toán này thì ràng buộc đối ngẫu cuả nó phải là chặt đối với mọi phương án tối ưu của bài toán kia. 2.8.3. Ứng dụng của định lý độ lệch bù phân tích tính chất tối ưu của một phương án Cho X là phương án của bài toán gốc, để phân tích tính chất tối ưu của X ta làm như sau: Giả sử X là phương án tối ưu, theo định lý độ lệch bù mọi phương án tối ưu Y của bài toán đối ngẫu phải thoả mãn chặt các ràng buộc đối ngẫu với các ràng buộc mà X thoả mãn lỏng. Các ràng buộc này tạo thành một hệ phương trình đối với Y. Giải hệ phương trình này để tìm nghiệm nếu: Hệ vô nghiệm thì kết luận phương án X không tối ưu. Hệ có nghiệm thì thử các nghiệm vào các ràng buộc còn lại của bài toán đối ngẫu nếu: 55
Chương II: Quy hoạch tuyến tính • Mọi nghiệm Y đều không thoả mãn các ràng buộc còn lại của bài toán đối ngẫu, nghĩa là mọi nghiệm đều không phải là phương án thi X không tối ưu. • Có nghiệm Y là phương án (thoả mãn tất cả các ràng buộc còn lại của bài toán đối ngẫu) thì phương án này là phương án tối ưu đồng thời X là phương án tối ưu, từ đó sẽ xác định được toàn bộ tập phương án tối ưu của bài toán đối ngẫu. Đồng thời nhờ một phương án tối ưu nào đó của bài toán đối ngẫu ta lại xác định được tập phương án tối ưu (nếu có) của bài toán gốc. Để khảo sát ứng dụng này ta sẽ lấy ví dụ trong bài tập mẫu (xét sau). 2.8.4. Ý nghĩa cặp bài toán đối ngẫu Khi phân tích song song một cặp bài toán đối ngẫu ta có thể nhận được những kết luận hay cả về toán học cả về ý nghĩa king tế. Để phân tích được nhiều khía cạnh về mối quan hệ của cặp bài toán đối ngẫu ta sử dụng cặp bài toán đối ngẫu đối xứng (7) → (9), (10)→(11): n (P): f(X) = ∑ cxjj → min j=1 ⎧ n ⎪∑ axij j≥= b i (,) i1 m ⎨ j=1 ⎪ ⎩xjnj ≥=01(,) m ' (P): ϕ(Y) = ∑ byii → max i=1 ⎧ m ⎪∑ ayij j≥= c j (,) j1 n ⎨ i=1 ⎪ ⎩yimi ≥=01(,) a. Ý nghĩa hình học Khi có cj > 0 , ∀ j thì biết ngay được 1 phương án cực biên của bài toán đối ngẫu. Nếu Y0 là phương án cực biên của bài toán đối ngẫu thì khi bài toán gốc thêm 1 ràng buộc ta có (Y0 , 0) vẫn là phương án cực biên của bài toán đối ngẫu. Đôi khi dùng cặp bài toán đối ngẫu để giải gần đúng theo ý nghĩa sau: Giải cả hai bài toán và nếu hiệu giữa các giá trị tương ứng của các hàm mục tiêu đủ nhỏ thì dừng lại và phương án cực biên thu được lấy làm nghiệm gần đúng. b. Ý nghĩa kinh tế Giả sử bài toán (P) mang nội dung kinh tế sau: có n phương pháp khác nhau để sản xuất m loại sản phẩm. Khi sử dụng 1 đơn vị thời gian cho phương pháp j (j= 1, n ) sẽ thu được đồng thời ai j đơn vị sản phẩm i (i= 1, m ) và mất một chi phí là cj (j= 1, n ). Nhu cầu xã hội về sản phẩm i là bi (i= 1, m ). Hãy xác định các khoảng thời gian xj sử dụng mỗi mỗi phương pháp j (j= 1, n ) sao cho tổng chi phí sản xuất là nhỏ nhất với điều kiện tổng số đơn vị sản phẩm i mỗi loại sản xuất ra không ít hơn bi (i= 1, m ). 56
Chương II: Quy hoạch tuyến tính Nội dung kinh tế bài toán (P') sẽ là: Trong những điều kiện như trên hãy tìm một hệ thống giá trị yi (i= 1, m ) sao cho tổng giá trị toàn bộ sản phẩm theo yêu cầu xã hội đạtcực đại với điều kiện tổng các giá trị sản phẩm sản xuất theo từng phương pháp j (j= 1, n ) trong 1 đơn vị thời gian không vượt quá chi phí sản xuất cj (j= 1, n ). Để thích hợp, ta goị véctơ x =(x1,x2, xn) của bài toán (P) là phương án sản xuất, véctơ Y = (y1,y2, ym) của bài toán (P') là phương án đánh giá. Từ định lý về độ lệch bù suy ra: 1. Nếu một phương án sản xuất được sử dụng (xj > 0) thì tổng giá trị các sản phẩm sản xuất m theo phương pháp ấy phải đúng bằng chi phí ().∑ ayij j= c j i=1 2. Nếu một phương án có giá trị (yi >0) thì tổng số đơn vị sản phẩm ấy sản xuất ra phải n đúng bằng nhu cầu ( ∑ axij j= b i ) j=1 Các vấn đề nêu trên hoàn toàn phù hợp với lý luận kinh tế, đồng thời có thể dùnh làm căn cứ để xác định hệ thống giá cả sản phẩm có tác dụng thúc đẩy sản xuất. Để làm phong phú thêm ý nghĩa kinh tế của cặp bài toán đối ngẫu nhờ định lý độ lệch bù, ta sẽ xét ví dụ cụ thể trong phần bài tập mẫu. 2.8.5. Các bài tập mẫu Bài 1. Cho bài toán. f(X) = 5x1-9x2+15x3+7x4+6x5 →min ⎧xxxxx12345+31 −−+≤ ⎪ ⎪42xxxx1345++−= 4 ⎨−−xxx + −21 x ≥− ⎪ 123 5 ⎪ ⎩xjxRj ≥=025(,),1 ∈ Và véctơ X= (0,1,0,2,0). - Viết bài toán đối ngẫu; - Phân tích tính chất của X đối với bài toán đã cho. Giải ϕ(Y) = y1 +4y2-y3 → max ⎧yyy123+−45 = ⎪39yy−≤− ⎪ 13 ⎪−+yyy123 + ≤15 ⎨ ⎪−+yy1227 ≤ ⎪yy−−26 y ≤ ⎪ 12 3 ⎩yyRy12≤∈≥00,,. 3 57
Chương II: Quy hoạch tuyến tính Dễ dàng thấy véctơ X = (0,1,0,2,0) thoả mãn mọi ràng buộc của bài toán nên X- là phương án của bài toán đã cho. Phương án X thoả mãn chặt các ràng buộc 1,2,3 và hai ràng buộc về dấu x1= x3 = x5 = 0 suy ra X thoả mãn chặt 6 ràng buộc chặt Suy ra X không phải là phương án cực biên. Phương án X thoả mãn lỏng 2 ràng buộc về dấu; x2 = 1>0 và x4 = 2>0. Giả sử X là phương án tối ưu, theo định lý về độ lệch bù mọi phương án tối ưu Y của bài toán đối ngẫu phải thoả mãn hệ phương trình: ⎧yyy123+−=45 ⎪ ⎧yyy123+−=45 ⎨39yy13−=− ⇔ ⎨ ⎪ ⎩612yy23−= ⎩−+yy1227 = ⎧ 1 yy=−3 + ⎪ 133 ⎪ ⎪ 1 ⇒ ⎨yy23=+2 ⎪ 6 ⎪yR3 ∈ ⎩⎪ Vậy nghiệm của hệ là: 1 1 Y = (y1,y2,y3) = ( −+3 y , 2 + y , y ), yR∈ 3 3 6 3 3 3 Thay Y vào các ràng buộc còn lại của bài toán ta có: 1 1 • -y1+y2+y3 ≤ 15 ⇒ 3- y3 +2 + y3 +y3 ≤ 15 ⇒ y3 ≤ 12.(1) 3 6 1 1 • y1-y1-2y3 ≤ 6 ⇒ -3 + y3 -2 - y3 -2y3 ≤ 6 ⇒ y3 ≥ -6 (2) 3 6 1 • y1 ≤ 0 ⇒ -3+ y3 ≤ 0 ⇒ y3 ≤ 9 (3) 3 • y3 ≥ 0 (4) Từ (1), (2), (3), (4) ⇒ Y muốn là phương án thì y3 phải thoả mãn điều kiện: 0 ≤ y3 ≤ 9 Kết luận: X là phương án tối ưu của bài toán gốc và Y với 0 ≤ y3 ≤ 9 là phương án tối ưu của bài toán đối ngẫu (theo định lý độ lệch bù). Bài 2. Một nhà máy có 3 phương pháp khác nhau để sản xuất ra 3 mặt hàng 1,2,3. số lượng hàng loại i phải sản xuất tối thiểu là bi chiếc. Nếu áp dụng cách sản xuất thứ j trong một đơn vị thời gian thì chi phí là cj và thu được ai j đơn vị hàng loại i. Các số liệu được cho trong bảng sau: 58
Chương II: Quy hoạch tuyến tính j 1 2 3 bj i 1 4 4 1 16 2 5 3 1 20 3 1 1 1 3 cj 10 8 2 Yêu cầu đối với nhà máy là cần sử dụng phương pháp sản xuất sao cho đảm bảo nhu cầu về sản phẩm đồng thời chi phí là ít nhất. a. Lập dạng toán học của bài toán trên? Viết bài toán đối ngẫu của nó (nói rõ nội dung kinh tế các biến trong bài toán đối ngẫu). b. Dùng lý thuyết đối ngẫu, chứng tỏ véctơ X = (4,0,0) là phương án tối ưu của bài toán gốc. Phân tích ý nghĩa kinh tế trong mối quan hệ giữa hai bài toán trêncơ sở hai phương án tối ưu của chúng. Giải a. Gọi xj là thời gian áp dụng phương pháp sán xuất thứ j (j= 13, ). Dạng toán học của bài toán này là: 3 Tìm véctơ X = (x1,x2,x3) ∈ R : f(X) = 10x1+8x2+2x3 → min ⎧44216xxx123++≥ ⎪ ⎪53xxx123++≥ 20 ⎨xxx++≥3 ⎪ 123 ⎪ ⎩xjj ≥=013(,) Bài toán đối ngẫu: Gọi yi là giá trị của 1 đơn vị hàng loại i (i=13, ). Ta có: ϕ(Y) = 16y1+20y2+3y3 → max ⎧45yyy123++ ≤ 10 ⎪ ⎪43yyy123++ ≤ 8 ⎨22yyy++ ≤ ⎪ 123 ⎪ ⎩yii ≥=013(,) Vậy nội dung kinh tế thì f(X) chính là tổng chi phí, ϕ(Y) là tổng giá trị sản phẩm sản xuất được. 59
Chương II: Quy hoạch tuyến tính b. Giả sử X = (4,0,0) là phương án tối ưu và X thoả mãn lỏng các ràng buộc (3) và x1 = 4 > 0 nên theo định lý về độ lệch bù mọi phương án tối ưu Y =(y1,y2,y3) của bài toán đối ngẫu phải ⎧y3 = 0 thoả mãn hệ phương trình: ⎨ ⎩45yyy123++ 10 4 ⇔ 4y1+5y2 = 10 ⇒ y2 = 2- y1 , y1 ∈ R 5 4 Vậy nghiệm của hệ là: Y= (y1, 2- y1,0 ) , y1 ∈ R 5 Thay vào các ràng buộc còn lại ta được: 4 5 • 4y1+3y2+y3 ≤ 8 ⇒ 4y1+3(2- y1) ≤ 8 ⇒ y1 ≤ (7) 5 4 4 • 2y1+y2+y3 ≤ 2 ⇒ 2y1 + 2- y1 ≤ 2 ⇒ y1 ≤ 0 (8) 5 5 5 • y2 ≥ 0 ⇒ 2- y1 ≥ 0 ⇒ y1 ≤ (9) 4 2 • y1 ≥ 0 (10) Từ (7), (8), (9), (10) ⇒ y1 = 0 Vậy Y = (0,2,0) là phương án của bài toán đối ngẫu, nên theo định lý về độ lệch bù thì X = (4,0,0), Y = (0,2,0) tương ứng là phương án tối ưu của bài toán gốc và bài toán đối ngẫu. Phân tích ý nghĩa kinh tế: Ta có x1 = 4 >0 chứng tỏ cách sản xuất thứ nhất đẫ được sử dụng, chỉ cần 4 đơn vị thời gian cho cách sản xuất thứ nhất là đáp ứng được nhu cầu về sản phẩm và tổng các giá trị các sản phẩm sản xuất được là ϕ(Y) =16.0 +20.2+3.0 = 40. Tương ứng trong đánh giá tối ưu ràng buộc (4) thoả mãn chặt, điều này nói nên với phương pháp sản xuất đó mọi hao phí bỏ ra đếu được chuyển hoá thành giá trị sản phẩm. Đây là cách sản xuất tối ưu cần được áp dụng. Với cách sản xuất này nếu ta tăng thêm 1 đơn vị thời gian thì có thể xây dựng được phương án tối ưu mới với tổng giá trị sản phẩm cao hơn trước là 10. Thay phương án tối ưu Y vào các ràng buộc của bài toán đối ngẫu ta được ràng buộc (5) thoả mãn lỏng, chứng tỏ với phương pháp sản xuất thứ hai mọi hao phí bỏ ra không được chuyển hoá hết thành giá trị sản phẩm nên không sử dụng phương pháp sản xuất này (x2 = 0). Trong phương án tối ưu Y ta có y2 = 2>0, điều này nói nên sản phẩm hàng loại 2 được đánh giá có giá trị và chính nó có vai trò làm tăng tổng giá trị sản phẩm. Tương ứng trong phương án tối ưu X ràng buộc (2) thoả mãn chặt, nghĩa là sản phẩm hàng loại 2 sản xuất vừa đủ nhu cầu tối thiểu, sản phẩm đến đâu tiêu thu đến đấy. Vì vậy trong phương án sản xuất theo hướng sản phẩm hàng loại 2 phải tăng thêm về số lượng. Ở đây ràng buộc (6) của bài toán đối ngẫu cũng thoả mãn chặt, điều này nói nên có thể sử dụng cách sản xuất thứ 3 thay thế cách sản xuất thứ nhất trong trường hợp cách sản xuất thứ nhất gặp khó khăn về trang thiết bị, nhiên liệu Ràng buộc (3) của bài toán gốc thoả mãn lỏng nên 60
Chương II: Quy hoạch tuyến tính trong phương án đánh giá tối ưu Y, sản phẩm này được xem là không có giá trị, nghĩa là trong phương án sản xuất tiếp theo không nên chú trọng sản xuất sản phẩm này. 2.9. PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐỐI NGẪU ĐỐI XỨNG 2.9.1. Đặt vấn đề. Đối với cặp bài toán đối ngẫu đối xứng , lời giải của bài toán này có thể thông qua lời giải của bài toán kia (bằng phương pháp đơn hình) mà không cần giải trực tiếp nó. Xét cặp bài toán đối ngẫu đối xứng sau: n (P): f(X) = ∑cxj j → max j=1 ⎧ n ⎪∑ axij j ≤= bi (,) i1 m ⎨ j=1 ⎪ ⎩xjnj ≥=01(,) n (Q): ϕ(Y) = ∑ byi i → min j=1 ⎧ m ⎪∑ axij j ≥= cj (,) j1 n ⎨ i=1 ⎪ ⎩yimj ≥=01(,) Giả sử Y* =(y1*, y2*, ,ym*) là phương án tối ưu của bài toán (Q). Để tìm Y* ta giải bài toán (P). Đưa bài toán (P) về dạng chính tắc, ta dược bài toán (P'): n (P'): f(X) = ∑cxj j → max j=1 ⎧ n ⎪∑ axij j += xni+ b i (,) i =1 m ⎨ j=1 ⎪ ⎩xjnmj ≥=+01(, ) Giải bài toán (P') bằng phương pháp đơn hình: • Nếu bài toán (P') vô nghiệm thì bài toán (Q) cũng vô nghiệm. • Nếu bài toán (P') có nghiệm tức có phương án tối ưu thì bà toán (Q) cũng có phương án tối ưu và từ dòng cuối cùng của bảng đơn hình ứng với phương án tối ưu của bài toán (P') ta suy ra được phương án tối ưu của bài toán (Q). * * * Công thức suy nghiệm: Y* =(y1*, y2*, ,ym*) = (Δ n+1, Δ n+2, , Δ n+m). * Trong đó Δ n+i , (i= 1, m ) là các số kiểm tra của các biến phụ xn+i ≥ 0, (i= 1, m ) trong bảng đơn hình ứng với phương án tối ưu của bài toán (P')). 61
Chương II: Quy hoạch tuyến tính Giả sử x* =(x1*, x2*, ,xn*) là phương án tối ưu của bài toán (P) thì nghiệm X* của bài toán đó cũng được tìm thông qua các số kiểm tra tương ứng của bài toán đối ngẫu (Q) trong bảng * * * đơn hình ứng với phương án tối ưu. x* =(x1*, x2*, ,xn*) = (-Δ m+1,- Δ m+2, , -Δ m+n). * Trong đó Δ m+j , (j= 1, n ) là các số kiểm tra của các biến phụ ym+j ≥ 0 (j= 1, n ) trong bảng đơn hình ứng với phương án tối ưu của bài toán (Q)). Đối với cặp bài toán đối ngẫu đối xứng , vai trò của bài toán gốc và bài toán đối ngẫu có thể thay thế cho nhau. 2.9.2. Các bài tập mẫu Bài 1. Cho bài toán: f(X) = x1+3x2 +4x3+x4 → min ⎧xx12−+≥224 x 4 ⎪ ⎪ 349xx23−+ x 4 ≥− ⎨−++32xx xx −≥ 10 ⎪ 12 34 ⎪ ⎩xjj ≥=014(,) - Viết bài toán đối ngẫu. - Giải bài toán đối ngẫu bằng phương pháp đơn hình, từ đó suy ra nghiệm cho bài toán trên. Giải ϕ(Y) = 4y1- 9y2+10y3 → max. ⎧yy−≤31 ⎪ 13 ⎪−+23yyy123 +≤ 3 ⎪ ⎨ −+yy2324 ≤ ⎪24yyy+− ≤ 1 ⎪ 123 ⎪ ⎩yii ≥=013(,) Đưa bài toán đối ngẫu về dạng chính tắc bằng cách thêm vào bài toán các biến phụ yi ≥ 0 (i= 13, ) . Ta có: ϕ(Y) = 4y1- 9y2+10y3 → max. ⎧yyy−+=31 ⎪ 134 ⎪−+23yyyy1235 ++= 3 ⎪ ⎨ −+yyy23624 + = ⎪24yyyy+−+= 1 ⎪ 1237 ⎪ ⎩yii ≥=017(,) Từ bài toán dạng chính tắc này ta có ngay phương án cực biên xuất phát 0 4 Y = (0,0,0,1,3,4,1) với cơ sơ đơn vị E4 = {AAAA4567,,, } trong R . Lập bảng đơn hình giải bài toán chính tắc đó với phương án cực biên xuất phát Y0 . 62
Chương II: Quy hoạch tuyến tính Bảng 3 có Δj ≥ 0 ∀ j= 17, . Phương án tối ưu của bài toán chính tắc là: 3 11 Y = ( ,0,2, ,4,0,0) , ϕmax = 26. opt 2 2 3 Suy ra phương án tối ưu của bài toán đối ngẫu là: Yopt = ( ,0,2) , ϕmax = 26. 2 Từ bảng 3 ta suy ra phương án tối ưu của bài toán gốc là: Xopt = (x1,x2,x3,x4) = (Δ$, Δ5, Δ6, Δ7) = (0,0,6,2) và fmin = ϕmax = 26. Bài 2. Cho bài toán: f(X) = 2x1- x2 + 4x3 → max ⎧xx12+−25 x 3 ≤ ⎪ ⎪xx12−≤24 ⎨xx+≤2 ⎪ 23 ⎪ ⎩xjj ≥=013(,) Viết bài toán đối ngẫu. Tìm nghiệm của bài toán trên thông qua bài toán đối ngẫu của nó. Giải Bài toán đối ngẫu: ϕ(Y) = 5y1+4y2+2y3 → min ⎧yy12+≥2 ⎪ ⎪yyy123−+21 ≥− ⎨−+24yy ≥ ⎪ 13 ⎪ ⎩yii ≥=013(,) ⇔ ϕ(Y) = 5y1+4y2+2y3 → min ⎧yy12+≥2 ⎪ ⎪−+yyy12321 − ≤ ⎨−+24yy ≥ ⎪ 13 ⎪ ⎩yii ≥=013(,) ⇔ ϕ( Y) = 5y1+4y2+2y3 → min ⎧yy12+− y 4 =2 ⎪ ⎪−+yyyy123521 − + = ⎨−+24yy − y = ⎪ 13 6 ⎪ ⎩yii ≥=016(,) ⇔ ϕ ()Y = 5y1+4y2+2y3 +My7+My8 → min 63
Chương II: Quy hoạch tuyến tính ⎧yy12+−+= y 4 y 7 2 ⎪ ⎪−+−+=yyyy123521 ⎨−+24yy − y += y ⎪ 13 6 8 ⎪ ⎩yii ≥=018(,) Từ bài toán này ta có ngay phương án cực biên xuất phát: 0 3 Y = (0,0,0,0,1,0,2,4) với cơ sở đơn vị E3 = {AAA758,,} trong R . Lập bảng đơn hình giải bài toán với phương án cực biên xuất phát Y0 đã biết. Bảng 3 có: Δj ≤∀=016j,. Phương án tối ưu của bài toán (M) là: Yopt = (0,2,4,0,1,0,0,0) , ϕopt = 16. ⇒ Phương án tối ưu của bài toán chính tắc là: Yopt = (0,2,4,0,1,0) , ϕmin = 16. ⇒ Phương án tối ưu của bài toán đối ngẫu là: Yopt = (0,2,4) , ϕmin = 16. Từ bảng 3, suy ra phương án tối ưu của bài toán gốc là: Xopt = (x1,x2,x3) = (-Δ4 ,- Δ5 ,- Δ6) = (4,0,2) và fmax = ϕmin = 16. BÀI TẬP CHƯƠNG 2 Giải bằng phương pháp đơn hình 1. f(x) = 2x1 + 3x3 → max ⎧ ⎪x 1 + x 2 + x 3 = 5 ⎪ x 1 + 3x 2 + x 4 = 9 ⎪ ⎨x1 − x 5 = 4 ⎪x + 2x + x = 8 ⎪ 1 2 6 ⎪ ___ ⎩⎪x j ≥ 0 (j = 1,6) ĐS: xopt = (3,2,0,0,1,1); fmax = 12 2. f(x) = 2x1 +x2 + 2x3 + 5x4 - 5x5 - 5x6 → max ⎧− 2x 1 + 3x 2 + x 3 + x 6 = 1 ⎪x + 4x + x + x = 4 ⎪ 1 2 3 5 ⎨- x − 3x + x + x = 4 ⎪ 1 2 3 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) ĐS: bài toán không có lời giải (f(x) → + ∞) 3. f(x) = 7x1 -21x2 + 14x3 → min 64
Chương II: Quy hoạch tuyến tính ⎧2x 1 − 3x 2 + x 3 ≥ 6 ⎪x + 7x − 3x ≤ 1 ⎪ 1 2 3 ⎨- 3x − x + x = −3 ⎪ 1 2 3 ⎪ ___ ⎩x j ≥ 0 (j = 1,3) ĐS: xopt = (0,1/7,0,45/7,0,20/7); fmin = -3 4. f(x) = x1 +2x2 - 2x4 - x5 - 3x6 → min ⎧x 1 + x 2 + x 4 - x 6 = 2 ⎪x + x + x = 12 ⎪ 4 5 6 ⎨4x + x + 2x + 3x = 9 ⎪ 1 3 4 6 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) 5. f(x) = 2x1 +x2 - x3 -x4 → max ⎧x 1 + x 2 + 2x 3 - x 4 ≤ 5 ⎪x + 2x + x ≤ 7 ⎪ 1 2 4 ⎨x + x + 2x ≤ 3 ⎪ 1 3 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,4) ĐS: xopt = (3,2,0,0); fmax = 8 6. f(x) = -5x1 +5x2 - 9x3 + 3x4 → min ⎧ ⎪− 3x 1 + 2x 3 − x 4 ≥ −13 ⎪ 4x 1 − 3x 3 + 8x 4 ≤ 25 ⎪ ⎨x 2 − 2x 3 + 2x 4 = 4 ⎪- 2x + x − 3x ≥ - 13 ⎪ 1 3 4 ⎪ ___ ⎩⎪x j ≥ 0 (j = 1,4) ĐS: bài toán không có lời giải (f(x) → -∞ ) 9 7. f(x) = 2x1 +7x2 - 5x3 + x → min 2 2 ⎧ ⎪x 1 − 2x 2 − x 3 + 3x 4 = 14 ⎪ x 2 − 4x 3 + x 4 ≤ 8 ⎪ ⎨x 2 − 2x 3 + 3x 4 = 4 ⎪- 2x + x − 3x ≥ - 20 ⎪ 1 3 4 ⎪ ___ ⎩⎪x j ≥ 0 (j = 1,4) ĐS: xopt = (0,0,34,16): fmin = -98 8. Cho bài toán quy hoạch tuyến tính 65
Chương II: Quy hoạch tuyến tính f(x) = 6x2 +4x4 + x5 + x6 → min ⎧x 1 − x 2 + 3 x 3 - 7x 4 - 2x 5 + x 6 = 14 ⎪− 4x + 6x − 9x + 21x + 5x - 2x = - 45 ⎪ 1 2 3 4 5 6 ⎨- 2x + 4x − x + 2x - x + x = - 15 ⎪ 1 3 3 4 5 6 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) Chứng tỏ x(0) = (12,0,0,0,7,16) là một phương án cực biên của bài toán. Lợi dụng x(0) giải bài toán bằng phương pháp đơn hình. Hướng dẫn và đáp số: Chứng tỏ x(0) thoả mãn chặt 6 ràng buộc trong hệ ràng buộc của bài toán và 6 véctơ tương ứng độc lập tuyến tính. Để giải bằng phương pháp đơn hình cần biến đổi matrận mở rộng của hệ phương trình trong hệ điều kiện để đưa các véctơ A1, A5, A6 về các véctơ đơn vị. Ta được bài toán tương đương. f(x) = 6x2 + 4x4 + x5 + x6 → min ⎧x 1 − x 2 + x 3 - 2x 4 = 14 ⎪4x + x + x = 16 ⎪ 2 4 6 ⎨2x − x + 3x + x = 7 ⎪ 2 3 4 5 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) Phương án cực biên x(0) = (12,0,0,0,7,16) ứng với cơ sở đơn vị: {A1, A5, A6, } = E3 Bài toán có vô số phương án tối ưu, tập các phương án tối ưu: (0) (1) (2) {xopt} = {λ0 x opt +λ1 x opt + λ 2 x opt } với 0 ≤ λ0, λ1, λ2≤ 1 và λ0 + λ1 λ2 = 1 (0) Trong đó: x opt = (50/3,0,0,7/3,41/3). và fmin = 23 9. Cho bài toán: f(x) = x1 +2x2 + x3 +3x4 - 2x5 → max ⎧3x 2 + 7x 2 − x 3 + 7x 4 - 2x 5 = 9 ⎪x + 8x + 9x + 7x = 25 ⎪ 2 4 5 ⎨x + x + x = 3 ⎪ 3 4 5 ⎪ ___ ⎩x j ≥ 0 (j = 1,5) Chứng tỏ x(0) = (3,0,0,2,1) là một phương án cực biên của bài toán. Giải bài toán với phương án cực biên xuất phát đó. (0) H.D: chỉ ra x thoả mãn chặt 5 ràng buộc độc lập tuyến tính. Giả tương tự bài tập 9. xopt = (5,1,3,0,0); fmax = 10. 10. f(x) = 2x1 +10x2 + 4x3 +8x4 + 8x5 + 3x6 → max 66
Chương II: Quy hoạch tuyến tính ⎧x 1 + x 5 = 5 ⎪ ⎪ 3 − x 1 + x 5 + 2x 6 = 11 ⎪ 5 ⎨3 6 ⎪ x1 + x 2 - x 6 = 4 ⎪5 5 ⎪ ___ ⎩⎪x j ≥ 0 (j = 1,6) Đ.S: xopt = (5,7,0,0,4,5); fmax = 127 11. f(x) = 5x1 + 4x2 + 5x3 + 2x4 + x5 + 3x6 → min ⎧2x1 + x 2 + 3x 3 + 4x 5 = 46 ⎪4x + 3x − x + 2x = 38 ⎪ 1 3 4 5 ⎨3x + x + x = 21 ⎪ 1 3 6 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) (1) (2) ĐS: x opt = (7,12,0,5,0,0); x opt = (5,0,0,9,0,6) (1) (2) { xopt} = { λ x opt + ( 1- λ) x opt ; 0 ≤ λ ≤ 1} và fmin = 79 12. f(x) = 2x1 + x2 - x3 - 4x4 → min ⎧2x 2 − 2 x 3 + 3x 4 ≤ 12 ⎪2x − 3x + x = 10 ⎪ 1 2 3 ⎨2x − 3x − 2x - 4x = 6 ⎪ 1 2 3 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,4) ĐS: xopt = (5,0,0,1); fmin = 6 13. f(x) = - x1 + x2 - 3x3 → max ⎧ ⎪- 2x1 + x 2 + 3x 3 = 2 ⎪ ⎨x 1 + x 2 + 2x 3 = 1 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,3) ĐS: bài toán không có phương án 14. f(x) = - x1 - 2x2 - x4+5 → max ⎧2x1 + 3x 2 − 4x 3 ≤ 5 ⎪− 3x − 5x + x ≤ -3 ⎪ 1 2 3 ⎨x + x − x = 6 ⎪ 1 2 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,4) ĐS: Bài toán có vô số phương án tối ưu. Tập phương án tối ưu có dạng: (1) (2) {xopt} = {λ x opt +(1− λ)x opt + 0 ≤ λ ≤ 1 } 67
Chương II: Quy hoạch tuyến tính (1) (2) Trong đó: x opt = (6,0,15,0); x opt ;= (6,0,7/4,0);fmax= 11 15. f(x) = 6x1 + x2 - 2x3 → min ⎧9x1 + x 2 + x 3 ≤ 18 ⎪15x + x − 2x = 20 ⎪ 1 2 3 ⎨3x + x = 3 ⎪ 1 3 ⎪ ___ ⎩x j ≥ 0 (j = 1,3) ĐS: x0pt = (1,5,0), fmin = 11 16. f(x) = x1 + 2x2 - 4x3 + 3x4 → min ⎧2x 1 − x 2 + x 3 + x 4 = 4 ⎪− 6x + 3x + 3x + 2x = 18 ⎪ 1 2 3 4 ⎨- x + x - x + x = 10 ⎪ 1 2 3 4 ⎪ ___ ⎩x j ≥ 0 (j = 1,4) ĐS: xopt = (2,6,0,6), fmin = 32 17. f(x) = x1 - 2x2 +x3 -8x4 + x5 + x6 → max ⎧x1 + 4 x 2 - x 3 − x 4 + x 6 = 12 ⎪x − 2x = 6 ⎪ 3 4 ⎨- 2x + 3x + 6 x − 2x - x = 12 ⎪ 2 3 4 5 6 ⎪ ___ ⎩x j ≥ 0 (j = 1,6) Nếu c4 = -11 thì có kết luận gì ? ĐS: trị số của f(x) không bị chặn trên tập phương án (f(x) → + ∞ ) Với c4 - 11 bài toán có phương án cực biên tối ưu: xopt = (11,0,6,0,3,0) và fmax = 20 18. f(x) = -2x1 - 3x2 +6x3 -4x4 → min ⎧ ⎪2x1 + 3 x 2 - x 3 + x 4 = 1 ⎪ ⎨4x 1 + 6x 2 + 3x 3 - 2x 4 = 3 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,4) ĐS: bài toán có tập phương án tối ưu: (1) (2) {xopt} = {λ x opt +(1− λ)x opt + 0 ≤ λ ≤ 1 } (1) (2) Trong đó: x opt = (0,2/5,1/5,0); x opt = (3/5,0,1/5,0); fmin = 0 19. f (x) = 3x1 + 4x2 - 6x4 → max 68
Chương II: Quy hoạch tuyến tính ⎧ ⎪x1 + 4x 2 - 2x 3 + x 4 = 10 ⎪ 2x 2 − x 3 + x 5 ≤ - 2 ⎪ ⎨− 7x 2 + x 2 + 4x 3 ≤ 22 ⎪4x + 2x − 2x − 4x = 20 ⎪ 2 3 4 5 ⎪ ___ ⎩⎪x j ≥ 0 (j = 1,5) ĐS: Bài toán không có phương án tối ưu(f (x) → + ∞). 20. f (x) = 4x1 - 2x2 + x3 - x4 → min ⎧2x1 + 2x 2 + x 4 = 10 ⎪ 3 ⎪x + 5x + 3x + x ≤ 32 ⎪ 1 2 3 4 ⎨ 2 ⎪2x 1 − 2x 2 + 2x 3 + x 4 = 16 ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,4) ĐS: xopt = (8,3,0,6); fmin = 20 21. f (x) = x1 - 2x2 - 2x3 + x6 → min ⎧ ⎪4x 1 + 2x 2 − x 4 + x 5 + 2x 6 = 5 ⎪ x 2 − 3x 3 + 2x 4 - x 6 ≤ 10 ⎪ ⎨3x 1 − x 2 − 5x 3 + 3x 4 - 4x 6 ≤ 3 ⎪x + x + x − 2x + x = 4 ⎪ 1 2 3 4 5 ⎪ ___ ⎩⎪x j ≥ 0 (j = 1,6) ĐS: Trị số: f (x) → - ∞ trên tập phương án. Bài toán không có phương án tối ưu Giải và biện luận các bài toán sau đây theo tham số m 22. . Cho quy hoạch tuyến tính: f (x) = - 2x1 + x2 → max ⎧ ⎪- x1 + ax 2 ≤ 1 ⎪ ⎨x 1 − a(3 - x 2 ) = 10 - 3a ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,2);a − tham sè ĐS: Nếu a ≤ 0 bài toán không có phương án tối ưu (f (x) → + ∞ ) 11 Nếu 0 < a < 1/3; xopt = (9/2; 11/2a); fmax = − 9 2a 1 Nếu a ≥ ; xopt = (10,0); fmax = - 20 3 23. f (x) = 3x1 + 4x2 → min 69
Chương II: Quy hoạch tuyến tính ⎧ ⎪ax1 − 2x 2 ≥ 2 ⎪ ⎨x 1 + a(x 2 - 2) + x 3 = 2 (2 - a) ⎪ ___ ⎪ ⎩x j ≥ 0 (j = 1,3);a − tham sè 1 ĐS: Nếu a 1; xopt = ( , 0,0,); fmin = 2a 2a 25. f (x) = 4x1 + 2x2 → max ⎧ax1 + x 2 ≤ 6 ⎪ax ≤ 3 ⎪ 1 ⎨- 2ax − x ≥ - 10 ⎪ 1 2 ⎪ ___ ⎩x j ≥ 0 (j = 1,2);a − tham sè ĐS: Nếu a ≤ 0 bài toán vô nghiệm 12 Nếu 0 2; xopt = (0,6); fmax = 12 26. f (x) = x1 + x2 + 2x3 - 3x4 → min ⎧x1 + x 2 + ax 3 = 2 ⎪x + 2ax + x = 3 ⎪ 1 3 4 ⎨4x + ax = 1 ⎪ 1 3 ⎪ ___ ⎩x j ≥ 0 (j = 1,4);a − tham sè − 4 1 4 11 9 ĐS: Nếu a < ; xopt = ( , ,0, );f − . 7 4 7 4 min 2 3 27. f (x) = ax1 + x2 + x3 + 3x4 - x5 → min 2 70