區(qū)間線性規(guī)劃最優(yōu)解對應的約束矩陣的構(gòu)造

(杭州電子科技大學理學院，浙江 杭州310018)

0 引 言

對于不確定性規(guī)劃，人們一般引用隨機或者模糊技術(shù)。但在實際問題中，概率分布和隸屬函數(shù)往往是不可知的[1-2]，因此近年來區(qū)間線性規(guī)劃得到廣泛研究。然而，對于求最優(yōu)解相對應的約束矩陣的問題，目前所得方法只能針對最優(yōu)解求出唯一的一組約束矩陣[3]。區(qū)間線性規(guī)劃可分為3種形式[4]，本文對帶有區(qū)間線性方程組的問題進行討論，在原方法的基礎上進一步研究，從而構(gòu)造出一個最優(yōu)解所對應的無數(shù)多組約束矩陣。

1 準備知識

矩陣A≤B是指A的每個分量小于等于B 中對應的分量，A=(aij)的絕對值為|A|=(|aij|)。

下列定義與文獻[6]所給出的相同。

定義1 給定A∈Rm×n，b∈Rm，c∈Rn，問題稱為一個線性規(guī)劃問題，可簡寫為稱A，b為約束矩陣，c為目標函數(shù)的系數(shù)。稱D ={x|Ax≤(=，≥)b，x≥0}為可行域，x∈D為該問題的可行解。若該問題可行域非空，且它有一個可行解x*∈D 使得cTx*≤cTx，x∈D，則稱x*是該線性規(guī)劃問題的最優(yōu)解。

任取A∈AI，b∈bI，c∈cI，得到問題Min{cTx|Ax≤(=，≥)b，x≥0}，稱它的一個最優(yōu)解為式(1)的一個最優(yōu)解，相應的最優(yōu)目標函數(shù)值為式(1)的一個最優(yōu)值。本文討論問題如下:

設向量y∈Rm，定義

由文獻[3]可得引理及定理1 如下:

x*是式(3)的一個最優(yōu)解，則有:

2 主要結(jié)果

計算最優(yōu)值區(qū)間是區(qū)間線性規(guī)劃的一個常見的問題，相關研究見文獻[5]、文獻[7]。而人們一般會對什么情況下取到最優(yōu)值感興趣，本文討論的就是式(2)最優(yōu)值的下界在哪些情況下可以取到的問題，也就是求出式(3)的一個最優(yōu)解所對應的目標函數(shù)系數(shù)及約束矩陣。本文在文獻[3]中對該問題的研究基礎上進行拓展，得到以下結(jié)論。

x*是式(6)的最優(yōu)解，且有式(4)成立，其中:

對于向量y∈Rm，由式(7)、(8)知，且Acx*-bc=Ty(AΔx*+bΔ)，則(Ac-TyAΔ)x*=bc+TybΔ，所以x*是(Ac-TyAΔ)x =bc+TybΔ，x≥0的一個可行解。而由|y|≤e可知所以可得不等式因此即x*是式(6)的最優(yōu)解，且式(4)成立，證畢。

由定理2可知，yi可以有無窮多種取值，隨之就有無窮多種約束矩陣，但不論Ty怎么變，也就是約束矩陣怎么變，x*都是它們所確定的線性規(guī)劃問題的最優(yōu)解，這也就是說在最優(yōu)解、最優(yōu)值不變的前提下，可以構(gòu)造出無窮多組約束條件。

3 算例

例 求區(qū)間線性規(guī)劃問題的最好最優(yōu)值，及最好最優(yōu)

解對應的目標函數(shù)系數(shù)和約束矩陣。

解 由文獻[6]提出的最好最優(yōu)解模型可得本問題的最好最優(yōu)解模型為:

解式(9)求得最好最優(yōu)解與最好最優(yōu)值分別為x*=(1，0，0)T，z*=-1。易知計算得由定理1 即原方法可得y1=1，y2=-1，從而進而可得最好最優(yōu)解x*對應的目標函數(shù)系數(shù)為c' =(-1，1，2)T，約束矩陣而用定理2 即本文所得的新方法可得到y(tǒng)1=α，α∈[-1，1]，y2=-1得到c″=c'，b″=b'，不同的是約束矩陣A″ =其中β∈[1，5]，γ∈[-1，3]。

4 結(jié)束語

本文構(gòu)造出了在帶有區(qū)間線性方程組的區(qū)間線性規(guī)劃問題中一個最優(yōu)解所對應的無數(shù)多組約束矩陣。通過實例演示，體現(xiàn)出了本文所得方法與原方法的不同及與之相比的優(yōu)勢所在。同時可以看出，本文所得方法不僅具有理論價值，也具有較強的實用價值。

[1]Oliver Chukwudi Ibe.Fundamentals of Applied Probability and Random Processes[M].London:Access Online via Elsevier，2005:59-76.

[2]謝季堅，劉承平.模糊數(shù)學方法及其應用[M].武漢:華中科技大學出版社，2000:1-72.

[3]Fiedler M，Nedoma J.Linear optimization problems with inexact date[M]，New York:Springer，2006:35-92.

[4]Hladik M.Linear Programming—New Frontiers in Theory and Applications[M].New York:Nova Science Publishers，2011:1-46.

[5]Hladík M.Optimal value range in interval linear programming[J].Fuzzy Optimization and Decision Making，2009，(8):283-294.

[6]李煒.線性優(yōu)化及其擴展[M].北京:國防工業(yè)出版社，2011:200-212.

[7]Chinneck John W，Ramadan K.Linear programming with interval coefficients[J].Journal of the Operational Research Society.2000，51(7):209-220.