探討單純形法的改進

李豐兵

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

關鍵詞：線性規劃 ?單純形法 ?人工變量法 ?初始可行基

中圖分類號：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

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

1 ?單純形法的改進

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

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

2 ?結語

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

參考文獻

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

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

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

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

[5] 胡運權.運籌學基礎及應用[M].北京：高等教育出版社，2008.