最优化算法课后习题标准版

1、第三章一单纯形方法题解】.用单纯胳方法讲F列线性规划何题：(1) minTfi 16xi(2) maxXi +3xss. t”厂+*.?含十 jt*=80s. L2j( +3j-j + xi62jci + 3x+x* 90一疋 i +xf+r4= 1 *，巧鼻0 - j I *2 *3*4巧30, j = l234.(3) max 3丹 +j-j(4) rnin3,r, 3升2tr4 xts, 1.Xti j-t+2xi7 *氣t.;ti+jq+ Xj4 *2jfi 4-4jTfWl2*-L 门一 *7士+ jt 斗十4j-| +3=+8sW10jt十j十十匕口十3x*W12.jt t,r；

2、* Ja 二j=l,2.3U,(5 ) JU 1113jTi Jjs tT3ji +5j-i + x5= 3i)4ji4归+x4 16 *2j-j 一升12,r,0* j= 1 *2*3*4.解(1用单純形方迭求耕过程测下；XiXiXi直m1 1 080Z30I90916000Xj X|龙事JT i丄T10+。-1 120305040320011351410_邑x5524D0A一倔最优解丘= (244 *0*0) *理优仇丿 = 一 1 lu.(2)用单纯形方法求解过稈如下C2）用单纯形方法求梢过稈如 X* Xj q213I0011-1-3000Qi33-1101L-40033!01T_色J_

3、5021S530025275疑优解A(号魯。町凤优值/_ = yT(31引人松龍变虽x F *升.化成标准形式：mu 耳 .T| + 3x； + ,f3礼 L 3,Ti Js H- 2 .rj + jti= 7 *2j-| 4* 4j*t+ Xs= 12 4ti + 3jf + 8j4- j I Otg p (1j =叭2卮 用单纯形方法求辭过程如下专业word可编辑53-1Z1007-30010123E001103-10000亘021J_4010-Tf1 21001T01x32003411120-103 T090BT27810502525010虽?3125114K001一丄1J1201010

4、D0137735S30100訪莎皿低辭亍=( I： 血=宇，J = I畀*氐 用单纯陋方袪求解过侵如下J|X|X),JT*JT帘33Iool30ijj J01012100I123100寸00I_3_T018J01 T040101214n40_3_0-12处ft解壬=U3.OO1 垠优值孑24.2.求解下列线性规划问题(1min4ji +.rj + 18j*3(2)tlltfiX2.rj +jjJ4十3叭P3*轧L,T| +*jrs + 2n5JTi ,Fi0 .ri t-fjJT)0.机门 +ZrM2 1 *Fl T1mu xSuri 一Sjtjn il i nXi 3j +心也1. +t=

5、+ 4才$ 右山 ts, tB2X1一 辛 + 丁$ =氛Ju+ Ti 235 *2j-t + j-jA2 *Xi +2j-t +j i + 2xt巧 *lF * i j 0,rj .口 *,厂1max3xi + 2jt ra(6)min2ti 3tj + 4j-j贏t.2ji + XoS. Lxi + jt +,r39 4xi +3jti +.C3、疋+ 2、口 一、fj“-+ Xi=2-2 .巧芯 7 +Lr | * ,j_；JP1 5(7)min !.rt +tsmin? r( 氐1.2xi 3.0 +t3 = I!k tb2xi Tf j丄孑3 +芝叭十3%，飢.f i，L .rf +

6、 J-$2 *ji *xi *,n 0.J- JT * lTI A。*min2X1 +jTf Ts J*(10) niHK3,门一 xs 3jp3 + j4缶1,n .壮+2,口 一 2*s, lPX| +21 JTj + 才4 02xi +j-j3x +xi = 6 Ji + 2Jrj j( = 6JTi +jTt +ji 7 -2 7 i 2jtj + 3,fj + 3,ri 9 XjOt j12,3+,冲2=0.；-L23.4.解(I)引人松弛变秋h卄一化为标准曙真t rti in 4心 + 6丹 + I &r$s. L 誉i+ 3tj Xi=3*JTf 十 2x1 Ji =5 i兀P

7、丿=I *2*5- 用凱純形方法求解过程加F：JJIJ1片J10-J030I20-1s006T-6121T01_0I22T0T-13200-636最优解工=1*0*0)*最优值= 36”C2)引人松弛变窒卄化嵐标孝形式max 厂+减s. t, ,rj + j-t + xi=5Xl 一 JTX一J*=0*fixi + 2xi+ Ji = 21JT* 上 0+ J = *5”JT |XfJFj,JF*Js,Ji1110005-10-10104620010211-1c-100040210-15Ji1-10-01Q40806I62100000-J0得到原线性规划的一个堆本可荷解由此岀駆求龄优解过程血下

8、;JT|JTfJTjJT*JTj,片0110手1-I0-1000tt01210-30-2001ISXi0IT0TLi5JT|0Ty0TXl00TIi00邑i3015 T3I90170TTL1IL10一 T0TT0a-212 ?ooLo131244优解斤=(+o.*w)巅优值/=j.引入松弛变61斗化成标准影式max 3,T| 5j(s, k J-, + 2jrt + 4jTj + Xt=4 T| 十 Tg + 2.Tj+ Jj =5t一 j+S + j-3 r* = I並 P 01/ = N2-, t6.用网阶段法求做为此引人人T变肚丫辭F列线性规划：uibu ys. i. jri + 2xi

9、 + Axi + jr=4*Ji + 卫 + 2xj4- j-j 5 +对 + 2才 -J- jr、丈 + y =】+刃 P (h j=l*2*6* ,v 0XjJTjJTjJT.jJE.-1Z41000411201005y-1100-111-12100-1010Q3101-133T03 T01 Z129 T-T!1211 TQ0121T12000000-0得到取线性規划的 f 率本可行机=扌心3魯0). 由此出发求巅优解.过程如F1可J1-ri轧 t*2J + J;心 + JTi4,ri + 3,rj + Ti一丹+加=3*.ti + Jt 4 jj十力=2 +6 2= Si .并 匸求解过

10、程如T：fi Ji 斗 Ji 齐 血 加21-1000刃410一 1103-111000123420105Z_0_1J._ j_T04JJ3L丄30_LTi301Ji_7_T000iT1T111Z1430T0T31T52 _l010001L00J121 T-1212213FT6123 T000000 -10T*J-!Jj町 叭 c 巧 寸 M 血得到- 亍甚本可行解玄=（0*.击弋）.从求得的苹本可行無出发求最优斛*过稈如kJi忑*JlJi-40 0 1161o0 -y丄7 T0 1 032230 0 0 -412230-2103311002Xs一7Q2G13103004(6) 引人松弛变bt

11、小+吧 y 化锻标准形式：min 2xi 一 3,rs +4xi扎 I, ji +n 十乃+.“=9*.Ti + 2,ri Tj=二*2jt 归十.r* = : #心 A 0* j 2#*6. 用大Af袪求解.引入人1：喪磺収大:正数时解下列线件建划cnin 2jti 3ji + Tj + jVfyi. Jj + jt + 巧 + j=9*jti + 2 JzJi 心 十y$*tjTl X!+ X* =7 *刀 3 Ch J = 1 # 2* y A CL求梆过程如下1TjR*TtJf上.L110009y-1-L010L5兀3-1000)07Vf 2?刖+3一M一q0.w005阳3 T03T0

12、113 TXf1 g12001T53 T0) 201iT19 T1 205 :03 TQW_XM 215 F-TS30320113XV1It0009T( 3x( + jri2jti + 3jt*jj 0 * J = 1 2*3* 4*用大M法求解.引进人I变尿屮取大正数耐解下列级性规虬mir 3jT 2,rj + 片 + My氣 t. 2xi 3j-s += 1 *2工| + 3,rt曲0J = 1,2.34# 丫鼻厲求解过程如下:眄巧yJ12一3001y201182M-13M-008M+14巧Ji401-11gZ116T10TT00丄1HT戟优解丘一（号40）晟优值（8）引人松弛童秋冲化眦标

13、沖形式：min 2,rj 一 :gS, *2ti JTz T3 _ Xt=*x i -fl十才一吐=2.JTt P 0*j =丨工*.5、用大财法求解引进人T连就屮和取大正较M.解下列线性视划min 2.J-J 3口 H- M（ Vi + v；）k L 2Ji x2 ,Tj j-t+ _vi=3.ri ,rj +xj jj4- yi=2*兀 0 j = I * 2 r B*肌 X 0*1-1-1-11-100-11001323M22M + 39一jVf-M0SM1zJ ZI T01 Z03 T廿_i T-1_J_Iifl;M+?yWIyM-i-M -供+L0yAf+32Hi1111513l r

14、333AAflII121213J.393330 T0_2_2骄2tm t-仃10 T现荷除本可行解下时应口的月别数大F0约束系颉第3列无正元人变hi均为非 宰变试取值为因此不徉在有限城优餅.（9）用惓正单纯形法求it初祈庙本町打無最知，用两阶殷法.min yi + ; + yf丸 1” Ji Xs + 2xs Ji + J?i21 + ji 3-ti + TiJj +J-!+ Jj + J*+ yi = 7 *jj 0 ca = 0 zt 一 r4 =x-p* r* = 1 * s ti = -4 i =? Ct = “*却ti = maxs 一勺 =*因此 jti 进基.主列作主元消去运律;

15、-a11741002yt-2i0Zyi-i0L51111510020060011第?次迭代；由上表知单摊瞻乘T汁寵现廿基下时应各变戢的判别数:“ 口 = *pr G = 5* 野C =岬 3 一 门=$ *zi | = c# 4 = ffr ft = 0 si ci = rnx(- rj计算主列-0- I- -ri*_l Pz -2101=3-101.2.作主元消去运第；31L7100Zyi-2102yi-I0t51233ILL0sT_LTT0?T1233IliT第3次选代t由附菽划甲乳形乘广宙=(+ 討)，计算HHB下对应各变的判别數:第3次迭代*由前表知，单摊形乘知小计算现行基下对应各变足

16、的判别数;j n = wpi o =y*甌一门=wp4 一口 =0盅E Ci =*Pft 一 C =一?弐_“=杯一心=_即 n maxi Zj cf计境主列*丄丄M33厂_1J旷P=i t 0-3rai 童凍线性規划的最第1次这代雄变蜃为曲y W 先计算单翹帘乘f:4 n3111rrH=c(ii =5 一TT1_n7 n(2 1 6A=(1?77丿11123TT月标爾数值/ = = &理和毎卜对口齐*扯的押别数：门一门= = “一C = m 為1_口.詹血_口.監计算主列*用主元消古运悴:H1TT2TT3 u211x utiTTJ_1)丄 TTa-Fl_互丄7 n3Ti呈Ti.11?982)

17、1 11 11431itnii_A 一丄Z11Ll11123111LlLI计算对应各变童的判别数”国为只有i个非雄变扯升.只霜计算对应寸的判别数.劭一巾=up一e 2 用修正匏饨形法求解”初始堆本可行解未知下面用大M搓*引人人T.变触小、肌 n 取一卩大正數M.解F 列线性规划：mux 3xi jrt 3js + x -Vf(yL + jft + yi S. h J| + 2nJj + T| +=04 工工 + 2j-3 .口+ 肝=6 *2xi 一 2j*z + 3xs + 3j*4+ 处 9.Xj 0*_/=1*3丫4，” P0 j = L2tS,记约电系救世阵*右端向蛀及冃标系数向底如下

18、=1 211I00_,4 /Ji Pi pt Pt pt pi PtI 1210】02 -233001_b = 0 + fi*9J T - c = (r| *r3 ifi *rj *rs nrpi cs M + 1 * 艺、* =冲 * c 3jM I +计WIt E时症拎变粧的判别数：Zi 门段p l i 1AJ 3 衍一门= k P i 一口 =_罷订+皐计律主列t作主元消去运算!-M .w-w-15Ml000jn0I0yi0 019-4M-3I3A/+3 Af 15fXI1000yi-II0yi-2019第2次这代*汁程现厅髓下对宣备变応的判别豊：Zi Ci ! Cj 9M +7* Zj

19、 ra *ps n = SAT*z* ct =wp 彳=hf 十 2 zs 一 c5 = *ps ca = 4M + 3 Zi Ci =ss c* =zr g =0 Zj g =m in-z, 一门 = 8Af. 计算主列.0O- r-r102=301.3.15.柞主元消占运算:3.W+3一.M MISMJFI000ytt106-2019-M-I313:=三|讷+3一灯M一 115曲3rt ?T0 =訝5113351352rt丄95U5第3次讣彈现行基下对应各变就的判别数：Zi f I =十 7 + 4| ! =wpt r(=里 Af + 2 订o讣算主列上作主元消左运算：-*M+3-帥3_0

20、丄25S5X15X S50丄9 T2T_35T7-71电331115一 113302-3第4次遠代t缶* iqi ； rr jV/ + 7判别数均非负+已达到最优解.毘优和最优值分别是I = (1,K3.O)和f. = 73. U明用单純形方也求解线性规划问題时，在主元消去前后对燼同一变量的判别独疽 下耐关系（=:,一 j ）=（石一CJ 1 如丄一门TVri其中（耳一巧泸是主元消去后的判别数，其余是主元消去前的数据%主元.证 约束柜阵记作A = Pl肌丹主尤涓上啊后的氛并別记作肘和虽*施变星的费用系数向就分别记作4和“，创疋5力曙 I 片打-土兀旳 ArttlR*悴堀 AU.W削 i h J

21、 kJij *iy,t * AMA-JzXlAlKTIH j -Cj tf -QJe# F4!X* =证 约束矩阵记作A = p】丹pj*主元消止前片的基分别记柞用和R，基愛境的费用系数向斌分别记作仆和5- 同时址一 1煦力咙A-I阿叫主元泊蛊整斥r单雉憨方世申踊商,贰元常眇網记为孑射鼻Jf沪星元口比主Bj-rj勻C可一多附下艸芸h丄假设一个线件规划何题存在有限的星小偵几.现在用单纯形方法求它的抗优解挝小值 点X设在第k次送代得到牛退化的基本可行解且只有一牛基变量为零（兀=0几此时目 标函数心人几.试证这个退化的堪本町行解隹且后各次進代中不会直新出现一minfiE设现行基本可行解中忒坐址叭=厂

22、=0.武他基变星均取正值.目标晡数值为 /打若下次这代屮.心进歲厂离基则進代后对应非羞变hi心的刘跚数为负数斥绒这代 中旳不进基*若下按这代中2#进基.冲仍为基变蜃.则r逬基片的取值U =新的基本町行骼处川赫酮数值丿=几一旧一r訂心夭.曲于单纯形方送得到的歯数值序列单澗减小，悶此原追化的甚本町行解不会重址出现.5.個设给証一个线性现划问题屋其一个甚本可行解+在此线性规划中变竝之和的上界为6在已知的基本标嚴数值为%最大判别数是純一5又设冃标囲数值的 允许溟基为打用几表示未知的H标函數的最小值.证明：若把+ -L e/tJ */-/,o.rfll,iLJ,th比较（I）式两端的齐井bb腸知就m利出

23、”有下列形式：由r-drlfM町打域的方向，因此同理.山八才少=（1. BI由怕）式SU3）式得到两端左乘序一+则有代人方向屮和.从而碍到耐十S=也Ml11 + 毎旳=8丄丄lidi,rfir 虬趴%寸帝=业才1， 托中町肠 氛f d即dn .rf（zpJ同向非零向比因此方向d不能衣示嵐两个不同方向的正线性组含/是可齐域的犢方向.7,(1 min Sj-j Tzs. L 冲 +，riH *0盂6. j = U2 .用XF变触仃界惰形的单纯附方法解下列问理；（2） max一才|一3j-j(33 min i+2丁= + 3丁3 rt*+t.jtin +j2j盂 6*2ji +tj x5A?、j-x

24、 +-Ti .r3 + .ri 8. 0冲孟3 *i Wr W 斗JTi +2ji +-rj H-.r, = I H () j i 4 oW j冬斗。茎jt,总取 tnax 4丁 +6j=札 t* 2.n + xj4 -g * oSm. Ojn 茎 3.解 门引进松整变”宵歳乔列形式min 3jij% A J- 4- xa H- jj = t 0鲨兀鲨氣 r- 1.2， 小耳0= 目标函数值几D.取樹捲阜搖可忙解：jp. Ta 9 工爲 nX!小纯形表轴厂取下界的非基变量下标集总=口圧八取上界的非恥支试卜林集隔=0.巳用符号1标注在衷K选择升作为进幫変SL令归=0+鼻=4 *计算岛90禹=-=

25、9* 虚=8. 岛=G 0 = 6 as-niin9.00.61=5，此取侑上界仍为非基更嗣 EL貶竝卮m *1R值改堕匕-jj 皿_、亠=9 6 3J ft 一“n )js 0 X 6 = 6.Ji rt1 19-3L001Jfc下界的非基变BtT标集民= HfJ?t上界的非基变St下标集乩=0.巳用符号】标 注在舂下.选择心作为逬甚变血令曲0+爲鸟计算山“q 0 /Si =9 長=8胃 禹=6 =乩令由二miM矢击=触因此氣取值g仍沟非坠咗賦*舉空啟览冲取值改变工Ta = Tt =b yi2 =9 6=3* f =/ ( =r ri )j-j = 1 X 6 = 6,修改推现形表如下：4斗

26、m 131A|已鮭达到殳优+最优Mj = CO.6.3H最优值/* = 一&（2）用阴阶具法求解”先求一亍毘本可行訴为此解下列线性规划:Tint y弘 I. 2ji 一 2jj + .rj,Fi 十 iri 尹土 十 xt0 W才1W4*0 Ji1.0 Wx.i4+0 W斗W12.,v 4 0.6护一单址形崔如八y0-21 0 161211010221006111选择变试片令JTLO七1L“下面计其增饋 d10|=3. 氏=8 闻=4令為01诚氛8N氛固ftjri-3.未达刃的匕界作为进基变fit.:卜闔吨 H： W25丫离城修改单纯形表如下斗X1y1-11-0iS03丄Z127&000_ L

27、0111-阶园I憫;:达到最応帙改单纯形 乩进行第.阶段IXiXtXiJT*10-31Ti70i370I0一32已经达到最优最优解壬最优值（3）用两阶卅法求解.先解F列线杵规划.求-个星本对行解:in ni ys, C J- j-j 十 丁丄2j-4 + JS2ji + j-j -FjJi d- Lr3 rj + ,t40 j-i W 3 *1苍乃W 4 *0 M *巧 I ( *2 M 口 盂 5 *f5 *xi *y 0,取衲始第启可行解：r =”y102* J* =:巧y巧一=11|-5.* /= 1 +0单纯形丧如下t工|r*JTty1-1)-?10001)y1-100_】01I上T-

28、1L-)00I05Z1-100】0011111选择变屋心，令算d的取值:冋=min (丄L厂.打_2 =* 雋=8. ft =3 0 =3.y离咅心谡替斯甚下目标值心一241一2泻0.修改盲单纯務表如下:X| 斗 1 斗 丹 竝 丹y。-1A 一22 1 T0I z211 1IA、i0I12-y 00 -yTT八33,“ 11li 22 10 t1TT0 00 00 00-10得到原柬线性規划的，覃举可疔解.下面进行第二阶凰*从求得的基本可行解出发,求最优为此*先修改上面单地形表.0_3_I 7I1 T021T1J_-T 00-丄 20丄 T0_3_ i-Aiz0丄 T1ILTA3_ 丁.fh

29、jAiU72 1u?u2XIXlJTlXlXtTI选抒变吐令员=筈+尖下血求1:题= 0* 摂=5 二=3”令严min愕*g*$=3m取上界值.血TT177./ =/* z* n)iii = 1 X 3 =慘改单沌彬农右罐列*得卜崔;1寺0 Tt 71-y0o i 00 -f 133 T125 To -1-1】0 -y0sU求得最优解仕 JQ5夢5罰尽优值匚U)引人松翹变竝d/匕拠max 1.r + 6.ra氈J.瓷珀亠才丄+的 413xj jet+ r* = 9 0 W .r M 4 ”0 jr： Jj T1 X| 1 1 013-10LJ2-4-60fl18JQ还本达到讯忧*石* S、 -4-0-4.选择变fix.*g=0+4计算 4 fl-0 12-0r o IpTlI12_r._217.i=min _/ fn (Z fl )岛 18 ( jO X 20*廿边垄+心岛產取F界”经進代猫到新单地形灰上巧斗 -Tj斗i丄丄2Z01To -鱼一豆1211 UZ22042020已经达到最优最优解4特心辛呆优值人严如乩用分解算嗟解下列线性视划问题*(1) ma