Quy hoạch tuyến tính

GV Hướng Dẫn:
Trần Chí Lê

Bài giảng:
Quy Hoạch tuyến tính



Toán chuyên đề 4-QHTT
(2-tín chỉ)
Chương I. Bài toán qui hoạch tuyến tính
Chương II. Bài toán vận tải
Chương III. Mô hình sơ đồ mạng lưới
Chương I. Bài toán qui hoạch tuyến tính và phương pháp đơn hình

Bài 1. Dạng của bài toán qui hoạch tuyến tính
I. Một số bài toán thực tế
1) Bài toán lập khẩu phần ăn
a) Phát biểu bài toán



b) Dạng toán học:
Đặt X = (x1, x2, x3, x4) là véc tơ khẩu phần ăn
f(X) = 12x1 + 9x2 + 7x3 + 8x4  min
3x1 + 2x2 + x3 + 2x4  28
2x1 + x2 + x3 + 2x4  20
4x1 + 3x2 + 2x3 + x4  40
x1  0, x2  0, x3  0, x4  0

2.Bài toán vận tải
Cho 3 kho hàng A1; A2; A3 và 3 điểm nhận hàng B1; B2; B3 theo sơ đồ sau:
Yêu cầu: Lập phương án vận chuyển sao cho điểm nhận nhận đủ hàng và tổng chi phí vận chuyển nhỏ nhất
f(X)=11x11 + 9x12 + 12x13 + 8x21 + 6x22 + 9x23 + 13x31 + 7x32 + 6x33  Min
x11 + x12 + x13 = 80
x21 + x22 + x23 = 70
x31 + x32 + x33 = 50
x11 + x21 + x31 = 40
x12 + x22 + x32 = 60
x13 + x23 + x33 = 100
xij  0, i, j.
3) Bài toán pha cắt vật liệu
4) Bài toán tiết kiệm tài nguyên
a) Ph¸t biÓu bµi to¸n:
Một nhà máy có thể sản xuất ra n-SP theo sơ đồ sau: Hãy lập PA sản xuất sao cho tổng lợi nhuận thu được là lớn nhất
2) Bài toán tiết kiệm tài nguyên – b) dạng toán học
f(X) = c1x1 + c2x2 + . + cnxn ? max
a11x1 + a12x2 + . + a1nxn ?? b1
a21x1 + a22x2 + . + a2nxn ? b2
...
am1x1 + am2x2 + . + amnxn ? bm
xj ? 0, ? j =
f(X) = cjxj  max

aijxj ≤ bi (i = )
xj  0,  j =
II. bài toán qhtt tổng quát
1. Dạng tổng quát
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
2.1) Hàm mục tiêu (1)
2.2) Hệ ràng buộc
Định nghĩa
Ràng buộc chung: (2)
Ràng buộc dấu: (3)
Vector hệ số của một ràng buộc:
Ví dụ 1.2.1 :
x1 + 3x2 – 2x4  7
x2  0
n=4, (1, 3, 0, -2); (0, 1, 0, 0)
n=5, (1, 3, 0, -2, 0); (0, 1, 0, 0, 0).
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
2.3) phương án

2.4) Miền ràng buộc

II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
2.3) phương án

2.4) Miền ràng buộc

2.5) phương án tối ưu

2.6) bài toán có lời giải và không có lời giải

Phương án tối ưu KH:X* là 1 PA thỏa mãn:
f(X*) ≤ f(X)  P.á X (f → min)
f(X*) ≥ f(X)  P.á X (f → max)
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
2.7) ràng buộc chặt; ràng buộc lỏng

X là 1 PA của bài toán QHTT
+) Nếu X làm cho ràng buộc “ i “ xảy ra dấu “=“ thì ràng buộc đó gọi là chặt với PA X
+) Nếu X làm cho ràng buộc “ i “ không xảy ra dấu “=“ thì ràng buộc đó gọi là lỏng với PA X
Ví dụ 1 : Cho bài toán QHTT sau
f(X) = 8x1 + 2x2 + 9x3 - x4  min
3x1 + 2x3 - x4  14 (1)
x1 - 4x2 - 2x4 = 8 (2)
- x1 + 7x2 + x3 + 3x4  -7 (3)
x1  0 (4), x2  0 (5), x3  0 (6);
X0 = (0, -1, 6, -2)có phải p.án ko, nếu có thì làm cho ràng buộc nào chặt; lỏng?
X0 = (0, -1, 6, -2) là PA, n = 4.
(1): vt = 14 = vp (thỏa mãn chặt);
(2): vt = 8 = vp (t/m chặt);
(3): vt = -7 = vp (t/m chặt);
(4): x1 = 0 = 0 (t/m chặt);
(5): x2 = -1 < 0 (t/m lỏng);
(6): x3 = 6 > 0 (t/m lỏng);
II. bài toán qhtt tổng quát

II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
2.7) ràng buộc chặt; ràng buộc lỏng

X0 là PACB của bài toán QHTT khi và chỉ khi nó phải làm thỏa mã chặt ít nhất n-ràng buộc, trong đó phải có n-ràng buộc độc lập tuyến tính
Chú ý: các ràng buộc là ĐLTT nếu hệ véc tơ ràng buộc ĐLTT
2.8)Phương án Cực biên

Ví dụ 2.
f(X) = 8x1 + 2x2 + 9x3 - x4  min
3x1 + 2x3 - x4  14 (1)
x1 - 4x2 - 2x4 = 8 (2)
- x1 + 7x2 + x3 + 3x4  -7 (3)
x1  0 (4), x2  0 (5), x3  0 (6);
X1 = (4, 0, 0, -2); X2 = (0, 0, 5, -4); X3 = (6, 0, 0, -1);
X4 = (12, 0, 0, 2) có phải p.án, p.án cực biên của bài toán?
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
Ví dụ 2
f(X) = 8x1 + 2x2 + 9x3 - x4  min
3x1 + 2x3 - x4  14 (1)
x1 - 4x2 - 2x4 = 8 (2)
- x1 + 7x2 + x3 + 3x4  -7 (3)
x1  0 (4), x2  0 (5), x3  0 (6)




D =
X1 = (4, 0, 0, -2), n = 4.
(1): vt = 14 = vp (thỏa mãn chặt);
(2): vt = 8 = vp (t/m chặt);
(3): vt = -10 < -7 = vp (t/m lỏng);
(4): x1 = 4 > 0 (t/m lỏng);
(5): x2 = 0 = 0 (t/m chặt);
(6): x3 = 0 = 0 (t/m chặt);
X1 là p.án cực biên
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
Ví dụ 2
f(X) = 8x1 + 2x2 + 9x3 - x4  min
3x1 + 2x3 - x4  14 (1)
x1 - 4x2 - 2x4 = 8 (2)
- x1 + 7x2 + x3 + 3x4  -7 (3)
x1  0 (4), x2  0 (5), x3  0 (6)
Chọn (1), (2), (4), (5).



D =
X2 = (0, 0, 5, -4), n = 4.
(1): vt = 14 = vp (thỏa mãn chặt);
(2): vt = 8 = vp (t/m chặt);
(3): vt = -7 = -7 = vp (t/m chặt);
(4): x1 = 0 = 0 (t/m chặt);
(5): x2 = 0 = 0 (t/m chặt);
(6): x3 = 5 > 0 (t/m lỏng);
X2 là p.án cực biên
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
Ví dụ 2
f(X) = 8x1 + 2x2 + 9x3 - x4  min
3x1 + 2x3 - x4  14 (1)
x1 - 4x2 - 2x4 = 8 (2)
- x1 + 7x2 + x3 + 3x4  -7 (3)
x1  0 (4), x2  0 (5), x3  0 (6)
X3 = (6, 0, 0, -1), n = 4.
(1): vt = 19 >14 = vp (t/m lỏng);
(2): vt = 8 = vp (t/m chặt);
(3): vt = -9 < -7 = vp (t/m lỏng);
(4): x1 = 4 > 0 (t/m lỏng);
(5): x2 = 0 = 0 (t/m chặt);
(6): x3 = 0 = 0 (t/m chặt);
X4 = (12, 0, 0, 2), n = 4.
(1): vt = 34 >14 = vp (t/m lỏng);
(2): vt = 8 = vp (t/m chặt);
(3): vt = - 6  -7 (không t/m ).
X3 là p.án không cực biên.
X4 không phải là p.án.
II. bài toán qhtt tổng quát
2. Các khái niệm cơ bản
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc
1. Dạng chính tắc
f(X) = c1x1 + c2x2 + … + cnxn  min (max)
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
.. .…….
am1x1 + am2x2 + … + amnxn = bm
xj  0  j =
f(X) = cjxj  min (max)

aijxj = bi (i = )

xj  0, (  j = )
Dạng rút gọn
Dạng tường minh
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc
2. Dạng chuẩn
Ví dụ 3a: Bài toán QHTT sau có là bài toán chuẩn hay không ?
Vậy bài toán QHTT trên là chuẩn !
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc
2. Dạng chuẩn
Ví dụ 3b: Bài toán QHTT sau có là bài toán chuẩn hay không ?
Vậy bài toán QHTT trên là chuẩn !
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc
2. Dạng chuẩn
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc

3. Các phép biến đổi sơ cấp – Đưa bài toán về dạng
Chính tắc
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc

3. Các phép biến đổi sơ cấp – Đưa bài toán về dạng
Chính tắc
Ví dụ 4: hãy chuyển bài toán sau về dạng chính tắc
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc

3. Các phép biến đổi sơ cấp – Đưa bài toán về dạng
Chính tắc
Ví dụ 5: hãy chuyển bài toán sau về dạng chính tắc
f(X) = 8x1 + 2x2 + 9x3 - x4  min
3x1 + 2x3 - x4  14
x1 - 4x2 - 2x4 = 8
- x1 + 7x2 + x3 + 3x4  -7
x1  0 , x2  0 , x3  0.
f(X) = 8x1 - 2x’2 + 9x3 – x’4 + x’’4  min
3x1 + 2x3 – x’4 + x’’4 - x5 = 14
x1 + 4x’2 - 2x’4 + 2x’’4 = 8
- x1 - 7x’2 + x3 + 3x’4 - 3x’’4 + x6 = -7
( x1 ; x’2 ; x 3 ; x’4 ; x’’ 4 ; x5 ; x6  0 )
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc

3. Các phép biến đổi sơ cấp – Đưa bài toán về dạng
Chính tắc
III. Bài toán qhtt dạng chính tắc và dạng chuẩn tắc

3. Các phép biến đổi sơ cấp – Đưa bài toán về dạng
Chính tắc
Nhận xét quan trọng:
Ta thấy bài toán QHTT bất kỳ đều có thể sử dụng quy tắc cơ bản để đưa về dạng chính tắc.
Từ đây trở về sau chúng ta chỉ xét các bài toán QHTT dạng chính tắc là đủ !!!
IV. Các tính chất cơ bản của bài toán qhtt

Đặt J(x) = {j / x*j > 0 } ta có:
+) Nếu |J(x)| = m (m là hạng của MT hệ số ràng buộc A) thì PACB là ko suy biến
+) Nếu |J(x)| < m thì PACB là suy biến
IV. Các tính chất cơ bản của bài toán qhtt

Chú ý: Tập J(x) = {j / x*j > 0 } gọi là tập cơ sở và xj gọi là biến cơ sở
Bài toán QHTT gọi là không suy biến nếu mọi PACB đều không suy biến
Bài toán QHTT là suy biến nếu chỉ cần có ít nhất 1 PACB suy biến !!
IV. Các tính chất cơ bản của bài toán qhtt

Ví dụ 6: Cho bài toán QHTT sau:
Nếu là PACB thì hãy chỉ ra nó là PACB suy biến hay không suy biến
IV. Các tính chất cơ bản của bài toán qhtt

Ví dụ 6: Cho bài toán QHTT sau:
Với X = (2, 2, 0);
Y = (0, 0, 4 );
Z = (1, 1, 2).
LG:X; Y; Z đều là PA, mặt khác
X là PACBkSB vì : J(x) = {1;2}  |J(x)| = 2 = m = r(A)
IV. Các tính chất cơ bản của bài toán qhtt

IV. Các tính chất cơ bản của bài toán qhtt

Ví dụ 6: Cho bài toán QHTT sau:
Với X = (2, 2, 0);
Y = (1, 1, 2 );
Z = (0, 0, 4).
LG:X; Y; Z đều là PA, mặt khác
Y là PACBSB vì : J(x) = {3}  |J(x)| = 1 < 2 = m = r(A)
IV. Các tính chất cơ bản của bài toán qhtt

Ví dụ 6: Cho bài toán QHTT sau:
Với X = (2, 2, 0);
Y = (1, 1, 2 );
Z = (0, 0, 4).
LG:X; Y; Z đều là PA, mặt khác
IV. Các tính chất cơ bản của bài toán qhtt

HỆ QUẢ 3. Nếu bài toán QHTT dạng chính tắc có PA thì cũng có PACB
IV. Các tính chất cơ bản của bài toán qhtt

IV. Các tính chất cơ bản của bài toán qhtt

IV. Các tính chất cơ bản của bài toán qhtt

IV. Các tính chất cơ bản của bài toán qhtt

Nhận xét quan trọng:
Với bài toán QHTT dạng chuẩn ta luôn tìm được 1 PACBkSB bằng cách : cho tất cả các biến không phải cơ sở = 0 !!!
Ví dụ 7: cho QHTT sau hãy tìm 1 PACB của bài toán đó ?
Cho x1= 0; x4= 0; x6= 0; x7= 0; ta được nghiệm của hệ là: X0 = (0;3;9;0;2;0;0)
Ta có X0 là 1 PA, hơn thế nữa J(x) = {2,3,5} và {A2 ; A3 ;A5 } ĐLTT

IV. Các tính chất cơ bản của bài toán qhtt

Ví dụ 8: cho QHTT sau hãy tìm 1 PACB của bài toán đó ?
Lời giải:
Bài2 .Phương pháp đơn hình giải bài toán QHTT
I)Tư tưởng của PPĐH:
-Xuất phát từ 1 PACB X0 ta tìm cách đánh giá nó, nếu nó tối ưu thì ta dừng lại !!  X0 là lời giải của bài toán !!!
-Nếu chưa tối ưu ta tìm cách chuyển sang 1 PACB mới X1 tốt hơn theo nghĩa f(X1) < f(X0)
-Thuật toán sẽ dừng lại sau hữu hạn bước ( vì số PACB là hữu hạn)
Bài2 .Phương pháp đơn hình giải bài toán QHTT
II) Phương pháp đơn hình
Xét bài toán QHTT dạng chính tắc:
Giả thiết:
Bài toán không suy biến, hạng của mt A = m
- Có 1 PACB ban đầu là X0 = (x01;x02;….; x0n)
Bài2 .Phương pháp đơn hình giải bài toán QHTT
II) Phương pháp đơn hình
Bước1: Bảng đơn hình:
Với X0 = (x01;x02;….; x0n);J(x) = {j/ x0n > 0}

Thì: jk J(x)
Với {Aj /j J(x) } ĐLTT

Thì: As = zjs.Aj
Với s = cj .zjs – cs

-s gọi là ước lượng của biến xs theo cs J(x)
f(x) = 2x1 + 3x2 – x3 – 1/2x4  min
x1 – x2 + x3 + 1/2x4 = 18
x2 – 4x3 + 8x4 + x5 = 8
–2x2 + 2x3 – 3x4 + x6 = 20
xj ≥ 0 (j = 1…6)
VD9: Lập bảng đơn hình đầu tiên của bài toán QHTT sau:
Lời giải:
-Ta thấy bài toán có dạng chuẩn vì vậy ta có ngay PACB xuất phát là: X0 = (18, 0, 0, 0, 8, 20)
J(x) = {1;5;6} và x1 ; x5 ; x6 là các biến cơ sở


Lời giải:
-Ta thấy bài toán có dạng chuẩn vì vậy ta có ngay PACB xuất phát là: X0 = (18, 0, 0, 0, 8, 20)
J(x) = {1;5;6} và x1 ; x5 ; x6 là các biến cơ sở


f(x) = 2x1 + 3x2 – x3 – 1/2x4  min
x1 – x2 + x3 + 1/2x4 = 18
x2 – 4x3 + 8x4 + x5 = 8
–2x2 + 2x3 – 3x4 + x6 = 20
xj ≥ 0 (j = 1…6)
f(x) = 2x1 + 3x2 – x3 – 1/2x4  min
x1 – x2 + x3 + 1/2x4 = 18
x2 – 4x3 + 8x4 + x5 = 8
–2x2 + 2x3 – 3x4 + x6 = 20
xj ≥ 0 (j = 1…6)
f(x) = 2x1 + 3x2 – x3 – 1/2x4  min
x1 – x2 + x3 + 1/2x4 = 18
x2 – 4x3 + 8x4 + x5 = 8
–2x2 + 2x3 – 3x4 + x6 = 20
xj ≥ 0 (j = 1…6)
Bước2: Kiểm tra dấu hiệu tối ưu:

-Nếu ∆s ≤ 0, k thì x0 là phương án tối ưu.

-Nếu ∆s > 0 thì chuyển sang bước 3.
Bước 3: Kiểm tra tính không giải được của bài toán:
- Nếu tồn tại ∆s > 0 mà xjs ≤ 0 thì bài toán không có phương án tối ưu.
- Nếu với mọi ∆s > 0 đều có ít nhất một xjs > 0 thì chuyển sang bước 4.



Bước 4: Chọn vectơ đưa vào cơ sở và xác định vectơ loại khỏi cơ sở:

-Giả sử , vectơ As được đưa vào cơ sở.




Bước 4: Chọn vectơ đưa vào cơ sở và xác định vectơ loại khỏi cơ sở:
-tính giả sử:

-khi đó Phần tử xrs gọi là phần tử xoay; vecto Ar sẽ loại khỏi cơ sở .

Bước 5: Biến đổi bảng:
Thay ẩn cơ sở xjr bằng ẩn cơ sở mới xs ; thay hệ số cjr của xjr bởi hệ số cs của xs

Bước 5: Biến đổi bảng:
Thay ẩn cơ sở xjr bằng ẩn cơ sở mới xs ; thay hệ số cjr của xjr bởi hệ số cs của xs

Bước 5: Biến đổi bảng:
Thay ẩn cơ sở xjr bằng ẩn cơ sở mới xs ; thay hệ số cjr của xjr bởi hệ số cs của xs

Bước6:
-Biến đổi lại toàn bộ bảng đơn hình để được bảng đơn hình mới theo quy tắc sau:
+) Lấy toàn bộ các phần tử ở hàng xoay chia cho phần tử xoay
+) Các phần tử không thuộc hàng xoay được tính theo công thức hình chữ nhật:
Bước6:-Công thức hình chữ nhật:




Lặp lại các bước đã thực hiện với bảng đơn hình mới (ta gọi là B2)
Tổng quát ta có sơ đồ sau
VD10: Giải bài toán QHTT sau bằng PPĐH:
Lời giải:
-Ta thấy bài toán có dạng chuẩn vì vậy ta có ngay PACB xuất phát:X0 = (0, 0, 0, 152, 60, 36)
J(x) = {4;5;6} và x4 ; x5 ; x6 là các biến cơ sở


VD10: Giải bài toán QHTT sau bằng PPĐH:
VD11: Giải bài toán QHTT sau bằng PPĐH:
VD11: Giải bài toán QHTT sau bằng PPĐH:
:
Ví dụ 12. Cho bài toán qhtt chính tắc:

f(X) = 2x1 + x2 + 4x3 + x4 – x5  min
3x1 – x2 + 2x3 + x4 - x6 = 26
4x2 – x3 + 2x5 + x7 = 20
x1 + 2x2 – 2x3 + x5 = 13
xj  0,  j = 1..7

Biết X0 = (3, 5, 0, 22, 0, 0, 0) là p.án cực biên của bt. Hãy lợi dụng X0 giải bải toán đó bằng PPĐH
Lời giải: Ta có J(x)={1;2;4} Và ma trận hệ số ràng buộc là:
Ta chuyển cơ sở J(x)={1;2;4} Về cơ sở đơn vị:
Ta biến đổi ma trận mở rộng sao cho tại vị trí :1;2;4 là các vecto đơn vị, Khi đó Matran cuối cùng thu được chính là Matran Hệ số trong bảng đơn hình đầu tiên:
+ Thuật toán dừng sau 2 bước lặp vì f  min và k ≤ 0  k = 1..7
P.án c.biên t.ưu X* = (3, 0, 0, 17, 10, 0, 0); J* = {4, 5, 1}; fmin = 13.
Ví dụ 13. Cho b.toán qhtt:
f(X) = - 4x1 + 5x2 - 3x3 + 5x4  min
- x1 + 3x2 - x3 + x4 = -2 (1)
3x1 - x2 + 2x3 - x4 ≥ 14 (2)
2x1 + x2 + x3 - 3x4 ≤ 30 (3)
xj  0,  j = . (4, 5, 6, 7)
Cho X0 = (0, 2, 8, 0).
.Chứng tỏ X0 là p.án, p.án cực biên của b.toán trên?
.Xuất phát từ X0, giải b.toán tìm p.án tối ưu bằng phương pháp đơn hình.
c.P.án tối ưu tìm được có duy nhất không, vì sao?
Ví dụ 13. Cho b.toán qhtt:
f(X) = - 4x1 + 5x2 - 3x3 + 5x4  min
- x1 + 3x2 - x3 + x4 = -2 (1)
3x1 - x2 + 2x3 - x4 ≥ 14 (2)
2x1 + x2 + x3 - 3x4 ≤ 30 (3)
xj  0,  j = . (4, 5, 6, 7)
Cho X0 = (0, 2, 8, 0).
Ví dụ 13. Cho b.toán qhtt:
f(X) = - 4x1 + 5x2 - 3x3 + 5x4  min
- x1 + 3x2 - x3 + x4 = -2 (1)
3x1 - x2 + 2x3 - x4 ≥ 14 (2)
2x1 + x2 + x3 - 3x4 ≤ 30 (3)
xj  0,  j = . (4, 5, 6, 7)
Cho X0 = (0, 2, 8, 0).
X0 = (0, 2, 8, 0, 0, 20) là p.á của bt c.tắc.
X0 = (0, 2, 8, 0, 0, 20) là p.á của bt c.tắc.
b) -Ta có X0 = (0, 2, 8, 0, 0, 20) là PACB KSB
- Vì {A2; A3; A6} không phải cơ sở chính tắc:
b) -Ta có X0 = (0, 2, 8, 0, 0, 20) là PACB KSB
- Vì {A2; A3; A6} không phải cơ sở chính tắc:
b) -Ta có X0 = (0, 2, 8, 0, 0, 20) là PACB KSB
- Vì {A2; A3; A6} không phải cơ sở chính tắc:
+ T.toán dừng sau 2 bước lặp vì f  min và k  0,  k =1..6 .
X* = (0, 7, 23, 0, 25, 0); Cơ sở t.ưu: J* = {3, 2, 5}.
Ví dụ 14. Cho bài toán qhtt chính tắc:
f(X) = x1 – x2 + 2x3 + x4 - 5x5  min
2x1 + x2 - x3 + x5 + x6 = 2
- x1 - x2 + x3 + x4 - x5 = 1
5x1 - x2 + 2x3 - 2x4 - 3x5 - x7 = 1
xj  0,  j =1..7
Giải bài toán tìm p.án tối ưu bằng phương pháp đơn hình. Biết X0 = (0, 0, 3/4, 1/4, 0, 11/4, 0) là p.án cực biên.
III) Vấn đề tìm PACB xuất phát
1) Bài toán dạng chính tắc nhưng không phải dạng chuẩn đồng thời không biết phương án cực biên, muốn áp dụng thuật toán đơn hình cần phải tìm một phương án cực biên xuất phát.
2) Phương pháp:
Chúng ta 2 phương pháp thông dụng đó là:
+) Phương pháp Bài toán (M) (tự tìm hiểu)
+) Phương pháp 2 pha ( ta sẽ nghiên cứu)
III) Vấn đề tìm PACB xuất phát
3. Nội dung của Phương pháp 2 pha:
III) Vấn đề tìm PACB xuất phát
3. Nội dung của Phương pháp 2 pha:
Pha 1: Giải bài toán phụ P
Nhận xét:+) Bài toán P có dạng chuẩn nên ta có ngay PACB ban đầu.
+) BT P có hàm mục tiêu bị chặn, và tập PA khác rỗng nên chắc chắn có lời giải
III) Vấn đề tìm PACB xuất phát
3. Nội dung của Phương pháp 2 pha:
Pha 1: Giải bài toán phụ P
Ta có kết quả như sau:
+) Nếu tồn tại u*i khác không trong PATƯ -> Bài toán ban đầu không có PA !!

+) Nếu tất cả u*i = 0 (với mọi i = m+1..m+n) và trong cơ sở tương ứng của PATƯ chỉ gồm toàn xj thì: Đây chính là PACB và cơ sở xuất phát để bắt đầu Pha 2 – giải bài toán ban đầu !!

+) Nếu tất cả u*i = 0 (với mọi i = m+1..m+n) và trong cơ sở tương ứng của PATƯ vẫn còn tồn tại ui thì ta phải tìm cách loại tất cả các ui ra khỏi cơ sở !! ( loại như thế nào ????)
III) Vấn đề tìm PACB xuất phát
Ví dụ 15. Giải bài toán QHTT sau bằng PPĐH:


f(x) = - 3x1 + x2 + 3x3 - x4 => MIN
x1 + 2x2 - x3 + x4 = 2
2x1 - 6x2 + 3x3 + 3x4 = 9
x1 - x2 + x3 - x4 = 6
xj >=0 (j =1..4)
Lời giải: Pha 1 Xét bài toán P
P = u5 + u6 + u7 => MIN
x1 + 2x2 - x3 + x4 + u5 = 2
2x1 - 6x2 + 3x3 + 3x4 + u6 = 9
x1 - x2 + x3 - x4 + u7 = 6
xj >=0 (j =1..4)
Ta có PACB của P là: X0 = (0; 0; 0; 0; 2; 9; 6)
Ta có PATƯ của P là: X* = (3; 2; 5; 0; 0; 0; 0)
Pha 2: xét lại bài toán ban đầu với hàm mục tiêu:
f(x) = - 3x1 + x2 + 3x3 - x4 => MIN
Vậy PAT Ư X*=(3;2;5;0) và fmin = 8
III) Vấn đề tìm PACB xuất phát
Chú ý Quan trọng
+) Khi xây dựng bài toán phụ chỉ cộng thêm biến giả vào những phương trình cần thiết ( nhằm tạo ma trận điều kiện của bài toán phụ có đủ m vectơ đơn vị ).
+) Một biến giả đã bị loại khỏi cơ sở thì cột tương ứng không cần tính ở các bước tiếp sau.
III) Vấn đề tìm PACB xuất phát
Ví dụ 16. Giải bài toán QHTT sau bằng PPĐH:


Pha 1
Pha 2: ta giữ lại các ẩn x ở bảng cuối cùng của Pha 1, thay các hệ số bằng các hệ số mới
Pha 2: ta giữ lại các ẩn x ở bảng cuối cùng của Pha 1, thay các hệ số bằng các hệ số mới
Vậy: PATƯ là (11;3;0;0;5) và fmin = 45
Bài3 .Bài toán đối ngẫu và PP đơn hình đối ngẫu
I) Cách thành lập bài toán đối ngẫu
1) Mục đích và ý nghĩa
Bài3 .Bài toán đối ngẫu và PP đơn hình đối ngẫu
2) Cách thành lập:
Về dấu: BT gốc quy định BT đối ngẫu:
+) rb biến quy định rb chung.
+) rb chung quy định rb dấu
Bài3 .Bài toán đối ngẫu và PP đơn hình đối ngẫu
VD17. Lập bài toán đối ngẫu của bài toán sau:
bài toán đối ngẫu :
VD18. Lập bài toán đối ngẫu của bài toán sau:
bài toán đối ngẫu
bài toán gốc:
Bài3 .Bài toán đối ngẫu và PP đơn hình đối ngẫu
3) Cặp ràng buộc đối ngẫu:
Ta gọi 2 ràng buộc bất đẳng thức (kể cả ràng buộc dấu) trong hai bài toán cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu :

VD18. Xác định cặp ràng buộc đối ngẫu của cặp bài toán sau:
bài toán đối ngẫu
bài toán gốc:
VD19. Lập bài toán đối ngẫu của bài toán sau, và chỉ rõ cặp đối ngẫu:
Cặp ràng buộc đối ngẫu :
4) Các định lý đối ngẫu:
4) Các định lý đối ngẫu:
-X;Y là 2 PA của cặp bài toán đối ngẫu (X là PA của bt gốc, Y là PA của bt đối ngẫu)
- Điều kiện cần và đủ để X; Y là 2 PA tối ưu của cặp bài toán đối ngẫu là:Trong các cặp ràng buộc đối ngẫu, nếu ràng buộc này là lỏng thì ràng buộc kia là chặt.
Chú ý: lỏng --> chặt
chặt -/-> lỏng
4) Các định lý đối ngẫu:
Về mặt áp dụng:
-X* là PATƯ của bài toán P
-Từ X* và các cặp ràng buộc đối ngẫu (lỏngchặt) ta sẽ thu được hệ pt tuyến tính theo y1 ;y2 ;…;ym.
- Giải hệ ta nhận được nghiệm Y=(y1;..,ym)
- Nếu Y là PA của bài toán D thì Y = Y*
( Tương tự ta cũng có thể bắt đầu từ Y* )
VD20. Cho bài toán QHTT sau: Biết nó có PATƯ X*=(0;14;6;5). Hãy tìm PAtƯ của bài toán đối ngẫu
VD20. Cho bài toán QHTT sau: Biết nó có PATƯ X*=(0;14;6;5). Hãy tìm PAtƯ của bài toán đối ngẫu
VD21. Cho bài toán QHTT sau
VD21. Cho bài toán QHTT sau
VD20. Cho bài toán QHTT sau
Giải hệ ta có nghiệm Y=(0;2;1); Kiểm tra Y là PA của bt đối ngẫu.
Hơn nữa f(X) = f*(Y), vậy X là PATƯ của bt
II) Phương pháp đơn hình đối ngẫu
1)Tư tưởng của PPĐH đối ngẫu:
PPĐH: {X=(x1 ;..;xn),xj>=0; s >= 0;} {s <= 0}

PPĐH đối ngẫu:
{X=(x1 ;..;xn) ;s <= 0 }{X=(x1 ;..;xn) ;xj>=0 }

II) Phương pháp đơn hình đối ngẫu
2)PPĐH đối ngẫu:
Bước 1: Lập bảng đơn hình đối ngẫu
Bước 2: Tiêu chuẩn tối ưu:
-Nếu x0j >=0 (với mọi j=1..m) thì PA X0 là PATƯ
-Nếu tồn tại x0j < 0 thì chuyển sang bước 3 !
Bước 3: Tiêu chuẩn Ko tối ưu:
- Nếu tồn tại x0j < 0 mà zrk ≥ 0,  k J thì bài toán Ko có lời giải ; ngược lại chuyển sang B4
Bước 4: Tìm PA mới tốt hơn:
-Đặt x0r = min{x0j < 0 } thì hàng-r gọi là hàng xoay;
-Tính: ; khi đó cột-s là cột xoay;
-Phần tử Zrs là phần tử xoay, biến đổi lại bảng đơn hình theo quy tắc cũ !!!.
Bài toán sẽ dừng lại sau hữu hạn bước
VD20. Giải bài toán QHTT sau bằng PPĐH đối ngẫu:
Cho x1=x2=x3=0;  x4 =-6; x5 =-2; x6 =-5; Vậy ta có giả PA X0 =(0; 0; 0; -6; -2; -5)
VD20. Giải bài toán QHTT sau bằng PPĐH đối ngẫu:
Cho x2=x3=x5=0;  x1 =-2; x4 =-4; x6 =2; x7 =6 Vậy ta có giả PA X0 =(-2; 0; 0; -4; 0;2; 6)
Ta thấy tồn tại x7 <=0 mà z4k > 0; KL: Bài toán Ko có TƯ
II) Phương pháp đơn hình đối ngẫu
3) Vấn đề tìm cơ sở đối ngẫu:
Không phải lúc nào ta cũng “MAY MẮN “ đoán được giả PA thỏa mãn: s <=0;
-Ta sẽ tìm cơ sở J 0(x) sao cho s <=0 với mọi s
Không mất tính tổng quát ta xét cặp bài toán:
II) Phương pháp đơn hình đối ngẫu
3) Vấn đề tìm cơ sở đối ngẫu:
Không phải lúc nào ta cũng “MAY MẮN “ đoán được giả PA thỏa mãn: s <=0;
-Ta sẽ tìm cơ sở J 0(x) sao cho s <=0 với mọi s
Cơ sở đối ngẫu.
Cho Y0 là một p.án của bài toán đn.
Ký hiệu J0(Y0) = {j : Y0Aj = cj .Ta gọi {Aj : j  J0}, viết tắt là J0 là một cơ sở đối ngẫu của Y0.
b. Bổ đề. Nếu P:f → min &D: g → max và Y0 là p.án cực biên của bài toán đối ngẫu với cơ sở J0. Thì giả PA X0 đối với cơ sở đối ngẫu J0 sẽ có:
Δk ≤ 0,  k = 1..n.
Cơ sở đối ngẫu.
Cho Y0 là một p.án của bài toán đn.
Ký hiệu J0(Y0) = {j : Y0Aj = cj .Ta gọi {Aj : j  J0}, viết tắt là J0 là một cơ sở đối ngẫu của Y0.
VD 21: Cho bài toán QHTT sau:
f(x) = 4x1 + 3x2 + 2x3 + 3x4  min
x1 + x3 - x4 = 2
- x1 + 2x2 + x4 + x5 = 11
2x1 + x2 - 3x4 -x6 = 8
xj  0,  j = 1..6
Biết Y0 = (2;0;0) là PACB của bài đối ngẫu.
Hãy xác định cơ sở đối ngẫu
Dựa vào cơ sở đối ngẫu, hãy giải bài toán QHTT trên bằng PPĐH đối ngẫu
Cơ sở đối ngẫu.
Cho Y0 là một p.án của bài toán đn.
Ký hiệu J0(Y0) = {j : Y0Aj = cj .Ta gọi {Aj : j  J0}, viết tắt là J0 là một cơ sở đối ngẫu của Y0.
VD 21: Cho bài toán QHTT sau:
f(x) = 4x1 + 3x2 + 2x3 + 3x4  min
x1 + x3 - x4 = 2
- x1 + 2x2 + x4 + x5 = 11
2x1 + x2 - 3x4 -x6 = 8
xj  0,  j = 1..6
Biết Y0 = (2;0;0) là PACB của bài toán đối ngẫu.
+ Bài toán đối ngẫu:
g(Y) = 2y1 + 11y2 + 8y3 ? max
y1 - y2 + 2y3 ? 4 (1)
2y2 + y3 ? 3 (2)
y1 ? 2 (3)
-y1 +y2 - 3y3 ? 3 (4)
y2 ? 0 (5)
-y3 ? 0 (6)
+ Kiểm tra:
(1): 2 < 4 (t/m lỏng)
(2): 0 < 3 (t/m lỏng)
(3): 2 = 2 (t/m chặt)
(4): -2 < 3 (t/m lỏng)
(5): 0 = 0 (chặt)
(6): 0 = 0 (chặt).
+ Y0 là p.án của
bt đối ngẫu.
+ Y0 thỏa mãn chặt
m=3; D = -1.
+ Y0 là cực biên;
J0 = {3, 5, 6}.
VD 21: Cho bài toán QHTT sau:
f(x) = 4x1 + 3x2 + 2x3 + 3x4  min
x1 + x3 - x4 = 2
- x1 + 2x2 + x4 + x5 = 11
2x1 + x2 - 3x4 -x6 = 8
xj  0,  j = 1..6
Biết Y0 = (2;0;0) là PACB của bài toán đối ngẫu.
+ Y0 là p.án của
bt đối ngẫu.
+ Y0 thỏa mãn chặt
m=3; D = -1.
+ Y0 là cực biên;
J0 = {3, 5, 6}.
Giả PA của bài toán này là : X=(0;0;2;0;11;-8)
Ta bắt đầu PPĐH đối ngẫu
Giả PA của bài toán này là : X=(0;0;2;0;11;-8)
Ta bắt đầu PPĐH đối ngẫu
Thuật toán dừng sau 3 bước lặp vì xj ? 0 ? j.
Phương án tối ưu của bài toán chính tắc là
X* = (2, 4, 0, 0, 5, 0), J* = {2, 5, 1}; fmin= 20.
+ P.án tối ưu bài toán gốc: X* = (2, 4, 0, 0); fmin = 20.
VD22: Cho bài toán QHTT sau:
f(X) = 3x1 + 5x2 - 7x3 + x4  min
2x2 - x3 + 3x4  10
x1 + x2 - 4x3 - x4 = 3
3x2 + 2x3 + 4x4  7
xj  0,  j =1..4 .
Chứng minh Y0 = (0, 3, 0) là PACB bài toán đối ngẫu
Giải bài toán QHTT trên bằng PP đơn hình đối ngẫu