運籌學-整數(shù)規(guī)劃建模(已修改)
2025-01-30 20:39 本頁面
【正文】 第 6章 整數(shù)規(guī)劃 北京理工大學珠海學院 廖愛紅 本章內容要點 ?整數(shù)規(guī)劃相關概念 ?整數(shù)規(guī)劃問題的一般特點 ?整數(shù)規(guī)劃建模舉例 引例 甲 乙 丙 丁 A 10 12 13 15 B 15 10 15 22 C 15 15 14 17 D 20 15 13 16 人 任 務 經(jīng)濟管理當中經(jīng)常存在人員分派問題，企業(yè)中有 4個人可以勝任 4項不同工作的任意一項，但是完成工作的效率有所不同。如表所示： 為了使得企業(yè)獲得最好的經(jīng)濟效益，應該如何分派這四個人完成四項不同工作？ 整數(shù)規(guī)劃問題的提出 問題特征 變量取值范圍是離散的，經(jīng)典連續(xù)數(shù)學中的理論和方法一般無法直接用來求解整數(shù)規(guī)劃問題。 ? 不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構成的規(guī)劃問題稱為整數(shù)規(guī)劃問題的 松弛問題 。若松弛問題是一個線性規(guī)劃問題，則稱該整數(shù)規(guī)劃問題為 整數(shù)線性規(guī)劃問題 。 ? 整數(shù)線性規(guī)劃問題的分類： 純整數(shù)線性規(guī)劃問題： 要求全部變量均取整數(shù) 混合整數(shù)線性規(guī)劃問題： 要求部分變量取值為整數(shù) 01整數(shù)線性規(guī)劃問題： 決策變量取值為 0或 1 整數(shù)規(guī)劃建模中常用的處理方法 （ 1） 資本預算問題 設有 n個投資方案， cj為第 j個投資方案的收益。投資過程共分為 m個階段， bi為第 i個階段的投資總量，aij為第 i階段第 j項投資方案所需要的資金。目標是在各階段資金限制下使整個投資的總收益最大。 設決策變量 xj為對第 j個方案的?。?xj=1）或舍（ xj=0），可得到下列整數(shù)規(guī)劃問題，是 0— 1規(guī)劃。 yj yj yj x xij 為整數(shù) 9 例．某公司考慮今后五年內給以下項目投資。 ? 項目 A：每年年初可以投資，于次年末回收本利115% ，投資金額必須為 1萬元的整數(shù)倍； ? 項目 B ：每年初可購買公債，于當年末歸還，并加利息 6%，投資金額必須為 1萬元的整數(shù)倍； ? 項目 C：第 2年初可以投資，到第 5年未能回收本利140% ，投資金額必須為 1萬元的整數(shù)倍； ? 項目 D：第 3年初可以投資，到第 5年未能回收本利128% ，如果投資金額必須大于 2萬元； ? 該部門現(xiàn)有資金 10萬元，問它應如何確定給這些項目的每年投資額，使到第 5 年末擁有的資金本利總額為最大 ? 10 解： 1) 設 xiA、 xiB、 xiC、 xiD ( i ＝ 1， 2， 3， 4， 5)分別表示第 i 年年初給項目 A， B， C， D的投資額； 變量： 第 1年 第 2年 第 3年 第 4年 第 5年 A x1A x2A x3A x4A B x1B x2B x3B x4B x5B C x2C D x3D 建模中常用的處理方法（續(xù)） （ 2）指示變量： 指示不同情況的出現(xiàn) P139 例 .有 m個倉庫，要決定動用哪些倉庫，滿足 n個顧客對貨物的需要，并決定從各倉庫分別向不同顧客運送多少貨物？ 11 , 2 , ,0():iiijiy i myx i j???????動 用 倉 庫令否 則為 指 示 變 量從 倉 庫 到 顧 客 運 送 的 貨 物 量 顧客 B1 顧客 B 2 顧客 B 3 倉庫固定運營費 倉庫 A 1 6 4 6 10 倉庫 A 2 6 5 5 11 顧客需求量 150 150 200
教學課件相關推薦
鄂ICP備17016276號-1