Mở đầu Như đã nói, để tìm hiểu ứng dụng của hệ bất phương trình bậc nhất hai ẩn, chúng tôi giới hạn phạm vi toán học để nghiên cứu là Quy hoạch tuyến tính (QHTT). Sự lựa chọn này có hai lý do. Thứ nhất, đây là một ngành toán học ứng dụng, nên trong đó ta có thể gặp những vấn đề ngoài toán học được giải quyết bằng công cụ toán học. Điều này liên quan trực tiếp đến đề tài nghiên cứu của luận văn.
Thứ hai, trong QHTT ta gặp nhiều bài toán có sự can thiệp của phương trình, bất phương trình bậc nhất hai ẩn. Những giáo trình đại học được chúng tôi sử dụng cho việc nghiên cứu này bao gồm: - Tối ưu hóa tuyến tính, Nguyễn Thành Cả, 2007, Nxb Thống kê. - Lý thuyết – Bài tập – Bài giải quy hoạch tuyến tính tối ưu hóa, Lê Khánh Luận, 2009, Nxb Đại học quốc gia TP. Hồ Chí Minh.
- Quy hoạch tuyến tính và ứng dụng trong kinh tế, Lê Văn Phi, 2004, Nxb Giáo dục. - Tối ưu hóa- Giáo trình cho ngành tin học và công nghệ thông tin, Nguyễn Hải Thanh, 2006, Nxb Bách khoa- Hà Nội. - Quy hoạch tuyến tính, Đặng Hấn, 1995, Nxb Đại học quốc gia TP. Hồ Chí Minh.
Khi nghiên cứu các tài liệu này, chúng tôi sẽ cố gắng làm rõ : - một số kiểu nhiệm vụ tiêu biểu (ngoài toán học) mà lời giải đòi hỏi sự can thiệp của các hệ phương trình, bất phương trình bậc nhất - những kỹ thuật giải có thể dùng cho hệ bất phương trình bậc nhất 1.1 Vài kiểu nhiệm vụ : Trong phần này, chúng tôi sẽ trình bày một số các bài toán thực tế tìm thấy trong cuốn sách “Tối ưu hóa tuyến tính” của tác giả Nguyễn Thành Cả. Kiểu nhiệm vụ “lập kế hoạch sản xuất” Để người đọc dễ tiếp cận, chúng tôi không nêu các kiểu nhiệm vụ ở dạng tổng quát mà chỉ đưa ra mỗi ví dụ cho một trường hợp. Điều này cũng thuận lợi hơn cho chúng tôi khi tham chiếu để phân tích CT, SGK dành cho bậc phổ thông, nơi mà các bài toán khái quát phức tạp không có mặt. Ví dụ: Một xí nghiệp sản xuất giấy hiện có số lượng Bột gỗ và Chất hồ keo tương ứng là 5.
Các yếu tố sản xuất khác có số lượng lớn. Xí nghiệp có thể sản xuất ra 3 loại giấy A, B, C. Biết mức tiêu hao các loại nguyên liệu để sản xuất ra 1 tấn giấy thành phẩm cho trong bảng sau (Bảng định mức kinh tế- kỹ thuật): Nguyên liệu Sản phẩm A B C Bột gỗ (m3) 1,5 1,8 1,6 Chất hồ keo (kg) 2 3 2,4 Ngoài ra, giả sử rằng sản phẩm sản xuất ra đều có thể tiêu thụ được hết với lợi nhuận khi sản xuất 1 tấn giấy A, B, C tương ứng là 2,7: 3,6: 3 (triệu đồng). Yêu cầu lập kế hoạch sản xuất tối ưu.
Vấn đề này dẫn đến bài toán : tìm x j , j = 1, 2, 3 sao cho : f = 2,7x 1 + 3,6x 2 + 3x 3 → max với hệ ràng buộc : 1, 5x + 1, 8x + 1, 6x ≤ 5.Kiểu nhiệm vụ “xác định khẩu phần thức ăn” Ví dụ: Giả sử để sinh sống trong một ngày đêm, mỗi người cần ít nhất 70g Protit, 30g Lipit và 420g Gluxit. Hàm lượng các chất trên có trong 1g thức ăn A và B như sau: 9 Chất dinh dưỡng Thức ăn A B Protit (g) 0,1 0,2 Lipit (g) 0,1 0,1 Gluxit (g) 0,7 0,6 Ngoài ra, biết giá của mỗi gam thức ăn A và B tương ứng là 40đ và 60đ. Hãy xác định khối lượng thức ăn tối ưu cần mua. Để giải quyết kiểu nhiệm vụ trên người ta có thể đưa về giải bài toán sau: Tìm x 1 , x 2 sao cho : f = 40x 1 + 60x 2 → min Với hệ ràng buộc : 0,1x1 + 0, 2x 2 ≥ 70 0,1x1 + 0,1x 2 ≥ 30 0, 7x1 + 0, 6x 2 ≥ 420 x ≥ 0, x ≥ 0 1 2 1.
Kiểu nhiệm vụ “phân bổ vốn đầu tư” Ví dụ: Một nhà đầu tư có 2 tỉ đồng muốn đầu tư vào 4 lĩnh vực: chứng khoán, công trái, gửi tiết kiệm và bất động sản. Biết lãi suất hàng năm của lĩnh vực đầu tư như sau: Lĩnh vực đầu tư Lãi suất hàng năm Chứng khoán 20% Công trái 12% Gửi tiết kiệm 10% Bất động sản 15% Ngoài ra, để giảm thiểu mức rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 40% tổng vốn đầu tư, còn đầu tư vào công trái và gửi tiết kiệm phải ít nhất là 25% tổng vốn đầu tư và tiền gởi tiết kiệm phải ít nhất là 100 triệu đồng. 10 Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho tổng thu nhập hàng năm là lớn nhất. Vấn đề này dẫn đến bài toán : Tìm x j , j = 1, 4 sao cho : f = 0,2x 1 + 0,12x 2 + 0,1x 3 + 0,15x 4 → max Với hệ ràng buộc : 1.
Kiểu nhiệm vụ “lập tiến độ sản xuất ” Ví dụ: Một nhà máy sản xuất một loại sản phẩm có khối lượng hợp đồng đặt hàng trong 3 tháng liên tiếp và chi phí sản xuất của mỗi đơn vị sản phẩm trong từng tháng cho trong bảng sau: Dữ liệu Tháng 1 2 3 “Khối lượng hợp đồng đặt hàng (đv) 95 90 120 Chi phí sản xuất trong thời gian thường (1.000 đ/đv) 30 32 34 Chi phí sản xuất trong thời gian phụ trội (1. Chi phí lưu kho cho 1 đv sản phẩm không bán được là 2. Nhà máy không có đơn vị hàng nào vào đầu tháng 1 và mong muốn có ít nhất 5 đơn vị hàng vào cuối tháng 3. Ngoài ra, giả sử sản phẩm sản xuất ra đều được cung cấp ngay cho người đặt hàng cho đến lúc đủ khối lượng hợp đồng.
Vấn đề này dẫn đến bài toán : Tìm x j , yj , z j , j = 1, 3 sao cho : f = 30x 1 + 32x 2 + 34x 3 +34y1 + 36y2 + 38y3 + 2z 1 + 2z 2 + 2z 3 → min Với hệ ràng buộc : 11 x1 + y1 − z1 = 95 x 2 + y 2 + z1 − z 2 = 90 x + y + z − z = 120 3 3 2 3 z3 ≥ 5 0 ≤ x j ≤ 100, j = 1, 3 0 ≤ y j ≤ 15, j = 1, 3 z j ≥ 0, j = 1, 3 1. Bài toán tối ưu hóa tổng quát Những kiểu nhiệm vụ nêu trên người ta đều có thể chuyển thành bài toán tìm cực trị của một hàm số (gọi là hàm mục tiêu) với có hay không có hệ ràng buộc đối với các biến số. Trong trường hợp có hệ ràng buộc thì bài toán tối ưu hóa được gọi là bài toán quy hoạch toán học. Tùy theo dạng toán học của hàm mục tiêu và các ràng buộc là tuyến tính hay phi tuyến tính mà ta có QHTT hay quy hoạch phi tuyến tính (gọi tắt là quy hoạch phi tuyến).
Trong nhiều trường hợp, bài toán quy hoạch phi tuyến tính có thể chuyển về tuyến tính. Bài toán QHTT dạng tổng quát : Một bài toán QHTT là một mô hình toán tìm cực tiểu (min) hoặc cực đại (max) của hàm mục tiêu tuyến tính với các ràng buộc là bất đẳng thức và đẳng thức tuyến tính. Dạng tổng quát của một bài toán QHTT quy ước viết như sau: Tìm x j , j = 1, 2, …, n sao cho: n =f ∑ c x → min (max) j=1 j j (1) với hệ ràng buộc: ≤ n ∑ a ij= xj = bi , i 1, 2,., n (3) tuy y (1) được gọi là hàm mục tiêu 12 (2) được gọi là các ràng buộc chung. (3) được gọi là các ràng buộc dấu (của biến) A = (a ij ) m×n : Ma trận hệ số ràng buộc.
B = (b 1 , b 2 ,…, b m ): Ma trận hệ số tự do. X = (x 1 , x 2 ,…, x n )T : Ma trận ẩn. C = (c 1 , c 2 , …, c n )T : Ma trận chi phí. Các ẩn ứng với các véc tơ đơn vị trong ma trận ràng buộc A được gọi là các ẩn cơ sở.
Ẩn cơ sở ứng với các vectơ cột thứ i được gọi là ẩn cơ sở thứ i. Các ẩn còn lại gọi là các ẩn không cơ sở (ẩn tự do). Véc tơ x = (x 1 , x 2 , …, x n )T được gọi là phương án (PA) hay lời giải chấp nhận được của bài toán QHTT nếu nó thỏa mãn hệ ràng buộc của bài toán. Một PA mà các ẩn không cơ sở đều bằng 0 được gọi là PA cơ bản.
Một PA cơ bản có đủ m thành phần dương gọi là PA cơ bản không suy biến. Ít hơn m thành phần dương gọi là suy biến. Phương án x* = (x* 1 , x 2 *,…, x n *)T được gọi là phương án tối ưu (PATU)của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt nhất. Giải bài toán QHTT tức là tìm PATU của nó (nếu có).
Hai bài toán QHTT được gọi là tương đương với nhau nếu chúng có chung tập hợp các PATU. Dạng chính tắc Bài toán QHTT dạng chính tắc là bài toán QHTT có tất cả các ràng buộc chung đều ở dạng đẳng thức và tất cả các biến đều không âm. Dạng chuẩn Bài toán QHTT dạng chuẩn là bài toán QHTT dạng chính tắc thỏa mãn hai điều kiện: + Các hằng số ở vế phải của các ràng buộc chung đều không âm + Mỗi ràng buộc chung có biến cơ bản tương ứng. Mọi bài toán QHTT dạng tổng quát đều có thể chuyển về dạng chính tắc nhờ vào cách sử dụng các ẩn phụ.
Ẩn phụ được thêm vào theo nguyên tắc sau: 13 n Nếu điều kiện ràng buộc có dạng ∑ a ij x j ≥ bi thì ta cộng thêm vào vế trái một j=1 ẩn phụ không âm x n+i ≥ 0 với hệ số -1 để biến thành phương trình n ∑a x − x j=1 ij j n +i = bi n Nếu điều kiện ràng buộc có dạng ∑ a ij x j ≤ bi thì ta cộng thêm vào vế trái một j=1 ẩn phụ không âm x n+i ≥ 0 với hệ số 1 để biến thành phương trình n ∑a x + x j=1 ij j n +i = bi .