CHƯƠNG 3
MÔ HÌNH TỐI ƯU TUYẾN TÍNH
§1. Khái niệm cơ bản về bài toán QHTT
§2. Thuật toán đơn hình
§3. Bài toán đối ngẫu
1
§1. KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN
QUY HOẠCH TUYẾN TÍNH
1. Một số ví dụ
Ví dụ 1 Một trại chăn nuôi định nuôi 3 loại bò: bò sữa, bò cày, bò thịt. Nguồn cung cấp giống bò sữa chỉ có thể cung cấp tối đa 18 con. Dự trù kinh phí chăn nuôi (tính trên mỗi con bò) được cho trong bảng sau :
Bò sữa Bò cày Bò thịt
Tiền dự tính (đv : 10000 ĐVN)
Loại bò Chi phí
Vốn
128
137
165
7020
Chi phí chăn nuôi 59
43
43
860
Tiền lãi
71
45
61
Tìm số bò mỗi loại cần nuôi để đạt lợi nhuận lớn nhất
2
Một nhà đầu tư có 4 tỉ đồng muốn đầu tư vào bốn lĩnh vực
Lĩnh vực đầu tư
Lãi suất / năm
Ví dụ 2
Chứng khoán Công trái Gửi tiết kiệm Bất động sản
20% 12% 15% 18%
Ngoài ra, để giảm thiểu rủi ro, nhà đầu tư cho rằng không
nên đầu tư vào chứng khoán vượt quá 30% tổng số vốn đầu
đầu tư; gửi tiết kiệm ít nhất 300 triệu đồng.
tư; đầu tư vào công trái và gửi tiết kiệm ít nhất 25% tổng vốn
Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho tổng
thu nhập hàng năm là lớn nhất.
3
• Các bước lập bài toán QHTT :
1) Xác định ẩn và hàm mục tiêu.
2) Xác định hệ ràng buộc về biến.
3) Xác định hệ ràng buộc về dấu.
4
Công ty A có kết hoạch quảng cáo sản phẩm trong 1 tháng với
tổng chi phí là 120 triệu đồng. Các phương tiện quảng cáo:
truyền hình, báo giấy, phát thanh. Các dữ liệu như sau :
Phương tiện
Chi phí cho 1 lần QC
Số lần QC tối đa
Dự đoán số người tiếp nhận QC trong 1 lần
Truyền hình Báo Phát thanh
1,2 triệu đồng 0,9 triệu đồng 0,4 triệu đồng
90 28 120
10 000 15 000 5 000
Vì lí do chiến lược tiếp thị, yêu cầu ít nhất phải có 60 lần
quảng cáo trên truyền hình trong 1 tháng. Hãy lập mô hình bài
toán xác định kế hoạch quảng cáo.
5
2. Bài toán quy hoạch tuyến tính (QHTT)
2.1 Bài toán QHTT tổng quát Tìm x = (x1, x2, . . . , xn) sao cho:
hàm mục tiêu
ràng buộc biến
(ràng buộc chính)
ràng buộc dấu
6
2.2 Một số khái niệm
(một véctơ) thỏa mãn các hệ ràng
• Một phương án của bài toán QHTT là một bộ n số
buộc (2), (3).
• Tập hợp các véctơ thỏa mãn (2),(3) gọi là tập phương
án.
7
• Phương án tối ưu (PATƯ) là một phương án thỏa (1).
2.2 Một số khái niệm
Bài toán giải được là bài toán có PATƯ.
đó hoặc là bài toán không có phương án hoặc có phương án
Bài toán không giải được là bài toán không có PATƯ. Khi
nhưng hàm mục tiêu không bị chặn
( đối với bài toán max (min)).
Nếu phương án x thỏa mãn ràng buộc nào đó với dấu “=”
thì ta nói x thỏa mãn chặt ràng buộc đó. Ngược lại nếu thỏa
8
dấu “>” hoặc “<” thì ta nói thỏa mãn lỏng ràng buộc đó.
2.2 Một số khái niệm
- Ứng với ràng buộc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3). - Ký hiệu:
là vectơ các hệ số của biến xj trong các ràng buộc (không kể ràng buộc dấu).
- Hệ vectơ Ai* tương ứng với các ràng buộc chính tạo thành
- Các ràng buộc gọi là độc lập tuyến tính nếu hệ véctơ Ai*
ma trận ràng buộc chính, ký hiệu là A.
9
tương ứng độc lập tuyến tính.
2.2 Một số khái niệm
• Phương án cực biên (phương án cơ bản)
(PACB): phương án thỏa mãn chặt n ràng buộc độc
lập tuyến tính.
Lưu ý: PACB có thể thỏa mãn chặt hơn n ràng buộc,
nhưng chỉ có n ràng buộc độc lập tuyến tính.
• PACB không suy biến: phương án cực biên thỏa
mãn đúng n ràng buộc.
• PACB suy biến: phương án cực biên thỏa mãn hơn
n ràng buộc.
10
Ví dụ 3
x2
x =9
• Tìm các PACB của bài toán QHTT sau.
x1
2
24
9
–4
11
3. Các dạng đặc biệt của bài toán QHTT
3.1 Bài toán dạng chính tắc
Dạng ma trận
Mọi bài toán QHTT dạng tổng quát đều có thể đưa về dạng
chính tắc tương đương – theo nghĩa :
• Giá trị tối ưu của các hàm mục tiêu là trùng nhau.
• Phương án, PATƯ của bài toán này sẽ suy ra phương án,
12
PATƯ của bài toán kia.
Ví dụ 4
Đưa các bài toán QHTT sau về dạng chính tắc tương đương
f(x) = x1 + x2 + 3x3 Max
a) b) f(x) = 2x1 + x2 – x3 Min
13
3.2 Đặc điểm PACB của bài toán dạng chính tắc
Định lí 1
Gọi Aj là cột thứ j của ma trận A. Phương án x của bài toán QHTT dạng chính tắc là cực
biên thì hệ véc tơ {Aj} tương ứng với thành phần dương của phương án là độc lập tuyến tính.
Ví dụ 5. Véctơ x=( 2,1,0) là PACB của bài toán QHTT
f(x) = x1 + 4 x2 + 6 x3 max 3x1 + 4 x2 + 4 x3 = 10 – x1 + x2 + x3 = – 1
14
Chú ý
Với bài toán QHTT dạng chính tắc :
Ta có thể giả thiết r(A)=m và m < n .Từ đó suy ra :
-PACB có không quá m thành phần dương;
-PACB không suy biến là PA có m thành phần dương;
-PACB suy biến là PA có ít hơn m thành phần dương.
15
3.2 Đặc điểm PACB của bài toán dạng chính tắc
Định lí 2 (phát biểu cho bài toán QHTT dạng chính tắc)
1. Bài toán có phương án thì có PACB.
2. Nếu bài toán có phương án tối ưu thì có PACB tối ưu.
Định lí 3
1. Bài toán có phương án và trị số hàm mục tiêu bị chặn
dưới (trên) trên tập các phương án khi f(x)→min (max)
thì có PATƯ.
2. Số PACB khác nhau trong mỗi bài toán là hữu hạn.
16
3. Các dạng đặc biệt của bài toán QHTT
3.3 Bài toán dạng chuẩn
17
có ma trận con đ.vị cấp m
3.3 Bài toán dạng chuẩn
Ví dụ 6 Cho bài toán QHTT:
f(x) = x1 – 2x2 + x3 – 3x4 + x5 Min
Bài toán trên có phải là bài toán dạng chuẩn không?
Tìm một phương án cực biên.
18
3.3 Bài toán dạng chuẩn
• AÅn cô bản (ẩn cơ sở) là ẩn öùng vôùi caùc veùctô coät
ñôn vò trong ma traän heä soá A; (caùc aån coøn laïi laø aån
khoâng cô baûn) (noùi caùch khaùc noù laø aån coù heä soá laø 1 ôû
moät phöông trình vaø coù heä soá laø 0 trong caùc phöông
trình coøn laïi).
•
Phöông aùn cô baûn cuûa BTQHTT daïng chuaån là
phöông aùn coù caùc aån khoâng cô baûn baèng 0 .
19
3.3 Bài toán dạng chuẩn
Ví dụ 7 Cho bài toán QHTT:
f(x) = x1 – 2x2 + x3 Min
a) Hãy tìm một PACB của bài toán, phương án đó có suy biến không ?
b) Hãy tìm một PACB mới.
20
Ví dụ 8
Đưa các bài toán QHTT sau về dạng chuẩn tương đương
a) b)
21
