線性規(guī)劃在日常管理中的應(yīng)用

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

關(guān)鍵字：線性規(guī)劃；背包問題；整數(shù)規(guī)劃

1、引言

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

2、線性規(guī)劃簡介

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

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

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

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

（1）根據(jù)實際問題，建立數(shù)學(xué)模型，即使用數(shù)學(xué)建模的方法建立優(yōu)化模型；

（2）根據(jù)優(yōu)化模型，利用LINGO來求解模型。主要是根據(jù)LINGO軟件，把數(shù)學(xué)模型轉(zhuǎn)譯成計算機語言，借助于計算機來求解。

3、線性規(guī)劃問題在實際中的應(yīng)用

（1）背包問題的求解

1.1背包問題的定義

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

1.2背包問題的數(shù)學(xué)模型

背包問題的數(shù)學(xué)模型如下：

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

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

2.1問題的提出

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

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

2.2模型的建立

若xi=1表示應(yīng)攜帶物品i；若xi=0表示該隊員不應(yīng)攜帶物品I

因此模型可表達為：

目標函數(shù)：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對模型的計算、分析

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

4、結(jié)語

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

參考文獻：

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

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

作者簡介：劉曉彤（1990—），男，山西呂梁人，山西財經(jīng)大學(xué)2015（管理科學(xué)與工程）學(xué)術(shù)碩士研究生，研究方向：創(chuàng)業(yè)過程與企業(yè)孵化.