LỜI CÁM ƠN
DANH SÁCH CÁC BẢNG
DANH SÁCH CÁC HÌNH
MỤC LỤC
LỜI MỞ ĐẦU

-1-


Chương 1
MÔ HÌNH BÀI TOÁN TỐI ƯU HÓA
Trong chương này, luận văn sẽ trình bày một số kiến thức cơ bản về mô hình tổng
quát của bài toán tối ưu hóa, việc phân loại các bài toán tối ưu và cơ sở toán học
của bài toán tối ưu. Các kiến thức này được tham khảo trong các tài liệu [1, 2, 3,
4].

1.1 Các khái niệm cơ bản
1.1.1 Mô hình tổng quát bài toán tối ưu hóa
Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh hưởng
đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm giải pháp
tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan trọng như việc
tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các quá trình … Nếu
sử dụng các kiến thức trên nền tảng của toán học để giải quyết các bài toán cực trị,
người ta sẽ đạt được hiệu quả kinh tế cao. Điều này phù hợp với mục đích của các vấn
đề đặt ra trong thực tế hiện nay.
Bài toán tối ưu tổng quát được phát biểu như sau:
Cực đại hóa (cực tiểu hóa) hàm:

f ( X ) → max(min)
Với các điều kiện:
gi ( X ) = bi , i ∈ J1

(1.1)

g j ( X ) ≤ bj , j ∈ J2

(1.2)

g k ( X ) ≥ bk , k ∈ J 3

(1.3)

x1 , x2 ,..., xn ≥ 0.

(1.4)

Trong đó f ( X ) được gọi là hàm mục tiêu, Các điều kiện (1.1) được gọi là ràng
buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức. Các

-2-


điều kiện (1.4) được gọi là ràng buộc về dấu. X = ( x1 , x2 ,..., xn ) là véc tơ thuộc không
gian R n . Tập các véc tơ X thỏa mãn hệ ràng buộc lập nên một miền D được gọi là
miền phương án (hay miền chấp nhận được), mỗi điểm X ∈ D gọi là một phương án.
Một phương án X * ∈ D làm cho hàm mục tiêu f ( X ) đạt max (min) được gọi là phương
án tối ưu.

1.1.2 Phân loại bài toán tối ưu
Dựa trên mô hình tổng quát, người ta thường phân loại lớp các bài toán tối ưu
như sau:

• Qui hoạch tuyến tính: là những bài toán mà hàm mục tiêu f ( X ) và tất cả các
hàm ràng buộc gi ( X ), g j ( X ), g k ( X ) là tuyến tính.
• Qui hoạch phi tuyến: là những bài toán một trong hàm mục tiêu f ( X ) hoặc
các hàm ràng buộc gi ( X ) , g j ( X ) , g k ( X ) là phi tuyến.
• Qui hoạch lồi: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lồi trên
tập các ràng buộc D lồi.
• Qui hoạch lõm: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lõm
trên tập các ràng buộc D lõm.
• Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền ràng
buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị
nguyên thì ta có qui hoạch nguyên.
• Qui hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời
các hàm mục tiêu khác nhau.
Trong các lĩnh vực kinh tế kỹ thuật thì qui hoạch phi tuyến, qui hoạch tuyến tính là
những bài toán thường gặp.

1.2 Bài toán quy hoạch tuyến tính
Từ một số các mô hình trong thực tế, ta có mô hình tổng quát cho bài toán quy
hoạch tuyến tính như sau:
Xác định các biến x j ( j = 1, 2,..., n) sao cho:

-3-


n

F ( x) = ∑ c j x j → Max( Min)
j =1

n


∑a x
j =1

ij

j

≥ bi ( i ∈ I1 ⊂ M )

(1.5)

j

= bi ( i ∈ I 2 = M \ I1 )

(1.6)

n

∑a x
j =1

ij

x j ≥ 0( j ∈ J ⊂ N )

Với

(1.7)


M = { 1, 2,..., m} , N = { 1, 2,..., n}

Vectơ X = ( x1 , x2 ,..., xn ) thỏa mãn các điều kiện (1.5) - (1.7) được gọi là một
phương án của bài toán. Tập các nghiệm thỏa mãn hệ ràng buộc được gọi là miền
phương án ký hiệu là D . Phương án thỏa mãn điều kiện để hàm mục tiêu đạt
Max(min) được gọi là phương án tối ưu.
Dạng chính tắc:
n

F ( x) = ∑ c j x j → Min
j =1

n

∑a x
j =1

ij

j

= bi ( i ∈ M )

x j ≥ 0( j ∈ N )

Dạng chuẩn tắc:
n

F ( x) = ∑ c j x j → Min

j =1

n

∑a x
j =1

ij

j

≥ bi ( i ∈ M )

x j ≥ 0( j ∈ N )

Sử dụng các ký hiệu vectơ và ma trận, mô hình bài toán quy hoạch tuyến tính
tổng quát được biểu diễn như sau:

-4-


f ( X ) = C T X → Max(min)
AX = b
X ≥0

Trong đó: X = ( x1 , x2 ,..., xn ), C = (c1 , c2 ,..., cn )
 a11
a
A =  21
 ...


 am1

a12
a22
am 2

... a1n 
 x1 
b1 


b 

... a2 n 
x2 

 2
X
=
b
=
,
,


... 

...
 

 

... amn 
 xn 
bm 

1.3 Một số thuật toán kinh điển
1.3.1 Thuật toán đơn hình
1.3.1.1 Mô tả thuật toán gốc
Cơ sở của phương pháp này được Dantzig công bố năm 1947 có tên gọi là
phương pháp đơn hình. Xuất xứ tên gọi như vậy vì những bài toán đầu tiên được giải
bằng phương pháp đó có các ràng buộc dạng:
n

∑x
j =1

Mà tập các điểm x ∈ ¡

j

n

= 1, x j > 0, ( j = 1, 2,..., n)

thoả mãn các ràng buộc trên là một đơn hình trong

không gian n chiều.
1.3.1.2 Tư tưởng chung
Phương pháp đơn hình dựa trên hai nhận xét sau:

• Nếu bài toán QHTT có phương án tối ưu thì có ít nhất một đỉnh của D là
phương án tối ưu.
• Đa diện lồi D có một số hữu hạn đỉnh.
Như vậy phải tồn tại một thuật toán hữu hạn. Thuật toán gồm 2 bước như sau:
Bước 1: Tìm 1 phương án cực biên.
Bước 2: Kiểm tra điều kiện tối ưu đối với phương án đó.

-5-


+ Nếu điều kiện tối ưu được thoả mãn thì phương án đó là tối ưu. nếu không ta
chuyển sang phương án cực biên mới sao cho làm tốt hơn giá trị hàm mục tiêu.
+ Kiểm tra điều kiện tối ưu đối với phương án mới.
Người ta thực hiện một dãy các thủ tục như vậy cho đến khi nhận được phương
án tối ưu, hoặc đến tình huống bài toán không có phương án tối ưu.
1.3.1.3 Cơ sở lý thuyết
Xét bài toán QHTT dưới dạng chính tắc:
f ( x ) = CT X ⇒ Min
AX = b

X ≥0

Trong đó A = ( aij ) n×m , X = ( x1 , x2 ,..., xn ); C = (c1 , c2 ,..., cn ). , giả sử rằng hạng của ma
trận A là m .
Giả sử X là một phương án cực biên nào đó.
Ta ký hiệu: J * = { j | x j > 0}

(2.1)

Vì các véc tơ Aj , j ∈ J * là độc lập tuyến tính nên | J * |≤ m .

Định nghĩa 1.1: Phương án cực biên X được gọi là không suy biến nếu
| J * |= m , suy biến nếu | J * |< m .

Ta chọn một hệ thống m véc tơ độc lập tuyến tính { Aj , j ∈ J } sao cho J ⊇ J * .
Hệ thống đó là cơ sở của X , các véc tơ Aj , j ∈ J và biến x j , j ∈ J được gọi là các véc
tơ và các biến cơ sở tương ứng. Các véc tơ và các biến Aj , x j , ( j ∉ J ) gọi là các véc tơ
và các biến phi cơ sở.
Nếu X không suy biến thì tồn tại một cơ sở duy nhất, đó là J = J * .
Mọi véc tơ Ak phi cơ sở có thể biểu diễn dưới dạng tổ hợp tuyến tính của các
véc tơ cơ sở:
Ak = ∑ z jk A j

(2.2)

j∈J

-6-


Trong các hệ số z jk được xác định duy nhất bởi việc giải hệ phương trình:
a jk = ∑ z jk aij , (i = 1, 2,..., m)
j∈J

( 2.3)

Bài toán QHTT được gọi là không suy biến nếu tất cả các phương án cực biên
của nó đều không suy biến.
Giả sử bài toán không suy biến và ta đã tìm được một phương án cực biên
X = ( x1 , x2 ,..., xm , 0,..., 0) và cơ sở của nó A1 , A2 ,..., Am .


Đối với phương án cực biên này ta có:
m

∑x A
j

j =1

j

= b, x j > 0, ( j = 1, 2,..., m)

(2.4)

Với giá trị hàm mục tiêu:
m

∑c x
j =1

j

j

= Z 0 , x j > 0, ( j = 1, 2,..., m)

(2.5)

Ta tính các đại lượng sau:
m


∑z
j =1

jk

c j = zk

(2.6)

Ký hiệu:
m

∆ k = zk − ck = ∑ z jk c j − ck
j =1

(2.7)

Định lý 1.1: Nếu đối với các phương án cực biên X = ( x1 , x2 ,..., xm , 0,..., 0) mà
các điều kiện sau được thỏa mãn:
∆ k ≥ 0, ∀k = 1, 2,..., n

(2.8)

thì X là phương án tối ưu.
Nhận xét:
1. Trong (2.2) nếu Aj là một véc tơ cơ sở khi đó tồn tại chỉ một hệ số zij = 1 , tất cả
các hệ số khác đều bằng 0 và ta có: ∆ j = c j − c j = 0, j ∈ J

-7-



Và trong thực tế để kiểm tra điều kiện tối ưu của phương án cực biên X ta chỉ
kiểm tra: ∆ k ≥ 0, ∀k ∉ J
2. Người ta có thể chứng minh rằng nếu bài toán không suy biến thì (2.8) cũng là
điều kiện cần của bài toán tối ưu.
Định lý 1.2: Nếu tồn tại một chỉ số k sao cho ∆ k < 0 thì ta có thể tìm được ít
nhất một phương án X ' mà đối với nó Z ' > Z .
Trong thực tế Dantzig đã chứng minh rằng số các bước lặp sẽ giảm đáng kể nếu

{ ∆ k | ∆ k < 0} và khi đó véc tơ Ar
ta thay véc tơ Ak bởi véc tơ As thỏa mãn ∆ s = min
k
được xác định theo công thức:
 x
 x
θ s = min  j | z js > 0  = r
 zrs
 z js

(2.9)

Ta có phương án cực biên mới X ' mà các thành phần của nó có dạng:
xr '

x
−
z js , j ≠ r
j


z

rs
x 'j = 
x
 r , j=r
 zrs

Với cơ sở của nó là: Aj , j ∈ J ' = J \ { r} ∪ { s}
Xuất phát từ cơ sở lý thuyết trên, chúng ta có thuật toán sau đây.
1.3.1.4 Thuật toán đơn hình
Bước 1: Tìm một phương án cực biên xuất phát X và cơ sở của nó Aj , j ∈ J
Bước 2:
z jk Aj
+ Xác định các số z jk bởi hệ thống: Ak = ∑
j∈J

+ Đối với mỗi k ∉ J tính các ước lượng:
m

∆ k = ∑ z jk c j − ck
j =1

-8-

(2.10)

(2.11)



• Nếu (∀k ∉ J ), ∆ k ≥ 0 ⇒ x là nghiệm tối ưu. Thuật toán dừng.
• Nếu X không phải là nghiệm tối ưu:
o (∃k ∉ J ), ∆ k < 0 và z jk ≤ 0, ∀j ∈ J ⇒ bài toán QHTT không có nghiệm tối
ưu. Thuật toán dừng.
o Đối với mỗi k ∉ J sao cho ∆ k < 0 đều tồn tại j ∈ J : z jk > 0 ⇒ chọn
∆ s = min { ∆ k | ∆ k < 0} , đưa véc tơ As vào cơ sở.
 xj
 x
| z js > 0  = r . Đưa véc tơ Ar ra khỏi cơ sở.
 zrz
 zrs

Bước 3: Xác định: θ s = min 

Bước 4: Xác định phương án cực biên mới X ' với cơ sở J ' = J \ { r} ∪ { s} .
Quay trở lại bước 2.
1.3.1.5 Công thức đổi cơ sở, bảng đơn hình
Ta xét các công thức chuyển từ phương án cực biên X với cơ sở J , sang
phương án cực biên X ' với cơ sở J ' . Xuất phát từ công thức (2.10) cho phép tính các
'
thành phần của X ' . Ta cần thiết lập công thức tính các số z jk .

Ta có:
As = ∑ zij Aj ⇒ Ar =
j∈J

1
( As − ∑ z js A j )
zrs
j∈J


(2.12)

j≠r

Mặt khác:
Ak = ∑ ( z jk A j + zrk Ar )

(2.13)

j∈J

Thay biểu thức của Ar từ (2.12) vào (2.13) ta có:
Ak = ∑ z jk A j +
j∈J

zrk
( As − ∑ z js A j )
zrs
j∈J
j ≠r

Ak = ∑ ( z jk A j −
j∈J
j≠r

zrk
z
z js )Aj + sk
zrs

zrs

-9-


Đây là công thức biểu diễn Ak qua cơ sở mới J ' = J \ { r} ∪ { s} . Khi đó ta có:
zrk

 z jk − z z js , j ≠ r

rs
z 'jk = 
z
 rk , j = r
 zrs
'
'
z 'jk c j − ck
Sau khi có z jk ta tính: ∆ k = ∑
j∈J

(2.14)

Để dễ tính toán, tại mỗi bước lặp ta thiết lập bảng đơn hình
cj

Cơ

Phương


c1

c2…

c j…

cr…

cm…

ck

…cs

…ch

sở

án

A1

A2…

Aj …

A r…

Am…


Ak

…As

…Ah

c1

A1

x1

1

0…

0…

0…

0…

z1k

z1s

z1n

c2


A2

x2

0

1

0

0

0

z2k

z2s

z2n

.

.

.

.

.


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.


.

.

cj

Aj

xj

0

0

1

0

0

zjk

zjs

zjn

.

.


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.


.

.

.

.

.

cr

Ar

xr

0

0

0

1

0

zrk

zrs


zrn

.

.

.

.

.

.

.

.

.

.

.

.

.

.


.

.

.

.

.

.

.

.

cm

Am

xm

0

0

0

0


1

zmk

zms

zmn

F

0

0…

0…

0…

0…

∆k

… ∆s

… ∆n

Bảng 1.1: Bảng đơn hình
Sử dụng các phương pháp biến đổi theo thuật toán sau

-10-



- Nếu tất cả các số trong hàng cuối (trừ F) đều ≥ 0 , nghĩa là ∆ k ≥ 0, ∀k , khi đó
X là phương án tối ưu. Thuật toán dừng.

- Nếu hàng cuối (không kể F) tồn tại số âm mà mọi số trong cột tương ứng đều
≤ 0 thì bài toán không tồn tại phương án tối ưu.

Ngược lại:
+ Chọn cột s sao cho: ∆ s = min { ∆ k | ∆ k < 0} , Cột s gọi là cột xoay. Véc tơ As
được đưa vào cơ sở.
+ Chọn hàng r mà tỉ số: θ r =

 x

xr
= min  j | z js > 0  . Hàng r gọi là hàng xoay.
zrs

 z js

Véc tơ Ar bị đưa ra khỏi cơ sở.
Phần tử zrs > 0 là giao của cột xoay và dòng xoay gọi là phần tử trục. Các phần
tử z js , j ≠ r gọi là phần tử xoay.
Theo các công thức (2.10), (2.11), (2.14), bảng đơn hình mới suy được từ bảng
đơn hình cũ bằng cách thay cr , Ar trong hàng xoay bằng cs , As . Sau đó thực hiện các
phép biến đổi dưới đây:
1) Chia mỗi phần tử ở hàng xoay cho phần tử trục, kết quả thu được gọi là hàng
chuẩn.
2) Đối với các hàng còn lại thực hiện biến đổi theo công thức

Hàng mới = hàng cũ tương ứng – Hàng chuẩn × phần tử xoay.
Toàn thể phép biến đổi trên gọi là phép quay xung quanh trục zrs . Sau khi thực
hiện phép xoay ta có một phương án mới và một cơ sở mới, tiến hành kiểm tra điều
kiện tối ưu.
1.3.2 Thuật toán đơn hình mở rộng
Xét bài toán

-11-


(I)

n

f
(
X
)
=
c j x j ⇒ min
∑

j =1

 n
∑ aij x j = bi , (i = 1...m)
 j =1
 x ≥ 0, ( j = 1...n)
 j



Ta đưa thêm vào một số ẩn cơ sở mới xn +1,..., xn + m và chuyển bài toán về dạng

(II)

n
m
 *
f
(
X
)
=
c
x
+
M
xn +i ⇒ min
∑
∑
j j

j =1
i =1

 n
∑ aij x j + xn +i = bi , (i = 1...m)
 j =1
 x ≥ 0, ( j = 1...m + n)
 j



Trong đó M là một số dương đủ lớn, các biến xn +i gọi là biến giả (như vậy bài
toán M có n + m biến). Lúc này bài toán (II) là dạng chính tắc có thể áp dụng phương
pháp đơn hình để giải.
Một số chú ý
*
+ Ta thấy rằng giá trị hàm mục tiêu f * và các số kiểm tra ∆ j là hàm bậc nhất
*
đối với M theo dạng aM + b . Vì M > 0 đủ lớn cho nên dấu của ∆ j phụ thuộc vào dấu
*
*
hệ số a . nếu a < 0 ⇔ ∆ j < 0 và a > 0 ⇔ ∆ j > 0 . Vì vậy khi lập bảng đơn hình ta sẽ tách

dòng m + 1 thành hai dòng (m + 1) và (m + 2) . Số a và b lần lượt điền vào dòng
(m + 2) và (m + 1) khi phải lập bảng mới sẽ chọn cột khóa dựa vào số dương lớn nhất ở

dòng (m + 2) , sau đó so sánh đến số ở dòng (m + 1) .
+ Khi viết bài toán M , cho bài toán gốc. Nếu bài toán gốc đã có một số véc tơ
đơn vị thì ta chỉ cần thêm một số biến giả sao cho nó có đủ m véc tơ đơn vị.
+ Dòng khóa vẫn chọn như cũ, khi sang bảng mới nếu một véc tơ giả bị loại
khỏi cơ sở thì các số liệu trên cột chứa véc tơ giả đó không phải tính nữa. Nếu như tất
cả các véc tơ giả bị loại khỏi cơ sở thì phương án nhận được lúc đó chính là phương án
cực biên của bài toán gốc và dòng (m + 2) không cần đến nữa. Việc giải bài toán tiếp
tục bình thường.

-12-


+ Đối với bài toán max, nếu giải trực tiếp thì ta sẽ thêm − M vào hàm mục tiêu.

Trên cơ sở lý thuyết trên, thuật toán đơn hình tổng quát được mô tả bằng sơ đồ
khối sau đây:

Hình 1.1: Sơ đồ khối thuật toán đơn hình
Thuật toán đơn hình có thể thực hiện trên máy tính điện tử thông qua một phần
mềm tính toán. Với những bài toán QHTT có biến số quá lớn (như dạng bài toán vận
tải), trong thực tế không thể giải bằng phương pháp đơn hình được, lúc này người ta sử
dụng 1 thuật toán khác được gọi là thuật toán phân phối.

-13-


1.3.3 Thuật toán phân phối
1.3.3.1 Thuật toán phân phối
Một loại hàng hoá nào đó cần được vận chuyển từ m nơi giao (trạm phát)
A1 , A2 ,..., Am với các lượng hàng dự trữ tương ứng là a1 , a2 ,..., am tới n nơi nhận

(trạm thu) B1 , B2 ,..., Bn với các yêu cầu tương ứng là b1 , b2 ,..., bn . Ký hiệu cij là cước
phí vận chuyển một đơn vị hàng hoá từ nơi giao Ai tới nơi nhận B j . Hãy xác định
những đại lượng xij cho mọi con đường ( i, j ) sao cho tổng cước phí vận chuyển là
nhỏ nhất. Bài toán được mô tả bằng bảng ma trận vận chuyển sau đây:
Nơi nhận hàng \

B1

nơi giao hàng

...

c11


Bj
c1j

A1

…

…

…
ci1

…

…

…

ai
xin

…

cmj

…

…


cmn

…

…

xm1

am

xmj
…

…

…
xij

cm1

b1

…
cin

xi1

Yêu cầu

…


…

Am

a1
x1n

cij

…

Dự trữ

…
x1j

…

Ai

Bn
c1n

x11

…

…


bj

xmn
…

bn

m

n

i =1

j =1

∑ ai = ∑ b j

Bảng 2.2: Bảng ma trận vận chuyển
Đặt xij là số đơn vị hàng hoá cần vận chuyển từ địa điểm giao Ai đến địa điểm
nhận B j . Ta luôn coi bài toán là cân bằng thu – phát, tức là tổng số hàng hoá theo khả
năng ở các nơi giao bằng tổng số hàng hoá theo nhu cầu ở các nơi nhận.
Khi đó bài toán vận tải tương đương với mô hình bài toán tối ưu sau đây:

-14-


m

n


F = ∑∑ cij xij → min
i =1 j =1

m

∑x
i =1

ij

n

∑x
j =1

ij

(2.15)

= b j ( j = 1...n )

(2.16)

= ai ( i = 1...m )

(2.17)

xij ≥ 0, i = 1..m; j = 1..n.
m


n

i =1

j =1

∑ ai = ∑ b j

(2.18)
(2.19)

Hệ gồm m + n phương trình đại số tuyến tính với m × n ẩn.
Trong số tất cả các nghiệm không âm của hệ (2.16) - (2.18) cần tìm một nghiệm
sao cho hàm mục tiêu (2.15) đạt giá trị nhỏ nhất.
Các tính chất của bài toán vận tải
Bài toán vận tải luôn có phương án tối ưu
Nếu bài toán không cân bằng thu - phát thì ta luôn đưa được về dạng cân bằng
bằng cách:
m

•

i

i =1

m

là


n

∑ a > ∑b

•

n

∑ a − ∑b
i =1

j =1

i

j =1

j

j

thì thành lập thêm một trạm thu giả bn +1 với lượng hàng tương ứng

, chi phí là ci ,n +1 = 0, (∀i = 1...m) .

m

n

i =1


j =1

n

m

j =1

i =1

∑ ai < ∑ b j thì thành lập thêm một trạm phát giả am+1 với lượng hàng tương

ứng là ∑ b j − ∑ ai , chi phí là cm +1, j = 0, (∀j = 1...n)
Các véc tơ hệ số Aij ứng với các ẩn số xij có tối đa m + n − 1 véc tơ độc lập tuyến
tính trong đó véc tơ Aij có tọa độ trên dòng i và dòng m + j bằng 1, còn lại bằng 0.

-15-


Một số định nghĩa
• Ô nằm trong dòng i , cột j ký hiệu là ( i, j ) . Một ô ( i, j ) mà xij > 0 gọi là ô
chọn, các ô còn lại được gọi là ô loại.
• Một dãy các ô được gọi là dây chuyền nếu dãy ô đó có tính chất cứ 2 ô liên tục
của dãy thì cùng nằm trên một dòng (hoặc một cột). Cứ 3 ô liên tục của dãy thì không
thể cùng nằm trên một dòng (hoặc một cột).
• Chu trình (hay vòng) là một dây truyền mà ô đầu tiên và ô cuối cùng trên cùng
một dòng (hoặc một cột).
• Tập hợp tất cả các ô chọn tạo thành vòng gọi là vòng chọn.
• Vòng loại (ứng với ô loại ( i, j ) ) là một vòng trong đó chỉ có ô loại ( i, j ) các ô

còn lại là ô chọn.
• Một phương án chứa vòng chọn nào đó gọi là phương án có chu trình hay là
phương án chứa vòng. Một phương án không chứa chu trình nào gọi là phương án
không có vòng.
Định lí 2.3: Điều kiện cần và đủ để một dãy ô chứa vòng là hệ véc tơ Aij tương
ứng phụ thuộc tuyến tính.
Hệ quả:
1. Một dãy ô không chứa vòng ⇔ Hệ véc tơ tương ứng độc lập tuyến tính.
2. Một phương án cực biên của bài toán vận tải có tối đa m + n − 1 ô chọn.
Định nghĩa 2.2: Một phương án cực biên có đúng m + n − 1 ô chọn gọi là phương
án cực biên không suy biến.
3. Bất kỳ m + n ô trở lên đều chứa vòng.
Định lí 2.4: Nếu tập E gồm m + n − 1 không tạo thành vòng, khi thêm một ô không
thuộc tập E vào tập E ta sẽ được một vòng duy nhất.
Hệ quả: Giả sử tập ô tạo thành vòng duy nhất thì khi bỏ đi một ô, các ô còn lại
không tạo thành vòng.

-16-


1.3.3.2 Thuật toán phân phối
Giả sử ta có một phương án cực biên không suy biến X 0 , xét một vòng loại ứng
với ô loại ( i, j ) , bắt đầu từ ô loại ( i, j ) ta đánh số thứ tự 1,2,…
• Tập các ô có số thứ tự lẻ gọi là nửa vòng lẻ Vl .
• Tập các ô có số thứ tự chẵn gọi là nửa vòng chẵn Vc .
Như vậy số ô của Vl bằng số ô của Vc .
Số kiểm tra của ô loại ( i, j ) là:
∆ ij =

∑


( i , j )∈Vl

cij −

∑

( i , j )∈Vc

cij

Định lí 2.5:
+ Nếu với mọi ô loại ( i, j ) ta đều có ∆ ij ≥ 0 thì X 0 là phương án tối ưu.
+ Nếu tồn tại một ô loại ( i, j ) mà ∆ ij < 0 thì X 0 chưa tối ưu và có phương án mới
tốt hơn.
1.3.3.3 Sơ đồ mô tả thuật toán phân phối

-17-


Bắt đầu

Tìm x0

Tính cho các ô loại (i,j)

,

Tìm x mới
False

True

e

Ghi nhận phương
án tối ưu

Kết thúc
Hình 1.2: Sơ đồ thuật toán phân phối
Điều kiện của phương án X 0 là có m + n − 1 ô chọn không tạo thành vòng.
Thuật toán phân phối được thực hiện theo các bước như sau
Bước 1: Xác định phương án cực biên không suy biến ban đầu X 0
Sử dụng 1 trong 3 phương pháp sau đây
1) Phương pháp góc tây bắc:
Xây dựng nghiệm chấp nhận được của bài toán bắt đầu bằng việc chuyên chở lớn
nhất có thể được từ điểm phát thứ nhất tới điểm thu thứ nhất (do đó được gọi là
phương pháp góc tây bắc) tức là xij = min { a1 , b1} . Quá trình lặp lại theo đúng quy
tắc như vậy cho đến khi phân phối xong.
2) Phương pháp cực tiểu cước phí:

-18-


Xác định ô (i0 , j0 ) với ci , j = min { ci , j , ∀(i, j )} . Nếu cực tiểu đạt tại nhiều ô thì ta
0

0

chọn một ô theo quy tắc từ vựng. Sau đó phân phối hàng nhiều nhất có thể được
theo tuyến i0 → j0 một lượng: xi , j = min { ai , b j } . Quá trình lặp lại cho đến khi

0

0

0

0

phân phối xong.
3) Phương pháp Fogel
Định nghĩa 2.3: Hiệu giữa giá trị cước phí nhỏ thứ nhì và nhỏ nhất trên cùng một
cột (hoặc một dòng) được gọi là độ lệch của cột (dòng).
Để tìm phương án ban đầu ta làm như sau:
• Chọn cột (dòng) có độ lệch lớn nhất ưu tiên phân phối trước, phân phối tối đa
vào ô có cước phí min của cột (dòng) đã chọn (đối với bài toán max, độ lệch là cước
phí lớn nhất và lớn nhì).
• Lặp lại quá trình
Bước 2: Tính các số kiểm tra
Thực hiện theo phương pháp quy không ô chọn: Chọn các số ri , s j sao cho đối với
các ô chọn thì cij + ri + s j = 0 . Khi đó số kiểm tra của các ô loại lúc này là cij + ri + s j
.
Nếu tồn tại một số kiểm tra bằng 0, mọi số kiểm tra còn lại đều dương thì bài toán
có vô số phương án tối ưu.
Bước 3: Điều chỉnh để tìm phương án mới
Giả sử ô loại ( i, j ) có số kiểm tra ∆ ij < 0 ta điều chỉnh các số liệu của các ô thuộc
vòng loại này như sau:

{ xij} . Khi đó:
Chọn θ = (min
i , j )∈V

c

'
+ xij = θ

nếu ( i, j ) là ô loại.

'
+ xij = xij − θ nếu (i, j ) ∈ Vc .

-19-


'
+ xij = xij + θ nếu (i, j ) ∈ Vl .

Khi điều chỉnh như vậy thì ô loại trở thành ô chọn và ít nhất một ô chọn trở thành
ô loại.
Quay lại bước 2.
Tương tự như thuật toán đơn hình, thuật toán phân phối cũng được thực hiện bằng
1 phần mềm tính toán trên máy tính điện tử.
Trên cơ sở các thuật toán đã trình bày, chúng ta có thể sử dụng các ngôn ngữ lập
trình cơ bản như C++, Pasal, Java để thực hiện thuật toán trên máy tính điện tử.
Một trong những phương pháp thông dụng hiện nay đối với các kĩ sư không
chuyên tin là sử dụng các phần mềm có sẵn để tìm nghiêm của các bài toán quy
hoạch tuyến tính.
Sau đây là một phương pháp sử dụng phần mềm Matlab giải bài toán quy hoạch
tuyến tính:

-20-



Chương 2:
MỘT SỐ MÔ HÌNH CƠ BẢN
Trong chương này, luận văn sẽ trình bày một số mô hình cơ bản thuật toán điều
chỉnh nhân tử giải bài toán sản xuất đồng bộ, thuật toán Hungary giải bải toán bổ
nhiệm…. là các thuật toán đặc trưng trong ngành Công nghệ thông tin.

2.1 Bài toán sản xuất đồng bộ
2.1.1 Bài toán sản xuất đồng bộ
Giả sử có một số loại máy cùng tham gia vào một qui trình sản xuất các chi tiết
cho một loại sản phẩm nào đó. Năng suất của các máy khi sản xuất các chi tiết khác
nhau cũng khác nhau. Bài toán đặt ra là: phải bố trí công việc cho các máy trong một
đơn vị thời gian sao cho việc sản xuất được “ đồng bộ” để đạt được hiệu quả cao nhất,
sản xuất ra nhiều sản phẩm nhất.
Bài toán được đặt ra với giả thiết: Mỗi loại máy chỉ có một cái và mỗi sản phẩm
chỉ cần đúng một chi tiết cho mỗi loại. (một đơn vị thời được hiểu là một ca làm việc.)
Với mọi n ∈ ¥ * , ký hiệu: I n = { 1, 2,..., n} .
2.1.2 Mô hình bài toán sản xuất đồng bộ tổng quát
Có m loại máy M i , (i ∈ I m ) , mỗi loại một cái, sản xuất ra n loại chi tiết
C j , ( j ∈ I n ) của một loại sản phẩm. Mỗi sản phẩm chỉ cần một chi tiết của mỗi loại.

Biết ma trận năng suất ( aij ) m×n , trong đó aij là năng suất trong một ca của máy M i khi
sản xuất loại chi tiết C j . Yêu cầu lập kế hoạch phân công hoạt động cho các máy sao
cho số sản phẩm được sản xuất ra là nhiều nhất.
Số lượng chi tiết j sản xuất được trong một ca là:

-21-



m

z j = ∑ aij xij
i =1

Với mọi i ∈ I m và j ∈ I n , đặt xij là phần thời gian trong một ca mà máy M i dùng
để sản xuất chi tiết C j , và z là số sản phẩm được sản xuất ra trong một ca.
Ký hiệu vectơ ( x11 , x12 ,..., xm1 ,..., xmn , z ) là ( xij , z ) , i ∈ I m , j ∈ I n .
Mô hình toán học:
Tìm: ( xij , z ) , i ∈ I m , j ∈ I n sao cho: z → max
 n
∑ xij = 1, i ∈ I m
 j =1
 m
 −∑ aij xij + z ≤ 0, j ∈ I n
 i =1
 xij ≥ 0, ( i, j ) ∈ I m × I n

 z ≥ 0

(2.20)

Đây là một bài toán quy hoạch tuyến tính. Ký hiệu Aij và Az theo thứ tự là các
vectơ cột trong ma trận điều kiện ứng với các ẩn xij và z . Như vậy Aij có thành phần
thứ i bằng 1 và thành phần thứ m + j bằng − aij ; Az có m thành phần đầu bằng 0 còn
n thành phần cuối đều bằng 1.

Bài toán có thể được biểu diễn dưới dạng bảng m hàng và n cột, như bài toán
vận tải. Mỗi hàng đặc trưng cho một loại máy, mỗi cột đặc trưng cho một loại chi tiết.
Ô ( i, j ) đặc trưng cho việc sử dụng máy i để sản xuất chi tiết j nên ô này ghi năng

suất aij tương ứng (bảng 2.3):
Chi tiết

C1

Máy

…

Cm-1

Cm

M1

a11

…

a1m-1

a1m

M2

a21

…

a2m-1


a2m

…

…

…

…

…

-22-


Mn

an1

…

anm-1

anm

Bảng 2.1: Các tham số của bài toán
Do đó bảng này còn được gọi là bảng năng suất của bài toán sản xuất đồng bộ.
Các tính chất của bài toán:
1) Vectơ ( xij , z ) , i ∈ I m , j ∈ I n thoả mãn tất cả các ràng buộc của bài toán là một

phương án của bài toán. Tuy nhiên, bất kỳ vectơ ( xij ) nào thoả mãn các ràng buộc của
bài toán cũng cho tương ứng một họ phương án với thành phần z được xác định bởi:
0 ≤ z ≤ min z j
j∈I n

Với:
m

z j = ∑ aij xij ( j ∈ I n )
i =1

Trong số đó, rõ ràng phương án có

z = min z j
j∈I n

là tốt hơn cả. Vì vậy từ nay ta sẽ

gọi vectơ ( xij ) , i ∈ I m , j ∈ I n , hoặc ma trận ( xij ) m×n thoả mãn các ràng buộc của bài toán
(SXĐB) là một phương án của bài toán với quy ước là thành phần z của nó bằng:
m

min ∑ aij xij .
j∈J

i =1

2) Hàm mục tiêu của một bài toán sản xuất đồng bộ luôn bị chặn trên trong
miền ràng buộc của nó, vì với mọi phương án ( xij ) của bài toán:
m


m

i =1

i =1

z ≤ ∑ aij xij ≤ ∑ aij
1
n

'
'
Ngoài ra, rõ ràng vectơ ( xij ) với xij = , ∀ ( i, j ) ∈ I m × J là một phương án của

bài toán. Vậy, bài toán luôn giải được.

2.2 Phương pháp điều chỉnh nhân tử

-23-


Nếu tìm được một phương án ( xij , z ) của bài toán và một phương án ( ui , v j ) của
bài toán đối ngẫu sao cho:

 xij . ( ui − aijv j ) = 0, ( i. j ) ∈ I m × I n

  n

 z.  ∑ v j − 1 ÷ = 0


  j =1
 
m
v j .  z − ∑ aij xij ÷ = 0, j ∈ I n
 
i =1


{

(2.21)

thì ( xij , z ) là một phương án tối ưu của bài toán và ( ui , v j ) là một phương án tối ưu của
bài toán đối ngẫu.
Nội dung của phương pháp điều chỉnh nhân tử như sau:
Trước hết, chúng ta xây dựng một phương án cực biên suy rộng ( ui , v j ) của bài
toán, đó là một hệ thống nhân tử hàng và nhân tử cột; đồng thời xác định các ô chọn.
Gọi S là tập ô ( i, j ) tương ứng với m + n − 1 ràng buộc chặt độc lập tuyến tính dạng
ui − aijv j = 0 . Các ô thuộc S được lấy làm các ô chọn, nên S được gọi là tập ô chọn của

phương án cực biên suy rộng ( ui , v j ) .

2.2.1 Thuật toán điều chỉnh nhân tử:
Bước 1: Xây dựng hệ thống nhân tử ( ui , v j ) (hay phương án cực biến suy rộng của bài
toán đối ngẫu:
aij . Đặt: v j = 1 và
Trước hết, xác định ô ( i, j ) có aij lớn nhất. Giả sử: ai j = max
i, j
0 0


0

ui0 = ai0 j0 .v j0 . Ô ( i0 , j0 ) được lấy làm ô chọn và được đánh dấu. Các nhân tử còn lại được

xác định như sau:
- Trên hàng i đã có nhân tử ui , tìm ô có năng suất lớn nhất nằm trên cột j chưa
u

i
) trong đó min lấy với
có nhân tử. Nhân tử của cột này được xác định bởi: v j = min(
i
a
ij

-24-


mọi hàng i đã có nhân tử. Ô tương ứng với nhân tử v j đó được lấy làm ô chọn và được
đánh dấu.
- Trên cột j đã có nhân tử v j , tìm ô có năng suất lớn nhất nằm trên hàng i chưa
aijv j / với mọi cột j đã
có nhân tử. Nhân tử của hàng này được xác định bởi: ui = max(
j

có nhân tử ) Ô tương ứng nhân tử ui đó được lấy làm ô chọn và được đánh dấu.
Tiếp tục quá trình trên cho đến khi xây dựng được toàn bộ hệ thống nhân tử.
Như vậy, trừ ô chọn ( i0 , j0 ) đầu tiên tương ứng với hai nhân tử ui và v j ; sau đó, mỗi
0


0

lần xây dựng được một nhân tử thì đồng thời cũng xác định được một ô chọn. Do đó,
tổng số các ô chọn là m + n − 1 , và hiển nhiên chúng không tạo thành vòng.
Ký hiệu tập ô chọn là S, ta có:
∀i ∈ I m , ∀j ∈ I n , ui − aijv j ≥ 0

∀ ( i, j ) ∈ S , ui − aijv j = 0
 n

∑ v j ≥ 1
 j =1
∀j ∈ I n , v j ≥ 0

( u ,v )
i

j

(2.22)

vừa tìm được là một phương án cực biên suy rộng của bài toán đối ngẫu.

Bước 2: Xây dựng giả phương án ( xij , z ) :
m

z=

∑u

i =1
n

∑v
j =1

i

j

Các xij được tính nhờ vào giá trị của z và hệ phương trình:
 n
∑ xij = 1, i ∈ I m
 j =1
 m
∑ aij xij = z , j ∈ I n
 i =1
 xij = 0, ( i, j ) ∉ S



-25-

(2.23)