Thuật toán mô hình mở rộng
lượt xem 9
download
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ị.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Thuật toán mô hình mở rộng
- BÀI 3
- ̣ đ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
- ̉ 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 )
- 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
- 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. ̣
- 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Ư.
- 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
- 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Ư
- 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.
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
TOÁN ỨNG DỤNG- CHƯƠNG 3 GIỚI THIỆU LÍ THUYẾT MÔ PHỎNG VÀ MÔ HÌNH HÀNG CHỜ
33 p | 1475 | 391
-
Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học Quốc gia Hà Nội ) - Chương 3
53 p | 92 | 16
-
Quá trình hình thành giáo trình lý thuyết điều khiển logic mờ trong các hàm liên thuộc của mô hình matlap 6.0 p2
9 p | 98 | 9
-
Xây dựng chương trình tối ưu bộ thông số mô hình TANK bằng thuật giải di truyền
7 p | 156 | 7
-
Ứng dụng kỹ thuật trí tuệ nhân tạo trong dự báo chỉ số nén lại (Cr) của đất yếu khu vực đồng bằng Bắc bộ
8 p | 14 | 6
-
Thuật toán đường đi tăng luồng tìm luồng cực đại trên mạng hỗn hợp mở rộng
6 p | 12 | 3
-
Thuật toán đẩy luồng trước tìm luồng cực đại trên mạng hỗn hợp mở rộng
5 p | 16 | 3
-
Mô hình toán đánh giá hiệu quả giảm sóng của hàng rào tre
3 p | 24 | 3
-
Bài giảng Toán kinh tế: Bài toán vận tải
22 p | 38 | 3
-
Thuật toán hoán chuyển nguồn đích tìm luồng cực đại trên mạng mở rộng
4 p | 15 | 3
-
Ứng dụng phương trình sai phân trong giảng dạy một số mô hình kinh tế cho sinh viên khối ngành Kinh tế tại trường Đại học Sư phạm Kỹ thuật thành phố Hồ Chí Minh
13 p | 54 | 3
-
Mô phỏng dòng chảy trong môi trường rỗng bằng mô hình K - WSST
9 p | 70 | 3
-
Giáo trình hình thành đạo hàm ứng dụng nguyên lý chuyển đổi hàm liên thuộc kiểu S dạng trơn p2
10 p | 72 | 3
-
Tổng quan về hệ thống mô hình hóa telemac-mascaret và khả năng ứng dụng
5 p | 95 | 2
-
Điều khiển dự báo dựa trên mô hình cho hệ phi tuyến với tầm dự báo bằng 1
7 p | 51 | 2
-
Một thuật toán rút gọn bề mặt biểu diễn mô hình 3D
11 p | 75 | 1
-
Nâng cao tần số làm việc ngưỡng của vi chấp hành điện nhiệt dạng chữ V sử dụng thuật toán tối ưu bầy đàn
10 p | 9 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn