Сайт о телевидении

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

Для многих задач линейного програм­мирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов P j не всегда есть m единичных.

Рассмотрим такую задачу:

Пусть требуется найти максимум функции

F = c 1 x 1 + c 2 x 2 + ……+ c n x n (1)

при условиях

……………………………………… (2)

где b i  0 (i =l, m), m <.>n и среди векторов P 1 , P 2 , …, P n нет m единичных.

Определение . Задача, состоящая в определении максимального значения функции

F = c 1 x 1 + c 2 x 2 + ……+ c n x n -М x n +1 - …- М x n + m (3)

при условиях

……………………………………… (4)

где M - некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей (М-задачей) по отношению к задаче (1) - (2).

Расширенная задача имеет опорный план

Х=(0; 0; ...; 0; b 1 ; b 2 ; ...;b m).

определяемых системой единичных векторов P n +1 ; Р п+2 , … Р п+т , образующих базис m-ro векторного пространства, который назы­вается искусственным. Сами векторы, так же как и переменные x n + i (i =l, m ), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Теорема Если в оптимальном плане X*=(x* 1 , x * 2 , ...; x * n , x * n +1 ; ...; x * n + m) расширенной задачи (3) - (4) значения ис­кусственных переменных x * n + i =0 (i =1, m ), то X*=(x* 1 , x * 2 , ...; x * n) является оптимальным планом задачи (1) - (2).

Таким образом, если в найденном оптимальном плане расши­ренной задачи, значения искусственных переменных равны ну­лю, то тем самым получен оптимальный план исходной задачи.

Значения индексной строки ∆ 0 , ∆ 1 , …, ∆ n состоят из двух частей, одна из кото­рых зависит от M, а другая - нет. Заполняют симплекс - таблицу, которая содер­жит на одну строку больше, чем обычная симплексная табли­ца. При этом в (m+2)-ю строку помещают коэффициенты при M, а в (m+1)-ю – слагаемые, не содержащие M. При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m+2)-й строки. Искусствен­ный вектор, исключенный из базиса, в следующую симплекс-таблицу не записывают. Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

Итерационный процесс по (m+2) -и строке ведут до тех пор, пока:

либо все искусственные векторы не будут исключены из базиса;

либо не все искусственные векторы исключены, но (m+2)-я строка не содержит больше отрицательных элементов в индексах ∆ 1 , …, ∆ n .

В первом случае базис отвечает некоторому опорному пла­ну исходной задачи и определение ее оптимального плана про­должают по (m+1)-й строке.

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

Этапы нахождения решения задачи (1) - (2)

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

Составляют расширенную задачу (3) - (4).

Находят опорный план расширенной задачи.

С помощью обычных вычислений симплекс-метода исклю­чают искусственные переменные из базиса. В результате либо на­ходят опорный план исходной задачи (1) - (2), либо уста­навливают ее неразрешимость.

Используя найденный опорный план задачи (1) - (2), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

Пример.

Найти минимум функции F = - 2x 1 + 3x 2 - 6x 3 - x 4

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

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 ≤22

x 1 -x 2 +2x 3 ≥10

x i ≥0, i =1,4

Решение.

Запишем данную задачу в форме основной задачи: найти максимум функции F = 2x 1 - 3x 2 + 6x 3 + x 4

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

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6= 10

x i ≥0, i =1, 6

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

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

F = 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7

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

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6 +x 7= 10

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

Понятие двойственной (соапряженной) задачи линейного программирования.

Правила построения двойственной задачи.

С каждой задачей линейного программирования (ЗЛП), которая называется двойственной задачей (или сопряженной) по отношению к исходной задаче, которая называется прямой.

Двойственная задача строится по отношению к прямой задаче, записанной в стандартной форме:

F=c 1 x 1 +c 2 x 2 +…+c n x n  max (3.6)

a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1 ,

a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2 ,

………………………………

a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)

a k+1,1 x 1 +a k+1,2 x 2 +…+a k+1,n x n =b k+1 ,

………………………………

a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,

x j ≥ 0, , l ≤ n (3.8)

Задача, состоящая в нахождении минимального значения функции

L = b 1 y 1 + b 2 y 2 + … + b m y m (3.9)

при условиях

a 11 y 1 + a 12 y 2 +…+ a m1 y m ≥ c 1

a 21 y 1 + a 22 y 2 +…+ a m2 y m ≥ c 2

………………………………

a 1 l y 1 + a 2 l y 2 +…+ a m l y m ≥ c l (3.10)

a l +1,1 y 1 + a l +1,2 y 2 +…+ a l +1,m y m = c l+1

………………………………

a m1 y 1 + a m2 y 2 +…+ a mn y m = c m

y i ≥ 0, , k ≤ m (3.11)

называется двойственной по отношению к задаче (3.6) – (3.8).

Правила построения двойственной задачи приведены в таблице:

Структурные характеристики ЗЛП	Задача линейного программирования
		Двойственная
1. Целевая функция	Максимизация (max)	Минимизация (min)
2. Количество переменных	n переменных	Равно количеству ограничений прямой задачи (3.7), y i , т.е. m
3. Количество ограничений	m ограничений	Равно количеству переменных прямой задачи x j , , т.е n
4. Матрица коэффициентов в системе ограничений
5. Коэффициенты при переменных в целевой функции	c 1 ,c 2, …,c n	b 1 ,b 2, …,b m
6. Правая часть системы ограничений	b 1 ,b 2, …,b m	c 1 ,c 2, …,c n
7. Знаки в системе ограничений	а) x j ≥ 0- условие неотрицательности	j-е ограничение имеет знак «≥»
	б) на переменную x j не наложено условие неотрицательности	j-е ограничение имеет знак «=»
	в) i-е ограничение имеет знак «≤»	переменная y i ≥0
	г) i-е ограничение имеет знак «=»	на переменную y i не наложено условие неотрицательности

Примечание

Прямая задача на максимум и двойственная на минимум являются взаимодвойственными задачами. Поэтому можно считать задачу (3.9) – (3.11) прямой ЗЛП, а задачу (3.6) – (3.8) – двойственной к ней задачей. При этом правила построения двойственной ЗЛП сохраняются, лишь с тем изменением, что исходной считается задача на минимум.

Если исходная задача решается на max (min), а в системе ограничений) i -е (j -е) ограничение имеет знак «≤» («≥»), то для построения двойственной задачи необходимо:

а) либо домножить обе части i -го (j -го) неравенства на (-1) и поменять знак на «≤» («≥»)

б) либо привести i -е (j -е) ограничение к равенству путем введения дополнительной переменной x n+ i ≥0

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

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

Саб симплекс

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

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

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

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

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

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

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

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

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

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

ru.wikipedia.org

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

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

НОРДИТРОПИН® СИМПЛЕКС® (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). Поэтому в левую часть третьего уравнения системы ограничений добавим дополнительную неотрицательную переменную x 7 и рассмотрим расширенную задачу, состоящую в максимизации функции

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-й строк находим F 0 и значения разностей zj – cj (j= ):

F 0 = 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 ;

Значения F 0 и 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

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

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

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

Когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:

max{F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» R j следующим образом:

∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c i x i , а другая – для составляющей M ∑R j Рассмотрим процедуру решения задачи на конкретном примере.

Пример 1. Найти максимум функции F(x) = -x 1 + 2x 2 - x 3 при ограничениях:

2x 1 +3x 2 +x 3 =3,

x 1 ≥0, x 2 ≥0, x 3 ≥0 .

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

2x 1 + 3x 2 + x 3 + R 1 = 3;

x 1 + 3x 3 + R 2 = 2 ;

Функция цели F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).

Выразим сумму R 1 + R 2 из системы ограничений: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , тогда F(x) = -x 1 + 2x 2 - x 3 - M(5 - 3x 1 - 3x 2 - 4x 3) .

При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x 1 , x 2 , x 3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.

Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x 3 , которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R 2 должна быть из базиса исключена. Ведущий элемент обведен контуром.

В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:

x 1 =0; x 2 =7/9; F max =8/9.

Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥

Пример 2 . Найти минимальное значение функции F(x) = 2x 1 + 3x 2 - x 3 при следующих ограничениях

2x 1 +x 2 -3x 3 ≥6,

x 1 -x 2 +2x 3 =4,

x 1 +x 2 +x 3 ≤5,

x 1 ≥0, x 2 ≥0, x 3 ≥0 .

Домножим первое из ограничений на (-1) и введем в ограничения дополнительные переменные x 4 , x 5 и искусственную переменную R следующим образом:

2x 1 -x 2 +3x 3 +x 4 =-6,

x 1 -x 2 +2x 3 +R=4,

x 1 +x 2 +x 3 +x 5 =5,

Пусть x 4 , R и x 5 – базисные переменные, а x 1 , x 2 , x 3 – небазисные. Функция цели F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).

В первой (табл. 4.) коэффициенты при небазисных переменных в F-строке и M-строках знака не меняют, так как осуществляется минимизация функции. Свободный член в методе искусственного базиса в M-строке берется с противоположным знаком. Решение, соответствующее табл. 4, не является допустимым, так как есть отрицательный свободный член.

Выберем ведущий столбец и строку в соответствии с шагом 2 алгоритма решения. После пересчета получим табл. 5. Оптимизация решения в методе искусственного базиса (шаг 5 алгоритма) осуществляется вначале по M-строке. В результате x 3 введем в базис, а переменную R исключим из рассмотрения, сократив количество столбцов. После пересчета получим табл. 6, которая соответствует оптимальному решению задачи.

Таблица 4

базисные переменные	Свободные члены	Небазисные переменные
		x 1	x 2	x 3
x 4	-6	-2	-1	3
R	4	1	-1	2
x 5	5	1	1	1
F	0	2	3	-1
M	-4	-1	1	-2

Таблица 5

базисные переменные	Свободные члены	Небазисные переменные
		x 4	x 2	x 3
x 1	3	-1/2	1/2	-3/2
R	1	1/2	-3/2	7/2
x 5	2	1/2	1/2	5/2
F	-6	1	2	2
M	-1	-1/2	3/2	-7/2

Таблица 6

Искомый минимум функции F(x) равен свободному члену F-строки табл. 6, взятому с обратным знаком, так как min F(x) = -max(-F(x)); x 4 = x 2 = 0;

x 1 =24/7; x 3 =2/7; x 5 =9/7; F min =46/7;

Решение системы производится путём ввода искусственных переменных R i со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом ).

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной . Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные (x n+m) и искусственные (R i)- базисными.

Исходная таблица для "Метода искусственного базиса" имеет следующий вид:

	x 1	x 2	...	x n-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1,1	a 1,2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2,1	a 2,2	...	a 2,n-1	a 2,n	b 2
R i	a i,1	a i,2	...	a i,n-1	a i,n	b i
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m
M	-∑a i,1	-∑a i,2	...	-∑a i,n-1	-∑a i,n	-∑b i

Элементы дополнительной строки M расчитываются как сумма соответствующих коэффициентов условий-равенств (условий в которые после приведения к каноническому виду введены переменные R i) взятая с противоположным знаком.

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

Подготовительный этап

Приводим задачу ЛП к каноническому виду

F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1

a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2

.........................................

a i,1 x 1 +a i,2 x 2 +...a i,n x n +R i =b i

.......................................

a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, x n+m , к каждому i-му условию-равенству добавляем искусственную переменную R i .

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

	x 1	x 2	...	x n-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1,1	a 1,2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2,1	a 2,2	...	a 2,n-1	a 2,n	b 2
R i	a i,1	a i,2	...	a i,n-1	a i,n	b i
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m
M	-∑a i,1	-∑a i,2	...	-∑a i,n-1	-∑a i,n	-∑b i

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно .

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

Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

Шаг 2. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строках M и F(не беря в расчет элемент b 0 - текущее значение целевой функции и элемент -∑b i) нет отрицательных, то найдено оптимальное решение.

2.1 Положительность строки M

Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑b i)

При a i,l >0, b i >0

Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2

Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2 .

2.2 Положительность строки F

Проверяем на положительность элементы строки F. Если имеются отрицательные элементы (не считая b 0), выбираем среди отрицательных элементов строки F максимальный по модулю.

-a 0,l =min{-a 0,i }

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

b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0

k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.

Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

Метод искусственного базиса (или метод “М”) может быть применен для решения задачи ЛП, если ее система ограничений, помимо неравенств смысла “≤” имеет неравенства смысла “≥” или строгие равенства. Рассмотрим задачу ЛП, заданную в самом общем виде.

Найти экстремум функции

Алгоритм метода «М».

1. От системы неравенств переходим к системе уравнений, вводя дополнительные неотрицательные переменные:

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

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

4. Строим расширенную М – задачу ЛП:

найти экстремум линейной формы

при следующих ограничениях:

Найдем первоначальный опорный план М – задачи.

Так как дополнительные неотрицательные переменные и искусственные переменные входят в ограничения с положительными единичными коэффициентами, которые составляют систему линейно-независимых векторов как столбцы единичной матрицы, то упомянутые переменные будут являться базисными, а все остальные – свободными, т.е.

Тогда первоначальный опорный план будет иметь вид:

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

Проверяется признак оптимальности по (m+2)-й строке и определяется переменная, подлежащая включению в базис. Симплекс-процедуру по (m+2) индексной строке проводят до тех пор, пока по этой строке не будет выполнен признак оптимальности. Затем процесс отыскания оптимального плана продолжают по (m+1) индексной строке.

7. Анализируем оптимальный план М – задачи. Если в этом плане все искусственные переменные равны нулю, т.е. то план X(x 1 , x 2 , …, x n) является оптимальным планом исходной задачи. Если же в оптимальном плане М – задачи хотя бы одна искусственная переменная не равна нулю, т.е. то исходная задача решения не имеет.

Если в процессе решения М – задачи устанавливаем ее не разрешимость, то неразрешима и исходная задача.

Решение контрольного примера.

Найти минимум функции

при следующих ограничениях:

1. От системы неравенств переходим к системе уравнений, вводя в 1-е и во 2-е ограничения дополнительные неотрицательные переменные x 4 и x 5 . Третье уравнение переписываем без изменения:

2. Во 2-е и 3-е уравнения вводим искусственные переменные y 1 и y 2:

3. В линейную форму L(X) вводим сумму y 1 +y 2 с множителем М. Так как задача поставлена на минимум, то множитель М берем со знаком «+».

4. Строим М – задачу. Найти минимум линейной формы

при следующих ограничениях:

5. Решаем эту задачу симплекс-методом. Так как x 4 , y 1 , y 2 являются базисными переменными, то выражаем их через свободные и подставляем в функцию L(X):

6. Строим симплекс-таблицу, которая имеет две индексные строки: в первую, как обычно, записываются коэффициенты Cj, взятые с противоположным знаком, а во вторую – соответствующие коэффициенты при множителе М (тоже с обратным знаком, кроме свободного члена).

Проверяем признак оптимальности по (m+2) индексной строке. Так как задача на минимум, то признак не выполнен, поскольку в столбце x 2 находится положительный элемент 4. Отмечаем этот ключевой столбец стрелкой и , как обычно, выбираем ключевую строку. При выборе ключевой строки получили два одинаковых наименьших значения θ. Чтобы избежать зацикливания, применяем правило Креко. Строки x 1 и y 1 делим на соответствующие элементы ключевого столбца 2 и 4. Результаты от деления читаем слева направо, и ту строку, где первым встретится меньшее число, выбираем за ключевую, т.е.

Отмечаем строку y 1 стрелкой и находим генеральный элемент 4. Затем выполняем обычную симплекс-процедуру и получаем вторую таблицу (таблица 1.2.), в которой опять анализируем (m+2)-ю индексную строку и выбираем столбец x 3 за ключевой.

В результате построения третьей таблицы (таблица 1.2.) получаем оптимальный план расширенной задачи так как по обеим индексным строкам признак оптимальности выполнен.

Вследствие того, что все искусственные переменные выведены из базиса, оптимальным планом исходной задачи является план и

Для рассматриваемой задачи можно построить второе оптимальное решение с тем же самым значением L min =24 (таблица 1.2.). Следовательно, задача имеет множество оптимальных планов где

Таблица 1.2.

№ таблиц	Базисные переменные	Свободные члены	X 1	X 2	X 3	X 4	X 5	å	Q
	X 4				-4
Y 1		-1		-2		-1
Y 2								-
L(X)		-1	-2	-2			-5	Min
		4­			-1		-
	X 4		7/2		-3		1/2		-
X 2		-1/4		-1/4		-1/4		-
Y 2
L(X)		-3/2		-3		-1/2		Min
			2­
	X 3		1/2					15/2
X 2						-1/4	27/4	-
X 4						1/2	49/2	18/5
L(X)						-1/2	47/2	Min
	X 3	21/5			-1/10		-1/20	101/20
X 2						-1/4	27/4
X 4	18/5			1/5		-1/10	49/10
L(X)						-1/2	47/2	min