_64 _CÓ 3 CÔNG NHÂN CÓ THỂ LÀM 3 VIỆC VỚI SỐ GIỜ NHƯ SAU
Bài 1:
_64 _Có 3 công nhân có thể làm 3 việc với số giờ như sau : (Đvị tính :giờ)
CV
X
Y
Z
CN
A
13
10
16
B
15
8
14
C
15
10
12
Phân công mỗi CN làm mỗi việc để tổng thời gian là min
Cần xem kĩ lý thuyết của thầy ( 78/ lý thuyết chương 6)
Bài toán này thuộc bài toán cực tiểu
Các bước giải :
Bước 1 : lập ma trận
Bước 2 : trên các hàng của ma trận xác định phân tử nhỏ nhất rồi lấy các phân tử trên hàng trừ đi phân tử
này.
13
10
16
3
0
6
15
8
14
7
0
6
15
10
12
5
0
2
Bước 3 : tương tự bước 2 thực hiện trên cột
3
0
6
0
0
4
7
0
6
4
0
4
5
0
2
2
0
0
Bước 4, 5 : Trên các hàng ( cột) của ma trận, chọn hàng (cột) có 1 số 0, đánh dấu số 0 đó rồi gạch bỏ
cột(hàng)
0
0
4
C
4
0
4
p
C
2
0
0
p
Bước 6 : Kiểm tra xem số 0 được đánh dấu có bằng n chưa? Nếu bằng thì bài toán đã được giải xong,
nếu chưa ta thực hiện tiếp bước 7
Bước 7 : Trên các phân tử chưa bị gạch, xác định phần tử nhỏ nhất.
Đối với các phần tử bị gạch 2 đường thì cộng với phân tử này
Chưa bị gạch thì trừ phân tử này
Bị gạch 1 gạch thì giữ nguyên. Sau đó trở lại bước 4
Như vậy :
A làm công việc X
B làm công việc Y
C làm công việc Z
Tổng thời gian làm việc nhỏ nhât là : 13 + 7 + 14 = 34 giờ
NTP_VB2K16B_QT01
Page 22