<< Chapter < Page Chapter >> Page >

Ta được phương án tối ưu . Xong pha 1 . Chuyển sang pha 2.

Pha 2

Loại bỏ biến giả cải biên x6  0

Khởi tạo

A ¯ 0 = 1 3 2 3 0 1 2 3 1 3 2 3 1 0 1 3 b ¯ 0 = 10 9 7 9 alignl { stack { size 12{ {overline {A}} rSub { size 8{0} } = left [ matrix {{ {1} over {3} } {} # { {2} over {3} } {} # 0 {} # 1 {} # { {2} over {3} } {} ## { {1} over {3} } {} # { {2} over {3} } {} # 1 {} # 0 {} # - { {1} over {3} } {}} right ]" "} {} #{overline {b}} rSub { size 8{0} } = left [ matrix { { {"10"} over {9} } {} ##{ {7} over {9} } } right ]{} } } {}

c T = 3 4 1 0 0 size 12{c rSup { size 8{T} } = left [ matrix { " 3" {} # 4 {} # 1 {} # 0 {} # 0{}} right ]} {}

Bước lặp k=0

c B 0 size 12{c rSub { size 8{B rSub { size 6{0} } } } } {} i B 0 size 12{i rSub { size 8{B rSub { size 6{0} } } } } {} x1 x2 x3 x4 x5 b ¯ 0 size 12{ {overline {b}} rSub { size 8{0} } } {}
0 4 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {} 0 1 2 3 size 12{ { {2} over {3} } } {} 10 9 size 12{ { {"10"} over {9} } } {}
1 3 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {} 1 0 1 3 size 12{ - { {1} over {3} } } {} 7 9 size 12{ { {7} over {9} } } {}
cT 3 4 1 0 0 z(x0)
c ¯ 0 T size 12{ {overline {c}} rSub { size 8{0} } rSup { size 8{T} } } {} 8 3 size 12{ { {8} over {3} } } {} 10 3 size 12{ { {"10"} over {3} } } {} 0 0 1 3 size 12{ { {1} over {3} } } {} 7 9 size 12{ { {7} over {9} } } {}

Bước lặp k=1

c B 1 size 12{c rSub { size 8{B rSub { size 6{1} } } } } {} i B 1 size 12{i rSub { size 8{B rSub { size 6{1} } } } } {} x1 x2 x3 x4 x5 b ¯ 1 size 12{ {overline {b}} rSub { size 8{1} } } {}
0 4 0 0 -1 1 1 1 3 size 12{ { {1} over {3} } } {}
4 2 1 2 size 12{ { {1} over {2} } } {} 1 3 2 size 12{ { {3} over {2} } } {} 0 1 2 size 12{ - { {1} over {2} } } {} 7 6 size 12{ { {7} over {6} } } {}
cT 3 4 1 0 0 z(x1)
c ¯ 1 T size 12{ {overline {c}} rSub { size 8{1} } rSup { size 8{T} } } {} 1 0 -5 0 2 14 3 size 12{ { {"14"} over {3} } } {}

Bước lặp k=2

c B 2 size 12{c rSub { size 8{B rSub { size 6{2} } } } } {} i B 2 size 12{i rSub { size 8{B rSub { size 6{2} } } } } {} x1 x2 x3 x4 x5 b ¯ 2 size 12{ {overline {b}} rSub { size 8{2} } } {}
0 5 0 0 -1 1 1 1 3 size 12{ { {1} over {3} } } {}
4 2 1 2 size 12{ { {1} over {2} } } {} 1 1 1 2 size 12{ { {1} over {2} } } {} 0 4 3 size 12{ { {4} over {3} } } {}
cT 3 4 1 0 0 z(x2)
c ¯ 2 T size 12{ {overline {c}} rSub { size 8{2} } rSup { size 8{T} } } {} 1 0 -3 -2 0 16 3 size 12{ { {"16"} over {3} } } {}

Bước lặp k=3

c B 3 size 12{c rSub { size 8{B rSub { size 6{3} } } } } {} i B 3 size 12{i rSub { size 8{B rSub { size 6{3} } } } } {} x1 x2 x3 x4 x5 b ¯ 3 size 12{ {overline {b}} rSub { size 8{3} } } {}
0 5 0 0 -1 1 1 1 3 size 12{ { {1} over {3} } } {}
3 1 1 2 2 1 0 8 3 size 12{ { {8} over {3} } } {}
cT 3 4 1 0 0 z(x3)
c ¯ 3 T size 12{ {overline {c}} rSub { size 8{3} } rSup { size 8{T} } } {} 0 -2 -5 -2 0 8

Kết quả của bài toán đã cho :

. Phương án tối ưu  x 1 = 8 3 x 2 = 0 x 3 = 0 x 4 = 0 x 5 = 1 3 { { { { size 12{alignl { stack { left lbrace x rSub { size 8{1} } = { {8} over {3} } {} #right none left lbrace x rSub { size 8{2} } =0 {} # right none left lbrace x rSub { size 8{3} } =0 {} #right none left lbrace x rSub { size 8{4} } =0 {} # right none left lbrace x rSub { size 8{5} } = { {1} over {3} } {} #right no } } lbrace } {}

. Giá trị hàm mục tiêu  z(x)=z(x3)= 8

Phương pháp m vô cùng lớn

Phương pháp M vô cùng lớn ( M là số vô cùng lớn ) tương tự như phương pháp hai pha, ngoại trừ ở pha 1 hàm mục tiêu cải biên có dạng sau đây cho bài toán max/min

max [z(x) - M*( tổng các biến giả cải biên) ]

min [z(x) + M*( tổng các biến giả cải biên) ]

Bằng phương pháp này, trong quá trình tối ưu, các biến giả cải biên sẽ được loại dần ra khỏi ma trận cơ sở : tất cả đều bằng 0. Nếu trong quá trình tìm phương án tối ưu mà không loại bỏ được các biến giả cải biên ra khỏi cơ sở thì bài toán vô nghiệm.

So với phương pháp hai pha thì phương pháp này tránh được việc phải cập nhật lại dữ liệu cho bài toán gốc nhưng không tiện lợi bằng trong lập trình ứng dụng.

Ví dụ : Xét bài toán tương tự như trên 

max z ( x ) = 3x 1 + 4x 2 + x 3 x 1 + 2x 2 + 2x 3 + x 4 = 8 3 x 1 + 2x 2 + 3x 3 x 5 = 7 3 x j 0 ( j = 1,2,3,4,5 ) { alignl { stack { size 12{"max"" "z \( x \) =3x rSub { size 8{1} } +4x rSub { size 8{2} } +x rSub { size 8{3} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} } +2x rSub { size 8{3} } +x rSub { size 8{4} } = { {8} over {3} } {} #right none left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} } +3x rSub { size 8{3} } - x rSub { size 8{5} } = { {7} over {3} } {} # right no } } lbrace {} #x rSub { size 8{j} }>= 0" " \( j="1,2,3,4,5" \) {} } } {}

Thêm biến giả cải biên x6  0 vào ràng buộc thứ hai đồng thời cải biên hàm mục tiêu theo như trên ta được :

max w ( x ) = 3x 1 + 4x 2 + x 3 Mx 6 x 1 + 2x 2 + 2x 3 + x 4 = 8 3 x 1 + 2x 2 + 3x 3 x 5 + x 6 = 7 3 x j 0 ( j = 1,2,3,4,5,6 ) { alignl { stack { size 12{"max "w \( x \) =3x rSub { size 8{1} } +4x rSub { size 8{2} } +x rSub { size 8{3} } - ital "Mx" rSub { size 8{6} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} } +2x rSub { size 8{3} } +x rSub { size 8{4} } = { {8} over {3} } {} #right none left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} } +3x rSub { size 8{3} } - x rSub { size 8{5} } +x rSub { size 8{6} } = { {7} over {3} } {} # right no } } lbrace {} #x rSub { size 8{j} }>= 0" " \( j="1,2,3,4,5,6" \) {} } } {}

Tìm phương án tối ưu cho bài toán cải biên này bằng phương pháp đơn hình cải tiến

Khởi tạo

A ¯ 0 = 1 2 2 1 0 0 1 2 3 0 1 1 b ¯ 0 = 8 3 7 3 size 12{ {overline {A}} rSub { size 8{0} } = left [ matrix { 1 {} # 2 {} # 2 {} # 1 {} # 0 {} # 0 {} ##1 {} # 2 {} # 3 {} # 0 {} # - 1 {} # 1{} } right ]" " {overline {b}} rSub { size 8{0} } = left [ matrix { { {8} over {3} } {} ##{ {7} over {3} } } right ]} {} c T = 3 4 1 0 0 M size 12{c rSup { size 8{T} } = left [ matrix { 3 {} # 4 {} # 1 {} # 0 {} # 0 {} # - M{}} right ]} {}

Bước lặp k=0

c B 0 size 12{c rSub { size 8{B rSub { size 6{0} } } } } {} i B 0 size 12{i rSub { size 8{B rSub { size 6{0} } } } } {} x 1 size 12{x rSub { size 8{1} } } {} x 2 size 12{x rSub { size 8{2} } } {} x 3 size 12{x rSub { size 8{3} } } {} x 4 size 12{x rSub { size 8{4} } } {} x 5 size 12{x rSub { size 8{5} } } {} x 6 size 12{x rSub { size 8{6} } } {} b ¯ 0 size 12{ {overline {b}} rSub { size 8{0} } } {}
0 4 1 2 2 1 0 0 8 3 size 12{ { {8} over {3} } } {}
-M 6 1 2 3 0 -1 1 7 3 size 12{ { {7} over {3} } } {}
cT 3 4 1 0 0 -M w(x0)
c ¯ 0 T size 12{ {overline {c}} rSub { size 8{0} } rSup { size 8{T} } } {} 3+M 4+2M 1+3M 0 -M 0 7M 3 size 12{ - { {7M} over {3} } } {}

Bước lặp k= 1

c B 1 size 12{c rSub { size 8{B rSub { size 6{1} } } } } {} i B 1 size 12{i rSub { size 8{B rSub { size 6{1} } } } } {} x 1 size 12{x rSub { size 8{1} } } {} x 2 size 12{x rSub { size 8{2} } } {} x 3 size 12{x rSub { size 8{3} } } {} x 4 size 12{x rSub { size 8{4} } } {} x 5 size 12{x rSub { size 8{5} } } {} x 6 size 12{x rSub { size 8{6} } } {} b ¯ 1 size 12{ {overline {b}} rSub { size 8{1} } } {}
0 4 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {} 0 1 2 3 size 12{ { {2} over {3} } } {} 2 3 size 12{ - { {2} over {3} } } {} 10 9 size 12{ { {"10"} over {9} } } {}
1 3 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {} 1 0 1 3 size 12{ - { {1} over {3} } } {} 1 3 size 12{ { {1} over {3} } } {} 7 9 size 12{ { {7} over {9} } } {}
cT 3 4 1 0 0 -M w(x1)
c ¯ 1 T size 12{ {overline {c}} rSub { size 8{1} } rSup { size 8{T} } } {} 8 3 size 12{ { {8} over {3} } } {} 10 3 size 12{ { {"10"} over {3} } } {} 0 0 1 3 size 12{ { {1} over {3} } } {} 5 3 M size 12{ - { {5} over {3} } - M} {} 7 9 size 12{ { {7} over {9} } } {}

Do x6 = 0 (vì ngoài cơ sở) nên bị loại ra khỏi bảng và ta tiếp tục tìm phương án tối ưu cho bài toán gốc đã cho có phương án cơ sở khả thi được khởi tạo như sau :

c B 0 size 12{c rSub { size 8{B rSub { size 6{0} } } } } {} i B 1 size 12{i rSub { size 8{B rSub { size 6{1} } } } } {} x 1 size 12{x rSub { size 8{1} } } {} x 2 size 12{x rSub { size 8{2} } } {} x 3 size 12{x rSub { size 8{3} } } {} x 4 size 12{x rSub { size 8{4} } } {} x 5 size 12{x rSub { size 8{5} } } {} b ¯ 0 size 12{ {overline {b}} rSub { size 8{0} } } {}
0 4 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {} 0 1 2 3 size 12{ { {2} over {3} } } {} 10 9 size 12{ { {"10"} over {9} } } {}
1 3 1 3 size 12{ { {1} over {3} } } {} 2 3 size 12{ { {2} over {3} } } {} 1 0 1 3 size 12{ - { {1} over {3} } } {} 7 9 size 12{ { {7} over {9} } } {}
cT 3 4 1 0 0 z(x0)
c ¯ 0 T size 12{ {overline {c}} rSub { size 8{0} } rSup { size 8{T} } } {} 8 3 size 12{ { {8} over {3} } } {} 10 3 size 12{ { {"10"} over {3} } } {} 0 0 1 3 size 12{ { {1} over {3} } } {} 7 9 size 12{ { {7} over {9} } } {}

Các bước tiếp theo được thực hiện giống như phương pháp hai pha.

Quy hoạch tuyến tính suy biến

Khi thực hiện thuật toán đơn hình trường hợp bất thường có thể xảy ra là khi xác định biến ra thì tồn tại tỷ số b i a ik = 0 size 12{ { {b rSub { size 8{i} } } over {a rSub { size 8{ ital "ik"} } } } =0} {} , tức là tồn tại bi=0, hay không có tỷ số nào dương thật sự. Người ta xem đây là trường hợp suy biến. Khi một bảng đơn hình rơi vào tình trạng suy biến thì có thể gây khó khăn mà cũng có thể không khi ta tiếp tục thực hiện thuật toán đơn hình.

Các ví dụ về quy hoạch tuyến tính suy biến

Ví dụ 1 : xét quy hoạch tuyến tính :

min z ( x ) = 7 + x 1 x 2 x 1 2x 2 2 3x 1 6 2x 1 0 x 1 , x 2 0 { { alignl { stack { size 12{"min"" z" \( x \) =7+x rSub { size 8{1} } - x rSub { size 8{2} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } - 2x rSub { size 8{2} }<= 2 {} # right none left lbrace - 3x rSub { size 8{1} }<= 6 {} # right none left lbrace - 2x rSub { size 8{1} }<= 0 {} # right no } } lbrace {} #x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} } } {}

Đưa bài toán về dạng chuẩn :

min z ( x ) = 7 + x 1 x 2 x 1 2x 2 + x 3 = 2 3x 1 + x 4 = 6 2x 1 + x 5 = 0 x 1 , x 2 0 { { alignl { stack { size 12{"min"" z" \( x \) =7+x rSub { size 8{1} } - x rSub { size 8{2} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } - 2x rSub { size 8{2} } +x rSub { size 8{3} } =2 {} #right none left lbrace - 3x rSub { size 8{1} } +x rSub { size 8{4} } =6 {} # right none left lbrace - 2x rSub { size 8{1} } +x rSub { size 8{5} } =0 {} #right no } } lbrace {} # x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} } } {}

với ma trận hệ số là :

x1 x2 x3 x4 x5 b
1 -2 1 0 0 2
-3 0 0 1 0 6
-2 0 0 0 1 0

có chứa ma trận đơn vị. Áp dụng thuật toán đơn hình cải tiến ta được :

cB iB x1 x2 x3 x4 x5 b
0 3 1 -2 1 0 0 2
0 4 -3 0 0 1 0 6
0 5 -2 0 0 0 1 0
{} {} c T size 12{c rSup { size 8{T} } } {} 1 -1 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 1 -1 0 0 0
w=7

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Quy hoạch tuyến tính. OpenStax CNX. Aug 08, 2009 Download for free at http://cnx.org/content/col10903/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Quy hoạch tuyến tính' conversation and receive update notifications?

Ask