ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

ĐINH QUANG NGỌC

MỘT PHƯƠNG PHÁP XẤP XỈ TRONG
GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN PHÂN TUYẾN TÍNH
THEO PHƯƠNG PHÁP NHÁNH CẬN VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - 2015


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

ĐINH QUANG NGỌC

MỘT PHƯƠNG PHÁP XẤP XỈ TRONG
GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN PHÂN TUYẾN TÍNH
THEO PHƯƠNG PHÁP NHÁNH CẬN VÀ ỨNG DỤNG

Chuyên ngành: Toán ứng dụng
Mã số:

60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học:

Bài toán vận tải phân tuyến tính . . . . . . . . . . . . .

4

1.1.2

Bài toán cực tiểu giá thành sản phẩm . . . . . . . . . .

4

1.1.3

Bài toán cực đại hiệu suất tiêu diệt mục tiêu địch . . . .

5

Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ
bất phương trình tuyến tính và một vài tính chất của nó . . . . .
1.2.1
1.2.2

6

Bài toán quy hoạch phân tuyến tính với miền ràng buộc
là hệ bất phương trình tuyến tính . . . . . . . . . . . . .

6

Một vài tính chất của bài toán quy hoạch phân tuyến
tính với miền ràng buộc là hệ bất phương trình tuyến tính

hoạch phân tuyến tính . . . . . . . . . . . . . . . . . . 23

1.4

Bảng lặp giải bài toán quy hoạch phân tuyến tính bởi thuật toán
PTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.5

Thuật toán nón xoay tìm một nghiệm của hệ bất phương trình
tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5.1

Thuật toán nón xoay tìm một nghiệm của hệ bất phương
trình tuyến tính với cơ sở xuất phát từ gốc toạ độ là đỉnh
của nón Rn+ . . . . . . . . . . . . . . . . . . . . . . . . 31

1.5.2

Bảng lặp tìm một nghiệm của hệ bất phương trình tuyến
tính với cơ sở xuất phát từ gốc toạ độ là đỉnh của nón Rn+ 32

2

Thuật toán nhánh cận xấp xỉ trong giải bài toán quy hoạch nguyên
phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến
tính và ứng dụng
2.1

34



iii

Lời cam đoan
Tôi xin cam đoan đây là công trình nghiên cứu của tôi.

Thái Nguyên, ngày 20 tháng 04 năm 2015
Học viên

Đinh Quang Ngọc


1

Mở đầu
Nhiều bài toán thực tế trong kinh tế cũng như trong toán học, thường gặp
trong lý thuyết trò chơi, trong công nghiệp hóa chất, trong cắt nguyên vật liệu,
trong mạng vận tải và trong định giá thành sản phẩm, . . . dẫn đến chúng ta
phải đi giải các bài toán quy hoạch nguyên phân tuyến tính. Một phương pháp
hiệu quả thường sử dụng để giải bài toán này đó là phương pháp nhánh cận
Land-Doig.
Để giải bài toán quy hoạch nguyên phân tuyến tính thông thường là chúng ta
phải tiến hành giải các bài toán quy hoạch phân tuyến tính tương ứng khi chưa
có điều kiện nguyên của biến với các ràng buộc bổ sung dạng bất phương trình
cho các thành phần của biến. Rõ ràng khi sử dụng phương pháp nhánh cận để đi
tìm các cận dưới tốt hơn (đối với bài toán min) cho bài toán quy hoạch nguyên
thì ta thường phải giải các bài toán tương ứng khi chưa có điều kiện nguyên
với miền ràng buộc được bổ sung thêm sau mỗi bước một ràng buộc dạng bất
phương trình đối với thành phần chưa nguyên của biến.

3

Chương 1

Bài toán quy hoạch phân tuyến tính với miền
ràng buộc là hệ bất phương trình tuyến tính và
thuật toán giải
Như chúng ta đã biết, nhiều bài toán thực tế trong kinh tế cũng như trong
toán học, thường gặp trong lý thuyết trò chơi, trong công nghiệp hóa chất, trong
cắt nguyên vật liệu, trong mạng vận tải và trong định giá thành sản phẩm, . . .
đều có mô hình toán học dạng các bài toán quy hoạch nguyên phân tuyến tính.
Vì vậy nội dung của chương này sẽ giới thiệu một số mô hình thực tế có dạng
bài toán này và sau đó trình bày thuật toán xấp xỉ trong giải bài toán quy hoạch
phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính, làm cơ sở
để xây dựng thuật toán giải bài toán quy hoạch nguyên phân tuyến tính với miền
ràng buộc là hệ bất phương trình tuyến tính trình bày trong chương 2.

1.1

Một số bài toán thực tế đưa về bài toán quy hoạch phân
tuyến tính và quy hoạch nguyên phân tuyến tính

Sau đây chúng ta trình bày một số mô hình bài toán thực tế có dạng bài toán
quy hoạch phân tuyến tính và bài toán quy hoạch nguyên phân tuyến tính với
miền ràng buộc là hệ bất phương trình tuyến tính.


4

1.1.1

i=1 j=1

Chúng ta cần phải cực đại hóa (cực tiểu hóa) hàm mục tiêu trên với các điều
kiện ràng buộc sau:
n

xij

ai (i = 1, 2, ...m)

(1.2)

xij

bj (j = 1, 2, ...n)

(1.3)

j=1
m

i=1

xij

1.1.2

0, nguyên, (i = 1, 2, . . . , m) , (j = 1, 2, . . . , n)

(1.4)

có n loại (bom, tên lửa, rốc két, . . . ). Máy bay phải mang vũ khí đến đánh một
mục tiêu của địch, trọng lượng mỗi đơn vị vũ khí loại j là aj (j = 1, 2, . . . , n).
Xác suất tiêu diệt mục tiêu địch (trúng mục tiêu) của một đơn vị vũ khí loại j
là pj , số lượng vũ khí loại j có trong kho là Nj . Gọi xj là số lượng vũ khí loại j
mà máy bay cần mang. Bài toán đặt ra là máy bay cần mang mỗi loại vũ khí là
bao nhiêu để hàm hiệu suất chiến đấu dưới đây đạt cực đại:
n

pj .xj
P (x) =

j=1
n

xj
j=1

Với các ràng buộc

n

aj .xj

M

j=1

0

xj


L (x)

 f (x) = 1
→ min
L
(x)
2
(LF P )

 x ∈ P := {x ∈ Rn : < Ai , x > +b
i

0, i = 1, 2, ..., m}

trong đó
L1 (x) =< A0 , x > +b0 , L2 (x) =< C 0 , x > +d0 , A0 , Ai , C 0 , x ∈ Rn là
các vectơ dòng, A0 (a01 , a0 2, ..., a0n ), Ai (ai1 , ai2 , ..., ain ), C 0 (c01 , c02 , ..., c0n ),
là các vectơ dòng bi ∈ R1 . Hạng của hệ Ai (i = 1, 2, ..., m) bằng n, (m

n),

giả thiết này rất bình thường bởi miền ràng buộc P của bài toán quy hoạch phân
tuyến tính bao giờ cũng có ràng buộc về dấu của biến x. Giả thiết P là một đa


7
diện và L2 (x) = 0 trên P và không mất tính tổng quát giả sử L2 (x) > 0 trên P ,
L1 (x)
−L1 (x)

Định lí 1.1. Hàm f (x) =

định.
Chứng minh. Lấy x, y ∈ D xét sự thay đổi của f (x) trên đoạn thẳng nối hai
điểm x, y :
z = λx + (1 − λ)y, (0 λ 1).
λ.L1 (x) + (1 − λ) .L1 (y)
f (z) =
= L (λ) , (0
λ.L2 (x) + (1 − λ) .L2 (y)
đạo hàm theo λ:



λ

1)

dL(λ)
1  L1 (x) L1 (y) 
= 2
dλ
L2 (z) L2 (x) L2 (y)

dấu của đạo hàm phụ thuộc vào dấu của định thức. Vậy khi λ thay đổi trong
đoạn [0; 1] thì f (z) tăng hoặc giảm, hoặc giữ nguyên giá trị bằng hằng số.


8
Tính tái tối ưu hóa của bài toán LFP

, ∀i ∈ I∗ . Bây giờ ta
∗

thêm vào miền ràng buộc PT của bài toán (T ) ràng buộc sau:
< AN +1 , x > +bN +1

0.

(1.5)

Khi đó nếu xM∗ thoả mãn (1.5) thì nó cũng là một lời giải của bài toán (T ) có
thêm ràng buộc bổ sung (1.5), nếu ngược lại mà
< AN +1 , xM∗ > +bN +1 > 0.

(1.6)

Thì chúng
 ta gọi bài toán sau đây là bài toán tái tối ưu hoá của bài toán (T ):
L1 (x)


f (x) =
→ min
L2 (x)
(T∗ )

 x ∈ PT = x ∈ Rn :< Ai , x > +bi 0, i = 1, 2, . . . , m
trong đó m = N + 1



< AN +1 , x1 > +bN +1 < 0,
và do xM∗ không phải là phương án của bài toán (T∗ ) tức ta có (1.6).
< AN +1 , x1 > +bN +1
Gọi α1 =
(< AN +1 , xM∗ > +bN +1 ) − (< AN +1 , x1 > +bN +1 )

(1.7)


10
Và
(1.8)

x(α1 ) = α1 xM∗ + (1 − α1 )x1
Dễ dàng kiểm tra thấy:

(1.9)

< AN +1 , x(α1 ) > +bN +1 = 0.

Lại từ (1.6), (1.7) dễ dàng thấy α1 ∈ (0, 1) và vì xM∗ , x1 tương ứng là phương
án của các bài toán (T ) và (T∗ ) nên ta có:
< Ai , x(α1 ) > +bi = α1 [< Ai , xM∗ > +bi ]+(1−α1 )[< Ai , x1 > +bi ]

0,

∀i = 1, 2, ..., N
Hay
< Ai , x(α1 ) > +bi



11
tuyến tính trong Rn , thì khi biết một phương án cực biên chấp nhận được của nó
chúng ta có thể giải bài toán bằng thuật toán tương tự như thuật toán đơn hình
(xem [2] , [8]). Sau đây chúng ta từ khái niệm nón xoay tuyến tính trình bày trong
[5], xây dựng một thuật toán xấp xỉ trong giải trực tiếp bài toán quy hoạch phân
tuyến tính dạng chuẩn với các ràng buộc chính là hệ bất phương trình tuyến tính
trong Rn . Rõ ràng việc giải trực tiếp bài toán quy hoạch với các ràng buộc chính
của miền chấp nhận được là hệ bất phương trình tuyến tính có những ưu điểm
là giải bài toán khi các ràng buộc chính của miền chấp nhận được là hệ phương
trình tuyến tính, bởi vì như vậy số chiều bài toán không tăng lên do phải thêm
vào các biến bù.

1.3.1

Khái niệm về nón đơn hình tuyến tính

Xét tập M xác định từ n ràng buộc tuyến tính của P , cụ thể là:
M := {x ∈ Rn :< Ai , x > +bi

0, i ∈ IM }

(1.12)

trong đó IM := {i1 , i2 , ..., in } ⊂ {1, 2, ..., m}, |IM | = n (ở đây |IM | là số đo hay
là số phần tử của tập IM ) và Ai với i ∈ IM là một hệ độc lập tuyến tính. Tập
M gọi là nón đơn hình tuyến tính của hệ ràng buộc P với đỉnh xM là nghiệm
(được xác định) thoả mãn hệ sau:
< Ai , x > +bi = 0, ∀i ∈ IM



 < Ar , z i >= 0, ∀r ∈ IM , r = i
M

(1.15)

 < Ai , z i >= −1
M
gọi là vectơ chỉ phương của cạnh i của nón M .

Đỉnh xM của nón M có thể xác định từ (1.13), trong trường hợp biết hệ
i
vectơ chỉ phương zM
(i ∈ IM ) thì chúng ta có thể sử dụng công thức sau:

xM =

(1.16)

i
bi .zM
i∈IM

Định lí 1.2. Nếu xM là đỉnh của nón đơn hình M được xác định từ (1.13), và
i
hệ vectơ chỉ phương zM
(i ∈ IM ) của cạnh i của nón M xác định từ (1.15) thì

chúng ta có thể xác định đỉnh xM từ công thức sau:
xM =

(Vì zM
thoả mãn (1.15) ) Mặt khác do hệ Ai (∀i ∈ IM ) là hệ độc lập tuyến

tính nên nghiệm của hệ (1.13) là duy nhất, suy ra ta có công thức (1.16) Vậy từ
i
định lí 1.2.1 ta suy ra trong trường hợp biết hệ vectơ chỉ phương zM
(i ∈ IM ) thì


13
chúng ta có thể xác định đỉnh xM từ công thức sau:
xM =

i
bi .zM
i∈IM

Dễ thấy tập các điểm x nằm trên cạnh i của nón M đều có thể biểu diễn như
sau:
x = xM + λi , λi

(1.17)

0, ∀i ∈ IM

i
với i ∈ IM là một hệ độc lập tuyến tính.
Định lí 1.3. Hệ vectơ chỉ phương zM

Chứng minh. Ta chứng minh bằng phản chứng, giả sử ngược lại hệ vectơ chỉ


Định lí 1.4. Với mỗi x bất kỳ thuộc nón đơn hình M , luôn có biểu diễn duy nhất
x = xM +

i
λi .zM
, λi

0, ∀i ∈ IM .

i∈IM

Ngược lại mọi điểm x = xM +

i
αi .zM
, αi

0, ∀i ∈ IM đều thuộc nón

i∈IM

M.
i
Chứng minh. Vì hệ vectơ chỉ phương zM
với i ∈ IM là một hệ độc lập tuyến

tính nên tồn tại bộ số duy nhất λi (∀i ∈ IM ), sao cho ta có biểu diễn:
x − xM =



0

i∈IM
r
⇔λr . < Ar , zM
>

0 ⇔ λr

0, ∀r ∈ IM .

Điều ngược lại ta dễ dàng thay biểu diễn của x vào các ràng buộc tương ứng xác
định nón đơn hình M để kiểm tra và thấy thoả mãn.
Từ định lí này, chúng ta có thể định nghĩa khác về nón đơn hình M như sau:
1
2
Định nghĩa 1.1. Cho trước một điểm xM và n vectơ độc lập tuyến tính zM
, zM
,
n
..., zM
. Tập M :=

x ∈ Rn : x = x M +

n

i
αi .zM

Nếu xM ∈ P tức là:
< Ai , xM > +bi

0, ∀i = {1, 2, . . . , m}

thì nón đơn hình tuyến tính M gọi là nón đơn hình tuyến tính chấp nhận được
của P hay còn gọi là nón đơn hình chấp nhận được của P . Vậy nếu nón đơn
hình chấp nhận được của P là không thoái hóa thì ta có
< Ai , xM > +bi < 0, ∀i = {1, 2, . . . , m} \IM

(1.20)


15
Bài toán quy hoạch phân tuyến tính (LF P ), gọi là không thoái hóa nếu tất cả
các đỉnh của các nón đơn hình chấp nhận được của P là không thoái hóa. Từ
nay về sau ta giả thiết bài toán (LF P ) là bài toán không thoái hóa. Giả sử M là
một nón đơn hình chấp nhận được của P nó được xác định bởi (1.12) Ta gọi:
JM := {j ∈ {1, 2, ..., m} : j ∈ IM }

(1.21)

J xM := j ∈ {1, 2, ..., m} :< Aj , xM > +bj = 0

(1.22)

Rõ ràng J xM ⊂ JM và IM ∪ JM = {1, 2, ..., m}
i
>= 0}
Với mỗi i ∈ IM ta gọi JM (i) := {j ∈ JM :< Aj , zM

∀j ∈ JM (r) ta có JM
(r) = ∅, tức là
r
< Aj , zM
>

0, ∀j ∈ JM

(1.23)

r
Mặt khác zM
là nghiệm của (1.15) nên ta có: ∀j ∈ IM và j = r thì
r
< Aj , zM
>= 0

(1.24)


16
Còn với j = r thì
(1.25)

r
< Ar , zM
>= −1

Từ (1.23),(1.24) và (1.25) với chú ý là IM ∪ JM = 1, 2, ..., m. Ta có:
r

Ta gọi S(i) :=

αij . Rõ ràng nếu nón M là một nón chấp nhận
s : αis = min
+
j∈IM (i)

được của bài toán (LF P ) thì < Aj , xM > +bj
0

0, ∀s ∈ S(i) ta có

+
αij , ∀j ∈ JM
(i)

αis

(1.27)

Định lí 1.7. Nếu xM là một điểm chấp nhận được của P thì ∀i ∈ IM , ∀s ∈ S(i)
i
điểm xsl = xM + αis .zM
cũng là một điểm chấp nhận được của P .

Chứng minh. Từ (1.27) ta có: 0
⇔−

αis


i
s
< A , zM >
< Aj , xM > +bj < As , xM > +bs
j i
−
=< A , zM >
i >
i >
< Aj , zM
< As , zM
j

M

(1.29)
Từ (1.28) nên
< Aj , xM > +bj < As , xM > +bs
−
i >
i >
< Aj , zM
< As , zM

0

(1.30)

+
i

Với ∀j ∈ IM và j = i thì
i
< Aj , xsi > +bj =< Aj , xM + αis .zM
> +bj
i
=< Aj , xM > +bj + αis < Aj , zM
>

=0

(1.33)

Với j = i thì
i
< Ai , xsi > +bi =< Ai , xM + αis .zM
> +bi
i
=< Ai , xM > +bi + αis < Ai , zM
>

= 0 + (−αis )
0
Từ (1.31), (1.32), (1.33) và (1.34) ta dễ dàng kết luận:

(1.34)


18
0, ∀j = 1, 2, ..., m Điều này chứng tỏ xsi là một điểm



Xác định một nón đơn hình tuyến tính gọi là nón xoay M (r, s) đỉnh là:
(1.36)

r
xM (r,s) = xsr = xM + αrs .zM

< As , xM > +bs
=−
trong đó xác định từ (3.b):
i >
< As , zM
đỉnh xsr thỏa mãn: < Ai , xsr > +bi = 0, ∀i ∈ IM (r, s) = (IM ∪ {s} \ {r}) .
αrs

αis

Tập chỉ số cơ sở mới IM (r, s) nhận được từ tập chỉ số cơ sở cũ IM bằng cách
loại chỉ số r ra khỏi tập cơ sở cũ, đưa chỉ số s vào thay. Ta nói nón xoay M (r, s)
sinh ra từ nón M .
Bổ đề 1.1. Hệ Ai với i ∈ IM (r, s) là một hệ độc lập tuyến tính.
Chứng minh. Thật vậy, nếu ngược lại hệ Ai với i ∈ IM (r, s) là phụ thuộc tuyến
tính thì dễ dàng suy ra tồn tại biểu diễn:
As =

r
βi .Ai =< As , zM
>=


xác định từ (1.15) với tập chỉ số cơ sở mới IM (r, s), hoặc xác định từ một trong
r
i
(xác định từ (1.15)) với i, r
, zM
các công thức đơn giản dưới đây theo các zM

thuộc IM là tập chỉ số của cơ sở cũ:

i
0


zM
khi i ∈ IM




i
 i
> r
< As , zM
i
z
−
.zM khi i ∈ I s , i = r
M
zM (r,s) =

các cạnh xác định theo (1.7), ∀i ∈ IM đường thẳng x = xM + αi .zM
cắt siêu

phẳng < As , x > +bs = 0 tại các giao điểm xsi xác định theo (1.a), (1.b). Khi
đó nón xoay mới M (r, s) có đỉnh là xM (r,s) = xsr xác định từ (1.36) với cơ sở
tương ứng là IM (r, s) = (IM ∪ {s} \ {r}) và các vectơ chỉ phương của các
i
cạnh tương ứng là zM
(r,s) được xác định bởi (1.37).

Chứng minh. Ta có với mỗi i ∈ IM thì:
i
< Aj , zM
>= 0, ∀j ∈ IM , j = i

(1.38)

i
< Ai , zM
>= −1

(1.39)

Ta cần phải chứng minh với mỗi i ∈ IM (r,s) thì:
i
< Aj , zM
(r,s) >= 0, ∀j ∈ IM (r,s) , j = i
i
< Ai , zM
(r,s) >= −1

>=
=< Ai , zM
. < Ai , zM
M
(r,s)
s
αi
Tóm lại ta có:
i
s
, i = r: < Aj , zM
+ i ∈ IM
(r,s) >= 0, ∀j ∈ IM (r,s) , j = i
i
+ < Ai , zM
(r,s) >= −1
s
)
(chú ý αis = 0, vì s ∈ JM (r) và i ∈ IM

2) Với i = s ta chứng minh như sau:
Ta có ∀j ∈ I (r, s) , j = s :
1
1
r
j r
z


Tóm lại ta có: với mỗi i ∈ IM (r, s) thì:
i
< Aj , zM
(r,s) >= 0, ∀j ∈ IM (r,s) , j = i
i
< Ai , zM
(r,s) >= −1

Bổ đề đã được chứng minh.
Giả sử f (x) là hàm phân tuyến tính của bài toán (LF P ), ta có định lí sau:
Định lí 1.8. ∀x, xi (i = 1, 2, ..., N ) ∈ P và f (x)

f xi (i = 1, 2, ..., N ) thì

N

f (x)

N
i

f

αi x
i=1

, ∀αi

0,