- 1 -

Mục Lục
Nội dung Trang
Mở đầu 2
Chơng 1: Các kiến thức bổ trợ
1.1. Bài toán quy hoạch tuyến tính tổng quát 5
1.2. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính 7
1.3. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính chính tắc 9
Chơng 2: Bài toán quy hoạch nguyên tuyến tính
2.1. Bài toán tối u rời rạc 19
2.2. Một số thuật toán giải bài toán quy hoạch nguyên tuyến tính 26
Chơng 3: Bài tập vận dụng
3.1. Bài tập vận dụng thuật toán cắt Gomory 50
3.2. Bài tập vận dụng thuật toán Land - Doig 58
3.3. Bài tập đa bài toán về bài toán cái túi để giải 64
Tài liệu tham khảo 74


với sinh viên s phạm toán. Với mong muốn khai thác sâu kiến thức môn quy
hoạch tuyến tính nói riêng; mở rộng tầm hiểu biết của bản thân về tri thức toán

- 3 -

nói chung, việc nghiên cứu lý thuyết bài toán quy hoạch nguyên tuyến tính là hết
sức cần thiết.
Vì những lý do trên chúng tôi chọn "Về bài toán quy hoạch nguyên
tuyến tính" làm đề tài nghiên cứu.
2. Mục đích nghiên cứu
Hệ thống lại một cách chi tiết các vấn đề lý thuyết về bài toán quy hoạch
nguyên tuyến tính; xây dựng hệ thống bài tập vận dụng, để từ đó thấy đợc tầm
quan trọng và tính thiết thực của lý thuyết bài toán quy hoạch nguyên tuyến tính
đối với các lĩnh vực khoa học kỹ thuật, các hoạt động thực tiễn của đời sống x
hội.
3. Nhiệm vụ nghiên cứu
Nghiên cứu các kiến thức liên quan đến bài toán quy hoạch tuyến tính
tổng quát, một số thuật toán giải bài toán quy hoạch tuyến tính.
Nghiên cứu các phơng pháp giải bài toán quy hoạch nguyên tuyến tính.
Nghiên cứu một số bài tập vận dụng phơng pháp giải bài toán quy hoạch
nguyên tuyến tính.
4. Đối tợng và phạm vi nghiên cứu
Đối tợng nghiên cứu: Lý thuyết tối u hoá.
Phạm vi nghiên cứu: Nghiên cứu lý thuyết bài toán quy hoạch nguyên tuyến tính.
5. Phơng pháp nghiên cứu
Phơng pháp nghiên cứu lý luận: Đọc các tài liệu về môn quy hoạch tuyến
tính, các tài liệu liên quan đến tối u hoá, các khoá luận tốt nghiệp về quy
hoạch tuyến tính của các khoá trớc ở trờng Đại học Hùng Vơng.
Phơng pháp lấy ý kiến chuyên gia: Tham khảo ý kiến của giảng viên
hớng dẫn và các giảng viên dạy tối u hoá; quy hoạch tuyến tính của

3.1. Bài tập vận dụng thuật toán cắt của Gomory
3.2. Bài tập vận dụng thuật toán Land - Doig
3.3. Bài tập đa bài toán về bài toán cái túi để giải - 5 -

CHƯƠNG 1
CáC KIếN THứC Bổ TRợ

1.1. Bài toán quy hoạch tuyến tính tổng quát
1.1.1. Bài toán quy hoạch tuyến tính tổng quát
Tìm vectơ
1 2
( , , , )
n
x x x x
=
sao cho hàm f(x) =
1
n
j j
j
c x
=

min với các điều

a x b i I
a x b i I
x j J
x R j J
x j J
=
=
=







=















J; J = { 1, , n}; J = J
1
J
2
J
3
,

J
i
J
k
= ỉ; I k; i,k = 1,2,3.
b
i
,

c
j
, a
ij
là các hằng số cho trớc.
Trong bài toán trên:
f đợc gọi là hàm mục tiêu.
Mỗi hệ thức ở (1.1), (1.2), (1.3), (1.4), (1.5), (1.6) gọi là một ràng buộc.
Mỗi ràng buộc (1.1), (1.2), (1.3) gọi là ràng buộc cỡng bức (hay cơ bản).
Ràng buộc (1.4), (1.5), (1.6) gọi là ràng buộc tự do (hay ràng buộc dấu).
+ Mỗi vectơ
1 2
( , , , )

2j
, ,a
mj
) là vectơ cột (ma trận
cột) thứ j (j = 1,2, ,n) của A.
b) A
t
là ma trận chuyển vị của A.
c) Nếu A = (a
ij
) và B = (b
ij
) là hai ma trận cùng kiểu thì bất đẳng thức ma trận
A B đợc hiểu là a
ij
b
ij
với i,j.
Đặc biệt với vectơ (ma trận)
1 2
( , , , )
n
x x x x
=
thì x 0 đợc hiểu là x
j
0 j.
d) Mỗi vectơ đợc xem nh ma trận cột trong các phép tính ma trận ( nếu
không nói gì thêm hoặc không có quy ớc gì khác).
e) Biểu thức tích vô hớng của hai vectơ


là ma trận cấp 1 ( c
t
là
ma trận chuyển vị của c).
Với những quy ớc nh trên bài toán quy hoạch tuyến tính tổng quát đợc
viết gọn nh sau:
Tìm vectơ
1 2
( , , , )
n
x x x x
=
R
n
thoả mn:
f(x) = c
t
x min.

- 7 -

1
2
1
2
,
,
0,
,

j
Ax b
x j J






Dạng chính tắc:
f(x) = c
t
x min

0,
j
Ax b
x j J
=





1.2. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính
Xét bài toán quy hoạch tuyến tính chính tắc (bài toán I)

1
( ) min
n

0
x
và cơ sở
{
}
;
j
B
B A j J
=
tơng ứng, trong đó
{
}
/
j
B
J j J A B
=
. Tìm các hệ
số khai triển
ij
a
và các ớc lợng
j

(
ij
a
: hệ số khai triển vectơ A
i

của cột
j
A
tơng ứng.
a) Nếu tồn tại
j

> 0 mà tất cả
ij
a
0 j J thì kết luận hàm mục
tiêu giảm vô hạn trên miền ràng buộc. Bài toán không có lời giải
hữu hạn. Thuật toán kết thúc.
b) Nếu với mỗi j
B
J
mà
j

> 0 đều tồn tại ít nhất một hệ số
0
ij
a
>

thì tiến hành tìm phơng án cực biên mới tốt hơn với cơ sở
1
( \ )
B
J J r s
Dòng
r
A
gọi là dòng xoay.

- 9 -

Phần tử nằm trên giao của dòng xoay và cột xoay của bảng đơn hình đợc
gọi là phần tử xoay.
Bớc 4: Thực hiện phép biến đổi đơn hình chuyển từ phơng án cơ sở
chấp nhận đợc x sang phơng án cơ sở chấp nhận đợc
x
: Bảng đơn hình
tơng ứng với
x
(gọi tắt là bảng mới) có thể thu đợc từ bảng đơn hình
tơng ứng với x (gọi tắt là bảng cũ) theo các quy tắc biến đổi sau đây:
a) Các phần tử ở vị trí dòng xoay trong bảng mới (
rj
a
) bằng các phần
tử tơng ứng trong bảng cũ chia cho phần tử xoay:
,
rj
rj
rs
a
a j J

j J j s
rj s
j
j
rs
a
a

=

1.3. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính chính tắc
1.3.1. Cơ sở chấp nhận đợc đối ngẫu
Xét bài toán quy hoạch tuyến tính dạng chính tắc (P) và bài toán đối ngẫu (Q).
(P)
( ) min
t
f x c x=
(Q)
( )
g y by max
= 0
Ax b
x
=

1 2
, , ,
n
N A A A
=
\ B. Phơng án cơ sở (x
B
, x
N
) của bài toán (P) tơng
ứng với cơ sở B thu đợc bằng cách giải hệ phơng trình tuyến tính x
N
= 0, A
B
x
B

= b.
Định nghĩa : Ta gọi B là cơ sở chấp nhận đợc gốc nếu phơng án cơ sở
tơng ứng với nó là phơng án chấp nhận đợc của bài toán gốc, (tức là nếu
1
0
B B
x A b

=
). Ta gọi phơng án cơ sở đối ngẫu tơng ứng với cơ sở B là vectơ y
thu đợc bằng cách giải hệ phơng trình tuyến tính
t
B B

1
( ) 0
t t
B B
A A c c


(1.7)
Dễ thấy nếu B là cơ sở chấp nhận đợc gốc, thì điều kiện (1.7) chính là
tiêu chuẩn tối u. Nh vậy, cơ sở B sẽ là tối u nếu nh nó vừa là chấp nhận
đợc gốc vừa là chấp nhận đợc đối ngẫu.
Nhận xét
Thuật toán đơn hình gốc là bắt đầu từ một cơ sở chấp nhận đợc gốc, sau
một số hữu hạn lần chuyển cơ sở sẽ đi đến cơ sở tối u.
Thuật toán đơn hình đối ngẫu lại bắt đầu từ một cơ sở chấp nhận đối ngẫu
nhng cha phải chấp nhận đợc gốc, ta tiến hành dịch chuyển sang các
cơ sở chấp nhận đợc đối ngẫu mới cho đến khi gặp đợc cơ sở tối u thì
dừng lại.
1.3.2. Thuật toán đơn hình đối ngẫu khi đã biết cơ sở chấp nhận đợc đối ngẫu

- 11 -

Xét bài toán quy hoạch tuyến tính dạng chính tắc.
f(x) = c
t
x min

0
A x b
x

c
j
A
j c
n
A
n
A
1
A
2

A
m
c
1
c
2

c
m
1
b

2
b


m
b b b b B b

= =1
1 , 2
( , , ) , 1,
j
j
j j mj
A a a a B A j n

= = =1 j
j B j
c B A c

=
;
1,
j n
=

Cột giả phơng án có thể chứa các thành phần âm vì B cha chắc đ là
một cơ sở chấp nhận đợc gốc.


=
thì giả phơng án (x
B
, x
N
) là một phơng án tối u.
Thuật toán kết thúc.
Nếu i,
1,
i m
=
mà
i
b
< 0 thì ta tìm
r
b
= min{
i
b
,
1,
i m
=
}.
Nếu có nhiều chỉ số cùng đạt cực tiểu thì chọn r là một chỉ số tuỳ ý trong số đó.
Bớc 2: Kiểm tra điều kiện để tập phơng án của bài toán là không rỗng: nếu có
1,
i m
=

a x b i m
=
= =

(*)
(*) không thể xảy ra vì
ij
a
0, x
j
0 (
1,
j n
=
) còn b
i
< 0. Vậy bài toán (P)
không có phơng án.
Nếu trên mỗi dòng ứng với
i
b
< 0 đều tồn tại ít nhất một phần tử
0
ij
a

. Khi đó ta tiến hành một bớc lặp đơn hình đối ngẫu để
chuyển sang một cơ sở chấp nhận đợc đối ngẫu mới. Giả sử đ chọn
dòng xoay r. Ta tìm cột đa vào cơ sở thay cho cột A
r

rs rj
a
a a



= <. Cột A
s
gọi là cột xoay.
Sau khi đ xác định đợc dòng xoay, cột xoay ta tiến hành các tính toán
trong phép biến đổi đơn hình giống nh đ làm trong bài toán gốc.
1.3.3. Thuật toán đơn hình đối ngẫu khi cha biết cơ sở xuất phát chấp
nhận đợc đối ngẫu
Xét bài toán quy hoạch tuyến tính dạng chính tắc sau:
f(x) = c
t
x min

0
A x b
x
=






- 14 -

bài toán mở rộng. Đối với bài toán mở rộng ta có một cơ sở của nó là
0 1
( , , , )
m
B A A A
=



Ta xây dựng bảng đơn hình tơng ứng với cơ sở
B

của bài toán mở rộng.
Phơng án c
0
c
1c
j c
n
Cơ
sở
B


1
A
m
A


c
0

c
1

c
m

0
1
bm
b

1
0



n


Chú ý rằng, khi tính giá trị các thành phần của cột phơng án ta viết nó
dới dạng
i i
b b M
+

. Khi đó trong bảng đơn hình cột phơng án đợc tách ra làm
hai cột, một cột ghi hệ số
i
b

của M, còn cột kia ghi hệ số tự do
i
b

.
Giả sử
s

= max {
j

;
1,
j n
=


1) Bài toán mở rộng không có phơng án. Khi đó bài toán xuất phát cũng
không có phơng án. Thật vậy, nếu bài toán xuất phát có phơng án chấp
nhận đợc x = (x
1
, x
2
, , x
n
) thì rõ ràng
x
= (x
0
, x
1
, , x
n
) với x
0
= M -
x
m+1
x
n
cũng là một phơng án của bài toán mở rộng.
2) Bài toán mở rộng có phơng án tối u
0 1
( , , , )
n
x x x x

x
và giảm dần giá trị M cho đến khi có
một trong các
1
x
,
2
x
, ,
n
x
trở thành 0.
1.3.4. áp dụng thuật toán đơn hình đối ngẫu để giải bài toán quy hoạch
tuyến tính với số ràng buộc tăng dần
Xét bài toán quy hoạch tuyến tính (I):
Giả sử ta đ giải bài toán (I) bằng thuật toán đơn hình và thu đợc phơng
án tối u cơ sở
*
x
với cơ sở tối u B. Không giảm tổng quát ta có thể coi rằng
{
}
1 2
, , ,
m
B A A A
=
. Ta có bảng đơn hình tối u là bảng 1 phần 1.3.2.

- 16 -

j
j
a b
x
+ +
=
>

(1.9)
Vấn đề đặt ra: Liệu ta có thể sử dụng phơng án tối u
*
x
và cơ sở tối u B để
giải bài toán với ràng buộc bổ sung hay không?
Đa thêm vào biến phụ
1
n
x
+
0 chuyển ràng buộc (1.8) về dạng đẳng
thức ta thu đợc:

1, 1 1
1
n
m j j n m
j
a x x b
+ + +
=

j
a x b i m
a x x b
x j n
=
+ + +
=

= =



+ =



= +



- 17 -

Đối với bài toán bổ sung cơ sở của nó là
1 2 1
( , , , , )
m n
B A A A A


c
j
j
A

c
n
n
A


c
n+1
1
n
A
+


1
A


2
A



1
m
b
+1
j
a

2
j
amj
a

1,
m j
a
+

0
0
0
0
1
j

+ +
=
= = +
1,
0; 1,
m j
a j m
+
= =1
1 1,
1
m
m
m m i i
i
b b a b
+
+ +
=
=


Do (1.9) nên bảng đơn hình thu đợc không phải là chấp nhận đợc gốc.
Thế nhng rõ ràng nó là chấp nhận đợc đối ngẫu. Vì vậy ta có thể áp dụng thuật

2.1. Bài toán tối u rời rạc
2.1.1. Xây dựng mô hình tối u rời rạc
Trớc tiên chúng ta bàn về những nguyên nhân dẫn đến tính rời rạc của
biến số trong việc xây dựng mô hình tối u hoá cho các bài toán thực tế.
Một trong những nguyên nhân đầu tiên dẫn đến tính rời rạc của biến số là
tính không chia cắt đợc của đối tợng nghiên cứu. Ngoài ra, trong nhiều bài
toán thực tế chính do cấu trúc tổ hợp ban đầu của bài toán mà các biến số chỉ có
thể nhận các giá trị rời rạc. Cuối cùng, tính rời rạc của các biến số có thể xuất
hiện từ tính không liên tục, đa cực trị của hàm mục tiêu của bài toán. Ta sẽ minh
hoạ cho các vấn đề vừa bàn tới ở các ví dụ sau này.
Mô hình bài toán tối u rời rạc tổng quát
Bài toán tối u rời rạc tổng quát có thể phát biểu nh sau:

1 2
( , , , ) min( )
n
f x x x max

, (2.1)

1 2
( , , , )
n
n
x x x x D=
R

Trong đó D là tập các vectơ
1 2
( , , , )

j n
=
(2.4)
Khi đó bài toán (2.1) - (2.4) đợc gọi là bài toán quy hoạch nguyên.
Nếu
1
n n
=
ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu
1
n n
<
ta
có bài toán quy hoạch nguyên bộ phận.
Một trờng hợp riêng quan trọng của bài toán quy hoạch nguyên là bài
toán quy hoạch nguyên tuyến tính thu đợc từ bài toán tổng quát khi các hàm
( )
f x
và
( )
i
g x
(i = 1,2, ,m) là tuyến tính.
2.1.2. Một số tình huống thờng gặp khi xây dựng các mô hình thực tế của
tối u rời rạc
2.1.2.1. Bài toán điều kiện không chia cắt đợc
Trong việc mô hình hoá nhiều vấn đề ứng dụng, từ ý nghĩa thực tế các
biến số phải nhận giá trị nguyên. Chẳng hạn, xét bài toán lập kế hoạch sản xuất
với sản phẩm cuối cùng là không chia cắt đợc. Một nhà máy có khả năng sản
xuất n loại sản phẩm. Để sản xuất các loại sản phẩm này cần sử dụng m loại

nan hoa xe đạp) thì việc bỏ qua tính nguyên của biến số không dẫn đến những
sai lệch đáng kể. Thế nhng nếu sản phẩm đợc sản xuất với số lợng không lớn
và giá trị một sản phẩm là cao (ví dụ cỗ máy kéo), thì tính nguyên của biến số

- 21 -

không thể bỏ qua. Ta thu đợc mô hình toán học của bài toán là bài toán quy
hoạch nguyên tuyến tính sau:

1
n
j j
j
c x max
=

1
, 1,
n
ij j i
j
a x b i m
=
=

j
tối thiểu cần sản xuất để bù lại đợc những chi
phí cần bỏ ra khi đa phơng thức sản xuất sản phẩm mới này vào hoạt động ).
Tức là chúng ta gặp phải điều kiện hoặc là
j
x
= 0, hoặc là
j j
x d

. Giả sử biết
cận trên
j
p
của biến
j
x
trong bài toán đang xét. Khi đó đa vào biến logic

1,
0,
j
neu chap nhan san xuat san pham j
y
neu nguoc lai

=




=

Ví dụ nếu
j
x
là quy mô công suất của nhà máy điện cần xây dựng ở địa
điểm
j
, thì
j
Q
là tập các quy mô công suất tiêu chuẩn.
Bằng cách đa vào các biến phụ
ij
t
ràng buộc nói trên là tơng đơng với hệ

1
m
j ij ij
i
x q t
=
=
1
1
m

j ij
i
x t
=
=
1
1
m
ij
i
t
=
=
{
}
0,1 , 0,
ij
t i m
=

trong đó
2
log
j

j j j j
j j
j
d c x x
f x
x
+ >


=

=



với
j
d
> 0,
1,
j n
=
. Các số
j
d
thờng đợc hiểu là chi phí cố định cần thiết để đa
phơng thức sản xuất
j
vào hoạt động, nó không phụ thuộc vào cờng độ sử
dụng phơng thức này (

j j j
x D x p t

,
{
}
0,1 ,
j
t
1,
j n
=
.
2.1.3. Một số mô hình phổ biến của tối u rời rạc
Trong phần này ta trình bày một số mô hình đ đóng vai trò quan trọng
trong việc phát triển lí thuyết tối u rời rạc đồng thời cũng là những mô hình có
nhiều ứng dụng rộng ri trong thực tế của tối u rời rạc.
2.1.3.1. Bài toán cái túi
Một nhà thám hiểm cần đem theo một cái túi có trọng lợng không quá b. Có
n loại đồ vật có thể đem theo. Đồ vật thứ
j
có trọng lợng là
j
a
và giá trị sử
dụng là
j
c
(
1,

=









=





2.1.3.2. Bài toán ngời du lịch
Một ngời du lịch muốn đi tham quan n +1 thành phố
0 1
, , ,
n
T T T
. Xuất
phát từ
0
T
ngời du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố
đúng một lần, rồi quay trở lại thành phố xuất phát. Biết
ij
c


=
của n số tự nhiên 1,2, ,n. Đặt

( )
f

=
1 1 2 1
0 0

n n n
i i i i i i
c c c c

+ + + +

và kí hiệu P
P P
P

là tập

tất cả

các hoán vị
1 2
( , , , )
n
i i i

n
A A A
là một họ các tập con của tập m phần tử X. Hỏi
rằng có thể tìm đợc F F
FF
F

sao cho

,
i
i
A F
X A

=


i j
A A
=
,
i j

,
,
i j
A A F

,






1, , 1,
i m j n
= =
. Kí hiệu
j j
c A
=
= số phần tử của tập
j
A
. Đa vào biến số

1,
0,
j
j
neu A F
x
neu nguoc lai



=



0,1 , 1,
j
x j n
=
.
Rõ ràng nếu giá trị tối u của bài toán vừa viết bằng m thì ta có trả lời
khẳng định cho bài toán phân hoạch, ngợc lại bài toán phân hoạch không có lời
giải.
Một trờng hợp riêng của bài toán tối u rời rạc là bài toán quy hoạch
nguyên tuyến tính khi ta đa thêm vào bài toán quy hoạch tuyến tính tổng quát
điều kiện các biến số là nguyên. Dạng tổng quát của bài toán.
Tìm vectơ
1 2
( , , , )
n
x x x x
=
sao cho hàm
( )
f x
=
1
n
j j
j
c x
=

min với hệ điều
kiện