線性規劃

線性規劃（Linear programming,簡稱LP）是運籌學中研究較早、發展較快、套用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法。研究線性約束條件下線性目標函式的極值問題的數學理論和方法。英文縮寫LP。它是運籌學的一個重要分支，廣泛套用于軍事作戰、經濟分析、經營管理和工程技術等方面。為合理地利用有限的人力、物力、財力等資源作出的最優決策，提供科學的依據。

基本介紹

• 中文名：線性規劃
• 外文名：linear programming
• 所屬學科：運籌學
• 研究內容：線性最最佳化問題
• 套用學科：高中數學必修5

線性規劃簡介

數學模型

（1）列出約束條件及目標函式

線性規劃步驟

（2）畫出約束條件所表示的可行域

（3）在可行域內求目標函式的最優解及最優值

標準型

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

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

　
以下形式的問題約束：

和非負變數：


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

模型建立

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

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 對數障礙函式法

本章小結

複習題

習題答案

索 引

編者語