線性規劃在日常管理中的應用

摘要：背包問題是算法設計分析中的經典問題， 本文給出了一種求解整數背包問題的爬山解法，提出了一個解決此類問題的數學模型。并以具體實例詳細描述算法基本思想，通過仿真模擬得出最優解。數值實驗表明，該算法簡便易行，在其適用范圍內具有計算復雜度低等優點。

關鍵字：線性規劃；背包問題；整數規劃

1、引言

線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法。在經濟管理、交通運輸、工農業生產等經濟活動中，提高經濟效果是人們不可缺少的要求，而提高經濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產工藝，使用新設備和新型原材料；二是生產組織與計劃的改進，即合理安排人力物力資源。線性規劃所研究的是在一定條件下，合理安排人力物力等資源，使經濟效果達到最優。一般地，求線性目標函數在線性約束條件下的最大值或最小值的問題，統稱為線性規劃問題。文章根據線性規劃問題在現實生活中的意義進行相關討論與探究，介紹了線性規劃問題產生的背景、特點和實際運用情況，以及線性規劃問題在經濟生活中運用的意義。

2、線性規劃簡介

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

1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法。用這種方法求解線性規劃問題在變量個數為5000時只要單純形法所用時間的1/50?，F已形成線性規劃多項式算法理論。

線性規劃問題的求解可以通過運行Lingo軟件來完成。Lingo軟件的特色在于其內置建模語言，提供十幾個內部函數，而且執行速度非?？?。

一般地，使用LINGO求解運籌學問題可以分為以下兩個步驟來完成：

（1）根據實際問題，建立數學模型，即使用數學建模的方法建立優化模型；

（2）根據優化模型，利用LINGO來求解模型。主要是根據LINGO軟件，把數學模型轉譯成計算機語言，借助于計算機來求解。

3、線性規劃問題在實際中的應用

（1）背包問題的求解

1.1背包問題的定義

已知有n種物品和一個可容納M重量的背包，每種物品i的重量為wi，假定將物品i的一部分xi放入背包就會得到pixi的效益，這里，0<=xi<=1，pi>0。采用不同的裝包方法將會得到不同的裝入背包物品的總效益。由于背包容量是M，因此要求所有選中要裝入背包的物品總重量不得超過M，如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益，如果這些物品的總重量大于M，則需要選取最優解。

1.2背包問題的數學模型

背包問題的數學模型如下：

其中，①式是目標函數，②和③是約束條件。滿足約束條件的任一集合（x1，x2...xn）是一個可行解，使目標函數取得最大值的可行解即是最優解。當約束條件xi為正整數時稱為整數背包問題，當約定x只取0或1時稱為0-1背包問題。

（2）背包問題的仿真模擬

2.1問題的提出

一個人要想旅行必須作好出發前的準備，才不會有危險。

登山隊員，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相器材，通信器材等，每種物品的重量及重要性系數見表1登山隊員可攜帶的最大量為25kg，試選擇該隊員所應攜帶的物品.

2.2模型的建立

若xi=1表示應攜帶物品i；若xi=0表示該隊員不應攜帶物品I

因此模型可表達為：

目標函數：Max：Z=20x1+15x2+18x3+14x4+8x5+4x6+10x7

約束條件：s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25

xi=1或 0，i=1，2，3，4，5，6，7

2.3對模型的計算、分析

對問題進行分析后得到上述模型，現擬利用lingo軟件對模型進行求解。將模型輸入到lingo軟件中，運行軟件即得解。

4、結語

整數背包問題的應用十分廣泛，對該問題的求解方法的研究無論是在理論上還是實踐中都具有一定的意義，在現實生活中類似的問題還有很多，比如管理中的資源分配，集裝箱的貨物裝運，物流公司的貨物發配，以及工廠里的材料下料問題等，不勝枚舉。本文討論的求解學習效益問題構成了整數背包問題的一個應用類，其數學模型及算法可以推廣，此程序實用性很強，可以用lingo輕而易舉地解決該類型的其它一些問題。同時我們對這一算法的性能和計算復雜度與幾種求解背包問題的經典方法進行了對比實驗，結果表明，本文提出的爬山算法是求解背包問題的有效方法。

參考文獻：

[1]唐加冕，周京徽.線性規劃問題在經濟生活中的應用[J].商業經濟，2011（19）：10-11.

[2]王孝通，徐冠雷，周紅進.線性規劃模型建模和分析管理[J].系統工程理論與實踐，2015，09：2387-2393.

作者簡介：劉曉彤（1990—），男，山西呂梁人，山西財經大學2015（管理科學與工程）學術碩士研究生，研究方向：創業過程與企業孵化.