第四章整數規劃
4.1 某工廠生產甲、乙兩種裝置，已知生產這兩種裝置需要消耗材料a、材料b，有關資料如下，問這兩種裝置各生產多少使工廠利潤最大？（只建模不求解）
表4－1
解：設生產甲、乙這兩種裝置的數量分別為x1、x2，由於是裝置台數，則其變數都要求為整數，建立模型如下：
4.2割平面法求解。（下表為最優表）
解： 線性規劃的最優解為：
由最終表中得：
將係數和常數項分解成整數和非負真分式之和，上式化為；
移項後得：
即只要把增加的約束條件加到b問題的最優單純形表中。
表4－3
這時得到的為非可行解，用對偶單純形法進行求解。進行迭代得到：
表4－4
由計算結果知還沒有得到整數解，重新再尋找割平面方程。
由x1行得：
將係數和常數項分解成整數和非負真分數之和：
得到新的約束條件
在的最優單純形表中加上此約束，用對偶單純形法求解：
則最優解為，最優目標函式值為z*=55。
4.3max z＝4x1＋3x2＋2x3
隱列舉法
解：（1）先用試探的方法找出乙個初始可行解，如x1＝x2＝0，x3＝1。滿足約束條件，選其作為初始可行解，目標函式z0＝2。
（2）附加過濾條件
以目標函式作為過濾約束：
原模型變為：
max z＝4x1＋3x2＋2x3
求解過程如表所示。
所以該0－1規劃最優解為。
4.4 某公司擬在市東、西、南三區中建立門市部，有7個點ai（i＝1，2，…，7）可供選擇，要求滿足以下條件：
（1）在東區，在a1，a2，a3三個點中至多選兩個；
（2）在西區，a4，a5兩個點中至少選乙個；
（3）在南區，a6，a7兩個點為互斥點。
（4）選a2點必選a5點。
若ai點投資為bi萬元，每年可獲利潤為ci萬元，投資總額為b萬元，試建立利潤最大化的0－1規劃模型。
解：設決策變數為
建立0－1規劃模型如下：
4.5 某城市消防隊布點問題。該城市共有6個區，每個區都可以建消防站，市**希望設定的消防站最少，但必須滿足在城市任何地區發生火警時，消防車要在15 分鐘內趕到現場。
據實地測定，各區之間消防車行駛的時間見表4－9，請幫助該市制定乙個布點最少的計畫。
表4－9 消防車在各區間行駛時間表單位：min
解：引入0－1變數xi作決策變數，令
目標函式為
min z＝x1＋x2＋x3＋x4＋x5＋x6
本問題的約束方程是要保證每個地區都有乙個消防站在15分鐘行程內。如地區1，由表4－9可知，在地區1及地區2內設消防站都能達到此要求，即
x1＋x2≥1
因此本問題的數學模型為：
min z＝x1＋x2＋x3＋x4＋x5＋x6
x1＋x21
x1＋x2x6≥1
x3＋x41
x3＋x4＋x5 ≥1
x4＋x5＋x6 ≥1
x2 ＋x5＋x6 ≥1
xi＝1或0 （i＝1，…，6）
4.7 乙個登山隊員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通訊器材等，每種物品的重量及重要性係數見表4－10所示，能攜帶的最大重量為25 kg，試選擇該隊員所應攜帶的物品。
表4－10
解：引入0－1變數xi
（i＝1，…，7）
則0－1規劃模型為：
max z＝20x1＋15x2＋16x3＋14x4＋8x5＋14x6＋9x7
5x1＋5x2＋2x3＋5x4＋10x5＋2x6＋3x7≤25
xi＝0或1，i＝1，0，…，7
課內實驗 運籌學 整數規劃 第三次
課內實驗報告 課程名 運籌學 任課教師 專業學號 姓名2015 2016學年第 2 學期 南京郵電大學通達學院商學院 實驗背景 某公司計畫在市區的東 西 南 北四區建立銷售中心，擬議中有10個位置 aj j 1，2，3，10 可供選擇，考慮到各地區居民的消費水平及居民居住密集度，規定 在東區由a1 ...
運籌學 線性規劃
數學與計算科學學院 實驗報告 實驗專案名稱線性規劃 所屬課程名稱運籌學b 實驗型別綜合實驗 實驗日期 班級成績 附錄1 源程式 附錄2 實驗報告填寫說明 1 實驗專案名稱 要求與實驗教學大綱一致.2 實驗目的 目的要明確，要抓住重點，符合實驗教學大綱要求.3 實驗原理 簡要說明本實驗專案所涉及的理論...
第二章運籌學線性規劃
主要內容 1 線性規劃問題及數學模型 2 線性規劃問題的解及其性質 3 法 4 單純形法 5 大m法和兩階段法 重點與難點 線性規劃數學模型的建立 一般形成轉化為標準型的方法 單純形法的求解步驟。要求 理解本章內容，掌握本章重點與難點問題 深刻理解線性規劃問題的基本概念 基本性質，熟練掌握其求解技巧...