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

Do tồn tại giá trị Δ0 nên chưa có PATƯ Cột có giá trị lơn nhất ưng vơi x2 vậy biến đưa vào là x2 Hàng có giá trị lamda nhỏ nhất ưng vơi cột là hàng 2 ta thay x2vào x5 trong bảng sau | Bài 3 F(x)= 2x1+3x2- 5x3 → max g(x)= -f(x)=-2x1-3x2 +5x3 → min 4x1+ x2 – 2x3 ≤ -12 -4x1- x2+2x3 ≥ 12 -2x1+ 1/2x2 +x3 ≤ 8 -2x1+ 1/2x2 +x3 ≤ 8 -2x1+ 3/2x2 + x3 = 20 -2x1+ 3/2x2 + x3 = 20 xj ≥0(j=1,2,3) xj ≥0(j=1,2,3) -4x1- x2+2x3 –x4 =12 -4x1- x2+2x3 –x4 + x6 =12 -2x1+ 1/2x2 +x3 + x5 =8 -2x1+ 1/2x2 +x3 + x5 = 8 -2x1+ 3/2x2 + x3 = 20 -2x1+ 3/2x2 + x3 + x7 =20 xj ≥0(j=1,2,3);x4,x5 ≥0 xj ≥0(j=1,2,3) ; x4,x5,x6,x7 ≥ 0 → F(x)= -2x1-3x2 +5x3 +Mx6 + Mx7 → min Đây là dạng chuẩn của bài toán QHTT trong đó: x4, x5 là biến phụ; x6, x7 là ẩn giả Hệ số ACB (-2)X1 (-3)X2 (5)X3 (0)X4 (0)X5 M X6 12 -4 -1 [2] -1 0 0 X5 8 -2 ½ 1 0 1 M X7 20 -2 3/2 1 0 0 F(X) 0 2 3 -5 0 0 32M -6M 1/2M 3M -M 0M Do tồn tại giá trị ∆>0 nê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á trị lamda nhỏ nhất ứng với cột là hàng 1, ta thay x3 vào x6 trong bảng sau Hệ số ACB (-2)X1 (-3)X2 (5)X3 (0)X4 (0)X5 5 X3 6 -2 -1/2 1 -1/2 0 0 X5 2 0 [1] 0 ½ 1 M X7 14 0 2 0 ½ 0 F(X) 30 -8 ½ 0 -5/2 0 14M 0M 2M 0M 1/2M 0M Do tồn tại giá trị ∆>0 nên chưa có PATƯ Cột có giá trị lớn nhất ứng với x2 vậy biến đưa vào là x2 Hàng có giá trị lamda nhỏ nhất ứng với cột là hàng 2 ta thay x2vào x5 trong bảng sau Hệ số ACB (-2)X1 (-3)X2 (5)X3 (0)X4 (0)X5 5 X3 7 -2 0 1 -1/4 ½ -3 X2 2 0 1 0 ½ 1 M X7 10 0 0 0 -1/2 -2 F(X) 29 -8 0 0 -11/4 -1/2 10M 0M 0M 0M -1/2M -2M PATƯ của bài toán mở rộng là (0,2,7,0,0,0,10) 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 TOAN F(x)= 2x1+3x2- 5x3 → max F(y)= -12y1+8y2+ 20y3 → min 4x1+ x2 – 2x3 ≤ -12 4y1-2y2-2y3 -2x1+ 1/2x2 +x3 ≤ 8 y1+1/2y2 +3/2y3 -2x1+ 3/2x2 + x3 = 20 -2y1+y2+y3 xj ≥0(j=1,2,3) y1,y2 ≥0;y3 tùy ý Các cặp đối ngẫu: 4x1+ x2 – 2x3 ≤ -12 y1≥0 -2x1+ 1/2x2 +x3 ≤ 8 y2 ≥0 -2x1+ 3/2x2 + x3 = 20 y3 tùy ý x1 ≥0 4y1-2y2-2y3 x2≥0 y1+1/2y2 +3/2y3 x3 ≥0 -2y1+y2+y3