Xem mẫu
- TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
BỘ MÔN KHOA HỌC CƠ BẢN
BÀI GIẢNG
QUY HOẠCH TUYẾN TÍNH
- Chương I: BÀI TOÁN QUY HOẠCH TUYẾN
TÍNH
Chương II: BÀI TOÁN VẬN TẢI
Chương III: MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI
- CHƯƠNG I:
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1.1. Bài toán quy hoạch tuyến tính tổng quát
1.2. Bài toán dạng chính tắc
1.3. Bài toán dạng chuẩn
1.4. Các tính chất chung
1.5. Phương pháp đơn hình
1.6. Phương pháp đơn hình đối ngẫu
- 1.1. Bài toán quy hoạch tuyến tính tổng quát
n
f ( x ) = ∑ c j x j → min (max)
j=1
n
∑ a ij x j = b i ( i ∈ I1 )
j=1
n
a x ≥ ( ≤) b ( i ∈ I )
∑ ij j i 2
j=1
Hàm f(x) gọi là hàm mục tiêu
Mỗi phương trình hoặc bất phương trình trong hệ điều
kiện gọi là một ràng buộc.
- ■ Một số khái niệm :
Phương án: Vectơ x = (x1, x2,..., xn) thoả mãn mọi điều
Ph
kiện ràng buộc của bài toán gọi là một phương án.
n
∑a x = b i thì ràng buộc i gọi là “chặt” đối với
-Nếu ij j
j=1
phương án x, hoặc phương án x thoả mãn chặt ràng buộc i.
n
-Nếu ∑ a ij x j > (
- 1.2. Bài toán dạng chính tắc:
n
f ( x ) = ∑ c j x j → min (max)
j=1
n
∑ a ij x j = b i (i = 1, m)
j=1
x ≥ 0 (j = 1, n )
j
Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài
toán dạng chính tắc tương đương theo nghĩa trị tối ưu của
hàm mục tiêu trong hai bài toán là trùng nhau và từ phương
án tối ưu của bài toán này suy ra phương án tối ưu của bài
toán kia
- ●Cách đưa bài toán về dạng chính tắc
-Nếu xj ≤ 0 thì đổi biến xj’= −xj ≥ 0.
n
∑a x ≤ bi
-Nếu một nràng buộc có dạng thì có thể
ij j
thay bằng ∑
j=1
a ij x j + x = b i với x ip ≥ 0 và hệ số của
p
i
j=1
p
x x ip
i
n
∑ ọi
Các biến a ij x jg≥ iblà biến phụ.
trong f(x) bằng 0.
n j=1
∑
-Nếu mộa ij x j − x = có dạng x ip ≥ 0
p
bi
buiộc
t ràng thì thay
j=1
bằng ,
-Nếu xj không có ràng buộc dấu thì đặt xj = xj’− xj’’,
- Ví dụ: Đưa bài toán sau về dạng chính tắc:
f(x) = –2x1 + x2 + 3x3 + 5x4 ⇒ min
x1 – 3x2 + 5x3 – x4 ≤ 16
2x1 – x2 – 2x3 + 2x4 ≥ – 4
4x1 + 3x2 + x3 + x4 = 9
x1, x2 ≥ 0, x3 ≤ 0
- Các biến phụ sẽ được đánh số tiếp là x5, x6.
Đặt x3’= – x3 ≥ 0, x4 = x4’ – x4’’, x4’, x4’’ ≥ 0.
Ta được bài toán chính tắc tương đương sau:
f(x) = –2x1 + x2 – 3x3’ + 5x4’ – 5x4’’ ⇒ min
x – 3x2 – 5x3’ – x4’ + x4’’ + x5 = 16
1
2x – x2 + 2x3’ + 2x4’ – 2x4’’ – x6 = –4
1
4x + 3x2 – x3’ + x4’ – x4’’ =9
1
x1, x2 , x3’, x4’, x4’’, x5, x6 ≥0
- 1.3. Bài toán dạng chuẩn
n
f ( x ) = ∑ c j x j → min (max)
j=1
x1 + a 1m +1x m +1 + a 1m + 2 x m + 2 + ...... + a 1n x n = b1
x 2 + a 2m +1x m +1 + a 2m + 2 x m + 2 + ...... + a 2n x n = b 2
......................................................................
x + a
mm +1 x m +1 + a mm + 2 x m + 2 + ...... + a mn x n = b m
m
x j ≥ 0 (j = 1, n )
Trong đó: b i ≥ 0, (i = 1, m)
- Bài toán dạng chuẩn là bài toán dạng chính tắc có vế
phải không âm và mỗi phương trình đều có một biến số
với hệ số bằng 1 đồng thời không có trong các phương
trình khác (gọi là biến cô lập với hệ số bằng 1).
Từ hệ phương trình ràng buộc của bài toán dễ dàng suy
ra một phương án đầu tiên: x0 = (b1, b2, …,bm, 0, 0,…, 0),
với cơ sở là {A1, A2,…Am} = E, đó là phương án cực biên.
- 1.4. Các tính chất chung
1. Tính chất 1: Sự tồn tại phương án cực biên:
Nếu bài toán có phương án và hạng của ma trận hệ
ràng buộc bằng n thì bài toán có phương án cực biên.
Hạng của ma trận hệ ràng buộc của bài toán dạng chính
tắc luôn luôn bằng n nên nếu bài toán chính tắc có phương
án thì phải có phương án cực biên.
2. Tính chất 2: Sự tồn tại phương án tối ưu:
Nếu bài toán có phương án và trị số hàm mục tiêu bị
chặn trên tập phương án thì bài toán có phương án tối ưu.
3. Tính chất 3: Tính hữu hạn của số phương án cực
biên:
Số phương án cực biên của mọi bài toán quy hoạch
- 1.5. Phương pháp đơn hình
1. Nội dung của phương pháp:
Xuất phát từ một phương án cực biên đầu tiên, tìm cách
đánh giá phương án cực biên ấy, nếu nó chưa tối ưu thì
tìm cách chuyển sang một phương án cực biên mới tốt
hơn, quá trình được lặp lại vì số phương án cực biên là
hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận
bài toán không giải được vì hàm mục tiêu không bị chặn
hoặc sẽ tìm được phương án tối ưu.
Phương pháp này chỉ áp dụng được cho những bài toán
có phương án cực biên, tuy nhiên mọi bài toán QHTTT
đều có thể đưa về bài toán dạng chính tắc, và khi nó đã có
phương án thì sẽ có phương án cực biên.
Do đó không làm mất tính chất tổng quát từ đây ta sẽ
chỉ xét bài toán dạng chính tắc.
- 2. Cơ sở của phương án cực biên:
Định nghĩa: Một hệ vectơ {Aj } độc lập tuyến tính bao
hàm hệ thống các vectơ tương ứng với các thành phần
dương của phương án cực biên x gọi là cơ sở của phương
án cực biên ấy
Ký hiệu: J, trong đó: J = {j, Aj nằm trong cơ sở}.
Một phương án cực biên không suy biến có đúng m thành
phần dương, có một cơ sở duy nhất, đó chính là các vectơ
tương ứng với các thành phần dương, còn phương án cực
biên suy biến thì có nhiều cơ sở khác nhau, phần chung của
chúng là các vectơ tương ứng với các thành phần dương.
- 3. Thuật toán của phương pháp đơn hình
Giả sử đã biết phương án cực biên x0, cơ sở J0. Lập
bảng đơn hình tương ứng:
Hệ Cơ Phươn c1 c2 … cr … cm cm+1 … ck … cs … cn
số sở gán: xJ x x … x … x x … x … x … x
1 2 r m m+1 k s n
cJ J
c1 x1 x10 1 0 … 0 …0 x1,m+1… x1k … x1s… x1n
c2 x2 x20 0 1 … 0 …0 x2,m+1… x2k … x2s … x2n
… … … …………………………………………….
cr xr xr0 0 0 … 1 … 0 xr,m+1… xrk … xrs … xrn
…………………………………………………….
… … …
0 0…0…1 xm,m+1…xmk …xms ... xmn
cm xm xm0
f(x) f(x0) 0 0…0…0 ∆m+1 … ∆k … ∆s … ∆n
- Bước 1: Kiểm tra dấu hiệu tối ưu:
∑c x
Tính các ước lượng ∆k theo công thức: Δ = − ck
k j jk
j∈J
-Nếu ∆k ≤ 0, (∀k ∉ J0) thì x0 là phương án tối ưu.
-Nếu ∆k > 0 thì x0 không phải là phương án tối ưu,
chuyển sang bước 2.
Bước 2: Kiểm tra tính không giải được của bài toán:
-Nếu tồn tại một ∆k > 0 mà xjk ≤ 0 (∀j ∈ J0) thì bài toán
không có phương án tối ưu.
-Nếu với mỗi ∆k > 0 đều có ít nhất một xjk > 0 thì
chuyển sang bước 3.
- Bước 3: Chọn vectơ đưa vào cơ sở và xác định vectơ
loại khỏi cơ sở:
-Giả sử max ∆ k = ∆ s , vectơ As được đưa vào cơ sở,
∆ k >0
x0
j
tính θ 0 = min
x js
j∈J 0 , x js > 0
x0
( r ∈ J 0 , x rs > 0)
-Giả sử θ 0 = r
x rs
Vectơ Ar bị loại khỏi cơ sở
Phần tử xrs gọi là phần tử xoay của phép biến đổi.
Lập bảng đơn hình mới, thay xs vào vị trí xr, và cs vào
vị trí cr. Chuyển sang bước 4.
- tổng quát cho toàn bộ bảng (bao gồm cả hàng ước lượng
∆ k).
-Để tính hàng vectơ đưa vào (xs) trong bảng mới ta
lấy hàng vectơ loại ra (xr) trong bảng cũ chia cho phần tử
xoay.
-Để tính hàng xj trong bảng mới, ta lấy hàng xj trong
bảng cũ trừ đi hàng xs vừa mới tính được sau khi nhân nó
với xjs.
Kết quả của quá trình biến đổi sẽ cho ta bảng đơn hình
ứng với phương án cực biên mới x1, tốt hơn x0.
Đối với x1 quay trở lại bước 1 và quá trình lặp lại sau
một số hữu hạn bước sẽ tìm được phương án cực biên tối
ưu hoặc kết luận bài toán không giải được vì hàm mục tiêu
không bị chặn.
- Ví dụ 1: Giải bài toán sau bằng phương pháp đơn hình:
f(x) = 2x1 + 3x2 – x3 – 1/2x4 ⇒ min
x – x2 + x3 + 1/2x4 = 18
1
x2 – 4x3 + 8x4 ≤ 8
–2x2 + 2x3 – 3x4 ≤ 20
xj ≥ 0 (j =1…4)
- Trước hết đưa bài toán về dạng chính tắc bằng cách
cộng vào ràng buộc hai và ba hai biến phụ x5 và x6. Ta có:
f(x) = 2x1 + 3x2 – x3 – 1/2x4 ⇒ min
x1 – x2 + x3 + 1/2x4 = 18
x2 – 4x3 + 8x4 + x5 =8
–2x2 + 2x3 – 3x4 + x6 = 20
xj ≥ 0 (j = 1…6)
nguon tai.lieu . vn
