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

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

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

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

Кафедра ЕН

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

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

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

Выполнил студент группы ВИВТ-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 = С₁ х₁ +С₂ х₂ +... +С_N x_N

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

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

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

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

a_{М 1} x₁ + a_{М 2} 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 - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

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

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

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

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

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

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

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

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

,

Ограничения:

1. Правые части всех ограничений должны быть неотрицательными b_i ≥0, i=1,..m. Если какой-нибудь из коэффициентов b_i < 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

2. Все ограничения должны быть представлены в виде равенств, поэтому при переходе от неравенства к равенству используют аппарат дополнительных переменных. Если исходные ограничения определяют расход некоторого ресурса (знак ""), то переменные x_j ≥0, j=n+1,…kследует интерпретировать как остаток, или неиспользованную часть ресурса. В этом случае x_j – остаточная переменная и вводится в уравнение со знаком "+". Если исходные ограничения определяют избыток некоторого ресурса (знак ""), то вводится избыточная переменная x_j ≥0, j=k+1,…Nзнаком "-".

Переменные:

· Все переменные должны быть неотрицательными, т.е. x_j ≥0, j=1,…n.

· Если переменная не имеет ограничения в знаке, то её нужно представить как разность двух неотрицательных переменных: x=x^’ -x^’’ , где x^’ ≥0, x^’’ ≥0. Такую подстановку следует использовать во всех ограничениях, содержащих эту переменную, а также в выражении для целевой функции. Если такая переменная попадает в оптимальное решение, то

.

Целевая функция:

· Подлежит максимизации или минимизации. maxz= - min(-z)

· Система ограничений в виде равенств и неравенств образует выпуклое множество - выпуклый многогранник. Это множество может быть ограниченным и неограниченным. Целевая функция задачи линейного программирования также является выпуклой функцией. Таким образом, задача линейного программирования является частным случаем задачи выпуклого программирования.

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

· Система (1) линейных уравнений совместна, если она имеет, по крайней мере, одно решение.

· Система (1) называется избыточной, если одно из уравнений можно выразить в виде линейной комбинации остальных.

· В системе (1) число переменных (неизвестных x_j ) n больше, чем число ограничений m. Будем считать, что ранг этой системы равен m (система не избыточна) и что система (1) совместна. Тогда m переменных из общего их числа образуют базисные переменные, а остальные (n-m) переменных называют небазисными.

· Если система уравнений имеет решение, то она имеет и базисное решение.

· Решение системы уравнений (1) называют допустимым, если все его компоненты неотрицательны.

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

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

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

Прямая задача.

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

Найти максимум (минимум) функции

при условиях

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

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

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

При графическом методе решения задачи линейного программирования (ЗЛП) оптимальному решению соответствует всегда одна из угловых (экстремальных) точек пространства решений. Это результат положен в основу построения симплекс-метода. Симплекс-метод не обладает наглядностью геометрического представления пространства решений.

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

Обозначим: N– общее количество переменных в ЗЛП, представленной в канонической форме; n- количество исходных переменных; m - количество ограничений, n_q - количество дополнительных переменных, тогда N=n+n_q . Каждая вершина многогранника решений имеет m - ненулевых переменных и

(N-m) - нулевых переменных. Ненулевые переменные называются базисными, нулевые переменные – небазисными. Дополним систему равенств равенством целевой функции, при этом будем считать, что z является m+1 базисной переменной, которая всегда присутствует в базисе для любой вершины.

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

При выборе начального допустимого базиса для составления симплекс-таблицы на первом шаге исходные x₁ ,x₂ переменные приравниваются к нулю и являются небазисными, среди введённых дополнительных переменных выбираются переменные с коэффициентами равными единице. Переменные x₃ ,x₄ ,x₅ в равенствах (2) - (4) являются базисными и в z - строку входят с коэффициентами, равными 0. Для заполнения симплекс-таблицы необходимо целевую функцию преобразовать к виду

.

Таким образом, окончательно получаем:

(1)

(2)

(3)

(4)

При составлении симплекс-таблицы придерживаются следующих правил:

1. в крайнем левом столбце располагаются базисные переменные и z;

2. в крайнем правом столбце располагаются правые части ограничений;

3. в первой строке располагаются переменные в определённом порядке: сначала z, потом небазисные переменные, базисные переменные располагаются в последних m столбцах перед правой частью.

Идею рассмотрим на примере:

7x₁ +5x₂ →max

2x₁ +3x₂ ≤19

2x₁ +x₂ ≤13

3x₂ ≤15

3x₁ ≤18

x₁ ≥0, x₂ ≥0

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

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

7x₁ +5x₂ →max

2x₁ +3x₂ +x₃ =19

2x₁ +x₂ +x₄ =13

3x₂ +x₅ =15

3x₁ +x₆ =18

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

В нашем случае базисными переменными являются x₃ , x₄ ,x₅ ,x₆ . Остальные переменные являются свободными (x₁ ,x₂ ). Придавая произвольные значения свободным переменным мы будем получать различные значения базисных. Любое решение системы ограничений задачи называется допустимым. Опорным называется решение задачи, записанное в каноническом виде в котором свободные переменные равны 0.

Теорема 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₂ +…+ λ_k x_k

Теорема 3:

Множество P={λ₁ x₁ + λ₂ x₂ +…+ λ_k x_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 =åс_j x_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 = С₁ х₁ +С₂ х₂ +... +С_n x_n →max

a₂₁ x₁ + a₂₂ x₂ + ... + a_2m x_n ≤b₂

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

a_m1 x₁ + a_m2 x₂ + ... + a_mn x_n ≤b_m

x_j ≥0 j=1,…,n

Z = b₁ х₁ +b₂ х₂ +... +b_n x_n →min

a₁₂ y₁ + a₂₂ y₂ + ... + a_{m 2} y₂ ≤C₂

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

a_{1 n} y_n + a_{2 m} y_n + ... + a_nm y_n ≤C_n

y_i ≥0 i=1,…,m

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

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

Fmax=Zmin

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

Если (5) и (6) пара симметричных двойственных задач, то (x⁰ ₁ , x⁰ ₂ , ... , x⁰ _n ) и (y⁰ ₁ , y⁰ ₂ , ... , y⁰ _n ) являются их оптимальными решениями, то компоненты оптимальных решений удовлетворяются системе.

x₁ ⁰ (a₁₁ y₁ ⁰ +a₂₁ y₂ ⁰ +…+a_m1 y_n ⁰ -c₁ )=0

x₂ ⁰ (a₁₂ y₁ ⁰ +a₂₂ y₂ ⁰ +…+a_m2 y_n ⁰ -c₂ )=0

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

x_n ⁰ (a_1n y₁ ⁰ +a_2m y₂ ⁰ +…+a_m1 y_n ⁰ -c₁ )=0

y₁ ⁰ (a₁₁ x⁰ ₁ +a₂₂ x⁰ ₂ +...+a_1m x⁰ _n -b₁ )=0

y₂ ⁰ (a₂₁ x⁰ ₁ +a₂₂ x⁰ ₂ +... +a_2m x⁰ _n -b₂ )=0

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

y_n ⁰ (a_m1 x⁰ ₁ +a_m2 x⁰ ₂ +...+a_mn x⁰ _n -b_m )=0

Заключение

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

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

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