运筹学基础及应用.ppt

运 筹 学( Operations Research )夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外 《《史记史记· 高祖本纪高祖本纪》》绪 论（（1）运筹学简述）运筹学简述（（2）运筹学的主要内容）运筹学的主要内容（（3）本课程的主要学习内容）本课程的主要学习内容（（4）运筹学的应用）运筹学的应用（（5）本课程的教材及参考书）本课程的教材及参考书（（6）本课程授课方式与考核）本课程授课方式与考核 本章主要内容：本章主要内容：一、古代朴素的运筹学思想一、古代朴素的运筹学思想国外国外³英文原名英文原名 Operations Research 简称简称““O.R.”³直译为：运用研究或作业研究直译为：运用研究或作业研究³正式出现于正式出现于19381938年年7 7月英国一份关于防空作战系统运月英国一份关于防空作战系统运行的研究报告中行的研究报告中中国古代运筹学案例中国古代运筹学案例二、运筹学的起源二、运筹学的起源（一）运筹学简述（一）运筹学简述运作研究运作研究(Operational Research)小组小组””:二战期间解决二战期间解决复杂的战略和战术问题。

例如：复杂的战略和战术问题例如：1. 1.如何合理运用雷达有效地对付德军空袭如何合理运用雷达有效地对付德军空袭2. 2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；损失最少；3. 3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等增加对德国潜艇的杀伤力等二战后运筹学的发展经历了三个阶段二战后运筹学的发展经历了三个阶段 （（1 1））19451945年到年到2020世纪世纪5050年代初年代初————创建时期创建时期 （（2 2））20 20 世纪世纪5050年代初到年代初到2020世纪世纪5050年代末年代末————成长时期成长时期 （（3 3）） 20 20 世纪世纪6060年代以来年代以来————迅速发展和普及的时期迅速发展和普及的时期•国内国内–19561956年成立第一个运筹学小组年成立第一个运筹学小组–19571957年从年从““夫运筹策帷幄之中，决胜于千里之外夫运筹策帷幄之中，决胜于千里之外””中中摘取摘取““运筹运筹””二字，将二字，将O.R.正式翻译为正式翻译为““运筹学运筹学””三、运筹学的定义三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供研究目的：对有限资源进行合理规划、使用，并提供 优化决策方案。

优化决策方案研究对象：复杂系统的组织和管理研究对象：复杂系统的组织和管理参考参考《《大英百科全书大英百科全书》》、、《《辞海辞海》》、、《《中国企业管理百科全书中国企业管理百科全书》》等四、运筹学研究的基本特点四、运筹学研究的基本特点• 系统的整体优化系统的整体优化• 多学科的配合多学科的配合 • 模型方法的应用模型方法的应用五、运筹学研究的基本步骤五、运筹学研究的基本步骤• 分析与表述问题分析与表述问题• 建立数学模型建立数学模型 • 对问题求解对问题求解• 对模型和模型导出的解进行检验对模型和模型导出的解进行检验• 建立对解的有效控制建立对解的有效控制• 方案的实施方案的实施（二）运筹学的主要内容（二）运筹学的主要内容数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、、动态规划等）动态规划等）图论图论存贮论存贮论排队论排队论对策论（博弈论）对策论（博弈论）决策论决策论（三）运筹学的应用（三）运筹学的应用 运筹学方法运筹学方法 应用例应用例 线性规划线性规划 生产结构优化生产结构优化 非线性规划非线性规划 投资组合优化投资组合优化 整数规划整数规划 选址问题选址问题 动态规划动态规划 资源分配问题资源分配问题 网络分析网络分析 工程计划优化工程计划优化 排队论排队论 服务系统优化服务系统优化 存贮论存贮论 订货库存管理订货库存管理 决策分析决策分析 机会选择机会选择  运筹学的广泛实际背景促使其不断发展并运筹学的广泛实际背景促使其不断发展并 在经济管理和在经济管理和系统工程等多领域中发挥着令系统工程等多领域中发挥着令 人瞩目的重要作用。

人瞩目的重要作用  诺贝尔经济学奖从诺贝尔经济学奖从1969年首发至今的年首发至今的57 位获奖者中就有位获奖者中就有多位是运筹学家多位是运筹学家  1975年诺贝尔经济学奖授给了库普曼和康脱罗维年诺贝尔经济学奖授给了库普曼和康脱罗维 奇，以表奇，以表彰首先将线性规划与经济问题相联系而彰首先将线性规划与经济问题相联系而 做出的贡献；做出的贡献； 1994年诺贝尔经济学奖授给了三位博弈论专家：年诺贝尔经济学奖授给了三位博弈论专家： 纳什、泽尔纳什、泽尔腾、海萨尼博弈论已经成为当代经腾、海萨尼博弈论已经成为当代经 济学的基石济学的基石  2005年以色列经济学家罗伯特年以色列经济学家罗伯特-奥曼和美国经济奥曼和美国经济 学家托马学家托马斯斯-斯切林，因斯切林，因““通过博弈论分析加强了通过博弈论分析加强了 我们对冲突和合作的我们对冲突和合作的理解理解””所作出的贡献而获奖所作出的贡献而获奖 发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排成本进行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送和优化炼油程序及产品供应、配送和营销营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的销售中心选址优化商业用户的销售中心选址每年节约成本每年节约成本4.064.06亿美亿美元，销售额大幅增加元，销售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点控制成本库存（制定最优再定购点和定购量确保安全库存）和定购量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司制定最优铁路时刻表并调整铁路日制定最优铁路时刻表并调整铁路日运营量运营量每年节约成本每年节约成本15001500万美万美元，年收入大幅增加。

元，年收入大幅增加Taco BellTaco Bell优化员工安排，以最低成本服务客优化员工安排，以最低成本服务客户户每年节约成本每年节约成本13001300万美万美元元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实优化配置上千个国内航线航班来实现利润最大化现利润最大化每年节约成本每年节约成本1 1亿美元亿美元（四）本课程的教材及参考书（四）本课程的教材及参考书选用教材选用教材 Ø《《运筹学基础及应用运筹学基础及应用》》胡运权主编胡运权主编 （第五版）高等教（第五版）高等教育出版社育出版社参考教材参考教材Ø《《运筹学教程运筹学教程》》胡运权主编胡运权主编 （第（第4 4版）清华出版社版）清华出版社Ø《《管理运筹学管理运筹学》》韩伯棠主编韩伯棠主编 （第（第2 2版）高等教育出版社版）高等教育出版社Ø《《运筹学运筹学》》( (修订版修订版) ) 钱颂迪主编钱颂迪主编 清华出版社清华出版社 （五）本课程的主要学习内容（五）本课程的主要学习内容 第一章第一章 线性规划及单纯形法线性规划及单纯形法 第二章第二章 线性规划的对偶理论线性规划的对偶理论 第三章第三章 运输问题运输问题 第四章第四章 整数规划与分配问题整数规划与分配问题 （六）本课程授课方式与考核（六）本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（（3030％）％）课堂考勤课堂考勤（（1212％）％）平时作业平时作业（（1818％）％）期末成绩期末成绩（（7070％）％）讲授为主，结合讨论、习题作业讲授为主，结合讨论、习题作业第一章第一章 线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Method线性规划-发展简史 法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。

1939年苏联数学家年苏联数学家Л Л.В В.康托罗维奇康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视1947年美国数学家年美国数学家G.B.丹齐克丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法单纯形法，为这门学科奠定了基础1947年美国数学家年美国数学家J.von诺伊曼提出对诺伊曼提出对偶理论偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力1951年美国经济学家年美国经济学家T.C.库普曼斯库普曼斯把线性规划应用到经济领域把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法例如，1954年年C.莱姆基提出对偶单纯形法莱姆基提出对偶单纯形法，1954年年S.加斯和加斯和T.萨迪等人解决了线性规划的灵敏度分析萨迪等人解决了线性规划的灵敏度分析和参数规划问题，和参数规划问题，1956年年A.塔克提出互补松弛定理，塔克提出互补松弛定理，1960年年G.B.丹齐克和丹齐克和P.沃尔夫提出分解算法沃尔夫提出分解算法等线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。

由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题1979年苏联数学家年苏联数学家Л Л.Г Г.哈奇扬提出解线性规划问题的椭球哈奇扬提出解线性规划问题的椭球算法算法，并证明它是多项式时间算法1984年年美国贝尔实验室的印度数学家N.卡马卡提出解线性规划问题的新卡马卡提出解线性规划问题的新的多项式时间算法的多项式时间算法-内点算法内点算法用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50现已形成线性规划多项式算法理论50年代后线性规划的应用范围不断扩大 1. 1939年，前苏联科学家康托洛维奇年，前苏联科学家康托洛维奇--《《生产组织与管理中的数学方法生产组织与管理中的数学方法》》是线性是线性规划应用于工业生产问题的开山之作规划应用于工业生产问题的开山之作； (LEONID VITALIYEVICH KANTOROV(1912-1986) 2. 1947年，美国数学家乔治年，美国数学家乔治··伯纳德伯纳德··丹齐格丹齐格--单纯形法，被称单纯形法，被称为线性规划之父。

为线性规划之父 George Bernard Dantzig(1914~2005)　　 丹齐格在丹齐格在1946年获伯克利大学的博士学位年获伯克利大学的博士学位1947年，年，33岁提出岁提出了解决一种最优化问题的单纯形法了解决一种最优化问题的单纯形法,该方法奠定了线性规划的基础，使该方法奠定了线性规划的基础，使得经济学、环境科学、统计学应用等学科获得了迅速发展得经济学、环境科学、统计学应用等学科获得了迅速发展Dantzig也因而被誉为也因而被誉为““线性规划之父线性规划之父”” 1952年他在兰德公司任研究数学年他在兰德公司任研究数学家，在公司电脑上实行线性规划家，在公司电脑上实行线性规划1960年他被母校聘任教授计算机年他被母校聘任教授计算机科学，终于当上运筹学中心主任科学，终于当上运筹学中心主任1966年他在史丹福大学当类似职年他在史丹福大学当类似职位，留在那里直到位，留在那里直到1990年代退休年代退休　　　　Dantzig在运筹学建树极高，获得了包括在运筹学建树极高，获得了包括““冯诺伊曼理论奖冯诺伊曼理论奖””在在内的诸多奖项他在内的诸多奖项。

他在Linear programming andextensions一书中研一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献他究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确定规划SIAM Journal on Optimization1991年创刊号是献给他的年创刊号是献给他的Mathematical Programming Society为表彰丹齐格，设立丹齐格奖，为表彰丹齐格，设立丹齐格奖，1982年起每三年颁给一至两位在数学规划有突出贡献的人年起每三年颁给一至两位在数学规划有突出贡献的人xa此为无约束的极值问题此为无约束的极值问题§1.1 一般线性规划问题的数学模型一般线性规划问题的数学模型1-1 1-1 问题的提出问题的提出例例1 1 用一块边长为用一块边长为a的正方形铁皮做一个无盖长方体容器，的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？应如何裁剪可使做成的容器的容积最大？解：如图设四个角上减去的小正方形边解：如图设四个角上减去的小正方形边长为长为x，则容器体积为：，则容器体积为：时，容积最大时，容积最大 例例2 2 常山机器厂生产常山机器厂生产 I I、、IIII 两型产品。

这两型两型产品这两型产品都分别要在产品都分别要在A A、、B B、、C C三种不同设备上加工按三种不同设备上加工按工艺规定，生产每件产品的单位利润、消耗三种设工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：备的工时以及各种设备工时的限额如下表： 单位产品消耗设单位产品消耗设备工时备工时I IIIII设备工时限量设备工时限量（小时）（小时） 设备设备A A设备设备B B设备设备C C2 24 40 02 20 05 5121216161515单位利润（元）单位利润（元）2 23 3如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？如何安排生产才能使总的利润最大？解：设计划期内两种产品的数量分别为解：设计划期内两种产品的数量分别为x x1 1，，x x2 2，则总利润为：，则总利润为：maxz=2 x1+3 x2 2 x1+2 x2   124x1   16 5 x2   15x1 0，， x2  0简记为：简记为： s.t.（约束于：）（约束于：）z=2 x1+3 x2在满足限制条件下求在满足限制条件下求z的最大值。

的最大值此为有约束极值问题此为有约束极值问题1-2 1-2 线性规划问题的数学模型线性规划问题的数学模型原型原型模型模型数学模型数学模型提炼提炼数学工具数学工具1 1、、原型原型：现实世界中人们关心、研究的实际对象现实世界中人们关心、研究的实际对象 模型模型：将某一部分信息简缩、提炼而构造的原型替代物将某一部分信息简缩、提炼而构造的原型替代物 数学模型数学模型：对现实世界的一个特定对象，为达到一定目的，：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设根据内在规律做出必要的简化假设, ,并运用适当数学工具得到并运用适当数学工具得到的一个数学结构的一个数学结构3 3、规划问题数学模型的三要素、规划问题数学模型的三要素（（2 2））目标函数目标函数：问题要达到的目标要求，表示为决策变量的：问题要达到的目标要求，表示为决策变量的函数用 z= =f( (x1 1，，x2 2，，……，，xn n) )表示1 1））决策变量决策变量：决策者为实现规划目标采取的方案、措施，：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量用是问题中要确定的未知量。

用x1 1，，x2 2，，……，，xn n表示3 3））约束条件约束条件：决策变量取值时受到的各种可用资源的限制，：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式表示为含决策变量的等式或不等式2 2、规划问题、规划问题即求目标函数在若干约束条件下的最值即求目标函数在若干约束条件下的最值4 4、线性规划问题（、线性规划问题（Linear ProgrammingLinear Programming）的数学模型）的数学模型（（2 2））一般形式一般形式：：（（1 1））条件条件：决策变量为可控的连续变量，目标函数和约束条：决策变量为可控的连续变量，目标函数和约束条件都是线性的简记为件都是线性的简记为““L.P.” max (或或 min) z=c1x1+c2x2+…+cnxn s.t. a11x1+a12x2+…+a1nxn ≤（（=，，≥））b1 a21x1+a22x2+…+a2nxn ≤（（=，，≥）） b2 … am1x1+am2x2+…+amnxn≤（（=，，≥）） bm x1 , x2, …, xn≥0（（3 3））其他形式其他形式：：连加形式连加形式向量形式向量形式其中 称为价值行向量价值行向量；决策列向量决策列向量系数列向量系数列向量右端列向量右端列向量矩阵形式矩阵形式其中 称为价值行向量；称为价值行向量；决策列向量决策列向量右端列向量右端列向量约束矩阵或系数矩阵约束矩阵或系数矩阵1-3 1-3 线性规划问题的标准形式线性规划问题的标准形式1 1、标准形式、标准形式或或2 2、条件、条件目标函数求极大值目标函数求极大值约束条件全是等式（线性方程组）约束条件全是等式（线性方程组）决策变量全非负决策变量全非负右端常数全非负右端常数全非负3 3、标准化方法、标准化方法（（1）若目标函数求极小值，即）若目标函数求极小值，即则令则令 转化为转化为（（2 2）若约束条件为不等式，）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。

转化为等式约束条件注意注意：松弛变量在目标函数中系数全为：松弛变量在目标函数中系数全为0约束为约束为≥不等式，减去松弛变量，化为等式约束条件；不等式，减去松弛变量，化为等式约束条件；约束为约束为≤不等式，加上松弛变量，化为等式约束条件不等式，加上松弛变量，化为等式约束条件多多退退少少补补例：例：max z=2 x1+3 x2 2 x1+2 x2   124x1   16 5 x2   15x1 0，， x2  0 s.t.标准化标准化（（3 3）若决策变量）若决策变量xj≤0，则令，则令（（4 4）若决策变量）若决策变量xj取值无限制，则令取值无限制，则令（（5 5）若约束等式的右端常数）若约束等式的右端常数bi ≤ 0 0，则等式两边同时乘以，则等式两边同时乘以“-1-1”其中其中（（“一分为二一分为二”））例：例：将下列线性规划模型化为标准形式将下列线性规划模型化为标准形式则问题化为标准形式：则问题化为标准形式：并引入松弛变量并引入松弛变量x4, x5,课堂练习：将下列线性规划问题化为标准形式线性规划问题的数学模型标准形式如下：1-4 1-4 线性规划问题的解线性规划问题的解已知线性规划的标准形式：已知线性规划的标准形式：或或1 1、、求解线性规划问题求解线性规划问题：：从满足（从满足（2）、（）、（3）的方程组中找出一个解使目标函）的方程组中找出一个解使目标函数（数（1）达到最大值。

达到最大值2 2、、可行解可行解：：所有可行解的集合所有可行解的集合可行域可行域：：满足约束条件（满足约束条件（2）、（）、（3）的解记做记做最优解最优解：： 使目标函数达到最大值的可行解使目标函数达到最大值的可行解（（1 1））基基：设：设A A为线性规划问题约束条件的为线性规划问题约束条件的 m   n 系数矩阵系数矩阵（（m

满足决策变量非负要求的基解7 7））可行基可行基：与基可行解对应的基与基可行解对应的基8 8））基最优解基最优解：使目标函数达到最大值的基可行解使目标函数达到最大值的基可行解注意：基解最多注意：基解最多 个9 9））最优基最优基：与基最优解对应的基与基最优解对应的基4 4、线性规划问题各种解之间的关系、线性规划问题各种解之间的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解例例：在下述线性规划问题中，列出全部基、基解、基：在下述线性规划问题中，列出全部基、基解、基可行解，并指出最优解可行解，并指出最优解解：系数矩阵为解：系数矩阵为若取基为若取基为 B=(P1, P2, P3),则基变量为则基变量为x1, x2, x3, 非基变量为非基变量为x4, x5令令x4=x5=0，代入约束方程组，代入约束方程组解得解得x1=4, x2=3, x3=-2从而得到一个基解从而得到一个基解 X=(4,3,-2,0,0) T这个基解不是基可行解！这个基解不是基可行解！该该 L.P. 共有共有8个基解若取基为若取基为 B=(P3, P4, P5)=I3,则基变量为则基变量为x3, x4, x5, 非基变量为非基变量为x1, x2令令x1=x2=0，代入约束方程组，代入约束方程组从而得到一个基解从而得到一个基解 X=(0,0,12,16,15) T这个基解是基可行解！这个基解是基可行解！（注意：选择单位矩阵为基可以较方便的求出一个基可行解。

注意：选择单位矩阵为基可以较方便的求出一个基可行解同理可得其他基解同理可得其他基解. .基基B基解基解是基是基可行可行解？解？目标目标函数函数值值x1x2x3x4x5P1P2P34 43 3-2-20 00 0否否1717P1P2P43 33 30 04 40 0是是1515P1P2P54 42 20 00 05 5是是1414P1P3P54 40 04 40 01515是是8 8P1P4P56 60 00 0-8-81515否否1212P2P3P40 03 36 616160 0是是9 9P2P4P50 06 60 01616-15-15否否1818P3P4P50 00 0121216161515是是0 0（最优基）（最优基）（最优解）（最优解）（最优目标函数值）（最优目标函数值）§§1.2 1.2 图解法图解法1 1、适用范围：仅含两个决策变量的、适用范围：仅含两个决策变量的 L.P.2、步骤：、步骤：（（1 1）作平面直角坐标系，标上刻度；）作平面直角坐标系，标上刻度；（（2 2）作出约束方程所在直线，确定可行域；）作出约束方程所在直线，确定可行域；（（3 3）作出一组目标函数的等值线，判定优化方向；）作出一组目标函数的等值线，判定优化方向；（（4 4）沿优化方向移动，确定与可行域相切的点，确定）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优目标函数值。

最优解，并计算最优目标函数值例：例： 用图解法求解下列线性规划问题用图解法求解下列线性规划问题1）） max z=2x1+3x2 s.t. 2x1+2x2 12 ----------①① 4x1  16 ----------②② 5x2  15 ----------③③ x1 0, x2 0 x1x222468460①① 2x1+2x2=12 ③③ 5x2 =15②② 4x1 =16 Z=6Z=0A(3,3)Zmax有有唯一最优解唯一最优解，，当当 x1=x2=3 时，时，Zmax = 15= 15C(4,0)D(0,3)(0,0)B(4,2)顶点顶点基可行解基可行解A（（3,3））（（3,3,0,4,0））B（（4,2））（（4,2,0,0,5））C（（4,0））（（4,0,4,0,15））D（（0,3））（（0,3,6,16,0））O（（0,0））（（0,0,12,16,15））一一对应一一对应x1x2omax Z = 3x1 + 3x2 x1 ≥ 0 , x2 ≥ 0s.t.s.t. 2x1 + 2x2 ≤ 12 4x1 ≤ 16 5x2 ≤ 154x1=16（ ≤）5x5x2 2 =15 =15（（ ≤ ≤））2x1 + 2x2 =12（ ≤）红色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=18是唯一的。

D可行域(4,2)(3,3)x1x2omax Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0s.t.4x1 ≤ 164x1=16（ ≤）无界解(无最优解)x1x2无可行解(即无最优解)max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0s.t.2x1 +2x2 ≤ 12x1 +2x2 ≥ 14x1 +2x2 = 14（ ≥）2x1 +2x2 =12（≤ )3 3、线性规划问题解的类型、线性规划问题解的类型（（1）唯一最优解：只有一个解为最优解）唯一最优解：只有一个解为最优解（（2）无穷多最优解：有无穷多个解为最优解）无穷多最优解：有无穷多个解为最优解（（3）无界解：目标函数的取值无界）无界解：目标函数的取值无界（（4）无可行解：可行域为空集，即存在互相矛盾的约束条）无可行解：可行域为空集，即存在互相矛盾的约束条件4 4、可行域的特征、可行域的特征（（1 1）若）若L.P.的可行域不是空集，则可行域为凸集的可行域不是空集，则可行域为凸集2 2）若）若L.P.有最优解，则一定可以在可行域的顶点上找到最有最优解，则一定可以在可行域的顶点上找到最优解。

优解3 3））L.P.L.P. 的顶点与基可行解一一对应的顶点与基可行解一一对应 §§1.3 1.3 单纯形法单纯形法（（Simplex Method））原理原理3-1 3-1 预备知识：凸集与顶点预备知识：凸集与顶点（（1 1）凸集：对于集合）凸集：对于集合C C中任意两点连线段上的点，若全在中任意两点连线段上的点，若全在C C内，内，则称集合则称集合C C为凸集或对任何或对任何X X1 1∈∈C C，， X X2 2∈∈C，有，有a X X1 1+(1-+(1-a) X) X2 2 ∈∈C C，则称，则称C C为为凸集凸集. 直观特征：图形从内部向外部凸出直观特征：图形从内部向外部凸出凸集凸集非凸集非凸集（（2 2）顶点：凸集中不在任意两点的连线段内部的点顶点：凸集中不在任意两点的连线段内部的点X1X4X3X5X23-2 3-2 3-2 3-2 几个基本结论几个基本结论几个基本结论几个基本结论（（1）若线性规划问题存在可行解，则可行域为凸集若线性规划问题存在可行解，则可行域为凸集 （（2）线性规划问题的可行解）线性规划问题的可行解 X=(x1, x2, ···, xn)T 为基可行解为基可行解的充要条件是的充要条件是 X 的正分量所对应的系数列向量线性无关。

的正分量所对应的系数列向量线性无关3）线性规划问题的基可行解）线性规划问题的基可行解1-11-1对应可行域的顶点对应可行域的顶点 例如：比较表例如：比较表1-1和图和图1-3 （（4）若线性规划问题有最优解，则一定存在一个基可行解）若线性规划问题有最优解，则一定存在一个基可行解为最优解为最优解注意：注意：若线性规划问题有最优解，不一定所有的最优解若线性规划问题有最优解，不一定所有的最优解都是基可行解都是基可行解单纯形法的计算步骤：单纯形法的计算步骤： 初始基可行解初始基可行解使目标函数值增大使目标函数值增大的新的基可行解的新的基可行解是否最优解？是否最优解？结束结束是是否否3-3 3-3 3-3 3-3 确定初始基可行解确定初始基可行解已知线性规划问题形如：已知线性规划问题形如：引入松弛变量引入松弛变量xsi ( i=1,2,…,m )化为标准形式：化为标准形式：注意：约束条件全是≤此时系数矩阵为：此时系数矩阵为：取后取后m列对应的单位子矩阵为基，得到初始基可行解：列对应的单位子矩阵为基，得到初始基可行解：X=( 0,0,······,0, b1,b2,······,bm)Tn 个个 0 0注意：用这个方法确定初始基可行解，必须保证约束注意：用这个方法确定初始基可行解，必须保证约束条件全是条件全是““≤≤”” 。

 取前取前m m列为基，则基可行解为列为基，则基可行解为X（（0））=(x10, x20,···, xm0,0, ···, 0)T ，，且前且前m个分量为正值个分量为正值P1 P2 …… Pm Pm+1 …… Pj…… Pn 1 0 …… 0a 1,m+1 ····· a1j ····· a 1n 0 1 …… 0 a 2,m+1 ····· a2j ····· a 2n 0 0 …… 1a m,m+1 ····· amj ····· a mn………………………………………………3-4 3-4 3-4 3-4 从一个基可行解转换为另一个基可行解从一个基可行解转换为另一个基可行解n-m 个个 0 0且系数矩阵且系数矩阵A为为因为因为X（（0））是基可行解，所以满足约束方程组：是基可行解，所以满足约束方程组：又因为又因为P1,P2,…,Pm是一个基，非基变量是一个基，非基变量xj ( j≥m+1 )的系数的系数列向量列向量 Pj 可以用这个基线性表示：可以用这个基线性表示：①①将上式乘以一个正数将上式乘以一个正数θ得到：得到：移项得：移项得：上式与上式与①①式相加得：式相加得：从而找到了满足约束方程组的另一个解：从而找到了满足约束方程组的另一个解：第第j个分量个分量为使为使成为基可行解，只需要取成为基可行解，只需要取即可。

即可第第 j 个分量个分量（（j≥m+1））注意：若某个注意：若某个x xi i0 0=0=0，则允许，则允许θ=0θ=03-5 3-5 最优性检验和解的判别最优性检验和解的判别将基可行解将基可行解X（（0））和和X（（1））分别分别代入目标函数中：代入目标函数中：为了比较为了比较 Z（（0））和和Z（（1）） 的大小，记的大小，记称为线性规划问题的非基变量称为线性规划问题的非基变量xj的的检验数检验数又又  >0>0，，∴∴有如下结论：有如下结论：(1) (1) 若对所有若对所有j≥m+1，有，有 j ＜＜ 0 0 ，则，则z（（1））＜＜ z （（0）） ，即，即z （（0））为为最优函数值，最优函数值，X（（0））为为唯一最优解唯一最优解；；(2) (2) 若对所有若对所有j ≥m+1 ，，有有 j   0，且，且存在某个非基变量的检验数存在某个非基变量的检验数 k=0，则将，则将Pk作为新的基向量得出新的基可行解作为新的基向量得出新的基可行解X（（1 1）） ，满足，满足z（（1）） = z （（0）） ，故，故z（（1）） 也也为最优函数值，从而为最优函数值，从而 X（（1））也也为最优解，为最优解，∴ ∴ X（（0）） 、、X（（1）） 连线上所有点均为最优解，因此该线性规划连线上所有点均为最优解，因此该线性规划模型具有模型具有无穷多最优解无穷多最优解；；(3) (3) 若存在某个若存在某个 j > > 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则，则当当  + + 时，有时，有z（（1））  + + ，，∴ ∴ 该线性规划模型具有该线性规划模型具有无界解无界解。

§§1.4 1.4 单纯形法的计算步骤单纯形法的计算步骤1 1、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵前提：标准化的线性规划问题的系数矩阵含有单位子矩阵不妨假设不妨假设A中前中前m列对应的子矩阵是单位列对应的子矩阵是单位矩阵，取其为基矩阵，取其为基B，得到初始基可行解，得到初始基可行解m+3行行n+4列列第第1行：价值行行：价值行 cj第第2行：变量行行：变量行 xj最后一最后一行：检验数行行：检验数行 σj第第1列：基价值列列：基价值列 CB第第2列列：基变量列：基变量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 θθ主体：系数矩阵主体：系数矩阵Am×n2 2、单纯形表的结构、单纯形表的结构3 3、初始单纯形表：含初始基可行解的单纯形表、初始单纯形表：含初始基可行解的单纯形表 最优单纯形表：含最优解的单纯形表最优单纯形表：含最优解的单纯形表4 4、单纯形法（、单纯形法（ Simplex MethodSimplex Method ）：）： 利用单纯形表求解线性规划问题的方法。

利用单纯形表求解线性规划问题的方法5 5、单纯形法的计算步骤、单纯形法的计算步骤(1) (1) 化化 L.P.问题为标准形式问题为标准形式, ,建立初始单纯形表；建立初始单纯形表；(3) (3) 计算计算(4)(4) 以以alk为主元素为主元素( (简称主元，用简称主元，用[ ][ ]表示表示) )，进行线性方程组，进行线性方程组 的的初等行变换，将主元列初等行变换，将主元列Pk化为单位向量得到新的单纯形表，化为单位向量得到新的单纯形表，转入转入(2)(2)最大正检验数决定换入变量）（最大正检验数决定换入变量）（最小比值（最小比值θ决定换出变量决定换出变量））例例1：用单纯形法求解下列线性规划问题：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2   124x1   16 5 x2   15x1 0，， x2  0 s.t.解：先标准化解：先标准化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 再列初始单纯形表：再列初始单纯形表：θ6-32 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 1615 2 2 1 0 0 6 4 0 0 1 0 - 0 [5] 0 0 1 3 2 3 0 0 0以以[5][5]为主元进为主元进行初等行变换行初等行变换Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 6 16 3 [2] 0 1 0 -2/5 3 4 0 0 1 0 4 0 1 0 0 1/5 - 2 0 0 0 -3/5x1 1为换入变量为换入变量下面开始单纯形法迭代：下面开始单纯形法迭代：x5 5为换出变量为换出变量x2 2为换入变量为换入变量以以[2][2]为主元进为主元进行初等行变换行初等行变换x3 3为换出变量为换出变量主元化为主元化为1，主元列，主元列的其他元素化为的其他元素化为0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 ½ 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5此时得到唯一最优解此时得到唯一最优解X*=(3,3)T, , Zmax=15=15。

例例2 2 用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题解：先标准化解：先标准化 2 1 0 0 54 x3x400 x1 x2 x3 x4bxBcB 2 1 0 0cj 2415351 0[6]201 0 0 x3x102 x1 x2 x3 x4bxBcB 2 1 0 0cj4301[4]1 01/3-1/21/61/3-1/33/412 0 0 -1/12 -7/24 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810 -1/125/24唯一最优解6、单纯形法中存在的问题、单纯形法中存在的问题（（1 1）） 存在两个以上的最大正检验数存在两个以上的最大正检验数任取一个最大正检验数对应的变量作为换入变量任取一个最大正检验数对应的变量作为换入变量2 2）） θ出现两个以上相同的最小值。

出现两个以上相同的最小值任取一个最小任取一个最小θ对应的变量作为换出变量对应的变量作为换出变量此时此时L.P.问题出现退化现象问题出现退化现象练习：练习：5-1 5-1 人工变量法（大人工变量法（大M法）法）§1.5 单纯形法的进一步讨论 前面讨论了在标准型中系数矩阵有单位矩阵，很前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解在实际问题中有些模型容易确定一组基可行解在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量这种人为加的变量称为人工变得到一组基变量这种人为加的变量称为人工变量，构成的可行基称为人工基，用大量，构成的可行基称为人工基，用大MM法或两阶法或两阶段法求解，这种用人工变量作桥梁的求解方法称段法求解，这种用人工变量作桥梁的求解方法称为人工变量法为人工变量法例例1：用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题解：先标准化为解：先标准化为系数矩阵系数矩阵但是但是A中没有单位矩阵，在中没有单位矩阵，在A中人为的增加两列中人为的增加两列此时对应的约束方程组为对应的约束方程组为：该问题新增加了两个变量：x4, x5（称为人工变量）（称为人工变量）A有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。

有单位子矩阵，选择这个单位矩阵作为基（称为人工基）为使 必须保证在可行解中人工变量必须保证在可行解中人工变量x4=x5=0，，故令故令x4，，x5在目标函数中的系数为在目标函数中的系数为－－M （其中（其中M表示任意大的正数），表示任意大的正数），这种添加人工变量求解这种添加人工变量求解LP的方法称为的方法称为人工变量法人工变量法,计算过程中出现了计算过程中出现了M，这种方法也称为，这种方法也称为大大M法法等价于于是，这个线性规划问题转化为：于是，这个线性规划问题转化为：以下可用单纯形法继续求解以下可用单纯形法继续求解Cj →x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 -2 -3 0 -M -M34x4 x5-M -Mcj - zj -2+2M-3+3M-M03/1=34/2= 21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj - zj -1/2+M/2 0 -M 0 3/2-3M/2-M -3241 0 -2 2 -1 0 1 1 -1 1x1 x221cj - zj 0 0 -1 1-M 1-M-2 -3θx50唯一最优解故 zmin=7注意：此时人工变量x4=x5=0说明：说明： 若表中所有若表中所有 j  0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型型无可行解无可行解。

采用大采用大M法求解线性规划模型时，如果模型中法求解线性规划模型时，如果模型中各个系数与各个系数与M的值非常接近或相差很大，若用手工计算的值非常接近或相差很大，若用手工计算不会出现问题但是若利用计算机求解，则容易引起混不会出现问题但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大淆，使得机器判断出错，从而使大M法失效 在这种情况下，可采用下面的两阶段法进行计算在这种情况下，可采用下面的两阶段法进行计算5-2 5-2 两阶段法两阶段法( (将将L.P.问题分成两个阶段来考虑问题分成两个阶段来考虑) ) 第一阶段第一阶段: : 判断原判断原L.P.L.P.问题是否存在可行解问题是否存在可行解 给原给原L.P.L.P.问题加入人工变量，并构造仅含人工变量的目标问题加入人工变量，并构造仅含人工变量的目标函数函数w（（人工变量在人工变量在w中的系数一般取为中的系数一般取为1 1）并求）并求w的最小值；的最小值；然后用单纯形法求解若求得然后用单纯形法求解若求得wmin=0=0，则该问题有可行解，进，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。

入第二阶段，否则该问题无可行解，结束 第二阶段：将第第二阶段：将第一一阶段得到的最终表去掉人工变量，并阶段得到的最终表去掉人工变量，并将目标函数还原为原将目标函数还原为原L.P.问题的目标函数（即修改最终表中问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解用单纯形法求解例：用两阶段法求解下列线性规划问题例：用两阶段法求解下列线性规划问题标准化引入人工变量z′(1) (1) 第一阶段，构造判断是否存在可行解的模型：第一阶段，构造判断是否存在可行解的模型： 用单纯形法求解这个问题，先标准化为；用单纯形法求解这个问题，先标准化为；Cj →x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj - zj 2 3-103/1=34/2= 21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj - zj 1/2 0 -1 0 -3/2-1 0241 0 -2 2 -1 0 1 1 -1 1x1 x221cj - zj 0 0 0 -1 -10 0θx50最优解本问题有可行解，进入第二阶段 (2) (2) 第二阶段第二阶段 先在第一阶段的最终单纯形表去掉人工变量，再还原原先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即目标函数，即 max z′=-2=-2x1 1-3-3x2 2+0+0x3 3，，继续迭代：继续迭代：Cj →x1x2x3XBbCB1 0 -2 0 1 1 -2 -3 0 21x1 x2-2 -3cj - zj 0 0-1唯一最优解故 zmin=7注意：两阶段法中不再出现大M，但需要解两个线性规划问题，要注意目标函数系数的变化。

5-3 关于解的判别例例7 用单纯形法解下列线性规划用单纯形法解下列线性规划无穷多解当所有的当所有的 ，但某一非基变量检验数，但某一非基变量检验数 ，存，存在无穷多最优解的条件是在无穷多最优解的条件是Ps列向量中至少存在一个元列向量中至少存在一个元素素 ，且能找出最优解，且能找出最优解.例例8 用单纯形法解下列线性规划用单纯形法解下列线性规划无界解无界解 若存在某个若存在某个 j > > 0 0，但对应的第，但对应的第j列系数全非正，即列系数全非正，即aij 0 0，则问题的解无界，则问题的解无界. .例例9 用单纯形法解下列线性规划用单纯形法解下列线性规划无可行解无可行解若表中所有若表中所有 j  0 0 ，但存在非，但存在非0 0的人工变量的人工变量 ，则该模，则该模型无可行解型无可行解用最终单纯形表判断线性规划问题解的类型：用最终单纯形表判断线性规划问题解的类型：解的类型解的类型最终表的特征最终表的特征无可行解无可行解有非有非0 0的人工变量的人工变量有有可可行行解解唯一最优解唯一最优解无无非非0 0的人的人工变量，非基变量的检验工变量，非基变量的检验数全为负数数全为负数无穷多最优解无穷多最优解无非无非0 0的人工的人工变量，非基变量的检验变量，非基变量的检验数全非正，且有某个非基变量的检验数全非正，且有某个非基变量的检验数为数为0 0无界解无界解无非无非0 0的的人工变量，有某个非基变量人工变量，有某个非基变量的检验数为正数，但该变量对应的系的检验数为正数，但该变量对应的系数全为非正数数全为非正数已知线性规划问题形如：已知线性规划问题形如：5-4 单纯形法计算的向量、矩阵描述引入松弛变量xs 记记X=(XB,XN,XS)T其中，其中， XS为松弛变量，在初始表中是基变量；为松弛变量，在初始表中是基变量； XB为为最终表中基变量；最终表中基变量； XN表示表示既不是初始表的基变量又不是最终表的基变量。

既不是初始表的基变量又不是最终表的基变量 注意：注意：XS和和XB允许有公共变量允许有公共变量2 2））A=(B,N,I) B,N,I分别为分别为XB 、、XN 、、 XS在初始表中在初始表中对应对应的矩阵则（则（1 1））C=(CB,CN,0) CB,CN,0分别为分别为XB 、、XN 、、 XS在目标函数中的系数在目标函数中的系数3 3））A′=(I,N′,B-1) I,N′,B-1分别为分别为XB 、、XN 、、 XS在最终表中在最终表中对应对应的矩阵约束方程组两端同时左乘B-1，则可得如下表达式：初始单纯形表初始单纯形表最终单纯形表最终单纯形表用单纯形表表示如下：用单纯形表表示如下：XS bB N IXB b´ I N´ B-1初始表初始表 X XB B X XN N X XS S cj - zj 0,······,0  N´  S´=（（-y1,-y2,…,-ym））=-YT 最终表最终表 X XB B X XN N X XS S cj - zj B N 0,······,0 比较得：比较得：b´ =B-1b N´ =B-1N 或者或者 Pj´ =B-1Pj S´ = -CB B-1=-YT N´ = CN-CB B-1 N = CN-YT N或者或者 j´=Cj-CBB-1 Pj···其中其中B B-1-1为初始表中基变量在最终表对应的系数矩阵，为初始表中基变量在最终表对应的系数矩阵， B B为最终表中基变量在初始表对应的系数矩阵。

为最终表中基变量在初始表对应的系数矩阵例：用单纯形法求解下列线性规划问题.max z=2 x1+3 x2 2 x1+2 x2  124x1  16 5 x2  15x10， x2 0 s.t.解：先标准化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 得到初始单纯形表：θ6-3 2 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 ½ 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5最终单纯形表：X4010X4010可以验证：三三要要素素决策变量决策变量约束条件约束条件目标函数目标函数两两个个三个三个以上以上xj≥0xj无无约束约束xj ≤ 0 bi ≥0bi < 0≤=≥maxZminZxs xa标标准准化化图图解解法法、、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj = xj′ - xj″ xj′ ≥0xj″ ≥0令令 xj ′=- xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z′=- Z 0-M根据上表可以列出初始单纯形表根据上表可以列出初始单纯形表5-5 5-5 单纯形法小结单纯形法小结个数取值限制右端常数约束方向要求系数列初始表列初始表§1.7 应用举例 一般而言，一个经济、管理问题要满足以下条一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：件，才能建立线性规划模型： ⑴ ⑴. .需要求解问题的目标能用数值指标来反映，需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；且能用线性函数来描述目标的要求； ⑵ ⑵. .为达到这个目标存在多种方案；为达到这个目标存在多种方案； ⑶ ⑶. .要求达到的目标是在一定条件下实现的，这要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。

些条件可用线性等式或不等式来描述（一）、混合配料问题例：某糖果厂用原料例：某糖果厂用原料A A、、B B、、C C加工成三种不同牌号的糖果甲、乙、丙已知加工成三种不同牌号的糖果甲、乙、丙已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示问该厂每月生产这三三种牌号糖果的单位加工费用及售价如下表所示问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大请建立这个问题的线性规种牌号糖果各多少千克，能使该厂获利最大请建立这个问题的线性规划模型甲甲乙乙丙丙原料成本（元原料成本（元/kg/kg））每月限制用每月限制用量（量（kgkg））A AB BC C≥60﹪≥60﹪≤≤20﹪20﹪≥30﹪≥30﹪≤≤50﹪50﹪ ≤≤60﹪60﹪2.002.001.501.501.001.00200020002500250012001200加工费（元加工费（元/kg/kg））0.500.500.400.400.300.30售价（元售价（元/kg/kg））3.403.402.852.852.252.25解：用i=1,2,3表示原料A、B、C；用j=1,2,3表示糖果甲、乙、丙；设xij为生产第j种糖果使用的第i种原料的质量，则该问题的数学模型为：s.t.原料供应限制含量要求条件用单纯形法求得：即每月生产甲糖果 kg，乙糖果 kg，不生产丙糖果，可获得最大利润为5450元。

（二）、投资项目组合问题例：兴安公司有一笔例：兴安公司有一笔3030万元的资金，考虑今后三年内用于下列万元的资金，考虑今后三年内用于下列项目的投资：项目的投资：1 1、三年内每年年初均可投资，每年获利为投资额的、三年内每年年初均可投资，每年获利为投资额的20%20%，其本，其本利可一起用于下一年投资；利可一起用于下一年投资；2 2、只允许第一年初投入，于第二年末收回，本利合计为投资额、只允许第一年初投入，于第二年末收回，本利合计为投资额的的150%,150%,但此类投资限额不超过但此类投资限额不超过1515万元；万元；3 3、允许于第二年初投入，于第三年末收回，本利合计为投资额、允许于第二年初投入，于第三年末收回，本利合计为投资额的的160%160%，但限额投资，但限额投资2020万元；万元；4 4、允许于第三年初投入，年末收回，可获利、允许于第三年初投入，年末收回，可获利40%40%，但限额为，但限额为1010万元万元. .试为该公司确立一个使第三年末本利和最大的投资组合方案，试为该公司确立一个使第三年末本利和最大的投资组合方案，请建立这个问题的线性规划模型请建立这个问题的线性规划模型。

解：用xij表示第i年初投放到第j个项目的资金数，则建立如下线性规划模型：1234一√√二√√三√√第第i年初年初投入第投入第j个项目个项目1234一一166666.7133333.3二二0200000三三100000100000 第三年末本利和第三年末本利和=580000用单纯形法求得：综上投资组合方案如下：综上投资组合方案如下： ( (三）、人力资源分配问题三）、人力资源分配问题例例 某昼夜服务的公交线路每天各时间段内所需某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:00————10:0060210:00————14:0070314:00————18:0060418:00————22:0050522:00————2:002062:00————6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?解：设xi表示第i班次时开始上班的司机和乘务人员人数。

此问题最优解：x1＝50， x2＝20， x3＝50， x4＝0， x5＝20， x6＝10，一共需要司机和乘务员150人（四）、套裁下料问题（四）、套裁下料问题例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根问如何才能根问如何才能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案其次要求这些方案的总体能裁下所有各种规格个下料方案其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用种下料方案以供套裁用ⅠⅡⅢⅣ2.5m32101.3m0246料头料头0.50.40.30.2设按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：Lingo软件LINGO软件是美国的LINDO系统公司（Lindo System Inc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.  LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等. LINGO的语法规定：的语法规定： （（1）求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=…或或MIN=…来表示；来表示； （（2）每个语句必须以分号）每个语句必须以分号“；；”结束，每行可以有许多语结束，每行可以有许多语句，语句可以跨行；句，语句可以跨行； （（（（3）变量名称必须以字母（）变量名称必须以字母（A~Z）开头，由字母、数字）开头，由字母、数字（（0~9）和下划线所组成，长度不超过）和下划线所组成，长度不超过32个字符，不区分个字符，不区分大小写；大小写； （（4）可以给语句加上标号，例如）可以给语句加上标号，例如MAX=200*X1+300*X2；； （（5）以惊叹号）以惊叹号“！！”开头，以分号开头，以分号“；；”结束的语句是注结束的语句是注释语句；释语句；（（6）如果对变量的取值范围没有作特殊说明，则默认所有）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；决策变量都非负； （（7））LINGO模型以语句模型以语句“MODEL：：”开头，以开头，以“END”结束，对于比较简单的模型，这两个语句可以省略结束，对于比较简单的模型，这两个语句可以省略在LINGO中的输入如下：MAX = 5*x1 + 8*X2;X1 + x2 < 6;5*x1 +9*X2 <= 45; !说明：一个约束分成两行写也没有关系;END例例用鼠标点击菜单中的求解命令用鼠标点击菜单中的求解命令（（SOLVE）就可得到解答，结果）就可得到解答，结果窗口显示如下：窗口显示如下：Global optimal solution found.Objective value: 41.25000Total solver iterations: 2Variable Value Reduced CostX1 2.250000 0.000000X2 3.750000 0.000000Row Slack or Surplus Dual Price1 41.25000 1.0000002 0.000000 1.2500003 0.000000 0.7500000Global optimal solution found”表示找到了全局表示找到了全局最优解。

最优解Objective value”表示最优目标值（表示最优目标值（41.25000））.“Total solver iterations”表示算法的迭代次数表示算法的迭代次数以下的以下的“Value”给出最优解中各变量给出最优解中各变量(“Variable”)的值的值: X1=2.250000, X2=3.750000.Reduced Cost”的含义是的含义是 ( 对对max型问题型问题)：： 基变量的基变量的Reduced Cost值为值为0；对于非基变；对于非基变量量, 相应的相应的 Reduced Cost值表示当该非基变值表示当该非基变量增加一个单位时（其他非基变量保持不变）量增加一个单位时（其他非基变量保持不变）目标函数减少的量本例中两个变量都是基目标函数减少的量本例中两个变量都是基变量，此值均为变量，此值均为0Row Slack or Surplus Dual Price1 41.25000 1.0000002 0.000000 1.2500003 0.000000 0.7500000Slack or Surplus” 给出对应约束给出对应约束(“Row”)的松驰（或剩余）变量的值，表示的松驰（或剩余）变量的值，表示约束是否起作用约束约束是否起作用约束: 第第2、、3行松驰变量均为行松驰变量均为0, 说明对于最优解而言，两个约说明对于最优解而言，两个约束（第束（第2、、3行）均是起作用约束（取等号）。

注意：行）均是起作用约束（取等号）注意：LINGO中将目标函数自中将目标函数自动看作第动看作第1行，从第行，从第2行开始才是真正的约束行行开始才是真正的约束行.“Dual Price” 给出约束的影子给出约束的影子价格（也称为对偶价格）的值价格（也称为对偶价格）的值: 第第2、、3行（约束）对应的影子价格分别为行（约束）对应的影子价格分别为 1.250000，，0.750000。