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

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

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

Thêm vào BST
Báo xấu
94
lượt xem 10
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 2: Bài toán quy hoạch tuyến tính đối ngẫu" cung cấp cho người học các kiến thức: các thành lập bài toán quy hoạch tuyến tính đối ngẫu, các định lý đối ngẫu, giải thuật đơn hình đối ngẫu,... Mời các bạn cùng tham khảo nội dung chi tiết.

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 2 - ThS. Nguyễn Công Trí

  1. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TOAÙN QUY HOAÏCH CHÖÔNG 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU TUYEÁN TÍNH ÑOÁI NGAÃU Muïc ñích vaø yù nghóa  Vôùi baøi toaùn QHTT, baøi toaùn goác, kyù hieäu laø P 1. CAÙCH THAØNH LAÄP BAØI TOAÙN QUY HOAÏCH (Primal), chuùng ta coù theå thieát laäp baøi toaùn QHTT Ths. Nguyeãn Coâng Trí TUYEÁN TÍNH ÑOÁI NGAÃU (Xem) khaùc, baøi toaùn ñoái ngaãu, kyù hieäu laø D (Dual), sao cho töø lôøi giaûi cuûa baøi toaùn naøy ta coù theå thu 2. CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU (Xem) thaäp ñöôïc thoâng tin veà lôøi giaûi cuûa baøi toaùn kia. Copyright 2001 3. THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU (Xem)  Ñeå coù thoâng tin caàn thieát veà baøi toaùn goác, coù theå nghieân cöùu treân baøi toaùn ñoái ngaãu cuûa noù. 4. MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI  Hôn nöõa, khi phaân tích ñoàng thôøi caû hai baøi NGAÃU TRONG BAØI TOAÙN QHTT (Xem) toaùn goác vaø ñoái ngaãu, chuùng ta coù theå ruùt ra Ths. Nguyeãn Coâng Trí caùc keát luaän coù giaù trò veà maët toaùn hoïc laãn veà 5. BAØI TAÄP (Xem) Copyright 2001 maët yù nghóa kinh teá. THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Xeùt baøi toaùn QHTT (P) döôùi daïng chính taéc Goïi g(y) laø haøm muïc tieâu cuûa baøi toaùn (II), ta coù  f P ( x)  c t x  min g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0.  P   Ax  b I   ≤ ctx + yt(b – Ax), vôùi x ≥ 0.  x  0. Vôùi x = (x1, x2,...…, xn)n, b = (b1, b2,...…, bm)m  Neáu x laø P.A cuûa baøi toaùn (I) thì b – Ax = 0 vaø Giaû söû baøi toaùn (P) coù P.A.T.U laø xopt vaø goïi x0 laø g(y) ≤ ctx. Vaäy g(y) laø moät caän döôùi baát kyø cuûa moät P.A cuûa baøi toaùn (P), ta coù ctxopt ≤ ctx0. haøm muïc tieâu. Goïi x = (x1, x2,...…, xn)n, vôùi x ≥ 0 sao cho  Ta tìm caän döôùi lôùn nhaát Max{g(y)}, thaät vaäy Ax – b  0 g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0. Baøi toaùn töông ñöông:  L ( x, y )  c t x  y t  b  Ax   min = min{ctx + ytb – ytAx}, vôùi x ≥ 0.  P   x0  II  = min{ytb + (ct – ytA)x}, vôùi x ≥ 0.  = ytb + min{ (ct – ytA)x}, vôùi x ≥ 0.  y  Rm. 1
  2. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Xeùt 0 khi c  y A  0 t t Ví duï 2.1.  min  c t  y t A  x    t t Baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT sau ñaây x0   khi c  y A  0 Vaäy ta ñöôïc  f ( x)  2 x1 8 x4 6 x5  min  2 x1  x3  x5  4 g(y) = ytb   2 x2  x5  4 Suy ra baøi toaùn ñoái ngaãu coù daïng   x2 2 x3 3 x4  13  g ( y )  y t b  max  g ( y )  y t b  max   x j  0 j  1,5  D    ct  y t A  0   y t A  ct  y  Rm .  y  Rm . laø baøi toaùn  f D ( y )  4 y1 4 y2 13 y3  max    2 y1  2  Hay baøi toaùn töông ñöông  2 y2  y3  0  g ( y )  y t b  max   y1 2 y3  0  D   At y  c  3 y3  8    y  Rm .  y1  y2  6 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Baøi toaùn goác (P) Baøi toaùn ñoái ngaãu (D) Ví duï 2.2. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc Haøm muïnc tieâu Haøm muïc mtieâu caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT Baøi toaùn ñoái ngaãu f P ( x)   c j x j  min f D ( y )   bi yi  max  f ( x)  x1  2 x2  x3  2 x4  min  f D ( y )  y1  3 y2  4 y3  max j 1 i 1  x  x2 2 x3 2 x4  1 y1 3 y2 2 y3  Raøng buoäc thöù i Raøng buoäc thöù j  1 1  3x   1  x  x  3 y  y  3 y  2     2 3 1 2 3 n m  2 x1 3 x2  x3  x4  4 2 y1    aij x j  bi i  1, m  aij yi    c j , j  1, n   y2  y3  1     x j  0 j  1, 2 2 y1  y3  2 j 1 i 1         y  0, y Caùc caëp ñoái ngaãu  1 2 0 AÅn thöù j AÅn thöù I       x1  0, y1 3 y2 2 y3  1 1 xj     0, j  1, n yi    0, i  1, m x2  0, y1  y2 3 y3  2  2     khoâng raøng buoäc   khoâng raøng buoäc x1  x2 2 x3 2 x4  1, y1  0  3 VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 3x1  x2  x3  3, y2  0  4 2
  3. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.3. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc Ví duï 2.4. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT Baøi toaùn ñoái ngaãu f ( x )  4 x1  3 x 2  8 x 3  m in  f ( x)  2 x  x  8 x  max 1 2 3 7 x  f D ( y )  28 y1  10 y2  15 y3  min  x1  4 x2 2 x3  28 1 0 1    2  1 7 y x2   3x  x2 3 x3  10 3 y2 2 y3  2 0 1 2     5   1  1  2 x1  14 y  y2 3 y3  1  x3  3 x2  x3  15  2 y 3 y2  y3  8 xj  0 j  1, 3  xj  0 j  1, 2  1 Caùc raøng buoäc ñoái ngaãu y  0, y Baøi toaùn ñoái ngaãu  3 0 Caùc caëp ñoái ngaãu 1 f D ( y )  2 y1  5 y 2  max x1  0, y1  4 1 x1  0, 7 y1 3 y2 2 y3  2 1  1 0 4 x2  0, y2  3  2 x2  0, 4 y1  y2 3 y3  1  2  0 1   y1    3  x3  0, y1 2 y2  8  3      7 x1 4 x2 2 x3  28, y1  0  3  1 2   y2   8  x1  x3  2, y1  0  4     2 x1 3x2  x3  15, y3  0  4 y j  0; j  1, 2 x2 2 x3  5, y2  0 5 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.5. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc ÑÒNH LYÙ 1. caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT Neáu moät trong hai baøi toaùn ñoái ngaãu nhau coù f ( x )  2 x1  5 x2  max Baøi toaùn ñoái ngaãu f D ( y )  4 y1  3 y 2  8 y 3  m in P.A.T.Ö thì baøi toaùn kia cuõng coù P.A.T.Ö vaø giaù trò  1 0 4  0 1   x1    3   y1  haøm muïc tieâu cuûa chuùng baèng nhau.      1 0 1   2 HEÄ QUAÛ 1.  1 2   x2   8  0   y2    5       1 2  y     3 Ñieàu kieän caàn vaø ñuû ñeå cho caùc baøi toaùn ñoái x j  0; j  1, 2 Raøng buoäc ñoái ngaãu y j  0 j  1, 3 ngaãu nhau coù phöông aùn toái öu laø moãi baøi toaùn x1  0, y1  y3  2 1 coù ít nhaát moät phöông aùn. x2  0, y2  2 y3  5 2 HEÄ QUAÛ 2. x1  4, y1  0  3 Ñieàu kieän caàn vaø ñuû ñeå cho caùc baøi toaùn ñoái x2  3, y2  0 4 ngaãu nhau khoâng coù P.A.T.Ö laø moät baøi toaùn coù x1  2 x2  8, y3  0 5 P.A coøn baøi toaùn kia khoâng coù P.A. 3
  4. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU ÑÒNH LYÙ 2.(ÑÒNH LYÙ ÑOÄ LEÄCH BUØ YEÁU) ÑÒNH LYÙ 3.(ÑÒNH LYÙ ÑOÄ LEÄCH BUØ MAÏNH) Ñieàu kieän caàn vaø ñuû ñeå caëp baøi toaùn ñoái ngaãu Neáu caëp baøi toaùn ñoái ngaãu nhau coù P.A.T.Ö. thì nhau coù P.A.T.Ö. laø trong caëp raøng buoäc ñoái toàn taïi moät caëp phöông aùn sao cho trong caùc ngaãu, neáu raøng buoäc naøy xaûy ra vôùi daáu baát caëp ñoái ngaãu, neáu raøng buoäc naøy xaûy ra vôùi daáu ñaúng thöùc ngaët (“>” hoaëc “ 0 thì a ij yiopt  c j  Neáu xjopt = 0 thì toàn taïi  aij yiopt   c j n   ,  i 1 n i 1    Neáu  aij x opt thì toà n taï i y opt  0 (> hoaëc
  5. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.7. Cho baøi toaùn QHTT Caùc caëp raøng buoäc ñoái ngaãu f ( x )  2 x1  2 x2  x3  4 x 4  max x1 ≥ 0 vaø 5y1 – 3y2 + 4y3 ≥ 2 (1) 5 x1  x2  x3  6 x4  50 x2 ≥ 0 vaø y1 ≥ 2 (2)  3 x1  x3  2 x4  16 x3 ≥ 0 vaø y1 + y2 + 3y3 ≥ 1 (3) 4 x1  3 x3  x4  23 x4 ≥ 0 vaø 6y1 + 2y2 + y3 ≥ 4 (4) xj  0 j  1, 4 -3x1 + x3 + 2x4 ≥ 16 vaø y2 ≤ 0 (5) Coù P.A.T.Ö laø xopt = (0,14, 6, 5) vaø f(xopt) = 54. Haõy 4x1 + 3x3 + x4 ≤ 23 vaø y3 ≥ 0 (6) tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu. Thay xopt = (0, 14, 6, 5) vaøo caùc raøng buoäc Baøi toaùn ñoái ngaãu Töø (2): x2 = 14 > 0  y1 = 2.  f D ( y )  5 0 y1  1 6 y2  2 3 y 3  m in  Töø (3): x3= 6 > 0  y1 + y2 + 3y3 = 1  5 y1  3 y 2  4 y 3  2 Töø (4): x4= 5 > 0  6y1 + 2y2 + y3 = 4  y1  2  y1  y 2  3 y 3  1 Giaûi heä phöông trình treân, ta coù y1 = 2; y2 = -23/5;   6 y1  2 y 2  y 3  4 y3 = 6/5. Vaäy, P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø  yopt= (2, -23/5, 6/5) vaø fD(yopt) = 54.  y2  0; y 3  0 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.8. Cho baøi toaùn QHTT 1. Kieåm tra tröïc tieáp, ta thaáy X, Y, vaø T laø P.A cuûa  f ( x)   x1  2 x2  x3  Max  baøi toaùn. Vì Z khoâng thoûa maõn caùc raøng buoäc x1 3 x2  x4  5  neân Z khoâng laø P.A cuûa baøi toaùn.  x1  x2  3  2. Baøi toaùn ñoái ngaãu  3x1  x3  x4  2  f D ( y )  5 y1  3 y2  2 y3  min  x j  0 j  1, 4 y1  y2 3 y3  1 Xeùt caùc vectô sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), 3 y1  y2  2 Z = (-4, 2, 0, 10) vaø T = (1, 2, 1, 2). Vectô naøo laø P.A.T.Ö. cuûa baøi toaùn? y3  1 Caùch giaûi.  y1  y3  0 1. Kieåm tra caùc vectô coù phaûi laø P.A hay khoâng? y1  0; y2  0; y3  0 2. Vieát baøi toaùn ñoái ngaãu, 3. Kieåm tra caùc P.A coù phaûi laø P.A.T.Ö.? Ta coù 7 caëp raøng buoäc ñoái ngaãu 5
  6. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU x1 ≥ 0 vaø y1 + y2 – 3y3 ≥ -1 (1) x2 ≥ 0 vaø 3y1 + y2 ≥ 2 (2) Deã daøng kieåm tra vectô X*= (0, 2, 1) thoûa caùc x3 ≥ 0 vaø y3 ≥ 1 (3) raøng buoäc cuûa baøi toaùn ñoái ngaãu. x4 ≥ 0 vaø – y1 + y3 ≥ 0 (4) Hôn nöõa, fD(X*)= f(X)= 8 neân X laø P.A.T.Ö. cuûa x1 + 3x2 – x4 ≤ 5 vaø y1 ≥ 0 (5) baøi toaùn goác. x1 + x2 ≤ 3 vaø y2 ≥ 0 (6)  Do Y = (2, 1, 8, 0) laø P.A cuûa baøi toaùn goác vaø -3x1 + x3 + x4 ≤ 2 vaø y3 ≥ 0 (7) 3. Kieåm tra X, Y, T laø P.A.T.Ö f(X) = f(Y)= 8 neân Y cuõng laø P.A.T.Ö.  Giaû söû X = (3, 0, 11, 0) laø P.A.T.Ö cuûa baøi toaùn.  Vôùi T = (1, 2, 1, 2), ta coù f(T)= 4  fmax = 8 Töø (1): x1 = 3 > 0  y1 + y2 – 3y3 = -1 Vaäy T khoâng phaûi laø P.A.T.Ö. maø T chæ laø phöông Töø (3): x3=11 > 0  y3 = 1 aùn cuûa baøi toaùn. Töø (5): 3 + 0 + 0 + 0 = 3 < 5  y1 = 0 Giaûi heä phöông trình, ta ñöôïc X*= (0, 2, 1). AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.9. Giaûi baøi toaùn QHTT f ( x )  10 x1  8 x2  19 x3  min Ñöa baøi toaùn veà daïng chính taéc baèng caùch theâm 3 aån phuï y4 ≥ 0, y5 ≥ 0, y6 ≥ 0  2 1 1   x1   6   3 0 2  x    2  f D ( y )  6 y1  2 y2  5 y3  max   2     1 2 5  x   5   2 3 1   y1   y4  10    3     1 0 2 y    y    8  xj  0 j  1,3   2   5    Baøi toaùn ñoái ngaãu f D ( y )  6 y1  2 y2  5 y3  max  1 2 5   y   y  19    3   6     2 3 1   y1  10   1 0 2 y    8  yj  0 j  1,6   2     1 2 5   y  19  Ta thaáy baøi toaùn cuõng coù daïng chuaån.   3    Söû duïng thuaät giaûi ñôn hình Ví duï 2.10 yj  0 j  1,3 6
  7. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU HEÄ AÅN P.A 6 2 5 0 0 0 HEÄ AÅN P.A 6 2 5 0 0 0 y1 y2 y3 y4 y5 y6 SOÁ C.B y1 y2 y3 y4 y5 y6 SOÁ C.B 0 y4 10 2 3 1 1 0 0 6 y1 4 1 2 0 3 2 1 2 0 0 y5 8 1 0 2 0 1 0 5 y3 2 0 1 1 1 3 2 3 0 0 y6 19 1 2 5 0 0 0 y6 5 0 5 0 1 3 1 1 f  x 0 6 2 5 0 0 0 f  x  34 0 5 0 7 3 4 3 0 GHI CHUÙ 6 y1 5 1 32 1 2 1 2 0 0 Baøi toaùn coù P.A.T.Ö yopt=(4, 0, 2) vaø f(yopt)= 34. 0 y5 3 0 3 2 3 2 1 2 1 0 P.A.T.Ö cuûa baøi toaùn goác laø 0 y6 14 0 12 9 2 1 2 0 1  x1   4  b4  x1  7 3  0  7 3   xopt   x2  5  b5  xopt   x2  4 3  0  4 3 f  x 30 0 7 2 3 0 0 x    b x  0  0  0  3 6 6  3 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Caùch 2: duøng ñònh lyù ñoái ngaãu GHI CHUÙ. Chuùng ta cuõng coù theå söû duïng quy taéc x1 ≥ 0 vaø 2y1 + 3y2 + y3 ≤ 10 (1) sau ñaây ñeå tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu: x2 ≥ 0 vaø y1 + 2y3 ≤ 8 (2)  y1  1  c1  y   c x3 ≥ 0 vaø y1 + 2y2 + 5y3 ≤ 19 (3)  yopt  2 2 2 2x1 + x2 + x3 ≥ 6 vaø y1 ≥ 0 (4)   3x1 + 2x3 ≥ 2 vaø y2 ≥ 0 (5)  ym   m  cm x1 + 2x2+ 5x3 ≥ 5 vaø y3 ≥ 0 (6) Vôùi caùc aån cô baûn xj (j = 1, 2, ...…, m) trong P.A.C.B Ta coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu yopt= (4,0,2) ñaàu tieân laäp thaønh ma traän ñôn vò caáp m töông Töø (3): 4 +20 + 52 = 14 < 19  x3 = 0. öùng vôùi caùc j trong baûng cuoái cuøng. Töø (4): y1 = 4 > 0  2x1 + x2 + x3 = 6 Trong Ví duï 2.9, aån cô baûn ñaàu tieân cuûa baøi toaùn Töø (6): y3= 2 > 0  x1 + 2x2 + 5x3 = 5 ñoái ngaãu laø y4, y5 vaø y6 thì P.A.T.Ö cuûa baøi toaùn Giaûi heä phöông trình, ta coù PA.T.Ö cuûa baøi toaùn goác (ñoái ngaãu cuûa baøi toaùn ñoái ngaãu) laø goác laø xopt = (7/3, 4/3, 0) vaø f(xopt) = 34. Xopt = (7/3, 4/3, 0) vaø f(Xopt) = 34. 7
  8. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU  Do Lemke G.E ñeà xuaát naêm 1954. Ñaây laø thuaät LAÄP BAÛNG ÑÔN HÌNH ÑOÁI NGAÃU giaûi ñôn hình ñöôïc aùp duïng vaøo baøi toaùn ñoái ngaãu nhöng ñeå tìm P.A.T.Ö cho baøi toaùn goác. Ñuùng Ñuùng bi ≥ 0,i? j ≤ 0,j? P.A.T.Ö  Thuaät giaûi ñôn hình ñoái ngaãu xuaát phaùt töø moät Sai Sai “phöông aùn giaû” thoûa caùc raøng buoäc chính cuûa Ñuùng THUAÄT GIAÛI KEÁT THUÙC aij  0,j? baøi toaùn (nghieäm ñuùng Ax = b) nhöng khoâng ÑÔN HÌNH THUAÄT GIAÛI Sai thoaû ñieàu kieän raøng buoäc veà daáu (x  0), nghóa laø XAÙC ÑÒNH PHÖÔNG AÙN MÔÙI baûng ñôn hình ñaàu tieân khoâng coù phaàn töû döông BAØI TOAÙN Aån ra : Min bi  xi bi  0 KHOÂNG COÙ P.A.T.Ö trong doøng muïc tieâu (doøng cuoái) nhöng laïi coù j phaàn töû aâm trong coät phöông aùn. Aån vaøo : Min  xj aij 0 aij  Thuaät giaûi naøy thöôøng ñöôïc aùp duïng khi chöa bieát P.A.C.B naøo cuûa baøi toaùn goác nhöng laïi coù BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH SOÁ BÖÔÙC LAËP saün moät P.A.C.B cuûa baøi toaùn ñoái ngaãu. LAØ HÖÕU HAÏN THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Ví duï 2.10. Giaûi baøi toaùn QHTT trong Ví duï 2.9 Heä AÅn P.A 10 8 19 0 0 0 baèng thuaät giaûi ñôn hình ñoái ngaãu. soá C.B x1 x2 x3 x4 x5 x6 Ñöa baøi toaùn veà daïng chính taéc, roài sau ñoù nhaân (–1) cho caùc raøng buoäc ñaúng thöùc, ta coù 0 x4 –6 –2 –1 –1 1 0 0 baøi toaùn daïng chính taéc nhö sau 0 x5 –2 –3 0 –2 0 1 0  f ( x )  10 x1  8 x2  19 x3  min 0 x6 –5 –1 –2 –5 0 0 1  2 x1  x2  x3  x4  6  f(x) 0 –10 –8 –19 0 0 0  3x1 2 x3  x5  2  10 x1 3 1 ½ ½ –½ 0 0   x1 2 x2 5 x3  x6  5 0 x5 7 0 3/2 –½ –3/2 1 0   x j  0, j  1, 6 0 x6 –2 0 –3/2 9/2 –½ 0 1 Xuaát phaùt töø phöông aùn giaû X = (0,0,0,–6,–2,–5). f(x) 30 0 –3 –14 –5 0 0 Ta coù baûng ñôn hình ñoái ngaãu nhö sau 8
  9. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Heä AÅn P.A 10 8 19 0 0 0 GHI CHUÙ. Ñoái vôùi thuaät giaûi ñôn hình ñoái ngaãu, soá C.B x1 x2 x3 x4 x5 x6 ñeå tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu Yopt, ta coù bieåu thöùc sau  y1  1  c1 10 x1 7/3 1 0 2 –2/3 0 1/3  y    c  0 x5 5 0 0 4 –2 1 1 yopt   2 2 2   8 x3 4/3 0 1 –3 1/3 0 –2/3  ym   m  cm f(x) 34 0 0 –23 –4 0 –2 Trong Ví duï 2.10, aån cô baûn ñaàu tieân cuûa baøi toaùn ñoái ngaãu laø x4, x5 vaø x6 thì Vaäy, P.A.T.Ö cuûa baøi toaùn laø xopt = (7/3, 4/3, 0)  y1   4  c4  y1  (4)  0  4 vaø f(xopt) = 34.  yopt   y2  5  c5    y2  0  0  0  y    c  y  ( 2)  0  2  3 6 6  3 P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø Yopt = (4, 0, 2) vaø f*(Yopt) = 34. THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Ví duï 2.11. Heä AÅn P.A 2 –4 1 –1 2 0 0 Duøng thuaät giaûi ñôn hình ñoái ngaãu ñeå giaûi baøi soá C.B x1 x2 x3 x4 x5 x6 x7 toaùn quy hoaïch tuyeán tính sau ñaây 2 x1 –2 1 –2 0 0 –2 0 0  f ( x)  2 x1  4 x2  x3  x4  2 x5  Min –1 x4 –4 0 4 1 1 –1 0 0  0 x6 2 0 0 2 0 –1 1 0  x1 2 x2 2 x5  2  4 x2  x3  x4  x5  4 0 x7 6 0 1 1 0 4 0 1  2 x3  x5  x6  2 f(x) 0 0 –4 –2 0 –5 0 0 Do a4j  0,   x2  x3 4 x5  x7  6 2 x1 6 1 –10 –2 –2 0 0 0 j = 1,..., 7  –1 x5 4 0 –4 –1 –1 1 0 0 neân baøi  x j  0, j  1, 7 toaùn treân 0 x6 6 0 –4 1 –1 0 1 0 khoâng coù Xuaát phaùt töø phöông aùn giaû X = (–2,0,0,–4,0,2,6). 0 x7 –10 0 17 5 4 0 0 1 P.A.T.Ö. Ta coù baûng ñôn hình ñoái ngaãu f(x) 20 0 –24 –7 –5 0 0 0 9
  10. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Ví duï 2.12. 1. TÌM PHÖÔNG AÙN TOÁI ÖU MÔÙI KHI COÙ a) Duøng thuaät giaûi ñôn hình ñoái ngaãu ñeå giaûi baøi THEÂM RAØNG BUOÄC VAØO BAØI TOAÙN (XEM) toaùn quy hoaïch tuyeán tính sau ñaây 2. TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ  f ( x)  15 x1  12 x2  10 x3  Min  3 x1 4 x2 2 x3  160 PHÖÔNG TRÌNH TUYEÁN TÍNH BAÈNG THUAÄT   x1 2 x2 3 x3  140 GIAÛI ÑÔN HÌNH MÔÛ ROÄNG (XEM)   x j  0, j  1, 3 3. YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN QUY  b) Neáu theâm moät raøng buoäc nöõa x1 + x2 + x3  60 HOAÏCH TUYEÁN TÍNH ÑOÁI NGAÃU (XEM) vaøo baøi toaùn treân, tìm phöông aùn toái öu cuûa baøi toaùn môùi. MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Heä AÅn P.A 15 12 10 0 0 Ñöa baøi toaùn veà daïng chính taéc, roài sau ñoù Soá C.B x1 x2 x3 x4 x5 nhaân (–1) cho caùc raøng buoäc ñaúng thöùc, ta coù 0 x4 –160 –3 –4 –2 1 0 baøi toaùn daïng chính taéc nhö sau 0 x5 –140 –1 –2 –3 0 1 f(x) 0 –15 –12 –10 0 0  f ( x)  15 x1  12 x2  10 x3  Min  12 x2 40 ¾ 1 ½ –¼ 0  3 x1 4 x2 2 x3  x4  160  0 x5 –60 ½ 0 –2 –½ 1  x1 2 x2 3 x3  x5  140 f(x) 480 –6 0 –4 –3 0   x j  0, j  1,5 12 x2 25 7/8 1 0 –3/8 ¼  a) Xuaát phaùt töø phöông aùn giaû X = (0, 0, 0, –160, 10 x3 30 –¼ 0 1 ¼ –½ –140. Ta coù baûng ñôn hình ñoái ngaãu f(x) 600 –7 0 0 –2 –2 P.A.T.Ö laø xopt = (0, 25, 30) vaø f(xopt) = 600. 10
  11. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Heä AÅn P.A 15 12 10 0 0 0 b) Do xopt = (0, 25, 30) khoâng thoûa raøng buoäc x1 soá C.B x1 x2 x3 x4 x5 x6 + x2 + x3  60 neân xopt khoâng phaûi laø phöông aùn cuûa baøi toaùn môùi. Ñeå xöû lyù raøng buoäc môùi naøy, 12 x2 25 7/8 1 0 –3/8 ¼ 0 ta ñöa raøng buoäc baát ñaúng thöùc veà raøng buoäc 10 x3 30 –¼ 0 1 ¼ –½ 0 ñaúng thöùc baèng caùch theâm aån phuï x6  0, ta ñöôïc –x1 – x2 – x3 + x6 = –60. 0 x6 –60 –1 –1 –1 0 0 1 Söû duïng baûng cuoái cuøng trong caâu a) vaø ñöa f(x) 600 –7 0 0 –2 –2 0 raøng buoäc môùi –x1 – x2 – x3 + x6 = –60 vaøo baûng 12 x2 25 7/8 1 0 –3/8 ¼ 0 treân. Löu yù aån x6 laø aån cô baûn trong baøi toaùn môùi, coøn x4 vaø x5 laø aån cô baûn trong baøi toaùn cuõ 10 x3 30 –¼ 0 1 ¼ –½ 0 neân trong ma traän heä soá cuûa baøi toaùn môùi ta 0 x6 –5 –3/8 0 0 –1/8 –¼ 1 coäng doøng 1 vaø doøng 2 vaøo doøng 3 ñeå vectô f(x) 600 –7 0 0 –2 –2 0 coät öùng vôùi x4 vaø x5 laø caùc vectô ñôn vò. MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU TÌM NGHIEÄM KHOÂNG AÂM CUÛA Heä AÅn 15 12 10 0 0 0 HEÄ PHÖÔNG TRÌNH TUYEÁN TÍNH P.A Tìm nghieäm khoâng aâm cuûa heä phöông trình soá C.B x1 x2 x3 x4 x5 x6 tuyeán tính AX = b, X  0 (1), trong ñoù A laø ma 12 x2 20 ½ 1 0 –½ 0 1 traän mn, bm coù theå quy m veà giaûi baøi toaùn quy 10 x3 40 ½ 0 1 ½ 0 –2 hoaïch tuyeán tính f  x   M  x gj  min 0 x5 20 3/2 0 0 ½ 1 –4 j 1 AX  X g  b 2 f(x) 640 –4 0 0 –1 0 –8 g X  0, X  0, M  0 P.A.T.Ö laø x/opt = (0, 20, 40) vaø f(x/opt) = 640.  Baøi toaùn (2) luoân luoân coù P.A.T.Ö vì (0,b) laø moät P.A vaø haøm muïc tieâu bò chaën [f(x)  0].  Giaû söû P.A.T.Ö cuûa baøi toaùn treân laø (xopt, xgopt), neáu xgopt = 0, j thì xopt laø nghieäm cuûa baøi toaùn (1). Ngöôïc laïi neáu toàn taïi xgj  0 thì baøi toaùn (1) voâ nghieäm. 11
  12. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ PHÖÔNG TRÌNH TUYEÁN TÍNH YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.1.Tìm nghieäm khoâng aâm cuûa heä phöông Xeùt baøi toaùn goác laø baøi toaùn khaåu phaàn thöùc aên trình tuyeán tính 2 x1 3 x2  x3  7  Thöùc aên Möùc  x1 2 x2 4 x3  9 Chaát dinh  3x 1 2 ... j ... n dinh döôõng döôõng (%)  1  x2 2 x3  4 toái thieåu Ta coù theå quy baøi toaùn treân veà baøi toaùn QHTT 1 a11 a12 ... a1j ... a1n b1  f ( x)  M  x4  x5  x6   Min  2 a21 a22 ... a2j ... a2n b2  2 x1 3x2  x3  x4  7  ... ... ... ... ... ... ... ...  x1  2 x2 4 x3  x5  9  i ai1 ai2 ... aij ... ain bi 3x1  x2 2 x3  x6  4  ... ... ... ... ... ... ... ...  x j  0, j  1, 6 m am1 am2 ... amj ... amn bm Giaûi baøi toaùn treân, ta ñöôïc P.A.T.Ư laø (xopt, xgopt) = (3, 1, 2, 0, 0, 0). Vaäy nghieäm khoâng aâm cuûa heä Giaù moät ñôn c1 c2 ... cj ... cn phöông trình tuyeán tính treân laø x = (3, 1, 2). vò thöùc aên YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU Goïi xj (j = 1, 2, ..., n) laø soá ñôn vò thöùc aên trong Goïi yi laø giaù baùn moät vieân thuoác boå coù chöùa moãi böûa, ta coù moâ hình baøi toaùn QHTT nhö sau chaát dinh döôõng i (i = 1, 2, ..., m).  f  x   c1 x1 c2 x2    cn xn  min Ngöôøi chaên nuoâi seõ phaûi löïa choïn:   Mua thuoác boå, neáu a1jy1 + a2jy2 +... + anjyn < cj.  ai1 x1  ai 2 x2    ain xn  bi , i  1, m  Vì giaù thuoác boå reû hôn vaø luùc naøy xj = 0 (ñònh lyù  x j  0, j  1, n ñoä leäch buø yeáu). Baøi toaùn ñoái ngaãu  Mua thöùc aên, theo ñònh lyù ñoä leäch buø yeáu,  f D  y   b1 y1 b2 y2   bm ym  max neáu yi > 0 thì ai1x1 + ai2x2 + … + ainxn = bi,   a1 j y1  a2 j y2    amj ym  cj , j  1, n Nghóa laø, neáu giaù moät vieân thuoác boå khaù cao thì  yi  0, i  1, m ngöôøi chaên nuoâi seõ mua caùc loaïi thöùc aên sao  cho thoaû nhu caàu toái thieåu cuûa chaát dinh döôõng. Chaát dinh döôõng thay theá: nhaø saûn xuaát thuoác Vaäy, khi phaân tích caëp baøi toaùn ñoái ngaãu nhau boå töông öùng vôùi caùc chaát dinh döôõng treân. chính laø phaân tích tính T.Ö cuûa töøng baøi toaùn. 12
  13. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 1.a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT  f ( x)  4 x1 4 x2 3x3 2 x4  min LAÄP BAØI TOAÙN ÑOÁI NGAÃU   x1 2 x2  x3  x4  1 [1a] [1b] [2]  2 x1  x2 3x3  x4  8 Th.s Nguyeãn Coâng Trí    x1 5 x2  x3 3 x4  4 SÖÛ DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU  x1  0, x3  0, x4  0 Baøi toaùn ñoái ngaãu [3] Copyright [4] [5] 2001 [6]  f D ( y )   y1   y1 8 y2 2 y2 4 y3  y3  max  4 PHÖÔNG PHAÙP ÑÔN HÌNH ÑOÁI NGAÃU  2 y1  y2 5 y3  4   y1 3 y2  y3  3 [7a] [7b]   y1  y2 3 y3  2  y2  0, y3  0 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 1.b) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT 2. Chöùng minh baøi toaùn QHTT sau ñaây truøng vôùi  f ( x)  2 x1 3x2 4 x3 5 x4  max  baøi toaùn ñoái ngaãu cuûa noù (Baøi toaùn töï ñoái ngaãu).  x1  x2 2 x3 2 x4  10   x1 2 x2  x3  x4  8  f ( x)  x1  x2  x3  min    x2  x3  1 x1  x2 2 x3  x4  9    x2  0, x3  0, x4  0  x1  x3  1 Baøi toaùn ñoái ngaãu   x1  x2  1  fD ( y)  10 y1 8 y2 9 y3  min   y1  y2  y3  2  x1  0, x2  0 x3  0,   y1 2 y2  y3  3   2 y1  y2 2 y3  4  2 y1  y2  y3  5   y1  0, y3  0 13
  14. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 3. Cho baøi toaùn QHTT sau ñaây: a) Baøi toaùn ñoái ngaãu f D ( y)  y1  3y2  3y3  min b) Giaûi baøi toaùn goác, y1  2 f ( x )  2 x1  4 x2  x3  x4  max ta ñöôïc P.A.T.Ö laø xopt = 3y1 5y2  y3  4 x1 3 x 2  x4  1 (1, 0, 3/4, 0), fmax= 11/4 4 y3  1 5 x 2 2 x4  3 Caùc caëp ñoái ngaãu y1 2 y2  y3  1 x1  0 vaø y1  2 (1) y2  0 x2 4 x3  x4  3 x2  0 vaø 3y1 – 5y2 + y3  4 (2) xj  0 j  1, 4 x3  0 vaø + 4y3  1 (3) a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. x4  0 vaø y1 – 2y2 + y3  1 (4) b) Giaûi baøi toaùn goác, suy ra lôøi giaûi cuûa baøi -5x2 – 2x4 ≤ 3 vaø y2  0 (5) Giaûi hpt (1), (3) vaø (5), ta ñöôïc toaùn ñoái ngaãu. yopt = (2, 0, 1/4) vaø fD(yopt)= 11/4 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 5. Cho baøi toaùn QHTT 4. Cho baøi toaùn QHTT sau ñaây: f ( x)  5x1  9 x2  15x3  7x4  6 x5  min f ( x )  12 x1  27 x2  6 x3  min x1 3x2  x3  x4  x5  1 2 x1 3 x 2 2 x3  12 4 x1  x3 2 x4  x5  4 x1 3 x 2  x3  6  x1  x2  x3 2 x5  1 6 x1 9 x 2 2 x3  24 x j  0 j  2,5 a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. xj  0 j  1,3 b) Phaân tích caùc tính chaát (P.A.C.B suy bieán hay a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. khoâng suy bieán) cuûa vectô X = (0, 1, 0, 2, 0). b) Giaûi baøi toaùn ñoái ngaãu, suy ra lôøi giaûi cuûa c) Cho bieát X laø P.A.T.Ö cuûa baøi toaùn goác vaø baøi toaùn goác. f(X) = 5. Tìm P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu. 14
  15. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 a) Baøi toaùn ñoái ngaãu fD ( y)  y1  4y2  y3  max 6. Cho baøi toaùn QHTT b) Kieåm tra tröïc tieáp, ta y1 4y2  y3  5 f ( x)  3 x1  7 x2  x3  2 x4  max thaáy X = (0, 1, 0, 2, 0) laø P.A 3y1  y3  9 2 x1 3 x2  x3 2 x4  30 2 x1 2 x2 3 x3  60 vaø X thoûa 5 raøng buoäc chaët,  y1  y2  y3  15  y1 2y2  7 2 x1 2 x2 3 x3 4 x4  32 deã daøng kieåm tra hpt raøng y1  y2 2 y3  6 xj  0 j  1, 4 buoäc coù haïng khaùc 5, y1  0, y3  0 Cho caùc vectô: neân X khoâng laø P.A.C.B. X = (-1, 2, 3, 4); Y = (0, 2, 1, 3); Z = (0, 0, 0, 8), T = c) Chæ ra 6 caëp ñoái ngaãu, töø ñoù aùp duïng ñònh lyù (14, 0, 0, 1); S = (18, 2, 0, 0) ñoái ngaãu, ta coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø Trong caùc vectô treân, vectô naøo laø phöông aùn toái Yopt = [(y3 – 9)/3, (y3 + 12)/6, y3], vôùi y3 ≥ 0, y1 ≤ 0. öu cuûa baøi toaùn? Haõy giaûi thích. BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 1. Kieåm tra tröïc tieáp X, Y khoâng phaûi laø phöông 3. Kieåm tra tính toái öu cuûa caùc phöông aùn aùn. Caùc vectô Z, T, S laø caùc phöông aùn vì chuùng  Xeùt phöông aùn Z = (0, 0, 0, 8), giaû söû Z laø thoûa caùc raøng buoäc cuûa baøi toaùn. P.A.T.Ö. cuûa baøi toaùn goác, ta coù f(Z) = –16. 2. Baøi toaùn ñoái ngaãu Töø (4): z4 = 8  2 y1 + 4y3 = –2 Caùc caëpf Draø ( yn) g 30cy1ñoái 60  buoä y2 u 32 y3 ngaã  min Töø (5): 2x1 – 3x2 – x3 + 2x4 = 16 < 30  y1 = 0  Töø (6): 2x1 – 2x2 + 3x3 = 0 < 60  y2 = 0  2y1 + 2y2 +1 2y3 ≥ 23 2 y3 x1 ≥ 0 vaø 2 y 2 y  (1) 3  –3y – 2y3–y1 2y ≥2 y–7 2 y3  7 P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu seõ laø Z*= (0, 0,–½), x2 ≥ 0 vaø 1 2 3 2 (2) y1 3 y2 3 y3 nhöng Z* khoâng thoûa raøng buoäc cuûa baøi toaùn ñoái x3 ≥ 0 vaø – y1 + 3y 2 – 3y3 ≥ 1  (3) 1  2 y1 4 y3  2 ngaãu neân Z* khoâng theå laø P.A.T.Ö. Vaäy, Z khoâng x4 ≥ 0 vaø 2 y1 + 4y3 ≥ –2 (4) theå laø P.A.T.Ö. cuûa baøi toaùn goác.  y1  0, y2  0 2x1 – 3x2 – x3 + 2x4 ≤ 30 vaø y1 ≥ 0 (5)  Töông töï, giaû söû T = (14, 0, 0, 1) laø P.A.T.Ö. cuûa 2x1 – 2x2 + 3x3 ≤ 60 vaø y2 ≥ 0 (6) baøi toaùn goác ta coù f(T) = 40. 15
  16. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 Töø (1): t1 = 14  2y1 + 2y2 + 2y3 = 3 7. a) Duøng PPÑHÑN giaûi baøi toaùn QHTT sau ñaây, Töø (4): t4 = 1  2 y1 + 4y3 = –2 töø ñoù suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu Töø (6): 2x1 – 2x2 + 3x3 = 28 < 60  y2 = 0  f ( x)  x1 3 x2  x3 2 x4  min  x1  x2 2 x3 2 x4  10 Giaûi heä phöông trình treân, ta coù P.A.T.Ö. cuûa baøi  toaùn ñoái ngaãu seõ laø T*= (4, 0,–5/2).   x1 2 x2  x3  x4  8  x1  x2  x3  x4  9 Deã daøng kieåm tra T* thoûa caùc raøng buoäc cuûa baøi  toaùn ñoái ngaãu neân T* laø P.A.T.Ö. cuûa baøi toaùn ñoái  x1  0, x2  0, x3  0, x4  0 ngaãu. Hôn nöõa, fD(T*) = f(T) = 40 Vaäy, T laø P.A.T.Ö. cuûa baøi toaùn goác.  Xeùt phöông aùn S = (18, 2, 0, 0), ta coù f(S) = 40 = f(T). Vaäy, S laø P.A.T.Ö. cuûa baøi toaùn goác. BAØI TAÄP CHÖÔNG 2 7. b) Duøng PPÑHÑN giaûi baøi toaùn QHTT sau ñaây, töø ñoù suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu  f ( x)  2 x1  x2 6 x3 3x4  max  x1  x2  1    x2  x3  4   x2  x4  2   x1  0, x2  0, x3  0, x4  0 16
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2