Giáo trình Quy hoạch tuyến tính

· · · · · · · · ·
cm A
m xm0 0 · · · 0 · · · 1 · · · xmj · · · 0
0 An+1 b′m+1 0 · · · 1 · · · 0 · · · xm+1,j · · · 1
0 · · · 1 · · · 0 · · · ∆j ≤ 0 · · · 0
trong đó:
b′m+1 = bm+1 −
m∑
i=1
am+1,ixi0 (4.4.18)
xm+1,j = am+1,j −
m∑
i=1
am+1,ixij (j = 1, 2, . . . , n). (4.4.19)
Nói cách khác là nhân dòng i, (i = 1, 2, . . . ,m) của bảng cuối cùng với −am+1,j
cộng tất cả lại, rồi cộng với hệ số tương ứng của ràng buộc bổ sung, kết quả được
đặt vào dòng m+ 1.
Ví dụ 4.4.1. Cho bài toán
f(x) = −x1 + 3x2 + x3 + 2x4 + x5 → min
x1 +3x2 +2x4 −9x5 = 5
3x2 −2x3 +2x4 −7x5 ≤ 19
3x2 −3x3 +x5 ≤ 15
xj ≥ 0, j = 1, 2, 3, 4, 5.
(a) Giải bài toán đã cho.
(b) Giải bài toán đã cho khi vế phải b = (5, 19, 15) được thay bởi b = (3, 14, 6).
Giải
60
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Ta dùng thuật toán hai pha. Đưa vào hai ẩn giải x6, x7 ta có bài toán phụ
f(x) = −x1 + 3x2 + x3 + 2x4 + x5 → min
x1 +3x2 +2x4 −9x5 = 5
3x2 −2x3 +2x4 −7x5 +x6 = 19
3x2 −3x3 +x5 +x7 = 15
xj ≥ 0, j = 1, 2, 3, 4, 5, 6, 7.
Ta có bảng sau:
c0 cơ x0 -1 3 1 2 1 1 1
sở b b x1 x2 x3 x4 x5 x6 x7
0 A1 5 1 0 3 2 -9 0 0
1 A6 19 0 3 -2 2 -7 1 0
1 A7 15 0 (3) -3 0 1 0 1
0 6 -5 2 -6 0 0
0 A1 5 1 0 3 2 -9 0
1 A6 4 0 0 1 (2) -8 1
0 A2 5 0 1 -1 0 1/3 0
0 0 1 2 -8 0
-1 A1 1 -5 1 0 2 0 (-1)
2 A4 2 4 0 0 1/2 1 -4
3 A2 5 2 0 1 -1 0 1/3
18 0 0 -5 0 -7
1 A5 5 -1 0 -2 0 1
2 A4 24 -4 0 -15/2 1 0
3 A2 1/3 1/3 1 -1/3 0 0
54 -7 0 -19 0 0
Đối với bài toán đã cho, ở bước 3 đã xuất hiện dấu hiệu tối ưu với phương án
tối ưu là x∗ = (1, 5, 0, 2, 0) và f(x) = 18.
61
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
2) Cơ sở tối bước 3 đối với bài toán đã cho là {A1, A4, A2}
B = [A1A4A2] =

1 2 0
0 2 3
0 0 3

Đặt x0 = (x1, x4, x2). Khi đó hệ x
0 = B−1b tương đương với Bx0 = b và có dạng
x1 +3x4 = 3
2x4 +3x2 = 14
3x2 = 6
⇔ x0 =

−5
4
2

Do x0 có thành phần âm nên x∗ không phải là phương án tối ưu của bài toán
mới và cần phải tiếp tục tính toán.
Đặt x0 vào cột b ở bước thứ 3 rồi tiếp tục thuật toán đơn hình đối ngẫu (chú ý
rằng, chỉ biến đổi cột b theo phần tử trục đã xác định khi giải bài toán ban đầu).
Ở bước 4, dấu hiệu tối ưu đối với bài toán mới xuất hiện là x˜ = (0, 1/3, 0, 24, 5)
giá trị tối ưu của hàm mục tiêu tại x˜ là 54.
4.5. Bài tập chương 4
Bài 4.1. Tìm giá trị tối ưu của hàm mục tiêu của các bài toán sau:
(a)
n∑
j=1
cjxj → max
n∑
j=1
ajxj ≤ β
xj ≥ 0, j = 1, 2, . . . , n
trong đó β, cj, aj, j = 1, 2, . . . , n là các số dương.
(b)
n∑
j=1
jxj → min
i∑
j=1
xj ≤ i, i = 1, 2, . . . , n
xj ≥ 0, j = 1, 2, . . . , n.
62
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Bài 4.2. Chứng tỏ bài toán sau có hàm mục tiêu không bị chặn
f(x) = −4x1 − 2x2 + 3x3 + 5x4 → min
x1 +x2 −4x3 ≥ 7
−2x1 +3x2 +3x3 −5x4 ≥ 10
2x1 +8x2 −4x3 +6x4 ≥ 16
xj ≥ 0, j = 1, 2, 3, 4.
Bài 4.3. Chứng minh rằng bài toán {tcx→ max : Ax ≤ b, x ≥ 0} có phương án
tối ưu nếu b ≥ 0 và ma trận A có ít nhất một dòng gồm toàn các số dương.
Bài 4.4. Chứng tỏ rằng x = (0, 1, 0, 3) là phương án tối ưu của bài toán
f(x) = −x1 − 3x2 + x3 − 2x4 → min
4x1 +12x2 +4x4 = 24
x1 +3x2 −x3 ≥ 3
4x1 −18x2 +2x3 +3x4 ≥ −33
xj ≥ 0, j = 1, 2, 3, 4.
Bài 4.5. Kiểm tra tính tối ưu của phương án x = (0, 0, 2,−2, 0) của bài toán:
f(x) = −2x1 + 4x2 − x3 − 2x4 + 2x5 → min
x1 +2x2 +3x3 +x4 ≥ −1
4x1 +x3 −5x4 +2x5 ≥ 5
3x1 −x2 +4x3 +3x4 −2x5 = 2
x1 ≥ 0, x2 ≥ 0,
63
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Bài 4.6. Biết rằng phương án tối ưu của bài toán
f(x) = 15x1 + 10x2 + 6x3 → min
3x1 +2x3 = 24
x1 +2x2 +2x3 ≥ 3
x1 +x2 +x3 ≥ 2
4x1 +2x2 −2x3 ≥ 1
x1 ≥ 1, x2 ≥ 0, x3 ≥ 0.
là x = (1, 5/4, 11/4). Hãy tìm phương án tối ưu của bài toán đối ngẫu.
Bài 4.7. Tìm tập phương án tối ưu của bài toán
f(x) = x1 + x2 + 2x3 − 2x4 − 4x5 → min
−x1 +x2 −3x3 +2x4 −2x5 = 8
−2x1 −x3 +x4 −x5 ≥ −21
3x1 +5x3 −3x4 +2x5 = 25
2x1 +x4 +4x5 ≤ 20
xj ≥ 0, j = 1, 2, 3, 4, 5.
biết rằng y = (1, 0, 1,−1) là phương án tối ưu của bài toán đối ngẫu.
Bài 4.8. Cho bài toán
f(x) = x1 + x2 − x3 → min
x1 +2x2 +x3 ≤ 7
4x1 +3x2 −6x3 ≤ 9
2x1 −x2 −8x3 ≤ −6
−2x2 +x3 ≤ 2
−2x1 −x2 +5x3 ≤ 1
−x1 +3x3 ≤ 1
x3 ≤ 0
64
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
(a) Chứng tỏ rằng các phương án x = (−4, 6,−1), y = (4/5, 0, 3.5, 0, 0, 1) theo
thứ tự là phương án tối ưu của bài toán đã cho và bài toán đối ngẫu của nó.
(b) Tìm tập phương án tối ưu của bài toán đã cho và bài toán đối ngẫu của nó.
Bài 4.9. Cho bài toán
f(x) = 2x1 + 3x2 + 5x3 + 4x4 → max x1 +2x2 +3x3 +x4 ≤ 5x1 +x2 +2x3 +3x4 ≥ 3
xj ≥ 0, j = 1, 2, 3, 4.
(a) Chứng tỏ rằng phương án x = (0, 1, 1, 0) là phương án tối ưu của bài toán
đã cho.
(b) Tìm tất cả các phương án tối ưu của bài toán đã cho thỏa mãn điều kiện
c3 + 5x4 = 1.
Bài 4.10. Cho bài toán:
f(x) = 5x1 − 9x2 + 5x3 + 7x4 + 3x5 → min
2x1 +6x2 −2x3 −2x4 +x5 ≤ −4
8x1 +2x3 +4x4 −x5 = 20
−x1 −x2 +x3 −x5 ≥ −1
xj ≥ 0, j = 2, 3, 4, 5.
(a) Chứng tỏ rằng phương án x = (0, 1, 0, 5, 0) là phương án tối ưu của bài toán
đã cho. Tìm tập phương án tối ưu của bài toán đối ngẫu.
(b) Hãy tìm tất cả các phương án tối ưu của bài toán đã cho có thành phần thứ
ba là x3 = 4.
65
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Bài 4.11. Cho bài toán
f(x) = 4x1 + 3x2 − 12x3 + αx4 + βx5 → min
2x1 +5x4 +x5 ≥ b1
3x2 −7x4 −x5 ≥ b2
−4x3 +2x4 −2x5 ≥ b3
x4 ≥ 0, x5 ≥ 0.
(a) Tìm tất cả các phương án cực biên của bài toán đã cho.
(b) Tìm điều kiện cần và đủ về các tham số α, β để bài toán đã cho có phương
án tối ưu với mọi b1, b2, b3.
(c) Với giá trị nào của α, β bài toán đã cho có hàm mục tiêu không bị chặn?
Bài 4.12. Cho bài toán
f(x) = x1 + 3x2 − 12x3 + αx4 + βx5 → min
2x1 +5x4 +x5 ≥ b1
3x2 −7x4 −x5 ≥ b2
−4x3 +2x4 −2x5 ≥ b3
x4 ≥ 0, x5 ≥ 0.
(a) Giải bài toán đã cho.
(b) Tìm tập phương án tối ưu của bài toán đã cho.
Bài 4.13. Cho bài toán
f(x) = −4x1 − x2 − 8x3 + 5x4 → min x1 +2x2 −2x3 +4x4 = 35x1 +3x2 +6x3 −x4 = 8
x4 ≥ 0, x5 ≥ 0.
66
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Hãy tìm tất cả các cơ sở đối ngẫu. Trong các cơ sở đối ngẫu hãy chỉ ra các cơ sở
tối ưu của bài toán đã cho.
67
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Chương 5.
BÀI TOÁN VẬN TẢI VÀ THUẬT
TOÁN THẾ VỊ
5.1. Bài toán vận tải
Trong mục 1.1., ta đã nêu dạng tổng quát của bài toán vận tải là
m∑
i=1
n∑
j=1
cijxij → min (1)
n∑
j=1
xij = ai, (i = 1, 2, . . . ,m) (2)
m∑
i=1
xij = bj, (i = 1, 2, . . . , n) (3)
xij ≥ 0, (i = 1, 2, . . . ,m, j = 1, 2, . . . , n) (4)
trong đó ai > 0, (i = 1, 2, . . . ,m, bj > 0, (j = 1, 2, . . . , n).
Đó là bài toán quy hoạch tuyến tính dạng chính tắc nhưng có cấu trúc khá đặc
biệt mà ta gọi nó là bài toán vận tải cổ điển.
Đặt a =
m∑
i=1
ai, b =
n∑
j=1
bj. Nếu a = b thì bài toán vận tải (1),(2),(3),(4) được gọi
là bài toán cân bằng thu phát..
Kí hiệu A là ma trận ràng buộc và
x = (x11, . . . , x1n, . . . , x21, . . . , x2n, . . . , xm1, . . . , xmn) ∈ Rmn (5.1.1)
c = (c11, . . . , c1n, . . . , c21, . . . , c2n, . . . , cm1, . . . , cmn) ∈ Rmn (5.1.2)
Thì bài toán vận tải được viết lại dưới dạng
f(x) =t cx→ min
Ax = A0
x ≥ 0.
68
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Trong bài toán vận tải, hệ Ax = A0 gồm m + n phương trình với n × m ẩn,
trong đó chỉ có m + n − 1 phương trình độc lập tuyến tính, mỗi phương trình là
hệ quả của các phương trình còn lại.
Sau này mỗi phương án ta viết dưới dạng ma trận cở m × n : x = (xij). Ta
cũng có ma trận cước phí cỡ m× n : c = (cij).
Như vậy, bài toán vận tải được coi là đã cho nếu biết vectơ lượng phát a =
(a1, a2, . . . , am), vectơ lượng thu b = (b1, b2, . . . , bn) và ma trận cước phí c = (cij).
Ta kí hiệu bài toán vận tải đó là 〈a, b, c〉.
Định lý 5.1.1 (Điều kiện có phương án tối ưu). Để bài toán vận tải (1),(2),(3),(4)
có phương án tối ưu, điều kiện cần và đủ là có điều kiện cân bằng thu phát a = b.
5.2. Các Tính chất của bài toán vận tải
5.2.1 Chu trình
Một dãy ô có dạng
(i1, j1), (i1, j2), (i2, j2), · · · , (ik, jk), (ik, j1) hay
(i1, j1), (i2, j1), (i2, j2), · · · , (ik, jk), (i1, jk) được gọi là một chu trinh (hai ô kế
tiếp cùng mằn trong một dòng hay một cột, ba ô liên tiếp không cùng mằn trên
một dòng hay một cột, ô đầu tiên và ô cuối cùng cũng được coi là hai ô liên tiếp).
Như vậy số ô trong một chu trình là một số chẵn không nhỏ hơn 4.
Tập ô Γ ⊂ U = {(i, j) : i = 1, 2, . . . ,m; j = 1, 2, . . . , n} được gọi là chứa chu
trình nếu như từ các ô của Γ có thể lập được ít nhất một chu trình. Nếu trái lại
thì ta nói Γ không chứa chu trình.
Định lý 5.2.2 (Điều kiện không chứa chu trình). Điều kiện cần và đủ để tập
ô Γ ⊂ U không chứa chu trình là hệ vectơ tương ứng với nó, tức là hệ {Aij : (i, j) ∈
Γ}, độc lập tuyến tính.
Hệ quả 5.2.3 (Số ô tối đa không chứa chu trình). Nếu bảng vận tải gồm m
dòng và n cột thì tập ô không chứa chu trình có tối đa là n+m− 1 ô.
69
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Định lý 5.2.4 (Chu trình duy nhất). Giả sử bảng vận tải gồm m dòng và n
cột, E là tập ô gồm m + n − 1 ô không chứa chu trình, (i, j) là một ô của bảng
không thuộc E. Khi đó F = E ∪ {i, j} có một chu trình duy nhất qua ô (i, j).
Định lý 5.2.5 (Dấu hiệu tập không chứa chu trình). Giả sử F là một tập
gồm m+n ô chứa chu trình duy nhất V và (i, j) ∈ V . Khi đó tập ô E = F \{(i, j)}
sẽ không chứa chu trình.
Định lý 5.2.6 (Điều kiện cực biên). Phương án x = (xij) của bài toán vận tải
(1),(2),(3),(4) là phương án cực biên khi và chỉ khi tập ô chọn tương ứng với nó,
tức là tập ô
H(x) = {(i, j) : xij > 0} (5.2.3)
không chứa chu trình.
Định lý 5.2.7 (Điều kiện chứa ít nhất một chu trình). Tập ô không rỗng Γ ⊂
U sẽ chứa ít nhất một chu trình nếu trong mỗi dòng và mỗi cột của bảng vận tải
hoặc là không có ô nào của Γ, hoặc có ít nhất hai ô của Γ.
5.3. Vấn đề tính các ước lượng
Giả sử bằng cách nào đó ta đã tìm được phương án cực biên x = (xij) của bài toán
vận tải với tập ô chọn H(x) gồm m+n− 1 ô (kể cả ô chọn-không) không chứa chu
trình. Theo thuật toán đơn hình để xét tính tối ưu của x ta phải tìm được các ước
lượng ∆ij ứng với mỗi vectơ A
ij ngoài cơ sở của x, tức là ứng với mỗi ô loại (i, j).
Chúng ta dễ dàng chứng minh được
∆ij =
∑
(i,j)∈V c
cij −
∑
(i,j)∈V l
cij (5.3.4)
trong đó, V c và V l theo thứ tự là tập hợp các ô mang số hiệu chẵn lẻ của V .
Ví dụ 5.3.1. Bài toán vận tải và phương án cực biên x ban đầu của nó được cho
bởi bảng
70
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
trong đó các cước phí ghi ở góc trên bên trái mỗi ô, các thành phần cơ sở của
phương án cực biên x ban đầu được ghi ở góc đối diện (các thành phần phi cơ sở
bằng 0). Có 9 ô loại là các ô (1, 3), (1, 4), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 2), (4, 4).
Ta hãy lập bảng tính ∆ij với A
ij ngoài cơ sở, tức là với các ô loại (i, j). Trước
hết ta hãy tính ∆32. Tập ô gồm ô (3, 2) và các ô chọn chứa chu trình duy nhất gồm
6 ô, được thể hiện bởi được thể hiện bởi đường nét đứt trên bảng. Các ô này cùng
với số hiệu của nó và cước phí tương ứng là
Ô trong chu trình (3,2) (3,4) (2,4) (2,1) (1,1) (1,2)
Số hiệu 1 2 3 4 5 6
cij 30 16 18 68 40 15
Theo công thức (5.3.4) ta có
∆32 = 16− 18 + 68− 40 + 15− 30 = 11
71
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Tương tự ta cũng tính được
∆13 = 40− 30 + 13− 35 = −12,
∆14 = 40− 68 + 18− 100 = −100,
∆22 = 68− 40 + 15− 51 = −8,
∆23 = 68− 30 + 13− 53 = −2
∆31 = 16− 18 + 68− 120 = −54
∆33 = 16− 18 + 68− 30 + 13− 150 = −101
∆42 = 30− 40 + 15− 54 = −49
∆44 = 30− 68 + 18− 80 = −100
Việc tính các ước lượng theo công thức (5.3.4) là khá đơn giản nhờ hình ảnh trực
quan của khái niệm chu trình, nhưng sẽ đơn giản hơn nếu ta ứng dụng định lý
dưới đây
Định lý 5.3.2 (Phương pháp đơn giản xác định các ước lượng). Nếu ta thay
ma trận cước phí c = (cij) bởi ma trận c
′ = (c′ij), trong đó c
′
ij = cij + ri + sj, tức
là nếu ta cộng vào cước phí ở mỗi ô của dòng i với cùng một số ri, cộng vào cước
phí ở mỗi ô của cột j với cùng một số sj thì sẽ được một bài toán vận tải mới
tương đương với bài toán vận tải ban đầu (theo nghĩa hai bài toán có chung tập tập
phương án tối ưu).
Định lý 5.3.3 (Dấu hiệu tối ưu). Giả sử x = (xij) là một phương án cực biên
của bài toán vận tải với tập ô chọn H(x) và c′ij = 0 với mọi ô (i, j) ∈ H(x) (tức là
đã quy-không các ô chọn).
(a) Nếu c′ij ≥ 0 với mọi ô (i, j) /∈ H(x) thì x là phương án tối ưu của bài toán.
(b) Nế tồn tại ô (i, j) /∈ H(x) sao cho c′ij < 0 thì ta có thể xây dựng được phương
án cực biên x′ tốt hơn x, nếu x không suy biến (nói chung x′ không xấu hơn
x).
72
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
5.4. Một số phương pháp xây dựng phương án
cực biên ban đầu
Dưới đây ta nêu ra ba phương pháp, đó là phương pháp góc tây bắc, phương pháp
cực tiểu theo bảng và phương pháp Vaugen. Đối với bảng vận tải gồm m dòng và
n cột, việc tìm tập ô chọn gồm m+ n− 1 ô không chứa chu trình được tiến hành
bằng phương pháp quy nạp theo m+ n là tổng số dòng và cột của bảng vận tải.
Nếu m+ n = 2 thì bảng gồm một ô duy nhất. Do điều kiện cân bằng thu phát
nên a1 = b1. Đối với cả ba phương pháp ấy điều chọn ô (1,1) và đặt x11 = a1. Đó
là phương án cực biên vì A11 6= 0và rõ ràng có n + m− 1 = 1 ô chọn không chứa
chu trình.
Giả sử đã biết cách xây dựng phương án cực biến ban đầu theo cả ba phương
pháp với bảng có m+n ≤ k− 1, khi đó đối với bảng mà m+n = k ta sẽ tiến hành
như sau:
Nếu as ≤ bt thì xst = as và xóa ngay dòng s; bt được thay bởi b′t = bt − as.
Nếu as > bt thì xst = bt và xóa ngay cột t; as được thay bởi a
′
s = as − bt.
Sau khi xóa đi, ta được bảng mới gồm m+n = k−1, trên đó đã xây dựng được
phương án cực biên (theo giả thuyết qui nạp) với tập ô chọnH gồm n+m−1 = k−2
ô. Dễ thấy rằng H ∪ {s, t} là tập gồm k− 1 ô chọn (đối với bảng mới) không chứa
chu trình, bởi vì nếu trái lại thì chu trình ắt phải qua ô (s,t) nhưng điều này không
thể được vì dòng s cột t đã bị xóa. Như vậy, với bảng mà m+ n = k ta xây dựng
được phương án cực biên với tập ô chọn H ∪ {s, t} gồm k − 1 ô.
Như vậy, ở mỗi bảng hình thành trong quá trình phân phối (kể cả bảng đầu
tiên) sau khi phân phối tối đa vào ô (s,t) nào đó ta xóa chỉ một dòng hoặc một cột
để được một bảng mới.
Việc chọn ô (s, t) là ngẫu nhiên, nhưng ta thường dùng các phương pháp sau:
(1) Phương pháp góc tây bắc: (s,t) là ở góc trên bên trái của bảng (ở mỗi bước).
(2) Phương pháp cực tiểu theo bảng (s, t) là ô sao cho cst = min cij trong đó cực
tiểu được chọn theo ô (i,j) của bảng (ở mỗi bước).
73
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Bảng 5.4.1: Phương pháp tây bắc
Bảng 5.4.2: Phương pháp Vaugen
(3) Phương pháp Vaugen Với mỗi dòng và mỗi cột ta điều tính hiệu của cước phí
thấp thứ nhì và thấp thứ nhất (ta gọi hiệu đó là độ chênh lệch của dòng hay
cột đó). Chọn dòng (hay cột) có độ chênh lệch lớn nhất. Trên dòng (hay cột)
đã chọn ta sẽ chọn ô (s,t) có cước phí thấp nhất.
Ví dụ 5.4.1. Dưới đây là các phương án cực biên ban đầu tìm được bằng phương
pháp góc tây bắc và phương pháp Vaugen.
74
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
5.5. Thuật toán thế vị
Phương pháp đã nêu trên đây để tìm phương án tối ưu của bài toán vận tải với
các bước cụ thể sau đây được gọi là thuật toán thế vị.
Bước 1. Tìm phương án cực biên ban đầu x = (xij).
Bước 2. Quy-không các ô chọn. Nếu c′ij ≥ 0 với mọi ô (i, j) của bảng thì kết
thúc việc tính toán và kết luận x là phương án tối ưu. Nếu trái lại, tức là tồn tại
ô (i,j) sao cho cij < 0 thì chọn c
′
st = min{c′ij : c′ij < 0} và chuyển sang bước 3.
Bước 3. Lập chu trình V đi qua ô (s,t) và số ô xác định nào đó của H(x).
Tính
θ = min{xij : ij ∈ V c}. (5.5.5)
chuyển sang bước 4.
Bước 4. Xây dựng x′ = (xij) theo công thức
x′ij =

xij + θ nếu(i, j) ∈ V l
xij − θ nếu(i, j) ∈ V c
xij nếu(i, j) ∈ V
(5.5.6)
cho x′ đóng vai trò của x và quay lại bước 2.
Ví dụ 5.5.1. Giải bài toán vận tải 〈a, b, c〉 với vectơ lượng phát a = (100, 400, 230)
vectơ lượng thu b = (320, 180, 110, 120) và ma trận cước phí
c =

5 3 16 9
5 3 7 8
1 8 12 10

Giải
Bằng phương pháp góc tây bắc ta thu được phương án cực biên đấu tiên suy biến,
trong đó có một ô-chọn-không, đó là ô (2,3) (sau khi phân phối tối đa lần thứ bao
với x22 = 180, nếu xóa dòng 2 thì ô-chọn-không là ô (3,2)).
75
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
76
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
Từ đó ta có phương án tối ưu
x∗ =

0 100 0 0
90 80 110 120
230 0 0 0

với giá trị tối ưu của hàm mục tiêu là
f∗ = 110.3 + 90.5 + 80.3 + 110.7 + s120.8 + 230.1 = 2950.
5.6. Tiêu chuẩn tối ưu. Bài toán đối ngẫu của bài
toán vận tải
5.6.1 Tiêu chuẩn tối ưu
Giả sử x = (xij) là một phương án của bài toán vận tải (1),(2),(3),(4).
Theo 4.1.6 thì điều kiện cần và đủ để phương án x là phương án tối ưu của bài
toán vận tải là tồn tại vectơ
y = (u, v) = (u1, . . . , um, v1, . . . , vm) ∈ Rm+n (5.6.7)
77
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
sao cho
ytAij ≤ cij nếu xij = 0
ytAij = xij xij > 0
Do tính chất đặc biệt của vectơ Aij nên ta có
ytAij = ui + vj (i = 1, 2, . . . ,m; j = 1, 2, . . . , n) (5.6.8)
Từ đó suy ra rằng:
Điều kiện cần và đủ để phương án x = (xij) là phương án tối ưu của bài toán
(1),(2),(3),(4) là tồn tại các số ui với i = 1, 2, . . . ,m và vj với j = 1, 2, . . . , n sao
cho
ui + vj ≤ cij xij = 0
ui + vj = cij xij > 0
Nếu x là phương án tối ưu của bài toán vận tải (1),(2),(3),(4) thì y = (u, v) là
phương án tối ưu của bài toán đối ngẫu.
5.6.2 Bài toán đối ngẫu của bài toán vận tải
Bài toán vận tải là bài toán quy hoạch tuyến tính dạng chính tắc. Chú ý đến
(5.6.8), bài toán đối ngẫu của nó dạng
m∑
i=1
aiui +
n∑
j=1
bjvj → max
ui + vj ≤ cij (i = 1, 2, . . . ,m, j = 1, 2, . . . , n)
Từ điều kiện cần và đủ để bài toán vận tải (1),(2),(3),(4) nhận phương án x
làm phương án tối ưu nêu trên, ta rút ra kết luận:
Nếu (r, s) = (r1, . . . , rm, s1, . . . , sn) là một hệ thống thế vị ứng với phương án
tối ưu thì
(−r,−s) = (−r1, . . . ,−rm,−s1, . . . ,−sn)
là phương án tối ưu của bài toán đối ngẫu.
78
Chỉ mục
Đ
Đánh thuế, 31
Đối ngẫu, 42
Đối ngẫu mạnh, 44
Đối ngẫu yếu, 43
Độ chênh lệch, 74
Độ lệch bù, 45
Đa diện lồi, 15
Điểm cực biên, 15
Đoạn thẳng, 14
Ư
Ước lượng, 21
B
Bài toán gốc, 42
Bài toán mở rộng, 55
Bài toán quy hoạch, 3
Bài toán vận tải, 68
Bài toán vận tải đối ngẫu, 78
Bảng đơn hình, 24
Bổ trợ, 27
BT lập kế hoạch sản xuất, 3
BT QHTT tổng quát, 5
BT vận tải, 4
C
Cân bằng thu phát, 68
Cặp ràng buộc đối ngẫu, 42
Cơ sở ban đầu, 27
Chứa chu trình, 69
Chu trình, 69
D
Dạng chính tắc, 6
Dạng chuẩn tắc, 6
H
Hai pha, 28
M
Ma trận cước phí, 69
P
Phương án cực biên, 15
Phương pháp đồ thị, 8
Phương pháp cực tiểu theo bảng,
73
Phương pháp góc tây bắc, 73
Phương pháp Vaugen, 74
S
Số phương án cực biên, 16
Suy biến, 27
79
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
T
Tính lồi, 15
Tập lồi, 14
Tập lồi đa diện, 15
Tổ hợp lồi, 14
Thuật toán đơn hình, 24, 35, 47
Thuật toán thế vị, 75
V
Vận tải cổ điển, 68
80
Quy hoạch tuyến tính Trường ĐHSP Đồng Tháp
DANH SÁCH ĐỊNH LÝ
2.1.2. Tính chất bắc cầu của tổ hợp lồi
2.1.4. Tính chất của tập lồi
2.2.1. Tính lồi của tập phương án
2.2.2. Tính lồi của tập phương án
2.3.1. Điều kiện là phương án cực biên
2.3.3. Phương án cực biên tối ưu
2.3.4. Điều kiện có phương án tối ưu
3.1.2. Dấu hiệu tối ưu
3.1.3. Dấu hiệu hàm mục tiêu không bị chặn
3.1.4. Dấu hiệu xây dựng được phương án tối hơn
3.2.9. Quan hệ giữa bài toán gốc và M -lớn
4.1.4. Đối ngẫu yếu
4.1.6. Đối ngẫu mạnh
4.1.7. Sự tồn tại phương án
4.1.8. Độ lệch bù
5.1.1. Điều kiện có phương án tối ưu
5.2.2. Điều kiện không chứa chu trình
5.2.4. Chu trình duy nhất
5.2.5. Chu trình duy nhất
5.2.6. Điều kiện cực biên
5.2.7. Điều kiện chứa ít nhất một chu trình
5.3.2. Phương pháp đơn giản xác định các ước lượng
5.3.3. Dấu hiệu tối ưu (bài toán vận tải)
81