商学与人文部运筹学

2023/4/71.线性规划问题的标准形式特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。一。线性规划问题的数学模型2023/4/72（2）如何化标准形式

目标函数的转换

如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令，可得到上式。即

若存在取值无约束的变量，可令其中：

变量的变换

若存在取值变量≤0

，可令其中：2023/4/73

约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量

常量bi＜0

的变换:约束方程两边乘以（－1）i=1,2,…..,m

i=1,2,…..,m

书上11页例1-81-92023/4/75二。加入人工变量构造初始基：把所有约束方程的右端常数调整为大于等于零。对

约束,引入松弛变量。对约束,引入一剩余变量和一人工变量。对=

约束，引入一人工变量。2023/4/76例题1.17：

maxz=3x1–x2–x3s.t.x1–2x2+x3

（）11 -4x1+x2+2x3

（

）3 -2x1+x3

（=）1

x1,x2,0=+x7

=+x4–

x5+x6=大M法通过引入人工变量构成初始基，从而找到一个初始基可行解；在目标函数中人工变量的系数是任意大正数M的相反数-M；用线性规划的优化机制迫使人工变量出基；如果无法使人工变量出基，原问题无可行解。–Mx6–Mx7x3,x4,x5,x6,x7cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70X4111-211000-MX63-4120-110-MX71-2010001j0X4103-20100-1-MX610100-11-2-1X31-2010001j2023/4/773-6M-1+M-1+3M0-M001-1+M00-M0-3M+1与书上39页11题相似对偶与灵敏度9三。写出下面线性规划的对偶规划模型解：按照对称形式的对偶关系，其对偶模型为对偶与灵敏度10对偶与灵敏度11写出下列线性规划的对偶问题：（1）s.t.(LP)对偶与灵敏度12LPDP四。运输问题书78页最小元素法书81页闭回路法14以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。则解的变化和目标函数的变化如何。

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量81412144815要保证产销平衡，则

为闭回路

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量814121448116

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量8141214481217

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量81412144812118

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量8141214481021119

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量814121448121121020

销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量814121448121-11210检验数中有负数，说明原方案不是最优解。2023/4/7五。。无向图情形求网络中v1至v7的最短路。v1v2v3v4v5v6v72253557157132023/4/7无向图情形答案（1）：v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]六。网络计划（30分）计算各工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差、单时差，并指出关键工序。24关键工序：hbgafk1324785691011c7e5f5k1J2d3a3l7b4h5005578161711111414141416171919202099m3g2七。决策分析悲观准则乐观准则（行动方案）（自然状态）需求数量订购量

6 7 8 9 10 6* 30 30 30 30 30 7 10 35 35 35 35 8-10 15 40 40 40 9 -30 -5 20 45 45 10 -50 -25 0 25 50

min3010-10-30-50Max30悲观准则（行动方案）（自然状态）需求数量订购量

6 7 8 9 10 6 30 30 30