Bài toán giải thuật đơn hình

Chia sẻ: nvcuong198

Tài liệu tham khảo lập trình - Bài toán giải thuật đơn hình

Nội dung Text: Bài toán giải thuật đơn hình

Bài 1:
D ng bài toán QHTT
* D ng t ng quát
n
(1) f (x) = ∑ c j x j → min(max)
j=1

n
 ∑ a ij x j = bi , i ∈ I1
 j=1
n

(2) ∑ a ij x j ≤ bi , i ∈ I 2
 j=1
n
 ∑ a ij x j ≥ bi , i ∈ I3
 j=1

(3) x j ≥ 0 j ∈ J1 , x j ≤ 0 j ∈ J 2 , x j tu`y y ' j ∈ J 3
Trong ó
- f(x) là hàm m c tiêu
- I1 , I2 , I3 là r i nhau và I1 U I2 U I3 ={1,2, …,m}
- J1 , J2 , J3 là r i nhau và J1 U J2 U J3 = {1,2,…,n}
- A= (aij)mxn : Ma tr n h s ràng bu c
- B= (b1 , b2, …, bm): Vectơ các h s t do
- C= (c1 , c2, …,cm): Vectơ các h s n trong hàm m c tiêu
- X=(x1, x2, …,xn): Vectơ các n s
* D ng chính t c
n
(1) f (x) = ∑ c j x j → min(max)
j=1
n

∑a x = bi , i = 1..m
(2) ij j
j=1

(3) x j ≥ 0 j = 1..n
* D ng chu n
n
(1) f (x) = ∑ c j x j → min(max)
j=1
n

∑a x = bi , i = 1..m
(2) ij j
j=1

(3) x j ≥ 0 j = 1..n
Trong ó :
- Các h s t do b1, b2, …, bm u không âm.
m vectơ c t ơn v e1, e2, …,em:
- Trong ma tr n h s ràng bu c A = (aij)mxn có y
1 0 0
  
0 1 0
e1 =   ;e 2 =   ;...; em =  
 ...   ...   ... 
  
0 0 1

D ng t ng quát D ng chính t c D ng chu n




Ths c 0972 670 808 1 onthicaohoc_toankinhte@yahoo.com
Bài 2: Phương pháp ơn hình
Bư c 1: L p b ng ơn hình xu t phát
* Xác nh pacb ban u xu t phát: x = (x1 , x 2 ,..., x n ) . Là phương án có các n không cơ b n u là s
0, n cơ b n có giá tr b ng các h s t do
* Xác nh J(x) = { j/ x j > 0}
n cơ b n {x j j ∈ J(x)}
* Xác nh h
* L p b ng ơn hình xu t phát sau:
c1 c2 … cn λj
n cơ b n Phương án
Hs
x1 x2 … xn


xj cj bj zj1 zj2 … zjn λ jn



f …
∆1 ∆2 ∆n


∑ cx
Trong ó: f = = f (x) : giá tr hàm m c tiêu tương ng v i x (f = c t H s * c t Phương án)
j j
j∈J(x )

∑ cz − c k : h s ư c lư ng c a bi n xk, k=1..n ( ∆ k = c t H s *c t zjk –ck)
∆k = j jk
j∈J(x )

Lưu ý: ∆ k = 0, k ∈ J(x) ( ng v i các n cơ b n).
f (x) = x1 − 2x 2 + 2x 3 − x 4 + x 5 − 2x 6 → min
 2x1 − x 2 − 5x 3 + x 4 = 5

 x1 − 2x 2 + 2x 3 + x 5 = 4
−4x + x + x + x = 2
 1 2 3 6

x j ≥ 0, j = 1..6
Gi i :
Ta có: c= (1,-2,2,-1,1,-2)
Các bi n cơ b n là x4, x5, x6
Các bi n không cơ b n: x1, x2, x3
x=(0,0,0,5,4,2), J(x)= {4,5,6}
 2 −1 −5 1 0 0 
A =  1 −2 2 0 1 0 
 
 −4 1 1 0 0 1 
 
2  −1  −5  1 0 0
 1  , A =  2  , A =  2  . Tương t cho các bi n cơ b n A =  0  , A =  1  , A =  0 
A1 =   2   3    5  6 
4
 −4  1 1 0  
0 1
   




Ths c 0972 670 808 2 onthicaohoc_toankinhte@yahoo.com
n cơ Hs PA 1 -2 2 -1 1 -2
bn x1 x2 x3 x4 x5 x6
cj
2
x4 -1 5 -1 -5 1 0 0
x5 1 4 1 -2 2 0 1 0
x6 -2 2 -4 1 1 0 0 1
(6)
-5 -1 3 0 0 0
Bư c 2: Xét d u hi u t i ưu
* Xem dòng ghi ∆1 , ∆ 2 ,..., ∆ n
- N u có ∆ k ≤ 0, ∀k : phương án ang xét là PATU. Thu t toán k t thúc
- N u không: bư c 3
Bư c 3: Xét d u hi u không t i ưu
* Xét xem có c t ∆ k sao cho ∆ k > 0 và m i ph n t thu c c t này ( bư c l p ang xét ) u ≤ 0
không?.
- N u có : BT không có PATU. Thu t toán k t thúc
- N u không bư c 4
Bư c 4: C i ti n PA ( Tìm pacb t t hơn)
Tìm pacb x ' = (x '1 , x '2 ,..., x 'n ) t t hơn pacb x: f(x’) 0} . Ch n c t có ∆ k dương l n nh t . Khi ó xv là n mà ta s ưa
vào h n cơ b n.
b) Ch n n ưa ra kh i h n cơ b n
 b j  
 
b
Ch n λ r = r = min   j ∈ J(x) và z jv > 0  . Khi ó n xr là n ưa ra kh i h cơ b n.
z 
z rv  jv  
 
Bư c 5: Tìm ph n t ch t
Ph n t ch t là ph n t giao gi a n ưa vào và n ưa ra: zrv
Bư c 6: Bi n i b ng
• Trong c t n cơ b n ta thay xr b ng xv. Trong c t h s ta thay cr b ng cv.
h
• Dùng phép bi n i h r = r : nghĩa là hàng r m i = hàng r cũ /ph n t ch t.
z rv
• V i các hàng i ≠ r ta dùng phép bi n i:
z jv * z rk
z 'jk = z jk −
z rv
 z rk   z rv Ph n t ch t
chia
  
  
  nhân 
  
 z jk ?   z jv 
  

zrv
zrv




zrv
Bư c 7: Quay v bư c 2 zrv

Ths c 0972 670 808 3 onthicaohoc_toankinhte@yahoo.com
*Lưu ý: Quy t c ch s bé nh t c a R.G.Bland
*Trong các c t có ∆ dương thì ta ch n c t có ch s nh nh t
* N u có nhi u λ r ch n thì ch n dòng có ch s nh nh t.

Bài 5: Bài toán i ng u
1. Quy t c thành l p bài toán i ng u
* Hàm m c tiêu c a Bài toán (BT) g c → min(max) ⇔ Hàm m c tiêu c a BT i ng u → min(max)
* H s c a hàm m c tiêu c a BT g c là h s v ph i c a ràng bu c chung c a BT i ng u.
H s v ph i c a ràng bu c chung c a BT g c là h s c a hàm m c tiêu c a BT i ng u
* Ma tr n h s c a BT g c l y chuy n v thành ma tr n h s c a BT i ng u.
* S ràng bu c chung c a BT g c là s bi n c a BT i ng u
*Quy t c v d u như sau:
D u m t ràng bu c chung c a bài toán g c quy nh d u c a m t ràng bu c bi n tương ng cùa BT i
ng u
D u m t ràng bu c bi n c a BT g c quy nh d u c a m t ràng bu c chung tương ng c a BT i
ng u.




Cách nh :
Bài toán g c min: ràng bu c chung cùng d u, ràng bu c bi n trái d u.
Bài toán g c max: ràng bu c chung trái d u, ràng bu c bi n cùng d u.
Ví d :
f (x) = x1 − 2x 2 + 3x 4 → min BT DN g(y) = 7y1 + y 2 − 2y3 → max
 x1 + 3x 2 + 4x 3 + x 4 ≥ 7  y1 + 0y 2 + 5y3 ≤ 1
 − x + 2x + 6x ≤ 1 3y − y + 5y ≥ −2
 1
2 3 4 2 3
  , y1 ≥ 0, y 2 ≤ 0, y3 tùy ý
5x1 + 5x 2 + x 3 + 8x 4 = −2 4y1 + 2y 2 + y3 = 0
 
 x1 ≥ 0, x 2 ≤ 0, x 3 , x 4 tùy ý  y1 + 6y 2 + 8y3 = 3
 
 1 0 5
1 3 4 1  
3 −1 5 
 
AT = 
A =  0 −1 2 6 
 4 2 1
5 5 1 8
 
 
 1 6 8

Ths c 0972 670 808 4 onthicaohoc_toankinhte@yahoo.com
2. Cách tìm PATU c a BT i ng u
* T PATU c a Bài Toán g c (BT i ng u) x ' = (x '1 , x '2 ,..., x 'n ) ( hoac y ' = (y '1 , y '2 ,..., y 'n ) ) ta th
vào các ràng bu c chung c a BT g c ( BT i ng u).
* Ki m tra xem trong các ràng bu c chung BT g c n u ràng bu c nào không x y ra d u ‘=’ thì n
tương ng trong BT i ng u s ‘=0’
* Ngư c l i n u trong PA x ' = (x '1 , x '2 ,..., x 'n ) c a BT g c, giá tr x i' > 0 thì phương trình th i trong
BT i ng u s x y ra d u ‘=’.




Ths c 0972 670 808 5 onthicaohoc_toankinhte@yahoo.com
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản