zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Giải thuật nâng cao: Quy hoạch tuyến tính - TS. Ngô Quốc Việt

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

Báo xấu

97
lượt xem 12
download

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

Bài giảng này trang bị cho người học những kiến thức về quy hoạch tuyến tính. Nội dung chính trình bày trong bài giảng gồm có: Giới thiệu chung về quy hoạch tuyến tính, giải quy hoạch tuyến tính dựa trên đồ thị, bài toán đối ngẫu, giải thuật Simplex, Max-Flow dựa trên LP. 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 Giải thuật nâng cao: Quy hoạch tuyến tính - TS. Ngô Quốc Việt

QUY HOẠCH TUYẾN TÍNH TS. NGÔ QUỐC VIỆT 2015
Nội dung 1. Giới thiệu 2. Giải quy hoạch tuyến tính dựa trên đồ thị 3. Bài toán đối ngẫu 4. Giải thuật Simplex 5. Max-Flow dựa trên LP Giải thuật nâng cao-Quy hoạch tuyến tính 2
Giới thiệu  Mục tiêu kinh doanh thường: maximizing profit hoặc minimizing costs.  Quy hoạch tuyến tính (Linear programming) sử dụng các quan hệ tuyến tính để biểu diễn các quyết định, với business objective, và các constraints.  Linear Programming model tìm maximize hoặc minimize linear function, thỏa mãn linear constraints. Giải thuật nâng cao-Quy hoạch tuyến tính 3
Quy hoạch tuyến tính • Nhiều vấn đề thực tế có dạng linear programming. • Các vấn đề thực khác có thể xấp xỉ theo linear models. • Có nhiều ứng dụng trong : • Manufacturing, Marketing, Finance (investment), Advertising, Agriculture, Energy, etc. • Có nhiều kỹ thuật hiệu quả nhằm tìm nghiệm của linear programming models. Giải thuật nâng cao-Quy hoạch tuyến tính 4
Giới thiệu Chuyển vấn đề sang LP 1. Xác định vấn đề có thể giải bằng linear programming. 2. Lập mô hình toán của unstructured problem theo các bước a. Xác định hàm mục tiêu b. Xác định các biến quyết định c. Xác định ràng buộc 3. Giải mô hình dựa trên một số kỹ thuật. Giải thuật nâng cao-Quy hoạch tuyến tính 5
Quy hoạch tuyến tính-ví dụ 1 MAX 4X1 + 7X3 - 6X4 2X1 + 3X2 - 2X4 = 20 -2X2 + 9X3 + 7X4  10 -2X1 + 3X2 + 4X3 + 8X4  35 Ràng buộc X2  5 Mọi X  0 X1  0, X2  0, X3  0, X4  0 Giải thuật nâng cao-Quy hoạch tuyến tính 6
Quy hoạch tuyến tính-ví dụ 2 • Resource 40 giờ công mỗi ngày Availability: 120 lbs đất sét • Decision x1 = số chén (bowl) sản xuất mỗi ngày Variables: x2 = số ca (mug) sản xuất mỗi ngày • Objective Maximize Z = $40x1 + $50x2 Function: với Z = lợi nhuận mỗi ngày • Resource 1x1 + 2x2  40 (giờ công) Constraints: 4x1 + 3x2  120 lbs đất sét • Non-Negativity x1  0; x2  0 Constraints: Giải thuật nâng cao-Quy hoạch tuyến tính 7
Quy hoạch tuyến tính-ví dụ 2 (tt) Mô hình tuyến tính Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Giải thuật nâng cao-Quy hoạch tuyến tính 8
Quy hoạch tuyến tính-ví dụ 3 • Post office cần số nhân viên theo từng ngày trong tuần, được xác định trong bảng cụ thể. • Quy định: mỗi nhân viên phải làm 5 ngày liên tục, rồi nghỉ hai ngày. • Yêu cầu: lập LP sao cho post office có thể sử dụng ít nhân viên nhất. Giải thuật nâng cao-Quy hoạch tuyến tính 9
Quy hoạch tuyến tính-ví dụ 3 • Đặt: x1, x2,…, x7 là số nhân viên làm việc bắt đầu tương ứng vào Monday, Tue, …, Sun (x1 làm từ Mon đến Fri) • Hàm mục tiêu: z=Min (x1+x2+…+x7) • Ràng buộc: x1+ +x4+x5+x6+x7 >=17 x1+ x2+ +x5+x6+x7 >=13 x1+x2+x3+ +x6+x7 >=15 x1+x2+x3+ x4+ +x7 >=19 x1+x2+x3+x4+x5 >=14 x2+x3+x4+x5+x6 >=16 x3+x4+x5+x6+x7 >=11 Giải thuật nâng cao-Quy hoạch tuyến tính 10
Các thành phần của mô hình • Các biến quyết định – ký hiệu toán biểu diễn các trạng thái/mức độ của một vấn đề cụ thể. Các biến quyết định là độc lập • Hàm mục tiêu – quan hệ tuyến tính mô tả mục tiêu, theo các decision variable – yêu cầu là cần cực đại/tiểu hàm này. • Ràng buộc – các yêu cầu hay hạn chế ràng buộc bài toán, thể hiện quan hệ tuyến tính giữa các decision variable. • Tham số - các hệ số và hằng của hàm mục tiêu và ràng buộc. Giải thuật nâng cao-Quy hoạch tuyến tính 11
Phương pháp đồ thị cho LP • Phương pháp graphical phù hợp cho các mô hình linear programming chỉ có hai decision variables • Phương pháp graphical thể hiện trực quan lời giải của linear programming problem. Giải thuật nâng cao-Quy hoạch tuyến tính 12
Phương pháp đồ thị cho LP • Xét ví dụ 2 X2: số mug Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 X1: số bowl Giải thuật nâng cao-Quy hoạch tuyến tính 13
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Đồ thị ràng buộc giờ công Giải thuật nâng cao-Quy hoạch tuyến tính 14
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Vùng ràng buộc giờ công Giải thuật nâng cao-Quy hoạch tuyến tính 15
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Vùng ràng buộc đất sét Giải thuật nâng cao-Quy hoạch tuyến tính 16
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Hai ràng buộc Giải thuật nâng cao-Quy hoạch tuyến tính 17
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Vùng nghiệm Giải thuật nâng cao-Quy hoạch tuyến tính 18
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Đường giá trị hàm mục tiêu với Z =800 Giải thuật nâng cao-Quy hoạch tuyến tính 19
Phương pháp đồ thị cho LP (tt) Maximize Z = $40x1 + $50x2 Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Các đường khác của hàm mục tiêu Giải thuật nâng cao-Quy hoạch tuyến tính 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.