1、第一節(jié) 整數(shù)線性規(guī)劃問題整數(shù)線性規(guī)劃問題舉例解整數(shù)線性規(guī)劃問題的困難性整數(shù)線性規(guī)劃問題整數(shù)線性規(guī)劃（ILP）具有下述形式0-1整數(shù)線性規(guī)劃模型混合整數(shù)線性規(guī)劃1. 整數(shù)線性規(guī)劃問題舉例例 3.1.1例3.1.1 投資決策問題分析變量每個項目是否投資約束總金額不超過限制目標(biāo)總收益最大例3.1.1 投資決策問題數(shù)學(xué)模型旅行售貨員問題此外，運籌學(xué)還有一個著名的問題：旅行售貨員問題（TSP）顯示問題2. 解整數(shù)線性規(guī)劃問題的困難性整數(shù)規(guī)劃可行解是松弛問題的可行解最優(yōu)值大于等于松弛問題的最優(yōu)值松弛的線性規(guī)劃問題與線性規(guī)劃的關(guān)系：2. 解整數(shù)線性規(guī)劃問題的困難性LP的可行集合費用下降方向LP問題的最優(yōu)解I

2、LP問題的最優(yōu)解2. 解整數(shù)線性規(guī)劃問題的困難性續(xù)最優(yōu)解不一定在頂點上達(dá)到最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多于松弛問題的頂點，枚舉法不可取解ILP問題要遠(yuǎn)難于解松弛的LP問題如果松弛的LP問題無解，顯然原ILP問題無解。反之，不一定成立。如果松弛的LP問題無界呢？可以證明原ILP問題也無界第二節(jié) Gomory割平面法Gomory 割平面法基本思想Gomory 割平面法計算步驟1. Gomory 割平面法基本思想整數(shù)規(guī)劃松弛的線性規(guī)劃問題( )( 兩個問題具有如下明顯關(guān)系：(1) ( )的可行域 ( )的可行域;(2) 若( )無可行解，則( )無可行解；(3) ( )的最優(yōu)

3、值是( )的最優(yōu)值的一個下界；(4) 若( )的最優(yōu)解是整數(shù)向量，則它也是( )的最優(yōu)解.)Gomory 割平面法基本思想續(xù)一由松弛問題的可行域向整數(shù)規(guī)劃的可行域逼近方法利用超平面切除要求 整數(shù)解保留 松弛問題最優(yōu)值增加割平面法生成方法割平面生成方法條件-保留整數(shù)解刪除非整數(shù)的最優(yōu)解!下面是求c松弛問題的最后一張單純形表：割平面法生成方法續(xù)整數(shù)可行解加入松弛變量s 割平面Gomory 割平面法基本思想續(xù)二Gomory 割平面法基本思想續(xù)三Gomory 割平面法基本思想續(xù)四Gomory 割平面法基本思想續(xù)五 Gomory 割平面法基本思想續(xù)六Gomory 割平面法基本思想續(xù)七2. Gomory

4、割平面法計算步驟求松弛問題的最優(yōu)基可行解判斷是否為整數(shù)解是得到最優(yōu)解否在單純性表中加入一列利用對偶單純形算法求最優(yōu)解2. Gomory 割平面法計算步驟-例題例3.2.1求解ILP問題(1,1.5)第三節(jié) 分枝定界法分枝定界法基本思想分枝定界法計算步驟1. 分枝定界法基本思想最優(yōu)值比界壞 最優(yōu)解為整數(shù)最優(yōu)值比界好 最優(yōu)解為非整數(shù)最優(yōu)值比界好分 枝邊 界分 枝舍 棄1. 分枝定界法基本思想續(xù)條件-保留整數(shù)解刪除最優(yōu)解!下面是求松弛問題的最后一張單純形表：1. 分支定界法基本思想續(xù)分枝的方法1. 分枝定界法基本思想續(xù)分枝方法示意圖1. 分枝定界法基本思想續(xù)定界1. 當(dāng)前得到的最好整數(shù)解的目標(biāo)函數(shù)值2. 分枝后計算松弛的線性規(guī)劃的最優(yōu)解整數(shù)解且目標(biāo)值小于原有最好解的值則替代原有最好解整數(shù)解且目標(biāo)值大于原有最好解的值則 刪除該分支其中無最優(yōu)解非整數(shù)解且目標(biāo)值小于原有最好解的值則繼