MỘT HTX VẬN CHUYỂN CÓ 5 HỢP ĐỒNG. TIỀN LỜI CÁC XE KHI THỰC HIỆN CÁC HỢ...
Bài 4:
Một HTX vận chuyển có 5 hợp đồng. Tiền lời các xe khi thực hiện các hợp đồng như sau:
Đơn vị tính : 100 000 đ
Xe
HĐ 1
HĐ 2
HĐ 3
HĐ 4
HĐ 5
A
7
6
8
9
8
B
10
8
9
6
7
C
8
10
9
8
10
D
9
9
10
8
9
E
8
7
6
7
6
a/
Hãy phân công nhiệm vụ cho các xe
Nhận thấy phân công nhiệm vụ cho các xe để tiền lời lớn nhất => bài toán cực đại
Ta có :
-7
-6
-8
-9
-8
2
3
1
0
1
-10
-8
-9
-6
-7
0
2
1
4
3
-8
-10
-9
-8
-10
2
0
1
2
0
-9
-9
-10
-8
-9
1
1
0
2
1
-8
-7
-6
-7
-6
0
1
2
1
2
2
3
1
0
1
0
2
1
4
3
2
0
1
2
0
1
1
0
2
1
0
1
2
1
2
2
3
1
0
1
2
2
1
0
0
0
2
1
4
3
0
1
1
4
2
2
0
1
2
0
3
0
2
3
0
1
1
0
2
1
1
0
0
2
0
0
1
2
1
2
0
0
2
1
1
Vậy nhiệm vụ của các xe là :
Xe A nhận HĐ 4
Xe B nhận HĐ 1
Xe C nhận HĐ 5
Xe D nhận HĐ 3
Xe E nhận HĐ 2
Tiền lời lớn nhất các xe nhận được : 900 000 + 1 000 000 + 1 000 000 + 1 000 000 + 700 000 = 4 600 000 đ
b/
Phân công nhiệm vụ với điều kiện lời cho các xe phải > 700 000 đ
Đây là dạng bài toán có ô cấm ( /81/ lý thuyết chương 6)
NTP_VB2K16B_QT01
Page 25
X
X
-8
-9
-8
-10
-8
-9
X
X
-8
-10
-9
-8
-10
-9
-9
-10
-8
-9
-8
X
X
X
X
Nhận thấy ở ma trận trên thì xe E chỉ có thể nhận HĐ 1 nên ta có
X
-8
-9
-8
X
1
0
1
-8
-9
X
X
1
0
X
X
-10
-9
-8
-10
0
1
2
0
-9
-10
-8
-9
1
0
2
1
X
1
0
1
X
1
0
0
1
0
X
X
0
0
X
X
0
1
2
0
0
2
3
0
1
0
2
1
0
0
2
0
Đến đây ta có các trường hợp :
Nếu ta chọn xe B là hợp đồng 2 thì
X
1
0
0
0
0
X
X
0
2
3
0
0
0
2
0
Xe A nhận HĐ 4
Xe B nhận HĐ 2
Xe C nhận HĐ 5
Xe D nhận HĐ 3
Xe E nhận HĐ 1
Tổng lợi nhuận : 900 000 + 800 000 + 1 000 000 + 1 000 000 + 800 000 = 4 500 000 đ
Nếu ta chọn xe B nhận HĐ 3 thì
Đến lúc này thì ta lại có 2 trường hợp:
Xe C nhận HĐ 2 và xe D nhận HĐ 5
=>
Xe A nhận HĐ 4
Xe B nhận HĐ 3
Xe C nhận HĐ 2
Xe D nhận HĐ 5
Tổng lợi nhuận : 900 000 + 900 000 + 1 000 000 + 900 000 + 800 000 = 4 500 000 đ
NTP_VB2K16B_QT01
Page 26
Xe C nhận HĐ 5 và xe D nhận HĐ 2
Xe D nhận HĐ 2
Vậy có 3 cách sắp xếp các xe để thỏa đề :
Trường hợp 1
Xe A nhận HĐ 4
Trường hợp 2
Trường hợp 3
c/
Giả sử có thêm HĐ thứ 6 với mức tiền lời tương ứng là 10, 9, 8, 11, 10 thì công ty nên từ chối HĐ nào
Vì có 5 xe mà có 6 HĐ nên không thể xây dựng ma trận đơn vị, nên ta
Giả sử có thêm xe F có tiền lời = 0
Xe
HĐ 1
HĐ 2
HĐ 3
HĐ 4
HĐ 5
HĐ 6
A
7
6
8
9
8
10
B
10
8
9
6
7
9
C
8
10
9
8
10
8
D
9
9
10
8
9
11
E
8
7
6
7
6
10
F
0
0
0
0
0
0
NTP_VB2K16B_QT01
Page 27
-7
-6
-8
-9
-8
-10
3
4
2
1
2
0
-10
-8
-9
-6
-7
-9
0
2
1
4
3
1
-8
-10
-9
-8
-10
-8
2
0
1
2
0
2
-9
-9
-10
-8
-9
-11
2
2
1
3
2
0
-8
-7
-6
-7
-6
-10
2
3
4
3
4
0
0
0
0
0
0
0
0
0
0
0
0
0
3
4
2
1
2
0
0
2
1
4
3
1
2
0
1
2
0
2
2
2
1
3
2
0
2
3
4
3
4
0
0
0
0
0
0
0
3
4
2
1
2
0
3
3
1
0
1
0
0
2
1
4
3
1
0
1
0
3
2
1
2
0
1
2
0
2
3
0
1
2
0
3
2
2
1
3
2
0
2
1
0
2
1
0
2
3
4
3
4
0
2
2
3
2
3
0
0
0
0
0
0
0
1
0
0
0
0
1
Đến đây có thể thấy các số 0 tạo thành vòng tròn nên ta có thể chọn 2 cách
Cách 1 : chọn số 0 ở vị trí dòng 3, cột 2
Cách 2 : chọn số 0 ở vị trí dòng 6, cột 2
Vậy xe F có thể rơi vào 2 trường hợp : hoặc là HĐ 2 hoặc là HĐ 5
Vậy ta có thể từ chối HĐ 2 hoặc HĐ 5