久久久av698cc,久久精品福利区

一、線性目標(biāo)規(guī)劃介紹

線性規(guī)劃在實(shí)踐中得到了廣泛的應(yīng)用，但是存在兩方面的不足：一是不能處理多目標(biāo)優(yōu)化的問題；二是其約束條件過于剛性化，不允許約束資源有絲毫差錯。目標(biāo)規(guī)劃就是為了解決上述問題不足，而創(chuàng)建的一類數(shù)學(xué)模型。
在處理多目標(biāo)問題分析各類目標(biāo)的重要性時(shí)，引入了賦予個目標(biāo)優(yōu)先因子和加權(quán)系數(shù)等概念，進(jìn)一步完善了數(shù)學(xué)模型，這里僅介紹有優(yōu)先等級和加權(quán)系數(shù)的線性目標(biāo)規(guī)劃，下面所提到的目標(biāo)規(guī)劃均指線性目標(biāo)規(guī)劃。

二、目標(biāo)規(guī)劃的數(shù)學(xué)模型

在實(shí)際工廠決策時(shí)，需要考慮市場等一系列其他條件。

根據(jù)市場信息，產(chǎn)品Ⅰ的銷售量有下降的趨勢，故考慮產(chǎn)品Ⅰ的產(chǎn)量不大于產(chǎn)品Ⅱ。
超過計(jì)劃供應(yīng)的原材料時(shí)，需要高價(jià)采購，會使成本大幅度增加。
應(yīng)盡可能充分利用設(shè)備臺班，但不希望加班；
應(yīng)盡可能達(dá)到并超過利潤指標(biāo)56元。
這樣考慮產(chǎn)品決策，稱為多目標(biāo)決策問題。目標(biāo)規(guī)劃方法是解這類決策問題的方法之一。下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念。
正負(fù)偏差變量 $d^+$ , $d^?$ ：設(shè) $x_1,x_2$ 為決策變量，此外，引進(jìn)正偏差變量 $d^+$ 表示決策值超過目標(biāo)值的部分；負(fù)偏差變量 $d^-$ 表示決策值未達(dá)到目標(biāo)值的部分。因?yàn)闆Q策值不可能既要超過目標(biāo)值同事又未達(dá)到目標(biāo)值，即恒有 $d^+?d^?=0$ 。
絕對約束和目標(biāo)約束：絕對約束是指必須嚴(yán)格滿足的等式約束和不等式約束；如線性規(guī)劃問題的所有約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。目標(biāo)約束時(shí)目標(biāo)規(guī)劃特有的，可把約束右端項(xiàng)看做要追求的目標(biāo)值。在達(dá)到此目標(biāo)值時(shí)允許發(fā)生在偏差或負(fù)偏差，因此在這些約束中加入正負(fù)偏差變量，它們是軟約束。線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正負(fù)偏差變量后可變換為目標(biāo)約束。也可以根據(jù)問題的需要將絕對約束變換為目標(biāo)約束。
優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù)：一個規(guī)劃問題常常有若干目標(biāo)。但決策者在要求達(dá)到這些目標(biāo)時(shí)，是由主次或輕重緩急的。要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子 $P_1$ ，次位的目標(biāo)賦予優(yōu)先因子 $P_2，\dots$ ，并規(guī)定 $P_k>>P_{k+1},k=1,2,\dots,K$ 。表示 $P_k$ 比 $P_{k+1}$ 有更大的優(yōu)先權(quán)。即首先保證 $P_1$ 級目標(biāo)的實(shí)現(xiàn)，這是可不考慮次級目標(biāo)；而 $P_2$ 級目標(biāo)是在實(shí)現(xiàn) $P_1$ 級目標(biāo)的基礎(chǔ)上考慮的；以此類推。若要區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，這是可以分別賦予它們不同的權(quán)系數(shù) $\omega_j$ ，這些都由決策者按具體情況而定。
目標(biāo)規(guī)劃的目標(biāo)函數(shù)：目標(biāo)規(guī)劃的目標(biāo)函數(shù)（準(zhǔn)則函數(shù)）是按照個目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是。其基本形式有三種：
- 要求恰好達(dá)到目標(biāo)值，即正負(fù)偏差變量都要盡可能地小，這時(shí)： $min z = f(d^++d^-)$
- 要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能地小。這時(shí) $min z = f(d^+)$
- 要求超過目標(biāo)值，即超過量不限，但是必須是負(fù)偏差變量要盡可能地小，這時(shí) $min z = f(d^-)$

對每一個具體目標(biāo)規(guī)劃問題，可根據(jù)決策者的要求和賦予個目標(biāo)的優(yōu)先因子來構(gòu)造目標(biāo)函數(shù)。而在建立目標(biāo)規(guī)劃的數(shù)學(xué)模型時(shí)，需要確定目標(biāo)值、優(yōu)先等級、權(quán)系數(shù)等，它都具有一定的主觀性和模糊性，可以用專家評定法給以量化。

三、解目標(biāo)規(guī)劃的圖解法

對只具有兩個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型，可以使用圖解法來分析求解。
先在平面直角坐標(biāo)系的第一象限畫出各約束條件。絕對約束條件的作圖和線性規(guī)劃相同。

四、解目標(biāo)規(guī)劃的單純形法

目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上并沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但是要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，現(xiàn)做以下規(guī)定：

因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以 $c_j-z_j\geq0(j=1,2,\dots,n)$ 為最優(yōu)準(zhǔn)則。
因非基變量的檢驗(yàn)數(shù)中含有不同等級的優(yōu)先因子，即 $c_j-z_j=\sum{\alpha}_{kj}P_{k},j=1,2,\dots,n;k=1,2,\dots,K$ 因 $P_1>>P_2>>\dots>>P_K$ ；從每個檢驗(yàn)數(shù)的整體來看：檢驗(yàn)數(shù)的正負(fù)首先決定于的 $P_1$ 系數(shù) $\alpha_{1j}$ 的的正負(fù)。若 $\alpha_{1j}=0$ ，這時(shí)此檢驗(yàn)數(shù)的正負(fù)就決定于 $P_2$ 的系數(shù) $\alpha_{2j}$ 的正負(fù)，下面可以類推。

解目標(biāo)規(guī)劃問題的單純形法的計(jì)算步驟如下：

建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1，即對應(yīng)優(yōu)先因子行中的第一行開始計(jì)數(shù)。
檢查該行中是否存在負(fù)數(shù)，且對應(yīng)列的前k-1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)第三步。若無負(fù)數(shù)，轉(zhuǎn)第五步；
按最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時(shí)，選取具有較高優(yōu)先級別的變量為換出變量。
按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回第二步。
當(dāng)k=K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回第二步。

五、項(xiàng)目實(shí)戰(zhàn)

5.1 案例一
某研究所領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時(shí)，依次遵循以下優(yōu)先級順序規(guī)定：
（1）不超過年工資總額3000萬元；
（2）提級時(shí)，每級的人數(shù)不超過定編規(guī)定的人數(shù)；
（3）Ⅱ，Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無越級提升。
此外，Ⅲ級不足編制的人數(shù)可錄用新職工，又Ⅰ級的職工有10%要退休。
有關(guān)資料匯總于下表，問該領(lǐng)導(dǎo)應(yīng)如何擬定一個滿意的方案。

等級	工資額/(萬元/年)	現(xiàn)有人數(shù)/人	編制人數(shù)
Ⅰ	10.0	100	120
Ⅱ	7.5	120	150
Ⅲ	5.0	150	150
合計(jì)		370	420

解：使用線性目標(biāo)規(guī)劃來求解此問題，設(shè) $x_1,x_2,x_3$ 分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的新職工人數(shù)。對各目標(biāo)確定的優(yōu)先因子為：

$P_1$ -- 不超過年工資總額3000萬元；
$P_2$ -- 每級的人數(shù)不超過定編規(guī)定的人數(shù)；
$P_3$ -- Ⅱ、Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。

先分別建立各目標(biāo)約束。
年工資總額不超過3000萬元
$10(100-100{\times}0.1+x_1)+7.5(120-x_1+x_2)+5.0(150-x_2+x_3)+d_{1}^{-}-d_{1}^{+}=3000(萬元)$
每級的人數(shù)不超過定編規(guī)定的人數(shù)：
對Ⅰ級有： $100(1-0.1)+x_1+d_{2}^{-}-d_{2}^{+}=120(人)$
對Ⅱ級有： $120-x_1+x_2+d_{3}^{-}-d_{3}^{+}=150(人)$
對Ⅲ級有： $150-x_2+x_3+d_{4}^{-}-d_{4}^{+}=150(人)$
Ⅱ、Ⅲ級的升級面不大于現(xiàn)有人數(shù)的20%：
對Ⅱ級有： $x_1+d_{5}^{-}-d_{5}^{+}=120{\times}0.2(人)$
對Ⅲ級有： $x_2+d_{6}^{-}-d_{6}^{+}=150{\times}0.2(人)$
目標(biāo)函數(shù)： $min z = P_{1}d_{1}^{+}+P_2(d_{2}^{+}+d_{3}^{+}+d_{4}^{+})+P_3(d_{5}^{-}+d_{6}^{-})$
經(jīng)過整理后得到下列目標(biāo)規(guī)劃模型
$min z = P_{1}d_{1}^{+}+P_2(d_{2}^{+}+d_{3}^{+}+d_{4}^{+})+P_3(d_{5}^{-}+d_{6}^{-})$
$\begin{equation} \left\{ \begin{array}{r1} 2.5x_1+2.5x_2+5.0x_3+d_{1}^{-}-d_{1}^{+}=450 \\ x_1+d_{2}^{-}-d_{2}^{+}=30\\ -x_1+x_2+d_{3}^{-}-d_{3}^{+}=30\\ -x_2+x_3+d_{4}^{-}-d_{4}^{+}=0\\ x_1+d_{5}^{-}-d_{5}^{+}=24\\ x_2+d_{6}^{-}-d_{6}^{+}=30\\ x_1,x_2,x_3,d_{i}^{-},d_{i}^{+}{\geq}0(i=1,2,\dots,6) \end{array} \right. \end{equation}$
該問題最終還是轉(zhuǎn)換成了一個LP的問題，如何使用cplex來進(jìn)行求解了，這里我們需要自定義優(yōu)先因子 $P_1,P_2,P_3$ ，這里我們不妨分別取 $P_1=10,P_2=5,P_3=1$ 來代表其優(yōu)先級，權(quán)系數(shù)從這里看都是1，這里的正負(fù)偏差，我們可以當(dāng)作決策變量來考慮，即目標(biāo)規(guī)劃模型轉(zhuǎn)化為以下線性規(guī)劃模型：
$min z = 10d_{1}+0d_{2}+5(d_{3}+0d_{4}+d_{5}+0d_{6}+d_{7}+0d_{8})+1(0d_{9}+d_{10}+0d_{11}+1d_{12})$
$\begin{equation} \left\{ \begin{array}{r1} 2.5x_1+2.5x_2+5.0x_3+d_{2}-d_{1}=450 \\ x_1+d_{4}-d_{3}=30\\ -x_1+x_2+d_{6}-d_{5}=30\\ -x_2+x_3+d_{8}-d_{7}=0\\ x_1+d_{10}-d_{9}=24\\ x_2+d_{12}-d_{11}=30\\ x_1,x_2,x_3,d_{i}{\geq}0(i=1,2,\dots,12) \end{array} \right. \end{equation}$

package com.opreation.research;
import ilog.concert.*;
import ilog.cplex.IloCplex;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.util.HashSet;
import java.util.Random;

import static ilog.cplex.IloCplex.IntParam.SolnPoolIntensity;


/**
* @Description: 線性目標(biāo)規(guī)劃求解
* @Author 
* @Date 2022/7/28 14:18
*/
public class LPTest {
    
    public static void main(String[] args) throws IloException {
        try{
            
            
            // 1. 創(chuàng)建模型
            IloCplex cplex = new IloCplex();
            
            
            // 2. 定義優(yōu)化參數(shù)
            // 定義基本參數(shù)
            IloNumVar[] x = cplex.numVarArray(3, 0, Double.MAX_VALUE);
            // 定義約束參數(shù)
            IloNumVar[] d = cplex.numVarArray(12, 0, Double.MAX_VALUE);
            double[] c = {10, 0, 5, 0, 5, 0, 5, 0, 0, 1, 0, 1};
            IloNumExpr cs1 = cplex.numExpr();
            for(int i=0;i<12;i++){
                cs1 = cplex.sum(cs1,cplex.prod(c[i], d[i]));
            }
            
            
            // 3. 設(shè)置目標(biāo)函數(shù)
            cplex.addMinimize(cs1);
            // 4. 設(shè)置約束
            cplex.addEq(cplex.sum(cplex.prod(2.5,x[0]), cplex.prod(2.5,x[1]), cplex.prod(5,x[2]), d[1], cplex.prod(-1, d[0])), 450);
            cplex.addEq(cplex.sum(x[0], d[3], cplex.prod(-1, d[2])), 30);
            cplex.addEq(cplex.sum(cplex.prod(-1,x[0]), x[1], d[5], cplex.prod(-1, d[4])), 30);
            cplex.addEq(cplex.sum(cplex.prod(-1, x[1]), x[2], d[7], cplex.prod(-1, d[6])), 0);
            cplex.addEq(cplex.sum(x[0], d[9], cplex.prod(-1, d[8])), 24);
            cplex.addEq(cplex.sum(x[1], d[11], cplex.prod(-1, d[10])), 30);
            
            
            
            //            // 5. 模型求解及輸出
            if(cplex.solve()){
                cplex.output().println("Solution status = " + cplex.getStatus());
                cplex.output().println("Solution Value = " + cplex.getObjValue());
                double[] val = cplex.getValues(x);
                double[] vald = cplex.getValues(d);
                for(int j=0;j<3;j++){
                    System.out.println("x" + (j+1) + " = " + val[j]);
                }
                
                for(int j=0;j<12;j++){
                    System.out.println("d" + (j+1) + " = " + vald[j]);
                }
                
            }
            cplex.end();
        } catch (IloException e){
            System.err.println("Concert exception caught: " + e);
        }
        
    }
}

運(yùn)行結(jié)果：

Tried aggregator 1 time.
LP Presolve eliminated 1 rows and 8 columns.
Reduced LP has 5 rows, 7 columns, and 12 nonzeros.
Presolve time = 0.00 sec. (0.00 ticks)

Iteration log . . .
Iteration:     1   Dual objective     =             0.000000
Solution status = Optimal
Solution Value = 0.0
x1 = 24.0
x2 = 30.0
x3 = 0.0
d1 = 0.0
d2 = 315.0
d3 = 0.0
d4 = 6.0
d5 = 0.0
d6 = 24.0
d7 = 0.0
d8 = 30.0
d9 = 0.0
d10 = 0.0
d11 = 0.0
d12 = 0.0

結(jié)果分析：
在課本習(xí)題上給出的滿意解是取值為0，此時(shí)變量 $x_1$ (晉升到Ⅰ級的人數(shù)/人）、 $x_2$ （晉升到Ⅱ級的人數(shù)/人）、 $x_3$ （新招收Ⅲ級的人數(shù)/人）、 $d_2$ （工資總額的結(jié)余額/萬元）、 $d_4$ （Ⅰ級缺編人數(shù)/人）、 $d_6$ （Ⅱ級缺編人數(shù)/人）、 $d_8$ （Ⅲ級缺編人數(shù)/人）分別為24、30、30、16.5、6、24、0。
在cplex的給出的滿意解取值為0，此時(shí)變量 $x_1$ (晉升到Ⅰ級的人數(shù)/人）、 $x_2$ （晉升到Ⅱ級的人數(shù)/人）、 $x_3$ （新招收Ⅲ級的人數(shù)/人）、 $d_2$ （工資總額的結(jié)余額/萬元）、 $d_4$ （Ⅰ級缺編人數(shù)/人）、 $d_6$ （Ⅱ級缺編人數(shù)/人）、 $d_8$ （Ⅲ級缺編人數(shù)/人）分別為24、30、0、315、6、24、30。
這里cplex求出的滿意解和書本上的滿意解不一樣，這邊將cplex求出來的滿意解代入計(jì)算一下：
$z=10\times0+0\times315+5(0+0\times6+0+0\times24+0+0\times30)+1(0\times0+0+0\times0+1\times0)=0$
$\begin{equation} \left\{ \begin{array}{r1} 2.5\times24+2.5\times30+5.0\times0+315-0=450 \\ 24+6-0=30\\ -24+30+24-0=30\\ -30+0+30-0=0\\ 24+0-0=24\\ 30+0-0=30 \end{array} \right. \end{equation}$
從上述計(jì)算結(jié)果可知，該問題有多個滿意解，cplex求解出來的解和書本上的解都是滿意解。
5.2 案例二
已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價(jià)表見下表。有關(guān)部門在研究調(diào)運(yùn)方案時(shí)依次考慮以下七項(xiàng)目標(biāo)，并規(guī)定其相應(yīng)的優(yōu)先等級：
$P_1$ --- $B_4$ 是重點(diǎn)保證單位，必須全部滿足其需要；
$P_2$ --- $A_3$ 向 $B_1$ 提供的產(chǎn)量不少于100；
$P_3$ --- 每個銷地的供應(yīng)量不小于其需要量的80%；
$P_4$ --- 所定調(diào)運(yùn)方案的總費(fèi)用不超過最小運(yùn)費(fèi)調(diào)用方案的10%；
$P_5$ --- 因路段的問題，盡量避免安排將 $A_2$ 的產(chǎn)品往 $B_4$ ;
$P_6$ --- 給 $B_1$ 和 $B_3$ 的供應(yīng)率要相同；
$P_7$ --- 力求總運(yùn)費(fèi)最?。?br> 試求滿意的調(diào)運(yùn)方案。

產(chǎn)地	銷地				產(chǎn)量
	$B_1$	$B_2$	$B_3$	$B_4$
$A_1$	5	2	6	7	300
$A_2$	3	5	4	6	200
$A_3$	4	5	2	3	400
銷量	200	100	450	250	900/1000

解：目標(biāo)函數(shù)為：
$minz=P_1d_{4}^{-}+P_2d_{5}^{-}+P_3(d_{6}^{-}+d_{7}^{-}+d_{8}^{-}+d_{9}^{-})+P_{4}d_{10}^{+}+P_5d_{11}^{+}+P_6(d_{12}^{-}+d_{12}^{+})+P_7d_{13}^{+}$
供應(yīng)約束
$x_{11}+x_{12}+x_{13}+x_{14}{\leq}300\\ x_{21}+x_{22}+x_{23}+x_{24}{\leq}200\\ x_{31}+x_{32}+x_{33}+x_{34}{\leq}400$
需求約束
$x_{11}+x_{21}+x_{31}+d_1^{-}-d_{1}^{+}=200\\ x_{12}+x_{22}+x_{32}+d_2^{-1}-d_2^{+}=100\\ x_{13}+x_{23}+x_{33}+d_3^{-}-d_3^{+}=450\\ x_{14}+x_{24}+x_{34}+d_4{-}-d_4^{+}=250$
$A_3$ 向 $B_1$ 提供的產(chǎn)品了不少于100：
$x_{31}+d_5^{-}-d_5^{+}=100$
每個銷地的供應(yīng)量不小于其需要量的80%:
$x_{11}+x_{21}+x_{31}+d_6^{-1}-d_6^{+}=200{\times}0.8\\ x_{12}+x_{22}+x_{32}+d_7^{-}-d_7^{+}=100{\times}0.8\\ x_{13}+x_{23}+x_{33}+d_8^{-}-d_8^{-}=450{\times}0.8\\ x_{14}+x_{24}+x_{34}+d_9^{-}-d_9^{+}=250{\times}0.8$
調(diào)運(yùn)方案的總費(fèi)用不超過最小運(yùn)費(fèi)調(diào)運(yùn)方案的10%：
$\sum_{i=1}^{3}\sum_{j=1}^{4}c_{ij}x_{ij}+d_10^{-}-d_10^{+}=2960(1+10\%)$
力求總運(yùn)費(fèi)最省
$\sum_{i=1}^{3}\sum_{j=1}^{4}c_{ij}x_{ij}+d_{13}^{-1}-d_{13}^{+}=2950$
最終得到總運(yùn)費(fèi)為3360元。