Trịnh Anh Dũng Toán Kinh Tế 46
A. Mở đầu
Trong quản lý và phát triển nền kinh tế quốc dân ta luôn đụng chạm tới rất
nhiều mối quan hệ qua lại chằng chịt và quy định lẫn nhau một cách phức
tạp. Bên cạnh mặt chất lượng, những mối quan hệ ấy, ở những mức độ khác
nhau đều được thể hiện dưới dạng số lượng và điều đó cho phép sử dụng các
công cụ toán học để phân tích. Sự phát triển vũ bão của khoa học kỹ thuật,
sự cải tiến thường xuyên công nghệ và kết cấu sản xuất, sự ra đời của những
mặt hàng sản phẩm mới, sự phân công lao động sâu hơn và hợp tác trên
những quy mô lớn ngày càng làm cho các mối quan hệ đó tăng thêm mạnh
mẽ. Do đó, việc giải quyết các vấn đề nảy sinh trong công tác quản lý trở
nên hết sức phức tạp và khó khăn, tốn nhiều công sữc. Trong tình hình như
vậy, việc lựa chọn một giải quyết có căn cứ khoa học đòi hỏi phải thu nhập
và sử lý một khối lượng thông tin đồ sộ, tới mức nếu dùng những phương
pháp và công cụ quản lý cổ điển thì thời gian cần thiết trở nên quá lớn, vượt
xa khả năng thực tế của con người. Vì thế, để có thể lựa chọn được những
cách giải quyết các vấn đề nảy sinh trong quản lý tốt nhất theo một quan
điểm nào đó, những chiến lược hiệu quả nhất để đạt được các mục tiêu đã
đặt ra trong một giai đoạn nhất định, cần phải có những phương pháp, công
cụ mới, cho phép trong một khoảng thời gian chấp nhận được tìm ra giải
pháp thích đáng và có căn cứ. Từ nhu cầu của thực tế quản lý nảy sinh và
phát triển một ngành toán học mới: quy hoạch toán học, chuyên nghiên cứu
những bài toán hình thành trong lĩnh vực kinh tế, kỹ thuật và cơ sở lý luận
của những phương pháp giải chúng.
Đề án này khảo sát một bài toán quy hoạch lồi, định lý Kuhn-Tucker
và ứng dụng của định lý Kuhn-Tucker trong kinh tế.
Xin chân thành cảm ơn thầy Cao Xuân Hòa đã giúp tôi hoàn thành đề
án này!
1
Trịnh Anh Dũng Toán Kinh Tế 46
B.Quy Hoạch Lồi

1.Bài toán quy hoạch lồi tổng quát:
f(x) và g
i
(x) : hàm lồi, xác định trên tập lồi đóng D
∈
E
n
, khi đó bài toán quy
hoạch lồi tổng quát có dạng sau đây:
Tìm x = {x
1
, x
2
, …, x
n
} sao cho:
f(x)
→
min (1)
x
∈
D, g
i
(x)
≤
0 (i =
1,m
) (2)
Điểm x
*

nghiệm đúng (2) được gọi là phương án hay điểm chấp nhận được.
Nếu x
*
thoả mãn (1) và (2) thì nó là phương án tối ưu hoặc điểm tối ưu.
Tập phương án M = { x
∈
D, g
i
(x)
≤
0 (i =
1,m
) }
Nếu x
*
là cực tiểu địa phương của f(x) trên M thì nó cũng là cực tiểu tuyệt
đối của f(x) trên M, do đó để giải quy hoạch lồi người ta chỉ cần xây dựng
các thuật toán tìm cực tiểu địa phương là đủ.
2.Hướng chấp nhận được:
Với
X

∈
M, ta nói z
∈
E
n
là hướng chấp nhận được tại
X
nếu

∃
ε
>0 sao
cho
X
+
z
λ
∈
M
λ
∀ ∈
[0,
ε
].
Cũng có thể nói z là hướng chấp nhận được tại
X
nếu z =
ε
(x -
X
) trong
đó x là một điểm bất kỳ thuộc M, và
ε
> 0 bất kỳ.
Gọi M
x
là tập các phương chấp nhận được tại
X
. Khi đó M

x
sẽ là một nón
lồi. Thật vậy, dễ thấy nếu z
∈
M
x
thì
( 0)z M x
λ λ
∈ ∀ >
. Hơn nữa với z
1
, z
2
M x∈
thì z
1
+ z
2
cũng thuộc
M x
vì nếu z
1

M x∈
thì phải tồn tại
1
0
ε
>

để
2
2
X z M
ε
+ ∈
, lúc đó chỉ cần lấy
1 2
min( , )
ε ε ε
=
ta sẽ có:
1 2 2
1
( ) ( )
2 2
X z z X z M
ε
ε
+ + = + ∈
tức
1 2
z z M x+ ∈
Tiêu chuẩn tối ưu:
Định lý: Phương án
X
tối ưu khi và chỉ khi:
δ
f(
, ) 0x z z M x≥ ∀ ∈

Hệ quả: Nếu f(x) khả vi và
∇
f(
x
) – 0 vời
X M∈
thì
x
là tối ưu.
Thật vậy, khi ấy
δ
f
( ) ( )
, , 0x z f x z z≤ ∇ ∀ ≥ ⇒
tối ưu.
Điều kiện chính quy:
Tập phương án M của bài toán (1) và (2) thoả mãn điều kiện chính quy (hay
còn gọi là giả thiết Slater) nếu
0
x M∃ ∈ sao cho:
1)
0 0 0
(x D D∈
là miền trong của D)
2) g
i
(x
0
) < 0 với các g
i

phi tuyến thực sự
Một dạng khác của giả thiết chính quy là
0
x M∃ ∈ sao cho:
2
Trịnh Anh Dũng Toán Kinh Tế 46
1’) x
0
∈
D
2’)g
i
(x
0
) < 0 (
1,i m∀ =
)
Hàm Lagrange và điều kiện tối ưu:
Định nghĩa 1:
Hàm f(x, t) = f(x) +
1
( )
m
i i
i
t g x
=
∑
(3)
Xét trên miền x

∈
D, t
≥
0 được gọi là hàm Largrange của quy hoạch lồi (1)
(2)
Định nghĩa 2:
Cặp điểm (
,x t
) được gọi là điểm yên ngựa của hàm Largrange (3) trên miền
x
∈
D và t
≥
0 nếu
x D∈
,
0t ≥
và ta luôn luôn có:
F(
,x t
)
≤
F(
,x t
)
≤
F(
,x t
) (4)
, 0x D t∀ ∈ ∀ ≥

Định lý 1:
Nếu (
,x t
) là điểm yên ngựa của hàm F(x,t) trên miền x
∈
D, t
≥
0 thì:
x
= arg min f(x)
x
∈
M
Định lý 2 - Định lý Kuhn –Tucker:
Định lý 2a (Định lý Kuhn – Tucker):
Giả sử bài toán (1) (2) thoả mãn giả thiết Slater, khi ấy điều kiện cần và đủ
để một điểm
x
là phương án tối ưu của nó là:
0,
m
t t E∃ ≥ ∈
sao cho (
,x t
) là
điểm yên ngựa của hàm Largrange F(x,t) trên miền x
∈
D, t
≥
0.

Các chú ý:
Chú ý 1:
Từ (4) ta có:
Max
( , ) ( , ) min ( , )F x t F x t F x t≤ ≤
0,t x D≥ ∈
min [ max F(x,t) ]
≤
max [ min F(x,t) ]

x D∈

0t ≥

x D∈
t
≥
0
Đồng thời bất đăng thức ngược lại luôn luôn đúng với mọi hàm F(x,t) vì (
x D∀ ∈
) và
0t∀ ≥
ta luôn có:
max F(x,t)
≥
F(x,t)
≥
min F(x,t)
t
0≥

x
D∈
và từ đó: min [ max F(x,t) ]
≤
max [ min F(x,t) ]
x
D∈
t
0≥
x
∈
D t
0≥
Như vậy từ (4) ta có hệ thức tương đương sau:
min[max F(x,t) ] = F(
,x t
) = max[ min F(x,t) ] (4’)
Chú ý 2:
3
Trịnh Anh Dũng Toán Kinh Tế 46
Vế phải của (4’) có nghĩa là với t =
t
thì
( , ) min{F(x, ) / }F x t t x D= ∈
Vế trái của (4’) có ngihĩa là với
x x=
thì
( , ) ax{F( , ) / 0}F x t m x t t= ≥
Hay
1 1

, ( ) ax ( ) / 0
m m
i
i i i
i i
t g x m t g x t
= =
 
= ≥
 
 
∑ ∑
từ đó định lý Kuhn – Tucker được phát biểu lại như sau:
Định lý 2.b:
Mỗi điểm
x D∈
là phương án tối ưu của quy hoạch lồi (1) (2) khi và chỉ khi
∃
m
t E∈
.

0t ≥
sao cho:
a)
1
arg min ( ) ( ) /
m
i i
i

x f x t g x x D
=
 
= + ∈
 
 
∑
b)
1
arg min ( ) / 0
m
i i
i
t t g x t
=
 
= ≥
 
 
∑
Chú ý 3:
Ta thấy điều kiện b) trong định lý 3.2.b tương đương với:

1
( ) 0, ( ) 0( 1, )
m
i i i
i
t g x g x i m
=

= ≤ =
∑
Vì từ điều kiện này hiển nhiên có b), và ngược lại nếu có b) thì lập luận như
trong chứng minh định lý 2.2 ta có:

( ) 0( 1, )
i
g x i m≤ ∀ =
, từ đó
0t
∀ ≥
ta có
1
( ) 0
m
i i
i
t g x
=
≤
∑
và tổng này sẽ đạt cực
đại bằng 0 khi
0t =
tức là có
1
( ) 0
m
i i
i

t g x
=
=
∑
vì vậy định lý Kuhn – Tuker có thể được phát biểu lại như sau:
Định lý 2.c
Phương án
x
của quy hoạch lồi (1) (2) là tối ưu khi và chỉ khi
m
t E∃ ∈
,
0t ≥

sao cho:
a)
1
arg min ( ) ( ) /
m
i i
i
x f x t g x x D
=
 
= + ∈
 
 
∑
b)
1

( ) 0
m
i i
i
t g x
=
=
∑

Chú ý 4:
Xét trường hợp
n
D E≡
và các hàm
( )f x
,
( )g x
(
1,i m=
) điều khải vi, khi ấy
a) tương đương với
1
( )
( )
0
m
i
i
j j
g x

f x
t
x x
=
∂
∂
+ =
∂ ∂
∑
(
1,i m=
) . Vì vậy ta có:
Định lý 2.d:
4
Trịnh Anh Dũng Toán Kinh Tế 46
Phương án
x
của quy hoạch lồi (1) (2) là tối ưu khi và chỉ khi
m
t E∃ ∈
,
0t ≥

sao cho:
a)
1
( ) ( ) 0
m
i i
i

f x t g x
=
∇ + ∇ =
∑
b)
1
( ) 0
m
i i
i
t g x
=
=
∑
Chú ý 5:
Xét quy hoạch lồi:
( ) minf x →

( ) 0
i
g x =
(
1,i L=
)

( ) 0
i
g x ≤
(
1,i L m= +

)
Lúc đó:

( ) 0
i
g x ≤
( 0)
i
g x = ⇔

( ) 0
i
g x− ≤
Điều này xảy ra khi và chỉ khi
( )
i
g x
đang xét là afin. Khi áp dụng định lý
3.2 Hàm Lagrange cho bài toán này có dạng:
' ''
1 1
( , ) ( ) ( ) ( ) ( )
L m
i i i i i
i i L
F x t f x t t g x t g x
= = +
= + − +
∑ ∑
Trong đó:

'
0
i
t ≥
,
''
0
i
t ≥
(
1,i L=
)
0
i
t ≥
(
1,i L m= +
)
Nếu đặt
' "
i i i
t t t= −
(
1,i L=
) thì hàm Lagrange có dạng như cũ nhưng các
i
t
này
có dấu tuỳ ý.
3.Cách thiết lập điều kiện Kuhn – Tuker đối với một số bài toán kinh tế.

3.1. Phân tích hành vi của người tiêu dùng:
Vấn đề kinh tế: giả thết:
Người tiêu dùng có hàm lợi ích khả vi hai lần
1 2
( , )u x x
, trong đó
1
x
và
2
x
là
lượng hàng hoá 1 và 2 được người tiêu dùng, tiêu dùng tương ứng.
Người tiêu dùng có thu nhập được dùng để chi tiêu cho hai hàng hoá đó là
y
.
Giá của hàng hoá
i
là
i
p
.
Ta cũng giả thiết là người tiêu dùng hoặc mua hoặc không mua hàng hoá…
do đó
0x ≥
. Giả thiết người tiêu dùng cực đại lợi ích tiêu dùng.
5
Trịnh Anh Dũng Toán Kinh Tế 46
Bài toán


max ( )
x
u x

1 1 2 2
p x p x y+ ≤

1
0x ≥
,
2
0x ≥
3.1.1. Bước 1: Lập hàm Lagrange.
Hàm Lagrange của bài toán có dạng sau:

( ) ( )L u x y px
λ
= + −
3.1.2. Bước 2: Tìm các đạo hàm riêng cấp một của hàm Lagrange theo
các biến và các nhân tử Lagrange.
Đạo hàm của hàm Lagrange theo biến
i
x
ta được.

( )
0
i
i
u x

p
x
λ
∂
− ≤
∂
,
1,2,...,i n=
.
Đạo hàm của hàm Lagrange theo nhân tử Lagrange ta được

L
λ
∂
∂
* 0y px= − ≥
và điều kiện bù

[ ]
* 0
L
y px
λ λ
λ
∂
= − =
∂

0
λ

≥
;
* 0
i
x ≥

1,2,..., .i n=

3.1.3. Bước 3: Phân tích và rút ra kết luận từ kết quả thu được.
Như vậy nếu
* 0 : * 0
j k
x x> >

( )
0
i
i
u x
p
x
∂
− =
∂

,i j k=
nghĩa là người tiêu dùng
mua cả hai hàng hoá j và k thì chúng ta phải có:

( )

( )
j j
k k
u x p
u x p
=
Điều kiện này chỉ ra rằng nếu người tiêu dùng, tiêu dùng cả hai hàng hoá j
và k thì nhất định tỉ lệ lợi ích biên giữa hàng hoá phải bằng tỉ giá của hai
hàng hoá đó.
3.2. Phân tích hành vi của người tiêu dùng.
Với giả thiết không bão hoà địa phương ta có thể phát biểu lại bài toán cực
đại lợi ích dưới dạng sau:

1 1 2 2
max ( )u x
p x p x y+ =
Giả sử hàm lợi ích có dạng CES

1
1 2 1 2
( , ) ( )f x x x x
ρ ρ ρ
= +
và giả sử
0 1
ρ
≠ <
. Giải bài toán cực đại lợi ích của người tiêu dùng, ta có:
6