TRONG HỆ THỐNG THỦY LỢI
7.2. QUI HOẠCH TUYẾN TÍNH (QHTT)
7.2.3. Giải bài toán QHTT
Để giải bài toán QHTT bằng phương pháp hình học, chúng ta sử dụng mô hình bài toán đã thiết lập cho thí dụ 7.1. Xét mô hình bài toán QHTT dạng chuẩn (7.23), ta thấy tồn tại 2 biến chính là X1 và X2, với chỉ 2 biến, chúng ta có thể dễ dàng nghiên cứu lời giải bằng phương pháp đồ thị trên không gian 2 chiều (mặt phẳng), để từ đó có thể rút ra những tính chất tổng quát cho bài toán nhiều biến.
Trước tiên cần xác định miền biến thiên của biến chính. Do có ràng buộc không âm đối với biến chính, chúng ta chỉ cần xét trên 1/4 mặt phẳng mà (X1, X2 ≥
0) trong hình 7.2. Sau đó tới điều kiện ràng buộc (7.18), ràng buộc này chính là phần mặt phẳng nằm bên trái đường thẳng X1 = 4. Tương tự, đối với rằng buộc (7.20) là phần mặt phẳng bên dưới đường X2 = 6. Ràng buộc về sức lao động (7.21) là phần bên trái của đường 3X1 + 2X2 = 18, đường này đi qua các điểm có tọa độ (X1=0, X2=9) và (X1=6, X2=0).
Đối với hàm mục tiêu (7.17), vì hàm mục tiêu Z có giá trị xác định đối với X1
và X2 trong phạm vi ràng buộc của chúng, cho nên có thể viết lại như sau:
2 1
Z 3
X X
5 5
= + (7.25)
Phương trình (7.25) là một họ các đường thẳng có hệ số góc bằng (3/5), còn tùy thuộc vào giá trị của Z mà đường thẳng này cắt trục X2 ở đâu. Thí dụ khi Z = 0, thì đường thẳng đi qua điểm gốc tọa độ (X1=0, X2 =0), nếu Z = 5, đường thẳng sẽ đi qua điểm (X1=0, X2 =1). Lưu ý rằng, khi Z càng lớn thì đường thẳng sẽ càng đi lên phía trên của trục X2.
X1 <= 4
X2 <= 6
3X
1+ 2X
2<= 18
X1
X2
Z = 0 Z = 5
Z = 36
0 1
1
2 3 4 5 6 7
2 3 4 5 6 7 8 9 10
Miền giới hạn của biến chính
nghiệm của bμi toán:
X1* = 2 X2* = 6 Z* = 36
Hình 7.2: Phương pháp đồ thị giải thí dụ 7.1
Bây giờ bằng phương pháp tịnh tiến, chúng ta dịch chuyển đường (7.25) dần lên phía trên của trục X2, sao cho không vượt ra ngoài miền giới hạn của hai biến X1 và X2. Cuối cùng chúng ta tìm được đường cho giá trị cao nhất Z = 36 đi qua
điểm (X1=2,
X2 =6). Đó chính là lời giải của bài toán, tức là Z* = 36, còn X1* = 2 và X2* = 6.
2. Một số nhận xét quan trọng từ phương pháp đồ thị
Sau khi giải bằng phương pháp hình học với miền giới hạn của biến quyết định cũng như sự thay đổi của hàm mục tiêu, chúng ta có thể rút ra một số nhận xét quan trọng đã được chứng minh trong toán học cho mọi trường hợp của bài toán QHTT (Tâm, et al., 1998).
- Nếu bài toán QHTT có phương án tối ưu, thì có ít nhất một đỉnh của miền nghiệm cho giá trị tối ưu của hàm mục tiêu. Sở dĩ nói ít nhất có một đỉnh bởi có thể đường mức của hàm mục tiêu Z trong trường hợp nào đó sẽ trùng với một cạnh của miền nghiệm, khi đó tất cả các điểm trên cạnh này là phương án nghiệm tối ưu và cho cùng một giá trị tối ưu của hàm mục tiêu.
- Nếu miền giới hạn của nghiệm giới nội (biên khép kín) và không rỗng thì chắc chắn tồn tại phương án tối ưu.
- Nếu miền giới hạn của nghiệm không giới nội nhưng hàm mục tiêu bị chặn trên ở miền giới hạn của biến thì bài toán cũng chắc chắn tồn tại phương án tối ưu.
3. Giải bài toán bằng phương pháp đơn hình (Simplex Method)
Cơ sở của phương pháp đơn hình được Dantzig công bố năm 1947. Có tên gọi như vậy là vì những bài toán đầu tiên được giải bằng phương pháp của Dantzig có các ràng buộc dạng:
n
j j
j 1
x 1, x 0 , j 1, ..., n
= = ≥ =
∑ (7.26)
mà tập các điểm x∈Rn thỏa mãn các ràng buộc trên là một đơn hình trong không gian n chiều. Sau đó thuật toán đơn hình được cải biên có tên gọi phương pháp đơn hình cải biên. Từ phương pháp đơn hình và đơn hình cải biên, các nhà toán học đã dần dần hoàn thiện các vấn đề toán học xung quanh phương pháp này. Chẳng hạn như phương pháp số lớn M hay phương pháp hai pha khi tìm phương án nghiệm cực biên, bài toán đối ngẫu. Gần đây, đã xuất hiện phương pháp tìm nghiệm tắt với thuật toán khác với thuật toán của phương pháp đơn hình. Các phần tiếp theo, chúng ta sẽ lần lượt đề cập đến những phương pháp quan trọng nhất và có ý nghĩa thực tế nhất trong các phương pháp nêu trên.
Đường lối chung của phương pháp đơn hình dựa trên hai nhận xét sau:
- Nếu bài toán QHTT có phương án tối ưu thì có ít nhất một đỉnh của miền giới
hạn nghiệm là phương án tối ưu.
- Đa diện lồi của miền giới hạn nghiệm chắc chắn có số đỉnh hữu hạn. Như vậy
phải tồn tại thuật toán giải hữu hạn.
Như vậy, về nguyên tắc, thuật toán giải bài toán QHTT gồm hai giai đoạn:
Giai đoạn 1: Tìm một phương án cực biên (tại một đỉnh của miền giới hạn nghiệm).
Giai đoạn 2: Kiểm tra điều kiện tối ưu đối với phương án tìm được ở giai đoạn 1. Nếu điều kiện tối ưu được thỏa mãn thì phương án đó là tối ưu. Nếu không, ta chuyển sang phương án cực biên mới có giá trị hàm mục tiêu tốt hơn.
Tiếp theo lại kiểm tra điều kiện tối ưu đối với phương án mới cho tới khi giá trị của hàm mục tiêu không thể tốt hơn nữa.
Người ta thực hiện một dãy các thủ tục như vậy cho đến khi nhận được phương án tối ưu của bài toán, hoặc đến tình huống bài toán không có phương án tối ưu.
Về mặt thuật toán, phương pháp đơn hình được thực hiện đối với bài toán QHTT dạng chính tắc và bao gồm ba bước cơ bản là:
- Bước xuất phát: Bắt đầu với một phương án nghiệm cực biên nào đó.
- Bước lặp: Thực hiện tính lặp cho điểm nghiệm biên kề cận tốt hơn.
- Bước dừng: Kiểm tra điều kiện tối ưu của phương án, nếu đạt yêu cầu, dừng bài toán, nếu chưa đạt, điều chỉnh phương án và quay lại bước lặp.
Xét mô hình bài toán của thí dụ 7.1, sau khi đã đưa các biến phụ vào điều kiện ràng buộc để được bài toán dạng chính tắc (7.24), chúng ta có thể viết lại mô hình bài toán để sử dụng phương pháp đơn hình.
1 2
1 3
2 4
1 2 5
1 2 3 4 5
Max ' Z ' Thỏa mãn :
(0) Z 3X 5X 0
(1) X X 4
(2) X X 12
(3) 3X 2X X 18
X , X , X , X , X 0
− − =
+ =
+ =
+ + =
≥
(7.27)
Khi đã có mô hình bài toán QHTT dạng chính tắc tương tự như (7.27), ba bước cơ bản của thuật toán đơn hình nêu trên được chi tiết thành 5 bước giải bài toán như sau:
Bước 0: Từ mô hình bài toán QHTT dạng chính tắc, tìm phương án cực biên ban đầu, sau đó xây dựng bảng đơn hình xuất phát. Người ta hay cho các biến chính nhận giá trị 0, sau đó tính ra giá trị các biến phụ, và tất nhiên giá trị của hàm
mục tiêu cũng sẽ bằng 0. Theo cách như vậy, ở mô hình (7.27), phương án cực biên xuất phát sẽ là:
{X1, X2, X3, X4, X5} = {0, 0, 4, 12, 18}
Phương án cực biên xuất phát ứng với điểm gốc tọa độ trong hình 7.2 khi giải bằng phương pháp đồ thị. Và chúng ta có được bảng đơn hình xuất phát dưới đây.
Bảng đơn hình xuất phát
Các hệ số của biến Tên
hàng Tên
biến Phương
trình số Z X1 X2 X3 X4 X5
Giá trị vế phải
Hàng 0 Z 0 1 -3 -5 0 0 0 0
Hàng 1 X3 1 0 1 0 1 0 0 4
Hàng 2 X4 2 0 0 2 0 1 0 12
Hàng 3 X5 3 0 3 2 0 0 1 18
Bước 1: Kiểm tra hàng 0 (là hàng chứa biến Z), nếu tất cả các hệ số đều không âm thì dừng tính toán và chúng ta đã có nghiệm tối ưu, nếu không thì chuyển sang bước 2. Trong bảng đơn hình xuất phát trên, tồn tại hai hệ số mang dấu âm (-) là (-3) và (-5), cho nên phải chuyển sang bước tiếp theo.
Bước 2: Tìm "cột quay" và "biến thay thế". Cột quay là cột chứa hệ số âm lớn nhất của biến trong hàng 0. Biến thay thế là biến ứng với hệ số âm lớn nhất đó.
Trong bảng đơn hình xuất phát ở trên, hệ số âm lớn nhất của hàng 0 là (-5) và cột chứa nó là cột quay, còn biến thay thế là X2 (xem bảng đơn hình 1).
Bước 3: Kiểm tra điều kiện về phương án biên. Nếu tất cả các hệ số thuộc cột quay là không dương, điều này chứng tỏ phương án nghiệm ban đầu không nằm trên biên. Dừng tính toán và tìm phương án nghiệm xuất phát khác (quay lại bước 0). Nếu có ít nhất một hệ số là dương, chuyển sang bước 4.
Bước 4: Tìm "hàng quay" và "biến bị thay thế". Muốn vậy cần phải tính toán và tìm tỉ số hệ số nhỏ nhất ốmin.
i i
ik
b
θ = a đối với tất cả aik > 0 (7.28) Trong đó aik là hệ số thứ i của biến thuộc cột quay, bi là giá trị thứ i ở vế phải.
Sau đó so sánh và chọn được ốmin = min (ối). Lưu ý không tính với hàng 0 (hàng chứa biến Z).
Trong bảng đơn hình xuất phát, ứng cột quay, đối với hàng 1 có 1 4 θ = 0 = ∝, đối với hàng 2 có 2 12 6
θ = 2 = , đối với hàng 3 có 3 18 9
θ = 2 = . Ta tìm được ốmin = min(ối) = ối = 6.
Như vậy hàng quay là hàng 2 và biến bị thay thế ứng với hàng 2 là biến X4. Bước 5: Lập bảng đơn hình tiếp theo và quay lại bước 1. Bảng đơn hình tiếp theo có những đặc điểm cơ bản sau:
+ Biến bị thay thế ở cột "Tên biến" sẽ bị đưa ra khỏi bảng và biến thay thế sẽ được đưa vào tại vị trí vừa bỏ trống.
+ Hàng có biến mới sẽ thay thế hàng quay cũ với những hệ số (kể cả vế phải) mới được tính theo công thức sau:
Hệ số hàng có biến mới = (Hệ số hàng quay cũ)/(Hệ số tại cột quay) Trong bảng đơn hình xuất phát, hệ số của hàng quay tại cột quay là (2), cho nên các hệ số mới của hàng quay mới sẽ là:
0 2 0 1 0 12
2 2 2 2 2 2
0 1 0 1 0 6
2
⎧ ⎫
⎨ ⎬
⎩ ⎭
⎧ ⎫
⎨ ⎬
⎩ ⎭
(7.29)
+ Các hàng mới còn lại (kể cả hàng 0 chứa Z) sẽ thay thế các hàng cũ với những hệ số mới được tính theo công thức sau:
Hệ số hàng mới = (Hệ số hàng cũ) - (Hệ số tại cột quay) x x (Hệ số hàng có biến mới tương ứng)
Xét hàng 0 ở bảng đơn hình xuất phát: hệ số tại cột quay là (-5), hệ số hàng có biến mới đã tính ở trên (7.20), cho nên các hệ số mới của hàng 0 sẽ là:
3 ( 5) * 0 5 ( 5) * 1 0 ( 5) * 0 0 ( 5) *1 0 ( 5) * 0 0 ( 5) * 6 2
3 0 0 5 0 30
2
⎧− − − − − − − − − − − − − − ⎫
⎨ ⎬
⎩ ⎭
⎧− ⎫
⎨ ⎬
⎩ ⎭
Xét hàng 1 ở bảng đơn hình xuất phát: vì hệ số tại cột quay là (0), cho nên các hệ số mới của hàng này sẽ không thay đổi.
Tương tự, xét hàng 3 ở bảng đơn hình xuất phát: hệ số tại cột quay là (2), hệ số hàng có biến mới đã tính ở trên (7.29), cho nên các hệ số mới của
hàng 3 sẽ là:
{ }
3 (2) * 0 2 (2) * 1 0 (2) * 0 0 (2) *1 1 (2) * 0 18 (2) * 6 2
3 0 0 1 1 6
⎧ − − − − − − ⎫
⎨ ⎬
⎩ ⎭
−
Và chúng ta có được bảng đơn hình tiếp theo dưới đây.
Bảng đơn hình tiếp theo
Các hệ số của biến Tên
hàng Tên
biến Phương
trình số Z X1 X2 X3 X4 X5
Giá trị vế phải
Hàng 0 Z 0 1 -3 -5 0 0 0 0
Hàng 1 X3 1 0 1 0 1 0 0 4
Hàng 2 X4 2 0 0 2 0 1 0 12
Hàng 3 X5 3 0 3 2 0 0 1 18
Hàng 0 Z 0 1 -3 0 0 5/2 0 30
Hàng 1 X3 1 0 1 0 1 0 0 4
Hàng 2 X2 2 0 0 1 0 1/2 0 6
Hàng 3 X5 3 0 3 0 0 -1 1 6
Sau khi có bảng đơn hình kế tiếp, quay lại bước 1 và chưa tìm được nghiệm tối ưu, chúng ta cần tiếp tục các bước kế tiếp và thu được kết quả của bảng đơn hình cuối cùng như sau.
Bảng đơn hình cuối
Các hệ số của biến Tên
hàng Tên
biến Phươn g
trình số Z X1 X2 X3 X4 X5
Giá trị vế phải
Hàng 0 Z 0 1 -3 -5 0 0 0 0
Hàng 1 X3 1 0 1 0 1 0 0 4
Hàng 2 X4 2 0 0 2 0 1 0 12
Hàng 3 X5 3 0 3 2 0 0 1 18
Hàng 0 Z 0 1 -3 0 0 5/2 0 30
Hàng 1 X3 1 0 1 0 1 0 0 4
Hàng 2 X2 2 0 0 1 0 1/2 0 6
Hàng 3 X5 3 0 3 0 0 -1 1 6
Hàng 0 Z 0 1 0 0 0 3/2 1 36
Hàng 1 X3 1 0 0 0 1 1/3 -1/3 2
Hàng 2 X2 2 0 0 1 0 1/2 0 6
Hàng 3 X1 3 0 1 0 0 -1/3 1/3 2
Với bảng đơn hình này, khi kiểm tra điều kiện tối ưu (bước 1), thấy thỏa mãn. Và chúng ta đã thu được nghiệm tối ưu trùng với kết quả của phương pháp hình học (Tâm, et al., 1998).
Z* = 36, còn X1* = 2 và X2* = 6.
4. Phương pháp số lớn M
Phương pháp số lớn hay phương pháp hai pha là kỹ thuật giải bài toán QHTT, trong nhiều trường hợp cho phép đơn giải hóa bài toán hơn phương pháp đơn hình.
Xét mô hình bài toán cơ bản (7.23) trong thí dụ 7.1.
1 2
1 2
1 2
1 2
Max Z 3X 5X
Thỏa mãn
X 4
X 6
3X 2X 18
X , X 0
= +
≤
≤
+ ≤
≥
Như đã nghiên cứu, mô hình này tương đương với mô hình bài toán ở dạng chính tắc (7.27).
1 2
1 3
2 4
1 2 5
1 2 3 4 5
Max ' Z ' Thỏa mãn :
(0) Z 3X 5X 0
(1) X X 4
(2) X X 12
(3) 3X 2X X 18
X , X , X , X , X 0
− − =
+ =
+ =
+ + =
≥
Với nhận xét là: nếu thêm vào phương trình số 0 một tích MX5, với M là số dương có giá trị rất lớn, còn X5là biến tự tạo có giá trị không âm thì phương trình này sẽ tương đương với phương trình:
1 2 5
(0 ') Z − 3X − 5X + MX = 0
khi giá trị X5 =0, và chỉ có tại đó mới có nghiệm tối ưu. Bằng kỹ thuật này, bây giờ chúng ta có mô hình của phương pháp số lớn M như sau:
1 2 5
1 3
2 4
1 2 5
1 2 3 4 5
Max ' Z ' Thỏa mãn :
(0) Z 3X 5X MX 0
(1) X X 4
(2) X X 12
(3) 3X 2X MX 18
X , X , X , X , X 0
− − + =
+ =
+ =
+ + =
≥
(7.30)
Bây giờ nếu sử dụng phương pháp đơn hình để giải mô hình (7.21) sẽ thu được cùng kết quả những khối lượng tính toán bảng đơn hình giảm đi đáng kể, nếu ở bảng xuất phát chúng ta tính hàng 0 mới theo quy tắc sau (pha thứ nhất):
Hệ số hàng mới = (Hệ số hàng cũ) + (-M) x (Các hệ số tương ứng của các ràng buộc chứa biến tự tạo) Với thí dụ trên ta có:
Hàng 0 cũ: { -3 -5 0 0 M 0 } Hàng 3x(-M): -M{ 3 2 0 0 1 18 } Hàng 0 mới: {(-3M-3) (-2M-5) 0 0 0 -18M}
Sau khi đã qua kỹ thuật xử lý trên, chúng ta lại quay trở lại với các quy tắc giải của phương pháp đơn hình (pha thứ hai). Trong thí dụ 7.2 ở phần sau sẽ minh họa chi tiết hơn về việc áp dụng phương pháp số lớn M để giải bài toán QHTT.
5. Bài toán đối ngẫu
Người ta đã chứng minh được rằng: bài toán QHTT dạng chuẩn hoàn toàn tương đương với một bài toán QHTT dạng "đối ngẫu" với bài toán gốc. Cùng với bài toán gốc, bài toán QHTT tạo thành một cặp bài toán với một số đặc điểm sau:
- Mỗi ràng buộc của bài toán này tương ứng với một biến của bài toán kia.
- Mỗi phần tử bên vế phải thuộc ràng buộc của bài toán này tương ứng với một
hệ số biến trong hàm mục tiêu của bài toán kia.
- Tiêu chuẩn tối ưu của bài toán này ngược lại với tiêu chuẩn tối ưu của bài toán
kia. Tức là mục tiêu bài toán này nếu là maximum thì bài toán kia là minimum
và ngược lại.
- Ràng buộc của bài toán maximum có dấu ≤, còn ở bài toán minimum là dấu
≥.
- Các biến chính của cả hai bài toán đêu không âm.
Như vậy bài toán QHTT gốc dạng chuẩn đã xét:
n
0 j j
j 1
Max x c x
= ∑= (j=1, 2,..., n)
Thỏa mãn các ràng buộc:
n
ij j i
j 1
a x b
= ≤
∑ (i=1, 2,..., m)
xj ≥ 0 (j=1, 2,..., n)
Sẽ tương đương với bài toán đối ngẫu tổng quát sau:
m
0 i i
i 1
Min y b y
= ∑= (i=1, 2,..., m)
Thỏa mãn các ràng buộc:
m
ij i j
i 1
a y c
= ≥
∑ (j=1, 2,..., n) yj ≥ 0 (i=1, 2,..., m)
Trong thực tế, đôi khi giải bài toán đối ngẫu lại dễ dàng và thuận tiện hơn bài toán gốc, ngoài ra còn có thể phân tích kỹ hơn những yếu tố ảnh hưởng tới hàm mục tiêu thực tế.
Trở lại mô hình ài toán QHTT trong thí dụ 7.1, dạng bài toán gốc và bài toán đối ngẫu được viết lại dưới đây.
Bài toán gốc: Bài toán đối ngẫu:
0 1 2 0 1 2 3
1 1 3
2 2 3
1 2
1 2 3 4 5 1 2 3
Max X Z 3X 5X Min Y 4Y 12Y 18Y
Thỏa mãn Thỏa mãn
X 4 Y 3Y 3
2X 12 2Y 2Y 5
3X 2X 18
X , X , X , X , X 0 Y , Y , Y 0
= = + = + +
≤ + ≥
≤ + ≥
+ ≤
≥ ≥
(7.31)
Để thấy rõ hơn tính chất thực tiễn của bài toán đối ngẫu cũng như cách giải bài toán này, chúng ta sẽ cùng nghiên cứu thí dụ 7.2.
Thí dụ 7.2: Trong hình 7.3, minh họa sơ đồ và số liệu của thí dụ. Mục tiêu của bài toán là tìm mức độ xử lý nước thải (tỷ lệ phần trăm xử lý lượng nước thải chảy vào sông) tại mặt cắt 1 và mặt cắt 2 của con sông H để đạt được nồng độ O2
yêu cầu tại mặt cắt 2 và mặt cắt 3 với tổng chi phí nhỏ nhất. Lưu ý rằng mức độ xử lý tối thiểu do yêu cầu về môi trường là 0,30 (30%), còn tối đa là 0,95 (95%) do yêu cầu về kỹ thuật xử lý nước thải (Nhật, et. al., 2001).
chi phí xử lý tỷ lệ tuyến tính với mức độ (về khối luợng) xử lý tại mc-1 lμ c1 (đơn vị tiền tệ) Tại mc-2 lμ c2 (đơn vị tiền tệ)
sông h nu
íc th
ải w1=
200m 3/s
nu íc
th
ải w2=
100m 3/s
mặt cắt 1
mặt cắt 2
mặt cắt 3 Mức độ cải thiện (aij) chất
luợng nuớc tại MC (mg/l) Khi 1 m3 nuớc thải
đuợc xử lý
tại mặt cắt mặt cắt 2 mặt cắt 1
mặt cắt 3
mặt cắt 2
0,0250 0,0125 0,0250
Hàm luợng Oxy (O2) MC (mg/l)
2 7
mặt cắt 3 Thành phần
tÝnh chÊt
3 mặt cắt 2 Hàm luợng O2 tự nhiên
Hàm luợng O2 yêu cầu 6
Hình 7.3: Sơ đồ và số liệu của thí dụ 7.2
Với thí dụ này, chúng ta đặt biến chính là tỷ lệ (mức độ) xử lý đối với nguồn nước thải đổ vào MC1 là X1 và MC2 là X2. Vì chi phí xử lý tỷ lệ tuyến tính với mức độ xử lý tại mỗi mặt cắt, cho nên hàm mục tiêu sẽ là:
1 1 2 2
Min Z = C X + C X
Nếu đặt nồng độ oxy tự nhiên tại mặt cắt i là hi còn nồng độ yêu cầu tại đó là Hi chúng ta sẽ có ràng buộc về yêu cầu nồng độ như sau:
2 12 1 1 2
3 13 1 1 23 2 2 3
h a W X H
h a W X a W X H
+ ≥
+ + ≥
Tất nhiên do biến chính là tỷ lệ phần trăm cần xử lý lượng nước thải chảy vào sông cho nên tồn tại ràng buộc không âm, nhưng trong thực tế của bài toán thì:
1 2
0, 30 ≤ X , X ≤ 0, 95
Thay các số liệu đầu bài vào ràng buộc bất phương trình sẽ có được dạng số của ràng buộc như sau:
1
1 2
3 0, 0250 x 200 X 7
2 0, 0125 x 200 X 0, 0250 x 100 X 6
+ ≥
+ + ≥
Tiếp tục rút gọn lại, cuối cùng thu được:
1
1 2
X 0, 8
X X 1, 6
≥
+ ≥
Giải bài toán bằng phương pháp đồ thị:
Tương tự như quá trình giải bằng đồ thị đối với thí dụ 7.1, hình 7.4 cho bức tranh rõ nét về quá trình cũng như kết quả của bài toán QHTT trong thí dụ 7.2.
X1 <= 0,95 X2 <= 0,95
X1
X2
Z ( kh
i C
1=C
2)
0 0,2 0,4 0,6
0,2 0,4 0,6 0,8 1,0
Miền giới hạn của biến chính
0,8 1,0
X1 >= 0,30
X2 >= 0,30 X1 >= 0,80
Z (kh
i C
1<C
2) Z (k
hi C
1>C
2)
X1
+X
2 >
= 1,6 C
1>C
2
C1<
C2 C1=C
2
lời giải của bμi toán 1. nÕu C1>c2: X1*=0,80; X2*=0,80 (®iÓm A) 2. nếu C1=C2: vô số nghiệm (đoạn ab) 3. nÕu c1<C2: X1*=0,95; X2*=0,65 (®iÓm B) a
b
Hình 7.4: Quá trình và lời giải thí dụ 7.2 bằng đồ thị Giải bài toán bằng phương pháp số lớn M:
Từ kết quả lời giải bằng hình học, chúng ta biết rằng, nếu C1 > C2 thì sẽ tồn tại một nghiệm duy nhất tại X1=0,8 và X2=0,8.
Do đó, để mô hình đầy đủ hơn, chúng ta giả thiết C1=10 và C2=6. Bây giờ mô hình gốc của bài toán sẽ là:
1 2
1
1 2
1 2
1 2
Min Z 10X 6X
Thỏa mãn : X 0, 8
X X 1, 6
X 0, 95 X 0, 95 X , X 0, 30
= +
≥
+ ≥
≤
≤
≥
(7.32)
Dưới dạng chuẩn, mô hình (7.32) trở thành: