- Trang Chủ
- Toán học
- Chương 3: Mô hình tối ưu tuyến tính - Quy hoạch tuyến tính (Bài 1)
Xem mẫu
- BỐ CUC BAI GIANG
̣ ̀ ̉
1.Cac ví dụ dân đên bai toan Quy hoach tuyên
́ ̃ ́ ̀ ́ ̣ ́
́
tinh:
1.1 Lâp kế hoach san xuât:
̣ ̣ ̉ ́
1.2 Phân bổ vôn đâu tư:
́ ̀
̣ ̃
2. Đinh nghia:
- 1. Cac ví dụ dân đên bai toan Quy hoach tuyên
́ ̃ ́ ̀ ́ ̣ ́
́
tinh (QHTT):
1.1 Lâp kế hoach san xuât:
̣ ̣ ̉ ́
̉ ̉
san phâm S1 S2 S3 Số lượng nguyên
Chi phí liêu hiên có
̣ ̣
̣
Nguyên liêu 1 (N1) 4 5 3 15.000
̣
Nguyên liêu 2 (N2) 2 4 3 12.000
̣
Nguyên liêu 3 (N3) 3 6 4 10.000
Lao đông ̣ 10 7 6 500.000
Giả sử răng san phâm san xuât ra đêu có thể tiêu thụ được
̀ ̉ ̉ ̉ ́ ̀
hêt với lợi nhuân khi ban môt đơn vị san phâm S1, S2, S3
́ ̣ ́ ̣ ̉ ̉
tương ứng là 5000:10000:7000 (đông). Yêu câu lâp kế hoach
̀ ̀ ̣ ̣
san xuât tôi ưu.
̉ ́ ́
- Goi xj là số san phâm cua Sj (j = 1,2, 3) cần san xuât
̣ ̉ ̉ ̉ ̉ ́
(xj ≥ 0, j = 1, 2, 3.)
Theo kế hoach san xuât phai tim lượng nguyên liêu tiêu
̣ ̉ ́ ̉ ̀ ̣
̀
hao la:
N1: 4 x1 + 5 x2 + 3 x3 ≤ 15000
N2: 2 x1 + 4 x2 + 3 x3 ≤ 12000
N3: 3 x1 + 6 x2 + 4 x3 ≤ 10000
Số phut cân sử dung:
́ ̀ ̣ 10 x1 + 7 x2 + 6 x3 ≤ 500.000
Tông lợi nhuân theo kế hoach san xuât la:
̉ ̣ ̣ ̉ ́ ̀
5000 x1 + 10000 x2 + 7000 x3
Yêu cầu tối ưu 5000 x + 10000 x + 7000 x → max
là: 1 2 3
- ̀ ̀ ́
Mô hinh bai toan:
̀
Tim x = (x1, x2, x3) sao cho:
f ( x ) = 5000 x + 10000 x + 7000 x → max
1 2 3
4 x + 5 x + 3x ≤ 15000
1 2 3
2 x + 4 x + 3x ≤ 12000
1 2 3
3x1 + 6 x2 + 4 x3 ≤ 10000
10 x1 + 7 x2 + 6 x3 ≤ 500000
x j ≥ 0, j = 1, 2,3
- Tông quat: ta có bai toan lâp kế hoach san xuât
̉ ́ ̀ ́ ̣ ̣ ̉ ́
dưới dang bang số liêu sau đây:
̣ ̉ ̣
Yêu tố
́ Số lượng ̉ ̉
San phâm
san xuât hiên có
̉ ́ ̣ S1 S2 … Sn
Y1 b1 a11 a12 … a1n
Y2 b2 a21 a22 … a2n
… … … … … …
… … … … … …
Ym bm am1 am2 … am
n
Lợi nhuân đơn vị
̣ c1 c2 … cn
- ̀
Mô hinh:
̀
Tim x = (x1, x2,…, xn) sao cho:
n
f = ∑ c j x j → max
j =1
n
∑ aij x j ≤ bi , i = 1,..., m
j =1
x j ≥ 0, j = 1,..., n
- 2.2 Phân bổ vôn đâu tư:
́ ̀
Môt nhà đâu tư có 4 tỉ đông muôn đâu tư vao 4 linh vực
̣ ̀ ̀ ́ ̀ ̀ ̃
Linh vực đâu tư
̃ ̀ ̃ ́
Lai suât/năm
Chứng khoan ́ 20%
Công trai ́ 12%
Gửi tiêt kiêm
́ ̣ 15%
́ ̣
Bât đông san ̉ 18%
Ngoai ra, để giam thiêu rui ro, nhà đâu tư cho răng
̀ ̉ ̉ ̉ ̀ ̀
không nên đâu tư vao chứng khoan vượt quá 30%
̀ ̀ ́
tông số vôn đâu tư; đâu tư vao công trai và gửi tiêt
̉ ́ ̀ ̀ ̀ ́ ́
kiêm it nhât 25% tông vôn đâu tư; gửi tiêt kiêm it
̣ ́ ́ ̉ ́ ̀ ́ ̣ ́
nhât 300 triêu đông. Hay xac đinh kế hoach phân bổ
́ ̣ ̀ ̃ ́ ̣ ̣
vôn đâu tư sao cho tông thu nhâp hang năm là lớn
́ ̀ ̉ ̣ ̀
nhât. ́
- Goi x1, x2, x3, x4 tương ứng là số tiên (triêu đông) đâu
̣ ̀ ̣ ̀ ̀
tư vao chứng khoan, công trai, gửi tiêt kiêm, bât đông
̀ ́ ́ ́ ̣ ́ ̣
san ( x j ≥ 0, j = 1,..., 4 )
̉
• Do tông số tiên đâu tư không được vượt quá số tiên
̉ ̀ ̀ ̀
hiên có nên: x1 + x2 + x3 + x4 ≤ 4000 (triêu đông)
̣ ̣ ̀
•Điêu kiên về số tiên đâu tư vao chứng khoan:
̀ ̣ ̀ ̀ ̀ ́
x ≤ 0,3( x + x + x + x ) ⇔ −0,7 x + 0,3x + 0,3x + 0,3x ≥ 0
1 1 2 3 4 1 2 3 4
•Điêu kiên về số tiên đâu tư vao công trai và gửi tiêt kiêm:
̀ ̣ ̀ ̀ ̀ ́ ́ ̣
x2 + x3 ≥ 0, 25 ( x1 + x2 + x3 + x4 ) ⇔ 0, 25 x1 + 0, 75 x2 + 0, 75 x3 − 0, 25 x4 ≥ 0
Và x3 ≥ 300
•Thu nhập của năm là: 0, 2 x1 + 0,12 x2 + 0,15 x3 + 0,18 x4
•Yêu cầu tối ưu: 0, 2 x1 + 0,12 x2 + 0,15 x3 + 0,18 x4 → max
- ̀
Mô hinh:
̀
Tim x = ( x1, x2, x3, x4) sao cho:
f ( x) = 0, 2 x1 + 0,12 x2 + 0,15 x3 + 0,18 x4 → max
x1 + x2 + x3 + x4 ≤ 4000
−0,7 x + 0,3x + 0,3x + 0,3x ≥ 0
1 2 3 4
0, 25 x1 + 0, 75 x2 + 0, 75 x3 − 0, 25 x4 ≥ 0
x3 ≥ 300
x j ≥ 0, j = 1,..., 4
- Vây để lâp mô hinh toan hoc cua môt bai toan thực
̣ ̣ ̀ ́ ̣ ̉ ̣ ̀ ́
tê, ta phân tich bai toan đó theo 3 bước sau:
́ ́ ̀ ́
Bước 1: Đăt ân và điêu kiên cho ân.
̣ ̉ ̀ ̣ ̉
Bước 2: Lâp hệ rang buôc chinh
̣ ̀ ̣ ́
Bước 3: Lâp ham muc tiêu
̣ ̀ ̣
- ̣ ̃
2. Đinh nghia:
Bai toan quy hoach tuyên tinh dang tông quat có dang:
̀ ́ ̣ ́ ́ ̣ ̉ ́ ̣
̀
Tim x = (x1, x2, …,xn) sao cho:
n
f ( x) = ∑ c j x j → min ( max ) ̀ ̣
ham muc tiêu
j =1
Với hệ rang buôc:
̀ ̣
≤
= b , i = 1,..., m ̀ ̣ ́
rang buôc biên
∑ aij x j i ̀ ̣ ́
(rang buôc chinh)
≥
≥ 0
x j ≤ 0 , j = 1, 2,..., n
̀ ̣ ́
rang buôc dâu
tuy y
- Môt số khai niêm:
̣ ́ ̣
Vectơ x=( x1, x2, x3, x4)T được goi là phương an (PA) cua
̣ ́ ̉
bai toan QHTT nêu nó thoa man hệ rang buôc cua bai toan
̀ ́ ́ ̉ ̃ ̀ ̣ ̉ ̀ ́
Phương an x*=( x1*, x2*, x3*, x4*)T được goi là
́ ̣
phương an tôi ưu (PATƯ) cua bai toan QHTT nêu giá trị
́ ́ ̉ ̀ ́ ́
ham muc tiêu tai đó là tôt nhât.
̀ ̣ ̣ ́ ́
Giai bai toan QHTT tức là tim phương an tôi ưu cua nó
̉ ̀ ́ ̀ ́ ́ ̉
́ ́
(nêu co).
- Môt số khai niêm:
̣ ́ ̣
Bai toan giai được là bai toan có PATƯ.
̀ ́ ̉ ̀ ́
Bai toan không giai được là bai toan không có PATƯ.
̀ ́ ̉ ̀ ́
Khi đó hoăc là bai toan không có phương an hoăc có
̣ ̀ ́ ́ ̣
phương an nhưng ham muc tiêu không bị chăn
́ ̀ ̣ ̣
( f ( x ) → +∞ ( −∞ ) đôi với bai toan max (min)).
́ ̀ ́
Nêu phương an x thoa man rang buôc nao đó với dâu
́ ́ ̉ ̃ ̀ ̣ ̀ ́
“=” thì ta noi x thoa man chăt rang buôc đo. Ngược lai
́ ̉ ̃ ̣ ̀ ̣ ́ ̣
nêu thoa dâu “>” hoăc “
- Môt số khai niêm:
̣ ́ ̣
- Ứng với rang buôc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3
̀ ̣
- Ký hiêu:
̣
a1 j
là vectơ cac hệ số cua biên xj trong cac
́ ̉ ́ ́
a2 j
Ai =
. rang buôc (không kể rang buôc dâu).
̀ ̣ ̀ ̣ ́
a3 j
- Hệ vectơ Ai* tương ứng với cac rang buôc chinh tao
́ ̀ ̣ ́ ̣
thanh ma trân rang buôc chinh, ký hiêu là A.
̀ ̣ ̀ ̣ ́ ̣
- Cac rang buôc goi là rang buôc đôc lâp tuyên tinh nêu
́ ̀ ̣ ̣ ̀ ̣ ̣ ̣ ́ ́ ́
hệ vectơ Ai* tương ứng đôc lâp tuyên tinh.
́ ̣ ̣ ́ ́
- Môt số khai niêm:
̣ ́ ̣
- Phương an cực biên (phương an cơ ban): là phương
́ ́ ̉
́ ̉ ̃ ̣ ̀ ̣ ̣ ̣ ́ ́
an thoa man chăt n rang buôc đôc lâp tuyên tinh.
+ Phương an cực biên (PACB) thoa man chăt đung n
́ ̉ ̃ ̣ ́
rang buôc goi là PACB không suy biên, PACB thoa man
̀ ̣ ̣ ́ ̉ ̃
chăt hơn n rang buôc goi là PACB suy biên.
̣ ̀ ̣ ̣ ́
- Ví dụ 1:
f ( x ) = 10 x1 + 12 x2 + 9 x3 → max
x1 − 12 x2 + 5 x3 ≥ 0
8 x1 + 4 x2 − 6 x3 = 52
x ≥ 0, x ≤ 0, x
1 2 3
1 1 -12 5
A = (1, −12,5); A1 = ; A=
*
1
8 8 4 -6
x 0 = ( 13 2;0;0 ) ; x1 = ( 8;0;2 )
- ̀ ̀ ́
Mô hinh bai toan:
̀
Tim x = (x1, x2, x3) sao cho:
f ( x ) = 5000 x + 10000 x + 7000 x → max ̀
Ham muc ̣
1 2 3 tiêu
4 x + 5 x + 3x ≤ 15000
1 2 3
2 x + 4 x + 3x ≤ 12000
1 2 3 Hệ rang buôc chinh
̀ ̣ ́
3x1 + 6 x2 + 4 x3 ≤ 10000
10 x1 + 7 x2 + 6 x3 ≤ 500000
x j ≥ 0, j = 1, 2,3
Hệ rang buôc dâu
̀ ̣ ́
- ́ ̣ ̣ ̣ ̉ ̀ ́
3. Cac dang đăc biêt cua bai toan QHTT:
̀ ́ ̣ ́ ́
a. Bai toan QHTT dang chinh tăc:
n
f ( x ) = ∑ c j x j → max ( min )
j =1
n
∑ aij x j = bi ( i = 1,..., m )
j =1
x j ≥ 0 ( j = 1,..., n )
Đinh ly: Phương an x cua bai toan QHTT dang chinh tăc
̣ ́ ́ ̉ ̀ ́ ̣ ́ ́
là phương án cực biên khi và chỉ khi hệ thông cac vectơ
́ ́
{Aj} tương ứng với cac thanh phân dương cua phương
́ ̀ ̀ ̉
an là đôc lâp tuyên tinh.
́ ̣ ̣ ́ ́
- Ví dụ 2: Cho bài toán QHTT có hệ ràng buộc:
x1 + 2x2 + x4 = 4
3x2 + x3 + 2x4 = 3
x j ≥ 0; j = 1,..., 4
Các phương án
x1 = (4; 0; 3; 0); x2 = (2; 1; 0; 0); x3 = (0; 1/2; 0; 3/4)
là các PACB theo định lý trên.
nguon tai.lieu . vn