Tài liệu Nguyên lý phân rã trong quy hoạch tuyến tính

.. „I HÅC THI NGUY–N TR×ÍNG „I HÅC KHOA HÅC V×ÌNG M„NH C×ÍNG NGUY–N LÞ PH…N R‚ TRONG QUY HO„CH TUY˜N TNH LUŠN V‹N TH„C Sž TON HÅC Th¡i Nguy¶n - 2013 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Cæng tr¼nh ÷ñc ho n th nh t¤i Tr÷íng ¤i Håc Khoa Håc - ¤i Håc Th¡i Nguy¶n Ng÷íi h÷îng d¨n khoa håc: GS - TS. Tr¦n Vô Thi»u Ph£n bi»n 1: TS: Nguy¹n V«n Ngåc - Vi»n To¡n håc Ph£n bi»n 2: GS. TS: Nguy¹n B÷íng - Vi»n CNTT Luªn v«n ÷ñc b£o v» tr÷îc hëi çng ch§m luªn v«n håp t¤i: Tr÷íng ¤i Håc Khoa Håc - ¤i Håc Th¡i Nguy¶n Ng y 12 th¡ng 10 n«m 2013 Câ thº t¼m hiºu t¤i Th÷ Vi»n ¤i Håc Th¡i Nguy¶n Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 1 Möc löc Mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ch÷ìng 1. Ki¸n thùc chu©n bà 1.1. 1.2. 1.3. 1.4. Tªp lçi v  tªp lçi a di»n . . . . . . . B i to¡n quy ho¤ch tuy¸n t½nh . . . èi ng¨u trong quy ho¤ch tuy¸n t½nh Thuªt to¡n ìn h¼nh c£i bi¶n . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ch÷ìng 2. Nguy¶n lþ ph¥n r¢ cõa Dantzig-Wolfe 2.1. 2.2. 2.3. 2.4. 2.5. Þ t÷ðng ph¥n r¢ cõa Dantzig - Wolfe . . Tr÷íng hñp G khæng bà ch°n . . . . . . . X¥y düng ph÷ìng ¡n cüc bi¶n ban ¦u . V½ dö minh håa ph¥n r¢ Dantzig - Wolfe Quy ho¤ch tuy¸n t½nh c§u tróc khèi . . . Ch÷ìng 3. Nguy¶n lþ ph¥n r¢ cõa Benders 3.1. 3.2. 3.3. 3.4. . . . . . Þ t÷ðng ph¥n r¢ cõa Benders . . . . . . . B i to¡n chõ v  b i to¡n chõ thu hµp . . . V½ dö minh håa ph¥n r¢ Benders . . . . . Quy ho¤ch tuy¸n t½nh c§u tróc bªc thang . K¸t luªn . . . . . . . . . . . . . . . . . . . . . T i li»u tham kh£o . . . . . . . . . . . . . . . Soá hoùa bôûi trung taâm hoïc lieäu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 7 . 7 . 12 . 14 . 15 . . . . . . . . . . . http://www.lrc.tnu.edu.vn/ 21 21 27 30 32 35 38 38 41 44 46 51 52 2 Mð ¦u Qui ho¤ch tuy¸n t½nh (Linear Programming) l  b i to¡n tèi ÷u ìn gi£n nh§t. â l  b i to¡n t¼m cüc tiºu (hay cüc ¤i) cõa mët h m tuy¸n t½nh vîi c¡c r ng buëc ¯ng thùc hay b§t ¯ng thùc tuy¸n t½nh. Qui ho¤ch tuy¸n t½nh câ nhi·u ùng döng rëng r¢i trong lþ thuy¸t v  thüc ti¹n. Ph÷ìng ph¡p ìn h¼nh (do G. B. Dantzig · xu§t n«m 1947) l  ph÷ìng ph¡p quen thuëc, câ hi»u qu£ º gi£i b i to¡n qui ho¤ch tuy¸n t½nh v  c¡c b i to¡n ÷a ÷ñc v· qui ho¤ch tuy¸n t½nh. Ph÷ìng ph¡p ìn h¼nh câ nhi·u bi¸n thº kh¡c nhau. Ch¯ng h¤n, vîi b i to¡n qui ho¤ch tuy¸n t½nh câ nhi·u h» sè b¬ng khæng, ta th÷íng dòng thuªt to¡n ìn h¼nh c£i bi¶n º tªn döng ë th÷a cõa c¡c h» sè kh¡c khæng. Vîi b i to¡n câ c§u tróc °c bi»t, ta c¦n sû döng c¡c thuªt to¡n ri¶ng, hi»u qu£. Luªn v«n n y d· cªp tîi nguy¶n lþ ph¥n r¢ Dantzig - Wolfe v  nguy¶n lþ ph¥n r¢ Benders º gi£i c¡c b i to¡n qui ho¤ch tuy¸n t½nh câ k½ch th÷îc lîn ho°c câ c§u tróc °c bi»t (c§u tróc ma trªn khèi hay c§u tróc ma trªn bªc thang). Þ t÷ðng cì b£n cõa kÿ thuªt ph¥n r¢ l  ÷a b i to¡n ban ¦u v· c¡c b i to¡n con nhä hìn (½t bi¸n sè hìn ho°c ½t r ng buëc hìn) ho°c câ thº tªn döng c§u tróc ri¶ng cõa b i to¡n con (ch¯ng h¤n c§u tróc b i to¡n vªn t£i) º gi£i hi»u qu£ hìn. Ta b­t ¦u tø tr÷íng hñp ìn gi£n, ð â b i to¡n gçm hai khèi r ng buëc ëc lªp nhau (two independent subsystems) khæng câ bi¸n sè chung. Ch¯ng h¤n, z= n1 X j=1 Soá hoùa bôûi trung taâm hoïc lieäu cj xj + n X cj xj → M in j=n1 +1 http://www.lrc.tnu.edu.vn/ 3 Vîi i·u ki»n. n1 X aij xj j=1 n1 X aij xj = bi , i = 1, ... , m1 (0.1) = bi , i = m1 + 1, ... , m j=n1 +1 xj ≥ 0, j = 1, 2, ... , n. Do khæng câ mèi li¶n h» n o giúa hai khèi n y (trø h m möc ti¶u) n¶n rã r ng l  nghi»m cõa b i to¡n qui ho¤ch tuy¸n t½nh (0.1) câ thº t¼m b¬ng c¡ch gi£i hai qui ho¤ch tuy¸n t½nh con (méi qui ho¤ch ùng vîi mët khèi) t¡ch bi»t nhau, rçi cëng hai gi¡ trà tèi ÷u l¤i º nhªn ÷ñc gi¡ trà tèi ÷u chung z. Mët mð rëng cõa b i to¡n (0.1) l  b i to¡n câ c§u tróc gâc - khèi (block - angular system) (0.2) sau ¥y. B i to¡n n y câ K khèi ëc lªp nhau v  c¡c r ng buëc li¶n k¸t: z = (c0 )T x0 + (c1 )T x1 + ... + (ck )T xk → M in Vîi i·u ki»n A0 x0 + A1 x1 + . . . + AK xK = b B 1 x1 = b1 .. ... (0.2) B K xK = bK x0 ≥ 0, x1 ≥ 0, ... , xK ≥ 0. Câ thº gi£i th½ch þ ngh¾a thüc t¸ cõa mæ h¼nh khèi (0.2) nh÷ sau: Gi£ sû mët cæng ty gçm K nh  m¡y ho¤t ëng g¦n nh÷ ëc lªp k = 1, ... , K. Méi nh  m¡y câ c¡c r ng buëc ri¶ng, ëc lªp vîi r ng buëc cõa c¡c nh  m¡y kh¡c. Tuy nhi¶n, giúa c¡c nh  m¡y câ mët sè r ng buëc chung, nh÷ h¤n ch¸ v· t i ch½nh, v· lao ëng l nh ngh· v  câ mët h m lñi ½ch chung ¤i di»n cho quy·n lñi cõa cæng ty v  K nh  m¡y. Trong b i to¡n (0.2) xk l  v²ctì biºu thà c÷íng ë ho¤t ëng cõa nh  m¡y thù k v  x0 l  c÷íng ë ho¤t ëng cõa bë phªn qu£n lþ cæng ty, khæng l  ho¤t ëng cõa b§t cù nh  m¡y n o. Dáng thù nh§t l  h m möc ti¶u chung cho to n cæng ty; dáng thù hai l  m r ng buëc v· sû döng chung m t i Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 4 nguy¶n khan hi¸m (t i ch½nh, lao ëng l nh ngh· ...); dáng thù ba l  x1 r ng buëc ch¿ ri¶ng cõa nh  m¡y thù nh§t v  dáng cuèi còng l  mK r ng buëc ch¿ ri¶ng cõa nh  m¡y thù K. C§u tróc gâc khèi (0.2) gñi þ cho ta chia nhä b i to¡n ban ¦u th nh K b i to¡n con ëc lªp nhau, rçi sau â i·u ch¿nh líi gi£i c¡c b i to¡n n y º t½nh ¸n c¡c r ng buëc li¶n k¸t chung. Mët c¡ch xû lþ kh¡ phê bi¸n èi vîi c¡c nh  kinh t¸ l  b­t ¦u tø ành gi¡ tuý þ c¡c t i nguy¶n khan hi¸m v  º cho c¡c nh  m¡y tü tèi ÷u ho¡ ho¤t ëng cõa m¼nh vîi i·u ki»n l  nh  m¡y ph£i tr£ ti·n cho c¡c t i nguy¶n hi¸m theo gi¡ ¢ qui ành. C¡c t i nguy¶n khan hi¸m m  bë phªn qu£n lþ cæng ty v  c¡c nh  m¡y c¦n ¸n nâi chung v÷ñt qu¡ mùc b (nguçn t i nguy¶n cæng ty ¢ câ). B i to¡n trð th nh t¼m mët thuªt to¡n hi»u qõa º i·u ch¿nh c¡c gi¡ (c¡c nh¥n tû Lagrange). Nguy¶n lþ ph¥n r¢ Dantzig-Wolfe cho ph²p l m vi»c n y nhí mët sè húu h¤n l¦n l°p. Ph¥n r¢ Benders thüc ch§t l  ph¥n r¢ Dantzig - Wolfe ¡p döng v o b i to¡n èi ng¨u. Theo c¡ch n y, sè bi¸n cõa b i to¡n ÷ñc gi£m bît b¬ng c¡ch th¶m nhi·u r ng buëc mîi v o b i to¡n èi ng¨u. Trong ph¥n r¢ Dantzig - Wolfe c¡c cët cõa "b i to¡n chõ" ÷ñc sinh ra khi c¦n. Trong ph¥n r¢ Benders công vªy, c¡c r ng buëc cõa b i to¡n chõ Benders ch¿ ÷ñc sinh ra khi c¦n ¸n. Mët lîp b i to¡n kh¡c công hay g°p trong thüc ti¹n v  câ thº ¡p döng nguy¶n lþ ph¥n r¢ l  c¡c h» thèng bªc thang (staircase systems). C¡c h» thèng n y kh¡c vîi h» thèng gâc - khèi (0.2) ð ché: c¡c ho¤t ëng ð méi b÷îc thang chia s´ c¡c nguy¶n li»u ¦u v o v  c¡c s£n ph©m ¦u ra vîi hai. b÷îc thang li·n tr÷îc v  ngay sau nâ. Ch¯ng h¤n, (0.3) mæ t£ mët h» thèng bªc thang câ bèn c§p. z = (c1 )T x1 + (c2 )T x2 + (c3 )T x3 + (c4 )T x4 → min Vîi i·u ki»n A11 x1 A21 x1 + A22 x2 A32 x2 + A33 x3 A43 x3 + A44 x4 = = = = b1 , b2 , b3 , b4 , x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ (0.3) 5 H» thèng bªc thang th÷íng n¡y sinh khi x²t c¡c qu¡ tr¼nh di¹n ra theo thíi gian, trong â c¡c ho¤t ëng ð mët thíi ký (hay giai o¤n) trüc ti¸p t¡c ëng tîi (hay chàu £nh h÷ðng bði) c¡c ho¤t ëng ð thíi ký ti¸p sau (hay li·n tr÷îc) m  khæng câ t¡c ëng tîi (hay chàu £nh h÷ðng bði) c¡c ho¤t ëng ð c¡c thíi ký (giai o¤n) kh¡c. C¡c h» thèng nh÷ th¸ n£y sinh trong s£n xu§t khi ho¤t ëng s£n xu§t ð méi giai o¤n ch¿ chàu £nh h÷ðng bði s£n xu§t ð giai do¤n li·n tr÷îc v  ch¿ câ t¡c ëng tîi s£n xu§t ð giai o¤n li·n sau. Trong c¡c b i to¡n nh÷ th¸, th÷íng mët sè ma trªn con tr¶n ÷íng ch²o ch½nh Aii l  gièng nhau v  mët sè ma trªn con tr¶n ÷íng ch²o phö Ai,i−1 công gièng nhau. Khi â câ thº khai th¡c c§u tróc °c bi»t n y º gi£i b i to¡n. Nëi dung luªn v«n ÷ñc chia th nh ba ch÷ìng ch½nh. Ch÷ìng 1 vîi ti¶u · "Ki¸n thùc chu©n bà" tr¼nh b y mët sè ki¸n thùc cì sð v· tªp lçi, tªp lçi a di»n, c¡ch x¡c ành tªp ¿nh v  tªp c¤nh væ h¤n cõa mët tªp lçi a di»n v  ành lþ biºu di¹n tªp lçi a di¶n qua c¡c ¿nh v  c¤nh væ h¤n cõa nâ. N¶u c¡c ki¸n thùc c¦n thi¸t v· b i to¡n qui ho¤ch tuy¸n t½nh v  t½nh ch§t, c¡ch x¥y düng b i to¡n èi ng¨u v  c¡c quan h» èi ng¨u trong qui ho¤ch tuy¸n t½nh. Cuèi ch÷ìng nh­c l¤i thuªt to¡n ìn h¼nh c£i bi¶n gi£i qui ho¤ch tuy¸n t½nh. Thuªt to¡n n y s³ ÷ñc dòng ¸n ð ch÷ìng sau º gi£i "b i to¡n chõ" theo ph¥n r¢ Dantzig - Wolfe. Ch÷ìng 2 vîi ti¶u · "Nguy¶n lþ ph¥n r¢ Dantzig - Wolfe" tr¼nh b y thuªt to¡n theo nguy¶n lþ ph¥n r¢ Dantzig - Wolfe gi£i qui ho¤ch tuy¸n t½nh câ k½ch th÷îc lîn ho°c câ c§u tróc ma trªn khèi °c bi»t: n¶u þ t÷ðng cõa ph÷ìng ph¡p v  c¡c kÿ thuªt t½nh to¡n cö thº. Þ t÷ðng cõa c¡ch ph¥n r¢ n y l  ÷a b i to¡n vîi nhi·u r ng buëc v· b i to¡n ½t r ng buëc hìn (gåi l  b i to¡n chõ) nh÷ng vîi r§t nhi·u bi¸n. Cët h» sè cõa c¡c bi¸n n y s³ ÷ñc t¼m d¦n khi c¦n, nhí gi£i c¡c b i to¡n phö. Tr÷íng hñp mi·n r ng buëc cõa b i to¡n con khæng bà ch°n v  v§n · t¼m ph÷ìng ¡n cüc bi¶n ban ¦u cho b i to¡n chõ công ÷ñc x²t tîi v  sau â n¶u mët v½ dö sè º minh ho¤. Cuèi ch÷ìng n¶u ¡p döng ph¥n r¢ Dantzig - Wolfe v o b i to¡n qui ho¤ch tuy¸n t½nh câ c§u tróc ma trªn ÷íng ch²o khèi. Ch÷ìng 3 vîi ti¶u · "Nguy¶n lþ ph¥n r¢ Benders" tr¼nh b y thuªt to¡n theo nguy¶n lþ ph¥n r¢ Benders gi£i qui ho¤ch tuy¸n t½nh, trong â c¡c v²ctì i·u ki»n cõa b i to¡n ÷ñc t¡ch th nh hai nhâm, çng thíi Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 6 c¡c v²ctì thuëc nhâm thù nh§t câ c§u tróc °c bi»t (ch¯ng h¤n c§u tróc b i to¡n vªn t£i, c§u tróc ma trªn khèi hay c§u tróc ma trªn bªc thang ...), cho ph²p khi gi£i b i to¡n ch¿ vîi c¡c v²ctì i·u ki»n thuëc nhâm n y câ thº sû döng c¡c ph÷ìng ph¡p gi£i ri¶ng câ hi»u qõa hìn so vîi ph÷ìng ph¡p gi£i chung, cán c¡c v²ctì thuëc nhâm thù hai câ d¤ng têng qu¡t. Þ t÷ðng cõa c¡ch ph¥n r¢ n y l  ÷a b i to¡n vîi nhi·u bi¸n v· b i to¡n ½t bi¸n hìn (gåi l  b i to¡n chõ) nh÷ng vîi r§t nhi·u r ng buëc. C¡c r ng buëc n y ÷ñc t¼m d¦n khi c¦n, nhí gi£i c¡c b i to¡n phö. Sau â n¶u mët v½ dö sè º minh ho¤. Cuèi ch÷ìng n¶u ¡p dung ph¥n r¢ Benders v o qui ho¤ch tuy¸n t½nh câ c§u tróc ma trªn bªc thang. Luªn v«n n y ÷ñc ho n th nh vîi sü h÷îng d¨n v  ch¿ b£o tªn t¼nh cõa GS -TS Tr¦n Vô Thi»u - Vi»n to¡n håc Vi»t Nam. Tø ¡y láng m¼nh, em xin ÷ñc b y tä láng bi¸t ìn s¥u s­c èi vîi sü quan t¥m, ëng vi¶n v  sü ch¿ b£o h÷îng d¨n cõa th¦y. Em xin tr¥n trång c£m ìn tîi c¡c Th¦y Cæ trong Tr÷íng ¤i Håc Khoa Håc - ¤i Håc Th¡i Nguy¶n, pháng  o T¤o Tr÷íng ¤i Håc Khoa Håc. çng thíi tæi xin gûi líi c£m ìn tîi tªp thº lîp cao håc to¡n K5C, K5A Tr÷íng ¤i Håc Khoa Håc ¢ ëng vi¶n gióp ï tæi trong qu¡ tr¼nh håc tªp v  l m lu¥n v«n n y. Tæi xin c£m ìn tîi UBND huy»n Na Hang - PGD  o t¤o Na Hang -Tuy¶n Quang, Ban gi¡m hi»u, c¡c çng nghi»p tr÷íng phê thæng D¥n Tëc B¡n Tró THCS Sinh Long - Na Hang -Tuy¶n Quang ¢ t¤o i·u ki»n cho tæi håc tªp v  ho n th nh k¸ ho¤ch håc tªp. Do ¥y l  l¦n ¦u ti¶n thüc hi»n cæng vi»c nghi¶n cùu, n¶n trong luªn v«n khæng tr¡nh khäi nhúng thi¸u sât, em r§t mong ÷ñc sü âng gâp þ ki¸n cõa c¡c Th¦y Cæ v  c¡c b¤n º b£n luªn v«n ÷ñc ho n thi»n hìn. Th¡i Nguy¶n, ng y 08 th¡ng 08 n«m 2013 Ng÷íi thüc hi»n V÷ìng M¤nh C÷íng Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 7 Ch÷ìng 1 Ki¸n thùc chu©n bà Ch÷ìng n y tr¼nh b y mët sè ki¸n thùc cì sð v· tªp lçi, tªp lçi a di»n v  ành lþ biºu di¹n tªp lçi a di¶n qua c¡c ¿nh v  c¤nh væ h¤n cõa nâ. N¶u c¡c ki¸n thùc c¦n thi¸t v· b i to¡n qui ho¤ch tuy¸n t½nh v  t½nh ch§t, b i to¡n èi ng¨u v  c¡c quan h» èi ng¨u trong qui ho¤ch tuy¸n t½nh. Cuèi ch÷ìng · cªp tîi thuªt to¡n ìn h¼nh c£i bi¶n gi£i qui ho¤ch tuy¸n t½nh. Nëi dung cõa ch÷ìng ÷ñc tham kh£o chõ y¸u tø c¡c t i li»u [2], [3] v  [4]. 1.1. Tªp lçi v  tªp lçi a di»n Tªp lçi l  mët kh¡i ni»m quan trång ÷ñc dòng rëng r¢i trong tèi ÷u ho¡. Tªp lçi câ nhi·u t½nh ch§t ¡ng chó þ, °c bi»t l  tªp lçi a di»n. ành ngh¾a 1.1.1. Tªp con C trong Rn ÷ñc gåi l  mët tªp lçi n¸u nâ chùa trån o¤n th¯ng nèi hai iºm b§t ký thuëc nâ. Nâi c¡ch kh¡c, tªp C l  lçi n¸u αa + (1 − α)b ∈ C vîi måi a, b ∈ C v  måi 0 ≤ α ≤ 1. Nâi ri¶ng, tªp ∅, tªp gçm duy nh§t mët ph¦n tû v  to n bë khæng gian Rn l  c¡c tªp lçi • Mët sè tªp lçi ¡ng chó þ: a,Tªp afin, tùc l  tªp chùa trån ÷íng th¯ng i qua hai iºm b§t ký thuëc nâ. b, Si¶u ph¯ng, tùc l  tªp câ d¤ng  H = x ∈ Rn : aT x = α, a ∈ Rn \ {0} , α ∈ R }. c, C¡c nûa khæng gian âng   H + = x ∈ Rn : aT x ≤ α , H − = x ∈ Rn : aT x ≥ α}. d, C¡c nûa khæng gian mð   H + = x ∈ Rn : aT x < α , H − = x ∈ Rn : aT x > α}. e, H¼nh c¦u âng B(a, r) = {x ∈ Rn : kx − ak ≤ r} (a ∈ Rn r > 0 cho tr÷îc.) Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 8 • Tø ành ngh¾a tªp lçi trüc ti¸p suy ra mët sè t½nh ch§t cì b£n sau ¥y: a) Giao cõa mët hå b§t ký c¡c tªp lçi l  mët tªp lçi ( nh÷ng hñp khæng óng ) b) Têng cõa hai tªp lçi v  hi»u cõa hai tªp lçi công l  c¡c tªp lçi. c) N¸u C ⊂ Rm, D ⊂ Rn th¼ t½ch C × D = {(x, y) : x ∈ C, y ∈ D} l  mët tªp lçi trong Rm+n (Câ thº mð rëng cho nhi·u tªp lçi). d) Tªp M l  mët tªp afin khi v  ch¿ khi M = a + L vîi a ∈ M v  L l  mët khæng gian con, gåi l  khæng gian con song song vîi M , hay t÷ìng ÷ìng: M l  mët tªp afin khi v  ch¿ khi M l  tªp nghi»m cõa mët h» ph÷ìng tr¼nh tuy¸n t½nh, tùc câ biºu di¹n M = {x ∈ Rn : Ax = b, A ∈ Rm+n , b ∈ Rm }. Giao cõa b§t ký c¡c tªp afin l  tªp afin. ành ngh¾a 1.1.2. a) iºm x ∈ Rn câ d¤ng x = λ1a1+λ2a2+...+λk ak vîi ai ∈ Rn , λi ≥ 0, λ1 + λ2 + ... + λk = 1 , gåi l  mët tê hñp lçi cõa c¡c iºm a1 , a2 , ..., ak . b) iºm x ∈ Rn câ d¤ng x = λ1a1 + λ2a2 + ... + λk ak vîi ai ∈ Rn, λi ≥ 0, λ1 + λ2 + ... + λk = 1 , gåi l  mët afin cõa c¡c iºm a1 , a2 , ..., ak . c) iºm x ∈ Rn câ d¤ng x = λ1a1 + λ2a2 + ... + λk ak vîi ai ∈ Rn, λi ≥ 0 , gåi l  mët tê hìp tuy¸n t½nh khæng ¥m hay l  tê hñp nân cõa c¡c iºm a1 , a2 , ..., ak . ành ngh¾a 1.1.3. Cho E l  mët tªp b§t ký trongRn. , . . . , a) Giao cõa t§t c£ c¡c tªp afin chùa E gåi l  bao afin cõa E, kþ hi»u l  aff E. â l  tªp afin nhä nh§t chùa E . b) Giao cõa t§t c£ c¡c tªp lçi chùa E gåi l  bao lçi cõa E, kþ hi»u l  convE. â l  tªp lçi nhä nh§t chùa E. ành ngh¾a 1.1.4. a)Thù nguy¶n (hay sè chi·u) cõa mët tªp afin M, kþ hi»u dimM, l  thù nguy¶n (sè chi·u) cõa khæng gian con song song vîi nâ. Qui ÷îc dim φ = −1 b) Thù nguy¶n (hay sè chi·u) cõa mët tªp lçi C, kþ hi»u dim E, l  thù nguy¶n hay sè chi·u cõa bao afin aff C cõa nâ. Mët tªp lçi C trong Rn gåi l  câ thù nguy¶n ¦y õ n¸u dimC = n Tªp lçi a di»n l  mët d¤ng tªp lçi câ c§u tróc ìn gi£n v  r§t hay g°p trong lþ thuy¸t tèi ÷u tuy¸n t½nh. ành ngh¾a 1.1.5. Mët tªp lçi m  l  giao cõa mët sè húu h¤n c¡c nûa khæng gian âng gåi l  mët tªp lçi a di»n. Nâi c¡ch kh¡c, â l  tªp Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 9 nghi»m cõa mët h» húu h¤n c¡c b§t ph÷ìng tr¼nh tuy¸n t½nh: a1i x1 + a12 x2 +, ..., +a1n xn ≤ bi , i = 1, 2, ..., m, Ngh¾a l  tªp c¡c x nghi»m óng Ax ≤ b vîi A = (aij) ∈ Rm×n b = (b1 , ..., bm )T V¼ mët ph÷ìng tr¼nh tuy¸n t½nh câ thº biºu di¹n t÷ìng ÷ìng b¬ng hai b§t ph÷ìng tr¼nh tuy¸n t½nh n¶n tªp nghi»m cõa mët h» ph÷ìng tr¼nh v  b§t ph÷ìng tr¼nh tuy¸n t½nh công l  mët tªp lçi a di»n: a1i x1 + a12 x2 +, ..., +a1n xn = bi i = 1, 2, ..., m, a1i x1 + a12 x2 +, ..., +a1n xn ≤ bi i = p + 1, ..., m, Mët tªp lçi a di»n câ thº khæng bà ch°n (khæng giîi nëi). Mët tªp lçi a di»n bà ch°n cán ÷ñc gåi l  mët a di»n lçi. C¡c a gi¡c lçi theo ngh¾a thæng th÷íng trongR2 l  nhúng v½ dö cö thº v· a di»n lçi. Cho D = {x ∈ Rn : Ax = b, x ≥ 0} , tùc D l  tªp nghi»m khæng ¥m cõa mët h» ph÷ìng tr¼nh tuy¸n t½nh. Theo ành ngh¾a, D l  mët tªp lçi a di»n. Tªp n y khæng chùa trån ÷íng th¯ng n o (do x ≥ 0) n¶n D câ ¿nh. C¡c ph÷ìng cüc bi¶n (¢ chu©n hâa) cõa D l  c¡c nghi»m cì sð cõa h» Ay = 0, eT y = 1, y ≥ 0 trong â e = (1, ..., 1)T Ta câ ành lþ biºu di¹n sau ¥y, th÷íng hay ÷ñc dòng trong c¡c chùng minh. ành lþ 1.1.1. Méi iºm cõa tªp lçi a di»n D = {x ∈ Rn : Ax = b, x ≥ 0} câ thº biºu di¹n d÷îi d¤ng mët tê hñp lçi cõa mët tªp húu h¤n c¡c ¿nh cõa D cëng vîi mët tê hñp tuy¸n t½nh khæng ¥m cõa mët tªp húu h¤n c¡c ph÷ìng cüc bi¶n cõa D. Chùng minh. ành lþ kh¯ng ành: méi nghi»m ch§p nhªn ÷ñc x = x cõa h» Ax = b, x ≥ 0 (1.1) câ thº biºu di¹n d÷îi d¤ng  p q P P  i  x= αi u + βj v j    i=1 j=1 p P 1= αi ui    i=1   αi ≥ 0, i = 1, ..., p, βj ≥ 0, j = 1, ..., q, Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ (1.2) 10 trong â ui l  tªp húu h¤n t§t c£ c¡c ¿nh v  vi l  tªp húu h¤n t§t c£ c¡c ph÷ìng cüc bi¶n (ph÷ìng cõa c¡c c¤nh væ h¤n) cõa D. Tr÷îc h¸t, gi£ sû x = x ÷ñc x¡c ành theo(1.2)vîi c¡c h» sè αi, i = 1, ..., p v  βj , j = 1, ..., q n o â. º þ x = x ≥ 0 l  do αi ≥ 0, βj ≥ 0 vîi måi i, j. Hìn núa, do Aui = b vîi måi i = 1, ... , p v  Avj = 0 vîi måi j = 1, ... , q n¶n ta câ  Ax = A  p P i αi u + A i=1 = q P j=1 αi b + q P j βj v = j=1 q P βj (0) = b j=1 p P i αi (Au ) + i=1 q P βj (Av j ) j=1 Ngh¾a l  x thäa m¢n vîi (1.1) Ti¸p theo, ta chùng minh ng÷ñc l¤i r¬ng vîi b§t ký nghi»m ch§p nhªn ÷ñc ¢ cho x = x cõa (1.1) t¼m ÷ñc c¡c sè αi ≥ 0, βi ≥ 0 thäa m¢n (1.2). Muèn th¸, gi£ thi¶t ph£n chùng r¬ng khæng tçn t¤i αi, βi thäa m¢n:  p q P P  i  αi u + βj v j = x    i=1 j=1  P p αi ui = 1  i=1    α ≥ 0, i = 1, ..., p,    i βj ≥ 0, j = 1, ..., q, (1.3) i·u n y k²o theo (dòng Bê · Farkas) tçn t¤i c¡c nh¥n tû π = (π 1 , ..., π n )T v  γ = γ khæng çng thíi b¬ng 0 sao cho h» sau câ nghi»m:   ( a) π T ui + γ ≥ 0 vîi måi i = 1, ... , p, (1.4) (b) πT vi ≥ 0 vîi måi j = 1,... , q,  . (c) π T x + γ < 0 Nh÷ng b¥y gií ta s³ ch¿ ra r¬ng thüc t¸ (1.4) væ nghi»m, do â tr¡i vîi gi£ thi¶t ph£n chùng tr÷îc â cho r¬ng (1.3) væ nghi»m. Muèn th¸ ta x²t qui ho¤ch tuy¸n t½nh: min {πw : Aw = b, w ≥ 0}. (1.5) Vîi c¡c h» sè möc ti¶u π thäa m¢n (1.4) v  c¡cr ng buëc ch½nh l i c¡c i r ng buëc cõa (1.1), v¼ th¸ (1.5) câ tªp ¿nh l  u thäa m¢n Au = b Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 11 v  tªp ph÷ìng cüc bi¶n l  vi thäa m¢n Avj = 0. B i to¡n (1.5) câ nghi»m ch§p nhªn ÷ñc w = x (theo gi£ thi¶t). Rã r ng qui ho¤ch tuy¸n t½nh (1.5) câ nghi»m cüc tiºu húu h¤n, v¼ theo (1.4b), måi ph÷ìng cüc bi¶n thäa m¢n πT vj ≥ 0, ngh¾a l  h m möc ti¶u khæng gi£m theo måi ph÷ìng cüc bi¶n. i·u n y k²o theo cüc tiºu cõa h m möc ti¶u ¤t t¤i mët ¿nh cõa mi·n r ng buëc. B¬ng c¡ch trø (1.4c) cho méi b§t ¯ng thùc (1.4a) ta nhªn ÷ñc c¡c h» thùc. π T x < π T ui vîi måi i = 1,..., p. Rã r ng â l  i·u m¥u thu¨n, bði v¼ i·u n y câ ngh¾a l  gi¡ trà h m möc ti¶u t¤i iºm ch§p nhªn ÷ñc w = x thüc sü nhä hìn gi¡ trà möc ti¶u t¤i måi ¿nh. V¼ th¸, ta k¸t luªn r¬ng ph£i câ c¡c sè αi v  αi thäa m¢n c¡c h» thùc (1.2).  V½ dö 1.1.1. V½ dö n y nh¬m minh håa cho c¡ch biºu di¹n mët iºm thuëc mët tªp lçi a di»n d÷îi d¤ng mët tê hñp lçi cõa mët tªp húu h¤n c¡c ¿nh cëng vîi mët tê hñp tuy¸n t½nh khæng ¥m cõa mët tªp húu h¤n c¡c ph÷ìng cüc bi¶n chu©n hâa, nh÷ ¢ ÷ñc chùng minh trong ành lþ 2.1. Cho tªp lçi a di»n:   D = x ∈ R2 : x1 + x2 ≥ 2, x1 ≥ 0, x2 ≥ 0 , nh÷ v³ ð h¼nh 1.1.Tø h¼nh v³ n y ta th§y C¡c ¿nh cõa E gçm u1 = (2, 0)T v  u2 = (0, 2)T . C¡c c¤nh væ h¤n ( nûa ÷íng th¯ng) cõa D: (x1 ≥ 2, x2 = 0) v  (x1 = 0, x2 ≥ 2). C¡c ph÷ìng cüc bi¶n cõa D gçm câ v1 = (1, 0)T v  v2 = (0, 1)T Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 12 Vîi c¡c v½ dö n y, ành lþ 1.1 nâi r¬ng méi iºm x ∈ D câ thº vi¸t d÷îi d¤ng:  x = α1 2 0   + α2 0 2   + β1 1 0   + β2 0 1  Trong â α1 ≥ 0, α2 ≥ 0, β1 ≥ 0, β2 ≥ 0 Ch¯ng h¤n x = (1, 3)T câ biºu di¹n tr¶n vîi α1 = 0, α2 = 1, β1 = β2 = 0 ho°c α1 = α2 = 0, 5; β1 = 0, β2 = 2 ho°c mët tê hñp lçi b§t ký cõa hai biºu di¹n n y. 1.2. B i to¡n quy ho¤ch tuy¸n t½nh Qui ho¤ch tuy¸n t½nh l  b i to¡n t¼m cüc tiºu (hay cüc ¤i) cõa mët h m tuy¸n t½nh vîi c¡c r ng buëc tuy¸n t½nh. Ð d¤ng ch½nh t­c nâ câ thº vi¸t nh÷ sau:  n P   f (x) = cj xj → min    j=1 n P aij xj = bi , i = 1, ..., m,    j=1   xj ≥ 0, j = 1, 2, ..., n, (1.6) . trong â aij, bi, cj l  c¡c h¬ng sè thüc cho tr÷îc. Trong b i to¡n (1.6), f(x) gåi l  h m möc ti¶u, méi ph÷ìng tr¼nh ai1 x1 + ai2 x2 +, ..., +ain xn = bi (i = 1, 2, ..., m). gåi l  mët r ng buëc ¯ng thùc, méi b§t ¯ng thùc xj gåi l  mët r ng buëc v· d§u (hay r ng buëc khæng ¥m). iºm (hay v²ctì) x ∈ Rn thäa m¢n måi r ng buëc, gåi l  mët iºm ch§p nhªn ÷ñc, hay mët ph÷ìng ¡n cõa b i to¡n. Tªp hñp t§t c£ c¡c ph÷ìng ¡n cõa b i to¡n gåi l  mi·n r ng buëc hay mi·n ch§p nhªn ÷ñc cõa b i to¡n v  kþ hi»u l  D, tùc l  °t D = {x ∈ Rn : Ax = b, x ≥ 0} . Nh÷ ¢ nh­c l¤i ð möc 1.1.2, D l  mët tªp lçi a di»n câ ¿nh (n¸u tªp D 6= ∅). Ph÷ìng ¡n ¤t gi¡ trà nhä nh§t cõa h m möc ti¶u, gåi l  mët ph÷ìng ¡n tèi ÷u hay líi gi£i cõa b i to¡n. Mët ph÷ìng ¡n m  çng thíi l  mët ¿nh cõa D gåi l  mët ph÷ìng ¡n cüc bi¶n cõa b i to¡n. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 13 K½ hi»u A = (aij ) ∈ Rm×n , b = (b1 , ..., bm )T , c = (c1 , ..., cn )T , x = (x1 , ..., xn )T . Khi â b i to¡n (1.6) câ thº vi¸t gån l¤i th nh.  min f (x) = cT x : Ax = b, x ≥ 0 . ành lþ sau n¶u i·u ki»n c¦n v  õ º b i to¡n qui ho¤ch tuy¸n t½nh câ líi gi£i. ành lþ 1.2.1. N¸u mët qui ho¤ch tuy¸n t½nh câ ½t nh§t mët ph÷ìng ¡n v  n¸u h m möc ti¶u bà ch°n d÷îi trong mi·n r ng buëc (èi vîi b i to¡n min) th¼ b i to¡n ch­c ch­n câ ph÷ìng ¡n tèi ÷u (líi gi£i.) Mët ph÷ìng ¡n x ∈ D m  çng thíi l  mët ¿nh cõa D, gåi l  mët ph÷ìng ¡n cüc bi¶n, ngh¾a l  x khæng thº biºu di¹n ÷ñc d÷îi d¤ng mët tê hñp lçi cõa b§t cù hai ph÷ìng ¡n n o kh¡c cõa D. Nâi mët c¡ch kh¡c, h¹ x = γx1 + (1 − γ)x2 vîi 0 < γ < 1 v  x1, x2 ∈ D th¼ ph£i câ x = x1 = x2 . ành lþ sau n¶u mët t½nh ch§t °c tr÷ng cõa ph÷ìng ¡n cüc bi¶n cõa b i to¡n qui ho¤ch tuy¸n t½nh ch½nh t­c. ành lþ 1.2.2. º mët ph÷ìng ¡n x0 = x01, x02, ..., x0n
cõa b i to¡n qui ho¤ch tuy¸n t½nh ch½nh t­c l  ph÷ìng ¡n cüc bi¶n, th¼ c¦n v  õ l  c¡c v²ctì cët Aj cõa ma trªn A ùng vîi c¡c th nh ph¦n xj > 0 l  ëc lªp tuy¸n t½nh. Tø ành lþ tr¶n suy ra c¡c h» qu£ sau. H» qu£ 1.2.1. Sè ph÷ìng ¡n cüc bi¶n (tùc sè ¿nh) cõa b i to¡n qui ho¤ch tuy¸n t½nh ch½nh t­c l  húu h¤n. H» qu£ 1.2.2. Sè th nh ph¦n d÷ìng trong méi ph÷ìng ¡n cüc bi¶n cõa b i to¡n qui ho¤ch tuy¸n t½nh ch½nh t­c tèi a b¬ng m (m l  sè h ng cõa ma trªn A). Câ hai lo¤i ph÷ìng ¡n cüc bi¶n: ph÷ìng ¡n cüc bi¶n khæng suy bi¸n (n¸u nâ câ sè th nh ph¦n d÷ìng óng b«ng m) v  ph÷ìng ¡n cüc bi¶n suy bi¸n (n¸u sè th nh ph¦n d÷ìng cõa nâ nhä hìn m). ành lþ 1.2.3. N¸u b i to¡n qui ho¤ch tuy¸n t½nh ch½nh t­c câ ph÷ìng ¡n tèi ÷u th¼ công câ ph÷ìng ¡n cüc bi¶n tèi ÷u. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 14 1.3. èi ng¨u trong quy ho¤ch tuy¸n t½nh Ta ành ngh¾a èi ng¨u cõa b i to¡n qui ho¤ch tuy¸n t½nh ch½nh t­c, kþ hi»u b i to¡n (P ): f (x) = c1 x1 + c2 x2 +, ..., +cn xn → min ai1 x1 + ai2 x2 +, ..., +ain xn = bi , i = 1, 2, ..., m, . xj ≥ 0, j = 1, 2, ..., n, l  b i to¡n, kþ hi»u b i to¡n (Q): g(y) = b1 y1 + b2 y2 +, ..., +bn yn → max, a1j y1 + a2j y2 +, ..., +amj ym ≤ cj , i = 1, 2, ..., n. Ta nhªn x²t r¬ng: a) C¡c r ng buëc ¯ng thùc trong b i to¡n ban ¦u (m  ta s³ gåi l  qui ho¤ch gèc hay b i to¡n gèc) t÷ìng ùng mët-mët vîi c¡c bi¸n trong b i to¡n èi ng¨u (m  ta s³ gåi l  c¡c bi¸n èi ng¨u), trong khi c¡c bi¸n trong qui ho¤ch gèc (bi¸n gèc) s³ t÷ìng ùng mët-mët vîi c¡c r ng buëc b§t ¯ng thùc trong b i to¡n èi ng¨u. C¡c bi¸n èi ng¨u khæng câ r ng buëc v· d§u (hay c¡c bi¸n èi ng¨u câ d§u tòy þ). b) C¡c h» sè ð v¸ ph£i r ng buëc trong b i to¡n gèc trð th nh c¡c h» sè möc ti¶u trong b i to¡n èi ng¨u, cán c¡c h» sè möc ti¶u trong b i to¡n gèc s³ trð th nh c¡c h» sè ð v¸ ph£i r ng buëc trong b i to¡n èi ng¨u. c) B i to¡n gèc t¼m min, cán b i to¡n èi ng¨u t¼m max (v  ng÷ñc l¤i) Dòng kþ hi»u v²ctì v  ma trªn, ta câ thº vi¸t gån l¤i nh÷ sau: B i to¡n gèc: f (x) = cT x → min, Ax = b, x ≥ 0 B i to¡n èi ng¨u: g(y) = bT x → max, AT y ≤ c, x ≥ 0 Ta câ c¡c quan h» èi ng¨u sau giúa hai b i to¡n gèc v  èi ng¨u. Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 15 ành lþ 1.3.1. (èi ng¨u y¸u). N¸u x l  mët ph÷ìng ¡n b§t ký cõa b i to¡n gèc (P) v  y l  mët ph÷ìng ¡n b§t ký cõa b i to¡n èi ng¨u (Q) th¼. f (x) = c1 x1 + c2 x2 +, ..., +cn xn ≥ g(y) = b1 y1 + b2 y2 +, ..., +bm ym ành lþ 1.3.2. (èi ng¨u m¤nh). N¸u mët qui ho¤ch tuy¸n t½nh câ ph÷ìng ¡n tèi ÷u th¼ qui ho¤ch èi ng¨u cõa nâ công câ ph÷ìng ¡n tèi ÷u v  gi¡ trà tèi ÷u cõa chóng l  b¬ng nhau. ành lþ 1.3.3. (ë l»ch bò y¸u). Mët c°p ph÷ìng ¡n x, y cõa hai qui ho¤ch tuy¸n t½nh èi ng¨u (P ) v  (Q) l  c¡c ph÷ìng ¡n tèi ÷u khi v  ch¿ khi chóng nghi»m óng h» thùc. T x c − A y = 0, T
hay xi  cj − m P  aij yi = 0, i=1 vîi måi j = 1, ..., n. 1.4. Thuªt to¡n ìn h¼nh c£i bi¶n Ph÷ìng ph¡p ìn h¼nh (do Dantzig · xu§t n«m 1947) l  ph÷ìng ph¡p thæng döng v  r§t hi»u qu£ º gi£i c¡c b i to¡n qui ho¤ch tuy¸n t½nh. Ph÷ìng ph¡p n y câ nhi·u bi¸n thº kh¡c nhau cho c¡c d¤ng b i to¡n cö thº: thuªt to¡n ìn h¼nh gèc, thuªt to¡n ìn h¼nh èi ng¨u, thuªt to¡n ìn h¼nh c£i bi¶n ... Thuªt to¡n ìn h¼nh c£i bi¶n câ °c iºm l  ð méi váng l°p ch¿ c¦n l÷u giú v  bi¸n êi ma trªn cì sð nghàch £o cï m × m, khæng c¦n bi¸n êi to n bë ma trªn i·u ki»n ban ¦u (cï m × n lîn hìn nhi·u), nhí â ti¸t ki»m ÷ñc bë nhî v  thíi gian t½nh to¡n gi£i b i to¡n. Thuªt to¡n n y °c bi»t th½ch hñp cho c¡c b i to¡n câ k½ch th÷îc lîn v  câ sè r ng buëc nhä hìn nhi·u so vîi sè bi¸n cõa b i to¡n. Nâ s³ ÷ñc sû döng trong c¡c thuªt to¡n ph¥n r¢, · cªp tîi ð c¡c ch÷ìng sau cõa luªn v«n. Möc n y s³ tr¼nh b y v­n t­t nëi dung thuªt to¡n ìn h¼nh c£i bi¶n. X²t b i to¡n qui ho¤ch tuy¸n t½nh d¤ng ch½nh t­c (m r ng buëc ¯ng thùc v  n bi¸n):  min f (x) = cT x : Ax = b, x ≥ 0 . (1.7) Gi£ sû ta câ ph÷ìng ¡n cüc bi¶n x vîi cì sð j = {j1, j2, ..., jm} , (Ai , Ai , ..., Ai l  c¡c v²c tì cì sð v  xi , xi , ..., xi l  c¡c bi¸n cì sð). °t 1 2 m Soá hoùa bôûi trung taâm hoïc lieäu 1 2 m http://www.lrc.tnu.edu.vn/ 16 B = (Ai1 , Ai2 , ..., Aim ) - ma trªn cì sð(m h ng × m cët). Zk = (z1k , z2k , ..., z1k )T - v²c tì cët c¡c h» sè khai triºn cõa v²c tì Ak theo cì sð B cB = (ci1 , ci2 , ..., cim )T - v²ctì cët c¡c h» sè möc ti¶u cõa c¡c bi¸n cì sð - v²ctì cët ghi gi¡ trà c¡c bi¸n cì sð. Theo ph÷ìng ph¡p ìn h¼nh, ta câ c¡c cæng thùc t½nh sau: xB = B −1 b, f (x) = (cB )T B −1 b, Zk = B −1 Ak , k = 1, 2, ..., n. ∆k = (cB )T Zk − ck l  ÷îc l÷ñng cõa bi¸n xk , k = 1, 2, ... , n. (1.8) Khi ÷a v²ctì phi cì sð Asv o cì sð B v  lo¤i khäi B v²ctì Ai vîi Zrs 6= 0, ta nhªn ÷ñc cì sð mîi: ngh¾a l  B 0 ch¿ kh¡c B bði mët v²ctì: As thay cho Ar (ð và tr½ thù r trong cì sð). kþ hi»u xB = (xi1 , xi2 , ..., xim )T r −1 Q = B −1 = (qik )m×n , Q0 = (B 0 ) = (q 0 ik )m×n . Khi â, cæng thùc li¶n h» giúa c¡c ph¦n tû q,ik v  qik nh÷ sau: , q ik =  qik − (qrk /zrs )zis , i 6= r qrk /zrs ) , i = r, i, k = 1, ..., m. (1.9) Qu¡ tr¼nh gi£i b i to¡n theo ìn h¼nh c£i bi¶n sû döng hai b£ng: B£ng 1.1 v  1.2. Trong B£ng 1.1, m + 1 dáng ¦u l÷u giú c¡c h» sè aij , bi ,cij cõa b i to¡n c¦n gi£i (1.7). Tø dáng m + 2 trð i ghi c¡c ÷îc l÷ñng ∆k cõa bi¸n xk ð méi váng l°p t½nh theo (1.8) Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 17 B£ng 1.2 gåi l  b£ng ìn h¼nh c£i bi¶n. Cët ¦u ghi t¶n c¡c bi¸n cì sð. Cët cB ghi h» sè möc ti¶u cõa c¡c bi¸n cì sð. Trong cët thù ba: m ph¦n tû ¦u l  gi¡ trà c¡c bi¸n cì sð, ph¦n tû cuèi l  trà sè h m möc ti¶u t÷ìng ùng. Ma trªn cì sð nghàch £o B −1 ÷ñc ghi ð m cët ti¸p theo. Cët Zs (cët quay): m ph¦n tû ¦u ghi c¡c h» sè khai triºn cõa v²ctì ÷a v o cì sð As theo c¡c v²ctì cì sð, ph¦n tû cuèi ghi ÷îc l÷ñng∆s. Dáng ph½a d÷îi ma trªn nghàch £o ghi ph÷ìng ¡n cõa b i to¡n èi ng¨u, nâ ÷ñc t½nh theo cæng thùc: (qm+1,1 , qm+1,2 , ..., qm+1,m ) = (cB )T B −1 (1.10) Thuªt to¡n ìn h¼nh c£i bi¶n gçm c¡c b÷îc sau. B÷îc 0 (X¥y düng b£ng ìn h¼nh ban ¦u). Gi£ sû lóc ¦u câ ph÷ìng ¡n cüc bi¶n x vîi cì sð J . °t B = {Aij : j ∈ J} ,T½nh ma trªn nghàch £o v  ghi nâ v o b£ng 1.2. T½nh m ph¦n tû ¦u cõa cët Ph÷ìng ¡n theo (1.8) v  t½nh qm+1,0 = (cB )T B −1b C¡c ph¦n tû qm+1,k (k = 1, ..., m) l  t½ch cõa v²ctì cB vîi v²ctì cët thù k cõa B −1, theo cæng thùc (1.10). B÷îc 1 (Kiºm tra tèi ÷u v  t¼m cët quay). T½nh ÷îc l÷ñng cõa bi¸n xk theo cæng thùc (1.8) : ∆k l  t½ch cõa dáng m + 1 cõa B£ng 1.2 vîi cët Ak ð B£ng 1.1, rçi trø ck . N¸u ∆k ≤ 0 vîi måi k = 1, ..., m th¼ ph÷ìng ¡n cüc bi¶n hi»n câ l  tèi ÷u. Tr¡i l¤i, ta x¡c ành v²ctì As ÷a v o cì sð theo cæng thùc (ho°c chån ng¨u nhi¶n, n¸u câ nhi·u ch¿ sè ¤t max): ∆s = max {∆k : ∆k ≥ 0, k ∈ / j} . Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 18 B÷îc 2 (Kiºm tra b i to¡n khæng câ líi gi£i húu h¤n v  t¼m dáng quay). Tr÷îc h¸t t½nh cët quay (cët Zs ð B£ng 1.2) theo cæng thùc Zs = B −1 As , tùc l  nh¥n tøng dáng cõa ma trªn nghàch £o B −1 vîi cët As ð B£ng 1.1 ta s³ ÷ñc tøng ph¦n tû cõa cët quay Zs cõa B£ng 1.2. Ph¦n tû cuèi cõa cët n y l  ∆s. N¸u zis ≤ 0 vîi måi i = 1, ..., m th¼ h m möc ti¶u cõa b i to¡n (1.7) khæng bà ch°n d÷îi: døng t½nh to¡n. Tr¡i l¤i, ta x¡c ành v²ctì lo¤i khäi cì sð theo cæng thùc:   qr0 qi0 θ0 = = min : zis > 0 zrs zis . Cët θ trong B£ng 1.2 dòng º ghi c¡c t¿ sè qi0/zis. vîi zis ≥ 0. B÷îc 3 (Bi¸n êi b£ng ìn h¼nh c£i bi¶n). Bi¸n cì sð ð dáng r l  xi bà lo¤i khäi cì sð, thay v o â l  bi¸n xs. Trong cët cB , thay h» sè möc ti¶u ð dáng r l  ci bði cs. Bi¸n êi ma trªn (qik )(m×n)×(m+1) (i = 1, 2, ... , m + 1; k = 0, 1, ... , m) theo cæng thùc t÷ìng tü (1.9) vîi cët quay Zs , dáng quay r v  ph¦n tû quay zrs > 0. Cö thº a) Chia méi ph¦n tû ð dáng r cho zrs. Dáng nhªn ÷ñc gåi l  dáng ch½nh. b) L§y méi dáng kh¡c trø t½ch cõa dáng ch½nh vîi ph¦n tû cõa dáng â tr¶n cët quay, tùc l  trø (dáng ch½nh)×zis. Quay trð l¤i thüc hi»n B÷îc1. V½ dö 1.4.1. º minh håa, ta gi£i b i to¡n sau theo thuªt to¡n ìn h¼nh c£i bi¶n. r r f (x) = 26x1 + 35x2 + 34x3 + 37x4 + 25x5 + 31x6 → min . 28x1 + 34x2 + 28x3 + 30x4 + 30x5 + 34x6 = 32 x1 + x2 + x3 + x4 + x5 + x6 = 1 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 Sè li»u ban ¦u cõa b i to¡n v  c¡c ÷îc l÷ñng ∆k ð méi váng lªp ghi ð b£ng sau. C¡c b÷îc gi£i b i to¡n ÷ñc n¶u trong ba b£ng ìn h¼nh c£i bi¶n. B£ng 1: Cì sð ban ¦u gçm hai v²ctì A1 v  A2vîi  B = (A1 ,A2 ) = Soá hoùa bôûi trung taâm hoïc lieäu 28 34 1 1  ⇒B −1  = − 16 1 6 17 3 − 14 3  http://www.lrc.tnu.edu.vn/