Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Пермский государственный технический университет

Лысьвенский филиал

Кафедра ЕН

Курсовая работа

по дисциплине «Системный анализ и исследование операций»

по теме: «Симплекс метод в форме презентации»

Выполнил студент группы ВИВТ-06-1:

Старцева Н. С.

Проверил преподаватель:

Мухаметьянов И.Т.

Лысьва 2010г.

Введение. 3

Математическое программирование. 5

Графический метод. 6

Табличный симплекс – метод. 6

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

Модифицированный симплекс – метод. 7

Двойственный симплекс – метод. 7

Общий вид задачи линейного программирования. 9

Решение задачи линейного программирования симплекс-методом. 11

Вычислительные процедуры симплекс – метода. 11

Теорема 1: 13

Теорема 2: 14

Теорема 3: 15

Теорема 4: 15

Теорема 5: 15

Переход к новому опорному плану. 15

Двойственная задача. 17

Теорема 1 (первая теорема двойственности) 18

Теорема 2(вторая теорема двойственности) 18

Заключение. 20

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

7x 1 +5x 2 →max

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 первоначальный опорный план

x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

На интуитивном уровне понятно, что естественным будет увеличение x 1 , так как коэффициент при нем больше чем при x 2 . Оставляя x 2 =0, мы можем увеличивать до тех пор, пока x 3 , x 4 , x 5 , x 6 будут оставаться неотрицательными.

x 1 =min{19/2;13/2;∞;18/3}=6

Это означает что при x 1 =6, x 6 =0, то есть x 1 -переходит в число базисных, а x 6 -в число свободных.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2 ; x 6) =42-7/3 x 6 +5 x 2

При данном опорном плане (6;0;7;1;15;0) x 2 переводиться из свободных в базисные переменные:

x 2 =min{∞;7/3;1/11;15/3}=1

Выражаем x 2 через x 4

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

Выражаем неизвестные переменные и целевую функцию через свободные переменные:

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 положительное, следовательно можно увеличивать

x 6 =min{18;∞;3;6}=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

В целевой функции все коэффициенты при переменных отрицательны, значение функции увеличивать нельзя, аналогично преобразовываем остальные переменные, находим опорный план, из которого определяем x 1 ,x 2 .

1. Пересечение замкнутых множеств, множество нетривиальных ограничений.

2. Множество решений системы линейных нестрогих неравенств и уравнений является замкнутым.

αX=(αx 1 ,x 2 ,…, αx n)

X+Y=(x 1 +y 1 , x 2 +y 2 ,… x n +y n)

Линейные координаты X 1 ,X 2 ,…X n называется точка P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Множество P={λ 1 x 1 + λ 2 x 2 +…+ λ k x k } 0≤ h i ≤1 для i= 1,…k n åR i =1, 1≤ i ≤k выпуклая линейная комбинация точек x 1 ,x 2 ,…x n . Если k=2, то это множество называется отрезком. X 1 ,X 2 – концы отрезка. Угловой точкой замкнутого множества называется точка, которая не является нетривиальной линейной комбинацией точек множества (угловая точка).

Нетривиальность означает, что хотя бы одна из λ отлична от 0 или 1.

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

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

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

Переход к новому опорному плану

F 1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 можно доказать, где υ k рассмотренный выше минимум, который определяется при введении k-ой переменной в базис, а Δ k =åс j x j (1) -С k , где n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1))- оценка k-ой переменной, поэтому если решается задача на максимум, то величина ΔF 2 положительной должна быть, Δk – отрицательная. При решении задач на минимум ΔF 2 -отрицательная, Δ k - положительная. Эти величины вычисляются и если среди ΔF 2 все значения не положительны, то при решении задач на минимум наоборот. Если при решении на максимум среди ΔF 2 несколько положительных, то вводим в базис тот вектор, при котором эта величина достигает максимум, а если задача решается на минимум и среди ΔF 2 несколько отрицательных, то в число базисных включается вектор с наименьшим значением ΔF 2 , то есть с наибольшим по абсолютной величине. При выполнении этих условий гарантируется наибольшее возможное изменении значения функции.

Решение задачи будет единственным, если для любых векторов x k не входящих в базис, оценки Δ k ≠0, если хотя бы одно из таких Δ k =0, то решение не является единственным, для нахождения другого решения переходим к другому опорному плану, включая в базис x k , где Δ k =0. Перебор все такие опорные решений составляют их в линейную комбинацию, которая и будет решением задачи.

Если для любого некоторого Δ k противоречащих условию оптимальности коэффициенты при переменной x k ≤ 0, то система ограничений не ограничена, то есть оптимального плана не существует.

Двойственная задача

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

Двойственная задача имеет:

1. m переменных, соответствующих числу ограничений прямой задачи;

2. n ограничений, соответствующих числу переменных прямой задачи.

Двойственная задача получается путём симметричного структурного преобразования условий прямой задачи по следующим правилам:

· Каждому ограничению b i ПЗ соответствует переменная y i ДЗ;

· Каждой переменной x j ПЗ соответствует ограничение C j ДЗ;

· Коэффициенты при x j в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;

· Коэффициенты C j при x j в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

· Постоянные ограничений b i ПЗ становятся коэффициентами целевой функции ДЗ.

Рассмотрим следующие две задачи:

F = С 1 х 1 +С 2 х 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 х 1 +b 2 х 2 +... +b n x n →min

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

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

a 1 n y n + a 2 m y n + ... + a nm y n ≤C n

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

1. Основы математических методов и их применение;

2. Решение задач с помощью симплекс – метода.

Модифицированный симплекс-метод

В модифицированном методе матрица

не пересчитывается, хранится и пересчитывается только матрица. В остальном алгоритм похож на вышеописанный.

1. Вычисляем двойственные переменные

2. Проверка оптимальности. преобразуется в.

Проверка заключается в вычислении для всех столбцов. Столбец со значением < 0 можно вводить в базис.

Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.

Чаще выбирают значение, меньшее некоторого заданного значения

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

3. Определение выводимого.

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

Умножим слева на, т.е.

Здесь - базисный план, - разложение вводимого столбца по базису.

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

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный план по уже приведенной формуле с найденным значением.

5. Пересчитываем обратную к базисной.

Пусть - выводимый столбец.

Матрица B представима в виде

где - базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид

Нам нужно найти матрицу, такую что

Замечание.

При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».

Мультипликативный вариант симплекс-метода

В мультипликативном варианте матрица не хранится, хранятся лишь множители

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

Другие варианты симплекс-метода

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

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

Метод основан на том, что базисная матрица может быть представлена в виде

Обратная к ней имеет вид

При относительно небольших размерах матрицы остальная часть матрицы может не храниться.

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

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

Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:

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

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

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

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. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

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

3.1. Описание

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

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

Уравнение W(x) = c, где W(x) – максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. При этом экстремальная задача приобретает следующую формулировку: требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причем их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Сущность симплекс-метода состоит в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяются на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придаются произвольные значения и затем подставляются в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

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

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

1. нахождение исходной вершины множества допустимых решений;

2. последовательный переход от вершины к вершине, ведущий к оптимизации значения целевой функции.

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

двухфазный .

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

Усиленная постановка задачи

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

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x – переменные из исходного линейного функционала; x s – новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство; c – коэффициенты исходного линейного функционала; Z – переменная, которую необходимо максимизировать. Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт число степеней свободы. Проще говоря, если рассматривать вершину многогранника, это есть число рёбер, по которым можно продолжать движение.

Тогда можно присвоить такому числу переменных значение 0 и назвать