Chương III: Các mở rộng của quy hoạch tuyến tính 89
Bảng 2: X
0
b
j

a
j
30 25 35 40 u
1
45
9 1
25
2
20
7 0
50
5
- 30
4

6 2
+ 20
-2
35
5
+
6 1

20
7 4 0
50
5 10 4

6 2
40
-1
35
5
20
6 1
15
3 -1
v
j
6 1 2 3

X
1
là phương án tối ưu: X
opt
= X
1
=
025200
10 0 0 40
20 0 15 0
⎡
⎣

4
-4
-5
-1
-6
Chương III: Các mở rộng của quy hoạch tuyến tính 90
Giải: Cách 1: Tìm phương án xuất phát bằng phương pháp góc Tây Bắc.
Bước 1:Tìm phương án xuất phát bằng phương pháp góc Tây Bắc ta được phương án xuất
phát X
0
được cho ở bảng 1.
Bước 2: Kiểm tra tính tối ưu của phương án xuất phát X
0
.
Ta thấy X
0
là phương án không suy biến, chưa tối ưu.
Bảng 1: X
0
b
j

a
i
150 90 90 70 u
1
120

Bảng 2: X
1
b
j

a
i
150 90 90 70 u
1
120
9
- 115
6
+ 5
3
5
9- 3
125
6
+ 35
8
- 90
7- - 0
155
5 3 7 3 2
85
7
70
2
v

150 90 90 70 u
1
120
9
- 25
6 5
+ 90
3
+ 5
9 - 0
125
6
+ 125
8 - 7 - 8 - -3
155
5 + 3 7 - 2
- 85
7
70
-1
v
j
9 6 3 8
Bảng 4: X3

b
j

a
i


X
opt
=
090300
125 0 0 0
25 0 60 70
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
; f
min
= f(X
opt
) = 2065 (đvcp)
Bài toán có phương án tối ưu là không duy nhất. Thật vậy nếu chọn ô (2,4) làm ô điều chỉnh
ta tìm được phương án tối ưu khác.

Cách 2:
Tìm phương án xuất phát bằng phương pháp Min-cước
Khi tìm phương án xuất phát bằng phương pháp Min- cước ta được phương án xuất phát
X
0

chỉnh ta tìm được phương án tối ưu khác.
Cách 3: Tìm phương án xuất phát bằng phương pháp xấp xỉ Phogel
Khi sử dụng phương pháp xấp xỉ Phogel ta được phương án xuất phát X
0
được cho ở bảng 1
sau:
Bảng 1: X
0
b
j

a
i

150 90 90 70
Chênh
lệch hàng
120
9 6
90
3 9
30
3 3 0 0
125
6
1 85
8 7 8
40
1 2 2 2
155

0
125
6
1 85
8 - 7 8
+ 40
-1
155
5 +
65
7 - 2 -
90
7 0 -2
V
j
7
6
4
9
Ở bảng 2 ta thấy X
0
là phương án chưa tối ưu.
Điều chỉnh X
0
→ X
1
được cho ở bảng 3 sau:
Chương III: Các mở rộng của quy hoạch tuyến tính
3 0 -2
V
j
7
6
4
9

Ta thấy X
1
là phương án tối ưu vì ∀ Δ
ij

≤
0 (i = 13, , j = 14, ) X
1
= X
opt
X
1
= X
opt
=
090300
55 0 0 70
950600
⎡
⎣
⎢
⎢

i
m
ij ij
j
n
cx
==
∑∑
→
11
min

xai m
xbj n
ximjn
ij i
j
n
ij j
i
m
ij
≤=
==
≥= =
⎧
⎨
⎪
⎪
⎪

(j = 1, n ) sẽ thu đủ hàng, còn m điểm phát A
i
(i = 1, m ) sẽ có
điểm chưa phát hết hàng.
+) Cầu lớn hơn cung:
ab
i
i
m
j
j
n
+=
∑∑
<
11

Chương III: Các mở rộng của quy hoạch tuyến tính 94
f(x) =
i
m
ij ij
j
n
cx
==
∑∑

(,)
(,)
(,;,)
1
1
01 1
1
1
với ab
i
i
m
j
j
n
==
∑∑
<
11
(II)
Ở bài toán này, m điểm phát A
i
(i=1, m ) sẽ phát hết hàng, còn n điểm thu B
j
(j = 1, n ) có
những điểm chưa thu đủ hàng.
b. Phương pháp giải
* Giải bài toán vận tải cung lớn hơn cầu:
Ta thêm vào bài toàn một trạm thu giả B
n+1

) = f
min
.
c. Bài tập mẫu
Bài 1: Giải bài toán vận tải với số liệu cho ở bảng sau:
b
j

a
i

55 35 45
60
2 6 7
45
9 4 5
55
4 8 6
Giải: Với bài toán đã cho ta thấy:

a
i
i
=
∑
=++=
1
3
60 45 55 160 (đvhh) ;


= ab
i
i
i
j
+=
∑∑
−
1
3
1
3
= 25 ; c
i4
= 0; i = 3,1
Sử dụng phương pháp min- cước tìm phương án cực biên xuất phát ta được phương án
X
0

cho ở bảng 1 sau:
Bảng 1
b
j

a
i

55 35 45 25 u
1
60

13, ; j = 14, ) Suy ra X
0

≡
X
0
opt

X
0
opt
=
55 0 0 5
035100
0 0 35 20
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
;
f
min
= 510 (đvcp)
Vậy phương án tối ưu của bài toán ban đầu là:

3 2 1
30
9 4 6
30
8 2 3
Giải: Với bài toán đã cho ta thấy:

a
i
i
=
∑
=++=
1
3
40 30 30 100
(đvhh) ;
Chương III: Các mở rộng của quy hoạch tuyến tính 96
b
j
j
=
∑
=++=
1
3
30 20 70 120 (đvhh)

= 120-100 = 20 (đvhh) và cước phí c
4 j
= 0 (j = 13, ). Khi đó
ta có bài toán cân bằng cung cầu được cho ở bảng 1 sau:
Bảng 1: X
0

b
j

a
i
30 20 70 u
1

40
4 0 2 - 1
40
1
30
9
10
4 1
+
6
- 20
6
30
8 - 2
- 20

j
a
i
30 20 70 u
1

40
4 0
+
2 - 1
+ 40
1
30
9
- 10
4
20
6
- 0
6
30
8 - 2 - 3
30
3
20
0
20
0 - 0 - -3
V
j

;
f
min
=
290 (đvcp)
Tuy nhiên ô(1,1) có
Δ
11
= 0 nên ta có thể chọn ô (1,1) làm ô điều chỉnh và điều chỉnh
được phương án
X
2
là phương án tối ưu bảng 2.
Vậy bài toán ban đầu có tập phương án xác định bởi:
X
1
opt
=
0040
10 20 0
0030
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥

, (0<
λ
<1)

3.2.2. Bài toán vận tải cực đại
a. Bài toán
f(x) =
i
m
ij ij
j
n
cx
==
∑∑
→
11
max

()
()
xaim
xbjn
ximjn
ij i
j
n
ij j
i
m

điểm sau:
- Khi tìm phương án cực biên ban đầu, ưu tiên phân phối hàng tối đa vào ô c
ij
lớn nhất trong
bảng vận tải .
- Tiêu chuẩn tối ưu của bài toán vận tải cực đại như sau:
Nếu
Δ
ij
≥ 0 (
∀
=i 1, m , ∀ j = 1, n ) thì phương án đang xét là tối ưu.
- Tìm hệ thống thế vị và kiểm tra tính tối ưu của bài toán giống như bài toán min- cước.
- Ô điều chỉnh là ô (i, j) có
Δ
ij
= min {
Δ
ij
<0}.
c. Bài tập mẫu
Chương III: Các mở rộng của quy hoạch tuyến tính 98
Bài 1: Giải bài toán vận tải cực đại được cho ở bảng sau:
b
j
a
i

10 (đvhh).
Sử dụng phương Pháp max- cước tìm phương án xuất phát ta được
X
0
cho ở bảng 1.
Bảng1.
X
0

b
j

a
i
45 70 25 10 u
1
50
9 + 8
50
5 + 0 2
30
7 + 6
20
1 + 0
10
0
20
5 + 6 + 7
20
0 + 1

opt
=
0500 0
020010
00200
45 0 5 0
⎡
⎣
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥
;
f
max
= f( X
opt
) = 1140 (đv)
Chương III: Các mở rộng của quy hoạch tuyến tính 99
Suy ra X
opt

35 45 50 60
55 10 3 5 4
65 3 5 7 10
70 2 5 6 8

Giải:
Sử dụng phương án "max-cước", tìm phương án xuất phát X
0
được cho ở bảng 1.
- X
0
- là phương án không suy biến
- X
0
- chưa tối ưu.
- Điều chỉnh X
0
→ X
1
(ở bảng2).
Ô (1,3) là ô điều chỉnh.
Δ
13
= min {
Δ
i j
}, lượng hàng điều chỉnh q = 20.
Bảng 1 X
0Chương III: Các mở rộng của quy hoạch tuyến tính 100
Bảng 2 X
0

b
j
a
i
35 45 50 60 u
i
55
10
35
3 0 5
20
4 0 -3
65
3 + 5 + 7
5
10
60
0
70
2 + 5 +

⎤
⎦
⎥
⎥
⎥
;
f
max
= f(X
opt
) = 1465(đv)
3.2.3. Bài toán vận tải theo chỉ tiêu thời gian
a. Bài toán
T
x
= max{t
i j
∈T}→ min.

xai m
xbj n
ximjn
ij i
j
n
ij
i
m
j
ij

b. phương pháp giải
* Bước 1: Tìm phương án xuất phát X
0
(bằng phương pháp tây bắc, min-cước, ). Tính thời
gian thực hiện phương án X
0
.

t
X
0
= Max{t
i j:
x
i j
>0}
* Bước 2: Giải bài toán phụ:
Giải bài toán cước phí phụ bằng phương pháp thế vị, bài toán phụ được lập ra theo nguyên
tắc sau:
Chương III: Các mở rộng của quy hoạch tuyến tính 101
C = (c
i j
)
m.n
với c
i j
=

opt
của bài toán theo chỉ tiêu với thời gian thực hiện ngắn nhất là
t
X
k
= min { tt t
X
XX
k
0
1
, , , } suy ra thuật toán kết thúc.
Khả năng 2: Nếu giải bài toán phụ được phương án tối ưu X
k
nào đó mà tất cả các ô (i j): c
i
j
= 0 thì phương án X
k
≠ X
opt
của bài toán theo chỉ tiêu thời gian. Khi đó ta tiếp tục thực hiện
thuật toán như trên cho đến khi nhận được phương án tối ưu.
c. Bài tập mẫu
Bài 1: Giải bài toán vận tải theo chỉ tiêu thời gian được cho ở bảng dưới đây.

b
j

a

7 3
15
8
20

4

2
12
5 7
8

- X
0
là phương án suy biến ta bổ sung ô chọn không vào ô (2,1).
-
t
X
0
= max{2,3,2,3,4,7}= 7
- Lập bài toán cước phí phụ theo công thức. ta có bảng 2.
c
i j
=
0
1
0
0
nÕu t
nÕu t

a
i

17 12 15 16 u
i

25

0
- 17
0 1 0
+ 8
0
15

0
+ 0
1 0
- 15
1 0
20

0

0
12
0
+
1
- 8

8
1 0
7
1 0
20

0

0
12
0
8
0

0
v
j
0 0 0 0
- X
2
0
chưa tối ưu vì thuộc trường hợp hai.
- Lấy phương án
X
2
0
làm phương án thứ hai X
1
(coi như X
0

4

2
12
5
8
7

Chương III: Các mở rộng của quy hoạch tuyến tính 103

ta có:
t
X
1
= max{2,3,2,3,5,4} = 5
- Lập bài toán phụ ta thu được phương án tối ưu cho ở bảng 5
Bảng 5.
X
0
1

b
j

a
i


làm phương án xuất phát của bài toán ban đầu ta được bảng 6.
Bảng 6. X
2

b
j

a
i

17 12 15 16
25

2
9
6 7 4
16
15

3
0
7 3
15
8
20

4
8
2
12

0
1 0
15
1
20

1
8
0
12
1 1

Chương III: Các mở rộng của quy hoạch tuyến tính 104
Ở bảng 7 ta thấy:
-
X
0
2
là phương án tối ưu của bài toán phụ và có ô (i j): x
i j
>0 nằm ở ô có cước phí là 1
(trường hợp 1) nên
X
0
2
đồng thời là phương án tối ưu của bài toán theo chỉ tiêu thời gian.
- Vậy X

j
(j = 1, n ) với yêu cầu nhận b
j
(j =
1, n ) tương ứng. Hãy bố trí hành trình xe chạy để hoàn thành kế hoạch vận chuyển mà số km xe
chạy không là ít nhất.
3.3.2. Phương pháp giải
* Bước 1: Giải bài toán vận tải "giao - nhận" xe không theo phương pháp giải bài toán vận
tải cước phí với độ dài quãng đường đóng vai trò là cước phí vận chuyển. B
j
(j = n,1 ) là điểm
giao, A
i
(i = m,1 ) là điểm nhiệm xe không.
* Bước 2: Lập hành trình xe chạy trên cơ sở kế hoạch vận chuyển hàng và phương án tối
ưu của bài toán "giao- nhận" xe không.
3.3.3. Bài tập mẫu
Bài 1: Giải bài toán vận tải điều xe với các số liệu được cho ở bảng 1, với x
i j
> 0 trong
khuyên tròn là lượng hàng cần vận chuyển từ A
i
→ B
j
(i= 3,1 ; j = 4,1 ), hàng hóa là cùng loại, đơn
vị hàng là tấn, c
i j
- quãng đường A
1
→B

3
20
Giải
Chương III: Các mở rộng của quy hoạch tuyến tính 105
* Lập bài toán giao nhận xe không. Từ kế hoạch vận chuyển hàng ta xác định được:
A
1
: a
1
= 30+ 15 = 45; A
2
: a
2
= 5+ 10 = 15;
A
3
: a
3
= 20 + 15 + 20 = 55
Kế hoạch điều xe không từ B
j
→ A
i
(i= 3,1 ; j = 4,1 ).
B
1
: b

b
i
45 15 55 u
i

35 3
35
10 - 5 - 4
20 7 - 4 - 6
20
6
30 8 - 2 - 3
30
3
v
j
-1 -6 0

Sử dụng thuật toán thế vị giải bài toán cho ở bảng 2 ta được phương án tối ưu là:
X
opt
= X
0
=
⎥
⎥
⎥
⎥
⎦
⎤

2
⎯→⎯
'5
B
1
+ A
2
⎯→⎯
'10
B
4
+ A
3
⎯→⎯
'15
B
3
+ A
3
⎯→⎯
'20
B
4
+ A
3
⎯→⎯
'20
B
4
+ B

+ B
4

⎯→⎯
'30
A
3
Trong đó: a
t
i
(tấn hàng) ; b
t
(tấn. km xe chạy không hàng)
Chương III: Các mở rộng của quy hoạch tuyến tính 106
Ta có hành trình xe chạy như sau:
* Dạng con thoi
1
T30
1
BA ⎯⎯→← ;
3
T10
1
BA ⎯⎯→← ;
2
T20
3

'10
3
ABABA ⎯→⎯⎯→⎯⎯→⎯⎯→⎯
Vậy nếu sử dụng xe 5 tấn thì ở hành trình 1 dùng một xe, hành trình 2 dùng hai xe.
Bài 2: Giải bài toán vận tải điều xe với các số liệu được cho ở bảng 1 với x
i j
>0 trong
khuyên tròn là lượng hàng cần vận chuyển từ A
i
→ B
j
(i= 4,1 ; j = 3,1 ), hàng hóa là cùng loại,
đơn vị hàng tấn,, c
i j
- quãng đường từ A
i
→ B
j
, đơn vị là km.

Bảng 1

B
j
A
i
B1 B2 B3
A
1
5

: a
2
= 30 tấn
A
3
: a
3
= 35 + 5 = 40 (tấn) A
4
: a
4
= 20 + 40= 60 tấn
Kế hoạch điều xe không là:
B
1
: b
1
= 20 + 20 = 40 (tấn.km xe không);
B
2
: b
2
= 30 + 35 = 65 (tấn.km xe không);
B
3
: b
3
= 30 + 5 + 40 = 75 (tấn.km xe không);
3
1

2
40
3
- 20
0
V
j
5 7 2 3

Ở bảng 2 ta có bài toán cân bằng cung cầu
(
)180ba
4
1j
j
3
1i
i
==
∑∑
==
(đv)
Bảng 3: X
1

a
j
b
j
50 30 40 60 u

2

a
j
b
j
50 30 40 60 u
i

40 5 - 4
30
8 - 1
10
1
65 7
50
9 - 5 - 4
15
4
75 8 - 7 - 2
40
3
35
3
V
j
3 3 -1 0
Chương III: Các mở rộng của quy hoạch tuyến tính
BA
BA
⎯⎯→⎯
⎯⎯→⎯
⎯→⎯
⎯→⎯
⎯⎯→⎯
⎯⎯→⎯
⎯⎯→⎯

4
T35
3
T40
3
4
T15
2
1
T50
2
4
T10
1
2
T30
1
AB
3AB
AB


* Các hành trình khác
1)
1
T20
2
T20
3
T20T20
2
T20
1
T20
1
ABA3BABA ⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
2)
2
T10
1
T10
4
T10
2
T10
3
T10
3
T10
2
ABABABA ⎯→⎯⎯→⎯⎯→⎯⎯→⎯⎯→⎯⎯→⎯

⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎨
⎧
==≥
=≤
==
∑
∑
=
=
)4( )n.1j,m.1i(0x
)3( )n.1j(bx
)2( )m.1i(ax
ij
m
1i
jij
n
1j
iij

3.4.2. Phương pháp giải


* Nếu y
j
> 0 thì đạt kho tại B
j
với trữ lượng y
j
.
3.4.3. Bài tập mẫu
Bài 1: Một công ty quân đội cần vận chuyển một loại hàng hóa từ 4 xí nghiệp A
i
( 1,4 i = )
với khối lượng tương ứng a
i
= 70, 85, 35, 110 (tấn) về 4 nơi dự kiến đặt kho bảo quản B
j
( 1,4) j = .
Trong đó biết B
2
, B
3
có trữ lượng là b
2
= 80, B
3
= 120 (tấn). Cước phí vận chuyển một đơn vị
hàng hóa từ A
i
→B
j

vận chuyển đạt nhỏ nhất.
Giải: Bài toán có dạng không cân bằng cung cầu. Các kho B
1
, B
4
được coi là có trữ lượng:
b
1
= b
4
=
∑
=
4
1i
1
a = 70+85+35+110 = 300 tấn
Lập trạm phát giả A
5
để đưa bài toán về dạng cân bằng cung cầu với:
a
5
=
∑∑
==
−
4
1i
i
4

110 9 - 5 - 9 - 1
110
1
500 0
275
0 - 0
35
0
190
0
V
j
0 -1 0 0
Giải bài toán vận tải với điều kiện cân bằng cung cầu ta thu được phương án tối ưu cho ở
bảng 1.
==
opt
xx
0
190350275
110000
001025
08500
00700
; 755
min
=f (ngàn đồng)
Vậy x
opt
110000

Bảng 1

Chương III: Các mở rộng của quy hoạch tuyến tính 111
b
j

a
j

b
1
b
2
20 30
70 9 4 2 6
30 3 2 1 3
20 8 6 3 2
Giải: từ bài toán đã cho ta có: trữ lượng: b
1
- b
2 = 170
3
1
1

3 - 2
20 8 - 6 - 3 - 2
20
2
170 0
120
0
40
0 - 0
10
0

v
j
0 0 - 1 0
Áp dụng thuật toán thế vị giải bài toán cân bằng được cho ở bảng 2 ta có
0
x là phương án
cực biên xuất phát chưa tối ưu. Điều chỉnh
0
x →
1
x được cho ở bảng 3.
Chương III: Các mở rộng của quy hoạch tuyến tính 112
Bảng 3,
1
x

0 0 - 2 0

1
x =x
opt
=
10040120
20000
00300
020500
;
min
f =200+60+40+40=340 (đvcp)
Vậy: x
opt
=
20000
00300
020500
; f
min
=340(đvcp) (ngàn)
Nơi đặt kho và trữ lượng tương ứng là: B
1
với y
1
= 0 tấn; B
2
với y
2

⎨
⎧
===
==
==
∑
∑
=
=
),1;0
),1(1
),1(1
1
1
njx
mix
njx
Þ
n
i
Þ
m
i
Þ
m 1, (i 1 hoÆc

Bài toán là bài toán dạng đóng với a
1
= b
1

0

B
j
A
j
I II III
u
i
A 6
- 1
7
0
8 -
+
0
B 8
+ 0
6 -

9
1
2

C 5 - 7
1
6 - 0
v
j
6 7 7

0
B 8
1
6 9
0
1

C 5 7
1
6 0
v
j
7 7 8

- X
1
là phương án suy biến (bổ sung ô chọn không (2,3)).
- X
1
là phương án tối ưu vì ∀Δ
ij
≤ 0 (i = )3,1;3,1 =j