南京大学：《计算机问题求解》课程教学资源（课件讲稿）线性规划

计算机问题求解-论题3-15 线性规划 2014年12月22日

计算机问题求解 – 论题3-15 - 线性规划 2014 年12 月22 日

自学检查 When converting one linear program L into another linear program L',we would like the property that an optimal solution to L'yields an optimal solution to L.To capture this idea,we say that two maximization linear programs L and L'are eguivalent if for each feasible solution to L with objective value there is a corresponding feasible solution to L'with objective value and for each feasible solution 'to L'with objective value there is a corresponding feasible solution to L with objective value (This definition does not imply a one-to-

自学检查

maximize X1 + X2 subject to 问题1： 4X1 X2 S 8 2x1 + X2 ≤ 10 你能否利用左边 5x1 2X2 ≥ -2 X1,X2 ≥ 0 的式子和图解释 X2 ：目标函数、约 7 2X2 5x 束条件、可行解 X 、目标值、目标 R 3≤8 + 值的可行解、线 =4 性规划问题的解 2≥0 +2 0 线性规划？

问题2 policy urban suburban rural 如何趣邻下列语句 build roads -2 5 3 gun control 8 2 -5 Although we cannot easily graph farm subsidies 0 0 10 linear programs with more than two gasoline tax 10 0 -2 variables,the same intuition holds.If we have three variables,then each constraint corresponds to a half- space in three-dimensional space. The intersection of these half-spaces forms the feasible region. minimize X1 + X2 + X3 + X4 subject to -2x1 8x2 + 0x3 + 10x4 2 50 5x1 2x2 + 0x3 + 0x4 ≥ 100 3x1 5x2 + 10x3 2x4 ≥ 25 X1,X2,X3,X4 ≥ 0

Although we cannot easily graph linear programs with more than two variables, the same intuition holds. If we have three variables, then each constraint corresponds to a half￾space in three-dimensional space. The intersection of these half-spaces forms the feasible region

问题3： 线性规划问题中的不等 式能不能用严格的大于 或小于？

一个“现实”问题：Product-Mix This corporation has 10 plants in various parts of the world.Each of these plants produces the same 10 products and then sells them within its region.The de- mand (sales potential)for each of these products from each plant is known for each of the next 10 months.Although the amount of a product sold by a plant in a given month cannot exceed the demand,the amount produced can be larger,where the excess amount would be stored in inventory (at some unit cost per month)for sale in a later month 每个厂有10条生产线，可以安排任何产品，但效率和成本可能不 同。必要时也可以考虑在厂间运输成品，特定两个厂之间单位产品运 输成本是固定的。每个厂存储能力有上限，单位成本相同。 Management now needs to determine how much of each product should be produced by each machine in each plant during each month,as well as how much each plant should sell of each product in each month and how much each plant should ship of each prod- uct in each month to each of the other plants.Considering the worldwide price for each product,the objective is to find the feasible plan that maximizes the total profit(total sales revenue minus the sum of the total production costs,inventory costs,and shipping costs)

一个“现实”问题：Product-Mix 每个厂有10条生产线，可以安排任何产品，但效率和成本可能不 同。必要时也可以考虑在厂间运输成品，特定两个厂之间单位产品运 输成本是固定的。每个厂存储能力有上限，单位成本相同

问题4： 你能否估计一下这个问题 66 规模”有多大？ 1000prodvariables:n for each combntion of a pat,machne,produt and month 1,000 inventory variables:one for each combination of a plant,product,and month 1,000 sales variables:ne for each combination of a plant,product,and month shipping variables:n for each ombination of a produt,month,plant (the fromplant),and another plant (the toplant)

线性规划问题的标准形式 n maximize ∑ jxj = subject to i≤b fori=1,2,..,m ≥0forj=1,2,.,n maximize CTx subject to Ax ≤ b ≥ 0

线性规划问题的标准形式

minimize -2x1+3x2 subject to X1 X2 三7 X1- 2x2 ≤ 4 X1 ≥ 0 问题5： 为什么说这不是“标准形式

mizing a linear function subject to linear constraints,into standard form.A linear program might not be in standard form for any of four possible reasons: 1.The objective function might be a minimization rather than a maximization. 2.There might be variables without nonnegativity constraints. 3.There might be equality constraints,which have an equal sign rather than a less-than-or-equal-to sign. 4.There might be inequality constraints,but instead of having a less-than-or- equal-to sign,they have a greater-than-or-equal-to sign