home Other disciplines Books Mathematics programmers - Nakonechny S.I.

Mathematics programmers - Nakonechny S.I.

ROZDIL 3. THEORETICAL DUALITY TWO TWO OCINS IN LINE PROGRAMMING

"And the last beggar, under other conditions,

Is able to be the first rich man. "

Compositions by Kozma Prutkov

3.1. Eco-friendly Interpretation of the direct tasks of the linear programming

The leather task of the linear program is written in the form of a so-called dual task.

Economically, the integration of the skin of such a problem is rooted in the application of vibrotic problems (§ 2.1).

Directly the problem is : max F = c1x1 + c2x2 + ... + cnxn (3.1)

For the mind: (3.2)

. (3.3)

Necessarily viznachiti, yaku kіlkіst productions dermal j - th type Neobhhidno vigotovlati v protsessi vibrobitvtva, shchob maksimizuvaty zagalnu virchku vіd realizatії produktsii pіdpriєmstva. Причому відомі: наявні обсяги ресурсів - ; Normi ​​vitrat і- th kind of resource on the virbitnitsu odinnitsi j - th kind of product - , But also - Ціни реалізації одниці j -ої продукції.

Roshglyanemo now tsyu task itself zinoshogo look. It is permissible, but for the previous minds, to sell the deed to part of the whole resource. It is necessary to vignify the resource values. Skin Resource Posovimo u vidpovdnist yogo otsinka . Wisely in the right, scho - The price of the resource is the same.

On vigotovlennya oditnitsi j - th type of product vitrachayatsya zgіdno in the model (3.1) - (3.3) m vidiv resources in kіlostіі vіdpіidno . Оскільки ціна одниці і- го view the resource дорівнює , Then zagalna vartіst resursiv, shto vitrachayutsya vibromnitsut odinnitsi j - th kind of product, enumerate in such a way:

.

Sell ​​the resource dotsilno deprive for umovi, scho virchka, otrimana vіd sale of resources, перевищує суму, yak mozhno bulo b otrimati vіd realіzіcії produktsії, vygotovlenії з тих обсягів ресурсів, тобто:

.

Зрозуміло, що покупці ресурсів прагать здійснити операцію якнайдешевше, отже, необхідно визначити мінімальні ціни odіnitsk of the skin type of resources, for some їх sales є доцільнішим, ніж виготовлення продукції. I can increase the number of resources in terms of the formula:

.

In the result, in the result, the task is :

(3.4)

For the mind: (3.5)

(3.6)

Tobto neobhіdno viznachiti, yakі mіnіmalnі tsіni mozhna vstanoviti for odnitsy dermal i- th kind of resource , Щоб продаж ресурсів був доцільнішим, ніж виробництво продукції.

Zauvazhimo, scho spravzhny zmist values - Умовні ціни, що виражають рівень "цінності" is a resource for danogo vibrobitvva. Anglijskij term "shadow prices" at the frontier yak "otsinka" abo "tinyou, implicit tsina." Academician L. V. Kantorovich called їх objectively the educational resources of the resource.

The problem (3.4) - (3.6) is conjugate to problems (3.1) - (3.3), and yak is called direct (basic, pogotkov). Поняття двоїстості-взаємним. On suti mova yde about one and the same problem, ale z riznyh poglyadiv. Dyssno, it is not important to change over, but the task before (3.4) - (3.6) zbiagetsya pobatkova. It is possible for them to make a direct cut from them, and іншу - dvuhistoyu. The symmetry of these two problems is obvious. Yak in straight lines, so in two tasks one can find one nabir of obchatkovyh tribute: , ; . In addition, the vector of obtobzhen pochatkoy tasks and the vector of the functions of the functions of the two functions and problems, and the rows of matrices A (matrixes of functions in the case of interchange of direct tasks) become stacks of matrices in the middle of the problems in the dual tasks. Skin obmenzhennu pochatkoy tasks vidpodiada zmіnna dvuhistoy i navpaki.

The formulation of the problem and the mathematical model of the waveguide operator (3.1) - (3.3), and (3.4) - (3.6). Otzhe, as a rule, seems to be about a pair of conjugating problems of linear programming.