Chương 9: Hoạch định bằng chương trình tự động

Trong chương này chúng ta quan tâm đến trường hợp đặc biệt: toàn bộ số sản phẩm tậphợp trong chỉ một họ. Trong trường hợp này, có thể ước tính trực tiếp giá thành sản xuất hoặctồn kho cua 1 sô x, san phâm dua vào trung bình sản xuất cần thiết. Cac ràng buộc truoc dây nhưsố giờ bổ sung, sự thầu lại vv....duoc ngâm tinh chung trong gia.
Nội dung trích xuất từ tài liệu:
Chương 9: Hoạch định bằng chương trình tự động CHƯƠNG 9: Hoạch định bàng chuong trinh động Trong chương này chúng ta quan tâm đến trường hợp đặc biệt: toàn bộ số sản phẩm tậphợp trong chỉ một họ. Trong trường hợp này, có thể ước tính trực tiếp giá thành sản xuất hoặctồn kho cua 1 sô x, san phâm dua vào trung bình sản xuất cần thiết. Cac ràng buộc truoc dây nhưsố giờ bổ sung, sự thầu lại vv....duoc ngâm tinh chung trong gia. 9.1 Thuật toán cho trường hợp tông quat 9.1.1 Ví dụ: Xí nghiệp AKL là một công ty con của một nhà xây dựng hàng không lớn. Nó laprap và kiểm tra những modun điện tử sử dụng trong thiêt bi diêu khiên máy bay. Vìnhững lý do gắn với giá thành, sản xuất có thể từ 10 đến 16 thiết bị. Cũng vậy, vi phaico 1 luong hàng tồn kho an toàn và do kích cỡ cua kho, sô luong này nằm trong khoảngtù 3 dên 6. Không được phép thiếu hụt. Yêu cầu trong 6 tháng tới là: 9 17 14 18 11 17 thiết bị. Nêu tính số giờ bổ sung và cóthể goi thêm 1 công ty gia công, thi chi phí sản xuất CF(x) của x thiết bị (ngoài trù gianguyên vât liêu và linh kiên) là: x 10 11 12 13 14 15 16 CF(x) 20 22 25 30 33 37 40 Chi phí tồn kho hàng tháng là x 3 4 5 6 CS(x) 2 3 5 7 Số hàng tồn kho ban đầu là 3 đơn vị và người ta dinh se dat số hàng tồn kho cuốikỳ thứ 6 là 4. Chung ta phai xac dinh sô luong Xi thiết bị cân sản xuất trong tháng thứ i và voi muctiêu là tối thiểu hoa tổng số chi phí sản xuất và chi phí tồn kho. Ở đây, nhận thấy sự quantrọng của việc sản xuất, không thể xấp xỉ kết quả bằng một số thực mà chúng ta pháilàm việc bằng những số nguyên. Như trong chương trước, chúng ta thê m các biến Si làmức tồn kho vào cuối tháng i. Ta thấy dễ dàng: 6 Min ∑ [CF(Xi) + CS(Si)] i=1 Với những ràng buộc: 10 ≤ Xi ≤ 16 3 ≤ Si ≤ 6 S0 = 3 S6 = 4 X 1 + S 0 = S1 + 9 X2 + S1 = S2 + 17 X3 + S2 = S3 + 14 X4 + S3 = S4 + 18 X5 + S4 = S5 + 11 X6 + S5 = S6 + 17 9.1.2 Mô hình hoá CF(x) và CS(x) là chi phí sản xuất và tồn kho cua x sản phẩm. Chi phí tồn khođược tính toán dựa trên số hàng tồn kho vào cuối kỳ, như trong các chương trước (cacmô hinh se rất ít khác nhau nêu ta giả thiết rằng chi phí được tính dựa trên số tồn khođầu tháng). Số luong sản phẩm sản xuất có thể chấp nhận là ở giữa XMin và XMax vàthêm cac ràng buôc vê sô luong hàng tồn kho an toàn hay vê diên tich mặt bằng kho nênmức hàng tồn kho nằm giữa SMin và SMax. Người ta biết được số hàng yêu cầu của pthoi kỳ tiếp theo và. di là yêu cầu của thoi kỳ thứ i. Mức hàng tồn kho đầu tiên là SInit vàngười ta du định đat số hàng tồn kho SFin ở cuối kỳ thứ p. Không được phép thiếu hụt. Muc đích là xác định được số hàng sản xuất Xi ở kỳ thứ i để cực tiểu tổng chi phícủa sản xuất và tồn kho. Chúng ta đưa vào các biến Si như trước, là số thành phẩm tồnkho ở cuối tháng. Người ta thu được mô hình sau: Min ∑i =1→p[CF(Xi) + CS(Si)] Và những ràng buộc: XMin ≤ Xi ≤ XMax SMin ≤ Si ≤ SMax S0 = SInit Sp = SFin Xi + Si-1 = Si +di Công thức trên hầu như là công thức đạt được trong chương trước. Nhưng ở đây,nếu những rằng buộc là tuyến tính, hàm mục tiêu không còn nữa. Bài toán này khôngthể giai bàng quy hoạch tuyến tính. 9.1.3 Mô hình hoá dưới dạng đồ thị Để giải quyết bài toán này, trước tiên người ta sẽ mô hình hoá no dưới dạng đồthị, mà chúng ta sẽ định nghĩa những đỉnh và cung. 1. Đỉnh Một đỉnh Vi,l biểu thị số luong tồn kho ở mức l o cuối kỳ thứ i. 2. Cung Người ta tạo ra một cung từ Vi-1,k đến Vi,l nêu co thê di tù tinh trang « số tồn khoở cuối kỳ thứ i-1 o mức k » dên tinh trang « số tồn kho ở cuối kỳ thứ i o mức l ». Yêucâu ở kỳ thứ i đã biết là di, ta suy ra số sản phẩm cần sản xuất trong kỳ thứ i là Xi = l +di – k. Với giá trị số tồn kho l da duoc biet ở cuối kỳ thứ i, cac giới hạn cua Xi sẽ dandên nhung giới hạn vê số tồn kho k ở kỳ thứ i -1. 1. Voi số luong tôn kho nhỏ nhất là Xmin.thi giá trị lớn nhất của k đạt được trong thoi ky i-1 là l + di – XMin. 2. Voi số luong sản xuât lớn nhất là Xmax.thi giá trị nhỏ nhất của k đạt được là l + di – XMax. Mặt khác, số tồn kho nằm trong khoảng từ SMin đến SMax, suy ra k nằm trongkhoảng kmin và kmax với kmin = Max (l + di – XMax , SMin) kmax = Min (l + di – XMax, SMax) Đồ thị là một đường không khep kin. Chúng ta sẽ tìm một con đường ngắn nhấttừ V0,Sinit đến Vp,SFin. Đồ thị co cac dinh cua tùng thoi ky và voi thoi ky i duoc dinh boiluong tôn kho tang. Thuật toán chung: Voi i thay doi từ 1 đ ...