Đang chuẩn bị liên kết để tải về tài liệu:
Bài 6: Đối ngẫu của bài toán

Tham khảo tài liệu bài 6: đối ngẫu của bài toán , khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Bài 6 F(x)= x1+ 2x2- x3 → max G(x)=-f(x)= - x1- 2x2+ x3 → min -x1+ 4x2- 2x3 ≤ 6 -x1+ 4x2- 2x3 +x4=6 x1+ x2+2x3 ≥ 6 x1+ x2+2x3 – x5 = 6 2x1-x2+ 2x3 = 4 2x1-x2+ 2x3 = 4 xj≥ 0(j= 1,2,3) xj≥ 0(j= 1,2,3);x4,x5≥ 0 G(x)=-f(x)= - x1- 2x2+ x3 +Mx6+Mx7→ min -x1+ 4x2- 2x3 +x4=6 Đây là bài toán dạng chuẩn, trong đó x1+ x2+2x3 – x5 + x6 = 6 x4,x5 là biến phụ 2x1-x2+ 2x3 + x7 = 4 x6,x7 là ẩn giả xj≥ 0(j= 1,2,3);x4,x5,x6,x7≥ 0 Hệ số ACB P.án (-1)X1 (-2)X2 (1)X3 (0)X4 (0)X5 0 X4 6 -1 4 -2 1 0 M X6 6 1 1 2 0 -1 M X7 4 2 -1 [2] 0 0 F(X) 0 1 2 -1 0 0 10M 3M 0M 4M 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 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 3 ta thay x3 vào x7 trong bảng sau Hệ số ACB P.án (-1)X1 (-2)X2 (1)X3 (0)X4 (0)X5 0 X4 10 1 3 0 1 0 M X6 2 -1 [2] 0 0 -1 1 X3 2 1 -1/2 1 0 0 F(X) 2 2 3/2 0 0 0 2M -M 2M 0M 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 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 x2 vào x6 trong bảng sau Hệ số ACB P.án (-1)X1 (-2)X2 (1)X3 (0)X4 (0)X5 0 X4 7 5/2 0 0 1 3/2 -2 X2 1 -1/2 1 0 0 -1/2 1 X3 5/2 [¾] 0 1 0 -1/4 F(X) 1/2 11/4 0 0 0 3/4 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 3 ta thay x1 vào x3 trong bảng sau Hệ số ACB P.án (-1)X1 (-2)X2 (1)X3 (0)X4 (0)X5 0 X4 -4/3 0 0 -10/3 1 [7/3] -2 X2 8/3 0 1 2/3 0 -2/3 -1 X1 10/3 1 0 4/3 0 -1/3 F(X) -26/3 0 0 -11/3 0 5/3 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 x5. vậy biến đưa vào là x5 Hàng có giá trị lamda dương ứng với cột là hàng 1 ta thay x5 vào x4 trong bảng sau Hệ số ACB P.án (-1)X1 (-2)X2 (1)X3 (0)X4 (0)X5 0 X5 4/7 0 0 -10/7 3/7 1 -2 X2 64/21 0 1 -2/7 6/21 0 -1 X1 74/21 1 0 6/7 3/21 0 F(X) -18/7 0 0 -9/7 -5/7 0 PATƯ của bài toán là(74/21,64/21,0,0,4/7,0,0), với G(x)= -18/7 Giá trị hàm mục tiêu đạt được, như vậy bài toán xuất phat có giá trị là (18/7) ĐỐI NGẪU CỦA BÀI TOÁN: F(x)= x1+ 2x2- x3 → max G(Y)= 6y1+6y2+4y3 → min -x1+ 4x2- 2x3 ≤ 6 -y1+ y2+2y3 ≥1 x1+ x2+2x3 ≥ 6 4y1+ y2-y3 ≥ 2 2x1-x2+ 2x3 = 4 -2y1+2y2+ 2y3 ≥ -1 xj≥ 0(j= 1,2,3) y1≤0; y2≥ 0, y3 tùy ý Các cặp đối ngẫu: -x1+ 4x2- 2x3 ≤ 6 y1≤0 x1+ x2+2x3 ≥ 6 y2≥ 0 2x1-x2+ 2x3 = 4 y3 tùy ý x1≥ 0 -y1+ y2+2y3 ≥1 x2≥ 0 4y1+ y2-y3 ≥ 2 x3≥ 0 -2y1+2y2+ 2y3 ≥ -1