Tiểu luận đề tài: Quy hoạch tuyến tính - Trường ĐH Công Nghiệp HCM

Tiểu luận đề tài Quy hoạch tuyến tính giúp nghiên cứu tìm hiểu về các ứng dụng của quy hoạch tuyến tính việc học quy hoạch tuyến tính rất quan trọng, nó đem lại những hiệu quả kinh tế rất lớn nếu biết lập các mô hình và tính toán đúng quy cách, ứng dụng trong kinh doanh sản xuất hiệu quả.
Nội dung trích xuất từ tài liệu:
Tiểu luận đề tài: Quy hoạch tuyến tính - Trường ĐH Công Nghiệp HCM , Bộ CÔNG THƯƠNG ĨHUÍ TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HÒ CHÍ MINH HO CHI UNH UMVBBITY Cf INDLSTSY KHOA KHOA HỌC cơ BẢN Viện Công nghệ Sinh học - Thực phẩm Lớp : 211301202 Bộ MÔN QUY HOẠCH TUYÉN TÍNH TIẺU LUẬN GVHD : TS. Võ Văn Tuấn Dũng 1. Nguyễn Trung Nhân 0771637 2. Mai Hạnh Nguyên 0770613 3. Huvnh Thành Trung 0771757 4. Hồ Thị Thanh Hiếu 0771725 5. Dưong Thị Hà Như 0771496 6. Cao Thị Ngọc Tuvền 0770834 7. Mai Nguyễn Thục Hiền 0770770 8. Vũ Kim Hường 0771102 ■d\ TP. HCM, ngày 25 tháng 4 năm 2009 LỜI MỞ ĐẦU 1. Lv do chọn đề tài Trong thực tế ta thường hay gặp các tình huống là phải lựa chọn một trong số những quyết định quan trọng đê đưa ra những phương án hoặc chiến lược tốt nhất trong sản xuất kinh doanh hay trong một trò chơi mà đối thủ là một kẻ thông minh và nguy hiêm...Khi đó ta cần phải lập mô hình toán học quy hoạch tuyến tính đê có được phương án tối ưu cần thiết. Trong đó phương pháp đơn hình được George Bemanrd Dantzig đưa ra năm 1947 cùng lúc với việc khai sinh ra quy hoạch tuyến tính, phương pháp này thực sự có hiệu quả đê giải những bài toán quy hoạch tuyến tính cỡ lớn trong thực tế mà ta thường gặp, như đế vận chuyển hàng hóa đầy đủ nhưng có tong chi phí là nhở nhất - đây chính là bài toán vận tải. Hoặc trong kinh doanh phải lập kế hoạch sản xuất đối với các nguyên liệu và sản phẩm đê thu được tổng lợi nhuận là lớn nhất... Kiến thức sau khi học quy hoạch tuyến tính rất cần thiết, đây là những kiến thức rất quan trọng đê xây dựng một mô hình toán học cho bất kỳ bài toán phức tạp nào trong thực tế, chỉ cần xây dựng các thuật toán đã mô hình hóa ngôn ngữ nhờ việc lập trình trên máy tính ta có thê giải quy hoạch tuyến tính một cách dê dàng nhanh chóng và chính xác. Như vậy việc học quy hoạch tuyến tính rất quan trọng, nó đem lại những hiệu quả kinh tế rất lớn nếu biết lập các mô hình và tính toán đúng quy cách. 2. Đối tượng nghiên cứu và phương pháp nghiên cứu. Quy hoạch tuyến tính là lĩnh vực nghiên cứu các bài toán tối ưu mà hàm mục tiêu là vấn đề được quan tâm nhất và các ràng buộc là các yêu cầu ,điều kiện của kế hoạch đặt ra, đều là hàm và các phương trình, bất phương trình tiiyến tính. Các bước đê nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điên hình là: ■ Xác định vấn đề cần giải quyết, thu thập dữ liệu . Æ ■ Lập mô hình toán học thật chính xác. ■ Xây dựng các thuật toán đê giải bài toán trên các lập trình máy tính. ■ Tính toán thử và điều chỉnh mô hình nếu cần . ■ Áp dụng đê giải các bài toán thực tế . CHƯƠNG 1: BÀI TOÁN QUY HOẠCH TUYỂN TÍNH A. LÝ THUYẾT 1. ĐỊNH NGHĨA Bài toán quy hoạch tuyến tính (qhtt) tổng quát có dạng: Tìm Xj, j=l,2,...,n sao cho: f=Vớjc. -»min(max) (1) 7=1 Với hệ ràng buộc: ịy, bị, i=l,2,...,m (2) 7=1 >0 (3) ) hoặc có dạng đang thức (=). (3) được gọi là các ràng buộc dấu (của biến), nó có thể không âm (>0), không dương ( Tức là: f(x*)=XC,*; f(x) = ỴJCJXJ là giá trị hàm mục tiêu tại phương án 7=1 L-J j=1 T x=(xl5x2,...,xn) bất kỳ. (Dấu < ứng với bài toán cực tiểu. Dấu > ứng với bài toán cực đại). Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nêu có). Hai bài toán QHTT được gọi là tương đương với nhau riếu chúng có chung tập hợp các phương án tối ưu. Mệnh đề: (Quan hệ giữa bài toán cực đại và bài toán cực tiểu) f(x)—» max  íg(x) = ‐f(x) —>• min  0)0 v (2) XGX [xeX (Trong đó: X là tập hợp các phương án) Tức là: nếu đồi dấu hàm mục tiêu và đổi loại hàm mục tiêu thì ta được bài toán tương đương. Vì lí do này mà khi nghiên cứu cách giải bài toán qhtt, người ta chỉ xét bài toán có loại hàm mục tiêu là cực tiểu (hay chỉ xét bài toán có loại hàm mục tiêu là cực đại) 2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUI HOẠCH TUYÉN TÍNH 2 BIÉN Bài toán có dạng: tìm x=(xi,x2)t sao cho f(x)=cix1+c2x2“^ min (max) Với hệ ràng buộc: ailx1+ai2x2>bi, i=l,2,...,m Chú ý: - Ràng buộc chung có dạng: a-b. - Ràng buộc chung có dạng: a = b thì tương đương với: a>b và -a>-b. - Còn các ràng buộc biến có thê xem là các trường hợp riêng của các ràng buộc chung. Như vậy, hệ ràng buộc của bài toán QHTT có 2 biến luôn luôn có thê giả thiết là có dạng: a¡iXi+ai2X2>b¡; i=l, 2..., m 2.1. Xác định miền phương án Đưa các điểm (xi,x2) lên hệ trục tọa độ vuông góc. Ta ...