Баланс: 0.00
Авторизация
Openstudy » Рефераты » Наука и техника (Рефераты) » Метод искусственного базиса
placeholder
Openstudy.uz saytidan fayllarni yuklab olishingiz uchun hisobingizdagi ballardan foydalanishingiz mumkin.

Ballarni quyidagi havolalar orqali stib olishingiz mumkin.

Метод искусственного базиса Исполнитель

Matn

Метод искусственного базиса

Если  ограничения   задачи  линейного  программирования  содержат  единичную  матрицу  порядка  m, то  тем  самым  при  неотрицательных  правых  частях  уравнений  определен  первоначальный  план, исходя  из  которого  с  помощью  симплексного  метода  находится  оптимальный  план..

{spoiler=Подробнее}

Если  ограничения  задачи  линейного  программирования  можно  преобразовать к виду   АХ £ А0  при  А0 ³ 0, то  система  ограничений  всегда  содержит  единичную  матрицу . Многие  задачи  линейного  программирования , имеющие  решения ,  не  содержат  единичной  матрицы  и  не  приводятся  к указанному  виду . В этом случае  для  решения   задач   применяется  метод  искусственного  базиса . Рассмотрим  общую  задачу  линейного  программирования .

Найти минимальное значение линейной функции  Z=C1x1+C2x2+  +... + Cnxn+Mxn+1+...+Mxn+m при ограничениях

xj    (j=1,2,...,n+m),

Величина М предполагается достаточно большим положительным числом, если задача решается на отыскание минимального значения линейной функции, и достаточно малым отрицательным числом, если находится максимальное значение линейной функции. Единичные векторы

Аn+1, Аn+2, ...., Аn+m,

соответствующие искусственным переменным, образуют искусственный базис.

Для отыскания оптимального плана исходной задачи используют следующую теорему.

Теорема.  Если в оптимальном плане Х=(х12,... , хn, 0, 0, ... ,0) расширенной задачи искусственные переменные хn+i=0(i = 1,2, ... ,m), то план Х=(х1, х2, ... ,хn)  является оптимальным планом исходной задачи.

Пример. Найти максимальное значение линейной функции Z=5x1+3x2+4x3-x4 при ограничениях

xj>=0 (j=1,2,3,4).

Решение. Система ограничение не содержит единичной матрицы. Прибавим к каждому уравнению по одной неотрицательной искусственной переменной (соответственно x5³ 0, x6³0) и перейдём к расширенной задаче.

Найти максимальной  значение линейной функции

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

xj>=0 (j=1,2,3,4,5,6).

или векторной форме:

A1x1+A2x2+A3x3+...+A6x6=A0

Выберем за базис единичные векторы А5, А6, которые и образуют искусственный базис. Приравнивая свободные неизвестные нулю: x1=x2=x3=x4=0, получаем первоначальный опорный план расширенной задачи:

Х0=(0:0:0:0:3:3), которому соответствует разложение х5А56А60.

Составим симплексную таблицу (табл.) в которой m+2 строки, и по оценкам, содержащимся в ней, проверим план на оптимальность.

Значения оценок, записанных в (m+1)-й и в (m+2)-й строках, находим по формулам.

Z(X0)=CбазX0=3M3M+0=06M,

Z1C1=CбазX1C1=M2M5=53M,

Z2C2=CбазX2C2=3M2M2=35M, и. т. д.,

т.е. если M заранее не фиксировано, то оценки Zj-Cj являются линейным функциями величины М, причем функция состоит из двух слагаемых, одно из которых зависит от М, а второй -не зависит.

Для удобства вычислений в (m+1) -ю строку - коэффициенты при М, которые позволяют сравнивать оценку между собой. В (m+2) -й строке отрицательные оценки, поэтому опорные план Х0 расширенной задачи не являются оптимальным и его можно улучшить.

базис с базиса A0 5 3 4 -1 -M -M
A1 A2 A3 A4 A5 A6
1 A5 M 3 1 3 2 2 1 0
2 A6 M 3 2 2 1 1 0 1
m+1 0 -5 -3 -4 1 0 0
m+2 -6 -3 -5 -3 -3 0 0

Вычислим max 0oj(Zj-Cj), которое достигается для вектора A2; 002(Zj-Cj),=3/3×(-5)=-5. Разрешающий элемент число 3, вектор А2 включаем в базис, вектор А5- исключаем.

Составим симплексную таблицу (табл.). для этого разделим элементы направляющей строки на 3 и произведем одно полное исключение.

В результате второй итерации с разрешающим элементом 4/3 из базиса исключен последний искусственный вектор А6, поэтому в  (m+2)-й строке третьей итерации все оценки, кроме оценок двух искусственных векторов, обратились в нуль.

В силу выбора величины М векторы А5 и А6 уже не могут попасть в базис, исключаем их из дальнейшего рассмотрения, но сохраним для получения обратной матрицы.

Опорной план 3/4;3/4;0;0;0;0;), полученные в третьей итерации, являются планом исходной задачи, и не оптимальным, так как в (m+1) -й строке имеется отрицательная оценка Z2-C3=-3<0.

Дальнейший итерационный процесс проводим по (m+1) -й строке, (m+2)-ю строку из дальнейшего рассмотрения исключаем, а величину М включаем в оценки искусственных векторов. В четвертой итерации находим оптимальный план исходной задачи: Х=(1;0;1;0); при этом плане Zmax(x)=9. В столбцах А5 и А6 получено матрица, из которой можно получить обратную, поменяв местами первую и вторую строки.

Принимая во внимание, что если  система ограничений задачи линейного программирования содержит единичный базис, то для решения задачи необходимо примерно m итераций; если  же для получения первоначального опорного плана необходимо ввести полный искусственный базис, то количество итераций увеличивается приблизительно до 2m.


5 3 4 -1
1 A2 3 1 1/3 1 2/3 2/3 1/3 0
2 1 4/3 0 -1/3 -1/3 -2/3 1
m+1 3 -4 0 -2 3 1 0
m+2 -1 -4/3 0 1/3 1/3 5/3 0
1 A2 3 3/4 0 1 3/4 ¾ 1/2 -1/4
2 A1 5 3/4 1 0 -1/4 -1/4 -1/2 3/4
m+1 6 0 0 -3 2 -1 3
m+2 0 0 0 0 0 1 1
1 A3 4 1 0 4/3 1 1 2/3 -1/3
2 A1 5 1 1 1/3 0 0 -1/3 2/3
m+1 Zi-Cj 9 0 4 0 5 1+M 2+M

При решений  определенной экономической задачи, по характеру которой известно, что она обладает планами и в процессе решения не требуется получения обратной матрицы, количество вводимых искусственных векторов можно значительно сократить, если используя метод полного исключения,  сначала включить в базис линейно независимые векторы из имеющийся системы векторов А12, ... ,Аn.

{/spoilers}

Комментарии (0)
Комментировать
Кликните на изображение чтобы обновить код, если он неразборчив
Copyright © 2024 г. openstudy.uz - Все права защищены.