lttaaa線性規(guī)劃-文庫吧
2025-07-20 09:30 本頁面
【正文】 習 題 1用圖解法求解下面的線性規(guī)劃問題：x1x2 123(2)x1x2 123(1)（一）、基本思想 將模型的一般形式變成標準形式，再根據(jù)標準型模型，從可行域中找一個基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基本可行解，當目標函數(shù)達到最大時，得到最優(yōu)解。（二）、線性規(guī)劃模型的標準形式標準形式四、單純形法 特征： ⑴. 目標函數(shù)為求極大值，也可以用求極小值； ⑵. 所有約束條件（非負條件除外）都是等式，右端常數(shù)項為非負； ⑶. 變量為非負。轉(zhuǎn)換方式： ⑴. 目標函數(shù)的轉(zhuǎn)換 如果是求極小值即 ，則可將目標函數(shù)乘以（－ 1），可化為求極大值問題。也就是：令 ，可得到上式。即⑵. 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量⑶. 變量的變換 若存在取值無約束的變量 ，可令 其中：例 一、將下列線性規(guī)劃問題化為標準形式為無約束（無非負限制） 解 : 用 替換 ，且 ， 將第 3個約束方程兩邊乘以 （－ 1）將極小值問題反號，變?yōu)榍髽O大值標準形式如下：引入變量例二、將線性規(guī)劃問題化為標準型為無約束解：（三）、單純形法例一、變成標準型約束方程的系數(shù)矩陣為基變量為非基變量I 為單位矩陣且線性獨立令：則：∴ 基本可行解為 （ 0 0 12 8 16 12） 此時， Z = 0 然后，找另一個基本可行解。即將非基變量換入基變量中，但保證其余的非負。如此循環(huán)下去，直到找到最優(yōu)解為止。 注意：為盡快找到最優(yōu)解，在換入變量時有一定的要求。如將目標系數(shù)大的先換入等。找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束其步驟總結(jié)如下：當 時， 為換入變量確定換出變量為換出變量接下來有下式： 用高斯法，將 的系數(shù)列向量換為單位列向量，其步驟是：結(jié)果是：代入目標函數(shù)： 有正系數(shù)表明：還有潛力可挖，沒有達到最大值；此時：令 得到另一個基本可行解 （ 0， 3， 6， 2， 16， 0） 有負系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費用。當 時，即不再利用這些資源。如此循環(huán)進行，直到找到最優(yōu)為止。本例最優(yōu)解為： （ 4， 2， 0， 0， 0， 4）（四）、單純形表判定標準：若求 或例 題：cj 2 3 0 0 0 0cB xB b x1 x2 x3 x4 x5 x60000x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z 0 2 3 0 0 0 012/28/2－12/4 x1 x 5 6 4 0 0 0 1 0 3 x2 3 0 1 0 0 0 1/426 2 0 1 0 0 1/21 0 0 1 0 1/2cj 2 3 0 0 0 0cB xB b x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 1/2 1 0 0 1 0 1/2 4 0 0 0 1 0 0 1 0 0 0 1/4Z 9 2 0 0 0 0 3/46/2216/4－ 2 3 0 0 0 0cB xB b x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 2 0 1/2 1 0 0 1 0 1/2 0 0 0 4
黨政相關相關推薦
鄂ICP備17016276號-1