Mục lục
Mở đầu
Chơng I. Một số khái niệm cơ bản về giải tích lồi và bài toán qui hoạch tuyến
tính.
1.1 Một số khái niệm cơ bản .. ...................7
1.1.1 Tập afine . .. . ....................7
1.1.2 Tập lồi .. . .................8
1.1.3 Tập lồi đa diện .. ...............10
1.1.4 Điểm trong và điểm trong tơng tơng đối ..................13
1.1.5 Hàm lồi ....................15
1.1.6 Tính chất cực trị ...................15
1.2 Phơng pháp đơn hình giải bài toán qui hoạch tuyến tính ....................16
1.2.1 Mô hình toán học .................16
1.2.2 Mô tả hình học của phơng pháp đơn hình ..................18
1.2.3 Nghiệm cơ sở và phơng án cực biên..............................................18
1.2.4 Thuật toán đơn hình .................19
1.2.5 Công thức đổi cơ sở và bảng đơn hình .....................26
1.2.6 Vấn đề cơ sở cực biên và cơ sở xuất phát ... .................28
1.2.7 Đối ngẫu của qui hoạch tuyến tính..................................................29
1.3 Kết luận ...................................................................................................33
Chơng II. Bài toán qui hoạch tuyến tính đa mục tiêu.
2.1 Thế nào là bài toán tối u đa mục tiêu ..................34
2.2 Mô hình toán học và cấu trúc tập nghiệm .................39
1
2.2.1 Không gian với thứ tự từng
phần ...................40
2.2.2 Nghiệm hữu hiệu, nghiệm hữu hiệu yếu ..
.................41
2.3 Lý do giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá
trị .........................................................................................................................42
2.4 Kết luận.....................................................................................................43

chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà qui
hoạch tuyến tính không giải đợc, chẳng hạn nh trong một công ty ngoài việc nâng
3
cao chất lợng sản phẩm thì công ty cũng chú trọng tới đa dạng hoá sản phẩm, già
thành rẻ, doanh thu lớn, Khách hàng khi chọn mua hàng thì muốn hàng rẻ, vừa
có chất lợng cao, vừa có hình thức đẹp. Tóm lại, mục đích của bài toán qui hoạch
tuyến tính đa mục tiêu là tối u đồng thời nhiều hàm mục tiêu độc lập với nhau trên
một miền chấp nhận đợc. Do không gian giá trị của lớp bài toán này không đợc sắp
thứ tự toàn phần, nên khái niệm nghiệm thông thờng không còn thích hợp. Trong
qui hoạch đa mục tiêu, cùng với khái niệm thứ tự từng phần, ta sẽ sử dụng khái
niệm nghiệm hữu hiệu.
Một phơng án chấp nhận đợc đợc gọi là nghiệm hữu hiệu nếu không tồn tại
một phơng án chấp nhận đợc khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các
mục tiêu khác không tồi hơn.
Đầu thế kỷ XX, Pareto đã sử dụng khái niệm này khi ông nghiên cứu phúc
lợi và thu nhập của dân chúng. Ông đã lập luận nh sau: "Nếu thu nhập của một
nhóm dân c tăng lên, nhng thu nhập của một nhóm khác giảm xuống thì khi đó
không thể so sánh "phúc lợi" của toàn xã hội. Đó là trờng hợp không so sánh đợc.
Nhng có thể thấy rằng, phúc lợi xã hội sẽ tăng lên nếu thu nhập của ít nhất một
nhóm ngời nào đó lớn lên, còn thu nhập của những nhóm khác không thấp xuống".
Ta nhận thấy rằng, theo quan điểm của toán học, khái niệm nghiệm hữu hiệu mà
chúng ta dùng trong qui hoạch đa mục tiêu phù hợp với luận đề Pareto.
Khi
( )
2pp
hàm mục tiêu đều là hàm tuyến tính và miền ràng buộc là tập
lồi đa diện khác rỗng trong
n
R
, ta nhận đợc bài toán qui hoạch tuyến tính đa mục

6
Chơng I
Một số khái niệm cơ bản về giải tích lồi và
bài toán qui hoạch tuyến tính.
Bài toán qui hoạch tuyến tính có vai trò trợ giúp quan trọng trong các bớc
giải bài toán qui hoạch tuyến tính đa mục tiêu. Trong chơng này, trớc hết em xin
nhắc lại một số khái niệm cơ bản sẽ cần dùng đến trong các phần sau. Phần tiếp
của chơng dành để trình bày phơng pháp đơn hình giải bài toán qui hoạch tuyến
tính.
1.1. Một số khái niệm cơ bản
1.1.1-Tập affine
* Đờng thẳng đi qua 2 điểm
n
Rb,a
là tập hợp tất cả các điểm x trong R
n
có dạng
R,b)1(ax +=

mọi với
.
* Một tập M chứa đờng thẳng đi qua 2 điểm bất kì của nó thì đợc gọi là tập
affine.
* Đoạn thẳng đi qua 2 điểm
n
Rb,a
kí hiệu là
[ ]
b,a
, là tập

R
thoả mãn bất phơng trình
tuyến tính:
{ }
R,0\Ra,x,a
n


đợc gọi là nửa không gian đóng.
* Nửa không gian đợc cho bởi:
{ }
R,0\Ra,x,a
n
<

đợc gọi là
nửa không gian mở.
1.1.2- Tập lồi
* Một tập A trong không gian R
n
đợc gọi là tập lồi nếu
Ab,a
,
[ ]
1,0

thì
Ab)1(ax +=

.

.
8
Mệnh đề 1.1.1. Tập
n
RA
là lồi khi và chỉ khi nó chứa tất cả các tổ hợp lồi
của các phần tử thuộc A.
* Tập M

R
n
đợc gọi là một nón với đỉnh a nếu:
0,Mx

thì
x
=
M)ax(a +

.
Định lý 1.1.1 Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số
và phép lấy tổ hợp tuyến tính. Nếu A và B là 2 tập lồi trong R
n
thì các tập sau
cũng là lồi:
(i)
{ }
Bx,Ax:x:BA =

(ii)

i
=
,
trong đó
,Ra
ni


Rb
i

.
* Một tập lồi đa diện là bao lồi của một số hữu hạn điểm và một số hữu hạn
đoạn thẳng.
* Một tập lồi đa diện bị chặn thờng đợc gọi là đa diện lồi.
* Một đa diện lồi là giao của một số hữu hạn điểm.

Cho tập lồi đa diện M, tập con MF đợc gọi là diện nếu:
.Fb,aFb)1(,10,Mb,a,Fx +=<<

ax
Nói cách khác, F là một diện của M nếu F chứa một điểm trong (hoặc điểm trong
tơng đối) của một đoạn thẳng nào đó của M thì F chứa trọn cả đoạn thẳng đó. Một
diện có thứ nguyên là 0 đợc gọi là một đỉnh hay điểm cực biên, cạnh là diện có thứ
nguyên bằng 1.
10
* Cho C là một tập lồi đa diện, một điểm
Cx
0


.
Ví dụ 1.1.3
Trong mặt phẳng
2
R
đơn hình là một tam giác, Hình 2a.
Trong không gian
3
R
đơn hình là một tứ diện, Hình 2b.
a) b)
Hình 2.
11
* ảnh của tập lồi: Cho
n
RS
và ánh xạ
p
RS:f
. Khi đó nếu S là tập lồi
và f là ánh xạ tuyến tính thì ảnh f(S) của S qua ánh xạ f cũng là tập lồi. Nhắc lại
rằng, ma trận C cấp
( )
pm ì
chính là ánh xạ tuyến tính từ
pn
RR
.
Xét ánh xạ tuyến tính
pn

( )
1,0v
2
= ,
( )
2,1v
3
= ,
( )
0,3v
4
= .
Khi đó
{ }
4321
z,z,z,zconv)S(C =
, với
( )
0,0Cvz
11
==
,
( )
1,2Cvz
22
==
,
( )
1,5Cvz
33

D,B,AconvC =
nh Hình 4.
A
x
2
, .
B D
Hình 4.
Theo định nghĩa:
Cintx
1

,
ABrix
2

.
* Giả sử C là tập lồi trong R
n
, véc tơ y

0 đợc gọi là hớng lùi xa của C nếu
0,Cx >

thì
Cyx +

.
Tập hợp tất cả các hớng lùi xa gọi là nón lùi xa, kí hiệu là rec C.
Định lí 1.1.4

là các đỉnh, d
j
là phơng của
các cạnh vô hạn của A .
Định nghĩa 1.1.1
i) Ta nói hai tập con khác rỗng
n
RD,C
là đợc tách bởi siêu phẳng
{ }
{ }
R,0\Ra,x,a:RxH
nn
==

nếu
y,asupx,ainf
DyCx


.
ii) Hai tập
n
RD,C
đợc gọi là tách mạnh (tách hẳn, tách chặt) bởi siêu
phẳng
{ }
{ }
R,0\Ra,x,a:RxH
nn


* Hàm f đợc gọi là lõm (lõm chặt) nếu f là lồi (lồi chặt ).
* Hàm f đợc gọi là tựa lồi trên A, nếu R

tập mức
{ }

)x(f:Ax
là tập lồi. Hàm f đợc gọi là tựa lõm nếu f là tựa lồi.
1.1.6 Tính chất cực trị
Cho
n
RD
và
RD:f
(không nhất thiết lồi) ta có định nghĩa
Định nghĩa 1.1.2
Một điểm
Dx
*

đợc gọi là cực tiểu địa phơng của f trên D, nếu tồn tại
một lân cận mở U của x
*
, sao cho UDx),x(f)x(f
*
.
Điểm x
*
đợc gọi là cực tiểu tuyệt đối của f trên D nếu

nm ì
và
n
Rx,c
,
m
Rb
.
Trong nghiên cứu qui hoạch tuyến tính cũng nh trong thực tế, ngời ta thờng
dùng 2 dạng
16
* Dạng chính tắc
x,cmin
, (LP)
với điều kiện
{ }
0xbAx:Rx:Dx
n
== ,
.
* Dạng chuẩn tắc
x,cmin
,
với điều kiện
{ }
0xbAx:Rx:Dx
n
= ,
.
Nh đã biết, ta có thể dễ dàng chuyển một bài toán qui hoạch tuyến tính bất

ii
n
1j
jij
buxa =+

=
với biến phụ
0u
i

.
Không giảm tính tổng quát, ở đây em xin trình bày phơng pháp đơn hình
giải bài toán qui hoạch tuyến tính dạng chính tắc (LP).
17
1.2.2 Mô tả hình học của phơng pháp đơn hình:
Xuất phát từ một điểm cực biên
0
x
của tập lồi đa diện ràng buộc D, các tr-
ờng hợp sau có thể xảy ra:
(i) Trên mọi cạnh của tập lồi đa diện xuất phát từ đỉnh
0
x
, hàm mục tiêu đều
không giảm. Do tính chất tuyến tính của hàm mục tiêu,
0
x
là một nghiệm
tối u.

18
điều kiện cần và đủ để một điểm chấp nhận đợc là phơng án cực biên cho bởi mệnh
đề sau (xem chứng minh trong [2]).
Mệnh đề 1.2.1. Cho
( )
n21
x,...,x,xx =
thỏa mãn (1.2.0). Cho
{ }
0x:jJ
j
>=
.
Điều kiện cần và đủ để x là một phơng án cực biên là các véc tơ
{ }
Jj:A
j

là
độc lập tuyến tính.
Giả sử x là phơng án cực biên. Đặt
{ }
0x:jJ
j*
>=
. Theo Mệnh đề 1.2.1 các
véc tơ
( )
*j
JjA

một nghiệm cơ sở. Một tập lồi gọi là không thoái hoá, nếu mọi phơng án cực biên
(đỉnh) của nó không thoái hoá.
1.2.4 Thuật toán đơn hình
19
Giả sử ta đã có một phơng án cực biên x. Gọi J là tập chỉ số cơ sở của x. Do
hệ
{ }
Jj:A
j

là 1 cơ sở, nên mọi cột
Jk,A
k

đều là một tổ hợp tuyến tính của
véc tơ
j
A
(
Jj
). Tức là tồn tại các số thực
jk
z
sao cho:



=
Jj
jjkk


=
Jj
jjkk
cz:z
(1.2.4)

kkk
cz =

(1.2.5)
Chú ý rằng
0
k
=

nếu
Jk
. Ta sẽ gọi
k

là các ớc lợng của phơng án cực biên
(nghiệm cơ sở của x).
Ta có thể viết các công thức trên dới dạng ma trận. Giả sử đã có tập cơ sở J.
Ta đa vào các kí hiệu sau:
j
A
: ma trận có các cột thuộc cơ sở J (ma trận cơ sở).
Jk
Z



b.AxbxA
1
JJJJ

==
(1.2.2)
(1.2.3)


kJkJk
cZc =

kk
1
JJ
cAAc =

(1.2.3)
Nh vậy nếu tính đợc ma trận nghịch đảo
1
J
A

thì ta tính đợc các đại lợng
kJJk
,x,z

.Ta xét điều kiện đủ để x là một nghiệm tối u:

kk
cz


=

n
1k
kk
yzz
(1.2.8)
Thay A
k
từ (1.2.1) vào (1.2.6) ta có:
bAzy
j
Jj
jk
n
1k
k
=







=

1k
jkkj
=

=
.
Vậy:

= = =
==






=
Jj
n
1k
n
1k
kkkjkj
Jj Jj
n
1k
jkkjjj
yzyzczycxc
.
So sánh với (1.2.8)

k
>

, đều có
0z
jk
>
với một
Jj
, thì tìm đựơc một cơ sở x
1
ứng
với cơ sở B
1
thoả mãn
xcxc
T1T

.
Chứng minh:
Gọi J là tập chỉ số cơ sở của x. Do x là nghiệm cơ sở nên



=
Jj
jj
bAx
(1.2.10)
Theo định nghĩa của

bAA)zx(

(1.2.11)
Lấy véc tơ x
1
có các toạ độ đợc cho bởi:






+

=
0
zx
zx
x
kkk
jkj
1
j


,
nếu
nếu
nếu


kjjkjjkjjkj
1T
cczcxcc)zx(xc

.
Do


=
Jj
jjkjk
czz
,
ta có:
k
T
kk
T1T
xc)cz(xcxc

==
.
Cho
+

ta thấy hàm mục tiêu giảm đến

. Điều đó chứng tỏ trong trờng
hợp này bài toán không có nghiệm hữu hạn.
ii) Chọn

. Đối với
1
Jj
chọn:

{ }
rkr1jkj
z/xJj:z/xmin ==

(1.2.13)
(r là chỉ số cơ sở đạt min), và
}Jj:A{B
1j
=

với
{ } { }
)kr\J(J =

. Theo đại
số tuyến tính do


=
Jj
jjkk
AzA
và
0z
jk


==

. (1.2.14)
Nhận xét:
Qua chứng minh này, ta thấy rằng, nếu x
r
=0 thì chọn

theo (1.2.13) khi đó
theo (1.2.12) x

=x và do đó
xcxc
T'T
=
. Nh vậy trờng hợp này nghiệm cơ sở không
thay đổi, chỉ có cơ sở thay đổi. Tức là nghiệm cơ sở x ứng với với hai cơ sở B và B

(x thoái hoá). Nếu

>0, thì theo (1.2.14)
xcxc
T'T
<
, do đó
xx
'

. Hiển nhiên

24
Thuật toán đơn hình:
Giả sử bài toán qui hoạch tuyến tính
min
x,c
với điều kiện
{ }
0xbAx:Rx:Dx
n
== và
(1.2.15)
và ta đã biết một phơng án cực biên x
0
.
Bớc 1: Chọn một cơ sở
}Jj:A{B
j
=
của x
0
.
a) Với mỗi
Jk
tính z
jk
bằng cách giải hệ phơng trình tuyến tính sau:



=

0
k
>

và
Jj,0z
kj

: bài toán không có nghiệm hữu hạn. Thuật
toán kết thúc.
b2) ứng với
0
k
>

đều tồn tại
0z
jk
>
với một
Jj
. Chọn s sao cho
0
s
>

.
(Để hàm mục tiêu giảm nhanh thờng chọn s sao cho
s