BÀI 3
(
(
)P
)P%
=
1. Cach thiêt lâp bai toan đôi ngâu: ́ ́ ̣ ̀ ́ ́ ̃
=
)
)
( f x
+ + ...
max
( % f y
+ + ...
min
c x 1 1
c x n n
b y 1 1
b y m m
=
(cid:0) (cid:0)
=
+ + ...
1,...,
m
1,...,
m
a x 1 1 i
a x in n
iy
(cid:0)�� �� b i , �� i ��= ��
(cid:0)� � 0 � � 0 i , � � � �� � tuy y
=
(cid:0) (cid:0)
+ + ...
,
j
1,...,
n
a y 1 ij
a y mj m
j
=
1,...,
n
jx
(cid:0)�� �� c �� ��= ��
(cid:0)� � 0 � � 0 j , � � � �� � tuy y
(cid:0) (cid:0)
)
( f y%
́ ́ ̣ ̀ ́ ́ ̃ (cid:0) (cid:0) (cid:0) ́ ̀
́ ̀ ̣ ́ ̀ ́ ̀ ̀ ́ ́
́ ̀ ́
́ ự ̣ ́ ̀ ̣ ̉ ̀ ́ ̀ ̀ ̣
̉ ̣ ̀ ̣ ̀ ́
̣ ̀ ̣ ̉ ̀ ́ ̀ ̉ ̣ ̉
ng ng v i ̀ ươ ứ ớ ̀ ̣ ̀ ́ ̉ ̀ ́
̀ ̣ ̀ ́ ̉ ̀ ́
́ ́ ̀ ̣ ̀ ́ ̀ ́ ̀ ̀
ng ng trong bai toan kia co dâu “=” ̣ ươ ứ ̀ ̀ ́ ́ ́
ứ ộ ệ ̀ ̣ ́ ̉
ủ ớ ̀ ́ ̀ ̀ ̀ ̣ ́ ̀
́
ứ ộ ệ ̀ ̣ ́ ̉
c chiêu v i rang buôc dâu trong ượ ủ ớ ̀ ́ ̀ ̀ ̣ ́
* Nguyên tăc thiêt lâp bai toan đôi ngâu: 1) Nêu f(x) min (max) thi max (min) 2) Sô rang buôc chinh trong bai toan nay băng sô biên sô trong bai toan kia 3) Hê sô trong ham muc tiêu cua bai toan nay la hê sô t do cua hê rang buôc trong bai toan kia. 4) Ma trân điêu kiên cua hai bai toan la chuyên vi cua nhau. 5) Rang buôc vê biên cua bai toan nay t rang buôc vê dâu cua bai toan kia. 6) Biên không co rang buôc vê dâu trong bai toan nay thi rang buôc t 7) Rang buôc bât đăng th c trong h ràng bu c chính c a bai toan min cung chiêu v i rang buôc dâu trong bai toan max 8) Rang buôc bât đăng th c trong h ràng bu c chính c a bai toan max ng bai toan min. ̀ ́
=
+
Vi du 1: vi ế t bài toán đ i ng u c a bài toán QHTT sau: ủ ố ẫ ́ ̣
)
x
min
( f x
2
4
3
6
4
+
(cid:0) - -
x 1 + 3
2
x 3 20
-
x 2 = x 4 7
x 1 3
x 4
x 2 + x 2
+
x 3 + x 7 3 +
x 1 +
- - (cid:0)
( ) 32 1 ) (
x
18
2
2
4
x 3
x 1
(cid:0)
x 1
(cid:0)
x 2
(cid:0)
x 4 2 ) ( 0 3 ( ) 0 4 ( ) 0 5
x 3
(cid:0)
=
+
+
)
(
)
% P
( % f y
:
20
32
y
18
max
(cid:0)
y 1 3
y
2 y 2 3
- (cid:0)
) )
y
4
+
+
- (cid:0) -
7
+ 2 + 2 y
y 3 ( 2 6 ( 3 7 ( ) 4 8
(cid:0)
2 y
7
6
y 3 y 3 = - y 3
+ 2
y 1 2y 1 3y 1 + y 1
y 1
-
y
2
(cid:0)
)
y
tuy y ( ) 0 9 ( 0 10
3
(cid:0)
2) Căp rang buôc đôi ngâu: ̣ ̀ ̣ ́ ̃
C p ràng bu c đ i ng u la căp rang buôc bât đăng th c ứ ố ộ ẫ ặ ̀ ̣ ̀ ̣ ́ ̉
(kê ca rang buôc dâu) trong hai bai toan cung t ươ ng ng ứ ̉ ̉ ̀ ̣ ́ ̀ ́ ̀
v i môt căp chi sô. ớ ̣ ̣ ̉ ́
Vi du: trong vi du 1 ta co căp rang buôc đôi ngâu la : (1), ́ ̣ ́ ̣ ́ ̣ ̀ ̣ ́ ̃ ̀
(9); (2), (10); (3), (6); (4), (7); (5), (8)
=
+
)
=
+
+
)
(
)
( f x
2
4
3
min
6
% P
( % f y
:
20
32
y
18
max
x 4
(cid:0) - - (cid:0)
+
y 1 3
y
x 1 + 3
2
x 3 20
2 y 2 3
- (cid:0) -
) )
y
4
x 2 = x 4 7
x 1 3
x 4
x 2 + x 2
+
+
- (cid:0) - - - (cid:0)
7
+ 2 + 2 y
y 3 ( 2 6 ( 3 7 ( ) 4 8
+
x 3 + x 7 3 +
x 1 +
( ) 32 1 ) (
18
2
2
x 4
x 3
x 1
(cid:0) (cid:0)
2 y
7
6
y 3 y 3 = - y 3
+ 2
y 1 2y 1 3y 1 + y 1
-
x 2 )
x 1
y 1
(cid:0)
x 2
(cid:0)
y
2
(cid:0)
4 ( 0 3 ) ( 0 4 ) ( 0 5
(cid:0)
)
y
tuy y ) ( 0 9 ( 0 10
3
tuy y
x 3 x 4
(cid:0)
́ ̣ ́ ̀ ́ ̃ ̃ ̀ ̀ ̣ ̀ ̣
+
=
+
+
Vi du 2: viêt bai toan đôi ngâu va tim các căp rang buôc đôi ngâu cua bai toan sau: ́ ̃ ̉ ̀ ́
)
10
max
( f x
15
12
x 4
x 2
+
+
+
(cid:0)
3
x 16 3 ( ) 20 1
+
+
+
=
x 4 2
x 4
x 1 x 2 1 +
+
x 1 x 3 x 3 3 +
(cid:0)
)
2
x 3
=
(cid:0)
20 ( 24 2 ( )
x 1 x
x 2 x 2 x 2 j
0,
x 2 4 ) ( 1,..., 4 3
6
j
(cid:0) (cid:0)
Ý nghĩa kinh t c a bài toán đ i ng u: ế ủ ố ẫ
+
=
Xét bài toán l p k ho ch s n xu t: ế ấ ậ ạ ả
)
max
( f x
c x 2 2
x c 1 1 +
(cid:0)
(cid:0) (cid:0)
+
(cid:0)
(cid:0) (cid:0)
(cid:0)
a x 11 1 a x 21 1 a x 31 1
b 1 b 2 b 3
(cid:0)
(cid:0)
a x 12 2 a x 22 2 a x 32 2 =
+ (
)
j
0
x
1, 2
j
(cid:0) (cid:0) (cid:0)
thi ả ườ i mu n mua toàn b s ộ ố ố
ế ng các y u t s n xu t c a xí nghi p. Khi đó giá ệ
t tình hu ng có ng Ta gi ố l ấ ủ ế ố ả ượ bán nên đ t ra là bao nhiêu? ặ
s n xu t ộ ơ ị ế ố ả ấ
(cid:0) G i yọ i (i = 1,2,3) là giá bán m t đ n v y u t lo i i. (y ạ
i 0)
s n xu t ượ ấ
c khi bán các y u t ế ố ả ẩ ị ả
+ +
Lo i 1:ạ
a y 11 1 a y 12 1
2
Lo i 2: ạ Ta có s ti n thu đ ố ề dùng đ s n xu t ra m t đ n v s n ph m ộ ơ ể ả + a y 31 3 + a y 32 3 ấ a y 21 2 a y 22
c 1
+
+
(cid:0) Đ i v i ng ố ớ + a y 11 1 ườ a y 21 2 i bán: + a y 31 3
a y 12 1
a y 22
2
a y 32 3
c 2
(cid:0)
ườ
b y 1 1
b y 2
2
b y 3 3 min
Đ i v i ng ố ớ + i mua: + (cid:0)
+
+
Mô hình:
+
(cid:0)
+
+
(cid:0)
b y 1 1 a y 11 1 a y 12 1
b y 3 3 min + a y 31 3 a y 32 3
c 1 c 2
(cid:0)
b y 2 2 a y 21 2 a y 22 2 = i 0 (
1,2,3)
iy
(cid:0)
+
+
+
max
(cid:0) (cid:0)
+
(cid:0) (cid:0) (cid:0)
+
(cid:0)
+
+
b y 1 1 a y 11 1 a y 12 1
b y 3 3 min + a y 31 3 a y 32 3
c 1 c 2
(cid:0) (cid:0) (cid:0)
(cid:0)
b y 2 2 a y 21 2 a y 22 2 = i 0 (
1,2,3)
x c 1 1 a x 11 1 a x 21 1 a x 31 1
b 1 b 2 b 3
iy
(cid:0) (cid:0) (cid:0)
c x 2 2 + a x 12 2 a x 22 2 a x 32 2 =
+ (
)
x
0
j
1, 2
j
(cid:0) (cid:0) (cid:0)
(
3) Cac đinh ly đôi ngâu: ́ ̣ ́ ́ ̃
)P%
Đinh ly 1: Cho hai bai toan đôi ngâu (P) va . Khi đo ̣ ́ ̀ ́ ́ ̃ ̀ ́
ng h p: ợ ườ ̉
̉ ̀ ́
xay ra ba tr Ca hai đêu không co PA. Ca hai đêu co PA. Khi đo ca hai đêu giai đ c. ̉ ượ ̉ ̀ ́ ́ ̉ ̀
Căp x* va y* la tôi u ́ ư f(x*) = g(y*) ̣ ̀ ̀
Môt bai toan co PA, bai toan con lai không co ̣ ̀ ́ ́ ̀ ́ ̀ ̣ ́
PA. Khi đo ham muc tiêu cua bai toan co PA ́ ̀ ̣ ̉ ̀ ́ ́
không bi chăn trên tâp cac PA, do đo bai toan ̣ ̣ ̣ ́ ́ ̀ ́
nay không co PAT . Ư ̀ ́
* Hê qua : Nêu môt trong hai bai toan co PAT thi bai Ư ̀ ̣ ̉ ́ ̣ ̀ ́ ́ ̀
toan kia cung co PAT . Ư ́ ̃ ́
3) Cac đinh ly đôi ngâu: ́ ̣ ́ ́ ̃
̣ ́ ̣ ̣ ̀ ́
ng an cua hai bai toan. Khi đo x ươ ̀ ̀ ́ ̉ ̀ ́ ́
ng an tôi u cua hai bai toan ́ nêu ươ ́ ư ̀ ̀ ́ ̉ ̀ ́
̣ ̀ ̣ ́ ̃ ̀ ̣ ̉ ̀ ́
Đinh ly 2 : (đô lêch bu yêu) Cho x va y la hai ph va y la hai ph trong căp rang buôc đôi ngâu rang buôc cua bai toan nay la long thi rang buôc đôi ngâu cua no la chăt. ̀ ̀ ̉ ̀ ̀ ̣ ́ ̃ ̉ ́ ̀ ̣
x
c
0
j
a y i ij
j
- (cid:0)
0
y i
a x ij
j
b i
m � � = � 1 i n � � = j 1 �
� = � � � = � �
- (cid:0)
́ ớ ̣ ̉ ́ ̣ ̣ ̀ ̣ ̀ ̉
̉ ̀ ́ ̀ ̀ ̀ ̣ ́ ̃ ̉ ́ ̉ ̀
Hê qua: Nêu môt căp rang buôc la long đôi v i PAT Ư cua bai toan nay thi rang buôc đôi ngâu cua no phai la chăt v i PAT cua bai toan kia. Ư ̉ ̣ ớ ̀ ́
4) ng dung cua bai toan đôi ngâu: Ứ ̣ ̉ ̀ ́ ́ ̃
=
+
+
+
Vi du 3: Cho bai toan QHTT: ́ ̣ ̀ ́
)
min
( f x
2
5
4
x 4
(cid:0)
6
x 1 2
x
x 3 32
x 1
x 2
4
x 2 = 9 x 5 3
1
+
+
+
=
2
30
x
5
x 3
x 2
2
+
- - -
3
36
x 42 ( ) 1
x 2
=
(cid:0)
x 5 j
0,
x
1,...,5(2)
(6)
j
(cid:0) (cid:0)
a) Hay giai bai toan băng ph ng phap đ n hinh ươ ơ ̃ ̉ ̀ ́ ̀ ́ ̀
b) Viêt bai toan đôi ngâu ́ ̀ ́ ́ ̃
c) Tim ph ng an tôi u cua bai toan đôi ngâu ươ ́ ư ̀ ́ ̉ ̀ ́ ́ ̃
+
=
+
́ ́
max
( % f y
32
30
36
y
y 3
y 1
(cid:0) a) Đap sô: x* = (32,0,30,0,0) f(x*) = 184 b) )
2 2(7)
+
+
(cid:0)
2
y
3
5(8)
y 3
2
y 1 -6y 1
(cid:0)
y
4(9)
2
1
(cid:0)
1(10)
3
+ 2y 1 +
y 22 +
- (cid:0)
y
0(11)
2
-9y 1
y 3
2
y 1
(cid:0)
)
y
,y tuy y 2 ( 12 0
3
(cid:0)
c) x* = (32,0,30,0,0)
(cid:0) x1 = 32 0: y1 = 2
(cid:0)
x3 = 30 0: y2 = 4
Ta co rang buôc (*) va (**) la căp rang buôc ́ ̀ ̣ ̀ ̀ ̣ ̀ ̣
đôi ngâu ma x* thoa long rang buôc (*) => ở ́ ̃ ̀ ̉ ̉ ̀ ̣
y* thoa chăt rang buôc (**) => y3 = 0 ̣ ở ̉ ̀ ̣
̣
184
Vây y* = (2,4,0) )* ( % f y =
Vi du 4: ́ ̣
a) Giai bai toan vi du 2 băng ph ng phap đ n hinh ́ ở ươ ơ ̉ ̀ ́ ̣ ̀ ́ ̀
b) Viêt bai toan đôi ngâu va cac căp rang buôc đ i ng u. ố ẫ ́ ̀ ́ ́ ̃ ̀ ́ ̣ ̀ ̣
c) Tim PAT cua bai toan đôi ngâu. Ư ̉ ̀ ̀ ́ ́ ̃
Giai: ̉
a) Đap sô: x* = (0,4,0,8) ́ ́
fmax = f(x*) = 128
=
+
+
)
( % f y
20
20
y
24
y 1
y 3
+
+
b) (cid:0)
2 y
2
+
2 +
(cid:0)
y
2
2
y 3 y 3
+
y 1 3y 1 +
(cid:0)
3
y
2
y 1 +
(cid:0)
)
min ( ) 15 7 ) ( 12 8 ) ( 16 9 ( 10 10
2
2
y 3 y 3
(cid:0)
+ y 2 ( ) 0 11
y 1 y 1 y
2
(cid:0)
y
tuy y ( ) 0 12
3
(cid:0)
Cac căp rang buôc đôi ngâu: ́ ̣ ̀ ̣ ́ ̃
(1),(11); (2),(12); (3),(7); (4),(8); (5),(9); (6),(10)
+
+
=
= (cid:0) 4
y
2
12
+
=
+
c)
0 : 3y 1 y 2
y 3 10
2 2
4
2
(cid:0)
y 3 18 4
y 3
y 3
,
* =� y
y , 3
5
5
x 2 x =8 0:y 1 14 2 � � �
� � �
- -
18 4
*
y 3
y 3
=
(cid:0) - - V y:ậ
,
y
y , 3
5
5
(cid:0)
� � �
(cid:0)
14 2 � � � 5
y 3
=
128
* % f y
(cid:0) (cid:0) - (cid:0)
(
)
̉ : 5) Môt sô dang bai toan c ban ơ ̣ ́ ̣ ̀ ́
(
Bai toan 1: Nêu x* la PAT cua bai toan (P). Tim toan ̀ ́ ́ ̀ ̀ ́ ̀ ̀
Ư ̉ )P% bô PAT cua bai toan . Ư ̉ ̣ ̀ ́
Ph ng phap giai: S dung đinh ly đô lêch bu yêu. ươ ử ́ ̉ ̣ ̣ ́ ̣ ̣ ̀ ́
Bai toan 2: Tim PAT cua bai toan (P). Ư ̉ ̀ ́ ̀ ̀ ́
Ph ng phap giai: ươ Giai bai toan đôi ngâu sau đo s ́ ử ́ ̉ ̉ ̀ ́ ́ ̃
dung đinh ly đô lêch bu yêu tim PAT cua bai toan (P). Ư ̉ ̣ ̣ ́ ̣ ̣ ̀ ́ ̀ ̀ ́
=
+
+
Vi du: Gi i bài toán QHTT sau: ́ ̣
52
60
36
min
( f x
x 1
x 2
x 3
(cid:0) ả )
2(1)
+
+
(cid:0) -
4
3
6(2)
x 2
x 3
x 1 x 2 1
+
(cid:0)
4(3)
4
2
x 1
(cid:0)
x 2 2(4)
(cid:0) -
3(5)
=
x 2 x 3 x
tuy y,
j
1, 2,3
j
(cid:0)
34
22
0,
,
,0, 2
Giai:̉ Chuyên sang gi i bai toan đôi ngâu: ả ̉ ̀ ́ ́ ̃
)
(
3
3
*
310
=
% f y
* y = (
)
3
34
=
+
+
=
y
0 : 2
4
3
6
2
x 1
x 2
x 3
3
22
+
=
=
(cid:0) Ta có:
0 : 4
4
2
x 2
=
x 1 3
= (cid:0) 2
3 0 :
(cid:0)
5
,3
-
)
(
3
x 3 11 , 6
310
* f x
y 3 y 5 * =� x ) (
3
=
Bai toan 3 : Cho bât ky x*. Hoi x* co phai la PAT . Ư ̀ ́ ́ ̀ ̉ ́ ̉ ̀
Ph ng phap giai: ươ ́ ̉
( f y%
)*
T x* s dung đinh ly đô lêch bu yêu ta giai tim y* ử ừ ̣ ̣ ́ ̣ ̣ ̀ ́ ̉ ̀
Nêu co nghiêm y* và f(x
*) = thi x* la PAT
Ư ́ ́ ̣ ̀ ̀
Nêu không co nghiêm y* thi x* không la PAT . Ư ́ ́ ̣ ̀ ̀
i bài toán QHTT sau đây b ng cách gi i bài toán đ i ằ ả ố
+
+
=
Gi ng u và dùng đ nh lý đ l ch bù y u: ộ ệ ả ẫ ế ị
)
9
min
( f x
8
6
x 3
x 1 +
(cid:0)
3
x 2 12
x 3
x 2 +
(cid:0)
2
15
+ 21 x + x 2
x 3
+
+
(cid:0)
3
18
+
+
(cid:0)
16
x 1 x 1 x 2 1
x 2 x 2
x 3 x 3 3
*
7
3
11
=
)
y
;
;
(cid:0)
*
2 9
10 9
10 57
( ( -=
;0 )
x
;
;
10
10
=
=
f
min
% f m ax
2 711 10
Đáp s :ố
Gi i bài toán QHTT sau đây b ng ph ng pháp đ n ả ằ ươ ơ
hình. Vi t bài toán đ i ng u và tìm PAT c a bài toán ế Ư ủ ố ẫ
=
+
+
+
đ i ng u b ng cách s d ng đ nh lý đ l ch bù y u. ử ụ ộ ệ ố ế ẫ ị
( f x
6
5
m
4
3
ax
x 4
x 1 +
(cid:0) ằ )
3
x 3 15
x 2 + x 4
+
=
x 2 +
2
3
10
x 4
x 3 x 3
+ 21 x + 2 x 2
+
+
+
(cid:0)
2
12
x 4
x 3
x 1 x 2 1
=
(cid:0)
x 2 (
)
x
j
0
1,4
j
*
*
7
9
=
=
=
=
(
(cid:0)
(
x
y
) ; 0 ;
;
f
39
m ax
% f min
5
5
) 4;0;3;0 ;
Đs:
