intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: Bình Yên | Ngày: | Loại File: PDF | Số trang:11

150
lượt xem
12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

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

6/17/2016<br /> <br /> ĐẠI HỌC TÀI CHÍNH – MARKETING<br /> BỘ MÔN TOÁN – KHOA CƠ BẢN<br /> <br /> Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH<br /> 1. CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT<br /> 2. PHAÂN LOAÏI BAØI TOAÙN QHTT<br /> 3. CAÙC KHAÙI NIEÄM CÔ BAÛN<br /> <br /> Chương 1<br /> QUY HOẠCH TUYẾN TÍNH<br /> <br /> 4. PHÖÔNG PHAÙP HÌNH HOÏC GIAÛI BAØI TOAÙN QHTT<br /> 5. PHÖÔNG PHAÙP ÑÔN HÌNH GIAÛI BAØI TOAÙN QHTT<br /> <br /> ThS. Nguyeãn Vaên Phong<br /> Email : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vn<br /> <br /> CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT<br /> Ví dụ 1. ( Bài toán sản suất ) Giả sử một xí nghiệp sản<br /> xuất có m loại nguyên vật liệu V1, V2, … , Vm với số lượng<br /> tương ứng lần lượt là b1, b2, …, bm (đv) để sản xuất ra n<br /> loại sản phẩm S1, S2, … , Sn. Lợi nhuận và tỷ lệ các<br /> nguyên vật liệu dùng để sản xuất được cho trong bảng<br /> sau:<br /> Sj<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 2<br /> NGUYEÃN VAÊN PHONG<br /> <br /> CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT<br /> Ví dụ 2. (Bài toán đầu tư vốn) Giả sử một doanh nhân A có<br /> một lượng vốn là V0 tỷ muốn đầu tư vào các danh mục<br /> sau đây:<br />  Gửi tiết kiệm không kì hạn với lãi suất<br /> <br /> a% /năm.<br /> <br />  Gửi tiết kiệm có kì hạn với lãi xuất<br /> <br /> b% /năm.<br /> <br /> S1<br /> <br /> S2<br /> <br /> …<br /> <br /> Sn<br /> <br /> Lượng<br /> NL<br /> <br /> V1<br /> <br /> a11<br /> <br /> a12<br /> <br /> …<br /> <br /> a1n<br /> <br /> b1<br /> <br />  Mua trái phiếu chính phủ với lãi xuất<br /> <br /> c% /năm.<br /> <br /> V2<br /> <br /> a21<br /> <br /> a22<br /> <br /> a2n<br /> <br /> b2<br /> <br />  Cho doanh nghiệp tư nhân vay với lãi suất<br /> <br /> d% /năm.<br /> <br />  Mua đất phân lô bán nền với lãi suất<br /> <br /> e% /năm.<br /> <br /> Vi<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> …<br /> <br /> Vm<br /> <br /> am1<br /> <br /> am2<br /> <br /> …<br /> <br /> amn<br /> <br /> bm<br /> <br /> Lợi<br /> nhuận<br /> <br /> c1<br /> <br /> c2<br /> <br /> …<br /> <br /> cn<br /> <br /> Yêu cầu: Lập kế hoạch sản xuất tối ưu<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> Giả sử thời gian đáo hạn là như nhau. Các hình thức đầu<br /> tư đều có rủi ro. Để hạn chế rủi ro chúng ta nhận được<br /> <br /> 3<br /> NGUYEÃN VAÊN PHONG<br /> <br /> các thông tin từ các chuyên gia tư vấn sau:<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 4<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 1<br /> <br /> 6/17/2016<br /> <br /> CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT<br /> Ví dụ 2. (Bài toán đầu tư vốn)<br />  Không cho doanh nghiệp tư nhân vay quá 30% số vốn.<br />  Số tiền mua trái phiếu Chính phủ không vượt quá số<br /> tiền đầu tư trong 4 lĩnh vực kia.<br />  Ít nhất 20% số tiền đầu tư phải thuộc lĩnh vực tiết kiệm<br /> có kỳ hạn và trái phiếu.<br /> <br /> CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT<br /> Ví dụ 3. (Bài toán khẩu phần ăn). Giả sử ta cần chế biến<br /> món ăn từ nhiều thành phần nhưng đảm bảo đầy đủ các<br /> chất bổ cần thiết (như: đạm, béo, đường,…) mà giá thành<br /> lại rẻ nhất.<br /> Giả sử có n thành phần, với giá một đơn vị thành<br /> phần j là cj, j = 1,2,…,n. Đồng thời có m chất. Biết rằng<br /> một đơn vị thành phần j chứa aij đơn vị chất i, i =1, 2, …,<br /> m, và mức chấp nhận được số đơn vị chất i là nằm giữa li<br /> và ui, i = 1,2,…,m. (hay ít nhất là bi)<br /> <br />  Tỷ lệ tiết kiệm không kỳ hạn trên tiết kiệm có kỳ hạn<br /> không vượt quá 1/3.<br />  Số tiền mua đất không vượt quá 40% số vốn.<br /> Doanh nhân A muốn đầu tư toàn bộ số vốn. Hãy lập mô<br /> hình bài toán tìm phương án đầu tư sao cho thu được lợi<br /> 5<br /> nhuận tối đa.<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> NGUYEÃN VAÊN PHONG<br /> <br /> CAÙC VÍ DUÏ DAÃN ÑEÁN BAØI TOAÙN QHTT<br /> Ví dụ 4. (Bài toán vận tải). Giả sử hàng hóa được vận<br /> chuyển từ m kho hàng đến n cửa hiệu bán lẻ. Lượng hàng<br /> ở kho thứ i có mi (i = 1,2,…,m) (đv) và cửa hiệu j có nhu<br /> cấu là nj (j =1,2,…,n) (đv). Cước vận chuyển một đv hàng<br /> hóa từ kho i đến cửa hiệu j là cij (đv). Giả sử rằng<br /> 1. Tổng hàng hóa ở các kho = Tổng nhu cầu hàng<br /> hóa của các cửa hiệu.<br /> 2. Hàng hóa ở kho thứ i có thể vận đến bất kỳ của<br /> hiệu nào và cửa hiệu thứ j có thể nhận hàng hóa từ 1 kho<br /> bất kỳ.<br /> 3. Mỗi cửa hàng phải nhận đủ số hàng và mỗi kho<br /> phải phát hết hàng.<br /> Yêu cầu: Lập kế hoạch vận chuyển sao cho cước phí là<br /> bé nhất.<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 7<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 6<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> PHÂN LOẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH<br /> I. DẠNG TỔNG QUÁT (LP)<br /> Tìm x  ( x1 , x 2 ,..., x n ) sao cho :<br /> n<br /> <br /> (I ) f ( x )   c j x j  min (max)<br /> j 1<br /> <br /> <br />  n<br /> i  1, k ,<br /> <br />   aij x j  bi ,<br /> <br />  j 1<br /> <br />  n<br /> <br /> i  k  1, l ,<br />  (2)<br />   aij x j  bi ,<br /> (II ) <br />  j 1<br /> <br />  n<br /> <br /> i  l  1, m.<br />   aij x j  bi ,<br /> <br />  j 1<br /> <br /> <br />  (3) x j  0, x j  0, x j  , j  1,2,..., n<br /> Với: cj , là hệ số hàm mục tiêu, bi là các hệ số tự do, aij là<br /> hệ số của các ràng buộc chung.<br /> 8<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> NGUYEÃN VAÊN PHONG<br /> <br /> 2<br /> <br /> 6/17/2016<br /> <br /> PHÂN LOẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH<br /> II. DẠNG CHÍNH TẮC (LPct)<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> I. CÁC KÝ HIỆU<br /> Xét bài toán QHTT dạng tổng quát. Ta đặt<br /> <br /> Tìm x  ( x 1, x 2 ,..., x n ) sao cho :<br /> n<br /> <br /> f (x) <br /> <br /> c x<br /> j<br /> <br /> j<br /> <br /> n<br /> <br /> a<br /> <br /> ij<br /> <br /> x j  bi , i  1, m .<br /> <br /> j 1<br /> <br /> x j  0, j  1,2,..., n.<br /> III. DẠNG CHUẨN (LPc)<br /> <br /> f  c, x  min(max)<br /> <br /> n<br /> <br /> c x<br /> j<br /> <br /> j<br /> <br />  min (max)<br /> <br /> Ax<br /> <br /> j 1<br /> <br /> n<br /> <br /> xi <br /> <br /> <br /> <br /> aij x j  bi , bi  0, i  1, m.<br /> <br /> j m 1<br /> <br /> x j  0, j  1,2,..., n.<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 9<br /> NGUYEÃN VAÊN PHONG<br /> <br />  , ,  <br /> <br /> <br /> <br /> bi , i  1, m<br /> <br /> Đối với ràng buộc<br /> <br /> a x  b<br /> thì  a x  x<br /> <br /> Neáu<br /> <br /> - x  D Gọi là một phương án (PA)<br /> *<br /> <br /> - x  D , f x  x , c     x , c  f ( x ), x  D<br /> thì x* là một phương án tối ưu (PATƯ)<br /> - i0  1,2,..., m : a i0 , x  bi0 gọi là một ràng buộc chặt.<br /> - Một PA thỏa chặt n ràng buộc độc lập tuyến tính được<br /> gọi là phương án cực biên (PACB)<br /> - Một PACB thỏa chặt đúng n ràng buộc gọi là phương<br /> án cực biên không suy biến (PACB), thỏa chặt hơn n<br /> ràng buộc gọi là PACB suy biến<br /> <br /> NGUYEÃN VAÊN PHONG<br /> <br /> ij<br /> <br /> ij<br /> <br /> j<br /> <br /> j<br /> <br /> i<br /> <br /> n 1<br /> <br /> hay<br /> <br /> a<br /> <br /> ij<br /> <br />  bi hay<br /> <br /> x j  bi<br /> <br /> a<br /> <br /> ij<br /> <br /> x j  x n 1  bi<br /> <br /> vôùi x n  1  0 : goïi laø aån phuï<br /> Đối với ràng buộc dấu<br /> <br /> Neáu x j  0 thì ñaët x /j   x j  0<br /> Neáu x j   thì ñaët x j  x /j /  x /j / / vôùi x /j / , x /j/ /  0<br /> <br /> - Một bài toán QHTT được gọi là giải được nếu tồn tại ít<br /> nhất một PATƯ.<br /> 11<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br />  , ,  <br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> <br /> <br />  <br /> <br /> ai , x<br /> <br /> hay<br /> <br /> b<br /> <br /> III. CHUYỂN DẠNG TỔNG QUÁT VỀ DẠNG CHÍNH TẮC<br /> <br /> Gọi D  x Ax   ,  ,   b là miền chấp nhận được. Khi đó<br /> *<br /> <br /> f  c , x  min(max)<br /> <br /> x  0, x  0 or x  <br /> x  0, x  0 or x  <br /> c , x  c1 x1  c2 x 2  ...  cn x n<br /> trong đó<br /> 10<br /> a i , x  ai 1 x1  ai 2 x 2  ...  ain x n<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> NGUYEÃN VAÊN PHONG<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> II. CÁC KHÁI NIỆM<br /> <br /> *<br /> <br /> ...<br /> <br /> Khi đó, bài toán QHTT được viết lại dưới dạng sau<br /> <br /> Tìm x  ( x1, x 2 ,..., x n ) sao cho :<br /> f (x) <br /> <br /> a1n   x  ( x1, x 2 ,..., x n )<br /> <br /> ... a2n   b   b1 , b2 ,..., bm <br /> ,<br /> ... ...  c  (c1, c2 ,..., cn )<br /> <br /> ... amn   a i , A j : doøng i , coät j cuûa A<br /> <br /> <br />  a11 a12<br /> a<br /> a22<br /> 21<br /> A<br />  ...<br /> ...<br /> <br /> am 1 am 2<br /> <br /> <br />  min (max)<br /> <br /> j 1<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 12<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 3<br /> <br /> 6/17/2016<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> IV. CHUYỂN DẠNG CHÍNH TẮC VỀ DẠNG CHUẨN<br /> <br /> V. MỘT SỐ NHẬN XÉT<br /> <br /> Đối với hệ số tự do<br /> <br /> 1. Bài toán QHTT dạng chính tắc đạt nghiệm tối ưu tại ít<br /> nhất một PACB. Khi đó<br /> <br /> Neáu bi  0 thì   aij x j   bi  0<br /> Đối với ràng buộc<br /> Nếu ràng buộc nào chưa có ẩn cơ sở (Là ẩn chỉ<br /> xuất hiện trong một ràng buộc và có hệ số bằng 1) thì ta<br /> thêm vào ẩn cơ sở (ẩn giả). Khi đó hệ số của ẩn giả trong<br /> hàm mục tiêu tương ứng là +M cho BT min (M rất lớn) và<br /> –M cho BT max (M rất lớn). Lúc này bài toán được gọi là<br /> bài toán mở rộng, ký hiệu là (M)<br /> <br /> Xeùt<br /> D   x Ax  b, x  0 vaø A j : coät thöù j cuûa A mn<br /> Luùc ñoù Ax  b  A1x1  A2 x 2  ...  An x n  b<br /> 0<br /> 0<br /> 0<br /> Xeùt x 0   x 1 , x 2 ,..., x n   D , J ( x 0 )  j  {1,2,..., n } x 0  0<br /> j<br /> <br /> <br /> <br /> 0<br /> <br /> Kyù hieäu J ( x ) laø soá thaønh phaàn ( ) trong x<br /> Nhận xét :<br /> <br /> <br /> <br /> 0<br /> <br /> <br /> <br /> <br /> <br /> - x 0  D laø PACB  Heä caùc veùc tô A j j  J ( x 0 ) laø ÑLTT<br /> - Neáu x 0 laø PACB thì J ( x 0 )  r ( A)<br /> <br /> Nhận xét :<br /> <br /> Neáu f ( x )  min thì g ( x )  f ( x )  max<br /> 13<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br />  Neáu J ( x 0 )  r ( A) thì x 0 khoâng suy bieán<br />  Neáu J ( x 0 )  r ( A) thì x 0 suy bieán<br /> 14<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> V. MỘT SỐ NHẬN XÉT<br /> <br /> VI. MỐI QUAN HỆ GIỮA CÁC BÀI TOÁN<br /> <br /> 2. Bài toán QHTT dạng chuẩn<br /> Đối với bài toán dạng chuẩn, thì việc xác định một PACB<br /> ban đầu được thực hiện như sau:<br /> Cho các ẩn tự do nhận các giá trị bằng 0. Khi đó,<br /> các ẩn cơ sở sẽ có giá trị là số hạng tự do tương ứng.<br /> <br /> 1. Tổng quát (TQ) với Chính tắc (CT)<br /> - Nếu (CT) không có PATƯ thì (TQ) không có PATƯ<br /> - Nếu (CT) có PATƯ mà không chứa các ẩn phụ thì<br /> (TQ) có PATƯ<br /> 2. Chính tắc với Bài toán (M)<br /> - Nếu (M) không có PATƯ thì (CT) không có PATƯ<br /> - Nếu (M) có PATƯ là x(M) thì<br /> + Nếu trong x(M) có thành phần ứng với biến<br /> giả khác 0 thì (CT) không có PATƯ<br /> + Nếu trong x(M) có tất cả các thành phần<br /> ứng với biến giả đều bằng 0 thì (CT) có PATƯ<br /> <br /> i .e., x 0   b1, b2 ,..., bm ,0,....,0 <br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 15<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 16<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 4<br /> <br /> 6/17/2016<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> VII. MỘT SỐ VÍ DỤ<br /> <br /> VII. MỘT SỐ VÍ DỤ<br /> <br /> Ví dụ 1a. Hãy tìm miền chấp nhận được cho bài toán<br /> QHTT sau<br /> <br /> Ví dụ 2. Cho bài toán QHTT sau<br /> <br /> min f ( x )  2 x1  x 2<br />   x1  2 x 2<br />  x<br />  1  x2<br /> <br />  x1<br />  x1  2 x 2<br /> <br /> <br /> 3 x <br />  1<br />  x1 <br /> <br /> <br /> <br />  4<br />  5<br />  4<br />  8<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> (4,1)<br /> (2,3)<br /> (3,2)<br /> (1,2)<br /> <br /> : PACBKSB, (0,2) là gì?<br /> : PACBSB<br /> : Không là PACB<br /> 17<br /> : Là PA<br /> NGUYEÃN VAÊN PHONG<br /> <br /> CÁC KHÁI NIỆM CƠ BẢN<br /> <br /> <br /> <br /> <br /> x j  0;<br /> <br /> 10 x 3<br /> x3<br /> <br />  10<br /> 1<br /> <br /> j  1,3<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 18<br /> NGUYEÃN VAÊN PHONG<br /> <br /> PHƯƠNG PHÁP HÌNH HỌC GIẢI BT QHTT<br /> <br /> VII. MỘT SỐ VÍ DỤ<br /> <br /> Xét bài toán QHTT 2 biến<br /> <br /> Ví dụ 3. Cho bài toán QHTT với tập ràng buộc sau<br /> <br />  x1  2 x2<br /> <br />   x1  2 x 2<br />  x<br />  1<br /> <br /> 4 x2<br /> x2<br /> <br /> a) CMR (2,1,0) là PACBKSB<br /> b) CMR (0,0,1) lá PACBSB<br /> <br /> x j  0; j  1,2<br /> Ví dụ 1b. CMR<br /> <br /> min f ( x )  x1  x 2  2 x 3<br /> <br /> <br /> <br /> x3<br /> <br /> <br />  2<br />  4<br /> <br /> x4<br /> <br /> f ( x )  c , x  c1x 1  c2 x 2  min(max)<br /> Ax ( , ,  ) b<br /> x j  0, x j  0, x j  <br /> <br /> x5<br /> <br />  5<br /> <br /> - Goïi D   x Ax (,  ,  ) b laø mieàn chaáp nhaän ñöôïc<br /> <br /> x1, x 2 , x 3 , x 4 , x 5<br /> <br />  0<br /> <br /> - c  (c1 , c2 ) : laø phaùp veùc tô cuûa f<br /> <br /> <br /> <br /> Các véc tơ sau có là PACB của bài toán trên không?<br /> a) (0,2,2,0,5)<br /> b) (1,1,1,3,4)<br /> c) (2,0,0,6,5)<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 19<br /> NGUYEÃN VAÊN PHONG<br /> <br /> - L( , f )   x  D f ( x )    laø ñöôøng möùc cuûa f<br /> Khi đó, phương pháp hình học, bao gồm các bước sau:<br /> B1: Vẽ miền D, c, và đường mức L( 0,f ) qua 0 và vuông<br /> góc với c.<br /> B2: Lấy một điểm bất kỳ<br /> <br /> x  D vaø veõ ñöôøng L ñi qua x vaø // vôùi L(0, f ) 20<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> NGUYEÃN VAÊN PHONG<br /> <br /> 5<br /> <br />
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
13=>1