線性規劃

線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法。在經濟管理、交通運輸、工農業生產等經濟活動中，提高經濟效果是人們不可缺少的要求，而提高經濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產工藝，使用新設備和新型原材料。二是生產組織與計劃的改進，即合理安排人力物力資源。線性規劃所研究的是：在一定條件下，合理安排人力物力等資源，使經濟效果達到最好。一般地，求線性目標函數在線性約束條件下的最大值或最小值的問題，統稱為線性規劃問題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變數、約束條件、目標函數是線性規劃的三要素。

描述線性規劃問題的常用和最直觀形式是標準型。標準型包括以下三個部分：

一個需要極大化的線性函數:

以下形式的問題約束：

和非負變數：

其他類型的問題，例如極小化問題，不同形式的約束問題，和有負變數的問題，都可以改寫成其等價問題的標準型。

從實際問題中建立數學模型一般有以下三個步驟；

1.根據影響所要達到目的的因素找到決策變數；

2.由決策變數和所在達到目的之間的函數關係確定目標函數；

3.由決策變數所受的限制條件確定決策變數所要滿足的約束條件。

所建立的數學模型具有以下特點：

1、每個模型都有若干個決策變數（x1，x2，x3……，xn），其中n為決策變數個數。決策變數的一組值表示一種方案，同時決策變數一般是非負的。

2、目標函數是決策變數的線性函數，根據具體問題可以是最大化（max）或最小化（min），二者統稱為最優化（opt）。

3、約束條件也是決策變數的線性函數。

當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。

例：

生產安排模型：某工廠要安排生產Ⅰ、Ⅱ兩種產品，已知生產單位產品所需的設備台時及A、B兩種原材料的消耗，如表所示，表中右邊一列是每日設備能力及原材料供應的限量，該工廠生產一單位產品Ⅰ可獲利2元，生產一單位產品Ⅱ可獲利3元，問應如何安排生產，使其獲利最多？

解：

1、確定決策變數：設x1、x2分別為產品Ⅰ、Ⅱ的生產數量；

2、明確目標函數：獲利最大，即求2x1+3x2最大值；

3、所滿足的約束條件：

設備限制：x1+2x2≤8

原材料A限制：4x1≤16

原材料B限制：4x2≤12

基本要求：x1，x2≥0

用max代替最大值，s.t.（subject to 的簡寫）代替約束條件，則該模型可記為：

max z=2x1+3x2

s.t. x1+2x2≤8

4x1≤16

4x2≤12

x1，x2≥0

求解線性規劃問題的基本方法是單純形法，現在已有單純形法的標準軟體，可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解演演算法和各種多項式時間演演算法。對於只有兩個變數的簡單的線性規劃問題，也可採用圖解法求解。這種方法僅適用於只有兩個變數的線性規劃問題。它的特點是直觀而易於理解，但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。

對於一般線性規劃問題： Min z=CX

S.T.

AX =b

X>=0

其中A為一個m*n矩陣。

若A行滿秩

則可以找到基矩陣B，並尋找初始基解。

用N表示對應於B的非基矩陣。則規劃問題1可化為：

規劃問題2：

Min z=CB XB+CNXN

S.T. B XB+N XN = b （1）

XB >= 0， XN >= 0 （2）

（1）兩邊同乘於B-1，得

XB + B-1 N XN = B-1 b

同時，由上式得XB = B-1 b - B-1 N XN，也代入目標函數，問題可以繼續化為：

規劃問題3：

Min z=CB B-1 b + （ CN - CB B-1 N ） XN

S.T.

XB+B-1N XN = B-1 b （1）

XB >= 0， XN >= 0 （2）

令N：=B-1N，b：= B-1 b，ζ= CB B-1b，σ= CN - CB B-1 N，則上述問題化為規劃問題形式4：

Min z= ζ + σ XN

S.T.

XB+ N XN = b （1）

XB >= 0， XN >= 0 （2）

在上述變換中，若能找到規劃問題形式4，使得b>=0，稱該形式為初始基解形式。

上述的變換相當於對整個擴展矩陣（包含C及A）乘以增廣矩陣。所以重在選擇B，從而找出對應的CB。

若存在初始基解

若σ>= 0

則z >=ζ。同時，令XN = 0，XB = b，這是一個可行解，且此時z=ζ，即達到最優值。所以，此時可以得到最優解。

若σ >= 0不成立

可以採用單純形表變換。

σ中存在分量<0。這些負分量對應的決策變數編號中，最小的為j。N中與j對應的列向量為Pj。

若Pj <=0不成立

則Pj至少存在一個分量ai，j為正。在規劃問題4的約束條件（1）的兩邊乘以矩陣T。

T=

則變換后，決策變數xj成為基變數，替換掉原來的那個基變數。為使得T b >= 0，且T Pj=ei（其中，ei表示第i個單位向量），需要：

l ai，j>0。

l βq+βi*（-aq，j/ai，j）>=0，其中q!=i。即βq>=βi/ ai，j * aq，j。

n 若aq，j<=0，上式一定成立。

n 若aq，j>0，則需要βq / aq，j >=βi/ ai，j。因此，要選擇i使得βi/ ai，j最小。

如果這種方法確定了多個下標，選擇下標最小的一個。

轉換后得到規劃問題4的形式，繼續對σ進行判斷。由於基解是有限個，因此，一定可以在有限步跳出該循環。

若對於每一個i，ai，j<=0

最優值無界。

若不能尋找到初始基解

無解。

若A不是行滿秩

化簡直到A行滿秩，轉到若A行滿秩。

法國數學家J.- B.- J.傅里葉和C.瓦萊－普森分別於1832和1911年獨立地提

出線性規劃的想法，但未引起注意。

1939年蘇聯數學家Л.В.康托羅維奇在《生產組織與計劃中的數學方法》一書中提出線性規劃問題，也未引起重視。

1947年美國數學家G.B.Dantzing提出求解線性規劃的單純形法，為這門學科奠定了基礎。

1947年美國數學家J.von諾伊曼提出對偶理論，開創了線性規劃的許多新的研究領域，擴大了它的應用範圍和解題能力。

1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域，為此與康托羅維奇一起獲1975年諾貝爾經濟學獎。

50年代后對線性規劃進行大量的理論研究，並湧現出一大批新的演演算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題，1956年A.塔克提出互補鬆弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解演演算法等。

線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的演演算法研究。由於數字電子計算機的發展，出現了許多線性規劃軟體，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變數的線性規劃問題。

1979年蘇聯數學家L. G. Khachian提出解線性規劃問題的橢球演演算法，並證明它是多項式時間演演算法。

1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間演演算法。用這種方法求解線性規劃問題在變數個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式演演算法理論。50年代后線性規劃的應用範圍不斷擴大。建立線性規劃模型的方法

·出版社：武漢大學出版社

·頁碼：370 頁

·出版日期：2008年06月

·ISBN：7307041014/9787307041011

·條形碼：9787307041011

·版本：第2版

·裝幀：平裝

·開本：16

·正文語種：中文

·叢書名：高等學校數學系列教材

內容簡介

線性規劃是運籌學的重要分支，它是一門實用性很強的應用數學學科。隨著計算機技術的發展和普及，線性規劃的應用越來越廣泛。它已成為人們為合理利用有限資源制訂最佳決策的有力工具。《線性規劃》系統地介紹了線性規劃知識，包括單純形方法、對偶原理與對偶演演算法、靈敏度分析、分解演演算法、內點演演算法，以及整數線性規劃等。《線性規劃》適於用做高等院校、師範院校有關專業的線性規劃課教材。

目錄

前言

第一章 線性規劃問題

1.1 線性規劃問題的實例

1.2 線性規劃問題的數學模型

1.3 二變數線性規劃問題的圖解法

本章小結

複習題

第二章 單純形方法

2.1 基可行解

2.2 最優基可行解的求法

2.3 單純形法的計算步驟、單純形表

2.4 退化情形的處理

2.5 初始基可行解的求法

2.6 單純形法的幾何意義

2.7 改進單純形法

本章小結

複習題

第三章 對偶原理與對偶演演算法

3.1 對偶線性規劃問題

3.2 對偶定理

3.3 對偶單純形法

3.4 初始正則解的求法

3.5 原-對偶單純形法

本章小結

複習題

第四章 運輸問題

4.1 運輸問題的特性

4.2 初始方案的求法

4.3 檢驗數的求法

4.4 方案的調整

4.5 不平衡的運輸問題

4.6 分派問題

本章小結

複習題

第五章 有界變數線性規劃問題

5.1 基解的特徵

5.2 有界變數單純形法

5.3 有界變數對偶單純形法

本章小結

複習題

第六章 靈敏度分析與參數線性規劃問題

6.1 靈敏度分析

6.2 參數線性規劃問題

本章小結

複習題

第七章 整數線性規劃

7.1 幾個典型的整數線性規劃問題

7.2 割平面法

7.3 分枝定界法

7.4 隱枚舉法

7.5 建立整數規劃模型的一些技巧

本章小結

複習題

第八章 分解演演算法

8.1 可行解的分解表達式

8.2 二分演演算法

8.3 p分演演算法

本章小結

複習題

第九章 內點演演算法

9.1 原仿射尺度法

9.2 對偶仿射尺度法

9.3 對數障礙函數法

本章小結

複習題

習題答案

索 引

編者語

本教材主要為管理學、經濟學等專業本科生而編寫，也可以作為其他專業的學習參考書。在本書的編寫過程中，主要體現了如下幾個特點：

1.線性規劃已經具有成熟的理論與方法，本書既力爭在內容形式上保持理論體系的完整性，也嘗試使用幾何直觀來解釋其概念與方法，努力做到推導嚴謹、通俗易懂。

2.內容由淺入深、理論結合實際。比如通過實例討論，引入逐步逼近最優解的迭代思想與方法，並由此導出單純性方法原理；在單純性方法的基礎上，給出了不同的優化求解方法，並分析了各種方法之間的聯繫與差別。

3.突出課程特點，注重實際應用。例題、習題選取新穎，緊密結合經濟與管理專業的實際需要，為學生學以致用、理論聯繫實際，培養學生解決實際問題的能力奠定基礎。對於手工計算求解的題目，則重點突出方法訓練，而盡量避免複雜運算或大量重複運算的現象。

4.本書安排了必修內容和選修內容，可滿足40學時或48學時的教學要求。每章內容之後配有適量練習題，並在全書後面安排了總練習題。既滿足基本概念、基本方法的訓練，也為學生全面複習提供了基本素材。

本書在編寫中受到了教研室同仁的大力支持，浙江大學出版社為本書的順利出版付出了大量勞動，在此表示衷心感謝！

由於水平有限，書中可能存在一定的錯誤或不足之處，敬請讀者或同行批評指正。

唐曉文，福建工程學院數理系教授。主要研究方向為矩陣理論。主持“高等代數”福建省省級精品課程。參與“車輛橡膠配件動態性能測試設備的研發”等福建省科技廳項目，主持“廣義嚴格對角佔優矩陣與非奇M-矩陣的判定及應用的研究”、“幾類特殊矩陣的判定及其應用研究”等項目。主編《線性代數》等教材多部。撰寫、發表的論文有Stable，Analysis of a Pedalor-prev，SIRS Model with Saturation Infectious Force、《數學教學觀的轉變與發展創新》、 《相互競爭的兩種群中具有飽和傳染率的sIRs模型的穩定性分析》等多篇。劉海英，福建廣播電視大學電子信息與計算機系副教授。主要研究方向為計算數學。參加工作以來發表論文十餘篇，主要有《基於多感測器信息融合技術》、《信息融合在空間點目標識別中的應用》、《基於信息融合理論的空間點目標識別實驗結果分析》、《最短路徑問題在管理中的應用》等。主持課題“BP神經網路演演算法研究”、“基於Dijkstra演演算法的最短路徑改進演演算法”、“利用Excel軟體優化企業資源配置”、“線性規劃方法的應用”等十餘項。