Slide quy hoạch tuyến tính - Thầy Nguyễn Công Trí

Ths. Nguyeãn Coâng Tr. ã â ã â íí Copyright 2001 Ths. Nguyeãn Coâng Trã â í Copyright 2001 1. THIEÁÁT LAÄÄP MO HÌNH BA ØØI TOAÙÙN (Xem) 2. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QUY HOAÏÏCH TUYEÁÁN TÍNH (Xem) 3. CAÙÙC KHAÙÙI NIEÄÄM CÔ BAÛÛN VEÀÀ BAØØI TOAÙÙN QUY HOAÏÏCH TUYEÁÁN TÍNH (Xem) 4. CAÙÙC PHÖÔNG PHAÙÙP GIAÛÛI BAØØI TOAÙÙN QUY HOAÏÏCH TUYEÁÁN TÍNH (Xem) 5. BAØØI TAÄÄP (Xem) BAØØI TOAÙÙN QUY HOAÏÏCH TUYEÁÁN TÍNH CHÖÔNG 1 Ví duïï 1.1. BAØØI TOAÙÙN LAÄÄP KEÁÁ HOAÏÏCH SAÛÛN XUAÁÁT Moäät xí nghieääp duøøng 3 loaïïi nguyeân lieâ ääu: N1; N2; N3 ñeåå saûûn xuaáát ra moäät loaïïi saûûn phaååm theo 3 phöông phaùùp khaùùc nhau: PP1; PP2; PP3. Ñònh möùùc nguyeân â lieääu vaøø soáá löôïïng saûûn phaååm saûûn xuaáát ra trong 1 giôøø ñöôïïc cho ôûû baûûng sau: Haõy laõ ääp moâ hâ ình baøøi toaùùn sao cho xí nghieääp saûûn xuaáát ra nhieààu saûûn phaååm nhaáát? MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT 91210Soáá saûûn phaååm (sp/giôøø) 463450N3 142350N2 354250N1 PP3PP2PP1 Ñònh möùùc nguyeân lieâ ääuSoáá löôïïng hieään coùù (ñv) Nguyeânâ Lieääu Goïïi x1, x2, x3 laààn löôïït laøø thôøøi gian saûûn xuaáát ra saûûn phaååm theo 3 phöông phaùùp PP1, PP2, PP3. Toåång saûûn phaååm saûûn xuaáát (caààn laøøm cöïïc ñaïïi) f(x) = 10x1 + 12x2 + 9x3 max Do xí nghieääp chæ coùù 250 nguyeân lieâ ääu N1 neânâ x1, x2, x3 phaûûi thoûûa maõn 4xõ 1 + 5x2 + 3x3 250 Töông töïï cho caùùc nguyeân lieâ ääu N2, N3 ta coùù 2x1 + 4x2 + x3 350 vaøø 3x1 + 6x2 + 4x3 450 Dó nhieân ta phaâ ûûi coùù x1, x2, x3 khoâng aâmâ â Vaääy moâ hâ ình baøøi toaùùn ñöôïïc phaùùt bieååu nhö sau: Tìm caùùc bieáán x1, x2, x3 sao cho f(x)= 10x1 + 12x2 + 9x3 max, thoûûa caùùc ñieààu kieään 4x1 + 5x2 + 3x3 250 2x1 + 4x2 + x3 350 3x1 + 6x2 + 4x3 450 x1 0 x2 0 x3 0 MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT Ví duïï 1.2. BAØØI TOAÙÙN PHA CAÉÉT VAÄÄT LIEÄÄU Moäät xí nghieääp may maëëc caààn saûûn xuaáát ñuùùng 2.000 quaààn vaøø ít nhaáát 1.000 aùùo. Moãi taã áám vaûûi coùù 6 caùùch caéét nhö sau: Haõy tõ ìm phöông aùùn caéét quaààn aùùo sao cho toåång soáá taáám vaûûi laøø ít nhaáát? MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT 10006 01205 90604 70703 55802 35901 AÙÙoQuaàànCaùùch caéét Goïïi xj (j = 1, 2, ..., 6) laøø soáá taáám vaûûi ñöôïïc caéét theo caùùch thöùù j. Toåång soáá taáám vaûûi duøøng ñeåå saûûn xuaáát (caààn laøøm cöïïc tieååu) laøø f(x) = x1 + x2 + x3 + x4 + x5 + x6 min Do xí nghieääp caààn saûûn xuaáát ñuùùng 2.000 quaààn neânâ caùùc xj phaûûi thoûûa maõn õ 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 Töông töïï cho ñieààu kieään veàà saûûn xuaáát aùùo, ta coùù 35x1 + 55x2 + 70x3 + 90x4 + 100x6 1000 Dó nhieân ta phaâ ûûi coùù xj (j = 1, 2, ..., 6) khoâng aâmâ â Vaääy moâ hâ ình baøøi toaùùn ñöôïïc phaùùt bieååu nhö sau: Tìm caùùc bieáán xj (j = 1, 2, ..., 6) sao cho f(x)= xj min, thoûûa caùùc ñieààu kieään 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 35x1 + 55x2 + 70x3 + 90x4 + 100x6 1000 xj 0, (j = 1, 2, ..., 6). MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT Ví duïï 1.3. BAØØI TOAÙÙN XAÙÙC ÑÒNH KHAÅÅU PHAÀÀN Ñeåå nuoâi moâ äät loaïïi gia suùùc coùù hieääu quaûû, moãi ngaã øøy caààn phaûûi coùù khoáái löôïïng toáái thieååu caùùc chaáát protit, glucit, khoaùùng töông öùùng laøø 90 gram, 130 gram, 10 gram. Tyûû leää (%) theo khoáái löôïïng caùùc chaáát treân â coùù trong caùùc loaïïi thöùùc aên A, B, C nhê ö sau: Giaùù 1 kg thöùùc aên A, B, C tê öông öùùng laøø 3.000 ñoààng, 4.000 ñoààng, 5.000 ñoààng. Haõy laõ ääp moâ hâ ình baøøi toaùùn xaùùc ñònh khoáái löôïïng thöùùc aên caê ààn thieáát sao cho chi phí nuoâi gia suâ ùùc laøø thaááp nhaáát? MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT 32030C 14020B 23010A KhoaùùngGlucitProtit Chaáát dinh döôõng (%)õThöùùc aênê ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Goïïi xj (j = 1, 2, 3) laøø soáá gram thöùùc aên A, B, C caê ààn mua moãi ngaã øøy. Toåång chi phí duøøng ñeåå mua thöùùc aên (caê ààn laøøm cöïïc tieååu) laøø f(x) = 3x1 + 4x2 + 5x3 min (ñoààng) Do caùùc tyûû leää caùùc chaáát protit, glucit vaøø khoaùùng coùù trong thöùùc aên Aê neân caâ ùùc xj phaûûi thoûûa maõn õ 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ùù 0,3x1+0,4x2+0,2x3 130 vaøø 0,02x1+0,01x2+0,03x3 10 Vaääy moâ hâ ình baøøi toaùùn ñöôïïc phaùùt bieååu nhö sau: Tìm caùùc bieáán xj (j = 1, 2, 3) sao cho f(x) = 3x1 + 4x2 + 5x3 min, thoûûa caùùc ñieààu kieään 0,1x1 + 0,2x2 + 0,3x3 90 0,3x1 + 0,4x2 + 0,2x3 130 0,02x1 + 0,01x2 + 0,03x3 10 xj 0, (j = 1, 2, 3). MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT Ví duïï 1.4. BAØØI TOAÙÙN VAÄÄN TAÛÛI Caààn vaään chuyeåån xi maêng tê öøø 3 kho K1, K2, K3 ñeáán 4 coâng trâ öôøøng xaây dâ öïïng T1, T2, T3, T4. Cho bieáát löôïïng xi maêng coê ùù ôûû moãi kho, lã öôïïng xi maêng caê ààn ôûû moãiã coâng trâ öôøøng vaøø cöôùùc phí vaään chuyeåån (ngaøøn ñoààng/ taáán) töøø moãi kho ã ñeáán coâng trâ öôøøng nhö sau: Laääp moâ hâ ình baøøi toaùùn vaään chuyeåån sao cho caùùc kho phaùùt heáát xi maêng coê ùù, coâng trâ öôøøng nhaään ñuûû xi maêng caê ààn vaøø chi phí vaään chuyeåån thaááp nhaáát? MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT 35 15 25 T4: 140 t 403045K3: 180 taáán 302515K2: 200 taáán 221820K1: 170 taáán T3: 120 tT2: 160 tT1: 130 tCoâng trâ öôøøngKho Goïïi xij (i = 1, 2, 3, j = 1, 2, 3, 4) laøø löôïïng xi maêng ê caààn vaään chuyeåån töøø kho Ki ñeáán coâng trâ öôøøng Tj. Toåång chi phí vaään chuyeåån (caààn laøøm cöïïc tieååu) laøø f(x) = 20x11 + 18x12 + 22x13 + 25x14 15x21 + 25x22 + 30x23 + 15x24 45x31 + 30x32 + 40x33 + 35x34 min Ñieààu kieään cuûûa caùùc kho x11 + x12 + x13 + x14 = 170 x21 + x22 + x23 + x24 = 200 x31 + x32 + x33 + x34 = 180 Ñieààu kieään cuûûa caùùc coâng trâ öôøøng x11 + x21 + x31 = 130 x12 + x22 + x32 = 160 x13 + x23 + x33 = 120 x14 + x24 + x34 = 140 xij 0, i = 1, 2, 3, j = 1, 2, 3, 4. MOÄÄT VAØØI VÍ DUÏÏ VEÀÀ BAØØI TOAÙÙN QHTT 2.1. DAÏÏNG TOÅÅNG QUAÙÙT Tìm x = (x1, x2,..., xn) sao cho: (2.1) goïïi laøø haøøm muïïc tieâuâ . (2.2) goïïi laøø heää raøøng buoääc. (2.3) goïïi laøø raøøng buoääc veàà daááu cuûûa aåån soáá. Ví duïï 1.1, Ví duïï 1.2 vaøø Ví duïï 1.3 laøø caùùc baøøi toaùùn QHTT coùù daïïng toåång quaùùt. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 1 ( ) min ( max) (2.1) n j j j f x c x hay 1 1, 2.2 0, 0, 2.3 n ij j i j j k a x b i m x x j k n Moäät vectô x = (x1, x2,..., xn) thoûûa maõn õ ñieààu kieään (2) vaøø (3) ñöôïïc goïïi laøø moäät phöông aùùn (P.A) cuûûa baøøi toaùùn quy hoaïïch tuyeáán tính (QHTT). Taääp caùùc P.A cuûûa baøøi toaùùn QHTT ñöôïïc goïïi laøø mieààn raøøng buoääc. Kyùù hieääu laøø D. Moäät phöông aùùn toáái öu, ñöôïïc kyùù hieääu laøø Xopt (optimality), neááu vectô X laøø laøø moäät P.A vaøø X thoûûa maõn (2.1) hay haõ øøm muïïc tieâu (2.1) bò chaâ ëën. Baøøi toaùùn QHTT ñöôïïc goïïi laøø giaûûi ñöôïïc hay coùù lôøøi giaûûi neááu noùù coùù ít nhaáát moäät PA.T.Ö. Baøøi toaùùn QHTT khoâng giaâ ûûi ñöôïïc neááu D = hay noùù coùù P.A nhöng khoâng coâ ùù PA.T.Ö. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 2.2. DAÏÏNG CHÍNH TAÉÉC Tìm x = (x1, x2,..., xn) sao cho: Nhaään xeùùt: Heää raøøng buoääc cuûûa baøøi toaùùn daïïng chính taééc ñeààu laøø caùùc ñaúúng thöùùc vaøø moïïi bieáán cuûûa baøøi toaùùn ñeààu khoâng aâm. â â Ví duïï 1.4 BAØØI TOAÙÙN VAÄÄN TAÛÛI coùù daïïng chính taééc. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 1 ( ) min ( max) n j j j f x c x hay 1 1, 0, 1, n ij j i j j a x b i m x j n ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 2.3. DAÏÏNG CHUAÅÅN Tìm x = (x1, x2,..., xn) sao cho: Nhaään xeùùt: Baøøi toaùùn daïïng chuaåån laøø baøøi toaùùn ôûû daïïng chính taééc vôùùi heää raøøng buoääc chöùùa ma traään con Im laøø ma traään ñôn vò caááp m. Trong ñoùù caùùc xi (i = 1, 2,..., m) ñöôïïc goïïi laøø aåån cô baûûn (A.C.B), coøøn caùùc aåån xi,m+k, (k = 0, 1,..., n – m) ñöôïïc goïïi laøø aåån khoâng cô baâ ûûn. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 1 ( ) min ( max) n j j j f x c x hay , 1 , 1, 0 1, 0 n m i i m k m k i k j i x a x b i m x j n b 2.4. CHUYEÅÅN ÑOÅÅI DAÏÏNG BAØØI TOAÙÙN QHTT Khi xeùùt baøøi toaùùn QHTT, ngöôøøi ta thöôøøng söûû duïïng daïïng chính taééc, coùù theåå ñöa baøøi toaùùn veàà daïïng chính taééc baèèng caùùc bieáán ñoååi sau: 1) Neááu raøøng buoääc thöùù i coùù daïïng aijxj bi thì theâm â vaøøo moäät aåån phuïï xn+1 0, sao cho aijxj + xn+1 = bi. 2) Neááu raøøng buoääc thöùù i coùù daïïng aijxj bi thì theâm â vaøøo moäät aåån phuïï xn+1 0, sao cho aijxj – xn+1 = bi. 3) Neááu bieáán xj 0 thì ñöôïïc thay baèèng x/j = – xj 0. 4) Neááu bieáán xj khoâng raâ øøng buoääc veàà daááu thì thay xj baèèng hai aåån phuïï x/j vaøø x//j sao cho xj = x/j – x//j, vôùùi x/j 0, x//j 0. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT Ñeåå baøøi toaùùn goïïn hôn, chuùùng ta duøøng caùùc kyùù hieääu Trong ñoùù A laøø ma traään m n goààm caùùc heää soáá ôûû veáá traùùi cuûûa heää raøøng buoääc; Aj laøø vectô coäät thöùù j cuûûa ma traään A; b laøø vectô heää soáá ôûû veáá phaûûi cuûûa heää raøøng buoääc; c laøø vectô heää soáá ôûû haøøm muïïc tieâu; x laâ øø vectô aåån soáá; 0 laøø vectô khoâng.â Khi ñoùù baøøi toaùùn QHTT ôûû daïïng chính taééc coùù daïïng f(x) = cTx min (hay max) Ax = b, x 0 CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 11 12 1 21 22 2 1 2 , n n m m mn a a a a a a A a a a 1 2 , m b b b b 1 2 , n c c c c 1 2 , n x x x x 0 0 0 0 1 2 , j j j mj a a A a Ví duïï 1.5. Ñöa baøøi toaùùn QHTT sau ñaây veâ àà daïïng chính taééc vaøø vieáát baøøi toaùùn chính taééc döôùùi daïïng ma traään Theâm 2 aâ åån phuïï x4, x5 0 vaøøo raøøng buoääc thöùù nhaáát vaøø raøøng buoääc thöùù ba. Thay x/3 = –x3 0 Thay x2 = x/2 –x//2 0, vôùùi x/2, x//2 0 CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 3 2 min 3 2 7 2 4 12 4 3 8 10 0 0 f x x x x x x x x x x x x x x x Baøøi toaùùn QHTT coùù daïïng chính taééc nhö sau Baøøi toaùùn QHTT döôùùi daïïng ma traään nhö sau f(x) = (1, 3, – 2, 0, 0, 0)T(x1, x/2, x//2, x/3, x4, x5) min (x1, x/2, x//2, x/3, x4, x5) (0, 0, 0, 0, 0, 0) CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 1 2 2 3 1 2 2 3 4 1 2 2 3 1 2 2 3 5 1 2 2 3 4 5 ( ) 3 3 2 min 3 2 7 2 4 4 12 4 3 3 8 10 0, 0, 0, 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x x x x x x 1 2 2 3 4 5 3 1 1 2 1 0 7 2 4 4 1 0 0 12 4 3 3 8 0 1 10 x x x x x x Ví duïï 1.6. Cho baøøi toaùùn QHTT sau: Ta coùù ma traään heää soáá cuûûa heää raøøng buoääc: chöùùa I3 neân baâ øøi toaùùn quy hoaïïch tuyeáán tính treân coâ ùù daïïng chuaåån. CAÙÙC DAÏÏNG CUÛÛA BAØØI TOAÙÙN QHTT 2 5 1 2 5 2 3 5 2 4 5 ( ) min 2 1 3 3 2 2 0 1,5j f x x x x x x x x x x x x x j 11020 10130 20011 A ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Moäät phöông aùùn x* = (x1*, x2*,..., xn*) cuûûa baøøi toaùùn QHTT daïïng toåång quaùùt laøø phöông aùùn cöïïc bieânâ (P.A.C.B) neááu x* = (x1*, x2*,..., xn*) thoûûa maõn chaõ ëët n raøøng buoääc ñoääc laääp tuyeáán tính. Töùùc laøø: Trong ñoùù A laøø ma traään con caááp n cuûûa hpt (*). Moäät P.A.C.B khoâng suy bieâ áán laøø moäät P.A.C.B thoûûa maõn õ ñuùùng n raøøng buoääc chaëët. Moäät P.A.C.B suy bieáán laøø moäät P.A.C.B thoûûa maõn õ hôn n raøøng buoääc chaëët. P.A.C.B coøøn ñöôïïc goïïi laøø phöông aùùn cô baûûn. ÑÒNH NGHÓA PHÖÔNG AÙÙN CÖÏÏC BIEÂN *X la P.A.C.B j n * ij i j=1 * j a x = b , i=1,k,k m * k+l n,det A 0 x =0, j=1,l,l n Ví duïï 1.7. Cho baøøi toaùùn QHTT Caùùc vectô naøøo sau ñaâyâ laøø phöông aùùn cöïïc bieân?â ÑÒNH NGHÓA PHÖÔNG AÙÙN CÖÏÏC BIEÂN 1 2 3 1 2 3 1 1 2 3 1 2 3 2 3 ( ) 50 16 23 min 5 3 4 2 2 3 1 6 2 4 0 0 f x x x x x x x x x x x x x x x x 0, 1, 3X 3, 0, 0Y 23 62, , 5 5 Z ÑÒNH LYÙÙ 1. (TÍNH CHAÁÁT ÑAËËC TRÖNG CUÛÛA P.A.C.B) Moäät phöông aùùn X* = (x1*, x2*,…, xn*) cuûûa baøøi toaùùn QHTT daïïng chính taééc laøø phöông aùùn cöïïc bieân neâ ááu vaøø chæ neááu heää vectô coäät Aj öùùng vôùùi thaøønh phaààn xj* > 0 laøø ñoääc laääp tuyeáán tính. Ví duïï 1.8. Cho baøøi toaùùn QHTT Caùùc vectô naøøo sau ñaây X = (2, 2, 0), Y = (0, 0, 4), â Z = (1, 1, 2), laøø P.A.C.B cuûûa baøøi toaùùn. CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT 1 2 3 1 2 3 1 2 ( ) 2 3 min 4 0 0, 1,3j f x x x x x x x x x x j X, Y, Z thoûûa caùùc raøøng buoääc neân chuâ ùùng laøø P.A. Maëët khaùùc ta coùù Vôùùi X = (2, 2, 0), neân X laâ øø P.A.C.B. Vôùùi Y = (0, 0, 4), heää chæ goààm moäät vectô A3 neân â Y cuõng laõ øø P.A.C.B. Vôùùi Z=(1, 1, 2), ta thaááy heää {A1, A2, A3} phuïï thuoääc tuyeáán tính vì A1+A2–2A3=0 neân Z khoâng laâ â øø P.A.C.B. HEÄÄ QUAÛÛ 1. (tính höõu haõ ïïn cuûûa P.A.C.B). Soáùáù phöông aùùn cöïïc bieân cuâ ûûa baøøi toaùùn QHTT daïïng chính taééc laøø höõu haõ ïïn. CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT 1 1 1 A 2 1 1 A 3 1 0 A 1 1 det 2 1 1 HEÄÄ QUAÛÛ 2. Soáùáù thaøønh phaààn döông trong moãi ã phöông aùùn cöïïc bieân cuâ ûûa baøøi toaùùn quy hoaïïch tuyeáán tính daïïng chính taééc toáái ña baèèng m (m laøø soáá doøøng cuûûa ma taään A). ÑÒNH LYÙÙ 2. (SÖÏÏ TOÀÀN TAÏÏI CUÛÛA PHÖÔNG AÙÙN TOÁÁI ÖU) Neááu baøøi toaùùn quy hoaïïch tuyeáán tính coùù phöông aùùn vaøø haøøm muïïc tieâu bò chaâ ëën döôùùi (ñoáái vôùùi f(x) min) hoaëëc haøøm muïïc tieâu bò chaâ ëën treân â (ñoáái vôùùi f(x) max) treân taâ ääp caùùc phöông aùùn thì baøøi toaùùn coùù phöông aùùn toáái öu. ÑÒNH LYÙÙ 3. (SÖÏÏ TOÀÀN TAÏÏI CUÛÛA P.A.C.B. TOÁÁI ÖU) Neááu baøøi toaùùn QHTT daïïng chính taééc coùù P.A.T.Ö thì baøøi toaùùn coùù P.A.C.B toáái öu (P.A.C.B.T.Ö). CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT ÑÒNH LYÙÙ 4. (SÖÏÏ TOÀÀN TAÏÏI NHIEÀÀU P.A.C.B.T.Ö) Neááu baøøi toaùùn QHTT coùù P.A.T.Ö laøø X0 vaøø X1, X2 hai phöông aùùn khaùùc nhau cuûûa baøøi toaùùn thoaûû X0 = X1 + (1– )X2, 0 1 thì X1, X2 laøø P.A.T.Ö. NHAÄÄN XEÙÙT 1. Ta coùù theåå tìm P.A.T.Ö cuûûa baøøi toaùùn QHTT trong soáá caùùc P.A.C.B cuûûa baøøi toaùùn vaøø coùù theåå xaùùc ñònh ngay P.A.C.B cuûûa baøøi toaùùn daïïng chuaåån baèèng caùùch cho caùùc aåån khoâng cô baâ ûûn baèèng khoâng (xem â Ví duïï 1.9). 2. Trong baøøi toaùùn QHTT daïïng chính taééc. Neááu haïïng cuûûa ma traään heää soáá A laøø m thì P.A.C.B ñöôïïc goïïi laøø khoâng suy bieâ áán neááu noùù coùù ñuùùng m thaøønh phaààn döông. Neááu P.A.C.B coùù ít hôn m thaøønh phaààn döông thì ñöôïïc goïïi laøø P.A.C.B suy bieáán (xem Ví duïï 1.10). CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oâ g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví duïï 1.9 . Vôùùi baøøi toaùùn quy hoaïïch tuyeáán tính Ta coùù phöông aùùn X = (1, 0, 3, 2, 0) laøø phöông aùùn cöïïc bieân cuâ ûûa baøøi toaùùn vì caùùc aåån x1, x3, x4 laøø caùùc aåån cô baûûn cuûûa baøøi toaùùn daïïng chuaåån. CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT 5,10 22 33 12 min)( 542 532 521 52 jx xxx xxx xxx xxxf j Ví duïï 1.10 . Vôùùi baøøi toaùùn quy hoaïïch tuyeáán tính Kieååm tra vectô X = (11, 3, 0, 0) coùù phaûûi laøø P.A.C.B? Kieååm tra tröïïc tieááp, ta coùù X laøø P.A cuûûa baøøi toaùùn. Haïïng cuûûa ma traään heää soáá cuûûa heää raøøng buoääc tuyeáán tính baèèng 3 vaøø X coùù 2 thaøønh phaààn döông laøø x1 =11, x2 = 3 neân X laâ øø P.A.C.B suy bieáán. CAÙÙC TÍNH CHAÁÁT CUÛÛA BAØØI TOAÙÙN QHTT 1 2 3 4 1 2 4 1 2 3 4 1 2 3 4 ( ) 3 4 2 2 min 2 2 28 5 3 2 26 2 2 2 16 0 1,4j f x x x x x x x x x x x x x x x x x j Ths. Nguyeãn Coâng Trã â í Copyright 2001 4.1. PHÖÔNG PHAÙÙP HÌNH HOÏÏC (Xem) 4.2. PHÖÔNG PHAÙÙP ÑÔN HÌNH (Xem) 4.3.PHÖÔNG PHAÙÙP ÑÔN HÌNH MÔÛÛ ROÄÄNG (BAØØI TOAÙÙN M) (Xem) CAÙÙC PHÖÔNG PHAÙÙP GIAÛÛI BAØØI TOAÙÙN QUY HOAÏÏCH TUYEÁÁN TÍNH ax+by=c PHÖÔNG PHAÙÙP HÌNH HOÏÏC ax+by>c ax+by<c O =m (ñöôøøng möùùc) a b taêngê giaûûm N(a,b) Xeùùt baøøi toaùùn QHTT coùù 2 bieáán. Ví duïï 1.11. Moäät coâng ty coâ ùù 2 phaân xâ öôûûng: PX1 vaøø PX2 cuøøng saûûn xuaáát 2 loaïïi saûûn phaååm A vaøø B. Naêng ê suaáát vaøø chi phí saûûn xuaáát cuûûa moãi PX trong 1 giôã øø: Ñôn ñaëët haøøng: ít nhaáát 5.000 SpA, 3.000 SpB. Haõy phaân phoõ â áái thôøøi gian hoaïït ñoääng cuûûa 2 phaân â xöôûûng sao cho thoaûû yeâu caâ ààu ñôn ñaëët haøøng vaøø chi phí saûûn xuaáát thaááp nhaáát. 10,6Chi phí (trieääu ñoààng/ giôøø) 200100Saûûn phaååm B 250250Saûûn phaååm A PX2PX1Phaân xâ öôûûng Naêng suaê áát PHÖÔNG PHAÙÙP HÌNH HOÏÏC Goïïi x1, x2 laààn löôïït laøø soáá giôøø hoaïït ñoääng cuûûa phaân â xöôûûng thöùù nhaáát vaøø phaân xâ öôûûng thöùù hai. Ta coùù moâ hâ ình baøøi toaùùn Duøøng phöông phaùùp hình hoïïc ñeåå giaûûi baøøi toaùùn treân nhâ ö sau PHÖÔNG PHAÙÙP HÌNH HOÏÏC 1 2 1 2 1 2 1 2 0,6 min 250 250 5000 100 200 3000 0 0 f x x x x x x x x x ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 10 20 30 10 15 20 250x1+250x2=5000 100x1+200x2=3000 0,6x1+x2=m taêngê giaûûm Mieààn raøøng buoääc DA1(0,20) A2(30,0) A3 (10,10) PHÖÔNG PHAÙÙP HÌNH HOÏÏC Vaääy P.A.T.Ö: xopt(10,10) vaøø f(xopt)=16 trieääu ñoààng. Ví duïï 1.12. Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính baèèng phöông phaùùp hình hoïïc 1 2 1 2 1 2 1 2 2 min 2 2 2 0 0 f x x x x x x x x x PHÖÔNG PHAÙÙP HÌNH HOÏÏC Haøøm muïïc tieâu khoâng bò chaâ â ëën. Baøøi toaùùn khoâng â coùù phöông aùùn toáái öu. -2 2 2 x1-x2= -2 taêngê giaûûm Mieààn raøøng buoääc D -1 -x1+2x2= -2 A1(0,2) A2(2,0)O -1 -2x1+x2= m PHÖÔNG PHAÙÙP HÌNH HOÏÏC Ví duïï 13: giaûûi baøøi toaùùn Ñöa baøøi toaùùn veàà daïïng chính taééc 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 3 2 min 2 4 3 10 3 4 5 2 2 8 0 1,3j f x x x x x x x x x x x x x x j CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 1 2 3 1 2 3 1 1 2 3 2 1 2 3 3 ( ) 3 2 min 2 4 3 10 3 4 5 2 2 8 0, 1,3, 0, 1,3j i f x x x x x x x w x x x w x x x w x j w i Ta coùù P.A.C.B laøø x = (0, 0, 0, 10, 5, 8) Baøøi toaùùn töông ñöông coùù P.A.C.B laøø x = (0, 0, 0, 10, 5, 8) vaøø f(x) = 0. Nhaään xeùùt: coùù theåå ñoååi P.A baèèng caùùch taêng xê 1 baèèng moäät giaùù trò döông vaøø giöûû x2 = x3 = 0 thoûûa ñieààu kieään wi 0. CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 ( ) 3 2 min 10 2 4 3 5 3 4 8 2 2 0 1,3, 0, 1,3j i f x x x x w x x x w x x x w x x x x j w i Ta coùù Choïïn x1 = 5/3, ta ñöôïïc P.A môùùi laøø x1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3. Vaøø f(x) = - 5. Baøøi toaùùn töông ñöông: taïïi raøøng buoääc thöùù hai tính x1 theo caùùc bieáán coøøn laïïi, roàài theáá giaùù trò x1 vöøøa tính ñöôïïc vaøøo caùùc raøøng buoääc vaøø haøøm muïïc tieâu.â CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 1 1 1 2 1 1 1 3 1 1 510 2 0 5 55 3 0 3 3 8 0 8 xw x w x x x w x x (Choïn doøng 2) ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oâ g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ta coùù keáát quaûû Nhaään xeùùt: coùù theåå ñoååi P.A baèèng caùùch taêng xê 2 baèèng moäät giaùù trò döông vaøø giöûû x3 = w2 = 0 thoûûa ñieààu kieään wi 0. CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 2 2 3 1 2 2 3 1 2 2 3 3 2 2 3 ( ) 5 3 min 20 2 10 1 3 3 3 3 5 1 1 4 3 3 3 3 19 1 5 2 3 3 3 3 0 1,3, 0, 1,3j i f x w x x w w x x x w x x w w x x x j w i Ta coùù Choïïn x2 = 2, ta ñöôïïc P.A môùùi laøø x1 = 1, x3 = w1 = w2 = 0, w3 = 3 vaøø f(x) = - 7. Baøøi toaùùn töông ñöông: taïïi raøøng buoääc thöùù nhaáát tính x2 theo caùùc bieáán coøøn laïïi, roàài theáá giaùù trò x2 vöøøa tính ñöôïïc vaøøo caùùc raøøng buoääc vaøø haøøm muïïc tieâu.â CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 1 1 2 1 2 2 2 2 3 2 20 10 0 3 3 2 5 1 0 5 2 3 3 1919 5 0 53 3 w x x x x x x xw x (Choïn doøng 1) Ta coùù keáát quaûû Baøøi toaùùn coùù P.A.T.U laøø xopt = (1, 2, 0) vaøø f(xopt) = - 7 CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 1 2 3 2 1 2 3 1 1 2 3 3 1 3 3 4 31( ) 7 min 10 5 10 3 1 12 10 5 10 1 6 391 10 15 30 1 23 2 3 0 1,3, 0, 1,3j i f x w w x x w w x x w w x w w x x j w i 1 , 1 ( ) min max 1 2 0 1, 0 3 n j j j n m i i m k m k i k j i f x c x hay x a x b x j n b CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH 0 0 1 2 1 ( , , ; ,.0 ,0) ( ) m m i i i x b b b f x c b 1 2, ( , , , )nx D x x x x 1 1 1 ( ) n m n m j j i i m k m k j i k f x c x c x c x Döïïa treân cô sôâ ûû baøøi toaùùn coùù daïïng chuaåån Daááu hieääu toáái öu cuûûa baøøi toaùùn Phöông aùùn cöïïc bieân â ñaààu tieân laâ øø: Choïïn moäät P.A baáát kyøø cuûûa baøøi toaùùn CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH , 1 2 , n m i i i m k m k k x b a x , 1 1 1 m n m m i i i m k i m k m k i k i f x c x a c c x , 1 m m k i m k i m k i a c c 0 1 n m m k m k k f x f x x 0m k 0 ,f x f x 0m kx 0m k 0 ,f x f x 0m kx 1 m j ij i j i a c c ( )f x Min 0;j j ( )f x Max 0;j j Ñaëët thì Neááu thì vì Neááu thì vì Kyùù hieääu laïïi: (1) Khi thì (2) Khi thì Daááu hieääu baøøi toaùùn khoâng coâ ùù P.A.T.Ö Ñònh lyùù. Vôùùi moäät phöông aùùn cöïïc bieân, neâ ááu toààn taïïi j > 0 maøø aij 0, i thì baøøi toaùùn khoâng coâ ùù P.A.T.Ö. (xem Ví duïï 1.13) CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH C1 C2 … Ci … Cm Cm+1 … Cj … CnHeää soáá Aåån C.B PA CB x1 x2 … xi … xm xm+1 … xj … xm C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n Ci xi bi 0 0 … … … 0 ai,m+1 … aij … ain xm bm 0 0 … … … 1 am,m+1 … amj … amnCm f(x) f(x0) 0 0 … … … 0 m+1 … j … n ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com C1 C2 … Ci … Cm Cm+1 … Cj … CnHeää soáá AÅÅn C.B PA CB x1 x2 … xi … xm xm+1 … xj … xm C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n Ci xi bi 0 0 … … … 0 ai,m+1 … aij … ain xm bm 0 0 … … … 1 am,m+1 … amj … amnCm f(x) f(x0) 0 0 … … … 0 m+1 … j … n Daááu hieääu baøøi toaùùn coùù P.A.C.B. khaùùc toáát hôn Ñònh lyùù. Vôùùi moäät P.A.C.B, neááu j>0, i: aij > 0 thì baøøi toaùùn coùù P.A.C.B khaùùc toáát hôn P.A.C.B ñang xeùùt. CÔ SÔÛÛ PHÖÔNG PHAÙÙP ÑÔN HÌNH BAÛÛNG ÑÔN HÌNH C1 C2 … Ci … Cm Cm+1 … CJ … CnHeä Soá AÅn C.B PA CB x1 x2 … xi … xm xm+1 … xj … xn C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n Ci xi bi 0 0 … … … 0 ai,m+1 … aij … ain xm bm 0 0 … … 1 am,m+1 … amj … amnCm f(x) f(x0) 0 0 … … … 0 m+1 … j … n j 0, j? THUAÄÄT GIAÛÛI ÑÔN HÌNH Sai Ñuùùng Sai Ñuùùng LAÄÄP BAÛÛNG ÑÔN HÌNH XAÙÙC ÑÒNH PHÖÔNG AÙÙN MÔÙÙI Aåån vaøøo: Aåån ra: P.A.T.Ö KEÁÁT THUÙÙC THUAÄÄT GIAÛÛI aij 0, i? BAØØI TOAÙÙN KHOÂNG CO ÙÙ P.A.T.Ö BIEÁÁN ÑOÅÅI BAÛÛNG ÑÔN HÌNH 0j j jMax x 0ij i ia ij bMin x a SOÁÁ BÖÔÙÙC LAËËP LAØØ HÖÕU HAÕ ÏÏN THUAÄÄT GIAÛÛI ÑÔN HÌNH NHAÄÄN XEÙÙT. Daááu hieääu baøøi toaùùn coùù nhieààu P.A.T.Ö. Vôùùi P.A.C.B.T.Ö Xopt tìm ñöôïïc, neááu j = 0, maøø xj khoâng laâ øø P.A.C.B thì baøøi toaùùn coùù P.A.C.B.T.Ö khaùùc X/opt (xem Ví duïï 1.15). Taääp phöông aùùn toáái öu: Tröôøøng hôïïp coùù 2 P.A.C.B.T.Ö Xopt vaøø X/opt Topt = { Xopt + (1 – )X/opt, [0, 1]} Tröôøøng hôïïp coùù 3 P.A.C.B.T.Ö X(1)opt, X(2)opt, X(3)opt Topt = { X(1)opt + X(2)opt + X(3)opt, }, vôùùi , , 0 vaøø + + = 1. 1 2 3 4 5 6 7 1 2 4 6 7 1 3 4 6 7 1 4 5 6 ( ) 6 3 7 6 min 3 2 4 2 9 4 2 3 2 0 1,7j f x x x x x x x x x x x x x x x x x x x x x x x j Ví duïï 1.14. Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính THUAÄÄT GIAÛÛI ÑÔN HÌNH BT khoâng coâ ùù P.A.T.Ö vì 4= 1 > 0 maøø ai4 < 0, i. HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 6x 7x 6 1 1 3 1 7 6 2x 3x 5x 1 1 1 3 9 2 1 2 4 1 0 0 1 1 4 2 2 3 1 f x 14 5 0 0 6 0 7 6 0 0 0 0 0 1 1 1 6x 3x 5x 7 1 1 3 1 1 0 1 0 1 1 3 0 2 1 2 0 30 11 1 3 0 1 0 31 f x 7 2 7 0 1 0 0 13 THUAÄÄT GIAÛÛI ÑÔN HÌNH ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví duïï 1.15. Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính Baøøi toaùùn coùù phöông aùùn toáái öu khaùùc hay khoâng? â Neááu coùù tìm taääp phöông aùùn toáái öu vaøø chæ ra 3 phöông aùùn toáái öu. 1 2 3 4 5 6 1 2 3 4 1 2 3 5 1 3 6 ( ) 5 4 5 2 3 min 2 4 3 152 4 2 3 60 3 36 0 1,6j f x x x x x x x x x x x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 5x 6x 2 1 3 152 60 36 2 4 3 4 2 0 1 3 3 1 0 0 f x 472 12 6 7 0 0 0 0 0 0 01 1 4x 5x 1x 2 1 5 128 0 4 7 3 1 0 2 3 12 0 2 5 3 0 4 31 12 1 0 13 0 130 f x 328 0 6 3 0 0 4 THUAÄÄT GIAÛÛI ÑÔN HÌNH Baøøi toaùùn coùù P.A.T.Ö xopt=(12, 6, 0, 104, 0, 0) vaøø f(xopt)= 292. Baøøi toaùùn coøøn P.A.C.B.T.Ö khaùùc vì 6 = 0, nhöng x6 khoâng phaâ ûûi laøø A.C.B. Ta coùù P.A.C.B.T.Ö thöùù hai baèèng caùùch choïïn aåån x6 laøø aåån ñöa vaøøo. HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 2x 1x 2 4 5 104 0 0 1 1 2 2 6 0 1 5 6 0 2 312 12 1 0 13 0 130 f x 292 0 0 2 0 3 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH Baøøi toaùùn coùù phöông aùùn cöïïc bieân toâ áái öu khaùùc laøø x/opt = (0, 30, 0, 32, 0, 36) vaøø f(x/opt) = 292. Taääp phöông aùùn toáái öu Topt={ xopt + (1 - )x/opt, 0, 1 } HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 2x 6x 2 4 3 32 6 0 3 1 2 0 30 2 1 3 2 0 012 36 3 0 1 0 10 f x 292 0 0 2 0 3 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH Vôùùi taääp phöông aùùn toáái öu, ta coùù : xopt + (1 - )x/opt = (12, 6, 0, 104, 0, 0) + (1- )(0, 30, 0, 32, 0, 36) = (12 , 30–24 , 0, 32 + 72 , 0, 36 - 36 ) 3 phöông aùùn toáái öu laøø Vôùùi = 0, ta coùù P.A.T.Ö: x/opt = (0, 30, 0, 32, 0, 36) vaøø f(x/opt) = 292. Vôùùi = 1, ta coùù P.A.T.Ö: xopt = (12, 6, 0, 104, 0, 0) vaøø f(x/opt) = 292. Vôùùi = ½, ta coùù P.A.T.Ö: Zopt = (6, 18, 0, 68, 0, 18) vaøø f(zopt) = 292. THUAÄÄT GIAÛÛI ÑÔN HÌNH NHAÄÄN XEÙÙT. Neááu baøøi toaùùn coùù haøøm muïïc tieâuâ Coùù hai caùùch giaûûi: Giaûûi tröïïc tieááp baøøi toaùùn (xem Ví duïï 1.16), vôùùi: Tieâu chuaâ åån toáái öu laøø AÅÅn vaøøo laøø AÅÅn ra laøø Chuyeåån haøøm muïïc tieâu cuâ ûûa baøøi toaùùn veàà min 1 ( ) n j j j f x c x Max ( ) ( )g x f x Min 0,j j 0j jMin THUAÄÄT GIAÛÛI ÑÔN HÌNH 0ij i a ij bMin a ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví duïï 1.16. Giaûûi baøøi toaùùn quy hoaïïch tuyeáán tính Baøøi toaùùn coùù phöông aùùn toáái öu khaùùc hay khoâng? â Neááu coùù, haõy chõ æ ra phöông aùùn toáái öu khaùùc. 1 2 3 4 1 2 3 4 2 3 4 3 4 ( ) 2 max 2 2 7 3 2 3 2 5 0 1,4j f x x x x x x x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH Ñöa baøøi toaùùn veàà daïïng chính taééc baèèng caùùch theâm aâ åån phuïï x5 0 vaøøo raøøng buoääc thöùù hai vaøø aåån phuïï x6 0 vaøøo raøøng buoääc thöùù ba. Ta coùù baøøi toaùùn ôûû daïïng chuaåån Laääp baûûng ñôn hình 1 2 3 4 1 2 3 4 2 3 4 5 3 4 6 ( ) 2 max 2 2 7 3 2 3 2 5 0 1,6j f x x x x x x x x x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 6x 2 1 1 1 0 0 1x 5x 6x 2 0 0 2 2 5 1 0 0 1 1 0 1 2 7 3 3 2 f x 4 0 1 5 1 0 0 0 0 0 01 1 3x 5x 6x 1 0 0 1 12 12 1 12 0 0 9 7 2 5 2 0 12 01 8 3 2 3 2 0 12 10 f x 1 5 2 3 2 0 32 0 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH Vì caùùc j 0, j neân bâ aøøi toaùùn coùù P.A.T.Ö laøø Xopt = (0, 0, 9, 16) vaøø f(Xopt) = 25. Baøøi toaùùn treân khoâng coâ â øøn phöông aùùn toáái öu naøøo khaùùc vì khoâng coâ ùù j = 0 naøøo vôùùi xj laøø aåån khoâng â cô baûûn. HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 6x 2 1 1 1 0 0 3x 5x 4x 1 0 1 9 2 2 1 0 0 1 17 5 4 0 0 11 16 3 3 0 1 20 f x 25 7 6 0 0 0 3 THUAÄÄT GIAÛÛI ÑÔN HÌNH Xuaáát phaùùt töøø baøøi toaùùn daïïng chính taééc Khoâng laâ øøm maáát tính toåång quaùùt cuûûa baøøi toaùùn, ta giaûû söûû caùùc bi 0 vaøø ma traään heää soáá cuûûa heää raøøng buoääc khoâng châ öùùa vectô (coäät) ñôn vò naøøo. Coääng vaøøo moãi raã øøng buoääc vôùùi moäät aåån giaûû töông öùùng xi(g) 0 thì ta ñöôïïc baøøi toaùùn coùù daïïng: CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG 1 1 ( ) , 1, 0 1, 0 n j j j n ij j i j j i f x c x Min a x b i m I x j n b Baøøi toaùùn (I) ñöôïïc goïïi laøø baøøi toaùùn goáác, baøøi toaùùn (II) goïïi laøø baøøi toaùùn môûû roääng hay baøøi toaùùn M. Moäät phöông aùùn cuûûa baøøi toaùùn M coùù daïïng trong ñoùù xj goààm n aåån thaäät vaøø xi(g) goààm m aåån giaûû. CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG 1 1 1 ( ) , 1, 0, 1, ; 0, 1, , 0 vo â cuøng lôùn. n m g j j i j i n g ij j i i j g j i f x c x M x Min a x x b i m II x j n x i m M , gj ix x x ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Trong ñoùù caùùc xn+i (i = 1, 2, ..., m) laøø caùùc aåån giaûû. C1 C2 … Cm Cm+1 … Cj … CnHeä Soá AÅn C.B PA CB x1 x2 … xm xm+1 … xj … xn M xn+1 b1 a11 a12 … a1m a1,m+1 … a1j … a1,n M x n+2 b2 a21 a22 … a2m a2,m+1 … a2j … a2,n M x n+i bi ai1 ai2 … aim ai,m+1 … aij … ai,n xn+m bm am1 am2 … amm am,m+1 … amj … am,nM f(x) f(x0) 1 2 … m m+1 … j … n BAÛÛNG ÑÔN HÌNH MÔÛÛ ROÄÄNG NHAÄÄN XEÙÙT. Khi thuaäät giaûûi cuûûa baøøi toaùùn M keáát thuùùc thì coùù hai tröôøøng hôïïp sau ñaây coâ ùù theåå xaûûy ra: [1] Neááu baøøi toaùùn M (Baøøi toaùùn II) khoâng coâ ùù phöông aùùn toáái öu thì baøøi toaùùn goáác (Baøøi toaùùn I) cuõng khoâng coõ â ùù phöông aùùn toáái öu. [2] Neááu baøøi toaùùn M (Baøøi toaùùn II) coùù phöông aùùn toáá i öu thì coùù 3 tröôøøng hôïïp xaûûy ra sau ñaây:â a) Trong heää A.C.B khoâng châ öùùa aåån giaûû naøøo thì P.A.T.Ö cuûûa baøøi toaùùn M cuõng chõ ính laøø P.A.T.Ö cuûûa baøøi toaùùn goáác (xem Ví duïï 1.17). CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG b) Neááu trong heää aåån cô baûûn cuûûa baøøi toaùùn M coùù chöùùa aåån giaûû nhöng giaùù trò cuûûa chuùùng ñeààu baèèng khoâng thâ ì P.A.T.Ö cuûûa baøøi toaùùn goáác laøø P.A.T.Ö. cuûûa baøøi toaùùn M loaïïi boûû caùùc aåån giaûû baèèng khoâng â (xem Ví duïï 1.18). c) Neááu trong heää aåån cô baûûn cuûûa baøøi toaùùn M coùù moäät aåån giaûû maøø giaùù trò cuûûa chuùùng khaùùc khoâng thâ ì baøøi toaùùn goáác khoâng coâ ùù P.A.T.Ö. Chuùù yùù. Neááu haøøm muïïc tieâu laâ øø f(x) Max thì heää soáá caùùc aåån giaûû trong haøøm muïïc tieâu cuâ ûûa baøøi toaùùn M laøø (– M), vôùùi M > 0 voâ cuâ øøng lôùùn (xem Ví duïï 1.19). CÔ SÔÛÛ THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG Ñuùùng Sai aij 0? Sai Ñuùùng Khoângâ CoùùÑuùùng j 0? THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG Sai LAÄÄP BAÛÛNG ÑÔN HÌNH Xaùùc ñònh phöông aùùn môùùi Aåån vaøøo: Aåån ra: COÙÙ P.A.T.Ö ÑÖA BAØØI TOAÙÙN VEÀÀ DAÏÏNG CHUAÅÅN KHOÂNG COÙÙ P.A.T.Ö KEÁÁT THUÙÙC THUAÄÄT GIAÛÛI COÙÙ P.A.T.Ö BIEÁÁN ÑOÅÅI BAÛÛNG ÑÔN HÌNH ?gix 0? g ix KHOÂNG COÙÙ P.A.T.Ö 0j jMax 0ij i a ij bMin a SOÁÁ BÖÔÙÙC LAËËP LAØØ HÖÕU HAÕ ÏÏN Ví duïï 1.17. (tröôøøng hôïïp a). Giaûûi baøøi toaùùn QHTT Nhaân (⠖ 1) vaøøo raøøng buoääc thöùù nhaáát, baøøi toaùùn coùù daïïng chính taééc nhö sau 1 2 3 1 2 3 1 2 3 ( ) 8 6 2 min 4 4 3 18 4 3 4 16 0 1,3j f x x x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG 1 2 3 1 2 3 1 2 3 ( ) 8 6 2 min 4 4 3 18 4 3 4 16 0 1,3j f x x x x x x x x x x x j Ñöa baøøi toaùùn veàà daïïng chuaåån: Theâm hai aâ åån giaûû x4 0 vaøø x5 0 vaøøo laààn löôïït vaøøo raøøng buoääc thöùù nhaáát vaøø thöùù hai cuûûa baøøi toaùùn Baøøi toaùùn coùù daïïng chuaåån nhö sau: Ta coùù baûûng ñôn hình môûû roääng 1 2 3 4 5 1 2 3 4 1 2 3 5 ( ) 8 6 2 ( ) 4 4 3 18 4 3 4 16 0 1,5 M 0 vo â cuøng lôùn.j f x x x x M x x Min x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Baøøi toaùùn coùù P.A.T.Ö Xopt=(5/2, 2, 0), f(Xopt)= –8. HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 8 6 2 4x 5x M M 18 16 4 4 4 3 3 4 f x 34M 8 8M 7 6M 2M 4x 1x M 8 2 0 1 7 4 1 3 4 1 f x 2 32M 0 12M 7 10M THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG 2x 1x 6 8 2 5 2 0 1 1 0 7 25 4 f x 8 0 0 94 Ví duïï 1.18. (tröôøøng hôïïp b). Giaûûi baøøi toaùùn QHTT Theâm aâ åån phuïï x4 0 vaøøo raøøng buoääc thöùù nhaáát 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 6 3 min 2 5 10 4 3 2 16 2 4 8 0 1,3j f x x x x x x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG 1 2 3 1 2 3 4 1 2 3 1 2 3 ( ) 6 3 min 2 5 10 4 3 2 16 2 4 8 0 1,4j f x x x x x x x x x x x x x x x j Theâm hai aâ åån giaûû x5 0, x6 0 laààn löôïït vaøøo raøøng buoääc thöùù hai vaøø raøøng buoääc thöùù ba. Ta coùù baøøi toaùùn daïïng chuaåån nhö sau Ta coùù baûûng ñôn hình môûû roääng 1 2 3 5 6 1 2 3 4 1 2 3 5 1 2 3 6 ( ) 6 3 ( ) min 2 5 4 3 2 2 4 0 1 1 6 , 0 8 6 1 j f x x x x M x x x x x x x x x x x x x x x j M 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 6 3 1 0 4x 5x 6x 0 M M 10 16 8 2 4 2 5 3 1 2 1 0 0 f x 24M 6 6M 3M 3 1M 0 4 1 4x 5x 1x 0 M 6 2 0 1 0 1 0 0 11 0 0 4 1 2 12 0 f x 24 0 11 9M 2 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG P.A.T.Ö cuûûa BTM laøø vôùùi aåån giaûû x5 = 0 P.A.T.Ö cuûûa BT goáác laøø xopt = (0, 0, 8) vaøø f(xopt) = 8. HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 6 3 1 0 4x 5x 3x 0 M 1 2 0 1 0 1 0 0 11 0 0 8 2 4 1 0 f x 8 4 11 1M 0 0 0, 0, 8, 2, 0, 0x THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG Ví duïï 1.19. (tröôøøng hôïïp c). Giaûûi baøøi toaùùn QHTT Theâm 2 aâ åån phuïï x4, x5 0 vaøøo raøøng buoääc (1) & (2) 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 2 max 4 2 12 2 2 10 2 1 2 10 0 1,3j f x x x x x x x x x x x x x x j THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG 1 2 3 1 2 3 4 1 2 3 5 1 2 3 ( ) 2 max 4 2 12 2 2 10 2 1 2 10 0 1,5j f x x x x x x x x x x x x x x x x j ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Theâm 2 aâ åån giaûû vaøøo x6, x7 0 laààn löôïït vaøøo raøøng buoääc (1) & (3). Ta coùù baøøi toaùùn daïïng chuaåån nhö sau Ta coùù baûûng ñôn hình môûû roääng 1 2 3 6 7 1 2 3 4 6 1 2 3 5 1 2 3 7 ( ) 2 max 4 2 12 2 2 10 12 10 2 0 1,7j f x x x x M x x x x x x x x x x x x x x x x j M 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG P.A.T.Ö Xopt = (0, 0, 6, 0, 16, 0, 13), vôùùi x7 = 13 0 neân baâ øøi toaùùn goáác khoâng coâ ùù P.A.T.Ö. 1 1 2 4 M HEÄÄ SOÁÁ AÅÅN C.B P.A 1x 2x 3x 4x 5x 2 1 1 0 0 6x 5x 7x M 0 M 12 10 10 4 2 1 1 2 0 1 2 1 1 2 0 0 f x 22M 3 2M 3 1M 32 1M M 0 2 0 1 3x 5x 7x 1 0 M 6 2 12 1 12 0 16 4 3 2 0 12 1 13 0 9 4 0 14 0 f x 6 13M 0 912 4 M 0 0 THUAÄÄT GIAÛÛI ÑÔN HÌNH MÔÛÛ ROÄÄNG LAÄÄP MO HÌNH BA ØØI TOAÙÙN [1] [2] [3] [4] BAØØI TOAÙÙN QHTT DAÏÏNG CHÍNH TAÉÉC [5a] [5b] XAÙÙC ÑÒNH P.A – P.A.C.B VAØØ P.A.T.Ö. [6] [7a] [7b] [7c] GIAÛÛI BAØØI TOAÙÙN QHTT BAÈÈNG PP HÌNH HOÏÏC [8a] [8b] [8c] GIAÛÛI BAØØI TOAÙÙN QHTT BAÈÈNG PP ÑÔN HÌNH [9] [10] [11] [12] [13] [14] [15] [16] [17] BAØØI TAÄÄP CHÖÔNG 1 ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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 Ñònh möùc Nguyeân lieäu Boä tuû Boä cöûa Boä sa-loâng Boä giöôøng nguû Goã nhoùm I 30 40 0 10 Goã nhoùm II 10 20 50 60 Goã nhoùm III 10 50 80 20 Lôïi nhuaän (trieäu ñoàng) 0,5 0,8 0,4 0,6 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 ñ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 quaûng caùo Chi phí cho moãi laàn quaûng caùo (trieäu ñoàng) Soá laàn quaûng caùo toái ña trong thaùng Döï ñoaùn soá ngöôøi xem quaûng caùo 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 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 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. 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), ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy eãn C oâ g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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 Chi phí vaän chuyeån Kho B1 B2 B3 B4 Löôïng haøng hieän coù (taán) 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 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 (a) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ( ) 4 3 2 min 4 6 2 3 8 3 4 2 3 0, 0 f x x x x x x x x x x x x x x x ; (b) 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 2 3 max 4 2 15 5 2 10 3 6 2 25 0, 0 f x x x x x x x x x x x x x x x XAÙC ÑÒNH PHÖÔNG AÙN – PHÖÔNG AÙN CÖÏC BIEÂN VAØ PHÖÔNG AÙN TOÁI ÖU [7] Cho baøi toaùn quy hoaïch tuyeán tính 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? (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? [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 (a) 1 2 3 1 2 3 1 2 3 ( ) 4 3 2 min 1 3 0, 1, 2,3j f x x x x x x x x x x x j ; (b) 1 2 3 1 2 3 1 2 3 ( ) 4 3 2 min 10 2 3 14 0, 1,2,3j f x x x x x x x x x x x j ; (c) 1 2 3 1 2 3 1 2 ( ) 4 3 2 min 4 0 0, 1, 2,3j f x x x x x x x x x x j 1 2 3 4 1 2 3 4 1 2 3 1 2 3 4 j f(x) 3x 7 2 max 2x 3 2 30 2x 2 3 60 2x 2 3 +4 32 x 0 (j 1,4) x x x x x x x x x x x ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng uy ãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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 (a) 1 2 1 2 1 2 1 2 ( ) max 1 3 2 6 3 9 0, 1, 2j f x x x x x x x x x x j ; (b) 1 2 1 2 1 2 1 2 ( ) 5 4 max 2 8 2 4 3 2 12 0, 1, 2j f x x x x x x x x x x j ; (c) 1 2 1 2 1 2 1 2 ( ) 5 3 min 2 6 0 2 0 0, 1, 2j f x x x x x x x x x x j 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: 3,10 53 224 12 min3)( 31 321 321 321 jx xx xxx xxx xxxxf j Ñ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: 6,10 9342 12 2 min322)( 6543 642 6541 65421 jx xxxx xxx xxxx xxxxxxf j Ñ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: 7,10 2021711 1 2 1 4 13 3 4 12 2 1 max343)( 76541 65431 5421 4321 jx xxxxx xxxxx xxxx xxxxxf j Ñ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 ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng u eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 6,10 10824 1242 723 min22)( 6532 432 5321 532 jx xxxx xxx xxxx xxxxf j Ñ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: 4,10 16222 31235 2822 min2243)( 4321 4321 421 4321 jx xxxx xxxx xxx xxxxxf j Ñ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: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 ( ) 3 2 2 min 2 4 10 3 2 2 8 4 2 4 0 1,4j f x x x x x x x x x x x x x x x x x j Ñ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: 4,10 102 2052 1532 min32)( 4321 321 321 4321 jx xxxx xxx xxx xxxxxf j Ñ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: 6,10 2 2 1423 3 2 1 3 12 4226 min52)( 654321 54321 654321 65421 jx xxxxxx xxxxx xxxxxx xxxxxxf j Ñ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. ÝØJLÒÙ ïæ ÞßH× ÌÑßGÒ ÏË× ØÑßQÝØ ÌËÇÛ_Ò ÌSÒØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½ Ng u eãn C oân g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com