Программа научного семинара «Mетоды анализа и выбора решений» (стр. 1 )

Правительство Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

"Национальный исследовательский университет
"Высшая школа экономики"

Нижегородский филиал

Факультет бизнес-информатики и прикладной математики

Программа научного семинара

«Mетоды анализа и выбора решений»

(«Analysis and decision making methods»)

на английском языке

для направления 010400.68 «Прикладная математика и информатика»

подготовки магистра

Автор программы: , д. т.н., профессор, [e-mail]

Одобрена на заседании кафедры ПМИ «___»____________ 2011 г.

Зав. кафедрой _____________

Рекомендована секцией УМС «Прикладная математика» «___»____________ 2011 г.

Председатель _____________

Утверждена УМС филиала «___»_____________2011 г.

Председатель _____________

Нижний Новгород, 2011

Научный семинар на английском языке «Mетоды анализа и выбора решений» «Analysis and decision making methods»

I. Пояснительная записка

1. Цель научного семинара

The objective of this семинар is to make students familiar with all steps of analysis and decision making methods by means of planning and processing research activities for challenging problems in operations research. The first set of problems is from single machine scheduling theory and the second set of problems is from location-allocation analysis applied to cluster analysis based on the p-median problem and its generalization.

2. Определение области и объекта исследований

It is important to differentiate between problem analysis and decision making taking into account that these concepts might be combined and integrated in a systematically designed sequence of steps induced by the nature of the problem under consideration. It means that these concepts cannot be completely separated from one another. Problem analysis must be done first, then the information gathered in that process may be used towards decision making. The following steps are involved not only in the whole problem analysis but also for each of sub-problems induced by decision making process.

Problem must be precisely identified and described;

Sub-problems are caused by some actions in decision making;

Causes to sub-problems can be deducted from relevant changes found in analyzing the whole problem;

Most likely cause to a (sub-) problem is the one that exactly explains all the facts.

The following steps are typical for decision making:

Objectives must first be established, classified and placed in order of importance;

Alternative actions must be developed;

The alternative must be evaluated against all the objectives;

The alternative that is able to achieve all the objectives is the tentative decision;

The tentative decision is evaluated for more possible consequences;

The decisive actions are taken, and additional actions are taken to prevent any adverse consequences from becoming problems and starting both systems (problem analysis and decision making) all over again.

In this seminar we are going to deal with decision theory in normative or prescriptive way, i. e., it is concerned with identifying the best decision to take, assuming an ideal decision maker who is fully informed, able to compute with perfect accuracy, and fully rational. The practical application of this prescriptive approach (how people actually make decisions) is called decision analysis, and aimed at finding tools, methodologies and software to help people make better decisions. The most systematic and comprehensive software tools developed in this way are called decision support systems.

An optimal decision (solution) is a decision such that no other available decision options will lead to a better outcome. It is an important concept in decision theory. In order to compare the different decision outcomes, one commonly assigns a relative utility to each of them. If there is uncertainty in what the outcome will be, the optimal decision maximizes the expected (average) utility.

Sometimes, the equivalent problem of minimizing loss is considered, particularly in financial situations, where the utility is defined as economic gain.

"Utility" is only an arbitrary term for quantifying the desirability of a particular decision outcome and not necessarily related to "usefulness." For example, it may well be the optimal decision for someone to buy a sports car rather than a station wagon, if the outcome in terms of another criterion (e. g., effect on personal image) is more desirable, even given the higher cost and lack of versatility of the sports car.

In case the decision outcome is subject to uncertainty, an optimal decision is maximizing the expected utility.

The problem of finding the optimal decision is a mathematical optimization problem. In practice, few people verify that their decisions are optimal, but instead use more intuitive approaches to make decisions that are "good enough." In mathematics, computer science and economics, optimization, or mathematical programming, refers to choosing the best element from some set of available alternatives.

In the simplest case, this means solving problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set (set of feasible solutions). This formulation, using a scalar, real-valued objective function, is probably the simplest example; the generalization of optimization theory and techniques to other formulations comprises a large area of applied mathematics. More generally, it means finding "best available" values of some objective function given a defined domain, including a variety of different types of objective functions and different types of domains.

To solve problems, researchers may use algorithms that terminate in a finite number of steps, or iterative methods that converge to a solution (on some specified class of problems), or heuristics that may provide approximate solutions to some problems (although their iterates need not converge).

In this seminar we study the so called combinatorial optimization problems. In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object (solution) from a finite set of objects (feasible solutions). In many such problems, exhaustive search is not possible. It operates on the domain of those optimization problems, in which the set of feasible solutions is discrete or can be reduced to discrete, and in which the goal is to find the best solution. Some common problems involving combinatorial optimization are the traveling salesman, simple plant location, assignment, and minimum spanning tree problems just to mentione a few.

Combinatorial optimization is a subset of optimization that is related to operations research, algorithm theory, and computational complexity theory. It has important applications in several fields, including artificial intelligence, machine learning, mathematics, and software engineering.

Some research literature considers discrete optimization to consist of integer programming together with combinatorial optimization (which in turn is composed of optimization problems dealing with graphs, matroids, and related structures) although all of these topics have closely intertwined research literature. It often involves determining the way to efficiently allocate resources used to find an optimal solution to mathematical problems.

Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items, therefore, in principle, any sort of search algorithm or heuristic can be used to solve them. However, generic search algorithms are not guaranteed to find an optimal solution, nor are they guaranteed to run quickly (in polynomial time). (Since some discrete optimization problems are NP-complete, such as the travelling salesman problem, this is expected unless P=NP.)

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i. e., as the input size goes to infinity. For example, if the time required by an algorithm on all inputs of size n is at most 5n3 + 3n, the asymptotic time complexity is O(n3).

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.

Since an algorithm may take a different amount of time even on inputs of the same size, the most commonly used measure of time complexity, the worst-case time complexity of an algorithm, denoted as T(n), is the maximum amount of time taken on any input of size n. Time complexities are classified by the nature of the function T(n). For instance, an algorithm with T(n) = O(n) is called a linear time algorithm, and an algorithm with T(n) = O(2n) is said to be an exponential time algorithm.

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A problem L is NP-complete if it has two properties:

It is in the set of NP (nondeterministic polynomial time) problems: Any given solution to L can be verified quickly (in polynomial time). It is also in the set of NP-hard problems: Any NP problem can be converted into L by a transformation of the inputs in polynomial time.

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard), if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial.

For example, the NP-hard knapsack problem can be solved by a dynamic programming algorithm requiring a number of steps polynomial in the size of the knapsack and the number of items (assuming that all data are scaled to be integers). This algorithm is exponential time since the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and Johnson (1979) observed, “A pseudo-polynomial-time algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.”

The related term strongly NP-complete (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in unary (that is, if the data are “small” relative to the overall input size).

3. Актуальность исследований в этом научном семинаре

In this seminar, Boolean Linear Programming (BLP) models will be studied for

three single machine scheduling problems with equal-length jobs and different release dates, and it is proven that they are polynomially solvable. The objective of the first problem, in which preemption is allowed, is to minimize the total weighted completion time. The objective of the other two problems is to minimize the total weighted tardiness. The second problem is preemptive, the third is not.

The single machine scheduling problems addressed in this seminar have an open computational complexity status. Based on the -classification scheme of Graham et al. (1979) Peter Brucker has updated the computational complexity status of all studied and well known scheduling problems at the website http://www. informatik. uni-osnabrueck. de/knust/class/ as follows.