2 线性规划

1 2 线性规划习题答案

1、试述线性规划数学模型的组成部分及其特性

答：线性规划数学模型由决策变量、约束条件和目标函数三个部分组成。

线性规划数学模型特征：

（1） 用一组决策变量表示某一方案，这组决策变量均为非负的连续变量；

（2） 存在一定数量（m）的约束条件，这些约束条件可以用关于决策变量的一组线性等式或者不等式来加以表示；

（3） 有一个可以用决策变量加以表示的目标函数，而该函数是一个线性函数。

2、一家餐厅24小时全天候营业，在各时间段中所需要的服务员数量分别为：

2：00~6：00 3人 6：00~10：00 9人

10：00~14：00 12人 14：00~18：00 5人

18：00~22：00 18人 22：00~ 2：00 4人

设服务员在各时间段的开始时点上上班并连续工作八小时，问该餐厅至少配备多少服务员，才能满足各个时间段对人员的需要。试构造此问题的数学模型。

解：用决策变量1x,2x,3x,4x,5x,6x分别表示2：00~6：00， 6：00~10：00 ，10：00~14：00 ，14：00~18：00，18：00~22：00， 22：00~ 2：00 时间段的服务员人数。

其数学模型可以表述为：123456minZxxxxxx

16122334455612345639125184,,,,,0xxxxxxxxxxxxxxxxxx

3、现要截取2.9米、2.1米和1.5米的元钢各100根，已知原材料的长度是7.4米，问应如何下料，才能使所消耗的原材料最省。试构造此问题的数学模型。

方法一

解：圆钢的截取有不同的方案，用θ表示每种切割方案的剩余材料。其切割方案如下所示：

2.9 2.1 1.5 θ

1' 1 1 1 0.9

西安理工大学实验报告

第 页（共 页）

课 程：_____________________________ 实验日期： 年 月 日

专业班号：____________组别：___________ 交报告日期： 年 月 日

姓 名：____________学号：___________ 报告退发： （订正、重做）

同 组 者：_____________________________ 教师审批签字：

实验报告格式

一、 预习准备：实验目的和要求、实验仪器和设备等；

二、 实验过程：实验步骤和实验数据记录等；

三、实验总结：实验数据处理和实验结果讨论等。

实验一

线性规划

运筹学 成绩

无 2012 3 26

2012 3 28 西安理工大学实验报告用纸 第 页（共 页）

实验一：线性规划

一、预习准备

（一）实验目的：安装WinQSB软件，了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。用WinQSB软件求解线性规划。

（二）内容和要求：安装与启动软件，建立新问题，输入模型，求解模型，结果的简单分析。

（三）操作步骤：

1.将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。

2.指定安装WinQSB软件的目标目录（默认为C:\ WinQSB）。

3. 安装过程需输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中。

4.熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。

5．求解线性规划。启动程序 开始→程序→WinQSB→Linear and Integer Programming 。

两阶段法

孙敏 枣庄学院

考虑线性规划问题

0 s.t.min

xbAxcxZ （1）

符号说明与教材一致，唯一的不同之处是不要求假设矩阵A是行满秩的。

在初始基本可行解未知的情况下，可以采用两阶段法。这种方法的基本思想是：第一阶段在约束中增加人工变量ax，修改目标函数为极小化人工变量的和，即下面的问题（2），然后用普通单纯形法消去人工变量（如果可能的话），即把人工变量都变换成非基变量，求出问题（1）的一个基本可行解。第二阶段就从得到的基本可行解出发，用普通单纯法求解问题（1）。

0,0 s.t.min

aaaTxxbxAxxeW （2）

这样，在极小化目标函数的过程中，由于大M的存在，将迫使人工变量离基。

由于bxxa,0是线性规划（2）一个基本可行解，目标函数在可行域上有下界0，因此问题（2）一定存在最优基本可行解。用单纯形法求解线性规划（2），设得到的最优基本可行解是**axx，此时必有下列三种情形之一。

（a）0*ax。这时问题（1）无可行解。因为如果问题（1）有可行解xˆ，则

0ˆxxxa

是线性规划（2）的可行解。在此点处，问题（2）的目标函数值

***000ˆaaTTxxWxeexW

这与**axx是问题（2）的最优解矛盾。

（b）0*ax且*ax的分量都是非基变量。这时，m个基变量都是问题（1）的变量，又知0***xxxa是问题（2）的基本可行解，因此*x是问题（1）的一个基本可行解。转第二阶

第二章 线性规划的对偶问题

４７ 习题二

2.1 写出下列线性规划问题的对偶问题

(1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4

st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4 ≤5

4x1＋ x2＋ x3≤20 2x1－ x2＋3x3 ＝－4

xj ≥0 （j＝1,2,3） x1 － x3＋ x4≥1

x1，x3≥0，x2，x4无约束

(3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3

st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15

x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20

2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5

x1≥0，x4≤0，x2，，x3 无约束 x1≤0， x2≥0，x3 无约束

2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：

（1）问题的第k个约束条件乘上常数λ（λ≠0）；

（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；

（3）目标函数改变为max z＝λCX（λ≠0）；

（4）模型中全部x1用31'x代换。

2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4

st. x1＋2x2 ＋ x4≥3

3x1＋ x2＋ x3＋ x4≥6

x3 ＋ x4＝2

x1 ＋ x3 ≥2

xj≥0（j＝1,2,3,4）

(1) 写出其对偶问题；