intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Quy hoạch tuyến tính

Chia sẻ: Abcdef_14 Abcdef_14 | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
205
lượt xem 51
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

2.1 Định nghĩa bài toán đối ngẫu2.1.1 Định nghĩa Xét bài toán quy hoạch tuyến tính gốc (P Bài toán quy hoạch tuyến tínhBài toán sau đây được gọi là bài toán đối ngẫu của bài toán (P), ta gọi là bài toán (Q)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Quy hoạch tuyến tính

  1. Ta gọi vectơ  Bài toán đối ngẫu 2.1 Định nghĩa bài toán đối ngẫu 2.1.1 Định nghĩa Xét bài toán quy hoạch tuyến tính gốc (P) f  c1 x1  c2 x2  ..  cn xn  min(max) ai1 x1  ai2 x2  ..  ain xn  bi ; i  I1 (1) ai1 x1  ai2 x2  ..  ain xn  bi ; i  I 2 (2) ai1 x1  ai2 x2  ..  ain xn  bi ; i  I 3 (3) ( P)  x  0; j  J (4) 1  x  0; j  J (5) j j 2  x j  R; j  J 3 (6) 1
  2.  Bài toán quy hoạch tuyến tính Bài toán sau đây được gọi là bài toán đối ngẫu của bài toán (P), ta gọi là bài toán (Q) g  b1 y1  b2 y2  ..  bm ym  max(min) a1j y1  a2j y2  ..  amj ym  c j ; j  J1 (4') a1j y1  a2j y2  ..  amj ym  c j ; j  J 2 (5') a y  a y  ..  a y  c ; j  J (6') (Q)  1j 1 2j 2 3 mj m j yi  0; i  I1 (1')   yi  0; i  I 2 (2')  yi  R; i  I 3 (3') Trong đó các cặp ràng buộc (1) – (1), (2) – (2), .., (6) – (6) được gọi là các ràng buộc đối ngẫu với nhau. 2
  3.  Bài toán quy hoạch tuyến tính VD21: Viết bài toán đối ngẫu (Q) biết f  2 x1  x2  3x3  x4  2 x5  min  x1  x2  2 x3  x4  x5  12  x3  3x4  2 x5  5 2 x1  x1  3x2  2 x4  x5  6  ( P) 3x1  2 x2  x3  x4  3  x1 , x3  0  x5  0  x2 , x4    3
  4.  Bài toán quy hoạch tuyến tính Giải: Bài toán đối ngẫu của bài toán (P) là bài toán sau: g  12 y1  5 y2  6 y3  3 y4  max  y1  2 y2  y3  3 y4  2  y1  3 y3  2 y4  1 2 y1  y2  y4  3 (Q )   y1  3 y2  2 y3  y4  1  y  2 y  y  2  y1  0 , 2y , y3  0 , y  R. 1 2 4 3 4
  5. Ta gọi vectơ  Bài toán đối ngẫu 2.1.2 Cách thành lập bài toán đối ngẫu Bài toán gốc Bài toán đối ngẫu f = cjxj  min g = biyi  max  bi 0 aijxj  bi 0 yi R = bi 0  cj ajiyi 0  cj xj R = cj 5
  6.  Bài toán quy hoạch tuyến tính VD22: Viết bài toán đối ngẫu (Q) biết f  x1  x2  x4  3x5  min  x1  2 x3  2 x4  x5  4  x1  3x3  x4  2 x5  7  ( P) 2 x1  3x2  x3  x4  3x5  6  x1  2 x2  4 x3  x4  x5  3  x2 , x5  0 , x3 , x4  0 , x1  R.  6
  7.  Bài toán quy hoạch tuyến tính Giải: Bài toán đối ngẫu của bài toán (P) là bài toán sau: f  4 y1  7 y2  6 y3  3 y4  max  y1  y2  2 y3  y4  1 3 y3  2 y4  1 2 y1  3 y2  y3  4 y4  0 (Q)  2 y1  y2  y3  y4  1  y  2 y  3 y  y  3  y1, y 2R, y 3 0, y  0 4 2 1 3 4 Lưu ý: Ta có đối ngẫu của bài toán đối ngẫu chính là bài toán gốc ban đầu. 7
  8. Ta gọi vectơ  Bài toán đối ngẫu 2.2 Mối liên hệ giữa bài toán gốc và bài toán đối ngẫu Ta xét bài toán quy hoạch tuyến tính gốc dạng tìm min. 2.2.1 Định lý 1 (Đối ngẫu yếu) Cho x, y theo thứ tự là phương án của bài toán gốc và đối ngẫu ta có f(x)  g(y). Lưu ý: Từ định lý nếu ta có phương án của bài toán gốc và đối ngẫu theo thứ tự là x, y mà f(x) = g(y) thì x, y lần lượt là phương án tối ưu của bài toán gốc và bài toán đối ngẫu. 2.2.2 Định lý 2 (Đối ngẫu mạnh) Nếu một trong hai bài toán có phương án tối ưu thì bài toán đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu của chúng là bằng nhau. 8
  9. Ta gọi vectơ  Bài toán đối ngẫu 2.2.3 Định lý 3 (Định lý tồn tại) Một cặp bài toán và bài toán đối ngẫu của nó chỉ có thể xảy ra một trong 3 khả năng loại trừ sau:  Cả hai bài toán đều không có phương án.  Cả hai bài toán đều có phương án, khi đó cả hai cùng có phương án tối ưu và giá trị tối ưu của hai hàm mục tiêu là bằng nhau.  Một bài toán có phương án còn bài toán kia không có phương án, khi đó bài toán có phương án sẽ không có phương án tối ưu và hàm mục tiêu không bị chặn trong miền ràng buộc. 9
  10. Ta gọi vectơ  Bài toán đối ngẫu 2.2.4 Định lý 4 (Độ lệch bù) Một cặp phương án x, y của bài toán gốc và đối ngẫu là phương án tối ưu khi và chỉ khi chúng nghiệm đúng hệ thức sau   n  bi   aij x j  yi  0 i  1, m   j 1   c   a y  x  0 j  1, n  m  j i 1 ji i  j   Lưu ý: bi – aijxj là độ lệch ở ràng buộc thứ i ở bài toán gốc và cj – ajiyi là độ lệch ở ràng buộc thứ j ở bài toán đối ngẫu của nó. 10
  11. Ta gọi vectơ  Bài toán đối ngẫu 2.3 Giải bài toán đối ngẫu 2.3.1 Áp dụng định lý độ lệch bù VD23: Cho bài toán gốc f = x1  2x2 + 2x3  min x1 + x2 + 4x4 = 6 2x2 + x3 + 5x4 = 8 xj  0, j=1,2,3,4 có phương án tối ưu là x* = (2, 4, 0, 0) và giá trị tối ưu là fmin = 6. Tìm phương án tối ưu của bài toán đối ngẫu. 11
  12. Ta gọi vectơ  Bài toán đối ngẫu Giải: Ta có bài toán đối ngẫu của bài toán đã cho: g = 6y1 + 8y2  max y1  1 y1 + 2y2  2 y2  2 4y1 + 5y2  0 y1, y2  R Do x* = (2, 4, 0, 0) nên áp dụng định lý độ lệch bù ta có: 1 y1 = 0 hay y1 = 1 2  (y1 + 2y2) = 0 y2 = 3/2 Suy ra phương án tối ưu của bài toán đối ngẫu là y* = (1, 3/2) và gmax = 6.1 + 8.(3/2) = 6 = fmin 12
  13. Ta gọi vectơ  Bài toán đối ngẫu VD24: Cho bài toán gốc f = x1 + x2 + x3 + x4 + x5  min 3x1 + x2 + x3 = 1 5x1 + x2 + x3 + x4 = 3 2x1 + 5x2 + x3 + x5 = 8 xj  0, j=1,2,3,4,5 có phương án tối ưu là x* = (0, 1, 0, 2, 3) và giá trị tối ưu là fmin = 6. Tìm phương án tối ưu của bài toán đối ngẫu. Giải: Ta có bài toán đối ngẫu của bài toán đã cho: 13
  14. Ta gọi vectơ  Bài toán đối ngẫu g = y1 + 3y2 + 8y3  max 3y1 + 5y2 + 2y3  1 y1 + y2 + 5y3  1 y1 + y2 + y3  1 y2  1 y3  1 yi  R,, i=1,2,3 Do x* = (0, 1, 0, 2, 3) nên áp dụng định lý độ lệch bù ta có: 1 (y1 + y2 + 5y3 ) = 0 y1 = 5 hay 1  y2 = 0 y2 = 1 1  y3 = 0 y3 = 1 Suy ra phương án tối ưu của bài toán đối ngẫu là y* = (5, 1, 1) và gmax = 5 + 3 + 8 = 6 = fmin 14
  15. Ta gọi vectơ  Bài toán đối ngẫu 2.3.2 Dùng bảng đơn hình của bài toán gốc VD25: Giải bài toán gốc f = x1  2x2 + 2x3  min x1 + x2 + 4x4 = 6 2x2 + x3 + 5x4 = 8 xj  0, j=1,2,3,4 Suy ra phương án tối ưu của bài toán đối ngẫu. Giải: Phương án cực biên ban đầu x0 = (6, 0, 8, 0) Lập bảng đơn hình 15
  16.  Bài toán đối ngẫu x1 x2 x3 x4 Biến Hệ Phương  án cơ sở số 1 -2 2 0 x1 1 6 1 1 0 (4) [3/2] x3 2 8 0 2 1 5 8/5 Bảng 1 22 0 7 0 [14] x4 0 3/2 1/4 1/4 0 1 6 x3 2 1/2 -5/4 3/4 1 0 [2/3] Bảng 2 1 -7/2 [7/2] 0 0 16
  17.  Bài toán đối ngẫu x4 0 4/3 (2/3) 0 -1/3 1 [2] x2 -2 2/3 -5/3 1 4/3 0 Bảng 3 -4/3 [7/3] 0 -14/3 0 x1 1 2 1 0 -1/2 3/2 x2 -2 4 0 1 1/2 5/2 Bảng 4 -6 0 0 -7/2 -7/2 Phương án tối ưu x* = (2, 4, 0, 0), fmin = 6. Biến cơ sở ở bước lặp đầu tiên là x1 và x3 suy ra phương án tối ưu của bài toán đối ngẫu cho bởi: y1 = 1 + c1 = 0 + 1 = 1 y2 = 3 + c3 = 7/2 + 2 = 3/2 17
  18. Ta gọi vectơ  Bài toán đối ngẫu VD26: Giải bài toán gốc f = x1 + x2 + x3 + x4 + x5  min 3x1 + x2 + x3 = 1 5x1 + x2 + x4 = 3 2x1 + 5x2 + x5 = 8 xj  0, j=1,2,3,4,5 Suy ra phương án tối ưu của bài toán đối ngẫu. 18
  19. Ta gọi vectơ  Bài toán đối ngẫu Giải: Phương án cực biên ban đầu x0 = (0, 0, 1, 3, 8) Lập bảng đơn hình x1 x2 x3 x4 x5 Biến Hệ Phương  án cơ sở số 1 1 1 1 1 x3 1 1 (3) 1 1 0 0 [1/3] x4 1 3 5 1 0 1 0 3/5 x5 1 8 2 5 0 0 1 4 Bảng 1 12 [9] 6 0 0 0 19
  20. Ta gọi vectơ  Bài toán đối ngẫu x1 1 1/3 1 (1/3) 1/3 0 0 [1] x4 1 4/3 0 -5/3 1 0 -2/3 x5 1 22/3 0 -2/3 0 1 22/13 13/3 Bảng 2 9 0 [3] -3 0 0 x2 1 1 3 1 1 0 0 x4 1 2 2 0 -1 1 0 x5 1 3 -13 0 -5 0 1 Bảng 3 6 -9 0 -6 0 0 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2