Bài toán đối ngẫu và ứng dụng

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

Thêm vào BST

Báo xấu

239
lượt xem 38
download

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

Tham khảo bài thuyết trình 'bài toán đối ngẫu và ứng dụng', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Bài toán đối ngẫu và ứng dụng

BÀI 3
́ thiêt́ lâp 1. Cach ̣ baì toan ́ đôí ngâu: ̃ ( P) ( P% ) f ( x ) = c1 x1 + ... + cn xn max f% ( y ) = b1 y1 + ... + bm ym min �� 0 � ai1 x1 + ... + ain xn ��bi , i = 1,..., m � � yi 0 , i = 1,..., m �� = �� tuy y � � � �0 � �� xj � 0 � , j = 1,..., n aij y1 + ... + amj ym ��c , j = 1,..., n ��j � � = �� tuy y � ��
* Nguyên tăc ́ thiêt́ lâp ̣ baì toan ́ % đôí ngâu: ̃ 1) Nêú f(x) min (max) thì f ( y ) max (min) 2) Số rang ̀ buôc ̣ chinh ́ trong baì toan ́ nay ̀ băng ̀ số biên ́ số trong baì toan ́ kia 3) Hệ số trong ham ̀ muc ̣ tiêu cua ̉ baì toan ́ nay ̀ là hệ số tự do cua ̉ hệ rang ̀ buôc ̣ trong baì toan ́ kia. 4) Ma trân ̣ điêu ̀ kiên ̣ cua ̉ hai baì toan ́ là chuyên ̉ vị cua ̉ nhau. 5) Rang̀ buôc ̣ về biên ́ cua ̉ baì toan ́ nay ̀ tương ứng với ̀ buôc rang ̣ về dâu ́ cua ̉ baì toan ́ kia. 6) Biên ́ không có rang ̀ buôc ̣ về dâu ́ trong baì toan ́ naỳ thì ̀ buôc rang ̣ tương ứng trong baì toan ́ kia có dâu ́ “=” 7) Rang ̀ buôc ̣ bât́ đăng ̉ thức trong hệ ràng buộc chính của baì toan ́ min cung ̀ chiêu ̀ với rang ̀ buôc ̣ dâu ́ trong baì toań max 8) Rang ̀ buôc ̣ bât́ đăng ̉ thức trong hệ ràng buộc chính của baì toan ́ max ngược chiêu ̀ với rang ̀ buôc ̣ dâu ́ trong
Ví dụ 1: viết bài toán đối ngẫu của bài toán QHTT sau: f ( x ) = 2 x1 − 3 x2 + 4 x3 − 6 x4 min x1 + 2 x2 + 3 x3 − x4 = 20 −3 x1 − x2 + 7 x3 + 7 x4 32 ( 1) 2 x1 + 4 x2 + x3 + x4 18 ( 2 ) x1 0 ( 3) x2 0 ( 4) x3 0 ( 5)
( P% ) : f% ( y ) = 20 y1 + 32 y2 + 18 y3 max y1 − 3 y2 + 2 y3 2 ( 6 ) 2y1 − y2 + 4 y3 −3 ( 7 ) 3y1 + 7 y2 + y3 4 ( 8 ) − y1 + 7 y2 + y3 = −6 y1 tuy y y2 0 ( 9 ) y3 0 ( 10 )
̣ rang 2) Căp ̀ buôc ̣ đôí ngâu: ̃ Cặp ràng buộc đối ngẫu là căp ̣ rang ̀ buôc ̣ bât́ đăng ̉ thức (kể cả rang ̀ buôc ̣ dâu) ́ trong hai baì toan ́ cung ̀ tương ứng với môṭ căp ̣ chỉ sô.́ Ví du:̣ trong ví dụ 1 ta có căp ̣ rang ̀ buôc ̣ đôí ngâu ̃ là : (1), (9); (2), (10); (3), (6); (4), (7); (5), (8)
f ( x ) = 2 x1 − 3x2 + 4 x3 − 6 x4 min ( P% ) : f% ( y ) = 20 y1 + 32 y2 + 18 y3 max x1 + 2 x2 + 3x3 − x4 = 20 y1 − 3 y2 + 2 y3 2 ( 6 ) − 3x1 − x2 + 7 x3 + 7 x4 32 ( 1) 2y1 − y2 + 4 y3 −3 ( 7 ) 3y1 + 7 y2 + y3 4 ( 8 ) 2 x1 + 4 x2 + x3 + x4 18 ( 2 ) − y1 + 7 y2 + y3 = − 6 x1 0 ( 3) y1 tuy y x2 0 ( 4 ) y2 0 ( 9 ) x3 0 ( 5 ) y3 0 ( 10 ) x4 tuy y
Ví dụ 2: viêt́ baì toań đôĩ ngâu ̃ và tim ̀ các căp ̣ rang ̀ buôc ̣ đôí ngâu ̃ cua ̉ baì toań sau: f ( x ) = 15 x1 + 12 x2 + 16 x3 + 10 x4 max x1 + 3 x2 + x3 + x4 20 ( 1) 2 x1 + x2 + 3 x3 + 2 x4 = 20 x1 + 2 x2 + x3 + 2 x4 24 ( 2 ) x j 0, j = 1,..., 4 ( 3 ) ( 6)
Ý nghĩa kinh tế của bài toán đối ngẫu: Xét bài toán lập kế hoạch sản xuất: f ( x ) = c1 x1 + c2 x2 max a11 x1 + a12 x2 b1 a21 x1 + a22 x2 b2 a31 x1 + a32 x2 b3 xj 0 ( j = 1, 2 )
Ta giả thiết tình huống có người muốn mua toàn bộ số lượng các yếu tố sản xuất của xí nghiệp. Khi đó giá bán nên đặt ra là bao nhiêu? Gọi yi (i = 1,2,3) là giá bán một đơn vị yếu tố sản xuất loại i. (yi 0) Ta có số tiền thu được khi bán các yếu tố sản xuất dùng để sản xuất ra một đơn vị sản phẩm Loại 1: a11 y1 + a21 y2 + a31 y3 Loại 2: a12 y1 + a22 y2 + a32 y3
 Đối với người bán: a11 y1 + a21 y2 + a31 y3 c1 a12 y1 + a22 y2 + a32 y3 c2  Đối với người mua: b1 y1 + b2 y2 + b3 y3 min Mô hình: b1 y1 + b2 y2 + b3 y3 min a11 y1 + a21 y2 + a31 y3 c1 a12 y1 + a22 y2 + a32 y3 c2 yi 0 (i = 1,2,3)
c1 x1 + c2 x2 max b1 y1 + b2 y2 + b3 y3 min a11 x1 + a12 x2 b1 a11 y1 + a21 y2 + a31 y3 c1 a21 x1 + a22 x2 b2 a12 y1 + a22 y2 + a32 y3 c2 a31 x1 + a32 x2 b3 yi 0 (i = 1,2,3) xj 0 ( j = 1, 2 )
́ đinh 3) Cac ̣ lý đôí ngâu: ̃ ̣ lý 1: Cho hai baì toan Đinh ̃ (P) và ( P% ) . Khi đó ́ đôí ngâu ̉ ra ba trường hợp: xay  Cả hai đêu ̀ không có PA.  Cả hai đêu ̀ có PA. Khi đó cả hai đêu ̀ giaỉ được. ̣ x* và y* là tôí ưu  f(x*) = g(y*) Căp  Môṭ baì toan ́ có PA, baì toan ́ con ̀ laị không có PA. Khi đó ham ̀ muc ̣ tiêu cua ̉ baì toan ́ có PA không bị chăn ̣ trên tâp ̣ cac ́ PA, do đó baì toan ́ ̀ không có PATƯ. nay * Hệ quả : Nêu ́ môṭ trong hai baì toan ́ có PATƯ thì baì ́ kia cung toan ̃ có PATƯ.
́ đinh 3) Cac ̣ lý đôí ngâu: ̃ ̣ lý 2 : (độ lêch Đinh ̣ bù yêu) ́ Cho x và y là hai phương an ́ cuả hai baì toan.́ Khi đó x và y là hai phương an ́ tôí ưu cua ̉ hai baì toan ́  nêu ́ trong căp ̣ rang ̀ buôc ̣ đôí ngâu ̃ rang̀ buôc ̣ cua ̉ baì toań naỳ là long ̉ thì rang ̀ buôc ̣ đôí ngâu ̃ cua ̉ nó là chăt. ̣ �m � x j � aij yi − c j �= 0 i =1 � � �n � yi � aij x j − bi �= 0 �j =1 � Hệ qua:̉ Nêu ́ môṭ căp ̣ rang̀ buôc ̣ là long ̉ đôí với PATƯ ̉ baì toan cua ́ nay ̀ thì rang ̀ buôc ̣ đôí ngâu ̃ cua ̉ nó phaỉ là chăṭ với PATƯ cua ̉ baì toan ́ kia.
4) Ứng dung ̣ cua ̉ baì toan ́ đôí ngâu: ̃ Ví dụ 3: Cho baì toan ́ QHTT: f ( x ) = 2 x1 + 5 x2 + 4 x3 + x4 min x1 − 6 x2 − 2 x4 − 9 x5 = 32 2 x2 + x3 + 1 x4 + 3 x 5 = 30 2 2 3 x2 + x5 36 ( 1) xj 0, j = 1,...,5(2) (6) ̃ giaỉ baì toan a) Hay ́ băng ̀ phương phap ́ đơn hinh ̀ b) Viêt́ baì toan ́ đôí ngâu ̃ ̀ phương an c) Tim ́ tôí ưu cua ̉ baì toan ́ đôí ngâu ̃
a) Đaṕ sô:́ x* = (32,0,30,0,0) f(x*) = 184 b) f% ( y ) = 32 y1 + 30 y2 + 36 y3 max y1 2(7) -6y1 + 2 y2 + 3 y3 5(8) y2 4(9) − 2y1 + 1 y2 1(10) 2 -9y1 + 3 y2 + y3 0(11) 2 y1 ,y 2 tuy y y3 0 ( 12 )
c) x* = (32,0,30,0,0) x1 = 32 0: y1 = 2 x3 = 30 0: y2 = 4 Ta có rang ̀ buôc ̣ (*) và (**) là căp ̣ rang ̀ buôc ̣ đôí ngâu ̃ mà x* thoa ̉ long ̉ ở rang ̀ buôc ̣ (*) => ̉ chăṭ ở rang y* thoa ̀ buôc ̣ (**) => y3 = 0 ̣ y* = (2,4,0) Vây %f ( y* ) = 184
Ví dụ 4: a) Giaỉ baì toan ́ ở ví dụ 2 băng ̀ phương phap ́ đơn hinh ̀ b) Viêt́ baì toan ́ đôí ngâu ̃ và cac ́ căp ̣ rang ̀ buôc ̣ đối ngẫu. ̀ PATƯ cua c) Tim ̉ baì toan ́ đôí ngâu. ̃ ̉ Giai: ́ sô:́ x* = (0,4,0,8) a) Đap fmax = f(x*) = 128
b) f% ( y ) = 20 y1 + 20 y2 + 24 y3 min y1 + 2 y2 + y3 15 ( 7 ) 3y1 + y2 + 2 y3 12 ( 8 ) y1 + 3 y2 + y3 16 ( 9 ) y1 + 2 y2 + 2 y3 10 ( 10 ) y1 0 ( 11) y2 tuy y y3 0 ( 12 ) ́ căp Cac ̣ rang ̀ buôc ̣ đôí ngâu: ̃ (1),(11); (2),(12); (3),(7); (4),(8); (5),(9); (6),(10)
c) x2 = 4 0 : 3y1 + y2 + 2 y3 = 12 x 4 =8 0:y1 + 2 y2 + 2 y3 = 10 * �14 − 2 y3 18 − 4 y3 � � y =� , , y3 � � 5 5 � Vậy: * 14 − 2 y3 18 − 4 y3 � � y =� , , y3 � � 5 5 � y3 −5 ( ) f% y* = 128