Phương pháp điểm trong giải quy hoạch tuyến tính

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ HỒNG LÊ

PHƯƠNG PHÁP ĐIỂM TRONG

GIẢI QUI HOẠCH TUYẾN TÍNH

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - Năm 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ HỒNG LÊ

PHƯƠNG PHÁP ĐIỂM TRONG

GIẢI QUI HOẠCH TUYẾN TÍNH

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số : 60.46.36

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 - Năm 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

Mục lục

Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i

LỜI NÓI ĐẦU 1

Nội dung 5

1 KIẾN THỨC CHUẨN BỊ 5

1.1 Qui hoạch tuyến tính và qui hoạch đối ngẫu . . . . . . . . 5

1.2 Phương pháp đơn hình và đơn hình đối ngẫu . . . . . . . . 9

1.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 12

1.4 Ví dụ Klee-Minty về độ phức tạp mũ . . . . . . . . . . . . . 15

2 PHƯƠNG PHÁP ELLIPSOID 19

2.1 Về hệ bất phương trình đại số tuyến tính . . . . . . . . . . 20

2.2 Kỹ thuật ellipsoid . . . . . . . . . . . . . . . . . . . . . . . 23

2.3 Thuật toán Khachian . . . . . . . . . . . . . . . . . . . . . 26

2.4 Áp dụng vào giải qui hoạch tuyến tính . . . . . . . . . . . . 29

3 PHƯƠNG PHÁP ĐIỂM TRONG 30

3.1 Tâm giải tích . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2 Đường trung tâm . . . . . . . . . . . . . . . . . . . . . . . 34

3.2.1 Đường trung tâm đối ngẫu . . . . . . . . . . . . . . 37

3.2.2 Đường trung tâm gốc-đối ngẫu . . . . . . . . . . . 40

3.3 Chiến thuật giải . . . . . . . . . . . . . . . . . . . . . . . . 41

3.3.1 Phương pháp hàm chắn gốc . . . . . . . . . . . . . . 43

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

3.3.2 Phương pháp bám đường gốc- đối ngẫu . . . . . . . 45

3.3.3 Phương pháp hàm thế gốc- đối ngẫu . . . . . . . . . 48

3.3.4 Độ phức tạp của mỗi vòng lặp . . . . . . . . . . . . 51

3.4 Vấn đề khởi sự và kết thúc thuật toán . . . . . . . . . . . . 52

3.4.1 Khởi sự thuật toán . . . . . . . . . . . . . . . . . . 53

3.4.2 Kết thúc thuật toán . . . . . . . . . . . . . . . . . 54

3.4.3 Thuật toán HSD . . . . . . . . . . . . . . . . . . . 56

Kết luận 61

Tài liệu tham khảo 64

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1

LỜI NÓI ĐẦU

Nhiều bài toán thực tế trong kinh tế, tài chính, công nghiệp và kỹ thuật

có thể diễn đạt như bài toán qui hoạch tuyến tính, tức là dưới dạng bài

toán tìm cực đại (hay cực tiểu) 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.

Phương pháp đơn hình do Dantzig đề xuất từ năm 1947, đến nay vẫn

còn được sử dụng rộng rãi để giải các bài toán qui hoạch tuyến tính. Cách

tiếp này chỉ cần xét các đỉnh của tập đa diện ràng buộc và mỗi lần lặp đi

từ một đỉnh tới một đỉnh kề với nó, thường là tốt hơn đỉnh trước đó (cải

tiến được giá trị của hàm mục tiêu). Cuối cùng, nó đạt tới đỉnh mà từ đó

không thể cải tiến hàm mục tiêu được nữa, đỉnh đó chính là lời giải cần

tìm của bài toán.

Mặc dầu nó rất hiệu quả trong thực tiễn (số lần lặp thường nhỏ hơn

m+n, trong đó m là số ràng buộc tuyến tính và n là số biến của bài toán).

Tuy nhiên, V.Klee và G.Minty(1972) đã đưa ra một bài toán qui hoạch

tuyến tính đặc biệt mà để giải nó cần một thời gian tỉ lệ với hàm mũ của

n. Điều này chứng tỏ về mặt lý thuyết thuật toán đơn hình không phải là

một thuật toán thời gian đa thức.

Vào những năm 1950, người ta đã đề cao tới các phương pháp điểm

trong (đi từ phía trong miền ràng buộc). Tuy nhiên, chúng chưa thành đạt

như phương pháp đơn hình. Năm 1979 [4] Khachian là người đầu tiên đã

chứng minh được rằng có thể giải bài toán qui hoạch tuyến tính trong thời

gian đa thức, bằng cách sử dụng thuật toán điểm trong thích hợp. Mặc

dầu thuật toán Khachian chưa đủ hiệu quả trong thực tiễn, nhưng thành

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

2

tựu này của Khachian đã làm khởi sắc sự quan tâm trở lại tới các phương

pháp điểm trong giải qui hoạch tuyến tính.

Tiếp đó, năm 1984 [3] Karmarkar đã đề xuất một phương pháp điểm

trong mới giải qui hoạch tuyến tính. Phương pháp này có độ phức tạp đa

thức và nó có hiệu năng thực tiễn cao, đặc biệt đối với các bài toán tuyến

tính cỡ lớn.

Các công trình nghiên cứu của Khachian và Karmarkar là điểm khởi

đầu cho nhiều nghiên cứu về các phương pháp điểm trong giải qui hoạch

tuyến tính. Đó cũng là chủ đề chính của luận văn này. Cách tiếp cận mới

khác cơ bản với phương pháp đơn hình . Thay cho đi trên các cạnh của tập

ràng buộc từ đỉnh này tới đỉnh khác, các điểm lặp (xấp xỉ) đi men theo

“ đường trung tâm” để tới tập lời giải. Có nhiều dạng phương pháp điểm

trong , tiêu biểu nhất là phương pháp chắn gốc, phương pháp bám đường

gốc-đối ngẫu tạo ra lời giải cho cả hai bài toán gốc và đối ngẫu của qui

hoạch tuyến tính, phương pháp hàm thế ,...Trong nhiều năm kể từ 1984,

các thuật toán và phần mềm giải qui hoạch tuyến tính đã trở nên hoàn

toàn tinh xảo và có thể nói rằng đến nay các phương pháp điểm trong đã

thực sự chiếm ưu thế.

Cũng đã có nhiều mở rộng của phương pháp điểm trong để giải các bài

toán tối ưu phi tuyến; qui hoạch lồi toàn phương, qui hoạch nón. . . Chẳng

hạn, Nesterov và Nemirovsky (1994) [6] đã xây dựng cơ sở lý thuyết các

phương pháp điểm trong cho tối ưu hóa lồi.

Luận văn này đề cập tới các phương pháp điểm trong giải qui hoạch

tuyến tính do Khachian và Karmarkar đề xuất. Việc tìm hiểu và nghiên

cứu chủ đề này là rất cần thiết và hữu ích giúp hiểu được các mở rộng và

ứng dụng của phương pháp điểm trong vào các bài toán tối ưu khác. Nội

dung luận văn được chia thành ba chương:

Chương 1“ Kiến thức chuẩn bị” nhắc lại tóm tắt một số kiến thức cơ

bản cần thiết về bài toán qui hoạch tuyến tính và lý thuyết đối ngẫu trong

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn