- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
上页 下页 返回 课堂练习1-2:用图解法求解下面的线性规划 按小组分工完成:①画约束条件1;③画约束条件2;⑤画约束条件3;⑦标明可行域;⑨目标函数等值线;⑾说明如何得到最优解,算出相应的目标函数最优值。 其他6个小组对应讲评。 第一步 模型标准化; 第二步 按照基本解的定义 ①?找基(非退化3阶方阵)—— 多少个?不超过 ,为什麽?怎麽找? ②?确定基变量和非基变量; ③?令非基变量为0,解出基变量; ④基变量和相应非基变量搭配构成基本解; 凸集——设K是n维欧氏空间的一个点集,若任意两点X(1)∈K,X(2)∈K的连线上的一切点: αX(1)+(1-α)X(2) ∈ K (0α1),则称K为凸集。 顶点——设K是凸集,X?K;若X不能用 X(1) ? K,X(2) ? K 的线性组合表示,即 X≠αX(1)+(1-α)X(2) (0α1) 则称X为K的一个顶点(也称为极点或角点)。 图解法 —(练习) 18 — 16 — 14 — 12 — 10 — 8 — 6 — 4 — 2 — 0 | | | | | | | | | 2 4 6 8 10 12 14 16 18 x1 x2 4x1 + 6x2 ? 48 2x1 + 2x2 ? 18 2x1 + x2 ? 16 可行域 A B C D E 1、定义“顶点”的方式有什麽特点? 2、这种定义方式在什麽场合运用最方便? 讨 论 2、线性规划问题解的性质定理: 定理1-1 线性规划问题的可行解集 (即可行域) 是凸集。 证明思路:根据凸集定义,采用直接法证明; 具体步骤:①从D中任取两个不同的点, 应满足 可行解定义中相应的条件; ②证明X=αX(1)+(1-α)X(2)∈D (利用①,证明X满足凸集定义中相应的条件) 定理1-2 线性规划几何理论基本定理 若 , 则X是D的一个顶点的充分必要条件是X为线性规 划的基本可行解。 证明思路:定理1-2是X是D的一个顶点= X为LP的基本可行解; 引理是X为LP的基本可行解=X的正分量所对应的系数列向量线性无关; 从而将问题 转化为 X是D的一个顶点 = X的正分量所对应的系数列向量线性无关 证明要点:(1)引理: X为LP的基本可行解=X的正分量所对应的系数列向量线性无关 必要性→由基本可行解定义直接证得 充分性←正分量K个 k=m →X=(x1,x2,…,xm,0,…0)T即为 基本可行解 km →补齐得基→退化的基本可行解 (2)定理1-2 (反证法) 必要性→ 第一步:将反证法假设和已知条件具体化; 第二步:寻找X附近的属于D的两个点X(1)和X(2)(技巧:将第一步得到的两个式子相加减得到); 第三步:选取适当的λ,可保证 X=1/2X(1)+1/2X(2), 从而与“X是顶点”矛盾。 充分性← 第一步:将反证法假设具体化,明确正分量; 第二步:由大前提X是可行解,找出不全为0的一组数; 第三步:得到P1,P2,…,Pm线性相关的结论,与已知条件矛盾; 定理1-3 若可行域非空有界,则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。 证明思路: 首先可行域非空有界就肯定有最优解 本定理要证明的是设在非顶点X处取得最优值,则存在顶点X(1)和X(2)也取得相同的最优值。 定理1-4 若目标函数在k个点处达到最优值(k≥2),则在这些顶点的凸组合上也达到最优值. 证明思路:根据凸组合的定义直接证得结论。 课后小组讨论2: (1)读懂证明,理清思路,写出从最罗嗦的证明过渡到最简洁的证明过程 (加上边注——段落大意) 可以作为小实践选题! (2)P70习题1-4(①检查是否属于可行域;②检查相应的Pj是否线性相关) 上述4个定理的一些有意义的启示: LP的可行域一定是凸集,但是凸集不一定成为LP的可行域,而非凸集一定不会是LP的可行域。 (为什麽?能举例说明吗?) 线性规划的基本可行解和可行域的顶点是一一对应的(类似
文档评论(0)