單純形法兩種形式的區(qū)別與聯(lián)系

張益 唐金芳

【摘要】線性規(guī)劃問(wèn)題的單純形法一直是運(yùn)籌學(xué)課程教學(xué)的重點(diǎn)和難點(diǎn)，經(jīng)過(guò)對(duì)教材上兩種常見(jiàn)單純形法的形式進(jìn)行比較分析，指出單純形法不同形式之間的區(qū)別與聯(lián)系，得出結(jié)果直觀，并且便于做靈敏度分析的形式，通過(guò)算例證明這種形式更加簡(jiǎn)單直觀，使學(xué)生更容易理解單純形法的算法.

【關(guān)鍵詞】單純形法；有限改進(jìn)法；靈敏度分析；單純形表

【中圖分類號(hào)】O221【文獻(xiàn)標(biāo)識(shí)碼】A

線性規(guī)劃是現(xiàn)代管理中應(yīng)用最為廣泛的一種數(shù)學(xué)模型，它是解決經(jīng)營(yíng)管理中如何有效利用現(xiàn)有人力、物力、財(cái)力完成更多的任務(wù)，或在預(yù)定的任務(wù)目標(biāo)下，如何使耗用的人力、物力、財(cái)力最少，以實(shí)現(xiàn)目標(biāo)的問(wèn)題.1947年美國(guó)數(shù)學(xué)家G.B.Dantzig提出的單純形法（simplex method）是解線性規(guī)劃問(wèn)題最為有效的方法.作為運(yùn)籌學(xué)的一個(gè)重要分支，線性規(guī)劃的應(yīng)用極其廣泛，很多學(xué)者對(duì)單純形法做了改進(jìn)和補(bǔ)充.線性規(guī)劃問(wèn)題的單純形法一直是運(yùn)籌學(xué)課程教學(xué)的重點(diǎn)和難點(diǎn)，一些學(xué)者也做了單純形法教學(xué)方面的研究，為單純形法的教學(xué)提供了新的思路.單純形法是一種迭代算法，它求解線性規(guī)劃問(wèn)題的基本思想是：首先找出一個(gè)初始基可行解，判斷其是否為最優(yōu)解；如果為否，則轉(zhuǎn)換到使得目標(biāo)值不斷增大，并且與其相鄰的基可行解，直到找到最優(yōu)解為止.

目前不同的教材在介紹單純形法時(shí)采用的列表形式不一樣，鑒于這種情況，本文就教材上兩種常見(jiàn)的形式進(jìn)行比較分析得出結(jié)果明顯，并且便于做靈敏度分析的形式，通過(guò)算例說(shuō)明這種形式既便于計(jì)算又便于教學(xué).