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

Особенности алгоритма метода искусственного базиса

Алгоритм метода искусственного базиса имеет следующие особенности:

1. Ввиду того, что начальное опорное решение расширенной задачи содержит искусственные переменные, входящие в целевую функцию с коэффициентом —М (в задаче на максимум) или +М (в задаче на минимум), оценки разложений векторов условий состоят из двух слагаемых и , одно из которых не зависит от М, а другое зависит от М. Так как М скольугодно велико по сравнению с единицей (М>>1), то на первом этапе расчета для нахождения векторов, вводимых в базис, используются только слагаемые оценок .

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

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

4. Переход от решения расширенной задачи к решению исходной задачи производится с использованием доказанных выше теорем 4.1-4.3.

Пример 4.4. Решить задачу линейного программирования методом искусственного базиса

.

Решение. Составляем расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом (всегда) +1. Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим , во второе — . Данная задача — задача на нахождение максимума, поэтому и в целевую функцию вводятся с коэффициентом — М. Получаем

Задача имеет начальное опорное решение с единичным базисом .

Пример решения задачи методом искусственного базиса.

Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении.

. .

Записываем исходные данные в симплексную таблицу (табл. 4.6).


Т а б л и ц а 4.6

При этом оценки и для удобства вычислений записываем в две строки: в первую — слагаемые , не зависящие от М, во вторую — слагаемые , зависящие от М. Значения удобно указывать без М, имея в виду однако, что оно там присутствует.

Начальное опорное решение не является оптимальным, так как в задаче на максимум имеются отрицательные оценки. Выбираем номер вектора , вводимого в базис опорного решения, и номер вектора , выводимого из базиса. Для этого вычисляем приращения целевой функции при введении в базис каждого из векторов с отрицательной оценкой и находим максимум этого приращения. При этом слагаемыми оценок (без М) пренебрегаем до тех пор, пока хотя бы одно слагаемое М) не будет отлично от нуля. В связи с этим строка со слагаемыми оценок может отсутствовать в таблице до тех пор, пока присутствует строка . Находим при k = 3.

В третьем столбце " " за разрешающий элемент выбираем коэффициент 1 во второй строке и выполняем преобразование Жордана.

Вектор , выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем опорное решение с базисом (табл. 4.7). Решение не является оптимальным так как имеется отрицательная оценка = 1.

Т а б л и ц а 4.7

В столбце " " единственный положительный элемент принимаем за разрешающий и переходим к новому опорному решению с базисом (табл. 4.8).


Т а б л и ц а 4.8

Данное опорное решение является единственным оптимальным решением расширенной задачи, так как в задаче на максимум оценки для всех векторов, не входящих в базис, положительны. По теореме 4.1 исходная задача также имеет оптимальное решение, которое получается из оптимального решения расширенной задачи отбрасыванием нулевых искусственных переменных, т. е. Х* = (0,0,6,2).

Ответ: max Z(X) = -10 при .

Пример 4.5. Решить методом искусственного базиса задачу линейного программирования со смешанными ограничениями

Решение. Приводим задачу линейного программирования к каноническому виду. Для этого вводим дополнительные переменные и в первое и третье ограничения соответственно. Получаем

.

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

.

Данная расширенная задача имеет начальное опорное решение

с единичным базисом , . Вычисляем оценки векторов условий по базису опорного решения и записываем в симплексную таблицу так же, как в предыдущем примере. Решение не является оптимальным, так как в задаче на минимум векторы и имеют положительные оценки . Улучшаем опорные решения. Каждому опорному решению соответствует своя таблица. Все таблицы можно записать друг под другом, объединив в единую таблицу (табл. 4.9).

Т а б л и ц а 4.9

Определяем, введение какого из векторов или в базис начального опорного решения приведет к большему уменьшению целевой функции. Находим при k = 2, т. е. лучше ввести в базис вектор . Получаем второе опорное решение с базисом . Целевая функция . Это решение также не является оптимальным, так как вектор имеет положительную оценку . Вводим вектор в базис, получаем третье опорное решение с базисом . Целевая функция . Это решение оптимальное, но не единственное, так как вектор , не входящий в базис, имеет нулевую оценку. Поэтому необходимо перейти к новому опорному решению, которое также будет оптимальным. Для этого требуется ввести в базис вектор .

Переходим к четвертому опорному (оптимальному) решению

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

Ответ: при , , , .

Слово симплекс

Слово симплекс английскими буквами(транслитом) — simpleks

Слово симплекс состоит из 8 букв: е и к л м п с с

Значения слова симплекс. Что такое симплекс?

Симплекс

Симплекс (от лат. simplex — простой) (математический), простейший выпуклый многогранник данного числа измерений n. При n = 3 трёхмерный С. представляет собой произвольный, в том числе неправильный, тетраэдр.

БСЭ. — 1969—1978

Симплекс — выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. С. выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости.

slovar-lopatnikov.ru

СИМПЛЕКС — выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. С. выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости.

Лопатников. — 2003

Саб симплекс

Саб симплекс Способ применения и дозы: Внутрь, во время или после еды и, при необходимости, перед сном. Перед применением следует активно встряхнуть флакон.

Решение ЗЛП симплекс методом с искусственным базисом

Чтобы суспензия начала поступать из пипетки…

РЛС. — 2012

Саб симплексДействующее вещество ›› Симетикон* (Simethicone*) Латинское название Sab simplex АТХ:›› A02DA Ветрогонные препараты Фармакологическая группа…

Словарь медицинских препаратов. — 2005

САБ® СИМПЛЕКС (SAB® SIMPLEX) Суспензия для приема внутрь от белого до серо-белого цвета, слегка вязкая, с характерным фруктовым (ванильно-малиновым) запахом. 100 мл симетикон 6.919 г…

Справочник лекарственных препаратов "Видаль"

ШОКЕ СИМПЛЕКС

ШОКЕ СИМПЛЕКС — непустое компактное выпуклое множество Xв локально выпуклом пространстве E, обладающее следующим свойством: при вложении Ев качестве гиперплоскости в пространство проектирующий конус.

Математическая энциклопедия. — 1977-1985

Шеффилд-Симплекс

«Шеффилд-Симплекс» (англ. Sheffield-Simplex) — лёгкий пулемётный бронеавтомобиль Вооружённых сил Российской империи. Разработан британской фирмой «Sheffield-Simplex» на базе шасси собственного легкового автомобиля…

ru.wikipedia.org

Нордитропин Симплекс

Нордитропин Симплекс Показания: Задержка роста у детей вследствие недостаточности гормона роста или хронической почечной недостаточности (в препубертатном возрасте), синдрома Шерешевского — Тернера…

РЛС. — 2012

НОРДИТРОПИН® СИМПЛЕКС® (NORDITROPIN SimpleXx) Раствор для п/к введения 1.5 мл (1 картридж) соматропин 10 мг 1.5 мл — картриджи (1) — упаковки ячейковые контурные (1) — пачки картонные.

Справочник лекарственных препаратов "Видаль"

СТАНДАРТНЫЙ СИМПЛЕКС

СТАНДАРТНЫЙ СИМПЛЕКС — 1) С. с.- симплекс размерности пв пространстве с вершинами в точках е i=(0,…, 1,…, 0), i=0,…, п(единица стоит на i-м месте), т. е.

Математическая энциклопедия. — 1977-1985

Двойственный симплекс-метод

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

ru.wikipedia.org

Русский язык

Си́мпле́кс/.

Морфемно-орфографический словарь. — 2002

Поиск Лекций

Пример решения задачи методом искусственного базиса.

Найти минимум функции F=-2×1+3×2 — 6×3 — x4 при условиях

Решение. Запишем данную задачу в форме основной задачи: найти максимум функции F1=2×1 – 3×2 + 6×3 + x4 при условиях

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

А1= А2= А3= А4= А5= А6=

Среди векторов А1,…, А6 только два единичных (А4 и А5). Поэтому в левую часть третьего уравнения системы ограничений добавим дополнительную неотрицательную переменную x7 и рассмотрим расширенную задачу, состоящую в максимизации функции

F=2×1 – 3×2 + 6×3 + x4 – Mx7

при условиях

Расширенная задача имеет опорный план X=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: А4 , А5 , А7 .

Таблица 1

i Базис Сσ А0 -3 M
А1 А2 А3 А4 А5 А6 P7
А4 -2
А5
А7 M -1 -1
m+1   -8
m+2     -10 -1 -2

Составляем таблицу (1) I итерации, содержащую пять строк. Для заполнения 4-й и 5-й строк находим F0 и значения разностей zj – cj (j= ):

F0 = 24–10M;

z1–c1= 0–M;

z2–c2 = 4+M;

z3–c3= –8–2M;

z4–c4=0+M;

z5–c5=0+M;

z6–c6= 0+M;

z7–c7=0+M;

Значения F0 и zj–cj состоят из двух слагаемых, одно из которых содержит M, а другое – нет.

Для удобства итерационного процесса число, состоящее при M, записываем в 5-й строке, а слагаемое, которое не содержит M,– в 4-й строке.

В 5-й строке табл.1 в столбцах векторов Аj (j= ) имеется два отрицательных числа (-1 и -2). Наличие этих чисел говорит о том, что данный опорный план расширенной задачи не является оптимальным. Переходим к новому опорному плану расширенной задачи.

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

В базис вводим вектор А3. Чтобы определить вектор, исключаемый из базиса, находим θ=min(22/4; 10/2)=10/2. Следовательно, вектор А7исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейшем столбец данного вектора не заполняется (табл. 2 и 3).

Составляем таблицу II итерации (табл. 2). Она содержит только четыре строки, так как искусственный вектор из базиса исключен.

Таблица2

i Базис Сσ А0 -3
А1 А2 А3 А4 А5 А6
А4 -1
А5 -1
А3 1/2 -1/2 -1/2
m+1     -4

Как видно из табл. 2, для исходной задачи опорным является план Х=(0;0;5;34;2).

Проверим его на оптимальность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора А6 имеется отрицательное число (-4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора А6. Из базиса исключается вектор А5. Составляем таблицу III итерации.

Таблица 3

i Базис Сσ А0 -3
А1 А2 А3 А4 А5 А6
А4 5/2 1/2
А6 -1/2 1/2
А3 11/2 ¼ 1/2 1/4
m+1    

В 4-й строке табл.3 среди чисел ∆j нет отрицательных. Это означает, что найденный новый опорный план исходной задачи Х*=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы Fmax = 68.

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

©2015-2018 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

admin