Qui hoạch tuyến tính và ứng dụng trong kinh tế

Tài liệu nêu lên lý thuyết và phương pháp giải các bài toán tối ưu tuyến tính chứa tham số. Tài liệu đã được in trong cuốn "Qui hoạch tuyến tính và ứng dụng trong kinh tế" Tác giả Lê Văn Phi
Nội dung trích xuất từ tài liệu:
Qui hoạch tuyến tính và ứng dụng trong kinh tếLyù thuyeátquihoaïchtuyeán tính C HƯƠNG VI: TỐI ƯU TUYẾN TÍNH CHỨA THAM SỐ Trong thực tế, ở một số mô hình bài toán tối tuyến tính, các hệ số ban đầu như a ij, bi,cj, i = 1,2,…,m; j = 1,2,…,n, có thể không được cho biết một cách chính xác hoặc giá trịcủa chúng thường phụ thuộc vào sự thay đổi của một hay nhiều tham số như thời gian,thời tiết, chất lượng nguyên liệu, nhiên liệu v.v… Nếu phải tiến hành việc giải bài toánứng với từng giá trị khác nhau của các tham số ấy thì khối lượng và do đóchi phí tính toánsẽ rất lớn và, do vậy, việc giải bài toán TƯTT tìm phương án tối ưu sẽ mất hết ý nghĩakinh tế. Để khắc phục khó khăn này người ta đã phát triển một phương pháp gọi là phươngpháp giải bài toán TƯTT chứa tham. Phương pháp này xuất phát từ việc giải bài toánTƯTT đối với một giá trị xác định của tham số cần khảo sát bằng phương pháp đơn hìnhthông thường, Sau đó sẽ tìm khoảng biến thiên của tham số để cho phương án hiện cóvẫn còn là phương án tối ưu của bài toán mới hoặc sẽ trực tiếp tìm ra phương án tối ưumới dựa trên phương án tối ưu hiện có. Bằng cách ấy người ta sẽ tìm ra phương án tối ưucủa các bài toán TƯTT ứng với từng giá trị khác nhau của tham số cần khảo sát. Người ta phân biệt thành bài toán qui hoạch tuyến tính chứa một tham số ở hệ số hàmmục tiêu (cj), ở vế phải (bi), ở hệ số các ràng buộc (aij), chứa một tham số ở cả hàm mụctiêu và ở vế phải hoặc chứa hai tham số cùng biến thiên độc lập v.v….Trong phạm vi giáotrình này chúng tôi chỉ xét hai loại bài toán đầu tiên. Tương tự như ở các chương trước chúng tôi không đi sâu vào phân tích cơ sở lý thuyếtcủa phương pháp giải, không trình bày kỹ phần chứng minh các định lý mà chú trọng trìnhbày thuật toán giải và các ý nghĩa kinh tế cũng như thực tiễn. Để nghiên cứu thêm phần cơsở lý thuyết, tìm hiểu thêm các phương pháp giải bài toán TƯTT chứa tham số khác, bạnđọc có thể tham khảo thêm ở [ ].2.1 Phương pháp đơn hình giải bài toán TƯTT chứa tham số ở hàm mục tiêu2.1.1. Cơ sở lý thuyết và thuật toán Ta xét bài toán qui hoạch sau đây: Tìm giá trị của x1, x2,…, xn làm cực tiểu hàm mục tiêu nZ( x ) = ∑ (c j + d j t ) x j (2.1) j =1 ứng với các ràng buộc n ∑ aij xj = bi , i = 1,2,..., m (2.2) j=1 xj ≥ 0, j = 1,2,..., n ( 2.3) u≤ t≤ v (2.4)Trong đó cj, dj, aij, bi, i = 1,2,…,m; j = 1,2,…,n và u, v là các số cho trước; t là tham số; u cóthể là -∞, v có thể là + ∞; tức tham số t có thể không bị chặn dưới hoặc không bị chặntrên. Đễ thấy rằng ứng với mỗi giá trị cố định của tham số t = t 0∈[u,v] bài toán tối ưuchứatham số (2.1) – (3.3) trở thành bài toán TƯTT bình thường. Vì vậy, người ta gọi bàitoán (2.1) - (2.4) là bài toán TƯTT chứa tham số (hay, ngắn gọn, bài toán tối ưu tham số).Ngoài ra, để cho bài toán tham số có ý nghĩa thì ngoài các giả thiết cần có của bài toánLêVănPhi 87Lyù t huyeát qui hoaï ch t uyeán tí nhTƯTT thông thường người ta còn giả thiết rằng ít nhất một hệ số d j, 1 ≤ j ≤ n, là kháckhông, bởi vì, nếu dj = 0, ∀j, thì bài toán (2.1)-(2.4) trở thành bài toán TƯTT thông thường. Nhằm đơn giản cách trình bày bắt đầu từ đây chúng ta ký hiệu bài toán (2.1)-(2.4) làP(0, t). Ta nhận thấy rằng các aij và bi, i = 1,2,…,m; j = 1,2,…, n, đều không phụ thuộc vàotham số t nên tập các phương án chấp nhận được X là như nhau ứng với mọi giá trị của t.Vì vậy, nếu ứng với một giá trị nào đó của tham số t mà miền chấp nhận được rỗng thìhiển nhiên miền chấp nhận được của bài toán (2.1) – (2.4) cũng là rỗng với mọi giá trị củat. Trong trường hợp này bài toán tối ưu tuyến tính tham số (2.1) – (2.4) không giải đượcvới mọi giá trị của t, đặc biệt với t∈[u,v]. Phương pháp giải bài toán tối ưu tham số (2.1) - (2.4) bắt đầu bằng việc cho tham số tnhận giá trị t0 nào đó thuộc [u,v] (nếu u là hữu hạn, ta đặt t = u) 26. Sau đó áp dụng phươngpháp đơn hình (hoặc đơn hình mở rộng) giải bài toán P(0,t0). Để dễ dàng cho việc thựchiện phương pháp giải về sau các hệ số đặc trưng am+1,j được tính tách riêng theo các hệsố cj và dj tương ứng dưới dạng: am+1,j = h j + gjt ,j = 0,1,2,…,n (trong đó hj được tính theo cjvà gj theo dj). Có 3 trường hợp xảy ra:• Trường hợp 1: Bài toán P(0,t0) không có lời giải chấp nhận được.• Trường hợp 2: Bài toán P(0,t0) không có lời giải tối ưu; tức là hàm mục tiêu (2.1) ứng với t = t0 không bị chặn dưới trên tập hợp chấp nhận được.• Trường hợp 3: Bài toán P(0,t0) có lời giải cơ sở tối ưu là x0.Ta lần lượt xét các trường hợp 1, 2 và 3.1) Xét trường hợp 1: Vì như nhận xét ở ...