Контакты
Главная / BSoD

Допустимым решением злп является. Графический метод оптимизации линейных моделей. Каноническая форма задачи линейного программирования

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

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

В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel " Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:

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

Параметры задач ограничиваются такими предельными показателями:

  • количество неизвестных – 200;
  • количество формульных ограничений на неизвестные – 100;
  • количество предельных условий на неизвестные – 400.

Алгоритм поиска оптимальных решений включает в себя несколько этапов:

  • подготовительные работы;
  • отладка решения;
  • анализ решения .

Последовательность необходимых подготовительных работ , выполняемых при решении задач экономико-математического моделирования с помощью MS Excel , приведена на блок-схеме рисунка 1.6 .


Рис. 1.6.

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

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

Кроме того, всегда известны значения ресурсов . В предыдущем примере это был недельный запас досок и возможности использовать машинное время: , . Часто в задачах значения переменных требуется ограничить. Поэтому нужно определить нижний и верхний пределы области их изменений.

Таким образом, в диалоговом окне оптимизационной программы " Поиск решения" мы должны задать следующий целевой алгоритм :

Целевая функция равна произведению вектора искомых значений переменных на вектор целевых коэффициентов

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

Значения переменной должны находиться в заданных пределах число исходных элементов системы

Число исходных элементов системы

Число заданных видов ресурсов

Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):


Рис. 1.7.
  • если не получено допустимое решение, то выполнить корректировку модели исходных данных;
  • если не получено оптимальное решение , то ввести дополнительные ограничения.

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

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

Экономический анализ ставит перед собой следующие цели :

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

Возможные методы анализа представлены в схеме на рисунке 1.8 .

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

Учитывая ответственность принятия экономического управленческого решения , руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:

  • "что будет, если…"
  • "что надо, чтобы…"

Анализ с целью ответа на первый вопрос называется вариантным анализом ; анализ с целью ответа на второй вопрос называется решениями по заказу.

Вариантный анализ бывает следующих видов:

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

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

Задача линейного программирования (ЗЛП) − это задача нахождения наибольшего (или наименьшего) значения линейной функции на выпуклом многогранном множестве.

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

Рассмотрим следующую задачу линейного программирования в канонической форме:

(1)
(2)
(3)

Метод искусственного базиса

Как было паказано выше, для задачи, записанной в канонической форме, если среди векторов столбцов матрицы A есть m единичных и линейно независимых , можно непосредственно указать опорный план. Однако для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, среди векторов столбцов матрицы A не всегда есть m единичных и линейно независимых. Рассмотрим такую задачу:

Пусть требуется найти максимум функции

при условиях

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

(28)

образуют так называемый искусственный базис m -мерного векторного пространства.

Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.

Теорема 4. Если в оптимальном плане расширенной задачи (24)−(26) значения искусственных переменных , то является оптимальным планом задачи (21)−(23).

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

Значение целевой функции при опорном плане (27):

Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.

После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m +1)-ю строку помещают коэффициенты, не содержащие M , а в (m +2)-ю строку − коэффициенты при M .

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

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

m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.

Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.

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

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

Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:

  • Составляют расширенную задачу (24)−(26).
  • Находят опорный план расширенной задачи.
  • Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
  • Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.

Для решения задач линейного программирования онлайн, пользуйтесь калькулятором

Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

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

  • - задача об оптимальном использовании ресурсов при производственном планировании;
  • - задача о смесях (планирование состава продукции);
  • - задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
  • - транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
  • - математические модели большого числа экономических задач линейны относительно искомых переменных;
  • - данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
  • - многие задачи линейного программирования, будучи решенными, нашли широкое применение;
  • - некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных. В общем виде модель записывается следующим образом:
  • - целевая функция:

C1x1 + c2x2 + ... + cnxn > max(min);- ограничения:

a11x1 + a12x2 + ... + a1nxn {? = ?} b1,

a21x1 + a22x2 + ... + a2nxn {? = ?} b2

am1x1 + am2x2 + ... + amnxn {? = ?} bm;

Требование неотрицательности:

При этом aij, bi, cj () - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор, удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

1. Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей. Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

По данному условию сформулируем задачу линейного программирования. Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП:

4x1 + 6x2 ? 120,

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Система переменных величин в задаче по оптимизации структуры посевных площадей с учётом севооборотов

Основой для решения экономических задач являются математические модели.

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

Составление математической модели включает:
  • выбор переменных задачи
  • составление системы ограничений
  • выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X 1 , X 2 ,...,X n).

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

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

В общем случае задача линейного программирования может быть записана в таком виде:

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X 1 , X 2 ,...,X n) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X 1 , X 2 ,...,X n), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

Пример составления математической модели

Задача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

  • b i (i = 1,2,3,...,m) — запасы каждого i-го вида ресурса;
  • a ij (i = 1,2,3,...,m; j=1,2,3,...,n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
  • c j (j = 1,2,3,...,n) — прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X 1 , X 2 ,...,X n), где x j (j = 1,2,...,n) — объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема x j продукции равны a ij x j , поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна c j x j , поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

Каноническая форма задачи линейного программирования

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

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

Она может быть представлена в координатной, векторной и матричной записи.

Каноническая задача линейного программирования в координатной записи имеет вид:

Каноническая задача линейного программирования в матричной записи имеет вид:

  • А — матрица коэффициентов системы уравнений
  • Х — матрица-столбец переменных задачи
  • Ао — матрица-столбец правых частей системы ограничений

Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной записи имеют вид:

Приведение общей задачи линейного программирования к канонической форме

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a 1 x 1 +a 2 x 2 +...+a n x n ≤b и прибавим к его левой части некоторую величину x n+1 , такую, что неравенство превратилось в равенство a 1 x 1 +a 2 x 2 +...+a n x n +x n+1 =b. При этом данная величина x n+1 является неотрицательной.

Рассмотрим все на примере.

Пример 26.1

Привести к каноническому виду задачу линейного программирования:

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x 4 x 5 (на математической модели эта операция отмечена буквой Д).
Переменная х 4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x 5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x 4 x 5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде.

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам

и обращающие в максимум линейную функцию этих переменных

Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда.

ЗЛП неразрешима (не имеет оптимального решения):

Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.

Рисунок 1 - Несовместность системы ограничений

Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.

Рисунок 2 - Неограниченность целевой функции на множестве решений

ЗЛП разрешима:

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

Рисунок 3 - Множество решений состоит из одной точки

Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.

Рисунок 4 - Единственное оптимальное решение

Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.

Рисунок 5 - Оптимальное решение не единственно

Решение задач линейного программирования симплекс-методом

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

Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:

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

Алгоритмический характер метода позволяет успешно программировать и реализовать его с помощью технических средств.

Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции .

Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

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

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

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

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

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

Таким образом, применение симплексного метода распадается на два этапа:

Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

Нахождение оптимального решения в случае совместности системы ограничений.

Алгоритм перехода к следующему допустимому решению следующий:

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

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

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

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

Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов .