LINK TẢI LUẬN VĂN MIỄN PHÍ CHO AE KET-NOI
LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Trong thực tế ta thường hay gặp các tình huống là phải lựa chọn một trong số những quyết định quan trọng để đưa ra những phương án hay chiến lược tốt nhất trong sản xuất kinh doanh hay trong một trò chơi mà đối thủ là một kẻ thông minh và nguy hiểm…Khi đó ta cần lập mô hình toán học quy hoạch tuyến tính để có được phương án tối ưu cần thiết.
Trong đó phương pháp đơn hình được George Bemanrd Dantzig đưa ra năm 1947 cùng lúc với việc khai sinh ra quy hoạch tuyến tính, phương pháp này thực sự có hiệu quả để giải những bài toán quy hoạch tuyến tính cỡ lớn trong thực tế mà ta thường gặp, như để vận chuyển hàng hóa đầy đủ nhưng có tổng chi phí là nhỏ nhất – đây chính là bài toán vận tải. hay trong kinh doanh phải lập kế hoạch sản xuất đối với các nguyên liệu và sản phẩm để thu được tổng lợi nhuận là lớn nhất…
Kiến thức sau khi học quy hoạch tuyến tính rất cần thiết, đây là những kiến thức rất quan trọng để xây dựng một mô hình toán học cho bất kỳ bài toán phức tạp nào trong thực tế, chỉ cần xây dựng các thuật toán đã mô hình hóa ngôn ngữ nhờ việc lập trình trên máy tính ta có thể giải quy hoạch tuyến tính một cách dể dàng nhanh chóng và chính xác. Như vậy việc học quy hoạch tuyến tính rất quan trọng, nó đem lại những hiệu quả kinh tế rất lớn nếu biết lập các mô hình và tính toán đúng quy cách.
2. Đối tượng nghiên cứu và phương pháp nghiên cứu.
Quy hoạch tuyến tính là lĩnh vực nghiên cứu các bài toán tối ưu mà hàm mục tiêu là vấn đề được quan tâm nhất và các ràng buộc là các yêu cầu ,điều kiện của kế hoạch đặt ra, đều là hàm và các phương trình, bất phương trình tuyến tính. Các bước để nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điển hình là:
Xác định vấn đề cần giải quyết, thu thập dữ liệu .
Lập mô hình toán học thật chính xác.
Xây dựng các thuật toán để giải bài toán trên các lập trình máy tính.
Tính toán thử và điều chỉnh mô hình nếu cần .
Áp dụng để giải các bài toán thực tế .
CHƯƠNG 1:
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
A. LÝ THUYẾT
1. ĐỊNH NGHĨA
Bài toán quy hoạch tuyến tính (qhtt) tổng quát có dạng:
Tìm xj, j=1,2,…,n sao cho: f=(max) (1)
Với hệ ràng buộc: , i=1,2,…,m (2)
, j=1,2,…,n (3)
(1) được gọi là hàm mục tiêu, nó có thể là cực tiểu (min) hay cực đại (max).
(2) được gọi là các ràng buộc chung hay ràng buộc hàm, nó có thể có dạng bất đẳng thức (≤ hay ≥) hay có dạng đẳng thức (=).
(3) được gọi là các ràng buộc dấu (của biến), nó có thể không âm (≥0), không dương (≤0) hay tùy ý.
Như vậy, bài toán QHTT là bài toán có các biểu thức xác định hàm mục tiêu và các ràng buộc chung đều ở dạng tuyến tính.
Véctơ x=(x1, x2,…,xn)T được gọi là phương án (pa) hay lời giải chấp nhận được của bài toán QHTT nếu nó thỏa mãn hệ ràng buộc của bài toán.
Phương án x*=(được gọi là phương án tối ưu (patư) hay lời giải tối ưu, nghiệm tối ưu của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt nhất.
Tức là: f(x*)= là giá trị hàm mục tiêu tại phương án x=(x1,x2,…,xn)T bất kỳ. (Dấu ≤ ứng với bài toán cực tiểu. Dấu ≥ ứng với bài toán cực đại).
Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nếu có).
Hai bài toán QHTT được gọi là tương đương với nhau nếu chúng có chung tập hợp các phương án tối ưu.
Mệnh đề: (Quan hệ giữa bài toán cực đại và bài toán cực tiểu)
(Trong đó: X là tập hợp các phương án)
Tức là: nếu đổi dấu hàm mục tiêu và đổi loại hàm mục tiêu thì ta được bài toán tương đương. Vì lí do này mà khi nghiên cứu cách giải bài toán qhtt, người ta chỉ xét bài toán có loại hàm mục tiêu là cực tiểu (hay chỉ xét bài toán có loại hàm mục tiêu là cực đại)
2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 2 BIẾN
Bài toán có dạng: tìm x=(x1,x2)T sao cho f(x)=c1x1+c2x2 min (max)
Với hệ ràng buộc: ai1x1+ai2x2≥bi, i=1,2,…,m
Chú ý:
Ràng buộc chung có dạng: a≤b, ta đưa về dạng tương đương là: -a≥-b.
Ràng buộc chung có dạng: a = b thì tương đương với: a≥b và –a≥-b.
Còn các ràng buộc biến có thể xem là các trường hợp riêng của các ràng buộc chung.
Như vậy, hệ ràng buộc của bài toán QHTT có 2 biến luôn luôn có thể giả thiết là có dạng: ai1x1+ai2x2≥bi; i=l, 2..., m
2.1. Xác định miền phương án
Đưa các điểm (x1,x2) lên hệ trục tọa độ vuông góc. Ta xác định được các điểm thỏa mãn phương trình: ai1x1+ai2x2=b, hình thành nên một đường thẳng chia mặt phẳng tọa độ thành 2 nửa mặt phẳng (mp). Một nửa mp bao gồm các điểm (x1, x2) thỏa mãn bất phương trình: ai1x1+ai2x2≥bi, và nửa kia bao gồm các điểm (x1, x2) thỏa mãn bất phương trình: ai1x1+ai2x2≤bi.
Trong thực hành, để xác định nửa mp nào ứng với bất phương trình: ai1x1+ai2x2≥bi. Ta thường lấy một điểm đặc biệt như (0,0); (0,1); (1,0);… thay vào bất phương tình, nếu nó thỏa mãn thì nửa mp chứa điểm đặc biệt đó là nửa mp phải tìm; còn nếu nó không thỏa mãn thì nửa mp phải tìm là nửa mp không chứa điểm đặc biệt đó.
Các điểm thỏa mãn hệ ràng buộc của bài toán là các điểm thuộc miền giao của các nửa mp xác định các bất phương trình tương ứng, nó tạo nên một hình đa giác lồi có thể bị giới nội hay không bị giới nội; hay miền giao là rỗng ứng với trường hợp hệ ràng buộc không tương thích. Trường hợp miễn phương án X không rỗng ta thực hiện tiếp bước sau.
.
Năng lực cao nhất thu được là : 5.10 + 4.15+ 5.10 + 10.4 + 20.5 + 15.4 = 400
b. Một đội làm rau gồm 23 lao động nữ , chia làm 3 loại: loại A và B có 10 người ; loại C có 3 người. Đội đó cần bố trí 3 người đi hái rau, 8 người làm cỏ rau và 12 người trồng rau. Năng suất lao động của từng loại được cho trong bảng sau:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Trong thực tế ta thường hay gặp các tình huống là phải lựa chọn một trong số những quyết định quan trọng để đưa ra những phương án hay chiến lược tốt nhất trong sản xuất kinh doanh hay trong một trò chơi mà đối thủ là một kẻ thông minh và nguy hiểm…Khi đó ta cần lập mô hình toán học quy hoạch tuyến tính để có được phương án tối ưu cần thiết.
Trong đó phương pháp đơn hình được George Bemanrd Dantzig đưa ra năm 1947 cùng lúc với việc khai sinh ra quy hoạch tuyến tính, phương pháp này thực sự có hiệu quả để giải những bài toán quy hoạch tuyến tính cỡ lớn trong thực tế mà ta thường gặp, như để vận chuyển hàng hóa đầy đủ nhưng có tổng chi phí là nhỏ nhất – đây chính là bài toán vận tải. hay trong kinh doanh phải lập kế hoạch sản xuất đối với các nguyên liệu và sản phẩm để thu được tổng lợi nhuận là lớn nhất…
Kiến thức sau khi học quy hoạch tuyến tính rất cần thiết, đây là những kiến thức rất quan trọng để xây dựng một mô hình toán học cho bất kỳ bài toán phức tạp nào trong thực tế, chỉ cần xây dựng các thuật toán đã mô hình hóa ngôn ngữ nhờ việc lập trình trên máy tính ta có thể giải quy hoạch tuyến tính một cách dể dàng nhanh chóng và chính xác. Như vậy việc học quy hoạch tuyến tính rất quan trọng, nó đem lại những hiệu quả kinh tế rất lớn nếu biết lập các mô hình và tính toán đúng quy cách.
2. Đối tượng nghiên cứu và phương pháp nghiên cứu.
Quy hoạch tuyến tính là lĩnh vực nghiên cứu các bài toán tối ưu mà hàm mục tiêu là vấn đề được quan tâm nhất và các ràng buộc là các yêu cầu ,điều kiện của kế hoạch đặt ra, đều là hàm và các phương trình, bất phương trình tuyến tính. Các bước để nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điển hình là:
Xác định vấn đề cần giải quyết, thu thập dữ liệu .
Lập mô hình toán học thật chính xác.
Xây dựng các thuật toán để giải bài toán trên các lập trình máy tính.
Tính toán thử và điều chỉnh mô hình nếu cần .
Áp dụng để giải các bài toán thực tế .
CHƯƠNG 1:
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
A. LÝ THUYẾT
1. ĐỊNH NGHĨA
Bài toán quy hoạch tuyến tính (qhtt) tổng quát có dạng:
Tìm xj, j=1,2,…,n sao cho: f=(max) (1)
Với hệ ràng buộc: , i=1,2,…,m (2)
, j=1,2,…,n (3)
(1) được gọi là hàm mục tiêu, nó có thể là cực tiểu (min) hay cực đại (max).
(2) được gọi là các ràng buộc chung hay ràng buộc hàm, nó có thể có dạng bất đẳng thức (≤ hay ≥) hay có dạng đẳng thức (=).
(3) được gọi là các ràng buộc dấu (của biến), nó có thể không âm (≥0), không dương (≤0) hay tùy ý.
Như vậy, bài toán QHTT là bài toán có các biểu thức xác định hàm mục tiêu và các ràng buộc chung đều ở dạng tuyến tính.
Véctơ x=(x1, x2,…,xn)T được gọi là phương án (pa) hay lời giải chấp nhận được của bài toán QHTT nếu nó thỏa mãn hệ ràng buộc của bài toán.
Phương án x*=(được gọi là phương án tối ưu (patư) hay lời giải tối ưu, nghiệm tối ưu của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt nhất.
Tức là: f(x*)= là giá trị hàm mục tiêu tại phương án x=(x1,x2,…,xn)T bất kỳ. (Dấu ≤ ứng với bài toán cực tiểu. Dấu ≥ ứng với bài toán cực đại).
Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nếu có).
Hai bài toán QHTT được gọi là tương đương với nhau nếu chúng có chung tập hợp các phương án tối ưu.
Mệnh đề: (Quan hệ giữa bài toán cực đại và bài toán cực tiểu)
(Trong đó: X là tập hợp các phương án)
Tức là: nếu đổi dấu hàm mục tiêu và đổi loại hàm mục tiêu thì ta được bài toán tương đương. Vì lí do này mà khi nghiên cứu cách giải bài toán qhtt, người ta chỉ xét bài toán có loại hàm mục tiêu là cực tiểu (hay chỉ xét bài toán có loại hàm mục tiêu là cực đại)
2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 2 BIẾN
Bài toán có dạng: tìm x=(x1,x2)T sao cho f(x)=c1x1+c2x2 min (max)
Với hệ ràng buộc: ai1x1+ai2x2≥bi, i=1,2,…,m
Chú ý:
Ràng buộc chung có dạng: a≤b, ta đưa về dạng tương đương là: -a≥-b.
Ràng buộc chung có dạng: a = b thì tương đương với: a≥b và –a≥-b.
Còn các ràng buộc biến có thể xem là các trường hợp riêng của các ràng buộc chung.
Như vậy, hệ ràng buộc của bài toán QHTT có 2 biến luôn luôn có thể giả thiết là có dạng: ai1x1+ai2x2≥bi; i=l, 2..., m
2.1. Xác định miền phương án
Đưa các điểm (x1,x2) lên hệ trục tọa độ vuông góc. Ta xác định được các điểm thỏa mãn phương trình: ai1x1+ai2x2=b, hình thành nên một đường thẳng chia mặt phẳng tọa độ thành 2 nửa mặt phẳng (mp). Một nửa mp bao gồm các điểm (x1, x2) thỏa mãn bất phương trình: ai1x1+ai2x2≥bi, và nửa kia bao gồm các điểm (x1, x2) thỏa mãn bất phương trình: ai1x1+ai2x2≤bi.
Trong thực hành, để xác định nửa mp nào ứng với bất phương trình: ai1x1+ai2x2≥bi. Ta thường lấy một điểm đặc biệt như (0,0); (0,1); (1,0);… thay vào bất phương tình, nếu nó thỏa mãn thì nửa mp chứa điểm đặc biệt đó là nửa mp phải tìm; còn nếu nó không thỏa mãn thì nửa mp phải tìm là nửa mp không chứa điểm đặc biệt đó.
Các điểm thỏa mãn hệ ràng buộc của bài toán là các điểm thuộc miền giao của các nửa mp xác định các bất phương trình tương ứng, nó tạo nên một hình đa giác lồi có thể bị giới nội hay không bị giới nội; hay miền giao là rỗng ứng với trường hợp hệ ràng buộc không tương thích. Trường hợp miễn phương án X không rỗng ta thực hiện tiếp bước sau.
.
Năng lực cao nhất thu được là : 5.10 + 4.15+ 5.10 + 10.4 + 20.5 + 15.4 = 400
b. Một đội làm rau gồm 23 lao động nữ , chia làm 3 loại: loại A và B có 10 người ; loại C có 3 người. Đội đó cần bố trí 3 người đi hái rau, 8 người làm cỏ rau và 12 người trồng rau. Năng suất lao động của từng loại được cho trong bảng sau:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links