線性規(guī)劃（Linear programming，簡稱LP）是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法。英文縮寫LP。它是運(yùn)籌學(xué)的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。
一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。
簡介
線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料。二是生產(chǎn)組織與計(jì)劃的改進(jìn)，即合理安排人力物力資源。線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好。一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。
標(biāo)準(zhǔn)型
描述線性規(guī)劃問題的常用和最直觀形式是標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型包括以下三個(gè)部分：
一個(gè)需要極大化的線性函數(shù):
以下形式的問題約束：
和非負(fù)變量：
其他類型的問題，例如極小化問題，不同形式的約束問題，和有負(fù)變量的問題，都可以改寫成其等價(jià)問題的標(biāo)準(zhǔn)型。
模型建立
從實(shí)際問題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟；
1.根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；
2.由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；
3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。
所建立的數(shù)學(xué)模型具有以下特點(diǎn)：
1、每個(gè)模型都有若干個(gè)決策變量（），其中n為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。
2、目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問題可以是最大化（max）或最小化（min），二者統(tǒng)稱為最優(yōu)化（opt）。
3、約束條件也是決策變量的線性函數(shù)。
當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。
例：
生產(chǎn)安排模型：某工廠要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時(shí)及A、B兩種原材料的消耗，如表所示，表中右邊一列是每日設(shè)備能力及原材料供應(yīng)的限量，該工廠生產(chǎn)一單位產(chǎn)品Ⅰ可獲利2元，生產(chǎn)一單位產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安排生產(chǎn)，使其獲利最多？
解：
1、確定決策變量：設(shè)分別為產(chǎn)品Ⅰ、Ⅱ的生產(chǎn)數(shù)量；
2、明確目標(biāo)函數(shù)：獲利最大，即求最大值；
3、所滿足的約束條件：
設(shè)備限制：
原材料A限制：
原材料B限制：
基本要求：
用max代替最大值，s.t.（subject to 的簡寫）代替約束條件，則該模型可記為：
解法
求解線性規(guī)劃問題的基本方法是單純形法，現(xiàn)在已有單純形法的標(biāo)準(zhǔn)軟件，可在電子計(jì)算機(jī)上求解約束條件和決策變量數(shù)達(dá) 10000個(gè)以上的線性規(guī)劃問題。為了提高解題速度，又有改進(jìn)單純形法、對聯(lián)單純形法、原始對偶方法、分解算法和各種多項(xiàng)式時(shí)間算法。對于只有兩個(gè)變量的簡單的線性規(guī)劃問題，也可采用圖解法求解。這種方法僅適用于只有兩個(gè)變量的線性規(guī)劃問題。它的特點(diǎn)是直觀而易于理解，但實(shí)用價(jià)值不大。通過圖解法求解可以理解線性規(guī)劃的一些基本概念。
對于一般線性規(guī)劃問題：
其中A為一個(gè)矩陣。
若A行滿秩
則可以找到基矩陣B，并尋找初始基解。
用N表示對應(yīng)于B的非基矩陣。則規(guī)劃問題1可化為：
規(guī)劃問題2：
（1）
（2）
（1）兩邊同乘于，得
同時(shí)，由上式得，也代入目標(biāo)函數(shù)，問題可以繼續(xù)化為：
規(guī)劃問題3：
（1）
（2）
令則上述問題化為規(guī)劃問題形式4：
（1）
（2）
在上述變換中，若能找到規(guī)劃問題形式4，使得，稱該形式為初始基解形式。
上述的變換相當(dāng)于對整個(gè)擴(kuò)展矩陣（包含C及A）乘以增廣矩陣。所以重在選擇B，從而找出對應(yīng)的CB。
若存在初始基解
若
則同時(shí)，令，這是一個(gè)可行解，且此時(shí)，即達(dá)到最優(yōu)值。所以，此時(shí)可以得到最優(yōu)解。
若不成立
可以采用單純形表變換。
σ中存在分量。這些負(fù)分量對應(yīng)的決策變量編號中，最小的為j。N中與j對應(yīng)的列向量為P_j。
若不成立
則Pj至少存在一個(gè)分量ai，j為正。在規(guī)劃問題4的約束條件（1）的兩邊乘以矩陣T。
T=
則變換后，決策變量xj成為基變量，替換掉原來的那個(gè)基變量。為使得（其中，ei表示第i個(gè)單位向量），需要：
其中。即。
n 若aq，，上式一定成立。
n 若aq，，則需要因此，要選擇i使得，最小。
如果這種方法確定了多個(gè)下標(biāo)，選擇下標(biāo)最小的一個(gè)。
轉(zhuǎn)換后得到規(guī)劃問題4的形式，繼續(xù)對σ進(jìn)行判斷。由于基解是有限個(gè)，因此，一定可以在有限步跳出該循環(huán)。
若對于每一個(gè)
最優(yōu)值無界。
若不能尋找到初始基解
無解。
若A不是行滿秩
化簡直到A行滿秩，轉(zhuǎn)到若A行滿秩。
發(fā)展
法國數(shù)學(xué)家J.- B.- J.傅里葉和C.瓦萊－普森分別于1832和1911年獨(dú)立地提
出線性規(guī)劃的想法，但未引起注意。
1939年蘇聯(lián)數(shù)學(xué)家Л.В.康托羅維奇在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書中提出線性規(guī)劃問題，也未引起重視。
1947年美國數(shù)學(xué)家G.B.Dantzing提出求解線性規(guī)劃的單純形法，為這門學(xué)科奠定了基礎(chǔ)。
1947年美國數(shù)學(xué)家J.von諾伊曼提出對偶理論，開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。
1951年美國經(jīng)濟(jì)學(xué)家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾獎(jiǎng)。
50年代后對線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，1956年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。
線性規(guī)劃的研究成果還直接推動了其他最優(yōu)化問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問題。
1979年蘇聯(lián)數(shù)學(xué)家L. G. Khachian提出解線性規(guī)劃問題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。
1984年美國貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的。現(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。建立線性規(guī)劃模型的方法
高校教材
·出版社：武漢大學(xué)出版社
·頁碼：370 頁
·出版日期：2008年06月
·ISBN：7307041014/9787307041011
·條形碼：9787307041011
·版本：第2版
·裝幀：平裝
·開本：16
·正文語種：中文
·叢書名：高等學(xué)校數(shù)學(xué)系列教材
內(nèi)容簡介
線性規(guī)劃是運(yùn)籌學(xué)的重要分支，它是一門實(shí)用性很強(qiáng)的應(yīng)用數(shù)學(xué)學(xué)科。隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，線性規(guī)劃的應(yīng)用越來越廣泛。它已成為人們?yōu)楹侠砝糜邢拶Y源制訂最佳決策的有力工具。《線性規(guī)劃》系統(tǒng)地介紹了線性規(guī)劃知識，包括單純形方法、對聯(lián)原理與對偶算法、靈敏度分析、分解算法、內(nèi)點(diǎn)算法，以及整數(shù)線性規(guī)劃等。《線性規(guī)劃》適于用做高等院校、師范院校有關(guān)專業(yè)的線性規(guī)劃課教材。
目錄
前言
第一章 線性規(guī)劃問題
1.1 線性規(guī)劃問題的實(shí)例
1.2 線性規(guī)劃問題的數(shù)學(xué)模型
1.3 二變量線性規(guī)劃問題的圖解法
本章小結(jié)
復(fù)習(xí)題
第二章 單純形方法
2.1 基可行解
2.2 最優(yōu)基可行解的求法
2.3 單純形法的計(jì)算步驟、單純形表
2.4 退化情形的處理
2.5 初始基可行解的求法
2.6 單純形法的幾何意義
2.7 改進(jìn)單純形法
本章小結(jié)
復(fù)習(xí)題
第三章 對偶原理與對偶算法
3.1 對偶線性規(guī)劃問題
3.3 對偶單純形法
3.4 初始正則解的求法
3.5 原-對偶單純形法
本章小結(jié)
復(fù)習(xí)題
第四章 運(yùn)輸問題
4.1 運(yùn)輸問題的特性
4.2 初始方案的求法
4.3 檢驗(yàn)數(shù)的求法
4.4 方案的調(diào)整
4.5 不平衡的運(yùn)輸問題
4.6 分派問題
本章小結(jié)
復(fù)習(xí)題
第五章 有界變量線性規(guī)劃問題
5.1 基解的特征
5.2 有界變量單純形法
5.3 有界變量對偶單純形法
本章小結(jié)
復(fù)習(xí)題
第六章 靈敏度分析與參數(shù)線性規(guī)劃問題
6.1 靈敏度分析
6.2 參數(shù)線性規(guī)劃問題
本章小結(jié)
復(fù)習(xí)題
第七章 整數(shù)線性規(guī)劃
7.1 幾個(gè)典型的整數(shù)線性規(guī)劃問題
7.2 割平面法
7.3 分枝定界法
7.4 隱枚舉法
7.5 建立整數(shù)規(guī)劃模型的一些技巧
本章小結(jié)
復(fù)習(xí)題
第八章 分解算法
8.1 可行解的分解表達(dá)式
8.2 二分算法
8.3 p分算法
本章小結(jié)
復(fù)習(xí)題
第九章 內(nèi)點(diǎn)算法
9.1 原仿射尺度法
9.2 對偶仿射尺度法
9.3 對數(shù)障礙函數(shù)法
本章小結(jié)
復(fù)習(xí)題
習(xí)題答案
索 引
編者語
序言
本教材主要為管理學(xué)、經(jīng)濟(jì)學(xué)等專業(yè)本科生而編寫，也可以作為其他專業(yè)的學(xué)習(xí)參考書。在本書的編寫過程中，主要體現(xiàn)了如下幾個(gè)特點(diǎn)：
1.線性規(guī)劃已經(jīng)具有成熟的理論與方法，本書既力爭在內(nèi)容形式上保持理論體系的完整性，也嘗試使用幾何直觀來解釋其概念與方法，努力做到推導(dǎo)嚴(yán)謹(jǐn)、通俗易懂。
2.內(nèi)容由淺入深、理論結(jié)合實(shí)際。比如通過實(shí)例討論，引入逐步逼近最優(yōu)解的迭代思想與方法，并由此導(dǎo)出單純性方法原理；在單純性方法的基礎(chǔ)上，給出了不同的優(yōu)化求解方法，并分析了各種方法之間的聯(lián)系與差別。
3.突出課程特點(diǎn)，注重實(shí)際應(yīng)用。例題、習(xí)題選取新穎，緊密結(jié)合經(jīng)濟(jì)與管理專業(yè)的實(shí)際需要，為學(xué)生學(xué)以致用、理論聯(lián)系實(shí)際，培養(yǎng)學(xué)生解決實(shí)際問題的能力奠定基礎(chǔ)。對于手工計(jì)算求解的題目，則重點(diǎn)突出方法訓(xùn)練，而盡量避免復(fù)雜運(yùn)算或大量重復(fù)運(yùn)算的現(xiàn)象。
4.本書安排了必修內(nèi)容和選修內(nèi)容，可滿足40學(xué)時(shí)或48學(xué)時(shí)的教學(xué)要求。每章內(nèi)容之后配有適量練習(xí)題，并在全書后面安排了總練習(xí)題。既滿足基本概念、基本方法的訓(xùn)練，也為學(xué)生全面復(fù)習(xí)提供了基本素材。
本書在編寫中受到了教研室同仁的大力支持，浙江大學(xué)出版社為本書的順利出版付出了大量勞動，在此表示衷心感謝！
由于水平有限，書中可能存在一定的錯(cuò)誤或不足之處，敬請讀者或同行批評指正。
作者簡介
唐曉文，福建工程學(xué)院數(shù)理系教授。主要研究方向?yàn)榫仃嚴(yán)碚摗Ｖ鞒帧案叩却鷶?shù)”福建省省級精品課程。參與“車輛橡膠配件動態(tài)性能測試設(shè)備的研發(fā)”等福建省科技廳項(xiàng)目，主持“廣義嚴(yán)格對角占優(yōu)矩陣與非奇M-矩陣的判定及應(yīng)用的研究”、“幾類特殊矩陣的判定及其應(yīng)用研究”等項(xiàng)目。主編《線性代數(shù)》等教材多部。撰寫、發(fā)表的論文有Stable，Analysis of a Pedalor-prev，SIRS Model with 色彩飽和度 Infectious Force、《數(shù)學(xué)教學(xué)觀的轉(zhuǎn)變與發(fā)展創(chuàng)新》、 《相互競爭的兩種群中具有飽和傳染率的sIRs模型的穩(wěn)定性分析》等多篇。劉海英，福建開放大學(xué)電子信息與計(jì)算機(jī)系副教授。主要研究方向?yàn)橛?jì)算數(shù)學(xué)。參加工作以來發(fā)表論文十余篇，主要有《基于多傳感器信息融合技術(shù)》、《信息融合在空間點(diǎn)目標(biāo)識別中的應(yīng)用》、《基于信息融合理論的空間點(diǎn)目標(biāo)識別實(shí)驗(yàn)結(jié)果分析》、《最短路徑問題在管理中的應(yīng)用》等。主持課題“BP神經(jīng)網(wǎng)絡(luò)算法研究”、“基于Dijkstra算法的最短路徑改進(jìn)算法”、“利用Excel軟件優(yōu)化企業(yè)資源配置”、“線性規(guī)劃方法的應(yīng)用”等十余項(xiàng)。
參考資料 >