Bài giảng Quy hoạch toán học Trang 11
________________________________________________________________________
∀ θ>0, xét bộ số x=(x
j
)
n
với
⎪
⎩
⎪
⎨
⎧
≠+==
=
=−=
), 1(0
) 1(
kjnmjx
x
miabx
j
k
ikii
ϑ
ϑ

∀ i=1 m: x
i
+ a
∑
+=

≥0 ∀ j=m+1 n (2)
(1) và (2) có x
∈ d

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

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

m
i 1
i
a
ik
+c
k
θ
= f(x
o
) – θ( c
∑
=
m
i 1
i
a
ik
-c
k
)
= f(x
o
) – θ∆
k

Cho x→ +∞ thì f(x) → -∞ trên d. Hay f(x) không bị chặn dưới trên d.
Vậy bài toán vô nghiệm.

Định lý 3 ( Điều chỉnh phương án)

Giả sử θ=
rs
r
a
b
, có
rs
r
a
b
≤
is
i
a
b

Xét bộ số
x =(x
j
)
n
với
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 12
________________________________________________________________________
⎪
⎩
⎪
⎨

is
θ= b
i
(1)
x
s
= θ>0 nên x
j
≥0 j=m+1 n ∀
∀ i=1 m: x
i
= b
i
-θa
is
= b
i
-
rs
r
a
b
a
is
≥0. Vì
is
i
a
b
≥

là ẩn không cơ bản.
Hệ vectơ liên kết x
o
là m vectơ đơn vị {A
1
, A
2
, …, A
m
}.
Vậy hệ vectơ liên kết
x là hệ con của {A
1
, A
2
, …, A
m
}U {A
s
}\{A
r
}.
Giả sử hệ vectơ liên kết
x phụ thuộc tuyến tính thì hệ {A
1
, A
2
, …, A
m
} {AU

m
ri
i
ii
Ak
1
1
, A
2
, …, A
m
} là hệ
vectơ đơn vị. Vậy k
s
≠0 và + k
∑
≠
=
m
ri
i
ii
Ak
1
s
A
s
= θ
hay A
s

i
(4)
Trừ (4) cho (3) có
∑
≠
=
+
m
ri
i
i
s
i
is
A
k
k
a
1
)( + a
rs
A
r
= θ.
Do {A
1
, A
2
, …, A
m

n
mj 1
j
x
j
= c
∑
=
m
i 1
i
(b
i
-θa
is
) + c
∑
+=
n
mj 1
j
x
j
= c
∑
=
m
i 1
i
b

o
) , vì θ>0 và ∆
s
>0.
Hay phương án cơ bản tốt hơn phương án cơ bản x
o
một lượng θ∆
s
.
2.2.4. Các bước của thuật toán đơn hình
Bước 1 Kiểm tra tính tối ưu của phương án x
o
=(b
1
, b
2
, …, b
m
, 0, …, 0)
* Nếu ∆
j
≤0 ∀ j = 1 n thì x
o
là phương án tối ưu và f
min
=f(x
o
)= c
∑
=

} với ∆
j
>0 (j=1 n) thì đưa x
s
đưa vào tập ẩn cơ bản .
* Nếu
rs
r
a
b
=min {
is
i
a
b
} với a
is
> 0 thì loại x
r
ra khỏi tập ẩn cơ bản .
* Chuyển sang bước 4.

Bước 4 Biến đổi bảng đơn hình
* Biến đổi bảng đơn hình theo công thức sau:
⎪
⎪
⎩
⎪
⎪
⎨

ria
a
b
bb
b
is
rs
r
ii
r
θ

* Tính lại các giá trị ∆
j
, quay lại bước 1.
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 14
________________________________________________________________________
Quá trình này có thể mô tả như việc biến đổi sơ cấp về hàng trên ma trận bổ sung
của hệ ràng buộc sao cho vectơ A
s
trở thành vectơ đơn vị thứ r, và các vectơ đơn vị khác
vẫn giữ nguyên.

Nhận xét Các công thức biến đổi cho a
ij
cũng đúng cho cả b
i
và ∆

=≥
=++
=+++
=+++
)6 1(0
363
60324
52342
631
5321
4321
jx
xxx
xxxx
xxxx
j

Hệ
số
Ẩn
CB
P/Án x
1
5
x
2
4
x
3
5


128
0 6 3 0 0 -4
2 x
4
4 0 0 -1 1 -2 2
4 x
2
6 0 1 5/6 0 1/2 -2/3
5 x
1
12 1 0 1/3 0 0 1/3

92
0 0 -2 0 -3 0

∆
j
≤0 j =1 6, x
∀
opt
= (12, 6, 0, 4, 0, 0) và f
min
=92

Ví dụ 2.3
f (x) = 3x
1
-2x
2

________________________________________________________________________
Hệ
số
Ẩn
CB
P/Án x
1
3
x
2
-1
x
3
2
x
4
-1
3 x
1
1 1 1 0 -2
2 x
3
1 0 -2 1 3

5
0 0 0 1
3 x
1
5/3 1 -1/3 2/3 0
-1 x

1
n+i
≥0

∑
với x
=
≥
n
j
ijij
bxa
1
⇔
∑
=
+
=−
n
j
iinjij
bxxa
1
n+i
≥0
x
n+i
gọi là ẩn phụ. Có kết luận sau:
Nếu
x = (x

⎪
⎩
⎪
⎪
⎨
⎧
=≥
≤++−
−≥−−
=++−
)4 1(0
10834
1242
723
321
321
4321
jx
xxx
xxx
xxxx
j

Bài toán chính tắc tương đương
g (x) = x
1
-3x
2
+2x
3

là ẩn phụ.
Đây là bài toán (d,f) chuẩn tắc nên được đưa vào bảng đơn hình để giải. ________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 16
________________________________________________________________________

Hệ
số
Ẩn
CB
P/Án x
1
1
x
2
-3
x
3
2
x
4
0
x
5
0
x
6

5 0 1 7/10 1/5 3/10 0
0 x
6
11 0 0 19/2 1 -1/2 1

-11
0 0 -16/5 -1/5 -4/5 0

∆
j
≤0 j =1 6, x
∀
opt
= (4, 5, 0, 0, 0, 11) và f
min
=-11. Vậy nghiêm bài toán gốc là
x
opt
= (4, 5, 0, 0) và f
max
=11.

Nếu các giá trị min/max đạt tại nhiều vị trí thì chọn tùy ý một vị trí bất kỳ trong số đó.
Thông thường chọn chỉ số nhỏ nhất.
2.2.6. Bài toán ẩn giả
Cho bài toán (d,f) dạng chính tắc:
f(x) =
c
∑
=

Xét bài toán:

f ( x ) = c
∑
=
n
j 1
j
x
j
+ M
∑
x
=
m
i 1
n+i
→ min
⎪
⎩
⎪
⎨
⎧
+=≥
==+
+
=
∑
) 1(0
) 1(

, , x
n
, 0, ,0) thì x = (x
1
, x
2
, , x
n
) là
nghiệm của bài toán (d,f).
• Nếu bài toán M có nghiệm
x = (x
1
, x
2
, , x
n+m
) và
∃
x
n+m
)>0 thì bài toán (d,f) vô
nghiệm.

Tiến trình giải bài toán M là loại dần các ẩn giả ra khỏi tập ẩn cơ bản cho đến khi loại tất
cả là bắt đầu giải bài toán gốc. Nên từ đó có thể không cần tính cho các cột ẩn giả. Nếu
cuối cùng không loại được các ẩn giả mà nhận giá trị 0 thì bài toán gốc cũng có nghiệm.

Ở đây giả sử bài toán (d,f) trong ma trận số liệu A không có vectơ
đơn vị nào. Tuy

321
jx
xxx
xxx
xxx
j

Dạng chính tắc tương đương:
f (x) = -x
1
-2x
2
+x
3
→ min
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=≥
=+−
=−++
=+−+−
)5 1(0
422
62
624

7
→ min
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 18
________________________________________________________________________

⎪
⎪
⎩
⎪
⎪
⎨
⎧
=≥
=++−
=+−++
=+−+−
)7 1(0
422
62
624
7321
65321
4321
jx
xxxx
xxxxx
xxxx
j

M x
7
4 2 -1 2 0 0 0 1 3M+1 2 4M-1 0 -M 0 0
0 x
4
10 1 3 0 1 0 0 1
M x
6
2 -1 2 0 0 -1 1 -1
1 x
3
2 1 -1/2 1 0 0 0 1/2 -M+2 2M+3/2 0 0 -M 0 -2M+1/2
0 x
4
7 5/2 0 0 1 3/2 -3/2 5/2
-2 x
2
1 -1/2 1 0 0 -1/2 1/2 -1/2
1 x
3
5/2 3/4 0 1 0 -1/4 1/4 1/4

-9/2
11/4 0 0 0 3/4 -M-3/4 -M+5/4


⎪
⎩
⎪
⎨
⎧
=≥
=−+
=++
)3 1(0
434
4434
321
321
jx
xxx
xxx
j

Bài toán M tương ứng:

f ( x ) = -8x
1
+6x
2
+2x
3
+Mx
4
+Mx

P/Án x
1
-8
x
2
6
x
3
2
x
4
M
x
5
M
M x
4
4 4 3 4 1 0
M x
5
4 4 1 -3 0 1 8M+8 4M-6 M-2 0 0
-8 x
1
1 1 3/4 1 1/4 0
M x
5
0 0 -2 -7 -1 1

)3 1(0
534
4434
321
321
jx
xxx
xxx
j

Bài toán M tương ứng:

f ( x ) = -8x
1
+6x
2
+2x
3
+Mx
4
+Mx
5
→ min ⎪
⎩
⎪
⎨
⎧

M x
4
4 4 3 4 1 0
M x
5
5 4 1 -3 0 1 8M+8 4M-6 M-2 0 0
-8 x
1
1 1 3/4 1 1/4 0
M x
5
1 0 -2 -7 -1 1 0 -2M-12 -7M-10 -2M-2 0

Ẩn giả x
5
còn là ẩn cơ bản nhưng nhận giá trị x
5
=1>0 nên nên bài toán gốc vô nghiệm.
________________________________________________________________________
GV: Phan Thanh Tao
Bài giảng Quy hoạch toán học Trang 20
________________________________________________________________________
2.3. Cài đặt thuật toán đơn hình
2.3.1. Khai báo dữ liệu

ẩn cơ bản thứ i ⇔ acb[i]=j

Tập ẩn cơ bản ban đầu gồm m ẩn được nhập từ bàn phím
2.3.2. Tính các ước lượng ∆
j

for (j=1; j<=n; j++){
a[m+1][j]=0;
for (i=1; j<=m; i++) a[m+1][j]+= a[0][ACB[i]]*a[i][j];
a[m+1][j]-= a[0][j];
}
2.3.3. Kiểm tra tối ưu và tìm ẩn thay thế
int Toiuu( )
{
int s=1, j=1;
for (j=1; j<=n; j++)
if (a[m+1][j]> a[m+1][s])s=j;
return a[m+1][s]>0;
}
2.3.4. Kiểm tra vô nghiệm
int Vonghiem( )
{
int i,j;

for (j=1; j<=n; j++)
if (a[m+1][j]> 0){
i=1; while (i<=m && a[i][j]<=0)i++;
if (i>m)retrun 1;
}
return 0;