数学季刊 >

2024 , Vol. 39 >Issue 4: 388 - 398

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2024.04.005

全局求解Minimax线性分式规划的分支定界算法

展开
  • School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, China
WANG Hui-man (1999-), female, native of Hebi, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application; SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; LIANG Yu-xin (2000-), female, native of Nanyang, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application.

收稿日期: 2024-02-27

  网络出版日期: 2024-12-30

基金资助

Supported by the National Natural Science Foundation of China (Grant Nos. 12071133 and 11871196).

收起

Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

Expand
  • School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, China
WANG Hui-man (1999-), female, native of Hebi, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application; SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; LIANG Yu-xin (2000-), female, native of Nanyang, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application.

Received date: 2024-02-27

  Online published: 2024-12-30

Supported by

Supported by the National Natural Science Foundation of China (Grant Nos. 12071133 and 11871196).

Fold

摘要

In this paper, we study the minimax linear fractional programming problem on a non-empty bounded set, called problem (MLFP), and we design a branch and bound algorithm to find a globally optimal solution of (MLFP). Firstly, we convert the problem (MLFP) to a problem (EP2) that is equivalent to it. Secondly, by applying the convex relaxation technique to problem (EP2), a convex quadratic relaxation problem (CQRP) is obtained. Then, the overall framework of the algorithm is given and its convergence is proved, the worst-case iteration number is also estimated. Finally, experimental data are
listed to illustrate the effectiveness of the algorithm.

关键词： Minimax linear fractional programming; Global optimal solution; Branch and bound

本文引用格式

王慧满, 申培萍, 梁雨欣 . 全局求解Minimax线性分式规划的分支定界算法[J]. 数学季刊, 2024 , 39(4) : 388 -398 . DOI: 10.13371/j.cnki.chin.q.j.m.2024.04.005

Abstract

In this paper, we study the minimax linear fractional programming problem on a non-empty bounded set, called problem (MLFP), and we design a branch and bound algorithm to find a globally optimal solution of (MLFP). Firstly, we convert the problem (MLFP) to a problem (EP2) that is equivalent to it. Secondly, by applying the convex relaxation technique to problem (EP2), a convex quadratic relaxation problem (CQRP) is obtained. Then, the overall framework of the algorithm is given and its convergence is proved, the worst-case iteration number is also estimated. Finally, experimental data are
listed to illustrate the effectiveness of the algorithm.

Key words： Minimax linear fractional programming; Global optimal solution; Branch and bound

Options
文章导航

/

〈 〉

版权所有 © 《数学季刊》编辑部
地址：河南省开封市明伦街85号河南大学数学季刊编辑部
电话：0371-23881698　E-mail: sxjk@henu.edu.cn　QQ: 2454327236
本系统由北京玛格泰克科技发展有限公司设计开发　技术支持：support@magtech.com.cn