Реферат Симлекс-метод
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Содержание.
Введение. 3
1. Общая характеристика симплекс метода. 4
2. Решение различных задач симплекс методом. 11
3. Табличный симплекс метод. 21
3. Заключение. 29
Список использованной литературы. 31
Введение.
Симлекс-метод - это характерный пример итерационных вычислений. используемых при решении большинства оптимизационных задач.
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
.
1. Общая характеристика симплекс метода.
Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит
- умение находить начальный опорный план;
- наличие признака оптимальности опорного плана;
- умение переходить к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в каноническом виде:
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части
Пусть система ограничений имеет вид
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные
которая имеет предпочтительный вид
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю
Пусть далее система ограничений имеет вид
Сведём её к эквивалентной вычитанием дополнительных переменных
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные
Пусть исходная ЗЛП имеет вид
причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:
Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид
Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.
Теорема. Если в оптимальном плане
М-задачи (4)-(6) все искусственные переменные
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план
Решение исходной задачи симплексным методом путем введения искусственных переменных
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Признаки оптимальности.
Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки
Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки
Для привидения системы ограничений неравенств к каноническому виду, необходимо в системе ограничений выделить единичный базис.
I. Ограничения вида «0»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
II. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1». а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
III. Ограничения вида «0» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.
Алгоритм симплекс метода.
(первая симплекс таблица)
X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
……………………………………………………………….
Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm
В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.
Fmin= C1X1+ C2X2+ C3X3+....+ CnXn
Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.
Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица1).
Таблица 1.
Симплекс таблица.
| C | Б | H | C1 | C2 | … | Cm | Cm+1 | … | Cm+k |
| | | | X1 | X2 | … | Xm | Xm+1 | … | Xm+k |
| C1 C2 C3 : : Cm | X1 X2 X3 : : Xm | h1 h2 h3 : : hm | 1 0 0 : : 0 | 0 1 0 : : 0 | : : : : : : | 0 0 0 : : 0 | q1,m+1 q2,m+1 q3,m+1 : : qm,m+1 | : : : : : : | q1,m+k q2,m+k q3,m+k : : qm,m+k |
| | F= | F0 | | | … | m | m+1 | … | m+k |
Первый столбец- коэффициенты в целевой функции при базисных переменных.
Второй столбец - базисные переменные.
Третий столбец - свободные члены (hi00).
Самая верхняя строка - коэффициенты при целевой функции.
Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».
Индексная строка позволяет нам судить об оптимальности плана:
1. При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
2. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.
Переход ко второй итерации:
Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.
Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.
Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца.
На пересечении строки и столбца находится разрешающий элемент.
На этом этапе осуществляется к переходу к последующим итерациям.
Переход к итерациям:
1. Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
2. Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
3. Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
4. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
5. Остальные элементы переносятся по формуле:
2. Решение различных задач симплекс методом.
Е
Алгоритмы симплекса-метода позволяют также установить, является ли задача линейного программирования разрешимой.
Запишем ограничения задачи ЛП в таком виде:
A1x1 + A2x2 + . + Anxn +An+1xn+1 +.+ An+mxn+m = A0.
Пусть A1,.,Am-множество линейно независимых векторов.
Тогда уравнение
A1x1*+ A2x2* + . + Anxn* +An+1xn+1* +.+ An+mxn+m* = A0, (2...2.1)
определяет базисное решение x1*, x2*,.,xm*,
Предположим, что это решение допустимо, то есть x1*³0, x2*³0,.,xm*³0. Базис {A1,.,Am}образует m-мерное пространство, а потому каждый из векторов Am+1,.,Am+n единственным образом выражается через этот базис. Если Ar не входит в базис, то
A1x1r + A2x2r + . + Amxmr = Ar, (2...2.2)
где xir- соответствующие коэффициенты (i = 1, 2, ..., m).
Предположим, что хотя бы одна из величин xir больше нуля.
Решение уравнения
A1x1 + A2x2 + . + Amxm + Arxr = A0 (2...2.3)
обозначим как
Тогда ,очевидно:
Умножив уравнение (2.2.2) на xr и вычтя полученное уравнение из уравнения (2.2.1), получим
A1(x1*-xrx1r) + A2(x2*-xrx2r) +.+Am(xm*-xrxmr)=A0-xrAr. (2.2.5)
Сравнив уравнения (2.2.5) и (2.2.4), находим связь нового решения
Решение (2.2.6), во-первых, не будет базисным, так как содержит
m + 1 переменную, а во-вторых, будет допустимым не для всех значений xr.
Чтобы новое решение оставалось допустимым, нужно выбрать значение xr таким, чтобы ни одна из величин
xr max =
где xir > 0.
Чтобы сделать новое допустимое решение базисным, нужно одну переменную xi вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов.
Для этого выбираем значения в соответствии с (2.2.7). Тогда новое базисное решение имеет вид
x1* - xr maxx1r;
x2* - xr maxx2r;
xj (опущен)
xr max,
а новый базис - (A1, A2, ., Aj-1, Aj+1, ., Am, Ar).
Такой переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению, которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность).
Новому ДБР { x1* - xrx1r, x2* - xrx2r, ., xm* - xrxmr, xr}
соответствует следующее значение целевой функции
z1 = с1(x1*-xrx1r) + с2(x2*-xrx2r) +.+сrxr =
= (с1x1*+с2x2*+.+сmxm*)+xr(сr-с1x1r-.-сmxmr)=
=z0+xr(сr-с1x1r-.-сmxmr), (2.2.8)
где z0 - значение целевой функции для начального ДБР;
сr-с1x1r -с2x2r - . - сmxmr - симплекс-разность для переменной хr.
Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение, и выбирают такую небазисную переменную хr, для которой симплекс-разность положительна и максимальна.
Таким образом, алгоритм симплекса-метода состоит из следующих этапов:
1) находят начальный базис и связанное с ним допустимое базисное решение;
2) вычисляют симплекс-разность для каждой переменной, не входящей в базисное решение;
3) вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплексом-разностью; ее значение xrmax определяют из соотношения
для всех xir > 0,
4) выводят из базисного решения переменную xj, соответствующую
а из базиса - вектор A j;
5) переходят к этапу 2 новой итерации.
Этапы 2) - 4) повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными.
Это и есть признак оптимальности текущего базисного решения.
Пример 2.2. Решить симплексом-методом такую задачу:
максимизировать (2x1+5x2)
при ограничениях
x1£400, x2£300, x1+x2£500 .
Расширенная форма задачи имеет вид
Ограничения задачи запишем в виде табл. 2.1.
Первая итерация. 1. Выбрав в качестве начального базиса векторы { A3, A4, A5}, находим первое допустимое базисное решение:
A3x3*+A4x4*+A5x5*=A0,
откуда x3*=400, x4*=300, x5*=500,
2. Записываем каждый из небазисных векторов A1, A2 в виде линейной комбинации базисных {A3, A4, A5}
A3x31+A4x41+A5x51=A1;
A3x32+A4x42+A5x52=A2.
Таблица 2.1
| А1 | A2 | A3 | А4 | А5 | а0 |
| 1 | 0 | 1 | 0 | 0 | 400 |
| 0 | 1 | 0 | 1 | 0 | 300 |
| 1 | 1 | 0 | 0 | 1 | 500 |
Решая эти уравнения, получим
х31=1; x41=0; х51=1; x32=0; х42=1; х52=1.
3. Находим симплекс-разности для небазисных переменных x1 и x2:
с1-с3х31-с4х41- с 5х51= с 1=2;
с 2- с 3х32- с 4х42- с 5х52= с 2=5.
Поскольку с 2> с 1, вводим в базис вектор x2.
4. Определяем, какая переменная выводится из базиса. Для этого находим
х3= х3* - х2х32=х3*;
х4= х4* - х2х42=300-1х2;
х5= х5* - х2х52=500-1х2;
Итак переменная х2 вводится в базис со значением x2*= 300, переменная x4 выводится из базисного решения, а вектор A4- из базиса.
Вторая итерация. 1. Раскладываем каждый из небазисных векторов через базисные {A2,A3,A5}. Базисное решение
x2*=300, х3*=400, х5*=500-300*1=200
Представим каждый из векторов A1, A4 ,не вошедших в базис, в виде линейной комбинации A2,A3,A5 .Так как вектор A4 был выведен из базиса, рассмотрим только вектор A1.
Уравнение будет иметь вид
A2х21+A3х31+A5х51=A1,
откуда х21=0; х31=1; х51=1.
2. Находим симплекс-разность для переменной x1:
с 1- с 2х21- с 3х31- с 5х51= с 1-0-0-0= с 1=2>0.
Итак, переменную х1 можно ввести в базис.
3. Определяем, какую переменную (вектор) следует вывести из базиса. Для этого вычисляем
х2= х2* - х1х21=300-0х1;
х3= х3* - х1х31=400-1х1;
х5= х5* - х1х51=200-1х1;
Следовательно, из базиса выводится вектор х5 , из базисного решения - A5.
4. Вычисляем новый ДБР.
Переходим к третьей итерации. Следующие итерации проводятся аналогично.
x1*=200; x2*=300.
Метод полного исключения
Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ. Потребовалась его рационализация как по форме представления информации, так и в способе организации вычислений, чтобы сделать его пригодным для реализации на ЭВМ. С этой целью был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана - Гаусса.
Пусть задана система линейных алгебраических уравнений
В матричной форме данная система имеет следующий вид:
Ax=A0.
Матрица Ap=[A, A0] называется расширенной матрицей. Метод полного исключения Жордана - Гаусса состоит из конечного числа однотипных итераций и заключается в сведении матрицы к единичному виду. Метод основывается на двух операциях:
1) одну из строк расширенной матрицы умножают на множитель, отличный от нуля;
2) из каждой строки расширенной матрицы вычитают одну строку, умноженную на некоторое число.
Каждое из таких элементарных преобразований ( называемых преобразованием Гаусса) приводит к новой системе линейных уравнений, которая эквивалентна начальной системе.
Первая итерация метода полного исключения.
1. Среди элементов A выбирают произвольный элемент, отличный от нуля. Его называют направляющим элементом итерации. Строку и столбец, содержащие направляющий элемент, называют направляющими.
2. Все элементы направляющей строки расширенной матрицы делят на направляющий элемент. В результате получают направляющую строку с направляющим элементом, равным единице. Далее из элементов каждой строки матрицы A вычитают элементы новой направляющей строки, умноженные на элементы, которые расположены на пересечении данной строки и направляющего столбца.
Матрицу, в которую преобразовалась расширенная матрица Ap после первой итерации, обозначим Ap(1). В ней все элементы направляющего столбца, кроме направляющего элемента ( равного 1), стали нулями. Совокупность элементов первых n столбцов матрицы Ap, лежащих вне направляющей строки и столбца предыдущей (предыдущих) итерации называют главной частью матрицы Ap(1).
Вторая и дальнейшие итерации метода проводятся аналогично первой, причем до тех пор, пока имеется возможность выбора направляющего элемента.
Если после k-й итерации главная часть матрицы Ap(k) не содержит ни одного элемента или содержит только нули, то процесс заканчивается.
Пусть процесс оборвался после итерации 1. Предположим вначале, что среди строк матрицы A(l) есть такие, которые не были направляющими ни в одной из предыдущих итераций, например, строка с номером i. Тогда очевидно,
aij = 0; j = 1, 2, ., n.
Поскольку для любой строки справедливо
A(i)x = ai0 , (2.2.9)
то уравнение для і-й строки имеет вид
0x1+0x2+.+0xn=ai0(l). (2.2.10)
Если ai0(l)≠0, то уравнение (2.2.10) противоречиво, и данная система уравнений неразрешима.
Если ai0(l)=0, то уравнение (2.2.10) представляет собой тождество и
i-я строка может быть отброшена.
Перебрав одну за другой все строки матрицы A(l), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.
Таким образом, в системе окажется равно l уравнений. Примем для определенности, что это первые по порядку l уравнений. Тогда полученную систему уравнений можно записать в виде
Пусть i-й направляющей строке соответствует i-й направляющий столбец вследствие соответствующего выбора направляющего элемента. Тогда
aij(l)=
Следовательно, (2.2.11) можно записать в виде:
xi = ai0(l) -
причем переменные xi ( i =1, ., l) являются базисными, а переменные xj
( j=l+1, ., n) - небазисными.
При xj = 0 ( j=l+1, ., n) получим одно из базисных решений системы уравнений
xi = ai0(l), i =1, 2, ., l, xj=0; j=l+1,.,n.
Задавая для xj произвольные значения
Если xi - i-я компонента этого решения, то
Обозначим
x0= (a10, a20,., al0,0,.,0 )
xj= (-a1j, -a2j,., -aij, 0 ,., 0, 1, 0 ,.,0 ), 1 £ j £ n.
j n
Тогда общее (полное) решение системы линейных уравнений определяется соотношением, аналогичным (2.2.14):
x общ = x0 +
где x0- базисное решение начальной системы уравнений;
Обозначим расширенную матрицу системы уравнений после k-й итерации через
Ap(k)=[ai0(k), ai1(k),.,ain(k)],i=1,2,.,m.
Пусть aij(k)- направляющий элемент преобразования на (k + 1)-й итерации. Тогда в результате (k + 1)-й итерации метода полного исключения Гаусса получим матрицу Ap(k+1), элементы которой определяются следующими соотношениями:
1) для всех элементов направляющей строки
2) для элементов направляющего столбца
arj(k+1)=0; r=1,.,n, причем r¹и; aij(k+1)=1; (2.2.17)
3) для всех остальных элементов матрицы
Пример 2.3. Применим метод полного исключения Гаусса для исследования системы уравнений
x1 + 2x2 + x3 + x4 = 3;
2x1 + x2 + x3 + 3x4 = 3;
4x1 + 5x2 + 3x3 + 5x4 = 9.
Расширенная матрица имеет вид:
Первая итерация. В качестве первого направляющего элемента возьмем a11= 1 , умножим первую строку матрицы А на 2 и на 4 , затем вычитая результаты из второй и третьей строк, получим
Вторая итерация. Поскольку главная часть матрицы Ap(1) содержит ненулевые элементы, продолжим процесс исключения. Выберем элемент a22(1)=-3.
После аналогичных преобразований получим
Как видим, главная часть матрицы Ap(2), состоящая из элементов a33(2) и a34(2) , содержит только нули. Следовательно, процесс исключения заканчивается.
Исследуем матрицу A(2). Поскольку третья строка содержит лишь нулевые элементы, то она может быть отброшена. Тогда эквивалентная матрица системы уравнений будет иметь вид
Соответственно формулам (2.2.13), (2.2.14) имеем базисное решение
x1*=1; x2*=1; x3=0; x4=0.
Общее решение данной системы имеет такой вид:
X1=1-
где a3, a4- произвольные скаляры.
3. Табличный симплекс метод.
Основная идея симплекса-метода состоит в переходе от одного допустимого базисного решения к другому таким образом, что значения целевой функции при этом непрерывно возрастают (для задач максимизации).
Предположим, что ограничения задачи сведены к такому виду, что в матрице А иеется единичная подматриця и все свободные члены положительные. Иными словами, пусть матрица ограничений имеет вид
A1x1+.+Anxn+e1xn+e1xn+1+.+emxn+m=A0=[ai0],
где
для всех i = 1, 2,., n.
Применим одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, ., An, e1, ., em, A0].
Пусть aij- направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (3.3.18) получим новые значения свободных членов:
Исследуем выражения (3.3.19). и выясним условия, при которых al0(k+1)>0 для всех l, то есть новое базисное решение будет также допустимым.
По предположению al0(k)>0; l=1,.,m,
aij(k)>0,
тогда
Если alj(k)<0, тогда al0(k+1) > 0, поскольку ai0(k) > 0 , aij(k) > 0.
Если alj(k)>0, то
будет больше нуля при всех l=1, 3. ..., m тогда и только тогда, когда
Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:
a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;
б) направляющую строку i выбирают так, чтобы отношение
При таком преобразовании в базис вводится вектор Aj и выводится вектор Аi. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.
Для этого используют так называемые оценки векторов Dj:
где Iб - множество индексов базисных векторов; xij- определяют из условия
Величины {Dj } равны симплекс-разницам для переменных {xj} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец Аj с наибольшей по модулю отрицательной оценкой, то есть
Таблица 3.3.
| c | | | c1 | c2 | c3 | . | cj | . | cn |
| | Bx | a00 | A1 | A2 | A3 | . | Aj | . | An |
| c1 | x1 | a1o | a11 | a12 | a13 | . | a1j | . | a1n |
| c2 | x2 | a2o | a21 | a22 | a23 | . | a2j | . | a2n |
| . | . | . | . | . | . | . | . | . | . |
| | xi | aio | ai1 | ai2 | ai3 | . | aij | . | ain |
| . | . | . | . | . | . | . | . | . | . |
| cm | xm | amo | am1 | am2 | am3 | . | amj | . | amn |
| | D | | D1 | D2 | D3 | . | Dj | . | Dn |
Последняя сторока таблицы - индексная -служит для определения направляющего столбца. Ее элементы Dj определяют по формуле (3.3.21). Очевидно, для всех базисных векторов {Ai} i=1,.,m оценки Dи=a0и=0.
Значение целевой функции a00 определяется из соотношения
В столбце Bx записываем базисные переменные {xi} i= 1, ..., т. Их значения определяются столбиком свободных членов ai0, то есть
xi=ai0, i=1, 2,.,m.
Направляющие строка Ai и столбец Aj указываются стрелками. Если в качестве направляющего элемента выбран aij, то переход от данной симплекс таблицы к следующей определяется соотношениями (3.3.16) - (3.3.18).
Итак, алгоритм решения задачи ЛП табличным симплексом-методом состоит из этапов.
1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.
3. В качестве направляющего столбца выбирают Aj, для которого
3. Направляющая строка Aі выбирают из условия
4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом aij, для чего используют соотношения (3.3.16) - (3.3.18). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой
Правильность вычислений контролируют по формулам непосредственного счета:
В столбце Bx новой таблицы заменяют xi на xj, а в столбце С ci на cj.
5. Если все a0l(k+1)³0, l=1,.,n, то новое базисное решение xi= ai0(k+1), iÎIб(k+1) - оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.
6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:
а) все a0l ³0. Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы;
б) найдется такой a0j=Dj<0, что все элементы этого столбца arj£0,
r = 1, ., m. Это признак неограниченности целевой функции z=
Назовем некоторые особенности применения табличного симплекс-метода.
Если в качестве начального базиса выбирают базис из свободных переменных, для которых ci=0, то оценки для всех небазисных переменных равны Dj = a0j = -cj, а соответствующее значение целевой функции
a00=
Отсутствие векторов с отрицательными оценками при решении задач максимизации является признаком оптимальности соответствующего базисного решения.
Если существует такой небазисный вектор, для которого оценка отрицательна, а все элементы этого столбца неположительны, то целевая функция задачи в области допустимых решений неограничена.
При решении задач минимизации в базис вводится вектор с наибольшей положительной оценкой, а отсутствие таких векторов является признаком оптимальности последнего базисного решения.
Пример 3.4.
Максимизировать 4x1+3x2
при ограничениях
x1 £ 4000;
x2 £ 6000;
x1 +
x1, x2 ³ 0.
Расширенная форма задачи имеет такой вид:
максимизировать 4x1+3x2
при ограничениях
1x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4000;
0x1 + 1x2 + 0x3 + 1x4 + 0x5 = 6000;
1x1 + 2/3x2 + 0x3 + 0x4 + 1x5 = 6000;
Так как A0>0, а векторы A3, A4, A5 образуют единичный базис, то задачу можно решать методом симплекс-таблиц.
Первая итерация. Составляем и заполняем начальную симплекс-таблицу (табл.3.3).
| Ci | | | 4 | 3 | 0 | 0 | 0 | ||
| | Bx | Ai0 | A1 | A2 | A3 | A4 | A5 | ||
0 | X3 | 4000 | 1 | 0 | 1 | 0 | 0 | ||
| 0 | X4 | 6000 | 0 | 1 | 0 | 1 | 0 | ||
| 0 | X5 | 6000 | 1 | 1/3 | 0 | 0 | 1 | ||
| | D | 0 | -4 | -3 | 0 | 0 | 0 |
Поскольку -4<-3<0, то направляющий столбец - первый.
Составив отношение вида
Итак, направляющая строка -первая, направляющий элемент a11=1.
Таблица 3.4.
| Ci | | | 4 | 3 | 0 | 0 | 0 | ||
| | Bx | ai0 | A1 | A2 | A3 | A4 | A5 | ||
| 4 | X1 | 4000 | 1 | 0 | 1 | 0 | 0 | ||
| 0 | X4 | 6000 | 0 | 1 | 0 | 1 | 0 | ||
0 | X5 | 2000 | 0 | 2/3 | -1 | 0 | 1 | ||
| | D | 160000 | 0 | -3 | 4 | 0 | 0 |
Вторая итерация. Как видим с табл. 3.4.,направляющий столбец - второй, а направляющая строка - третья, так как
Выполнив очередную итерацию симплекс-метода, получим симплекс-таблицу 3.5.
| Ci | | | 4 | 3 | 0 | 0 | 0 | ||
| | Bx | ai0 | A1 | A2 | A3 | A4 | A5 | ||
| 4 | X1 | 4000 | 1 | 0 | 1 | 0 | 0 | ||
0 | X4 | 3000 | 0 | 0 | 3/2 | 1 | -3/2 | ||
| 3 | X2 | 3000 | 0 | 1 | -3/2 | 0 | 3/2 | ||
| | D | 250000 | 0 | 0 | -1/2 | 0 | 9/2 |
Третья итерация. Так как a03= -1/2 <0, то направляющий столбец A3, а направляющая строка - вторая, поскольку a23=3/3. Выполнив очередную итерацию с направляющим элементом a23=3/2, получим симплекс-таблицу 3.6.
Таблица 3.6.
| Ci | | | 4 | 3 | 0 | 0 | 0 |
| | Bx | ai0 | A1 | A2 | A3 | A4 | A5 |
| 4 | X1 | 2000 | 1 | 0 | 0 | -2/3 | 1 |
| 0 | X3 | 2000 | 0 | 0 | 1 | 2/3 | -1 |
| 3 | X2 | 6000 | 0 | 1 | 0 | 1 | 0 |
| | D | 260000 | 0 | 0 | 0 | 1/3 | 4 |
Поскольку в индексной строке табл. 3.6. все оценки положительны, то найдено оптимальное решение: x1опт=2000, x2опт=6000, x3опт=2000.
Соответствующее значение целевой функции:
max (4x1+3x2)=a00=26000=4x1опт+3x2опт.
3. Заключение.
Симплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.
Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач.
Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.
Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, если не десятками, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний хоть и экспоненциален в худшем случае, однако на практике справляется с задачами ЛП многократно лучше. Все промышленные (да и кустарные) реализации решения ЛП основаны на симплекс-методе и его вариантах.
Список использованной литературы.
1. Лищенко «Линейное и нелинейное программирование», М. 2003
2. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000
3. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004
