作業研究 第二章 線性規劃 林吉仁 著 高立圖書公司出版.

Slides:



Advertisements
Similar presentations
手工加工全框眼镜技术 前调整确定加工基准制作模板割边 磨边磨安全角 (抛光) 装配 后调整检测.
Advertisements

融资融券业务的保证金与保证金比例 光大证券 · 信用业务管理总部 2015 年 12 月 ★融资融券业务投资者教育活动材料★
道家養生保健長壽藥膳 藥膳應用原則: 天人相應,道法自然 藥膳有兩個職能: 一是保健增壽,一是治療疾病。 ◎ 黃蕙棻.
盈泰盛世精选 - 华泰并购投资基金 宝蓄财富 - 产品部. 产品基本要素 产品名称盈泰盛世精选华泰并购投资基金 管理人北京恒宇天泽投资管理有限公司 托管人国信证券股份有限公司 发行规模 1.2 亿元,以实际募集规模为准 人数限制 200 人上限 投资标的本基金委托将主要投向于华泰瑞联二期并 购基金中心(有限合合)(以企业登记的.
《公路纵断面设计》 —— 纵断面设计的要求 道桥系 二○○七年五月. 纵断面设计的一般要求 1 .纵坡设计必须满足《公路工程技术标准》中的各项规定。 2 .为保证汽车能以一定的车速安全舒顺地行驶,纵坡应具有 — 定 的平顺性,起伏不宜过大及过于频繁。尽量避免采用极限纵坡 值.缓和坡段应自然地配合地形设置,在连续采用极限长度的.
1 主題三 網路常見衝突事件 的防範 3-1 認識網路兩性交往常見的衝突事件 3-2 瞭解處理兩性網路交往衝突之注意事項 3-3 認識處理兩性網路交往常見的衝突事件的 有效方法 有效方法.
動動腦時間 — 腦筋急轉彎 —. 1. 有三個小朋友在猜 拳,一個出石頭,一 個出布,一個出剪刀, 請問三個人共有幾根 指頭? 答案: 60 根.
第二节 脉搏的评估及异 常时的护理. 教学目标  1 、解释有关名词  2 、说出脉搏、呼吸的正常值  3 、叙述脉搏、呼吸的测量方法;识别脉搏、 呼吸的异常变化  4 、叙述测量脉搏、呼吸的注意事项  5 、正确记录脉搏、呼吸,做到认真负责,实 事求是。
项目四、腻子的施工  一、准备工作  二、安全与卫生  三、板件表面的处理  四、准备腻子  五、刮腻子  六、腻子的干燥  七、腻子的打磨  结束.
诗词鉴赏的术语及含义.
泛黄的春联还残留在墙上 依稀可见几个字岁岁平安 在我没回去过的老家米缸 爷爷用楷书写一个满 黄金葛爬满了雕花的门窗 夕阳斜斜映在斑驳的砖墙 铺着榉木板的屋内还弥漫 姥姥当年酿的豆瓣酱 我对着黑白照片开始想像 爸和妈当年的模样 说着一口吴侬软语的姑娘缓缓走过外滩 消失的旧时光一九四三 在回忆的路上时间变好慢.
河南中考电学考题汇总 涉村三中 翟新伟.
冷 热 疗 法.
個人理財規劃 第八章 投資規劃.
大洋洲.
保育员工作职责.
开天门 梅州市中医医院 郑雪辉.
小儿斜颈的诊断与治疗.
未成年少女墮胎的法律問題.
当代 国 际 关 系(案例6) 冷战时期美苏关系的演变.
政府採購法規概要 報告人:杜國正 行政院公共工程委員會企劃處.
说课课件 感悟工业革命力量,闪耀科技创新光辉 ----《走向整体的世界》教学设计及反思 爱迪生 西门子 卡尔·本茨 诺贝尔 学军中学 颜先辉.
中式面点技艺 长春市商业职业技术学校 王成贵 中式面点技艺 长春市商业职业技术学校 授课教师: 王 成 贵.
手太阳小肠经.
消防安全知识讲座 ---校园防火与逃生 保卫科.
一、平面点集 定义: x、y ---自变量,u ---因变量. 点集 E ---定义域, --- 值域.
“炝虾”食用安全性的 初步研究 上海市吴淞中学生物与环境社团 责任者:李 胤 吴蓓莉 指导老师:张 治 许 沁.
之 魔 析 妖 鬼 解 怪 大 沈家仪小组出品.
游泳四式技術分析暨初級教法.
第三章 儿童少年、女子及 中老年的体育卫生 第一节 儿童少年的体育卫生
美国史 美利坚合众国创造了一个人类建国史的奇迹,在短短230年的时间从一个被英帝国奴役的殖民地到成为驾驭全世界的“超级大国”、“世界警察”,美国的探索为人类的发展提供了很宝贵的经验。
第六单元 百病始生.
学生学业水平诊断与提升策略探究 平阳中学 周秀丽.
征服火灾是全社会的事业,它需要科技的进步,需要消防监督,也需要消防科学知识的普及和提高。通过各类的消防安全培训,从而使人们更好的掌握消防常识和了解消防法规,提高消防安全意识,提高自防自救能力,使我们的生产和生活远离火灾的侵袭。
管理学基本知识.
上海第二医科大学附属瑞金医院临床微生物科
足球運動情報蒐集與分析 趙榮瑞 教授.
滁州学院首届微课程教学设计竞赛 课程名称:高等数学 主讲人:胡贝贝 数学与金融学院.
战 后 国 际 关 系 专题五:冷战时期美苏关系的演变 政治学与行政管理系.
講師:賴玉珊 心理師 證照:諮商心理師(諮心字第001495號) 學歷:國立台南大學諮商與輔導研究所 畢 現任:長榮大學諮商中心專任心理師
二、汽化和液化.
工 程 力 学 主讲教师:李林安.
复习: 一、细胞膜的成分 1、脂质 2、蛋白质 3、糖类 二、生物膜的功能: 1、界膜 2、控制物质的进出 3、进行细胞间信息交流.
第九章 长期资产及摊销 2017/3/21.
崇拜即將開始,請大家安靜片刻, 預備心靈敬拜上帝。
第1节人体内物质的运输 人体的组织细胞每时每刻都需要营养物质和氧,并不断产生二氧化碳、尿素等废物。这些物质在人体内运输主要依靠 系统。人体的血液循环系统由 、 和 组成。 血液循环 血管 心脏 血液.
拾貳、 教育行政 一、教育行政的意義 教育行政,可視為國家對教育事務的管理 ,以增進教育效果。 教育行政,乃是一利用有限資源在教育參
膝关节常见病 康复科.
課程銜接 九年一貫暫行綱要( )  九年一貫課程綱要( ) 國立台南大學數學教育系 謝 堅.
2.4 二元一次方程组的应用(1).
第3节 以水为主要传热介质 的烹调方法.
母系氏族社会代表 时间 代表区域 具体地点 房屋样式 农作物 生产工具 手工业 河姆渡原始居民 半坡原始居民 距今约五六千年
第一章 汽车的解体与清洗 第一节 汽车解体工艺 一、零件的拆卸原则 1、拆卸前应熟悉被拆总成的结构
汽 车 文 化.
線 性 代 數 第 1 章 線性方程式系統.
第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法.
教科版初中九年级物理 第五章 欧姆定律 3 等效电路.
第九章 责任会计 第一节 责任会计概述 第二节 不同类型的责任中心的责任会计 第三节 内部转移价格 第四节 责任预算、责任报告与业绩考核.
Chapter 3 線性規劃單形法.
敏感度與參數分析 Sensitivity and Parametric Analyses
網路遊戲版 幸福農場168號.
第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析.
电工电子技术实验 电工电子教学部.
評分標準.
課稅負擔的歸屬.
6.6 線性規劃的單體法 單體法 (simplex method)
实验八 石蜡切片法.
第五章 對偶理論 Duality Theory 作業研究 二版 2009 © 廖慶榮.
提昇教師專業會議(華人社區) 「教師專業行為表現」專題討論 學生和家長眼中的教師專業行為 日期:2005年10月29日 地點:香港教育學院C-Lp-01室 主講 :香港教育工作者聯會 韓湛恩老師.
用加減消去法解一元二次聯立方程式 台北縣立中山國中 第二團隊.
Presentation transcript:

作業研究 第二章 線性規劃 林吉仁 著 高立圖書公司出版

2-1 簡介 典型的線性規劃(LP)數學模式如下: 其他名詞:可行解、可行區、最佳 解、線性、 非線性 林吉仁著 目標函數 功能限制式 非負限制式 決策變數 其他名詞:可行解、可行區、最佳 解、線性、 非線性

2-2 圖解法 使用時機:LP問題只有兩個決策變數時 圖解法步驟: (1)在座標平面劃出所有限制式的“半平面”, 林吉仁著 2-2 圖解法 使用時機:LP問題只有兩個決策變數時 圖解法步驟: (1)在座標平面劃出所有限制式的“半平面”, 而所有半平面的交集即是可行區域 (2)設目標函數 Z=c1x+c2y , 劃出梯度 Z=[c1, c2]的方向 (3)劃出垂直於 Z的平行線系 (4)平行線系沿Z方向(反方向)移動,與可行 區域最後接觸的點,即是Z產生最大值(最 小值)的地方。

林吉仁著 例題2-1

林吉仁著

線性規劃的一般性質 1. 可行區域可能是空集合、有界的 、無界的 林吉仁著 線性規劃的一般性質 1. 可行區域可能是空集合、有界的 、無界的 2.線性規劃的最佳解有四種可能情形: (1) 無解;(2) 恰有一個最佳解;(3) 有無限多個最佳解; (4) 目標無限值解 ( 屬於找不出最佳解 ) 3.( 頂點定理 ) 假設可行區域非空集合 (1)若可行區域有界,則最佳解必存在,且必可於頂點 找到最佳解 (2)若可行區域無界,則可能有最佳解或是目標無限值 解。若存在最佳解,則必可於頂點找到最佳解。 4. 若可行區域某頂點的Z值優於 ( 或不劣於 )所有鄰近 頂點的Z值,則該頂點即是最佳解,其Z值即最佳值

林吉仁著 LP最佳解可能情形

林吉仁著 例題2-2 設某公司有大、中兩型貨車,大型貨車上有20單位的冷藏空間,30單位的非冷藏空間;中型貨車上有20單位的冷藏空間,10單位的非冷藏空間。今有某商人需用160單位的冷藏空間,120單位的非冷藏空間,由台北運貨至高雄,問此公司應使用大型、中型貨車各若干輛,以使其汽油最節省。但已知大型貨車一趟需300加侖汽油,中型貨車一趟需200加侖汽油。

林吉仁著

林吉仁著 例題2-3

林吉仁著

林吉仁著 例題2-4 某工廠用三種原料甲、乙、丙,製造X、Y兩種成品 。每噸的X需要甲6噸,乙4噸,丙12噸,可得利潤為2萬元。每噸的Y,需要甲4噸,乙6噸,丙3噸,可得利潤6萬元。本月份購入原料甲、乙、丙各為60噸,根據這個來擬定生產目標,應該生產X種成品 x 噸,Y種成品 y 噸,才可得到最大利潤 p 萬元,求 x, y, p之值?

林吉仁著 解: 依題意建立線性規劃模式  沿 p=[2,6] 方向,p 愈右上移,p 值愈大。x=0,y=10 時 p 有最大值60

2-3單體法 (Simplex Method) 決策變數有三個以上時,不適用圖解法 林吉仁著 2-3單體法 (Simplex Method) 決策變數有三個以上時,不適用圖解法 單體法(Simplex Method)1947年由線性規劃之父G. B. Dantzig發展出來 單體法由原點出發往相鄰頂點前進,每次的頂點目標值必優於前一次的頂點,如此反覆進行,不須檢查所有頂點即可求得最佳解 單體法通常是在單體表中進行 使用單體法須先將LP問題化成“正規型”

化成“正規型”的步驟 1.檢查每一變數是否均有非負限制式 林吉仁著 化成“正規型”的步驟 1.檢查每一變數是否均有非負限制式 2.Max Z=f(x1,x2,…,xn)  Max Z f(x1,x2,…,xn) =0 3.功能限制式RHS是否均大於等於 0 4.功能限制式的關係符號, (1)為“”時,增一“+s”,s  0,且改為“=”號 (2)為“=”時,增一“r”,r  0,且目標左邊增“+Mr” (3)為“”時,增一個“u”,一個“+r”,u0,r  0 且改為“=”號,且目標左邊增加“+Mr” 5.填入單體表

其他要點 2.多個s時,可依序以s1,s2,…表之,r、u亦同 3.事實上,人工變數r=0 林吉仁著 其他要點 1.目標函數若有常數,移項時可將常數留在右邊。 2.多個s時,可依序以s1,s2,…表之,r、u亦同 3.事實上,人工變數r=0 4.莫忘每加入r,立即在正規目標函數左邊增“+Mr” 5. M在術語上稱為大 M(Big-M) 6.正規型除了非負限制式,關係符號應全為等號 又如果將正規型中人工變數的項全刪除,並使用原來的目標式,稱為等式型 (equation form) 7.正規型的解稱為擴充解。可行頂點的擴充解,稱為可行基解

林吉仁著 例題2-5 化為正規型、等式型 (1) (2)

林吉仁著 解: (1) (正規型) (等式型)

林吉仁著 (2) (正規型) (等式型)

單體法步驟 1. 將問題填入單體表中。取Z與各限制式中之si , ri 填入基變數欄。 2. 將起始單體表調整成適當型,此解稱為起始可行基解 林吉仁著 單體法步驟 1. 將問題填入單體表中。取Z與各限制式中之si , ri 填入基變數欄。 2. 將起始單體表調整成適當型,此解稱為起始可行基解 3. 最佳解檢定:若表中Z列的變數係數均0,則到步驟7.,否則到步驟4. 4. 選取基準行:以Z列變數係數的最負值欄為基準行,該行的變數為調入變數。當最負值不止一個時,可任取其一。

如果基準行元素均小於等於0,我們無法選出基準列,此時代表Z是無限值解,停止運算。 林吉仁著 5. 選取基準列:計算各列「右手常數除以基準行“正數”元素」,取此比率最小之列為基準列,該列之基變數為調出變數。此步驟是為了保持符合可行解檢定。基準行與基準列交集元素稱為基準元素 (pivot)。 如果基準行元素均小於等於0,我們無法選出基準列,此時代表Z是無限值解,停止運算。

6. 基變數的調整:利用「單體法的列運算」將基準行變成基準元素為1的單位行向量,並在基變數欄以調入變數取代調出變數。回到步驟3.。 林吉仁著 6. 基變數的調整:利用「單體法的列運算」將基準行變成基準元素為1的單位行向量,並在基變數欄以調入變數取代調出變數。回到步驟3.。 ※單體法的列運算有二: (1)基準列乘一數使基準元素為1。 (2)基準列乘一數加到另一列使基準行 ( 除基準元素外 ) 所有元素為0。 7. 停止運算。判讀最佳解。  

林吉仁著 例題2-6 試以單體法解

林吉仁著 解: 化成正規型如下 填入單體表進行單體法

林吉仁著 當x1 = 150, x2 = 100, s1 = s2 =0 時, Z 有最大值2800

林吉仁著 例題2-7 解線性規劃問題

林吉仁著 解: 化成正規型如下 填入單體表進行單體法

故得 x = 4, y = 4, s1 = u2 = r2 = 0時,Z有最大值12 ( 注意:r2 = 0) 林吉仁著 故得 x = 4, y = 4, s1 = u2 = r2 = 0時,Z有最大值12 ( 注意:r2 = 0)

2-4目標函數、限制式的處理 1.目標函數的處理: (1) 目標函數是min 時,處理方式有兩種: (a) 修改單體法準則,改變的有 林吉仁著 2-4目標函數、限制式的處理 1.目標函數的處理: (1) 目標函數是min 時,處理方式有兩種: (a) 修改單體法準則,改變的有 「最佳解檢定」改成「Z係數均小於等於0」。 「選取基準行」改成「以Z列係數正的最大值欄為基準行」 (b)先將目標函數乘一負號,轉化為max,待求出最佳解再乘一負 號加以還原 (2) 當目標函數為 min max (f1, f2, , fk) 可化為線性表示法如右:   目標函數為 max min (f1, f2, , fk) 的問題,可用類似方式處理

2. 限制式的處理:通常是處理使變數均有非負限制式,使限制式為線性等。同時,盡量減少變數個數,以方便解題。 林吉仁著 2. 限制式的處理:通常是處理使變數均有非負限制式,使限制式為線性等。同時,盡量減少變數個數,以方便解題。

林吉仁著 3. 功能限制式右手常數的處理:若右手常數為負值,只要全式乘一負號即可。 課本中尚有許多單體法例題請多練習

2-5單體法解的特殊情形 一般情形: 非基變數值為0,而基變數值不為0。當基變數數值為0,即產生了退化。 林吉仁著 2-5單體法解的特殊情形 一般情形: 非基變數值為0,而基變數值不為0。當基變數數值為0,即產生了退化。 基變數行向量在目標列的係數為0,而非基變數對應的應不為0。若非基變數在目標列係數也為0,即可能有了多重最佳解。 當無基準行時,則停止運算並依人工變數是否為0,判定無解或已找出最佳解。 當有基準行(max目標列係數有負值者),卻無基準列時,停止運算。而目標則是無限值解。

林吉仁著 2-5-1多重最佳基解 在最佳解的單體表,若有非基變數的行向量在目標列的元素為0,且若以此非基變數為調入變數,也存在調出變數,則此線性規劃問題存在多重最佳基解。若就前面所說的方式變換其基變數,仍會得到相同的 Z 值。事實上此兩最佳基解之間的線性組合均是最佳解。

林吉仁著 例題2-12 線性規劃問題

林吉仁著 最佳解的單體表如下

2-5-2退化解 退化是指有基變數值為0 退化的產生有兩種可能: (1)在起始時,正規型中有RHS為0 林吉仁著 2-5-2退化解 退化是指有基變數值為0 退化的產生有兩種可能: (1)在起始時,正規型中有RHS為0 (2)在運算過程中,當比率最小值不唯一時, 在下一小表中,必會產生退化 遇到退化時,仍按一般方式運算,可能產生循環 (cycling) 現象,但機會很小。

2-5-3無限值解 在無大M單體表的演算過程中,存在了基準行,但,不存在基準列,則此問題是無限值解 大 M 法時,若有基準行不存在基準列, 林吉仁著 2-5-3無限值解 在無大M單體表的演算過程中,存在了基準行,但,不存在基準列,則此問題是無限值解 大 M 法時,若有基準行不存在基準列, (1)若所有人工變數均為0,則本題為無限值解。 (2)若有人工變數不為0,而基準行是對應目標列元素最負值,則本題無可行解;若基準行不是對應目標列元素最負值,則改換基準行繼續作下去

林吉仁著 例題2-15 解

林吉仁著 解: ∵ 尚未達最佳解,但若選 x1 為調入變數,不存在調出變數, ∴ 為無限值解。

林吉仁著 2-5-4 無 解 當所有限制式的交集區域為空集合,即不存在任何可行解時,當然就不存在最佳解。而表現在單體表中的即目標列變數係數已均大於等於0,停止運算了,但卻有人工變數 ri 不為0,則此問題無解。

2-6雙階法 (Two-phase Method) 林吉仁著 2-6雙階法 (Two-phase Method) 雙階法是大 M法之外,是處理人工變數的另一種方法 雙階法步驟: (1)以min Q =  ri 為第一階段的目標函數,原目標函數視為限制式 ( 但不可為基準列 ) (2)第一階段完成,若目標值    (a) Q  0,本題無解,停止運算。    (b) Q = 0,進入第二階段。刪去 Q 與 ri 相關 之列、行,利用原目標函數對應之列為 目標列,繼續往下運算。

林吉仁著 例題2-16 以雙階法求解

林吉仁著 解: 化為雙階法正規型如下

林吉仁著 故 x1 = 0, x2 = 0, x3 = 4 時,Z 有最大值 8

林吉仁著 例題2-17 以雙階法求解

林吉仁著 解: 化為雙階法正規型如下

林吉仁著 ∵ Q = 4  0 ∴ 本題無可行解。

林吉仁著 2-7存在起始可行基變數 當線性規劃問題的 = 號、 號功能限制式已存有變數可作為起始基變數時,則以單體法求解可不須引入人工變數,以節省運算。但勿忘先調整起始單體表為適當型。 (例題請參考課本)

2-8線性規劃的基本假設 線性規劃的基本假設有四: 1.成比例性:投入與產出的比例是固定的 2.可加性:變數代表的活動互相獨立 林吉仁著 2-8線性規劃的基本假設 線性規劃的基本假設有四: 1.成比例性:投入與產出的比例是固定的 2.可加性:變數代表的活動互相獨立 3.確定性:模式中的係數都是確定的數值 4.可分割性:變數可以是0.5、3/2等非整數

2-9單體法效率的影響因素 單體法程式效率受下列因素影響: 1.功能限制式個數:求解時間約與功能限制式個數的三次方成正比。 林吉仁著 2-9單體法效率的影響因素 單體法程式效率受下列因素影響: 1.功能限制式個數:求解時間約與功能限制式個數的三次方成正比。 2.變數的個數:變數個數若增為2倍,求解時間增加略少於2倍。 3.功能限制式係數的密度:密度低可加速解題速度。