Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 [ 40 ] 41 42 43 44 45 46

Невозможность такого перехода означает, что либо найдено решение задачи линейного программирования, либо установлено, что задача линейного программирования неразрешима, т. е. функция L(x) на множестве Г принимает сколь угодно большие значения (это возможно лишь в случае, если множество Г является неограниченным).

Мы начнем с описания этапа 2, считая, что некоторая вершина х множества Г известна.

Если вершина х = (жх, ж2, , xq) множества Г известна, то в силу условия невырожденности из набора чисел (1,2,..., q) можно выбрать р чисел s\, s2,..., sp, таких, что Xj > 0, если j равно одному из чисел 3\, s2,..., sp, и ж,- = 0, если j не равно ни одному из этих чисел.

Лемма, р-мерные вектора Dgl, D,2,..., D3p линейно независимы.

Доказательство. Предположим противное. Тогда существуют числа а1? а2,..., ар не все равные нулю, такие, что

f>D . =0.

Построим q-мерный вектор у = (yi,y2,... ,yq) следующим способом

{а,-, если j = Si при некотором i 0, если j не совпадает ни с одним из чисел Si.

Тогда

Выберем е > 0 так, что при любом г = 1,2,... ,р

x i -£Уч>® и xt. +eySi > 0.



Это возможно сделать в силу условия хв! > 0 при г = = 1,2, ...,р. Тогда точки х = (х - еу) и х - (х + еу) принадлежат множеству Г, поскольку координаты каждой из них удовлетворяют условиям (10.2) и (10.3). С другой стороны,

Но множество Г является выпуклым, и его вершина не может быть серединой отрезка, соединяющего две другие точки этого множества. Лемма доказана.

Линейно независимые вектора DSl, DS2,..., DSp, построенные по вершине х множества Г, называются базисом этой вершины. Разложим каждый из векторов D0, -Di, D2,..., Dq по векторам базиса:

Рассматривая это разложение при j = 0, легко сделать следующий вывод. Зная вектор D0 и базис вершины, можно однозначно восстановить координаты этой вершины. Действительно, сравнивая формулы (10.4) и (10.2), видим, что 7 о = xni i = 1)2,... ,р. Отметим, что в силу условия невырожденности 7io > 0 при i - 1,2,... ,р.

При j - 1> 2,..., q введем обозначения

х =0.5 х + 0.5 х .

(10.4)


Здесь ci, с2,..., cq - коэффициенты из (10.1).



Зная коэффициенты 7 и величины Д.,-, можно определить, какая из следующих трех ситуаций имеет место.

1. Рассматриваемая вершина х является решением задачи линейного программирования.

2. Задача линейного программирования не имеет решения.

3. Перебор вершин следует продолжить. Ответ имеет следующий вид.

1. Если Aj > 0 при любом j = 1,2,..., q, то вершина х является решением задачи линейного программирования.

2. Если существует j такое, что Д- < 0, и все соответствующие данному j коэффициенты неположительны, т. е.

7ij < 0 при * = 1,2,...,р,

то задача линейного программирования неразрешима, т. е. при ограничениях (10.2), (10.3) линейная функция £(ж), определяемая в (10.1), может принимать сколь угодно большие значения.

3. Если Дл- < 0 для некоторых индексов j, и для каждого такого j, по крайней мере, одно из чисел 7 положительно, то существует вершина у множества Г, для которой L(y) > > L(x).

Эта вершина у может быть найдена следующим образом. Зафиксируем некоторое к, для которого Д*. < 0. Например, можно выбрать к так, чтобы Ак было наименьшим из всех Д ,-. Среди всех индексов г (1 < i < р), для которых jik > 0, выберем тот индекс (обозначим его через г), для которого

7го . 7*о - = mm -.

7rfe * 7*fe

Используя условие невырожденности, можно показать, что



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 [ 40 ] 41 42 43 44 45 46