Thuyết trình: q nêu Các yêu cầu của 1 bài toán quy hoạch tuyến tính, xây dựng bài toán quy hoạch tuyến tính, cách giải bài toán quy hoach tuyến tính bằng đồ thị, thể hiện các ràng buộc trên đồ thị ,phương pháp giải dùng đường đẳng nhuận, phương pháp góc - điểm.
AMBIENT/
Chủ đề:
Nội dung Text: Thuyết trình: Quy hoạch tuyến tính
- Quy Hoạch
Tuyến Tính
Linear Programming
GVHD: TS. Phạm Văn Lâm
Nhóm 8
Bùi Hồng Ngọc
Nguyễn Văn Thuận
Phan Thanh Hải
Hồ Nguyễn Phước Thành
Lê Nguyên Khôi
© 2008 Prentic e Hall, Inc . B–1
- Nội dung
Các yêu cầu của 1 bài toán Quy
Hoạch Tuyến Tính
Xây dựng bài toán Quy Hoạch
Tuyến Tính
Ví dụ về Shader Electronics
© 2008 Prentice Hall, Inc . B–2
- Nội dung
Cách giải bài toán Quy Hoach
Tuyến Tính bằng đồ thị
Thể hiện các Ràng buộc trên đồ thị
Phương pháp giải dùng Đường
Đẳng Nhuận
Phương pháp Góc-Điểm
© 2008 Prentice Hall, Inc . B–3
- Nội dung
Phân tích mức độ nhạy cảm
Bản mô tả mức độ nhạy cảm
Thay đổi giá trị nguồn lực phía bên
phải.
Thay đổi hệ số hàm mục tiêu
Giải bài toán Tối thiểu hóa
© 2008 Prentice Hall, Inc . B–4
- Nội dung
Ứng dụng Bài toán Quy Hoạch
Tuyến Tính
Bài toán Kết hợp sản xuất
Bài toán về chế độ thức ăn
Bài toán về kế hoạch làm việc nhân
công
Phương pháp đơn hình
© 2008 Prentic e Hall, Inc . B–5
- Mục tiêu
Khi hoàn thành, bạn sẽ có khả năng:
1. Xây dựng các mô hình bài toán LP,
gồm một hàm mục tiêu và hệ ràng
buộc.
2. Giải bài toán bằng đồ thị, dung
phương pháp Đường đẳng nhuận.
3. Giải bài toán bằng đồ thị, dùng
phương pháp Góc-Điểm.
© 2008 Prentic e Hall, Inc . B–6
- Mục tiêu
Khi hoàn thành, bạn có thể:
4. Phân tích độ nhạy và các mức giá ảo
5. Xây dựng và giải bài toán Tối thiểu
hóa (minimization)
6. Xây dựng bài toán Kết hợp sản xuất,
bài toán Chế độ thức ăn, và bài toán
Kế hoạch làm việc cho nhân công.
© 2008 Prentice Hall, Inc . B–7
- Quy Hoạch Tuyến Tính (LP)
Một phương pháp toán học giúp
lên kế hoạch và ra các quyết
định về bố trí các nguồn lực.
Giúp tìm ra giá trị tối đa hoặc tối
thiểu của đối tượng.
Đảm bảo cách giải quyết tối ưu
cho mô hình được xây dựng.
© 2008 Prentic e Hall, Inc . B–8
- Các ứng dụng của LP
1. Lên lịch chạy cho xe buýt trường học
để giảm thiểu tổng quãng đường di
chuyển.
2. Bố trí các đơn vị tuần tra cảnh sát đến
những khu tội phạm trọng điểm để
giảm thiểu thời gian trả lời các cuộc
gọi 911
3. Lên kế hoạch làm việc cho Giao dịch
viên tại các ngân hàng nhằm đáp ứng
nhu cầu trong mọi thời điểm trong khi
giảm thiểu chi phí nhân công.
© 2008 Prentic e Hall, Inc . B–9
- Các ứng dụng của LP
4. Lựa chọn kết hợp sản phẩm tại 1 nhà
máy để sử dụng hiệu quả nhất các thiết
bị máy móc trong khi tối đa hóa lợi
nhuận.
5. Pha trộn nguyên liệu trong máy nghiền
thức ăn để tạo ra hỗn hợp thức ăn với
chi phí thấp nhất
6. Quyết định hệ thống phân phối sao cho
chi phí vận chuyển ở mức thấp nhất
© 2008 Prentic e Hall, Inc . B – 10
- Các ứng dụng của LP
7. Xây dựng quy trình sản xuất thỏa mãn
nhu cầu tương lai về sản phẩm của 1
doanh nghiệp đồng thời tối thiểu hóa
chi phí sản xuất và chi phí tồn kho
8. Phân bố không gian kết hợp cho các
khách thuê trong một trung tâm
thương mại để tối đa hóa doanh thu
cho một công ty chuyên cho thuê bất
động sản.
© 2008 Prentic e Hall, Inc . B – 11
- Các yêu cầu của một bài toán LP
1. Bài toán LP hướng đến việc tối đa
hóa hoặc Tối thiểu hóa một giá trị
nào đó (thường là lợi nhuận hoặc
chi phí). Đây là Hàm Mục Tiêu.
2. Các Ràng buộc (Constraint) giới
hạn mức độ của mục tiêu mà ta có
thể theo đuổi.
© 2008 Prentic e Hall, Inc . B – 12
- Các yêu cầu của bài toán LP
3. Phải có các phương án hành động
thay thế để doanh nghiệp lựa
chọn.
4. Mục tiêu và Các ràng buộc trong
bài toán LP phải được mô tả dưới
dạng phương trình tuyến tính hay
bất đẳng thức.
© 2008 Prentic e Hall, Inc . B – 13
- Xây dựng bài toán LP
Bài toán kết hợp sản phẩm tại Shader Electronics
Hai sản phẩm
1. Shader Walkman
2. Shader Watch - TV
Quyết định cách phối hợp các sản
phẩm để tạo ra lợi nhuận cao nhất
© 2008 Prentic e Hall, Inc . B – 14
- Xây dựng bài toán LP
Số giờ cần thiết
để sx 1 đv sp
Walkman Watch TV Số giờ
Bộ phận (X1) (X2) có trong tuần
Kĩ thuật điện tử 4 3 240
Lắp ráp 2 1 100
Lợi nhuận của
1 đv sp $7 $5
Các biến số quyết định:
X1 = số lượng Walkman cần sx
X2 = số lượng Watch-TV cần sx
© 2008 Prentic e Hall, Inc . B – 15
- Xây dựng bài toán LP
Hàm mục tiêu:
Tối đa hóa lợi nhuận = $7X1 + $5X2
Có 3 loại ràng buộc
Cận trên quy định nguồn lực sử dụng ≤
nguồn lực hiện có
Cận dưới quy định nguồn lực sử dụng ≥
nguồn lực hiện có
Đẳng thức thể hiện nguồn lực sử dụng =
nguồn lực hiện có
© 2008 Prentic e Hall, Inc . B – 16
- Xây dựng bài toán LP
Ràng buộc 1:
Thời gian sx kĩ thuật Thời gian sx điện tử
điện tử dùng đến ≤ có sẵn
4X1 + 3X2 ≤ 240 (số giờ của sx điện tử)
Ràng buộc 2:
Thời gian lắp ráp Thời gian lắp ráp
dùng đến ≤ có sẵn
2X1 + 1X2 ≤ 100 (số giờ lắp ráp)
© 2008 Prentic e Hall, Inc . B – 17
- Cách giải bằng đồ thị
Có thể dùng khi có 2 biến số quyết định
1. Phác họa các phương trình giới hạn tại các
mức giới hạn bằng cách chuyển các
phương trình thành đẳng thức.
2. Xác định miền khả thi
3. Xác định một đường đẳng nhuận (đường thể
hiện lợi nhuận bằng nhau) dựa trên hàm
mục tiêu.
4. Di chuyển đường này ra ngoài cho đến khi
xác định được điểm tối ưu
© 2008 Prentic e Hall, Inc . B – 18
- Cách giải bằng đồ thị
X2
100 –
–
80 –
Lắp ráp (Ràng buộc B)
Số lượng Watch-TV
–
60 –
–
40 –
– Điện tử (Ràng buộc A)
20 – Miền khả
thi
–
|
– | | | | | | | | | | X1
0 20 40 60 80 100
Số lượng Walkman
© 2008 Prentic e Hall, Inc . B – 19
- Cách giải bằng đồ thị
Phương pháp sử dụng đường đẳng nhuận
(Iso-Profit Line)
Chọn 1 giá trị khả thi cho hàm mục tiêu
$210 = 7X1 + 5X2
Tìm ra trục chặn của hàm và vẽ ra
X2 = 42 X1 = 30
© 2008 Prentic e Hall, Inc . B – 20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
