Bài giảng quy hoạch toán
Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
PHƯƠNG PHÁP HÌNH HỌC
1.1.
Các bài toán thực tế
1.1.1. Bài toán lập kế hoạch sản xuất
a) Ví dụ Để sản xuất kẹo và bánh cần 2 thứ nguyên liệu chính là đường và bột mì,
với trữ lượng hiện có là 0,9kg đường và 1,1 kg bột mì. 1kg kẹo cần 0,5 kg đường và 0,3
kg bột mì; 1kg bánh cần 0,2kg đường và 0,4 kg bột mì.
Giá 1kg kẹo là 10000đ; 1kg bánh là 20000đ. Hãy lập kế hoạch sản xuất sao cho
tổng giá trị sản phẩm lớn nhất.

Gọi x
1
là số kg kẹo được sản xuất; x
2
là số kg bánh được sản xuất.
Có mô hình toán học:

f(x) = 10000x
1
+20000x
2
→ max

⎪
⎩
⎪
⎨
⎧
≥

là số sản phẩm j được sản xuất,
f(x) là tổng doanh thu ứng với kế hoạch sản xuất x = (x
1
,x
2
, , x
n
).
Có mô hình toán học:

f(x) =
c
∑
=
n
j 1
j
x
j
→ max
⎪
⎩
⎪
⎨
⎧
=≥
=≤
∑
=
) 1(0

m
i 1 =
n
j 1
ij
x
ij
→ min ⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎨
⎧
==≥
==
=≤
∑
∑
=
=
) 1, 1(0
) 1(

,x
2
, , x
n
).
Có mô hình toán học sau:
f(x) =
c
∑
=
n
j 1
j
x
j
→ min
⎪
⎩
⎪
⎨
⎧
=≥
=≥
∑
=
) 1(0
) 1(
1
njx
mibxa

⎨
⎧
+=≤
+=≥
==
∑
∑
∑
=
=
=
) 1(
) 1(
) 1(
1
1
1
mkibxa
kpibxa
pibxa
ij
n
j
ij
ij
n
j
ij
ij
n

nhưng có thể đưa về bài toán 2 ẩn tương đương.

Xét bài toán
f(x) = ax +by → min (max)
(d)

{
) 1( miciybxa
ii
=≤+

Miền d d là giao các nửa mặt phẳng, hay là một đa giác. Bài toán có thể phát biểu bằng
hình học như sau:
Tìm trong họ đường thẳng song song ax+ by = f gọi là họ đường mức ,một đường mức
ứng với f nhỏ nhất (lớn nhất) có ít nhất 1 điểm chung với miền d.

Ví dụ 1.1
f(x,y) = x + 2y → max ⎪
⎩
⎪
⎨
⎧
≥
≤+
≤+
0,
1143

=
4
11
và f
max
=
2
11
.
Nhận xét
- Nghiệm là đỉnh của đa giác.
- Nếu hàm mục tiêu là f(x,y) = 3x + 4y thì nghiệm là cả đoạn thẳng AB.
- Giá trị f của họ đường mức tăng theo chiều của pháp vectơ.

Ví dụ 1.2
f(x,y) = x + y → max ⎪
⎩
⎪
⎨
⎧
≥
≤−
−≥−
0,
22
1
yx

xy
+≤
+≤
≥≥
⎧
⎨
⎪
⎩
⎪
,
2
xy
xy
xy
+≤
+≥
≥≥
⎧
⎨
⎪
⎩
⎪
24
36
00,3. f(x) = 3x + y → max 4. f(x) = 2x + 3y +10 → max
⎪
⎪
⎩
⎪
⎪
,5. f(x) = 2x + 5y → max 6. f(x) = x + 3y → max 22
8
3
21
00
xy
xy
xy
xy
xy
+≥
+≤
+≥
+≤
≥≥
⎧
⎨
⎪
⎪

+≤
≥≥
⎧
⎨
⎪
⎩
⎪
8
21
00,
4
xy
xy
xy
xy
+
≥
+≥
+≥
≥≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
28
36
34 1

00
++=
++≤
++ ≤
≥≥≥
⎧
⎨
⎪
⎪
⎩
⎪
⎪
,,
xxx
xx x
xxx
123
12 3
123
1
223
00
++=
++ ≥
≥≥≥
⎧
⎨
⎪
⎩
⎪

=≥
==
∑
=
)3() 1(0
)2() 1(
1
njx
mibxa
j
ij
n
j
ij(2) gọi là ràng buộc cưỡng bức, (3) gọi là ràng buộc tự nhiên.
Với bài toán (d,f) chính tắc, có thể giả sử m ≤n.

Một trường hợp đặc biệt của dạng chính tắc là ma trận số liệu A = (a
ij
)
mxn
có chứa
đủ m vectơ cột là m vectơ đơn vị của không gian R
m
và b
i
≥ 0 (i=1 m) gọi là dạng chuẩn
tắc. Không mất tính tổng quát, có thể định nghĩa bài toán (d,f) chuẩn tắc như sau:


trong đó b
i
≥ 0 (i=1 m).
2.1.2. Các phép biến đổi
Các phép biến đổi sau để đưa bài toán (d,f) bất kỳ về dạng chính tắc tương đương
để giải, và từ đó suy ra nghiệm của bài toán ban đầu.
a/ f(x) → max
g(x) = -f(x) → min ⇔
b/
∑
với x
=
≤
n
j
ijij
bxa
1
⇔
∑
=
+
=+
n
j
iinjij
bxxa
1
n+i

, x
2
, , x
n
, x
n+1
, , x
n+m
) là nghiệm của bài toán chính tắc biến đổi thì
x=(x
1
, x
2
, , x
n
) là nghiệm bài toán gốc.
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 7
________________________________________________________________________

c/ Nếu ẩn x
j
không ràng buộc về dấu thì được thay bằng hiệu hai ẩn không âm.
Nghĩa là đặt x
j
=x
j
’ – x
j

⎩
⎪
⎨
⎧
=≥
==
∑
=
) 1(0
) 1(
1
njx
mibxa
j
ij
n
j
ijĐặt A
j
= (a
1j
, a
2j
, , a
mj
) là vectơ cột thứ j trong ma trận A
mxn

j
> 0.

Nhận xét:
- Phương án cơ bản có tối đa m thành phần dương.
Phương án cơ bản có đúng m thành phần dương gọi là không suy biến. Ngược lại
gọi là suy biến. Bài toán có phương án cơ bản suy biến gọi là bài toán suy biến.
- Số phương án cơ bản của một bài toán (d,f) là hữu hạn.
- Với bài toán dạng chuẩn tắc thì có phương án cơ bản là x
o
= (b
1
, b
2
, ,b
m
,0, ,0).
2.1.4. Các tính chất
Tính chất 1 Bài toán (d,f) chỉ xảy ra 1 trong 3 trường hợp sau:
a) Vô nghiệm b) Có 1 nghiệm duy nhất c) Vô số nghiệm.

Tính chất 2 Nếu hàm mục tiêu f(x) là chặn dưới (trên ) đối với bài toán dạng min (max)
trên tập phương án d thì bài toán (d,f) có nghiệm.
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 8
________________________________________________________________________
Tính chất 3 Nếu bài toán (d,f) có nghiệm thì có nghệm là phương án cơ bản.
2.2. Phương pháp đơn hình
2.2.1. Nội dung

xxx
jCó phương án cơ bản x
o
= (0, 0, 4, 5) và f(x
o
)=2 với x
3
, x
4
là ẩn cơ bản.
Đánh giá:
∀ x=(x
1
,x
2
,x
3
,x
4
)∈ d :
⎪
⎩
⎪
⎨
⎧
=≥
=++

1
-2x
2
+3x
3
-2x
4
= x
1
-2x
2
+3(4-2x
1
+3x
2
) -2(5-x
1
-x
2
)
= 2 -3x
1
+9x
2

= 2-∆
1
x
1
- ∆

⎨
⎧
=+
=
5
42
41
1
xx
x
x⇒
1
=2 và x
4
=3.
Rõ ràng A
1
, A
4
độc lập tuyến tính nên có phương án cơ bản là x = (2, 0, 0, 3)
và f(
x ) = - 4.
Đánh giá:
∀ x=(x
1
,x
2
,x
3
,x

1
2
5
3
2
1
2
3
2
xxx
xxx

f(x) = x
1
-2x
2
+3x
3
-2x
4
= (2+
2
3
x
2
-
2
1
x
3

2
- ∆
3
x
3
)
≥ -4
Vì x
2
, x
3
≥0 nên x là phương án tối ưu (∆
2
, ∆
3
≤0).
2.2.2. Bảng đơn hình
Cho bài toán (d,f) chuẩn tắc:
f(x) =
c
∑
=
n
j 1
j
x
j
→ min
⎪
⎩

a
ij
- c
j
và gọi là ước lương của ẩn x
j
đối với phương án cơ bản
x
o
=(b
1
, b
2
, …, b
m
, 0, …, 0) với f(x
o
)= c
∑
=
m
i 1
i
b
i
Lưu ý: ∆
i
= 0 , ∀ i=1 m

Có bảng đơn hình sau:

1
x
1
b
1
1 0 … 0 a
1,m+1
… a
1s
… a
1n
c
2
x
2
b
2
0 1 … 0 a
2,m+1
… a
2s
… a
2n
… …
…
… … … … … … …
c
r
x
r

m+1
∆
s
∆
n
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 10
________________________________________________________________________
2.2.3. Cơ sở lý luận
Cho bài toán (d,f) chuẩn tắc:
f(x) =
c
∑
=
n
j 1
j
x
j
→ min
⎪
⎩
⎪
⎨
⎧
=≥
==+
∑
+=

1
, b
2
, …, b
m
, 0, …, 0) với f(x
o
)= c
∑
=
m
i 1
i
b
i
Định lý 1 ( Dấu hiệu tối ưu)
Nếu ∆
j
≤0 với mọi j = 1 n thì x
o
là phương án tối ưu.

Chứng minh
Có f(x
o
)= c
∑
=
m
i 1

j
(i=1 m)
f(x) =
c
∑
=
n
j 1
j
x
j

=
c
∑
=
m
i 1
i
x
i
+ c
∑
+=
n
mj 1
j
x
j
= c

i
- ( c
∑
+=
n
mj 1
∑
=
m
i 1
i
a
ij
-c
j
) x
j
= f(x
o
) - ∆
∑
+=
n
mj 1
j
x
j
≥ f(x
o
) : vì ∆