BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HỒ CHÍ MINH
……………….o0o……………….
QUY HOẠCH TUYẾN TÍNH
Khoa: Khoa Học Cơ Bản
Lớp: 211301219
GVHD: Nguyễn Ngọc Chương
TP.HCM 11/2014
1
TIỂU LUẬN
BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP.HỒ CHÍ MINH
……………….o0o……………….
QUY HOẠCH TUYẾN TÍNH

Khoa: Khoa Học Cơ Bản
Lớp: 211301219
GVHD: Nguyễn Ngọc Chương
Danh Sách Nhóm
Võ Ngân Hà 13008641
Nguyễn Mạnh Khương 13010131
Lê Thị Kim Luyến 13022461
Nguyễn Thị Tuyết Nhung 13015781
Trần Thị Thanh Trang 13037681
Đoàn Thị Trinh 13022461
2
TIỂU LUẬN
LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Trong thực tế ta thường hay gặp các tình huống là phải lựa chọn một trong số những
quyết định quan trọng để đưa ra những phương án hoặc chiến lược tốt nhất trong sản

 Khi phân tích đồng thời cả hai bài toán gốc và dối ngẫu ta có thể rút ra các kết luận
sâu sắc cả về mặt toán học lẫn về ý nghĩa thực tiễn.
1. CÁCH LẬP BÀI TOÁN ĐỐI NGẪU
1.1. Xét quy hoạch tuyến tính dạng chuẩn tắc:
f(x) = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
min



=≥
=≥+++
,n, ,2,1j,0x
m ,,2,1i,bxa xaxa
j
inin22i11i
(P) [Bài toán gốc]
Trong đó a
ij
, b

=≥
=≤+++
,n,,2,1i,0y
,n,,2,1j,cyayaya
jmmj2j21j1



(Q) [Bài toán đối ngẫu]
Ở đây y = (y
1
, y
2
, … ,y
m
)∈ R
m
là vectơ biến cần tìm.
 Nhận xét:
- Các ràng buộc chính của (P) ↔ các biến của (Q). Các biến của (P) ↔ các ràng buộc
chính của (Q).
- Các hệ số vế phải ràng buộc chính của (P) trở thành các hệ số mục tiêu của (Q), còn
các hệ số mục tiêu của (P) lại trở thành các hệ số vế phải ràng buộc chính của (Q).
- Bài toán gốc tìm min thì bài toán đối ngẫu tìm max (và ngược lại).
- Cả hai bài toán (P) và(Q) đều có dạng chuẩn.
 Ví dụ: tìm bài toán đối ngẫu của bài toán QHTT dạng chuẩn.
f(x) = 20x
1
+ 15x
2

3
→ max





≥≥≥
≤++
≤++
0;0;0
15
203
321
321
321
yyy
yyy
yyy
 Dùng ký hiệu vectơ và ma trận, ta có thể viết:
Bài toán gốc: Bài toán đối ngẫu:





≥
≥
→=
0

==+++
→+++=
,,,2,1,0
,,,2,1,
min)(
2211
2211
njx
mibxaxaxa
xcxcxcxf
j
ininii
nn



Là bài toán:



=≤+++
→+++=
,,,2,1,
max)(
2211
2211
njcyayaya
ybybybyg
jmmjjj
m









∈≤∈∈≥
∈
∈
∈










≤
=
≥
+++
→+++=
)(0),(),(0
,
,

∩I
k
= ∅, i, k = 1, 2, 3 (i≠k); J
1
∪J
2
∪J
3
= {1,…,n},
J
i
∩J
k
= ∅, j, k = 1, 2, 3(j≠k).
Ta gọi đối ngẫu của bài toán trên là bài toán:









∈≤∈∈≥
∈
∈
∈



iii
j
j
j
mmjjj
mm


SƠ ĐỒ ĐỐI NGẪU TỔNG QUÁT
Bài toán gốc Bài toán đối ngẫu
Các biến gốc: x
1
, x
2
,…, x
n
Các biến đối ngẫu: y
1
, y
2
,…,y
m
Hàm mục tiêu
f(x) = c
1
x
1
+ c
2
x

n










≤
=
≥

3
2
1
,
,
Iib
Iib
Iib
i
i
i
∈
∈
∈
y









≤
≥
0
0
ýtùydâu

3
2
1
Jj
Jj
Jj
∈
∈
∈
a
1j
y
1
+a
2j
y









≤≥
≤−+
=+−−
≥−+
→+−=
ýtùyxxx
xxx
xxx
xxx
xxxxf
321
321
321
321
321
,0,0
343
642
832
min234)(
Bài toán đối ngẫu là:



≥
≥
→=
0
min,)(
x
bAx
xcxf
(Q)







≥
≤
→=
0
max,)(
y
cyA
ybyg
T
Để tiện nghiên cứu lý thuyế đối ngẫu, ta xét cặp bài toán đối ngẫu (P) và (Q) cho ở
dạng chuẩn. Tuy nhiên các kết quả nhận được cũng đúng cho một cặp bài toán đối ngẫu
bất kỳ.
 Định lý 1: (Đối ngẫu yếu).

bài toán đối ngẫu không có bất kỳ mộ phương án nào.
- Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trong miền ràng buộc của nó
thì bài toán gốc không có bất kỳ một phương án nào.
- Nếu x* là 1 phương án của bài toán gốc, y* là 1 phương án của bài toán đối ngẫu và f(x*)
= g(y*) thì x* là phương án tối ưu của bài toán gốc và y* là phương án tối ưu của bài toán
đối ngẫu.
 Định lý 2: (Đối ngẫu mạnh).
Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của nó cũng có
phương án tối ưu và giá trị tối ưu của chúng là bằng nhau.
 Định lý 3: (Định lý tồn tại).
Đối với mỗi cặp quy hoạch đối ngẫu nhau thì có thể xảy ra một trong ba khả năng
loại trừ nhau sau đây.
- Cả hai bài toán đều không có phương án.
- Cả hai bài toán đều có phương án. Khi đó, cả hai bài toán đều có phương án tối ưu và giá
trị tối ưu của các hàm mục tiêu là bằng nhau.
- Một bài toán có phương án và bài toán kia không có phương án. Khi đó, bài toán có
phương án sẽ không có phương án tối ưu và hàm mục tiêu của nó không giới nội trong
miền ràng buộc.
 Định lý 4: (Định lý về độ lệch bù).
Một cặp phương án x, y của hai bài toán (P), (Q) là những phương án tối ưu khi và
chỉ khi chúng nghiệm đúng các hệ thức:

)1(,m,,2,1i,0bxay
n
1j
ijiji
=∀=









−
∑
=
n
j
ijij
bxa
1
: độ lệch ở ràng buộc I của (P).






−
∑
=
m
i
iijj
yac
1
: độ lệch ở ràng buộc j của(Q).
Ghi chú:

jij
xa
1
=b
i
Hệ thức (2) cũng có nghĩa tương tự:
∑
=
m
i
iij
ya
1
< c
j

⇒
x
j
= 0
Và x
j
> 0
⇒

∑
=
m
i
iij

852
35
13
min)(
5321
4321
321
54321
jx
xxxx
xxxx
xxx
xxxxxxf
j
Có phương án tối ưu x* = (0, 1, 0, 2, 3) với f
min
= 6. Hãy tìm phương án tối ưu của
bài toán đối ngẫu tương ứng.
Giải
Bài toán đối ngẫu của bài toán gốc là:
















=
=
=++
1
1
15
3
2
321
y
y
yyy
Giải hệ phương trình ta có:





=
=
−=
1
1
5
3

min322)(
6543
642
6541
65421
jx
xxxx
xxx
xxxx
xxxxxxf
j
Xuất phát từ phương án cực biên ban đầu x
0
=(2, 12, 9, 0, 0, 0), cơ sở tương ứng {A
1
,
A
2
, A
3
). Quá trình giải được ghi lại trong bảng đơn hình dưới đây.
Cơ
Sở
Hệ số
c
j
Phươn
g
án
A

Bảng 3 -17 -4/5 0 -3/5 0 -21/5 0
Để tìm lời giải (phương án tối ưu) của bài toán đối ngẫu ta áp dụng qui tắc sau:
Qui tắc
Nếu cơ sở ban đầu của (P) là cơ sở chính tắc (các vecto đơn vị), giả sử là {A
j
, j∈J}.
Để tìm lời giải của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình cuối cùng của (P)
các ∆
j
(j∈J) rồi cộng với hệ số c
j
tương ứng.
Vì thế, lời giải của bài toán đối ngẫu y* = (y*
1
, y*
2
, y*
3
) được xác định như sau:







−
=+
−
=+∆=

max
= -17 = f
min
B. BÀI TẬP
1. Viết bài toán đối ngẫu của các qui hoạch tuyến tính sau:
a. f = 2x
1
+ 3x
2
- 4x
3
+ 5x
4+
→
min
Điều kiện







≥≤≥
≤+−−
=−++−
≥+−+
.0x,0x,0x,ýtùyx
,9xx2xx
,8xxx2x

,52
,422
,32
,2
231
321
321
321
321
ýtùyyyy
yyy
yyy
yyy
yyy
b. f = x
1
- 4x
2
- 3x
3
- 2x
4
→
min
Điều kiện













≤≥
−≥+−
−≤−+
−=−+−
≤−+
.0,0,
,23
,33
,452
,12
321
321
321
321
321
yyýtùyy
yyy
yyy
yyy
yyy
1. Xét qui hoạch tuyến tính:






≥≥≥
−≥+−
−≥−
−≥+−
→++=
0y,0y,0y
1yy
1yy
1yy
minyyyg
321
21
31
32
321
/
Bài toán đối ngẫu của bài toán gốc f(x) là:









≥≥≥

−≥+−
−≥+
−≥+−
→++=
.0y,0y,0y
,1yy
,1yy
,1yy
min,yyyg
321
21
31
32
321
/
Bài toán tương đương của bài toán đối ngẫu trùng với bài toán gốc.
⇒ bài toán tự đối ngẫu.
⇒ điều phải chứng minh.
2. Cho bài toán qui hoạch tuyến tính:







=≥
=++
=++
→+−=

≤
−≤+
≤
→+=
ýtùyyy
yy
y
yy
y
yyg
21
21
2
21
1
21
,
.054
,2
,22
,1
max,86
Gọi y
*
= (y
1
, y
2
) là phương án tối ưu của bài toán đối ngẫu.
Do x

) = -6 = f
min
3. Xét qui hoạch tuyến tính:
,
.0,0
,743
,2
,33
min1915
21
21
21
21
21









≥≥
≥+
≥+
≥+
→+=
xx
xx

b. Ta giải bài toán đối ngẫu:
Thêm vào hai ẩn phụ
0,0
54
≥≥ yy
vào ràng buộc thứ nhất và thứ hai. Lập bảng đơn
hình, ta có:
Cơ
sở
Hệ
số
Phương
án
A
1
A
2
A
3
A
4
A
5
θ
3 2 7 0 0
A
4
0 15 3 1 3 1 0 5
A
5

, x
2
) là phương án tối ưu của bài toán gốc.
Do y
2
*
, y
3
*
>0, nên theo định lí về độ lệch bù, x
*
là nghiệm đúng hệ phương trình:



=+
=+
743
2
21
21
xx
xx
Giải hệ phương trình, ta được: x
*
= (1, 1)
Với f
min
= g
max

,6x3x
3x3x4x2
,4xx
,2x4x3x
321
31
21
321
32
321
(*)
Viết bài toán đối ngẫu. Chứng tỏ x
0
= (-1, 1, 1) là phương án tối ưu. Xác định
một phương án tối ưu của bài toán đối ngẫu.
Giải
Bài toán đối ngẫu của bài toán gốc:
g(y) = -2y
1
+ 4y
2
- 3y
3
- 6y
4
+ 3y
5
→ max







=+
−≥−=−−
−=+−−
≤=−
−=−+−
.321
,6431
,3342
,4011
,2431
x
0
= (-1, 1, 1) thỏa (*) ⇒ x
0
là phương án của bài toán gốc.
Gọi y
0
= (y
1
, y
2
, y
3
, y
4
, y

0
= (1, 0, 1, 0, -1).
Với: f(x) = g(x) = -8.
⇒ x
0
= (-1, 1, 1) là phương án tối ưu của bài toán gốc.
⇒ y
0
= (1, 0, 1, 0, -1) là phương án tối ưu của bài toán đối ngẫu.
5. Xét qui hoạch tuyến tính:









=≥
≥−+
−≥−++−−
=−++−
→+−+−=
.5,3,1,0
,843
,4232
,6232
min,2)(
531

Do độ lệch ràng buộc 2 khác 0 và x
1
0
, x
2
0
, x
3
0
, x
4
0
khác 0 nên theo định lí về độ lệch
bù vectơ x
0
= (5, -6, 1, -4, 0) là phương án tối ưu của bài toán gốc khi tồn tại vectơ
y
0
= (y
1
, y
2
, y
3
) ∈ R
3
sao cho:




yy
yyy
Hệ này vô nghiệm
⇒ không tồn tại y
0
∈ R
3
thoả hệ trên.
⇒ phương án x
0
= (5, -6, 1, -4, 0) không phải là phương án tối ưu của bài toán gốc.
b. Bài toán đối ngẫu của bài toán gốc:











≥≥
≤−−−
−=+
≤++
−=−−
≤+−
→+−=









≥
−
≥
−
≤
≤
=
−
=
.0
,
28
5
,
21
4
,4
,
7
8
,
7

=++−−−
−≥−−++−
≥++−+
→−−++−=
.3,2,1,0
,2322
,95242
,5345
min,2081694)(
54321
54321
54321
54321
jx
xxxxx
xxxxx
xxxxx
xxxxxxf
j
(*)
a. Kiểm tra tính tối ưu của phương án x
0
= (2, 0, 1, -2, 3).
b. Phát biểu bài toán đối ngẫu của bài toán trên.
c. Tìm phương án tối ưu của bài toán đối ngẫu.
Giải
a. Thế x
0
= (2, 0, 1, -2, 3) vào hệ ràng buộc (*), ta có:


, y
2
, y
3
) ∈ R
3
sao cho:











≥=
−=+−
−=+−
=−+−
≤−+
−=−−
.0,0
,2035
,8223
,164
,9224
,45






≥≥
−=+−
−=+−
≤−+−
≤−+
−≤−−
→+−=
.0,0
,2035
,8223
,164
,9224
,45
max,295)(
21
321
321
321
321
321
321
yy
yyy
yyy
yyy









=+−−−
=+−−−
=−+−−
=−+−
=−−−−
=++−−−−
=−−++−−−
=++−+−
03520
02238
0416
02249
054
03222
052429
03455
5321
4321
3321
2321
1321
354321

=
0
4
0
2035
822
04
0
3
2
1
32
32
32
1
y
y
y
yy
yy
yy
y
Vậy phương án tối ưu của bài toán đối ngẫu là y
0
= (0, 4, 0).
Với g
max
= f
min
= -36.

a. Phát biểu bài toán đối ngẫu của bài toán trên.
b. Hãy giải một trong hai bài toán rồi suy ra phương án tối ưu của bài toán còn lại.
Giải
a. Bài toán đối ngẫu của bài toán gốc:











≥≥
≥+
≥−+
≥++−
≥
→++=
.0,0
,33
,124
,1112
,2
min,20816)(
32
32
321

A
5
A
6
θ
2 1 1 3 0 0
A
1
2 16 1 -2 1 0 0 0
A
5
0 8 0 [1] 4 1 1 0 8
A
6
0 20 0 1 -2 3 0 1 20
Bảng 1 32 0 -5 1 -3 0 0
A
1
2 32 1 0 9 2 2 0
A
2
1 8 0 1 4 1 1 0
A
6
0 12 0 0 -6 2 -1 1
Bảng 2 72 0 0 21 2 5 0
⇒ Phương án tối ưu của bài toán gốc là x
0
= (32, 8, 0, 0).
Gọi y

min
= f
max
= 72.