ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
-----o0o----- 
Bài giảng môn
TỐI ƯU HÓA THÂN QUANG KHOÁT
Thái nguyên - 2007

Thân Quang Khoát

MỤC LỤC

Chương 1. MỞ ĐẦU......................................................................................................3

4.1. Vấn đề .............................................................................................................31
4.2. Phương pháp hai pha giải bài toán QHTT ......................................................32
Bộ môn Khoa Học Cơ Bản
1
Bài Giảng môn Tối Ưu Hoá
4.3. Một số ví dụ ....................................................................................................34
§5. PHƯƠNG PHÁP ĐÁNH THUẾ.........................................................................36
§6. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ...................................41
6.1. Bài toán đối ngẫu ............................................................................................41
6.2. Các định lý đối ngẫu .......................................................................................42
6.3. Một số ứng dụng của lý thuyết đối ngẫu ........................................................44
6.4. Thuật toán đơn hình đối ngẫu .........................................................................46
Chương 3. TỐI ƯU HOÁ RỜI RẠC .........................................................................56
§1. BÀI TOÁN TỐI ƯU HOÁ RỜI RẠC.................................................................56
1.1. Mở đầu............................................................................................................56
1.2. Một số bài toán tối ưu hoá rời rạc tiêu biểu....................................................56
§2. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QHTT NGUYÊN..........58
2.1. Tư tưởng chung của phương pháp cắt ............................................................58
2.2. Phương pháp cắt Gomory cho bài toán QHTT nguyên hoàn toàn .................59
2.3. Phương pháp cắt Gomory cho bài toán QHTT nguyên bộ phận ....................64
§3. PHƯƠNG PHÁP NHÁNH CẬN ........................................................................65
3.1. Sơ đồ tổng quát ...............................................................................................65
3.2. Thuật toán nhánh cận Land-Doig giải bài toán QHTT nguyên......................66
3.3. Một số ví dụ ....................................................................................................68
§4. BÀI TOÁN CÁI TÚI...........................................................................................72
4.1. Đưa bài toán QHTT Nguyên về bài toán cái túi.............................................72
4.2. Phương pháp Quy hoạch động giải bài toán cái túi........................................74
Tài liệu tham khảo.......................................................................................................77
gx b j m m
gx b k m m
xX
→
⎧
≥=
⎪
⎪
⎪
⎪
≤=+⎪
⎪
⎪
⎨
⎪
==+
⎪
⎪
⎪
⎪
∈⊂ℜ
⎪
⎪
⎩

Trong đó
()f x
được gọi là hàm mục tiêu;
(), 1,
i

D
được gọi là miền ràng buộc (hay miền chấp nhận được). Mỗi một vectơ
được gọi là một phương án của bài toán (hay lời giải chấp
nhận được).
12
( , , ..., )
n
xxx x D=
Định nghĩa: Phương án được gọi là phương án tối ưu của bài toán nếu
thoả mãn điều kiện sau
*
xD∈

(®èi víi bµi to¸n t×m Min)
(®èi víi bµi to¸n t×m Max)
*
*
() (),
() (),
f xfx xD
fx fx x D
≤∀∈
≥∀∈

khi đó giá trị
*
()f x
được gọi là giá trị tối ưu.
1.2. Phân loại bài toán
Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính

ij
a
- lượng nguyên liệu loại
i
cần thiết để sản xuất một đơn vị sản phẩm loại
j
i
b
- lượng dự trữ nguyên liệu loại
i

j
c
- tiền lãi từ việc bán một đơn vị sản phẩm loại
j
1, , 1,imj==n

Hãy xây dựng kế hoạch sản xuất sao cho nhà máy thu được tổng lợi nhuận
là nhiều nhất.
Gọi
là lượng sản phẩm loại mà nhà máy sẽ sản xuất, rõ ràng ta có
. Kế hoạch sản xuất của nhà máy sẽ là véctơ . Đại lượng
là tổng chi phí nguyên liệu loại theo kế hoạch sản xuất , theo giả
thiết ta có:

j
x j
0
j
x ≥

n
jj
j
cx
=
∑

1
1
()
,1,
0, 1,
n
jj
j
n
ij j i
j
j
f xcxM
ax b i m
xjn
=
=
=→
⎧
≤=
⎪
⎪
⎪

Gọi
(1,
j
xj n
= )
là số lượng đồ vật loại mà nhà thám hiểm sẽ đem theo.
Khi đó tổng giá trị của các đồ vật đó là
, tổng trọng lượng của chúng là
. Từ giả thiết ta có . Như vậy yêu cầu của bài toán sẽ đưa
về việc giải bài toán sau:
j
1
n
jj
j
cx
=
∑
1
n
jj
j
ax
=
∑
1
n
jj
j
ax b

⎩
∑
∑
1,)n

Đây lại là một bài toán quy hoạch tuyến tính Nguyên.
1.3.3. Bài toán vận tải

Có
m
kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho thứ
i
là
(1,
m
)
i
ai
=
. Có
n
địa điểm tiêu thụ loại hàng nói trên, với nhu cầu tiêu thụ ở
điểm
là
j
(1,
j
bj n
)=
. Biết là cước phí vận chuyển một đơn vị hàng hoá từ

=
∑
là lượng hàng vận chuyển từ kho thứ
i

1
m
ij
i
x
=
∑
là lượng hàng vận chuyển đến điểm tiêu thụ thứ
j
khi đó bài toán lập kế hoạch trên có thể đưa về mô hình toán học như sau:

11
1
1
0, 1, , 1,
mn
ij ij
ij
n
ij i
j
n
ij j
j
ij


Đây chính là một bài toán Quy hoạch tuyến tính.

§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

2.1. Dạng tổng quát
Tìm véctơ
sao cho:
12
(, ,..., )
t
n
xxx x=∈
1
() ( )
n
jj
j
f xcxMinMa
=
=→
∑
x

với các điều kiện:
tù do ,
1
1
12
1

=
=
=
⎧
≥=
⎪
⎪
⎪
⎪
≤=+
⎪
⎪
⎪
⎪
⎪
==+
⎪
⎪
=
⎨
⎪
≥=
⎪
⎪
⎪
⎪
≤=+
⎪
⎪
⎪

1
1
1
n
ij j i
n
j
ij j i
n
j
ij j i
j
ax b
ax b
ax b
=
=
=
⎧
⎪
≥
⎪
⎪
⎪
=⇔
⎨
⎪
≤
⎪
⎪

được gọi là các biến bù.
ni
x
+
6) Một biến
không ràng buộc về dấu (tự do) có thể được thay bằng hiệu
hai biến không âm:
j
x

Víi 0, 0
jjj j j
xxx x x
=− ≥ ≥

Từ các nhận xét trên ta thấy rằng bất kỳ một bài toán quy hoạch tuyến tính
nào cũng có thể đưa về một trong hai dạng sau đây:
2.2. Dạng chuẩn tắc

1
1
()
,1,
0, 1,
n
jj
j
n
ij j i
j

=→
≥
⎧
⎪
⎪
⎨
⎪
≥
⎪
⎩

trong đó:

lµ ma trËn cÊp
,, ,
nm
cx b A m n∈ℜ ∈ℜ ×
2.3. Dạng chính tắc
Bộ môn Khoa Học Cơ Bản
7
Bài Giảng môn Tối Ưu Hoá

1
1
()
,1,
0, 1,
n
jj
j

f xcxMin
Ax b
x
=→
=
⎧
⎪
⎪
⎨
⎪
≥
⎪
⎩

Ví dụ: Cho bài toán quy hoạch tuyến tính

12 34
12 4
234
12 3
() 2 3 4 5 max
6
293
4
57
2
0, 1, 4
i
f xxxxx
xx x

12 4
2345
12 3 6
() 2 3 4 5 min
6
293
4
57
2
0, 1, 6
i
gx xxxx
xx x
xxxx
xxx x
xi
=− + − + →
⎧
+−
⎪
=
⎪
⎪
⎪
−++−
=
⎪
⎪
⎨
⎪

xx x
xi
=− + − + →
⎧
+−
≥
⎪
⎪
⎪
⎪
−++
≥
⎪
⎪
⎪
−−+
≥
−
⎨
⎪
⎪
−− +
≥
⎪
−
⎪
⎪
⎪
≥=
⎪

.
n
C ⊂ℜ
12
,xx C∈
Hoặc ta có thể phát biểu như sau:
lµ tËp låi th×
12 1 2
,,0;1 (1)C xxC x x xCλλλ
⎡ ⎤
⇔∀ ∈ ∀ ∈ = + − ∈
⎢ ⎥
⎣ ⎦

Các tập lồi

Ví dụ: Trong không gian 2 chiều thì các đa giác, các hình tròn, các hình elip,…
là các tập lồi.
Các siêu phẳng
{
1
n
n
ii
i
}
cxβ
=
=∈ℜ =
∑

C
. Tức là,
0
x
0
12 1 2 1
x=
2
,, : (1)xx Cx x x xαα∃∈ ≠ +−
⎡⎤
∈
⎢⎥
⎣⎦
với
α
.
0; 1
Ví dụ:
C
là đa giác lồi trong
ℜ
thì các đỉnh của nó chính là các điểm cực biên,
các điểm khác đều không là điểm cực biên. Tất cả các điểm trên đường tròn là
2
Bộ môn Khoa Học Cơ Bản
9
Bài Giảng môn Tối Ưu Hoá
điểm cực biên của hình tròn đó.
* Chú ý:
- Cần phân biệt Điểm biên và Điểm Cực biên. Ví dụ các đỉnh của một

i
α
=
=
∑
Như vậy nếu ta có 2 điểm A, B thì mọi điểm nằm trên đoạn thẳng nối hai
điểm đó sẽ là tổ hợp lồi của hai điểm A và B. Định lý sau đây sẽ cho ta biết
được một tập khi nào là một tập lồi.
Định lý: Tập
C
là tập lồi khi và chỉ khi
,0(1,)
i
i
xC i m
α∀∈ ∀≥ =
1
1
m
i
i
α
=
=
∑
α
=
∈
,
thì

điểm A, B, C là các đi
ểm cực biên của đa diện lồi này.
Định lý: Nếu M là một đa diện lồi thì nó có điểm cực biên. Số điểm cực biên của M
Khoa Công nghệ thông tin - ĐHTN
10
Thân Quang Khoát
là hữu hạn và mọi điểm của M đều là các tổ hợp lồi của các điểm cực biên đó.
Như vậy định lý này cho chúng ta biết được một tính chất quan trọng của
đa diện lồi, đó là số đỉnh cực biên của một đa diện lồi cho trước là hữu hạn.
Về mặt hình học ta thấy, đa diện lồi là một tập lồ
i và là giao của một số các
nửa không gian đóng trong
. Tuy nhiên điều ngược lại chưa chắc đúng. Vậy
thì làm thế nào để biết được phần giao của các nửa không gian đóng trong
là
một đa diện lồi ?
n
ℜ
n
ℜ
Hai nhà toán học là Hoàng Tụy và Asmanov sẽ trả lời cho chúng ta bằng
định lý sau đây:
Định lý: Xét tập
{
n
Mx Axb
=∈ℜ ≥
}
trong đó
A

⎪
⎨
⎪
≥
⎪
⎩
(I)
Ký hiệu:
{}
,0
n
Dx Axbx=∈ℜ = ≥

Đặt: ,
0
EE
A
b
AAb
E
⎛⎞
⎛⎞
⎟
⎟
⎜
⎜
⎟

⎟
⎟⎜
⎜
⎝⎠
⎝⎠
b
khi đó ta có:
{}
n
EE
Dx Axb
=∈ℜ ≥

Phương án cực biên: Phương án được gọi là phương án cực biên của
bài toán (I) nếu
là điểm cực biên của
D
.
0
xD∈
0
x
Bộ môn Khoa Học Cơ Bản
11
Bài Giảng môn Tối Ưu Hoá
Phương án cực biên tối ưu: Nếu phương án cực biên là phương án tối ưu
của bài toán (I) thì
được gọi là phương án cực biên tối ưu của bài toán (I).
0
x

∑∑
j
j
yβ
(1,
i
xi m=
)
là các điểm
cực biên của
G
;
1
0, 1, 0, 0 ( 1, )
m
j
ii j
i
Ay j k
αα β
=
≥=≥≥=
∑
.
Áp dụng định lý đối với miền ràng buộc
thì ta có: Do nên
theo định lý, nếu
(tức là bài toán (I) có phương án) thì
D
có đỉnh cực

pk
i
i
ij
xx
α
==
=+
∑∑
(1,
i
xi p=
)
là các điểm cực biên của ;
D
1
0, 1, 0, 0 ( 1, )
p
j
ii j
i
Ay j k
αα β
=
≥==≥=
∑
.
Chứng minh:
Ta viết lại
dưới dạng

1
k
j
j
j
y
β
=
+
∑
(1,
i
xi p=
)
là các điểm cực biên của ; ,
D
1
0, 1
p
ii
i
αα
=
≥=
∑
0, 0 ( 1, )
j
Ej
Ay j k
β

x
của (I) đều có thể viết dưới dạng:
11
mk
i
i
ij
xx
α
==
=+
∑∑
j
j
y
β
, trong đó
(1,
i
xi m=
)
là các điểm cực biên của ;
D
1
0, 1, 0, 0 ( 1, )
m
j
ii j
i
Ay j k

thì
0
0,
j
jjβ =∀≠
0
j
β
→+∞
0
0
1
() ( ) .( )
m
ij
ij
i
f xfxfy
αβ
=
=+→
∑
−∞
r
. Điều này trái với giả thiết
hàm mục tiêu bị chặn dưới trên miền ràng buộc
D
.
b)
thì:

=+
≥
≥==
∑∑
∑
∑∑

Vậy
() ( ),
r
f xfx xD
≥∀∈
, hay là phương án tối ưu của bài toán (I). Do đó ta
đi đến kết luận của hệ quả này. ■
r
x
4.2. Điều kiện cần và đủ để một phương án là cực biên
Xét bài toán QHTT dạng chính tắc (I). Ký hiệu
là các véctơ cột
của ma trận ràng buộc
12
, ,...,
n
aa a11 12 1
21 22 2
12
...

⎜
⎟
⎜
⎝⎠
Không mất tổng quát ta luôn giả thiết

{}
12
( ) , ,...,
n
rank A rank a a a m
==
Bộ môn Khoa Học Cơ Bản
13
Bài Giảng môn Tối Ưu Hoá
(nếu có phương trình nào trong hệ là tổ hợp tuyến tính của các phương
trình khác thì ta có thể loại bỏ đi). Khi đó ta có định lý sau:
Ax b
=
Định lý: Phương án
là một phương án cực biên khi và chỉ khi hệ các
véctơ cột của ma trận
tương ứng với các thành phần dương của độc lập
tuyến tính.
0
xD
∈
A
0
x

(có thể đánh lại
chỉ số các biến nếu cần thiết để thu được điều kiện này).
0
(){1,2,...,}
Jx k
=
“Điều kiện cần”: giả thiết
là một phương án cực biên của (I).
0
xD∈
Giả sử hệ vectơ
phụ thuộc tuyến tính. Khi
đó tồn tại các số không đồng thời bằng 0 để . Đặt
. Khi đó ta có:
{}
{
012
,(),,...,
j
ajJx aa a
+
∈=
12
, ,...,
k
zz z
1
1
...
k

đủ bé sao cho (luôn lấy được vì
z
) thì ta có
. Mà ta lại có
λ
'0,''0xx≥≥
λ
θ≠
',''xDx D∈∈
0
11
'
22
xxx=+''
}
}
, trái với giả thiết là phương án
cực biên của (I). Vậy hệ
{
độc lập tuyến tính.
0
x
12
, ,...,
k
aa a
“Điều kiện đủ”: giả thiết hệ
{
độc lập tuyến tính.
12

jj
nk
jj jj
jj
Ax xa xa b
Ax x a x a b
==
==
===
===
′′ ′
∑∑
∑∑

Khoa Công nghệ thông tin - ĐHTN
14
Thân Quang Khoát
11
0
11
nk
jj jj
jj
kkk
jj jj jj
jjj
Ax x a x a b
xa xa xa
==
===

mâu thuẫn với giả thiết
x
. Do đó là phương án cực biên. ■
0
xxx==
′′′
′′
x≠
′
0
x
Ví dụ: xét miền D được xác định như sau

12 3
12 3
134
32
23
22
0, 1, 4
i
xx x
xx x
xxx
xi
++ =
⎧
⎪
⎪
⎪

{}
0
() 1;3;4Jx
+
=
{
0
|(
j
ajJx
+
∈
13
(3,2,2), (2,3,1),
tt
aa==
4
a =
(0, 0, 2)
t 0
(1; 0; 1; 3)
t
x =
Dễ dàng kiểm tra được rằng vectơ
1
9
2
(0;5;0; )
t
x =

()Card J x k
+
=
0
x
{}
0
,(
j
aj J x
+
∈
≤
Nếu
thì ta luôn có thể bổ xung thêm
(
véctơ cột khác của
để được một hệ véctơ độc lập tuyến tính cực đại gồm đủ
véctơ, nghĩa là ta
tìm được tập gồm đủ
chỉ số sao cho hệ
là độc lập tuyến tính. Còn nếu
k
thì ta đặt .
km< mk− A
m
m
{}
0
12

0
x
Định nghĩa: một phương án cực biên là không suy biến nếu có đúng
thành phần dương, tức là
. Ngược lại thì gọi là suy biến.
0
x
m
()
0
()
Card J x m
+
=
Ví dụ: Đối với ví dụ trên thì
.
() 3rank A =
- Phương án cực biên
có cơ sở là .
Do đó nó là phương án cực biên không suy biến.
0
(1; 0; 1; 3)
t
x =
0
( ) {1;3;4}JJx
+
==
- Phương án cực biên
1

m
n
CKhoa Công nghệ thông tin - ĐHTN
16
Thân Quang Khoát

Chương 2. THUẬT TOÁN ĐƠN HÌNH

§1. MỞ ĐẦU
1.1. Bài toán
Ta xét bài toán QHTT dạng chính tắc sau:

()
0
t
f xcxMin
Ax b
x
=→
=
⎧
⎪
⎪
⎨
⎪
≥
⎪

,1,
iii
ax ax b i m+≥ =

Ký hiệu:
{}
12 11 22
(, ) , 1,
iii
Dxxxaxaxb i m== + ≥ =

Ta biết rằng mỗi một bất phương trình tuyến tính
xác định
11 22ii
ax ax b+≥
i
Bộ môn Khoa Học Cơ Bản
17
Bài Giảng môn Tối Ưu Hoá
một nửa mặt phẳng. Như vậy tập
D
là giao của
m
nửa mặt phẳng sẽ là một đa
giác lồi trên mặt phẳng.
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.

,
ta dịch chuyển đường mức theo hướng ngược với hướng véctơ
cho
đến khi nào việc dịch chuyển tiếp theo làm cho đường mức không cắt
D
nữa thì
dừng. Các điểm của
nằm trên đường mức này sẽ là các lời giải cần tìm, còn
giá trị mức chính là giá trị tối ưu của bài toán.
12
(, )ccc=
12
(, )
ccc
=
D
Ví dụ: Giải bài toán QHTT sau

12
12
12
12
12
() min
7(
2
22
0, 0
1)
(2)

giảm (dựa vào véctơ pháp tuyến
) để tìm ra đường mức có mức nhỏ
nhất cắt miền D.
12
0xx−=
(1, 1)c =−

Khoa Công nghệ thông tin - ĐHTN
18
Thân Quang Khoát

2
x
1
x
Ta thấy miền D của bài toán chính là đa giác ABIJK. Khi dịch chuyển
đường mức theo hướng véctơ
thì điểm I chính là điểm cuối cùng mà đường
mức cắt miền D. Vì vậy I chính là điểm cực biên tối ưu.
c−

Do I là giao điểm của đường thẳng (1) với
nên toạ độ điểm I chính là
nghiệm của hệ pt:
2
Ox1
12


()
0
t
f xcxMin
Ax b
x
=→
=
⎧
⎪
⎪
⎨
⎪
≥
⎪
⎩
(I)
Bộ môn Khoa Học Cơ Bản
19
Bài Giảng môn Tối Ưu Hoá
trong đó
lµ ma trËn cÊp
,, ,
nm
cx b A m n
∈ℜ ∈ℜ ×
Chúng ta đã biết rằng:
- Nếu bài toán (I) có phương án thì có phương án cực biên.
- Nếu bài toán (I) có phương án tối ưu thì cũng có phương án cực biên tối ưu.

J
tương ứng. Khi đó ta có:
0
x

hay (2.2.1)
0
Ax b=
0
1
n
j
j
jjJ
bxa x
=∈
==
∑∑
0
j
j
a
Vì hệ véctơ
{ }
|
j
ajJ∈
là độc lập tuyến tính nên nó là một cơ sở trong không
gian
. Do đó ta có thể biểu diễn véctơ qua cơ sở đó như sau:

bxa xa x
=∈
∉
==+
∑∑∑jj
jk
jJ jJ
kJ
xa x z a
∈∈
∉
=+
∑∑∑

( )
j
jjkk
jJ
kJ
xzx
∈
∉
=+
∑∑
a
}
)

ta gọi (2.2.3) là khai triển của một phương án bất kỳ qua cơ sở
J
.
Bây giờ ta xét hàm mục tiêu:

1
()
n
t
jj jj kk
jjJ
kJ
f xcx cx cx cx
=∈
∉
===+
∑∑∑
()
()
0
0
jjkkjk
jJ
kJ kJ
jj jkj k k
jJ jJ
kJ

f xfx x
∉
=−∆
∑
(2.2.4)
Đại lượng
được gọi là công thức số gia hàm mục tiêu.
kk
kJ
x
∉
−∆
∑
Từ (2.2.4) ta thấy rằng, nếu (do
). Do đó ta có dấu hiệu tối ưu sau:
th×
0
,0()(),
k
k J fx fx x D∀∉ ∆≤ ≥ ∀∈
0x ≥
Định lý: Phương án cực biên
ứng với cơ sở
J
là phương án tối ưu khi và chỉ
khi
.
0
x
0,

0
x
1
x
1
x
1
J
1
{ }\{ }
JJsr
=∪
s
a
r
a
s
a
r
a
1
x
0
x
Vì mọi thành phần ngoài cơ sở của một phương án cực biên đều bằng 0 nên
phương án cực biên mới
có cơ sở là
1
x
1

Thay (2.2.5) vào (2.2.3) ta được: 10 10
()
j j jk k j js
kJ
xx zxx z jJθ
∉
=− =− ∀∈
∑
Như vậy ta có:

(2.2.6)
víi
víi
víi
1
0
0,
j
jjs
jJj s
xj
xz jJ
θ
θ
⎧
⎪
∉≠

jjs
jjs
jJ jJ
Ax xa xa x z a a
xa z a a b
θθ
θθ
∈∈
∉
∈∈
=+=−+
=− +=
∑∑∑
∑∑
Vậy
thì ràng buộc thứ nhất luôn thoả mãn. Do đó ta chỉ cần chọn sao
cho
. Có hai trường hợp xảy ra:
θ∀
θ
1
0
x
≥
a)
Trường hợp 1: Nếu thì là phương án,
nhưng:
1
0, 0, 0
js

sẽ không bị chặn dưới
trong miền ràng buộc.
b)
Trường hợp 2: Nếu , khi đó theo (2.2.6) số
θ
không thể lớn tuỳ
ý, nó phải thoả mãn điều kiện
. Như vậy có thể lấy:
,
js
jJz∃∈ >0
10
0( )
jj js
xx z jJ
θ
=−≥∀∈

{}
0
0
min : , 0
j
r
js
rs js
x
x
jJz
zz

r
jjs
rs
jJj s
x
x
z
x
xz jJ
z
∉≠
⎧
⎪
⎪
⎪
⎪
⎪
⎪
=
⎨
⎪
⎪
⎪
⎪
−∈
⎪
⎪
⎩
js
=

và trong cơ sở . Người
ta đã tìm được chúng như sau:
jk
z
k
∆
1
jk
z
1
k
∆
1
J

víi
víi
1
,
rk
rs
jk
rk
jk js
rs
z
js
z
z
z

bước trước để tìm tất cả các yếu tố cần thiết cho việc thực hiện các bước sau của
thuật toán đơn hình.
J
1
{ }\{ }
JJsr=∪
2.4. Thuật toán đơn hình (Simplex method)
* Thuật toán:
¾ Bước xuất phát: Tìm một phương án cực biên
và cơ sở tương
ứng. Tính các hệ số khai triển
và các ước lượng .
0
x
J
jk
z
k
∆
¾ Bước 1: (kiểm tra dấu hiệu tối ưu)
a) Nếu
0, 1,
k
k∆≤ ∀ = n
thì kết luận là phương án tối ưu. Kết
thúc thuật toán.
0
x
Bộ môn Khoa Học Cơ Bản
23

{}
0
0
min : , 0
j
r
js
rs js
x
x
jJz
zz
=∈>
1
jk

chuyển sang bước 4.
¾ Bước 4: Tính các giá trị
trong cơ sở mới
theo các công thức (2.2.7), (2.2.8), (2.2.9), (2.2.10).
Quay trở lại bước 1.
111
,(), ,
jk
xfx z∆
1
{ }\{ }
JJsr=∪
2.5. Bảng đơn hình
Cơ sở Hệ số Phương án 1 2 … k … n

j
x

1
1j
z

1
2j
z

…
1
jk
z

…
1
jn
z

2
j

2
j
c

2
j

x

1
m
j
z

2
m
j
z

…
m
jk
z

…
m
jn
z

()f x

1
∆

2
∆