1
Năm 2014 2

MỤC LỤC Trang

CHƯƠNG 1. Bài toán quy hoạch tuyến tính 4
1.1. Các ví dụ dẫn tới bài toán QHTT 4
1.1.1. Bài toán lập thực ñơn
4
1.1.2. Bài toán lập kế hoạch sản xuất 4

2.2.3. Bảng ñơn hình 14
2.3. Thuật toán ñơn hình ñối với bài toán chuẩn 16
2.4. Giải bài toán QHTT tổng quát, phương pháp hai pha, phương pháp bài toán M 16
2.4.1. Thuật toán ñơn hình hai pha 16
2.4.2. Phương pháp ñánh thuế 17

3

2.5. Vn ủ bi toỏn suy bin 17
Cõu hi, bi tp, ni dung ụn tp v tho lun 17
CHNG 3. Cỏc bi toỏn ủi ngu
22
3.1. Khỏi nim v cỏc bi toỏn ủi ngu 22
3.1.1. Nguyờn tc thit lõp bi toỏn ủi ngu 22
3.1.2. Cỏc dng bi toỏn ủi ngu 22
3.2. Cỏc ủnh lý ủi ngu v ng dng 23
3.2.1. Quan h gia cp bi toỏn ủi ngu 23
3.2.2. nh lý ủi ngu 23
3.3. Phng phỏp ủn hỡnh ủi ngu 23
3.3.1. C s chp nhn ủc ủi ngu 23
3.3.2. Th tc ủn hỡnh ủi ngu khi bit c s chp nhn ủc ủi ngu 24
3.3.3. Thut toỏn ủn hỡnh ủi ngu khi cha bit c s chp nhn ủc ủi ngu 24
3.4. Tìm nghiệm của một cặp bài toán đối ngẫu bằng giải hệ phơng trình tuyến tính 25
Cõu hi ụn tp v tho lun 25
CHNG 4. Phng phỏp phõn phi
29
4.1. Gii thiu bi toỏn. Lp bi toỏn di dng bng 29
4.1.1. Thit lp bi toỏn 29
4.1.2. iu kin tn ti nghim 30
4.1.3. Bng vn ti, cỏc tớnh cht ca bng 30

Có n loại thực phẩm
(
)
njT
j
,1, =
. Biết rằng mỗi ñơn vị
j
T
chứa
ij
a
ñơn vị chất
(
)
mii ,1, =

và có giá thành là
j
c
ñơn vị tiền. Hãy lập một thực ñơn sao cho bữa ăn phải ñảm bảo có ít nhất
i
b
ñơn vị chất dinh dưỡng
(
)
mii ,1, =
mà có giá thành rẻ nhất.
Lập bài toán: Gọi
j

1
ñơn vị tiền.
Mô hình toán học của bài toán:
Tìm các
(
)
njx
j
,1; =
sao cho hàm:
( )
∑
=
=
n
j
jj
xcxf
1
ñạt giá trị nhỏ nhất với hệ ñiều kiện:
njxmibxa
ji
n
j
jij
,1;0;,1,
1
=≥=≥
∑
=

(
)
; 1,
j
x j n
=
sao cho hàm:
( )
1
n
j j
j
f x c x
=
=
∑
ñạt giá trị lớn nhất với hệ ñiều kiện:
1
, 1, ; 0; 1,
n
ij j i j
j
a x b i m x j n
=
≤ = ≥ =
∑
.
1.1.3. Bài toán vận tải
Có m ñiểm phát hàng
1 2

i j
a b
= =
=
∑ ∑
và cước phí vận chuyển một ñơn vị hàng từ trạm phát
i
A
tới trạm thu
j
B
là
ij
c
. Hãy
lập phương án ñiều hàng sao cho yêu cầu thu và phát ñược ñảm bảo và tổng chi phí nhỏ nhất.
Dạng toán học của bài toán:
Gọi
( 1, , 1, )
ij
x i m j n
= =
là số ñơn vị hàng cần vận chuyển theo kế hoạch từ trạm phát
thứ i tới trạm thu thứ j
( 1, , 1, )
i m j n
= =
thì bài toán vận tải có mô hình toán học như sau:

1 1
0, 1, , 1,
ij
x i m j n
≥ = = .
Trong
ñ
ó
0, 1,
i
a i m
≥ =
0, 1,
j
b j n
≥ = ,
1 1
m n
i j
i j
a b
= =
=
∑ ∑

1.2. Bài toán QHTT tổng quát
Tìm véc tơ
(
)

0 3
0 4
n
ij j i
j
n
ij j i
j
j
j
a x b i I
a x b i I
x j J
x j J
=
=

≥ ∈




= ∈



≥ ∈

<=> ∈


2 1
\
J J J
=
,
2 1
J J
ϕ
∩ =
(
0
j
x
<=>

ñượ
c hi
ể
u là
j
x
không ph
ụ
thu
ộ
c d
ấ
u).
Hàm f
ñượ

ộ
c d
ấ
u).
V
ề
m
ặ
t lý thuy
ế
t ta có th
ể
ch
ỉ
xét các bài toán tìm giá tr
ị
nh
ỏ
nh
ấ
t (m
ọ
i bài toán max s
ẽ

ñượ
c
chuy
ể
n v

A a
×
=
là ma trận các hệ số của hệ ràng buộc cơ bản;
•
(
)
1 2
, , ,
j
j j mj
a a a a
=
là véc tơ cột ( ma trận cột) thứ
(
)
1,
j j n
=
của ma trận A;
•
(
)
1 2
, , ,
i i i in
a a a a
=
là véc tơ dòng ( ma trận dòng) thứ
(

t
f c x
Ax b
x
= →
=
≥

Dạng véctơ

1
. min
0
n
j
j
j
f c x
a x b
x
=
= →
=
≥
∑

1.4. Hình ảnh hình học của các tập phương án của bài toán QHTT
Trong
2
R

n
1j
j
1
thoả mãn
∑
=
α=
n
1j
jj
xx

1.5.2. Tập hợp lồi . Tập
n
R
X
⊂
ñược gọi là tập hợp lồi nếu với
Xx,x
21
∈
và
1
0
≤
α
≤

thì

ðịnh lý 1.5. (về sự tồn tại phương án cực biên).
ðể phương án
(
)
n.1j
j
00
xx
=
=
(khác 0) của bài toán qui hoạch tuyến tính dạng chính tắc
với tập phương án






≥=∈=
∑
=
n
1j
j
jn
0x;bxa:RxD
là ph
ươ
ng án c
ự

a ph
ươ
ng án này là
ñộ
c l
ậ
p
tuy
ế
n tính.

ðịnh nghĩa 1.3
. Ph
ươ
ng án c
ự
c biên c
ủ
a bài toán QHTT d
ạ
ng chính t
ắ
c
ñượ
c g
ọ
i là
không suy bi
ế
n n

i là suy bi
ế
n.
1.6.2. Cơ sở của phương án cực biên
Giả sử
(
)
n
1j
0
j
0
xx
=
=
(khác 0) là một phương án cực biên của bài toán QHTT chính tắc và
hạng(A) = m. Ký hiệu J là một bộ gồm ñủ m chỉ số :
(
)
0
xJJ
+
⊃

(
)
{
}
(
)

B
B a j J
= ∈
là một cơ sở của phương án cực biên
x
thì các
Bj
Jj,x
∈
ñược gọi là
các thành phần cơ sở;
Bj
Jj,x
∉
ñược gọi là các thành phần phi cơ sở.
Nhận xét:
1. Số thành phần dương của một phương án cực biên của bài toán QHTT dạng chính tắc tối
ña là bằng m .
2. Số phương án cực biên của một bài toán QHTT là hữu hạn.
3. Phương án cực biên không suy biến chỉ có một cơ sở duy nhất, ñó là các véc tơ tương
ứng thành phần dương của phương án.
4. Phương án cực biên suy biến có nhiều cơ sở khác nhau, phần chung của chúng là các véc
tơ tương ứng với các thành phần dương của phương án.

*) Tài liệu học tập: [1]; [2]; [3]; [5].
*) Câu hỏi, bài tập, nội dung ôn tập và thảo luận 8


, x
3
.
c. Phát biểu và giải bài toán trong trường hợp có 4 ñiểm x
1
, x
2
, x
3
,x
4

3
R
∈
không thẳng
hàng và không ñồng phẳng.
Bài tập 1.2. Cho hình cầu tâm O bán kính a trong R
3

V=
{
}
22
3
2
2
2
1
3


+=
. Hãy
xem xét D có phải tập lồi không? Giải thích tại sao?
Bài tập 1.4. Cho X và Y là hai tập lồi trong R
n
; Z là 1 tập ñược ñịnh nghĩa như sau:
{
}
Yy;Xx;yxz:zZ
∈
∈
+
=
=
. Xét xem Z có phải tập lồi không?
Bài tập 1.5. Chứng minh rằng: Nếu bài toán QHTT có tập phương án khác rỗng và mọi ẩn số
ñều bị chặn
(
)
jHxh
jjj
∀
≤
≤
thì nó luôn luôn có phương án tối ưu.
Bài tập 1.6. Chứng minh rằng bài toán sau luôn có phương án tối ưu:
(
)
maxhayminxcf

thanh thép nguyên ñể vừa ñảm bảo ñủ số lượng các ñoạn thép cần có mà tốn ít thanh thép
nguyên nhất?
Bài tập 1.8. Một ñội sản xuất nông sản có 3 loại ñất dự kiến trồng 4 loại cây với số quỹ ñất và
năng suất dự kiến ñược cho trong bảng sau (Năng suất: tạ/ha)
Cây (ha)

ðất (ha)
Sắn
150
Khoai
200
Lạc
100
ðậu
80
Thịt 100 7 6 4

4
Cát 230 5 5 3 2
Cát pha 200 6 7 3 3 9

Hãy tính xem nên trồng cây gì trên ñất gì ñể ñạt tổng năng suất cao nhất?
a. Viết dạng toán học của bài toán.
b. Hãy chỉ ra một phương án của bài toán.
c. Chứng tỏ bài toán luôn có phương án tối ưu.
d. Hãy tổng quát hoá bài toán.
Bài tập 1.9. Hãy thiết lập bài toán quy hoạch tuyến tính cho bài toán sau:

≥≥
=++
−≤−−
≥++
0x,0x
11x6x3x2
1x2xx
3xx7x4
21
321
321
321

b) f =
1 2 3
5 4 3 min
x x x
− − − →

1 2 3
1 2 3
1 2 3
1 2 3
2 3 5
4 2 11
3 4 2 8
, , 0
x x x
x x x
x x x

x x
− − + ≤


− − ≥


+ + =


≥


Bài tập 1.11. ðưa bài toán sau về dạng chuẩn tắc minxx3xf
321
→
−
+
=















≥
=+
=+++−
=+++−
0x
33x2x3
22xxxx2
11xxx2x
1
42
4321
4321(
)
3,0,1,0x −=

b.
1 4
max
g x x
= + →


không bị chặn trên tập phương án.
minx12xxx3x4x3f
654321
→
+
+
+
+
+
−
=








=≥
=++++−
−=−−+−−
=+++−
6,1j,0x
11x3x5x3x2x
5x3x2xxx
3x9x2xx2
j
65421
65432

21
21
21
xx
xx
xx
xx

b.
max
21
→
+
−
=
xxf






≥≥
≤−
≤+
≥+
0;0

≤+
−≥+−
−≤−−
0;0
1
632
22
21
21
21
21
xx
xx
xx
xxBài tập 1.16. Hãy tìm ñiều kiện của hàm mục tiêu trong bài toán sau ñể thu ñược:
a. Bài toán vô nghiệm.
b. Bài toán vô số nghiệm
21
3xxf
+
=











≥≥
≤+
≥
+
0x,0x
)2(2xmx
)1(3xx
21
21
21
`
Bài tập 1.18. Cho bài toán quy hoạch tuyến tính

maxxx)x(f
21
→
+
=


12CHƯƠNG 2
Phương pháp ñơn hình
Số tiết: 10 (Lý thuyết 9 ; bài tập, thảo luận: 1)

*) Mục tiêu. Cung cấp cho sinh viên những kiến thức cơ bản về cơ sở lý luận của
phương pháp ñơn hình; các thuật toán ñơn hình: Thuật toán gốc, thuật toán hai pha, một số vấn
ñề về bài toán suy biến.
2.1. Cơ sở lý thuyết của phương pháp ñơn hình
2.1.1. Tư tưởng cơ bản của phương pháp ñơn hình
Xét bài toán quy hoạch tuyến tính dạng chính tắc:
min
x
c
f
t
→

x
. Nếu
0
x
chưa phải là phương án tối ưu thì
cải tiến nó ñể chuyển sang một phương án cực biên mới và tốt hơn
01
xx ≠
(
)x(f)x(f
01
≤
).
Sau một số hữu hạn bước hoặc sẽ tìm ñược phương án cực biên tối ưu hoặc sẽ kết luận về tính
không giải ñược của bài toán.
2.1.2. Biểu diễn qua cơ sở. Dấu hiệu tối ưu
Giả sử
(
)
n,1j
j
00
xx
=
=
là ph
ươ
ng án c
ơ
s

B
k
∉

ñề
u có th
ể
khai tri
ể
n duy nh
ấ
t theo c
ơ
s
ở
này B nh
ư
sau:
∑
∈
=
B
Jj
j
jk
k
aza
,
)Jk(
B

(
)
Dxx
n,1j
j
∈
=
=
ta luôn có:

(
)
B
Jk
kjk
j
0
j
Jjxzxx
B
∈−=
∑
∉
;
(
)
(
)
∑
∉

của cơ sở B mà
0
k
≤
∆
)
J
k
(
∈
∀
thì
0
x
là phương án tối ưu của bài toán (I).

13

Chú ý : Bất ñẳng thức
0
k
≤
∆
)
J
k
(
∈
∀
chỉ là ñiều kiện ñủ, trong trường hợp

∃

)Jk(
B
∉
thì
0
x

là phương án tối ưu không duy nhất của bài toán.
2.1.3. Tìm phương án cực biên mới tốt hơn, công thức ñổi cơ sở
2.1.3.1. Dấu hiệu hàm mục tiêu không bị chặn trên tập phương án
ðịnh lý 2.3. Nếu ứng với phương án cực biên
0
x
của cơ sở B tồn tại một chỉ số
k
)Jk(
B
∉
ñể
0
k
>
∆
và
0z
k
≤
thì hàm mục tiêu của bài toán (I) không bị chặn dưới trên tập

=
Bjs
j
0
B
j
1
Jjkhizx
sjkhi
sj,Jjkhi0
x
(2.1)
ở ñó:
(
)
(
)
01
xfxf ≤
;
{
}
1
1
,
j
B
B a j J
= ∈
,

r
0
js
js
j
0
x
x
0z,
z
x
min =










>
(2.3)
ðịnh lý 2.5. Phương án
1
x
ñược xác ñịnh theo công thức (2.1) là phương án cơ sở của
1
B

khảo sát vai trò của phương án
1
x
ñối với bài toán ta sẽ tính
k
1
∆
và
jk
1
z
. Ta có công thức ñổi cơ
sở như sau:







≠∈−
=
=
rj,Jjkhiz
z
z
z
sjkhi
z
z

jk
z
và các ước lượng
k
∆
.
Bước 2. Kiểm tra dấu hiệu tối ưu:
• Nếu
k
∆
B
Jk0
∉
∀
≤
thì
0
x
là phương án tối ưu. Thuật toán kết thúc.
• Nếu
Bk
Jk,0
∉
>
∆
∃
thì chuyển sang bước 3.
Bước 3. Kiểm tra dấu hiệu hàm mục tiêu giảm vô hạn, cải tiến phương án.
Với mỗi
B

∉
mà
k
∆
> 0 ñều tồn tại ít nhất một hệ số
0z
jk
>
thì chuyển sang cơ
sở mới
{
}
1
1
,
j
B
B a j J
= ∈
,
{
}
{
}
1
\ , ;
B B B B
J J r s s J r J
= ∪ ∉ ∈
với phương án cực biên

,
trong trường hợp này khi chuyển sang phương án cơ sở chấp nhận ñược tiếp theo giá trị hàm
mục tiêu sẽ không thay ñổi. Hơn nữa, tình huống trên có thể lặp lại nhiều lần và tình huống xấu
hơn nữa là sau một số lần như vậy thuật toán lại quay trở về với một cơ sở trước ñó ñã xét qua.
Khi ñó nếu vẫn giữ nguyên cách chọn dòng xoay, cột xoay thì chu trình này sẽ lặp lại vô hạn lần.
Hiện tượng nói trên ñược gọi là hiện tượng xoay vòng. Một trong những hướng khắc phục hiện
tượng này là sử dụng các cách chọn dòng xoay, cột xoay sao cho trong quá trình thực hiện thuật
toán không có cơ sở nào bị lặp lại.
2.2.3. Bảng ñơn hình
2.2.3.1. Lập bảng ñơn hình xuất phát

15

Không giảm tổng quát, ta giả thiết rằng ñã biết cơ sở xuất phát
{
}
,
j
B
B a j J
= ∈
,
{
}
(
)
m, ,2,1J
B
=


= =

Ta kí hiệu
1
H B A
−
=
thì ma trận H có dạng sau:
(
)
1 1 1 1
, ,
n
H B A B a B a
− − −
= =

(
)
n
1j
j
z
=
=
. Các dữ kiện về phương án, các ước lượng
k
∆
của các
véc tơ

n
c

j
c

( )
B
j J
∈

Cơ
sở
Phương
án
1
z

2
zm
z

1m
z
+
zs1
zn1
z2
c

2
a

0
2
x

0 1 0
1m2
z
+k2
z


js
zjn
z
r
c

r
a

0
r
x

0 0 0
1mr
z
+kr
zsr
mn
z
k
∆

1
∆

2
∆m
∆

1m
+
∆k
∆s

j
c
( )
B
j J
∈
: thay
r
c
bằng
s
c
.
 Chia các phần tử của hàng xoay (hàng r của bảng 1) cho phần tử xoay
sr
z
ta ñược hàng s
của bảng mới ( hàng này ñược gọi là hàng chuẩn).
 Mỗi phần tử khác ngoài hàng xoay trừ ñi tích của phần tử cùng hàng với nó trên cột xoay
với phần tử cùng cột với nó trên hàng chuẩn ñược phần tử cùng vị trí trong bảng ñơn hình mới.
Chú ý khi thực hiện thuật toán:

16

 Có thể ñưa bất kỳ véc tơ nào ứng với
0
k
>
∆
vào cơ sở cũng ñều cải tiến ñược phương án.

gốc chưa ñầy ñủ (về tính tương thích của hệ ràng buộc, hạng của ma trân A, sự tồn tại phương án
cực biên của bài toán (I))
Nội dung thuật toán:
Xây dựng và giải bài toán phụ của bài toán (I):
minxe
u
t
→
;
0x,0x,bxAx
uu
≥
≥
=
+
(II)
Trong ñó:

(
)
mn2n1nu
x, ,x,xx
+++
=
(viết gọn:
(
)
,Jxx
uu
=

j
u
B a j J
= ∈
với phương án cơ sở chấp nhận
ñược
(
)
(
)
b,0x,x
u
=
.
Quá trình giải bài toán (II) gọi là pha thứ nhất trong phương pháp hai pha. Kết thúc pha thứ
nhất ta sẽ xây dựng ñược phương án cơ sở chấp nhận ñược tối ưu
)x,x(
*
u
*
của cơ sở
{
}
*
*
,
j
B
B a j J
= ∈

*
. Khi ñó
*
x
là phương án cơ sở chấp nhận ñược của bài toán (I).
Từ cơ sở này ta tiến hành thuật toán ñơn hình 2 giải bài toán (I) (pha thứ 2).
Tình huống 2
{
}
*
*
,
j
B
B a j J
= ∈
,
φ
≠
∩
u
B
JJ
*
. Kí hiệu
u
B
*i
JJi,x
*

j
a
và tìm ñược cơ sở
{
}
{
}
* *
1
* *
\
i j
B B a a
= ∪
, tiếp tục pha thứ hai giải bài toán.
Nếu
0z
ji
*
=

*
B
J\Jj
∈
∀
thì ràng buộc tương ứng với nó trong hệ phương trình tuyến tính
Ax = b là hệ quả của các phương trình còn lại khi ñó ta xoá véc tơ
*
i

∑
=
+
; (III)

mn,1j,0x
j
+=≥
.

Trong ñó ký hiệu M ñể chỉ một số dương vô cùng lớn, lớn hơn bất cứ số cụ thể nào mà ta
cần phải so sánh với nó, các biến
m,1i,x
in
=
+
gọi là các biến giả, kí hiệu
u
x
là véc tơ các biến
giả. áp dụng thuật toán ñơn hình ñối với bài toán (III) bắt ñầu từ phương án cơ sở chấp nhận ñược:
(
)
m,1i,bx;n,1j,0x
iinj
====
+
cơ sở tương ứng là ma trận ñơn vị cấp m.
Khi tính các ước lượng
j

β
còn
j
α
là tuỳ ý, hoặc là
0=
j
β
và
0>
j
α
.
•
qp
∆
>
∆
nếu hoặc là
qp
β
>
β
còn
qp
,
α
α
là tuỳ ý, hoặc là
qp

với
0x
*
u
≠
. Khi ñó bài toán xuất phát không có
phương án chấp nhận ñược nên vô nghiệm.
• Nếu bài toán (III) không có phương án tối ưu thì bài toán (I) cũng không có phương án tối ưu.
2.5. Vấn ñề bài toán suy biến
- Bài toán có phương án cực biên xuất phát là suy biến (số thành phần dương của phương án ít
hơn số véc tơ trong cơ sở của phương án cực biên) (xem thêm 2.2.2.2.)
*) Tài liệu học tập: [1]; [2]; [3]; [6].
*) Câu hỏi, bài tập, nội dung ôn tập và thảo luận:

18Bài tập 2.1. Giả sử
x
là một ñiểm của tập
{
}
m,1i,bxa:RxX
ii
n
=≥∈=
(trong ñó
i
a
là ma trận

3,1j,0x
t730x4x
t260x2x3
t40xx2x
j
21
31
321

Tìm ñiều kiện cần và ñủ về tham số t ñể bài toán ñã cho có tập phương án khác rỗng.
Bài tập 2.3. Giải các bài toán sau bằng phương pháp ñơn hình:
a)
minx5x6x4f
651
→
−
−
=










=≥
=++

→
−
−
−
−
−
−
=








=≥
=++
=+++
=+++
6,1j,0x
21xxx3
38xx3x2x4
46xx3x4x2
j
631
5321
4321

Chứng minh tính không duy nhất của phương án tối ưu và tìm

Bài tập 2.4. Cho bài toán:

maxx5x7xx3f
4321
→
−
−
−
=19








=≥
≥−−+
−=++−−
≤+−+
4,1j,0x
25xxx3x2
5x3xxx
37xx3x2x
j
4321







=≥
−=+−+−+−
−=−++−+−
=+−−+−
6,1j,0x
15xxx2xx4x2
45x2x5x21x9x6x4
14xx2x7x3xx
j
654321
654321
654321

và phương án cực biên
(
)
16,7,0,0,0,12x
0
=
.
a. Biết
0c
1
=

5,1j,0x
4x1tx
14x2xt1x8x2
9x4tx2x12xx
j
41
5431
54321

a. Biết rằng
0
x
là một phương án cực biên ứng với cơ sở
(
)
1 2 5
, ,
a a a
. Hãy lập bảng ñơn
hình ứng với
0
x
. Tìm t ñể
0
x
là phương án tối ưu.
b. Giải bài toán khi t =1 và t=3.

Bài tập 2.7. Giải và biện luận bài toán sau theo tham số m:
minxmxx2f

→
−
+
−
=20








=≥
=+−
=+−−
=−−
4,1j,0x
52x2xx2
20xxxx
15xx2x
j
431
4321
321

b)

xxxx
j

c)
minxx3xx2f
4321
→
+
+
−
=








=≥
−=−+−
=+−+
=++−
4,1j,0x
2xx2x2x
10x2xxx
8xxxx2
j
4321
4321

4321

Bài tập 2.9. Giải các bài toán sau ñây bằng phương pháp thuật toán M.

a)
minxx2xf
421
→
−
−
=








=≥
=+−+
=−−+
=+−
4,1j,0x
48x2x2x2x
60xx3xx2
24xxx
j
4321
4321

4321
→
+
−
+
=








=≥
−=−+−
=++−
=+++
4,1j,0x
36xxxx2
20xxxx
24xxxx
j
4321
4321
4321

d)
min432
4321

Bài tập 2.10. Cho bài toán:

(
)
(
)
minx3xt2xt1x6x3x8f
654321
→
−
+
−
−
+
−
−
−
−
−
=










22CHƯƠNG 3
Các bài toán ñối ngẫu
Số tiết: 7 (Lý thuyết 6; bài tập, thảo luận: 1)

*) Mục tiêu. Cung cấp cho sinh viên những kiến thức cơ bản về lý thuyết ñối ngẫu,
nguyên tắc thiết lập bài toán ñối ngẫu, các ñịnh lý ñối ngẫu và ứng dụng, thuật toán ñơn hình ñối
ngẫu.

bAx
minxcf
t
≥
=
→=maxybg
t
→=

cyA
t
≤

y <=> 0 3.1.1.3. Bài toán ñối ngẫucủa bài toán QHTT dạng tổng quát
Bài toán gốc (P) Tập chỉ số Bài toán ñối ngẫu (Q)
min
x
c
f
t
→
=
J
j
∈

j
jt
cay ≤

0
<=>
j
x

Jj
′
∈

j
jt
cay =Trong ñó: (
{
}
m, 2,1MII
=
=
′
∪

3.2.1. Quan hệ giữa cặp bài toán ñối ngẫu
ðịnh lý 3.1. Giả sử
{
}
y,x
tương ứng là cặp phương án chấp nhận ñược của bài toán gốc
và ñối ngẫu, khi ñó ta có:
ybxc
tt
≥
.
Hệ quả. Giả sử
{
}
**
y,x
tương ứng là cặp phương án chấp nhận ñược của bài toán gốc và
ñối ngẫu ñồng thời thoả mãn
*t*t
ybxc =
. Khi ñó
{
}
**
y,x
là cặp phương án tối ưu của bài toán
gốc và ñối ngẫu.
3.2.2. ðịnh lý ñối ngẫu
ðịnh lý 3.2 (ñịnh lý ñối ngẫu) Nếu bài toán gốc (P) có phương án tối ưu thì bài toán ñối
ngẫu (Q) của nó cũng có phương án tối ưu và giá trị tối ưu của chúng bằng nhau.






−
∑
=
;
j,0xyac
j
m
1i
iijj
∀=








−
∑
=
.
3.3. Phương pháp ñơn hình ñối ngẫu
3.3.1. Cơ sở chấp nhận ñược ñối ngẫu
3.3.1.1. Cơ sở chấp nhận ñược gốc

y B c
−
=
). Cơ sở B
ñược gọi là cơ sở chấp nhận ñược ñối ngẫu nếu phương án cơ sở ñối ngẫu ứng với nó là phương
án chấp nhận ñược của bài toán ñối ngẫu.
3.3.1.3. Giả phương án
ðịnh nghĩa 3.3. Phương án
(
)
(
)
(
)
1
, 0
j J j
j J j J
B B
x x x B b x
−
∈ ∉
= = = =
với B là cơ sở
ñối ngẫu ñược gọi là giả phương án của bài toán gốc ứng với cơ sở B;
Bj
Jj,x
∈
ñược gọi là
thành phần cơ sở của giả phương án,

x
của
cột giả phương án ñều không âm, thuật toán kết thúc. Nếu ngược lại thì chuyển sang bước 2.
Bước 2. Kiểm tra tính tương thích của bài toán gốc, cải tiến phương án.
• Nếu
B
Jj
∈
∃
sao cho
0x
j
<
mà
n,1k0z
jk
=∀≥
thì bài toán gốc (P) không có phương án
và sẽ không có phương án tối ưu.
• Nếu
B
Jj
∈
∀
ở ñó
0x
j
<
ñều tìm ñược ít nhất một phần tử
0z

s
a
ñược ñưa vào cơ sở khi










<
∆
=
∆
=θ 0z,
z
min
z
rj
rj
j
rs
s
(
n,1j =∀
). (Dòng r ñược
gọi là dòng xoay, cột s ñược gọi là cột xoay,

+
+

Trong ủú
(
)
n2m1m
x, ,x,x
++
l vộc t cỏc bin phi c s cũn M l mt s dng ln hn
bt k s c th no cn so sỏnh vi nú. Bi toỏn thu ủc s ủc gi l bi toỏn m rng. i
vi bi toỏn ny ta cú ngay mt c s
(
)
0 1 2
, , , ,
m
B a a a a
=
. Xõy dng bng ủn hỡnh tng ng
vi c s
B
ging nh trng hp cú sn c s ủn v. Kt thỳc thut toỏn ta cú th gp mt
trong cỏc tỡnh hung sau:
Bi toỏn m rng vụ nghim khi ủú bi toỏn ban ủu cng vụ nghim.
Bi toỏn m rng cú phng ỏn ti u
(
)
*
n

x, ,x,x
v
0
x
l mt bin phi c s, khi ủú
cỏc bin c s s ph thuc M. Cú hai kh nng sau:
Mt l: Giỏ tr hm mc tiờu ca bi toỏn m rng ph thuc M, khi ủú
(
)
+



MkhixF
suy ra bi toỏn ban ủu khụng cú phng ỏn ti u.
Hai l: Giỏ tr ti u ca bi toỏn m rng khụng ph thuc M, khi ủú bi toỏn ban ủu
cú phng ỏn ti u m ta cú th thu ủc t phng ỏn ti u ca bi toỏn m rng bng cỏch
loi b
0
x
v gim dn giỏ tr ca M cho ủn khi trit tiờu giỏ tr ca mt bin c s no ủú
trong bi toỏn m rng.
Chỳ ý khi thc hin thut toỏn:
V nguyờn tc, cú th loi khi c s bt k vộc t no ng vi
0x
j
<
cng ci tin ủc
phng ỏn ca bi toỏn ủi ngu.
i vi bi toỏn cú hm mc tiờu dn ủn max cú th gii trc tip vi du hiu c s

3.4. Tìm nghiệm của một cặp bài toán đối ngẫu bằng giải hệ phơng trình tuyến tính
T cỏc tớnh cht ca cp bi toỏn ủi ngu,vic gii bi toỏn gc ủi ngu cú th ủa v
vic gii h phng trỡnh v bt phng trỡnh sau ủõy :

; 0
; 0
AX b X
YA C Y
CX Yb






=
*) Ti liu hc tp: [3]; [1];[2].
*) Cõu hi, bi tp, ni dung ụn tp v tho lun