Mô Hình Toán Học Trong Quy Hoạch Tuyến Tính

Quy hoạch tuyến tính là phân ngành quan trọng của toán học ứng dụng và nghiên cứu vận hành. 116 trang · Hutech.

• Trường học: Hutech
• Chuyên ngành: Quy Hoạch Tuyến Tính
• Đề tài: Mô Hình Toán Học Trong Quy Hoạch Tuyến Tính
• Loại tài liệu: bài tập

Mục lục chi tiết

• HƯỚNG DẪN
• 1. BÀI 1: GIỚI THIỆU VỀ BÀI TOÁN TUH VÀ QHTT
• 1.1. GIỚI THIỆU VỀ BÀI TOÁN QHTT VÀ PHƯƠNG PHÁP LẬP MÔ HÌNH
• 1.2. CÁC DẠNG CỦA BÀI TOÁN QHTT
• 1.3. CÁC ĐỊNH LÝ TỒN TẠI NGHIỆM, MỘT SỐ TÍNH CHẤT
• 2. BÀI 2: PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QHTT HAI BIẾN
• 2.1. BIỂU DIỄN ĐẲNG THỨC, BẤT ĐẲNG THỨC HAI BIẾN TRÊN ĐỒ THỊ
• 2.2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QHTT CÓ HAI BIẾN
• 3. BÀI 3: THUẬT TOÁN ĐƠN HÌNH GIẢI BÀI TOÁN QHTT NHIỀU BIẾN
• 3.1. CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH
• 4. BÀI 4: THUẬT TOÁN ĐƠN HÌNH MỞ RỘNG
• 5. BÀI 5: BÀI TOÁN ĐỐI NGẪU
• 6. BÀI 6: BÀI TOÁN ĐỐI NGẪU (TT)
• 7. BÀI 7: BÀI TOÁN VẬN TẢI, ỨNG DỤNG VÀ MÔ HÌNH TOÁN HỌC
• 7.1. BÀI TOÁN VẬN TẢI DẠNG TỔNG QUÁT
• 7.2. CÁC TÍNH CHẤT VÀ TIÊU CHUẨN TỐI ƯU CỦA BÀI TOÁN VẬN TẢI
• 8. BÀI 8: THUẬT TOÁN TÌM NGHIỆM XUẤT PHÁT, THUẬT TOÁN THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI
• 8.1. CÁC PHƯƠNG PHÁP TÌM PHƯƠNG ÁN CỰC BIÊN ĐẦU TIÊN CỦA BÀI TOÁN VẬN TẢI
• 8.2. THUẬT GIẢI THẾ VỊ CHO BÀI TOÁN VẬN TẢI
• 9. BÀI 9: MỞ RỘNG BÀI TOÁN VẬN TẢI
• 9.1. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU - PHÁT
• BÀI TẬP
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về mô hình toán học trong quy hoạch tuyến tính

Quy hoạch tuyến tính là phân ngành quan trọng của toán học ứng dụng và nghiên cứu vận hành. Ngành này tập trung giải quyết bài toán phân bổ nguồn lực hữu hạn nhằm đạt hiệu quả tối đa. Việc xây dựng mô hình toán học là bước khởi đầu mang tính quyết định. Mô hình chuyển đổi các vấn đề thực tiễn phức tạp thành ngôn ngữ đại số chính xác. Một bài toán quy hoạch tuyến tính hoàn chỉnh phản ánh đầy đủ mối quan hệ giữa mục tiêu kinh tế và giới hạn thực tế. Hệ thống phương trình và bất phương trình bậc nhất thiết lập khuôn khổ phân tích logic. Mô hình giúp loại bỏ tính cảm tính trong quá trình ra quyết định quản lý. Các nhà quản trị sử dụng công cụ này để dự báo kết quả hoạt động sản xuất, kinh doanh và điều phối vận tải. Độ chính xác của mô hình phụ thuộc vào việc xác định biến số và tham số. Nắm vững bản chất toán học giúp khai thác tối đa sức mạnh của các thuật toán tối ưu hóa hiện đại.

1.1. Khái niệm cơ bản về quy hoạch tuyến tính

Quy hoạch tuyến tính nghiên cứu các bài toán cực trị với hàm mục tiêu tuyến tính. Toàn bộ mối liên hệ giữa các biến số đều mang tính chất tỉ lệ thuận hoặc tuyến tính bậc nhất. Thuật ngữ tuyến tính biểu thị việc các biến xuất hiện với bậc một, không có tích chéo hay hàm phi tuyến. Quy hoạch thể hiện quy trình lập kế hoạch tối ưu dựa trên cơ sở khoa học định lượng. Miền chấp nhận được của bài toán tạo thành một tập lồi đa diện trong không gian n chiều. Nghiệm tối ưu luôn tồn tại tại ít nhất một đỉnh hoặc một cạnh của đa diện này. Lý thuyết quy hoạch tuyến tính cung cấp nền tảng toán học vững chắc cho phân tích quyết định hiện đại.

1.2. Vai trò của mô hình hóa toán học

Mô hình hóa toán học đóng vai trò cầu nối giữa thực tế sản xuất và lý thuyết tối ưu. Công cụ này chuẩn hóa các thông số kinh tế kỹ thuật thành hệ thống phương trình rõ ràng. Việc trừu tượng hóa bài toán thực tế giúp người phân tích loại bỏ các yếu tố nhiễu không cần thiết. Mô hình cho phép chạy các mô phỏng thử nghiệm với chi phí rủi ro bằng không. Nhờ đó, doanh nghiệp kiểm tra được tính khả thi của các kế hoạch kinh doanh trước khi triển khai. Các nhà quản lý cũng dễ dàng thực hiện phân tích độ nhạy khi dữ liệu đầu vào biến động. Quá trình mô hình hóa nâng cao năng lực kiểm soát và hoạch định chiến lược dài hạn.

II. Phân tích cấu trúc mô hình toán học trong quy hoạch tuyến tính

Thiết lập cấu trúc chuẩn xác là yếu tố then chốt giúp mô hình phản ánh đúng bản chất bài toán. Một mô hình toán học hoàn chỉnh luôn bao gồm ba thành phần cơ bản gắn kết chặt chẽ. Thành phần thứ nhất là hệ biến quyết định thể hiện các đại lượng cần tìm. Thành phần thứ hai là hàm mục tiêu thể hiện đích đến cần đạt được về mặt kinh tế hoặc kỹ thuật. Thành phần thứ ba là hệ thống các điều kiện ràng buộc giới hạn phạm vi nghiệm. Khó khăn lớn nhất trong giai đoạn phân tích nằm ở việc nhận diện sai lệch các biến số hoặc bỏ sót ràng buộc thực tế. Mối quan hệ phi tuyến tính trong đời sống đôi khi bị đơn giản hóa quá mức dẫn đến sai số. Nếu các tham số không ổn định, nghiệm tìm được sẽ mất đi tính khả thi thực tiễn. Việc phân tách rõ ràng cấu trúc mô hình hỗ trợ kiểm soát tính hợp lệ của bài toán trước khi áp dụng thuật toán.

2.1. Hàm mục tiêu và các biến quyết định

Biến quyết định là các ẩn số đại diện cho mức độ hoạt động của từng phương án cụ thể. Người lập mô hình gán các ký hiệu biến số tương ứng với khối lượng sản phẩm hoặc vật tư. Hàm mục tiêu là biểu thức tuyến tính kết hợp giữa biến quyết định và các hệ số đóng góp. Biểu thức này đo lường tổng lợi nhuận cần cực đại hóa hoặc tổng chi phí cần cực tiểu hóa. Sự chính xác của các hệ số chi phí và giá thành quyết định tính đúng đắn của toàn bộ mô hình. Xác định sai mục tiêu kinh tế sẽ dẫn tới việc điều hướng sai lệch toàn bộ quy trình sản xuất.

2.2. Hệ thống ràng buộc và giới hạn nghiệm

Ràng buộc thể hiện các giới hạn vật lý và kinh tế mà bài toán bắt buộc phải thỏa mãn. Các giới hạn này bao gồm năng lực máy móc, nguồn vốn, nhân công và nhu cầu thị trường. Về mặt toán học, hệ ràng buộc gồm các phương trình hoặc bất phương trình tuyến tính bậc nhất. Điều kiện không âm của biến số cũng là một ràng buộc kỹ thuật bắt buộc để phản ánh thực tiễn. Hệ ràng buộc thu hẹp không gian nghiệm thành một miền đa diện lồi cụ thể. Nếu các ràng buộc mâu thuẫn lẫn nhau, miền nghiệm sẽ rỗng và bài toán không có phương án khả thi. Phân tích ràng buộc giúp phát hiện những nút thắt tài nguyên nghiêm trọng trong hệ thống.

III. Phương pháp giải mô hình toán học trong quy hoạch tuyến tính

Sau khi thiết lập mô hình, việc lựa chọn phương pháp giải phù hợp quyết định tốc độ tìm ra nghiệm tối ưu. Khoa học tối ưu hóa cung cấp nhiều công cụ giải thuật tương ứng với quy mô của bài toán. Đối với bài toán hai biến số, phương pháp hình học trực quan là giải pháp nhanh chóng và dễ tiếp cận nhất. Đối với các mô hình nhiều biến trong môi trường công nghiệp, thuật toán đơn hình đóng vai trò nền tảng. Thuật toán này di chuyển tuần tự qua các đỉnh của miền nghiệm để tìm giá trị tối ưu. Bên cạnh đó, lý thuyết đối ngẫu cung cấp góc nhìn sâu sắc về giá bóng của các nguồn lực hạn chế. Việc biến đổi mô hình về dạng chuẩn tắc hoặc chính tắc là bước chuẩn bị kỹ thuật bắt buộc. Sự kết hợp giữa các thuật toán cổ điển và phần mềm máy tính hiện đại giúp giải quyết những bài toán hàng triệu biến số chỉ trong vài giây.

3.1. Phương pháp đồ thị cho bài toán hai biến

Phương pháp hình học biểu diễn các ràng buộc dưới dạng các nửa mặt phẳng trên hệ trục tọa độ Oxy. Giao của các nửa mặt phẳng này tạo thành miền nghiệm khả thi của bài toán. Đường mức của hàm mục tiêu được tịnh tiến theo vector pháp tuyến để tìm điểm tiếp xúc cực trị. Nghiệm tối ưu sẽ xuất hiện tại đỉnh hoặc cạnh biên tiếp xúc cuối cùng với miền nghiệm. Phương pháp này mang tính minh họa cao, giúp người học nắm bắt trực quan cơ chế tối ưu hóa. Tuy nhiên, cách tiếp cận bằng hình học bị giới hạn hoàn toàn trong không gian hai hoặc ba chiều. Dù vậy, nguyên lý hình học này vẫn là cơ sở lý luận cho các giải thuật nhiều chiều phức tạp hơn.

3.2. Thuật toán đơn hình và bài toán đối ngẫu

Thuật toán đơn hình do George Dantzig phát minh là giải thuật kinh điển cho các bài toán nhiều biến. Thuật toán bắt đầu từ một phương án cực biên cơ bản ban đầu trên bảng đơn hình. Qua mỗi bước lặp, giải thuật kiểm tra tiêu chuẩn tối ưu và đổi biến cơ sở để tăng giá trị hàm mục tiêu. Quá trình dừng lại khi không còn biến nào có thể cải thiện nghiệm. Song song với đó, lý thuyết đối ngẫu biến đổi bài toán gốc sang một bài toán đối ngẫu tương đương. Định lý đối ngẫu mạnh khẳng định giá trị tối ưu của hai bài toán luôn bằng nhau nếu tồn tại nghiệm. Việc giải bài toán đối ngẫu hỗ trợ định giá kinh tế cho nguồn tài nguyên khan hiếm.

IV. Ứng dụng thực tiễn mô hình toán học trong quy hoạch tuyến tính

Mô hình toán học trong quy hoạch tuyến tính có tầm ảnh hưởng sâu rộng trong thực tiễn kinh tế và quản trị vận hành. Trong công nghiệp chế tạo, mô hình tối ưu hóa kế hoạch phân bổ dây chuyền và pha chế nguyên liệu. Trong logistics, bài toán vận tải kinh điển giải quyết việc luân chuyển hàng hóa giữa các kho với chi phí thấp nhất. Lĩnh vực tài chính áp dụng quy hoạch tuyến tính để cân bằng danh mục đầu tư nhằm tối đa lợi nhuận dưới mức rủi ro kiểm soát. Ngành năng lượng sử dụng mô hình để phân bổ tải điện thông minh qua mạng lưới phân phối. Việc áp dụng mô hình toán học giúp các tổ chức cắt giảm lãng phí tài nguyên và gia tăng năng lực cạnh tranh. Công cụ này chứng minh giá trị to lớn khi giải quyết hiệu quả các thách thức điều hành phức tạp của nền kinh tế số.

4.1. Bài toán vận tải và logistics chuỗi cung ứng

Bài toán vận tải là mô hình nhánh tiêu biểu của quy hoạch tuyến tính ứng dụng trong chuỗi cung ứng. Mục tiêu chính là giảm thiểu tổng cước phí vận chuyển từ các trạm phát đến các trạm thu. Mỗi trạm phát có năng lực cung ứng cố định, trong khi mỗi trạm thu có lượng nhu cầu xác định. Thuật toán tìm nghiệm ban đầu như góc tây bắc kết hợp phương pháp thế vị giúp xác định lộ trình phân phối tối ưu. Mô hình này giúp doanh nghiệp điều phối phương tiện chở hàng hiệu quả, tránh tình trạng chuyến xe rỗng hoặc quá tải. Ứng dụng mô hình vận tải mang lại lợi ích tài chính trực tiếp và nâng cao năng lực lưu thông hàng hóa.

4.2. Tối ưu hóa kế hoạch sản xuất kinh doanh

Trong quản trị vận hành, các nhà máy luôn đối mặt với vấn đề khan hiếm giờ máy và nguyên vật liệu. Mô hình quy hoạch tuyến tính hỗ trợ lập cơ cấu sản phẩm tối ưu nhằm mang lại lợi nhuận cao nhất. Các tham số như định mức tiêu hao nguyên liệu, đơn giá bán và quỹ thời gian máy được lượng hóa chặt chẽ. Kết quả giải mô hình cung cấp số lượng sản phẩm chi tiết cần sản xuất cho từng ca làm việc. Ngoài ra, giá trị biến đối ngẫu phản ánh mức giá cao nhất mà nhà máy sẵn sàng trả để mua thêm tài nguyên. Điều này tạo cơ sở vững chắc cho các quyết định đầu tư mở rộng quy mô sản xuất.

Nội dung chính

Đánh Giá Giáo Trình Tối Ưu Hóa Và Quy Hoạch Tuyến Tính (Đại Học Công Nghệ TP.HCM)

Tổng quan về giáo trình

Giáo trình Tối Ưu Hóa và Quy Hoạch Tuyến Tính do ThS. Trần Tuấn Anh biên soạn, được Trường Đại học Công nghệ TP.HCM (HUTECH) phát hành dưới dạng ấn bản 2017 (sửa đổi và bổ sung). Tài liệu được xây dựng nhằm phục vụ công tác giảng dạy và học tập trong chương trình đào tạo bậc đại học, đặc biệt hướng đến sinh viên ngành Tin học và các ngành kỹ thuật, công nghệ có liên quan đến việc ứng dụng mô hình toán học vào giải quyết bài toán thực tế.

Mục tiêu học tập của tài liệu tập trung vào việc trang bị cho người học khả năng phân tích, mô hình hóa các bài toán kinh tế - kỹ thuật thành bài toán quy hoạch tuyến tính; nhận diện và phân loại các dạng cấu trúc bài toán (dạng tổng quát, dạng chính tắc, dạng chuẩn); nắm vững cơ sở lý thuyết về điều kiện tồn tại nghiệm, phương án cực biên; đồng thời thành thạo kỹ thuật tính toán thông qua các thuật toán giải cơ bản như phương pháp hình học, thuật toán đơn hình, thuật toán đơn hình mở rộng (phương pháp M), lý thuyết đối ngẫu và bài toán vận tải.

Về mặt cấu trúc, giáo trình bao gồm 9 bài học được sắp xếp theo trình tự sư phạm từ xây dựng mô hình, biểu diễn không gian hai biến đến các thuật giải đa biến và các bài toán chuyên biệt. Nội dung tiếp cận theo hướng định lượng, kết hợp giữa chứng minh toán học nền tảng và quy trình giải thuật dạng bảng có tính hệ thống cao. Điểm đặc thù của tài liệu là việc chuẩn hóa các bước lặp tính toán, phục vụ hiệu quả cho mục tiêu cài đặt thuật toán trên máy tính.

---

Nội dung kiến thức cốt lõi

Các chương và chủ đề chính

Nội dung học phần được phân bổ chi tiết qua 9 bài học cụ thể:

• Bài 1: Giới thiệu về bài toán quy hoạch tuyến tính và phương pháp lập mô hình: Trình bày phương pháp mô hình hóa các vấn đề kinh tế - kỹ thuật thực tế thông qua việc xác định biến số, hàm mục tiêu cực đại hóa hoặc cực tiểu hóa và hệ ràng buộc kỹ thuật. Bài học định nghĩa chi tiết ba dạng toán học: dạng tổng quát, dạng chính tắc ($Ax = b, x \ge 0$) và dạng chuẩn (dạng chính tắc có chứa ma trận đơn vị $I_m$). Bài này cũng thiết lập các quy tắc chuyển đổi biến tự do, biến không dương, bổ sung biến phụ ($x_{n+i} \ge 0$) và định nghĩa phương án cực biên không suy biến, phương án cực biên suy biến cùng hệ quả về tính hữu hạn của số phương án cực biên.
• Bài 2: Phương pháp hình học giải bài toán quy hoạch tuyến tính hai biến: Hướng dẫn biểu diễn các nửa mặt phẳng nghiệm của bất đẳng thức trên hệ trục tọa độ $Oxy$, xác định miền phương án $D$. Phân tích hai trường hợp: miền phương án là đa giác lồi giới nội (tìm nghiệm tại các đỉnh của đa giác) và miền phương án không giới nội (sử dụng phương pháp tịnh tiến hàm mục tiêu theo hướng vector chỉ phương $\theta_y$ hoặc $-\theta_y$ để tìm điểm tiếp xúc tối ưu).
• Bài 3: Thuật toán đơn hình giải bài toán quy hoạch tuyến tính nhiều biến: Xây dựng cơ sở lý thuyết của bảng đơn hình xuất phát từ bài toán dạng chuẩn. Trình bày chi tiết công thức tính số gia $\Delta_j = \sum (c_i a_{ij}) - c_j$, tiêu chuẩn tối ưu ($\Delta_j \le 0$ đối với bài toán cực tiểu, $\Delta_j \ge 0$ đối với bài toán cực đại), tiêu chuẩn bài toán không có nghiệm tối ưu do hàm mục tiêu không bị chặn, và quy tắc đổi cơ sở chọn ẩn đưa vào (max $\Delta_j$), ẩn đưa ra qua tỉ số $\theta = \min {b_i / a_{ij} \mid a_{ij} > 0}$ cùng phép biến đổi sơ cấp dòng quanh phần tử trục.
• Bài 4: Thuật toán đơn hình mở rộng: Thiết lập thuật giải cho bài toán chính tắc chưa ở dạng chuẩn thông qua kỹ thuật bổ sung các ẩn giả $x_i^{(g)} \ge 0$ với hệ số phạt $M$ rất lớn ($+M$ cho bài toán tìm cực tiểu, $-M$ cho bài toán tìm cực đại). Giáo trình phân loại 3 kết cục khi dừng thuật toán: bài toán $M$ không có nghiệm tối ưu; bài toán $M$ có nghiệm tối ưu không chứa ẩn giả trong cơ sở; và bài toán $M$ có nghiệm tối ưu nhưng ẩn giả trong cơ sở có giá trị khác không (bài toán gốc vô nghiệm).
• Bài 5 và Bài 6: Bài toán đối ngẫu: Định nghĩa mối quan hệ giữa bài toán gốc (Primal) và bài toán đối ngẫu (Dual). Hướng dẫn quy tắc chuyển đổi hệ số hàm mục tiêu thành vector vế phải, ma trận hệ số chuyển vị $A^T$, các định lý đối ngẫu yếu, đối ngẫu mạnh và ứng dụng tìm nghiệm tối ưu của bài toán đối ngẫu từ bảng đơn hình cuối của bài toán gốc.
• Bài 7, Bài 8 và Bài 9: Bài toán vận tải và các mô hình mở rộng: Trình bày mô hình bài toán vận tải dạng tổng quát, điều kiện cân bằng thu - phát ($\sum a_i = \sum b_j$). Bài 8 đi sâu vào các phương pháp tìm phương án cực biên xuất phát (phương pháp góc Tây Bắc, phương pháp cước phí nhỏ nhất) và thuật giải thế vị ($u_i + v_j = c_{ij}$) để tối ưu hóa mạng lưới phân phối. Bài 9 hoàn thiện nội dung với các trường hợp bài toán vận tải không cân bằng thu phát (thêm điểm thu ảo hoặc phát ảo).

Kiến thức nền tảng được xây dựng

Giáo trình củng cố và vận dụng trực tiếp các nền tảng toán học bao gồm:

• Lý thuyết không gian Euclid và đại số tuyến tính: Ma trận, định thức, sự phụ thuộc và độc lập tuyến tính của hệ vector cột $A_j$, hạng của ma trận hệ số và kỹ thuật biến đổi sơ cấp dòng (phép khử Gauss-Jordan).
• Hình học lồi và tối ưu hóa: Định nghĩa tập lồi, đa giác lồi, điểm cực biên, tính chất nghiệm tối ưu luôn đạt được tại các phương án cực biên nếu tập phương án bị chặn.
• Khung phân tích quy hoạch toán học: Quy tắc đối ngẫu hóa hệ ràng buộc, cơ chế bù chặt và mối tương quan giữa nghiệm của hai bài toán phụ thuộc.

Kỹ năng phát triển

Thông qua hệ thống bài học và bài tập, người học được rèn luyện các nhóm kỹ năng cụ thể:

• Kỹ năng kỹ thuật toán học: Thành thạo các bước lập bảng đơn hình, xác định phần tử trục, xoay bảng đơn hình, tính thế vị trong phân phối cước phí vận tải.
• Kỹ năng phân tích mô hình: Chuyển đổi các mô tả thực tế bằng văn bản thành các hệ phương trình/bất phương trình toán học xác định rõ hàm mục tiêu $f(x)$ và miền ràng buộc.
• Kỹ năng biện luận nghiệm: Nhận biết các trường hợp bài toán có nghiệm duy nhất, bài toán có vô số nghiệm tối ưu (khi xuất hiện $\Delta_j = 0$ tại biến không cơ sở) hoặc bài toán vô nghiệm/không bị chặn.

---

Phương pháp giảng dạy và học tập

Giáo trình triển khai phương pháp tiếp cận sư phạm đi từ cụ thể đến trừu tượng. Đầu mỗi bài học, tài liệu đưa ra các case study thực tế điển hình, sau đó trừu tượng hóa thành mô hình toán học và cuối cùng là khái quát hóa thành các định lý, thuật toán tổng quát:

• Bài toán kế hoạch sản xuất: Mô hình xí nghiệp sử dụng 3 loại nguyên liệu $N_1, N_2, N_3$ để sản xuất một loại sản phẩm theo 3 phương pháp $PP_1, PP_2, PP_3$ với các hạn mức tài nguyên trong kho nhằm đạt sản lượng lớn nhất.
• Bài toán pha cắt vật liệu: Mô hình xí nghiệp may mặc cắt các tấm vải theo 6 cách cắt khác nhau để thu được tối thiểu 2000 chiếc quần và 1000 chiếc áo sao cho tổng số tấm vải sử dụng là ít nhất.
• Bài toán xác định khẩu phần dinh dưỡng: Mô hình tối ưu hóa chi phí thức ăn gia súc từ hai loại thức ăn $A$ và $B$ nhằm đáp ứng định mức tối thiểu về protit (700g), glucit (300g) và khoáng chất (4200g).
• Bài toán kinh doanh thiết bị: Ví dụ sản xuất hai dòng điện thoại SH07B và SH01D với ràng buộc về nguồn vốn ($3500) và giới hạn công suất lao động (tối đa 16 sản phẩm).

Về cấu trúc tự học, mỗi bài đều có phần tóm tắt lý thuyết trọng tâm và hệ thống bài tập thực hành cuối bài (từ Bài 1 đến Bài 9). Phương pháp đánh giá học phần được quy định rõ trong đề cương giáo trình:

• Điểm quá trình (30%): Do giảng viên trực tiếp quyết định dựa trên mức độ chuyên cần, làm bài tập về nhà và bài kiểm tra trên lớp.
• Thi kết thúc học phần (70%): Hình thức thi tự luận trong thời gian 90 phút, bao quát toàn bộ khối lượng kiến thức và bài tập từ Bài 1 đến Bài 9.

Người học được hướng dẫn tiếp nhận nội dung theo quy trình: đọc trước mục tiêu bài học, nghiên cứu nội dung lý thuyết, trả lời các câu hỏi kiểm tra nhanh theo từng mục và hoàn thành toàn bộ bài tập tính toán trước khi chuyển sang bài mới.

---

Điểm nổi bật và cập nhật

Ấn bản 2017 (sửa đổi và bổ sung) của tài liệu học tập HUTECH mang những đặc điểm cấu trúc riêng:

• Tính chuẩn hóa quy trình: Các thuật toán được diễn giải theo từng bước rõ ràng (Bước 1: lập bảng, Bước 2: kiểm tra tiêu chuẩn tối ưu qua $\Delta_j$, Bước 3: kiểm tra tính giải được, Bước 4: chọn phần tử trục và biến đổi). Sơ đồ khối thuật toán được minh họa trực quan, hỗ trợ trực tiếp cho sinh viên ngành Tin học khi chuyển đổi giải thuật sang các ngôn ngữ lập trình.
• Làm rõ các trường hợp ngoại lệ trong tính toán: Giáo trình không chỉ dừng lại ở các bài toán chuẩn tắc có nghiệm duy nhất mà phân tích sâu các trường hợp suy biến, các tình huống xuất hiện biến phụ, biến giả và các tiêu chuẩn phát hiện bài toán vô nghiệm hoặc vô số nghiệm.
• Gắn kết ứng dụng công nghiệp và vận hành: Các ví dụ mở rộng phản ánh trực tiếp các bài toán quản lý hiện đại: bài toán phân bổ ca làm việc giữa nhân viên chính thức (40 giờ/tuần) và nhân viên bán thời gian (20 giờ/tuần) tại công ty bảo hiểm; bài toán lập lịch in ấn sách "Toán Cao Cấp 1" và "Toán Cao Cấp 2" tại xưởng in; bài toán tối ưu ngân sách chiến dịch truyền thông đa kênh (truyền hình, báo in, phát thanh) với ngân sách 120 triệu đồng.

---

Đối tượng sử dụng giáo trình

Tài liệu được thiết kế tương thích với các nhóm đối tượng cụ thể:

• Sinh viên đại học: Giáo trình phục vụ trực tiếp cho sinh viên năm thứ hai hoặc năm thứ ba thuộc khoa Công nghệ Thông tin, Hệ thống Thông tin Quản lý, Khoa học Dữ liệu, Kỹ thuật Công nghiệp và Quản trị Kinh doanh.
• Kiến thức tiên quyết: Người học bắt buộc phải hoàn thành học phần Đại số tuyến tính, nắm vững các phép tính trên ma trận, định thức, phương pháp giải hệ phương trình tuyến tính và không gian vector.
• Giảng viên giảng dạy: Tài liệu cung cấp khung đề cương chi tiết cho học phần 2 đến 3 tín chỉ, đi kèm ngân hàng ví dụ mẫu và hệ thống bài tập tự luận phục vụ việc ra đề kiểm tra giữa kỳ và đề thi kết thúc học phần 90 phút.
• Người tự học và nghiên cứu viên: Tài liệu là nguồn tham khảo phục vụ việc tra cứu nhanh các bước thực hiện thuật toán đơn hình, thuật toán thế vị và các mô hình quy hoạch toán học tuyến tính.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Giáo trình được biên soạn phục vụ giảng dạy cho sinh viên bậc đại học ngành Tin học, Kỹ thuật và Quản lý tại Trường Đại học Công nghệ TP.HCM (HUTECH), đồng thời là tài liệu tham khảo cho người cần nắm vững kỹ thuật giải toán quy hoạch tuyến tính.

2. Cần chuẩn bị kiến thức nền nào trước khi học?

Người học cần có nền tảng vững vàng về Đại số tuyến tính, đặc biệt là các phép toán ma trận, định thức, không gian nghiệm của hệ phương trình tuyến tính và biểu diễn hình học trong không gian tọa độ.

3. Điểm khác biệt trong cách tiếp cận của giáo trình này là gì?

Tài liệu tập trung vào việc chuẩn hóa thuật toán thông qua hệ thống bảng tính (bảng đơn hình, bảng vận tải, bảng phương pháp M), trình bày chi tiết từng bước lặp tính toán để người học dễ dàng chuyển hóa sang thuật toán lập trình trên máy tính.

4. Làm sao để tự học hiệu quả với tài liệu này?

Người học nên tuân thủ quy trình: đọc kỹ mục tiêu bài giảng, nghiên cứu cách thiết lập mô hình từ các bài toán mẫu, tự tay thực hiện việc lập bảng và biến đổi ma trận cho các ví dụ trước khi giải hệ thống bài tập tự luận ở cuối mỗi bài.

5. Có tài liệu bổ trợ nào kèm theo giáo trình không?

Cuối giáo trình có danh mục tài liệu tham khảo bổ trợ và hệ thống bài tập tính toán từ Bài 1 đến Bài 9. Mọi ý kiến đóng góp học thuật về nội dung được gửi trực tiếp về Ban biên tập qua địa chỉ e-mail: [e-mail].

---

Kết luận

Giáo trình Tối Ưu Hóa và Quy Hoạch Tuyến Tính của ThS. Trần Tuấn Anh là tài liệu học tập chuẩn hóa tại Đại học Công nghệ TP.HCM, cung cấp hệ thống kiến thức toán học ứng dụng chặt chẽ từ khâu lập mô hình đến các thuật toán giải số trị. Lộ trình học tập được thiết kế khoa học qua 9 bài học giúp sinh viên xây dựng tư duy mô hình hóa và nắm vững các thuật giải tối ưu hóa tuyến tính cổ điển. Tài liệu đóng vai trò nền tảng trong chương trình đào tạo chuyên ngành tin học ứng dụng và kỹ thuật công nghiệp tại nhà trường.

Trích đoạn nội dung tài liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC CÔNG NGHỆ TP.HCM Tối ƯU HÓA VÀ QUY HOẠCH TUYẾN TÍNH Biên Soạn: ThS. Trần Tuấn Anh www.vn TỐTI ƯU HÓA VÀ QUY HOẠCH TUYẾN TÍNH Ấn bản 2017 (Sửa đổi và bổ sung) Các ý kiến đóng góp về tài liệu học tap nay, xin gui vé e-mail cua ban biên tập: [e-mail] Mục Lực mm MỤC LỤC MỤC LỤC. HƯỚNG DẪN BÀI 1: GIỚI GHIỆU VỀ BÀI TOÁN TUH VÀ QHTT.1 GIỚI THIỆU VỀ BÀI TOÁN QHTT VÀ PHƯƠNG PHÁP LẬP MÔ HÌNH. 1 1,2 CAC DANG CUA BAI TOÁN QHTT.3 CÁC ĐỊNH LÝ TỒN TẠI NGHIỆM, MỘT SỐ TÍNH CHẤT.

LH TH HH E8 14 BÀI 2: PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QHTT HAI BIẾN.1 BIỂU DIỄN ĐĂNG THỨC, BẤT ĐĂNG THỨC HAI BIẾN TRÊN ĐỒ THỊ.2 PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QHTT CÓ HAI BIẾN. 25 BÀI 3: THUẬT TOÁN ĐƠN HÌNH GIẢI BÀI TOÁN QHTT NHIÊU BIẾN .2 CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH. TH HH TH HH HH HH Hư rệt 28 7. BÀI 5: BÀI TOÁN ĐỐI NGẪU BÀI 7: BÀI TOÁN VẬN TẢI, ỨNG DỤNG VÀ MÔ HÌNH TOÁN HỌC.1 BÀI TOÁN VẬN TẢTI DẠNG TỔNG QUÁT.Á nH SH TH TH TH KH tk Hư 69 7.2 CÁC TÍNH CHẤT VÀ TIÊU CHUAN TOI UU CUA BÀI TOÁN VẬN TẮT.

+2 73 mm Mục Lực 9. 75 BÀI 8: THUẬT TOÁN TÌM NGHIỆM XUẤT PHÁT, THUẬT TOÁN .1 CÁC PHƯƠNG PHÁP TÌM PHƯƠNG ÁN CỰC BIÊN ĐẦU TIÊN CỦA BÀI TOÁN VẬN TẢI.2 THUẬT GIẢI THẾ VỊ CHO BÀI TOÁN VẬN TẢI. SG LH HSH 1111k Hy Hy cư 78 I9.ÔỎ 91 ; 0) TA hh. 91 BÀI 9: MỞ RỘNG BÀI TOÁN VẬN TẢI.1 BAI TOAN VAN TAI KHONG CAN BANG THU - PHÁT.

BAI TAP TAI LIEU TT.ÔỎ 110 HƯỚNG DẪN ia HUONG DAN MO TA MON HOC Tối ưu hóa nói chung và Quy hoạch tuyến tính nói riêng là một phần kiến thức không thể thiếu cho tất cả những người làm việc trong lĩnh vực ứng dụng của khoa học và kỹ thuật. Đặc biệt với sinh viên tin học, nó là kiến thức căn bản của nhiều ứng dụng, thể hiện thế mạnh và ưu việt của các phát triển tin học vào thực tế. Trình bày được một cách có hệ thống những kiến thức cơ bản nhất của Tối ưu hóa và Quy hoạch tuyến tính về: Khái niệm và cách thiết lập bài toán quy hoạch tuyến tính, phương án, phương án cực biên, phương án tối ưu của một bài toán quy hoạch tuyến tính; Các thuật toán giải bài toán quy hoạch tuyến tính; Bài toán đối ngẫu và cách giải; Bài toán vận tải và ứng dụng. NỘI DUNG MÔN HỌC Bài 1.

Giới thiệu về bài toán QHTT và phương pháp lập mô hình toán từ các vấn đề thực tiễn. Các dạng của bài toán QHTT, các định lý tồn tại nghiệm. -_ Bài 2: Phương pháp hình học giải bài toán QHTT hai biến. -_ Bài 3: Thuật toán đơn hình giải bài toán QHTT nhiều biến -_ Bài 4: Thuật toán đơn hình mở rộng.

-_ Bài 5: Bài toán đối ngẫu. - Bai 6: Bai todn đối ngẫu (tt). - Bai 7: Bai toan van tai, tng dung va mô hình toán học. - Bai 8: Thuat toan tim nghiém xuat phat, thuat toan thé vị giải bài toán vận tải.

-_ Bài 9: Mở rộng bài toán vận tải. KIẾN THỨC TIỀN ĐỀ Môn học TUH và QHTT đòi hỏi sinh viên có nần tảng về đại số tuyến tính. YEU CAU MON HOC Người học phải dự học đầy đủ các buổi lên lớp và làm bài tập đầy đủ ở nhà. CÁCH TIẾP NHẬN NỘI DUNG MÔN HỌC Để học tốt môn này, người học cần ôn tập các bài đã học, trả lời các câu hỏi và làm đầy đủ bài tập; đọc trước bài mới và tìm thêm các thông tin liên quan đến bài học.

Đối với mỗi bài học, người học đọc trước mục tiêu và tóm tắt bài học, sau đó đọc nội dung bài học. Kết thúc mỗi ý của bài học, người đọc trả lời BÀI TẬP và kết thúc toàn bộ bài học, người đọc làm các bài tập. PHƯƠNG PHÁP ĐÁNH GIÁ MÔN HỌC Môn học được đánh giá gồm: -_ Điểm quá trình: 30%. Hình thức và nội dung do GV quyết định, phù hợp với quy chế đào tạo và tình hình thực tế tại nơi tổ chức học tập.

Hình thức bài thi tự luận trong 90 phút. Nội dung gồm các bài tập từ bài 1 đến bài 9. BÀI 1:GIỚI GHIỆU VỀ BÀI TOÁN TUH VÀ QHTT ta BÀI 1: GIOT GHIEU VE BAI TOAN TUH VA QHTT Sau khi hoc xong bai nay, hoc vién can - _ Nắm vững một số khái niệm về tối ưu hóa trong tính toán; - _ Phân biệt các dạng của bài toán QHTT; -_ Lập được mô hình toán học từ bài toán thực tế; -_ Nắm được các khái niệm, định lý về tồn tại nghiệm.1 GIỚI THIỆU VỀ BÀI TOÁN QHTT VÀ PHƯƠNG PHÁP LẬP MÔ HÌNH TOÁN TỪ CÁC VẤN ĐỀ THUC TIEN 1.1 Một số ví dụ thực tiễn về bài toán QHTT Trong thực tế, có rất nhiều dạng, mô hình sản xuất kinh doanh khác nhau. Các mô hình đều có những đặc điểm và những tính năng riêng biệt cho từng mục tiêu cụ thể.

Sau đây là một số ví dụ các mô hình: a. Bài toán lập kế hoạch sản xuất Một xí nghiệp dùng 3 loại nguyên liệu khác nhau là N1, N2 và N3 để sản xuất ra một loại sản phẩm theo 3 phương pháp khác nhau: PP1, PP2 và PP3. Định mức nguyên liệu và số lượng sản phẩm sản xuất ra được cho ở bảng bên dưới (bảng 1. Vấn đề đặt ra là hãy lập mô hình toán học của bài toán trên với mục tiêu sau cho xí nghiệp sản xuất được nhiêu sản phẩm nhất.

Pa BÀI 1:GIỚI GHIỆU VỀ BÀI TOÁN TUH VÀ QHTT Số lượng Định mức tiêu thụ nguyên liệu Nguyên liệu nguyên liệu hiện có trong kho PP1 PP2 PP3 Ni 250 5 : N2 350 5 : : N3 450 5 4 Số lượng sản phẩm (sp/ giờ) 10 l2 5 b. Bài toán pha cắt vật liệu Một xí nghiệp may mặc cắt những tấm vải thành đúng 2000 quần và ít nhất 1000 áo. Mỗi tấm vải có 6 cách cắt như sau: Cách cắt Quần Áo 1 90 35 2 80 55 3 70 70 4 60 90 5 120 0 6 0 100 Hãy tìm phương án cắt quần áo sao cho tổng số tấm vải là ít nhất? c. Bài toán xác định khẩu phần Để nuôi một loại gia súc có hiệu quả, mỗi ngày cần khối lượng tối thiểu 700gr protit, 300gr glucit và 4200gr khoáng.

Tỷ lệ theo khối luợng các chất có trong thức ăn A và B như sau: Thức ăn Chất dinh dưỡng Protit Glucit Khoáng A 1 1 7 B 2 1 6 Giá 1 gram thức ăn A, B tương ứng là 40 đồng và 60 đồng. Hãy lập mô hình bài toán xác định khối lượng thức ăn cần thiết sao cho chi phí nuôi gia súc là thấp nhất? BÀI 1:GIỚI GHIỆU VỀ BÀI TOÁN TUH VÀ QHTT a 1.2 Lap m6 hinh toan a. Bài toán lập kế hoạch sản xuất Gọi x;,x;,x; lần lượt là thời gian sản xuất ra sản phẩm theo 3 phương pháp PP1, PP2 và PP3. Trong 1 giờ PP1 sản xuất được 10 sản phẩm, như vậy theo PP1 ta có tổng sản phẩm sau x; giờ là 10x;.

Tưởng tự tổng số sản phẩm theo PP2 và PP3 là: 12x; và 9x; Tổng sản phẩm sản xuất theo cả 3 phương pháp (cần làm cực đại) f(x) = 10x, + 12x, + 9x3 > max Do xí nghiệp chỉ có 250 nguyên liệu N1 nên: Ax, + 5x2 +3x3 = 250 Tương tự cho nguyên liệu N2: 2⁄¡+ 4x; +*x¿ < 350 Và nguyên liệu N3 3x¡ + 6x; + 4x; < 450 Dĩ nhiên vì x;,x;,xạ là thòi gian sản xuất nên các giá trị này không âm. - Vậy mô hình bài toán được phát biểu như sau: Tìm các biến z;,x;,x; sao cho: Ham muc tiéu f(x) = 10x, + 12x, + 9x3 > max Thỏa các điều kiện: 4x, +5x, + 3x, < 250 Rang buéc} 2x, +4x, +x, < 350 3x1 + 6x, + 4x, < 450 Ràng buộc dau: x, > 0,x, =0,x, =0 b. Bài toán pha cắt vật liệu Gọi x;Ú = 1,2,.,6) là số tấm vải được cắt theo cách thứ j Tổng số tấm vải dung để sản xuất (cần tìm cực tiểu): f(x) =x 42 +43 +44 +X5 +X > min | 4 BÀI 1:GIỚI GHIỆU VỀ BÀI TOÁN TUH VÀ QHTT Do xí nghiệp cần sản xuất đúng 2000 quần nên các x; phải thỏa mẫn: 90x; + 80x; + 70x; + 60x„ + 120x; = 2000 Xí nghiệp cần sản xuất tối thiểu 1000 cái áo: 35x, + 55x; + 70x, + 90x, + 100x¿ > 1000 Va dĩ nhiên ta phải có x;Ú = 1,2,. - Vậy mô hình bài toán được phát biểu như sau: Tìm các biến x;Ú = 1,2,.,6) sao cho: Hàm mục tiêuƒ(x) = xạ + #¿ + xã +x¿ +; +x; — mín Thỏa các điều kiện: 90x, + 80x, + 70x, + 60x, + 120x, = 2000 35x, +55x2 + 70x; + 90x, + 100x, = 1000 Ràng buộc dấu: z; > 0 Ợ = 1,2,.

Bài toán xác định khẩu phần Gọi x;,x;là số gram thức ăn A, B cần mua mỗi ngày.Tổng chi phí dùng để mua thức ăn (cần làm cực tiểu) là f@) = 40x, + 60x, > min Do các tỷ lệ các chất protit, glucit và khoáng có trong thức ăn A nân các x; phai thỏa mãn x, + 2x, = 700 Tương tự cho điều kiện của thức ăn B và C, ta có #⁄¡ +*x¿ > 300 và 7x¡ + 6x; > 4200 - Vậy mô hình bài toán được phát biểu như sau: Tìm các biến x,,x2,x, Sao cho: Hàm mục tiêuƒ(+) = 40x¡ + 60x; > min Thỏa các điều kiện: x, + 2x; > 700 Ràng buộc #¡ +x¿ >300 7#¡ + 6x; > 4200 Rang buộc dấu: zx; >0,x;ạ>0 BÀI 1:GIỚI GHIỆU VỀ BÀI TOÁN TUH VÀ QHTT a 1.2 CAC DANG CUA BAI TOAN QHTT Trong mục này chúng ta sẽ tìm hiểu một số dạng cơ bản của bài toán QHTT bao gồm dạng tổng quát, dạng chính tắc và dạng chuẩn. Xem xét mối quan hệ, sự chuyển đổi giữa các dạng 1.1 Biểu diễn bài toán dưới dạng ma trận Để thuận tiện hơn trong việc giải quyết các bài toán QHTT ta có thể biểu diễn bài toán dưới dạng ma trận. Chúng ta dung các ký hiệu: trong đó A là ma trận mm x œ gồm các hệ số ở vế trái của hệ ràng buộc, A; la véc-tơ cột thứ j của ma trận A, b là véc-tơ hệ số ở vế phải của hệ ràng buộc, x la véc-to ẩn số.2 Vi du Xét bài toán lập kế hoạch sản xuất ta có 4 5 3 4 250 4 a=(2 4 i)A.3 Dạng tổng quát của bài toán QHTT Tìm x = Œ,*¿,.