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

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ả
Nội dung trích xuất từ tài liệu:
Bài toán đối ngẫu và ứng dụng BÀI 3 ́ thiêt́ lâp 1. Cach ̣ baì toan ́ đôí 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 ̣ baì toan ́ % đôí ngâu: ̃ 1) Nêú f(x) min (max) thì f ( y ) max (min) 2) Số rang ̀ buôc ̣ chinh ́ trong baì toan ́ nay ̀ băng ̀ số biên ́ số trong baì toan ́ kia 3) Hệ số trong ham ̀ muc ̣ tiêu cua ̉ baì toan ́ nay ̀ là hệ số tự do cua ̉ hệ rang ̀ buôc ̣ trong baì toan ́ kia. 4) Ma trân ̣ điêu ̀ kiên ̣ cua ̉ hai baì toan ́ là chuyên ̉ vị cua ̉ nhau. 5) Rang̀ buôc ̣ về biên ́ cua ̉ baì toan ́ nay ̀ tương ứng với ̀ buôc rang ̣ về dâu ́ cua ̉ baì toan ́ kia. 6) Biên ́ không có rang ̀ buôc ̣ về dâu ́ trong baì toan ́ naỳ thì ̀ buôc rang ̣ tương ứng trong baì toan ́ kia có dâu ́ “=” 7) Rang ̀ buôc ̣ bât́ đăng ̉ thức trong hệ ràng buộc chính của baì toan ́ min cung ̀ chiêu ̀ với rang ̀ buôc ̣ dâu ́ trong baì toań max 8) Rang ̀ buôc ̣ bât́ đăng ̉ thức trong hệ ràng buộc chính của baì toan ́ max ngược chiêu ̀ với rang ̀ buôc ̣ dâu ́ trong Ví dụ 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 ̣ đôí ngâu: ̃ Cặp ràng buộc đối ngẫu là căp ̣ rang ̀ buôc ̣ bât́ đăng ̉ thức (kể cả rang ̀ buôc ̣ dâu) ́ trong hai baì toan ́ cung ̀ tương ứng với môṭ căp ̣ chỉ sô.́ Ví du:̣ trong ví dụ 1 ta có căp ̣ rang ̀ buôc ̣ đôí ngâu ̃ là : (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 Ví dụ 2: viêt́ baì toań đôĩ ngâu ̃ và tim ̀ các căp ...