<< Chapter < Page Chapter >> Page >

Đây là trường hợp suy biến, biến vào là x2, nó được tăng lên đến mức vẫn thỏa những điều kiện về dấu của các biến trong cơ sở x3, x3, x5 . Đó là :

x 3 = 2 + 2x 2 0 x 4 = 6 + 0x 2 0 x 3 = 0 + 0x 2 0 { { size 12{alignl { stack { left lbrace x rSub { size 8{3} } =2+2x rSub { size 8{2} }>= 0 {} # right none left lbrace x rSub { size 8{4} } =6+0x rSub { size 8{2} }>= 0 {} # right none left lbrace x rSub { size 8{3} } =0+0x rSub { size 8{2} }>= 0 {} # right no } } lbrace } {} x 2 2 2 x 2 0 x 2 0 { { size 12{alignl { stack { left lbrace x rSub { size 8{2} }>= - { {2} over {2} } {} # right none left lbrace forall x rSub { size 8{2} }>= 0 {} # right none left lbrace forall x rSub { size 8{2} }>= 0 {} # right no } } lbrace } {}

Như vậy x2 có thể lớn tùy ý nên hàm mục tiêu không bị giới nội. Vậy bài toán không có phương án tối ưu. Trường hợp này ở bảng đơn hình không có tỷ số nào dương thật sự để xác định biến ra.

Ví dụ 2 : 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
cB iB x1 x2 x3 x4 x5 b
-1 2 1 2 size 12{ { {1} over {2} } } {} 1 1 2 size 12{ { {1} over {2} } } {} 0 0 1
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} } } {} 3 2 size 12{ { {3} over {2} } } {} 0 1 2 size 12{ { {1} over {2} } } {} 0 0
w=6

Đây là bảng đơn hình tối ưu.

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

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

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

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

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

x1 x2 x3 x4 x5 b
1 2 size 12{ { {1} over {2} } } {} 0 1 2 size 12{ { {1} over {2} } } {} 1 0 1
-1 1 1 0 1 0

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

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

x2 vào , x5 ra

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

x1 vào , x4 ra

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

Đây là bảng đơn hình tối ưu

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

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

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

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

với ma trận hệ số

x1 x2 x3 x4 x5 x6 x7 b
0,5 -5,5 -2,5 9 1 0 0 0
0,5 -1,5 -0,5 1 0 1 0 0
1 0 0 0 0 0 1 1

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

cB iB x1 x2 x3 x4 x5 x6 x7 b
0 5 0,5 -5,5 -2,5 9 1 0 0 0
0 6 0,5 -1,5 -0,5 1 0 1 0 0
0 7 1 0 0 0 0 0 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} -10 57 9 24 0 0 0
w=0

x1 vào , x5 ra

cB iB x1 x2 x3 x4 x5 x6 x7 b
-10 1 1 -11 -5 18 2 0 0 0
0 6 0 4 2 -8 -1 1 0 0
0 7 0 11 5 -18 -2 0 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 0 -53 -41 204 20 10 0
w=0

x2 vào , x6 ra

cB iB x1 x2 x3 x4 x5 x6 x7 b
-10 1 1 0 0,5 -4 -0,75 2,75 0 0
57 2 0 1 0,5 -2 -0,25 0,25 0 0
0 7 0 0 -0,5 4 0,75 -2,75 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 0 0 -14,5 98 6,75 13,25 0
w=0

x3 vào , x1 ra

cB iB x1 x2 x3 x4 x5 x6 x7 b
9 3 2 0 1 -8 -1,5 5,5 0 0
57 2 -1 1 0 2 0,5 -2,5 0 0
0 7 1 0 0 0 0 0 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 29 0 0 -18 -15 93 0
w=0

x4 vào , x2 ra

cB iB x1 x2 x3 x4 x5 x6 x7 b
9 3 -2 4 1 0 0,5 -4,5 0 0
24 4 -0,5 0,5 0 1 0,25 -1,25 0 0
0 7 1 0 0 0 0 0 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 20 9 0 0 -10,5 70,5 0
w=0

x5 vào , x3 ra

cB iB x1 x2 x3 x4 x5 x6 x7 b
0 5 -4 8 2 0 1 -9 0 0
24 4 0,5 -1,5 -0,5 1 0 1 0 0
0 7 1 0 0 0 0 0 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} -22 93 21 0 0 -24 0
w=0

x6 vào , x4 ra

cB iB x1 x2 x3 x4 x5 x6 x7 b
0 5 0,5 -5,5 -2,5 9 1 0 0 0
0 6 0,5 -1,5 -0,5 1 0 1 0 0
0 7 1 0 0 0 0 0 1 1
c T size 12{c rSup { size 8{T} } } {} -10 57 9 24 0 0 0
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} -10 57 9 24 0 0 0
w=0

Bảng đơn hình hiện thời giống với bảng đơn hình xuất phát : đây là hiện tượng xoay vòng .

Xử lý trường hợp suy biến

Theo các ví dụ trên, trong trường hợp quy hoạch tuyến tính suy biến thì sau một số lần lặp có thể phương án nhận được vẫn như cũ mà không có sự thay đổi nào, có thể phương án nhận được tốt hơn, có thể phương án nhận được là một phương án đã nhận trước đó rồi và từ đó cứ xoay vòng mãi. Do đó nếu không có biện pháp phòng ngừa thì thuật toán đơn hình sẽ có thể kéo dài vô tận.

Khi thực hiện thuật toán đơn hình thì hiện tượng suy biến xảy ra khi có sự tình cờ khử lẫn nhau làm cho tồn tại b ¯ i size 12{ {overline {b}} rSub { size 8{i} } } {} nào đó bằng 0. Trong trường hợp này có thể có nhiều biến thỏa điều kiện của biến ra. Gặp trường hợp này cần phải lựa chọn biến ra sao cho tránh được hiện tượng xoay vòng.

Người ta thường dùng phương pháp nhiễu loạn, phương pháp từ vựng để tránh sự tình cờ khử lẫn nhau này. Trong thực tiển tính toán người ta đã đề ra một quy tắc xử lý khá đơn giản, gọi là quy tắc Bland, khi dùng giải thuật đơn hình giải các quy hoạch tuyến tính suy biến, đó là :

Với xk là biến vào , biến ra xr được chọn là biến có chỉ số nhỏ nhất thỏa điều kiện chọn biến ra :

min b ¯ i a ¯ ik , a ¯ ik > 0 ( i = 1,2, . . . ,m ) size 12{"min"" " left lbrace { { {overline {b}} rSub { size 8{i} } } over { {overline {a}} rSub { size 8{ ital "ik"} } } } " , " {overline {a}} rSub { size 8{"ik"} }>"0 " right rbrace " " \( i="1,2," "." "." "." ",m" \) } {}

Ví dụ :

Xét quy hoạch tuyến tính suy biến :

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

Áp dụng quy tắc Bland ta thấy :

cB iB x1 x2 x3 x4 x5 x6 x7 b ¯ size 12{ {overline {b}} } {}
0 1 1 0 0 1 3 size 12{ { {1} over {3} } } {} -2 -1 12 0
0 2 0 1 0 1 2 size 12{ { {1} over {2} } } {} -1 1 6 size 12{ - { {1} over {6} } } {} 2 3 size 12{ { {2} over {3} } } {} 0
0 3 0 0 1 0 1 1 -9 2
cT 0 0 0 4 3 size 12{ - { {4} over {3} } } {} 2 -1 16
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 0 0 0 4 3 size 12{ - { {4} over {3} } } {} 2 -1 16
w=0

Biến ra có thể là x1 hay x2 . Chọn x1

cB iB x1 x2 x3 x4 x5 x6 x7 b ¯ size 12{ {overline {b}} } {}
4 3 size 12{ - { {4} over {3} } } {} 4 3 0 0 1 -6 -3 36 0
0 2 3 2 size 12{ - { {3} over {2} } } {} 1 0 0 2 4 3 size 12{ { {4} over {3} } } {} 34 3 size 12{ - { {"34"} over {3} } } {} 0
0 3 0 0 1 0 1 1 -9 2
cT 0 0 0 4 3 size 12{ - { {4} over {3} } } {} 2 -1 16
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 4 0 0 0 -6 -5 64
w=0

Biến ra là x2

cB iB x1 x2 x3 x4 x5 x6 x7 b ¯ size 12{ {overline {b}} } {}
4 3 size 12{ - { {4} over {3} } } {} 4 3 2 size 12{ - { {3} over {2} } } {} 3 0 1 0 1 2 0
2 5 3 4 size 12{ - { {3} over {4} } } {} 1 2 size 12{ { {1} over {2} } } {} 0 0 1 2 3 size 12{ { {2} over {3} } } {} 17 3 size 12{ - { {"17"} over {3} } } {} 0
0 3 3 4 size 12{ { {3} over {4} } } {} 1 2 size 12{ - { {1} over {2} } } {} 1 0 0 1 3 size 12{ { {1} over {3} } } {} 10 3 size 12{ - { {"10"} over {3} } } {} 2
cT 0 0 0 4 3 size 12{ - { {4} over {3} } } {} 2 -1 16
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 1 2 size 12{ - { {1} over {2} } } {} 3 0 0 0 -1 30
w=0

Biến ra có thể là x4 hay x5 . Chọn x4

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

Biến ra là x5

cB iB x1 x2 x3 x4 x5 x6 x7 b ¯ size 12{ {overline {b}} } {}
-1 6 0 -6 0 -3 6 1 -40 0
0 1 1 6 0 8 3 size 12{ - { {8} over {3} } } {} 4 0 -28 0
0 3 0 6 1 3 -5 0 31 2
cT 0 0 0 4 3 size 12{ - { {4} over {3} } } {} 2 -1 16
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 0 -6 0 13 3 size 12{ - { {"13"} over {3} } } {} 81 0 -24
w=

Biến ra là x3

cB iB x1 x2 x3 x4 x5 x6 x7 b ¯ size 12{ {overline {b}} } {}
-1 6 0 54 31 size 12{ { {"54"} over {"31"} } } {} 40 31 size 12{ { {"40"} over {"31"} } } {} 27 31 size 12{ { {"27"} over {"31"} } } {} 14 31 size 12{ - { {"14"} over {"31"} } } {} 1 0 80 31 size 12{ { {"80"} over {"31"} } } {}
0 1 1 18 31 size 12{ - { {"18"} over {"31"} } } {} 28 31 size 12{ { {"28"} over {"31"} } } {} 4 93 size 12{ { {4} over {"93"} } } {} 16 31 size 12{ - { {"16"} over {"31"} } } {} 0 0 56 31 size 12{ { {"56"} over {"31"} } } {}
16 7 0 6 31 size 12{ { {6} over {"31"} } } {} 1 31 size 12{ { {1} over {"31"} } } {} 3 31 size 12{ { {3} over { ital "31"} } } {} 5 31 size 12{ - { {5} over {"31"} } } {} 0 1 2 31 size 12{ { {2} over {"31"} } } {}
cT 0 0 0 4 3 size 12{ - { {4} over {3} } } {} 2 -1 16
c ¯ T size 12{ {overline {c}} rSup { size 8{T} } } {} 0 42 31 size 12{ { {"42"} over {"31"} } } {} 24 31 size 12{ { {"24"} over {"31"} } } {} 187 93 size 12{ - { {"187"} over {"93"} } } {} 128 31 size 12{ { {"128"} over {"31"} } } {} 0 0
w= 48 31 size 12{ - { {"48"} over {"31"} } } {}

Đến đây không còn hiện tượng suy biến.

Biến vào là x7

CÂU HỎI CHƯƠNG 2

1- Trình bày cơ sở lý thuyết của thuật toán đơn hình cơ bản.

2- Định nghĩa quy hoạch tuyến chuẩn.

3- Trình bày các bước lập bảng đơn hình theo phép toán trên dòng .

4- Cải biên một quy hoạch tuyến tính tổng quát như thế nào ? . Cách giải quy hoạch tuyến tính cải biên và quy hoạch tuyến tính gốc.

Bài tập chương 2

1- Tìm phương án tối ưu của bài toán sau đây bằng phương pháp đơn hình cơ bản

a)- max z = 3x 1 + 2x 2 -x 1 + x 2 4 x 1 + 2x 2 14 5x 1 + 2x 2 30 x 1 , x 2 0 { { { alignl { stack { size 12{"max"" z"="3x" rSub { size 8{1} } +2x rSub { size 8{2} } } {} #alignl { stack { left lbrace "-x" rSub { size 8{1} } +x rSub { size 8{2} }<= 4 {} # right none left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} }<= "14" {} # right none left lbrace "5x" rSub { size 8{1} } +2x rSub { size 8{2} }<= "30" {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} # right no } } lbrace {}} } {} b)- min z = -2x 1 2x 2 2x 1 + x 2 4 2x 1 + 3x 2 3 4x 1 + x 2 5 x 1 + 5x 2 1 x 1 , x 2 0 { { { { alignl { stack { size 12{"min"" z"="-2x" rSub { size 8{1} } - 2x rSub { size 8{2} } } {} #alignl { stack { left lbrace "2x" rSub { size 8{1} } +x rSub { size 8{2} }<= 4 {} # right none left lbrace "2x" rSub { size 8{1} } +3x rSub { size 8{2} }<= 3 {} # right none left lbrace "4x" rSub { size 8{1} } +x rSub { size 8{2} }<= 5 {} # right none left lbrace x rSub { size 8{1} } +5x rSub { size 8{2} }<= 1 {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} # right no } } lbrace {}} } {}

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

2- Tìm phương án tối ưu của bài toán sau bằng phương pháp đơn hình cải tiến

a)max z = 5x1 + 3x2

2x1 + 2x2  80

x1  30

x1, x2  0

b)max z = x1 + 2x2

2x1 + 3x2  7

x1 - x2  1

x1  0, x2  0

c) max z = 5x1 + 3x2 + x3

2x1 + 3x2 - x3  4

3x1 - x2 + 2x3  2

x1 + x2 + 3x3  5

x1  0, x2  0, x3  0

3- Tìm phương án tối ưu của các bài toán sau bằng phương pháp biến giả cải biên.

a)max z = 3x1 - x2

2x1 + x2  100

x1  10

x2  0

b)min w = 3x1 + x2

x1 + x2  3

2x1  5

x1, x2  0

c)max z = 3x1 + x2 - 3x3

x1 + 2x2 - x3 = 2

-10x2 + 5x3 = 5

-3x2 + 2 x3 = 4

xi  0, i = 13

d)- max z = 2x 1 + 6x 2 x 1 x 2 x 3 2 2x 1 x 2 + x 3 1 x 1 , x 2 , x 3 0 { { alignl { stack { size 12{"max"" z"="2x" rSub { size 8{1} } +6x rSub { size 8{2} } } {} #alignl { stack { left lbrace - x rSub { size 8{1} } - x rSub { size 8{2} } - x rSub { size 8{3} }<= - 2 {} # right none left lbrace 2x rSub { size 8{1} } - x rSub { size 8{2} } +x rSub { size 8{3} }<= 1 {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} } ,x rSub { size 8{3} }>= 0 {} # right no } } lbrace {}} } {} e)- min w = -x 1 3x 2 x 1 + x 2 3 x 1 + x 2 1 x 1 + 2x 2 4 x 1 , x 2 0 { { { alignl { stack { size 12{"min"" w"="-x" rSub { size 8{1} } - 3x rSub { size 8{2} } } {} #alignl { stack { left lbrace x rSub { size 8{1} } +x rSub { size 8{2} }>= 3 {} # right none left lbrace - x rSub { size 8{1} } +x rSub { size 8{2} }<= - 1 {} # right none left lbrace x rSub { size 8{1} } +2x rSub { size 8{2} }<= 4 {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} # right no } } lbrace {}} } {}

f)- max z = x 1 + 3x 2 x 1 x 2 3 x 1 + x 2 1 x 1 + 2x 2 2 x 1 , x 2 0 { { { alignl { stack { size 12{"max"" z"=x rSub { size 8{1} } +3x rSub { size 8{2} } } {} #alignl { stack { left lbrace - x rSub { size 8{1} } - x rSub { size 8{2} }<= - 3 {} # right none left lbrace - x rSub { size 8{1} } +x rSub { size 8{2} }<= - 1 {} # right none left lbrace - x rSub { size 8{1} } +2x rSub { size 8{2} }<= 2 {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} # right no } } lbrace {}} } {} g)- min w = 2x 1 + x 2 x 1 + x 2 1 x 1 2x 2 2 x 2 1 x 1 , x 2 0 { { { alignl { stack { size 12{"min"" w"="2x" rSub { size 8{1} } +x rSub { size 8{2} } } {} #alignl { stack { left lbrace - x rSub { size 8{1} } +x rSub { size 8{2} }<= - 1 {} # right none left lbrace - x rSub { size 8{1} } - 2x rSub { size 8{2} }<= - 2 {} # right none left lbrace x rSub { size 8{2} }<= 1 {} # right none left lbrace x rSub { size 8{1} } ,x rSub { size 8{2} }>= 0 {} # right no } } lbrace {}} } {}

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