Chương 3: Mô hình tối ưu tuyến tính - Quy hoạch tuyến tính (Bài 1)

Chia sẻ: AN TON | Ngày: | Loại File: PPT | Số trang:27

Thêm vào BST

Báo xấu

1.539
lượt xem 478
download

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

Ngoài ra, để giảm thiếu rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 30% tổng số vốn đầu tư, đầu tư vào công trái và gởi tiết kiệm ít nhất 25% tổng vốn đầu tư, gửi tiết kiệm ít nhất 300 triệu đồng. Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho tổng thu nhập hàng năm lớn nhất.

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: Mô hình tối ưu tuyến tính - Quy hoạch tuyến tính (Bài 1)

BỐ CUC BAI GIANG ̣ ̀ ̉ 1.Cac ví dụ 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:
1. Cac ví dụ 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 phí liêu hiên có ̣ ̣ ̣ 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 Giả sử răng san phâm san xuât ra đêu có thể tiêu thụ được ̀ ̉ ̉ ̉ ́ ̀ hêt với lợi nhuân khi ban môt đơn vị san phâm S1, S2, S3 ́ ̣ ́ ̣ ̉ ̉ tương ứng là 5000:10000:7000 (đông). Yêu câu lâp kế hoach ̀ ̀ ̣ ̣ san xuât tôi ưu. ̉ ́ ́
Goi xj là 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
̀ ̀ ́ 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 
Tông quat: ta có 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 có ̉ ́ ̣ S1 S2 … Sn Y1 b1 a11 a12 … a1n Y2 b2 a21 a22 … a2n … … … … … … … … … … … … Ym bm am1 am2 … am n Lợi nhuân đơn vị ̣ c1 c2 … cn
̀ 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
2.2 Phân bổ vôn đâu tư: ́ ̀ Môt nhà đâu tư có 4 tỉ đô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, nhà đâu tư cho răng ̀ ̉ ̉ ̉ ̀ ̀ không nên đâu tư vao chứng khoan vượt quá 30% ̀ ̀ ́ tông số vôn đâu tư; đâu tư vao công trai và 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 là lớn ́ ̀ ̉ ̣ ̀ nhât. ́
Goi x1, x2, x3, x4 tương ứng là 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 quá số tiên ̉ ̀ ̀ ̀ hiên có 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 và 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
̀ 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
Vây để lâp mô hinh toan hoc cua môt bai toan thực ̣ ̣ ̀ ́ ̣ ̉ ̣ ̀ ́ tê, ta phân tich bai toan đó theo 3 bước sau: ́ ́ ̀ ́ Bước 1: Đăt ân và đ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 ̣ ̀ ̣
̣ ̃ 2. Đinh nghia: Bai toan quy hoach tuyên tinh dang tông quat có 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   
 Môt số khai niêm: ̣ ́ ̣  Vectơ x=( x1, x2, x3, x4)T được goi là phương an (PA) cua ̣ ́ ̉ bai toan QHTT nêu nó thoa man hệ rang buôc cua bai toan ̀ ́ ́ ̉ ̃ ̀ ̣ ̉ ̀ ́  Phương an x*=( x1*, x2*, x3*, x4*)T được goi là ́ ̣ phương an tôi ưu (PATƯ) cua bai toan QHTT nêu giá trị ́ ́ ̉ ̀ ́ ́ ham muc tiêu tai đó là tôt nhât. ̀ ̣ ̣ ́ ́  Giai bai toan QHTT tức là tim phương an tôi ưu cua nó ̉ ̀ ́ ̀ ́ ́ ̉ ́ ́ (nêu co).
 Môt số khai niêm: ̣ ́ ̣ Bai toan giai được là bai toan có PATƯ. ̀ ́ ̉ ̀ ́ Bai toan không giai được là bai toan không có PATƯ. ̀ ́ ̉ ̀ ́ Khi đó hoăc là bai toan không có phương an hoăc có ̣ ̀ ́ ́ ̣ phương an nhưng ham muc tiêu không bị chăn ́ ̀ ̣ ̣ ( f ( x ) → +∞ ( −∞ ) đôi với bai toan max (min)). ́ ̀ ́  Nêu phương an x thoa man rang buôc nao đó với dâu ́ ́ ̉ ̃ ̀ ̣ ̀ ́ “=” thì ta noi x thoa man chăt rang buôc đo. Ngược lai ́ ̉ ̃ ̣ ̀ ̣ ́ ̣ nêu thoa dâu “>” hoăc “
 Môt số khai niêm: ̣ ́ ̣ - Ứng với rang buôc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3 ̀ ̣ - Ký hiêu: ̣  a1 j    là 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, ký hiêu là A. ̀ ̣ ̀ ̣ ́ ̣ - Cac rang buôc goi là rang buôc đôc lâp tuyên tinh nêu ́ ̀ ̣ ̣ ̀ ̣ ̣ ̣ ́ ́ ́ hệ vectơ Ai* tương ứng đôc lâp tuyên tinh. ́ ̣ ̣ ́ ́
 Môt số khai niêm: ̣ ́ ̣ - Phương an cực biên (phương an cơ ban): là 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 là PACB không suy biên, PACB thoa man ̀ ̣ ̣ ́ ̉ ̃ chăt hơn n rang buôc goi là PACB suy biên. ̣ ̀ ̣ ̣ ́
Ví dụ 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 )
̀ ̀ ́ 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 ̀ ̣ ́
́ ̣ ̣ ̣ ̉ ̀ ́ 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 ̣ ́ ́ ̉ ̀ ́ ̣ ́ ́ là phương án cực biên khi và chỉ khi hệ thông cac vectơ ́ ́ {Aj} tương ứng với cac thanh phân dương cua phương ́ ̀ ̀ ̉ an là đôc lâp tuyên tinh. ́ ̣ ̣ ́ ́
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.