Лекция 3. Симплексные таблицы. Алгоритм симплексного метода.
§ 3 СИМПЛЕКСНЫЙ МЕТОД
3.1. Общая идея симплекс–метода. Геометрическая интерпретация
Графический способ применим к весьма узкому классу задач линейного программирования: эффективно им можно решать задачи, содержащие не более двух переменных. Были рассмотрены основные теоремы линейного программирования, из которых следует, что если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Был указан путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор в конце концов приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Число перебираемых
допустимых базисных решений можно
сократить, если производить перебор не
беспорядочно, а с учетом изменений
линейной функции, т.е. добиваясь того,
чтобы каждое следующее решение было
"лучше" (или, по крайней мере, "не
хуже"), чем предыдущее, по значениям
линейной функции (увеличение ее при
отыскании максимума
,
уменьшение–
при отыскании минимума
).
Такой
перебор позволяет сократить число шагов
при отыскании оптимума. Поясним это
на графическом примере.
Пусть область допустимых решений изображается многоугольником ABCDE . Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать пять допустимых базисных решений, соответствующих пяти угловым точкам многоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем – к оптимальной точке С. Вместо пяти перебрали только три вершины, последовательно улучшая линейную функцию.
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования – симплексного метода или метода последовательного улучшения плана.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение по отношению к цели задачи; до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:
способ определения какого-либо первоначального допустимого базисного решения задачи;
правило перехода к лучшему (точнее, не худшему) решению;
критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
В литературе достаточно подробно описываются: нахождение начального опорного плана (первоначального допустимого базисного решения), тоже – методом искусственного базиса, нахождение оптимального опорного плана, решение задач с помощью симплексных таблиц.
3.2. Алгоритм симплекс–метода.
Рассмотрим решение ЗЛП симплекс-методом и изложим ее применительно к задаче максимизации.
1. По условию задачи составляется ее математическая модель.
2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.
3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.
Симплекс
таблица: вписывается система ограничительных
уравнений и целевая функция в виде
выражений, разрешенных относительно
начального базиса. Строку, в которую
вписаны коэффициенты целевой функции
,
называют
–строкой
или строкой целевой функции.
4.
Находят начальный опорный план, производя
симплексные преобразования с положительными
разрешающими элементами, отвечающими
минимальным симплексным отношениям, и
не принимая во внимание знаки элементов
–строки.
Если в ходе преобразований встретится
0-строка, все элементы которой, кроме
свободного члена, нули, то система
ограничительных уравнений задачи
несовместна. Если же встретится 0-строка,
в которой, кроме свободного члена, других
положительных элементов нет, то система
ограничительных уравнений не имеет
неотрицательных решений.
Приведение системы (2.55), (2.56) к новому базису будем называть симплексным преобразованием . Если симплексное преобразование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входящими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая наоборот – из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.
5. Найденный начальный опорный план исследуется на оптимальность:
а) если в
–строке
нет отрицательных элементов (не считая
свободного члена), то план оптимален.
Если при этом нет и нулевых, то
оптимальный план единственный; если же
есть хотя бы один нулевой, то оптимальных
планов бесконечное множество;
б) если в
–строке
есть хотя бы один отрицательный элемент,
которому соответствует столбец
неположительных элементов, то
;
в) если в
–строке
есть хотя бы один отрицательный элемент,
а в его столбце есть хотя бы один
положительный, то можно перейти к
новому опорному плану, более близкому
к оптимальному. Для этого указанный
столбец надо назначить разрешающим, по
минимальному симплексному отношению
найти разрешающую строку и выполнить
симплексное преобразование. Полученный
опорный план вновь исследовать на
оптимальность. Описанный процесс
повторяется до получения оптимального
плана либо до установления неразрешимости
задачи.
Столбец коэффициентов
при переменной, включаемой в базис,
называют разрешающим. Таким образом,
выбирая переменную, вводимую в базис
(или выбирая разрешающий столбец) по
отрицательному элементу
–строки,
мы обеспечиваем возрастание функции
.
Немного сложней определяется переменная, подлежащая исключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует, как уже установлено, положительность базисных компонент в новом опорном плане.
В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обязательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разрешающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:
1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например –строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагаем, что ограничения задачи совместны);
2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);
3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р –строка;
4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент –строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на следующем шаге вновь обращаются к–строке. Если задача разрешима, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.
Если в форму ЗЛП облечена некоторая реальная производственная ситуация, то дополнительные переменные, которые приходится вводить в модель в процессе преобразования ее к канонической форме, всегда имеют определенный экономический смысл.
Можно организовать перебор только допустимых базисных решений и число перебираемых решений резко сократить, если каждое следующее допустимое базисное решение выбирать так, чтобы соответствующее значение целевой функции улучшалось или хотя бы не ухудшалось. Такой подход позволяет сократить число шагов при отыскании оптимального базисного решения. Эту идею поясним графически.
Геометрический смысл симплекс–метода состоит в том, что выполняется последовательный переход от одной вершины многогранника допустимых решений задачи к соседней, в которой целевая функция принимает значение не худшее, чем в предыдущей вершине. Этот переход продолжается до тех пор, пока не будет найдено оптимальное решение или не будет обнаружено, что задача его не имеет.
Нахождение оптимального плана. Этот метод является универсальным, он позволяет решать задачи линейного программирования любой размерности в общей постановке. Однако такой метод требует приведения исходной задачи к каноническому виду.
Основная идея симплекс-метода заключается в том, чтобы так переходить от одной вершины ОДР к другой, чтобы при каждом переходе значение ЦФ уменьшалось. Именно так из любой вершины можно добраться до оптимальной и получить оптимальный план.
Например: пусть известен опорный план 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
…………………………..
Одним из универсальных методов явл-ся симплесный метод. В симплексном м-де осущ-ся направленный перебор опорных планов, в том смысле, что при переходе от одного опорного плана к другому целевая функция возрастает. Пусть задача записана в канонической форме:
f=(n; j=1)ΣCj*Xj (max)
(n;j=1)Σaij*xj=aio (i=1,m)
Xj>=0 (j=1,n)
Если задача разрешима, то ее оптимальный план совпадает по крайней мере с одним из опорных решений с-мы уравнений. Именно этот опорный план и отыскивается симплекс-методом в результате упорядоченного перебора опорных планов. Упорядоченность понимается в том смысле, что при переходе от одного опорного плана к другому соответствующие им значения целевой функции возрастают. Поэтому симплекс-метод наз-ют м-дом последовательного улучшения плана .
Общая идея симпл.метода состоит в том что симпл. м-д разбивается на 2 этапа:
1. нахождение начального опорного плана;
2. последовательное улучшение вплоть до нахождения оптимального, в котором целевая функция достигает максим.значения.
8. Признак оптимальности опорного плана ЗЛП.
Признак опорного плана явл-ся неотрицательность элементов столбца свободных членов, не считая элементов f-строки. Признаком оптимального плана - если в симплексной таблице содержится опорный план, все элементы f-строки, которые неотрицательны (не считая свободного члена bоо), то этот опорный план является оптимальным. Если в соотношении f=boo-(n-m;j=1)Σboj*Xj+m значение всех свободных переменных равно нулю, то целевая функция будет равна свободному члену f(векторXo)=boo. При увеличении значений свободных переменных функция начнет умен-ся, следовательно при плане Хо функция принимает экстремальное значение.
9. Нахождение начального опорного плана ЗЛП.
Для нахождения начального опорного плана можно предложить следующий алгоритм:
1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1.
-x1 ….. -xn | ||
0= | a1o | a11 …. a1n |
….. | ….. | ……………………….. |
0= | amo | am1 ….. amn |
f= | -c1 …. -cn |
Таблицу преобразовывать шагами жордановых исключений, замещая нули в левом столбце соответствующими х. При этом на каждом шаге разрешающим может быть выбран любой столбец, содержащий хотя бы один положительный элемент. Разрешающая строка определяется по наименьшему из отношений свободных членов к соответствующем положительным элементам разрешающего столбца. Если в процессе исключений встретится 0-строка, все элементы которой- нули, а свободный член отличен от нуля, то с-ма ограничительных уравнений решений не имеет. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то с-ма ограничительных уравнений не имеет неотрицательных решений Если с-ма ограничительных уравнений совместна , то через некоторое число шагов все нули в левом столбце будут замещены х и тем самым получен некоторый базис, а следовательно, и отвечающий ему опорный план.
10. Нахождение оптимального опорного плана ЗЛП.
Начальный опорный план Хо исследуется на оптимальность.
Если в f-строке нет отрицательных элементов (не считая свободного члена), -план оптимален. Если в f- строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество. Если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области. Задача не разрешима. Если в f- строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отриц-ом элементом в f-строке берут за разрешающий ; опред-ют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуется на оптимальность. Это повторяется до тех пор, пока не будет найден оптимальный опорный план либо установлена неразрешимость задачи.
11. Признак неограниченности целевой функции на множестве планов и геометрическая иллюстрация.
Признаком неограниченности целевой функции является получение в процессе поиска оптимал-го плана столбца с отрицательном элементом в f-строке, не содержащего ни одного положит.элемента.
12. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация.
Признаком бесконечности множ-ва планов явл-ся наличие в f-строке симплексной т-це, содержащей оптимал.план, хотя бы одного нулевого элем-та не считая свободного члена. Пусть найден оптим.план Х1*, при чем в f-строке один нулевой элемент. Другой оптим.план Х2* можно найти, выбрав в качестве разреш-го столбец с нулевым элементом в f-строке. Остальные оптим. планы можно определить как линейную комбинацию:
Х1*= λХ1*+(1-λ)Х2* 0=<λ<=λ
Универсальный метод решения задач ЛП называется симплекс-методом. Применение этого метода и его наиболее часто встречающейся модификации - двухфазного симплекс-метода мы поясним на примерах.
Пример
. Решить следующую задачу ЛП в канонической форме симплекс-методом.
(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
.