運籌學習題解答(編輯修改稿)

　

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