Một cải tiến cách chọn véc tơ đưa vào cơ sở của phương pháp nón xoay giải bài toán quy hoạch tuyến tính

®¹i häc th¸i nguyªn

Tr-êng ®¹i häc khoa häc

VŨ VĂN CÔNG

MỘT CẢI TIẾN CÁCH CHỌN VÉC TƠ ĐƯA

VÀO CƠ SỞ CỦA PHƯƠNG PHÁP NÓN XOAY

GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

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

th¸i nguyªn - n¨m 2014

®¹i häc th¸i nguyªn

Tr-êng ®¹i häc KHOA HäC

VŨ VĂN CÔNG

[

MỘT CẢI TIẾN CÁCH CHỌN VÉC TƠ ĐƯA

VÀO CƠ SỞ CỦA PHƯƠNG PHÁP NÓN XOAY

GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

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

Chuyên ngành: Toán ứng dụng

Mã số: 60 46 01 12

Người hướng dẫn khoa học: TS. NGUYỄN ANH TUẤN

Thái Nguyên, 2014

1

Mục lục

Mục lục ..................................................................................................1

Mở đầu...................................................................................................2

Chương 1 Bài toán quy hoạch tuyến tính và phương pháp giải........4

1. Bài toán quy hoạch tuyến tính tổng quát .........................................4

1.1. Dạng chuẩn và dạng chính tắc ..................................................5

1.2. Đưa bài toán quy hoạch tuyến tính về dạng chuẩn hoặc chính

tắc.....................................................................................................5

2. Phương pháp đơn hình và phương pháp nón xoay ..........................7

2.1. Phương pháp đơn hình giải bài toán QHTT dạng chính tắc .......7

2.2. Phương pháp nón xoay 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...........................11

2.2.1. Khái niệm về nón đơn hình tuyến tính ...............................11

2.2.2. Khái niệm về cạnh của nón đơn hình .................................11

2.2.3. Khái niệm nón xoay M(r,s) sinh ra từ nón M .....................14

2.2.4. §Þnh nghÜa Nón cực tiểu (Nón-min) ..................................17

2.3. Phương pháp nón xoay tuyến tính............................................18

2.3.1. Thuật toán nón xoay tuyến tính..........................................19

2.3.2. Bảng lặp giải bài toán qui hoạch tuyến tính bởi thuật toán

nón xoay tuyến tính và ví dụ minh hoạ ........................................21

Chương 2 Một cách chọn véc tơ đưa vào cơ sở................................26

2.1. Lựa chọn chỉ số đưa vào cơ sở....................................................26

2.2. Ví dụ bằng số minh hoạ ..............................................................30

Tài liệu tham khảo ..............................................................................32