第二章单纯形法 如前所述，线性规划是运筹学的一个发展最早的重要分支，无论从理论、应用和计算 的角度， 线性规划仍然是最优化技术中发展得最好的一个分支，其发展与单纯形算法是分不 开的.至今为止，在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. 00}非空，则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 ☛ ❋✡á✡❉✡③✡➌✡ÿ✡❝✡❞✡✕✡ü✡ý
6 第二章单纯形法 在单纯形表中，枢运算直接利用矩阵的初等变换进行计算，而检验数的计算可以直 接用公式(11)和(1.12)计算，也可以把检验数行与约束条件同等对待，直接进行初等 变换将检验数行中基变量对应的检验数变为0（新基本可行解对应的典式的目标函数中决 策变量的系数)，则G一与行中的数即为各变量对应的检验数 典式中有关系数的经济解释 取非基变量xm+k,k≥1，令xm+k=1,其它非基变量仍然为0，由典式可直接得到： （x1=以-m+ 2=-dm+ 工m=in-dn,m+h 而目标函数的取值为 2=20+(cm+k-2m+) 可见典式中非基变量xm+k的系数m+k为增加1单位的工m+k后使得第i行的基变量 减少的数量，而检验数cm+k一2m k则为增加一单位的工m+k后目标函数的变化量.从 经济的角度看，为了从事第m+k项活动1单位，需要消耗一套资源，因此需要减少当前 活动的数量以获得这一套资源，am+k就是为了获得从事第m+k项活动的一套资源而 减少的第i行的基变量对应的活动的数量.i项活动的数量：减少 对相妮函数的院献将损尖6因比为了获得从事小十大现活动止检修珠衫 套资源，目标函数将损失的数量（在经济上称为活动m+的机会费用为 cdt=Gm以t=Carp=ah 可见式(1.11)中名值的经济意义就是第)个活动的机会费用.另外从事第m+k项活动 1单位对目标函数的贡献为cm+k,因此从事第m+k项活动1单位而使得目标函数的变 化量为cm+k一2m+k,这就是工m+k的检验数 $2.3单纯形法 单纯形法的基本思路 找到一个基本可行解判断该基本可行解是否为最优解若不是最优解则过渡到另 更优的基本可行解重复上述步骤，直到找到最优解或判断不存在最优解为止 这样我们需要解决三个问题： 1.如何找到第一个基本可行解（称为初始基本可行解）： 2.判定一个基本可行解是否为最优解的判定准则（最优检验准则）月 3.如何在现行基本可行解的基础上得到新的基本可行解 我们以第一章例2的模型为例说明单纯形法的基本步骤。把第一章例2的模型化为
6 ò✡ó✡ôöõ✡÷✡ø❤ù ❋✢❀✢❁✢❂sÐ✺✹✻ïþý✢✒✢✰✢➅sòÓ ✭Û✢Ü✕sÿ✢②✢❝sÞ➢ ➌✢✯✢✰✢ïÓ❡s➨s➩✢Õ✢✕✢✯✢✰✢❳✢ä✢➅ ò✢✭✁sÛ (1.11) ✮ (1.12) ✯✢✰✢ï✖➧✢❳✢ä✢➛s➨s➩✢Õ✢➌✢✿✢❪✢❫❴✢❵ä✢②✢â✁✂✢ï✬➅sò➢ ➌sÿ✢② ❝✁Þ☎✄✁➨✁➩✡Õ✡➌❤✹❥ÿ✡❝✡❞✡â✡✫✡✕✁➨✁➩✡Õ✡❝✡❉ 0(✆✡ÿ✡➼✡❳✡➌✡❏✡â✡✫✡✕✁ç✁Û✡✕ÒÑÓ➹✡Ô✡Õ❤✹❥❛ ❜✡❝✡❞✡✕✁➄✡Õ)ï✬➓ cj − zj ➌❤✹❥✕✡Õ✁❣✡❉✡③✡❝✡❞✡â✡✫✡✕✁➨✁➩✡Õ. ç✁Û❤✹❥▼✡ë✁➄✡Õ✡✕✡✇✡①✡❏☎✝: ü✁✡✡ÿ✡❝✡❞ xm+k,k ≥ 1, à xm+k = 1, ✾✁✞✁✡✡ÿ✡❝✡❞✡✳✡✴✡❉ 0, ❽☛ç✁Û✡❳✡➅✁ò✡✼✡♠: x1 = b 0 1 − a 0 1,m+k x2 = b 0 2 − a 0 2,m+k . . . . . . xm = b 0 m − a 0 m,m+k ❡ÒÑÓ➹✡Ô✡Õ✡✕✡ü✡ý✡❉ z = z0 + (cm+k − zm+k). ❳☎✞✁ç✁Û❤✹☛✡✡ÿ✡❝✡❞ xm+k ✕✁➄✡Õ a 0 i,m+k ❉☎✟✁➱ 1 ❀✁é✡✕ xm+k ➯✡❢✡✼✡❾ i ➌✡✕✡ÿ✡❝✡❞ xi ➘✁➷✡✕✡Õ✡❞, ❡✁➨✁➩✡Õ cm+k − zm+k ➓✡❉☎✟✁➱✡✖✡❀✁é✡✕ xm+k ➯ÒÑÓ➹✡Ô✡Õ✡✕✡❝✡✶✡❞. ★ ✇✡①✡✕✡✱✡✲☎✠, ❉✡➊✡★✡✈✡❾ m + k Ø☎✡☎☛ 1 ❀✁é, ☞✡✣☎✌☎✍✡✖☎✎☎✏☎✑, ❤þ☞✡✣✁➘✁➷✁➇✠ ✡☎☛✕✡Õ✡❞✡ä☎✒✡✼✡↔✡✖☎✎✁✏☎✑, a 0 i,m+k ▲✡✑✡❉✡➊☎✒✡✼✡★✡✈✡❾ m + k Ø☎✡☎☛✕✡✖☎✎☎✏☎✑✡❡ ➘✁➷✡✕✡❾ i ➌✡✕✡ÿ✡❝✡❞✡â✡✫✡✕✡☎☛✕✢Õ✢❞. i Ø☎✡☎☛✕✡Õ✡❞ xi ➘✁➷ a 0 i,m+k ❀✁é, ➏☎✓✡P xi âÒÑÓ➹✡Ô✡Õ✡✕☎✔☎✕☎✄☎✖✡ñ cia 0 i,m+k , ❤þ❉✡➊☎✒✡✼✡★✡✈ m + k Ø☎✡☎☛ 1 ❀✁é☛ ☞✡✕✡✖ ✎☎✏☎✑, ÑÓ➹✡Ô✡Õ☎✄☎✖✡ñ✡✕✡Õ✡❞ (❋✡✇✡①✡❬➱❉✡☎☛ m + k ✕✘✗☎✙☎✚☎✛) ❉ Xm i=1 cia 0 i,m+k = CBP 0 m+k = CBB −1Pm+k = zm+k. ❳☎✞✁Û (1.11) ✹ zj ý✡✕✡✇✡①✡➏✡➐✁▲✡✑✡❾ j ✗ ✡☎☛✕✡◗☎✜☎✢✡✭. ✣☎✤✡★✡✈✡❾ m + k Ø☎✡☎☛ 1 ❀✁é✡âÒÑÓ➹✡Ô✡Õ✡✕☎✔☎✕✡❉ cm+k, ❤þ★✡✈✡❾ m + k Ø☎✡☎☛ 1 ❀✁é✡❡✡❢✡✼ÒÑÓ➹✡Ô✡Õ✡✕✡❝ ✶✡❞✡❉ cm+k − zm+k, ↔✁▲✡✑ xm+k ✕✁➨✁➩✡Õ. §2.3 ✥✧✦✧★✧✩ ❀✡❁✡❂✡❃✡✕✡ÿ✡➼✁➺✁➻: ➟✡♠✡✖✡✗✡ÿ✡➼✡❳✡➌✡❏, ✪☎✫☎✬☎✭☎✮☎✯☎✰☎✱☎✲☎✳☎✴☎✵☎✶☎✱; ✷☎✸☎✲☎✵☎✶☎✱☎✹☎✺☎✻☎✼☎✽☎✾ ✿ ✶☎❀☎✭☎✮☎✯☎✰☎✱. ❁☎❂☎❃☎❄☎❅☎❆, ❇☎✼☎❈☎✼☎✵☎✶☎✱☎❉☎✪☎✫☎✸☎❊☎❋☎✵☎✶☎✱☎✴☎●. ❍☎■☎❏☎❑☎▲☎▼✱☎◆☎❖☎P☎◗☎❘: 1. ❙☎❚☎❈☎✼☎❯☎✾☎P☎✭☎✮☎✯☎✰☎✱ (❱☎✴☎❲☎❳☎✭☎✮☎✯☎✰☎✱); 2. ✪☎❨☎✾☎P☎✭☎✮☎✯☎✰☎✱☎✲☎✳☎✴☎✵☎✶☎✱☎❀☎✪☎❨☎❩☎✹ (✵☎✶☎❬☎❭☎❩☎✹); 3. ❙☎❚☎❋☎❪☎✰☎✭☎✮☎✯☎✰☎✱☎❀☎✭☎❫☎❃☎❴☎✼☎❵☎❀☎✭☎✮☎✯☎✰☎✱. ❏☎❑☎❛ ❯☎✾☎❜☎❝ 2 ❀☎❞☎❡☎✴☎❝☎❢❤❣❥✐☎❦☎❧☎♠☎❀☎✭☎✮✁❅☎❆. ♥☎❯☎✾☎❜☎❝ 2 ❀☎❞☎❡☎♦☎✴
$2.3的典式法 标行型： maxz=40x1+45x2+24x3 2红1+3x2+3+z4 =100 31+32+2z +z5=120 (x≥0基一本j. 充要零量所对应亲数列向 基一个关必要由问题，则知立】 可m个变妨系为一变妨只条点问题必若时怡 为一变妨构 充则得一点解 工1 0 为一点解于则是一点可若解.基城极有必即为“≤”规的关必要由问题。在最题为标 行型优定一个城极有必以在顶达到才一个：找变妨.若例找变妨为一变妨，则多情况 得到一寻一点可若解点只时恰x4, 6为一变妨，则得一寻不可若解 1=2=g=0,x4=100,6=120 虽也检验限同题的标行型次为问一点可解基后的但较很为这但后的单性 规思（问题单性规思）： 思2-1 404524 0 0 CB T3 100 2与 C-2 40 45 24 路要调整更样仅够 线上解非行卿 (关必由间题(1.6).(1.7)，若一点可若解X'基后的但的标函少必搜一变 妨的加即典满 C-CBB-1B≤0 则一点可若解X'为限问题的线上解 ②，基泰必雾由向题(1.6,17，若一点可若解X蒸后的但的函少必所式搜 一变妨的加满 CN-CBB-1P≤0 考式-搜一变妨的加少衡和。：一头=0，则限何鄂式相表寻线上解 ③若一点可若解X基后煦但的标函少履一变妨的加少示于零考4茶 后的列向妨P以=B-1P≤0，则问意的解为限界解 证明：().则妨设一点可若解X'的一变妨为1,2，，工m,则基后的但为(1.13
§2.3 ♣☎q☎r❤s 7 t❩☎❡: max z = 40x1 + 45x2 + 24x3 ✉☎✈ 2x1 + 3x2 + x3 +x4 = 100 3x1 + 3x2 + 2x3 +x5 = 120 xj ≥ 0✇☎✾☎① j. ②☎③⑤④☎⑥☎⑦☎⑧☎⑨☎⑩☎❶☎❷☎❸ ✇❹✾❹P❹❺❹❻❹❼❹❽❹◗❹❘, ✸❹❾❹❿❹➀❹➁❹❨ m P❹➂❹➃❹➄❹✴❹✭❹➂❹➃. ❝❹❙❹✮❹◗❹❘➆➅➇✷❹➈❹➉ x1, x3 ✴☎✭☎➂☎➃, ➊ x2 = x4 = x5 = 0, ✹☎❴☎✭☎✮☎✱: x1 = 80, x3 = −60,x2 = x4 = x5 = 0. ➋ ✴☎✭☎✮☎✱, ➌☎✸☎✲☎✭☎✮☎✯☎✰☎✱. ✇☎➍☎➎☎➏☎➐☎➑☎✴ “≤” ❧☎➒☎❀☎❺☎❻☎❼☎❽☎◗☎❘, ❋☎➓☎♦☎✴t ❩☎❡☎➔☎→☎✾☎P☎➍☎➎☎➏☎➐☎➣☎↔☎↕☎➙☎➛☎➜☎➝☎✾☎P☎➞☎➟☎➂☎➃. ✷☎➠☎➞☎➟☎➂☎➃☎✴☎✭☎➂☎➃, ✹☎➡☎➢☎➤ ❴☎✼☎✾☎➥☎✭☎✮☎✯☎✰☎✱. ✮☎❝☎➈☎➉ x4, x5 ✴☎✭☎➂☎➃, ✹☎❴☎✾☎➥☎✭☎✮☎✯☎✰☎✱: x1 = x2 = x3 = 0, x4 = 100, x5 = 120 ➦✁➧✁➨✁➩✁➫◗✁❘✁❀t❩✁❡✁➭✁✴✁❲✁❳✁✭✁✮✁✯✁✰✁✱✁✇✁➯✁❀✁➲✁➒. ➳✁➵✁✴❍✁➸➲✁➒✁✇✁➯✁❀✁✐✁❦ ❧☎➺ (❲☎❳☎✐☎❦☎❧☎➺): ➺ 2–1 cj → 40 45 24 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 100 2 3 1 1 0 0 x5 120 3 3 2 0 1 zj 0 0 0 0 0 cj − zj 40 45 24 0 0 ➻③⑤➼☎➽☎➾☎➚☎➪☎➶ ✵☎✶☎❬☎❭☎❩☎✹: (1). ✇☎❺☎❻☎❼☎❽☎◗☎❘ (1.6),(1.7), ✷☎✭☎✮☎✯☎✰☎✱ X0 ✇☎➯☎❀☎➲☎➒☎❀➘➹ t☎➴☎➷➅➮➬☎✭✁➂ ➃☎❀☎➱➷ ➑☎✃✉☎✈: CN − CBB −1Pj ≤ 0 ✹☎✭☎✮☎✯☎✰☎✱ X0 ✴➫ ◗☎❘☎❀☎✵☎✶☎✱. (2). ✇☎❺☎❻☎❼☎❽☎◗☎❘ (1.6),(1.7), ✷☎✭☎✮☎✯☎✰☎✱ X0 ✇☎➯☎❀☎➲☎➒☎❀➘➹ t☎➴☎➷➅➮❐☎❒✁➬ ✭☎➂☎➃☎❀☎➱➷☎✉☎✈: CN − CBB −1Pj ≤ 0 ❮ ❒☎✾☎➬☎✭☎➂☎➃☎❀☎➱➷☎✉☎✈ ck − zk = 0, ✹➫ ◗☎❘☎❒☎❰☎Ï☎Ð☎➥☎✵☎✶☎✱. (3). ✷☎✭☎✮☎✯☎✰☎✱ X0 ✇☎➯☎❀☎➲☎➒☎❀➘➹ t☎➴☎➷➅❥➬☎✭☎➂☎➃ xk ❀☎➱➷☎Ñ☎Ò☎Ó❮ xk ✇ ➯☎❀☎Ô❤Õ❥➃ P 0 k = B−1Pk ≤ 0, ✹➫ ◗☎❘☎❀☎✱☎✴☎❰☎Ö☎×☎✱. Ø☎Ù: (1). ✸☎Ú☎Û☎✭☎✮☎✯☎✰☎✱ X0 ❀☎✭☎➂☎➃☎✴ x1, x2, . . . , xm, ✹☎✇☎➯☎❀☎➲☎➒☎✴ (1.13)
8 第二章单纯形法 任取一非基变量xk,令k=9≥0，xk以外的非基变量为0.则得如下解X: x=/-a{.0 =品-2 (2.14) Im =bin -am.ko =0 取0>0充分小，则可使得”，，”≥0，即现行解X”仍然为可行解此可行解对应的 目标函数值为=和+(C-)0.因为ck一0充分小，则 可使得X"仍然为可行解.因为c-=0,所以z”=0+(C一2)8=0.可见存在另 可行解X”与最优解X'有相同的目标值，即x“也是最优解、易证对任意的0≤a≤1 X=aX'+(1-a)X”仍为原问题的最优解，从而原问题有无穷多组最优解. (3.不妨设基本可行解X'的基变量为x1,x2,,xm,则对应的典式为(1.13).令非 基变量x以 0>0,x以外的非基变量为0，则得(1.14.因为(a1k,2, 由式(1.14)知任意xk=0>0,都使得1, 4药防幸花好 对应的目标函数值为2=0+(ck-4)9.因 ,4>0,所以2=20+(c-2)9> ·可见k能无限制的增加而不影响问 题的可行性，目标函数的值也随着(C:一2)9而无限制的增加，因此原问题有无限界解、· 三、基可行解的改进 如果典式的目标函数中非基变量的系数即非基变量的检验数中至少有一个大于零不 妨设非 基变量xk的检验数k-CBB-1P>0,且B1B中至少有一个分量大于零.由最 优检验准则得知，当前的基本可行解还不是最优解，此时需要对基本可行解改进，以便得 到另一个较优的基本可行解 改进基本可行解的方法是在非基变量中选择一个变址让它变为基变量（称为换人变 量)，再从原基变量中选择一个变量（称为换出变量），让它变为非基变量，得到一个新的基 本可行解 1,人量的确定 选择换入变量的基本原则是将变量换入后，得到一组使得目标函数较优的新的基本 可行解由最优检验准则的证明可知，选择检验数满足 c-CBB-1>0,且B-1P至少有一分量大于0 的非基变量xk进入基后，将使得目标函数的值增加.可见当非基变量k的检验数为大于 零的数时，将其换入可使得目标函数的值增加，此时可选择该非基变量为换入变量 一般选择换入变量的原则是选择检验数最大的那个非基变量在用计算机解线性规 划问题时，依次计算每个变量的检验数，第一个使得检验数大于0的那个非基变量就被选 择为换入变量.这样就不必将全部检验数计算出来后再选择最大的检验数，从而减少迭代 时间
8 Ü☎Ý☎Þß♣☎q☎r❤s ❿☎➠☎✾☎➬☎✭☎➂☎➃ xk, ➊ xk = θ ≥ 0,xk ❛☎à❀☎➬☎✭☎➂☎➃☎✴ 0. ✹☎❴☎❙☎➳☎✱ X00: x 00 1 = b 0 1 − a 0 l,kθ x 00 2 = b 0 2 − a 0 2,kθ . . . . . . x 00 m = b 0 m − a 0 m,kθ x 00 k = θ (2.14) ➠ θ > 0 á☎â☎ã, ✹☎✯☎ä☎❴ x 00 1 , . . . , x 00 m ≥ 0, ➭☎❪☎✰☎✱ X00 å➧ ✴☎✯☎✰☎✱. ➨✯☎✰☎✱☎✇☎➯☎❀ ➹ t☎➴☎➷☎æ✴ z 0 = z0 + (ck − zk)θ. ç☎✴ ck − zk 0 á☎â☎ã, ✹ ✯☎ä☎❴ X00 å➧ ✴☎✯☎✰☎✱. ç☎✴ ck − zk = 0, ❐ ❛ z 00 = z0 + (ck − zk)θ = z0. ✯☎è☎❊☎❋☎✽ ✾ò✯ò✰ò✱ X00 ó✵ò✶ò✱ X0 ❒òôòõò❀ö➹ tòæ, ➭ X00 ÷✲ò✵ò✶ò✱. ➤òñò✇ò❿ò➀ò❀ 0 ≤ α ≤ 1, X = αX0 + (1 − α)X00 å✴➫ ◗☎❘☎❀☎✵☎✶☎✱☎ø⑤í☎î➫ ◗☎❘☎❒☎❰☎Ï☎Ð☎➥☎✵☎✶☎✱. (3). ✸☎Ú☎Û☎✭☎✮☎✯☎✰☎✱ X0 ❀☎✭☎➂☎➃☎✴ x1, x2, . . . , xm, ✹☎✇☎➯☎❀☎➲☎➒☎✴ (1.13). ➊☎➬ ✭☎➂☎➃ xk = θ > 0,xk ❛☎à❀☎➬☎✭☎➂☎➃☎✴ 0, ✹☎❴ (1.14). ç☎✴ (a1,k, a2,k, . . . , am,k) T ≤ 0, ï❥➒ (1.14) ð☎❿☎➀ xk = θ > 0, ➛☎ä☎❴ x1, . . . , xm ≥ 0, ➭☎❪☎✰☎✱å➧ ✴☎✯☎✰☎✱. ➨✯☎✰☎✱ ✇☎➯☎❀➘➹ t☎➴☎➷☎æ✴ z 0 = z0 + (ck − zk)θ. ç ✴ ck − zk > 0, ❐ ❛ z 0 = z0 + (ck − zk)θ > z0. ✯☎è xk ❾☎❰☎Ö☎ù☎❀☎ú☎➜☎î☎✸☎û☎ü☎◗ ❘☎❀☎✯☎✰☎❻, ➹ t☎➴☎➷❀æ÷☎ý☎þ (ck − zk)θ î☎❰☎Ö☎ù☎❀☎ú☎➜, ç➨☎➫◗☎❘☎❒☎❰☎Ö☎×☎✱. ÿ③⑤⑨☎❶☎❷☎❸✁✁✂✁✄ ❙✆☎ò➲ò➒ò❀ö➹ tò➴ò➷➅➬ò✭ò➂ò➃ò❀ò➱➷ ➭ò➬ò✭ò➂ò➃ò❀ò❬ò❭➷ ➅✞✝✆✟ò❒ò✾òPÑòÒòÓ, ✸ Ú☎Û☎➬ ✭☎➂☎➃ xk ❀☎❬☎❭➷ ck − CBB−1Pk > 0, ❮ B−1Pk ➅✠✝✁✟☎❒☎✾☎P☎â☎➃Ñ☎Ò☎Ó. ï❥✵ ✶✁❬✁❭✁❩✁✹✁❴✁ð, ✡☞☛✁❀✁✭✁✮✁✯✁✰✁✱☞✌✁✸✁✲✁✵✁✶✁✱, ➨✁➩▲✁▼✇✁✭✁✮✁✯✁✰✁✱☞✍✁é, ❛☞✎❴ ✼☎✽☎✾☎P✁✏☎✶☎❀☎✭☎✮☎✯☎✰☎✱. ✍☎é☎✭☎✮☎✯☎✰☎✱☎❀☎➣☎♠☎✲☎❋☎➬☎✭☎➂☎➃❤➅❥➈☎➉☎✾☎P☎➂☎➃, ✑✁✒☎➂☎✴☎✭☎➂☎➃ (❱☎✴✁✓✁✔✁✕ ✖ ), ✗☎í➫ ✭☎➂☎➃❤➅❥➈☎➉☎✾☎P☎➂☎➃ (❱☎✴✘✓✁✙✁✕✖ ), ✑✁✒☎➂☎✴☎➬☎✭☎➂☎➃, ❴☎✼☎✾☎P☎❵☎❀☎✭ ✮☎✯☎✰☎✱. 1. ✓✁✔✁✕✖☎④☎⑥ ➈✁➉☞✚✁ê✁➂✁➃✁❀✁✭✁✮➫ ✹✁✲✁ë✁➂✁➃☞✚✁ê✁➔, ❴✁✼✁✾✁➥✁ä✁❴ ➹ t✁➴✁➷✏✁✶✁❀✁❵✁❀✁✭✁✮ ✯☎✰☎✱. ï❥✵☎✶☎❬☎❭☎❩☎✹☎❀☎ñ❤❣❥✯☎ð, ➈☎➉☎❬☎❭➷☎✉☎✈ ck − CBB −1Pk > 0, ❮ B −1Pk✝✁✟☎❒☎✾☎â☎➃Ñ☎Ò 0 ❀☎➬☎✭☎➂☎➃ xk é☎ê☎✭☎➔, ë☎ä☎❴➘➹ t☎➴☎➷❀æ ú☎➜. ✯☎è✁✡☎➬☎✭☎➂☎➃ xk ❀☎❬☎❭➷ ✴Ñ☎Ò Ó ❀➷➩ , ë✁✛✁✚☎ê☎✯☎ä☎❴➘➹ t☎➴☎➷❀æ ú☎➜, ➨☎➩✯☎➈☎➉☎✬☎➬☎✭☎➂☎➃☎✴✁✚☎ê☎➂☎➃. ✾☞✜✁➈✁➉☞✚✁ê✁➂✁➃✁❀➫ ✹✁✲✁➈✁➉✁❬✁❭➷ ✵Ñ ❀☞✢✁P✁➬✁✭✁➂✁➃. ❋☞✣☞✤☞✥☞✦✁✱✁❺✁❻✁❼ ❽☎◗☎❘➩ , ✧✁★✁✤✁✥☎→☎P☎➂☎➃☎❀☎❬☎❭➷ , ❯☎✾☎P☎ä☎❴☎❬☎❭➷☎Ñ☎Ò 0 ❀✁✢☎P☎➬☎✭☎➂☎➃✁✩✁✪☎➈ ➉☎✴✁✚☎ê☎➂☎➃. ❍☎■✩☎✸✁✫☎ë☎➑☎✃☎❬☎❭➷ ✤✁✥✁✬✁✭☎➔✁✗☎➈☎➉☎✵Ñ ❀☎❬☎❭➷ , í☎îì ✟✁✮✁✯ ➩✁✰
$2.3单纯形法 9 据此我们选择2为换入变量 2.换出变量的确定 确定换入变量后，我们需要解决两个问题：一个是确定换入变量的最大取值，另一个 是确定一个换出变量使基变量的个数不变 不妨仍然设原问题的基本可行解的基变量为1， m,非基变量xk(之m+1) 为换入变量令4进入基后的取值为>0，令4以外的非基变量取值仍然为0，由典式 的约束条件(113)可直接得到原基变量的取值 x4--a4k8,i-1,2,,m 要得到基本可行解，4的值日>0必须满足 x=-a4k020,i=1,2,,m (2.15) 且上式中至少有一个为零 若a≤0，则必有工≥0 若a>0,则由(1.15)得 令 0(爱>a-时-关 (2.16) ik 显然0满足(1.15)且使得p=0.把产的最小值子对应的钩束条件方程对应的 基变量x从基变量中换出来，可以证明这样得到的一组变量： 1,,p-1,p+1,,mk 仍为可行基.上述按式(116)确定换出变量的方法称为“最小比值规则.这样通过选择 一个换入变量和换出变量，得到了一组新的基本可行解，使得新基本可行解的目标函数较 原基本可行解为优对新的基本可行解进行枢运算，将换入变量对应的列向量变为单位向 量，构造新基本可行解对应的典式.枢运算可直接在单纯形表上利用初等变换得到，具体 方法如下： 设换出变量对应的行为，换入变量对应的列为飞，则令 =,-2,j=1,2mi≠p 响=j=12m 《=成-心杀职-去 号=-4g=12mi≠n
§2.3 ♣☎q☎r❤s 9 ✱➨❏☎❑➈☎➉ x2 ✴✁✚☎ê☎➂☎➃. 2. ✓✁✙✁✕✖☎④☎⑥ ✲❨✁✚☎ê☎➂☎➃☎➔, ❏☎❑☎▲☎▼✱☎◆✁✳☎P☎◗☎❘: ✾☎P☎✲✲❨✁✚☎ê☎➂☎➃☎❀☎✵Ñ ➠æ , ✽☎✾☎P ✲ ✲❨☎✾☎P✁✚✁✬☎➂☎➃☎ä☎✭☎➂☎➃☎❀☎P➷ ✸☎➂. ✸òÚå➧ Û➫ ◗ò❘ò❀ò✭ò✮ò✯ò✰ò✱ò❀ò✭ò➂ò➃ò✴ x1, x2, . . . , xm, ➬ò✭ò➂ò➃ xk (k ≥ qm+1) ✴✁✚☎ê☎➂☎➃. ➊ xk é☎ê☎✭☎➔☎❀☎➠æ ✴ θ > 0, ➊ xk ❛☎à❀☎➬☎✭☎➂☎➃☎➠æå➧ ✴ 0, ï❥➲☎➒ ❀☎➍☎➎☎➏☎➐ (1.13) ✯☎❇✁✴☎❴☎✼➫ ✭☎➂☎➃☎❀☎➠æ : xi = b 0 i − a 0 ikθ,i = 1, 2, . . . , m ▼ ❴☎✼☎✭☎✮☎✯☎✰☎✱, xk ❀æ θ > 0 ✫✁✵✉☎✈ xi = b 0 i − a 0 ikθ ≥ 0,i = 1, 2, . . . , m (2.15) ❮ ❃☎➒❤➅✠✝✁✟☎❒☎✾☎P☎✴Ó . ✷ a 0 ik ≤ 0, ✹✁✫☎❒ xi ≥ 0; ✷ a 0 ik > 0, ✹❤ï (1.15) ❴ θ ≤ b 0 i a 0 ik , i = 1, 2, . . . , m ➊ θ = min{ b 0 i a 0 ik a 0 ik > 0,i = 1, 2, . . . , m} = b 0 p a 0 pk (2.16) ➦☎➧ θ ✉☎✈ (1.15) ❮ ä☎❴ xp = 0. ♥ b 0 i a 0 ik ❀☎✵☎ãæ b 0 p a 0 pk ✇☎➯☎❀☎➍☎➎☎➏☎➐☎➣☎↔☎✇☎➯☎❀ ✭☎➂☎➃ xp í☎✭☎➂☎➃❤➅✠✚✁✬✁✭, ✯ ❛ ñ❤❣❍☎■❴☎✼☎❀☎✾☎➥☎➂☎➃: x1, . . . , xp−1, xp+1, . . . , xm, xk å✴✁✯✁✰✁✭. ❃✁❄☞✶✁➒ (1.16) ✲❨☞✚☞✬✁➂✁➃✁❀✁➣✁♠✁❱✁✴ “✵✁ã✸✷æ ❼✁✹”. ❍✁■☞✹✺✁➈✁➉ ✾☎P✁✚☎ê☎➂☎➃✁✺✁✚✁✬☎➂☎➃, ❴☎✼☎➝☎✾☎➥☎❵☎❀☎✭☎✮☎✯☎✰☎✱, ä☎❴☎❵☎✭☎✮☎✯☎✰☎✱☎❀➘➹ t☎➴☎➷✏ ➫ ✭☎✮☎✯☎✰☎✱☎✴☎✶. ✇☎❵☎❀☎✭☎✮☎✯☎✰☎✱☎é☎✰✁✻✁✼✁✽, ë✁✚☎ê☎➂☎➃☎✇☎➯☎❀☎Ô❤Õ❥➃☎➂☎✴☎✐✁✾❤Õ ➃, ✿✁❀☎❵☎✭☎✮☎✯☎✰☎✱☎✇☎➯☎❀✁➲☎➒. ❁✁❂✁✥☎✯☎❇✁✴☎❋☎✐☎❦☎❧☎➺✁❃✁❃☞✣☎❲☞❄☎➂☞✚✁❴☎✼, ❅✁❆ ➣☎♠☎❙☎➳: Û✁✚✁✬☎➂☎➃☎✇☎➯☎❀☎✰☎✴ p, ✚☎ê☎➂☎➃☎✇☎➯☎❀☎Ô☎✴ k, ✹☎➊ a 0 ij = a 0 ij − a 0 ik a 0 pj a 0 pk , j = 1, 2, . . . , n;i 6= p. a 0 pj = a 0 pj a 0 pk , j = 1, 2, . . . , n. b 0 i = b 0 i − a 0 ik b 0 p a 0 pk ,i 6= p; b 0 p = b 0 p a 0 pk . c 0 j = c 0 j − c 0 k a 0 pj a 0 pk , j = 1, 2, . . . , n;i 6= p
10 阵二章单纯形 把：单用和计算角单表达式代入法其典式单标标函数和约束意义方这形汁直接，得法述 公其 旧典式直称数严间单关称纯形法面单步骤，若原线性规划机题有有限角， 中清限步 经表21解化角 取p=1第其算经应单用变量然换出变量经表21进算框运算，达代出件用和计算 角经应单单纯形表（表2-2） 表2-2 40 4524 0 0 5 15 10 0 -15 表2-2直仍然有 于0单上验数所尚未达得最化，纯形前面步骤，选择工1然换入 变量，了 选择5然换出变量.迭代出件用和计算角经应单单纯形表条表2-3 表2-3 40 24 0 CR T5 2 20 2 21 40 45 25 5 10 0 0 -10 单纯形表2-3直单上羚数全小于等于0，所 ,最化角.最化角然1=20,2=20， ==0,就条单最日利润然40×20+45×羲=1700元 四备单纯形法的计算步骤 了SB,Sw对别表示用变量和非用变量下标单集合. 第等步首先，确定初可用和计算角，建立初可单纯形表，则第二步： 第二步上验各非用变量单上验数=-,jeSN.若)≤0，jSN,中面条最 化角，停止.仍中则第三步： 第步若存在大SN满事：>0且经应单晒数量滑事H≤0中此机题单角 无界，停止.仍中则第四步； 第四步按max{o∈SN}=ok确定换入变量xk,按最小比值规中计算
10 Ü☎Ý☎Þß♣☎q☎r❤s ♥☎❵☎❀☎✭☎✮☎✯☎✰☎✱☎❀☎➺✁❇✁➒☞✯☎ê✁❃✁✾☎➲✁➒☎❀ ➹ t☎➴✁➷✺☎➍✁➎☎➏✁➐✁➣☎↔✁ø⑤✯✁❇✁✴✁❴✁✼☎❃✁❄ ❈ ➒ (❵✁❉☎➲☎➒❤➅❥➱➷✁❊✰ ❀✁❋☎➱). ❁☎❂☎❃☎➵☎❀☎❅☎❆, ✷ ➫ ❺☎❻☎❼☎❽☎◗☎❘☎❒☎❒☎Ö☎×☎✱, ✹☎❒☎Ö☎❅☎➔✁✫☎❴☎✵☎✶☎✱. ✇☎➺ 2–1, ❏☎❑❒ x2 = min{ b 0 1 a 0 12 , b 0 2 a 0 22 } = min{ 100 3 , 120 3 } = 100 3 = b 0 1 a 0 1,2 . ➠ p = 1, ❯☎✾☎✰☎✇☎➯☎❀☎✭☎➂☎➃ x4 ✴✁✚✁✬☎➂☎➃. ✇☎➺ 2–1 é☎✰✁❁✁❂✁✥, ✮✁✯✁✬☎❵☎✭☎✮☎✯☎✰ ✱☎✇☎➯☎❀☎✐☎❦☎❧☎➺ (➺ 2–2) ➺ 2–2 cj → 40 45 24 0 0 cB xB b x1 x2 x3 x4 x5 45 x2 100 3 2 3 1 1 3 1 3 0 0 x5 20 1 0 1 −1 1 zj 30 45 15 15 0 cj − zj 10 0 9 −15 0 ➺ 2–2 ➅å➧ ❒Ñ☎Ò 0 ❀☎❬☎❭➷ , ❐ ❛❍●✠■❇☎✼☎✵☎✶, ❁☎❂✁☛☎➵☎❅☎❆, ➈☎➉ x1 ✴✁✚☎ê ➂☎➃, ➊ x1 = min{ 100 3 2 3 , 20 1 } = 20 ➈☎➉ x5 ✴✁✚✁✬☎➂☎➃. ✮✁✯✁✬☎❵☎✭☎✮☎✯☎✰☎✱☎✇☎➯☎❀☎✐☎❦☎❧☎➺☎❴☎➺ 2–3 ➺ 2–3 cj → 40 45 24 0 0 cB xB b x1 x2 x3 x4 x5 45 x2 20 0 1 − 1 3 1 − 2 3 20 x1 20 1 0 1 −1 1 zj 40 45 25 5 10 cj − zj 0 0 −1 −5 −10 ✐ò❦ò❧ò➺ 2–3 ➅❀ò❬ò❭➷ ➑òãÒ❄ Ò 0, ❐ ❛❑❏❴ò✵ò✶ò✱. ✵ò✶ò✱ò✴ x1 = 20, x2 = 20, x3 = x4 = x5 = 0, ▲☎❴☎❀☎✵Ñ ❃✁▼☎✴ 40 × 20 + 45 × 20 = 1700 ◆. medskip ❖ ③◗P✁❘✁❙✁❚✁✁❯✽✁❱✁❲ ➊ SB, SN â✁❳☎➺✁❨☎✭☎➂☎➃✁✺☎➬☎✭☎➂☎➃☎➳t ❀✁❩✁❬. ❭②❱❫❪✁❴, ✲❨☎❲☎❳☎✭☎✮☎✯☎✰☎✱, ❵✁❛☎❲☎❳☎✐☎❦☎❧☎➺, ➓☎❯✁❜☎❅; ❭➻ ❱ ❬☎❭✁❝☎➬☎✭☎➂☎➃☎❀☎❬☎❭➷ σj = cj − zj , j ∈ SN . ✷ σj ≤ 0, j ∈ SN , ✹ ❏❴☎✵ ✶☎✱, ❞☎●. ✳☎✹☎➓☎❯☎❖☎❅; ❭ÿ ❱ ✷☎❊☎❋ k ∈ SN ✉☎✈ σk > 0, ❮ xk ✇☎➯☎❀☎Ô❤Õ❥➃✉☎✈ P 0 k ≤ 0, ✹➨ ◗☎❘☎❀☎✱ ❰☎×, ❞☎●. ✳☎✹☎➓☎❯✁❡☎❅; ❭ ❖ ❱❫✶ max{σj |j ∈ SN } = σk ✲❨✁✚☎ê☎➂☎➃ xk, ✶☎✵☎ã❍✷æ ❼☎✹✁✤✁✥ θ = min b 0 i a 0 ik a 0 ik > 0 = b 0 p a 0 pk