Pyth基础及其求解 4

实用运筹学

－－运用Python建模和求解第8章线性目标规划LinearGoalProgramming本章内容要点目标规划的基本概念和数学模型优先目标规划加权目标规划本章主要内容框架图目标规划的提出线性规划的特征是在满足一组约束的条件下，优化一个单一目标（如总利润最大或总成本最小）。而在现实生活中最优只是相对的，或者说没有绝对意义上的最优，只有相对意义上的满意。1978年诺贝尔经济学奖获得者西蒙（H.A.Simon）教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”的概念和“最大化”的行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究。8.1目标规划的基本概念和数学模型对于第1章的例1-1，现在工厂领导要考虑市场等一系列其他因素，提出如下三个目标：目标1：根据市场信息，窗的销量有下降的趋势，故希望窗的产量不超过门的产量的2倍；(希望≤)目标2：车间3另有新的生产任务,因此希望车间3节省4个工时用于新的生产任务;(希望＝)目标3：应尽可能达到并超过计划的每周总利润3000元。（希望≥）例8-1

在工厂三个车间的工时不能超计划使用的前提下，考虑上述三个目标（优先顺序为目标1、目标2和目标3），试制订满意的生产计划。8.1目标规划的基本概念和数学模型【解】引入正偏差变量和负偏差变量目标约束1：目标约束2：目标约束3：优先目标规划的目标函数为：8.1目标规划的基本概念和数学模型目标规划的基本思想是化多目标为单一目标，下面引入与建立目标规划数学模型有关的概念。1．决策变量和偏差变量2．绝对约束和目标约束3．优先因子（优先级）与权系数4．目标规划的目标函数是由各目标约束的正、负偏差变量和赋予的相应的优先因子及权系数组成的。决策者的愿望是尽可能缩小与目标值的偏差，因此目标函数总是最小化。8.1目标规划的基本概念和数学模型对于例8-1，分别赋予三个目标优先因子P1，P2，P3，则例8-1的优先目标规划数学模型为目标约束偏差变量8.1目标规划的基本概念和数学模型目标规划的一般数学模型为目标约束偏差变量8.2优先目标规划在多目标决策问题中，决策者往往根据自己对目标的重视程度，赋予每个目标一定的优先级，从而将所有目标排序优先目标规划按照目标排序，得到一个满意解。假如所有目标都得到满足，满意解就是最优解。

8.2.1优先目标规划的Python代码对于例8-1，三个目标的优先级为目标1（P1）、目标2（P2）、目标3（P3）。利用Python求解例8-1利用pulp库求解代码框8-1例8-1.ipynb满意解：门的每周产量x1=2.0窗的每周产量x2=4.0每周总利润：2600.0偏差变量：d1_plus=0.0 d1_minus=0.0d2_plus=0.0 d2_minus=0.0d3_plus=0.0 d3_minus=400.0最优目标值（总偏差最小）：400.08.2.2优先目标规划的应用举例例8-2提级加薪问题。某公司的员工工资有四级，根据公司的业务发展需要，准备招收部分新员工，并将部分在职员工的工资提升一级。该公司的员工工资（年薪）及提级前后的编制如表8-2所示。其中提级后的编制是计划编制，允许有变化。公司领导在考虑员工的升级调资方案时，遵守以下规定（优先级从高到低）：（1）提级后在职员工的年工资总额不超过900万元；（2）提级后各级的人数不超过编制规定的人数；（3）级别2、3、4的升级人数尽可能达到现有人数的20％，且无越级提升；（4）级别4不足编制的人数可录用新员工，另外，级别1的员工中有1人要退休。该公司领导应如何拟定一个满意的员工升级调资方案。级别1级别2级别3级别4每人工资（万元/年）121086现有人数（人）10204030编制人数（人）102252308.2.2优先目标规划的应用举例【解】设x1，x2，x3，x4分别表示提升到级别1，2，3和录用到级别4的新员工人数（整数），则提级后各级的员工人数分别为三个目标约束分别为（1）提级后在职员工的年工资总额不超过900万元(希望≤)（2）提级后各级的人数不超过编制规定的人数(希望≤)（3）级别2、3、4的升级人数尽可能达到现有人数的20％（希望≥）目标函数8.2.2优先目标规划的应用举例对于例8-2，三个目标的优先级为目标1（P1）、目标2（P2）、目标3（P3）。利用Python求解例8-2利用pulp库求解代码框8-2例8-2.ipynb满意解（提级人数）：提升到级别1的员工人数x1=1提升到级别2的员工人数x2=3提升到级别3的员工人数x3=6录用到级别4新员工人数x4=0提级后人数：级别1的员工人数=10级别2的员工人数=22级别3的员工人数=43级别4的员工人数=24年工资总额：828最优目标值（总偏差最小）：8.08.3加权目标规划在加权目标规划中，各目标没有明确的优先级；所有偏差（含正、负偏差）都有相应的偏离系数（偏离各目标严重程度的罚数权重）；以偏差加权和（所有偏差与其罚数权重乘积的总和）为目标函数，求其最小值。因此，相对于优先目标规划，加权目标规划得到的满意解是全局的。这个满意解其实可以算作最优解，但为了避免与一般线性规划的最优解发生概念上的混淆，仍称之为满意解。8.3加权目标规划加权目标规划的数学模型8.3加权目标规划例8-3

某公司准备投产三种新产品，现在的重点是确定三种新产品的生产计划，但最好能实现管理层的三个目标。目标1：获得较高利润，希望总利润不低于125万元（希望

）。据估算，产品1、产品2、产品3的单位利润分别为12元、9元、15元。目标2：保持现有的40名工人（希望＝）。据推算，每生产1万件产品1、产品2和产品3分别需要5名、3名和4名工人。目标3：投资资金限制，希望总投资额不超过55万元（希望

）。据测算，生产1件产品1、产品2和产品3分别需要投入5元、7元和8元。8.3加权目标规划例8-3（续）但是，公司管理层意识到要同时实现三个目标是不太现实的，因此，他们对三个目标的相对重要性做出了评价。三个目标都很重要，但在重要程度上还是有些细小的差别，其重要性顺序为：目标1、目标2的前半部分（避免工人失业）、目标3、目标2的后半部分（避免增加工人）。另外，他们为每个目标分配了表示偏离目标严重程度的罚数权重，如表8-3所示。试制订满意的投产计划。目标因素偏离目标的罚数权重（偏离系数）1总利润5（低于目标的每万元）2工人4（低于目标的每个人）2（超过目标的每个人）3投资资金3（超过目标的每万元）8.3加权目标规划例8-3的加权目标规划数学模型8.3加权目标规划利用Python求解例8-3加权目标规划利用pulp库求解代码框8-3例8-3加权目标规划.ipynb满意解：产品1的产量x1=8.3333产品2的产量x2=0.0000产品3的产量x3=1.6667三个目标实现值：总利润：125.0000所需工人：48.3333投资资金：55.0000偏差变量：d1_plus=0.0000d1_minus=0.0000d2_plus=8.3333d2_minus=0.0000d3_plus=0.0000d3_minus=0.0000最优目标值（总偏差最小）：16.66678.3加权目标规划可以利用优先目标规划对例8-3重新规划求解，假设目标优先级顺序为目标1、目标2、目标3。利用Python求解例8-3优先目标规划利用pulp库求解代码框8-4例8-3优先目标规划.ipynb满意解：产品1的产量x1=3.7037产品2的产量x2=0.0000产品3的产量x3=5.3704三个目标实现值：总利润：125.0000所需工人：40.0000投资资金：61.4815偏差变量：d1_plus=0.0000d1_minus=0.0000d2_plus=0.0000d2_minus=0.0000d3_plus=6.4815d3_minus=0.0000最优目标值（总偏差最小）：6.48158.3.2加权目标规划的应用举例例8-4

某大学规定，运筹学专业的学生毕业时必须至少学习过2门数学类课程、3门运筹学类课程和2门计算机类课程。这些课程的编号、名称、学分、所属类别和先修课要求如表8-5所示。（1）毕业时学生最少可以学习这些课程中的哪些课程？请写出一般的0-1规划模型并求解。编号课程名称学分所属类别先修课要求1微积分5数学

2线性代数4数学

3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3运筹学；计算机计算机编程7计算机编程2计算机

8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数（2）如果某个学生既希望选修的课程数少，又希望获得的学分多，他可以选修哪些课程？请写出加权目标规划模型并求解。假设两个目标及偏离目标严重性的罚数权重如下：①最多选修6门课程，多选修1门课程罚7个单位；②最少获得26个学分，少修1个学分罚3个单位。8.3.2加权目标规划的应用举例【解】例8-4问题（1）的0-1规划模型和Python代码利用Python求解例8-4问题（1）0-1规划利用pulp库求解代码框8-5例8-4（1）.ipynb最优解（选修课程）：选修微积分x1=1选修线性代数x2=1选修最优化方法x3=1选修计算机模拟x6=1选修计算机编程x7=1选修数学实验 x9=1最优目标值（选修的课程总数最少）：6

选修的课程总学分：218.3.2加权目标规划的应用举例【解】例8-4问题（2）的加权目标规划模型8.3.2加权目标规划的应用举例【解】例8-4问题（2）的Python代码利用Python求解例8-4问题（2）加权目标规划利用pulp库求解代码框8-6例8-4（2）.ipynb满意解（选修课程）： 选修微积分 x1=1

选修线性代数 x2=1

选修最优化方法 x3=1

选修应用统计 x5=1

选修计算机模拟 x6=1

选修计算机编程 x7=1

选修数学实验 x9=1偏差变量：

d1_plus=1d1_minus=0 d2_plus=0d2_minus=1最优目标值（总偏差最小）：10

选修的课程总数：7

选修课