trong đó: là n biến cần tìm ;
các số được cho sẵn.
biểu thức (1),(2) gọi là các ràng buộc(RB) của bài toán;
biểu thức (3), (4) gọi là RB (điều kiện) về dấu của biến.
44 trang |
Chia sẻ: lylyngoc | Lượt xem: 1783 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Chương 1: Bài toán Quy hoạch tuyến tính, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 1
BÀI TOÁN
QUY HOẠCH TUYẾN TÍNH
20/6/2012 1MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
NỘI DUNG
1. Bài toán QHTT tổng quát
2. Các dạng của bài toán QHTT
3. Các tính chất của bài toán QHTT
4. Phương pháp hình học
5. Phương pháp đơn hình
20/6/2012 2MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Bài toán QHTT tổng quát
Là bài toán có dạng:
=
= →
≤ =
∑
∑
1
( ) max(min)
, 1,..., (1)
n
j j
j
n
f x c x
a x b i p
20/6/2012 3MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
=
= = +
≥ =
∈ = +
∑
ℝ
1
1
, 1,..., (2)
0, 1,..., (3)
, 1,..., (4)
ij j i
j
n
ij j i
j
j
j
a x b i p m
x j q
x j q n
Bài toán QHTT tổng quát
trong đó: là n biến cần tìm ;
các số được cho sẵn.
biểu thức (1),(2) gọi là các ràng buộc(RB) của bài toán;
biểu thức (3), (4) gọi là RB (điều kiện) về dấu của biến.
=, 1,...,jx j n
= =, 1,..., ; , , 1,...,j ij ic j n a b i m
20/6/2012 4MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Bài toán QHTT tổng quát
• Gọi D:= {x : thỏa mãn các ràng buộc (1) – (4)} là
tập ràng buộc (hay miền chấp nhận được (cnđ))
của bt.
• Mỗi gọi là phương án (PA) cnđ.∈x D
• PA cnđ thỏa mãn
(đ/v bài toán min)
được gọi là PA tối ưu (PATƯ).
• Giá trị được gọi là giá trị (mục tiêu) tối ưu.
20/6/2012 5MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
*x ≤ ∀ ∈*( ) ( ),f x f x x D
*( )f x
Bài toán QHTT tổng quát
Ví dụ 1 [1] Công ty RM sản xuất hai loại nước sơn:
s.nội thất và s.ngoài trời. Nguyên liệu gồm A (có 6
tấn) và B (có 8 tấn). Biết rằng:
• 1 tấn s.nội thất cần: 2 tấn A , 1 tấn B;
• 1 tấn s.ngoài trời cần: 1 tấn A, 2 tấn B.
Qua tiếp thị, được biết nhu cầu thị trường là như sau
(cho 1 ngày):
20/6/2012 6MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Bài toán QHTT tổng quát
• Nhu cầu s.nội thất không hơn nhu cầu s. ngoài trời
quá 1 tấn;
• Nhu cầu cực đại của s.nội thất là 2 tấn.
Vấn đề: Cty cần phải sx mỗi ngày như thế nào để
doanh thu là lơn nhất?
Biết rằng: 1 tấn s.nội thất giá 2000USD;
1 tấn s.ngoài trời giá 3000 USD.
20/6/2012 7MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Bài toán QHTT tổng quát
Gọi x, y là số tấn s.nội thất và s.ngoài trời được sx
ra trong ngày.
Mô hình bài toán:
= + →( , ) 2 3 maxf x y x y
20/6/2012 8MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
+ ≤
+ ≤
− ≤
≤
≥
2 6
2 8
1
2
, 0
x y
x y
x y
x
x y
Các dạng của bài toán QHTT
1. Dạng tổng quát
=
= →
≤ =
∑
∑
1
( ) max(min)
, 1,...,
n
j j
j
n
f x c x
a x b i p
20/6/2012 9MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
=
= = +
≥ =
∈ = +
∑
ℝ
1
1
, 1,...,
0, 1,...,
, 1,...,
ij j i
j
n
ij j i
j
j
j
a x b i p m
x j q
x j q n
Các dạng của bài toán QHTT
2. Dạng chính tắc
=
= →
∑
1
( ) max(min)
n
j j
j
n
f x c x
20/6/2012 10MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
= =
≥ =
∑
1
, 1,...,
0, 1,...,
ij j i
j
j
a x b i m
x j n
Các dạng của bài toán QHTT
3. Dạng chuẩn tắc
=
= →
∑
1
( ) max( )min
n
j j
j
n
f x c x
20/6/2012 11MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
≤ =
≥ =
≥∑
1
( ) , 1,...,
0, 1,...,
ij j i
j
j
a x b i m
x j n
Các tính chất của bài toán QHTT
Xét 2 tính chất cơ bản:
• Tập hợp D các PA của bài toán QHTT (dạng bất
kỳ) là một tập lồi.
• Nếu một QHTT có ít nhất một PA và hàm mục
tiêu bị chặn dưới trong miền ràng buộc (đ/v bài
toán min) thì bài toán chắc chắn có PATƯ.
20/6/2012 12MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp hình học (pp đồ thị)
Thường dùng để giải bài toán QHTT có 2 biến.
Xét bài toán có dạng:
Tìm x1, x2 sao cho:
= + →
20/6/2012 13MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
+ ≥ =
≥ ≥
1 2 1 2
1 1
1
2
2 2
1
2
( , ) min
, 1,
( 0, 0)
i i i
f x x x x
a x a x i
c
x
c
b m
x
Phương pháp hình học
• Mỗi bpt tuyến tính xác định
một nửa mặt phẳng.
• Tập là
+ ≥1 1 2 2i i ia x a x b
{ }= = + ≥ =1 2 1 1 2 2( , ) : , 1,i i iD x x x a x a x b i m
giao của m nửa mặt phẳng.
20/6/2012 14MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
x2 (3)(2)
x1O
(1)
D
7/27/2012 15MaMH 501014 Chương 1 Bài toán Quy hoạch tuyến tính
Phương pháp hình học
20/6/2012 16MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
D
Phương pháp hình học
Phương trình khi thay đổi sẽ xác
định trên mặt phẳng các đường thẳng song song
với nhau (gọi là đường mức), với giá trị mức
α+ =21 1 2c cx x α
α.
Bài toán: Trong số các đường mức cắt D, hãy tìm
đường mức với giá trị mức nhỏ nhất.
20/6/2012 17MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
α
Phương pháp hình học
Phương pháp:
• Xác định D.
• Vẽ véctơ , rồi vẽ đường mức qua gốc
tọa độ và vuông với véctơ
• Đ/v bt min, tịnh tiến đường mức ngược hướng
= 1 2( ),cc c
= 1 2,( ).cc c
với véctơ đến mức thấp nhất mà vẫn
còn cắt miền D (đường min).
Khi đó, “đường min” tiếp xúc với D và đặt D về
cùng một phía. Tiếp điểm tương ứng chính là
PATƯ.
20/6/2012 18MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
= 1 2( ),cc c
Phương pháp hình học
• Đối với bài toán max, thì làm ngược lại.
•Tịnh tiến mãi mà không tìm được điểm tiếp xúc→
bài toán không có PATƯ.
20/6/2012 19MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp hình học
Ví dụ 2 Giải bài toán sau bằng pp hình học
= + →
+ ≤
(1)
( , ) 2 3 max
2 6
f x y x y
x y
20/6/2012 20MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
+ ≤
− ≤
≤
≥
(2)
(3)
(4)
2 8
1
2
, 0.
x y
x y
x
x y
Phương pháp hình học
PATƯ của bài toán là tọa độ của điểm F = (1)∩(2).
20/6/2012 21MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp đơn hình
Ý tưởng: tiến hành khảo sát các đỉnh của miền
ràng buộc để tìm ra đỉnh tối ưu.
20/6/2012 22MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp đơn hình
Xét bài toán có dạng chính tắc sau:
+ +
= + + + →
+ + + =
+ + + =
1 2
1( 1) 1 1 1
1
1
2( ) ... min
...
...
n
m m n n
nf x x x x
a x a x b
a x a x b
c c
x
x
c
với
20/6/2012 23MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
+ +
+ +
+ + + =
≥ =
⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
2( 1) 1 2 2
( 1) 1
2
...
0, 1,
m m n n
m m m n m
j
m mna x a xx
j n
b
x
> =0, .1,ib i m
Phương pháp đơn hình
Định nghĩa 1: Biến cơ sở là biến đi với véctơ cột
đơn vị.
• Trong bt trên, các biến cơ sở là , các
biến còn lại là biến không cơ sở (có giá trị = 0).
1 2, ,..., mx x x
• Khi đó, là một PACB xuất
phát của bài toán.
20/6/2012 24MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
0
1 2( , ,..., ,0,...,0)mx b b b
Phương pháp đơn hình
Ví dụ 3 Bài toán
= + − + →
+ − =
1 2 3 4
1 2 3 (1)
( ) 3 5 2 min
4 1
f x x x x x
x x x
có PACB xuất phát là
(biến x1, x4 là biến cơ sở).
20/6/2012 25MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
+ + =
≥ =
2 3 4 (2)3 5
0, 1,4j
x x x
x j
=
0 (1,0,0,5),x
Phương pháp đơn hình
• Mỗi véctơ cột được biểu diễn qua
véctơ cơ sở:
=, 1,2,...,jA j n
= + + + =⋯1 1 2 2 , 1,j j j mj mA a A a A a A j n
• Giá trị mục tiêu tại x0 :
20/6/2012 26MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
= = + + +⋯0 0 0 1 1 2 2( ) , m mf x c x c b c b c b
Phương pháp đơn hình
• Số được gọi là ước lượng tương ứng
của biến , với
∆ =, 1,j j n
jx
=
∆ = − =∑
1
, 1, .
m
j i ij j
i
c a c j n
20/6/2012 27MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp đơn hình
Định lý 1 (Dấu hiệu tối ưu)
Nếu x0 là PACB sao cho thì x0 là
PATƯ.
∆ ≤ ∀ =0, 1,j j n
20/6/2012 28MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp đơn hình
Định lý 2 (Dấu hiệu bài toán không có lời giải)
Nếu ngoài cơ sở liên kết của PACB x0 sao cho
và (I0 là tập chỉ số biến cơ
sở), thì bài toán không có PATƯ.
∃ jA
∆ > 0j ≤ ∀ ∈ 00,ija i I
20/6/2012 29MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp đơn hình
Định lý 3 (Tìm PAmới tốt hơn)
Nếu ngoài cơ sở liên kết của PACB x0 sao cho
và với mà đều có ít nhất một chỉ
số sao cho thì ta có thể tìm được một
∃ jA
∆ > 0j
> 0,ija
j ∆ > 0j
∈ 0i I
PACB mới x1 tốt hơn x0 .
20/6/2012 30MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Phương pháp đơn hình
Thuật toán đơn hình
− Bước 1: Lập bảng đơn hình (tương ứng với x0)
− Bước 2: Kiểm tra các ước lượng
Sau khi tính tiến hành kiểm tra∆ ,j
∆ ≤ =• Nếu dấu hiệu tối ưu xuất hiện thì
PA đang xét là PATƯ.
• Nếu xuất hiện dấu hiệu hàm mục tiêu không bị
chặn thì kết luận bài toán
không có PATƯ.
20/6/2012 31MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
( 0, 1, )j j n
∃∆ > ≤ ∈ 0( 0, 0, )j ija i I
Phương pháp đơn hình
• Nếu không xảy ra 2 trường hợp trên, thì ta có thể
tìm được PA mới tốt hơn như sau:
1. Xác định biến vào
∆ ∆ > = ∆max{ : 0}j j k
kx
2. Xác định biến ra
với là các phần tử ở cột PA. Khi đó, phần tử
được gọi là phần tử trục.
20/6/2012 32MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
> =0 0min{ : 0}i i s
ik ks
k
a a
a
a a
sx
ska0ia
Phương pháp đơn hình
Tiếp theo, lập bảng đơn hình mới,
− Tính các giá trị của hàng mới vào:
′ = ≡,
sj
kj
sk
a
a i s
a
− Tính các giá trị còn lại trong bảng đơn hình:
20/6/2012 33MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
′ = − ≠,sjij ij ik
sk
a
a a a i s
a
′∆ = ∆ − ∆sjj j k
sk
a
a
Phương pháp đơn hình
Ví dụ 4 Giải bài toán sau bằng pp đơn hình
= + − + →
+ − =
1 2 3 4
1 2 3 (1)
( ) 3 5 2 min
4 1
f x x x x x
x x x
20/6/2012 34MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
+ + =
≥ =
2 3 4 (2)3 5
0, 1,4j
x x x
x j
Phương pháp đơn hình
Lập bảng đơn hình (PACB
Hệ
số
Biến
cơ sở
Phương
án
3 5 -1 2
x1 x2 x3 x4
=
0 (1,0,0,5))x
20/6/2012 35MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
3 x1 1 1 4 -1 0
2 x4 5 0 1 3 1
f(x0) = 13 0 9 4 0
∆1
∆2
∆3
∆4
Phương pháp đơn hình
Tìm PA mới:
Hệ
số
Biến
cơ sở
Phương
án
3 5 -1 2
x1 x2 x3 x4
20/6/2012 36MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
5 x2 1/4 1/4 1 -1/4 0
2 x4 19/4 -1/4 0 13/4 1
f(x1) = 43/4 -9/4 0 25/4 0
Phương pháp đơn hình
Tìm PA mới:
Hệ
số
Biến
cơ sở
Phương
án
3 5 -1 2
x1 x2 x3 x4
5 x 8/13 3/13 1 0 1/13
20/6/2012 37MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
2
-1 x3 19/13 -1/13 0 1 4/13
f(x2) = 21/13 -23/13 0 0 -25/13
Phương pháp đơn hình
Vì nên:
• PATƯ của bài toán: =* (0,8 / 13,19 / 13,0);x
∆ ≤ =0, 1,4j j
• Giá trị tối ưu:
20/6/2012 38MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
*( ) 21/ 13.f x
Phương pháp đơn hình
Lưu ý
1. Nếu bài toán , thì hoặc:
- Chuyển về bài toán
- Hoặc giải trực tiếp bài toán
( ) maxf x →
( ) ( ) min;g x f x= − →
( ) max.f x →
2. Ở bảng đơn hình tối ưu, nếu có với là
biến không cơ sở thì bài toán có PATƯ khác.
20/6/2012 39MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
0,j∆ = jx
Phương pháp đơn hình
Bài toán mở rộng
Xét bài toán ở dạng chính tắc:
1 1 2 2
11 1 12 2 1 1
( ) ... min
...
n n
n n
f x c x c x c x
a x a x a x b
= + + + →
+ + + =
20/6/2012 40MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
21 1 22 2 2 2
1 1 2 2
...
...
0, 1,
n n
m m mn n m
j
a x a x a x b
a x a x a x b
x j n
+ + + =
+ + + =
≥ =
⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
Phương pháp đơn hình
Giả sử bài toán chưa có biến cơ sở. Ta thêm vào
mỗi phương trình một biến giả với
hệ số là 1.
Trên hàm mục tiêu, các biến giả có hệ số là
0, 1,n ix i m+ ≥ =
với M là số
dương rất lớn.
20/6/2012 41MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
( ( ) min),M f x+ → ( ( ) max),M f x− →
Phương pháp đơn hình
Bài toán mở rộng:
1 1 2 2
11 1 12 2 1 1
1
1
( ) ... min
... 1
( )
m
n i
i
n
n n
n n
M x
x
f x c x c x c x
a x a x a x b
+
=
+
= + + + →
+ + + =
+
+
∑
20/6/2012 42MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
21 1 22 2 2 2
1 1 2 2
2...
...
0, 1
1
1
,
n
n m
n n
m m mn n m
j
xa x a x a x b
a x a x a x b
x mj
x
n
+
+
+ + + =
+ + + =
≥ +=
+
+
⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
Phương pháp đơn hình
Xét dấu
• nếu hoặc và
• nếu hoặc và
j j jMδ γ∆ = +
0j∆ > 0jδ > ( 0jδ = 0)jγ >
0j∆ < 0jδ < ( 0jδ = 0)jγ <
• nếu hoặc và
Các bước tính toán như pp đơn hình thông thường.
20/6/2012 43MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
j k∆ > ∆ j kδ δ> ( j kδ δ= )j kγ γ>
Phương pháp đơn hình
Quan hệ giữa bt mở rộng và bt gốc:
1. Nếu bt mở rộng không có PATƯ, thì bt gốc
cũng không có PATƯ.
2. Nếu bt mở rộng có PATƯ là
* * * *( , ,..., ,0,...,0)x x x x=
thì bt gốc có PATƯ là
3. Nếu bt mở rộng có PATƯ là
thì bt gốc không có PA.
20/6/2012 44MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
1 2 n
* * * *
1 2( , ,..., )nx x x x=
* * * *
1 2( , ,..., ,0,0, 0,..,0)
n i
n
x
x x x x a
+
= >