Chương 1: Phương pháp Sơ đồ mạng lưới (PERT). - Chương 2: Lý thuyết phục vụ Hệ thống công cộng. - Chương 3: Mô hình điều khiển dự trữ. Các chương trình bày dưới dạng sơ lược và cơ bản nhất, do lượng kiến thức, việc áp dụng các phần mềm tính toán còn hạn chế, rất mong nhận được sự hướng dẫn thêm của Cô.
Trân trọng cảm ơn sự quan tâm và chỉ dẫn của Cô trong thời gian vừa qua! Thực hiện: Nguyễn Trung Hiếu – MSSV: 070453M – Lớp: 07TN1D Trang 5 Một số mô hình Toán ứng dụng – GVHD: ThS. Trần Thị Thùy Nƣơng MỤC LỤC CHƢƠNG 1: PHƢƠNG PHÁP SƠ ĐỒ MẠNG LƢỚI (PERT). Dữ kiện và các yếu tố. Sơ đồ phác thảo và sơ đồ chính thức.
CÁC CHỈ TIÊU THỜI GIAN TRÊN SƠ ĐỒ MẠNG LƢỚI. Các chỉ tiêu thời gian cho các sự kiện (đỉnh) và đường găng. Các chỉ tiêu thời gian cho các cung (công việc). SƠ ĐỒ GANTL VÀ SƠ ĐỒ PERT NGANG .16 CHƢƠNG 2: LÝ THUYẾT PHỤC VỤ CÔNG CỘNG.
MÔ HÌNH BÀI TOÁN PHỤC VỤ CÔNG CỘNG. Bài toán lý thuyết phục vụ công cộng. Hệ thống phục vụ công cộng và các yếu tố. Tính chất của dòng yêu cầu Poisson và Poisson dừng.
Kiểm định giả thiết về phân phối Poisson. TRẠNG THÁI HỆ THỐNG, QUÁ TRÌNH CHUYỂN TRẠNG THÁI. Phương pháp phân tích. Phân loại hệ thống.
Trạng thái hệ thống và quá trình chuyển trạng thái. Sơ đồ trạng thái và hệ phương trình trạng thái. Quá trình hủy và sinh – lời giả của hệ phương trình trạng thái. MỘT SỐ HỆ THỐNG PHỤC VỤ CÔNG CỘNG POISSON DỪNG.
Hệ thống từ chối với việc phân chia năng suất kênh. Hệ thống phục vụ công cộng từ chối cổ điển (Eclang). Hệ thống phục vụ công cộng chờ thuần nhất. Hệ thống chờ với độ dài hàng chờ hạn chế và thời gian chờ không hạn chế.
Hệ thống phục vụ phân đoạn. MỘT SỐ HỆ THỐNG PHỤC VỤ CÔNG CỘNG POISSON KHÔNG DỪNG. Hệ thống phục vụ công cộng với dòng vào có tính chu kỳ. Hệ thống phục vụ công cộng với dòng vào phụ thuộc chất lượng phục vụ .34 CHƢƠNG 3: MÔ HÌNH ĐIỀU KHIỂN DỰ TRỮ.
BÀI TOÁN, CÁC KHÁI NIỆM VÀ CÁCH TIẾP CẬN. Bài toán dự trữ .36 Thực hiện: Nguyễn Trung Hiếu – MSSV: 070453M – Lớp: 07TN1D Trang 6 Một số mô hình Toán ứng dụng – GVHD: ThS. Trần Thị Thùy Nƣơng 1. Các khái niệm cơ bản.
Phân loại mô hình và cách tiếp cận. CÁC MÔ HÌNH DỰ TRỮ TẤT ĐỊNH. Mô hình dự trữ tiêu thụ đều, bổ sung tức thời (Willson). Một số mô hình mở rộng từ mô hình Wilson.
Mô hình dự trữ tiêu thụ đều bổ sung dần. Mô hình dự trữ giá hàng thay đổi theo số lượng đặt mua. CÁC MÔ HÌNH DỰ TRỮ NGẪU NHIÊN. Mô hình dự trữ một giai đoạn.
Mô hình dự trữ có bảo hiểm. Mô hình dự trữ bán thành phẩm. Mô hình dự trữ với hàng hóa có khả năng tự huỷ. CÁC MÔ HÌNH DỰ TRỮ CÓ RÀNG BUỘC.
Mô hình với số lượng và đơn giá thay đổi theo giai đoạn. Mô hình dự trữ một loại hàng có ràng buộc. Bài toán dự trữ nhiều loại hàng có ràng buộc. Mô hình dự trữ nhiều loại hàng với nhu cầu ngẫu nhiên có hạn chế kho.
Mô hình dự trữ ràng buộc kho với chi phí và giá bán .55 Thực hiện: Nguyễn Trung Hiếu – MSSV: 070453M – Lớp: 07TN1D Trang 7 Một số mô hình Toán ứng dụng – GVHD: ThS. Trần Thị Thùy Nƣơng CHƢƠNG 1: PHƢƠNG PHÁP SƠ ĐỒ MẠNG LƢỚI (PERT) 1. Định nghĩa: Sơ đồ mạng lƣới (PERT) là một đồ thị hữu hạn, bậc 1, có hƣớng, liên thông, không chu trình, phản xứng và có hai đỉnh đặc biệt: đỉnh khởi đầu (1) có U+1 = , đỉnh kết thúc (n) có U-n =. Đồng thời mỗi cung (i, j) xác định một số thực tij không âm, gọi là độ dài cung (i, j).
Một sơ đồ mạng lƣới thông thƣờng mô tả 1 qui trình, gồm nhiều bƣớc công việc, với trật tự logic chặt chẽ, trong đó: Mỗi đỉnh đánh dấu một sự kiện. Mỗi cung thể hiện một công việc. Dữ kiện và các yếu tố: 1. Dữ kiện: Là 1 qui trình với tập hợp các công việc {yi: i = }, trong đó, các công việc này phải tuân theo 1 trình tự nhất định: yi+1 chỉ bắt đầu sau khi yi kết thúc, trừ trƣờng hợp i = 1 hoặc i = n.
Ta có thể biểu diễn dữ kiện theo mô tả sau: Công việc Tên công việc Trình tự: Y1 …… ……. Các yếu tố: Trong mặt phẳng, ta dùng 2 yếu tố nhƣ sau: Vòng tròn: thể hiện các sự kiện Các cung (hay đoạn thẳng có hƣớng): thể hiện các công việc. Sơ đồ là một đồ thị, có đỉnh đầu tiên – gọi là đỉnh khởi công (bắt đầu), chỉ có các cung đi ra và đỉnh kết thúc chỉ có các cung đi đến. Đỉnh giả và cung giả: Sử dụng để đảm bảo tính đơn của đồ thị Nếu có 2 hay nhiều hơn công việc X, Y, Z cùng bắt đầu sau sự kiện i và sự kết thúc của chúng tạo nên sự kiện j, ta không thể mô tả nhƣ sau: X i Y j Z Nếu làm nhƣ hình vẽ, sẽ dẫn đến 1 đồ thị bậc cao sử dụng các công việc giả, có thời gian tƣơng ứng bằng 0 và tạo nên các đỉnh riêng biệt, xen kẽ giữa 2 đỉnh tƣơng ứng với 2 sự kiện nói trên.
Thực hiện: Nguyễn Trung Hiếu – MSSV: 070453M – Lớp: 07TN1D Trang 8 Một số mô hình Toán ứng dụng – GVHD: ThS. Trần Thị Thùy Nƣơng i2 i j i3 Các cung với nét đứt là các cung giả, tương ứng với công việc giả. Sử dụng cung giả trong trƣờng hợp một số công việc, chỉ đƣợc thực hiện sau khi hoàn thành những tổ hợp khác nhau của một số công việc khác X Y H Z K H có thể bắt đầu sau khi X, Y hoàn thành nhưng không đòi hỏi sau Z hoàn thành trong khi K chỉ bắt đầu được sau cả X, Y , Z hoàn thành. Sơ đồ phác thảo và sơ đồ chính thức: 1.
Phác thảo sơ đồ: Từ 1 qui trình thực tế, việc lập 1 sơ đồ mạng lƣới có thể rất phức tạp; phác thảo sơ đồ là bƣớc cần thiết để thể hiện đầy đủ tính logic của qui trình và các tính chất của một đồ thị với tƣ cách là một sơ đồ mạng lƣới. Nếu sơ đồ đơn giản thì sơ đồ phác thảo càng gần với sơ đồ chính. Sơ đồ chính: Đƣợc hiệu chỉnh từ sơ đồ phác thảo, sao cho: Các cung không ngƣợc hƣớng. Các cung chồng chéo ít nhất.
Các đỉnh và các cung có đủ điều kiện ghi các chỉ tiêu thời gian. Thông thƣờng, một đỉnh phải đủ điều kiện ghi các thông tin nhƣ sau: Số hiệu đỉnh i tsi tmi Chỉ số k Thực hiện: Nguyễn Trung Hiếu – MSSV: 070453M – Lớp: 07TN1D Trang 9 Một số mô hình Toán ứng dụng – GVHD: ThS. Trần Thị Thùy Nƣơng Qui tắc đánh số hiệu đỉnh: Đỉnh bắt đầu đƣợc đánh số 1. Khi đã đánh số i cho 1 đỉnh thì “xóa” U-i và đánh số i + 1 cho đỉnh có U+ là tập rỗng, nếu có một số đỉnh có tính chất nhƣ nhau thì đánh số theo thứ tự ngẫu nhiên.
Đỉnh kết thúc là đỉnh đƣợc đánh số (n) khi U-n chỉ còn là tập rỗng. VD1: Lập sơ đồ mạng lƣới cho qui trình có các bƣớc công việc theo trình tự liệt kê ở bảng dƣới đây: Mã công việc Trình tự Thời gian (tuần) Y1 Bắt đầu ngay 8 Y2 Bắt đầu ngay 6 Y3 Bắt đầu ngay 8 Y4 Sau Y1 hoàn thành 3 Y5 Sau Y1, Y3 hoàn 9 thành Y6 Sau Y2, Y3, Y4 hoàn 8 thành Y7 Sau Y5, Y6 hoàn 7 thành Y8 Sau Y1 hoàn thành 6 Y9 Sau Y1, Y3 hoàn 8 thành Bước 1: Lập sơ đồ phác thảo. - Sơ đồ phác thảo có thể rất khác nhau và đôi khi phải lập nhiều lần sao cho từ sơ đồ phác thảo có thể sửa thành sơ đồ chính. - Sơ đồ trên có 1 đỉnh giả, sử dụng đỉnh giả này để đảm bảo mô tả đúng trình tự các công việc ở bảng trên.
Bước 2: Hiệu chỉnh để đƣợc sơ đồ chính - Với sơ đồ phác thảo trên, ta có thể hiệu chỉnh vị trí các đỉnh để đƣợc sơ đồ nhƣ sau: Thực hiện: Nguyễn Trung Hiếu – MSSV: 070453M – Lớp: 07TN1D Trang 10 Một số mô hình Toán ứng dụng – GVHD: ThS. Trần Thị Thùy Nƣơng Thứ tự hai đỉnh 3 và 4 có thể đổi cho nhau 2. CÁC CHỈ TIÊU THỜI GIAN TRÊN SƠ ĐỒ MẠNG LƢỚI: 2. Các chỉ tiêu thời gian cho các sự kiện (đỉnh) và đường găng: Với mỗi đỉnh hay mỗi sự kiện, trên sơ đồ chính, ta cần xác định các chỉ tiêu thời gian với nhiều mục đích: Tìm đƣợc thời gian ngắn nhất hoàn thành toàn bộ quy trình.
Tìm đƣợc đƣờng đi sơ cấp dài nhất từ đỉnh khởi công đến đỉnh kết thúc. Thời điểm sớm của đỉnh và chỉ số k (chỉ số đường găng): - Là thời điểm sớm nhất có thể bắt đầu công việc, đo bằng đƣờng đi sơ cấp dài nhất từ đỉnh 1 đến đỉnh đang xét, nếu thời điểm sớm của đỉnh 1 là 0. Ký hiệu: tsi t s1 = 0 tsi = max (tsj + tji) với (j,i) ∈ U+i - Nếu tsi = tsk + tki k là chỉ số đƣờng găng của i. - Trong trƣờng hợp k không là duy nhất, ta ghi tất cả các chỉ số tìm đƣợc và phần chỉ số k của đỉnh i.
Riêng đỉnh 1 thì không cần ghi số k. - Xét lại với VD1, ta có: + ts1 = 0; ts2 = 8 (k = 1); + ts3 = 8 (k = 1); + ts4 = max(8+3, 0+8, 6) = 11 (k = 2); s + t 5 = max(0+8, 8+0) = 8 (k = 2, 3); + ts6 = max(11+8, 8+9)= 19 (k = 4); s + t 7 = max(19+7, 8+6, 8+8) = 26 (k = 6); 2. Thời điểm muộn của đỉnh: - Là thời điểm mà tất cả các công việc tƣơng ứng với các cung đi ra từ đỉnh đó phải bắt đầu thực hiện nếu không muốn kéo dài thời gian của toàn bộ qui trình đã đƣợc xác định nhờ đƣờng găng.