第二章单纯形法 如前所述，线性规划是运筹学的一个发展最早的重要分支，无论从理论、应用和计算 的角度， 线性规划仍然是最优化技术中发展得最好的一个分支，其发展与单纯形算法是分不 开的.至今为止，在1947年Dantzig提出的单纯形法算法仍是解线性规划问题的最有效的 算法随着计算机的运算速度和贮存能力的快速发展，用单纯形法可解有成干上万个约束 条件和决策变量的线性规划向题，从而使得线性规划的应用已逐渐扩展到工业、农业、交 通运输、军事和经济等各个领域 52.1线性规划问题的几何意义 在第一章第三节中介绍的图解法，已直观地说明了两个和三个变量线性规划问题的 可行域和最优解的儿何意义：若两个或三个变量的线性规划问题的最优解存在，则一定可 在可行域的顶点得到.这一节我们把这一结论推广到一般的线性规划问题，并从理论上作 进一步的讨论和说明. 线性规划问题的解 在进一步讨论之前，我们先介绍线性规划问题解的概念。本章如无特别说明，所讨论 的模型均为标准型： max 2=CX (2.1) 满足AX=b (2.2) X≥0 (2.3) 可行解满足约束条件(1.2).(1.3)的解X=(1,2,工)T称为线性规划问题的可 行解所有可行解的集合叫做可行域 最优解使目标函数(1.1)达到最优的可行解叫做最优解 基本解和基本可行解 设矩阵A=[a]mxn的秩是m,其中n为决策变量数，m为约束条件方程的个数， n>m.令 P=(ang,a2j...,amj) 为矩阵A的第G=1,2,,)列对应的列向量则AX=b可以写成： 且向量组乃，乃，，P的极大线性无关组包含m个向量，不失一般性，设乃，P,,Pm 为其极大线性无关组，则方程组 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
第二章单纯形法 有唯一解(，，，9)T,令其余的变量取值为0，则得到AX=b的一个解，称此解 为线性规划问题(1.1(1.3)的基本解矩阵B=[凸，B,,Pm]称为基本解xo)对应的 基本矩阵，简称基矩阵.1,2，，工m称为基 变量，其它变量称为非基变量.基变量组成的集合称为基若基本解XO)满足 Xo≥0，则称这个解为基本可行解若基本可行解中非零分量的个数小于约束条件方程 的个数m,则称此向题是退化的.如非特别说明，本书中讨论的问题均为非退化的 二、凸集及凸集中的顶点 定义2.11设K是n维欧氏空间中的一点集，若任意两点X1,X2∈K的连线上的任意 一点aX1+(1-a)X2∈K,其中0≤a≤1，则称K为凸集 (a) 图2-1 图2-1中的(a),b为凸集，(c),(d不是凸集 义2.1.2设K为凸集，X∈K.若X不能用不同的两点X1,X2∈K的线性组合表示 为 X=aX1+(1-a)X2 00 从而有 A(aX1+(1-a)X2)=aAX1+(1-a)AX2 ab+(1-a)=b 即X=aX+(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
2.2线性规划问题的典式 3 ,1-a≥0，X1≥0，X2≥0，从而X=aX1+(1-a)X2≥0，即X满足条件(1.5).定 理得证 定理2.12线性规划问题(1.1)，(1.2)和1.3)的可行解X是基本可行解的充要条件是 X的非零分量所对应的桑数列向量线性无关. 证明：必要性由基本可行解的定义即可知结论成立 充分性不妨设可行解X的前k个分量不为0，即X=(1,2，，，0， ,0)FP2 P为X的非零分量所对应的系数列向量。因为矩阵A的秩为m,若向量P,P P线性无关，则必有k≤m.当k=m时，,P,恰构成一基本矩阵，从而 X=(1,2,,k,0,…,0)T为对应的基本可行解.当k<m时则一定可从其余列 向量中取出m一k个与乃，B,,P一起构成A的一极大线性无关向量组，其对应的解 恰为X,根据定义可知X为基本可行解 定理2.1.3线性规划问题(1.1以1.2队、1.3)的基本可行解X对应于可行城D的极点 定理214线性规划问题若有可行解，则必有基本可行解，即线性规刻问题的可行域D 如非空，则必有极点 定理2.1.5线性规划问题(1.1以(1.2队(1.)若有最优解，则一定可以在可行域D的极点 顶点)上达到. 4 注意，这个定理并不是说只有极点才能使目标函数值最优，其它点不能.而是说如果 在其它点上使目标函数达到最优，则一定可以找到一个极点X使目标函数值达到最优例 如第一章第三节中的例5中有多重解时的情祝 根据这个定理，如果一个线性规刻向题有最优解，我们只要在基本可行解中寻找即 可（虽然不是基本可行解的解也有可能为最优解）.因为基本可行解最多有Cm个.把基 本可行解一 检验，有限次后必得最优解但当n和m较大时，基本可行解的个数仍然 是一个很大的数，所以一一检验基本可行解的计算量太大后面介绍的单纯形法很好的 解决了这个问题，其基本思路就是把当前的基本可行解调整成目标函数值更优的基本可 解，这样仅仅检验能够使得目标函数改进的基本可行解减少了搜索量，加快了计算速 度 52.2线性规划问题的典式 考虑标准型的线性规划向题 max :=CX (2.6) 满足 AX=6 1x≥0 (2.7) 对线性规划问题的一组可行基，不妨设基变量为1， xm,令A=(B,N,其中 B=(B,PB,Pm)为基阵N=(Pm+1,,Pn)为非基变量对应的矩阵把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
￥ 第二章单纯形法 不称CB,XB是别或C点X称能m集基只证对中凸是证组可凸m维向证，C,XN是别 题以写支： aN(X）- 利一是块矩阵凸乘组题凸： BXB+NXN=b 两边乘以B-1,凸： XB+B-INXN=B-16 移项题凸： XB=B-1b-B-INXN 目标函数z=CX题表示或： =csc(X知) =CBXB+CNXN 把XB=B-b-B-1VXw代入解式凸 z=CB(B-16-B-INXN)+CNXN =CBB-1b+(CN-CBB-IN)XN 据此原小于退划体就题转换我非下等价性式 min z=CBB-b+(CN-CBB-IN)XN (2.8) 满足 ∫XB+B-lNXN=B-b (2.9) 1X20 式维定会中价明西集体的首完全相同际解零休优汽超行基… 对中凸典式对非基只证工，令 =B-B=(a4g,anm月 并令 B-6=(,，n) B-1N=B-1(Pnm+,Pm+2,,Pn)=(B-1Pm+1,B-1Pm+2,,B-1Pn) a,m+11,m+2… =(Pn+1Pm+2,',P) 2.m+ d.m+2 am.m+1am,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
52.2线性规划问题的典式 5 (2.10) y=CaB-p=cn=∑4，j=m+1,n (2.1) 05=C-j=m+1,,n (2.12) 则典式可以写成： max 2=z0+(cm+ -2m+im+1+…+(cm-n)zn 满足 +m+1Pm+1+.+工nP%=,i=1,2,m X≥0 或 max =20+(cm+1-2m+1)江m+1+..+(cn-n)zn +a1m+1m+1+a1m+2m+2+…+ann= +.m+1正m+1+a吃.m+2m+2+.+吃n工n= 满足 (2.13) 工m+nm+1m+1+amm+2m+2++nnn=m x≥0，j=1,2,n 典式的基本特征为约束条件方程中基变量对应的列向量构成单位矩阵（每个约束条件方 程中仅有一个基变量的系数不为0，我们称这个基变量为这个约束条件方程对应的基变 量)，且目标函数中基变量的系数为0.上面把原问题转换为典式的过程称为枢运算.令非 基变量xm+1,,工m为零，则很容易从典式直接得到基变量的值及其对应的目标值。从而 可确定一基本解为计算方便，对任一组基变量对 应的典式，都可用单纯形表来表示（表格形式的典式）.下面为典式(1.13)对应的单纯 形表 Cm+l Cm+2 工m+1 Im+2 In C1 Z161 10...0 a1.m+l d.m+2 01.n x2b品 01 .,0 a吃，m+1 d吃.m+ …吃 cm工m 001 d'm C1 C2...Cm 2m+1 2m+2 C:-z; 00.，0C41-z41c42-z42 单纯形表中最上边一行为原问题的目标函数中决策变量的系数，表中第3行至倒数第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 ☛ ❋✡á✡❉✡③✡➌✡ÿ✡❝✡❞✡✕✡ü✡ý
第二章单纯形法 在单纯形表中，椒运算古接利用街阵的初等变换讲行计算.而检拾数的计算可以古 接用公式(1.1山)和(1.12)计算，也可以把检验数行与约束条件同等对待，直接进行初等 变换将检验数行中基变量对应的检验数变为0（新基本可行解对应的典式的目标函数中决 策变量的系数)，则G-与行中的数即为各变量对应的检验数 典式中有关系数的经济解释： 取非基变量工m+k,k之1，令工m+=1,其它非基变量仍然为0，由典式可直接得到 （1=-m+ 工2=的-m+k 。。 2'm =bm -dm.mth 而目标函数的取值为 2=20+(cm+k-2m+) 可见典式中非基变量工m+k的系数am+k为增加1单位的m+k后使得第i行的基变量 减少的数量，而检验数cm+k-m+k则为增加一单位的xm+后目标函数的变化量从 经济的角度看，为了从事第m+k项活动1单位，需要消耗一套资源，因此需要减少当前 活动的数量以获得这一套资源m+就是为了获得从事第m+k项活动的一套资源而 减少的第行的基变量对应的活动的数量。i项活动的数量减少。 吃m+单位意味者 工，对目标函数的贡献将损失Gam+,因此为了获得从事m+k项活动1单位所需的 套资源，目标函数将损失的数量（在经济上称为活动m+k的机会费用）为 c-CaPtk=CaB-Pnkmt 可见式(1.11)中值的经济意义就是第方个活动的机会费用.另外从事第m+k项活动 1单位对目标函数的贡献为cm+k,因此从事第m+k项活动1单位而使得目标函数的变 化量为cm+k一zm+k,这就是xm+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单纯形法 7 标准型： max 2 =401+45a2+24r3 2x1+3x2+x3+z4 =100 满足 31+3x2+2x +z5=120 马≥0对-切j 一、确定初始基本可行解 对一个线性规划何题，不能任意指定m个变量作为基变量.例如本何题中若选择 x1,r3为基变量.令r2=r4=c5=0.则得基本解：r1=80,x3=-60,r2=x4=r5=0 虽为基本解但不是基本可行解、对约束条件全为“<”形式的线性规划题在转化为标 准型后每一个约束条件方程左端都加了一个松弛变量.若取松弛变量为基变量，则很容易 得到一组基本可行解本例选择x4,5为基变量，则得一组基本可行解 x1=2=x=0,x4=100,x5=120 显然此时原问题的标准型即为初始基本可行解对应的典式。下面为这种典式对应的单纯 形表（初始单纯形表） 表2-1 40 4524 0 CB 120 2 C,-2 40 45 24 二、最优检验准则 最优检验准则： (1).对线性规划问题(1.6)，(1.7)，若基本可行解X对应的典式的目标函数中非基变 量的系数全部满足 CN-CBB-1≤0 则基本可行解X”为原何题的最优解 (②).对线性规划间题(1.6).(1.7)，若基本可行解X'对应的典式的目标函数中所有非 基变量的系数满足； Cw-CBB-1P≤0 且有一非基变量的系数满足，一k=0,则原问题有无穷多组最优解 (③).若基本可行解X'对应的典式的目标函数中非基变量k的系数大于零且k对 应的列向量P%=B-1P≤0，则原问题的解为无限界解. 证明：(1).不妨设基本可行解X'的基变量为x1,x2,,xm,则对应的典式为(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)
第二章单纯形法 任取一非基变量k,令k=日20，k以外的非基变量为0.则得如下解X =-a9 =的-a2.9 (2.14) T=6 取日>0充分小，则可使得，”≥0，即现行解x”仍然为可行解此可行解对应的 目标函数值为 -)a.因为-40充分小，则 可使得X”仍然为可行解.因为 =0.所以2”=0+(c ·2)=0.可见存在另 一可行解X”与最优解X有相同的目标值，即X”也是最优解.易证对任意的0≤α≤1， X=aX'+(1-a)X"仍为原问题的最优解，从而原问题有无穷多组最优解. (3).不妨设基本可行解X'的基变量为x 1,2,,m,则对应的典式为(113).令非 基变量xk=0>0,xk以外的非基变量为0，则得(1.14).因为(@1k,2k ,amk)T≤0 由式(1.14)知任意xk=0>0,都使得1，，工m≥0，即现行解仍然为可行解此可行解 对应的目标函数值为=0+（一）.因 为c-张>0，所以-0+(一2)>0.可见k能无限制的增加而不影响间 题的可行性，目标函数的值也随着(c一)9而无限制的增加，因此原问题有无限界解.口 三、基可行解的改进 如果典式的目标函数中非基变量的系数即非基变量的检验数中至少有一个大于零，不 妨设 基变量xk的检验数ck-CBB-1P>0,且B-1P中至少有一个分量大于零.由最 优检验准则得知，当前的基本可行解还不是最优解，此时需要对基本可行解改进，以便得 到另一个较优的基本可行解 改进基本可行解的方法是在非基变量中选择一个变量，让它变为基变量（称为换人变 量)，再从原基变量中选择一个变量（称为换出变量），让它变为非基变量，得到一个新的基 本可行解 1.换人变量的确定 选择换入变量的基本原则是将变量换入后，得到一组使得目标函数较优的新的基本 可行解由最优检验准则的证明可知，选择检验数满足 c-CBB-1P>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,2 .,xm,非基变量xk(k之gm+1) 为换入变量令4进入基后的取值为>0，令以外的非基变量取值仍然为0，由典式 的约束条件(113)可直接得到原基变量的取值 x4=-a4,i=1,2.,m 要得到基本可行解，k的值日>0必须满足 x1=-a4020,i=1,2,m (2.15) 且上式中至少有一个为零 若k≤0，则必有≥0 若a4>0,则由(1.15)得 ,i=1,2,,m =k>a=12时-务 (2.16) 显然9满足(L.15)且使得p=0.把的最小值对应的约束条件方程对应的 基变量xp从基变量中换出来，可以证明这样得到的一组变量： 工1，，，，工p-1,工p+1,,,,Cm,Tk 仍为可行基。上述按式(1.16)确定换出变量的方法称为“最小比值规则.这样通过选择 ·个换入变量和换出变量，得到了一组新的基本可行解，使得新基本可行解的目标函数较 原基本可行解为优对新的基本可行解进行枢运算，将换入变量对应的列向量变为单位向 量，构造新基本可行解对应的典式。枢运算可直接在单纯形表上利用初等变换得到，具体 方法如下： 设换出变量对应的行为，换入变量对应的列为k,则令 =-=12i≠ 《=-心杀斯去 号=-4会=12in
§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
0 第二章单纯形法 把新的基本可行解的表达式代入上一典式的目标函数和约束条件方程，可直接得到上述 公式（新旧典式中系数之间的关系）.重复上面的步骤，若原线性规划问题有有限界解 则有限步后必得最优解 对表2-1.我们右 取p=1,第一行对应的基变量4为换出变量。对表2-1进行枢运算，迭代出新基本可行 解对应的单纯形表（表2-2） 表2-2 40 4524 、0 0 CB TB 2工3 T4 T5 0 21 30 4515 15 0 0:-z: 10 0 -150 表2-2中仍然有大于0的检验数所以尚未达到最优，重复前面步骤，选择1为换入 变量，令 =mim学，=20 1 选择5为换出变量。迭代出新基本可行解对应的单纯形表得表2-3 表2-3 Ci- 40 4524 0 0 CB TBb T 45 20 0 1 40 45 25 5 10 9- -10 单纯形表2-3中的检验数全小于等于0，所以已得最优解.最优解为x1=20,2=20,3 x4=x5=0,获得的最大利润为40×20+45×20=1700元. 四、单纯形法的计算步骤 令SB,SN分别表示基变量和非基变量下标的集合. 第一步首先，确定初始基本可行解建立初始单纯形表，转第二步 第二步检验各非基变量的检验数)=g-,j∈SN.若≤0，j∈SN,则已得最 优解，停止.否则转第三步 第三步若存在k∈Sx满足k>0,且k对应的列向量满足P以≤0，则此问题的解 无界，停止。否则转第四步 第四步按max{oi∈Sw}=ok确定换入变量xk,按最小比值规则计算 =m{>}-
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