a- Định lý 1 ( đối ngẫu yếu )
Xét hai bài toán đối ngẫu :
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
size 12{ \( P \) " "alignl { stack {
left lbrace "max z" \( x \) =c rSup { size 8{T} } "x " {} #
right none left lbrace "Ax"=" b " {} #
right none left lbrace x >= "0 " {} #
right no } } lbrace } {}
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
size 12{ \( D \) " "alignl { stack {
left lbrace "min w" \( y \) =" b" rSup { size 8{T} } "y " {} #
right none left lbrace A rSup { size 8{T} } y >= "c " {} #
right none left lbrace "y tùy ý " {} #
right no } } lbrace } {}
Nếu
x¯x¯ size 12{ {overline {x}} } {} là phương án của bài toán (P)
y¯y¯ size 12{ {overline {y}} } {} là phương án của bài toán (D)
thì
z(x¯)≤w(y¯)z(x¯)≤w(y¯) size 12{z \( {overline {x}} \) <= w \( {overline {y}} \) } {}
nghĩa là giá trị hàm mục tiêu của bài toán max không vượt quá giá trị hàm mục tiêu của bài toán đối ngẫu min trên các phương án bất kỳ của mỗi bài toán .
Chứng minh
x¯x¯ size 12{ {overline {x}} } {} là phương án của (P) nên :
Ax¯=bAx¯=b size 12{A {overline {x}} =b" "} {}
Þ
y¯TAx¯=y¯T b=bTy¯=w(y¯)y¯TAx¯=y¯T b=bTy¯=w(y¯) size 12{ {overline {y}} rSup { size 8{T} } A {overline {x}} = {overline {y}} rSup { size 8{T} } " b"=b rSup { size 8{T} } {overline {y}} =w \( {overline {y}} \) } {}
y¯y¯ size 12{ {overline {y}} } {} là phương án của (D) nên :
ATy¯≥cATy¯≥c size 12{A rSup { size 8{T} } {overline {y}} >= c} {}
Þ
y¯TA≥cTy¯TA≥cT size 12{ {overline {y}} rSup { size 8{T} } A >= c rSup { size 8{T} } } {}
Þ
y¯TAx¯≥cTx¯=z(x¯)y¯TAx¯≥cTx¯=z(x¯) size 12{ {overline {y}} rSup { size 8{T} } A {overline {x}} >= c rSup { size 8{T} } {overline {x}} =z \( {overline {x}} \) } {}
Vậy
z(x¯)≤w(y¯)z(x¯)≤w(y¯) size 12{z \( {overline {x}} \) <= w \( {overline {y}} \) } {}
Định lý này được phát biểu và chứng minh cho hai bài toán đối ngẫu trong trường hợp tổng quát .
b- Định lý 2
Xét hai bài toán đối ngẫu :
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
size 12{ \( P \) " "alignl { stack {
left lbrace "max z" \( x \) =c rSup { size 8{T} } x {} #
right none left lbrace "Ax"=" b " {} #
right none left lbrace x >= "0 " {} #
right no } } lbrace } {}
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
size 12{ \( D \) " "alignl { stack {
left lbrace "min w" \( y \) =" b" rSup { size 8{T} } y {} #
right none left lbrace A rSup { size 8{T} } y >= "c " {} #
right none left lbrace "y tùy ý " {} #
right no } } lbrace } {}
x¯x¯ size 12{ {overline {x}} } {} là phương án khả thi của bài toán (P)
y¯y¯ size 12{ {overline {y}} } {} là phương án khả thi của bài toán (D)
Nếu
z(x¯)=w(y¯)z(x¯)=w(y¯) size 12{z \( {overline {x}} \) =w \( {overline {y}} \) } {} thì
x¯x¯ size 12{ {overline {x}} } {},
y¯y¯ size 12{ {overline {y}} } {} lần lượt là phương án tối ưu tương ứng của (P và (D).
Chúng minh
- Nếu
x¯x¯ size 12{ {overline {x}} } {} không là phương án tối ưu của bài toán (P) thì tồn tại một phương án x sao cho :
z
(
x
¯
)
<
z
(
x
)
z
(
x
¯
)
<
z
(
x
)
size 12{z \( {overline {x}} \) <z \( x \) } {}
Þ
w(y¯)<z(x)w(y¯)<z(x) size 12{w \( {overline {y}} \) <z \( x \) } {} : điều này mâu thuẩn với định lý 1.
- Nếu
y¯y¯ size 12{ {overline {y}} } {} không là phương án tối ưu của bài toán (D) thì tồn tại một phương án y sao cho :
w
(
y
)
<
w
(
y
¯
)
w
(
y
)
<
w
(
y
¯
)
size 12{w \( y \) <w \( {overline {y}} \) } {}
Þ
w(y)<z(x¯)w(y)<z(x¯) size 12{w \( y \) <z \( {overline {x}} \) } {} : điều này mâu thuẩn với định lý 1.
Vậy
x¯x¯ size 12{ {overline {x}} } {} và
y¯y¯ size 12{ {overline {y}} } {} lần lượt là phương án tối ưu của (P) và (D).
c- Định lý 3
Xét hai bài toán đối ngẫu :
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
size 12{ \( P \) " "alignl { stack {
left lbrace "max z" \( x \) =c rSup { size 8{T} } "x " {} #
right none left lbrace "Ax"=" b " {} #
right none left lbrace x >= "0 " {} #
right no } } lbrace } {}
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
size 12{ \( D \) " "alignl { stack {
left lbrace "min w" \( y \) =" b" rSup { size 8{T} } y {} #
right none left lbrace A rSup { size 8{T} } y >= "c " {} #
right none left lbrace "y tùy ý " {} #
right no } } lbrace } {}
Nếu x* là phương án tối ưu của bài toán (P) đối với cơ sở B thì phương án tối ưu y* của bài toán (D) được tính bởi công thức :
y
∗
T
=
c
B
T
B
−
1
y
∗
T
=
c
B
T
B
−
1
size 12{ left (y* right ) rSup { size 8{T} } =c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } } {}
Chứng minh
Do x* là phương án tối ưu của (P) với cơ sở B nên thoả dấu hiệu tối ưu
c
T
−
c
B
T
.
B
−
1
A
≤
0
c
T
−
c
B
T
.
B
−
1
A
≤
0
size 12{c rSup { size 8{T} } - c rSub { size 8{B} } rSup { size 8{T} } "." B rSup { size 8{ - 1} } A <= 0} {}
Þ
cBT.B−1A≥cTcBT.B−1A≥cT size 12{c rSub { size 8{B} } rSup { size 8{T} } "." B rSup { size 8{ - 1} } A >= c rSup { size 8{T} } } {}
Þ
y∗TA≥cTy∗TA≥cT size 12{ left (y* right ) rSup { size 8{T} } A >= c rSup { size 8{T} } } {}
Þy* là một phương án của (D)
Mặt khác x* được tính bởi công thức :
x
B
=
B
−
1
b
x
N
=
0
righ
x
=
x
B
=
B
−
1
b
x
N
=
0
righ
x
=
size 12{x rSup { size 8{*} } =alignl { stack {
left [x rSub { size 8{B} } rSup { size 8{*} } =B rSup { size 8{ - 1} } b {} #
right ] left [x rSub { size 8{N} } rSup { size 8{*} } =0 {} #
righ]} } \[ \] } {}
và giá trị mục tiêu tối ưu của (P) là :
z(x*) = cTx* =
cBTxBcBTxB size 12{c rSub { size 8{B} } rSup { size 8{T} } x rSub { size 8{B} } rSup { size 8{*} } } {}
Ta có :
w
(
y
)
=
b
T
y
∗
b
T
(
c
B
T
B
−
1
)
T
=
(
c
B
T
B
−
1
)
b
=
c
B
T
(
B
-1
b
)
=
c
B
T
x
B
=
c
B
T
x
B
=
z
(
x
)
w
(
y
)
=
b
T
y
∗
b
T
(
c
B
T
B
−
1
)
T
=
(
c
B
T
B
−
1
)
b
=
c
B
T
(
B
-1
b
)
=
c
B
T
x
B
=
c
B
T
x
B
=
z
(
x
)
alignl { stack {
size 12{w \( y rSup { size 8{*} } \) =b rSup { size 8{T} } y*=b rSup { size 8{T} } \( c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } \) rSup { size 8{T} } = \( c rSub { size 8{B} } rSup { size 8{T} } B rSup { size 8{ - 1} } \) b} {} #
" "=" c" rSub { size 8{B} } rSup { size 8{T} } \( B rSup { size 8{"-1"} } b \) =c rSub { size 8{B} } rSup { size 8{T} } x rSub { size 8{B} } rSup { size 8{*} } =c rSub { size 8{B} } rSup { size 8{T} } x rSub { size 8{B} } rSup { size 8{*} } =z \( x rSup { size 8{*} } \) {}
} } {}
Theo định lý 2 thì y* là phương án tối ưu của (D).
Định lý này cho phép tìm phương án tối ưu của bài toán quy hoạch tuyến tính đối ngẫu từ bài toán gốc. Trong đó :
-
cBTcBT size 12{c rSub { size 8{B} } rSup { size 8{T} } } {} được xác định trong bảng đơn hình tối ưu của (P).
- B-1 gồm m cột tương ứng với m cột của ma trận cơ sở ban đầu lấy từ bảng đơn hình tối ưu của bài toán gốc.
d- Định lý 4 ( sự đối ngẫu)
Xét hai bài toán đối ngẫu
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
size 12{ \( P \) " "alignl { stack {
left lbrace "max z" \( x \) =c rSup { size 8{T} } "x " {} #
right none left lbrace "Ax"=" b " {} #
right none left lbrace x >= "0 " {} #
right no } } lbrace } {}
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
size 12{ \( D \) " "alignl { stack {
left lbrace "min w" \( y \) =" b" rSup { size 8{T} } y {} #
right none left lbrace A rSup { size 8{T} } y >= "c " {} #
right none left lbrace "y tùy ý " {} #
right no } } lbrace } {}
- Nếu (P) và (D) đều có phương án khả thi thì chúng có phương án tối ưu và giá trị của hàm mục tiêu tương ứng là bằng nhau.
- Nếu một trong hai bài toán có phương án tối ưu không giới nội thì bài toán còn lại không có phương án khả thi.
Chứng minh
- Đây là kết quả của định lý 3 .
- Giả sử rằng phương án tối ưu của (D) không giới nội, tức là tồn tại một phương án khả thi y của (D) sao cho w(y)= bTy nhỏ tuỳ ý. Điều này cũng có nghĩa là : với mọi M>0 lớn tuỳ ý luôn tìm được một phương án khả thi
y¯y¯ size 12{ {overline {y}} } {}của (D) sao cho :
b
T
y
¯
≤
−
M
b
T
y
¯
≤
−
M
size 12{b rSup { size 8{T} } {overline {y}} <= - M} {}
Nếu (P) có phương án khả thi là
x¯x¯ size 12{ {overline {x}} } {} thì theo định lý 1 ta có :
z
(
x
¯
)
=
c
T
x
¯
≤
w
(
y
¯
)
=
b
T
y
¯
<
−
M
z
(
x
¯
)
=
c
T
x
¯
≤
w
(
y
¯
)
=
b
T
y
¯
<
−
M
size 12{z \( {overline {x}} \) =c rSup { size 8{T} } {overline {x}} <= w \( {overline {y}} \) =b rSup { size 8{T} } {overline {y}} < - M} {}
Điều này dẫn đến mâu thuẩn
e- Định lý 5 (tính bổ sung )
Xét hai bài toán đối ngẫu
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
(
P
)
max z
(
x
)
=
c
T
x
Ax
=
b
x
≥
0
{
{
size 12{ \( P \) " "alignl { stack {
left lbrace "max z" \( x \) =c rSup { size 8{T} } "x " {} #
right none left lbrace "Ax"=" b " {} #
right none left lbrace x >= "0 " {} #
right no } } lbrace } {}
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
(
D
)
min w
(
y
)
=
b
T
y
A
T
y
≥
c
y tùy ý
{
{
size 12{ \( D \) " "alignl { stack {
left lbrace "min w" \( y \) =" b" rSup { size 8{T} } y {} #
right none left lbrace A rSup { size 8{T} } y >= "c " {} #
right none left lbrace "y tùy ý " {} #
right no } } lbrace } {}
x¯ , y¯x¯ , y¯ size 12{ {overline {x}} " , " {overline {y}} } {} là phương án khả thi tương ứng của (P) và (D).
Điều kiện cần và đủ để
x¯ , y¯x¯ , y¯ size 12{ {overline {x}} " , " {overline {y}} } {} cũng là phương án tối ưu là :
x
¯
T
(
A
T
y
¯
−
c
T
)
=
0
x
¯
T
(
A
T
y
¯
−
c
T
)
=
0
size 12{ {overline {x}} rSup { size 8{T} } \( A rSup { size 8{T} } {overline {y}} - c rSup { size 8{T} } \) =0} {}
Chứng minh
- Do
x¯x¯ size 12{ {overline {x}} } {} là phương án khả thi của (P) nên :
A
x
¯
=
b
⇒
(
A
x
¯
)
T
=
b
T
⇒
x
¯
T
A
T
=
b
T
⇒
x
¯
T
A
T
y
¯
=
b
T
y
¯
⇒
x
¯
T
A
T
y
¯
−
x
¯
T
c
=
b
T
y
¯
-c
T
x
¯
(
x
T
c
=
c
T
x
)
⇒
x
¯
T
(
A
T
y
¯
−
c
)
=
b
T
y
¯
-c
T
x
¯
(
∗
)
A
x
¯
=
b
⇒
(
A
x
¯
)
T
=
b
T
⇒
x
¯
T
A
T
=
b
T
⇒
x
¯
T
A
T
y
¯
=
b
T
y
¯
⇒
x
¯
T
A
T
y
¯
−
x
¯
T
c
=
b
T
y
¯
-c
T
x
¯
(
x
T
c
=
c
T
x
)
⇒
x
¯
T
(
A
T
y
¯
−
c
)
=
b
T
y
¯
-c
T
x
¯
(
∗
)
alignl { stack {
size 12{" "A {overline {x}} =b} {} #
size 12{ drarrow " " \( A {overline {x}} \) rSup { size 8{T} } =b rSup { size 8{T} } } {} #
drarrow " " {overline {x}} rSup { size 8{T} } A rSup { size 8{T} } =b rSup { size 8{T} } {} #
drarrow " " {overline {x}} rSup { size 8{T} } A rSup { size 8{T} } {overline {y}} =b rSup { size 8{T} } {overline {y}} {} #
drarrow " " {overline {x}} rSup { size 8{T} } A rSup { size 8{T} } {overline {y}} - {overline {x}} rSup { size 8{T} } c=b rSup { size 8{T} } {overline {y}} "-c" rSup { size 8{T} } {overline {x}} " " \( " x" rSup { size 8{T} } c=c rSup { size 8{T} } x \) {} #
drarrow " " {overline {x}} rSup { size 8{T} } \( A rSup { size 8{T} } {overline {y}} - c \) =b rSup { size 8{T} } {overline {y}} "-c" rSup { size 8{T} } {overline {x}} " " \( * \) {}
} } {}
- Theo kết quả (*) :
. Nếu
x¯ , y¯x¯ , y¯ size 12{ {overline {x}} " , " {overline {y}} } {} là phương án tối ưu của (P) và (D) thì theo định lý 4
cTx¯=bTy¯⇒cTx¯−bTy¯=0⇒x¯T(ATy¯−c)=0cTx¯=bTy¯⇒cTx¯−bTy¯=0⇒x¯T(ATy¯−c)=0alignl { stack {
size 12{" "c rSup { size 8{T} } {overline {x}} =b rSup { size 8{T} } {overline {y}} } {} #
drarrow " "c rSup { size 8{T} } {overline {x}} - b rSup { size 8{T} } {overline {y}} =0 {} #
drarrow " " {overline {x}} rSup { size 8{T} } \( A rSup { size 8{T} } {overline {y}} - c \) =0" " {}
} } {}
. Nếu
x¯T(ATy¯−c)=0⇒bTy¯−cTx¯=0⇒bTy¯=cTx¯x¯T(ATy¯−c)=0⇒bTy¯−cTx¯=0⇒bTy¯=cTx¯ size 12{ {overline {x}} rSup { size 8{T} } \( A rSup { size 8{T} } {overline {y}} - c \) =0 drarrow b rSup { size 8{T} } {overline {y}} - c rSup { size 8{T} } {overline {x}} =0 drarrow b rSup { size 8{T} } {overline {y}} =c rSup { size 8{T} } {overline {x}} } {}
Theo định lý 2 thì
x¯ , y¯x¯ , y¯ size 12{ {overline {x}} " , " {overline {y}} } {} là phương án tối ưu .
