原文章：MATLAB求解線性規(guī)劃（含整數(shù)規(guī)劃和0-1規(guī)劃）問題
博主：一尺丈量

最有用的方法：
matlab官方文檔，搜索linprog函數(shù)和intlinprog函數(shù)赵抢。
https://www.mathworks.com/products/matlab.html

@[TOC]

線性規(guī)劃簡(jiǎn)介

線性規(guī)劃是數(shù)學(xué)規(guī)劃中的一類最簡(jiǎn)單規(guī)劃問題牲芋，常見的線性規(guī)劃是一個(gè)有約束的，變量范圍為有理數(shù)的線性規(guī)劃。如：

對(duì)于這類線性規(guī)劃問題庶柿，數(shù)學(xué)理論已經(jīng)較為完善看铆，可以有多種方法求解此類問題。但寫這篇文章的目的并不是為了介紹數(shù)學(xué)理論剩彬，我們這里主要講解如果利用工具求解這一類線性規(guī)劃問題酷麦。

最著名，同時(shí)也是最強(qiáng)大的數(shù)學(xué)最優(yōu)化軟件是LINGO/LINDO軟件包喉恋，它能夠求解多種的數(shù)學(xué)規(guī)劃問題沃饶，同時(shí)還提供了多種的分析能力母廷。但LINGO軟件并不容易上手，同時(shí)糊肤，應(yīng)用LINGO的場(chǎng)合一般是大規(guī)模的線性規(guī)劃問題琴昆，小小的線性規(guī)劃完全可以不使用它。一個(gè)更受科研人員歡迎的數(shù)學(xué)軟件是MATLAB轩褐，它以功能強(qiáng)大而稱著椎咧，并有數(shù)學(xué)軟件中的“航空母艦”之稱。我們這里就是要學(xué)習(xí)使用MATLAB軟件求解線性規(guī)劃（含整數(shù)規(guī)劃和0-1規(guī)劃）問題把介。

為了使得不熟悉MATLAB的人員也能夠使用MATLAB進(jìn)行線性規(guī)劃問題求解勤讽，本文將對(duì)MATALB中使用到的函數(shù)和過程以及結(jié)果進(jìn)行詳細(xì)的分析，最后會(huì)對(duì)每一個(gè)問題都給出一個(gè)可以完全“套用”的MATLAB程序拗踢。

我們首先從上面的線性規(guī)劃問題開始脚牍，為了便于表達(dá)，將上面的式子寫成矩陣形式：

于是約束就表達(dá)為了一個(gè)不等式巢墅。

用linprog函數(shù)解決線性規(guī)劃

求解MATLAB線性規(guī)劃時(shí)诸狭，最常用的函數(shù)是linprog函數(shù)，下面來介紹一下這個(gè)函數(shù)的使用君纫。

打開MATLAB幫助文檔（PS:幫助文檔的內(nèi)容是最全的驯遇，只要你的英文過了專業(yè)8級(jí)），可以看到linprog函數(shù)求解的是具有如下標(biāo)準(zhǔn)形式的線性規(guī)劃：

公式中各符號(hào)的意義是自明的蓄髓，在這里簡(jiǎn)單介紹下叉庐，首先MATLAB中求解的是目標(biāo)函數(shù)是最小值的問題，但如果我們的目標(biāo)函數(shù)是求最大值会喝，可以通過對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1陡叠，將求最大值問題轉(zhuǎn)化為求最小值問題；A肢执，b分別為不等式約束中的系數(shù)矩陣枉阵。Aeq和beq分別為等式約束中的系數(shù)矩陣，lb预茄，和ub分別為每個(gè)變量的上下區(qū)間兴溜；最后f為目標(biāo)函數(shù)中各變量的系數(shù)矩陣。

現(xiàn)在耻陕，是時(shí)候動(dòng)動(dòng)手昵慌，使用MATLAB編寫代碼求解這個(gè)線性規(guī)劃了。MATLAB代碼如下所示：

f=[-7,-12];
A=[9 4;4 5;3 10];
b=[300;200;300];
lb=zeros(2,1);% 生成一個(gè)2行1列的全0矩陣,很顯示淮蜈，上面例子中的x,y的最小值為0
[x,fval]=linprog(f,A,b,[],[],lb,[])

我們來解釋下linprog函數(shù)中每參數(shù)的意義，linprog中的一個(gè)原型如下：

[x,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,ub)

這7個(gè)參數(shù)的意義和上面f已卷、A梧田、b的意義是一樣的。f為目標(biāo)函數(shù)的系數(shù)矩陣，A為線性規(guī)劃不等式約束的變量系數(shù)矩陣裁眯，b為不等式約束的資源數(shù)（如上面的[300;200;300]）鹉梨，這是一個(gè)N行1列的矩陣，N為變量的個(gè)數(shù)穿稳。Aeq和beq是相應(yīng)等式約束的變量系數(shù)矩陣和資源數(shù)（很明顯存皂，上面的例子中并沒有等式約束）。lb和ub分別為保變量的上下區(qū)間逢艘。在上面的例子中旦袋，x和y和最小值都為0但都無最大值約束。而linprog的返回值x為求得的各變量的值它改，這是一個(gè)向量疤孕，fval為最優(yōu)化的值，一般是一個(gè)標(biāo)量央拖，exitflag意為函數(shù)的退出標(biāo)志祭阀。

上面所示的代碼[x,fval]=linprog(f,A,b,[],[],lb,[])中，[]代表不存在或空鲜戒，因?yàn)樵谏厦娴睦又胁淮嬖诘仁郊s束专控，所以Aeq和beq的位置為[]。而ub也為空遏餐，是因?yàn)樽兞繘]有最大值約束伦腐。

運(yùn)行上面的程序，行到結(jié)果為：

x =

  20.0000

  24.0000

fval =

  -428.0000

解釋為：

當(dāng)x=20,y=24時(shí)境输，可以求得最優(yōu)化的值蔗牡，最大值為428（因?yàn)檫@里的求目標(biāo)最大值，但MATLAB只能求目標(biāo)函數(shù)最小值嗅剖，所以對(duì)目標(biāo)函數(shù)進(jìn)行了乘-1處理辩越，所以也要對(duì)最后的結(jié)果乘以-1才是目標(biāo)函數(shù)所求）.

用intlinprog函數(shù)解決整數(shù)規(guī)劃

上面解決了簡(jiǎn)單的線性規(guī)劃問題的求解，線性規(guī)范有兩種比較特殊的情況信粮，即整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃黔攒。在之前（不知MATLAB幾之前……），MATLAB是不能直接求解這兩種規(guī)劃的强缘，bintprog函數(shù)可以用來求0-1整數(shù)規(guī)劃督惰，但求解過程比較麻煩，而且最新版的MATLAB已經(jīng)遺棄了這個(gè)函數(shù)旅掂，同時(shí)提供了一個(gè)比較新的赏胚、專用于求解整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃的函數(shù)——intlinprog。intlinprog的一個(gè)原型為：

[x,fval,exitflag]= intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

該函數(shù)的使用和linprog函數(shù)的使用十分相似商虐，其僅僅在linprog函數(shù)的基礎(chǔ)上多了一個(gè)參數(shù)——intcon觉阅。我們來通過下面的例子來學(xué)習(xí)該參數(shù)的意義崖疤。

在這里例子中，變量的取值范圍不再是有理數(shù)集典勇，而是整數(shù)集劫哼。求解此規(guī)劃問題的MATLAB程序如下：

f_13=[-1,-1];
ic_13=[1,2];
A_13=[-4,2;4,2;0,-2];
b_13=[-1;11;-1];
lb_13=zeros(2,1);
[x_13,fval_13,flag_13]=intlinprog(f_13,ic_13,A_13,b_13,[],[],lb_13,[])

在函數(shù)intlinprog中，intcon的意義為整數(shù)約束變量的位置割笙。如上例中权烧，因?yàn)閤1和x2都要是整數(shù)，intcon參數(shù)位置ic_13的值為[1,2]伤溉。這個(gè)位置是按照目標(biāo)函數(shù)和約束條件中變量位置來排列的般码。如果上式中僅有x2為整數(shù)約束，那么ic_13的值應(yīng)該為2谈火。

需要說明的是侈询，intlinprog函數(shù)在比較舊版本是不支持的（筆者使用的是MATLAB2014B），如果你發(fā)現(xiàn)你現(xiàn)在的MATLAB沒有intlinprog函數(shù)糯耍，請(qǐng)不要吃驚扔字，因?yàn)橐恢币詠恚琈ATLAB都是無法直接求解整數(shù)規(guī)劃的温技，但今時(shí)已經(jīng)不同往日了革为。

0-1規(guī)劃

現(xiàn)在又有了一個(gè)新問題，我們解決了在MATLAB上求解一般的整數(shù)規(guī)劃問題舵鳞，但要是遇到0-1整數(shù)規(guī)劃問題呢震檩？到這里，我們只要轉(zhuǎn)換一下思維蜓堕，就可以利用MATLAB求解0-1整數(shù)規(guī)劃了抛虏，這里先賣個(gè)關(guān)子，請(qǐng)大家看下面的例子是怎么用MATLAB求解0-1整數(shù)規(guī)劃的套才。

MATLAB程序如下：

f_12=[7 5 9 6 3];
ic_12=[1,2,3,4,5];
A_12=[56,20,54,42,15;1,4,1,0,0;-1,-2,0,-1,-2];
b_12=[100;4;-2];
lb_12=zeros(5,1);
ub_12=ones(5,1);
[x_12,fval_12,flag_12]=intlinprog(f_12,ic_12,A_12,b_12,[],[],lb_12,ub_12)

有木有發(fā)現(xiàn)在迂猴，與上面整數(shù)規(guī)劃不同的地方只有一個(gè)，就是多了ub_12=ones(5,1)背伴，也就是說求解0-1整數(shù)規(guī)劃只要在求解整數(shù)規(guī)劃的基礎(chǔ)上加上一個(gè)對(duì)變量最大值約束為1就行了沸毁，有木有恍然大悟的感覺？傻寂？息尺？

后面兩個(gè)程序并沒有給出程序運(yùn)行的結(jié)果，因?yàn)楣P者堅(jiān)信學(xué)習(xí)最好的方式就是“動(dòng)手”疾掰。^_