一課件第四章四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ù)的多重選擇 固定費(fèi)用問題 相互排斥的計(jì)劃該公司只有600萬資金可用于投資，由于技術(shù)上的原因，投資受到以下約束： 1、在項(xiàng)目1、2和3中必須有一項(xiàng)被選中 2、項(xiàng)目3和4只能選中一項(xiàng) 3、項(xiàng)目5被選中的前提是項(xiàng)目1被選中;如何 在 滿足上述條件下選擇一個(gè)最好的投資 方 案

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

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

4、利潤為最大。 解：這是一個(gè)整數(shù)規(guī)劃的問題。 設(shè)x1，x2， x3 分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說明固定費(fèi)用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第 i種容器, 即 xi 0 時(shí)) 或0（當(dāng)不生產(chǎn)第 i種容器即 xi = 0 時(shí)）。 引入約束 xi M yi ，i =1，2，3，M充分大，以保證當(dāng) yi = 0 時(shí)，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二、過濾隱枚舉法（適合于變量個(gè)數(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