Violet
Baigiang

Tìm kiếm theo tiêu đề

Tin tức thư viện

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

12099162 Kính chào các thầy, cô. Khi cài đặt phần mềm , trên PowerPoint và Word sẽ mặc định xuất hiện menu Bộ công cụ Violet để thầy, cô có thể sử dụng các tính năng đặc biệt của phần mềm ngay trên PowerPoint và Word. Tuy nhiên sau khi cài đặt phần mềm , với nhiều máy tính sẽ...
Xem tiếp

Quảng cáo

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (024) 66 745 632
  • 096 181 2005
  • contact@bachkim.vn

Tìm kiếm Bài giảng

bài giảng PP định lượng 2

Wait
  • Begin_button
  • Prev_button
  • Play_button
  • Stop_button
  • Next_button
  • End_button
  • 0 / 0
  • Loading_status
Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Dương Văn Hùng
Ngày gửi: 09h:48' 21-09-2010
Dung lượng: 1.5 MB
Số lượt tải: 16
Số lượt thích: 0 người
Bài toán dòng cực đại
Phương pháp tiếp cận chung như sau:
Tìm bất kỳ đường đi nào từ nút nguồn đến nút hút mà có tải năng trên dòng theo hướng đi của dòng lớn hơn 0 (>0) cho tất cả các cung trên đường đi.
Gia tăng dòng theo đường đi càng nhiều càng tốt.
Tiếp tục tìm các đường đi từ nút nguồn - nút hút, mà có tải năng trên dòng theo hướng đi của dòng lớn hơn 0 cho tất cả các cung, và gia tăng dòng theo các đường đi càng nhiều càng tốt.
Chấm dứt thuật toán khi không thể tìm thêm một đường đi từ nút nguồn đến nút hút có tải năng trên dòng lớn hơn 0 trên tất cả các cung theo đường đi.
Trước khi trình bày chi tiết về thuật toán dòng cực đại, chúng ta mô tả qui trình nhằm đảm bảo rằng mỗi bước theo trực giác sẽ dẫn đến giải pháp tối ưu cho bài toán dòng cực đại.
Qui trình này sử dụng lượng dòng bổ nhiệm để chọn tuyến đường tùy chọn bằng các dòng giả theo hướng đi ngược lại. Ví dụ, xem cung (3,6 )
Các bước của thuật toán dòng cực đại
Bước 1: Tìm bất kỳ một đường đi từ nút nguồn đến nút hút có các tải năng trên dòng theo hướng đi lớn hơn 0 (>0) đối với tất cả các cung theo đường đi. Nếu không có đường đi nào như vậy, phương án tối ưu đã đạt được và chuyển sang bước 4.
Bước 2: Tìm tải năng nhỏ nhất của cung theo đường đi lựa chọn ở bước 1: Pf.
Bước 3: Đối với đường đi lựa chọn ở bước 1, giảm tất cả tải năng dòng trên cung theo hướng đi bằng một lượng Pf và tăng tất cả tải năng dòng trên cung theo hướng đi ngược bằng một lượng Pf.
Quay lại bước 1.
Bước 4: So sánh tải năng ban đầu và cuối cùng trên dòng của cung cho tất cả các cung trong mạng cho phép xác định mô hình dòng cuối cùng.
Ví dụ: Chúng ta cùng xem xét hệ thống đường cao tốc liên tỉnh Bắc Nam đi qua Thành phố A. Dòng phương tiện di chuyển Bắc Nam đạt mức 1500 phương tiện/giờ vào thời gian cao điểm. Để thực hiện chương trình duy tu bảo dưỡng đường cao tốc vào mùa hè, theo đó cần thiết phải tạm thời đóng một số làn xe và giới hạn tốc độ thấp hơn, Sở giao thông đã đề trình một mạng tuyến đường tùy chọn qua Thành phố.
Sau bước lặp lần 4, kết quả như trên Hình 3-21. Như vậy, mạng không tồn tại bất kỳ một đường đi từ nút 1 đến nút 7 có tải năng trên dòng của các cùng theo hướng đi lớn hơn 0. Phương án tối ưu đã đạt được. Chúng ta chuyển sang bước 4 của thuật toán, sau đó So sánh tải năng đầu va cuối trên các cung ta có kết quả sau hình 3-22
1
1
7
7
Điều hành dự án với thời gian hoạt động có tính chắc chắn (PERT)
Ký hiệu nút trong sơ đồ PERT
Ví dụ: Dự án Mở rộng trung tâm
Bước 1: Xác định các hoạt động của dự án và dự kiến thời gian hoàn thành cho mỗi hoạt động. Nhận biết các hoạt động, xác định mối quan hệ liên kết giữa chúng và dự kiến thời gian hoàn thành mỗi hoạt động có ý nghĩa quan trọng trong việc áp dụng phương pháp điều hành PERT/CPM.
Sau đó, phải xác định các hoạt động ngay trước, tức là những hoạt động phải được hoàn thành để bắt đầu các hoạt động khác.
Bước 2: Thiết lập mạng dự án nhằm mô tả các hoạt động và các hoạt động ngay trước của các hoạt động như đã nêu trong bước 1.
Trên mỗi nút, ngoài trừ nút bắt đầu (Start) và nút kết thúc (Finish), đều có thể trình bày nhiều thông tin liên quan đến từng hoạt động.
Khi có mạng dự án, thực hiện việc đánh số thứ tự cho mỗi nút và ghi ngay thời gian hoàn thành của mỗi hoạt động.
Chú ý: khi vẽ nên tránh các cung cắt nhau.
Bước 3: Tính thời điểm khởi công sớm (ES) và hoàn thành sớm (EF) cho mỗi hoạt động.
- Thời điểm hoàn thành sớm của mỗi hoạt động theo công thức: EFj=ESj+tj
Thời điểm khởi công sớm: Thời điểm khởi công sớm của một hoạt động bằng giá trị lớn nhất trong các thời điểm hoàn thành sớm của tất cả các hoạtđộng ngay trước nó và được tính bằng công thức: ESj=Max{EFi} mọi i < j.
Chú ý: Bất cứ hoạt động nào, nếu chỉ có một hoạt động ngay trước nó đều có thời điểm khởi công sớm bằng thời điểm hoàn thành sớm của hoạt động ngay trước nó.
Bước 4: Tính thời điểm hoàn thành muộn (LF) và thời điểm khởi công muộn (LS).
- Thời điểm hoàn thành muộn của hoạt động cuối cùng bằng thời điểm hoàn thành dự án sớm.
- Thời điểm khởi công muộn của mỗi hoạt động được tính theo công thức: LSj=LFj-tj
- Thời điểm hoàn thành muộn: Thời điểm hoàn thành muộn của một hoạt động là giá trị nhỏ nhất trong các thời điểm khởi công của tất cả các hoạt động ngay sau hoạt động đó và được tính bằng công thức như sau: LFi=Min{LSj} mọi j>i
Bước 5: Tính thời gian dự trữ mỗi hoạt động, hoạt động găng và đường găng Thời gian dự trữ chính là thời gian một hoạt động có thể chậm trễ mà không làm tăng thời gian hoàn thành của dự án. Thời gian dự trữ của hoạt động j được tính theo công thức sau:
Sj=LSj-ESj=LFj-EFj
Hoạt động găng là hoạt động có thời gian dự trữ bằng không. Trong dự án mở rộng trung tâm, hoạt động găng gồm có A, E, F, G, I.
Bước 6: Hình thành bảng lịch trình hoạt động
Điều hành dự án với thời gian hoạt động có tính ngẫu nhiên (PERT)
Ví dụ: Dự án máy hút bụi
Các công thức tính
Thời gian kỳ vọng của hoạt động
Phương sai của thời gian
Ví dụ: Giả sử bộ phận quản trị đã dành cho dự án máy hút bụi thời gian 20 tuần. Do vậy, xác suất để dự án hoàn thành trong thời hạn 20 tuần này. Sử dụng phân phối xác suất chuẩn, chúng ta đang xác định xác suất để T ≤ 20.
0.4656
0.5
Z = (T- Ttb)/s
Sau khi tính z thì tra bảng phân phối chuẩn ta có kết quả xác suất
Kiểm định dòng vào bằng tiêu chuẩn c2
Quá trình kiểm định giả thuyết được tiến hành theo các bước sau:
Bước 1 Xây dựng cặp giả thuyết:
H0: dòng vào là dòng Poisson
H1: dòng vào không phải là dòng Poisson
Bước 2 Phân khoảng thời gian dự định quan sát dòng yêu cầu đến hệ thống ra thành n khoảng thời gian nhỏ với n≥50 sau đó tiến hành quan sát số yêu cầu xuất hiện trong từng khoảng thời gian nhỏ ấy. Hệ thống số liệu thu được dưới dạng một bảng phân phối thực nghiệm với đại lượng ngẫu nhiên là số yêu cầu đến hệ thống trong các khoảng thời gian.
Với m’ là số các giá trị quan sát đã được điều chỉnh theo yêu cầu ni ≥5 nghĩa là khi tính toán nếu có các n’i<5 thì chúng ta phải gom lại để bảo đảm tất cả các n’i ≥5.
Với a là số yêu cầu trung bình xuất hiện trong khoảng thời gian quan sát:
a =
Hệ thống từ chối cổ điển Erlang (M/M/n)
Một hệ thống gồm có n kênh phục vụ, năng suất như nhau và bằng μ (μ: số yêu cầu được phục vụ trong một đơn vị thời gian trên một kênh). Dòng yêu cầu đến hệ thống là dòng tối giản với cường độ λ (λ: số yêu cầu đến hệ thống trong một đơn vị thời gian). Thời gian phục vụ của các kênh là đại lượng ngẫu nhiên tuân theo qui luật hàm số mũ với tham số μ. Hệ thống phục vụ theo nguyên tắc: một yêu cầu đến hệ thống nếu gặp lúc trong hệ thống có ít nhất một kênh rỗi thì được nhận vào phục vụ tại một kênh rỗi. Ngược lại, gặp lúc mọi kênh đều bận thì bị từ chối và đi ra khỏi hệ thống..
k = (0,n)
Xác suất không có yêu cầu (p0)
Xác suất từ chối yêu cầu (ptc)
Xác suất phục vụ yêu cầu (pv)
Số kênh bận trung bình(Lb)
Hệ số kênh bận (Kb)
Số kênh rỗi trung bình (nr)
Năng lực phục vụ thực tế của hệ thống (Q)
Tổng chi phí và tổn thất (TC)
T là tổng thời gian hoạt động của hệ thống,
Cb là chi phí cho 1 kênh làm việc trong 1 đơn vị thời gian,
Cr là chi phí phí cho 1 kênh không làm việc trong 1 đơn vị gian,
Ctc là tổn thất do từ chối 1 yêu cầu trong 1 đơn vị thời gian.
Trong đó: d là doanh thu do phục vụ một yêu cầu trong một đơn vị thời gian.
Doanh thu (D)
Hiệu quả kinh tế (E)
Hệ thống chỉ tiêu phân tích tình hình hoạt động
Hệ số kênh bận (Kr)
Ví dụ:
Một trạm điện thoại tự động có khả năng phục vụ đồng thời 6 yêu cầu đàm thoại. Trung bình một cuộc đàm thoại mất 1,5 phút. Dòng yêu cầu đàm thoại đến trạm giả thiết là dòng tối giản có cường độ với 4 yêu cầu mỗi phút. Hãy đánh giá tình hình hoạt động của trạm.

Giải:
Trạm điện thoại được xem như hệ thống từ chối cổ điển.
Theo giả thiết, ta có:
- Số kênh n=6;
- Cường độ dòng vào là: λ=4yêu cầu/phút;
- Năng suất phục vụ là: μ=1/wb =1/1,5 yêu cầu/phút.
- Như vậy, α=λ/μ=6.
Dựa vào các đại lượng này, chúng ta tính toán một số chỉ tiêu phản ảnh tình hình hoạt động của trạm điện thoại như sau:
Một hệ thống có n kênh phục vụ, năng suất như nhau và bằng μ. Dòng yêu cầu đến hệ thống là dòng tối giản với cường độ λ. Thời gian phục vụ của các kênh tuân theo qui luật hàm số mũ với tham số μ. Hệ thống phục vụ theo nguyên tắc: một yêu cầu đến hệ thống nếu gặp lúc trong hệ thống có ít nhất một kênh rỗi thì được nhận vào phục vụ, ngược lại nếu mọi kênh đều bận thì phải xếp hàng chờ cho đến khi có ít nhất 1 kênh được giải phóng thì được nhận vào phục vụ (thời gian chờ và độ dài hàng chờ không hạn chế).
Hệ thống chờ với độ dài hàng chờ không hạn chế hạn chế (M/M/n)
Xác suất không có yêu cầu (p0)
Xác suất phục vụ yêu cầu (pv)
Số kênh bận trung bình(Lb)
Hệ số kênh bận (Kb)
Số kênh rỗi trung bình (nr)
Năng lực phục vụ thực tế của hệ thống (Q)
Tổng chi phí và tổn thất (TC)
Doanh thu (D)
Hiệu quả kinh tế (E)
Hệ thống chỉ tiêu phân tích tình hình hoạt động
Xác suất chờ của yêu cầu (pq)
Số yêu cầu chờ trung bình (Lq)
Thời gian chờ trung bình (Wq)
Hệ số kênh rỗi (Kr)
Thời gian lưu lại trung bình (W)
Ví dụ: Một bến cảng có 5 cầu xếp dỡ hàng hoá. Dòng các tàu đến cảng là dòng tối giản, trung bình trong một tháng có 20 tàu cập cảng. Thời gian bốc dỡ xong một tàu tại mỗi cầu tàu là đại lượng ngẫu nhiên và trung bình mỗi tàu mất 6 ngày. Cho biết:
- Chi phí bình quân cho 1 cầu xếp dỡ làm việc là 1 triệu đồng/tháng.
- Nếu 1 cầu xếp dỡ không làm việc trong 1 tháng thì cảng sẽ thiệt hại 1 triệu đồng.
- Chi phí cho bình quân một tàu chờ 1 triệu đồng/tháng.
Hệ thống chờ với độ dài hàng chờ hạn chế (M/M/n/n+m)
Một hệ thống có n kênh phục vụ, năng suất như nhau và bằng μ, thời gian phục vụ của các kênh tuân theo qui luật hàm số mũ với tham số μ. Dòng yêu cầu đến hệ thống là dòng tối giản với cường độ λ. Hệ thống phục vụ theo nguyên tắc: một yêu cầu đến hệ thống nếu gặp lúc trong hệ thống có ít nhất 1 kênh rỗi thì được nhận vào phục vụ, ngược lại nếu gặp lúc mọi kênh đều bận thì sẽ xảy ra 2 trường hợp: nếu trong hệ thống số yêu cầu chờ còn ít hơn số yêu cầu chờ cho phép (m) thì yêu cầu đó được xếp hàng chờ; nếu trong hệ thống, số yêu cầu chờ đã đủ (bằng m) thì yêu cầu đó bị từ chối.
Xác suất không có yêu cầu (p0)
Xác suất từ chối yêu cầu (ptc)
Xác suất phục vụ yêu cầu (pv)
Số kênh bận trung bình(Lb)
Hệ số kênh bận (Kb)
Số kênh rỗi trung bình (nr)
Năng lực phục vụ thực tế của hệ thống (Q)
Tổng chi phí và tổn thất (TC)
Doanh thu (D)
Hiệu quả kinh tế (E)
Hệ thống chỉ tiêu phân tích tình hình hoạt động
Xác suất chờ của yêu cầu (pq)
Số yêu cầu chờ trung bình (Lq)
Số yêu cầu lưu lại trung bình trong hệ thống (L)
Thời gian chờ trung bình (Wq)
Hệ số kênh rỗi (Kr)
Thời gian lưu lại trung bình (W)
Ví dụ:
Một trạm sửa chữa máy nông nghiệp có một căn nhà chứa được một máy đang sửa chữa và một sân có diện tích chứa được 3 máy chờ. Biết rằng trạm sữa chữa xong một máy trung bình mất 2 ngày (wb=2 ngày) và trung bình 2 ngày có một máy đến trạm sửa chữa (λ=0,5 máy/ngày). Nguyên tắc phục vụ của trạm là nguyên tắc phục vụ của hệ thống chờ với độ dài hàng chờ hạn chế.
Giả định tăng thêm 1 dây chuyền thì có tốt hơn không?
Nếu tăng thêm 1 dây chuyền sửa chữa nữa (n=2), kết quả tính toán được trình bày ở Bảng 5-4.
 
Gửi ý kiến