Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

Общая форма задачи имеет вид: найти при условиях

где

Здесь и далее нам удобнее считать с и аі вектор - строками, а x и b=(b1,...,bm)T - вектор столбцами.

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

т. е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I2 = 0, а в другом - I1 = 0.

Задача ЛП в канонической форме:

(1)

(2)

(3)

Задача ЛП в стандартной форме:

В обоих случаях А есть матрица размерности m x n, i-я строка которой совпадает с вектором аi.

Форма записи задачи ЛП. Задачу линейного программирования можно сформулировать так:

Максимизировать (4)

при условиях

(5)

(6)

Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой "легко" преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.

НЕ нашли? Не то? Что вы ищете?

Симплекс-метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г. Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.

Алгоритмы симплекса-метода позволяют также установить, является ли задача ЛП разрешимой.

Запишем ограничения задачи ЛП в таком виде:

A1x1 + A2x2 + ... + Anxn + An+1xn+1 + ... + An+mxn+m = A0.

Пусть A1,...,Am - множество линейно независимых векторов.

Тогда уравнение

A_1 x_1^* + A_2 x_2^* + \ldots + A_n x_n^* + A_{n+1} x_{n+1}^* + \ldots + A_{n+m} x_{n+m}^* = A_0

((1)

определяет базисное решение x_1^*, x_2^*, \ldots ,x_m^*,

Предположим, что это решение допустимо, то есть x_1^* \geq 0, x_2^* \geq 0, ., x_m^* \geq 0. Базис {A1,.,Am} образует m-мерное пространство, а потому каждый из векторов Am+1,.,Am+n единственным образом выражается через этот базис. Если Ar не входит в базис, то

A_1 x_{1r} + A_2 x_{2r} + \ldots + A_m x_{mr} = A_r,

(2)

где xir - соответствующие коэффициенты (i = 1, 2, ..., m).

Предположим, что хотя бы одна из величин xir больше нуля.

Решение уравнения

A_1 x_1 + A_2 x_2 + \ldots + A_m x_m + A_r x_r = A_0

(3)

обозначим как \{ \widetilde{x}_1 , \widetilde{x}_2 , \ldots , \widetilde{x}_m , \widetilde{x}_r \}

Тогда, очевидно:

A_1 \widetilde{x}_1 + A_2 \widetilde{x}_2 + \ldots + A_m \widetilde{x}_m + A_r \widetilde{x}_r =A_0 .

(4)

Умножив уравнение (4.2) на xr и вычтя полученное уравнение из уравнения (4.1), получим

A_1 (x_1^* - x_r x_{1r}) + A_2 (x_2^* - x_r x_{2r}) + \ldots + A_m (x_m^* - x_r x_{mr}) = A_0 - x_r A_r .

(5)

Сравнив уравнения (5) и (4), находим связь нового решения \widetilde{x}_1, ., \widetilde{x}_m, x_r со старым базисным решением x^*_1, ., x^*_m:

\widetilde{x}_1 = x_1^* - x_r, \, \widetilde{x}_2 = x_2^* - x_r x_{2r} , \, \ldots , \, \widetilde{x}_m = x_m^* - x_r x_{mr} , \, x_r .

(6)

Решение (4.6), во-первых, не будет базисным, так как содержит m + 1 переменную, а во-вторых, будет допустимым не для всех значений xr.

Чтобы новое решение оставалось допустимым, нужно выбрать значение xr таким, чтобы ни одна из величин \widetilde{x}_i = x_i^* - x_r x_{ir} \quad (i=1, 2, \ldots, m) не стала меньше нуля. Следовательно, максимальное значение переменной xr определяется соотношением

x_{r \max} = \min_i \left\{ \frac{x_i^*}{x_{ir}} \right\} ,

(7)

где xir > 0.

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

Для этого выбираем значения в соответствии с (7). Тогда новое базисное решение имеет вид

\begin{align*} & x_1^* - x_{r \max} x_{1r} ; \\ & x_2^* - x_{r \max} x_{2r} ; \\ & x_j \; \text{(опущен)} \\ & x_{r \max} , \end{align*}

а новый базис - (A1, A2, ., Aj-1, Aj+1, ., Am, Ar).

Такой переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению, которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность).

Новому ДБР x_1^*соответствует следующее значение целевой функции

\begin{align*} z_1 &= c_1(x_1^* - x_r x_{1r}) + c_2(x_2^* - x_r x_{2r}) + . + c_r x_r = \\ & = (c_1 x_1^* + c_2x_2^* + \ldots + c_m x_m^*) + x_r (c_r - c_{1r} - \ldots - c_mx_{mr}) = \\ & = z_0 + x_r (c_r - c_1 x_{1r} - \ldots - c_m x_mr), \end{align*}

(8)

где z0 - значение целевой функции для начального ДБР;

сr-с1x1r - с2x2r - ... - сmxmr - симплекс-разность для переменной хr.

Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение, и выбирают такую небазисную переменную хr, для которой симплекс-разность положительна и максимальна.

Таким образом, алгоритм симплекс-метода состоит из следующих этапов:

1.  находят начальный базис и связанное с ним допустимое базисное решение;

2.  вычисляют симплекс-разность для каждой переменной, не входящей в базисное решение;

3.  вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплекс-разностью; ее значение x_{r \max} определяют из соотношения

x_{r \max} = \min_i \left\{ \frac{x_i^*}{x_{ir}} \right\}

для всех xir > 0;

4.  выводят из базисного решения переменную xj, соответствующую

\min_i \left\{ \frac{x_i^*}{x_{ir}} \right\} = \frac{x_j^*}{x_{jr}}

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13