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

GIÁO TRÌNH QUY HOẠCH TUYẾN TÍNH

Chia sẻ: Mrking V2 | Ngày: | Loại File: PDF | Số trang:0

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

Giả sử, một cái túi có thể chứa tối đa b kg (bỏ qua yếu tố thể tích). Có n loại đồ vật T (i 1,n) i = có thể được đưa vào trong túi với khối lượng & giá trị tương ứng là i a và i c . Yêu cầu đặt ra: Cần đặt vào trong túi bao nhiêu đồ vật mỗi loại để cái túi có giá trị lớn nhất.

Chủ đề:

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

Lưu

Nội dung Text: GIÁO TRÌNH QUY HOẠCH TUYẾN TÍNH

  1. Quy hoaïch tuyeán tính Trang 1 CHÖÔNG I BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH BAØI 1. MOÄT SOÁ BAØI TOAÙN DAÃN ÑEÁN BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH 1. Baøi toaùn caùi tuùi Giaû söû, moät caùi tuùi coù theå chöùa toái ña b kg (boû qua yeáu toá theå tích). Coù n loaïi ñoà vaät Ti (i = 1, n) coù theå ñöôïc ñöa vaøo trong tuùi vôùi khoái löôïng & giaù trò töông öùng laø ai vaø ci . Yeâu caàu ñaët ra: Caàn ñaët vaøo trong tuùi bao nhieâu ñoà vaät moãi loaïi ñeå caùi tuùi coù giaù trò lôùn nhaát. Goïi xi laø soá ñoà vaät Ti (i = 1, n) caàn ñaët vaøo tuùi; vôùi ñieàu kieän xi ≥ 0 vaø xi nguyeân. Khi ñoù, moâ hình toaùn caàn laäp coù daïng nhö sau: n f ( x) = ∑ ci xi → max i =1 ⎧ n ⎪∑ ai xi ≤ b ⎨ i =1 ⎪ x ≥ 0 (i = 1, n), nguyen ⎩ i Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. 2. Baøi toaùn laäp keá hoaïch saûn xuaát toái öu Moät doanh nghieäp caàn saûn xuaát n loaïi saûn phaåm P1 ,..., P n töø m loaïi nguyeân lieäu M 1 ,..., M m . Giaù xuaát xöôûng saûn phaåm, tröõ löôïng nguyeân lieäu hieän coù vaø ñònh möùc söû duïng nguyeân lieäu ñeå saûn xuaát caùc loaïi saûn phaåm ñöôïc cho ôû baûng sau: Teân Tröõ löôïng Saûn phaåm nguyeân lieäu nguyeân lieäu P1 P2 … Pn M1 b1 a11 a12 … a1n M2 b2 a21 a22 … a2 n … … … … … … Mm bm am1 am 2 … amn Giaù xuaát xöôûng c1 c2 … cn Ñeå khoâng bò ñoäng trong quaù trình saûn xuaát, doanh nghieäp caàn xaùc ñònh soá löôïng saûn phaåm caàn saûn xuaát moãi loaïi sao cho toång trò giaù xuaát xöôûng laø lôùn nhaát trong phaïm vi tröõ löôïng nguyeân lieäu hieän coù cuûa doanh nghieäp. Haõy laäp moâ hình toaùn ñeå xaùc ñònh soá saûn phaåm ñoù. Goïi xi laø soá saûn phaåm Pi (i = 1, n) caàn phaûi saûn xuaát; vôùi ñieàu kieän xi ≥ 0 . Khi ñoù: n + Trò giaù xuaát xöôûng cuûa doanh nghieäp ñöôïc xaùc ñònh baèng: R = ∑ ci xi ; i =1 + Toång löôïng nguyeân lieäu loaïi M j ( j = 1, m) duøng ñeå saûn xuaát soá saûn phaåm treân laø: n w j = ∑ aij xi ; Trong phaïm vi tröõ löôïng nguyeân lieäu hieän coù cuûa doanh nghieäp, ta caàn i =1 Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  2. Quy hoaïch tuyeán tính Trang 2 xaùc ñònh xi (i = 1, n) sao cho w j ≤ b j ( j = 1, m) ; Do ñoù, moâ hình toaùn ñeå xaùc ñònh soá saûn phaåm caàn saûn xuaát cuûa doanh nghieäp ñöôïc vieát nhö sau: n R = ∑ ci xi → max i =1 ⎧ n ⎪∑ aij xi ≤ b j ( j = 1, m) ⎨ i =1 ⎪ x ≥ 0 (i = 1, n) ⎩ i Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. 3. Baøi toaùn xaùc ñònh khaåu phaàn thöùc aên toái öu Theo lôøi khuyeân cuûa chuyeân gia dinh döôõng, ñeå ñaûm baûo söùc khoeû vaø söï phaùt trieån toát cuûa moät loaïi gia suùc L naøo ñoù, haèng ngaøy, chuû chaên nuoâi caàn cung caáp ñuû caùc loaïi chaát dinh döôõng N1 ,..., N n vôùi khoái löôïng toái thieåu töông öùng b1 ,..., bn . Giaû söû treân thò tröôøng coù m loaïi thöùc aên F1 ,..., Fm vôùi haøm löôïng chaát dinh döôõng trong töøng loaïi vaø giaù mua moãi loaïi ñöôïc cho qua baûng sau: Teân chaát Löôïng Loaïi thöùc aên dinh döôõng toái thieåu F1 F2 … Fm N1 b1 a11 a12 … a1m N2 b2 a21 a22 … a2 m … … … … … … Nn bn an1 an 2 … anm Giaù mua c1 c2 … cm Yeâu caàu ñöôïc ñaët ra laø: Chuû chaên nuoâi caàn phaûi mua moãi loaïi thöùc aên bao nhieâu ñôn vò ñeå khoaûn chi mua thöùc aên thaáp nhaát nhöng vaãn ñaûm baûo chaát dinh döôõng cho gia suùc ñoù theo höôùng daãn cuûa chuyeân gia. Haõy laäp moâ hình toaùn ñeå xaùc ñònh khoái löôïng caàn mua moãi loaïi thöùc aên. Goïi xi (i = 1, m) laø soá ñôn vò caàn mua cuûa loaïi thöùc aên Fi ; vôùi ñieàu kieän xi ≥ 0 . Khi ñoù: m + Toång chi phí mua thöùc aên ñöôïc xaùc ñònh baèng: C = ∑ ci xi ; i =1 m + Toång löôïng chaát dinh döôõng N j ( j = 1, n) coù trong thöùc aên caàn mua laø: w j = ∑ aij xi ; i =1 Do yeâu caàu veà löôïng toái thieåu chaát dinh döôõng caàn cung caáp cho gia suùc, chuû chaên m nuoâi caàn ñaûm baûo raèng: w j = ∑ aij xi ≥b j ( j = 1, n) . i =1 Vaø moâ hình baøi toaùn ñöôïc vieát nhö sau: m C = ∑ ci xi → min i =1 ⎧ m ⎪∑ aij xi ≥b j ( j = 1, n) ⎨ i =1 Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. ⎪ x ≥ 0 (i = 1, m) ⎩ i Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  3. Quy hoaïch tuyeán tính Trang 3 4. Baøi toaùn vaän taûi ñoùng (Baøi toaùn vaän taûi caân baèng thu- phaùt) Giaû söû, coù n kho haøng (traïm phaùt) A1 ,..., An cuøng chöùa moät loaïi haøng vôùi löôïng haøng chöùa töông öùng laø ai (i = 1, n) vaø coù m ñaïi lyù tieâu thuï (traïm thu) B1 ,..., Bm vôùi nhu caàu töông öùng laø b j ( j = 1, m) . Chi phí vaän chuyeån moät ñôn vò haøng hoaù töø traïm Ai ñeán traïm B j laø cij . Haõy laäp keá hoaïch vaän chuyeån heát haøng hoaù töø caùc traïm phaùt ñeán giao heát taïi caùc traïm thu sao cho chi phí vaän chuyeån laø thaáp nhaát. Goïi xij laø löôïng haøng caàn vaän chuyeån töø traïm Ai ñeán B j (i = 1, n, j = 1, m) . Khi ñoù: n m + Toång chi phí vaän chuyeån ñöôïc xaùc ñònh baèng: f ( x) = ∑∑ cij xij ; i =1 j =1 m + Toång löôïng haøng phaùt ñi töø traïm Ai laø: ∑xj =1 ij (i = 1, n) ; n + Toång löôïng haøng thu taïi traïm B j laø: ∑x i =1 ij ( j = 1, m) ; Khi ñoù, moâ hình toaùn caàn laäp nhö sau: n m f ( x) = ∑∑ cij xij → min i =1 j =1 ⎧ m ⎪∑ xij = ai ⎪ j =1 ⎪n ⎪∑ xij = b j ⎨ i =1 ⎪m n ⎪∑ xij = ∑ xij ⎪ j =1 i =1 ⎪ ⎩ xij ≥ 0, (i = 1, n, j = 1, m) Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. 5. Baøi toaùn laäp keá hoaïch ñaàu tö voán cho saûn xuaát Moät doanh nghieäp caàn ñaàu tö voán vaøo n nhaø maùy khaùc nhau ñeå saûn xuaát ra m loaïi saûn phaåm vôùi saûn löôïng toái thieåu töøng loaïi laø Q j ( j = 1, m) . Do trang bò kyõ thuaät- coâng ngheä vaø trình ñoä toå chöùc saûn xuaát cuûa caùc nhaø maùy khaùc nhau neân hieäu quaû cuûa voán ñaàu tö vaøo caùc nhaø maùy khaùc nhau seõ khaùc nhau. Qua khaûo saùt & phaân tích, sau khoaûng thôøi gian nhaát ñònh, moät ñôn vò tieàn ñaàu tö vaøo nhaø maùy i seõ thu ñöôïc aij (i = 1, n, j = 1, m) saûn xuaát saûn phaåm j . Toång löôïng nguyeân lieäu vaø toång lao ñoäng maø doanh nghieäp coù theå cung caáp trong thôøi gian ñoù laàn löôït laø M (ñôn vò) vaø L (ñôn vò). Bieát raèng möùc hao phí veà nguyeân lieäu vaø lao ñoäng taïi nhaø maùy i khi saûn xuaát saûn phaåm j laàn löôït laø bij & cij (i = 1, n, j = 1, m) . Haõy laäp keá hoaïch ñaàu tö sao cho toång voán ñaàu tö laø nhoû nhaát. Goïi xi laø soá voán ñaàu tö vaøo nhaø maùy i; vôùi ñieàu kieän xi ≥ 0 (i = 1, n) . Khi ñoù: + Soá löôïng saûn phaåm j ñöôïc saûn xuaát taïi nhaø maùy i laø aij xi (ñôn vò); + Löôïng nguyeân lieäu söû duïng ñeå saûn xuaát saûn phaåm j taïi nhaø maùy i laø aij xi bij ; Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  4. Quy hoaïch tuyeán tính Trang 4 + Löôïng nguyeân lieäu söû duïng ñeå saûn xuaát m loaïi saûn phaåm taïi nhaø maùy i laø m ∑a j =1 xb ; ij i ij + Toång nguyeân lieäu söû duïng ñeå saûn xuaát m loaïi saûn phaåm taïi n nhaø maùy laø n m ∑∑ a i =1 j =1 xb ; ij i ij + Töông töï, toång lao ñoäng söû duïng ñeå saûn xuaát m loaïi saûn phaåm taïi n nhaø maùy laø n m ∑∑ a i =1 j =1 xc ; ij i ij n + Toång löôïng saûn phaåm j ñöôïc saûn xuaát töø n nhaø maùy ñöôïc tính baèng: ∑a i =1 x ; ij i Do ñoù, moâ hình toaùn ñöôïc vieát nhö sau: n f ( x) = ∑ xi → min i =1 ⎧ n m ⎪∑∑ aij xi bij ≤ M ⎪ i =1 j =1 ⎪n m ⎪∑∑ aij xi cij ≤ L ⎨ i =1 j =1 ⎪n ⎪∑ aij xi ≥ Q j ( j = 1, m) ⎪ i =1 ⎪ ⎩ xi ≥ 0 (i = 1, n) Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  5. Quy hoaïch tuyeán tính Trang 5 BAØI 2. CAÙC KHAÙI NIEÄM CÔ BAÛN VEÀ BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH 1. Ñònh nghóa baøi toaùn quy hoaïch tuyeán tính Baøi toaùn quy hoaïch tuyeán tính daïng toång quaùt (G) laø baøi toaùn coù daïng sau: n f ( x) = ∑ ci xi → max (min) (1) i =1 ⎧n ⎡≤ ⎤ ⎪ ⎢ ⎥ ⎪∑ aij xi ⎢≥ ⎥b j ( j = 1, m) (2) ⎪ i =1 ⎢⎣=⎥⎦ ⎪ ⎨ ⎪ ⎡≤ 0 ⎤ ⎪ x ⎢≥ 0 ⎥ (i = 1, n) (3) ⎪ i⎢ ⎥ ⎪⎩ ⎣ ⎢tuy y ⎥ ⎦ Trong ñoù: + (1) ñöôïc goïi laø haøm muïc tieâu cuûa baøi toaùn vaø f (x) laø moät haøm baäc nhaát theo caùc aån cuûa baøi toaùn. Neáu f ( x) → max thì baøi toaùn ñoù ñöôïc goïi laø baøi toaùn cöïc ñaïi; coøn neáu f ( x) → min thì baøi toaùn ñoù ñöôïc goïi laø baøi toaùn cöïc tieåu; + (2) laø moät heä goàm caùc phöông trình hay baát phöông trình baäc nhaát theo caùc aån cuûa baøi toaùn vaø ñöôïc goïi laø heä raøng buoäc chính cuûa baøi toaùn. + (3) laø caùc ñieàu kieän veà daáu cuûa caùc aån vaø ñöôïc goïi laø heä raøng buoäc daáu cuûa baøi toaùn. Neáu aån coù daáu tuyø yù thì coù theå khoâng ñöa vaøo heä (3); Neáu baøi toaùn khoâng coù heä (3) thì ta hieåu raèng toaøn boä aån ñeàu coù daáu tuyø yù. + Heä (2) vaø (3) ñöôïc goïi laø chung laø heä raøng buoäc cuûa baøi toaùn. 2. Caùc khaùi nieäm lieân quan + Ñoái vôùi baøi toaùn quy hoaïch tuyeán tính (G) n aån nhö treân, neáu toàn taïi moät vector n- chieàu x = ( x1 , x2 ,..., xn ) thoaû maõn heä raøng buoäc cuûa baøi toaùn (G) thì vector ñoù ñöôïc goïi laø moät phöông aùn cuûa baøi toaùn hay laø moät lôøi giaûi chaáp nhaän ñöôïc. + Taäp hôïp taát caû caùc phöông aùn cuûa baøi toaùn (G) ñöôïc goïi laø taäp phöông aùn cuûa (G) vaø ñöôïc kyù hieäu laø taäp X. Taäp X coù theå laø taäp roãng hay coù 1 phaàn töû hay coù voâ soá phaàn töû. + Phöông aùn x* thoaû maõn ñaúng thöùc “=” moät raøng buoäc naøo ñoù trong heä raøng buoäc thì ta noùi phöông aùn x* thoaû maõn chaët raøng buoäc ñoù. + Phöông aùn x thoaû maõn baát ñaúng thöùc “>” hoaëc “
  6. Quy hoaïch tuyeán tính Trang 6 nhaát (giaù trò nhoû nhaát) treân taäp phöông aùn X cuûa baøi toaùn (G). Khi ñoù, f(x0) ñöôïc goïi laø giaù trò toái öu cuûa baøi toaùn. Neáu phöông aùn toái öu x0 laø moät phöông aùn cô baûn thì x0 ñöôïc goïi laø phöông aùn cô baûn toái öu. + Baøi toaùn quy hoaïch tuyeán tính coù ít nhaát moät phöông aùn toái öu ñöôïc goïi laø baøi toaùn giaûi ñöôïc. + Baøi toaùn quy hoaïch tuyeán tính khoâng coù phöông aùn hoaëc coù phöông aùn maø haøm muïc tieâu khoâng bò chaën treân (ñoái vôùi baøi toaùn cöïc ñaïi) hay khoâng chaën döôùi (ñoái vôùi baøi toaùn cöïc tieåu) treân taäp phöông aùn cuûa baøi toaùn thì ñöôïc goïi laø baøi toaùn khoâng giaûi ñöôïc. + Giaûi moät baøi toaùn quy hoaïch tuyeán tính laø vieäc ñi tìm lôøi giaûi toái öu (phöông aùn toái öu vaø giaù trò toái öu) cuûa baøi toaùn hay chöùng minh baøi toaùn khoâng giaûi ñöôïc. Ví duï 1: Xeùt baøi toaùn quy hoaïch tuyeán tính (F) nhö sau: f ( x) = 2 x1 + x2 − 3x3 + x4 → max ⎧ x1 + 2 x2 − x3 = 4 ⎪2 x − x + 3 x = 4 ⎪ 1 2 4 ⎨ ⎪ x 2 + 2 x3 − x 4 = 1 ⎪⎩ x1 , x2 , x3 , x4 ≥ 0 Giaûi heä raøng buoäc cuûa baøi toaùn, ta coù taäp phöông aùn: ⎧⎪⎛ 29 7α 5 2α 1 α ⎞ ⎡ 29 ⎤ ⎫⎪ X = ⎨⎜ − , + , + ,α ⎟ α ∈ ⎢0, ⎥⎬ ⎪⎩⎝ 12 6 6 3 12 6 ⎠ ⎣ 14 ⎦ ⎪⎭ ⎛ 29 5 1 ⎞ • Vôùi α = 0 , ta coù phöông aùn x 0 = ⎜ , , , 0 ⎟ thoaû maõn chaët 3 raøng buoäc ⎝ 12 6 12 ⎠ chính vaø moät raøng buoäc veà daáu cuûa x4 neân x0 laø moät phöông aùn cô baûn cuûa baøi toaùn (F). Ñoàng thôøi x0 laø moät phöông aùn cô baûn khoâng suy bieán. ⎛ 1 13 5 ⎞ • Vôùi α = 2 , ta coù phöông aùn x* = ⎜ , , , 2 ⎟ thoaû maõn chaët 3 raøng buoäc ⎝ 12 6 12 ⎠ chính vaø thoaû maõn loûng 4 raøng buoäc veà daáu cho neân x* khoâng phaûi laø moät phöông aùn cô baûn cuûa baøi toaùn (F). • Vôùi taäp phöông aùn X, ta coù haøm muïc tieâu nhö sau: 65 7α ⎛ ⎡ 29 ⎤ ⎞ f ( x) = − → max ⎜⎜ α ∈ ⎢0, ⎥ ⎟⎟ 12 6 ⎝ ⎣ 14 ⎦ ⎠ 65 7α 65 ⎡ 29 ⎤ 0 Ta coù f ( x) = − ≤ = f (x0 ) ∀α ∈ ⎢0, ⎥ ; do ñoù, x laø phöông aùn cô baûn toái 12 6 12 ⎣ 12 ⎦ 65 öu vaø giaù trò f ( x 0 ) = laø giaù trò toái öu cuûa baøi toaùn (F). 12 Ví duï 2: Xeùt baøi toaùn (F) treân nhöng khoâng coù heä raøng buoäc daáu, töùc laø caùc aån coù daáu tuyø yù. Khi ñoù, taäp phöông aùn cuûa baøi toaùn seõ laø: ⎧⎛ 29 7α 5 2α 1 α ⎞⎫ 65 7α X = ⎨⎜ − , + , + ,α ⎟⎬ vaø haøm muïc tieâu f ( x) = − → max ; ⎩⎝ 12 6 6 3 12 6 ⎠⎭ 12 6 Khi α → −∞ thì f (x) → +∞ ; töùc laø f(x) khoâng bò chaën treân treân taäp phöông aùn cuûa baøi toaùn; do ñoù, baøi toaùn khoâng coù phöông aùn toái öu hay baøi toaùn khoâng giaûi ñöôïc. Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  7. Quy hoaïch tuyeán tính Trang 7 3. Tính chaát cuûa baøi toaùn quy hoaïch tuyeán tính Tính chaát 1: Neáu moät baøi toaùn quy hoaïch tuyeán tính coù phöông aùn thì noù seõ coù phöông aùn cô baûn vaø soá phöông aùn cô baûn cuûa baøi toaùn luoân höõu haïn. (Ñieàu naøy ñöôïc ruùt ra töø cô sôû: trong heä raøng buoäc chính cuûa baøi toaùn, ta chæ coù theå ruùt ra moät soá höõu haïn vectô ñoäc laäp tuyeán tính maø thoâi). Tính chaát 2: Neáu baøi toaùn cöïc ñaïi (cöïc tieåu) coù phöông aùn vaø haøm muïc tieâu bò chaën treân (chaën döôùi) treân taäp phöông aùn thì baøi toaùn ñoù coù phöông aùn toái öu. Tính chaát 3: Neáu baøi toaùn coù phöông aùn toái öu thì noù coù phöông aùn cô baûn toái öu. Tính chaát 4: Neáu baøi toaùn quy hoaïch tuyeán tính coù hôn 1 phöông aùn toái öu thì baøi toaùn seõ coù voâ soá phöông aùn toái öu. Giaû söû baøi toaùn coù 2 phöông aùn toái öu laø x0 vaø x* thì moïi vectô x coù daïng sau ñeàu laø phöông aùn toái öu cuûa baøi toaùn: x = αx 0 + (1 − α ) x * ; (α ∈ [0, 1]) Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  8. Quy hoaïch tuyeán tính Trang 8 BAØI 3. CAÙC DAÏNG ÑAËC BIEÄT CUÛA BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH 1. Baøi toaùn quy hoaïch tuyeán tính daïng chính taéc a) Ñònh nghóa: Baøi toaùn quy hoaïch tuyeán tính daïng chính taéc laø baøi toaùn quy hoaïch tuyeán tính coù caùc raøng buoäc chính laø caùc phöông trình vaø caùc aån ñeàu khoâng aâm. b) Daïng chính taéc: n f ( x) = c1 x1 + c2 x2 + ... + cn xn → max (min) f ( x) = ∑ ci xi → max (min) i =1 ⎧ ⎪a11 x1 + a12 x2 + ... + a1n xn = b1 ⎪a21 x1 + a22 x2 + ... + a2 n xn = b2 ⎧n ⎪ ⎪∑ a ji xi = b j ( j = 1, m) ⎨................... ⎨ i =1 ⎪a x + a x + ... + a x = b ⎪ x ≥ 0 (i = 1, n) ⎪ m1 1 m2 2 mn n m ⎩ i ⎪ x ≥ 0 (i = 1, n) ⎩ i Daïng ruùt goïn c) Ma traän ñieàu kieän & Vector ñieàu kieän Ma traän caùc heä soá cuûa raøng buoäc chính trong baøi toaùn quy hoaïch tuyeán tính chính taéc ñöôïc goïi laø ma traän ñieàu kieän, ñöôïc kyù hieäu laø A. Coät heä soá cuûa aån xi trong ma traän ñieàu kieän A ñöôïc goïi laø coät ñieàu kieän (vector ñieàu kieän) cuûa aån xi vaø kyù hieäu laø Ai. ⎡a11 a12 ... a1n ⎤ ⎡a1i ⎤ ⎢a a22 ... a2 n ⎥⎥ ⎢a ⎥ A= ⎢ 21 Ai = ⎢ 2 i ⎥ ⎢............................. ⎥ ⎢... ⎥ ⎢ ⎥ ⎢ ⎥ ⎣am1 am 2 ... amn ⎦ ⎣ami ⎦ d) Ñònh lyù Cho baøi toaùn quy hoaïch tuyeán tính daïng chính taéc nhö sau: n f ( x) = ∑ ci xi → max (min) i =1 ⎧n ⎪∑ a ji xi = b j ( j = 1, m) ⎨ i =1 ⎪ x ≥ 0 (i = 1, n) ⎩ i Ñieàu kieän caàn vaø ñuû ñeå phöông aùn x* = ( x1* , x2* ,..., xn* ) laø moät phöông aùn cô baûn cuûa { } baøi toaùn laø heä vector ñieàu kieän Ai xi* > 0 ñoäc laäp tuyeán tính. Moät heä caùc vector {v1, v2, …, vn} trong khoâng gian vector V ñöôïc goïi laø ñoäc laäp tuyeán tính khi n vaø chæ khi phöông trình vector ∑k v i =1 i i = 0 chæ coù nghieäm duy nhaát: k1 = k2 = ... = kn = 0. e. Bieán ñoåi baøi toaùn veà daïng chính taéc Moïi baøi toaùn quy hoaïch tuyeán tính ñeàu coù theå ñöôïc ñöa veà daïng chính taéc baèng caùc bieän phaùp sau: @ Heä raøng buoäc chính coù baát phöông trình: ta theâm vaøo nhöõng raøng buoäc baát phöông trình ñoù caùc aån phuï khoâng aâm ñeå ñöa raøng buoäc ñoù veà phöông trình; nguyeân taéc theâm aån phuï nhö sau: Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  9. Quy hoaïch tuyeán tính Trang 9 n + Neáu raøng buoäc chính coù daïng ∑a i =1 x ≤ b j thì ta coäng vaøo veá traùi cuûa raøng buoäc ji i n naøy moät aån khoâng aâm xn + k ñeå raøng buoäc chính trôû thaønh ∑a i =1 x + xn + k = b j . ji i n + Neáu raøng buoäc chính coù daïng ∑a i =1 x ≥ b j thì ta tröø vaøo veá traùi cuûa raøng buoäc naøy ji i n moät aån khoâng aâm xn + k ñeå raøng buoäc chính trôû thaønh ∑a i =1 x − xn + k = b j . ji i + Neáu soá haïng töï do ôû raøng buoäc j aâm (b j < 0) thì ta tieán haønh ñoåi daáu hai veá sao soá haïng töï do naøy khoâng aâm tröôùc khi tieán haønh theâm aån phuï (ñoái vôùi raøng buoäc baát phöông trình). Caùc bieán phuï chæ laø nhöõng ñaïi löôïng giuùp ta bieán caùc raøng buoäc daïng baát ñaúng thöùc thaønh ñaúng thöùc, noù phaûi khoâng aûnh höôûng gì ñeán haøm muïc tieâu neân khoâng xuaát hieän trong haøm muïc tieâu. @ Raøng buoäc veà daáu khoâng thoaû ñieàu kieän khoâng aâm (aån coù daáu tuyø yù hay ≤ 0 ) + Neáu aån xi ≤ 0 thì ta thöïc hieän pheùp ñoåi bieán soá xi = − xi' vôùi ñieàu kieän xi' ≥ 0 . + Neáu aån xi coù daáu tuyø yù thì ta thöïc hieän pheùp ñoåi bieán xi = xi' − xi'' vôùi ñieàu kieän xi' , xi'' ≥ 0 . * Ghi chuù: - Baøi toaùn ñaõ cho ñöôïc goïi laø baøi toaùn goác. Baøi toaùn sau khi bieán ñoåi ñöôïc goïi laø baøi toaùn phuï. - Baøi toaùn phuï coù hay khoâng coù phöông aùn toái öu thì baøi toaùn goác cuõng coù hay khoâng coù phöông aùn toái öu töông öùng. Neáu coù phöông aùn toái öu, phöông aùn toái öu cuûa baøi toaùn goác ñöôïc ruùt ra töø baøi toaùn phuï baèng caùch boû ñi phaàn aån phuï vaø ñoåi caùc trò soá cuûa bieán môùi veà bieán cuõ theo caùc coâng thöùc ñoåi bieán ñaõ duøng. ** Ví duï 1: Bieán ñoåi baøi toaùn sau veà daïng chính taéc f ( x) = 2 x1 − x2 + 2 x3 + x4 − 2 x5 → min ⎧ x1 − 2 x2 + x3 + 2 x4 + x5 ≤ 7 ⎪ x + 2 x + x ≥ −1 ⎪ 2 3 4 ⎪⎪2 x3 + x4 + 3 x5 ≥ 10 ⎨ ⎪ x1 + x2 − 2 x3 + x4 = 20 ⎪x , x ≥ 0 ⎪ 1 5 ⎪⎩ x4 ≤ 0 Giaûi: f ( x) = 2x 1 − ( x 2' − x 2' ' ) + 2( x 3' − x 3' ' ) − x 4' − 2 x 5 → min ⎧ x4 = − x4' ⎧x 1 − 2( x 2' − x 2' ' ) + ( x 3' − x 3' ' ) − 2x 4' + x 5 + x 6 = 7 ⎪ ⎪ ⎪ x = x − x2 ' '' ⎪− ( x 2 − x 2 ) − 2( x 3 − x 3 ) + x 4 + x 7 = 1 ' '' ' '' ' Ñaët ⎨ 2 2' Khi ñoù ⎪ ' ⎪ 3 x = x 3 − x '' 3 ⎨2( x 3 − x 3 ) − x 4 + 3x 5 − x 8 = 10 '' ' ⎪ x ' , x ' ' , x ' , x '' , x ' ≥ 0 ⎪ ⎪x 1 + ( x 2 − x 2 ) − 2( x 3 − x 3 ) − x 4 = 20 ' '' ' '' ' ⎩ 2 2 3 3 4 ⎪x , x ' , x ' ' , x ' , x ' ' , x ' , x , x , x , x ≥ 0 ⎩ 1 2 2 3 3 4 5 6 7 8 Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  10. Quy hoaïch tuyeán tính Trang 10 ** Ví duï 2: Ñöa baøi toaùn quy hoaïch tuyeán tính sau veà daïng chính taéc f ( x) = 2x1 + x2 − x3 + 3x4 − 8 → max ⎧2x1 − 3x2 + x3 + 2 x4 ≥ 4 ⎪ x − 2 x + 5x ≤ 9 ⎪1 2 3 (Sinh vieân töï giaûi) ⎨ ⎪2x2 − 3x3 − x4 ≥ −2 ⎪x , x ≥ 0 ⎩1 3 2. Baøi toaùn quy hoaïch tuyeán tính daïng chuaån taéc a) Ñònh nghóa: Baøi toaùn quy hoaïch tuyeán tính daïng chuaån taéc laø moät baøi toaùn quy hoaïch tuyeán tính daïng chính taéc trong ñoù heä raøng buoäc chính coù caùc soá haïng töï do ñeàu khoâng aâm vaø moãi raøng buoäc chính ñeàu coù moät aån cô baûn. Ñoù laø aån coù heä soá laø 1 ôû moät raøng buoäc chính vaø coù heä soá laø 0 ôû caùc raøng buoäc coøn laïi. AÅn cô baûn naèm ôû raøng buoäc thöù i ñöôïc goïi laø aån cô baûn thöù i, caùc aån coøn laïi cuûa baøi toaùn ñöôïc goïi laø aån töï do. b) Daïng cuûa baøi toaùn: n f ( x) = ∑ci xi → max (min) i =1 ⎧ n−m ⎪ k ∑akm+ j xm+ j = bk (k = 1, m; j = 1, n − m) x + ⎨ j =1 ⎪x ≥ 0 (i = 1, n) ⎩ i Trong ñoù, xk (k = 1, m) ñöôïc goïi laø aån cô baûn thöù k; caùc aån coøn laïi x j ( j = m + 1, n) ñöôïc goïi laø aån töï do. Baøi toaùn quy hoaïch tuyeán tính daïng chuaån coù ma traän ñieàu kieän nhö sau: ⎡1 0 ... 0 a1m+1 a1m+2 ... a1n ⎤ ⎢0 1 ... 0 a ⎥ ⎢ 2m+1 a2m+2 ... a2n ⎥ A= ⎢KKKKKKKKKKKKKKKK⎥ ⎢ ⎥ ⎣0 0 ... 1 amm+1 amm+2 ... amn ⎦ Ta thaáy ma traän A chöùa moät ma traän ñôn vò caáp m. Vaø neáu ta cho caùc aån töï do nhaän giaù trò 0 vaø caùc aån cô baûn nhaän trò soá baèng soá haïng töï do öùng vôùi aån cô baûn ñoù thì ta coù moät phöông aùn cô baûn cuûa baøi toaùn vaø phöông aùn cô baûn ñoù ñöôïc goïi laø phöông aùn cô baûn xuaát phaùt cuûa baøi toaùn. c) Ví duï: Xeùt baøi toaùn quy hoaïch tuyeán tính sau: f ( x) = 5 x1 + 2 x2 − 4 x3 + x4 → max ⎧x1 − 2x2 + x4 = 7 ⎪3x + x − x = 5 ⎪ 2 3 4 ⎨2x − 3x + x = 3 ⎪ 2 4 5 ⎪x ≥ 0 (i = 1,5) ⎩ i Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  11. Quy hoaïch tuyeán tính Trang 11 ⎡1 − 2 0 1 0⎤ Ma traän ñieàu kieän cuûa baøi toaùn: A = ⎢0 3 1 − 1 0 ⎥⎥ . Ma traän naøy chöùa ma traän ⎢ ⎢⎣0 2 0 − 3 1⎥⎦ ñôn vò caáp 3 vôùi caùc aån cô baûn laø x1, x3, x5. Caùc aån coøn laïi x2, x4 ñöôïc goïi laø aån töï do. Vaø phöông aùn cô baûn xuaát phaùt laø x = (7, 0, 5, 0, 3). d) Bieán ñoåi baøi toaùn veà daïng chuaån Vôùi baøi toaùn quy hoaïch tuyeán tính daïng chính taéc nhöng chöa coù daïng chuaån thì ta coù theå ñöa veà daïng chuaån baèng caùch coäng moät aån giaû khoâng aâm vaøo veá traùi cuûa raøng buoäc chaët khoâng coù aån cô baûn. Khi ñoù, trong haøm muïc tieâu cuûa baøi toaùn, heä soá cuûa aån giaû theâm vaøo seõ laø –M (neáu laø baøi toaùn cöïc ñaïi) hay +M (neáu laø baøi toaùn cöïc tieåu) vôùi M laø moät soá döông lôùn tuyø yù. Ví duï: Xeùt baøi toaùn quy hoaïch tuyeán tính nhö sau: f ( x) = 2 x1 + x2 − 3x3 + x4 → max ⎧x1 + 2x2 − x3 = 4 ⎪2x − x + 3x = 4 ⎪ 1 2 4 ⎨ ⎪x2 + 2x3 − x4 = 1 ⎪⎩x1, x2 , x3 , x4 ≥ 0 Ñaây laø baøi toaùn quy hoaïch tuyeán tính daïng chính taéc. Do heä raøng buoäc chính khoâng chöùa vector ñôn vò naøo cho neân, ñeå ñöa veà daïng chuaån, ta coäng vaøo veá traùi laàn löôït caùc aån giaû x5 , x6 , x7 ≥ 0 ; khi ñoù baøi toaùn coù daïng chuaån nhö sau: f ( x) = 2 x1 + x2 − 3x3 + x4 − M ( x5 + x6 + x7 ) → max ⎧x1 + 2x2 − x3 + x5 = 4 ⎪2x − x + 3x + x = 4 ⎪ 1 2 4 6 ⎨ ⎪x2 + 2x3 − x4 + x7 = 1 ⎪x ≥ 0 (i = 1,7) ⎩ i ** Ghi chuù: Baøi toaùn sau khi theâm aån giaû ñöôïc goïi laø baøi toaùn môû roäng hay baøi toaùn “M”. Do caùc aån giaû coù xuaát hieän trong haøm muïc tieâu cuûa baøi toaùn cho neân baøi toaùn môû roäng vaø baøi toaùn goác khoâng töông ñöông. Hai baøi toaùn naøy coù quan heä vôùi nhau nhö sau: + Neáu baøi toaùn môû roäng khoâng coù phöông aùn toái öu (khoâng giaûi ñöôïc) thì baøi toaùn goác cuõng khoâng coù phöông aùn toái öu (khoâng giaûi ñöôïc). + Neáu baøi toaùn môû roäng coù phöông aùn toái öu, trong ñoù taát caû caùc aån giaû ñeàu nhaän trò soá 0 thì baøi toaùn goác cuõng coù phöông aùn toái öu. Phöông aùn toái öu cuûa baøi toaùn goác ñöôùc ruùt ra töø phöông aùn toái öu cuûa baøi toaùn môû roäng baèng caùch boû ñi phaàn aån giaû vaø aån phuï (neáu coù). + Neáu baøi toaùn môû roäng coù phöông aùn toái öu nhöng toàn taïi ít nhaát 1 aån giaû coù giaù trò döông thì baøi toaùn goác khoâng coù phöông aùn (khoâng giaûi ñöôïc). Ví duï: Ñöa baøi toaùn quy hoaïch tuyeán tính sau veà daïng chuaån: f ( x) = 2 x1 + x2 − 3x3 + x4 → min Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  12. Quy hoaïch tuyeán tính Trang 12 ⎧ x1 + 2 x2 − x3 ≥ 4 ⎪2 x − x + 3 x ≤ 4 ⎪ 1 2 4 ⎨ ⎪ x2 + 2 x3 − x4 ≥ −1 ⎪⎩ x1 , x2 , x3 , x4 ≥ 0 Ta ñöa heä raøng buoäc cuûa baøi toaùn veà caùc phöông trình nhö sau: ⎧ x1 + 2 x2 − x3 − x5 = 4 ⎪2 x − x + 3 x + x = 4 ⎡1 2 − 1 0 − 1 0 0⎤ ⎪ 1 2 ⎢ ⎨− x − 2 x + x + x = 1 vôùi ma traän ñieàu kieän A = ⎢2 − 1 0 3 0 1 0 ⎥⎥ . 4 6 ⎪ 2 3 4 7 ⎢⎣0 − 1 − 2 1 0 0 1⎥⎦ ⎪ x ≥ 0 (i = 1,7) ⎩ i Trong ñoù, x5, x6, x7 laø caùc aån phuï. Ma traän A chæ chöùa 1 ma traän ñôn vò caáp 2 vôùi hai aån cô baûn laø x6, x7. Do ñoù, ta caàn theâm moät aån giaû x8 vaøo phöông trình thöù nhaát vaø khi ñoù, baøi toaùn seõ coù daïng chuaån nhö sau: f ( x) = 2 x1 + x2 − 3x3 + x4 + Mx8 → min ⎧ x1 + 2 x2 − x3 − x5 + x8 = 4 ⎪2 x − x + 3 x + x = 4 ⎪ 1 2 4 6 ⎨− x − 2 x + x + x = 1 ⎪ 2 3 4 7 ⎪ x ≥ 0 (i = 1,8) ⎩ i Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  13. Quy hoaïch tuyeán tính Trang 13 BAØI 4. GIAÛI BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH BAÈNG PHÖÔNG PHAÙP HÌNH HOÏC Do tính phöùc taïp cuûa vieäc bieåu dieãn hình hoïc vôùi caùc baøi toaùn coù nhieàu aån soá vaø döïa vaøo nhaän ñònh tröïc quan, vieäc giaûi baøi toaùn quy hoaïch tuyeán tính baèng hình hoïc thöôøng thích hôïp trong vieäc giaûi caùc baøi toaùn coù 2 aån soá. Vaø do ñoù, trong phaàn naøy, ta xeùt phöông phaùp naøy ñoái vôùi baøi toaùn quy hoaïch tuyeán tính 2 aån. 1. Giaûi baøi toaùn quy hoaïch tuyeán tính baèng phöông phaùp hình hoïc Xeùt baøi toaùn sau: f ( x) = Ax + By → max ⎧n ⎪∑ ai x + bi y ≤ ci (i = 1, n) ⎨ i =1 ⎪ x, y ≥ 0 ⎩ Bieåu dieãn trong maët phaúng R2 heä toaï ñoä vuoâng goùc Oxy. Ta bieát raèng, trong heä toaï ñoä ñoù, ñöôøng thaúng ñöôïc bieåu dieãn baèng phöông trình ax + by = c vaø moãi ñieåm treân ñöôøng thaúng laø nghieäm cuûa phöông trình ñoù. Moãi baát phöông trình trong heä raøng buoäc seõ xaùc ñònh moät nöûa maët phaúng. Giao giöõa n nöûa maët phaúng laø mieàn cuûa caùc phöông aùn. Moãi ñieåm F(x,y) treân mieàn naøy laø moät phöông aùn cuûa baøi toaùn. Mieàn naøy coù theå khoâng toàn taïi, coù theå chæ laø moät ñieåm hay coù theå laø moät ña giaùc loài (bò chaën) hay khuùc loài (khoâng bò chaën). Khi mieàn phöông aùn laø moät ña giaùc loài (ña giaùc naèm veà moät phía cuûa ñöôøng thaúng chöùa baát kyø caïnh naøo cuûa ña giaùc), moãi ñænh cuûa ña giaùc laø moät phöông aùn cô baûn. Do soá raøng buoäc cuûa baøi toaùn laø höõu haïn cho neân ña giaùc loài cuõng seõ coù höõu haïn ñænh. Vieäc giaûi baøi toaùn quy hoaïch tuyeán tính baèng phöông phaùp hình hoïc laø vieäc thöïc hieän pheùp tònh tieán ñöôøng thaúng Ax + By = c vuoâng goùc vôùi vectô phaùp tuyeán n = ( A, B) (song song vôùi ñöôøng thaúng Ax + By = 0) vaø xaùc ñònh giaù trò lôùn nhaát cuûa c (ñoái vôùi baøi toaùn cöïc ñaïi) hoaëc giaù trò nhoû nhaát cuûa c (ñoái vôùi baøi toaùn cöïc tieåu) treân mieàn caùc phöông aùn cuûa baøi toaùn. 2. Phöông phaùp giaûi Vôùi baøi toaùn quy hoaïch tuyeán tính 2 aån soá, vieäc giaûi baøi toaùn ñöôïc tieán haønh qua caùc böôùc sau: Böôùc 1: Bieåu dieãn taäp phöông aùn X (mieàn taäp phöông aùn) treân heä toaï ñoä Oxy. Böôùc 2: Bieåu dieãn vector phaùp tuyeán n = ( A, B) treân heä toaï ñoä Oxy. Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  14. Quy hoaïch tuyeán tính Trang 14 Böôùc 3: Tònh tieán ñöôøng thaúng (d2): Ax + By = c vuoâng goùc vôùi vector phaùp tuyeán n = ( A, B) theo caùc nguyeân taéc: “Tònh tieán cuøng chieàu vôùi n ñoái vôùi baøi toaùn cöïc ñaïi hay tònh tieán ngöôïc chieàu vôùi n ñoái vôùi baøi toaùn cöïc tieåu”; sau ñoù tìm tieáp ñieåm giöõa ñöôøng thaúng (d2) vôùi mieàn phöông aùn X. + Neáu (d2) luoân giao vôùi mieàn X thì baøi toaùn khoâng coù phöông aùn toái öu (khoâng giaûi ñöôïc). + Neáu (d2) tieáp xuùc vôùi X taïi moät ñieåm hay moät ñoaïn thaúng thì baøi toaùn seõ coù moät phöông aùn toái öu duy nhaát hay coù voâ soá phöông aùn toái öu vôùi hai ñaàu ñoaïn thaúng ñoù laø hai phöông aùn cô baûn toái öu cuûa baøi toaùn. Ta xaùc ñònh toaï ñoä cuûa tieáp ñieåm ñeå ñöa ra nghieäm cuûa baøi toaùn. 3. Caùc ví duï @ Ví duï 1: Giaûi baøi toaùn sau ñaây baèng phöông phaùp hình hoïc: f ( x) = 4 x + 5 y → max (min) ⎧2 x + y ≤ 8 ⎪x + 2 y ≥ 7 ⎪ ⎨ ⎪y ≤ 4 ⎪⎩ x, y ≥ 0 Giaûi: Bieåu dieãn mieàn phöông aùn cuûa baøi toaùn treân heä toaï ñoä Oxy ta ñöôïc töù giaùc loài ABCD vaø toaï ñoä caùc ñænh laø A(2,4), B(0,4), C(0, 3/2) vaø D(3,2). Bieåu dieãn vectô phaùp tuyeán n = (4,5) vaø haøm muïc tieâu baèng ñöôøng thaúng 4x+5y=c vaø tieán haønh tònh tieán ñöôøng thaúng naøy vuoâng goùc vôùi vectô phaùp tuyeán vaø ta xaùc ñònh nghieäm cuûa baøi toaùn cöïc ñaïi laø (2, 4) vôùi giaù trò cöïc ñaïi laø f(x)=28 vaø nghieäm cuûa baøi toaùn cöïc tieåu laø (0, 3/2) vôùi giaù trò cöïc tieåu laø f(x)= 15/2. @ Ví duï 2: Giaûi baøi toaùn sau baèng phöông phaùp hình hoïc f ( x) = 8 x1 + 7 x2 + x3 + x4 → min ⎧10 x1 + 11x2 − x3 − x4 − x5 = 400 ⎪4 x − x − x − x + x = 40 ⎪ 1 2 (Sinh vieân töï giaûi) 3 4 5 ⎨2 x + 3 x − x + x − x = 80 ⎪ 1 2 3 4 5 ⎪ x ≥ 0 (i = 1,5) ⎩ i Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  15. Quy hoaïch tuyeán tính Trang 15 BAØI 5. GIAÛI BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH BAÈNG PHÖÔNG PHAÙP ÑÔN HÌNH Phöông phaùp ñôn hình ñöôïc George Bernard Dantzig ñöa ra naêm 1947 cuøng luùc vôùi vieäc oâng khai sinh ra quy hoaïch tuyeán tính. Ñaây laø moät phöông phaùp thöïc söï coù hieäu quaû ñeå giaûi nhöõng baøi toaùn quy hoaïch tuyeán tính côû lôùn trong thöïc teá. Hieän nay, caùc chöông trình giaûi baøi toaùn Quy hoaïch tuyeán tính treân maùy tính ñeàu söû duïng phöông phaùp naøy. Vaø söû duïng phöông phaùp ñôn hình, chuùng ta coù theå töï thieát keá, vieát chöông trình theo yù mình ñeå giaûi baøi toaùn Quy hoaïch tuyeán tính treân maùy tính. Noäi dung cô baûn cuûa phöông phaùp ñôn hình ñöôïc theå hieän qua löu ñoà sau: Quaù trình ñi xaây döïng phöông aùn cô baûn naøy ñeán phöông aùn cô baûn khaùc ñöôïc goïi laø böôùc laëp cuûa phöông phaùp ñôn hình. Nhö chuùng ta ñaõ bieát, soá phöông aùn cô baûn cuûa moät baøi toaùn quy hoaïch tuyeán tính luoân höõu haïn, cho neân chuùng ta cuõng seõ coù höõu haïn böôùc laëp ñeå ñi ñeán lôøi giaûi cuûa baøi toaùn. 1. Öôùc löôïng cuûa aån- Daáu hieäu toái öu cuûa baøi toaùn Ta xeùt baøi toaùn quy hoaïch tuyeán tính daïng chuaån nhö sau: n f ( x) = ∑ ci xi → max (min) i =1 ⎧ n−m ⎪ x k + ∑ a kmj x j = b k ( k = 1, m ; j = 1, n − m ) ⎨ j =1 ⎪ x ≥ 0 , b ≥ 0 ( i = 1, n ; k = 1, m ; m < n ) ⎩ i k Khi ñoù, baøi toaùn coù phöông aùn cô baûn xuaát phaùt laø: x 0 = ( x10 , x20 ,K, xm0 , 0,K, 0) hay x 0 = (b1 , b2 ,K, bm , 0,K, 0) vôùi caùc aån cô baûn laø x1, x2, …, xm. Töø heä raøng buoäc chính ta n−m coù: xk = bk − ∑ akm+ j xm + j (k = 1, m; j = 1, n − m) . j =1 n m n−m f ( x) = ∑ ci xi = ∑ ck xk + ∑ cm + j xm + j i =1 k =1 j =1 m n−m n−m ⇔ f ( x) = ∑ ck (bk − ∑ akm + j xm + j ) + ∑ cm + j xm + j k =1 j =1 j =1 m m n−m n−m ⇔ f ( x) = ∑ ck bk − ∑∑ ck akm + j xm + j + ∑ cm + j xm + j k =1 k =1 j =1 j =1 m n−m ⎡⎛ m ⎞ ⎤ n m m n ⇔ f ( x) = ∑ ck bk − ∑ ⎢⎜ ∑ ck akm + j − cm + j ⎟ xm + j ⎥ (Theo tính chaát: ∑∑ Cij = ∑∑ Cij ) k =1 j =1 ⎣⎝ k =1 ⎠ ⎦ j =1 i =1 i =1 j =1 Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  16. Quy hoaïch tuyeán tính Trang 16 m Khi ñoù, ta ñaët Δ l = ∑ ck akl − cl (l = m + 1, n) ; Ñaïi löôïng Δ l naøy laø heä soá öôùc löôïng cuûa k =1 aån xl vaø ta coù nhaän xeùt nhö sau: Δ l laø hieäu soá giöõa toång cuûa caùc tích heä soá cuûa caùc aån cô baûn trong haøm muïc tieâu vôùi heä soá cuûa caùc aån khoâng cô baûn trong raøng buoäc chính (töông öùng) vaø heä soá cuûa aån xl (khoâng cô baûn) trong haøm muïc tieâu. Ñoàng thôøi, taïi caùc aån cô baûn, heä soá öôùc löôïng cuûa Δ l luoân baèng 0. Nhö vaäy, baøi toaùn ñöôïc vieát goïn laïi nhö sau: m n n f ( x) = ∑ ck bk − ∑ Δ l xl = f ( x 0 ) − ∑Δ x l l vaø do ñoù ta coù theå keát luaän: k =1 l = m +1 l = m +1 + Neáu Δ l ≥ 0 ∀l ∈ [m + 1, n] thì f ( x) ≤ f ( x 0 ) ; + Neáu Δ l ≤ 0 ∀l ∈ [m + 1, n] thì f ( x) ≥ f ( x 0 ) ; n n Δl f ( x) = ∑ ci xi → max f ( x) = ∑ ci xi → min i =1 i =1 Δ l ≥ 0 ∀l ∈ [m + 1, n] Coù phöông aùn toái öu Δ l ≤ 0 ∀l ∈ [m + 1, n] Coù phöông aùn toái öu Ñaây laø daáu hieäu toái öu cuûa phöông aùn cô baûn. ** Chuù yù: Khi coù daáu hieäu toái öu maø toàn taïi ít nhaát 1 heä soá öôùc löôïng baèng 0 cuûa aån khoâng cô baûn thì baøi toaùn coù theå coù nhieàu hôn 1 phöông aùn toái öu. 2. Ñònh lyù cô baûn Neáu trong 1 phöông aùn cô baûn cuûa baøi toaùn maø ∃Δ l < 0 (ñoái vôùi baøi toaùn cöïc ñaïi) hay ∃Δ l > 0 (ñoái vôùi baøi toaùn cöïc tieåu) cuûa aån khoâng cô baûn thì seõ xaõy ra 1 trong hai tröôøng hôïp sau: a) Neáu coù moät heä soá öôùc löôïng maø moïi akl ≤ 0 thì baøi toaùn khoâng giaûi ñöôïc. b) Neáu vôùi moãi heä soá öôùc löôïng maø toàn taïi ít nhaát moät akl > 0 thì baøi toaùn coù phöông aùn cô baûn môùi toát hôn. Chöùng minh: a) Phöông aùn cô baûn xuaát phaùt cuûa baøi toaùn laø x 0 = (b1 , ..., bm , 0, ..., 0) . Giaû söû taïi aån ⎛ m ⎞ xm + k ta coù aim + k ≤ 0 (i = 1, m) töông öùng vôùi heä soá Δ m + k ⎜ ⎝ Δ m+k = ∑ i =1 c i a im + k − c m + k ⎟ . ⎠ Khi ñoù ta coù theå xaây döïng moät phöông aùn x = ( x1 ,K, xm , 0, K, β ,K, 0) vôùi caùc thaønh β β β phaàn nhö sau: ⎧bi − aim + k β (i = 1, m) β ⎪ xi = ⎨β (i = m + k ; β > 0) ⎪0 (i = m + 1,..., m + k − 1, m + k + 1, K, n) ⎩ (Ñieàu kieän aim + k ≤ 0 (i = 1, m) vaø β >0 nhaèm ñaûm baûo xi ≥ 0 (i = 1, n) ) Vaø haøm muïc tieâu cuûa baøi toaùn ôû phöông aùn naøy ñöôïc vieát laïi nhö sau: n m m + k −1 n m f ( x β ) = ∑ ci xiβ = ∑ ci xiβ + ∑ c xβ + ci i m+k β + ∑ c xβ = ∑ c xβ + c i i i i m+ k β i =1 i =1 i = m +1 i = m + k +1 i =1 1 424 3 1 424 3 0 0 Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  17. Quy hoaïch tuyeán tính Trang 17 m m m ⎛ m ⎞ f ( x β ) = ∑ ci (bi − a im + k β ) + cm + k β = ∑ ci bi − ∑ ci aim + k β + cm + k β = f ( x 0 ) − ⎜ ∑ ci aim + k − cm + k ⎟ β i =1 i =1 i =1 ⎝1i =4 1 4 42444 3⎠ Δ m+k Nhö vaäy f ( x ) = f ( x ) − Δ m+ k β vaø ta coù nhaän xeùt sau: β 0 + Vôùi baøi toaùn cöïc ñaïi, neáu Δ m +k < 0 & aim + k ≤ 0 (i = 1, n) , khi β → +∞ thì f ( x β ) → +∞ ; töùc laø haøm muïc tieâu khoâng bò chaën treân; do ñoù baøi toaùn khoâng giaûi ñöôïc. + Vôùi baøi toaùn cöïc tieåu, neáu Δ m + k > 0 & aim + k ≤ 0 (i = 1, n) , khi β → +∞ thì f ( x β ) → −∞ ; töùc laø haøm muïc tieâu khoâng bò chaën döôùi vaø do ñoù baøi toaùn khoâng giaûi ñöôïc. b) Cuõng töông töï caùch laäp luaän nhö caâu a) nhöng baây giôø ta coù theâm tröôøng hôïp laø taïi moãi Δ m+ k ñeàu toàn taïi ít nhaát 1 chæ soá i sao cho aim + k > 0 ; Khi ñoù, ñeå thoaû ñieàu kieän xi ≥ 0 (i = 1, n) , ta caàn phaûi coù: bi bi − aim + k β ≥ 0 ⇔ β ≤ aim + k ⎛ bi ⎞ Ñeå β nghieäm ñuùng vôùi moïi i thì ta caàn coù ñieàu kieän 0 < β ≤ min⎜⎜ ⎟⎟ = β 0 ⎝ aim +k ⎠ Taïi β 0 (töông öùng vôùi chæ soá i=r), ta thöïc hieän pheùp chia 2 veá cuûa raøng buoäc chính thöù r cho heä soá arm+k vaø sau ñoù theá aån xm+k vaøo caùc raøng buoäc coøn laïi, ta ñöôïc baøi toaùn töông ñöông nhö sau: n−m n−m a 1 xr + ∑arm+ j xm+ j + arm+k xm+k = br ⇔ xm+k + ∑ rm+ j xm+ j + b xr = r = β0 j =1 j =1 arm+k arm+k arm+k j ≠k j ≠k n−m 1 arm+ j ⇔ xm+ k = β 0 − xr − ∑ xm+ j arm+ k j =1 arm+ k j ≠k n−m n−m xi + ∑ aim+ j xm+ j = bi ⇔ xi + ∑ aim+ j xm+ j + aim+k xm+k = bi j =1 j =1 j ≠k n −m ⎛ a ⎞ a ⇔ xi + ∑⎜⎜ aim+ j − aim+k rm+ j ⎟⎟ xm+ j − im+k xr = bi − aim+k β0 j =1 ⎝ arm+k ⎠ arm+k j ≠k Do ñoù, baøi toaùn goác seõ töông ñöông vôùi baøi toaùn daïng chuaån sau ñaây: n f ( x) = ∑ ci xi → max (min) i =1 ⎧ n−m a 1 br ⎪xm+k + ∑a xm+ j + a xr = a = β0 rm+ j ⎪ j =1 rm+k j ≠k rm+k rm+k ⎪ ⎪ n−m⎛ arm+ j ⎞ ⎟⎟xm+ j − im+k xr = bi − aim+k β0 (i = [1, r −1] ∪[r +1, m]) a ⎨ i ∑⎜ im+ j im+k x + ⎜ a − a ⎪ j =1 ⎝ arm+k ⎠ arm+k j ≠k ⎪ ( ⎪xh ≥ 0, h = 1, n ) ⎪ ⎩ Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  18. Quy hoaïch tuyeán tính Trang 18 Nhö vaäy, ta coù caùc aån cô baûn môùi laø x1, …, xr-1, xm+k, xr+1, …, xm vaø caùc aån khoâng cô baûn môùi laø xr, xm+1, …, xm+k-1, xm+k+1, …, xn; Phöông aùn cô baûn môùi cuûa baøi toaùn laø x β 0 = ( x1β 0 ,..., xrβ−01 , xmβ 0+ k , xrβ+01 ,..., xm , 0,..., 0) Ñoái vôùi haøm muïc tieâu f(x) taïi phöông aùn x β , ta thöïc hieän caùc pheùp tính toaùn 0 töông töï caâu a) vaø seõ coù: f ( x β ) = f ( x 0 ) − Δ m + k β 0 vaø ta coù nhaän xeùt sau: 0 + Ñoái vôùi baøi toaùn cöïc ñaïi, neáu Δ m +k < 0 thì f ( x β ) ≥ f ( x 0 ) ; töùc laø phöông aùn cô baûn 0 môùi toát hôn phöông aùn cô baûn ñang xeùt; + Ñoái vôùi baøi toaùn cöïc tieåu, neáu Δ m +k > 0 thì f ( x β ) ≤ f ( x 0 ) ; töùc laø phöông aùn cô baûn 0 môùi toát hôn phöông aùn cô baûn ñang xeùt; Nhö vaäy, ta coù theå xaây döïng phöông aùn cô baûn toát hôn cho baøi toaùn quy hoaïch tuyeán tính töø phöông aùn cô baûn ñang xeùt nhö sau: + Ñoái vôùi baøi toaùn cöïc ñaïi, khi taát caû caùc heä soá öôùc löôïng aâm cuûa caùc aån soá ñeàu toàn taïi ít nhaát moät chæ soá i sao cho aij > 0 thì phöông aùn cô baûn môùi ñöôïc xaây döïng töø phöông aùn cô baûn ñang xeùt baèng caùch choïn aån öùng vôùi Δ m +k < 0 nhoû nhaát ñöa vaøo ⎛ bi ⎞ laøm aån cô baûn thay cho aån cô baûn vôùi β 0 = min⎜⎜ ⎟⎟ vaø ñöa aån naøy ra laøm aån töï do. ⎝ aim +k ⎠ + Ñoái vôùi baøi toaùn cöïc tieåu, khi taát caû caùc heä soá öôùc löôïng döông cuûa caùc aån soá ñeàu toàn taïi ít nhaát moät chæ soá i sao cho aij > 0 thì phöông aùn cô baûn môùi ñöôïc xaây döïng töø phöông aùn cô baûn ñang xeùt baèng caùch choïn aån öùng vôùi Δ m +k > 0 lôùn nhaát ñöa vaøo ⎛ bi ⎞ laøm aån cô baûn thay cho aån cô baûn vôùi β 0 = min⎜⎜ ⎟⎟ vaø ñöa aån naøy ra laøm aån töï do. ⎝ aim +k ⎠ 3. Thuaät toaùn ñôn hình giaûi baøi toaùn quy hoaïch tuyeán tính chuaån 3.1) Giaûi baøi toaùn cöïc ñaïi a) Böôùc laëp thöù nhaát: a.1) Xaùc ñònh aån cô baûn, phöông aùn cô baûn xuaát phaùt x0 vaø giaù trò f(x0) cuûa haøm muïc tieâu taïi phöông aùn cô baûn naøy. a.2) Laäp baûng ñôn hình xuaát phaùt nhö sau A B C D Heä AÅn cô Phöông x1 x2 ... xm xm+1 … xn E soá baûn aùn cô baûn c1 c2 … cm cm+1 … cn F c1 x1 b1 1 0 … 0 a1m+1 … a1n c2 x2 b2 0 1 … 0 a2m+1 … a2n … … … … … … 0 ………. … … cm xm bm 0 0 … 1 amm+1 … amn 0 f(x) f(x ) 0 0 … 0 Δ m +1 … Δ n G Caùc thaønh phaàn cuûa baûng ñôn hình bao goàm: + Coät B: Ghi laàn löôït theo thöù töï caùc aån cô baûn cuûa baøi toaùn. + Coät A: Ghi töông öùng caùc heä soá cuûa caùc aån cô baûn trong haøm muïc tieâu. + Coät C: Ghi caùc soá haïng töï do töông öùng vôùi caùc aån cô baûn. + Coät D: Ghi ma traän ñieàu kieän cuûa heä raøng buoäc chính. Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  19. Quy hoaïch tuyeán tính Trang 19 + Haøng E: Ghi toaøn boä caùc aån cuûa baøi toaùn trong haøm muïc tieâu. + Haøng F: Ghi heä soá töông öùng cuûa caùc aån trong haøm muïc tieâu. + Haøng G: Tính trò soá cuûa caùc heä soá öôùc löôïng caùc aån vaø trò soá cuûa haøm muïc tieâu: m - Δ j = ∑ ci xi − c j (Toång cuûa tích coät A vôùi coät j roài tröø ñi heä soá cuûa aån xj taïi haøng F) i =1 vaø ñöôïc ghi töông öùng ôû haøng G cuûa coät D. (Heä soá öôùc löôïng cuûa caùc aån cô baûn luoân baèng 0). m - f ( x 0 ) = ∑ ci xi (Toång cuûa tích coät A vôùi coät C) vaø ñöôïc ghi ôû haøng G cuûa coät C. i =1 a.3) Ñaùnh giaù phöông aùn cô baûn xuaát phaùt: + Neáu taát caû caùc heä soá öôùc löôïng ñeàu khoâng aâm thì phöông aùn cô baûn xuaát phaùt ñang xeùt laø phöông aùn toái öu cuûa baøi toaùn. Vaø thuaät toaùn keát thuùc. + Neáu toàn taïi ít nhaát 1 heä soá öôùc löôïng aâm cuûa aån khoâng cô baûn maø vector ñieàu kieän cuûa aån ñoù chöùa caùc thaønh phaàn ñeàu khoâng döông thì baøi toaùn khoâng giaûi ñöôïc. Thuaät toaùn keát thuùc vôùi keát luaän baøi toaùn khoâng coù phöông aùn toái öu. + Neáu khoâng xaûy ra 2 tröôøng hôïp treân thì ta seõ ñi xaây döïng 1 phöông aùn cô baûn môùi toát hôn. Vaø ta tieáp tuïc thuaät toaùn vôùi böôùc laëp thöù 2. b) Böôùc laëp thöù hai: Heä AÅn PA x1 x2 ... xr … xm xm+1 … xm+k … xn soá CB CB c1 c2 … cr … cm cm+1 … cm+k … cn c1 x1 b1 1 0 … 0 … 0 a1m+1 … a1m+k … a1n β1 c2 x2 b2 0 1 … 0 … 0 a2m+1 … a2m+k … a2n β2 … … … … … … … … … ………. … … … … … cr xr br 0 0 … 1 … 0 arm+1 … arm+k … arn βr … … … … … … … … … ………. … … … … … cm xm bm 0 0 … 0 … 1 amm+1 … amm+k … amn βm f(x) f(x0) 0 0 … 0 … 0 Δ m +1 … Δ m+ k … Δ n b.1) Tìm aån ñöa vaøo: Ta tìm heä soá öôùc löôïng aâm nhoû nhaát trong baûng ñôn hình hieän taïi, giaû söû laø Δ m+ k thì aån xm+k seõ ñöôïc choïn ñöa vaøo heä aån cô baûn môùi cuûa baûng ñôn hình thöù hai. Khi ñoù, coät ñieàu kieän Am+k = (a1m+k, a2m+k,…, amm+k) ñöôïc goïi laø coät chuû yeáu. b.2) Tìm aån ñöa ra: Ta tieán haønh tính caùc heä soá β i = bi aim + k (i = 1, m) vaø tìm ra heä soá nhoû nhaát, giaû söû laø β r thì aån xr seõ ñöôïc ñöa ra khoûi heä cô baûn trong baûng ñôn hình thöù hai. Doøng r ñöôïc goïi laø doøng chuû yeáu. Heä soá naèm treân doøng chuû yeáu & coät chuû yeáu ñöôïc goïi laø heä soá chuû yeáu, trong baûng ñôn hình treân thì noù laø arm+k. b.3) Laäp baûng ñôn hình thöù hai: - Thay aån ñöa ra baèng aån ñöa vaøo vaø heä soá cuõng ñöôïc thay töông öùng. Caùc aån cô baûn khaùc vaø heä soá cuûa caùc aån cô baûn ñoù ñöôïc giöõ nguyeân khoâng ñoåi. Khi ñoù, doøng coù aån ñöa vaøo ñöôïc goïi laø doøng chuaån. Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
  20. Quy hoaïch tuyeán tính Trang 20 Heä AÅn PA x1 x2 ... xr … xm xm+1 … xm+k … xn soá CB CB c1 c2 … cr … cm cm+1 … cm+k … cn − a1m + k c1 x1 b1d 1 0 … … 0 a1dm +1 … 0 … a1dn βd1 arm + k c2 x2 − a2 m + k b2d 0 1 … … 0 a2dm +1 … 0 … a2dn βd2 arm + k … … … … … … … … … ... … … … … … br 1 arm +1 arn cm+k xm+k 0 0 … … 0 … 1 … βdr arm + k arm + k arm + k arm + k … … … … … … … … … ... … … … … … − amm + k cm xm bmd 0 0 … … 1 d amm +1 … 0 … d amn βd arm + k m f(x) f(x0) 0 0 … 0 … 0 Δdm+1 … Δdm+k … Δdn - Laáy doøng chuû yeáu cuûa baûng ñôn hình thöù nhaát chia cho heä soá chuû yeáu (arm+k) ñeå ta coù caùc thaønh phaàn cuûa doøng chuaån; töùc laø heä soá cuûa aån x j treân doøng chuaån ñöôïc xaùc arj ñònh baèng (vaø dó nhieân, heä soá cuûa caùc aån cô baûn khaùc luoân baèng 0). arm + k - Ñoái vôùi doøng i baát kyø, ta tính heä soá cuûa caùc aån khoâng cô baûn nhö sau: bid = bi − aim + k br arm + k ; d aim + j = aim + j − aim + k arm + j arm + k (i = 1, m) [Ñeå deã nhôù, ta coù theå duøng qui taéc hình chöõ nhaät: tích heä soá thuoäc 2 ñænh ñöôøng cheùo chính (ñi qua heä soá chuû yeáu) tröø ñi tích cuûa heä soá thoäc 2 ñænh cuûa ñöôøng cheùo phuï; sau ñoù chia cho heä soá chuû yeáu] - Caùc heä soá öôùc löôïng vaø giaù trò haøm muïc tieâu ñöôïc tính nhö böôùc laëp thöù nhaát. b.4) Ñaùnh giaù phöông aùn cô baûn thöù hai: Trong phöông aùn cô baûn thöù hai naøy, vieäc ñaùnh giaù xem noù coù phaûi laø toái öu hay chöa, baøi toaùn coù giaûi ñöôïc hay khoâng ñöôïc thöïc hieän töông töï nhö vieäc ñaùnh giaù phöông aùn cô baûn xuaát phaùt. Neáu baøi toaùn khoâng coù daáu hieäu khoâng giaûi ñöôïc maø phöông aùn cô baûn thöù hai khoâng phaûi laø phöông aùn cô baûn toái öu thì ta tieáp tuïc thuaät toaùn vôùi böôùc laëp thöù ba. Vaø töø böôùc laëp thöù ba trôû ñi ñöôïc thöïc hieän töông töï nhö böôùc laëp thöù hai. Nhöng caùc heä soá trong ma traän ñieàu kieän vaø caùc soá haïng töï do cuûa baûng ñôn hình sau ñöôïc tính döïa vaøo ma traän ñieàu kieän vaø caùc soá haïng töï do cuûa baûng ñôn hình ngay tröôùc noù. Nhö ñaõ bieát, do soá phöông aùn cô baûn cuûa baøi toaùn quy hoaïch tuyeán tính luoân höõu haïn cho neân baøi toaùn seõ coù lôøi giaûi chæ sau moät soá böôùc laëp höõu haïn. *** Chuù yù: + Neáu caùc heä soá öôùc löôïng cuûa caùc aån khoâng cô baûn trong baûng ñôn hình cuoái cuøng ñeàu döông thì baøi toaùn chæ coù duy nhaát 1 phöông aùn cô baûn toái öu- ñoù laø phöông aùn cô baûn toái öu vöøa tìm ñöôïc trong baûng ñôn hình cuoái cuøng. + Neáu caùc heä soá öôùc löôïng cuûa caùc aån khoâng cô baûn trong baûng ñôn hình cuoái cuøng ñeàu khoâng aâm, vaø toàn taïi ít nhaát 1 heä soá öôùc löôïng cuûa aån khoâng cô baûn baèng 0 thì baøi toaùn seõ coù voâ soá phöông aùn toái öu. Giaû söû ta tìm ñöôïc theâm phöông aùn toái öu x* Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009
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