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

Размещено на http://www.allbest.ru/

Лекция

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

Содержание

1. Общая характеристика симплекс-метода и подготовка модели к решению

2. Алгоритм симплекс-метода

3. Особые случаи в симплекс-методе

1. Общая характеристика симплекс-метода и подготовка модели к решению

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

Весь путь решения задачи симплекс-методом условно можно разбить на три этапа.

I этап. Нахождение исходного варианта и исследование его на допустимость, т.е. получение начального опорного решения.

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

Если исходный вариант допустим, то опорное решение найдено и переходим на второй этап. Иначе, осуществляем перебор вариантов решения задачи до получения допустимого (если такое возможно. Если нет, то задача решения не имеет).

II этап. Исследования допустимого варианта на оптимальность.

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

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

III этап. Перебор вариантов решения задачи до получения оптимального варианта (если такое возможно. Если нет, то задача не имеет оптимального решения).

Сам симплекс-метод выбирать варианты не умеет, он только показывает направление перебора вариантов (в нашем случае позволяет осуществить выбор разрешающего элемента). Для расчёта же, в качестве вычислительного аппарата, привлекаются другие методы. Мы будем использовать метод модифицированных Жордановых исключений (МЖИ). Так как данный метод - это метод решения систем линейных уравнений, а модель представляет собой систему линейных неравенств, то модель предварительно должна быть подготовлена.

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

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

I. Z=c1x1+c2x2+…+cnxnmax.

II. y1=-a11x1-a12x2-…-a1nxn+b1;

y2=-a21x1-a22x2-…-a2nxn+b2;

ym=-am1x1-am2x2-…-amnxn+bm.

III. x10, x20, …, xn0.

Из этого вида данные заносятся в табличную форму для осуществления решения.

2. Алгоритм симплекс-метода

I этап: получение начального опорного решения.

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

Таблица 1 - Симплекс-таблица исходного варианта

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

Исходный вариант (по таблице 1):

1) основные переменные (xj): x1=0, x2=0,…, xn=0;

2) дополнительные переменные (yi): y1=b1, y2=b2,…, ym=bm;

3) Z=0.

Исследуем полученный вариант на допустимость.

Теорема о допустимости: в таблице будет находиться допустимый вариант решения задачи, если среди свободных членов не будет отрицательных (элемент на пересечение столбца свободных членов и строки Z при анализе во внимание не принимается).

Доказательство: свободные члены являются значениями базисных переменных, если среди базисных переменных есть xj, то они не могут быть отрицательными в силу условия неотрицательности (xj0). Если в базисе yi, то оно не должно быть отрицательным так как yi вводилась как разница между большей и меньшей частью неравенства.

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

- выбор разрешающей строки: среди отрицательных свободных членов (кроме строки Z), выбрать больший по абсолютной величине. Пусть это b2;

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

Наименьшее положительное из симплексных отношений укажет на столбец.

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

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

II этап: исследование допустимого варианта на оптимальность.

Теорема об оптимальности: в таблице будет находиться оптимальный вариант, если среди коэффициентов строки Z не будет отрицательных при Zmax и не будет положительных при Zmin (элемент на пересечение столбца свободных членов и строки Z при анализе во внимание не принимается).

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

Предположим, что наш допустимый вариант не оптимален.

III этап: нахождение оптимального варианта.

Попытаемся получить оптимальный вариант, выбрав разрешающий элемент по следующему правилу:

при Zmax:

- разрешающий столбец: среди отрицательных коэффициентов строки Z выбрать наибольший по абсолютной величине (например, пусть это cn);

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

…

Наименьшее положительное из симплексных отношений укажет на строку;

при Z min:

- разрешающий столбец: среди положительных коэффициентов строки Z выбрать наибольший (например, пусть это c1);

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

…

Наименьшее положительное из симплексных отношений укажет на строку.

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

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

3. Особые случаи в симплекс-методе

1. Неразрешимость модели (система неравенств не имеет решения).

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

2. Неограниченность функционала (функция не имеет экстремального значения).

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

3. Альтернативный оптимум.

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

4. Случай вырожденности.

В симплекс-таблице будет находиться вырожденный вариант, если среди свободных членов (кроме строки Z), появится ноль.

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

5. Смешанная система ограничений.

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

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

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

Размещено на Allbest.ru