Bài giảng Quy hoạch tuyến tính: Chương 1 - ThS. Nguyễn Văn Phong

Bài giảng "Quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính" cung cấp cho người học các kiến thức: các ví dụ dẫn đến bài toán quy hoạch tuyến tính, phân loại bài toán QHTT, các khái niệm cơ bản, phương pháp hình học giải bài toán QHTT, phương pháp đơn hình giải bài toán QHTT. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính: Chương 1 - ThS. Nguyễn Văn Phong10/5/2012ĐẠI HỌC TÀI CHÍNH – MARKETINGBỘ MÔN TOÁN – KHOA CƠ BẢNBài giảngQUY HOẠCH TUYẾN TÍNHThS.ThS. Nguyeãn Vaên PhongEmail : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vnChương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH1. CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT2. PHAÂN LOAÏI BAØI TOAÙN QHTT3. CAÙC KHAÙI NIEÄM CÔ BAÛN4. PHÖÔNG PHAÙP HÌNH HOÏC GIAÛI BAØI TOAÙN QHTT5. PHÖÔNG PHAÙP ÑÔN HÌNH GIAÛI BAØI TOAÙN QHTT2NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHCAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTTVí dụ 1. ( Bài toán sản suất ) Giả sử một xí nghiệp sảnxuất có m loại nguyên vật liệu V1, V2, … , Vm với số lượngtương ứng lần lượt là m1, m2, …, mm (đv) để sản xuất ra nloại sản phẩm S1, S2, … , Sn. Lợi nhuận và tỷ lệ cácnguyên vật liệu dùng để sản xuất được cho trong bảngsau:SjViS1S2…SnLượngNL…a1nm1a2nm2V1a11a12V2a21a22………………Vmam1am2…amnmnLợinhuậnc1c2…cnYêu cầu: Lập kế hoạch sản xuất tối ưuQUY HOAÏCH TUYEÁN TÍNH3NGUYEÃN VAÊN PHONG110/5/2012CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTTVí dụ 2. (Bài toán đầu tư vốn) Giả sử một doanh nhân A cómột lượng vốn là V0 tỷ muốn đầu tư vào các danh mụcsau đây:Gửi tiết kiệm không kì hạn với lãi suấta% /năm.Gửi tiết kiệm có kì hạn với lãi xuấtb% /năm.Mua trái phiếu chính phủ với lãi xuấtc% /năm.Cho doanh nghiệp tư nhân vay với lãi suấtd% /năm.Mua đất phân lô bán nền với lãi suấte% /năm.Giả sử thời gian đáo hạn là như nhau. Các hình thức đầutư đều có rủi ro. Để hạn chế rủi ro chúng ta nhận đượccác thông tin từ các chuyên gia tư vấn sau:QUY HOAÏCH TUYEÁN TÍNH4NGUYEÃN VAÊN PHONGCAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTTVí dụ 2. (Bài toán đầu tư vốn)Không cho doanh nghiệp tư nhân vay quá 30% số vốn.Số tiền mua trái phiếu Chính phủ không vượt quá sốtiền đầu tư trong 4 lĩnh vực kia.Ít nhất 20% số tiền đầu tư phải thuộc lĩnh vực tiết kiệmcó kỳ hạn và trái phiếu.Tỷ lệ tiết kiệm không kỳ hạn trên tiết kiệm có kỳ hạnkhông vượt quá 1/3.Số tiền mua đất không vượt quá 40% số vốn.Doanh nhân A muốn đầu tư toàn bộ số vốn. Hãy lập môhình bài toán tìm phương án đầu tư sao cho thu được lợinhuận tối đa.5QUY HOAÏCH TUYEÁN TÍNHNGUYEÃN VAÊN PHONGCAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTTVí dụ 3. (Bài toán khẩu phần ăn). Giả sử ta cần chế biếnmón ăn từ nhiều thành phần nhưng đảm bảo đầy đủ cácchất bổ cần thiết (như: đạm, béo, đường,…) mà giá thànhlại rẻ nhất.Giả sử có n thành phần, với giá một đơn vị thànhphần j là cj, j = 1,2,…,n. Đồng thời có m chất. Biết rằngmột đơn vị thành phần j chứa aij đơn vị chất i, i =1, 2, …,m, và mức chấp nhận được số đơn vị chất i là nằm giữa livà ui, i = 1,2,…,m. (hay ít nhất là bi)QUY HOAÏCH TUYEÁN TÍNH6NGUYEÃN VAÊN PHONG210/5/2012CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTTVí dụ 4. (Bài toán vận tải). Giả sử hàng hóa được vậnchuyển từ m kho hàng đến n cửa hiệu bán lẻ. Lượng hàngở kho thứ i có mi (i = 1,2,…,m) (đv) và cửa hiệu j có nhucấu là nj (j =1,2,…,n) (đv). Cước vận chuyển một đv hànghóa từ kho i đến cửa hiệu j là cij (đv). Giả sử rằng1. Tổng hàng hóa ở các kho = Tổng nhu cầu hànghóa của các cửa hiệu.2. Hàng hóa ở kho thứ i có thể vận đến bất kỳ củahiệu nào và cửa hiệu thứ j có thể nhận hàng hóa từ 1 khobất kỳ.3. Mỗi cửa hàng phải nhận đủ số hàng và mỗi khophải phát hết hàng.Yêu cầu: Lập kế hoạch vận chuyển sao cho cước phí làbé nhất.7NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHPHÂN LOẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNHI. DẠNG TỔNG QUÁT (LP)Tìm x = ( x 1 , x 2 ,..., x n ) sao cho :n(I ) f ( x ) = ∑ c j x j → min (max)j =1 ni = 1, k , ∑ aij x j ≤ bi , j =1 ni = k + 1, l , (2) ∑ aij x j ≥ bi ,(II )  j =1 ni = l + 1, m. ∑ aij x j = bi , j =1 (3) x j ≤ 0, x j ≥ 0, x j ∈ ℝ, j = 1,2,..., nVới: cj , là hệ số hàm mục tiêu, bi là các hệ số tự do, aij làhệ số của các ràng buộc chung.8QUY HOAÏCH TUYEÁN TÍNHNGUYEÃN VAÊN PHONGPHÂN LOẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNHII. DẠNG CHÍNH TẮC (LPct)Tìm x = ( x 1, x 2 ,..., x n ) sao cho :nf ( x ) = ∑ c j x j → min (max)nj =1∑ aij x j = bi , i = 1, m.j =1x j ≥ 0, j = 1,2,..., n.III. DẠNG CHUẨN (LPc)Tìm x = ( x 1 , x 2 ,..., x n ) sao cho :nf ( x ) = ∑ c j x j → min (max)j =1xi +n∑j = m +1aij x j = bi , bi ≥ 0, i = 1, m.x j ≥ 0, j = 1,2,..., n.QUY HOAÏCH TUYEÁN TÍNH9NGUYEÃN VAÊN PHONG310/5/2012CÁC KHÁI NIỆM CƠ BẢNI. CÁC KÝ HIỆUXét bài toán QHTT dạng tổng quát. Ta đặt a11 a12aa2221A=... ...aam 2 m1... a1n   x = ( x1 , x 2 ,..., x n )... a2 n   b = ( b1 , b2 ,..., bm ) ,... ...  c = (c1, c2 ,..., cn )... amn   a i , A j : doøng i , coät j cuûa AKhi đó, bài toán QHTT được viết lại dưới dạng sauf = c , x → min(max)Ax( ≥ , ≤, = )f = c , x → min(max)haybai , x( ≥ , ≤, = )bi , i = 1, mx ≥ 0, x ≤ 0 or x ∈ ℝx ≥ 0, x ≤ 0 or x ∈ ℝc ...