Одним из универсальных методов явл-ся симплесный метод. В симплексном м-де осущ-ся направленный перебор опорных планов, в том смысле, что при переходе от одного опорного плана к другому целевая функция возрастает. Пусть задача записана в канонической форме:
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=<λ<=λ
Рассмотрим универсальный метод решения канонической задачи линейного программирования
с n переменными и m ограничениями-равенствами, известный как симплекс-метод.
Множество планов канонической задачи - выпуклое многогранное множество, имеющее конечное число угловых точек. И если эта задача имеет оптимальное решение, то оно достигается хотя бы в одной угловой точке.
С любой угловой точкой связан базисный план задачи, в котором переменных равны нулю, а оставшимся переменным соответствуют линейно независимые столбцы матрицы условий. Эти линейно независимые столбцы образуют невырожденную базисную матрицу.
Перебор всех угловых точек сопряжен с большими вычислительными затратами и поэтому не эффективен. В 1947 году Дж. Данциг предложил упорядоченную процедуру перебора угловых точек, при которой для нахождения оптимального решения достаточно исследовать лишь небольшую их часть. Эта процедура называется симплекс-методом .
Дж. Данциг предложил при переходе от одной крайней точки к другой заменять в базисной матрице всего один вектор. Это означает, что при таком переходе мы должны одну из базисных переменных исключить - сделать ее небазисной (равной нулю), а на ее место ввести новую переменную из числа небазисных (нулевых) - сделать ее базисной (положительной).
Оказывается, геометрически такая замена приводит к переходу от одной угловой точки к смежной (соседней), связанной с предыдущей точкой общим ребром.
Из всех соседних точек выбирается та, в которой целевая функция возрастает более всего. Поскольку число угловых точек конечно, через конечное число переходов будет найдена вершина с наибольшим значением целевой функции, либо будет установлена неограниченность целевой функции на неограниченном множестве планов.
Общая схема симплекс-метода состоит из следующих основных шагов.
· шаг 0 . Определение начального базиса и соответствующей ему начальной угловой точки (базисного плана) .
· шаг 1 . Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.
· шаг 2 . Нахождение переменной, вводимой в состав базисных. (Из условия увеличения целевой функции).
· шаг 3 . Нахождение переменной, исключаемой из состава базисных переменных (Из условия сохранения ограничений задачи).
· шаг 4 . Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.
Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.
Из этой схемы следует, что во-первых, для начала работы симплекс-метода надо иметь какую-то угловую точку - начальный базисный план, а во-вторых, надо уметь исследовать текущую угловую точку на оптимальность, не вычисляя всех смежных вершин. Эти проблемы легко решаются, если каноническая задача ЛП имеет некий специальный вид.
Определение . Будем говорить, что каноническая задача ЛП имеет "предпочтительный вид", если
1. правые части уравнений, .
2. матрица условий содержит единичную подматрицу размера
Другими словами, в любом уравнении есть переменная с коэффициентом равным единице, отсутствующая в остальных уравнениях. Первое условие не является обременительным, так как в случае отрицательной правой части некоторого уравнения, достаточно умножить его на (-1). В задаче предпочтительного вида начальный базисный план находится очень просто.
Пример 2.1.
Матрица условий A и вектор правых частей ограничений b имеют вид
а целевой вектор с = (1, -3, 0, 4, 2).
Сразу очевидна одна базисная матрица: с единичными векторами условий.
Следовательно, выбирая в качестве базисных переменных x 1 , x 3 , x 5 , и полагая в системе уравнений x 2 = x 4 = 0 (небазисные переменные), немедленно находим x 1 = 10, x 3 = 20, x 5 = 8, так что начальный базисный план x 0 = (10, 0, 20, 0, 8). Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей b i .
В дальнейшем, базисные переменные будем объединять в вектор x Б.
Таким образом, в канонической задаче предпочтительного вида в качестве начальной базисной матрицы берется единичная подматрица A Б = E , а соответствующие ей базисные переменные равны правым частям ограничений:
x Б = b .
Для базисного плана такого вида может быть сформулирован достаточно простой для проверки критерий оптимальности. Введем величины
? j = < с Б , A j > - c j , j = 1,...,n, (2.1)
где с Б - вектор из коэффициентов целевой функции при базисных переменных x Б , A j - j- й столбец матрицы условий, c j - j- й коэффициент целевой функции. Разности ? j называются симплексными разностями или симплексными оценками.
Критерий оптимальности базисного плана . Если для базисного плана с единичной базисной матрицей все симплексные оценки неотрицательны, то этот план оптимален.
Применим данный критерий для проверки на оптимальность базисного плана x 0 = (10, 0, 20, 0, 8) из примера 2.1.
Так как в этом плане вектор базисных переменных x Б =(x 1 , x 3 , x 5 ), то с Б = (c 1 , c 3 , c 5 ) = (1, 0, 2).
Следовательно,
? 1 = < с Б , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,
2 = < сБ, A2 > - c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,
? 3 = < с Б , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,
? 4 = < с Б , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,
? 5 = < с Б , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.
Так как оценка ? 4 < 0, то базисный план x 0 не оптимален. Заметим, что симплексные оценки, соответствующие базисным переменным, всегда равны нулю, так что достаточно проверять только небазисные оценки.
Лекция 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) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент –строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на следующем шаге вновь обращаются к–строке. Если задача разрешима, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.
Если в форму ЗЛП облечена некоторая реальная производственная ситуация, то дополнительные переменные, которые приходится вводить в модель в процессе преобразования ее к канонической форме, всегда имеют определенный экономический смысл.
Можно организовать перебор только допустимых базисных решений и число перебираемых решений резко сократить, если каждое следующее допустимое базисное решение выбирать так, чтобы соответствующее значение целевой функции улучшалось или хотя бы не ухудшалось. Такой подход позволяет сократить число шагов при отыскании оптимального базисного решения. Эту идею поясним графически.
Геометрический смысл симплекс–метода состоит в том, что выполняется последовательный переход от одной вершины многогранника допустимых решений задачи к соседней, в которой целевая функция принимает значение не худшее, чем в предыдущей вершине. Этот переход продолжается до тех пор, пока не будет найдено оптимальное решение или не будет обнаружено, что задача его не имеет.
Симплекс-метод заключается в нахождении и тестировании вершины (угла), являющейся решением задачи ЛП . На каждом этапе метод выделяет вершину и соответствующие ей переменные, которые обеспечивают движение к минимуму (максимуму) с наибольшей скоростью. Выбранная переменная заменяет другую, наиболее ограничивающую. Симплекс-метод позволяет также определить, существует ли решение. Реализующий симплекс-метод алгоритм можно записать в виде:
Шаг 1. Определяется некоторая вершина в ОДР, соответствующая базисным допустимым решениям (переменным), найденным путем выделения из матрицы т - линейно независимых столбцов и приравнивания нулю всех других переменных, соответствующих другим столбцам матрицы.
Шаг 2. Выбирается из всех возможных оставшихся п - т ребер, соответствующих небазисным переменным, ребро (переменная), которое приводит при движении по нему к наискорейшему уменьшению целевой функции.
Шаг 3. Осуществляется как бы движение от начальной вершины вдоль выбранного ребра к другой вершине, которая дает новое решение, имеющее меньшее значение ЦФ. Новая вершина образуется путем замены базисной переменной (ребра) на новую базисную переменную (ребро).
Столбцы и элементы векторов обычно упорядочиваются и записываются в виде симплекс-таблицы, образование которой будет показано ниже.
Симплекс-метод решает задачу Л П в стандартной форме.
Минимизировать (максимизировать) функцию при условиях х > 0; Ах = Ь.
Матрица А действительная, имеет размерность т х «и ранг т.
Сформулированную задачу ЛП можно также записать в виде
Исходя из записи задачи ЛП в виде (8Л) можно сказать, что расширенная матрица
размерности (т + 1) (п + 2) соответствует решениям[х/] т.
Представим матрицу А в виде совокупности столбцов
Так как матрица А имеет ранг т, то найдутся т линейно независимых столбцов матрицы А, например {а У1 ,...,а У/и Рассмотрим вектор х° > 0, такой, что все его п - т элементов равны 0 и Ах° = Ь. Пусть это будут элементы с номерами... , i n _ m . Предположим также, что место расположения aw линейно независимых столбцов матрицы А соответствует месту расположения ненулевых элементов векторах 0 . Геометрически, согласно утверждению 3 § 7.6, это означает, что х° является вершиной (углом) ОДР и, кроме того, удовлетворяет заданным условиям. Такое решение называется допустимым базисным решением. Углы допустимого множества являются допустимыми базисными решениями.
Напомним, что множество базисных решений содержит всю информацию, необходимую для оптимального решения задачи ЛП. Для рассмотренного в § 7.6 двумерного случая базисными решениями являются все 6 точек, а допустимыми базисными решениями являются точки Л, В, Си 0.
Таким образом, любой аналогичный х° вектор х можно записать как
где х в - вектор, элементы которого сответствуют линейно независимым столбцам матрицы A; x F - вектор с нулевыми элементами.
Аналогично определим векторы
Переменные, являющиеся элементами вектора х в, называются базисными переменными, а переменные, являющиеся элементами вектора x F , называются свободными (небазисными) переменными.
Так как x° F =0, то значение целевой функции для начального вектора х° будет равно
где/° - значение /в точке х°.
Решение (8.1) вида [х°/°] т при х > 0 называется очевидным {явным) решением. Таким образом, если приравнять нулю небазисные переменные, получается очевидное решение.
Для удобства переставим т линейно независимых столбцов матрицы А в левую часть и запишем матрицу в виде
Здесь матрица В соответствует т линейно независимым столбцам имеет размерность тх т и ранг т, а матрица F
является тх (п - т) матрицей. Так как матрица В состоит из линейно независимых столбцов, то она имеет обратную В -1 и detB ф 0. Отметим, что для образования матрицы В можно выбрать любые т линейно независимых столбцов матрицы А.
Представим задачу (8.1) с учетом введенных обозначений
Данному представлению соответствует расширенная матрица Предположим, что
откуда следует
Если вектор х в будет решением системы Вх й =Ь, то он будет базисным решением. Если выполняется неравенство в = В -1 Ь > О, тогда х в будет допустимым решением.
Таким образом, текущее решение удовлетворяет следующему уравнению:
Рассмотрим матрицу (8.4). Базисные переменные будут представлены в явном виде, если заменить матрицу В единичной матрицей I. Умножив первую строку матрицы (8.4) слева на В~ 1 , получим
где В _1 Ь > О, т.е. т верхних элементов в правом столбце неотрицательны и представляют собой текущее значение переменных.
В левой стороне верхней строки получилась единичная матрица: В -1 В = I. Данное представление очень удобно, так как при умножении на вектор х в каждая переменная будет находиться в отдельной строке.
Таким образом, базисное решение, которое будем считать допустимым и соответствующим базису В, есть х т = [х в 0], где х в = = В _1 Ь. Базисное решение является результатом предположения, что x F = 0. Однако, если x F * 0, то х^может быть вычислено какх 5 = = B~"b - B^"Fx/r. Подставив это выражение в целевую функцию (функцию стоимости), получим
Так как необходимо определить зависимость стоимости от небазисных переменных, одну из которых затем включить в базисные, то нижняя строка под матрицей I должна быть нулевой. Для этого в (8.7) умножим первую строку (матрицы) на с в и сложим со второй
где - значение целевой функции для начального век
тора х 0 из (8.3).
Матрица (8.8) называется симплекс-таблицей. Приведение ее к данному виду является начальным этапом симплекс-алгоритма. В процессе выполнения алгоритма осуществляется переход от одной таблицы к другой, пока нижний правый элемент таблицы не станет максимальным или минимальным.
С использованием симплекс-таблицы легко увидеть допустимое решение. Переменные x F соответствуют нулевой подматрице, переменные х в - единичной матрице:
Предположим, что задача Л П приведена к стандартной форме, вычислена симплекс-таблица и выбрано начальное базисное решение, соответствующее вершине многогранника решений.
Тогда - решение задачи (8.1). Так
как b > О, это решение базисное допустимое.
Представим матрицу (8.9) в более удобном виде, сохранив основные обозначения:
Рассмотрим отдельно задачи максимизации и минимизации.