一課件第四章四0-1問題

1、0-1整數(shù)規(guī)劃 榜上有名 形影不離(夫唱婦隨) 勢不兩立 脫穎而出0-1規(guī)劃的應(yīng)用10做第i件事不做第i件事n件事中必須做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要條件是做第j件事做第i件事的充要條件是不做第j件事只在做了第i件事前提下才考慮是否做第j件事0-1規(guī)劃的應(yīng)用 相互排斥的約束條件 資源系數(shù)的多重選擇 固定費用問題 相互排斥的計劃該公司只有600萬資金可用于投資，由于技術(shù)上的原因，投資受到以下約束： 1、在項目1、2和3中必須有一項被選中 2、項目3和4只能選中一項 3、項目5被選中的前提是項目1被選中;如何 在 滿足上述條件下選擇一個最好的投資 方 案

2、，使投資收益最大例1（投資問題）華美公司有5個項目被列入投資計劃，每個項目的投資額和期望的投資收益見下表：項目投資額（萬元）投資收益（萬元）12101502300210310060413080526018010投資第i個項目不投資第i個項目Z表示投資效益投資項目模型： 例2（布點問題）某城市共有6個區(qū)，每個區(qū)都可以建消防站。市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火火警時，消防車要在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間見右表。地區(qū)12345610101628272021002432171031624012272142832120152552717271501

3、4620102125140 請為該市制定一個最節(jié)省的計劃在第i個地區(qū)建站Z表示全區(qū)消防站總數(shù)不在第i個地區(qū)建站i=1,2, ,6布點問題模型：最優(yōu)解x2=1, x4=1最優(yōu)值Z=2 例3高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費用，每種容器售出一只所得的利潤分別為 4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機器有100臺/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費用：小號是l00萬元，中號為 150 萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的

4、利潤為最大。 解：這是一個整數(shù)規(guī)劃的問題。 設(shè)x1，x2， x3 分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第 i種容器, 即 xi 0 時) 或0（當(dāng)不生產(chǎn)第 i種容器即 xi = 0 時）。 引入約束 xi M yi ，i =1，2，3，M充分大，以保證當(dāng) yi = 0 時，xi = 0 。 這樣我們可建立如下的數(shù)學(xué)模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 為0-1變量，i = 1,2,3二、過濾隱枚舉法（適合于變量個數(shù)較少的0-1規(guī)劃）（x1 x2 x3)Z值 約束條件（1）（2）（3）（4）過濾條件（0 0 0）（0 0 1）（0 1 0）（1 0 0）（1 0