zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán cao cấp 1: Chương 5b - Nguyễn Văn Tiến

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:8

Báo xấu

56
lượt xem 2
download

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

Bài giảng "Toán cao cấp 1 - Chương 5b: Quy hoạch tuyến tính hai biến" cung cấp cho người học các kiến thức: Dạng ma trận của bài toán quy hoạch tuyến tính, đưa bài toán về dạng chính tắc, tính chất của tập phương án,... 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 Toán cao cấp 1: Chương 5b - Nguyễn Văn Tiến

16/04/2017 CHƯƠNG 5b Ví dụ 1 • Vậy ta có mô hình bài toán: f  x   f  x1 , x2 , x3   3x1  2 x2  2,5 x3  max QUY HOẠCH TUYẾN TÍNH 0,04 x1  0,06 x2  0,05 x3  500  0,07 x1  0,02 x3  300 HAI BIẾN  x  0 j  1, 2,3    j • Đây là bài toán quy hoạch tuyến tính 3 biến, tìm giá trị lớn nhất của hàm mục tiêu. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ 1 Ví dụ 2 • Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, • Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, đạm, đường, khoáng cho một loại gia súc tương ứng là 90g, 130g, 10g. Cho biết hàm lượng các chất dinh dưỡng đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, tiền trên có trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi lãi cho một bánh mỗi loại được cho trong bảng sau: loại được cho trong bảng sau: • Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần • Hãy lập mô hình toán học của bài toán xác định khối lượng sản xuất sao cho không bị động về nguyên liệu mà lãi đạt thức ăn mỗi loại phải mua để tổng số tiền chi cho mua được cao nhất. thức ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi ngày. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ 1 Ví dụ 3 • Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập • Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và cẩm, bánh dẻo cần phải sản xuất. giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau: • Điều kiện: xj ≥ 0 = 1,2,3 • Tiền lãi thu được (ngàn đồng) f  x   f  x1 , x2 , x3   3x1  2 x2  2,5 x3 • Lượng đường sử dụng và điều kiện: • Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất 0,04 x1  0,06 x2  0,05 x3  500 và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao • Lượng đậu sử dụng và điều kiện: động tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6. 0,07 x1  0,02 x3  300 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 1
16/04/2017 Ví dụ 4 Ví dụ 4 • Bài toán lập kế hoạch sản xuất • Bài toán sau có dạng chính tắc: • Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả 260 x1  120 x2  600 x3  max sử, đối với: • Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m 2 x1  x2  3 x3  500 ván 100 x  40 x  250 x  40000  1 2 3 • Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván  6  1 x  x2 • Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván  x1 , x2 , x3  0 thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài toán QHTT tổng quát Dạng ma trận của bài toán QHTT 1 f  x   c1 x1  c2 x2  ...  cn xn  min (max) • Xét bài toán QHTT dạng:   ai1 x1  ai 2 x2  ...  ain xn   bi  i  1, 2,.., m  f  x   c1 x1  c2 x2  ...  cn xn  min (max) 2     a11 x1  a12 x2  ...  a1n xn  b1  a x  a x  ...  a x  b  0   21 1 22 2 2n n 2   3 x j  0  j  1, 2,..., n  ..........................................  am1 x1  am 2 x2  ...  amn xn  bm tuy y  xj  0 (1) Hàm f(x) gọi là hàm mục tiêu (2) là hệ ràng buộc chính (3) là hệ ràng buộc dấu (2) Và (3) gọi chung là hệ ràng buộc của bài toán Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài toán dạng chính tắc Dạng ma trận của bài toán QHTT n f  x    c jx j  min (max) • Đặt: • Các ràng buộc  a11 a12 ... a1n   b1   x1   c1  j1 chính đều là  a a ... a2 n     b   x   c  n phương trình A   21 22 b 2  x 2 c 2  aijx j  bi (i  1,m)  ....................   ...   ...   ...  • Các ẩn đều  a a ... a         j1  m1 m 2 mn   bm   xn   cn  x  0 (j  1,n) không âm  j • Ta có dạng ma trận của bài toán QHTT: Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài f  cT x  min  max  toán dạng chính tắc tương đương theo nghĩa trị tối ưu  Ax  b của hàm mục tiêu trong hai bài toán là trùng nhau và từ  x  0 phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 2
16/04/2017 Các loại phương án Đưa bài toán về dạng chính tắc • Định nghĩa. Vec tơ ∈ thỏa tất cả các ràng • Bước 2. Kiểm tra điều kiện dấu các ẩn số buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được. • Nếu có ẩn dạng: xi  0 ta đổi biến: xi   xi • Nếu ẩn xi có dấu tùy ý ta đổi biến: xi  xi  xi • Định nghĩa. Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài • Chú ý: • Các ẩn mới và các ẩn phụ đều không âm. toán max) hay nhỏ nhất (nếu là bài toán min) • Hệ số của các ẩn phụ trong hàm mục tiêu là 0. thì được gọi là phương án tối ưu (PATU). • Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ được PATU của bài toán dạng tổng quát đã cho. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ Ví dụ • Cho bài toán QHTT: • Đưa bài toán sau về dạng chính tắc: f  x   120 x1  100 x2  max f  x   2 x1  4 x2  x3  min  2 x1  3x2  8 4 x1  6 x2  3 x3  12   5 x1  3x2  15 7 x1  x3  3  x  0, x  0   1 2 2 x1  3 x2  5 x3  6  x1  0, x2  0 • Trong các phương án sau phương án nào là phương án chấp nhận được. 1   2 1   2 u1    u2    u3    u4     2  2  3 1  Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Đưa bài toán về dạng chính tắc Tính chất của tập phương án • Bước 1. Kiểm tra ràng buộc chính • Định nghĩa. Đoạn thẳng nối hai điểm x1 và x2 được định nghĩa: • Ràng buộc dạng nhỏ hơn: • ai1 x1  ai 2 x2  ...  ain xn  bi x  R n x   x1  1    x2 , 0    1  • Ta cộng thêm ẩn phụ: • Nhận xét ai1 x1  ai 2 x2  ...  ain xn  xn k  bi • Nếu = 0 chúng ta có x2, = 1 chúng ta có x1. • Ràng buộc dạng lớn hơn: • Những điểm thuộc đoạn thẳng với 0 < < 1 gọi là ai1 x1  ai 2 x2  ...  ain xn  bi các điểm trong của đoạn thẳng • Ta trừ đi ẩn phụ: • x1, x2 gọi là các điểm biên của đoạn thẳng. ai1 x1  ai 2 x2  ...  ain xn  xn  k  bi Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 3
16/04/2017 Tính chất của tập phương án Tập lồi và tính chất • Định lý. Cho x1 và x2 là hai phương án chấp nhận được • Tập S gọi là tập lồi nếu với hai điểm phân biệt của bài toán QHTT. Điểm = 1 + 1 − 2 với 0 ≤ ≤ 1 thuộc đoạn thẳng nối hai điểm x1 và x2 . bất kỳ x1 và x2 thuộc S thì đoạn nối hai điểm x1 • Khi đó: và x2 cũng nằm trong tập S. • i) x cũng là phương án chấp nhận được • ii) Nếu các f(x1)=f(x2) thì f(x)=f(x1)=f(x2) Tập lồi • iii) Nếu f(x1)
16/04/2017 Điểm cực biên của tập hợp lồi Phương pháp đồ thị • Định lý. Điểm x của tập lồi S được gọi là điểm cực biên • Dùng cho bài toán quy hoạch tuyến tính 2 biến của S nếu x không là tổ hợp lồi của hai điểm của S khác x. • Xét bài toán quy hoach tuyến tính : 2 • Nhận xét: f  x    c j x j  min  max  • Nếu có x1, x2 thuộc S sao cho j 1 x   x1  1    x2 ,   0  2  aij x j  bi • Thì:  j 1 x  x1  x2 x  0  j A, B, C, D, E là các điểm cực biên Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Tính chất tập phương án Phương pháp đồ thị • Tập hợp các phương án của một bài toán quy • Biểu diễn các ràng buộc lên đồ thị Oxy. hoạch tuyến tính là một tập lồi đa diện. • Xác định phần được giới hạn bởi các ràng buộc là tập phương án. • Nếu tập hợp lồi đa diện này không rỗng và bị chặn thì đó là một đa diện lồi. Số điểm cực biên • Xác định các điểm cực biên (đỉnh) của tập phương án thỏa mãn các ràng buộc. của nó là hữu hạn. • Xác định giá trị của hàm mục tiêu tại các điểm cực biên. • So sánh và suy ra phương án tối ưu Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Phương án cực biên Ví dụ 1 • Định nghĩa. Điểm cực biên của tập các phương • Giải bài toán QHTT sau: án S trong bài toán QHTT gọi là phương án cực f  x1 , x2    x1  x2  min biên. 2 x1  x2  2 1 • Tính chất.   x1  x2  2  2 • Số phương án cực biên của tập phương án S   x1  x2  5  3 trong bài toán QHTT là hữu hạn  x  0, x  0  1 2 • Nếu bài toán QHTT dạng chính tắc có phương án tối ưu thì nó sẽ có một phương án cực biên là phương án tối ưu. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 5
16/04/2017 Ví dụ 1 Ví dụ 3 • Biểu diễn đồ thị các bất đẳng • Một xí nghiệp có thể sử dụng tối đa 510 giờ máy thức lên hệ trục tọa độ ta cán, 360 giờ máy tiện, 150 giờ máy mài để chế tạo được miền các phương án là C 3 loại sản phẩm A, B, C. Để chế tạo một đơn vị sản hình ngũ giác ABCDE. Các phẩm A cần 9 giờ máy cán, 5 giờ máy tiện, 3 giờ điểm có tọa độ như sau A(0,0); B D máy mài; 1 đơn vị sản phẩm B cần 3 giờ máy cán, 4 B(0,2); C(1,4); D(4,1); E(2,0) là A E giờ máy tiện; 1 đơn vị sản phẩm C cần 5 giờ máy các điểm cực biên. lần lượt cán. 3 giờ máy tiện, 2 giờ máy mài. Mỗi sản phẩm thay các cực biên vào hàm A trị giá 48 ngàn đồng, mỗi sản phẩm B trị giá 16 mục tiêu ta có f(A) = 0; f(B) = 2; ngàn đồng, mỗi sản phẩm C trị giá 27 ngàn đồng. f(C) = 3; f(D) = -3; f(E) = -2. • Vấn đề đặt ra là xí nghiệp cần chế tạo bao nhiêu • Vậy phương án tối ưu x*=(4,1) đơn vị sản phẩm mỗi loại để tổng giá trị sản phẩm tại đó hàm mục tiêu đạt giá trị xí nghiệp thu được là lớn nhất, với điều kiện không Min dùng quá số giờ hiện có của mỗi loại máy. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ 2 Tìm PACB bằng pp Đại số • Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu • Xét bài toán QHTT dạng chính tắc: 100 mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ chính quyết định sản lượng kế hoạch. Thợ rèn có 2000 f  x   cT x  min (max) công, thợ sắt có 3000 công, thợ mộc có 1500 công. Định mức lao động của mỗi loại tàu được cho trong  A.x  b bản:  100 mã lực 50 mã lực x  0 Thợ sắt (3000) 150 70 Thợ rèn (2000) 120 50 • A là ma trận cấp m.n (giả sử m≤n) Thợ mộc (1500) 80 40 • Ma trận A có hạng là m (có m dòng độc lập • Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt tuyến tính) tổng số mã lực cao nhất? Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ 2 Nghiệm cơ bản • Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã • Phương trình A.x=b được viết lại dạng: lực cần đóng x1 A1  x2 A2  ...  xn An  0 • Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2 max • Chọn m cột của ma trận A độc lập tuyến tính • Điều kiện: • Giả sử ta có các cột A1, A2, …, Am • Cho các biến tương ứng với các cột còn lại bằng 0 150x1  70x 2  3000 120x  50x  2000 • Giải phương trình ràng buộc với các biến còn lại  1 2  • Nghiệm tìm được kết hợp với các biến đã cho bằng 0  80 x 1  40 x 2  1500 tạo thành nghiệm cơ bản của bài toán. x1  0, x 2  0 Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 6
16/04/2017 Ví dụ Phương án cực biên • Cho hệ phương trình tuyến tính 4 ẩn như sau: • Nghiệm cơ bản thỏa mãn điều kiện các thành phần đều không âm gọi là phương án cực biên của bài toán.  x1  x2  x3 4 • PACB có đúng m thành phần dương gọi là PACB không  suy biến 5 x1  3x2  x4  15 • PACB có ít hơn m thành phần dương gọi là PACB suy • Tìm tất cả các nghiệm cơ bản biến. • Định lý. Nếu x=(x1,x2,…,xn) là PACB của tập các phương án S= {A.x=b, x≥0} thì các cột của A tương ứng với xj>0 là độc lập tuyến tính. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Phương án cơ bản Kiểm tra phương án cực biên • Xét bài toán QHTT dạng chính tắc có tập các • Chứng minh nó là phương án ràng buộc: • Đặt T={Aj|xj>0} trong đó Aj là các vectơ cột của ma trận hệ số A. S   x Ax  b, x  0 • Chứng minh các vectơ của T tạo thành hệ vectơ • Nghiệm cơ bản của hệ phương trình tuyến tính độc lập tuyến tính A.x=b thỏa mãn điều kiện về dấu x≥0 được gọi là phương án cơ bản của bài toán QHTT. Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ Ví dụ • Tìm tất cả các phương án cơ bản của bài toán • Chứng minh rằng x=(1,2,3,0) là PACB của bài QHTT: toán QHTT sau: f  4 x1  3x2  max • Với các điều kiện: Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 7
16/04/2017 Ví dụ • Tìm tất cả các phương án cực biên của bài toán QHTT: f  4 x1  3x2  max • Với các điều kiện: Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến Ví dụ Giá trị hàm Nghiệm cơ bản Phương án cực biên mục tiêu X1=(3/2; 5/2;0;0) X2=(3;0;1;0) X3=4;0;0;-5) X4=(0;5;-1;0) X5=(0;4;0;3) X6=(0;0;4;15) Bài giảng Toán Cao cấp 1 Nguyễn Văn Tiến 8

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.