资源描述：
《运筹学第二章线性规划的对偶理论复习题.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第二章线性规划的对偶理论习题1、某厂生产A、B、C三种产品，每种产品要表2-1经过Ⅰ、Ⅱ、Ⅲ三道工序加工，设每件产品在每道消工序单件耗ⅠⅡⅢ利润工序上加工所消耗的工时，每道工序可供利用的工产品（元）时上限，以及每件产品的利润如表2-1所示.A321200B413300试列出使总利润最大的线性规划模型，并写出C223250可用工时604020它的对偶问题，同时，就这个对偶问题作出经济上的解释.解：设x，，xx分别表示A、B、C各产品的数量，Z表示总产值则：123maxzxx=++200300250x123st.4 3x++≤x2x6
2、0123 2xxx++≤240123xxx++≤3320123xi(1=≥,2,3)0i原问题的对偶问题为min6wyy=++04020y１２３ 3st.2y++≥yy200１２３ ４yyy++≥3300１２３ 2yyy++≥23250１２３yyy≥≥≥0，0，0１２３经济解释：y1，y2，y3分别表示给别人代工时所得收入，对厂方而言，w越大越好，但定价不能太高，要对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理，厂方不会吃亏，对方也容易接受。2、写出下列线性规划问题的对偶问题：(1)maxz=10x+x+
3、2x123s.t.x+x+2x≤10123x+x+x≤201231x≥(0j=)3,2,1j解：minwy=+1020y１２st.1y+≥y0１２yy+≥1１２ 2yy+≥2１２yy≥≥0，0１２(2)minz=2x+2x+4x123s.t.2x+3x+5x≥21233x+x+7x≤3123x+4x+6x≤5123x≥(0j=)3,2,1j解：maxwyyy=++235１２３st.32 2y++≤yy１２３ 3yyy++≤42１２３ 5yyy++≤764１２３yyy≥≤≤0，0，0１２３(3)maxz=5x+6x+3x123
4、s.t.x+2x+2x=5123−x+5x−x≥31234x+7x+3x≤8123x无约束，x≥0，x≤0123解：minwyyy=++538１２３st.4y−+=yy5１２３ 2yyy++≥576１２３ 2yyy−+≤33１２３ 自由，yyy≤0，≥0１２３(4)minz=3x+2x−3x+4x1234s.t.x−2x−3x+4x≤312342x+3x+4x≥−52342x−3x−7x−4x=21234x≥,0x≤,0x,x无约束1423解：maxwyyy=−+352１２３st.2y+≤y3１２ -2yyy+−53＝2１
5、２３ -3yyy+−37＝-3１２３ 4yyy+−≥444１２３yyy≤≥≤0，0，0１２３3、应用对偶理论证明线性规划问题.maxz=x+x12s.t.−x+x+x≤2123−2x+x−x≤1123x,x,x≥0123有可行解，但无最优解.⎛⎞0⎜⎟证明：x=0是线性问题的可行解，即该问题存在可行解；⎜⎟⎜⎟0⎝⎠又∵其对偶问题为：minwyy=+2１２st.2 -y−≥y1１２yy+≥1１２yy−≥0１２yy≥≥0，0１２∵∴yy,0≥−-y20y≤这与约束条件（）不符1１２１２∴该对偶问题无可行解∴原问题无最优解。4、应
6、用弱对偶定理，证明线性规划问题3maxz=x+2x+x123s.t.x+x−x≤2123x−x+x=11232x+x+x≥2123x≥,0x≤,0x无约束123的最大值不超过1.证明：该线性问题的对偶问题为：minwyyy=++22１２３st.2y++≥yy1１２３yyy−+≤2１２３ -yyy++=1１２３yyy≥≤0，自由，0１２３T易知Y=（，010，）是对偶问题的一个可行解，由对偶问题的对偶定理可得：⎛⎞000⎜⎟cx≤=yb1(2,1,2)1=⎜⎟⎜⎟0⎝⎠∴maxz≤1即最大值不超过15、应用对偶理论，证明线性规划问
7、题maxz=3x+2x12s.t.−x+2x≤4123x+2x≤1412x−x≤312x,x≥012有最优解，并证明其对偶问题也有最优解.证明：对偶问题4minwyyy=++4143１２３st.33 -y++≥yy１２３ 2yyy+−≥242１２３yyy≥≥≥0，0，0１２３T由题易知X=（3，0）是原问题的一个可行解，TY=（0，1，0）是对偶问题的一个可行解由对偶问题的推论23−可得它们都有最优解。即得证。6、已知标准线性规划问题maxz=cxs.t.Ax=bx≥0具有最优解，假设将右端向量b改为另一向量d，如果改变后的问题
8、是可行的，试证该问题一定有最优解.7、考虑下列原始线性规划maxz=2x+x+3x123s.t.x+x+2x≤51232x+3x+4x=12123x≥(0j=)3,2,1j(1)写出其对偶问题；(2)已知（3,2,0）是上述原始问题的最优解，根据互
