规划模型(运筹学)论述

1x 6 1x25x1x3x220 x12x22x1x31 00
14
例5：容器的设计问题
某公司专门生产储藏用容器，定货合同要求该公
司制造一种敞口的长方体容器，容积恰好为12立方 米，该容器的底必须为正方形，容器总重量不超过 68公斤。已知用作容器四壁的材料为每平方米10 元， 重3公斤；用作容器底的材料每平方米20元，重2公 斤。试问制造该容器所需的最小费用是多少？
最短线路是 C4B5A6
20
k＝4时： f4 (A 3 ) m d d i4 4 ( (n A A 3 3 ,,B A 4 4 ) ) f f5 5 ( (B A 4 4 ) ) m 2 2 i 5 7 n 7
最短线路是 A3B4B5A6
f4 (B 3 ) m d d i4 4 ( (B B n 3 3 ,,C B 4 4 ) ) f f5 5 ( (C B 4 4 ) ) m 1 2 i 5 9 n 6
加和工（第元jc种／ij零个件）所。需问机在时这和个成生本产分周别期为内t怎ij （样机安时排／各个机）
床的生产任务，才能使得既完成加工任务，又使总的 加工成本最少？
解：在一个生产周期内，假设第i台机床加工第j
种零件的个数为 x ij 。
由于x ij 是零件个数，因此 x ij 必须是非负整数，
11
a 2 x 1 1 a 2 x 2 a 2 n x n ( , ) b 2
a m 1 x 1 a m 2 x 2 a m x n n ( , ) b m
x1,x2, ,xn0
7
例3：生产组织与计划问题
设有m种资源，第i(i=1,2…,m)种资源的现存量
为 b i ，现要生产n种产品，已知生产j(j=1,2…,n)种 产品时，每单位产品需要第i种资源量为 a ij ，而每

实验一线性规划模型一、实验目的掌握数学软件Lingo编程求解线性规划模型。

二、实验内容1 安装并启动Lingo软件，了解Lingo软件子菜单内容及其功能，掌握操作命令。

2 输入模型，求解模型，结果的简单分析，用Lingo软件求解书P47练习1.1。

3 用Lingo软件完成下列问题(1) 写出对偶线性规划；(2) 求原问题和对偶问题的最优解；(3) 分别写出价值系数和右端常数的最大允许变化范围；(4) 目标函数改为C=(5,3,6),同时常数改为b=(120,140,100),求最优解；(5) 增加一个设备约束和一个变量,系数为()=(7,5,4,1,2),求最优解。

4 思考题书P52案例1.2。

三、实验指导参考PDF文档。

四、实验程序和结果（学生填）2.题目1.1（a）输入程序：min=2*x1+3*x2;4*x1+6*x2>=6;4*x1+2*x2>=4;x1>=0;x2>=0;运行Global optimal solution found at iteration: 0Objectivevalue: 3.000000 Variable Value Reduced CostX1 0.7500000 0.000000X2 0.5000000 0.000000Row Slack or Surplus Dual Price1 3.000000 -1.0000002 0.000000 -0.50000003 0.000000 0.0000004 0.7500000 0.0000005 0.5000000 0.000000即x1=0.75,x2=0.5,min=3(b)max=3*x1+2*x2;2*x1+x2<=2;3*x1+4*x2>=12;x1>=0;x2>=0;Variable Value Reduced Cost X1 0.000000 0.7500000E+10 X2 2.000000 0.000000 Row Slack or Surplus Dual Price1 4.000000 1.0000002 0.000000 0.6000000E+103 -4.000000 -0.1500000E+104 0.000000 0.0000005 2.000000 0.000000 无可行解(c)max=x1+x2;6*x1+10*x2<=120;x1>=5;x1<=10;x2>=3;x2<=8;Global optimal solution found at iteration: 0Objectivevalue: 16.00000 Variable Value Reduced CostX1 10.00000 0.000000X2 6.000000 0.000000Row Slack or Surplus Dual Price1 16.00000 1.0000002 0.000000 0.10000003 5.000000 0.0000004 0.000000 0.40000005 3.000000 0.0000006 2.000000 0.000000即下，x1=10,x2=6,max=16(d)max=5*x1+6*x2;2*x1-x2>=2;-2*x1+3*x2<=2;x1>=0;x2>=0;Variable Value Reduced Cost X1 2.000000 0.000000X2 2.000000 0.000000 Row Slack or Surplus Dual Price1 22.00000 1.0000002 0.000000 6.7500003 0.000000 4.2500004 2.000000 0.0000005 2.000000 0.000000 即无界解2.(1)对偶问题为min=100*y1+100*y2+120*y3;2*y1+3*y2+3*y3>=42*y1+y2+y3>=24*y1+6*y2+2*y3>=3y1>=0y2>=0y3>=0（2）求原问题最优解，输入：max=4*x1+2*x2+3*x3;2*x1+2*x2+4*x3<=100;3*x1+x2+6*x3<=100;3*x1+x2+2*x3<=120;x1>=0;x2>=0;x3>=0;Global optimal solution found at iteration: 2Objectivevalue: 150.0000 Variable Value Reduced CostX1 25.00000 0.000000X2 25.00000 0.000000 X3 0.000000 5.000000 Row Slack or Surplus Dual Price1 150.0000 1.0000002 0.000000 0.50000003 0.000000 1.0000004 20.00000 0.0000005 25.00000 0.0000006 25.00000 0.0000007 0.000000 0.000000 即下，x1=25,x2=25,x3=0,max=150求对偶问题最优解，输入min=100*y1+100*y2+120*y3;2*y1+3*y2+3*y3>=4;2*y1+y2+y3>=2;4*y1+6*y2+2*y3>=3;y1>=0;y2>=0;y3>=0;Global optimal solution found at iteration: 0Objectivevalue: 150.0000 Variable Value Reduced CostY1 0.5000000 0.000000Y2 1.000000 0.000000Y3 0.000000 20.00000Row Slack or Surplus Dual Price1 150.0000 -1.0000002 0.000000 -25.000003 0.000000 -25.000004 5.000000 0.0000005 0.5000000 0.0000006 1.000000 0.0000007 0.000000 0.000000 即，y1=0.5,y2=1,y3=0,min=150.(3)即（4）输入max=5*x1+3*x2+6*x3;2*x1+2*x2+4*x3<=120;3*x1+x2+6*x3<=140;3*x1+x2+2*x3<=120;Global optimal solution found at iteration: 2Objectivevalue: 240.0000 Variable Value Reduced CostX1 30.00000 0.000000X2 30.00000 0.000000X3 0.000000 0.000000Row Slack or Surplus Dual Price1 240.0000 1.0000002 0.000000 1.0000003 20.00000 0.0000004 0.000000 1.000000 即，x1=30,x2=30,x3=0,max=240(5)输入max=4*x1+2*x2+3*x3+7*x4;2*x1+2*x2+4*x3+5*x4<=100;3*x1+x2+6*x3+4*x4<=100;3*x1+x2+2*x3+x4<=120;6*x1+5*x2+x3+2*x4<=200;x1>=0;x2>=0;x3>=0;x4>=0;Global optimal solution found at iteration: 0Objectivevalue: 157.1429 Variable Value Reduced CostX1 14.28571 0.000000X2 0.000000 0.2857143X3 0.000000 5.000000X4 14.28571 0.000000Row Slack or Surplus Dual Price1 157.1429 1.0000002 0.000000 0.71428573 0.000000 0.85714294 62.85714 0.0000005 85.71429 0.0000006 14.28571 0.0000007 0.000000 0.0000008 0.000000 0.0000009 14.28571 0.000000 即x1=14.25771,x2=0,x3=0,x4=14.28571,max=157.1429。

第一节目标规划实例与模型
看起来有 点繁～ 有点 ‘烦’… … …★
因此其目标规划的数学模型： minz=p1d1++p2(d2-+d2+)+p3d3s.t 2x1+x2≤11 x1-x2+d1--d1+=0 x1+2x2+d2--d2+=10 8x1+10x2+d3--d3+=56 x1,x2≥0,di-,di+≥0，i=1,2,3
第一节目标规划实例与模型
(5)目标函数—准则函数 目标函数是由各目标约束的正负偏差变量及其相应 的优先级、权因子构成的函数，且对这个函数求极小值， 其中不包含决策变量xi.因为决策者的愿望总是希望尽可能 缩小偏差，使目标尽可能达到理想值，因此目标函数总是 极小化。有三种基本形式：
第一节目标规划实例与模型
第一节目标规划实例与模型
(4)优先级与权因子 多个目标之间有主次缓急之分，凡要求首先达到的目 标，赋于优先级p1,要求第2位达到的目标赋于优先级 p2,…设共有k0个优先级则规定 p1>>p2>>p3……Pk0>0 P1优先级远远高于p2,p3，只有当p1级完成优化后，再考 虑p2,p3。反之p2在优化时不能破坏p1级的优先值，p3级 在优化时不能破坏p1,p2已达到的优值 由于绝对约束是必须满足的约束，因此与绝对约束相 应的目标函数总是放在p1级
第一节目标规划实例与模型
该问题的决策目标是： （1）总利润最大； （2）尽可能少加工； （3）尽可能多销售电扇； （4）生产数量不能超过预销售数量。 （5）绝对目标约束。所谓绝对目标约束就是必须要严格 满足的约束。绝对目标约束是最高优先级，在考虑较低 优先级的目标之前它们必须首先得到满足。

凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个 点X1和X2连线上的所有点都属于K，即“X =αX1+(1-α) X2 ∈ K(0≤a ≤ 1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1， u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X =αX1+(1α) X2 ∈ K(0≤a ≤ 1)”的证明思路如下:
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。