bài thu hoạch môn tối ưu hóa2

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.26 MB, 37 trang )

Trang 1<div class="page_container" data-page="1">

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC SƯ PHẠM KĨ THUẬT TP.HCMKHOA KINH TẾ

BÀI THU HOẠCH MÔN: TỐI ƯU HĨA

MÃ MƠN HỌC: MAOP230706 (Thứ hai tiết 4-6)NHĨM THỰC HIỆN: 21

GIẢNG VIÊN HƯỚNG DẪN: Ngô Hữu Tâm

Tháng 5, 2022

</div>Trang 2<div class="page_container" data-page="2">

Nhận xét của giảng viên:

</div>Trang 3<div class="page_container" data-page="3">

BÀI TẬP THU HOẠCH Mơn học: TỐI ƯU HĨA

Một cơng ty cần thực hiện một dự án lắp đặt hệ thống nhà xưởng bao gồm các công việc với các yêu cầu đặt ra cho trong bảng sau đây. Trong đó, a là thời gian ước tính hồn thành cơng việc một cách lạc quan, m là thời gian ước tính hồn thành cơng việc trong điều kiện bình thường, b là thời gian ước tính hồn thành cơng việc một cách bi quan.

Công việc Thời gian cần (ngày) Thời gian tiến hành Sau E,F,G,H hoàn thành Sau E,F hoàn thành Sau E,F hoàn thành Sau B,D,H hoàn thành Sau J,K,M hồn thành Sau B,D,H hồn thành

a) Hãy tính kỳ vọng và phương sai cho các đại lượng ngẫu nhiên biểu thị thời gian hồn thành cơng việc. Khi tính kỳ vọng làm tròn số phần thập phân như sau:

</div>Trang 4<div class="page_container" data-page="4">

Làm tròn thành0,1250,250,3750,50.6250,750,8751

b) Lập sơ đồ PERT, xác định đường găng, ước tính thời gian trung bình để hồn thành dự án. Tính xác suất để tồn bộ dự án được hồn thành với thời gian khơng quá 33 ngày (bỏ qua sai số do việclàm tròn số). Lập bảng chỉ tiêu thời gian cho các công việc. Dựng sơ đồ PERT ngang với điều

kiện công việc H và I không thể thực hiện trong cùng một thời điểm. Dựng sơ đồ PERT ngang với điều kiện nguồn lực của công ty không thể thực hiện 4 công việc cùng một thời điểm. c) Giả sử chi phí để rút ngắn thời gian hồn thành mỗi công việc theo quy luật ( là hệ số tỷ lệ

được cho trong bảng, C là chi phí rút ngắn ngày thứ k ứng với mỗi cơng việc và có đơn vị tínhk là triệu đồng)

Hãy rút ngắn thời gian trung bình hồn thành dự án khơng quá 25 ngày với chi phí thấp nhất và tính chi phí tăng thêm đó. Lập bảng chỉ tiêu thời gian cho các công việc và dựng sơ đồ PERT ngang đối với kế hoạch sau khi rút ngắn thời gian trung bình hồn thành dự án khơng q 25 ngày.

d) Dự án đang thực hiện theo kế hoạch đang lập ở (c) thì vào đầu ngày 6 có một sự cố xảy ra làm tồn bộ cơng việc của công ty phải ngưng thực hiện 01 ngày . Hy điều chỉnh kế hoạch sao cho thời gian trung bình hồn thành dự án khơng q 25 ngày với chi phí thấp nhất. e) Trình bày chi tiết mỗi kế hoạch ở (c) và (d) trên 1 trang giấy A3 biết: Dự án bắt đầu ngày sáng thứ hai ngày 04/07/2022, mỗi tuần làm việc 5 ngày (thứ hai đến thứ sáu), sáng từ 7 giờ đến 11 giờ và chiều từ 13 giờ đến 17 giờ.(phần này giáo viên sẽ hướng dẫn chi tiết)

Yêu cầu tiến độ thực hiện phần I

Từ lúc nhận đề đến 12/5/2022 Làm xong câu (a), (b) và báo cáo kết quả với giáo viên hướng dẫn. (chưa đánh máy)

Từ 12/5/2022đến 14/5/2022 Làm xong câu (c) và báo cáo kết quả với giáo viên hướng dẫn. (chưa đánh máy)

Từ 14/5/2022đến 16/5/2022 Làm xong câu (d) và báo cáo kết quả với giáo viên hướng dẫn. (chưa đánh máy)

Từ 16/5/2022đến 19/5/2022 Kiểm tra một lần nữa kết quả câu (c), (d) chính xác & giáo viên hướng dẫn chi tiết làm câu (e).

Từ 19/5/2022đến 21/5/2022 Đánh máy, vẽ hình, trình bày đầy đủ bài thu hoạch. Kiểm tra và sửa (làm lại) những chỗ cịn sai sót (nếu có).

Từ 21/5/2022đến 23/5/2022là các ngày dự trữ & nộp bài.

Cả nhóm kiểm tra tồn bộ kết quả chính xác và trình bày đầy đủ rồi thì mới nộp bài cho giáo viên.

</div>Trang 5<div class="page_container" data-page="5">

Phần II (3,5 điểm)

Tìm hiểu cách sử dụng một trong các phần mềm Excel, Maple, Matlab,…để giải bài tốn quy hoạch tuyến tính, bài tốn vận tải. Trình bày cách giải, nhập số liệu, giải và in kết quả đối với các bài toán (đối với bài 3, bài 4 phải lập mơ hình tốn học) sau:

Bài 1

Giải bài toán QHTT f(x) = 4x1+8x +5x23 max (2)

(3) tùy ý, ,

Bài 2

Một cơng ty cần sản xuất 45 đơn vị sản phẩm loại A , 85 đơn vị sản phẩm loại A 120 đơn vị sản12, phẩm A trong vịng 3 tháng. Cơng ty có 4 xí nghiệp B , B , B3 123, B4 với khả năng sản xuất (số đơn vị sản phẩm loại A hay sản phẩm loại A1 2 haysản phẩm loại A ) trong 3 tháng lần lượt là 90, 70, 60, 503

đơn vị sản phẩm. Lợi nhuận (đơn vị tính 1.000.000 đồng/1 sản phẩm và tính bằng giá bán trừ chiphí cho mỗi sản phẩm) của mỗi sản phẩm khi sản xuất tại các xí nghiệp được cho trong bảng sau

Vì chiến lược phát triển chung của cơng ty, nên xí nghiệp B phải sản xuất đủ 60 đơn vị sản phẩm.3

Hỏi phải phân phối cho các xí nghiệp sản xuất số lượng các sản phẩm như thế nào để tổng lợi nhuận

Bài 3

The National Credit Union has $250,000 available to invest in a 12-month commitment. The money can be placed in Treasury notes yielding an 8% return or in municipal bonds at an average rate of return of 9%. Credit union regulations require diversification to the extent that at least 50% of the investment be placed in Treasury notes. Because of defaults in such municipalities as Cleveland and New York, it is decided that no more than 40% of the investment be placed in bonds. How much should the National Credit Union invest in each security so as to maximize its return on investment?

Bài 4

Wilson Creek Farm has 200 acres of land available for planting. The owner is considering planting three crops: corn, soybeans, and wheat. The production yield, water requirements, and labor requirements for a salable crop are given here. The owner expects to have only 35,000 gallons of water available per week to use for the crops, and during the growing season he will only have 8000 person-hours of labor available. The expected profit per bushel of each crop is$1.50 for corn, $1.90 for soybeans, and $3.60 for wheat. The

</div>Trang 6<div class="page_container" data-page="6">

owner can use any mix of crops (i.e., he can plant the samecrop on all 200 acres or he can plant all three crops in different proportions).

a) Formulate the problem as a linear program to find the profit-maximizing planting strategy. b) Solve the problem using a computer.

Phần III (1,5 điểm)DESIGNING YOUR LIFE

How to Build a Well-Lived, Joyful Life?

</div>Trang 7<div class="page_container" data-page="7">

Designing/Planning/Programming YOUR LIFE

CUỘC ĐỜI CỦA BẠN như thế nào làTỐI ƯU?

3.1) CUỘC ĐỜI CỦA BẠN như thế nào làTỐI ƯU?

</div>Trang 8<div class="page_container" data-page="8">

Nếu bạn có được một đời Bình an-Hạnh phúc-Cân bằng-Viên mãn là tối ưu chưa? Hay bạn cần phải Giàu sang-Thành đạt có đầy đủ Của cải vật chất và Địa vị xã hội thì mới tối ưu? Hay bạn chỉ cần một cuộc sống đạt ở mức cơ bản về vật chất-không mất nhiều thời gian công sức học tập làm việc phục vụ cho nhu cầu vật chất- dành thời gian và nguồn lực đời người để tạo dựng một đời sống thật khỏe mạnh về thể chất, phong phú về tinh thần, thăng hoa tâm thức, …? Hãy suy ngẫm về tính tương đối&tính tuyệt đối của hệ thống các giá trị trong cộng đồng, xã hội, đời sống, nhân sinh,…

3.2) Bạn có những thiết kế/quy hoạch dài hạn, trung hạn, ngắn hạn như thế nào và ước tính cách thực hiện ra sao để được một cuộc đời tối ưu hoặc gầntối ưu?

(khi quy hoạch/thiết kế cần chú ý đến các giới hạn về mặt sinh học của chính bản thân bạn, các ràng buộc mối quan hệ của bạn với gia đình, cộng đồng, các điều kiện tự nhiên-xã hội,…..)

Hãy nêu trả lời cơ bản ngắn gọn các câu hỏi trên trong một hoặc vài trang giấy. Mỗi người có điều kiện, hồn cảnh, trải nghiệm, nhân sinh quan, thế giới quan,… khác nhau có thể trả lời khác nhau nhưng phù hợp cho cùng một câu hỏi (nếu người trả lời yêu cầu giữ bí mật các thơng tin riêng tư có trong câu trả lời thì giáo viên sẽ tuyệt đối thực hiện).

*** Các bạn SINH VIÊN thân mến,

Đây là câu hỏi mở về vấn đề quá rộng và còn rất nhiều bất định nên khơng thể có câu trả lời xác định. Trong câu hỏi ẩn chứa nhiều điều không tường minh. Tuy nhiên, giáo viên mong muốn hỏi để học từ các bạn sinh viên và để các bạn sinh viên thực sự áp dụng những kiến thức và kỹ năng đã học

được vào trong công việc và cuộc sống để thành công và hạnh phúc hơn. Khi trả lời các câu hỏi này sẽ giúp người trả lời hiểu rõ hơn bản chất và ý nghĩa cuộc sống, có các hoạch định/thiết kế và thực hiện các kế hoạch tương lai tốt hơn nhờ đó tăng khả năng thành cơng, thích ứng tốt hơn và vững vàng hơn với các khó khăn và biến động trong đời sống xã hội, từ đó giúp bạn có được một đời sốngsáng tạo-phong phú-biến đổi tiến triển-đầy thú vị- cân bằng-viên mãn.

Giáo viên tin và ủng hộ quan điểm: “Người học thật nhiều kiến thức mà không biết ứng dụng gì cho

cuộc sống được hạnh phúc thì giống như con lừa thồ sách” Chúc Bạn và Gia đình KHỎE MẠNH-BÌNH AN-HẠNH PHÚC!

Ngơ Hữu Tâm

……… Có thể tìm trên Internet (nên làm theo cách này) hay tham khảo các tài liệu sau:

[1] Nguyễn Đình Tê EXCELL XP quyển 2, nhà xuất bản Lao động Xã hội – 2007.,

[2] Trần Trí Dũng, EXCELL Solver cho kỹ sư, NXB Khoa học Kỹ thuật – 2005.

[3]Phạm Minh Hồng, MAPLE &các bài tốn ứng dụng, NXB Khoa học Kỹ thuật–2005.

[4] Phạm Trí Cao, Tối Ưu hóa Ứng dụng, NXB Lao động Xã hội -2014.

Một số yêu cầu đối với bài thu hoạch:

</div>Trang 9<div class="page_container" data-page="9">

Bài làm được đánh máy trên giấy A , các hình vẽ thì vẽ bằng tay hay vẽ bằng máy cũng được4 miễn sao đạt yêu cầu rõ ràng chính xác. (kỹ năng vẽ bằng máy hiện chưa cần nên vẽ tay thì tốt hơn) Ghi đầy đủ họ tên, mã số sinh viên các thành viên trong nhóm và ít nhất một số điện thoại để

liên lạc khi cần. Tự nhận xét và đánh giá nhóm của các bạn.

Thời gian nộp bài: Từ 21/5/2022 đến 23/5/2022. Nộp lại đề bài này chung với bài làm– Đề

bài ghép chung ngay trước phần bài làm không nhận bài nộp mà khơng có đề().

Mục tiêu đánh giá

Phần I Sử dụng sơ đồ PERT-CPM để: Lập kế hoạch cho dự án có thời gian ngẫu nhiên và biết cách sử dụng

thời gian dữ trữ các công việc không găng để điều chỉnh tối ưu kế hoạch sao cho thuận tiện trong việc thực hiện và quản lý (câu a&b). Điều chỉnh tối ưu hóa về mặt tài chính với quy định thời gian cho trước (câu c). Khắc phục sự cố dự án sao cho tối ưu hóa về mặt tài chính với thời gian quy định cho trước (câu d). Biết cách lập kế hoạch ngắn gọn chi tiết triển khai thực hiện kế hoạch dự án với thời gian thực (câu e).

Phần II Nhận dạng được bài toán thực tế dưới dạng ngôn ngữ thông thường (tiếng Việt hoặc tiếng Anh), lập

được mơ hình tốn học, sử dụng máy tính và phần mềm thích hợp để giải tìm lời giải tối ưu rồi suy ra kết quả bài toán thực tế.

Phần III Hoạch định cuộc đời bạn phù hợp nhất/tốt nhất với các điều kiện/ràng buộc của chính bạn, luôn

vững vàng và an lạc trước vạn biến/vô thường của cuộc đời.

Phát triển kỹ năng phối hợp làm việc nhóm, tìm kiếm tài liệu, trình bày, tranh luận & phản biện,…

</div>Trang 10<div class="page_container" data-page="10">

Đường găng: (1,A, 2, D, 4, E, 5, K, 8, N, 9.) Thời gian trung bình hồn thành dự án: E(T)=29,375

</div>Trang 11<div class="page_container" data-page="11">

Ta thấy thời gian dự trữ của I là 13.75 ngày nên ta dời I thêm 2 ngày. Ta có sơ đồ PERT ngang với điều kiện H và I không thể thực hiện trong cùng một thời điểm như sau:

Vì cơng ty không thể làm 4 việc cùng 1 lúc nên - Dời O thêm 13 ngày

- Dời G thêm 0.75 ngày

Ta được như sơ đồ PERT ngang với điều kiện nguồn lực công ty không thể thực hiện 4 công việc cùng một thời điểm như sau:

</div>Trang 12<div class="page_container" data-page="12">

c) Chi phí rút ngắn ngày thứ k với cơng việc găng C=5αk-4 Cơng việc Chi phí ngày

Cần phải rút 5 ngày để thời gian hồn thành trung bình dự án khơng q 25 ngày Để chi phí thấp nhất ta sẽ rút E,A,D,N,K mỗi việc 1 ngày:

</div>Trang 13<div class="page_container" data-page="13">

Chi phí tăng thêm là : 21+21+16+26+21=105 (triệu đồng)

</div>Trang 16<div class="page_container" data-page="16">

O(6,9) 8,375 10,375 22,375 24,375 17,25 8

d) Do đầu ngày 6 có một sự cố xảy ra nên các cơng việc D, F, I bị trì hỗn 1 ngày nên thời gian hồn thành tăng thêm 1 ngày. Để dự án không vượt quá 25 ngày với chi phí thấp nhất thì ta rút E đi 1 ngày.

</div>Trang 17<div class="page_container" data-page="17">

Bước 1: Vào File => Options. Tại hộp thoại Excel Options chọn Add-ins, tại dòng Manage chọn Go…

Hộp thoại Add-ins xuất hiện:

</div>Trang 18<div class="page_container" data-page="18">

Lúc này, nháy vào hộp thoại Data ta thấy tại Analysis xuất hiện lệnh Solver.

Bước 2: Nhập vào Excel cám hàm mục tiêu, các giá trị ràng buộc

Hàm mục tiêu: f(x)=4x1+8x2+5x3→max. Cơng thức tính hàm mục tiêu cho bài tốn ta sử dụng hàm SUMPRODUCT: =SUMPRODUCT(C4:E4,C3:E3)

Cơng thức ràng buộc thứ nhất: =SUMPRODUCT(C5:E5,$C$3:$E$3) Công thức ràng buộc thứ hai: =SUMPRODUCT(C6:E6,$C$3:$E$3) Công thức ràng buộc thứ ba: =SUMPRODUCT(C7:E7,$C$3:$E$3)

Nháy chọn Solver Add-ins

và nháy Oke

</div>Trang 19<div class="page_container" data-page="19">

Công thức ràng buộc thứ tư: =SUMPRODUCT(C8:E8,$C$3:$E$3)

Bước 3: Tiến hành giải bài tốn

Vào Data, chọn Solver lúc này màn hình xuất hiện hộp thoại Solver PramateresSet Objective: Ô chứa hàm mục tiêu

To: là giá trị tối ưu của hàm mục tiêuBy changing variable cells: Địa chỉ

của các ô chứa thành phần phương án nghiệm

Subject to the Constraints: Các ràng

buộc của bài tốn

Set Objective: Ơ chứa hàm mục tiêu là

ơ F4

Trong bài toán này hàm mục tiêu hướng về Min do đó trong hộp thoại

Solver Pramateres, ở hàng To ta chọn Max.

By changing variable cells: Nhập

Subject to the Constraints: Các ràng

buộc của bài toán

</div>Trang 20<div class="page_container" data-page="20">

Bấm nút Add để nhập ràng buộc thứ nhất, trên màng hình xuất hiện hộp thoại Add Constraint như sau.

Với ràng buộc 2X + 4X – X ≤ -2 nhập theo thứ tự như sau: $F$5 <= =$G$51 23

Sau đó bấm Add để nhập tiếp các ràng buộc còn lại Với ràng buộc 2X1+4X2+X3 ≤ 7 ta nhập $F$6 <= =$G$6 Với ràng buộc X + X + X ≤ 2 ta nhập $F$7 <= =$G$71 23 Với ràng buộc -3X + X + 2X ≤ 10 ta nhập $F$8 <= =$G$8123 Với Ràng buộc ẩn ta nhập $D$3:$E$3 <= 0

Sau khi nhập xong các ràng buộc nháy Ok để quay lại hộp thoại Solver Parameteres, lúc này tại ơ Subject to the Constraints ta hồn thành được bản điều kiện như hình bên.

</div>Trang 21<div class="page_container" data-page="21">

Tuy nhiên muốn thêm ràng buộc ta chọn Add, hiệu chỉnh ràng buộc ta chọn Change, xóa ràng buộc ta chọn ràng buộc từ danh sách

Subject to the Constraints và nhấn Delete

phương pháp giải ta chọn Simplex LP là giải theo phương pháp đơn hình

Sau khi kết thúc bước nhập dữ liệu bấm Solve

để chương trình bắt đầu chạy.

Ta thấy sau khi nhấp vào Solve, hộp

thoại Solver Results xuất hiện:Keep Solver Solution: Giữ lại lời bài

Restore Original Values: Phục hồi lại

giá trị ban đầu

Save Scenario…: Lưu kết quả vừa

tìm được thành một tình huống có thể xem lại sau này

Bài toán trên ta chọn Keep SolverSolution và nháy Ok, ta thu được kết

quả như sau:

</div>Trang 22<div class="page_container" data-page="22">

Từ bảng kết quả trên ta tính đc X =-1, X =0, X =0 và f123max=-4

Câu 2: Đây là bài tốn khơng cân bằng thu phát (Tổng thu lớn hơn tổng phát) với lượng phát ít hơn

thu một lượng là (90+70+60+50) – ( 45+85+120) = 20 đơn vị sản phẩm. Ta lập một trạm sản xuất giả A4 với lượng phát cần là α = 20 đơn vị sản phẩm. Để trạm B thu đủ hàng thì lượng hàng giả trạm A434 khơng được phát vào trạm B3 nên ô và (4,3) là ô cấm, vì cần tổng lợi nhuận cao nhất nên đây là bài tốn f => Max do đó cước phí ô (4,3) là -M (số dương lớn tùy ý).

Gọi X là lượng sản phẩm vận chuyển từ nhà máy i đến điểm tiêu thụ j nên X ≥ 0, i=(1,4), j=(1,4)ijij Hàm mục tiêu:

</div>Trang 23<div class="page_container" data-page="23">

Tổ chức dữ liệu trên bảng tính như sau:

Khởi tạo giá trị ban đầu của các biến X = 0; với i=(1,4); j=(1,4)ij

Sau đó ta lập cơng thức tính hàm mục tiêu tại ô C15 = SUMPRODUCT(C9:F12,C3:F6)

Số lượng sản phẩm A , A , A , A sản xuất tiêu thụ ở các cửa hàng B , B , B , B đúng bằng lượng sản12341234 phẩm yêu cầu

X11 + X + X + X = 45121314 X21 + X + X + X = 852223 24

</div>Trang 24<div class="page_container" data-page="24">

Tiến hành giải bài toán:

Vào Data chọn Solver để mở hộp thoại Solver ParametersSet Objective: $C$15

To: Min

By Changing Variable Cells: $C$9:$F$12