簡捷法 簡捷法可用來找尋端點,並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解,再算出是否有其他解的目標函數值較此點為佳。

Slides:



Advertisements
Similar presentations
第三章 單形法 Simplex Method © 廖慶榮 作業研究 二版 p.2/45 章節大綱 1. 前言 2. 單形法的幾何意義 單形法的幾何意義 3. 單形法的代數說明 單形法的代數說明 4. 單形法的表形式 單形法的表形式 5. 特殊情況 特殊情況 6. 對於其他形式的調整 對於其他形式的調整.
Advertisements

工職數學 第四冊 第一章 導 數 1 - 1 函數的極限與連續 1 - 2 導數及其基本性質 1 - 3 微分公式 1 - 4 高階導函數.
大綱 1. 三角函數的導函數. 2. 反三角函數的導函數. 3. 對數函數的導函數. 4. 指數函數的導函數.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
矩 陣 1-1 聯立方程式 1-2 矩陣的定義 1-3 矩陣的運算 1-4 基本列運算 1-5 反矩陣 1-6 行列式.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
3-2 條件不等式 解一元 n 次不等式 二元一次不等式的圖解法 函數的極植.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
Chapter 1 矩陣 1-1 聯立方程式 1-2 矩陣的定義 1-3 矩陣的運算 1-4 基本列運算 1-5 反矩陣 1-6 行列式.
第 9 章 線性微分方程組.
一旦以節點電壓定義好每一分枝電流,克希荷夫電流定律可用於每個節點:
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
二元一次不等式 課堂練習一:圖解 x
第 4 章 線性代數:代數方法.
LINGO.
Linear Programming: Introduction and Duality
Chapter 5 迴圈.
Chapter 2 線性規劃.
数学 九年级上、下册合订 新课标(ZJ).
高斯消去法 利用基本列運算化簡線性方程組的增廣矩陣求得一組解,而且恰有一組解,但是否每一個線性方程組都是如此呢?試觀察下面的例子:
第三章 單形法 Simplex Method 作業研究 二版 2009 © 廖慶榮.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
整數線性規劃 線性規劃中有一項假設,是決策變數是連續的,且不必為整數。如果某個問題符合線性規劃連續性等其他假設,但決策變數卻必須是整數,則成為『整數線性規劃(ILP)』。 7-1.
第6章 線性規劃:單形法 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
對偶理論 「敏感度分析」,研究數學規劃問題中參數值(如各類係數)的改變對於最佳解以及目標函數值的影響。
§1 整数规划的基本特点 §2 分枝定界法 §3 割平面法 §4 分配问题及其解法 §5 整数规划的应用举例
第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
力只與位置有關的運動方程式.
Wavelet transform 指導教授:鄭仁亮 學生:曹雅婷.
数据、模型与决策 汕头大学商学院 林佳丽.
第一章 直角坐標系 1-1 數系的發展.
第四章 線性規劃:敏感度分析與電腦報表解讀
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
第一章 直角坐標系 1-3 函數圖形.
第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析.
Definition of Trace Function
小學四年級數學科 8.最大公因數.
第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
CH05. 選擇敘述.
大綱:加減法的化簡 乘除法的化簡 去括號法則 蘇奕君 台灣數位學習科技股份有限公司
第三章 直線方程式與 二元一次不等式 3-1 直線的斜角與斜率 3-2 直線方程式的求法 3-3 二元一次方程式的圖形
物理化學輔助學習工具 2018/12/04.
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
反矩陣與行列式 東海大學物理系‧數值分析.
函數應用(二)與自定函數.
第九章 布林代數與邏輯設計.
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
1-1 二元一次式運算.
1757: Secret Chamber at Mount Rushmore
第一章 直角坐標系 1-3 函數及其圖形.
非負矩陣分解法介紹 報告者:李建德.
補充 數值方法 數值方法.
線性規劃的其他演算法 Special Simplex Method
2.1 一元一次不等式 定 義 設a、b為兩個實數。.
作業系統實習課(二) -Scheduler-Related System Calls-
第四組 停車場搜尋系統 第四組 溫允中 陳欣暉 蕭積遠 李雅俐.
第四章 線性規劃:敏感度分析與電腦報表解讀
10791: Minimum Sum LCM ★★★☆☆ 題組:Problem Set Archive with Online Judge
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
解下列各一元二次方程式: (1)(x+1)2=81 x+1=9 或 x+1=-9 x=8 或 x=-10 (2)(x-5)2+3=0
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
17.1 相關係數 判定係數:迴歸平方和除以總平方和 相關係數 判定係數:迴歸平方和除以總平方和.
以下是一元一次方程式的有________________________________。
ABC ( )已知 ,則下列哪些是x6-7x5-8x4 的因 式?(複選) (A) x+1 (B) 2x+2 (C) x3(x+1)
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
物理化學輔助學習工具 2018/12/04.
Presentation transcript:

簡捷法 簡捷法可用來找尋端點,並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解,再算出是否有其他解的目標函數值較此點為佳。 線性規劃問題若有最佳解,此解必定會落在可行區域的「端點」上。 5-1

範例說明 題目請見課本106-107 因不等式為小於等於,故於不等式左邊加入寬裕變數,即可將模型變成標準式。 Max Z = X1 + 4X2 + 0S1 + 0S2 (5.1) s.t. X1 + 5X2 + S1 = 10 (5.2) 2X1 + 6X2 + S2 = 16 (5.3) X1, X2, S1, S2  0 (5.4) 5-2

專有名詞 基本解(basic solution) :標準式的線性規劃中包含n個變數與m(< n)個線性方程式;令n-m個變數為零,再解m個聯立方程式,求出剩餘m個變數值 基本可行解(basic feasible solutions):滿足所有非負限制式的基本解 非基本變數(nonbasic variables) :基本可行解中令其為0的變數.( n-m個) 基本變數(basic variables) :基本可行解中須求解的變數(>=0;m個) 基底(basis):所有基本變數的集合. 5-3

求解流程 補充 5-4

簡捷法運算步驟(1/2) 最大化問題(且限制式皆<=0),其運算步驟: 將問題表示為線性規劃模型。 在每個限制式中加入寬裕變數,以表示成標準式。 構建最初的簡捷列表。 選擇於列 - 中具有最大正值的非基本變數為進入變數,將此變數所在的欄設為主軸欄。 5-5

簡捷法運算步驟(2/2) 對於每一列計算比值 / ,其中 > 0,j為主軸欄。選擇比值最大的列為主軸列,將此列所對應的變數設為離開變數。 執行基本列運算,將主軸欄轉換成單位欄,位於主軸列上者為1,其餘者為0。 執行最佳化檢驗。若所有欄之cj - zj  0,則已找到最佳解;否則,回覆到步驟4。 5-6

範例說明(1/5) 題目請見課本106-107 因不等式為小於等於,故於不等式左邊加入寬裕變數,即可將模型變成標準式。 Max Z = X1 + 4X2 + 0S1 + 0S2 (5.1) s.t. X1 + 5X2 + S1 = 10 (5.2) 2X1 + 6X2 + S2 = 16 (5.3) X1, X2, S1, S2  0 (5.4) 5-7

範例說明(2/5) 求得一組基本解(basic solution) 令X1 =0,S2 = 0,則上述線性方程式變成: 我們得到線性系統的解如下, X1 = 0 X2 = 8/3 S1 = - 10/3 S2 = 0 此組解稱為是弘光線性規劃問題的一組基本解。 5-8

範例說明(3/5) 求基本解步驟:考慮一個以標準式表示的線性規劃問題,其中包含n個變數與m(< n)個線性方程式;令n-m個變數為零,再解m個聯立方程式,求出剩餘m個變數值。我們稱這n-m個設為零的變數為非基本變數另外m個變數則稱為基本變數。 5-9

範例說明(4/5) 基本可行解: 一組基本可行解是一組滿足所有非負限制式的基本解。 弘光問題中,令X1 =0,S2 = 0,求得X2 = 8/3,S1 = - 10/3,這組解並非一組基本可行解,因S1為負數,違反非負的限制。然而,若令X1 = 0,X2 = 0,可求得寬裕變數S1 = 10,S2 = 16,我們得到線性系統的解如下, X1 = 0 X2 = 0 S1 = 10 S2 = 16 5-10

範例說明(5/5) 此組解為一組基本可行解,因為所有變數值皆大於等於零,滿足非負的限制式。 簡捷法是一種重複的求解過程,從一組基本可行解(端點)到另一組基本可行解(端點),直到求得最佳解為止。 5-11

列表式 標準式限制式有兩個特性 <特性一>須滿足以下條件: 在限制式中,那些包含基本變數的欄中只有其基本變數係數為1其餘基本變數的係數皆為0。 <特性二> 要求每個限制方程式的右側值皆為非負數,所得到的基本解為可行解。 若將n-m個非基本變數令為0,這m個基本變數值則等於這m個限制式的右側值。 倘若一個線性規劃問題滿足上述兩個特性,則稱其已表示為一列表式。 5-12

簡捷列表符號模式介紹(1/2) 介紹簡捷列表的一般表示,其符號如下: cj = 變數j的係數 bi = 限制式i的右側值 aij = 限制式i中第j個變數的係數 A = mn的矩陣,其構成元素為aij 5-13

簡捷列表符號模式介紹(2/2) c1 c2 … cn a11 a12 … a1n b1 a21 a22 … a2n b2 … … … … … … … … am1 am2 … amn bm 因此,弘光問題的簡捷列表為: X1 X2 S1 S2 1 4 0 0 1 5 1 0 10 2 6 0 1 16 5-14

建立簡捷列表(1/5) 為改善目標值,其做法是將某一個非基本變數換成基本變數,而將目前某個基本變數換成非基本變數。 以弘光問題,表示如下: X1 X2 S1 S2 Basis CB 1 4 0 0 S1 0 1 5 1 0 10 S2 0 2 6 0 1 16 5-15

建立簡捷列表(2/5) 另一組新的基本可行解來改善目標函數值是否可行? 在簡捷列表下方加上兩列:第一列標示為zj,表示當矩陣A的第j行所對應的變數移至基底,目標函數值的減少量;第二列標示為cj - zj,則表示當矩陣A的第j行所對應的變數移至基底,目標函數值的淨變化量。 5-16

建立簡捷列表(3/5) 介紹zj列值如何計算: 若X1 = 0變成1,改變時,若仍要滿足方程式成立,其餘變數中某些變數須同時改變 運用簡捷法時,只須改變基本變數即可。例如:第一個限制式X1 + 5X2 + S1 = 10 目前基本變數S1,若X2仍為非基本變數,其值仍為X2=0,若將X1 = 0變成X1 = 1,則S1必須減少1,變成S1 = 9。 5-17

建立簡捷列表(4/5) 欲計算zj列的值,則可以將CB欄位中的係數乘以矩陣A的第j行中同列的係數,然後再加總。如: 因目標函數中X1係數c1 = 1,c1 - z1 = 1 - 0 = 1,這表示將變數X1移至基底,X1每增加一單位,目標函數值將增加1 5-18

建立簡捷列表(5/5) X2同理,建立初始簡捷列表如下: X1 X2 S1 S2 Basis CB 1 4 0 0 zj 0 0 0 0 0  目標函數值 cj - zj 1 4 0 0 目前可行解目標值(=0),其值0(10) + 0(16) = 0。 5-19

尋找下一個較佳解 (1/2) 進入基底的變數選擇法 從cj - zj 列中選擇一個可以使得目標函數值的單位改善量最大的變數。 若有多個變數,習慣選擇這些變數最左欄者。 離開基底的變數選擇法 若進入變數是位於簡捷列表的第j欄,對每一列i,若aij > 0則計算比值bi/aij 。若第i*列的比值最小,則將此列所對應的基本變數從基底移除。 若有多列有相同比值,則習慣上選擇這些列中位於最上列者所對應的基本變數。 5-20

尋找下一個較佳解 (2/2) 說明選擇變數的演算過程,在簡捷表最右側多增加了一欄來表示比值bi/aij 。 進入(主軸欄)  X1 X2 S1 S2 bi / ai2 Basis CB 1 4 0 0 S1 0 1 5 1 0 10 10/5=2 離開(主軸列) S2 0 2 6 0 1 16 6/6=8/3 zj 0 0 0 0 0 cj - zj 1 4 0 0 5-21

計算下一個簡捷列表(1/4) 運用基本列運算,將簡捷列表轉換成同義的另一組限制方程式系統,基本列運算會改變變數的係數與右側值。 執行基本列運算的主要目的是要將簡捷列表變成一種容易找出新基本可行解的型式 5-22

計算下一個簡捷列表(2/4) 回顧弘光:進入(主軸欄)  X1 X2 S1 S2 Basis CB 1 4 0 0 5-23

計算下一個簡捷列表(3/4) 同理可得新簡捷表,如下: X1 X2 S1 S2 計算結果的意義 弘光問題最初之基本可行解為 Basis CB 1 4 0 0 X2 4 1/5 1 1/5 0 2 S2 0 4/5 0 -6/5 1 4 計算結果的意義 弘光問題最初之基本可行解為 X1 = 0、X2 = 0、S1 = 10、S2 = 16 簡捷法運算後,利潤變為8,基本可行解為:X1 = 0、X2 = 2、S1 = 0、S2 = 4 5-24

計算下一個簡捷列表(4/4) 最初基本可行解對應到點1,經變換運算後,沿X2方向移離原點,在可行區域內,最遠可至點 2 ,新的基本可行解即對應到此點。 5-25

往較佳解移動(1/4) 可否找到一組較佳基本可行解,必須重新計算zj與cj - zj,建立簡捷列表: X1 X2 S1 S2 Basis CB 1 4 0 0 X2 4 1/5 1 1/5 0 2 S2 0 4/5 0 -6/5 1 4 zj 4/5 4 4/5 0 8 cj - zj 1/5 0 -4/5 0 依據進入基底的變數選擇法,選擇了X1為進入變數,因其c1 – z1 = 1/5是cj - zj 列中最大的正數。 5-26

往較佳解移動(2/4) 接著決定離開變數,由於進入變數是位於簡捷列表的第1欄,對每一列i,若ai1 > 0則計算比值bi/ai1,如下: 進入(主軸欄)  X1 X2 S1 S2 Basis CB 1 4 0 0 X2 4 1/5 1 1/5 0 2 2/(1/5)=10 S2 0 4/5 0 -6/5 1 4 4/(4/5)=5 離開 zj 4/5 4 4/5 0 8 cj - zj 1/5 0 -4/5 0 因第2列比值最小,將此列所對應的基本變數從基底移除 5-27

往較佳解移動(3/4) 執行基本列運算步驟,可得簡捷列表: X1 X2 S1 S2 Basis CB 1 4 0 0 zj 1 4 1/2 1/4 9 cj - zj 0 0 -1/2 -1/4 得基本可行解X1 = 5、X2 = 1、S1 = 0、S2 = 0 目標函數值為: Z = X1 + 4X2 = 1(5) + 4(1) = 9 5-28

往較佳解移動(4/4) 由於列cj - zj中的所有數皆非正數,則表示當矩陣的任一欄所對應的變數移至基底,目標函數值的淨變化量皆為非正值, 即無法增大目標函數值,因此這組解已經是最佳解,此時的最大利潤值為9。 5-29

最佳解條件 當簡捷列表中cj - zj列的所有數皆為0或負數時,則表示已經找到最佳解,即為基本可行解。 5-30

一般情況之簡捷列表(1/7) 題目請見課本p122-123 將題目模型變成標準式,即於小於等於不等式左邊加上寬裕變數,於大於等於不等式左邊減去剩餘變數,將模型變成標準式 之後加入新人工變數:a3 (0) X1 + 5X2 + S1 = 10 (5.10) 2X1 + 6X2 + + S2 = 16 (5.11) X1 + X2 - S3 + a3 = 5 (5.12) 5-31

一般情況之簡捷列表(2/7) 若令X1 = X2 = S3 = 0,可得解:X1 = 0、X2 = 0、S1 = 10、S2 = 16、S3 = 0、a3 = 5 雖此解不是實際問題的可行解,確為可行解,可作為簡捷法運算的初始解,只要在得到最佳解之前將其移出基底,就不會違反實際問題的可行性。 5-32

一般情況之簡捷列表(3/7) 將其成本設為非常大正數,一般用M來表示。則目標函數為: Max X1 + 4X2 + 0S1 + 0S2 + 0S3 – Ma3 建立初始的簡捷列表 X1 X2 S1 S2 S3 a3 Basis CB 1 4 0 0 0 -M S1 0 1 5 1 0 0 0 10  S2 0 2 6 0 1 0 0 16 a3 -M 1 1 0 0 -1 1 5 zj -M -M 0 0 M -M -5M cj – zj 1+M 4+M 0 0 -M 0 5-33

一般情況之簡捷列表(4/7) 第一次主軸變換,進入變數為X2,離開變數為S1,運算結果如下:  X1 X2 S1 S2 S3 a3 Basis CB 1 4 0 0 0 -M X2 4 1/5 1 1/5 0 0 0 2 S2 0 4/5 0 -6/5 1 0 0 4 a3 -M 4/5 0 -1/5 0 -1 1 3  zj 4 0 M -M 8-3M cj - zj 0 0 -M 0 5-34

一般情況之簡捷列表(5/7) 第二次主軸變換,進入變數為X1,離開變數為a3,運算結果如下:  X1 X2 S1 S2 S3 a3 Basis CB 1 4 0 0 0 -M X2 4 0 1 1/4 0 1/4 -1/4 5/4 S2 0 0 0 -1 1 1 -1 1  X1 1 1 0 -1/4 0 -5/4 5/4 15/4 zj 1 4 3/4 0 -1/4 1/4 35/4 cj - zj 0 0 -3/4 0 1/4 5-35

一般情況之簡捷列表(6/7) 第三次主軸變換,進入變數為S3,離開變數為S2,運算結果如下: X1 X2 S1 S2 S3 a3 Basis CB 1 4 0 0 0 -M X2 4 0 1 1/2 -1/4 0 0 1 S3 0 0 0 -1 1 1 -1 1 X1 1 1 0 -6/4 5/4 0 0 5 zj 1 4 1/2 1/4 0 0 9 cj - zj 0 0 -1/2 -1/4 0 -M 5-36

一般情況之簡捷列表(7/7) 因上表之cj - zj列上的值皆非正數,且人工變數a3已經移離基底,所以已得最佳解 倘若,線性規劃問題cj - zj列上的所有值皆非正數,仍有至少一個人工變數aj不為0,則此線性規劃問題無解。 5-37

HW 1, 2, 3, 4, 5, 7, 10, 12 5-38