Huong Dan Hoc

tập bài giảng giản yếu về quy hoạch tuyến tính

Vũ Trung Hiếu [email protected]

MỤC LỤC

Thứ tự

Tên

Trang

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

1

Bài 1. Các bài toán thực tế

1

Bài 2. Bài toán quy hoạch tuyến tính

5

Bài 3. Tính chất của tập phương án

12

Chương 2. Phương pháp đơn hình

23

Bài 1. Cơ sở lý luận của phương pháp đơn hình

23

Bài 2. Thuật toán đơn hình

32

Bài 3. Vấn đề tìm cơ sở xuất phát

41

Chương 3. Bài toán quy hoạch tuyến tính đối ngẫu

52

Bài 1. Bài toán đối ngẫu

52

Bài 2. Quan hệ giữa cặp bài toán đối ngẫu

57

Bài 3. Thuật toán đơn hình đối ngẫu Chương 4. Lý thuyết trò chơi và Quy hoạch tuyến tính Bài 1. Trò chơi ma trận Bài 2. Điểm yên ngựa và chiến lược tối ưu Bài 3. Quan hệ giữa lý thuyết trò chơi và Quy hoạch tuyến tính

Tập bài giảng này không phải là tài liệu chính thức, nó là bản nháp đầu tiên của tác giả, chưa được bất cứ một tổ chức hay cá nhân nào kiểm định. Do đó, thiếu sót là điều không thể tránh khỏi. Tất nhiên mọi khiếm khuyết đó thuộc về lỗi của tác giả. Tác giả hoan hỷ và mong mỏi đón nhận lời phê bình. Tháng 3 năm 2007.

Hướng dẫn học chương 1 và chương 2 Phương pháp chung: Bước 1. Đọc tài liệu trước khi nghe giảng, chú ý đến các khái niệm và ví dụ. Bước 2. Nghe giảng và thảo luận, đặt câu hỏi có liên quan. Bước 3. Đọc lại và thực hành, làm bài tập đã cho. Chưong 1, các bạn cần chú ý các vấn đề sau: Bài 1. Cần nắm được cách xây dựng mô hình toán học của một bài toán thực tiễn. Bài 2. Cần nắm vững các khái niệm và tính chất của hàm mục tiêu, tập phương án, đọc kỹ 2.1. Biết phân loại các dạng bài toán chính tắc, chuẩn tắc và cách đưa một bài toán tổng quát về dạng chính tắc hoặc chuẩn tắc, đọc kỹ 2.2. Cần đọc qua 2.3 để biết tư tưởng của phương pháp giải bài toán quy hoạch tuyến tính trong mặt phẳng. Bài 3. Đọc qua 3.1 và 3.2 để lấy kiến thức cơ bản về tập lồi. Đọc kỹ 3.3, định lý 1 và nắm được cách tìm phương án cực biên - chú ý ví dụ trong trang 19. Bắt buộc phải nắm được kết quả trong các định lý 2, 3, 4, 5 để vận dụng làm bài tập và làm cơ sở cho chương 2.. Chương 2, các bạn cần chú ý các vấn đề sau: Bài 1. Cần nắm được tư tưởng của phương pháp đơn hình, 1.1. Đọc kỹ 1.2, đặc biệt là các ký hiệu phải sử dụng thành thạo. Cần nắm rõ kết quả định lý 1 trong 3.3, nếu đọc hiểu chứng minh thì tốt hơn. Trong 1.4 và 1.5 thì cần nắm được kết quả định lý 3, nên đọc chứng minh, đọc kỹ ví dụ, thuộc các công thức 31 đến 34 để vận dụng. Bài 2. Nhớ được thuật toán và sơ đồ thuật toán đơn hình 2.1. Biết cách lập bảng đơn hình và sử dụng phương pháp đơn hình trên bảng thành thạo. Trong đó chú ý đến cách tìm cột xoay, hàng chuẩn và phần tử trục. Đọc kỹ 4 ví dụ mẫu. Bài 3. Đọc kỹ 3.2 và phương pháp đánh thuế - bài toán M, chú ý các ví dụ mẫu.

Chú ý: Sinh viên phải hoàn thành các bài tập cuối chương được giao đúng thời hạn.