tailieunhanh - Bài 2: Đối ngẫu của bài toán

Do tồn tại ▲0 nên bài toán chưa có PATƯ Cột có giá trị lơn nhất ưng vơi x3 vậy biến đưa vào là x3 Hàng có giá tri lamda nhỏ nhất ưng vơi x6,ta thay x3vào x6trong bảng sau | Bài 2 F(x) = -3x1+ x2 + 3x3- x4 → min x1 + 2x2- x3 + x4 = 2 x1+2x2-x3+ x4+x5 = 2 2x1-6x2 +3x3 +3x4 =9 2x1-6x2+ 3x3 +3x4+ x6 = 9 x1- x2 +x3 – x4= 6 x1- x2 + x3 – x4+ x7 = 6 xj ≥0(j=1,4) xj ≥0,(j=1,4);x5,x6,x7 ≥0 →Đây là bài toán dạng chuẩn Trong đó: x5,x6,x7 là ẩn giả →F(x)= -3x1+ x2 + 3x3- x4 +Mx5+Mx6+ Mx7→ min Hệ số ACB (-3)X1 (1)X2 (3)X3 (-1)X4 M X5 2 [1] 2 -1 1 M X6 9 2 -6 3 3 M X7 6 1 -1 1 -1 F(x) 0 3 -1 -3 1 17M 4M -5M 3M 3M Do tồn tại ▲>0 nên bài toán chưa có PATƯ Cột có giá trị lớn nhất ứng với x1, vậy biến đưa vào là x1 Hàng có giá tri lamda nhỏ nhất ứng với x5, ta thay x1 vào x5 trong bảng sau Hệ số ACB (-3)X1 (1)X2 (3)X3 (-1)X4 -3 X1 2 1 2 -1 1 M X6 5 0 -10 [5] 1 M X7 4 0 -3 2 -2 F(x) -6 0 -7 0 -2 9M 0M -13M 7M -M Do tồn tại ▲>0 nên bài toán chưa có PATƯ Cột có giá trị lớn nhất ứng với x3 vậy biến đưa vào là x3 Hàng có giá tri lamda nhỏ nhất ứng với x6,ta thay x3vào x6trong bảng sau Hệ số ACB (-3)X1 (1)X2 (3)X3 (-1)X4 -3 X1 1 1 [4] -2 4/5 3 X3 1 0 -2 1 1/5 M X7 2 0 1 0 -12/5 F(x) 0 0 -19 6 -4/5 2M 0M M 0M -12/5M Do tồn tại ▲>0 nên bài toán chưa có PATƯ Cột có giá trị lớn nhất ứng với x2vậy biến đưa vào là x2 Hàng có giá tri lamda nhỏ nhất ứng với x1ta thay x2 vào x1 trong bảng sau Hệ số ACB (-3)X1 (1)X2 (3)X3 (-1)X4 1 X2 1/4 1/4 1 -1/2 1/5 3 X3 3/2 1/2 0 0 3/5 M X7 7/4 -1/4 0 1/2 -13/5 F(x) 19/4 19/4 0 -7/2 3 7/4M -1/4M 0M 1/2M -13/5M Do tồn tại ▲>0 nên bài toán chưa có PATƯ PATƯ của bài toán mở rộng là(0,1/4,3/2,0,0,0,7/4) Bài toán xuất phát không có PATƯ vì tồn tại biến giả có giá trị khác 0 ĐỐI NGẪU CỦA BÀI TOÁN: F(x) = -3x1+ x2 + 3x3- x4 → min F(y)= 2y1+9y2+6y3 → max x1 + 2x2- x3 + x4 = 2 y1+2y2+y3 ≤ -3 2x1-6x2 +3x3 +3x4 =9 2y1-6y2- y3 ≤ 1 x1- x2 +x3 – x4= 6 -y1+3y2+y3 ≤ 3 xj ≥0(j=1,4) y1+3y2-y3 ≤ -1 y1,y2,y3 tùy ý Các Cặp Đối Ngẫu: x1 + 2x2- x3 + x4 = 2 y1 tùy ý 2x1-6x2 +3x3 +3x4 =9 y2 tùy ý x1- x2 +x3 – x4= 6 y3 tùy ý x1≥0 y1+2y2+y3 ≤ -3 x2≥0 2y1-6y2- y3 ≤ 1 x3≥0 -y1+3y2+y3 ≤ 3 x4≥0 y1+3y2-y3 ≤ -1