On the Use of Duality and Pricing Criteria in the Generalized-simplex Method

Some results connected to the generalized-simplex method and several of its main features are discussed. The duality information and pricing criteria of the classical simplex method will be incorporated in this new approach. An analogy between the generalized-simplex method and the hybrid techniques (that combine interior point methods with the classical simplex method) is presented.     

A new LP formulation of the admission control problem modelled as an MDP under average reward criterion

The admission control problem can be modelled as a Markov decision process (MDP) under the average cost criterion and formulated as a linear programming (LP) problem. The LP formulation is attractive in the present and future communication networks, which support an increasing number of classes of service, since it can be used to explicitly control class-level requirements, such as class blocking probabilities. On the other hand, the LP formulation suffers from scalability problems as the number C of classes increases. This article proposes a new LP formulation, which, even if it does not introduce any approximation, is much more scalable: the problem size reduction with respect to the standard LP formulation is O((C?+?1)²/2 ^C ). Theoretical and numerical simulation results prove the effectiveness of the proposed approach.     

An LP approach to full-order and reduced-order state estimations of positive Markov jump systems with delay

In this paper, the problems of full-order and reduced-order positive state estimations are developed for discrete-time positive Markov jump linear systems with delay. By establishing a positive time-delay system for 1-moment function of the state vector, delay-dependent necessary and sufficient exponential stability conditions are first derived based on a comparison technique for positive systems. Then, on the basis of the derived stability conditions, the problems of designing positive state observers in full-order and reduced-order for positive Markov jump systems with delay are addressed. The existence conditions of positive observers and the design schemes are formulated in terms of linear programming problems which can be effectively solved by various optimisation algorithms to obtain the observer parameters. Finally, three numerical examples with simulations are given to validate the analysis and design results.     

控制系统l~1优化设计最优解的存在性和次优解

本文初步研究了控制对象有z平面单位圆上零极点时l~2优化设计问题解的存在性,指出在此种情况下l~1优化问题的最优解不一定总是存在。提出了解存在性的判别定理。在最优解不存在时给出了次优解的求取方法。     

求广义指派决策问题最优解的有效算法

分析和研究一类广义指派决策问题,给出了该问题的线性规划模型,并把该问题转化为传统指派决策问题,使得该问题可以用著名的匈牙利算法求解最优解,从而为该问题找到一个理想,简便而有效的求解方法,给出了一个数值例子。     

Unidirectional loop network layout by a LP heuristic and design of telecommunications networks

In this paper, we present a new linear programming-based heuristic procedure for optimal design of the unidirectional loop network layout problem. The heuristic procedure employs a linear programming formulation and solves the problem using the flow matrix of the unidirectional loop problem. To find an optimal solution, one can either generate all possible solutions or use a branch-and-bound procedure. But, both above methods require very high computational time and computer memory for larger problems. The heuristic developed in this paper is quite fast and obtains near optimal solutions. The heuristic procedure was tested on 16 different problems selected from the literature. The results showed that in most cases optimal—and in a few cases near optimal—solutions were obtained with very little computational time. Several examples are discussed. We also demonstrate that the above problem formulation and approach can be used to solve a special class of telecommunication networks where a set of computers (or processors) are attached by unidirectional point-to-point links around a loop.     

A duality approach for solving bounded linear programming problems with fuzzy variables based on ranking functions and its application in bounded transportation problems

There are several methods, in the literature, for solving fuzzy variable linear programming problems (fuzzy linear programming in which the right-hand-side vectors and decision variables are represented by trapezoidal fuzzy numbers). In this paper, the shortcomings of some existing methods are pointed out and to overcome these shortcomings a new method based on the bounded dual simplex method is proposed to determine the fuzzy optimal solution of that kind of fuzzy variable linear programming problems in which some or all variables are restricted to lie within lower and upper bounds. To illustrate the proposed method, an application example is solved and the obtained results are given. The advantages of the proposed method over existing methods are discussed. Also, one application of this algorithm in solving bounded transportation problems with fuzzy supplies and demands is dealt with. The proposed method is easy to understand and to apply for determining the fuzzy optimal solution of bounded fuzzy variable linear programming problems occurring in real-life situations.     

Optimal inventory control in a multi-period newsvendor problem with non-stationary demand

The optimal control of inventory in supply chains plays a key role in the competiveness of a corporation. The inventory cost can account for half of company’s logistics cost. The classical inventory models, e.g., newsvendor and EOQ models, assume either a single or infinite planning periods. However, these models may not be applied to perishable products which usually have a certain shelf life. To optimize the total logistic cost for perishable products, this paper presents a multi-period newsvendor model, and the problem is formulated as a multi-stage stochastic programming model with integer recourse decisions. We extend the progressive hedging method to solve the model efficiently. A numerical example and its sensitivity analysis are demonstrated.     

The transportation algorithm as an aid to chromosome classification

An algorithm is presented which obtains a constrained maximum likelihood classification of homogeneously stained chromosomes. Significantly improved results over a both context-free and a plausible context-driven classification are obtained. Extension to banded chromosomes and abnormal cells are discussed.     

Weighted sum of maximum regrets in an interval MOLP problem

This paper presents a multiobjective linear programming problem with interval objective function coefficients. Considering the concept of maximum regret, the weighted sum problem of maximum regrets is introduced and its properties are investigated. It is proved that an optimal solution of the weighted sum problem of maximum regrets is at least possibly weakly efficient. Further, the circumstances under which the optimal solution is necessarily efficient (necessarily weakly efficient or possibly efficient) are discussed. Moreover, using a relaxation procedure, an algorithm is proposed, which for a given set of weights finds one feasible solution that minimizes the weighted sum of maximum regrets. A numerical example is provided to illustrate the proposed algorithm.     

Application of an explicit min-max MPC to a scaled laboratory process

Min-max model predictive control (MMMPC) requires the on-line solution of a min-max problem, which can be computationally demanding. The piecewise affine nature of MMMPC has been proved for linear systems with quadratic performance criterion. This paper shows how to move most computations off-line obtaining the explicit form of this control law by means of a heuristic algorithm. These results are illustrated with an application to a scaled laboratory process with dynamics fast enough to preclude the use of numerical solvers.     

Optimal sequencing of water supply options at the regional scale incorporating alternative water supply sources and multiple objectives

In recent years, the sequencing of water supply projects has become increasingly complex, as a result of the need to consider alternative water sources and additional objectives. In order to address this problem, two sequencing approaches are presented in this paper to assist in identifying the optimal sequence of water supply projects. The methods are applied to a case study based on the southern Adelaide water supply system, South Australia, over a 40-year planning horizon. Desalination plants, rainwater and stormwater sources are considered in addition to existing surface water sources. The objectives used include the present value of cost and greenhouse gas (GHG) emissions and optimal sequences are obtained for a range of demand and discount rate scenarios. The results demonstrate that there are noticeable tradeoffs between costs and GHG emissions when favouring different objectives, but that the impacts of uncertain demands and discount rates are potentially more significant.     

Optimal sizing,scheduling and shift policy of the grinding section of a ceramic tile plant

This paper addresses the optimal design of the grinding section of a ceramic tile plant operating in a cyclic mode with the units (mills) following a batch sequence. The optimal design problem of this single product plant is formulated with a fixed time horizon of one week, corresponding to one cycle of production, and using a discrete-time resource task network (RTN) process representation. The size of the individual units is restricted to discrete values, and the plant operates with a set of limited resources (workforce and equipment). The goal is to determine the optimal number and size of the mills to install in the grinding section, the corresponding production schedule, and shift policy. This problem involves labor/semi-labor intensive (LI/SLI) units with a depreciation cost of the same order as that of the operation cost. The optimal design of the grinding section comprises the trade-off between these two costs. The resulting optimization formulation is of the form of a mixed integer linear programming (MILP) problem, solved using a branch and bound solver (CPLEX 9.0.2). The optimal solution is analyzed for various ceramic tile productions and different shift policies.     

Optimal design of linear control systems by an interactive optimization method

When designing linear control systems, one of the most difficult problems is that the designer almost has no theoretical basis for the determination of proper parameters in order to obtain a system with desired specifications. Poles and directions of eigenvectors in the pole assignment method or weighting matrices of the quadratic criterion function in the optimal regulator method are such parameters. The designer has to determine them by trial-and-error using computer simulation. The purpose of this paper is to propose an approach to helping determine proper parameters in linear control system design by the state space methods. In the case where the desired specifications are not given explicitly, the approach applies an interactive optimization method called the Interactive Simplex method to search the most suitable parameters directly in the parameter space. But, if the specifications are given explicitly, the design problem can be formulated as a multiobjective optimization problem. In this case, weights which indicate relative importance of different specifications are introduced and the Interactive Simplex method is applied in the weight space to indirectly find the most appropriate parameters. The approach is implemented as part of a CAD system. The designer has only to make pairwise comparisons of response curves which are shown on a graphics display terminal in order to obtain the most preferred control system. Two illustrative examples are demonstrated to indicate the efficiency of the approach.     

Sequence of linear programming for transmission of fine-scalable coded content in bandwidth-limited environments

In this paper, we propose an optimal peer assignment algorithm on peer-to-peer networks. This algorithm is designed to maximize the quality of transmitting fine-scalable coded content by exploiting the embedding property of scalable coding. To be more realistic, we assume that the requesting peer has a delay constraint to display the content within a certain delay bound, and it also has limited incoming bandwidth. We first use a simple example to illustrate the peer assignment problem, and then formulate this problem as a linear programming problem, followed by a nonlinear programming problem. To efficiently solve the second nonlinear problem, we transform it into a sequence of linear programming problems. Finally, we apply our proposed algorithm to both image and video transmissions in bandwidth-limited environments. Extensive experiments have been carried out to evaluate the complexity and performance of our approach by comparing it with both nonlinear formulation and two heuristic schemes. The results have verified the superior performance of our proposed algorithm.     

Higher Order Real-Time Approximations in Optimal Control of Multibody-Systems for Industrial Robots

The multibody system of an industrial robot leads to a mathematical model described by ordinary differential equations. Control functions have to be determined to calculate robot trajectories which are optimal due to a given performance index subject to additional constraints. In order to solve such optimal control problems, computationally expensive methods exist. These methods have no real-time capability, since perturbations during the motion of the robot require a recalculation of the optimal trajectory within a time frame much smaller than the operating-time of the robot. Hence, a robust numerical method based on the parametric sensitivity analysis of nonlinear optimization problems is suggested. Optimal control approximations of perturbed optimal solutions can be obtained in real-time by evaluating a first order Taylor expansion of the perturbed solution. Successive improvements to the constraints in the direction of the optimal perturbed solution lead to an admissible solution with a higher order approximation of the objective. The proposed numerical method is illustrated by the optimal control of an industrial robot with three degrees of freedom subject to deviations in the payload and initial values.     

Stability radius of an efficient solution of a vector problem of integer linear programming in the Gölder metric

A vector (multicriterion) problem of integer linear programming is considered on a finite set of feasible solutions. A metric l_p, 1 ≤ p ≤ ∞, is defined on the parameter space of the problem. A formula of the maximum permissible level of perturbations is obtained for the parameters that preserve the efficiency (Pareto optimality) of a given solution. Necessary and sufficient conditions of two types of stability of the problem are obtained as corollaries. This work has been carried out with financial support from the Belgosuniversity within the framework of the Intercollegiate Program “Fundamental and Applied Investigations” (project No. 492/28). __________ Translated from Kibernetika I Sistemnyi Analiz, No. 4, pp. 175–181, July–August 2006.     

一类非凸优化问题的遗传算法

线性二层规划是一类特殊的非凸优化问题,为了有效求解该问题,提出了一种基于单纯形方法的遗传算法。首先基于下层约束给出了一种新的编码方法;其次利用单纯形表的信息得到了下层问题的解函数,并结合最优性条件给出了适应度函数;最后基于个体编码的特点,设计了新的遗传算子。数值结果表明,所提出的算法是可行有效的。     

一类混杂系统建模和优化控制的研究

为解决混杂系统优化控制的计算复杂性问题,针对结合逻辑规则的工业过程混杂模型,采用结合约束程序的混合整数非线性规划算法,求解这种混杂模型的优化控制。计算实例表明,通过混杂建模方法,可以充分利用工业对象的机理模型以及操作工经验或专家经验,建立系统的更精确模型;结合约束程序混合整数非线性规划算法可以较迅速地求解混杂模型优化控制问题,从而使该方法可以用于工业过程实时控制中。     

高职院校网络编程课程教学存在的问题及其对策

网络编程课程实用性、技术性、可操作性和动态变化性强,对教师的要求非常高,加之一些条件的不成熟,导致高职院校网络编程课程教学运行存在一些问题。为此,高职教师层面应该树立现代化的教学理念,解析和重组网络编程课程的教学内容,开展学生自主学习的教学模式,提高自身教学素质和能力;学校层面应从网络编程课程教学所需要的设施设备和场地、资金和其他教学活动上提供支持;学生层面应提高自身自主学习能力,开展移动式学习模式。