<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta name="generator" content="pdf2htmlEX">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css">
<link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css">
<link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/625bbb5792dc900e622aaa18/raw.css">
<script src="https://static.pudn.com/base/js/compatibility.min.js"></script>
<script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script>
<script>
try{
pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});
}catch(e){}
</script>
<title></title>
</head>
<body>
<div id="sidebar" style="display: none">
<div id="outline">
</div>
</div>
<div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625bbb5792dc900e622aaa18/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h3 y2 ff2 fs0 fc0 sc0 ls0 ws0">-1- </div><div class="t m0 x3 h4 y3 ff2 fs1 fc0 sc1 ls1 ws0">第一章<span class="ff3 sc0 ls2"> </span>线性规划<span class="ff3 sc0 ls0"> </span></div><div class="t m0 x4 h5 y4 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h5 y5 ff2 fs2 fc0 sc0 ls0 ws0">§<span class="ff1 ls3 ws1">1 </span>线性规划<span class="ff1"> </span></div><div class="t m0 x5 h6 y6 ff2 fs2 fc0 sc0 ls0 ws0">在人们的生产实践中，<span class="_ _0"></span>经常会遇到如何利用现有资源来安排生产，<span class="_ _0"></span>以取得最大经济</div><div class="t m0 x4 h5 y7 ff2 fs2 fc0 sc0 ls4 ws0">效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划<span class="ff1 ls5">(Linear </span></div><div class="t m0 x4 h5 y8 ff1 fs2 fc0 sc0 ls6 ws0">Programming <span class="_ _1"> </span><span class="ff2 ls0">简记<span class="_ _2"> </span></span><span class="ls7">LP)<span class="ff2 ls0">则是数学规划的一个重要分支。自从<span class="_ _2"> </span></span><span class="ls8">1947<span class="_"> </span><span class="ff2 ls0">年<span class="_ _2"> </span></span><span class="ls9 ws2">G.<span class="_ _3"></span> B<span class="_ _3"></span>.<span class="_ _4"></span> D<span class="_ _4"></span>a<span class="_ _4"></span>n<span class="_ _3"></span>t<span class="_ _4"></span>z<span class="_ _3"></span>i<span class="_ _4"></span>g<span class="_ _3"></span> <span class="_ _1"> </span></span><span class="ff2 ls0">提出</span></span></span></div><div class="t m0 x4 h6 y9 ff2 fs2 fc0 sc0 ls0 ws0">求解线性规划的单纯形方法以来，<span class="_ _0"></span>线性规划在理论上趋向成熟，<span class="_ _0"></span>在实用中日益广泛与深</div><div class="t m0 x4 h6 ya ff2 fs2 fc0 sc0 ls0 ws0">入。<span class="_ _0"></span>特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，<span class="_ _0"></span>线性</div><div class="t m0 x4 h5 yb ff2 fs2 fc0 sc0 ls0 ws0">规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。<span class="ff1"> </span></div><div class="t m0 x5 h5 yc ff1 fs2 fc0 sc0 lsa ws0">1.1 <span class="_"> </span><span class="ff2 ls0">线性规划的实例与定义<span class="ff1"> </span></span></div><div class="t m0 x5 h5 yd ff2 fs2 fc0 sc0 ls0 ws0">例<span class="_ _2"> </span><span class="ff1 ls3 ws1">1 </span>某机床厂生产甲、<span class="_ _5"></span>乙两种机床，<span class="_ _5"></span>每台销售后的利润分别为<span class="_ _2"> </span><span class="ff1 ls8">4000<span class="_"> </span></span>元与<span class="_ _2"> </span><span class="ff1 ls8">3000<span class="_ _2"> </span></span>元。</div><div class="t m0 x4 h6 ye ff2 fs2 fc0 sc0 ls0 ws0">生产甲机床需用</div><div class="t m0 x6 h7 yf ff4 fs3 fc0 sc0 ls0 ws0">B<span class="_ _6"></span>A<span class="ff2">、<span class="_ _7"> </span><span class="fs2">机器加工，加工时间分别为每台<span class="_ _8"> </span><span class="ff1">2<span class="_ _8"> </span></span>小时和<span class="_ _8"> </span><span class="ff1">1<span class="_ _8"> </span></span>小时；生产乙机床</span></span></div><div class="t m0 x4 h6 y10 ff2 fs2 fc0 sc0 ls0 ws0">需用</div><div class="t m0 x7 h8 y11 ff4 fs4 fc0 sc0 ls0 ws0">C<span class="_ _9"></span>B<span class="_ _6"></span>A<span class="_ _a"> </span><span class="ff2">、<span class="_ _b"></span>、<span class="_ _c"> </span><span class="fs2">三种机器加工，<span class="_ _0"></span>加工时间为每台各一小时。<span class="_ _d"></span>若每天可用于加工的机器时</span></span></div><div class="t m0 x4 h6 y12 ff2 fs2 fc0 sc0 ls0 ws0">数分别为</div><div class="c x8 y13 w2 h9"><div class="t m0 x0 ha y14 ff4 fs5 fc0 sc0 ls0 ws0">A</div></div><div class="t m0 x9 h5 y15 ff2 fs2 fc0 sc0 ls0 ws0">机器<span class="_ _2"> </span><span class="ff1 ls8">10<span class="_"> </span></span>小时、</div><div class="c xa y16 w3 hb"><div class="t m0 x0 hc y17 ff4 fs6 fc0 sc0 ls0 ws0">B</div></div><div class="t m0 xb h7 y15 ff2 fs2 fc0 sc0 ls0 ws0">机器<span class="_ _2"> </span><span class="ff1">8<span class="_"> </span></span>小时和<span class="_ _4"> </span><span class="ff4 fs3">C<span class="_ _2"> </span></span>机器<span class="_ _2"> </span><span class="ff1">7<span class="_ _2"> </span></span>小时，<span class="_ _e"></span>问该厂应生产甲、<span class="_ _e"></span>乙机床各</div><div class="t m0 x4 h5 y18 ff2 fs2 fc0 sc0 ls0 ws0">几台，才能使总利润最大？<span class="ff1"> </span></div><div class="t m0 x5 h6 y19 ff2 fs2 fc0 sc0 ls0 ws0">上述问题的数学模型：<span class="_ _f"></span>设该厂生产</div><div class="t m0 xc hd y1a ff1 fs7 fc0 sc0 ls0 ws0">1</div><div class="t m0 xd he y1b ff4 fs8 fc0 sc0 ls0 ws0">x<span class="_ _10"> </span><span class="ff2 fs2">台甲机床和</span></div><div class="t m0 xe hd y1a ff1 fs7 fc0 sc0 ls0 ws0">2</div><div class="t m0 xf he y1b ff4 fs8 fc0 sc0 ls0 ws0">x<span class="_ _11"> </span><span class="ff2 fs2">乙机床时总利润最大，<span class="_ _f"></span>则</span></div><div class="t m0 x10 hd y1a ff1 fs7 fc0 sc0 ls0 ws0">2<span class="_ _12"></span>1</div><div class="t m0 x11 hf y1b ff1 fs8 fc0 sc0 ls0 ws0">,<span class="_ _1"> </span><span class="ff4">x<span class="_ _13"></span>x</span></div><div class="t m0 x4 h5 y1c ff2 fs2 fc0 sc0 ls0 ws0">应满足<span class="ff1"> </span></div><div class="t m0 x5 h6 y1d ff2 fs2 fc0 sc0 ls0 ws0">（目标函数）</div><div class="t m0 x12 hd y1e ff1 fs7 fc0 sc0 ls0 ws0">2<span class="_ _14"></span>1</div><div class="t m0 x13 hf y1f ff1 fs8 fc0 sc0 ls0 ws0">3<span class="_ _15"></span>4<span class="_ _16"></span>max<span class="_ _17"> </span><span class="ff4">x<span class="_ _18"></span>x<span class="_ _19"></span>z</span></div><div class="c x14 y20 w4 h10"><div class="t m0 x0 h11 y21 ff5 fs8 fc0 sc0 ls0 ws0">+</div></div><div class="t m0 x15 h11 y1f ff5 fs8 fc0 sc0 ls0 ws0">=</div><div class="t m0 x16 h5 y1d ff1 fs2 fc0 sc0 lsb ws0"> <span class="_ _1a"></span> <span class="_ _1a"></span> <span class="_ _1a"></span> (<span class="_ _0"></span>1<span class="_ _0"></span>)<span class="_ _0"></span> </div><div class="t m0 x17 h5 y22 ff1 fs2 fc0 sc0 lsc ws0">s.t.<span class="ff2 ls0">（约束条件）</span></div><div class="t m0 x18 h12 y23 ff5 fs9 fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h12 y24 ff5 fs9 fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h12 y25 ff5 fs9 fc0 sc0 ls0 ws0">⎩</div><div class="t m0 x18 h12 y26 ff5 fs9 fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h12 y27 ff5 fs9 fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h12 y28 ff5 fs9 fc0 sc0 ls0 ws0">⎨</div><div class="t m0 x18 h12 y29 ff5 fs9 fc0 sc0 ls0 ws0">⎧</div><div class="t m0 x19 h12 y2a ff5 fs9 fc0 sc0 ls0 ws0">≥</div><div class="t m0 x1a h12 y2b ff5 fs9 fc0 sc0 ls0 ws0">≤</div><div class="t m0 x1b h12 y2c ff5 fs9 fc0 sc0 ls0 ws0">≤<span class="_ _1b"></span>+</div><div class="t m0 x1c h12 y2d ff5 fs9 fc0 sc0 ls0 ws0">≤<span class="_ _1b"></span>+</div><div class="t m0 x1d h13 y2a ff1 fs9 fc0 sc0 ls0 ws0">0<span class="_ _15"></span>,</div><div class="t m0 x1e h13 y2b ff1 fs9 fc0 sc0 ls0 ws0">7</div><div class="t m0 x1f h13 y2c ff1 fs9 fc0 sc0 ls0 ws0">8</div><div class="t m0 x13 h13 y2d ff1 fs9 fc0 sc0 ls0 ws0">10<span class="_ _1c"></span>2</div><div class="t m0 x20 h14 y2e ff1 fsa fc0 sc0 ls0 ws0">2<span class="_ _12"></span>1</div><div class="t m0 x21 h14 y2f ff1 fsa fc0 sc0 ls0 ws0">2</div><div class="t m0 x19 h14 y30 ff1 fsa fc0 sc0 ls0 ws0">2<span class="_ _1d"></span>1</div><div class="t m0 x22 h14 y31 ff1 fsa fc0 sc0 ls0 ws0">2<span class="_ _1d"></span>1</div><div class="t m0 x23 h15 y32 ff4 fs9 fc0 sc0 ls0 ws0">x<span class="_ _13"></span>x</div><div class="t m0 x24 h15 y33 ff4 fs9 fc0 sc0 ls0 ws0">x</div><div class="t m0 x25 h15 y34 ff4 fs9 fc0 sc0 ls0 ws0">x<span class="_ _1e"></span>x</div><div class="t m0 x19 h15 y35 ff4 fs9 fc0 sc0 ls0 ws0">x<span class="_ _1e"></span>x</div><div class="t m0 x26 h5 y22 ff1 fs2 fc0 sc0 lsb ws0"> <span class="_ _1a"></span> <span class="_ _1a"></span> <span class="_ _1a"></span> <span class="ff2 ls0">（<span class="ff1">2</span>）<span class="ff1"> </span></span></div><div class="t m0 x4 h6 y36 ff2 fs2 fc0 sc0 ls0 ws0">这里变量</div><div class="t m0 x27 h16 y37 ff1 fsb fc0 sc0 ls0 ws0">2<span class="_ _1f"></span>1</div><div class="t m0 x9 h17 y38 ff1 fsc fc0 sc0 ls0 ws0">,<span class="_ _20"> </span><span class="ff4">x<span class="_ _21"></span>x<span class="_ _22"> </span><span class="ff2 fs2">称之为决策变量，<span class="_ _23"></span>（<span class="ff1">1</span>）<span class="_ _24"></span>式被称为问题的目标函数，<span class="_ _23"></span>（<span class="ff1">2</span>）<span class="_ _24"></span>中的几个不等式</span></span></div><div class="t m0 x4 h5 y39 ff2 fs2 fc0 sc0 ls0 ws0">是问题的约束条件，记为<span class="_ _25"> </span><span class="ff1 lsd">s.t.(</span>即<span class="_ _25"> </span><span class="ff1 lse ws3">subject to)</span>。由于<span class="_ _24"></span>上面的目标函数及约束条件均为线性</div><div class="t m0 x4 h5 y3a ff2 fs2 fc0 sc0 ls0 ws0">函数，故被称为线性规划问题。<span class="ff1"> </span></div><div class="t m0 x5 h6 y3b ff2 fs2 fc0 sc0 ls0 ws0">总之，<span class="_ _0"></span>线性规划问题是在一组线性约束条件的限制下，<span class="_ _0"></span>求一线性目标函数最大或最</div><div class="t m0 x4 h5 y3c ff2 fs2 fc0 sc0 ls0 ws0">小的问题。<span class="ff1"> </span></div><div class="t m0 x5 h6 y3d ff2 fs2 fc0 sc0 ls0 ws0">在解决实际问题时，<span class="_ _0"></span>把问题归结成一个线性规划数学模型是很重要的一步，<span class="_ _0"></span>但往往</div><div class="t m0 x4 h6 y3e ff2 fs2 fc0 sc0 ls0 ws0">也是困难的一步，<span class="_ _e"></span>模型建立得是否恰当，<span class="_ _e"></span>直接影响到求解。<span class="_ _e"></span>而选适当的决策变量，<span class="_ _26"></span>是我</div><div class="t m0 x4 h5 y3f ff2 fs2 fc0 sc0 ls0 ws0">们建立有效模型的关键之一。<span class="ff1"> </span></div><div class="t m0 x5 h5 y40 ff1 fs2 fc0 sc0 lsa ws0">1.2<span class="ff6 ls0"> <span class="_ _20"> </span><span class="ff2">线性规划的<span class="_ _1"> </span></span></span>Matlab<span class="_"> </span><span class="ff2 ls0">标准形式<span class="ff1"> </span></span></div><div class="t m0 x5 h6 y41 ff2 fs2 fc0 sc0 ls0 ws0">线性规划的目标函数可以是求最大值，<span class="_ _0"></span>也可以是求最小值，<span class="_ _0"></span>约束条件的不等号可以</div><div class="t m0 x4 h5 y42 ff2 fs2 fc0 sc0 lsf ws0">是小于号也可以是大于号。为了避免这种形式多样性带来的不便，<span class="ff1 lse">Matlab<span class="_ _10"> </span></span>中规定线性</div><div class="t m0 x4 h5 y43 ff2 fs2 fc0 sc0 ls0 ws0">规划的标准形式为<span class="ff1"> </span></div><div class="t m0 x23 h18 y44 ff4 fsd fc0 sc0 ls0 ws0">x<span class="_ _27"></span>c</div><div class="t m0 x28 h18 y45 ff4 fsd fc0 sc0 ls0 ws0">x</div><div class="t m0 xa h19 y46 ff4 fse fc0 sc0 ls0 ws0">T</div><div class="t m0 x29 h1a y44 ff1 fsd fc0 sc0 ls0 ws0"> <span class="_ _28"></span>min<span class="_ _29"> </span><span class="fs2"> </span></div><div class="t m0 x4 h5 y47 ff1 fs2 fc0 sc0 ls10 ws0"> <span class="_ _24"></span> s<span class="_ _2a"></span>.<span class="_ _2a"></span>t<span class="_ _0"></span>.<span class="_ _2a"></span> </div><div class="t m0 x18 h1b y48 ff5 fsf fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h1b y49 ff5 fsf fc0 sc0 ls0 ws0">⎩</div><div class="t m0 x18 h1b y4a ff5 fsf fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h1b y4b ff5 fsf fc0 sc0 ls0 ws0">⎨</div><div class="t m0 x18 h1b y4c ff5 fsf fc0 sc0 ls0 ws0">⎧</div><div class="t m0 x2a h1b y4d ff5 fsf fc0 sc0 ls0 ws0">≤<span class="_ _2b"></span>≤</div><div class="t m0 x1b h1b y4e ff5 fsf fc0 sc0 ls0 ws0">=<span class="_ _21"></span>⋅</div><div class="t m0 x2b h1b y4f ff5 fsf fc0 sc0 ls0 ws0">≤</div><div class="t m0 x2c h1c y50 ff4 fsf fc0 sc0 ls0 ws0">ub<span class="_ _19"></span>x<span class="_ _2c"></span>lb</div><div class="t m0 x2d h1c y51 ff4 fsf fc0 sc0 ls0 ws0">beq<span class="_ _2d"></span>x<span class="_ _2e"></span>Aeq</div><div class="t m0 x2e h1c y52 ff4 fsf fc0 sc0 ls0 ws0">b<span class="_ _14"></span>Ax</div><div class="t m0 xd h5 y53 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h6 y54 ff2 fs2 fc0 sc0 ls11 ws0">其中</div><div class="t m0 x2f h1d y55 ff4 fs10 fc0 sc0 ls0 ws0">c<span class="_ _20"> </span><span class="ff2 fs2">和</span></div><div class="c x30 y56 w5 h1e"><div class="t m0 x0 h1d y57 ff4 fs10 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 x31 h1f y55 ff2 fs2 fc0 sc0 ls0 ws0">为<span class="_ _20"> </span><span class="ff4 fs10">n<span class="_ _20"> </span></span><span class="ls11">维列向量，<span class="_ _25"> </span></span><span class="ff4 fs11">A<span class="_ _20"></span></span>、<span class="_ _2"> </span><span class="ff4 fs12">Aeq<span class="_ _2"> </span></span><span class="ls11">为适当维数的矩阵，<span class="_ _3"> </span></span><span class="ff4 fs10">b<span class="_ _2"> </span></span>、<span class="_ _2f"> </span><span class="ff4 fs12">beq<span class="_ _1"> </span></span><span class="ls11">为适当维数的列向</span></div><div class="t m0 x4 h5 y58 ff2 fs2 fc0 sc0 ls0 ws0">量。<span class="ff1"> </span></div></div><div class="pi" data-data='{"ctm":[1.611639,0.000000,0.000000,1.611639,0.000000,0.000000]}'></div></div>
</body>
</html>
<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625bbb5792dc900e622aaa18/bg2.jpg"><div class="t m0 x32 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x33 h3 y2 ff2 fs0 fc0 sc0 ls0 ws0">-2- </div><div class="t m0 x34 h5 y59 ff2 fs2 fc0 sc0 ls0 ws0">例如线性规划<span class="ff1"> </span></div><div class="t m0 x35 h20 y5a ff4 fs13 fc0 sc0 ls0 ws0">b<span class="_ _14"></span>Ax<span class="_ _30"></span>x<span class="_ _27"></span>c</div><div class="t m0 x36 h20 y5b ff4 fs13 fc0 sc0 ls0 ws0">x</div><div class="t m0 x37 h21 y5c ff4 fs14 fc0 sc0 ls0 ws0">T</div><div class="t m0 x26 h22 y5a ff5 fs13 fc0 sc0 ls0 ws0">≥<span class="_ _31"></span><span class="ff1"> <span class="_ _32"></span>s.t.<span class="_ _33"></span> <span class="_ _18"></span> <span class="_ _34"></span>max</span></div><div class="t m0 x38 h5 y5d ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x39 h5 y5e ff2 fs2 fc0 sc0 ls0 ws0">的<span class="_ _2"> </span><span class="ff1 lse">Matlab<span class="_"> </span></span>标准型为<span class="ff1"> </span></div><div class="t m0 x39 h20 y5f ff1 fs2 fc0 sc0 lsb ws0"> <span class="_ _1a"></span> <span class="_ _35"> </span><span class="ff4 fs13 ls0">b<span class="_ _36"></span>Ax<span class="_ _37"></span>x<span class="_ _27"></span>c</span></div><div class="t m0 x3a h20 y60 ff4 fs13 fc0 sc0 ls0 ws0">x</div><div class="t m0 x29 h19 y61 ff4 fse fc0 sc0 ls0 ws0">T</div><div class="t m0 x3b h22 y5f ff5 fsd fc0 sc0 ls0 ws0">−<span class="_ _38"></span>≤<span class="_ _18"></span>−<span class="_ _39"></span>−<span class="_ _3a"> </span><span class="ff1 fs13"> <span class="_ _32"></span>s.t.<span class="_ _33"></span> <span class="_ _3b"></span> <span class="_ _2b"></span>min<span class="_ _3c"> </span><span class="fs2"> </span></span></div><div class="t m0 x34 h5 y62 ff1 fs2 fc0 sc0 lsa ws0">1.3 <span class="_"> </span><span class="ff2 ls0">线性规划问题的解的概念<span class="ff1"> </span></span></div><div class="t m0 x34 h5 y63 ff2 fs2 fc0 sc0 ls0 ws0">一般线性规划问题的（数学）标准型为<span class="ff1"> </span></div><div class="t m0 x3c h23 y64 ff5 fs15 fc0 sc0 ls0 ws0">∑</div><div class="t m0 x3d h24 y65 ff5 fs16 fc0 sc0 ls0 ws0">=</div><div class="t m0 x3e h25 y66 ff5 fs17 fc0 sc0 ls0 ws0">=</div><div class="t m0 x3d h26 y67 ff4 fs16 fc0 sc0 ls0 ws0">n</div><div class="t m0 x28 h26 y68 ff4 fs16 fc0 sc0 ls0 ws0">j</div><div class="t m0 xb h26 y69 ff4 fs16 fc0 sc0 ls0 ws0">j<span class="_ _3d"></span>j</div><div class="t m0 x15 h27 y66 ff4 fs17 fc0 sc0 ls0 ws0">x<span class="_ _3e"></span>c<span class="_ _31"></span>z</div><div class="t m0 x3f h28 y65 ff1 fs16 fc0 sc0 ls0 ws0">1</div><div class="t m0 x40 h29 y66 ff1 fs17 fc0 sc0 ls0 ws0">max<span class="_ _3f"> </span><span class="fs2 lsb"> <span class="_ _1a"></span> <span class="_ _1a"></span> <span class="_ _1a"></span> <span class="_ _1a"></span>(<span class="_ _2a"></span>3<span class="_ _0"></span>)<span class="_ _0"></span> </span></div><div class="t m0 x41 h5 y6a ff1 fs2 fc0 sc0 lsd ws4">s.t. </div><div class="t m0 x42 h2a y6b ff5 fs18 fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x42 h2a y6c ff5 fs18 fc0 sc0 ls0 ws0">⎩</div><div class="t m0 x42 h2a y6d ff5 fs18 fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x42 h2a y6e ff5 fs18 fc0 sc0 ls0 ws0">⎨</div><div class="t m0 x42 h2a y6f ff5 fs18 fc0 sc0 ls0 ws0">⎧</div><div class="t m0 x43 h2a y70 ff5 fs18 fc0 sc0 ls0 ws0">=<span class="_ _40"></span>≥</div><div class="t m0 x1e h2a y71 ff5 fs18 fc0 sc0 ls0 ws0">=<span class="_ _40"></span>=</div><div class="t m0 x44 h2b y72 ff5 fs19 fc0 sc0 ls0 ws0">∑</div><div class="t m0 x45 h2c y73 ff5 fs1a fc0 sc0 ls0 ws0">=</div><div class="t m0 x1c h2d y74 ff4 fs18 fc0 sc0 ls0 ws0">n<span class="_ _41"></span>j<span class="_ _42"></span>x</div><div class="t m0 x16 h2d y75 ff4 fs18 fc0 sc0 ls0 ws0">m<span class="_ _43"></span>i<span class="_ _34"></span>b<span class="_ _32"></span>x<span class="_ _27"></span>a</div><div class="t m0 x46 h2e y76 ff4 fs1a fc0 sc0 ls0 ws0">j</div><div class="t m0 x45 h2e y77 ff4 fs1a fc0 sc0 ls0 ws0">n</div><div class="t m0 x47 h2e y78 ff4 fs1a fc0 sc0 ls0 ws0">j</div><div class="t m0 x48 h2e y79 ff4 fs1a fc0 sc0 ls0 ws0">i<span class="_ _44"></span>j<span class="_ _45"></span>ij</div><div class="t m0 x49 h2f y74 ff1 fs18 fc0 sc0 ls0 ws0">,<span class="_ _1f"></span>,<span class="_ _46"></span>2<span class="_ _47"></span>,<span class="_ _48"></span>1<span class="_ _49"></span>0</div><div class="t m0 x4a h2f y75 ff1 fs18 fc0 sc0 ls0 ws0">,<span class="_ _1f"></span>,<span class="_ _46"></span>2<span class="_ _47"></span>,<span class="_ _48"></span>1</div><div class="t m0 x4b h30 y73 ff1 fs1a fc0 sc0 ls0 ws0">1</div><div class="t m0 x1e h31 y74 ff7 fs18 fc0 sc0 ls0 ws0">L</div><div class="t m0 x13 h31 y75 ff7 fs18 fc0 sc0 ls0 ws0">L</div><div class="t m0 x4c h5 y7a ff1 fs2 fc0 sc0 lsb ws0"> <span class="_ _1a"></span> <span class="_ _1a"></span> <span class="_ _1a"></span> (<span class="_ _0"></span>4<span class="_ _2a"></span>)<span class="_ _0"></span> </div><div class="t m0 x34 h32 y7b ff2 fs2 fc0 sc1 lsf ws0">可行解<span class="ff3 sc0 ls10"> <span class="ff2 ls0">满足约束条件<span class="_ _0"></span>（<span class="ff1">4</span><span class="ls12">）的<span class="_ _1"> </span>解</span></span></span></div><div class="t m0 x4d h33 y7c ff1 fs6 fc0 sc0 ls0 ws0">)<span class="_ _13"></span>,<span class="_ _4a"></span>,<span class="_ _12"></span>,<span class="_ _27"></span>(</div><div class="t m0 x4e h34 y7d ff1 fs1b fc0 sc0 ls0 ws0">2<span class="_ _12"></span>1<span class="_ _4b"> </span><span class="ff4">n</span></div><div class="t m0 x4f h2d y7c ff4 fs18 fc0 sc0 ls0 ws0">x<span class="_ _4c"></span>x<span class="_ _13"></span>x<span class="_ _32"></span>x<span class="_ _4d"> </span><span class="ff7 fs6">L</span></div><div class="c x50 y7e w6 h35"><div class="t m0 x0 h36 y57 ff5 fs6 fc0 sc0 ls0 ws0">=</div></div><div class="t m0 x51 h6 y7c ff2 fs2 fc0 sc0 ls0 ws0">，<span class="_ _0"></span>称为线性规划问题的可行解，</div><div class="t m0 x39 h5 y7f ff2 fs2 fc0 sc0 ls0 ws0">而使目标函数（<span class="ff1">3</span>）达到最大值的可行解叫最优解。<span class="ff1"> </span></div><div class="t m0 x34 h32 y80 ff2 fs2 fc0 sc1 lsf ws0">可行域<span class="ff3 sc0 ls10"> <span class="ff2 ls0">所有可行解构成的集合称为问题的可行域，记为</span></span></div><div class="c x52 y81 w3 hb"><div class="t m0 x0 h2d y17 ff4 fs18 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x53 h5 y82 ff2 fs2 fc0 sc0 ls0 ws0">。<span class="ff1"> </span></div><div class="t m0 x34 h5 y83 ff1 fs2 fc0 sc0 lsa ws0">1.4 <span class="_"> </span><span class="ff2 ls0">线性规划的图解法<span class="ff1"> </span></span></div><div class="t m0 x54 h37 y84 ff6 fs1c fc0 sc0 ls0 ws0">0<span class="_ _4e"> </span>2<span class="_ _4e"> </span>4<span class="_ _4e"> </span>6<span class="_ _4e"> </span>8<span class="_ _4f"> </span><span class="ls13">10</span></div><div class="t m0 x55 h37 y85 ff6 fs1c fc0 sc0 ls0 ws0">0</div><div class="t m0 x55 h37 y86 ff6 fs1c fc0 sc0 ls0 ws0">1</div><div class="t m0 x55 h37 y87 ff6 fs1c fc0 sc0 ls0 ws0">2</div><div class="t m0 x55 h37 y88 ff6 fs1c fc0 sc0 ls0 ws0">3</div><div class="t m0 x55 h37 y89 ff6 fs1c fc0 sc0 ls0 ws0">4</div><div class="t m0 x55 h37 y8a ff6 fs1c fc0 sc0 ls0 ws0">5</div><div class="t m0 x55 h37 y8b ff6 fs1c fc0 sc0 ls0 ws0">6</div><div class="t m0 x55 h37 y8c ff6 fs1c fc0 sc0 ls0 ws0">7</div><div class="t m0 x55 h37 y8d ff6 fs1c fc0 sc0 ls0 ws0">8</div><div class="t m0 x55 h37 y8e ff6 fs1c fc0 sc0 ls0 ws0">9</div><div class="t m0 x56 h37 y8f ff6 fs1c fc0 sc0 ls13 ws0">10</div><div class="t m0 x38 h37 y8c ff6 fs1c fc0 sc0 ls14 ws0">x2<span class="_ _50"></span>=<span class="_ _50"></span>7</div><div class="t m0 x57 h37 y90 ff6 fs1c fc0 sc0 ls13 ws0">2x<span class="_ _51"></span>1+x<span class="_ _51"></span>2=<span class="_ _24"></span>10</div><div class="t m0 x58 h37 y91 ff6 fs1c fc0 sc0 ls14 ws0">x1<span class="_ _50"></span>+<span class="_ _1a"></span>x2<span class="_ _50"> </span>=<span class="_ _50"> </span>8</div><div class="t m0 x1d h37 y92 ff6 fs1c fc0 sc0 ls14 ws0">z=<span class="_ _50"></span>1<span class="_ _1a"></span>2</div><div class="t m0 x59 h37 y93 ff6 fs1c fc0 sc0 ls15 ws0">(2<span class="_ _4"> </span>,<span class="_ _24"></span>6<span class="_ _50"> </span>)</div><div class="t m0 x5a h5 y94 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x5b h2 y95 ff2 fs0 fc0 sc0 ls0 ws0">图<span class="_ _20"> </span><span class="ff1 ws5">1 </span>线性规划的图解示意图<span class="ff1"> </span></div><div class="t m0 x34 h5 y96 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x34 h6 y97 ff2 fs2 fc0 sc0 ls0 ws0">图解法简单直观，<span class="_ _0"></span>有助于了解线性规划问题求解的基本原理。<span class="_ _0"></span>我们先应用图解法来</div><div class="t m0 x39 h5 y98 ff2 fs2 fc0 sc0 ls0 ws0">求解例<span class="_ _25"> </span><span class="ff1">1<span class="_ _1a"></span></span>。对于每一固定的值</div><div class="t m0 xa h38 y99 ff4 fs1d fc0 sc0 ls0 ws0">z<span class="_ _20"> </span><span class="ff2 fs2">，使目标函数值等于<span class="_ _20"> </span></span>z<span class="_ _20"> </span><span class="ff2 fs2">的点构成的直线称为目标函数等</span></div><div class="t m0 x39 h6 y9a ff2 fs2 fc0 sc0 ls0 ws0">位线，当</div><div class="c x5c y9b w7 h39"><div class="t m0 x0 h3a y14 ff4 fs1e fc0 sc0 ls0 ws0">z</div></div><div class="t m0 x5d h5 y9c ff2 fs2 fc0 sc0 ls0 ws0">变动时，我们得到一族平行直线。<span class="_ _24"></span>对于例<span class="_ _2"> </span><span class="ff1">1</span>，显然等位线越趋于右上方，<span class="_ _24"></span>其</div><div class="t m0 x39 h6 y9d ff2 fs2 fc0 sc0 ls11 ws0">上的点具有越大的目标函数值<span class="_ _24"></span>。不难看出，本例的最优解<span class="_ _24"></span>为</div><div class="t m0 x5e h3b y9e ff4 fs1b fc0 sc0 ls0 ws0">T</div><div class="t m0 x5f h38 y9f ff4 fs1d fc0 sc0 ls0 ws0">x<span class="_ _52"> </span><span class="ff1 fs6">)<span class="_ _53"></span>6<span class="_ _46"></span>,<span class="_ _47"></span>2<span class="_ _53"></span>(<span class="_ _28"></span>*<span class="_ _20"> </span><span class="ff5">=<span class="_ _54"> </span><span class="ff2 fs2 ls11">，最优目标值</span></span></span></div><div class="t m0 x60 h27 ya0 ff1 fs3 fc0 sc0 ls0 ws0">26<span class="_ _55"></span>*<span class="_ _1"> </span><span class="ff5">=<span class="_ _13"></span><span class="ff4 fs17">z<span class="_ _56"> </span><span class="ff2 fs2">。<span class="ff1"> </span></span></span></span></div><div class="t m0 x34 h5 ya1 ff2 fs2 fc0 sc0 ls0 ws0">从上面的图解过程可以看出并不难证明以下断言：<span class="ff1"> </span></div><div class="t m0 x34 h5 ya2 ff2 fs2 fc0 sc0 ls0 ws0">（<span class="ff1">1</span>）<span class="_ _26"></span>可行域</div><div class="c x27 ya3 w3 hb"><div class="t m0 x0 h38 y17 ff4 fs1d fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x56 h6 ya4 ff2 fs2 fc0 sc0 ls0 ws0">可能会出现多种情况。</div><div class="c x16 ya3 w3 hb"><div class="t m0 x0 h38 y17 ff4 fs1d fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x4c h6 ya4 ff2 fs2 fc0 sc0 ls0 ws0">可能是空集也可能是非空集合，<span class="_ _26"></span>当</div><div class="c x61 ya3 w3 hb"><div class="t m0 x0 h38 y17 ff4 fs1d fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x62 h6 ya4 ff2 fs2 fc0 sc0 ls0 ws0">非空</div><div class="t m0 x39 h6 ya5 ff2 fs2 fc0 sc0 ls0 ws0">时，<span class="_ _d"></span>它必定是若干个半平面的交集<span class="_ _0"></span>（除非遇到空间维数的退化）<span class="_ _57"></span>。</div><div class="c x63 ya6 w3 hb"><div class="t m0 x0 h38 y17 ff4 fs1d fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x64 h6 ya7 ff2 fs2 fc0 sc0 ls0 ws0">既可能是有界区域，</div><div class="t m0 x39 h5 ya8 ff2 fs2 fc0 sc0 ls0 ws0">也可能是无界区域。<span class="ff1"> </span></div><div class="t m0 x65 h5 ya9 ff2 fs2 fc0 sc0 ls0 ws0">（<span class="ff1">2</span>）<span class="_ _5"></span>在</div><div class="c x8 yaa w3 hb"><div class="t m0 x0 h38 y17 ff4 fs1d fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x66 h6 yab ff2 fs2 fc0 sc0 ls0 ws0">非空时，<span class="_ _5"></span>线性规划既可以存在有限最优解，<span class="_ _5"></span>也可以不存在有限最优解<span class="_ _f"></span>（其</div><div class="t m0 x39 h5 yac ff2 fs2 fc0 sc0 ls0 ws0">目标函数值无界）<span class="_ _57"></span>。<span class="ff1"> </span></div></div><div class="pi" data-data='{"ctm":[1.611639,0.000000,0.000000,1.611639,0.000000,0.000000]}'></div></div>
<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625bbb5792dc900e622aaa18/bg3.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h3 y2 ff2 fs0 fc0 sc0 ls0 ws0">-3- </div><div class="t m0 x67 h5 y59 ff2 fs2 fc0 sc0 ls0 ws0">（<span class="ff1">3</span>）<span class="_ _d"></span>若线性规划存在有限最优解，<span class="_ _0"></span>则必可找到具有最优目标函数值的可行域</div><div class="c x68 yad w3 hb"><div class="t m0 x0 h38 y17 ff4 fs1d fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x69 h6 y59 ff2 fs2 fc0 sc0 ls0 ws0">的</div><div class="t m0 x4 h5 yae ff2 fs2 fc0 sc0 ls0 ws0">“顶点”<span class="_ _57"></span>。<span class="ff1"> </span></div><div class="t m0 x67 h6 yaf ff2 fs2 fc0 sc0 ls0 ws0">上述论断可以推广到一般的线性规划问题，<span class="_ _5"></span>区别只在于空间的维数。<span class="_ _5"></span>在一般的</div><div class="t m0 x6a h27 yb0 ff4 fs17 fc0 sc0 ls0 ws0">n<span class="_ _20"> </span><span class="ff2 fs2">维</span></div><div class="t m0 x4 h6 yb1 ff2 fs2 fc0 sc0 lsf ws0">空间中，满足一线性等式</div><div class="t m0 x6b h3c yb2 ff5 fs1f fc0 sc0 ls0 ws0">∑</div><div class="t m0 xa h3d yb3 ff5 fs20 fc0 sc0 ls0 ws0">=</div><div class="t m0 x1c h3e yb4 ff5 fs21 fc0 sc0 ls0 ws0">=</div><div class="t m0 xa h3f yb5 ff4 fs20 fc0 sc0 ls0 ws0">n</div><div class="t m0 x6c h3f yb6 ff4 fs20 fc0 sc0 ls0 ws0">i</div><div class="t m0 x22 h3f yb7 ff4 fs20 fc0 sc0 ls0 ws0">i<span class="_ _58"></span>i</div><div class="t m0 x6d h40 yb4 ff4 fs21 fc0 sc0 ls0 ws0">b<span class="_ _32"></span>x<span class="_ _59"></span>a</div><div class="t m0 x5b h41 yb3 ff1 fs20 fc0 sc0 ls0 ws0">1</div><div class="t m0 x6e h6 yb4 ff2 fs2 fc0 sc0 lsf ws0">的点集被称为一个超平面，而满足一线性不等式</div><div class="t m0 x6f h3c yb8 ff5 fs1f fc0 sc0 ls0 ws0">∑</div><div class="t m0 x70 h3d yb9 ff5 fs20 fc0 sc0 ls0 ws0">=</div><div class="t m0 x71 h3e yba ff5 fs21 fc0 sc0 ls0 ws0">≤</div><div class="t m0 x70 h3f ybb ff4 fs20 fc0 sc0 ls0 ws0">n</div><div class="t m0 x32 h3f ybc ff4 fs20 fc0 sc0 ls0 ws0">i</div><div class="t m0 x17 h3f ybd ff4 fs20 fc0 sc0 ls0 ws0">i<span class="_ _58"></span>i</div><div class="t m0 x72 h40 yba ff4 fs21 fc0 sc0 ls0 ws0">b<span class="_ _5a"></span>x<span class="_ _59"></span>a</div><div class="t m0 x65 h41 yb9 ff1 fs20 fc0 sc0 ls0 ws0">1</div><div class="t m0 x66 h6 ybe ff2 fs2 fc0 sc0 ls0 ws0">（或</div><div class="t m0 x73 h3c yb8 ff5 fs1f fc0 sc0 ls0 ws0">∑</div><div class="t m0 x74 h3d yb9 ff5 fs20 fc0 sc0 ls0 ws0">=</div><div class="t m0 x29 h3e yba ff5 fs21 fc0 sc0 ls0 ws0">≥</div><div class="t m0 x74 h3f ybb ff4 fs20 fc0 sc0 ls0 ws0">n</div><div class="t m0 x75 h3f ybc ff4 fs20 fc0 sc0 ls0 ws0">i</div><div class="t m0 x76 h3f ybd ff4 fs20 fc0 sc0 ls0 ws0">i<span class="_ _58"></span>i</div><div class="t m0 x77 h40 yba ff4 fs21 fc0 sc0 ls0 ws0">b<span class="_ _5a"></span>x<span class="_ _59"></span>a</div><div class="t m0 x54 h41 yb9 ff1 fs20 fc0 sc0 ls0 ws0">1</div><div class="t m0 x59 h33 ybe ff2 fs2 fc0 sc0 ls0 ws0">）<span class="_ _e"></span>的点集被称为一个半空间<span class="_ _e"></span>（其中<span class="_ _5b"> </span><span class="ff1 fs6">)<span class="_ _5c"></span>,<span class="_ _13"></span>,<span class="_ _5d"></span>(</span></div><div class="t m0 x78 h41 ybf ff1 fs20 fc0 sc0 ls0 ws0">1<span class="_ _5e"> </span><span class="ff4">n</span></div><div class="t m0 x79 h40 ybe ff4 fs21 fc0 sc0 ls0 ws0">a<span class="_ _5f"></span>a<span class="_ _60"> </span><span class="ff7 fs6">L<span class="_ _61"> </span><span class="ff2 fs2">为一<span class="_ _2f"> </span></span></span><span class="fs22">n<span class="_ _1"> </span><span class="ff2 fs2">维行</span></span></div><div class="t m0 x4 h6 yc0 ff2 fs2 fc0 sc0 ls0 ws0">向量，</div><div class="t m0 x7a h42 yc1 ff4 fs22 fc0 sc0 ls0 ws0">b<span class="_ _1"> </span><span class="ff2 fs2">为一<span class="_ _1a"></span>实数）<span class="_ _57"></span>。若干个半空间的交集被称为多胞形，<span class="_ _1a"></span>有界的多胞形又被称为多<span class="_ _1a"></span>面</span></div><div class="t m0 x4 h6 yc2 ff2 fs2 fc0 sc0 ls0 ws0">体。易见，线性规划的可行域必为多胞形（为统一起见，空集</div><div class="c x7b yc3 w8 hb"><div class="t m0 x0 h3e y17 ff5 fs21 fc0 sc0 ls0 ws0">Φ</div></div><div class="t m0 x7c h5 yc4 ff2 fs2 fc0 sc0 ls0 ws0">也被视为多胞形）<span class="_ _57"></span>。<span class="ff1"> </span></div><div class="t m0 x4 h6 yc5 ff2 fs2 fc0 sc0 ls0 ws0">在一般</div><div class="t m0 x7a h27 yc6 ff4 fs17 fc0 sc0 ls0 ws0">n<span class="_ _1"> </span><span class="ff2 fs2">维空间中，<span class="_ _e"></span>要直接得出多胞形<span class="_ _e"></span>“顶点”<span class="_ _e"></span>概<span class="_ _1a"></span>念还有一些困难。<span class="_ _e"></span>二维空间中的顶点</span></div><div class="t m0 x4 h6 yc7 ff2 fs2 fc0 sc0 ls0 ws0">可以看成为边界直线的交点，<span class="_ _62"></span>但这一几何概念的推广在一般</div><div class="t m0 x7d h42 yc8 ff4 fs22 fc0 sc0 ls0 ws0">n<span class="_ _1"> </span><span class="ff2 fs2">维空间中的几何意义并不</span></div><div class="t m0 x4 h5 yc9 ff2 fs2 fc0 sc0 ls0 ws0">十分直观。为此，我们将采用另一途径来定义它。<span class="ff1"> </span></div><div class="t m0 x67 h32 yca ff2 fs2 fc0 sc1 ls16 ws0">定义<span class="_ _10"> </span><span class="ff3 sc0 ls3 ws6">1 </span><span class="sc0 ls0">称</span></div><div class="t m0 x74 h42 ycb ff4 fs22 fc0 sc0 ls0 ws0">n</div><div class="t m0 x3e h6 ycc ff2 fs2 fc0 sc0 ls17 ws0">维空间中的区域</div><div class="c x6e ycd w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x7e h27 ycc ff2 fs2 fc0 sc0 ls17 ws0">为一凸集，若<span class="_ _63"> </span><span class="ff4 fs17 ls0">R<span class="_ _64"></span>x<span class="_ _21"></span>x<span class="_ _65"> </span><span class="ff5 fsc">∈<span class="_ _66"></span>∀</span></span></div><div class="t m0 x53 h41 yce ff1 fs20 fc0 sc0 ls0 ws0">2<span class="_ _1f"></span>1</div><div class="t m0 x7d h43 ycc ff1 fs3 fc0 sc0 ls0 ws0">,<span class="_ _67"> </span><span class="ff2 fs2">及<span class="_ _68"> </span></span><span class="fs12">)<span class="_ _47"></span>1<span class="_ _48"></span>,<span class="_ _46"></span>0<span class="_ _69"></span>(<span class="_ _6a"></span><span class="ff5">∈<span class="_ _6b"></span>∀</span></span></div><div class="c x7f ycf w9 h44"><div class="t m1 x0 h45 y57 ff5 fs23 fc0 sc0 ls0 ws0">λ</div></div><div class="t m0 x80 h6 ycc ff2 fs2 fc0 sc0 ls17 ws0">，有</div><div class="t m0 x81 h40 yd0 ff4 fs21 fc0 sc0 ls0 ws0">R<span class="_ _64"></span>x<span class="_ _30"></span>x<span class="_ _6c"> </span><span class="ff5 fs12">∈<span class="_ _40"></span>−<span class="_ _1e"></span>+</span></div><div class="t m0 x47 h41 yd1 ff1 fs20 fc0 sc0 ls0 ws0">2<span class="_ _6d"></span>1</div><div class="t m0 x82 h43 yd0 ff1 fs12 fc0 sc0 ls0 ws0">)<span class="_ _5a"></span>1<span class="_ _47"></span>(</div><div class="t m2 x72 h46 yd0 ff5 fs24 fc0 sc0 ls0 ws0">λ<span class="_ _16"></span>λ</div><div class="t m0 x83 h5 yd0 ff2 fs2 fc0 sc0 ls0 ws0">。<span class="ff1"> </span></div><div class="t m0 x67 h32 yd2 ff2 fs2 fc0 sc1 lsf ws0">定义<span class="_ _8"> </span><span class="ff3 sc0 ls3 ws7">2 </span><span class="sc0 ls0">设</span></div><div class="c x73 yd3 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x84 h27 yd4 ff2 fs2 fc0 sc0 ls0 ws0">为<span class="_ _2f"> </span><span class="ff4 fs17">n<span class="_ _20"> </span></span>维空间中的一个凸集，</div><div class="c x58 yd3 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x85 h6 yd4 ff2 fs2 fc0 sc0 ls0 ws0">中的点</div><div class="c x86 yd5 w5 h1e"><div class="t m0 x0 h27 y57 ff4 fs17 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 x87 h6 yd4 ff2 fs2 fc0 sc0 ls0 ws0">被称为</div><div class="c x88 yd3 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x5e h6 yd4 ff2 fs2 fc0 sc0 ls0 ws0">的一个极点，若不</div><div class="t m0 x4 h6 yd6 ff2 fs2 fc0 sc0 ls0 ws0">存在</div><div class="t m0 x89 h47 yd7 ff4 fs25 fc0 sc0 ls0 ws0">R<span class="_ _55"></span>x<span class="_ _1d"></span>x<span class="_ _6e"> </span><span class="ff5">∈</span></div><div class="t m0 x8a h48 yd8 ff1 fs26 fc0 sc0 ls0 ws0">2<span class="_ _6f"></span>1</div><div class="t m0 x17 h43 yd7 ff2 fs25 fc0 sc0 ls0 ws0">、<span class="_ _56"> </span><span class="fs2">及<span class="_ _70"> </span><span class="ff1 fs12">)<span class="_ _47"></span>1<span class="_ _48"></span>,<span class="_ _46"></span>0<span class="_ _69"></span>(<span class="_ _45"></span><span class="ff5">∈</span></span></span></div><div class="c x84 yd9 w9 h44"><div class="t m2 x0 h46 yda ff5 fs24 fc0 sc0 ls0 ws0">λ</div></div><div class="t m0 x23 h6 yd7 ff2 fs2 fc0 sc0 ls0 ws0">，使得</div><div class="t m0 x8b h41 yd8 ff1 fs20 fc0 sc0 ls0 ws0">2<span class="_ _6d"></span>1</div><div class="t m0 x4d h40 yd7 ff1 fs12 fc0 sc0 ls0 ws0">)<span class="_ _5a"></span>1<span class="_ _47"></span>(<span class="_ _5e"> </span><span class="ff4 fs21">x<span class="_ _30"></span>x<span class="_ _55"></span>x</span></div><div class="t m2 x8c h46 yd7 ff5 fs24 fc0 sc0 ls0 ws0">λ<span class="_ _16"></span>λ</div><div class="t m0 x8d h49 yd7 ff5 fs12 fc0 sc0 ls0 ws0">−<span class="_ _1e"></span>+<span class="_ _71"></span>=<span class="_ _72"> </span><span class="ff2 fs2">。<span class="ff1"> </span></span></div><div class="t m0 x67 h5 ydb ff2 fs2 fc0 sc0 ls0 ws0">定义<span class="_ _2"> </span><span class="ff1 ls3">1 <span class="_"> </span></span>说明凸集中任意两点的连线必在此凸集中；<span class="_ _d"></span>而定义<span class="_ _2"> </span><span class="ff1 ls8">2 <span class="_"> </span></span>说明，<span class="_ _d"></span>若</div><div class="c x8e ydc wa h4a"><div class="t m0 x0 h42 y57 ff4 fs22 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 x8f h6 ydd ff2 fs2 fc0 sc0 ls0 ws0">是凸集</div><div class="c x69 yde w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x4 h6 ydf ff2 fs2 fc0 sc0 ls11 ws0">的一个极点，则</div><div class="c x90 ye0 w5 h1e"><div class="t m0 x0 h27 y57 ff4 fs17 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 x91 h6 ydf ff2 fs2 fc0 sc0 ls11 ws0">不能位于</div><div class="c x23 ye1 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x2e h6 ydf ff2 fs2 fc0 sc0 ls11 ws0">中任意两点的连线上。不难证明，多胞形必为凸集。同</div><div class="t m0 x4 h6 ye2 ff2 fs2 fc0 sc0 ls0 ws0">样也不难证明，二维空间中可行域</div><div class="c x92 ye3 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x93 h6 ye4 ff2 fs2 fc0 sc0 ls0 ws0">的顶点均为</div><div class="c x4f ye3 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x94 h6 ye4 ff2 fs2 fc0 sc0 ls0 ws0">的极点（</div><div class="c x95 ye3 w3 hb"><div class="t m0 x0 h40 y17 ff4 fs21 fc0 sc0 ls0 ws0">R</div></div><div class="t m0 x96 h5 ye4 ff2 fs2 fc0 sc0 ls0 ws0">也没有其它的极点）<span class="_ _57"></span>。<span class="ff1"> </span></div><div class="t m0 x67 h5 ye5 ff1 fs2 fc0 sc0 lsa ws0">1.5 <span class="_"> </span><span class="ff2 ls0">求解线性规划的<span class="_ _1"> </span></span><span class="lse">Matlab<span class="_"> </span><span class="ff2 ls0">解法<span class="ff1"> </span></span></span></div><div class="t m0 x67 h6 ye6 ff2 fs2 fc0 sc0 lsf ws0">单纯形法是求解线性规划问题的最常用、最有效的算法之<span class="_ _1a"></span>一。这里我们就不介绍</div><div class="t m0 x4 h5 ye7 ff2 fs2 fc0 sc0 ls0 ws0">单纯形法，<span class="_ _2a"></span>有兴趣的读者可以参看其它线性规划书籍。<span class="_ _f"></span>下面我们介绍线性规划的<span class="_ _2"> </span><span class="ff1 ls18">Matlab</span></div><div class="t m0 x4 h5 ye8 ff2 fs2 fc0 sc0 ls0 ws0">解法。<span class="ff1"> </span></div><div class="t m0 x5 h5 ye9 ff1 fs2 fc0 sc0 lsa ws0">Matlab<span class="_"> </span><span class="ff2 ls0">中线性规划的标准型为<span class="ff1"> </span></span></div><div class="t m0 x97 h40 yea ff4 fs21 fc0 sc0 ls0 ws0">x<span class="_ _27"></span>c</div><div class="t m0 x98 h40 yeb ff4 fs21 fc0 sc0 ls0 ws0">x</div><div class="t m0 x99 h21 yec ff4 fs14 fc0 sc0 ls0 ws0">T</div><div class="t m0 x2b h43 yea ff1 fs12 fc0 sc0 ls0 ws0"> <span class="_ _28"></span>min</div><div class="t m0 x9a h5 yed ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h5 yee ff1 fs2 fc0 sc0 ls10 ws0"> <span class="_ _24"></span> s<span class="_ _2a"></span>.<span class="_ _2a"></span>t<span class="_ _0"></span>.<span class="_ _2a"></span> </div><div class="t m0 x18 h4b yef ff5 fsc fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h4b yf0 ff5 fsc fc0 sc0 ls0 ws0">⎩</div><div class="t m0 x18 h4b yf1 ff5 fsc fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x18 h4b yf2 ff5 fsc fc0 sc0 ls0 ws0">⎨</div><div class="t m0 x18 h4b yf3 ff5 fsc fc0 sc0 ls0 ws0">⎧</div><div class="t m0 x2a h4b yf4 ff5 fsc fc0 sc0 ls0 ws0">≤<span class="_ _2b"></span>≤</div><div class="t m0 x1b h4b yf5 ff5 fsc fc0 sc0 ls0 ws0">=<span class="_ _21"></span>⋅</div><div class="t m0 x2b h4b yf6 ff5 fsc fc0 sc0 ls0 ws0">≤</div><div class="t m0 x2c h27 yf7 ff4 fs17 fc0 sc0 ls0 ws0">ub<span class="_ _19"></span>x<span class="_ _2c"></span>lb</div><div class="t m0 x2d h27 yf8 ff4 fs17 fc0 sc0 ls0 ws0">beq<span class="_ _2d"></span>x<span class="_ _2e"></span>Aeq</div><div class="t m0 x2e h27 yf9 ff4 fs17 fc0 sc0 ls0 ws0">b<span class="_ _14"></span>Ax</div><div class="t m0 xd h5 yfa ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h5 yfb ff2 fs2 fc0 sc0 ls0 ws0">基本函数形式为<span class="_ _2"> </span><span class="ff1 ls19">linprog(c,A,b)</span>，<span class="_ _d"></span>它的返回值是向量</div><div class="c x9b yfc w5 h1e"><div class="t m0 x0 h27 y57 ff4 fs17 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 x9c h6 yfd ff2 fs2 fc0 sc0 ls0 ws0">的值。<span class="_ _d"></span>还有其它的一些函数调用形</div><div class="t m0 x4 h5 yfe ff2 fs2 fc0 sc0 ls0 ws0">式（在<span class="ff1 ls1a ws8"> Matlab </span>指令窗运行<span class="ff1 ls1b ws9"> he<span class="_ _24"></span>lp <span class="_ _2a"></span>linprog <span class="ff2 ls0 ws0">可以看到所有的函数调用形式）<span class="_ _23"></span><span class="ls1c">，如<span class="_ _1a"></span>：<span class="ff1 ls0"> </span></span></span></span></div><div class="t m0 x17 h5 yff ff1 fs2 fc0 sc0 ls1d ws0">[x,fval]=linpr<span class="_ _24"></span>og(c,A,b,Aeq,beq<span class="_ _24"></span>,LB,UB,X</div><div class="t m0 x9d h4c y100 ff1 fs14 fc0 sc0 ls0 ws0">0</div><div class="t m0 x9e h5 y101 ff1 fs2 fc0 sc0 ls1e ws0">,OPTIONS) </div><div class="t m0 x4 h5 y102 ff2 fs2 fc0 sc0 ls0 ws0">这里<span class="_ _2"> </span><span class="ff1 lsc">fval<span class="_"> </span></span>返回目标函数的值，<span class="_ _5"></span><span class="ff1 ls1f">LB<span class="_"> </span><span class="ff2 ls0">和<span class="_ _2"> </span></span><span class="ls20">UB<span class="_"> </span><span class="ff2 ls0">分别是变量</span></span></span></div><div class="c x94 y103 w5 h1e"><div class="t m0 x0 h27 yda ff4 fs17 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 x9f h6 y104 ff2 fs2 fc0 sc0 ls0 ws0">的下界和上界，</div><div class="t m0 xa0 h41 y105 ff1 fs20 fc0 sc0 ls0 ws0">0</div><div class="t m0 xa1 h40 y104 ff4 fs21 fc0 sc0 ls0 ws0">x<span class="_ _11"> </span><span class="ff2 fs2">是</span></div><div class="c xa2 y103 w5 h1e"><div class="t m0 x0 h27 yda ff4 fs17 fc0 sc0 ls0 ws0">x</div></div><div class="t m0 xa3 h6 y104 ff2 fs2 fc0 sc0 ls0 ws0">的初始值，</div><div class="t m0 x4 h5 y106 ff1 fs2 fc0 sc0 ls1e ws0">OPTIONS<span class="_"> </span><span class="ff2 ls0">是控制参数。</span><span class="lsb"> </span></div><div class="t m0 x67 h5 y107 ff2 fs2 fc0 sc0 ls0 ws0">例<span class="_ _2"> </span><span class="ff1 ls3 ws1">2 </span>求解下列线性规划问题<span class="ff1"> </span></div><div class="t m0 x67 h5 y108 ff1 fs2 fc0 sc0 lsb ws0"> <span class="_ _2a"></span> </div><div class="t m0 x12 h41 y109 ff1 fs20 fc0 sc0 ls0 ws0">3<span class="_ _18"></span>2<span class="_ _b"></span>1</div><div class="t m0 xa4 h40 y10a ff1 fs12 fc0 sc0 ls0 ws0">5<span class="_ _73"></span>3<span class="_ _73"></span>2<span class="_ _74"></span>max <span class="_ _75"> </span><span class="ff4 fs21">x<span class="_ _76"></span>x<span class="_ _77"></span>x<span class="_ _55"></span>z</span></div><div class="c x2c y10b w6 h35"><div class="t m0 x0 h49 y57 ff5 fs12 fc0 sc0 ls0 ws0">−</div></div><div class="t m0 x5b h49 y10a ff5 fs12 fc0 sc0 ls0 ws0">+<span class="_ _2d"></span>=<span class="_ _78"> </span><span class="ff1 fs2"> </span></div><div class="t m0 xa5 h5 y10c ff1 fs2 fc0 sc0 lsd ws4">s.t. </div><div class="t m0 x2b h43 y10d ff1 fs12 fc0 sc0 ls0 ws0">7</div><div class="t m0 xa6 h41 y10e ff1 fs20 fc0 sc0 ls0 ws0">3<span class="_ _1d"></span>2<span class="_ _2b"></span>1</div><div class="t m0 x21 h40 y10d ff5 fs12 fc0 sc0 ls0 ws0">=<span class="_ _79"></span>+<span class="_ _32"></span>+<span class="_ _7a"> </span><span class="ff4 fs21">x<span class="_ _2c"></span>x<span class="_ _33"></span>x<span class="_ _7b"> </span><span class="ff1 fs2"> </span></span></div><div class="t m0 xa7 h5 y10f ff1 fs2 fc0 sc0 ls10 ws0"> <span class="_ _20"> </span> </div><div class="t m0 x99 h43 y110 ff1 fs12 fc0 sc0 ls0 ws0">10<span class="_ _1c"></span>5<span class="_ _18"></span>2</div><div class="t m0 x77 h41 y111 ff1 fs20 fc0 sc0 ls0 ws0">3<span class="_ _1d"></span>2<span class="_ _55"></span>1</div><div class="t m0 x2b h40 y110 ff5 fs12 fc0 sc0 ls0 ws0">≥<span class="_ _79"></span>+<span class="_ _76"></span>−<span class="_ _7c"> </span><span class="ff4 fs21">x<span class="_ _2c"></span>x<span class="_ _2e"></span>x<span class="_ _7d"> </span><span class="ff1 fs2"> </span></span></div><div class="t m0 xa7 h5 y112 ff1 fs2 fc0 sc0 ls10 ws0"> <span class="_ _20"> </span> </div><div class="t m0 xb h43 y113 ff1 fs12 fc0 sc0 ls0 ws0">12<span class="_ _1c"></span>3</div><div class="t m0 x6b h41 y114 ff1 fs20 fc0 sc0 ls0 ws0">3<span class="_ _1d"></span>2<span class="_ _55"></span>1</div><div class="t m0 xa8 h49 y113 ff5 fs12 fc0 sc0 ls0 ws0">≤<span class="_ _79"></span>+</div><div class="c x90 y115 w6 h35"><div class="t m0 x0 h49 y57 ff5 fs12 fc0 sc0 ls0 ws0">+</div></div><div class="t m0 x43 h40 y113 ff4 fs21 fc0 sc0 ls0 ws0">x<span class="_ _2c"></span>x<span class="_ _2e"></span>x<span class="_ _7d"> </span><span class="ff1 fs2"> </span></div><div class="t m0 xa7 h5 y116 ff1 fs2 fc0 sc0 ls21 ws0"> </div><div class="t m0 x24 h43 y117 ff1 fs12 fc0 sc0 ls0 ws0">0<span class="_ _77"></span>,<span class="_ _12"></span>,</div><div class="t m0 xa9 h41 y118 ff1 fs20 fc0 sc0 ls0 ws0">3<span class="_ _1f"></span>2<span class="_ _12"></span>1</div><div class="t m0 x3d h40 y117 ff5 fs12 fc0 sc0 ls0 ws0">≥<span class="_ _4a"></span><span class="ff4 fs21">x<span class="_ _5c"></span>x<span class="_ _4a"></span>x<span class="_ _7e"> </span><span class="ff1 fs2"> </span></span></div></div><div class="pi" data-data='{"ctm":[1.611639,0.000000,0.000000,1.611639,0.000000,0.000000]}'></div></div>
<div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625bbb5792dc900e622aaa18/bg4.jpg"><div class="t m0 x32 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x33 h3 y2 ff2 fs0 fc0 sc0 ls0 ws0">-4- </div><div class="t m0 x34 h5 y59 ff2 fs2 fc0 sc0 ls0 ws0">解<span class="ff1"> <span class="_"> </span></span>（<span class="ff1">i</span>）编写<span class="_ _2"> </span><span class="ff1">M<span class="_"> </span></span>文件<span class="ff1"> </span></div><div class="t m0 x39 h4d y119 ff8 fs27 fc0 sc0 ls22 ws0">c=[2;3;-5];<span class="fs6 ls0"> </span></div><div class="t m0 x39 h4d y11a ff8 fs27 fc0 sc0 ls22 ws0">a=[-2,5,-1;1,3,1]; b=[-10;12];<span class="fs6 ls0"> </span></div><div class="t m0 x39 h4d y11b ff8 fs27 fc0 sc0 ls22 ws0">aeq=[1,1,1];<span class="fs6 ls0"> </span></div><div class="t m0 x39 h4d y11c ff8 fs27 fc0 sc0 ls22 ws0">beq=7;<span class="fs6 ls0"> </span></div><div class="t m0 x39 h4d y11d ff8 fs27 fc0 sc0 ls22 ws0">x=linprog(-c,a,b,aeq,beq,zeros(3,1))<span class="fs6 ls0"> </span></div><div class="t m0 x39 h4d y11e ff8 fs27 fc0 sc0 ls22 ws0">value=c'*x<span class="fs6 ls0"> </span></div><div class="t m0 x34 h5 y11f ff2 fs2 fc0 sc0 ls0 ws0">（<span class="ff8 ls23">ii</span>）将<span class="ff1">M</span>文件存盘，并命名为<span class="ff1 lsa">example1.m<span class="_ _24"></span><span class="ff2 ls0">。<span class="ff1"> </span></span></span></div><div class="t m0 x34 h5 y120 ff2 fs2 fc0 sc0 ls0 ws0">（<span class="ff1 lsa">iii</span>）在<span class="ff1 ls24">Matlab</span>指令窗运行<span class="ff1 lsa">example1</span>即可得所求结果。<span class="ff1"> </span></div><div class="t m0 x34 h5 y121 ff2 fs2 fc0 sc0 ls0 ws0">例<span class="ff1">3</span> <span class="_"> </span>求解线性规划问题<span class="ff1"> </span></div><div class="t m0 xaa h41 y122 ff1 fs20 fc0 sc0 ls0 ws0">3<span class="_ _1e"></span>2<span class="_ _b"></span>1</div><div class="t m0 xab h40 y123 ff1 fs12 fc0 sc0 ls0 ws0">3<span class="_ _73"></span>2<span class="_ _6"></span> <span class="_ _28"></span>min<span class="_ _7f"> </span><span class="ff4 fs21">x<span class="_ _32"></span>x<span class="_ _77"></span>x<span class="_ _55"></span>z<span class="_ _80"> </span><span class="ff5 fs12">+</span></span></div><div class="c xac y124 w6 h35"><div class="t m0 x0 h49 y57 ff5 fs12 fc0 sc0 ls0 ws0">+</div></div><div class="t m0 xad h49 y123 ff5 fs12 fc0 sc0 ls0 ws0">=<span class="_ _81"> </span><span class="ff1 fs2"> </span></div><div class="t m0 x34 h5 y125 ff1 fs2 fc0 sc0 ls10 ws0"> </div><div class="t m0 xae h4b y126 ff5 fsc fc0 sc0 ls0 ws0">⎪</div><div class="t m0 xae h4b y127 ff5 fsc fc0 sc0 ls0 ws0">⎩</div><div class="t m0 xae h4b y128 ff5 fsc fc0 sc0 ls0 ws0">⎪</div><div class="t m0 xae h4b y129 ff5 fsc fc0 sc0 ls0 ws0">⎨</div><div class="t m0 xae h4b y12a ff5 fsc fc0 sc0 ls0 ws0">⎧</div><div class="t m0 xac h4b y12b ff5 fsc fc0 sc0 ls0 ws0">≥</div><div class="t m0 xaf h4b y12c ff5 fsc fc0 sc0 ls0 ws0">≥<span class="_ _82"></span>+</div><div class="t m0 xb0 h4b y12d ff5 fsc fc0 sc0 ls0 ws0">≥<span class="_ _4c"></span>+<span class="_ _83"></span>+</div><div class="t m0 x75 h4e y12e ff1 fs3 fc0 sc0 ls0 ws0">0<span class="_ _71"></span>,<span class="_ _4a"></span>,</div><div class="t m0 x81 h4e y12f ff1 fs3 fc0 sc0 ls0 ws0">6<span class="_ _4c"></span>2<span class="_ _76"></span>3</div><div class="t m0 x3d h4e y130 ff1 fs3 fc0 sc0 ls0 ws0">8<span class="_ _84"></span>2<span class="_ _84"></span>4</div><div class="t m0 x7 h4f y131 ff1 fs28 fc0 sc0 ls0 ws0">3<span class="_ _13"></span>2<span class="_ _4a"></span>1</div><div class="t m0 x27 h4f y132 ff1 fs28 fc0 sc0 ls0 ws0">2<span class="_ _77"></span>1</div><div class="t m0 xb1 h4f y133 ff1 fs28 fc0 sc0 ls0 ws0">3<span class="_ _15"></span>2<span class="_ _77"></span>1</div><div class="t m0 xb2 h27 y12e ff4 fs17 fc0 sc0 ls0 ws0">x<span class="_ _85"></span>x<span class="_ _21"></span>x</div><div class="t m0 xb3 h27 y134 ff4 fs17 fc0 sc0 ls0 ws0">x<span class="_ _76"></span>x</div><div class="t m0 x81 h27 y135 ff4 fs17 fc0 sc0 ls0 ws0">x<span class="_ _2d"></span>x<span class="_ _76"></span>x</div><div class="t m0 xaa h5 y125 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x34 h5 y136 ff2 fs2 fc0 sc0 ls0 ws0">解<span class="ff1 ls10"> </span>编写<span class="ff1 ls24">Matlab</span>程序如下：<span class="ff1"> </span></div><div class="t m0 x39 h6 y137 ff2 fs2 fc0 sc0 ls3 ws0">c=[2;3;1];<span class="_ _24"></span> </div><div class="t m0 x39 h6 y138 ff2 fs2 fc0 sc0 ls3 ws0">a=[1,4,2;3<span class="_ _24"></span>,2,0]; </div><div class="t m0 x39 h6 y139 ff2 fs2 fc0 sc0 ls3 ws0">b=[8;6]; </div><div class="t m0 x39 h5 y13a ff2 fs2 fc0 sc0 ls8 ws0">[x,y]=lin<span class="_ _1a"></span>prog(c,-a,-<span class="_ _1a"></span>b,[],[],zer<span class="_ _1a"></span>os(3,1))<span class="ff1 ls0"> </span></div><div class="t m0 x34 h5 y13b ff1 fs2 fc0 sc0 lsa wsa">1.6 <span class="ff2 ls0 ws0">可以转化为线性规划的问题<span class="ff1"> </span></span></div><div class="t m0 x34 h6 y13c ff2 fs2 fc0 sc0 ls0 ws0">很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如：<span class="_ _57"></span><span class="ff8"> </span></div><div class="t m0 x34 h6 y13d ff2 fs2 fc0 sc0 ls0 ws0">例<span class="ff8">4</span> <span class="_ _86"> </span><span class="ff8"> <span class="_ _e"></span><span class="ff2">规划问题为<span class="ff8"> </span></span></span></div><div class="t m0 x3c h50 y13e ff4 fs29 fc0 sc0 ls0 ws0">b<span class="_ _18"></span>Ax</div><div class="t m0 xb4 h50 y13f ff4 fs29 fc0 sc0 ls0 ws0">x<span class="_ _87"></span>x<span class="_ _5f"></span>x</div><div class="t m0 xa4 h51 y140 ff4 fs2a fc0 sc0 ls0 ws0">n</div><div class="t m0 x3e h52 y13e ff5 fs29 fc0 sc0 ls0 ws0">≤</div><div class="c x3 y141 w6 h53"><div class="t m0 x0 h52 y57 ff5 fs29 fc0 sc0 ls0 ws0">+</div></div><div class="t m0 x21 h52 y142 ff5 fs29 fc0 sc0 ls0 ws0">+<span class="_ _88"></span>+</div><div class="t m0 x40 h54 y143 ff1 fs29 fc0 sc0 ls0 ws0"> <span class="_ _77"></span> t.<span class="_ _3e"></span>s.</div><div class="t m0 x93 h54 y142 ff1 fs29 fc0 sc0 ls0 ws0">|<span class="_ _85"></span>|<span class="_ _36"></span>|<span class="_ _89"></span>|<span class="_ _8a"></span>|<span class="_ _21"></span>|<span class="_ _77"></span>min</div><div class="t m0 x18 h55 y140 ff1 fs2a fc0 sc0 ls0 ws0">2<span class="_ _83"></span>1</div><div class="t m0 x1a h56 y142 ff7 fs2b fc0 sc0 ls0 ws0">L</div><div class="t m0 x6e h57 y144 ff8 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x39 h6 y145 ff2 fs2 fc0 sc0 ls0 ws0">其中</div><div class="t m0 xb1 h58 y146 ff4 fs2c fc0 sc0 ls0 ws0">T</div><div class="t m0 x55 h58 y147 ff4 fs2c fc0 sc0 ls0 ws0">n</div><div class="t m0 xb5 h59 y145 ff4 fs2d fc0 sc0 ls0 ws0">x<span class="_ _8b"></span>x<span class="_ _32"></span>x<span class="_ _81"> </span><span class="ff1">]<span class="_ _8c"></span>[</span></div><div class="t m0 x5d h5a y148 ff1 fs2c fc0 sc0 ls0 ws0">1</div><div class="t m0 x31 h5b y145 ff7 fs2d fc0 sc0 ls0 ws0">L<span class="_ _8d"></span><span class="ff5">=<span class="_ _8e"> </span><span class="ff2 fs2">，</span></span></div><div class="c x37 y149 w2 h9"><div class="t m0 x0 h47 y14 ff4 fs25 fc0 sc0 ls0 ws0">A</div></div><div class="t m0 x6c h42 y145 ff2 fs2 fc0 sc0 ls0 ws0">和<span class="_ _3"> </span><span class="ff4 fs22">b<span class="_ _2"> </span></span>为相应维数的矩阵和向量。<span class="ff8"> </span></div><div class="t m0 x65 h6 y14a ff2 fs2 fc0 sc0 ls25 ws0">要把上面的问题变换成线性规<span class="_ _1a"></span>划问题，只要注意到事实：<span class="_ _1a"></span>对任意的</div><div class="t m0 x8e h58 y14b ff4 fs2c fc0 sc0 ls0 ws0">i</div><div class="t m0 xb6 h5c y14c ff4 fs2d fc0 sc0 ls0 ws0">x<span class="_ _8f"> </span><span class="ff2 fs2 ls26">，存在</span></div><div class="t m0 x2f h59 y14d ff1 fs2d fc0 sc0 ls0 ws0">0<span class="_ _77"></span>,<span class="_ _90"> </span><span class="ff5">></span></div><div class="t m0 x34 h58 y14e ff4 fs2c fc0 sc0 ls0 ws0">i<span class="_ _91"></span>i</div><div class="t m0 x6f h5c y14d ff4 fs2d fc0 sc0 ls0 ws0">v<span class="_ _92"></span>u<span class="_ _4f"> </span><span class="ff2 fs2">满足<span class="ff1"> </span></span></div><div class="t m0 x65 h57 y14f ff8 fs2 fc0 sc0 ls27 ws0"> </div><div class="t m0 x46 h58 y150 ff4 fs2c fc0 sc0 ls0 ws0">i<span class="_ _44"></span>i<span class="_ _2b"></span>i</div><div class="t m0 x89 h5c y151 ff4 fs2d fc0 sc0 ls0 ws0">v<span class="_ _6"></span>u<span class="_ _32"></span>x<span class="_ _93"> </span><span class="ff5">−<span class="_ _79"></span>=<span class="_ _67"> </span><span class="ff2 fs2">，</span></span></div><div class="t m0 x2a h58 y150 ff4 fs2c fc0 sc0 ls0 ws0">i<span class="_ _94"></span>i<span class="_ _6b"></span>i</div><div class="t m0 xb7 h59 y151 ff4 fs2d fc0 sc0 ls0 ws0">v<span class="_ _2c"></span>u<span class="_ _19"></span>x<span class="_ _95"> </span><span class="ff5">+<span class="_ _79"></span>=<span class="_ _46"></span><span class="ff1">|<span class="_ _13"></span>|<span class="_ _96"> </span><span class="ff8 fs2"> </span></span></span></div><div class="t m0 x39 h6 y152 ff2 fs2 fc0 sc0 ls0 ws0">事实上，我们只要取</div><div class="t m0 xb8 h5d y153 ff1 fs2e fc0 sc0 ls0 ws0">2</div><div class="t m0 x19 h5d y154 ff1 fs2e fc0 sc0 ls0 ws0">|<span class="_ _92"></span>|</div><div class="t m0 x25 h5e y155 ff4 fs2f fc0 sc0 ls0 ws0">i<span class="_ _1e"></span>i</div><div class="t m0 x84 h5e y156 ff4 fs2f fc0 sc0 ls0 ws0">i</div><div class="t m0 x2b h5f y157 ff4 fs2e fc0 sc0 ls0 ws0">x<span class="_ _55"></span>x</div><div class="t m0 x74 h5f y158 ff4 fs2e fc0 sc0 ls0 ws0">u</div><div class="t m0 x24 h60 y157 ff5 fs2e fc0 sc0 ls0 ws0">+</div><div class="t m0 xb9 h60 y158 ff5 fs2e fc0 sc0 ls0 ws0">=</div><div class="t m0 xba h6 y159 ff2 fs2 fc0 sc0 ls0 ws0">，</div><div class="t m0 xbb h5d y153 ff1 fs2e fc0 sc0 ls0 ws0">2</div><div class="t m0 xbb h5d y154 ff1 fs2e fc0 sc0 ls0 ws0">|<span class="_ _92"></span>|</div><div class="t m0 xbc h5e y155 ff4 fs2f fc0 sc0 ls0 ws0">i<span class="_ _1e"></span>i</div><div class="t m0 x6d h5e y156 ff4 fs2f fc0 sc0 ls0 ws0">i</div><div class="t m0 x9e h5f y157 ff4 fs2e fc0 sc0 ls0 ws0">x<span class="_ _64"></span>x</div><div class="t m0 x2d h5f y158 ff4 fs2e fc0 sc0 ls0 ws0">v</div><div class="c xbd y15a w6 h53"><div class="t m0 x0 h60 y57 ff5 fs2e fc0 sc0 ls0 ws0">−</div></div><div class="t m0 xbe h60 y159 ff5 fs2e fc0 sc0 ls0 ws0">=<span class="_ _97"> </span><span class="ff2 fs2">就可以满足上面的条件。<span class="ff8"> </span></span></div><div class="t m0 x65 h6 y15b ff2 fs2 fc0 sc0 ls11 ws0">这样，记</div><div class="t m0 x20 h61 y15c ff4 fs30 fc0 sc0 ls0 ws0">T</div><div class="t m0 xa8 h61 y15d ff4 fs30 fc0 sc0 ls0 ws0">n</div><div class="t m0 x98 h62 y15e ff4 fs31 fc0 sc0 ls0 ws0">u<span class="_ _98"></span>u<span class="_ _1b"></span>u<span class="_ _81"> </span><span class="ff1">]<span class="_ _8c"></span>[</span></div><div class="t m0 x74 h63 y15f ff1 fs30 fc0 sc0 ls0 ws0">1</div><div class="t m0 xb0 h64 y15e ff7 fs31 fc0 sc0 ls0 ws0">L<span class="_ _8d"></span><span class="ff5">=<span class="_ _99"> </span><span class="ff2 fs2">，</span></span></div><div class="t m0 x94 h61 y15c ff4 fs30 fc0 sc0 ls0 ws0">T</div><div class="t m0 x4f h61 y15d ff4 fs30 fc0 sc0 ls0 ws0">n</div><div class="t m0 x8d h62 y15e ff4 fs31 fc0 sc0 ls0 ws0">v<span class="_ _74"></span>v<span class="_ _5a"></span>v<span class="_ _9a"> </span><span class="ff1">]<span class="_ _9b"></span>[</span></div><div class="t m0 xbf h63 y15f ff1 fs30 fc0 sc0 ls0 ws0">1</div><div class="t m0 xc0 h64 y15e ff7 fs31 fc0 sc0 ls0 ws0">L<span class="_ _42"></span><span class="ff5">=<span class="_ _9c"> </span><span class="ff2 fs2 ls11">，从而我们可以把上面的问题</span></span></div><div class="t m0 x39 h6 y160 ff2 fs2 fc0 sc0 ls0 ws0">变成<span class="ff8"> </span></div><div class="t m0 x65 h57 y161 ff8 fs2 fc0 sc0 ls27 ws0"> </div><div class="t m0 x44 h3c y162 ff5 fs1f fc0 sc0 ls0 ws0">∑</div><div class="t m0 xc1 h3d y163 ff5 fs20 fc0 sc0 ls0 ws0">=</div><div class="t m0 xc2 h64 y164 ff5 fs31 fc0 sc0 ls0 ws0">+</div><div class="t m0 xc1 h5e y165 ff4 fs2f fc0 sc0 ls0 ws0">n</div><div class="t m0 x27 h5e y166 ff4 fs2f fc0 sc0 ls0 ws0">i</div><div class="t m0 x18 h5e y167 ff4 fs2f fc0 sc0 ls0 ws0">i<span class="_ _94"></span>i</div><div class="t m0 x28 h65 y164 ff4 fs31 fc0 sc0 ls0 ws0">v<span class="_ _2c"></span>u</div><div class="t m0 x46 h5a y163 ff1 fs2c fc0 sc0 ls0 ws0">1</div><div class="t m0 x43 h66 y164 ff1 fs21 fc0 sc0 ls0 ws0">)<span class="_ _9d"></span>(<span class="_ _9e"></span>min<span class="_ _9f"> </span><span class="ff8 fs2"> </span></div><div class="t m0 x65 h57 y168 ff8 fs2 fc0 sc0 ls27 ws0"> </div><div class="t m0 xb2 h64 y169 ff5 fs31 fc0 sc0 ls0 ws0">⎩</div><div class="t m0 xb2 h64 y16a ff5 fs31 fc0 sc0 ls0 ws0">⎨</div><div class="t m0 xb2 h64 y16b ff5 fs31 fc0 sc0 ls0 ws0">⎧</div><div class="t m0 x74 h64 y16c ff5 fs31 fc0 sc0 ls0 ws0">≥</div><div class="t m0 x3d h64 y16d ff5 fs31 fc0 sc0 ls0 ws0">≤<span class="_ _1b"></span>−</div><div class="t m0 x3e h66 y16e ff1 fs21 fc0 sc0 ls0 ws0">0<span class="_ _19"></span>,</div><div class="t m0 x57 h66 y16f ff1 fs21 fc0 sc0 ls0 ws0">)<span class="_ _a0"></span>(</div><div class="t m0 x72 h66 y170 ff1 fs21 fc0 sc0 ls0 ws0"> <span class="_ _5d"></span> t.<span class="_ _8a"></span>s.</div><div class="t m0 xaf h65 y16e ff4 fs31 fc0 sc0 ls0 ws0">v<span class="_ _3e"></span>u</div><div class="t m0 x29 h65 y171 ff4 fs31 fc0 sc0 ls0 ws0">b<span class="_ _1b"></span>v<span class="_ _34"></span>u<span class="_ _27"></span>A</div><div class="t m0 x77 h57 y172 ff8 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x65 h5 y173 ff2 fs2 fc0 sc0 ls0 ws0">例<span class="_ _2"> </span><span class="ff1 ls3 ws1">5 </span></div><div class="t m0 x28 h67 y174 ff1 fs32 fc0 sc0 ls0 ws0">|}<span class="_ _a1"></span>|<span class="_ _6b"></span>max<span class="_ _1e"></span>{<span class="_ _6f"></span>min</div><div class="t m0 xb0 h68 y175 ff4 fs33 fc0 sc0 ls0 ws0">i</div><div class="t m0 x4b h68 y176 ff4 fs33 fc0 sc0 ls0 ws0">y</div><div class="t m0 x72 h68 y177 ff4 fs33 fc0 sc0 ls0 ws0">x</div><div class="t m0 x56 h69 y178 ff4 fs34 fc0 sc0 ls0 ws0">i</div><div class="t m0 x40 h69 y179 ff4 fs34 fc0 sc0 ls0 ws0">i</div><div class="c x3e y17a wb h10"><div class="t m2 x0 h6a y21 ff5 fs35 fc0 sc0 ls0 ws0">ε</div></div><div class="t m0 x43 h5 y174 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x39 h6 y17b ff2 fs2 fc0 sc0 ls0 ws0">其中</div><div class="t m0 xb3 h68 y17c ff4 fs33 fc0 sc0 ls0 ws0">i<span class="_ _a1"></span>i<span class="_ _2b"></span>i</div><div class="t m0 x9 h65 y17d ff4 fs31 fc0 sc0 ls0 ws0">y<span class="_ _5a"></span>x<span class="_ _a2"> </span><span class="ff5">−<span class="_ _1b"></span>=</span></div><div class="c xc3 y17e wb h35"><div class="t m2 x0 h46 y57 ff5 fs24 fc0 sc0 ls0 ws0">ε</div></div><div class="t m0 x44 h5 y17d ff2 fs2 fc0 sc0 ls0 ws0">。<span class="ff1"> </span></div><div class="t m0 x65 h6 y17f ff2 fs2 fc0 sc0 ls0 ws0">对于这个问题，如果我们取</div><div class="t m0 xc4 h6b y180 ff1 fs36 fc0 sc0 ls0 ws0">|<span class="_ _4a"></span>|<span class="_ _6b"></span>max</div><div class="t m0 x2a h6c y181 ff1 fs37 fc0 sc0 ls0 ws0">0<span class="_ _a3"> </span><span class="ff4">i</span></div><div class="t m0 x93 h6d y182 ff4 fs37 fc0 sc0 ls0 ws0">y</div><div class="t m0 xc5 h6e y183 ff4 fs38 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb7 h6f y180 ff4 fs36 fc0 sc0 ls0 ws0">x</div><div class="c xc6 y184 wb h35"><div class="t m3 x0 h70 y57 ff5 fs39 fc0 sc0 ls0 ws0">ε</div></div><div class="c x9a y184 w6 h35"><div class="t m0 x0 h71 y57 ff5 fs36 fc0 sc0 ls0 ws0">=</div></div><div class="t m0 xc7 h5 y180 ff2 fs2 fc0 sc0 ls0 ws0">，这样，上面的问题就变换成<span class="ff1"> </span></div></div><div class="pi" data-data='{"ctm":[1.611639,0.000000,0.000000,1.611639,0.000000,0.000000]}'></div></div>
<div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/625bbb5792dc900e622aaa18/bg5.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h3 y2 ff2 fs0 fc0 sc0 ls0 ws0">-5- </div><div class="t m0 x67 h5 y185 ff1 fs2 fc0 sc0 ls10 ws0"> </div><div class="t m0 xb1 h6c y186 ff1 fs37 fc0 sc0 ls0 ws0">0</div><div class="t m0 xc8 h65 y185 ff1 fs21 fc0 sc0 ls0 ws0">min<span class="_ _a4"> </span><span class="ff4 fs31">x<span class="_ _a5"> </span></span><span class="fs2"> </span></div><div class="t m0 x67 h5 y187 ff1 fs2 fc0 sc0 ls10 ws0"> </div><div class="t m0 xbc h6c y188 ff1 fs37 fc0 sc0 ls0 ws0">0<span class="_ _a6"></span>0<span class="_ _2c"></span>1<span class="_ _1e"></span>1</div><div class="t m0 x1f h65 y189 ff1 fs21 fc0 sc0 ls0 ws0">,<span class="_ _13"></span>,<span class="_ _a7"></span> <span class="_ _6"></span> t.<span class="_ _3e"></span>s.<span class="_ _a8"> </span><span class="ff4 fs31">x<span class="_ _55"></span>y<span class="_ _19"></span>x<span class="_ _36"></span>x<span class="_ _79"></span>y<span class="_ _5a"></span>x</span></div><div class="t m0 xc9 h6d y188 ff4 fs37 fc0 sc0 ls0 ws0">n<span class="_ _5a"></span>n</div><div class="c x3b y18a w6 h35"><div class="t m0 x0 h64 y57 ff5 fs31 fc0 sc0 ls0 ws0">≤</div></div><div class="c xca y18a w6 h35"><div class="t m0 x0 h64 y57 ff5 fs31 fc0 sc0 ls0 ws0">−</div></div><div class="t m0 x21 h64 y189 ff5 fs31 fc0 sc0 ls0 ws0">≤<span class="_ _55"></span>−<span class="_ _a9"> </span><span class="ff7">L<span class="_ _aa"> </span><span class="ff1 fs2"> </span></span></div><div class="t m0 x4 h5 y18b ff2 fs2 fc0 sc0 ls0 ws0">此即我们通常的线性规划问题。<span class="ff1"> </span></div><div class="t m0 x4 h5 y18c ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h5 y18d ff2 fs2 fc0 sc0 ls0 ws0">§<span class="ff1 ls3 ws1">2 </span>运输问题<span class="ff1">(</span>产销平衡<span class="ff1 ls28">) </span></div><div class="t m0 x67 h5 y18e ff2 fs2 fc0 sc0 ls0 ws0">例<span class="_ _2"> </span><span class="ff1 ls3 ws1">6 </span>某商品有</div><div class="t m0 xb0 h6f y18f ff4 fs36 fc0 sc0 ls0 ws0">m<span class="_ _2"> </span><span class="ff2 fs2">个产地、<span class="_ _2f"> </span></span>n<span class="_ _20"> </span><span class="ff2 fs2">个销地，各产地的产量分别为</span></div><div class="t m0 xcb h6d y190 ff4 fs37 fc0 sc0 ls0 ws0">m</div><div class="t m0 xcc h65 y18f ff4 fs31 fc0 sc0 ls0 ws0">a<span class="_ _83"></span>a<span class="_ _a"> </span><span class="ff1 fs21">,<span class="_ _4a"></span>,</span></div><div class="t m0 xcd h6c y190 ff1 fs37 fc0 sc0 ls0 ws0">1</div><div class="t m0 xce h72 y18f ff7 fs31 fc0 sc0 ls0 ws0">L<span class="_ _ab"> </span><span class="ff2 fs2">，各销地的</span></div><div class="t m0 x4 h6 y191 ff2 fs2 fc0 sc0 ls0 ws0">需求量分别为</div><div class="t m0 x57 h6d y192 ff4 fs37 fc0 sc0 ls0 ws0">n</div><div class="t m0 x83 h65 y193 ff4 fs31 fc0 sc0 ls0 ws0">b<span class="_ _2d"></span>b<span class="_ _ab"> </span><span class="ff1 fs21">,<span class="_ _4a"></span>,</span></div><div class="t m0 x45 h6c y192 ff1 fs37 fc0 sc0 ls0 ws0">1</div><div class="t m0 x90 h65 y193 ff7 fs31 fc0 sc0 ls0 ws0">L<span class="_ _ac"> </span><span class="ff2 fs2">。<span class="_ _26"></span>若该商品由<span class="_ _3"> </span><span class="ff4 fs31">i<span class="_ _1"> </span></span>产地运到</span></div><div class="c xcf y194 wc h73"><div class="t m0 xd0 h65 y57 ff4 fs31 fc0 sc0 ls0 ws0">j</div></div><div class="t m0 x4f h6 y193 ff2 fs2 fc0 sc0 ls0 ws0">销地的单位运价为</div><div class="t m0 xd1 h6d y192 ff4 fs37 fc0 sc0 ls0 ws0">ij</div><div class="t m0 xd2 h65 y193 ff4 fs31 fc0 sc0 ls0 ws0">c<span class="_ _ad"> </span><span class="ff2 fs2">，<span class="_ _26"></span>问应该如何调</span></div><div class="t m0 x4 h5 y195 ff2 fs2 fc0 sc0 ls0 ws0">运才能使总运费最省？<span class="ff1"> </span></div><div class="t m0 x67 h6 y196 ff2 fs2 fc0 sc0 ls0 ws0">解：引入变量</div><div class="t m0 xb9 h6d y197 ff4 fs37 fc0 sc0 ls0 ws0">ij</div><div class="t m0 xb1 h65 y198 ff4 fs31 fc0 sc0 ls0 ws0">x<span class="_ _ad"> </span><span class="ff2 fs2">，其取值为由</span></div><div class="t m0 x50 h47 y199 ff4 fs25 fc0 sc0 ls0 ws0">i</div><div class="t m0 xbe h6 y198 ff2 fs2 fc0 sc0 ls0 ws0">产地运往</div><div class="c x58 y19a wc h73"><div class="t m0 xd0 h65 y57 ff4 fs31 fc0 sc0 ls0 ws0">j</div></div><div class="t m0 xd3 h5 y198 ff2 fs2 fc0 sc0 ls0 ws0">销地的该商品数量，数学模型为<span class="ff1"> </span></div><div class="t m0 x67 h5 y19b ff1 fs2 fc0 sc0 ls10 ws0"> </div><div class="t m0 x90 h23 y19c ff5 fs15 fc0 sc0 ls29 ws0">∑∑</div><div class="t m0 xd4 h3d y19d ff5 fs20 fc0 sc0 ls2a ws0">==</div><div class="t m0 x55 h6d y19e ff4 fs37 fc0 sc0 ls0 ws0">m</div><div class="t m0 x73 h6d y19f ff4 fs37 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb9 h6d y19e ff4 fs37 fc0 sc0 ls0 ws0">n</div><div class="t m0 x83 h6d y19f ff4 fs37 fc0 sc0 ls0 ws0">j</div><div class="t m0 x6c h6d y1a0 ff4 fs37 fc0 sc0 ls0 ws0">ij<span class="_ _ae"></span>ij</div><div class="t m0 x29 h6f y1a1 ff4 fs36 fc0 sc0 ls0 ws0">x<span class="_ _38"></span>c</div><div class="t m0 x91 h6c y19d ff1 fs37 fc0 sc0 ls2b ws0">11</div><div class="t m0 xd5 h6b y1a1 ff1 fs36 fc0 sc0 ls0 ws0">min<span class="_ _17"> </span><span class="fs2 ls10"> </span></div><div class="t m0 x17 h5 y1a2 ff1 fs2 fc0 sc0 lsd ws4">s.t. </div><div class="t m0 x82 h74 y1a3 ff5 fs3a fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x82 h74 y1a4 ff5 fs3a fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x82 h74 y1a5 ff5 fs3a fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x82 h74 y1a6 ff5 fs3a fc0 sc0 ls0 ws0">⎩</div><div class="t m0 x82 h74 y1a7 ff5 fs3a fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x82 h74 y1a8 ff5 fs3a fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x82 h74 y1a9 ff5 fs3a fc0 sc0 ls0 ws0">⎪</div><div class="t m0 x82 h74 y1aa ff5 fs3a fc0 sc0 ls0 ws0">⎨</div><div class="t m0 x82 h74 y1ab ff5 fs3a fc0 sc0 ls0 ws0">⎧</div><div class="t m0 x56 h74 y1ac ff5 fs3a fc0 sc0 ls0 ws0">≥</div><div class="t m0 x59 h74 y1ad ff5 fs3a fc0 sc0 ls0 ws0">=<span class="_ _9e"></span>=</div><div class="t m0 x23 h74 y1ae ff5 fs3a fc0 sc0 ls0 ws0">=<span class="_ _8d"></span>=</div><div class="t m0 x7 h75 y1af ff5 fs3b fc0 sc0 ls0 ws0">∑</div><div class="t m0 x7 h75 y1b0 ff5 fs3b fc0 sc0 ls0 ws0">∑</div><div class="t m0 x47 h76 y1b1 ff5 fs3c fc0 sc0 ls0 ws0">=</div><div class="t m0 xc1 h76 y1b2 ff5 fs3c fc0 sc0 ls0 ws0">=</div><div class="t m0 x91 h77 y1b3 ff1 fs3a fc0 sc0 ls0 ws0">0</div><div class="t m0 xbe h77 y1b4 ff1 fs3a fc0 sc0 ls0 ws0">,<span class="_ _4a"></span>,<span class="_ _46"></span>2<span class="_ _46"></span>,<span class="_ _48"></span>1<span class="_ _31"></span>,</div><div class="t m0 x1f h77 y1b5 ff1 fs3a fc0 sc0 ls0 ws0">,<span class="_ _4a"></span>,<span class="_ _48"></span>1<span class="_ _2d"></span>,</div><div class="t m0 xd6 h78 y1b1 ff1 fs3c fc0 sc0 ls0 ws0">1</div><div class="t m0 x46 h78 y1b2 ff1 fs3c fc0 sc0 ls0 ws0">1</div><div class="t m0 x45 h79 y1b6 ff4 fs3c fc0 sc0 ls0 ws0">ij</div><div class="t m0 x89 h79 y1b7 ff4 fs3c fc0 sc0 ls0 ws0">m</div><div class="t m0 x44 h79 y1b1 ff4 fs3c fc0 sc0 ls0 ws0">i</div><div class="t m0 x3d h79 y1b8 ff4 fs3c fc0 sc0 ls0 ws0">j<span class="_ _6b"></span>ij</div><div class="t m0 x47 h79 y1b9 ff4 fs3c fc0 sc0 ls0 ws0">n</div><div class="t m0 x27 h79 y1b2 ff4 fs3c fc0 sc0 ls0 ws0">j</div><div class="t m0 x3d h79 y1ba ff4 fs3c fc0 sc0 ls0 ws0">i<span class="_ _1d"></span>ij</div><div class="t m0 x7 h7a y1b3 ff4 fs3a fc0 sc0 ls0 ws0">x</div><div class="t m0 x12 h7a y1b4 ff4 fs3a fc0 sc0 ls0 ws0">n<span class="_ _41"></span>j<span class="_ _55"></span>b<span class="_ _79"></span>x</div><div class="t m0 x13 h7a y1b5 ff4 fs3a fc0 sc0 ls0 ws0">m<span class="_ _9e"></span>i<span class="_ _1e"></span>a<span class="_ _1b"></span>x</div><div class="t m0 x1f h7b y1b4 ff7 fs3a fc0 sc0 ls0 ws0">L</div><div class="t m0 xba h7b y1b5 ff7 fs3a fc0 sc0 ls0 ws0">L</div><div class="t m0 xc h5 y1bb ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h5 y1bc ff2 fs2 fc0 sc0 ls0 ws0">显然是一个线性规划问题，当然可以用单纯形法求解。<span class="ff1"> </span></div><div class="t m0 x67 h5 y1bd ff2 fs2 fc0 sc0 ls0 ws0">对产销平衡的运输问题，由于有以下关系式存在：<span class="ff1"> </span></div><div class="t m0 xd7 h7c y1be ff5 fs3d fc0 sc0 ls0 ws0">∑<span class="_ _af"></span><span class="ls2c">∑∑<span class="_ _b0"></span>∑<span class="_ _b1"></span><span class="ls2d">∑∑</span></span></div><div class="t m0 x4f h7d y1bf ff5 fs3e fc0 sc0 ls0 ws0">=<span class="_ _b2"></span><span class="ls2e">==<span class="_ _b3"></span>=<span class="_ _b1"></span><span class="ls2f">==</span></span></div><div class="t m0 x9e h7e y1c0 ff5 fs3f fc0 sc0 ls0 ws0">=</div><div class="t m0 xbd h7e y1c1 ff5 fs3f fc0 sc0 ls0 ws0">⎟</div><div class="t m0 xbd h7e y1c2 ff5 fs3f fc0 sc0 ls0 ws0">⎠</div><div class="t m0 xbd h7e y1c3 ff5 fs3f fc0 sc0 ls0 ws0">⎞</div><div class="t m0 x93 h7e y1c1 ff5 fs3f fc0 sc0 ls0 ws0">⎜</div><div class="t m0 x93 h7e y1c2 ff5 fs3f fc0 sc0 ls0 ws0">⎝</div><div class="t m0 x93 h7e y1c3 ff5 fs3f fc0 sc0 ls0 ws0">⎛</div><div class="t m0 xba h7e y1c0 ff5 fs3f fc0 sc0 ls0 ws0">=</div><div class="t m0 xb7 h7e y1c4 ff5 fs3f fc0 sc0 ls0 ws0">⎟</div><div class="t m0 xb7 h7e y1c5 ff5 fs3f fc0 sc0 ls0 ws0">⎟</div><div class="t m0 xb7 h7e y1c6 ff5 fs3f fc0 sc0 ls0 ws0">⎠</div><div class="t m0 xb7 h7e y1c7 ff5 fs3f fc0 sc0 ls0 ws0">⎞</div><div class="t m0 xd8 h7e y1c8 ff5 fs3f fc0 sc0 ls0 ws0">⎜</div><div class="t m0 xd8 h7e y1c9 ff5 fs3f fc0 sc0 ls0 ws0">⎜</div><div class="t m0 xd8 h7e y1ca ff5 fs3f fc0 sc0 ls0 ws0">⎝</div><div class="t m0 xd8 h7e y1cb ff5 fs3f fc0 sc0 ls0 ws0">⎛</div><div class="t m0 x74 h7e y1cc ff5 fs3f fc0 sc0 ls0 ws0">=</div><div class="t m0 xd3 h7f y1cd ff4 fs3e fc0 sc0 ls0 ws0">m</div><div class="t m0 xd9 h7f y1ce ff4 fs3e fc0 sc0 ls0 ws0">i</div><div class="t m0 x51 h7f y1cf ff4 fs3e fc0 sc0 ls0 ws0">i</div><div class="t m0 xda h7f y1cd ff4 fs3e fc0 sc0 ls0 ws0">n</div><div class="t m0 xb2 h7f y1ce ff4 fs3e fc0 sc0 ls0 ws0">j</div><div class="t m0 xdb h7f y1cd ff4 fs3e fc0 sc0 ls0 ws0">n</div><div class="t m0 x1f h7f y1ce ff4 fs3e fc0 sc0 ls0 ws0">j</div><div class="t m0 xdc h7f y1cd ff4 fs3e fc0 sc0 ls0 ws0">m</div><div class="t m0 x26 h7f y1ce ff4 fs3e fc0 sc0 ls0 ws0">i</div><div class="t m0 xc0 h7f y1cf ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 xb9 h7f y1cd ff4 fs3e fc0 sc0 ls0 ws0">m</div><div class="t m0 x83 h7f y1ce ff4 fs3e fc0 sc0 ls0 ws0">i</div><div class="t m0 x24 h7f y1cd ff4 fs3e fc0 sc0 ls0 ws0">n</div><div class="t m0 xa6 h7f y1ce ff4 fs3e fc0 sc0 ls0 ws0">j</div><div class="t m0 x59 h7f y1cf ff4 fs3e fc0 sc0 ls0 ws0">ij<span class="_ _1c"></span>j</div><div class="t m0 x94 h80 y1c0 ff4 fs3f fc0 sc0 ls0 ws0">a<span class="_ _b4"></span>x<span class="_ _b5"></span>x<span class="_ _b6"></span>b</div><div class="t m0 x8c h81 y1bf ff1 fs3e fc0 sc0 ls0 ws0">1<span class="_ _b7"></span><span class="ls30">11<span class="_ _b3"></span>1<span class="_ _b1"></span><span class="ls31">11</span></span></div><div class="t m0 xdd h5 y1d0 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h6 y1d1 ff2 fs2 fc0 sc0 ls0 ws0">其约束条件的系数矩阵相当特殊，<span class="_ _57"></span>可用比较简单的计算方法，<span class="_ _57"></span>习惯上称为表上作业法<span class="_ _57"></span>（由</div><div class="t m0 x4 h5 y1d2 ff2 fs2 fc0 sc0 ls0 ws0">康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）<span class="_ _57"></span>。<span class="ff1"> </span></div><div class="t m0 x4 h5 y1d3 ff1 fs2 fc0 sc0 ls0 ws0"> </div><div class="t m0 x4 h5 y1d4 ff2 fs2 fc0 sc0 ls0 ws0">§<span class="ff1 ls3 ws1">3 </span>指派问题<span class="ff1"> </span></div><div class="t m0 x67 h5 y1d5 ff1 fs2 fc0 sc0 lsa wsa">3.1 <span class="ff2 ls0 ws0">指派问题的数学模型<span class="ff1"> </span></span></div><div class="t m0 x67 h5 y1d6 ff2 fs2 fc0 sc0 ls0 ws0">例<span class="_ _2"> </span><span class="ff1 ls3 ws1">7 </span>拟分配</div><div class="t m0 xde h47 y1d7 ff4 fs3f fc0 sc0 ls0 ws0">n<span class="_ _20"> </span><span class="ff2 fs2">人去干<span class="_ _2f"> </span></span>n<span class="_ _1"> </span><span class="ff2 fs2">项工作，每人干且仅干一项工作，若分配第<span class="_ _4"> </span></span><span class="fs25">i<span class="_ _1"> </span><span class="ff2 fs2">人去干第</span></span></div><div class="c xdf y1d8 wc h73"><div class="t m0 xd0 h65 y57 ff4 fs31 fc0 sc0 ls0 ws0">j</div></div><div class="t m0 x4 h6 y1d9 ff2 fs2 fc0 sc0 ls0 ws0">项工作，需花费</div><div class="t m0 x55 h7f y1da ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 x56 h65 y1d9 ff4 fs31 fc0 sc0 ls0 ws0">c<span class="_ _ad"> </span><span class="ff2 fs2">单位时间，问应如何分配工作才能使工人花费的总时间最少？<span class="ff1"> </span></span></div><div class="t m0 x67 h6 y1db ff2 fs2 fc0 sc0 ls0 ws0">容易看出，要给出一个指派问题的实例，只需给出矩阵</div><div class="t m0 xe0 h66 y1dc ff1 fs21 fc0 sc0 ls0 ws0">)<span class="_ _4a"></span>(</div><div class="t m0 xe1 h7f y1dd ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 xe2 h65 y1dc ff4 fs31 fc0 sc0 ls0 ws0">c<span class="_ _14"></span>C</div><div class="c xe3 y1de w6 h35"><div class="t m0 x0 h64 yda ff5 fs31 fc0 sc0 ls0 ws0">=</div></div><div class="t m0 xe4 h80 y1dc ff2 fs2 fc0 sc0 ls0 ws0">，<span class="_ _4"> </span><span class="ff4 fs3f">C<span class="_ _2"> </span></span>被称为指<span class="_ _1a"></span>派</div><div class="t m0 x4 h5 y1df ff2 fs2 fc0 sc0 ls0 ws0">问题的系数矩阵。<span class="ff1"> </span></div><div class="t m0 x67 h6 y1e0 ff2 fs2 fc0 sc0 lsf ws0">引入变量</div><div class="t m0 xaf h7f y1e1 ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 x45 h65 y1e2 ff4 fs31 fc0 sc0 ls0 ws0">x<span class="_ _ad"> </span><span class="ff2 fs2 lsf">，若分配</span></div><div class="t m0 x77 h47 y1e3 ff4 fs25 fc0 sc0 ls0 ws0">i</div><div class="t m0 x23 h6 y1e2 ff2 fs2 fc0 sc0 ls0 ws0">干</div><div class="c x19 y1e4 wc h73"><div class="t m0 xd0 h65 y57 ff4 fs31 fc0 sc0 ls0 ws0">j</div></div><div class="t m0 x49 h66 y1e2 ff2 fs2 fc0 sc0 lsf ws0">工作，则取<span class="_ _7a"> </span><span class="ff1 fs21 ls0">1</span></div><div class="c x8d y1e4 w6 h35"><div class="t m0 x0 h64 y57 ff5 fs31 fc0 sc0 ls0 ws0">=</div></div><div class="t m0 x9e h7f y1e1 ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 xe5 h65 y1e2 ff4 fs31 fc0 sc0 ls0 ws0">x<span class="_ _61"> </span><span class="ff2 fs2 lsf">，否则取<span class="_ _b8"> </span></span><span class="ff1 fs21">0</span></div><div class="c xe6 y1e4 w6 h35"><div class="t m0 x0 h64 y57 ff5 fs31 fc0 sc0 ls0 ws0">=</div></div><div class="t m0 xe7 h7f y1e1 ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 x95 h65 y1e2 ff4 fs31 fc0 sc0 ls0 ws0">x<span class="_ _b8"> </span><span class="ff2 fs2 lsf">。上述指派问题的</span></div><div class="t m0 x4 h5 y1e5 ff2 fs2 fc0 sc0 ls0 ws0">数学模型为<span class="ff1"> </span></div><div class="t m0 x67 h5 y1e6 ff1 fs2 fc0 sc0 ls10 ws0"> </div><div class="t m0 x57 h7c y1e7 ff5 fs3d fc0 sc0 ls32 ws0">∑∑</div><div class="t m0 xe8 h7d y1e8 ff5 fs3e fc0 sc0 ls33 ws0">==</div><div class="t m0 xe8 h7f y1e9 ff4 fs3e fc0 sc0 ls0 ws0">n</div><div class="t m0 xa9 h7f y1e8 ff4 fs3e fc0 sc0 ls0 ws0">i</div><div class="t m0 x48 h7f y1e9 ff4 fs3e fc0 sc0 ls0 ws0">n</div><div class="t m0 xa6 h7f y1e8 ff4 fs3e fc0 sc0 ls0 ws0">j</div><div class="t m0 x3 h7f y1ea ff4 fs3e fc0 sc0 ls0 ws0">ij<span class="_ _ae"></span>ij</div><div class="t m0 x25 h80 y1eb ff4 fs3f fc0 sc0 ls0 ws0">x<span class="_ _38"></span>c</div><div class="t m0 xd8 h81 y1e8 ff1 fs3e fc0 sc0 ls34 ws0">11</div><div class="t m0 xc1 h77 y1eb ff1 fs3a fc0 sc0 ls0 ws0">min<span class="_ _17"> </span><span class="fs2"> </span></div><div class="t m0 x67 h5 y1ec ff1 fs2 fc0 sc0 lsd wsb"> s.t. <span class="_ _3d"></span> </div><div class="t m0 x47 h7c y1ed ff5 fs3d fc0 sc0 ls0 ws0">∑</div><div class="t m0 x4b h7d y1ee ff5 fs3e fc0 sc0 ls0 ws0">=</div><div class="t m0 xb9 h7e y1ef ff5 fs3f fc0 sc0 ls0 ws0">=</div><div class="t m0 x46 h7f y1f0 ff4 fs3e fc0 sc0 ls0 ws0">n</div><div class="t m0 x45 h7f y1f1 ff4 fs3e fc0 sc0 ls0 ws0">j</div><div class="t m0 xde h7f y1f2 ff4 fs3e fc0 sc0 ls0 ws0">ij</div><div class="t m0 xd4 h80 y1ef ff4 fs3f fc0 sc0 ls0 ws0">x</div><div class="t m0 x56 h81 y1ee ff1 fs3e fc0 sc0 ls0 ws0">1</div><div class="t m0 x28 h77 y1ef ff1 fs3a fc0 sc0 ls0 ws0">1<span class="_ _50"></span><span class="fs2"> </span></div></div><div class="pi" data-data='{"ctm":[1.611639,0.000000,0.000000,1.611639,0.000000,0.000000]}'></div></div>
