凸优化内点法在排队问题中的应用
发布时间：2018-11-04 14:59
【摘要】：排队论或称队论,是研究各种排队性质的理论,是为了研究如何设计、使用一个服务系统,且使这个服务系统既能满足实际问题解决的需要,同时使整个过程花费最少的一门学科。如果用数学思想来解释,可以把它归结为运筹学。排队问题,现实生活中无处不在。而排队问题的解决的关键是如何优化排队系统中主要性能指标,如负荷配置、顾客平均等待队长、顾客平均等待时间、缓冲区占有量及某种稳定状态出现的概率等。然而诸如这些优化问题的目标函数均是非线性的,通常的优化算法难以得到满意的结果。本文主要是研究如何将排队问题中某些性能指标的非线性优化问题转化成运筹学中的凸优化问题,并用目前凸优化理论中较完备且成熟的内点法,作为计算工具。全文主要对排队问题中顾客平均等待队长这一性能指标的优化问题进行研究分析,首先将原问题近似等价为几何规划问题,然后通过变量替换,转换成凸优化问题,最后利用凸优化内点法进行具体的算法设计和收敛性分析。结果证明,将凸优化内点法引入排队系统这一性能指标的优化问题中,能够充分展示了内点算法的优点,整个算法迭代次数少,收敛速度快,收敛结果满足排队系统实际需求,且在具体提高整个排队系统服务效率和服务质量颇有成效。
[Abstract]:Queuing theory, or queue theory, is a theory that studies the nature of queuing. It is to study how to design and use a service system, and to make the service system meet the needs of practical problem solving. A discipline that simultaneously minimizes the cost of the whole process. If it is explained by mathematical thought, it can be reduced to operational research. The problem of queuing is ubiquitous in real life. The key to solve the queuing problem is how to optimize the main performance indicators in the queuing system, such as load allocation, customer average waiting length, customer average waiting time, buffer possession and probability of occurrence of some stable state. However, the objective functions of these optimization problems are nonlinear, and the usual optimization algorithms are difficult to obtain satisfactory results. In this paper, we mainly study how to transform the nonlinear optimization problem of some performance indexes in queueing problem into convex optimization problem in operational research, and use the more complete and mature interior point method in convex optimization theory as a calculation tool. In this paper, the optimization problem of customer average waiting length in queuing problem is studied and analyzed. Firstly, the original problem is equivalent to geometric programming problem, and then the optimization problem is transformed into convex optimization problem by variable substitution. Finally, the convex optimization interior point method is used to design the algorithm and analyze the convergence. The results show that the convex optimization interior point method can fully demonstrate the advantages of the interior point algorithm when it is introduced into the optimization problem of queueing system. The whole algorithm has fewer iterations, faster convergence speed, and the convergence results can meet the actual needs of queueing system. Moreover, it is effective to improve the service efficiency and service quality of the whole queuing system.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O226
，
本文编号：2310181
[Abstract]:Queuing theory, or queue theory, is a theory that studies the nature of queuing. It is to study how to design and use a service system, and to make the service system meet the needs of practical problem solving. A discipline that simultaneously minimizes the cost of the whole process. If it is explained by mathematical thought, it can be reduced to operational research. The problem of queuing is ubiquitous in real life. The key to solve the queuing problem is how to optimize the main performance indicators in the queuing system, such as load allocation, customer average waiting length, customer average waiting time, buffer possession and probability of occurrence of some stable state. However, the objective functions of these optimization problems are nonlinear, and the usual optimization algorithms are difficult to obtain satisfactory results. In this paper, we mainly study how to transform the nonlinear optimization problem of some performance indexes in queueing problem into convex optimization problem in operational research, and use the more complete and mature interior point method in convex optimization theory as a calculation tool. In this paper, the optimization problem of customer average waiting length in queuing problem is studied and analyzed. Firstly, the original problem is equivalent to geometric programming problem, and then the optimization problem is transformed into convex optimization problem by variable substitution. Finally, the convex optimization interior point method is used to design the algorithm and analyze the convergence. The results show that the convex optimization interior point method can fully demonstrate the advantages of the interior point algorithm when it is introduced into the optimization problem of queueing system. The whole algorithm has fewer iterations, faster convergence speed, and the convergence results can meet the actual needs of queueing system. Moreover, it is effective to improve the service efficiency and service quality of the whole queuing system.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O226
，
本文编号：2310181
本文链接：https://www.wllwen.com/kejilunwen/yysx/2310181.html
