【文章內(nèi)容簡介】 合約束條件，計算出其目標函數(shù)值Z =2。對于極大化問題，當然希望z≥2，于是增加一個約束條件，后加的約束條件稱為過濾條件。過濾條件為： ◎目標函數(shù)可以改寫成：因為1，1，2是遞增的，變量(x3，x2 , x1)也按下述順序取值（0，0，0），（0，0，1），（0，1，0），（0，1，1）等。 ◎點(x3，x2 , x1)約束條件是否滿足條件Z值◎①②③④（0，0，0）0不滿足（0，0，1）2√√√√滿足2（0，1，0）1不滿足（0，1，1）3√√√√滿足3改進過濾條件，用 ◎代替過濾條件，再繼續(xù)進行。點(x3，x2 , x1)約束條件是否滿足條件Z值◎①②③④（1，0，0）1不滿足（1，0，1）1不滿足（1，1，0）0不滿足（1，1，1）2不滿足至此，z值已不能再改進，即得到最優(yōu)解。最優(yōu)解為(x3，x2 , x1)＝（0，1，1）；最優(yōu)值為z=3。1有4個工人，要指派他們分別完成4項工作，每人做各項工作所消耗的時間如表2，問如何分配工作可使總的消耗時間為最少？表2 工作工人ABCD甲15182124乙19232218丙26171618丁19212317解：首先進行行、列變換，使每一行和每一列都出現(xiàn)0元素。在第一列減去15，第二列減去17，第三列減去16，第四列減去17，然后再從第二行中減去1。得首先進行行、列變換，使每一行和每一列都出現(xiàn)0元素。如上表中第一行減去7，第二行減去5，第三行減去4，第四行減去2，然后再從第四列中減去1。得01573550110014570進行試指派，尋找最優(yōu)解。由有0元素最少的行開始，圈出一個0元素，用◎ 表示，然后劃去同行同列的其他0元素，這樣依次進行，得◎157355◎11248?！?457248。由于獨立的0元素個數(shù)少于矩陣的階數(shù)，因此作最少的直線覆蓋所有的0元素。在沒有◎ 的行打√；對打√的行上的所有0元素的列打√號；再對打√的列上有◎ 的行上打 √號。重復以上步驟，直到得不出新的打 √號的行列為止。最后對沒有打√號的行畫橫線，將打有√號的列畫豎線?！?57355◎√11248?！?457248。√√由于覆蓋直線個數(shù)3少于矩陣階數(shù)4，故進行變換，以增加0元素。在沒有被直線覆蓋的部分中找出最小元素3；然后對沒有覆蓋的行中各元素中減去這個最小元素3；被直線覆蓋的列中各元素都加上這個最小元素3。這樣在沒有覆蓋的元素中又增加了0元素。015100220110041240再進行試指派，尋找最優(yōu)解。◎1510248。22248。11248?！?124◎由于獨立的0元素個數(shù)仍然少于矩陣的階數(shù)，因此作最少的直線覆蓋所有的0元素。◎1510√248。22248?！?1248。◎1124◎√√√004100110120051130再進行試指派，尋找最優(yōu)解。248?！?10◎11248。12248?！?113◎0100100000100001得到最優(yōu)解的指派方案為：甲－B，乙－A，丙－C，丁－D；最少消耗時間為70。 第二章 目標規(guī)劃一、思考題1，答：因為在經(jīng)營管理實際中，決策者不僅要考慮資源的最佳配置和有效利用，還要考慮到市場、競爭對手、替代品的政策法律環(huán)境等多方面的影響因素和指標要求，此時線性規(guī)劃模型不能完全解決問題。2，答：一般目標規(guī)劃是將多個目標函數(shù)寫成一個由偏差變量構(gòu)成的函數(shù)求最小值，并按多個目標的重要性，給定優(yōu)先等級和權(quán)重，順序求最小值。按決策者的意愿，對于事先給定的目標值，分為三種情況：（1） 當約束要求目標不超過目標值，目標函數(shù)求正偏差變量最小。（2） 當約束要求目標不低于目標值，目標函數(shù)求負偏差變量最小。（3） 當約束要求目標等于目標值，目標函數(shù)求正負偏差變量之和最小。3，答：（一）初始基變量的選擇 首先選擇所有的負偏差變量為初始基變量；如果負偏差變量數(shù)小于約束方程數(shù)，則增加選擇不同約束條件的松弛變量；如果負偏差變量和松弛變量的總數(shù)還小于約束方程數(shù)時，則需要加入人工變量，此時引入的M將被視作最高優(yōu)先級，即0級優(yōu)先級：。 （二）滿意解的判斷 當所有非基變量的檢驗數(shù)大于等于零時，目標規(guī)劃問題獲得最優(yōu)解。非基變量的檢驗數(shù)為：，由于，所以當非基變量檢驗數(shù)中的首項系數(shù)時，獲得滿意解。 （三）入基變量和出基變量的選擇 入基變量的選擇：選擇檢驗數(shù)首項系數(shù)為負的非基變量入基，若有多個首項系數(shù)為負，則取其中檢驗數(shù)首項優(yōu)先級最高系數(shù)最小的非基變量入基。如果首項優(yōu)先級相同且系數(shù)相等，再比較第二個優(yōu)先級的系數(shù)若有兩個及兩個以上的非基變量檢驗數(shù)（的所有各項系數(shù)）都相等，這些非基變量中有決策變量時，則首先選擇決策變量入基；若它們同時是決策變量或偏差變量，則可以選擇其中下標最小的變量入基。 出基變量的選擇：與單純形法相同。4，答：序列解法不需要使用優(yōu)先級系數(shù)，而是將單純形法應(yīng)用于不同目標層次的線性規(guī)劃問題。 單純形法適用于能給目標確定優(yōu)先級的場合，序列解法適用于目標層次不需確定優(yōu)先級的場合。5，答：第一個問題：看最優(yōu)解是否唯一或是否為最后一個層次。如果是，則不再繼續(xù)求解，已獲得滿意解；如果不是，則需要繼續(xù)下一層次目標的求解。 第二個問題：如果z*＝0，則在加入第二層次目標約束后從約束條件中刪去第一層次目標函數(shù)含有的偏差變量；如果z*0，則加入第二層次目標約束后，將第一層次的目標函數(shù)（令其等于z*）作為附加約束加入到第二層次約束條件中。 6， 判斷以下各種說法的正確性1） 正偏差變量大于等于零，負偏差變量小于等于零。答：錯，都大于等于零。2） 目標約束一定是等式約束。 答：對。3） 一對正負偏差變量至少一個大于零。 答：錯。4） 一對正負偏差變量至少一個等于零。 答：對。5） 要求至少達到目標值的目標函數(shù)是。 答：對。6） 要求不超過目標值的目標函數(shù)是。 答：錯。要求正偏差變量最小。二、選擇題7，答：正確的是C、E。 8. 答：應(yīng)該選擇D。9．答：應(yīng)該選擇A。三、計算題10， x1x2120圖1 圖解法第1題（1） 解：對于，桔黃色內(nèi)的部分滿足要求，對于，藍色內(nèi)的部分滿足要求，所以滿意解是＝2，＝0，＝1，其它偏差變量都等于零。x22Cx101圖2 圖解法第2題（2） 解：對于，桔黃色內(nèi)的部分滿足要求，對于，藍色內(nèi)的部分滿足要求，由圖2知無法滿足，所以滿意解在點c取到，滿意解是＝0，＝3，＝5，＝4，＝1，其它偏差變量都等于零。11，（1）解：初始基變量為三個負偏差變量，得到初始單純形表如表1。表1 題2(1)的初始單純形表000020016030408114221001000100100010012030408401000012000201非基變量的檢驗數(shù)分別為和，因此應(yīng)當入基，用最小比值法確定應(yīng)當出基。換基后，通過計算求得新的基本可行解，見表2。表2 題2(1)的第一次迭代單純形表000020002010201001/23/23/21/81/81/81/81/81/80100100010014020/340/30010000003/21/81/80201可得，入基，出基。換基后，通過計算求得新的基本可行解，見表3。表3 題2(1)的第二次迭代單純形表0000200050/320/3101000101/61/1201/61/1201/32/311/32/310010010010000000001101此時所有變量的檢驗數(shù)的首項系數(shù)都已經(jīng)大于等于零，因此獲得了滿意解如下：＝50/3，＝20/3，=10，其它偏差變量都等于零。（3） 解：初始基變量為四個負偏差變量，得到初始單純形表如表4。表4 題2(2)的初始單純形表0000000406050201110110110001000010001000010001000010001406050110101000010000001000100000001由上表得，入基，出基。換基后，通過計算求得新的基本可行解，見表5。表5 題2(2)的第一次迭代單純形表000000004020102010001011111011100100010000100010000100012010001001000001110001000100000001由上表得，入基，出基。換基后，通過計算求得新的基本可行解，見表6。表6 題2(2)的第二次迭代單純形表0000000005010102010000111001000100100010011101110000100011020001001000000000010000100000001由上表得，入基，出基。換基后，通過計算求得新的基本可行解，見表7。表7 題2(2)的第三次迭代單純形表000000000501020101000010000100010011101111101110100010001001001000000000010000000111101此時所有變量的檢驗數(shù)的首項系數(shù)都已經(jīng)大于等于零，因此獲得