串講練習(xí)題1. 某公司生產(chǎn)的產(chǎn)品A，B，C和D都要經(jīng)過下列工序：刨、立銑、鉆孔和裝配。已知每單位產(chǎn)品所需工時及本月四道工序可用生產(chǎn)時間如下表所示：刨立銑鉆孔裝配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生產(chǎn)時間（小時）1800280030006000又知四種產(chǎn)品對利潤貢獻(xiàn)及本月最少銷售需要單位如下：產(chǎn)品最少銷售需要單位元/單位A1002B6003C5001D4004問該公司該如何安排生產(chǎn)使利潤收入為最大？（建立模型）2已知線性規(guī)劃問題 min z=2x1-x2+2x3 -x1+x2+x3=4 -x1+x2-x36 x10,x20,x3無約束（1） 寫出其對偶問題并化為標(biāo)準(zhǔn)型式。（2） 用單純形法求出原問題的最優(yōu)解。3應(yīng)用對偶問題性質(zhì)，求出下面問題的最優(yōu)解。4.某混合飼料場為某種動物配置飼料。已知此動物的生長速度與飼料中的三種營養(yǎng)成分甲、乙、丙有關(guān)，且每頭動物每天需要營養(yǎng)甲85g、乙5g、丙15g。現(xiàn)有五種飼料中都含有這三種營養(yǎng)成分，每種飼料每公斤所含營養(yǎng)成分及每種飼料成本如下表所示。求既滿足動物生長需要又使成本最低的飼料配方。飼料營養(yǎng)甲/g營養(yǎng)乙/g營養(yǎng)丙/g成本/元10.500.100.08222.000.060.70633.000.040.35541.500.150.25450.800.200.0235.京成畜產(chǎn)品公司計劃在市區(qū)的東西南北四區(qū)建立銷售門市部，擬議中有10個位置可供選擇，考慮到各地區(qū)居民的生活水平及居民居住密集度，規(guī)定：在東區(qū)由三個點至多選擇兩個；在西區(qū)由兩個點中至少選一個；在南區(qū)由兩個點中至少選一個；在北區(qū)由三個點中至少選兩個。各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測情況如下表。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點可使年利潤為最大。投資額10012015080709080140160180利潤364050222030254858616已知下表為求解某線性規(guī)劃問題的最終單純形表，表中為松弛變量，問題的約束條件為形式。5/201/211/205/21-1/20-1/61/30-40-4-2（1） 寫出原線性規(guī)劃問題的數(shù)學(xué)模型；（2） 寫出原問題的對偶問題；（3） 直接由上表寫出對偶問題的最優(yōu)解。7已知線性規(guī)劃問題 max z=2x1+x2 5x215 6x1+2x224x1+x2 5 x1,x20（1）寫出其對偶問題并化為標(biāo)準(zhǔn)型式； （2）用單純形法求出原問題的最優(yōu)解；唯一最優(yōu)解（3）根據(jù)最終單純形表寫出其對偶問題的最優(yōu)解，三種資源的影子價格各為多少并說明其涵義；（4）若第三種資源增加3單位，問最優(yōu)解有何變化，資源的影子價格變?yōu)槎嗌佟?運輸問題課后習(xí)題3.3（1）（2）9指派問題 課后習(xí)題5.710最小樹問題 課后習(xí)題10.4，10.511最短路問題 課后習(xí)題10.6 10.712.最大流問題：10.12,10.13部分答案：2解：（1）其對偶問題為： 化成標(biāo)準(zhǔn)型式為：（2）原問題的準(zhǔn)標(biāo)準(zhǔn)型為： 用大M法求解 Cj-2 -1 2 -2 M 0 cBxBb x2 x4 x5 x6 x7 M0X6x7461 1 1 -1 1 0 1 1 -1 1 0 1 46檢驗數(shù)-2-M 1-M 2-M M-2 0 0-20X7421 1 1 -1 1 0 0 0 -2 2 -1 1-1檢驗數(shù)0 1 0 -4 M+2 0-2-2X5511 1 0 0 1/2 1/2 0 0 -1 1 -1/2 1/2 檢驗數(shù)0 1 0 0 M 2所以，原問題的最優(yōu)解為：4解：設(shè)為每千克混合飼料中所含5種飼料的重量 目標(biāo)函數(shù)為： 約束條件有：6解：（1）首先設(shè)a、b、c表示對應(yīng)原模型的價值系數(shù)，則由檢驗數(shù)的計算公式，得解此方程組，得：a=6，b=-2，c=10再由單純形表與原模型標(biāo)準(zhǔn)型的特點，得有這兩個關(guān)系式，可得：所以：愿問題的模型為：（2）由原問題的模型，得到其對偶問題模型： （3）由對偶理論，從原問題的最終單純形表中，直接得到對偶問題的最優(yōu)解：7（2）唯一最優(yōu)解 （3）其對偶問題的最優(yōu)解為： 第一種資源影子價格為0，第二種資源為1/4，第三種資源為1/2 其含義為：每增加一個單位的第一種資源，最優(yōu)值不會增加，每增加一個單位的第二種資源，最優(yōu)值增加1/4，每增加一個單位的第三種資源，最優(yōu)值會增加1/2。所以要想增加最優(yōu)值，可以增加第二和第三種資源。 （4）第三種資源增加三個單位，= 新最優(yōu)解為：13有七個城市V1,V2,，V7其公路網(wǎng)如下圖所示，弧旁數(shù)字為該段公路的長度，有一批貨物要從V1運到V7，試用迪克斯特拉算法或雙標(biāo)號法求出走那條路距離最短。 用狄克斯特拉算法或雙標(biāo)號法標(biāo)號 （7分）得到最短路路徑：V1V3V4V5V7（2分）最短路路權(quán)：10（1分）14.幾個工地之間建立一個局域網(wǎng)，由于條件不同，各工地間相連的費用不同，如下圖所示，求A,B,C,D,E間的最小連線方案。（10分）工地A工地B工地C工地D工地EA071153B7010144C11100137D5141306E34760由對稱表格畫出連通圖（4分）由破圈法或避圈法得到最小樹（4分），最小權(quán)和22（2分）