Читать курсовая по финансовому менеджменту, финансовой математике: "Задача составления оптимального графика ремонта инструмента" Страница 3

(Назад) (Cкачать работу)

Для удобства решения xj ( j=0(1)5 ); yj ( j=1(1)2 ); zj ( j=1(1)3 ); uj ( j=1(1)6 ) заменим на xk, где k=1(1)17. Ограничения примут вид:

xk 0 ( k = 1(1)17)

Для решения задачи методом искусственных переменных добавим в ограничения и целевую функцию переменные x18, x19, x20, x21, x22:

,

при ограничениях:

xk 0 ( k = 1(1)22)

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

A1x1+...+Anxn+e1xn+e1xn+1+…+emxn+m=A0=[ai0],

где

. - единичный базис, ai0 ≥ 0

для всех i = 1, 2,..., n. Применим одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, ., An, e1, ., em, A0].

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение было минимально при условии, что aij>0.

При таком преобразовании в базис вводится вектор Aj и выводится вектор Аi. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов ∆j:

(2.2.21)

где Iб - множество индексов базисных векторов; xij- определяют из условия

(2.2.22)

Величины {∆j} равны симплекс-разностям для переменных {xj} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец Аj с наибольшей по модулю отрицательной оценкой, то есть

.

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.2.

Таблица 2.2.

Последняя строка таблицы - индексная служит для определения направляющего столбца. Ее элементы ∆j определяют по формуле (2.2.21). Очевидно, для всех базисных векторов {Ai} i=1,.,m оценки ∆i=a0i=0.

Значение целевой функции a00 определяется из соотношения

.

В столбце Bx записываем базисные переменные {xi} i= 1, ..., т. Их значения определяются столбиком свободных членов ai0, то есть xi = ai0, i=1, 2,.,m.

Направляющие строка Ai и столбец Aj указываются стрелками. Если в качестве направляющего элемента выбран aij, то переход от данной симплекс таблицы к следующей определяется соотношениями (2.2.16) - (2.2.18).

Алгоритм решения задачи ЛП табличным симплексом-методом состоит из этапов.

1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

2. В качестве направляющего столбца выбирают Aj, для которого .

3. Направляющая строка Aі выбирают из условия

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом aij, для чего используют соотношения (2.2.16) - (2.2.18). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

Похожие работы