一、計算題

1． 用Gomory 切割法解以下問題。

【答案】(1)在該線性規劃問題的約束條件中分別加入松弛變量x3，x4，化為標準型

先不考慮上述模型中的整數約束，利用單純形法進行求解，如表所示。

表

此時的最優解為最優目標值。

由表中最終單純形表可得變量間的關系式：

將系數和常數項都分解成整數和非負數真分數之和，移項，則以上兩式變為

要求x 1，x 2，x 3，x 4為非負整數，從上述兩式看來，等式左邊是整數，等式右邊括號內是正數，所以等式右邊必須是負數，則上述第二個等式的右端可由下式代替：

即

加入松弛變量x 5，即得到切割方程:

表

將該約束條件加入到上表的最終單純形表中，并進行進一步求解，如下表所示。

由于x l ，x 2己為整數，所以最優解為

(2)在該線性規劃問題的約束條件中分別加入松弛變量x 3，x 4，x 6及人工變量x 5，化為標準型

先不考慮模型中的整數約束，利用單純形法進行求解，如表所示。

表

此時的最優解為

由表中最終單純形表可得變量間的關系式:

，最優目標值Z*=30/7。

將系數和常數項都分解成整數和非負真分數之和，并移項，則以上三式變為:

因為要求所有變量為非負整數，從上述第一個等式看來，等式左邊是整數，等式右邊括號內是正數，所以等式右邊必是負數，則上述第一個等式的右端可由下式代替：

加入松弛變量x 7，即得到切割方程：將該約束條件加入到表

總結

以上是生活随笔為你收集整理的昆明理工大学计算机面试题,2016年昆明理工大学管理与经济学院F003运筹学复试笔试仿真模拟题...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。