Chương 3: Lý thuyết qui hoạch tuyến tính

Tham khảo tài liệu chương 3: lý thuyết qui hoạch tuyến tính, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 3: Lý thuyết qui hoạch tuyến tính ́ thuyêtLy ́ qui ̣ hoach tuyên ́ ́ tinh Chương III : LÝ THUYẾT QUI HOẠCH TUYẾN TÍNH§1 Bài toán Qui hoạch tuyến tính (QHTT) dạng cơ bản1.1 Dạng toán họcBài toán : Tìm các số thực xj, j = 1,2,…,n, làm cực tiểu hàm số n Z = ∑ c jx j j =1 (1.1) thỏa mãn các ràng buộc n ∑ a ij x j ≥ bi , i = 1, 2,..., m (1.2) j= & x j ≥ 0, j = 1, 2....., n (1.3) Trong đó cj, aij, bi, i = 1,2, ……,m ; j = 1,2,….,n là những số thực cho trước. Bài toán (1.1) – (1.3) gọi là bài toán QHTT dạng cơ bản. Người ta cóthể phát biểu bài toán (1.1) – (1.3) dưới dạng ma trận như sau : Tìm vectơ x* = (x*1, x*2,…, x*n) thoả mãn : Z* = c, x * = min c, x (1.4) x∈X Với X = { x ∈ R n / Ax ≥ b, x ≥ 0} (1.5) Trong đó A là ma trận thực cấp (mxn) ; c là vectơ n chiều, b –vectơm chiều cho trước. Ký hiệu : Ai., i = 1,2,…, m là các n-vectơ hàng của A. Khi đó bài toánQHTT (1.4)-(1.5) còn có thể viết thành : Tìm x* thoả mãn Z* = c, x * = min c, x (1.4) x∈X { X = x ∈ R n / A i; , x ≥ bi ,i = 1, 2,..., m; x ≥ 0} (1.6)Các ký hiệu và khái niệm ở bài toán (1.1) – (1.3) :• Hàm Z trong (1.1) gọi là hàm mục tiêu, vì nó biểu diễn mục tiêu của việc giải bài toán11 Trong thực tế có thể đòi hỏi mục tiêu là tìm cực đại. Tuy nhiên dễ dàng chuyễn đổi từ mụctiêu tìm cực đại về mục tiêu tìm cực tiểu bằng cách đặt Z’ = -Z.Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 55 ́ ́ ̣ ̣ ́ thuyêtLy ́ qui ̣ hoach tuyên ́ ́ tinh• Hệ (1.2) gọi là hệ các ràng buộc, vì nó biểu diễn các ràng buộc của bài toán. Vì vậy, các vectơ hàng A i., i =1,2,…,m, được gọi là các vectơ ràng buộc.• Hệ (1.3) cũng là hệ ràng buộc. Nhưng do có cấu trúc đặc biệt và hạn chế về dấu của các biến số nên gọi là hệ các hạn chế.• Một vectơ x thoả mãn đồng thời hệ (1.2) và (1.3) gọi là một phương án hoặc là một lời giải chấp nhận được của bài toán QHTT2• Tập hợp X gồm các phương án (hoặc lời giải chấp nhận được) gọi là tập chấp nhận được.• Một phương án x* ∈ X tại đó hàm mục tiêu (1.1) đạt giá trị nhỏ nhất (thỏa mãn (1.1) hoặc (1.4)) gọi là một phương án tối ưu. Lý thuyết Qui hoạch tuyến tính bao gồm việc nghiên cứu để trả lờihai câu hỏi chủ yếu xoay quanh việc giải quyết bài toán QHTT : 1) Tồn tại hay không một phương án tối ưu như vậy ? và 2) Nếu tồn tại một phương án tối ưu thì làm cách nào để tìm ra phưpơng án tối ưu đó. Thông thường đối với một bài toán đặt ra từ thực tế sản xuất kinhdoanh có một số rất lớn các phương án giải quyết (thực hiện). Số phươngán này có thể lớn đến nỗi mà trong khuôn khổ những phương tiện và khảnăng cho phép người ta không thể tìm ra được phương án tối ưu (cho giátrị hàm mục tiêu nhỏ nhất hoặc lớn nhất). Vì vậy, cần phải tìm ra cácđiều kiện để nhận biết một phương án là phương án tối ưu và phát triễncác phương pháp để chỉ cần xét một số (đủ nhỏ) các phương án người tacó thể tìm ra phương án tối ưu (nếu như có phương án như vậy). Vì bài toán QHTT là trường hợp đặt biệt của bài toán Qui hoạch lồinên các điều kiện để nhận biết một phương án là tối ưu đã được nêu ởphần cuối chương II. Sự tồn tại một phương án tối ưu của bài toán quihoạch lồi được đảm bảo bằng sự tồn điểm yên ngựa của hàm Lagrangetương ứng và lời giải của hệ các điều kiện Kuhn-Tucker. Tuy nhiên, cũngcó trường hợp bài toán qui hoạch lồi có lời giải tối ưu nhưng hàmLagrange tương ứng không có điểm yên ngựa. Do cấu trúc đặt biệt của bài toán QHTT người ta có thể đưa ra cácđiều kiện tồn tại phương án tối ưu mà không cần phải dựa vào sự tồn tạiđiễm yên ngựa, tức là không cần phải tiến hành giải quyết hệ thống bấtđẵng thức Kuhn-Tucker. Đây chính là nội dung của lý thuyết qui hoạchtuyến tính.2 Từ « phương án » được sử dụng vì phương pháp qui hoạch tuyến tính thường được áp dụngđể giải quyết các bài toán xuất phát từ thực tế sản xuất, kinh doanh. Ở đó người ta thườngkhảo sát một số các phương án sản xuất có thể để tìm ra phương án sản xuất thỏa mãn mộtcách tốt nhất mục tiêu đã đề ra.Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 56 ́ ́ ̣ ̣Lý t huyế t qui hoạ c h t uyế n t í nh1.2 Các tính chất của bài toán QHTT Dựa vào cấu trúc đơn giản của bài toán QHTT người ta có thể chứngminh các tính chất cơ bản như sau :Tính chất 1 : Nếu tập chấp nhận được của bài toán QHTT là không rỗng thì đó là một tập lồi đa diện và có ít nhất một điểm cực biên ; đồng thời số điểm cực biên là hữu hạn.Chứng minh : Định lý này được suy ra trực tiếp từ định lý 5, chương I chotrường hợp bài toán Qui hoạch lồi với ràng buộc tuyến tính. Trong đó hệràng buộc và hạn chế (1.2) và (1.3) chương nay chỉ là trường hợp đặt biệt ̀của hệ (5.1)(5.2) chương I.ªTính chất 2 : Nếu tập chấp nhận được X khác trống và hàm mục tiêu (1.1) bị chặn dưới trên tập X thì tồn tại phương án cho giá trị hàm mục tiêu nhỏ nhất (phương án tối ưu); tức là bài toán QHTT giải được.Chứng minh : Hệ ràng buộc xác định tập X rõ ràng có hạng bằng n vì cóchứa n vectơ đơn vị ej ứng với e j , x ≥ 0 j = 1,2,…,n . Vì vậy có ...