Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
BÙI QUỐC ĐỘ

MỘT PHƢƠNG PHÁP XẤP XỈ TRONG
GIẢI BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH

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: TS . NGUYỄN ANH TUẤN Thái Nguyên – 2014
Số hóa bởi Trung tâm Học liệu

Mục lục
TT
Nội dung
Trang
1
Mở đầu

10
2.2. Thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính

20
11
Chương 3:Phương pháp nón xoay xấp xỉ trong giải bài toán quy hoạch phân
tuyến tính
28
12
3.0. Bổ trợ
28
13
3.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
30
14
3.2.Khái niệm về nón đơn hình tuyến tính, cạnh và phương của cạnh
32
15
3.3. Bảng lặp nón xoay giải bài toán quy hoạch phân tuyến tính bởi thuật toán
PTT
47
16
3.4. Nhận xét về độ phức tạp tính toán của thuật toán nón xoay PTT và kết luận
56
17
Tài liệu tham khảo
58
chuẩn và quy hoạch phân tuyến tính cùng với một số khái niệm và tính chất của
hàm gần lồi-gần lõm mà các hàm tuyến tính và phân tuyến tính đều thuộc lớp hàm
đăc biệt này.
Số hóa bởi Trung tâm Học liệu

Chương 2 trình bày thuật toán nón xoay tuyến tính[1] giải trực tiếp bài toán quy
hoạch tuyến tính dạng chuẩn khi biết một nón-min của hàm mục tiêu bài toán và
thuật toán kiểu đơn hình 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ệ phương trình tuyến tính[6].
Chương 3 dựa trên khái niệm nón xoay xây dựng 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 với miền ràng buộc là hệ bất phương
trình tuyến tính và các ví dụ bằng số minh hoạ cho thuật toán. Trong trường hợp
đặc biệt mẫu số của hàm mục tiêu bài toán đồng nhất bằng một thì hàm mục tiêu
bài toán trở thành hàm tuyến tính và thuật toán đề nghị trở thành một thuật toán
giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn tổng quát.
Thuật toán nón xoay này thuộc lược đồ xấp xỉ trong giải bài toán quy hoạch
phân tuyến tính khi biết một điểm chấp nhận được của miền ràng buộc là hệ bất
phương trình tuyến tính. Nó được xây dựng chi tiết, các bước của thuật toán được
trình bày sao cho chúng ta có thể dễ dàng lập trình chuyển sang các chương trình
trên máy tính bằng các ngôn ngữ như Pascal, C, Java,
Luận văn này hoàn thành dựa trên các cuốn sách “Quy hoạch gần lồi - gần lõm
ứng dụng vào quy hoạch tuyến tính” [2] và cuốn “Quy hoạch tuyến tính với
phương pháp nón xoay” [1] và trên các sách, tài liệu có trong phần tài liệu tham
khảo.
Tác giả
Bùi Quốc Độ


ii
D x X g x b i m
(1.4)
Được gọi là miền ràng buộc ( hay miền chấp nhận được ) . Mỗi điểm :
12
, , ,
n
x x x x D
được gọi là một phương án ( hay một lời giải chấp nhận
được ). Một phương án
*
xD
đạt cực đại ( hay cực tiểu ) của hàm mục tiêu, cụ
thể là:
*
,f x f x x D
( đối với bài toán Max )
*
,f x f x x D
( đối với bài toán Min )
Được gọi là phương án tối ưu ( lời giải tối ưu ). Khi đó giá trị
*
fx
được gọi là
giá trị tối ưu của bài toán .
1.2. Bài toán quy hoạch tuyến tính dạng chuẩn
Số hóa bởi Trung tâm Học liệu

Bài toán qui hoạch tuyến tính sau đây gọi là bài toán quy hoạch tuyến tính dạng
chuẩn tổng quát:

) ≠ O(0,…,0) ,
C(c
1
, c
2
, …, c
n
), b
i
1

, i=1, 2, , m. Hạng của hệ A
i
(i=1, 2, …, m) bằng n, giả
thiết này rất bình thường bởi miền ràng buộc P
L
của bài toán quy hoạch tuyến tính
bao giờ cũng có ràng buộc về dấu của biến x.
Rõ ràng bài toán quy hoạch tuyến tính bất kỳ đều dễ dàng đưa về dạng trên để
giải
1.3. 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
Bài toán quy hoạch sau đây gọi là 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:
1
2
()
( ) min
()
()

,C
0
là
các véc tơ dòng , m n,A
0
(a
01
, a
02
,

…, a
0n
), C
0
(c
01
, c
02
,

…, c
0n
), A
i
(a
i1
, a
i2
, , a

b
là lượng
dự trữ tài nguyên loại i (i = 1,…,m). Gọi x
j
là lượng sản phẩm loại j (j = 1,…, n) mà
xí nghiệp sản xuất. Trong các điều kiện đã cho, hãy xác định các giá trị
j
x
(j =
1,…, n) sao cho tổng tiền lãi (hay tổng giá trị sản lượng hàng hóa) là lớn nhất với
số tài nguyên hiện có.
Mô hình toán học có dạng bài toán quy hoạch tuyến tính sau:
n
j
jj
xc
1
max

với các điều kiện
n
j
ijj
bxa
1

mi , ,1

0
j

jj
1

,0
j
x

nj , ,1

Số hóa bởi Trung tâm Học liệu

j
x
- nguyên,
nj , ,1

Đây là một bài toán quy hoạch nguyên.
1.4.3. Bài toán mua (thuê) máy bay tối ƣu:
Để mở rộng hoạt động, hãng hàng không dự định mua hoặc thuê K loại máy bay
(B777, B767, A321, A330, A320, AT7, ) ta gọi tương ứng là loại máy bay k (k=1,
2, …, K). máy bay loại k có giá mua (thuê) là c
k
và có thời gian sử dụng là T
k
năm.
Hãng đự định mua (thuê) tối đa là N máy bay trong các loại máy bay trên với số
vốn đầu tư hiện có là V , Bài toán cần giải quyết là hãng hàng không nên mua bao
nhiêu máy bay mỗi loại để tổng thời gian sử dụng là nhiều nhất?
Ta gọi x
k

Đây là một bài toán quy hoạch nguyên.
1.4.4. Bài toán định giá thành sản phẩm[6]
Giả sử p
j
là năng suất của phương pháp T
j
(j=1, 2, …, n) (tức là số lượng sản
phẩm được sản xuất trong một đơn vị thời gian), r
j
là chi phí trong một đơn vị thời
gian đối với phương pháp T
j
, x
j
là số đơn vị thời gian sản xuất theo phương pháp
T
J
. như vậy giá thành của một đơn vị sản phẩm là:
11
( ) /
nn
j j j j
jj
c x c x p x

Số hóa bởi Trung tâm Học liệu

Bài toán đặt ra là cực tiểu hàm c(x) với các ràng buộc về vật tư, lao động, kỹ
thuật, vốn, ….
1.4.5. Bài toán vận tải phân tuyến tính

Gọi x
ij
là số lượng hàng cần vận chuyển từ A
i
đến B
j
. khi đó bài toán đặt ra là:
ij ij 0
11
1
2
ij ij 0
11
()
( ) ( ) min
()
mn
ij
mn
ij
p x p
Lx
L f x
Lx
d x d

Với các ràng buộc
1
ij
i=1

gọi là tập lồi đa diện.Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất
phương trình tuyến tính :

n
, , 1, , ( ,b )
ii
ii
a x b i m a 
(1.4)
nghĩa là tập các nghiệm đúng
Ax b
với là một ma trận cấp m*n và
m
b 

Vì một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất
phương trình tuyến tính nên một tập lồi đa diện cũng là tập nghiệm của một hệ các
phương trình và bất phương trình tuyến tính :

,
i
i
a x b
, = 1,…,

, , 1, ,
i
i
a x b i p m


i
xb
.
Với mỗi
Dx
ký hiệu
I : ,
i
i
x i a x b
là tập chỉ số của những ràng
buộc thoả mãn chặt tại x.
Ký hiệu
0
I : ,
i
i
i a x b x D
. Tính chất đặc trưng của các diện ( nói
riêng, các đỉnh và cạnh ) của D được cho trong định lý sau :
Định lý 1.5.1 Một tập con khác rỗng
FD
là một diện thực sự của D khi và chỉ
khi
: , , , ,
ii
ii
F x a x b x a x b i I

Với I là một tập chỉ số sao cho

cho :
1
i
rank a I n

Tức là mọi
xT
cùng thoả mãn chặt n-1 ràng buộc độc lập tuyến tính của hệ
(1.4).
Mỗi tập lồi đa diện chỉ có một sô hữu hạn đỉnh và cạnh ( hữu hạn hay vô hạn ).
Trong
n

một đa diện lồi có
1(0 )k k n
đỉnh độc lập afin gọi là một
k – đơn hình.
Số hóa bởi Trung tâm Học liệu

Định lý 1.5.2
a) Mỗi đa diện lồi C bằng bao lồi của tất cả các đỉnh của nó C=convC hay
xC
khi và chỉ khi :
12
12
x
p
p
v v v
với mọi

i
C i p u j q
là phương của các cạnh vô hạn của C
Với tập lồi đa diện không có đỉnh thì biểu diễn trên chỉ cần các
i
vC
và các

i
u recC
.
Định lý trên cho thấy ứng với mỗi tập lồi đa diện cho trước có hai nhóm hữu
hạn véctơ, sao cho tập lồi ấy chính là tập tất cả các điểm có thể biểu diễn thành
tổng của một tổ hợp lồi của các véctơ thuộc nhóm thứ nhất và một tổ hợp tuyến
tính không âm của các véctơ thuộc nhóm thứ hai. Các véctơ trong nhóm thứ nhất
đều thuộc ,các véctơ trong nhóm thứ hai đều là các phương vô hạn của .
Ngược lại, có thể chứng minh được rằng nếu cho trươc hai nhóm hữu hạn
véctơ thì tập tất cả các điểm có thể biểu diễn như trên xác định một tập lồi đa diện.
1.5.2. Một số khái niệm cơ bản liên quan đến hàm gần lồi-gần lõm
Hàm phân tuyến tính và tuyến tính là các hàm gần lồi – gần lõm trên miền xác
định trong R
n
([1], [2]). Do đó các kết quả lý thuyết cũng như phương pháp tìm cực
tiểu đối với hàm gần lồi-gần lõm đưa ra trong sách “Quy hoạch gần lồi-gần lõm
ứng dụng vào quy hoạch tuyến tính” ([1]) có thể áp dụng đối với hàm phân tuyến
tính và hàm tuyến tính. Chính vì vậy, trước khi trình bày bài toán quy hoạch phân
tuyến tính và thuật toán nón xoay giải nó, chúng ta nhắc lại một số khái niệm, định
nghĩa, các định lý, hệ quả và các tính chất cơ bản của hàm gần lồi-gần lõm đã trình
bày trong sách “Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính”
Số hóa bởi Trung tâm Học liệu

, f(x) f(y)
và (0, 1).
Định nghĩa 1.4:
Hàm f:
n1

là một hàm gần lồi (almost-convex) nếu nó là một hàm tựa lồi
và thoả mãn f( .x + (1- ).y )<max{f(x), f(y)} với mọi x, y
n

, f(x) f(y) và
(0, 1).
Định nghĩa 1.5: Hàm f:
n1

được gọi là một hàm gần lồi - gần lõm (almost-
convex and almost-concave) nếu nó vừa là một hàm gần lồi vừa là một hàm
gần lõm.
Tính chất 1.1. Min{f(x), f(y)} f( .x + (1- ).y) max{f(x), f(y)}, x, y ,
n

và
[0, 1].
Từ các định nghĩa trên ta suy ra một số tính chất sau của hàm vừa tựa lồi vừa tựa
lõm:
S húa bi Trung tõm Hc liu

Tớnh cht 1.2. Nu f(x) = f(y) thỡ f(x) = f( .x + (1- ).y) = f(y) [0,1].
Nu f l mt hm gn li-gn lừm thỡ nú s tho món cỏc tớnh cht:
Tớnh cht 1.3. Nu f(x) = f(y) thỡ f(x) = f( .x + (1- ).y ) = f(y),

2
, , z
N

l cỏc im bt k thuc
n

ta luụn cú:
min{f(z
1
), , f(z
N
)} f(
1
.z
1
+ +
N
.z
N
) max{f(z
1
), , f(z
N
)}
i
[0, 1];
1
1
N

i

1

, i=1, 2, , m.
Tập P xác định như trên gọi là miền ràng buộc tuyến tính và nó là một miền lồi.
Ở đây chúng ta ký hiệu
1
, . ,
n
ii
i
X Y x y
với
1 2 1 2
: ( , , , ), : ( , , , )
nn
X x x x Y y y y

Định nghĩa 1.6: Miền ràng buộc tuyến tính P được gọi là không bị chặn nếu nó tồn
tại một điểm chấp nhận x
0
thuộc P và một điểm z ≠ 0 sao cho

x
0
+

.z P, 0,
khi đó điểm z được gọi là phương vô hạn chấp nhận của P tại x

0
.
2. Điểm z ≠ 0 được gọi là một hướng giảm từ x
0
của hàm gần lồi – gần lõm f nếu
f(x
0
) > f( x
0
+

.z ) >0, hay ta nói f giảm theo hướng z từ x
0
.
Từ các định nghĩa trên ta suy ra một vài tính chất sau
3. Điểm z ≠0 gọi là hướng không đổi của f từ x
0
, nếu f(x
0
)=f(x
0
+

.z ), α
1

.
Định lý 1.5.6. Nếu tồn tại
1
> 0 mà f(x) < f(x+

2)
lim
f( x+

.z ) = -∞ , , với z là hướng giảm từ x của hàm f.
Định lý 1.5.8 f:
n1

là hàm gần lồi-gần lõm, nếu f(x
0
) ≤ f( x
0
+

z ). thì
f(x) ≤ f( x+

.z ), α >0, x
n

.
Định lý 1.4.8 cho ta kết luận rằng nếu z là một hướng không giảm của f tại x
0
thì
nó cũng là một hướng không giảm của f tại mọi điểm x thuộc
n

. Do đó ta gọi z là
một hướng không giảm của hàm f. Từ định lý 1.4.8 ta dễ dàng chứng minh được hệ
quả sau.

0
) < f( x
0
+

z) ,. thì z là một
hướng tăng của hàm f ,
n
x 
, tức là f(x)<f(x+ .z),
0,
n
x 
. Và ta gọi z là
một hướng tăng của hàm f.
Số hóa bởi Trung tâm Học liệu

Hệ quả 1.7: f:
n1

là hàm gần lồi-gần lõm, z≠0 .là một hướng tăng của hàm
f khi và chỉ khi: f(0)<f( .z),
0

Hệ quả 1.8.
f:
n1

là hàm gần lồi-gần lõm, và f(x)>f(y) thì z = x – y là một hướng tăng
của hàm f và z= y - x là một hướng giảm của hàm f.

0
.
Từ tính chất thứ 1.2 và hệ quả 1.9 ta có thể chứng minh dễ dàng hệ quả sau:
Hệ quả 1.11
Nếu x ≠ y mà f(x)=f(y) thì
1
,R
0
chúng ta có z = α.( x – y), là hướng
không đổi của hàm f và
n1
( ) ( .( )), ,f u f u x y u 

Hệ quả 1.12. f:
n1

là hàm gần lồi-gần lõm, z≠0 .là một hướng không giảm
của hàm f khi và chỉ khi: f(0)≤f( .z),
1

và
0
i
Li
f x C x c x
L
x P x A x b i m

x
n

, A
i
là véc tơ dòng và A
i
,
n

m n, A
i
(a
i1
, a
i2
, , a
in
) ≠ O(0,…,0) ,
C(c
1
, c
2
, …, c

giá trị của hàm mục tiêu tại các đỉnh còn lại của chóp thì nón chứa chóp đơn hình
tương ứng với đỉnh này chính là một nón-min của bài toán (L).
Thuật toán đề nghị giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn trình
bày ở đây chính là một biến thể của thuật toán nón-min giải bài toán quy hoạch gần
lồi - gần lõm nói trên với miền ràng buộc thuộc dạng bất phương trình tuyến tính(
[1]).
Xét bài toán (L) trong trường hợp biết một nón – min của bài toán (L).
Ý tưởng của thuật toán nón xoay tuyến tính giải bài toán (L) như sau:
Xuất pháp từ một nón-min M ban đầu của hàm mục tiêu bài toán, chúng ta
kiểm tra xem đỉnh của nó có thuộc miền chấp nhận của bài toán không (tức là đỉnh
này có thoả mãn tất cả các ràng buộc không) nếu đỉnh này thuộc miền chấp nhận
thì nó là một lời giải của bài toán (L). Ngược lại ta xây dựng nón xoay mới M(r,s)
(vẫn là nón-min) từ nón cũ M của bài toán (L) và lặp lại quá trình kiểm tra nón
xoay mới này tương tự như đối với nón M, quá trình này được thực hiện cho đến
khi đỉnh của nón xoay mới M(r,s) thuộc miền chấp nhận của bài toán (L) ( khi
miền ràng buộc của bài toán (L) có phương án) hoặc sẽ phát hiện ra miền ràng
buộc của bài toán (L) là rỗng.
2.1.2. Thuật toán nón xoay tuyến tính
Số hóa bởi Trung tâm Học liệu

Bước chuẩn bị (bước 0).Giả sử ta đã biết M
0
là nón - min của bài toán (L) với tập
chỉ số cơ sở là I
0
:={
0 0 0
12
, , ,
n

tương ứng là I
k
:=
12
, , ,
k k k
n
i i i
; x
k
=
k
M
x
và
i
k
z
=
k
i
M
z
.
Xác định tập J
+
(x
k
) như sau:
( ): 1,2, , : , 0

hoặc s
k
= max{j: j J
+
(x
k
) (gọi là qui tắc chọn max)
và xác định:
: : , 0
kk
ss
i
kk
I i I A z
;
12
: : , 0 , , ,
k k k
k k k k
s s s
kk
ik
k s s s q
I i I A z i i i
, (2.2)
2.1. Nếu
k
s
I
= thì dừng lại, suy ra bài toán (L) không có phương án.

và chọn chỉ số đưa ra khỏi cơ sở theo một trong hai cách sau:
Ta chọn r
k
là chỉ số tuỳ ý thuộc
k
s
V
.
hoặc ta chọn
r
k
= min{v: v
k
s
V
} hoặc r
k
= max{v: v
k
s
V
} (2.4)
Số hóa bởi Trung tâm Học liệu

(cách chọn chỉ số này gọi là qui tắc chọn min (hoặc là qui tắc chọn max)) .
Và ta xây dựng nón xoay M
k+1
= M
k
(r

,
( . ) ,
,
1
.
,
k
kk
kk
k
kk
i
kk
s
i
k
rs
ii
k k k k k
sr
k
r
kk
sr
k
z khi i I
Az
z z z khi i I i r
Az
z khi i s

k
-
,
.
,
kk
k
kk
s
s
sr
k
A x b
Az
k
r
k
z
=
1
1
.
k
i
ik
iI
bz
(2.6)
Quay trë l¹i b-íc k víi k k+1


i
k
z
theo công thức xoay (2.5).
Định lý 2.1.
Giải bài toán (L) theo thuật toán nón xoay với chỉ số chọn đưa vào cơ sở là s
k
=
min{j: j J
+
(x
k
)} (hoặc s
k
= max{j: j J
+
(x
k
)}) và chỉ số chọn đưa ra khỏi cơ sở
tương ứng là r
k
(s
k
)= min{v: v
k
s
V
} (hoặc tương ứng là r
k
(s

n
jj
j
n
jj
j
c x c
Lx
m
Lx
d x d
(2.7)
Với các ràng buộc
ij
1
n
ji
j
a x b
, i=1,……,n (2.8)
0
j
x
, j=1,……,n (2.9)
Bài toán quy hoạch phân tuyến có ý nghĩa lớn trong kinh tế cũng như trong lý
thuyết của toán học, thường gặp trong công nghiệp hóa chất, trong lý thuyết trò
chơi, trong bài toán vận tải, trong việc cắt nguyên vật liệu, trong việc định giá
thành sản phẩm.
2.2.2. Thuật toán giải
Bài toán quy hoạch phân tuyến tính gọi là chấp nhận được nếu

hoặc L
2
(x)
0
,
xD
thì ta chỉ cần giải
một bài toán max
( ) .L x x D
Tổng quát nếu bài toán (2.7) - (2.9) chấp nhận
được thì

12
ax ( ) ax ax ( ), ax ( ) .
x D x D x D
m L x m m L x m L x

Khi bài toán I (hay II) không chấp nhận được thì
1
ax ( )m L x x D
( hoặc
2
ax ( )m L x x D
)
trong biểu thức trên coi như . Việc khẳng định bài toán (2.7) - (2.9) chấp nhận
được hay không hoàn toàn biết được nhờ xét các bài toán I và II.
Như vậy vấn đề quy về việc tìm một phương pháp giải bài toán quy hoạch phân
tuyến tính có mẫu số của hàm mục tiêu luôn giữ nguyên một dấu và có thể bằng
không trên miền ràng buộc. Để xác định dưới đây ta sẽ xét bài toán (2.7) - (2.9) với
giả thiết

L z L
L x L y

Đạo hàm theo :

11
2
22
2
( ) ( )
( ) 1
( ) ( )
()
L x L y
dL
L x L y
d L z

Số hóa bởi Trung tâm Học liệu

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ì L(z) tăng hoặc giảm, hoặc giữ nguyên giá trị bằng hằng số.
Để giải bài toán (2.7) - (2.9) với điều kiện (2.10) trước tiên ta giải bài toán

2
ax ( )M m L x x D
(2.11)
Giải bài toán này bằng phương pháp đơn hình có thể biết được
D

cần giải tới bước tối ưu.
Tổng quát ở bước v ta có phương án cực biên x
v
với L
2
(x
v
) > 0, z
jk
(j
v
I
) là các
thành phần khai triển của vectơ A
k
theo cơ sở
,
jv
A j I
.
Xét phương án
1
x
v
nằm trên một cạnh của D kề với
x
v
ứng với vectơ cột A
s
.

jI
Z z c Z c
Z z d Z c

Dễ thấy rằng:

11
11
( ) ( )
vv
sv
L x L x
(2.13)

trong các trường hợp còn lại
Số hóa bởi Trung tâm Học liệu 12
22
( ) ( )
vv
sv
L x L x
(2.14)
Ký hiệu

21
12
( ) ( )

, k=1,….,n
thì nó là phương án tối ưu.
Chứng minh: Lấy bất kì y
D
mà
2
( ) 0Ly
ta phải chứng minh rằng
( ) ( )
v
L y L x

Từ giả thiết ta có

21
12
( )( ) ( )( ) 0,
vv
k k k k
L x Z d L x Z c

Suy ra
1 2 1 2
1
2
()
( ) ( )( )
()
v
v

vv
k k k k
v
kk
Z y L x Z y L x d c
Lx
Ly(2.15)