Download miễn phí Giáo trình Tin học trong quản lý xây dựng
Đôi khi, bài toán QHTT sẽkhông cho ta lời giải hữu hạn. Điều
này có nghĩa là trong bài toán QHTT cực đại hóa, gồm có một hay
nhiều biến, giá trịcủa hàm mục tiêu (lợi nhuận) có thểtiến đến lớn vô
cùng mà không vi phạm bất cứràng buộc nào cả. Nếu chúng ta giải
bài toán loại này bằng phương pháp đồthị, chúng ta sẽthấy miền
nghiệm khảthi là một miền mởkhông giới hạn (open-ended)®Bài
toán mở. Ngược lại, trong bài toán QHTT cực tiểu hóa, giá trịcủa
hàm mục tiêu (chi phí
có thểtiến đến nhỏvô cùng mà không vi phạm bất cứràng buộc nào cả.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
áo hay một tập danh mụcđầu tư sẽ bị giới hạn bởi tổng số tiền sẵn có để đầu tư.
+ Trong bài toán vận tải, việc cực tiểu hóa chi phí vận tải sẽ bị ràng
buộc bởi khả năng cung cấp của các nhà máy cũng như nhu cầu
tại các nơi tiêu thụ.
Vì vậy, chúng ta thường muốn cực đại hóa hay cực tiểu hóa các
đại lượng (hàm mục tiêu) trong điều kiện giới hạn về tài nguyên (các
điều kiện ràng buộc).
2.3. Phải có các phương án để lựa chọn (There must be
alternatives available).
Có một công ty sản xuất 3 loại sản phẩm khác nhau. Có thể công
ty tập trung sản xuất chủ yếu một trong 3 sản phẩm hay sản xuất đều 3
loại sản phẩm, hay phân bổ ở một tỷ lệ bất kỳ nào đó? Nhà quản lý
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 243
có thể sử dụng QHTT để xác định tỷ lệ phân bổ của chúng trong điều
kiện giới hạn về tài nguyên sản xuất (máy móc, công nhân,…) để cực
đại lợi nhuận. Nếu chỉ có một phương án, chúng ta không cần QHTT.
2.4. Hàm mục tiêu và các ràng buộc đều là hàm tuyến tính.
Dạng ràng buộc có thể là:
+ Bất phương trình có dạng “£” hay “³”;
+ Phương trình “=”.
Hàm tuyến tính có nghĩa là số mũ của các biến quyết định phải ở
dạng bậc nhất (không được là bậc 2, bậc 3 hay các bậc khác 1). Ví dụ:
+ Phương trình 2a+ 5b = 10 là phương trình tuyến tính, trong khi
đó 2a2 + 5b3 + 3ab = 10 không phải là phương trình tuyến tính
bởi vì biến a có bậc là 2, biến b có bậc là 3 và tích a.b cũng
không khả thi .
+ Hàm mục tiêu Z = 10x1 + 9x2 là hàm tuyến tính, trong khi đó
2
1 2Z 10x 9 x= + không phải là hàm tuyến tính.
Chúng ta thường gặp các dạng ràng buộc bất phương trình khi
giải các bài toán QHTT. Điều này có nghĩa là các ràng buộc không
phải lúc nào cũng có dạng phương trình A + B = C.
Các nhà khoa học quản lý đã nghiên cứu và tìm ra lời giải của rất
nhiều các mô hình toán học bao gồm một hàm mục tiêu và một tập các
ràng buộc. Các mô hình này được gọi là các mô hình quy hoạch toán
học (mathematical programming models). Mô hình QHTT là một
dạng đặc biệt của các mô hình quy hoạch toán học, trong đó hàm mục
tiêu và các ràng buộc đều là hàm tuyến.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 244
3. CÁC GIẢ THIẾT CƠ BẢN CỦA QUY HOẠCH TUYẾN
TÍNH
Thông thường các mô hình toán ứng dụng trong kinh tế đều có
các giả thiết đi kèm. Vậy tại sao phái sử dụng các giả thiết? Câu trả lời
là vì rất khó để có mô hình toán học nào mô tả một cách hoàn toàn
chính xác đến chi tiết trong các tình huống thực tế và nếu có thì mô
hình đó sẽ rất phức tạp. Vì vậy, để mô hình được đơn giản hóa (nhưng
vẫn phải đảm bảo không mất đi tính thực tế của bài toán), chúng ta
cần có các giả thiết đi kèm.
Có 5 giả thiết/yêu cầu cơ bản cần nắm khi giải các bài toán
QHTT:
1. Tính chắc chắn (Certainty): Các con số trong hàm mục tiêu và
các điều kiện ràng buộc được biết chắc chắn và không thay đổi
trong suốt quá trình nghiên cứu.
2. Tính tỷ lệ (Proportionality): Chúng ta phải giả thiết có tính tỷ lệ
tồn tại trong hàm mục tiêu và các ràng buộc. Nghĩa là sự đóng góp
đối với hàm mục tiêu và giá trị tài nguyên trong mỗi ràng buộc phải
tỷ lệ với giá trị của các biến quyết định.
Ví dụ như nếu sản xuất một sản phẩm mất 3 giờ thì sản xuất 10 sản
phẩm sẽ mất 30 giờ.
3. Tính cộng dồn (Additivity): Giá trị của hàm mục tiêu và tổng tài
nguyên sử dụng được tính toán bằng cách lấy tổng hàm mục tiêu
đóng góp và tài nguyên sử dụng của tất cả các biến quyết định.
Nghĩa là tổng các hoạt động sẽ bằng kết quả cộng dồn của từng hoạt
động riêng rẽ.
Ví dụ: Nếu có mục tiêu là cực đại hóa lợi nhuận bằng 8 USD của
sản phẩm 1 + 3 USD của sản phẩm 2 thì khi một sản phẩm được
sản xuất, lợi nhuận tổng cộng sẽ là 8 + 3 = 11 USD.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 245
4. Tính chia được (Divisibility): Biến quyết định là biến liên tục.
Giả thiết này chấp nhận các nghiệm số ở dạng thập phân (Lời giải
không nhất thiết phải là số nguyên). Nghĩa là có thể chấp nhận giá
trị như 1/3 cái bàn được sản xuất.
5. Tính không âm (Nonnegative): Tất cả các biến phải không âm.
Sử dụng các con số âm để đếm là không thể. Bạn không thể sản
xuất một số âm cái bàn, cái ghế, cái đèn, hay máy tính… được.
Bảng 4.1 sau đây trình bày tóm tắt các đặc điểm và giả thiết cơ
bàn của bài toán QHTT:
Bảng 4.1. Các đặc điểm và giả thiết cơ bản của bài toán QHTT
4 đặc điểm của QHTT 5 giả thiết của bài toán QHTT
1. Hàm mục tiêu;
2. Các ràng buộc;
3. Các phương án lựa chọn;
4. Hàm mục tiêu và các ràng
buộc là hàm tuyến tính.
1. Tính chắc chắn
2. Tính tỷ lệ
3. Tính cộng dồn
4. Tính chia được
5. Tính không âm
4. THÀNH LẬP BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Thành lập một bài toán QHTT liên quan đến việc xây dựng một
mô hình toán (mathematical model) để diễn tả vấn đề quản lý. Vì
vậy, để thành lập một bài toán QHTT, chúng ta cần hiểu một
cách sâu sắc vấn đề quản lý đang phải đối mặt. Khi đã nắm rõ,
chúng ta có thể bắt đầu xây dựng mô hình toán cho vấn đề. Việc thành
lập một bài toán QHTT bao gồm các bước sau đây:
1. Hiểu rõ vấn đề quản lý đang phải đối mặt.
2. Xác định hàm mục tiêu và các ràng buộc.
3. Định nghĩa các biến ra quyết định.
4. Sử dụng các biến ra quyết định để viết các mô hình toán cho hàm
mục tiêu và các ràng buộc.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Chương 4 - QUY HOẠCH TUYẾN TÍNH (LINEAR PROGRAMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 246
Một trong những ứng dụng phổ biến của QHTT là bài toán kế
hoạch sản xuất nhiều sản phẩm (Product mix problem). Hai hay
nhiều sản phẩm được sản xuất trong điều kiện giới hạn về tài nguyên
như lao động, máy móc, nguyên vật liệu…Lợi nhuận mà công ty
muốn cực đại được dựa trên lợi nhuận đóng góp của mỗi đơn vị sản
phẩm. Công ty sẽ phải quyết định sản xuất bao nhiêu sản phẩm mỗi
loại để cực đại hóa tổng lợi nhuận trong phạm vi cho phép về tài
nguyên.
Ví dụ về cách thành lập 1 bài toán QHTT: Công ty sản xuất nội
thất Phương Nam
Công ty Phương Nam sản xuất các loại bàn và ghế gỗ rẻ tiền.
Quy trình sản xuất của mỗi sản phẩm đều có điểm chung là cùng trải
qua công đoạn đóng mộc (carpentry work) và sơn, đánh bóng
(painting and varnishing):
- Mỗi cái bàn cần 4 giờ đóng mộc, 2 giờ sơn và đánh bóng.
- Mỗi cái ghế cần 3 giờ đóng mộc, 1 giờ sơn và đánh bóng.
Trong giai đoạn sản xuất hiện tại, chu kỳ 1 tuần, với lực lượng
công nhân lao động hiện có, công ty Phương Nam có tổng cộng 240
giờ đóng m...