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 mn<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 />