Tối ưu hóa công nghệ thông tin

NỘI DUNG THẢO LUẬN Trình bày các nội dung sau Thế nào là phương án cực biên, điều kiện cần và đủ để một phương án là phương án cực biên? Cho bài toán QHTT sau: Trong các phương án sau, phương án nào là phương án cực biên, phương án cực biên tối ưu của bài toán Thuật toán đơn hình: Tư tưởng của thuật toán, lưu đồ thuật toán Áp dụng thuật toán đơn hình giải các bài toán sau f(x) = 5x1 + x2 - 2x3 + 5x4 -> MAX x1 - x2 + 2x3 + x5 = 7 2x1 + x2 + 3x3 -3x4 + x6 = 9 3x1 -2x2 + x3 + x4 + x7 = 6 xj >=0, j=1,…,6 Trình bày các nội dung sau Khi nào thì bài toán QHTT có phương án tối ưu? Chứng minh rằng bài toán sau có phương án tối ưu Thuật toán đơn hình hai pha: Tư tưởng, lưu đồ thuật toán, các bươc thực hiện thuật toán Thế nào là hiện tượng xoay vòng? Trình bày phương pháp nhiễu loạn khắc phục hiện tượng xoay vòng? Áp dụng thuật toán đơn hình hai pha giải các bài toán sau Đáp số: x* = (0,0,16,31,14), f(x*)=7 Đáp số: Bài toán không có phương án Trình bày các nội dung sau Cơ sở của một phương án cực biên? Thế nào là phương án cực biên suy biến. Chứng tỏ rằng phương án là phương án cực biên suy biến tối ưu của bài toán Thuật toán đánh thuế: Tư tưởng, lưu đồ thuật toán So sánh 2 thuật toán: hai pha và đánh thuế. Áp dụng thuật toán đánh thuế giải các bài toán sau Đáp số: x* = (0,1,2) Đáp số: Bài toán không có phương án tối ưu Trình bày các nội dung sau Bài toán đối ngẫu, các qui tắc thiết lập bài toán đối ngẫu. Thuật toán đơn hình đối ngẫu: Tư tưởng, lưu đồ thuật toán. Tìm bài toán đối ngẫu của bài toán sau đây. Giải bài toán gốc bằng thuật toán đơn hình đối ngẫu và suy ra kết quả của bài toán đối ngẫu tương ứng Chứng tỏ là một cơ sở đối ngẫu và giải bài toán sau đây bằng thuật toán đơn hình đối ngẫu Trình bày các nội dung sau Các định lý đối ngẫu, ý nghĩa của định lý yếu về độ lêch bù, cho ví dụ. H Hiện tượng xoay vòng? Trình bày phương pháp nhiễu loạn khắc phục hiện tượng xaoy vòng. Giải bài toán sau Trình bày các nội dung sau Trình bày ý nghĩa thực tế của bài toán đối ngẫu, định lý yếu về độ lệch bù, ý nghĩa và tính ứng dụng của nó? Cho bài toán Chứng tỏ rằng là phương án tối ưu của bài toán đã cho. Tìm tập phương án tối ưu của bài toán đối ngẫu. Tìm bài toán đối ngẫu của bài toán sau đây. Giải bài toán gốc bằng thuật toán đơn hình đối ngẫu và suy ra kết quả của bài toán đối ngẫu tương ứng Trình bày các nội dung sau Khi nào thì bài toán QHTT có phương án tối ưu? Chứng minh rằng bài toán sau có phương án tối ưu Thế nào là hiện tượng xoay vòng, trình bày phương pháp từ vựng khắc phục hiện tượng xoay vòng, cho ví dụ. Vẽ lưu đồ thuật toán đơn hình có sử dụng phương pháp từ vựng Giải bài toán QHTT sau đây Đáp số: x*=(32,0,30,0,0), f(x*)=184 Trình bày các nội dung sau Thế nào là phương án tối ưu? Chứng minh rằng, đối với mỗi bài toán sau , là phương án tối ưu: Trình bày tư tưởng của phương pháp hình học, vẽ lưu đồ thuật toán hình học, lấy các ví dụ minh họa cho các trường hợp có nghiệm duy nhất, vô số nghiệm, không có nghiệm tối ưu khi giải bài toán bằng phương pháp hình học. Trình bày điều kiện cần khi giải bài toán QHTT bằng phương pháp đơn hình, điều kiện cần khi giải bài toán bằng phương pháp đơn hình đối ngẫu. Nêu cách khắc phục khi bài toán không thỏa mãn các điều kiện cần đó. Giải bài toán QHTT sau bằng phương pháp đơn hình đối ngẫu Yêu cầu: Các nhóm bốc thăm nội dung thảo luận. Mỗi tiết thảo luận: Hai nhóm báo cáo. Chuẩn bị nội dung báo cáo bằng các Slides. Các nhóm phân công người trình bày các nội dung. Trả lời các câu hỏi của giảng viên và của các nhóm khác. Điểm thảo luận: Cho điểm từng thành viên của mỗi nhóm.