2_CHUONG 2 - MO HINH QUY HOACH TUYEN TINH - GV.pdf

PHÂN TÍCH LOGISTICS SLIDE

1. Phân tích Logistics
Chương 2: Mô hình Quy hoạch Tuyến tính
1

2. Trong chương 1…
•Tiếp cận bài toán quyết định bằng mô hình
•Các mô hình toán học và phân loại
•Quy trình phân tích và xử lý vấn đề
2

3. Logistics
Nguyên
liệu
Sản
xuất
Kho
hàng
Vận tải/
phân
phối
…
3

4. Ví dụ bài toán Logistics
Công ty Việt Nhật sản xuất 2 loại tủ quần áo
Tủ Việt NamTủ Nhật Bản
Lợi nhuận/SP
bán ra
7 triệu đồng5 triệu đồng
àCần sản xuất bao nhiêu tủ quần áo mỗi loại để
đạt lợi nhuận tối đa?
Nhân công (giờ)96
Gỗ (thanh)1216
Công ty có sẵn
1000
2000
4

5. Ví dụ bài toán Logistics (tt)
Công ty Việt Nhật muốn vận chuyển các thanh
gỗ từ kho gỗ đến các xưởng gia công
2 kho gỗ: Long An và Tiền Giang
2 xưởng gia công: HCM và Bình Dương
5

6. Ví dụ bài toán Logistics (tt)
Long
An
Tiền
Giang
HCM
Bình
Dương
Khoảng cách (km)Công suấtSố thanh gỗ
400
600 700
300
Kho gỗ Gia công
40
80
60
120
à Cần vận chuyển bao nhiêu gỗ từ mỗi kho
đến mỗi xưởng gia côngà tối thiểu chi phí
6

7. Các bài toán Logistics
àTối đa lợi nhuận
àTối thiểu chi phí
àTối thiểu quãng đường
àTối ưu lượng sản xuất/ đặt hàng
àTối ưu không gian kho/ tàu chở
à...
Tối ưu hóa
7

8. Mục tiêu chương
•Trình bày được mục tiêu của việc tối ưu hóa
•Phân tích được mô hình Quy hoạch tuyến
tính (Linear Programming – LP)
•Xây dựng được mô hình máy tính cho các
bài toán LP
•Thực hiện được các bài toán LP trên Excel
•Vận dụng được mô hình LP để giải quyết các
vấn đề Logistics
8

9. Nội dung chương
1.Tối ưu hóa và Quy hoạch Tuyến tính (LP)
2.Ví dụ bài toán LP cơ bản
3.Thực hành giải bài toán LP trên máy tính
4.Vận dụng LP vào giải quyết các vấn đề
Logistics
9

10. 1.1 Tại sao phải tối ưu hóa?
•Các nguồn tài nguyên/ nguồn lực là hữu hạn:
•Khoáng sản (dầu mỏ/ các loại quặng,…)
•Đất đai, kho bãi, sức chứa tàu hàng/ xe tải,…
•Thời gian
•Tiền bạc
•Nhân lực,…
à quyết định cách sử dụng/ phân bố hiệu
quả nhất (MAX lợi nhuận, MIN chi phí,…)
10

11. 1.2 Ứng dụng toán tối ưu
•Xác định tổ hợp sản phẩm cần sản xuất
•Cải thiện công suất
•Định tuyến
•Vận tải
•Hoạch định tài chính
Tối ưu hóaQuy hoạch tuyến tính
11

12. 1.3 Quy hoạch Tuyến tính là gì?
Là 1 phương pháp tối ưu hóa nhằm chọn ra 1
tổ hợp/ 1 chuỗi thao tác hiệu quả nhất để đạt
được mục tiêu
mà trong đó
tất cả những mối quan hệ toán học giữa các
biến số trong hàm mục tiêu và trong các hạn
chế là quan hệ tuyến tính
12

13. 1.3 Quy hoạch Tuyến tính là gì? (tt)
“Tuyến tính” à là các hàm số mà mỗi biến trong
đó đều có bậc 1, và được cộng lại với nhau
!!"","#,…,"$ ='"""+'#"#+⋯+'$"$
*%∶các biến số ở bậc 1
7%∶các hằng số,có thể=0
13

14. 1.4 Các yếu tố trong mô hình LP
•Biến quyết định (Decisions/ Decision
variables): thường ký hiệu là !!,!",…,!#
•Ràng buộc (hạn chế) cần được thỏa mãn
$!!,!",…,!#≤&
$!!,!",…,!#≥&
$!!,!",…,!#=&
14

15. 1.4 Các yếu tố trong mô hình LP
(tt)
•Mục tiêu: (MIN/ MAX)
$$!!,!",…,!#
•Ràng buộc: cần được thỏa mãn
$!!!,!",…,!#≤&!$%!!,!",…,!#≥&%$&!!,!",…,!#=&&
15

16. 1.4 Các yếu tố trong mô hình LP
(tt)
Hàm mục tiêu: (Objective)
* =+!!!++"!"+⋯++'!# à MIN/ MAX
Ràng buộc: (Constraints)
.!!!!+.!"!"+⋯+.!#!#≤&!.%!!!+.%"!"+⋯+.%#!#≥&%.&!!!+.&"!"+⋯+.&#!#=&&
16

17. 1.5 Các nghiệm đặc biệt
Đa nghiệm tối ưu (alternate optimal
solutions)
à Có nhiều hơn 1 nghiệm/ Giải pháp (GP) tối
ưu
Vô nghiệm (infeasible solutions)
à Không có nghiệm/GP nào thõa mãn được
tất cả các ràng buộc
17

18. 1.5 Các nghiệm đặc biệt (tt)
Vô số nghiệm (unbounded solutions)
à Rất có thể mô hình đang gặp vấn đề (thiếu
ràng buộc, sai dấu…) và cần được xem xét lại.
18

19. Nội dung chương
1.Tối ưu hóa và Quy hoạch Tuyến tính (LP)
2.Ví dụ bài toán LP cơ bản
3.Thực hành giải bài toán LP trên máy tính
4.Vận dụng LP vào giải quyết các vấn đề
Logistics
19

20. 2.1 Quy trình lập bài toán LP
1. Đọc – hiểu vấn đề cần giải quyết
2.Xác định mục tiêu
3.Xác định các ràng buộc
4.Xác định các biến quyết định
5.Viết ra hàm mục tiêu dưới dạng tổ hợp
tuyến tính của các biến quyết định
6.Viết ra các ràng buộc dưới dạng tổ hợp
tuyến tính của các biến quyết định
20

21. Ví dụ 1: Bồn tắm
Tóm tắt bài toán
1 bơm
9 giờ nhân công
12 ft ống nước
1 bơm
9 giờ nhân công
16 ft ống nước
200 bơm
1566 giờ nhân công
2880 ft ống nước
Cần sản xuất bao
nhiêu
Aqua-Spas?
Hydro-Luxes?
à MAX lợi nhuận
Aqua-Spa $350Hydro-Lux $300
21

22. Ví dụ 1: Bồn tắm (tt)
Bước1: Hiểu cặn kẽ vấn đề cần giải quyết
MAX
Lợi
nhuận
Lợi nhuận
Aqua-Spa
Lợi nhuận
Hydro-Lux
Số lượng
Aqua-Spa
Số lượng
Hydro-Lux
Số bơm
nước
Số giờ
nhân công
Số feet ống
dẫn
22

23. Ví dụ 1: Bồn tắm (tt)
Bước 2: Xác định mục tiêu
MAX ? à MAX lợi nhuận/ doanh thu…
MIN ? à MIN chi phí/ quãng đường…
23

24. Ví dụ 1: Bồn tắm (tt)
Bước 3: Xác định các ràng buộc
Loại bồn tắmAqua-SpaHydro-LuxRàng buộc
Lợi nhuận/ SP$ 350$ 300-
Số bơm/ SP11200
Nhân công/ SP9 61566
Số ft ống/ SP12162880
24

25. Ví dụ 1: Bồn tắm (tt)
Bước4: Xác định các biến quyết định
Gọi: /( = SL bồn Aqua-Spa cần SX
/) = SL bồn Hydro-Lux cần SX
25

26. Ví dụ 1: Bồn tắm (tt)
Bước5: Viết hàm mục tiêu dưới dạng mô
hình LP
MAX: !=#$%&0+#%%&1
Aqua- Spa !! Hydro-Lux !"
Lợi nhuận/ SP$ 350$ 300
26

27. Ví dụ 1: Bồn tắm (tt)
Bước6: Viết các ràng buộc dưới dạng mô
hình LP
Loại bồn tắmAqua- Spa
!!
Hydro-Lux
!"
Ràng buộc
Số bơm/ SP1 1 #!!+#!"≤&''
Nhân công/ SP96(!!+)!"≤#*))
Số ft ống/ SP1216#&!!+#)!"≤&++'
Lưu ý: Xác định mọi giới hạn trên hoặc giới hạn dưới
của các biến quyết định à !!≥#
27

28. Ví dụ 1: Bồn tắm (tt)
Bước6: Viết các ràng buộc dưới dạng LP
Mô hình tuyến tính
Hàm mục tiêu: $%! '=)*#!"+)##!#
Các ràng buộc: ,$+,%≤200
9,$+6,%≤1566
12,$+16,%≤2880
,&≥0
,&=567 (5679:9;/=ố 6:?@ê6)
28

29. 2.2 Giải LP - Phương pháp trực giác
Aqua-Spa lời nhiều hơnà sản xuất 100% !!
Hàm mục tiêu: "=350!!+300(0)
Các ràng buộc: !!≤200
9!!≤1566 → !!≤174
12!!≤2880 → !!≤240
!"=0,!!=174Max
"=350174+3000
"=$ 60,900 à Khả thi
Nhưngcótốiưukhông?

29

30. 2.3 Giải LP - Phương pháp đồ thị (tự
học)
Nghiên cứu tài liệu [1] từ trang 25 - 31
2-10 Solving LP Problems: A Graphical Approach
Kết hợp
Nghiên cứu video tại đây
(bật “cc”/ dịch sang Tiếng Việt)
30

31. Nội dung chương
1.Tối ưu hóa và Quy hoạch Tuyến tính (LP)
2.Ví dụ bài toán LP cơ bản
3.Thực hành giải bài toán LP trên máy tính
4.Vận dụng LP vào giải quyết các vấn đề
Logistics
31

32. 3.1 Giải bài toán LP trên máy tính
Bước1: Viết vấn đề dưới dạng bài toán LP
Bước2: Trình bày dữ liệu của bài toán trên
Excel
Bước3: Tạo công thức trong các ô tương ứng
với mục tiêu/ các ràng buộc
Bước4: Dùng SOLVER à trình bày kết quả
32

33. 3.1 Ví dụ 1 – Bồn tắm (Excel)
Bước1: Viết vấn đề dưới dạng bài toán LP
!! = Số lượng bồn Aqua-Spa cần SX
!" = Số lượng bồn Hydro-Lux cần SX
Hàm mục tiêu: #$% &=350%#+300%$Các ràng buộc: %#+%$≤200
9%#+6%$≤1566
12%#+16%$≤2880
%%≥0
%%=345 (3457879/;ố 48=>ê4)
33

34. 3.1 Ví dụ 1 – Bồn tắm (Excel)
Vùng chứa biến X1, X2
vùng mục tiêu Z
Vùng giá trị bên trái
của các ràng buộc
Bước2: Trình bày trên Excel
34

35. 3.1 Ví dụ 1 – Bồn tắm (Excel)
Bước3: Lập công thức
=SUMPRODUCT(B5:C5,B6:C6)
=SUMPRODUCT(B5:C5,B9:C9)
=SUMPRODUCT(B5:C5,B10:C10)
=SUMPRODUCT(B5:C5,B11:C11)
35

36. 3.1 Ví dụ 1 – Bồn tắm (Excel)
vùng mục tiêu Z
MAX hay MIN?
Vùng chứa biến
Thêm ràng buộc
Phương pháp LP
Bước4: SOLVER
36

37. 3.1 Ví dụ 1 – Bồn tắm (Excel)
37

38. 3.2 Thực hành giải LP trên Excel
8 nhóm
3 nhóm thực hành chung 1 bài toán
Bibbins (Nhóm 1, 2)
Gourmet Grill (Nhóm 3, 4)
Mountain Mist (Nhóm 5, 6)
PC Express (Nhóm 7, 8)
38

39. Nội dung chương
1.Mô hình Quy hoạch Tuyến tính (LP)
2.Ví dụ bài toán LP với 2 biến
3.Giải bài toán LP trên Excel
4.Áp dụng LP vào phân tích các vấn đề
Logistics
39

40. Cảm ơn!
40