BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HỒ CHÍ MINH
 
KHOA KHOA HỌC CƠ BẢN

BỘ MÔN QUY HOẠCH TUYẾN TÍNH
Viện Công nghệ Sinh học – Thực phẩm
Lớp : 211301202
GVHD : TS. Võ Văn Tuấn Dũng
TP. HCM, ngày 25 tháng 4 năm 2009
BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HỒ CHÍ MINH
 
KHOA KHOA HỌC CƠ BẢN

BỘ MÔN QUY HOẠCH TUYẾN TÍNH
Viện Công nghệ Sinh học – Thực phẩm
Lớp : 211301202
GVHD : TS. Võ Văn Tuấn Dũng
1. Nguyễn Trung Nhân : 0771637
2. Mai Hạnh Nguyên : 0770613
3. Huỳnh Thành Trung : 0771757
4. Hồ Thị Thanh Hiếu : 0771725
5. Dương Thị Hà Như : 0771496
6. Cao Thị Ngọc Tuyền : 0770834
7. Mai Nguyễn Thục Hiền : 0770770
8. Vũ Kim Hường : 0771102
TP. HCM, ngày 25 tháng 4 năm 2009
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ố

1. ĐỊNH NGHĨA
Bài toán quy hoạch tuyến tính (qhtt) tổng quát có dạng:
Tìm x
j
, j=1,2,…,n sao cho: f=
min
1
→
∑
=
j
n
j
j
xc
(max) (1)
Với hệ ràng buộc:
i
n
j
jij
bxa









(3) được gọi là các ràng buộc dấu (của biến), nó có thể không âm (≥0),
không dương (≤0) hay tùy ý.
Như vậy, bài toán QHTT là bài toán có các biểu thức xác định hàm mục tiêu
và các ràng buộc chung đều ở dạng tuyến tính.
Véctơ x=(x
1
, x
2
,…,x
n
)
T
được gọi là phương án (pa) hay lời giải chấp nhận
được của bài toán QHTT nếu nó thỏa mãn hệ ràng buộc của bài toán.
Phương án x*=(
T
n
xxx ),...,,
**
2
*
1
được gọi là phương án tối ưu (patư) hay lời
giải tối ưu, nghiệm tối ưu của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt
nhất.
Tức là: f(x*)=
j
n
j
jj

Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nếu có).
Hai bài toán QHTT được gọi là tương đương với nhau nếu chúng có chung
tập hợp các phương án tối ưu.
Mệnh đề: (Quan hệ giữa bài toán cực đại và bài toán cực tiểu)
f (x) max g(x) f (x) min
(1) (2)
x X x X
→ = − →
 
⇔
 
∈ ∈
 
(Trong đó: X là tập hợp các phương án)
Tức là: nếu đổi dấu hàm mục tiêu và đổi loại hàm mục tiêu thì ta được bài
toán tương đương. Vì lí do này mà khi nghiên cứu cách giải bài toán qhtt, người ta
chỉ xét bài toán có loại hàm mục tiêu là cực tiểu (hay chỉ xét bài toán có loại hàm
mục tiêu là cực đại)
2. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QUI HOẠCH
TUYẾN TÍNH 2 BIẾN
Bài toán có dạng: tìm x=(x
1
,x
2
)
T
sao cho f(x)=c
1
x
1

≥b
i
; i=l, 2..., m
2.1. Xác định miền phương án
Đưa các điểm (x
1
,x
2
) lên hệ trục tọa độ vuông góc. Ta xác định được các điểm
thỏa mãn phương trình: a
i1
x
1
+a
i2
x
2
=b, hình thành nên một đường thẳng chia mặt
phẳng tọa độ thành 2 nửa mặt phẳng (mp). Một nửa mp bao gồm các điểm (x
1
, x
2
)
thỏa mãn bất phương trình: a
i1
x
1
+a
i2
x

. Ta thường lấy một điểm đặc biệt như (0,0); (0,1); (1,0);… thay vào bất
phương tình, nếu nó thỏa mãn thì nửa mp chứa điểm đặc biệt đó là nửa mp phải tìm;
còn nếu nó không thỏa mãn thì nửa mp phải tìm là nửa mp không chứa điểm đặc biệt
đó.
Các điểm thỏa mãn hệ ràng buộc của bài toán là các điểm thuộc miền giao của
các nửa mp xác định các bất phương trình tương ứng, nó tạo nên một hình đa giác lồi
có thể bị giới nội hay không bị giới nội; hoặc miền giao là rỗng ứng với trường hợp
hệ ràng buộc không tương thích. Trường hợp miễn phương án X không rỗng ta thực
hiện tiếp bước sau.
2.2. Xác định phương án tối ưu
Một điểm x=(x
1
,x
2
)
T
bất kỳ nằm trong mp tọa độ sẽ cho ta giá trị hàm mục tiêu
là: c
1
x
1
+c
2
x
2
=f.
Tập hợp tất cả các điểm có cùng giá trị hàm mục tiêu là f hình thành nên một
đường thẳng vuông góc với véctơ
OC
với C=(c

i
n
j
jij
bxa =
∑
=1
, i=1,2,…,m
x≥0, j=1,2,…,n
 Trường hợp ràng buộc chung có dấu bất đẳng thức ≤ (hay ≥) thì ta cộng
thêm (hay trừ đi) một biến phụ (biến bù) vào vế trái để cân bằng. Biến phụ phải ≥ 0
và hệ số tương ứng trong hàm mục tiêu phải bằng 0.
 Trường hợp biến có điều kiện ≤ 0 (hay tùy ý) thì ta thay biến đó bằng
“đối” của biến không âm (hay bằng hiệu của biến không âm)
Kết luận: Mọi bài toán qhtt đều đưa được về dạng chính tắc và việc giải bài
toán qhtt đã cho tương đương với việc giải bài toán qhtt dạng chính tắc tương ứng với
nó, theo nghĩa là nếu bài toán dạng chính tắc có patư thì từ đó suy ra được patư của
bài toán ban đầu, còn nếu bài toán dạng chính tắc không có phương án tối ưu thì bài
toán ban đầu cũng không có patư. Nói cách khác: Bài toán ban đầu có patư khi và
chỉ khi bài toán dạng chính tắc tương ứng với nó có patư.
 Như vậy ta chỉ cần tìm cách giải bài toán qhtt dạng chính tắc.
4. PHƯƠNG PHÁP KHỬ GAUSS-JORDAN. NGHIỆM CƠ BẢN CỦA HỆ
PHƯƠNG TRÌNH TUYẾN TÍNH
4.1. Phương pháp khử Gauss-Jordan
Xét hệ thống gồm m phương trình tuyến tính, n biến:






20
…
a
r0
…
a
m0
a
11
a
21
…
a
r1
…
a
m1
a
12
a
22
…
a
r2
…
a
m2
…
…
…

10
a’
20
…
a
r0
/a
rv
…
a’
m0
a’
11
a’
21
…
a
r1
/a
rv
…
a’
m1
a’
12
a’
22
…
a
r2

/a
rv
…
a’
mn
Trong đó: a
i0
=b
i
, i=1,2,…,m
Phép khử Gauss –Jordan (gọi tắt là phép khử) với phần tử trục (Phần tử giải;
Phần tử chủ yếu) là a
rv
≠0 (Dòng r được gọi là dòng xoay, cột v được gọi là cột xoay)
cho bảng mới tương đương với bảng cũ, theo nghĩa là 2 hệ thống tương ứng với 2
bảng là tương đương với nhau.
Quy tắc thực hiện:
- Các phần tử trên dòng xoay đều chia cho phần tử trục.
- Các phần tử còn lại trên cột xoay đều biến thành 0.
- Các phần tử khác tính theo qui tắc đường chéo hình chữ nhật rồi chia cho phần
tử trục:
[ ]
rv
ivrjrvij
rv
rvrj
vij
ij
a
aaaa

thành biến cơ sở tương ứng với dòng xoay.
Ta thấy một nghiệm cơ sở tương ứng với một dạng nghiệm tổng quát, mà các
dạng nghiệm tổng quát khác nhau là do hệ các biến tự do (hay hệ các biến cơ sở) là
khác nhau. Do đó để tìm tất cả nghiệm cơ sở ta đưa vào bảng tính cột x
B
chứa các
biến cơ sở tương ứng với mỗi phương trình và tiến hành thực hiện các phép khử với
các phần tử trục được chọn sao cho thu được các hệ biến cơ sở khác nhau.
Nghiệm cơ sở tương ứng với mỗi bảng sẽ được xác định bằng các cho các
biến cơ sở nhận giá trị tương ứng ở cột b, các biến không nằm trong hệ biến cơ sở
nhận giá trị 0.
- Nghiệm cơ sở suy biến là nghiệm cơ sở tương ứng với nó nhiều hơn 1 hệ
biến cơ sở.
- Nghiệm cơ sở không suy biến là nghiệm cơ sở có tương ứng với nó đúng 1
hệ biến cơ sở.
5. PHƯƠNG ÁN CỰC BIÊN
Pacb (phương án cơ sở; phương án cơ bản) của bài toán qhtt dạng chính tắc là
phương án đồng thời là nghiệm cơ sở của hệ các ràng buộc chung.
Nói cách khác, pacb là nghiệm cơ sở của hệ các ràng buộc chung có thỏa điều
kiện về dấu của các biến.
- Pacb không suy biến là pacb có tương ứng với nó đúng một hệ biến cơ sở.
- Pacb suy biến là pacb có tương ứng với nó nhiều hơn một hệ biến cơ sở.
Do số nghiệm cơ sở của một hệ phương trình tuyến tính là hữu hạng nên số
pacb là hữu hạng.
Số thành phần dương (>0) trong một pacb không vượt quá hạng của hệ ràng
buộc chung.
Pacb có số thành phần lớn hơn 0 đúng bằng hạng của hệ ràng buộc chung sẽ là
pacb không suy biến. Ngược lại, pacb có số thành phần lớn hơn 0 nhỏ hơn hạng của
hệ ràng buộc chung có thể là phương án cực biên suy biến.
6. CƠ SỞ GIẢI TÍCH LỒI

K
i
L
i
i
i
i
zxxXx
∑ ∑
= =
+=⇔∈
1 1
βα
Trong đó x
1
,…,x
K
là các pacb; z
1
,…,z
L
là các vectơ chỉ phương các cạnh vô
hạn.
0≥∀
i
α
, i=1,…,K;
0
≥∀
i

Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt tổng số mã lực cao nhất?
Giải
Gọi x
1
, x
2
lần lượt là số tàu 100 mã lực và 50 mã lực cần đóng
 f(x)=100x
1
+50x
2
 max
Điều kiện:







≥≥
≤+
≤+
≤+
0x,0x
1500x40x80
2000x50x120
3000x70x150
21
21

1
+16x
2
+27x
3
 max
Điều kiện:







=≥
≤+
≤++
≤++
3,2,1j,0x
150x2x3
360x3x4x5
510x5x3x9
j
31
321
321
c. Một xí nghiệp điện cơ sản xuất quạt điện các loại. Cần cắt từ một tấm tôn các cánh
quạt điện theo 3 kiểu A, B, C. Có 6 mẫu cắt khác nhau theo bảng sau:
Kiểu cánh
quạt

 f(x)= 2x
1
+ 2x
2
+ 2x
3
+ 2x
4
+ 3x
5
+ 3x
6
 min
Điều kiện:







=≥
≥++
≥++
≥++
6,5,4,3,2,1j,0x
3000x3x2x
5000xx2x
4000xxx2
j

0
5
8
1
6
2
40
30
30
Nhu cầu hàng hóa 20 25 30 15
Hãy lập kế hoạch vận chuyển sao cho tổng chi phí vận chuyển là bé nhất?
Giải
Gọi x
ij
là lượng hàng hóa cần vận chuyển từ xí nghiệp A
i
(i = 1, 2, 3) đến cửa
hàng B
j
(j=1, 2, 3, 4).
 f(x) = 3x
11
+ 4x
12
+ x
14
+ x
21
+ 2x
22

=++
=++
≤+++
≤+++
≤++
3,2,1,4,3,2,1,0
15
30
20
20
30
30
40
342414
3323
322212
312111
34333231
24232221
141211
ijx
xxx
xx
xxx
xxx
xxxx
xxxx
xxx
ij
e. Công ty may mặc Long Vũ hiện đang lập kế hoạch sản xuất 3 mặt hàng áo Jaket, áo

2
+ 2,8x
3
 max
Điều kiện:







=≥
≤++
≤++
≤++
3,2,1,200
5401.02.01.0
16504.05.03.0
12503.04.02.0
321
321
321
jx
xxx
xxx
xxx
j
f. Nhà máy sản xuất thiết bị nghe nhìn điện tử Hanel lắp ráp thành phẩm máy thu hình
TV, Stereo, loa thùng từ các bộ phận khác nhau. Tên các bộ phận và số lượng còn

1 2 3
1 2
1 2 3
j
x x 450
x 250
2x 2x x 800
x x 450
2x x x 600
x 0
+ ≤


≤


+ + ≤


+ ≤


+ + ≤

≥


Điều kiện:
2. Đưa về dạng chuẩn tắc và chính tắc các bài toán qui hoạch tuyến tính sau:
a. f(x) = 2x

4
- x
5
(x
4
, x
5
≥ 0) và thêm 2 biến phụ x
6
, x
7
≥ 0.
Ta được bài toán: f(x) = 2x
1
- x
4
+ x
5
 max
Điều kiện:
1 3 4 5 6
1 3 4 5 7
1 3 4 5
2 2 2
2 2 2 3
4
0( 1,3,4,5,6,7)
j
x x x x x
x x x x x

 max
Điều kiện:
1 3 4 5
1 3 4 5
1 3 4 5
1 3 4 5
1 3 4 5
1 3 4 5
1 3 4 5
2 2 2
2 2 2
2 2 2 3
2 2 2 3
4
4
4
0( 1,3,4,5)
0( 1,3,4,5)
j
j
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x j
x j
+ − + ≤






≥≥
=−
≤+
≥
0,0
52
4
3
21
21
21
1
xx
xx
xx
x
Giải
Dạng chính tắc: thêm 2 biến phụ x
3
, x
4
≥ 0. Ta có: f(x) = 3x
1
+ x
2

Điều kiện:









=≥
−≥+−
≥−
−≥−−
≥
4,3,2,1j,0x
5xx2
5xx2
4xx
3x
j
21
21
21
1
3. Viết các bài toán qui hoạch tuyến tính sau ở dạng chính tắc:
a. f(x) = 4x
1
+ 3x
2

-x
5
(x
4
, x
5
≥0), thêm 2 biến phụ x
6
, x
7
≥0.
Ta có: F(x) = 4x
1
+ 3x
2
- 2(x
4
- x
5
)  min
Điều kiện:







=≥
=−+−+

25x2x6x3
10xx2x5
15xx2x4
231
321
321
321
Giải
Đặt x
2
= x
4
- x
5
(x
4
, x
5
≥ 0), thêm 2 biến phụ x
6
, x
7
≥ 0.
Ta có: f(x) = 3x
1
+ x
4
– x
5
 min

3
+ x
4


max
Điều kiện:







=≥
=+−
=++
=+++
3,2,1,0
42
2
62
321
421
4321
jx
xxx
xxx
xxxx
j

1
0
0
1
0
-3
2
-2
-1
1
0
-1
2
2
0
1
0
0
1
0
-3
0
1
0
1
0
-1
2
2
0

24
3
21
42
3
21
x3x
2x
x22x
0xx3
2x
2x2x
Cho x
2
= α ⇒ x
4
= -3α, x
1
= 2 + 2α
Chọn α = 0: ta có một phương án (2, 0, 2, 0)
b. Tập phương án của bài toán:
D=
{ }
R,3x,2x,x,22x)x,x,x,x(x
43214321
∈αα−==α=α+==
5. Vẽ miền thỏa mãn các bất phương trình tuyến tính (bậc nhất) sau:
- 2x
1
+ 5x



≥≥
≤+
≤+
≤+
0,0
93
623
1
21
21
21
21
xx
xx
xx
xx
Giải
Miền ràng buộc: OAB
Phương án tối ưu: A(0,1)
Trị tối ưu: f
max
=1
b. f(x) = 5x
1
+ 4x
2



= 22
c. f(x) = 5x
1
+ 3x
2


max
Điều kiện:







≥≥
≥−
≤−
≤+
0,0
02
0
62
21
21
21
21
xx
xx

6
21
21
21
21
xx
xx
xx
xx
Giải
Miền ràng buộc: ABCD
Phương án tối ưu: B (4,2)
Trị tối ưu: f
min
= -10
7. Tìm các phương án cực biên không suy biến của bài toán qui hoạch tuyến tính với
điều kiện ràng buộc sau đây:
a. Điều kiện:





≥≥≥
=++
=−−
0,0,0
3
1
321

là phương án cực biên
không suy biến.
Cho x
3
=0  x
1
=2, x
2
=1  x
2
= (2,1,0)
Xét hệ {A
1
,A
2
} độc lập tuyến tính và x
1
, x
2
> 0 x
2
là phương án cực biên
không suy biến.
b. Điều kiện:





≥≥≥

3
> 0 x
1
là phương án cực biên
không suy biến.
Cho x
2
= 0 x
1
= 16, x
3
= -6 x
2
= (16, 0, -6)  không thỏa điều kiện x
3
> 0
Cho x
3
= 0  x
1
= 8, x
2
= 2  x
3
= (8, 2, 0)
Xét hệ {A
1
,A
2
} độc lập tuyến tính và x

3
= 4  x
1
= (0,0,4)
Xét hệ {A
2
, A
3
} độc lập tuyến tính và chỉ có x
3
> 0 x
1
là phương án cực biên
suy biến
Cho x
2
= 0  x
1
= 0, x
3
= 4  x
2
= x
1
= (0,0,4)
Xét hệ {A
1
, A
3
} độc lập tuyến tính và chỉ có x

- 5x
4


min (P)
Điều kiện:





≥
=+−
=++
0,,,
82
532
4321
432
431
xxxx
xxx
xxx
a. Liệt kê tất cả các phương án của (P)
b. Chứng tỏ (P) có phương án tối ưu. Từ đó chỉ ra phương án cực biên tối ưu
Giải
a. Nhận xét: phương án cực biên của bài toán có nhiều nhất 2 thành phần > 0
 có ít nhất 2 thành phần = 0
Cho x
1

4
= 0  x
2
= 21/2, x
3
= 5/2  x
2
= (0, 21/2, 5/2, 0)
Xét hệ {A
2
, A
3
} độc lập tuyến tính x
2
là phương án cực biên không suy biến
Cho x
2
= x
3
= 0  x
1
= -7, x
4
= 4  x
3
= (-7, 0, 0, 4)  không thỏa điều kiện x
1
> 0
Cho x
2

Cho x
1
= x
2
= x
3
= 0 VN
Cho x
1
= x
2
= x
4
= 0 VN
Cho x
1
= x
3
= x
4
= 0 VN
Cho x
2
= x
3
= x
4
=0 VN
b. Ta có f = x
1

) = x
1
+ 6x
3
- 5x
4
= -5.5/3 = -25/3
f(x
2
) = x
1
+ 6x
3
- 5x
4
= 6.5/2 = 15
f(x
5
)= x
1
+ 6x
3
- 5x
4
= 5
Vậy x
1
= (0,14/3,0,5/3) là phương án tối ưu của bài toán và trị tối ưu là -25/3
CHƯƠNG 2:
PHƯƠNG PHÁP ĐƠN HÌNH

ưu: dừng thuật toán.
- Trái lại, phương pháp sẽ tìm một phương án cực biên mới tốt hơn (giá trị ham mục
tiêu nhỏ hơn) mà nó là một đỉnh kề của đỉnh trước đó. Trở lại bước kiểm tra tối ưu.
Pacb ban đầu
x
0
x
opt
 Thuật toán đơn hình giải bài tập ( D,f ):
Bước 1:
Tìm một phương án cực biên ban đầu
x
0
với cơ sở
{
A
j
, j ∈ J
0
}
gồm m vectơ
độc lập tuyến tính của A
Giả sử
x
0
= (
x
1
0
, x

biến
x
j
(
j ∈ J
0
)
là biến cơ sở.
Mỗi vectơ cột A
k
(k = 1, 2, … , n) của A được biểu diễn qua cơ sở
{
A
j
, j ∈ J
0
}

A
k
= z
1k
A
1
+ z
2k
A
2
+ … + z
mk

2
z
2k
+…+c
m
z
mk
−c
k
,k=1, … ,n
Lập bảng đơn hình ứng với
x
0

Cơ
sở
Hệ
số c
j
Phương
án
x
1
… x
m
… x
k
… x
n
θ

2k
…
z
2n
… … … … … … … … … …
A
i
c
i
x
i
0
0 … 0 …
z
ik
…
z
¿
… …. … … … … … … … …
A
m
c
m
x
m
0
0 … 1 …
z
mk
…

z
m+1,0
= f
(
x
0
)
z
m+1, k
= ∆
k
(
k=1,2,…,n
)
Bước 2: (kiểm tra tối ưu)
Nếu
z
m+1, k
≤ 0,∀ j=1,2,… , n
, thì
x
0
là phương án tối ưu: dừng thuật toán. Trái lại, chuyển
sang bước 3.
Bước 3: (Kiểm tra bài toán không có phương án tối ưu)
Nếu
∃ k :1≤ k ≤ n
sao cho
z
m+1,k

z
i0
z
is
: z
is
>0
}
=
z
r0
z
rs

Giả sử tên biến cơ sở thứ r là
x
i
r
Đưa vectơ
A
i
r
ra khỏi cơ sở
 Xây dựng phương án cực biên mới: Phương án mới x
1
được xác định như sau:
Phương án x
1
tương ứng vói cơ sở J
1

khi thay đổi từ cơ sở cũ sang cơ sở mới, có thể sử
dụng các công thức sau:
(i = 1, 2, …, m+1; k = 0, 1, …, n)
(Chỉ số cột s và chỉ số hàng r được xác định ở bước 4)
Nhận xét: Với giả thiết bài toán không suy biến thì thuật toán giải nêu trên
phải dừng sau một số hữu hạn bước lặp, bởi vì mỗi lần thực hiện bước 4 ta nhận
được phương án cực biên mới tốt hơn phương án cực biên trước đó và số phương án
cực biên của bài toán là hữu hạn.
2. CÁCH TÌM PHƯƠNG ÁN CỰC BIÊN VÀ CƠ SỞ BAN ĐẦU
Xét bài toán QHTT dạng chính tắc ( D,f ):