50
2.3. Những phương pháp giải bài toán QHTT
2.3.1.
2.3.1.
Phương
Phương
ph
ph
á
á
p
p
đ
đ
ồ
ồ
th
th
ị
ị
2.3.2.
2.3.2.
Phương
Phương
ph
ph
á
á
p
p
đơn

 Xác định miềnphương án chấpnhận được;
 Từđótìmphương án tối ưutrênmiềnchấtnhận đó.
52
a. Xác định miềnchấpnhậnbằng đồ thị
 Mỗitrụcthể hiệnmộtbiếnquyết định;
 Mỗiràngbuộcvẽ một đường thẳng để xác định miềnchấp
nhận:
 Mỗi đường thẳng chỉ cầnvẽ 2 điểmvànối chúng với nhau;
 Chọnmột điểmbấtkỳ thoả mãn ràng buộc, miềnchứa điểm đó
sẽ là miềnchấpnhậnthỏamãnràngbuộc đang xét;
 Giao tấtcả các miềnchấpnhậncủa các ràng buộc hình thành
vùng chấpnhậncủa bài toán.
Bấtcứđiểmnàonằmtrênđường biên của vùng chấpnhậnhoặc
trong vùng chấpnhận đượcgọilàđiểmphương án chấpnhận được
đốivới bài toán qui hoạch.
53
a. Tiếp
Nguyên liệu 2
Nguyên liệu 1
Nguyên liệu 3
0
10
20
30
40
50
60
70
0 1020304050
Số tấn chất phụ gia

Vẽđường mục tiêu
Cho hàm mục tiêu bằng mộtgiátrị bấtkỳ và vẽđường mục
tiêu. Đốivớibàitoáncực đại, tịnh tiến đường mục tiêu trong
vùng chấpnhậntheohướng làm giá trị củahàmmục tiêu lớn
hơnchođến khi giá trị củahàmmục tiêu lớnnhất(đốivới
bài toán cựctiểu thì ngượclại);

Bấtkỳ phương án trên đường mụctiêuvớigiátrị lớnnhất
(đốivớibàitoáncực đại) là phương án tối ưu.
56
2.3.2. Phương pháp đơnhình
b.
b.
Thuật toán đơnhìnhgiảibàitoándạng chuẩn
c.
c.
Thuật toán đơnhìnhgiảibàitoánmở rộng
d.
d.
Giảibằng máy tính
a.
a.
Cơ sở toán họccủaphương pháp
57
Cơ sở toán củaphương pháp
 Tính chất1: Nếu bài toán có phương án tối ưuthìcũng có
phương án cơ bảntối ưu.
 Tính chất2: Số phương án cơ bảnlàhữuhạn.
 Tính chất3: Điềukiệncầnvàđủ để bài toán có phương án
tối ưulàhàmmục tiêu củanóbị chặndưới khi f(x)→min và

r
a
rn
a
rv
a
r(m+1)
0 1 00c
r
x
r
……
b
2
a
2n
a
2v
a
2(m+1)
0 0 10c
2
x
2
b
1
a
1n
a
1v

x
m
…x
r
…x
2
x
1
Hệ
số
Biến
cơ
bản
j
m
1i
ijij
m
1i
ii0
cac&bcf −=Δ=
∑∑
==
59
Thuật toán bài toán Min
 Bước3: Kiểm tra tính tối ưu
 Nếu Δ
j
≤0 ∀j Ö phương án đang xét là tối ưu và giá trị hàm
mục tiêu là f(x)=f

i
thì x
r
là biến đưa ra. Hàng r là hàng chủ yếu,
phầntử a
rv
là phầntử trục xoay.
60
Thuật toán bài toán Min
 Bước6: Biến đổibảng như sau :
 Thay x
r
bằng x
v
và c
r
bằng c
v
. Các biếncơ bảnkhácvàhệ số
tương ứng để nguyên.
 Chia hàng chủ yếu(hàngr) chophầntử trụcxoaya
rv
, chúng ta
đượchàngr mớigọilàhàng chuẩn.
 Muốncóhàngi mới(i≠r), lấy–a
iv
nhân vớihàngchuẩnrồi
cộng vào hàng i cũ.
 Muốncóhàngcuốimới, lấy-Δ
v

4
+ x
6
= 15
-2x
1
+ x
3
-2x
6
= 9
4x
1
+ 2x
4
+ x
5
-3x
6
= 2
Ràng buộcdấu
x
j
≥0 (mọij)
62
Giải
2630-200-5
2-3120041x
5
9-20010-21x

5
3900-212-41x
3
1510-101-1-7x
6
-713116
λ
i
P.án
x
6
x
5
x
4
x
3
x
2
x
1
Hệ
số
Biến
cơ
bản
Khôngcóphương án tối ưu
64
Thuật toán bài toán Max
So với bài toán Min, bài toán Max có các thay đổisau:

Ràng buộcdấu
F, B, S1, S2, S3 ≥0
66
Ví dụ 2: Bài toán ABC
Thành lậpbảng đơnhìnhđầutiên
0000-30-400
35211000,30,60S3
50100,200S2
50200010,50,40S1
0003040
λ
i
b
i
S3S2S1BF
Hệ số
Biến
cơ bản
67
Ví dụ 2: Bài toán ABC
Bảng 2
1400200/300-100
703510/6000,5140F
2550100,200S2
206-2/3010,300S1
0003040
λ
i
P.án
S3S2S1BF

bài toán xuấtphát.
 Nếu bài toán mở rộng có phương án tối ưu mà trong đócóít
nhấtmộtbiếngiả dương thì bài toán xuất phát không có
phương án tối ưu.
70
b. Thuậttoánđơnhìnhgiải bài toán mở rộng
 Trong bài toán mở rộng, Δ
j
và f(x*) sẽ gồm2 phần:
 mộtphầnphụ thuộcvàoM,
 mộtphần không phụ thuộcvàoM.
Ö
Hàng cuốicủabảng chia hai dòng nhỏ:
 dòng trên ghi phần không phụ thuộcM,
 dòng dưới ghi hệ số M.

Mỗi khi mộtbiếngiả bịđưakhỏihệ biếncơ bản thì sẽ không
được đưatrở lại, vì vậycóthể không cần chú ý tới các cột
ứng vớibiếngiả.
71
Ví dụ giải bài toán mở rộng
Min(x
1
+2x
2
+x
4
-5x
5
)

Min(x
1
+2x
2
+x
4
-5x
5
+Mx
6
+Mx
7
)
S.t.
3x
3
-9x
4
+x
6
=0
x
2
- 7x3 - x
4
-2x
5
+ x
7
= 5

Ph.án
x
5
x
4
x
3
x
2
x
1
Hệ số
Biến
cơ
bản
73
Giải bài toán mở rộng
00-9-300
37/02/3-2-47/3 00
7/3-1/31-5/3011x
1
5-2-1-7102x
2
00-9-300Mx
6
-51021
λ
i
Ph.án
x

b
à
à
i
i
to
to
á
á
n
n
đ
đ
ố
ố
i
i
ng
ng
ẫ
ẫ
u
u
2.4.2.
2.4.2. Qui
Qui
t
t
ắ
ắ

u
u
2.4.3.
2.4.3.
Quan
Quan
h
h
ệ
ệ
gi
gi
ữ
ữ
a
a
b
b
à
à
i
i
to
to
á
á
n
n
g
g

u
u