CHƯƠNG I: BÀI TOÁN QUI HOẠCH TUYẾN TÍNH
1.1 Bài toán quy hoạch tổng quát
Giả sử
( )
( )
1 1 2
, , ; , , : 1, , 1,
n n
n i j
x x x f g h i m j m= ∈ → = =¡ ¡ ¡
là những hàm
n
biến.
Giả sử
n
X ⊂ ¡
. Bài toán quy hoạch tổng quát có dạng:
Tìm vectơ
( )
1
, ,
t
n
x x x=
sao cho
( )
minf x →
(hoặc
max
) (1)
với các điều kiện:

Bài toán (1)-(4) được kí hiệu là (P).
Hàm f(x) được gọi là hàm mục tiêu (objective function ), các hàm
,
i j
g h
gọi là các hàm
ràng buộc (constraint function ), tập các vectơ
n
x X∈ ⊂¡
thỏa mãn các ràng buộc (2),(3)
gọi là tập phương án hay miền chấp nhận được của bài toán trên. Phương án
0
x
thỏa mãn
( )
( )
0
f x f x≤
với mọi
n
x X∈ ⊂¡
đối với bài toán min (
( )
( )
0
f x f x≥
với mọi
n
x X∈ ⊂¡


đối với bài toán max)là phương án tối ưu hay lời giải của bài toán, khi đó
( )
0
f x
là giá trị
tối ưu.
Nếu hàm mục tiêu
f
và các ràng buộc
,
i j
g h
đều là các hàm tuyến tính thì (P) được gọi là
bài toán quy hoạch tuyến tính (QHTT).
1.2. Một số ví dụ dẫn đến bài toán QHTT
1.2.1 Bài toán lập kế hoạch sản xuất
Một nhà máy muốn sản xuất ra n loại sản phẩm từ m loại nguyên liệu. Biết:
ij
a
là lượng nguyên liệu loại i cần để sản xuất ra một đơn vị sản phẩm loại j;
i
b
là lượng nguyên liệu loại i hiện có của nhà máy;
j
c
là tiền lãi từ việc bán một đơn vị sản phẩm loại j;
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
1
1
2

( ) 0, 1,2, , (2)
( ) 0, 1,2, , (3)
(4)
i
j
n
g x i m
h x j m
x X

≤ =

= =


∈ ⊂

¡
(
1 ,1i m j n≤ ≤ ≤ ≤
).
Hãy xây dựng kế hoạch sản xuất cho nhà máy đem lại tổng lợi nhuận lớn nhất.
Gọi
j
x
là lượng sản phẩm loại j mà nhà máy cần sản xuất (
0, 1,
j
x j n≥ =
). Kế hoạch sản

xuất của nhà máy là vectơ
( )
1
, ,
n
x x x=
.
ij
1
n
j
j
a x
=
∑
- tổng nguyên liệu loại i theo kế hoạch sản xuất
x
;
1
n
j j
j
c x
=
∑
- tổng lợi nhuận thu được theo kế hoạch sản xuất
x
.
Khi đó mô hình toán học của bài toán trên là:
Tìm

( )
1
, ,
n
x x x=
sao cho:
( )
1
ax
n
j j
j
f x c x m
=
= →
∑
và thỏa mãn điều kiện
ij
1
, 1,
0, 1,
n
j i
j
j
a x b i m
x j n
=

≤ =




≥ =

∑
1.2.2 Bài toán lập thực đơn
Có n loại thực phẩm
j
T
(
nj ,1=
), biết rằng mỗi đơn vị
j
T
chứa
ij
a
đơn vị chất i (
mi ,1=
)
và có giá thành là
j
c
đơn vị tiền. Hãy lập thực đơn sao cho bữa ăn phải bảo đảm có ít nhất
b
i
đơn vị chất
i
(

mi ,1=
) mà có giá thành rẻ nhất.
Lập bài toán:
Gọi
j
x
là số đơn vị thực phẩm
j
T
(
nj ,1=
) sử dụng cho bữa ăn
( )
0
j
x ≥
và tổng số đơn
vị chất
i
có trong bữa ăn là
),1(
1
nibx
ij
a
i
m
j
j
=≥

∑
=
. Giá thành của bữa ăn là
∑
=
n
j
jj
xc
1
.
Bài toán đặt ra là tìm
( )
1
, ,
n
x x x=
sao cho
( )
1
min
n
j j
j
f x c x
=
= →
∑
và thỏa mãn điều kiện
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền

2
1
, 1,
0, 1,
m
ij j i
j
j
a x b i m
x j n
=

≥ =



≥ =

∑
1.2.3 Bài toán vận tải
Có m kho hàng kí hiệu
1
, ,
m
A A
(điểm phát) cung cấp cùng một mặt hàng nào đó với khối
lượng có khả năng cung cấp tương ứng là
1
, ,
m

a a
và n cửa hàng (nơi tiêu thụ) kí hiệu
1
, ,
n
B B
có nhu cầu tiêu thụ lượng hàng tương ứng
1
, ,
n
b b
. Để thỏa mãn nhu cầu các điểm
thu thì tổng số lượng các điểm phát ít nhất phải bằng hay lớn hơn tổng yếu cầu các điểm
thu:
∑∑
==
≥
n
j
j
m
i
i
ba
11
.
Biết rằng cước phí vận chuyển một đơn vị hàng (tấn, cái…) từ nơi phát
i
A
tới nơi nhận

j
B
là
ij
c
đơn vị tiền. Ma trận
( )
ij
m n
C c
×
=
gọi là ma trận cước phí. Hãy lập phương án vận
chuyển sao cho các điểm thu đều nhận đủ hàng và chi phí vận chuyển là ít nhất.
Xây dựng bài toán:
Gọi
ij
x
là lượng hàng chuyển từ kho
i
A
tới điểm thu
j
B
.
Tất nhiên ta phải có
ij
0x ≥
(
1, , 1,i m j n= =

).
Tổng lượng hàng chuyển từ điểm phát
i
A
tới mọi điểm nhận
j
B
là
( )
1
1,
n
ij
j
x i m
=
=
∑
.
Tổng lượng hàng nhận tại điểm
j
B
từ các điểm phát
i
A
là
( )
1
1,
m

i j
i
x j n
=
=
∑
.
Tổng cước phí phải trả là
∑∑
= =
m
i
n
j
jiji
xc
1 1
.
Bài toán đặt ra là: Tìm
( )
ij
x x=
( )
1, , 1,i n j m= =
sao cho
( )
1 1
min
m n
i j i j

i j
f x c x
= =
= →
∑∑
và thỏa mãn các điều kiện
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
3
( )
( )
( )
n
ij
j=1
m
ij
i=1
ij
1,
1,
0 1, ; 1,
i
j
x a i m
x b j n
x i m j n

≤ =





= =



≥ = =



∑
∑
1.3. Bài toán QHTT tổng quát
1.3.1. Các dạng của bài toán quy hoạch tuyến tính
Bài toán QHTT có ba dạng là dạng tổng quát, dạng chuẩn tắc và dạng chính tắc.
a. Dạng tổng quát (GP)
Tìm vectơ
( )
1
, ,
t
n
x x x=
sao cho
( ) ( )
1
min max
n
j j
j

f x c x
=
= →
∑
với các điều kiện
1
1
1 2
1
2
1
( 1, , )
( 1, , )
( 1, , )
n
ij j i
j
n
ij j i
j
n
ij j i
j
a x b i m
a x b i m m
a x b i m m
=
=
=


≥ =




≤ = +



= = +



∑
∑
∑
và các ràng buộc về dấu
( )
( )
( )
1
1 2
2
0 1,
0 1,
1,
j
j
j
x j n

x j n n
x j n n

≥ =


≤ = +


 ∈ = +

¡
b. Dạng chuẩn tắc (NP)
Tìm vectơ
( )
1
, ,
t
n
x x x=
sao cho
( )
1
min
n
j j
j
f x c x
=
= →

∑
với các điều kiện
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
4





=≥
=≤
∑
=
),1(0
),1(
1
njx
mibxa
j
n
j
ijij
Chú ý: Mọi ràng buộc là bất đẳng thức cùng chiều.
c. Dạng chính tắc (CP)
Tìm vectơ
( )
1
, ,
t
n

x x x=
sao cho
( )
1
min
n
j j
j
f x c x
=
= →
∑
với các điều kiện
( )
( )
1
, 1, 0
0 ( 1, )
n
ij j i i
j
j
a x b i m b
x j n
=

= = ≥




≥ =

∑
1.3.2. Biến đổi bài toán QHTT về dạng chuẩn hoặc dạng chính tắc
Mọi bài toán QHTT tổng quát có thể biến đổi một cách tương đương về bài toán dạng
chuẩn tắc hoặc dạng chính tắc. Do vậy, không mất tính tổng quát ta chỉ cần xem xét bài
toán dạng chuẩn tắc hoặc dạng chính tắc.
Cách chuyển bài toán tổng quát về bài toán chính tắc:
a. Đưa bài toán cực đại về bài toán cực tiểu
Vì
( )
{ }
( )
{ }
max : min :f x x D f x x D∈ = − − ∈
nên bài toán
( )
{ }
max :f x x D∈
có thể thay
bằng bài toán tương đương sau
( )
{ }
min :f x x D− ∈
. Khi đó
0
x
là phương án tối ưu của bài
toán min thì
0

x
cũng là phương án tối ưu của bài toán max và
min max
f g= −
.
b. Chuyển ràng buộc bất đẳng thức về ràng buộc đẳng thức
•
1 1
; 0
n n
ij j i ij j n i i n i
j j
a x b a x x b x
+ +
= =
≤ ⇒ + = ≥
∑ ∑
•
1 1
; 0
n n
ij j i ij j n i i n i
j j
a x b a x x b x
+ +
= =
≥ ⇒ − = ≥
∑ ∑
(các biến
n i

x
+
được gọi là các biến bù)
c. Chuyển ràng buộc về dấu
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
5
•
j j
0 ; 0
j j
x x x x
′ ′
≤ ⇒ = − ≥
•
; 0; 0
j j j n j j n j
x x x x x x
+ +
′ ′ ′ ′
∈ ⇒ = − ≥ ≥¡
.
Ví dụ. Đưa bài toán sau về dạng chính tắc:
Tìm
( )
1 2 3
, ,x x x x=
sao cho
( )
1 2
2 minf x x x= − →

với các điều kiện
1 2 3
1 2 3
1 2 3
2 3
2 5
2 2 3
4
0, 0
x x x
x x x
x x x
x x
− + ≤


− − ≥


+ + =


≥ ≥

Thay
1 4 5
x x x= −
, với
4 5
0, 0x x≥ ≥

và thêm 2 biến phụ
6 7
, 0x x ≥
, bài toán trên tương
đương với bài toán dạng chính tắc tìm
( )
2 3 4 5 6 7
, , , , ,x x x x x x x=
sao cho
( ) ( )
2 4 5
2 minf x x x x= − + − →
với các điều kiện
2 3 4 5 6
2 3 4 5 7
2 3 4 5
2 2
2 2 2 3
4
0, 1,7
j
x x x x x
x x x x x
x x x x
x j
− + + − + =


− − + − − =



+ + − =


≥ =

Ví dụ. Đưa bài toán sau về dạng chính tắc
Tìm
( )
1 2 3
, ,x x x x=
sao cho
1 2 3
2 axx x x m+ − →
với các điều kiện
1 2 3
1 2
1 2 3
2 5
1
0, 0,
x x x
x x
x x x
+ − ≤


− ≥



≥ ≥ ∈

¡
Dạng chính tắc của bài toán trên là:
( )
1 2 4 5
2 ming x x x x x= − − + − →
với các điều kiện
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
6
1 2 4 5 6
1 2 7
1 2 4 5 6 7
2 5
1
, , , , , 0
x x x x x
x x x
x x x x x x
+ − + + =


− − =


≥

1.4. Một số khái niệm trong giải tích lồi
Định nghĩa. Đoạn thẳng với 2 đầu mút
,

n
a b∈¡
được kí hiệu và xác định như sau:
[ ]
( )
{ }
, : 1 0 1a b a b
λ λ λ
= + − ≤ ≤
.
Định nghĩa. Tập hợp
n
C ⊂ ¡
được gọi là tập hợp lồi nếu lấy 2 điểm bất kì
,a b C∈
thì
[ ]
,a b C⊂
.
Định nghĩa. Cho tập lồi
n
C ⊂ ¡
. Điểm
x C
∈
được gọi là điểm cực biên (đỉnh) của tập lồi
C
nếu
x
không là điểm trong của bất kì đoạn thẳng nào có 2 đầu mút trong

C
.
Định nghĩa. Một tập hợp
n
P ⊂ ¡
được gọi là một tập lồi đa diện nếu nó là giao của một
số hữu hạn các nửa không gian. Nói cách khác một tập lồi đa diện là tập nghiệm của một
hệ hữu hạn các bất đẳng thức tuyến tính
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2

n n
n n
m m mn n m
a x a x a x b
a x a x a x b
a x a x a x b
+ + + ≤


+ + + ≤




+ + + ≤

L
L

M
Tập lồi đa diện bị chặn thì gọi là đa diện lồi.
1.5. Các tính chất của bài toán QHTT
Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu quan trọng và được ứng
dụng rộng rãi nhất trong thực tiễn. Quy hoạch tuyến tính bắt nguồn từ những nghiên cứu
của nhà toán học người Nga Kantorovich L.V. trong các công trình về bài toán kế hoạch
hóa sản xuất
Công bố năm 1939. Năm 1947 nhà toán học người mỹ G. Dantzig đã đưa ra phương pháp
đơn hình đã được chạy trên máy tính điện tử ở Mỹ. Ngày nay có nhiều phần mềm dùng để
giải quyết các bài toán quy hoạch tuyến tính như Maple, Matlab,…
Trong phần này chúng tôi chỉ trình bày một số tính chất cơ bản của bài toán QHTT để từ
đó chuẩn bị cơ sở cho việc trình bày phương pháp đơn hình ở bài sau.
1.5.1. Bài toán QHTT dạng tổng quát
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
7
Ta có các tính chất sau:
a. Tập các phương án của bài toán là một tập lồi đóng.
b. Tập các phương án tối ưu của bài toán là một tập lồi (có thể bằng rỗng).
c. Nếu tập các phương án là bị chặn khác rỗng (tức nó là đa diện) thì bài toán có phương
án tối ưu.
1.5.2. Bài toán QHTT dạng chính tắc
Kí hiệu
( )
( )
1 1
1 ij
, , , , ,
n
m n
m n

b x
c c c b A a x
b x
×
   
 ÷  ÷
= = = =
 ÷  ÷
 ÷  ÷
   
M M
Bài toán được viết lại như sau:
Tìm vectơ
( )
1
, ,
t
n
x x x=
sao cho
( )
, minf x c x= →
với các điều kiện
0
A x b
x
=


≥


Giả thiết
,m n RankA m≤ =
.
Kí hiệu
1
, 1,
j
j
mj
a
A j n
a
 
 ÷
= =
 ÷
 ÷
 
M
.
Định nghĩa. Phương án cực biên là phương án mà là điểm cực biên.
Định lý. Giả sử
( )
1
, ,
n
x x x=
là phương án của bài toán (CP).
Đặt

{ }
{ }
1,2, , 0
x j
J J j n x= = ∈ >
. Khi đó
x
là một phương án cực biên khi và chỉ khi các
vectơ cột của A ứng với các thành phần dương của
x

{ }
j
A j J∈
là độc lập tuyến tính.
Ví dụ. Cho bài toán QHTT dạng chính tắc với các điều kiện
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
8
1 2 3
1 2
4
0
0, 1,2,3
i
x x x
x x
x i
+ + =



− =


≥ =

Hãy cho biết các vecto
( ) ( ) ( )
1 2 3
2,2,0 ; 0,0,4 ; 1,1,2x x x= = =
có phải là các phương án cực
biên không?
Hướng dẫn. Kiểm tra trực tiếp, ta thấy các vecto trên thỏa mãn điều kiện của bài toán nên
là các phương án của bài toán.
Ta có thể kiểm tra với ba hệ
{ } { } { }
1 2 3 1 2 3
, ; ; , ,A A A A A A
trong đó
1 2 1
1 1 1
; ;
1 1 0
A A A
     
= = =
     
−
     
, chỉ có hai hệ
{ } { }

1 2 3
, ;A A A
là độc lập tuyến tính. Do đó
1 2
,x x
là phương án cực biên.
Chú ý. Nếu ma trận A có chứa ma trận đơn vị cấp k thì ta có ngay phương án cực biên
0
x
của bài toán.
Từ định lý trên ta có các hệ quả sau:
Hệ quả . Số các thành phần dương của một phương án cực biên tối đa là bằng m, trong
trường hợp số thành phần dương của phương án cực biên là m thì phương án cực biên đó
gọi là không suy biến, ngược lại là phương án cực biên suy biến.
Hệ quả . Tập các phương án cực biên là hữu hạn (có thể bằng rỗng).
Ví dụ. Tìm phương án cực biên không suy biến của bài toán QHTT với các ràng buộc sau
1 2 3
1 2 3
3 2 3 6
2 4
0, 1,2,3
i
x x x
x x x
x i
− + =


− + − =



≥ =

Giải. Vì bài toán chỉ có hai ràng buộc chính biến nên số thành phần dương của một
phương án cực biên nhiều nhất chỉ là 2.
Thay
1
0x =
vào hệ trên và giải hệ, ta được
2 3
9
, 5
2
x x= =
.
Thay
2
0x =
vào hệ trên và giải hệ thì hệ vô nghiệm.
Thay
3
0x =
vào hệ trên và giải hệ, ta được
1 2
9
5,
2
x x= =
.
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền

9
Kiểm tra như ví dụ trước, ta có cả hai phương án
9 9
0, ,5 ; 5, ,0
2 2
   
 ÷  ÷
   
là hai phương án cực
biên không suy biến.
Định lý . Nếu bài toán QHTT có phương án thì nó có phương án cực biên.
Định lý. Bài toán QHTT (dạng tổng quát) dạng min có phương án tối ưu khi và chỉ khi
tập các phương án D khác rỗng và hàm mục tiêu bị chặn dưới trên D.
(tức là
( )
: ,h f x h x D∃ ∈ ≥ ∀ ∈¡
).
Định lý. Nếu bài toán có phương án tối ưu thì nó cũng có phương án cực biên tối ưu.
Nhận xét. Từ định lý trên ta thấy rằng ta chỉ cần tìm phương án tối ưu trong số các
phương án cực biên (số các phương án cực biên là hữu hạn). Đây là cơ sở của lý thuyết
thuật toán đơn hình ở phần sau.
Tóm lại: Đối với bài toán QHTT thì có các khả năng sau có thể xảy ra
TH1. Bài toán không có phương án.
TH2. Bài toán có phương án nhưng hàm mục tiêu không bị chặn dưới (không có phương
án tối ưu).
TH3. Bài toán có phương án và hàm mục tiêu bị chặn dưới khi và chỉ khi bài toán có
phương án tối ưu.
Bài tập chương 1
Bài 1. Một xí nghiệp dệt dự định sản xuất 3 loại vải A, B, C. Nguyên liệu để sản xuất là
các loại sợi cotton, katé, polyester, xí nghiệp đã chuẩn bị được với khối lượng tương ứng

là 3 tấn; 2,5 tấn; 4,2 tấn. Mức tiêu hao mỗi loại sợi để sản xuất 1m vải và giá bán (ngàn
đồng/ m) vải thành phẩm mỗi loại được cho trong bảng sau:
N
guyên liệu
(g)
Sản phẩm
A B C
Cotton 200 200 100
Katé 100 200 100
Polyester 100 100 100
Giá bán 35 48 25
Hỏi xí nghiệp cần phải sản xuất bao nhiêu loại vải A, B, C để cho tổng thu lớn nhất.
Hãy lập mô hình toán học cho bài toán trên.
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
10
Bài 2. Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng đạm, đường, khoáng cho
một loại gia súc tương ứng 90g, 130g, 10g. Một người chăn nuôi cần mua 3 loại thức ăn
A, B, C biết rằng hàm lượng các chất dinh dưỡng trên có trong 1 g thức ăn A, B, C và giá
mua mỗi kg thức ăn mỗi loại được cho trong bảng sau:
Chất
Dinh
dưỡng
Loại thức ăn
A B C
Đạm 0,1g 0,2g 0,3g
Đường 0,3g 0,4g 0,2g
Khoáng 0,02g 0,01g 0,03g
Giá mua 3000đ 4000đ 5000đ
Hỏi người chăn nuôi phải mua bao nhiêu kg thức ăn A, B, C sao cho vẫn đảm bảo tốt chất
dinh dưỡng cho bữa ăn của gia súc mà số tiền chi mua thức ăn là ít nhất.

Hãy lập mô hình toán học cho bài toán trên.
Bài 3. Một công ti lương thực cần vận chuyển gạo từ các kho A
1
, A
2
với khối lượng lần
lượt là 100 tấn, 150 tấn đến các đại lí B
1
, B
2
, B
3
với nhu cầu nhập hàng lần lượt là 70 tấn,
110 tấn, 90 tấn. Cho biết chi phí vận chuyển gạo (ngàn/ tấn) từ các kho đến các đại lí
được cho trong bảng sau:
B
1
B
2
B
3
A
1
100 70 30
A
2
50 90 60

Hỏi phải vận chuyển thế nào để các kho đều phát hết gạo và các đại lí đều nhận đủ số gạo
cần và chi phí vận chuyển là nhỏ nhất?

Hãy lập mô hình toán học cho bài toán trên.
Bài 4. Tìm các phương án cực biên không suy biến của bài toán QHTT với các ràng buộc
sau
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
11
Đại lí
Chi phí
Kho
1 2 3
1 2 3
1
) 6
0, 1,2,3
− − =


+ + =


≥ =

i
x x x
a x x x
x i
1 2 3
1 2 3
2 3 14
) 10
0, 1,2,3

− + =


+ + =


≥ =

i
x x x
b x x x
x i
CHƯƠNG II: PHƯƠNG PHÁP ĐƠN HÌNH
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
12
Phương pháp: Dantzig đề xuất một thuật toán như sau
Xuất phát từ phương án cực biên
0
x
, kiểm tra xem
0
x
có phải là lời giải tối ưu hay chưa,
nếu nó chưa phải là lời giải tối ưu thì tìm cách cải tiến nó để được một phương án cực
biên khác là
1
x
tốt hơn
0
x

theo nghĩa
( ) ( )
1 0
f x f x<
. Quá trình này lặp đi lặp lại nhiều
lần. Vì số phương án cực biên là hữu hạn nên sau hữu hạn bước lặp ta được phương án
cực biên tối ưu hoặc kết luận là bài toán không có lời giải.
Xét bài toán chính tắc (CP):
( )
, minf x c x= →
với các điều kiện
Ax =b
x 0


≥

Giả sử
rankA m=
(
m
là số dòng). Ta chỉ xét bài toán mà số các thành phần dương của các
phương án cực biên của nó đúng bằng
m
(bài toán không suy biến).
2.1. Cơ sở của phương pháp
Định nghĩa. Ta gọi cơ sở của ma trận A là một bộ gồm
m
vectơ cột độc lập tuyến tính
{ }

1 2
, , ,
m
j j j
A A A
của nó.
Giả sử
( )
0 0 0
1
, ,
n
x x x=
là phương án cực biên xuất phát đã biết,
{ }
{ }
{ }
( )
0
0
0
0 0
0
1, , 0 ,
,
: .
j
j
j
J j n x

A j J
x x j J
= ∈ >
= ∈
= ∈
0
0
B
B
Do
rankA m
=
nên mọi vectơ cột
k
A
với
{ }
1, ,k n∈
đều có thể biểu diễn qua các vectơ
{ }
0j
A j J∈
,
( )
0
, 1, . 2.1
k jk j
j J
A z A k n
∈

= =
∑
Kí hiệu
( )
0
:
t
k jk
z z j J= ∈
. Khi đó
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
13
( )
1
0 0
1
k k k k
A B z z B A
−
⇔ = ⇔ =
,
trong đó
( )
0 0
:
j
B A j J= ∈
.
Ta gọi
0

J
: tập chỉ số cơ sở
0
B
: ma trận cơ sở
j
A
với
0
j J∈
: các vectơ cơ sở (ứng với các thành phần dương)
k
A
với
0
k J∉
: các vectơ phi cơ sở
0
0
,
j
x j J∈
: các biến cơ sở
0
0
,
k
x k J∉
: các biến phi cơ sở.
Với mỗi

1,k n=
, kí hiệu
0
k j jk k
j J
c z c
∈
∆ = −
∑
. Nếu
0
k J∈
thì
0
k
∆ =
.
Định lý. (Điều kiện tối ưu)
Nếu
0, 1,
k
k n∆ ≤ ∀ =
thì
0
x
là phương án tối ưu.
Định lý. (Điều kiện để hàm mục tiêu không bị chặn dưới)
Nếu tồn tại chỉ số
0
k J∉

để
0
k
∆ >
sao cho
0
0,
jk
z j J≤ ∀ ∈
thì hàm mục tiêu không bị chặn
dưới trên tập các phương án. Do đó, bài toán không có phương án tối ưu.
Viết lại bằng kí hiệu:
Nếu:
0
, 0
k
k J∉ ∆ >
mà
0
0,
jk
z j J≤ ∀ ∈
thì
( )
f x → −∞
.
Định lý. (Cách chuyển sang phương án cực biên tốt hơn)
Giả sử tồn tại
{ }
1, ,k n∈

sao cho
0
k
∆ >
và ứng với k ấy tồn tại chỉ số
0
r J∈
sao cho
0
rk
z >
thì tồn tại một phương án cực biên mới
1
x
” tốt hơn” phương án
0
x
theo nghĩa
( ) ( )
1 0
f x f x<
.
Gợi ý chứng minh:
Đặt
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
14
0
0 0
0
0 0

1
0
0
, , 0;
,
,
0 , ,
r
rk
rk
j jk
j
x
r J z
z
x z j J
x j k
j J j k
θ
θ
θ
= ∈ >

− ∈

= =


∉ ≠


Ta chứng minh
1
x
được xác định như trên là phương án cực biên với
( ) ( )
1 0
f x f x<
.
2.2. Thuật toán đơn hình cơ sở
Bước 0. Có phương án cực biên
0
x
, xác định
( )
jk
z
,
0
k j jk k
j J
c z c
∈
∆ = −
∑
.
Bước 1. Kiểm tra điều kiện tối ưu
a. Nếu
0, 1,
k
k n∆ ≤ ∀ =

thì kết luận
0
x
là phương án tối ưu. Dừng thuật toán.
b. Nếu
{ }
1, , : 0
k
k n∃ ∈ ∆ >
chuyển sang bước 2
Bước 2. Kiểm tra hàm mục tiêu không bị chặn dưới
Nếu
0
0 : 0,
k jk
z j J∃∆ > ≤ ∀ ∈
thì
( )
f x → −∞
. Dừng thuật toán. Kết luận bài toán vô
nghiệm.
Khi điều kiện của bước 1 và bước 2 không thỏa mãn thì chuyển sang bước 3.
Bước 3. Chuyển sang phương án cực biên tốt hơn
• Tìm vectơ đưa vào cơ sở: Chọn chỉ số
0
s J∉
sao cho
{ }
k 0
ax 0,

s
m k J∆ = ∆ > ∉
, khi
đó
s
A
được đưa vào cơ sở.
• Tìm vectơ đưa ra cơ sở: Xác định chỉ số
0
r J∈
sao cho
0
0
0
min , , 0
j
r
js
rs js
x
x
j J z
z z
 
 
= ∈ >
 
 
 
khi đó ta chọn

r
A
đưa ra cơ sở.
• Xác định
( )
1 1 1 1
1 2
, , ,
n
x x x x=
theo công thức sau:
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
15
{ }
{ }
0
0
0
1
0
0
, \
0 ,
,
r js
j
rs
j
r
rs

x z
x j J r
z
x j J s
x
j s
z

− ∈



= ∉ ∪



=


(*)
Đặt
{ } { }
1 0
\J J r s= ∪
. Quay lại bước 0 ứng với
1
x
và
1
J

.
Vì số phương án cực biên là hữu hạn nên thuật toán đơn hình sẽ dừng lại sau hữu hạn
bước.
Sơ đồ khối của thuật toán đơn hình
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
có
Nghiệm
Vô Nghiệm
Xét các cột với và
Xét các
không
16
Tìm
Tìm
Biến đổi theo (*)
2.3. Công thức chuyển cơ sở
Trong bước 3 ta có phương án cực biên mới
( )
1 1 1 1
1 2
, , ,
n
x x x x=
. Từ số liệu hiện có cho
phương án cũ
0
x
, ta cần đưa ra công thức tính số liệu cho phương án mới
1
x

.
Đặt
{ } { }
1 0
\J J r s= ∪
. Khi đó
{ }
0
0
1
1
1
0
, \
0 ,
,
r js
j
rs
j
r
rs
x z
x j J s
z
x j J
x
j s
z


− ∈



= ∉



=


( ) ( )
0
1 0
r
s
rs
x
f x f x
z
= − ∆
Gọi
( )
1 1
1
:
k jk
z z j J= ∈
là các hệ số biểu diễn của các vectơ cột của ma trận A qua cơ sở
mới

{ }
1
:
j
A j J∈
. Khi đó
{ }
1
1
,
. , \
rk
rs
jk
rk
jk js
rs
z
j s
z
z
z
z z j J s
z

=


=



− ∈


1
.
rk
k k s
rs
z
z
∆ = ∆ − ∆
Với
1
k J∈
thì
1
0
k
∆ =
.
2.4. Cách lập bảng đơn hình và chuyển bảng đơn hình
Thuật toán đơn hình thường được biểu diễn dưới dạng bảng. Mỗi bước ứng với một
phương án cực biên là một bảng đơn hình.
Mỗi bảng đơn hình gồm
( )
3n +
cột và cách ghi số liệu trên bảng đơn hình như sau:
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
17

1
c
2
c
n
c
( )
0j
c j J∈
( )
0j
A j J∈
0
j
x
1
A
2
A
s
A
n
A
.
.
.
r
A
.
.

.
0
r
x
.
.
.
1r
z
.
.
.
rs
z
( )
0
f x
1
∆
2
∆
s
∆
n
∆
Giá trị
( )
0
f x
và các ước lượng

, 1,
j
j n∆ =
được tính ngay trên bảng đơn hình. Sau khi
tính các ước lượng ta tiến hành kiểm tra tính tối ưu, tính không bị chặn của hàm mục tiêu.
Nếu thỏa một trong hai tính trên thì thuật toán kết thúc, còn không ta xây dựng một
phương án cực biên mới ứng với bảng đơn hình mới. Để xây dựng bảng đơn hình tiếp
theo ta lần lượt làm các việc sau:
• Tìm cột xoay: Nếu phương án chưa thỏa tính tối ưu thì cột
s
ứng với véctơ đưa
vào cơ sở
s
A
là cột xoay.
• Tìm dòng xoay: Theo quy tắc tìm véctơ đưa ra cơ sở, nếu tìm được véctơ đưa ra là
r
A
thì
r
là dòng xoay.
• Tìm phần tử xoay: Ta có dòng
r
A
của ma trận
A
là dòng xoay, cột
s
A
của ma trận

A
là cột xoay, khi đó phần tử
rs
z
được gọi là phần tử xoay.
Từ bảng đơn hình này ta lập bảng đơn hình tiếp theo như sau:
• Trên dòng xoay thay
r
A
bởi
s
A
.
• Từ các công thức phần trước để tính các số liệu mới ta dùng quy tắc hình chữ
nhật như sau:
* Trên dòng xoay:
+ Giá trị mới =
* Trên các dòng khác

+ Giá trị mới = giá trị cũ
−
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
18
giá trị cũ (vị trí tương ứng)
phần tử xoay
ptử trên dòng xoay ptử trên cột xoay
phần tử xoay
(tương ứng vị trí của phần tử cần tìm trên hình chữ nhật)

bd

a'=a -
x
⇒
, trong đó
x
là phần tử xoay.
Ví dụ. Giải bài toán QHTT sau:
Tìm
( )
5
1 5
, ,x x x= ∈¡
sao cho
( )
1 2 3 5
2 3 minf x x x x x= + − + →
với các điều kiện
1 2 3
1 2 4
1 2 5
3
2 4
3 5
0, 1,5
j
x x x
x x x
x x x
x j
− + =



+ + =


− + + =


≥ ∀ =

Bài giải:
Ta có
1 2 3 4 5
1 1 1 0 0
2 , 1 , 0 , 1 , 0
1 3 0 0 1
A A A A A
−
         
 ÷  ÷  ÷  ÷  ÷
= = = = =
 ÷  ÷  ÷  ÷  ÷
 ÷  ÷  ÷  ÷  ÷
−
         
.
Ta thấy rằng
{ }
3 4 5
, ,A A A

độc lập tuyến tính.
Do đó ta có ngay phương án cực biên xuất phát là
( )
0,0,3,4,5
.
Bảng đơn hình:
2 3 -1 0 1
j
c
j
A
j
x
1
A
2
A
3
A
4
A
5
A
-1
0
1
3
A
4
A

5
A
3
4
5
1
2
-1
-1
1
3
1
0
0
0
1
0
0
0
1
f = 2 -4 1 0 0 0
-1
0
3
3
A
4
A
2
A

14/3
7/3
5/3
2/3
7/3
-1/3
0
0
1
1
0
0
0
1
0
1/3
-1/3
1/3
f = 1/3 -11/3 0 0 0 -1/3
Ở bước lặp thứ hai,
0, 1,5
j
j∆ ≤ ∀ =
, do đó phương án ở bước lặp này là tối ưu.
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
19
a
d
b x
Vậy

f
đạt min tại
( )
* 0,5/ 3,14/3,7 / 3,0x =
và
( )
* 1/3f x =
.
2.5. Tìm phương án cực biên xuất phát – Giải bài toán QHTT tổng quát
Thuật toán đơn hình cơ sở chỉ áp dụng giải bài toán QHTT dạng chính tắc khi đã có sẵn
cơ sở đơn vị và phương án cực biên xuất phát của nó. Tuy nhiên không phải lúc nào ta
cũng gặp may như vậy. Trong trường hợp đó, ta phải tìm cách đưa bài toán đã cho về
dạng có thể áp dụng thuật toán đơn hình cơ sở mà tìm ra phương án cực biên xuất phát.
Một trong những cách đó là dùng biến giả sẽ được trình bày dưới đây thông qua thuật
toán đánh thuế.
2.5.1. Thiết lập bài toán (M – lớn)
Xét bài toán QHTT dạng chính tắc (CP):
( )
, minf x c x= →
với các điều kiện
Ax b
x 0
=


≥


giả thiết
0b ≥

.
Với
0M >
, ta xét bài toán sau (gọi là bài toán (
M
-lớn)):
( )
1
, , min
m
i
i
g x t c x M t
=
= + →
∑
với các điều kiện
( )
Ax + t = b
x, t 0



≥


trong đó
, 1,
i
t i m=

được gọi là các biến giả,
M
là số dương rất lớn.
2.5.2. Mối liên hệ giữa bài toán gốc và bài toán
M
-lớn
Định lý. (quan hệ giữa bài toán gốc và bài toán
M
-lớn)
• Nếu bài toán gốc (CP) có phương án thì mọi phương án cực biên tối ưu
( )
,x t
của
bài toán
M
-lớn phải có
0t =
.
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
20
• Bài toán (CP) có phương án tối ưu
x
khi và chỉ khi bài toán
M
-lớn có phương án
tối ưu
( )
,0x
.
Nhận xét.

1. Định lý trên cho phép ta đưa việc giải bài toán gốc (chưa biết phương ná cực biên xuất
phát) về việc giải bài toán
M
-lớn mà bài toán này có ngay phương án cực biên xuất phát
là
( )
0,b
với cơ sở đơn vị. Có các trường hợp sau xảy ra:
• Khi bài toán
M
-lớn có phương án tối ưu
( )
*,0x
thì
*x
là lời giải cho bài toán gốc
(CP).
• Khi bài toán
M
-lớn có phương án tối ưu
( )
*, *x t
với
* 0t
≠
bài toán gốc (CP)
không có phương án.
• Khi bài toán
M
-lớn không có phương án tối ưu thì bài toán gốc không có phương

án tối ưu.
2. Trong khi giải bài toán
M
-lớn ta không cần biết chính xác giá trị M mà ta chỉ cần giả
thiết rằng M đủ lớn, lớn hơn mọi giá trị mà trong thuật toán cần phải so sánh với nó.
Các biệt thức
k
∆
có dạng
, 1,
k k k
M k n m
α β
∆ = + = +
(
,
k k
α β
là tính được cụ thể).
Nếu trong bài toán gốc đã có sẵn k biến đơn vị thì ta chỉ cần thêm
( )
m k−
biến giả trong
bài toán
M
-lớn.
2.5.3. Thuật toán đánh thuế
(i) Lập bài toán
M
-lớn. Lập biến giả cho những vecto đơn vị còn thiếu, nếu trong

bài toán gốc đã có sẵn
k
biến đơn vị thì ta chỉ cần thêm
( )
m k−
biến giả trong bài toán
M
-lớn. Lập bảng đơn hình xuất phát: các biệt thức
k
∆
có dạng
, 1,
k k k
M k n m
α β
∆ = + = +
nên tách ra hai dòng, dòng trên là
k
α
, dòng dưới là
k
β
.
(ii) Áp dụng phương pháp đơn hình giải. Khi giải so sánh các ước lượng
k k k
M
α β
∆ = +
, ta áp dụng theo quy tắc:
a.

0
k
∆ <
nếu
0
k
β
<
hoặc
( 0, 0)
k k
β α
= <
.
b.
0
k
∆ >
nếu
0
k
β
>
hoặc
( 0, 0)
k k
β α
= >
.
c.

k l
∆ < ∆
nếu
k l
β β
<
hoặc
,
k l k l
β β α α
= <
.
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
21
Ví dụ. Giải bài toán QHTT sau:
( )
1 2 3
1 2 3 4
1 2 3
1 2 5
1,2,3,4 5
12 8 min
2 2 3 10
4 8
4 4 8
0,
f x x x x
x x x x
x x x
x x x

x x
= + + →
+ + + =


+ + =


+ + =


≥ ∈

¡
Bài giải:
Ta xét bài toán
M
-lớn tương ứng của bài toán trên như sau:
( )
1 2 3 8
1 2 3 4
1 2 3 8
1 2 6 7
1,2,3,4,6,7 5 6 7
12 8 min
2 2 3 10
4 8
4 4 8
0,
g x x x x Mx

x x x x
x x x x
x x x x
x x x x
= + + + →
+ + + =


+ + + =


+ + − =


≥ = −

Phương án cực biên xuất phát của bài toán
M
-lớn là
( )
0,0,0,10,8,0,8
.
Bảng đơn hình
12 8 1 0 0 0 M
j
c
j
A
j
x

1
A
2
A
3
A
4
A
6
A
7
A
8
A
0
M
0
4
A
8
A
6
A
10
8
8
2(
41
z
)

1(
81
z
)
4(
61
z
)
2(
42
z
)
4(
82
z
)
4(
62
z
)
3
1
0
1
0
0
0
0
1
0

0
-1
0
1
0
k
α
0 -12 -8 -1 0 0 0 0
k
β
8 1 4 1 0 0 0 0
0
8
0
4
A
2
A
6
A
6
2
0
3/2
1/4
3
0
1
0
5/2

1/4
-1
1
0
0
0
0
1
0
0
-1
-1/2
1/4
-1
k
α
16 -10 0 1 0 0 0 2
k
β
0 0 0 0 0 0 0 -1
1
8
0
3
A
2
A
6
A
12/5

7/5
12/5
3/5
1/10
18/5
0
1
0
1
0
0
2/5
-1/10
2/5
0
0
1
0
0
-1
-1/5
3/10
-6/5
k
α
68/5 -53/5 0 0 -2/5 0 0 11/5
k
β
0 0 0 0 0 0 0 -1
Vậy

min
68/ 5g =
tại
( )
0,7 /5,12 /5,0,12/ 5,0x =
.
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
22
Do đó
min
68/ 5f =
tại
( )
0,7 /5,12 /5,0,12/ 5x =
.
Bài tập chương II
Bài 1. Một xí nghiệp có thể sản xuất 4 loại mặt hàng: H
1
,H
2
,H
3
,H
4
. Để sản xuất 4 loại mặt
hàng này, xí nghiệp dùng 2 loại nguyên liệu N
1
, N
2
. Số nguyên liệu mà xí nghiệp huy

động được tối đa tương ứng là 600kg ,800kg .Định mức tiêu hao mỗi loại nguyên liệu đối
với mỗi loại mặt hàng cũng như lãi 1 đơn vị hàng mặt hàng được cho trong bảng :

Hàng
Suất tiêu hao
Nguyên liệu
H
1
H
2
H
3
H
4
N
1
: 600Kg 0.5 0.2 0.3 0.6
N
2
: 800Kg 0.1 0.4 0.2 0.5
Lãi 0.8 0.3 0.4 0.4
Hãy tìm phương án sản xuất mỗi loại mặt hàng bao nhiêu đơn vị để tổng số lãi thu được
lớn nhất. Lập mô hình cho bài toán trên và giải bằng phương pháp đơn hình.
Bài 2. Bài toán pha trộn:
Một xí nghiệp luyện kim muốn sản xuất một loại hợp kim với 20% bạc , 30% đồng và
50% nhôm. Học sử dụng các nguyên liệu: bạc, đồng nhôm. Hợp kim A, hợp kim B, hợp
kim C, hàm lượng bạc, đồng, nhôm trong các nguyên liệu trên cũng như giá một đơn vị
khối lượng mỗi loại
( USD/kg ) được cho trong bảng dưới đây:


Hàng
Suất tiêu hao
Nguyên liệu
Bạc Đồng Nhôm A B C
Bạc 100% 0 0 30% 50% 40%
Đồng 0 100% 0 40% 20% 35%
Nhôm 0 0 100% 30% 30% 25%
Giá 1500 300 100 1000 1200 1100
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
23
Hãy lập phương án pha trộn như thế nào để giá thành là nhỏ nhất ( x
i
là khối lượng của
các chất và tỉ lệ các chất có trong các hợp kim).
Bài 3. Giải các bài toán QHTT sau
a. Tìm vecto
( )
1 2 3 4
, , ,x x x x x=
sao cho

( )
1 2 3 4
1
2 4 3 min
2
f x x x x x= + + − →
với các điều kiện
1 2 3 4
1 2 3 4

1 2 3 4
1,2,3,4
2 2 3 3 50
4 8 2 3 80
4 4 2 40
0
x x x x
x x x x
x x x x
x
+ + + ≤


+ + + =


+ + + =


≥

b. Tìm vecto
( )
1 2 3 4
, , ,x x x x x=
sao cho
( )
1 2 3 4
2 minf x x x x x= + − − →
với các điều kiện

1 2 3 4
1 2 3 4
1 2 3 4
1,2,3,4
2 2
2 3 6
7
0
x x x x
x x x x
x x x x
x
− + − =


+ − + =


+ + + =


≥

c. Tìm vecto
( )
1 2 3
, ,x x x x=
sao cho
( )
1 2 3

5 8 maxf x x x x= + + →
với các điều kiện
1 2 3
1 2 3
1 2 3
1,2,3
7
2 3 3 12
3 6 5 24
0
x x x
x x x
x x x
x
+ + ≤


+ + ≤


+ + ≤


≥

Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
24
CHƯƠNG III: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU
3.1. Bài toán đối ngẫu
Cho các bài toán QHTT:

( )
( )
( )
( )
( )
( )
( )
( )
1 1 2 2
1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 1 3
1
2
3
min



0
0
n n
i i i i
i i i i
i i i i
j
j
j
f x c x c x c x
a x a x a x b i I

a x a x a x b i I
P
a x a x a x b i I
x j J
x j J
x j J
= + + + →



+ + + ≥ ∈



+ + + = ∈




+ + + ≤ ∈




≥ ∈




∈ ∈




≤ ∈




¡

( )
( )
( )
( )
( )
( )
( )
( )
1 1 2 2
1 1 2 2 1
1 1 2 2 2
1 1 2 2 3
1
2
3
ax



0

0
m m
j j mj m j
j j mj m j
j j mj m i
i
i
i
g y b y b y b y m
a y a y a y c j J
a y a y a y c j J
D
a y a y a y c j J
y i I
y i I
y i I
= + + + →




+ + + ≤ ∈




+ + + = ∈





+ + + ≥ ∈




≥ ∈




∈ ∈




≤ ∈


¡

Người ta gọi bài toán (P) là bài toán gốc và (D) là bài toán đối ngẫu của bài toán (P).
Qui tắc lập bài toán đối ngẫu:
Bài toán gốc Bài toán đối ngẫu
∑
=
→=
n
j
jj

xcxf
1
min)(
max)(
1
→=
∑
=
m
i
ii
ybyg
• Ràng buộc thứ i
i
b≥
• Ràng buộc thứ i
i
b=
• Ràng buộc thứ i
i
b≤
• Dấu ẩn
0
i
y ≥
• Dấu
i
y
tùy ý
• Dấu

0
i
y ≤

• Dấu
0
j
x ≥
• Dấu
j
x
tùy ý
• Dấu
0
j
x ≤
• Ràng buộc thứ j
j
c≤
• Ràng buộc thứ j
j
c=
• Ràng buộc thứ j
j
c≥
Ví dụ. Viết bài toán đối ngẫu cho bài toán sau:
Tìm vectơ
( )
1 5
, ,x x x=

sao cho
Giáo viên thực hiện: Nguyễn Thị Mộng Tuyền
25