李豐兵

摘 ?要：該文對線性規(guī)劃單純形法進行改進探討，提出一種構(gòu)造初始可行基矩陣的新方法。該方法通過對單純形表進行某種初等行變換，逐步構(gòu)造出初始可行基矩陣，從而避免了增加人工變量及構(gòu)造輔助問題，因此，比人工變量法計算更簡單。實例計算表明，該方法切實可行。

關(guān)鍵詞：線性規(guī)劃 ?單純形法 ?人工變量法 ?初始可行基

中圖分類號：O221.1 ? 文獻標識碼：A ? ? ? ? ? 文章編號：1672-3791（2019）05（a）-0194-02

Abstract： In this paper， the simplex method of linear programming is improved and a new method of constructing initial feasible basis matrix is proposed. According to some rules， this method use elementary row transformation of simplex table step by step to construct the initial feasible basis matrix， and thus avoid the problem of adding artificial variables and constructing auxiliary problem. Therefore， this method is simpler than the artificial variable method. The calculation example shows that this method is feasible.

Key Words： Linear programming; Simplex method; Artificial variable method; Initial feasible basis

單純形法是求解線性規(guī)劃問題的基本方法，是運籌學及最優(yōu)化方法領(lǐng)域的一個重要研究內(nèi)容，目前，國內(nèi)外已存在諸多與單純形法密切相關(guān)的研究工作[1-3]。單純形法包括原始單純形法、兩階段法、大M法及對偶單純形法等。其中，原始單純形法又是最基本、最簡單的一種算法，它以線性規(guī)劃標準型系數(shù)矩陣中的單位陣作為初始可行基，條件過于苛刻。人工變量法（即兩階段法和大M法）通過引入人工變量及構(gòu)造輔助問題，并由此構(gòu)造出單位陣作為初始可行基矩陣，很好地解決了原始單純形法的上述缺陷，但是人工變量法因為引入了人工變量，故增大了決策空間的維數(shù)及求解問題的規(guī)模，使得計算變得更加復雜。此外，大M法中的參數(shù)M的取值沒有確定的方式，在計算機上實現(xiàn)比較困難。

1 ?單純形法的改進

針對單純形法的上述缺陷，該文對其進行改進，提出一種新的初始可行基的構(gòu)造方法，其思想是按照某種規(guī)則對單純形表實施轉(zhuǎn)軸運算（某種初等行變換），“分步”選擇出初始基變量。該法克服了原始單純形法依賴于標準型中單位陣的缺陷，同時又不用引入人工變量和構(gòu)造輔助問題，其詳細步驟如下。

其中y1、y2為人工變量。顯然，引入人工變量后，決策空間的維數(shù)增大了，由原來的5維變成了7維，這將導致計算過程變得更加復雜，實際計算過程比該文提出的改進方法要復雜多了。該文提出的方法不僅僅適用于上述問題（2），經(jīng)驗證對其他原始單純形法無法求解的標準型（1），該文方法照樣可行，由于篇幅限制，不再介紹其他實例的計算過程。

2 ?結(jié)語

該文對單純形法進行了改進探討，在原始單純形法的基礎(chǔ)上提出了一種僅通過對單純形表“逐步”實施轉(zhuǎn)軸運算就能構(gòu)造出初始可行基的方法。該方法改善了原始單純形法依賴單位陣作為初始可行基的不足，同時又沒有引入人工變量和構(gòu)造輔助問題，因此比人工變量法計算更簡單。從諸多實例計算結(jié)果可知，該方法確實可行。盡管如此，該方法仍需進一步研究，特別是理論上仍需完善。

參考文獻

[1] 趙旭芳，梁昔明，龍文.基于最優(yōu)個體指導單純形法改進的人工蜂群算法及應用[J].計算機應用與軟件，2019（2）：44-51，92.

[2] 王夢娜，王秋萍，王曉峰.基于Iterative映射和單純形法的改進灰狼優(yōu)化算法[J].計算機應用，2018，38（S2）：16-20，54.

[3] 吳卓然.基于改進單純形法的冗余證券的判別[J].金融經(jīng)濟，2016（16）：143-145.

[4] 熊偉.運籌學[M].北京：機械工業(yè)出版社，2008.

[5] 胡運權(quán).運籌學基礎(chǔ)及應用[M].北京：高等教育出版社，2008.