ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA ĐIỆN – ĐIỆN TỬ

BÁO CÁO THÍ NGHIỆM KỸ THUẬT RA
QUYẾT ĐỊNH
BÀI 2: GIẢI BÀI TOÁN VẬN TẢI BẰNG EXCEL VÀ
MATLAB
GVHD:
Nhóm:
Họ và tên

Mã số sinh viên

1.
2.
3.
4.

TP.HCM, Tháng 8 Năm 2018


MỤC LỤC
I. Phương pháp giải bài toán vận tải………………………………..………………………1
1) Bước 1: Tìm phương án xuất phát………………………………….….………………1
2) Bước 2: Kiểm tra tính tối ưu của một phương án…………….….…………...2
3) Bước 3: Tìm phương án mới tốt hơn…………………………………..….………….2

II. Qui trình giải bài toán vận tải bằng Excel và Matlab……..………………2
1) Thực hiện bằng Excel……………………………………………………….….………………2
2) Thực hiện bằng Matlab………………………………………………………………….……7

III. Một số ví dụ và kết quả………………………………………………..………………………8
1) Ví dụ 1…………………………………………………………………...………………………………8
2) Ví dụ 2………………………………………………………………………………………………….11
3) Ví dụ 3………………………………………………………………………………………………….14
4) Ví dụ 4…………………………………………………………………………………………….……16


I. Phương pháp giải bài toán vận tải:
Bài toán vận tải (transportation problem) là một dạng của bài toán quy hoạch tuyến tính.
Để giải quyết bài toán này, ta sử dụng thuật toán thế vị, bao gồm các bước như sau:
 Bước 1: Tìm phương án xuất phát;
 Bước 2: Kiểm tra tính tối ưu của một phương án, nếu:
+ Tối ưu: đi đến kết luận;
+ Chưa tối ưu: đi đến bước 3;
 Bước 3: Tìm phương án mới tốt hơn, quay lại bước 2.
Gọi:

xij

là lượng hàng vận chuyển từ điểm phát thứ i đến điểm thu thứ j.

cij

là chi phí vận chuyển một đơn vị hàng từ điểm phát thứ i đến điểm thu thứ j.

Ta có:

cij .xij


là chi phí vận chuyển từ điểm phát i đến điểm thu j.

�cij .xij

là tổng chi phí vận chuyển (hàm mục tiêu).

Nhiệm vụ của bài toán là tối ưu hóa chi phí vận chuyển bằng cách tìm min của hàm mục tiêu.

1) Bước 1: Tìm phương án xuất phát:
Việc tìm phương án xuất phát, ta thường sử dụng một trong ba qui tắc sau:
+ Qui tắc góc Tây Bắc (North – West Corner Rule);
+ Qui tắc chi phí nhỏ nhất (Least – Cost Rule);
+ Qui tắc Voghel.
Ở đây, ta sẽ đề cập đến qui tắc chi phí nhỏ nhất theo quy trình sau:
+ Tìm ô có chi phí nhỏ nhất;
+ Phân phối lượng hàng hóa tối đa có thể vào ô đó;
+ Loại bỏ dòng hay cột đã phân phối đủ hàng hóa;
+ Tiếp tục quá trình cho đến khi phân phối hết hàng.
Sau khi kết thúc quá trình phân phối hàng hóa vào bảng, ta cần liệt kê biến tại các ô
không có hàng hóa (bằng 0) là biến không cơ sở, ngược lại ở những ô có hàng hóa (lớn
hơn 0) là biến cơ sở.
1


2) Bước 2: Kiểm tra tính tối ưu của một phương án: (Using u – v Method).
u  v j  cij
�
�i
;  i, j: xij  0
�

u

0
ui
vj
�
 Tìm các hệ số và sao cho: � 1
(tính theo biến cơ sở).

 Tính

c%
ij  cij  (ui  v j ); i, j : xij  0

c% �0
�
� ij
�
 c%  0
� ij
 Tiêu chuẩn tối ưu: �

(tính theo biến không cơ sở).

� ph�
�
ng �
n t�
i�
u

� ph�
�
ng �
n ch�
a t�
i�
u

(đối với tìm min).

3) Bước 3: Tìm phương án mới tốt hơn:
+ Chọn ô có

c%
ij
âm nhất đối với bài toán tìm min (dương nhất đối với bài toán tìm

max) làm ô xuất phát.
+ Từ ô có

c%
x 0
ij
âm nhất và các ô có ij
(biến cơ sở), tạo một vòng chu trình, di

chuyển 1 lượng hàng hóa trong chu trình và lập lại bảng mới. Quay lại bước 2 để kiểm
tra tính tối ưu của bảng mới này.

II. Qui trình giải bài toán vận tải bằng Excel và Matlab:

1) Thực hiện bằng Excel:
Cũng như giải bài toán tuyến tính bằng thuật toán đơn hình, ở bài toán vận tải trên
Excel ta cũng bắt đầu bằng việc cài đặt công cụ

.

Chọn File  Options  Add – ins  Go…: hộp thoại Add – ins xuất hiện, ta tích
chọn vào ô Solver Add – in và click OK, như hình sau:

2


E1

Xét ví dụ
(với kết quả tính
tay):

W1

5

W2

35

W3

0


E2
3
4
5

0

5

15

5

5

40

E3

6

30
0

E4
5
6

0


7

0

6

0

7

20

20

30

20

cij

, nhập tiếp các biến

xij

7

35

bằng


50
25

Ta thực hiện lại trên Excel như sau:
+ Nhập lại bảng ví dụ trên vào Excel:

+ Các ô số màu xanh tương ứng với

có giá trị là 0

như hình:

3


+ Tiếp theo là hàm mục tiêu, ta nhập vào ô F12 =SUMPRODUCT(F8:I10,F4:I6)
hoặc có thể dùng chuột kéo:

+ Đến ràng buộc bên phía W, tại ô E14 nhập =SUM(F8:I8), tương tự cho ô E15
là =SUM(F9:I9) và ô E16 là =SUM(F10:I10)

4


+ Và cuối cùng là ràng buộc bên phía E, ở ô F14 nhập =SUM(F8:F10), ô G14
nhập =SUM(G8:G10), ô H14 nhập =SUM(H8:H10) và ô I14 nhập =SUM(I8:I10)

5



Tiến hành chọn Data 

để mở hộp thoại Solver Parameters và cấu hình như

sau:
 Set Objective: $F$12 (chứa giá trị của hàm mục tiêu)
 To: tích chọn Min (bài toán tìm min)
 By Changing Variable Cells: $F$8:$I$10 (danh sách các biến

xij

)

 Subject to the Constraints: click Add để mở hộp thoại Add Constraints (ràng buộc)

(nhập như hình và click Add, tương tự cho các ràng buộc khác: $E$15=$E$5, $E$16=$E$6,
$F$14=$F$3, $G$14=$G$3, $H$14=$H$3, $I$14=$I$3).
+ Cuối cùng click Solve để giải quyết bài toán:

6


+ Ta có kết quả như sau:

2) Thực hiện bằng Matlab:
7


+ Để giải bài toán vận tải trên Matlab, ta tạo file CostMin.m với source code được
đính kèm. Sau khi Run file CostMin.m, tiến hành nhập các ma trận vào Command

Window theo yêu cầu như sau:
 Ma trận chi phí (kích thước m*n)
 Ma trận cung cấp (kích thước m*1)
 Ma trận nhu cầu (kích thước 1*n)
+ Yêu cầu bài toán: tổng nguồn cung cấp phải bằng tổng lượng nhu cầu
+ Xét ví dụ trên phần Excel:

Cũng như Excel, Matlab cũng thu được chi phí nhỏ nhất là 550, cùng với bảng
phân phối như hình.

8


III. Một số ví dụ và kết quả:
1) Ví dụ 1:
Một xe container của công ty sản xuất gạo An Bình vận chuyển gạo từ kho Quận 8,
Thủ Đức, Dĩ An đến 4 cửa hàng bán lẻ Ngọc Trâm, Thạch Thảo, Như Phương, Minh
Thoa.
Kho Quận 8 cần vận chuyển đi 140kg gạo, kho Thủ Đức vận chuyển 55kg và kho Dĩ
An vận chuyển 85kg gạo.
Cửa hàng bán lẻ Ngọc Trâm cần nhập về 60kg gạo, cửa hàng Thạch Thảo cần 90kg,
cửa hàng Như Phương cần 70kg và Minh Thoa cần 60kg gạo để bán.
Chi phí vận chuyển (1000đ/kg) gạo từ mỗi kho đến mỗi cửa hàng cho trong bảng sau:
Cửa hàng
Kho
Quận 8
Thủ Đức

Ngọc Trâm


Thạch Thảo

Như Phương

Minh Thoa

6

8

8

10

8

12

10

9

Dĩ An
12
12
14
16
Công ty An Bình cần phân phối gạo từ các kho đến các cửa hàng như thể nào để tổng
chi phí vận chuyển là thấp nhất và tính chi phí đó?
a) Giải trên Excel:

+ Sau khi nhập các hàm SUMPRODUCT và SUM ta có bảng sau:

9


+ Cấu hình hộp thoại Solver Parameters:

+ Kết quả thực hiện ví dụ 1 bằng Excel:

10


b) Giải trên Matlab:

11


Kết quả trên Command Window cho ta thấy lời giải ban đầu chưa tối ưu nên phải
lặp 5 lần mới tìm được lời giải tối ưu.
*Nhận xét: Bảng phân phối (ma trận kết quả) và tổng chí phí trên Matlab hoàn toàn
giống với Excel.

2) Ví dụ 2:
Powerco có ba nhà máy điện cung cấp cho bốn thành phố. Mỗi nhà máy có thể cung
cấp số kwh điện sau đây: nhà máy 1 – 35 triệu, nhà máy 2 – 50 triệu, nhà máy 3 – 40
triệu. Nhu cầu sử dụng điện cao điểm tại các thành phố này xảy ra cùng lúc như sau:
thành phố 1 – 45 triệu, thành phố 2 – 20 triệu, thành phố 3 – 30 triệu, thành phố 4 – 30
triệu. Chi phí để truyền tải 1 triệu kwh điện từ nhà máy đến thành phố được cho trong
bảng sau đây:
Từ

Nhà máy 1
Nhà máy 2

Thành phố 1
$8
$9

Đến
Thành phố 2
Thành phố 3
$6
$10
$12
$13

Thành phố 4
$9
$7
12


Nhà máy 3
$14
$9
$16
$5
Lên kế hoạch phân phối điện năng từ 3 nhà máy đến 4 thành phố để tối thiểu hóa chi
phí truyền tải và tính chi phí này?
a) Giải trên Excel:


+ Cấu hình Solver Parameters như sau:

13


+ Kết quả ta được chi phí nhỏ nhất 880 và bảng phân phối như hình dưới:

b) Giải trên Matlab:
Sau khi Run file CostMin.m trên Command Window ta thực hiện như sau:
 Nhap ma tran chi phi:
[8 6 10 9;9 12 13 7;14 9 6 5]
 Nhap ma tran cung cap (dang cot):
[35;50;40]
 Nhap ma tran nhu cau (dang dong):
[45 20 30 30]

14


Kết quả bảng phân phối điện năng và tổng chi phí truyền tải hoàn toàn giống khi
thực hiện trên Excel.

15


3) Ví dụ 3:
Doc Councillman đang tập hợp một đội bơi gồm 4 người để chuẩn bị cho giải bơi
400m tiếp sức. Mỗi vận động viên phải bơi 100m bằng 1 trong các kiểu bơi sau: bơi
ếch, bơi ngửa, bơi bướm hoặc bơi tự do. Bảng thành tích 4 kiểu bơi của 4 vận động viên
được cho trong bảng sau:

Thời gian (s)
Bơi ếch

Bơi ngửa

Bơi bướm

Bơi tự do

Gary Hall

54

54

51

53

Mark Spitz

51

57

52

52

Jim Montgomery


50

53

54

56

Chet Jastremski
56
54
55
53
Hãy lên kế hoạch chọn kiểu bơi (duy nhất) cho 4 vận động viên để thời gian hoàn
thành đường bơi tiếp sức 400m là nhỏ nhất?
*Giải trên Excel:

16


+ Cấu hình Solver Parameters như sau:

+ Kết quả ta được thời gian ngắn nhất là 207s và bảng chỉ định kiểu bơi như hình dưới:

17


4) Ví dụ 4:
Bảng chi phí vận

chuyển
A
Cửa Hàng
B
C
Cung

1
464
352
995
80

2
513
416
682
65

Nhà Kho
3
654
690
388
70

4
867
791
685

85

Cầu
75
125
100

a) Giải trên Excel:
+ Sau khi nhập đầy đủ các thông số đề bài, ta có bảng sau trên Excel:

18


+ Cấu hình Solver Parameters như sau:

+ Kết quả ta được tổng chi phí nhỏ nhất là 152535 và bảng phân phối như hình dưới:

19


b) Giải trên Matlab:
Sau khi Run file CostMin.m trên Command Window ta thực hiện như sau:
 Nhap ma tran chi phi:
[464 513 654 867;352 416 690 791;995 682 388 685]
 Nhap ma tran cung cap (dang cot):
[75;125;100]
 Nhap ma tran nhu cau (dang dong):
[80 65 70 85]

Kết quả bảng phân phối và tổng chi phí vận chuyển nhỏ nhất hoàn toàn giống với khi

thực hiện trên Excel
20