0-1規(guī)劃的介紹

0-1規(guī)劃是決策變量僅取值0或1的一類特殊的整數(shù)規(guī)劃。在處理經(jīng)濟(jì)管理中某些規(guī)劃問題時，若決策變量采用 0-1變量即邏輯變量，可把本來需要分別各種情況加以討論的問題統(tǒng)一在一個問題中討論。

求解 0-1 規(guī)劃的方法主要是隱枚舉法（如分枝定界法）。對一些特殊問題還有一些更加有效的方法，例如對指派問題，用D.柯尼希發(fā)明的匈牙利法求解更顯方便有效。

0-1 規(guī)劃問題一般有三種解法，即變換法、窮舉法和隱枚舉法。變換法用于解特殊的 0-1 規(guī)劃問題。窮舉法就是檢查變量取值為 0 或 1 的每一種組合，比較目標(biāo)函數(shù)值來求最優(yōu)解，這就需要檢查變量取值的 2n個組合。對于 n>10 的情況，這幾乎是辦不到的。

因此常設(shè)計一些方法，只檢查變量取值組合的一部分，就能得到問題的最優(yōu)解。這樣的方法稱為隱枚舉法。

采用隱枚舉法解 0-1 規(guī)劃問題時要根據(jù)目標(biāo)函數(shù)的性質(zhì)增加一個相應(yīng)的不等式作為附加約束條件，稱為過濾條件，以減少運算次數(shù)。一般還要按目標(biāo)函數(shù)中 xi的系數(shù)遞增的順序，重新排列目標(biāo)函數(shù)和約束條件中 xi的次序，以簡化計算。

0-1規(guī)劃的簡介

0-1規(guī)劃
0-1 Programming
一種特殊形式的整數(shù)規(guī)劃 。這種規(guī)劃的決策變量僅取值0或1，故稱為0-1變量或二進(jìn)制變量 ，因為一個非負(fù)整數(shù)都可以用二進(jìn)制記 數(shù)法用若干個0-1變量表示 。0-1變量可以數(shù)量化地描述諸如開與關(guān)、取與棄、有與無等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件 ，因此0-1規(guī)劃非常適合描述和解決如線路設(shè)計 、工廠選址 、生產(chǎn)計劃安排、旅行購物、背包問題、人員安排、代碼選取、可靠性等人們所關(guān)心的多種問題。實際上，凡是有界變量的整數(shù)規(guī)劃都可以轉(zhuǎn) 化為0-1規(guī)劃來處理 。由于0-1規(guī)劃具有深刻的背景和廣泛的應(yīng)用，幾十年來一直受到人們的重視 。
求解0-1規(guī)劃的方法主要是隱枚舉法（如分枝定界法）。對一些特殊問題還有一些更加有效的方法，例如對指派問題，用D.柯尼希發(fā)明的匈牙利法求解更顯方便有效。

混合整數(shù)規(guī)劃與0-1規(guī)劃有什么關(guān)系？區(qū)別又是什么？

混合整數(shù)規(guī)劃與0-1規(guī)劃都屬于整數(shù)規(guī)劃。區(qū)別是0-1規(guī)劃屬于純整數(shù)規(guī)劃，它的決策變量均為整數(shù)，且只能取值0或1。而混合整數(shù)規(guī)劃只要求部分變量取整數(shù)值。

求解0-1整收規(guī)劃:Max z=3X1-2X2+5X3

例 求解下列0-1整數(shù)線性規(guī)劃 目標(biāo)函數(shù) max f=-3x1+2x2-5x3 約束條件 x1+2x2-x3≤2， x1+4x2+x3≤4， x1+x2≤3， 4x1+x3≤6， x1，x2，x3為0或1. 在Matlab命令窗口中輸入如下命令： f=[-3,2,-5]; a=[1,2,-1,;1,4,1;1,1,0;0,4,1];b=[2;4;3;6]; [x,fval]=bintprog(-f,a,b) %因為bintprog求解的為目標(biāo)函數(shù)的最小值，所以要在f前面加個負(fù)號。 運行結(jié)果為： Optimization terminated. x = 0 1 0 fval = -2 表示x1=

lingo 中的 0-1規(guī)劃能否具體舉例說明？？

lingo中的0-1規(guī)劃具體舉例說明：

1、模型的建立與求解，用xi =1表示選修表1中按編號順序的9門課程（xi =0表示不選；i =1,2,……9) . 問題的目標(biāo)為選修的課程總數(shù)最少。

2、以式（1.1）為目標(biāo)的函數(shù)，以式（1.2）～式（1.10）為約束條件的0-1 規(guī)劃模型，將這一模型輸入LINGO（注意加上xi為0-1的約束），求解得到結(jié)果為x1=x2=x3=x4=x5=x6=x7=x8=x=1。

3、其他變量為0，對照課程編號，它們是微積分、線性代數(shù)、最優(yōu)化方法、計算機(jī)模擬、計算機(jī)編程、數(shù)學(xué)實驗，共6 門課程，總學(xué)分為21。

概念分析

在使用使用@POSD函數(shù)時，通過增加的Semi-Definite Program (SDP)/Positive Definite (POSD)功能來增強(qiáng)圓錐曲線求解器選項的功能。例如，如果你在估計協(xié)方差矩陣的組合的時候，可以使用@POSD函數(shù)迫使矩陣是半正定的，這是任何協(xié)方差矩陣的必須需的性質(zhì) 。

背包問題相關(guān)的削減性改進(jìn)，一些背包問題模型的求解速率明顯增強(qiáng)。改進(jìn)的默認(rèn)節(jié)點選擇規(guī)則增強(qiáng)了對大部分整數(shù)規(guī)劃模型的性能。