sodepgiadep
New Member
Link tải luận văn miễn phí cho ae Kết Nối
MỤC LỤC
LỜI CẢM ƠN . 1
MỤC LỤC . 2
MỞ ĐẦU . 4
CHƯƠNG 1. TỐI ƯU RỜI RẠC VÀ MỘT SỐHƯỚNG TIẾP CẬN . 6
1.1. BÀI TOÁN TỐI ƯU .6
1.1.1. Dạng tổng quát của bài toán tối ưu .6
1.1.2. Phân loại các bài toán tối ưu .7
1.2. CÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠC .8
1.2.1. Phương pháp cắt Gomory .9
1.2.2. Phương pháp nhánh cận Land – Doig .13
1.3. BÀI TOÁN LUỒNG TRÊN MẠNG.15
1.3.1. Luồng trên mạng .15
1.3.2. Phân loại các thuật toán luồng trên mạng .16
1.3.3. Thuật toán tìm luồng cực đại trong mạng .17
1.4. ĐỘPHỨC TẠP CỦA CÁC BÀI TOÁN TỐI ƯU RỜI RẠC .20
CHƯƠNG 2. THUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN LẬP LỊCH . 22
2.1. BÀI TOÁN LẬP LỊCH .22
2.1.1. Mô hình toán học của bài toán lập lịch .22
2.1.2. Một sốbài toán lập lịch .23
2.1.3. Tính chất nghiệm của bài toán (P) .24
2.2. THUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN (P) .27
2.3. THUẬT TOÁN ĐA THỨC DẠNG BẢNG GIẢI BÀI TOÁN (P) .33
2.3.1. Cơsởphương pháp giải .33
2.3.2. Thuật toán.36
2.3.3. Độphức tạp của thuật toán.40
2.3.4. Ví dụminh họa .41
2.3.5. Cài đặt và thửnghiệm trên máy tính .46
CHƯƠNG 3. ỨNG DỤNG BÀI TOÁN LẬP LỊCH VÀO THỰC TẾ . 49
3.1. WEBSITE ĐĂNG KÝ MÔN HỌC TỰCHỌN .49
3.1.1. Giới thiệu.49
3.1.2. Mô hình ứng dụng .50
3.2. XÂY DỰNG WEBSITE.52
3.2.1. Các thành phần chính xây dựng website .52
3.2.2. Sơ đồchức năng .53
3.2.3. Tổchức chương trình .54
3.2.4. Cài đặt thuật toán .55
3.3. MỘT SỐKẾT QUẢTHỬNGHIỆM .59
3.3.1. Môi trường thửnghiệm .59
3.3.2. Giao diện website .59
3.3.3. Một sốthửnghiệm khác .62
CHƯƠNG 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN . 65
TÀI LIỆU THAM KHẢO . 67
PHỤLỤC . 68
CHƯƠNG 1.
3BTỐI ƯU RỜI RẠC VÀ MỘT SỐ HƯỚNG TIẾP CẬN
1.1. 8B ÀI TOÁN TỐI ƯU
Tối ưu hóa là một ngành toán học ứng dụng, đã và đang được nhiều người
quan tâm nghiên cứu, tìm hiểu và ứng dụng vào thực tiễn. Bài toán tối ưu là kết quả
của việc mô hình hóa những vấn đề nảy sinh từ thực tế, chúng có thể được diễn đạt
dưới dạng toán học là tìm các biến số thỏa mãn những điều kiện nhất định và làm
cho một hàm số cho trước đạt giá trị cực tiểu hay cực đại.
1.1.1. 18BDạng tổng quát của bài toán tối ưu
Tìm vectơ 1( ,... ,..., )k nx x x x= thỏa mãn:
f(x) Æ min(max) (1.1)
với điều kiện
≤( ) 0ig x , i = 1, 2, ..., p (1.2)
( ) 0jh x = , j = 1, 2, ..., q (1.3)
x ∈ X ⊂ RPnP, k = 1, 2, …, n (1.4)
Trong đó f, gRiR, hRjR (i = 1, 2, …, p; j = 1, 2, …, q) là các hàm số cho trước của n
biến số (f, gRiR, hRjR: R Pn P Æ R) và X ⊂ RPnP là tập đóng, thường có dạng
X = +
nR ≡ {x ∈ RPnP : xRjR ≥ 0, j = 1, 2, …, n}
Bài toán (1.1) – (1.4) có tên gọi là bài toán quy hoạch toán học. Hàm f(x)
được gọi là hàm mục tiêu, còn gRiR(x) và hRjR(x) là các hàm ràng buộc và ràng buộc
dạng xRjR ≥ 0, j = 1, 2, …, n, được gọi là các ràng buộc về dấu. Tập hợp:
D = { x ∈ X: ≤( ) 0ig x , i = 1, 2, ..., p; ( ) 0jh x = , j = 1, 2, ..., q},
7
gọi là miền ràng buộc hay miền chấp nhận được. Mỗi véctơ x ∈ D được gọi là một
phương án hay một lời giải chấp nhận được của bài toán. Phương án làm cho hàm
số f(x) đạt giá trị cực tiểu hay cực đại được gọi là phương án tối ưu hay lời giải
của bài toán.
1.1.2. 19BPhân loại các bài toán tối ưu
Các bài toán tối ưu nói chung rất phong phú và đa dạng. Để tìm lời giải cho
các bài toán này, có thể có một cách chung và đơn giản nhất là duyệt toàn bộ các
phương án có thể có của bài toán đặt ra để chọn phương án tối ưu. Song do số
phương án của các bài toán dạng này thường là một số rất lớn, thậm chí không đếm
được, nên cách làm này không phải bao giờ cũng thực hiện được, ngay cả khi kích
thước của bài toán không lớn lắm. Vì thế cần có những nghiên cứu về mặt lý
thuyết để tách ra những lớp bài toán riêng, khai thác cấu trúc đặc thù của nó để đề ra
phương pháp giải thích hợp. Sau đây là một số lớp bài toán tối ưu thường gặp:
- Quy hoạch tuyến tính: Khi hàm mục tiêu f(x) và tất cả các hàm ràng buộc
gRiR(x), hRjR(x) là tuyến tính, tập X là tập lồi đa diện (giao của một số hữu hạn các nửa
không gian đóng).
- Quy hoạch tham số: Khi các hệ số trong biểu thức của hàm mục tiêu và của
các ràng buộc phụ thuộc tham số.
- Quy hoạch phi tuyến: Khi hàm mục tiêu f(x) hay tồn tại ít nhất một trong
các hàm ràng buộc gRiR(x), hRjR(x) không phải là tuyến tính, hay tập X khác tập lồi
đa diện.
- Quy hoạch lồi: Khi hàm mục tiêu f(x) là hàm lồi (nếu xét bài toán tìm cực
tiểu) và miền ràng buộc D là tập hợp lồi.
- Quy hoạch lõm: Khi hàm mục tiêu f(x) là hàm lõm (nếu xét bài toán tìm cực
tiểu) và miền ràng buộc D là tập hợp lồi.
- Tối ưu rời rạc: Khi X là tập rời rạc. Các bài toán tối ưu rời rạc thường xuất
hiện khi nghiên cứu các quá trình hay đối tượng rời rạc. Trong trường hợp riêng khi
8
các biến chỉ nhận giá trị nguyên ta có quy hoạch nguyên. Một trường hợp riêng của
quy hoạch nguyên là quy hoạch Boole, khi mà các biến số chỉ nhận giá trị 0 hay 1.
Có thể chứng minh rằng: mọi bài toán tối ưu rời rạc đều có thể đưa về bài
toán quy hoạch Boole. Thật vậy, giả sử biến số x chỉ có thể lấy một trong các giá trị
cho trước aR1R, aR2R, …, aRkR. Khi đó bằng cách đặt:
x = aR1RuR1R + aR2RuR2R + … + aRkRuRk R,
uR1R + uR2R + …+ uRkR = 1, uRj R∈ {0, 1}, j = 1, 2, …, k
thì biến rời rạc x có thể thay thế bởi một số biến uRjR chỉ nhận giá trị 0 hay 1, gọi tắt là
biến 0-1 hay biến Boole.
Tương tự, nếu x ∈ {0, 1, …, k} thì ta có thể viết:
x = uR1R + uR2R + …+ uRkR với uRj R∈ {0, 1}, j = 1, 2, …, k
nghĩa là bất kỳ bài toán với các biến nguyên bị chặn tùy ý, đều có thể quy về bài
toán với các biến 0-1. Điều này cho thấy bài toán quy hoạch nguyên 0-1 giữ vai trò
quan trọng trong tối ưu rời rạc.
1.2. 9BCÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠC
Tối ưu rời rạc hay còn gọi là tối ưu tổ hợp là một lĩnh vực quan trọng trong
lý thuyết tối ưu hóa. Các bài toán tối ưu nói chung và các bài toán tối ưu tổ hợp nói
riêng rất phong phú và đa dạng. Chúng có nhiều ứng dụng rộng rãi trong thực tiễn.
Sau đây là một số công cụ thường dùng trong tối ưu tổ hợp. Đó là các
phương pháp cắt nổi tiếng của Gomory và phương pháp “nhánh và cận” rất có hiệu
quả với nhiều biến dạng khác nhau cho các bài toán cụ thể: phương pháp quy hoạch
động, phương pháp tìm kiếm ngẫu nhiên…
9
1.2.1. 20BPhương pháp cắt Gomory
Xét bài toán quy hoạch tuyến tính có thêm điều kiện nguyên, gọi là bài toán
quy hoạch nguyên tuyến tính.
0
1
n
j j
j
x c x
=
= ∑ → min
với các ràng buộc:
∑
=
n
j
jij xa
1
= bRiR , i = 1, 2, ..., m;
xRjR ≥ 0, j = 1, 2, ..., n;
xRjR nguyên, j = 1, 2, ..., nR1R ≤ n
Nếu nR1R = n ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu nR1R < n thì có
bài toán quy hoạch nguyên bộ phận.
Gomory là người đầu tiên đưa ra các thuật toán cắt giải quy hoạch nguyên
tuyến tính. Ý đại thể của phương pháp Gomory như sau: giải quy hoạch tuyến tính
không có điều kiện nguyên, nếu bài toán này không có lời giải thì bài toán nguyên
cũng không có lời giải. Nếu bài toán có lời giải và lời giải đó thỏa điều kiện nguyên
thì đó là lời giải của bài toán nguyên, còn nếu lời giải đó không nguyên thì ta sẽ
thêm vào một ràng buộc tuyến tính mới, cắt bỏ lời giải không nguyên này và vẫn
giữ lại các điểm nguyên của miền ràng buộc. Ràng buộc thêm vào như thế gọi là
siêu phẳng cắt hay lát cắt. Rồi lại giải quy hoạch tuyến tính tương ứng (không có
điều kiện nguyên)... Với những điều kiện nhất định, quá trình trên sẽ dẫn đến lời
giải nguyên sau một số hữu hạn bước lặp.
Để áp dụng được phương pháp Gomory, cần có các giả thiết sau đây:
a) Hàm mục tiêu 0x bị chặn dưới (đối với bài toán min) trên miền ràng
buộc không có điều kiện nguyên.
10
b) Tập phương án tối ưu (lời giải) của bài toán tuyến tính không có điều
kiện nguyên nếu khác rỗng thì phải bị chặn.
c) 0x đòi hỏi phải nguyên (chẳng hạn, mọi cRjR nguyên).
d) Có một trong hai điều kiện sau:
- Hàm mục tiêu xR0R bị chặn trên miền ràng buộc không có
điều kiện nguyên.
- Bài toán có phương án (điểm) nguyên.
Tóm lại, các điều kiện trên sẽ được thỏa mãn nếu miền ràng buộc (không kể
điều kiện nguyên) là bị chặn và các hệ số aRijR, bRiR, cRjR đều nguyên.
Có ba cách khác nhau thể hiện ý tưởng phương pháp giải nêu trên.
1.2.1.1. 42BThuật giải Gomory 1
Thuật toán này áp dụng cho bài toán quy hoạch nguyên hoàn toàn (nR1R = n).
Nội dung thuật toán như sau: Áp dụng phương pháp đơn hình đối ngẫu từ
vựng giải quy hoạch tuyến tính không có điều kiện nguyên, nếu bài toán không giải
được thì bài toán nguyên cũng không giải được. Nếu bài toán giải được và lời giải
thỏa m
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
LỜI CẢM ƠN . 1
MỤC LỤC . 2
MỞ ĐẦU . 4
CHƯƠNG 1. TỐI ƯU RỜI RẠC VÀ MỘT SỐHƯỚNG TIẾP CẬN . 6
1.1. BÀI TOÁN TỐI ƯU .6
1.1.1. Dạng tổng quát của bài toán tối ưu .6
1.1.2. Phân loại các bài toán tối ưu .7
1.2. CÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠC .8
1.2.1. Phương pháp cắt Gomory .9
1.2.2. Phương pháp nhánh cận Land – Doig .13
1.3. BÀI TOÁN LUỒNG TRÊN MẠNG.15
1.3.1. Luồng trên mạng .15
1.3.2. Phân loại các thuật toán luồng trên mạng .16
1.3.3. Thuật toán tìm luồng cực đại trong mạng .17
1.4. ĐỘPHỨC TẠP CỦA CÁC BÀI TOÁN TỐI ƯU RỜI RẠC .20
CHƯƠNG 2. THUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN LẬP LỊCH . 22
2.1. BÀI TOÁN LẬP LỊCH .22
2.1.1. Mô hình toán học của bài toán lập lịch .22
2.1.2. Một sốbài toán lập lịch .23
2.1.3. Tính chất nghiệm của bài toán (P) .24
2.2. THUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN (P) .27
2.3. THUẬT TOÁN ĐA THỨC DẠNG BẢNG GIẢI BÀI TOÁN (P) .33
2.3.1. Cơsởphương pháp giải .33
2.3.2. Thuật toán.36
2.3.3. Độphức tạp của thuật toán.40
2.3.4. Ví dụminh họa .41
2.3.5. Cài đặt và thửnghiệm trên máy tính .46
CHƯƠNG 3. ỨNG DỤNG BÀI TOÁN LẬP LỊCH VÀO THỰC TẾ . 49
3.1. WEBSITE ĐĂNG KÝ MÔN HỌC TỰCHỌN .49
3.1.1. Giới thiệu.49
3.1.2. Mô hình ứng dụng .50
3.2. XÂY DỰNG WEBSITE.52
3.2.1. Các thành phần chính xây dựng website .52
3.2.2. Sơ đồchức năng .53
3.2.3. Tổchức chương trình .54
3.2.4. Cài đặt thuật toán .55
3.3. MỘT SỐKẾT QUẢTHỬNGHIỆM .59
3.3.1. Môi trường thửnghiệm .59
3.3.2. Giao diện website .59
3.3.3. Một sốthửnghiệm khác .62
CHƯƠNG 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN . 65
TÀI LIỆU THAM KHẢO . 67
PHỤLỤC . 68
CHƯƠNG 1.
3BTỐI ƯU RỜI RẠC VÀ MỘT SỐ HƯỚNG TIẾP CẬN
1.1. 8B ÀI TOÁN TỐI ƯU
Tối ưu hóa là một ngành toán học ứng dụng, đã và đang được nhiều người
quan tâm nghiên cứu, tìm hiểu và ứng dụng vào thực tiễn. Bài toán tối ưu là kết quả
của việc mô hình hóa những vấn đề nảy sinh từ thực tế, chúng có thể được diễn đạt
dưới dạng toán học là tìm các biến số thỏa mãn những điều kiện nhất định và làm
cho một hàm số cho trước đạt giá trị cực tiểu hay cực đại.
1.1.1. 18BDạng tổng quát của bài toán tối ưu
Tìm vectơ 1( ,... ,..., )k nx x x x= thỏa mãn:
f(x) Æ min(max) (1.1)
với điều kiện
≤( ) 0ig x , i = 1, 2, ..., p (1.2)
( ) 0jh x = , j = 1, 2, ..., q (1.3)
x ∈ X ⊂ RPnP, k = 1, 2, …, n (1.4)
Trong đó f, gRiR, hRjR (i = 1, 2, …, p; j = 1, 2, …, q) là các hàm số cho trước của n
biến số (f, gRiR, hRjR: R Pn P Æ R) và X ⊂ RPnP là tập đóng, thường có dạng
X = +
nR ≡ {x ∈ RPnP : xRjR ≥ 0, j = 1, 2, …, n}
Bài toán (1.1) – (1.4) có tên gọi là bài toán quy hoạch toán học. Hàm f(x)
được gọi là hàm mục tiêu, còn gRiR(x) và hRjR(x) là các hàm ràng buộc và ràng buộc
dạng xRjR ≥ 0, j = 1, 2, …, n, được gọi là các ràng buộc về dấu. Tập hợp:
D = { x ∈ X: ≤( ) 0ig x , i = 1, 2, ..., p; ( ) 0jh x = , j = 1, 2, ..., q},
7
gọi là miền ràng buộc hay miền chấp nhận được. Mỗi véctơ x ∈ D được gọi là một
phương án hay một lời giải chấp nhận được của bài toán. Phương án làm cho hàm
số f(x) đạt giá trị cực tiểu hay cực đại được gọi là phương án tối ưu hay lời giải
của bài toán.
1.1.2. 19BPhân loại các bài toán tối ưu
Các bài toán tối ưu nói chung rất phong phú và đa dạng. Để tìm lời giải cho
các bài toán này, có thể có một cách chung và đơn giản nhất là duyệt toàn bộ các
phương án có thể có của bài toán đặt ra để chọn phương án tối ưu. Song do số
phương án của các bài toán dạng này thường là một số rất lớn, thậm chí không đếm
được, nên cách làm này không phải bao giờ cũng thực hiện được, ngay cả khi kích
thước của bài toán không lớn lắm. Vì thế cần có những nghiên cứu về mặt lý
thuyết để tách ra những lớp bài toán riêng, khai thác cấu trúc đặc thù của nó để đề ra
phương pháp giải thích hợp. Sau đây là một số lớp bài toán tối ưu thường gặp:
- Quy hoạch tuyến tính: Khi hàm mục tiêu f(x) và tất cả các hàm ràng buộc
gRiR(x), hRjR(x) là tuyến tính, tập X là tập lồi đa diện (giao của một số hữu hạn các nửa
không gian đóng).
- Quy hoạch tham số: Khi các hệ số trong biểu thức của hàm mục tiêu và của
các ràng buộc phụ thuộc tham số.
- Quy hoạch phi tuyến: Khi hàm mục tiêu f(x) hay tồn tại ít nhất một trong
các hàm ràng buộc gRiR(x), hRjR(x) không phải là tuyến tính, hay tập X khác tập lồi
đa diện.
- Quy hoạch lồi: Khi hàm mục tiêu f(x) là hàm lồi (nếu xét bài toán tìm cực
tiểu) và miền ràng buộc D là tập hợp lồi.
- Quy hoạch lõm: Khi hàm mục tiêu f(x) là hàm lõm (nếu xét bài toán tìm cực
tiểu) và miền ràng buộc D là tập hợp lồi.
- Tối ưu rời rạc: Khi X là tập rời rạc. Các bài toán tối ưu rời rạc thường xuất
hiện khi nghiên cứu các quá trình hay đối tượng rời rạc. Trong trường hợp riêng khi
8
các biến chỉ nhận giá trị nguyên ta có quy hoạch nguyên. Một trường hợp riêng của
quy hoạch nguyên là quy hoạch Boole, khi mà các biến số chỉ nhận giá trị 0 hay 1.
Có thể chứng minh rằng: mọi bài toán tối ưu rời rạc đều có thể đưa về bài
toán quy hoạch Boole. Thật vậy, giả sử biến số x chỉ có thể lấy một trong các giá trị
cho trước aR1R, aR2R, …, aRkR. Khi đó bằng cách đặt:
x = aR1RuR1R + aR2RuR2R + … + aRkRuRk R,
uR1R + uR2R + …+ uRkR = 1, uRj R∈ {0, 1}, j = 1, 2, …, k
thì biến rời rạc x có thể thay thế bởi một số biến uRjR chỉ nhận giá trị 0 hay 1, gọi tắt là
biến 0-1 hay biến Boole.
Tương tự, nếu x ∈ {0, 1, …, k} thì ta có thể viết:
x = uR1R + uR2R + …+ uRkR với uRj R∈ {0, 1}, j = 1, 2, …, k
nghĩa là bất kỳ bài toán với các biến nguyên bị chặn tùy ý, đều có thể quy về bài
toán với các biến 0-1. Điều này cho thấy bài toán quy hoạch nguyên 0-1 giữ vai trò
quan trọng trong tối ưu rời rạc.
1.2. 9BCÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠC
Tối ưu rời rạc hay còn gọi là tối ưu tổ hợp là một lĩnh vực quan trọng trong
lý thuyết tối ưu hóa. Các bài toán tối ưu nói chung và các bài toán tối ưu tổ hợp nói
riêng rất phong phú và đa dạng. Chúng có nhiều ứng dụng rộng rãi trong thực tiễn.
Sau đây là một số công cụ thường dùng trong tối ưu tổ hợp. Đó là các
phương pháp cắt nổi tiếng của Gomory và phương pháp “nhánh và cận” rất có hiệu
quả với nhiều biến dạng khác nhau cho các bài toán cụ thể: phương pháp quy hoạch
động, phương pháp tìm kiếm ngẫu nhiên…
9
1.2.1. 20BPhương pháp cắt Gomory
Xét bài toán quy hoạch tuyến tính có thêm điều kiện nguyên, gọi là bài toán
quy hoạch nguyên tuyến tính.
0
1
n
j j
j
x c x
=
= ∑ → min
với các ràng buộc:
∑
=
n
j
jij xa
1
= bRiR , i = 1, 2, ..., m;
xRjR ≥ 0, j = 1, 2, ..., n;
xRjR nguyên, j = 1, 2, ..., nR1R ≤ n
Nếu nR1R = n ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu nR1R < n thì có
bài toán quy hoạch nguyên bộ phận.
Gomory là người đầu tiên đưa ra các thuật toán cắt giải quy hoạch nguyên
tuyến tính. Ý đại thể của phương pháp Gomory như sau: giải quy hoạch tuyến tính
không có điều kiện nguyên, nếu bài toán này không có lời giải thì bài toán nguyên
cũng không có lời giải. Nếu bài toán có lời giải và lời giải đó thỏa điều kiện nguyên
thì đó là lời giải của bài toán nguyên, còn nếu lời giải đó không nguyên thì ta sẽ
thêm vào một ràng buộc tuyến tính mới, cắt bỏ lời giải không nguyên này và vẫn
giữ lại các điểm nguyên của miền ràng buộc. Ràng buộc thêm vào như thế gọi là
siêu phẳng cắt hay lát cắt. Rồi lại giải quy hoạch tuyến tính tương ứng (không có
điều kiện nguyên)... Với những điều kiện nhất định, quá trình trên sẽ dẫn đến lời
giải nguyên sau một số hữu hạn bước lặp.
Để áp dụng được phương pháp Gomory, cần có các giả thiết sau đây:
a) Hàm mục tiêu 0x bị chặn dưới (đối với bài toán min) trên miền ràng
buộc không có điều kiện nguyên.
10
b) Tập phương án tối ưu (lời giải) của bài toán tuyến tính không có điều
kiện nguyên nếu khác rỗng thì phải bị chặn.
c) 0x đòi hỏi phải nguyên (chẳng hạn, mọi cRjR nguyên).
d) Có một trong hai điều kiện sau:
- Hàm mục tiêu xR0R bị chặn trên miền ràng buộc không có
điều kiện nguyên.
- Bài toán có phương án (điểm) nguyên.
Tóm lại, các điều kiện trên sẽ được thỏa mãn nếu miền ràng buộc (không kể
điều kiện nguyên) là bị chặn và các hệ số aRijR, bRiR, cRjR đều nguyên.
Có ba cách khác nhau thể hiện ý tưởng phương pháp giải nêu trên.
1.2.1.1. 42BThuật giải Gomory 1
Thuật toán này áp dụng cho bài toán quy hoạch nguyên hoàn toàn (nR1R = n).
Nội dung thuật toán như sau: Áp dụng phương pháp đơn hình đối ngẫu từ
vựng giải quy hoạch tuyến tính không có điều kiện nguyên, nếu bài toán không giải
được thì bài toán nguyên cũng không giải được. Nếu bài toán giải được và lời giải
thỏa m
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: