Thuật toán đơn hình được trình bày trong mục trước có thể áp dụng trực tiếp cho các bài toán mà các biến cơ sở ban đầu có sẵn ngay sau bước khởi tạo. Đây là trường hợp nếu tất cả các ràng buộc trong mô hình là , các biến ảo có thể được thêm vào để làm cho chúng trở thành đẳng thức. Ma trận các hệ số công nghệ của các biến ảo tại bước khởi tạo ban đầu có dạng một ma trận đơn vị. Tuy nhiên, sẽ cần đến một số sự hiệu chỉnh công thức mô hình cho các bài toán mà không thể dễ dàng tìm thấy nghiệm khả thi cơ
sở bắt đầu. Điều này thường xảy ra với những mô hình có các các ràng buộc thuộc loại hoặc =. Bằng việc đơn giản là trừ đi biến ảo, s3, từ vế trái của dạng chính tắc của các ràng buộc, dẫn tới
2x1 - x2 - s3 = 0
Ma trận kết quả cùng với các biến ảo (s1, s2, và s3) là s1 s s2 3
1 0 0 0 1 0 0 0 -1
Đây không phải là một ma trận đơn vị. Vì vậy, s3 không thể được sử dụng như một trong các biến cơ sở bắt đầu. Trong minh họa trước về phương pháp đơn hình, cả hai vế của ràng buộc thứ ba được nhân với -1 tạo cho nó một ràng buộc vì thế hệ số công nghệ gắn liền với s3 là +1. Điều này là có thể được phép bởi vì vế phải của ràng buộc thứ ba là bằng 0 và sự vận dụng về dấu không vi phạm yêu cầu của vế phải không âm trong dạng chính tắc. Tuy nhiên, nếu vế phải của ràng buộc thứ ba là dương, như là hai ràng buộc kia, thay đổi chiều của bất đẳng thức sẽ vi phạm yêu cầu không
âm của dạng chính tắc.
Phương pháp biến nhân tạo đơn giản là một thủ thuật toán học mà thông qua sự bổ xung các biến (gọi là biến nhân tạo) để có thể giải một mô
hình quy hoạch tuyến tính sử dụng thuật toán đơn hình chính tắc được trình bày ở trên. Về cơ bản, các biến nhân tạo được sử dụng trong hai trường hợp:
(a) với các ràng buộc thuộc loại , các ràng buộc được viết thành:
1 n
ij j i i i
j
a x s r b
(3.4.1) còn (b) với các ràng buộc thuộc loại “=”, các ràng buộc được viết thành
1 n
ij j i i
j
a x r b
(3.4.2) trong đó ri là biến nhân tạo không âm.
Chú ý rằng hệ số đi kèm với các biến nhân tạo trong các ràng buộc luôn luôn bằng +1. Mục đích chính của việc đưa ra các biến nhân tạo là để sử dụng chúng như các biến khả thi cơ sở ban đầu để áp ụng thuật toán đơn hình chính tắc. Một lý do khác đưa ra các biến nhân tạo là những sự bổ xung của các biến này có thể gây nên một sự vi phạm của ràng buộc tương ứng, trừ khi chúng bằng 0, Các biến nhân tạo có thể được sử dụng như
những chỉ số để nói lên liệu mô hình đã xây dựng có một nghiệm khả thi hay không. Nếu tất cả các biến nhân tạo trong bài toán được chuyển tới không cơ sở tại mực 0 khi thuật toán đơn hình kết thúc, bài toán có ít nhất một nghiệm khả thi. Mặt khác, nếu ít nhất một biến nhân tạo vẫn còn trong các biến cơ sở khi đạt tới tối ưu, thì không gian nghiệm của bài toán không tồn tại và bài toán là vô nghiệm.
Sử dụng các biến nhân tạo như nghiệm cơ sở ban đầu trong bước lặp đơn hình, ta cần nhận rõ rằng nghiệm bắt đầu là không khả thi cho các ràng buộc gốc của bài toán. Để tìm nghiệm khả thi tối ưu cho bài toán gốc, tất các các biến nhân tạo phải được chuyển về 0, nếu có thể. Có nhiều cách để làm như vậy. Các mục con sau trình bày hai phương pháp được sử dụng phổ biến trong việc giải một mô hình quy hoạch phi tuyến khi các biến nhân tạo
được đưa ra. Sẽ vẫn sử dụng ví dụ sản xuất, xử lí rác thải để minh họa những phương pháp luận này.
3.4.1. Phương pháp đánh thuế (phương pháp M lớn)
Không vận dụng dấu của ràng buộc thứ ba của ví dụ sản xuất - xử lí rác thải, tập hợp ràng buộc có thể được viết dưới dạng chính tắc:
1 2 1
1 2 2
1 2 3 3
2 10
.4 .8 4
2 0
x x s
x x s
x x s r
(tất cả x1, x2, s1, s2, s3 và r3 là không âm)
trong đó, r3 là một biến nhân tạo mà sẽ được sử dụng, cùng với s1 và s2, như
các biến cơ sở bắt đầu.
Như đã đề cập ở trên, ta nên cố gắng khử tất cả các biến nhân tạo từ tập hợp biến cơ sở. Với một bài toán cực đại hóa, điều này có thể được làm bằng việc chỉ định một hệ số âm lớn, gọi là -M, cho các biến trong hàm mục tiêu.
Max 0
1 1
n m
j j i
j i
x c x Mr
Vì bài toán này thuộc loại cực đại hóa, sự liên quan của một hệ số âm lớn với các biến nhân tạo buộc một “bất lợi” cao cho sự tồn tại của các biến nhân tạo dương bất kỳ. Do đó, trong tiến trình của sự cực đại hóa, thuật toán này sẽ tự động cố tránh sử dụng biến nhân tạo bất kỳ làm biến cơ sở.
Bằng biểu hiện tương tự, nếu bài toán thuộc loại cực tiểu hóa, một hệ số dương lớn (+M) sẽ được chỉ định cho mỗi biến nhân tạo trong hàm mục tiêu
Min 0
1 1
n m
j j i
j i
x c x Mr
Số M lớn này có thể được xem như bất lợi đơn vị cho bất kỳ sự vi phạm nào của các ràng buộc mô hình. Hàm mục tiêu cho ví dụ này có thể được thành tạo là
Max x05x1x20s10s20s3Mr3 Có hai hạn chế cơ bản của phương pháp số lớn M. Đó là:
Bước cuối cùng phải được tiến hành trước khi phát hiện ra rằng bài toán không có nghiệm khả thi, tức là, một số biến nhân tạo là dương.
Trong việc thực thi tính toán của phương pháp số lớn M, ta phải giả sử một giá trị số của M. Làm như vậy, các lỗi tính toán và tính bất ổn định có thể xuất hiện trong tiến trình lặp chủ yếu do một bài toán xác định tỷ lệ.
Do đó, phương pháp thứ hai, là phương pháp hai pha, phá vỡ hai trở ngại của phương pháp số lớn M được sử dụng trong các gói phần mềm tính toán quy hoạch tuyến tính.
3.4.2. Phương pháp hai pha
Phương pháp này lấy tên từ thực tế rằng những tính toán đi theo hai pha.
Pha thứ nhất của tính toán đơn giản là cố điều chỉnh các biến nhân tạo trong nghiệm sử dụng phương pháp đơn hình vì vậy tạo nên một nghiệm bắt đầu, không có các biến nhân tạo, cho pha thứ hai. Pha thứ hai đơn thuần chỉ chuyển dịch tới nghiệm tối ưu sử dụng thuật toán đơn hình.
Trong tính toán Pha I, mô hình được giải có một hàm mục tiêu được diễn tả bằng:
Min 0
1 K
k k
r r
(3.4.3) trong đó K là tổng số biến nhân tạo trong mô hình, với giả thiết là các ràng buộc ở dạng chính tắc sau khi thêm các biến nhân tạo cần thiết. Hàm mục tiêu của pha này là như nhau cho cả bài toán cực đại hóa và cực tiểu hóa. Vì
tất các các biến nhân tạo là không âm, rõ ràng là r0 có thể đạt được nhỏ nhất là bằng 0 mà chỉ xảy ra khi tất các biến nhân tạo đều bằng 0, Trong trường hợp mà giá trị của r0 khác 0 khi sự tối ưu được đạt tới, bài toán không có miền nghiệm.
Dựa trên sự hoàn thành Pha I, sự tối ưu hóa Pha II tiếp tục, miễn là tất cả
các biến nhân tạo đều trở thành các biến không cơ sở ở mức 0, Trong các
tính toán Pha II, bảng tính toán cuối cùng của Pha I được hiệu chỉnh bằng việc hạ thấp các cột gắn liền với các biến nhân tạo. Hơn nữa, dòng r0 của bảng được thay thế bằng dòng x0 của hàm mục tiêu gốc. Trước khi kiểm tra
điều kiện tối ưu, ta phải kiểm tra bảng đó thỏa mãn yêu cầu rằng dòng x0 chỉ có thể là một hàm của các biến không cơ sở hay chưa. Nếu điều kiện này không thỏa mãn, các phép tính dòng phải được thực hiện để thỏa mãn yêu cầu. Khi điều kiện này được thỏa mãn, thuật toán đơn hình được áp dụng để giải tối ưu hóa bài toán.
Ví dụ 3.4.1. Giải bài toán sản xuất, xử lí rác thải sử dụng phương pháp hai pha.
Lời giải. Việc thiết lập Pha I của bài toán sản xuất, xử lí rác thải có thể được biểu diễn là:
Min r0 = r3
với ràng buộc là:
1 2 1
1 2 2
1 2 3 3
2 10
0, 4 0,8 4
2 0
x x s
x x s
x x s r
(Tất cả x1, x2, s1, s2, s3 và r3 là không âm)
Bảng đơn hình tương ứng với sự thiết lập mô hình này được chỉ ra trong bảng 3.4.1(a). Một lần nữa, trước khi đi tiếp với bước lặp đơn hình, dòng hàm mục tiêu trong bảng đơn hình phải được biểu thị chỉ bằng một hàm của các biến không cơ sở x1, x2 và s3. Điều này có thể được hoàn thành bằng việc thêm dòng r3 cho dòng r0, Bảng kết quả được trình bày trong bảng 3.4.1(b).
Mô hình pha I bây giờ có thể được tối ưu hóa bằng việc chọn x1 làm biến vào theo điều kiện tối ưu cho các bài toán cực tiểu hóa. Việc lựa chọn một biến ra cũng giống như trước đây theo điều kiện khả
thi. Sau một bước lặp, nghiệm tối ưu cho pha I của ví dụ này được đạt tới dựa trên bảng 3.4.1(c). Dựa vào bảng cuối cùng của thủ tục pha I, bảng bắt đầu của pha II được trình bày trong bảng 3.4.1(d).
Chú ý rằng bài toán cực đại hóa gốc được xem xét trong các tính toán pha II.
Chú ý rằng bảng 3.4.1(d) không thỏa mãn yêu cầu rằng dòng x0 chỉ có thể là một hàm của các biến không cơ sở. Biến cơ sở x1 có hệ số khác 0 trong dòng x0, Một lần nữa, các phép tính toán dòng lại
được áp dụng để khử hệ số -5 của x1 trong dòng x0, Sau các phép tính dòng này, bảng đơn hình kết quả có thể được viết lại như bảng 3.4.1(e). Rõ ràng là điều kiện tối ưu không được thỏa mãn bởi vì
các hệ số trong hàm mục tiêu của các biến không cơ sở x2 và s3 là âm. Sau một bước lặp nữa, thì đạt
được nghiệm tối ưu với bảng cuối cùng được chỉ ra trong bảng 3.4.1(g).
3.5. Giải thích thuật toán bảng đơn hình
Từ bảng đơn hình cuối cùng ta có thể nhận được thông tin liên quan tới nghiệm tối ưu và giá trị hàm mục tiêu tương ứng. Có thông tin nào khác
được cung cấp bởi bảng đơn hình này không? Câu trả lời là có. Sẽ rất quan trọng để có thể giải thích thông tin chứa trong bảng đơn hình bởi vì, trong thực tế, mặt tính toán của một thuật toán đơn hình được thực hiện bằng các máy tính. Ta nên biết giải thích nghiệm cuối cùng như thế nào và có thể thực hiện phân tích độ nhạy như thế nào. Xét bảng cuối cùng, đó là, Bảng 3.4.1(g), của bài toán sản xuất, xử lí rác thải được giải bằng phương pháp hai pha trong ví dụ 3.4.1. Như được trình bày trong các mục con sau đây, ta có thể nhận được nhiều thông tin hữu ích từ bảng này.
3.5.1. Nghiệm tối ưu
Các biến cơ sở tối ưu được liệt kê trong cột đầu tiên của bảng cuối cùng và các giá trị biến tương ứng được đưa trong cột cuối cùng của bảng. Giá trị hàm mục tiêu tối ưu được đưa trong cột nghiệm cùng với dòng hàm mục tiêu. Ví dụ, nghiệm tối ưu từ bảng 3.4.1(g) là
s x x*3, 2*, 1*10, 2, 6 víi x*0 28
Tất cả các biến quyết định khác đều bằng 0 bởi vì chúng là các biến không cơ sở. Trong việc tìm nghiệm, các giá trị của các biến ảo khả thi tối
ưu được bỏ qua vì chúng không cho bất kỳ thông tin gi liên quan đến tiến trình tối ưu của hành động được xác định bằng phân tích này.
3.5.2. Trạng thái của các tài nguyên
Trong nhiều mô hình quy hoạch phi tuyến, các hệ số RHS đặc trưng cho sự giới hạn về các tài nguyên hay có thể được xem như vậy, đặc biệt là với các ràng buộc loại . Mặc dù các giá trị của các biến ảo không mang ý nghĩa trực tiếp về mức tối ưu của các hoạt động cho bài toán, trạng thái của chúng thực sự biểu lộ trạng thái của tài nguyên hay các ràng buộc tại nghiệm tối ưu hiện thời.
Nếu một biến ảo nằm trong tập hợp nghiệm khả thi cơ sở, ràng buộc tương ứng là không chặt và tài nguyên tương ứng là dồi dào. Nói cách khác, ràng buộc là chặt và tài nguyên là khan hiếm. Xem bảng 3.4.1(g) trong Ví dụ 3.4.1, chú ý rằng s1 và s2 là không cơ sở còn s3 là cơ sở. Điều này ám chỉ rằng các ràng buộc 1 và 2 là chặt và “tài nguyên” sẵn có tương ứng được sử dụng hết . Để đặt sự thể hiện này trong nội dung bài toán, khả
năng tổng cộng của nhà máy xử lí và sự hạn chế của khả năng cho phép không xử lí rác thải đều tận dụng hết mức ở quyết dịnh tối ưu. Vì LHS của ràng buộc thứ 3 biểu thị lượng rác thải được xử lí, biến ảo s3* 10 thực sự là lượng rác thải tối ưu để được xử lí.
Bảng 3.4.1
Bài toán nhà máy xử lí chất thải giải bằng phương pháp hai pha Pha 1
Biến cơ sở r0 X1 x2 x3 s1 s2 r3 Sol’n
r0 1 0 0 0 0 0 -1 0
s1 0 2 -1 0 1 0 0 10
s2 0 0,4 0,8 0 0 1 0 4
(a)
r3 0 2 -1 -1 0 0 1 0
r0 1 2 -1 -1 0 0 0 0
s1 0 2 -1 0 1 0 0 10
(b)
s2 0 0,4 0,8 0 0 1 0 4
r3 0 -1 -1 0 0 1 0
r0 1 0 0 0 0 0 -1 0
s1 0 0 0 1 1 0 -1 10
s2 0 0 1 0,2 0 1 -0,2 4
(c)
x1 0 1 -0,5 -0,5 0 0 0,5 0
Pha 2
x0 1 -5 1 0 0 0 0
s1 0 0 0 1 1 0 10
s2 0 0 1 0,2 0 1 4
(d)
x1 0 1 -0,5 -0,5 0 0 0
x0 1 0 -1,5 -2,5 0 0 0
s1 0 0 0 1 0 10
s2 0 0 1 0,2 0 1 4
(e)
x1 0 1 -0,5 -0,5 0 0 0
x0 1 0 -1,5 0 2,5 0 25
s3 0 0 0 1 1 1 10
s2 0 0 0 -0,2 1 2
(f)
x1 0 1 -0,5 0 0,5 0 5
x0 1 0 0 0 2,2 1,5 28
s3 0 0 0 1 1 0 10
x2 0 0 1 0 -0,2 1 2
(g)
x1 0 1 0 0 0,4 0,5 6
3.5.3. Giá trị trên một đơn vị của các tài nguyên (giá mờ)
Kiến thức về giá trị trên một đơn vị của một tài nguyên làm cho ta có thể dành ưu tiên những sự phân bổ vốn trong tương lai cho các nguồn tài nguyên khác nhau. Về mặt toán học, giá trị trên một đơn vị của các nguồn tài nguyên (tức là, các giá trị RHS) có thể được biểu diễn bằng x0/bi với i
= 1, 2, ..., m. Với các ràng buộc không chặt mà tương ứng với các nguồn tài nguyên dồi dào, việc tăng hay giảm một đơn vị sẽ không có ảnh hưởng tới quyết định phân bổ tối ưu hiện tại. Với các ràng buộc chặt mà các nguồn tài nguyên tương ứng của nó là khan hiếm, giá trị trên một đơn vị của tài nguyên sẽ không còn bằng 0, Xem lại hình 3.2.1, bằng việc tăng khả năng của nhà máy xử lí chất thải b1 hay hạn chế khả năng cho phép của rác thải không được xử lí trong đường nước b2, vùng miền nghiệm sẽ được mở rộng về bên phải. Giá trị hàm mục tiêu tối ưu tương ứng cũng sẽ tăng theo.
Tương tự, nếu b1 hay b2 bị giảm, giá trị x0 tối ưu cũng sẽ giảm. Vì vậy, bất kỳ hiệu chỉnh các hệ số RHS nào của các ràng buộc chặt cũng sẽ dẫn tới
2
1
1
những thay đổi trong giá trị hàm mục tiêu tối ưu, để tốt hơn hoặc tồi tệ hơn.. Điều này chứng tỏ rằng giá trị trên một đơn vị của một tài nguyên cho một ràng buộc chặt là khác 0, Các giá trị của giá trị trên một đơn vị của một tài nguyên được cho trước trong bảng cuối cùng dưới các biến khả thi cơ sở bắt đầu. Trong ví dụ đã xem xét, các biến cơ sở bắt đầu là s1, s2, và r3 và các hệ số tương ứng trong dòng x0 là 2,2, 1,5, và 0 (vì r3 trong pha II có thể
được xem như một biến không cơ sở). Do đó, giá trị trên một đơn vị của tài nguyên cho các ràng buộc 1, 2, và 3 trong ví dụ là:
0 0 0
1 2 3
, , 2.2,1.5, 0
x x x
b b b
Các giá trị này có ý nghĩa là một sự tăng lên 1 đơn vị của khả năng xử lí b1 sẽ tăng giá trị x0 tối ưu lên 2,2 nghìn đô la còn một sự tăng một đơn vị của giới hạn có thể cho phép của rác không được xử lí sẽ tăng giá trị của x0 lên 1,5 ngàn đô la. Với sự hiểu biết này, thông tin về giá trị trên một đơn vị của một tài nguyên có thể được sử dụng để ưu tiên sự phân bổ các nguồn vốn bổ sung cho việc mở rộng hoạt động.