寫在前面：授課教師為宋燕，下文所用ppt為宋老師上課的課件。本文僅用于個人學習。
部分作業參考百度文庫的答案管理運籌學課后答案

文章目錄

• 第二章 線性規劃和單純形法
• • 第一節 線性規劃問題及其數學模型
  • • 2.1.1問題的提出
    • 2.1.2圖解法
    • 2.1.3線性規劃問題的標準形式
    • 2.1.4 線性規劃問題解的概念
    • • 作業題
  • 第二節 線性規劃問題的幾何意義
  • 第三節 單純形法
  • • 2.3.1 單純形法舉例
    • 2.3.2 初始基可行解的確定
    • 2.3.3 最優性檢驗與解的判別
    • 2.3.4 基變換
    • 2.3.5迭代（旋轉運算）
  • 第四節 單純形法的計算步驟
  • • 2.4.1 單純形表
    • 2.4.2 計算步驟
    • • 單純形表做題
  • 第五節 單純形法的進一步討論
  • • 2.5.1 人工變量法
    • • 課堂練習
      • 作業
• 第三章 對偶理論和靈敏度分析
• • 第1節 單純形法的矩陣描述
  • 第2節 改進單純形法
  • • • 改進單純形法例題
      • 作業題
  • 第3節 對偶問題的提出
  • 第4節 線性規劃的對偶理論
  • • 4.1原問題和對偶問題的關系
    • • 作業
    • 4.2 對偶問題的基本性質
    • • 作業
  • 第5節 對偶問題的經濟解釋
  • 第6節 對偶單純形法
  • • 對偶單純形法例題
    • • 作業
  • 第7節 靈敏度分析
  • • 7.1 資源數量變化的分析
    • 7.2 目標函數中價值系數$c_j$的變化分析
    • 7.3 技術系數${\alpha }_{ij}$的變化
    • • 靈敏度分析作業題
  • 第四章 運輸問題
  • • 第一節 運輸問題的典例
    • 第二節 運輸問題的數學模型
    • 第三節 求解方法-表上作業法
  • 第六章 整數規劃
  • • • 割平面法求解例題
      • 分支定界法求解例題
• 期末復習題
• 期末考試真題2020年（已刪除）

第二章 線性規劃和單純形法

第一節 線性規劃問題及其數學模型

2.1.1問題的提出

線性規劃通常解決兩類問題：

線性規劃數學模型三要素：決策變量、目標函數、約束條件。

2.1.2圖解法

圖解法求解線性規劃問題

通過圖解法，可以觀察到線性規劃的解可能出現下列的情況
（1）唯一最優解。
（2）無窮多最優解(多重最優解)。
（3）無界解。
（4）無可行解。

2.1.3線性規劃問題的標準形式

或者簡寫為

線性規劃問題標準形式的特點

如何進行標準化？

例2.3 將例2.1的數學模型化為標準形式的線性規劃。
不等式約束全是小于號，直接加上正的松弛變量即可。

例2.4 將下列線性規劃問題化為標準形式

標準形式如下

2.1.4 線性規劃問題解的概念

線性規劃問題

幾個重要概念
可行解、可行域、最優解、基、基向量、基變量、非基變量、基解、基可行解、可行基。

一篇文章：深入理解線性規劃中的基可行解

例2.5 求下列約束方程所對應的線性規劃的所有基解，基可行解。

下面來解這道題

這里的基為B，滿足m*m，并且組成的列向量線性無關(不成比例)

作業題

解答

第二節 線性規劃問題的幾何意義

第三節 單純形法

單純形法是求解線性規劃的主要算法，1947年由美國斯坦福大學教授丹捷格（G.B.Danzig）提出。盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實用的特色始終保持著絕對的“市場”占有率。

2.3.1 單純形法舉例

例2.6 試以例2.1來討論如何用單純形法求解。

解：約束條件(2-12)式的系數矩陣為

這個基可行解的經濟含義：工廠沒有安排生產產品Ⅰ和Ⅱ，資源都沒有被利用，所以利潤為z=0。

從(2-14)可以看到：非基變量x1,x2的系數都是正數，因此將非基變量變換為基變量，目標函數的值就可能增大。從經濟意義上講，安排生產產品Ⅰ或Ⅱ，就可以使工廠的利潤指標增加。
所以只要在目標函數(2-14)的表達式中還存在有正系數的非基變量，這表示目標函數值還有增加的可能，就需要將非基變量與基變量進行對換。

2.3.2 初始基可行解的確定

為了確定初始基可行解，要首先找出初始可行基，其方法如下。
1）直接觀察
2）加松弛變量
3）加非負的人工變量

2.3.3 最優性檢驗與解的判別

2.3.4 基變換

2.3.5迭代（旋轉運算）

例7 試用上述方法計算例6的兩個基變換。

第四節 單純形法的計算步驟

2.4.1 單純形表

為了便于理解計算關系，現設計一種計算表，稱為單純形表，其功能與增廣矩陣相似，下面來建立這種計算表。
將(2-22)式與目標函數組成n+1個變量，m+1個方程的方程組。
線性規劃的方程組

為了便于迭代運算，可將上述方程組寫成增廣矩陣的形式

2.4.2 計算步驟

單純形表做題

總結一下計算單純形表的步驟
1.寫出線性規劃標準形，找到初始基可行解。
2.列出單純形表，計算檢驗數σ，和θ。按照σ最大原則找到換入變量，按照θ最小原則找到換出變量。這里要求在σ＞0中選擇，θ在aj＞0中選擇。 換入變量和換出變量的交點是主元素。

3 初等行變換，把主元素所在列化成只有一個1，其他全為0.

4 基變量位置上換入變量寫上。
5迭代，直到所有的檢驗數σ都≤0.

第五節 單純形法的進一步討論

2.5.1 人工變量法

人工變量法是解決：線性規劃的約束條件中沒有可以作為初始基的單位矩陣



大M只需要添加在缺少單位變量的那個約束條件上。比如下面的第2、3個約束才需要添加，而第1個約束不需要添加，因為它已經有了x4可以提供單位矩陣。

求最大值問題，目標函數中的M的系數需要是負號；求最小值問題，目標函數中M的系數需要是正號，比如下面這道題目。

課堂練習

解答
設 Xk表示Xk名司機和乘務人員第k班次開始上班，接連工作8小時，也就是說，第k班次上班的工作人員可以在第k+1段時間工作，因此有如下的解答。

解答
常規的單純形法

作業

解答：

作業：使用大M法求解線性規劃問題

解答

用向量單純形法求解線性規劃問題
只要：使用非基變量表示基變量，然后確定入基變量，出基變量；令非基變量等于0，得到基解和目標函數值。查看目標函數中：非基變量的系數是否為負，非基變量系數如果有正的，說明還不是最優解，一直入基出基迭代。

第三章 對偶理論和靈敏度分析

第1節 單純形法的矩陣描述

第2節 改進單純形法

求解線性規劃問題的關鍵是計算$B^{?1}$,下面介紹一種比較簡便的計算$B^{?1}$的方法。

這里$\xi$表示的是變化過程，使得該列變成一個1，其他全是0的形式。具體過程：該列除以主元素，然后其他行減去 所在位置的值/主元素。

改進單純形法例題

矩陣計算檢驗數的公式$C_N?C_B{B}^{?1}N$
N是非基變量的系數矩陣

解答

θ最小規則，我們需要知道右端系數 $B^{?1}b$,這里$B^{?1}$是單位陣，所以右端系數還是b，也就是$(8,16,12{)}^T$
而$B^{?1}{P}_S$對應的是換入變量的系數，這里是x2的系數$(2，0，4{)}^T$

回顧在單純形表中的步驟，確定換入變量和換出變量之后，就要高斯消元法（初等行變換），對應到矩陣就是求$B^{?1}$

這里P2中主元素的確定還是根據換入變量和換出變量相交的位置，這里P2是x2換入變量，換出變量是x5，即下圖中第三個位置，所以，這里的主元素是4

然后$B_1^{?1}$等于$B_0^{?1}$左乘E1。

對于(5)，現在的基是(P3,P4,P2)，則非基變量的系數矩陣 N1=(P1,P5)

對于（6），就是計算右端常數值

下面是第二步：

作業題

解答

第3節 對偶問題的提出

對于例1的最大值線性規劃

第4節 線性規劃的對偶理論

4.1原問題和對偶問題的關系

對稱形式（約束條件沒有等號）




解答

非對稱形式

原問題中目標函數的價值向量C，在對偶問題中是約束條件的右端常數項；
原問題中約束條件的右端常數項b，在對偶問題中是目標函數的價值系數；
原問題中約束條件的系數矩陣在對偶問題中進行了轉置

對于對稱的LP問題，
如果原問題求的是極大化
其對偶問題的決策變量的方向與原問題約束條件不等號方向相反，對偶問題的約束條件不等號的方向與原問題決策變量的方向相同。

如果原問題求的是極小化，對偶問題的決策變量和原問題的約束條件不等號相同；對偶問題約束條件的不等號方向和原問題的決策變量的方向相反。

對偶問題的決策變量的方向，去找原問題的約束條件的不等號；
對偶問題的約束條件不等號的方向，去找原問題的決策變量的方向；

寫出非對稱的對偶問題的思路（僅限于原問題是求極大值）
1.將系數矩陣A轉置，把價值系數C轉置放到常數項的位置；不等號的方向去找原問題的決策變量的方向；
2.決策變量的方向去找原問題約束的不等號相反。

下面這道題：原問題是求極小值！！！

注意：本題原問題求的是最小值，也就是說對于對偶問題，其決策變量的方向與原問題不等號方向相同；其約束條件不等號方向與決策變量相反；

作業

寫出對偶問題

解答

4.2 對偶問題的基本性質

解答

解答
這里利用的是互補松弛性，對偶問題的化為標準形需要添加松弛變量Xs，把最優解代入到各個約束條件中，發現條件1是等式，所以松弛變量為0，解不出x1；約束條件2 ：代入最優解發現是嚴格的不等式，所以松弛變量是不等于0的，那么根據互補松弛性：$x_2?y_{s2}=0$，可以得到x2=0，如下。

這里 原問題的兩個約束條件應取等號原因如下：
y1，y2≥0，這里添加的松弛變量是0，只有在等式的時候才成立。

作業

解答
第（1）、（2）題反例：

補充題目

解答

第5節 對偶問題的經濟解釋

第6節 對偶單純形法

對偶單純形法例題

這里對偶變量的最優解由下表可得，就是松弛變量對應的檢驗數的相反數。


很難找到初始可行基的意思是：一組$C_N=C_B{B}^{?1}N＜0$很難找到

作業

解答（1）
詳細解答過程

解答（2）

詳細過程

第7節 靈敏度分析

7.1 資源數量變化的分析

注：下面這道例題求的是在原最優解不變的情況下，b2的變化范圍。

常數對應的是$B^{?1}b$，松弛變量對應的是$B^{?1}$

7.2 目標函數中價值系數$c_j$的變化分析

回顧矩陣表示的單純形表

由上圖，我們發現價值系數Cj不影響$B^{?1}$，而是影響檢驗數，而且它可能影響非基變量$C_N$，也可能影響基變量$C_B$.

這里我們令 $C_B{B}^{?1}=P影子價格$

下圖是例1的表2-5

7.3 技術系數${\alpha }_{ij}$的變化

靈敏度分析作業題

靈敏度分析的任務：確定各個變量使得最優解保持不變的變化范圍；以及在最優解改變的時候求出相應的最優解。

自己解答：答案正確

百度文庫解答

第四章 運輸問題

第一節 運輸問題的典例

第二節 運輸問題的數學模型

第三節 求解方法-表上作業法

第六章 整數規劃

純整數規劃

割平面法求解例題

將割平面添加到約束方程，重新寫單純形表，進行計算。

分支定界法求解例題

期末復習題

靈敏度分析題目

解答：
通過單純形法得到最終的單純形表

根據資源數量變化的關系：計算

期末考試真題2020年（已刪除）

運籌學期末考試2020年8月30日復盤

填空題20分 ，選擇題10分 答題70分。

2021年7月5日更新，由于某些原因，該部分已刪除。

總結

以上是生活随笔為你收集整理的运筹学期末复习2020年的全部內容，希望文章能夠幫你解決所遇到的問題。

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