Bài 9: Đố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
146
lượt xem
47
download

Bài 9: Đố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 đủ

Tham khảo tài liệu 'bài 9: đố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ả

Chủ đề:
Lưu

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

  1. Bài 9 F(x) = 2x1- 3x2+ x3 → max G(x)=-f(x)= -2x1+ 3x2- x3 → min x1+2x2 +2x3 ≤ 30 x1+2x2 +2x3 + x4 = 30 x1+ 2x2 +2x3 = 25 x1+ 2x2 +2x3 = 25 2x1 + x2+ x3 ≥ 40 2x1 + x2+ x3 – x5 = 40 xj≥ 0(j=1,2,3) xj≥ 0(j=1,2,3); x4,x5≥ 0 G(x)=-f(x)= -2x1+ 3x2- x3 +Mx6+Mx7→ min x1+2x2 +2x3 + x4 = 30 Đây là bài toán dạng chuẩn x1+ 2x2 +2x3 + x6 = 25 trong đó: x4,x5 là biến phụ 2x1 + x2+ x3 – x5 + x7= 40 x6,x7 là ẩn giả xj≥ 0(j=1,2,3); x4,x5,x6,x7≥ 0 Hệ số ACB P.án (-2)X1 (3)X2 (-1)X3 (0)X4 (0)X5 0 X4 30 1 2 2 1 0 M X6 25 1 2 2 0 0 M X7 40 [2] 1 1 0 -1 F(X) 0 2 -3 1 0 0 65M 3M 3M 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 3, ta thay x1 vào x7 trong bảng sau Hệ số ACB P.án (-2)X1 (3)X2 (-1)X3 (0)X4 (0)X5 0 X4 10 0 0 3/2 1 1/2 M X6 5 0 3/2 [3/2] 0 1/2 -2 X1 20 1 ½ ½ 0 -1/2 F(X) -40 0 -4 0 0 -1 5M 0M 3/2M 3/2M 0M 1/2M 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 2, ta thay x3 vào x6 trong bảng sau Hệ số ACB P.án (-2)X1 (3)X2 (-1)X3 (0)X4 (0)X5 0 X4 5 0 -3/2 0 1 0 -1 X3 10/3 0 1 1 0 [1/3] -2 X1 15 1 0 0 0 -2/3 F(X) -100/3 0 -4 0 0 1 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 nhỏ nhất ưng vơi cột là hàng 2, ta thay x5 vào x3 trong bảng sau Hệ số ACB P.án (-2)X1 (3)X2 (-1)X3 (0)X4 (0)X5 0 X4 5 0 -3/2 0 1 0 0 X5 10 0 3 3 0 1 -2 X1 65/3 1 2 2 0 0 F(X) -130/3 0 -7 -5 0 0 PATƯ của bài toán là (65/3,0,0,5,10,0,0). Vơi G(x)= -130/3 Giá trị hàm mục tiêu đạt được là như vậy, bài toán xuất phát có giá trị là 130/3
  2. ĐỐI NGẪU CỦA BÀI TOÁN: F(x) = 2x1- 3x2+ x3 → max f(y)= 30y1+ 25y2+40y3 → min x1+2x2 +2x3 ≤ 30 y1+y2 +2y3 ≥ 2 x1+ 2x2 +2x3 = 25 2y1+ 2y2 +y3 ≥ -3 2x1 + x2+ x3 ≥ 40 2y1 + 2y2+ y3 ≥ 1 xj≥ 0(j=1,2,3) y1≤ 0,y2 tùy ý,y3≥0 Các cặp đối ngẫu: x1+2x2 +2x3 ≤ 30 y1≤ 0 x1+ 2x2 +2x3 = 25 y2 tùy ý 2x1 + x2+ x3 ≥ 40 y3≥0 x1≥ 0 y1+y2 +2y3 ≥ 2 x2≥ 0 2y1+ 2y2 +y3 ≥ -3 x3 ≥ 0 2y1 + 2y2+ y3 ≥ 1
Đồng bộ tài khoản