亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        LP之單純形法教輔軟件設(shè)計(jì)與實(shí)現(xiàn)

        2020-08-26 07:46:55曹迎槐張靜趙強(qiáng)
        電腦知識(shí)與技術(shù) 2020年20期
        關(guān)鍵詞:單純形法仿真模型

        曹迎槐 張靜 趙強(qiáng)

        摘要:在線性規(guī)劃理論中,單純形法是非常經(jīng)典的求解算法,但它計(jì)算復(fù)雜,涉及數(shù)據(jù)較多,掌握相對(duì)困難,為提高教學(xué)效果,筆者開發(fā)了《軍事運(yùn)籌原理仿真模擬系統(tǒng)》,其中涉及了線性規(guī)劃模型的單純形求解算法仿真問題,經(jīng)教學(xué)實(shí)用,效果良好。

        關(guān)鍵詞:LP;模型;單純形法;仿真

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

        文章編號(hào):1009-3044(2020)20-0070-02

        Design and Implementation of LP Simplex Method Teaching Auxiliary Software

        CAO Ying-huai. ZHANG Jing, ZHAO Qiang

        (China Coast Cuard Academy, Ningb0 315801. China)

        Abstract: In the theory of' linear programming, Simplex method is a very c:lassical solution algorithm, But it's complicated, More da-to involved, lt's relatively difficult to master. In order to improve the teaching effect, 'rhe author develc}ped the simulation system ofmilitary operation principle, It involves the simulation of' simplex algorithm of' linear programming model, After teaching practical,the effect is good.

        Key words: linear programming; simplex method; foundation: simulation

        目前,在運(yùn)籌學(xué)之線性規(guī)劃(linear programming,簡(jiǎn)稱LP)分支中,最經(jīng)典的求解算法就是單純形法,它既是運(yùn)籌學(xué)教材之重點(diǎn),也是教學(xué)之難點(diǎn)所在。但該算法相對(duì)復(fù)雜,計(jì)算過程煩瑣,學(xué)生掌握相對(duì)困難,為此,筆者開發(fā)了該算法的求解仿真軟件,教學(xué)效果良好。

        1單純形法的求解步驟

        單純形法和基于窮舉思想的基可行解法不同,它不需要求出所有的基可行解,而是以LP模型之標(biāo)準(zhǔn)形式為出發(fā)點(diǎn)先求出一個(gè)基可行解,并檢驗(yàn)其是否為最優(yōu)解。如果它已最優(yōu),則求解結(jié)束,算法終止;如果它不是最優(yōu)解,就按照算法給定的方法求出另一個(gè)基可行解,該算法可以保證新求出的基可行解肯定要優(yōu)于上一個(gè)基可行解。只要LP問題存在最優(yōu)解,就一定可通過有限次的運(yùn)算求出最優(yōu)解。如果,所求的問題不存在有限的最優(yōu)解(即無解),則該算法也有相應(yīng)法則判斷之。

        其具體的求解算法可歸納為五步。

        1.1確定初始基可行解

        確定出初始(即第一個(gè))可行基時(shí),因標(biāo)準(zhǔn)化處理中多加入松弛變量,所以,初始基可行解的確定往往并不困難,一般直接選取各松弛變量即可。當(dāng)然,若個(gè)別約束方程未添加松弛變量,亦可借助線性代數(shù)知識(shí),通過行或列的交換等操作來得到。

        1.2最優(yōu)解檢驗(yàn)

        檢驗(yàn)初始基可行解是否最優(yōu)。若是最優(yōu)解,則停止運(yùn)算;若不是最優(yōu)解,就轉(zhuǎn)下一步。

        1.3無解檢驗(yàn)

        當(dāng)檢驗(yàn)初始基可行解不是最優(yōu)解時(shí),繼續(xù)檢驗(yàn)該規(guī)劃問題是否無解(即無有限的最優(yōu)解)。若無解則停止運(yùn)算,若依然無法判定是否無解則轉(zhuǎn)下一步。

        1.4基變換

        當(dāng)經(jīng)過上面的兩種檢驗(yàn)發(fā)現(xiàn),該基可行解既不最優(yōu),也不能判定其無解,則需要尋找另一個(gè)基可行解。即在該可行基之基礎(chǔ)上,先從原非基變量中選一個(gè)變量,稱換人變量;再于原基變量中選擇一個(gè)變量使其成為非基變量,稱之為換出變量。于是,新的基變量對(duì)應(yīng)的系數(shù)列向量,同原來保持不變的基變量對(duì)應(yīng)的系數(shù)列向量(m-1)個(gè),就組成一個(gè)新的可行基,此即基變換。

        1.5旋轉(zhuǎn)運(yùn)算

        基變換完成后,需進(jìn)一步求出其相應(yīng)的新基可行解,該過程即旋轉(zhuǎn)運(yùn)算。然后,轉(zhuǎn)步驟12。

        單純行法的求解算法亦可用傳統(tǒng)流程圖來描述,在仿真實(shí)現(xiàn)中如圖1所示。

        2單純形表

        利用單純形法求解LP問題,涉及大量的數(shù)值計(jì)算,且各數(shù)值之間關(guān)系復(fù)雜,種類繁多,為簡(jiǎn)明其見,通常是列表(稱為單純形表,見圖2)進(jìn)行。一般地,單純形表中應(yīng)考慮以下數(shù)據(jù):

        1)基變量:這里用xBi,表示,有xBi=xi(i=l,2,…,m),如圖2上部左側(cè)第1列;

        2)基變量的價(jià)值系數(shù):用cBi表示,有cBi=ci(i=1,2,…,m),如圖2上部左側(cè)第2列;

        3)約束方程右端的常數(shù)bi(i=l,2,…,m),如圖2上部有側(cè)第2列;

        4)目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)cj(j=1,2,…,n),填入Cj列,如圖2上部第1行;

        5)規(guī)劃模型之各基向量,Pj(j=1,2,…,n),填人xj行下面的對(duì)應(yīng)區(qū)域,如圖2上部中間區(qū)域;

        6)檢驗(yàn)數(shù)σj(j=1,2,…,n)填在單純形表的最下面一行,如圖2中部σj所示。公式為:

        7)確定換人變量時(shí),利用“θ最小比法則”計(jì)算出來的θi(i-1,2,…,m),填入單純形表最右側(cè)一列。當(dāng)然,換入變量確定之后,計(jì)算θi=bi/aik時(shí),當(dāng)aik>0時(shí)才須計(jì)算之,當(dāng)aik≤0時(shí)不用計(jì)算。所以,運(yùn)算過程中,θi一列并非總要填滿,要視情況而定。

        3單純形法求解仿真

        單純形法仿真求解是筆者設(shè)計(jì)開發(fā)之《軍事運(yùn)籌學(xué)原理仿真模擬系統(tǒng)》中的一個(gè)子模塊,假設(shè)給定的LP問題之標(biāo)準(zhǔn)型如圖2下半部區(qū)域所示。其中涉及目標(biāo)函數(shù)系數(shù)、約束方程系數(shù)矩陣、資源列向量、未知變量個(gè)數(shù)、約束方程個(gè)數(shù)等。

        界面最底部的文字用來描述仿真求解過程中相關(guān)操作信息。而“導(dǎo)入”按鈕則可將已標(biāo)準(zhǔn)化的LP模型納入單純形法求解仿真模塊,導(dǎo)人操作剛完成時(shí),并沒有圖2界面中上半部分單純形表中的相關(guān)數(shù)據(jù),這些數(shù)據(jù)是在求解過程中隨著各步操作的進(jìn)行而出現(xiàn)并動(dòng)態(tài)變化的?!扒宄卑粹o則可將該仿真模塊中的LP數(shù)據(jù)清空,屆時(shí)整個(gè)仿真界面呈現(xiàn)空白狀態(tài)。

        本仿真模塊的求解分兩種模式,一是“分步求解”,一是“連續(xù)求解”。當(dāng)LP模型數(shù)據(jù)導(dǎo)入完成后,即可通過單擊“分步求解”按鈕,啟動(dòng)單純形求解之第一步“確定初始可行基”,該步完成則同時(shí)填充該界面上半部分的“單純形表”之相關(guān)區(qū)域,并將“分步求解按鈕上的文字變?yōu)椤跋乱徊健保鐖D2所示。此后,可依次單擊“下一步”按鈕,則求解過程中各相關(guān)數(shù)據(jù)的變化即體現(xiàn)在該界面上半部分的單純形表相關(guān)區(qū)域中。

        持續(xù)單擊“下一步”按鈕,如果該LP模型存在最優(yōu)解,則求解完成時(shí),最優(yōu)解出現(xiàn)在相應(yīng)位置,同時(shí)“下一步”命令按鈕變?yōu)椤胺植角蠼狻?,如圖3所示。

        任何時(shí)候,均可通過“打印”按鈕將當(dāng)前界面的狀態(tài)打印出來,不過,在一般教學(xué)實(shí)施過程中,該功能使用并不多。通過“設(shè)置”按鈕可改變未知變量的個(gè)數(shù)和約束方程的個(gè)數(shù)等LP規(guī)模數(shù)據(jù),當(dāng)LP規(guī)模較高時(shí),可協(xié)同“高維模型”按鈕共同使用,但此刻仿真模塊已基本失去教學(xué)輔助之意義,逐漸靠向求解工具的范疇,因此,課堂上不常使用。

        “連續(xù)求解”按鈕可從導(dǎo)入標(biāo)準(zhǔn)化模型開始,直達(dá)最后得到求解結(jié)果,中間的各步信息也不再顯示在界面的底部,界面上半部直接顯示最優(yōu)解,這里不再贅述。

        “基解列表”按鈕可顯示該LP模型在本模塊之仿真求解過程中得到的所有可行基,如圖4所示。但一般肯定不是該LP模型的所有可能的基(含不可行的),這一點(diǎn)必須清楚。

        當(dāng)然,在該仿真模塊中,標(biāo)準(zhǔn)化之后LP模型未必能直接得出初始可行基,此時(shí)可借助大M法或兩階段法求解之。另外,如果LP模型無解,仿真模塊同樣會(huì)給出相關(guān)反饋信息。鑒于篇幅這里不再詳述。因水平所限,不妥和錯(cuò)誤之處,敬請(qǐng)大家批評(píng)指正!

        參考文獻(xiàn):

        [1]錢頌迪.運(yùn)籌學(xué)[M].北京:清華大學(xué)出版,1993.

        [2]曹迎槐,尹健,梁春美.軍事運(yùn)籌學(xué)[M].北京:國(guó)防工業(yè)出版社.2013.

        [3]曹迎槐.LP模型標(biāo)準(zhǔn)化教輔軟件設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù),2018(7):87-88.

        [4]曹迎槐.LP之單純形法教輔軟件設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù),2020(17):63-64.

        【通聯(lián)編輯:謝媛媛】

        收稿日期:2020-05-08

        作者簡(jiǎn)介:曹迎槐(1966-),男,河北蔚縣人,教授,技術(shù)5級(jí),碩士,長(zhǎng)期從事計(jì)算機(jī)技術(shù)、運(yùn)籌建模、海警信息與情報(bào)等領(lǐng)域的教學(xué)與科研工作;張靜(1980-),女,遼寧大連人,副教授,碩士,從事信息安全專業(yè)教學(xué)工作;趙強(qiáng)(1976-),男,青海西寧人,講師,碩士,從事多媒體和信息技術(shù)專業(yè)教學(xué)和科研工作。

        猜你喜歡
        單純形法仿真模型
        一半模型
        重要模型『一線三等角』
        基于單純形法的TLE軌道確定
        重尾非線性自回歸模型自加權(quán)M-估計(jì)的漸近分布
        基于單純形法的簡(jiǎn)單問題的研究與應(yīng)用
        青年生活(2019年35期)2019-09-10 00:13:32
        線性規(guī)劃最優(yōu)解研究
        Buck開關(guān)變換器的基本參數(shù)設(shè)計(jì)及仿真分析
        試析PLC控制下的自動(dòng)化立體倉庫仿真情況分析
        3D打印中的模型分割與打包
        基于MADYMO的航空座椅約束系統(tǒng)優(yōu)化設(shè)計(jì)
        科技視界(2016年18期)2016-11-03 21:44:44
        亚洲精品久久久久久| 91盗摄偷拍一区二区三区| 亚洲另类丰满熟妇乱xxxx| 午夜精品一区二区三区视频免费看 | 中文字幕久久精品一二三区| 天堂√最新版中文在线天堂| 中文字幕午夜AV福利片| 亚洲女同性恋激情网站| 精品粉嫩av一区二区三区| 久久精品中文闷骚内射| 最近最好的中文字幕2019免费 | 久久精品中文字幕大胸| 69sex久久精品国产麻豆| 国产亚洲精品久久久久秋霞| 99久久精品久久久| 97久久综合精品国产丝袜长腿 | 国产人妻精品一区二区三区| 国产极品美女高潮抽搐免费网站 | 中文字幕亚洲熟女av| 中文字幕av一区二区三区人妻少妇| 欧美 日韩 国产 成人 在线观看| 久久国产精品免费一区六九堂| 女同在线视频一区二区| 日本a级片免费网站观看| 亚洲综合色区另类av| 巨爆乳中文字幕爆乳区| 久久亚洲精品国产精品婷婷| 黄色影院不卡一区二区| 久久精品国产只有精品96| 黑人玩弄人妻中文在线| 久久久久久AV无码成人| 久久精品国产亚洲av四区| 99riav国产精品视频| 成全高清在线播放电视剧| 亚洲精品国产综合久久一线| 久久黄色精品内射胖女人| 国产成人a级毛片| 国产真实夫妇交换视频| 99精品国产第一福利网站| 中文字幕人妻一区二区二区| 久久天天躁狠狠躁夜夜av浪潮|