intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

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

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

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ị.

Chủ đề:
Lưu

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

  1. BÀI 3
  2. ̣ đich 1) Muc ́ : Giaỉ baì toan ́ QHTT có ân ̉ gia.̉ Baì toan ́ ̀ xuât́ hiên nay ̣ 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
  3. ̉ về baì toan: Ta chuyên ́ - Baì toan ́ dang ̣ chuân ̉ với biên ́ giả (baì toan ́ mở rông ̣ hay baì 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 )
  4. 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,3 Suy 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,5
  5. 2) 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ược laị 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. ̣
  6.  Baì toan ́ mở rông ̣ có dang ̣ chuân, ̉ xuât́ phat́ từ PACB i = bi . Ap g ̀ có cac ban đâ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ằng cá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Ư.
  7. 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 2
  8. Ví 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Ư
  9. 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ô:́ baì toan Đap ́ M có phương an ́ tôí ưu ̉ giả x7 = 7 > 0 nên baì xM* = (4, 0, 1, 0, 0, 0,7 ,0). Do ân ́ gôc toan ́ không có PA.
  10. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2