lttaaa線性規(guī)劃(完整版)
【正文】 其中：例 一、將下列線性規(guī)劃問題化為標準形式為無約束（無非負限制） 解 : 用 替換 ，且 ， 將第 3個約束方程兩邊乘以 （－ 1）將極小值問題反號，變?yōu)榍髽O大值標準形式如下：引入變量例二、將線性規(guī)劃問題化為標準型為無約束解：（三）、單純形法例一、變成標準型約束方程的系數(shù)矩陣為基變量為非基變量I 為單位矩陣且線性獨立令：則：∴ 基本可行解為 （ 0 0 12 8 16 12） 此時， Z = 0 然后，找另一個基本可行解。每個產(chǎn)品都經(jīng)過三道工序，資料如表所示。（二）、線性規(guī)劃問題的解 ⑷ 基本解：滿足條件 ② ，但不滿足條件 ③ 的所有解，最多為 個。 如果在規(guī)劃問題的數(shù)學模型中，變量是連續(xù)的（數(shù)值取實數(shù)）其目標函數(shù)是有關線性函數(shù)（一次方），約束條件是有關變量的線性等式或不等式，這樣，規(guī)劃問題的數(shù)學模型是線性的。 要求：有目標函數(shù)及約束條件，一般有非負條件存在，由此組成規(guī)劃數(shù)學模型。∴ Xj 為基變量，否則為非基變量。問如何合理安排機床的加工任務，才能使生產(chǎn)的零件總數(shù)最多？某工廠生產(chǎn) A A2 兩種產(chǎn)品， 每件可獲利潤 120元。即⑵. 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。如此循環(huán)進行，直到找到最優(yōu)為止。 即假定人工變量在目標函數(shù)中的系數(shù)為 M（ 任意大正數(shù)），如果是求極大值，需加 M； 如果是求極小值，需加 M。需作如下處理： ⑴. 當 中出現(xiàn)兩個以上最大值時， 選下標最小的非基變量為換入變量； ⑵. 當 θ中出現(xiàn)兩個以上最小值時，選下標最小的基變量為換出變量。 2 A1A2A3 最 低需要量 甲 乙 含 食 量 物成分（五）、運 輸 問 題已知資料如表所示：單 位 銷 運價 地產(chǎn) 地產(chǎn)量銷 量模型如下：某運輸問題的資料如下：6483銷量7524852431921092產(chǎn)量單位 銷地 運價產(chǎn)地例題 3：（ 六）、作物布局問題單 土 產(chǎn) 地作物播種面 積土地面積此外，還有連續(xù)投資、投入產(chǎn)出等模型問題。在一個周期內(nèi)，各機床可能工作的機時（臺時），工廠必須完成各種零件的數(shù)量、各機床加工每個零件的時間（機時 /個）和加工每個零件的成本（元 /個）如表所示，問如何安排各機床的生產(chǎn)任務，才能完成加工任務，又使總成本最低？加工 零 時間 件機床機 時限制必 須 零件數(shù)加工 零 成本 件機床（三）、合理下料問題 一般提法 設用某種原材料截取零件 A1,A2, … A m的毛坯。 第二階段：在第一階段的最終表中，去掉人工變量，將目標函數(shù)的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表（用單純形法計算）。若當 ，而還有人工變量（非零）時，則表示原問題無可行解。 注意：為盡快找到最優(yōu)解，在換入變量時有一定的要求。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基本可行解，當目標函數(shù)達到最大時，得到最優(yōu)解。非可行解可行解基解基可行解解的基本定理⑴ 線性規(guī)劃問題的可行域是凸集（凸多邊形）。所有解的集合為可行解的集或可行域。線 性 規(guī) 劃(Linear Programming)線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃問題的求解方法線性規(guī)劃的圖解法線性規(guī)劃的單純形法單純形法的進一步討論線性規(guī)劃模型的應用 為了完成一項任務或達到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務或達到一定的目的，這個過程就是規(guī)劃。 ⑵ 最優(yōu)解：使目標函數(shù)達到最大值的可行解。凸集 凸集 不是凸集頂 點⑵ 最優(yōu)解一定是在凸集的某一頂點實現(xiàn)（頂點數(shù)目不超過 個）⑶ 先找一個基本可行解，與周圍頂點比較，如不是最大，繼續(xù)比較，直到找出最大為止。（二）、線性規(guī)劃模型的標準形式標準形式四、單純形法 特征： ⑴. 目標函數(shù)為求極大值，也可以用求極小值； ⑵. 所有約束條件（非負條件除外）都是等式，右端常數(shù)項為非負； ⑶. 變量為非負。如將目標系數(shù)大的先換入等。 加入人工變量后，目的是找到一個單位向量，叫人工基。例：第一階段cj 0 0 0 0 0 1 1cB xB b x1 x2 x3 x4 x5 x6 x70 x4 11 1 2 1 1 0 0 0 111 x6 3 4 1 2 0 1 1 0 3/21 x7 1 2 0 1 0 0 0 1 1Z 4 6 1 3 0 1 0 00 x4 10 3 2 0 1 0 0 1 －1 x6 1 0 1 0 0 1 1 2 10 x3 1 2 0 1 0 0 0 1 －Z 1 0 1 0 0 1 0 30 x4 12 3 0 0 1 2 2 50 x2 1 0 1 0 0 1 1 20 x3 1 2
黨政相關相關推薦
鄂ICP備17016276號-1