开课学院、实验室： 数学与统计学院 实验时间 ： 年 月 日
课程 数学实验 名称 指导 教师 龚 劬 实验项目 名 称 成 绩 实验四、线性规划 验证 实验项目类型 演示 综合 设计 其他 √ 实验目的 [1] 学习最优化技术和基本原理，了解最优化问题的分类； [2] 掌握线性规划的建模技巧和求解方法； [3] 学习灵敏度分析问题的思维方法； [4] 熟悉MATLAB软件求解线性规划模型的基本命令； [5] 通过范例学习，熟悉建立线性规划模型的基本要素和求解方法。 通过该实验的学习，使学生掌握最优化技术，认识面对什么样的实际问题，提出假设和建立优化模型，并且使学生学会使用MATLAB软件进行线性规划模型求解的基本命令，并进行灵敏度分析。解决现实生活中的最优化问题是本科生学习阶段中一门重要的课程，因此，本实验对学生的学习尤为重要。 应用实验（或综合实验） 一、实验内容 1．最优化问题的提出，提出不同的假设可以建立不同的最优化模型； 2．建立线性规划模型的基本要素和步骤； 3．使用MATLAB命令对线性规划模型进行计算与灵敏度分析； 4．利用优化数值解与图形解对最优化特征作定性与定量分析； 二、问题分析 问题1： 两种面包产品的产量配比问题 田园食品公司生产的面包很出名。他们生产两种面包：一种是叫“唐师”的白面包，另一种是叫“宋赐”的大黑面包。每个唐师面包的利润是0.05元，宋赐面包是0.08元。两种面包的月生产成本是固定的4000元，不管生产多少面包。 该公司的面包生产厂分为两个部：分别是烤制和调配。 烤制部有10座大烤炉，每座烤炉的容量是每天出140台，每台可容纳10个唐师面包或5个更大的宋赐面包。可以在一台上同时放两种面包，只需注意宋赐面包所占的空间是唐师面包的两倍。 调配部每天可以调配最多8000个唐师面包和5000个宋赐面包。有两个自动调配器分别用于两种面包的调配而不至于发生冲突。 田园公司决定找出这两种面包产品的最佳产量配比，即确定两种面包的日产量，使得在公司面包厂的现有生产条件下利润最高。 问题分析：田园公司生产两种面包，设为A和B，由于受一些约束条件的限制，所以需要通过优化分析找出最优的生产方案，目标函数便是使公司的收益达到最大。目前已知A、B面包的单位收益pa和pb。又可以由题目找出约束条件，假设两个决策变量为x1,x2，分为为A类和B类面包的产量。于是可以通过优化模型求解出最佳方案。 模型假设： 1、 面包的生产过程除题中所给限制以外，不存在其他限制，诸如天气、设备检修之类的问题。 2、 假设面包生产设备和人员一直能正常工作。公司的收益大小只取决于决策。 3、 生产出来的面包都能顺利的销售出去，从而获得收益。 符号说明： x1,x2——分别表示“宋赐”面包和“唐师”面包的生产量，即决策变量 WP（x1,x2）——表示最终的收益，即目标函数。 三、数学模型的建立与求解(一般应包括模型、求解步骤或思路，程序放在后面的附录中) 先确定约束条件S.T.: 0?x1?50000?x2?8000 ——调配部产能限制 2*x1?x2?14000 ——烤制部产能限制 目标函数： WP（x1,x2）= 0.05*x2?0.08x1?4000 ——最终收益 于是在MATLAB中可以编写程序如下： C=[0.05 0.08]; V=[0 0]; L=[5000 8000]; A=[2 1]; B=[14000]; [x fa]=linprog(C,[],[],A,B,V,L) 可以得到如下结果： x = 5000 4000 fa = 570 即“宋赐”面包和“唐师”面包各生产5000个/天和4000个/天，可以得到最大的收益为：570元/天。 问题2：航空公司的机舱设计及机票销售 在五个城市A、B、C、D、E之间，有唯一一家航空公司提供四个航班服务，这四个航班的“出发地—目的地”分别为AC、BC、CD、CE，可搭载旅客的最大数量分别为100人、115人、120人、110人，机票的价格分头等舱和经济舱两类。经过市场调查，公司销售部得到了每天旅客的相关信息，见下表。该公司应该在每条航线上分别分配多少张头等舱和经济舱的机票？ 出发地-目的地 AC AD(经C转机) AE(经C转机) BC BD(经C转机) BE(经C转机) CD CE 对于题中航班航段信息作出下图： 110 D 120 C 图 1 航段与运量示意图 头等舱 需求（人） 31 22 10 25 20 8 34 13 价格（元） 190 244 261 170 260 280 140 186 52 41 60 33 31 41 59 15 经济舱 需求（人） 价格（元） 90 193 199 110 150 165 80 103 A E 100 B 115 问题分析： 该问题是一个线性规划问题，目标是是该家航空公司在四个航线上的总收益达到最大。决策变量是每条航线上头等舱和经济舱的数量设置。限制条件是每天航线上运力有限，已在图中标示出。于是可以建立目标函数（收益函数）、约束条件，继而求解出最优决策。在CE航线上没有转机的情况出现，所以认为部分舱位应该是优先提供给单纯走CE航线即非转机乘客，因为单个乘客分配到该航线的单程营收大于转机的营收。这样营收可以最大化。 模型假设： 1、 四条航线都只有唯一一家航空公司提供服务，即不存在竞争对手。价格是固定的。 2、 每天的乘客数按题中给出是基本固定的，即使有变化都在很小的范围内，不影响最后的决策。 3、 不考虑服务质量等因素，单纯追求收入最大化。 4、 机票营收入的最大化即代表利润收入的最大化。 5、 所以舱位都将会被出售，已达到营收的最大化。即不预留空座位。 符号说明： 1、S1,S2——表示头等舱和经济舱 2、S—number—航段标号—（转机）T—转机目的地——表示具体的某路线的乘客数量（例：S1ACTD:代表AD经C转机该路线的乘客数量） 3、WP——表示目标函数 模型建立与求解： 经过分析，可以知道： S1CE?13,S2CE?15，这是利益要求最大化的必然结果，可以从单航线增加的收入中推理出，优先给出。 于是目标函数可以认为是： WP?190*S1AC?90*S2AC?244*S1ACTD?193*S2ACTD?261*S1ACTE?199*S2ACTE?170*S1BC?110*S2BC260*S1BCTD?150*S2BCTD?280*S1BCTE?165*S2BCTE+140*x13+80*x14+186*x15+103*x16约束条件ST为： S1AC?S2AC?S1ACTD?S2ACTD?S1ACTE?S2ACTE?100S1BC?S2BC?S1BCTD?S2BCTD?S1BCTE?S2BCTE?115S1ACTD?S2ACTD?S1BCTD?S2BCTD?S1CD?S2CD?120S1ACTE?S2ACTE?S1BCTE?S2BCTE?S1CE?S2CE?110并且每种航段的人数不超过需求人数 使用Lingo软件求解该线性规划问题，可以得到如下结果： Global optimal solution found. Objective value: 53605.00 Total solver iterations: 11 Variable Value Reduced Cost X1 31.00000 0.000000 X2 0.000000 23.00000 X3 22.00000 0.000000 X4 2.000000 0.000000 X5 10.00000 0.000000 X6 35.00000 0.000000 X7 25.00000 0.000000 X8 33.00000 0.000000 X9 20.00000 0.000000 X10 0.000000 9.000000 X11 8.000000 0.000000 X12 29.00000 0.000000 X13 34.00000 0.000000 X14 42.00000 0.000000 X15 13.00000 0.000000 X16 15.00000 0.000000 可以得到最终每种航线的人数分配如下表： AC AD(C) AE(C) BC BD(C) BE(C) CD CE S1 31 22 10 25 20 8 34 13 S2 0 2 35 33 0 29 42 15 继而得到每航段的头等舱和经济舱的分配如下表：