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

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

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;

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

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
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

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

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

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

Пример 1

Найти максимум Z=4X1+2X2+X3

3Х1+2Х2+Х3=15

Хj³0, j=1,...,3

Переходим к канонической форме:

Х1+Х2+Х3-Х4=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3=15

Хj³0, j=1,...,5

Zmax=4X1+2X2+X3+0×X4+0×X5

Данная система ограничений не имеет единичного базиса, так как дополнительная переменная Х4 имеет коэффициент минус единица, а третье ограничение было представлено уравнением и в нем отсутствует базисная переменная. Для того, чтобы был единичный базис вводим в соответствующие ограничения искусственные переменные y1 и y2 с положительными коэффициентами (+1).

Следует отметить, что искусственные переменные вводятся только для математической формализации задачи. Поэтому схема вычислений должна быть такой, чтобы искусственные пременные не могли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например, 10000. Причем, при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум – со знаком плюс. Теперь будем решать Т (М)-задачу, целевая функция которой содержит целевую функцию Z–задачи и искусственные переменные с коэффициентом ±М, т.е.

T=Z-M S yi, при решении на максимум целевой функции и

T=Z+M S y, при решении на минимум целевой функции

В нашем случае:

Х1+Х2+Х3-Х4+y1=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3+y2=15

Хj³0, j=1,...,5

Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)

Эта задача решается в симплексных таблицах, но для удобства целевую функцию разбивают на 2 строки:

В первую строку записываем оценки, которые не содержат коэффициент М;

Во вторую строку- оценки по каждой свободной переменной, содержащие коффициент М.

Расчет элементов (оценок) этих двух строк производится по формуле (2). Только отличие:

При расчете оценок Z -строки должны быть учтены коэффициенты Cj , входящие в функцию Z ;

При расчете оценок М-строки этот коэффициент во внимание не берется, а М -выносится как общий множитель.

Для того, чтобы Т-задача и Z-задача были равны, нужно, чтобы yi были равны нулю. Поэтому пока y i не равно нулю, разрешающий столбец выбирается по оценкам во второй строке, используя алгоритм симплексного метода.

Лишь после того, как все y i станут равны нулю, дальнейший расчет будет вестись по первой индексной строке, т.е. -обычная Z-задача.

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

Между оптимальными решениями М-задачи и Z-задачи существует связь, устанавливаемая следующей теоремой:

1. Если в оптимальном решении М-задачи все искусственные переменные (y i) равны нулю, то это решение будет являться оптимальным решением Z-задачи.

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

3. Если М-задача оказалась неразрешимой (Т®+¥ или-¥), то исходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции Z.

Составим первую симплексную таблицу. При решении М-методом разрешающий столбец можно выбирать в М-строке не по наибольшей по абсолютной величине отрицательной оценке (при решении на максимум) и не по наибольшей положительной оценке (при решении на минимум), а по той из них, которая быстрее выводит У из базиса. В данном примере разрешающим столбцом будет столбец свободной переменной X2 с оценкой (-3).

Таблица 3.1.

Первая симплексная таблица

Заполнение Z- строки осуществляется по формуле (2):

а00 = 0 × 8– 0 = 0

а01 =0 × 2– 4 = -4

а02 =0 × 1– 2 = -2

а03 =0 × 1– 1 = -1

а02 =0 × 0– 0 = 0

Заполнение М- строки:

а¢00 = -М × 8 + (–М) × 15 = -23М

а¢01 = -М × 1 + (–М) × 3= -4М

а¢02 = -М × 1 + (–М) × 2= -3М

а¢03 = -М × 1+ (–М) × 1 = -2М

а¢04 = -М ×(-1)+ (–М) × 0 = 1М

М выносим как общий множитель.

В последнем столбце в разрешающей строке стоит 0, поэтому столбец свободной переменной X4 переносим без изменений.

Таблица 3.2.

Вторая симплексная таблица

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

Таблица 3.3.

Третья симплексная таблица

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

Таблица 3.4.

Четвертая симплексная таблица

Св.П	Cj
Б.П.	Ci	ai0	X5	X4
Х3				-1
X1
Х2			-2	-1
Z

В оценочной строке все элементы являются неотрицательными величинами, следовательно получено оптимальное решение:

Zmax=15 Xopt(0,7,1,0,0)

Пример2

Задача решалась на минимум (Z®min) целевой функции. На последней итерации получили следующую таблицу:

Таблица 3.5.

Последняя симплексная таблица

Св.П	Cj
Б.П.	Ci	ai0	X1	X3	X4
У1	М	-1/2	-1/2	-1/2	-1
X5		1/2	1/2	1/2
Х2		15/2	3/2	1/2
Z			-1
	М	-1/2	-1/2	-1/2	-1

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

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Предупреждение

Очистить все ячейки?

Закрыть Очистить

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

Правая часть ограничений системы уравнений имеет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x при . min (40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x 3 . Сделаем исключение Гаусса для столбца x 2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x 1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x 4 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F (X )=.

Пример 2. Найти максимум функции

Р е ш е н и е.

Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x 2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x 2 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x 3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x 5 . Сделаем исключение Гаусса для столбца x 3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

Пример 2. Найти оптимальный план задачи линейного программирования:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.