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

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

Например: пусть известен опорный план X =(x1,x2,…,xm,0,0,…,0) и связанная с ним система линейно независимых векторов: А1,А2,…,Аm , тогда для этого опорного плана можно подсчитать значение ЦФ Z=(c1x1+c2x2+…+cmxm) и записать условия ограничения в следующем виде x1A1+x2A2+…+xmAm=b

Поскольку векторы А1,А2,…,Аm линейно независимые любой вектор Aj можно разложить по этим векторам: Aj=x1jA1+x2jA2+…+xmjAm (*) Введем величины Zj Zj=x1jc1+x2jc2+…+xmjcm, где xij коэффициент соответствующий Ai в разложении вектора Aj по базисным векторам

Теорема1: улучшение опорного плана

Если для некоторого индекса j выполняется условие Zj-Cj>0, то можно уменьшить значение ЦФ причем:

· если ЦФ ограничена снизу, то можно построить опорный план с меньшим значением ЦФ, сем предыдущий

· если ЦФ не ограничена снизу, то можно построить план соответствующий сколь угодно малому значению ЦФ

Теорема2: критерий оптимальности опорного плана

Если для некоторого индекса j в опорном плане неравенство Zj-Cj0. Пусть этот минимум достигается для вектора Ak, тогда именно этот вектор подлежит выводу из базиса. Строка соответствующая этому вектору называется направляющей и обозначается «à».

4. После определения направляющих столбца и строки заполняют новую симплекс таблицу. В такой таблице на месте направляющей строки будет стоять Ai . Заполнение новой таблицы начинается с направляющей строки. В качестве компоненты опорного плана туда пишется величина Ө0 X’l=Ө0=Xk/Xkl, остальные элементы этой строки определяются по формуле X’lj X’lj=Xkj/Xkl где Xkl элемент находящийся на пересечении направляющих строки и столбца, именно на него делятся все бывшие элементы направляющей строки, а на месте бывшего элемента Xkl автоматически появляется единица. Общее правило для пересчета направляющей строки можно записать так: Ak (новый эл-т направляющей строки)=(старый Эл-т направл. строки)/(эл-т стоящий на пересечении направл. столбца и строки)

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

· для компонент опорного плана X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· для компонент разложенных по базису X’ij=Xij-(Xkj/Xkl)*Xil

· для дополнительной строки Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Все эти формулы строятся по одному правилу:

(новый эл-т)=(старый эл-т)-(эл-т новой направл. строки)*(эл-т направл. столбца стоящего в соотв. строке)

После заполнения новой симплекс таблицы осуществляется переход ко второму этапу алгоритма.

Методы природного и искусственного базиса. Основные понятия, алгоритмы методов.

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

Метод искусственного базиса основан на искусственном введении в математическую модель задачи таких векторов.

Пусть задана ЗЛП канонической формы

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Тогда ее преобразовывают к виду

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

……………………………….

a1mx1+a2mx2+…+anmxn+xn+m=bm

Где М – бесконечно большие числа. В полученной задаче сразу виден исходный базис, в качестве него следует взять вектора при искусственно введенных переменных xn+1, xn+2,…, xn+m. Поскольку именно эти вектора будут иметь вид: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Затем преобразованную задачу решают, используя алгоритм симплекс метода. Исходный опорный план преобразованной задачи имеет вид (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…,bm). Исходная симплекс таблица выглядит следующим образом

Базис	коэф. ЦФ	План	C1	C2	…	Cn	M	M	…	M
			A1	A2	…	An	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Определяем эл-ты дополнительной строки по формулам Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

Для определения разностей Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

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

Поскольку М очень большое число, то среди разностей Zj-Cj будет много положительных чисел. Т. е. будет множество претендентов на введение в базис среди векторов A1,A2,…,An

Если какой-то вектор соответствует искусственно введенным переменным xn+1,xn+2,…,xn+m, то соответствующий вектор выводится из базиса, а столбец симплекс таблицы при этом векторе вычеркивается и больше к нему не возвращаются. В конце преобразования симплекс таблицы возможны два варианта:

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

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

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

Симметричные двойственные задачи:

Первая стандартная форма

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

…………………………………………..

a1mx1+a2mx2+…+anmxn>=bm

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

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Не семеричная пара двойственных задач

Исходная задача в канонической форме

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

…………………………..

Идея симплекс– метода

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

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

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

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

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

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

Впервые симплекс–метод и его название были предложены американским математиком Джоном Данцигом в 1947 году, хотя идеи метода были опубликованы российским математиком Л.В. Канторовичем еще в 1939 году в статье «Математические методы организации и планирования производства».

Симплекс–метод состоит из трех основных элементов.

Курская академия государственной и муниципальной службы

Кафедра «информационной и техносферной безопасности»

Реферат

по дисциплине «Методы оптимальных решений»

на тему «Идея симплекс-метода»

Выполнила: студентка 2 курса

Специальности «экономика»

Москалева О. С.

Проверил: к.ф.м.н., доцент Погосян С. Л.

Курск – 2012

Введение……………………………………………………………………..3

1. Идея симплекс-метода…………………………………………….…4

2. Реализация симплекс-метода на примере……………………..……6

3. Табличная реализация простого симплекс-метода ……………….10

Заключение………………………………………………………………….15

Список использованной литературы………………………………..…….16

Введение.

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

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

Идея симплекс-метода

Рассмотрим универсальный метод решения канонической задачи линейного программирования, с n переменными и m ограничениями-равенствами, известный как симплекс-метод.

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

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

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

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

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

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

Общая схема симплекс-метода состоит из следующих основных шагов: шаг 0 . Определение начального базиса и соответствующей ему начальной угловой точки (базисного плана).

шаг 1 . Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.

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

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

шаг 4 . Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.

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

Определение . Будем говорить, что каноническая задача ЛП имеет "предпочтительный вид", если: правые части уравнений; матрица условий содержит единичную подматрицу размера.

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

Реализация симплекс-метода на примере

Продемонстрируем применение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП

f(x) = x 1 + 2x 2 + 0 x 3 + 0 x 4 > max
-x 1 + 2x 2 + x 3 = 4,
3 x 1 + 2x 2 + x 4 = 12,
x j ? 0, j = 1,2,3,4.

Матрица условий A = (A 1 , A 2 , A 3 , A 4), где

Целевой вектор c =(c 1 , c 2 , c 3 , c 4 ) = (1, 2, 0, 0); вектор правых частей b =(b 1 , b 2) = (4, 12).

Шаг 0. Нахождение начальной угловой точки (базисного плана).

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A 3, A 4 образуют единичную подматрицу. Значит начальная базисная матрица = (A 3 , A 4); x 3 и x 4 - базисные переменные, x 1 и x 2 - небазисные переменные, c Б = (c 3, c 4) = = (0, 0).

Начальный базисный план имеет вид x 0 = (0, 0, x 3 , x 4) = (0, 0, 4, 12); f(x o ) = 0.

Шаг 1. Проверка базисного плана на оптимальность.

Подсчитаем симплексные оценки для небазисных переменных по формуле (5.1)

? 1 = 1 > - c 1 = 0 ·(-1) + 0 ·3 - 1 = -1.

? 2 = 2 > - c 2 = 0 ·2 + 0 · 2 - 2 = -2.

Так как оценки отрицательны, то план x - не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

Шаг 2 . Нахождение переменной вводимой в базис.

Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x 1 или x 2 , поскольку обе оценки ? j x 2.

Шаг 3. Определение переменной выводимой из базиса.

После ввода в базис переменной x 2 новый план будет иметь вид

x" = (0, x 2, x 3 , x 4).

Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x 3 или x 4 . Подставим координаты плана x" = (0, x 2, x 3 , x 4) в ограничения задачи. Получим

2x 2 + x 3 = 4,

2x 2 + x 4 = 12.

Выразим отсюда базисные переменные x 3 и x 4 через переменную x 2 , вводимую в базис.

x 3 = 4 - 2x 2,
x 4 = 12 - 2x 2 .

Так переменные x 3 и x 4 должны быть неотрицательны, получим систему неравенств

4 - 2x 2 ? 0,
12 - 2x 2 ? 0.

Чем больше значение x 2 , тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).

Перепишем последние неравенства в виде

2x 2 ? 4,

2x 2 ? 12,

откуда максимальное значение x 2 = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x 3 и x 4 , получаем x 3 = 0. Следовательно x 3 выводится из базиса.

Шаг 4. Определение координат нового базисного плана.

Новый базисный план (смежная угловая точка) имеет вид

x" = (0, x 2, 0, x 4)

Базис этой точки состоит из столбцов A 2 и A 4 , так что = (A 2, A 4). Этот базис не является единичным, так как вектор A 2 = (2,2), и следовательно задача (2.2)-(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x 2, x 4, то есть чтобы переменная x 2 входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

- x 1 + 2 x 2 + x 3 = 4, (p 1)

3x 1 +2 x 2 + x 4 = 12. (p 2)

Поделим первое уравнение на коэффициент при x 2 . Получим новое уравнение = p 1 / 2, эквивалентное исходному

1/2 x 1 + x 2 + 1/2 x 3 = 2. ()

Используем это уравнение, которое назовем разрешающим, для исключения переменной x 2 из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p 2 . Получим = p 2 - 2 = p 2 - p 1:

4 x 1 - x 3 + x 4 = 8. ()

В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x 2 , x 4:

f (x ) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 ? max

1/2 x 1 + x 2 + 1/2 x 3 = 2 ()

4 x 1 - x 3 + x 4 = 8 ()

x j ? 0, j = 1,2,3,4

Подставляя сюда представление нового базисного плана x 1 = (0, x 2, 0, x 4), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений

x" = (0, 2, 0, 8); f (x 1)=4.

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

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

Табличная реализация простого симплекс-метода

Табличную реализацию продемонстрируем на том же примере (2.2)-(2.5).

Шаг 0 . Решение начинается с построения начальной симплекс-таблицы. Сначала заполняется правая часть таблицы с третьей колонки. В двух верхних строках записываются имена переменных задачи (x 1, ...,x 4) и коэффициенты целевой функции при этих переменных. Ниже записываются коэффициенты уравнений - элементы матрицы условий А , так что под переменной x 1 располагается столбец A 1 , под переменной x 2 - столбец A 2 и т.д. В правый столбец заносятся правые части ограничений (числа b i > 0).

Затем находим столбцы матрицы условий, образующие единичный базис - в нашем примере это A 3 и A 4 - и соответствующие им базисные переменные x 3, x 4 записываем во вторую колонку. Наконец, в первом столбце записываем коэффициенты целевой функции при базисных переменных.

Таблица 1 - Начальная симплекс-таблица

	Базисные переменные					Значения базисных перем. (x Б =b )
		x 1	x 2	x 3	x 4
	x 3	a 11 =-1
	x 4
Строка оценок ? j	? 1 = -1	? 2 = -2

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

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

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

? j = Б , A j > - c j .

? 1 = Б , A 1 > - c 1 = 0 ·(-1) + 0 ·3 - 1 = -1.

При табличной реализации для подсчета оценки ? 1 надо найти сумму произведений элементов первого столбца (c Б ) на соответствующие элементы столбца A 1 при небазисной переменной x 1 . Аналогично подсчитывается оценка ? 2 , как скалярное произведение первого столбца (c Б ) на столбец при переменной x 2 .

? 2 = 2 > - c 2 = 0 ·2 + 0 · 2 - 2 = -2.

Симплексные оценки записываются в последней строке симплекс-таблицы, которая называется дельта-строкой. При этом заполняются не только клетки при небазисных переменных, но и базисные клетки. Легко проверить, что для базисных единичных столбцов матрицы условий симплексные оценки равны нулю. В последней клетке строки оценок записываем значение целевой функции в точке x o . Заметим, что, так как небазисные координаты базисного плана равны нулю, то подсчет целевой функции удобно производить по формуле

f (x )= c Б, x Б >,

перемножая скалярно первый и последний столбцы таблицы.

Так как среди оценок ? j есть отрицательные, то план x o - не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.

Шаг 2. Поскольку обе оценки ? 1 и ? 2 то в базис можно включить любую из переменных x 1, x 2 . Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x 2 .

Столбец симплекс-таблицы, в котором находится вводимая в базис переменная называется ведущим столбцом .

В примере ведущим будет столбец при x 2 .

Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f (x ) ???. В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x 2 , при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x 2 = min{4/2, 12/2}=2.

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

Наименьшее отношение находится в строке с базисной переменной x 3. Значит переменная x 3 исключается из состава базисных переменных (x 3 = 0).

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

В примере ведущей строкой будет первая строка.

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

В нашем случае ведущий элемент a 12 = 2.

Табл. 2 - Начальная симплекс-таблица с ведущими строкой и столбцом

	Базисные перемен.					Значения базисных перем.	Уравнения
			x 2
c 3 =0	x 3	-1	2	1	0	4
			2
Строка оценок ? j	? 1 = -1	? 2 = -2

Шаг 4 . Для получения нового базисного плана приведем задачу к новому предпочтительному виду относительно новых базисных переменных.

Для этого построим новую симплекс-таблицу, во втором столбце которой вместо исключаемой переменной x 3 запишем новую базисную переменную x 2 , а в первом столбце (с Б ) вместо с 3 запишем коэффициент целевой функции при x 2 : c 2 =2 . В новой симплекс таблице столбец при x 2 должен стать единичным (ведущий элемент должен равняться единице, а все остальные элементы должны обратиться в ноль). Это достигается следующими преобразованиями строк таблицы.

a. Все элементы ведущей строки делим на ведущий элемент и записываем в той же строке новой симплекс- таблицы.

Полученную строку p 1 " назовем разрешающей.

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

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

c. Заполним последнюю строку, вычислив оценки ? j " = - - c j , где c Б ", A j " - соответствующие столбцы новой симплекс-таблицы, и значение целевой функции f(x)= .

Получим вторую симплекс-таблицу с новым базисом.

Таблица 3 - Результат первой итерации

	Базисные перемен.					Значения базисных перем.	Уравнения
		-1/2
	x 4	4	0	-1	1	8	p 2 " =p 2 - p 1
оценки ? j "	-2

Новый базисный план x " = (0, x 2 , 0, x 4) = (0, 2, 0, 8 ). Поскольку оценка ? 1 = -2 то план x " не оптимален. Для перехода к новому базисному плану (соседней угловой точки) проведем еще одну итерацию симплекс - метода.

Так как ? 1 то в базис вводится переменная x 1 . Первый столбец, содержащий x 1 - ведущий.

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

Выделяем ведущий столбец и ведущую строку и на их пересечении находим ведущий элемент (= 4) .

Строим новую (третью) симплекс-таблицу, заменяя в ней базисную переменную x 4 на x 1 , и снова преобразуя строки таблицы таким образом, чтобы ведущий элемент стал равным единице, а остальные элементы ведущего столбца обратились в ноль. Для этого ведущую (вторую) строку делим на 4, а к первой строке прибавляем полученную вторую строку, деленную на 2. Последнюю строку вычисляем по формулам для симплексных оценок ? j "" = "", A j "" > - c j , где c Б "", A j "" - соответствующие столбцы новой симплекс-таблицы. Значение целевой функции на новом базисном плане находим по формуле f(x "")= "", x Б "" >.

Таблица 4 - Результат второй итерации

	Базисн. перемен.					Значения базисных перем.	уравнения
							p 1 ""= p 1 "+p 2 ""/2
							p 2 "" = p 2 "/4
оценки ? j ""					f(x "")= 8

Новый базисный план x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Поскольку все оценки неотрицательны, то план x "" - оптимальный план.

Таким образом, x* = (2, 3, 0, 0 ), f(x*) = 8.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Ашманов С.А. Линейное программирование. - М.: Наука, 1981.

Универсальный метод решения задач ЛП называется симплекс-методом. Применение этого метода и его наиболее часто встречающейся модификации - двухфазного симплекс-метода мы поясним на примерах.
Пример . Решить следующую задачу ЛП в канонической форме симплекс-методом. (5.5) (5.6)
x i ≥ 0, i = 1,…,6 (5.7)
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.
Решение. Чтобы найти начальное допустимое базисное решение, т.е. чтобы определить базисные переменные, систему (5.6) нужно привести к "диагональному" виду. Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5.6): (5.8)
Следовательно, базисными являются переменные x 2 , x 4 , x 5 , x 6 , им придаем значения, равные свободным членам соответствующих строк: x 2 =40, x 4 =20, x 5 =10, x 6 =30, . Переменные x 1 и x 3 являются небазисными: x 1 =0, x 3 =0 .
Построим начальное допустимое базисное решение
x 0 = (0,40,0,20,10,30) (5.9)
Для проверки на оптимальность найденного решения x 0 нужно из целевой функции исключить базисные переменные (с помощью системы (5.8)) и построить специальную симплекс таблицу.
После исключения переменных целевую функцию удобно записать в виде:
f(x) = -7x 1 – 14x 3 +880 (5.10)
Теперь при помощи (5.8) –(5.10) составляем начальную симплекс-таблицу:

В нулевую строчку записаны коэффициенты с обратным знаком соответствующих переменных при целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(x 0 ) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так что начальное допустимое базисное решение (5.9) неоптимально: 7>0, 14>0 .
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. уравнение (5.7)). От первой по четвертую строки написаны коэффициенты переменных из системы (5.8).
Так как x 0 неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).
Сначала находим ведущий элемент таблицы, который стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В таблице 1 ведущий столбик - третий столбик, и ведущая строка - четвертая строка (min{40/1,30/1}=30/1) обозначены стрелками, а ведущий элемент - кружочком. Ведущий элемент показывает, что базисную переменную x 6 нужно заменить на небазисную x 3 . Тогда новыми базисными переменными будут x 2 , x 3 , x 4 , x 5 , , а небазисными -x 1 , x 6 , . Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения x 00 нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x 2 , x 3 , x 4 , x 5 , (см. таблицу 2) - базисные компоненты новой вершины x 00 (небазисные компоненты x 1 =0, x 6 =0, ).

Как показывает таблица 2, новое базисное решение x 00 =(0,10,30,20,40,0) неоптимально (в нулевой строке есть неотрицательная оценка 7). Поэтому с ведущим элементом 1 (см. таблицу 2) строим новую симплекс-таблицу, т.е. строим новое допустимое базисное решение

Таблице 3 соответствует допустимое базисное решение x 000 =(10,0,30,10,50,0) и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому f(x 000)=390 есть минимальное значение целевой функции.
Ответ: x 000 =(10, 0, 30, 10, 50, 0) - точка минимума, f(x 000)=390 .