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

Mathematics programmers - Nakonechny S.I.

2.2. The economical-mathematical model of problems of linear programming

Загальна лінійна економіко-математична model of economical processes in those cases - the so-called zagalnaya problem lіnіynogo програмування подається у вигляді:

(2.1)

For the mind:

(2.2)

(2.3)

Otzhe, Potrnibno znachit znachennya zmіnnikh x 1, x 2, ..., xn , yakі zadovolnyayut umovi (2.2) and (2.3), and the centrinal function (2.1) requires an extra (maximal minimum value).

For dovilnoy problems of mathematical programming, in § 1.2, boules are introduced to understand the permissible optimal plan.

For zagalnoy tasks lennyi programvannya vikoristovuyatsya taki ponyattya.

The vector X = ( x 1, x 2, ..., x n ), the coordinate of which is to satisfy the system of (2.2) and that of the unknowns (2.3), be allowed to be rozv'yazkom (plan) tasks and linear program .

Admissible plan X = ( x 1, x 2, ..., xn ) is called a basic plan of tasks of linear programming, yakschoo vin is not less satisfying, it is not possible to replace them with the system (2.2) in vigilant areas, and (2.3) shodo nevid ' Ємності змінних.

The basic plan is X = ( x 1, x 2, ..., xn ), nazivaetsya neizrogenim , yakshcho vinit m precisely m dodatnyh zmіnnih, inaksin vin virodzheniy .

The basic plan (2.1) reach the maximum (or the minimum) value, be called the optimal rozv'yazkom (plan) tasks and linear program .

The problem (2.1) - (2.3) can easily be reduced to a canonical form, then to such a vigil if in the system (2.2) all bi ( i = 1, 2, ..., m ) are not available, but all are interchanged.

Yaksho yaksy bi bi vіd'єmne, then multiplied i-that obmezhennia on (- 1), distano in the right part of the vidpіdnogo rivnosti dodatne znachennya. If i i x 1 + a i 2 x 2 + ... + a in xn ≤ bi , then the rest of the wizard can be called up to the level, having obtained the additive xmin + 1: ai 1 x 1 + ai 2 X2 + ... + + ain xn + xn + 1 = bi .

Analogously to the form a k 1 x 1 + ak 2 x 2 + ... + aknxn ≥ bk zvodyat till rіvnostі, vіdnіmayuchi vіd lіvoї partni додаткову змінну хn + 2, тобто: ak 1 x 1 + ak 2 x 2 + ... + aknxn - xn + 2 = bk ( xn +1 ≥ 0, xn +2 ≥ 0).

Dovedemo, scho zamenina nervenosti rivnyannymi for dopomoyu introduced dodatkovyh zmіnnih not zmіnit rozv'yaku pochatkoy zadachi. Розглянемо лінійну нерівність з n невідомими:

(2.4)

Для зведення нерівності (2.4) до рівняння нехідно до її лівої частини додати акку невід'ємну size х n + 1 ≥ 0. In the result дістаємо лінійне рівняння, яке містить n + 1 змінну:

A 1 x 1 + a 2 x 2 + ... + anxn + xn + 1 = b . (2.5)

THEOREM 2.1. Skin rozvozyu Нерівності (2.4) відповідає єдиний розв'язок Рівняння (2.5), which is one-hourly є rozv'yazkom nervivnosti (2.4), і, навпаки, кожному розв'язку Рівняння (2.5) і нерівності (2.4) відповідає єдиний розв'язок Nervivnosti (2.4).

Доведення : Нехай X * - розв'язок нерівності (2.4), тоді підстановко Нерівність виконується:

.

Moved to the left of the part of the given nerve in the right and knowable visas of the right part through , Tobto:

Otzhe, rozv'azok Задовольняє рівняння (2.5) and water stress (2.4). Дійсно, і при підстаноці In рівняння маємо:

Навпаки, нехай Y * задовольняє рівняння (2.5) і неівність (2.4), тобто:

I .

Тоді, відкидаючи в лівій частині рівності невід'ємнуну magnitude , Отримаємо нерівність:

.