Tổng hợp Bài toán tối ưu có giải | Học viện Phụ nữ Việt Nam

Tổng hợp Bài toán tối ưu có giải | Học viện Phụ nữ Việt Nam. Tài liệu gồm 64 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!

1
ĐỀ CƯƠNG BÀI GIẢNG
Hc phn:
CÁC PP T
ỐI
ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 1 Tiết 1-3
GV giảng: 3, Bài tập: 0, Tự học :3
Giáo vn: Nguyễn Trọng Toàn
Vũ Anh M
Chương 1 Bài toán ti ưu hoá và các vấn đề cơ sở
Các mục
1.1 Bài toán TUH và phân loi bài toán.
1.2 Một số hình thực tế
1.3 Không gian Euclide n-chiều
Mc đích -
yêu cầu
- Nắm được ý nghĩa ứng dụng trong thực tiễn của các bài toán TUH
- Nhc lại và bổ xung một s kiến thức ĐSTT có liên quan
NỘI DUNG
I. LÝ THUYẾT
Chương 1. BÀI TOÁN TỐI ƯU HÓA VÀ CÁC VẤN ĐỀ CƠ SỞ
1.1 BÀI TOÁN TI ƯU HÓA VÀ PHÂN LOẠI BÀI TOÁN
1.1.1 Bài toán tối ưu hoá tổng quát
Min (hoặc Max) của hàm f(x) (1.1)
với các điều kiện
i i
n
g (x) , , b ; i=1,m
x X R ,
(1.2)
trong đó:
- f(x) : Hàm mục tiêu với n biến.
- g
i
(x) ,
i 1,m
: Các hàm ràng buc. Mỗi bất đẳng thức gi là mt ràng buc.
- Tập
| 1
n
i i
D x X R g ( x ) , , b ;i ,m
Miền ràng buc (1.3)
- x = (x
1
,x
2
,..., x
n
) D : Phương án hay lời giải chấp nhận được.
- Phương án x
*
D làm cực đại (cực tiểu) hàm mc tiêu gọi là phương án hay lời
giải tối ưu. Cthể là: f(x
*
) f(x), x D đối với bài toán max hay f(x
*
) f(x),
x D đối với bài toán min. Khi đó f
*
= f(x
*
) gọi là g tr tối ưu của bài toán.
1.1.2 Phân loi bài toán
Để tìm thuật giải hiệu quả cho các bài toán Ti ưu hoá cần phân loại các bài toán:
- Quy hạch tuyến tính (QHTT);
- Quy hoach phi tuyến (QHPT);
- Qui hoch rời rạc ( QHRR);
- Qui hoch đa mục tiêu (QHĐMT).
1.2 MT S MÔ HÌNH THỰC TẾ
1.2.1i toán lập kế hoạch sản xuất tối ưu
Mt công ty muốn sản xuất 2 loại sản phẩm A và B bằng các loại nguyên liệu I,
II và III. Chi phí sn xuất cho một đơn vị sn phm được cho trong bảng sau:
2
Sn phẩm
Nguyên liệu
A B
I 2 1
II 1 2
III 0 1
Gisử công ty lương dtrữ nguyên liệu:
I 8
III 3
(Đơn vị nguyên liệu). Tin
lãi cho 1 đơn vị sản phẩm loại A và B ơng ứng : 4 và 5 (đơn vị tiền tệ). Cn lp kế
hoạch sản xuất sao cho công ty thu được lãi nhiều nhất với điều kiện hạn chế về nguyên
liệu như trên.
Kí hiệu x
1
và x
2
tương ứng là số lượng sản phm loại A và B cần sản xuất. Mô hình
toán học của bài toán trên có dạng một bài toán QHTT:
f(x) = 4x
1
+ 5 x
2
max
với điều kiện
1 2
1 2
2
1 2
2x x 8
x 2x 7
x 3
x ,x 0
Như vậy, bài toán lp kế hoạch sản xuất tổng quát có dạng:
n
j j
j 1
f(x) c x
max
n
ij j i
j 1
j
a x b ,i 1,m
x 0, j 1,n
trong đó: + x
j
: Ssản phẩm loại j (
j 1,n
) cần sản xuất ;
+ c
j
: Tiền lãi của một đơn vị sản phẩm loại j ;
+ a
ij
: Suất chi phí nguyên liệu loại i(
i 1,m
) cho một đơn vị sản phẩm loại j ;
+ b
i
: lượng dự trữ nguyên liệu loại i.
1.2.2 i toán vn tải
- m kho hàng cha cùng một loại hàng h được đánh số thứ tự
i 1,m
gọi
là điểm phát thi. Lượng hàng chứa tại điểm phát thứ i a
i
;
- n điểm tiêu thloại hàng hoá trên được đánh số thứ tự
j 1,n
gi điểm
thu thj; Điểm thu thứ j có nhu cu tiêu thhàng là b
j
.
- Biết c
ij
cước phí vận chuyn 1 đơn vị hàng hoá t điểm phát thứ i điển thu
th j (
i 1,m
;
j 1,n
).
y lp kế hoạch vận chuyển từ các điểm phát đến các điểm thu sao cho chi phí
vận chuyn là ít nhất với điều kiện: Các điểm phát phải pt hết hàng các điểm thu
thì tho mãn đủ nhu cầu.
Đặt x
ij
ợng hàng cần vận chuyn từ điểm phát A
i
đến điểm thu B
j
(
i 1,m
;
j 1,n
). Khi đó mô hình toán học của bài toán vận tải (BTVT) có dạng:
3
F(X) =
m n
ij ij
i 1 j 1
c x
min
với điều kiện:
n
ij i
j 1
m
ij j
i 1
ij
x a i 1,m
x b j 1,n
x 0 i =1,m ; j =1,n
Để bài toán có lời giải, thì nó phi thoả mãn điều kiện cân bằng thu phát:
m n
i j
i 1 j 1
a b
.
1.3 KNG GIAN EUCLIDE n-CHIỀU TRÊN TRƯỜNG SỐ THỰC
1.3.1 Tích vô hướng của 2 vector
- Tích hướng trên không gian vector V
là một hàm xác định trên VV thoả mãn:
i) <x, y> = <y, x> x,y V
ii) <x + y,z > = < x,z> + <y , z> x,y,z V
iii) <x,y > = <x,y> = <x,y> x,y V , R
iv) <x,x> 0 ; <x,x> = 0 x= 0
- Nếu <x,y> = 0 ta nói 2 vector x và y trc giao với nhau.
1.3.2 Siêu phng và nửa không gian
Cho vector aR
n
s thực , siêu phẳng P trong không gian R
n
là tp
n
P x R | a,x
Nếu = 0 thì P mt không gian con n-1 chiều. Mỗi siêu phẳng P chia không
gian R
n
thành 2 na không gian:
1
n
P x R | a,x
: Nửa không gian đóng
2
n
P x R | a,x
: Nửa không gian mở
1.3.3 Đa tạp tuyến tính
Định nghĩa 1.2 Giả sử A =(a
ij
)
mxn
, b
R
m
rank(A) = m khi đó tập:
n
A x R | Ax b
được gi là 1 đa tạp tuyến tính có thứ nguyên r = n-m.
Nếu b=0 thì D một không gian con r chiều. Như vậy siêu phẳng 1 đa tạp
tuyến tính có thứ nguyên n-1, đường thẳng là một đa tp tuyến tính thứ nguyên là 1,
mt điểm đa tạp tuyến nh thứ nguyên 0 không gian R
n
mt đa tạp tuyến
tính n thnguyên. Thnguyên ca một tập hợp là thnguyên của đa tạp tuyến tính
bé nht chứa nó.
II. TÀI LIỆU THAM KHẢO
1. Nguyễn Đức Nghĩa, Tối ưu hoá, Nxb GD, 1999
2. Trần Vũ Thiệu-Bùi Thế Tâm, Ti ưu h, Nxb GTVT, 2000
3. Nguyễn Địch, thuyết tối ưu hoá, Nxb ĐHQG nội, 2003
4
ĐỀ CƯƠNG BÀI GIẢNG
Hc phn:
CÁC PP T
ỐI
ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 2 Tiết 4-6
GV giảng: 3, Bài tập: 0, Tự học :3
Giáo vn: Nguyễn Trọng Toàn
Vũ Anh M
Chương 1 Bài toán ti ưu hoá và các vấn đề cơ sở
Các mục
1.3 Không gian Euclide n-chiều
1.4 Cơ sở giải tích lồi
Mc đích -
yêu cầu
- Nhc lại và bổ xung một s kiến thức ĐSTT có liên quan
- Nắm được cơ s và ý nghĩa hình học của các khái niệm toán học
NỘI DUNG
LÝ THUYẾT
1.4 SỞ GIẢI TÍCH LỒI
1.4.1 Đường thẳng đi qua 2 điểm
Cho 2 đim a và bR
n
, đường thẳng đi qua a và b là tập :
1
n
x R | x a b, R
.
Chú ý:
+
1
1 1
n
x R | x a b,
= [a, ): Na đường thẳng xuất phát từ a.
+
2
1 0
n
x R | x a b,
= [b, ): Nửa đường thẳng xuất phát từ b.
+
3
1 0 1
n
x R | x a b,
= [a,b]: Đoạn thẳng nối a với b.
1.4.2 Tập hợp lồi
Định nghĩa 1.1 Tập C được gọi là một tập lồi nếu x, y C thì
0 1 1
, ,x a b C

i i
a ,x b
Nghĩa là nếu x,y C thì C chứa cả đoạn thng nối x và y.
Thứ nguyên ca tập lồi là thnguyên của đa tạp tuyến tính nhỏ nhất chứa nó.
c tập lồi Các tp không lồi
Định lí 1.1 Giao của 2 tập lồi là tập lồi
5
Chứng minh:
1.4.3 Tổ hợp lồi
Cho họ gồm m vector S = {a
1
, a
2
, a
3
,... a
m
} R
n
. Tổ hợp lồi của họ S là biểu thức:
x :=
m
i i
i 1
x
vi
i
0 ,
i 1,m
và
m
i
i 1
=1
Tậpc tổ hợp lồi của S được gọi là bao lồi (convex hull) của S, kí hiệu conv(S).
T định nghĩa trên ta thy đoạn thẳng [a,b] là bao li của 2 điểm a và b cũng là
tập lồi nhỏ nhất chứa a và b.
Định lý 1.2 Nếu X là tập lồi thì nó chứa tổ hợp lồi của một số điểm bất k của nó.
Chứng minh: (Bằng phương pháp qui nạp theo m). Gis X là tập lồi và x
1
,x
2
, x
3
,...
x
m
X. Đặt x =
m
i i
i 1
x
vi
i
0,
i 1,m
m
i
i 1
=1. Ta cần chứng minh xX.
Thật vậy:
- Với m =2 ta x =
1
x
1
+
2
x
2
với
1
,
2
0
1
+
2
=1. Suy ra x=
1
x
1
+
(1-
1
) x
2
[x
1
, x
2
]. Do đó x X.
- Gisử định đúng cho m-1 điểm, tức là
m 1
i i
i 1
x
với
i
0 ,
i 1,m 1
m 1
i
i 1
=1. Đặt =
m 1
i
i 1
ta
m 1
i
i 1
=1
m
=1- 0 khi đó x =
m
i i
i 1
x
=
m 1
i
i 1
x
i
+(1-)x
m
Do giả thiết qui nạp ta
m 1
i
i 1
x
i
X , n nữa và x
m
X nên x X (đpcm).
1.4.4 Cu trúc tập lồi
Định nghĩa 1.3. Cho X mt tập lồi đóng trong không gian R
n
. Tập con F của X
được gọi là mt diện của F nếu F lồi và bất kỳ một đoạn thng nào nhận một điểm
x ca F làm điểm trong tđoạn thẳng đó cũng nằm trong F.
- Din thứ nguyên 0 được gọi đỉnh hay điểm cực biên ca X. Nếu x là mt
điểm cực biên của X thì không đoạn thẳng nào trong của X nhận x làm điểm trong.
Tập các điểm cực biên ca X gọi là viền của X và kí hiu là V(X).
- Din có thứ nguyên 1 được gọi là cạnh của X.
Định 1.4 Gisử X là tp lồi đóng , giới nội và x
0
X . Khi đó x
0
t hợp lồi của
mt shữu hạn các điểm cực biên của X.
Chứng minh:
1.4.5 Tập lồi đa diện và đa diện lồi
Định nghĩa 1.4
+ Tập lồi đa diện (hay khúc lồi) là giao của số hữu hạn nửa không gian đóng.
+ Đa diện lồi là mt tập lồi đa diện giới nội.
Giả sử tập lồi đa diện D là giao của m nửa không gian đóng cho bởi các bất phương
trình:
i i
a ,x b
với
i 1,m
,
1 2
n
i i i in
a a , a ,...,a R
.
Khi đó m bất phương trình viết lại dưới dạng ma trận
Ax b
và tập
6
1
n
i
D x R | Ax b ;i ,m
, với: A =(a
ij
)
mxn
x =
1
2
n
x
x
...
x
R
n
b =
1
2
m
b
b
...
b
R
m
Thí d1.2 x
0
A
P
1
B C
P
2
d
1
d
3
d
2
D
Tập lồi đa diện Tập lồi đa diện Đa diện lồi 4 đỉnh,
0 đỉnh, 1 cạnh 1 đỉnh, 3 cạnh 6 cạnh và 4 diện 2 thứ nguyên
Định 1.5 Nếu x
0
là mt đỉnh của tập lồi đa diện D, thì D được chứa trong nón G
đỉnh x
0
và có các cạnh sinh bởi các cạnh của D kvới x
0
.
Chứng minh:
KIỂM TRA THUYẾT
- Kiến thức về giải tích lồi và ý nghĩa hình hc
- Biểu diễn toán học của một đa diện lồi.
7
ĐỀ CƯƠNG BÀI GIẢNG
Hc phn:
CÁC PP T
ỐI
ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 3 Tiết 7-9
GV giảng: 3, Bài tập: 0, Tự học :3
Giáo vn: Nguyễn Trọng Toàn
Vũ Anh M
Chương 2 i toán Qui hoạch tuyến tính
Các mục
2.1
Bài toán thực tế và ý nghĩa hình hc
2.2 Bài toán qui hoạch tuyến tính dạng chính tắc
2.3 Thuật toán đơn hình (Simplex)
Mc đích -
yêu cầu
-
Giới thiệu một vài hình thực tiễn dẫn đến qui hoạch tuyến tính
- Hc viên nắm được Thuật toán đơn hình và cơ sở toán học của
NỘI DUNG
I. LÝ THUYẾT
Chương 2. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH
2.1 BÀI TOÁN THC TẾ VÀ Ý NGHĨA HÌNH HC
2.1.1 i toán lập kế hoạch sn xuất tối ưu
Bài toán có dạng:
n
j j
j 1
F(x) c x
max (2.1)
n
ij j i
j 1
a x b ,i 1,m
(2.2)
j
x 0, j 1,n
(2.3)
Hay dng ma trận:
F x c,x max
0
Ax b, x
Bài toán (2.1)-(2.3) có hàm mc tiêucác ràng buộc đều là hàm bc nhất của các
biến x
j
nên đây là mt bài toán QHTT.
Vector x
R
n
thomãn các điều kiện (2.2)-(2.3) được gọi pơng án chấp nhn
được, i gọn phương án. Tập tất cả các phương án
0
n
D x R | Ax b, x
được
gọi là miền chấp nhận được. Dễ thấy D là một tập lồi đa diện. Nếu D gii nội thì D
một đa diện lồi. Các bài toán thực tế luôn luôn thgiả thiết D là giới ni và vy
người ta thêm vào mt ràng buc có dạng:
1 2
n
x x ... x L
với L là mt số dương đủ lớn.
2.1.2 Thí dthực tế và ý nghĩa hình học
Xét i toán lập kế hoạch sản xuất sau: F(x) = 4x
1
+ 5x
2
max
1 2
1 2
2
1 2
2x x 8
x 2x 7
x 3
x 0,x 0
8
2.2 BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮC
2.2.1 hình tn học
Phần này ta nghiên cứu bài toán QHTT có dạng sau:
1
( )
n
j j
j
F x c x
min (2.4)
1
1
n
ij j i
j
a x b , i ,m
(2.5)
0 1
j
x , j ,n
(2.6)
hay thể viết dưới dạng ma trận:
F x c,x min
0
Ax b, x
Không làm mất tính tổng quát ta thể thêm các gi thiết: b
0 , rank(A)=m < n. Khi
đó tập các pơng án chấp nhn được D={xR
n
| Ax =b, x 0} đa diện có thứ
nguyên n-m.
2.2.2 c định lý cơ bản
Định lý 2.1 Nếu hàm F(x) đạt cực tiểu tại một điểm duy nhất x
*
, thì x
*
phải là mt đỉnh
ca D.
Chứng minh
Định 2.2 Nếu hàm F(x) đạt cc tiểu tại một vector x
*
là đim trong ca [a,b] trong
D thì F(x) đạt cc tiu tại mọi điểm trên đoạn thẳng đó.
Chứng minh
Hquả. Nếu bài toán QHTT phương án tới ưu tập D đỉnh thì F(x) đạt gtrị
ti ưu tại ít nhất một đỉnh của D.
Định 2.2 và hệ quca nó rất quan trọng trong xây dựng thuật toán giải QHTT.
Do khẳng định nếu bài toán lời giải tối ưu thỉ phải có lời giải tối ưu đỉnh của đa
diện ràng buc D, mặt khác do D là tập lồi đa diện nên ch một số hữu hạn đnh
nên ta tập trung vào việc tìm phương án tối ưu của bài toán trên các đỉnh của đa diện.
2.3 THUẬT TOÁN ĐƠN HÌNH (Simplex Algorithm)
2.3.1 Đường lối chung
Thut toán đơn hình bao gồm các bước cơ bản như sau:
Bước 1. Tìm phương án cực biên xuất phát
Kết quả của bước nàymt trong hai khả năng:
- Phát hiện bài toán không có phương án.
- m được phương án cực biên x
0
D.
9
Bước 2. Kiểm tra tiêu chun ti ưu đối với phương án tìm được.
hai khả năng có thể xảy ra:
- Nếu x
0
thỏa mãn tiêu chuẩn tối ưu : Dừng thuật toán, đặt x
*
= x
0
và tính F
*
=F(x
*
).
- Nếu x
0
không tha mãn tiêu chuẩn tối ưu , thì chuyển sang bước 3.
Bước 3. Cải tiến phương án
- Tìm phương án cực biên x
1
tốt hơn phương án x
0
, tức là F(x
1
) < F(x
0
).
- Lặp lại bước 2.
Do D là tập lồi đa diện nên nó chcó một số hữu hn đỉnh. Vì vy thuật toán sẽ kết
thúc sau một số bước lặp, kết quả là hoặc tìm được phương án tối ưu x
*
hoc phát hiện
bài toán không có phương án tối ưu.
2.3.2 Cơ sthuật toán
Xét i toán QHTT dạng chính tắc:
F x c,x min
0
n
x D x R | Ax b, x
với giả thiết b 0 và rank(A)=m < n.
Bước 1. Tìm phương án cực biên xuất phát x
0
D
Do x
0
phương án cực biên nên phi thỏa mãn chặt n ràng buộc đc lập
tuyến tính. Do x
0
mt phương án nên x
0
đã tha m phương trình ràng buc Ax=b,
nên nó còn phải thỏa mãn chặt thêm n-m ng buc dạng x
j
= 0 na. Không làm mất
tính tổng quát, giả sử :
0 0 0
1 2
0
m m n
x x ... x
(2.7)
Khi đó hệ phương trình để xác định m thành phần còn lại của x
0
là:
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
m m
m m
m m mm m m
a x a x ... a x b
a x a x ... a x b
... ... ... ... ...
a x a x ... a x b
(2.8)
hiệu J ={1,2,3,m}: Tập chỉ số cơ sở của x
0
;
A
j
=
1j
2j
mj
a
a
j=1,n
...
a
: Ct thứ j của ma trận A, vector cơ sở;
B=(A
1
,A
2
,…,A
m
) =(A
j
)
jJ
: Ma trận cơ sở và x
J
= ( x
j
)
jJ
;
Các biến x
j
với j J: Gọi là các biến cơ sở ; x
j
với j J : Gọi là các biến phi
sở.
Khi đó hệ phương trình (2.8) có thể viết thành Bx
J
= b.
Do githiết rank(B) = rank(A) = m nên
0
J
x
nghiệm của hệ (5.8) :
0
J
x
=B
-1
b 0
x
0
= (
0 0 0 0
1 2 3 m
x ,x ,x ,...,x ,
0,0.0,..,0)
Nếu
0
j
x 0
vi
j J
thì x
0
gọi phương án cực biên không suy biến (không thoái
a); Ngược lại nếu jJ để cho
0
j
x 0
thì x
0
gi là phương án cực biên suy biến.
10
T các phân ch trên ta nhận xét như sau: Gi sử ta tìm được tập J
{1,2,3,…,n} sao cho ||J|| = m và B=(A
j
)
jJ
là ma trận không suy biến. Khi đó:
- Nếu B
-1
b 0 thì B gọi là một cơ sở chấp nhận được của bài toán QHTT, nó xác
định một phương án cực biên;
- Nếu điều kiện B
-1
b 0 kng thỏa mãn thì B không phải schấp nhận
được của bài toán, do đó ta phi chọn lại m cột đc lập tuyến tính khác của A…cứ như
vy cho đến khi ta tìm được cơ sở chấp nhận được.
Cách làm này mang nhiều tính may rủi, tốn công sức.
Bước 2. Kiểm tra tiêu chun ti ưu
Gisử ta đã tìm được phương án cc biên x
0
tương ng với cơ sB=(A
j
)
jJ
.
Khi đó
0 0
j k
x 0 j J và x 0 k J.
Do (A
j
)
jJ
mt họ m vector độc lập tuyến tính trong không gian R
m
, nên nó tạo
thành một cơ strong không gian R
m
. Ta có thphân tích các vector A
k
với
k J
theo
cơ sở này:
A
k
=
jk j
j J
v A
k J (2.9)
Đặt
k jk j k
j J
v c c
k=1,2,…: Các số kiểm tra (2.10)
Định lý 2.3 (Công thức số gia của hàm mc tiêu). Nếu x
0
phương án cực biên tương
ứng với s B=(A
j
)
jJ
, thì xD ta có:
x
j
=
0
j jk k
k J
x v x
jJ
(2.11)
F(x)
=
0
k k
k J
F(x ) x
(2.12)
Ý nghĩa củac công thức (2.11) và (2.12)
Đặt x
j
=
0
j j jk k
k J
x x v x
, jJ : S gia của biến x
j
F(x)= F(x) -
0
k k
k J
F(x ) x
: Số gia của hàm mc tiêu.
Từ đó: Các biến cơ svà s gia của hàm mc tiêu là hàm tuyến tính của c biến phi cơ
sở.
Định 2.4 (Tiêu chuẩn tối ưu). Nếu x
0
phương án cực biên tương ứng với sở
B=(A
j
)
jJ
, thì điều kiện để x
0
là phương án tối ưu là:
k
0 với
k J
(2.13)
Chứng minh
Nều x
0
tha mãn tiêu chuẩn (2.13) thì x
0
là phương án ti ưu ca bài toán QHTT .
Còn nếu không thỏa mãn tiêu chuẩn (2.13) thì
k J
k
>0, ta cần cải tiến phương
án. Tuy nhiên định sau đây giúp ta nhận biết bài toán không có phương án tối ưu.
11
Định 2.5 (Tiêu chuẩn nhn biết bài toán không phương án tối ưu). Giả sử x
0
phương án cc biên tương ứng với cơ sB=(A
j
)
jJ
. Nếu
k J
k
>0 và v
jk
0 với
j J
thì bài toán không có phương án tối ưu.
Chứng minh
Bước 3. Cải tiến phương án
Gisử x
0
phương án cc biên tương ứng với cơ s B=(A
j
)
jJ
. Nếu
k J
để
k
>0 thì x
0
không phải pơng án tối ưu. Ta cần tìm phương án cực biên x
1
tốt hơn
x
0
: F(x
1
) < F(x
0
). Gọi B
1
sở tương ứng với x
1
. Để đơn giản ta tìm x
1
mt đỉnh
kề của x
0
, nghĩa là hai cơ sở tương ứng chỉ khác nhau đúng 1 vector:
B
1
= B\ {A
p
}{A
q
} p J và q J (2.14)
Vấn đề còn lại là chọn A
p
và A
q
như thế nào.
a. Chọn vector A
q
đưa vào cơ sở mới B
1
Do tiêu chun tối ưu
k
0 vi
k J
n thchọn vector A
q
bất k ơng
ứng với
q
>0. Tuy nhiên đ ng tốc độ giảm giá trị hàm mục tiêu ta chọn :
q
=
k
k J
max
(2.15)
Khi đó A
q
tương ứng với phương của cạnh tốc đ giảm của hàm hàm mục tiêu
nhanh nht vì:
F(x
1
) =
0
k k
k J
F(x ) x
= F(x
0
) -
1
q q
x
Có hai trường hợp có thể xảy ra:
- Nếu v
jq
0 với j J thì theo định lý 5.5 i toán không có phương án tối ưu.
- Nếu j J v
jq
>0 thì chuyển sang việc chọn A
p
.
b. Chn vector A
p
đưa ra khỏi B
Chọn A
p
ơng ứng với
jq 0
0 0
p j
v
pq jq
x x
min
v v
(2.16)
Tính hợp của việc chọn A
p
như trên được giải thích như sau: Việc chọn A
p
phải
bảo đảm x
1
0. Theo công thức (2.11) ta có :
1 0 1 0 1
0
j j jk k j jq q
k J
x x v x x v x
jJ
1
= J\{p}{q} (2.17)
- Nếu v
jq
0 thì đương nhiên
1
j
x
0
- Nếu v
jq
>0 từ (5.17) suy ra
1
q
x
0
j
jq
x
v
, vì vy
1
q
x
=
0 0
0
min
jq
p j
v
pq jq
x x
v v
2.4 BẢNG ĐƠN HÌNH
2.4.1 Bảng đơn hình xut phát
Xét i toán QHTT dạng chính tắc:
F x c,x min
0
n
x D x R | Ax b, x
Githiết : b 0 , rank(A)=m < n.
Gisử đã tìm được cơ sở xuất phát B=(A
j
)
jJ
. Lần lượt tính:
0
J
x
=B
-1
b H = B
-1
A = (B
-1
A
1
, B
-1
A
2
,…, B
-1
A
n
)=(V
1
,V
2
,…,V
n
)
12
Nếu J = {1,2,3,…,m} bảng đơn hình xuất phát có dạng.
Lp bảng đơn hình có dng:
B c
J
x
J
c
1
c
2
... c
m
c
m
+1
... c
k
... c
q
... c
n
h
j
v
jq
>0
A
1
A
2
... A
m
A
m+1
... A
k
... A
q
... A
n
A
1
c
1
x
1
1 0 0 v
1,m+1
v
1,k
v
1,q
v
1,n
A
2
c
2
x
2
0 1 0 v
2,m+1
v
2,k
v
2,q
v
2,n
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
A
j
c
j
x
j
0 0 0 v
j,m+1
v
j,k
v
j,q
v
j,n
j
jq
x
v
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
A
p
c
p
x
p
0 0 0 v
p,m+1
v
p,k
v
p,q
v
p,n
p
pq
x
v
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
A
m
c
m
x
m
0 0 1 v
m,m+1
v
m,
k
v
m,q
v
m,n
k
0
0
... 0
m+1
...
k
...
q
...
n
Với các số kiểm tra:
k
=
jk j k
j J
v c c
nếu k J và
k
=0 nếu kJ.
Sử dụng bảng đơn hình
- Nếu kJ
k
0 thì dừng và x
0
là phương án tối ưu;
Ngược lại cần chọn A
q
đưa vào B
1
theo qui tắc:
q k
k J
max
- Nếu trên cột A
q
: v
jq
0 jJ thì dừng: bài toán không phương án tối
ưu;
ợc lại tính h
j
=
jq
j
v
x
0
và chọn A
p
đưa ra khỏi B theo qui tắc : h
p
=
0
0
min
jq
p
j
v
pq
x
h
v
Gọi A
P
hàng xoay ct A
q
ct xoay và v
pq
phần tử xoay. Khi đã xác
định được phần tử xoay, ta lập bảng đơn hình mới với vớ B
1
đã tìm được.
2.4.2 Qui tc chuyển bảng theo cơ sở mới
Việc tính toán các số liệu trong bảng đơn hình mới thể làm như đối với s
B. Tuy nhiên ch làm như vậy rất tốn công sức. Chỉ cần chú ý rằng sở mới chỉ khác
cơ sở cũ đúng một vector, ta có công thức đổi bảng như sau:
Định lý 2.6
0
0
1
1
0
nê'u j J \{ }
nê'u j=q
p
j jq
pq
j
p
pq
x
x v q
v
x
x
v
1
1
nê'u j J \{ }
nê'u j=q
pk
jk jq
pq
jk
pk
pq
v
v v q
v
v
v
v
1
1
k J
pk
k k q
pq
v
v
Chứng minh…(Giống như công thức Gauss để giải hệ phương trình tuyến tính.)
Thí d 2.1 Gii bài toán QHTT bằng phương pháp đơn hình vi cơ sở xuất phát
B=(A
1
,A
2
,A
3
)
13
F(x) = x
1
+ 3x
2
+ 2x
3
- 3x
4
+ 6x
5
min
1 3 4 5
1 2 4 5
2 3 4 5
3 9
7
2 4 6
0; 1,5
j
x x x x
x x x x
x x x x
x j
Giải. Ta có B=(A
1
,A
2
,A
3
) =
1 0 1
1 1 0
0 1 1
. Tính B
-1
=
1 1 1
1
1 1 1
2
1 1 1
1
1 1 1 9 5
1
1 1 1 7 2
2
1 1 1 6 4
J
x B b
và H=B
-1
A=
1 0 0 1 2
0 1 0 0 3
0 0 1 2 1
Lập bảng đơn hình:
B
C
J
x
J
1 3 2 -3 6
h
J
A
1
A
2
A
3
A
4
A
5
A
1
A
2
A
3
1
3
2
5
2
4
1
0
0
0
1
0
0
0
1
1
0
2
-2
3
1
5
2
k
0 0 0
8
3
A
1
A
2
A
4
1
3
-3
3
2
2
1
0
0
0
1
0
-1/2
0
1/2
0
0
1
-5/2
3
1/2
k
0 0
-4 0 -1
Bài toán có phương án tối ưu x
*
= ( 3,2,0,2,0) F
*
=F(x
*
) = 1x3 + 3x2 - 3x2 = 3
14
ĐỀ CƯƠNG BÀI GIẢNG
Hc phn:
CÁC PP T
ỐI
ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 4 Tiết 10-12
GV giảng: 2, Bài tập: 1, Tự học :3
Giáo vn: Nguyễn Trọng Toàn
Vũ Anh M
Chương 2 i toán Qui hoạch tuyến tính
Các mục
2.4 Bng đơn hình
2.5 Phương pháp đơn hình hai pha
Mc đích -
yêu cầu
-
Giới thiệu phương pháp đơn hình hai pha: Tìm phương án xuất phát
- Luyện tập giải QHTT dạng chính tắc
NỘI DUNG
I. LÝ THUYẾT
2.5 PHƯƠNG PHÁP ĐƠN HÌNH HAI PHA
2.5.1 Ý tưởng của pơng pháp
Xét i toán QHTT dạng chính tắc:
F x c,x min
0
n
x D x R | Ax b, x
Gisử bài tính hay không. Vì vậy quá toán này ta chưa biết trước một cơ sở xuất
phát nào, cũng chưa biết các ràng buc độc lập tuyến trình giải bài toán cần được
chia làm 2 pha:
- Pha I : Tìm phương án cực biên xut phát
- Pha II: Giải bài toán bằng phương pháp đơn hình t phương án xuất phát tìm
được.
Pha II đã được nghiên cứu trong mục trên. Ta cần quan tâm đến việc giải quyết pha I.
2.5.2 Pha I: Tìm phương án cực biên xuất phát
Giả sử b 0. Giải bài toán QHTT ph:
G( X)= x
n+1
+ x
n+2
+ x
n+3
+ … +x
n+m
min
X {(x,y)R
n+m
| Ax +y = b , x0, y 0 }
Với
1 2
T
n n n m
y x ,x ,...,x
gọi là các biến ph hay biến giả. ràng, do gi
thiết b 0, bài toán cơ sxuất pt B=(A
n+1
,A
n+2
,…,A
n+m
) dạng ma trận đơn v
hàm mục tiêu của bài toán phbchặn ới bởi 0 nen i toán luôn luôn lời giải
ti ưu. Do đó giải bài toán QHTT ph ta được lời giải X
*
=(x
*
,y
*
) với cơ sở tối ưu B*.
Định lý 2.7 Giả sử bài toán QHTT phta được lời giải tối ưu X
*
=(x
*
,y
*
). Khi đó:
i) Nếu y
*
0 thì bài toán gốc không có phương án: D =
ii) Nếu y
*
= 0 thì bài toán gc có phương án cc biên xuất phát là x
*
Các tình huống xảy ra khi y
*
= 0
a) Nếu B* chỉ chứa các cột của biến gc: thể chuyển sang pha II.
b) Nếu B*có chứa các cột của biến pha: Nghĩa là nó chứa các cột A
p
với p> n.
Khi đó B* không phải là cơ sở của bài toán gốc . 2 trường hợp:
- Nếu v
pj
= 0 với j n thì ràng buc p của bài toán thợp tuyến tính các ràng
buộc còn lại, nên có thể xóa A
p
trong B*;
15
- Nếu q≤ n, v
pq
≠0 thì dùng v
pq
làm phần tử xoay đthay A
p
bi A
q
Tiếp tục như vy đến khi ta được cơ sở của bài toán gốc thì chuyển sang pha 2.
Thí dụ 2.2 Giải bài toán QHTT
F(x) = x
1
-2x
2
+ x
3
- 5x
4
min
1 2 3
1 2 3 4
1 3 4
2 15
20
2 2 52
0; 1,4
j
x x x
x x x x
x x x
x j
Giải. Lập bài toán ph: G(x) = x
5
+ x
6
+ x
7
min
1 2 3 5
1 2 3 4 6
1 3 4 7
2 15
20
2 2 52
0; 1,7
j
x x x x
x x x x x
x x x x
x j
Giải bài toán phụ với cơ sở xuất phát B=(A
5
, A
6
, A
7
)
B
C
J
x
J
0 0 0 0 1 1 1 h
J
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
5
A
6
A
7
1
1
1
15
20
52
1
1
2
-2
-1
0
-1
-1
-1
0
1
2
1
0
0
0
1
0
0
0
1
15
20
26
k
4
-3 -3 3 0 0 0
A
1
A
6
A
7
0
1
1
15
5
22
1
0
0
-2
1
4
-1
0
1
0
1
2
1
-1
-2
0
1
0
0
0
1
5
22/4
k
0 5 1 3 -4 0 0
A
1
A
2
A
7
0
0
1
25
5
2
1
0
0
0
1
0
-1
0
1
2
1
-2
-1
-1
2
2
1
-4
0
0
1
k
0 0
1
2 1 -5 0
A
1
A
2
A
3
0
0
0
27
5
2
1
0
0
0
1
0
0
0
1
0
1
-2
1
-1
2
-2
1
-4
1
0
1
k
0 0 0 0 -1 -1 -1
- sở tối ưu của bài toán phụ chỉ chứa các cột của biến gốc Chuyển sang pha II.
B
C
J
x
J
1 -2 1 -5 h
J
A
1
A
2
A
3
A
4
A
1
A
2
A
3
1
-2
1
27
5
2
1
0
0
0
1
0
0
0
1
0
1
-2
k
0 0 0
1
A
1
A
4
A
3
1
-5
1
27
5
12
1
0
0
0
1
2
0
0
1
0
1
0
k
0 -1 0 0
16
Bài toán gc có phương án tối ưu: x
*
= ( 27, 0, 12, 5) và
F
*
=F(x
*
) = 1x27 -5x5 +1x12 = 14.
Chú ý khi giải bài toán QHTT bằng phương pháp đơn hình hai pha:
- Không cần lập bài toán ph mà chcần lập bảng đơn hình cho pha I ngay;
- Trong bảng đơn hình pha I không cần ghi các ct của các biến pha x
6
, x
7
, x
8
chúng không nhởng đến quá trình phân tích và giải bài toán.
Thí dụ 2.3 Gii bài toán QHTT
F(x) = 2x
1
-3x
2
+ x
3
- 2x
4
- x
5
min
1 2 3 4 5
1 2 3 4 5
1 2
3 4 5
5
2 2 2 8
2
3
0 ; 1,5
j
x x x x x
x x x x x
x x
x x x
x j
Giải.
Pha I. Giải bài toán ph
B
C
J
x
J
0 0 0 0 0 h
J
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
1
1
1
1
5
8
2
3
1
1
1
0
1
1
1
0
1
2
0
1
1
2
0
1
1
2
0
1
5
4
3
k
3 3
4
4 4
A
6
A
7
A
8
A
3
1
1
1
0
2
2
2
3
1
1
1
0
1
1
1
0
0
0
0
1
0
0
0
1
0
0
0
1
2
2
2
k
3
3 0 0 0
A
6
A
7
A
1
A
3
1
1
0
0
0
0
2
3
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
1
k
0 0 0 0 0
Cơ sở tối ưu của bài toán phcó chứa cột A
6
A
7
với x
6
=x
7
=0, nhưng v
6j
= v
7j
= 0
với j ≤ 5 nên A
6
và A
7
thể bỏ được trong cơ sở để chuyển sang pha II.
Pha II. Giải bài toán gốc.
B
C
J
x
J
2 -3 1 -2 -1 h
J
A
1
A
2
A
3
A
4
A
5
A
1
A
3
2
1
2
3
1
0
1
0
0
1
0
1
0
1
k
0
5
0 3 2
A
2
A
3
-3
1
2
3
1
0
1
0
0
1
0
1
0
1
17
k
-5 0 0
3
2
A
2
A
4
-3
-2
2
3
1
0
1
0
0
1
0
1
0
1
k
-5 0 -3 0 -1
Bài toán gc có phương án tối ưu: x
*
= ( 0, 2, 0, 3,0) F
*
=F(x
*
) = -3x2 -2x3 = -12.
II. BÀI TẬP
1. Giải bài toán QHTT với phương pháp đơn hình với cơ sở xuất phát B=(A
1
,A
2
,A
3
)
F(x) = x
1
+ 3x
2
+ 2x
3
- 3x
4
+ 4x
5
+ 4x
6
min
1 2 4 5 6
2 3 4 5 6
1 2 3 4 5 6
3 2 6
4 3
2 3 5 6 8
0, 1,6
j
x x x x x
x x x x x
x x x x x x
x j
Đs : x* = (0, 0, 0, 45/34, 25/34,47/34) và F* = 9/2
2. Giải bài toán QHTT dng chuẩn:
F(x) = x
1
+ x
2
- x
3
min
1 2 3
1 2 3
1 2 3
+ 2 48
3 - 3 2x 36
3 3 30
0, 1,3
j
x x x
x x
x x x
x j
Đs X
*
=(0 , 6, 27 ) F*= 1 x 6 - 1x 27 = -21
3. Giải bài toán QHTT bằng phương pháp đơn hình 2 pha:
F(x)= 2x
1
+ 8x
2
- 2x
3
+ 3x
4
-x
5
+ x
6
min
1 2 4 5 6
2 3 4 5 6
1 3 4 5 6
2 2 10
2 3 2 3 14
3 3 6 4
0, 1,6
j
x x x x x
x x x x x
x x x x x
x j
Đs x
*
=(25/2 , 0, 13/2, 0, 0, 5/2) F*= 2x25/2 +1 x 5/2 -2 x13/2 = 29/2
18
ĐỀ CƯƠNG BÀI GIẢNG
Hc phn:
CÁC PP T
ỐI
ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 5 Tiết 13-15
GV giảng: 1, Bài tập: 2, Tự học :3
Giáo vn: Nguyễn Trọng Toàn
Vũ Anh M
Chương 2 i toán Qui hoạch tuyến tính
Các mục 2.6 Phương pháp hàm phạt
Mc đích -
yêu cầu
-
Giới thiệu phương pháp hàm phạt
- Luyện tập giải QHTT dạng chính tắc
NỘI DUNG
I. LÝ THUYẾT
2.6 PHƯƠNG PHÁP HÀM PHẠT
2.6.1 Mô tả phương pháp
Xét i toán QHTT dạng chính tắc:
F x c,x min
0
n
x D x R | Ax b, x
Githiết b 0. Chưa biết hạng của ma trận A và tp D có phương án hay không.
Lập bài tn phạt (bài tn M)
F
M
(x,y) = <c,x) + Mx
n+1
+Mx
n+2
+…+Mx
n+m
min
D
M
0 0
Ax y b
x , y
Trong đó y=(x
n+1
,x
n+2
,…,x
n+m
)
T
R
n
M >>1.
Các biến x
n+1
,x
n+2
,…,x
n+m
gi là các biến phạt hay biến giả.
Định lý 2.8 Giả sử bài toán M có lời giải tối ưu X
*
=(x
*
,y
*
). Khi đó:
i) Nếu y
*
0 thì bài toán gốc không có phương án: D =;
ii) Nếu y
*
= 0 thì bài toán gốc có phương án tối ưu là x
*
.
Định 2.9 Nếu bài toán M không có lời giải tối ưu (tức là F
M
(x,y) -) thì
bài toán gốc cũng không có phương án tối ưu (tức là F-).
2.6.2 c thí dụ ứng dụng
Thí dụ 2.4 Giải bài toán QHTT bằng phương pháp hàm phạt:
F(x) = -3x
1
+ x
2
+ 3x
3
- 3x
4
min
1 2 3 4
1 3 4
1 2 4
2 2
2 6
9
0; 1,4
j
x x x x
x x x
x x x
x j
Giải. Lp bài toán M:
F(x) = -3x
1
+ x
2
+ 3x
3
- x
4
+Mx
5
+Mx
6
+Mx
7
min
1 2 3 4 5
1 3 4 6
1 2 4 7
2 2
2 + 6
9
0; 1,7
j
x x x x x
x x x x
x x x x
x j
ng là bài toán M có cơ sở chấp nhận được xuất phát là B=(A
5
,A
6
,A
7
).
19
- Lập bng đơn hình gii bài toán M.
B
C
J
x
J
-3 1 3 -1 M M M h
J
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
5
A
6
A
7
M
M
M
2
6
9
1
2
1
2
0
-1
-1
-1
0
1
-1
-1
1
0
0
0
1
0
0
0
1
2
3
9
k
M
3 -1 -3 1 0 0 0
4 1 -2 -1 0 0 0
A
1
A
6
A
7
-3
M
M
2
2
7
1
0
0
2
-4
-3
-1
1
1
1
-3
-2
1
-2
-1
0
1
0
0
0
1
2
7
k
M
0 -7 0 -2 -3 0 0
0 -7
2
-5 -4 0 0
A
1
A
3
A
7
-3
3
M
4
2
5
1
0
0
-2
-4
1
0
1
0
-2
-3
1
-1
-2
1
1
1
-1
0
0
1
k
M
0 -7 0 -2 -3 0 0
0 1 0 1 0 -2 0
A
1
A
3
A
4
-3
3
-1
14
17
5
1
0
0
0
-1
1
0
1
0
0
0
1
1
1
1
-1
-2
-1
2
3
1
k
M
0 -5 0 0 -1 -2 2
0 0 0 0 -1 -1 -1
Bài toán phương án tối ưu x
*
= (14,0,17,5) và F
*
= -3x14 +3x17-1x5 = 4.
Thí d2.5 Giải bài toán QHTT sau đây:
F(x) = x
1
- 4x
2
- 4x
3
- 2x
4
+3x
5
min
1 2 3 4 5
1 2 4 5
1 2 3 4 5
2 8
2 2 3
3 2 3 2 14
0, 1,5
j
x x x x x
x x x x
x x x x x
x j
Giải. Do chưa biết cơ sở chấp nhận được nào nên ta áp dụng phương pháp hàm phạt.
B
C
J
x
J
1 -4 -4 -2 3 h
J
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
M
M
M
8
3
14
1
2
1
-1
2
-3
1
0
2
2
1
3
1
1
2
4
3
14/3
k
M
-1 4 4 2 -3
4 -2 3
6
4
A
6
A
4
A
8
M
-2
M
2
3
5
-3
2
-5
-5
2
-9
1
0
2
0
1
0
-1
1
-1
2
5/2
20
k
M
-5 0 4 0 -5
-8 -14
3
0 -2
A
3
A
4
A
8
-4
-2
M
2
3
1
-3
2
1
-5
2
1
1
0
0
0
1
0
-1
1
1
3/2
1
k
M
7 20 0 0 -1
1
1
0 0 1
A
3
A
4
A
2
-4
-2
-4
7
1
1
2
0
1
0
0
1
1
0
0
0
1
0
4
-1
1
k
-13 0 0 0 -21
Vy bài toán gc có lời giải tối ưu: x
*
=(0,1,7,1,0) và F*= -4 x7- 2x1- 4x1 = -34.
II. BÀI TP
1. Giải bài toán QHTT bng phương pháp đơn hình hai pha:
F(x)= 6x
1
+6x
2
+ x
3
- 5x
4
+2x
5
-x
6
min
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
2 3 2
2 3 3 12
2 3 5 18
0, 1,6
j
x x x x x x
x x x x x x
x x x x x x
x j
Đs x*=(7/2, 0, 8, 0, 0, 3 ) F* = 6x7/2- 1x3 + 1x8 = 26
2. Giải bài toán QHTT bng phương pháp hàm phạt :
F(x) =2x
1
- 4x
2
- 4x
3
- 2x
4
+3x
5
min
1 2 3 4 5
1 2 4 5
1 2 3 4 5
2 2 8
4 2 3
2 3 2 3 2 14
0, 1,5
j
x x x x x
x x x x
x x x x x
x j
Đs X
*
=(0 , 1, 7, 1, 0, 0) F*= -4 x 7 - 2 x 1 -4 x1 = -34
3. Giải bài toán QHTT bằng phương pháp m phạt:
F(x) = 2x
1
-3x
2
+ x
3
+ 4x
4
- 4x
5
+ 5x
6
min
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
3 2 10
2 2 12
2 12
0, 1,6
j
x x x x x x
x x x x x x
x x x x x x
x j
Đs: x* = (0, 17/2, 27/10 , 2/5, 0, 0) và F* = -106/5
4. Giải bài toán QHTT : F(x) = x
1
+4 x
2
+ 2x
3
+ x
4
+ 3x
5
min
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
j
+2 10
- + 2 6
3 - 12
x 0 , j=1,5
x x x x x
x x x x x
x x x x x
Đs x
*
=(11,0 , 8, 0, 9) F*= 1 x 11 + 2 x 8 + 3 x 9 = 54
| 1/64

Preview text:

ĐỀ CƯƠNG BÀI GIẢNG
Học phần: CÁC PP TỐI ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 1 Tiết 1-3
Giáo viên: Nguyễn Trọng Toàn
GV giảng: 3, Bài tập: 0, Tự học :3 Vũ Anh Mỹ
Chương 1 Bài toán tối ưu hoá và các vấn đề cơ sở
1.1 Bài toán TUH và phân loại bài toán. Các mục
1.2 Một số mô hình thực tế
1.3 Không gian Euclide n-chiều
Mục đích - - Nắm được ý nghĩa ứng dụng trong thực tiễn của các bài toán TUH yêu cầu
- Nhắc lại và bổ xung một số kiến thức ĐSTT có liên quan NỘI DUNG I. LÝ THUYẾT
Chương 1. BÀI TOÁN TỐI ƯU HÓA VÀ CÁC VẤN ĐỀ CƠ SỞ

1.1 BÀI TOÁN TỐI ƯU HÓA VÀ PHÂN LOẠI BÀI TOÁN
1.1.1 Bài toán tối ưu hoá tổng quát
Min (hoặc Max) của hàm f(x) (1.1) g (x) ,  , b ; i=1,m với các điều kiện i i  (1.2) n x  X  R , trong đó:
- f(x) : Hàm mục tiêu với n biến.
- gi(x) , i 1, m : Các hàm ràng buộc. Mỗi bất đẳng thức gọi là một ràng buộc. - Tập D   n
xX R | g ( x ) ,,b ;i 1,m i i  Miền ràng buộc (1.3)
- x = (x1,x2,..., xn)  D : Phương án hay lời giải chấp nhận được.
- Phương án x* D làm cực đại (cực tiểu) hàm mục tiêu gọi là phương án hay lời
giải tối ưu. Cụ thể là: f(x*)  f(x), x D đối với bài toán max hay f(x*)  f(x),
x D đối với bài toán min. Khi đó f* = f(x*) gọi là giá trị tối ưu của bài toán.
1.1.2 Phân loại bài toán
Để tìm thuật giải hiệu quả cho các bài toán Tối ưu hoá cần phân loại các bài toán:
- Quy hạch tuyến tính (QHTT);
- Quy hoach phi tuyến (QHPT);
- Qui hoạch rời rạc ( QHRR);
- Qui hoạch đa mục tiêu (QHĐMT).
1.2 MỘT SỐ MÔ HÌNH THỰC TẾ
1.2.1 Bài toán lập kế hoạch sản xuất tối ưu
Một công ty muốn sản xuất 2 loại sản phẩm A và B bằng các loại nguyên liệu I,
II và III. Chi phí sản xuất cho một đơn vị sản phẩm được cho trong bảng sau: 1 Sản phẩm A B Nguyên liệu I 2 1 II 1 2 III 0 1  I 8 
Giả sử công ty có lương dự trữ nguyên liệu: II 7 
(Đơn vị nguyên liệu). Tiền III 3 
lãi cho 1 đơn vị sản phẩm loại A và B tương ứng là: 4 và 5 (đơn vị tiền tệ). Cần lập kế
hoạch sản xuất sao cho công ty thu được lãi nhiều nhất với điều kiện hạn chế về nguyên liệu như trên.
Kí hiệu x1 và x2 tương ứng là số lượng sản phẩm loại A và B cần sản xuất. Mô hình
toán học của bài toán trên có dạng một bài toán QHTT: f(x) = 4x1 + 5 x2  max 2x  x  8 1 2 x  2x  7 với điều kiện 1 2  x  3 2   x , x   0 1 2
Như vậy, bài toán lập kế hoạch sản xuất tổng quát có dạng: n f (x)  c x   max j j j 1  n  a x   b ,i 1,m ij j i j 1    x  0, j1,n j 
trong đó: + xj : Số sản phẩm loại j ( j 1,n ) cần sản xuất ;
+ cj : Tiền lãi của một đơn vị sản phẩm loại j ;
+ aij : Suất chi phí nguyên liệu loại i( i 1, m ) cho một đơn vị sản phẩm loại j ;
+ bi : lượng dự trữ nguyên liệu loại i.
1.2.2 Bài toán vận tải
- Có m kho hàng chứa cùng một loại hàng hoá được đánh số thứ tự i  1, m gọi
là điểm phát thứ i. Lượng hàng chứa tại điểm phát thứ i ai;
- Có n điểm tiêu thụ loại hàng hoá trên được đánh số thứ tự j  1, n gọi là điểm
thu thứ j; Điểm thu thứ j có nhu cầu tiêu thụ hàng là bj .
- Biết c là cước phí vận chuyển 1 đơn vị h ij
àng hoá từ điểm phát thứ i điển thu
thứ j ( i  1,m ; j  1, n ).
Hãy lập kế hoạch vận chuyển từ các điểm phát đến các điểm thu sao cho chi phí
vận chuyển là ít nhất với điều kiện: Các điểm phát phải phát hết hàng và các điểm thu
thì thoả mãn đủ nhu cầu. Đặt x là lượng h ij
àng cần vận chuyển từ điểm phát Ai đến điểm thu Bj ( i  1,m ;
j  1, n ). Khi đó mô hình toán học của bài toán vận tải (BTVT) có dạng: 2 m n F(X) = c x   min ij ij i 1  j 1  n  x  a i 1,m ij i  j 1  m  với điều kiện: x    b j1,n ij j i 1   x  0 i =1,m ; j =1,n ij  m n
Để bài toán có lời giải, thì nó phải thoả mãn điều kiện cân bằng thu phát: a   b  . i j i 1  j 1 
1.3 KHÔNG GIAN EUCLIDE n-CHIỀU TRÊN TRƯỜNG SỐ THỰC
1.3.1 Tích vô hướng của 2 vector

- Tích vô hướng trên không gian vector V là một hàm xác định trên VV thoả mãn: i) = x,y V
ii) = < x,z> + x,y,z V
iii) <x,y > = =  x,y V , R iv)  0 ; = 0  x= 0
- Nếu = 0 ta nói 2 vector x và y trực giao với nhau.
1.3.2 Siêu phẳng và nửa không gian
Cho vector aRn và số thực , siêu phẳng P trong không gian Rn là tập   n P
x R | a,x   
Nếu  = 0 thì P là một không gian con n-1 chiều. Mỗi siêu phẳng P chia không
gian Rn thành 2 nửa không gian: n
P x R | a,x   1 
 : Nửa không gian đóng n
P xR | a,x   2   : Nửa không gian mở
1.3.3 Đa tạp tuyến tính
Định nghĩa 1.2
Giả sử A =(aij)mxn , bRmrank(A) = m khi đó tập:   n A
x R | Ax   b
được gọi là 1 đa tạp tuyến tính có thứ nguyên là r = n-m.
Nếu b=0 thì D là một không gian con r chiều. Như vậy siêu phẳng là 1 đa tạp
tuyến tính có thứ nguyên n-1, đường thẳng là một đa tạp tuyến tính có thứ nguyên là 1,
một điểm là đa tạp tuyến tính có thứ nguyên 0 và không gian Rn là một đa tạp tuyến
tính có n thứ nguyên. Thứ nguyên của một tập hợp là thứ nguyên của đa tạp tuyến tính bé nhất chứa nó.
II. TÀI LIỆU THAM KHẢO
1. Nguyễn Đức Nghĩa, Tối ưu hoá, Nxb GD, 1999
2. Trần Vũ Thiệu-Bùi Thế Tâm, Tối ưu hoá , Nxb GTVT, 2000
3.
Nguyễn Địch, Lý thuyết tối ưu hoá, Nxb ĐHQG Hà nội, 2003 3
ĐỀ CƯƠNG BÀI GIẢNG
Học phần: CÁC PP TỐI ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 2 Tiết 4-6
Giáo viên: Nguyễn Trọng Toàn
GV giảng: 3, Bài tập: 0, Tự học :3 Vũ Anh Mỹ
Chương 1 Bài toán tối ưu hoá và các vấn đề cơ sở
1.3 Không gian Euclide n-chiều Các mục
1.4 Cơ sở giải tích lồi
Mục đích - - Nhắc lại và bổ xung một số kiến thức ĐSTT có liên quan yêu cầu
- Nắm được cơ sở và ý nghĩa hình học của các khái niệm toán học NỘI DUNG LÝ THUYẾT
1.4 CƠ SỞ GIẢI TÍCH LỒI
1.4.1 Đường thẳng đi qua 2 điểm
Cho 2 điểm a và bRn, đường thẳng đi qua a và b là tập :    n
x R | x  a  1 b,   R . Chú ý: + n           1
x R |x a 1 b, 1= [a, ): Nửa đường thẳng xuất phát từ a. + n           2
x R |x a 1 b, 0= [b, ): Nửa đường thẳng xuất phát từ b. + n        
   = [a,b]: Đoạn thẳng nối a với b. 3
x R |x a 1 b,0 1
1.4.2 Tập hợp lồi
Định nghĩa 1.1 Tập C được gọi là một tập lồi nếu x, y  C thì  0,
1 ,x  a  1 b C i a , x i b
Nghĩa là nếu x,y C thì C chứa cả đoạn thẳng nối x và y.
Thứ nguyên của tập lồi là thứ nguyên của đa tạp tuyến tính nhỏ nhất chứa nó.
Các tập lồi Các tập không lồi
Định lí 1.1 Giao của 2 tập lồi là tập lồi 4 Chứng minh:… 1.4.3 Tổ hợp lồi
Cho họ gồm m vector S = {a1 , a2 , a3,... am } Rn . Tổ hợp lồi của họ S là biểu thức: m m
x :=  x với   0 , i 1,m và  =1 i i i i i 1  i 1 
Tập các tổ hợp lồi của S được gọi là bao lồi (convex hull) của S, kí hiệu conv(S).
Từ định nghĩa trên ta thấy đoạn thẳng [a,b] là bao lồi của 2 điểm a và b và cũng là
tập lồi nhỏ nhất chứa a và b.
Định lý 1.2 Nếu X là tập lồi thì nó chứa tổ hợp lồi của một số điểm bất kỳ của nó.
Chứng minh: (Bằng phương pháp qui nạp theo m). Giả sử X là tập lồi và x1 ,x2 , x3,... m m x     m X. Đặt x = x với  0, i  1, m và
=1. Ta cần chứng minh xX. i i i i i 1  i 1  Thật vậy: - Với m =2 ta có x =  
1x1+ 2x2 với 1 ,2 0 và 1 + 2 =1. Suy ra x= 1 x1 + (1-  ]. Do đó x 1) x2 [x1, x2 X. m 1 
- Giả sử định lý đúng cho m-1 điểm, tức là  x với   0 , i 1,m 1 và i i i i 1  m 1   m 1  m 1  m m 1   =1. Đặt    =  ta có i  =1 và   x =  i  x i i  m =1- 0 khi đó x = i i  i i 1  i 1  i 1  i 1  i 1  +(1-)xm m 1  
Do giả thiết qui nạp ta có i  
 xi  X , hơn nữa và xm X nên x X (đpcm). i 1 
1.4.4 Cấu trúc tập lồi
Định nghĩa 1.3. Cho X là một tập lồi đóng trong không gian Rn. Tập con F của X
được gọi là một diện của F nếu F lồi và bất kỳ một đoạn thẳng nào nhận một điểm
x của F làm điểm trong thì đoạn thẳng đó cũng nằm trong F.
- Diện có thứ nguyên 0 được gọi là đỉnh hay điểm cực biên của X. Nếu x là một
điểm cực biên của X thì không có đoạn thẳng nào trong của X nhận x làm điểm trong.
Tập các điểm cực biên của X gọi là viền của X và kí hiệu là V(X).
- Diện có thứ nguyên 1 được gọi là cạnh của X.
Định lý 1.4 Giả sử X là tập lồi đóng , giới nội và x0X . Khi đó x0 là tổ hợp lồi của
một số hữu hạn các điểm cực biên của X. Chứng minh:
1.4.5 Tập lồi đa diện và đa diện lồi Định nghĩa 1.4
+ Tập lồi đa diện (hay khúc lồi) là giao của số hữu hạn nửa không gian đóng.
+ Đa diện lồi là một tập lồi đa diện giới nội.
Giả sử tập lồi đa diện D là giao của m nửa không gian đóng cho bởi các bất phương trình:     i a ,x i
b với i 1, m , aa1, n i i i a 2 ,..., in a R .
Khi đó m bất phương trình viết lại dưới dạng ma trận Ax b và tập 5  x   b  1  1 x   b  D   n
xR | Ax b ;i 1,m 2  2  i
, với: A =(aij)mxn x =  Rn và b =   Rm ...   ...       x  b n   m  Thí dụ 1.2 x0 A P1 B C P2 d1 d3 d2 D
Tập lồi đa diện Tập lồi đa diện Đa diện lồi 4 đỉnh,
0 đỉnh, 1 cạnh 1 đỉnh, 3 cạnh 6 cạnh và 4 diện 2 thứ nguyên
Định lý 1.5 Nếu x0 là một đỉnh của tập lồi đa diện D, thì D được chứa trong nón G có
đỉnh x0 và có các cạnh sinh bởi các cạnh của D kề với x0. Chứng minh:
KIỂM TRA LÝ THUYẾT
- Kiến thức về giải tích lồi và ý nghĩa hình học
- Biểu diễn toán học của một đa diện lồi. 6
ĐỀ CƯƠNG BÀI GIẢNG
Học phần: CÁC PP TỐI ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 3 Tiết 7-9
Giáo viên: Nguyễn Trọng Toàn
GV giảng: 3, Bài tập: 0, Tự học :3 Vũ Anh Mỹ
Chương 2 Bài toán Qui hoạch tuyến tính
2.1 Bài toán thực tế và ý nghĩa hình học Các mục
2.2 Bài toán qui hoạch tuyến tính dạng chính tắc
2.3 Thuật toán đơn hình (Simplex)
Mục đích - - Giới thiệu một vài mô hình thực tiễn dẫn đến qui hoạch tuyến tính yêu cầu
- Học viên nắm được Thuật toán đơn hình và cơ sở toán học của nó NỘI DUNG I. LÝ THUYẾT
Chương 2. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH
2.1 BÀI TOÁN THỰC TẾ VÀ Ý NGHĨA HÌNH HỌC

2.1.1 Bài toán lập kế hoạch sản xuất tối ưu n
Bài toán có dạng: F(x)  c x   max (2.1) j j j 1  n a x   b ,i 1,m (2.2) ij j i j 1  x  0, j  1,n (2.3) j
Hay dạng ma trận: F x c,x max
Ax b , x  0
Bài toán (2.1)-(2.3) có hàm mục tiêu và các ràng buộc đều là hàm bậc nhất của các
biến xj nên đây là một bài toán QHTT.
Vector xRn thoả mãn các điều kiện (2.2)-(2.3) được gọi là phương án chấp nhận
được, nói gọn là phương án. Tập tất cả các phương án   n D
x R | Ax b, x   0 được
gọi là miền chấp nhận được. Dễ thấy D là một tập lồi đa diện. Nếu D giới nội thì D là
một đa diện lồi. Các bài toán thực tế luôn luôn có thể giả thiết D là giới nội và vì vậy
người ta thêm vào một ràng buộc có dạng:
x x . .x L 1 2 n
với L là một số dương đủ lớn.
2.1.2 Thí dụ thực tế và ý nghĩa hình học
Xét bài toán lập kế hoạch sản xuất sau: F(x) = 4x1+ 5x2  max  2x  x  8 1 2  x  2x  7 1 2  x  3 2  x   0, x  0 1 2 7
2.2 BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮC
2.2.1 Mô hình toán học
Phần này ta nghiên cứu bài toán QHTT có dạng sau: n F(x)  c x   min (2.4) j j j 1  n a x
 b , i 1,m (2.5) ij j i j 1 
x  0, j  1,n (2.6) j
hay có thể viết dưới dạng ma trận: F x c,x min
Ax b , x  0
Không làm mất tính tổng quát ta có thể thêm các giả thiết: b 0 , rank(A)=m < n. Khi
đó tập các phương án chấp nhận được D={xRn | Ax =b, x  0} là đa diện có thứ nguyên n-m.
2.2.2 Các định lý cơ bản
Định lý 2.1 Nếu hàm F(x) đạt cực tiểu tại một điểm duy nhất x*, thì x* phải là một đỉnh của D. Chứng minh…
Định lý 2.2
Nếu hàm F(x) đạt cực tiểu tại một vector x* là điểm trong của [a,b] trong
D thì F(x) đạt cực tiểu tại mọi điểm trên đoạn thẳng đó. Chứng minh…
Hệ quả. Nếu bài toán QHTT có phương án tới ưu và tập D có đỉnh thì F(x) đạt giá trị
tối ưu tại ít nhất một đỉnh của D.
Định lý 2.2 và hệ quả của nó rất quan trọng trong xây dựng thuật toán giải QHTT.
Do khẳng định nếu bài toán có lời giải tối ưu thỉ phải có lời giải tối ưu là đỉnh của đa
diện ràng buộc D, mặt khác do D là tập lồi đa diện nên nó chỉ có một số hữu hạn đỉnh
nên ta tập trung vào việc tìm phương án tối ưu của bài toán trên các đỉnh của đa diện.
2.3 THUẬT TOÁN ĐƠN HÌNH (Simplex Algorithm)
2.3.1 Đường lối chung
Thuật toán đơn hình bao gồm các bước cơ bản như sau:
Bước 1. Tìm phương án cực biên xuất phát
Kết quả của bước này là một trong hai khả năng:
- Phát hiện bài toán không có phương án.
- Tìm được phương án cực biên x0D. 8
Bước 2. Kiểm tra tiêu chuẩn tối ưu đối với phương án tìm được.
Có hai khả năng có thể xảy ra:
- Nếu x0 thỏa mãn tiêu chuẩn tối ưu : Dừng thuật toán, đặt x* = x0 và tính F* =F(x*).
- Nếu x0 không thỏa mãn tiêu chuẩn tối ưu , thì chuyển sang bước 3.
Bước 3. Cải tiến phương án
- Tìm phương án cực biên x1 tốt hơn phương án x0 , tức là F(x1) < F(x0). - Lặp lại bước 2.
Do D là tập lồi đa diện nên nó chỉ có một số hữu hạn đỉnh. Vì vậy thuật toán sẽ kết
thúc sau một số bước lặp, kết quả là hoặc tìm được phương án tối ưu x* hoặc phát hiện
bài toán không có phương án tối ưu.
2.3.2 Cơ sở thuật toán
Xét bài toán QHTT dạng chính tắc: F x c,x min    n x D
xR | Ax b, x   0
với giả thiết b 0 và rank(A)=m < n.
Bước 1. Tìm phương án cực biên xuất phát x0D
Do x0 là phương án cực biên nên nó phải thỏa mãn chặt n ràng buộc độc lập
tuyến tính. Do x0 là một phương án nên x0 đã thỏa m phương trình ràng buộc Ax=b,
nên nó còn phải thỏa mãn chặt thêm n-m ràng buộc dạng xj = 0 nữa. Không làm mất
tính tổng quát, giả sử : 0 0 0 x
x ...x  0 (2.7) m 1  m2 n
Khi đó hệ phương trình để xác định m thành phần còn lại của x0 là:     1 a 1 1 x 1 a 2x2 ... 1 a m m x 1 ba x  a x... a xb 21 1 22 2 2m m 2  (2.8) ... ...... ......  a     1 m 1 x m a 2x2 ... m a mxm m b
Ký hiệu J ={1,2,3,…m}: Tập chỉ số cơ sở của x0; a1j    a   A 2 j j = j=1,n  
: Cột thứ j của ma trận A, vector cơ sở; ...   a  mj  
B=(A1,A2,…,Am) =(Aj)jJ: Ma trận cơ sở và xJ = ( xj) jJ ;
Các biến xj với j J: Gọi là các biến cơ sở ; xj với j J : Gọi là các biến phi cơ sở.
Khi đó hệ phương trình (2.8) có thể viết thành Bx J= b.
Do giả thiết rank(B) = rank(A) = m nên 0
x là nghiệm của hệ (5.8) : 0 J x =B-1b 0 và J x0 = ( 0 0 0 0 1
x , x2, x3,..., xm, 0,0.0,..,0) Nếu 0
x  với   thì x0 gọi là phương án cực biên không suy biến (không thoái j 0 j J
hóa); Ngược lại nếu jJ để cho 0 x  j
0 thì x0 gọi là phương án cực biên suy biến. 9
Từ các phân tích trên ta có nhận xét như sau: Giả sử ta tìm được tập J 
{1,2,3,…,n} sao cho ||J|| = m và B=(Aj)jJ là ma trận không suy biến. Khi đó:
- Nếu B-1b 0 thì B gọi là một cơ sở chấp nhận được của bài toán QHTT, nó xác
định một phương án cực biên;
- Nếu điều kiện B-1b  0 không thỏa mãn thì B không phải là cơ sở chấp nhận
được của bài toán, do đó ta phải chọn lại m cột độc lập tuyến tính khác của A…cứ như
vậy cho đến khi ta tìm được cơ sở chấp nhận được.
Cách làm này mang nhiều tính may rủi, tốn công sức.
Bước 2. Kiểm tra tiêu chuẩn tối ưu
Giả sử ta đã tìm được phương án cực biên x0 tương ứng với cơ sở B=(Aj)jJ . Khi đó 0 0 x     j 0 j J và xk 0 k J.
Do (Aj)jJ là một họ m vector độc lập tuyến tính trong không gian Rm, nên nó tạo
thành một cơ sở trong không gian Rm. Ta có thể phân tích các vector Ak với k  J theo cơ sở này: Ak = v  k J (2.9) jk A j j J  Đặt   
 k=1,2,…: Các số kiểm tra (2.10) k v jkcj ck j J 
Định lý 2.3 (Công thức số gia của hàm mục tiêu). Nếu x0 là phương án cực biên tương
ứng với cơ sở B=(Aj)jJ , thì xD ta có: xj = 0 x   jJ (2.11) j v jkxk k J  F(x) = 0 F(x )    (2.12) k x k k J 
Ý nghĩa của các công thức (2.11) và (2.12) Đặt xj = 0 x   
, jJ : Số gia của biến x j x j v jkxk j k J  F(x)= F(x) - 0 F(x )   
: Số gia của hàm mục tiêu. k xk k J 
Từ đó: Các biến cơ sở và số gia của hàm mục tiêu là hàm tuyến tính của các biến phi cơ sở.
Định lý 2.4 (Tiêu chuẩn tối ưu). Nếu x0 là phương án cực biên tương ứng với cơ sở
B=(Aj)jJ , thì điều kiện để x0 là phương án tối ưu là:
k  0 với  k  J (2.13) Chứng minh…
Nều x0 thỏa mãn tiêu chuẩn (2.13) thì x0 là phương án tối ưu của bài toán QHTT .
Còn nếu nó không thỏa mãn tiêu chuẩn (2.13) thì  k  J k >0, ta cần cải tiến phương
án. Tuy nhiên định lý sau đây giúp ta nhận biết bài toán không có phương án tối ưu. 10
Định lý 2.5 (Tiêu chuẩn nhận biết bài toán không có phương án tối ưu). Giả sử x0 là
phương án cực biên tương ứng với cơ sở B=(A   j)jJ. Nếu  k  J k >0 và vjk 0 với
j J thì bài toán không có phương án tối ưu. Chứng minh…
Bước 3. Cải tiến phương án
Giả sử x0 là phương án cực biên tương ứng với cơ sở B=(Aj)jJ . Nếu  k  J để
k >0 thì x0 không phải là phương án tối ưu. Ta cần tìm phương án cực biên x1 tốt hơn
x0: F(x1) < F(x0). Gọi B là cơ sở tương ứng với x1. Để đơn giản ta t 1 ìm x1 là một đỉnh
kề của x0 , nghĩa là hai cơ sở tương ứng chỉ khác nhau đúng 1 vector:
B1 = B\ {Ap}{Aq} p J và q J (2.14)
Vấn đề còn lại là chọn Ap và Aq như thế nào.
a. Chọn vector Aq đưa vào cơ sở mới B1
Do tiêu chuẩn tối ưu là k  0 với  k  J nên có thể chọn vector Aq bất kỳ tương
ứng với  >0. Tuy nhiên để tăng tốc độ giảm giá trị h q àm mục tiêu ta chọn : q = max  k (2.15) k J 
Khi đó A tương ứng với phương của cạnh có tốc độ giảm của h q àm hàm mục tiêu nhanh nhất vì: F(x1) = 0 F(x )    = F(x0) - 1  k x k q xq k J 
Có hai trường hợp có thể xảy ra:
- Nếu vjq 0 với  j J thì theo định lý 5.5 bài toán không có phương án tối ưu.
- Nếu  j J vjq >0 thì chuyển sang việc chọn Ap .
b. Chọn vector Ap đưa ra khỏi B 0 0 x x Chọn A p j p tương ứng với  min (2.16) v v pq jq 0 v  jq
Tính hợp lý của việc chọn Ap như trên được giải thích như sau: Việc chọn Ap phải
bảo đảm x10. Theo công thức (2.11) ta có : 1 0 1 0 1 x x v x
x v x  0 jJ j j jk k j jq q 1= J\{p}{q} (2.17) k J
- Nếu vjq  0 thì đương nhiên 1 x  j 0 0 x 0 0 x x j p j - Nếu v  jq >0 từ (5.17) suy ra 1 x min q  , vì vậy 1 xq = v v jq 0 v v jq pq jq 2.4 BẢNG ĐƠN HÌNH
2.4.1 Bảng đơn hình xuất phát
Xét bài toán QHTT dạng chính tắc: F x c,x min    n x D
x R | Ax b, x   0
Giả thiết : b 0 , rank(A)=m < n.
Giả sử đã tìm được cơ sở xuất phát B=(Aj)jJ . Lần lượt tính: 0
xJ =B-1b H = B-1A = (B-1A1, B-1A2,…, B-1An)=(V1,V2,…,Vn) 11
Nếu J = {1,2,3,…,m} bảng đơn hình xuất phát có dạng.
Lập bảng đơn hình có dạng: c1 c2 ... cm cm+1 ... ck ... cq ... cn hj B cJ
xJ A1 A2 ... Am Am+1 ... Ak ... Aq ... An vjq>0 A1 c1 x1 1 0 0 v1,m+1 v1,k v1,q v1,n A2 c2 x2 0 1 0 v2,m+1 v2,k v2,q v2,n ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... x Aj cj xj 0 0 0 vj,m+1 vj,k vj,q vj,n j v jq ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... x Ap cp xp 0 0 0 vp,m+1 vp,k vp,q vp,n p vpq ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Am cm xm 0 0 1 vm,m+1 vm,k vm,q vm,n ...  ...  ... k 0 0 ... 0 m+1 k q n
Với các số kiểm tra: k= v c
c nếu k J và  jk j k k =0 nếu kJ. jJ
Sử dụng bảng đơn hình - Nếu  kJ  
k 0 thì dừng và x0 là phương án tối ưu;
Ngược lại cần chọn Aq đưa vào B1 theo qui tắc:    q max k kJ - Nếu trên cột A  q : vjq
0  jJ thì dừng: bài toán không có phương án tối ưu; x0 0 gược lại tính h j xp j =
và chọn Ap đưa ra khỏi B theo qui tắc : hp =  min h v j v 0 vjq jq pq
Gọi AP là hàng xoay và cột Aq là cột xoay và vpq là phần tử xoay. Khi đã xác
định được phần tử xoay, ta lập bảng đơn hình mới với vớ B1 đã tìm được.
2.4.2 Qui tắc chuyển bảng theo cơ sở mới
Việc tính toán các số liệu trong bảng đơn hình mới có thể làm như đối với cơ sở
B. Tuy nhiên cách làm như vậy rất tốn công sức. Chỉ cần chú ý rằng cơ sở mới chỉ khác
cơ sở cũ đúng một vector, ta có công thức đổi bảng như sau: Định lý 2.6 0  xv 0 p x   v nê'u j J \{ } q pk v   v nê'u j J \{ } q j jq 1 vjk jq 1 v  1 pq x   1 pq vj  0 x jk v ppk nê'u j=q   nê'u j=q vv pqpqv 1 pk      k J k k q 1 vpq
Chứng minh…(Giống như công thức Gauss để giải hệ phương trình tuyến tính.)
Thí dụ 2.1 Giải bài toán QHTT bằng phương pháp đơn hình với cơ sở xuất phát B=(A1,A2,A3) 12
F(x) = x1 + 3x2 + 2x3 - 3x4 + 6x5 min xx 3  xx  9 1 3 4 5 x xxx  7 1 2 4 5   xx 2
x 4x  6 2 3 4 5  
x  0; j  1,5  j 1 0 1  1 1 1   1 Giải. Ta có B=(A      1,A2,A3) = 1 1 0  . Tính B-1 = 1 1 1   0 1 1   2 1  1 1   1 1 19 5 1 0 0 1 2 1 1
x Bb   1 1
1   7    2 và H=B-1A= 0 1 0 0 3  J 2        1 1   1 6 4     0 0 1 2 1  
Lập bảng đơn hình: 1 3 2 -3 6 B CJ xJ hJ A1 A2 A3 A4 A5 A1 1 5 1 0 0 1 -2 5 A2 3 2 0 1 0 0 3 A3 2 4 0 0 1 2 1 2 k 0 0 0 8 3 A1 1 3 1 0 -1/2 0 -5/2 A2 3 2 0 1 0 0 3 A4 -3 2 0 0 1/2 1 1/2 k 0 0 -4 0 -1
Bài toán có phương án tối ưu x* = ( 3,2,0,2,0) F* =F(x*) = 1x3 + 3x2 - 3x2 = 3 13
ĐỀ CƯƠNG BÀI GIẢNG
Học phần: CÁC PP TỐI ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 4 Tiết 10-12
Giáo viên: Nguyễn Trọng Toàn
GV giảng: 2, Bài tập: 1, Tự học :3 Vũ Anh Mỹ
Chương 2 Bài toán Qui hoạch tuyến tính 2.4 Bảng đơn hình Các mục
2.5 Phương pháp đơn hình hai pha
Mục đích - - Giới thiệu phương pháp đơn hình hai pha: Tìm phương án xuất phát yêu cầu
- Luyện tập giải QHTT dạng chính tắc NỘI DUNG I. LÝ THUYẾT
2.5 PHƯƠNG PHÁP ĐƠN HÌNH HAI PHA
2.5.1 Ý tưởng của phương pháp
Xét bài toán QHTT dạng chính tắc: F x c,x min    n x D
x R | Ax b, x   0
Giả sử bài tính hay không. Vì vậy quá toán này ta chưa biết trước một cơ sở xuất
phát nào, cũng chưa biết các ràng buộc có độc lập tuyến trình giải bài toán cần được chia làm 2 pha:
- Pha I : Tìm phương án cực biên xuất phát
- Pha II: Giải bài toán bằng phương pháp đơn hình từ phương án xuất phát tìm được.
Pha II đã được nghiên cứu trong mục trên. Ta cần quan tâm đến việc giải quyết pha I.
2.5.2 Pha I: Tìm phương án cực biên xuất phát
Giả sử b  0. Giải bài toán QHTT phụ:
G( X)= xn+1 + xn+2 + xn+3 + … +xn+m  min
X  {(x,y)Rn+m | Ax +y = b , x0, y 0 } T
Với y  xn 1,xn 2 ,..., n x  
m  gọi là các biến phụ hay biến giả. Rõ ràng, do giả
thiết b  0, bài toán có cơ sở xuất phát B=(An+1,An+2,…,An+m) có dạng ma trận đơn vị
và hàm mục tiêu của bài toán phụ bị chặn dưới bởi 0 nen bài toán luôn luôn có lời giải
tối ưu. Do đó giải bài toán QHTT phụ ta được lời giải X* =(x*,y*) với cơ sở tối ưu B*.
Định lý 2.7 Giả sử bài toán QHTT phụ ta được lời giải tối ưu X* =(x*,y*). Khi đó:
i) Nếu y*  0 thì bài toán gốc không có phương án: D =
ii) Nếu y* = 0 thì bài toán gốc có phương án cực biên xuất phát là x*
 Các tình huống xảy ra khi y* = 0
a) Nếu B* chỉ chứa các cột của biến gốc: Có thể chuyển sang pha II.
b) Nếu B*có chứa các cột của biến pha: Nghĩa là nó có chứa các cột Ap với p> n.
Khi đó B* không phải là cơ sở của bài toán gốc .Có 2 trường hợp:
- Nếu vpj = 0 với  j ≤ n thì ràng buộc p của bài toán là tổ hợp tuyến tính các ràng
buộc còn lại, nên có thể xóa Ap trong B*; 14 - Nếu q≤ n, v ≠0 th pq
ì dùng vpq làm phần tử xoay để thay Ap bởi Aq…
Tiếp tục như vậy đến khi ta được cơ sở của bài toán gốc thì chuyển sang pha 2.
Thí dụ 2.2 Giải bài toán QHTT
F(x) = x1 -2x2 + x3 - 5x4 min x 2x x  15 1 2 3  x  xxx  20 1 2 3 4  2x
x 2x  52 1 3 4  x   0; j 1,4 j
Giải. Lập bài toán phụ: G(x) = x5 + x6 + x7 min x 2  x xx 15 1 2 3 5 x  xx xx  20 1 2 3 4 6  2x
x 2x x  52 1 3 4 7  x   0; j 1,7 j
Giải bài toán phụ với cơ sở xuất phát B=(A5, A6, A7) 0 0 0 0 1 1 1 h B J CJ xJ A1 A2 A3 A4 A5 A6 A7 A5 1 15 1 -2 -1 0 1 0 0 15 A6 1 20 1 -1 -1 1 0 1 0 20 A7 1 52 2 0 -1 2 0 0 1 26 k 4 -3 -3 3 0 0 0 A1 0 15 1 -2 -1 0 1 0 0 A6 1 5 0 1 0 1 -1 1 0 5 A7 1 22 0 4 1 2 -2 0 1 22/4  0 5 1 3 -4 0 0 k A1 0 25 1 0 -1 2 -1 2 0 A2 0 5 0 1 0 1 -1 1 0 A7 1 2 0 0 1 -2 2 -4 1  0 0 k 1 2 1 -5 0 A1 0 27 1 0 0 0 1 -2 1 A2 0 5 0 1 0 1 -1 1 0 A3 0 2 0 0 1 -2 2 -4 1  0 0 0 0 -1 -1 -1 k
- Cơ sở tối ưu của bài toán phụ chỉ chứa các cột của biến gốc Chuyển sang pha II. 1 -2 1 -5 h B J CJ xJ A1 A2 A3 A4 A1 1 27 1 0 0 0 A2 -2 5 0 1 0 1 A3 1 2 0 0 1 -2  0 0 0 k 1 A1 1 27 1 0 0 0 A4 -5 5 0 1 0 1 A3 1 12 0 2 1 0  0 -1 0 0 k 15
Bài toán gốc có phương án tối ưu: x* = ( 27, 0, 12, 5) và
F* =F(x*) = 1x27 -5x5 +1x12 = 14.
Chú ý khi giải bài toán QHTT bằng phương pháp đơn hình hai pha:
- Không cần lập bài toán phụ mà chỉ cần lập bảng đơn hình cho pha I ngay;
- Trong bảng đơn hình ở pha I không cần ghi các cột của các biến pha x6, x7, x8
chúng không ảnh hưởng đến quá trình phân tích và giải bài toán.
Thí dụ 2.3 Giải bài toán QHTT F(x) = 2x 1 -3x2 + x3 - 2x4 - x5 min
x x xxx  5 1 2 3 4 5
x x 2x 2x 2x  8 1 2 3 4 5 x x  2 1 2   xxx  3 3 4 5 
x  0 ; j  1, 5 jGiải.
Pha I. Giải bài toán phụ 0 0 0 0 0 h B J CJ xJ A1 A2 A3 A4 A5 A6 1 5 1 1 1 1 1 5 A7 1 8 1 1 2 2 2 4 A8 1 2 1 1 0 0 0 A9 1 3 0 0 1 1 1 3  3 3 k 4 4 4 A6 1 2 1 1 0 0 0 2 A7 1 2 1 1 0 0 0 2 A8 1 2 1 1 0 0 0 2 A3 0 3 0 0 1 1 1 k 3 3 0 0 0 A6 1 0 0 0 0 0 0 A7 1 0 0 0 0 0 0 A1 0 2 1 1 0 0 0 A3 0 3 0 0 1 1 1  0 0 0 0 0 k
Cơ sở tối ưu của bài toán phụ có chứa cột A =0, nhưng v 6 và A7 với x6=x7 6j = v7j = 0
với  j ≤ 5 nên A6 và A7 có thể bỏ được trong cơ sở để chuyển sang pha II.
Pha II. Giải bài toán gốc. 2 -3 1 -2 -1 h B J CJ xJ A1 A2 A3 A4 A5 A1 2 2 1 1 0 0 0 A3 1 3 0 0 1 1 1  0 k 5 0 3 2 A2 -3 2 1 1 0 0 0 A3 1 3 0 0 1 1 1 16  -5 0 0 k 3 2 A2 -3 2 1 1 0 0 0 A4 -2 3 0 0 1 1 1  -5 0 -3 0 -1 k
Bài toán gốc có phương án tối ưu: x* = ( 0, 2, 0, 3,0) F* =F(x*) = -3x2 -2x3 = -12. II. BÀI TẬP
1. Giải bài toán QHTT với phương pháp đơn hình với cơ sở xuất phát B=(A1,A2,A3)
F(x) = x1 + 3x2 + 2x3 - 3x4 + 4x5 + 4x6 min x x 3xx 2  x  6 1 2 4 5 6  xxx 4xx  3 2 3 4 5 6   xx 2
x 3x 5x 6  x  8 1 2 3 4 5 6  
x  0, j  1, 6 j
Đs : x* = (0, 0, 0, 45/34, 25/34,47/34) và F* = 9/2
2. Giải bài toán QHTT dạng chuẩn:
F(x) = x1 + x2 - x3 min  xx + 2x  48 1 2 3    3x - 3x 2x 36 1 2 3   3 x 3xx  30 1 2 3  
x  0, j  1, 3 j
Đs X*=(0 , 6, 27 ) F*= 1 x 6 - 1x 27 = -21
3. Giải bài toán QHTT bằng phương pháp đơn hình 2 pha: F(x)= 2x  1 + 8x2 - 2x3 + 3x4 -x5 + x6 min x 2x 2xxx  10 1 2 4 5 6       2 x x 3x 2 x 3x 14 2 3 4 5 6  xx 3x 3x 6x  4 1 3 4 5 6  x   0, j  1,6 j
Đs x*=(25/2 , 0, 13/2, 0, 0, 5/2) F*= 2x25/2 +1 x 5/2 -2 x13/2 = 29/2 17
ĐỀ CƯƠNG BÀI GIẢNG
Học phần: CÁC PP TỐI ƯU
Đơn vị: Bộ môn Toán, Khoa CNTT
Thời gian: Tuần 5 Tiết 13-15
Giáo viên: Nguyễn Trọng Toàn
GV giảng: 1, Bài tập: 2, Tự học :3 Vũ Anh Mỹ
Chương 2 Bài toán Qui hoạch tuyến tính Các mục
2.6 Phương pháp hàm phạt
Mục đích - - Giới thiệu phương pháp hàm phạt yêu cầu
- Luyện tập giải QHTT dạng chính tắc NỘI DUNG I. LÝ THUYẾT
2.6 PHƯƠNG PHÁP HÀM PHẠT 2.6.1 Mô tả phương pháp

Xét bài toán QHTT dạng chính tắc: F x c,x min    n x D
xR | Ax b, x   0
Giả thiết b  0. Chưa biết hạng của ma trận A và tập D có phương án hay không.
Lập bài toán phạt (bài toán M)
FM (x,y) =  Ax y b DM  x   0, y  0
Trong đó y=(xn+1,xn+2,…,xn+m)T  Rn và M >>1.
Các biến xn+1,xn+2,…,xn+m gọi là các biến phạt hay biến giả.
Định lý 2.8 Giả sử bài toán M có lời giải tối ưu X* =(x*,y*). Khi đó:
i) Nếu y*  0 thì bài toán gốc không có phương án: D =;
ii) Nếu y* = 0 thì bài toán gốc có phương án tối ưu là x*.
Định lý 2.9 Nếu bài toán M không có lời giải tối ưu (tức là FM(x,y) -) thì
bài toán gốc cũng không có phương án tối ưu (tức là F-).
2.6.2 Các thí dụ ứng dụng
Thí dụ 2.4
Giải bài toán QHTT bằng phương pháp hàm phạt:
F(x) = -3x1 + x2 + 3x3 - 3x4 min  x 2
x x x  2 1 2 3 4 2x  x x  6 1 3 4  xxx  9 1 2 4  x   0; j 1,4 j
Giải. Lập bài toán M: F(x) = -3x
1 + x2 + 3x3 - x4 +Mx5 +Mx6 +Mx7 min x
2x x x x  2 1 2 3 4 5 2x
x x +x  6 1 3 4 6  xx
x x  9 1 2 4 7  x   0; j 1,7 j
Rõ ràng là bài toán M có cơ sở chấp nhận được xuất phát là B=(A5,A6,A7). 18
- Lập bảng đơn hình giải bài toán M. -3 1 3 -1 M M M h B J CJ xJ A1 A2 A3 A4 A5 A6 A7 A5 M 2 1 2 -1 1 1 0 0 2 A6 M 6 2 0 -1 -1 0 1 0 3 A7 M 9 1 -1 0 -1 0 0 1 9  3 -1 -3 1 0 0 0 k 4 1 -2 -1 0 0 0 M A1 -3 2 1 2 -1 1 1 0 0 A6 M 2 0 -4 1 -3 -2 1 0 2 A7 M 7 0 -3 1 -2 -1 0 1 7  0 -7 0 -2 -3 0 0 k M 0 -7 2 -5 -4 0 0 A1 -3 4 1 -2 0 -2 -1 1 0 A3 3 2 0 -4 1 -3 -2 1 0 A7 M 5 0 1 0 1 1 -1 1  0 -7 0 -2 -3 0 0 k M 0 1 0 1 0 -2 0 A1 -3 14 1 0 0 0 1 -1 2 A3 3 17 0 -1 1 0 1 -2 3 A4 -1 5 0 1 0 1 1 -1 1  0 -5 0 0 -1 -2 2 k M 0 0 0 0 -1 -1 -1
Bài toán có phương án tối ưu x* = (14,0,17,5) và F* = -3x14 +3x17-1x5 = 4.
Thí dụ 2.5 Giải bài toán QHTT sau đây:
F(x) = x1 - 4x2 - 4x3 - 2x4 +3x5 min       1 x 2 x 3 x 2x4 5 x 8 2     1 x 2x2 x4 5 x 3        1 x 3 2 x 2 3 x 3 4 x 2 5 x 14  
x  0, j  1,5 j
Giải. Do chưa biết cơ sở chấp nhận được nào nên ta áp dụng phương pháp hàm phạt. B CJ xJ 1 -4 -4 -2 3 hJ A1 A2 A3 A4 A5 A6 M 8 1 -1 1 2 1 4 A7 M 3 2 2 0 1 1 3 A8 M 14 1 -3 2 3 2 14/3  -1 4 4 2 -3 k M 4 -2 3 6 4 A6 M 2 -3 -5 1 0 -1 2 A4 -2 3 2 2 0 1 1 A8 M 5 -5 -9 2 0 -1 5/2 19  -5 0 4 0 -5 k M -8 -14 3 0 -2 A3 -4 2 -3 -5 1 0 -1 A4 -2 3 2 2 0 1 1 3/2 A8 M 1 1 1 0 0 1 1  7 20 0 0 -1 k M 1 1 0 0 1 A3 -4 7 2 0 1 0 4 A4 -2 1 0 0 0 1 -1 A2 -4 1 1 1 0 0 1 k -13 0 0 0 -21
Vậy bài toán gốc có lời giải tối ưu: x*=(0,1,7,1,0) và F*= -4 x7- 2x1- 4x1 = -34. II. BÀI TẬP
1. Giải bài toán QHTT bằng phương pháp đơn hình hai pha: F(x)= 6x  1 +6x2 + x3 - 5x4 +2x5 -x6 min 2xxxx 3x x  2 1 2 3 4 5 6
2x 3x x 3x x x 12 1 2 3 4 5 6   2 xxx 3x 5x x  18 1 2 3 4 5 6  
x  0, j  1, 6 j
Đs x*=(7/2, 0, 8, 0, 0, 3 ) F* = 6x7/2- 1x3 + 1x8 = 26
2. Giải bài toán QHTT bằng phương pháp hàm phạt :
F(x) =2x1 - 4x2 - 4x3 - 2x4 +3x5 min 2xxx 2xx  8 1 2 3 4 5 4x  2xxx  3 1 2 4 5  2x 3x 2x 3  x 2  x  14 1 2 3 4 5  x   0, j 1,5 j
Đs X*=(0 , 1, 7, 1, 0, 0) F*= -4 x 7 - 2 x 1 -4 x1 = -34
3. Giải bài toán QHTT bằng phương pháp hàm phạt:
F(x) = 2x1 -3x2 + x3 + 4x4 - 4x5 + 5x6 min xx
x  3x 2x x  10 1 2 3 4 5 6
x 2x  2x x x x  12 1 2 3 4 5 6   xxx  2xx x  12 1 2 3 4 5 6  
x  0, j  1,6 j
Đs: x* = (0, 17/2, 27/10 , 2/5, 0, 0) và F* = -106/5
4. Giải bài toán QHTT : F(x) = x1 +4 x2 + 2x3 + x4 + 3x5 min
x +2 x xxx  10 1 2 3 4 5
x x - x + 2x x  6  1 2 3 4 5   x 3x - xxx 12 1 2 3 4 5   x  0 , j=1,5 j 
Đs x*=(11,0 , 8, 0, 9) F*= 1 x 11 + 2 x 8 + 3 x 9 = 54 20