Tổng Hợp Thông Tin Quy Hoạch Tuyến Tính | Môn Linear algebra and Algebraic structures - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58759230
Tổng hợp cho tôi thông tin về đề tài quy hoạch tuyến tính,
môn học đại số tuyến tính. Làm thành một file pdf. Lưu ý là
tránh trùng lặp quá mức với 2 file được đính kèm. Tìm kiếm
trên mạng và trong file. Và nhớ ghi cả nguồn gốc của thông
tin. Đưa ra các lưu ý, lời khuyên cho bài báo cáo thuyết trình
Chắc chắn rồi! Dưới đây là thông tin tổng hợp về ứng dụng của Đại số tuyến tính trong quy hoạch tuyến tính,
đặc biệt là bài toán vận tải, cùng với các lưu ý và lời khuyên cho bài báo cáo hoặc thuyết trình của bạn.
Ứng Dụng Của Đại Số Tuyến Tính Trong Vận Tải Quy Hoạch Tuyến Tính) Cơ Sở Lý Thuyết
a) Quy hoạch tuyến tính LP
Là một thuật toán tìm phương án tối ưu từ vô số các phương án quyết định, thỏa mãn các mục tiêu đề ra của
một hãng dựa trên các ràng buộc.
Giải quyết vấn đề phân bổ nguồn lực khan hiếm giữa các hoạt động cạnh tranh một cách tối ưu (hiệu quả cao
nhất, lãi gộp cao nhất, chi phí thấp nhất).
Thành phần của mô hình LP
Hàm mục tiêu: Xác định mục tiêu cụ thể cần đạt tới.
Các ràng buộc: Các giới hạn về sự sẵn có của nguồn lực hoặc yêu cầu tối thiểu, được biểu diễn dưới dạng tuyến tính.
b) Bài toán vận tải
Giao thông vận tải đóng vai trò quan trọng trong nền kinh tế, tham gia vào quá trình sản xuất và lưu thông hàng hóa.
Doanh nghiệp vận tải luôn ưu tiên yếu tố lợi nhuận, do đó cần giảm chi phí vận chuyển và tối ưu hóa công tác tổ chức vận tải.
Bài toán vận tải trong quy hoạch tuyến tính là một công cụ quan trọng để giải quyết vấn đề này, được chính
thức hóa bởi nhà toán học Gaspard Monge vào năm 1781. lOMoAR cPSD| 58759230 Tóm Tắt Bài Toán
Giải bài toán vận tải:
Bài toán cân bằng thu phát: Tổng lượng thu bằng tổng lượng phát. Sử dụng các phương án cực biên để tính cước phí nhỏ nhất.
Bài toán không cân bằng thu phát: Tổng lượng thu không bằng tổng lượng phát.
Nếu tổng lượng thu lớn hơn tổng lượng phát: Thêm vào hàng phát thứ m+1 một lượng bằng tổng thu trừ tổng phát.
Ngược lại: Thêm vào cột thu thứ n+1 một lượng bằng tổng phát trừ tổng thu.
Sau đó tính bằng phương án cực biên như bài toán cân bằng thu phát, rồi loại bỏ hàng hoặc cột đã thêm vào.
Phương Pháp Giải Bài Toán Vận Tải
Phương án cực biên cơ bản:
Không suy biến: Số ô chọn bằng m + n - 1.
Suy biến: Số ô chọn nhỏ hơn m + n - 1. Cần chọn thêm một ô có giá trị nhỏ nhất (ưu tiên từ trên bên
trái) và không tạo thành chu trình.
Phương Pháp Tây Bắc The Northwest Corner Method):
Bắt đầu từ ô ở góc tây bắc. lOMoAR cPSD| 58759230
Cung cấp tối đa từ điểm nguồn cho các điểm đích theo thứ tự từ trái sang phải. Nếu nguồn đã hết thì
chuyển sang nguồn tiếp theo.
Đáp ứng tối đa nhu cầu của điểm đích từ các nguồn theo thứ tự từ trên xuống dưới. Nếu nhu cầu đã đủ
thì chuyển sang nhu cầu tiếp theo.
Phương Án Cước Phí Bé Nhất Minimal Cost Method):
Ưu tiên chọn ô có cước phí thấp nhất để đáp ứng tối đa khả năng cung ứng và nhu cầu.
Loại bỏ các ô của điểm nguồn hoặc điểm đích đã hết khả năng cung ứng hoặc nhu cầu.
Xác định lại ô có chi phí thấp nhất còn lại và tiếp tục phân bổ như trên.
Phương án cực biên tối ưu hơn Thuật toán thế vị):
Thành lập phương án cực biên ban đầu theo nguyên lý phân bổ tối đa bằng các phương pháp như góc
Tây Bắc, cước phí thấp nhất, Fogel,...
Xét dấu hiệu tối ưu của phương án:
Tìm các biệt số dòng ui và biệt số cột vj bằng cách giải hệ phương trình ô chọn: ui + vj = cij (chọn u1 0 làm tham số).
Tìm các ước lượng cho các ô loại: ∆ij = ui + vj − cij Nếu mọi ∆ ≤
0 Phương án đang xét tối ưu.
Nếu có ∆ > 0 Phương án không tối ưu, cần cải tiến.
Cải tiến phương án:
Đưa ô loại có ước lượng ∆ lớn nhất vào thành ô chọn, tạo thành chu trình K duy nhất.
Đánh dấu âm/dương xen kẽ cho chu trình K (bắt đầu từ ô mới bổ sung mang dấu +).
Xác định xij min trong các ô mang dấu (-).
Bớt đi lượng xij min cho các ô mang dấu (-).
Cộng thêm lượng xij min cho các ô mang dấu (+).
Kiểm tra lại tính tối ưu và lặp lại nếu cần. Ứng Dụng MATLAB
MATLAB có thể được sử dụng để xác định phương án cực biên cơ bản không suy biến.
Cần nhập ma trận giá, ma trận thu và ma trận phát.
Code MATLAB có thể được viết để thực hiện cả phương pháp Tây Bắc và phương pháp cước phí nhỏ nhất. lOMoAR cPSD| 58759230
Lưu Ý và Lời Khuyên Cho Bài Báo Cáo/Thuyết Trình
Tính trực quan: Sử dụng sơ đồ, hình ảnh minh họa để làm rõ các khái niệm và phương pháp.
Ví dụ cụ thể: Trình bày một ví dụ bài toán vận tải thực tế và cách giải nó bằng các phương pháp khác nhau.
So sánh: So sánh ưu nhược điểm của các phương pháp giải Tây Bắc, cước phí nhỏ nhất, thuật toán thế vị).
Ứng dụng thực tế: Nhấn mạnh tầm quan trọng của quy hoạch tuyến tính và bài toán vận tải trong việc tối
ưu hóa chi phí và tăng hiệu quả hoạt động của doanh nghiệp.
MATLAB demo: Nếu có thể, trình diễn cách sử dụng MATLAB để giải bài toán vận tải.
Tương tác: Đặt câu hỏi cho khán giả để khuyến khích sự tham gia và đảm bảo họ hiểu rõ nội dung.
Nguồn tham khảo: Luôn ghi rõ nguồn gốc của thông tin và tài liệu tham khảo.
Thời gian: Chuẩn bị kỹ lưỡng để đảm bảo bài thuyết trình nằm trong thời gian quy định. Nguồn Tham Khảo
Trường Đại Học Bách Khoa Tp.HồChí Minh
PDF] https://tailieuplk.webnode.vn/_files/200000131 93a3694a51/Chuong%203,%20Bai% 20toan%20van%20tai,%20SV.pdf
$$YT Giang Lê - Qui hoạch tuyến tính .chương 3 Bài toán vận tải https://www.youtube.co m/watch?v=y_kPBQl7GVU $$YT Hà Chí Công - Lý
Chúc bạn có một bài báo cáo/thuyết trình thành công! ⁂