На головну

# Building an economic model c using the simplex method - Economic-mathematical modeling

Minesterstvo Education of Ukraine

Dneprpetrovsky State University

Coursework

Subject: Construction of an economic model using the simplex method.

Work performed:

student group RS-97-1

Barshcheuski Egor

Check:

Associate Professor, Department ASIP

Salikov VA

Dnepropetrovsk 1999

TABLE OF CONTENTS

Abstract ___ 3

Introduction .___ 4

1. a systematic manner ___ 5

1.1.Osnovnye concepts and definitions of the system podhoda__ 5

1.1.1. The concept of system and environment ___ 7

1.1.2. The concept of a problem situation ___ 11

1.1.3. Understand the purpose of ___ 14

1.1.4. The concept of system functions ___ 16

1.1.5. The structure of the system ___ 17

1.1.6. External conditions of ___ 20

1.1.7. The main stages of system activity ___ 21

1.2. Model systems ___ 22

1.2.1. Definition and classification of models of systems ___ 22

1.2.2. Levels of system models * ___ 25

The practical part ___ 28

Verbal description ___ 28

Mathematical description .___ 29

Restrictions ___ 30

Variables ___ 31

The objective function ___ 32

Simplex method .___ 33

Presentation of the solution space of the standard tasks

linear programming .___ 34

Computational procedures simplex method .___ 37

Optimal solution ___ 42

Status of resources ___ 43

The value of the resource ___ 45

The maximum change in resource stocks ___ 47

The maximum change in the coefficients of specific ___ 50

profit (cost) ___ 50

Conclusion ___ 52

References: ___ 53 Abstract

In the course of this paper discusses the basic principles of the system, as well as the practical application of the knowledge gained by the example of distribution of funds of the company.

Introduction.

Today in for every citizen of Ukraine is not a secret that the economy of his country almost moved to a market economy and is entirely under the laws of the market. Each company is responsible for the work itself and itself decides on further development. Modern conditions of market economy impose on forecasting methods are very demanding, due to the increasing importance of a correct prediction for the future of the company, and the economy as a whole.

It is forecasting economic performance of regions or even countries, in my opinion you need to pay close attention at the moment, because of the veil of momentary own problems all somehow forgot that the country's economy, too, must be controlled, and therefore forecasting of its development should be put on a firm scientific basis.

The purpose of the course work was to study the practical experience of the use of economic and statistical forecasting methods.

Modeling research was used in ancient times, and gradually captured all the new scientific knowledge: technical design, construction and architecture, astronomy, physics, chemistry, biology, and finally, the social sciences. Great success and recognition in almost all branches of modern science has brought to the method of modeling the twentieth century. However, the methodology of modeling for a long time developed independently by individual sciences. There was no unified system of concepts, uniform terminology. Only gradually became aware of the role of modeling as a universal method of scientific knowledge

The term "model" is widely used in various fields of human activity and has many meanings. Consider only the "models" that are the tools of learning.

Model - is a material or mentally represent objects, which in the research process replaces the original object so that its direct study provides new knowledge about the object-original.

By modeling refers to the process of construction, study and application of models. It is closely related with such categories as abstraction, analogy, hypothesis, and others. The modeling process necessarily involves and abstraction, and reasoning by analogy, and the construction of scientific hypotheses.

The main feature of the simulation is that it is a method of knowledge mediated via proxy objects. The model serves as a kind of tool of knowledge, which the researcher puts between himself and the object with which to study the interests of its object. This feature modeling method determines the specific form of use of abstractions, analogies, hypotheses, methods and other categories of knowledge.

The need to use the modeling method is determined by the fact that many objects (or problems relating to these objects) directly investigate or impossible, or it requires a lot of research time and money.

Simulation - a cyclical process. This means that for the first four-cycle may be followed by a second, third, etc. In this case, the knowledge about the object and expand tochnyayutsya, and the original model is gradually improving. Defects discovered after the first cycle modeling buslovlennye little knowledge of the object and errors in the construction of the model, can be corrected in subsequent cycles. In the modeling methodology, so the possibilities are self-development.

1. a systematic manner 1.1.Osnovnye concepts and definitions of the system approach

Around us productive, social, organizational and natural sites have many different properties: they are quite complex, distributed in space, are dynamic in time, their behavior is described by both deterministic and stochastic laws, etc.

In the management of such systems involve a large number of people, huge natural, material and energy resources. In this respect, the approach to the control objects as complex systems expresses one of the main features of the current stage of development of society.

The ability to recognize the system decompose it into elementary components, determine control laws of each subsystem and re-synthesize the system requires the development of a number of special formal models, procedures, algorithms. Another philosopher of ancient Rome Kviantilian argued that any arbitrarily complex situation can fully describe the structure and guided by the following seven questions  (Fig. 1.1).

Fig. 1.1. The main factors of the system

Science, in which studies have been developed to address the problems expressed above, called "systems theory" - "systems approach" - "systems analysis". This theory originated in the 30-ies and 50-ies was formed as an independent on-uchnoe direction. Her origins were biologists Bertalanffy, P, Gerard, an expert on mathematical problems in biology and psychology - A.Rapoport economist - K. Boulding .

In the future, these studies were continued in numerous works of foreign and domestic scientists .: Mesarochicha M., S. Optnera, S. Yang, J. Takaharu, R. Ackoff, AA Bogdanova, VN Sadowski, AI Uyomov, Yu.I.Chernyaka, AA Denisov and dr.1.1.1. The concept of the system and environment

The concept of the system is refined and developed over the development of the system analysis. Thus, the founder of the theory of systems of Ludwig von Bertalanffy defined as a complex system of interacting elements that are in certain respects with each other and with the environment.

Thus the starting point in determining the system is its contrasting environments, ie Wednesday - is all that is not included in the system, and the system - a finite set of objects, somehow isolated from the environment. Between the environment and the system there is an infinite number of interconnections in which the interaction process is implemented, most media and systems. Allocation system of protection and the definition of the boundaries of their interaction is one of the priorities of the system analysis. On the correct definition of the boundaries depend not only on the functions performed, the effectiveness and quality of the system, but often its very vital functions. On the other side, the dialectical basis of the system is the principle of systematic research, the essence of which is to ensure that the system as whole has properties that are not inherent in its constituent elements. In this case, the determination of the system must be based on two fundamental concepts:

is a system as a set of interacting elements; -system as complete medium with a new backbone-forming properties.

Based on the above list the following distinctive quality of the system:

-system is something a whole;

-system is a set of elements, attributes and relations;

-system is an organized set of elements;

-system is a dynamic set of elements.

Then the definition of a system can be constructed as follows: the system has a finite set of functional elements and relations between them, isolated from the medium in accordance with the defined-term aim, within a certain time interval.

In this case, a simple element is commonly understood as an indivisible part of the system - subsystem. In this case, the answer to the question, which is a part can not be unique and depends on the purpose of considering the object as a system.

Objectively, from the viewpoint of the environment, any system exists as a source address their needs. From this it follows that the simplest model of the interaction between the system and the environment as follows (Figure 1.2).

Figure 1.2. Model of the interaction of the system and environment

The input to the system from among the applicants:

set of objectives and constraints - Z = {Zk} is the set of resources - X = {Xj}

Output of the system is the set of final products, goods and services focused on the needs of the environment - Y = {Yi}.

Wherein the plurality of end products and resources can be classified into the following groups: physical, informational, financial, labor, energy.

In a number of cases in the classifier system outputs in addition to useful end-products is necessary to allocate the waste, ie, final products, have a negative impact on the environment.

Fig. 1.3 presents a generalized model of the interaction of the enterprise "as a system" with elements of its environment.

Fig. 1.3. Model of the interaction of the enterprise with elements of the environment

As an example, consider a fragment of the model of interaction of the institution with the elements of the environment.

As the final product of the institution can rassmat-regarded the following sets:

Y1- engineering staff;

Y11- engineering staff prepared according to standard programs;

Y12- engineering staff commissioned by the governing bodies;

Y13- engineering staff commissioned by the Institute of financial institutes;

Y14- engineering staff, commissioned by a particular company, etc .;

Y2- information products of high school;

Y21- teaching literature;

Y22- scientific and technical literature;

Y23- report information on the activities of the institution;

Y3- scientific and technical development of the university;

Y4- of highly qualified personnel.

As input resources of the institution to allocate:

X1 - financial resources for the organization of educational process;

X11 - the federal budget;

X12 - the local budget;

X13 - budget funds;

X14 - charities;

X15 - bank loans;

X2 - the financial resources for the organization of research activity;

X3 - financial resources for the organization of the administrative host-nomic activity;

X4 - they enter the university;

X41 - based on the state budget financing;

X42 - on the orders of the authorities and management;

X43 - on the orders of financial institutions;

X44 - on the orders of specific industrial enterprises.

As the set objectives and constraints that determine the activities of the university, you will find:

-by learning activities -

Z11 - GOS requirements for training in specific spe-tiality;

Z12 - requirements governing bodies for training specialists-sheets;

Z13 - requirements of financial institutions for training of specialists;

-by research activities -

Z21 - requirements of federal agencies to perform quality gosbyud-budgetary issues;

Z22 - customer requirements for quality performance of contractual issues.

1.1.2. The concept of a problem situation

As was shown in the previous section, the interaction between the system and the environment built as follows: Wednesday delivers system resources, sets goals, constraints, and gets out of the system and uses its end products. Characteristically, the manual system in principle can not be created in the medium (otherwise, there is no need to allocate from the system environment).

The resulting degree of dissatisfaction brewing or environmental elements of the final products or low efficiency of interaction of the elements of the environment to generate a new system in adoption of a systems approach - "problematic situation" - emerged or maturing degree of dissatisfaction with the relationship between the system and the environment. In this case it is obvious that a list of problematic situations can be determined by analyzing the correlation of the sets of elements:

Y = {Yip}; X = {Xjp}; Z = {Zkp}

In conducting this research phase system is recommended primarily to articulate the essence of the problem and describe a situation in which it takes place . The content of activities includes the following steps:

-establishing content problems, ie clarification of whether there is actually a problem or it is far-fetched;

Define the novelty of the problem situation;

-establishing causes of the problem situation;

Define the degree of the relationship of problem situations;

Define the completeness and accuracy of the information about the problem situation; Define the possibility of solving the problem.

Determination of the existence of the problem involves the verification of the truth or falsity formulation of the problem and its accessories. Checking the validity of the existence of the problem should be carried out primarily by the presence in the set of economic and social losses, and its significance - the criterion of economic or social effects produced in the system after the elimination of the problem situation. Evaluation equally problematic must be done on a comparison of the actual (currently or in the future) values ??with their planned goals or normative values.

Definition of novelty of the problem situation must be to identify and possible precedents or analogies. Past experience or regulatory guidelines can greatly facilitate the work of experts on the development and decision-making to eliminate the problem.

Attribution (as in the system and in the environment) of the problem allows a deeper understanding of laws governing the functioning of the control object, to reveal the most important factors that led to the problem situation.

In the analysis of the problem situation, you must install the possible relationship of the problem to other problems. Thus it is necessary to classify these problems into major and minor, public and private, urgent and non-urgent. Analysis of the relationship problems will clearly and deeply identify causal relationships and contribute to the development of integrated solutions. Complexity implies in reaching a decision to issue recommendations for change not only the system under study, but also the environment.

Great importance in the analysis is to determine the degree of completeness and accuracy of the information about the problem situation. In the case of complete information is not difficult to formulate the essence of the problem and the complex is characterized by its terms. If there is uncertainty of information, it is necessary to consider two alternatives: to work to obtain the missing information; opt out of receiving additional-term information and make a decision in terms of the uncertainty. The choice of an alternative in each case must be carried out on the basis of the scheme "costs - effect."

An important part of the analysis of the problem situation is the certain degree of solvability of the problem. In this case, even in the preliminary stage must be at least a rough estimate of the possibility of solving the problem, because it makes no sense to engage pois-com solutions to intractable at this time problems.

The complexity and diversity of systems and problem situations require the development of formal procedures for organizing such activities. In  the following list of techniques to organize the analysis and evaluation of problematic situations:

-anketnoe examination;

-prognozirovanie based on time series;

derivative of forecasting (use of already obtained forecasts to assess any situation, for example, a company producing spare parts for cars can use the forecasts on the volume of pro-car sales);

-modelirovanie on the basis of factor analysis and regression analysis (mouth-ment of causal relationships between certain factors and variables that need to be determined);

-method brainstorming;

Delphi-method;

-method development scenarios.

Continuing with the example of the analysis of the interaction of the institution with the elements of the environment, we distinguish the following list of problematic situations:

-on the relationship X14 - low quality of training to the requirements of modern production;

-on the relationship X11 - low level of funding of the educational process by the state;

-on the relationship X13 - low volumes and rates to attract extra-budgetary resources in the organization of the target and the commercial preparation of students;

-on the relationship X41 - low competition for admission to the university for a number of specialties, etc.

1.1.3. Understand the purpose of the system

Understand the purpose and the related concepts of focus, commitment, expediency difficult to formulate due to their single-digit interpretation. Thus, in the TSB objective is defined as "pre conceivable result of creative activity of man." In addition, in the literature there are a number of alternative options to define the purpose of the system:

- "Desired state of the outputs of the system";

- "A certain external or installed by the system state of its outputs"; - "Ideal image of what a person or group of people wants to achieve"; - "Anticipation in the minds of the result, towards which the action";

- "Required external environment performance of the system for data output on the set of the final products."

In this case, the definition of objectives will be based on the following assumptions. Since the problem situation is identified with the analysis of the relationship with the elements of the external environment, the objectives of the system should be expressed through the image of the perfect information of this relationship. Thus, the main difficulty of forming the purposes connected with the fact that the goals are like the antithesis of problems. Form-lating the problems we're talking explicitly that we do not like. Speaking about the goals we are trying to articulate what we want. In formulating the goals should not substitute its means. Suppose you want to "improve the information service of the firm" - the acquisition of the necessary number of PC is just one of the possible actions in this on-board.

Further presentation of the material will be carried out on the basis of the following classification purposes (Fig. 1.4).

Fig. 1.4. Target classification

The ultimate goals characterize a well-defined result, koto-ing can be produced in a given time and space. Endless goal is usually determined by the total activity. The choice of class objectives depends on the nature of the problem being solved. It is clear that in determining the goals necessary to proceed from the interests of public-owls system. In this case, the wording of the objectives can be expressed as in-QUALITY-governmental and quantify, to be clear and compact, wear imperious character.

With respect to the objectives of the system can be in two modes of functioning and development. In the first case it is considered that the system meets the needs of the environment and the process of its transition and its individual elements from state to state occurs at a constant predetermined goals. In the second case it is considered that the system at some point ceases to satisfy the needs of the environment, and requires previous adjustment of targets.

Given that almost all systems are a class of multi-product (multi-purpose) systems, should be considered simple (private) system objectives and complex (complex) target. For example, for the achievements of-business success can restrict the objectives in the following areas of activity :

Effectively;

-Performance;

-organization functioning;

-innovatsii;

-materialnye resources;

-financial resources;

-social responsibility.

This example shows that if you are wondering if the business organization is only one purpose, for example, in the area of ??efficiency - "maximum profit", your activity is parasitic. Ultimately, every business should have a definite social purpose, be useful to society in terms of production of any of the final products and services.

1.1.4. The concept of system functions

The presence of a problem situation and objective goals of the system as a prototype of the future state, requires the implementation of specific actions for achieving targets results.

In this case, we define the function of the system as a way to (set of actions) to achieve system goals.

For the definition of the functions can be successfully used already mentioned:

-method brainstorming;

Delphi-method;

-method development scenarios.

In some cases, to generate a set of functions is recommended to involve external experts, who had no previous system, not knowing its internal limitations and contradictions.

For example, if the objective of "To ensure the quality of training to the requirements of a particular company" can be formulated as the following functions (activities):

1.zaklyuchenie treaties target training;

2.perevod students for individual learning;

3. Preparation of a cycle of specialized training to the requirements of the enterprise; 4. Development of the material base of the educational process, etc.

1.1.5. System Structure

The above steps of creating a system under the problematic situation (formation of goals and ways to achieve them, ie functions) objectively require the next logical step - to identify such elements and the relationships between them (the internal structure of the system) that implement purposeful functioning of the system. Elements of any content required to implement the function is said to be parts or com-ponents of the system. The combination of parts (components) of its elemental form (component) composition. In this case, the elements of which are considered as indivisible, will be called elementary. Part of the system consisting of more than one element forms a subsystem. However, each of the subsystems that implement a particular function, can in turn be regarded as a new system, etc. Ordered set of relations between the parts, significant in relation to the objectives necessary to implement the functions, forms the structure of the system.

The concept of structure is derived from the Latin word structure, meaning the structure, layout, order, and the most accurate definition of the structure is as follows: "Under the structure refers to the set of elements of the system and the relationships between them." In this case, the term "communication" can characterize both the structure (static) and functioning (dynamics) of the system. In addition, in the analysis are two defining concepts of structure: material structure and formal structure.

In general, under the formal structure refers to the totality-of functional elements and their relationships are necessary and sufficient to achieve the system goals. The definition implies that the formal structure describes something in common, inherent in the system of the same type.

In turn, the material structure is a carrier of specific types and properties of elements and their relationships.

These considerations allow us to draw two conclusions about the nature of formal structures: fixed targets usually corresponds to one and only one formal structure; a formal structure can match a lot of material structures.

When conducting system analysis at the stage of studying formal and material structures of the system analysts usually solve the following problems:

-Meet whether the current structure of the new objectives and functions of the system; -Requires whether reorganization of the existing structure or the need to design an entirely new structure;

-How can distribute (redistribute) old and new system functions on the elements of the structure.

All these tasks are largely dependent on the types of structures in the system. In this context, a brief look at some typical structures of systems used to describe the organizational and economic, manufacture-governmental and technical objects (Fig. 1.5).

Fig. 1.5. Types (species) structures

Linear structure (Figure 1.5) is characterized in that each vertex is associated with two adjacent. When failure of at least one element (bond) the structure collapses.

The ring structure (Figure 1.5 b) differs reserve, any two elements have two lines of communication. This increases the speed of communication, makes the structure more tenacious.

The honeycomb structure (Figure 1.5, c) characterized by the presence of reserve connections which increases the reliability (persistence) of functioning structure, but leads to an increase in cost.

Multiply structure (Figure 1.5, g) is a complete graph. Reliability of the maximum efficiency ing high-functioning, due to the presence of shortest paths, the cost - the maximum. A special case of a multiply connected structure is the "wheel" - (Figure 1.5, etc.).

The hierarchical structure (Figure 1.5, e) is the most widely spread in the design of control systems, the higher level of the hierarchy the fewer connections have its elements. All elements except the upper and lower levels have both command and subordinate management functions. Each level of the system, characterized terized by hierarchy level, which is defined as the ratio of the number of outgoing connections to the number of incoming calls.

Stellar structure (Figure 1.5, g) has a central node, which acts as the center, all the other elements of the system are subordinate.

Graph structure (Figure 1.5, z) is invariant with respect to the hierarchical and is commonly used in describing the production and technological systems.

In general, the structure of the material carrier is targeted activities to eliminate the problem situation and of its effectiveness depends largely on the end result of this activity. In this case, the choice of a particular variant structures, it is advisable to use non-which performance indicators, such as efficiency, centralization, peripheral, vitality and volume.

Efficiency is estimated response time of the system to the impact of the external environment, or its rate of change, and depends mainly on the general scheme of combining the elements and their location.

Centralization determines the possibility of the one of the elements of the system management functions. Centralization numerically determined by the average number of connections of the central (governing) element with all the others.

Peripherality characterizes the spatial properties of the structures. Peripherality index numerically characterized the center of gravity structure, in this case as a single assessment measures of connectivity supports "relative weight" structure element.

Survivability of the system determines the ability to maintain the values ??of the indicators of the system is damaged. This figure can be characterized by the relative number of elements (or ties), the destruction of which other parameters are within the permissible limits.

The volume is a quantitative characteristic of the structure and is usually determined by the total number of elements or medium density.

The problem of optimization of the structure in order to obtain maximum efficiency of the system is relevant and requires a certain mathematical apparatus for its decision. As such a device commonly used graph theory and integer programming.

1.1.6. Environmental conditions System

Application of the above stages of the formation of a problematic situation (definition of objectives, functions and structure of the system) for a perfectly-regulatory system that can serve as a model of real systems that operate within the constraints imposed by the environment. In case of noncompliance of the existing structure of the normative set of functions, leading to the goals and the impossibility of its reorganization by internal resources of the system should be considered raising options in the elements of the environment. In most cases, the elements of the environment, actively affecting the system are considered:

-External resources: financial, material, labor;

-BOUNDED: acts, legal documents, etc.

Obviously, those and other effects may influence both the structure and the function of the system.

Sometimes, after the definition of the necessary resources becomes obvious unreality set target results and requires correction original goals or set of functions to implement them.

However, the stage production of "best goals" is not a loss, as the strategy "is the best that can be done" may be replaced by a strategy "is the best that can be done" In case of external resources enough, then we can talk about the elimination of the analyzed problem situation. Otherwise, we should go about rethinking the problem and formulate a new system goals.

Example. As the resources of the environment in the implementation of the "training to the requirements of a particular company" can be considered:

-financial resources available from the company in the form of monetary compensation for additional training;

-materialnye resources presented in the form of the original location-ment, appliances and devices that the student should learn and be able to use; -postanovleniya Ministry of Education of the Russian Federation governing the rights and obligations of the university, the company and the student.

1.1.7. The main stages of system activity

Using the above concepts and definitions in the system activity allows you to answer a set of interrelated questions: "what?", "How?", "Who?" and "what?". In other words, should answer the questions: the presence or absence of a problem situation and determine the main directions (objectives) of its liquidation; what functions the system when it is necessary to implement and what the structure; and, finally, whether there is for this implementation appropriate resources.

Is easy to see that the chain "problem situation, objectives, functions, structures, external resources" forms logically justified (on a content level) sequence of system activity (Figure 1.6), and can be used as stages of the analysis (study) and synthesis ( Design) systems.

Figure 1.6. Model stages of system activity

In this case, the solid line shows the steps of synthesis, and the dashed - analiza.1.2. Model systems 1.2.1. Definition and classification of models of systems

The set of objects surrounding us and the phenomena have the presence of the input properties. The process of knowledge of these properties is that we create for ourselves some idea of ??the object under study to help better understand its internal state, laws of functioning, the main characteristics. Such a representation, expressed in one way or another form called a model. As noted in , a model should be understood any other system that has the same formal structure, provided that:

-between system characteristics model and the original there is a match; -model more simple and accessible to explore and investigate the basic properties of the original object.

Any model is an object substitute the original object, which provides the study of some properties of the original.

Substitution of one object by another in order to obtain information about the most important properties of the original object using the object model can be called a simulation, ie modeling - a representation of the object model to obtain information about an object by means of an experiment with his model.

From the perspective of modeling should be considered as an effective means of knowledge of nature. In this case, the simulation assumes that: the object of study, the researchers an experimental model.

In automated data processing systems and management as a modeling object may be:

-proizvodstvennye processes; administrative processes; processes of the functioning of the technical means; processes of the organization and functioning of the Information

-Ensure the ACS; processes functioning of the software control systems. The advantages of simulation is that there is

-Ability relatively simple means to study the properties of the system, modify its parameters, enter the target and resource characteristics of the environment.

Typically, modeling is used:

1. To study the system before it is designed to determine its basic characteristics and rules of interaction elements among themselves and with the environment;

2. On the design stage for the analysis and synthesis of different types of structures and to select the best embodiment of the subject formulated optimality criteria and restrictions;

3. On the operation phase of the system for optimal performance and forecasts of its development.

Thus the same system can be described by different types of models. For example, some areas of the transport network can simulate the electrical circuit, hydraulic system, a mathematical model using the apparatus of the theory of graphs.

Briefly the classification used in practice patterns:

-by way of describing the model are divided into descriptive (non-formal) and formalized;

-on the nature of occurrence of the objectives of the model are divided into cognitive (theoretical objectives) and pragmatic (practical purposes). At the same cognitive goals are a form of organization and pre-representation of knowledge, connecting means new knowledge available. Pragmatic models are usually management tool, a means of organizing for action, the right way to present exemplary action. It should be noted that in the event of differences between the model and reality, in the first case we are talking about adjusting the model, and in the second case - to change reality, ie in accordance with this model the decision to change the properties and structure of the system;

-on the nature of the elements of the model are divided into physical (analog, power, graphics, drawings, photographs) and mathematics.

In what follows we study only the class of mathematical models, which refers to a set of mathematical expressions describing the behavior of the (structure) of the system and the conditions (disturbance limit), in which it operates. In sovoyu turn, mathematical models depending on the mathematical apparatus are divided into:

a statistical and dynamic;

-determinirovannye and probability;

a discrete and continuous;

analytic and numerical.

Statistical models describe the behavior of the object at any point in time, and reflect the dynamic behavior of the object in time. Deterministic models describe processes in which there are no (not included) random factors, in turn, reflect the probabilistic models of random processes - events. Discrete models describe the processes described by discrete variables, in turn, continuous - continuous. Analytical models describe the process in the form of certain functional relations or (and) logical conditions. Numerical models represent elementary phenomena preserving their logical structure and sequence of the flow of time.

1.2.2. Levels of system models *

The first and most simple and abstract level description of the system is the model, the so-called "black box". In this case, it is assumed that the selected system is associated with the environment through a set of inputs and outputs. The outputs of the model corresponds to the notion of goals, and inputs - respectively the concepts of resources and constraints (Fig. 1.7). This assumes that we do not know and do not want to know about the inner content of the system. The model in this case reflects two important and significant of its properties: integrity and isolation from the environment.

Such a model, despite its apparent simplicity and lack of information about the internal structure, is often useful in the first stage of system analysis.

For example, to analyze the health of domestic TV, you need to check the inputs (power cord, antenna, control knobs and settings) and outputs (CRT screen and output dynamics); systematic description of a manufacturing process should begin with an analysis of its information and material inputs and outputs - planned and resulting performance, the quality of inputs and final products, etc.

Fig. 1.7

It should be noted that there are many systems, the internal structure of which it is impossible or impractical to describe, in which case the model is a "black box" is the only option for their research. For example, we do not know what's inside the human body; at the same time it is necessary to study the impact and behavioral aspects of media influence on the living organism of medicines, etc. Formalization of the model of "black box" is based on the task of two sets of input and output variables, and no other relations between the sets is not fixed.

However, it should be noted that the construction of a model of "black box" is not a trivial task, as the answer to a question about the content of sets is not always straightforward.

Construction of the model is based on the selection of an infinite set of relations with the environment of their finite set, adequately reflects the objectives of the study. Obviously. That such models do not have to be reduced to monosystem (ie, a system with a single input and output), and to justify the necessary and sufficient number of parameters sets X and Y are widely used methods of mathematical statistics, to attract experienced experts.

The next level of modeling complex systems are models of systems. When considering any system in the first place it is found that the integrity and isolation act as an external property. However, as the internal structure of the system is varied, a nonuniform and indivisible member of the plurality of functional elements. Decomposition of the internal structure of the "black box" into smaller components (subsystems, individual elements) allow you to build models of systems (Fig. 1.8).

Fig. 1.8. Model of the system

For example, if the system considered production unit, then as a subsystem are the production sites, but as individual elements - equipment, raw materials, work; theme television system consists of transmission equipment, communication channels, the reception apparatus.

Building a model of diversity due to the nature and forms of the elements is not a simple matter. This can be explained by three factors:

1.neodnoznachnostyu concept of "elementary cell";

2.mnogotselevym nature of the object you want to select an objective for each objective the corresponding composition;

3.uslovnostyu (subjectivity) procedures for dividing the whole into parts (system into subsystems, components).

Simplicity and accessibility models "black box" and the composition can solve with their use of many practical problems. However, for a more detailed (deep) study of systems to be installed in the model structure of relationships (links) between the elements. Description of the system through a set of necessary and sufficient for the purposes of relations between the elements of the structure is called a model system.

A list of links between elements, at first glance, is not-as abstract, abstract model. In fact, how to deal with communication, if not dealt with the elements themselves.

The practical part of Verbal description

The company, which produces some products it carries advertising in two ways through radio and through television. The cost of radio advertising cost the company \$ 5, and the cost of television advertising - \$ 100 per minute.

The company is ready to spend on advertising to \$ 1000 per month. It is also known that the company is ready to advertise their products on the radio at least 2 times higher than on television.

Experience from previous years has shown that television advertising brings in 25 times greater than radio advertising sales of products.

The challenge is in the correct allocation of financial resources of the firm.

Mathematical description.

X1 - the time spent on radio advertising.

X2 - the time spent on television advertising.

Z - the desired objective function, orazhayuschaya maximum sales from 2 types of advertising.

X1 => 0, X2 => 0, Z => 0;

Max Z = X1 + 25X2;

5X1 + 100X2 <= 1000;

X1 -2X2 => 0

Using the graphical method is convenient only when solving LP problems with two variables. For a large number of variables necessary to use an algebraic system. This chapter discusses the general method for solving LP problems, called the simplex method.

Information that can be obtained using the simplex method is not limited to only the optimal values ??of the variables. Simplex method actually allows us to give economic interepritatsiyu solution obtained and analyze the sensitivity of the model.

The process of solving a linear programming problem is iterative in nature: uniform computational procedures in the sequence is repeated until until you get the optimal solution. Procedures implemented within the framework of the simplex method, require the use of computers - a powerful tool for solving linear programming.

Simleks method - is a typical example of iterative calculations used in most of optimization problems. This chapter describes the iterative procedure of this kind, providing the tasks with the help of models of operations research.

In Chapter 2, it was shown that the right and left sides of the limitations of the linear model may be related marks <=, = and =>. In addition, the variables that appear in the LP problem can be non-negative or do not have restrictions on the sign. To construct a general method for solving LP problems corresponding models must be presented in some form, which we call standatrnoy form of linear optimization models. In the standard form of a linear model

1. All restrictions are written in the form of equations with nonnegative right-hand side;

2. The values ??of all variables in the model are non-negative;

3. The objective function subject to the maximization or minimization.

We show how any linear model can be reduced to the standard.

Restrictions

1. The initial limit, written in the form of an inequality of <= (=>)

can be represented as equation by adding the residual to the left side variable restriction (variable excessive subtracting from the left side).

For example, in the left part of the original restriction

5X1 + 100X2 <= 1000

vvodistya residual variable S1> 0, with the result that the initial inequality becomes an equality

5X1 + 100X2 + S1 = 1000, S1 => 0

If the original constraint determines the flow rate of a resource variable S1 should be interpreted as a remnant, or the unused portion of the resource.

Consider the initial limit of another type:

X1 - 2X2 => 0

Since the left side of this restriction can not be less than the right to appeal the initial inequality in equality subtract from the left-hand side variable excess S2> 0. As a result, we obtain

X1 - 2X2 - S2 = 0, S2 => 0

2. The right-hand side is always possible to make a non-negative, multiplying the obi part of -1.

Such as equality X1 - 2X2 - S2 = 0 is equivalent to - X1 + 2X2 + S2 = 0

3. The inequality sign is reversed in the multiplication of both sides by -1.

For example you can substitute 2 <4 record - 2> - 4, the inequality X1 - 2X2 <= 0 is replaced by - X1 + 2X2 => 0

Variables

Any variable Yi, has no limit in the sign, can be represented as the difference of two nonnegative variables:

Yi = Yi'-Yi '', where Yi ', Yi' '=> 0.

This substitution should be used in all restrictions which contain an original variable Yi, as well as the expression for the objective function.

Usually find the solution of the LP, which featured variables Yi 'and Yi' ', and then use the back-substitution determine the value of Yi. An important feature of the variables Yi 'and Yi' 'is that for any feasible solution, only one of these variables can take on a positive value, ie, if Yi '> 0, Yi' '= 0, and vice versa. This allows us to consider Yi 'as residual variable and Yi' '- as redundant variable, with only one of these variables can take on a positive value. This regularity is widely used in the target programming and in fact is a prerequisite for use to appropriate changes in problem 2.30

The objective function

The objective function of the linear optimization model is presented in a standard format, may be subject to both maximize and minimize. In some cases it is useful to modify the original objective function.

Maximizing equivalent to minimization of a function of the same function, taken from an opposite sign, and vice versa. Such as the maximization of

Z = X1 + 25X2

is equivalent to the minimization of the function

(-Z) = -X1 - 25X2

Equivalence means that when the same set of constraints optimum values ??X1, X2, in both cases are identical. The only difference is that with the same numerical values ??of the objective functions of their signs are opposite.

Simplex method.

In the computational scheme of the simplex method is implemented orderly process in which, starting from some initial allowable corner point (usually the origin), made successive transitions from one admissible extreme point to another until, until you find the point corresponding to the optimal solution.

The general idea of ??the simplex method can be illustrated by a model posroennoy for our problem. Space solutions of this problem we represent in Fig. 1. The starting point of the algorithm is the origin (point A in Fig. 1). The solution corresponding to this point, usually called the initial solution. From the reference point moves to a point adjacent to the corner.

Selecting each subsequent extreme point when using the simplex method is determined by the following two rules.

1. Each subsequent corner point must be adjacent to the previous one. This transition occurs along the boundaries (edges) of the solution space.

2. Reverse the transition to the preceding extreme point can not be made.

Thus, the search for the optimal solution begins with a permissible angular point, and all referrals are made only to adjacent points, and before a new transition points obtained from each tested for optimality.

Define the solution space and corner points agebraicheski. Required sootnoschsheniya set of specified in the table corresponds to the geometric and algebraic definitions

.

Geometric definition of algebraic definition (simplex method)

Limitations of the solution space of the standard form

The corner points of a basic solution of the problem in the standard form

Presentation of the solution space of a standard linear programming problem.

The linear model built for our problem and reduced to the standard form, is as follows:

Maximize

Z = X1 + 25X2 + 0S1 + 0S2

Under the constraints

5X1 + 100X2 + S1 = 1000

- X1 + 2X2 + S2 = 0

X1 => 0, X2 => 0, S1 => 0, S2 => 0

Each point of the space of solutions of this problem, shown in Figure 1, can be determined by variables X1, X2, S1 and S2, figuring in the model standard form. When S1 = 0 and S2 = 0 is equivalent to the model limitations that seem relevant edges of the solution space. Increase variables S1 and S2 will match the displacement of admissible points with the boundaries of the solution space in its interior. Variables X1, X2, S1 and S2, which are associated with extreme points A, B, and C can be ordered on the basis of what value (zero or non-zero), this variable is in an extreme point.

Extreme point of zero variables nonzero variables

A S2, X2 S1, X1

In S1, X2 S2, X1

From S1, S2 X1, X2

Analyzing the table is easy to see two patterns:

1. The standard model contains two equations and four

unknown, so in each of the two extreme points (= 4 - 2) variables should be set to zero.

2. Related extreme points differ by only one Pe-

variable in each group (zero and nonzero variables)

The first law suggests the possibility of determining

dividing the extreme points of the algebraic way through merger

equating to zero the number of such variables, which is equal to

the difference between the number of unknowns and the number of equations.

This is the essence of property uniquely extreme

Toce in Figure 1, each point corresponds to a non-extreme

no more than one variable zero. Thus, any point inside

region of the solution space does not have a single zero

variable, and any nonextremal point lying on the boundary,

always zero has only one variable.

Uniqueness property allows the definition of extreme points

share their algebraic method. We assume that the linear

model standard form contains m equations and n (m <= n) non-

known (right restrictions - non-negative). Then

all permissible extreme points are defined as any single

valued non-negative solutions of m equations in which

toryh n - m variables are zero.

Unambiguous solutions of the system of equations obtained

by equating to zero (n - r) variables are called

basic solutions. If the basic solution satisfies

request non-negativity right parts, it is called

admissible basic solution. Variables with zero

value are called nonbasic variables, the rest -

basic variables.

From the above it follows that the implementation of the simplex

Methods of algebraic definition of basis solutions correspond

exists identifying extreme points carried out at

the geometrical representation of the solution space. In such a

time, the maximum number of iterations using simplex

method is equal to the maximum number of basic solutions of the LP,

represented in a standard form. This means that the amount of

Iterative procedures simplex method does not exceed

Cpt = n! / [(N - m)! M! ]

The second of the above mentioned laws is

very useful for the construction of computational procedures symptomatic

Lex method, the implementation of which the sequence

transitions from one extreme point to another adjacent to it. Since adjacent extreme points differ only

one variable, you can define each subsequent (adjacent

tion) extreme point by replacing one of the non-current

baseline (zero) variables of the current basic variable.

In our case, we obtain a solution corresponding to the point A, which implies the transition to point B. To do this, increase the nonbasic variables X2ot initial zero value to the value

tion corresponding to the point B (see. Fig. 1). At point B variable

S1 (which has the base point A) is automatically drawn in

zero and hence becomes nonbasic variables. In this

way between the set and the set of nonbasic basis

variables are variables interchange X2i S1. This

the process can be visualized in the following table.

Extreme point of zero variables nonzero variables

A S2, X2 S1, X1

In S1, X2 S2, X1

Applying the same procedure to all the extreme points

Fig. 1, we can make sure that any subsequent extrema

mal point can always be determined by mutual replacement

One variable in the composition and the basic variables nonbasic

(Adjacent to the previous point). This factor greatly simplifies

Computational procedures for implementing the simplex method.

The above process of mutual change of variables leads

necessary to introduce two new terms. Includes Pe-

nonbasic belt called a variable moment,

to be included in the set of basic variables It should

following iteration (in the transition to an adjacent extreme point).

Excludes variable - this is the basic variable, which

the next iteration shall be excluded from the set of balance

-crisis variables.

Computational procedures of the simplex method.

simplex algorithm consists of the following steps.

Step 0. Using the linear model standard form determined

lyayut initial admissible basic solution by equating

of zero to n - m (nonbasic) variables.

Step 1. Of the current nonbasic (zero) variables

tions choose to include a new variable basis, the increase in

which provides an improvement of the objective function values. If

no such variable, the calculations are terminated, as the current

basic solution is optimal. Otherwise carried

Go to step 2.

Step 2. From the number of variables of the current baseline is selected exclusion

tea variable that must take a value of zero (become

non-ground) with the introduction of the new variable basis.

Step 3. Is the new basic solution corresponding to

new formulations nonbasic and basic variables. The transition to step 1.

We explain the procedure of the simplex method on the example of our problem solving

chi. First, you need to present an objective function and limitations of the model in the standard form:

Z - X1 - 25X2 + 0S1-0S2 = 0 (objective function)

5X1 + 100X2 + S1 = 1000 (limited)

-X1 + 2X2 + S2 = 0 (Limited)

As noted earlier, as the initial trial solution

used the solution of equations in which the two variables are taken to be zero. This provides the only

sensitization and the admissibility of the resulting solutions. In this

case, it is clear that the substitution of X1 = X2 = 0 immediately yields the following result: S1 = 1000, S2 = 0 (t. e. the solution corresponding to point A in Fig. 1). Therefore, the point A can be used as an initial feasible solution. The value Z at this point is zero because both X1 and X2 have the value zero. Therefore, the transformed equation of the objective function so that the right-hand side becomes equal to zero, we can see that the right sides of the objective function and constraints fully characterize the initial decision. It occurs in all cases where the initial basis consists of residual variables.

The results obtained can be conveniently represented in the form of a table:

Basic variables Z X1 X2 S1 S2 Solution

Z 1 -1 - 25 0 0 0 Z - equation

S1 0 1 0 5100 1000 S1 is the equation

S2 0 0 1 -1 2 0 S2 - equation

This table is interpreted as follows. Column

"The basic variables" contains variables trial basis S1,

S2, the values ??of which are shown in the column "decision". At

This implies that the nonbasic variables X1 and X2 (not pre-

representations in the first column) are zero. Value of the objective function

of Z = 1 * 0 + 25 * 0 + 0 + 0 * 1000 1 * equals zero, as shown in the last column of the table.

Determine whether the resulting test solution most

the best (optimal). Analyzing Z - equation, it is easy to replace

mentioning that both nonbasic variables X1 and X2, equal to zero, are

negative coefficients. Always select the variable with the largest absolute value of the negative coefficient (in Z - equation) as well as a practical computing experience shows that in this case, the optimum is reached faster.

This rule base is used in computing

scheme simplex method optimality conditions, which consists in

that, if the problem of maximizing all the nonbasic variables in

Z - The equation coefficients are non-negative, the resulting test solution is optimal. Otherwise chamber

celebrates the new basic variable should choose the one that has

largest absolute value of the negative coefficient.

Applying the optimality condition for the source table, choose

as a variable to be included in the basis, the variable X2. Excluded

tea variable must be selected from the set of base

variables S1, S2. The procedure for selecting the excluded variable involves checking the condition of admissibility requiring that as an excluded variable chosen is that of transition

variables current basis, which is the first vanishes at increased

lichenii includes variables X2 up to a value corresponding to an adjacent extreme point.

We are interested in the ratio of (retaining the desired point pe-intersection and identifies excludes variable) can be

simplex determined from the table. For this column, the respective input variable X2, negative and zero are deleted restriction elements. Then calculates the ratio of the constants appearing in the right-hand sides of these restrictions, the remaining elements of the column corresponding to the input variable X2. Eliminates the variable will be the basis of the current variable, for which the above mentioned ratio is minimal.

The initial simplex table for our problem, obtained after checking the admissibility conditions (t. E., After calculating the corresponding relations and expressly excludes variable), reproduced below. For convenience of description, computational procedures implemented in the next iteration, we introduce some necessary definitions. Column simplex table associated with the input variable will be referred to the leading column. Line corresponding to the excluded variable is called the pivot row (equation), and a table element, located at the intersection of the leading column and pivot row will be called the leading element.

Once defined to include and exclude transition

variables (using the optimality conditions and admissibility)

the next iteration (search for a new basic solution) carried

is a method of elimination of variables, or by Gauss - Jordan. This process changes the base includes two types of computational procedures.

Type 1 (the formation of a leading equation).

New leading line = Previous leading line / host item

Type 2 (formation of all the other equations, including Z - yravnenie).

The new equation = Previous equation -

e u factor

e leading column e * (new leading line).

e e previous

e u equation

Performing type 1 causes that the new

master equation leading element becomes equal to unity.

As a result of the procedure of type 2 all the other co-

coefficients appearing in the leading column become equal

zero. This is equivalent to obtaining a basic solution by use

connection of input variable in all equations except the master.

Applying to the original procedure table 1, we divide S2 - the equation by the leading element equal to 1.

Basic variables Z X1 X2 S1 S2 Solution

Z

S1

S2 0

- 1/2 1 0

1/2 0

To create a new simplex table, perform the necessary computational procedures of type 2.

1. The new Z - equation.

old Z - equation (1 -1 0 0 -25 0)

(- (-25) * (1/2 1 0 0 1/2 0)

(1 -131 / 20 0 121/20)

2. New S1- equation

old S1- equation (1 0 0 5100 1000)

(- 100) * (0 -1/21 01/20)

(1 0 0 55 -50 1000)

New simplex table will look like:

Basic variables Z X1 X2 S1 S2 Solution

Z 1

-13 1/2 0 0

December 1/2 0 Z - equation

S1 0 55 0 1 -50 1000 S1 is the equation

X2 0

- 1/2 1 0

1/2 0 X2 - equation

The new decision X1 = 0 and S2 = 0. The Z value is not changed.

Note that the new simplex table has the same characteristics

tics, like the previous one: only the nonbasic variables

X1i S2ravny zero, and the values ??of the basic variables, as before,

are shown in the column "decision". This corresponds exactly to

the results obtained by using the Gauss-the Jordan

given.

From the last table shows that for the next iteration in accordance

with the terms of optimality as input variables

hydrochloric select X1, because the coefficient of this variable

Z-ypavnenii is -131 / 2. Based on the conditions of admissibility, it is determined that the variable will be excluded S1. The relationships expressed in the right part of the table shows that the new basic solution includes a variable value X1budet ravno1000 / 55 (= minimum ratio). This leads to an increase in the objective function (1000/55) * (-131 / 2) = (2455/11).

To obtain the simplex table corresponding to the new iteration, give the following computing operations of the Gauss-Jordan.

1) The new master equation = S1- Previous S1- equation / (55).

Basic variables Z X1 X2 S1 S2 Solution

Z

S1 0 1 0

1/55

- 50/55

1000/55

X2

2) The new Z - Previous equation = Z - equation - (-131 / 2) * New / master equation:

(1 -131 / 20 0 121/20)

- (-131 / 2) * (0, 1 01 / 55-50 / 551000/55)

(1 0 027/1105/222455/11)

3) New X2- equation = Previous X2- equation - (1/2) * New master equation:

(01/20 -1/21 0)

- (1/2) * (0, 1 01 / 55-50 / 551000/55)

(0 0 11/1101/2291/11)

As a result of these transformations we obtain the following symp-

Lex table.

Basic variables Z X1 X2 S1 S2 Solution

Z 1 0 0

27/110

5 / 2nd 2nd

245 5/11

X1 0 1 0

1/55

- 50/55

100 0 / May 5

X2 0 0 1

1/110

1/22

9 1/11

The new basic solution X1 = 1000 / 55I X2 = 91/11. Z value increased from 0 (previous simplex table) to 2455/11 (the latter simplex table). The resulting increase in the objective function due to an increase up to 1000 X1ot About / 55, as of the Z - line simplex previous table shows that the increase in the variable unit corresponds to an increase of the objective function at (-131 / 2).

Last simplex table corresponds to the optimal solution

NIJ problem, since Z - none equation nonbasic variables did not appear with a negative coefficient. Getting this pezultiruyuschey table and end computational procedures of the simplex method.

In the above example, the algorithm of the simplex method used

use when solving the problem in which the objective function subject to maximization. This minimizes the objective function in this

algorithm need only change the optimality condition:

as a new base peremennoysleduet choose the variable that is in Z - equation has the largest positive coefficient. Admissibility conditions in both cases (maximization and minimization) are the same. It seems appropriate to give the final wording now both conditions used in the simplex method.

Optimality condition. Input variable in the problem of maximization (minimization) is nonbasic variables having a Z-equation largest negative (positive) coefficient In case of equality of the coefficients for a number of nonbasic variables choice is arbitrary, if all the coefficients of the nonbasic variables in Z - equation are nonnegative (nonpositive ), the obtained solution is optimal.

The condition of admissibility, in the problems of maximizing and minimizing as an excluded variable selected is the basic variable for which the ratio of the constant on the right corresponds to the limit (positive) factor leading column is minimal. In case of equality of this relationship for a number of basic variables, the choice is arbitrary.

Optimal solution

From the point of view of practical application of the re-

solving problems LP classification variables, providing

their division into basic and nebaznsnye irrelevant and

analysis of data characterizing the optimal solution can

not taken into account. Variables that are not in the column "Basis

variables ", be sure to have a value of zero. OC values

experimental variables are given under "Resolution". When the interval

tation of optimization results in our problem, we are primarily interested in the amount of time that our company will order on radio and TV, t. e. the values ??of the controlled variables X1i X2. Using the data contained in the simplex table for the optimal solution, the main results can be summarized as follows:

The optimal values ??of the controlled variables Solution

X 1

1000/55 Time allocated by TV advertising

X 2

9 1/11 Time allocated to the radio advertising company

Z

245 5/11 Profits derived from advertising.

Note that Z = X1 + 25X2 = 1000/55 + 25 * 91/11 = 2455/11. This decision is consistent with the final simplex table .Status resources

Will refer to scarce resources or nedifitsitnym depending on whether total or partial use

tion provides an optimal solution to the problem. Now the goal

is to obtain the relevant information di-

rectly from the simplex table for the optimal solution. Single

ever, you must first clearly understand the following. Talking about resources,

appearing in the LP problem, we assume that the set

some maximum limits of their reserves, so the corresponding

sponding initial restrictions to be used on the <=.

Consequently, the sign restrictions => can not be considered

as constraints on resources. Rather, the limitations of this type of reflection

zhayut the fact that the solution must satisfy the definition

divided requirements, such as ensuring a minimum demand

meat or minimal deviations from the established structural

characteristics of production (sales).

In the model developed for the problem, the restriction appears with the sign <=. This requirement can be regarded as a restriction on the relevant "resource", since the increase in demand for the products is equivalent to the expansion of "representation" of the firm on the market.

From the above it follows that the status of resources (scarce

or a readily available) for each model can be installed non-LP

indirectly resulting from the simplex table, paying at-

tion to the residual values ??of variables. Applied to our problem can cause the following summary of the results

:

Resources residual variable Inventory Status

Restriction on the budget

S 1 Deficient

Timeout radio advertising on TV

S 2 Deficient

A positive value indicates the residual variable

incomplete use of the resource, that is. e. given

resource is nedefitsyatnym. If the variable is equal to the residual

at zero, it indicates full consumption sootvetstvuyusche-

th resource. The table shows that our resources are scarce. In the case of a readily available any uvilichenie resources in excess of the maximum value would lead only to the fact that they would become even more nedefnintnymi. Optimal solution in this case would remain unchanged.

Resources, an increase in stocks which can improve the re-

solution (increase profits), - a residual variables S1i S2, Therefore

How many of the simplex table for the optimal solution can be seen,

they are scarce. In this regard, it is logical to ask the following

question: which of the scarce resources should be given preference

at an investment of additional funds to increase their reserves

owls in order to get the most out of them? Answer to

this question will be given in the next section of this chapter, where the distribution

regarded the value of different resources.

The value of the resource

The value of the resource is characterized by improved optical

minimum value Z, per unit volume growth

this resource.

Information for the optimal solution of the problem presented in the simplex table. Pay attention to the values ??of the coefficients Z - equation, standing at varying initial basis S1i S2. Mark for convenience sootvetstzuyuschuyu part of the simplex table:

Basic variables Z X1 X2 S1 S2 Solution

Z 1 0 0

27/110

5 / 2nd 2nd

245 5/11

As follows from the theory of solving LP problems, the value of resources can always be determined by the values ??of the coefficients of the variables of the initial basis, appearing in Z - equation optimal simplex table, so Y1 = 27/110, and Y2 = 5/22.

We show how a similar result can be obtained directly from the simplex table for the optimal solution. Consider Z - equation simplex table for the optimal solution of our problem

Z = 2455/11 (27 / 110S1 + 5 / 22S2).

Incremented variable S1otnositelno its current

zero value leads to a proportional decrease in Z,

the proportionality coefficient raven27 / 110. But, as follows from the first limitations of the model:

5X1 + 100X2 + S1 = 1000

increase S1ekvivalentno reduce the amount of money allocated for advertising (hereafter we will use in the text, as the first resource).

It follows that the reduction in the amount of money allocated for advertising causes a proportional decrease in the objective function with the same coefficient of proportionality ravnym27 / 110.Tak as

we operate with linear functions, the resulting output can be

summarize, considering that an increase in the amount of money allocated for advertising (equivalent to the introduction of excessive variable S1 <0) leads to a proportional increase in Z with the same coefficient of proportionality ravnym27 / 110. Similar arguments

Livs to limit 2.

Although the value of the various resources defined by

values ??of the variables Yi, was presented in terms of value, it can not be equated with the actual Task

us, for which the possibility of purchasing the appropriate resources.

In fact, we are talking about some extent with economic

Mr. quantitatively characterizing the nature of the resource value only in relation to the obtained optimal value of the objective function.

If you change the restriction of appropriate economic model

assessment will vary even when the optimized process

involves the use of the same resources. Therefore, when characteristics

tick value resource economists prefer to use

Terms such as the shadow price, the implicit price, or more spe-

fichny term - dual assessment.

Note that the shadow price (the value of the resource) characterizes in-

intensity to improve the optimal value Z. However,

not fixed range of values ??increase resource stocks,

in which the intensity of the improvement of the objective function remains

constant. For most practical situations logical pre-

put the upper limit of the presence of increasing reserves, with pre-

which elevated the corresponding limit becomes excessive

accurate that in turn results in a new basic solution

and the corresponding new shadow prices. The following shall be

niterval values ??of resource stocks, where relevant

The present restriction does not become excessive.

The maximum change in resource stocks

When deciding on whether a stock of resources should be

increase in the first place, are commonly used shadow prices

To determine the range of values ??of inventory change resource

where the shadow price of the resource, (appearing in the conclusion

considerably simplex table remains unchanged, it is necessary to perform some additional calculations. Consider first

appropriate computational procedures, and then show how

the required information can be obtained from the simplex table

for the optimal solution.

In our problem, the stock has changed to the first resource D1t. e. the budget reserve of 1,000 + D1. With a positive value D1zapas this resource increases, the negative - is reduced. Typically, examines the situation increases when the amount of the resource (D1> 0), however, to obtain the result in a general way, we consider two cases.

How to change the simplex table when changing the value of the charge

pass the resource to D1? The easiest way to answer this question.

if you enter the right-hand side of the first D1v restrictions initial symmetry

Plex table and then perform all the algebraic transformation

of the corresponding sequence of iterations. Since

right sides of the constraints are never used as a

pivots, it is evident that at each iteration D1budet

have an impact only on the right side constraints.

The values ??of elements of the equation on the right side of the respective iterations

(Early calculations) 1 to 2 (optimum)

Z 0 0

245 5/11

January 1000

1000 + D 1

1000/55 + D 1

2 0 0

9 1/11

In fact vce change right sides limitations due

lennye introduction D1, can be determined directly from the data

contained in the simplex tableau. First of all, note that

at each iteration, a new right-hand side of each restriction pre-

is the sum of two values: 1) constant, and 2) the member lines

linearly dependent on D1. Continued compliance with numbers that

appear on the corresponding iterations of restrictions on the right sides of the simplex table before the introduction of D1. D1vo coefficients of the second term is at odds S1na the same iteration. For example, at the last iteration (optimal solution) permanent (2455/11, 1000/55, 91/11) are sobo numbers appearing in the right-hand portion of the limited optimal simplex table before the introduction of D1. Coefficients (27/110; 1/55; 1/110) are the coefficients of the same S1v simplex table because this variable is associated only with the first constraint. In other words, when analyzing the impact of changes on the right side of the second restriction is necessary to use the coefficients of the variable S2.

What conclusions can we draw from these results?

Since the introduction D1skazyvaetsya only on the right side simplex

table, change the resource stock can affect only

admissible solutions. Therefore D1ne can take values

in which any of the (basic) variables becomes nega-

tive. From this it follows that the value D1dolzhna be lim-

nichena this range of values ??under which the INSTALLS

dition non-negativity restrictions on the right sides of the resultant

RATE simplex table, that is. e.

X1 = 1000/55 + (1/55) D1 => 0 (1)

X2 = 91/11 + (1/110) D1 => 0 (2)

To determine the allowable range of variation D1rassmo-

consider two cases.

Case 1: D1 => 0 is obvious that both neravnestva under this condition will always be non-negative.

Case 2: D1 <0.

(1/55) D1 => -1000/55. From this it follows that D1 => - 1000

(2)

(1/110) D1 => - 91/11. From this it follows that D1 => - 1000

Combining the results obtained in both cases, it is possible

conclude that - in 1000 <= D1 <= + ? solution of the task

chi will always be valid, any value D1, going beyond

outside this range lead to unacceptable solutions and

a new set of basic variables.

Now consider to what extent may vary headroom 2 analysis was performed in a similar way:

Stock second resource has changed to D2t. e. supply of advertising time will be 0 + D2. How has the simplex table to the extent that the resources are on the D2.

The values ??of elements of the equation on the right side of the respective iterations

(Early calculations) 1 to 2 (optimum)

Z 0 0

245 5/11

1 1000 1000

1000/55

2 0

0 + D 2

9 1/11 + D 2

Let us find the limiting value range D2

X1 = 1000 / 55- (50/55) D2 (1)

X2 = 91/11 + (1/22) D2 (2)

To determine the allowable range of variation D1rassmo-

consider two cases.

Case 1: D2 => 0: (1)

(50/55) D2 <= 1000 / 55iz this inequality implies that D2 <= 20

(2)

Obviously, the second equation is non-negative on the site.

Combining the two equations for Case 1, we obtain the interval for D2.

D2I [0; 20]

Case 2: D2 <0. (1)

(50/55) D2 => -1000/55. From this it follows that D2 <= 20

(2)

(1/22) D2 => - 91/11. From this it follows that D2 => - 200

Combining the two equations for the case 2, we obtain the interval for D2.

D2I [- 200; 0]

Combining the two cases we obtain the interval [- 200; 20]

The maximum change in the coefficients of specific profit (cost)

Along with the definition of acceptable change resource stocks

Owls of interest and the establishment of permissible range

changes in factors specific profit (or cost).

It should be noted that the objective function equation is never used as a master equation. Therefore lyu-

bye changing coefficients of the objective function will have an impact

Z-only simplex resultant equation table. Is This

means that such changes may make the resulting solution

suboptimal. Our goal is to find inter-

shafts values ??changes the coefficients of the objective function (distribution

smatrivaya each coefficient separately), under which determined

mal values ??of the variables remain unchanged.

To show how to implement the relevant calculations

tion, we assume that the specific volume of sales associated with the variable

X1izmenyaetsya from 1 to 1 + d1gde d1mozhet be both positive and negative. The objective function in this case takes the following form:

Z = (1 + d1) X1 + 25X2

If you use these initial simplex table and

perform all the calculations necessary to (get zaklyuchn-

tive simplex table, the last Z-equation will vyglya-

do as follows:

Basic variables X1 X2 S1 S2 Solution

Z 0 0

27/110 + 1/55 d 1

5/2 2 - 50/55 1 d

245 5/11 + 100 0/5 5 1 d

The coefficients of the basic variables X1, I X2i residual equal to zero. This equation differs from the Z-administration to equation d1, only the presence of members comprising d1. D1ravny coefficients of the coefficient of the relevant variables in the equation Z-simplex table for previously obtained optimal solution

Basic variables X1 X2 S1 S2 Solution

X1 0 1

1/55

- 50/55

100 0 / May 5

We consider X1- equation as coefficient is at

Eton variable in the expression for the function changed tselevoi

on d1.

The optimal values ??of the variables will remain unchanged

governmental at values ??d1, satisfying non-negative

of (the problem of finding the maximum) all the coefficients of the non-

basic variables in the Z-equation. Thus, subject to the following inequality:

27/110 + 1 / 55d1 => 0

5 / 22-50 / 55d1 => 0

From the first inequality we obtain that d1 => - 13,5, and the second follows that d1 <= 1/4. These results define the limits of variation coefficient C1v as the following ratio: - 13,5 <= d1 <= 1/4. Such

Thus, with a decrease in the coefficient of the objective function

X1do variable value equal to 1 + (- 13.5) = - 12.5 or by increasing it to 13.5 + 1 = 14.5 optimal values ??of the variables are

unchanged. However, the optimum value of Z will vary (in accordance with the expression 2455/11 1000 + / 55d1, wherein - 13,5 <= d1 <= 1/4

X2izmenyaetsya from 25 to 25+ d2gde d2mozhet be both positive and negative. The objective function in this case takes the following form:

Z = (25 + d2) X2 + X1

All the previous discussion relating to research changes the coefficient of the variable that is assigned a limit appearing in the simplex table. However, there is a limitation only in the case where the variable is basic (e.g. X1i X2). If the variable is nonbasic, the column that contains the basic variables, it will not be presented.

Any variation of the objective function at the nonbasic variables leads only to the fact that in the final simplks table only changes this ratio. Consider as an illustration of the case where the coefficient of the variable S1 (first residual variable) varies from 0 to d3. Performing transformations needed to obtain the final simplex table leads to the following result Z-equation:

Basic variables X1 X2 S1 S2 Solution

Z 0 0

27/110 + 1/55 d 1

5 / 2nd 2nd

245 5/11

Conclusion

As a result of the study, it was verified the beneficial use of mathematical and economic design and system analysis methods for the analysis and planning of economic systems.

References:

At this point, should be indicated literature used in the course work, but progress has led to the fact that all the information was gathered on the pages INTERNET, and hence

List of servers:

www.citforum.ru

www.rambler.ru

www.msu.ru

www.ntcf.ru

www.yandex.ru

© 8ref.com - українські реферати