Giáo trình Toán ứng dụng – PGS. TS Nguyễn Hà Thanh

pdf

148

1 MB

0

41

4.3 (
6 lượt)

1481 MB

Nhấn vào bên dưới để tải tài liệu

Đang xem trước 10 trên tổng 148 trang, để tải xuống xem vừa đủ hãy nhấn vào bên trên

Chủ đề tương quan

Tài liệu tương tự

Nội dung

TRƯỜNG ĐẠI HỌC NÔNG NGHIỆP I
PGS.TS. NGUYỄN HẢI THANH

TOÁN ỨNG DỤNG
(Giáo trình Sau đại học)

NHÀ XUẤT BẢN ĐẠI HỌC SƯ PHẠM

Mã số: 01.01.1/121. ĐH 2005

2

Mục lục

Mở đầu
CHƯƠNG I. MỘT SỐ MÔ HÌNH VÀ PHƯƠNG PHÁP TỐI ƯU
1. Mô hình quy hoạch tuyến tính
1.1. Các bước cần thiết khi áp dụng phương pháp mô hình hoá
1.2. Mô hình quy hoạch tuyến tính
1.3. Phương pháp đơn hình
1.4. Giải mô hình quy hoạch tuyến tính bằng các phần mềm tính toán
1.5. Một số ứng dụng của phương pháp đơn hình

5
7
7
7
7
11
14
16

2. Bổ sung thêm về phương pháp đơn hình
2.1. Đưa BTQHTT về dạng chính tắc
2.2. Phương pháp đơn hình mở rộng

17
17
19

3. Mô hình quy hoạch tuyến tính đa mục tiêu
3.1. Các khái niệm cơ bản
3.2. Một số phương pháp giải BTQHTT đa mục tiêu
3.3. Phương pháp thoả dụng mờ tương tác giải BTQHTT đa mục tiêu

21
21
23
25

4. Mô hình tối ưu phi tuyến đơn và đa mục tiêu
4.1. Một số khái niệm cơ bản
4.2. Một số phương pháp và phần mềm giải bài toán tối ưu phi tuyến đơn mục tiêu
4.3. Một số phương pháp giải bài toán tối ưu phi tuyến đa mục tiêu

29
29
31
37

CHƯƠNG II. CÁC MÔ HÌNH MẠNG

41

1. Mô hình mạng vận tải
1.1. Phát biểu bài toán vận tải
1.2. Tạo phương án vận tải xuất phát
1.3. Phương pháp phân phối giải bài toán vận tải
1.4. Phương pháp phân phối cải biên giải bài toán vận tải

41
41
42
44
48

2. Mô hình mạng PERT
2.1. Các khái niệm cơ bản về PERT
2.2. Sơ đồ PERT với số liệu ngẫu nhiên
2.3. Điều chỉnh dự án khi kế hoạch một số hoạt động bị phá vỡ
2.4. Tính thời gian rút gọn tối ưu bằng phương pháp đơn hình
2.5. Áp dụng mạng PERT trong phân tích chi phí và quản lí tài chính dự án

51
51
56
57
59
59

3. Một số mô hình mạng khác
3.1. Bài toán cây khung tối thiểu
3.2. Bài toán tìm đường đi ngắn nhất và quy hoạch động
3.3. Áp dụng quy hoạch động cho một số bài toán ngành điện

62
62
64
67

3

CHƯƠNG III. GIỚI THIỆU LÍ THUYẾT MÔ PHỎNG VÀ MÔ HÌNH HÀNG CHỜ

73

1. Mục đích và các công cụ của mô phỏng
1.1. Khái niệm về mô phỏng ngẫu nhiên
1.2. Các công cụ chủ yếu của mô phỏng
1.3. Mô phỏng một số phân phối xác suất

73
73
73
74

2. Áp dụng mô phỏng ngẫu nhiên
2.1. Vai trò của phương pháp mô phỏng
2.2. Các bước cần tiến hành khi áp dụng mô phỏng
2.3. Một số ví dụ về áp dụng phương pháp mô phỏng

78
78
78
79

3. Một số vấn đề về mô hình hàng chờ
3.1. Một số yếu tố cơ bản của hệ thống hàng chờ
3.2. Các chỉ số cần khảo sát
3.3. Tính toán các chỉ số
3.4. Áp dụng mô phỏng cho một số hệ thống hàng chờ

88
88
92
92
94

CHƯƠNG IV. PHÂN TÍCH MARKOV VÀ ỨNG DỤNG

105

1. Các khái niệm cơ bản về xích Markov
1.1. Một số định nghĩa
1.2. Ma trận xác suất chuyển trạng thái và phân phối dừng
1.3. Các tính chất và định lí

105
105
106
111

2. Một số ứng dụng của phân tích Markov
2.1. Tìm cân bằng thị phần
2.2. Chính sách thay thế vật tư thiết bị
2.3. Phân tích Markov trong dự báo thất thu cho các hợp đồng thực hiện trước
2.4. Tìm phân phối giới hạn cho một hệ thống kĩ thuật
2.5. Một ứng dụng của quá trình sinh−tử cho hệ thống hàng chờ

111
112
112
113
116
120

3. Mô phỏng xích Markov
3.1. Mô phỏng xích Markov thời gian rời rạc
3.2. Mô phỏng xích Markov thời gian liên tục

123
123
124

Phần bài tập
Phần phụ lục
Tài liệu tham khảo

4

126
137
145

Mở đầu

Trong một vài năm gần đây, các môn học Toán − Tin ứng dụng đã được đưa vào
chương trình đào tạo Sau đại học cho một số chuyên ngành kinh tế − kĩ thuật như Quản
trị kinh doanh, Quản lí đất đai, Công nghệ thông tin, Sinh học … tại một số trường đại
học trong nước. Các môn học này, tuy số đơn vị học trình chưa nhiều nhưng đã giúp cho
học viên cao học cũng như các nghiên cứu sinh có những kiến thức cơ sở và nâng cao về
Toán học và Tin học, đặc biệt về các phương pháp tính toán khoa học (Scientific
Computing Methods), là các vấn đề hết sức cần thiết cho các đề tài nghiên cứu khoa học
của họ. Điều này cũng phù hợp với xu thế chung trong đào tạo Sau đại học tại các
trường đại học nước ngoài, với các môn học về Toán – Tin nâng cao cho học viên cao
học, thường chiếm thời lượng khá lớn tới khoảng 200 đến 250 tiết bao gồm nhiều nội
dung phong phú và cấp thiết.
Xuất phát từ những lí do trên và dựa trên các kinh nghiệm tích luỹ được trong quá
trình dạy một số môn học cho chương trình Cao học Quản lí đất đai và Cao học Điện
(Trường Đại học Nông nghiệp I), Cao học Toán − Tin ứng dụng (Trường Đại học Bách
khoa Hà Nội), Cao học Quản trị kinh doanh (tại một số trường đại học khác), chúng tôi
biên soạn giáo trình này với mong muốn việc ứng dụng các phương pháp toán học, các
phương pháp vận trù học được triển khai rộng rãi hơn và mang lại các hiệu quả thiết
thực hơn. Giáo trình với thời lượng từ 45 tới 60 tiết, trước hết, dành cho học viên cao
học ngành Điện, với các nội dung đã được Khoa Cơ điện và Khoa Sau đại học, Trường
Đại học Nông nghiệp I, thông qua. Các chủ đề trong giáo trình bao gồm: một số mô hình
và phương pháp tối ưu, các bài toán về mạng, giới thiệu về quy hoạch động, một số ứng
dụng của lí thuyết hàng chờ (Waiting Line Theory) và mô phỏng ngẫu nhiên (Stochastic
Simulation), các khái niệm cơ bản và ứng dụng của quá trình ngẫu nhiên Markov. Đây là
các chủ đề chính về Toán ứng dụng và Vận trù học mà học viên cao học của nhiều
chuyên ngành kinh tế – kĩ thuật tại các trường đại học nước ngoài bắt buộc phải học.
Các chủ đề này có thể giúp ích không chỉ cho vấn đề quản lí – sử dụng điện mà còn cho
vấn đề thiết kế và xây dựng các hệ thống kĩ thuật điện. Giáo trình cũng có thể được lấy
làm tài liệu tham khảo về các phương pháp toán ứng dụng hay mô hình hoá cho chương
trình Cao học các chuyên ngành như: Quản lí đất đai, Kinh tế nông nghiệp và một số
chuyên ngành kinh tế − kĩ thuật khác.
Khi biên soạn giáo trình, chúng tôi luôn chú ý nhấn mạnh khía cạnh ứng dụng các
phương pháp toán học và khía cạnh tính toán khoa học với các ví dụ minh hoạ chọn lọc,
nhằm giúp cho học viên hiểu rõ nên áp dụng các phương pháp đó vào các vấn đề nghiên
cứu nào và áp dụng chúng như thế nào cho một số trường hợp cụ thể. Do thời lượng của
môn học, giáo trình không đi sâu vào vấn đề chứng minh toán học của các phương pháp
này cũng như các ứng dụng tổng quát của chúng trong các hệ thống lớn.

5

Hi vọng rằng, những học viên cao học quan tâm tới các phương pháp toán học
được trình bày trong giáo trình có thể tự mình tiếp tục có những nghiên cứu chuyên sâu
hơn sau này. Chẳng hạn, với kiến thức về quy hoạch động và các phương pháp tối ưu phi
tuyến mà giáo trình cung cấp, người đọc có thể tiếp tục nghiên cứu về các phương pháp
quy hoạch động nhằm áp dụng vào các hệ điều khiển tối ưu trong tự động hoá. Còn với
một số chủ đề về xích Markov và ứng dụng cũng như mô phỏng xích Markov, người đọc
có thể tiếp tục nghiên cứu về các mô hình ngẫu nhiên như quá trình sinh−tử hay quá
trình hồi phục có nhiều ứng dụng rộng rãi trong ngành Điện, Điện tử và Viễn thông hay
Công nghệ thông tin.
Đây là một trong số không nhiều các giáo trình về Toán ứng dụng dành cho chương
trình Sau đại học các chuyên ngành kinh tế – kĩ thuật tại các trường đại học trong nước,
nên mặc dù chúng tôi hết sức cố gắng trong quá trình biên soạn, nhưng chắc chắn giáo
trình không tránh khỏi còn tồn tại những điểm hạn chế. Chúng tôi rất mong nhận được các
ý kiến đóng góp của các nhà khoa học, các thầy giáo, cô giáo, các học viên cao học, tiến sĩ
để giáo trình được hoàn chỉnh, chính xác và sinh động hơn.
Cuối cùng, tác giả xin chân thành cảm ơn Khoa Sau đại học và Khoa Cơ điện,
Trường Đại học Nông nghiệp I về những giúp đỡ quý báu trong quá trình biên soạn;
cảm ơn Bộ môn Toán, giảng viên Đặng Xuân Hà và Bộ môn Tin học, các học viên cao học
chuyên ngành Điện khoá 10 và 11, Trường Đại học Nông nghiệp I; kĩ sư Phan Văn Tiến
và các học viên cao học chuyên ngành Toán – Tin ứng dụng, khoá 1 và 2, Trường Đại học
Bách Khoa Hà Nội, đã dành ý kiến đóng góp và tham gia hoàn chỉnh một số nội dung của
giáo trình này. Tác giả cũng xin chân thành cảm ơn các ý kiến phản biện quý báu của các
ông Trưởng bộ môn Toán, Trường Đại học Nông nghiệp I và Trưởng khoa Toán – Tin ứng
dụng, Trường Đại học Bách khoa Hà Nội.
Hà Nội, ngày 19 tháng 5 năm 2005
PGS.TS. Nguyễn Hải Thanh

6

Chương I
MỘT SỐ MÔ HÌNH VÀ PHƯƠNG PHÁP TỐI ƯU
1.

Mô hình quy hoạch tuyến tính

1.1.

Các bước cần thiết khi áp dụng phương pháp mô hình hoá

− Trước hết phải khảo sát, phát hiện vấn đề cần giải quyết.
− Phát biểu các điều kiện ràng buộc, mục tiêu của bài toán dưới dạng định tính. Sau
đó lựa chọn các biến quyết định / các ẩn số và xây dựng mô hình định lượng (còn gọi là
mô hình toán học).
− Thu thập số liệu, xác định phương pháp giải quyết.
− Định ra quy trình giải / thuật giải. Có thể giải mô hình bằng cách tính toán thông
thường. Đối với các mô hình lớn, gồm nhiều biến và nhiều điều kiện ràng buộc cần lập
trình và giải mô hình trên máy tính.
− Đánh giá kết quả. Trong trường hợp phát hiện thấy có kết quả bất thường hoặc kết
quả không phù hợp với thực tế, cần kiểm tra và chỉnh sửa lại quy trình giải hoặc mô hình.
− Triển khai các phương án tìm được trên thực tế.
Các thuật ngữ sau thường gặp khi áp dụng phương pháp mô hình hoá:
− Ứng dụng toán / Toán ứng dụng (Mathematical Applications hay Applied Mathematics).
− Vận trù học (Operations Research viết tắt là OR).
− Khoa học quản lí (Management Science viết tắt là MS)
1.2.

Mô hình quy hoạch tuyến tính

Phát biểu mô hình
Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình
quy hoạch tuyến tính hay bài toán quy hoạch tuyến tính (BTQHTT), mà trong đó chúng
ta muốn tối ưu hoá (cực đại hoá hay cực tiểu hoá) hàm mục tiêu:
z = c1x1 + c2x2 + cnxn → Max (Min)
với các điều kiện ràng buộc:
a11x1 + a12x2 +… +a1nxn

≤ b1

a21x1 + a22x2 +… +a2nxn

≤ b2

…
am1x1 + am2x2 +… +amnxn

≤ bm

x1, x2,…, xn ≥ 0 (điều kiện không âm)

7

Ví dụ: z = 8×1 + 6×2 → Max
với các ràng buộc:
4×1 + 2×2 ≤ 60
2×1 + 4×2 ≤ 48
x 1, x2 ≥ 0
Cần tìm các giá trị của các biến quyết định x1, x2 để các ràng buộc được thoả mãn
và hàm mục tiêu đạt giá trị lớn nhất.
Bài toán này có ý nghĩa kinh tế như sau: Giả sử một xí nghiệp sản xuất hai loại sản
phẩm I và II. Để sản xuất ra một đơn vị sản phẩm I cần có 4 đơn vị nguyên liệu loại A và
2 đơn vị nguyên liệu loại B, các chỉ tiêu đó cho một đơn vị sản phẩm loại II là 2 và 4.
Lượng nguyên liệu dự trữ loại A và B hiện có là 60 và 48 (đơn vị). Hãy xác định phương
án sản xuất đạt lợi nhuận lớn nhất, biết lợi nhuận trên mỗi đơn vị sản phẩm bán ra là 8 và 6
(đơn vị tiền tệ) cho các sản phẩm loại I và II.
Phương pháp đồ thị
Phương pháp đồ thị có ý nghĩa minh hoạ và giúp hiểu bản chất vấn đề.
Bước 1: Vẽ miền ràng buộc / miền các phương án khả thi, là tập hợp các phương án
khả thi (các phương án, nếu nói một cách ngắn gọn). Mỗi phương án được thể hiện qua bộ
số (x1, x2) còn gọi là véc tơ nghiệm, thoả mãn tất cả các ràng buộc đã có (xem hình I.1).
− Trước hết chúng ta vẽ đồ thị 4×1 + 2×2 = 60 bằng cách xác định hai điểm trên đồ
thị: (x1 = 0, x2 = 30) và (x2 = 0, x1 = 15).

x2
30
4×1 + 2×2 = 60
12

A

8

B
2×1 + 4×2 = 48

4
C
O

3

6

15

24

x1

Hình I.1. Phương pháp đồ thị giải bài toán quy hoạch tuyến tính

8

Đồ thị trên là một đường thẳng chia mặt phẳng làm hai nửa mặt phẳng: một phần
gồm các điểm (x1, x2) thoả mãn 4×1 + 2×2 ≤ 60; một phần thoả mãn 4×1 + 2×2 ≥ 60. Ta
tìm được nửa mặt phẳng thoả mãn 4×1 + 2×2 ≤ 60.
− Tương tự, có thể vẽ đồ thị 2×1 + 4×2 = 48 bằng cách xác định hai điểm thuộc đồ
thị (x1 = 0, x2 = 12) và (x2 = 0, x1 = 24). Sau đó tìm nửa mặt phẳng thoả mãn 2×1 + 4×2 ≤ 48.
− Lúc này, giao của hai nửa mặt phẳng tìm được trên cho ta tập hợp các điểm (x1, x2)
thoả mãn hai ràng buộc đầu tiên. Tuy nhiên, để thoả mãn điều kiện không âm của các
biến, ta chỉ xét các điểm nằm trong góc phần tư thứ nhất. Vậy miền các phương án khả
thi là miền giới hạn bởi tứ giác OABC (còn gọi là đơn hình vì là miền tạo nên bởi giao
của các nửa mặt phẳng).
Bước 2: Trong miền (OABC) ta tìm điểm (x1, x2) sao cho
z = 8×1 + 6×2 đạt giá trị lớn nhất.
Cách 1: Dùng đường đồng mức. Tùy theo giá trị của x1, x2 mà z có những mức giá
trị khác nhau.
− Vẽ đường đồng mức: 8×1 + 6×2 = c ở mức c = 24, (ta có thể chọn giá trị c bất kì,
nhưng chọn c = 24 là bội số chung của 6 và 8 để việc tìm toạ độ các điểm cắt hai trục toạ
độ thuận lợi hơn). Dễ dàng tìm được hai điểm nằm trên đường đồng mức này là (x1 = 0,
x2 = 4) và (x2 = 0, x1 = 3). Các điểm nằm trên đường đồng mức này đều cho giá trị hàm
mục tiêu z = 24.
− Tương tự, có thể vẽ đường đồng mức thứ hai: 8×1 + 6×2 = 48 đi qua hai điểm (x1 = 0,
x2 = 8) và (x2 = 0, x1 = 6). Chúng ta nhận thấy, nếu tịnh tiến song song đường đồng mức
G
lên trên theo hướng của véc tơ pháp tuyến n (8, 6) thì giá trị của hàm mục tiêu z = 8×1 + 6×2
tăng lên.

Vậy giá trị z lớn nhất đạt được khi đường đồng mức đi qua điểm B(12, 6) (tìm
được x1 = 12, x2 = 6 bằng cách giải hệ phương trình 4×1 + 2×2 = 60 và 2×1 + 4×2 = 48).
Kết luận: Trong các phương án khả thi thì phương án tối ưu là (x1 = 12, x2 = 6). Tại
phương án này, giá trị hàm mục tiêu là lớn nhất zmax = 8 × 12 + 6 × 6 = 132.
Nhận xét: Phương án tối ưu của bài toán trên (hay các BTQHTT khác, nếu có) luôn
đạt được tại một trong các đỉnh của đơn hình hay còn gọi là các điểm cực biên của đơn
hình (chính xác hơn, điểm cực biên là điểm thuộc đơn hình, mà không thể tìm được một
đoạn thẳng nào cũng thuộc đơn hình nhận điểm đó là điểm trong). Nhận xét trên đây là
một định lí toán học đã được chứng minh một cách tổng quát. Nói một cách hình ảnh,
muốn đạt được phương án tối ưu cho các BTQHTT thì cần phải “mạo hiểm” đi xét các
điểm cực biên của miền phương án.
Cách 2: Từ nhận xét trên, để tìm phương án tối ưu ta chỉ cần so sánh giá trị của
hàm mục tiêu tại các điểm cực biên của miền phương án.

Tính giá trị z tại O(0, 0): z(0, 0) = 0; tại A(0, 12): z(0, 12) = 72; tại C(15,0): z(15, 0)
= 120; tại B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. Vậy zmax = 132.

9

Nhận xét: Muốn tìm phương án tối ưu của BTQHTT ta xuất phát từ một điểm cực
biên nào đó, tìm cách cải thiện hàm mục tiêu bằng cách đi tới điểm cực biên kề nó. Tiếp
tục như vậy cho tới khi tìm được phương án tối ưu. Trong trường hợp BTQHTT có
phương án tối ưu thì quy trình giải này bao gồm hữu hạn bước (do số điểm cực biên là
hữu hạn).

Đối với BTQHTT đang xét, quy trình giải được minh hoạ như sau:
O(0, 0)

→

A(0,12)

→

B(12,6) dừng

z=0

→

z = 72

→

z = 132

O(0, 0)

→

C(15, 0)

→

B(12, 6) dừng

z=0

→

z = 120

→

z = 132

hoặc:

Sơ đồ khối

Bắt đầu

Nhập dữ liệu

Tìm điểm cực biên
xuất phát

Kiểm tra
điều kiện tối ưu

Sai

Đúng
In và lưu trữ kết quả

Dừng
Hình I.2. Sơ đồ khối giải BTQHTT

10

Tìm
điểm cực biên
kề tốt hơn

Source: https://mindovermetal.org
Category: Ứng dụng hay