运筹与优化课内实验 检测
实验一：线性规划问题与对偶问题的建模与求解
一． 线性规划：
满足以下三个条件的称之为线性规划问题：
（1）决策变量的取值是连续的，既可以为整数，也可以喂分数、小数或实数。
（2）目标函数是决策变量的线性函数。
（3）结束条件是含决策变量的线性等式或者不等式。
二．线性规划模型的形式：
2.1．一般形式
()()1
1
max min ..
,1,2
,001,2
,n
i i
i n
ij
j
i
j j j z c x s t a x b
i m x x j n
===≤≥==≥≤=∑∑（）
(2.1)
矩阵形式
()()max min ..
,0T z c X s t AX b X =≤≥=≥≤（X 0)
(2.2) 其中()T
n x ,x ,x X 21=为决策向量，()T
n c c c c ,,21=为目标函数的系数向量，
()T
m b ,b ,b b 21=为常数向量，()n m ij a A ⨯=为系数矩阵。
2.2．标准形式
所谓线性规划问题的标准形式，是指目标函数要求min 所有约束条件都是等式约束，且所有决策定量都是非负的，即
1211221111221121122222112212min ()..0n n n n n n n m m mn n m
n f x x x c x c x c x a x a x a x b a x a x a x b s t a x a x a x b x x x =++++++=⎧⎪
+++=⎪⎪⎨
⎪+++=⎪⎪≥⎩，，，，
，
，，
，
，，，
三．原问题与对偶问题的表达形式和关系
在线性规划的对偶理论中，把如下线性规划形式称为原问题的标准形式
11221111221121122222112212min ()..0n n n n n n m m mn n m
n f X c x c x c x a x a x a x b a x a x a x b s t a x a x a x b x x x =++
++++≥⎧⎪
+++≥⎪⎪⎨
⎪+++≥⎪⎪≥⎩，
，
，，
，
，，． 而把如下线性规划形式称为对偶问题的标准形式
11221111221121122222112212max ()..0n n m m m m n n mn m n
m g Y b y b y b y a y a y a y c a y a y a y c s t a y a y a y c y y y =++
++++≥⎧⎪
+++≥⎪⎪⎨
⎪+++≥⎪⎪≥⎩，
，，，
，
，，． 若用矩阵形式表示，则原问题和对偶问题分别可写成如下形式：
原问题
min ()..0f X CX AX b s t X =≥⎧⎨
≥⎩，，．
对偶问题
'max (),,..0.
g Y Y b YA C s t Y =≤⎧⎨
≥⎩ 原问题与对偶问题的关系见表
四．实际问题与lingo 求解计算
例4.1.1（原问题）：设某种植物每天至少需要2g 水，4g 矿物质，5g 维生素。已知三种肥料A ，B ，C ；其中A 种肥料含有1g 水，3g 维生素；B 种肥料含有3g 水，2g 矿物质，1g 维生素；C 种肥料含有1g 水，2g 矿物质，2g 维生素。其中A 种肥料6元每克，B 种肥料4元每克，C 种肥料7元每克，要求确定既要满足植物生长的营养需求，又要费用最省的选用肥料的方案。 该问题的模型为:
min z=6*x1+4*x2+7*x3;
s.t.⎪⎪⎪⎪
⎩⎪⎪⎪⎪⎨⎧>=>=>=>=++>=++>=+0;
x30;x20;x15;
x3*2x2*2x14;x3x2*2x1*32;
x3*3x1
用lingo 求解代码如下： model :
min =6*x1+4*x2+7*x3; x1+3*x3>=2; 3*x1+2*x2+x3>=4;
x1+2*x2+2*x3>=5;
x1>=0;
x2>=0;
x3>=0;
end
求解得：
Global optimal solution found at iteration: 0
Objective value: 12.00000
Variable Value Reduced Cost
X1 0.000000 3.000000
X2 1.833333 0.000000
X3 0.6666667 0.000000
Row Slack or Surplus Dual Price
1 12.00000 -1.000000
2 0.000000 -1.000000
3 0.3333333 0.000000
4 0.000000 -2.000000
5 0.000000 0.000000
6 1.833333 0.000000
7 0.6666667 0.000000通过上面结果可以知道，最佳费用为12元，此时，需要A,B,C三种肥料为
