Bài toán qui hoạch tuyến tính

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í P