zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Tối ưu hóa: Chương 1 - ThS. Nguyễn Công Trí

Chia sẻ: Sơn Tùng | Ngày: | Loại File: PDF | Số trang:26

Báo xấu

130
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Tối ưu hóa - Chương 1: Bài toán quy hoạch tuyến tính" cung cấp cho người học các kiến thức: Thiết lập mô hình bài toán, các dạng của bài toán quy hoạch tuyến tính, các khái niệm cơ bản của bài toán quy hoạch tuyến tính,... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tối ưu hóa: Chương 1 - ThS. Nguyễn Công Trí

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TOAÙN CHÖÔNG 1 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT QUY HOAÏCH TUYEÁN TÍNH 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 1. THIEÁT LAÄP MOÂ HÌNH BAØI TOAÙN (Xem) ñeå saûn xuaát ra moät loaïi saûn phaåm theo 3 phöông 2. CAÙC DAÏNG CUÛA BAØI TOAÙN QUY phaùp khaùc nhau: PP1; PP2; PP3. Ñònh möùc nguyeân Ths. Nguyeãn Coâng Trí HOAÏCH TUYEÁN TÍNH (Xem) lieäu vaø soá löôïng saûn phaåm saûn xuaát ra trong 1 giôø ñöôïc cho ôû baûng sau: 3. CAÙC KHAÙI NIEÄM CÔ BAÛN VEÀ BAØI TOAÙN Nguyeân Soá löôïng Ñònh möùc nguyeân lieäu Lieäu hieän coù (ñv) PP1 PP2 PP3 Copyright 2001 QUY HOAÏCH TUYEÁN TÍNH (Xem) N1 250 4 5 3 N2 350 2 4 1 4. CAÙC PHÖÔNG PHAÙP GIAÛI BAØI TOAÙN N3 450 3 6 4 QUY HOAÏCH TUYEÁN TÍNH (Xem) Soá saûn phaåm (sp/giôø) 10 12 9 Ths. Nguyeãn Coâng Trí Haõy laäp moâ hình baøi toaùn sao cho xí nghieäp saûn 5. BAØI TAÄP (Xem) Copyright 2001 xuaát ra nhieàu saûn phaåm nhaát? MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi x1, x2, x3 laàn löôït laø thôøi gian saûn xuaát ra saûn Ví duï 1.2. BAØI TOAÙN PHA CAÉT VAÄT LIEÄU 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) Moät xí nghieäp may maëc caàn saûn xuaát ñuùng 2.000 f(x) = 10x1 + 12x2 + 9x3  max quaàn vaø ít nhaát 1.000 aùo. Moãi taám vaûi coù 6 caùch Do xí nghieäp chæ coù 250 nguyeân lieäu N1 neân x1, x2, caét nhö sau: Caùch caét Quaàn AÙo x3 phaûi thoûa maõn 4x1 + 5x2 + 3x3 ≤ 250 Töông töï cho caùc nguyeân lieäu N2, N3 ta coù 1 90 35 2x1 + 4x2 + x3 ≤ 350 vaø 3x1 + 6x2 + 4x3 ≤ 450 2 80 55 Dó nhieân ta phaûi coù x1, x2, x3 khoâng aâm 3 70 70 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 4 60 90 f(x)= 10x1 + 12x2 + 9x3  max, thoûa caùc ñieàu kieän 5 120 0 4x1 + 5x2 + 3x3 ≤ 250 6 0 100 2x1 + 4x2 + x3 ≤ 350 3x1 + 6x2 + 4x3 ≤ 450 Haõy tìm phöông aùn caét quaàn aùo sao cho toång soá x1  0 x2  0 x3  0 taám vaûi laø ít nhaát? 1
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi xj (j = 1, 2, ..., 6) laø soá taám vaûi ñöôïc caét theo Ví duï 1.3. BAØI TOAÙN XAÙC ÑÒNH KHAÅU PHAÀN caùch thöù j. Ñeå nuoâi moät loaïi gia suùc coù hieäu quaû, moãi ngaøy Toång soá taám vaûi duøng ñeå saûn xuaát (caàn laøm cöïc caàn phaûi coù khoái löôïng toái thieåu caùc chaát protit, tieåu) laø f(x) = x1 + x2 + x3 + x4 + x5 + x6  min glucit, khoaùng töông öùng laø 90 gram, 130 gram, Do xí nghieäp caàn saûn xuaát ñuùng 2.000 quaàn neân 10 gram. Tyû leä (%) theo khoái löôïng caùc chaát treân caùc xj phaûi thoûa maõn coù trong caùc loaïi thöùc aên A, B, C nhö sau: 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 Thöùc aên Chaát dinh döôõng (%) Töông töï cho ñieàu kieän veà saûn xuaát aùo, ta coù 35x1 + 55x2 + 70x3 + 90x4 + 100x6  1000 Protit Glucit Khoaùng Dó nhieân ta phaûi coù xj (j = 1, 2, ..., 6) khoâng aâm A 10 30 2 Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: B 20 40 1 Tìm caùc bieán xj (j = 1, 2, ..., 6) sao cho C 30 20 3 f(x)= xj  min, thoûa caùc ñieàu kieän Giaù 1 kg thöùc aên A, B, C töông öùng laø 3.000 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 ñoàng, 4.000 ñoàng, 5.000 ñoàng. Haõy laäp moâ hình 35x1 + 55x2 + 70x3 + 90x4 + 100x6  1000 baøi toaùn xaùc ñònh khoái löôïng thöùc aên caàn thieát xj  0, (j = 1, 2, ..., 6). 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 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi xj (j = 1, 2, 3) laø soá gram thöùc aên A, B, C caàn Ví duï 1.4. BAØI TOAÙN VAÄN TAÛI mua moãi ngaøy. Toång chi phí duøng ñeå mua thöùc aên (caàn laøm cöïc Caàn vaän chuyeån xi maêng töø 3 kho K1, K2, K3 ñeán 4 tieåu) laø f(x) = 3x1 + 4x2 + 5x3  min (ñoàng) coâng tröôøng xaây döïng T1, T2, T3, T4. Cho bieát löôïng Do caùc tyû leä caùc chaát protit, glucit vaø khoaùng coù xi maêng coù ôû moãi kho, löôïng xi maêng caàn ôû moãi trong thöùc aên A neân caùc xj phaûi thoûa maõn coâng tröôøng vaø cöôùc phí vaän chuyeån (ngaøn 0,1x1 + 0,2x2 + 0,3x3  90 ñoàng/ taán) töø moãi kho ñeán coâng tröôøng nhö sau: Töông töï cho ñieàu kieän cuûa thöùc aên B vaø C, ta coù Coâng tröôøng T1: 130 t T2: 160 t T3: 120 t T4: 140 t 0,3x1+0,4x2+0,2x3 130 vaø 0,02x1+0,01x2+0,03x310 Kho Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: K1: 170 taán 20 18 22 25 Tìm caùc bieán xj (j = 1, 2, 3) sao cho K2: 200 taán 15 25 30 15 f(x) = 3x1 + 4x2 + 5x3  min, thoûa caùc ñieàu kieän K3: 180 taán 45 30 40 35 0,1x1 + 0,2x2 + 0,3x3  90 0,3x1 + 0,4x2 + 0,2x3  130 Laäp moâ hình baøi toaùn vaän chuyeån sao cho caùc 0,02x1 + 0,01x2 + 0,03x3  10 kho phaùt heát xi maêng coù, coâng tröôøng nhaän ñuû xi xj  0, (j = 1, 2, 3). maêng caàn vaø chi phí vaän chuyeån thaáp nhaát? 2
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT 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. 2.1. DAÏNG TOÅNG QUAÙT Toång chi phí vaän chuyeån (caàn laøm cöïc tieåu) laø Tìm x = (x1, x2,..., xn) sao cho: f(x) = 20x11 + 18x12 + 22x13 + 25x14 n 15x21 + 25x22 + 30x23 + 15x24 f ( x )   c j x j  min ( hay max) (2.1) 45x31 + 30x32 + 40x33 + 35x34  min j 1 Ñieàu kieän cuûa caùc kho  n      x11 + x12 + x13 + x14 = 170  aij x j    bi i  1, m  2.2  x21 + x22 + x23 + x24 = 200  j 1    x31 + x32 + x33 + x34 = 180  Ñieàu kieän cuûa caùc coâng tröôøng  x j  0, xk  0, j  k  n  2.3  x11 + x21 + x31 = 130 (2.1) goïi laø haøm muïc tieâu. (2.2) goïi laø heä raøng x12 + x22 + x32 = 160 buoäc. (2.3) goïi laø raøng buoäc veà daáu cuûa aån soá. x13 + x23 + x33 = 120 x14 + x24 + x34 = 140 Ví duï 1.1, Ví duï 1.2 vaø Ví duï 1.3 laø caùc baøi toaùn xij  0, i = 1, 2, 3, j = 1, 2, 3, 4. QHTT coù daïng toång quaùt. CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT  Moät vectô x = (x1, x2,..., xn) thoûa maõn ñieàu kieän 2.2. DAÏNG CHÍNH TAÉC (2) vaø (3) ñöôïc goïi laø moät phöông aùn (P.A) cuûa Tìm x = (x1, x2,..., xn) sao cho: n baøi toaùn quy hoaïch tuyeán tính (QHTT). f ( x)   c j x j  min ( hay max)  Taäp caùc P.A cuûa baøi toaùn ñöôïc goïi laø mieàn j 1 raøng buoäc hay mieàn xaùc ñònh. Kyù hieäu laø D.  n  Phöông aùn toái öu (P.A.T.Ö) hay nghieäm cuûa  aij x j  bi i  1, m  j 1 baøi toaùn, kyù hieäu laø Xopt (optimality), neáu vectô X  x  0, j  1, n laø moät P.A vaø haøm muïc tieâu (2.1) bò chaën.  j Nhaän xeùt: Heä raøng buoäc cuûa baøi toaùn daïng chính  Baøi toaùn ñöôïc goïi laø giaûi ñöôïc hay coù lôøi giaûi hay coù nghieäm neáu noù coù ít nhaát moät P.A.T.Ö. taéc ñeàu laø caùc ñaúng thöùc vaø moïi bieán cuûa baøi  Baøi toaùn khoâng giaûi ñöôïc hay voâ nghieäm neáu toaùn ñeàu khoâng aâm. Ví duï 1.4 BAØI TOAÙN VAÄN TAÛI D =  hay noù coù P.A nhöng khoâng coù PA.T.Ö. coù daïng chính taéc. 3
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT 2.3. DAÏNG CHUAÅN 2.4. CHUYEÅN ÑOÅI DAÏNG BAØI TOAÙN QHTT Tìm x = (x1, x2,..., xn) sao cho: Khi xeùt baøi toaùn QHTT, ngöôøi ta thöôøng söû duïng n f ( x)   c j x j  min ( hay max) daïng chính taéc, coù theå ñöa baøi toaùn daïng toång j 1 n m quaùt veà daïng chính taéc baèng caùc bieán ñoåi sau:   xi   ai ,mk xm k  bi , i  1, m 1) Neáu raøng buoäc thöù i coù daïng aijxj ≤ bi thì theâm  k 1 vaøo moät aån phuï xn+1  0, sao cho aijxj + xn+1 = bi.  x  0 j  1, n b  0  j i 2) Neáu raøng buoäc thöù i coù daïng aijxj  bi thì theâm 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 vaøo moät aån phuï xn+1  0, sao cho aijxj – xn+1 = bi. con Im laø ma traän ñôn vò caáp m. 3) Neáu aån xj ≤ 0 thì ñöôïc thay baèng x/j = – xj  0. Trong ñoù caùc xi (i = 1, 2,..., m) ñöôïc goïi laø aån cô 4) Neáu aån xj khoâng raøng buoäc veà daáu thì thay xj baûn (A.C.B), coøn caùc aån xi,m+k, (k = 0, 1,..., n – m) baèng hai aån phuï x/j vaø x//j sao cho xj = x/j – x//j, vôùi ñöôïc goïi laø aån khoâng cô baûn. x/j  0, x//j  0. CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT 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 Ví duï 1.5. Ñöa baøi toaùn QHTT sau ñaây veà daïng  a11 a12  a1n   a1 j   b1   c1   x1  0 chính taéc vaø vieát baøi toaùn chính taéc döôùi daïng a a22  a2 n  a   b   c   x  0 ma traän A   21  , Aj   2 j  ,b   2  ,c   2  , x   2  ,0    f ( x )  x1  3 x2  2 x3  min                        am1 am 2  amn   amj   bm   cn   xn  0  3 x1  x2  2 x3  7 Trong ñoù A laø ma traän mn goàm caùc heä soá ôû veá 2 x  4 x  x3  12  1 2 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ä 4 x1  3 x2  8 x3  10  x1  0 x3  0 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. Theâm 2 aån phuï x4, x5  0 vaøo raøng buoäc thöù nhaát Khi ñoù baøi toaùn QHTT ôû daïng chính taéc coù daïng vaø raøng buoäc thöù ba. f(x) = cTx  min (hay max) Thay x/3 = –x3  0 Ax = b, x  0 Thay x2 = x/2 –x//2  0, vôùi x/2, x//2  0 4
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT Baøi toaùn QHTT coù daïng chính taéc nhö sau Ví duï 1.6. Cho baøi toaùn QHTT: f ( x)  x1  3x2  3x2  2 x3  min f ( x )  x2  x5  min  3x1  x2  x2  2 x3  x4  7  2 x  4 x  x1  x2 2 x5  1  1 2 4 x2  x3   12  3 x2  x3  x5  3 4  1 x  3 x  2  3x2  8 x3  x5  10 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 xj  0 j  1,5 f(x) = (1, 3, – 2, 0, 0, 0)T(x1, x/2, x//2, x/3, x4, x5)  min Ta coù ma traän heä soá cuûa heä raøng buoäc:  x1   x   1 1 0 0  2   1 1 2 1 0     7  2 3 A  0 3 1 0 1   2 4 4 1 0 0   x2    12  0  2 0 1 1          4 3 3 8 0 1  x3   10    x      4 x5  chöùa I3 neân baøi toaùn quy hoaïch tuyeán tính treân coù  (x1, x/2, x// , x/ , x , x )  (0, 0, 0, 0, 2 3 4 5 0, 0) daïng chuaån. ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN Moät phöông aùn x* = (x1*, x2*,..., xn*) cuûa baøi toaùn Ví duï 1.7. Cho baøi toaùn QHTT QHTT daïng toång quaùt laø phöông aùn cöïc bieân f ( x )  50 x1  16 x2  23 x3  min (P.A.C.B) neáu x* = (x1*, x2*,..., xn*) thoûa maõn chaët 5 x1  3 x2  4 x3  2 n raøng buoäc ñoäc laäp tuyeán tính. Töùc laø:  x n  2 *  1  aijx j = bi , i=1,k, k  m  x1  x2  3x3  1 X * la P.A.C.B *   j=1 k +l  n,det  A   0 x* =0, j=1,l, l  n 6 x  2 x2  x3  4  j  1 Trong ñoù A laø ma traän con caáp n cuûa hpt (*).  x2  0 x3  0  Moät P.A.C.B khoâng suy bieán laø moät P.A.C.B Caùc vectô naøo sau ñaây thoûa maõn ñuùng n raøng buoäc chaët.  23 6   Moät P.A.C.B suy bieán laø moät P.A.C.B thoûa maõn X   0, 1, 3 Y   3, 0, 0  Z   2,  ,   5 5 hôn n raøng buoäc chaët. laø phöông aùn cöïc bieân? P.A.C.B coøn ñöôïc goïi laø phöông aùn cô baûn. 5
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT º Deã daøng kieåm tra X khoâng phaûi laø phöông aùn. ÑÒNH LYÙ 1. (TÍNH ÑAËC TRÖNG CUÛA P.A.C.B) Y, Z laø phöông aùn cuûa baøi toaùn. 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 º Y thoûa 2 raøng buoäc chaët (2 raøng buoäc veà daáu) bieân neáu vaø chæ neáu heä vectô coät Aj öùng vôùi neân Y chæ laø P.A. thaønh phaàn xj* > 0 laø ñoäc laäp tuyeán tính. º Z thoûa 3 raøng buoäc chaët (raøng buoäc 2, raøng Ví duï 1.8. Cho baøi toaùn QHTT buoäc 3, raøng buoäc 4) vaø f ( x)   x1  2 x2  3 x3  min  x1  x2  x3  4 1 0 0     x1  x2  0 det  1 1 3   1   6   5  0 6 2 1     x j  0, j  1,3 Vaäy Z laø phöông aùn cöïc bieân cuûa baøi toaùn. 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 CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT  X, Y, Z thoûa caùc raøng buoäc neân chuùng laø P.A. HEÄ QUAÛ 2. Soáù thaønh phaàn döông trong moãi  Maët khaùc ta coù phöông aùn cöïc bieân cuûa baøi toaùn quy hoaïch 1 1 1  A1    A2    A3    tuyeán tính daïng chính taéc toái ña baèng m (m laø 1  1 0 soá doøng cuûa ma taän A). 1 1  ÑÒNH LYÙ 2. (SÖÏ TOÀN TAÏI CUÛA PHÖÔNG AÙN TOÁI ÖU)  Vôùi X = (2, 2, 0), det    2 neân X laø P.A.C.B.  1 1 Neáu baøi toaùn quy hoaïch tuyeán tính coù phöông  Vôùi Y = (0, 0, 4), heä chæ goàm moät vectô A3 neân aùn vaø haøm muïc tieâu bò chaën döôùi (ñoái vôùi Y cuõng laø P.A.C.B. f(x) min) hoaëc haøm muïc tieâu bò chaën treân  Vôùi Z=(1, 1, 2), ta thaáy heä {A1, A2, A3} phuï thuoäc (ñoái vôùi f(x) max) treân taäp caùc phöông aùn thì tuyeán tính vì A1+A2–2A3=0 neân Z khoâng laø P.A.C.B. baøi toaùn coù phöông aùn toái öu. HEÄ QUAÛ 1. (tính höõu haïn cuûa P.A.C.B). ÑÒNH LYÙ 3. (SÖÏ TOÀN TAÏI CUÛA P.A.C.B. TOÁI ÖU) Soáù phöông aùn cöïc bieân cuûa baøi toaùn QHTT Neáu baøi toaùn QHTT daïng chính taéc coù P.A.T.Ö daïng chính taéc laø höõu haïn. thì baøi toaùn coù P.A.C.B toái öu (P.A.C.B.T.Ö). 6
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT 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.Ö) Ví duï 1.9 . Neáu baøi toaùn coù P.A.T.Ö laø Xopt vaø X(1), X(2) laø 2 phöông aùn khaùc nhau cuûa baøi toaùn thoaû Xopt = Vôùi baøi toaùn quy hoaïch tuyeán tính X(1) + (1–)X(2), 0    1 thì X(1), X(2) laø P.A.T.Ö. NHAÄN XEÙT f ( x)  x 2  x5  min 1. Ta coù theå tìm P.A.T.Ö cuûa baøi toaùn QHTT x1  x2  2 x5  1 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 3x 2  x3  x5  3 chuaån baèng caùch cho caùc aån khoâng cô baûn  2 x2  x4  x5  2 baèng khoâng (xem Ví duï 1.9). 2. Trong baøi toaùn QHTT daïng chính taéc. Neáu x j  0 j  1,5 haïng cuûa ma traän heä soá A laø m thì P.A.C.B Ta coù phöông aùn X = (1, 0, 3, 2, 0) laø phöông aùn ñöôï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 cöïc bieân cuûa baøi toaùn vì caùc aån x1, x3, x4 laø caùc thaønh phaàn döông thì ñöôïc goïi laø P.A.C.B suy aån cô baûn cuûa baøi toaùn daïng chuaån. bieán (xem Ví duï 1.10). CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT CAÙC PHÖÔNG PHAÙP GIAÛI Ví duï 1.10 . Vôùi baøi toaùn quy hoaïch tuyeán tính BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH f ( x)  3 x1  4 x2  2 x3  2 x4  min 2 x1 2 x2  x4  28 4.1. PHÖÔNG PHAÙP HÌNH HOÏC (Xem) x1 2 x1 5 x2 2 x2 3 x3 2 x3 2 x4  x4  26  16 Ths. Nguyeã 4.2. PHÖÔNG nHÌNH PHAÙP ÑÔN Coâng Trí (Xem) x j  0 j  1, 4 4.3. PHÖÔNG PHAÙP ÑÔN HÌNH MÔÛ ROÄNG 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. Copyright 2001 (BAØI TOAÙN M) (Xem)  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. 7
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC 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 ax+by=c suaát vaø chi phí saûn xuaát cuûa moãi PX trong 1 giôø: =m (ñöôøng möùc) Phaân xöôûng PX1 PX2 taêng ax+byc Saûn phaåm B 100 200 a O Chi phí (trieäu ñoàng/ giôø) 0,6 1 giaûm b N(a,b) Ñô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. PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC 0,6x1+x2=m 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. 100x1+200x2=3000 Mieàn raøng buoäc Ta coù moâ hình baøi toaùn D f  x   0,6 x1  x2  min 20 A1(0,20) 15 250 x1  250 x2  5000 10 A3 taêng  (10,10) A2(30,0) 100 x1  200 x2  3000 10 20 30 x  0 x2  0  1 giaûm 250x1+250x2=5000 Duøng phöông phaùp hình hoïc ñeå giaûi baøi toaùn Vaäy P.A.T.Ö: xopt(10,10) vaø f(xopt)=16 trieäu ñoàng. treân nhö sau 8
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC -2x1+x2= m x1-x2= -2 Ví duï 1.12. Giaûi baøi toaùn quy hoaïch tuyeán tính Mieàn raøng buoäc  f  x   2 x1  x2  min D -x1+2x2= -2  2  x1  x2  2 A1(0,2)    x1  2 x2  2 x  0 x2  0 -2 -1 O 2A 2(2,0)  1 taêng giaûm -1 baèng 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. CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH Ví duï 13: giaûi baøi toaùn f ( x)  3x1  2 x2  x3  min Ta coù P.A.C.B laø x = (0, 0, 0, 10, 5, 8)  2 x1 4 x2 3 x3  10 Baøi toaùn töông ñöông 3x  x 4 x3  5 f ( x)  3x1  2 x2  x3  min  1 2 x 2 x2 2 x3  8  w1  10 2 x1 4 x2 3 x3  1  w  5 3 x  x  x j  0 j  1,3  2 1 2 4 x3  w  8  x Ñöa baøi toaùn veà daïng chính taéc 2 x2 2 x3  3 1 f ( x)  3 x1  2 x2  x3  min  x j  0 j  1,3, wi  0, i  1,3  2 x1 4 x2 3x3  w1  10 coù P.A.C.B laø x = (0, 0, 0, 10, 5, 8) vaø f(x) = 0. 3 x  x 4 x3  w2  5  1 2 Nhaän xeùt: x 2 x2 2 x3  w3  8  1 coù theå ñoåi P.A baèng caùch taêng x1 baèng moät giaù  x j  0, j  1,3, wi  0, i  1,3 trò döông vaø giöû x2 = x3 = 0 thoûa ñieàu kieän wi ≥ 0.  9
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH Ta coù Ta coù keát quaû  x1  5 f ( x)  5  w2  x2  3 x3  min  w1  10 2 x1  0    5 5  20 2 10 1  w2  5 3x1  0   x1   x1   w1  3  3 w2  3 x2  3 x3 w  3 3  3  8  x1  0 (Choïn doøng 2)   x1  8 x  5 1 1 4  1  w2  x2  x3  3 3 3 3 Choïn x1 = 5/3, ta ñöôïc P.A môùi laø  19 1 5 2 x1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3.  w3   w2  x2  x3  3 3 3 3 Vaø f(x) = - 5.  x  0 j  1,3, wi  0, i  1,3 Baøi toaùn töông ñöông: taïi raøng buoäc thöù hai tính Nhaän xeùt:  j x1 theo caùc bieán coøn laïi, roài theá giaù trò x1 vöøa tính coù theå ñoåi P.A baèng caùch taêng x2 baèng moät giaù ñöôïc vaøo caùc raøng buoäc vaø haøm muïc tieâu. 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 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH Ta coù Ta coù keát quaû 3 4 31  20 10 f ( x)  7  w1  w2  x3  min  w1  3  3 x1  0  10 5 10   x2  2  3 1 1  5 1   x2  2  10 w1  5 w2  10 x3  x1   x2  0   x2  5  x2  2  3 3    19 5  x2  19 (Choïn doøng 1)  x  1  1 w  6 w  39 x w   x  0  1 10 1 15 2 30 3  3 2  5   3 3 Choïn x2 = 2, ta ñöôïc P.A môùi laø  1 2  w3  3  w1  x3 x1 = 1, x3 = w1 = w2 = 0, w3 = 3 vaø f(x) = - 7.  2 3 Baøi toaùn töông ñöông: taïi raøng buoäc thöù nhaát  x j  0 j  1,3, wi  0, i  1,3 tính x2 theo caùc bieán coøn laïi, roài theá giaù trò x2 vöøa Baøi toaùn coù P.A.T.U laø xopt = (1, 2, 0) tính ñöôïc vaøo caùc raøng buoäc vaø haøm muïc tieâu. vaø f(xopt) = - 7 10
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH n m m nm m Döïa treân cô sôû baøi toaùn coù daïng chuaån n  2   xi  bi   ai ,mk xmk , f  x    ci xi     ai ,mk ci  cmk xmk f ( x)   c j x j  min  hay max 1 k 1 m i 1 k 1  i 1  n m j 1 nm Ñaët  mk  a i 1 c  cm k thì f  x   f  x     mk xmk i ,m k i 0 k 1   xi   ai ,m  k xm  k  bi  2  Neáu  m k  0 thì f  x 0   f  x  , vì xmk  0  k 1  x  0 j  1, n b  0  3  j  Daáu hieäu toái öu cuûa baøi toaùn i  Neáu  mk  0 thì f  x   f x 0 , vì   xmk  0 m Phöông aùn cöïc bieân ñaàu tieân laø: x 0  (b1 , b2 ,; bm ,.0,0)  f ( x 0 )   cibi m Kyù hieäu laïi:  j  a c  c i 1 ij i j i 1 Choïn moät P.A baát kyø cuûa baøi toaùn (1) Khi f ( x )  Min thì  j  0; j n m nm x  D, x  ( x1 , x2 ,, xn )  f ( x )   c j x j   ci xi   cmk xmk j 1 i 1 k 1 (2) Khi f ( x )  Max thì  j  0; j CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH  Daáu hieäu baøi toaùn khoâng coù P.A.T.Ö  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 phöông aùn cöïc bieân, neáu toàn taïi Ñònh lyù. Vôùi moät P.A.C.B, neáu j>0, i: aij > 0 thì baøi j > 0 maø aij ≤ 0, i thì baøi toaùn khoâng coù P.A.T.Ö. toaùn coù P.A.C.B khaùc toát hôn P.A.C.B ñang xeùt. (xem Ví duï 1.13) Heä Aån PA C1 C2 …... Ci ……... Cm Cm+1 …...… Cj ... Cn Heä Aån PA C1 C2 …... Ci ……... Cm Cm+1 … ...… C j ... C n soá C.B CB x1 x2 ... xi …...… xm xm+1 …...… xj ... xn soá C.B CB x1 x2 ... xi …...… xm xm+1 … ...… x j ... x n C1 x 1 b1 1 0 . .. . .. . .. 0 a1,m+1 …...… a1j ... a1n C1 x1 b1 1 0 ... ... ... 0 a1,m+1 …...… a1j ... a1n C2 x 2 b2 0 1 … ... . .. . .. 0 a2,m+1 ……... a2j ... a2n C2 x2 b2 0 1 …... ... ... 0 a2,m+1 ……... a2j ... a2n . .. . .. ... ... ... ... ... ... ... ... . .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Ci x i bi 0 0 … ... . .. … ... 0 ai,m+1 ... aij ...… ain Ci xi bi 0 0 …... ... …... 0 ai,m+1 ... aij ...… ain . .. . .. ... ... ... …... ... …... ... ... . .. ... ... ... ... ... ... ... ... …... ... …... ... ... ... ... ... ... C m x m bm 0 0 … ... . .. … ... 1 am,m+1 ...… amj …... amn Cm xm bm 0 0 …... ... …... 1 am,m+1 ...… amj …... amn f(x) f(x0) 0 0 …... ... …... 0 m+1 … ...  j ... …  n 0 f(x) f(x ) 0 0 …... ... …... 0 m+1 …... j ...… n 11
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAÛNG ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Heä Aån PA C1 C2 …... Ci ……... Cm Cm+1 …...… Cj ... Cn LAÄP BAÛNG ÑÔN HÌNH soá C.B CB x1 x2 ... xi …...… xm xm+1 …...… xj ... xn j ≤ 0,j? Ñuùng P.A.T.Ö C1 x1 b1 1 0 ... ... ... 0 a1,m+1 …...… a1j ... a1n Sai C2 x2 b2 0 1 …... ... ... 0 a2,m+1 ……... a2j ... a2n Ñuùng KEÁT THUÙC aij ≤ 0,i? ... ... ... ... ... ... ... ... ... ... ... ... ... ... Sai THUAÄT GIAÛI Ci xi bi 0 0 …... ... …... 0 ai,m+1 ... aij ...… ain XAÙC ÑÒNH PHÖÔNG AÙN MÔÙI BAØI TOAÙN ... ... ... ... ... …... ... …... ... ... ... ... ... ... Aån vaøo: Max  j  x j  j 0 KHOÂNG COÙ P.A.T.Ö Cm xm bm 0 0 …... ... …... 1 am,m+1 ...… amj …... amn bi Aån ra:   Min  xi aij 0 aij f(x) f(x0) 0 0 …... ... …... 0 m+1 …... j ...… n BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH SOÁ BÖÔÙC LAËP LAØ HÖÕU HAÏN THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Thuaät giaûi goàm 4 böôùc: Böôùc 4: Tìm P.A.C.B môùi cuûa baøi toaùn Böôùc 1: Laäp baûng ñôn hình  Choïn aån vaøo: Baøi toaùn phaûi ôû daïng chuaån, ñöa caùc soá lieäu vaøo Choïn Maxj (j > 0), aån xj seõ ñöôïc choïn ñöa vaøo baûng ñôn hình. heä aån cô baûn öùng vôùi j ñaõ ñöôïc choïn. Böôùc 2: Kieåm tra tính toái öu cuûa baøi toaùn  Choïn aån ra: Choïn  = Min{bi/aij} (aij > 0), aån xi seõ ñöôïc choïn Tính j = ∑aijci – cj ñöa ra khoûi heä aån cô baûn öùng vôùi  nhoû nhaát.  Neáu j ≤ 0: baøi toaùn coù P.A.T.U. Phaàn töû aij (öùng vôùi aån vaøo xi vaø aån ra xj) ñöôïc  Neáu j > 0: chuyeån sang böôùc 3. goïi laø phaàn töû truïc. Böôùc 3: Kieåm tra tính giaûi ñöôïc cuûa baøi toaùn  Duøng phöông phaùp bieán ñoåi sô caáp doøng  Neáu aij ≤ 0, i: baøi toaùn khoâng coù P.A.T.U. treân ma traän heä soá ñeå bieán ñoåi aån môùi ñöa vaøo  Neáu aij > 0: chuyeån sang böôùc 4. trôû thaønh aån cô baûn. Sau ñoù quay veà böôùc 2. 12
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH 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í duï 1.14. Vôùi P.A.C.B.T.Ö Xopt tìm ñöôïc, neáu j = 0, maø xj Giaûi baøi toaùn quy hoaïch tuyeán tính khoâng laø P.A.C.B thì baøi toaùn coù P.A.C.B.T.Ö khaùc f ( x )  6 x1  x2  x3  3 x4  x5  7 x6  6 x7  min X/opt (xem Ví duï 1.15).  x1  x2  x4  x6  x7 3 Taäp phöông aùn toái öu: 2 x1  x3 4 x4 2 x6  x7 9  Tröôøng hôïp coù hai P.A.C.B.T.Ö laø Xopt vaø X/opt 4 x1 2 x4  x5 3 x6 2 Topt = {Xopt + (1 – )X/opt, [0, 1]} xj  0 j  1,7  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. THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH HEÄ AÅN P.A 6 1 1 3 1 7 6 Ví duï 1.15. SOÁ C.B x1 x2 x3 x4 x5 x6 x7 Giaûi baøi toaùn quy hoaïch tuyeán tính 1 x2 3 1 1 0 1 0 1 1 f (x)  5x1  4x2  5x3  2x4  x5 3x6 min 1 x3 9 2 0 1 4 0 2 1 2x1 4x2 3x3 x4  152 1 x5 2 4 0 0 2 1 3 0 4x1 2x2 3x3 x5  60 f  x 14 5 0 0 6 0 7 6 7 x6 3 1 1 0 1 0 1 1 3x1 x3 x6  36 1 x3 3 0 2 1 2 0 0 3 xj  0 j 1,6 1 x5 11 1 3 0 1 1 0 3 Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? f  x 7 2 7 0 1 0 0 13 Neáu coù tìm taäp phöông aùn toái öu vaø chæ ra 3 BT khoâng coù P.A.T.Ö vì 4= 1 > 0 maø ai4 < 0, i. phöông aùn toái öu. 13
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH HEÄ AÅN P.A 5 4 5 2 1 3 HEÄ AÅN P.A 5 4 5 2 1 3 x1 x2 x3 x4 x5 x6 SOÁ C.B x1 x2 x3 x4 x5 x6 SOÁ C.B 2 x4 152 2 4 3 1 0 0 2 x4 104 0 0 1 1 2 2 1 x5 60 4 2 3 0 1 0 4 x2 6 0 1 5 6 0 12 2 3 3 x6 36 3 0 1 0 0 1 5 x1 12 1 0 1 3 0 0 1 3 f  x 472 12 6 7 0 0 0 f  x  292 0 0 2 0 3 0 2 x4 128 0 4 73 1 0 2 3 Baøi toaùn coù P.A.T.Ö xopt=(12, 6, 0, 104, 0, 0) vaø x5 f(xopt)= 292. 1 12 0 2 53 0 1 4 3 x1 Baøi toaùn coøn P.A.C.B.T.Ö khaùc vì 6 = 0, nhöng x6 5 12 1 0 13 0 0 13 khoâng phaûi laø A.C.B. Ta coù P.A.C.B.T.Ö thöù hai f  x 328 0 6 3 0 0 4 baèng caùch choïn aån x6 laø aån ñöa vaøo. THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Vôùi taäp phöông aùn toái öu, ta coù : HEÄ AÅN P.A 5 4 5 2 1 3 xopt + (1 - )x/opt = SOÁ C.B x1 x2 x3 x4 x5 x6 (12, 6, 0, 104, 0, 0) + (1-)(0, 30, 0, 32, 0, 36) 2 x4 32 6 0 3 1 2 0 = (12 , 30–24, 0, 32 + 72, 0, 36 - 36) 4 x2 30 2 1 3 2 0 12 0 3 phöông aùn toái öu laø 3 x6 36 3 0 1 0 0 1  Vôùi  = 0, ta coù P.A.T.Ö: f  x 292 0 0 2 0 3 0 x/opt = (0, 30, 0, 32, 0, 36) vaø f(x/opt) = 292. Baøi toaùn coù phöông aùn cöïc bieân toái öu khaùc laø  Vôùi  = 1, ta coù P.A.T.Ö: x/opt = (0, 30, 0, 32, 0, 36) vaø f(x/opt) = 292. xopt = (12, 6, 0, 104, 0, 0) vaø f(x/opt) = 292. Taäp phöông aùn toái öu  Vôùi  = ½, ta coù P.A.T.Ö: Topt={xopt + (1 - )x/opt, 0, 1} Zopt = (6, 18, 0, 68, 0, 18) vaø f(zopt) = 292. 14
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH NHAÄN XEÙT. Neáu baøi toaùn coù haøm muïc tieâu Ví duï 1.16. n f ( x)   c j x j  Max Giaûi baøi toaùn quy hoaïch tuyeán tính j 1 Coù hai caùch giaûi: f ( x)  2x1  x2  x3  x4  max  Giaûi tröïc tieáp baøi toaùn (xem Ví duï 1.16), vôùi: x1  x2 2x3  x4  2  Tieâu chuaån toái öu laø  j  0, j  x2 7 x3 3x4  2 •  AÅn vaøo laø Min  j 3x3 2x4  5  j 0 •  AÅn ra laø Min i b aij 0 a ij xj  0 j  1,4  Chuyeån haøm muïc tieâu cuûa baøi toaùn veà min Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? g ( x)   f ( x )  Min Neáu coù, haõy chæ ra phöông aùn toái öu khaùc. THUAÄT GIAÛI ÑÔN HÌNH 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 HEÄ AÅN P.A 2 1 1 1 0 0 phuï x6 ≥ 0 vaøo raøng buoäc thöù ba. SOÁ C.B x1 x2 x3 x4 x5 x6 Ta coù baøi toaùn ôû daïng chuaån 2 x1 2 1 1 2 1 0 0 f ( x)  2x1  x2  x3  x4  max 0 x5 2 0 1 7 3 1 0 x1 x2 2x3 x4  2 0 x6 5 0 0 3 2 0 1 f  x 4 0 1 5 1 0 0 x2 7x3 3x4 x5  2 x3 1 1 1 1 2 2 1 1 2 0 0 3x3 2x4 x6  5 0 x5 9 7 2 5 2 0 1 2 1 0 0 x6 8 3 3 0 12 0 1 x j  0 j  1,6 2 2 Laäp baûng ñôn hình f  x 1 5 2 3 2 0 3 2 0 0 15
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Xuaát phaùt töø baøi toaùn daïng chính taéc HEÄ AÅN P.A 2 1 1 1 0 0 n x1 x2 x3 x4 x5 x6 f ( x)   c j x j  Min SOÁ C.B j 1 1 x3 9 2 2 1 0 0 1 n x5  0 17 5 4 0 0 1 1  aij x j  bi , i  1, m 1 x4 16 3 3 0 1 0 2  j 1 I   x  0 j  1, n b  0 f  x 25 7 6 0 0 0 3  j i Vì caùc j  0, j neân baøi toaùn coù P.A.T.Ö laø Khoâng laøm maát tính toång quaùt cuûa baøi toaùn, ta Xopt = (0, 0, 9, 16) vaø f(Xopt) = 25. giaû söû caùc bi  0 vaø ma traän heä soá cuûa heä raøng Baøi toaùn treân khoâng coøn phöông aùn toái öu naøo buoäc khoâng chöùa vectô (coät) ñôn vò naøo. khaùc vì khoâng coù j = 0 naøo vôùi xj laø aån khoâng Coäng vaøo moãi raøng buoäc vôùi moät aån giaû töông cô baûn. öù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 BAÛNG ÑÔN HÌNH MÔÛ ROÄNG n m f ( x)   c j x j  M  xig  Min Heä AÅn PA C1 C2 … Cm Cm+1 … Cj … Cn j 1 i 1 Soá C.B CB x1 x2 … xm xm+1 … xj … xn n  g M xn+1 b1 a11 a12 … a1m a1,m+1 … a1j … a1,n  aij x j  xi  bi , i  1, m  II   j 1 M x n+2 b2 a21 a22 … a2m a2,m+1 … a2j … a2,n  x  0, j  1, n; x g  0, i  1, m, M  0 voâcuøng lôùn. … … … … … … … … … … … …  j i M x n+i bi ai1 ai2 … aim ai,m+1 … aij … ai,n Baøi toaùn (I) ñöôïc goïi laø baøi toaùn goác, baøi toaùn … … … … … … … … … … … … M xn+m bm am1 am2 … amm am,m+1 … amj … am,n (II) goïi laø baøi toaùn môû roäng hay baøi toaùn M. f(x) f(x0) 1 2 … m m+1 … j … n Moät phöông aùn cuûa baøi toaùn M coù daïng x   x j , xig  trong ñoù xj goàm n aån thaät vaø xi(g) goàm m aån giaû. Trong ñoù caùc xn+i (i = 1, 2, ..., m) laø caùc aån giaû. 16
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG NHAÄN XEÙT. b) Neáu trong heä aån cô baûn cuûa baøi toaùn M coù Khi thuaät giaûi cuûa baøi toaùn M keát thuùc thì coù hai chöùa aån giaû nhöng giaù trò cuûa chuùng ñeàu baèng tröôøng hôïp sau ñaây coù theå xaûy ra: khoâng thì P.A.T.Ö cuûa baøi toaùn goác laø P.A.T.Ö. [1] Neáu baøi toaùn M (Baøi toaùn II) khoâng coù cuûa baøi toaùn M loaïi boû caùc aån giaû baèng khoâng phöông aùn toái öu thì baøi toaùn goác (Baøi toaùn I) (xem Ví duï 1.18). cuõng khoâng coù phöông aùn toái öu. c) Neáu trong heä aån cô baûn cuûa baøi toaùn M coù [2] Neáu baøi toaùn M (Baøi toaùn II) coù phöông aùn toái moät aån giaû maø giaù trò cuûa chuùng khaùc khoâng thì öu thì coù 3 tröôøng hôïp xaûy ra sau ñaây: baøi toaùn goác khoâng coù P.A.T.Ö. a) Trong heä A.C.B khoâng chöùa aån giaû naøo thì Chuù yù. Neáu haøm muïc tieâu laø f(x)  Max thì heä soá P.A.T.Ö cuûa baøi toaùn M cuõng chính laø P.A.T.Ö caùc aån giaû trong haøm muïc tieâu cuûa baøi toaùn M cuûa baøi toaùn goác (xem Ví duï 1.17). laø (– M), vôùi M > 0 voâ cuøng lôùn (xem Ví duï 1.19). THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG ÑÖA BAØI TOAÙN VEÀ DAÏNG CHUAÅN Ví duï 1.17. (tröôøng hôïp a). Giaûi baøi toaùn QHTT f ( x)  8 x1  6 x2  2 x3  min LAÄP BAÛNG ÑÔN HÌNH 4 x1 4 x2 3 x3  18 j ≤ 0? Ñuùng COÙ xig ? Coù xig  0? Ñuùng 4 x1 3 x2 4 x3  16 P.A.T.Ö Sai Sai Ñuùng KHOÂNG Khoâng x j  0 j  1,3 aij ≤ 0? COÙ COÙ P.A.T.Ö KHOÂNG Nhaân (– 1) vaøo raøng buoäc thöù nhaát, baøi toaùn coù Sai P.A.T.Ö COÙ P.A.T.Ö daïng chính taéc nhö sau Xaùc ñònh phöông aùn môùi f ( x)  8 x1  6 x2  2 x3  min Aån vaøo: Max  j  j 0 KEÁT THUÙC THUAÄT GIAÛI Aån ra: b 4 x1 4 x2 3 x3  18   Min i aij  0 a ij 4 x1 3 x2 4 x3  16 SOÁ BÖÔÙC LAËP BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH LAØ HÖÕU HAÏN xj  0 j  1,3 17
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Ñöa baøi toaùn veà daïng chuaån: HEÄ AÅN P.A 8 6 2 Theâm hai aån giaû x4 ≥ 0 vaø x5 ≥ 0 vaøo laàn löôït vaøo SOÁ C.B x1 x2 x3 raøng buoäc thöù nhaát vaø thöù hai cuûa baøi toaùn M x4 18 4 4 3 Baøi toaùn coù daïng chuaån nhö sau: M x5 16 4 3 4 f  x 34M 8M  8 7 M  6 M  2 f (x)  8x1  6x2  2x3  M (x4  x5 )  Min x4 M 2 0 1 7 4x1 4x2 3x3 x4 18 8 x1 4 1 3 4 1 4x1 3x2 4x3 x5 16 f  x  2M  32 0 M  12 7 M  10 6 x2 2 0 1 7 x j  0 j  1,5 M  0 voâ cuøng lôùn. 8 x1 5 2 1 0 25 4 f  x 8 0 0 94 Ta coù baûng ñôn hình môû roäng Baøi toaùn coù P.A.T.Ö Xopt=(5/2, 2, 0), f(Xopt)= –8. THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Ví duï 1.18. (tröôøng hôïp b). Giaûi baøi toaùn QHTT f ( x )  6 x1  3x2  x3  min Theâm hai aån giaû x5 ≥ 0, x6 ≥ 0 laàn löôït vaøo raøng  2 x1 5 x2  x3  10 buoäc thöù hai vaø raøng buoäc thöù ba.  4x 3 x2 2 x3  16 Ta coù baøi toaùn daïng chuaån nhö sau  1  2x 1 4 x2  x3  8 f (x)  6x1  3x2  x3  M (x5  x6 )  min   x j  0 j  1,3  2x1 5x2 x3 x4  10 Theâm aån phuï x4  0 vaøo raøng buoäc thöù nhaát 4x1 3x2 2x3 x5 f ( x)  6 x1  3 x2  x3  min  16  2 x1 5 x2  x3  x4  10 2x1 4x2 x3 x6  8  4 x1 3 x2 2 x3  16   2 x1 4 x2  x3  8 xj  0 j  1, 6 M  0  Ta coù baûng ñôn hình môû roäng x j 0 j  1, 4  18
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG HEÄ AÅN 6 3 0 1 HEÄ AÅN P.A 6 3 1 0 P.A x1 x2 x3 x4 SOÁ x1 x2 x4 x3 SOÁ C.B C.B 0 x4 10 2 5 1 1 0 x4 2 0 1 0 1 M x5 16 4 3 0 2 M x5 0 0 11 0 0 M x6 8 2 4 0 1 1 x3 8 2 4 1 0 f  x  24M 6 M  6 M  3 3M  1 0 f  x 8 4 11M  1 0 0 0 x4 2 0 1 0 1 P.A.T.Ö cuûa BTM laø x   0, 0, 8, 2, 0, 0  M x5 0 0 11 0 0 vôùi aån giaû x5 = 0 6 x1 4 1 2 1 2 0 P.A.T.Ö cuûa BT goác laø xopt = (0, 0, 8) f  x 24 0 11M  9 2 0 vaø f(xopt) = 8. THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG 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 giaû vaøo x6, x7  0 laàn löôït vaøo raøng f ( x)  2 x1  x2  x3  max buoäc (1) & (3).  4 x1  x2 2 x3  12  2 x Ta coù baøi toaùn daïng chuaån nhö sau  1 2 x2  x3  10  x1 2 x2 1 2 x3  10 f ( x)  2x1  x2  x3  M  x6  x7   max  x j  0  j  1,3 4x1 x2 2x3 x4  x6  12 Theâm 2 aån phuï x4, x5 ≥ 0 vaøo raøng buoäc (1) & (2) 2x1 2x2 x3  x5  10 f ( x)  2 x1  x2  x3  max 1  4 x1  x2 2 x3  x4  12 x1 2x2  x3 x7  10  2 x 2 x2  x3  x5  10 2  1  x1 2 x2 1 2 x3  10 x j  0 j  1,7 M  0  xj  0  j  1,5 Ta coù baûng ñôn hình môû roäng 19
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG BAØI TAÄP CHÖÔNG 1 HEÄ AÅN 2 1 1 0 0 LAÄP MOÂ HÌNH BAØI TOAÙN P.A x1 x2 x3 x5 x4 SOÁ C.B [1] [2] [3] [4] M x6 12 4 1 2 0 1 BAØI TOAÙN QHTT DAÏNG CHÍNH TAÉC 0 x5 10 2 2 1 1 0 [5a] [5b] M x7 10 1  1 2 2 0 0 XAÙC ÑÒNH P.A – P.A.C.B VAØ P.A.T.Ö. f  x  22M 3M  2 3M  1 2 M  1 M 3 0 [6] [7a] [7b] [7c] 1 x3 6 2  1 2 1  1 2 0 GIAÛI BAØI TOAÙN QHTT BAÈNG PP HÌNH HOÏC 0 x5 16 4 3 2 0 1 2 1 [8a] [8b] [8c] M x7 13 0 9 4 0 1 4 0 GIAÛI BAØI TOAÙN QHTT BAÈNG PP ÑÔN HÌNH f  x  6  13M 0 2  4 M 0 1 9 1 2  4M 0 1 [9] [10] [11] [12] 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.Ö. [13] [14] [15] [16] [17] BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 1. Moät xí nghieäp cheá bieán ñoà goã hieän coù 3.000 1.Goïi xj (j=1, 2, 3, 4) laàn löôït laø soá löôïng boä tuû, ñôn vò goã nguyeân lieäu nhoùm I, 5.000 ñôn vò goã boä cöûa, boä sa–loâng vaø boä giöôøng nguû do xí nguyeân lieäu nhoùm II vaø 2.000 ñôn vò goã nguyeân nghieäp saûn xuaát. 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ù vôùi ñònh möùc nguyeân Moâ hình cuûa baøi toaùn lieäu vaø lôïi nhuaän ñöôïc theå hieän trong baûng sau f(x) = 0,5x1 + 0,8x2 + 0,4x3 + 0,6x4  Max Saûn phaåm Vôùi caùc raøng buoäc veà nguyeân lieäu Ñònh möùc Boä tuû Boä cöûa Boä sa-loâng Boä giöôøng nguû Nguyeân lieäu 30x1 + 40x2 + +10x4 ≤ 3000, Goã nhoùm I 30 40 0 10 Goã nhoùm II 10 20 50 60 10x1 + 20x2 + 50x3 + 60x4 ≤ 5000, Goã nhoùm III 10 50 80 20 10x1 + 50x2 + 80x3 + 20x4 ≤ 2000, Lôïi nhuaän (trieäu ñoàng) 0,5 0,8 0,4 0,6 Raøng buoäc caùc aån soá Haõy laäp moâ hình baøi toaùn sao cho xí nghieäp ñaït lôïi nhuaän nhieàu nhaát? xj ≥ 0 , j = 1, 2, 3, 4 20

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.