Quy hoạch tuyến tính

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

Thêm vào BST

Báo xấu

87
lượt xem 6
download

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

Giả sử rằng sản phẩm sản xuất ra đều có thể tiêu thụ được hết với lợi nhuận khi bán một đơn vị sản phẩm L1, L2, L3 tương ứng là 5000:10000:7000 (đồng). Yêu cầu lập kế hoạch sản xuất tối ưu.

Chủ đề:

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

Lưu

Nội dung Text: Quy hoạch tuyến tính

BỐ CUC ̣ BAÌ GIANG ̉ 1.Cac ́ ví dụ dân ̃ đên ́ baì toan ́ Quy hoach ̣ tuyên ́ ́ tinh: ̣ kế hoach 1.1 Lâp ̣ san ̉ xuât: ́ 1.2 Phân bổ vôn ́ đâu ̀ tư: ̣ nghia: 2. Đinh ̃
1. Cać ví dụ dân ̃ đên ́ baì toan ́ Quy hoach ̣ tuyên ́ ́ (QHTT): tinh 1.1 Lâp̣ kế hoacḥ san̉ xuât: ́ ̉ phâm san ̉ Số lượng nguyên L1 L2 L3 Chi phí ̣ hiên liêu ̣ có (kg) ̣ 1 (N1) Nguyên liêu 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 ̣ (phút) 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 ̉ L1, L2, L3 tương ứng là 5000:10000:7000 (đông). ̀ Yêu câu ̀ lâp ̣ kế hoach ̣ ̉ xuât́ tôí ưu. san
Goị xj là số san ̉ phâm ̉ cua ̉ Lj (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 ̉ lợi nhuân Tông ̣ 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
̀ baì toan: Mô hinh ́ ̀ x = (x1, x2, x3) sao cho: Tim 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 3x + 6 x + 4 x 10000 1 2 3 10 x + 7 x + 6 x 500000 1 2 3 x j 0, j = 1, 2,3
̉ quat: Tông ́ ta có baì toań lâp ̣ kế hoach ̣ san ̉ xuât́ dưới dang ̣ bang ̉ số liêu ̣ sau đây: ̉ phâm San ̉ Yêú tố Số lượng ̉ xuât́ hiên san ̣ có S1 S2 … Sn Y1 b1 a11 a12 … a1n Y2 b2 a21 a22 … a2n … … … … … … … … … … … … Ym bm am1 am2 … amn Lợi nhuân ̣ đơn vị c1 c2 … cn
̀ Mô hinh: ̀ x = (x1, x2,…, xn) sao cho: Tim n f = c jx j max j =1 n aij x j bi , i = 1,..., m j =1 xj 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 ̃ vực đâu Linh ̀ tư Laĩ suât/năm ́ Cổ phiếu 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 ̀ cổ phiếu 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̉ lợi nhuận hang ̀ năm là lớn nhât. ́
Goị x1, x2, x3, x4 tương ứng là số tiên ̀ (triêu ̣ đông) ̀ ̀ tư đâu ̀ chứng khoan, vao ́ 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 ̀ ̣ có nên: x1 + x2 + x3 + x4 ≤ 4000 (triêu hiên ̣ đô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 •Lãi suất 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: ̀ x = ( x1, x2, x3, x4) sao cho: Tim 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,3 x + 0,3 x 0 1 2 3 4 −0, 25 x1 + 0, 75 x2 + 0, 75 x3 − 0, 25 x4 0 x3 300 xj 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
̣ nghia: 2. Đinh ̃ Baì toan ́ quy hoach ̣ tuyên ́ tinh ́ dang ̣ tông ̉ quat́ có dang: ̣ ̀ x = (x1, x2, …,xn) sao cho: Tim n f ( x) = cjxj min ( max ) ̀ muc ham ̣ tiêu j =1 Với hệ rang ̀ buôc: ̣ �� n �� ̀ buôc rang ̣ biên ́ = bi , i = 1,..., m aij x j �� j =1 ̀ buôc (rang ̣ chinh ́ ) �� 0 � xj � 0 � � �, j = 1, 2,..., n ̀ buôc rang ̣ dâu ́ � tuy y � � �
 Môṭ số khaí niêm: ̣  Vectơ x=( x1, x2,…, xn) đượ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*, …, xn*) đượ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́ ́ co). (nêu ́
 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)). ́ phương an  Nêu ́ 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̣ ́ thoa nêu ̉ 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 ́ a �2j� Aj = ̀ buôc ̣ (không kể rang ̀ buôc ̣ dâu). ́ . � rang � � � amj � � � � - Hệ vectơ Ai* tương ứng với cac ́ rang ̀ buôc ̣ chinh ́ tao ̣ ̀ ma trân thanh ̣ rang ̀ buôc ̣ chinh ́ , ký hiêu ̣ là A. ́ rang - Cac ̀ buôc ̣ goị là rang ̀ ̣ đôc buô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 ́ thoa an ̉ 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 ̀ buôc rang ̣ 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 2 x1 + x2 − x3 + x4 5 −4 x1 + 3x2 − 5 x3 + 2 x4 8 x1 + 8 x3 = −15 x1 0 x2 0 x4 0 x 0 = ( 9, 0, −3, 0 ) là một phương án. x1 = ( 1, 0, −2,1) là một phương án cực biên.
̀ baì toan: Mô hinh ́ ̀ x = (x1, x2, x3) sao cho: Tim f ( x ) = 5000 x + 10000 x + 7000 x max ̀ muc Ham ̣ 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 ́ 3x + 6 x + 4 x 10000 1 2 3 10 x + 7 x + 6 x 500000 1 2 3 x j 0, j = 1, 2,3 Hệ rang ̀ buôc ̣ dâu ́
́ dang 3. Cac ̣ đăc̣ biêṭ cua ̉ baì toań QHTT: a. Baì toań QHTT dang̣ chinh ́ tăc:́ n f ( x) = cjxj max ( min ) j =1 n aij x j = bi ( i = 1,..., m ) j =1 xj 0 ( j = 1,..., n ) ̣ ly:́ Phương an Đinh ́ 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 ́ là đôc an ̣ lâp ̣ tuyên ́ tinh. ́
Ví dụ 2: Cho bài toán QHTT có hệ ràng buộc: x1 + 2 x2 + x4 = 4 3x2 + x3 + 2 x4 = 3 xj 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.