BÀI 3

1) Mục đích: Giải bài toán QHTT có ẩn giả. Bài toán
này xuất hiện khi chuyển bài toán dạng chính tắc về
bài toán dạng chuẩn bằng cách đưa vào ẩn giả để tạo
ma trận đơn vị.
- Từ bài toán xuất phát dạng chính tắc:
1
( )
n
j
f x c x
j j
=
= →
∑
Min (Max)
ij
, 1, ,
j i
a x b i m= =
∑
0; 1, ,x j n
j
≥ =

Ta chuyển về bài toán:
- Bài toán dạng chuẩn với biến giả (bài toán mở rộng hay
bài toán M).
( )

a x x b i m
ij j i i
j
x x i m j n
j i
+ = =
∑
=
≥ ≥ = =

Ví dụ 1:
( )
8 6 2 min
1 2 3
4 4 3 18
1 2 3
4 3 4 16
1 2 3
0, 1,2,3
f x x x x
x x x
x x x
x j
j
= − + + →
+ − =
+ + =
≥ =
Suy ra ta có bài toán dạng chuẩn với biến giả:
( )

) = (x, 0)

là phương án của bài toán mở rộng. Ngược
lại phương án của bài toán mở rộng là (x*, x
i
g
) = (x, 0) thì
x là phương án của bài toán xuất phát.

x là phương án cơ bản của bài toán xuất phát  (x, 0)
là PACB của bài toán mở rộng.
( )
0,
g
i
x i
= ∀


Bài toán mở rộng có dạng chuẩn, xuất phát từ PACB
ban đầu có các ẩn . Áp dụng thuật toán đơn hình
giải bài toán đơn hình sau một số bước ta có kết luận:

Bài toán M không có PATƯ thì bài toán xuất phát
không có PATƯ

Bài toán M có PATƯ (x*, x
i
g
). Khi đó xảy ra 2 TH:

Ví dụ 3: Giải bài toán QHTT sau:
( )
5
2 5 min
1 2 4
2 4 2
5
1 2 3 4
7 5 5
2 3 4
9 0
3 4
0, 1, ,5
f x x x x x
x x x x x
x x x
x x
x j
j
= + + − →
− + + − =
− − =
+ =
≥ =
ĐS: bài toán không có PATƯ

Ví dụ 4: Giải bài toán QHTT:
( )
2 3 4 max
1 2 3 4

2 3 4
2 4 min
3 1
5 2 3
4 3
0, 1;4
j
f x x x x x
x x x
x x
x x x
x j
= − − − − →
+ + =


− − ≤


+ + ≤


≥ =

Giải bài toán QHTT sau: