第1章-运筹学基础及应用-第六版ppt课件.ppt

《第1章-运筹学基础及应用-第六版ppt课件.ppt》由会员分享，可在线阅读，更多相关《第1章-运筹学基础及应用-第六版ppt课件.ppt（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用管理运筹学管理运筹学OPERATIONS RESEARCHFOR MANAGEMENT SCIENCE 2022/12/291经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔

2、偿的金额为消费者购买商品的价款或接受服务的费用第一章第一章 线性规划及单纯形法线性规划及单纯形法(Linear Programming&Simplex Method)1 一般线性规划问题的数学模型一般线性规划问题的数学模型2 图解法图解法3 单纯形法原理单纯形法原理4 单纯形法的计算步骤单纯形法的计算步骤5 单纯形法的进一步讨论单纯形法的进一步讨论6 数据包络分析数据包络分析(DEA)7 应用举例应用举例2022/12/292经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当

3、按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例2(教材第9页)生产计划问题生产计划问题常山机器加工厂，利用A、B、C三种不同设备加工生产、两种产品。按工艺要求，每生产一个单位的产品，需要占用三种设备2、4、0小时；每生产一个单位的产品，需要占用三种设备2、0、5小时。已知三种设备加工能力分别为12、16、15小时。且每生产一个单位的产品可获取2单位的利润；每生产一个单位的产品可获取2单位的利润。问应当如何安排加工，可使获取的总利润最大？2022/12/293经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额

4、为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1 1 一般一般线性性规划划问题的数学模型的数学模型1.1 1.1 引例引例 例例1、生产计划问题、生产计划问题 设备能力（小时）设备能力（小时）设备设备A 2 2 12 设备设备B 4 0 16 设备设备C 0 5 15 利润（元）利润（元）2 3问：问：，两种产品各加工多少单位两种产品各加工多少单位,可获最大利润可获最大利润?2022/12/294经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，

5、增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2022/12/295 2x1+2x2 12 12 s.t.4x1 16 5x2 15 x1，x2 0注意模型特点注意模型特点 max Z=2x1+3x2解解:设产品设产品,产量分别为变量产量分别为变量x1，x2防灾科技学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿

6、其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用附例附例 营养配餐问题营养配餐问题假假定定一一个个成成年年人人每每天天需需要要从从食食物物中中获获得得3000千千卡卡的的热热量量、55克克蛋蛋白白质质和和800毫毫克克的的钙钙。如如果果市市场场上上只只有有四四种种食食品品可可供供选选择择，它它们们每每千千克克所所含含的的热热量量和和营营养养成成分分和和市市场场价价格格见见下下表表。问问如如何何选选择择才才能能在在满满足足营营养养的的前前提提下使购买食品的费用最小？下使购买食品的费用最小？经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金

7、额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用各种食物的营养成分表各种食物的营养成分表每天需要每天需要每天需要每天需要 3000 55 800 x1x2x3x4经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解解：设设xj为为第第j种种食食品品每每天天的的购购入入

8、量量，则则配配餐餐问题问题的的线线性性规规划模型划模型为为：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划模型的特点线性规划模型的特点n决策变量决策变量：向量：向量X=(x1 xn)T 决策人要考虑决策人要考虑和控制的因素，非负和控制的因素，非负n约束条件约束条件：关于：关于X的线性等式或不等式的线性等式或不等式n目标函数目标函数：Z=(x1 xn)为关于为关于X 的线性函数

9、，的线性函数，求求Z极大或极小极大或极小2022/12/2910经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用防灾科技学院11LP问题一般可整理为：决策决策变变量及各量及各类类系数之系数之间间的的对应对应关系关系经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照

10、消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用防灾科技学院12上述模型的共同特征：l每一个每一个线线性性规规划划问题问题都用一都用一组组决策决策变变量量 表表示示某某一一方方案案，这这组组决决策策变变量量的的值值代代表表一一个个具具体体方方案案。一一般般这这些些变变量的取量的取值值是非是非负负且且连续连续的；的；l都都有有关关于于各各种种资资源源和和资资源源使使用用情情况况的的技技术术数数据据，创创造造新新价价值值的数据；的数据；l存存在在可可以以量量化化的的约约束束条条件件，这这些些约约束束条条件件可可以以用用一一组组线线性性等等式或式或线线性不等式来

11、表示性不等式来表示;l都都有有一一个个达达到到某某一一目目标标的的要要求求，可可用用决决策策变变量量的的线线性性函函数数(称称为为目目标标函函数数)来来表表示示。按按问问题题的的要要求求不不同同，要要求求目目标标函函数数实现实现最大化或最小化。最大化或最小化。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1.2 线性规划问题的数学模型三个三个组成要素：成要素：1.决策变量决策变量:是

12、决策者为实现规划目标采取的是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。方案、措施，是问题中要确定的未知量。2.目标函数目标函数:指问题要达到的目的要求，表指问题要达到的目的要求，表示为决策变量的函数。示为决策变量的函数。3.约束条件约束条件:指决策变量取值时受到的各种可指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或用资源的限制，表示为含决策变量的等式或不等式。不等式。2022/12/2913经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，

13、应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划的数学模型由三个要素构成决策决策决策决策变变变变量量量量 Decision variables Decision variables 目目目目标标标标函数函数函数函数 Objective functionObjective function约约约约束条件束条件束条件束条件 ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题问题问题问题的目的目的目的目标标标标函数是多个决策函数是多个决策函数是多个决策函数是多个决策变变变变量的量的量的量的线

14、线线线性性性性函数，通函数，通函数，通函数，通常是求最大常是求最大常是求最大常是求最大值值值值或最小或最小或最小或最小值值值值；（2 2 2 2）问题问题问题问题的的的的约约约约束条件是一束条件是一束条件是一束条件是一组组组组多个决策多个决策多个决策多个决策变变变变量的量的量的量的线线线线性性性性不等不等不等不等式或等式。式或等式。式或等式。式或等式。怎怎怎怎样样样样辨辨辨辨别别别别一个模型是一个模型是一个模型是一个模型是线线线线性性性性规规规规划模型？划模型？划模型？划模型？经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接

15、受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一般线性规划问题的数学模型：目标函数：目标函数：约束条件：约束条件：2022/12/2915经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划模型的简写形式(求和符号)经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的

16、损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一般线性规划(LP)问题模型向量形式其中：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一般线性规划(LP)问题模型矩阵形式其中：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受

17、到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1.3 线性规划问题的标准形式标准形式：准形式：标准形式特点：准形式特点：4.决策变量取值非负。决策变量取值非负。1.目标函数为求极大值；目标函数为求极大值；2.约束条件全为等式；约束条件全为等式；3.约束条件右端常数项全为非负；约束条件右端常数项全为非负；2022/12/2919经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的

18、费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一般一般线性性规划划问题如何化如何化为标准型：准型：1.目标函数求极小值：目标函数求极小值：令：令：，即化为：，即化为：2022/12/2920经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2.约束条件为不等式：约束条件为不等式：（1）当约束条件为）当

19、约束条件为“”时时如：如：可令：可令：，显然显然（2）当约束条件为）当约束条件为“”时时如：如：可令：可令：，显然显然 称为称为松弛松弛变量。量。称为称为剩余剩余变量量。2022/12/2921经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用松弛变量和剩余变量统称为松弛变量松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数）目标函数中松弛变量的系数 由于松弛变量和剩余变量分

20、别表示未被充分利由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利用的资源以及超用的资源，都没有转化为价值和利润，因此润，因此在目标函数中系数为零在目标函数中系数为零。2022/12/2922经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.取值无约束的变量取值无约束的变量 如果变量如果变量 xj 代表某产品当年计划数与上代表某产品当年计划数与上一年

21、计划数之差，显然一年计划数之差，显然 xj 的取值可能是正也的取值可能是正也可能是负，这时可令：可能是负，这时可令：其中：其中：令令4.变量变量 xj0，显然，显然2022/12/2923经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例3(教材教材15页页)将下述将下述LP模型化为标准型模型化为标准型2022/12/2924经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增

22、加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解：解：令令得标准形式为：得标准形式为：2022/12/2925经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划问题及数学模型线性规划问题及数学模型线性规划问题及数学模型线性规划

23、问题及数学模型线性规划（线性规划（线性规划（线性规划（Linear Programming)Linear Programming)Linear Programming)Linear Programming)创始人：创始人：创始人：创始人：1947194719471947年美国人年美国人年美国人年美国人G.B.G.B.G.B.G.B.丹齐克（丹齐克（丹齐克（丹齐克（DantzigDantzigDantzigDantzig）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消

24、费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）1951195119511951年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（SimplexSimplexSimplexSimplex）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者

25、服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）1963196319631963年年年年DantzigDantzigDantzigDantzig写成写成写成写成“Linear Programming and Linear Programming a

26、nd Linear Programming and Linear Programming and ExtensionExtensionExtensionExtension”经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（

27、丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）19631963年年DantzigDantzig写成写成“Linear Programming and Linear Programming and ExtensionExtension”1979197919791979年苏联的年苏联的年苏联的年苏联的KhachianKhachianKhachianKhachian提出提出提出提出“椭球法椭球法椭球法椭球法”经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受

28、服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）19631963年年DantzigDantzig写成写成“Linear Programming and Linear Programming and ExtensionEx

29、tension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”1984198419841984年印度的年印度的年印度的年印度的KarmarkarKarmarkarKarmarkarKarmarkar提出提出提出提出“投影梯度法投影梯度法投影梯度法投影梯度法”,又又又又称多项式时间算法称多项式时间算法称多项式时间算法称多项式时间算法 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为

30、消费者购买商品的价款或接受服务的费用线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）19511951年提出单纯形算法（年提出单纯形算法（SimplexSimplex）19631963年年DantzingDantzing写成写成“Linear Programming and Linear Programming and ExtensionExtension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法

31、椭球法”19841984年印度的年印度的KarmarkarKarmarkar提出提出“投影梯度法投影梯度法”线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额

32、为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用求解线性规划问题：求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。值中，找出使得目标函数达到最大的值。1.4 线性规划问题的解的概念2022/12/2933经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的

33、要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 可行解：可行解：满足所有约束条件的解称为满足所有约束条件的解称为可行解可行解，所有可行，所有可行解的集合称为解的集合称为可行域可行域。最最优解：解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。基基：约束方程组的一个满秩子矩阵称为规划问题的一：约束方程组的一个满秩子矩阵称为规划问题的一个个基基，基中的每一个列向量称为，基中的每一个列向量称为基向量基向量，与基向量对应，与基向量对应的变量称为的变量称为基变量基变量，其他变量称为，其他变量称为非基变量非基变量。基解：基解：在约束方程组中，令所有非基变量为在

34、约束方程组中，令所有非基变量为0，可以，可以解出基变量的唯一解，这组解与非基变量的解出基变量的唯一解，这组解与非基变量的0共同构成共同构成基解基解。基可行解：基可行解：满足变量非负的基解称为满足变量非负的基解称为基可行解基可行解可行基：可行基：对应于基可行解的基称为对应于基可行解的基称为可行基可行基2022/12/2934经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例：考察下述线性

35、规划问题：例：考察下述线性规划问题：2022/12/2935经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（1）可行解，如可行解，如或或满足约束条件，所以是可行解。满足约束条件，所以是可行解。（2）基基系数矩阵系数矩阵A：其中其中 或或 都构成基。而都构成基。而 不构成基。不构成基。2022/12/2936经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，

36、增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（3）基向量、基变量）基向量、基变量是对应于基是对应于基的三个基向量，而的三个基向量，而是对应于这三个基向量的基变量。是对应于这三个基向量的基变量。（4）基解、基可行解、可行基）基解、基可行解、可行基是对应于基是对应于基的一个基解、基可行解。的一个基解、基可行解。是对应于基是对应于基的一个基解、基可行解。的一个基解、基可行解。均是可行基均是可行基。练习：练习：P14，例例42022/12/2937经营者提供商品或者

37、服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 为了便于建立为了便于建立 n 维空间中线性规划问题的概念及维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。先介绍图解法。求解下述线性规划问题：求解下述线性规划问题：2 2 线性性规划划问题的的图解法解法2022/12/2938经营者提供商品或者服务有欺诈行为的，应当按照

38、消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用画出线性规划问题的可行域：画出线性规划问题的可行域：目标函数等值线2022/12/2939经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1、可行域：、可行域：约束条件所束

39、条件所围成的区域成的区域。2、基可行解：、基可行解：对应可行域的可行域的顶点。点。3、目标函数等值线：、目标函数等值线：4、目标函数最优值、目标函数最优值:最大截距所最大截距所对应的的 。目目标函数等函数等值线有无数条，且平行。（有无数条，且平行。（观察察规律律)2022/12/2940经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解的几种情况解的几种情况：(2)2)无穷多最优解无穷

40、多最优解(1)唯一最优解唯一最优解若目标函数改为：若目标函数改为：约束条件不变，则约束条件不变，则:目标函数等值线此时，线段此时，线段上所有点都是最优上所有点都是最优值点。值点。2022/12/2941经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解的几种情况解的几种情况：(4)4)无界解无界解(3)无可行解：无可行解：当可行域当可行域为空集空集时，无可行解。，无可行解。若目标函数不

41、变，将若目标函数不变，将约束条件约束条件1和和3去掉，则可行域及解的去掉，则可行域及解的情况见下图。情况见下图。目标函数等值线此时，目标函数等此时，目标函数等值线可以向上无穷值线可以向上无穷远处平移，远处平移，Z值无值无界。界。2022/12/2942经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用几点说明：几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问、图解法只能用来求

42、解含有两个决策变量的线性规划问 题。题。2、若最优解存在，则必在可行域的某个顶点处取得。、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。解、无最优解、无界解。2022/12/2943经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3单纯形法原理形法原理凸集：凸集：如果集

43、合如果集合 C 中任意两个点中任意两个点 ，其连线上的所有点，其连线上的所有点也都是集合也都是集合C 中的点。中的点。上图中（上图中（1）（）（2）是凸集，（）是凸集，（3）（）（4）不是凸集）不是凸集顶点：点：如果对于凸集如果对于凸集 C 中的点中的点 X，不存在，不存在C 中的任意其它两中的任意其它两个不同的点个不同的点 ，使得，使得 X 在它们的连线上，这时称在它们的连线上，这时称 X 为凸为凸集的顶点。集的顶点。3.1 预备知识 2022/12/2944经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营

44、者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.2 线性规划问题基本定理定理定理1:1:若线性规划问题存在可行解，则问题的可行域是凸集。若线性规划问题存在可行解，则问题的可行域是凸集。证明证明:设设 是线性规划的任意两个可行解，则是线性规划的任意两个可行解，则于是对于任意的于是对于任意的 ，设，设 ，则，则 所以所以 也是问题的可行解，即可行域是凸集。也是问题的可行解，即可行域是凸集。2022/12/2945经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商

45、品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用引理引理:线性规划问题的可行解线性规划问题的可行解 X为基可行解的充要条件是为基可行解的充要条件是X的的正分量所对应的系数列向量线性无关。正分量所对应的系数列向量线性无关。证明证明:设设 （1 1）必要性显然。必要性显然。（2 2）设设 A A 的秩为的秩为m m。可行解。可行解 X X 的前的前 k k 个分量为正，且它们对应个分量为正，且它们对应的系数列向量的系数列向量 线性无关，则线性无关，则 。当当 时，时，恰好构成一组基，而恰好构成

46、一组基，而 就是这组基对应的基可行解。就是这组基对应的基可行解。当当 时，在时，在 基础上从其余列向量中可以找出基础上从其余列向量中可以找出个线性无关的向量，恰好构成一组基，而个线性无关的向量，恰好构成一组基，而 X 就是这组基对应的基可行解。就是这组基对应的基可行解。2022/12/2946经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用定理定理2:线性规划问题的基可行解线性规划问题

47、的基可行解 X 对应线性规划问题可行对应线性规划问题可行 域（凸集）的顶点。域（凸集）的顶点。证明证明:问题即是要证明问题即是要证明:X是基可行解是基可行解 X是可行域顶点，也即要证明是可行域顶点，也即要证明其逆否命题：其逆否命题：X不是基可行解不是基可行解 X不是可行域顶点不是可行域顶点。（1 1）X不是基可行解不是基可行解 X不是可行域顶点。不是可行域顶点。假设假设X是可行解，但不是基可行解，是可行解，但不是基可行解，X 的前的前 k 个分量为正个分量为正,其余分量为其余分量为0，则有则有又又X不是基可行解，所以由引理知，正分量对应的列向量不是基可行解，所以由引理知，正分量对应的列向量线性

48、相关。即存在一组不全为零的数线性相关。即存在一组不全为零的数 ，使得，使得2022/12/2947经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用非零常数用非零常数 乘以上式得：乘以上式得：（1）+（3）得：）得：（1）-（3）得：）得：令令选择合适的选择合适的 ，使得所有的，使得所有的于是于是 均是可行解，并且均是可行解，并且 ，所以，所以 X 不是可行不是可行域顶点。域顶点。20

49、22/12/2948经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（2）X不是可行域顶点不是可行域顶点 X不是基可行解不是基可行解。设设 不是可行域的顶点，因而可以找到可行域内不是可行域的顶点，因而可以找到可行域内另两个不同的点另两个不同的点 ，使得使得 ，用分量表示即为：用分量表示即为：易知，当易知，当 时，必有时，必有 所以所以所以所以于是（于是（1）-（2）得）得而而 不全为零

50、，于是知不全为零，于是知 线性相关，线性相关，X不是基可行解。不是基可行解。2022/12/2949经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用定理定理3:若线性规划问题有最优解，一定存在一个基可行解是若线性规划问题有最优解，一定存在一个基可行解是 最优解。最优解。引理：引理：有界有界 凸集中的任何一点均可表示成顶点的凸组合。凸集中的任何一点均可表示成顶点的凸组合。证明证明:假设假