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

Bài toán về quy hoạch tuyến tính

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

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

Trong toán học, quy hoạch tuyến tính (QHTT) (tiếng Anh: linear programming - LP) là bài toán tối ưu hóa, trong đó hàm mục tiêu (objective function) và các điều kiện ràng buộc đều là tuyến tính. Trong bài toán này, cho một đa tạp (polytope) (chẳng hạn một đa giác hoặc một đa diện), và một hàm tuyến tính (affine) nhận giá trị thực f(x_1, x_2, \dots, x_n)=a_1x_1+a_2x_2+\cdots +a_nx_n+b\, xác định trên đa tạp đó, mục đích là tìm một điểm trên đa tạp tại đó hàm có giá trị nhỏ nhất (hoặc lớn nhất). Các điểm như...

Chủ đề:

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

Lưu

Nội dung Text: Bài toán về quy hoạch tuyến tính

  1. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØØI TOAÙÙN MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA BA TOA CHÖÔNG 1 QUY HOAÏÏCH TUYEÁÁN TÍNH TUYE TÍ HOA Ví duïï 1.1. BAØØI TOAÙÙN LAÄÄP KEÁÁ HOAÏÏCH SAÛÛN XUAÁÁT du BA TOA LA KE HOA CH SA XUA Moäät xí nghieääp duøøng 3 loaïïi nguyeân lieääu: N1; N2; N3 Mo xí nghie du ng loa lie u: 1. THIEÁÁT LAÄÄP MO HÌNH BAØØI TOAÙÙN THIE LA BA TOA (Xem) ñeå saûûn xuaáát ra moäät loaïïi saûûn phaååm theo 3 phöông phö sa xua mo loa sa pha phaùùp khaùùc nhau: PP1; PP2; PP3. Ñònh möùc nguyeân möù pha kha Ths. Nguyeãn Coâng Trí 2. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QUY CA DA NG CU BA TOA Trí lieääu vaøø soáá löôïng saûûn phaååm saûûn xuaáát ra trong 1 lie va so ng sa pha sa xua HOAÏÏCH TUYEÁÁN TÍNH HOA CH TUYE TÍ (Xem) giôøø ñöôïc cho ôûû baûûng sau: giô ñöô ô ba ng Nguyeân Soáá löôïng Ñònh möùc nguyeân lieääu möù So ng lie 3. CAÙÙC KHAÙÙI NIEÄÄM CÔ BAÛÛN VEÀÀ BAØØI TOAÙÙN CA KHA NIE BA VE BA TOA Copyright 2001 Lieääu hieään coùù (ñv) Lie hie co PP 1 PP2 PP3 QUY HOAÏÏCH TUYEÁÁN TÍNH HOA CH TUYE TÍ N1 250 4 5 3 (Xem) í N2 350 2 4 1 4. CAÙÙC PHÖÔNG PHAÙÙP GIAÛÛI BAØØI TOAÙÙN CA PHÖ PHA GIA BA TOA Tr N3 450 3 6 4 QUY HOAÏÏCH TUYEÁÁN TÍNH HOA CH TUYE TÍ Soáá saûûn phaååm (sp/giôøø) 10 12 9 So sa pha (sp/giô (Xem) Ths. Nguyeãn Coân g Trí Trí Ths. Haõy laääp moâ hình baøøi toaùùn sao cho xí nghieääp saûûn hì xí nghie sa la ba toa 5. BAØØI TAÄÄP BA TA (Xem) Copyright 2001 xuaáát ra nhieààu saûûn phaååm nhaáát? xua nhie sa pha nha t? g oân MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA Goïïi x1, x 2, x 3 laààn löôït laøø thôøøi gian saûûn xuaáát ra saûûn la lö la thô Go sa xua sa Ví duïï 1.2. BAØØI TOAÙÙN PHA CAÉÉT VAÄÄT LIEÄÄU du BA TOA CA VA LIE phaååm theo 3 phöông phaùùp PP 1, PP 2, PP3. phö pha pha Moäät xí nghieääp may maëëc caààn saûûn xuaáát ñuùng 2.000 Mo xí nghie ma ca sa xua ng Toåång saûûn phaååm saûûn xuaáát (caààn laøøm cöïc ñaïi) To ng sa pha sa xua (ca la cöï i) quaààn vaøø ít nhaáát 1.000 aùùo. Moãi taáám vaûûi coùù 6 caùùch qua va nha a o. ta va co ca ch f(x) = 10x1 + 12x2 + 9x 3 max caéét nhö sau: ca nhö Do xí nghieääp chæ coùù 250 nguyeân lieääu N1 neân x1, x2, xí nghie chæ co lie Caùùch caéét Quaààn A Ùo Ca ch ca Qua C x 3 phaûûi thoûûa maõn 4x1 + 5x2 + 3x3 250 pha tho 1 90 35 Töông töï cho caùùc nguyeân lieääu N2, N 3 ta coùù töï ca lie co 2x1 + 4x 2 + x3 350 vaøø 3x1 + 6x2 + 4x3 450 va 2 80 55 Dó nhieân ta phaûûi coùù x1, x 2, x 3 khoâng aâm pha co 3 70 70 Vaääy moâ hình baøøi toaùùn ñöôïc phaùùt bieååu nhö sau: hì ba toa ñöô pha bie nhö Va 4 60 90 Tìm caùùc bieáán x1, x2, x3 sao cho ca bie eãn f(x)= 10x 1 + 12x2 + 9x3 max, thoûûa caùùc ñieààu kieään max, tho ca ie kie 5 120 0 4x1 + 5x 2 + 3x3 250 6 0 100 2x1 + 4x2 + x3 350 Haõy tìm phöông aùùn caéét quaààn aùùo sao cho toåång soáá tì phö a ca qua a to ng so 3x1 + 6x 2 + 4x3 450 taáám vaûûi laøø ít nhaáát? ta va la nhat? x1 0 x2 0 x3 0 y gu MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA Goïïi xj (j = 1, 2, ..., 6) laøø soáá taáám vaûûi ñöôïc caéét theo la so ta va ñöô ca Go Ví duïï 1.3. BAØØI TOAÙÙN XAÙÙC ÑÒNH KHAÅÅU PHAÀÀN du BA TOA XA KHA PHA caùùch thöù j. ca ch thöù Ñeå nuoâi moäät loaïïi gia suùùc coùù hieääu quaûû, moãi ngaøøy mo loa su co hie qua nga Toåång soáá taáám vaûûi duøøng ñeå saûûn xuaáát (caààn laøøm cöïc sa xua (ca la cöï To ng so ta va du ng caààn phaûûi coùù khoáái löôïng toáái thieååu caùùc chaáát protit, ca pha co kho lö ng to thie ca cha tieååu) laøø f(x) = x1 + x2 + x3 + x4 + x5 + x6 min tie u) la glucit, khoaùùng töông öùng laøø 90 gram, 130 gram, khoa ng tö öùng la Do x í nghieääp caààn saûûn xuaáát ñuùng 2.000 quaààn neân nghie ca sa xua ng qua 10 gram. Tyûû leää (%) theo khoáái löôïng caùùc chaáát treân kho lö ng ca cha Ty le caùùc xj phaûûi thoûûa maõn ca pha tho coùù trong caùùc loaïïi thöùc aên A, B, C nhö sau: ca loa thöù nhö co N 90x 1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 Thöùc aên Thöù Chaáát dinh döôõng (%) dö Cha Töông töï cho ñieààu kieään veàà saûûn xuaáát aùùo, ta coùù töï ie kie ve sa xua a o, co Protit Glucit Khoaùùng Khoa ng 35x 1 + 55x2 + 70x3 + 90x4 + 100x6 1000 A 10 30 2 Dó nhieân ta phaûûi coùù xj (j = 1, 2, ..., 6) khoâng aâm pha co B 20 40 1 Vaääy moâ hình baøøi toaùùn ñöôïc phaùùt bieååu nhö sau: hì ba toa ñöô pha bie nhö Va C 30 20 3 Tìm caùùc bieáán xj (j = 1, 2, ..., 6) sao cho ca bie Giaùù 1 kg thöùc aên A, B, C töông öùng laøø 3.000 thöù tö Gia ng la f(x)= xj min, thoûûa caùùc ñieààu kieään min, tho ca ie kie ñoàng, 4.000 ño àng, 5.000 ñoàng. Haõy laääp moâ hình hì ng, ng, ng. la 90x 1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 baøøi toaùùn xaùùc ñònh khoáái löôïng thöùc aên caààn thieáát kho lö ng thöù ba toa xa ca thie 35x 1 + 55x2 + 70x3 + 90x4 + 100x6 1000 sao cho chi phí nuoâi gia suùùc laøø thaááp nhaáát? phí su la tha nha t? xj 0, (j = 1, 2, ..., 6). ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  2. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA Goïïi xj (j = 1, 2, 3) laøø soáá gram thöùc aên A, B, C caààn thöù Go la so ca Ví duïï 1.4. BAØØI TOAÙÙN VAÄÄN TAÛÛI du BA TOA VA TA mua moãi ngaøøy.nga y. Caààn vaään chuyeåån xi maêng töø 3 kho K1, K 2, K3 ñeán 4 töø Ca va chuye Toåång chi phí duøøng ñeå mua thöùc aên (caààn laøøm cöïc phí du ng thöù (ca la cöïc To ng coâng tröôøng xaây döïng T1, T2, T3, T4. Cho bieáát löôïng trö ng döï ng bie lö ng tieååu) laøø f(x) = 3x1 + 4x2 + 5x 3 min (ñoàng) (ñ ng) tie u) la xi maêng coùù ô û moãi kho, löôïng xi maêng caààn ôûû moãi lö ng co ca ô Do caùùc tyûû leää caùùc chaáát protit, glucit vaøø khoaùùng coùù ca ty le ca cha va khoa ng co coâng tröôøng vaøø cöôùc phí vaään chuyeåån (ngaøøn trö ng va phí va chuye (nga trong thöùc aên A neân caùùc x j phaûûi thoûûa maõn thöù ca pha tho ñoàng/ taáán) töø moãi kho ñeán coâng tröôøng nhö sau: ng/ tan) töø trö ng nhö 0,1x1 + 0,2x2 + 0,3x3 90 Töông töï cho ñieààu kieään cuûûa thöùc aên B vaøø C, ta coùù töï ie kie cu thöù va co Coâng tröôøng T1: 130 t T2: 160 t T3: 120 t T4: 140 t trö ng Kho 0,3x1+0,4x2+0,2x3 130 vaøø 0,02x1+0,01x2+0,03x3 10 va K1: 170 taáán 20 18 22 25 Vaääy moâ hình baøøi toaùùn ñöôïc phaùùt bieååu nhö sau: hì ba toa ñöô pha bie nhö ta Va Tìm caùùc bieáán xj (j = 1, 2, 3) sao cho ca bie K2: 200 taáán 15 25 30 15 ta í f(x) = 3x1 + 4x2 + 5x3 min, thoûûa caùùc ñieààu kieään min, tho ca ie kie K3: 180 taáán 45 30 40 35 ta Tr 0,1x1 + 0,2x2 + 0,3x3 90 Laääp moâ hình baøøi toaùùn vaään chuyeåån sao cho caùùc hì La ba toa va chuye ca 0,3x1 + 0,4x2 + 0,2x3 130 kho phaùùt heáát xi maêng coùù, coâng tröôøng nhaään ñuû xi trö ng nha pha he co 0,02x 1 + 0,01x2 + 0,03x3 10 maêng caààn vaøø chi phí vaään chuyeåån thaááp nhaáát? phí va chuye tha nha t? ca va xj 0, (j = 1, 2, 3). g oân MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT MO VA VÍ DU VE BA TOA CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CA DA NG CU BA TOA Goïïi xij (i = 1, 2, 3, j = 1, 2, 3, 4) laøø löôïng xi maêng Go (i la ng 2.1. DAÏÏNG TOÅÅNG QUAÙÙT DA NG TO NG QUA caààn vaään chuyeåån töø kho Ki ñeán coâng tröôøng Tj. ca va chuye töø trö ng Toåång chi phí vaään chuyeåån (caààn laøøm cöïc tieååu) laøø phí va chuye (ca la cöï tie u) la To ng Tìm x = (x 1, x 2,..., xn) sao cho: f(x) = 20x11 + 18x12 + 22x13 + 25x14 22x n 15x21 + 25x 22 + 30x23 + 15x24 25x f ( x) cj xj min ( hay max) (2.1) C 45x31 + 30x 32 + 40x33 + 35x34 min 30x j1 Ñieààu kieään cuûûa caùùc kho ie kie cu ca n x11 + x12 + x13 + x14 = 170 aij x j bi i 1, m 2.2 x21 + x22 + x23 + x24 = 200 j1 x31 + x32 + x33 + x34 = 180 Ñ ieààu kieään cuûûa caùùc coâng tröôøng trö ng ie kie cu ca x j 0, xk 0, j k n 2.3 x11 + x21 + x31 = 130 eãn (2.1) goïïi laøø haøøm muïïc tieâu. (2.2) goïïi laøø heää raøøng go la ha go la he ra ng mu x12 + x22 + x32 = 160 buoääc. (2.3) goïïi laøø raøøng buoääc veàà daááu cuûûa aåån soáá. go la ra ng buo ve da cu a so buo x13 + x23 + x33 = 120 Ví duïï 1.1, Ví duïï 1.2 vaøø Ví duïï 1.3 laøø caùùc baøøi toaùùn Ví du du va du la ca ba toa x14 + x24 + x34 = 140 QHTT coùù daïïng toåång quaùùt. co da ng to ng qua t. xijj 0, i = 1, 2, 3, j = 1, 2, 3, 4. i y gu CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CA DA NG CU BA TOA CA DA NG CU BA TOA Moäät vectô x = (x1, x2,..., xn) thoûûa maõn ñieààu kieään Mo tho ie kie 2.2. DAÏÏNG CHÍNH TAÉÉC DA NG CHÍ TA (2) vaøø (3) ñöôïc goïïi laøø moäät phöông aùùn (P.A) cuûûa ñöô go la mo phö va cu a Tìm x = (x 1, x 2,..., xn) sao cho: baøøi toaùùn quy hoaïïch tuyeáán tính (QHTT). hoa ch tuye tí ba toa n f ( x) cjxj min ( hay max) Taääp caùùc P.A cuûûa baøøi toaùùn QHTT ñöôïc goïïi laøø ñöô go la Ta ca cu ba toa j1 N mieààn raøøng buoääc. Kyùù hieääu laøø D. mie ra ng buo Ky hie la n aij x j bi i 1, m Moäät phöông aùùn toáái öu, ñöôïc kyùù hieääu laøø X opt ñöô ky hie la Mo phö a to j1 (optimality), neááu vectô X laøø laøø moäät P.A vaøø X thoûûa ne la la mo va tho xj 0, j 1, n maõn (2.1) hay haøøm muïïc tieâu (2.1) bò chaëën. ha mu cha n. Nhaään xeùùt: Heää raøøng buoääc cuûûa baøøi toaùùn daïïng chính Nha xe t: He ra ng buo cu ba toa da ng chí Baøøi toaùùn QHTT ñöôïc goïïi laøø giaûûi ñöôïc hay coùù ñöô go la gia ñöô Ba toa co taééc ñeàu laøø caùùc ñaúng thöùc vaøø moïïi bieáán cuûûa baøøi ng thöù va mo bie cu ba ta la ca lôøøi giaûûi neááu noùù coùù ít nhaáát moäät PA.T.Ö. lô gia ne no co nha mo PA.T.Ö toaùùn ñeàu khoâng aâm. Ví duïï 1.4 BAØØI TOAÙÙN VAÄÄN TAÛÛI toa du BA TOA VA TA Baøøi toaùùn QHTT khoâng giaûûi ñöôïc neááu D = hay Ba toa gia ñöô ne hay khoâ coùù daïïng chính taééc. co da ng chí ta c. noùù coùù P.A nhöng khoâng coùù PA.T.Ö. nhö co PA.T.Ö no co ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  3. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CA DA NG CU BA TOA CA DA NG CU BA TOA 2.3. DAÏÏNG CHUAÅÅN 2.4. CHUYEÅÅN ÑO ÅI DAÏÏNG BAØØI TOAÙÙN QHTT 2.3. DA NG CHUA CHUYE DA NG BA TOA Tìm x = (x 1, x 2,..., xn) sao cho: Khi xeùùt baøøi toaùùn QHTT, ngöôøi ta thöôøng söû duïïng ngö thö ng söû du ng xe ba toa daïïng chính taééc, coùù theåå ñöa baøøi toaùùn veàà daïïng da ng chí ta c, co the ñöa ba toa ve da ng n f ( x) c j xj min ( hay max) chính taééc baèèng caùùc bieáán ñoåi sau: chí ta ba ng ca bie j1 nm 1) Neááu raøøng buoääc thöù i coùù daïïng aijxj bi thì theâm Ne ra ng buo thöù co da ng thì xi ai ,m k xm bi , i 1, m k vaøøo moäät aåån phuïï x n+1 0, sao cho aijx j + xn+1 = bi. va mo a phu k1 x j 0 j 1, n bi 0 2) Neááu raøøng buoääc thöù i coùù daïïng aijxj bi thì theâm Ne ra ng buo thöù co da ng thì Nhaään xeùùt: Baøøi toaùùn daïïng chuaåån laøø baøøi toaùùn ôûû Nha xe t: Ba toa da ng chua la ba toa ô vaøøo moäät aåån phuïï x n+1 0, sao cho aijx j – x n+1 = bi. va mo a phu daïïng chính taééc vôùùi heää raøøng buoääc chöùa ma traään da ng chí ta vô he ra ng buo chöù tra í 3) Neááu bieáán xj 0 thì ñöôïc thay baèèng x/j = – xj 0. thì ñöô Ne bie ba ng con Im laøø ma traään ñôn vò caááp m. la tra ca Tr 4) Neááu bieáán xj khoâng raøøng buoääc veàà daááu thì thay xj ra ng buo ve da thì Ne bie Trong ñoù caùùc x i (i = 1, 2,..., m) ñöôïc goïïi laøø aån cô ñöô go la ca baèèng hai aåån phuïï x/j vaøø x//j sao cho x j = x/j – x //j, vôùùi ba ng a phu va vô baûûn (A.C.B), coøøn caùùc aåån xi,m+k, (k = 0, 1,..., n – m) co ca a ba x/j 0, x//j 0. ñöôïc goïïi laøø aån khoâng cô baûûn. ñöô go la ba g oân CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CA DA NG CU BA TOA CA DA NG CU BA TOA Ñeå baøøi toaùùn goïïn hôn, chuùùng ta duøøng caùùc kyùù hieääu Ví duïï 1.5. Ñöa baøøi toaùùn QHTT sau ñaây veàà daïïng Ñöa ba toa ba toa go chu ng dung ca ky hie du ve da ng chính taééc vaøø vieáát baøøi toaùùn chính taééc döôùi daïïng chí ta va vie ba toa chí ta dö dang a1 j b1 c1 x1 0 a11 a12 a1n ma traään tra a2 j b2 c2 x2 a21 a22 a2 n 0 f ( x) x1 3 x2 2 x3 min , Aj ,b ,c ,x ,0 A C 3 x1 x2 2 x3 7 amj bm cn xn am1 am 2 amn 0 Trong ñoù A laøø ma traään m n goààm caùùc heää soáá ôû veáá la tra go ca he so ve 2 x1 4 x2 x3 12 traùùi cuûûa heää raøøng buoäc; Aj laøø vectô coäät thöù j cuûûa tra cu he ra ng buoäc; co thöù cu la 4 x1 3 x2 8 x3 10 ma traään A; b laøø vectô heää soáá ôû veáá phaûûi cuûûa heää tra la he so ve pha cu he raøøng buoääc; c laøø vectô heää soáá ôû haøøm muïïc tieâu; x laøø ra ng buo c; la he so ha mu la x1 0 x3 0 eãn Theâm 2 aåån phuïï x 4, x5 0 vaøøo raøøng buoääc thöù nhaáát va ra ng buo thöù nha vectô aåån soáá; 0 laøø vectô khoâng. a phu a so la Khi ñoù baøøi toaùùn QHTT ôûû daïïng chính taééc coùù daïïng ô dang chí vaøø raøøng buoääc thöù ba. va ra ng buo thöù ba toa ta co dang f(x) = cTx min (hay max) Thay x /3 = –x 3 0 Ax = b, x 0 Thay x 2 = x/2 –x//2 0, vôùùi x/2, x //2 0 vô y gu CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CA DA NG CU BA TOA CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT CA DA NG CU BA TOA Baøi toaùùn QHTT coùù daïïng chính taééc nhö sau co da ng chí ta nhö toa Ví duïï 1.6. Cho baøøi toaùùn QHTT sau: du ba toa f (x ) x1 3x 2 3x2 2 x3 min f ( x) x2 x5 min 3 x1 x2 x2 2 x3 x4 7 x1 x2 2 x5 1 2 x1 4 x2 4 x2 x3 12 3x2 x3 x5 3 4 x1 3 x2 3 x2 8 x3 x5 10 N 2 x2 x4 x5 2 x1 0, x2 0, x2 0, x3 0, x4 0, x5 0 Baøi toaùùn QHTT döôùi daïïng ma traään nhö sau dö da ng tra nhö toa xj 0 j 1,5 f(x) = (1, 3, – 2, 0, 0, 0)T(x1, x/2, x //2, x/3, x4, x 5) min Ta coùù ma traään heää soáá cuûûa heää raøøng buoääc: co tra he so cu he ra ng buo c: x1 1 1 00 2 x2 A 0 3 10 1 3 1 1 21 0 7 x 02 2 4 4 10 12 0 201 1 x 13 4 3 3 80 10 chöùa I3 neân baøøi toaùùn quy hoaïïch tuyeáán tính treân coùù chöù hoa ch tuye tí ba toa co x4 daïïng chuaåån. x5 da ng chua n. (x1, x/2, x //2, x/3, x4, x 5) (0, 0, 0, 0, 0, 0) ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  4. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÑÒNH NGHÓA PHÖÔNG AÙÙN CÖÏC BIEÂN NGHÓ PHÖ A CÖÏ ÑÒNH NGHÓA PHÖÔNG AÙÙN CÖÏC BIEÂN NGHÓ PHÖ A CÖÏC Moäät phöông aùùn x* = (x1*, x2*,..., x n*) cuûûa baøøi toaùùn Mo phö a cu ba toa Ví duïï 1.7. Cho baøøi toaùùn QHTT du ba toa QHTT daïïng toåång quaùùt laøø phöông aùùn cöïc bieân da ng to ng qua la phö a cöï f ( x ) 50 x1 16 x2 23x3 min (P.A.C.B) neááu x* = (x1*, x2*,..., xn*) thoûûa maõn chaëët ne tho cha 5 x1 3x 2 4 x3 2 n raøøng buoääc ñoäc laääp tuyeáán tính. Töùc laøø: la tuye tí Töù la ra ng buo x1 2 n aijx* = bi, i=1,k, k m x1 x2 3 x3 1 X la P.A.C.B * k +l n,det A 0 j * j=1 x* = 0, j=1,l,l n 6 x1 2x2 x3 4 j Trong ñoù A laøø ma traään con caááp n cuûûa hpt (*). la tra ca cu x2 0 x3 0 Moäät P.A.C.B khoâng suy bieáán laøø moäät P.A.C.B Mo bie la mo Caùùc vectô naøøo sau ñaây Ca na í thoûûa maõn ñuùng n raøøng buoääc chaëët. tho ng ra ng buo cha t. Tr 23 6 Moäät P.A.C.B suy bieáán laøø moäät P.A.C.B thoûûa maõn Mo bie la mo tho X 0, 1, 3 Y 3, 0, 0 Z 2, , 5 5 hôn n raøøng buoääc chaëët. ra ng buo cha t. laøø phöông aùùn cöïc bieân? la phö a cöï P.A.C.B coøøn ñöôïc goïïi laøø phöông aùùn cô baûûn. co ñöô go la phö a ba g oân CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT CA TÍ CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT CA TÍ CHA CU BA TOA CHA CU BA TOA Ñ ÒNH LYÙÙ 1. (TÍNH CHAÁÁT ÑAËC TRÖNG CUÛÛA P.A.C.B) (TÍ TRÖ X, Y, Z thoûûa caùùc raøøng buoääc neân chuùùng laøø P.A. LY CHA CU tho ca ra ng buo chu ng la Maëët khaùùc ta coùù Ma kha co 1 Moäät phöông aùùn X* = (x1*, x2*,…, xn*) cuûûa baøøi Mo phö a cu ba 1 1 toaùùn QHTT daïïng chính taééc laøø phöông aùùn cöïc da ng chí ta la phö a cöï toa A1 A2 A3 1 1 0 bieân neááu vaøø chæ neááu heää vectô coäät A j öùng vôùùi ne va chæ ne he co ng vô C thaøønh phaààn x j* > 0 laøø ñoäc laääp tuyeáán tính. la tuye tí tha nh pha la 1 1 Vôùùi X = (2, 2, 0), det 2 neân X laøø P.A.C.B. Vô la Ví duïï 1.8. Cho baøøi toaùùn QHTT du ba toa 1 1 Vôùùi Y = (0, 0, 4), heää chæ goààm moäät vectô A3 neân he chæ go mo Vô f ( x) x1 2 x2 3x3 min Y cuõng laøø P.A.C.B. la x1 x2 x3 4 Vôùùi Z=(1, 1, 2), ta thaááy heää {A 1, A2, A3} phuïï thuoääc Vô tha he phu thuo eãn x1 x2 0 tuyeáán tính vì A 1+A2–2A3=0 neân Z khoâng laøø P.A.C.B. tuye tí vì la HEÄÄ QUAÛÛ 1. (tính höõu haïïn cuûûa P.A.C.B). (tí hö ha cu HE QUA xj 0, j 1, 3 Caùùc vectô naøøo sau ñaây X = (2, 2, 0), Y = (0, 0, 4), Ca na Soááù phöông aùùn cöïc bieân cuûûa baøøi toaùùn QHTT So phö a cöï cu ba toa Z = (1, 1, 2), laøø P.A.C.B cuûûa baøøi toaùùn. la cu ba toa n. daïïng chính taééc laøø höõu haïïn. da ng chí ta la ha n. y gu CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT CA TÍ CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT CA TÍ CHA CU BA TOA CHA CU BA TOA Ñ ÒNH LYÙÙ 4. (SÖÏ TOÀÀN TAÏÏI NHIEÀÀU P.A.C.B.T.Ö) (SÖÏ TO TA NHIE P.A.C.B.T.Ö LY HEÄÄ QUAÛÛ 2. Soááù thaøønh phaààn döông trong moãi HE QUA So tha nh pha dö Neááu baøøi toaùùn QHTT coùù P.A.T.Ö laøø X 0 vaøø X1, X2 co P.A.T.Ö la Ne ba toa va phöông aùùn cöïc bieân cuûûa baøøi toaùùn quy hoaïïch phö a cöï cu ba toa hoa ch hai phöông aùùn khaùùc nhau cuûûa baøøi toaùùn thoaûû phö a kha cu ba toa thoa tuyeáán tính daïïng chính taééc toáái ña baèèng m (m laøø tuye tí da ng chí ta to ba ng la X0 = X 1 + (1– )X 2, 0 1 thì X1, X 2 laøø P.A.T.Ö. thì la P.A.T.Ö soáá doøøng cuûûa ma taään A). so do ng cu ta NHAÄÄN XEÙÙT NHA XE Ñ ÒNH LYÙÙ 2. (SÖÏ TOÀÀN TAÏÏI CUÛÛA PHÖÔNG AÙÙN TOÁÁI ÖU) (SÖÏ TO TA CU PHÖ 1. Ta coùù theåå tìm P.A.T.Ö cuûûa baøøi toaùùn QHTT P.A.T.Ö cu LY A TO co the ba toa N trong soáá caùùc P.A.C.B cuûûa baøøi toaùùn vaøø coùù theåå so ca cu ba toa va co the Neááu baøøi toaùùn quy hoaïïch tuyeáán tính coùù phöông hoa ch tuye tí co phö Ne ba toa xaùùc ñònh ngay P.A.C.B cuûûa baøøi toaùùn daïïng xa cu ba toa da ng aùn vaøø haøøm muïïc tieâu bò chaëën döôùi (ñoái vôùùi cha dö (ñ va ha mu vô chuaåån baèèng caùùch cho caùùc aåån khoâng cô baûûn chua ba ng ca ch ca a ba f(x) min) hoaëëc haøøm muïïc tieâu bò chaëën treân hoa ha mu cha baèèng khoâng (xem Ví duïï 1.9). du 1.9). ba ng (ñoái vôùùi f(x) max) treân taääp caùùc phöông aùùn thì ta ca phö a thì vô 2. Trong baøøi toaùùn QHTT daïïng chính taééc. Neááu da ng chí ba toa ta c. Ne haïïng cuûûa ma traään heää soáá A laøø m thì P.A.C.B thì ha ng cu tra he so la baøøi toaùùn coùù phöông aùùn toáái öu. ba toa co phö a to ñöôïc goïïi laøø khoâng suy bieáán neááu noùù coùù ñuùng m ñöô go la bie ne no co ng ÑÒNH LYÙÙ 3. (SÖÏ TOÀÀN TAÏÏI CUÛÛA P.A.C.B. TOÁÁI ÖU) (SÖÏ TO TA CU LY TO thaøønh phaààn döông. Neááu P.A.C.B coùù ít hôn m tha nh pha dö Ne co Neááu baøøi toaùùn QHTT daïïng chính taééc coùù P.A.T.Ö da ng chí ta co P.A.T.Ö Ne ba toa thaøønh phaààn döông thì ñöôïc goïïi laøø P.A.C.B suy tha nh pha dö thì ñöô go la thì baøøi toaùùn coùù P.A.C.B toáái öu (P.A.C.B.T.Ö). thì ba toa co (P.A.C.B.T.Ö to bieáán (xem Ví duïï 1.10). du 1.10). bie ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  5. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT CA TÍ CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT CA TÍ CHA CU BA TOA CHA CU BA TOA Ví duïï 1.10 . Vôùùi baøøi toaùùn quy hoaïïch tuyeáán tính hoa ch tuye tí V í duïï 1.9 . du Vô ba toa du f ( x) 3 x1 4 x2 2 x3 2 x4 min Vôùùi baøøi toaùùn quy hoaïïch tuyeáán tính hoa ch tuye tí Vô ba toa 2 x1 2 x2 x4 28 f ( x) x2 x5 min x1 5 x2 3 x3 2 x4 26 x1 x2 2 x5 1 2 x1 2 x2 2 x3 x4 16 3x 2 x3 x5 3 x j 0 j 1,4 Kieååm tra vectô X = (11, 3, 0, 0) coùù phaûûi laøø P.A.C.B? Kie co pha la 2 x2 x4 x5 2 xj 0 j 1,5 Kieååm tra tröïc tieááp, ta coùù X laøø P.A cuûûa baøøi toaùùn. tröïc tie p, Kie co la cu ba toa n. í Ta coùù phöông aùùn X = (1, 0, 3, 2, 0) laøø phöông aùùn co phö la phö a a Tr Haïïng cuûûa ma traään heää soáá cuûûa heää raøøng buoääc Ha ng cu tra he so cu he ra ng buo cöïc bieân cuûûa baøøi toaùùn vì caùùc aåån x1, x 3, x 4 laøø caùùc cu ba toa vì ca a la ca tuyeáán tính baèèng 3 vaøø X coùù 2 thaøønh phaààn döông laøø tuye tí ba ng va co tha nh pha dö la aån cô baûûn cuûûa baøøi toaùùn daïïng chuaåån. ba cu ba toa da ng chua n. x1 =11, x2 = 3 neân X laøø P.A.C.B suy bieáán. la bie n. g oân CAÙÙC PHÖÔNG PHAÙÙP GIAÛÛI CA PHÖ PHA GIA PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ PHA HO BAØØI TOAÙÙN QUY HOAÏÏCH TUYEÁÁN TÍNH HOA CH TUYE TÍ BA TOA Xeùùt baøøi toaùùn QHTT coùù 2 bieáán. Xe ba toa co bie n. ax+by=c 4.1. PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ PHA HO =m (ñöôøng möùc) (ñöô ng möù c) Ths.ÖNguyeãnHÌNH ng Trí 4.2. PHÖÔNG PHAÙÙP ÑÔN Coâ Trí (Xem) C taêng PH PHA ax+byc 4.3. PHÖÔNG PHAÙÙP ÑÔN HÌNH MÔÛÛ ROÄÄNG PHÖ PHA MÔ RO NG Copyright 2001 (BAØØI TOAÙÙN M) (BA TOA (Xem) a O giaûûm gia eãn b N(a,b) y gu PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ PHA HO PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ PHA HO Ví duïï 1.11. Moäät coâng ty coùù 2 phaân xöôûng: PX1 vaøø xö ng: du Mo co va Goïïi x 1, x2 laààn löôït laøø soáá giôøø hoaïït ñoäng cuûûa phaân la lö la so giô hoa Go ng cu PX2 cuøøng saûûn xuaáát 2 loaïïi saûûn phaååm A vaøø B. Naêng cung sa xua loa sa pha va xöôûng thöù nhaáát vaøø phaân xöôûng thöù hai. ng thöù nha va xö ng thöù suaáát vaøø chi phí saûûn xuaáát cuûûa moãi PX trong 1 giôøø: phí sa xua cu sua va giô Ta coùù moâ hình baøøi toaùùn hì co ba toa Phaân xöôûng xö ng PX1 PX 2 Naêng suaáát sua N fx 0, 6 x1 x2 min Saûûn phaååm A 250 250 Sa pha Saûûn phaååm B 100 200 250 x1 250 x2 5000 Sa pha Chi phí (trieääu ñoàng/ giôøø) phí (trie 0,6 1 ng/ giô 100 x1 200 x2 3000 Ñôn ñaët haøøng: ít nhaáát 5.000 SpA, 3.000 SpB. ha ng: nha x1 0 x2 0 Haõy phaân phoáái thôøøi gian hoaïït ñoäng cuûûa 2 phaân pho thô hoa ng cu Duøøng phöông phaùùp hình hoïïc ñeå giaûûi baøøi toaùùn Du ng phö pha hì ho gia ba toa xöôûng sao cho thoaûû yeâu caààu ñôn ñaët haøøng vaøø ng thoa ca ha ng va chi phí saûûn xuaáát thaááp nhaáát. phí sa xua tha nha t. treân nhö sau nhö ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  6. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ PHA HO PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ PHA HO 0,6x1+x2=m Ví duïï 1.12. du Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính hoa ch tuye tí Gia ba toa Mieààn raøøng buoääc Mie ra ng buo 100x1+200x2=3000 D fx 2 x1 x2 min A1(0,20) 20 15 x1 x2 2 A3 10 taêng (10,10) A2(30,0) x1 2 x2 2 10 20 30 10 í x1 0 x2 0 Tr giaûûm gia baèèng phöông phaùùp hình hoïïc ba ng phö pha hì ho 250x1+250x2=5000 Vaääy P.A.T.Ö: x opt(10,10) vaøø f(xopt)=16 trieääu ñoàng. Va P.A.T.Ö va trie ng. g oân PHÖÔNG PHAÙÙP HÌNH HOÏÏC PHÖ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ PHA HO PHA Ví duïï 13: giaûûi baøøi toaùùn f ( x) du gia ba toa -2x 1+x2= m x 1 -x 2 = - 2 3x1 2 x2 x3 min 2 x1 4 x2 3 x3 10 Mieààn raøøng buoääc Mie ra ng buo 3x1 x2 4 x3 5 D C x1 2 x2 2 x3 8 -x1+2x2= -2 2 xj 0 j 1, 3 A1(0,2) Ñöa baøøi toaùùn veàà daïïng chính taééc Ñöa ba toa ve dang chí ta f ( x) 3x1 2 x2 x3 min 2A 2 (2,0) -1 O -2 2 x1 4 x2 3 x3 w1 10 giaû giaûm eãn taêng -1 3x1 x2 4 x3 w2 5 x1 2 x2 2 x3 w3 8 Haøøm muïïc tieâu khoâng bò chaëën. Baøøi toaùùn khoâng Ha mu cha n. Ba toa coùù phöông aùùn toáái öu. co phö a to xj 0, j 1,3, wi 0, i 1,3 y gu CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ PHA PHA Ta coùù P.A.C.B laøø x = (0, 0, 0, 10, 5, 8) Ta coùù co la co Baøøi toaùùn töông ñöông Ba toa tö ñöông x1 5 w1 10 2 x1 0 f ( x) 3x1 2 x2 x3 min 5 5 w2 5 3x1 0 x1 x1 3 3 w1 10 2 x1 4 x2 3x3 (Choïn doøng 2) w3 8 x1 0 N x1 8 w2 5 3x1 x2 4 x3 Choïïn x1 = 5/3, ta ñöôïc P.A môùùi laøø ñöô Cho mô la w3 8 x1 2 x2 2 x3 x 1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3. xj 0 j 1,3, wi 0, i 1,3 coùù P.A.C.B laøø x = (0, 0, 0, 10, 5, 8) vaøø f(x) = 0. Vaøø f(x) = - 5. co la va Va Nhaään xeùùt: Baøøi toaùùn töông ñöông: taïïi raøøng buoääc thöù hai tính Ba toa tö ñöông: ta ra ng buo thöù tí Nha xe t: x 1 theo caùùc bieáán coøøn laïïi, roàài theáá giaùù trò x 1 vöøa tính tí ca bie co la i, ro the gia coùù theåå ñoåi P.A baèèng caùùch taêng x1 baèèng moäät giaùù co the ba ng ca ch ba ng mo gia ñöôïc vaøøo caùùc raøøng buoääc vaøø haøøm muïïc tieâu. ñöô va ca ra ng buo va ha mu trò döông vaøø giöû x 2 = x3 = 0 thoûûa ñieààu kieään wi 0. dö va giöû tho ie kie ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  7. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ PHA PHA Ta coùù keáát quaûû Ta co ke qua Ta coùù co f ( x) 5 w2 x2 3x3 min 20 10 w1 x1 0 3 3 20 2 10 1 x2 2 w1 w2 x2 x3 5 1 3 3 3 3 x1 x2 0 x2 5 x2 2 3 3 5 1 1 4 19 (Choïn doøng 1) x1 w2 x2 x3 19 5 x2 3 3 3 3 w3 x0 5 32 3 19 1 5 2 Choïïn x2 = 2, ta ñöôïc P.A môùùi laøø ñöô Cho mô la w3 w2 x2 x3 3 3 3 3 í x 1 = 1, x 3 = w1 = w2 = 0, w3 = 3 vaøø f(x) = - 7. va xj 0 j 1,3, wi 0, i 1,3 Nhaään xeùùt: Tr Nha xe t: Baøøi toaùùn töông ñöông: taïïi raøøng buoääc thöù nhaáát Ba toa tö ñöông: ta ra ng buo thöù nha coùù theåå ñoåi P.A baèèng caùùch taêng x2 baèèng moäät giaùù co the ba ng ca ch ba ng mo gia tính x2 theo caùùc bieáán coøøn laïïi, roàài theáá giaùù trò x2 vöøa ca bie co la i, ro the gia trò döông vaøø giöû x 3 = w2 = 0 thoûûa ñieààu kieään wi 0. dö va giöû tho ie kie tính ñöôïc vaøøo caùùc raøøng buoääc vaøø haøøm muïïc tieâu. ñöô va ca ra ng buo va ha mu g oân CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ PHA PHA Ta coùù keáát quaûû co ke qua Döïa treân cô sôûû nbaøi toaùùn coùù daïïng chuaåån öïa sô baø toa co da ng chua 3 4 31 f ( x) 7 w1 w2 x3 min f ( x) cjxj min hay max 1 10 5 10 j1 3 1 1 x2 2 w1 w2 x3 nm C 10 5 10 xi ai ,m k xm bi 2 k k1 1 6 39 x1 1 w1 w2 x3 xj 0 j 1, n bi 0 3 10 15 30 Daááu hieääu toáái öu cuûûa baøøi toaùùn Da hie to cu ba toa 1 2 w3 3 w1 x3 Phöông aùùn cöïc bieân ñaàu tieân laøø: Phö a cöï la 2 3 eãn m x0 (b1 , b2 , ; bm ,.0 ,0) f ( x0 ) cibi xj 0 j 1,3, wi 0, i 1,3 Choïïn moäät P.A baáát kyøø cuûûa baøøi toaùùn Cho mo ba ky cu ba toa i1 Baøøi toaùùn coùù P.A.T.U laøø xopt = (1, 2, 0) Ba toa co la n m nm vaøø f(xopt) = - 7 va x D, x ( x1 , x2 , , xn ) f (x ) cjxj ci xi cm k xm k j1 i1 k1 y gu CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ PHA PHA Daááu hieääu baøøi toaùùn khoâng coùù P.A.T.Ö co P.A.T.Ö Da hie ba toa nm m nm m 2 xi bi a i , m k xm k , f x ci xi ai ,m k ci cm xm Ñònh lyùù. Vôùùi moäät phöông aùùn cöïc bieân, neááu toààn taïïi ly Vô mo phö a cöï ne to ta k k k1 i1 k1 i1 j > 0 maøø aij 0, i thì baøøi toaùùn khoâng coùù P.A.T.Ö. thì ba toa co P.A.T.Ö m ma nm Ñaët cm k thì f x thì ai ,m k ci f x0 xm (xem Ví duïï 1.13) du 1.13) mk mk k k1 i1 Heä Aån PA C1 C2 … Ci … C m C m+1 … Cj … Cn Neááu thì thì f x , vì Ne f x0 N xm 0 0 mk k soá C.B C B x1 x2 … xi … x m xm+1 … xj … xm C1 x1 b1 1 0 … … … 0 a1,m+ 1 … a1j … a1n Neááu thì f x thì f x , vì Ne 0 xm 0 0 k C2 x2 b2 0 1 … … … 0 a2,m+ 1 … a2j … a2n mk m … … … … ………… … … ………… Kyùù hieääu laïïi: Ky hie la i: aij ci c j Ci xi bi 0 0……… 0 ai,m+1 … aij … ain j i1 … … … … ………… … … ………… (1) Khi thì thì f ( x) Min 0; j Cm xm bm 0 0 … … … 1 am,m+1 … a mj … amn j f(x) f(x0) 0 0……… 0 … … (2) Khi thì thì m+1 j n f ( x) Max 0; j j ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  8. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH SÔ PHÖ BAÛÛNG ÑÔN HÌNH PHA BA NG Daááu hieääu baøøi toaùùn coùù P.A.C.B. khaùùc toáát hôn Da hie ba toa co kha to Heä AÅn PA C 1 C2 … Ci … C m Cm+1 … CJ … Cn Ñònh lyùù. Vôùùi moäät P.A.C.B, neááu j>0, i: aij > 0 thì baøøi thì ba ly Vô mo ne Soá C.B CB x1 x2 … xi … xm xm+1 … xj … xn toaùùn coùù P.A.C.B khaùùc toáát hôn P.A.C.B ñang xeùùt. toa co kha to xe t. C1 b1 1 0……… 0 a1,m+1 … a1j … a1n x1 Heä AÅn PA C1 C2 … Ci … Cm Cm+1 … Cj … Cn C2 b2 0 1……… 0 a2,m+1 … a2j … a2n x2 so á C.B CB x1 x2 … x i … x m xm+1 … x j … xm … … … ………… … … ……… … … C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n Ci bi 0 0……… 0 ai,m+1 … aij … ain xi C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n … … … ………… … … ……… … … … … … … ………… … … ………… í bm 0 0…… 1 am,m+1 … amj … amn xm Ci xi bi 0 0……… 0 ai,m+1 … aij … ain Cm Tr f(x) f(x0) 0 0……… 0 … … … … … … ………… … … ………… m+1 j n Cm xm bm 0 0 … … … 1 am,m+1 … amj … amn f(x) f(x0) 0 0……… 0 … … m+1 n j g oân THUAÄÄT GIAÛÛI ÑÔN HÌNH THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUA GIA LAÄÄP BAÛÛNG ÑÔN HÌNH LA BANG NHAÄÄN XEÙÙT. Daááu hieääu baøøi toaùùn coùù nhieààu P.A.T.Ö. NHA XE T. Da hie ba toa co nhie P.A.T.Ö Ñuùng ng Vôùùi P.A.C.B.T.Ö Xopt tìm ñöôïc, neááu Vô P.A.C.B.T.Ö ñöô c, ne j = 0, maøø xj ma P.A.T.Ö P.A.T.Ö 0, j? j khoâng laøø P.A.C.B thì baøøi toaùùn coùù P.A.C.B.T.Ö khaùùc ì ba toa co P.A.C.B.T.Ö kha la th Sai C Ñuùng ng KEÁÁT THUÙÙC X/opt (xem Ví duïï 1.15). du 1.15). KE THU aij 0, i? THUAÄÄT GIAÛÛI THUA GIA Sai Taääp phöông aùùn toáái öu: Ta phö a to XAÙÙC ÑÒNH PHÖÔNG AÙÙN MÔÙÙI PHÖ XA A MÔ BAØØI TOAÙÙN BA TOA Tröôøng hôïïp coùù 2 P.A.C.B.T.Ö Xopt vaøø X/opt Trö ng hô co P.A.C.B.T.Ö va Aån vaøøo: Max j va o: xj KHOÂNG COÙÙ P.A.T.Ö CO P.A.T.Ö 0 j Topt = { Xopt + (1 – )X/opt, [0, 1]} 1]} bi Aån ra: Min eãn xi Tröôøng hôïïp coùù 3 P.A.C.B.T.Ö Trö ng hô co P.A.C.B.T.Ö X(1)opt, X(2)opt, X(3)opt aij aij 0 SOÁÁ BÖÔÙC LAËËP SO LA Topt = { X(1)opt + X (2)opt + X(3)opt, }, vôùùi , , 0 vaøø vô va BIEÁÁN ÑOÅI BAÛÛNG ÑÔN HÌNH BIE BA NG LAØØ HÖÕU HAÏÏN LA HA + + = 1. y gu THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA HEÄÄ P.A HE AÅ N 6 131 7 6 1 Ví duïï 1.14. du SOÁÁ SO C.B x1 x2 x3 x4 x5 x6 x7 Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính hoa ch tuye tí Gia ba toa x2 3 0 10 1 1 1 1 1 1 x3 9 0 1 40 2 2 1 f (x) 6x1 x2 x3 3x4 x5 7x6 6x7 min N x5 1 2 4 0 021 3 0 x1 x2 x4 x6 x7 3 fx 5 0 0 60 7 6 14 2x1 x3 4x4 2x6 x7 9 x6 3 0 10 7 1 1 1 1 x3 1 3 0 1 20 0 3 4x1 2x4 x5 3x6 2 2 x5 1 11 1 3 0 11 0 3 xj 0 j 1,7 fx 0 10 0 13 7 2 7 BT khoâng coùù P.A.T.Ö vì co P.A.T.Ö 4= 1 > 0 maøø ai4 < 0, i. ma ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  9. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄÄT GIAÛÛI ÑÔN HÌNH THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUA GIA Ví duïï 1.15. du HEÄÄ P.A HE AÅ N 5 452 3 1 Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính hoa ch tuye tí Gia ba toa SOÁÁ SO C.B x1 x2 x3 x4 x5 x6 f (x) 5x1 4x2 5x3 2x4 x5 3x6 min x4 152 431 0 0 2 2 2x1 4x2 3x3 x4 152 1 x5 60 230 0 4 1 x6 3 36 3 010 0 1 4x1 2x2 3x3 x5 60 fx 472 670 0 0 12 3x1 x3 x6 36 x4 2 4 73 1 128 0 0 2 í 3 xj 0 j 1,6 x5 4 2 53 0 1 0 12 1 Tr 3 Baøøi toaùùn coùù phöông aùùn toáái öu khaùùc hay khoâng? Ba toa co phö a to kha x1 0 13 0 1 5 12 1 0 3 Neááu coùù tìm taääp phöông aùùn toáái öu vaøø chæ ra 3 ta phö va chæ Ne co a to fx 630 4 328 0 0 phöông aùùn toáái öu. phö a to g oân THUAÄÄT GIAÛÛI ÑÔN HÌNH THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUA GIA HEÄÄ P.A HE AÅN 5 452 3 1 HEÄÄ P.A HE AÅ N 5 452 1 3 SOÁÁ SO C.B x1 x2 x3 x4 x5 x6 SOÁÁ SO C.B x1 x2 x3 x4 x5 x6 x4 104 0 011 2 2 2 x4 32 6 031 2 0 2 C x2 2 1 56 0 1 4 60 x2 30 2 3 1 32 0 1 4 2 0 2 x1 12 1 0 13 0 1 5 0 x6 36 3 3 3 010 0 1 f x 292 0 020 0 3 f x 292 020 0 0 3 Baøøi toaùùn coùù P.A.T.Ö xopt=(12, 6, 0, 104, 0, 0) vaøø Ba toa co P.A.T.Ö va Baøøi toaùùn coùù phöông aùùn cöïc bieân toáái öu khaùùc laøø Ba toa co phö a cöï kha la to f(xopt)= 292. eãn x /opt = (0, 30, 0, 32, 0, 36) vaøø f(x /opt) = 292. (0, va Baøøi toaùùn coøøn P.A.C.B.T.Ö khaùùc vì 6 = 0, nhöng x6 Ba toa co P.A.C.B.T.Ö kha vì 0, nhö Taääp phöông aùùn toáái öu Ta phö a to khoâng phaûûi laøø A.C.B. Ta coùù P.A.C.B.T.Ö thöù hai co P.A.C.B.T.Ö thöù pha la baèèng caùùch choïïn aåån x6 laøø aån ñöa vaøøo. ñöa va o. bang ca ch cho a la Topt={ xopt + (1 - )x/opt, 0, 1 } (1 y gu THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA Vôùùi taääp phöông aùùn toáái öu, ta coùù : Vô ta phö a to co NHAÄÄN XEÙÙT. Neááu baøøi toaùùn coùù haøøm muïïc tieâu NHA XE T. Ne ba toa co ha mu x opt + (1 - )x/opt = n (1 f ( x) cj xj Max (12, 6, 0, 104, 0, 0) + (1- )(0, 30, 0, 32, 0, 36) (1- j1 Coùù hai caùùch giaûûi: Co ca ch gia i: = (12 , 30–24 , 0, 32 + 72 , 0, 36 - 36 ) 30 Giaûûi tröïc tieááp baøøi toaùùn (xem Ví duïï 1.16), vôùùi: Gia tröï tie ba toa du 1.16), vô i: N 3 phöông aùùn toáái öu laøø phö a to la Tieâu chuaåån toáái öu laøø chua to la Vôùùi = 0, ta coùù P.A.T.Ö: co P.A.T.Ö Vô 0, j j x /opt = (0, 30, 0, 32, 0, 36) vaøø f(x /opt) = 292. (0, va AÅn vaøøo laøø Min va la j Vôùùi = 1, ta coùù P.A.T.Ö: co P.A.T.Ö Vô 0 j bi AÅn ra laøø Min la xopt = (12, 6, 0, 104, 0, 0) vaøø f(x/opt) = 292. (12, va aij aij 0 Chuyeåån haøøm muïïc tieâu cuûûa baøøi toaùùn veàà min Chuye ha mu cu ba toa ve Vôùùi = ½, ta coùù P.A.T.Ö: co P.A.T.Ö Vô Z opt = (6, 18, 0, 68, 0, 18) vaøø f(zopt) = 292. (6, va g ( x) f ( x) Min ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  10. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄÄT GIAÛÛI ÑÔN HÌNH THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUA GIA Ñöa baøøi toaùùn veàà daïïng chính taééc baèèng caùùch Ñöa ba toa ve da ng chí ta ba ng ca ch Ví duïï 1.16. du theâm aåån phuïï x 5 0 vaøøo raøøng buoääc thöù hai vaøø aån va ra ng buo thöù a phu va Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính hoa ch tuye tí Gia ba toa phuïï x6 0 vaøøo raøøng buoääc thöù ba. va ra ng buo thöù phu Ta coùù baøøi toaùùn ôûû daïïng chuaåån co ba toa ô da ng chua f ( x) 2x1 x2 x3 x4 max f (x) 2x1 x2 x3 x4 max x1 x2 2x3 x4 2 x1 x2 2x3 x4 2 x2 7 x3 3x4 2 x2 7x3 3x4 x5 2 3x3 2 x4 5 í 3x3 2x4 x6 5 Tr xj 0 j 1,4 Baøøi toaùùn coùù phöông aùùn toáái öu khaùùc hay khoâng? Ba toa co phö a to kha xj 0 j 1,6 Neááu coùù, haõy chæ ra phöông aùùn toáái öu khaùùc. chæ phö Ne co a to kha c. Laääp baûûng ñôn hình hì La ba ng g oân THUAÄÄT GIAÛÛI ÑÔN HÌNH THUAÄÄT GIAÛÛI ÑÔN HÌNH THUA GIA THUA GIA HEÄÄ P.A HE AÅ N HEÄÄ P.A HE AÅ N 11 10 0 2 2 111 0 0 SOÁÁ SO C.B SOÁÁ x1 x2 x3 x4 x5 x6 SO C.B x1 x2 x3 x4 x5 x6 x1 1 1210 0 x3 2 2 9 2 210 0 1 1 C 0 x5 x5 17 2 0 1731 0 0 5 400 1 1 x6 0 x4 16 5 0 0320 3 301 0 1 2 1 fx f x 25 600 0 1510 0 3 4 0 7 Vì caùùc j 0, j neân baøi toaùùn coùù P.A.T.Ö laøø neâ ba toa co P.A.T.Ö la x3 ca 1 1 12 0 1 0 1 1 2 2 eãn X opt = (0, 0, 9, 16) vaøø f(Xopt) = 25. va x5 7 5 0 12 1 0 9 0 2 2 Baøøi toaùùn treân khoâng coøøn phöông aùùn toáái öu naøøo co phö Ba toa a to na x6 3 3 0 12 0 0 8 1 2 2 khaùùc vì khoâng coùù j = 0 naøøo vôùùi xj laøø aån khoâng kha vì co na vô la 0 32 0 fx 3 5 0 1 cô baûûn. ba n. 2 2 y gu CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG SÔ THUA GIA MÔ RO NG SÔ THUA GIA MÔ RO NG Xuaáát phaùùt töø baøøi toaùùn daïïng chính taééc Xua pha töø ba toa da ng chí ta n m xig f ( x) c j xj M Min n f ( x) cj xj Min j1 i1 j1 n xig aij x j bi , i 1, m II n N aij x j bi , i 1, m j1 I 0 voâ cuø ng lôùn. xig j1 xj 0, j 1, n; 0, i 1, m, M xj 0 j 1, n bi 0 Baøøi toaùùn (I) ñöôïc goïïi laøø baøøi toaùùn goáác, baøøi toaùùn ñöô go la ba toa go ba toa Ba toa Khoâng laøøm maáát tính toåång quaùùt cuûûa baøøi toaùùn, ta la ma tí to ng qua cu ba toa n, (II) goïïi laøø baøøi toaùùn môûû roääng hay baøøi toaùùn M. go la ba toa mô rong ba toa giaûû söû caùùc bi 0 vaøø ma traään heää soáá cuûûa heää raøøng gia ca va tra he so cu he rang buoääc khoâng chöùa vectô (coäät) ñôn vò naøøo. chöù buo (co t) na o. Moäät phöông aùùn cuûûa baøøi toaùùn M coùù daïïng x x j , xig Mo phö a cu ba toa co da ng Coääng vaøøo moãi raøøng buoääc vôùùi moäät aåån giaûû töông Co ng va ra ng buo vô mo a gia trong ñoù xj goààm n aåån thaäät vaøø xi(g) goààm m aåån giaûû. go a tha va go a gia öùng xi(g) 0 thì ta ñöôïc baøøi toaùùn coùù daïïng: thì ñöô ba toa co da ng: ng ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  11. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAÛÛNG ÑÔN HÌNH MÔÛÛ ROÄÄNG BA NG MÔ RO NG CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG SÔ THUA GIA MÔ RO NG NHAÄÄN XEÙÙT. NHA XE T. Heä AÅn PA C1 C2 … Cm Cm+1 … Cj … Cn Khi thuaäät giaûûi cuûûa baøi toaùùn M keáát thuùùc thì coùù hai thua gia cu baø toa ke thu thì co Soá C.B CB x1 x2 … xm xm+1 … xj … xn tröôøng hôïïp sau ñaây coùù theåå xaûûy ra: trö ng hô co the xa M xn+1 b1 a11 a12 … a1m a1,m+1 … a1j … a1,n [1] Neááu baøøi toaùùn M (Baøøi toaùùn II) khoâng coùù Ne ba toa (Ba toa co M x n+2 b2 a21 a22 … a2m a2,m+1 … a2j … a2,n phöông aùùn toáái öu thì baøøi toaùùn goáác (Baøøi toaùùn I) phö thì ba toa go (Ba toa a to … … … … …… … … ……… … cuõng khoâng coùù phöông aùùn toáái öu. co phö a to M x n+i bi ai1 ai2 … aim ai,m+1 … aij … ai,n [2] Neááu baøøi toaùùn M (Baøøi toaùùn II) coùù phöông aùùn toáái co phö Ne ba toa (Ba toa a to … … … … …… … … ……… … öu thì coùù 3 tröôøng hôïïp xaûûy ra sau ñaây: thì co trö ng hô xa M xn+m bm am1 am2 … amm am,m+1 … amj … am,n í Tr f(x) f(x0) … … … a) Trong heää A.C.B khoâng chöùa aåån giaûû naøøo thì chöùa a gia na thì he 1 2 m m+1 j n P.A.T.Ö cuûûa baøøi toaùùn M cuõng chính laøø P.A.T.Ö P.A.T.Ö cu ba toa chí la P.A.T.Ö Trong ñoù caùùc x n+i (ii = 1, 2, ..., m) laøø caùùc aåån giaûû. Trong ca ( la ca a gia cuûûa baøøi toaùùn goáác (xem V í duïï 1.17). du 1.17). cu ba toa go g oân THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO NG CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG SÔ THUA GIA MÔ RO NG ÑÖA BAØØI TOAÙÙN VEÀÀ DAÏÏNG CHUAÅÅN ÑÖA BA TOA VE DA CHUA b) Neááu trong heää aån cô baûûn cuûûa baøøi toaùùn M coùù Ne he ba cu ba toa co chöùa aåån giaûû nhöng giaùù trò cuûûa chuùùng ñeàu baèèng chöù a gia nhö gia cu chu ng ba ng LAÄÄP BAÛÛNG ÑÔN HÌNH LA BANG khoâng thì P.A.T.Ö cuûûa baøøi toaùùn goáác laøø P.A.T.Ö. thì P.A.T.Ö cu ba toa go la P.A.T.Ö COÙÙ 0? Ñuùng CO ng Ñ uùng ng Coùù Co xig ? xig cuûûa baøøi toaùùn M loaïïi boûû caùùc aåån giaûû baèèng khoâng cu ba toa loa bo ca a gia ba ng 0? C P.A.T.Ö P.A.T.Ö j Sai (xem Ví duïï 1.18). du 1.18). Ñuùng KHOÂN G Khoâng Sai ng KHOÂNG COÙÙ CO COÙÙ P.A.T.Ö CO P.A.T.Ö c) Neááu trong heää aån cô baûûn cuûûa baøøi toaùùn M coùù aij 0? Ne he ba cu ba toa co COÙÙ CO P.A.T.Ö P.A.T.Ö Sai moäät aåån giaûû maøø giaùù trò cuûûa chuùùng khaùùc khoâng thì thì mo a gia ma gia cu chung kha P.A.T.Ö P.A.T.Ö Xaùùc ñònh phöông aùùn môùùi phö Xa a mô baøøi toaùùn goáác khoâng coùù P.A.T.Ö. co P.A.T.Ö ba toa go Aån vaøøo: va Max KEÁÁT THUÙÙC THUAÄÄT GIAÛÛI KE THU THUA GIA eãn j Chuùù yù. Neááu haøøm muïïc tieâu laøø f(x) Max thì heää soáá Max thì he so Chu Ne ha mu la 0 bi Aån ra: j Min caùùc aåån giaûû trong haøøm muïïc tieâu cuûûa baøøi toaùùn M ca a gia ha mu cu ba toa aij aij 0 SOÁÁ BÖ ÔÙC LAËËP SO LA laøø (– M), vôùùi M > 0 voâ cuøøng lôùùn (xem V í duïï 1.19). du 1.19). la vô cu ng lô LAØØ HÖÕU HAÏÏN LA HA BIEÁÁN ÑOÅI BAÛÛNG ÑÔN HÌNH BIE BA NG y gu THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO NG THUA GIA MÔ RO Ví duïï 1.17. (tröôøng hôïïp a). Giaûûi baøøi toaùùn QHTT (trö ng hô du Gia ba toa Ñöa baøøi toaùùn veàà daïïng chuaåån: Ñöa ba toa ve da ng chua n: Theâm hai aåån giaûû x4 0 vaøø x5 0 vaøøo laààn löôït vaøøo va la lö va a gia va f ( x) 8 x1 6 x2 2 x3 min raøøng buoääc thöù nhaáát vaøø thöù hai cuûûa baøøi toaùùn ra ng buo thöù nha va thöù cu ba toa 4 x1 4 x2 3 x3 18 Baøøi toaùùn coùù daïïng chuaåån nhö sau: Ba toa co da ng chua nhö 4 x1 3 x2 4 x3 16 N x j 0 j 1,3 f (x) 8x1 6x2 2x3 M (x4 x5 ) Min Nhaân (– 1) vaøøo raøøng buoääc thöù nhaáát, baøøi toaùùn coùù va ra ng buo thöù nha t, ba toa co 4x1 4x2 3x3 x4 18 daïïng chính taééc nhö sau dang chí ta nhö 4x1 3x2 4x3 x5 16 f ( x) 8 x1 6 x2 2 x3 min x j 0 j 1,5 M 0 voâ cuø ng lôù n. 4 x1 4 x2 3 x3 18 4 x1 3 x2 4 x3 16 Ta coùù baûûng ñôn hình môûû roääng hì co ba ng mô ro ng xj 0 j 1,3 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  12. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO NG THUA GIA MÔ RO Ví duïï 1.18. (tröôøng hôïïp b). Giaûûi baøøi toaùùn QHTT (trö ng hô du Gia ba toa HEÄÄ AÅN HE P.A 6 2 8 SOÁÁ SO C.B f ( x) 6 x1 3x2 x3 min x1 x2 x3 x4 18 4 4 3 2 x1 5x2 x3 10 M x5 M 4 x1 3x2 2 x3 16 16 3 4 4 fx 2 x1 4x2 x3 8 34M 8M 8 7M 6M 2 x4 2 0 7 1 M xj 0 j 1,3 x1 3 Theâm aåån phuïï x 4 0 vaøøo raøøng buoääc thöù nhaáát va ra ng buo thöù nha 8 4 1 1 a phu 4 f x 2M 32 0 M 12 7 M 10 f ( x ) 6x1 3x2 x3 min í x2 0 2 1 7 6 2 x1 5x2 x3 x4 10 Tr x1 5 25 8 0 1 4 x1 3x2 2 x3 16 2 4 8 0 0 94 fx 2 x1 4 x2 x3 8 Baøøi toaùùn coùù P.A.T.Ö X opt=(5/2, 2, 0), f(Xopt)= –8. Ba toa co P.A.T.Ö xj 0 j 1, 4 g oân THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO NG Theâm hai aåån giaûû x5 0, x 6 0 laààn löôït vaøøo raøøng la lö va ra ng a gia HEÄÄ HE AÅ N 6 3 1 0 P.A buoääc thöù hai vaøø raøøng buoääc thöù ba. buo thöù va rang buo thöù SOÁÁ SO C.B x1 x2 x3 x4 Ta coùù baøøi toaùùn daïïng chuaåån nhö sau co ba toa da ng chua nhö x4 0 10 2 5 1 1 C f (x) 6x1 3x2 x3 M(x5 x6 ) min x5 M 16 3 0 4 2 2x1 5x2 x3 x4 x6 10 M 8 4 0 2 1 6 M 3 3M 1 0 4x1 3x2 2x3 x5 fx 24M 6M 16 x4 0 2 1 0 1 0 2x1 4x2 x3 eãn x6 8 x5 M 0 0 0 11 0 xj 0 j 1, 6 M 0 x1 1 6 4 1 2 0 2 Ta coùù baûûng ñôn hình môûû roääng hì co ba ng mô ro ng 0 fx 0 11M 9 2 24 y gu THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO NG Ví duïï 1.19. (tröôøng hôïïp c). Giaûûi baøøi toaùùn QHTT (trö ng hô du Gia ba toa HEÄÄ HE AÅ N 6 3 0 1 P.A f ( x) 2 x1 x2 x3 max SOÁÁ SO C.B x1 x2 x3 x4 4 x1 x2 2 x3 12 x4 0 2 10 1 0 2 x1 2 x2 x3 10 x5 M 0 0 110 0 N x1 2 x2 1 2 x3 10 x3 1 8 2 4 0 1 xj 0 j 1,3 Theâm 2 aåån phuïï x4, x5 0 vaøøo raøøng buoääc (1) & (2) a phu va ra ng buo 0 fx 11M 1 0 4 8 f ( x) 2 x1 x2 x3 max P.A.T.Ö cuûûa BTM laøø P.A.T.Ö cu la x 0, 0, 8, 2, 0, 0 4 x1 x2 2 x3 x4 12 vôùùi aåån giaûû x5 = 0 vô a gia 2 x1 2 x2 x3 x5 10 P.A.T.Ö cuûûa BT goáác laøø xopt = (0, 0, 8) P.A.T.Ö cu go la x1 2 x2 1 2 x3 10 vaøø f(xopt) = 8. va xj 0 j 1, 5 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  13. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO NG THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG THUA GIA MÔ RO HEÄÄ HE AÅN 2 1 1 0 0 P.A Theâm 2 aåån giaûû vaøøo x6, x 7 0 laààn löôït vaøøo raøøng la lö va ra ng Theâ a gia va x1 x2 x3 x4 x5 SOÁÁ SO C.B buoääc (1) & (3). (3). buo x6 12 4 1 2 1 0 M Ta coùù baøøi toaùùn daïïng chuaåån nhö sau co ba toa da ng chua nhö 0 x5 10 2 2 1 0 1 f ( x) 2x1 x2 x3 M x6 x7 max x7 M 1 10 0 0 1 2 2 fx M1 0 4x1 x2 2x3 x4 x6 12 3 22 M 3M M 2 3M 1 2 x3 1 1 6 2 1 0 1 2x1 2x2 x3 x5 10 2 2 x5 0 3 1 16 4 0 1 í 2 2 1 x1 2x2 x3 x7 10 x7 9 1 13 0 0 0 M Tr 4 4 2 f x 6 13M 1M 1 0 0 0 4M 9 1 0 j 1,7 M 0 2 4 2 xj P.A.T.Ö Xopt = (0, 0, 6, 0, 16, 0, 13), vôùùi x7 = 13 Ö 0 P.A.T. vô Ta coùù baûûng ñôn hình môûû roääng hì co ba ng mô ro ng neân baøøi toaùùn goáác khoâng coùù P.A.T.Ö. co P.A.T.Ö ba toa go g oân BAØØI TAÄÄP CHÖÔNG 1 BA TA CHÖ LAÄÄP MO HÌNH BAØØI TOAÙÙN LA BA TOA [1] [2] [3] [4] BAØØI TOAÙÙN QHTT DAÏÏNG CHÍNH TAÉÉC DA NG CHÍ BA TOA TA C [5a] [5b] XAÙÙC ÑÒNH P.A – P.A.C.B VAØØ P.A.T.Ö. VA P.A.T.Ö XA [6] [7a] [7b] [7c] GIAÛÛI BAØØI TOAÙÙN QHTT BAÈÈNG PP HÌNH HOÏÏC GIA BA TOA BA NG HO eãn [8a] [8b] [8c] GIAÛÛI BAØØI TOAÙÙN QHTT BAÈÈNG PP ÑÔN HÌNH GIA BA TOA BA NG [9] [10] [11] [12] [13] [14] [15] [16] [17] y gu N ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  14. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØI TAÄP CHÖÔNG 1 LAÄP MO HÌNH BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH [1] Moät xí nghieäp cheá bieán ñoà goã hieän coù 3.000 ñôn vò goã nguyeân lieäu nhoùm I, 5.000 ñôn vò goã nguyeân lieäu nhoùm II vaø 2.000 ñôn vò goã nguyeân lieäu nhoùm III. Theo keá hoaïch xí nghieäp phaûi saûn xuaát boán loaïi haøng hoaù: boä tuû trang trí cao caáp, boä cöûa cao caáp, boä sa-loâng vaø boä giöôøng nguû. Ñònh möùc nguyeân lieäu duøng cho saûn xuaát vaø lôïi nhuaän khi saûn xuaát moät ñôn vò haøng hoùa ñöôïc theå hieän trong baûng sau Saûn phaåm í Tr Ñònh möùc Boä tuû Boä cöûa Boä sa-loâng Boä giöôøng nguû Nguyeân lieäu Goã nhoùm I 30 40 0 10 Goã nhoùm II 10 20 50 60 g Goã nhoùm III 10 50 80 20 Lôïi nhuaän (trieäu ñoàng) 0,5 0,8 0,4 0,6 oân Haõy laäp moâ hình baøi toaùn xaùc ñònh soá löôïng saûn xuaát caùc saûn phaåm sao cho xí nghieäp ñaït lôïi nhuaän nhieàu nhaát? [2] Moät coâng ty coù keá hoaïch quaûng caùo moät loaïi saûn phaåm do coâng ty saûn xuaát trong thôøi gian moät thaùng vôùi toång chi phí laø 100 trieäu ñoàng. Caùc phöông tieän ñöôïc choïn C ñeå quaûng caùo saûn phaåm laø truyeàn hình, baùo vaø phaùt thanh vôùi soá lieäu ñöôïc döï kieán nhö sau: Phöông tieän Chi phí cho Soá laàn quaûng caùo Döï ñoaùn soá ngöôøi quaûng caùo moãi laàn quaûng caùo toái ña xem quaûng caùo eãn (trieäu ñoàng) trong thaùng trong moãi laàn Truyeàn hình (1 phuùt) 1,5 60 15.000 Baùo (1/2 trang) 1 26 30.000 Phaùt thanh (1 phuùt) 0,5 90 9.000 y Vì lyù do chieán löôïc tieáp thò neân coâng ty yeâu caàu phaûi coù ít nhaát 30 laàn quaûng caùo treân truyeàn hình trong thaùng. Haõy laäp moâ hình baøi toaùn sao cho phöông aùn quaûng caùo saûn gu phaåm cuûa coâng ty laø toái öu. [3] Moät xí nghieäp coù theå söû duïng toái ña 510 giôø maùy caùn, 360 giôø maùy tieän vaø 150 giôø maùy maøi ñeå cheá taïo 3 saûn phaåm A, B vaø C. Ñeå cheá taïo moät saûn phaåm A caàn 9 giôø maùy caùn, 5 giôø maùy tieän vaø 3 giôø maùy maøi; moät saûn phaåm B caàn 3 giôø maùy caùn, 4 giôø maùy tieän; moät saûn phaåm C caàn 5 giôø maùy caùn, 3 giôø maùy tieän vaø 2 giôø maùy maøi. N Moãi saûn phaåm A trò giaù 48 ngaøn ñoàng, moãi saûn phaåm B trò giaù 16 ngaøn ñoàng vaø moãi saûn phaåm C trò giaù 27 ngaøn ñoàng. [4] Haõy laäp moâ hình baøi toaùn xí nghieäp caàn cheá taïo moãi loaïi bao nhieâu saûn phaåm ñeå coù toång giaù trò saûn phaåm lôùn nhaát. [5] Moät xí nghieäp vaän taûi caàn chuyeån moät loaïi haøng hoùa töø ba kho haøng A1, A2 vaø A3 ñeán boán cöûa haøng B1, B2, B3 vaø B4. Löôïng haøng hieän coù ôû moãi kho Ai (i = 1, 2, 3), ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  15. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ nhu caàu nhaän haøng ôû caùc cöûa haøng Bj (j = 1, 2, 3, 4) vaø chi phí vaän chuyeån moät ñôn vò haøng hoùa töø moãi kho ñeán moãi cöûa haøng ñöôïc cho ôû baûng sau Cöûa haøng Löôïng haøng Chi phí vaän chuyeån B2 B3 B4 hieän coù (taán) B1 Kho A1 3 4 0 1 40 A2 1 2 5 6 30 A3 1 5 8 2 30 í Nhu caàu cuûa cöûa haøng (taán) 20 25 30 15 Tr Haõy laäp moâ hình baøi toaùn vaän taûi haøng hoùa sao cho toång chi phí vaän taûi beù nhaát? BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH DAÏNG CHÍNH TAÉC [6] Ñöa caùc baøi toaùn quy hoaïch tuyeán tính sau ñaây veà daïng chính taéc g f ( x ) 4 x1 3x2 2 x3 min f ( x) 2 x1 3x2 x3 max x1 x2 4 x3 6 4 x1 2 x2 x3 15 oân (a) 8; (b) 2 x1 x2 3 x3 5x1 2 x2 x3 10 3x1 4 x2 2 x3 3 3x1 6 x2 2 x3 25 x1 0, x2 0 x1 0, x3 0 XAÙC ÑÒNH PHÖÔNG AÙN – PHÖÔNG AÙN CÖÏC BIEÂN VAØ PHÖÔNG AÙN TOÁI ÖU C [7] Cho baøi toaùn quy hoaïch tuyeán tính f(x) 3x1 7 x2 x3 2 x 4 max 2x1 3 x2 2 x4 30 x3 2x1 2 x2 3 x3 60 eãn 2x1 2 x2 3 x3 +4 x4 32 xj 0 (j 1,4) Xeùt caùc veùctô X = (0, 0, 0, 8), Y = (14, 0, 0, 1), Z = (7, 0, 0, 9/2), T = (16, 1, 0, ½). (a) Vectô naøo laø phöông aùn; vectô naøo laø phöông aùn cöïc bieân cuûa baøi toaùn? y (b) Cho bieát Y laø phöông aùn toái öu cuûa baøi toaùn treân. Trong soá caùc vectô coøn laïi, vectô naøo laø phöông aùn toái öu cuûa baøi toaùn? gu [8] Tìm phöông aùn cöïc bieân khoâng suy bieán cuûa caùc baøi toaùn quy hoaïch tuyeán tính sau f ( x ) 4 x1 3x2 2 x3 min f ( x) 4 x1 3x2 2 x3 min x1 x2 x3 1 x1 x2 x3 10 (a) ; (b) ; x1 x2 x3 3 2 x1 x2 3x3 14 N xj 0, j 1, 2,3 x j 0, j 1, 2,3 f ( x) 4 x1 3x2 2 x3 min x1 x2 x3 4 (c) x1 x2 0 xj 0, j 1, 2,3 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  16. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ GIAÛI BAØI TOAÙN QHTT BAÈNG PHÖÔNG PHAÙP HÌNH HOÏC [9] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây baèng phöông phaùp hình hoïc f ( x) x1 x2 max f ( x ) 5x1 4 x2 max x1 x2 1 x1 2 x2 8 (a) 6; (b) 4; 3x1 2 x2 x1 2 x2 3x1 x2 9 3x1 2 x2 12 x j 0, j 1, 2 x j 0, j 1, 2 f ( x ) 5x1 3x2 min í 2 x1 x2 6 Tr (c) x1 x2 0 2 x1 x2 0 x j 0, j 1, 2 g GIAÛI BAØI TOAÙN QHTT BAÈNG PHÖÔNG PHAÙP ÑÔN HÌNH [10] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: oân f ( x ) x1 x 2 3x3 min 2 x1 x2 x3 1 4 x1 2x2 x3 2 3x1 x3 5 C x j 0 j 1,3 Ñs: Xopt = (1/3, 11/3, 4) vaø fmin = – 46/3 [11] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: eãn f ( x) x1 x 2 2 x 4 2 x5 3 x6 min x1 x4 x5 x6 2 x2 x4 x6 12 x3 2 x4 4 x5 3x 6 9 x j 0 j 1,6 y Ñs: Xopt = (0, 8, 0, 3, 0, 1) vaø fmin = – 17 [12] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: gu f ( x) 3x1 4 x 2 3x3 x 4 max 1 1 x1 x2 2 x4 x5 3 2 4 1 1 3x1 x3 x4 x5 x6 1 N 4 2 11x1 17 x 4 x5 2 x6 x7 20 x j 0 j 1,7 Ñs: Xopt = (0, 3, 1, 0, 0, 0, 20) vaø fmax = 15 [13] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  17. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ f ( x) x2 2 x3 2 x5 min x1 3x 2 x3 2 x5 7 2 x2 4 x3 x4 12 4 x2 2 x3 8 x5 x6 10 xj 0 j 1,6 Ñs: Xopt = (10, 0, 3, 0, 0, 4) vaø fmin = – 6 [14] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: f ( x) 3x1 4 x 2 2 x 3 2 x 4 min í 2 x1 2 x2 x4 28 Tr x1 5 x2 3 x3 2 x4 31 2 x1 2 x2 2 x3 x4 16 xj 0 j 1,4 g Ñs: Xopt = (11, 3, 0, 0) vaø fmin = 45 [15] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: oân f ( x ) 3x1 2 x2 2 x3 x4 min 2 x1 4 x3 10 x2 x4 3 x1 2 x2 2x4 8 x3 4 x1 2 x3 4 x2 C 0 j 1,4 xj Ñs: Xopt = (28, 108, 0, 62) vaø fmin = – 70 [16] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: eãn f ( x) x1 2 x 2 3x 3 x 4 min x1 2 x2 3 x3 15 2 x1 x2 5 x3 20 x1 2 x2 x3 x4 10 y xj 0 j 1,4 Ñs: Xopt = (5/2, 5/2, 5/2, 0) vaø fmin = – 15 [17] Giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây: gu f ( x ) x1 2 x 2 x 4 x5 5 x 6 min 6 x1 2 x2 x3 x4 x5 2 x6 4 1 1 2 x1 x2 x3 x4 x5 3 3 2 N 1 3x1 x2 2 x3 4 x4 x5 x6 2 2 xj 0 j 1,6 Ñs: Baøi toaùn khoâng coù P.A.T.Ö. [18] Duøng phöông phaùp ñôn hình giaûi caùc baøi toaùn töø baøi taäp [1] ñeán baøi taäp [8]. Ñs: [1] Xopt = (80, 0, 0, 60) vaø f(Xopt) = 76. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  18. ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA BAØØI TOAÙÙN QUY HOAÏÏCH BA TOA HOACH CHÖÔNG 2 Muïïc ñích vaøø yù nghóa Mu ñích va nghó TUYEÁÁN TÍNH ÑOÁI NGAÃU TUYE TÍ Vôùùi baøøi toaùùn QHTT, baøøi toaùùn goáác, kyùù hieääu laøø P Vô ba toa ba toa go ky hie la 1. CAÙÙCH THAØØNH LAÄÄP BAØØI TOAÙÙN QUY HOAÏÏCH CA CH THA NH LA BA TOA HOA CH Ths. Nguyeãn Coâng Trí Trí (Primal), chuùùng ta coùù theåå thieáát laääp baøøi toaùùn QHTT chung co the thie la ba toa TUYEÁÁN TÍNH ÑOÁI NGAÃU TUYE TÍ khaùùc, baøøi toaùùn ñoái ngaãu, kyùù hieääu laøø D (Dual), kha c, ba toa ky hie la (Xem) Xem) sao cho töø lôøøi giaûûi cuûûa baøøi toaùùn naøøy ta coùù theåå thu töø lô gia cu ba toa na co the 2. CAÙÙC ÑÒNH LYÙÙ ÑOÁI NGAÃU CA LY (Xem) Xem) Copyright 2001 thaääp ñöôïc thoâng tin veàà lôøøi giaûûi cuûûa baøøi toaùùn kia. tha ñöô ve lô gia cu ba toa Ñeå coùù thoâng tin caààn thieáát veàà baøøi toaùùn goáác, coùù co ca thie ve ba toa go c, co 3. THUAÄÄT GIAÛÛI ÑÔN HÌNH ÑOÁI NGAÃU THUA GIA (Xem) theåå nghieân cöùu treân baøøi toaùùn ñoái ngaãu cuûûa noùù. cöù the ba toa cu no í 4. MOÄÄT SOÁÁ ÖÙNG DUÏÏNG CUÛÛA LYÙÙ THUYEÁÁT ÑOÁI MO SO NG DU CU LY THUYE Hôn nöõa, khi phaân tích ñoàng thôøøi caûû hai baøøi nö tí ng thô ca ba Tr NGAÃU TRONG BAØØI TOAÙÙN QHTT BA TOA toaùùn goáác vaøø ñoái ngaãu, chuùùng ta coùù theåå ruùùt ra toa go va chung co the ru (Xem) Ths. Nguyeãn Coân g Trí Trí caùùc keáát luaään coùù giaùù trò veàà maëët toaùùn hoïïc laãn veàà Ths. ca ke lua co gia ve ma toa ho ve 5. BAØØI TAÄÄP BA TA maëët yùù nghóa kinh teáá. ma y nghó te (Xem) Copyright 2001 g oân THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA THA NH LA BA TOA Xeùùt baøøi toaùùn QHTT (P) döôùi daïïng chính taééc dö da ng chí Xe ba toa ta Goïïi g(y) laøø haøøm muïïc tieâu cuûûa baøøi toaùùn (II), ta coùù Go la ha mu cu ba toa co ct x g(y) = min{ctx + yt(b – Ax)}, vôùùi x 0. vô 0. f P ( x) min P I Ax b c tx + yt(b – Ax), vôùùi x 0. vô 0. x 0. Neááu x laøø P.A cuûûa baøøi toaùùn (I) thì b – Ax = 0 vaøø thì C Ne la cu ba toa va Vôùùi x = (x1, x2,... , x n) n, b = (b , b ,... , b ) Vô m 1 2 m g(y) ctx. Vaääy g(y) laøø moäät caään döôùi baáát kyøø cuûûa la mo ca dö ba ky cu Va Giaûû söû baøøi toaùùn (P) coùù P.A.T.U laøø x opt vaøø goïïi x0 laøø Gia ba toa co la va go la moäät P.A cuûûa baøøi toaùùn (P), ta coùù ctx opt ctx0. mo cu ba toa co haøøm muïïc tieâu. ha mu Goïïi x = (x 1, x2,... , x n) n, vôùùi x 0 sao cho Go vô sao Ta tìm caään döôùi lôùùn nhaáát Max{g(y)}, thaäät vaääy tì ca dö lô nha tha va Ax – b 0 g(y) = min{ctx + yt(b – Ax)}, vôùùi x 0. vô 0. eãn Baøøi toaùùn töông ñöông: Ba toa tö ñöông: = min{ctx + ytb – ytAx}, vôùùi x 0. vô 0. t t L ( x, y ) c x y b Ax min = min{ytb + (c t – ytA)x}, vôùùi x 0. vô 0. P II x0 = ytb + min{ (ct – ytA)x}, vôùùi x 0. vô 0. Rm. y y gu THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA THA NH LA BA TOA Ví duïï 2.1. du Xeùùt Xe t t 0 khi c yA 0 Baøøi toaùùn ñoái ngaãu cuûûa baøøi toaùùn QHTT sau ñaây Ba toa cu ba toa min c t yt A x khi c t yt A 0 x0 Vaääy ta ñöôïc ñöô Va f ( x) 2 x1 8 x4 6 x5 min g(y) = ytb 2 x1 x3 x5 4 Suy ra baøøi toaùùn ñoái ngaãu coùù daïïng ba toa co da ng 2 x2 x5 4 N x2 2 x3 3 x4 13 t t g ( y) yb max g ( y) yb max xj 0 j 1, 5 ct yt A 0 yt A ct D laøø baøøi toaùùn la ba toa f D ( y) 4 y1 4 y2 13 y3 max y Rm. y Rm. 2 y1 2 Hay baøøi toaùùn töông ñöông ba toa tö ñöông 2 y2 y3 0 ytb g ( y) max y1 2 y3 0 At y c D 3 y3 8 y Rm. y1 y2 6 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  19. ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA Baøøi toaùùn goáác (P) Baøøi toaùùn ñoái ngaãu (D) Ví duïï 2.2. Vieáát baøøi toaùùn ñoái ngaãu vaøø chæ ra caùùc va chæ Ba toa go Ba toa du Vie ba toa ca caëëp raøøng buoääc ñoái ngaãu cuûûa baøøi toaùùn QHTT ca ra ng buo cu ba toa Haøøm muïïc tieâu Haøøm muïïc m u Ha mu tieâ Ha mu Baøøi toaùùn ñoái ngaãu Ba toa n f D ( y) bi yi max f ( x) x1 2 x2 x3 2 x4 min f P ( x) cjxj min fD ( y ) y1 3 y2 4 y3 max j1 i1 Raøøng buoääc thöù i Ra ng buo thöù Raøøng buoääc thöù j Ra ng buo thöù x1 x2 2 x3 2x4 1 y1 3 y2 2 y3 1 3x1 x2 x3 3 y1 y2 3 y3 2 m n 2 x1 3 x2 x3 x4 4 2 y1 y2 y3 1 aij yi c j , j 1, n aij x j bi i 1, m 2 y1 y3 2 xj 0 j 1, 2 i1 j1 Caùùc caëëp ñoái ngaãu Ca ca y1 0, y2 0 AÅn thöù j thöù AÅn thöù i thöù í x1 0, y1 3 y2 2 y3 1 1 Tr x2 0, y1 y2 3 y3 2 2 0, j 1, n yi 0, i 1, m xj x1 x2 2 x3 2 x4 1, y1 0 3 khoâ ng raøng buoä c khoâng raøng buoä c VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 3 x1 x2 x3 3, y2 0 4 VD2.2 g oân THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA Ví duïï 2.3. Vieáát baøøi toaùùn ñoái ngaãu vaøø chæ ra caùùc va chæ Ví duïï 2.4. Vieáát baøøi toaùùn ñoái ngaãu vaøø chæ ra caùùc va chæ du Vie ba toa ca du Vie ba toa ca caëëp raøøng buoääc ñoái ngaãu cuûûa baøøi toaùùn QHTT caëëp raøøng buoääc ñoái ngaãu cuûûa baøøi toaùùn QHTT ca ra ng buo cu ba toa ca ra ng buo cu ba toa Baøøi toaùùn ñoái ngaãu Ba toa f (x) 4 x1 3x2 8 x3 m in f ( x) 2 x x 8x max 1 2 3 x1 f D ( y ) 28 y1 10 y2 15 y3 min C 7 x1 4 x2 2 x3 28 1 0 1 2 x2 7 y1 3 y2 2 y3 2 3 x1 x2 3 x3 10 0 1 2 5 x3 4 y1 y2 3y3 1 2 x1 3 x2 x3 15 Caùùc raøøng buoääc ñoái ngaãu xj 0 j 1, 3 Ca ra ng buo 2 y1 3 y2 y3 8 Baøøi toaùùn ñoái ngaãu x 0, Ba toa xj 0 j 1, 2 y1 0, y3 0 y1 4 1 Caùùc caëëp ñoái ngaãu Ca ca 1 f D ( y) 2 y1 5 y2 max eãn x2 0, y2 3 2 x1 0, 7 y1 3 y2 2 y3 2 1 10 4 x3 0, y1 2 y2 8 3 y1 x2 0, 4 y1 y2 3 y3 1 2 01 3 x1 x3 2, y1 0 4 y2 7 x1 4 x2 2 x3 28, y1 0 3 12 8 x2 2 x3 5, y2 0 5 2 x1 3 x2 x3 15, y3 0 4 yj 0; j 1, 2 y gu THAØØNH LAÄÄP BAØØI TOAÙÙN ÑOÁI NGAÃU THA NH LA BA TOA CAÙÙC ÑÒNH LYÙÙ ÑOÁI NGAÃU CA LY Ví duïï 2.5. Vieáát baøøi toaùùn ñoái ngaãu vaøø chæ ra caùùc va chæ du Vie ba toa ca Ñ ÒNH LYÙÙ 1. LY caëëp raøøng buoääc ñoái ngaãu cuûûa baøøi toaùùn QHTT ca ra ng buo cu ba toa Neááu moäät trong hai baøøi toaùùn ñoái ngaãu nhau coùù Ne mo ba toa co Baøøi toaùùn ñoái ngaãu Ba toa f ( x ) 2 x1 5 x 2 max P.A.T.Ö thì baøøi toaùùn kia cuõng coùù P.A.T.Ö vaøø giaùù trò P.A.T.Ö thì ba toa co P.A.T.Ö va gia fD ( y) 4 y1 3 y2 8 y3 m in haøøm muïïc tieâu cuûûa chuùùng baèèng nhau. ha mu cu chu ng ba ng 10 4 x1 y1 01 3 HEÄÄ QUAÛÛ 1. HE QUA 1 0 1 2 N x2 y2 12 8 0 1 2 5 Ñ ieààu kieään caààn vaøø ñuû ñeå cho caùùc baøøi toaùùn ñoái ie kie ca va ca ba toa y3 xj 0; j 1, 2 ngaãu nhau coùù phöông aùùn toáái öu laøø moãi baøøi toaùùn co phö a to la ba toa Raøøng buoääc ñoái ngaãu y j Ra ng buo 0 j 1, 3 coùù ít nhaáát moäät phöông aùùn. co nha mo phö a n. x1 0, y1 y3 2 1 HEÄÄ QUAÛÛ 2. HE QUA x2 0, y2 2 y3 5 2 Ñ ieààu kieään caààn vaøø ñuû ñeå cho caùùc baøøi toaùùn ñoái ie kie ca va ca ba toa x1 4, y1 0 3 ngaãu nhau khoâng coùù P.A.T.Ö laøø moäät baøøi toaùùn coùù co P.A.T.Ö la mo ba toa co x2 3, y2 0 4 P.A coøøn baøøi toaùùn kia khoâng coùù P.A. co ba toa co 2 x2 8, 0 5 x1 y3 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  20. ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CAÙÙC ÑÒNH LYÙÙ ÑOÁI NGAÃU CAÙÙC ÑÒNH LYÙÙ ÑOÁI NGAÃU CA LY CA LY ÑÒNH LYÙÙ 2.(ÑÒNH LYÙÙ ÑOÄ LEÄÄCH BUØØ YEÁÁU) LY 2.(Ñ LY LE CH BU YE U) ÑÒNH LYÙÙ 3.(ÑÒNH LYÙÙ ÑOÄ LEÄÄCH BUØØ MAÏÏNH) LY 3.(Ñ LY LE CH BU MA NH) Ñ ieààu kieään caààn vaøø ñuû ñeå caëëp baøøi toaùùn ñoái ngaãu ie kie ca va ca ba toa Neááu caëëp baøøi toaùùn ñoái ngaãu nhau coùù P.A.T.Ö. thì co P.A.T.Ö thì Ne ca ba toa nhau coùù P.A.T.Ö. laøø trong caëëp raøøng buoääc ñoái co P.A.T.Ö la ca ra ng buo toààn taïïi moäät caëëp phöông aùùn sao cho trong caùùc to ta mo ca phö a ca ngaãu, neááu raøøng buoääc naøøy xaûûy ra vôùùi daááu baáát caëëp ño ái ngaãu, neááu raøøng buoääc naøøy xaûûy ra vôùùi daááu ca ne ra ng buo na xa vô da ne ra ng buo na xa vô da ba ñaúng thöùc thì raøøng buoääc kia xaûûy ra vôùùi daááu baáát ng thöù thì rang buo xa vô da ba ñaúng thöùc ngaëët (“>” hoaëëc “ 0 thì thì Ne Neááu xjopt = 0 thì toààn taïïi thì to ta Ne aij yiopt aij yiopt cj cj i1 i1 , n n Neááu bi thì toààn taïïi yiopt thì to ta 0 (> hoaëëc 0 y1 = 2. Töø (3): x3= 6 > 0 y1 + y2 + 3y3 = 1 f ( y) 50 y 16 y 23 y m in D 1 2 3 Töø (4): x4= 5 > 0 6y1 + 2y2 + y3 = 4 5y 3y 4y 2 6y 1 2 3 y 2 Giaûûi heää phöông trình treân, ta coùù y1 = 2; y 2 = -23/5; Gia he phö trì co 1 y y 3y 1 y3 = 6/5. Vaääy, P.A.T.Ö cuûûa baøøi toaùùn ñoái ngaãu laøø Va y, P.A.T.Ö cu ba toa la 1 2 3 6y 2y y 4 yopt= (2, -23/5, 6/5) vaøø fD(yopt) = 54. va 1 2 3 y 0; y 0 2 3 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
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
4=>1