运筹学 第五章--线性目标规划

第五章线性规划在管理中的应用某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。

管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。

可用的机器设备是限制新产品产量的主要因素，具体数据如下表：司的利润最大化。

1、判别问题的线性规划数学模型类型。

2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。

3、建立该问题的线性规划数学模型。

4、用线性规划求解模型进行求解。

5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。

6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。

解：1、本问题是资源分配型的线性规划数学模型。

2、该问题的决策目标是公司总的利润最大化，总利润为：+ +决策的限制条件：8x1+ 4x2+ 6x3≤500 铣床限制条件4x1+ 3x2≤350 车床限制条件3x1+ x3≤150 磨床限制条件即总绩效测试（目标函数）为：max z= + +3、本问题的线性规划数学模型max z= + +S．T．8x1+ 4x2+ 6x3≤5004x1+ 3x2≤3503x1+ x3≤150x1≥0、x2≥0、x3≥04、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。

5、灵敏度分析目标函数最优值为: 30变量最优解相差值x1 50 0x2 25 0x3 0 .083约束松弛/剩余变量对偶价格1 0 .052 75 03 0 .033目标函数系数范围:变量下限当前值上限x1 .4 .5 无上限x2 .1 .2 .25x3 无下限.25 .333常数项数范围:约束下限当前值上限1 400 500 6002 275 350 无上限3 150（1）最优生产方案：新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。

问题一：建立一个资源利用的规划模型，需加入时间资源、资金资源。

1、问题的提出1.1基本情况某公司现在新购一生产线，生产电脑配件B1、B2、B3。

已知生产单位产品的利润与所需的劳动力时间、设备台时及单位产品的资金投入，公司的资金拥有量和工作时间拥有量如表1-1所示：表1T项目B1配件种类资源限制B2B3资金（百元）412200劳动力/工时643360设备台时（小323210时）产品利润（元/754件）1.2提出问题1、假设每种配件的市场都是供不应求，不用考虑市场及原材料的供应问题那么在现有的条件下应该如何分配者三种配件的生产才能获得最大利润。

2、模型的建立2.1确定决策变量因为获得最大利润的核心目标，要确定各种配件的生产数量从而去求得所能获得的最大利润。

因此可以设尤，x ,x来表示B1，B2, B3的产量。

1 2 32.2确定目标函数该问题归结为求效益最大化的问题。

这里所追求的利润s应是最大（简写为max）max S = 7 x + 5 x + 4 x1 2 32.3确定约束条件考虑到资金限制和劳动力总工时以及设备台时的要求，会有一定的约束条件用不等式表示参考表1_1数值有'4x + x + 2x < 200<6x + 4x + 3x < 360I3x + 2x + 3x < 210侦1 2 32.4建立模型综合前述各步及变量非负的条件建立起线性规划模型如下。

求变量气(i = 1,2,3)使得目标函数：max S = 7 x + 5 x + 4 x1 2 3取得最大值，并满足如下的约束条件的要求：4x + x + 2x < 2001 2 36x + 4x + 3 x < 360s.t. < 1 2 3|3x i+ 2x2 + 3x3 < 210I x , x , x > 0v 1 2 33、模型的求解分析上述线性规划模型是非标准的线性规划模型，用常规方法将其变为标准型的线性规划模型，然后利用单纯形法进行求解。

商学院课程实验报告课程名称 运筹学 专业班级 金融工程班 姓 名 指导教师 成 绩2018年 9 月 20日学号：表2 所需营业员统计表星期一二三四五六日需要人数300 300350400480600 5503.建立线性规划模型设x j（j=1，2，…，7）为休息2天后星期一到星期日开始上班的营业员数量，则这个问题的线性规划问题模型为minZ=x1+x2+x3+x4+x5+x6+x7{x1+x4+x5+x6+x7≥300 x1+x2+x5+x6+x7≥300 x1+x2+x3+x6+x7≥350 x1+x2+x3+x4+x7≥400 x1+x2+x3+x4+x5≥480x2+x3+x4+x5+x6≥600x3+x4+x5+x6+x7≥550x≥0,j=1,2,…,7（二）操作步骤1.将WinQSB安装文件复制到本地硬盘，在WinQSB文件夹中双击setup.exe。

图1 WinQSB文件夹2.指定安装软件的目标目录，安装过程中输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中，熟悉软件子菜单内容和功能，掌握操作命令。

图2 目标目录3.启动线性规划和整数规划程序。

点击开始→程序→WinQSB→Linear and Lnteger Programming，屏幕显示如图3所示的线性规划和整数规划界面。

图3 线性规划4.建立新问题或打开磁盘中已有文件。

按图3所示操作建立或打开一个LP问题，或点击File→New Problem建立新问题。

点击File→Load Problem打开磁盘中的数据文件，点击File→New Problem，出现图4所示的问题选项输入界面。

图4 建立新问题5.输入数据。

在选择数据输入格式时，选择Spreadsheet Matrix Form则以电子表格形式输入变量系统矩阵和右端常数矩阵，是固定格式，如图5所示。

选择Normal Model Form则以自由格式输入标准模型。

第五章 目标规划一、建立下列问题的数学模型1、P164, 5.8 某种牌号的酒由三种等级的酒兑制而成。

已知各种等级的酒每天供应量和单位成本如下：等级I ：供应量1500单位/天，成本6元/单位；等级Ⅱ：供应量2000单位/天，成本4.5元/单位； 等级Ⅲ：供应量1000单位/天，成本3元/单位。

该种牌号的酒有三种商标（红、黄、蓝）各种商标酒的混合比及售价如表所示。

确定经营目标：P1：兑制要求配比必须严格满足；P2：企业获取尽可能多的利润； P3：红色商标酒产量每天不低于2000单位。

试对此问题建立相应的目标规划模型。

解：设红黄蓝分别为1、2、3号酒，ij x 表示i 号酒中j 原料的用量。

则依题意建立如下模型：-+-+-=33222)(min d P d d P Z.3,2,3,2,1,,0,,020000)(3)(5.4)(6)(8.4)(0.5)(5.5100020001500)%(10)%(50)%(20)%(70)%(50)%(103313121122332313322212312111333231232221131211332313322212312111333231313332313323222121232221231312111113121113==≥≥=+-++=+-++-++-++-++++++++≤++≤++≤++++≥++≤++≥++≤++≥++≤-+-+-+k j i d d x d d x x x d d x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x k k ij2、P164, 5.9 某公司从三个产地1A ，2A ，3A 将产品运往四个销地1B ，2B ，3B ，4B .各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。

第五章 目标规划§5.1重点、难点提要一、目标规划的基本概念与模型特征 （1）目标规划的基本概念。

当人们在实践中遇到一些矛盾的目标，由于资源稀缺和其它原因，这些目标可能无法同时达到，可以把任何起作用的约束都称为“目标”。

无论它们是否达到，总的目的是要给出一个最优的结果，使之尽可能接近制定的目标。

目标规划是处理多目标的一种重要方法，人们把目标按重要性分成不同的优先等级，并对同一个优先等级中的不同目标赋权，使其在许多领域都有广泛应用。

在目标规划中至少有两个不同的目标；有两类变量：决策变量和偏差变量；两类约束：资源约束（也称硬约束）和目标约束（也称软约束）。

（2）模型特征。

目标规划的一般模型：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=≥==-+=≤⎪⎭⎫ ⎝⎛+=+-=+-===++--∑∑∑∑.,,2,1;0,;,,2,10,,2,1,,2,1..)(min 1111K k d d n j x K k g d d x c m i b x a t s d d P Z k k j n j k k k j kj i nj j ij Lr K k k rk k rk r ωω 其中r P 为目标优先因子，+-rk rk ωω,为目标权系数，+-k k d d ,为偏差变量。

1）正、负偏差变量,i i d d +-。

正偏差变量i d +表示决策值超过目标值的部分；负偏差变量i d -表示决策值未达到目标值的部分。

因为决策值不可能既超过目标值同时又未达到目标值，所以有0i i d d +-⨯=。

2）硬约束和软约束。

硬约束是指必须严格满足的等式约束和不等式约束；软约束是目标规划特有的。

我们可以把约束右端项看成是要努力追求的目标值，但允许发生正、负偏差，通过在约束中加入正、负偏差变量来表示努力的结果与目标的差距，于是称它们为目标约束。

3）优先因子与权系数。

一个规划问题通常有若干个目标，但决策者在要求达到这些目标时，是有主次或缓急之分的。

5.1 规划论基础规划论是运筹学中应用最为广泛的一个分支，本小节重点介绍在军事通信网分析和规划中常用的两类模型——线性规划和目标规划。

5.1.1 线性规划1. 问题和模型线性规划问题主要有以下2种：一是如何有效利用现有的人力、物力完成更多的任务；二是在预定的任务目标下，如何耗用最少的人力、物力去实现目标。

这些规划问题的数学模型都是由3个要素组成：一是变量，或称决策变量，是需要确定的未知量，用来表明规划中的用数量表示的方案；二是目标函数，它是决策变量的线性函数，按优化目标在该函数前加上max 或min ；三是约束条件，它是含决策变量的线性等式或不等式。

下面，以一个具体的例子来说明问题。

例5.1 某通信连计划用两种通信设备A 和B 进行通信联络，建网方式有甲、乙两种，有关数据见表5.1。

问：两种方式的组网数各为多少时，能在规定的条件下，使得提供的话路总数z 达到最大？解： 设12x x ，分别为甲、乙两种方式的组网数，则由已知条件，容易得到该问题的线性规划模型为：目标函数：12max 1815z x x =+约束条件：12121232422200x x x x x x +≤⎧⎪+≤⎨⎪≥⎩，一般地，规定线性规划问题的标准形式如下：1max nj j j z c x ==∑..s t 1(1,2,,)0(1,2,,)nij j i j j a x b i m x j n ∙∙∙∙∙∙=⎧==⎪⎨⎪≥=⎩∑ 其中，{}(1,2,,)j x j n ∙∙∙=是决策变量，1max nj jj z c x==∑为目标函数，1nij ji j a xb ==∑，1,2,,i m ∙∙∙=，0(1,2,,)j x j n ∙∙∙≥=为约束条件，..s t （subject to 的缩写）为约束于。

约束条件右端的常数项i b 全为非负。

对于非标准形式的线性规划问题可以通过引入松弛变量等转化为标准形式。

所谓松弛变量，是指在化为标准形式时，使约束不等式变为等式时所加入的变量。

运筹学中关于规划问题的常用解决方法运筹学是一门研究如何在有限资源下做出最优决策的学科。

在运筹学中，规划问题是一类常见的问题，它涉及到如何合理分配资源以达到特定的目标。

本文将介绍运筹学中关于规划问题的常用解决方法。

首先，线性规划是解决规划问题最常用的方法之一。

线性规划的目标是在一组线性约束条件下，找到使目标函数最大或最小的变量值。

线性规划的数学模型可以表示为：max/min Z = c₁x₁ + c₂x₂ + ... + cₙxₙsubject to:a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 0其中，Z是要优化的目标函数，c₁, c₂, ..., cₙ是目标函数的系数，a₁₁,a₁₂, ..., aₙₙ是约束条件的系数，b₁, b₂, ..., bₙ是约束条件的常数，x₁, x₂, ..., xₙ是决策变量。

其次，整数规划是线性规划的一种扩展形式，它要求决策变量必须取整数值。

整数规划在实际问题中具有广泛的应用，例如生产调度、物流配送等。

整数规划的求解方法包括分支定界法、割平面法等。

分支定界法通过将整数规划问题划分成一系列子问题，并逐步求解，最终得到最优解。

割平面法则通过添加额外的线性约束条件来逐步逼近最优解。

除了线性规划和整数规划，规划问题还可以通过动态规划方法求解。

动态规划是一种将问题分解成子问题并逐步求解的方法。

它适用于具有重叠子问题和最优子结构性质的问题。

动态规划的核心思想是通过存储中间结果来避免重复计算，从而提高计算效率。

动态规划在求解最短路径、背包问题等方面具有广泛的应用。

此外，启发式算法是一类基于经验和直觉的求解方法，它通过不断搜索和优化来寻找问题的近似最优解。

启发式算法常用于求解复杂的规划问题，如旅行商问题、车辆路径问题等。

线性规划与目标规划的异同和作用一、线性规划与目标规划（1）线性规划线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。

一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。

线性规划模型的一般形式如下：在线性规划的数学模型中，方程（1）称为目标函数；（2）称为约束条件。

满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。

决策变量、约束条件、目标函数是线性规划的三要素。

在生产管理和经营活动中经常提出一类问题，即如何合理利用有限的人力、物力、财力等资源，以便达到最好的经济效果。

例． [生产计划安排问题]某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，单位产品的获利，如下表所示：产品Ⅰ产品Ⅱ资源限制设备 1 1 300台时原料A 2 1 400千克原料B 0 1 250千克单位产品获利50元100元问题：计划期内工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？解：设工厂在计划期内应安排生产产品ⅠX1件, 产品ⅡX2件。

所获利润为z元。

由题意得：Max z = 50 x1 + 100 x2x1 + x2 ≤ 300s.t. 2 x1 + x2 ≤ 400x2 ≤ 250x1 , x2 ≥ 0上例有这样的特征：（1）用一组变量表示某个方案，一般这些变量取值是非负的；（2）存在一定的约束条件，可以用线性等式或线性不等式来表示；（3）都有一个要达到的目标，可以用决策变量的线性函数来表示。

（2）目标规划目标规划（Goal programming）目标规划是线性规划的一种特殊应用，能够处理单个主目标与多个目标并存，以及多个主目标与多个次目标并存的问题。

目标规划的模型分为以下两大类： 1.多目标并列模型。

2.优先顺序模型。

目标规划在企业人力资源需求预测中的应用企业人力资源需求预测是人力资源管理是的一项重要工作，它可以帮助企业明确未来人力需求趋势，做好人才储备工作；同时也可以帮助企业合理预测未来各部门、各类职位人员的需求情况，做好企业的定岗定编工作。

运筹学：应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

第一章、线性规划的图解法1.基本概念线性规划：是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。

线性规划的三要素：变量或决策变量、目标函数、约束条件。

目标函数：是变量的线性函数。

约束条件：变量的线性等式或不等式。

可行解：满足所有约束条件的解称为该线性规划的可行解。

可行域：可行解的集合称为可行域。

最优解：使得目标函数值最大的可行解称为该线性规划的最优解。

唯一最优解、无穷最优解、无界解（可行域无界）或无可行解（可行域为空域）。

凸集：要求集合中任意两点的连线段落在这个集合中。

等值线：目标函数z，对于z的某一取值所得的直线上的每一点都具有相同的目标函数值，故称之为等值线。

松弛变量：对于“≤”约束条件，可增加一些代表没使用的资源或能力的变量，称之为松弛变量。

剩余变量：对于“≥”约束条件，可增加一些代表最低限约束的超过量的变量，称之为剩余变量。

2.线性规划的标准形式约束条件为等式（=）约束条件的常数项非负（b j≥0）决策变量非负（x j≥0）3.灵敏度分析：是在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响。

4.目标函数中的系数c i的灵敏度分析目标函数的斜率在形成最优解顶点的两条直线的斜率之间变化时，最优解不变。

5.约束条件中常数项b i的灵敏度分析对偶价格：约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。

当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格为零。

第二章、线性规划问题在工商管理中的应用1.人力资源分配问题（P41）设x i为第i班次开始上班的人数。

2.生产计划问题（P44）3.套材下料问题（P48）下料方案表（P48）设x i为按各下料方式下料的原材料数量。

4.配料问题（P49）设x ij为第i种产品需要第j种原料的量。

运筹学中的线性规划和整数规划运筹学是一门涉及决策分析、优化、模型构建和仿真等知识领域的学科，应用广泛，如供应链管理、交通规划、制造业生产、金融投资等方面。

其中，线性规划和整数规划是运筹学中最为基础和重要的优化技术，被广泛应用于各个领域。

一、线性规划线性规划是一种在一组线性约束条件下，求解线性目标函数极值问题的数学方法。

在生产、运输、选址等问题中，线性规划都有着重要的应用。

其数学模型可以表示为：$\max c^Tx$$s.t. Ax \leq b,x\geq 0$其中$c$为目标函数的向量，$x$为决策变量向量，$A$为约束矩阵，$b$为约束向量，$c^Tx$表示目标函数的值，$\leq$表示小于等于。

如果目标函数和约束都是线性的，则可以通过线性规划的求解方法来确定决策变量的最优值。

线性规划的求解方法一般分为单纯形法和内点法两种方法。

单纯性法是线性规划中最为常用的方法，通过对角线交替调整，逐步从可行解中寻找最优解，收敛速度较快，但是存在不稳定的情况。

内点法是近年来发展起来的用于求解大规模线性规划问题的数值方法，其核心思想是迭代求解一系列线性方程组，每次保持解在可行域内部，直到找到最优解为止。

这种方法对大规模问题求解能力强，使用较多。

二、整数规划整数规划是线性规划的升级版，它要求决策变量必须取整数值。

整数规划在很多实际问题中都有着重要的应用，比如很多生产过程中需要将生产数量取整数，物流路径问题需要选取整数条路径等。

与线性规划不同的是，整数规划是NP难问题，没有一种有效的算法能够完全解决所有的整数规划问题。

因此，通常需要采用分支定界、割平面等方法来求解。

分支定界是一种常用的整数规划求解方法。

它通过将整数规划问题分为多个子问题，依次求解这些子问题并优化当前最优解，以逐步逼近最优解。

割平面法则是在分支定界方法的基础上加入约束条件，使得求解过程更加严格化，最终得到更好的结果。

总的来说，运筹学中线性规划和整数规划是不可或缺的优化工具，我们可以通过理论和实践加深对它们的理解。