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

MỤC LỤC

Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

PHƯƠNG PHÁP HÌNH HỌC.1

1.1. Các bài toánthực tế.1

1.1.1. Bài toán lập kếhoạch sản xuất.1

1.1.2. Bài toán vận tải.2

1.1.3. Bài toán xác định khẩu phần.2

1.2. Bài toán qui hoạch tuyếntính.2

1.3. Phương pháp hình học.3

1.4. Bài tập.5

Chương 2. PHƯƠNG PHÁP ĐƠN HÌNH.6

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

2.1.1. Định nghĩa.6

2.1.2. Các phép biến đổi.6

2.1.3. Phương án cơbản.7

2.1.4. Các tính chất.7

2.2. Phương pháp đơn hình.8

2.2.1. Nội dung.8

2.2.2. Bảng đơn hình.9

2.2.3. Cơsởlý luận.10

2.2.4. Các bước của thuật toán đơn hình.13

2.2.5. Bài toán ẩn phụ.15

2.2.6. Bài toán ẩn giả.16

2.3. Cài đặt thuật toán đơn hình.20

2.3.1. Khai báo dữliệu.20

2.3.2. Tính các ước lượng ∆j.20

2.3.3. Kiểm tra tối ưu và tìm ẩn thay thế.20

2.3.4. Kiểmtra vô nghiệm.20

2.3.5. Tìm ẩn loại ra.21

2.3.6. Biến đổi bảng.21

2.4. Bài tập.22

Chương 3. BÀI TOÁN ĐỐI NGẪU.24

3.1. Các bài toánthực tế.24

3.1.1. Bài toán lập kếhoạch sản xuất.24

3.1.2. Bài toán đánh giá sản phẩm.24

3.2. Bài toán đối ngẫu.25

3.2.1. Đối ngẫu không đối xứng.25

3.2.2. Đối ngẫu đối xứng.26

3.2.3. Sơ đồtucker.28

3.3. Các nguyên lý đối ngẫu.28

3.3.1. Nguyên lý 1.29

3.3.2. Nguyên lý 2.29

3.3.3. Nguyên lý 3 (Độlệch bù).29

3.4. Ý nghĩa kinhtế.30

3.4.1. Ý nghĩa bài toán (2).30

________________________________________________________________________

GV: Phan Thanh Tao

Bài giảng Quy hoạch toán học Trang 64

________________________________________________________________________

3.4.2. Ý nghĩa bài toán (2

~

).30

3.4.3. Ý nghĩa nguyên lý độlệch bù.31

3.5. Bài tập.31

Chương 4. BÀI TOÁN VẬN TẢI.33

4.1. Bài toán vận tải dạng chính tắc.33

4.1.1. Định nghĩa.33

4.1.2. Điều kiện cân bằng thu phát.34

4.2. Bảng phân phối và tính chất.34

4.2.1. Bảng phân phối.34

4.2.2. Tính chất.35

4.3. Thuật toán thếvị.36

4.3.1. Nội dung.36

4.3.2. Xây dựng phương án cơbản ban đầu.36

4.3.3. Các bước của thuật toán thếvị.37

4.4. Các dạng khác.38

4.4.1. Không cân bằng thu phát.38

4.4.2. Suy biến.39

4.4.3. Dạng cực đại.41

4.4.4. Bài toán xe rỗng.45

4.4.5. Bài toán ô cấm.47

4.5. Cài đặt thuật toán thếvị.48

4.5.1. Khai báo dữliệu.48

4.5.2. Xây dựng phương án cơbản ban đầu.48

4.5.3. Xây dựng hệthống thếvị.49

4.5.4. Kiểm tra tối ưu.49

4.5.5. Tìmvòng điều chỉnh.50

4.5.6. Biến đổi bảng.50

4.6. Bài tập.51

Chương 5. PHƯƠNG PHÁP HUNGARY.53

5.1. Bài toán bổnhiệm.53

5.2. Bài tập.62

pdf64 trang | Chuyên mục: Đại Số Tuyến Tính | Chia sẻ: dkS00TYs | Ngày: 02/10/2014 | Lượt xem: 5098 | Lượt tải: 15download
Tóm tắt nội dung Bài giảng Quy hoạch tuyến tính, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
1.1. Các bài toán thực tế......................................................................................................... 1 
1.1.1. Bài toán lập kế hoạch sản xuất...................................................................................... 1 
1.1.2. Bài toán vận tải ............................................................................................................. 2 
1.1.3. Bài toán xác định khẩu phần......................................................................................... 2 
1.2. Bài toán qui hoạch tuyến tính ......................................................................................... 2 
1.3. Phương pháp hình học .................................................................................................... 3 
1.4. Bài tập ............................................................................................................................. 5 
Chương 2. PHƯƠNG PHÁP ĐƠN HÌNH................................................................................ 6 
2.1. Dạng chính tắc và dạng chuẩn tắc................................................................................... 6 
2.1.1. Định nghĩa..................................................................................................................... 6 
2.1.2. Các phép biến đổi.......................................................................................................... 6 
2.1.3. Phương án cơ bản.......................................................................................................... 7 
2.1.4. Các tính chất ................................................................................................................. 7 
2.2. Phương pháp đơn hình .................................................................................................... 8 
2.2.1. Nội dung........................................................................................................................ 8 
2.2.2. Bảng đơn hình............................................................................................................... 9 
2.2.3. Cơ sở lý luận ............................................................................................................... 10 
2.2.4. Các bước của thuật toán đơn hình............................................................................... 13 
2.2.5. Bài toán ẩn phụ ........................................................................................................... 15 
2.2.6. Bài toán ẩn giả ............................................................................................................ 16 
2.3. Cài đặt thuật toán đơn hình ........................................................................................... 20 
2.3.1. Khai báo dữ liệu.......................................................................................................... 20 
2.3.2. Tính các ước lượng ∆j ................................................................................................. 20 
2.3.3. Kiểm tra tối ưu và tìm ẩn thay thế .............................................................................. 20 
2.3.4. Kiểm tra vô nghiệm .................................................................................................... 20 
2.3.5. Tìm ẩn loại ra .............................................................................................................. 21 
2.3.6. Biến đổi bảng .............................................................................................................. 21 
2.4. Bài tập ........................................................................................................................... 22 
Chương 3. BÀI TOÁN ĐỐI NGẪU....................................................................................... 24 
3.1. Các bài toán thực tế....................................................................................................... 24 
3.1.1. Bài toán lập kế hoạch sản xuất.................................................................................... 24 
3.1.2. Bài toán đánh giá sản phẩm ........................................................................................ 24 
3.2. Bài toán đối ngẫu .......................................................................................................... 25 
3.2.1. Đối ngẫu không đối xứng ........................................................................................... 25 
3.2.2. Đối ngẫu đối xứng ...................................................................................................... 26 
3.2.3. Sơ đồ tucker ................................................................................................................ 28 
3.3. Các nguyên lý đối ngẫu................................................................................................. 28 
3.3.1. Nguyên lý 1................................................................................................................. 29 
3.3.2. Nguyên lý 2................................................................................................................. 29 
3.3.3. Nguyên lý 3 (Độ lệch bù)............................................................................................ 29 
3.4. Ý nghĩa kinh tế.............................................................................................................. 30 
3.4.1. Ý nghĩa bài toán (2) .................................................................................................... 30 
________________________________________________________________________ 
GV: Phan Thanh Tao 
Bài giảng Quy hoạch toán học Trang 64 
________________________________________________________________________ 
3.4.2. Ý nghĩa bài toán ( 2~ )................................................................................................... 30 
3.4.3. Ý nghĩa nguyên lý độ lệch bù ..................................................................................... 31 
3.5. Bài tập ........................................................................................................................... 31 
Chương 4. BÀI TOÁN VẬN TẢI .......................................................................................... 33 
4.1. Bài toán vận tải dạng chính tắc ..................................................................................... 33 
4.1.1. Định nghĩa................................................................................................................... 33 
4.1.2. Điều kiện cân bằng thu phát........................................................................................ 34 
4.2. Bảng phân phối và tính chất.......................................................................................... 34 
4.2.1. Bảng phân phối ........................................................................................................... 34 
4.2.2. Tính chất ..................................................................................................................... 35 
4.3. Thuật toán thế vị ........................................................................................................... 36 
4.3.1. Nội dung...................................................................................................................... 36 
4.3.2. Xây dựng phương án cơ bản ban đầu ......................................................................... 36 
4.3.3. Các bước của thuật toán thế vị.................................................................................... 37 
4.4. Các dạng khác ............................................................................................................... 38 
4.4.1. Không cân bằng thu phát ............................................................................................ 38 
4.4.2. Suy biến ...................................................................................................................... 39 
4.4.3. Dạng cực đại ............................................................................................................... 41 
4.4.4. Bài toán xe rỗng.......................................................................................................... 45 
4.4.5. Bài toán ô cấm ............................................................................................................ 47 
4.5. Cài đặt thuật toán thế vị ................................................................................................ 48 
4.5.1. Khai báo dữ liệu.......................................................................................................... 48 
4.5.2. Xây dựng phương án cơ bản ban đầu ......................................................................... 48 
4.5.3. Xây dựng hệ thống thế vị............................................................................................ 49 
4.5.4. Kiểm tra tối ưu ............................................................................................................ 49 
4.5.5. Tìm vòng điều chỉnh ................................................................................................... 50 
4.5.6. Biến đổi bảng .............................................................................................................. 50 
4.6. Bài tập ........................................................................................................................... 51 
Chương 5. PHƯƠNG PHÁP HUNGARY ............................................................................. 53 
5.1. Bài toán bổ nhiệm ......................................................................................................... 53 
5.2. Bài tập ........................................................................................................................... 62 
________________________________________________________________________ 
GV: Phan Thanh Tao 

File đính kèm:

  • pdfUnlock-Quy_Hoach_tuyen_tinh_Bai_giang.pdf
Tài liệu liên quan