第6讲整数规划、非线性规划模型

MATLAB编程

最优化模型(2)一、一般的线性规划模型 二、整数规划模型三、非线性规划模型

MATLAB编程

运用最优化方法解决最优化问题的一般 方法步骤如下：①前期分析：分析问题，找出要解决的目标，约束条件， 并确立最优化的目标。②定义变量，建立最优化问题的数学模型，列出目标函 数和约束条件。 ③针对建立的模型，选择合适的求解方法或数学软件。 ④编写程序，利用计算机求解。 ⑤对结果进行分析，讨论诸如：结果的合理性、正确性， 算法的收敛性，模型的适用性和通用性，算法效率与 误差等。

MATLAB编程

练习： 【汽车安排模型】 丰顺汽车运输队有 8 辆载重量为 6t 的 A 型卡车与 6 辆载重量为 10t 的 B 型卡车，有 10 名驾驶员。 此车队承包了每天至少搬运 720t 蔬菜的任务。已 知每辆卡车每天往返的次数为 A 型卡车 16 次，B 型卡车 12 次。每辆卡车每天往返的成本费为 A 型 车 240 元，B 型车 378 元。则每天派出 A 型车与 B 型车各多少辆运输队所花的成本最低。

MATLAB编程

一、 问题前期分析 该问题是要求在满足卡车数量，往返次数，司机数量等限制条 件下完成运输任务所需的最小运输成本。 二、 模型假设 1. 假设卡车不能超载。 2. 假设卡车往返次数不受驾驶速度等其他因素影响。 3. 假设运输成本只与车辆数量有关，与车次无关。 4. 不考虑聘请外面的驾驶员。

MATLAB编程

变量假设： 假设每天派出 x1 辆 A 型车和 x2 辆 B 型车花费成本为 C 元。 一、 模型的分析与建立 目标函数：求运输的总成本最小。 运输总成本为： C 240x1 378x2 受 A 型车数量限制： x1 8 受 B 型车数量限制： x2 6 受司机数量限制： x1 x2 10 要完成每天运输任务： 16 6 x1 12 10 x2 720

MATLAB编程

综上分析，得到该问题的线性规划模型

min C 240x1 378x2 x1 8 x 6 2 s.t. x1 x2 10 96 x 120 x 720 2 1 x1 , x2 0, x1 , x2 Z

MATLAB编程

用YALMIP编程求解程序如下：x=intvar(1,2); C=[240 378]; a=[1 0;0 1;1 1];b=[8 6 10]; f=C*x'; F=set(0<=x<=inf); F=F+set(a*x'<=b')+set(96*x(1)+120*x(2)>=720); solvesdp(F,f) double(f)

double(x)

MATLAB编程

整

数

规

划

最优化问题中的所有变量均为整数时，这类 问题称为整数规划问题。 如果线性规划中的所有变量均为整数时，称 这类问题为线性整数规划问题。 整数规划可分为线性整数规划和非线性整数 规划 ，以及混合整数规划等。 如果决策变量的取值只能为0或1,则这样的 规划问题称为0-1规划。

MATLAB编程

例1

某钢厂两个炼钢炉同时各用一种方法炼钢。

第一种炼法每炉用a小时，第二种用b小时(包

括清炉时间)。假定这两种炼法，每炉出钢都是k公斤，而炼1公斤钢的平均燃

料费第一法为m元，

第二法为n元。若要求在c小时内炼钢公斤数不少于d,试列出燃料费最省的两种方法的分配方案 的数学模型。

MATLAB编程

设用第一种炼法炼钢x1炉，第二种炼钢x2炉

max z k (mx1 nx2 ) ax1 c s.t. bx2 c k ( x1 x2 ) d x1 , x2 0且为整数

MATLAB编程

引例2.资源分配问题：某个中型的百货商场要求售货人员每周工作5 天，连续休息2天，工资200元/周，已知对售货人 员的需求经过统计分析如下表，问如何安排可使 配备销售人员的总费用最少？星期 所需售货员人数 开始休息的人数 一 18 x1 二 15 x2 三 12 x3 四 16 x4 五 19 x5 六 14 x6 日 12 x7

设决策变量如上，可建立如下模型：

MATLAB编程

min

z 200( x1 x2 x3 x4 x5 x6 x7 )

x2 x3 x4 x5 x6 18 x3 x4 x5 x6 x7 15 x4 x5 x6 x7 x1 12 x5 x6 x7 x1 x2 16 s.t. x6 x7 x1 x2 x3 19 x7 x1 x2 x3 x4 14 x1 x2 x3 x4 x5 14 x , x , x , x , x , x , x 0且为整数 1 2 3 4 5 6 7

MATLAB编程

练习： 【蛋糕生产模型】 美好蛋糕店计划在圣诞节当天生产草莓、蓝莓、柠檬三种口味 的蛋糕，各种口味的蛋糕每个需要消耗的面粉和鸡蛋数量以及获得 的相应售价见表 4-5. 若该商店当天只配备了 6000 g 面粉， 2000 g 鸡 蛋，蛋糕店应如何安排生产才能获得最大收益. 草莓 面粉( g / 个 ) 鸡蛋( g / 个 ) 售价(元/个) 20 5 2 蓝莓 30 8 3 柠檬 40 12 4

MATLAB编程

一、模型准备 该问题是在原料数量一定的限制条件下，求商店生产三种口味 蛋糕各多少时，可获得最大收益. 二、模型假设 1.假设在生产过程中没有材料的浪费. 2. 假设生产的面包能全部售出， 且不考虑影响销售价格的因素. 三、变量假设 设商店生产草莓、蓝莓、柠檬三种口味的蛋糕的数量分别为

x1 , x2 , x3 ,获得的总收益为 R 元.

MATLAB编程

三、模型的分析与建立 目标：获得的总收益最大. 目标函数：总收益为 R 2 x1 3x2 4 x3 . 约束条件： 1.受面粉数量的限制： 20x1 30x2 40x3 6000 2.受鸡蛋数量的限制： 5x1 8x2 12x3 2000

MATLAB编程

综上分析，得到该问题的线性规划模型

max R 2x1 3x2 4x3 20x1 30x 2 40x3 6000 5 x 8 x 12x 2000 1 2 3 s.t. x1 , x 2 , x3 0 x1 , x 2 , x3 Z