ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐỖ HOÀNG TÙNG
THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU VÀ ỨNG DỤNG
TRONG TÁI TỐI ƯU HÓA VỚI RÀNG BUỘC PHỤ
(The dual simplex method and its applications to
reoptimization with supplementary constraints)
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
GS.TS. TRẦN VŨ THIỆU
Thái Nguyên - 2015
MỤC LỤC
Trang
MỞ ĐẦU
3
Chương 1. Kiến thức về qui hoạch tuyến tính
5
3.1. Vấn đề tái tối ưu hóa
28
3.2. Thuật toán đơn hình đối ngẫu trong tái tối ưu hóa
29
3.3. Ví dụ minh họa
30
KẾT LUẬN
34
TÀI LIỆU THAM KHẢO
35
2
MỞ ĐẦU
Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến
tính với các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Qui hoạch tuyến
tính có nhiều ứng dụng rộng rãi trong lý thuyết và thực tiễn.
Với mỗi bài toán qui hoạch tuyến tính đã cho (gọi là bài toán gốc) được gắn
với một bài toán qui hoạch tuyến tính khác (gọi là bài toán đối ngẫu). Hai bài toán
này có quan hệ chặt chẽ với nhau và là cặp bài toán đối ngẫu của nhau. Nghiên cứu
cơ bản cần thiết về qui hoạch tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu,
các định lý đối ngẫu trong qui hoạch tuyến tính, với nhiều ví dụ số và hình vẽ minh
họa cho các sự kiện, các định lý đã trình bày. Cuối chương giới thiệu ý tưởng cơ
bản của phương pháp đơn hình gốc, đơn hình đối ngẫu giải qui hoạch tuyến tính.
• Chương 2 "Thuật toán đơn hình đối ngẫu " trình bày chi tiết các bước tính
toán của thuật toán đơn hình đối ngẫu dạng đầy đủ và thuật toán đơn hình đối ngẫu
dạng cải biên. Cuối chương trình bày ví dụ áp dụng thuật toán đơn hình đối ngẫu
dạng đầy đủ vào giải bài toán trò chơi ma trận.
• Chương 3 “Kỹ thuật tái tối ưu hóa với ràng buộc phụ” trình bày vấn đề tái
tối ưu hóa khi thêm ràng buộc vào bài toán sau khi đã giải xong và vai trò của việc
áp dụng thuật toán đơn hình đối ngẫu trong tái tối ưu hóa. Cuối chương nêu ví dụ
minh họa.
Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có
những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác
giả tiếp tục hoàn thiện luận văn sau này.
Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Trần
Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành
cảm ơn các thầy giáo, cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên,
Viện Toán hoc - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và
tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.
4
Chương 1
KIẾN THỨC VỀ QUI HOẠCH TUYẾN TÍNH
Chương này trình bày tóm tắt một số kiến thức cơ bản cần thiết về qui hoạch
tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu, các định lý đối ngẫu trong qui
hoạch tuyến tính và phương pháp đơn hình gốc, đơn hình đối ngẫu giải qui hoạch
Định nghĩa 1.1. Một nghiệm chấp nhận được x ∈ D mà đồng thời là một đỉnh
của D được gọi là một nghiệm cơ sở hay một phương án cực biên, nghĩa là x không
thể biểu diễn được dưới dạng một tổ hợp lồi của bất kỳ hai nghiệm chấp nhận được
(phương án) nào khác của bài toán.
Định lý sau nêu một tính chất đặc trưng cho phương án cực biên (nghiệm cơ
sở) của bài toán qui hoạch tuyến tính chính tắc với giả thiết m ≤ n và rank (A) = m.
Định lý 1.3. Để một nghiệm chấp nhận được x = { x1 , x 2 , ... , x n } của qui
hoạch tuyến tính chính tắc là nghiệm cơ sở thì cần và đủ là các véctơ cột Aj 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.
Người ta phân ra hai loại nghiệm cơ sở: không suy biến nếu nghiệm đó có số
thành phần dương bằng m và suy biến nếu nó có số thành phần dương nhỏ hơn m.
Định lý sau cho thấy qui hoạch tuyến tính chính tắc có phương án cực biên.
Định lý 1.4. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có ít nhất một
phương án thì nó cũng có phương án cực biên, nghĩa là tập ràng buộc D có đỉnh.
Định lý sau cho phép tìm phương án tối ưu của bài toán qui hoạch tuyến tính
chính tắc trong số các phương án cực biên của bài toán (số này hữu hạn).
Định lý 1.5. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có phương án
tối ưu thì nó cũng có phương án cực biên tối ưu.
Ví dụ 1.1. Xét bài toán qui hoạch tuyến tính
f(x) = x1 + x2 min,
với các điều kiện:
x1 3x2 2, 3x1 x2 14, x1 0,
x1 + 4x2 22, x1 + x2 3, x2 0.
6
Tập ràng buộc của bài toán là đa giác lồi 6 đỉnh vẽ ở Hình 1.1. Tọa độ các
đỉnh: O = (0, 0), A = (2, 0), B = (5, 1), C = (6, 4), D = (2, 5), E = (0, 3). Theo Định
(Q)
max {g(y) = bTy : ATy ≤ c, y ≥ 0}
(AT là ma trận chuyển vị của ma trận A).
Ví dụ 1.2. Đối ngẫu của bài toán qui hoạch tuyến tính chuẩn tắc
f(x) = 20x1 + 15x2 min,
3x1 + x2 60,
7
x1 + x2 40,
x1 + 2x2 60,
x1 0, x2 0,
là bài toán qui hoạch tuyến tính:
g(y) = 60y1 + 40y2 + 60y3 max,
3y1 +
y2 + y3 20,
y1 +
y2 + 2y3 15,
y1 0, y2 0, y3 0.
• Đối ngẫu của qui hoạch tuyến tính dạng chính tắc (qui hoạch gốc):
(P)
min {f(x) = cTx : Ax = b, x ≥ 0}
2y1
2y2 +
y1
+
y3
0,
2y3 0,
3y3 0,8
y1
0,6.
+ y2
Dễ kiểm tra lại rằng lấy đối ngẫu của bài toán đối ngẫu ta được lại bài toán
gốc. Vì thế ta gọi (P) và (Q) là cặp bài toán qui hoạch tuyến tính đối ngẫu nhau.
8
1.2. CÁC ĐỊNH LÝ ĐỐI NGẪU
Các kết quả nêu dưới đây đúng cho cặp bài toán đối ngẫu (P), (Q) dạng bất kỳ.
Định lý 1.6 (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của bài
toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì
x1, x2 tuỳ ý
y1 0, y2 0
b) Bài toán gốc và bài toán đối ngẫu có phương án.
f(x) = 5x1 + 10x2 min,
g(y) = 14y1 + 12y2 max,
9
2x1 + 3x2 14
2y1 +
x1 + 4x2 12
y2 5
3y1 + 4y2 10
x1 0, x2 0
y1 0, y2 0
Phương án tối ưu của hai bài toán là x* = (4; 2) và y* = (2; 1) với f(x*) =
g(y*) = 40.
c) Bài toán gốc và bài toán đối ngẫu đều không có phương án tối ưu.
f(x) = x1
a ij yi ) = 0 j = 1, 2, ... , n ⇔ xT(c ATy) = 0.
i 1
Ví dụ 1.4. Xét cặp bài toán đối ngẫu chuẩn tắc:
min {4x1 : x1 + x2 2, x1 x2 2, xj 0, x2 0} và
max {2y1 + 2y2 : y1 + y2 4, y1 y2 0, y1 0, y2 0}.
y2
x2
4
2
y*
2
0
4
2
x1
y1
0
x*
Bài toán đối ngẫu của (P) có dạng (với y ℝm, s ℝn):
(Q)
max {g(y) = bTy : ATy c} = max {bTy : ATy + s = c, s 0}.
Định nghĩa 1.2. Giả sử B là ma trận con cấp mm của A. Nếu B có hạng m
thì ta nói B là một cơ sở của A.
Giả sử cơ sở B gồm m véctơ cột A j , A j , … , A j của A.
1
2
m
Ký hiệu J = {j1, j2, ... , jm}. Để cho tiện, đôi khi ta cũng gọi J là cơ sở. Các
véctơ Aj và các biến xj với j J lần lượt được gọi là các véctơ cơ sở và biến cơ sở.
Còn các véctơ Aj và các biến xj với j J gọi là các véctơ và biến ngoài cơ sở.
Đặt N = {Ak : k J}, xB = (xj : j J)T, xN = (xj : j J)T, cB = (cj : j J), cN =
x
(cj : j J). Khi đó, x, c ℝ n tách thành x = B , cT = (cB, cN) (véctơ hàng). Do
xN
rank (B) = m nên tồn tại ma trận nghịch đảo B1. Mỗi véctơ cột Ak (k = 1, 2, ... , n)
của ma trận A được biểu diễn qua các véctơ cơ sở Aj, j J như sau:
11
Ak = z jk A j = z1kA j + z2kA j + ... + zmkA j với k = 1, ... , n.
jJ
nhận được đối ngẫu nếu N 0 và là cơ sở tối ưu nếu B-1b 0 và N 0.
Định lý 1.10. Nếu B là cơ sở tối ưu (tức là B-1b 0 và N 0) thì
a) x = (xB = B-1b, xN = 0)T là nghiệm tối ưu của bài toán gốc,
b) yT = cBB-1, s = (sB = 0, sN = N)T là nghiệm tối ưu của bài toán đối ngẫu.
Chứng minh suy từ hệ thức đối ngẫu cTx = cBxB = cBB-1b = yTb.
Phương pháp đơn hình gốc xuất phát từ một cơ sơ B chấp nhận được gốc
(tức là B-1b 0) và nghiệm cơ sở của (P): xB = B-1b, xN = 0. Nếu với cơ sở đó N
0 thì B là cơ sở tối ưu: dừng thuật toán. Còn nếu N có thành phần dương, chẳng
hạn s > 0 với s J, thì có thể giảm giá trị hàm mục tiêu cTx bằng cách đưa biến xs
12
vào cơ sở và tìm đưa ra khỏi cơ sở biến xr (r J) thích hợp. Làm như thế ta sẽ thu
được một nghiệm cơ sở mới tốt hơn nghiệm cơ sở cũ (hay ít ra không kém), tương
ứng với cơ sở mới B’ (thay cho cơ sở cũ B). Thuật toán lặp lại với cơ sở B’, cho tới
khi đạt tới phương án tối ưu hoặc khi phát hiện bài toán có trị tối ưu vô cực.
Định lý 1.11. (Dấu hiệu bài toán có trị tối ưu vô cực). Nếu với cơ sở B chấp
nhận được gốc tồn tại chỉ số k J sao cho ước lượng k > 0 và zjk 0, j J thì
bài toán gốc (P) đã cho có trị tối ưu vô cực (- ∞ đối với bài toán min).
Phương pháp đơn hình đối ngẫu xuất phát từ một cơ sơ B chấp nhận được
đối ngẫu (tức là N 0) và "giả" nghiệm cơ sở của (P): xB = B-1b, xN = 0 (gọi là
“giả” vì xB có thể có thành phần âm). Nếu B-1b 0 thì B là cơ sở tối ưu: dừng thuật
toán. Còn nếu B-1b có thành phần âm, chẳng hạn (B-1b)r < 0 với r J, thì có thể cải
tiến (trường hợp này là tăng) trị mục tiêu cTx bằng cách đưa biến xr ra khỏi cơ sở và
tìm đưa vào cơ sở một biến ngoài cơ sở xs (s J) thích hợp và ta sẽ thu được một
cơ sở mới B’ (thay cho cơ sở cũ B). Thuật toán lặp lại với cơ sở mới B’, cho tới khi
đạt tới phương án tối ưu hoặc khi phát hiện bài toán gốc không có phương án.
Nếu (B-1b)r < 0 với r J và zrk 0 k J thì đó là dấu hiệu cho biết (P)
không có nghiệm chấp nhận được (D = ).
Tóm lại, chương này đã nhắc lại một số kiến thức cơ bản về bài toán qui hoạch
phương án). Các bảng đơn hình được biến đổi sao cho luôn đảm bảo điều kiện tối
ưu và quá trình này tiếp diễn cho đến khi nhận được phương án (không còn phần tử
âm trong cột Giả phương án). Phương án đó sẽ là phương án tối ưu.
Phương pháp đơn hình đối ngẫu thường được sử dụng khi ta chưa biết một
phương án cực biên nào của bài toán gốc, nhưng lại có sẵn một phương án cực biên
14
của bài toán đối ngẫu. Chẳng hạn, khi bài toán cần giải có dạng chuẩn và véctơ hệ
số mục tiêu c 0:
min {f(x) = cTx : Ax b, x 0} (vế phải b tuỳ ý)
Bài toán đối ngẫu có dạng
max{g(y) = bTy : ATy c, y 0}.
Rõ ràng y0 = 0 là một phương án cực biên của bài toán đối ngẫu, bởi vì ATy0 =
0 c.
2.1.2. Thuật toán đơn hình đối ngẫu
Các bước tiến hành thuật toán đơn hình đối ngẫu như sau:
Bước 1. Lập bảng đơn hình đối ngẫu ban đầu (xem các ví dụ minh hoạ 2.1,
2.2 dưới đây).
Bước 2. Kiểm tra tối ưu: Nếu mọi phần tử trong cột giả phương án đều không
âm thì dừng quá trình giải và ta nhận được phương án tối ưu của bài toán đã cho.
Trái lại, chuyển sang Bước 3.
Bước 3. Chọn dòng quay: Đó là dòng đầu tiên từ trên xuống mà nó chứa phần
tử âm nhỏ nhất trong cột giả phương án.
Bước 4. Chọn cột quay: Chia các phần tử trên dòng ước lượng (cuối mỗi
bảng) cho các phân tử tương ứng trên dòng quay, nhưng chỉ chia cho những phần
tử âm trên dòng quay. Cột quay là cột đầu tiên từ trái sang phải ứng với số nhỏ nhất
trong các tỉ số đó.
bảng đầu tiên ghi lại các hệ số trong bài toán, chỉ khác là cột “Phương án” bây giờ
được thay bằng cột “Giả phương án”, vì trong thành phần của “phương án” xuất
phát có các phần tử âm. Bảng này tương ứng với giả phương án ban đầu x0 = (0, 0,
0, 160, 140), f0 = f(x0) = 0.
Biến
cơ sở
CB
Giả phương
x1
x2
x3
x4
x5
án
15
12
10
0
0
1
0
15
12
10
0
0
Bảng 1
x2
12
40
3/4
1
1/2
3
0
x2
12
25
7/8
1
0
3/8
1/4
x3
10
30
1/4
0
10
3, 2 = 5).
Phần tử quay bằng 4 (trong ô được tô bóng mờ). Biến đổi bảng này theo qui
tắc đơn hình ta nhận được Bảng 2.
Trong Bảng 2, cột giả phương án vẫn còn phần tử âm. Ta chọn dòng x5 làm
dòng quay và chọn cột x3 làm cột quay. Phần tử quay bằng 2. Biến đổi Bảng 2 ta
nhận được Bảng 3. Trong bảng này, mọi phần tử trong cột giả phương án đều
dương nên ta nhận được phương án tối ưu: x* = (0, 25, 30) với fmin = 600.
Từ các kết quả tính toán nêu trên, ta cũng có thể tìm được lời giải của bài toán
đối ngẫu nhờ vận dụng qui tắc sau đây:
Qui tắc B. Nếu cơ sở ban đầu là ma trận đơn vị thì để tìm phương án tối ưu
của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình đối ngẫu cuối cùng các j của
các cột biến xj mà chúng là các biến cơ sở ở bước lặp đầu tiên (Bảng 1), rồi cộng
thêm với hệ số cj tương ứng. Sau đó, đổi dấu tổng tìm được nếu biến cơ sở tương
ứng ban đầu nhận giá trị âm.
Với ví dụ đang xét ta thấy các biến cơ sở ở bước lặp đầu tiên (Bảng 1) là x4,
x5 (A4, A5 là các véctơ đơn vị). Lúc đầu các biến này nhận giá trị âm, nên phương
án tối ưu của bài toán đối ngẫu y* = ( y1* , y*2 ) được xác định như sau:
y1* = 4 c4 = 2 0 = 2
y*2 = 5 c5 = 2 0 = 2
Vậy, y* = (2; 2) và gmax = 1602 + 1402 = 600 = fmin.
Ví dụ sau đây cho thấy bài toán gốc không có phương án.
Ví dụ 2.2. Dùng phương pháp đơn hình đối ngẫu giải bài toán sau.
f(x) = 2x1 4x2 + x3 x4 + 2x5
x1 2x2
min,
2x5
x2
x3
x4
x5
x6
x7
phương án
2
4
1
1
2
0
0
x1
1
1
0
0
x6
0
2
0
0
2
0
1
1
0
x7
5
0
0
x1
2
6
1
10
2
2
0
0
0
x5
2
0
1
0
x7
0
10
0
17
5
4
0
0
1
Bảng 2
20
2.2. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU DẠNG CẢI BIÊN
2.2.1. Ký hiệu và công thức tính toán
Xét bài toán qui hoạch tuyến tính chính tắc:
min {f(x) = cTx : Ax = b, x ≥ 0}.
(2.1)
Nếu đã biết một phương án đối ngẫu chấp nhận được của bài toán (2.1) thì ta
có thể giải nó theo thuật toán đơn hình đối ngẫu dạng cải biên. Thuật toán dạng này
chỉ cần lưu trữ và biến đổi ma trận nghịch đảo cấp mm, thay cho ma trận điều kiện
ban đầu A (cỡ mn lớn hơn nhiều), nhờ đó tiết kiệm được bộ nhớ và thời gian tính
toán giải bài toán. Thuật toán càng hiệu quả đối với những bài toán qui hoạch tuyến
tính có số ràng buộc m nhỏ hơn nhiều so với số biến n của bài toán và có ma trận A
thưa (tỉ lệ các phần tử khác 0 trong A rất nhỏ, chỉ khoảng từ 5% đến 10%).
Ta nhắc lại một số ký hiệu và công thức tính dùng trong thuật toán đơn hình.
Giả sử có phương án cực biên x với cơ sở J = {i1, i2, . . , im} ( Ai1 , Ai2 , ... ,
Aim ) là các véctơ cơ sở và x i1 , x i2 , ... , x im là các biến cơ sở). Đặt
B = ( Ai1 , Ai2 , ... , Aim ) - ma trận cơ sở.
Zk = (z1k, z2k, ... , zmk)T - véctơ cột hệ số khai triển của Ak theo cơ sở B.
cB = ( ci1 , ci2 , ... , cim ) - véctơ hàng gồm hệ số mục tiêu của các biến cơ sở.
xB = ( x i1 , x i2 , ... , x im )T - véctơ cột ghi giá trị các biến cơ sở.
Theo phương pháp đơn hình, ta đã có các công thức tính sau:
xB = B-1b, f(x) = cBB-1b, Zk = B-1Ak, k = 1, 2, ... , n,
k = cBZk ck, gọi là ước lượng của biến xk, k = 1, 2, ... , n.
(2.2)
hay ở dạng ma trận ta có (B')1 = UrB1, trong đó
1
0
Ur =
0
0
0 z1s / z rs
1 z r 1,s / z rs
1/ z rs
0 z r 1,s / z rs
là một ma trận sơ cấp, nghĩa là nó chỉ khác ma trận đơn vị ở một cột duy nhất.
2.2.2. Thuật toán đơn hình đối ngẫu cải biên
Xét bài toán qui hoạch tuyến tính chính tắc ở dạng (2.1). Quá trình giải bài
toán theo đơn hình đối ngẫu dạng cải biên sử dụng hai bảng: Bảng 2.1 và 2.2.
Trong Bảng 2.1, m + 1 dòng đầu lưu giữ các hệ số aij, bi, cij của bài toán cần
giải (2.1). Từ dòng m + 2 trở đi ghi các phần tử của véctơ Pr = (zr1, ... , zrn) và các
ước lượng k của biến xk ở mỗi vòng lặp tính theo công thức (2.2).
Bảng 2.1.
Dòng 0
b
A1
As
An
Dòng 1
b1
a11
amn
Dòng m + 1
c
c1
cs
cn
Ước lượng
1
1
s
n
20
Bảng 2.2 gọi là bảng đơn hình đối ngẫu cải biên. Cột đầu ghi tên các biến cơ
sở. Cột cB ghi hệ số mục tiêu của các biến cơ sở. Trong cột thứ ba (Giả phương án):
m phần tử đầu là giá trị các biến cơ sở, phần tử cuối là giá trị hàm mục tiêu tương
ứng. Ma trận cơ sở nghịch đảo B-1 được ghi ở m cột tiếp theo.
Cột Zs (cột quay): m phần tử đầu ghi các hệ số khai triển của véctơ đưa vào cơ
sở As theo các véctơ cơ sở, phần tử cuối ghi ước lượng s . Dòng phía dưới ma trận
nghịch đảo ghi phương án của bài toán đối ngẫu, nó được tính theo công thức:
(qm+1,1, qm+1,2, ... , qm+1,m) = cBB-1.
(2.4)
Bảng 2.2. Bảng đơn hình đối ngẫu cải biên
Biến
cơ sở
cB
x i1
ci1
x ir
qr1
qrm
zrs
qm0
qm1
qmm
zms
của dòng quay: zrk = (B1)rAk, k = 1, ... , n, tức là nhân dòng thứ r của ma trận B1
với cột As ở Bảng 2.1, ta sẽ được phần tử zrk của dòng quay Pr và ghi vào Bảng 2.1.
Bước 4. (Chọn cột quay). Chia các phần tử trên dòng ước lượng (cuối mỗi
bảng) cho các phân tử tương ứng trên dòng quay, nhưng chỉ chia cho những phần
tử âm trên dòng quay. Cột quay là cột đầu tiên từ trái sang phải ứng với số nhỏ nhất
trong các tỉ số đó. Giả sử cột As là cột quay. Trước hết tính cột quay (cột Zs ở Bảng
2.2) theo công thức Zs = B1As, tức là nhân từng dòng của ma trận nghịch đảo B-1
với cột As ở Bảng 2.1 ta sẽ được từng phần tử của cột quay Zs của Bảng 2.2. Phần
tử cuối của cột này là s (đã tính ở trên).
Bước 5. Biến đổi bảng đơn hình đối ngẫu cải biên (trừ cột As) hoàn toàn như
trong phương pháp đơn hình thường (thay đổi biến cơ sở, đổi hệ số mục tiêu tương
ứng, biến đổi dòng quay và biến đổi các dòng khác theo qui tắc hình chữ nhật).
Cuối cùng, biến đổi và ghi vào bảng 2.1 dòng ước lượng mới ' theo công thức:
'k = k - (zrk/zrs)s, k = 1, ... , n, k s, 's = 0.
(2.5)
Trở lại thực hiện Bước 2 mô tả ở trên.
Chú ý 2.1. Khi tìm cột quay, nếu mọi phần tử trên dòng quay đều không âm
thì đó là dấu hiệu cho thấy bài toán gốc ban đầu không có phương án: Dừng thuật
toán.
Ví dụ 2.3. Giải lại bài toán ở Ví dụ 2.1 theo thuật toán đơn hình đối ngẫu dạng
cải biên.
f(x) = 15x1 + 12x2 + 10x3
3x1 4x2 2x3 + x4
x1 2x2 3x3
min,
= 160,
+ x5 = 140,
- 140
-1
-2
-3
0
1
c
15
12
10
0
0
1
- 15
- 12
2
-6
0
-4
-3
0
Pr
0,5
0
-2
- 0,5
1
-
-
0
- 160
1
0
-4
x5
0
- 140
0
1
-2
0
0
0
- 15
0 và f1 = 0,
Tính các ước lượng = ATy - c = (15 12 10 0 0). Đưa véctơ A4
(tương ứng với x4 = 160 < 0 nhỏ nhất) ra khỏi cơ sở. Chọn véctơ A2 (tương ứng
với chỉ số k = k/z1k = 3 nhỏ nhất) đưa vào cơ sở. Bảng 1 được biến đổi theo Bước
5 của thuật toán nêu trên, với phần tử quay z12 = 4 (ô tô đậm). Kết quả ta nhận
được Bảng 2.
23
Giả
Biến
cơ sở
cB
x2
12
40
- 1/4
0
1/2
véctơ A3 (tương ứng với chỉ số k = k/z2k = 2 nhỏ nhất) đưa vào cơ sở. Bảng 1
được biến đổi theo Bước 5 của thuật toán nêu trên, với phần tử quay z12 = 2 (ô tô
đậm). Kết quả ta nhận được Bảng 3.
Biến
cơ sở
cB
Giả
phương án
x2
12
25
- 3/8
1/4
x3
10
30
1/4
- 1/2
1 0 3 2
Ta thấy min{aij: aij < 0} = 2, vì thế ta chọn = 3 và thay A bởi ma trận
5 4 3 1
.
A = [aij + ] =
4
3
6
5
Mọi phần tử của ma trận A dương nên giá của trò chơi v > 0. Cặp bài toán
đối ngẫu của người chơi P1 và P2 là
f1 = x'1 + x'2 min,
5x'1 + 4x'2 1,
f2 = y'1 + y'2 + y'3 + y'4 max,
4x'1 + 3x'2 1,
5y'1 + 4y'2 + 3y'3 + y'4 1,
3x'1 + 6x'2 1,
4y'1 + 3y'2 + 6y'3 + 5y'4 1,
x'1 + 5x'2 1,
y'1 0, y'2 0, y'3 0, y'4 0.
Copyright: Tài liệu đại học ©