zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Chương 1: Bài toán quy hoạch tuyến tính - bài 5

Chia sẻ: Lê Văn Nhứt | Ngày: | Loại File: PDF | Số trang:0

Báo xấu

387
lượt xem 112
download

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

Tham khảo tài liệu 'chương 1: bài toán quy hoạch tuyến tính - bài 5', 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ả

Chủ đề:

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

Lưu

Nội dung Text: Chương 1: Bài toán quy hoạch tuyến tính - bài 5

 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH Nội dung cơ bản của PP đơn hình 1  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH Xét BT QHTT dạng chuẩn tắc như sau: n f ( x)   ci xi  max (min) i 1  n m xk  akmj x j  bk (k  1, m; j  1, n  m)  j 1 x  0, b  0 (i  1, n; k  1, m; m  n) i k 2 1
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 1. Ước lượng của ẩn: PACB XP: x0 (x10, x20,, xm0 , 0,, 0) hay x0  (b1, b2 ,, bm, 0,, 0) Với hệ ẩn CB: x1, x2, …, xm m  l   ck akl  cl (l  m  1, n) k 1 Được gọi là hệ số ước lượng của ẩn xl. 3  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 2. Dấu hiệu tối ưu của bài toán n n l f ( x )   ci xi  max f ( x)   ci xi  min i 1 i 1  l  0 l  m  1, n Có PATU l  0 l m 1, n Có PATU ** Chú ý: Khi có dấu hiệu tối ưu mà tồn tại ít nhất 1 hệ số ước lượng bằng 0 của ẩn không cơ bản thì bài toán có thể có nhiều hơn 1 phương án tối ưu. 4 2
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 3. Định lý cơ bản Nếu trong 1 phương án cơ bản của bài toán mà l 0 (đối với bài toán cực đại) hay l  0(đối với bài toán cực tiểu) của ẩn không cơ bản thì sẽ xảy ra 1 trong hai trường hợp sau: a) Nếu có một hệ số ước lượng mà mọi kl a 0 thì bài toán không giải được. b) Nếu với mỗi hệ số ước lượng mà tồn tại ít nhất một akl  0 thì bài toán có phương án cơ bản mới tốt hơn. 5  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại a) Bước lặp thứ nhất a.1) Xác định ẩn CB, PACB xuất phát x0 và giá trị f(x0) của hàm mục tiêu tại PACB này. a.2) Lập bảng đơn hình (BDH) xuất phát như sau: 6 3
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại a) Bước lặp thứ nhất Các thành phần của BDH bao gồm: + Cột B: Ghi lần lượt theo thứ tự các ẩn CB của BT. + Cột A: Ghi tương ứng các hệ số của các ẩn CB trong HMT. + Cột C: Ghi các số hạng tự do tương ứng với các ẩn CB. + Cột D: Ghi ma trận điều kiện của hệ ràng buộc chính. + Hàng E: Ghi toàn bộ các ẩn của BT trong HMT. + Hàng F: Ghi hệ số tương ứng của các ẩn trong HMT. 7  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại a) Bước lặp thứ nhất Các thành phần của BDH bao gồm: + Hàng G: Tính trị số của các hệ số ước lượng (HSUL) các ẩn và trị số của HMT: m (Tổng của tích cột A với cột j rồi trừ đi  j   ci xi  c j hệ số của ẩn xj tại hàng F) và được ghi tương ứng ở hàng G của cột D. i 1 (Hệ số ước lượng của các ẩn cơ bản luôn bằng 0) m f ( x )   ci xi + N số 0 (Tổng của tích cột A với cột C) và hạng tự do (nếu có) và được i 1 ghi ở hàng G của cột C. 8 4
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại a) Bước lặp thứ nhất a.3) Đánh giá phương án cơ bản xuất phát: + Nếu tất cả các HSUL đều không âm thì PACB xuất phát đang xét là PATU của BT. Và thuật toán kết thúc. + Nếu tồn tại ít nhất 1 HSUL âm của ẩn không CB mà vector điều kiện của ẩn đó chứa các thành phần đều không dương thì bài toán không giải được. Thuật toán kết thúc với kết luận bài toán không có PATU. + Nếu không xảy ra 2 trường hợp trên thì ta sẽ đi xây dựng 1 PACB mới tốt hơn. Và ta tiếp tục thuật toán với bước lặp thứ 2. 9  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai 10 5
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.1) Tìm ẩn đưa vào: Ta tìm HSUL âm nhỏ nhất trong BDH hiện tại, giả sử là  m  k thì ẩn xm+k sẽ được chọn đưa vào hệ ẩn CB mới của BDH thứ hai. Khi đó, cột điều kiện Am+k = (a1m+k, a2m+k,…, amm+k) được gọi là cột chủ yếu. 11  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.2) Tìm ẩn đưa ra: Với các thành phần dương của vector đkiện, ta tiến hành tính các hệ số   a i  1, m và tìm ra hệ bi i imk số nhỏ nhất, giả sử là  r thì ẩn xr sẽ được đưa ra khỏi hệ CB trong BDH thứ hai. Dòng r được gọi là dòng chủ yếu. Hệ số nằm trên dòng chủ yếu & cột chủ yếu được gọi là hệ số chủ yếu, trong bảng đơn hình trên thì nó là arm+k. 12 6
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.3) Lập bảng đơn hình thứ hai: - Thay ẩn đưa ra bằng ẩn đưa vào và hệ số cũng được thay tương ứng. Các ẩn cơ bản khác và hệ số của các ẩn cơ bản đó được giữ nguyên không đổi. Khi đó, dòng có ẩn đưa vào được gọi là dòng chuẩn. - Lấy dòng chủ yếu của bảng đơn hình thứ nhất chia cho hệ số chủ yếu (arm+k) để ta có các thành phần của dòng chuẩn; tức là hệ số của ẩn trên dòng chuẩn được xác định bằng (và dĩ nhiên, hệ số của các ẩn cơ bản khác luôn bằng 0). 13  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.3) Lập bảng đơn hình thứ hai: - Đối với dòng i bất kỳ, ta tính hệ số của các ẩn không cơ bản như sau: br b  bi  aimk i d armk a d im  j  aim  j  aim  k arm  j arm  k i  1, m 14 7
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.3) Lập bảng đơn hình thứ hai: - Đối với dòng i bất kỳ, ta tính hệ số của các ẩn không cơ bản như sau: br bid  bi  aimk armk ad im  j  aim  j  aim  k arm  j arm  k i  1, m - Các hệ số ước lượng và giá trị hàm mục tiêu được tính như bước lặp thứ nhất. 15  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai d d b.3) Lập bảng đơn hình thứ hai: Vd về cách tính i b aim j Ghi chú: Mới = Cũ - Hệ số cột chủ yếu * Hệ số dòng chuẩn 16 8
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.3) Lập bảng đơn hình thứ hai: 17  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại b) Bước lặp thứ hai b.4) Đánh giá PACB thứ hai: Trong PACB thứ hai này, việc đánh giá xem nó có phải là tối ưu hay chưa, BT có giải được hay không, được thực hiện tương tự như việc đánh giá PACB xuất phát. Nếu BT không có dấu hiệu không giải được mà PACB thứ hai không phải là PACBTU thì ta tiếp tục thuật toán với bước lặp thứ ba. Và từ bước lặp thứ ba trở đi được thực hiện tương tự như bước lặp thứ hai. Nhưng các hệ số trong ma trận điều kiện và các số hạng tự do của BDH sau được tính dựa vào ma trận điều kiện và các số hạng tự do của bảng đơn hình ngay trước nó. 18 9
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại ***** CHÚ Ý: + Nếu các HSUL của các ẩn không CB trong BDH cuối cùng đều dương thì BT chỉ có duy nhất 1 PACBTU- đó là PACBTU vừa tìm được trong BDH cuối cùng. + Nếu các HSUL của các ẩn không CB trong BDH cuối cùng đều không âm, và tồn tại ít nhất 1 HSUL của ẩn không CB bằng 0 thì BT sẽ có   0, 1 vô số PATU: x  x 0  (1   ) x * ; 19  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc A. Giải BT cực đại ***** CHÚ Ý: + Nếu BT chuẩn được giải là BT phụ (có ẩn phụ) thì BT phụ có hay không có PATU sẽ làm cho BT gốc cũng có hay không có PATU tương ứng. Nếu BT phụ có PATU, PATU của BT gốc được rút ra từ BT phụ bằng cách bỏ đi phần ẩn phụ và đổi các trị số của biến mới về biến cũ theo các công thức đổi biến đã dùng. 20 10
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc B. Giải BT cực tiểu @ BT cực tiểu cũng được giải tương tự như BT cực đại nhưng cần chú ý đến HSUL trong BT cực tiểu như sau: + Điều kiện tối ưu của BT cực tiểu là:  j  0, j + Điều kiện BT không giải được là tồn tại ít nhất 1 HSUL của ẩn không CB dương và các thành phần của vector điều kiện tương ứng của ẩn đó đều không dương; tức là   0 & a  0 i  1, m j ij   + Ẩn được chọn đưa vào là ẩn ứng với HSUL dương lớn nhất. 21  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 4. Thuật toán đơn hình giải BTQHTT dạng chuẩn tắc B. Giải BT cực tiểu @ BT cực tiểu g(x) cũng có thể được giải theo BT cực đại f(x) với cách biến đổi HMT từ cực tiểu sang cực đại: g ( x)   f ( x) 22 11
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình 5.1) Giải BT sau bằng PP đơn hình: f ( x)   x1  4 x2  3x3  max 2 x1  x2  2 x3  16  4 x  2 x  8  1 3   x1  2 x2  x3  12  x1 , x2 , x3  0 23  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.1: Đưa bài toán trên về dạng chuẩn như sau: f ( x)   x1  4 x2  3 x3  max  2 x1  x 2  2 x3  x 4  16  4 x  2 x  x  8  1 3 5 x  x  x  x   1 2 2 3 6 12   x  0 i  1,6  i  Hệ ẩn CB: x4, x5 và x6 PACB xuất phát là x0 = (0, 0, 0, 16, 8, 12) 24 12
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.1: 25  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.1: Sau bước lặp thứ ba, ta có HSUL của ẩn x1 (là ẩn không CB) là -7 trong khi vector điều kiện của ẩn này đều có thành phần âm; cho nên BT phụ không giải được và do đó, BT gốc cũng không giải được (BT không có PATU). 26 13
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình 5.2) Giải BT sau bằng PP đơn hình f ( x)  5 x1  2 x2  3 x3  x4  min 2 x1  3 x2  2 x3  x4  14 4 x  2 x  3 x  38  1 2 3 3 x  2 x  21  1 3  x  0 i  1,4  i   27  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.2: Đưa bài toán về dạng chuẩn như sau: f ( x)  5x1  2 x2  3x3  x4  min  4 x1  3x2  2 x3  x4  x5  14 4 x  2 x  3x  x  38  1 2 3 6 3x  2 x  x  21  1 3 7  x  0 i  1,7  i  Hệ ẩn CB: x4, x6 và x7; PACB xuất phát: x0 = (0, 0, 0, 14, 0, 38, 21). 28 14
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.2: 29  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.2: Tại bước lặp thứ ba, ta có tất cả các HSUL đều không dương cho nên kết thúc thuật toán đơn hình. Khi đó, BT gốc có PATU là: x* = (0, 118/13, 86/13, 0); Trị số HMT đạt được là: f(x*) = -38. 30 15
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình 5.3) Giải BT sau bằng PP đơn hình f ( x)  25  3 x1  2 x2  4 x3  x4  max 4 x1  x2  3 x3  2 x4  14 2 x  2 x  x  5 x  x  4  1 2 3 4 5  x1  x2  2 x3  4 x4  5 x , x , x  0  1 3 4  x2  0 31  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.3: Đưa bài toán trên về dạng chính tắc bằng cách đặt: x2   x2 a ; x5  x5 a  x5b f ( x)  25  3 x1  2 x2 a  4 x3  x4  max 4 x1  x2 a  3x3  2 x4  x6  14 2 x  2 x  x  5 x  x  x  x  4  1 2a 3 4 5a 5b 7  x1  x2 a  2 x3  4 x4  x8  5  x  0 i  1, 3, 4, 6, 7, 8  i  x2 a , x5 a , x5b  0 Hệ ẩn CB: x5a, x6, và x8 PACB xuất phát x0 = (0, 0, 0, 0, 4, 0, 14, 0, 5) 32 16
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.3: 33  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 5. Các ví dụ về giải BTQHTT bằng PP Đơn hình Giải BT ví dụ 5.3: Tại bước lặp thứ hai, tất cả các HSUL của ẩn đều không âm. Như vậy, BT phụ có PACBTU là xs = (0, 0, 0, 5/4, 41/4, 0, 33/2, 0, 0) với trị số HMT là f(x) = 25 + 5/4 = 105/4. Khi đó, BT gốc sẽ có PATU là: x* = (0, 0, 0, 5/4, 41/4) và trị số HMT vẫn là f(x*) = 105/4. 34 17
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH Kinh nghiệm giải toán: @ Nếu ta có nhiều hơn 1 ẩn được chọn đưa vào hệ ẩn CB- tức là có nhiều hơn 1 HSUL âm bé nhất (BT cực đại) hoặc HSUL dương lớn nhất (BT cực tiểu)- thì ta sẽ chọn ẩn nào đây??? @ Nếu ta có nhiều hơn 1 ẩn được chọn đưa ra hệ ẩn CB- tức là có nhiều hơn 1 hệ số bêta bé nhất thì ta sẽ chọn ẩn nào đây??? 35  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 6. Thuật toán đơn hình mở rộng giải BT “M” Để giải bài toán “M”, chúng ta tiến hành qua hai bước: A. Giải bài toán mở rộng B. Tìm lời giải bài toán gốc. 36 18
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 6. Thuật toán đơn hình mở rộng giải BT “M” A. GIẢI BT MỞ RỘNG- BT “M” Do BT “M” là BT dạng chuẩn cho nên ta cũng giải BT “M” bằng PP đơn hình như đã trình bày ở trên. Tuy nhiên, do các ẩn giả xuất hiện trong hàm mục tiêu với hệ số M; cho nên HSUL của các ẩn sẽ có dạng là   aM  b ; và ta cần chú ý những vấn đề sau: @ Trong cột D của bảng đơn hình không cần thể hiện ẩn giả; 37  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 6. Thuật toán đơn hình mở rộng giải BT “M” @ Do M là một số dương vô cùng lớn, cho nên, trên BDH, dấu của HSUL phụ thuộc vào hệ số a của M trong HSUL đó. Việc so sánh giá trị của hai HSUL cần tuân theo qui tắc sau: - Hệ số a của M sẽ quyết định chính; tức là nếu a1 > a2 thì 1   2 bất kể giá trị b. - Nếu hệ số a bằng nhau thì hệ số b sẽ quyết định; tức là nếu b1 < b2 thì 1   2 . 38 19
 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 6. Thuật toán đơn hình mở rộng giải BT “M” @ Khi trong hệ ẩn CB không còn ẩn giả thì BT “M” trở thành BTQHTT thông thường. TÌM LỜI GIẢI CỦA BT GỐC 39  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 6. Thuật toán đơn hình mở rộng giải BT “M” B. TÌM LỜI GIẢI CỦA BT GỐC BT “M” và BT gốc có mối quan hệ như sau: @ Nếu BT “M” không giải được (không có PATU) thì BT gốc cũng không giải được. @ Nếu BT “M” có PATU nhưng tồn tại ít nhất 1 ẩn giả có giá trị dương thì BT gốc không giải được (không có PATU). @ Nếu BT “M” có PATU và các ẩn giả đều nhận giá trị 0 thì BT gốc giải được. PATU của BT “M” sau khi bỏ đi phần ẩn giả và thay thế ẩn phụ (nếu có) sẽ là PATU của BT gốc. 40 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.