2025年大學《數理基礎科學》專業(yè)題庫——線性規(guī)劃與整數規(guī)劃的解法比較考試時間：______分鐘總分：______分姓名：______一、1.寫出線性規(guī)劃問題的標準形式，并說明其中各符號的含義。2.簡述單純形法的基本思想和主要步驟。3.解釋對偶單純形法的適用條件和與標準單純形法的主要區(qū)別。二、4.已知線性規(guī)劃問題：$\maxZ=3x_1+5x_2$s.t.$\begin{cases}x_1+x_2\leq4\\2x_1+x_2\leq5\\x_1,x_2\geq0\end{cases}$求解該問題的初始單純形表，并指出基變量和非基變量。三、5.什么是線性規(guī)劃的對偶問題？請寫出上述第4題所示問題的對偶問題。6.簡述對偶理論中的強對偶定理，并說明其在線性規(guī)劃求解中的應用價值。7.解釋線性規(guī)劃靈敏度分析的基本思想，它可以分析哪些方面的參數變化？四、8.寫出純整數規(guī)劃與混合整數規(guī)劃的定義，并舉例說明。9.簡述整數規(guī)劃問題的可行域與相應的線性規(guī)劃松弛問題的可行域之間的關系。10.解釋分支定界法的基本思想，并說明在分支定界過程中如何進行剪枝？五、11.什么是整數規(guī)劃的松弛問題？求解整數規(guī)劃的松弛問題有何意義？12.簡述割平面法的基本思想，并說明它是如何改進線性規(guī)劃松弛問題的解界的。13.比較單純形法求解線性規(guī)劃松弛問題和分支定界法求解整數規(guī)劃問題在基本思路上的主要不同點。六、14.對于一個標準形式的線性規(guī)劃問題，若其所有檢驗數均為非正數，且最優(yōu)解中存在取值為零的基變量，試問該最優(yōu)解是唯一最優(yōu)解嗎？請說明理由。15.已知一個整數規(guī)劃問題，其線性規(guī)劃松弛問題的最優(yōu)解為$x_1=3.6,x_2=2.4,Z=16.8$。請構造一個有效的Gomory割平面，并將其添加到松弛問題的最優(yōu)單純形表中（無需完成后續(xù)計算）。16.在比較線性規(guī)劃與整數規(guī)劃的求解難度時，通常提到多項式時間算法與非多項式時間算法。請簡要解釋什么是多項式時間算法，并說明為什么LP被認為有較好的計算復雜性而IP的計算復雜性相對較差。試卷答案一、1.線性規(guī)劃問題的標準形式為：$\maxZ=\mathbf{c}^T\mathbf{x}$s.t.$\mathbf{Ax}=\mathbf$,$\mathbf{x}\geq\mathbf{0}$，其中$\mathbf{c}=(c_1,c_2,\dots,c_n)^T$是價值向量，$\mathbf{x}=(x_1,x_2,\dots,x_n)^T$是決策變量向量，$\mathbf{A}$是$m\timesn$的系數矩陣，$\mathbf=(b_1,b_2,\dots,b_m)^T$是資源向量，$\mathbf{0}$是零向量。$\mathbf{c}^T\mathbf{x}$表示目標函數，$\mathbf{Ax}=\mathbf$表示約束條件（等式），$\mathbf{x}\geq\mathbf{0}$表示變量的非負限制。2.單純形法的基本思想是：從可行域的一個頂點（通常是原點）開始，通過迭代尋找相鄰的頂點，使得目標函數值得到改善（增大或減小），直到找到使目標函數達到最優(yōu)值的頂點為止。主要步驟包括：確定初始基本可行解和初始單純形表；計算檢驗數，判斷是否達到最優(yōu)解；若未達到最優(yōu)解，選擇入基變量和出基變量，進行基變換，得到新的基本可行解和單純形表，然后返回第一步；若檢驗數均不大于零（對于最大化問題），則當前解為最優(yōu)解。3.對偶單純形法的適用條件是：當前解是基本解，且該基本解對應的檢驗數全非正（對于最大化問題）。與標準單純形法的主要區(qū)別在于：標準單純形法從可行解出發(fā)，沿著可行方向移動到最優(yōu)解（檢驗數全非正），而對偶單純形法從最優(yōu)檢驗數條件出發(fā)，沿著非可行方向（通過出基變量）移動到新的基本解，同時保持檢驗數全非正，最終到達可行解（最優(yōu)解）。二、4.將約束條件變?yōu)榈仁剑?\begin{cases}x_1+x_2+x_3=4\\2x_1+x_2+x_4=5\end{cases}$，其中$x_3,x_4$為松弛變量。目標函數變?yōu)?\maxZ=3x_1+5x_2+0x_3+0x_4$。初始單純形表如下（僅列出核心部分）：|基變量|$x_1$|$x_2$|$x_3$|$x_4$|RHS||:-----|:----|:----|:----|:----|:-:||$x_3$|1|1|1|0|4||$x_4$|2|1|0|1|5||$Z$|-3|-5|0|0|0|基變量為$x_3,x_4$；非基變量為$x_1,x_2$。三、5.線性規(guī)劃的對偶問題是指，原問題（稱為原始問題）的目標函數系數向量構成對偶問題的資源向量，原始問題的資源向量構成對偶問題的目標函數系數向量，原始問題的約束系數矩陣轉置成為對偶問題的約束系數矩陣，原始問題的約束類型（等式或不等式）決定對偶問題的約束類型（對應），原始問題的變量類型（非負）決定對偶問題的變量類型（對應）。對于上述第4題問題，其對偶問題為：$\minW=4y_1+5y_2$s.t.$\begin{cases}y_1+2y_2\geq3\\y_1+y_2\geq5\\y_1,y_2\geq0\end{cases}$6.強對偶定理指出：若原始問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且兩者對應的最優(yōu)目標函數值相等。其在線性規(guī)劃求解中的應用價值在于：可以不直接求解對偶問題，而是利用原始問題的最優(yōu)解來得到對偶問題的最優(yōu)解；當求解對偶問題比原始問題更容易時（例如，約束條件多而變量少），可以利用對偶理論求解；對偶理論也為靈敏度分析提供了理論基礎。7.線性規(guī)劃靈敏度分析的基本思想是：當線性規(guī)劃模型中的參數（如目標函數系數、約束右端項、約束系數矩陣元素）發(fā)生微小變化時，分析這些變化對原最優(yōu)解（最優(yōu)值、最優(yōu)基）的影響。它可以分析目標函數系數$c_i$在什么范圍內變化不會改變最優(yōu)基；約束右端項$b_i$在什么范圍內變化時，最優(yōu)基保持不變，最優(yōu)解如何變化（通過對偶價格）；增加新的變量或新的約束條件對最優(yōu)解可能產生的影響。四、8.純整數規(guī)劃是指所有決策變量都必須取整數值（0,1,2,...）的整數規(guī)劃問題?；旌险麛狄?guī)劃是指決策變量中有一部分必須取整數值，另一部分可以取連續(xù)值的整數規(guī)劃問題。例如：純整數規(guī)劃：$\maxZ=3x_1+2x_2$s.t.$x_1+x_2\leq4$,$x_1,x_2\geq0$且均為整數；混合整數規(guī)劃：$\maxZ=3x_1+2x_2$s.t.$x_1+x_2\leq4$,$x_1\geq0$且為整數,$x_2\geq0$可以為連續(xù)值。9.整數規(guī)劃問題的可行域是其定義域中所有整數解的集合。對于純整數規(guī)劃，這個可行域是原始線性規(guī)劃可行域的一個子集，通常表現(xiàn)為原始可行域中由整數格點構成的區(qū)域。對于混合整數規(guī)劃，其可行域是原始可行域中，對整數變量取整數值、對連續(xù)變量取連續(xù)值的部分。因此，整數規(guī)劃的可行域通常比其對應的線性規(guī)劃松弛問題的可行域?。ɑ蛳嗤斪顑?yōu)解本身就是整數時）。10.分支定界法的基本思想是：首先求解與整數規(guī)劃問題相應的線性規(guī)劃松弛問題。若松弛問題的最優(yōu)解滿足整數約束，則該解即為整數規(guī)劃的最優(yōu)解。否則，松弛問題的最優(yōu)解不滿足整數約束，選擇一個取非整數值的變量進行分支，將原問題分解為若干子問題（通過添加不等式約束來限制該變量的取值范圍），然后對每個子問題重復求解其松弛問題或進行評估。通過不斷分支和評估（計算目標函數值、更新上界和下界），最終找到整數規(guī)劃的最優(yōu)解。剪枝是指在分支過程中，如果一個子問題的松弛解的目標函數值已經嚴格小于當前已知的整數最優(yōu)解的目標函數值（上界），或者該子問題不可能包含整數最優(yōu)解（例如，其搜索分支已經無法滿足整數約束），則可以放棄該子問題的進一步搜索，這個過程稱為剪枝。五、11.整數規(guī)劃的松弛問題是指將整數規(guī)劃問題中的整數約束（要求變量取整數值）去掉后得到的線性規(guī)劃問題。求解整數規(guī)劃的松弛問題有以下意義：它是整數規(guī)劃問題的一個下界（對于最大化問題）；它是分支定界法的基礎，即從松弛問題的最優(yōu)解開始進行搜索；對于某些特殊結構的整數規(guī)劃問題，其松弛問題的解可能本身就滿足整數約束，從而直接得到整數最優(yōu)解。12.割平面法的基本思想是：從一個不滿足整數約束的線性規(guī)劃松弛問題的最優(yōu)解出發(fā)，構造一個能夠“切割掉”松弛解可行域中一部分非整數區(qū)域，但又不過于嚴格地切割掉任何整數可行解的線性不等式（即割平面），然后將這個不等式添加到原松弛問題中，形成一個新的大些的線性規(guī)劃問題。對新問題進行求解，若得到整數解，則停止；若仍得到非整數解，則重復構造割平面并添加的過程，直到找到整數最優(yōu)解。割平面法的目的是通過逐步縮小非整數解的可行域，最終逼向整數最優(yōu)解。13.單純形法求解線性規(guī)劃松弛問題是一個迭代過程，從一個初始基本可行解出發(fā)，通過判斷檢驗數選擇入基變量和出基變量，沿著可行方向（使目標函數改善）移動到相鄰的基本可行解，直到檢驗數全非正為止。其核心在于保證每一步得到的解都是線性規(guī)劃可行域的頂點，并且目標函數值不斷改善或保持最優(yōu)。而分支定界法求解整數規(guī)劃問題，是從松弛問題的最優(yōu)解開始，首先判斷其整數可行性。若不可行，則進行分支，將搜索空間劃分為多個子問題（對應于對某個非整數變量取值的限制），然后對每個子問題求解其松弛問題或進行評估（比較目標函數值與當前上界），并決定是否剪枝。其核心在于利用整數約束將搜索空間逐步縮小，并通過比較上界和下界來逼近最優(yōu)整數解。單純形法是局部搜索方法，每次移動到更好的相鄰頂點；分支定界法是全局搜索方法，通過分支和剪枝系統(tǒng)地探索解空間的不同部分。六、14.不唯一。根據單純形法原理，若所有檢驗數均為非正數，則當前解為最優(yōu)解。若最優(yōu)解中存在取值為零的基變量，這表明存在多個最優(yōu)解。因為該基變量對應的解是對偶可行基（非基變量檢驗數非正），當該基變量從零變?yōu)榉橇銜r，只要保持其他基變量在約束條件的范圍內，目標函數值$Z$仍保持不變，從而得到另一組最優(yōu)解。因此，存在取值為零的基變量是存在多重最優(yōu)解的標志。15.已知松弛問題的最優(yōu)解為$x_1=3.6,x_2=2.4,Z=16.8$。取取整值為零的基變量，例如$x_3$（其值為4）。根據Gomory割平面法的構造方法，割平面為：$\sum_{j\inJ}a_{ij}x_j\leqb_i-\lfloorb_i^*\rfloor$，其中$J$是非基變量集合，$a_{ij}$是原約束條件的系數，$b_i$是原約束條件的右端項，$b_i^*$是當前最優(yōu)解中對應約束條件的RHS值（即松弛變量的值）。對于$x_3$對應的約束$x_1+x_2+x_3=4$，有$a_{11}=1,a_{12}=1,a_{13}=1,b_i=4,b_i^*=4$。將非基變量代入當前最優(yōu)解：$1\cdot3.6+1\cdot2.4+x_3=4$，即$6+x_3=4$，所以$x_3=4-6=-2$。割平面為：$3.6+2.4\leq4-\lfloor4\rfloor$，即$6\leq4-4$，即$6\leq0$。將此不等式標準化為$-6\geq-4$，即$6-4\leq0$。添加到單純形表中為：$\begin{array}{ccccccc}x_1&x_2&x_3&x_4&\text{RHS}\\\hline\text{(行號需根據原單純形表確定)}&-6&0&-4&\leq&0\end{array}$（此行需插入到原單純形表中適當位置，例如作為新的約束行）。16.多項式時間算法是指求解問題的計算時間隨問題規(guī)模$n$的增長而最多以多項式函數（如$n^2,n^3$）的速度增長。線性規(guī)劃（及線性規(guī)劃松弛問題）存在有效的多項式時間算法，如Khachian的ellipsoid算法和Karmark