Xem mẫu

  1. BỐ CUC BAI GIANG ̣ ̀ ̉ 1.Cac ví dụ dân đên bai toan Quy hoach tuyên ́ ̃ ́ ̀ ́ ̣ ́ ́ tinh: 1.1 Lâp kế hoach san xuât: ̣ ̣ ̉ ́ 1.2 Phân bổ vôn đâu tư: ́ ̀ ̣ ̃ 2. Đinh nghia:
  2. 1. Cac ví dụ dân đên bai toan Quy hoach tuyên ́ ̃ ́ ̀ ́ ̣ ́ ́ tinh (QHTT): 1.1 Lâp kế hoach san xuât: ̣ ̣ ̉ ́ ̉ ̉ san phâm S1 S2 S3 Số lượng nguyên Chi phí liêu hiên có ̣ ̣ ̣ Nguyên liêu 1 (N1) 4 5 3 15.000 ̣ Nguyên liêu 2 (N2) 2 4 3 12.000 ̣ Nguyên liêu 3 (N3) 3 6 4 10.000 Lao đông ̣ 10 7 6 500.000 Giả sử răng san phâm san xuât ra đêu có thể tiêu thụ được ̀ ̉ ̉ ̉ ́ ̀ hêt với lợi nhuân khi ban môt đơn vị san phâm S1, S2, S3 ́ ̣ ́ ̣ ̉ ̉ tương ứng là 5000:10000:7000 (đông). Yêu câu lâp kế hoach ̀ ̀ ̣ ̣ san xuât tôi ưu. ̉ ́ ́
  3. Goi xj là số san phâm cua Sj (j = 1,2, 3) cần san xuât ̣ ̉ ̉ ̉ ̉ ́ (xj ≥ 0, j = 1, 2, 3.) Theo kế hoach san xuât phai tim lượng nguyên liêu tiêu ̣ ̉ ́ ̉ ̀ ̣ ̀ hao la: N1: 4 x1 + 5 x2 + 3 x3 ≤ 15000 N2: 2 x1 + 4 x2 + 3 x3 ≤ 12000 N3: 3 x1 + 6 x2 + 4 x3 ≤ 10000 Số phut cân sử dung: ́ ̀ ̣ 10 x1 + 7 x2 + 6 x3 ≤ 500.000 Tông lợi nhuân theo kế hoach san xuât la: ̉ ̣ ̣ ̉ ́ ̀ 5000 x1 + 10000 x2 + 7000 x3 Yêu cầu tối ưu 5000 x + 10000 x + 7000 x → max là: 1 2 3
  4. ̀ ̀ ́ Mô hinh bai toan: ̀ Tim x = (x1, x2, x3) sao cho: f ( x ) = 5000 x + 10000 x + 7000 x → max 1 2 3 4 x + 5 x + 3x ≤ 15000  1 2 3 2 x + 4 x + 3x ≤ 12000  1 2 3  3x1 + 6 x2 + 4 x3 ≤ 10000  10 x1 + 7 x2 + 6 x3 ≤ 500000   x j ≥ 0, j = 1, 2,3 
  5. Tông quat: ta có bai toan lâp kế hoach san xuât ̉ ́ ̀ ́ ̣ ̣ ̉ ́ dưới dang bang số liêu sau đây: ̣ ̉ ̣ Yêu tố ́ Số lượng ̉ ̉ San phâm san xuât hiên có ̉ ́ ̣ S1 S2 … Sn Y1 b1 a11 a12 … a1n Y2 b2 a21 a22 … a2n … … … … … … … … … … … … Ym bm am1 am2 … am n Lợi nhuân đơn vị ̣ c1 c2 … cn
  6. ̀ Mô hinh: ̀ Tim x = (x1, x2,…, xn) sao cho: n f = ∑ c j x j → max j =1 n ∑ aij x j ≤ bi , i = 1,..., m j =1 x j ≥ 0, j = 1,..., n
  7. 2.2 Phân bổ vôn đâu tư: ́ ̀ Môt nhà đâu tư có 4 tỉ đông muôn đâu tư vao 4 linh vực ̣ ̀ ̀ ́ ̀ ̀ ̃ Linh vực đâu tư ̃ ̀ ̃ ́ Lai suât/năm Chứng khoan ́ 20% Công trai ́ 12% Gửi tiêt kiêm ́ ̣ 15% ́ ̣ Bât đông san ̉ 18% Ngoai ra, để giam thiêu rui ro, nhà đâu tư cho răng ̀ ̉ ̉ ̉ ̀ ̀ không nên đâu tư vao chứng khoan vượt quá 30% ̀ ̀ ́ tông số vôn đâu tư; đâu tư vao công trai và gửi tiêt ̉ ́ ̀ ̀ ̀ ́ ́ kiêm it nhât 25% tông vôn đâu tư; gửi tiêt kiêm it ̣ ́ ́ ̉ ́ ̀ ́ ̣ ́ nhât 300 triêu đông. Hay xac đinh kế hoach phân bổ ́ ̣ ̀ ̃ ́ ̣ ̣ vôn đâu tư sao cho tông thu nhâp hang năm là lớn ́ ̀ ̉ ̣ ̀ nhât. ́
  8. Goi x1, x2, x3, x4 tương ứng là số tiên (triêu đông) đâu ̣ ̀ ̣ ̀ ̀ tư vao chứng khoan, công trai, gửi tiêt kiêm, bât đông ̀ ́ ́ ́ ̣ ́ ̣ san ( x j ≥ 0, j = 1,..., 4 ) ̉ • Do tông số tiên đâu tư không được vượt quá số tiên ̉ ̀ ̀ ̀ hiên có nên: x1 + x2 + x3 + x4 ≤ 4000 (triêu đông) ̣ ̣ ̀ •Điêu kiên về số tiên đâu tư vao chứng khoan: ̀ ̣ ̀ ̀ ̀ ́ x ≤ 0,3( x + x + x + x ) ⇔ −0,7 x + 0,3x + 0,3x + 0,3x ≥ 0 1 1 2 3 4 1 2 3 4 •Điêu kiên về số tiên đâu tư vao công trai và gửi tiêt kiêm: ̀ ̣ ̀ ̀ ̀ ́ ́ ̣ x2 + x3 ≥ 0, 25 ( x1 + x2 + x3 + x4 ) ⇔ 0, 25 x1 + 0, 75 x2 + 0, 75 x3 − 0, 25 x4 ≥ 0 Và x3 ≥ 300 •Thu nhập của năm là: 0, 2 x1 + 0,12 x2 + 0,15 x3 + 0,18 x4 •Yêu cầu tối ưu: 0, 2 x1 + 0,12 x2 + 0,15 x3 + 0,18 x4 → max
  9. ̀ Mô hinh: ̀ Tim x = ( x1, x2, x3, x4) sao cho: f ( x) = 0, 2 x1 + 0,12 x2 + 0,15 x3 + 0,18 x4 → max x1 + x2 + x3 + x4 ≤ 4000 −0,7 x + 0,3x + 0,3x + 0,3x ≥ 0 1 2 3 4 0, 25 x1 + 0, 75 x2 + 0, 75 x3 − 0, 25 x4 ≥ 0 x3 ≥ 300 x j ≥ 0, j = 1,..., 4
  10. Vây để lâp mô hinh toan hoc cua môt bai toan thực ̣ ̣ ̀ ́ ̣ ̉ ̣ ̀ ́ tê, ta phân tich bai toan đó theo 3 bước sau: ́ ́ ̀ ́ Bước 1: Đăt ân và điêu kiên cho ân. ̣ ̉ ̀ ̣ ̉ Bước 2: Lâp hệ rang buôc chinh ̣ ̀ ̣ ́ Bước 3: Lâp ham muc tiêu ̣ ̀ ̣
  11. ̣ ̃ 2. Đinh nghia: Bai toan quy hoach tuyên tinh dang tông quat có dang: ̀ ́ ̣ ́ ́ ̣ ̉ ́ ̣ ̀ Tim x = (x1, x2, …,xn) sao cho: n f ( x) = ∑ c j x j → min ( max ) ̀ ̣ ham muc tiêu j =1 Với hệ rang buôc: ̀ ̣ ≤   =  b , i = 1,..., m ̀ ̣ ́ rang buôc biên ∑ aij x j   i ̀ ̣ ́ (rang buôc chinh) ≥    ≥ 0  x j  ≤ 0  , j = 1, 2,..., n   ̀ ̣ ́ rang buôc dâu  tuy y   
  12.  Môt số khai niêm: ̣ ́ ̣  Vectơ x=( x1, x2, x3, x4)T được goi là phương an (PA) cua ̣ ́ ̉ bai toan QHTT nêu nó thoa man hệ rang buôc cua bai toan ̀ ́ ́ ̉ ̃ ̀ ̣ ̉ ̀ ́  Phương an x*=( x1*, x2*, x3*, x4*)T được goi là ́ ̣ phương an tôi ưu (PATƯ) cua bai toan QHTT nêu giá trị ́ ́ ̉ ̀ ́ ́ ham muc tiêu tai đó là tôt nhât. ̀ ̣ ̣ ́ ́  Giai bai toan QHTT tức là tim phương an tôi ưu cua nó ̉ ̀ ́ ̀ ́ ́ ̉ ́ ́ (nêu co).
  13.  Môt số khai niêm: ̣ ́ ̣ Bai toan giai được là bai toan có PATƯ. ̀ ́ ̉ ̀ ́ Bai toan không giai được là bai toan không có PATƯ. ̀ ́ ̉ ̀ ́ Khi đó hoăc là bai toan không có phương an hoăc có ̣ ̀ ́ ́ ̣ phương an nhưng ham muc tiêu không bị chăn ́ ̀ ̣ ̣ ( f ( x ) → +∞ ( −∞ ) đôi với bai toan max (min)). ́ ̀ ́  Nêu phương an x thoa man rang buôc nao đó với dâu ́ ́ ̉ ̃ ̀ ̣ ̀ ́ “=” thì ta noi x thoa man chăt rang buôc đo. Ngược lai ́ ̉ ̃ ̣ ̀ ̣ ́ ̣ nêu thoa dâu “>” hoăc “
  14.  Môt số khai niêm: ̣ ́ ̣ - Ứng với rang buôc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3 ̀ ̣ - Ký hiêu: ̣  a1 j    là vectơ cac hệ số cua biên xj trong cac ́ ̉ ́ ́ a2 j  Ai =  .  rang buôc (không kể rang buôc dâu). ̀ ̣ ̀ ̣ ́    a3 j    - Hệ vectơ Ai* tương ứng với cac rang buôc chinh tao ́ ̀ ̣ ́ ̣ thanh ma trân rang buôc chinh, ký hiêu là A. ̀ ̣ ̀ ̣ ́ ̣ - Cac rang buôc goi là rang buôc đôc lâp tuyên tinh nêu ́ ̀ ̣ ̣ ̀ ̣ ̣ ̣ ́ ́ ́ hệ vectơ Ai* tương ứng đôc lâp tuyên tinh. ́ ̣ ̣ ́ ́
  15.  Môt số khai niêm: ̣ ́ ̣ - Phương an cực biên (phương an cơ ban): là phương ́ ́ ̉ ́ ̉ ̃ ̣ ̀ ̣ ̣ ̣ ́ ́ an thoa man chăt n rang buôc đôc lâp tuyên tinh. + Phương an cực biên (PACB) thoa man chăt đung n ́ ̉ ̃ ̣ ́ rang buôc goi là PACB không suy biên, PACB thoa man ̀ ̣ ̣ ́ ̉ ̃ chăt hơn n rang buôc goi là PACB suy biên. ̣ ̀ ̣ ̣ ́
  16. Ví dụ 1: f ( x ) = 10 x1 + 12 x2 + 9 x3 → max  x1 − 12 x2 + 5 x3 ≥ 0  8 x1 + 4 x2 − 6 x3 = 52  x ≥ 0, x ≤ 0, x  1 2 3 1  1 -12 5  A = (1, −12,5); A1 =   ; A=  * 1  8 8 4 -6  x 0 = ( 13 2;0;0 ) ; x1 = ( 8;0;2 )
  17. ̀ ̀ ́ Mô hinh bai toan: ̀ Tim x = (x1, x2, x3) sao cho: f ( x ) = 5000 x + 10000 x + 7000 x → max ̀ Ham muc ̣ 1 2 3 tiêu 4 x + 5 x + 3x ≤ 15000  1 2 3 2 x + 4 x + 3x ≤ 12000  1 2 3 Hệ rang buôc chinh ̀ ̣ ́  3x1 + 6 x2 + 4 x3 ≤ 10000  10 x1 + 7 x2 + 6 x3 ≤ 500000   x j ≥ 0, j = 1, 2,3  Hệ rang buôc dâu ̀ ̣ ́
  18. ́ ̣ ̣ ̣ ̉ ̀ ́ 3. Cac dang đăc biêt cua bai toan QHTT: ̀ ́ ̣ ́ ́ a. Bai toan QHTT dang chinh tăc: n f ( x ) = ∑ c j x j → max ( min ) j =1 n ∑ aij x j = bi ( i = 1,..., m ) j =1 x j ≥ 0 ( j = 1,..., n ) Đinh ly: Phương an x cua bai toan QHTT dang chinh tăc ̣ ́ ́ ̉ ̀ ́ ̣ ́ ́ là phương án cực biên khi và chỉ khi hệ thông cac vectơ ́ ́ {Aj} tương ứng với cac thanh phân dương cua phương ́ ̀ ̀ ̉ an là đôc lâp tuyên tinh. ́ ̣ ̣ ́ ́
  19. Ví dụ 2: Cho bài toán QHTT có hệ ràng buộc: x1 + 2x2 + x4 = 4 3x2 + x3 + 2x4 = 3 x j ≥ 0; j = 1,..., 4 Các phương án x1 = (4; 0; 3; 0); x2 = (2; 1; 0; 0); x3 = (0; 1/2; 0; 3/4) là các PACB theo định lý trên.