Chapter 8 整數規劃與目標規劃.

Slides:



Advertisements
Similar presentations
—— 海淀区高三化学《考试说明》解读 2015 年 1 月 29 日 学习《考试说明》 备考理综化学.
Advertisements

猜谜语 有个小娃娃,真是没 礼貌。 见到小树摇一摇,吓 得树叶哇哇叫。 见到小花逗一逗,摘 去她的太阳帽。 没人和它交朋友,只 好自已到外处跑。
盈泰盛世精选 - 华泰并购投资基金 宝蓄财富 - 产品部. 产品基本要素 产品名称盈泰盛世精选华泰并购投资基金 管理人北京恒宇天泽投资管理有限公司 托管人国信证券股份有限公司 发行规模 1.2 亿元,以实际募集规模为准 人数限制 200 人上限 投资标的本基金委托将主要投向于华泰瑞联二期并 购基金中心(有限合合)(以企业登记的.
《公路纵断面设计》 —— 纵断面设计的要求 道桥系 二○○七年五月. 纵断面设计的一般要求 1 .纵坡设计必须满足《公路工程技术标准》中的各项规定。 2 .为保证汽车能以一定的车速安全舒顺地行驶,纵坡应具有 — 定 的平顺性,起伏不宜过大及过于频繁。尽量避免采用极限纵坡 值.缓和坡段应自然地配合地形设置,在连续采用极限长度的.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
梦想的力量.
1.1 利用平方差及完全平方的恆等式 分解因式 A 利用平方差的恆等式 B 利用完全平方的恆等式 目錄.
遞迴關係-爬樓梯.
多目標規劃 前言 3.1 基本概念 3.2 多目標單形法 3.3 妥協規劃法 3.4 案例研討.
石牌金頭腦 概數篇(可複選)加油哦!.
認識倍數(一) 設計者:建功國小 盧建宏.
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
5.1 自然對數函數:微分 5.2 自然對數函數:積分 5.3 反函數 5.4 指數函數:微分與積分 5.5 一般底數的指數函數和應用 5.6 反三角函數:微分 5.7 反三角函數:積分 5.8 雙曲函數.
LINGO.
實驗計畫資料分析作業解答 何正斌 國立屏東科技大學工業管理系.
Linear Programming: Introduction and Duality
Chapter 2 線性規劃.
Chapter 12 馬可夫鏈.
簡易C++除錯技巧 長庚大學機械系
Chapter 17 投資決策經濟分析.
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.
第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
8 動態風險規劃求解 投資組合最適化資金配置.
1.3 在整除性問題之應用 附加例題 3 © 文達出版 (香港 )有限公司.
網路遊戲版 幸福農場168號.
非線性規劃 Nonlinear Programming
第四章 線性規劃:敏感度分析與電腦報表解讀
整數規劃 Integer Programming
----直線運動 應用力學by志伯 ----直線運動
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
15.3 極大與極小 附加例題 5 附加例題 6 © 文達出版 (香港 )有限公司.
數學 近似值 有效數值.
哪些人是管理者? 管理者? 指和一群人工作,並藉由協調他人來完成工作,以便達成組織目標的人
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. 選擇敘述.
微積分網路教學課程 應用統計學系 周 章.
挑戰C++程式語言 ──第8章 進一步談字元與字串
蕭志明 老師 Algorithm(演算法) Ext:6779
地方科技基础条件资源调查管理信息系统 (标准化器)操作培训 2017年7月 呼和浩特
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
反矩陣與行列式 東海大學物理系‧數值分析.
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
11058: Encoding ★☆☆☆☆ 題組:Problem Set Archive with Online Judge
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
10328: Coin Toss ★★★☆☆ 題組:Problem Set Archive with Online Judge
1757: Secret Chamber at Mount Rushmore
13194: DPA Number II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
Parasitics Extraction (PEX) 與 postsimulation(posim)
第一章 直角坐標系 1-3 函數及其圖形.
提昇教師專業會議(華人社區) 「教師專業行為表現」專題討論 學生和家長眼中的教師專業行為 日期:2005年10月29日 地點:香港教育學院C-Lp-01室 主講 :香港教育工作者聯會 韓湛恩老師.
10599: Robots(II) ★★★★☆ 題組:Problem Set Archive with Online Judge
非負矩陣分解法介紹 報告者:李建德.
線性規劃的其他演算法 Special Simplex Method
4-1 變數與函數 第4章 一次函數及其圖形.
第四章 線性規劃:敏感度分析與電腦報表解讀
10440: Ferry Loading II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
Chapter 4 Multi-Threads (多執行緒).
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
ABC ( )已知 ,則下列哪些是x6-7x5-8x4 的因 式?(複選) (A) x+1 (B) 2x+2 (C) x3(x+1)
Chapter 16 動態規劃.
物理化學輔助學習工具 2018/12/04.
Presentation transcript:

Chapter 8 整數規劃與目標規劃

線性規劃模式 整數規劃 混合整數規劃 純整數規劃 0-1 整數規劃 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

0-1 整數規劃 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

混合整數規劃 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

純整數規劃 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

為什麼 LP 最佳解,取四捨五入的整數解是不可行? 可能是非可行解 (求 Max 去掉小數位)。 太多決策變數值要四捨五入,離最佳解會很遠。 如果決策變數值比較大(如 1234.56)四捨五入可能近似最佳解;如果決策變數值較小(如 2.78)和最佳解就「差很大」。 0-1 變數四捨五入,沒有意義。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

求極大整數規劃分限法流程圖 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題1求解 (一) 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題1求解 (二) 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題1求解 (三) 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題1求解 (四) 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題1求解(五) 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

切面法1/2 第1步:解沒有整數限制的LP問題,令為最佳解,令p = 1。 第2步:若 全為整數,則為整數規劃最佳解,停止。 第2步:若 全為整數,則為整數規劃最佳解,停止。 第3步:令 , 是最佳解右手常數, 是小於等於的最大整數。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

切面法2/2 第4步:令 ,增加一個限制式(切面): yp 是新的虛變數, 是最佳解非基變數 xj 的第 q 列的係數。 第4步:令 ,增加一個限制式(切面): yp 是新的虛變數, 是最佳解非基變數 xj 的第 q 列的係數。 第5步:增加以上限制條件到目前的LP問題,求其最佳解。或者將上列限制條件加到目前最佳解表中,再利用對偶單形法。 第6步:若以上LP問題,無可行解,則整數規劃無解,停止。 若 p > M,停止。否則 為LP最佳解,令 p = p+1,回到第2步。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解1/8 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解2/8 限制式可改寫為: 得到兩個切面限制式: 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解3/8 C1 和 C2 兩個限制式加上 LP 限制式,得到新的最佳解 x1 = 0,x2 = 5,z = 40。 利用演算法及對偶單形法,如下 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解4/8 切面法演算步驟 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解5/8 切面法演算步驟 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解6/8 切面法演算步驟 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解7/8 切面法演算步驟 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題3-解8/8 圖8-9 切面法 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

線性規劃模式兩大假設:(I) 線性規劃模式或整數規劃模式都只能有一個目標函數,但是管理的問題常常是互斥的多種目標,因此無法將管理的多目標,強迫列入這個單一目標函數中。例如: 最大化利潤與最小化成本 最小化運送成本與最大化運送數量 最大化製程輸出與最小化製程時間 最小化存貨與最大化銷售 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

線性規劃模式兩大假設:(II) 當線性規劃模式或整數規劃模式無解時,無法知道是那些限制式造成此無解的狀況。當線性規劃模式或整數規劃模式規模非常大(千或萬條限制式),但仍有無解的狀況時,從中找出是那些限制式造成此無解的狀況是非常困難且常常是不可能的任務。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃 目標規劃模式就是為解決上述兩個造成線性規劃模式或整數規劃模式使用限制上的重大假設的方法 目標規劃模式是線性規劃模式或整數規劃模式的變型,以重複執行的線性規劃方法指令來解決多目標線性規劃模式,同時將所有限制式改成目標限制式,解決線性規劃模式或整數規劃模式無解的問題。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

離差變數(Deviational Variables) di+:過多離差變數(Amount Over Deviational Variable),為超過目標i的數量 di-:不足離差變數(Amount Under Deviational Variable),為低於目標i的數量 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式之變數 在建構目標規劃模式的過程中,除了一般線性規劃模式或整數規劃模式的變數外,會運用兩種特殊的變數(離差變數),將原限制式轉換成目標限制式 。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

例題4 某製造商生產兩種商品(商品1與商品2),每單位商品1需使用5小時人工製造時間、8元的生產成本、可獲得3元的利潤;每單位商品2需使用2小時製造時間、10元的生產成本、可獲得2元的利潤。此製造商每週共有900小時可用的人工製造時間、共有2800元可用的製造資金。我們再討論一下這個製造商的目標。這些目標依其對此製造商的重要性排列包括: 為避免裁員的狀況發生,此製造商希望將所有可用的人工製造時間用完。 若假設所有生產的商品都可銷售出去,此製造商希望能獲得每週$650的利潤。 為避免資金缺口,此製造商希望每週的製造資金不超過2800元。 若人工製造時間不夠用可啟動加班機制,但是此製造商希望加班小時最少。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:建構模式 在建構目標規劃模式前,若先不考量四的目標,可將原產品組合問題的線性規劃模式列出如下: 首先定義變數如下: x = 商品1每週生產的數量 y = 商品2每週生產的數量 Max 3x + 2y s.t. 5x + 2y  900 8x + 10y  2800 x  0, y  0 此線性規劃模式的目標為最大化此製造商每週利潤,受限於製造資金人工製造時間與製造資金。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:目標1 為避免裁員的狀況發生,此製造商希望將所有可用的人工製造時間用完 假設: d1+:為超過目標1的數量的過多離差變數。 則限制式5x + 2y  900應修改為5x + 2y + d1- - d1+ = 900,且目標函式為Min P1 d1-,其中P1為第一目標的意思。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:目標2 若假設所有生產的商品都可銷售出去,此製造商希望能獲得每週$650的利潤 假設: d2+:為超過目標2的數量的過多離差變數。 d2-:為低於目標2的數量的不足離差變數。 則目標函式3x + 2y應修改為限制式3x + 2y + d2- - d2+ = 650,且目標函式為Min P1 d1-, P2 d2-,其中P2為第二目標的意思。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:目標3 為避免資金缺口,此製造商希望每週的製造資金不超過2800元 假設: d3+:為超過目標3的數量的過多離差變數。 則限制式8x + 10y  2800應修改為8x + 10y + d3- - d3+ = 2800,且目標函式為Min P1 d1-, P2 d2-, P3 d3+,其中P3為第三目標的意思。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:目標4 若人工製造時間不夠用可啟動加班機制,但是此製造商希望加班小時最少 此目標與目標1有關,因此可沿用目標1的離差變數與修改之限制式5x + 2y + d1- - d1+ = 900,只需將目標函式修改為Min P1 d1-, P2 d2-, P3 d3+, P4 d1+,其中P4為第四目標的意思。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

模式8-1 Min P1 d1-, P2 d2-, P3 d3+, P4 d1+ s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式之解題 解決目標規劃模式的步驟,是以重複執行的線性規劃或整數規劃方法指令來解決多目標線性規劃模式,其演算方法與步驟如下: 將目標1定為目前的目標,解決最小化線性規劃或整數規劃問題。 將所得到之最佳解,列為一條限制式。 若已經沒有其他的目標,則停止解題輸出最後之解。若還有其他目標則進入步驟4 將下一目標定為目前的目標,解決最小化線性規劃或整數規劃問題,並到步驟2。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

步驟1: 最小化目標1 將目標1定為目前的目標,解決最小化線性規劃問題如下: Min Z1 = d1- s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為D2),結果如下: 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z1 = d1- = 0 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

步驟2: 最小化目標2 將目標1所得到之最佳解,列為一條限制式,並將目標2定為目前的目標,解決最小化線性規劃問題如下: Min Z2 = d2- s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 Z1 = d1- = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為F2),結果如下: 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z2 = d2- = 0 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

步驟3: 最小化目標3 將目標2所得到之最佳解,列為一條限制式,並將目標3定為目前的目標,解決最小化線性規劃問題如下: Min Z3 = d3+ s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 Z1 = d1- = 0, Z2 = d2- = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為I2),結果如下: 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z3 = d3+ = 0。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

步驟4: 最小化目標4 將目標3所得到之最佳解,列為一條限制式,並將目標4定為目前的目標,解決最小化線性規劃問題如下: Min Z4 = d1+ s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 Z1 = d1- = 0, Z2 = d2- = 0, Z3 = d3+ = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為E2),結果如下: 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z4 = d1+ = 0 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式之解答 全部4個步驟都做完總結這個問題用目標規劃模式求解之後所得到的最佳解為:此製造商應生產100單位的商品1與200單位的商品2;總得利潤為700元;每週共900小時的人工製造時間且無加工;共使用2800元的製造資金。 根據上述最佳解,四個目標的達成狀況為: 目標1. 為避免裁員的狀況發生,此製造商希望將所有可用的人工製造時間用完。因為d1- = 0表示所有可用的人工製造時間都用完,所以目標1達成。 目標2. 若假設所有生產的商品都可銷售出去,此製造商希望能獲得每週$650的利潤。因為d2- = 0表示每週有至少$650的利潤,且d2+ = 50表示每週有$50多於$650的利潤,總利潤為$700,所以目標2達成。 目標3. 為避免資金缺口,此製造商希望每週的製造資金不超過2800元。因為d3+ = 0表示每週使用的製造資金並未超過2800元,所以目標3達成。 目標4. 若人工製造時間不夠用可啟動加班機制,但是此製造商希望加班小時最少。因為d1+ = 0表示每週使用的人工製造時間並未超過900小時,所以目標4達成。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

特殊目標規劃模式之問題 以8.8節中之產品組合問題為例,若除了上述的三個目標之外,將上述第4個目標換成以下目標4,再加入另一個目標5如下: 目標4. 若人工製造時間不夠用可啟動加班機制,但是此製造商希望加班小時少於100小時。 目標5. 為此製造商已與某零售商簽約,必須製造至少120單位的商品1與200單位的商品2,以免毀約。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:目標4 若人工製造時間不夠用可啟動加班機制,但是此製造商希望加班小時少於100小時 假設: d4+:為超過目標4的數量的過多離差變數。 d4-:為低於目標4的數量的不足離差變數。 則限制式5x + 2y + d1- - d1+ = 900,應加入一新的限制式d1- + d4- - d4+ = 100,且目標函式為Min P1 d1-, P2 d2-, P3 d3+, P4 d4+,其中P4為第四目標的意思。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式建構:目標5 為此製造商已與某零售商簽約,必須製造至少120單位的商品1與200單位的商品2,以免毀約 假設: d5+:為超過目標5商品1數量的過多離差變數。 d5-:為低於目標5商品1數量的不足離差變數。 d6+:為超過目標5商品2數量的過多離差變數。 d6-:為低於目標5商品2數量的不足離差變數。 應加入兩個新的限制式x + d5- - d5+ = 120 (每單位利潤$3)與y + d6- - d6+ = 200 (每單位利潤$2),且目標函式為Min P1 d1-, P2 d2-, P3 d3+, P4 d4+, P5 (3d5-+2d6-),其中P5為第五目標的意思,在這個目標中總共有兩種商品,但是因為此二商品的單位利潤不同,因此在目標中應將此單位利潤當成權數。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

模式8-2 Min P1 d1-, P2 d2-, P3 d3+, P4 d4+, P5 (3d5-+2d6-) s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 d1- + d4- - d4+ = 100 x + d5- - d5+ = 120 y + d6- - d6+ = 200 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0, d4- 0, d4+  0, d5- 0, d5+  0, d6- 0, d6+  0 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

步驟4: 最小化目標4 運用Excel解決此最小化線性規劃問題(目標位置為K2)的結果: 將目標3所得到之最佳解,列為一條限制式,並將目標4定為目前的目標,解決最小化線性規劃問題如下: Min Z4 = d4+ s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 d1- + d4- - d4+ = 100 x + d5- - d5+ = 120 y + d6- - d6+ = 200 Z1 = d1- = 0, Z2 = d2- = 0, Z3 = d3+ = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0, d4- 0, d4+  0, d5- 0, d5+  0, d6- 0, d6+  0 所得到的結果為 x = 120, y = 184, d1- = 0, d1+ = 68, d2- = 0, d2+ = 78, d3- = 0, d3+ = 0, d4- = 32, d4+ = 0, d5- = 0, d5+ = 0, d6- = 16, d6+ = 0 而目標 Z4 = d4+ = 0。 運用Excel解決此最小化線性規劃問題(目標位置為K2)的結果: 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

步驟5: 最小化目標5 運用Excel解決此最小化線性規劃問題(目標位置為P2)的結果: 將目標4所得到之最佳解,列為一條限制式,並將目標5定為目前的目標,解決最小化線性規劃問題如下: Min Z5 = 3d5-+2d6- s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 d1- + d4- - d4+ = 100 x + d5- - d5+ = 120 y + d6- - d6+ = 200 Z1 = d1- = 0, Z2 = d2- = 0, Z3 = d3+ = 0, Z4 = d4+ = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0, d4- 0, d4+  0, d5- 0, d5+  0, d6- 0, d6+  0 所得到的結果為 x = 120, y = 184, d1- = 0, d1+ = 68, d2- = 0, d2+ = 78, d3- = 0, d3+ = 0, d4- = 32, d4+ = 0, d5- = 0, d5+ = 0, d6- = 16, d6+ = 0 而目標 Z5 = 3d5- + 2d6- = 32。 運用Excel解決此最小化線性規劃問題(目標位置為P2)的結果: 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式之解答1/2 全部5個步驟都做完總結這個問題用目標規劃模式求解之後所得到的最佳解為:此製造商應生產120單位的商品1與184單位的商品2;總得利潤為728元;每週共用968小時的人工製造時間且無加工;共使用2800元的製造資金。根據上述最佳解,五個目標的達成狀況為: 目標1. 為避免裁員的狀況發生,此製造商希望將所有可用的人工製造時間用完。因為d1- = 0表示所有可用的人工製造時間都用完,所以目標1達成。 目標2. 若假設所有生產的商品都可銷售出去,此製造商希望能獲得每週$650的利潤。因為d2- = 0表示每週有至少$650的利潤,且d2+ = 78表示每週有$78多於$650的利潤,總利潤為$728,所以目標2達成。 目標3. 為避免資金缺口,此製造商希望每週的製造資金不超過2800元。因為d3+ = 0表示每週使用的製造資金並未超過2800元,所以目標3達成。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

目標規劃模式之解答2/2 目標4. 若人工製造時間不夠用可啟動加班機制,但是此製造商希望加班小時少於100小時。因為d4+ = 0表示每週使用的人工製造時間並未超過900小時,且d4- = 32表示每週100加班小時中仍有32小時未用完,所以目標4達成。 目標5.為此製造商已與某零售商簽約,必須製造至少120單位的商品1與200單位的商品2,以免毀約。因為d5- = 0與d6- = 16表示每週製造之商品1不足0單位與商品2不足16單位,所以目標5並未達成。此製造商必須毀約。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

重點結論 目標規劃模式之最佳解,會因為目標排序的順序不同,而有不同的結果,因此目標排序是目標規劃模式最重要的前置作業。以上述的例子為例,若將目標做重新的排序,則最佳解就會改變。 目標規劃模式解題最後得到之最佳解,是依順序一一將所有目標都最小化後所得到的,因此目標順序不同而會有不同的結果。若目標規劃模式中所有的限制式都依所需目標而定,則此目標規劃模式必定有可行解。若欲解決線性規劃模式中無解的問題,則可將原線性規劃模式中所有限制式都改為依目標而定之限制式,並將這些限制式之對應目標排序,以目標規劃模式一一解題。 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

電腦應用範例 管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

管理科學:作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】