i
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------------------- ĐÀO MINH BẰNG MỘT PHƢƠNG PHÁP XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH THEO PHƢƠNG PHÁP NHÁNH CẬN VÀ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Thái Nguyên - 2015
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
ii
MỤC LỤC
MỤC LỤC ....................................................................................................... i
Mở đầu ........................................................................................................... iv
Chương 1. BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ BÀI
1.1. Một số mô hình thực tế thuộc dạng bài toán quy hoạch nguyên tuyến tính dạng
chuẩn ............................................................................................................................. 1
1.1.1. Bài toán pha cắt vật liệu .................................................................................... 1
1.1.2. Bài toán lập kế hoạch sản xuất .......................................................................... 2
1.1.3. Bài toán cái túi .................................................................................................. 2
1.1.4. Mô hình phân bố máy bay cực tiểu tổng chi phí trên toàn mạng đường bay hàng
không ......................................................................................................................... 3
1.1.5. Bài toán mua (thuê) máy bay tối ưu: .................................................................. 6
1.2. Bài toán quy hoạch nguyên tuyến tính dạng chuẩn và phương pháp giải ........................... 7
1.2.1. Bài toán quy hoạch nguyên tuyến tính ............................................................... 7
1.2.2. Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính ..................... 9
1.3. Bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính
.................................................................................................................................... 15
1.3.1. Phương pháp nón xoay xấp xỉ ngoài tuyến tính ............................................... 16
Thuật toán xấp xỉ ngoài LP ....................................................................................... 16
1.3.2. Bảng lặp giải bài toán quy hoạch tuyến tính bởi thuật toán nón xoay xấp xỉ
ngoài tuyến tính ........................................................................................................ 18
1.3.3. Bài toán quy hoạch tuyến tính tái tối ưu hóa và thuật toán TTH....................... 22
TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN.................................. 1
Chương 2. THUẬT TOÁN NHÁNH CẬN XẤP XỈ NGOÀI GIẢI BÀI
2.1. Thuật toán nhánh cận xấp xỉ ngoài giải bài toán quy hoạch nguyên tuyến tính ...... 28
2.2. Minh họa ứng dụng thuật toán nhánh cận xấp xỉ ngoài ILP giải bài toán quy hoạch
nguyên tuyến tính có số chiều nhỏ với miền ràng buộc là hệ bất phương trình tuyến tính
.................................................................................................................................... 31
TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ ỨNG DỤNG ............. 28
KẾT LUẬN ................................................................................................... 52
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
TÀI LIỆU THAM KHẢO ............................................................................. 54
iii
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iv
Mở đầu
Như chúng ta đã biết, nhiều bài toán thực tế dẫn đến chúng ta phải
đi giải các bài toán quy hoạch nguyên tuyến tính, và một trong những
phương pháp hiệu quả để giải nó đó là phương pháp nhánh cận Land -
Doig. Mỗi bước trung gian để giải bài toán quy hoạch nguyên tuyến tính
thông thường là chúng ta phải tiến hành giải các bài toán quy hoạch tuyến
tính tương ứng khi chưa có điều kiện nguyên của biến với các ràng buộc
bổ sung dạng bất phương trình cho các thành phần của biến. Do đó việ c
sử dụng các thuật toán giải trực tiếp bài toán quy hoạch tuyến tính với
miền ràng buộc là hệ bất phương trình tuyến tính là khá ưu việt và hiệu
quả, một trong những thuật toán như vậy là thuật toán nón xoay tuyến tính
xấp xỉ ngoài trình bày trong [4].
Nội dung chính của luận văn được trình bày trong hai chương:
Chương 1, trình bày một số mô hình bài toán thực tế có dạng bài toán
quy hoạch nguyên tuyến tính, phương pháp nhánh cận Land-Doig và thuật
toán nón xoay xấp xỉ ngoài tái tối ưu hóa TTH giải bài toán quy hoạch tuyến
tính dạng chuẩn.
Chương 2, trình bày việc xây dựng thuật toán xấp xỉ ngoài ILP giải bài
toán quy hoạch nguyên tuyến tính từ thuật toán nhánh cận Land-Doig và thuật
toán nón xoay xấp xỉ ngoài TTH. Thuật toán đã dựa trên một định lý làm cho
trong mỗi bước để tìm các cận dưới đúng của bài toán nguyên, chúng ta chỉ
phải đi giải các bài toán quy hoạch tuyến tính tương ứng khi chưa có điều
kiện nguyên có số chiều là n - 1 (n là số chiều của bài toán). Tiếp đó minh họa
ứng dụng thuật toán trình bày giải cho một số ví dụ đã có trong một số tài liệu
[2], [3] và [5] để so sánh tính thuận lợi của thuật toán khi trường hợp bài toán
có sô chiều hay số ràng buộc chính là nhỏ. Và trong trường hợp bài toán quy
hoạch nguyên tuyến tính dạng chuẩn 2 chiều thì việc giải các bài toán quy
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
hoạch tuyến tính tương ứng khi chưa có điều kiện nguyên, trong mỗi bước để
v
tìm các cận dưới đúng của bài toán chỉ còn là việc kiểm tra tìm giá trị nhỏ
nhất của hàm một biến tại hai đầu mút (nếu có).
Các thuật toán trình bày trong luận văn này được xây dựng chi tiết, các
bước của thuật toán được trình bày sao cho chúng ta có thể dễ dàng lập trình
chuyển sang các chương trình trên máy tính bằng các ngôn ngữ như Pascal, C,
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Basis, Java, ...
1
Chƣơng 1
BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH
VÀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN
Trong chương này chúng ta sẽ trình bày một số bài toán thực tế
điển hình thuộc dạng bài toán quy hoạch nguyên tuyến tính, giới thiệu
một số phương pháp quan trọng thường dùng để giải bài toán quy hoạch
nguyên tuyến tính. Và trong quá trình các bước giải bài toán này cần phải
giải các bài toán quy hoạch tuyến tính dạng chuẩn trung gian khi thêm
vào các siêu phẳng cắt hoặc thêm vào các ràng buộc dạng bất phương
trình tuyến tính để chia nhỏ miền chấp nhận sau mỗi bước. Chính vì thế,
trong phần cuối của chương này sẽ trình bày một thuật toán xấp xỉ ngoài
giải trực tiếp bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất
phương trình tuyến tính và thuật toán này khá hiệu quả trong trường hợp
tái tối ưu hóa.
1.1. Một số mô hình thực tế thuộc dạng bài toán quy hoạch nguyên tuyến
tính dạng chuẩn
1.1.1. Bài toán pha cắt vật liệu
Một phân xưởng có những thanh vật liệu (thanh thép, ống nhựa, ….)
có độ dài cho trước, chúng ta cần cắt chúng thành những đoạn ngắn theo các
mẫu cho trước. Vấn đề đặt ra là ta nên cắt như thế nào cho tổng những phần
dư còn thừa lại là tốn ít nhất?
Giả sử aij là độ dài đoạn loại i theo mẫu j, bi là số đoạn loại i cần có,
cj là rẻo thừa khi cắt theo mẫu j, gọi xj là số thanh cắt theo mẫu j (j= 1,2, …,
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
n). Ta có bài toán quy hoạch nguyên tuyến tính sau:
2
với các điều kiện
và nguyên,
Đây là một bài toán quy hoạch tuyến tính chính tắc nguyên.
1.1.2. Bài toán lập kế hoạch sản xuất
Giả sử một xí nghiệp sản xuất n loại sản phẩm và sử dụng m loại
nguyên liệu khác nhau, cj là lãi suất (hay giá bán) đối với một đơn vị sản
phẩm j (j =1,…, n), là suất chi phí tài nguyên loại i để sản xuất một đơn vị
sản phẩm loại j, là lượng dự trữ tài nguyên loại i (i = 1,…,m). Gọi xj là
lượng sản phẩm loại j (j = 1,…, n) mà xí nghiệp sản xuất. Trong các điều kiện
đã cho, hãy xác định các giá trị (j = 1,…, n) sao cho tổng tiền lãi (hay tổng
giá trị sản lượng hàng hóa) là lớn nhất với số tài nguyên hiện có.
Mô hình toán học có dạng bài toán quy hoạch tuyến tính dạng chuẩn sau:
với các điều kiện
,
Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên.
1.1.3. Bài toán cái túi
Một người du lịch muốn đem theo một cái túi có thể đựng được các đồ
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
vật nặng không quá b kilogam. Có n loại đồ vật mà anh ta dự định đem theo.
3
Mỗi một đồ vật loại j có khối lượng kilogam và giá trị Người du lịch
muốn chất vào túi các đồ vật sao cho tổng giá trị đồ vật đem theo là lớn nhất.
Ký hiệu là số đồ vật loại j sẽ chất vào túi. Ta có bài toán sau:
- nguyên,
Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên.
1.1.4. Mô hình phân bố máy bay cực tiểu tổng chi phí trên toàn mạng
đường bay hàng không
1. Các tham số và biến quyết định của bài toán:
Giả sử chúng ta đang khai thác sử dụng K loại máy bay (777, 767,
A321, A330, A320, AT7,...), là số máy bay loại k đang khai thác sử dụng
(k=1,2,...,K), giả sử số sân bay (thành phố) tham gia vào mạng là N. Ta sử
dụng các ký hiệu sau đây: (i, j) là chặng bay từ sân bay i đến sân bay j
(i, j=1,2...,N).
Ta giả thiết chiều dài trung bình thực tế Dij và chiều dài thương mại của
mỗi chặng bay là bằng nhau.
Pij là số lượng khách trung bình dự báo có thu nhập thực tế chuyên chở
được trên chặng bay (i, j) (trong mỗi tuần).
Sk là số ghế tương ứng (số ghế tối đa được phép xếp khách cho từng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
chặng bay của loại máy bay k)
4
gij là ghế suất (hệ số sử dụng ghế suất) trung bình trên chặng bay (i, j)
- số giờ khai thác bay trung bình lớn nhất cho phép của một chiếc
máy bay loại k trong một tuần.
- là vận tốc bình quân thực tế của máy bay loại k.
tương ứng là tần xuất bay ít nhất và nhiều nhất (số
chuyến bay trong một tuần) của loại máy bay k trên chặng bay (i, j).
là chi phí theo chuyến bay (trong một tuần) trên chặng bay (i, j) của
loại máy bay k.
là tần suất bay (số chuyến bay trong một tuần) của loại máy bay k
trên chặng bay (i, j) (biến quyết định).
2. Hàm mục tiêu:
Ta ký hiệu Cost là tổng chi phí theo chuyến bay cho tất cả máy bay
đang khai thác sử dụng trong thời kỳ phân tích (một tuần) trên các tuyến
bay toàn mạng. Thời kỳ phân tích là khoảng thời gian cần nghiên cứu cần
phân tích mà ta có thể quy định là một tuần, một tháng, một quý, sáu tháng,
một năm,....
Hàm mục tiêu Cost là tổng chi phí cho chuyến bay trên toàn mạng được
xác định như sau:
(I.1)
Trong đó
(chi phí cố định) là tổng chi phí không phát sinh thêm khi chuyến bay được thực hiện như: giá thuê máy bay, bảo hiểm máy bay, bảo
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
dưỡng sửa chữa máy bay, khấu hao thiết bị máy bay, quản lí chung...C là
5
chi phí biến đổi theo chuyến bay của loại máy bay k xuất hiện khi thực hiện
chuyến bay như: phục vụ hàng khách, giờ bay, hàng hóa, nhiên liệu...
3. Các ràng buộc của bài toán:
Ràng buộc về thương mại:
(I.2)
Ràng buộc này có nghĩa là tần suất bay của loại máy bay k trên
chặng bay (i, j) không ít hơn và không nhiều hơn (ràng
buộc về hạn chế thương mại).
Ràng buộc về khai thác:
Với mỗi vòng bay j (Pairing) ta có:
= (I.3)
(j = 1,2,...N, k = 1,2,...,K)
Ràng buộc (I.3) có nghĩa là trong khoảng thời gian phân tích (của một
chu kỳ bay) thì các đội bay của loại máy bay k rời sân bay căn cứ j (Crew
Base) bay đến sân bay i thì sẽ bay về sân bay j trong vòng bay.
(I.4)
Trong đó là thời gian bay trên chặng bay (i, j) của loại máy bay k.
Ràng buộc (I.4) có nghĩa là số giờ khai thác bay trung bình của một
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
chiếc máy bay loại k không vượt quá số giờ bay cho phép.
6
(i, j = 1,2,...,N) (I.5)
Ràng buộc (I.5) có nghĩa là hệ số sử dụng ghế (ghế suất) thực tế
trên chặng bay (i, j) của loại máy bay k phải đạt ít nhất bằng và không
vượt quá 100%.
Bài toán đặt ra là cựu tiểu hàm mục tiêu (I.1) với ràng buộc thỏa mãn
(I.2), (I.3), (I.4) và (I.5). Vậy mô hình bài toán “Phân bố máy bay” cực tiểu
tổng chi phí cho chuyến bay như sau:
(I.6)
Với các ràng buộc:
= (j = 1,2,...N, k = 1,2,...,K)
(i, j=1,2,...,N)
Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên.
1.1.5. Bài toán mua (thuê) máy bay tối ưu:
Để mở rộng hoạt động, hãng hàng không dự định mua (thuê) K loại
máy bay (B777, B767, A321, A330, A320, AT7,...) ta gọi tương ứng là loại
máy bay k (k=1, 2, …, K). máy bay loại k có giá mua (thuê) là ck và có thời
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
gian sử dụng là Tk năm. Hãng dự định mua (thuê) tối đa là N máy bay trong
7
các loại máy bay trên với số vốn đầu tư hiện có là V, Bài toán cần giải quyết
là hãng hàng không nên mua (thuê) bao nhiêu máy bay mỗi loại để tổng thời
gian sử dụng là nhiều nhất?
Ta gọi xk là số lượng máy bay loại k cần mua (thuê), khi đó mô hình
bài toán đặt ra là:
(I.7)
Với các ràng buộc:
, nguyên
Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên.
1.2. Bài toán quy hoạch nguyên tuyến tính dạng chuẩn và phƣơng pháp giải
Trong mục này, chúng ta giới thiệu về bài toán quy hoạch nguyên
tuyến tính dạng chuẩn và phương pháp nhánh cận Land-Doig để giải nó. Nội
dung của mục này dựa chủ yếu vào các tài liệu [2], [3], [4] và [5].
1.2.1. Bài toán quy hoạch nguyên tuyến tính
Quy hoạch nguyên tuyến tính (Interger linener Programming, viết tắt
ILP), 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 trên một
tập hợp điểm rời rạc, thường là tập điểm nguyên:
( ILP)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
trong đó cho trước.
8
Khi có một số, không phải tất cả các biến là nguyên thì ta gọi đó là bài
toán qui hoạch nguyên bộ phận. Khi có điều kiện tất cả các biến đều nguyên
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
thì ta gọi đó là bài toán quy hoạch nguyên hoàn toàn.
9
Cũng như trong quy hoạch tuyến tính, f được gọi là hàm mục tiêu, tập
gọi là miền ràng buộc hay miền chấp nhận được. Điểm gọi là
một nghiệm chấp nhận được hay một phương án của bài toán. Một phương án
đạt cực tiểu (hay cực đại) của hàm mục tiêu gọi là nghiệm tối ưu hay một
phương án tối ưu. Nghiên cứu cấu trúc tập ràng buộc D và xây dựng các thuật
toán tìm nghiệm tối ưu của bài toán ILP là đối tượng của quy hoạch nguyên
tuyến tính.
1.2.2. Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính
Chúng ta đã biết khi giải bài toán quy hoạch tuyến tính bằng
phương pháp đơn hình thì nhiều bài toán như bài toán vận tải sẽ cho
chúng ta lời giải nguyên. Song cũng có nhiều bài toán cho chúng ta lời
giải chưa phải là nguyên, chính vì thế mà một số phương pháp giải bài
toán quy hoạch nguyên đã ra đời.
Năm 1954, Dantzig, Fulkerson và Johnson đã đưa ra ý tưởng về
phương pháp siêu phẳng cắt để giải bài toán quy hoạch nguyên. Ý tưởng
chính của phương pháp này là mỗi bước lặp sẽ dùng siêu phẳng cắt để thu nhỏ
miền chấp nhận được ở bước trước sao cho nghiệm tối ưu chưa nguyên ở
bước này phải bị cắt đi và mọi phương án nguyên chấp nhận được không bị
cắt đi. Năm 1958, Ralph Gomory đã xây dựng thuật toán đảm bảo hữu hạn
bước nhận được lời giải tối ưu nguyên. Đến năm 1960, Land-Doig đã đưa ra
thuật toán nhánh cận giải bài toán quy hoạch nguyên hiệu quả hơn nhiều so
với phương pháp siêu phẳng cắt của Gomory.
Sau đây chúng ta sẽ trình bày thuật toán Land-Doig là một trong
những thuật toán của phương pháp nhánh cận. Sơ đồ tổng quát của phương
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
pháp nhánh cận chúng ta có thể tìm thấy ở các tài liệu [2], [3] và [5].
10
Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính
Xét bài toán quy hoạch nguyên tuyến tính sau đây:
(1.8)
Ký hiệu:
(với T là ký hiệu chuyển vị vectơ hay ma trận). Khi đó bài toán trên
được viết lại dưới dạng ma trận như sau:
(1.9)
Để áp dụng phương pháp nhánh cận, ta phải xác định hai thủ tục
chính đó là phân nhánh và tính cận. Ta xét cách xây dựng hai thủ tục này của
Land-Doig.
Đặt
Ta có miền D là miền chấp nhận được của bài toán (1.9). Ta sẽ ký hiệu
là bài toán (1.9).
Giải bài toán quy hoạch tuyến tính tương ứng với ta sẽ thu được
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
phương án tối ưu nói chung không nguyên.
11
Ta có:
Vì thế giá trị có thể dùng làm cận dưới cho giá trị tối ưu của
bài toán .
Như vậy ta đã có thủ tục để tính cận dưới: đặt giá trị cận dưới của bài
toán quy hoạch nguyên tuyến tính bằng giá trị tối ưu của bài toán quy hoạch
tuyến tính tương ứng với nó:
.
Ta phân chia tập chấp nhận được của bài toán thành hai tập bằng
cách đưa vào hai ràng buộc loại trừ lẫn nhau như sau:
Giả sử là một thành phần không nguyên nào đó của .
Ký hiệu:
(1.10)
(1.11)
Trong đó là phần nguyên của
Khi đó
. (1.12)
Như vậy, ta đã xác định được thủ tục phân hoạch theo các công thức
(1.10)-(1.12).
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Gọi là bài toán: .
12
Gọi là bài toán: .
Rõ ràng đây là các bài toán quy hoạch nguyên tuyến tính.
Khi giải bài toán quy hoạch tuyến tính tương ứng với bài toán
, để tính cận dưới cho các tập , ta có thể gặp một số các tình
huống sau đây:
1) Bài toán không có phương án chấp nhận được.
2) Tìm được phương án tối ưu nguyên.
3) Tìm được phương án tối ưu không nguyên.
Trường hợp 1): Bài toán cũng không có phương án chấp nhận được,
tức là . Khi đó, ta có thể loại bỏ tập khỏi qua trình xét tiếp theo.
Trường hợp 2): cũng là phương án của bài toán . Vì vậy là
phương án chấp nhận được của bài toán xuất phát. Trong trường hợp này, ta
có thể cải thiện được kỷ lục, còn tập cũng sẽ bị loại không cần xét tiếp.
Trường hợp 3): Ta thu được cận dưới của tập là
.
Tập cần xem xét tiếp:
Ta có thể mô tả thuật toán Land-Doig để giải bài toán quy hoạch
nguyên tuyến tính (1.9) như sau:
Thuật toán Land-Doig
Bước chuẩn bị: Giải bài toán quy hoạch tuyến tính tương ứng với
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
và thu được phương án tối ưu . Giả sử là không nguyên.
13
Đặt cận dưới của là và danh mục các bài toán cần xét là
.
Nếu biết là phương án chấp nhận được của bài toán thì đặt
và ngược lại, ta đặt ∞.
Bước lặp k = 1, 2, . . .
1) Nếu thuật toán kết thúc. Khi đó, nếu là giá thì
trị tối ưu và là phương án tối ưu của bài toán. Trong trường hợp ngược lại,
bài toán không có phương án chấp nhận được.
2) Nếu : Chọn là bài toán có cận dưới nhỏ nhất trong .
Gọi là miền chấp nhận được, là phương án tối ưu của bài toán quy
hoạch tuyến tính tương ứng với nó.
2.1. Giả sử là một thành phần không nguyên nào đó của .
Phân hoạch tập thành hai tập:
.
Gọi là bài toán
.
Gọi là bài toán
.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Đây là các bài toán quy hoạch nguyên tuyến tính.
14
2.2. Lần lượt giải các bài toán quy hoạch tuyến tính tương ứng với
để tính cận dưới đúng cho bài toán . Khi đó, ta có thể gặp một
trong các tình huống sau đây:
a) Phát hiện bài toán không có phương án chấp nhận được.
b) Tìm được phương án tối ưu là nguyên.
c) Tìm được phương án tối ưu là không nguyên.
Trường hợp a): Bài toán cũng không có phương án chấp nhận
được, vì vậy ta loại bỏ việc xem xét tiếp theo.
Trường hợp b): Tính lại các kỷ lục theo công thức:
Gọi là kỷ lục tương ứng với giá trị này. Bài toán đã xét xong.
Trường hợp c): Đặt cận dưới của là , và kết nạp nó vào danh
sách các bài toán cần xét:
2.3. Loại bỏ khỏi tất cả các bài toán có cận dưới lớn hơn hoặc bằng
giá trị kỷ lục. Đặt:
và chuyển sang bước k + 1.
Như vậy chúng ta đã trình bày xong thuật toán nhánh cận Land-Doig
giải bài toán quy hoạch nguyên tuyến tính dạng chuẩn. Chúng ta thấy khi giải
bài toán quy hoạch nguyên tuyến tính theo thuật toán trên thì các tính toán ở
giai đoạn 2.2. để giải các bài toán quy hoạch tuyến tính tương ứng tính cận
dưới là khâu quan trọng cần thiết. Rõ ràng sau mỗi bước mỗi bài toán quy
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
hoạch tuyến tính tương ứng cần giải lại thêm một ràng buộc bất phương trình.
15
Chính vì vậy khi giải các bài toán này chúng ta nên lựa chọn các thuật
toán giải trực tiếp được cho bài toán quy hoạch tuyến tính dạng chuẩn (miền
ràng buộc là hệ bất phương trình tuyến tính) nhất là những thuật toán mà có
ưu điểm thuận lợi trong trường hợp bài toán là tái tối ưu hóa (sau một bước lại
giải lại bài toán khi chỉ bổ sung thêm 1 ràng buộc).
Một thuật toán giải bài toán quy hoạch tuyến tính với miền ràng buộc
là hệ bất phương trình tuyến tính và có ưu điểm khi bài toán là tái tối ưu hóa
là thuật toán nón xoay trong [4]. Sau đây chúng tôi sẽ trình bày thuật toán nón
xoay và trong trường hợp bài toán cần giải là bài toán tái tối ưu hóa (tức là
giải lại bài toán mới khi bổ sung thêm một ràng buộc bất phương trình vào
miền ràng buộc của bài toán trước đã biết lời giải của nó). Chứng minh định
lý khẳng định bài toán tái tối ưu hóa nếu có lời giải thì sẽ có ít nhất một lời
giải thỏa mãn chặt ràng buộc bổ sung. Và nhờ tính chất này mà khi giải các
bài toán quy hoạch tuyến tính tương ứng trong bước 2.2. của thuật toán Land-
Doig trình bày trên chung ta chỉ phải giải các bải toán quy hoạch tuyến tính
với số chiều (số biến nguyên) là n-1 (n là số chiều của bài toán).
1.3. Bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất phƣơng
trình tuyến tính
Xét bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất
phương trình tuyến tính sau:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
xRn, Ai là véc tơ dòng và AiRn, m n, Ai(ai1, ai2, ..., ain) ≠ O(0,…,0) ,
16
C(c1, c2,…, cn), bi R1, i=1, 2, ..., m. Hạng của hệ Ai (i=1, 2, …, m)
bằng n, giả thiết này rất bình thường bởi miền ràng buộc PL của bài toán quy
hoạch tuyến tính nói chung bao giờ cũng có ràng buộc về dấu của biến x.
1.3.1. Phương pháp nón xoay xấp xỉ ngoài tuyến tính
Xét bài toán (L) trong trường hợp biết một nón – min của bài toán (L).
Ý tưởng của thuật toán nón xoay tuyến tính giải bài toán (L) như sau:
Xuất pháp từ một nón-min M ban đầu của hàm mục tiêu bài toán,
chúng ta kiểm tra xem đỉnh của nó có thuộc miền chấp nhận của bài toán
không (tức là đỉnh này có thoả mãn tất cả các ràng buộc không) nếu đỉnh này
thuộc miền chấp nhận thì nó là một lời giải của bài toán (L). Ngược lại ta xây
dựng nón xoay mới M(r,s) (vẫn là nón-min) từ nón cũ M của bài toán (L) và
lặp lại quá trình kiểm tra nón xoay mới này tương tự như đối với nón M, quá
trình này được thực hiện cho đến khi đỉnh của nón xoay mới M(r,s) thuộc
miền chấp nhận của bài toán (L) (khi miền ràng buộc của bài toán (L) có
phương án) hoặc sẽ phát hiện ra miền ràng buộc của bài toán (L) là rỗng.
Thuật toán xấp xỉ ngoài LP
Bước chuẩn bị (bước 0). Giả sử ta đó biết M0 là nón - min của bài
}, x0 = toán (L) với tập chỉ số cơ sở là I0:={ là đỉnh của M0 và
(i các véc tơ chỉ phương của các cạnh i của nón M0 là = I0).
Bước k ( k=0, 1, 2, ...). Giả sử Mk là nón - min của bài toán (L) (đã
được xây dựng), với tập chỉ số cơ sở, đỉnh và các véc tơ chỉ phương của các
; xk = và = . cạnh của nón Mk tương ứng là Ik:=
Xác định tập J+(xk) theo (1.6):
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
1. Nếu J+(xk) = thì dừng lại. xk chính là một lời giải của bài toán (L),
17
2. Nếu J+(xk) , ta chọn chỉ số đưa vào cơ sở theo một trong hai
cách sau:
Ta chọn sk là một chỉ số tuỳ ý thuộc J+(xk) hoặc ta chọn sk=min{j:jJ+(xk)}
(gọi là qui tắc chọn min) (1.13)
hoặc sk = max{j: j J+(xk) (gọi là qui tắc chọn max) và xác định:
; (1.14)
, (1.15)
2.1. Nếu = thì dừng lại, suy ra bài toán (L) không có phương án.
:
2.2. Nếu
Gọi :={ } (1.16)
và chọn chỉ số đưa ra khỏi cơ sở theo một trong hai cách sau:
. Hoặc ta chọn Ta chọn rk là chỉ số tuỳ ý thuộc
rk = min{v: v } hoặc rk = max{v: v } (1.17)
(cách chọn chỉ số này gọi là qui tắc chọn min (hoặc là qui tắc chọn max)) .
Và ta xây dựng nón xoay Mk+1 = Mk(rk , sk) sinh ra từ nón-min Mk, tập chỉ số
(xem [4]) sao cơ sở là Ik+1= Ik(rk , sk) = (Ik {sk}) \ {rk} và các véc tơ chỉ phương
cho:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
(1.18)
18
(
,
và
)= =xk+
xk+1=x = xk - = (1.19)
Quay trở lại bước k với k:= k+1.
1.3.2. Bảng lặp giải bài toán quy hoạch tuyến tính bởi thuật toán nón xoay
xấp xỉ ngoài tuyến tính
Để dễ tính toán, trong mỗi bước lặp k ta thiết lập bảng dưới đây gọi là
bảng nón xoay thu gọn giải bài toán quy hoạch tuyến tính dạng chuẩn khi biết
một nón – min của hàm mục tiêu của bài toán.
Bảng lặp nón xoay thu gọn:
Bảng A
… … Chỉ số cơ sở bj
k=1,2,…
… … b1
…… …… … … … …. ….
( ) (< , >+ ) ( , >+ ) … …
… … … … …
m …
… … -
… …
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
… … … … … … … … ] [ ) ( rk=
19
… … … … … (- )
… … … … …
- … …
xk … …
Bước k=0,1,2,…
Bảng lặp nón xoay thu gọn A gồm 2 phần (xem bảng A): Các số liệu
ban đầu được đưa vào bảng và các số liệu cần tính toán theo các công thức
trong thuật toán nón xoay được xây dựng thứ tự theo các bước từ trên xuống
dưới và từ trái sang phải như sau:
Bước k (k=0, 1, 2, …):
Phần thứ nhất của bảng là khai báo số liệu của bƣớc chuẩn bị:
Đưa vào các số liệu ban đầu của bài toán nằm trong các cột bao gồm có
cột chỉ số cơ sở 1, 2, …, m, cột số liệu các giá trị bi (i=1, 2, …, m), dòng đầu
tiên trên cùng của phần này là các hệ số của hàm mục tiêu, và ma trận hệ số
các ràng buộc A cụ thể là:
- Dòng đầu tiên của bảng là dòng các toạ độ cj của véc tơ C của hàm
mục tiêu.
- Cột đầu tiên thứ nhất là cột chỉ số của các véc tơ dòng Ai của ma
trận ràng buộc A của bài toán (L) từ 1 đến m.
- Cột thứ hai là cột các giá trị của véc tơ cột B của ma
trận ràng buộc.
- Tiếp theo bên phải cột thứ hai là bảng của ma trận hệ số gồm các giá
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
trị của ràng buộc A: aij (i=1,2,…,m; j =1,2,…,n)
20
Phần thứ hai của bảng liền với phần thứ nhất là số liệu tính toán
các giá trị của hệ véc tơ chỉ phƣơng và các toạ độ của đỉnh xk:
Tại bước k (k = 0, 1, 2, …) bảng gồm các cột và ma trận của giá trị
các véc tơ chỉ phương cụ thể như sau:
- Cột thứ nhất là cột chỉ số cơ sở iIk
- Cột thứ hai là cột giá trị bi với
- Tiếp theo bên phải cột thứ hai là bảng ma trận các véc tơ chỉ phương
. Dòng cuối cùng là các giá trị toạ độ của xk là đỉnh của nón-min
Mk đã biết ở bước k.
Đến đây ta có bảng nón xoay tại bước k (k = 0, 1, 2, ….) đã xây dựng xong.
Bây giờ ta chuyển sang kiểm tra tiêu chuẩn tối ưu và xây dựng bảng
nón xoay mới ở bước tiếp theo k+1 nếu xk chưa phải là phương án tối ưu.
Từ dòng cuối cùng của phần thứ hai của bảng là dòng các toạ độ của xk ,
chúng ta đi tính các giá trị và xây dựng tiếp các cột
chứa các giá trị này ở bên phải ma trận ràng buộc A trong phần thứ nhất của bảng.
Từ cột chứa giá trị đã biết này ở bước lặp
k (vị trí bên phải ma trận ràng buộc A). Theo thuật toán nón xoay ta xác định
được tập có hai khả năng:
- Nếu thì dừng và xk là một lời giải của bài (L)
- Nếu thì theo thuật toán nón xoay ta chọn được chỉ số đưa
vào cơ sở sk và chúng ta tiến hành tính toán các cột sau:
Bên phải bảng ở phần thứ hai của bảng ta xây dựng cột chứa
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
giá trị
21
Từ cột giá trị này ta xác định được tập và theo thuật toán ta có hai
khả năng:
+ Nếu thì dừng và kết luận bài toán (L) không có phương án.
+ Nếu thì từ thuật toán nón xoay chúng ta phải xây dựng cột
tính giá trị . Từ đây theo (1.17) của thuật toán nón xoay
tuyến tính ta chọn được chỉ số đưa ra cơ sở là rk .
Đến đây các thông tin để xây dựng bảng lặp ở bước k+1 từ bảng lặp
ở bước k đã đầy đủ, chúng ta xây dựng bảng lặp ở bước k+1 phía dưới bảng
lặp ở bước k như sau:
- Cột đầu tiên của bảng lặp ở bước k+1 là cột chỉ số cơ sở
được xây dựng bằng cách chuyển cột chỉ số cơ sở của
bảng ở bước lặp k xuống và chỉ cần thay chỉ số rk bằng chỉ số sk ở bảng mới
là được.
(bên phải cột chỉ số - Cột tiếp theo là cột chứa các giá trị bi với
cơ sở ) được xây dựng bằng cách chuyển cột chứa các giá tri bi với
của bảng ở bước lặp thứ k xuống và thay giá trị bằng giá trị ở bảng mới
(bước k+1) .
- Tiếp theo bên phải cột là bảng ma trận các véc tơ chỉ
phương của nón-min Mk+1 được tính từ các véc tơ chỉ phương
của nón – min Mk ở bảng lặp bước k theo công thức xoay (1.23).
Sau đó ta tính toán đến dòng cuối cùng tiếp theo của bảng này là dòng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
(xem [4]) các toạ độ của đỉnh nón – min Mk+1 là xk+1 =
22
Đến đây bảng nón xoay mới ở bước lặp k+1 đã được xây dựng xong.
Quá trình lặp này sẽ kết thúc sau hữu hạn bước bởi định lý 1.6.[4],
Một số phần tử trung tâm cần chú ý khi xây dựng bảng nón xoay
thu gọn là:
- Giá trị dương nằm trong cột chứa các giá
trị được ở trong dấu móc tròn ( )
tương ứng với dòng sk (được chọn đưa vào cơ sở ở bước lặp k) theo mục b1)
hay b2) trong thuật toán nón xoay tuyến tính.
- Giá trị nằm trong cột chứa các giá trị
được ở trong dấu móc tròn tương ứng với dòng rk (được chọn
đưa ra cơ sở ở bước lặp k) theo tiêu chuẩn (1.21) và (1.22) của thuật toán nón
xoay tuyến tính.
- Phần tử xoay thuộc cột chứa các giá trị
được nằm trong dấu móc vuông là [ ].
1.3.3. Bài toán quy hoạch tuyến tính tái tối ưu hóa và thuật toán TTH
Trên thực tế do những biến động về kinh tế luôn thay đổi theo thời
gian, có rất nhiều những vấn để trong sản xuất, xây dựng, sửa chữa và cải tạo
lại, … việc bổ sung thêm các điều kiện vật chất vào đầu tư ban đầu là rất cần
thiết và không thể thiếu được. Do vậy lời giải và các kết quả tìm được từ các
mô hình bài toán quy hoạch trước đây đã trở lên lạc hậu và không còn phù
hợp nữa, buộc chúng ta phải bổ sung thêm vào các điều kiện mới cho phù
hợp. Vì thế xuất hiện một dạng bài toán quy hoạch thường gặp và chúng ta
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
phải giải quyết gọi là bài toán tái tối ưu hoá.
23
Ngay khi chúng ta đi giải các bài toán quy hoạch nguyên thì việc phải giải
các bài toán quy hoạch có bổ sung thêm các ràng buộc là không thể tránh khỏi.
Chính vì vậy, dưới đây chúng ta sẽ xét và giải quyết bài toán quy hoạch
tuyến tính dạng chuẩn có thêm ràng buộc bổ sung gọi là bài toán tái tối ưu
hoá trong trường hợp đã biết lời giải của bài toán ban đầu.
1.3.3.1. Bài toán quy hoạch tuyến tính tái tối ưu hoá dạng chuẩn
Xét bài toán qui hoạch tuyến tính dạng chuẩn sau:
xRn, Ai là véc tơ dòng và AiRn, N n, Ai (ai1, ai2, ..., ain) ≠ O(0,…,0) ,
C(c1, c2, …, cn), bi R1, i=1, 2, ..., N. Hạng của hệ Ai (i=1, 2, …, N)
bằng n, giả thiết này rất bình thường bởi vì miền ràng buộc PT của bài toán
quy hoạch tuyến tính thông thường có ràng buộc về dấu của biến x.
Giả sử chúng ta đã biết một lời giải của bài toán (T) là
là đỉnh của nón đơn hình M* với tập chỉ số cơ sở là
Và các véc tơ chỉ phương của các cạnh của nón M* là
Bây giờ ta thêm vào miền ràng buộc PT của bài toán (T) ràng buộc sau:
(1.20)
Khi đó nếu thoả mãn (3.1) thì nó cũng là một lời giải của bài toán
(T*) có thêm ràng buộc bổ sung (3.1), nếu ngược lại mà
(1.21)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Thì chúng ta gọi bài toán sau đây là bài toán tái tối ưu hoá của bài toán (T):
24
Trong đó m=N+1
Rõ ràng để giải bài toán (T*) mà sử dụng phương pháp đơn hình thì
chúng ta sẽ không khai thác được thông tin về việc đã biết lời giải của bài
toán (T). Còn nếu chúng ta sử dụng phương pháp nón xoay trình bày trong
chương 2 thì sẽ khai thác được thông tin nói trên. Đồng thời dựa trên kết quả
của một định lý được chứng minh dưới đây chúng ta sẽ đề ra một quy tắc ưu
tiên chọn chỉ số đưa ra khỏi cơ sở làm cho thuật toán nón xoay trở nên hiệu
quả hơn khi giải bài toán tái tối ưu hoá (T*).
Định lý tái tối ƣu hoá: Nếu là một lời giải của bài toán (T),
nhưng nó không phải là phương án của bài toán (T*) và bài toán (T*) có
phương án, thì bài toán (T*) luôn có phương án tối ưu x* thoả mãn:
Chứng minh: Ta thấy và do là một lời giải của (T) nên:
Điều này có nghĩa là trên miền hàm mục tiêu bài toán (T*) bị chặn
dưới và nó có phương án thì nó phải có phương án tối ưu. Giả sử x1 là một
phương án tối ưu của bài toán (T*), vậy dễ thấy:
1/ Nếu thì ta có ngay điều phải chứng minh.
2/ Nếu (1.22)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Và do không phải là phương án của bài toán (T*) tức ta có (1.21).
25
Gọi
Và (1.23)
Dễ dàng kiểm tra thấy:
(1.24)
Lại từ (1.21), (1.22) dễ dàng thấy và vì tương ứng là
phương án của các bài toán (T) và (T*) nên ta có:
Hay (1.25)
Vậy từ (1.23), (1.24) và (1.25) suy ra là một phương án của bài
toán (T*)
Mặt khác do tính đơn điệu của hàm tuyến tính (là hàm gần lồi-gần lõm)
nên ta có:
(1.26)
Từ (1.26) và do x1 là phương án tối ưu của bài toán (T*) nên suy ra
cũng là phương án tối ưu của bài toán (T*) thoả mãn (1.24).
Định lý được chứng minh
1.3.3.2. Thuật toán xấp xỉ ngoài tái tối ưu hoá
Bây giờ từ thuật toán xấp xỉ ngoài LP trình bày ở trên, chúng ta xây
dựng thuật toán sau đây gọi là thuật toán xấp xỉ ngoài TTH giải bài toán quy
hoạch tuyến tính dạng chuẩn trong trường hợp tái tối ưu hoá, trước hết ta đi
xây dựng nón – min ban đầu của bài toán.
Xây dựng nón-min ban đầu
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Giả sử chúng ta đã biết một lời giải của bài toán (T) là
26
là đỉnh của nón đơn hình M* với tập chỉ số cơ sở là
Và các véc tơ chỉ phương của các cạnh của nón M* là
Nếu chỉ biết đỉnh thì chúng ta có thể thay giá
trị các tọa độ của nó vào vế trái các ràng buộc để xác định tập các chỉ số
cơ sở của nón M* (là tập các chỉ số ứng với các ràng buộc
thoả mãn chặt ), từ đó xác định các véc tơ chỉ phương của các cạnh
có thể từ hệ phương trình định nghĩa trong [4]. của nón M* là
Tóm lại ta luôn biết được một nón-min ban đầu của bài toán (T*) chính
là nón M* với đỉnh của nó là lời giải đã biết của bài toán (T).
Thuật toán xấp xỉ ngoài TTH:
Đã biết nón-min ban đầu của bài toán (T*) như trên.
Bước chuẩn bị (bước 0). Đặt M0 := M* là nón - min của bài toán (T*)
}, x0 = với tập chỉ số cơ sở là I0:=I*={ }={ là đỉnh của M*
và các véc tơ chỉ phương của các cạnh i của nón M0 là = = (i I0).
Bước k ( k=0, 1, 2, ...). Giả sử Mk là nón - min của bài toán (T*) (đã
được xây dựng), với tập chỉ số cơ sở, đỉnh và các véc tơ chỉ phương của các
; xk = và = . cạnh của nón Mk tương ứng là Ik:=
Xác định tập J+(xk) theo (2.9):
1. Nếu J+(xk) = thì dừng lại. xk chính là một lời giải của bài toán (T*),
2. Nếu J+(xk) , ta chọn chỉ số đưa vào cơ sở theo một trong hai
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
cách sau:
27
Ta chọn sk là một chỉ số tuỳ ý thuộc J+(xk)
hoặc ta chọn sk=min{j:jJ+(xk)} (gọi là qui tắc chọn min) (1.27)
hoặc sk = max{j: j J+(xk) (gọi là qui tắc chọn max)
và xác định: ;
, (1.28)
2.1. Nếu = thì dừng lại, suy ra bài toán (T*) không có phương án.
:
2.2. Nếu
Gọi :={ } (1.29)
và chọn chỉ số đưa ra khỏi cơ sở theo một trong hai cách sau:
. Ta chọn rk là chỉ số tuỳ ý thuộc
hoặc ta chọn
rk = min{v: v }
hoặc rk = max{v: v } (1.30)
(cách chọn chỉ số này gọi là qui tắc chọn min (hoặc là qui tắc
chọn max)) .
Và ta xây dựng nón xoay Mk+1 = Mk(rk , sk) sinh ra từ nón-min Mk (xem [4]),
tập chỉ số cơ sở là Ik+1= Ik(rk , sk) = (Ik {sk}) \ {rk}; và các véc tơ chỉ phương:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
(1.31)
28
(
,
Và
)= =xk+
xk+1=x = xk - = (1.32)
ơ Quay trở lại bước k với k k+1
Sự hữu hạn bước lặp của thuật toán đó được suy ra từ định lý 2.10
trong [4].
Một số chú ý khi thực hành sử dụng thuật toán TTH
1/ Rõ ràng ở bước 0 ta có tập J+(x0) := {N+1}, do đó sang bước 1 chỉ số
N+1 được đưa vào cơ sở, vậy theo định lý tái tối ưu hoá thì từ bước này (bước
1) trở đi chỉ số được chọn để đưa ra khỏi cơ sở sẽ là chỉ số nhỏ hơn N+1
2/ Dựa trên định lý tái tối ưu hoá và sử dụng thuật toán TT kết hợp với
phương pháp nhánh-cận Land-Doig chúng ta có thể xây dựng được nhưng
thuật toán hiệu quả để giải các bài toán quy hoạch nguyên tuyến tính.
Chƣơng 2
THUẬT TOÁN NHÁNH CẬN XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY
HOẠCH NGUYÊN TUYẾN TÍNH VÀ ỨNG DỤNG
Rõ ràng thuật toán xấp xỉ ngoài TTH trình bày trong mục 1.3.3.2. ở
chương 1 có nhiều ưu điểm khi sử dụng nó giải cho lớp các bài toán quy
hoạch tuyến tính tái tối ưu hóa hay quy hoạch tuyến tính nguyên. Chính vì
vậy trong chương này, từ thuật toán Land-Doig (trình bày trong mục 1.2.2. ở
chương 1) giải bài toán quy hoạch nguyên tuyến tính, chúng ta kết hợp với
thuật toán xấp xỉ ngoài TTH xây dựng một thuật toán giải bài toán quy hoạch
nguyên tuyến tính dạng chuẩn dưới đây.
2.1. Thuật toán nhánh cận xấp xỉ ngoài giải bài toán quy hoạch nguyên
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
tuyến tính
29
Thuật toán nhánh cận xấp xỉ ngoài ILP
Bước chuẩn bị: Giải bài toán quy hoạch tuyến tính tương ứng với
bằng thuận toán xấp xỉ ngoài LP (bỏ qua điều kiện nguyên) và thu được
phương án tối ưu . Giả sử là không nguyên.
Đặt cận dưới của là và danh mục các bài toán cần xét là
.
Nếu biết là phương án chấp nhận được của bài toán thì đặt
và ngược lại, ta đặt ∞.
Bước lặp k = 1, 2, . . .
1) Nếu thuật toán kết thúc. Khi đó, nếu thì là giá trị
tối ưu và là phương án tối ưu của bài toán. Trong trường hợp ngược lại, bài
toán không có phương án chấp nhận được.
2) Nếu : Chọn là bài toán có cận dưới nhỏ nhất trong Gọi
là miền chấp nhận được, là phương án tối ưu của bài toán quy hoạch
tuyến tính tương ứng với nó.
2.1. Giả sử là một thành phần không nguyên nào đó của . Phân
hoạch tập thành hai tập:
.
Gọi là bài toán
.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Gọi là bài toán
30
.
Đây là các bài toán quy hoạch nguyên tuyến tính.
2.2. Lần lượt giải các bài toán quy hoạch tuyến tính tương ứng với
(bỏ qua điều kiện nguyên) để tính cận dưới đúng cho bài toán ,
chúng ta tiến hành như sau:
Theo định lý tái tối ưu hóa trong mục 1.3.3.2 chương 1, thì bài toán
sẽ có ít nhất một lời giải thỏa mãn chặt ràng buộc
Và bài toán sẽ có ít nhất một lời giải thỏa mãn chặt ràng buộc
Do đó việc giải các bài toán quy hoạch tuyến tính tướng ứng (bỏ qua
điều kiện nguyên) để tính cận dưới đúng cho bài toán , ta giải
các bài toán quy hoạch tuyến tính tương đương ( n-1 chiều) là (bỏ
qua điều kiện nguyên) dưới đây bằng thuật toán xấp xỉ ngoài TTH (trình bày
trong mục 1.3.3.2. của chương 1):
là bài toán:
là bài toán:
Trong đó và
Khi đó, ta có thể gặp một trong các tình huống sau đây:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
a) Phát hiện bài toán không có phương án chấp nhận được.
31
b) Tìm được phương án tối ưu là nguyên.
c) Tìm được phương án tối ưu là không nguyên.
Trường hợp a): Bài toán cũng không có phương án chấp nhận được,
vì vậy ta loại bỏ việc xem xét tiếp theo.
Trường hợp b): Tính lại các kỷ lục theo công thức:
Gọi là kỷ lục tương ứng với giá trị này. Bài toán đã xét xong.
Trường hợp c): Đặt cận dưới của là , và kết nạp nó vào
danh sách các bài toán cần xét:
2.3. Loại bỏ khỏi tất cả các bài toán có cận dưới lớn hơn hoặc
bằng giá trị kỷ lục. Đặt:
và chuyển sang bước k + 1.
Các bước của thuật toán ILP này có thể dễ dàng lập trình chuyển sang các
chương trình trên máy tính bằng các ngôn ngữ như Pascal, C, Basis, Java, ...
2.2. Minh họa ứng dụng thuật toán nhánh cận xấp xỉ ngoài ILP giải bài
toán quy hoạch nguyên tuyến tính có số chiều nhỏ với miền ràng buộc là
hệ bất phƣơng trình tuyến tính
Rõ ràng thuật toán nhánh cận xấp xỉ ngoài ILP trình bày trên sẽ hiệu
quả và thuận lợi trong tính toán khi ứng dụng giải các bài toán giải bài toán
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
quy hoạch nguyên tuyến tính dạng chuẩn có số chiều hay số ràng buộc chính
32
dạng bất phương trình tuyến tính là nhỏ. Trong mục này, chúng ta sẽ ứng
dụng thuật toán này giải lại một số ví dụ đối với bài toán quy hoạch nguyên
tuyến tính dạng chuẩn có số chiều là 2 và “bài toán cái túi” đã được giải trong
các tài liệu [2], [3] và [5]. Trong các trường hợp này chúng ta thấy việc giải
các bài toán phụ khá đơn giản, chỉ là giải các bài toán một biến (không phải
giải bằng phương pháp đơn hình mà chỉ cần tìm giá trị nhỏ ở hai đầu mút của
hàm một biến) hoặc sau một bước lặp sẽ cho ta nhận được ngay cận dưới
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
đúng tương ứng khi giải các bài toán phụ chưa có điều kiện nguyên.
33
Ví dụ 1[3]:
Giải bài toán quy hoạch nguyên tuyến tính P0 sau đây bằng thuật
toán xấp xỉ ngoài ILP:
Kí hiệu là bài toán quy hoạch tuyến tính (bỏ qua điều kiện
nguyên) tương ứng với bài toán quy hoạch nguyên đã cho . Giải
bằng thuật toán xấp xỉ ngoài LP, ta có bảng nón xoay giải bài toán trên sau một
bước lặp cho lời giải
-1 -1 Aj( ) Aj( ) Chỉ số
Cơ sở bj
-4 2 12 0 1 1
4 2 0 0 2 -11
0 -1 -5 -2 3 1/2
-1 0 0 -3/2 4 0
0 -1 -11/2 -5/2 5 0
[-8] 1 -2 (1/8) (4) 0
-1 -11 0 -1/2 1/2 2
Bước 0 0 11/2
1 1 1/8 -1/4
2 -11 -1/8 -1/4
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Bước 1 x1 3/2 5/2
34
Ta được phương án tối ưu: ứng với giá trị hàm mục tiêu
z = - 4.
Đó là cận dưới cho mọi phương án nguyên của bài toán quy hoạch
nguyên đang xét.
Vì biến có giá trị không nguyên nên ta chọn để phân nhánh. Ta
thu được bài toán quy hoạch tuyến tính mới.
Thêm vào ràng buộc ta thu được bài toán .
Thêm vào ràng buộc ta thu được bài toán .
P2
Để tính cận dưới đúng của 2 bài toán này, chúng ta đi giải 2
bài toán quy hoạch tuyến tính tướng ứng với bỏ qua điều kiện
nguyên, theo thuật toán xấp xỉ ngoài ILP thì chúng ta đi giải 2 bài toán quy
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên)
35
Giải 2 bài toán này tương đương với việc giải 2 bài toán một biến
tương ứng sau:
Hay
Dễ dàng thấy lời giải của là và lời giải của là x2.
Suy ra phương án tối ưu của bài toán quy hoạch tuyến tính tương ứng của
là với giá trị mục tiêu và phương án tối ưu của bài
toán quy hoạch tuyến tính tương ứng của là với giá trị mục
tiêu .
Bài toán có giá trị hàm mục tiêu nhỏ hơn nên ta chọn để phân
nhánh, vì biến có giá trị không nguyên nên ta chọn để phân nhánh, ta
thu được hai bài toán quy hoạch tuyến tính mới.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Thêm vào ràng buộc ta thu được bài toán
36
Thêm vào ràng buộc ta thu được bài toán
Để tính cận dưới đúng của 2 bài toán này, chúng ta đi giải 2
bài toán quy hoạch tuyến tính tướng ứng với bỏ qua điều kiện
nguyên, theo thuật toán xấp xỉ ngoài ILP thì chúng ta đi giải 2 bài toán quy
hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên)
Giải 2 bài toán này tương đương với việc giải 2 bài toán một biến
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
tương ứng sau:
37
Hay
Dễ dàng thấy lời giải của là và bài toán là không có
phương án. Suy ra phương án tối ưu của bài toán quy hoạch tuyến tính tương
ứng của là:
và bài toán P5 không có với giá trị mục tiêu
phương án (bài toán P5 bị loại).
Giải bài toán ta thu được phương án tối ưu với giá
trị mục tiêu .
Ta phải xét hai bài toán và do bài toán có giá trị hàm
mục tiêu nhỏ hơn nên ta chọn để phân nhánh.
Vì biến chưa nguyên nên ta chọn để phân nhánh, ta thu
được hai bài toán quy hoạch nguyên tuyến tính mới.
Thêm vào ràng buộc ta thu được bài toán
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Thêm vào ràng buộc ta thu được bài toán
38
Để tính cận dưới đúng của 2 bài toán này, chúng ta đi
giải 2 bài toán quy hoạch tuyến tính tướng ứng với bỏ qua điều
kiện nguyên, theo thuật toán xấp xỉ ngoài ILP thì chúng ta đi giải 2 bài toán
quy hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên)
Giải 2 bài toán này tương đương với việc giải 2 bài toán một biến
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
tương ứng sau:
39
Hay
Dễ dàng thấy lời giải của là không có là x2 = 1 và bài toán
phương án . Suy ra bài toán quy hoạch tuyến tính tương ứng P6 có phương án
tối ưu là với giá trị hàm mục tiêu và bài toán P7 không
có phương án (bài toán P7 bị loại không xét tiếp nữa).
Phương án này có nguyên nên ta nhận được giá trị kỉ lục của
hàm mục tiêu là và đã xét xong (bị loại).
Bài toán có giá trị hàm mục tiêu lớn hơn giá trị kỉ lục nên chắc chắn
nó không chứa phương án nguyên nào tốt hơn (giá trị mục tiêu nhỏ hơn) vì
thế cũng bị loại.
Đến đây không còn bài toán nào phải xem xét nữa nên phương án
nguyên đã nhận được là phương án tối ưu cần tìm của bài toán quy hoạch
nguyên đã cho.
Quá trình giải bài toán nêu trên được thể hiện trong sơ đồ 1 vẽ ở hình
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
dưới đây:
40
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
41
Sơ đồ 1
Không có phƣơng án ( Loại )
Không có
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
phƣơng án ( Loại )
42
Ví dụ 2 [4]:
Một hãng hàng không dự định mua một số máy bay Airbus A320 và
Boing 777 để mở rộng hoạt động. Mỗi máy bay Airbus giá 5 triệu đô và có
thời gian sử dụng 6 năm, mỗi máy bay Boing giá 9 triệu đô và có thời gian sử
dụng 8 năm (các số ở đây là giả định). Hãng ước tính chỉ cần mua 6 máy bay
và số tiền để mua máy bay không quá 46 triệu đô. Hỏi hãng nên mua bao
nhiêu máy bay mỗi loại để tổng thời gian phục vụ của chúng là lâu nhất?
Ta gọi x1 là số máy bay Airbus cần mua và gọi x2 là số máy bay
Boing cần mua, khi đó ta có mô hình bài toán trên là:
Kí hiệu là bài toán quy hoạch tuyến tính (bỏ qua điều kiện
nguyên) tương ứng với bài toán quy hoạch nguyên đã cho. Giải
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
bằng thuật toán xấp xỉ ngoài LP, ta có bảng nón xoay thu gọn giải bài toán trên như sau:
43
-6 -8 Aj( ) Aj( ) Chỉ số cơ sở bj
-1 0 0 -2 1 0
0 -1 -6 -4 2 0
1 1 0 0 3 -6
5 9 8 0 4 -46
1 -1 [-4] (1/2) (1) 0
0 -1 -9 8/9 3 -6
Bước 0 0 6
4 -46 1/4 -1/4
3 -6 -9/4 5/4
Bước 1 x1 2 4
Ta được phương án tối ưu: ứng với giá trị hàm mục tiêu
z = - 44
Bài toán này có ngay lời giải nguyên ở bước chuẩn bị, nó chính là lời
giải của bài toán quy hoạch nguyên tương ứng. Vậy lời giải của bài toán ban
đầu là Hãng Hàng không mua 2 Airbus và 4 Boing thì tổng thời gian sử dụng
lớn nhất là 44 năm.
Ví dụ 3 [3]:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Giải bài toán cái túi P0 sau đây bằng thuật toán xấp xỉ ngoài ILP:
44
Kí hiệu là bài toán quy hoạch tuyến tính (bỏ qua điều kiện nguyên)
tương ứng với bài toán trên. Giải
bằng thuật toán xấp xỉ ngoài LP, ngay ở bước chuẩn bị đã có lời giải tối ưu là x0 = (13/3, 0, 0) ứng với giá trị hàm mục
tiêu z = - 104/3. Đó là cận dưới cho mọi phương án nguyên của bài toán quy
hoạch nguyên đang xét.
Vì biến có giá trị không nguyên nên ta chọn để phân nhánh.
Ta thu được bài toán quy hoạch tuyến tính mới.
Thêm vào ràng buộc ta thu được bài toán .
Thêm vào ràng buộc ta thu được bài toán .
Để tính cận dưới đúng của 2 bài toán này, chúng ta đi giải
2 bài toán quy hoạch tuyến tính tướng ứng với bỏ qua điều kiện
nguyên, theo thuật toán xấp xỉ ngoài ILP thì chúng ta đi giải 2 bài toán quy
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên):
45
Giải 2 bài toán này tương đương với việc giải 2 bài toán hai biến tương
ứng sau:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Hay
46
Giải bài toán bằng thuận toán xấp xỉ ngoài LP thì ngay ở bước
chuẩn bị ta đã thu đươc lời giải tối ưu là với giá trị mục tiêu
, còn bài toán dễ thấy ngay không có phương án. Suy ra bài toán
quy hoạch tuyến tính tương ứng của bài toán P2 có lời giải tối ưu là:
với giá trị mục tiêu , còn bài toán P3
không có phương án (loại).
Bài toán có biến có giá trị không nguyên nên ta chọn để
phân nhánh, ta thu được hai bài toán quy hoạch tuyến tính mới.
Thêm vào ràng buộc ta thu được bài toán
Thêm vào ràng buộc ta thu được bài toán
Để tính cận dưới đúng của 2 bài toán này, chúng ta đi
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
giải 2 bài toán quy hoạch tuyến tính tướng ứng với bỏ qua điều
47
kiện nguyên, theo thuật toán xấp xỉ ngoài ILP thì chúng ta đi giải 2 bài toán
quy hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên)
Giải 2 bài toán này tương đương với việc giải 2 bài toán hai biến tương
ứng sau:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Hay
48
Giải bài toán bằng thuật toán xấp xỉ ngoài TTH, sau một bước
. lặp từ bảng nón xoay thu gọn ta được lời giải tối ưu là
vậy ta nhận được kỷ lục
Giải bài toán bằng thuật toán xấp xỉ ngoài TTH, ngay ở bước chuẩn
bị ta đã nhận được lời giải tối ưu là . Vậy ta suy ra lời giải của
, với giá trị bài toán quy hoạch tuyến tính tương ứng P5 là
mục tiêu là
Ta xét tiếp bài toán P5, có biến x1 có giá trị không nguyên nên ta chọn
x1 để phân nhánh, ta thu được hai bài toán quy hoạch nguyên tuyến tính mới.
Thêm vào ràng buộc ta thu được bài toán
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Thêm vào ràng buộc ta thu được bài toán
49
Để tính cận dưới đúng của 2 bài toán
2 bài toán quy hoạch tuyến tính tướng ứng với này, chúng ta đi giải bỏ qua điều kiện
nguyên, theo thuật toán xấp xỉ ngoài ILP thì chúng ta đi giải 2 bài toán quy
hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên)
Giải 2 bài toán này tương đương với việc giải 2 bài toán hai biến tương
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
ứng sau:
50
Hay
Giải bài toán bằng thuật toán xấp xỉ ngoài TTH, ngay ở bước chuẩn
bị ta đã nhận được lời giải tối ưu là . Vậy ta suy ra lời giải của
với giá trị bài toán quy hoạch tuyến tính tương ứng P6 là
mục tiêu
, vậy ta nhận được kỷ lục mới là
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
.
51
Dễ dàng thấy bài toán không có phương án vậy suy ra bài toán P7
không có phương án (loại bài toán P7)
Đến đây không còn bài toán nào phải xem xét nữa, nên phương án
nguyên đã nhận được là phương án tối ưu cần tìm của bài toán quy hoạch
nguyên đã cho.
Vậy lời giải của bài toán cái túi P0 ban đầu là
Quá trình giải bài toán nêu trên được thể hiện trong sơ đồ 2 vẽ ở hình dưới
đây:
Sơ đồ 2
P3
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
= -33
Không có phƣơng án ( Loại )
52
KẾT LUẬN
Luận văn đã trình bày việc xây dựng thuật toán nhánh cận giải bài toán
quy hoạch nguyên tuyến tính, đó là lớp bài toán quy hoạch có nhiều ứng dụng
trong thực tế. Các phương pháp giải bài toán quy hoạch tuyến tính đã có rất
nhiều, song các thuật toán hầu hết là chỉ cho lời giải chưa nguyên. Vì vậy đã
xuất hiện các phương pháp cắt, phương pháp nhánh cận để giải các bài toán
quy hoạch nguyên, các phương pháp này khi thực hiện để giải bài toán quy
hoạch nguyên trong mỗi bước đều phải giải các bài toán phụ (chưa có điều
kiện nguyên) bổ sung thêm bất phương trình vào miền ràng buộc. Do đó để
làm tăng thêm tính hiệu quả của các phương pháp nhánh cận được biết thì
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
việc giải trực tiếp các bài toán quy hoạch tuyến tính với miền ràng buộc là hệ
53
bất phương trình tuyến tính là rất cần thiết. Chính vì thế, luận văn đã trình bày
thuật toán nhánh cận xấp xỉ ngoài ILP giải bài toán quy hoạch nguyên tuyến
tính thực chất chính là thuật toán nhánh cận Land-Doig, tuy nhiên trong mỗi
bước khi giải các bài toán quy hoạch tuyến tính tương ứng (chưa có điều kiện
nguyên) thuật toán đã khai thác các đặc thù riêng (dựa trên định lý tái tối ưu
hóa trong 1.3.3.1 của chương 1) cho nhận biết các bài toán quy hoạch tuyến
tính này có lời giải tối ưu thỏa mãn chặt các ràng buộc và
. Và do đó khi sử dụng thuật toán xấp xỉ ngoài LP và TTH trong
cuối chương 1 để giải các bài toán quy hoạch tuyến tính tương ứng phụ để tìm
các cận dưới đúng hiệu quả hơn so với một số phương pháp khác như phương
pháp đơn hình (vì phải thêm vào nhiều biến phụ để đưa bài toán về dạng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
chính tắc và không khai thác được tính tái tối ưu hóa của các bài toán phụ).
54
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Lê Dũng Mưu (1998), Nhập môn các phương pháp tối ưu, NXB
Khoa học và Kỹ thuật.
[2] Nguyễn Đức Nghĩa (1997), Tối ưu hoá (Quy hoạch tuyến tính và
rời rạc), NXB Giáo dục.
[3] Bùi Minh Trí (2008), Bài tập tối ưu hoá, NXB Khoa học và Kỹ
thuật.
[4] Nguyễn Anh Tuấn, Nguyễn Văn Quý (2012), Quy hoạch tuyến tính
với phương pháp nón xoay, NXB Giáo dục Việt Nam.
[5] Trần Vũ Thiệu, Bùi Thế Tâm (1998), Các phương pháp tối ưu hóa,
NXB Giao thông Vận tải.
Tiếng Anh
[6] Belenski A.C. (1982), Minimization monotone function in a polyhedron
set, Automatic and Tele - Mechanics 9, pp. 112-121.
[7] Dantzig G. B., Thapa M. N. (1997), Linear Programming, 1: Introduction,
Springer - Verlag New York.
[8] Tuan N.A. and Duong P.C. (1996), Minimization of an almost-convex
and almost-concave functions, Vietnam Journal of Mathematics, 24(1), pp. 57-74.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
[9] Tuy H. (1998), Convex Analysis and Global Optimization, Kluwer.
