【文章內(nèi)容簡(jiǎn)介】 = B1 b B1 N XN，也代入目標(biāo)函數(shù)，問題可以繼續(xù)化為： 　　規(guī)劃問題3： 　　Min z=CB B1 b + ( CN CB B1 N ) XN 　　. 　　XB+B1N XN = B1 b (1) 　　XB = 0, XN = 0 (2) 　　令N:=B1N，b:= B1 b，ζ= CB B1b，σ= CN CB B1 N，則上述問題化為規(guī)劃問題形式4： 　　Min z= ζ + σ XN 　　. 　　XB+ N XN = b (1) 　　XB = 0, XN = 0 (2) 　　在上述變換中，若能找到規(guī)劃問題形式4，使得b=0，稱該形式為初始基解形式。 　　上述的變換相當(dāng)于對(duì)整個(gè)擴(kuò)展矩陣（包含C及A） 乘以增廣矩陣 。所以重在選擇B，從而找出對(duì)應(yīng)的CB。 　　若存在初始基解 　　若σ= 0 　　則z =ζ。同時(shí)，令XN = 0，XB = b，這是一個(gè)可行解，且此時(shí)z=ζ，即達(dá)到最優(yōu)值。所以，此時(shí)可以得到最優(yōu)解。 　　若σ = 0不成立 　　可以采用單純形表變換。 　　σ中存在分量0。這些負(fù)分量對(duì)應(yīng)的決策變量編號(hào)中，最小的為j。N中與j對(duì)應(yīng)的列向量為Pj。 　　若Pj =0不成立 　　則Pj至少存在一個(gè)分量ai，j為正。在規(guī)劃問題4的約束條件（1）的兩邊乘以矩陣T。 　　T= 　　則變換后，決策變量xj成為基變量，替換掉原來的那個(gè)基變量。為使得T b = 0，且T Pj=ei（其中，ei表示第i個(gè)單位向量），需要： 　　l ai，j0。 　　l βq+βi*(aq,j/ai,j)=0，其中q!=i。即βq=βi/ ai,j * aq,j。 　　n 若aq,j=0，上式一定成立。 　　n 若aq,j0，則需要βq / aq,j =βi/ ai,j。因此，要選擇i使得βi/ ai,j最小。 　　如果這種方法確定了多個(gè)下標(biāo)，選擇下標(biāo)最小的一個(gè)。 　　轉(zhuǎn)換后得到規(guī)劃問題4的形式，繼續(xù)對(duì)σ進(jìn)行判斷。由于基解是有限個(gè)，因此，一定可以在有限步跳出該循環(huán)。 求解線性規(guī)劃問題的通用方法。它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。 　　根據(jù)單純形法的原理，在線性規(guī)劃問題中，決策變量（控制變量）x1，x2，…xn的值稱為一個(gè)解,滿足所有的約束條件的解稱為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱為最優(yōu)解。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。 　　最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限增大）。 　　單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問題的最優(yōu)解。⑤若迭代過程中發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無界，則終止迭代。 　　用單純形法求解線性規(guī)劃問題所需的迭代次數(shù)主要取決于約束條件的個(gè)數(shù)?，F(xiàn)在一般的線性規(guī)劃問題都是應(yīng)用單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對(duì)于具有106個(gè)決策變量和104個(gè)約束條件的線性規(guī)劃問題已能在計(jì)算機(jī)上解得。 數(shù)學(xué)模型的建立單純形法是一種迭代算法，其基本原理及主要步驟是：首先設(shè)法找到一個(gè)（初始）基可行解，然后再根據(jù)最優(yōu)性理論判斷這個(gè)基可行解是否最優(yōu)解。若是最優(yōu)解，則輸出結(jié)果，計(jì)算停止；若不是最優(yōu)解，則設(shè)法由當(dāng)前的基可行解產(chǎn)生一個(gè)目標(biāo)值更優(yōu)的新的基可行解，再利用最優(yōu)性理論對(duì)所得的新基可行解進(jìn)行判斷，看其是否最優(yōu)解，這樣就構(gòu)成一個(gè)迭代算法。由于基本可行解只有有限個(gè)，而每次目標(biāo)值都有所改進(jìn)，因而必可在有限步內(nèi)終止。如果原問題確有最優(yōu)解，必可在有限步內(nèi)達(dá)到，且計(jì)算量大大少于窮舉法；若原問題無最優(yōu)解，也可根據(jù)最優(yōu)性理論及時(shí)發(fā)現(xiàn)，停止計(jì)算，避免錯(cuò)誤及無效運(yùn)算。回顧以前的產(chǎn)品生產(chǎn)問題. 約束條件: 原料限制: 工時(shí)限制: 非負(fù)條件: x1, x2 , x3, x40 令 得 p5可用pi (i=1,…,4) 的線性組合表示. xi視為系數(shù), 存在無窮組xi可使上式成立. 現(xiàn)在的目標(biāo)是為找到使目標(biāo)函數(shù)有最優(yōu)值的最優(yōu)組xi. 因p5是二維向量, 可用兩個(gè)線性無關(guān)的向量的線性組合表示, 則系數(shù)xi是唯一確定的, 對(duì)應(yīng)于基本解 (注: 基本解和基本可行解的關(guān)系).例: 得 這里 定義為基變量, 定義為基向量. 單純形法的基本原理: 不斷地更換基變量和基向量(對(duì)應(yīng)于不斷地更換頂點(diǎn)). 這種變換是在對(duì)應(yīng)于可行區(qū)域頂點(diǎn)的各組基本可行解中找出最優(yōu)解. 尋找起始點(diǎn): 做為基向量, 基本矩陣為易得 以及 對(duì)應(yīng)于A點(diǎn), 目標(biāo)值 z/=z=6x14x2=0 (即兩種產(chǎn)品均未安排生產(chǎn)).目標(biāo)是通過選xi (i=1,…,4) 使z增長(或使z減少)最快. x1增加一個(gè)單位, 使z減少6個(gè)單位, x2增加一個(gè)單位, 使z減少4個(gè)單位, 所以選擇x1, 使其從0增大(即使x1進(jìn)基).x1的增大受到限制, 因?yàn)? 當(dāng)x2=0, x1=100/2=50時(shí), 使 x3=0 (原料剩余量, 用完).當(dāng)x2=0, x1=120/4=30時(shí), 使 x4=0 (工時(shí)剩余量, 用完)..所以, x1=30時(shí), 已使x4=0, x1進(jìn)基增長, x4離基減少.由約束條件, 得 ……………………(1)回顧: ………………(2)消去x1, 得 ………………(3)目標(biāo)函數(shù) z/+6x1+4x2=0 (注z/=z) ………………(4) (4)中消去x1, 得 z/+ x2 x4= 180 ……………………(5)即當(dāng)x1=30, x2=0, z/=180 (即 z=180) 注: 現(xiàn)從A點(diǎn)移至D點(diǎn). 問題: 能否進(jìn)一步減少z/?由(5)式得知, 因?yàn)閤2的系數(shù)為正, 則x2由0增大, 會(huì)使z/ 進(jìn)一步減少. 由(3)式和(1)式可得x2增大受到限制, 當(dāng)x2=40/2=20時(shí), 使x3=0, (注x4已經(jīng)為零 ) 當(dāng)x2=30/(1/2)=60時(shí), 使x1=0, 所以x2只能增大到20.由(3)式得, ……………………(6)考慮 (1)式, 消去x2, 得 ……………………(7)由(5)式減去(6)式可得, ……………………(8)由(7)式, 基變量, 非基變量, z/=200.由于(8)式中x的系數(shù)均為負(fù), z/無法再減少, 所以z/=200, 即z=200. 單純形法的主要思路:1) 先找出初始基本可行解, 通常選個(gè)決策變量為零, 而松弛變量等于約束方程右邊值作為初始解. 2) 改進(jìn)目標(biāo)值進(jìn)行換基. 選擇目標(biāo)方程中系數(shù)為正而且絕對(duì)值最大的那一項(xiàng)對(duì)應(yīng)的變量x作為基變量. 再計(jì)算當(dāng)它增加時(shí), 將原來的首先減為零的變量做為離基變量. 然后將方程進(jìn)行交換, 使進(jìn)基變量在這一方程中的系數(shù)為1, 在其余方程(包括目標(biāo)方程)中的系數(shù)為零(以利于迅速求得基變量值). 這是目標(biāo)值將得到改善. 3) 然后進(jìn)一步查看目標(biāo)值能否再減少. 若目標(biāo)方程中變量x的系數(shù)仍有正數(shù), 則選最大的一項(xiàng)進(jìn)行換基, 直到所有系數(shù)為負(fù), 目標(biāo)值無法再進(jìn)一步改進(jìn)為止. 第三章 原材料投入對(duì)生產(chǎn)成本的影響的數(shù)學(xué)模型分析根據(jù)題目中給出的加工每千克飼料所需的營養(yǎng)質(zhì)量（表3—1）和各原料的營養(yǎng)成分含量及價(jià)格（表3—2）表3—1 肉用種雞公司標(biāo)準(zhǔn)每千克飼料所需營養(yǎng)質(zhì)量 表3—2 各原料的營養(yǎng)成分含量及價(jià)格另外公司根據(jù)原料的來源，還要求1噸混合飼料中原料的含量為：玉米不低于400kg，小麥不低于100kg，米糠不超過150kg，豆餅不超過100kg，菜子餅不低于30kg，魚粉不低于50kg，DL蛋氨酸、骨粉、碳酸鈣適量。按照肉用種雞公司標(biāo)準(zhǔn)，以1kg配合飼料來計(jì)算，其約束條件列舉見表3—3表3—3X1X2X3X4X5X6X7X8X9X10X11X12Min=23C1=C278114142117402360450170=135C378114142117402360450170=145C416229572491130108=45C56=C6980=C716340300400=30C8101352740140=5C91000=C10111111111111=1C111000=400C121000