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

Chia sẻ: Lê Văn Phi | Ngày: | Loại File: DOC | Số trang:22

Thêm vào BST

Báo xấu

517
lượt xem 225
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 3: Lý thuyết qui hoạch tuyến tính

́ thuyêt Ly ́ 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ản 1.1 Dạng toán học Bà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án QHTT (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án1 1 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ục tiê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ồ Chí Minh 55 ́ ́ ̣ ̣
́ thuyêt Ly ́ 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ời hai 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 kinh doanh 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ễn các phương pháp để chỉ cần xét một số (đủ nhỏ) các phương án người ta có 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ồi nê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 qui hoạch lồi được đảm bảo bằng sự tồn điểm yên ngựa của hàm Lagrange tương ứng và lời giải của hệ các điều kiện Kuhn-Tucker. Tuy nhiên, cũng có trường hợp bài toán qui hoạch lồi có lời giải tối ưu nhưng hàm Lagrange 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ạch tuyế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ường khả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ột cá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ồ Chí Minh 56 ́ ́ ̣ ̣
Lý t huyế t qui hoạ c h t uyế n t í nh 1.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ứng minh 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 cho trườ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ó thể áp dụng định lý 5.6 chương I (định lý biểu diễn mở rộng cho tập lồi đa diện). p theo đó, nếu x∈X thì sẽ tồi tại xi∈ X , λ i ≥ 0, i = 1,2,…,p, với ∑ λ i = 1 và 00 i =1 các β j ≥ 0, lj, j = 1, 2,…,q , để cho 3 p q x = ∑ λi x i + ∑ β jl j (1.7) i =1 j =1 Trong đó lj, j = 1, 2,…,q, là vectơ định hướng của các cạnh không bị chặn của X. Theo giả thiết hàm mục tiêu Z = c, x bị chặn trên X , tức là tồn tại µ ∈ R, để cho ∀ x∈X : Z = c, x ≥ µ (1.8) Từ (1.7) và (1.8) kéo theo p q ∀ x∈X : µ ≤ c, x = ∑ λ i c, x i + ∑ β j c,l j i =1 j =1 (1.9) Bạn đọc dễ dàng suy ra rằng bất đẵng thức này chỉ đúng với mọi phần tử trong X, nếu c,l j ≥ 0, ∀j = 1, 2,...,q . Do đó 3 Không giảm tổng quát, có thể coi p là toàn bộ các điểm cực biên, q là toàn bộ các cạnh không bị chặn của X. Theo tính chất 1 thì p, q là hữu hạn. Nếu có điểm cực biên hoặc cạnh không bị chặn nào đó không xuất hiện trong dạng biểu diễn (1.7) thì ta xem như chúng xuất hiện với hệ số λ i hoặc β j tương ứng bằng 0. Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 57 ́ ́ ̣ ̣
Lý t huyết qui hoạc h t uyến tí nh p ∀ x∈X : c, x ≥ ∑ λ i c, x i (1.10) i =1 Chọn x0 với c, x 0 = min c, x i (1.11) i =1,2,...,p Điểm x ∈X như vậy phải tồn tại vì p hữu hạn. Khi đó theo (1.10) thì 0 ∀ x∈X : c, x ≥ c, x 0 (1.12) Chúng tỏ x0 là điểm cực tiểu của Z trên X và do đó là lời giải của bài toán QHTT (1.1)-(1.3).ª Tính chất 3 : Nếu bài toán QHTT (1.1)-(1.3) giải được thì sẽ tồn tại ít nhất một điểm cực biên của X để cho giá trị tối ưu Zmin đạt được tại đó. Tức là tồn tại x0 ∈X để cho : Zmin = c, x = min c, x i 0 x∈X Chứng minh : Suy ra từ phần chứng minh ở tính chất 2, công thức (1.11) và (1.12). Các tính chất này cho phép giải bài toán QHTT bằng cách thiết lập tất cả các điểm cực biên của X (nếu X ≠∅ ) và so sánh giá trị hàm mục tiêu Z tại các điểm cực biên ấy. Từ đó tìm ra lời giải tối ưu hoặc nhận biết được rằng bài toán không giải được. Tuy nhiên hầu hết các bài toán thực tế thường chứa rất nhiều biến số và rất nhiều ràng buộc. Do đó một phương pháp như vậy hoàn toàn không có hiệu quả do tốn kém về thời gian và chi phí và cũng không có ý nghĩa. Lý thuyết QHTT, ngoài việc nghiên cứu và tìm ra các tính chất như trên, còn phát triễn các phương pháp cho phép xác định một số rất ít các điểm cực biên của tập X để tìm ra điểm cực biên tối ưu. Chương sau sẽ trình bày các phương pháp số để giải bài toán QHTT ở nhiều dạng khác nhau. Phần tiếp theo đây sẽ mô tả phương pháp đồ thị (hay còn gọi là phương pháp hình học hoặc ý nghĩa hình học) để giải bài toán trên. Do phương pháp này chỉ áp dụng cho trường hợp 2 chiều (hai biến) hoặc tối đa là 3 chiều (ba biến) nên không có ý nghĩa thực tiễn. Dù vậy, việc nghiên cưú phương pháp cũng giúp cho người học hiểu rõ thêm các tính chất của bài toán QHTT và nguyên lý thực hiên Phương pháp đơn hình ở chương sau. §2 Phương pháp hinh hoc giải bài toán QHTT (1.1)-(1.3) ̀ ̣ Mặt dù phương pháp hinh hoc không cò ý nghĩa nhiều trong việc giải ̀ ̣ các bài toán QHTT trong thực tế vì các bài toán này thường có rất nhiều Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 58 ́ ́ ̣ ̣
Lý thuyết qui hoạch tuyến tính ràng buộc và rất nhiêu các biến số. Tuy nhiên việc trình bày phương pháp hinh hoc cũng sẽ minh hoa được các tính chất của bài toán QHTT nêu trên. ̀ ̣ ̣ Phương pháp này chủ yếu bao gồm hai bước cơ bản : 1) Thiết lập miền chấp nhận được X 2) Tìm giá trị cực tiểu (hoặc cực đại) của Z trên miền đó. 2.1 Thiết lập miền chấp nhận được X Trên mặt phẳng tọa độ x20x1, mỗi ràng buộc ở (1.2) có thể được viết thành : a1x1 + a2x2 ≥ b 4) (2.1) Phần mặt phẳng giới hạn bởi điều kiện (2.1), chúng ta quen gọi là nửa không gian (hoặc nửa mặt phẳng), được giới hạn bởi đường thẳng a1x1 + a2x2 = b (2.2) Vì vậy, để xác định phần mặt phẳng giới hạn bởi (2.1) trước hết cần vẽ đường thẳng (2.2). Ta phân biệt 2 trường hợp : α) b = 0. Đường thẳng (2.2) trở thành a1x1 + a2x2 = 0 (2.3) Ở trường hợp này (2.2) là đường thẳng qua gốc tọa độ. Chỉ cần xác định thêm một điểm nữa thì có thể vẽ được đường thẳng đó. Giả sử đã vẽ xong đường thẳng (2.2). Dường thẳng này qua gốc tọa độ và chia mặt phẳng thành hai nửa mặt phẳng. Để xác định xem nửa mặt phẳng nào ứng với ràng buộc (2.1) người ta chỉ cần chọn một điểm x*= (x1*,x2*) bất kỳ không nằm trên đường thẳng (2.3). Sau đó thay x 1 = x1*, x2 = x2* vào (2.3). Nếu a1x1* + a2x2* > 0 thì nửa mặt phẳng tương ứng là nửa mặt phẳng chứa gốc 0 = (0, 0). Trong trường hợp ngược lại thì nửa mặt phẳng phải tìm là nửa mặt phẳng không chứa gốc tọa độ β ) b ≠ 0. Khi ấy phương trình đường thẳng (2.2) trở thành a1 a x1 + 2 x 2 = 1 (2.4) b b Dễ thấy rằng, đường thẳng (2.4) cắt trục Ox2 tại điểm C = (0, b/a2), nếu a2 ≠ 0 hoặc sẽ song song với Ox2 ở trường hợp ngược lại. Đường thẳng này cũng cắt 0x1 tại điểm D = (b/a1, 0), nếu a1≠ 0 hoặc song song với 0x1. Sau khi xác định được hai điểm C và D. Nối hai điểm đó ta sẽ có được đường thẳng (2.4). Việc xác định phần mặt phẳng ứng với (2.1) được tiến hành đơn giản hơn. Cụ thể như sau : a) Nếu b > 0 thì nửa mặt phẳng phải tìm không chứa gốc tọa độ. b) Khi b < 0 thì nửa mặt phẳng tương ứng là nửa mặt phẳng chứa gốc tọa độ. 4 Để đơn giản ký hiệu, chúng ta bỏ chi số thứ nhất (chỉ số ứng với các hàng của A) Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 59 ́ ́ ̣ ̣
Lý t huyết qui hoạc h t uyến tí nh Để đánh dấu nửa mặt phẳng tương ứng người ta thường dùng ký hiệu mũi tên « ». Theo đó phần mặt phẳng hướng theo chiều mũi tên là phần mặt phẳng phải tìm. Sau khi đã xác định các phần mặt phẳng ứng với m ràng buộc dạng (2.1). Tập chấp nhận được X sẽ là phần giao của m phần mặt phẳng này với góc phần tư thứ nhất (I) của mặt phẳng tọa độ x20x1. Nếu phần giao này không rỗng, tức X ≠∅ , tức là bài toán QHTT có phương án chấp nhận được (Hình ). Trong trường hợp ngược lại, X = ∅ và bài toán QHTT không giải được (các ràng buộc mâu thuẩn nhau). x2 X 0 x1 ̀ Hinh 3.1 2.2 Tìm lời giải tối ưu 1) Biểu diễn hàm mục tiêu: Sau khi đã biể diễn tập chấp nhận được X và giả sử X ≠∅ . Bước tiếp theo là tìm trên tập X một điểm x* cho giá trị hàm mục tiêu Z nhỏ nhất. Ở trường hợp hai chiều hàm mục tiêu (1.1) hoặc (1.4) có dạng: Z = c1x1 + c2x2 (2.5) Giả sử c1≠ 0 hoặc c2 ≠ 0. 5 a) Khi c2 ≠ 0. Hàm (2.5) trở thành c Z x 2 = − 1 x1 + (2.6) c2 c2 Khi Z biến thiên, (2.6) biểu diễn một lớp các đường thẳng song song cắt trục 0x2 tại các điểm (0,Z/c2) và có cùng hệ số góc (– c1/c2). Đặc biệt ứng với Z = 0, đường thẳng (2.6) sẽ đi qua gốc tọa độ. Do vậy, ban dầu sau khi đã xác định X, người ta sẽ vẽ đường thẳng (2.6) ứng với Z = 0. b) Khi c1 ≠ 0, c2 = 0. Hệ đường thẳng (2.6) trở thành 5 Trường hợp c1 = c2 = 0 sẽ làm cho bài toán QHTT không có ý nghĩa kinh tếđồng thời cũng không có ý nghĩa toán học. Vì khi đó phương án nào cũng là phương án tối ưu. Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 60 ́ ́ ̣ ̣
Lý t huyết qui hoạc h t uyến tí nh Z x1 = (2.7) c1 Đây là hệ các đường thẳng vuông góc với trục 0x 1 tại điểm (Z/c1, 0). Người ta dễ dàng vẽ được đường thẳng này ứng với giá trị Z bất kỳ. 3) Tìm giá trị tối ưu : Khi c2 ≠ 0. Người ta phân biệt 2 trường hợp nhỏ : α) Với c2 > 0, ta nhận thấy giá trị Z/c2 giảm khi và chỉ khi Z giảm và ngược lại. Vì vậy, đường thẳng ứng với giá trị Z nhỏ nhất là đường thẳng thấp nhất mà có phần giao khác trống với tập chấp nhận được X. Để tìm đường thẳng này chỉ cần tịnh tiến đường thẳng c x 2 = − 1 x1 c2 ứng với giá trị Z = 0 lên phía trên cho đến khi cắt (hoậc tiếp xúc với) miền chấp chấp nhận được. Đây là đường thẳng ứng với giá trị Z tối ưu. (Hình ) Tương tự, nếu c1 > 0, c2 = 0 thì đường thẳng đầu tiên ở bên trái có giao khác trống với X sẽ là đường thẳng ứng với giá trị Z nhỏ nhất. β) Khi c2 < 0, giá trị Z/c2 giảm khi và chỉ khi Z tăng và ngược lại. Vì vậy, đường thẳng ứng với giá trị Z nhỏ nhất là đường thẳng cao nhất mà có phần giao khác trống với tập chấp nhận được X. Để tìm đường thẳng này chỉ cần tịnh tiến đường thẳng c x 2 = − 1 x1 c2 ứng với giá trị Z = 0 lên phía trên cho đến khi rời khỏi miền chấp chấp nhận được. Đường thẳng cuối cùng cắt hoặc tiếp xúc với X đường thẳng ứng với giá trị Z tối ưu. (Hình 3.2) Tương tự, nếu c1 < 0, c2 = 0 thì đường thẳng cuối cùng ở bên phải có giao khác trống với X sẽ là đường thẳng ứng với giá trị Z nhỏ nhất. x2 c2 > 0 x2 c2 = 0, c1 > 0 Zmin/c2 X X X x2* x2* 0 x1* x1 0 Zmin/c1= x1* x1 c x 2 = − 1 x1 c2 Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 61 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui hoach ̣ tuyên ́ ́ tinh ̀ Hinh 3.2 x2 c2 < 0 x2 c2 = 0, c1 < 0 XXX X X x2* x2* 0 x1* x1 0 Z min/c1= x1* c1 c1 Z x2 = − x1 x2 = − x1 + min c2 c2 c2 ̀ Hinh 3.3  Zmin   Zmin  Giá trị tối ưu là Zmin =   c 2 hoặc Z min =   c1  c2   c1  Phương án tối ưu là x1 = x1*, x2 = x2* 2.3 Ví dụ minh họa : Để làm ví dụ minh họa ta xét các bài toán QHTT sau đây :Tìm x1, x2 sao cho : 1) 2) Z = 2x1 + 3x 2 → min Z = 6x1 + 10x 2 → max  x1 +x2 ≤ 4  3x1 +5x 2 ≤ 15  6x   1 +2x 2 ≥ 6  5x1 +2x 2 ≤ 10  x1  +5x 2 ≥ 4  x ≥ 0; x ≥ 0  1 2   x1 ≤ 3  x2 ≤ 2   x1 ≥ 0; x 2  ≥ 0 3) 4) Z = 2x1 + 3x 2 → max Z = 5x1 + 3x 2 → min  x1 −x 2 ≥ −1  − x1 −x 2 ≥ −1    x1 −2x 2 ≥ −4  2x1 +2x 2 ≥ 4  x ≥ 0; x ≥ 0  x ≥ 0; x ≥ 0  1 2  1 2 Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 62 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh Z = −3x1 + 5x 2 → min  − x1 +x2 ≤ 0 5)   −3x1 + x 2 ≥ 2  x ≥ 0; x ≥ 0  1 2 Bài giải : 1) Các đường thẳng tương ứng sẽ là : x2 1 1 x1 + x2 = 1 (I) 4 4 (II) 1 x1 + x2 = 1 (II) 2 3 (V) Z min/3 A X 1 5 x1 + x2 = 1 (III) 4/5 4 4 x2* x1 = 3 (IV) 0 x1* 3 4 x1 (III) x2 = 2 (V) (IV) (I) x1 = 0; x2 = 0 Z=0 Zmin= 49/14 ̀ Hinh 3.4 2 Z Ở đây, đường thẳng hàm mục tiêu có dạng : x 2 = − x1 + . 3 3 Vì c2 = 3 > 0 và cần tìm Zmin nên phải tịnh tiến đường thẳng hàm mục tiêu ứng với Z = 0 lên phía trên cho đến khi tiếp xúc với miền chấp nhận được X thì dừng lại. Đây là đường thẳng ứng với giá trị Z nhỏ nhất (là đường thẳng thấp nhất). Điểm tiếp xúc là giao điểm của hai đường thẳng (II) và (III). Bằng cách chiếu thẳng góc lên hai trục tọa độ 0x1, 0x2, ta sẽ tính được các giá trị x1*, x2* ứng với với giá trị tối ưu Z*= Zmin. Tuy nhiên, bằng cách giải hệ 2 phương trình (II), (III) có thể tính được các giá trị này là : x1* = 11/14 ; x2* = 9/14. Khi đó OA = Zmin/3 = 49/42, và do vậy Zmin = 49/14. Vì đường thẳng tối ưu chỉ tiếp xúc với tập X ở duy nhất một điểm nên bài toán QHTT đang xét chỉ có duy nhất một phương án tối ưu ; đó là một điểm cực biên của X. Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 63 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh Tương tự, lời giải ứng với các bài toán kế tiếp như sau : 2) x2 3) x2 (I) Zmax/10= 3 A B x2* 2 X (II) X (I) 1 0 x1* 2 (II) 5 x1 -1 0 x1 ̀ Hinh 3.5 Ở bài 2, đường thẳng hàm mục tiêu 6x1 + 10x2 = Z có hệ số góc trùng với đường thẳng 1 1 (I) : x1 + x 2 = 1 5 3 Do hệ số c2 = 10 > 0, nên đường thẳng ứng với giá trị Z max sẽ là đường thẳng cao nhất có phần chung với tập X. Phần chung giữa đường thẳng này với tập X là cạnh AB (có hai điểm cực biên là A và B). Đây cũng chính là hai lời giải cơ sở tối ưu : A = (0, 3) và B = (20/19 ; 45/19). Giá trị tối ưu Zmax = 30. Dễ thấy rằng cạnh AB là một diện của đa diện lồi X. Do đó mọi điểm trên AB đều là lời giải tối ưu. Chúng la tổ hợp lồi của hai lời giải cực biên A va B. Trong trường hợp này bài toán QHTT có vô số lời giải tối ưu. Ở bài 3, X là tập hợp không bị chặn ; đó là tập lồi đa diện. Đường 2 Z thẳng biểu diễn hàm mục tiêu tương ứng có dạng : x 2 = − x1 + . Vì c3 = 3 3 3 > 0, nên để tìm giá trị Z lớn nhất phải tịnh tiến đường thẳng hàm mục tiêu lên phía trên. Tuy nhiên, do tập chấp nhận được X không bị chặn nên sẽ không tồn tại đường thẳng cao nhất có phần chung không rỗng với tập X. Điều này cho thấy hàm mục tiêu không bị chặn trên. Do dó bài toán QHTT không có lời giải tối ưu (Z → ∞). 4) Ở hai bài toán 4 và 5 tập chấp nhận được X tà tập rỗng (Hình ) : x2 x2 (I) (II) 2 1 Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 64 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh -2/3 1 1 2 0 1 x1 (I) (II) 4) 5) ̀ Hinh 3.6a ̀ Hinh 3.6b Ở bài 4 hai ràng buộc mâu thuẩn nhau. Các nửa không gian tương ứng không có điểm chung. Tức là X = ∅ (Hinh 3.6a). Trong bài 5, hai nửa mặt ̀ phẳng tương ứng có phần chung khác trống nhưng không nằm trong góc phần tư thứ I mà trong góc phần tư thứ III. Vì vậy X = ∅. (Hinh 3.6b). ̀ Năm ví dụ trên đây, một lần nửa, cho thấy rõ các tính chất cơ bản của bài toán QHTT là : i) Nếu miền chấp nhận được khác trống thì nó là tập lồi đa diện (và là đa diện lồi, nếu bị chặn) và có hữu hạn điểm cực biên. ii) Nếu miền chấp nhận được của bài toán QHTT khác trống và hàm mục tiêu bị chặn dưới (tương ứng : bị chặn trên) thì bài toán có lời giải tối ưu. iii) Nếu bài toán QHTT có lời giải tối ưu thì sẽ tồn tại ít nhất một điểm cực biên là lời giải tối ưu.(Ở bài toán 2 có hai diểm cực biên tối ưu, nên có vô số lời giải tối ưu và tập hợp các lời giải tối ưu biểu diễn một diện của tập chấp nhận được X). Vì vậy, để giải bài toán QHTT, nếu như không có điều kiện nào khác, chỉ cần xét các điểm cực biên của tập chấp nhận được ; so sánh giá trị hàm mục tiêu ở các điểm ấy, sẽ tìm ra giá trị tối ưu hoặc chứng tỏ rằng bài toán QHTT không giải được. §3 Bài toán qui hoạch tuyến tính đối ngẫu Tính chất của cặp bài toán QHTT đối ngẫu 3.1 Bài toán qui hoạch tuyến tính đối ngẫu : Xét bài toán QHTT dạng cơ bản (1.1) – (1.3), ký hiệu là bài toán P (primal) n Z = ∑ c jx j j =1 → min (1.1) ∑ a x ≥ b , n i = 1, 2,..., m (1.2)  j= & ij j i    x j ≥ 0, j = 1, 2....., n (1.3) Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 65 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh Đn 3.1 : Ưng với bài toán (P) người ta định nghĩa bài toán QHTT sau đây và gọi là bài toán QHTT đối ngẫu với (P), ký hiệu là bài toán (D) (dual) : Tìm m số thực yi, i = 1,2,…,m thỏa mãn : n W = ∑ bi yi → max j =1 (3.1) ∑ a y ≤ c , m j = 1, 2,..., n ( 3.2 )  i =1 ij i j   yi ≥ 0,  i = 1, 2....., m (3.3) Ký hiệu A = ((aij)), i = 1,2,…,m ; j = 1,2,…,n , là ma trận thực cấp mxn ; b là vectơ m-thành phần bi, i = 1,2,…,m , c là vectơ n-thành phần cj, j = 1,2,…,n , thì hai bài toán (P) và (D) có thể được viết dưới dạng ma trận nhu sau : Tìm x = (x1, x2,…, xn) sao cho Tìm y = (y1, y2,…, ym) sao cho Z = 〈c,x〉 → min W = 〈b,y〉 → max (P) Ax ≥ b (D) ATy ≤ b x≥ 0 y≥ 0 Nhận xét : 1) Các hệ số aij, cj, bi, i = 1 ,2 ,….,m ; j = 1,2,….n, ở hai bài toán gốc và đối ngẫu là như nhau. 2) Số biến số của bài toán đối ngẫu (D) bằng số ràng buộc của bài toán gốc (P) ; 3) Số ràng buộc của bài toán đối ngẫu (D) bằng số biến số của bài toán gốc (P) ; 4) Mỗi cột của A ứng với mỗi biến số xj của (P) và mỗi hàng của A ứng với mỗi biến số yi của (D) 5) Vectơ vế phải b của (P) trở thành vectơ hệ số hàm mục tiêu của (D) ; vectơ hệ số hàm mục tiêu c của (P) trở thành vectơ vế phải của (D). 3.2 Các qui tắc thành lập bài toán đối ngẫu ứng với một bài toán QHTT bất kỳ 3.2.1 Qui tắc chung : Để thành lập bài toán QHTT đối ngẫu ứng với một bài toán QHTT cho trước người ta tiến hành các bước sau đây : a) Chuyễn bài toán QHTT gốc về dạng bài toán (1.1) – (1.3) theo các kỹ thuật như sau : Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 66 ́ ́ ̣ ̣
Lý t huyế t qui hoạ c h t uyế n t í nh n i) Ưng với ràng buộc dạng ∑ a ij ≤ bi : Chỉ cần nhân 2 vế với j =1 (–1) và đặt a‘ij = -aij, b’i = -bi, ∀ij, sẽ có dạng như (1.2) . n ii) Mỗi ràng buộc dạng ∑ a ij = bi tương ứng với hai ràng buộc j =1 n n dạng ∑ a ij ≥ bi và ∑ ( −a ij ) ≥ ( − bi ) . Ưng với ràng buộc thứ 2 j =1 j =1 dùng ký hiệu như ở phần i) sẽ có dạng (1.2). iii) Điều kiện xj ≤ 0, tương đương với điều kiện –xj ≥ 0. Chỉ cần đổi biến số x’j = -xj sẽ có dạng như (1.3) ; iv) Khi biến xj trong bài toán có thể nhận giá trị bất kỳ (không hạn chế về dấu), có thể đặt xj = xj’ – xj’’ và thêm 2 điều kiện xj’≥ 0, xj’’≥ 0. Hai điều kiện này có dạng (1.3) và dễ thấy rằng chúng tương đương với điều kiện xj không bị hạn chế về dấu. v) Nếu bài toán ban đầu đòi hỏi tìm cực đại của hàm mục tiêu : Z → max, thì chỉ cần đổi biến số và đặt Z’ = -Z và yêu cầu Z’→min . Khi đó giá trị tối ưu Zmax = -Z’min. Với Z’ mục tieu cần tìm có dạng như (1.1). b) Dùng định nghĩa để tìm bài toán QHTT đối ngẫu tương ứng. Sau đây là cách thực hiện đơn giản : x1≥ 0 … xj ≥ 0 … xn≥ 0 W y1≥ 0 a11 … a1j … a1n ≥ b1 … … … … … … … yi≥ 0 ai1 … aij … ain ≥ bi … … … … … … … ym≥ 0 am1 … amj … amn ≥ bm ≤ … ≤ … ≤ ↓max Z c1 … cj cn → min Từ sơ đồ này, để có ràng buộc của bài toán đối ngẫu chỉ cần nhân tương ứng cột biến số yi với từng cột của ma trận A. Dấu của các ràng buộc ứng với dấu ở dưới mỗi cột (trên cj) ; để có hàm mục tiêu W chỉ cần nhân tương ứng cột biến số yi với cột vế phải b. (Sơ đồ này cũng cho biết dạng cụ thể của bài toán gốc). Ví dụ : Tìm bài toán QHTT đối ngẫu của bài toán sau đây : Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 67 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui hoach ̣ tuyên ́ ́ tinh Z = 4x1 − 2x 2 + 5x 3 → max  x1 + 3x 2 − x 3 ≤ 5  3x1 + x3 ≥ 6 (3.4)  x +x +x =8  1 2 3 x 2 ≥ 0, x 3 ≤ 0 Bai giải : Trước hết hãy đưa bài toán trên về dạng cơ bản. Chúng ta tiến ̀ hành lần lượt các bước sau đây : Đặt Z’ = -Z = -4x1 + 2x2 - 5x3 ; nhân 2 vế của ràng buộc 1 với –1 ; thay ràng buộc 3 bằng hai ràng buộc  x1 + x 2 + x 3 ≥ 8  ;  − x1 − x 2 − x 3 ≥ −8 đặt x1 = x1’ – x1’’ ; thay x3 bằng x3’= -x3. Bài toán (3.4) tương đương với bài toán QHTT sau đây : Z' = −4x1 + 4x1 + 2x 2 + 5x 3 → min ' '' '  − x1 + x1'' − 3x 2 − x 3 ≥ −5 ' '   3x1 − 3x1 − x '3 ≥ 6 ' ''  (3.5)  x1 − x1 + x 2 − x 3 ≥ 8 ' '' '  − x1 + x1 − x 2 + x 3 ≥ −8  ' '' ' x1' ≥ 0, x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0 '' ' Áp dụng qui tắc thành lập bài toán QHTT đối ngẫu ở trang bên, ta có bảng x1’≥ x1’’≥ 0 x2≥ 0 x3’ ≥ 0 W 0 y1≥ 0 -1 1 -3 -1 ≥ -5 y2≥ 0 3 -3 0 -1 ≥ 6 y’3≥ 1 -1 1 -1 ≥ 8 0 y’4≥ -1 1 -1 1 ≥ -8 0 ≤ ≤ ≤ ≤ ↓max Z’ -4 4 2 5 → min Khi đó bài toán đối ngẫu có dạng : Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 68 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh W ' = −5y1 + 6y '2 + 8y '3 − 8y '4 → max  − y1 + 3y '2 + y '3 − y '4 ≤ −4  y − 3y ' − y ' + y ' ≤ 4  1 2 3 4  (3.6)  −3y1 + y '3 − y '4 ≤ 2  − y1 − y '2 − y '3 + y '4 ≤ 5  y1 ≥ 0, y '2 ≥ 0, y '3 ≥ 0, y '4 ≥ 0 Do bài toán (D) cũng là bài toán QHTT nên cũng có bài toán đối ngẫu tương ứng. Bằng cách dùng các kỹ thuật biến đổi như trên để đưa bài toán (D) về dạng cơ bản, áp dụng định nghĩa để viết bài toán đối ngẫu tương ứng. Sau đó thực hiện các phép biến đổi ngược lại, người ta có thể chứng minh định lý sau đây : Đlí 3.1 : Bài toán QHTT đối ngẫu với (D) chính là bài toán (P) 6 Do đó hai bài toán (P) và (D) được gọi là cặp bài toán đối ngẫu. 3.2.2 Qui tắc trực tiếp lập bài toán đối ngẫu từ một bài toán gốc bất kỳ : Bằng cách dùng các kỹ thuật biến đổi tương tự để đưa một bài toán QHTT bất kỳ về dạng cơ bản (1.1) – (1.3), lập bài toán đối ngẫu theo qui tắc chung (như phần 3.2.1), sau đó biến đổi ngược lại, người ta có thể chứng minh Qui tắc trực tiếp lập bài toán đối ngẫu như sau đây. Tuy nhiên, theo Đlí 3.1, bất kỳ bài toán QHTT nào cũng có bài toán đối ngẫu tương ứng nên cần phân biệt hai trường hợp : Trường hợp A : (P) Z → min ↔ (D) W → max ∑ aijxj ≥ bi ↔ yi ≥ 0 ∑ aijxj = bi ↔ yi nhận giá trị tùy ý ∑ aijxj ≤ bi ↔ yi ≤ 0 xj ≥ 0 ↔ ∑ aijyi ≤ cj xj nhận giá trị tùy ý ↔ ∑ aijyi = cj xj ≤ 0 ↔ ∑ aijyi ≥ cj Trường hợp B : 6 Trong một số tài liệu khác viết về Lý thuyết QHTT, người ta định nghĩa bài toán gốc có dạng như bài toán (D) còn bài toán đối ngẫu tương ứng có dạng như (P). Theo định lý trên thì hai cách định nghĩa này la tương đương nhau. Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 69 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh (P) Z → max ↔ (D) W → min ∑ aijxj ≤ bi ↔ yi ≥ 0 ∑ aijxj = bi ↔ yi nhận giá trị tùy ý ∑ aijxj ≥ bi ↔ yi ≤ 0 xj ≥ 0 ↔ ∑ aijyi ≥ cj xj nhận giá trị tùy ý ↔ ∑ aijyi = cj xj ≤ 0 ↔ ∑ aijyi ≤ cj Ví du : Xét bài toán QHTT đối ngẫu (3.6). Hai ràng buộc đầu tương đương với ràng buộc duy nhất (dạng đẵng thức): y1 - 3y’2 – y’3 + y’4 = 4 Đặt y3 = y’4 - y’3, y2 = -y’2, W = -W’. Khi đó bài toán (3.6) trở thành : W = 5y1 + 6y 2 + 8y3 → min  y1 + 3y 2 + y3 = 4   3y1 + y3 ≥ −2 (3.7)  −y + y + y ≤ 5  1 2 3 y1 ≥ 0, y 2 ≤ 0; y3 ∈ R Dễ thấy rằng bài toán (3.7) là bài toán QHTT đối ngẫu của (3.4) được lập theo qui tắc trực tiếp 3.2.2. 3.3 Tính chất của cặp bài toán QHTT đối ngẫu : Để trình bày các tính chất của cặp bài toán QHTT đối ngẫu chúng ta trở lại dạng bài toán (1.1)-(1.3) và (3.1)-(3.3) hay dạng ma trân (P) và (D). Để đơn giản chứng minh, ta sử dụng dạng ma trận. Ký hiệu X = {x∈Rn/ Ax ≥ b, x ≥ 0}, Y = {y ∈Rm/ ATy ≤ c, y ≥ 0} là các miền chấp nhận được tương ứng ; Zmin, Wmax là các giá trị tối ưu (nếu có). TC1 : Giả sử X, Y không rỗng : ∀x∈X, ∀y∈Y : 〈b,y〉 ≤ 〈c,x〉 (3.8) Tức là, dù cho x và y chọn như thế nào đi nữa thì giá trị hàm mục tiêu của bài toán đối ngẫu không bao giờ vượt quá giá tri hàm mục tiêu của bài toán gốc. Chứng minh (Bài tập 52) TC2 : Điều kiện cần và đủ để bài toán QHTT (P) giải được là bài toàn QHTT đối ngẫu (D) cũng giải được. Khi đó Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 70 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh Zmin = Wmax (3.9) Chứng minh : Thật vậy, (P), (D) là các dạng đặc biệt của bài toán QH lồi cơ bản. Do đó có thể áp dụng các kết quả trong chương II cho bài toán (P) và (D). Ta xét (P). Giã sử (P) giải được và x* là lời giải tối ưu. Khi đó theo Định lý 2.3 (chương II), sẽ tồn tại y* ≥ 0, để cho cặp (x*,y*) là điểm yên ngựa của hàm Lagrange LP(x,y) trên miền Γ = {x∈Rn/ x ≥ 0} và {y∈Rn/ y ≥ 0}, trong đó LP(x,y) = 〈c,x〉 + 〈y, b - Ax〉 . Theo định lý 2.4 cặp (x*,y*) thỏa mãn các điều kiện Kuhn-Tucker (2.28) dành cho bài toán QHTT với Q = 0 và p = c: c - ATy* – v =0 Ax* – b – u* = 0 〈x*, v*〉 + 〈y*, u*〉 = 0 x* ≥ 0; v* ≥ 0; y* ≥ 0; u* ≥ 0 Hay c - ATy* ≥ 0 (3.10) 〈x*, c - ATy*〉 =0 (3.11) x* ≥ 0 (3.12) và Ax* – b ≥ 0 (3.13) 〈y*, Ax* – b 〉 =0 (3.14) y* ≥ 0 (3.15) Từ đây suy ra với (3.10) và (3.15) thì y*∈Y. Mặt khác, do (x*, y*) là điểm yên ngựa của hàm LP(x,y), nên ∀ x ≥ 0, ∀ y ≥ 0 : LP(x*,y) ≤ LP(x*,y*) ≤ LP(x,y*) Tức là 〈c,x*〉 + 〈y, b – Ax*〉 ≤ 〈c,x*〉 + 〈y*, b – Ax*〉 ≤ 〈c,x〉 + 〈y*, b - Ax〉 Hay 〈b, y〉 + 〈x*, c – ATy〉 ≤ 〈b,y*〉 + 〈x*, c – ATy*〉 ≤ 〈b,y*〉 +〈x, c - ATy*〉 Do có (3.11) nên ∀ x ≥ 0, ∀ y ≥ 0 〈b, y〉 + 〈x*, c – ATy〉 ≤ 〈b,y*〉 ≤ 〈b,y*〉 +〈x, c - ATy*〉 Do ∀ y∈Y, 〈x*, c – ATy〉 ≥ 0, nên từ bất dẵng thức bên trái suy ra 〈b, y〉 ≤ 〈b,y*〉 Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 71 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh Tức là Wmax = 〈b,y*〉 . Vậy (D) giải được. Tương tự, từ giả thiết (D) giải được cũng chứng minh được rằng (P) giải được. Như vậy các vectơ x*, y* lập nên điểm yên ngựa của LP(x,y) là lời giải của (P) và (D) tương ứng. Mặt khác do LP(x*,y*) = 〈c,x*〉 + 〈y*, b – Ax*〉 = 〈b,y*〉 + 〈x*, c – ATy*〉 nên từ (3.11) và (3.14) suy ra Z min = 〈c,x*〉 = 〈b,y*〉 = Wmax.ª TC 3 : (Định lý độ lệch bù yếu) Điều kiện cần và đủ để cho x*∈X, y*∈Y là lời giải tối ưu của cặp bài toán QHTT tương ứng (P), (D) là m x *j .(c j − ∑ a ij y* ) = 0; j = 1, 2,..., n i (3.16) i =1 n y* .( ∑ a ij x *j − bi ) = 0; i = 1, 2..., m i (3.17) j =1 Chứng minh : Điều này dễ dàng suy ra từ các Bất đẵng thức Kuhn- Tucker (3.10) – (3.15). ª Hệ quả 1 : Để cho cặp bài toán QHTT (P), (D) giải được thì điều kiện cần và đủ là X ≠ ∅ và Y≠ ∅. Hệ quả 2 : Nếu X ≠ ∅ và Z =〈c, x〉 không bị chặn dưới trên X thì Y=∅ va, do đó, (D) không giải được. Ngược lại, nếu Y≠ ∅ và W =〈b, y〉 không bị chặn trên trên Y thì X =∅ và, do đó, (P) không giải được. Bạn đọc sẽ chứng minh các hệ quả này dựa trên các tính chất 1, 2, 3 đã nêu ở trên. §4 Ý nghĩa kinh tế của bài toán QHTT 4.1 Bài toán sản xuất Bài toán : Một xí nghiệp có thể sản xuất n loại sản phẩm, ký hiệu S1, S2, …, Sn, từ m loại nguyên liệu khác nhau, ký hiệu N1, N2…Nm. Biết aij, là khối lượng nguyên liệu loại Ni tiêu hao bởi một đơn vị sản phẩm loại Sj; bi là khối lượng nguyên liệu loại Ni mà xí nghiệp có thể huy động được ; cj là lợi nhuận thu được khi sản xuất và bán một đơn vị sản phẩm loại S j, i = 1,…,m ; j = 1,2,…,n. Giả sử xí nghiệp có thể sản xuất và tiêu thụ sản phẩm không hạn chế. Hãy tìm khối lượng sản phẩm mỗi loại mà trong phạm vi số nguyên liệu huy động được, xí nghiệp có lợi nhuận tối đa. Lập mô hình : Đặt xj là số sản phẩm loại Sj mà xí nghiệp cần phải sản xuất (phải tìm), j =1,2,…,n ; Z là tổng lợi nhuận mà xí nghiệp thu được khi sản xuất và tiêu thụ số sản phẩm sản xuất ra. Khi ấy mô hình bài toán như sau: Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 72 ́ ́ ̣ ̣
́ thuyêt Ly ́ qui ̣ hoach tuyên ́ ́ tinh  Z = ∑ c x → max n  j =1 j j n   ∑ a ij x j ≤ bi , i = 1, 2,..., m (3.18)  j=1  x j ≥ 0, j = 1, 2,..., n   4.2 Bài toán pha trộn thức ăn gia súc : Bài toán : Người ta cần phải pha trộn một loại thức ăn gia súc từ n loại thức ăn thô khác nhau, ký hiệu B1,…,Bn. Theo yêu cầu chất lượng, trong một đơn vị thức ăn tổng hợp phải chứa đủ bi đơn vị chất dinh dưỡng Ai, i = 1,2,…,m. Biết rằng trong một đơn vị thức ăn thô mỗi loại Bj có aij đơn vị dinh dưỡng Ai, cj là chi phí cho một đơn vị thức ăn thô Bj, i = 1,2,…,m ; j = 1,2,…., n. Tìm tỉ lệ pha trộn thức ăn thô trong một đơn vị thức ăn tổng hợp sao cho tổng chi phí cho một đơn vị thức ăn tổng hợp ít nhất. Lập mô hình : Gọi xj là số đơn vị thức ăn thô loại Bj trong một đơn vị thức ăn tổng hợp, j = 1, 2,…,n ; Z là tổng chi phí cho một đơn vị thức ăn tổng hợp. Khi đó ta có mô hình bài toán như sau :  Z = ∑ c x → min n  j =1 j j n   ∑ a ij x j ≥ bi , i = 1, 2,..., m (3.19)  j=1  x j ≥ 0, j = 1, 2,..., n   4.3 Bài toán pha cắt đơn giản Bài toán : Tại một xí nghiệp sản xuất sườn xe đạp người ta cần phải cắt từ một ống sắt có độ dài cố định là l m thành m đoạn có độ dài tương ứng là li, i = 1, 2,…,m. Biết rằng theo đơn đặt hàng làm sườn xe, xí nghiệp cần phải cắt bi, đoạn có độ dài li, i = 1, 2,…,m. Tìm phương án cắt ống sắt sao cho đảm bảo được hợp đồng nhưng với số lượng ống sắt sử dụng là ít nhất. Lập mô hình : Giả sử từ một ống sắt có độ dài cố định là l người ta có n cách cắt (phương án cắt), ký hiệu Vj, j = 1, 2, …, n, thành các đoạn có độ dài li khác nhau, 1≤ i ≤ m ; gọi aij là số đoạn ống có độ dài li cắt dược từ ống sắt có độ dài l theo phương án Vj ; cj là độ dài đoạn ống còn dư khi cắt theo phương án Vj. Hiển nhiên, 0 ≤ cj ≤ min {li}, i = 1, 2,…,m ; j = 1, 2,…, n. Đặt xj là tổg số ống sắt được cắt theo phương án Vj , j = 1, 2,…, n và Z là tổng độ dài ống còn dư ra. Khi đó tổng số đoạn ống có độ dài li là : Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 73 ́ ́ ̣ ̣
Lý t huyế t qui hoạ c h t uyế n t í nh n n ∑ a ij x j và tổng số độ dài ống dư ra là Z = ∑ c j x j . Căn cứ vào yêu cầu của j =1 j =1 bài toán ta có mô hình bài toán QHTT có dạng (3.19). Chú ý : Nếu yêu cầu cắt sao cho tổng số ống sắt phải sử dụng là ít nhất, n thì bài toán sẽ có hàm mục tiêu đơn giản là : Z = ∑ x j → min. j =1 4.4 Bài toán pha trộn khí đốt Bài toán : Tại một cơ sở sản xuất chất đốt phục vụ người tiêu dùng người ta cần phải pha trộn thành một loại chất đốt tổng hợp từ n loại chất đốt tự nhiên, ký hiệu là B j, j = 1, 2, …, n.. Biết nhiệt lượng riêng của loại chất đốt tự nhiên Bj là cj kcal/ m3; hàm lượng độc tố loại Ai (có hại đến sức khỏe người tiêu dùng) trong 1 m 3 chất đốt tự nhiên loại Bj là aij g/ m3, i =1,2,…,m; chi phí sản xuất 1 m3 chất đốt tự nhiên Bj là dj, j =1, 2, …,n. Theo yêu cầu, nhiệt lượng riêng của chất đốt tổng hợp phải ở trong khoảng [u, v] kcal/m3 ; hàm lượng độc tố loại Ai có trong 1 m3 chất đốt tổng hợp phải không vượt quá bi g, i = 1, 2, …, m. Tìm khối lượng mỗi chất đốt tự nhiên phải sử dụng để pha trộn sao cho hất đốt tổng hợp có được nhiệt lượng riêng theo yêu cầu và khối lượng chất độc mỗi loại ở mức cho phép với tổng chi phí sản xuất khối lượng chất đốt tự nhiên cần thiết là ít nhất. Lập mô hình : Gọi xj là khối lượng chất đốt tự nhiên Bj dược sử dụng, j = 1,2,…,n. Z là tổng chi phí sản xuất khối lượng các loại chất đốt tự nhiên phải sử dụng. Khi đó tổng nhiệt lượng tỏa ra của chất khí tổng hợp sẽ là n ∑ c j x j kcal. Vậy nhiệt lượng riêng của chất đốt tổng hợp phải thỏa mãn j =1 n ∑ c jx j j =1 u≤ n ≤ v ∑ xj j =1 n n n Hay u ∑ x j ≤ ∑ c j x j ≤ v∑ x j (3.20) j =1 j =1 j =1 Hàm lượng độc tố Ai trong 1 m3 chất đốt tổng hợp phải thỏa mãn điều n ∑ ai jx j j =1 kiện 0≤ n ≤ bi . ∑xj j =1 n n Hay 0 ≤ ∑ a ij x j ≤ bi ∑ x j j =1 j =1 Ta có mô hình bài toán QHTT như sau : Tìm các giá trị x1, x2,…., xn sao cho Lê Văn Phi, Khoa Toan Thông kê,Trường Đai hoc Kinh tế Tp. Hồ Chí Minh 74 ́ ́ ̣ ̣