Giáo trình môn tối ưu hóa tuyến tính - ĐH Đồng Tháp

gaconueh2005

Thành viên thân thiết
Thành viên thân thiết
Tham gia
3/3/2013
Bài viết
4.056
Mục lục:

CHƯƠNG I : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
I- GIỚI THIỆU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1- Bài toán vốn đầu tư
2- Bài toán lập kế hoạch sản xuất
3- Bài toán vận tải
II- ĐỊNH NGHĨA VÀ NHỮNG KẾT QUẢ CƠ BẢN
1- Quy hoạch tuyến tính tổng quát
2- Quy hoạch tuyến tính dạng chính tắc
3- Phương án
4- Đa diện lồi các phương án khả thi - Phương pháp hình học
III- MỘT VÍ DỤ MỞ ĐẦU
IV- DẤU HIỆU TỐI ƯU
1- Ma trận cơ sở - Phương án cơ sở - Suy biến
2- Dấu hiệu tối ưu
CHƯƠNG II : GIẢI THUẬT ĐƠN HÌNH
I- GIẢI THUẬT ĐƠN HÌNH CƠ BẢN
1- Cơ sở lý thuyết
2- Định lý về sự hội tụ
3- Giải thuật đơn hình cơ bản
4- Chú ý trong trường hợp suy biến
II- GIẢI THUẬT ĐƠN HÌNH CẢI TIẾN
1- Một cách tính ma trận nghịch đảo
2- Quy hoạch tuyến tính dạng chuẩn
3- Giải thuật đơn hình cải tiến
4- Phép tính trên dòng - Bảng đơn hình
III- PHƯƠNG PHÁP BIẾN GIẢ CẢI BIÊN
1- Bài toán cải biên
2- Phương pháp hai pha
3- Phương pháp M vô cùng lớn
CHƯƠNG III : BÀI TOÁN ĐỐI NGẪU
I- KHÁI NIỆM VỀ ĐỐI NGẪU
1- Đối ngẫu của quy hoạch tuyến tính dạng chính tắc
2- Định nghĩa đối ngẫu trong trường hợp quy hoạch tổng quát
3- Các định lý về sự đối ngẫu
II- GIẢI THUẬT ĐỐI NGẪU
CHƯƠNG IV : ỨNG DỤNG QUY HOẠCH TUYẾN TÍNH
I- MỞ ĐẦU
II- BÀI TOÁN TRÒ CHƠI

1- Trò chơi có nghiệm ổn định
2- Trò chơi không có nghiệm ổn định
III- BÀI TOÁN VẬN TẢI
1- Mở đầu
2- Các khái niệm cơ bản
3- Bài toán vận tải cân bằng thu phát
4- Các bài toán được đưa về bài toán vận tải
IV- BÀI TOÁN DÒNG TRÊN MẠNG
1- Mở đầu
2- Phát biểu bài toán dòng trên mạng
V- QUY HOẠCH NGUYÊN
1- Mở đầu
2- Bài toán quy hoạch nguyên trong thực tế
ST
 

Đính kèm

Hiệu chỉnh:
BÀI GIẢNG:LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH
TUYẾN TÍNH
Chương này trình bày cách xây dựng mô hình quy hoạch tuyến tính của những
bài toán dạng đơn giản. Đây là những kiến thức quan trọng để xây dựng mô hình cho
những bài toán phức tạp hơn trong thực tế sau này. Các khái niệm về ‘’ lồi’’ đuợc
trình bày để làm cơ sở cho phương pháp hình học giải quy hoạch tuyến tính. Một ví
dụ mở đầu được trình bày một cách trực quan để làm rõ khái niệm về phương án tối
ưu của quy hoạch tuyến tính.

Nội dung chi tiết của chương bao gồm :

I- GIỚI THIỆU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

1- Bài toán vốn đầu tư
2- Bài toán lập kế hoạch sản xuất
3- Bài toán vận tải

II- QUY HOẠCH TUYẾN TÍNH TỔNG QUÁT VÀ CHÍNH TẮC

1- Quy hoạch tuyến tính tổng quát
2- Quy hoạch tuyến tính dạng chính tắc
3- Phương án

III- ĐẶC ĐIỂM CỦA TẬP HỢP CÁC PHƯƠNG ÁN

1- Khái niệm lồi và tính chất
2- Đặc điểm của tập các phương án
3- Phương pháp hình học

IV- MỘT VÍ DỤ MỞ ĐẦU
V- DẤU HIỆU TỐI ƯU

1- Ma trận cơ sở - Phương án cơ sở - Suy biến
2- Dấu hiệu tối ưu

ST
 

Đính kèm

Hiệu chỉnh:
GIẢI THUẬT ĐƠN HÌNH
Chương này trình bày một cách chi tiết nội dung của giải thuật đơn hình. Sau
phần cơ sở lý thuyết của giải thuật là các ví dụ tương ứng. Các ví dụ được trình bày
đúng theo các bước của giải thuật. Kiến thức trong chương này cần thiết cho việc lập
trình giải quy hoạch tuyến tính trên máy tính.
Nội dung chi tiết của chương bao gồm :
I- GIẢI THUẬT ĐƠN HÌNH CƠ BẢN
1- Cơ sở xây dựng giải thuật đơn hình cơ bản
2- Định lý về sự hội tụ
3- Giải thuật đơn hình cơ bản
4- Chú ý trong trường hợp suy biến
II- GIẢI THUẬT ĐƠN HÌNH CẢI TIẾN
1- Một cách tính ma trận nghịch đảo
2- Quy hoạch tuyến tính dạng chuẩn
3- Giải thuật đơn hình cải tiến
4- Phép tính trên dòng - Bảng đơn hình
III- PHƯƠNG PHÁP BIẾN GIẢ CẢI BIÊN
1- Bài toán cải biên
a- Cải biên bài toán quy hoạch tuyến tính
b- Quan hệ giữa bài toán xuất phát và bài toán cải biên
2- Phương pháp hai pha
3- Phương pháp M vô cùng lớn
IV- QUY HOẠCH TUYẾN TÍNH SUY BIẾN
1- Các ví dụ về quy hoạch tuyến tính suy biến
2- Xử lý quy hoạch tuyến tính suy biến
ST
 

Đính kèm

Hiệu chỉnh:
BÀI TOÁN ĐỐI NGẪU
Chương này trình bày trình bày khái niệm đối ngẫu, các quy tắc đối ngẫu và
giải thuật đối ngẫu. Đây là các kiến thức có giá trị trong ứng dụng vì nhờ đó có thể
giải một quy hoạch tuyến tính từ quy hoạch tuyến tính đối ngẫu của nó.
Nội dung chi tiết của chương này bao gồm :
I- KHÁI NIỆM VỀ ĐỐI NGẪU
1- Đối ngẫu của quy hoạch tuyến tính dạng chính tắc
2- Định nghĩa đối ngẫu trong trường hợp tổng quát
3- Các định lý về sự đối ngẫu
a- Định lý 1 ( đối ngẫu yếu )
b- Định lý 2
c- Định lý 3
d- Định lý 4 ( sự đối ngẫu)
e- Định lý 5 (tính bổ sung )
II- GIẢI THUẬT ĐỐI NGẪU
ST
 

Đính kèm

Hiệu chỉnh:
ỨNG DỤNG QUY HOẠCH TUYẾN TÍNH
Chương này trình bày các bài toán để thấy khả năng ứng dụng rộng rãi của
quy hoạch tuyến tính. Bài toán trò chơi được trình bày một cách chi tiết, các bày toán
còn lại chỉ trình bày mô hình. Việc giải các bài toán này được nghiên cứu thêm trong
các môn tiếp theo.
Nội dung chi tiết của chương này bao gồm :
I- MỞ ĐẦU
II- BÀI TOÁN TRÒ CHƠI
1- Trò chơi có nghiệm ổn định
2- Trò chơi không có nghiệm ổn định
III- BÀI TOÁN VẬN TẢI
1- Mở đầu
2- Các khái niệm cơ bản
3- Bài toán vận tải cân bằng thu phát
4- Các bài toán được đưa về bài toán vận tải
IV- BÀI TOÁN DÒNG TRÊN MẠNG
1- Mở đầu
2- Phát biểu bài toán dòng trên mạng
V- QUY HOẠCH NGUYÊN
1- Mở đầu
2- Bài toán quy hoạch nguyên trong thực tế
ST
 

Đính kèm

BÀI TẬP TỔNG HỢP
I- Xí nghiệp sản xuất giấy có 3 phân xưởng. Do trang bị kỹ thuật khác nhau nên mức
hao phí tre gỗ, axit để sản xuất một tấn giấy thành phẩm cũng khác nhau. Mức hao phí
được cho trong bảng dưới đây :
Mức hao phí nguyên liệu cho 1 tấn giấy
Nguyên liệu P.Xưởng I P.Xưởng II P.Xưởng III
Tre gỗ 1,4 (tấn) 1,3 1,2
Axit 0,1 0,12 0,15
Số lượng tre gỗ có trong năm là 1.500.000 tấn, Axit là 100.000 tấn.
Yêu cầu
1. Xây dựng mô hình sao cho tổng số giấy sản xuất trong năm của xí nghiệp là
nhiều nhất.
2. Xây dựng mô hình bài toán đối ngẫu với mô hình toán của câu 1.
........
ST
 

Đính kèm

Hiệu chỉnh:
×
Quay lại
Top Bottom