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

Bài giảng Tối ưu hóa: Chương 2 - ThS. Phạm Trí Cao

Chia sẻ: Thôi Kệ | Ngày: | Loại File: PDF | Số trang:10

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

Chương 2 của bài giảng Tối ưu hóa trình bày về bài toán quy hoạch tuyến tính đối ngẫu. Chương này gồm có các nội dung chính như: Cách thành lập bài toán QHTT đối ngẫu, các định lý đối ngẫu. Mời bạn đọc cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tối ưu hóa: Chương 2 - ThS. Phạm Trí Cao

  1. ThS. Phạm Trí Cao * Chương 2 03/01/2014  I) CAÙCH THAØNH LAÄP BAØI TOAÙN CHÖÔNG 2: QHTT ÑOÁI NGAÃU BAØI TOAÙN QUY HOAÏCH  Ñeå laäp baøi toaùn QHTT ñoái ngaãu ñöôïc ñôn giaûn ta neân chuyeån baøi toaùn veà daïng ma TUYEÁN TÍNH ÑOÁI NGAÃU traän, baèng caùch taùch caùc giaù trò soá vaø bieán rieâng ra. 1 2  Ví duï 2.1:  Baøi toaùn goác (P):  f(x) = x1 + 2x2 + 0x3  4x4  min  4x1 + 6x2 + x3 + x4 >= 1680  x1 + x2  5x3 + 2x4 =0 , x2 >=0 , x3
  2. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Nhaän xeùt:  Baøi toaùn ñoái ngaãu cuõng laø baøi toaùn QHTT.  Baøi toaùn goác (P) coù patö laø x*= (212, 0, 92, 924) vaø fmin= -3484, baøi toaùn ñoái ngaãu (P*) coù patö laø y*= (47/70, -27/70, -91/70) vaø fmax= -3484.  Caùc caëp raøng buoäc ñoái ngaãu: laø caùc caëp raøng buoäc coù daïng baát ñaúng thöùc.  Vieát caùc caëp raøng buoäc ñoái ngaãu cho VD2.1?  VD2.2 5 6  Quy taéc laäp baøi toaùn ñoái ngaãu:  Daáu moät raøng buoäc chung cuûa baøi toaùn goác quy  Qua 2 ví duï treân ta coù quy taéc laäp bt ñoái ngaãu nhö sau: ñònh daáu moät raøng buoäc bieán töông öùng cuûa baøi  Haøm muïc tieâu cuûa baøi toaùn goác  min (max) toaùn ñoái ngaãu.  haøm muïc tieâu cuûa baøi toaùn ñoái ngaãu  max (min).  Daáu moät raøng buoäc bieán cuûa baøi toaùn goác quy ñònh  Veùc tô heä soá haøm muïc tieâu cuûa baøi toaùn goác trôû thaønh daáu moät raøng buoäc chung töông öùng cuûa baøi toaùn veùc tô heä soá veá phaûi raøng buoäc chung cuûa baøi toaùn ñoái ñoái ngaãu. ngaãu.  Caùch nhôù: baïn ñoïc neân thuoäc loøng 2 caâu “thaàn  Veùc tô heä soá veá phaûi raøng buoäc chung cuûa baøi toaùn goác chuù”: trôû thaønh veùc tô heä soá haøm muïc tieâu cuûa baøi toaùn ñoái  Baøi toaùn goác min: raøng buoäc chung cuøng daáu, ngaãu. raøng buoäc bieán traùi daáu.  Ma traän heä soá cuûa baøi toaùn goác laáy chuyeån vò trôû thaønh ma traän heä soá cuûa baøi toaùn ñoái ngaãu.  Baøi toaùn goác max: raøng buoäc chung traùi daáu, raøng 7 8 buoäc bieán cuøng daáu. 2
  3. ThS. Phạm Trí Cao * Chương 2 03/01/2014 Quy taéc veà daáu ñöôïc cho trong baûng sau:  II) CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU GOÁC ÑOÁI NGAÃU  Ta nhaän xeùt thaáy: baøi toaùn goác (P) vaø baøi toaùn ñoái ngaãu min max (P*) laø baøi toaùn QHTT. Ta coù theå keû 2 baûng ñôn hình ñeå >= >=0 giaûi 2 baøi toaùn naøy rieâng leû. Tuy nhieân, vieäc naøy seõ phöùc Raøng buoäc chung
  4. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Caùc ñònh lyù ñoái ngaãu:  Töø caùc ñònh lyù treân ta coù keát quaû sau:  Xeùt caëp baøi toaùn ñoái ngaãu:  * Caû hai baøi toaùn cuøng coù pa thì caû 2 baøi  (P) (P*) toaùn cuøng coù patö, vaø giaù trò toái öu cuûa 2 f(x) =  min f*(y) =  max haøm muïc tieâu luoân baèng nhau. xX yY  * Chæ 1 baøi toaùn coù pa thì caû 2 baøi toaùn cuøng khoâng coù patö (giaû söû (P) coù pa thì f(x) khoâng  X laø mieàn raøng buoäc (taäp pa) cuûa baøi toaùn (P). bò chaën döôùi, hoaëc (P*) coù pa thì f*(y) khoâng  Y laø mieàn raøng buoäc cuûa baøi toaùn (P*). bò chaën treân).  * Caû 2 baøi toaùn cuøng khoâng coù pa thì hieån  Chi tieát xem trong saùch. nhieân chuùng cuøng khoâng coù patö. 13 14  Caâu hoûi:  Nhaéc laïi:  Qua caùc keát quaû naøy ta coù caùch ñeå kieåm  Raøng buoäc chaët laø raøng buoäc xaûy ra daáu = tra baøi toaùn coù patö hay khoâng, tröôùc khi  Raøng buoäc loûng laø raøng buoäc xaûy ra daáu baát ñaúng thöùc thöïc söï (< , >) keû baûng ñôn hình giaûi noù. Hoï thöïc hieän  Caùc khaùi nieäm naøy xeùt cho caû raøng buoäc chung vaø ñieàu ñoù nhö theá naøo !? raøng buoäc bieán  ÑL3 (ñoä leäch buø yeáu):  Lôøi giaûi ñaùp xem trong saùch.  x*, y* laø patö cuûa (P), (P*)  x*, y* laø pa cuûa (P), (P*) vaø thoûa ñieàu kieän: Trong caùc caëp raøng buoäc ñoái ngaãu, neáu raøng buoäc naøy laø loûng thì raøng buoäc kia laø chaët. 15 16 4
  5. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Caùch tìm patö cuûa baøi toaùn ñoái ngaãu döïa vaøo Ví duï 2.5: ñònh lyù ñoái ngaãu: Baøi toaùn goác (P)  Töø caùc ñònh lyù ñoái ngaãu treân ta coù caùch laøm nhö f(x) = (6, 2, 5).(x1, x2, x3)  max sau: 2  3 1   x  10    1    Töø patö x* cuûa (P) vaø caùc caëp raøng buoäc ñoái ngaãu,  1 0 2 . x    8    2   ta seõ ñöôïc heä phöông trình tuyeán tính theo y (coù  1 2 5  x    19       caùc aån laø y1, y2, …). Giaûi heä pttt naøy ta ñöôïc    3   nghieäm y*. xj >=0, j= 1,3  Kieåm tra: 1) Giaûi (P) baèng phöông phaùp ñôn hình? Neáu y* laø pa cuûa (P*) thì y* seõ laø patö cuûa (P*), 2) Vieát baøi toaùn ñoái ngaãu (P*), tìm patö cuûa (P*)? vaø hai giaù trò toái öu seõ baèng nhau (f*max = fmin). Giaûi: 17 1) 18 Ta coù patö cuûa (P) laø x*= (4, 0, 2) , f max = 34 Baøi toaùn ñoái ngaãu (P*)  Caùc caëp raøng buoäc ñoái ngaãu:  2x1 + 3x2 + x3 =0 f*(y) = (10, 8, 9).(y1, y2, y3)  min  x1 + 2x3 =0    2 1 1  y   6     x1 + 2x2 + 5x3 =0      1        x1 >=0  2y1 + y2 + y3 >= 6 3 0 2 . y   2    2    x2 >=0  3y1 + 2y3 >= 2      1 2 5  y   5  x3 >=0  y1 + 2y2 + 5y3 >= 5         3   yi >=0, i= 1,3 19 20 5
  6. ThS. Phạm Trí Cao * Chương 2 03/01/2014 Ta coù: Ví duï 2.7: Baøi toaùn goác (P): 2(4) + 3(0) + 2 = 10 (c)   f(x)= (17, 10, 4).(x1,x2,x3)  max 4 + 2(2) = 8 (c)   3  1 7  x   20       1  x2= 0 (c)       1    5 1. x   0       4 + 2(0) + 5(2) = 14 < 19 (l)  y3 = 0    2   4 3 1   x    40        3 x1 = 4 >0 (l)  2y1 + y2 + y3 = 6    x3 = 2 >0 (l)  y1 + 2y2 + 5y3 = 5 x1 =0 Giaûi heä pttt treân ta ñöôïc: y*= (7/3, 4/3, 0). 1) Duøng phöông phaùp ñôn hình giaûi baøi toaùn (P)? Kieåm tra y* laø pa cuûa (P*): ta thaáy y* thoûa taát caû caùc 2) Vieát baøi toaùn ñoái ngaãu (P*), giaûi (P*)? raøng buoäc cuûa baøi toaùn (P*) neân laø pa cuûa (P*). Giaûi: Vaä 21 y y* laø patö duy nhaát cuûa (P*) , f*min = fmax = 34 1) Ta coù patö cuûa (P) laø x*= (0, 13, 1) vaø fmax= 134 22 Baøi toaùn ñoái ngaãu (P*): Ta coù: f*(y)= (20, 0, 40).(y1,y2,y3)  min 3  1 4   y   17  0 + 5(13) + 1 = 66 >0  y2 = 0  1  1  5 3   . y   2     10     x3= 1 >0  7y1 + y2 + y3 = 4       7 1 1   y   4  Ta thaáy ñaây laø heä pttt coù 2 pt, 3 aån. Giaûi heä ta ñöôïc          3    y1 >=0, y2 = 0  y2
  7. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Vaäy ñeå tìm y* thì ta giaûi heä sau: Ví duï 2.9:  7y1 + y2 + y3 = 4 Baøi toaùn goác (P) f = 6x1 + 8x2 + 9x3 + 9x4  max y1 + 5y2 + 3y3 = 10 x    1     y2 =0 2   2 3 1    x   12      2    Giaûi heä treân ta ñöôïc: y*= (1/10, 0, 33/10). Ta 1 3 2 2.   16  x   3   thaáy y* thoûa 2 raøng buoäc (a), (b) coøn laïi neân   2 1 2 2  16     x    y* laø pa cuûa (P*).  4    Vaäy y* laø patö duy nhaát cuûa (P*) vaø f*min = xj >= 0, j= 1,4 fmax = 134. Giaûi bt ñoái ngaãu (P*) baèng caùch duøng ñònh lyù ñoái ngaãu? Giaûi: 25 Duøng pp ÑH giaûi (P) ta ñöôïc x*= (0, 0, 2, 6) , fmax = 72 26 Bt ñoái ngaãu (P*)  x3 = 2>0  3y1 + 2y2 + 2y3 = 9 f* = 12y1 + 16y2 + 16y3  min  x4 = 6>0  y1 + 2y2 + 2y3 = 9 2  1 2    6     Giaûi heä ta ñöôïc: y*= (0, y3+9/2, y3) , vôùi y3IR  y     2   1    Muoán y* laø pa cuûa (P*) thì y* phaûi thoûa 2 raøng 3 1     8   . y       buoäc coøn laïi: 2   2     3 2 9   y     2(0) + (-y3+9/2) + 2y3 >= 6    1  2 2   3    9     2(0) + 3(-y3+9/2) + y3 >= 8 * Caùc caëp raøng buoäc ñoái ngaãu:  ta ñöôïc: 3/2 = 6  Vaäy y*= (0, -y3+9/2, y3) , vôùi y3[3/2, 11/4] laø pa cuûa (P*) neân laø patö cuûa (P*). x2 >=0  2y1 + 3y2 + y3 >= 8  Vaäy y* laø patö toång quaùt cuûa (P*) , f*min = 72 x3 >=0  3y1 + 2y2 + 2y3 >= 9  Baøi toaùn (P*) coù voâ soá patö. x27 4 >=0  y1 + 2y2 + 2y3 >=9 28 7
  8. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Ta thaáy, töø patö cuûa (P) ta suy ra patö cuûa Ví duï 2.10: (P*) baèng caùch giaûi heä pttt. Baøi toaùn (P) f(x)= (2, 3, 2, 5, 6).(x1, x2, x3, x4, x5)  min  Vaán ñeà ñaët ra laø: Neáu (P) coù voâ soá patö thì x   1   moãi patö cuûa (P) coù cho ra 1 patö töông öùng  x  3    20   1 0 1 2    2   cuûa (P*) hay khoâng? Hay moïi patö cuûa (P)    chæ cho ra cuøng 1 patö cuûa (P*)?   1 1 1 0 1  . x   14     3         0   2 1 3 2   x   4 8          Ví duï 2.10:   x   5    Baøi giaûi chi tieát xem trong saùch. 29 30 xj >=0, j= 1,5 Baøi toaùn (P*)  Caùc caëp raøng buoäc ñoái ngaãu:  x1 + x2 + x3  x5 =0         x1 >=0  3y1  y2 =0  y1 + y2  2y3 =0  y2 + y3 =0   y1  3y3 =0  2y1  y2 + 2y3
  9. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Ví duï 2.11: 1) Vôùi x= (0, 6, 6, 0, 7)  Vôùi (P) vaø (P*) cuûa VD 2.10 Thay vaøo caùc caëp raøng buoäc ñoái ngaãu:  1) Xeùt xem x= (0, 6, 6, 0, 7) coù laø patö cuûa (P)?  2) Xeùt xem x= (0, 2, 3, 0, 9) coù laø patö cuûa (P)? 0 + 6 + 6  7 = 5 < 14  y2 =0 x2= 6>0  y1 + y2  2y3 = 3  HD: x3= 6>0  y2 + y3 = 2  Ta duøng keát quaû sau: x5= 7>0  2y1  y2 + 2y3 = 6  x laø pa cuûa (P).  x laø patö cuûa (P)  toàn taïi y laø pa cuûa (P*) Giaûi heä ta coù y*= (1, 0, 2).  (Vôùi y tìm ñöôïc töø x vaø caùc caëp rb buoäc ñoái ngaãu) Ta thaáy y* laø pa cuûa (P*) neân y* laø patö cuûa (P*). 33 Do ñoù x laø patö cuûa (P). 34 2) Vôùi x= (0, 2, 3, 0, 9)  VD 2.12:  Baøi toaùn (P) Thay vaøo caùc caëp raøng buoäc ñoái ngaãu:  f(x) = 3x1 + x2 + 2x3 + 3x4 + 2x5 + 4x6  min 0 + 2 + 3  9 = 4 < 14  y2 =0  2x1 + x3 + x4 + 2x6 = 5 2(2) + 3  3(0) + 2(9) = 17 > 8  y3 = 0  3x1 + x2 + 2x4 + x6 = 11 x1 + 2x4 + x5 + x6 = 5 x2= 2>0  y1 + y2  2y3 = 3   xj >=0 , j= 1,6 x3= 3>0  y 2 + y3 = 2 x5= 9>0  2y1  y2 + 2y3 = 6  x = (5/2, 7/2, 0,0, 5/2, 0) coù laø patö cuûa baøi toaùn (P) khoâng? Giaûi heä, ta coù heä voâ nghieäm.  Baøi giaûi chi tieát xem trong saùch. Vaäy x khoâng laø patö cuûa (P). 35 36 9
  10. ThS. Phạm Trí Cao * Chương 2 03/01/2014 Ví duï 2.13: Baøi toaùn ñoái ngaãu (P*) Baøi toaùn (P) f* = 12y1 + 15y2 + 18y3 + 16y4  max y  f= 8x1 + 6x2 + 9x3  min 3 1 4 2     1     8 3 2 1    12      y     x      2       1     2 1 1 1. 6   y    1 1 2   15  . x   1 2 3 3  3 9        4 1 3   2    18     y       4    x      2 1 3  3      16   yi >=0, i= 1,4 1) Chöùng toû raèng: keû baûng ñôn hình giaûi tröïc tieáp (P) seõ Giaûi baøi toaùn (P*) baèng pp ñôn hình seõ coù 7 bieán. coù 14 bieán? Ta coù patö cuûa bt (P*) laø y*= (11/10, 7/2, 3/10, 0) , f*max 2) Giaûi (P) baèng caùch giaûi baøi toaùn ñoái ngaãu cuûa noù? 37 = 711/10 38  Caùc caëp raøng buoäc ñoái ngaãu: Môøi gheù thaêm trang web:  3x1 + 2x2 + x3 >=12  y1 >=0 40  x1 + x2 + 2x3 >=15  y2 >=0  https://sites.google.com/a/ueh.edu.vn/phamtricao/  4x1 + x2 + 3x3 >=18  y3 >=0  https://sites.google.com/site/phamtricao/  2x1 + x2 + 3x3 >=16  y4 >=0  Ta coù:  y1 = 11/10 >0  3x1 + 2x2 + x3 = 12  y2 = 7/2 >0  x1 + x2 + 2x3 = 15  y3 = 3/10 >0  4x1 + x2 + 3x3 = 18  Giaûi heä ta coù: x*= (-9/10, 9/2, 57/10) 39 Vaäy x* laø patö duy nhaát cuûa (P), fmin = 711/10 10
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