1
TIẾP CẬN BÀI TOÁN QUY HOẠCH TUYẾN
TÍNH THÔNG QUA BÀI TOÁN TÌM ĐƯỜNG
ĐI NGẮN NHẤT
Trần Ngọc Việt
NCS khóa 2010 - 2014
Đại học Đà Nẵng

2
2
Nội dung trình bày

Tóm tắt

Sơ lược về các phương pháp tối ưu

Xây dựng mô hình toán học cho các bài toán tối
ưu thực tế

Bài toán đường đi có trọng số bé nhất
+Bài toán
+Định lý
+Thuật toán Dijkstra tìm đường đi ngắn nhất
+Hướng tiếp cận bài toán quy hoạch tuyến tính thông
qua bài toán tìm đường đi ngắn nhất

Kết luận
3
3
TÓM TẮT
Kết quả chính của bài báo là nghiên cứu mối

Bước 2:
Xây dựng mô hình toán học cho vấn đề đang xét.
Trong bước này việc quan trọng là phải xác định hàm
mục tiêu và các ràng buộc toán học.
Bước 3:
Sử dụng công cụ toán học để khảo sát, giải quyết
các bài toán hình thành trong bước 2.
Bước 4:
Kiểm định lại các kết quả thu được trong bước 3.
6
6
3. Bài toán đường đi có trọng số bé nhất
3.1. Bài toán
. Cho đồ thị G = (V, E, c) và hai đỉnh
a, z
.
Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh
a
đến đỉnh
z
trong đồ thị G. Đồ thị G được gọi là
đồ thị có trọng số
nếu trên mỗi cạnh (
i, j
) của đồ thị được gán một số
nguyên không âm
c
(
i,j
)

cách bằng ∞.
7
7
3.2. Định lý.
Tại mỗi đỉnh
z
giá trị nhãn
d
(
z
) cuối cùng (nếu có) chính là độ dài của đường đi
ngắn nhất từ đỉnh
a
đến đỉnh
z.
Chứng minh.
Sau khi đã thực hiện xong thuật toán trên, nếu giá trị nhãn

d
(
z
) xác định thì ta có đường đi từ đỉnh
a
tới đỉnh
z
.
Ta khôi phục đường đi từ
a
đến
z

a1, a2
)
, ,
(
ak-1, z
)
Ta có:

d
(
a
)
+ c
(
a,a1
)
= d
(
a1
)
d
(
a1
)
+ c
(
a1,a2
)
= d
(

+ c
(
ak-1,z
)
= d
(
z
)
.

Vậy nhãn
d
(
z
) là độ dài của đường đi ngắn nhất.
)(),()(
11
zdzacad
kk
=+
−−
8
8

3.3.Thuật toán Dijkstra tìm đường đi ngắn nhất
Thuật giải tìm đường đi ngắn nhất từ
đỉnh nguồn
a
đến đỉnh đích
z

+ Phương pháp gồm các bước sau:
(1)Khởi tạo: Gán L(a):=0. Với mọi đỉnh gán
. Đặt T:=V.
(2)Tính
Nếu , kết thúc và ta nói không tồn tại đường đi
từ a đến z.
Ngược lại, nếu , chọn :
và đặt . Sang bước 3.
(3)Nếu , kết thúc, L(z) là chiều dài đường đi ngắn
nhất từ a đến z.
Từ z lần ngược theo đỉnh được ghi nhớ ta có đường đi
ngắn nhất.
Ngược lại, nếu , sang bước 4.
(4)Với mỗi kề (kề sau) v, nếu thì gán
và ghi nhớ đỉnh v cạnh x để xây dựng đường đi ngắn nhất.
Quay về bước 2.
ax ≠
∞=:)(xL
}.)(min{: TuuLm ∈=
+∞=m
+∞<m
Tv ∈
mvL =)(
}{: vTT −=
vz =
vz ≠
Tx ∈
),,()()( xvcvLxL +>
),()(:)( xvcvLxL +=
10

)(/)( yyD
α
)()(
1
1
qlengthy
k
yk
−
=
−
α
),(/)()(
1
qpApbqcff
kk
+=⇒
−
Ta được cấu trúc bài toán đối ngẫu:








+=
−
),(/)(

−
−−
∑∑
∑
kffkD
iyqiA
qpA
pb
iyib
iyibkD
kk
i
k
i
k
i
k
αε
ε
∑
=
−
−−+=⇒
k
l
ll
lffDkD
1
1
)1()()0()(

ll
lxffmix
1
1
)1()()(
β
ε
δ
βεβε
βε
δ
β
ε
β
ε
β
ε
δ
/./.
/)(
1
1
1
1
1
.)0(.
)1(.
)1()(1
)1()()1()()(
1

−
∑
Dùng BĐT:
βε
δ
/.
.)()()(
k
f
emkDkxkD ≤⇒≤
Vậy,
βε
δ
/.
.)(1
t
f
emtD ≤≤
14
14

3.5.Thử nghiệm chương trình:
Kết quả chạy chương trình bài toán quy
hoạch tuyến tính thông qua bài toán tìm đường
đi ngắn nhất.
Ví dụ:
Cho mạng đồ thị gồm 4 đỉnh, 7 cạnh và
các nút từ 1 đến 4
15
15