TAILIEUCHUNG - Bài 1: Đối ngẫu của bài toán
Tham khảo tài liệu bài 1: đố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ả | F(x)= x1-4x2- 3x3→min 2x1 + x2- 2x3 ≤16 2x1+ x2 – 2x3+ x4 =16 -4x1 + 2x3 ≤8 -4x1 + 2x3 + x5 = 8 x1 + 2x2 – x3 ≤ 12 x1 + 2x2 – x3+ x6 =12 xj ≥0(j=1,2,3) xj ≥0(j=1,2,3);x4,x5,x6 ≥0 →Đây là bài toán dạng chuẩn trong đó: x4,x5,x6 là biến phụ Hệ số ACB (1)X1 (-4)X2 (-3)X3 X4 X5 X6 0 X4 16 2 1 -2 1 0 0 0 X5 8 -4 0 2 0 1 0 0 X6 12 1 [2] -1 0 0 1 F(X) 0 -1 4 3 0 0 0 Do tồn tại giá trị ▲>0 nên bài toá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 Cột có giá trị lamda nhỏ nhất ứng với cột là hàng 3, ta thay x2 vào x6. ta có bảng sau Hệ số ACB (1)X1 (-4)X2 (-3)X3 X4 X5 X6 0 X4 10 3/2 0 -3/2 1 0 -1/2 0 X5 8 -4 0 [2] 0 1 0 -4 X2 6 ½ 1 -1/2 0 0 1/2 F(X) -24 -3 0 5 0 0 -2 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á trị dương duy nhất là hàng 2, ứng với x5. Ta thay x3 vào x5 trong bảng sau Hệ số ACB (1)X1 (-4)X2 (-3)X3 X4 X5 X6 0 X4 6 -3 0 3/2 0 ¾ 0 -3 X3 4 -2 0 1 0 ½ 0 -4 X2 8 -1/2 1 0 0 ¼ 1/2 F(X) -44 7 0 0 0 -5/2 -2 Bài toán không có PATƯ vì không tìm được biến PATƯ của bài toán mở rộng là(0,8,4,6,0,0) ĐỐI NGẪU CỦA BÀI TOÁN: F(x)= x1-4x2- 3x3→min f(y)= 16y1+8y2 +12y3→ max 2x1 + x2- 2x3 ≤16 2y1- 4y2 +y3 ≤ 1 -4x1 + 2x3 ≤8 y1+2y3 ≤ -4 x1 + 2x2 – x3 ≤ 12 -2y1+2y2 –y3 ≤ -3 xj ≥0(j=1,2,3) y1≥0,y2 ≥0, y3 ≥0 Các Cặp Đối Ngẫu: 2x1 + x2- 2x3 ≤16 y1≥0 -4x1 + 2x3 ≤8 y2 ≥0 x1 + 2x2 – x3 ≤ 12 y3 ≥0 x1≥0 2y1- 4y2+y3 ≤ 1 x2≥0 y1+2y3 ≤ -4 x3≥0 -2y1+2y2-y3 ≤ -3
đang nạp các trang xem trước
