Anewalgorithmforminimizingalinearobjectivefunctionsubjecttoasystemoffuzzyrelationequationswithmax-productcomposition资源-CSDN文库

58 浏览量 2021-02-21 05:49:18 上传评论收藏 178KB PDF 举报

资源推荐

资源详情

资源评论

Fuzzy Inf. Eng. (2010) 3: 249-267

DOI 10.1007/s12543-010-0048-3

ORIGINAL ARTICLE

A New Algorithm for Minimizing a Linear Objective

Function Subject to a System of Fuzzy Relation Equations

with Max-product Composition

Jian-xin Li · Gang Hu

Received: 23 April 2010/ Revised: 1 July 2010/

Accepted: 19 August 2010/

Research Society of China 2010

Abstract In this paper, we study a problem of minimizing a linear objective func-

tion subject to a system of fuzzy relation equations with max-product composition.

First, we present a standard form of an original model.Then by using the concept of

chained-set suite, we educe optimal solutions of the standard form, with which we

can get optimal solutions of the original model. On basis of these results, ﬁnally we

get an algorithm for the studied problem, which is simple and rapid for application.

Keywords Fuzzy optimization · Fuzzy relational equations · Max-product compo-

sition

1. Introduction

In this paper, we are interested in studying an optimization problem with a linear

objective function subject to a system of fuzzy relation equations with max-product

composition:

Minimize Z(x) = c

· x

+...+c

· x

(I)

s.t.

⎧

⎪

⎨

⎪

⎩

· x

∨ a

· x

∨···∨a

· x

= b

· x

∨ a

· x

∨···∨a

· x

= b

··· ··· ··· ··· ··· ··· ···

· x

∨ a

· x

∨···∨a

· x

= b

(II)

where, c

∈ R, a

, x

, b

∈ [0, 1](i = 1, 2,...,m,

j = 1, 2,...,n

), ‘·’ represents the

ordinary multiplication and a ∨ b = max{a, b}.

Jian-xin Li ()

Faculty of Applied Mathematics, Guangdong University of Technology, China

email: lijx002@163.com

Hu Gang

Faculty of Electromechanical Engineering, Guangdong University of Technology, China

250 Jian-xin Li · Gang Hu (2010)

As an application, Model (I)-(II) can be employed for the streaming media provider

seeking a minimum cost while fulﬁlling clients’ requirements.We give such an exam-

ple as follows.

A streaming media corporation services m clients, B

, B

,...,B

, through n re-

gional servers, A

, A

,...,A

. Each client has access to the n regional servers through

network connections (no limitation of bandwidth). Each client is guaranteed to have

at least one way of receiving the multimedia streaming data that meets its quality

level.

Suppose that the ith client B

has quality requirement b

. The jth server A

sends

streaming data with quality level x

to B

, and in the long-distance transmission, trans-

mission loss of the quality level x

will be produced, so, we let the transmission loss

coeﬃcient be a

(0 ≤ a

≤ 1), where i = 1, 2,...,m, j = 1, 2,...,n. Hence, B

actually receives streaming data quality level is a

· x

. So, the streaming media

corporation can successfully service client B

(i = 1, 2,...,m), through n regional

servers, A

, A

,...,A

⇔max



· x

j = 1, 2,...,n



= b

(i = 1, 2,...,m), i.e.,

· x

∨ a

· x

∨ ...∨ a

· x

∨ ...∨ a

· x

= b

. (II)

The max operations reﬂect that each client needs at least one regional server to

fulﬁll its quality requirement. In this application, all the quality levels x

, b

and

transmission loss coeﬃcient a

have been normalized to be within [0, 1]. Let c

the unit cost of x

( j = 1, 2,...,n). Then we get the objective function of the streaming

media corporation:

Minimize Z(x) = c

· x

+...+c

· x

+...+c

· x

. (I)

The objective function is the service cost per unit time, measured in dollars per

second. Combining (I) with (II), we get Model (I)-(II).

The notion of fuzzy relation equations with the max-min composition was ﬁrst

investigated by Sanchez [12]. Since then, the fuzzy relation equations have been

extended to the fuzzy relation equations with the t-norm composition, in which the

max-product composition is a member [2, 8, 11]. Several studies [3, 5, 9, 10, 13,

14, 16] have shown that the max-min operator may not always be the most desirable

fuzzy relational composition and in fact the max-product operator was superior in

these instances. Some outlines for selecting an appropriate operator of fuzzy relation

has been provided by Yager [15].

Bourke and Fisher [1] studied the fuzzy relation equations (II) and provided some

theoretical results for the solution set of (II). Their results showed that when the solu-

tion set of (II) is not empty, it can be completely determined by one unique maximum

solution and a ﬁnite number of minimal solutions.

Li [6] studied the solution procedure of (II) and gave an eﬃcient algorithm for

solving the System (II).

The optimization problem, Model (I)-(II), was ﬁrst explored by Loetamonphong

and Fang [7]. They captured some special characteristics of Model (I)-(II) and got

some procedures to reduce the original problem. The problem was transformed into

some 0-1 integer programs which are then solved by the branch-and-bound method.

Fuzzy Inf. Eng. (2010) 3: 249-267 251

Ghodousian and Khorram [4] studied Model (I)-(II). They split it into two sub-

problems: Model (I’)-(II) and Model (I”)-(II), here, (I’) is “MinZ(x) =



≥0

” and

(I”) is “MinZ(x) =



”. Then they search for optimal solutions of Model (I’)-

(II) and Model (I”)-(II), respectively. Finally, the optimal solutions of Model (I)-(II)

can be composed of these optimal solutions.

We note that the complicacy of searching for total optimal solutions of Model (I)-

(II) is concerned with the problem size, a simple, transparent and eﬃcient solution

procedure is always in demand.

In this paper, we try to seek a new algorithm solution to Model (I)-(II).

To decrease the complicacy, we should cut down the sizes of (I) and (II) as much

as possible, according to the general conditions of Model (I)-(II). So, in Section 2,

we work for simplifying Model (I)-(II) into its standard form Model (a)-(b).

To avoid a great deal of computations of searching for optimal solutions among

the minimal solutions of (II), in Section 3, we study characteristics of Model (a)-(b)

and set up some conceptions related to optimal solutions of Model (a)-(b). We prove

that the optimal solutions of Model (a)-(b) can be founded in the set of tight chained

solutions of (b).

To solve Model (I)-(II) eﬃciently, in Section 4, we give a new algorithm to Model

(I)-(II). The algorithm is operated on a table, in which there is just key data related

to a further simpliﬁed model of Model (a)-(b). Through comparing some relevant

data from the table, we can easily get all the optimal solutions of Model (a)-(b), with

which we can compose all the optimal solutions of Model (I)-(II).

Section 5 gives two examples in detail to display that our algorithm is eﬃcient and

reliable.

2. Simplify Model (I)-(II)

First, we start to simplify (II).

Let I = {1, 2,...,m} and J = {1, 2,...,n} be two index sets.

Model (I)-(II) can be expressed as

MinimizeZ(x) =



j∈J

(I)

s.t.

∨

j∈J

= b

, i ∈ I. (II)

where, a

, x

, b

∈ [0, 1], ∀i ∈ I, j ∈ J, c

∈ R.

For i ∈ I, denote D

= { j ∈ J

> 0}.

Lemma 1 [6] Let x = (x

, x

,...,x

) be a solution of (II). If in (II) there is b

= 0,

then

= 0, ∀ j ∈ D

. (1)

If there is b

= 0 in (II), then using Lemma 1, we can simplify (II) as follows:

1) Substitute the result (1) into (II), then the ith equation of (II) becomes a zero

row. In further solving process, the zero row will be useless, and we do not need to

consider it any more. So, we delete the ith equation of (II).

剩余18页未读，继续阅读

评论收藏

内容反馈

weixin_38557670

粉丝: 3
资源: 902

A new algorithm for minimizing a linear objective function subje...

最新资源

A new algorithm for minimizing a linear objective function subje...

Adaptive Fuzzy Filter Algorithm for Real-time Video Denoising

An Experimental Comparison of Min-Cut/Max-Flow Algorithms

Fuzzy Control Systems

A Robust Fuzzy Local Information C-Means Clustering Algorithm

1511.02306 Quantum algorithm for systems of linear equations.pdf

Fuzzy and Neuro-Fuzzy Systems in Medicine

A Fast Algorithm for Recovery of Jointly Sparse Vectors based on

A new algorithm for fine acquisition of GPS carrier frequency

Building a Fine-Grained Entity Typing System Overnight for a New X

Adaptive Fuzzy Sliding Mode Control Design-Lyapunov Approach

A Neural Algorithm of Artistic Style（一个艺术风格化的神经网络算法）

MaPle A Fast Algorithm for Maximal Pattern-based Clustering∗

Optimal Shape Design Of Aerodynamic Configurations-A Newton-Krylov Approach.pdf

A Self-Stabilizing Algorithm for Maximal Matching in Anonymous Networks

An Algorithm for License Plate Recognition Applied to ITS

Distributed Optimal Consensus Control for Multiagent Systems With Input Delay

A compact algorithm for rectification of stereo pairs

High Bandwidth Sensorless Algorithm for AC Machines Based on Square-wave Type

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

XCP协议的规范文档

GD32替换STM32注意事项.pdf

NPPJSONViewer.zip

蓝牙BLE协议中文版.pdf

CANoe通过CAPL脚本实现自动测试

电路分析基础第二版PDF电子书免费下载

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）