1、對偶問題的性質5——互補鬆弛性
設x0和y0分別是p問題和 d問題的可行解，則它們分別是最優解的充要條件是：
其中：xs、ys為鬆弛變數
性質5的應用：該性質給出了已知乙個問題最優解求另乙個問題最優解的方法，即已知y＊求x＊或已知x＊求y＊
由於變數都非負，要使求和式等於零，則必定每一分量為零，因而有下列關係：
若y＊≠0，則xs必為0；若x＊≠0，則ys必為0
利用上述關係，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優解。
例2.4 已知線性規劃的最優解是x＊=(6,2,0)t,求其對偶問題的最優解y＊。
設對偶問題最優解為y＊＝(y1，y2),由互補鬆弛性定理可知，x＊和 y＊滿足：
因為x1≠0，x2≠0，所以對偶問題的第
一、二個約束的鬆弛變數等於零，即y3＝0，y4＝0，帶入方程中：
解此線性方程組得y1=1,y2=1,從而對偶問題的最優解為：
y＊=(1,1)，最優值w=26。
2、圖的基本概念
若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關聯邊。若點vi、vj與同一條邊關聯，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。
如果邊e的兩個端點相重，稱該邊為環。如右圖中邊e1為環。如果兩個點之間多於一條，稱為多重邊，如右圖中的e4和e5，對無環、無多重邊的圖稱作簡單圖。
與某乙個點vi相關聯的邊的數目稱為點vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數的點稱作奇點，次為偶數的點稱作偶點，次為1的點稱為懸掛點，次為0的點稱作孤立點。
圖的次: 乙個圖的次等於各點的次之和。
圖中某些點和邊的交替序列，若其中各邊互不相同，且對任意vi,t-1和vit均相鄰稱為鏈。用μ表示：
起點與終點重合的鏈稱作圈。如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。
賦予權的圖g稱為網路(或賦權圖）
有向圖中，以vi為始點的邊數稱為點vi的出次，用d+(vi)表示；以vi為終點的邊數稱為點vi 的入次，用表示d-(vi) ；vi 點的出次和入次之和就是該點的次。
3、圖的基本性質：
定理1 任何圖中，頂點次數之和等於所有邊數的2倍。
定理2 任何圖中，次為奇數的頂點必為偶數個。
4、 樹：無圈的連通圖即為樹
性質1：任何樹中必存在次為1的點。
性質2：n 個頂點的樹必有n-1 條邊。
性質3：樹中任意兩個頂點之間，恰有且僅有一條鏈。
性質4：樹連通，但去掉任一條邊，必變為不連通。
性質5：樹無迴圈，但不相鄰的兩個點之間加一條邊，恰得到乙個圈。
5、最短路問題
例6.8 裝置更新問題。某公司使用一台裝置，在每年年初，公司就要決定是購買新的裝置還是繼續使用舊裝置。
如果購置新裝置，就要支付一定的購置費，當然新裝置的維修費用就低。如果繼續使用舊裝置，可以省去購置費，但維修費用就高了。請設計乙個五年之內的更新裝置的計畫，使得五年內購置費用和維修費用總的支付費用最小。
已知：裝置每年年初的**表
裝置維修費如下表
解：將問題轉化為最短路問題，如下圖：用vi表示「第i年年初購進一台新裝置」,弧（vi,vj）表示第i年年初購進的裝置一直使用到第j年年初。
把所有弧的權數計算如下表，把權數賦到圖中，再用dijkstra演算法求最短路。
最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1→v3→v6和 v1→v4→v6
6、 網路的最大流
1. 容量網路：隊網路上的每條弧(vi,vj)都給出乙個最大的通過能力，稱為該弧的容量，簡記為cij。
容量網路中通常規定乙個發點(也稱源點，記為s)和乙個收點(也稱匯點，記為t)，網路中其他點稱為中間點。
網路的最大流是指網路中從發點到收點之間允許通過的最大流量。
流是指加在網路各條弧上的實際流量，對加在弧(vi,vj)上的負載量記為fij。若fij=0，稱為零流。
考研備考政治大綱 新大綱考前複習規劃
考前備考提點 本階段主要以模擬考試為主要複習方法 二 歸納總結，強化訓練 本階段複習主要解決兩個問題 一是歸納總結，查缺補漏 二是強化應試訓練，找出應試技巧。這是政治複習的關鍵階段。關於這一階段書籍的選擇，一方面要好好利用歷年的考試真題，同時也可以關注一些著名考研輔導班的內部資料。本階段政治複習應注...
考研數學規劃 確定基礎階段複習目標
考研複習是乙個龐大的系統工程,複習課程多，時間跨度長，因此考研複習最重要的是要有自己的計畫。對於廣大理工類和經濟類考生來說，考研數學是重點拿分的一門科目，是決定考研成績總分高低的關鍵科目，建議在初期階段參考以下內容確定基礎階段性複習目標，從而使後面的強化階段和衝刺階段的複習更有針對性。一 初期複習目...
考前複習總結理科
1 已知定義域為r的函式不是奇函式，則下列命題一定為真命題的是 ab c d 2設，則 是 a end b beginb end altimg w 114 h 20 的 a 充分不必要條件 b 必要不充分條件 c 充要條件 d 既不充分也不必要條件 3已知則 是 的 a.充分不必要條件b.必要不充分...