Bài 3: Đố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
93
lượt xem
20
download

Bài 3: Đố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 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

Chủ đề:
Lưu

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

  1. ̀ Bai 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)= -2x -3x1 2 +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 P.án (-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 P.án (-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 P.án (-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
  2. ́ ̃ ̉ ĐÔI NGÂU CUA BAI TOAǸ 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 tuy ý ̀ ́ ̣ ́ Cac căp đôi ngâu:̃ 4x1+ x2 – 2x3 ≤ -12 y1≥0 -2x1+ 1/2x2 +x3 ≤ 8 y2 ≥0 -2x1+ 3/2x2 + x3 = 20 y3 tuy ý ̀ x1 ≥0 4y1-2y2-2y3 x2≥0 y1+1/2y2 +3/2y3 x3 ≥0 -2y1+y2+y3
Đồng bộ tài khoản