CHƯƠNG III
MÔ HÌNH TỐI ƯU TUYẾN TÍNH (QHTT)
I. Thí dụ mở đầu
II. Mô hình bài toán QHTT
III. Các tính chất chung của bài toán QHTT
IV. Phương pháp đơn hình
V. Bài toán đối ngẫu
I. Thí dụ mở đầu
•Thí dụ 1: Bài toán lựa chọn danh mục đầu tư
- Nội dung: Một công ty đầu tư dự định dùng khoản quỹ đầu tư 500 tỷ đồng
để mua một số cổ phiếu trên thị trường chứng khoán. Để phòng ngừa rủi
ro công ty đưa ra các yêu cầu về đa dạng hoá danh mục đầu như sau:
+ Loại cổ phiếu và giới hạn mua:
+ Tỷ lệ đầu tư vào cổ phiếu A và C phải chiếm ít nhất 55% và cổ phiếu B
phải chiếm ít nhất 15% tổng số vốn đầu tư thực hiện
- Bài toán: Với số tiền dự kiến đầu tư, hãy xác định một danh mục đầu tư
sao cho đảm bảo về đa dạng hoá danh mục đầu tư và đem lại mức lợi tức
lớn nhất.
Loại CK Lợi tức Giới hạn mua
A 7%/năm 100 tỷ
B 8,5%/năm 300 tỷ
C 7,8%/năm 250 tỷ
D 8,2%/năm 320 tỷ
- Mô hình hoá:
+ Gọi xA, xB, xC, xDlà các khoản tiền đầu tư vào các loại chứng
khoán A, B, C, D
+ Các điều kiện về đa dạng hoá danh mục đầu tư:
0 xA 100; 0 xB300 (1)
0 xC250, 0 xD320 (2)
xA + xC 0,55(xA + xB+ xC + xD) (3)
xB0,15(xA + xB+ xC + xD) (4)
xA + xB+ xC + xD 500 (5)
+ Mức lợi tức ứng với danh mục đầu tư:
Z = 0,07xA + 0,085xB+ 0,078xC + 0,082xD (tỷ đồng)
- Xác định x = (xA, xB, xC, xD) sao cho:
Z Max; với các điều kiện (1), (2), (3), (4), (5).
- Bài toán này gọi là bài toán QHTT
•Thí dụ 2: Bài toán vận tải
- Nội dung: Một công ty kinh doanh xăng dầu tại khu vực Z hàng
tuần cần cung ứng xăng cho 3 trạm bán lẻ A, B và C. Công ty có
thể đưa xăng đến các trạm từ tổng kho I và II. Lượng xăng dự trù
cung ứng cho các trạm của kho I là 20 tấn, kho II là 40 tấn. Nhu cầu
tiêu thu xăng hàng tuần của các trạm A, B, C lần lượt là 20, 15, 15
(tấn). Chi phí cho việc cung ứng xăng được cho dưới bảng sau:
Đơn vị: nghìn đồng/tấn
- Bài toán: Cần lập một kế hoạch cung ứng xăng từ các kho đến các
trạm để đảm bảo đáp ứng đủ nhu cầu của các trạm với tổng chi phí
vận chuyển là nhỏ nhất.
Kho\ Trạm A B C
I 500 400 700
II 600 500 500
- Mô hình hoá:
+ Gọi x1A, x1B, x1C, x2A, x2B, x2C (tấn) lần lượt là các lượng xăng
vận chuyển từ kho I, kho II đến các trạm A, B, C.
+ Điều kiện để đáp ứng đầy đủ nhu cầu của các trạm:
x1A + x2A = 20 (1)
x1B + x2B = 15 (2)
x1C + x2C = 15 (3)
+ Điều kiện về lượng xăng dự trù cung ứng của các kho:
x1A + x1B + x1C 20 (4)
x2A + x2B + x2C 40 (5)
+ Tổng chi phí vận chuyển:
Y = 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C (nghìn
đồng)
- Xác định x1A, x1B, x1C, x2A, x2B, x2C 0 sao cho:
Y Min; với các điều kiện (1), (2), (3), (4), (5)
Bài toán này gọi là bài toán QHTT