Thuật toán mô hình mở rộng

1) Mục đích: Giải bài toán QHTT có ẩn giả. Bài toán này xuất hiện khi chuyển bài toán dạng chính tắc về bài toán dạng chuẩn bằng cách đưa vào ẩn giả để tạo ma trận đơn vị.
Nội dung trích xuất từ tài liệu:
Thuật toán mô hình mở rộngBÀI 3 ̣ đich1) Muc ́ : Giaỉ baì toan ́ QHTT có ân ̉ gia.̉ Baì toan ́ ̀ xuât́ hiênnay ̣ khi chuyên ̉ baì toan ́ dang ̣ chinh ́ tăc ́ vềbaì toan ́ dang ̣ chuân ̉ băng ̀ cach ́ đưa vao ̀ ân ̉ giả để tao ̣ ̣ đơn vi.̣ma trân - Từ baì toan ́ xuât́ phat́ dang ̣ chinh ́ tăc: ́ n f ( x) = c jx j Min (Max) j =1 aij x j = bi , i = 1,..., m xj 0; j = 1,..., n ̉ về baì toan:Ta chuyên ́- Baì toan ́ dang ̣ chuân ̉ với biên ́ giả (baì toan ́ mở rông ̣ haybaì toan ́ M). n m g ( g ) g x, xi = �c j x j + M � xi i =1 i=1 min �g x, x g = n c x − M m x g � � i( i =1 ) � j j � i i =1 � max � � n g aij x j + xi = bi , i = 1,..., m j =1 x j 0, xi 0 ( i = 1,..., m; j = 1,..., n )Ví dụ 1: f ( x ) = −8 x1 + 6 x2 + 2 x3 min 4 x1 + 4 x2 − 3 x3 = 18 4 x1 + 3 x2 + 4 x3 = 16 xj 0, j = 1, 2,3Suy ra ta có baì toan ́ dang ̣ chuân ̉ với biên ́ gia:̉ ( g ( x ) = −8 x1 + 6 x2 + 2 x3 + M x4 + x5 ) min 4 x1 + 4 x2 − 3 x3 + x4 = 18 4 x1 + 3 x2 + 4 x3 + x5 = 16 xj 0, j = 1, 2,3, 4,52) Quan hệ giữa baì toan ́ xuât́ phat́ và baì toan ́ mở rông: ̣Giả sử (x*, xig) là phương an ́ cua ̉ baì toan ́ mở rông, ̣ ta co:́ ́ x là PA cua Nêu ̉ baì toan ́ xuât́ phat́ thì (x*, xig) = (x, 0) (xi g = 0, ∀i ) là phương an ́ cua ̉ baì toan ́ mở rông. ̣ Ngượclaị phương an ́ cua ̉ baì toan ́ mở rông ̣ là (x*, xig) = (x, 0) thìx là phương an ́ cua ̉ baì toan ́ xuât́ phat. ́ x là phương an ́ cơ ban ̉ cua ̉ baì toan ́ xuât́ phat́  (x, 0)là PACB cua ̉ baì toan ́ mở rông. ̣ Baì toan ́ mở rông ̣ có dang ̣ chuân, ̉ xuât́ phat́ từ PACB i = bi . Ap g ̀ có cacban đâu ́ ân ̉ x ́ dung ̣ thuâṭ toan ́ đ ơn hinh ̀giaỉ baì toan ́ đơn hinh ̀ sau môṭ số bước ta có kêt́ luân: ̣ Baì toań M không có PATƯ thì baì toan ́ xuât́ phat́ không có PATƯ Baì toan ́ M có PATƯ (x*, xig). Khi đó xay ̉ ra 2 TH:TH 1: trong PATU của bài toán M các ẩn giả đều có giá trịbằng 0 thì PATU của bài toán xuất phát có được bằngcách bỏ đi phần ẩn giả trong PATU của bài toán M.TH 2: trong PATƯ cua ̉ baì toań M có môṭ ân ̉ giả có giá trịdương thì baì toan ́ xuât́ phat́ không có PA nên không co ́PATƯ.Ví dụ 2: Giaỉ baì toan ́ QHTT được cho ở ví dụ 1. ́ sô:́Đap ( ) ( ) x * = 5 , 2,0,0,0 , g x * = −8 2 ( ) ( ) � x* = 5 , 2,0 , f x* = −8 2Ví dụ 3: Giaỉ baì toan ́ QHTT sau: f ( x ) = x1 + 2 x2 + x4 − 5 x5 min x1 − x2 + 2 x3 + 4 x4 − x5 = 2 x2 − 7 x3 − 5 x4 = 5 x3 + 9 x4 = 0 xj 0, j = 1,...,5ĐS: baì toan ́ không có PATƯVí dụ 4: Giaỉ baì toan ́ QHTT: f ( x ) = 2 x1 + 3 x2 + 4 x3 + x4 max x1 + x2 + x3 + x4 5 2 x1 + 2 x2 + 3 x3 = 18 2 x1 + x2 + 3 x4 8 xj 0, j = 1,..., 4 ́ sô:́ ...