Bài giảng môn học Toán kinh tế

ộc này thoả món 0 (Ak,y( )) = (Ak, y0) +  ( Ak, wr ) = ),( 0 r j Jj jkkk wAxc     =       ),( 0 r j Jj jkkk wAxc  = rkkk xc  Do đú để y( ) là phương ỏn chỉ cần: rkkk xc  kc (kJ0), tức là: 0 rkk x (kJ0) 4.Thuật toán của phương pháp đơn hình đối ngẫu Giả sử bài toỏn đối ngẫu khụng suy biờn và yo là phương ỏn cực biờn của bài toỏn đối ngẫu ứng với cơ sở Jo. Giả sử đó biết phương ỏn cực biờn y của bài toỏn đối ngẫu của bài toỏn dạng chớnh tắc ,cơ sở j.Thành lập bảng đơn hỡnh tương ứng ,chỳ ý là :  jkk  0 .Núi một cỏch khỏc là đó biết một cơ sở j của bài toỏn dạng chớnh tắc mà  jkk  0 .Thuật toỏn được thực hiện cho cỏc bước sau : 1)kiểm tra dấu hiệu tối ưu -Nếu 0jx - mọi thành phần cơ sở của giả phương ỏn đều khụng õm - thỡ giả phương ỏn x là phương ỏn cực biờn tối ưu .Nếu 0 jx với Jj . 43 2)Kiểm tra tớnh khụng giải được của bài toỏn -Nếu 0 jx với Jj mà )(0 jkx jk  thỡ bài toỏn đối ngẫu khụng giả được vỡ trị số của hàm  yf~ khụng bị chặn trờn tập phương ỏn,do đú bài toỏn gốc khụng cú phương ỏn .Nếu ứng với mỗi xj<0 đều cú ớt nhất 1 xjk<03-Chọn vộctơ loại khỏi và xỏc định vộctơ đưa vào cơ sở : 4-Biến đổi bảng Bước 1 : Kiểm tra dấu hiệu tối ưu Nếu mọi thành phần cơ sở của giả phương ỏn x đều khụng õm thỡ giả phương ỏn x trở thành phương ỏn và là phương ỏn cực biờn tối ưu của bài toỏn gốc đồng thời phương ỏn cực biờn y tương ứng bờn bài toỏn đối ngẫu cũng tối ưu. Bước 2 : Kiểm tra tớnh khụng giải được của bài toỏn Nếu tồn tại xj0 <0 đồng thời mọi xjk ≥ 0 thỡ bài toỏn đối ngẫu khụng giải được lỳc đú bài gốc khụng cú phương ỏn. Trong trường hợp ngược lại chuyển bước 3 Bước 3 : Cải tiến phương ỏn Nếu tồn tại xj0 <0 đồng thời tồn tại xjk < 0 thỡ cải tiờn phương ỏn như sau: Giả sử min(xj0 <0 ) = xr0 <0 thỡ vộc tơ Ar bị loại khỏi cơ sở Xột bước đi θo = Min(∆k/Xrk0) Xrk0< 0, Giả sử r đạt tại chỉ số r = s lỳc này θo = Min(∆k/Xsk0) Xsk0< 0, như vậy vộc tơ được đua vào cơ sở là vộc tơ Ar . Thực hiện cỏc phộp biến đổi sơ cấp , tương đương ta thu được giả phương ỏn mới tương đối tốt hơn ứng với cơ sở mới. Bước 4 : Biến đổi bảng: Thực hiện cỏc phộp biến đổi sơ cấp , tương đương ta thu được giả phương ỏn mới tương đối tốt hơn ứng với cơ sở mới. sau đú lại quay lại chu trỡnh của thuật toỏn sau hưu hạn bước sộ kết luận bài toỏn 5.Các chú ý khi áp dụng thuật toán Cỏc chỳ ý khi thực hiện thuật toỏn -Đối với bài toỏn cú max)( xf ,cú thể giải trực tiếp với dấu hiệu cơ sở đối ngẫu tương ứng là cơ sở mà  jkk  0 ,do đú 0 tớnh theo cụng thức : rkkx X jk /{-min 00    },cỏc yếu tố khỏc của thuật toỏn khụng đổi ,hoặc cú thể chuyển về giải bbài toỏn với hàm     min xfxg ,cần chỳ ý là fmax=-gmin -Về nguyờn tắc cú thể loại khỏi cơ sở bất kỡ vộctơ nào ứng với xj<0 cũngđều cải tiến được phương ỏn của bài toỏn đối ngẫu . 44 - Trường hợp bài toỏn đối ngẫu suy biến thỡ 0 cú thể bằng 0.khi 00  ,vẫn thực hiện thuật toỏn một cỏch bỡnh thường ,nghĩa là vẻcơ ứng với 0 vẫn được đưa vào cơ sở . Tuy nhiờn kết quả tớnh toỏn trong trường hợp này chỉ cho ta bảng đơn hỡnh ứng với một cơ sở khỏc ,do đú giả phương ỏn khỏc ,của cựng một phương ỏn cực biờn suy biến của bài toỏn đối ngẫu .Trờn bảng đơn hỡnh hàng ước lượng k khụng đổi . - Dấu hiệu suất hiện phương ỏn cực biờn suy biến của bài toỏn đối ngẫu là 0 đạt tại nhiều chỉ số , khi đú sẽ chọn vectơ đưa vào cơ sở là một trong số những vecto ứng với 0 theo quy tắc ngẫu nhiờn . -Nếu *j là cơ sở ứng với phương ỏn cực biờn tối ưu thỡ phương ỏn tối ưu y* được xỏc định bởi hệ phương trỡnh : (Aj,y)=cj(j *)J .Trường hợp đặc biệt nếu cú vộcto điều kiện ik cA  thỡ kki cy  * điều này làm đơn giản quỏ trỡnh giải hệ phương trỡnh trờn f(X)= x1+3x2 +2x3+3x4 +5x5→min. x1 + 2x2 - x3 + x4 - x5 = -3 -x2 - x3 + 2x4 +4x5 -x6 =18 - x2 - 3x3 +2 x5 + x7 = 10 xj ≥ 0 (j = 1,7) cJ J xJ 1 3 2 3 5 0 0 x1 x2 x3 x4 x5 x6 x7 x1 x6 x7 -3 -18 10 1 2 -1 1 -1 0 0 0 1 1 [-2] -4 1 0 0 -1 -3 0 2 0 1 1 0 0 f~ (y) -3 0 -1 -3 -2 -6 0 0 x 1 x4 x7 -12 9 10 1 5/2 -1/2 0 [-3] 1/2 0 0 -1/2 -1/2 1 2 -1/2 0 0 -1 -3 0 2 0 1 1 3 0 f~ (y) 15 0 -2 -4 0 -2 -1 0 45 x5 x4 x7 4 1 2 -1/3 -5/6 1/6 0 1 -1/6 0 2/3 7/6 5/6 1 0 -1/6 0 2/3 2/3 -10/3 0 0 1/3 1 5 3 0 f~ (y) 23 -2/3 -11/3 -11/3 0 0 -4/3 0 -Tỡm cơ sở đối ngẫu (giả đối ngẫu )xuất phỏt a) trường hợp đặc biệt bài toỏn cú dạng :      n j jj xcxF 1 min       n j ijij mibxa 1 1  njx j  10 trong đú  njc j  10 Đưa bài toỏn về dạng chớnh tắc ,cỏc vộctơ điều kiện ứng với cỏc biến phụ tạo thành cơ sở E ,lập bảng đơn hỡnh ,dễ thấy  nkckk  10 đú là cơ sở đối ngẫu ỏp dụng được thuật toỏn . b)Bài toỏn dạng chớnh tắc ,biết được cơ sở J khụng phải cơ sở đối ngẫu ,nghĩa là 0 k .Xõy dựng bài toỏn mở rộng (M) bằng cỏch thờm vào một ràng buộc gỉa với vế trỏi là tổng cỏc biến phi cơ sở nhỏ thua hoặc bằng một hằng số dương tuỳ ý M.Cộng biến phụ x0 vào ràng buộc này để đưa bài toỏn về dạng chớnh tắc .Giải bài toỏn M bằng thuật toỏn đơn hỡnh đối ngẫu sẽ gặp cỏc trường hợp : -Xuất hiện dấu hiệu bài toỏn M khụng cú phương ỏn thỡ bài toỏn xuất phỏt cũng khụng cú phương ỏn -Tỡm được cơ sở đối ngẫu của bài toỏn M cú dạng {0} JJ nghĩa là vectơ 0A ,nằm trong cơ sở .Khi đú J chớnh là cơ sở đối ngẫu của bài toỏn xuất phỏt .Để cú bảng đơn hỡnh tương ứng chỉ cần bỏ hàng và cột ứng với x0 .sau đú tiếp tục thuật toỏn giải bằng toỏn xuất phỏt . -Tỡm được phương ỏn cực biờn tối ưu của bài toỏn M với 0A là vecto phi cơ sở .Khi đú cỏc thành phần cơ sở của phương ỏn cực biờn tối ưu phụ thuộc M: Nếu trị tối ưu của hàm mục tiờu phụ thuộc M ,hệ số của M phải là số õm vỡ nú bằng 00  thỡ bài toỏn khụng giải được vỡ trị số hàm mục tiờu khụng bị chặn . Nếu trị tối ưu của hàm mục tiờu khụng phụ thuộc M ,nghĩa là 00  thỡ đưa 0A vào cơ sở theo thuật toỏn đơn hỡnh ta sẽ được một phương ỏn cực biờn tối ưu khỏc của bài toỏn M .Vỡ 0A nằm trong cơ sở nờn bỏ hàng và cột ứng với x0 sẽ được bản đơn hỡnh ứng với cơ sở tối ưu của bài toỏn xuất phỏt .Tuy nhiờn trường hợp này sẽ khụng xảy ra nếu khi thực hiện thuật toỏn ta luụn ưu tiờn đưa vectơ 0A vào cơ sở khi nú ứng với 0 . - Đặc điểm tớnh toỏn khi giải bài toỏn M Vỡ thành phần cơ sở của giả phương ỏn phụ thuộc M nờn trong bảng đơn hỡnh cột phương ỏn chia làm hai : Một cột ghi phần phụ thuộc M ,một cột ghi hệ số của M trong thành phần cơ sở .Khi hệ số của M khỏc 0 thỡ dấu của nú chớnh là 46 dấu của thành phần cơ sở .Chỳ ý rằng cột hệ số của M hoàn toàn trựng với cột 0, 00 cx ,nờn 0 trựng với hệ số của M trong  yf Vỡ vậy để đơn giản trong bảng cú thể dựng chớnh cột này làm cột x0. 47 Chương III: Bài toán vận tải I.Nội dung và đặc điểm 1.Nội dung kinh tế và dạng toán học Nội dung bài toỏn. Giả sử trờn một khu vực địa lý ,tại một thời điểm nhất định cú m nơi sản xuất ( kho) một loại hàng hoỏ thuần nhất .Ký hiệu nơi sản xuất i là Ai và gọi là trạmphỏt Ai mi  1 ; lượng hàng hiện cú ở Ai là ai .Đồng thời cú n nơi tiờu thụ loại hàng hoỏ đú .Ký hiệu nơi tiờu thụ j là Bj và gọi là trạm thu  1jB j n  ; yờu cầu của trạm thu Bj là bj .Để thuận tiện từ đõy ta sẽ gọi ai và bj là yờu cầu của cỏctrạm phỏt và thu .Chi phớ vận chuyển một đơn vị hàng húa từ trạm phỏt Ai tới trạm thu Bj là cij  1 , 1i m j n    .Lập phương ỏn vận chuyển đỏp ứng đầy đủ yờu cầu của cỏc trạm thu bằng tỏt cả cỏc hàng húa cú ở cấc trạm phỏt với tổng chi phớ vận chuyển là nhỏ nhất . . Hóy lập kế hoạch vận chuyển từ mỗi điểm phỏt đến mỗi điểm thu bao nhiờu hàng để : - Cỏc điểm phỏt đều phỏt hết hàng - Cỏc điểm thu đều nhận đủ hàng - Tổng cước phớ phải trả là ớt nhất Gọi xij là lượng hàng chuyển từ điểm phỏt Ai đến điểm thu Bj , xij ≥ 0 . Vỡ tổng lượng hàng phỏt đi từ mỗi điểm phỏt Ai đến mọi điểm thu Bj bằng lượng hàng phỏt từ Ai nờn : Dạng toỏn học Gọi xij là lượng hàng vận chuyển từ trạm phỏt Ai tới trạm thu Bj .Mụ hỡnh bàicú dạng :         ij ij 1 1 ij 1 ij ij 1 min 1 1 , , n m j i n i j m j i f x c x x a i m x b j n x o i j                  48 Bài toỏn trờn gọi là bài toỏn vận tải cổ điển hay bài toỏn dạng đúng .Rừ ràng bài toỏn chỉ cú nghĩa khi 1 1 m n i j i j a b     ,với điều kiện này bài toỏn gọi là cõn bằng thu phỏt . Bài toỏn khụng cõn bằng thu phỏt cú 2 dạng và gọi chỳng là bài toỏn dạng mở . a) 1 1 m n i j i j a b       ij ij 1 1 min n m j i f x c x      ij 1 1 n i j x a i m        ij ij 1 1 , 0 , m j i x b j n x i j       b) 1 1 m n i j i j a b       ij ij 1 1 min n m j i f x c x           ij 1 ij ij 1 1 1 , 0 , n i j m j i x a i m x b j n x i j             2.Các đặc điểm Tớnh chất chung của bài toỏn vận tải đúng -Đú là bài toỏn dạng chớnh tắc .Trong hệ m+ n phương trỡnh ràng buộc chỉ cú m+n-1 phương trỡnh độc lập tuyến tớnh , do đú một phương ỏn cực biờn cú tối đa m+n-1 thành phần dương . - Cỏc vecto điều kiện Aij tương ứng với biến xij cú thành phần I và thànhphần m+j bằng 1 ,cỏc thành phần cũn lại đều bằng 0. -Bài toỏn cõn bằng thu phỏt luụn giải được . 3.Mô tả bài toán dưới dạng bảng Bài toỏn vận tải dạng bảng Xõy dựng một bản gồm m hàng và n cột ;mỗi hàng dặc trwung cho một trạm phỏt ,mỗi cột đặc trưng cho một trạm thu .Tương ứng với mỗi hàng hoặc cột ghi yờu cầu của trạm phỏt hoặc trạm thu . 49 -Phương phỏp chi phớ nhỏ nhất ( đường gần ):luụn ưu tiờn phõn phối cho ụ cú cij nhỏ nhất trong bảng .-Phương phỏp Fogels : Luụn ưu tiờn phõn phối cho ụ cú cij nhỏ nhất nằm trờn hàng hoặc cột cú hiệu số giữa chi phớ nhỏ nhỡ và nhỏ nhất và lớn nhất . Ta đưa bài toỏn vào một bảng gọi là bảng vận tải. Bảng gồm (m+1) hàng và (n+1) cột, cột 1 ghi tờn và lượng hàng ở cỏc điểm phỏt (Ai và ai). Hàng 1 ghi tờn và lượng hàng ở cỏc điểm thu (Bj và bj), ụ cũn lại trong mỗi ụ gúc trờn bờn trỏi ghi cước phớ cij, gúc dưới bờn phải ghi lượng hàng xij. • Cỏc khỏi niệm về bài toỏn dạng bảng: • ễ chọn: Là ụ cú lượng hàng xij ≥0, cũn gọi là ụ sử dụng, khoanh trũn xij lại. • ễ loại: Là ụ khụng cú hàng, tức xij=0, ta để trống ụ đú. • Dõy chuyền: là một đoạn thẳng hay một dóy liờn tiếp cỏc đoạn thẳng gấp khỳc mà hai đầu mỳt là hai ụ chỉ nằm trờn cựng một hàng hoặc một cột với một ụ chọn khỏc thuộc dõy truyền của bảng vận tải. • Chu trỡnh: Là dõy chuyền khộp kớn Như vậy một hàng hoặc một cột mà chu trỡnh đi qua thỡ chỉ đi qua hai ụ và số ụ. Do đú số ụ ớt nhất của một chu trỡnh là 4. • Ma trận X = (xi j)m.n thỏa món hệ (2) - (4) được gọi là một phương ỏn của bài toỏn. • Phương ỏn: X = (xi j)m.n thỏa món được gọi là phương ỏn cực biờn của bài toỏn vận tải nếu tập hợp cỏc ụ tương ứng với cỏc thành phần dương của nú khụng tạo thành chu trỡnh. • Phương ỏn X = (xi j)m.n được gọi là phương ỏn cực biờn khụng suy biến nếu số ụ chọn của nú đỳng bằng m+n+1. • Phương ỏn X = (xi j)m.n được gọi là phương ỏn cực biờn suy biến nếu số ụ chọn của nú nhỏ thua m+n+1. • Một phương ỏn thoả món yờu cầu (1) được gọi là phương ỏn tối ưu (nghiệm) của bài toỏn, ký hiệu là Xopt. Cho bài toỏn vận tải dạng bảng kớch thước m x n. Một tập hợp cỏc ụ cú thứ tự được gọi là một dõy chuyền nếu: 50 • Hai ụ liờn tiếp cựng dũng hoặc cựng cột. • Ba ụ liờn tiếp khụng cựng dũng hoặc cựng cột. Một dõy chuyền khộp kớn, nghĩa là ụ cuối cựng dũng hoặc cựng cột với ụ đầu tiờn được gọi là một chu trỡnh. Chỳ ý rằng mệnh đề ngược lại của éịnh lớ 3 khụng đỳng. Số m+n-1 chỉ là dấu hiệu cần nhưng khụng phải là điều kiện đủ để xột tập hợp cỏc ụ cú chứa chu trỡnh hay khụng. Hệ quả Một phương ỏn cực biờn cú khụng quỏ m+n-1 ụ chọn hay một phương ỏn cú từ m+n ụ chọn trở lờn thỡ khụng phải là phương ỏn cực biờn . Mệnh đề ngược lại khụng đỳng . Số ụ chọn khụng quỏ m+n-1 chỉ là dấu hiệu cần nhưng khụng đủ để xột một phương ỏn cú phải là cực biờn hay khụng . II.Xây dựng phương á n cực biên Bài toỏn vận tải là bài toỏn Qui hoạch tuyến tớnh dạng chớnh tắc nờn cú thể giải bằng phương phỏp đơn hỡnh ( Chương I ) .Tuy nhiờn , bài toỏn vận tải thường cú số ẩn rất lớn ( mxn ) và cú cấu trỳc đặc biệt : ma trận cỏc hệ số hầu hết bằng 0 ,do đú , chỳng ta sẽ khụng giải bài toỏn theo phương phỏp đơn hỡnh đó biết mà xõy dựng một phương phỏp giải đơn giản hơn , đú là phương phỏp (thuật toỏn ) phõn phối . Cú 3 phương phỏp xõy dựng phương ỏn cực biờn thường sử dụng là phương phỏp gúc . Nội dung chớnh của phương phỏp phõn phối gồm cỏc bước như sau : 1.Nguyên tắc phân phối tối đa(TL) Lõy ụ(i,j) bất kỳ và phõn phối lượng hàng xij = min(ai,bj) sẽ cú ba trường hợp xẩy ra như sau. Trường hợp 1: xij = ai nghĩa là trạm phỏt Ai đó hết hàng, loại bỏ hàng i đồng thời sửa lại nhu cầu của trạm thu Bj lượng hàng mới là b’j = bj- ai. Trường hợp 2: xij = bj nghĩa là trạm thu Bi đó hết hàng, loại bỏ cột j đồng thời sửa lại nhu cầu của trạm phỏt Aj lượng hàng mới là a’j = ai – bj Trường hợp 3: xij = ai = bj nghĩa là trạm phỏt Ai đó hết hàng và trạm thu Bj đó thoả món nhu cầu loại bỏ hàng i và cột J 51 Quỏ trỡnh cứ tiếp tục như vậy cho đến khi toàn bộ lượng hàng ở cỏc tram phỏt phõn phối hết và cỏc trạm thu thoả món nhu cầu về hàng hoỏ. 2.Các phương pháp xây dựng phương á n cực biên a. Phương phỏp tỡm phương ỏn cực biờn xuất phỏt. Để xõy dựng một phương ỏn cực biờn xuất phỏt người ta thường sử dụng một trong ba phương phỏp sau: • Phương phỏp gúc Tõy-Bắc. Phương phỏp gúc tõy bắc gồm những bước sau: Bước 1. Chọn ụ nằm ở dũng 1, cột 1 của bảng vận tải. Bước 2. Phõn lượng hàng h = min{a1, b1} vào ụ(1,1) Bước 3. Đỏnh dấu hàng (cột), theo đú lượng hàng ở trạm phỏt (trạm thu) tương ứng đó hết (đó đủ). Bước 4. Quay trở về bước 1 thực hiện cụng việc ở những ụ cũn lại. • Phương phỏp min- cước. Nội dung phương phỏp min cước gồm cỏc bước sau đõy. Bước 1. Chọn ụ cú cước phớ thấp nhất để phõn hàng giả sử là ụ (i,j). Bước 2. Phõn lượng hàng h = min {ai, bj} vào ụ(i,j) Bước 3. Đỏnh dấu cỏc ụ thuộc hàng i, hoặc cột j nếu trạm phỏt Ai đó phỏt hết hàng, hoặc trạm thu Bj đó nhận đủ hàng. Bước 4. Quay trở lại bước 1 thực hiện cụng việc ở những ụ cũn lại. • Phương phỏp xấp xỉ Phoghel. • Định nghĩa. Độ lệch của hàng (cột) là hiệu số giữa ụ cú cước phớ thấp thứ nhỡ trừ đi ụ cú cước phớ thấp thứ nhất của hàng (cột) đú. Nội dung của phương phỏp Phoghen gồm cỏc bước sau: Bước 1. Chọn hàng hoặc cột cú độ chờnh lệchlớnnhất 52 Bước 2. Chọn ụ cú cước phớ thấp nhất thuộc hàng (cột) cú độ chờnh lệch lớn nhất, giả sử ụ(i,j). Bước 3. Phõn lượng hàng h = min{ai, bj} vào ụ(i,j) Bước 4. Đỏnh dấu cỏc ụ thuộc hàng (cột), theo đú trạm phỏt Ai đó phỏt hết hàng hoặc trạm thu Bj đó nhận đủ hàng, quay trở về từ bước 1 tiếp tục thực hiện thuật toỏn. Phương phỏp gúc Tõy - Bắc - Phõn phối tối đa vào ụ gúc Tõy - Bắc của bảng ( gúc trờn bờn trỏi ) . - Tớnh lại lượng hàng ở dũng và cột vừa tham gia phõn phối . Tạm thời loại dũng hoặc cột cú lượng hàng cũn lại bằng 0 ra khỏi quỏ trỡnh phõn phối . Quay lại bước ở trờn và tiếp tục phõn phối cho đến hết . Cỏc số ai được viết ở cột đầu tiờn , cỏc số bj được viết ở dũng đầu tiờn . Cỏc dũng và cột này khụng tớnh vào kớch thước bài toỏn . Ma trận cước phớ [ ci j ] đưọc viết nhỏ hơn ở phớa dưới mỗi ụ . Phương phỏp ưu tiờn cước phớ nhỏ nhất - Phõn phối tối đa vào ụ cú cước phớ nhỏ nhất của toàn bảng . - Tớnh lại lượng hàng ở dũng và cột vừa tham gia phõn phối . Tạm thời loại dũng hoặc cột cú lượng hàng cũn lại bằng 0 ra khỏi quỏ trỡnh phõn phối . Quay lại bước - ở trờn và tiếp tục phõn phối cho đến hết . - Phương phỏp xấp xỉ Fogen - Tớnh độ lệch của cỏc dũng [ cột ] bằng hiệu số giữa cước phớ nhỏ thứ nhỡ và cước phớ nhỏ nhất trong dũng [ cột ] đú . - Xỏc định ụ trũng : ụ cú cước phớ nhỏ nhất ở trờn dũng và cột cựng cú độ lệch lớn nhất . Phõn phối tối đa vào ụ trũng nếu cú và chuyển sang bước tiếp theo. - Phõn phối tối đa vào ụ cú cước phớ nhỏ nhất ở trờn dũng [ cột ] cú độ lệch lớn nhất . - Tớnh lại lượng hàng trờn dũng và cột vừa phõn phối . Loại bỏ dũng hoặc cột cú lượng hàng bằng 0 khỏi quỏ trỡnh phõn phối . Quay lại bước và tiếp tục quỏ trỡnh cho đến hết . Phương ỏn thu được theo nguyờn tắc phõn phối tối đa là phương ỏn cực biờn . 53 III.Phương pháp thế vị giải bài toán vận tải 1.Tiêu chuẩn tối ưu Tiờu chuẩn tối ưu : Điều kiện cần và đủ để phương ỏn ij{x }x  của bài toỏn vận tải tối ưu là tồn tại một hệ thống số i{u }jv thỏa món : a) ij ( , )j iv u c i j   b) ijj iv u c  nếu xij>0 Cỏc số ui,vj trong tiờu chuẩn tối ưu và trong cỏc tớnh toỏn sẽ gặp được gọi làcỏc thế vị hàng và cột . 3. Thuật toán của phương pháp thế vị Thuật toỏn của phương phỏp thế vị Giả sử đó biết một phương ỏn cực biờn với tập ụ cơ sở S tương ứng .Thuật toỏn gồm cỏc bước sau : Bước 1: Tỡm phương ỏn cực biờn xuất phỏt X0= (xij )m..xn Sử dụng một trong 3 phương phỏp đó trỡnh bầy ở trờn để tỡm phương ỏn cực biờn xuất phỏt (nếu phương ỏn tỡm được là phương ỏn suy biến thỡ ta phải bổ xung ụ chọn khụng để được phương ỏn khụng suy biến, ụ chọn cú vai trũ như cỏc ụ chọn khỏc). Bước 2: Kiểm tra tớnh tối ưu của phương ỏn. • Xõy dựng hệ thống thế vị. 1)Xõy dựng hệ thống thế vị {ui,vj}Lấy một hàng I bất kỡ và cho nú một thế vị u ,tựy ý .Cỏc thế vị cũn lại được xỏc định theo quy tắc : -Nếu hàng I đó cú ui và (I,j) S thỡ thế vị của cột j được tớnh bởi :Vj=ui+cij-Nếu cột j đó cú vj và (I,j) S thỡ thế vị của hàng I được tớnh bởi : Ui=vj-cijQuỏ trỡnh tiếp tục cho tới khi xỏc định được toàn bộ hệ thống thế vị . 2) Kiểm tra tiờu chuẩn tối ưu -Cỏc ụ cơ sở (I,j) S ,hiển nhiờn thỏa món điều kiện b vỡ vậy chỉ cần kiểm tra điều kiện a đối với cỏc ụ phi cơ sở (I,j) S . -Nếu vj-uicij,  ,i j S  thỡ phương ỏn tương ứng tối ưu . 54 -Nếu tồn tại một ụ  Sji , mà vj - ui > cij thỡ phương ỏn khụng tối ưu .Cỏc ụ cú vj - ui > cij gọi là cỏc ụ vi phạm ,tớnh ijijij cuv  đối với cỏc ụ vi phạm ,như vậy 0ij 3) Điều chỉnh phương ỏn -Giả sử rkij ij   max 0 .ễ (r,k) được lấp làm ụ điều chỉnh .Tỡm vũng tạo bởi ụ điều chỉnh với cỏc ụ cơ sở .Trờn vũng đỏnh dấu lẻ chẵn cỏc ụ với ụ điều chỉnh (r,k) là ụ lẻ .Ký hiệu vi,vc tương ứng là tập ụ lẻ ,chẵn trờn vũng .Xỏc định q=min xij,   cVji , .Thực hiện phộp biến đổi biến số trờn vũng :             cij iij ij ij Vjiqx Vjiqx Vjix x , ,, ,, -Thực chất phộp biến đổi trờn là tăng q cho ụ lẻ và giảm q ở ụ chẵn . -Kết quả của quỏ trỡnh biến đổi ta được phương ỏn cực biờn mới x' tốt hơn x :     rkqxfxf  .' sau điều chỉnh ụ điều chỉnh thành ụ cơ sở ,ụ ứng với q sẽ trở thành phi cơ sở. 3.Trường hợp suy biến - Trường hợp bài toỏn suy biến thỡ q cú thể bằng 0.Khi q=0 ta vẫn thực hiện thuật toỏn một cỏch bỡnh thường ,nghĩa là ụ ứng với q vẫn bị loại khỏi tập ụ cơ sở .Tuy nhiờn kết quả của quỏ trỡnh điều chỉnh chỉ chuyển sang một tập ụ cơ sở khỏc của cựng một phương ỏn cực biờn suy biến . - Dấu hiệu xuất hiện phương ỏn cực biờn suy biến là q đạt tại nhiều ụ .Khi đú ta sẽ loại một trong những ụ ứng với q ra khỏi tập ụ cơ sở theo quy tắc ngẫu nhiờn ,cỏc ụ cũn lại ứng với q vẫn giữ trong tập ụ cơ sở với tư cỏch ụ bổ sung. IV.Bài toán không cân bằng thu phát 1.Phát lớn hơn thu Trường hợp      m i n j jba 1 1 1 ta đưa về bài toỏn cõn bằng thu phỏt bằng cỏch thờm vào một trạm thu giả Bn+1 với yờu cầu       m i n j jn bab 1 1 11 ,đồng thời ci.n+1=0 )( j .Lượng hàng lấy từ trạm phỏt A1 cung cấp cho trạm thu giả Bn+1 nghĩa là lượng hàng được giữ lại ở trạm phỏt A1 P.hương phỏp giải • Giải bài toỏn vận tải cung lớn hơn cầu: 55 Ta thờm vào bài toàn một trạm thu giả Bn+1 với lượng hàng thu là: Cước phớ từ trạm phỏt giả Am+1 đến cỏc trạm thu Bj là cm+1,j = 0 (j = ,1 n ). Khi đú bài toỏn đó cho trở về bài toỏn cung bằng cầu mà ta đó biết cỏch giải. Chỳ ý: - Khi giải bài toỏn trờn, nếu sử dụng phương phỏp min- cước tỡm phương ỏn cực biờn xuất phỏt ta ưu tiờn phõn phối hàng tối đa vào ụ cú cựớc phớ dương nhỏ nhất trước rồi mới mới đến ụ cú cước phớ bằng khụng. • Giỏ trị hàm mục tiờu: f (Xopt) = f ( X opt) = fmin. 2.Phát it hơn thu -Trường hợp      m i n j ji ba 1 1 .Ta đưa về bài toỏn cõn bằng thu phỏt bằng cỏch thờm vào một trạm phỏt giả Am+1 với yờu cầu am+1=     n j m i ij ab 1 1 ,đồng thời )(0 jc ijm  .Lượng hàng lấy từ trạm phỏt giả Am+1 cung cấp cho trạm thu Bj ,nghĩa là lượng yờu cầu của trạm thu Bj khụng được thoả món . hàng. Phương phỏp giải • Giải bài toỏn vận tải cung lớn hơn cầu: Ta thờm vào bài toàn một trạm thu giả Bn+1 với lượng hàng thu là: Cước phớ từ trạm phỏt giả Am+1 đến cỏc trạm thu Bj là cm+1,j = 0 (j = ,1 n ). Khi đú bài toỏn đó cho trở về bài toỏn cung bằng cầu mà ta đó biết cỏch giải. Chỳ ý: - Khi giải bài toỏn trờn, nếu sử dụng phương phỏp min- cước tỡm phương ỏn cực biờn xuất phỏt ta ưu tiờn phõn phối hàng tối đa vào ụ cú cựớc phớ dương nhỏ nhất trước rồi mới mới đến ụ cú cước phớ bằng khụng. • Giỏ trị hàm mục tiờu: fmin. Thực hành giải bài toán QHTT trên máy tính 56 tài liệu tham khảo 1. Toán kinh tế - Đại học Mỏ địa chất. 2. Toán kinh tế - Học viện Tài chính Hà Nội. 3. Trần Túc - Quy hoạch tuyến tính Đại học Kinh tế quốc dân -Hà Nội 1998 4. Bài giảng giải các bài toán tối ưu và thống kê trên Excel- PGS.TS Bùi Thế Tâm - Phòng tối ưu và điều khiển viện toán học Việt Nam. 5. Hoàng Tuỵ - Lý thuyết quy hoạch Tập I nhà xuất bản khoa học hà nội - 1968.