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- vận tải ba chỉ số (solid transport p
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
LỜI MỞ ĐẦU
Cùng với sự phát triển mạnh mẽ của khoa học kỹ thuật, các bài toán tối ưu
M
xuất hiện ngày càng nhiều và tính phức tạp của chúng ngày càng lớn. Phạm vi
và khả năng ứng dụng của các bài toán tối ưu cũng ngày càng đa dạng và phong
phú.
.CO
Lớp bài toán tối ưu quan trọng được nghiên cứu đầu tiên và được ứng dụng
nhiều nhất là bài toán quy hoạch tuyến tính (linear programming). Đó là mô
hình toán học của một lớp rộng lớn các bài toán ứng dụng trong kinh tế và kỹ
thuật. Do đó cấu trúc của lớp bài toán quy hoạch tuyến tính có nhiều tính chất
OKS
rất tốt về mặt toán học, người ta đã tìm được các thuật giải rất hữu hiệu cho bài
toán này. Năm 1947 nhà toán học Mỹ G.B. Dantzig đã nghiên cứu và đề xuất ra
thuật toán đơn hình (simplex method) để giải bài toán quy hoạch tuyến tính.
Thuật toán đơn hình được phát triển mạnh mẽ trong những năm sau đó và được
xem là một phương pháp kinh điển để giải các bài toán quy hoạch tuyến tính.
Đây là một phương pháp được sử dụng có thể nói là rộng rãi nhất. Có ba lý do
OBO
chính:
Một là: Rất nhiều vấn đề thực tế, trong nhiều lĩnh vực khác nhau có thể đưa
về bài toán quy hoạch tuyến tính.
Hai là: Trong nhiều phương pháp giải các bài toán phi tuyến, bài toán
tuyến tính xuất hiện như là một bài toán phụ cần phải giải trong nhiều bước lặp.
Ba là: Phương pháp đơn hình là phương pháp hiệu quả để giải bài toán quy
KIL
hoạch tuyến tính.
Ngày nay, bằng thuật toán đơn hình và các dạng cải biên của chúng, người
ta có thể giải rất nhanh các bài toán QHTT cỡ lớn.
Lớp các bài toán vận tải là trường hợp đặc biệt của quy hoạch tuyến tính,
bởi vậy có thể dùng các phương pháp của quy hoạch tuyến tính để giải. Tuy
nhiên, do tính chất đặc thù riêng của nó, người ta xây dựng các phương pháp
giải riêng.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Thông thường khi nói đến bài toán vận tải ta thường liên hệ ngay đến bài
toán vận tải hai chỉ số, bởi đây là bài toán vận tải kinh điển có những phương
pháp giải hay. Bên cạnh đó, người ta còn xét một số các bài toán vận tải mở
M
rộng như bài toán vận tải ba chỉ số, bài toán vận tải khoảng, bài toán vận tải đa
mục tiêu và rất nhiều bài toán khác, đó là các biến thể của bài toán vận tải kinh
điển trên.
.CO
Trong khuôn khổ khoá luận này, em xem xét và 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 đó. Đó là các bài toán: Bài toán
vận tải ba chỉ số (solid transport problem) không hạn chế và có hạn chế khả
năng thông qua, Bài toán vận tải ba chỉ số khoảng (interval solid transport
KIL
OBO
OKS
problem) và giới thiệu một số Bài toán vận tải đa mục tiêu.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
CHƯƠNG I. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Trong việc nghiên cứu các bài toán tối ưu nói chung, giải tích lồi giữ một
M
vai trò rất quan trọng. Nó được sử dụng làm cơ sở toán học trong việc xây dựng
các thuật toán.
Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu được nghiên
.CO
cứu trọng vẹn cả về phương diện lý thuyết lẫn thực hành, Bài toán vận tải là một
dạng đặc biệt của QHTT. Do đó chương này nhằm giới thiệu một số khái niệm
và kiến thức cơ bản về giải tích lồi và QHTT.
1.1 Một số khái niệm về giải tích lồi
OKS
1.1.1 Không gian Euclude
Một vector n chiều trên trường số thực là một bộ được sắp thứ tự gồm n số
thực x=(x1, x2, ..., xn). Các xi, i =1, ..., n gọi là các thành phần hay toạ độ của
vector. Ví dụ x=(4,5,10,20).
Hai vectơ x và y gọi là bằng nhau x=y, nếu xi=yi, ∀i =1, ..., n.
Xét hai phép toán trên các vector:
OBO
Phép cộng: x+y=(x1+y1, x2+y2, ..., xn+yn)
Phép nhân: αx=(αx1, αx2, ..., αxn), ∀α ∈ R
Khi đó tập hợp tất cả các vector n chiều trong đó xác định phép cộng các
vector, nhân một số thực với vector như trên tạo thành không gian tuyến tính n
chiều trên trường số thực R, ký hiệu Rn.
Các vector x(i) ∈Rn, i =1, ..., m được gọi là độc lập tuyến tính nếu:
m
= 0 ⇔ α i = 0, i =1, m
KIL
∑α x
i =1
i
(i )
m
Nếu: x = ∑αi x (i) với ít nhất một αi ≠ 0 thì x gọi là tổ hợp tuyến tính của
i =1
các x(i), i =1, ..., m. Hơn nữa nếu αi > 0, i =1, ..., m và
m
∑α
i =1
i
=1
thì x gọi là tổ hợp
lồi của các x(i), i =1, ..., m.
Trong Rn có n vector độc lập tuyến tính lập thành cơ sở của nó.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Giả sử e(1), e(2), ..., e(n) là một cơ sở của Rn thì bất kỳ một vector x ∈ Rn đều
là tổ hợp tuyến tính của các vector e(1), e(2), ..., e(n). Ta gọi tích vô hướng của hai
vector x=(x1, x2, ..., xn) và y=(y1, y2, ..., yn), ký hiệu, , là một số bằng.
M
n
< x, y > = ∑ x i y i
i =1
Tích vô hướng là một dạng song tuyến tính, đối xứng, không âm, tức là:
.CO
1. = . ∀x,y ∈ Rn
2. =< x(1), y >+< x(2), y>. ∀x(1), x(2), y ∈ Rn
3. <λx,y> = λ. ∀x,y ∈ Rn
4. ≥ 0, ∀x∈ Rn dấu bằng xẩy ra khi và chỉ khi x= 0.
OKS
Độ dài của vector x=(x1, x2, ..., xn) là một số xác định bởi.
x = < x, x > =
n
∑x
i =1
2
i
Khoảng cách giữa hai vector x và y là một số xác định bởi:
ρ ( x, y ) = x − y = < x − y , x − y > =
n
∑ (x
i =1
i
− yi )
2
là không gian Euclude.
1.1.2 Tập compact
OBO
Không gian vector trong đó có tích vô hướng và khoảng cách như trên gọi
Dãy {x(k) }⊂Rn k=1, 2, ... được gọi là có giới hạn x(0) khi k → ∞ và viết
lim x(k) = x(0), nếu
k→∞
(
)
lim ρ x ( k ) , x ( 0) = 0
k →∞
KIL
Hình cầu tâm a bán kính ρ là tập S={x∈Rn :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 A⊂Rn 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 A⊂Rn 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 x∈A,x≤ ρ. Một dãy {x(k)}
hội tụ thì bao giờ cũng giới nội.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
* Một tập hợp G⊂Rn được gọi là mở nếu với mọi x∈G đều tồn tại một hình
cầu tâm x nằm gọn trong G. Một tập F⊂Rn được gọi là đóng nếu với mọi dãy hội
Một tập chứa mọi điểm biên của nó là tập đóng.
M
tụ{x(k)}⊂ F ta đều có: lim x (k ) ∈F
k →∞
* 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
.CO
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
x∈Rn : x = λa + (1-λ)b, λ ∈ R.
OKS
Cho hai điểm a, b ∈Rn. Ta gọi đường thẳng qua a, b là tập điểm có dạng
Đoạn thẳng nối hai điểm a, b là tập lồi các điểm có dạng
x∈Rn :x = λx + (1-λ)y, 0 ≤ λ ≤ 1
* Một tập M⊂Rn được gọi là một đa tạp affine nếu với hai điểm bất kỳ
OBO
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 Rn là tập hợp tất cả các điểm
x=(x1, x2, ..., xn) ∈Rn thỏa mãn phương trình tuyến tính
a1x1+ a2x2+ ... + anxn = α trong đó a1, a2, ..., an , α ∈R
* Tập hợp các điểm x=(x1, x2, ..., xn) ∈Rn thoản mãn bất phương trình
KIL
tuyến tính a1x1+ a2x2+ ... + anxn ≤ α được gọi là nửa không gian đóng.
* Nửa không gian được cho bởi a1x1+ a2x2+ ... + anxn < α được gọi là nửa
không gian mở.
* Tập X⊂Rn đượ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 ...
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
* 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.
M
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.
.CO
a11 x1 + a12 x 2 + ... + a1n x n ≤ b1
a x + a x + ... + a x ≤ b
21 1
22 2
2n n
2
.
. . . . . . . . . . . . . . . . . . . .
a n1 x1 + a n 2 x 2 + ... + a nn x n ≤ bn
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]
OKS
1.1.4 Hàm lồi
* Một hàm số f(x) xác định trên tập lồi C ⊂ Rn đượ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)
OBO
* Hàm f(x) xác định trên C đạt cực tiểu tuyệt đối tại x* ∈C nếu
f(x*) ≤ f(x):∀ x∈C
* 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):∀ x∈C ∩U
tuyệt đối.
KIL
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
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 đã
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
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ỹ.
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
n
∑c
j =1
n
j =1
x j → max
x j (≤, =, ≥ ) bi , i = 1, ..., m
ij
x j ≥ 0,
j = 1,..., n
OKS
∑a
j
.CO
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:
(1.1)
(1.2)
(1.3)
Ký hiệu: A=(aij)mxn là ma trận với các phần tử aij
(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à
n
f ( x ) = ∑ c j x j → min
j =1
x∈D
OBO
Thì giữ nguyên ràng buộc và đưa về bài toán Max bằng cách
n
f ( x ) = −∑ c j x j → max
j =1
x∈D
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à fmin=-fmax
Thật vậy, vì x* là nphương ánn tối ưu của bài toán Max nên ta có:
max
= −∑ c j x *j ≥ −∑ c j x j , ∀x ∈ D
j =1
KIL
f
hay
j =1
n
n
j =1
j =1
∑ c j x *j ≤ ∑ c j x j , ∀x ∈ D
Chứng tỏ x* là phương án tối ưu của bài toán Min và
n
f min = ∑ c j x *j = − f
j =1
max
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:
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
-Dạng chuẩn:
n
∑a
j =1
ij
x j ≤ bi , i = 1,..., m
x j ≥ 0,
j = 1,..., n
-Dạng chính tắc:
n
∑c
j =1
n
∑a
j =1
j
x j → max
.CO
n
x j → max
j
j =1
M
∑c
x j = bi , i = 1,...m
ij
OKS
x j ≥ 0, j = 1,..., n
Đư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
n
ij
x j ≥ bi
OBO
∑a
j =1
Có thể đưa về ràng buộc − ∑ j =1 a ij x j ≤ −bi bằng cách nhân hai vế với (-1) và
n
viết lại
∑
n
j =1
a ' ij x j ≤ b' i .
ii) Một ràng buộc đẳng thức
n
∑a
j =1
ij
x j = bi
KIL
có thể thay bằng hai ràng buộc bất đẳng thức:
n
∑a
j =1
ij
n
x j ≤ bi , − ∑ a ij x j ≤ −bi
j =1
iii) Một biến xj 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:
x j = x +j − x −j , víi x +j ≥ 0, x −j ≥ 0
iv) Một ràng buộc bất đẳng thức
n
∑a
j =1
ij
x j ≤ bi
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Có thể đưa về ràng buộc đẳng thức bằng cách đưa vào biến phụ yi ≥ 0:
∑a
j =1
ij
x j + y i = bi
M
n
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
.CO
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ố:
c1 x1 + c 2 x 2 → max
OKS
a i1 x1 + a i1 x 2 ≤ bi , i = 1,..., m
D=
x j ≥ 0, j = 1,2
Từ ý nghĩa hình học ta biết rằng mỗi bất phương trình tuyến tính ai1x1+ai2x2 ≤ bi
xác định một nửa mặt phẳng.
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 c1x1+c2x2=α 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
OBO
= (x1 ,điểm
x2 )
sẽ gọi là các đường mức (với giá trị mức α).xMỗi
∈D sẽ nằm
= c1 xvới
trên một đườngαmức
1 + cmức
2 x2 .
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
chúng
thì giá trị mức sẽ tăng, nếu dịch chuyển theo hướng ngược lại
KIL
n = (c1 , c 2 )
của
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 (c1,c2) 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)
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
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.
2 x1 + x 2 ≤ 8
x1 + 2 x 2 ≤ 7
x2 ≤ 3
x1 ≥ 0, x 2 ≥ 0
.CO
f(x)= 4x1+5x2→max
M
Ví dụ: Xét bài toán:
Xét đường mức: 4x1+5x2=10. Đường mức này đi qua hai điểm (0,2) và
(2.5,0). Ta có x*=(3,2), fmax=22
n
OKS
y
x*
x
OBO
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.
tối ưu.
KIL
- 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
- Nếu miền ràng buộc không giới nội nhưng 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.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
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
M
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
hợp lồi của các điểm đó.
.CO
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ổ
Ký hiệu Aj, 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:
(1.4)
OKS
x1A1 + x2A2 + ... + xnAn = b
Mệnh đề 3: Nếu các vector A1, A2, ..., Ak là độc lập tuyến tính và thoả mãn
x1A1+x2A2+...+xnAn=b
trong đó xj > 0, j=1,...k thì điểm
x=(x1,x2,...,xk,0,...,0)
là điểm cực biên của tập lồi đa diện D.
OBO
Mệnh đề 4: Nếu x =(x1,x2,...,xn) là điểm cực biên của tập lồi đa diện D thì
các vector Aj trong biểu diễn (1.4) ứng với các thành phần xj > 0 lập thành hệ
độc lập 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 =(x1,x2...,xn) là phương án cực biên của QHTT dưới dạng
KIL
chính tắc thì cần và đủ là các vector cột Aj của ma trận A ứng với các thành phần
xj > 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:
n
∑x
j =1
j
= 1, x j ≥ 0,
j = 1,..., n
(1.5)
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Mà tập hợp các điểm x∈Rn 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.
M
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
.CO
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
OKS
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:
(1.6)
Ax = b
(1.7)
x≥0
(1.8)
OBO
< c, x > → max
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:
KIL
J* = {j| xj > 0}
(1.9)
Vì các vector Aj, j∈J* là độc lập tuyến tính nên |J*| ≤ m (|J*| là số số phần
tử
xj >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.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Ta chọn một hệ thống m vector độc lập tuyến tính {Aj, j ∈ J}sao cho J ⊇
J*. Hệ thống đó gọi là cơ sở của x, các vector {Aj, j ∈ J} và các biến {xj, 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 Aj,
M
xj, 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*.
các vector cơ sở:
Ak = ∑ z jk A j
j∈J
.CO
Mỗi vector Ak phi cơ sở có thế biểu diễn dưới dạng tổ hợp tuyến tính của
(1.10)
Trong đó các hệ số zjk được xác định duy nhất bởi việc giải hệ phương
∑z
jk
j∈J
aij = aik , i =1, m
OKS
trình:
(1.11)
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=(x1, x2,...xm, 0,...0) và cơ sở của nó A1,, A2,...Am.
m
∑x
j =1
j
OBO
Đối với phương án cực biên này ta có:
A j = b, x j > 0,
j = 1,...., m
(1.12)
với giá trị của hàm mục tiêu:
m
∑c
j =1
j
x j = z0
Ta tính các đại
lượng sau:
m
∑z
Kí hiệu:
jk
c j = Zk
KIL
j =1
m
∆ k = Z k − c k = ∑ z jk c j − c k
(1.13)
(1.14)
(1.15)
j =1
Định lý 1.1: (Tiêu chuẩn tối ưu). Nếu đối với phương án cực biên
x=(x1,x2,...,xm,0...0) các điều kiện sau được thỏa mãn
∆ k ≥ 0, ∀k = 1, 2,....., n
thì x* là phương án tối ưu.
Chú ý:
(1.16)
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
• Trong (1.10) nếu Aj là một vector cơ sở, khi đó tồn tại chỉ một hệ số
zjj=1, tất cả các hệ số khác đều bằng 0 và ta có:
(1.17 )
∆ j = c j − c j = 0, j ∈ J
M
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, ∀k∉J
(1.18)
cũng là điều kiện cần của tối ưu.
.CO
• Người ta có thể chứng minh rằng nếu bài toán không thoái hoá thì (1.16)
Đị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’ > Z0.
OKS
Công thức tìm phương án x’:
Nhân (1.10) với θ nào đó ta có:
m
∑θ z
j =1
jk
A j = θ Ak
(1.19)
Lấy (1.12) trừ đi (1.19) từng vế ta có:
j =1
j
− θ z jk )A j + θ Ak = b
OBO
∑ (x
m
(1.20)
Nếu các hệ số của các vector Aj, j=1,.....,m và Ak trong (1.20) không âm,
Z'= Z0 −θ ∆k
(1.21)
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ị
Trong (1.12) tất cả các biến xj, j=1,...,m đều dương. Vì vậy có thể tìm được
θ > 0 sao cho
'
j
:
=
x
j
−
θ
x' j := x j − θ z jk ≥ 0, j = 1,....., m
z
jk
≥
0
,
j
=
1
,.....,
m
(3
.
29
)
KIL
x
(1.22)
Nếu đối với chỉ số k mà ∆k < 0, tồn tại zjk> 0, j∈J thì giá trị θ lớn nhất còn
thoả mãn (1.22) có thể xác định bởi hệ thức :
x j
z jk
θ 0 = min
j∈J
x
z jk > 0 = r
z rk
(1.23)
Nếu ta thay θ trong (1.20) và (1.21) bởi θo thì thành phần thứ r sẽ bằng 0:
xr- θozrk=0.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Như vậy ta nhận được phương án mới x’ với cơ sở Aj, j∈J\ {r}∪{k}=J’.
Nếu zjk ≤ 0, ∀j∈ J thì tất cả các thành phần xj- θ zjk trong (1.22) sẽ không
trị hàm mục tiêu tiến tới +∞ khi θ tiến tới +∞.
M
âm ∀θ >0, nghĩa là ta luôn có phương án ∀θ >0, nhưng từ (1.21) ta dễ thấy giá
Trong thực hành Dantzig đã chứng minh rằng các bước lặp sẽ giảm đáng kể
∆ s = min{∆ k
k
∆ k < 0}
.CO
nếu ta thay vector As thoả mãn:
(1.24)
và khi đó vector Ar được xác định theo công thức:
x j
z js
θ s = min
x
z js > 0, j ∈ J = r
z rs
(1.25)
x j − ( x r / z rs )z js ,
x' j =
x / z ,
r rs
OKS
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:
nếu j ≠ r
nếu j=r
A j , j ∈ J ' = J \ {r} ∪ {s}
(1.27 )
OBO
và cơ sở của nó là
(1.26)
Trên cơ sở lý thuyết đã nhận được, ta chuyển sang xét thuật toán đơn hình.
Thuật toán đơn hình
Giả sử ta đã đưa QHTT về dạng chính tắc:
cx=Z→ max
KIL
Ax=b
x≥0
Bước 1: Xây dựng bảng đơn hình xuất phát. 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.
•
Xác định các số zjk bởi hệ phương trình:
∑z
j∈J
•
jk
A j = Ak
Đối với mỗi k ∉ J , tính các ước lượng:
∆ k = ∑ z jk c j − c k
j∈J
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Còn với j∈J thì ∆j = 0.
•
Tính giá trị hàm mục tiêu
Z0 = ∑ c j x j
j∈J
M
Bước 2: Kiểm tra tối ưu.
Nếu ∆k ≥ 0, ∀k ∉ J thì x là phương án tối ưu, dừng thuật toán. Trái lại,
.CO
chuyển sang bước 3.
Bước 3: Tìm vector đưa vào cơ sở. Có hai khả năng xảy ra:
•
Tồn tại k∉J sao cho ∆k< 0 và zjk ≤ 0, ∀j∈J thì bài toán QHTT
không có lời giải tối ưu (Z không bị chặn trên). Dừng thuật toán.
chọn chỉ số s theo tiêu chuẩn:
∆ s = min{∆ k
OKS
Đối với mỗi k∉J sao cho ∆k< 0 đều tồn tại j ∈ J: zjk> 0. Khi đó
•
∆ k < 0}
Đưa vector As vào cơ sở.
Bước 4: Tìm vector loại khỏi cơ sở. Xác định
xj
θ s = min
z rs
x
z js > 0 = r
z rs
OBO
Và đưa vector Ar ra khỏi cơ sở.
Bước 5: Chuyển sang phương án cực biên mới và cơ sở mới. Cơ sở mới là
{Aj,j ∈J’} với J’= J\{r} ∪ z{s}. Phương án cực biên mới x’ được tính theo
(1.26), khai
triển của các véc tơ Ak theo các cơ sở mới được tính theo công thức (1.28).
Quay lên bước 2.
KIL
Chú ý. Đối với bài toán min
{〈c, x〉
Ax = b,
x ≥ 0} thì tiêu chuẩn tối ưu là
∆k≤ 0 (∀k) và vector As được chọn đưa vào cơ sở theo công thức:
∆ s = max{∆ k ∆ k > 0, k ∉ J }
Công thức đổi cơ sở và 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’.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Ta đã có công thức (1.26) để tính các thành phần của x’. Bây giờ ta thiết
lập công thức tính các số z’jk. Ta có:
As = ∑ z js A j ⇒
j∈J
1
z rs
As −
∑z
j∈J , j ≠ r
js
A j
M
Ar =
Ak =
∑z
j∈J ,
jk
Aj =
∑z
j∈J , j ≠ r
jk
A j + z rk Ar
Thay biểu thức của Ar vào ta được:
Ak =
∑z
j∈J ,i ≠ r
jk
Aj +
z rk
z rs
As −
∑z
js
j∈J , j ≠ r
A j =
.CO
Mặt khác
z
z
z jk − rk A j + rk As
z js
z rs
j∈J , j ≠ r
∑
OKS
Đây là công thức biểu diễn Ak qua cơ sở mới J’ =J\{r}∪{s}. Bởi vậy ta có:
z jk − (z rk / z rs )z js ,
z ' jk =
z / z ,
rk rs
nếu j≠r
(1.28),
nếu j=r
∆' k =
Sau khi có z’jk ta tính:
∑ z'
j∈J '
jk
(1.29)
c j − ck
1.1).
OBO
Để dễ tính toán, trong mỗi bước lặp ta thiết lập bảng đơn hình (xem bảng
Nếu tất cả các số trong dòng cuối (trừ hàm mục tiêu f) đều không âm, nghĩa
là ∆k≥0 ∀k, khi đó x là phương án tối ưu.
Bảng 1.1
Cơ
sở
Ph
án
KIL
cj
c1
...
cj
...
cr
...
cm
A1
...
Aj
...
Ar.
..
Am
x1
...
xj
...
xr
...
xm
f
c1 ... cj ... cr ... cm... ck... cs ... cn
Aa... Aj... Ar... Am...Ak... As... An
1
...
0
...
0
...
0
0
...
1
...
0
...
0
0
...
0
...
1
...
0
0
...
0
...
0
...
1
z1k
...
zjk
...
zrk
...
zmk
z1s
...
zjs
...
zrs.
..
zms
z1n
...
zjn
...
zrn.
..
zm
n
0... 0... 0...
0 ... ∆k ... ∆s... ∆n
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Nếu dòng cuối (không kể f ) có những số âm thì xem thử có cột nào cắt
dòng cuối ở một số âm mà mọi số trong cột đó đều âm hay không. Nếu có cột
nào như thế thì bài toán không có phương án tối ưu. Nếu trái lại thì chọn cột sao
M
∆ s = min{ ∆ k ∆ k < 0}
cho
Rồi chọn ( trong số các dòng cắt cột s ở những số dương ) dòng r sao cho:
x j
xr
= min
z js > 0
z rs
z js
.CO
θr =
Cột s gọi là cột quay. Vector Ar được đưa vào cơ sở. Dòng r gọi là dòng
quay. Vector Ar bị đưa ra khỏi cơ sở.
OKS
Phần tử zrs > 0 là giao của cột quay và dòng quay gọi là phần tử chính của
phép quay. Các phần tử zjs, j ≠ r gọi là phần tử quay.
Các công thức (1.26), (1.29) gọi là các công thức đổi cơ sở. Bảng đơn hình
mới suy được từ bảng cũ bằng cách thay cr, Ar trong dòng quay bằng cs, As. Sau
đó thực hiện các phép biến đổi dưới đây:
i) Chia mỗi phần tử ở dòng quay cho phần tử chính được số 1 ở vị trí của zrs
OBO
cũ. Kết quả thu được là dòng chính.
ii) Lấy mỗi dòng khác trừ đi tích của dòng chính nhân với phần tử quay
tương ứng được số 0 ở mọi vị trí còn lại của cột quay.
Dòng mới = dòng cũ tương ứng - dòng chính x phần tử quay
Lưu ý rằng sau phép quay thì ở vị trí ∆s ta thu được số 0 vì lúc này As trở
của bảng cũ.
KIL
thành vector đơn vị cơ sở, nghĩa là ta đã làm mất số âm nhỏ nhất ở dòng cuối
Toàn thể phép biến đổi trên gọi là phép quay xung quanh phần tử chính zrs.
Sau khi thực hiện phép quay ta có một phương án mới và một cơ sở mới. Nếu
chưa đạt yêu cầ nghĩa là còn ∆k <1 thì ta lại tiếp tục quá trình.
Chú ý: Trong bảng đơn hình ở bảng 1.1, không giảm tổng quát ta coi các
vector cơ sở được đánh số A1, A2, ..., Am, nghĩa là J = {1,2, ..., m}.
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
CHƯƠNG 2. BÀI TOÁN VẬN TẢI VÀ BÀI TOÁN VẬN TẢI MỞ RỘNG
2.1 Bài toán vận tải hai chỉ số
M
2.1.1 Phát biểu bài toán và tính chất
Có m địa điểm A1, A2, ..., An cùng sản xuất một loại hàng hóa với các
lượng hàng tương ứng là a1, a2, ..., an.
là b1, b2, ..., bn.
Để đơn giản ta sẽ gọi
Ai là điểm phát i, i=1, ..., m
OKS
Bj là điểm thu j, j=1, ..., n
.CO
Có n nơi tiêu thụ loại hàng hóa đó B1, B2, ..., Bn với các yêu cầu tương ứng
Hàng có thể chở từ một điểm phát bất kỳ (i) đến một điểm thu bất kỳ (j)
Ký hiệu:
cij - chi phí chuyên chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j).
xij - lượng hàng chuyên chở từ (i) đến (j).
Bài toán đặt ra là: xác định những đại lượng xij cho mọi con đường (i,j) sao
OBO
cho tổng chi phí chuyên chở là nhỏ nhất với giả thiết là:
Tức là lượng hàng phát ra bằng đúng lượng hàng yêu cầu ở các điểm thu
(điều kiện cân bằng thu phát).
Dạng toán học của BTVT là:
m
n
∑∑ c
i =1 j =1
ij
xij → min
KIL
n
∑ x ij = a i , i = 1, m
j =1
m
∑ x ij = b j , j = 1, n
i =1
x ≥ 0, i = 1, m ; j = 1, n
ij
m
n
a i , b j > 0; ∑ a i = ∑ b j
i =1
j =1
(2.1)
(2.2)
(2.3)
(2.4)
(I )
Hệ rằng buộc (2.2), (2.3) có m + n phương trình, m x n ẩn, tuy nhiên do (I)
nên bất kỳ phương trình nào trong m + n phương trình cũng là hệ quả của các
http://kilobooks.com
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
phương trình còn lại và có thể bỏ đi. Thật vậy, hệ rằng buộc có thể viết dạng
(2.5).
Giả sử ta cộng các phương trình từ thứ (m+1) tới thứ (m+n) rồi trừ đi tổng
M
các phương trình từ thứ (2) tới thứ (m) thì ta được phương trình thứ (1). Do đó
số phương trình cực đại của hệ (2.2), (2.3) không quá m + n-1.
m1
(1)
= a2
( 2)
+ xm 2 + . . . + xmn = a m
( m)
m1
.CO
x
+x
= a1
+ xm 2
OKS
x11 + x12 + . . . + x1n
x21 + x22 + . . . + x2 n
.....
+ x21 + . . .
x11
x12 +
x22
.....
+ x2 n
x1n
+ xmn
= b1
(m + 1)
= b2
( m + 2)
= bn
( m + n)
Ký hiệu ma trận của hệ (2.5) là A.
X = (x11, x12, ..., xij, ..., xmn) - Vector cột mxn thành phần.
C = (c11, c12, ..., cij, ..., cmn) - Vector hàng mxn thành phần.
P = (a1, a2, ..., am, b1, b2, ..., bn) - Vector cột vế phải.
OBO
Ta đưa BTVT về dạng.
min < C , X >
AX = P
X ≥ 0
(2.6)
(2.7)
(2.8)
Ta gọi Pij là cột của ma trận A ứng với biến xij. Vector này có 2 thành phần
bằng 1 tại dòng thứ i và dòng thứ m+j còn các thành phần khác bằng 0.
của BTVT.
KIL
Định nghĩa 1: Vector X thỏa mãn (2.7), (2.8) được gọi là một phương án
Một phương án đạt cực tiểu (2.6) gọi là phương án tối ưu.
Một phương án X gọi là phương án cơ sở nếu vector cột Pij của ma trận A
tương ứng với các xij > 0 là độc lập tuyến tính.
Định lý 2.1: BTVT luôn có phương án tối ưu.
Chứng minh:
1) Trước hết ta chứng minh BTVT luôn có phương án.
2) Sau đó chứng minh rằng miền rằng buộc giới nội.
(2.5)
- Xem thêm -