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

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

Thêm vào BST

Báo xấu

78
lượt xem 9
download

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

1) Mục đích: Giải bài toán QHTT có ẩn giả. Bài toán này xuất hiện khi chuyển bài toán dạng chính tắc về bài toán dạng chuẩn bằng cách đưa vào ẩn giả để tạo ma trận đơn vị.

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán mô hình mở rộng

BÀI 3
̣ đich 1) Muc ́ : Giaỉ baì toan ́ QHTT có ân ̉ gia.̉ Baì toan ́ ̀ xuât́ hiên nay ̣ khi chuyên ̉ baì toan ́ dang ̣ chinh ́ tăc ́ về baì toan ́ dang ̣ chuân ̉ băng ̀ cach ́ đưa vao ̀ ân ̉ giả để tao ̣ ̣ đơn vi.̣ ma trân - Từ baì 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ề baì toan: Ta chuyên ́ - Baì toan ́ dang ̣ chuân ̉ với biên ́ giả (baì toan ́ mở rông ̣ hay baì 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 )
Ví dụ 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,3 Suy ra ta có baì 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,5
2) Quan hệ giữa baì toan ́ xuât́ phat́ và baì toan ́ mở rông: ̣ Giả sử (x*, xig) là phương an ́ cua ̉ baì toan ́ mở rông, ̣ ta co:́ ́ x là PA cua  Nêu ̉ baì toan ́ xuât́ phat́ thì (x*, xig) = (x, 0) (xi g = 0, ∀i ) là phương an ́ cua ̉ baì toan ́ mở rông. ̣ Ngược laị phương an ́ cua ̉ baì toan ́ mở rông ̣ là (x*, xig) = (x, 0) thì x là phương an ́ cua ̉ baì toan ́ xuât́ phat. ́  x là phương an ́ cơ ban ̉ cua ̉ baì toan ́ xuât́ phat́  (x, 0) là PACB cua ̉ baì toan ́ mở rông. ̣
 Baì toan ́ mở rông ̣ có dang ̣ chuân, ̉ xuât́ phat́ từ PACB i = bi . Ap g ̀ có cac ban đâu ́ ân ̉ x ́ dung ̣ thuâṭ toan ́ đ ơn hinh ̀ giaỉ baì toan ́ đơn hinh ̀ sau môṭ số bước ta có kêt́ luân: ̣ Baì toań M không có PATƯ thì baì toan ́ xuât́ phat́ không có PATƯ Baì toan ́ M có PATƯ (x*, xig). Khi đó 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ằng cách bỏ đi phần ẩn giả trong PATU của bài toán M. TH 2: trong PATƯ cua ̉ baì toań M có môṭ ân ̉ giả có giá trị dương thì baì toan ́ xuât́ phat́ không có PA nên không co ́ PATƯ.
Ví dụ 2: Giaỉ baì toan ́ QHTT được cho ở ví dụ 1. ́ sô:́ Đap ( ) ( ) x * = 5 , 2,0,0,0 , g x * = −8 2 ( ) ( ) � x* = 5 , 2,0 , f x* = −8 2
Ví dụ 3: Giaỉ baì 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: baì toan ́ không có PATƯ
Ví dụ 4: Giaỉ baì 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ô:́ baì toan Đap ́ M có phương an ́ tôí ưu ̉ giả x7 = 7 > 0 nên baì xM* = (4, 0, 1, 0, 0, 0,7 ,0). Do ân ́ gôc toan ́ không có PA.
Giải bài toán QHTT sau: f ( x ) = −2 x1 − 4 x2 − x3 − x4 min x1 + 3 x2 + x4 = 1 −5 x2 − 2 x4 3 x2 + 4 x3 + x4 3 xj 0, j = 1; 4