Giáo Trình Toán Rời Rạc - Bài Toán đối Ngẫu - Tài Liệu đại Học

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Tài liệu khác

1. Home
2. Tài liệu khác
3. Giáo trình Toán rời rạc - Bài toán đối ngẫu

Trich dan Giáo trình Toán rời rạc - Bài toán đối ngẫu - pdf 16 Download miễn phí Giáo trình Toán rời rạc - Bài toán đối ngẫu Trong trường hợp quy hoạch tuyến tính tổng quát, những quy tắc sau đây được áp dụng đểxây dựng bài toán đối ngẫu : - Hàmmục tiêu đối ngẫu :. max ↔min - Biến đối ngẫu : . Mỗi ràng buộc ↔một biến đối ngẫu - Chi phí đối ngẫu và giới hạn ràng buộc : . Chi phí đối ngẫu ↔giới hạn ràng buộc - Ma trận ràng buộc đối ngẫu : . Ma trận chuyển vị- Chiều của ràng buộc vàdấu của biến : . Ràng buộc trong bài toán max có dấu ≤thìbiến đối ngẫu trong bài toán min có dấu ≥0 ( trái chiều ) http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-02-giao_trinh_toan_roi_rac_bai_toan_doi_ngau.KojIoOuMhR.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53443/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

BÀI TOÁN ĐỐI NGẪU 70 CHƯƠNG III BÀI TOÁN ĐỐI NGẪU Chương này trình bày trình bày khái niệm đối ngẫu, các quy tắc đối ngẫu và giải thuật đối ngẫu. Đây là các kiến thức có giá trị trong ứng dụng vì nhờ đó có thể giải một quy hoạch tuyến tính từ quy hoạch tuyến tính đối ngẫu của nó. Nội dung chi tiết của chương này bao gồm : I- KHÁI NIỆM VỀ ĐỐI NGẪU 1- Đối ngẫu của quy hoạch tuyến tính dạng chính tắc 2- Định nghĩa đối ngẫu trong trường hợp tổng quát 3- Các định lý về sự đối ngẫu a- Định lý 1 ( đối ngẫu yếu ) b- Định lý 2 c- Định lý 3 d- Định lý 4 ( sự đối ngẫu) e- Định lý 5 (tính bổ sung ) II- GIẢI THUẬT ĐỐI NGẪU BÀI TOÁN ĐỐI NGẪU 71 CHƯƠNG III BÀI TOÁN ĐỐI NGẪU I- KHÁI NIỆM VỀ ĐỐI NGẪU Đối ngẫu là một khái niệm cơ bản của việc giải bài toán quy hoạch tuyến tính vì lý thuyết đối ngẫu dẫn đến một kết quả có tầm quan trọng về mặt lý thuyết và cả mặt thực hành. 1- Đối ngẫu của quy hoạch tuyến tính dạng chính tắc Xét một bài toán quy hoạch tuyến tính dạng chính tắc ⎪⎩ ⎪⎨ ⎧ ≥ = = 0x b Ax xcz(x) min T Giả sử rằng x* là phương án tối ưu cần tìm của bài toán và x0 là một phương án của bài toán thì một cận trên của giá trị mục tiêu tối ưu được xác định vì : cTx* ≤ cTx0 Tuy chưa tìm được phương án tối ưu x* nhưng nếu biết thêm được một cận dưới của giá trị mục tiêu tối ưu thì ta đã giới hạn được phần nào giá trị mục tiêu tối ưu. Người ta ước lượng cận dưới này theo cách như sau : Với mỗi vectơ xT = [x1 x2 ... xn] ≥ 0 thuộc Rn chưa thoả ràng buộc của bài toán, tức là b – Ax ≠ 0 người ta nới lỏng bài toán trên thành bài toán nới lỏng : min L(x,y) = cTx + yT(b - Ax) x ≥ 0 yT = [ y1 y2 ... ym] tuỳ ý ∈ Rm Gọi g(y) là giá trị mục tiêu tối ưu của bài toán nới lỏng, ta có : g(y) = min { cTx + yT(b - Ax) } (x ≥ 0) BÀI TOÁN ĐỐI NGẪU 72 ≤ cTx + yT(b - Ax) Trong trường hợp x là phương án của bài toán ban đầu, tức là : b - Ax = 0 thì g(y) ≤ cTx Vậy g(y) là một cận dưới của giá trị mục tiêu bất kỳ nên cũng là cận dưới của giá trị mục tiêu tối ưu. Một cách tự nhiên là người ta quan tâm đến bài toán tìm cận dưới lớn nhất, đó là : max g(y) y tuỳ ý ∈ Rm Bài toán này được gọi là bài toán đối ngẫu của bài toán ban đầu. Trong phần sau người ta sẽ chứng minh giá trị mục tiêu tối ưu của bài toán đối ngẫu bằng với giá trị mục tiêu tối ưu của bài toán gốc ban đầu. Người ta đưa bài toán đối ngẫu về dạng dể sử dụng bằng cách tính như sau : g(y) = min { cTx+yT(b - Ax) } (x ≥ 0) = min { cTx + yTb - yTAx } (x ≥ 0) = min { yTb + (cT - yTA)x } (x ≥ 0) = yTb + min { (cT - yTA)x } (x ≥ 0) Ta thấy : ⎢⎢⎣ ⎡ <− ≥−=− ≥ 0Ayc khi đinh xáckhông 0Ayc khi 0 x)Ay(c min TT TT )0x( TT Vậy ta nhận được : g(y) = yTb với cT - yTA ≥ 0 Suy ra bài tóan đối ngẫu có dạng : ⎪⎩ ⎪⎨ ⎧ ∈ ≤ = tùy ý Ry cAy byg(y) max m TT T Hay là : BÀI TOÁN ĐỐI NGẪU 73 ⎪⎩ ⎪⎨ ⎧ ∈ ≤ = tùy ý Ry cyA ybg(y) max m T T 2- Định nghĩa đối ngẫu trong trường hợp quy hoạch tổng quát Trong trường hợp quy hoạch tuyến tính tổng quát, những quy tắc sau đây được áp dụng để xây dựng bài toán đối ngẫu : - Hàm mục tiêu đối ngẫu : . max ↔ min - Biến đối ngẫu : . Mỗi ràng buộc ↔ một biến đối ngẫu - Chi phí đối ngẫu và giới hạn ràng buộc : . Chi phí đối ngẫu ↔ giới hạn ràng buộc - Ma trận ràng buộc đối ngẫu : . Ma trận chuyển vị - Chiều của ràng buộc và dấu của biến : . Ràng buộc trong bài toán max có dấu ≤ thì biến đối ngẫu trong bài toán min có dấu ≥ 0 ( trái chiều ) . Ràng buộc trong bài toán max có dấu = thì biến đối ngẫu trong bài toán min có dấu tùy ý. . Ràng buộc trong bài toán max có dấu ≥ thì biến đối ngẫu trong bài toán min có dấu ≤ 0 ( trái chiều ) . Biến của bài toán max có dấu ≥ 0 thì ràng buộc đối ngẫu trong bài toán min có dấu ≥ ( cùng chiều ) . Biến của bài toán max có dấu tùy ý thì ràng buộc đối ngẫu trong bài toán min có dấu = . . Biến của bài toán max có dấu ≤ 0 thì ràng buộc trong bài toán đối ngẫu min có dấu ≤ ( cùng chiều ) Xét các ràng buộc dạng ma trận của một bài toán quy hoạch tuyến tính tổng quát như sau : BÀI TOÁN ĐỐI NGẪU 74 j m i 1 n j 2 1 mn2m1m n11211 T i A b ... b ... b x ... x ... x x a......aa .................. ...... .................. a......aa a ↑ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ ≥ ≤ = ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ → mj iniji2i1 1j a aaaa a Ký hiệu : là dòng thứ i (i=1,2,...,m) Tia Aj là cột thứ j (j=1,2,...,n) Khi đó, mối liên hệ giữa hai bài toán đối ngẫu có thể được trình bày như sau : z(x) = cTx → min w(y) = yTb → max Ràng buộc / Dấu i T i bxa = yi tự do i T i bxa ≤ yi ≤ 0 i T i bxa ≥ yi ≥ 0 Cùng chiều xj ≥ 0 yTAj ≤ cj xj ≤ 0 yTAj ≥ cj xj tự do yTAj = cj Trái chiều Ví dụ a- Hai bài toán sau đây là đối ngẫu : (P) 0x,x 6x22x 4x2x x1030xz(x)max 21 21 21 21 ≥ ⎩⎨ ⎧ ≤+ ≤+ += (D) 0y,y 10y2y 30y22y y64yw(y) min 21 21 21 21 ≥ ⎩⎨ ⎧ ≥+ ≥+ += b- Hai bài toán sau đây là đối ngẫu : BÀI TOÁN ĐỐI NGẪU 75 0x ,tuy y x ,0x,x 5x2x7x 9x5x23x 7x4x3x32x 6x5xx2x x2xxxw(x) min 4321 431 321 4321 4321 4321 ≤≥ ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥−+ =+− ≥−+− ≤+−+ ++−= (D) 0y tuy y, y,0y,0y 2y2y45y 1yy5y3y- 1y2y32y 1y7y3y2y y5y9y76yz(y) max 4321 421 4321 321 4321 4321 ≥≥≤ ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥−− =+++ −≤−− ≤+++ +++= (P) Ðối với cặp bài toán đối ngẫu (P) và (D) chỉ xảy ra một trong ba trường hợp sau : - Cả hai bài toán đều không có phương án tối ưu . - Cả hai bài toán đều có phương án, lúc đó chúng đều có phương án tối ưu và giá trị hàm mục tiêu đối với hai phương án tối ưu là bằng nhau. - Một trong hai bài toán không có phương án, còn bài toán kia thì có phương án, khi đó bài toán có phương án không có phương án tối ưu. 3- Các định lý về sự đối ngẫu a- Định lý 1 ( đối ngẫu yếu ) Xét hai bài toán đối ngẫu : ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ = = 0x b Ax x cz(x)max )P( T ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ = tùy ý y cyA y b w(y) min )D( T T Nếu x là phương án của bài toán (P) y là phương án của bài toán (D) thì )y(w)x(z ≤ nghĩa là giá trị hàm mục tiêu của bài toán max không vượt quá giá trị hàm mục tiêu của bài toán đối ngẫu min trên các phương án bất kỳ của mỗi bài toán . Chứng minh BÀI TOÁN ĐỐI NGẪU 76 x là phương án của (P) nên : bxA = ⇒ )y(wybb yxAy TTT === y là phương án của (D) nên : cyA T ≥ ⇒ TT cAy ≥ ⇒ )x(zxcxAy TT =≥ Vậy )y(w)x(z ≤ Định lý này được phát biểu và chứng minh cho hai bài toán đối ngẫu trong trường hợp tổng quát . b- Định lý 2 Xét hai bài toán đối ngẫu : ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ = = 0x b Ax xcz(x)max )P( T ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ = tùy ý y cyA yb w(y) min )D( T T x là phương án khả thi của bài toán (P) y là phương án khả thi của bài toán (D) Nếu )y(w)x(z = thì x , y lần lượt là phương án tối ưu tương Yêu cầu Download Tài liệu, ebook tham khảo khác

• Giáo trình Toán rời rạc - Bài toán đếm
• Giáo trình Toán rời rạc - Đại số Boole
• Một số giải pháp nâng cao hiệu quả sử dụng vốn tại công ty TNHH Nhật Minh
• Khảo sát hàm số và vẽ đồ thị
• Hoàn thiện công tác kế toán tiền lương và các khoản trích theo lương tại Công Ty Cổ Phần Xây Dựng Long Thường
• Hoàn thiện chất lượng dịch vụ ăn uống trong kinh doanh nhà hàng âu MonDo
• Hoàn thiện tổ chức kế toán bán hàng và kết quả bán hàng tại Công ty cổ phần Thương mại và dịch vụ tin học Thanh Bình
• Hoạt động xuất khẩu gạo của Việt Nam theo quan điểm đảm bảo an ninh lương thực từ năm 2007 đến nay
• Một số giải pháp nhằm nâng cao hiệu quả công tác huy động vốn thông qua tài khoản tiền gửi tại NHNo&PTNT huyện Yên Lạc Tỉnh Vĩnh Phúc
• Báo cáo tổng hợp về hoạt động sản xuất kinh doanh của công ty cổ phần cơ khí thương mại AN KIM

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top