探討單純形法的改進(jìn)

李豐兵

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

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

中圖分類號(hào)：O221.1 ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? 文章編號(hào)：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ī)劃問(wèn)題的基本方法，是運(yùn)籌學(xué)及最優(yōu)化方法領(lǐng)域的一個(gè)重要研究?jī)?nèi)容，目前，國(guó)內(nèi)外已存在諸多與單純形法密切相關(guān)的研究工作[1-3]。單純形法包括原始單純形法、兩階段法、大M法及對(duì)偶單純形法等。其中，原始單純形法又是最基本、最簡(jiǎn)單的一種算法，它以線性規(guī)劃標(biāo)準(zhǔn)型系數(shù)矩陣中的單位陣作為初始可行基，條件過(guò)于苛刻。人工變量法（即兩階段法和大M法）通過(guò)引入人工變量及構(gòu)造輔助問(wèn)題，并由此構(gòu)造出單位陣作為初始可行基矩陣，很好地解決了原始單純形法的上述缺陷，但是人工變量法因?yàn)橐肓巳斯ぷ兞?，故增大了決策空間的維數(shù)及求解問(wèn)題的規(guī)模，使得計(jì)算變得更加復(fù)雜。此外，大M法中的參數(shù)M的取值沒(méi)有確定的方式，在計(jì)算機(jī)上實(shí)現(xiàn)比較困難。

1 ?單純形法的改進(jìn)

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

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

2 ?結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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