文档介绍：第一章线性规划及单纯形法
线性规划及单纯形法
线性规划问题及数学模型
图解法
单纯形法原理
单纯形法计算步骤
单纯形法进一步讨论
数据包络分析
其他应用例子
§1线性规划问题
问题的提出
线性规划问题的数学模型
线性规划概念和模型
问题的提出
问题的提出
生产和经营管理中经常提出如何合理安排,使用人力、物力等各种资源得到充分利用,获得最大效益,这就是规划问题。
规划问题主要有两类:
一、给定了人力、物力资源,研究如何合理地利用这些资源;
二、研究如何统筹安排,尽量以最少的人力、物力资源来完成一定的任务。
实际上,这两类问题是一个问题的两个方面,都是寻求整个问题的某个整体指标的最优化问题。
问题的提出
例1 美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A,B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况,如表1-1所示。问该公司应制造两种家电各多少件,使获取的利润为最大。
表1-1
数学模型
例1中先用变量x1和x2分别表示美佳公司制造家电Ⅰ和Ⅱ的数量。这时该公司可获取的利润为(2x1+x2)元,令z=2x1+x2,因问题中要求获取的利润为最大,即max z。
z是该公司能获取的利润的目标值,它是变量x1,x2的函数,称为目标函数。
x1,x2的取值受到设备A、B和调试工序能力的限制,用于描述限制条件的数学表达式称为约束条件。
由此例1的数学模型可表为:
数学模型
()
目标函数
约束条件
()
()
()
max: maximize的缩写, “最大化”,
. subject to的缩写, “受限制于……”
问题的提出
例2 捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表1-3。租借仓库的合同每月初都可办理,每份合同具体规定租用面积和期限。因此该厂可根据需要,在任何一个月初办理租借合同。每次办理时可签一份合同,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小。
表1-2
单位:100m2
表1-3
单位:元/100m2
数学模型
例2中若用变量xij表示捷运公司在第i(i=1,…,4)个月初签订的租借期为j(j=1,…,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库,故x24,x33,x34,x42,x43,x44均为零。该公司希望总的租借费用为最小,故有如下数学模型:
目标函数
约束条件 .
min:minimize , “最小化”
数学模型
第一步,选取决策变量。
第二步,建立目标函数。
为了解决上述问题,首先要求把该问题用数学的语言来描述,这个过程叫做建立问题的数学模型。建立数学模型,可以按以下三个步骤进行:
第三步,确定约束方程。