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

Chia sẻ: Phạm Minh Hiếu | Ngày: | Loại File: DOC | Số trang:2

0
129
lượt xem
47
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:
Lưu

Nội dung Text: Bài 2: Đối ngẫu của bài toán

  1. ̀ Bai 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 P.án (-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 P.án (-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 P.án (-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 P.án (-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
  2. 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
Đồng bộ tài khoản