Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Начальный опорный план задачи (5.1) - (5.3) имеет вид

[pic]
Переменные [pic] называются искусственными переменными.

Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой известен. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план задачи (2.1) - (2.3), либо убедиться в ее неразрешимости, если оказывается неразрешимой М-задача.

В соответствии с вышеизложенным имеем: требуется решить задачу
(2.12), (2.13), записанную в канонической форме. Введем искусственную неотрицательную переменную х9 и рассмотрим расширенную М-задачу

[pic] (5.4) при условиях

[pic] (5.5)

[pic], где [pic]. где М – сколь угодно большая положительная величина.

Как и в L-задаче, добавление только одной искусственной переменной
[pic] (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7.

6. Решение М-задачи II алгоритмом симплекс-метода

Описание II алгоритма

Второй алгоритм (или метод обратной матрицы) симплекс метода основан на ином способе вычисления оценок [pic] векторов условий Аj, чем в первом алгоритме.

Рассматривается задача линейного программирования в канонической форме
(2.1) - (2.3). Пусть Х – опорный план с базисом [pic]. Все параметры, необходимые для оценки плана на оптимальность и перехода к лучшему плану, можно получить, преобразовывая от шага к шагу элементы матрицы [pic].

Действительно, зная обратную матрицу [pic], можно получить базисные составляющие опорного плана:

[pic] и вычислить оценки векторов условий относительно текущего базиса

[pic], (6.1) предварительно определив вектор-строку [pic] по формуле

[pic] или

[pic]. (6.2)
Здесь [pic]- вектор-строка из коэффициентов линейной формы, отвечающих базисным переменным.

Оценки [pic] позволяют установить оптимальность рассматриваемого опорного плана и определить вектор Ак, вводимый в базис. Коэффициенты [pic] разложения вектора Ак по текущему базису вычисляются по формуле

[pic].

Как и в I алгоритме, вектор, подлежащий исключению из базиса, определяется величиной

[pic].

Таким образом при втором алгоритме на каждом шаге запоминаются базисные компоненты [pic], обратная матрица [pic], значение линейной формы F(X) и вектор Y, соответствующие текущему опорному плану Х. Элементы столбцов матрицы [pic] удобно рассматривать как коэффициенты [pic] разложения единичных векторов [pic] по векторам базиса. Рекуррентные формулы, связывающие параметры двух последовательных итераций

[pic]; (6.3)

[pic]. (6.3)
Здесь

[pic].

Рекомендуем скачать другие рефераты по теме: доклад, курсовая работа на тему предприятие.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки