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

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

Первым исследованием по линейному  программированию является работа Л. В. Кантфовича “Математические методы организации и планирования производства”, опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающих множителей решения задач линейного программирования и дано его теоретическое обоснование.

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

Математическое программирование – это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Симплекс метод

2.1 Математическое описание метода.

Допустим, имеется система уравнений  ограничений:

 

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

 

  

Избавляемся от отрицательных коэффициентов  для этого принимаем

 

 

Данная  форма записи уравнений называется стандартной.

 

	СЧ	х1	х2	х3	х4
у1	b1	a11	a12	a13	a14
у2	b2	a21	a22	a23	a24
у3	b3	a31	a32	a33	a34
у4	b4	a41	a42	a43	a44
у5	b5	a51	a52	a53	a45

При пересечении  разрешающей строки у₃ и разрешающего столбца х₂ получаем разрешающий элемент а_32.

Необходимо  найти коэффициенты, которые получатся  в разрешающей строке после обмена х₂ ↔ у_3.

 

	СЧ	х1	у3	х3	х4
у1
y2
x2
y4
y5

 

 

Алгоритм  преобразования коэффициентов стандартной  таблицы.

1. Разрешающий элемент заменяется на обратную ему величину.
2. Все остальные элементы разрешающей строки делятся на разрешающий элемент.
3. Все элементы разрешающего столбца, кроме самого разрешающего элемента делятся на разрешающий элемент и меняют знак.
4. Каждый из остальных элементов подвергаются следующему преобразованию: к нему прибавляются произведение элементов, стоявшего в прежней разрешающей строке на том же месте по порядку (т. е. в том же столбце), на элемент стоящий в новом разрешающем столбце на соответствующем месте (т. е. в той же строке, что и рассчитываемый элемент).

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

 

Алгоритм преобразования x_j ↔ y_i стандартной таблицы сводится к следующим операциям:

1. Выделить в таблице разрешающий элемент. Вычислить ее обратную величину и записать в нижней части этой же ячейки, например в правом нижнем углу.
2. Все элементы разрешающей строки, кроме самого разрешающего элемента умножить на , результат записать в нижней части той же ячейки.
3. Все элементы разрешающего столбца, кроме всего разрешающего элемента умножить на на – a, записать в нижней части той же ячейки.
4. Подчеркнуть в разрешающей строке все верхние числа (прежние элементы) за исключением самого разрешающего элемента. А в разрешающем столбце все новые элементы, кроме самого разрешающего элемента.
5. Для каждого из элементов не принадлежащих ни к разрешающей строке, ни к разрешающему столбцу в нижней часть ячейки записать произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент.
6. Переписать таблицу, заменив:
• x_j на  y_i;
• элемент разрешающей строки и столбца, числами, стоящими в нижней части тех же ячеек;
• каждый из остальных элементов суммой чисел стоящей в верхней и нижней части той же ячейки.

В любой задаче ОЗЛП существует так  же линейная функция L, которая в общем случае выглядит следующим образом:

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

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

Нахождение решения каждой задачи распадается на два этапа:

2. нахождение опорного плана;
3. отыскание оптимального решения.

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

В процессе второго этапа выясняется, ограничена ли снизу функция L, которая стремиться к минимуму, если нет, то оптимального решения не существует. Если да, то оно отыскивается после замены x на y.

 

Двойственные задачи ОЗЛП.

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

Допустим, имеется одно из уравнений  с отрицательным свободным членом:

 

	СЧ		x1		x2		x3
y1	1	2	-1	1	-2	1	-1	0
y2	-5	4	-2	2	1	2	1	0
y3	2	2	1	1	1	1	0	0
y4	1	0	0	0	-1	0	1	0

 

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

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

 

	СЧ	x1	x2	x3
y1	3	2	1	2
y2	1	2	3	-1
y3	2	1	-1	0
y4	1	0	-1	0

 

2.2 Блок  – схема алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3 Пример решения задачи с использованием симплекс-метода.

 

Даны данные, из которых составляется система уравнений вида:

 

 

 

Целевая функция этой системы уравнений  стремится в максимум, и имеет  вид:

 

 

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

В данной системе 3 – уравнения с 3 – неизвестными, принимают за основные X₄, X_5, X₆ – переменных.

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

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