如何用matlab求解0 1規劃問題

時間 2022-05-16 23:45:14

1樓:匿名使用者

§3 0 −1型整數規劃

0 −1型整數規劃是整數規劃中的特殊情形,它的變數j x 僅取值0 或1。這時j x 稱

為0 −1變數,或稱二進位制變數。j x 僅取值0 或1 這個條件可由下述約束條件:

0 ≤ ≤ 1 j x ,整數所代替,是和一般整數規劃的約束條件形式一致的。在實際問題中,如果引入0 −1變

量,就可以把有各種情況需要分別討論的線性規劃問題統一在一個問題中討論了。我們

先介紹引入0 −1變數的實際問題,再研究解法。

如果有m 個互相排斥的約束條件:

a x a x b i m i in n i 1,2, , 1 1 +l+ ≤ = l

為了保證這m 個約束條件只有一個起作用,我們引入m 個0 −1變數y (i 1,2, ,m) i = l

和一個充分大的常數m ,而下面這一組m +1個約束條件

a x a x b y m i m i in n i i 1,2, , 1 1 +l+ ≤ + = l (1)

1 1 y + + y = m − l m (2)

就合於上述的要求。這是因為,由於(2),m 個i y 中只有一個能取0 值,設0 * = i y ,

代入(1),就只有i = i*的約束條件起作用,而別的式子都是多餘的。

3.2 0 −1型整數規劃解法之一(過濾隱列舉法)

解0 −1型整數規劃最容易想到的方法,和一般整數規劃的情形一樣,就是窮舉法,

即檢查變數取值為0 或1 的每一種組合,比較目標函式值以求得最優解,這就需要檢查

變數取值的2n個組合。對於變數個數n較大(例如n >100),這幾乎是不可能的。因

此常設計一些方法,只檢查變數取值的組合的一部分,就能求到問題的最優解。這樣的

方法稱為隱列舉法(implicit enumeration),分枝定界法也是一種隱列舉法。當然,對有些問題隱列舉法並不適用,所以有時窮舉法還是必要的。

蒙特卡洛法(隨機取樣法)

前面介紹的常用的整數規劃求解方法,主要是針對線性整數規劃而言,而對於非線

性整數規劃目前尚未有一種成熟而準確的求解方法,因為非線性規劃本身的通用有效解

法尚未找到,更何況是非線性整數規劃。

然而,儘管整數規劃由於限制變數為整數而增加了難度;然而又由於整數解是有限

個,於是為列舉法提供了方便。當然,當自變數維數很大和取值範圍很寬情況下,企圖

用顯列舉法(即窮舉法)計算出最優值是不現實的,但是應用概率理論可以證明,在一

定的計算量的情況下,完全可以得出一個滿意解。

指派問題的計算機求解

整數規劃問題的求解可以使用 lingo 等專用軟體。對於一般的整數規劃問題,無法

直接利用matlab 的函式,必須利用matlab 程式設計實現分枝定界解法和割平面解法。但對

於指派問題等0 −1整數規劃問題,可以直接利用matlab 的函式bintprog 進行求解。

2樓:我都吃了三碗了

你是數學建模的吧,我也在愁這個問題

matlab程式設計:0-1規劃問題:向高手求程式**。

3樓:淡淡幽情

建立數學模型

設xi=1表示ai被選中,xi=0表示ai沒被選中。

則數學模型是:

max 1500x1+2000x2+1300x3+2300x4+2800x5

s.t.   x1+x2=1

x4+x5=1

x1+x4<=1

x2-x5=0

xi=0或1,i=1,2,3,4,5

2.程式設計求解

matlab程式:

f = [-1500 -2000 -1300 -2300 -2800];

a = [1 0 0 1 0];

b = 1;

aeq = [1 1 0 0 0;0 0 0 1 1;0 1 0 0 -1];

beq = [1;1;0];

x = bintprog(f,a,b,aeq,beq)解出來是:

x =011

01也就是說運送a2,a3,a5

matlab求解非線性約束方程,求教 如何用matlab解帶約束的非線性方程組

用fmincon函式就可以解決,以下是fmincon的說明,你照葫蘆畫就可以了。這個函式的基本形式為 x fmincon fun,x0,a,b,aeq,beq,lb,ub,nonlcon,options 其中fun為你要求最小值的函式,可以單寫一個檔案設定函式,如以上給的例子中。1.如果fun中有n...

如何用matlab的plot命令畫出ysin1的圖形

墨汁諾 x 1 0.02 1 plot x,sin 1.x 語句中的點代表對於元素相除,除0並不是錯誤,僅僅是內部資料溢位而已,可以不用管。x 0 0.1 10 y sin x plot x,y 例如 根據已知函式可知,在x 0處有間斷點,所以繪製該函式圖形,應避開該間斷點。圖形實現 如下 x 10...

matlab如何用if自定義分段函式

1 與建立m檔案類似,在命令視窗中輸入edit。2 編寫函式,需要注意函式命名規則,註釋部分可有可無,用 開始。3 編寫完成後儲存檔案,最好儲存在當前工作路徑的資料夾。4 直接輸入函式名,形參,就能返回計算結果。5 和檢視其它函式說明一樣,輸入 help 函式名 就能看到這個函式的註釋說明。 舉個簡...