Bài giảng Mô hình hóa hệ thống sản xuất TS. Đặng Vũ Tùng (ĐH Bách khoa Hà Nội) chuẩn nhất

Trường Đại học Bách khoa Hà Nội Viện Kinh tế và Quản lý

MỤC ĐÍCH MÔN HỌC

MÔ HÌNH HÓA

HỆ THỐNG SẢN XUẤT

TS. Đặng Vũ Tùng

Giúp cho sinh viên: l Hiểu biết về các phương pháp và kỹ năng lập mô hình cho các hệ thống sản xuất l Làm chủ một số công cụ giải mô hình l Khả năng nhận dạng, xây dựng, giải quyết & diễn giải kết quả cho các bài toán thực tế liên quan đến tối ưu hóa hoạt động của hệ thống sản xuất

Hànội - 2014

Mô hình hóa – TS Đặng Vũ Tùng – ĐH Bách Khoa Hà Nội

NỘI DUNG MÔN HỌC

PHƯƠNG PHÁP

l Chương 1. Giới thiệu l Chương 2. Mô hình tuyến tính l Chương 3. Mô hình vận tải l Chương 4. Mô hình mạng l Chương 5. Mô hình biến nguyên

l Giờ lý thuyết + thực hành phòng máy l Phát bài giảng; yêu cầu đọc trước ở nhà l Trên lớp cần lắng nghe + phát biểu l Đánh giá kết quả: Kiểm tra giữa kỳ (60’) + Bài tập nghiên cứu/thực hành + Thi cuối kỳ (60’)

l Làm bài được phép sử dụng tài liệu

Mô hình hóa

Chương 1. Giới thiệu về Mô hình hóa

1. vai trò của mô hình hóa

tiềm năng ứng dụng

Nhu cầu Nghiên cứu qua Mô hình Luôn có nhu cầu nghiên cứu hoàn thiện các hệ thống. Khó khăn gặp phải: l khi tiếp cận/tái tạo các hệ thống đang tồn tại l khi không hiệu quả (về thời gian, nguồn lực, chi phí)

3. các bước thực hiện mô hình hóa

nếu nghiên cứu trên hệ thống thực

thành phần của một mô hình ra quyết định

l khi nghiên cứu các hệ thống chưa tồn tại

5. một số yếu tố ảnh hưởng tới mô hình hóa

=> cần 1 công cụ nghiên cứu: mô hình!

Mô hình hóa

Các loại Mô hình

Mô hình ra quyết định

l Nhằm tìm kiếm đáp ứng tốt nhất (tối ưu) cho một vấn đề cần ra quyết định trong điều kiện có các hạn chế, ràng buộc (về nguồn lực, v.v.)

l mô hình nguyên mẫu thu nhỏ (prototype): là sự thể hiện cấu trúc hệ thống qua các quan hệ vật chất hữu hình, ví dụ như các mẫu thiết kế/kiến trúc, mô hình nhà xưởng, mẫu máy bay/ôtô thử nghiệm

l Mô hình hóa = sử dụng công cụ mô hình toán để

giải quyết vấn đề tối ưu cho hệ thống

l mô hình ra quyết định (decision model): là sự thể hiện hệ thống qua các quan hệ toán học hay logíc, ví dụ như mô hình dự báo nhu cầu sản phẩm, mô hình tương tác điện từ

=> Bài toán Tối ưu hóa

l mô hình khác

Mô hình hóa

Tiềm năng ứng dụng

Ví dụ l Tính toán vị trí đặt nhà máy để giảm thiểu chi phí

l Mô hình “Lập thời biểu tuần tra” cho cảnh sát San

vận chuyển nguyên vật liệu và sản phẩm

l Thiết kế bộ phận dịch vụ khách hàng tại các ngân

hàng, siêu thị, hãng taxi

l Thiết kế qui trình vận hành của robot/tay máy tại

Francisco: => tiết kiệm chi phí 11 triệu đôla/năm, giảm thời gian phản ứng 20% & tăng thu từ tiền phạt vi phạm giao thông 3 triệu đôla. (Interfaces 19, 1989, no.1).

các dây chuyền sản xuất, lắp ráp

l Lập mô hình bố trí sản xuất giảm thiểu tác động

l Mô hình “Dự trữ nhiên liệu tối ưu” cho Viện

môi trường

l Điều độ sản xuất sao cho đáp ứng nhu cầu với chi

phí tối thiểu

Nghiên cứu Điện lực Hoa Kỳ (EPRI) cắt giảm trên 125 triệu đôla từ chi phí dự trữ nhiên liệu tại 79 cty điện lực trên toàn nước Mỹ. (Interfaces 19, 1989, no.1).

l V.v.

Mô hình hóa

Hệ thống thực

Minh họa Quá trình chế tạo một sản phẩm thường qua nhiều công đoạn và đòi hỏi sự tham gia từ nhiều bộ phận khác nhau trong doanh nghiệp, từ bộ phận thiết kế đến bộ phận kế hoạch, bộ phận vật tư, xưởng sản xuất, bộ phận lưu kho, đến bộ phận marketing và bán hàng. Nhu cầu xác định sản lượng tối ưu mà DN cần duy trì ?

Hệ thống giả lập

Mô hình

Hệ thống thực có vô số quan hệ ràng buộc và yếu tố ảnh hưởng đến sản lượng của DN cần được xem xét.

Hệ thống giả lập chỉ “trích ra” những ràng buộc và ảnh hưởng có tính then chốt đối với sự vận động của hệ thống thực.

Mô hình hóa

Mô hình lại “giản hóa” những quan hệ then chốt này thành các công thức toán học dưới dạng hàm mục tiêu và tập hợp các ràng buộc.

Các bước mô hình hóa

Các bước thực hiện mô hình hóa

1. Xác định vấn đề: tìm hiểu vấn đề gặp phải, tìm hiểu hệ thống, xác định các phương án có thể ra quyết định, thu thập số liệu

2. Xây dựng mô hình: lượng hóa các quan hệ, xác định loại mô hình phù hợp, và phương pháp sử dụng để giải mô hình

1. Xác định vấn đề 2. Xây dựng mô hình 3. Giải mô hình 4. Kiểm chứng mô hình 5. Ứng dụng kết quả vào thực tế &

đánh giá

3. Giải mô hình: tìm phương án tối ưu và các phương án lựa chọn nếu có, phân tích độ nhạy để dự đoán hành vi của nghiệm khi các thông số thay đổi

Mô hình hóa

Chu trình thực hiện

Các bước mô hình hóa

4. Kiểm chứng mô hình: kiểm tra xem mô hình có

thể hiện được hành vi của hệ thống không, phương pháp phổ biến là so sánh với các số liệu quá khứ. Điều chỉnh lại mô hình nếu cần.

Xác định Vấn đề Xây dựng Mô hình

5. Ứng dụng kết quả và đánh giá: trình bày kết quả thu được với người ra quyết định trong đơn vị, diễn giải kết quả thành các hành động cụ thể, phối hợp cùng thực hiện và đánh giá kết quả của việc áp dụng. Rút ra bài học.

Giải Mô hình Áp dụng & Đánh giá

Mô hình hóa

Kiểm chứng

Thành phần của một Mô hình

Ba thành phần cơ bản: l các phương án lựa chọn (biến ra quyết định), l các điều kiện ràng buộc của vấn đề (=>

nghiệm khả thi), và

l tiêu chí lựa chọn phương án (hàm mục tiêu,

=> nghiệm tối ưu).

Ví dụ Công ty R. sản xuất sơn tường nhà gồm 2 loại: sơn trong nhà (giá bán 20 triệu đồng/tấn) và sơn ngoài nhà (giá bán 30 triệu đồng/tấn). Hai nguyên liệu chủ yếu A và B được cung cấp tối đa mỗi ngày là 6 tấn A và 8 tấn B. Để sản xuất 1 tấn sơn trong nhà cần 2 tấn nguyên liệu A và 1 tấn nguyên liệu B, trong khi 1 tấn sơn ngoài trời cần 1 tấn A và 2 tấn B. Nghiên cứu thị trường cho thấy nhu cầu tối đa đối với sơn trong nhà là 2 tấn /ngày. Vậy công ty R. nên sản xuất bao nhiêu tấn sơn mỗi loại để doanh thu đạt lớn nhất?

Mô hình hóa

Ví dụ (tiếp)

2. Hàm mục tiêu: thể hiện đích mà mô hình muốn hướng tới, trong trường hợp này là tối đa hóa tổng doanh thu từ việc bán 2 loại sơn.

– –

Tóm tắt vấn đề: Công ty cần xác định số lượng (tấn) sơn mỗi loại sẽ sản xuất để tối đa hóa tổng doanh thu trong khi thỏa mãn các điều kiện ràng buộc về mức độ sử dụng các nguyên liệu.

3. Các điều kiện ràng buộc: thể hiện những yêu cầu đặt ra đối với các giá trị của biến để nhằm ồm hạn chế về mức độ sử dụng từng loại nguyên liệu (A, B) không vượt quá lượng nguyên liệu sẵn có, và thỏa mãn đòi hỏi của thị trường (nhu cầu tối đa 2 tấn sơn trong nhà) và các biến là không âm

1.Biến ra quyết định: thể hiện phương án lựa chọn cho người ra quyết định, trong trường hợp này là lượng sơn SX số tấn sơn trong nhà sản xuất mỗi ngày số tấn sơn ngoài trời sản xuất mỗi ngày

Mô hình hóa

Đây là bước quan trọng nhất có ảnh hưởng đến thành công của việc lập và giải mô hình.

Vai trò của số liệu

Thuật toán sử dụng

l Kết quả của mô hình chỉ có ý nghĩa khi có

số liệu đầu vào tin cậy

l Mong muốn giải ra nghiệm tối ưu l Không phải tất cả các mô hình đều có thuật toán

tương ứng giải ra nghiệm tối ưu – vấn đề thời gian!

l Mô hình tất định: các thông số đã biết chắc

chắn

l Phương pháp tìm kiếm nghiệm gần tối ưu được

l Mô hình bất định: 1 vài số liệu chưa biết

chắc chắn

nghiên cứu áp dụng cho 1 số loại mô hình: – Thời gian tính toán – Chất lượng nghiệm gần tối ưu

l Nhu cầu thay đổi mô hình để phù hợp với

các số liệu sẵn có

Mô hình hóa

Kết luận

l mô hình hóa có vai trò và tiềm năng quan

trọng trong đời sống và SXKD l có 5 bước thực hiện mô hình hóa l ba thành phần của một mô hình ra quyết

định

l yếu tố số liệu đầu vào và thuật toán phù hợp có ảnh hưởng lớn tới mô hình hóa

Mô hình hóa

Trường Đại học Bách khoa Hà Nội Viện Kinh tế và Quản lý

Chương 2. Mô hình Tuyến tính (LP)

MÔ HÌNH HÓA

HỆ THỐNG SẢN XUẤT

1. Đặc tính của mô hình tuyến tính 2. Phương pháp giải bằng đồ thị 3. Bài toán cơ cấu sản phẩm 4. Phân tích độ nhạy 5. Bài toán phối trộn sản phẩm

TS. Đặng Vũ Tùng

Hànội - 2014

Mô hình hóa

Mục tiêu của Chương

Lịch sử ra đời & phát triển

Giúp sinh viên: l Nắm được các đặc trưng của bài toán LP l Biết cách xây dựng mô hình LP cho bài toán

l Ra đời từ đầu TK20 trong lĩnh vực quân sự l Là công cụ giải bài toán tối ưu hóa l Được ứng dụng rộng rãi trong quân sự, các

sản xuất

ngành công nghiệp, nông nghiệp, ngân hàng, giáo dục, hóa dầu, vận tải, y tế, lâm nghiệp, và thậm chí cả các ngành khoa học xã hội.

l Các công ty Fortune 500: 85% có sử dụng LP

l Biết cách giải bài toán LP l Biết cách phân tích độ nhạy của nghiệm (thời lượng: 8 tiết + 4 tiết thực hành)

Mô hình hóa

Thế nào là bài toán LP

Ví dụ 2.1 Bài toán cơ cấu sản phẩm Công ty R. sản xuất 2 loại sơn tường : sơn trong nhà (giá bán 20 tr.đ/tấn) và sơn ngoài nhà (giá bán 30 tr.đ/tấn).

Hai nguyên liệu chủ yếu A và B được cung cấp tối đa 6

Là một bài toán tối ưu hóa trong đó: l Phân bổ các nguồn lực cho các hoạt động l Nhằm đến tối ưu hóa một mục tiêu l Việc phân bổ nguồn lực phải thỏa mãn các

tấn A và 8 tấn B mỗi ngày. Sản xuất 1 tấn sơn trong nhà cần 2 tấn nguyên liệu A và 1 tấn nguyên liệu B, trong khi 1 tấn sơn ngoài trời cần 1 tấn A và 2 tấn B.

Nghiên cứu thị trường => nhu cầu tối đa 2 tấn sơn

điều kiện ràng buộc về các tài nguyên và/hoặc các hoạt động

l Các ràng buộc và mục tiêu đều là các đẳng

thức hay bất đẳng thức tuyến tính

trong nhà /ngày; nhu cầu sơn trong nhà không nhiều hơn nhu cầu sơn ngoài trời quá 1 tấn / ngày. Công ty R. nên sản xuất bao nhiêu tấn sơn mỗi loại để đạt doanh thu lớn nhất?

Mô hình hóa

Ví dụ 2.1 (2/5)

Ví dụ 2.1 (3/5)

2. Hàm mục tiêu: thể hiện đích mà mô hình muốn hướng tới, trong trường hợp này là tối đa hóa tổng doanh thu từ việc bán lượng sơn đã SX ra.

l Vì mỗi tấn sơn trong nhà bán được 20 triệu

Tóm tắt vấn đề: Công ty cần xác định số lượng (tấn) sơn mỗi loại sẽ sản xuất để tối đa hóa tổng doanh thu trong khi thỏa mãn các điều kiện ràng buộc về mức độ sử dụng các nguyên liệu và nhu cầu thị trường.

– Xt = số tấn sơn trong nhà sản xuất mỗi ngày – Xn = số tấn sơn ngoài trời sản xuất mỗi ngày

đồng, nên doanh thu từ sơn trong nhà là 20 xt. l Tương tự doanh thu từ sơn ngoài trời là 30 xn. l Với giả thiết là việc tiêu thụ 2 loại sơn độc lập với nhau thì tổng doanh thu z = 20 xt + 30 xn.

l Hàm mục tiêu: Max z = 20 xt + 30 xn.

1.Biến ra quyết định: thể hiện phương án lựa chọn cho người ra quyết định, trong trường hợp này là lượng sơn SX

Mô hình hóa

Đây là bước quan trọng nhất có ảnh hưởng đến thành công của việc lập và giải mô hình.

Ví dụ 2.1 (5/5)

Ví dụ 2.1 (4/5) 3. Các điều kiện ràng buộc: thể hiện những yêu cầu đặt ra

Mô hình xây dựng được:

max: thỏa mãn:

đối với các giá trị của biến, gồm: l Hạn chế về mức độ sử dụng từng loại nguyên liệu (A, B)

(nguyên liệu A) (nguyên liệu B)

2xt + xn  6 xt + 2xn  8

(1) (2) (3) (4) (5), (6)

z = 20xt + 30xn 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0

không vượt quá lượng nguyên liệu sẵn có: – –

(chênh lệch giữa 2 loại sơn) (sơn trong nhà)

xt - xn  1  2 xt

l Hạn chế về nhu cầu thị trường của hai loại sơn, tức là “lượng sơn trong nhà trừ lượng sơn bên ngoài”  1 tấn/ngày, và “nhu cầu sơn trong nhà”  2 tấn/ngày: – –

Mô hình hóa

l Các biến là không âm: xt  0; xn  0

Giả thiết cho bài toán LP (1/2)

Giả thiết cho bài toán LP (2/2)

1. Giả định về tính tỷ lệ (proportionality):

3. Giả định về tính chia được (divisibility):

Tính chia được yêu cầu mỗi biến được phép nhận các giá trị không nguyên (giá trị thực).

4. Giả định về tính chắc chắn (certainty):

Đóng góp của mỗi biến ra quyết định vào giá trị của hàm mục tiêu hay vào mức độ sử dụng tài nguyên tỷ lệ thuận với giá trị của biến ra quyết định đó.

2. Giả định về tính cộng được (addivity):

Đóng góp của mỗi biến ra quyết định vào giá trị của hàm mục tiêu / hàm ràng buộc độc lập với giá trị của các biến khác.

Giả định này cho rằng tất cả các thông số của bài toán (các hệ số trong hàm mục tiêu, các hệ số công nghệ và các giá trị ở vế phải của các hàm ràng buộc) đều là các hằng số đã biết một cách chắc chắn.

Mô hình hóa

PP Giải bằng đồ thị (1)

PP Giải bằng đồ thị (2)

l Bước 2. Thể hiện hàm mục tiêu trên đồ thị.

l Bước 1. Vẽ miền nghiệm của bài toán.

(5)

z = 0

z = 60

z = 126,67

(3)

(2)

(1)

(4)

l Bước 3. Tìm

F A

nghiệm tối ưu: C

B 4

(6)

Mô hình hóa

PP Giải bằng đồ thị (3)

Trường hợp đặc biệt (1)

a) Trường hợp vô số nghiệm. Ví dụ 2.1.a

Tính toán giá trị của nghiệm: l Lưu ý rằng C là điểm giao giữa các đường thẳng

VD 2.1: Do cạnh tranh, giá bán của sơn trong nhà giảm xuống còn 15 tr.đ/tấn. xt Phương án SX tối ưu?

(1) và (2), tức là C đồng thời thỏa mãn : – 2xt + xn = 6 – xt + 2xn = 8

l => xt = 11/3 , xn = 31/3 . Tức là cty nên SX 11/3 tấn sơn trong nhà và 31/3 tấn sơn bên ngoài mỗi ngày.

Đường Z // ràng buộc (2) => mọi điểm trên đoạn CB

l Doanh thu cực đại tương ứng là:

đều đạt z tối đa

F A

z = 20xt + 30xn = 126 2/3 (triệu đồng).

Mô hình hóa

(1) (2)

Trường hợp đặc biệt (2)

b) Trường hợp vô

(5)

(8)

Trường hợp đặc biệt (3) c) Trường hợp nghiệm không xác định. Ví dụ 2.1.c VD 2.1: nhà cung cấp đảm bảo cung cấp không hạn chế lượng nguyên liệu A, B mỗi ngày. Phương án SX tối ưu?

(3)

(5)

(3)

(2)

nghiệm. Ví dụ 2.1.b VD 2.1: GĐ cty đặt chỉ tiêu sản xuất ít nhất 1,5 tấn sơn trong nhà và 3,5 tấn sơn bên ngoài / ngày. Phương án SX tối ưu?

(1)

(7)

(4)

Miền nghiệm không tồn

tại !!!

(6)

Mô hình hóa

(6)

Miền nghiệm không bị chặn. Z có thể dịch chuyển tăng vô tận mà không rời khỏi miền nghiệm

PP giải bằng Bảng tính

l Bước 1: Nhập tất cả các thông số đầu vào

của mô hình – Đóng khung các ô này bằng viền màu xanh

l Bước 3: Tính toán lượng tài nguyên mỗi loại sử dụng bởi các biến (dùng hàm SUMPRODUCT) – Nhập dấu của các ràng buộc

l Bước 2: Nhập giá trị bất kỳ vào các ô có thể

l Bước 4: Tính toán doanh thu (dùng hàm

thay đổi (biến ra quyết định) – Đóng khung các ô này bằng viền màu đỏ

SUMPRODUCT) – Đóng khung ô mục tiêu bằng viền màu đen

Mô hình hóa

PP giải bằng Bảng tính

Hộp thoại Solver

l Nhấn vào Tools/Solver l Nhập thông số vào hộp thoại Solver

– Xem slide sau

l Đánh dấu vào ô Assume Linear Model trong

phần Options – Giữ nguyên các giá trị mặc định khác

l Nhấn vào nút Solve

Mô hình hóa

Đặc tính của nghiệm tối ưu

Phân tích độ nhạy

l Nửa trên trình bày mỗi hàng ứng với một ô

có giá trị thay đổi (biến) – Chú ý tới giá trị “reduced costs”

l Sơn trong nhà sản xuất 1,33 tấn/ngày l Sơn ngoài trời sản xuất 3,33 tấn/ngày l Tổng doanh thu đạt 126,67 triệu đ/ngày l Toàn bộ lượng nguyên liệu A, B đều sử

dụng hết

l Nửa dưới trình bày mỗi hàng ứng với một ràng buộc (không phải là các giới hạn trên và dưới của các biến) – Chú ý tới giá trị “shadow prices”

Mô hình hóa

Một số bài toán SX khác

Phân tích độ nhạy

l Một cách khác để phân tích độ nhạy là thay đổi các thông số đầu vào và chạy lại mô hình (Solver)

l Biện pháp này rõ ràng và đơn giản nhưng

l Bài toán phối trộn nguyên vật liệu l Bài toán dự trữ - sản xuất tối ưu l Bài toán danh mục đầu tư l V.v.

không thuận tiện khi có nhiều thông số đầu vào

Mô hình hóa

Bài toán phối trộn

Nhận xét bài toán phối trộn

l Cho số lượng các nguyên liệu đầu vào (nhận giá

l Bài toán đơn giản nhưng khi giải cần đặc

trị liên tục)

biệt lưu ý một số mẹo

l Phối trộn sao cho thỏa mãn:

l Ràng buộc phi tuyến có thể chuyển thành

tuyến tính bằng phép nhân đơn giản

l Lựa chọn kỹ biến ra quyết định

– Chia nhỏ các biến ra để dễ dàng tính toán và

– Ràng buộc về sản lượng đầu ra – Ràng buộc về chất lượng (thành phần, v.v.) – Chi phí có liên quan đến quá trình phối trộn l Trong các cách có thể, chọn biện pháp mang lại lợi

khống chế các yêu cầu về chất lượng

ích tối đa (chi phí tối thiểu, v.v.)

Mô hình hóa

Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý ***

Chương 3. Các Bài toán Vận tải

MÔ HÌNH HÓA

HỆ THỐNG SẢN XUẤT

1. Bài toán vận tải (transportation) 2. Bài toán giao việc (assignment) 3. Bài toán chuyển hàng (transshipment) 4. Bài tập ứng dụng

TS. Đặng Vũ Tùng

Hànội - 2014

Mô hình hóa

Mục tiêu của Chương

3.1. Bài toán Vận tải

l Bài toán vận tải liên quan đến việc xác định cách

Giúp sinh viên: l Nắm được các đặc trưng của bài toán vận tải l Biết cách lập mô hình vận tải cân bằng, các

phương pháp giải mô hình

l Biết cách lập và giải mô hình cho bài toán phân

thức vận chuyển một loại hàng hóa từ một số điểm nguồn (điểm cung, chẳng hạn như các nhà máy) đến một số điểm đích (điểm cầu, chẳng hạn như các nhà kho).

việc; phương pháp Hungary

l Quá trình ra quyết định về tuyến đường tốt nhất để vận chuyển này thường liên quan đến yếu tố chi phí vận tải giữa các điểm cung - cầu, hoặc các ràng buộc tương tự.

l Biết cách lập mô hình cho bài toán chuyển hàng l Biết cách dùng phần mềm để giải mô hình (thời lượng: 4 tiết + 4 tiết thực hành)

Mô hình hóa

Ví dụ 3.1: Truyền tải điện

Ví dụ 3.1 – tiếp

Đến

l Công ty Powerco mua điện từ 3 nhà máy điện để

Từ

cấp điện cho 4 thành phố.

Tp 1 Tp 2

Tp 3 Tp 4

Cung (GWh)

Nhà máy 1

$10

l Mỗi nhà máy có sản lượng cung cấp điện & Nhu cầu phụ tải đỉnh của các thành phố ở bảng sau l Chi phí truyền tải từ nhà máy đến nơi tiêu thụ phụ

Nhà máy 2

$12

$13

thuộc vào khoảng cách giữa 2 điểm này

Nhà máy 3

$14

$16

l Lập mô hình để giảm thiểu chi phí truyền tải điện

Cầu (GWh)

của Powerco

Mô hình hóa

Ví dụ 3.1

l Biến ra quyết định:

l Mô hình LP cho bài toán Powerco

– Powerco cần xác định lượng điện truyền tải từ mỗi nhà máy đến mỗi thành phố, nên đặt xij = lượng điện cấp từ nhà máy i cho thành phố j

l x14 = lượng điện cấp từ nhà máy 1 cho thành phố 4

Min Z = 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24 +14x31+9x32+16x33+5x34

l Ràng buộc:

– Ràng buộc phía cung để đảm bảo tổng lượng điện mà

Th.mãn: x11+x12+x13+x14 ≤ 35 (Ràng buộc cung)

– Ràng buộc phía cầu để đảm bảo tổng lượng điện mà mỗi th.phố nhận được thỏa mãn nhu cầu phụ tải của th. phố – Lượng điện truyền tải không thể âm, nên xij≥ 0 (i,j).

(Ràng buộc cầu) mỗi nhà máy cung cấp không thể vượt quá sản lượng tối đa của nhà máy

Mô hình hóa

(Không âm) x21+x22+x23+x24 ≤ 50 x31+x32+x33+x34 ≤ 40 x11+x21+x31 ≥ 45 x12+x22+x32 ≥ 20 x13+x23+x33 ≥ 30 x14+x24+x34 ≥ 30 xij ≥ 0 (i= 1,2,3; j= 1,2,3,4)

Ví dụ 3.1

Bài toán Vận tải tổng quát

Điểm cầu

Điểm cung

d1=45

l Một bài toán vận tải tổng quát được đặc

Th.phố 1

x11=0

s1=35

x12=10

Nhà máy 1

x13=25

x14=0

d2=20

x21=45

Th.phố 2

s2=50

trưng bởi những thông tin sau: – Một tập m điểm cung cấp mà từ đó hàng hóa sẽ được vận chuyển đi. Mỗi điểm cung i có thể cung cấp tối đa si đơn vị hàng.

x22=0 x23=5

Nhà máy 2

x24=0

d3=30

x31=0

Th.phố 3

x32=10

s3=40

x33=0

– Một tập n điểm cầu mà hàng hóa sẽ được vận chuyển tới. Mỗi điểm cầu j phải nhận được tối thiểu dj đơn vị hàng.

Nhà máy 3

x34=30

d4=30

– Mỗi đơn vị hàng hóa vận chuyển từ điểm cung i

Th.phố 4

tới điểm cầu j đòi hỏi chi phí cij.

Mô hình hóa

Mô hình tổng quát

l Xij = số đơn vị hàng được chuyển từ điểm cung i tới

Trường hợp đặc biệt l Bài toán có các ràng buộc như trên với hàm mục tiêu là max vẫn là một bài toán vận tải

điểm cầu j :

l Nếu i si = j dj thì tổng cung bằng với

tổng cầu, và bài toán đó được gọi là bài toán vận tải cân bằng (balanced transportation problem), khi đó tất cả các ràng buộc đều trở thành ràng buộc chặt (binding constraint) : j Xij = si và i Xij = dj

l Bài toán vận tải cân bằng có thể giải dễ

dàng hơn các bài toán LP khác

Mô hình hóa

Cân bằng Bài toán Vận tải

l Trường hợp tổng cung vượt quá tổng cầu:

l Trường hợp tổng cầu vượt quá tổng cung :

– Cân bằng bài toán vận tải bằng cách tạo ra một điểm

– Không có nghiệm khả thi, vì sẽ có một phần nhu cầu

– Nếu được phép không đáp ứng một phần nhu cầu, với mỗi đơn vị hàng bị thiếu phải chịu khoản ‘tiền phạt’ (penalty),

– Do việc chuyển hàng đến điểm cầu giả này không thực xảy ra, nên chi phí vận chuyển tới điểm này bằng 0 – Lượng hàng chuyển từ mỗi điểm cung tới điểm cầu giả

– Thì có thể lập bài toán cân bằng nhờ một điểm cung

không được thỏa mãn cầu ‘giả’ (dummy) có lượng cầu đúng bằng lượng cung dư

– Lượng hàng chuyển tới một điểm cầu từ điểm cung giả

– Nếu hàng hóa dư thừa tại điểm cung phải chịu phí lưu kho, thì đơn giá vận tải từ đó đến điểm cầu giả sẽ đúng bằng chi phí lưu kho

đúng bằng lượng cung dư thừa của điểm cung đó ‘giả’ (dummy) có chi phí vận chuyển tới mỗi điểm cầu đúng bằng mức tiền phạt tại điểm cầu đó

Mô hình hóa

thể hiện lượng hàng bị thiếu tại điểm cầu đó

Giải Bài toán Vận tải

Phương pháp Góc Tây-Bắc

l Xuất phát từ góc trên bên trái (Tây-Bắc) của Bảng Vận tải, gán cho x11 giá trị lớn nhất có thể (= min{s1, d1}) l Gạch hàng/cột đã được thỏa mãn, các ô còn lại trong

l Khác với các bài toán LP khác, bài toán vận tải cân bằng với m điểm cung và n điểm cầu rất dễ giải, dù có tới m + n ràng buộc là đẳng thức l Nguyên nhân là nếu một tập các giá trị (xij) thỏa

hàng/cột đó sẽ nhận giá trị 0. Nếu cả hàng và cột cùng thỏa mãn thì chỉ được gạch một

mãn (m + n – 1) ràng buộc thì ràng buộc còn lại sẽ nghiễm nhiên được thỏa mãn.

l Khi giải bằng phương pháp đơn hình (simplex),

l Cập nhật lượng cung/cầu còn lại và tiếp tục áp dụng quá trình gán cho ô tây-bắc của Bảng không nằm trên một hàng / cột đã bị gạch

l Quá trình kết thúc khi trong bảng chỉ còn một hàng hoặc

một cột chưa bị gạch

nghiệm cơ sở có thể tìm dễ dàng bằng các phương pháp Góc Tây-Bắc, Chi phí Cực tiểu, hay Vogel thông qua Bảng vận tải (transportation tableau)

Đặc điểm: đơn giản, nhưng chưa tính đến yếu tố chi phí

Mô hình hóa

Phương pháp Chi phí Cực tiểu

Phương pháp Vogel

Phương pháp này thực hiện tương tự như phpháp

Phương pháp xấp xỉ Vogel (VAM) thường cho nghiệm

cơ sở gần tối ưu

Góc Tây-Bắc, nhằm tìm nghiệm cơ sở và có tính đến chi phí vận chuyển:

l Bắt đầu với việc tính giá trị penalty cho mỗi

l Tìm biến có chi phí nhỏ nhất (cij=min), gán xij cho

hàng/cột (đúng bằng chênh lệch giữa 2 giá trị nhỏ nhất trong cùng hàng/cột đó)

giá trị lớn nhất có thể (=min{s1, d1})

l Gạch hàng/cột đã thỏa mãn, và cập nhật lượng

cung/cầu còn lại

l Lặp lại với ô tiếp theo có chi phí nhỏ nhất và

l Xác định hàng/cột có penalty lớn nhất, gán giá trị tối đa cho biến có chi phí nhỏ nhất trong hàng/cột đó l Gạch hàng/cột tương ứng (tương tự các pp trước),

không nằm trên hàng/cột đã bị gạch

tính lại các giá trị penalty

Phpháp này thường cho nghiệm cơ sở có chi phí lớn

l Lặp lại cho đến khi chỉ còn 1 hàng/cột chưa bị gạch

Mô hình hóa

Chuyển đổi sang bài toán vận tải

Ứng dụng : Ví dụ 3.2 Bài toán Sản xuất – Dự trữ

Hệ thống Vận tải

Hệ thống Sản xuất

Kỳ sản xuất i Kỳ tiêu thụ j

Một công ty lập kế hoạch SX cho 4 tháng tới: l Nhu cầu các tháng: 100, 200, 180 và 300 đvị. l Năng lực SX tương ứng: 50, 180, 280 và 270 đvị. l Hàng có thể giao ngay, dự trữ hoặc giao chậm l Chi phí: sản xuất = 4$/đvị,

lưu kho = 0.5$/đvị/thg, giao hàng chậm = 2$/đvị/thg

l Xác định kế hoạch SX để chi phí tối thiểu.

Điểm cung i Điểm cầu j Lượng cung tại nguồn i Năng lực Sxuất của kỳ i Nhu cầu của khách hàng Nhu cầu tại đích j trong kỳ j Chi phí sản xuất và dự trữ từ kỳ i đến kỳ j

Chi phí vận chuyển từ nguồn i đến đích j

Mô hình hóa

Ví dụ 3.2 - Bảng Tableau

Ví dụ 3.2 – Kế hoạch SX

Kỳ tiêu thụ

Kỳ SX

Cung 50 180 280 270

N.lực

4.5

5.5

Kỳ sản xuất 1 2 3 4

4.5

180

50 50 130 70 180 30 270

3 4

6 8 200

4 6 180

4.5 4 300

280 270 780

8 10 Nhu cầu 100

1 2 3 4 Kỳ tiêu thụ

Mô hình hóa

Cầu 100 200 180 300

3.2. Bài toán Giao việc

Ví dụ 3.3: Bố trí máy

l Cty Machineco có 4 cỗ

l Các bài toán giao việc (assignment) là một

1 2 3 4 Chi tiết

14 5 8 7 máy và cần gia công 4 chi tiết. Mỗi máy phải gia công một chi tiết.

lớp các bài toán vận tải đặc biệt có thể được giải một cách đơn giản và hiệu quả hơn rất nhiều mà không cần dùng đến phương pháp đơn hình (simplex).

l Thời gian cần thiết để mỗi máy khởi động & gia công 1 chi tiết như sau:

2 12 6 5 Máy 1 Máy 2

l Machineco cần bố trí máy thế nào để thời gian hoàn thành là tối thiểu

7 8 3 9

Mô hình hóa

2 4 6 10 Máy 3 Máy 4

Ví dụ 3.3 – Mô hình l Machineco cần xác định máy nào được giao gia công chi tiết

Đặc điểm Bài toán l Bài toán giao việc chính là bài toán vận tải cân bằng, trong

l Được đặc trưng bởi các chi phí có liên quan đến việc gán

nào. Đặt biến: đó mọi cung cầu đều bằng 1.

l xij=1 (nếu máy i được giao thực hiện chi tiết j) l xij=0 (nếu máy i không được giao thực hiện chi tiết j) l i,j=1,2,3,4

l Do lượng cung và lượng cầu của bài toán giao việc là nguyên, nên nghiệm tối ưu cũng nhận giá trị nguyên.

• Mô hình min z = 14x11+5x12+8x13+7x14 +2x21+12x22+6x23+5x24 +7x31+8x32+3x33+9x34 +2x41+4x42+6x43+10x44

mỗi điểm cung cho một điểm cầu (ma trận chi phí).

l Do vế phải (RHS) của mỗi ràng buộc đều bằng 1, mỗi biến xij phải là số nguyên không lớn hơn 1. Nên xij phải là 0 hoặc 1, và ta có thể bỏ qua ràng buộc xij = 0 hoặc 1, và giải bài toán như một bài toán vận tải cân bằng.

Mô hình hóa

(i=1,2,3,4) (j=1,2,3,4) (ràng buộc về máy) (ràng buộc về chi tiết) th.mãn j xij = 1 i xij = 1 xij = 0 hoặc 1

Phương pháp Hungary

Phương pháp Hungary (2)

l Bước 2: Gạch số đường tối thiểu (ngang hoặc

l Phương pháp Hungary rất hiệu quả để giải các bài toán giao việc mà không cần sử dụng đến phép biến đổi đơn hình (simplex). Các bước thực hiện: l Bước 1: Tìm phần tử nhỏ nhất trong mỗi hàng của ma trận chi phí (m x m). Lập ma trận mới bằng cách trừ giá trị trong mỗi ô cho giá trị nhỏ nhất trong hàng tương ứng. Với ma trận này lại tìm phần tử nhỏ nhất trong mỗi cột, và xây dựng ma trận tối giản bằng cách trừ trừ giá trị trong mỗi ô cho giá trị nhỏ nhất trong cột tương ứng.

dọc) sao cho đi qua tất cả mọi số 0 trong ma trận tối giản. Nếu cần tổng cộng m đường thẳng, thì nghiệm tối ưu có được từ các giá trị 0 đã được gạch qua. Nếu chỉ cần ít hơn m đường => Bước 3. l Bước 3: Tìm phần tử khác 0 nhỏ nhất (có giá trị là k) chưa bị gạch qua trong ma trận tối giản ở Bước 2. Trừ k từ mỗi phần tử chưa được kẻ qua của ma trận tối giản, và cộng k vào những phần tử được gạch qua 2 lần. Quay lại bước 2.

Mô hình hóa

3.3. Bài toán Chuyển hàng

Ví dụ 3.3 – Giải bằng ph.pháp Hungary

l Trong bài toán vận tải, hàng chuyển trực tiếp từ

điểm cung đến điểm cầu

14 5 8 7 9 0 3 2

l Khi hàng có thể chuyển giữa các điểm cung hoặc

2 12 6 5 0 10 4 3

7 8 3 9 4 5 0 6

giữa các điểm cầu, hoặc có thể qua các điểm trung chuyển trên đường từ điểm cung đến điểm cầu => Bài toán chuyển hàng (transshipment)

2 4 6 10 0 2 4 8

9 0 3 0 10 10 0 0 3 3 0 0

0 10 4 1 0 0 9 9 3 3 0 0

l Định nghĩa: Điểm cung là điểm chỉ có thể gửi đi mà không nhận vào; Điểm cầu là điểm chỉ có thể nhận vào mà không gửi đi; Điểm trung chuyển vừa có thể nhận & gửi hàng

4 5 0 4 5 5 5 5 0 0 4 4

Mô hình hóa

0 2 4 6 0 0 1 1 3 3 5 5

Thuật toán

l Tìm nghiệm tối ưu cho bài toán chuyển hàng bằng

Ví dụ 3.4: Định tuyến vận chuyển l Cty GM sản xuất xe tại 2 nhà máy ở Memphis và Denver, có công suất 150 và 200 xe/ngày. Xe được chuyển tới khách hàng ở L.A & Boston, mỗi nơi có nhu cầu 130 xe/ngày. Hàng có thể giao trực tiếp hoặc thông qua kho ở N.Y hoặc Chicago. Xác định tuyến vận chuyển tối ưu.

mô hình vận tải (giả thiết cung ≥ cầu): – Bước 1. Cân bằng bài toán (bổ sung điểm cầu giả nếu

Từ \ Đến Memphis Denver

N.Y

Chicago

L.A

Boston

Memphis

Denver

N.Y

Chicago

– Bước 2. Lập bảng vận tải: mỗi hàng thể hiện cho một điểm cung / trung chuyển, mỗi cột thể hiện cho một điểm cầu / trung chuyển. Gọi s = tổng lượng cung. Mỗi điểm trung chuyển lượng cung (cầu) bằng lượng cung (cầu) ban đầu của điểm đó + s (đảm bảo lượng hàng tịnh qua điểm trung chuyển và để bài toán cân bằng)

L.A

– Bước 3. Giải mô hình vận tải tìm được

Boston

cần, có cung bằng 0 và cầu bằng lượng cung vượt trội). Hàng chuyển đến điểm này có chi phí bằng 0. 0 - 8 13 25 28

Mô hình hóa

- - - - - 0 - - - - 15 0 6 - - 12 6 0 - - 26 16 14 0 - 25 17 16 - 0

Bài toán Lập kế hoạch SX

Ví dụ 3.4: Mô hình l Lập mô hình vận tải cân bằng cho bài toán

chuyển hàng bằng cách bổ sung điểm cầu giả có nhu cầu = 150+200-130-130 = 90

N.Y

Chicago

L.A

Boston

Dummy

Cầu

Memphis

Denver

8 13 25 28 0 150

N.Y

15 12 26 25 0 200

Chicago

0 6 16 17 0 350

Cung

6 0 14 16 0 350

l Nhu cầu của loại động cơ tiết kiệm năng lượng trong 5 tháng tới là 200, 150, 300, 250 và 400 chiếc. Nhà sản xuất có khả năng sản xuất tương ứng trong các tháng đó là 180, 230, 430, 300 và 300 chiếc. Hàng không được phép giao chậm, nhưng cty có thể huy động làm thêm giờ nếu cần, với sản lượng bổ sung đạt tối đa 50% công suất bình thường. Chi phí SX các tháng là 100$, 96$, 115$, 102$ và 105$. Chi phí cho động cơ làm ngoài giờ cao gấp rưỡi chi phí SX bình thường. Ngoài ra những động cơ được SX và dự trữ để bán sau sẽ có chi phí lưu kho 4$/đcơ/tháng. Lập mô hình vận tải để giải bài toán này.

Mô hình hóa

350 350 130 130 90

Bài toán Điều xe

l Cảnh sát 113 Hànội nhận được 3 cuộc gọi yêu cầu hỗ trợ. Hiện có 5 xe tuần tra có thể huy động, thời gian cần thiết để các xe này tới được nơi yêu cầu như trong bảng. Hãy dùng phương pháp Hungary để xác định xe nào cần điều đến vị trí nào.

Bài toán Cung ứng dịch vụ l Một cty cung ứng dvụ ký HĐ cung cấp khăn trải bàn sạch cho 1 nhà hàng có nhu cầu trong tuần như sau. Cty có thể: - cung cấp khăn mới, với giá 1.2$/chiếc - giặt hấp nhanh để ngay sáng hôm sau nhận được khăn sạch, với giá 0.6$/chiếc - giặt hấp thông thường để 3 ngày sau nhận được khăn sạch, với giá 0.3$/chiếc

l Cty nên lập kế hoạch cung ứng khăn ntn?

Xe 1 Xe 2 Xe 3 Xe 4 Xe 5

Ngày CN T2 T3 T4 T5 T6 T7 Cuộc gọi 1 10 6 7 5 9

Mô hình hóa

Cuộc gọi 2 11 7 8 6 4 Nhu cầu 240 120 140 200 180 140 220 Cuộc gọi 3 18 7 5 4 7

Bài toán Bố trí lịch bay

Lịch bay AirVN

Chuyến

Rời HAN

Đến SGN

Rời SGN

Đến HAN

7 am

9 am

l AirVN cần bố trí phi hành đoàn cho các chuyến bay hàng ngày giữa Hà Nội (HAN) và thành phố HCM (SGN). Mỗi ngày một phi hành đoàn phải bay một chuyến HAN-SGN và 1 chuyến SGN- HAN với thời gian nghỉ giữa 2 chuyến bay tối thiểu là 1h. Cty muốn lập lịch bay sao cho giảm thiểu thời gian chờ giữa 2 chuyến bay của phi hành đoàn.

7.30 am 9.30 am 11 am 3 pm 5 pm 7 pm 9 pm

1 pm 5 pm 7 pm 9 pm 11 pm

1 2 3 4 5 6 7

6.30 am 8.30 am 10 am 2 pm 4 pm 7 pm 8 pm 10 pm

8 am 12 pm 2 pm 5 pm 6 pm 8 pm

1 2 3 4 5 6 7

l Dùng mô hình giao việc để giải bài toán, giả thiết rằng cuối ngày các nhân viên phi hành đoàn đều trở về nhà.

Mô hình hóa

Bài toán Tuyển dụng LĐ l Một cty môi giới cần cung ứng lao động bán phổ thông cho 5 tháng tới với số lượng tương ứng là 100, 120, 80, 170, 50 người. Chi phí để sử dụng lao động phụ thuộc vào độ dài thời gian thuê lao động. Dùng mô hình chuyển hàng xây dựng kế hoạch tuyển LĐ để chi phí là nhỏ nhất?

Thời gian thuê LĐ (tháng)

1,3

1,8

2,2

2,5

Chi phí/LĐ (triệu đồng)

Mô hình hóa

Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý ***

Chương 4. Một số mô hình Mạng

1. Bài toán Tuyến đường ngắn nhất (shortest path)

MÔ HÌNH HÓA

2. Bài toán Lưu lượng tối đa (maximum flow)

3. Bài toán Mạng với chi phí tối thiểu (minimum

HỆ THỐNG SẢN XUẤT

cost capacitated network)

4. Bài toán cây tối thiểu (minimum spanning tree)

TS. Đặng Vũ Tùng

5. Bài tập ứng dụng: Kiểm soát dự án (CPM &

PERT)

Hànội - 2014

Mô hình hóa

4.1. Khái niệm

Mục tiêu của Chương

l Bài toán vận tải và các biến thể của nó là những bài toán có thể biểu diễn và giải bằng mô hình mạng.

l Một số ví dụ khác:

Giúp sinh viên: l Nắm được các đặc trưng của bài toán mạng l Biết cách lập mô hình để đưa một bài toán

– Thiết kế mạng đường ống dẫn khí tự nhiên nối các

về dạng mô hình mạng

l Lập mô hình cho một số bài toán mạng cơ

– Xác định tuyến đường ngắn nhất nối 2 thành phố trong

giếng khoan ở Biển Đông vào nhà máy chế biến khí Dinh Cố

bản

l Dùng phần mềm để giải mô hình

(thời lượng: 6 tiết + 4 tiết thực hành)

– Xác định kế hoạch vận chuyển với chi phí nhỏ nhất từ nơi khai thác dầu đến nhà máy lọc dầu và tới các trung tâm phân phối xăng dầu. Xăng dầu có thể vận chuyển bằng tàu thủy, xe bồn hoặc đường ống với công suất tối đa đã biết

Mô hình hóa

mạng giao thông đường bộ hiện có

4.2 Bài toán Tuyến đường ngắn nhất

Khái niệm (tiếp) l Nhiều bài toán tối ưu hóa có thể phân tích rất thuận tiện

l Giả thiết mỗi cung trong mạng có độ dài

xác định

l Trong mỗi mạng có dòng chảy (flow) của hàng hóa dưới

l Bài toán tìm đường đi ngắn nhất từ nút

thông qua biểu đồ (graph) biểu thị quan hệ giữa các yếu tố. l Một biểu đồ mạng được xác định bởi tập các nút (node) và các cung (arc).

l Các dòng chảy qua một cung bị hạn chế bởi công suất của

dạng nào đó (dầu chảy qua mạng đường ống, dòng xe chạy trong mạng giao thông,..)

mạng số 1 đến một nút bất kỳ trong mạng gọi là Bài toán Tuyến đường ngắn nhất l Ví dụ: tìm đường ngắn nhất từ nhà T đến

giảng đường D8

l Một cung sẽ là có hướng nếu nó cho dòng chảy dương qua nó theo một chiều và không cho chảy theo chiều ngược lại. Một mạng có hướng sẽ gồm nếu các cung của nó đều có hướng

Mô hình hóa

cung (có thể là hữu hạn hoặc vô hạn)

Ví dụ 4.1 – Lập mô hình mạng

Ví dụ 4.1: Thay thế thiết bị l Một thiết bị mới được mua với giá $12,000 tại thời điểm 0. l Chi phí bảo dưỡng thiết bị trong một năm phụ thuộc vào số

l Bài toán này có thể được lập mô hình dưới dạng

bài toán tuyến đường ngắn nhất

l Biểu đồ mạng gồm có 6 nút:

l Có thể thanh lý máy cũ và mua máy mới để tránh chi phí bảo dưỡng quá lớn. giả thiết giá máy mới là không đổi l Mục tiêu là tối thiểu hóa chi phí cho 5 năm hoạt động

Tuổi (năm) Chi phí bảo dưỡmg Giá thanh lý

– Nút i là thời điểm bắt đầu năm i và với i

$2,000

$4,000

$7,000

l Chiều dài của cung (i,j) là cij chính là tổng chi phí

$5,000

$6,000

$9,000

$2,000

khi sử dụng máy từ năm i đến năm j cij = chi phí bảo dưỡng các năm i,i+1,…,j-1

$12,000

$1,000

+ chi phí mua máy mới đầu năm i - giá thanh lý máy cũ đầu năm j

Mô hình hóa

năm đã khai thác thiết bị (tuổi của thiết bị)

Ví dụ 4.1 – Tính toán chi phí

Ví dụ 4.1 – Nghiệm

l Chiều dài các cung ứng với chi phí vận hành từ

thời điểm i đến thời điểm j:

l Từ biểu đồ có thể thấy cả hai tuyến 1-3-5-6 và 1-2-4-6 đều cho giá trị nhỏ nhất (=31).

c12=2+12-7=7 c13=2+4+12-6=12 c14=2+4+5+12-2=21 c15=2+4+5+9+12-1=31

c16=2+4+5+9+12+12-0=44 c23=2+12-7=7 c24=2+4+12-6=12 c25=2+4+5+12-2=21

c45=2+12-7=7 c46=2+4+12-6=12 c56=2+12-7=7

c26=2+4+5+9+12-1=31 c34=2+12-7z=7 c35=2+4+12-6=12 c36=2+4+5+12-2=21

Mô hình hóa

2 3 4 5 6 1

Phương pháp giải

Bảng tableau

Mua\Bán 2

l Với giả thiết các cung có độ dài không âm, thuật toán Dijkstra được dùng để tìm tuyến ngắn nhất từ một nút mạng

l Có thể lập bài toán này như bài toán trung chuyển (transshipment): 1 đơn vị hàng chuyển từ điểm nguồn đến điểm đích qua các tuyến khác nhau trong mạng. Mục tiêu là giảm thiểu quãng đường đi từ điểm nguồn đến điểm đích.

l Giải bài toán trung chuyển bằng LINGO

Mô hình hóa

4.3 Bài toán Lưu lượng Tối đa (Maximum Flow)

Ví dụ 4.2: Lưu lượng tối đa l Cty Sunco Oil muốn chuyển lượng dầu tối đa (mỗi giờ) qua hệ

l Nhiều tình huống có thể lập mô hình dưới dạng

Cung

Công suất (1000 thùng/giờ)

a0(2)

(so,1)

(0)3

(so,2)

thống đường ống từ điểm so đến điểm si.

(1,2)

(2)2

(2)3

(2)2

một mạng trong đó các cung có một năng lực hạn chế về lượng hàng có thể chuyển qua cung đó l Trong những tình huống đó, thường có nhu cầu

(1,3)

(0)1

(0)4

1 so si 2

(3,si)

vận chuyển dòng hàng tối đa từ một điểm ban đầu (nguồn) đến một điểm cuối (đích)

(2,si)

l Những loại bài toán này gọi là Bài toán Lưu

lượng Tối đa

l Các cung thể hiện các tuyến đường ống có Ø khác nhau => quyết định số thùng dầu tối đa có thể chuyển qua đường ống (công suất của cung)

Mô hình hóa

Phương pháp giải l Lập mô hình LP để xác định số thùng dầu tối đa

Phương pháp giải l Gọi x0 = lưu lượng qua cung giả ao, nguyên lý bảo toàn

có thể chuyển từ so đến si mỗi giờ

l Mục tiêu của Sunco là tối đa hóa x0.

l Lập cung giả a0 nối điểm đích đến điểm nguồn l Xác định biến ra quyết định:

Max Z= X0 S.t.

(Công suất của cung)

– xij = Lượng thùng dầu chuyển qua cung (i,j) mỗi giờ l Để có dòng chảy tồn tại phải thỏa mãn 2 đặc tính: – 0 <= lưu lượng chảy qua cung <= công suất của cung – Lưu lượng chảy vào nút i = Lưu lượng chảy ra khỏi nút

dòng chảy => x0 = tổng lượng dầu đến điểm đích

(Cân bằng nút so) (Cân bằng nút 1) (Cân bằng nút 2) (Cân bằng nút 3) (Cân bằng nút si)

Xso,1<=2 Xso,2<=3 X12<=3 X2,si<=2 X13<=4 X3,si<=1 X0=Xso,1+Xso,2 Xso,1=X12+X13 Xso,2+X12=X2,si X13+X3,si X3,si+X2,si=X0 Xij>=0

l Bài toán Lưu lượng tối đa có thể giải thuận tiện

bằng LINGO

l Một nghiệm tối ưu cho bài toán LP này là Z=3, xso,1=2,

Mô hình hóa

x13=1, x12=1, xso,2=1, x3,si=1, x2,si=2, xo=3.

Ví dụ 4.3 : Định tuyến vận chuyển

4.4. Bài toán mạng với chi phí tối thiểu (MCCN)

Chuyến

Số lượng max

l Các bài toán vận tải, giao việc, trung chuyển,

Juneau- Settle

Settle – Los Angeles

tuyến đường ngắn nhất, lưu lượng tối đa,.. đều là các trường hợp đặc biệt của bài toán mạng với chi phí tối thiểu (minimum cost capacitated network - MCCN).

Settle -Denver

l Dạng thức chung của bài toán MCCN:

Los Angeles - Dallas

(với mỗi nút i trong mạng)

Denver -Dallas

l Hãng HK Fly-by-Night cần bố trí các chuyến bay nối chuyến giữa Juneau (Alaska) và Dallas (Texas). Các chuyến bay phải dừng tại Settle, rồi dừng ở Los Angeles hoặc Denver. Cty được cấp phép số chuyến bay tối đa giữa các thành phố mỗi ngày như sau. Hãy lập kế hoạch bay để tăng tối đa số chuyến bay hàng ngày từ Juneau đến Dallas.

(với mỗi cung trong mạng)

Mô hình hóa

Ví dụ 4.4 - Bài toán MCCN

MCCN – Đặc điểm bài toán

Nhà máy

Chi phí SX/ tấn

CS min (tấn)

CS max (tấn)

l Ràng buộc yêu cầu tổng dòng ra tịnh của nút i phải bằng bi được gọi là phương trình cân bằng dòng.

25$

400

800

l Các phương trình cân bằng dòng trong bài toán

28$

450

900

Nhà máy

Nhà cung ứng S1

Nhà cung ứng S2

Khách hàng C1

Khách hàng C2

10$

MCCN có thuộc tính quan trọng sau: Mỗi biến xij có hệ số +1 trong phương trình cân bằng của nút i, hệ số -1 trong phương trình cân bằng của nút j, và hệ số là 0 trong tất cả các phương trình cân bằng khác.

l Dùng LINGO để giải dễ dàng các bài toán MCCN.

12$

13$

l Một cty sản xuất 1 hợp chất cơ bản để làm các loại sơn. Cty có 2 nhà máy và ký hợp đồng cung cấp từ 2 nhà cung ứng để bán SP cho 2 khách hàng. Hợp đồng cung ứng 500 và 700 tấn nguyên liệu từ nhà cung ứng 1 và 2 với gia tương ứng là 200$ và 210$/tấn. Để tạo 1 tấn hợp chất cần 1.2 tấn nguyên liệu. Chi phí vận chuyển, công suất của các nhà máy và nhu cầu của khách hàng như trong bảng.

Mô hình hóa

Ví dụ 4.4 - Bài toán MCCN

l Sơ đồ mạng biểu diễn bài toán:

Ví dụ 4.5 - Bài toán vận tải dưới dạng MCCN (1) l Mô hình MCCN dùng mô tả bài toán vận tải khi:

– Điểm cung nối trực tiếp với điểm cầu – Công suất tối thiểu của các cung bằng 0 – Công suất tối đa của các cung bằng 

Điểm cung 1

Điểm cầu 1

25$

[-660]

4 (Nút 1)

10$ (0,500)

200$ (500,)

(400,800)

12$ (0,500)

[F]

2 4 6 8 1 3

5 (Nút 2)

[-800]

210$ (750,)

13$ (0,750)

28$ (450,900)

6 (Nút 3)

3 (Nút 4)

Điểm cầu 2

Điểm cung 2

Mô hình hóa

3 5 7 9 2 4

Ví dụ 4.5 - Bài toán vận tải dưới dạng MCCN (2)

Bài toán tuyến đường ngắn nhất dưới dạng MCCN

l Biểu diễn dưới dạng MCCN:

l Mô hình MCCN dùng mô tả bài toán tuyến đường ngắn

đơn vị

– Tất cả các cung có công suất tối thiểu của các cung bằng 0, và

min Z = X13+2X14+3X23+4X24 nhất khi: – Điểm nguồn chuyển +1 đơn vị hàng và điểm đích nhận -1

công suất tối đa của các cung bằng 

X13 X14 X23 X24 0 1 0 1 = 4 Nút 1

– Đơn giá chi phí của dòng vận chuyển trên mỗi cung thể hiện

khoảng cách giữa các nút mạng

0 0 1 1 = 5 Nút 2

l Mục tiêu của bài toán là chuyển 1 đơn vị hàng từ

-1 0 -1 0 = -6 Nút 3

nguồn đến đích với chi phí (khoảng cách) là nhỏ nhất

1 -1 0 -1 = -3 Nút 4

Mô hình hóa

Các biến không âm

Ví dụ 4.6 - Bài toán lưu lượng tối đa dưới dạng MCCN

Bài toán lưu lượng tối đa dưới dạng MCCN

l Xét ví dụ 4.2. Ta có: bso=b1=b2=b3=bsi=0 min Z = -X0

l Mô hình MCCN dùng mô tả bài toán lưu lượng tối đa khi:

Xso,1 Xso,2 X13

X12 X3,si X2,si

– Công suất tối đa của các cung thể hiện dòng tối đa cho phép,

-1

Nút so

công suất tối thiểu của các cung bằng 0

-1

Nút 1

-1

Nút 2

-1

Nút 3

-1

Nút si

– Tất cả các cung có đơn giá chi phí vận chuyển bằng 0 – Lượng chuyển từ nút nguồn và lượng nhận tại nút đích được đặt tương ứng bằng +F và –F. Giá trị F cần chọn đủ lớn để cho phép dòng tối đa chảy qua mạng

≤

Cung (so,1)

≤

Cung (so,2)

≤

Cung (1,3)

≤

Cung (1,2)

≤

Cung (3,si)

– Một cung trực tiếp nối điểm nguồn với điểm đích. Mục đích là để chuyển lượng dư (surplus) của F không chảy qua mạng. Cung này không có hạn chế về công suất, và có chi phí vận chuyển đủ lớn để lượng hàng qua mạng ban đầu là lớn nhất.

≤

Cung (2,si)

Mô hình hóa

0 Mô hình hóa

Các biến không âm

Ví dụ 4.7 - Bài toán giao thông l Mỗi giờ có trung bình 900 xe vào mạng tại nút 1 để đi đến

nút 6. Thời gian cần để đi qua mỗi phố và số xe tối đa có khả năng lưu thông qua mỗi phố trong 1 giờ (trong ngoặc) như trên hình. Lập mô hình MCCN để tối thiểu hóa tổng thời gian cần để tất cả các xe đi qua mạng từ nút 1 đến nút 6.

4.5 Bài toán Cây tối thiểu (Minimum Spanning Tree) l Xét trường hợp cần tạo mạng đường giao thông nối liền một số cụm dân cư ở vùng nông thôn. Do ngân sách hạn hẹp nên cần xây dựng số km đường tối thiểu mà vẫn cho phép giao thông từ nơi này đến nơi khác.

30 (600)

60 (400)

10 (800)

70 (100)

2 4

30 (600)

l Trường hợp trên có thể biểu diễn bằng một mạng lưới trong đó mỗi cụm dân là một nút và mỗi con đường là một cung.

10 (300)

30 (600)

50 (600)

6 1

60 (400)

Mô hình hóa

3 5

Thuật toán Cây tối thiểu l Bước 1. Bắt đầu từ nút i bất kỳ, nối nó với nút j gần nhất

l Bước 2. Chọn một phần tử thuộc C’ (nút n) gần nhất với một phần tử bất kỳ nằm trong C (nút m). Cung (m,n) sẽ thuộc cây tối thiểu. Cập nhật các tập C (gồm nút i,j, n) và C’ (loại bỏ nút n).

trong mạng. Hai nút i, j tạo thành tập các nút kết nối C={i,j} và cung (i,j) nằm trong cây tối thiểu. Các nút còn lại trong mạng tạo thành tập các nút chưa kết nối C’

Bài toán Cây tối thiểu l Mô hình thu được là một điển hình của bài toán cây tối thiểu, trong đó phải xác định tập các cung trong một mạng sao cho chúng nối tất cả các nút mạng với nhau với tổng độ dài các cung là nhỏ nhất ( kết nối có hiệu quả nhất tất cả các nút mạng với nhau) l Mỗi cung (i,j) trong mạng có một độ dài nhất định, và cung (i,j) biểu diễn việc kết nối nút i với nút j l Với một mạng có n nút, một cây là nhóm n-1 cung nối tất cả các nút của mạng với nhau và không tạo thành vòng

l Bước 3. Lặp lại quá trình trên cho đến khi tập C’ rỗng, tức là toàn bộ các nút đã nằm trong cây tối thiểu. Các phương án có cùng giá trị có thể lựa chọn ngẫu nhiên, và thể hiện các phương án thay thế.

Mô hình hóa

Ví dụ 4.8 – Kéo mạng cáp

l Cty truyền hình cáp ABC (1) đang lập kế hoạch cung cấp dịch vụ cho 4 khu đô thị mới (2-5).

– Bước 1: Chọn nút 1 để bắt đầu. Nút gần nhất là 2. Do đó C={1,2}, Ć={3,4,5}, cung (1,2) là thuộc cây nhỏ nhất

l Xác định cách kết nối cần ít cáp nhất

– Nếu không có đường nối giữa 2 khu đô thị nghĩa là về mặt kỹ thuật không thể kéo cáp trực tiếp giữa 2 khu đó

Mô hình hóa

1 1 2 2 2 1 1 6 2 5 4 2 2 3 2 6 4 5 4 4 3 2 3 4 5 4 3 5

Ví dụ 4.8 – Kéo mạng cáp

l Bước 3: Do nút 3 gần nút 5 nhất, đưa cung (5,3) vào cây nhỏ nhất. Ta có C={1,2,5,3} và Ć={4}.

l Bước 2: Nút 5 gần nhất với tập C. Do nút 5 cách đều nút 1 và 2, nên có thể đưa cung (2,5) hoặc (1,5) vào cây nhỏ nhất. Giả sử chọn cung (2,5). Vậy C={1,2,5} và Ć={3,4}.

Mô hình hóa

1 1 1 2 1 2 2 2 2 6 2 6 5 4 3 2 5 4 4 3 2 4 4 3 5 4 3 5

Ví dụ 4.8 – Kéo mạng cáp

4.6 CPM & PERT l Mô hình mạng có thể dùng để lập tiến độ cho các

l Bước 4: Nút 5 gần nút 4 nhất. Đưa cung (5,4) vào

dự án lớn gồm rất nhiều hoạt động

cây nhỏ nhất

l Cây nhỏ nhất gồm các cung (1,2), (2,5), (5,3), và (5,4). Chiều dài tối thiểu của cây là 1+2+2+4=9

l Nếu thời gian thực hiện mỗi hoạt động đã biết và xác định, thì phương pháp đường găng (CPM) có thể dùng để tính toán thời gian cần thiết để hoàn thành một dự án

l Nếu thời gian thực hiện các hoạt động là chưa biết chắc chắn, thì phương pháp (PERT) có thể dùng để dự tính xác suất là dự án sẽ hoàn thành tại một mốc thời gian nào đó

Mô hình hóa

1 1 2 2 2 6 5 4 3 2 4 4 3 5

Hoạt động của dự án

Ứng dụng l CPM & PERT được sử dụng trong nhiều ứng dụng

l Để áp dụng CPM & PERT, cần liệt kê các hoạt động

khác nhau, chẳng hạn: – Lập tiến độ cho các dự án xây dựng như xây tòa nhà văn phòng, chung cư, cầu đường, sân vận động,…

l Dự án hoàn thành khi tất cả các hoạt động đã hoàn thành l Để bắt đầu một hoạt động nhất định cần hoàn thành một

(activities) của dự án.

l Dùng biểu đồ mạng để thể hiện quan hệ trình tự trước sau

tập các hoạt động khác (hoạt động tiền đề)

l Hoạt động thể hiện bằng các cung có hướng và các nút thể hiện sự kiện (event) hoàn thành các hoạt động (biểu đồ AOA)

– Cài đặt hệ thống máy tính mới – Thiết kế và marketing sản phẩm mới – Đóng tàu – Hòan tất việc sát nhập công ty – V.v.

Mô hình hóa

giữa các hoạt động của dự án

Ví dụ: lập tiến độ dự án

Biểu đồ mạng AOA l Biểu đồ dự án AOA được xây dựng dựa trên các hoạt động

l Cty Widgetco chuẩn bị giới thiệu SP mới. Các hoạt động và trình tự như sau. Thể hiện dự án bằng biểu đồ mạng

một hoạt động không có tiền đề.

và quan hệ tiền đề với những quy tắc sau: 1. Nút 1 biểu diễn sự kiện bắt đầu dự án. Cung đi ra từ nút 1 thể hiện

2. Có một nút thể hiện sự hoàn thành dự án (nút kết thúc) 3. Đánh số các nút trong mạng để nút thể hiện điểm hoàn thành của một hoạt động luôn có số lớn hơn nút thể hiện điểm bắt đầu của hoạt động đó.

4. Một hoạt động không thể hiện bởi nhiều hơn một cung trong mạng 5. Hai nút chỉ nối với nhau bởi tối đa 1 cung.

l Để tránh vi phạm quy tắc 4 &5, đôi khi cần sử dụng các

Hoạt động Hđ trước Thời gian (ngày) A: đào tạo công nhân - 6

Mô hình hóa

hoạt động giả có thời gian thực hiện bằng không. B: mua nguyên liệu C: SX sản phẩm 1 D: SX sản phẩm 2 E: thử nghiệm sản phẩm 2 F: lắp ráp sản phẩm 1&2 - A, B A, B D C, E 9 8 7 10 12

Biểu đồ mạng

Thời gian bắt đầu sớm ET(i)

l Biểu đồ dự án Widgetco C (8)

l Thời gian bắt đầu sớm của nút i, ET(i), là thời điểm sớm nhất mà sự kiện ứng với nút i có thể diễn ra. l Để tìm thời gian bắt đầu sớm của mỗi nút mạng:

– Tìm các sự kiện tiền đề trực tiếp của nút i (là nút được

Hđộng giả

– cộng thời gian của mỗi hoạt động tiền đề với giá trị ET

F (12) 3 5 6 A (6) D (7) nối bằng một cung tới nút i) 1 E (10)

– ET(i) bằng giá trị lớn nhất của các tổng vừa tính

B (9) của mỗi sự kiện tiền đề của nút i, 2 4

Mô hình hóa

Nút 1 = bắt đầu Nút 6 = kết thúc

Thời gian bắt đầu muộn LT(i)

Ví dụ - Tính LT(i)

– Từ biểu đồ ta biết thời gian hoàn thành muộn của nút 6

l Thời gian bắt đầu muộn của nút i, LT(i), là thời điểm chậm nhất mà sự kiện ứng với nút i có thể diễn ra mà không làm ảnh hưởng đến thời gian hoàn thành dự án.

– Do nút 6 là nút kế tiếp duy nhất của nút 5, nên

l Để tính LT(i) ta bắt đầu từ nút kết thúc và tính

là ngày 38.

– Nút 4 và 5 là các nút kế tiếp của nút 3, do vậy

ngược lại: – Tìm mỗi nút xảy ra sau nút i và được nối trực tiếp với nút i bởi một cung. Những sự kiện này là sự kiện kế tiếp của nút i.

– Trừ thời gian thực hiện của hoạt động kế tiếp của nút i

LT(5)=LT(6)-12=26. Tương tự LT(4)= LT(5)-10=16.

– LT(i) là giá trị nhỏ nhất trong các giá trị vừa tính

Mô hình hóa

từ giá trị LT(i) của sự kiện kế tiếp của nút i.

l Tính ET(i) & LT(i) cho bài toán Widgetco

Tính toán đường găng l Khái niệm độ tự do tổng của một hoạt động (i,j), TF(i,j), của là thời gian mà thời điểm bắt đầu của hoạt động (i,j) có thể lui lại kể từ điểm bắt đầu sớm nhất của nó mà không làm chậm thời điểm hoàn thành dự án.

l Một hoạt động có TF=0 là một hoạt động găng l Đường nối từ nút 1 đến nút kết thúc mà chỉ gồm

toàn các hoạt động găng gọi là đường găng l Đường găng của ví dụ Widgetco là 1-2-3-4-5-6.

Mô hình hóa

Nút 1 2 3 4 5 6 ET(i) 0 9 9 16 26 38 LT(i) 0 9 9 16 26 38

Công cụ LP

Bài tập ứng dụng

l Dùng LP để tính toán chiều dài đường găng:

– Biến ra quyết định : xj – thời gian diễn ra sự kiện ứng

– Mục tiêu là giảm thiểu thời gian cần để hoàn thành dự

với nút j

– Với mỗi hoạt động (i,j), trước khi j diễn ra thì i phải

án, Z = xF-x1

l LP còn có thể dùng để xác định phương án phân bổ các nguồn lực của dự án để hoàn thành dự án với chi phí nhỏ nhất trong trừơng hợp cần hoàn thành dự án trong thời gian ngắn hơn chiều dài của đường găng (crashing)

Mô hình hóa

145

diễn ra và hoạt động (i,j) đã hoàn thành

Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý ***

Chương 5. Bài toán Biến nguyên (IP)

MÔ HÌNH HÓA

HỆ THỐNG SẢN XUẤT

TS. Đặng Vũ Tùng

1. Đặc tính của mô hình IP 2. Giải mô hình IP: phương pháp B&B 3. Một số Bài toán điển hình: 1. Lập tiến độ chạy máy 2. Bài toán Set-covering 3. Bài toán Chi phí cố định 4. Bài toán kế hoạch sản xuất 5. Bài toán Knap-sack 6. Bài toán TSP

Hànội - 2014

Mô hình hóa

147

Lập mô hình

Biến ra quyết định: thể hiện phương án lựa chọn cho người ra quyết định, trong trường hợp này là lượng sơn SX

5.1. Ví dụ 5.1 Bài toán cơ cấu sản phẩm Công ty R. sản xuất 2 loại sơn tường : sơn trong nhà (giá bán 20 tr.đ/bồn) và sơn ngoài nhà (giá bán 30 tr.đ/bồn).

– –

Xt = số bồn sơn trong nhà sản xuất mỗi ngày Xn = số bồn sơn ngoài trời sản xuất mỗi ngày

Hai nguyên liệu chủ yếu A và B được cung cấp tối đa 6 tấn A và 8 tấn B mỗi ngày. Sản xuất 1 bồn sơn trong nhà cần 2 tấn nguyên liệu A và 1 tấn nguyên liệu B, trong khi 1 bồn sơn ngoài trời cần 1 tấn A và 2 tấn B.

l 3. l

Hàm mục tiêu: thể hiện đích mà mô hình muốn hướng tới, tức là tối đa hóa tổng doanh thu từ việc bán lượng sơn đã SX ra: Z = 20 xt + 30 xn. Hàm mục tiêu: Max z = 20 xt + 30 xn. Các điều kiện ràng buộc: Hạn chế về mức độ sử dụng từng loại nguyên liệu (A, B) : (nguyên liệu A) (nguyên liệu B)

– –

2xt + xn  6 xt + 2xn  8

Hạn chế về nhu cầu thị trường của hai loại sơn, : (chênh lệch giữa 2 loại sơn) (sơn trong nhà)

xt - xn  1  2 xt

Nghiên cứu thị trường => nhu cầu tối đa 2 bồn sơn trong nhà /ngày; nhu cầu sơn trong nhà không được nhiều hơn nhu cầu sơn ngoài trời quá 1 bồn / ngày. Công ty R. nên sản xuất bao nhiêu bồn sơn mỗi loại để đạt doanh thu lớn nhất? (Số bồn sơn phải nguyên.)

– – Các biến nguyên & không âm: xt  0; xn  0; xt , xn = nguyên

Mô hình hóa

148

Mô hình hóa

149

Mô hình IP cho bài toán

max: thỏa mãn:

5.2. Khái niệm l Bài toán biến nguyên (integer programming - IP) là một bài toán qui hoạch trong đó một số hoặc toàn bộ các biến phải nhận giá trị nguyên và không âm.

l Bài toán biến nguyên tuyến tính (integer linear

programming - ILP) là một bài toán qui hoạch tuyến tính (LP) trong đó một số hoặc toàn bộ các biến phải nhận giá trị nguyên và không âm.

z = 20xt + 30xn 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt , xn : nguyên

l Nếu trong bài toán có ít nhất một quan hệ phi tuyến và có biến cần nhận giá trị nguyên thì ta có một bài toán biến nguyên phi tuyến (integer nonlinear programming - INP).

Mô hình hóa

150

Mô hình hóa

151

Khái niệm (2) l Bài toán IP mà tất cả các biến đều phải là có giá trị

Nới lỏng về tuyến tính l Bài toán IP giải khó hơn bài toán LP rất nhiều -

nguyên gọi là bài toán IP thuần túy (pure IP).

miền nghiệm rời rạc

l Bài toán IP trong đó chỉ có một số biến đòi hỏi giá trị

nguyên gọi là bài toán IP hỗn hợp (mixed IP).

l Bài toán LP thu được khi loại bỏ tất cả các ràng buộc về điều kiện nguyên hoặc 0-1 đối với các biến của một bài toán IP được gọi là sự nới lỏng về tuyến tính cho bài toán IP.

l Bài toán IP trong đó tất cả các biến đều bằng 0 hoặc 1 được gọi là bài toán IP 0-1 (binary IP hay IP nhị phân).

l Nghiệm của bài toán IP không bao giờ “tốt hơn”

nghiệm của bài toán LP nới lỏng tương ứng

l Một bài toán IP luôn có thể biến đổi đưa về bài toán

IP nhị phân

Mô hình hóa

152

Mô hình hóa

153

Thực hiện phương pháp B&B

Phương pháp B&B

l Chọn biến để rẽ nhánh:

l Phương pháp B&B: giải bài toán LP, sau đó bổ

– Bất kỳ hoặc rẽ nhánh theo biến có ý nghĩa kinh tế quan trọng nhất (có đóng góp lớn nhất vào hàm mục tiêu) l Điều kiện dừng rẽ nhánh: Một bài toán con (LP) sẽ

sung dần các điều kiện rẽ nhánh theo các biến có giá trị không nguyên trong nghiệm tối ưu của bài toán LP.

l Bản chất là liệt kê (enumeration) toàn bộ các điểm nghiệm trong miền nghiệm nguyên, loại bỏ chúng cho đến khi chỉ còn lại nghiệm nguyên tối ưu.

không cần phải tiếp tục rẽ nhánh khi bài toán con đó : – không có nghiệm – có nghiệm tối ưu với tất cả các biến đều nhận giá trị nguyên – có giá trị z của nghiệm tối ưu không tốt hơn giới hạn dưới

Mô hình hóa

154

Mô hình hóa

155

(LB) hiện có (với bài toán maximization)

Thực hiện phương pháp B&B

Giải Bài toán Hỗn hợp Sản phẩm (vd 5.1) bằng B&B

l Qui tắc chọn nhánh rẽ :

– Back-tracking: rẽ nhánh theo bài toán con tạo ra gần nhất – Jump-tracking: rẽ nhánh theo bài toán con có giá trị z tốt

Bài toán con No.1 (LP relaxation): max: z = 20xt + 30xn thỏa mãn:

l Cập nhật giá trị nghiệm tối ưu:

– Cập nhật giá trị z tốt nhất hiện thời làm giới hạn xét các bài toán con tiếp theo (giới hạn dưới LB với bài toán max.)

2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0

l Quá trình kết thúc khi:

– Toàn bộ các bài toán con đã được dừng rẽ nhánh – Nghiệm của bài toán IP chính là nghiệm tốt nhất hiện có

Nghiệm tối ưu: l xt = 11/3 , xn = 31/3 l Doanh thu max tương ứng là z1 = 126 2/3

Mô hình hóa

156

Mô hình hóa

157

nhất hiện có

Rẽ nhánh theo xt :

Bài toán con No.2 = No1 + điều kiện xt  1 : max:z = 20xt + 30xn thỏa mãn:

z = 20xt + 30xn

Rẽ nhánh theo xt : Bài toán con No.3 = No1 + điều kiện xt  2 : max: thỏa mãn:

 2

l l Doanh thu max tương ứng là z2 = 125

2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0  1 xt Nghiệm tối ưu: xt = 2 , xn = 2 xt = 1 , xn = 3.5

Mô hình hóa

158

Mô hình hóa

159

2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt Nghiệm tối ưu: l l Doanh thu max tương ứng là z3 = 100 => ứng viên nghiệm tối ưu; LB=100

Rẽ nhánh theo xn :

z = 20xt + 30xn

2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0  1 xt  3 xn

2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt  1 xn  4

Bài toán con No.4 = No2 + điều kiện xn  3: max: thỏa mãn: Bài toán con No.5 = No2 + điều kiện xn  4 : max: thỏa mãn:

xt = 1 , xn = 3 xt = 0 , xn = 4

Mô hình hóa

160

Mô hình hóa

161

Nghiệm tối ưu: l l Doanh thu max tương ứng là z4 = 110 => ứng viên nghiệm tối ưu; LB=110 Nghiệm tối ưu: l l Doanh thu max tương ứng là z5 = 120 => ứng viên nghiệm tối ưu; LB=120

Ví dụ 5.2. Bài toán lập tiến độ chạy máy (machine scheduling)

Bài toán xác định trình tự chạy máy (job sequencing)

l Nếu 4 công việc được thực hiện theo trình tự 1-2-3-4, thì tổng

thời gian trễ hạn sẽ là 16 ngày.

l Bốn công việc cần được gia công trên một thiết bị. Thời gian cần để thực hiện mỗi việc và thời hạn hoàn thành của chúng như trong bảng dưới đây. Thời gian trễ hạn tính bằng số ngày kể từ khi hết hạn đến khi việc được hoàn thành (hoàn thành trước hoặc đúng hạn thì thời gian trễ hạn bằng 0). Vậy phải thực hiện các việc trên theo trình tự nào để tổng thời gian trễ hạn là thấp nhất.

Thời gian hoàn thành Số ngày trễ hạn Việc 1 6 0 Thời gian thực hiện Thời hạn hoàn thành

Mô hình hóa

163

162

2 3 4 6 + 4 = 10 10 + 5 = 15 15 + 8 = 23 10 – 4 = 6 15 – 12 = 3 23 – 16 = 7 Tổng thời gian trễ D = 0+6+3+7 = 16 ngày Việc 1 2 3 4 6 ngày 4 ngày 5 ngày 8 ngày Cuối ngày 8 Cuối ngày 4 Cuối ngày 12 Cuối ngày 16

Giải bằng phương pháp B&B

Kế hoạch gia công

x14=1

x24=1

x34=1

x44=1

l Để xác định trình tự thực hiện công việc, đặt: xij = 1 nếu việc i được thực hiện ở thứ tự j

= 0 nếu khác

D≥15

D≥19

D≥11

D≥7

l Thực hiện phương pháp B&B bằng cách phân

x13=1

x23=1

x43=1

x13=1

x23=1

x33=1

vùng các nghiệm theo việc được thực hiện cuối cùng.

D≥21

D≥25

D≥13

D≥14

D≥18

D≥10

l Ta có trong nghiệm thu được: hoặc x14 = 1, hoặc

x12=1

x22=1

x24 = 1, hoặc x34 = 1, hoặc x44 = 1 => rẽ nhánh theo việc hoàn thành cuối cùng

D=12

D=16

Mô hình hóa

164

Mô hình hóa

165

Ví dụ 5.3. Bài toán Set-covering

Bài toán tổng quát về xác định trình tự chạy máy

l Bài toán trong đó các phần tử của một tập hợp A (Set A) phải được “phục vụ” (covered) bởi ít nhất một phần tử thuộc một tập hợp B khác (Set 2). Mục tiêu của bài toán là tối thiểu hóa số lượng phần tử B cần dùng để phục vụ được tất cả các phần tử A.

l n công việc cần được gia công trên một thiết bị l Yêu cầu về trình tự gia công đối với một số việc l Yêu cầu về thời điểm bắt đầu gia công đối với một số việc l Thời gian cần để gia công việc i là ai l Thời hạn cần hoàn thành việc i là di l 1. Phải thực hiện các việc trên theo thứ tự nào để đảm bảo thời hạn hoàn thành của các việc, và trong thời gian ngắn nhất ? l 2. Một số việc được phép hoàn thành trễ hạn. Phải thực hiện

l Bài toán loại này được ứng dụng trong nhiều lĩnh vực, chẳng hạn lập kế hoạch điều động phi hành đoàn / chuyến bay, điều động xe (routing), thiết lập mạng lưới đại lý, v.v.

Mô hình hóa

166

Mô hình hóa

167

các việc trên theo trình tự nào để tổng thời gian trễ hạn là thấp nhất ?

Bài toán Set-covering

l Gợi ý đặt biến xi =1 nếu đặt trạm tại quận i

10 20 30 30 20

= 0 nếu không đặt

25 35 20 10

15 30 20

15 25

l Hàm mục tiêu: Min z = ? l Ràng buộc đảm bảo có ít nhất một trạm trong vòng 15’ chạy xe từ mỗi quận: ?

l Thành phố A cần xác định số điểm tối thiểu để xây dựng các trạm cấp cứu tại trung tâm các quận để đảm bảo phục vụ tất cả các quận trong vòng 15’ kể từ khi có yêu cầu. Khoảng cách chạy xe giữa các quận như trong bảng. Hãy xác định số trạm cấp cứu cần xây và địa điểm đặt chúng.

168

Mô hình hóa

169

Ví dụ 5.4. Bài toán Chi phí cố định

Bài toán Chi phí cố định

l Một sản phẩm có thể được sản xuất trên 4 cỗ máy khác

l Đặt xi = số SP làm bằng máy i l Hàm mục tiêu: min tổng chi phí cđịnh + bđổi:

l Ràng buộc:

min z =  Fi * yi +  Vi*xi

nhau. Mỗi máy có chi phí khởi động (cố định), chi phí gia công (biến đổi theo sản phẩm), và công suất tối đa như trong bảng. Cần phải SX tổng cộng 2000 đơn vị sản phẩm. Hỏi bố trí sản xuất thế nào để giảm thiểu chi phí.

Máy Công suất Pi

– xi <= Pi max (CS tối đa) –  Xi = 2000 (đáp ứng nhu cầu) – Nếu xi >0 thì có chi phí cố định (yi=1) – xi nguyên, không âm – yi = 0 , 1

1 Chi phí khởi động Fi 1000 Chi phí gia công Vi 20 900

Mô hình hóa

171

170

Nhiều bài toán logistic và sản xuất có thể mô hình hóa dưới dạng bài toán biến nguyên chi phí cố định 920 800 700 24 16 28 1000 1200 1600 2 3 4 Mô hình hóa

Điều kiện Nếu-Thì

Ví dụ 5.5. Bài toán kế hoạch SX l Cty Dorian sản xuất 3 loại ôtô: cỡ nhỏ-trung-lớn. Các

l Nếu ràng buộc f(xi) > 0 thỏa mãn thì ràng buộc g(xi) ≥

l Ngược lại, nếu ràng buộc f(xi) > 0 không thỏa mãn thì

0 cũng phải thỏa mãn

ràng buộc g(xi) ≥ 0 có thể không thỏa mãn nguồn lực cần thiết và lợi nhuận tương ứng khi SX xe mỗi loại như trong bảng. Hiện tại Cty có thể huy động 6000 tấn thép & 60.000 h lao động. Để SX 1 loại xe nhất định đạt hiệu quả kinh tế thì phải làm tối thiểu 1000 chiếc. Lập mô hình IP để giải bài toán.

l Ta có thể biểu diễn quan hệ này bằng cách đưa vào biến nhị phân y và thể hiện bằng cặp 2 ràng buộc:

Cỡ nhỏ Cỡ trung Cỡ lớn

1,5 tấn Thép 3 tấn 5 tấn

Lao động 30 h 25 h 40 h

Mô hình hóa

172

Mô hình hóa

173

f(xi) ≤ M.y, -g(xi) ≤ M(1-y), y = 0 hoặc 1 Lãi $2000 $3000 $4000

Bài toán kế hoạch SX

Điều kiện Hoặc-Hoặc

l Hoặc ràng buộc f(xi) ≤ 0 phải thỏa mãn hoặc ràng buộc

l Ta có thể biểu diễn quan hệ này bằng cách đưa vào biến nhị phân y và thể hiện bằng cặp 2 ràng buộc:

l Gọi lượng xe mỗi loại sẽ SX là xi l Hàm mục tiêu (1000 $): max z=2x1+3x2+4x3 l Ràng buộc về nguyên liệu thép: 1.5x1+3x2+5x3≤ 6000 l Ràng buộc về giờ lao động: 30x1+25x2+40x3≤ 60000 l Ràng buộc về lượng xe SX cỡ nhỏ: x1≤ 0 hoặc x1≥ 1000 l Ràng buộc về lượng xe SX cỡ trung: x2≤ 0 hoặc x2≥ 1000 l Ràng buộc về lượng xe SX cỡ lớn: x3≤ 0 hoặc x3≥ 1000

g(xi) ≤ 0 phải thỏa mãn

Mô hình hóa

174

Mô hình hóa

175

f(xi) ≤ M.y, g(xi) ≤ M(1-y), y = 0 hoặc 1

Ví dụ 5.6. Bài toán Knap-sack l NASA cần xác định

Biến thể của Bài toán Knap-sack l Knap-Sack (Xếp đồ vào túi) đơn (single dimension) là bài

Đồ vật 1

Lợi ích 10

Trọng lượng 3

l Knap-Sack đa chiều là bài toán có nhiều hơn một ràng buộc, chẳng hạn ràng buộc về thể tích của các vật.

l Knap-Sack 0-1 (nhị phân) là bài toán trong đó mỗi biến chỉ

toán IP có dạng: – Max z =  ci xi – Thmãn: ai xi ≤ bi – xi nguyên

l Giải bằng phương pháp Branch & Bound hoặc Dynamic

trong 3 loại đồ vật cần mang lên tàu vũ trụ nên mang bao nhiêu chiếc mỗi loại. Trọng lượng và lợi ích của đồ vật nêu trong bảng. Được phép mang lên tàu tối đa 26 kg đồ vật. Nên mang những vật nào để có lợi nhất?

được nhận giá trị 0 hoặc 1 (mỗi đồ vật chỉ được lấy 1 chiếc)

Mô hình hóa

177

Mô hình hóa

178

Programming

Ví dụ 5.7. Bài toán người giao hàng (TSP)

Các thuật toán Heuristic l Khi việc tìm nghiệm tối ưu là không thể /

không hiệu quả (vd bài toán TSP)

l Khi sai số nằm trong giới hạn chấp nhận

được (vd mô hình EOQ)

l Khi yêu cầu cần nhanh chóng xác định

phương án đủ “tốt”

l Một người xuất phát tại 1 điểm cần đi thăm n điểm khác nhau trước khi quay về điểm xuất phát. Anh ta phải đi theo trình tự nào để giảm thiểu tổng khoảng cách cần đi. l Số phương án có thể: n! l Giải bằng B&B l Giải bằng Heuristics: lân cận gần nhất (nearest neighbor); chèn rẻ nhất (cheapest insertion)

l => Sử dụng giải thuật xây dựng riêng cho bài toán (mỗi giải thuật có chất lượng nghiệm khác nhau)

Mô hình hóa

179

Mô hình hóa

180