Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính

Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính, cung cấp cho người học những kiến thức như: Bài toán dẫn đến bài toán quy hoạch tuyến tính; Bài toán quy hoạch tuyến tính tổng quát, chính tắc, chuẩn tắc; Phương pháp hình học; Các dạng đặc biệt của bài toán quy hoạch tuyến tính; Phương pháp đơn hình; Phương pháp đơn hình mở rộng (ko thi). Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tínhTỐI ƯU HÓA VÀ QUY HOẠCH TUYẾN TÍNH Thời lượng: 30 tiết ltnhan1001@gmail.com 1TÀI LIỆU THAM KHẢO[1] NGUYỄN THÀNH CẢ, Tối ưu hóa quy hoạch tuyến tính. NXB Lao Động 2010 2 3 Tính cần thiết của môn học Tối ưu hóa và Quy hoạch tuyến tínhTối ưu hóa nói chung và Quy hoạch tuyến tính nóiriêng là một phần kiến thức không thể thiếu cho tấtcả những người làm việc trong lĩnh vực ứng dụngcủa khoa học và kỹ thuật. Đặc biệt với sinh viên tinhọc, nó là kiến thức căn bản của nhiều ứng dụng,thể hiện thế mạnh và ưu việt của các phát triển tinhọc vào thực tế. 4NỘI DUNGChương 1. Bài toán quy hoạch tuyến tính (bài 1,2- Tuần 1,2)Chương 2. Bài toán đối ngẫu (bài 3-tuần 3)Chương 3. Bài toán vận tải (Bài 4-Tuần 4) 5 CHƯƠNG 1BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 6MỤC TIÊU CHƯƠNG1. Biết được các khái niệm về bài toán QHTT2. Hiểu được PP hình học giải bài toán QHTT(hai biến)3. Hiểu được PP đơn hình (THI: 5đ) 7NỘI DUNG CHƯƠNG1.1 Bài toán dẫn đến bài toán QHTT1.2 Bài toán QHTT tổng quát, chính tắc, chuẩntắc1.3 Phương pháp hình học1.4 Các dạng đặc biệt của bài toán QHTT1.5 Phương pháp đơn hình1.6 Phương pháp đơn hình mở rộng (ko thi) 81.1 Bài toán dẫn đến bài toán QHTT Bài toán sản xuất tối ưu: Một Công ty sản xuất bánh trung thu cần sản xuất 3 sản phẩm bánh từ 3 loại nguyên liệu chính khác nhau, với các thông số như sau:Bài toán sản xuất tối ưu Loại Khối lượng Loại bánh nguyên liệu nguyên liệu(g) L1 L2 L3 Đường 10000 10 20 20 Bột 50000 20 30 30 Sữa 30000 20 30 40 Giá bán 1 đv sản phẩm ($) 2 3 4 Giả sử các sp sau khi sản xuất được tiêu thụ hết. Hãy lập kế hoạch sản xuất tối ưu cho Công ty?(XS ntn để lợi nhuận cao nhất) 9 10Bài toán sản xuất tối ưuGọi xj ,j = 1,2,3 là số đơn vị sản phẩm bánh loạicần sản xuất. Ta có điều kiện x j  0, j  1, 2,3.Tổng khối lượng nguyên liệu các loại dùng để sảnxuất 3 sản phẩm: - Đường: 10 x1  20 x2  20 x3  10000 - Bột: 20 x1  30 x2  30 x3  50000 - Sữa: 20 x1  30 x2  40 x3  30000Tổng doanh thu Công ty thu được khi bán hết sảnphẩm: Z  2 x1  3x2  4 x3 11Bài toán sản xuất tối ưuMô hình toán học của bài toán san xuất tối ưu:Tìm xj ,j = 1,2,3 , sao cho: Z  2 x1  3 x2  4 x3  max 10x1  20 x2  20 x3  10000 20 x1  30 x2  30 x3  50000 20 x1  30 x2  40 x3  30000 x j  0, j  1, 2, 3 12Bài toán sản xuất tối ưu tổng quátTrong đó: aij gọi là hệ số công nghệ 13Mô hình toán học của bài toán QHTTTìm x j , ( j  1, n) saocho n Z   c j x j  max j 1 n a j 1 ij x j  bi ,(i  1, m) (1.1.1) x j  0, ( j  1, n)(1.1.1) là một dạng bài toán quy hoạch tuyến tính. 14Một số bài toán khác Bài toán xác định khẩu phần ăn tối ưu Bài toán pha trộn Bài toán bổ nhiệm …. 151.2 Bài toán QHTT Bài toán QHTT tổng quát (1.2) 16Bài toán QHTT Phương án. Một vector n chiều x*  n thỏa hệ ràng buộc (1.2) được gọi là một PA chấp nhận được hay PA. Tập hợp tất cả các PA của bài toán QHTT gọi là tập phương án hay miền ràng buộc. 171.2 Bài toán QHTT Phương án cơ bản (PACB) Một PA thỏa mãn với dấu đẳng thức ít nhất n ràng buộc được gọi là phương án cơ bản. Một PACB thoả mãn đúng n ràng buộc với dấu đẳng thức gọi là PACB không suy biến. Phương án tối ưu Một phương án thỏa luôn hàm mục tiêu của (1.1) gọi là PA tối ưu. 181.2 Bài toán QHTTVí dụ 1.2.1: Xét bài toán QHTT Z  2 x1  x2  2 x3  max x1  2 x2 1 x2  x3  3 (1.2.1) x1 , x2 , x3  0 191.2 Bài toán QHTT - Tập phương án của (1.2.1) là:   {(1  2 x2 , x2 ,3  x2 ) / 0  x2 ...