Trích đề thi 30% Môn quy hoạch tuyến tính.
1

Câu 1: Hãy trình bày một điều kiện cần và đủ để bài toán quy hoạch tuyến tính
(QHTT) bất kỳ có nghiệm. Chứng minh điều đó.
Ý tưởng chứng minh:
Bước 1: Đầu tiên ta phát biểu điều kiện đủ để bài toán QHTT dạng chính tắc:
 
0
, min
0
c u
TT Au b
u
 






có nghiệm.
Giả sử
0
M
 
với
0
M
là tập phương án của


TT
(với tập phương án
0
M
) tương ứng với nó.
CM: - Nếu
M
 
thì
0
M
 
.
- Nếu hàm mục tiêu của


TT
bị chặn dưới trong
M
thì hàm mục tiêu của


0
TT
bị chặn dưới trong
0
M
.
Bước 3: Phát biểu và CM điều kiện cần và đủ để bài toán QHTT dạng tổng quát
có nghiệm.

.
Trích đề thi 30% Môn quy hoạch tuyến tính.
2

Nếu hàm
: ,
u c u


bị chặn dưới trong
0
M
thì


0
TT
có nghiệm.
□ Trước khi chứng minh mệnh đề 1, ta phát biểu và chứng minh mệnh đề sau:
Mệnh đề 2: Tập điểm cực biên của
0
M
là hữu hạn và khác rỗng.

0
extM
hữu hạn.
Ta có
0
M

0
u M
 và có ít thành phần dương hơn
u
. Dùng tiêu chuẩn điểm cực biên
cho tập lồi đa diện
0
M
, xem
1
u
có là điểm cực biên không? Nếu không,
xây dựng tiếp
21
0
u M
 có ít thành phần dương hơn
1
u
. Cứ thế tiếp tục thì
hoặc là sẽ có
i
u
thỏa tiêu chuẩn điểm cực biên hoặc là đi đến vecto 0
cũng là điểm cực biên.
- Vậy
0
extM
 





:
j
a j J u
  độc lập tuyến tính trong
m
R
.
Ta gọi




:
j
a j J u
 là hệ vecto liên kết với
u
.

- Lấy
0
u M

- Nếu
0
u


0 ,
0 ,
u v
u v
 












0 1 , 0,1
tu t v t iii
    
Mà
0
,
u v M
 nên
 
0

0
u

 
0
1 0
1 0
tu
tu t v
t v


   

 

(mâu thuẫn với


0 1
tu t v
   )
Nhưng
0

0
u
v








,
j
x j J u
   không đồng thời bằng 0 sao cho
 
0
j j
j J u
x a




Ta đặt
n
t R
 được xác định như sau:
 


 
neu
0 neu
j
j
x j J u
t
j J u


. Đặt
 
0
min , 0, 0
i
i
i
u
t i J u
t

 
 
   
 
 
 

Khi đó
0 0
0, 0
u t u t
 
   
và có 1 vectow có ít thành phần dương hơn u.
Hơn nữa.
   
 
0 0

1 2
1 1
2 2
u u u
  trong đó
1
u
có số thành phần
dương ít hơn so với
u
. Nếu
1
u
vẫn không phải là điểm cực biên thì cũng
tương tự như trên ta lại xây dựng được
3 4
,
u u
trong đó
3
u
có số thành phần
dương ít hơn so với
1
u
.
Trích đề thi 30% Môn quy hoạch tuyến tính.
5

Nếu

, , ,
k
v v v
. Khi đó ta chọn
*
0
v extM
 sao cho
*
, , , 1, .
i
c v c v i k
 
Từ đó suy ra:
*
0
, , , .
c v c u u M
 
Vậy
*
v
là phương án tối ưu.
Chứng minh cụ thể:
Lấy
0
u M

 Nếu
0

,
A u t b R
 
  
không mất tính
tổng quát, giả sử
, 0
c t

(nếu
, 0
c t

thì lấy
t

thay cho
t
)
Trích đề thi 30% Môn quy hoạch tuyến tính.
6

Một cách tương tự chứng minh mệnh đề 2 ta chọn
0
0


, đủ nhỏ sao cho
0
0

(vì
, 0
c t

).
Mặt khác
: ,
u c u


bị chặn dưới trong
0
M
nên đến giá trị
*

phải có
thành phần nào đó của
*
u t

 bằng 0 để sau đó
u t


ra ngoài
0
M
, tức là
*

, đủ nhỏ
thì
0 0
u t M

  nên đường thẳng qua một điểm của
0
M
. Mà
0
M
không chứa
đường thẳng (vì có ràng buộc
0
u

) nên có điểm
*
u t

 , khi đường thẳng
đến ranh giới để rời
0
M
, có ít thành phần dương hơn
u
. Hơn nữa:
*
, ,
c u t c u

 có một
i
v
để
, ,
i
c v c u
 nên
*
0
, , ,
c v c u u M
   , đương nhiên
*
0
v M
 .
Vậy
*
v
là phương án tối ưu. Tức là


0
TT
có nghiệm.
Trích đề thi 30% Môn quy hoạch tuyến tính.
7

Nhận xét:


khi di chuyển theo nửa
đường thẳng (cho

tăng) thì ràng buộc


A u t b

 
luôn thỏa. Nhưng vì
hàm mục tiêu bị chặn dưới trong
0
M
mà lại có
, khi +
c u t
 
    
,
như vậy sẽ có những điểm trên nửa đường thẳng không thuộc
0
M
, tức là
không thỏa ràng buộc
0
u t

 
, tức là có thành phần nào đó của




0 0
0
j j
u t

 
, khi ra ngoài
0
M
ta có




0 0
0
j j
u t

 
.
Xét hàm số theo
:


   
0 0

Cho
 
, min

c u
TT
Au b






,
M M
 
là tập phương án chấp nhận được của


TT
.
Đặt
   
1 2
1 1 2
1 2
, min

, 0
c u u

 

Đặt
   
1 2
0 1 2
1 2
, min

, , 0
c u u
TT A u u Iv b
u u v
  

  





 


1 2
0 1 2
1 2
, , :
, , 0
n n m



0
TT
bị chặn dưới trong
0
M

Chứng minh:
(i) Giả sử
M
 
thì
u M
 

Đặt
1 2
,
n
u u R
 được xác định như sau:
 




 
1
if 0

u

 







Ta có
1 2 1 2
, 0, 0
u u u u u
   

Do
u M

nên


1 2
0
Au b A u u
   

Đặt



1 2
, ,
n n m
u u v R R R
  
ta có
1 2
, , 0
u u v


Do cách đặt ta có:


1 2
A u u Iv b
  
tức là


1 2 0 0
, , hay u u v M M
  

(ii) Hàm mục tiêu của


TT
bị chặn dưới trong
M


Vậy hàm mục tiêu của


1
TT
bị chặn dưới trong
1
M
.
+ Lấy


1 2 0 1 2
, , . CM ,u u v M c u u

  

Đặt


1 2
,
u u u
 , do


1 2 0
, ,
u u v M

M
nên
1 2
,c u u

 
.
Từ đó ta có hàm mục tiêu của


0
TT
bị chặn dưới trong
0
M
.
Bước 3:
Xét
 
, min
c u
TT
Au b






M


TT
có nghiệm, tức là:
*
*
, ,
u M
c u c u

 






Đặt
*
,
c u

 , Ta có , ,u M c u

  
hay
: ,
u c u


bị chặn dưới trong






 
 
1 2
0
1 2
1 2
, min
, , 0
c u u
TT
A u u Iv b
u u v

 

  





Do
M
 
và hàm

có
nghiệm và


TT
có nghiệm.
Chứng minh xong.