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 1

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.3 MB
Số lượt tải: 14
Số lượt thích: 0 người
CÁC PHƯƠNG PHÁP ĐỊNH LƯỢNG
(Tóm tắt)
DẠNG TỔNG QUÁT
Dạng chính tắc
Bài toán dạng chính tắc là bài toán có những đặc trưng cơ bản sau:
- Các ràng buộc đều là phương trình,
- Các biến số đều không âm,
- Vế phải có thể nhận giá trị bất kỳ.
Nhận xét: Bài toán dạng chuẩn là bài toán dạng chính tắc có thêm các điều kiện, đó là:
- Các số hạng tự do không âm (các số hạng ở vế phải không âm) ;
- Ma trận các hệ số các ràng buộc A có chứa một ma trận đơn vị cấp m.
Nói cách khác, hệ các ràng buộc là hệ phương trình chuẩn.
Chú ý:
a. Phân biệt biến phụ và biến giả với 3 điểm sau:
- Biến phụ được sử dụng để đưa bài toán dạng tổng quát về dạng chính tắc còn biến giả được sử dụng để đưa bài toán dạng chính tắc về dạng chuẩn.
- Trong hàm mục tiêu, hệ số của các biến giả bằng M khi f(x) min hay bằng –M khi f(x) max còn biến phụ luôn có hệ số bằng 0.
- Biến phụ là con số thực giúp chúng ta biến đổi ràng buộc dạng bất phương trình về dạng phương trình còn biến giả thì 2 vế đã bằng nhau mà vẫn cộng thêm là làm việc “giả tạo” để tạo ra véc tơ đơn mà thôi.
b. Nếu bài toán dạng chính tắc có bi ≥0 và đã có sẵn một số véc tơ cột đơn trong A, thì chỉ cần thêm biến giả vào những phương trình cần thiết đủ để tạo bài toán mở rộng dạng chuẩn.
Phương pháp đồ thị (phương pháp hình học)

Một bài toán qui hoạch tuyến tính chỉ bao gồm 2 biến quyết định có thể được giải bằng phương pháp đồ thị. Phương pháp đồ thị bao gồm 2 bước cơ bản sau:
- Xác định miền chấp nhận bằng đồ thị
- Tìm giá trị của hàm mục tiêu trên miền chấp nhận đó.
Ví dụ: Bài Toán MAX
Sản phẩm
Nguyên liệu Chất phụ gia Bazơ hoà tan
Nguyên liệu 1 0,4 0,5
Nguyên liệu 2 0,2
Nguyên liệu 3 0,6 0,3
Nguyên liệu 1, 2 và 3 chỉ được cung ứng tương ứng là 20 tấn, 5 tấn và 21 tấn.
Giá bán cho mỗi sản phẩm và tính được lợi nhuận đạt được của mỗi tấn
chất phụ gia, bazơ hoà tan tương ứng là 40 ngàn đồng và 30 ngàn đồng. Để cực đại lợi nhuận trên mỗi tấn sản phẩm ta xây dựng bài toán Max.
Max 40F + 30B
Ràng buộc
0,4F + 0,5B ≤ 20 Nguyên liệu 1
0,2B ≤ 5 Nguyên liệu 2
0,6F + 0,3B ≤ 21 Nguyên liệu 3
F,B ≥ 0
Phân tích độ nhạy
Thay đổi các hệ số của hàm mục tiêu
Chú ý: Nếu hệ số của hàm mục tiêu thay đổi đủ lớn, điểm cực biên sẽ cho phương án tối ưu mới.
Phân tích độ nhạy
Thay đổi các hệ số của hàm mục tiêu
Phân tích độ nhạy
Thay đổi các ràng buộc
PHƯƠNG PHÁP ĐƠN HÌNH (Bài toán Min)
Max 40x1 + 30x2
Ràng buộc
0,4x1 + 0,5x2 ≤ 20
0,2x2 ≤ 5
0,6x1 + 0,3x2 ≤ 21
x1, x2 ≥ 0
-(Min) - 40x1 - 30x2
Ràng buộc
0,4x1 + 0,5x2 + x3 = 20
0,2x2 + x4 = 5
0,6x1 + 0,3x2 + x5 = 21
x1, x2 ≥ 0
Thuật toán gồm 5 bước như sau:
Bước 1: Lập bảng ban đầu. Căn cứ vào bài toán dạng chuẩn để lập bảng.
40
30
0
0
0
0
Bước 2: Kiểm tra tính tối ưu
- Nếu Δj ≤0 Vj thì phương án đang xét là tối ưu và giá trị hàm mục tiêu là f(x)=f0.
- Nếu ЭΔj >0 mà aij ≤0 Vi thì bài toán không có phương án tối ưu.
Nếu cả hai trường hợp trên không xảy ra thì chuyển sang bước 3.
Bước 3: Tìm biến đưa vào:
Xét các Δj >0, Nếu Δv=max Δj thì xv được chọn đưa vào. Khi đó cột v gọi là cột chủ yếu.
Bước 4: Tìm biến đưa ra:
Tính λi = bi/aiv ứng với các aiv > 0
Nếu λr=min λi thì xr là biến đưa ra. Khi đó, hàng r gọi là hàng chủ yếu, phần tử arv là phần tử trục xoay.
Bảng đơn hình đầu tiên
40
30
0
0
0
0
50
M
25
Bước 5: Biến đổi bảng như sau:
1. Thay xr bằng xv và cr bằng cv. Các biến cơ bản khác và hệ số tương ứng để nguyên.
2. Chia hàng chủ yếu (hàng r) cho phần tử trục xoay arv, chúng ta được hàng r mới và được gọi là hàng chuẩn.
3. Để có hàng i mới (i≠r), chúng ta lấy –aiv nhân với hàng chuẩn rồi cộng vào hàng i cũ.
4. Để có hàng cuối mới, chúng ta lấy -Δv nhân với hàng chuẩn rồi cộng vào hàng cuối cũ.
20
25
70
40
30
0
0
0
0
50
M
25
0
1/5
0
1
0
5
0
3/10
1
0
-2/3
6
0
10
0
0
-200/3
56
Bảng đơn hình thứ hai
1
1/2
0
0
10/6
35
20
25
70
0
1/5
0
1
0
5
0
3/10
1
0
-2/3
6
0
10
0
0
-200/3
-1400
0
0
-2/3
1
4/9
1
1
0
-5/3
0
-25/9
25
0
0
-100/3
0
-400/3
-1600
Bảng đơn hình thứ hai
Bảng đơn hình thứ ba
Kết luận: Bài toán có các Dj <0 Vjnên bài toán có phương án đang xét là tối ưu với nghiệm bài toán {x1, x2, x4} = {25,20,1} và -Minf(0) = -(-1600) =Maxf(0)
0
1
10/3
0
-20/9
20
Bài toán đường ngắn nhất
Thuật toán đặt nhãn
Ví dụ bài toán đặt nhãn
[19,3]
Thuật toán cây bao trùm tối thiểu
Bước 1: Một cách tùy ý, chúng ta bắt đầu tại nút 1, NC={1}. Xét các cung có nối với nút 1, cung (1,2) với khoảng cách bằng 20 km là nhỏ nhất. Vậy cung (1,2) thuộc cây bao trùm tối thiểu. Điều chỉnh tập nút NC={1,2} và tập nút NU={3,4,5,6}.
Bước 2: Xét tất cả các cung nối các nút từ tập NC đến NU. Cung (1,4) với khoảng cách bằng 30 km là nhỏ nhất so với các cung đang xét khác. Vậy, cung (1,4) thuộc cây bao trùm tối thiểu. Điều chỉnh tập nút NC={1,2,4} và tập nút NU = {3,5,6}.
Lặp lại Bước 2: Cung (4,3) với khoảng cách bằng 10km là nhỏ nhất so với các cung đang xét khác. Vậy, cung (4,3) thuộc cây bao trùm tối thiểu. Điều chỉnh tập nút NC = {1,2,4,3}và tập nút NU = {5,6}.
Lặp lại Bước 2: Cung (4,6) với khoảng cách bằng 20 km là nhỏ nhất. Vậy cung (4,6) thuộc cây bao trùm tối thiểu. Điều chỉnh tập NC ={1,2,4,3,6}, tập NU={5}.
Lặp lại Bước 2: Cung (3,5) với khoảng cách bằng 30km là nhỏ nhất. Vậy, cung (3,5) thuộc cây bao trùm tối thiểu. Điều chỉnh tập NC ={1,2,4,3,5,6}, tập NU={Ø}.
Cây bao trùm tối thiểu bao gồm các cung (1,2), (1,4), (4,3), (4,6) và (3,5) với tổng khoảng cách bằng 110 km.
No_avatarf
to tim huong giai toan bang phuong phap thdon hinh.sao toan ly thuyet the
 
Gửi ý kiến