tailieunhanh - Bài 4: Đố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 x1. vậy biến đưa vào là x1 Hàng có giá trị lamda nhỏ nhất ưng vơi cột là hàng 1, ta thay x1 vào x4 trong bảng sau | Bài 4 F(x)= 2x1- 2x2 + 3x3 → min 2x1+2x2-x3 ≤ 1 2x1+2x2-x3 +x4= 1 x1-x2-3x3 ≥ 1 x1-x2-3x3 - x5 =1 xj≥ 0(j=1,2,3) xj≥ 0(j=1,2,3); x4,x5≥ 0 2x1+2x2-x3 +x4 = 1 F(X)= 2x1- 2x2 + 3x3 +Mx6 → min x1-x2-3x3 - x5 + x6 =1 →đây là bài toán chuẩn, trong đó: xj≥ 0(j=1,2,3); x4,x5, x6≥ 0 x4,x5 là biến phụ; x6 là ẩn giả Hệ số ACB (2)X1 (-2)X2 (3)X3 (0)X4 (0)X5 0 X4 1 [2] 2 -1 1 0 M X6 1 1 -1 -3 0 -1 F(X) 0 -2 2 -3 0 0 M M -1M -3M 0M -M 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 x1. vậy biến đưa vào là x1 Hàng có giá trị lamda nhỏ nhất ứng với cột là hàng 1, ta thay x1 vào x4 trong bảng sau Hệ số ACB (2)X1 (-2)X2 (3)X3 (0)X4 (0)X5 2 X1 ½ 1 1 -1/2 ½ 0 M X6 ½ 0 -2 -5/2 -1/2 -1 F(X) 1 0 4 -4 1 0 1/2M 0M -2M -5/2M -1/2M -M PATƯ của bài toán mở rộng là(1/2,0,0,0,0,1/2) 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)= 2x1- 2x2 + 3x3 → min F(y)= y1+ y2 → max 2x1+2x2-x3 ≤ 1 2y1+y2 ≤ 2 x1-x2-3x3 ≥ 1 2y1-y2 ≤ -2 xj≥ 0(j=1,2,3) -y1- 3y2 ≤3 y1≥ 0; y2≤0 Các cặp đối ngẫu: 2x1+2x2-x3 ≤ 1 y1≥ 0 x1-x2-3x3 ≥ 1 y2≤0 x1≥ 0 2y1+y2 ≤ 2 x2≥ 0 -y1-y2 ≤ -2 x3≥ 0 -y1- 3y2 ≤3