Xem Xét & nghiên cứu Một số bài toán mở rộng trong lớp các bài toán vận tải mở rộng ( Toán –tin)

Hình cầu tâm a bán kính là tập S={xR
n
:x-a }. Hình cầu này tạo nên
- lân cận của điểm a, hay gọi là lân cận của a.
* Nếu tập AR
n
chứa cùng với điểm x một lân cận của nó thì x gọi là điểm
trong của A. Nếu trong lân cận bất kỳ của x A có các điểm của A và các điểm
không thuộc A thì x gọi là điểm biên của tập hợp A.
* Một tập AR
n
gọi là giới nội nếu nó đợc chứa trong một hình cầu tâm O nào
đó, tức là tồn tại số đủ lớn sao cho với mọi xA,x . Một dãy {x
(k)
} hội tụ thì
bao giờ cũng giới nội.
* Một tập hợp GR
n
đợc gọi là mở nếu với mọi xG đều tồn tại một hình cầu
tâm x nằm gọn trong G. Một tập FR
n
đợc gọi là đóng nếu với mọi dãy hội tụ{x
(k)
}
F ta đều có:
Fx
k
k


)(
lim

Một tập chứa mọi điểm biên của nó là tập đóng.
* Tập C đợc gọi là tập Compact nếu từ mọi dãy vô hạn {x
(k)
} thuộc C đều có thể
trích ra một dãy con {x
(ki)
} hội tụ tới phần tử thuộc C. Tập C là Compact khi và chỉ
khi C đóng và giới nội. Tập Compact M của tập đóng C cũng đóng trong C. Tập con
đóng M của tập Compact cũng Compact.
Hàm f(x) liên tục trên tập Compact C thì sẽ đạt cực trị trên tập ấy.
1.1.3 Tập lồi
Cho hai điểm a, b R
n
. Ta gọi đờng thẳng qua a, b là tập điểm có dạng
xR
n
: x = a + (1-)b, R.
Đoạn thẳng nối hai điểm a, b là tập lồi các điểm có dạng
xR
n
:x = x + (1-)y, 0 1
* Một tập MR
n
đợc gọi là một đa tạp affine nếu với hai điểm bất kỳ
x, y M thì toàn bộ đờng thẳng đi qua hai điểm đó cũng thuộc M.
Tức là x + (1-)y M : x,y M, R.
* Một siêu phẳng trong không gian R
n
là tập hợp tất cả các điểm
x=(x
1
, x
2
, , x
n
) R
n
thỏa mãn phơng trình tuyến tính
Trang: 5

a
1
x
1
+ a
2
x
2
+ + a
n
x
n
= trong đó a
1
, a
2
, , a
n
, R
* Tập hợp các điểm x=(x
1
, x
2
, , x
n
) R
n
thoản mãn bất phơng trình tuyến tính
a
1
x
1
+ a
2
x
2
+ + a
n
x
n
đợc gọi là nửa không gian đóng.
* Nửa không gian đợc cho bởi a
1
x
1
+ a
2
x
2
+ + a
n
x
n
< đợc gọi là nửa không
gian mở.
* Tập XR
n
đợc gọi là tập lồi nếu cùng với việc chứa hai điểm x, y nó chứa cả
đoạn thẳng chứa hai điểm ấy, tức là chứa tất cả các điểm có dạng:
x + (1-)y, 0 1
Ví dụ về các tập lồi: Không gian Euclide, các nửa không gian, mặt phẳng, nửa
mặt phẳng, hình chữ nhật, hình vuông, hình elip, hình hộp, hình cầu
* Một tập hợp là giao của một số hữu hạn các nửa không gian đóng đợc gọi là
tập lồi đa diện.
Mệnh đề: Giao của hai tập lồi là một tập lồi.
Hệ quả 1. Giao của một số bất kỳ tập hợp lồi là tập lồi.
Hệ quả 2. Miền chứa nghiệm của một hệ bất phơng trình tuyến tính dạng.
là một tập lồi (đa diện lồi). Một tập lồi đa diện giới nội gọi là một đa diện. Giao
của tất cả các tập lồi chứa tập X gọi là bao lồi của nó, ký hiệu [X]
1.1.4 Hàm lồi
* Một hàm số f(x) xác định trên tập lồi C R
n
đợc gọi là hàm lồi trên C, nếu
với mọi x, y C và 0 1 ta có f(x + (1-)y) f(x) + (1-)f(y).
* Hàm f(x) đợc gọi là hàm lồi chặt nếu với mọi x, y C và 0 1 ta có. f(x
+ (1-)y) < f(x) + (1-)f(y).
* Hàm f(x) đợc gọi là hàm lõm (lõm chặt) nếu - f(x) là hàm lồi (lồi chặt)
* Hàm f(x) xác định trên C đạt cực tiểu tuyệt đối tại x* C nếu
Trang: 6
.




2211
22222121
11212111







+++
+++
+++
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa

f(x
*
) f(x): xC
* Hàm f(x) đạt cực tiểu địa phơng tại x*

C nếu tồn tại lân cận mở U của x*
sao cho f(x*) f(x): xC U
Mệnh đề 1: Bất kỳ điểm cực tiểu địa phơng nào của hàm lồi trên tập lồi cũng là
điểm cực tiểu tuyệt đối.
Hệ quả: Bất kỳ điểm cực đại địa phơng nào của hàm lõm cũng là cực đại tuyệt
đối.
Mệnh đề 2: Cực đại của một hàm lồi (nếu có) trên một tập lồi có điểm cực biên
bao giờ cũng đạt tại một điểm cực biên.
1.2 Bài toán Quy hoạch tuyến tính
QHTT bắt nguồn từ những nghiên cứu của nhà toán học Nga nổi tiếng, Viện sỹ
L.V. Kantorovich trong một loạt các công trình về bài toán kế hoạch hoá sản xuất,
công bố năm 1938. Năm 1947 nhà toán học Mỹ G.B. Dantzig đã nghiên cứu và đề
xuất phơng pháp đơn hình (Simplex method) để giải bài toán QHTT. Năm 1952 ph-
ơng pháp đơn hình đã đợc chạy trên máy tính điện tử của Mỹ.
1.2.1 Bài toán quy hoạch tuyến tính
Bài toán tổng quát.
Để nhất quán lập luận ta xét bài toán tìm cực đại, sau đó ta xét cách chuyển bài
toán tìm cực tiểu sang tìm cực đại. Bài toán tổng quát của QHTT có dạng:
Ký hiệu: A=(a
ij
)
mxn
là ma trận với các phần tử a
ij
(1.1) gọi là hàm mục tiêu, (1.2) là các rằng buộc.
Nếu gặp bài toán Min, tức là
Thì giữ nguyên ràng buộc và đa về bài toán Max bằng cách
Trang: 7
( )
Dx
xcxf
j
n
j
j

=

=
min
1
( )
Dx
xcxf
j
n
j
j

=

=
max
1
( )
1.1max
1


=
j
n
j
j
xc
( ) ( )
( )
3.1, ,1,0
2.1 ,,1,,,
1
njx
mibxa
j
i
n
j
jij
=
==

=

Nếu bài toán Max có phơng án tối u là x* thì bài toán min cũng có phơng án là
x* và f
min
=-

f
max
Thật vậy, vì x* là phơng án tối u của bài toán Max nên ta có:
Chứng tỏ x* là phơng án tối u của bài toán Min và
Dạng chuẩn và dạng chính tắc.
Ngời ta thờng xét bài toán quy hoạch tuyến tính dới hai dạng sau:
-Dạng chuẩn:
-Dạng chính tắc:
Đa bài toán QHTT về dạng chuẩn hoặc dạng chính tắc.
Bất kỳ QHTT nào cũng có thể đa về một trong hai dạng chuẩn hoặc chính tắc
nhờ các phép biến đổi tuyến tính sau:
i) Một ràng buộc
Trang: 8
Dxxcxc
hayDxxcxcf
n
j
jj
n
j
jj
j
n
j
j
n
j
jj

=


==
==
,
,
11
*
11
*
max

=
==
n
j
jj
fxcf
1
max
*
min
njx
mibxa
xc
j
i
n
j
jij
n
j
jj
, ,1,0
, ,1,
max
1
1
=
=



=
=
njx
mibxa
xc
j
i
n
j
jij
j
n
j
j
, ,1,0
, 1,
max
1
1
=
==



=
=

=

n
j
ijij
bxa
1

Có thể đa về ràng buộc bằng cách nhân hai vế với (-1) và viết
lại
ii) Một ràng buộc đẳng thức
có thể thay bằng hai ràng buộc bất đẳng thức:
iii) Một biến x
j
không bị ràng buộc dấu có thể thay thế bởi hiệu của hai biến
không âm bằng cách đặt:
iv) Một ràng buộc bất đẳng thức
Có thể đa về ràng buộc đẳng thức bằng cách đa vào biến phụ y
i
0:
Về nguyên tắc, áp dụng nhiều lần các phép biến đổi (i), (ii) và (iii) ta có thể đa
một bài toán QHTT bất kỳ về dạng chuẩn, sau đó áp dụng nhiều lần phép biến đổi
(iv) ta sẽ đa nó về dạng chính tắc.
Giải bài toán QHTT bằng phơng pháp hình học.
Xét bài toán QHTT dới dạng chuẩn với hai biến số:
Từ ý nghĩa hình học ta biết rằng mỗi bất phơng trình tuyến tính a
i1
x
1
+a
i2
x
2

b
i
xác
định một nửa mặt phẳng.
Trang: 9
i
n
j
jij
bxa =

=1
i
n
j
jiji
n
j
jij
bxabxa

== 11
,
0,0, =
++
jjjjj
xxxxx với
ij
n
j
ij
bxa

=1
i
n
j
ijij
byxa =+

=1
ij
n
j
ij
bxa

=1
.''
1
ij
n
j
ij
bxa

=



=
=+
=
+
2,1,0
, ,1,
max
2111
2211
jx
mibxaxa
D
xcxc
j
iii

Nh vậy miền ràng buộc D đợc xác định nh là giao của một nửa mặt phẳng và sẽ
là một đa giác lồi trên mặt phẳng. Phơng trình c
1
x
1
+c
2
x
2
=

khi

thay đổi sẽ xác
định trên mặt phẳng các đờng thẳng song song với nhau mà ta sẽ gọi là các đờng
mức (với giá trị mức

). Mỗi điểm D sẽ nằm trên một đờng mức với mức
Bài toán đặt ra có thể phát biểu theo ngôn ngữ hình học nh sau: trong số các đ-
ờng mức cắt tập D, hãy tìm đờng mức với gía trị lớn nhất.
Nếu dịch chuyển song song các đờng mức theo hớng vector pháp tuyến của
chúng thì giá trị mức sẽ tăng, nếu dịch chuyển theo hớng ngợc lại thì giá
trị mức sẽ giảm. Vì vậy để giải bài toán đặt ra, ta có thể tiến hành nh sau.
Bắt đầu từ một đờng mức cắt D, ta dịch chuyển song song các đờng mức theo h-
ớng vector pháp tuyến (c
1
,c
2
) cho đến khi việc dịch chuyển tiếp theo làm cho đờng
mức không còn cắt D nữa thì dừng. Điểm của D (có thể nhiều điểm) nằm trên đờng
mức cuối cùng này sẽ là lời giải tối u cần tìm, còn giá trị của hàm mục tiêu tại đó
chính là giá trị tối u của bài toán.
Ví dụ: Xét bài toán:
f(x)= 4x
1
+5x
2
max
Xét đờng mức: 4x
1
+5x
2
=10. Đờng mức này đi qua hai điểm (0,2) và (2.5,0). Ta
có x*=(3,2), f
max
=22

Trang: 10
0,0
3
72
82
21
2
21
21







+
+
xx
x
xx
xx
( )
21
, xxx =
.
2211
xcxc +=

( )
21
,ccn =
y
n
*x
x

và x* là một đỉnh của D. Qua phơng pháp hình học ta thấy rằng:
- Nếu quy hoạch tuyến tính có phơng án tối u thì có ít nhất một đỉnh là tối u. Sở
dĩ nói ít nhất vì có trờng hợp đờng mức ở vị trí giới hạn trùng với một cạnh của D thì
tất cả các điểm trên cạnh này là phơng án tối u, trong đó có hai đỉnh.
- Nếu miền ràng buộc D giới nội và khác rỗng thì chắc chắn có phơng án tối u.
- Nếu miền ràng buộc không giới nội nhng hàm mục tiêu bị chặn trên ở trên
miền ràng buộc thì cũng chắc chắn có phơng án tối u.
1.2.2 Một số tính chất chung
Mệnh đề 1: Tập hợp tất cả các phơng án của một bài toán QHTT là tập lồi.
Tập lồi D các phơng án của một bài toán QHTT xác định bởi toàn bộ các ràng
buộc (1.2) và (1.3). Tập D có thể là rỗng, hoặc là một đa diện lồi hoặc là một tập lồi
đa diện không giới nội.
Nếu D là một đa diện lồi thì bài toán có phơng án, hơn nữa giá trị tối u của hàm
mục tiêu trên đa diện lồi là hữu hạn và việc tìm phơng án tối u đa đến việc chọn các
điểm của đa diện D có số đỉnh (điểm cực biên hay phơng án cực biên) hữu hạn.
Mệnh đề 2: Hàm mục tiêu của bài toán QHTT sẽ đạt Max tại điểm cực biên của
tập D. Nếu hàm mục tiêu không chỉ nhận Max tại một điểm cực biên của tập lồi D
mà tại nhiều điểm cực biên thì nó sẽ đạt giá trị cực đại tại những điểm là tổ hợp lồi
của các điểm đó.
Ký hiệu A
j
, j=1, , n là các vector cột của ma trận A.
Khi ấy hệ ràng buộc Ax =b có thể viết:
x
1
A
1
+ x
2
A
2
+ + x
n
A
n
= b (1.4)
Mệnh đề 3: Nếu các vector A
1
, A
2
, , A
k
là độc lập tuyến tính và thoả mãn
x
1
A
1
+x
2
A
2
+ +x
n
A
n
=b
trong đó x
j
>
0, j=1, k thì điểm
x=(x
1
,x
2
, ,x
k
,0, ,0)
là điểm cực biên của tập lồi đa diện D.
Mệnh đề 4: Nếu x =(x
1
,x
2
, ,x
n
) là điểm cực biên của tập lồi đa diện D thì các
vector A
j
trong biểu diễn (1.4) ứng với các thành phần x
j
> 0 lập thành hệ độc lập
Trang: 11

tuyến tính. Vì ma trận A có m dòng nên từ đây suy ra rằng điểm cực biên không có
quá m thành phần dơng.
Các mệnh đề 3 và mệnh đề 4 có thể gộp lại thành một mệnh đề sau:
Mệnh đề 5: Để x =(x
1
,x
2
,x
n
) là phơng án cực biên của QHTT dới dạng chính
tắc thì cần và đủ là các vector cột A
j
của ma trận A ứng với các thành phần x
j
> 0 là
độc lập tuyến tính.
1.2.3 Phơng pháp đơn hình giải bài toán QHTT
Cơ sở của phơng pháp này đơc G.B. Dantzig công bố năm 1947 có tên gọi là
phơng pháp đơn hình. Sở dĩ có tên gọi nh vậy là 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:
Mà tập hợp các điểm xR
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.
Đờng lối chung và cơ sở của thuật toán.
i) Đờng lối 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, đa diện lồi D có một số hữu hạn đỉnh. Nh vậy phải tồn tại thuật toán hữu
hạn. Thuật toán gồm hai giai đoạn:
- Giai đoạn 1: Tìm một phơng án cực biên (một đỉnh).
- Giai đoạn 2: Kiểm tra điều kiện tối u đối phơng án tìm đợc ở giai đoạn 1.
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 cải tiến giá trị hàm mục tiêu.
Tiếp theo lại 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.
ii) Cơ sở của thuật toán.
Xét bài toán QHTT dới dạng chính tắc:
< c, x > max (1.6)
Ax

= b (1.7)
Trang: 12
( )
5.1, ,1,0,1
1
njxx
j
n
j
j
==

=

x 0 (1.8)
Trong đó A là ma trận kích thớc mxn và giả sử rằng hạng của ma trận A là m
(điều này không làm mất tính tổng quát). x là một vector.
Giả sử x là một phơng án cực biên nào đó. Ta ký hiệu:
J* = {j| x
j
> 0} (1.9)
Vì các vector A
j
, jJ* là độc lập tuyến tính nên |J*| m (|J*| là số số phần tử
x
j
>0).
* Phơng án cực biên x đợc gọi là không thoái hoá nếu | J* |= m, thoái hoá nếu
|J*| < m.
Ta chọn một hệ thống m vector độc lập tuyến tính {A
j
, j J}sao cho J J*.
Hệ thống đó gọi là cơ sở của x, các vector {A
j
, j J} và các biến {x
j
, j J} đợc gọi
là các vector và các biến cơ sở tơng ứng. Các vector và các biến A
j
, x
j
, j J gọi là các
vector và các biến phi cơ sở tơng ứng.
Nếu x không thoái hoá thì tồn tại một cơ sở duy nhất, đó là J=J*.
Mỗi vector A
k
phi cơ sở có thế biểu diễn dới dạng tổ hợp tuyến tính của các
vector cơ sở:
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:
Bài toán QHTT đợc gọi là không thoái hoá nếu tất cả các phơng án cực biên của
nó đều không thoái hoá.
Giả sử bài toán không thoái hoá và ta đã tìm đợc một phơng án cực biên x=(x
1
,
x
2
, x
m
, 0, 0) và cơ sở của nó A
1,
, A
2
, A
m
.
Đối với phơng án cực biên này ta có:
với giá trị của hàm mục tiêu:
Trang: 13
( )
11.1,1, miaaz
ikij
Jj
jk
==


( )
10.1


=
Jj
jjkk
AzA
( )
12.1, ,1,0,
1
mjxbAx
j
m
j
jj
=>=

=
( )
13.1
1
0

=
=
m
j
jj
zxc

Ta tính các đại lợng sau:
Kí hiệu:
Định lý 1.1: (Tiêu chuẩn tối u). Nếu đối với phơng án cực biên
x=(x
1
,x
2
, ,x
m
,0 0) các điều kiện sau đợc thỏa mãn
thì x* là phơng án tối u.
Chú ý:
Trong (1.10) nếu A
j
là một vector cơ sở, khi đó tồn tại chỉ một hệ số z
jj
=1, tất
cả các hệ số khác đều bằng 0 và ta có:
và trong thực hành để kiểm tra điều kiện tối u của phơng pháp cực biên x ta chỉ
cần kiểm tra

k
0, kJ (1.18)
Ngời ta có thể chứng minh rằng nếu bài toán không thoái hoá thì (1.16) cũng
là điều kiện cần của tối u.
Định lý 1.2: Nếu tồn tại một chỉ số k sao cho
k
< 0 thì ngời ta có thể tìm đợc ít
nhất một phơng án x mà đối với nó Z > Z
0
.
Công thức tìm phơng án x:
Nhân (1.10) với

nào đó ta có:
Lấy (1.12) trừ đi (1.19) từng vế ta có:
Nếu các hệ số của các vector A
j
, j=1, ,m và A
k
trong (1.20) không âm, khi đó
ta có một phơng án mới x mà đối với nó hàm mục tiêu f có giá trị
Trang: 14
( )
14.1
1

=
=
m
j
kjjk
Zcz
( )
15.1
1
k
m
j
jjkkkk
cczcZ ==

=
( )
16.1, ,2,1,0 nk
k
=
( )
17.1,0 Jjcc
jjj
==
)19.1(
1
kj
m
j
jk
AAz

=

=
( )
)20.1(
1
bAAzx
kj
m
j
jkj
=+

=

)21.1('
0 k
ZZ =

Xem chi tiết: Xem Xét & nghiên cứu Một số bài toán mở rộng trong lớp các bài toán vận tải mở rộng ( Toán –tin)