第二章单纯形法 如前所述，线性规划是运筹学的一个发展最早的重要分支，无论从理论、应用和计算 的角度， 线性规划仍然是最优化技术中发展得最好的一个分支，其发展与单纯形算法是分不 开的.至今为止，在1947年Dantzig提出的单纯形法算法仍是解线性规划问题的最有效的 算法随着计算机的运算速度和贮存能力的快速发展，用单纯形法可解有成干上万个约束 条件和决策变量的线性规划向题，从而使得线性规划的应用已逐渐扩展到工业、农业、交 通运输、军事和经济等各个领域 52.1线性规划问题的几何意义 在第一章第三节中介绍的图解法，已直观地说明了两个和三个变量线性规划问题的 可行域和最优解的几何意义：若两个或三个变量的线性规划问题的最优解存在，则一定可 在可行域的顶点得到，这一节我们把这一结论推广到一般的线性规划问题，并从理论上作 进 一步的讨论和说明。 一、线性规划问题的解 在进一步讨论之前，我们先介绍线性规划问题解的概念.本章如无特别说明，所讨论 的模型均为标准型： max 2=CX (2.1） 满足AX=b (2.2) x≥0 2.3) 可行解满足约束条件(12)，(13)的解X=(1，2，，工)T称为线性规划问题的可 行解所有可行解的集合叫做可行域 最优解使目标函数(1.1)达到最优的可行解叫做最优解 基本解和基本可行解 设矩阵A=【a]mxn的秩是m,其中n为决策变量数，m为约束条件方程的个数， n之m.令 乃=(a,a2,,am)T 为矩阵A的第jG=1,2,,n)列对应的列向量则AX=b可以写成： 且向量组B,乃，，Pn的极大线性无关组包含m个向量，不失一-般性，设B,P,,Pm 为其极大线性无关组，则方程组 P=b =1 1
✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠✡☛✡☞, ✌✡✍✡✎✡✏✡✑✡✒✡✓✡✔✡✕✡✖✡✗✡✘✡✙✡✚✡✛✡✕✢✜✡✣✢✤✡✥, ✦✡✧✡★✡✩✡✧✡✪✬✫✡✭✡✮✡✯✡✰ ✕✡✱✡✲, ✌✢✍✢✎✢✏✢✳✢✴✢✑✢✚✢✵✢✶✢✷✢✸✺✹✻✘✢✙✢✼✢✚✢✽✢✕✢✖✢✗✢✤✢✥, ✾✢✘✢✙✢✿✢❀✢❁✢❂✢✰✢❃✢✑✢✤✢❄ ❅ ✕. ❆❈❇❈❉❈❊, ❋ 1947 ● Dantzig ❍❈■❈✕❈❀❈❁❈❂❈❃❈✰❈❃❈✳✡✑❈❏✡✌❈✍✡✎✡✏❈❑✡▲✡✕❈✚✡▼❈◆✡✕ ✰✡❃. ❖✡P✡✯✡✰✡◗✡✕✡✒✡✰✡❘✡✲✡✮✡❙✡❚✡❯✡❱✡✕✡❲✡❘✡✘✡✙, ✭✡❀✡❁✡❂✡❃✡❳✡❏✡▼✡❨✡❩✡❬✡❭✡✗✡❪✡❫ ❴✡❵✮✡❛✡❜✡❝✡❞✡✕✡✌✡✍✡✎✡✏✡❑✡▲, ★✡❡✡❢✡✼✡✌✡✍✡✎✡✏✡✕✡✫✡✭❤❣❥✐✡❦✡❧✡✙✡♠✡♥✡♦✡✪q♣✡♦✡✪qr s✒✡t✡✪✬✉✡✈✡✮✡✇✡①✡②✡③✡✗✡④✡⑤. §2.1 ⑥⑧⑦⑧⑨⑧⑩⑧❶⑧❷⑧❸⑧❹⑧❺⑧❻❽❼ ❋✢❾✢✖✢❿✢❾✢➀✢➁✺✹✻➂✢➃✢✕✢➄✢❏✢❃, ❣✻➅✢➆✢➇✢➈✺➉✻➊✢➋✢✗✢✮✢➀✢✗✢❝✢❞✢✌✢✍✢✎✢✏✢❑✢▲✢✕ ❳✡➌✡⑤✡✮✡✚✡✵✡❏✡✕✡➍✡➎✡➏✡➐: ➑✡➋✡✗✡➒✡➀✡✗✡❝✡❞✡✕✡✌✡✍✡✎✡✏✡❑✡▲✡✕✡✚✡✵✡❏✡❚✡❋, ➓✡✖✡➔✡❳ ❋✡❳✡➌✡⑤✡✕✡→✡➣✡✼✡♠. ↔✡✖✡➁✡↕✡➙✡➛✡↔✡✖✡➜✡✧✡➝✡➞✡♠✡✖✡➟✡✕✡✌✡✍✡✎✡✏✡❑✡▲, ➠✡★✡✩✡✧✡❬✡➡ ➢ ✖✡➤✡✕✡➥✡✧✡✮✡➈❤➉. ➦ ✪✬➧✡➨✡➩✡➫✡➭✡➯✡➲✡➳ ❋➢ ✖✡➤✡➥✡✧✡➵✠ , ↕✡➙✡➸✡➂✡➃✡✌✡✍✡✎✡✏✡❑✡▲✡❏✢✕✢➺✡➻. ➼✡❿✟✦✡➽✡➾✡➈❤➉, ☛ ➥✡✧ ✕✡➚✡➪✡➶✡❉✡➹✡➘✡➪: max z = CX (2.1) ➴✡➷ AX = b (2.2) X ≥ 0 (2.3) ➬✡➮➳:➴✡➷❪✡❫❴✡❵ (1.2),(1.3) ✕✡❏ X = (x1, x2, . . . , xn) T ➱❉✡✌✡✍✡✎✡✏✡❑✡▲✡✕ ➬ ➮ ➳. ☛ ▼✡❳✡➌✡❏✡✕✡✃✡❐❤❒❥❮ ➬✡➮✡❰. Ï✡Ð➳: ❢ÒÑÓ➹✡Ô✡Õ (1.1) Ö✡♠✡✚✡✵✡✕✡❳✡➌✡❏❤❒❥❮✡✚✡✵✡❏. ×✡Ø➳✡Ù×✡Ø➬✡➮➳: Ú✢Û✢Ü A = aij m×n ✕✢Ý✢✑ m, ✾✺✹ n ❉✢❛✢❜✢❝✢❞✢Õ, m ❉✢❪✢❫❴✢❵✢Þ✢ß✕✢✗✢Õ, n ≥ m. à Pj = a1j , a2j , . . . , amj T ❉Û✡Ü A ✕✡❾ j(j = 1, 2, . . . , n) á✡â✡✫✡✕✡á❤ã❥❞. ➓ AX = b ❳✡ä✡å✡❨: Xn j=1 Pjxj = b æ ãç❞❈è P1, P2, . . . , Pn ✕❈é❈ê❈✌❈✍❈✦❈ë❈è❈ì❈í m ✗îãç❞❈ïð❄❈ñ❈✖❈➟❈✍❈ï Ú P1, P2, . . . , Pm ❉✡✾✡é✡ê✡✌✡✍✡✦✡ë✡è✡ï✬➓Þ✡ßè Xm j=1 Pjxj = b 1
2 第二章单纯形法 有唯一解(x,,.,)T,令其余的变量取值为0，则得到AX=b的一个解，称此解 为线性规划题(1.1)1.3)的基本解矩阵B=[凸，B,,Pm】称为基本解Xo对应的 基本矩阵，简称基矩阵。1,2，，工m称为基 变量，其它变量称为非基变量.基变量组成的集合称为基若基本解X©)满足 x≥0，则称这个解为基本可行解若基本可行解中非零分量的个数小于约束条件方程 的个数m,则称此问题是退化的.如非特别说明，本书中讨论的问题均为非退化的. 二、凸集及凸集中的顶点 定义2.1.1设K是n维欧氏空间中的一点集，若任意两点X1,X2∈K的连线上的任意 一点aX1+(1-a)X2∈K,其中0≤a≤1，则称K为凸集 (a) 图2-1 图2-1中的(a),(⑥)为凸集，(c,(d不是凸集. 义2.12设K为凸集，X∈K.若X不能用不同的两点X1,X2∈K的线性组合表示 为 X=aX1+(1-a)X2. 0<a<1 则称X为K的一个极点或顶点 极点X的直观意义是X不是K中任何线段的内点.如图2-1()，()中正方型和四 面体的顶点就是凸集的极点 三、基本定理 定理2.1.1若约来条件为(1.2)，(1.3)的线性规划问题的可行解的集合D={XAX= b.X>0}非空，则D是凸集 证明：根据凸集的定义，只要证明任意两点X1,X2∈D,都有X=aX1+(1-a)K2 D,0≤a≤1，即有 A(aX1+(1-a)X2)=b (2.4) aX1+(1-a)X2≥0 2.5) 因为X1,X2∈D,故有 AX1=b.X1≥0 AX2=b.X2≥0 从而有 A(aX1+(1-a)X2)=aAX1+(1-a)AX2 ab+(1-a)6=6 即X=aX1+(1-a)X满足条件(1.4).因为0≤a≤1
2 ò✡ó✡ôöõ✡÷✡ø❤ù ▼❈ú❈✖❈❏ (x (0) 1 , x (0) 2 , . . . , x (0) m ) T , à❈✾❈û❈✕❈❝❈❞❈ü❈ý❈❉ 0, ➓❈✼❈♠ AX = b ✕❈✖❈✗❈❏❈ï ➱❈þ❏ ❉✡✌✡✍✡✎✡✏✡❑✡▲ (1.1)-(1.3) ✕ ×✡Ø➳. Û✡Ü B = [P1, P2, . . . , Pm] ➱❉✡ÿ✡➼✡❏ X(0) â✡✫✡✕ ×✡Ø✁✁✂, ✄➱ ×✁✁✂. x1, x2, . . . , xm ➱❉ × ☎✝✆, ✾✝✞❝❞➱❉✠✟×✝☎✝✆. ÿ❝❞è❨✕✃❐➱❉ × . ➑ÿ➼❏ X(0) ➴➷ X(0) ≥ 0, ➓➱↔✡✗✡❏✡❉ ×✡Ø➬✡➮➳. ➑✡ÿ✡➼✡❳✡➌✡❏❤✹☛✡✁☞✡✤✡❞✡✕✡✗✡Õ✁✌✁✍✡❪✡❫❴✡❵✡Þ✡ß ✕✡✗✡Õ m, ➓➱✡þ❑✡▲✡✑✏✎✁✑ ✕. ✟ ✡✡➽✡➾✡➈❤➉, ➼✁✒❤✹❥➥✡✧✡✕✡❑✡▲✡➶✡❉✁✡✁✓✡✶✡✕. ✔ ✪✖✕✁✗✁✘✁✕✁✗✁✙✡➲✁✚✁✛ ✜✁✢ 2.1.1 ✣ K ✤ n ✥✧✦✁★✁✩✁✪✁✫☛✬✁✭✁✮✁✯, ✰✁✱✁✲✁✳✁✮ X1,X2 ∈ K ✬✁✴✁✵✁✶✁✬✁✱✁✲ ✭✁✮ αX1 + (1 − α)X2 ∈ K, ✷✧✫ 0 ≤ α ≤ 1, ✸✁✹ K ✺✻✕✁✗. (a) (b) ➄ 2–1 ➄ 2–1 ✹❥✕ (a),(b) ❉✧✼❥✃,(c),(d) ❄✡✑✧✼❥✃. ✜✁✢ 2.1.2 ✣ K ✺✧✽☛✯, X ∈ K. ✰ X ✾✁✿✁❀✁✾✧❁☛✬✁✳✁✮ X1, X2 ∈ K ✬✁✵✁❂✁❃✁❄✁❅✁❆ ✺ X = αX1 + (1 − α)X2, 0 < α < 1 ✸✁✹ X ✺ K ✬✁✭✁❇✻❈✁✛✻❉✻✚✁✛. é✡➣ X ✕✡➅✡➆✡➏✡➐✡✑ X ❄✡✑ K ✹☛❊✡➎✡✌✁❋✡✕✧●❥➣. ✟ ➄ 2–1(a),(b) ✹☛❍Þ ➪✡✮✁■ ❏✁❑✕✡→✡➣✁▲✡✑✧✼❥✃✡✕✡é✡➣. ▼ ✪ ×✡Ø✜✁◆ ✜✁◆ 2.1.1 ✰P❖❘◗✝❙✝❚✝✺ (1.2),(1.3) ✬✝✵✝❂✝❯✝❱P❲❘❳✝✬✝❨✝❩✝❬✝✬✝✯✝❄ D = {X|AX = b, X ≥ 0} ❭✁✩❥ï✖✸ D ✤✧✽☛✯. ❪❴❫: ❵❴❛❜✼ç✃❈✕❈➔❈➐, ❝❈✣❴❞î➉❡❊❈➏❈➋❈➣ X1, X2 ∈ D, ❢❈▼ X = αX1 + (1 − α)X2 ∈ D, 0 ≤ α ≤ 1, ❣✡▼ A(αX1 + (1 − α)X2) = b (2.4) αX1 + (1 − α)X2 ≥ 0 (2.5) ❤❉ X1, X2 ∈ D, ✐✡▼ AX1 = b, X1 ≥ 0 AX2 = b, X2 ≥ 0 ★✡❡✡▼ A(αX1 + (1 − α)X2) = αAX1 + (1 − α)AX2 = αb + (1 − α)b = b ❣ X = αX1 + (1 − α)X2 ➴✡➷✡❴✡❵ (1.4). ❤❉ 0 ≤ α ≤ 1
52.2线性规划问题的典式 -a20,X1≥0，X2≥0，从而X=aX1+(1-a)X2≥0，即X满足条件(1.5).定 理得证 4 定理2.12线性规划问题(1.1，(1.)和(13)的可行解X是基本可行解的充要条件是 X的非零分量所对应的象数列向量线性无关」 证明：必要性由基本可行解的定义即可知结论成立 充分性不妨设可行解X的前k个分量不为0，即X-(c1,工2，，工k,0,,0)F乃，P2 P为X的非零分量所对应的系数列向量因为矩阵A的秩为m,若向量乃乃2 线性无关，则必有k≤m.当k=m时，乃，乃，A恰构成一基本矩阵，从而 X=(1,2,,xk,0,,0)T为对应的基本可行解当k<m时，则一定可从其余列 向量中取出m-k个与乃，B,,P一起构成A的一极大线性无关向量组，其对应的解 恰为X,根据定义可知X为基本可行解 定理2.1.3线性规划问题(1.1入、(1.2)、(1.3)的基本可行解X对应于可行域D的极点 定理2.1.4线性规划问题若有可行解.则必有基本可行解.即线性规划问题的可行域D 如非空，则必有极点 ■ 定理2.1.5线性规划问题(1.1以、1.2以、1.)若有最优解，则一定可以在可行城D的极点 顶点)上达到 注意，这个定理并不是说只有极点才能使目标函数值最优。其它点不能。而是说如果 在其它点上使目标函数达到最优则一定可以找到一个极点X使目标函数值达到最优例 如第一章第三节中的例5中有多重解时的情祝. 根据这个定理，如果一个线性规划向题有最优解，我们只要在基本可行解中寻找即 可（虽然不是基本可行解的解也有可能为最优解） 因为基本可行解最多有C”个，把基 本可行解一一检验，有限次后必得最优解但当n和m较大时，基本可行解的个数仍然 是一个很大的数，所以一一检验基本可行解的计算量太大后面介绍的单纯形法很好的 解决了这个问题，其基本思路就是把当前的基本可行解调整成目标函数值更优的基本可 行解，这样仅仅检验能够使得目标函数改进的基本可行解减少了搜索量，加快了计算速 度 S2.2线性规划问题的典式 考虑标准型的线性规划向题 max之-CX (2.6) 【AX=b 满足 1x20 (2.7) 对线性规划问题的一组可行基不妨设基变量为1,2，，工m,令A=(B,N),其中 B=(B,B,,Pm)为基阵，N=(Pm+1,,P)为非基变量对应的矩阵把C和X相 应地表示为： C=(CB.CN),X=(XB XN)T
§2.2 ❥✁❦✁❧✁♠✧♥☛♦✧♣☛q✧r 3 , 1 − α ≥ 0, X1 ≥ 0,X2 ≥ 0, ★✡❡ X = αX1 + (1 − α)X2 ≥ 0, ❣ X ➴✡➷✡❴✡❵ (1.5). ➔ ✩✡✼✁❞. ✜✁◆ 2.1.2 ✵s❂s❯s❱t❲✉❳ (1.1), (1.2) ✈ (1.3) ✬s❨s❩s❬ X ✤s✇s①s❨s❩s❬s✬s②s③s❙s❚s✤ X ✬✧❭☛④✁⑤✁⑥✁⑦✁⑧✁⑨✁✬✧⑩☛❶✁❷✧❸☛⑥✁✵✁❂✁❹✧❺. ❪✁❫: ❻✁❼✡➨. ❽❥ÿ✡➼✡❳✡➌✡❏✡✕✡➔✡➐✁❣✡❳✁❾✡➜✡✧✡❨✁❿. ➀➂➁➨. ❄➂➃Ú❳➌❏ X ✕✠ k ✗✤❞❄❉ 0, ❣ X = (x1, x2, . . . , xk, 0, . . . , 0)T ,P1,P2,. . ., Pk ❉ X ✕✝✡✝☞✤❞☛ â✫✕✝➄Õá ã❞. ❤ ❉ÛÜ A ✕Ý❉ m, ➑ ã❞ P1,P2,. . ., Pk ✌✍✦ë, ➓➆➅▼ k ≤ m. ➇ k = m ➈,P1,P2,. . ., Pk ➉➆➊❨✖ÿ➼ ÛÜ , ★❡ X = (x1, x2, . . . , xk, 0, . . . , 0)T ❉â✫✕ÿ➼❳➌❏. ➇ k < m ➈, ➓✖➔❳★✾ûá ã❥❞❤✹❥ü✡■ m − k ✗✡✿ P1,P2,. . ., Pk ✖✁➋➊❨ A ✕✡✖✡é✡ê✡✌✡✍✡✦✡ë❤ã❥❞✡è, ✾✡â✡✫✡✕✡❏ ➉❉ X, ❵✁❛✡➔✡➐✡❳✁❾ X ❉✡ÿ✡➼✡❳✡➌✡❏. ✜✁◆ 2.1.3 ✵✁❂✁❯✁❱✧❲☛❳ (1.1)✪ (1.2)✪ (1.3) ✬✁✇✁①✁❨✁❩✁❬ X ⑧✁⑨✁➌✁❨✁❩✁➍ D ✬✁➎✁✮. ✜✁◆ 2.1.4 ✵s❂s❯s❱t❲✉❳s✰s➏s❨s❩s❬, ✸s➐s➏s✇s①s❨s❩s❬, ➑✉✵s❂s❯s❱t❲✉❳s✬s❨s❩s➍ D ➒ ❭✁✩, ✸✁➐✁➏✁➎✁✮. ✜✁◆ 2.1.5 ✵✁❂✁❯✁❱✧❲☛❳ (1.1)✪ (1.2)✪ (1.3) ✰✁➏✁➓✁➔✁❬, ✸✁✭✁→✁❨✧➣☛↔✁❨✁❩✁➍ D ✬✁➎✁✮ (↕✁✮) ✶✁➙✁➛. ➜ ➏✡ï✬↔✡✗✡➔✡✩✡➠✡❄✡✑✡➈✁❝✡▼✡é✡➣✁➝✡❯✡❢ÒÑÓ➹✡Ô✡Õ✡ý✡✚✡✵, ✾✁✞✡➣✡❄✡❯. ❡✡✑✡➈✟✁➞ ❋❈✾❴✞❈➣❈❬❈❢ Ñ✬➹❈Ô❈Õ❈Ö❈♠❈✚❈✵, ➓❈✖❈➔❈❳❈ä❴➟❈♠❈✖❈✗❈é❈➣ X ❢ Ñ✬➹❈Ô❈Õ❈ý❈Ö❈♠❈✚❈✵. ➠ ✟❾✡✖✡❿✡❾✡➀✡➁❤✹❥✕✁➠ 5 ✹❥▼✁➡✡✜✡❏✁➈✡✕✁➢✁➤. ❵s❛✢↔✢✗✢➔✢✩✢ï ✟s➞✖✢✗✢✌✢✍✢✎✢✏✢❑✢▲✢▼✢✚✢✵✢❏✢ïÓ↕✢➙s❝✢✣✢❋✢ÿ✢➼✢❳✢➌✢❏✺✹✉➥s➟s❣ ❳ (➦✢✴✢❄✢✑✢ÿ✢➼✢❳✢➌✢❏✢✕✢❏s➧✢▼✢❳✢❯✢❉✢✚✢✵✢❏). ❤❉✢ÿ✢➼✢❳✢➌✢❏✢✚s➡✢▼ C m n ✗, ➛✢ÿ ➼✡❳✡➌✡❏✡✖✡✖✁➨✁➩✡ï✬▼✁➫✁➭✁➯✁➅✡✼✡✚✡✵✡❏. ➲✁➇ n ✮ m ➳✡ê✁➈✡ï✬ÿ✡➼✡❳✡➌✡❏✡✕✡✗✡Õ✡✳✡✴ ✑✢✖✢✗s➵✢ê✢✕✢Õ✢ï ☛ ä✢✖✢✖s➨s➩✢ÿ✢➼✢❳✢➌✢❏✢✕✢✯✢✰✢❞s➸✢ê. ➯❏ ➂✢➃✢✕✢❀✢❁✢❂✢❃s➵✢✽✢✕ ❏✡❛✡➊✡↔✡✗✡❑✡▲✡ï✬✾✡ÿ✡➼s➺✁➻s▲✡✑✢➛s➇✠ ✕✢ÿ✡➼✢❳✢➌✡❏s➼✁➽✢❨ ÑÓ➹✢Ô✢Õ✡ýs➾✡✵✢✕✢ÿ✡➼✢❳ ➌❈❏❈ï ↔❴➚❴➪❴➪❴➨❴➩❈❯❴➶✡❢❈✼ÒÑÓ➹❈Ô✡Õ✁➹➢ ✕❈ÿ✡➼✡❳❈➌✡❏✡ï➴➘❴➷✡➊✁➬❴➮✡❞✡ï➴➱❈❲✡➊✡✯❈✰✡❘ ✲. §2.2 ⑥⑧⑦⑧⑨⑧⑩⑧❶⑧❷⑧❸❐✃❐❒ ❮✁❰➹✡➘✡➪✡✕✡✌✡✍✡✎✡✏✡❑✡▲: max z = CX (2.6) ➴✡➷ ( AX = b X ≥ 0 (2.7) â✡✌✡✍✡✎✡✏✡❑✡▲✡✕✡✖✡è✡❳✡➌✡ÿ, ❄✁➃Úÿ✡❝✡❞✡❉ x1, x2, . . . , xm, à A = (B, N), ✾❤✹ B = (P1, P2, . . . , Pm) ❉✡ÿÜ , N = (Pm+1, . . . , Pn) ❉✁✡✡ÿ✡❝✡❞✡â✡✫✡✕Û✡Ü. ➛ C ✮ X Ï ✫✡➇✁Ð✁Ñ✡❉: C = (CB, CN ), X = (XB, XN ) T
4 第二章单纯形法 其中CB,XB分别为C和X中与m个基变量对应的分量组成的m维向量，Cv,Xw分别 为C和X中与n-m个非基变量对应的分量组成的n-m维向量，则约束方程AX=b 可以写为： aN(Xe）= 利用分块矩阵的乘法可得： BXB+NXN=6 两边乘以B1,得： XB+B-INXN B-1b 移项可得： XB=B-1b-B-INXN 目标函数z=CX可表示为： cc) CBXB+CNXN 把XB=B-b-B-1NXw代入上式得 z=CB(B-16-B-INXN)+CNXN CBB-1b+(CN-CBB-IN)XN 据此原线性规划问题可转换为如下等价形式 min 2=CBB-b+(CN-CBB-IN)XN (2.8) 满足 XB+B-1VXw=B-b X20 (2.9 显然上式与原问题完全等价，即两个问题的解完全相同，称上述问题为可行基1,2，工n 对应的典式对非基变量，令 g=B-lB=(@a吃，am) 并令 B-1b=(,,,n) 则 B-N =B-1(Pm+1.Pm+2.....Pn)=(B-IPm+1,B-1Pm+2.....B-1Pn) ai,m+1 1n =(Pm+1,Pm+2,'.,P)= m+1a吃，m+2…a吃.n m+1 dm.m+2
4 ò✡ó✡ôöõ✡÷✡ø❤ù ✾î✹ CB, XB ✤❈➾❈❉ C ✮ X ✹ç✿ m ✗❈ÿ❈❝❈❞❈â❈✫❈✕❈✤❈❞❈è❈❨❈✕ m Òîãç❞, CN , XN ✤❈➾ ❉ C ✮ X ✹❥✿ n − m ✗✁✡✡ÿ✡❝✡❞✡â✡✫✡✕✡✤✡❞✡è✡❨✡✕ n − m Ò❤ã❥❞, ➓✡❪✡❫Þ✡ß AX = b ❳✡ä✡å✡❉: (B, N) XB XN ! = b Ó ✭✡✤✁ÔÛ✡Ü✕✁Õ✡❃✡❳✡✼: BXB + NXN = b ➋✁Ö✁Õ✡ä B−1 , ✼: XB + B −1NXN = B −1 b ×✁Ø❳✡✼: XB = B −1 b − B −1NXN ÑÓ➹✡Ô✡Õ z = CX ❳✁Ð✁Ñ✡❉: z = (CB, CN ) XB XN ! = CBXB + CN XN ➛ XB = B−1 b − B−1NXN Ù✁Ú❬✁Û✡✼ z = CB(B −1 b − B −1NXN ) + CN XN = CBB −1 b + (CN − CBB −1N)XN ❛þ✁Ü✌✡✍✡✎✡✏✡❑✡▲✡❳✁Ý✁Þ✡❉✟✁ß②✁à✡❂✁Û: min z = CBB −1 b + (CN − CBB −1N)XN (2.8) ➴✡➷ ( XB + B−1NXN = B−1 b X ≥ 0 (2.9) á✴❬➂Û✿Ü❑▲➂â➂ã②➂à, ❣➋✗❑▲✕❏➂â➂ã➂Ï➂ä, ➱❬☞ ❑▲❉❳➌ÿ x1 , x2, . . . , xm â✡✫✡✕✏å✁æ. â✁✡✡ÿ✡❝✡❞ xj , à P 0 j = B −1Pj = (a 0 1j , a 0 2j , . . . , a 0 mj ) T ➠✡à B −1 b = (b 0 1 , b 0 2 , . . . , b 0 m) T ➓ B −1N = B−1(Pm+1, Pm+2, . . . , Pn) = (B −1Pm+1, B −1Pm+2, . . . , B −1Pn) = (P 0 m+1, Pm+2, 0 . . . , P 0 n) = a 0 1,m+1 a 0 1,m+2 . . . a 0 1,n a 0 2,m+1 a 0 2,m+2 . . . a 0 2,n . . . . . . . . . . . . a 0 m,m+1 a 0 m,m+2 . . . a 0 m,n
$2.2线性规划问题的典式 5 (2.10) 与=rg=Gn-=m+1 (2.11) 0=-j=m+1,n (2.12) 则典式可以写成： max 2=20十(Cm+1-2m+1)Em+1十.·+(Cm-2nEn 满足 十xm+1P%+1+.+工nP%=,i=1,2,,m X>0 max z=20+(cm+1-2m+1)江m+1+…+(cn-zn)zn tai.m+im++ai.m+2m2+..+ai.nin= T2 +a.m+1工m+1+a吃.m+2m+2十…+吃.n工n=的 满足 (2.13) +dn.m+1m+1+dn.m+2m+2+…+dnnn=n ≥0，j=1,2,,n 典式的基本特征为约束条件方程中基变量对应的列向量构成单位矩阵（每个约束条件方 程中仅有一个基变量的系数不为0，我们称这个基变量为这个约束条件方程对应的基变 量)，且目标函数中基变量的系数为0.上面把原问题转换为典式的过程称为枢运算.令非 基变量工m+ 为零，则很容易从典式直接得到基变量的值及其对应的目标值。从而 可确定一基本解为计算方便，对任一组基变量对 应的典式，都可用单纯形表来表示（表格形式的典式）.下面为典式(1.13)对应的单纯 形 Cm+l Cm+2 1E2.Em Im+1 工m42 10.0 d.m+1 d.m+2 0 1 0 d2,m+1 2.m+2 Cm Im 0 0… 1 am.m+1 dm.m+2 C1 C2...Cm 2m+1 2m+2 00 单纯形表中最上边一行为原问题的目标函数中决策变量的系数，表中第3行至倒数第 行间的每一行对应典式的一个约束条件方程。表中最下边一行为典式的目标函数中决策 变量的系数，我们称为检验数.CB所在列为各行基变量在原问题目标函数中的系数江B 所在列为各行对应的基变量，b所在列为各行基变量的取值
§2.2 ❥✁❦✁❧✁♠✧♥☛♦✧♣☛q✧r 5 à z0 = CBB −1 b = Xm i=1 c 0 i b 0 i , (2.10) zj = CBB −1Pj = CBP 0 j = Xm i=1 c 0 ia 0 ij , j = m + 1, . . . , n. (2.11) σj = cj − zj , j = m + 1, . . . , n, (2.12) ➓✁ç✁Û✡❳✡ä✡å✡❨: max z = z0 + (cm+1 − zm+1)xm+1 + . . . + (cn − zn)xn ➴✡➷ ( xi + xm+1P 0 m+1 + . . . + xnP 0 n = b 0 i ,i = 1, 2, . . . , m X ≥ 0 ➒ max z = z0 + (cm+1 − zm+1)xm+1 + . . . + (cn − zn)xn ➴✡➷ x1 +a 0 1,m+1xm+1 + a 0 1,m+2xm+2 + . . . + a 0 1,nxn = b 0 1 x2 +a 0 2,m+1xm+1 + a 0 2,m+2xm+2 + . . . + a 0 2,nxn = b 0 2 . . . . . . . . . . . . xm +a 0 m,m+1xm+1 + a 0 m,m+2xm+2 + . . . + a 0 m,nxn = b 0 m xi ≥ 0, j = 1 , 2, . . . , n (2.13) çsÛ✢✕✢ÿ✢➼✢➽sè✢❉✢❪✢❫❴✢❵✢Þ✢ß ✹✻ÿ✢❝✢❞✢â✢✫✢✕✢á✺ã✻❞➊❨✢❀séÛ✢Ü (ê✢✗✢❪✢❫❴✢❵✢Þ ß ✹✉➪✢▼✢✖✢✗✢ÿ✢❝✢❞✢✕s➄✢Õ✢❄✢❉ 0, ↕✢➙➱↔✢✗✢ÿ✢❝✢❞✢❉✢↔✢✗✢❪✢❫❴✢❵✢Þß â✫✢✕ÿ✢❝ ❞), æ ÑÓ➹✡Ô✡Õ❤✹❥ÿ✡❝✡❞✡✕✁➄✡Õ✡❉ 0. ❬❏ ➛Ü❑✡▲✁Ý✁Þ✡❉✁ç✁Û✡✕✁ëß➱❉íì✁î✁ï. à✁✡ ÿ✡❝✡❞ xm+1, . . . , xn ❉✁☞, ➓✁➵✁ð✁ñ✡★✁ç✁Û✡➅✁ò✡✼✡♠✡ÿ✡❝✡❞✡✕✡ý✁ó✡✾✡â✡✫✡✕ÒÑÓ➹✡ý, ★✡❡ ❳✁ô✡➔✡✖✡ÿ✡➼✡❏. ❉✡✯✡✰Þ✁õ, â✁❊✡✖✡è✡ÿ✡❝✡❞✡â ✫✡✕✁ç✁Û, ❢✡❳✡✭✡❀✡❁✡❂✁Ð✁ö✁Ð✁Ñ (Ð✁÷✡❂✁Û✡✕✁ç✁Û). ß❏ ❉✁ç✁Û (1.13) â✡✫✡✕✡❀✡❁ ❂✁Ð: cj → c1 c2 . . . cm cm+1 cm+2 . . . cn cB xB b x1 x2 . . . xm xm+1 xm+2 . . . xn c1 x1 b 0 1 1 0 . . . 0 a 0 1,m+1 a 0 1,m+2 . . . a 0 1,n c2 x2 b 0 2 0 1 . . . 0 a 0 2,m+1 a 0 2,m+2 . . . a 0 2,n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . cm xm b 0 m 0 0 . . . 1 a 0 m,m+1 a 0 m,m+2 . . . a 0 m,n zj c1 c2 . . . cm zm+1 zm+2 . . . zn cj − zj 0 0 . . . 0 cm+1 − zm+1 cm+2 − zm+2 . . . cn − zn ❀✢❁✢❂sÐ✺✹✻✚✢❬sÖ✢✖✢➌✢❉Ü❑✢▲✢✕ Ñ ➹✢Ô✢Õ✺✹✻❛✢❜✢❝✢❞✢✕s➄✢Õ, Ð✺✹✻❾ 3 ➌✢❆sø✢Õ✢❾ 3 ➌sù✢✕sê✢✖✢➌✢â✢✫sçsÛ✢✕✢✖✢✗✢❪✢❫❴✢❵✢Þ✢ß. Ð✺✹✻✚ßÖ✢✖✢➌✢❉sçsÛ✢✕ Ñ ➹✢Ô✢Õ✺✹✻❛✢❜ ❝✢❞✢✕s➄✢Õ, ↕✢➙➱❉✻úsûsü. CB ☛ ❋✢á✢❉✢③✢➌✢ÿ✢❝✢❞✢❋Ü❑✢▲ Ñ ➹✢Ô✢Õ✺✹✻✕s➄✢Õ,xB ☛ ❋✡á✡❉✡③✡➌✡â✡✫✡✕✡ÿ✡❝✡❞,b ☛ ❋✡á✡❉✡③✡➌✡ÿ✡❝✡❞✡✕✡ü✡ý