Bài Toán Tối ưu Rời Rạc Và Lượng Cực đại - Tài Liệu đại Học

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Luận văn tổng hợp

1. Home
2. Luận văn tổng hợp
3. Bài toán tối ưu rời rạc và Lượng cực đại

Trich dan Bài toán tối ưu rời rạc và Lượng cực đại - Pdf 16

ứng dụng luồng cực đại trong bài toán tối ưu rời rạcĐức TrọngI. Bài toán Xétbài toán: Trongđó aij thuộc {0,1} pi nguyên dương i = 1,2,…,m;j = 1,2,…,n Bài toán trên là mô hình toán học của nhiều bàitoán tối ưu tổ hợp trong thực tế. Ví dụ: II. Vídụ 1. Bài toán phânnhóm sinh hoạt: Cóm sinh viên và n nhóm sinh hoạt chuyên đề.Với mỗi sinh viên i biết: - aij =1, nếu sinh viêni có nguyện vọng tham gia vào nhóm j - aij =0, nếu ngượclại - pi là số lượngnhóm chuyên đề mà sinh viên i phải tham dự i=1,2,…,m; j=1,2,…,n Trong số các cách phân các sinh viên vào nhóm chuyênđề mà họ có nguyện vọng tham gia và đảm bảo mỗi sinh viên i phảitham gia đúng pi nhóm, hãy tìm cách phân phối với số người trong nhómcó nhiều sinh viên tham gia nhất là nhỏ nhất có thể được. Bổ đề 1: Bài toán (1)-(2) có nghiệm tối ưu khi và chỉ khi: Chứng minh: Điều kiện cần là hiển nhiên vì sự tồn tại phương án của bàitoán suy ra bất đẳng thức trong (3) được thực hiện ít nhất dưới dạng dấu đẳngthức. Điều kiện đủ: Chỉ cần chỉ ra rằng nếu có (3) thì luôn có phươngán. Giả sử (3) đúng, gọi: Do(3) là điều kiện để (1)-(2) có nghiệm nên trong phần tiếp theo ta luôngiả thiết rằng điều kiệnđược thực hiên. Bâygiờ ta chỉ ra rằng bài toán (1)-(2) có thể chuyển về giải một số hữuhạn bài toán luồng cực đại trong mạng. Trước hết với mỗi k nguyêndương ta xây dựng mạng G(k) = (V,E) vớie thuộc E:khả năng thông qua c(e) c(s,ui) = pi c(ui,vj) = aij c(vj,t) = k Bổđề 2: Giả sử vớik nào đó luồng cực đại trong mạng Gtrong G(k*) có giá trị Δ Chứng minh: Do giá trị của luồng cực đại trong mạng G(k*)không vượt qu Δ, nên để chứng minh bổ đề ta chỉ cần chỉ ra luồngvới giá trị Δ trong mạng G(k*). Ta xây dựng luồng Φ như sau: Dễ dàng chứng minh Φ là luồng trong mạng G(m) có giá trị Δ.(đpcm) Bổđề 4: Nếu k=m thìluồng cực đại trong mạng G(m) có giá trị Δ. Chứng minh: Lập luận tương tự bổ đề 3 ta chỉ cần chỉ ra luồng với giátrị Δ trong mạng G(m). Thậtvậy, giả sử x* là nghiệm bài toán (1)-(2) được xây dựngtheo công thức như bổ đề 1, xây dựng Φ theo bổ đề 3 ta có luồng giá trị Δ.(đpcm) IV. Thuậttoán: Từ nhận xét 2 và 3 suy ra việc giải bài toán (1)-(2) là tìm k*nguyên dương nhỏ nhất sao cho luồng cực đại trong mạng G(k*)có giá trị Δ.Nhận xét 4 giới hạn giá trị k* thuộc [1,m]. Từ đây rút ra thuật toán: áp dụng phương pháp chia nhị phântrên đoạn [1,m] tìm k* trong mỗi bước giải bài toán tìm luồngcực đại trong. Delta:=0; For i:=1 to m do begin read(fi,p[i]); Delta:=Delta+p[i]; End; For i:=1 to m do For j:=1 to n do read(fi,a[i,j]); Close(fi); s:=m+1;t:=n+1; For i:=1 to m do a[s,i]:=p[i]; End; FunctionFindPath:Boolean; Var Queue:Array[1..100]of Integer; i,j,First,Last,v:Integer; Begin Fillchar(TraceX,Sizeof(TraceX),0); Fillchar(TraceY,Sizeof(TraceY),0); First:=1;Last:=0; For i:=1 to m do If x[s,i]inc(last); Queue[last]:=i; traceX[i]:=-1; end; While First<=Last do Begin i:=Queue[First];Inc(first); For j:=1 to n do If (traceY[j]=0)and(x[i,j]traceY[j]:=i; Tải File Word Nhờ tải bản gốc Tài liệu, ebook tham khảo khác

• Giải các bài toán tối ưu và thống kê trên MS Excel
• Bài toán lượng cực đại và ứng dụng
• Bài toán tối ưu rời rạc và Lượng cực đại
• Bài toán tối ưu bê móng trụ nền đá
• Báo cáo tổng hợp về một số phần hành kế toán chủ yếu & tình hình tổ chức hạch toán tại Công ty sản xuất ô tô daihatsu-vietindo
• 1 Báo cáo tổng hợp về một số phần hành kế toán chủ yếu và tình hình tổ chức hạch toán tại Công ty sản xuất ô tô daihatsu-vietindo
• Mã hóa tối ưu nguồn rời rạc không nhớ
• Bài toán tối ưu và quy hoạch tuyến tính
• Bài giảng Giải các bài toán tối −u và thống kê trên Microsoft Excel
• Chương 5: MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ
• Thông tin chính trị ngoại giao bằng ảnh báo chí trên báo Nhân dân hằng ngày (Khảo sát từ tháng 1 năm 2011 đến tháng 5 năm 2013)
• Phát ngôn cầu khiến gián tiếp trong tiếng Việt ( liên hệ với tiếng Hán)
• Phát thanh tiếng dân tộc với người dân tộc thiểu số bản địa Kon Tum
• Phóng sự điều tra trên Báo Công an thành phố Hồ Chí Minh
• Phát thanh trên mạng Internet
• Phát triển kinh tế biển để thoát nghèo bền vững tại các xã ven biển huyện Hậu Lộc tỉnh Thanh Hóa
• Phát triển và quảng bá thương hiệu giáo dục đại học Việt Nam trên báo điện tử hiện nay
• Phim tài liệu chân dung truyền hình (TFS) - Đài truyền hình Thành phố Hồ Chí Minh
• Phong cách chính luận của nhà báo Trần Bạch Đằng
• Phong cách hài chính luận của nhà báo Lý Sinh Sự (Khảo sát trên Báo Lao Động năm 2012 – 2013)

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top