|
楼主 |
发表于 2004-5-4 20:16:32
|
显示全部楼层
< 0cm 0cm 0pt"><B normal">第二节<FONT face="Times New Roman"> </FONT></B><B normal">用<FONT face="Times New Roman">LINDO</FONT></B><B normal">求解线性规划(<FONT face="Times New Roman">LP</FONT></B><B normal">)问题<p></p></B></P>< 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P>< 0cm 0cm 0pt"><FONT face="Times New Roman">2.1</FONT>初试<FONT face="Times New Roman"> LINDO</FONT></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> LINDO </FONT>的求解机制:<FONT face="Times New Roman">LINDO </FONT>的求解过程采用单纯形法,一般是首先寻求一个可行解<FONT face="Times New Roman">, </FONT>在有可行解情况下再寻求最优解<FONT face="Times New Roman">. </FONT>用<FONT face="Times New Roman">LINDO </FONT>求解一个<FONT face="Times New Roman">LP</FONT>问题会得到如下的几种结果<FONT face="Times New Roman">:</FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>不可行<FONT face="Times New Roman">(No feasible solution) </FONT>或<FONT face="Times New Roman"> </FONT>可行<FONT face="Times New Roman">(Feasible)<p></p></FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>可行时又可分为<FONT face="Times New Roman">: </FONT>有最优解<FONT face="Times New Roman">(Optimal Solution)</FONT>和解无界<FONT face="Times New Roman">(Unbounded Solution)</FONT>两种情况<FONT face="Times New Roman">. </FONT>由于在实际问题中<FONT face="Times New Roman">, </FONT>不太可能出现最大利润无上限的情形<FONT face="Times New Roman">, </FONT>所以使用者应检查是否少了一个约束或有其它印刷错误<FONT face="Times New Roman">.</FONT></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>在<FONT face="Times New Roman">LINDO</FONT>子目录下执行<FONT face="Times New Roman">LINDO.EXE</FONT>文件即可进入<FONT face="Times New Roman">LINDO</FONT>工作环境,其屏幕显示如下:</P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt 21.1pt">LINDO/PC 5.02 (<st1:date Month="3" Day="4" Year="1992">4 MAR 92</st1:date>)<p></p></P><P 0cm 0cm 0pt"> <p></p></P><P 0cm 0cm 0pt 21.1pt">STUDENT VERSION. FOR EDUCATIONAL USE ONLY.<p></p></P><P 0cm 0cm 0pt"> <p></p></P><P 0cm 0cm 0pt 21.1pt">SINGLE USER LICENSE FOR EDUCATIONAL USE ONLY <p></p></P><P 0cm 0cm 0pt 21.1pt">DISTRIBUTED WITH TEXTBOOKS BY <st1:City><st1:place>WADSWORTH</st1:place></st1:City> PUBLISHING <p></p></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt 21.1pt"><FONT face="Times New Roman">: </FONT></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt 21.1pt">“:”为<FONT face="Times New Roman">LINDO</FONT>提示符,在其之后,<FONT face="Times New Roman"> </FONT>使用者即可用具体的命令来输入并求解优化问题。让我们来解如下<FONT face="Times New Roman">LP</FONT>问题:</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><v:shapetype><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path gradientshapeok="t" connecttype="rect" extrusionok="f"></v:path><lock v:ext="edit" aspectratio="t"></lock></v:shapetype><v:shape><v:imagedata><FONT face="Times New Roman"></FONT></v:imagedata></v:shape></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><FONT face="Times New Roman"> </FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>由于<FONT face="Times New Roman">LINDO </FONT>中已假设所有的变量都是非负的<FONT face="Times New Roman">, </FONT>所以非负约束可不必再输入到计算机中;<FONT face="Times New Roman">LINDO</FONT>也不区分变量中的大小写字符(实际上任何小写字符将被转换为大写字符);约束条件中的“<FONT face="Times New Roman"><=</FONT>”<FONT face="Times New Roman"> </FONT>及“<FONT face="Times New Roman">>=</FONT>”可用“<FONT face="Times New Roman"><</FONT>”<FONT face="Times New Roman"> </FONT>及“<FONT face="Times New Roman">></FONT>”代替。上面问题用键盘输入如下:<p></p></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt"> : MAX 2x + 3Y<p></p></P><P 0cm 0cm 0pt"> ? ST<p></p></P><P 0cm 0cm 0pt"> ? 4X + 3Y < 10<p></p></P><P 0cm 0cm 0pt"> ? 3x + 5Y < 12<p></p></P><P 0cm 0cm 0pt"> ? END<p></p></P><P 0cm 0cm 0pt"> :<p></p></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><FONT face="Times New Roman">LINDO </FONT>中一般称上面这种问题实例(<FONT face="Times New Roman">INSTANCE</FONT>)为模型(<FONT face="Times New Roman">MODEL</FONT>)。以后涉及该模型时,目标函数为第一行,两个约束条件分别为第二、三行。直接键入运行(<FONT face="Times New Roman">GO</FONT>)命令就可得到解答,<FONT face="Times New Roman"> </FONT>屏幕显示如下:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">:GO<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">LP OPTIMUM FOUND AT STEP 2<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> OBJECTIVE FUNCTION VALUE<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> 1) 7.4545450 <p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> VARIABLE VALUE REDUCED COST<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> X 1.272727 .000000<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> Y 1.636364 .000000<p></p></P><P 0cm 0cm 0pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> ROW SLACK OR SURPLUS DUAL PRICES<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> 2) .000000 .090909<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> 3) .000000 .545455<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> NO. ITERATIONS= 2<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> <p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">DO RANGE(SENSITIVITY) ANALYSIS?<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">? N<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> <p></p></P><P 0cm 0cm 0pt 21.1pt">计算结果表明:</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“<FONT face="Times New Roman">LP OPTIMUM FOUND AT STEP2</FONT>”表示单纯形法在两次迭代(旋转)后得到最优解。</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“<FONT face="Times New Roman">OBJECTIVE FUNCTION VALUE 1) </FONT>7.4545450 ”表示最优目标值为7.4545450<FONT face="Times New Roman">.</FONT></P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“<FONT face="Times New Roman">VALUE</FONT>”给出最优解中各变量<FONT face="Times New Roman">(</FONT>VARIABLE<FONT face="Times New Roman">)</FONT>的值<FONT face="Times New Roman">: </FONT>X =1.272727, Y =1.636364.</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“<FONT face="Times New Roman">REDUCED COST</FONT>”<FONT face="Times New Roman"> </FONT>给出最优单纯形表中第<FONT face="Times New Roman">0</FONT>行中变量的系数<FONT face="Times New Roman"> ( max</FONT>型问题<FONT face="Times New Roman">). </FONT>其中基变量的<FONT face="Times New Roman">reduced cost</FONT>值应为<FONT face="Times New Roman">0</FONT>,对于非基变量<FONT face="Times New Roman">, </FONT>相应的<FONT face="Times New Roman"> reduced cost</FONT>值表示当该非基变量增加一个单位时目标函数减少的量。本例中此值均为<FONT face="Times New Roman">0</FONT>。</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“<FONT face="Times New Roman">SLACK OR SURPLUS</FONT>”<FONT face="Times New Roman"> </FONT>给出松驰变量的值<FONT face="Times New Roman">: </FONT>第<FONT face="Times New Roman">2</FONT>、<FONT face="Times New Roman">3</FONT>行松驰变量均为<FONT face="Times New Roman">0, </FONT>说明对于最优解来讲,两个约束(第<FONT face="Times New Roman">2</FONT>、<FONT face="Times New Roman">3</FONT>行)均取等号。</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“<FONT face="Times New Roman">DUAL PRICES</FONT>”<FONT face="Times New Roman"> </FONT>给出对偶价格的值<FONT face="Times New Roman">: </FONT>第<FONT face="Times New Roman">2</FONT>、<FONT face="Times New Roman">3</FONT>行对偶价格分别为<FONT face="Times New Roman"> </FONT>.090909,.545455。</P><P 0cm 0cm 0pt"><FONT face="Times New Roman"> </FONT>“NO. ITERATIONS= 2”<FONT face="Times New Roman"> </FONT>表示用单纯形法进行了两次迭代(旋转)。<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">一个问题解答之后<FONT face="Times New Roman">, LINDO </FONT>会询问是否需要做灵敏性分析(DO RANGE (SENSITIVITY) ANALYSIS? )<FONT face="Times New Roman"> </FONT>如果你不需要,你应回答“<FONT face="Times New Roman">N</FONT>”(<FONT face="Times New Roman">NO</FONT>),回到提示符“:”之下<FONT face="Times New Roman">. <p></p></FONT></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt">如果想重新看到刚才的模型,可键入<FONT face="Times New Roman"> LOOK </FONT>命令<FONT face="Times New Roman">, LINDO </FONT>会询问具体的行号<FONT face="Times New Roman">. </FONT>典型的应答可以是<FONT face="Times New Roman"> 3, </FONT>或<FONT face="Times New Roman">1-2, </FONT>或<FONT face="Times New Roman">ALL, </FONT>而结果<FONT face="Times New Roman">, </FONT>相应地会显示出第<FONT face="Times New Roman"> 3</FONT>行<FONT face="Times New Roman">, </FONT>第<FONT face="Times New Roman">1-2 </FONT>行<FONT face="Times New Roman">, </FONT>或所有问题行<FONT face="Times New Roman">.<p></p></FONT></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">: LOOK<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">ROW:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">3<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> 3) 3 X + 5 Y <= 12<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">:<p></p></P><P 0cm 0cm 0pt">或<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt">: LOOK all<p></p></P><P 0cm 0cm 0pt"><p> </p></P><P 0cm 0cm 0pt"> MAX 2x + 3Y<p></p></P><P 0cm 0cm 0pt"> SUBJECT TO<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> 2) 4 X + 3 Y <= 10<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 18pt"> 3) 3 X + 5 Y <= 12<p></p></P><P 0cm 0cm 0pt"> END<p></p></P><P 0cm 0cm 0pt"> :<p></p></P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt">如果想修改问题,可键入<FONT face="Times New Roman"> ALTER </FONT>命令<FONT face="Times New Roman">, LINDO </FONT>会询问行号<FONT face="Times New Roman">, </FONT>变量名<FONT face="Times New Roman">, </FONT>及新的系数<FONT face="Times New Roman">. </FONT>例如:如果要将上面问题中约束条件<v:shape><FONT face="Times New Roman"> <v:imagedata></v:imagedata></FONT></v:shape>改为<v:shape><FONT face="Times New Roman"> <v:imagedata></v:imagedata></FONT></v:shape>,再全部看一下,并求解新问题,那么键入<FONT face="Times New Roman">ALTER </FONT>命令后相应的应答为<FONT face="Times New Roman"> 2,X,</FONT>和<FONT face="Times New Roman">6, </FONT>以下是演示过程:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">:ALTER<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">ROW:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">2<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">VAR:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">X<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">NEW COEFFICIENT:<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">6<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">OOK ALL <p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> MAX 2 X + 3 Y<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> SUBJECT TO<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> 2) 6 X + 3 Y <= 10<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> 3) 3 X + 5 Y <= 12<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> END<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">:go<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> <p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> LP OPTIMUM FOUND AT STEP 0<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> OBJECTIVE FUNCTION VALUE<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> 1) 7.3333330 <p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> VARIABLE VALUE REDUCED COST<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> X .666667 .000000<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> Y 2.000000 .000000<p></p></P><P 0cm 0cm 0pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> ROW SLACK OR SURPLUS DUAL PRICES<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> 2) .000000 .047619<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> 3) .000000 .571429<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"> NO. ITERATIONS= 0<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt"> DO RANGE(SENSITIVITY) ANALYSIS?<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">? N<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt">: QUIT<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 27pt"><p> </p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt">最后键入退出(<FONT face="Times New Roman">QUIT</FONT>)命令<FONT face="Times New Roman">, </FONT>即可退出<FONT face="Times New Roman">LINDO</FONT>工作环境。<p></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt"><p><FONT face="Times New Roman"> </FONT></p></P><P 0cm 0cm 0pt; TEXT-INDENT: 21pt">注:输入、查看和修改一个<FONT face="Times New Roman">LP</FONT>模型更方便的方法是采用全屏幕编辑器。在“:”提示符下键入编辑(<FONT face="Times New Roman">EDIT</FONT>)命令可以进入全屏幕编辑器,可以和其他文本编辑器一样方便使用。</P><P 0cm 0cm 0pt"><p><FONT face="Times New Roman"> </FONT></p></P> |
|