Bài giảng Tin học ứng dụng: Chương 6 - Lê Hữu Hùng

Chia sẻ: Phong Phong | Ngày: | Loại File: PPTX | Số trang:33

Thêm vào BST

Báo xấu

62
lượt xem 3
download

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

Bài giảng cung cấp cho người học các kiến thức: Một số ví dụ về bài toán QHTT, các dạng bài toán qui hoạch tuyến tính, bài toán vận tải, lập mô hình toán học. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Tin học ứng dụng: Chương 6 - Lê Hữu Hùng

Sự cạnh tranh trong hoạt động sản xuất kinh doanh luôn đòi hỏi các nhà quản lý doanh nghiệp phải thường xuyên lựa chọn phương án để đưa ra các quyết định nhanh chóng, chính xác và kịp thời với những ràng buộc và hạn chế về các điều Chương kiện liên quan tới tiềm năng
Trong môn hoc ̣ Toán kinh tế viêc ̣ giai ̉ bài toán QHTT thường được thực hiên bặ ̣ ̀ng thuât toán đơn hình. Trong phần mềm Excel bài toán QHTT được ̉ giai nhanh cho ̣ ̀i thêm là Solver. ́ng qua công cu ca 6.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTTT 1. Bài toán lập kế hoạch sản xuất: ̣ ́ nghiêp d Môt xi ̣ ự đinh san xuâ ̣ ̉ ̣ ̉ ̉ ́t hai loai san phâm là S1 và S2 từ vật liệu V1 và V2. Số liệu được cho ở bảng sau:
Mô hì nh toá n học. Goi x1, x2 lâ ̣ ̀n lượt là số đơn ̣ ̉ ̉ vi san phâm S1, S2 câ ̉ ̀n san xuâ ́t. ̉ Tông thu nhâp cua xi ̣ ̉ ́ nghiêp (̣ cần làm cực đaị ) sẽ là f = 50x1 + 30x2 (ngàn đồng). Vây bạ ̣ ̀i toán đăt ra đ ược phát biêu tha ̉ ̀nh: Tìm các biến số x1 và x2 sao cho f = 50x1 + 30x2 max, vớ i cá c điề u kiên ̣ 4x1 + 3x2 1.200, 5x1 + 2x2 1.080, (1.1) x1 0, x2 0.
2. Bài toán xác định khẩu phần thức ăn Khẩu phần thức ăn/ 1 bữa ăn của một xí nghiêp ̣ chăn nuôi như sau: ̉ xí nghiêp Hoi ̣ cần mua bao nhiêu kg T1, T2 cho mỗi bữa ăn, sao cho vừa đam bao tô ̉ ̉ ́t dinh dưỡng cho bữa ăn cua ̉ gia súc, vừa đê ̉ tông ̉ số tiền chi mua thức ăn là nho nhâ ̉ ́t?
Mô hì nh toá n hoc. ̣ Goi x1, x2 lâ ̣ ̀n lượt là số kg thức ăn T1, T2 cần mua cho mỗi bữa ăn. Số tiền chi mua thức ăn (cần làm cực tiêu ̉ ) bằng f = 20x1 + 15x2 (ngàn đồng). ̣ Vây ba ̀i toán nêu trên được phát biêu tha ̉ ̀nh: Tìm các biến số x1 và x2 sao cho: f = 20x1 + 15x2 min, vớ i cá c điề u kiên ̣ 3x1+ x2 60, x1 + x2 40, (1.2) x1 + 2x2 60, x1 0, x2 0.
3. Bài toán vận tải ̣ ̉ Cần vân chuyên xi măng t ừ 3 kho K1, K2, K3 tới 4 công trường xây dựng T1, T2, T3, T4. Số liêu cho ̣ ở bang sau: ̉ ̣ ̣ ̉ Vấn đề là tìm kế hoach vân chuyên xi măng t ừ các kho tới các công trường sao cho moi ̣ kho phát hết lượng xi măng có, moi công tr ̣ ường nhân ̣ ̉ ượng xi măng cần và tông chi phi đu l ̉ ̣ ̉ ́ vân chuyên ̉ là nho nhâ ́t?
Mô hì nh toá n hoc. ̣ Goi xij la ̣ ̀ lượng xi măng cần ̣ vân chuyên t ̉ ừ kho Ki (i = 1, 2, 3) tới công trường Tj (j = 1, 2, 3, 4). ̉ Tông chi phi ̣ ̉ ́ vân chuyên (cần làm cực tiêu) bă ̉ ̀ng: f = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 25x22 + 30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34. ̣ Vây bài toán nêu trên được phát biêu tha ̉ ̀nh:
Tìm các biến số xij sao cho: f min, vớ i cá c điề u kiên ̣ x11 + x12 + x13 + x14 = 170, x21 + x22 + x23 + x24 = 200, x31 + x32 + x33 + x34 = 180, x11 + x21 + x31 = 130, (1.3) x12 + x22 + x32 = 160, x13 + x23 + x33 = 120, x14 + x24 + x34 = 140, xij 0, i = 1, 2, 3; j = 1, 2, 3, 4.
6.2. CÁ C DANG BÀI TOÁN QHTTT ̣ ̣ Qui hoach tuyê ́n tính là bài toán tìm cực tiêu ( ̉ hay cực đaị ) cua ̉ môt ̣ hàm tuyến tính thoa ̉ mãn các phương trình và/hoặc bất phương trình tuyến tính. 1. Bài toán tổng quát ̣ Bài toán nan ̀y có dang: Ti ̀m các biến số x1, x2,..., xn sao cho: f (x ) = c j x j min (hay max) (1.4) j =1 ̉ Thoa ma ̣ ̃n các điều kiên: n �� aij xj �� = bi , i=1,2,...,m, �� (1.5) j=1 �� xj ��0, j=1,2,...,n1 n. (1.6) ��
 f goi la ̣ ̀ hàm muc tiêu, ̣ ̣  (1.5) là các ràng buôc chi ̣ ́nh (các PT và/hoăc bpt tuyến tính). ̣ về biến (có thê ̉ không  (1.6) là các ràng buôc âm, không dương hay tùy ý). Điêm ̉ x = (x1, x2, ..., xn) Rn thoa ̉ mãn (1.5), ̣ ̀ phương á n cua ba (1.6) goi la ̉ ̀ i toá n. Tâp h ̣ ợp ̣ là D, goi tất ca ̉ các phương án, ký hiêu ̣ là miề n rà ng buôc̣ hay miề n chấ p nhân đ ̣ ược. Môt ̣ phương án thoa ̉ mãn (1.4) goi ̣ là môt ̣ phương á n tố i ưu hay lờ i giaỉ cua ̉ bài toán đã cho.
2. Bài toán dạng chính tắc (ràng buộc chính chỉ là các đẳng thức và mọi biến đều không âm). ̣ mô hình bài toán vân Ví du: ̣ tai ̉ nêu ở (1.1) có ̣ dang chi ́nh tắc.
3. Bài toán dạng chuẩn tắc ̣ (ràng buôc chi ̉ ̀m các bất đăng th ́nh chi gô ̉ ức đối với bài toán min hoăc ̣ đối với bài toán ̣ max, và moi biê ́n đều không âm). ̣ mô hình bài toán xác đinh Ví du: ̣ khâu ̉ phần thức ăn hay mô hình bài toán lâp ̣ kế hoach ̣ san ̉ xuất đã xét ở (1.1) có dang chuân tă ̣ ̉ ́c.
Giải quy hoạch tuyến tính trên EXCEL Để giải các bài toán QHTT, phần mềm Excel cung cấp cho ta một công cụ khá hữu ích là Solver trong Menu Tools của Excel. Các bài toán QHTT dạng chính tắc và dạng chuẩn chỉ là trường hợp riêng của bài toán QHTT dạng tổng quát. Vì thế ở đây ta sẽ xem xét cách giải quyết bài toán QHTT dạng tổng quát. Ví dụ: Xét bài toán QHTT sau: f (x) = x1 + 4x2 + x3 min Các ràng buộc: 5x1 + x2 – 2x3 12 x1 + 2x2 x3 2 x1 + 4x2 – 2x3 1 2x1 + 3x2 + 4x3 ≥ 20
Các bước thực hiện giải bài toán: Bước 1: Nhập dữ liệu bài toán vào bảng tính dưới dạng sau: Phương án ban đầu X = (1, 1, 1) có thể không chấp nhận được. Bước 2: Tính giá trị hàm mục tiêu tại ô E3 bằng công thức: E3 =SUMPRODUCT($B$2:$D$2;B3:D3) Copy công thức từ ô E3 sang dãy các ô E4:E7 để tính giá trị vế trái của 4 ràng buộc của bài toán.
Bước 3: Dùng lệnh Tools | Solver, xuất hiện hộp thoại Solver Parameters: Mục Set Target Cell: chọn ô đích (chứa giá trị hàm mục tiêu), trong ví dụ chọn ô E3. Mục Equal To: chọn Max nếu cực đại hàm mục tiêu; chọn Min nếu cực tiểu hàm mục tiêu; chọn Value of và nhập giá trị nếu muốn ô đích bằng 1 giá trị nhất định, trong ví dụ chọn Min.
Mục By Changing Cells: chọn các ô chứa các biến của bài toán, trong ví dụ chọn khối ô B3:D2. Nháy nút Add để nhập tất cả các ràng buộc vào khung Subject to the Contraints. Sau khi nhập xong các ràng buộc , nháy nút options, hiện hộp thoại Solver Options, đánh dấu kiểm vào mục Assume Linear Model (khẳng định mô hình của ta là tuyến tính.)
Bước 4: Trong hộp thoại Solver Parameters, nháy vào nút Solver để bắt đầu giải bài toán. Giải xong bài toán xuất hiện hộp thoại Solver Results. Chọn mục Keep Solver Solution (giữ lại lời giải), nháy OK, kết quả giải bài toán nằm ở các ô B2:D2. Kết quả ta có phương án tối ưu là x* = (0,5; 0; 4,75), và trị tối ưu là fmin = 5,25.
6.3. BÀI TOÁN VẬN TẢI 1. Nội dung bài toán: Gia s ̉ ử cần vân chuyên môt ̣ ̉ ̣ ̣ loai ha ̀ng thuần nhất (vât t ̣ ư, lương thực, ...) từ m địa điểm cung cấp (điêm pha ̉ ́t) A1, A2, ..., Am đến n đia điêm tiêu thu ( ̣ ̉ ̣ điêm thu ̉ ) B1, B2, ..., Bn. Biết rằng : Số lượng hàng có ở Ai là ai (i = 1,..., m), Số lượng hàng cần ở Bj là bj (j = 1,..., n), ̣ ̉ Chi phí vân chuyên môt đ ̣ ơn vi ha ̣ ̀ng từ Ai đến Bj là cij (i = 1,...,m; j = 1,...,n). Vấ n đề đăt ̣ ra: Lâp ̣ kế hoach ̣ vân ̣ chuyên ̉ hàng từ các điểm phát đến các đia điêm thu đê tông chi ̣ ̉ ̉ ̉ ̣ phí vân chuyên be ̉ ́ nhất và thoa ma ̉ ̃n nhu cầu thu phát.
̣ Đây là môt trong nh ững bài toán điên hi ̉ ̀nh và có nhiều ứng dung ̣ nhất cua ̉ QHTT. Bài toán này không có gì phức tap nê ̣ ̣ ́u mang l ưới giao thông tương đối đơn gian ̉ và số đia ̣ điêm ̉ cung ̣ cấp, tiêu thu không nhiều lắm. Tuy nhiên với những mạng lưới đường giao thông phức tạp thì bằng kinh nghiệm và trực giác khó có thể tìm ra được phương án tối ưu. Khi ấy, cần sử dụng các phương pháp, dựa vào tính chất đặc thù của bài toán để tìm phương án tối ưu.
Mô hình toán học của bài toán: ̣ xij là số lượng hàng cần vân Goi ̉ từ Ai ̣ chuyên đến Bj. Ta có: m n ��c x i =1 j =1 ij ij : To� ng chi ph�va� n chuye� n, n xij : So� l�� ng ha� ng ch�� i t�� Ai, j =1 m xij : So� l�� ng ha� ng ch�� t�� i Bj , i =1 Mô hình toán học của bài toán là: