Qui Hoạch Tuyến Tính
Đề tài: Phương án Tây- Bắc, Voghel, min cước và một số bài tập
thực hành
Để tìm phương án cực biên ban đầu của bài toán vận tải. Chúng ta cần biết thế
nào là bài toán vận tải và một số khái niệm của nó.
Định nghĩa bài toán vận tải
Xí nghiệp cần vận chuyển hàng hóa từ m kho (điểm phát) P
I
,i=1,2,…,m đến nơi
tiêu thụ (điểm thu) T
j,
j= 1,2,…,n. lượng hàng có ở mỗi kho P
i
, là a
i
, i=1,2,…,m.
lượng hàng cần ở mỗi nơi tiêu thụ T
j
là b
j
, j=1,2,…,n. chi phí vận chuyển một
đơn vị hàng từ kho P
I
đến nơi tiêu thụ T
j
là c
ij
, i=1,2,…,m, j=1,2,…,n. cho biết
tổng lượng hàng ở các kho bằng tổng lượng hàng cần tiêu thụ.
Hãy lập kế hoạch vận chuyển hàng hóa sao cho chi phí là nhỏ nhất và đảm bảo
yêu cầu thu phát

∑
a
i
=
∑
b
j
(điều kiện cân bằng thu phát)
Lưu ý: bài toán vận tải cân bằng thu phát luôn có phương án tối ưu và ta cũng có
thể giải bằng phương pháp đơn hình.
Ta trình bày dưới dạng bảng vận tải như sau:

Thu
Phát
b
1
b
2
… b
n
a
1
c
11
X
11
… c
1n
X
1n

mn
Một số khái niệm
Xét bảng vận tải m
×
n
+ ô chọn là ô (I,j) nằm trên dòng I, cột j mà lượng hàng x
ij
>0, ô loại là ô
(I,j) mà x
ij
= 0.
x x x
x
x x
+ Dây chuyền là một tập hợp các ô chọn sao cho không có quá 2 ô liên tiếp
nằm trên cùng một dòng hoặc cột.
x x
x x
x x
dây chuyền không là dây chuyền
+ Chu trình là một dây chuyền khép kín. Số các ô trong một chu trình là số
chẵn. số các ô tối đa trong bảng không tạo thành chu trình là m + n – 1.
Với m + n – 1 không tạo thành chu trình ta có thể bổ sung thêm một ô bất
kì để có ít nhất một chu trình.
x x x x x x
x x x x
2
x x x x x x
Một số chu trình thường gặp
+ Ma trận cước phí là ma trận (c

Quy trình:
3
• Tính số cước phí của hai ô có cước phí bé nhất trên các dòng và cột.
• Trên dòng hay cột có hiệu số lớn nhất tìm ô có cước phí bé nhất.
• Loại bỏ dòng hay cột đã phân phối đủ hàng.
• Tính lại hệ số cước phí trên dòng hay cột.
• Tiếp tục quá trình cho đến khi phân phối hết hàng.
CHƯƠNG 3 BÀI TẬP THỰC HÀNH
3.1 Tìm phương án cực biên ban đầu bằng phương pháp Tây Bắc
Bai 1a
j
i
50 80 70
75 4(50) 7 12
65 5 8 15
60 6 7 3
j
i
80 70
25 7(25) 12
65 8 15
60 7 3
j
i
55 70
65 8(55) 15
60 7 3
j
i
70

j
i
10 30
40 4(10) 3
j
i
30
30 3(30)
j 50 20 30
5
i
60 6(50) 1(10) 2
40 5 4(10) 3(30)
Vậy phương án cực biên ban đầu là
(
50 10 0
0 10 30
)
, f= 440
Bài 3a

j
i
45 55 60
70 5(45) 2 3
90 2 1 4
j
i
55 60
25 2(25) 3

i
55 60 80 30
25 2(25) 3 6 10
90 1 4 9 4
50 5 5 8 6
60 12 13 7 7
j
i
30 60 80 30
90 1(30) 4 9 4
50 5 5 8 6
60 12 13 7 7
j
i
60 80 30
60 4(60) 9 4
50 5 8 6
60 13 7 7
7
j
i
80 30
50 8(50) 6
60 7 7
j
i
30 30
60 7(30) 7
j
i

80
70
→
j
i
20 50 80
80 20
70
→
j
i
50 80
60 50
70
→
j
i
80
10 10
70 70
→ f = 1780
Vậy phương án cực biên ban đầu là
(
60 40
0 20
0 0
0 0
50 10
10 70
)

→
j
i
20 180 150
230 20
120
→
j
i
180 150
210 180
120
→
j
i
150
30 30
120 120
→ f
= 16 813
10
Vậy phương án cực biên ban đầu là
(
120 0
39 105
0
136
0 0
0 0
0 0

j
i
120 160
80 30(80) 15
200 40 35
j
i
40 160
200 40(40) 35
j
i
160
160 35(160)
Do đó ta có bảng sau:
12
j
i
130 140 120 160
180 20(130) 18(50) 22 25
170 15 25(90) 30(80) 15
200 45 30 40(40) 35(160)
Vậy phương án cực biên ban đầu là 130 50 0 0
0 90 80 0
0 0 40
160
Và f= 15350
Bài 8a phương pháp gốc tây bắc
50 70 60 80
110 7 11 8 13
100 21 17 12 10

j
i
50
50 16(50)
14
Do đó ta có bảng sau:
j
i
50 70 60 80
110 7(50) 11(60) 8 13
100 21 17(10) 12(12) 10(30)
50 8 18 13 16(50)
Vậy phương án cực biên ban đầu là 50 60 0 0
0 10 60 30
0 0 0 50
Và f= 3000
Bài 9a phương pháp min cước
1 1 1 1
1 32 18 32 16
1 22 14 12 16
1 24 30 26 24
1 26 30 28 20
Giải
j
i
1 1 1 1
1 32(1) 18 32 16
1 22 14 12 16
1 24 30 26 24
15

Bài 10a
j
i
30 60 50 40
45 30
80
55
→
j
i
60 50 40
15 15
80
55
→
j
i
45 50 40
80 45
55
→
j
i
50 40
35 35
55
17
→
j
i

65 55
60
→
j
i
70
10 10
60 60
18