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

Chia sẻ: Hoamaudon | Ngày: | Loại File: PDF | Số trang:86

Thêm vào BST

Báo xấu

39
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

TỐI ƯU HÓA VÀ QUY HOẠCH TUYẾN TÍNH Thời lượng: 30 tiết ltnhan1001@gmail.com 1
TÀ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ính Tối ưu hóa nói chung và Quy hoạch tuyến tính nói riêng là một phần kiến thức không thể thiếu cho tất cả những người làm việc trong lĩnh vực ứng dụng của khoa học và kỹ thuật. Đặc biệt với sinh viên tin họ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 tin học vào thực tế.
4 NỘI DUNG Chươ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 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
6 MỤC TIÊU CHƯƠNG 1. Biết được các khái niệm về bài toán QHTT 2. 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đ)
7 NỘI DUNG CHƯƠNG 1.1 Bài toán dẫn đến bài toán QHTT 1.2 Bài toán QHTT tổng quát, chính tắc, chuẩn tắc 1.3 Phương pháp hình học 1.4 Các dạng đặc biệt của bài toán QHTT 1.5 Phương pháp đơn hình 1.6 Phương pháp đơn hình mở rộng (ko thi)
8 1.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
10 Bài toán sản xuất tối ưu Gọi xj ,j = 1,2,3 là số đơn vị sản phẩm bánh loại cầ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ản xuấ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  30000 Tổng doanh thu Công ty thu được khi bán hết sản phẩm: Z  2 x1  3x2  4 x3
11 Bài toán sản xuất tối ưu Mô 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
12 Bài toán sản xuất tối ưu tổng quát Trong đó: aij gọi là hệ số công nghệ
13 Mô hình toán học của bài toán QHTT Tì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.
14 Mộ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 ….
15 1.2 Bài toán QHTT  Bài toán QHTT tổng quát (1.2)
16 Bà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.
17 1.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.
18 1.2 Bài toán QHTT Ví 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
19 1.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  3} - Phương án: x0  (1,0,3), x1  (7,3,0) là 2 phương án cơ bản của bài toán (1.2.1). - Phương án: x0=(7,3,0) là PATƯ và Zmax=11 Thật vậy: Z  2 x1  x2  2 x3  2(1  2 x2 )  x2  2(3  x2 )  8  x2  11, 0  x2  3
20 Tính chất của bài toán QHTT  Nếu bài toán max(min) có phương án và hàm mục tiêu bị chặn trên (dưới) thì có phương án tối ưu.  Nếu bài toán QHTT có nhiều hơn một PATƯ thì có vô số PATƯ. Nếu x0 và x1 là 2 PATƯ thì bao lồi của nó là: x   x  (1   ) x ,   [0,1] 0 1 cũng là PATƯ của bài toán này.