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

Стр 1 из 3Следующая ⇒

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

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

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

Выполнил студент группы ВИВТ-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

Приложение. 21

Введение

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

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

Действительно, путь необходимо исследовать на экстремум линейную функцию

Z = С₁х₁+С₂х₂+... +С_Nx_N

при линейных ограничениях

a₁₁x₁ + a₂₂x₂ +... + a_1NХ_N = b₁

a₂₁x₁ + a₂₂x₂ +... + a_2NХ_N = b₂

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

a_М₁x₁ + a_М₂x₂ +... + a_М_NХ_N = b_М

Так как Z - линейная функция, то Z = С_j, (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

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

Задачи курсовой заботы:

1. привести теоретический материал;

2. на примерах рассмотреть симплекс метод;

3. представить данную курсовую работу в виде презентации.

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

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f ( x₁, x₂, ..., x_n ) при ограничениях g_i ( x₁, x₂, ..., x_n) * b_i, где g_i- функция, описывающая ограничения, * - один из следующих знаков £, =, ³, а b_i - действительное число, i = 1, ..., m. f называется целевой функцией.

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

Задачу линейного программирования можно сформулировать так. Найти max

при условии: a₁₁ x₁ + a₁₂ x₂ +... + a_1n x_n £ b₁;

a₂₁ x₁ + a₂₂ x₂ +... + a_2n x_n£ b₂;

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

a_m1 x₁ + a_m2 x₂ +... + a_mn x_n£ b_m;

x₁ ³ 0, x₂ ³ 0, ..., x_n ³ 0.

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

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

Найти:

max c_T x

при условии:

A x £ b;

x ³ 0,

где А - матрица ограничений размером (m´ n),

b(m´ 1) - вектор-столбец свободных членов,

x(n ´ 1) - вектор переменных,

с_Т = (c₁, c₂, ..., c_n) - вектор-строка коэффициентов целевой функции.

Решение х₀ называется оптимальным, если для него выполняется условие:

с_Тх₀ ³ сТ х, для всех х Î R(x).

Поскольку min f(x) эквивалентен max [- f(x)], то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный (прямой, простой) симплекс - метод;

3) метод искусственного базиса;

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

5) двойственный симплекс - метод.

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

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

Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

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

Для его применения необходимо, чтобы знаки в ограничениях были вида “меньше либо равно”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

Если в исходной системе ограничений присутствовали знаки “ равно ”

или “ больше либо равно ”, то в указанные ограничения добавляются

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

2. Формируется симплекс-таблица.

3. Рассчитываются симплекс – разности.

4. Принимается решение об окончании либо продолжении счёта.

5. При необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

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

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

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

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

Теорема 1:

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

7x₁+5x₂→ max

x₃=19-2x₁-3x₂(0; 0; 19; 13; 15; 18)

x₄=13-2x₁-x₂ первоначальный опорный план

x₅ =15-3x₂

x₆=18-3x₁F(x₁, x₂)=7*0+5*0=0

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

На интуитивном уровне понятно, что естественным будет увеличение x₁, так как коэффициент при нем больше чем при x₂. Оставляя x₂=0, мы можем увеличивать до тех пор, пока x₃, x₄, x₅, x₆ будут оставаться неотрицательными.

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

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

x₁=6-1/3 x₆

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

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

x₄=13-2(6-1/3 x₆)- x₂=1+2/3 x₆- x₂

x₅= x₅=15

F(x₂; x₆) =42-7/3 x₆+5 x₂

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

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

Выражаем x₂ через x₄

x₂=1+2/3 x₆- x₄

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

x₃=7+2/3 x₆-3(1+2/3x₆ –x₄)= 7+2/3 x₆-3-2x₆+3x₄=4-4/3x₆+3 x₄

x₅= 12-2x₆+3x₄-

F=42-7/3 x₆+5(1+2/3x₂- x₄) =47-7/3x₆ +10/3x₆-5x₄=47+x₆-5x₄

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

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

x₄=4/3-4/9 x₆- 1/3x₃

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

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

Теорема 2:

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

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

α X=(α x₁, x₂, …, α x_n)

X+Y=(x₁+y₁, x₂+y₂, … x_n+y_n)

Линейные координаты X₁, X₂, …X_n называется точка P=λ ₁x₁+ λ ₂x₂+…+ λ _kx_k

Теорема 3:

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

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

Теорема 4:

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

Теорема 5:

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

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

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

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

Решение задачи будет единственным, если для любых векторов 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 = С₁х₁+С₂х₂+... +С_nx_n→ max

(5)

a₁₁x₁ + a₂₂x₂ +... + a_1mx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ +... + a_2mx_n ≤ b₂

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

a_m1x₁ + a_m2x₂ +... + a_mnx_n ≤ b_m

x_j≥ 0 j=1, …, n

Z = b₁х₁+b₂х₂+... +b_nx_n→ min

(6)

a₁₁y₁ + a₂₁y₂ +... + a_m1y₁ ≤ C₁

a₁₂y₁ + a₂₂y₂ +... + a_m₂y₂ ≤ C₂